Lecture 03 · N-grams

المحاضرة 03 · نماذج N-grams

Entropy, Cross-Entropy, and Summary

الإنتروبيا (Entropy) والإنتروبيا المتقاطعة (Cross-Entropy) والملخص

Slides 101–104الشرائح 101–104 P2 SHOULDP2 مهم

Why perplexity is 2 raised to the cross-entropy, proved on a three-word language, followed by a one-page revision sheet for the whole lecture.

لماذا تساوي perplexity العدد 2 مرفوعاً إلى cross-entropy، مع برهان على لغة من ثلاث كلمات، تليها ورقة مراجعة من صفحة واحدة للمحاضرة كلها.

Entropy is an average number of bits

الإنتروبيا متوسط عدد من البتات

Slide 101. For a random variable X with distribution p:

الشريحة 101. لمتغير عشوائي X توزيعه p:

H(X) = − Σ_x p(x) log₂ p(x)

تقول المعادلة: الـ entropy هي سالب مجموع p(x) log₂ p(x) على كل النتائج الممكنة x.

Two readings, both exam-safe:

قراءتان، وكلتاهما آمنة في الامتحان:

Uncertainty. How unpredictable the next outcome is. Low entropy means easy to guess.
عدم اليقين. مقدار صعوبة توقّع النتيجة التالية. الـ entropy المنخفضة تعني أن التخمين سهل.
Bits. The lower bound on the average number of bits needed to encode one outcome under an optimal code. Base 2 is what makes the unit "bits".
البتات. الحد الأدنى لمتوسط عدد البتات اللازمة لترميز نتيجة واحدة بأفضل ترميز ممكن. والأساس 2 هو ما يجعل الوحدة "بتات" (bits).

The minus sign is there because log₂ p is negative for probabilities below 1, so the sum would otherwise come out negative. It is often easier to write the equivalent positive form:

إشارة السالب موجودة لأن log₂ p سالب لأي احتمال أقل من 1، فلولاها لخرج المجموع سالباً. وكثيراً ما يكون أسهل أن تكتب الصيغة الموجبة المكافئة:

H(X) = Σ_x p(x) log₂ 1p(x)

أي أن H(X) هي مجموع p(x) مضروباً في log₂(1/p(x))، دون إشارة سالب لأن 1/p(x) أكبر من 1.

Read that as: each outcome costs log₂(1/p) bits, and you pay the average.

اقرأها هكذا: كل نتيجة تكلّف log₂(1/p) بت، وأنت تدفع المتوسط.

The uniform case does all the work

الحالة المنتظمة (uniform) تقوم بكل العمل

Take k equally likely outcomes, so p(x) = 1/k for each.

خذ k نتيجة متساوية الاحتمال، فيكون p(x) = 1/k لكل منها.

H = − Σ_{i=1..k}  (1/k) · log2(1/k)

  = − k · (1/k) · log2(1/k)

  = − log2(1/k)

  = log2 k

so    2^H = 2^(log2 k) = k

يمشي الاشتقاق هكذا: H = − Σ (1/k) · log2(1/k) على k حداً متساوياً، فيصبح − k · (1/k) · log2(1/k)، أي − log2(1/k)، أي log2 k. إذن 2^H = 2^(log2 k) = k.

Read the last line slowly, because it is the whole relationship between entropy and perplexity. If you have k equally likely options, the entropy is log₂ k bits and 2 to that power is k, the number of options itself.

اقرأ السطر الأخير ببطء، لأنه العلاقة كلها بين entropy وperplexity. إذا كان لديك k خيار متساوي الاحتمال، فالـ entropy تساوي log₂ k بت، و2 مرفوعاً إلى هذه القوة يساوي k، أي عدد الخيارات نفسه.

The hookالمدخل

Perplexity is entropy expressed as a number of choices instead of a number of bits.

الـ perplexity هي الـ entropy معبَّراً عنها بـ عدد خيارات بدلاً من عدد بتات.

Bits are the exponent. Perplexity is the answer. Same quantity, two units. Going from bits to choices is 2^H. Going from choices back to bits is log₂ PP.

البتات هي الأس، والـ perplexity هي الناتج. الكمية نفسها بوحدتين. الانتقال من البتات إلى الخيارات هو 2^H، والرجوع من الخيارات إلى البتات هو log₂ PP.

The three-colour language, computed twice

لغة الألوان الثلاثة، محسوبة مرتين

Slide 40 introduces L = {red, blue, green} and asserts the perplexities. Here is the entropy behind them.

تقدّم الشريحة 40 اللغة L = {red, blue, green} وتذكر قيم perplexity مباشرة. وهذه هي الـ entropy التي تقف وراءها.

Three real options either way. Skewing the distribution cuts the effective number of options from 3.00 to 1.89, which is the weighted branching factor of slide 39.

ثلاثة خيارات حقيقية في الحالتين. لكن جعل التوزيع منحرفاً يخفّض العدد الفعلي للخيارات من 3.00 إلى 1.89، وهو weighted branching factor في الشريحة 39.

الرسم مخططا أعمدة على red وblue وgreen. في الحالة المتساوية ثلاثة أعمدة متساوية، وentropy تساوي 1.585 بت وperplexity تساوي 3. وفي الحالة المنحرفة عمود red طويل وعمودان قصيران، وentropy تساوي 0.922 بت وperplexity تساوي 1.89. هناك ثلاثة خيارات حقيقية في الحالتين، لكن انحراف التوزيع يخفّض العدد الفعلي للخيارات من 3.00 إلى 1.89، وهذا هو weighted branching factor في الشريحة 39.

Worked, every stepمثال محلول، خطوة بخطوة

CASE 1, uniform.  p(red) = p(blue) = p(green) = 1/3

  H = 3 * ( 1/3 * log2(3) )
    = log2 3
    = 1.5849625...
    = 1.585 bits

  PP = 2^H = 2^(log2 3) = 3.00      exactly 3, no rounding needed


