The recursive form

الصيغة التكرارية (recursive)

Slide 94. Same shape as the bigram formula, written for arbitrary order.

الشريحة 94. الشكل نفسه الذي رأيته في صيغة bigram، لكن مكتوباً لأي رتبة.

اقرأ الصيغة في جزئين. الجزء الأول كسر: بسطه max(c_KN(w_i−n+1:i) − d, 0)، أي عدّاد الـ n-gram كاملاً بعد خصم d منه مع منع السالب، ومقامه Σ_v c_KN(w_{i−n+1:i−1} v)، أي مجموع العدّادات على كل كلمة v يمكن أن تتبع السياق. الجزء الثاني هو λ للسياق مضروباً في الصيغة نفسها برتبة أقل. ترتيب الحساب: ابدأ من أعلى رتبة، وكل مرة اسقط الكلمة الأقصى يساراً من السياق، ونزّل حتى تصل للأرضية.

Three things changed from the bigram case, and nothing else:

ثلاثة أمور فقط تغيّرت عن حالة bigram، ولا شيء غيرها:

• The history wi−1 became a whole context wi−n+1:i−1.

  التاريخ wi−1 صار سياقاً كاملاً wi−n+1:i−1.

• The thing you back off to is no longer PCONT directly. It is the same formula one order down, with the leftmost history word dropped (wi−n+2:i−1). That is the recursion.

  ما ترتدّ إليه (back off) لم يعد PCONT مباشرة، بل الصيغة نفسها برتبة أقل بواحد، بعد إسقاط أقصى كلمة يساراً من التاريخ (wi−n+2:i−1). هذا هو التكرار (recursion).

• Counts are written cKN, not C. That subscript is the entire content of slide 95.

  العدّادات تُكتب cKN وليست C. هذا الحرف السفلي وحده هو كل مضمون الشريحة 95.

The one thing on this page you cannot get wrong

الشيء الوحيد في هذه الصفحة الذي لا يجوز أن تخطئ فيه

Slide 95 defines cKN as a two-case function:

تعرّف الشريحة 95 الرمز cKN كدالة بحالتين:

سطران فقط: في أعلى رتبة (highest) يكون c_KN هو count(·)، أي العدّ الخام العادي. وفي كل الرتب الأدنى (lower) يكون continuationcount(·)، أي عدد الأنواع المختلفة التي تسبق المعامل.

So the symbol cKN changes meaning as the recursion descends. At the top of the ladder it is an ordinary token count. One step down and all the way to the bottom it is a count of distinct preceding word types.

إذن الرمز cKN يتغير معناه كلما نزل التكرار. في أعلى السلّم هو عدّ عادي للـ tokens، ومن الدرجة التي تحته وحتى الأسفل هو عدّ لأنواع الكلمات المختلفة التي تسبقه.

يرسم المخطط سلّماً من أربع درجات لنموذج trigram. الدرجة العليا (trigram) تستخدم c_KN = count( ) أي العدّ الخام. الدرجتان تحتها (bigram ثم unigram) تستخدمان continuationcount( )، ومستوى unigram هو P_CONT نفسه بثوب آخر. والدرجة الأخيرة هي الأرضية المنتظمة 1 / V بلا أي عدّادات. والأسهم بينها هي ضرب في lambda للسياق. الخلاصة أسفل الرسم: العدّ الخام يظهر على درجة واحدة فقط، وهي القمة.

Which count at which level

أي عدّ في أي مستوى

Read this table as "I am training a trigram Kneser-Ney model". The highest order is a property of the model you chose, not of the formula.

اقرأ الجدول بافتراض أنك تدرّب نموذج trigram Kneser-Ney. فـ أعلى رتبة صفة للنموذج الذي اخترته، لا للصيغة نفسها.

