MLE is two words: count and normalize

الـ MLE كلمتان: عُدّ ثم طبّع

Slide 16 gives the whole method in two bullets: estimate probabilities from relative frequency counts, and normalize so they sum to 1. Then the formula:

تختصر الشريحة 16 الطريقة كلها في نقطتين: قدّر الاحتمالات من relative frequency counts، ثم طبّق normalization حتى يصبح مجموعها 1. وبعدها تأتي الصيغة:

P(w_n | w_n−1) = C(w_n−1, w_n)C(w_n−1)

In words: how many times did the pair appear, divided by how many times the first word appeared. "Maximum likelihood" sounds like it needs calculus. It does not. For this model the maximum-likelihood estimate is exactly the relative frequency, so the recipe is: count, divide, done.

بالكلمات: كم مرة ظهر الزوج معاً، مقسوماً على كم مرة ظهرت الكلمة الأولى. مصطلح "maximum likelihood" يوحي بأنك تحتاج تفاضلاً وتكاملاً، وهذا غير صحيح هنا. في هذا النموذج تحديداً يكون تقدير maximum likelihood مساوياً تماماً لـ relative frequency، فتصبح الوصفة: عُدّ، اقسم، انتهى.

Why the denominator is C(w_n−1)

لماذا المقام هو C(w_n−1)

Slide 17 exists only to answer this, because getting the denominator wrong is the most common arithmetic error in the whole lecture. The argument is three lines:

الشريحة 17 موجودة فقط للإجابة على هذا السؤال، لأن الخطأ في المقام هو أشهر خطأ حسابي في المحاضرة كلها. والبرهان ثلاثة أسطر:

1. Every time the word w_n−1 occurs, something follows it. Some word w comes next, even if that word is </s>.

   في كل مرة تظهر الكلمة w_n−1 يأتي بعدها شيء ما بالضرورة. هناك كلمة w تتبعها، ولو كانت تلك الكلمة هي </s> نفسها.

2. So if you add up the counts of every bigram that starts with w_n−1, you get back the number of times w_n−1 occurred: Σ_w C(w_n−1, w) = C(w_n−1).

   إذن لو جمعت counts كل bigram يبدأ بـ w_n−1، يرجع لك عدد مرات ظهور w_n−1 نفسه: Σ_w C(w_n−1, w) = C(w_n−1).

3. Therefore dividing every such bigram count by C(w_n−1) makes the numbers sum to exactly 1. The conditional distribution is normalized.

   وبالتالي فإن قسمة كل bigram count من هذه على C(w_n−1) تجعل مجموع الأرقام يساوي 1 بالضبط، أي أن conditional distribution صار موزوناً بشكل صحيح (normalized).

Put differently: C(w_n−1) is the row total. Lay the bigram counts out as a matrix with the context word as the row and the next word as the column. Dividing a row by its own total is what turns counts into a probability distribution over the next word.

بصيغة أخرى: C(w_n−1) هو مجموع الصف. ارسم bigram counts على شكل مصفوفة، فيها كلمة السياق هي الصف والكلمة التالية هي العمود. قسمة الصف على مجموعه الخاص هي بالضبط ما يحوّل counts إلى probability distribution على الكلمة التالية.

bigram  : C(I am)       / C(I)
trigram : C(I am Sam)   / C(I am)
4-gram  : C(do not like green) / C(do not like)

The toy corpus walkthrough

شرح الـ corpus الصغير خطوة بخطوة

Slide 18 gives a three-sentence corpus with boundary symbols already attached:

تعطي الشريحة 18 corpus من ثلاث جمل، مع رموز الحدود (boundary symbols) مضافة مسبقاً:

<s> I am Sam </s>
<s> Sam I am </s>
<s> I do not like green eggs and ham </s>

Step 1: unigram counts

الخطوة 1: عدّات unigram

Count every token, boundary symbols included. Three sentences, so three of each boundary symbol.

عُدّ كل token، بما في ذلك رموز الحدود. ثلاث جمل، إذن ثلاث نسخ من كل رمز حدّ.