CASE 2, skewed.  p(red) = 0.8,  p(blue) = p(green) = 0.1

  log2(1/0.8) = log2(1.25)  = 0.3219281
  log2(1/0.1) = log2(10)    = 3.3219281

  red   term : 0.8 * 0.3219281 = 0.2575425
  blue  term : 0.1 * 3.3219281 = 0.3321928
  green term : 0.1 * 3.3219281 = 0.3321928
                                 ---------
  H                            = 0.9219281
                               = 0.922 bits

  PP = 2^0.9219281 = 1.894646
     = 1.89          (about 1.9 to two significant figures)


CROSS-CHECK using the perplexity definition directly (slide 33).
For a model that matches the truth, PP = product of p(x)^(-p(x)):

  0.8^(-0.8) * 0.1^(-0.1) * 0.1^(-0.1)
    = 1.195446 * 1.258925 * 1.258925
    = 1.894646                             same answer

الحالة الأولى، التوزيع المتساوي p = 1/3 لكل لون: H = 3 * (1/3 * log2(3)) = log2 3 = 1.585 بت، وPP = 2^(log2 3) = 3.00 بالضبط دون تقريب. الحالة الثانية، التوزيع المنحرف p(red) = 0.8 وp(blue) = p(green) = 0.1: log2(1/0.8) = 0.3219281 وlog2(1/0.1) = 3.3219281، فحدّ red يساوي 0.2575425، وحدّا blue وgreen يساوي كل منهما 0.3321928، والمجموع H = 0.9219281، أي 0.922 بت. وPP = 2^0.9219281 = 1.894646، أي 1.89 (نحو 1.9 برقمين معنويين). وللتحقق بتعريف perplexity مباشرة (الشريحة 33)، لنموذج يطابق الحقيقة تكون PP حاصل ضرب p(x)^(-p(x)): 0.8^(-0.8) * 0.1^(-0.1) * 0.1^(-0.1) = 1.195446 * 1.258925 * 1.258925 = 1.894646، وهو الجواب نفسه.

Entropy fell from 1.585 to 0.922 bits, so perplexity fell from 3.00 to 1.89. Skew reduces both. A model that always predicted red with probability 1 would have H = 0 bits and PP = 2⁰ = 1, the floor: one choice, no uncertainty.

انخفضت الـ entropy من 1.585 إلى 0.922 بت، فانخفضت perplexity من 3.00 إلى 1.89. الانحراف يخفّض الاثنين. ونموذج يتنبأ دائماً بـ red باحتمال 1 ستكون له H = 0 بت وPP = 2⁰ = 1، وهذا هو الحد الأدنى: خيار واحد ولا عدم يقين.

Cross-entropy, and why we need it

الإنتروبيا المتقاطعة (Cross-entropy)، ولماذا نحتاجها

Slide 102. Entropy needs the true distribution p. You do not have it. You have a model m. Cross-entropy measures the cost of encoding data drawn from p using a code built for m:

الشريحة 102. الـ entropy تحتاج التوزيع الحقيقي p، وهو ليس عندك. عندك نموذج m. والـ cross-entropy تقيس تكلفة ترميز بيانات مسحوبة من p باستخدام ترميز مبني على m:

H(p, m) = − Σ_x p(x) log₂ m(x)

تقول المعادلة: H(p, m) هي سالب مجموع p(x) log₂ m(x)، أي أن الأوزان من التوزيع الحقيقي p واللوغاريتم من النموذج m.

Weights from reality, logs from your model. In practice you never see p, so you approximate the per-word cross-entropy from one long test sequence W = w₁ … w_N:

الأوزان من الواقع، واللوغاريتمات من نموذجك. وفي التطبيق لا ترى p أبداً، فتقرّب الـ cross-entropy لكل كلمة من تسلسل اختبار واحد طويل W = w₁ … w_N:

H(W) = − 1N · log₂ P(w₁ w₂ … w_N)

أي أن H(W) تساوي سالب 1/N مضروباً في log₂ P(w₁ w₂ … w_N)، وهو احتمال النموذج لتسلسل الاختبار كله مقسوماً على طوله.

That is just "average number of bits your model spends per word on the test set". The key property is the direction of the inequality:

هذا ببساطة "متوسط عدد البتات التي ينفقها نموذجك لكل كلمة على مجموعة الاختبار". والخاصية الأساسية هي اتجاه المتباينة:

H(p, m) ≥ H(p) for every model m

أي أن H(p, m) ≥ H(p) لكل نموذج m.

Cross-entropy is an upper bound on the true entropy. You can never beat reality, only approach it. A better model has lower cross-entropy, and therefore a tighter bound. This also means a model cannot cheat by underestimating the true entropy.

الـ cross-entropy حد أعلى للـ entropy الحقيقية. لا يمكنك أبداً أن تتفوق على الواقع، بل أن تقترب منه فقط. النموذج الأفضل له cross-entropy أقل، وبالتالي حد أضيق. وهذا يعني أيضاً أن النموذج لا يستطيع الغش بـ التقليل من تقدير الـ entropy الحقيقية.

The link: PP = 2 to the cross-entropy

الرابط: PP تساوي 2 أُس الإنتروبيا المتقاطعة

Slide 102 states PP(W) = 2^H(W). It is one line of algebra from slide 33.

تذكر الشريحة 102 أن PP(W) = 2^H(W). وهي سطر جبري واحد انطلاقاً من الشريحة 33.

H(W) = − (1/N) log2 P(W)

2^H(W) = 2^( −(1/N) log2 P(W) )

       = ( 2^(log2 P(W)) )^(−1/N)

       = P(W)^(−1/N)                     this is slide 33's definition

       = 1 / P(W)^(1/N)

       = Nth root of ( 1 / P(W) )         this is slide 34's definition

الاشتقاق: نبدأ من H(W) = − (1/N) log2 P(W)، فيكون 2^H(W) = 2^( −(1/N) log2 P(W) )، أي ( 2^(log2 P(W)) )^(−1/N)، أي P(W)^(−1/N)، وهذا هو تعريف الشريحة 33. ثم 1 / P(W)^(1/N)، أي الجذر من الرتبة N لـ 1 / P(W)، وهذا هو تعريف الشريحة 34.

