Lecture 03 · N-grams

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

Kneser-Ney Smoothing

تنعيم Kneser-Ney

Slides 80–93الشرائح 80–93 P1 MUSTP1 ضروري

The one smoothing method the exam will make you compute by hand: why the backoff unigram must be a continuation model, and the full toy calculation end to end.

هذه هي طريقة smoothing الوحيدة التي سيُطلب منك حسابها باليد في الاختبار: لماذا يجب أن يكون unigram الذي نرجع إليه في backoff نموذج continuation، مع الحساب الكامل للمثال المصغّر من أوله إلى آخره.

Read this firstاقرأ هذا أولاً

Kneser-Ney is absolute discounting with one change. The discounted first term is identical to slide 78. Only the thing you back off to changes: not the raw unigram P(w), but a continuation distribution P_CONT(w). Everything on this page is that one swap plus its bookkeeping.

Kneser-Ney هو absolute discounting مع تغيير واحد فقط. الحد الأول المخصوم مطابق تماماً لما في الشريحة 78. الشيء الوحيد الذي تغيّر هو ما نرجع إليه في backoff: ليس unigram الخام P(w)، بل توزيع continuation اسمه P_CONT(w). كل ما في هذه الصفحة هو هذا التبديل الواحد وما يترتب عليه من حسابات.

The example that forces the idea

المثال الذي يفرض الفكرة

Slide 80 gives the book's sentence:

تعطي الشريحة 80 الجملة التي يستخدمها الكتاب:

I can't see without my reading ______

You want glasses. A bigram model has never seen reading glasses often enough to be confident, so it leans on the lower-order unigram. And the raw unigram prefers Kong.

الكلمة التي تريدها هي glasses. لكن نموذج bigram لم يرَ reading glasses بعدد مرات يكفي ليكون واثقاً، فيتّكئ على unigram الأدنى رتبة. وunigram الخام يفضّل Kong.

Why? Because Hong Kong is a frequent phrase, so the token Kong is frequent. But Kong is frequent for a single reason. It appears after exactly one word, ever: Hong. It is not a versatile continuation. It is a prisoner of one phrase.

لماذا؟ لأن عبارة Hong Kong متكررة كثيراً، فتصبح الكلمة Kong متكررة بدورها. لكن تكرار Kong سببه واحد فقط: هي تأتي بعد كلمة واحدة فقط في corpus كله، وهي Hong. فهي ليست continuation مرنة تصلح في أي مكان، بل سجينة عبارة واحدة.

glasses, meanwhile, follows reading, sun, safety, my, and many more. It shows up all over the place.

أما glasses فهي تأتي بعد reading وsun وsafety وmy وغيرها كثير. أي أنها تظهر في كل مكان وبعد سياقات متنوعة.

The hookالمدخل

Ordinary unigram asks "how popular is this word?"
Kneser-Ney asks "how many different friends does this word have?"

unigram العادي يسأل: "كم هذه الكلمة مشهورة؟"
وKneser-Ney يسأل سؤالاً مختلفاً: "كم عدد الأصدقاء المختلفين لهذه الكلمة؟"

Popularity is a token count. Friends are context types. For guessing a novel continuation, friends win.

الشهرة هي عدّ tokens، أما الأصدقاء فهم أنواع السياقات (context types). وعند تخمين continuation جديدة لم تُرَ من قبل، الأصدقاء هم من يفوز، لا الشهرة.

Picture it

تخيّلها

Count arrows, not tokens. Kong has one arrow into it. glasses has four. Kneser-Ney scores the arrows.

عُدّ الأسهم لا الـ tokens. Kong يدخل إليها سهم واحد، وglasses يدخل إليها أربعة. وKneser-Ney يعطي الدرجة على الأسهم.

يرسم الشكل الفكرة كلها: عُدّ الأسهم، لا tokens. الكلمة Kong يدخل إليها سهم واحد فقط (من Hong) رغم أن عدد ظهورها 30، أما glasses فيدخل إليها أربعة أسهم من أربع كلمات مختلفة رغم أن عدد ظهورها 4 فقط. Kneser-Ney يعطي الدرجة للأسهم، لا للتكرار.

Continuation count

عدّ الاستمرار (Continuation count)

Slide 82. For a word w, the continuation count is the number of distinct word types that precede it:

الشريحة 82. بالنسبة لكلمة w، فإن continuation count هو عدد أنواع الكلمات المختلفة التي تأتي قبلها:

continuationcount(w) = |{ v : C(v, w) > 0 }|

Read it literally: collect every word v that was ever followed by w, throw away duplicates, count what is left. Equivalently, it is the number of bigram types ending in w.

اقرأها حرفياً: اجمع كل كلمة v جاءت w بعدها في أي موضع، ثم احذف المكرر، ثم عُدّ ما تبقّى. وبصيغة أخرى مكافئة تماماً: هو عدد أنواع bigram التي تنتهي بـ w.

The book's phrasing is worth memorising: every bigram type was a novel continuation the first time it was seen. So the number of bigram types a word completes is a direct estimate of how often it shows up somewhere new.