يعرض هذا الجدول unigram counts لكل token في corpus الصغير، مع ذكر الجمل التي ظهر فيها. ما يجب أن تلاحظه: رمزا الحدود لهما count يساوي 3 لأن عدد الجمل ثلاث، وI هي الكلمة الوحيدة التي ظهرت في الجمل الثلاث كلها فصار count لها 3، أما am وSam فكل منهما 2 فقط، وكلمات الجملة الثالثة كلها 1. هذه الأرقام هي المقامات التي ستستخدمها لاحقاً، فثبّتها جيداً.

Step 2: the bigram count matrix

الخطوة 2: مصفوفة عدّات bigram

Row = context word, column = next word. The cell is the count of the column word following the row word. Notice the row totals.

الصف = كلمة السياق، والعمود = الكلمة التالية. والخلية هي count ظهور كلمة العمود بعد كلمة الصف. انتبه جيداً لمجاميع الصفوف.

هذه مصفوفة bigram counts لـ corpus الصغير: كل خلية هي عدد مرات ظهور كلمة العمود مباشرة بعد كلمة الصف، والعمود الأخير هو مجموع الصف. أهم ملاحظتان: أولاً، معظم الخلايا أصفار حتى في corpus بثلاث جمل فقط، وهذه بداية مشكلة sparsity. وثانياً، مجموع كل صف يساوي بالضبط unigram count لكلمة ذلك الصف، وهو المقام الذي ستقسم عليه.

The right-hand column is slide 17's claim made concrete: each row sums to the unigram count of the row word. Row <s> sums to 3 = C(<s>). Row am sums to 2 = C(am). That is why the row total is always the correct denominator.

العمود الأيمن هو ما تقوله الشريحة 17 مجسّداً بالأرقام: مجموع كل صف يساوي unigram count لكلمة الصف. صف <s> مجموعه 3 = C(<s>)، وصف am مجموعه 2 = C(am). ولهذا فإن مجموع الصف هو المقام الصحيح دائماً.

P(I | <s>)
  numerator   C(<s> I)  = 2    sentences 1 and 3 start with I
  denominator C(<s>)    = 3    three sentences
  = 2 / 3 = 0.667

P(Sam | <s>)
  numerator   C(<s> Sam) = 1   only sentence 2 starts with Sam
  denominator C(<s>)     = 3
  = 1 / 3 = 0.333

P(am | I)
  numerator   C(I am) = 2       "I am" in sentence 1, "I am" in sentence 2
  denominator C(I)    = 3       I occurs three times
  = 2 / 3 = 0.667

P(do | I)
  numerator   C(I do) = 1       "I do" in sentence 3
  denominator C(I)    = 3
  = 1 / 3 = 0.333

P(</s> | Sam)
  numerator   C(Sam </s>) = 1  sentence 1 ends "am Sam </s>"
  denominator C(Sam)       = 2  Sam occurs twice
  = 1 / 2 = 0.5

The general n-gram formula, subscripts decoded

صيغة n-gram العامة، مع فك رموز المؤشرات السفلية

Slide 20 generalizes from bigrams to any order:

تعمّم الشريحة 20 الصيغة من bigram إلى أي order:

P(w_n | w_{n−N+1:n−1}) = C(w_n−N+1:n)C(w_{n−N+1:n−1})

The slide's own gloss: "prefix in denominator, full n-gram in numerator". The subscripts look worse than they are. There are only two of them and they differ by one character:

وشرح الشريحة نفسه: "prefix in denominator, full n-gram in numerator"، أي prefix في المقام وn-gram الكامل في البسط. الرموز السفلية تبدو أصعب مما هي عليه: هي اثنان فقط، والفرق بينهما حرف واحد.

So the only difference between top and bottom is the right endpoint: n on top, n - 1 on the bottom. That is the "chop the last word" mnemonic written in index notation.

إذن الفرق الوحيد بين البسط والمقام هو نقطة النهاية اليمنى: n في البسط، وn - 1 في المقام. وهذه هي قاعدة "اقطع الكلمة الأخيرة" نفسها مكتوبة بصيغة الفهارس.

Worked subscript table