So all three expressions on slides 33, 34 and 102 are the same number. Perplexity was never a separate idea. It is the exponential of a cross-entropy, which is why "inverse probability normalised by length" looks arbitrary until you see this.

إذن التعابير الثلاثة في الشرائح 33 و34 و102 هي العدد نفسه. لم تكن perplexity فكرة منفصلة قط. إنها 2 مرفوعاً إلى cross-entropy، ولهذا تبدو عبارة "الاحتمال المعكوس مُطبَّعاً بالطول" اعتباطية حتى ترى هذا.

Quantityالكمية	Formulaالصيغة	Unitالوحدة	Needs the true p?هل تحتاج p الحقيقية؟	Directionالاتجاه
Entropy `H(p)`الإنتروبيا `H(p)`	− Σ p log₂ p	bitsبتات	yes, unavailableنعم، وهي غير متاحة	floor you cannot go belowحد أدنى لا يمكنك النزول تحته
Cross-entropy `H(p, m)`الإنتروبيا المتقاطعة `H(p, m)`	− Σ p log₂ m	bitsبتات	weights only, estimated from the test setالأوزان فقط، تُقدَّر من test set	lower is better, bounded below by H(p)الأقل أفضل، وحدّها الأدنى H(p)
Per-word estimate `H(W)`التقدير لكل كلمة `H(W)`	− (1/N) log₂ P(W)	bits per wordبتات لكل كلمة	noلا	lower is betterالأقل أفضل
Perplexity `PP(W)`Perplexity `PP(W)`	2^H(W) = P(W)^−1/N	effective choicesخيارات فعلية	noلا	lower is better, floor is 1الأقل أفضل، وحدّها الأدنى 1

يرتّب الجدول الكميات الأربع. Entropy H(p): صيغتها − Σ p log₂ p، ووحدتها البت، وتحتاج p الحقيقي غير المتاح، وهي أرضية لا يمكنك النزول تحتها. Cross-entropy H(p, m): صيغتها − Σ p log₂ m، ووحدتها البت، وتحتاج p للأوزان فقط وتُقدَّر من مجموعة الاختبار، والأقل أفضل، وحدها الأدنى H(p). التقدير لكل كلمة H(W): صيغته − (1/N) log₂ P(W)، ووحدته البت لكل كلمة، ولا يحتاج p، والأقل أفضل. وPerplexity PP(W): صيغتها 2^H(W) = P(W)^−1/N، ووحدتها عدد الخيارات الفعلية، ولا تحتاج p، والأقل أفضل، وحدها الأدنى 1.

Slide errata and trapsأخطاء الشرائح والفخاخ

Slide 102 writes the key link as PP(W) = 2^H(W) immediately after introducing H(p, m). The H(W) in that line is not the true entropy of the language and not H(X) from slide 101. It is the per-word cross-entropy of your model on the test sequence, that is, H(W) = −(1/N) log₂ P(w₁…w_N). The deck reuses the letter H for three different things across two slides. If you plug the true entropy into 2^H you get the perplexity of a perfect model, not of yours.

تكتب الشريحة 102 العلاقة الأساسية على شكل PP(W) = 2^H(W) مباشرة بعد تقديم H(p, m). والرمز H(W) في هذا السطر ليس الـ entropy الحقيقية للغة، وليس H(X) من الشريحة 101. إنه cross-entropy لكل كلمة لنموذجك على تسلسل الاختبار، أي H(W) = −(1/N) log₂ P(w₁…w_N). العرض يستخدم الحرف H لثلاثة أشياء مختلفة عبر شريحتين. وإذا وضعت الـ entropy الحقيقية في 2^H فستحصل على perplexity نموذج مثالي، لا نموذجك.

The exponent must be per-word. Forget the 1/N and you get 2^{−log₂ P(W)} = 1/P(W), which grows without bound as the test set lengthens. That is exactly the problem slide 32 says perplexity exists to fix.

يجب أن يكون الأس لكل كلمة. إذا نسيت 1/N فستحصل على 2^{−log₂ P(W)} = 1/P(W)، وهي تكبر بلا حدود كلما طالت مجموعة الاختبار. وهذه بالضبط المشكلة التي تقول الشريحة 32 إن perplexity وُجدت لحلها.

Base matters. PP = 2^H only holds when H is in bits. If you computed entropy in nats with natural log, perplexity is e^H. Mixing log₂ and e is a silent, catastrophic error.

الأساس مهم. العلاقة PP = 2^H لا تصح إلا عندما تكون H بالبتات. وإذا حسبت الـ entropy بوحدة nats باللوغاريتم الطبيعي، فإن perplexity تساوي e^H. والخلط بين log₂ وe خطأ صامت وكارثي.

Perplexity comparisons need identical vocabularies and tokenization (slide 36). Two models with different V have different bit budgets, so their perplexities are not comparable at all.

مقارنات perplexity تحتاج مفردات وtokenization متطابقة (الشريحة 36). نموذجان بمفردات V مختلفة لهما ميزانيتا بتات مختلفتان، فلا يمكن مقارنة قيم perplexity بينهما إطلاقاً.

Book aside: the horse race, section 3.7

استطراد من الكتاب: سباق الخيل، القسم 3.7

Eight horses, equally likely: H = log₂ 8 = 3 bits, so a fixed 3-bit code is optimal and PP = 8. Now skew the odds to 1/2, 1/4, 1/8, 1/16 and four at 1/64. Then H = 2 bits, so PP = 4: eight real horses, four effective choices. Short codes for likely horses, long codes for unlikely ones. Same story as the three colours, bigger numbers.

ثمانية خيول متساوية الاحتمال: H = log₂ 8 = 3 bits، فالترميز الثابت بـ 3 بتات هو الأمثل وPP = 8. والآن اجعل الاحتمالات منحرفة: 1/2 و1/4 و1/8 و1/16، وأربعة خيول باحتمال 1/64 لكل منها. عندها H = 2 bits، فتكون PP = 4: ثمانية خيول حقيقية، وأربعة خيارات فعلية. ترميزات قصيرة للخيول المرجّحة، وطويلة للخيول غير المرجّحة. القصة نفسها في الألوان الثلاثة، بأرقام أكبر.

