Majid Al-RaimiHuffman coding, the Deep Compression pipeline and SqueezeNetترميز Huffman وخط عمل Deep Compression وSqueezeNet

COE 592Lecture 5.1المحاضرة 5.1Part 07الجزء 07

Huffman coding, the Deep Compression pipeline and SqueezeNetترميز Huffman وخط عمل Deep Compression وSqueezeNet

Variable-length Huffman codes exploit the uneven usage of the 32 effective weights. Deep Compression chains pruning, K-means quantization and Huffman coding for 35x to 49x reduction with no accuracy loss, and stacks on SqueezeNet for a 510x smaller model than AlexNet.رموز Huffman متغيرة الطول تستغل الاستخدام غير المتساوي للأوزان الفعلية الـ32. يربط Deep Compression التقليم وتكميم K-means وترميز Huffman لتخفيض من 35x إلى 49x دون فقدان في الدقة، ويُطبَّق فوق SqueezeNet لنموذج أصغر بـ510x من AlexNet.

Conceptsالمفاهيم
5
Slidesالشرائح
37-41
Readingمدة القراءة
30 min30 دقيقة
Understoodما فهمته
0/5 conceptsمفاهيم

Why this part mattersلماذا يهمّ هذا الجزء

Parts 05 and 06 turned every FP32 weight into a short cluster index that points into a small codebook. That already gives roughly 32/N compression for N-bit indexes. This part asks what is left to squeeze, and answers it three ways: encode the indexes more cleverly, chain quantization with pruning into one pipeline, and start from an architecture that needs fewer weights in the first place.

The pipeline is Deep Compression (Han, Mao and Dally, ICLR 2016), and its stage order, what each stage reduces and the headline ratios are the most examinable facts in this lecture. SqueezeNet then shows that a compact design and compression stack on top of each other, which is exactly the reasoning you need when a model has to fit in the on-chip memory of an embedded device.

حوّل الجزآن 05 و06 كل وزن FP32 إلى فهرس عنقود (cluster index) قصير يشير إلى codebook صغير. وهذا وحده يعطي ضغطاً بنحو 32/N عندما تكون الفهارس بطول N بت. يسأل هذا الجزء: ماذا بقي لنضغطه؟ ويجيب بثلاث طرق: ترميز الفهارس بذكاء أكبر، وربط الـ quantization مع الـ pruning في خط معالجة واحد، والبدء من معمارية تحتاج إلى أوزان أقل من الأساس.

خط المعالجة هذا اسمه Deep Compression (Han, Mao and Dally, ICLR 2016)، وترتيب مراحله، وما الذي تقلّله كل مرحلة، والنسب الرئيسية، هي أكثر الحقائق احتمالاً للظهور في الاختبار من هذه المحاضرة. ثم يبيّن SqueezeNet أن التصميم المدمج والضغط يتراكمان فوق بعضهما، وهذا بالضبط نوع التفكير الذي تحتاجه عندما يجب أن يتسع النموذج في الذاكرة الموجودة على الشريحة (on-chip memory) لجهاز مدمج.

By the end you canفي نهاية هذا الجزء ستستطيع

  1. Build a Huffman code by hand for a small alphabet and compute its average code length against a fixed-length code.أن تبني رمز Huffman يدوياً لأبجدية صغيرة، وتحسب متوسط طول الرمز مقارنةً برمز ثابت الطول.
  2. Explain why Huffman coding helps on quantized weights and sparse indexes, and why it is lossless.أن تشرح لماذا يفيد ترميز Huffman مع الأوزان المكمّاة (quantized) ومع الفهارس المتناثرة (sparse indexes)، ولماذا هو بلا فقد (lossless).
  3. Name the three Deep Compression stages in order, what each one reduces, and the cumulative 9x to 13x, 27x to 31x and 35x to 49x ranges.أن تسمّي مراحل Deep Compression الثلاث بالترتيب، وما الذي تقلّله كل مرحلة، والنطاقات التراكمية 9x إلى 13x ثم 27x إلى 31x ثم 35x إلى 49x.
  4. Read the six-network results table and explain why GoogleNet and ResNet-18 compress only 10x to 11x.أن تقرأ جدول نتائج الشبكات الست، وتشرح لماذا لا يتجاوز ضغط GoogleNet وResNet-18 ما بين 10x و11x.
  5. Count the weights in a SqueezeNet fire module and compare them with a plain 3x3 convolution.أن تعدّ الأوزان في fire module الخاصة بـ SqueezeNet وتقارنها بطبقة convolution عادية بحجم 3x3.
  6. Explain why SqueezeNet plus Deep Compression reaches 510x: architecture and compression multiply.أن تشرح لماذا يصل SqueezeNet مع Deep Compression إلى 510x: لأن أثر المعمارية وأثر الضغط يتضاعفان (يُضرب أحدهما في الآخر).

Huffman coding: short codes for the weights the network uses mostترميز Huffman: رموز قصيرة للأوزان التي تستخدمها الشبكة أكثر من غيرها

Take the last fully connected layer of AlexNet after K-means quantization with 32 clusters. Every surviving weight is now stored as a 5-bit Cluster index, because 2^5 = 32. The histogram on slide 37 counts how often each of the 32 indexes appears, and it is far from flat: two peaks near index 10 and index 19 each collect around 90,000 to 100,000 weights, while the indexes at both ends are used almost never. Yet a fixed-length code spends the same 5 bits on the index used 100,000 times as on the one used twice.

