The corpus behind the tables

الـ corpus الذي تقوم عليه الجداول

Berkeley Restaurant Project (BERP) is a real spoken-dialog corpus of restaurant queries.

Berkeley Restaurant Project (BERP) هو corpus حقيقي من حوار منطوق، محتواه استفسارات عن المطاعم.

• 9332 user queries.

  9332 استفساراً من المستخدمين.

• Vocabulary V ≈ 1446 word types after normalization.

  حجم vocabulary: V ≈ 1446 من الـ word types بعد التطبيع.

• The bigram table is therefore 1446 × 1446. Almost every cell is zero.

  إذن جدول الـ bigram حجمه 1446 × 1446، وتكاد كل خلية فيه تكون صفراً.

The slides print an 8 × 8 excerpt for the words i, want, to, eat, chinese, food, lunch, spend. Everything on this page is that excerpt, so stay aware of what it leaves out.

تطبع الشرائح مقتطفاً بحجم 8 × 8 للكلمات i، want، to، eat، chinese، food، lunch، spend. كل ما في هذه الصفحة هو ذلك المقتطف، فابقَ واعياً لما لا يظهر فيه.

How to read the bigram counts matrix

كيف تقرأ مصفوفة عدّات bigram

One rule, and it is the whole skill:

قاعدة واحدة، وهي كل المهارة المطلوبة:

تقول الصيغة إن الخلية الواقعة عند row = w₁ وcol = w₂ تساوي C(w₁ w₂)، أي عدّة الـ bigram. الصف هو الكلمة الأولى (السياق)، والعمود هو الكلمة الثانية (المتنبَّأ بها). اقرأ دائماً من الصف إلى العمود بهذا الترتيب.

يوضّح الرسم عملية البحث في الشبكة. الشريط الأفقي الملوّن هو الصف want، أي الكلمة الأولى، والشريط العمودي هو العمود to، أي الكلمة الثانية، وتقاطعهما هو الخلية 608. وفي الأسفل: C(want to) = 608 لكن C(to want) = 0. إذن المصفوفة ليست متناظرة، فتبديل الصف بالعمود يغيّر الرقم.

The excerpt, in full

المقتطف كاملاً

Rows are the first word. Columns are the second word. Zeros are in red.

الصفوف هي الكلمة الأولى، والأعمدة هي الكلمة الثانية، والأصفار بالأحمر.

هذا هو جدول عدّات الـ bigram كاملاً. طريقة قراءته: الصف هو الكلمة الأولى في الـ bigram، والعمود هو الكلمة الثانية، والخلية عند تقاطعهما هي C(w₁ w₂). فمثلاً الصف want مع العمود to يعطي 608، أما الصف to مع العمود want فيعطي 0. وعند التطبيع إلى احتمال، المقام هو عدّة الـ unigram لكلمة الصف، أي C(w₁)، وليس مجموع الصف ولا أي شيء من العمود. هذه النقطة هي أكثر ما يُفقد الطلاب الدرجة في هذا السؤال.

32 of these 64 cells are already zero, and this is the densest corner of the matrix because these are the 8 most common words in the corpus.

32 من هذه الـ 64 خلية أصفار بالفعل، وهذه هي أكثف زاوية في المصفوفة كلها، لأن هذه الكلمات الثماني هي الأشيع في الـ corpus.

Comparison: the same two words, both orders

مقارنة: الكلمتان نفسهما، بالترتيبين

يأخذ الجدول ثلاثة أزواج ويقلب ترتيبها ليبرز عدم التناظر: want to = 608 مقابل to want = 0، وto spend = 211 مقابل spend to = 1، وfood i = 15 مقابل i food = 0. العمود الأخير يفسّر السبب في كل حالة: نمط الاستفسار الشائع، أو حدّ جملة داخل الـ corpus، أو كون الترتيب غير سليم في الإنجليزية.

Trap 1: the unigram counts are not the row sums

الفخ 1: عدّات unigram ليست مجاميع الصفوف

To normalize a row you divide by C(w₁), the unigram count of the row word. People reach for the row sum of the printed table. That is wrong.

لتطبيع صف تقسم على C(w₁)، أي عدّة الـ unigram لكلمة الصف. كثيرون يمدّون أيديهم إلى مجموع الصف المطبوع، وهذا خطأ.