Lecture 03 revision sheet

ورقة مراجعة المحاضرة 03

Slide 103 is the deck's own summary. Here is the version you can actually revise from. Every formula in the lecture, with the condition that triggers it.

الشريحة 103 هي ملخص العرض نفسه. وهذه هي النسخة التي يمكنك المراجعة منها فعلاً: كل معادلة في المحاضرة، مع الحالة التي تستدعي استخدامها.

Every formula, with when to use it

كل صيغة، ومتى تستخدمها

Formulaالصيغة	When to use itمتى تستخدمها	Slideالشريحة
Chain rule P(w_1:n) = Π_k P(w_k \| w_1:k−1)قاعدة السلسلة (Chain rule) P(w_1:n) = Π_k P(w_k \| w_1:k−1)	Exact, always true. Use to justify decomposing a sentence probability. Never computable directly.دقيقة وصحيحة دائماً. استخدمها لتبرير تفكيك احتمال جملة. لا يمكن حسابها مباشرة أبداً.	11
Markov assumption P(w_n \| w_1:n−1) ≈ P(w_n \| w_{n−N+1:n−1})افتراض ماركوف (Markov assumption) P(w_n \| w_1:n−1) ≈ P(w_n \| w_{n−N+1:n−1})	The approximation that makes n-grams possible. Keep only the last n − 1 words.التقريب الذي يجعل نماذج n-grams ممكنة. احتفظ بآخر n − 1 كلمة فقط.	12
Bigram MLE P(w_n \| w_n−1) = C(w_n−1, w_n) / C(w_n−1)MLE للـ bigram P(w_n \| w_n−1) = C(w_n−1, w_n) / C(w_n−1)	Any count-based estimate with no smoothing. Denominator is the history count because the row sums to it (slide 17).أي تقدير مبني على العدّ بلا تنعيم. المقام هو عدّ السياق لأن مجموع الصف يساويه (الشريحة 17).	16
General n-gram MLE C(w_n−N+1:n) / C(w_{n−N+1:n−1})MLE العام للـ n-gram C(w_n−N+1:n) / C(w_{n−N+1:n−1})	Same rule at any order: n-gram count over (n−1)-gram prefix count.القاعدة نفسها في أي رتبة: عدّ الـ n-gram مقسوماً على عدّ الـ prefix من رتبة (n−1).	20
Log probabilities log P(W) = Σ log P(w_i \| h)الاحتمالات اللوغاريتمية log P(W) = Σ log P(w_i \| h)	Whenever you multiply many small probabilities. Prevents underflow, turns products into sums.كلما ضربت احتمالات صغيرة كثيرة. تمنع underflow وتحوّل حواصل الضرب إلى مجاميع.	26
Perplexity PP(W) = P(W)^−1/NPerplexity PP(W) = P(W)^−1/N	The standard intrinsic metric. Lower is better. Minimising PP equals maximising test-set probability.المقياس الداخلي (intrinsic) القياسي. الأقل أفضل. تقليل PP يكافئ تعظيم احتمال test set.	33
Perplexity, chain-rule form PP(W) = ^N√( Π_i 1 / P(w_i \| w_<i) )Perplexity بصيغة قاعدة السلسلة PP(W) = ^N√( Π_i 1 / P(w_i \| w_<i) )	When you have per-word conditional probabilities. Geometric mean of inverse probabilities.عندما تكون لديك احتمالات شرطية لكل كلمة. المتوسط الهندسي لمقلوبات الاحتمالات.	34
Laplace, unigram (c_i + 1) / (N + V)Laplace للـ unigram (c_i + 1) / (N + V)	Add-one baseline. Denominator gains V because you added 1 to each of V types.خط أساس add-one. يزيد المقام بمقدار V لأنك أضفت 1 لكل نوع من الأنواع الـ V.	61
Laplace, bigram (C(w_n−1, w_n) + 1) / (C(w_n−1) + V)Laplace للـ bigram (C(w_n−1, w_n) + 1) / (C(w_n−1) + V)	Same, per history row. Moves far too much mass, so pedagogy only.الشيء نفسه لكل صف سياق. ينقل كتلة أكثر بكثير من اللازم، فهو للتعليم فقط.	62
Add-k (C(w_n−1, w_n) + k) / (C(w_n−1) + kV)Add-k (C(w_n−1, w_n) + k) / (C(w_n−1) + kV)	Add-one with a tunable k such as 0.1. Pick k on a dev set.add-one مع k قابل للضبط مثل 0.1. اختر k على dev set.	66
Linear interpolation λ₁P(w_n) + λ₂P(w_n\|w_n−1) + λ₃P(w_n\|w_n−2w_n−1), Σλ = 1الاستيفاء الخطي (Linear interpolation) λ₁P(w_n) + λ₂P(w_n\|w_n−1) + λ₃P(w_n\|w_n−2w_n−1), Σλ = 1	Mix all orders every time. These λs are tuned on held-out data.امزج كل الرتب في كل مرة. قيم λ هذه تُضبط فعلاً على بيانات held-out.	68
Stupid backoff S = count ratio if count > 0, else λ·S one order down, λ ≈ 0.4Stupid backoff S = نسبة العدّ إن كان العدّ > 0، وإلا λ·S في الرتبة الأدنى، مع λ ≈ 0.4	Web-scale shortcut. Not a probability distribution, and that is accepted.اختصار على مقياس الويب. ليس توزيعاً احتمالياً، وهذا مقبول.	73
Absolute discounting (C(w_i−1w_i) − d) / Σ_vC(w_i−1v) + λ(w_i−1)P(w_i)الخصم المطلق (Absolute discounting) (C(w_i−1w_i) − d) / Σ_vC(w_i−1v) + λ(w_i−1)P(w_i)	Subtract a constant d from seen counts, interpolate with the raw unigram.اطرح ثابتاً d من العدّات المرئية، واستوفِ مع الـ unigram الخام.	78
Ney discount estimate d = n₁ / (n₁ + 2n₂)تقدير Ney للخصم d = n₁ / (n₁ + 2n₂)	A principled d instead of the 0.75 heuristic. n₁ and n₂ count n-grams seen once and twice.قيمة d مبدئية بدل القاعدة التجريبية 0.75. n₁ وn₂ تعدّان الـ n-grams التي ظهرت مرة ومرتين.	79
Continuation count \|{ v : C(v, w) > 0 }\|عدّ الاستمرار (Continuation count) \|{ v : C(v, w) > 0 }\|	Whenever you need a lower-order Kneser-Ney quantity. Distinct preceding types, deduplicated.كلما احتجت كمية من رتبة أدنى في Kneser-Ney. الأنواع السابقة المختلفة، بعد إزالة التكرار.	82
Continuation probability P_CONT(w) = \|{v : C(v,w) > 0}\| / \|{(u,v) : C(u,v) > 0}\|احتمال الاستمرار (Continuation probability) P_CONT(w) = \|{v : C(v,w) > 0}\| / \|{(u,v) : C(u,v) > 0}\|	The Kneser-Ney backoff unigram. Denominator is total bigram types.الـ unigram الذي يتراجع إليه Kneser-Ney. المقام هو مجموع أنواع الـ bigrams (types).	83
Interpolated Kneser-Ney, bigram max(C(w_i−1w_i) − d, 0)/C(w_i−1) + λ(w_i−1)P_CONT(w_i)Kneser-Ney الاستيفائي، bigram max(C(w_i−1w_i) − d, 0)/C(w_i−1) + λ(w_i−1)P_CONT(w_i)	The one you will be asked to compute. Keep the max(·, 0).هذه هي التي سيُطلب منك حسابها. احتفظ بـ max(·, 0).	84
Kneser-Ney backoff weight λ(w_i−1) = (d / C(w_i−1)) · \|{w : C(w_i−1, w) > 0}\|وزن التراجع في Kneser-Ney λ(w_i−1) = (d / C(w_i−1)) · \|{w : C(w_i−1, w) > 0}\|	Computed, never tuned. Equals the probability mass that discounting removed.تُحسب ولا تُضبط أبداً. تساوي الكتلة الاحتمالية التي أزالها الخصم.	85
Recursive Kneser-Ney max(c_KN(·) − d, 0)/Σ_vc_KN(·v) + λ·P_KN one order downKneser-Ney التكراري max(c_KN(·) − d, 0)/Σ_vc_KN(·v) + λ·P_KN في الرتبة الأدنى	Any n-gram order. Drop the leftmost history word at each step.أي رتبة n-gram. احذف كلمة السياق الأبعد يساراً في كل خطوة.	94
c_KN definition count at the highest order, continuationcount at lower ordersتعريف c_KN العدّ (count) في الرتبة الأعلى، وعدّ الاستمرار (continuation count) في الرتب الأدنى	Every time you evaluate the recursive form. Single most missed detail in the Kneser-Ney block.في كل مرة تحسب فيها الصيغة التكرارية. أكثر تفصيلة تُنسى في قسم Kneser-Ney.	95
Unigram termination max(c_KN(w) − d, 0)/Σ_w′c_KN(w′) + λ(ε)·(1/V)إنهاء التكرار عند الـ unigram max(c_KN(w) − d, 0)/Σ_w′c_KN(w′) + λ(ε)·(1/V)	The recursion floor. Guarantees no probability is ever zero, including <UNK>.أرضية التكرار. تضمن ألا يكون أي احتمال صفراً أبداً، بما في ذلك <UNK>.	96
Modified Kneser-Ney d₁, d₂, d₃₊ for counts 1, 2, and 3 or moreKneser-Ney المعدَّل d₁ وd₂ وd₃₊ للعدّات 1 و2 و3 فأكثر	Best classic performance. Structure unchanged, only the discount is split by count.أفضل أداء بين الطرق الكلاسيكية. البنية لم تتغير، والخصم فقط يُقسَّم حسب العدّ.	98
Entropy H(X) = − Σ_x p(x) log₂ p(x)الإنتروبيا (Entropy) H(X) = − Σ_x p(x) log₂ p(x)	Bits of uncertainty. For k uniform outcomes it is log₂ k.بتات من عدم اليقين. لـ k نتائج متساوية الاحتمال تساوي log₂ k.	101
Perplexity and entropy PP(W) = 2^H(W), H(W) = −(1/N) log₂ P(W)Perplexity والإنتروبيا PP(W) = 2^H(W), H(W) = −(1/N) log₂ P(W)	To convert bits into effective choices, or to explain where perplexity comes from.لتحويل البتات إلى خيارات فعلية، أو لتشرح من أين تأتي perplexity.	102