خذ آخر طبقة fully connected في AlexNet بعد K-means quantization بـ 32 عنقوداً. كل وزن باقٍ يُخزَّن الآن على شكل cluster index بطول 5 بتات، لأن 2^5 = 32. يعدّ الـ histogram في الشريحة 37 كم مرة يظهر كل فهرس من الفهارس الـ 32، والتوزيع بعيد جداً عن أن يكون مسطحاً: هناك قمّتان قرب الفهرس 10 والفهرس 19 تجمع كل منهما نحو 90,000 إلى 100,000 وزن، بينما الفهارس في الطرفين لا تكاد تُستخدم. ومع ذلك فإن الرمز ثابت الطول يصرف 5 بتات نفسها على الفهرس المستخدم 100,000 مرة وعلى الفهرس المستخدم مرتين فقط.

The bimodal index histogram (top) and the approximate code length, about log2(1/p) bits, that Huffman assigns each index (bottom). Peaks get codes shorter than the fixed 5 bits; the tails get longer ones.الـ histogram ثنائي القمة للفهارس (في الأعلى)، وطول الرمز التقريبي، نحو log2(1/p) بت، الذي يعطيه Huffman لكل فهرس (في الأسفل). القمم تحصل على رموز أقصر من الـ 5 بتات الثابتة، والأطراف تحصل على رموز أطول.

Huffman coding fixes that mismatch. It is the slide's two bullets made precise: infrequent weights get more bits, frequent weights get fewer bits, and the code lengths are chosen to minimise the average number of bits per symbol.

Huffman coding يعالج هذا التفاوت. هو صياغة دقيقة لنقطتَي الشريحة: الأوزان القليلة الظهور تأخذ بتات أكثر، والأوزان الكثيرة الظهور تأخذ بتات أقل، وتُختار أطوال الرموز بحيث يكون متوسط عدد البتات لكل رمز أصغر ما يمكن.

Worked exampleمثال محلول

Huffman code for four cluster indexesرمز Huffman لأربعة فهارس عناقيد

  1. Start with the probabilitiesابدأ بالاحتمالات

    Four indexes A, B, C, D occur with probabilities 0.5, 0.25, 0.125 and 0.125. A fixed code needs log2(4) = 2 bits for each.
    أربعة فهارس A, B, C, D تظهر باحتمالات 0.5 و0.25 و0.125 و0.125. الرمز الثابت يحتاج إلى log2(4) = 2 bits لكل منها.

  2. Merge the two least likelyادمج الرمزين الأقل احتمالاً

    Join C (0.125) and D (0.125) into a node of weight 0.25. The forest is now A 0.5, B 0.25, CD 0.25.
    اجمع C (0.125) وD (0.125) في عقدة وزنها 0.25. تصبح الغابة الآن A 0.5 وB 0.25 وCD 0.25.

  3. Repeat until one tree remainsكرّر حتى تبقى شجرة واحدة

    Merge B and CD into 0.5, then merge that with A into the root, 1.0. Three merges for four symbols.
    ادمج B وCD في 0.5، ثم ادمج الناتج مع A لتحصل على الجذر 1.0. ثلاث عمليات دمج لأربعة رموز.

  4. Read the codes off the treeاقرأ الرموز من الشجرة

    Label one branch 0 and the other 1 at each node, then read the path from the root: A = 0, B = 10, C = 110, D = 111.
    عند كل عقدة سمِّ أحد الفرعين 0 والآخر 1، ثم اقرأ المسار من الجذر: A = 0 وB = 10 وC = 110 وD = 111.

  5. Average lengthمتوسط الطول

    Lˉ=0.5(1)+0.25(2)+0.125(3)+0.125(3)=1.75 bits\bar{L} = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits}
    Lˉ=0.5(1)+0.25(2)+0.125(3)+0.125(3)=1.75 bits\bar{L} = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits}

  6. Resultالنتيجة

    1.75 bits per symbol instead of 2, a 12.5% saving, with no information lost.
    1.75 bits لكل رمز بدلاً من 2، أي توفير بنسبة 12.5%، دون فقد أي معلومة.

The general rule behind the example: the expected code length is the probability-weighted sum of the code lengths, and no prefix code can beat the entropy of the source. Huffman's greedy merge of the two least likely nodes is provably optimal among prefix codes and always lands within one bit of entropy.

القاعدة العامة وراء المثال: طول الرمز المتوقع هو مجموع أطوال الرموز موزوناً باحتمالاتها، ولا يمكن لأي prefix code أن يتفوق على الـ entropy الخاصة بالمصدر. والدمج الجشع (greedy) الذي يقوم به Huffman لأقل عقدتين احتمالاً مُثبَت أنه الأمثل بين كل الـ prefix codes، ويقع دائماً ضمن بت واحد من الـ entropy.

Lˉ=∑ipiℓi,H=−∑ipilog⁡2pi  ≤  LˉHuffman  <  H+1\bar{L} = \sum_i p_i \ell_i, \qquad H = -\sum_i p_i \log_2 p_i \;\le\; \bar{L}_{\text{Huffman}} \;<\; H + 1
Average code length and the entropy bound for an optimal prefix codeمتوسط طول الرمز وحد الإنتروبيا لرمز بادئة (prefix code) أمثل