صياغة الكتاب تستحق الحفظ: كل نوع bigram كان في المرة الأولى التي ظهر فيها novel continuation، أي استمراراً جديداً لم يُرَ سابقاً. ولذلك فإن عدد أنواع bigram التي تُكملها الكلمة هو تقدير مباشر لمدى قدرتها على الظهور في موضع جديد.

Continuation probability

احتمال الاستمرار (Continuation probability)

Slide 83. Normalise the continuation count by the total number of bigram types in the corpus:

الشريحة 83. نُطبّع (normalise) قيمة continuation count بالقسمة على العدد الكلي لأنواع bigram في corpus:

P_CONT(w) = |{ v : C(v, w) > 0 }||{ (u, v) : C(u, v) > 0 }|

Numerator: how many distinct contexts lead to w. Denominator: how many distinct bigrams exist at all. The result is a proper distribution over the vocabulary, because every bigram type has exactly one second word, so summing the numerator over all w reproduces the denominator.

البسط: كم سياقاً مختلفاً يؤدي إلى w. المقام: كم نوع bigram موجود في corpus أصلاً. والناتج توزيع احتمالي سليم على vocabulary، والسبب أن كل نوع bigram له كلمة ثانية واحدة بالضبط، فإذا جمعت البسط على كل الكلمات w حصلت على المقام نفسه، فيكون المجموع 1.

Exam trapفخ امتحان

The denominator counts bigram types, not bigram tokens. In the toy corpus below there are 34 bigram tokens but only 5 bigram types. The denominator is 5. If you write 34 you have built an ordinary unigram model wearing a Kneser-Ney costume, and Kong wins again.

المقام يعدّ أنواع bigram (types)، لا ظهوراتها (tokens). في المثال المصغّر أدناه عندنا 34 bigram token لكن 5 bigram types فقط. إذن المقام هو 5. وإذا كتبت 34 فأنت في الحقيقة بنيت نموذج unigram عادياً متنكراً بثوب Kneser-Ney، وستعود Kong لتفوز من جديد.

Same trap in the numerator: C(Hong Kong) = 30 contributes 1 to the continuation count of Kong, not 30. Repeat visits from the same friend do not make a new friend.

والفخ نفسه موجود في البسط: C(Hong Kong) = 30 تُسهم بـ 1 فقط في continuation count للكلمة Kong، لا بـ 30. فالزيارات المتكررة من الصديق نفسه لا تصنع صديقاً جديداً.

Raw frequency versus continuation count, side by side

التكرار الخام مقابل عدّ الاستمرار، جنباً إلى جنب

Question being askedالسؤال المطروح	Raw unigram P(w)الـ unigram الخام P(w)	Continuation P_CONT(w)الاستمرار P_CONT(w)
What it measuresماذا يقيس	How often `w` occursكم مرة تظهر `w`	How many distinct words precede `w`كم كلمة مختلفة تسبق `w`
Counting unitوحدة العدّ	Tokensالـ tokens	Bigram typesأنواع الـ bigrams (types)
Numerator for `Kong`البسط لـ `Kong`	30	1
Numerator for `glasses`البسط لـ `glasses`	4	4
Denominatorالمقام	34 tokens34 من الـ tokens	5 types5 أنواع
P(`Kong`)	30/34 = 0.882	1/5 = 0.200
P(`glasses`)	4/34 = 0.118	4/5 = 0.800
Which word it prefersأي كلمة يفضّل	`Kong` (wrong)`Kong` (خطأ)	`glasses` (right)`glasses` (صواب)
Hurt by one frequent phraseيتضرر من عبارة واحدة متكررة	Yes, badlyنعم، وبشدة	No, the phrase counts onceلا، العبارة تُعدّ مرة واحدة

يقارن الجدول سؤالين مختلفين: unigram الخام يسأل "كم مرة ظهرت w"، وP_CONT يسأل "كم كلمة مختلفة جاءت قبل w". الأهم أن تلاحظ انقلاب الترتيب في الصفّين الملوّنين: P(Kong) تهبط من 0.882 إلى 0.200، وP(glasses) ترتفع من 0.118 إلى 0.800. ولاحظ كذلك اختلاف المقام: 34 tokens في العمود الأول مقابل 5 types في العمود الثاني، وهذا هو مصدر الانقلاب كله.

Note that glasses has the same numerator either way (4 tokens, 4 contexts, because each occurrence happened after a different word). The whole flip comes from Kong: 30 tokens collapse to 1 context.

لاحظ أن glasses بسطها هو نفسه في الحالتين (4 tokens و4 سياقات، لأن كل ظهور لها جاء بعد كلمة مختلفة). الانقلاب كله سببه Kong: ثلاثون token تنضغط إلى سياق واحد.

The interpolated Kneser-Ney bigram formula

صيغة bigram لـ Kneser-Ney الاستيفائي

Slide 84.

الشريحة 84.