دليل قراءة الجدول، بالترتيب: Chain rule (الشريحة 11) صحيحة دائماً، تستخدمها لتبرير تفكيك احتمال الجملة، ولا تُحسب مباشرة أبداً.
Markov assumption (الشريحة 12) هو التقريب الذي يجعل الـ n-grams ممكنة: احتفظ بآخر n − 1 كلمات فقط.
Bigram MLE (الشريحة 16) لأي تقدير مبني على العدّ دون smoothing، والمقام هو عدّ السياق لأن مجموع الصف يساويه (الشريحة 17).
General n-gram MLE (الشريحة 20) القاعدة نفسها بأي رتبة: عدّ الـ n-gram على عدّ البادئة ذات n−1.
Log probabilities (الشريحة 26) كلما ضربت احتمالات صغيرة كثيرة، تمنع underflow وتحوّل الضرب إلى جمع.
Perplexity (الشريحة 33) هي المقياس الداخلي القياسي، والأقل أفضل، وتقليلها يساوي تعظيم احتمال مجموعة الاختبار.
صيغة Perplexity بقاعدة السلسلة (الشريحة 34) عندما تكون لديك احتمالات شرطية لكل كلمة، وهي المتوسط الهندسي للاحتمالات المعكوسة.
Laplace unigram (الشريحة 61) خط الأساس add-one، ويزيد المقام بـ V لأنك أضفت 1 لكل نوع من الـ V أنواع.
Laplace bigram (الشريحة 62) الشيء نفسه لكل صف سياق، وينقل كتلة احتمال أكثر من اللازم بكثير، فهو للتعليم فقط.
Add-k (الشريحة 66) هو add-one مع k قابل للضبط مثل 0.1، ويُختار k على dev set.
Linear interpolation (الشريحة 68) تمزج كل الرتب في كل مرة، وقيم λ هنا تُضبط على بيانات held-out.
Stupid backoff (الشريحة 73) اختصار لمستوى الويب، وليس توزيعاً احتمالياً، وهذا مقبول.
Absolute discounting (الشريحة 78) اطرح ثابتاً d من العدّات المرئية، وامزج مع الـ unigram الخام.
Ney discount estimate (الشريحة 79) قيمة d مبدئية بدلاً من القاعدة التقريبية 0.75، وn₁ وn₂ عدد الـ n-grams التي ظهرت مرة واحدة ومرتين.
Continuation count (الشريحة 82) كلما احتجت كمية رتبة أدنى في Kneser-Ney: عدد الأنواع السابقة المختلفة، دون تكرار.
Continuation probability (الشريحة 83) هي الـ unigram الاحتياطي في Kneser-Ney، ومقامها العدد الكلي لـ أنواع الـ bigram.
Interpolated Kneser-Ney, bigram (الشريحة 84) هي التي سيُطلب منك حسابها، احتفظ بـ max(·, 0).
Kneser-Ney backoff weight (الشريحة 85) تُحسب ولا تُضبط أبداً، وتساوي كتلة الاحتمال التي أزالها الخصم.
Recursive Kneser-Ney (الشريحة 94) لأي رتبة n-gram، احذف كلمة السياق الأبعد يساراً في كل خطوة.
تعريف c_KN (الشريحة 95): العدّ الخام في الرتبة الأعلى، وcontinuation count في الرتب الأدنى، تستخدمه في كل مرة تحسب فيها الصيغة التكرارية، وهو أكثر تفصيل يُنسى في قسم Kneser-Ney.
Unigram termination (الشريحة 96) أرضية التكرار، وتضمن ألا يكون أي احتمال صفراً أبداً، بما في ذلك <UNK>.
Modified Kneser-Ney (الشريحة 98) أفضل أداء كلاسيكي، والبنية لا تتغير، فقط يُقسم الخصم حسب العدّ إلى d₁ وd₂ وd₃₊.
Entropy (الشريحة 101) بتات عدم اليقين، وتساوي log₂ k لـ k نتيجة متساوية.
Perplexity and entropy (الشريحة 102) لتحويل البتات إلى خيارات فعلية، أو لشرح من أين تأتي perplexity.