In the worked example the probabilities are powers of two, so the entropy is exactly 1.75 bits and Huffman meets the bound with equality. The code is also prefix-free: no codeword is the start of another, so the decoder needs no separators. The bit string 0110100 can only be read as 0 | 110 | 10 | 0, that is A C B A.

في المثال المحلول الاحتمالات قوى للعدد اثنين، لذلك تساوي الـ entropy بالضبط 1.75 bits، ويبلغ Huffman الحد بالتساوي التام. والرمز أيضاً خالٍ من البادئات (prefix-free): لا توجد كلمة رمز هي بداية لكلمة أخرى، لذلك لا يحتاج فك الترميز إلى فواصل. سلسلة البتات 0110100 لا يمكن قراءتها إلا على أنها 0 | 110 | 10 | 0، أي A C B A.

InteractiveتفاعليBuild a Huffman tree one merge at a timeابنِ شجرة Huffman دمجًا بعد دمج
merge 0 of 3الدمج 0 من 3
8A4B2C2D
Huffman average1.75bits / symbolsum of probability times code lengthمجموع حاصل ضرب الاحتمال في طول الرمز
Fixed length2bits / symbolsaves 12.5 percent with Huffmanيوفّر Huffman نسبة 12.5 بالمئة
Entropy1.75bits / symbolno prefix code can average below thisلا يمكن لأي رمز بادئة أن يكون متوسطه أقل من هذا

Two streams get encoded, not oneيُرمَّز تياران لا تيار واحد

The dashed box on slide 37 has two entries, and both matter. Encode Weights Huffman-codes the cluster indexes. Encode Index Huffman-codes the sparse index: after pruning, each surviving weight also stores its position as a small relative offset from the previous nonzero, and small offsets are far more common than large ones, so that stream is skewed too. Han et al. report that Huffman coding these two non-uniform streams saves 20% to 30% of network storage. On AlexNet the average weight code falls from 5.4 to 4 bits and the index code from 4 to 3.2 bits.

المربع المنقّط في الشريحة 37 فيه بندان، وكلاهما مهم. Encode Weights يرمّز فهارس العناقيد بطريقة Huffman. وEncode Index يرمّز الفهرس المتناثر (sparse index) بطريقة Huffman: بعد الـ pruning يخزّن كل وزن باقٍ موقعه أيضاً على شكل إزاحة نسبية صغيرة عن آخر قيمة غير صفرية، والإزاحات الصغيرة أكثر شيوعاً بكثير من الكبيرة، فيكون هذا التيار منحازاً أيضاً. يذكر Han وزملاؤه أن ترميز هذين التيارين غير المنتظمين بطريقة Huffman يوفّر من 20% إلى 30% من مساحة تخزين الشبكة. وفي AlexNet ينخفض متوسط رمز الوزن من 5.4 إلى 4 بتات، ورمز الفهرس من 4 إلى 3.2 بت.

Recall

Four cluster indexes are each used exactly 25 percent of the time. How much does Huffman coding save over a 2-bit fixed code?أربعة فهارس عناقيد يُستخدم كل منها 25 بالمئة من الوقت بالضبط. كم يوفّر ترميز Huffman مقارنةً برمز ثابت بطول 2 بت؟

Nothing. Every merge pairs equal weights, every code has length 2, and the average stays 2 bits, which already equals the entropy log2(4). Huffman only helps when the distribution is skewed.
لا شيء. كل عملية دمج تجمع وزنين متساويين، فيكون طول كل رمز 2، ويبقى المتوسط 2 bits، وهو يساوي أصلاً الـ entropy أي log2(4). Huffman لا يفيد إلا عندما يكون التوزيع منحازاً.

Quick checkاختبار سريع

Four cluster indexes have probabilities 0.5, 0.25, 0.125 and 0.125. What is the average Huffman code length?أربعة فهارس عناقيد احتمالاتها 0.5 و0.25 و0.125 و0.125. ما متوسط طول رمز Huffman؟

The Deep Compression pipeline: fewer weights, fewer bits, shorter codesخط معالجة Deep Compression: أوزان أقل، وبتات أقل، ورموز أقصر

Follow AlexNet through the whole pipeline. It starts with 61M weights, each a 32-bit float, for 240 MB. Three different things can shrink that number, and Deep Compression attacks each one with its own stage.

تتبّع AlexNet عبر خط المعالجة كله. تبدأ الشبكة بـ 61M وزن، كل منها عدد عشري بطول 32 بت، أي 240 MB. هناك ثلاثة أشياء مختلفة يمكنها تقليص هذا الرقم، وDeep Compression يهاجم كل واحد منها بمرحلة خاصة به.

AlexNet through the three stages (Han et al., ICLR 2016, Table 4)AlexNet عبر المراحل الثلاث (Han et al., ICLR 2016, Table 4)