P_KN(w_i | w_i−1) = max(C(w_i−1 w_i) − d, 0)C(w_i−1) + λ(w_i−1) · P_CONT(w_i)

First term: discounted bigram

الحد الأول: الـ bigram المخصوم

Take the observed bigram count, subtract a fixed discount d (usually 0.75), divide by the history count. Exactly absolute discounting from slide 78.

خُذ عدّ bigram الذي رصدته، واطرح منه خصماً ثابتاً d (عادة 0.75)، ثم اقسم على عدّ السياق السابق (history). هذا هو absolute discounting نفسه من الشريحة 78 بلا أي تغيير.

The max(·, 0) is a floor. If the bigram was never seen, C = 0 and 0 − 0.75 = −0.75, so without the floor you would get a negative probability.

الدالة max(·, 0) هي حدّ أدنى يمنع النزول تحت الصفر. فلو كان bigram لم يُرَ أبداً، يكون C = 0 و0 − 0.75 = −0.75، أي أنك بدون هذا الحدّ ستحصل على احتمال سالب، وهذا مستحيل.

Second term: continuation backoff

الحد الثاني: التراجع إلى الاستمرار

The mass you just discounted has to go somewhere. It is handed to P_CONT, weighted by λ(w_i−1).

الكتلة الاحتمالية التي خصمتها قبل قليل لا يصح أن تضيع، فلا بد أن تذهب إلى مكان. وهي تُسلَّم إلى P_CONT بوزن مقداره λ(w_i−1).

This is the only line that differs from plain absolute discounting. Swap P_CONT for P and you are back to slide 78.

هذا هو السطر الوحيد الذي يختلف عن absolute discounting المجرّد. استبدل P_CONT بـ P وتعود فوراً إلى الشريحة 78.

Two traps in one formulaفخّان في صيغة واحدة

1. Never drop the max(·, 0). Unseen bigrams must contribute exactly 0 from the first term, not a negative number. For a seen bigram with C = 1 and d = 0.75, the max does nothing (0.25 is already positive), which is why students forget it exists until the question gives them a zero count.

1. لا تحذف max(·, 0) أبداً. bigrams التي لم تُرَ يجب أن تُسهم بصفر بالضبط من الحد الأول، لا بعدد سالب. وفي حالة bigram مرصود بـ C = 1 وd = 0.75، لا تفعل max شيئاً (لأن 0.25 موجبة أصلاً)، ولهذا ينسى الطلاب وجودها أساساً حتى يأتي سؤال الاختبار بعدّ يساوي صفراً فتنكشف الغلطة.

2. "Interpolated" means both terms always fire. Even when the bigram is seen 30 times you still add the backoff term. This is not backoff-if-zero. Compare with stupid backoff on slide 73, which picks one branch or the other.

2. كلمة "Interpolated" تعني أن الحدّين يعملان دائماً معاً. حتى لو رُصد bigram ثلاثين مرة، تبقى تجمع حد backoff أيضاً. فهذه ليست طريقة "ارجع فقط إذا كان العدّ صفراً". قارنها بـ stupid backoff في الشريحة 73، فهي تختار فرعاً واحداً من الفرعين ولا تجمعهما.

Where λ comes from: it is a budget, not a hyperparameter

من أين تأتي λ: إنها ميزانية لا معامل فائق (hyperparameter)

Slide 85.

الشريحة 85.

λ(w_i−1) = dC(w_i−1) · |{ w : C(w_i−1, w) > 0 }|

Think of it as accounting. Let N(h) be the number of distinct words that have followed the history h.

تعامل معها كأنها عملية محاسبة. ليكن N(h) هو عدد الكلمات المختلفة التي جاءت بعد السياق h.

You subtracted d from each of the N(h) distinct continuations of h. You did not subtract d from each token, only from each distinct type.
أنت طرحت d من كل واحدة من N(h) من continuations المختلفة للسياق h. ولم تطرح d من كل token، بل من كل نوع مختلف فقط.
Total count you removed: d × N(h).
إذن مجموع العدّ الذي سحبته هو d × N(h).
In probability terms everything after h is divided by C(h), so the removed probability mass is d × N(h) / C(h).
وبلغة الاحتمال، كل شيء بعد h مقسوم على C(h)، فتكون الكتلة الاحتمالية المسحوبة هي d × N(h) / C(h).
That expression is λ(h). It is forced. There is nothing left to choose.
وهذا التعبير هو λ(h) بعينه. فهو مفروض عليك بحكم الحساب، ولا يبقى لك فيه أي خيار تختاره.

Memory trickحيلة للحفظ

λ is a receipt, not a dial. It is literally "how much I took, expressed as a probability". The only free parameter in Kneser-Ney is d. The interpolation weights λ₁, λ₂, λ₃ on slide 68 are tuned on a dev set; the λ(h) here is computed from counts for every history separately.