Ranked by exam risk

مرتبة حسب خطورتها في الامتحان

Risk means examined often and easy to fake. Spend your remaining minutes top down.

الخطورة تعني أن الموضوع يُمتحن كثيراً ويسهل التظاهر بفهمه. اصرف دقائقك المتبقية من الأعلى إلى الأسفل.

Perplexity, computed. Definition, chain-rule form, lower is better, weighted branching factor, and the fact that comparisons require identical vocabulary and tokenization. Slides 32 to 40. Page: Perplexity.
حساب perplexity. التعريف، وصيغة قاعدة السلسلة، والأقل أفضل، وweighted branching factor، وأن المقارنة تتطلب مفردات وtokenization متطابقة. الشرائح من 32 إلى 40. الصفحة: Perplexity.
Kneser-Ney continuation counts. Types not tokens, the max(·, 0), and λ as a computed budget. Be able to run the reading glasses numbers cold. Slides 80 to 93. Page: Kneser-Ney Smoothing.
Kneser-Ney continuation counts. الأنواع لا الرموز (types not tokens)، وmax(·, 0)، وλ كميزانية محسوبة. يجب أن تستطيع حساب أرقام reading glasses من الذاكرة. الشرائح من 80 إلى 93. الصفحة: Kneser-Ney Smoothing.
Add-one and add-k arithmetic. Both forms, the adjusted-count view, and why V in the denominator moves too much mass. Slides 61 to 66.
حسابات add-one وadd-k. الصيغتان، ومنظور العدّ المعدَّل (adjusted count)، ولماذا ينقل V في المقام كتلة أكثر من اللازم. الشرائح من 61 إلى 66.
Chain rule to Markov assumption. Write the exact decomposition, then state precisely what the approximation discards. Slides 11 to 12. Page: Chain Rule and the Markov Assumption.
من chain rule إلى Markov assumption. اكتب التفكيك الدقيق، ثم اذكر بدقة ما الذي يتجاهله التقريب. الشريحتان 11 و12. الصفحة: Chain Rule and the Markov Assumption.
Entropy, cross-entropy, PP = 2^H. Know the direction of the bound, H(p, m) ≥ H(p), and the uniform case 2^{log₂ k} = k. Slides 101 to 102. This page.
Entropy وcross-entropy وPP = 2^H. اعرف اتجاه الحد H(p, m) ≥ H(p)، والحالة المتساوية 2^{log₂ k} = k. الشريحتان 101 و102. هذه الصفحة.
Absolute discounting and d ≈ 0.75. The Church and Gale held-out table and the Ney estimate d = n₁/(n₁ + 2n₂). Slides 75 to 79. Page: Absolute Discounting.
Absolute discounting وd ≈ 0.75. جدول held-out لـ Church and Gale، وتقدير Ney d = n₁/(n₁ + 2n₂). الشرائح من 75 إلى 79. الصفحة: Absolute Discounting.
The c_KN level rule. Raw count at the highest order only. Slides 94 to 96. Page: General and Modified Kneser-Ney.
قاعدة مستويات c_KN. العدّ الخام في الرتبة الأعلى فقط. الشرائح من 94 إلى 96. الصفحة: General and Modified Kneser-Ney.
Interpolation versus backoff. Interpolation always mixes orders; backoff picks the highest seen order. Slides 67 to 72.
Interpolation مقابل backoff. الـ interpolation يمزج الرتب دائماً، والـ backoff يختار أعلى رتبة مرئية. الشرائح من 67 إلى 72.
Sampling and the Shakespeare versus WSJ contrast. Higher n means more coherence and more memorisation; train on the right genre. Slides 41 to 56. Pages: Sampling, Generalization.
الـ sampling والمقارنة بين Shakespeare وWSJ. كلما زادت n زاد الترابط وزاد الحفظ الحرفي، ودرّب على النوع الصحيح من النصوص. الشرائح من 41 إلى 56. الصفحتان: Sampling وGeneralization.
Applications and definitions. Cheap marks. Slides 2 to 9. Page: Why Predict the Next Word?.
التطبيقات والتعريفات. درجات سهلة. الشرائح من 2 إلى 9. الصفحة: Why Predict the Next Word?.

