The prior and the channel modelالاحتمال المسبق (Prior) ونموذج القناة

Before looking at how acress could have been mistyped, ask a simpler question: if you pick a random word from a large body of English, how likely is it to be actress? In the COCA sample of 404,253,213 words, actress appears 9,321 times, so about 23 words in every million are actress. Across appears 120,844 times, about 299 per million. Without knowing anything about the typo, across is roughly 13 times more likely to be the word the writer meant.

قبل أن ننظر في الطريقة التي ربما كُتبت بها acress خطأً، اطرح سؤالًا أبسط: لو اخترت كلمة عشوائية من نص إنجليزي ضخم، فما احتمال أن تكون actress؟ في عيّنة COCA المكوّنة من 404,253,213 كلمة، تظهر actress عدد 9,321 مرة، أي قرابة 23 كلمة من كل مليون. وتظهر across عدد 120,844 مرة، أي قرابة 299 في المليون. فمن دون معرفة أي شيء عن الخطأ الإملائي، تكون across أرجح بنحو 13 مرة لأن تكون الكلمة التي قصدها الكاتب.

That number is the Prior probability, P(w): how plausible a candidate is as a piece of text before the typed string is taken into account. The noisy channel does not care where it comes from. Any language model from lecture 03 can provide it: a unigram, a Bigram language model that looks at the previous word, or a trigram that looks at two. The simplest choice, used on this slide, is the Unigram prior: the relative frequency of the word in a corpus.

هذا العدد هو prior probability أي الاحتمال المسبق P(w): مدى معقولية المرشح بوصفه قطعة من نص قبل أخذ السلسلة المكتوبة في الحسبان. ولا تهتم القناة الصاخبة بمصدره. فأي نموذج لغوي من المحاضرة 03 يمكنه توفيره: نموذج unigram، أو bigram language model الذي ينظر إلى الكلمة السابقة، أو نموذج trigram الذي ينظر إلى كلمتين. وأبسط خيار، وهو المستخدم في هذه الشريحة، هو unigram prior: التكرار النسبي للكلمة في مدوّنة.

The full table of priors for the six candidates of acress:

الجدول الكامل للاحتمالات المسبقة لمرشحي acress الستة:

Notice what this table cannot know. The original sentence was about a stellar and versatile acress, and any human reads actress at once. A unigram prior has no access to that sentence, so it ranks the candidates purely by how common they are in general. That is the weakness part 05 fixes by swapping in a bigram prior, which is exactly the flexibility slide 17 promises: the channel stays the same and only the language model changes.

لاحظ ما لا يستطيع هذا الجدول معرفته. كانت الجملة الأصلية عن acress «متألقة ومتعددة المواهب»، وأي إنسان يقرؤها actress فورًا. أما الاحتمال المسبق أحادي الكلمة فلا يصل إلى تلك الجملة، لذا يرتّب المرشحين فقط بحسب مدى شيوعهم عمومًا. وهذا هو الضعف الذي يعالجه الجزء 05 باستبدال احتمال مسبق من نوع bigram به، وهي بالضبط المرونة التي تعد بها الشريحة 17: تبقى القناة كما هي ويتغير النموذج اللغوي وحده.

Priors at web scaleالاحتمالات المسبقة على نطاق الويب

A search engine correcting queries has n-gram counts over hundreds of billions of words. Properly smoothed models such as Kneser-Ney are expensive to estimate at that size, so the slide points to Stupid backoff: use the relative frequency of the longest n-gram that was seen, and multiply by a fixed 0.4 each time you back off to a shorter one. The result is a score rather than a true probability, but the decoder only compares candidates, so a consistent score is enough. The full recipe and a worked example are in lecture 03, backoff and stupid backoff.

محرك البحث الذي يصحّح الاستعلامات يملك عدّات n-gram على مئات المليارات من الكلمات. والنماذج المنعّمة تنعيمًا سليمًا مثل Kneser-Ney مكلفة التقدير عند هذا الحجم، لذلك تشير الشريحة إلى stupid backoff: استخدم التكرار النسبي لأطول n-gram شوهد، واضرب في قيمة ثابتة 0.4 في كل مرة تتراجع فيها إلى n-gram أقصر. والنتيجة درجة وليست احتمالًا حقيقيًا، لكن المفكّك (decoder) يقارن المرشحين فقط، فتكفي درجة متّسقة. والوصفة الكاملة مع مثال محلول موجودة في المحاضرة 03، backoff وstupid backoff.