λ فاتورة، لا مقبض تضبطه. فهي حرفياً تعني "كم أخذتُ، معبَّراً عنه كاحتمال". المُعامل الحرّ الوحيد في Kneser-Ney هو d. أما أوزان interpolation أي λ₁, λ₂, λ₃ في الشريحة 68 فتُضبط على dev set، بينما λ(h) هنا تُحسب من العدّات لكل سياق على حدة.

Why it sums to 1

لماذا يساوي المجموع 1

Slide 86 asserts it and tells you to always check. Here is the one-line proof. Fix a history h, write N(h) = |{w : C(h, w) > 0}|, and use the fact from slide 17 that the bigram counts out of h sum to C(h).

الشريحة 86 تؤكد هذه الحقيقة وتوصيك بالتحقق منها دائماً. وهذا هو الإثبات في سطر واحد: ثبّت سياقاً h، واكتب N(h) = |{w : C(h, w) > 0}|، واستخدم الحقيقة المعروفة من الشريحة 17 وهي أن عدّات bigram الخارجة من h مجموعها يساوي C(h).

Σ_w P_KN(w | h)

  = Σ_{w : C(h,w) > 0}  [ C(h,w) − d ] / C(h)   +   λ(h) · Σ_w P_CONT(w)

                                                       \_____ = 1 _____/
      unseen w contribute 0 because of max(·, 0)

  = [ Σ_w C(h,w) − d · N(h) ] / C(h)            +   λ(h)

  = [ C(h) − d · N(h) ] / C(h)                  +   d · N(h) / C(h)

  = 1 − d·N(h)/C(h)  +  d·N(h)/C(h)

  = 1

The discounted mass and λ(h) are the same quantity written twice, once with a minus sign. That is the whole argument, and it is the sanity check slide 86 wants: backoff weight must equal total discounted mass.

الكتلة المخصومة وλ(h) هما الكمية نفسها مكتوبة مرتين، إحداهما بإشارة سالبة، فيلغي أحدهما الآخر ويبقى 1. هذه هي الحجة كلها، وهي نفسها فحص السلامة الذي تطلبه الشريحة 86: وزن backoff يجب أن يساوي مجموع الكتلة المخصومة.

The toy corpus, worked end to end

الـ corpus التجريبي، محلولاً من البداية إلى النهاية

Slides 87 to 93. Here is the corpus exactly as the deck states it, with d = 0.75.

الشرائح 87 إلى 93. هذا هو corpus كما ورد في العرض حرفياً، مع d = 0.75.

Bigram typeنوع الـ bigram	Count (tokens)العدّ (tokens)	Contributes a context toيضيف سياقاً إلى
`Hong Kong`	30	`Kong`
`reading glasses`	1	`glasses`
`sun glasses`	1	`glasses`
`safety glasses`	1	`glasses`
`my glasses`	1	`glasses`
Totalsالمجاميع	34 tokens34 من الـ tokens	5 bigram types5 أنواع من الـ bigrams

يسرد الجدول corpus المصغّر كله: خمسة أنواع bigram فقط، مجموع ظهوراتها 34 token. الذي يجب أن تلاحظه هو العمود الأخير: Hong Kong وحدها بعدّ 30 تُسهم بسياق واحد للكلمة Kong، بينما الأسطر الأربعة الأخرى، وعدّ كل منها 1 فقط، تُسهم بأربعة سياقات مختلفة للكلمة glasses. سطر المجاميع هو مصدر الفخ: 34 هو tokens، و5 هو types، ومقام P_CONT هو 5.

bigram types = 5 bigram tokens = 34 d = 0.75

The crossed-out chip is the number that is not the P_CONT denominator. Everything below uses 5.

البطاقة المشطوبة هي الرقم الذي ليس مقام P_CONT. كل ما يأتي بعد هذا السطر يستخدم 5.

Step 1, slide 88: continuation probabilities

الخطوة 1، الشريحة 88: احتمالات الاستمرار

Distinct contexts before Kong    : {Hong}                        => 1
Distinct contexts before glasses : {reading, sun, safety, my}     => 4
Total bigram types                                                =  5

P_CONT(Kong)    = 1 / 5 = 0.2
P_CONT(glasses) = 4 / 5 = 0.8

check: 0.2 + 0.8 = 1.0   (only these two words ever appear as continuations)

Step 2, slide 89: the backoff weight for the history `reading`

الخطوة 2، الشريحة 89: وزن التراجع للسياق `reading`

C(reading) = 1                         (reading occurs once, before glasses)
N(reading) = |{w : C(reading, w) > 0}| = |{glasses}| = 1

lambda(reading) = ( d / C(reading) ) * N(reading)
                = ( 0.75 / 1 ) * 1
                = 0.75

So three quarters of the probability mass after reading is handed to the continuation model. That is enormous, and correctly so: one observation of reading glasses is almost no evidence.

أي أن ثلاثة أرباع الكتلة الاحتمالية بعد reading تُسلَّم إلى نموذج continuation. وهذه نسبة ضخمة، وهي صحيحة تماماً: مشاهدة واحدة فقط لـ reading glasses لا تكاد تكون دليلاً على شيء، فمن الحكمة أن يعتمد النموذج على المستوى الأدنى.

