Lecture 05-3 · Quantization III
المحاضرة 05-3 · التكميم الثالث
Binary weights: sign, stochastic, BWN scale
الأوزان الثنائية: sign والعشوائية ومقياس BWN
P1 MUSTP1 ضروريPush weights all the way down to 1 bit: every weight becomes +1 or −1. Storage shrinks about 32x and every multiply turns into an add or a subtract. The price is accuracy, and one fp32 scale factor α buys most of it back.
ندفع الأوزان إلى 1 bit فقط: كل وزن يصبح +1 أو −1. يتقلص التخزين بحوالي 32x ويتحول كل ضرب إلى جمع أو طرح. الثمن هو الدقة، ومعامل مقياس واحد α بصيغة fp32 يستعيد معظمها.
Where binary sits among the quantization families
موقع الثنائي بين عائلات التكميم
Slide 49 (repeated on slide 64) places binary and ternary quantization at the far end of the table. K-means stores integer indices but still computes in floating point through the codebook. Linear quantization stores integers and computes with integer arithmetic. Binary and ternary store 1 or 2 bit weights and compute with bit operations.
تضع الشريحة 49 (وتتكرر في الشريحة 64) التكميم الثنائي (binary) والثلاثي (ternary) في أقصى الجدول. K-means يخزن فهارس صحيحة لكنه ما زال يحسب بالفاصلة العائمة عبر الـ codebook. وlinear quantization يخزن أعداداً صحيحة ويحسب بحساب الأعداد الصحيحة. أما binary/ternary فيخزن أوزاناً من 1 أو 2 بت ويحسب بـعمليات البتات (bit operations).
| Full precisionالدقة الكاملة | K-means | Linearالخطي | Binary / ternaryثنائي / ثلاثي | |
|---|---|---|---|---|
| Storageالتخزين | FP weightsأوزان FP | Int indices + FP codebookفهارس صحيحة + codebook بدقة FP | Int weightsأوزان صحيحة | Binary / ternary weightsأوزان ثنائية / ثلاثية |
| Computationالحساب | FP arithmeticحساب FP | FP arithmeticحساب FP | Int arithmeticحساب صحيح | Bit operationsعمليات على البتات |
السطر الأول هو التخزين والسطر الثاني هو الحساب. لاحظ أن K-means يوفّر في التخزين فقط، بينما linear يوفّر في الاثنين، وbinary/ternary يذهب أبعد فيستبدل الحساب الصحيح بعمليات بتات.
The running dot product with real and binary weights
الضرب النقطي الجاري بأوزان حقيقية وأوزان ثنائية
Slides 51 and 52 take one row of a fully connected layer, yi = Σj Wij xj, with W row [8, −3, 5, −1] and input x = [5, 2, 0, 1]. With real weights the row needs 4 multiplies and 3 adds. Replace each weight by its sign, [1, −1, 1, −1], and the multiplies disappear: each term is just +xj or −xj.
تأخذ الشريحتان 51 و52 صفاً واحداً من طبقة fully connected، y_i = Σ_j W_ij x_j، حيث صف الأوزان [8, −3, 5, −1] والمدخل x = [5, 2, 0, 1]. مع الأوزان الحقيقية يحتاج الصف 4 عمليات ضرب و3 عمليات جمع. استبدل كل وزن بإشارته [1, −1, 1, −1] فتختفي عمليات الضرب: كل حد يصبح +x_j أو −x_j فقط.
| inputالدخل | weightالوزن | operationsالعمليات | memoryالذاكرة | computationالحساب |
|---|---|---|---|---|
| R (real)R (حقيقي) | R (real)R (حقيقي) | + × | 1x | 1x |
| R (real)R (حقيقي) | B (binary)B (ثنائي) | + − | ~32x lessأقل بنحو 32x | ~2x lessأقل بنحو 2x |
الجدول من الشريحة 52: مدخل حقيقي R مع وزن ثنائي B يستخدم + و− فقط، فالذاكرة أقل بحوالي 32x (من 32 بت إلى 1 بت لكل وزن) والحساب أقل بحوالي 2x (لأن الضرب اختفى وبقي الجمع).
Why "~2x less computation" and not more: a MAC is one multiply plus one add. Removing the multiply leaves the add, so roughly half the operations survive. Memory is ~32x less because each weight drops from 32 bits to 1 bit.
لماذا "~2x أقل حساباً" وليس أكثر: الـ MAC ضرب واحد وجمع واحد. إزالة الضرب تترك الجمع، فيبقى تقريباً نصف العمليات. والذاكرة أقل بحوالي 32x لأن كل وزن ينزل من 32 بت إلى 1 بت.
Two ways to binarize
طريقتان للتحويل الثنائي
Deterministic
الطريقة الحتمية
Threshold at 0, giving a sign function. Note that 0 maps to +1.
عتبة عند 0، فنحصل على دالة الإشارة sign. لاحظ أن 0 تُحوَّل إلى +1.
q = sign(r) = +1 if r ≥ 0, −1 if r < 0
عتبة عند 0 فتنتج دالة إشارة. لاحظ أن الصفر يتحول إلى +1.
Stochastic (BinaryConnect)
الطريقة العشوائية (BinaryConnect)
Pick +1 with probability p = σ(r), else −1, where σ is the hard sigmoid. Harder in hardware: the quantizer needs a random bit generator.
اختر +1 باحتمال p = σ(r)، وإلا −1، حيث σ هي hard sigmoid. أصعب في العتاد: يحتاج المكمِّم إلى مولّد بتات عشوائية.
σ(r) = min(max((r + 1)/2, 0), 1)
اختر +1 باحتمال p = σ(r) وإلا −1، حيث σ هي hard sigmoid. أصعب في العتاد لأن المكمّم يحتاج مولّد بتات عشوائية.
Stochastic binarization only randomizes weights close to zero. A weight of 2.09 has σ = 1, so it is always +1. A weight of −1.08 has σ = 0, so it is always −1. A weight of 0.4 has σ = 0.7, so it is +1 seven times out of ten.
التكميم الثنائي العشوائي يجعل العشوائية فقط للأوزان القريبة من الصفر. الوزن 2.09 له σ = 1 فيكون دائماً +1. والوزن −1.08 له σ = 0 فيكون دائماً −1. والوزن 0.4 له σ = 0.7 فيكون +1 سبع مرات من كل عشر.
BWN: add one scale to minimize the error
BWN: إضافة scale واحد لتقليل الخطأ
Plain sign() throws away all magnitude. The Binary Weight Network (BWN, from the XNOR-Net paper) approximates W ≈ α WB with WB = sign(W) and one fp32 scale α. The α that minimizes ‖W − α WB‖F2 is the mean absolute value of the weights.
sign() وحدها ترمي كل المقدار. شبكة Binary Weight Network (BWN) من ورقة XNOR-Net تقرّب W ≈ α W^B حيث W^B = sign(W) ومقياس واحد α بصيغة fp32. قيمة α التي تصغّر ‖W − α W^B‖_F^2 هي متوسط القيمة المطلقة للأوزان.
WB = sign(W), α = (1/n) ‖W‖1 = (1/n) Σ |Wi|
Why the mean absolute value: expand ‖W − αB‖2 = ‖W‖2 − 2α (W · B) + α2 n, since B has n entries of ±1. Differentiate in α and set to zero: α = (W · B) / n. With B = sign(W), W · B = Σ |Wi| = ‖W‖1.
لماذا متوسط القيمة المطلقة: افتح ‖W − αB‖^2 = ‖W‖^2 − 2α (W · B) + α^2 n لأن B فيه n عنصر كلها ±1. اشتق بالنسبة لـ α واجعل الناتج صفراً: α = (W · B) / n. ومع B = sign(W) يكون W · B = Σ |W_i| = ‖W‖_1.
Compute WB, α and both errors for the slide 54 matrix.
احسب W^B وα والخطأين لمصفوفة الشريحة 54.
Row |sums| row 1: 2.09 + 0.98 + 1.48 + 0.09 = 4.64 row 2: 0.05 + 0.14 + 1.08 + 2.12 = 3.39 row 3: 0.91 + 1.92 + 0 + 1.03 = 3.86 row 4: 1.87 + 0 + 1.53 + 1.49 = 4.89 ‖W‖₁ = 4.64 + 3.39 + 3.86 + 4.89 = 16.78 α = 16.78 / 16 = 1.04875 ≈ 1.05 W^B = sign(W) (0 → +1) 1 −1 1 1 1 −1 −1 1 −1 1 1 −1 1 1 1 1 ‖W − W^B‖²_F = 9.28 (α = 1) ‖W − αW^B‖²_F = 9.24 (α = 1.05, the minimum) Reconstructed weights: ±1.05, e.g. 2.09 → 1.05, −0.14 → −1.05
The error drop looks small here only because this matrix's mean |w| is already close to 1. For a real layer with weights around 0.01, α ≈ 0.01 and plain ±1 would be off by two orders of magnitude, so the scale matters a lot.
انخفاض الخطأ يبدو صغيراً هنا فقط لأن متوسط |w| لهذه المصفوفة قريب أصلاً من 1. في طبقة حقيقية أوزانها حول 0.01 يكون α ≈ 0.01، وتكون ±1 وحدها خاطئة بمرتبتين عشريتين، لذلك المقياس مهم جداً.
| AlexNet-based networkشبكة مبنية على AlexNet | ImageNet top-1 accuracy deltaفرق دقة top-1 على ImageNet |
|---|---|
| BinaryConnect (no scale)BinaryConnect (بلا scale) | −21.2% |
| Binary Weight Network, BWN (scale α)Binary Weight Network، BWN (مع scale α) | 0.2% |
نتيجة الشريحة 54 على AlexNet: BinaryConnect بدون مقياس يخسر −21.2% من دقة top-1، بينما BWN مع المقياس α يبقى عند فرق 0.2% فقط. الفرق كله تقريباً من معامل المقياس.
"Sign for direction, mean |w| for size". WB keeps only the direction of each weight; α = mean |w| puts the average size back.
"الإشارة للاتجاه، ومتوسط |w| للحجم". W^B يحتفظ فقط باتجاه كل وزن، وα = mean |w| يعيد الحجم المتوسط.
sign(0) = +1, not 0. The slide's rule is r ≥ 0 → +1. The two zeros in the matrix become +1 in WB. Writing 0 would make it ternary.
sign(0) = +1 وليس 0. قاعدة الشريحة هي r ≥ 0 → +1. الصفران في المصفوفة يصبحان +1 في W^B. كتابة 0 تجعلها ternary.
α is the mean of absolute values, not the mean of the weights and not the max. The plain mean of this matrix is 8.50 / 16 ≈ 0.53 because positives and negatives cancel. The max |w| is 2.12. Only 16.78 / 16 = 1.05 is right.
α هو متوسط القيم المطلقة، وليس متوسط الأوزان وليس القيمة العظمى. المتوسط العادي لهذه المصفوفة 8.50 / 16 ≈ 0.53 لأن الموجب والسالب يلغي بعضه. وأكبر |w| هو 2.12. الصحيح فقط 16.78 / 16 = 1.05.
~2x, not ~32x, for computation. 32x is memory. Binary weights with real inputs still need the adds.
الحساب ~2x وليس ~32x. الـ 32x للذاكرة. الأوزان الثنائية مع مدخلات حقيقية ما زالت تحتاج عمليات الجمع.
Check yourself
اختبر نفسك
Weights [8, −3, 5, −1] are binarized with sign() and multiplied by x = [5, 2, 0, 1]. What is y?
الأوزان [8, −3, 5, −1] تُحوَّل إلى ثنائية بـ sign() ثم تُضرب في x = [5, 2, 0, 1]. ما قيمة y؟
C. sign gives [1, −1, 1, −1], so y = 5 − 2 + 0 − 1 = 2. A is the full-precision result 40 − 6 + 0 − 1. B adds every input (5 + 2 + 0 + 1). D drops the last term's sign.
C. دالة sign تعطي [1, −1, 1, −1]، لذا y = 5 − 2 + 0 − 1 = 2. الخيار A هو نتيجة الدقة الكاملة 40 − 6 + 0 − 1. والخيار B يجمع كل المدخلات (5 + 2 + 0 + 1). والخيار D يُسقط إشارة الحد الأخير.
For W = [0.6, −1.2, 0, 0.2], what are WB and the BWN scale α?
لـ W = [0.6, −1.2, 0, 0.2]، ما W^B وما مقياس BWN α؟
B. sign(0) = +1, and α = (0.6 + 1.2 + 0 + 0.2) / 4 = 2.0 / 4 = 0.5. A maps 0 to 0, which is ternary. C uses the signed mean (−0.4 / 4). D uses the max |w|.
B. sign(0) = +1، وα = (0.6 + 1.2 + 0 + 0.2) / 4 = 2.0 / 4 = 0.5. الخيار A يحوّل 0 إلى 0، وهذا تكميم ثلاثي. والخيار C يستخدم المتوسط بالإشارة (−0.4 / 4). والخيار D يستخدم أكبر |w|.
In stochastic binarization (BinaryConnect), what is the probability that r = −0.4 becomes +1?
في التكميم الثنائي العشوائي (BinaryConnect)، ما احتمال أن يصبح r = −0.4 مساوياً لـ +1؟
A. σ(−0.4) = (−0.4 + 1) / 2 = 0.3, inside [0, 1] so no clipping. B is the probability of −1. C is what deterministic sign would give as P(+1). D confuses r with p.
A. σ(−0.4) = (−0.4 + 1) / 2 = 0.3، وهي داخل [0, 1] فلا قص. الخيار B هو احتمال −1. والخيار C هو ما تعطيه sign الحتمية كقيمة لـ P(+1). والخيار D يخلط بين r وp.
Real inputs times binary weights (R × B) compared with R × R. Which pair is right?
مدخلات حقيقية في أوزان ثنائية (R × B) مقارنة بـ R × R. أي زوج صحيح؟
D. 32-bit weights become 1-bit (~32x), and the multiply is removed while the add stays (~2x). A swaps them. B is the B × B row (XNOR-Net). C uses an 8-bit to 1-bit ratio.
D. الأوزان بـ 32 بت تصبح بـ 1 بت (نحو 32x)، وتُزال عملية الضرب بينما يبقى الجمع (نحو 2x). الخيار A يعكسهما. والخيار B هو صف B × B (XNOR-Net). والخيار C يستخدم نسبة 8 بت إلى 1 بت.
Why does BWN lose only 0.2% on AlexNet while BinaryConnect loses 21.2%?
لماذا يخسر BWN فقط 0.2% على AlexNet بينما يخسر BinaryConnect 21.2%؟
C. The fp32 scale α restores the average magnitude, minimizing ‖W − αWB‖². A describes BNN or XNOR-Net and would hurt accuracy. B is ternary. D is BinaryConnect's own option.
C. الـ scale α بدقة fp32 يستعيد متوسط المقدار، فيقلّل ‖W − αWB‖². الخيار A يصف BNN أو XNOR-Net وسيضر بالدقة. والخيار B تكميم ثلاثي. والخيار D هو خيار BinaryConnect نفسه.