Originalالأصل
61M weights at 32 bits, 240 MB61M وزن بطول 32 بت، أي 240 MB
After pruningبعد الـ pruning
11% of the weights survive, a 9x cut in the weight countيبقى 11% من الأوزان، أي تخفيض عدد الأوزان بمقدار 9x
After quantizationبعد الـ quantization
conv layers use 256 shared values (8 bits), FC layers 32 (5 bits), average 5.4 bits per weight plus a 4-bit relative index; 27x including index and codebook overheadطبقات conv تستخدم 256 قيمة مشتركة (8 بتات)، وطبقات FC تستخدم 32 (5 بتات)، بمتوسط 5.4 بت لكل وزن إضافةً إلى فهرس نسبي بطول 4 بتات؛ والنتيجة 27x شاملةً كلفة الفهارس والـ codebook
After Huffman codingبعد ترميز Huffman
average weight code falls to 4 bits and index code to 3.2 bits, about 22% more saving; 6.9 MB, 35xينخفض متوسط رمز الوزن إلى 4 بتات ورمز الفهرس إلى 3.2 بت، أي توفير إضافي بنحو 22%؛ والحجم 6.9 MB، بنسبة 35x

The stored size is roughly the number of surviving weights times the bits each one costs, so the stages line up with the factors of a product:

الحجم المخزَّن يساوي تقريباً عدد الأوزان الباقية مضروباً في عدد البتات التي يكلّفها كل منها، لذلك تتطابق المراحل مع عوامل حاصل ضرب:

size≈#weights⏟pruning×(bits per weight⏟quantization+index bits)  →Huffman  average code length\text{size} \approx \underbrace{\#\text{weights}}_{\text{pruning}} \times \big(\underbrace{\text{bits per weight}}_{\text{quantization}} + \text{index bits}\big) \;\xrightarrow{\text{Huffman}}\; \text{average code length}
Each stage of Deep Compression shrinks a different factor of the storage costكل مرحلة في Deep Compression تقلص عاملًا مختلفًا من كلفة التخزين
  1. Pruning, fewer weights. Pruning trains to learn which connections matter, removes the small ones, retrains the rest, and iterates. Result: 9x to 13x.الـ pruning، أوزان أقل. يدرّب pruning الشبكة ليعرف أي الاتصالات مهمة، ثم يزيل الصغيرة منها، ويعيد تدريب الباقي، ويكرر ذلك. النتيجة: 9x إلى 13x.
  2. Quantization, fewer bits per weight. Cluster the surviving weights, build the Codebook, replace each weight by its cluster index, then retrain the codebook with Centroid fine-tuning, and iterate. Cumulative: 27x to 31x.الـ quantization، بتات أقل لكل وزن. جمّع الأوزان الباقية في عناقيد، وابنِ الـ codebook، واستبدل كل وزن بفهرس عنقوده، ثم أعد تدريب الـ codebook باستخدام centroid fine-tuning، وكرّر. النسبة التراكمية: 27x إلى 31x.
  3. Huffman encoding. Encode the weight indexes and the sparse index with variable-length codes. Cumulative: 35x to 49x. No training at all.ترميز Huffman. رمّز فهارس الأوزان والفهرس المتناثر برموز متغيرة الطول. النسبة التراكمية: 35x إلى 49x. دون أي تدريب على الإطلاق.
StageالمرحلةReducesما الذي تقلّلهSub-stepsالخطوات الفرعيةCumulative ratioالنسبة التراكميةRetraining?إعادة تدريب؟
PruningPruningNumber of weightsعدد الأوزانTrain connectivity, prune connections, train weights, iterateدرّب الاتصالات، ثم قلّم الاتصالات، ثم درّب الأوزان، وكرّر9x to 13x9x to 13xYes, prune and retrain loopنعم، حلقة pruning ثم إعادة تدريب
QuantizationQuantizationBits per weightعدد البتات لكل وزنCluster weights, generate codebook, quantize with codebook, retrain codebook, iterateجمّع الأوزان في عناقيد، وولّد الـ codebook، وكمّم باستخدامه، وأعد تدريب الـ codebook، وكرّر27x to 31x27x to 31xYes, centroid fine-tuningنعم، centroid fine-tuning
Huffman codingترميز HuffmanAverage code lengthمتوسط طول الرمزEncode weights, encode indexرمّز الأوزان، ورمّز الفهرس35x to 49x35x to 49xNo, purely an encodingلا، هو ترميز فقط
The three stages of slide 38المراحل الثلاث في الشريحة 38
InteractiveتفاعليStep through the Deep Compression pipelineتتبّع خط معالجة Deep Compression خطوة بخطوة
bar length is the stored size relative to the original 240 MBطول الشريط هو الحجم المخزّن نسبة إلى الأصل 240 MB
Original shrinks nothing yet. Slide range for this stage: 1x, same accuracy.الأصل لا يقلّص شيئا بعد. مدى الشريحة لهذه المرحلة: 1x، بالدقة نفسها.
  • dense FP32 network, every weight stored in 32 bitsشبكة FP32 كثيفة، كل وزن فيها مخزّن في 32 bit
Cumulative1xsmaller
Size240MBAlexNet, original 240 MBAlexNet، الأصل 240 MB
Weights kept100%of original
Bits per weight32avgindex bits: noneبتات الفهرس: none

The order is not arbitrary. Pruning goes first so that K-means clusters only the weights that will actually be stored, and the codebook is fitted to the weights that survive. Quantization must come before Huffman because Huffman needs a small alphabet with repeated symbols: on raw FP32 values almost every weight is unique, there is no skew to exploit, and the code would be useless. After quantization there are only 32 or 256 symbols, used very unevenly, which is exactly what Huffman feeds on.