يقول الجدول: على مستوى Trigram يكون c_KN هو count، أي كم مرة ورد ذلك الـ trigram. على مستوى Bigram يكون continuationcount، أي كم كلمة مختلفة v أنتجت v w_i−1 w_i. على مستوى Unigram هو عدد الكلمات المختلفة التي تسبق w_i. وعلى مستوى Floor لا عدّادات أصلاً، بل 1/V.

Now the same table for a bigram model, to show that the labels move:

والآن الجدول نفسه لنموذج bigram، ليبيّن أن التسميات تتحرك:

في نموذج bigram انتقلت التسمية درجة واحدة لأعلى: مستوى Bigram صار هو أعلى رتبة فيستخدم count الخام، ومستوى Unigram يستخدم continuationcount، ولهذا بالضبط ترتدّ الشريحة 84 إلى P_CONT.

Raw count versus continuation count at a lower level, with numbers

العدّ الخام مقابل عدّ الاستمرار في مستوى أدنى، بالأرقام

A trigram model, d = 0.75, and these are the only occurrences of the bigram reading glasses in training:

نموذج trigram، وd = 0.75، وهذه هي كل مواضع ظهور الـ bigram reading glasses في بيانات التدريب:

trigram types containing "reading glasses"
  the reading glasses   x 2
  my  reading glasses   x 1
  his reading glasses   x 1

raw bigram count            C(reading glasses) = 2 + 1 + 1 = 4
continuation count     c_KN(reading glasses) = |{the, my, his}| = 3

"reading" is followed only by "glasses", so at the bigram level
  Sum_v c_KN(reading v) = c_KN(reading glasses) = 3
  N(reading) = |{w : c_KN(reading w) > 0}| = 1


CORRECT, bigram level of a trigram model, using c_KN = 3
  discounted term = max(3 − 0.75, 0) / 3 = 2.25 / 3   = 0.7500
  lambda(reading) = (0.75 / 3) * 1      = 0.25        = 0.2500
  check            0.7500 + 0.2500                    = 1.0000

WRONG, same level but using the raw count 4
  discounted term = max(4 − 0.75, 0) / 4 = 3.25 / 4   = 0.8125
  lambda(reading) = (0.75 / 4) * 1                    = 0.1875
  check            0.8125 + 0.1875                    = 1.0000

Where the recursion stops

أين يتوقف التكرار

Slide 96. The unigram level does not back off to another n-gram. It backs off to a uniform distribution over the vocabulary.

الشريحة 96. مستوى unigram لا يرتدّ إلى n-gram آخر، بل يرتدّ إلى توزيع منتظم على كل الـ vocabulary.

هذه صيغة آخر درجة. الكسر الأول بسطه max(c_KN(w) − d, 0)، أي continuation count للكلمة بعد خصم d، ومقامه Σ_w′ c_KN(w′)، أي مجموع هذه العدّادات على كل كلمات vocabulary. ثم يُضاف λ(ε) مضروباً في 1/V، وε هي التاريخ الفارغ. لا يوجد نداء تكراري بعد هذا السطر، فهنا يتوقف النزول.

• ε is the empty string, that is, the empty history. Slide 96 writes it as λ() with nothing inside, which is the same thing.

  ε هي السلسلة الفارغة، أي التاريخ الفارغ. وتكتبها الشريحة 96 على صورة λ() بلا شيء داخلها، وهما الشيء نفسه.

• Because 1/V > 0 and λ(ε) > 0, no word can ever receive probability zero. The whole point of smoothing is discharged at this last rung.

  بما أن 1/V > 0 وλ(ε) > 0، فإنه لا يمكن لأي كلمة أن تحصل على احتمال صفر. كل الغرض من smoothing يتحقق عند هذه الدرجة الأخيرة.

• <UNK> needs no special treatment. Include it as an ordinary vocabulary item with count 0, and it inherits λ(ε)/V.

  <UNK> لا يحتاج معالجة خاصة. أدرجه كعنصر عادي في vocabulary بعدّاد صفر، فيأخذ تلقائياً λ(ε)/V.