Revision index

فهرس المراجعة

01Why Predict the Next Word?لماذا نتنبأ بالكلمة التالية؟Definition of an LM, four applications, what an n-gram isتعريف نموذج اللغة (LM)، وأربعة تطبيقات، وما هو الـ n-gramSlides 2–9 02Chain Rule and the Markov Assumptionقاعدة السلسلة وافتراض ماركوف (Markov)Exact decomposition, then the approximation that makes it tractableالتفكيك الدقيق، ثم التقريب الذي يجعله قابلاً للحسابSlides 10–16 03Maximum Likelihood Estimationتقدير الأرجحية العظمى (MLE)Counting bigrams, and why the denominator is the context countعدّ الـ bigrams، ولماذا المقام هو عدّ السياقSlides 16–21 04The Berkeley Restaurant Exampleمثال مطعم BerkeleyCounts matrix, probabilities matrix, a full sentence, log spaceمصفوفة العدّات، ومصفوفة الاحتمالات، وجملة كاملة، والحساب في فضاء اللوغاريتمSlides 22–27 05Evaluating a Language Modelتقييم النموذج اللغويExtrinsic versus intrinsic, train/dev/test, data contaminationالتقييم الخارجي مقابل الداخلي، وtrain/dev/test، وتلوّث البياناتSlides 28–32 06Perplexityالحيرة (Perplexity)Definition, chain-rule form, branching factor, three-colour exampleالتعريف، وصيغة قاعدة السلسلة، وbranching factor، ومثال الألوان الثلاثةSlides 33–40 07Samplingأخذ العينات (Sampling)Generating from unigram and bigram modelsالتوليد من نماذج unigram وbigramSlides 41–52 08Generalizationالتعميم (Generalization)Shakespeare versus WSJ, genre dependence, zeros appearShakespeare مقابل WSJ، والاعتماد على نوع النص، وظهور الأصفارSlides 53–60 09Laplace and Add-k Smoothingتنعيم Laplace وAdd-kAdd-one for unigrams and bigrams, smoothed counts, why it is too bluntadd-one للـ unigrams والـ bigrams، والعدّات المنعَّمة، ولماذا هو فظّ أكثر من اللازمSlides 60–66 10Interpolation and Backoffالاستيفاء (Interpolation) والتراجع (Backoff)Linear interpolation, context-dependent lambdas, stupid backofflinear interpolation، وقيم λ المعتمدة على السياق، وstupid backoffSlides 67–73 11Absolute Discountingالخصم المطلق (Absolute Discounting)Church and Gale held-out counts, d ≈ 0.75, Ney's estimateعدّات held-out لـ Church and Gale، وd ≈ 0.75، وتقدير NeySlides 74–79 12Kneser-Ney Smoothingتنعيم Kneser-NeyContinuation counts, the bigram formula, full toy computationالـ continuation counts، وصيغة الـ bigram، وحساب كامل على مثال صغيرSlides 80–93 13General and Modified Kneser-NeyKneser-Ney العام والمعدَّلRecursive form, c_KN by level, three discountsالصيغة التكرارية، وc_KN حسب المستوى، وثلاثة خصوماتSlides 94–100 ··All thirty pages, including lectures 02 and 04كل الصفحات الثلاثين، بما فيها المحاضرتان 02 و04Words and tokens, n-grams, and word embeddingsكل الصفحات الثلاثين، بما فيها المحاضرتان 02 و04: الكلمات والرموز، وn-grams، وword embeddingsIndex

Slide 103 in nine lines

الشريحة 103 في تسعة أسطر

Language models assign probabilities to sequences and predict the next word or token.
نماذج اللغة تعطي احتمالات للتسلسلات وتتنبأ بالكلمة أو الـ token التالي.
N-grams apply a Markov assumption: a limited window of context.
الـ n-grams تطبّق Markov assumption: نافذة سياق محدودة.
MLE estimates from counts, and the resulting tables are sparse.
MLE يقدّر من العدّات، والجداول الناتجة متناثرة (sparse).
Evaluate on held-out test data, tune on a dev set.
قيّم على بيانات اختبار محجوزة، واضبط على dev set.
Perplexity is the standard intrinsic metric, lower is better.
الـ perplexity هي المقياس الداخلي القياسي، والأقل أفضل.
Sampling visualises the learned distribution and exposes overfitting.
الـ sampling يُظهر التوزيع المتعلَّم ويكشف overfitting.
Smoothing deals with zeros: add-k, interpolation, backoff.
الـ smoothing يعالج الأصفار: add-k، وinterpolation، وbackoff.
Kneser-Ney makes the lower-order distribution a continuation model.
Kneser-Ney يجعل توزيع الرتبة الأدنى نموذج استمرار (continuation).
Modified Kneser-Ney uses multiple discounts d₁, d₂, d₃₊ for best performance.
Modified Kneser-Ney يستخدم عدة خصومات d₁, d₂, d₃₊ لأفضل أداء.

If you remember only four sentencesإن لم تتذكر إلا أربع جمل