الترتيب ليس اعتباطياً. يأتي الـ pruning أولاً حتى لا يجمّع K-means إلا الأوزان التي ستُخزَّن فعلاً، فيُضبط الـ codebook على الأوزان الباقية. ويجب أن يسبق الـ quantization ترميزَ Huffman لأن Huffman يحتاج إلى أبجدية صغيرة فيها رموز متكررة: مع قيم FP32 الخام يكون كل وزن تقريباً فريداً، فلا يوجد انحياز يمكن استغلاله، ويصبح الرمز عديم الفائدة. بعد الـ quantization لا يبقى إلا 32 أو 256 رمزاً، تُستخدم بشكل متفاوت جداً، وهذا بالضبط ما يتغذى عليه Huffman.

Recall

Which Deep Compression stage needs no retraining, and why?أي مرحلة من مراحل Deep Compression لا تحتاج إلى إعادة تدريب، ولماذا؟

Huffman coding. It is a lossless re-encoding of indexes that already exist, so every weight decodes to exactly the same value and the network's output cannot change.
ترميز Huffman. فهو إعادة ترميز بلا فقد لفهارس موجودة أصلاً، لذلك يُفك كل وزن إلى القيمة نفسها تماماً، ولا يمكن أن يتغير خرج الشبكة.

Quick checkاختبار سريع

Slide 38 labels one stage 'less bits per weight'. Which stage is it, and how does it work?تصف الشريحة 38 إحدى المراحل بأنها 'less bits per weight' (بتات أقل لكل وزن). أي مرحلة هي، وكيف تعمل؟

Results on six networks, and why compact networks compress lessالنتائج على ست شبكات، ولماذا تنضغط الشبكات المدمجة أقل

Check two rows of slide 39 yourself: AlexNet goes from 240 MB to 6.9 MB, and 240 / 6.9 = 34.8, which rounds to 35x. GoogleNet goes from 28 MB to 2.8 MB, exactly 10x. Same method, a 3.5x difference in outcome. The table is about why.

تحقّق بنفسك من صفّين في الشريحة 39: ينتقل AlexNet من 240 MB إلى 6.9 MB، و240 / 6.9 = 34.8، وتُقرَّب إلى 35x. وينتقل GoogleNet من 28 MB إلى 2.8 MB، أي 10x بالضبط. الطريقة نفسها، وفرق في النتيجة بمقدار 3.5x. والجدول يدور حول سبب ذلك.

InteractiveتفاعليDeep Compression results, click a header to sortنتائج Deep Compression، انقر عنوان عمود للترتيب
VGGNetImageNet, top-5550 MB11.3 MB49x88.68%+0.41 pts
LeNet-300MNIST, top-11070 KB27 KB40x98.36%+0.06 pts
LeNet-5MNIST, top-11720 KB44 KB39x99.20%+0.06 pts
AlexNetImageNet, top-5240 MB6.9 MB35x80.27%+0.03 pts
ResNet-18ImageNet, top-544.6 MB4.0 MB11x89.24%+0.04 pts
GoogleNetImageNet, top-528 MB2.8 MB10x88.90%+0.02 pts

Shaded rows are the compact modern networks. Sort by ratio and they fall to the bottom: less redundancy to remove.الصفوف المظلّلة هي الشبكات الحديثة المدمجة. رتّب حسب النسبة فتنزل إلى الأسفل: فيها تكرار أقل يمكن إزالته.

First, accuracy. Every row keeps or slightly improves its accuracy, by 0.02 to 0.41 percentage points. The gains are small enough to read as "no loss"; they come from the retraining in the pruning and quantization loops acting as a mild regulariser. The Compression ratio column is where the networks differ.

أولاً، الدقة. كل صف يحافظ على دقته أو يحسّنها قليلاً، بمقدار 0.02 إلى 0.41 نقطة مئوية. هذه المكاسب صغيرة بما يكفي لتُقرأ على أنها "لا خسارة"، ومصدرها إعادة التدريب في حلقتي الـ pruning والـ quantization التي تعمل كـ regularizer خفيف. أما عمود compression ratio فهو المكان الذي تختلف فيه الشبكات.

The networks that compress best, LeNet-300, AlexNet and VGGNet, spend most of their weights in huge fully connected layers. In AlexNet the three FC layers hold about 59M of the 61M weights, and Deep Compression prunes the two largest (fc6, fc7) to 9% of their weights and codes every FC layer with 5 bits. GoogleNet and ResNet-18 were designed to be compact: they replace the big FC layers with global average pooling and put almost all their weights in convolutions, which tolerate less pruning (AlexNet's conv layers keep 35% to 84% of their weights) and need more bits (8 for AlexNet's convs against 5 for its FC layers). There is simply less redundancy to remove, so they stop at 10x to 11x.

الشبكات الأفضل ضغطاً، LeNet-300 وAlexNet وVGGNet، تصرف معظم أوزانها في طبقات fully connected ضخمة. في AlexNet تحمل طبقات FC الثلاث نحو 59M من أصل 61M وزن، ويقلّم Deep Compression أكبر طبقتين منها (fc6 وfc7) إلى 9% من أوزانهما، ويرمّز كل طبقة FC بـ 5 بتات. أما GoogleNet وResNet-18 فقد صُمّمتا لتكونا مدمجتين: تستبدلان طبقات FC الكبيرة بـ global average pooling وتضعان معظم أوزانهما في طبقات convolution، وهذه تتحمل pruning أقل (طبقات الـ conv في AlexNet تحتفظ بـ 35% إلى 84% من أوزانها) وتحتاج إلى بتات أكثر (8 لطبقات conv في AlexNet مقابل 5 لطبقات FC). ببساطة فيهما تكرار (redundancy) أقل يمكن إزالته، فتتوقفان عند 10x إلى 11x.