Take the candidate across. To get acress from it, the writer must have typed e where o was intended. How often does that happen? Kernighan, Church and Gale counted it over a large set of real typos from newswire text: e was typed for o 93 times. That single number, divided by how often o occurs at all, is the probability of the edit. This is the whole idea of the Channel model, also called the error model or edit probability.

خذ المرشح across. لكي نحصل منه على acress، لا بد أن الكاتب كتب e حيث كان يقصد o. فكم مرة يحدث ذلك؟ عدّه Kernighan وChurch وGale على مجموعة كبيرة من الأخطاء الإملائية الحقيقية في نصوص الأخبار: كُتب e بدلًا من o عدد 93 مرة. هذا العدد الواحد، مقسومًا على عدد مرات ظهور o أصلًا، هو احتمال التعديل. وهذه هي الفكرة الكاملة لـ channel model، ويُسمّى أيضًا نموذج الخطأ (error model) أو احتمال التعديل (edit probability).

Fix the notation from slide 19. The typed, misspelled word is x = x₁ x₂ … xₘ and the intended, correct word is w = w₁ w₂ … wₙ, both as sequences of letters. Every candidate from part 03 differs from the typo by a single edit, so P(x|w) is just the probability of that one edit: a Deletion, an Insertion, a Substitution or a Transposition. A perfect error model would condition on the typist, the keyboard and the time of day. This one conditions only on the letters involved and, for insertion and deletion, the letter just before, which is local enough to estimate from data.

ثبّت الرموز من الشريحة 19. الكلمة المكتوبة الخاطئة هي x = x₁ x₂ … xₘ والكلمة المقصودة الصحيحة هي w = w₁ w₂ … wₙ، وكلتاهما متتالية من الحروف. كل مرشح من الجزء 03 يختلف عن الخطأ الإملائي بتعديل واحد، لذا فإن P(x|w) هو ببساطة احتمال ذلك التعديل الواحد: حذف deletion، أو إدراج insertion، أو استبدال substitution، أو تبديل transposition. نموذج الخطأ المثالي كان سيشترط على الكاتب ولوحة المفاتيح ووقت اليوم. أما هذا النموذج فيشترط فقط على الحروف المعنية، وفي حالتي الإدراج والحذف على الحرف السابق مباشرة، وهذا محلي بما يكفي لتقديره من البيانات.

The four tablesالجداول الأربعة

A Confusion matrix is a table of counts of how often one thing was mistaken for another. The Kernighan, Church and Gale channel model uses four of them, one per edit type, each indexed by a pair of letters.

confusion matrix أو مصفوفة الالتباس هي جدول عدّات لعدد المرات التي أُخذ فيها شيء على أنه شيء آخر. ويستخدم Kernighan, Church and Gale channel model أربعًا منها، واحدة لكل نوع تعديل، وكل منها مفهرسة بزوج من الحروف.

Insertion and deletion are conditioned on the previous character. Dropping the t in actress is recorded as del[c,t], a t lost after a c, not as a bare t lost anywhere. That matters, because some letters vanish far more easily in certain neighborhoods, such as one letter of a doubled pair. The same choice gives insertion its first index: the extra s in acress, read as acres plus an s, is ins[e,s] or ins[s,s] depending on which s you call the extra one, and both readings appear on slide 24.

الإدراج والحذف مشروطان بالحرف السابق. فإسقاط t من actress يُسجَّل على أنه del[c,t]، أي t ضاع بعد c، لا مجرد t ضاع في أي مكان. وهذا مهم، لأن بعض الحروف تختفي بسهولة أكبر بكثير في جوار معيّن، مثل أحد حرفي زوج مكرر. والاختيار نفسه يعطي الإدراج فهرسه الأول: فالحرف s الزائد في acress، إذا قرأناها acres مضافًا إليها s، يكون ins[e,s] أو ins[s,s] بحسب أي s تعدّه الزائد، والقراءتان كلتاهما تظهران في الشريحة 24.

Reading the substitution matrixقراءة مصفوفة الاستبدال