جدول محلول للمؤشرات السفلية

Take the sentence I want to eat food and predict the word eat. Index the tokens first, because n is a position, not an order.

خُذ الجملة I want to eat food واطلب توقّع الكلمة eat. رقّم الـ tokens أولاً، لأن n هي موضع في الجملة وليست order النموذج.

I(1)  want(2)  to(3)  eat(4)  food(5)

the word being predicted is  eat , so  n = 4 ,  w  = eat
                                                  n

Now vary the order N and read the subscripts off directly.

الآن غيّر order أي N، واقرأ الرموز السفلية مباشرة.

يفكّ هذا الجدول الرموز السفلية لثلاث قيم من N مع تثبيت n = 4 أي الكلمة eat: لكل صف ترى فهارس السياق وكلماته (المقام)، وفهارس n-gram الكامل وكلماته (البسط)، ثم تقدير MLE النهائي. ما يجب أن تلاحظه: البسط ينتهي عند eat في كل صف، والمقام ينتهي عند to في كل صف، والشيء الوحيد المتحرك هو الحد الأيسر للنافذة الذي يرتدّ إلى الخلف كلما زاد N. ولاحظ أيضاً أن طول المقام دائماً N - 1 كلمة، فـ trigram يشترط على كلمتين فقط.

Arithmetic for the start index, since that is the part people fumble. With n = 4: for N = 2 the start is 4 - 2 + 1 = 3, for N = 3 it is 4 - 3 + 1 = 2, for N = 4 it is 4 - 4 + 1 = 1. Bigger order means the window reaches further back, exactly as it should.

حساب فهرس البداية، لأنه الموضع الذي يتعثر فيه الطلاب. عند n = 4: إذا كان N = 2 فالبداية 4 - 2 + 1 = 3، وإذا كان N = 3 فهي 4 - 3 + 1 = 2، وإذا كان N = 4 فهي 4 - 4 + 1 = 1. أي أن order الأكبر يجعل النافذة تمتد إلى الخلف أكثر، وهذا هو المنطقي تماماً.

Note what never changes: the numerator always ends at eat, and the denominator always ends one word earlier at to. Only the left edge of the window moves.

ولاحظ ما لا يتغير أبداً: البسط ينتهي دائماً عند eat، والمقام ينتهي دائماً بكلمة واحدة قبلها عند to. الحد الأيسر للنافذة هو وحده الذي يتحرك.

Scaling up: the Berkeley Restaurant corpus

التوسع: corpus مطعم بيركلي (Berkeley Restaurant)

Slide 21 switches from the toy corpus to real data so that sparsity becomes visible. The three numbers from the slide:

تنتقل الشريحة 21 من corpus الصغير إلى بيانات حقيقية حتى تصبح مشكلة sparsity مرئية. والأرقام الثلاثة من الشريحة:

V x V = 1446 x 1446 = 2,090,916 possible bigrams

tokens available to fill them:
9332 sentences, roughly a handful of words each,
so on the order of 10^5 bigram tokens observed

2,090,916 cells  vs  ~10^5 observations
=> the overwhelming majority of cells must be 0

One real division from that corpus

قسمة حقيقية واحدة من ذلك الـ corpus

To see the method on real numbers, here is one bigram from the Berkeley Restaurant counts, using the same two-step recipe. The textbook reports C(to eat) = 686 and C(to) = 2417.

لترى الطريقة على أرقام حقيقية، هذا bigram واحد من counts مجموعة Berkeley Restaurant، بنفس الوصفة ذات الخطوتين. الكتاب يذكر أن C(to eat) = 686 وC(to) = 2417.

P(eat | to)
  = C(to eat) / C(to)
  = 686 / 2417
  = 0.2838...
  ~ 0.28

Same formula, same mnemonic. to is after the bar, so C(to) is on the bottom. Chop eat off to eat and you get to. The next page builds the full matrix.

نفس الصيغة ونفس القاعدة. كلمة to هي التي بعد الشرطة، فيكون C(to) في المقام. واقطع eat من to eat فينتج لك to. والصفحة التالية تبني المصفوفة الكاملة.