Recall

Which two networks on slide 39 compress least, and what do they have in common?ما الشبكتان الأقل ضغطاً في الشريحة 39، وما المشترك بينهما؟

GoogleNet (10x) and ResNet-18 (11x). Both are modern compact designs without large fully connected layers, so they have far less redundant weight to prune and quantize than AlexNet or VGGNet.
GoogleNet (10x) وResNet-18 (11x). كلتاهما تصميم حديث مدمج بلا طبقات fully connected كبيرة، لذلك فيهما أوزان زائدة أقل بكثير يمكن تقليمها وتكميمها مقارنةً بـ AlexNet أو VGGNet.

Quick checkاختبار سريع

Why does Deep Compression shrink ResNet-18 only 11x but VGGNet 49x?لماذا يقلّص Deep Compression حجم ResNet-18 بنسبة 11x فقط بينما يقلّص VGGNet بنسبة 49x؟

SqueezeNet's fire module: squeeze the channels before the 3x3 filtersالـ fire module في SqueezeNet: اضغط القنوات قبل مرشحات 3x3

Suppose a layer must turn 64 input channels into 128 output channels. A plain 3x3 convolution needs 64 x 128 x 9 = 73,728 weights. SqueezeNet gets the same 128 output channels from a Fire module with about a sixth of that.

افترض أن طبقة يجب أن تحوّل 64 قناة دخل إلى 128 قناة خرج. طبقة convolution عادية بحجم 3x3 تحتاج إلى 64 x 128 x 9 = 73,728 وزناً. أما SqueezeNet فيحصل على قنوات الخرج نفسها، 128، من fire module بنحو سدس هذا العدد.

Fire module from slide 40: 64 channels squeezed to 16 by a 1x1 conv, expanded by parallel 1x1 and 3x3 convs to 64 each, concatenated to 128.الـ fire module من الشريحة 40: تُضغط 64 قناة إلى 16 بطبقة conv بحجم 1x1، ثم تُوسَّع بطبقتي conv متوازيتين 1x1 و3x3 إلى 64 لكل منهما، وتُدمجان (concatenate) إلى 128.

The module has two layers. The squeeze layer is a 1x1 convolution that compresses the 64 input channels to 16. The expand layer runs a 1x1 convolution and a 3x3 convolution side by side on those 16 channels, 64 filters each, and concatenates the results into 128 channels. A convolution layer has C_in x C_out x k x k weights, so the expensive 3x3 filters now see 16 input channels instead of 64, and half of the outputs come from cheap 1x1 filters.

للوحدة طبقتان. طبقة squeeze هي convolution بحجم 1x1 تضغط قنوات الدخل الـ 64 إلى 16. وطبقة expand تشغّل convolution بحجم 1x1 وأخرى بحجم 3x3 جنباً إلى جنب على هذه القنوات الـ 16، بـ 64 مرشحاً لكل منهما، وتدمج النتائج (concatenate) في 128 قناة. طبقة الـ convolution فيها C_in x C_out x k x k وزناً، لذلك أصبحت المرشحات المكلفة 3x3 ترى 16 قناة دخل بدلاً من 64، ونصف المخرجات يأتي من مرشحات 1x1 رخيصة.

LayerالطبقةC_in x C_out x k x kC_in x C_out x k x kWeightsالأوزان
3x3 conv, 64 to 128طبقة 3x3 conv من 64 إلى 12864 x 128 x 964 x 128 x 973,72873,728
1x1 squeeze, 64 to 16طبقة 1x1 squeeze من 64 إلى 1664 x 16 x 164 x 16 x 11,0241,024
1x1 expand, 16 to 64طبقة 1x1 expand من 16 إلى 6416 x 64 x 116 x 64 x 11,0241,024
3x3 expand, 16 to 64طبقة 3x3 expand من 16 إلى 6416 x 64 x 916 x 64 x 99,2169,216
Fire module totalمجموع الـ fire module1,024 + 1,024 + 9,2161,024 + 1,024 + 9,21611,26411,264
Weights in a direct 3x3 convolution versus the slide's fire module (biases ignored)الأوزان في طبقة convolution مباشرة بحجم 3x3 مقابل الـ fire module في الشريحة (مع إهمال قيم الـ bias)

73,728 / 11,264 = 6.5, so the fire module uses about 6.5x fewer weights for the same output width. The SqueezeNet paper names the three ideas behind the design: replace 3x3 filters with 1x1 filters (each has 9x fewer weights), decrease the number of input channels to the 3x3 filters (that is the squeeze), and downsample late so the layers work on large activation maps, which protects accuracy. The squeeze width is always kept below the total expand width, s1x1 < e1x1 + e3x3.