يضع الجدول مجموع الخلايا الثماني المطبوعة بجانب العدّة الحقيقية C(word) لكل كلمة صف، والفرق بينهما في العمود الأخير. لاحظ الفجوة الهائلة: lunch مجموع صفه 3 وعدّته الحقيقية 341، وfood مجموعه 35 وعدّته 1093. استخدم دائماً عمود True C(word) كمقام، فهو وحده الصحيح.

From counts to probabilities

من العدّات إلى الاحتمالات

Maximum likelihood estimate for a bigram. Divide the cell by the unigram count of the row word.

تقدير maximum likelihood لـ bigram: اقسم الخلية على عدّة الـ unigram لكلمة الصف.

البسط هو عدّة الـ bigram C(w₁ w₂) كما هي في الخلية، والمقام المظلّل هو C(w₁) فقط، أي عدّة كلمة الصف وحدها. انتبه أن w₂ لا تظهر في المقام إطلاقاً.

Each row of the counts table gets divided by one number, so each row of the probability table sums to 1 over the full 1446 columns (not over the 8 printed ones).

كل صف في جدول العدّات يُقسم على رقم واحد، فيكون مجموع كل صف في جدول الاحتمالات 1 على الأعمدة الـ 1446 كاملة، لا على الأعمدة الثماني المطبوعة.

Worked examples straight off the table

أمثلة محلولة مباشرة من الجدول

يفكّك الجدول ثمانية بحوث مباشرة إلى ثلاث خطوات: الاحتمال المطلوب، ثم الخلية (البسط)، ثم المقسوم عليه (المقام). لاحظ أن المقام يتبع دائماً الكلمة المشروط عليها، أي كلمة الصف: P(to | want) = 608 / 927 = 0.66، وP(lunch | eat) = 42 / 746 = 0.056. غطِّ العمود الأخير وحاول إعادة إنتاجه بنفسك.

P(to | want)
  = C(want to) / C(want)
  = 608 / 927
  = 0.6559...
  = 0.66

P(spend | to)
  = C(to spend) / C(to)
  = 211 / 2417
  = 0.08729...
  = 0.087

P(chinese | want)
  = C(want chinese) / C(want)
  = 6 / 927
  = 0.006472...
  = 0.0065

The full normalized bigram matrix

مصفوفة bigram المطبَّعة كاملة

Every cell above divided by its row's unigram count.

كل خلية في الجدول السابق مقسومة على عدّة الـ unigram الخاصة بصفها.

هذه هي مصفوفة الاحتمالات المطبّعة، وتُقرأ بنفس الاتجاه: الصف هو الكلمة الأولى (الشرط)، والعمود هو الكلمة الثانية، فالخلية هي P(col | row). كل صف قُسِم على عدّة الـ unigram لكلمته هو. القيم الكبيرة هي الأنماط المتوقعة: P(to | want) = 0.66، وP(want | i) = 0.33، وP(eat | to) = 0.28، وP(food | chinese) = 0.52. والأصفار تبقى أصفاراً، لأن القسمة لا تحوّل صفراً إلى شيء.

Computing a sentence probability

حساب احتمال جملة

Bigram chain rule, with <s> at the front and </s> at the end.

chain rule لنموذج bigram، مع <s> في البداية و</s> في النهاية.

تتفكك الجملة إلى خمسة عوامل مضروبة. عدد العوامل يساوي عدد الكلمات زائد واحد، لأن إضافة <s> و</s> تخلق bigram إضافياً عند كل طرف. العاملان المظلّلان هما عاملا الحدود، وهما الوحيدان اللذان لا يمكن استخراجهما من الجدول.

Trap 2: not every factor comes from the table

الفخ 2: ليس كل عامل يأتي من الجدول

The 8 × 8 excerpt has no <s> row and no </s> column, so two of the five factors cannot be looked up. The slides supply them.

المقتطف بحجم 8 × 8 ليس فيه صف لـ <s> ولا عمود لـ </s>، فلا يمكن البحث عن عاملين من الخمسة. والشرائح تمدّك بهما جاهزين.

يصطفّ في الرسم خمسة صناديق مضروبة في بعضها. الثلاثة الوسطى بلون واحد وتحتها لافتة read off the 8 × 8 table: P(want|i) = 827/2533، وP(chinese|want) = 6/927، وP(food|chinese) = 82/158. والصندوقان في الطرفين بلون آخر وتحتهما لافتة must be supplied to you: P(i|<s>) = 0.25 وP(</s>|food) = 0.68. إذن خمسة عوامل ومصدران مختلفان.

Values supplied by the slides for the boundary and out-of-excerpt factors:

القيم التي تعطيها الشرائح لعوامل الحدود والعوامل الخارجة عن المقتطف:

P(<s> i want chinese food </s>)

  = P(i|<s>) x P(want|i) x P(chinese|want) x P(food|chinese) x P(</s>|food)
  =   0.25    x    0.33    x     0.0065      x      0.52        x     0.68

step 1   0.25   x 0.33    = 0.0825
step 2   0.0825 x 0.0065  = 0.00053625
step 3   0.00053625 x 0.52 = 0.000278850
step 4   0.000278850 x 0.68 = 0.000189618

  = 1.9 x 10^-4

Why we use log probabilities

لماذا نستخدم log probabilities

Every factor is at most 1, so the product only ever shrinks. A 30-word sentence multiplies 31 small numbers together and the result underflows to 0 in floating point. The fix is to add logs instead of multiplying probabilities.

كل عامل أصغر من 1 أو يساويه، فحاصل الضرب لا يفعل شيئاً إلا أن يصغر. وجملة من 30 كلمة تضرب 31 رقماً صغيراً، فينزلق الناتج إلى 0 في حساب الفاصلة العائمة (underflow). والحل أن تجمع اللوغاريتمات بدل أن تضرب الاحتمالات.

تقول الصيغة إن حاصل ضرب الاحتمالات يساوي exp لمجموع لوغاريتماتها. الجزء المظلّل هو الجمع، وهو ما تحسبه فعلياً، ثم تُطبّق exp مرة واحدة في النهاية إن احتجت الاحتمال نفسه.

same sentence, in log space (natural log)

  ln 0.25   = -1.386
  ln 0.33   = -1.109
  ln 0.0065 = -5.036
  ln 0.52   = -0.654
  ln 0.68   = -0.386
  ------------------
  sum       = -8.571

  exp(-8.571) = 1.90 x 10^-4      matches the direct product

What bigrams actually capture

ما الذي تلتقطه الـ bigrams فعلاً

None of this is engineered. It falls out of counting, which is why counting works so well and also why the model inherits every bias in the corpus.

لا شيء من هذا مصنوع يدوياً، بل يسقط من العدّ وحده. ولهذا يعمل العدّ بهذه الجودة، ولهذا أيضاً يرث النموذج كل تحيّز موجود في الـ corpus.

Sparsity, and why smoothing exists

التناثر (Sparsity)، ولماذا يوجد smoothing

يحسب المقطع حجم المشكلة: 1446 × 1446 = 2,090,916 خلية، مقابل 9332 استفساراً تعطي بضعة عشرات من آلاف الـ bigram tokens فقط. النتيجة أن الغالبية الطاغية من الخلايا 0.

A zero cell means the MLE says "this word pair is impossible". Multiply one impossible factor into a sentence and the whole sentence probability becomes exactly 0.

الخلية الصفرية تعني أن MLE يقول إن هذا الزوج من الكلمات مستحيل. واضرب عاملاً مستحيلاً واحداً في جملة فيصبح احتمال الجملة كلها 0 بالضبط.

The whole procedure in order

الإجراء كله بالترتيب

1. Add <s> and </s> to the sentence. Count the factors: a sentence of n words gives n+1 bigram factors.

   أضف <s> و</s> إلى الجملة، ثم عُدّ العوامل: جملة من n كلمة تعطي n+1 من عوامل الـ bigram.

2. For each factor, find the cell C(w₁ w₂) at row w₁, column w₂.

   لكل عامل، ابحث عن الخلية C(w₁ w₂) عند الصف w₁ والعمود w₂.

3. Divide by the unigram count C(w₁), taken from the given unigram row, never from a row sum.

   اقسم على عدّة الـ unigram C(w₁)، مأخوذة من صف الـ unigram المُعطى، لا من مجموع صف أبداً.

4. If a factor involves a word outside the printed excerpt (including the boundary tokens), use the value supplied in the question.

   إن كان العامل يضم كلمة خارج المقتطف المطبوع (ومنها رموز الحدود)، فاستخدم القيمة المعطاة في السؤال.

5. Multiply the factors, or add their logs and exponentiate at the end.

   اضرب العوامل، أو اجمع لوغاريتماتها ثم طبّق exp في النهاية.

6. Check for any zero factor. One zero means the answer is 0, and the real fix is smoothing.

   تحقّق من وجود أي عامل صفري. فصفر واحد يعني أن الجواب 0، والحل الحقيقي هو smoothing.