Why modified Kneser-Ney exists

لماذا وُجد Kneser-Ney المعدَّل

Slide 97. A single discount d for every count is a simplification. The Church and Gale evidence on slide 77 showed held-out counts sitting near c − 0.75 for c = 2 to 9, but the row for c = 1 was 0.448, which is 1 − 0.552, not 1 − 0.75. Counts of 1, counts of 2, and counts of 3 or more behave differently.

الشريحة 97. استخدام discount واحد d لكل العدّادات تبسيط. فبيانات Church and Gale في الشريحة 77 أظهرت أن عدّادات held-out تقع قريباً من c − 0.75 للقيم c = 2 إلى 9، لكن صف c = 1 كان 0.448، أي 1 − 0.552 لا 1 − 0.75. فعدّاد 1 وعدّاد 2 وعدّاد 3 أو أكثر تتصرف بطرق مختلفة.

Modified Kneser-Ney, slide 98

Modified Kneser-Ney، الشريحة 98

Chen and Goodman's fix: keep the Kneser-Ney structure exactly as it is, and use three discounts instead of one.

حلّ Chen and Goodman: أبقِ بنية Kneser-Ney كما هي تماماً، واستخدم ثلاثة discounts بدل واحد.

يربط الجدول كل عدّاد بالـ discount الخاص به: العدّاد 1 يأخذ d₁ لأن الـ singletons أكثرها ضجيجاً وأكثرها تقلّصاً في بيانات held-out، والعدّاد 2 يأخذ d₂ فهو ما زال فيه ضجيج لكن أقل، والعدّاد 3 أو أكثر يأخذ d₃₊ لأنه موثّق جيداً ويكفيه خصم شبه ثابت.

• Nothing else changes: still discount plus interpolation, still cKN with the same two-case definition, still a uniform floor.

  لا شيء آخر يتغير: ما زال discount مع interpolation، وما زال cKN بتعريفه ذي الحالتين نفسه، وما زالت الأرضية المنتظمة موجودة.

• λ gets more bookkeeping, since the mass reserved per history now depends on how many continuations had count 1, count 2, and count 3 or more.

  يزيد العمل الحسابي في λ، لأن الكتلة المحجوزة لكل تاريخ تعتمد الآن على عدد الـ continuations التي عدّادها 1، وعدّادها 2، وعدّادها 3 أو أكثر.

• It is the best-performing classic method and the standard baseline. Shipped in KenLM and SRILM.

  هي أفضل الطرق الكلاسيكية أداءً وخط الأساس القياسي، ومُضمّنة في KenLM وSRILM.

Practical notes

ملاحظات عملية

Slide 99, three bullets worth one sentence each.

الشريحة 99، ثلاث نقاط كل واحدة تستحق جملة واحدة.

1. Kneser-Ney is the strongest classic n-gram smoothing method on many benchmarks.

   Kneser-Ney هي أقوى طرق smoothing الكلاسيكية للـ n-gram في كثير من المعايير.

2. It helps most for higher-order n-grams with sparse counts, which is exactly where raw MLE collapses.

   أكبر فائدتها تكون في الـ n-grams ذات الرتب العالية وعدّاداتها المتناثرة، وهو بالضبط الموضع الذي ينهار فيه MLE الخام.

3. Smoothing parameters, d included, are tuned on dev or held-out data. Never on the test set, per slide 70.

   معاملات smoothing، ومنها d، تُضبط على بيانات dev أو held-out، ولا تُضبط أبداً على test set، حسب الشريحة 70.

Bridge to neural language models

الجسر إلى النماذج اللغوية العصبية

Slide 100 is the last content slide before entropy, and it explains why the course moves on.

الشريحة 100 هي آخر شريحة محتوى قبل entropy، وهي تشرح سبب انتقال المقرر إلى ما بعدها.