73,728 / 11,264 = 6.5، إذن تستخدم الـ fire module أوزاناً أقل بنحو 6.5x لعرض الخرج نفسه. تسمّي ورقة SqueezeNet الأفكار الثلاث وراء التصميم: استبدال مرشحات 3x3 بمرشحات 1x1 (كل واحد منها أقل بـ 9x في الأوزان)، وتقليل عدد قنوات الدخل إلى مرشحات 3x3 (وهذا هو الـ squeeze)، وتأخير الـ downsampling حتى تعمل الطبقات على خرائط تنشيط (activation maps) كبيرة، مما يحمي الدقة. ويبقى عرض الـ squeeze دائماً أقل من مجموع عرض الـ expand، أي s1x1 < e1x1 + e3x3.

Recall

Recount the fire module with a squeeze width of 32 instead of 16, keeping 64 + 64 expand filters. How many weights?أعد عدّ أوزان الـ fire module بعرض squeeze يساوي 32 بدلاً من 16، مع الإبقاء على 64 + 64 مرشح expand. كم عدد الأوزان؟

64 x 32 + 32 x 64 + 32 x 64 x 9 = 2,048 + 2,048 + 18,432 = 22,528. Doubling the squeeze width doubles every term, which is why the squeeze is kept narrow.
64 x 32 + 32 x 64 + 32 x 64 x 9 = 2,048 + 2,048 + 18,432 = 22,528. مضاعفة عرض الـ squeeze تضاعف كل حد، ولهذا يُبقى الـ squeeze ضيقاً.

Quick checkاختبار سريع

A direct 3x3 conv maps 64 channels to 128. The slide's fire module also outputs 128. Roughly how many times fewer weights does it need?طبقة 3x3 conv مباشرة تحوّل 64 قناة إلى 128. والـ fire module في الشريحة تُخرج 128 قناة أيضاً. بكم مرة تقريباً تقل الأوزان التي تحتاجها؟

Deep Compression on SqueezeNet: two orthogonal savings that multiply to 510xDeep Compression على SqueezeNet: توفيران متعامدان يتضاعفان إلى 510x

Slide 41 lines up five ways to get an ImageNet classifier at AlexNet accuracy. Read the size column from top to bottom: 240 MB, 48 MB, 6.9 MB, 4.8 MB and finally 0.47 MB, less than half a megabyte.

تصفّ الشريحة 41 خمس طرق للحصول على مصنّف ImageNet بدقة AlexNet. اقرأ عمود الحجم من الأعلى إلى الأسفل: 240 MB و48 MB و6.9 MB و4.8 MB وأخيراً 0.47 MB، أي أقل من نصف ميغابايت.

NetworkالشبكةApproachالطريقةSizeالحجمRatio vs AlexNetالنسبة مقارنةً بـ AlexNetTop-1Top-1Top-5Top-5
AlexNetAlexNetnoneبلا ضغط240 MB240 MB1x1x57.2%57.2%80.3%80.3%
AlexNetAlexNetSVDSVD48 MB48 MB5x5x56.0%56.0%79.4%79.4%
AlexNetAlexNetDeep CompressionDeep Compression6.9 MB6.9 MB35x35x57.2%57.2%80.3%80.3%
SqueezeNetSqueezeNetnoneبلا ضغط4.8 MB4.8 MB50x50x57.5%57.5%80.3%80.3%
SqueezeNetSqueezeNetDeep CompressionDeep Compression0.47 MB0.47 MB510x510x57.5%57.5%80.3%80.3%
Slide 41: compression and compact design on ImageNet (Iandola et al., 2016)الشريحة 41: الضغط والتصميم المدمج على ImageNet (Iandola et al., 2016)
Model size on a log scale. Deep Compression and SqueezeNet each cut about one and a half decades; together they cut more than two and a half.حجم النموذج على مقياس لوغاريتمي. كل من Deep Compression وSqueezeNet يقتطع نحو مرتبة عشرية ونصف، ومعاً يقتطعان أكثر من مرتبتين ونصف.

Three lessons sit in this table. First, not all compression is equal: a low-rank SVD factorisation buys only 5x and already costs 1.2 points of top-1 accuracy (57.2% to 56.0%), while Deep Compression buys 35x at no cost. Second, a better architecture can beat compression on its own: SqueezeNet is 50x smaller than AlexNet by design and even slightly more accurate in top-1. Third, and most important, the two are orthogonal.

في هذا الجدول ثلاثة دروس. أولاً، ليس كل ضغط متساوياً: تحليل SVD منخفض الرتبة (low-rank) لا يكسب إلا 5x ويكلّف أصلاً 1.2 نقطة من دقة top-1 (من 57.2% إلى 56.0%)، بينما يكسب Deep Compression نسبة 35x دون أي كلفة. ثانياً، المعمارية الأفضل قد تتفوق على الضغط وحده: SqueezeNet أصغر من AlexNet بـ 50x بحكم تصميمه، بل وأدق قليلاً في top-1. ثالثاً، وهو الأهم، أن الاثنين متعامدان (orthogonal)، أي مستقلان عن بعضهما.

240 MB4.8 MB=50×,4.8 MB0.47 MB≈10.2×,50×10.2≈510×\frac{240 \text{ MB}}{4.8 \text{ MB}} = 50\times, \qquad \frac{4.8 \text{ MB}}{0.47 \text{ MB}} \approx 10.2\times, \qquad 50 \times 10.2 \approx 510\times
Architecture and compression multiplyالمعمارية والضغط يتضاعفان معًا