Steps 3 and 4, slides 90 and 91: the two answers

الخطوتان 3 و4، الشريحتان 90 و91: الإجابتان

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

P_KN(glasses | reading)

  first term  = max( C(reading glasses) − d , 0 ) / C(reading)
              = max( 1 − 0.75 , 0 ) / 1
              = max( 0.25 , 0 ) / 1
              = 0.25 / 1
              = 0.25

  backoff     = lambda(reading) * P_CONT(glasses)
              = 0.75 * 0.8
              = 0.60

  total       = 0.25 + 0.60
              = 0.85


P_KN(Kong | reading)

  first term  = max( C(reading Kong) − d , 0 ) / C(reading)
              = max( 0 − 0.75 , 0 ) / 1
              = max( −0.75 , 0 ) / 1          <-- the max() is doing work here
              = 0 / 1
              = 0

  backoff     = lambda(reading) * P_CONT(Kong)
              = 0.75 * 0.2
              = 0.15

  total       = 0 + 0.15
              = 0.15


normalisation check (slide 86)

  0.85 + 0.15 = 1.00                               correct
  discounted mass removed = d * N / C(reading) = 0.75 * 1 / 1 = 0.75
  mass handed to backoff  = lambda(reading)         = 0.75     matches

glasses beats Kong by a factor of 0.85 / 0.15 = 5.67. Exactly the behaviour the sentence demanded.

إذن glasses تتغلب على Kong بفارق مقداره 0.85 / 0.15 = 5.67 ضعفاً. وهذا بالضبط هو التصرف الذي كانت الجملة الأصلية تطالب به.

Slide 92: compare with ordinary unigram backoff

الشريحة 92: المقارنة مع التراجع العادي إلى الـ unigram

Now run the identical machinery but back off to the raw unigram instead. Taking the word counts from the same corpus, Kong has 30 tokens and glasses has 4, out of 34.

الآن شغّل الآلة نفسها حرفياً، لكن اجعل backoff يرجع إلى unigram الخام بدلاً من continuation. وبأخذ عدّات الكلمات من corpus نفسه، تكون Kong بـ 30 token وglasses بـ 4، من أصل 34.

The comparison, computedالمقارنة محسوبة

raw unigram (token counts)
  P(Kong)    = 30 / 34 = 0.8824
  P(glasses) =  4 / 34 = 0.1176

absolute discounting with the raw unigram  (slide 78)
  P_AD(glasses | reading) = 0.25 + 0.75 * 0.1176 = 0.25 + 0.0882 = 0.3382
  P_AD(Kong    | reading) = 0    + 0.75 * 0.8824 = 0    + 0.6618 = 0.6618
  check: 0.3382 + 0.6618 = 1.0000

Kneser-Ney with the continuation unigram  (slide 84)
  P_KN(glasses | reading) = 0.25 + 0.75 * 0.8 = 0.8500
  P_KN(Kong    | reading) = 0    + 0.75 * 0.2 = 0.1500
  check: 0.8500 + 0.1500 = 1.0000

Modelالنموذج	P(glasses \| reading)	P(Kong \| reading)	Verdictالحكم
Absolute discounting, raw unigramالخصم المطلق مع الـ unigram الخام	0.338	0.662	prefers `Kong`, ratio 1.96 the wrong wayيفضّل `Kong`، بنسبة 1.96 في الاتجاه الخاطئ
Interpolated Kneser-NeyKneser-Ney الاستيفائي	0.850	0.150	prefers `glasses`, ratio 5.67يفضّل `glasses`، بنسبة 5.67

يضع الجدول الطريقتين وجهاً لوجه على السياق نفسه reading. والذي يجب أن تلاحظه أن الصف الأول (absolute discounting مع unigram الخام) يفضّل Kong بنسبة 0.662 مقابل 0.338، أي يجيب إجابة خاطئة، بينما الصف الثاني (Kneser-Ney) يقلب النتيجة إلى 0.850 لـ glasses مقابل 0.150. والفرق الوحيد بين الصفّين هو التوزيع الذي رجعنا إليه، لا شيء غير ذلك.

Both models discount identically. Both reserve the same 0.75 of mass. They disagree only about who deserves it. That is the slide 92 slogan: backoff should model continuation diversity, not token frequency.

النموذجان يخصمان بالطريقة نفسها تماماً، وكلاهما يحجز الكتلة نفسها وهي 0.75. الخلاف بينهما في نقطة واحدة فقط: من يستحق هذه الكتلة. وهذا هو شعار الشريحة 92: backoff يجب أن يُمثّل تنوّع السياقات (continuation diversity)، لا تكرار tokens.

Slide 93: the sanity check with history `Hong`

الشريحة 93: اختبار المعقولية مع السياق `Hong`

If P_CONT(Kong) is only 0.2, has Kneser-Ney broken Hong Kong? No, because λ scales with how much evidence you have.