1. N-grams are the chain rule plus a Markov assumption plus counting.
2. Perplexity is the inverse test probability normalised by length, and it equals 2 to the per-word cross-entropy.
3. Smoothing exists because MLE assigns zero to anything unseen, and a single zero destroys an entire sentence probability.
4. Kneser-Ney backs off to how many different friends a word has, not to how popular it is.

1. الـ n-grams هي chain rule زائد Markov assumption زائد العدّ.
2. الـ perplexity هي احتمال الاختبار المعكوس مُطبَّعاً بالطول، وتساوي 2 مرفوعاً إلى cross-entropy لكل كلمة.
3. الـ smoothing موجود لأن MLE يعطي صفراً لكل ما لم يُرَ، وصفر واحد يدمّر احتمال جملة كاملة.
4. Kneser-Ney يرجع إلى عدد الأصدقاء المختلفين للكلمة، لا إلى مدى شهرتها.

Check yourself

اختبر نفسك

A distribution is uniform over k outcomes. What are H and PP?

توزيع متساوٍ على k نتيجة. ما قيمتا H وPP؟

C. H = −Σ (1/k) log₂(1/k) = log₂ k, and PP = 2^{log₂ k} = k. This is the cleanest statement of the whole relationship: with k equally likely options the perplexity is literally the number of options. D forgets to exponentiate and so reports bits where choices were asked for. A confuses the quantity with its exponent in the wrong direction.

الجواب C. H = −Σ (1/k) log₂(1/k) = log₂ k، وPP = 2^{log₂ k} = k. هذه أنظف صياغة للعلاقة كلها: مع k خيار متساوي الاحتمال تكون perplexity حرفياً عدد الخيارات. والخيار D ينسى الرفع إلى الأس فيعطي بتات بينما المطلوب خيارات. والخيار A يخلط بين الكمية وأسّها في الاتجاه الخاطئ.

For P(red) = 0.8, P(blue) = P(green) = 0.1, the entropy is 0.922 bits. What is the perplexity?

لـ P(red) = 0.8 وP(blue) = P(green) = 0.1، الـ entropy تساوي 0.922 بت. فما قيمة perplexity؟

B. PP = 2^H = 2^0.9219 = 1.8946. A is the number of outcomes in the vocabulary, which is the perplexity only when the distribution is uniform, and that is precisely what has changed here. C skips the exponentiation entirely. D inverts instead of exponentiating: the inverse appears in P(W)^−1/N, not in the bits-to-choices conversion.

الجواب B. PP = 2^H = 2^0.9219 = 1.8946. الخيار A هو عدد النتائج في المفردات، وهو يساوي perplexity فقط عندما يكون التوزيع متساوياً، وهذا بالضبط ما تغيّر هنا. والخيار C يتخطى الرفع إلى الأس تماماً. والخيار D يقلب بدلاً من أن يرفع إلى الأس: المقلوب يظهر في P(W)^−1/N، لا في تحويل البتات إلى خيارات.

Which inequality does slide 102 assert about cross-entropy?

أي متباينة تقرّرها الشريحة 102 عن الـ cross-entropy؟

A. Encoding data from p with a code designed for m can only cost more, never less, with equality exactly when m = p. B is the trap, and the direction matters: the textbook notes a model cannot err by underestimating the true entropy. C is false for any real model; equality requires the model to be exactly correct. D mixes bits and choices in a single inequality, which is unit nonsense.

الجواب A. ترميز بيانات من p بترميز مصمَّم لـ m لا يمكن إلا أن يكلّف أكثر، لا أقل أبداً، والتساوي يحدث فقط عندما m = p. والخيار B هو الفخ، والاتجاه مهم: يذكر الكتاب أن النموذج لا يمكن أن يخطئ بالتقليل من تقدير الـ entropy الحقيقية. والخيار C خاطئ لأي نموذج حقيقي، فالتساوي يتطلب أن يكون النموذج صحيحاً تماماً. والخيار D يخلط البتات والخيارات في متباينة واحدة، وهذا هراء من ناحية الوحدات.

Why does the exponent in PP(W) = 2^H(W) have to be the per-word cross-entropy?

لماذا يجب أن يكون الأس في PP(W) = 2^H(W) هو الـ cross-entropy لكل كلمة؟

D. The 1/N is exactly the length normalisation that slide 32 says perplexity exists to provide, and it is what turns the quantity into a geometric mean. 2^{−log₂P(W)} = 1/P(W) is astronomically large for any real corpus. A is false: entropy is defined for any random variable, including a whole sequence. B confuses normalising by length with normalising by vocabulary, and nothing cancels later, which rules out C.

الجواب D. الـ 1/N هو بالضبط التطبيع بالطول الذي تقول الشريحة 32 إن perplexity وُجدت لتوفيره، وهو ما يحوّل الكمية إلى متوسط هندسي. و2^{−log₂P(W)} = 1/P(W) كبير جداً لأي corpus حقيقي. والخيار A خاطئ: الـ entropy معرّفة لأي متغير عشوائي، بما في ذلك تسلسل كامل. والخيار B يخلط بين التطبيع بالطول والتطبيع بحجم المفردات، ولا شيء يُلغى لاحقاً، وهذا يستبعد C.

Which single sentence best captures the relationship between entropy and perplexity?

أي جملة واحدة تلخص العلاقة بين entropy وperplexity على أفضل وجه؟

B. Bits are the exponent and perplexity is the answer. The uniform case makes it concrete: log₂ 3 = 1.585 bits is the same statement as 3 choices. A invents a speed dimension that neither quantity has. C is wrong because both apply to any probabilistic model. D swaps train and test for no reason and reverses the two concepts.

الجواب B. البتات هي الأس، والـ perplexity هي الناتج. والحالة المتساوية تجعل ذلك ملموساً: log₂ 3 = 1.585 بت هي العبارة نفسها مثل 3 خيارات. والخيار A يخترع بُعد سرعة لا تملكه أي من الكميتين. والخيار C خاطئ لأن الاثنتين تنطبقان على أي نموذج احتمالي. والخيار D يبدّل بين التدريب والاختبار بلا سبب ويعكس المفهومين.