SqueezeNet decides how many parameters the network needs; Deep Compression decides how many bits each surviving parameter costs. Because they act on different factors, their ratios multiply. The paper used 6-bit quantization and light pruning on SqueezeNet. Notice that compression gave only about 10x here, against 35x on AlexNet: exactly the lesson of the previous concept, since a compact network carries less redundancy.

SqueezeNet يحدد كم معاملاً تحتاج الشبكة، وDeep Compression يحدد كم بتاً يكلّف كل معامل باقٍ. ولأنهما يعملان على عوامل مختلفة، فإن نسبتيهما تُضربان. استخدمت الورقة quantization بـ 6 بتات وpruning خفيفاً على SqueezeNet. لاحظ أن الضغط أعطى هنا نحو 10x فقط، مقابل 35x على AlexNet: وهذا بالضبط درس المفهوم السابق، لأن الشبكة المدمجة تحمل تكراراً أقل.

Recall

Why is 510x not 50 x 35 = 1750x?لماذا النسبة 510x وليست 50 x 35 = 1750x؟

The 35x was measured on AlexNet, which is full of redundant FC weights. Applied to the already compact SqueezeNet, Deep Compression achieves only about 10x, and 50 x 10.2 = 510.
نسبة 35x قيست على AlexNet، وهو مليء بأوزان FC زائدة. وعند تطبيق Deep Compression على SqueezeNet المدمج أصلاً لا يحقق إلا نحو 10x، و50 x 10.2 = 510.

Quick checkاختبار سريع

SqueezeNet is 50x smaller than AlexNet, and Deep Compression shrinks SqueezeNet another 10x. What does that show?SqueezeNet أصغر من AlexNet بـ 50x، ويقلّص Deep Compression حجم SqueezeNet بـ 10x إضافية. ماذا يبيّن ذلك؟

Recapالخلاصة

If you remember nothing elseإن لم تتذكر شيئاً آخر فتذكّر هذا

  • Huffman coding gives frequent symbols short codes and rare symbols long codes. It is a prefix code, so it decodes without separators, and it is lossless.ترميز Huffman يعطي الرموز المتكررة رموزاً قصيرة والرموز النادرة رموزاً طويلة. وهو prefix code، لذلك يُفك دون فواصل، وهو بلا فقد (lossless).
  • Worked case: probabilities 0.5, 0.25, 0.125, 0.125 give codes 0, 10, 110, 111 and an average of 1.75 bits against 2 bits fixed.المثال المحلول: الاحتمالات 0.5 و0.25 و0.125 و0.125 تعطي الرموز 0 و10 و110 و111، بمتوسط 1.75 بت مقابل 2 بت للرمز الثابت.
  • Deep Compression Huffman-codes two streams: the cluster indexes of the quantized weights and the relative sparse indexes left by pruning. It saves 20 to 30 percent of storage with no retraining.يرمّز Deep Compression بطريقة Huffman تيارين: فهارس العناقيد (cluster indexes) للأوزان المكمّاة، والفهارس النسبية المتناثرة التي يتركها الـ pruning. ويوفّر 20 إلى 30 بالمئة من مساحة التخزين دون أي إعادة تدريب.
  • Pipeline order: pruning (fewer weights, 9x to 13x), then K-means quantization (fewer bits per weight, 27x to 31x cumulative), then Huffman coding (shorter average code, 35x to 49x cumulative), each at the same accuracy.ترتيب خط المعالجة: الـ pruning (أوزان أقل، 9x إلى 13x)، ثم K-means quantization (بتات أقل لكل وزن، 27x إلى 31x تراكمياً)، ثم ترميز Huffman (متوسط رمز أقصر، 35x إلى 49x تراكمياً)، وكل ذلك بالدقة نفسها.
  • AlexNet 240 MB to 6.9 MB (35x), VGGNet 550 MB to 11.3 MB (49x), GoogleNet 10x, ResNet-18 11x. FC-heavy networks hold the most redundancy.AlexNet من 240 MB إلى 6.9 MB (35x)، وVGGNet من 550 MB إلى 11.3 MB (49x)، وGoogleNet بنسبة 10x، وResNet-18 بنسبة 11x. الشبكات التي تغلب عليها طبقات FC تحمل أكبر قدر من التكرار (redundancy).
  • Fire module: 1x1 squeeze to 16 channels, then parallel 1x1 and 3x3 expands of 64 each, concatenated to 128. 11,264 weights against 73,728 for a direct 3x3 conv, about 6.5x fewer.الـ fire module: طبقة squeeze بحجم 1x1 إلى 16 قناة، ثم طبقتا expand متوازيتان 1x1 و3x3 بـ 64 مرشحاً لكل منهما، تُدمجان (concatenate) إلى 128. أي 11,264 وزناً مقابل 73,728 لطبقة 3x3 مباشرة، أقل بنحو 6.5x.
  • SqueezeNet is 4.8 MB (50x smaller than AlexNet); Deep Compression takes it to 0.47 MB, 510x smaller than AlexNet, with the same 57.5 percent top-1 and 80.3 percent top-5.حجم SqueezeNet هو 4.8 MB (أصغر من AlexNet بـ 50x)، ويوصله Deep Compression إلى 0.47 MB، أي أصغر من AlexNet بـ 510x، بالدقة نفسها: 57.5 بالمئة top-1 و80.3 بالمئة top-5.

Sourcesالمصادر