Slide 21 prints the substitution table from the original paper. Rows are X, the letter typed; columns are Y, the letter intended. So the cell in row e, column o is sub[e,o] = 93: e typed for o. The big numbers cluster among the vowels: sub[e,a] = 388, sub[a,e] = 342, sub[i,e] = 146, sub[o,e] = 116. Vowels sound alike in unstressed syllables, so writers who spell by ear confuse them constantly. Among consonants the standout is sub[m,n] = 180, two letters that are both similar in sound and adjacent on the keyboard.

تطبع الشريحة 21 جدول الاستبدال من الورقة الأصلية. الصفوف هي X، الحرف المكتوب؛ والأعمدة هي Y، الحرف المقصود. لذا فالخلية في الصف e والعمود o هي sub[e,o] = 93: كُتب e بدلًا من o. وتتجمع الأعداد الكبيرة بين حروف العلة: sub[e,a] = 388، sub[a,e] = 342، sub[i,e] = 146، sub[o,e] = 116. فحروف العلة تتشابه في النطق داخل المقاطع غير المنبورة، ولذلك يخلط بينها باستمرار من يكتبون بحسب السمع. ومن بين الحروف الساكنة يبرز sub[m,n] = 180، وهما حرفان متشابهان في الصوت ومتجاوران على لوحة المفاتيح معًا.

Where the counts come fromمن أين تأتي العدّات

You need a list of real misspellings paired with their corrections, such as the Wikipedia list of common misspellings, Roger Mitton's Birkbeck corpus, or Peter Norvig's collection. Align each pair, find the single edit, and add one to the matching cell. Slide 22 points to Norvig's file of counts of single-edit errors, which already does this: it lists edits such as e|i with a count, ready to drop into the four tables. Kernighan, Church and Gale had no such list, so they bootstrapped: start with uniform matrices, correct a corpus of rejected words with the current model, recount the edits the corrections imply, and repeat. That loop is an instance of the EM algorithm.

تحتاج إلى قائمة بأخطاء إملائية حقيقية مقرونة بتصحيحاتها، مثل قائمة ويكيبيديا للأخطاء الإملائية الشائعة، أو مدوّنة Birkbeck الخاصة بـ Roger Mitton، أو مجموعة Peter Norvig. حاذِ كل زوج، وجد التعديل الواحد، وأضف واحدًا إلى الخلية المطابقة. وتشير الشريحة 22 إلى ملف Norvig لعدّات أخطاء التعديل الواحد، الذي يقوم بهذا مسبقًا: فهو يسرد تعديلات مثل e|i مع عدّها، جاهزة للإدخال في الجداول الأربعة. لم يكن لدى Kernighan وChurch وGale قائمة كهذه، فبدؤوا من الصفر بطريقة تمهيدية (bootstrapping): ابدأ بمصفوفات منتظمة، وصحّح مدوّنة من الكلمات المرفوضة بالنموذج الحالي، وأعد عدّ التعديلات التي تقتضيها التصحيحات، ثم كرّر. وهذه الحلقة مثال على خوارزمية EM.

Back to across. The count sub[e,o] = 93 on its own is not a probability: it would be large simply because o is a common letter. The fair question is: of all the times a writer meant to type o, how often did e come out? In the training text of Kernighan, Church and Gale, the letter o occurred roughly 10,000,000 times, so P(e|o) = 93 / 10,000,000 = .0000093, the across row of slide 24.

لنعد إلى across. العدّ sub[e,o] = 93 وحده ليس احتمالًا: فقد يكون كبيرًا لمجرد أن o حرف شائع. والسؤال المنصف هو: من بين كل المرات التي قصد فيها الكاتب كتابة o، كم مرة خرج e؟ في نص التدريب الخاص بـ Kernighan وChurch وGale، ظهر الحرف o قرابة 10,000,000 مرة، لذا P(e|o) = 93 / 10,000,000 = .0000093، وهو صف across في الشريحة 24.

The general rule repeats that move for each edit: divide the confusion count by the number of times the intended context occurred. The context is whatever the matrix was indexed on in the correct word, so the denominator always counts letters of w, never of x.

القاعدة العامة تكرر هذه الخطوة لكل تعديل: اقسم عدّ الالتباس على عدد مرات ظهور السياق المقصود. والسياق هو ما فُهرست عليه المصفوفة في الكلمة الصحيحة، لذا فإن المقام يعدّ دائمًا حروف w، ولا يعدّ أبدًا حروف x.