إذا كانت P_CONT(Kong) لا تساوي إلا 0.2، فهل أفسد Kneser-Ney عبارة Hong Kong نفسها؟ لا، والسبب أن λ تتناسب مع حجم الدليل المتوفر لديك: كلما قوي الدليل صغرت λ.

History = Hongالسياق = Hong

C(Hong) = 30
N(Hong) = |{w : C(Hong, w) > 0}| = |{Kong}| = 1

lambda(Hong) = ( 0.75 / 30 ) * 1 = 0.025        tiny

P_KN(Kong | Hong)
  first term = max( 30 − 0.75 , 0 ) / 30 = 29.25 / 30 = 0.9750
  backoff    = 0.025 * P_CONT(Kong) = 0.025 * 0.2     = 0.0050
  total                                               = 0.9800

P_KN(glasses | Hong)
  first term = max( 0 − 0.75 , 0 ) / 30               = 0
  backoff    = 0.025 * P_CONT(glasses) = 0.025 * 0.8  = 0.0200
  total                                               = 0.0200

check: 0.98 + 0.02 = 1.00

After Hong, 98 percent of the mass still sits on Kong. The low P_CONT(Kong) barely registers because λ(Hong) = 0.025 leaves almost nothing for the backoff to influence.

بعد Hong، تبقى 98 في المئة من الكتلة الاحتمالية على Kong. وقيمة P_CONT(Kong) المنخفضة لا يكاد يظهر لها أثر، لأن λ(Hong) = 0.025 لا تترك لـ backoff إلا شيئاً ضئيلاً جداً يؤثر فيه.

Why this mattersلماذا يهم هذا

λ(h) = d · N(h) / C(h) is self-regulating. Strong evidence means large C(h) relative to N(h), so λ shrinks and the bigram dominates. Weak evidence means C(h) close to N(h), so λ grows and the continuation model takes over. Kneser-Ney never damages a well-attested bigram.

الصيغة λ(h) = d · N(h) / C(h) تنظّم نفسها تلقائياً. فالدليل القوي يعني C(h) كبيرة بالنسبة إلى N(h)، فتصغر λ ويسيطر bigram. والدليل الضعيف يعني C(h) قريبة من N(h)، فتكبر λ ويتولى نموذج continuation القيادة. ولهذا فإن Kneser-Ney لا يضرّ أبداً بـ bigram مدعوم بأدلة كثيرة.

Historyالسياق (History)	C(h)	N(h)	λ(h)	Who decidesمن يقرر
`reading`	1	1	0.750	mostly the continuation modelغالباً نموذج الاستمرار
`Hong`	30	1	0.025	almost entirely the bigramالـ bigram بشكل شبه كامل

يبيّن الجدول كيف تتصرف λ(h) مع سياقين مختلفين. السياقان لهما N(h) = 1 نفسه، لكن C(h) يختلف: 1 مقابل 30. والنتيجة أن λ تهبط من 0.750 إلى 0.025، أي ثلاثون ضعفاً. وهذا هو العمود الأخير: مع reading يقرّر نموذج continuation تقريباً، ومع Hong يقرّر bigram وحده. C(h) في المقام هو مقياس قوة الدليل.

Slide errata in this range

أخطاء الشرائح في هذا النطاق

Typesetting errors, do not be thrownأخطاء طباعية، لا تدعها تربكك

Slide 83 title. It prints "Continuation probability Pextcont". That is a LaTeX accident: P_{\text{cont}} lost its backslash so the word "text" leaked into the output minus its first letter. The intended symbol is P_CONT. The formula body on that slide is correct.

عنوان الشريحة 83. هو مطبوع هكذا: "Continuation probability Pextcont". وهذا مجرد خطأ في LaTeX: فالأمر P_{\text{cont}} فقد الشرطة المائلة الخاصة به، فتسربت كلمة "text" إلى المخرجات ناقصةً حرفها الأول. والرمز المقصود هو P_CONT. أما جسم المعادلة في تلك الشريحة فهو صحيح.

Slides 82 and 83 write C(vw). That is not v times w. It is the bigram count C(v, w), meaning "number of times v was immediately followed by w". The deck uses both spellings interchangeably.

الشريحتان 82 و83 تكتبان C(vw). هذا ليس v مضروباً في w. هو عدّ bigram أي C(v, w)، ومعناه "عدد المرات التي جاءت فيها w مباشرة بعد v". والعرض يستخدم الكتابتين بالتبادل وبالمعنى نفسه.

Slide 83 denominator variables. The numerator uses (v, w) but the denominator writes |{(u, w′) : C(u w′) > 0}|. The primed variables are fresh bound variables, deliberately unrelated to the w in the numerator. The denominator ranges over all bigram types in the corpus, not just the ones ending in w. If you read w′ as "the same w" you will get nonsense.

متغيّرات مقام الشريحة 83. البسط يستخدم (v, w) لكن المقام يكتب |{(u, w′) : C(u w′) > 0}|. المتغيّرات التي عليها علامة تنصيص هي متغيّرات مقيّدة جديدة، لا علاقة لها بتاً بـ w الموجودة في البسط. فالمقام يمرّ على كل أنواع bigram في corpus، لا على المنتهية بـ w فقط. وإذا قرأت w′ على أنها "نفس w" فستخرج بنتيجة لا معنى لها، ويصبح المقام هو البسط نفسه.

Slides 84 and 85 use C(w_i−1) where the textbook writes Σ_v C(w_i−1 v). These are equal by slide 17, except for the single corpus-final token that has no successor. Either form earns full marks. Write whichever you remember, but be consistent between the two terms.

الشريحتان 84 و85 تستخدمان C(w_i−1) في الموضع الذي يكتب فيه الكتاب Σ_v C(w_i−1 v). الصيغتان متساويتان بحكم الشريحة 17، باستثناء token واحد في آخر corpus لا يوجد بعده كلمة. وأي من الصيغتين يأخذ الدرجة كاملة، فاكتب ما تتذكره، لكن التزم بالصيغة نفسها في الحدّين ولا تخلط بينهما.

Slide 89 title reads "Step 2: compute (λ)" with stray parentheses. Nothing is missing.

عنوان الشريحة 89 مكتوب "Step 2: compute (λ)" بأقواس زائدة لا داعي لها. لا شيء ناقص في الشريحة.

What you must be able to do cold

ما يجب أن تستطيع فعله دون تحضير

Say the motivation in one sentence: the lower-order model should estimate how likely a word is as a novel continuation, not how frequent it is.
قل الدافع في جملة واحدة: النموذج ذو الرتبة الأدنى يجب أن يقدّر مدى احتمال أن تكون الكلمة استمراراً جديداً (novel continuation)، لا مدى تكرارها.
Compute a continuation count from a bigram list by deduplicating preceding words.
احسب عدّ الاستمرار من قائمة bigrams بإزالة تكرار الكلمات السابقة.
Compute P_CONT with the bigram type total in the denominator.
احسب P_CONT ومجموع أنواع الـ bigrams في المقام.
Write the bigram P_KN formula with the max(·, 0) intact.
اكتب صيغة P_KN للـ bigram مع إبقاء max(·, 0) كما هي.
Compute λ(h) from d, C(h) and N(h), and justify it as the discounted mass.
احسب λ(h) من d وC(h) وN(h)، وبرّرها بأنها الكتلة المخصومة.
Verify that your probabilities over a fixed history sum to 1.
تحقق من أن مجموع احتمالاتك على سياق ثابت يساوي 1.

Check yourself

اختبر نفسك

In the toy corpus of slide 87, what is the denominator of P_CONT?

في الـ corpus التجريبي في الشريحة 87، ما مقام P_CONT؟

C. The denominator is |{(u, v) : C(u, v) > 0}|, the number of distinct bigram types, which slide 87 states is 5. A is the single most common error: 30 + 1 + 1 + 1 + 1 = 34 counts tokens, and using it would make P(Kong) = 1/34 and P(glasses) = 4/34, which no longer sum to 1 and quietly reintroduces token frequency through the back door. D confuses the vocabulary of continuations with the number of bigram types.

الجواب C. المقام هو |{(u, v) : C(u, v) > 0}|، أي عدد أنواع الـ bigrams المختلفة، والشريحة 87 تذكر أنه 5. والخيار A هو أشيع خطأ على الإطلاق: 30 + 1 + 1 + 1 + 1 = 34 يعدّ الـ tokens، واستخدامه يجعل P(Kong) = 1/34 وP(glasses) = 4/34، ومجموعهما لم يعد 1، ويعيد تكرار الـ tokens بهدوء من الباب الخلفي. والخيار D يخلط بين مفردات الاستمرارات وعدد أنواع الـ bigrams.

C(Hong Kong) = 30. What does this contribute to the continuation count of Kong?

C(Hong Kong) = 30. بكم يساهم هذا في عدّ الاستمرار لـ Kong؟

B. The continuation count is a count of distinct preceding types, so all 30 occurrences of the same bigram type collapse to a single context. A is the entire error Kneser-Ney was designed to fix. D invents a rule: nothing is excluded, the phrase simply only counts once.

الجواب B. عدّ الاستمرار هو عدد الأنواع المختلفة السابقة، فكل الظهورات الـ 30 لنوع الـ bigram نفسه تنضغط في سياق واحد. والخيار A هو بالضبط الخطأ الذي صُمم Kneser-Ney لإصلاحه. والخيار D يخترع قاعدة: لا شيء يُستبعد، والعبارة ببساطة تُعدّ مرة واحدة.

Which statement about λ(w_i−1) in Kneser-Ney is correct?

أي عبارة عن λ(w_i−1) في Kneser-Ney صحيحة؟

A. λ(h) = (d / C(h)) · N(h) is fully determined by the counts for that specific history. B is the trap: linear interpolation on slide 68 does tune its λs on a dev set, but in Kneser-Ney only d is free. C is stupid backoff's λ ≈ 0.4 from slide 73, a different method entirely. D forgets the division by C(h) and the multiplication by N(h): in the toy example λ(reading) happens to equal 0.75 = d only because C(reading) = N(reading) = 1, while λ(Hong) = 0.025.