• Deletion divides by count[wᵢ₋₁ wᵢ], the number of times the pair that was supposed to appear actually appears, because each occurrence was a chance to drop its second letter.الحذف يقسم على count[wᵢ₋₁ wᵢ]، أي عدد مرات ظهور الزوج الذي كان يُفترض أن يظهر، لأن كل ظهور له كان فرصة لإسقاط حرفه الثاني.
• Insertion divides by count[wᵢ₋₁], a single letter, because each occurrence of it was a chance to type something extra afterwards. The numerator ins[wᵢ₋₁, xᵢ] names the extra typed letter xᵢ.الإدراج يقسم على count[wᵢ₋₁]، أي حرف واحد، لأن كل ظهور له كان فرصة لكتابة شيء زائد بعده. والبسط ins[wᵢ₋₁, xᵢ] يسمّي الحرف الزائد المكتوب xᵢ.
• Substitution divides by count[wᵢ], the intended letter that got replaced.الاستبدال يقسم على count[wᵢ]، أي الحرف المقصود الذي استُبدل.
• Transposition divides by count[wᵢ wᵢ₊₁], the intended pair that got swapped.التبديل يقسم على count[wᵢ wᵢ₊₁]، أي الزوج المقصود الذي تبادل حرفاه موقعيهما.

Mapping the acress table to the formulaربط جدول acress بالصيغة

Two rows need a closer look. For cress, the a at the start of acress is the extra letter, and there is no previous letter to condition on. The model uses a word-boundary symbol #, so the entry is a|#, priced as ins[#,a] / count[#], where count[#] is the number of word starts. Acres appears twice because there are two ways to read the extra s: inserted after e (es|e) or after the existing s (ss|s). Both are valid single edits, and in the original paper each row is scored as its own transformation; the two scores for acres are kept separate rather than merged.

صفّان يحتاجان إلى نظرة أدق. في cress، يكون الحرف a في بداية acress هو الحرف الزائد، ولا يوجد حرف سابق يُشترط عليه. فيستخدم النموذج رمز حدّ الكلمة #، فيصبح المدخل a|#، ويُحسب احتماله بـ ins[#,a] / count[#]، حيث count[#] هو عدد بدايات الكلمات. وتظهر acres مرتين لأن هناك طريقتين لقراءة s الزائد: مُدرج بعد e (es|e) أو بعد s الموجود أصلًا (ss|s). كلاهما تعديل واحد صالح، وفي الورقة الأصلية يُقيَّم كل صف بوصفه تحويلًا مستقلًا؛ فتبقى درجتا acres منفصلتين ولا تُدمجان.

Zero counts are smoothedالعدّات الصفرية تُنعَّم

Look up sub[r,c] in slide 21: row r, column c is 0. Nobody in the training data typed r for c. Yet slide 24 gives access a channel probability of .000000209, not zero. The reason is that the matrices are smoothed before use; the paper uses Good-Turing, which turns the zero into a small fractional count, about .98, over count[c] ≈ 4,700,000. Caress shows the same pattern, with a fractional count of about .95 over count[ca] ≈ 580,000. Without smoothing, one unseen confusion would veto a candidate no matter how strong its prior, which is the same zero problem n-gram models had in lecture 03.

ابحث عن sub[r,c] في الشريحة 21: الصف r والعمود c قيمته 0. لم يكتب أحد في بيانات التدريب r بدلًا من c. ومع ذلك تعطي الشريحة 24 الكلمة access احتمال قناة قدره .000000209، لا صفرًا. والسبب أن المصفوفات تُنعَّم قبل استخدامها؛ إذ تستخدم الورقة Good-Turing، الذي يحوّل الصفر إلى عدّ كسري صغير، قرابة .98، مقسومًا على count[c] ≈ 4,700,000. وتُظهر caress النمط نفسه، بعدّ كسري يقارب .95 مقسومًا على count[ca] ≈ 580,000. ومن دون تنعيم، فإن التباسًا واحدًا لم يُشاهَد سيُسقط المرشح مهما كان احتماله المسبق قويًا، وهي مشكلة الصفر نفسها التي واجهتها نماذج n-gram في المحاضرة 03.