الجواب A. λ(h) = (d / C(h)) · N(h) تحددها بالكامل عدّات ذلك السياق بعينه. والخيار B هو الفخ: الاستيفاء الخطي في الشريحة 68 يضبط قيم λ على dev set فعلاً، لكن في Kneser-Ney وحده d حر. والخيار C هو λ ≈ 0.4 الخاصة بـ stupid backoff من الشريحة 73، وهي طريقة مختلفة تماماً. والخيار D ينسى القسمة على C(h) والضرب في N(h): في المثال التجريبي تصادف أن λ(reading) تساوي 0.75 = d فقط لأن C(reading) = N(reading) = 1، بينما λ(Hong) = 0.025.

With d = 0.75, C(reading) = 1, C(reading glasses) = 1 and P_CONT(glasses) = 0.8, what is P_KN(glasses | reading)?

إذا كان d = 0.75، وC(reading) = 1، وC(reading glasses) = 1، وP_CONT(glasses) = 0.8، فما قيمة P_KN(glasses | reading)؟

D. max(1 − 0.75, 0)/1 = 0.25, plus λ(reading)·P_CONT(glasses) = 0.75 × 0.8 = 0.60, giving 0.85. A stops after the discounted term and forgets that interpolated Kneser-Ney always adds the backoff. B keeps only the backoff term. C comes from using the undiscounted count 1/1 = 1 in the first term and then adding 0.05, or from forgetting to discount at all, and should alarm you immediately since it exceeds 1.

الجواب D. max(1 − 0.75, 0)/1 = 0.25، زائد λ(reading)·P_CONT(glasses) = 0.75 × 0.8 = 0.60، فالناتج 0.85. والخيار A يتوقف بعد الحد المخصوم وينسى أن Kneser-Ney الاستيفائي يضيف حد التراجع دائماً. والخيار B يُبقي حد التراجع فقط. والخيار C يأتي من استخدام العدّ غير المخصوم 1/1 = 1 في الحد الأول ثم إضافة 0.05، أو من نسيان الخصم كلياً، ويجب أن ينبهك فوراً لأنه يتجاوز 1.

C(reading Kong) = 0. Why must the first term of P_KN(Kong | reading) be written with max(·, 0)?

C(reading Kong) = 0. لماذا يجب كتابة الحد الأول من P_KN(Kong | reading) مع max(·, 0)؟

B. The numerator C − d goes negative for every unseen bigram, and max(·, 0) floors it. A is wrong: the denominator is C(reading) = 1, which is fine. C has the symptom backwards: the normalisation proof actually depends on unseen bigrams contributing exactly 0, so removing max() breaks both validity and the sum. D is wrong because unseen bigrams are not dropped: they are precisely the case the formula must handle, and their entire probability comes from the backoff term.

الجواب B. البسط C − d يصبح سالباً لكل bigram غير مرئي، وmax(·, 0) ترفعه إلى الصفر. والخيار A خاطئ: المقام C(reading) = 1 ولا مشكلة فيه. والخيار C يعكس العَرَض: برهان التطبيع يعتمد فعلاً على أن تساهم الـ bigrams غير المرئية بـ 0 بالضبط، فحذف max() يكسر الصحة والمجموع معاً. والخيار D خاطئ لأن الـ bigrams غير المرئية لا تُحذف: هي بالضبط الحالة التي يجب أن تعالجها الصيغة، واحتمالها كله يأتي من حد التراجع.

P_CONT(Kong) = 0.2 is low. Why does Kneser-Ney still assign P_KN(Kong | Hong) = 0.98?

P_CONT(Kong) = 0.2 منخفض. فلماذا يعطي Kneser-Ney مع ذلك P_KN(Kong | Hong) = 0.98؟

C. λ(h) = d·N(h)/C(h) shrinks as the history gets more frequent, so with C(Hong) = 30 and one continuation type only 2.5 percent of the mass is exposed to the backoff distribution: 0.975 + 0.025 × 0.2 = 0.98. A and B invent exceptions that the formula does not contain, and the formula is applied identically for every history. D is wrong because P_CONT is a single global distribution that never depends on the current history, which is exactly why it is called the lower-order model.

الجواب C. λ(h) = d·N(h)/C(h) تصغر كلما زاد تكرار السياق، فمع C(Hong) = 30 ونوع استمرار واحد لا يتعرض لتوزيع التراجع إلا 2.5 بالمئة من الكتلة: 0.975 + 0.025 × 0.2 = 0.98. والخياران A وB يخترعان استثناءات لا تحتويها الصيغة، والصيغة تُطبَّق بالطريقة نفسها على كل سياق. والخيار D خاطئ لأن P_CONT توزيع عام واحد لا يعتمد أبداً على السياق الحالي، ولهذا تحديداً يُسمى النموذج ذا الرتبة الأدنى.