Spelling correctionالتصحيح الإملائي

Look at three screenshots from the lecture before reading any definitions. Each one shows a different system doing a different job, and together they already contain the whole taxonomy of this part.

انظر إلى ثلاث لقطات شاشة من المحاضرة قبل قراءة أي تعريفات. كل واحدة منها تُظهر نظاما مختلفا يؤدي مهمة مختلفة، وهي معا تحتوي مسبقا على التصنيف الكامل لهذا الجزء.

• Microsoft Word underlines the sentence This is bigger then that ofcourse. It flags then and offers the single fix than. That is remarkable: then is a perfectly good English word, so Word could only have caught it by reading bigger ... that around it. It also flags ofcourse, which is not a word at all; the writer simply left out a space.يضع Microsoft Word خطا تحت الجملة This is bigger then that ofcourse. فهو يعلّم then ويعرض إصلاحا واحدا هو than. وهذا لافت للنظر: then كلمة إنجليزية صحيحة تماما، فلم يكن بإمكان Word أن يكتشفها إلا بقراءة bigger ... that من حولها. ويعلّم أيضا ofcourse، وهي ليست كلمة أصلا؛ فالكاتب ببساطة نسي مسافة.
• A web search engine receives natural langage processing and answers Showing results for natural language processing, with a link to search the original instead. langage is not an English word, so the engine knew something was wrong and was confident enough to act on its fix.محرك بحث على الويب يستقبل natural langage processing فيجيب Showing results for natural language processing (أي: تُعرض نتائج natural language processing)، مع رابط للبحث عن النص الأصلي بدلا من ذلك. كلمة langage ليست كلمة إنجليزية، لذلك عرف المحرك أن هناك خطأ، وكان واثقا بما يكفي ليطبّق إصلاحه مباشرة.
• A phone keyboard shows I will check it ther and offers three buttons: there, the, they. It is sure ther is wrong but not sure what was meant, so it hands the choice back to the user.لوحة مفاتيح الهاتف تعرض I will check it ther وتقدّم ثلاثة أزرار: there وthe وthey. فهي متأكدة أن ther خاطئة، لكنها غير متأكدة مما كان مقصودا، لذلك تعيد قرار الاختيار إلى المستخدم.

Notice the two separate questions each tool answers. First: is there an error here at all? Second: what was intended, and how sure am I? The second question also decides how the fix is shown: replaced silently, offered once, or offered as a list. And notice the difference between the errors themselves. langage, ther and ofcourse are not words. then is a word, just the wrong one. That difference is the spine of the rest of the part.

لاحظ السؤالين المنفصلين اللذين تجيب عنهما كل أداة. الأول: هل يوجد خطأ هنا أصلا؟ الثاني: ما الذي كان مقصودا، وما مدى تأكدي؟ والسؤال الثاني يحدد أيضا طريقة عرض الإصلاح: يُستبدل بصمت، أو يُعرض مرة واحدة، أو يُعرض كقائمة. ولاحظ أيضا الفرق بين الأخطاء نفسها. langage وther وofcourse ليست كلمات. أما then فهي كلمة، لكنها الكلمة الخطأ. وهذا الفرق هو العمود الفقري لبقية هذا الجزء.

Type hte on a phone and it becomes the before you look up. Type ther and you get three buttons instead. Both systems detected the error. They differ in how much they trusted their correction.

اكتب hte على الهاتف فتتحول إلى the قبل أن ترفع نظرك. واكتب ther فتحصل بدلا من ذلك على ثلاثة أزرار. كلا النظامين اكتشف الخطأ، والفرق بينهما هو مقدار ثقتهما في التصحيح.

This is the first split. Spelling error detection decides whether a token is misspelled and nothing more; the red underline is detection. Spelling error correction proposes what the writer meant. Detection can exist without correction (a plain underline), but correction always needs detection first, because you cannot fix what you did not notice.

هذا هو التقسيم الأول. Spelling error detection (كشف الخطأ الإملائي) يقرر هل الكلمة مكتوبة خطأ أم لا، ولا شيء أكثر من ذلك؛ والخط الأحمر تحت الكلمة هو الكشف. أما Spelling error correction (تصحيح الخطأ الإملائي) فيقترح ما كان الكاتب يقصده. يمكن أن يوجد الكشف دون تصحيح (خط تحت الكلمة فقط)، لكن التصحيح يحتاج دائما إلى الكشف أولا، لأنك لا تستطيع إصلاح ما لم تلاحظه.

Correction comes in three strengths, and they form a ladder:

يأتي التصحيح بثلاث درجات من القوة، وهي تشكّل سلّما:

1. Autocorrect: replace the word without asking, as hte to the, or as the search engine does when it runs natural language processing straight away and leaves only a Search instead for link back. Only safe when the system is very confident, because a wrong silent change is worse than no change.Autocorrect (التصحيح التلقائي): استبدال الكلمة دون سؤال، كما في hte إلى the، أو كما يفعل محرك البحث حين يشغّل البحث عن natural language processing مباشرة ولا يترك إلا رابط Search instead for للعودة إلى النص الأصلي. وهو آمن فقط حين يكون النظام واثقا جدا، لأن التغيير الصامت الخاطئ أسوأ من عدم التغيير.
2. Suggest a correction: show one fix and let the user accept it, as Word does when its right-click menu offers than above Ignore.اقتراح تصحيح: عرض إصلاح واحد وترك المستخدم يقبله، كما يفعل Word حين تعرض قائمة النقر بالزر الأيمن than فوق خيار Ignore (تجاهل).
3. Suggestion list: show several fixes ranked by likelihood, as the keyboard does with there, the, they. Used when the top candidates are close.قائمة اقتراحات: عرض عدة إصلاحات مرتبة حسب الاحتمال، كما تفعل لوحة المفاتيح مع there وthe وthey. وتُستخدم حين تكون المرشحات الأولى متقاربة.

Why hte is safe to autocorrect and ther is not: hte has one overwhelmingly likely source, the most frequent word in English, one swap away. ther sits one edit away from there, the, they, then and her, several of them very common. The lecture returns to this policy at the end as the Confidence ladder, once you can compute the confidence it depends on.

لماذا يكون التصحيح التلقائي لـhte آمنا ولـther غير آمن: لـhte مصدر واحد مرجّح بفارق ساحق، وهو أكثر الكلمات تكرارا في الإنجليزية، على بُعد تبديل واحد. أما ther فتقع على بُعد تعديل واحد من there وthe وthey وthen وher، وكثير منها شائع جدا. وتعود المحاضرة إلى هذه السياسة في نهايتها باسم Confidence ladder (سلّم الثقة)، بعد أن تصبح قادرا على حساب الثقة التي تعتمد عليها.

Take three slips. Someone types graffe for giraffe. Someone types there when they meant three. Someone writes piece in a sentence about a peace treaty. All three are spelling errors, and they are three different problems.

خذ ثلاث زلات. شخص يكتب graffe بدلا من giraffe. وشخص يكتب there وهو يقصد three. وشخص يكتب piece في جملة عن معاهدة peace (سلام). الثلاثة كلها أخطاء إملائية، لكنها ثلاث مشكلات مختلفة.

Where the error lands decides everythingالمكان الذي يقع فيه الخطأ يحدد كل شيء

graffe is a Non-word error: the typed string is not in the dictionary. That one fact makes it easy to detect, since any lookup fails. there and piece are real-word errors: the slip happened to land on another valid word. Lookup succeeds, so the error is invisible to it. The only evidence left is that the word does not fit its neighbours: I bought there tickets is odd English, I bought three tickets is not.

graffe هي Non-word error (خطأ كلمة غير موجودة): النص المكتوب ليس في القاموس. وهذه الحقيقة وحدها تجعل كشفه سهلا، لأن أي بحث في القاموس سيفشل. أما there وpiece فهما real-word errors (أخطاء كلمات حقيقية): وقعت الزلة صدفة على كلمة صحيحة أخرى. فالبحث في القاموس ينجح، ولذلك يكون الخطأ خفيا عنه. والدليل الوحيد الباقي هو أن الكلمة لا تتلاءم مع جاراتها: I bought there tickets إنجليزية غريبة، أما I bought three tickets فليست كذلك.

Two ways to land on the wrong wordطريقتان للوقوع على الكلمة الخطأ

Real-word errors split again by what went wrong in the writer:

تنقسم أخطاء الكلمات الحقيقية مرة أخرى بحسب ما الذي أخفق عند الكاتب:

• A Typographical error is a slip of the fingers. The writer knows how to spell three; two keys were pressed in the wrong order and produced there. These errors look like keyboard accidents: one letter inserted, dropped, swapped or replaced, often by a neighbouring key.Typographical error (الخطأ الطباعي) زلة أصابع. الكاتب يعرف كيف يتهجى three، لكنه ضغط مفتاحين بترتيب خاطئ فنتجت there. وتبدو هذه الأخطاء كحوادث لوحة مفاتيح: حرف واحد يُدرج أو يُحذف أو يُبدَّل موضعه أو يُستبدل، وكثيرا ما يكون ذلك بمفتاح مجاور.
• A Cognitive error is a slip of knowledge. The writer believes piece is how the word for the absence of war is spelled. The typical case is a Homophone: words that sound the same and are spelled differently, such as piece and peace, too and two. These errors are close in sound, not necessarily close in letters.Cognitive error (الخطأ المعرفي) زلة معرفة. الكاتب يعتقد أن piece هي تهجئة الكلمة التي تعني غياب الحرب. والحالة النموذجية هي Homophone (الكلمات المتجانسة صوتيا): كلمات تُنطق بالطريقة نفسها وتُكتب بشكل مختلف، مثل piece وpeace، وtoo وtwo. هذه الأخطاء قريبة في الصوت، وليست بالضرورة قريبة في الحروف.

The split is not just labels. It tells you where to look for the intended word. For a typo, search words a few keystrokes away. For a cognitive error, search words that sound alike. Slide 8 builds exactly those two searches.

هذا التقسيم ليس مجرد تسميات، بل يخبرك أين تبحث عن الكلمة المقصودة. في الخطأ الطباعي، ابحث في الكلمات التي تبعد بضع ضغطات مفاتيح. وفي الخطأ المعرفي، ابحث في الكلمات المتشابهة في النطق. والشريحة 8 تبني هذين البحثين بالضبط.

How common are spelling errors? The lecture lists five numbers from 1% to 26%. They are not contradictory measurements of one quantity. Each one describes a different way of typing.

ما مدى شيوع الأخطاء الإملائية؟ تسرد المحاضرة خمسة أرقام من 1% إلى 26%. وهي ليست قياسات متناقضة لكمية واحدة، بل كل رقم منها يصف طريقة مختلفة في الكتابة.

• 26% of web queries contain an error (Wang et al., 2003). Queries are typed fast, with no review, and full of names and rare terms.26% من استعلامات البحث على الويب تحتوي على خطأ (Wang et al., 2003). فالاستعلامات تُكتب بسرعة، دون مراجعة، وهي مليئة بالأسماء والمصطلحات النادرة.
• 13% when people retype text without using backspace (Whitelaw et al., 2009). The paper measured 10.8% misspelled tokens for 25 English typists and 12.5% for German, typing at a normal pace and avoiding backspace and delete.13% حين يعيد الناس كتابة نص دون استخدام زر المسح backspace (Whitelaw et al., 2009). قاست الورقة 10.8% من الكلمات المكتوبة خطأ لدى 25 كاتبا بالإنجليزية، و12.5% بالألمانية، وهم يكتبون بسرعة عادية ويتجنبون زرَّي backspace وdelete.
• 7% errors made and then corrected, and 2% left uncorrected, when retyping on a phone-sized organizer (Soukoreff and MacKenzie, 2003).7% أخطاء ارتُكبت ثم صُحّحت، و2% بقيت دون تصحيح، عند إعادة الكتابة على منظِّم شخصي بحجم الهاتف (Soukoreff and MacKenzie, 2003).
• 1% to 2% for careful retyping of printed text on a normal keyboard (Kane and Wobbrock, 2007; Grudin, 1983).من 1% إلى 2% عند إعادة كتابة نص مطبوع بعناية على لوحة مفاتيح عادية (Kane and Wobbrock, 2007؛ Grudin, 1983).

Read the list as a set of input conditions: device size, speed, whether errors may be fixed, and when they are counted. Take away backspace and the rate rises because nothing gets fixed. Shrink the keyboard and fingers land on neighbouring keys. Count errors before the user fixes them, and you see the 7%; count after, and only the 2% that survived. The same person can produce all of these numbers in one afternoon.

اقرأ القائمة على أنها مجموعة من ظروف الإدخال: حجم الجهاز، والسرعة، وهل يُسمح بإصلاح الأخطاء، ومتى تُحسب. انزع زر المسح فيرتفع المعدل لأن شيئا لا يُصلَح. صغّر لوحة المفاتيح فتقع الأصابع على المفاتيح المجاورة. احسب الأخطاء قبل أن يصلحها المستخدم فترى 7%؛ واحسبها بعد ذلك فلا ترى إلا 2% التي نجت من الإصلاح. والشخص نفسه يمكن أن ينتج كل هذه الأرقام في عصر يوم واحد.

Back to graffe. A dictionary says it is not a word, so it is an error. Now what should replace it: giraffe, gaffe, graf, grail, craft?

لنعد إلى graffe. القاموس يقول إنها ليست كلمة، إذن هي خطأ. والآن، ما الذي يجب أن يحل محلها: giraffe أم gaffe أم graf أم grail أم craft؟

Detection: anything not in the dictionaryالكشف: كل ما ليس في القاموس

For non-word errors, detection is a lookup. Any token not in the dictionary is flagged. The slide adds that the larger the dictionary the better, and modern systems indeed use huge word lists harvested from the web, so that names, product names and new words are not flagged as errors.

في أخطاء الكلمات غير الموجودة، الكشف مجرد بحث في القاموس: تُعلَّم أي كلمة غير موجودة فيه. وتضيف الشريحة أنه كلما كبر القاموس كان أفضل، والأنظمة الحديثة تستخدم فعلا قوائم كلمات ضخمة مجموعة من الويب، حتى لا تُعلَّم الأسماء وأسماء المنتجات والكلمات الجديدة على أنها أخطاء.

Correction: generate, then chooseالتصحيح: ولّد ثم اختر

Correction has two steps. Candidate generation produces the real words that are similar to the error, usually all dictionary words within one or two edits. Then the system ranks them and picks the best, in one of two ways:

للتصحيح خطوتان. Candidate generation (توليد المرشحين) ينتج الكلمات الحقيقية المشابهة للخطأ، وعادة تكون كل كلمات القاموس التي تبعد تعديلا واحدا أو تعديلين. ثم يرتّبها النظام ويختار أفضلها بإحدى طريقتين:

• Shortest weighted edit distance. Use Edit distance from the previous lecture, but weight each edit by how plausible it is: swapping two adjacent letters, or hitting a neighbouring key, should cost less than an arbitrary substitution. giraffe is one insertion from graffe; grail needs two substitutions and a deletion.أقصر مسافة تحرير موزونة. استخدم Edit distance (مسافة التحرير) من المحاضرة السابقة، لكن زِن كل تعديل بحسب معقوليته: تبديل حرفين متجاورين، أو ضغط مفتاح مجاور، يجب أن يكلّف أقل من استبدال عشوائي. giraffe تبعد إدراجا واحدا عن graffe؛ أما grail فتحتاج إلى استبدالين وحذف واحد.
• Highest noisy channel probability. Score each candidate by how likely that word is to have been typed as graffe, times how common the word is. This is the Noisy channel model, the subject of the next part.أعلى احتمال في القناة المشوشة. قيّم كل مرشح بمدى احتمال أن تكون تلك الكلمة قد كُتبت على شكل graffe، مضروبا في مدى شيوع الكلمة. وهذا هو Noisy channel model (نموذج القناة المشوشة)، موضوع الجزء التالي.

The noisy channel is the stronger choice because it also uses frequency: gaffe and giraffe are both one edit from graffe, and only probabilities can say which one people actually mean more often.

القناة المشوشة هي الخيار الأقوى لأنها تستخدم التكرار أيضا: gaffe وgiraffe كلتاهما تبعد تعديلا واحدا عن graffe، والاحتمالات وحدها هي التي تستطيع أن تقول أيّهما يقصدها الناس فعلا أكثر.

Now take I bought there tickets. Nothing is flagged, because every word is in the dictionary. Which word should the system even look at?

خذ الآن I bought there tickets. لا شيء يُعلَّم، لأن كل كلمة موجودة في القاموس. فأي كلمة يجب أن ينظر إليها النظام أصلا؟

All of them. Since a Real-word error cannot be detected by lookup, real-word correction folds detection and correction into one step and runs it on every word w in the sentence. For each word it builds a Candidate set from three sources:

كلها. فبما أن Real-word error (خطأ الكلمة الحقيقية) لا يمكن كشفه بالبحث في القاموس، فإن تصحيح الكلمات الحقيقية يدمج الكشف والتصحيح في خطوة واحدة ويطبّقها على كل كلمة w في الجملة. ولكل كلمة يبني Candidate set (مجموعة المرشحين) من ثلاثة مصادر:

1. Words with similar pronunciation, which catches cognitive errors: peace for piece, two and to for too.كلمات متشابهة في النطق، وهي تلتقط الأخطاء المعرفية: peace بدلا من piece، وtwo وto بدلا من too.
2. Words with similar spelling, which catches typographical errors: three and where for there.كلمات متشابهة في التهجئة، وهي تلتقط الأخطاء الطباعية: three وwhere بدلا من there.
3. The word w itself.الكلمة w نفسها.

Then it chooses the best candidate in context, either with the Noisy channel model (now with a language model that looks at the neighbouring words) or with a Confusion-set classifier trained for one confusable pair such as there and three.

ثم يختار أفضل مرشح في ضوء السياق، إما باستخدام Noisy channel model (وهذه المرة مع نموذج لغوي ينظر إلى الكلمات المجاورة)، وإما باستخدام Confusion-set classifier (مصنِّف مجموعة الالتباس) مدرَّب على زوج واحد من الكلمات التي يُخلط بينها مثل there وthree.

Why the typed word must stay in the raceلماذا يجب أن تبقى الكلمة المكتوبة في السباق

The third source is the important one. Almost every word in normal text is correct. If the candidate set for there held only three, where and their, the system would be forced to change a word in every position of every sentence. Keeping w lets it answer the detection question: if w wins, there was no error. In over there, there wins; in bought there tickets, three should win. Later the lecture gives the typed word its own probability, P(w|w), the Probability of no error.

المصدر الثالث هو الأهم. فكل كلمة تقريبا في النص العادي صحيحة. لو احتوت مجموعة المرشحين لـthere على three وwhere وtheir فقط، لاضطر النظام إلى تغيير كلمة في كل موضع من كل جملة. إبقاء w يسمح له بالإجابة عن سؤال الكشف: إذا فازت w فلم يكن هناك خطأ. في over there تفوز there؛ وفي bought there tickets يجب أن تفوز three. ولاحقا تعطي المحاضرة الكلمة المكتوبة احتمالها الخاص P(w|w)، وهو Probability of no error (احتمال عدم وجود خطأ).

Someone types acress. You know at once that this is not an English word. But what did they mean? Maybe actress with the t dropped, maybe across with an e in place of the o, maybe acres with an extra s. You cannot see inside the writer's head. All you have is the damaged string and your knowledge of how people type and what people usually write.

يكتب شخص ما acress. تعرف فورًا أنها ليست كلمة إنجليزية. لكن ماذا قصد؟ ربما actress وقد سقط منها حرف t، وربما across مع e مكان o، وربما acres مع s زائدة. لا يمكنك أن ترى ما في رأس الكاتب. كل ما لديك هو النص التالف، ومعرفتك بكيف يكتب الناس وبما يكتبونه عادةً.

The channel distorts, the decoder reasons backwardsالقناة تشوّه، وفاكّ الترميز يستنتج بالاتجاه المعاكس

The noisy channel model turns that intuition into a model. Imagine the writer's intended word as a clean message. On its way to the page it passes through a channel: tired fingers, a cramped keyboard, a shaky memory of the spelling. The channel adds noise in the form of substituted, inserted, deleted or swapped letters. What arrives is the observed string, which we call $x$. The word that was sent we call $w$.

يحوّل noisy channel model (نموذج القناة المشوّشة) هذا الحدس إلى نموذج. تخيّل الكلمة التي قصدها الكاتب رسالةً نظيفة. في طريقها إلى الورق تمر عبر قناة: أصابع متعبة، ولوحة مفاتيح ضيقة، وذاكرة مهزوزة للتهجئة. تضيف القناة تشويشًا على شكل حروف مستبدلة أو مُدرجة أو محذوفة أو متبادلة المواقع. وما يصل هو النص المُلاحَظ، ونسمّيه $x$. أما الكلمة التي أُرسلت فنسمّيها $w$.

Correction runs the picture in reverse. The decoder takes each hypothesis word from the vocabulary, imagines sending it through a model of the same channel, and asks how likely that word is to come out looking like acress. It also asks how likely the word was to be written in the first place. The hypothesis that best explains the noise, weighed by how common it is, becomes the guess. So there are two directions: the channel runs forward from intention to typing, and the decoder runs backward from the typed string to the intention, pushing every hypothesis through its own copy of the channel to see which noisy output matches.

التصحيح يشغّل الصورة بالعكس. يأخذ decoder (فاكّ الترميز) كل كلمة فرضية من المفردات، ويتخيّل إرسالها عبر نموذج للقناة نفسها، ويسأل: ما مدى احتمال أن تخرج هذه الكلمة على شكل acress؟ ويسأل أيضًا: ما مدى احتمال أن تُكتب هذه الكلمة أصلًا؟ والفرضية التي تفسّر التشويش أفضل تفسير، موزونةً بمدى شيوعها، تصبح هي التخمين. إذن هناك اتجاهان: القناة تسير إلى الأمام من النية إلى الكتابة، وفاكّ الترميز يسير إلى الخلف من النص المكتوب إلى النية، فيدفع كل فرضية عبر نسخته الخاصة من القناة ليرى أي مخرج مشوّش يطابق ما رأيناه.

Notice what the decoder needs. It needs a list of hypotheses to try, which in practice is not the whole vocabulary but a short list of nearby words (that is candidate generation, part 03). It needs a model of the channel, so it can say how likely each hypothesis is to turn into $x$. And it needs a sense of which words people actually use. The next concept shows that these last two needs are exactly the two factors that fall out of Bayes' rule.

لاحظ ما يحتاجه فاكّ الترميز. يحتاج قائمة فرضيات يجرّبها، وهي في الواقع ليست المفردات كلها بل قائمة قصيرة من الكلمات القريبة (وهذا هو candidate generation، أي توليد المرشحين، في الجزء 03). ويحتاج نموذجًا للقناة، ليقول ما مدى احتمال أن تتحول كل فرضية إلى $x$. ويحتاج إحساسًا بالكلمات التي يستخدمها الناس فعلًا. والمفهوم التالي يبيّن أن هاتين الحاجتين الأخيرتين هما بالضبط العاملان اللذان يخرجان من قاعدة بايز.

Return to acress. If you could read off, for each candidate word, the probability that it was the intended word given that we saw acress, you would just pick the biggest. That probability is $P(w \mid x)$, and the whole derivation on slide 11 is about turning it into things we can actually estimate.

عُد إلى acress. لو استطعت أن تقرأ لكل كلمة مرشحة احتمال أن تكون هي الكلمة المقصودة بشرط أننا رأينا acress، لاخترت الأكبر ببساطة. هذا الاحتمال هو $P(w \mid x)$، والاشتقاق كله في الشريحة 11 يدور حول تحويله إلى أشياء نستطيع تقديرها فعلًا.

Step 1: state the goalالخطوة 1: حدّد الهدف

Out of every word $w$ in the vocabulary $V$, pick the one with the highest probability given the observation $x$. The hat on $\hat{w}$ means “our estimate of the correct word”, and argmax means “the argument that makes this largest”, so it returns a word, not a probability.

من بين كل الكلمات $w$ في المفردات $V$، اختر الكلمة ذات الاحتمال الأعلى بشرط الملاحظة $x$. القبعة فوق $\hat{w}$ تعني «تقديرنا للكلمة الصحيحة»، وargmax تعني «القيمة (المُدخَل) التي تجعل هذا المقدار أكبر ما يمكن»، لذلك فهي تعيد كلمة لا احتمالًا.

Step 2: apply Bayes' ruleالخطوة 2: طبّق قاعدة بايز

Bayes' rule rewrites any conditional probability by flipping it: $P(a \mid b) = P(b \mid a)\,P(a) / P(b)$. With $a = w$ and $b = x$, the posterior we cannot estimate directly becomes a product of two things we can, divided by a third.

تعيد Bayes' rule (قاعدة بايز) كتابة أي احتمال شرطي بقلبه: $P(a \mid b) = P(b \mid a)\,P(a) / P(b)$. ومع $a = w$ و$b = x$، يصبح الاحتمال اللاحق (posterior) الذي لا نستطيع تقديره مباشرةً حاصلَ ضرب شيئين نستطيع تقديرهما، مقسومًا على شيء ثالث.

Step 3: drop P(x), and know whyالخطوة 3: احذف P(x)، واعرف السبب

The denominator $P(x)$ is the probability of the observed string itself. When we compare candidates, we compare them for the same $x$: we are always asking which word best explains acress, never a different string. So $P(x)$ is one fixed positive number, shared by every candidate. Dividing every score by the same positive number shrinks or stretches all of them equally; it cannot change which one is largest. The argmax is unchanged, so we drop the denominator.

المقام $P(x)$ هو احتمال النص المُلاحَظ نفسه. عندما نقارن المرشحين، نقارنهم على $x$ نفسه: نحن نسأل دائمًا أي كلمة تفسّر acress أفضل تفسير، ولا نسأل أبدًا عن نص آخر. إذن $P(x)$ عدد موجب ثابت واحد يشترك فيه كل المرشحين. وقسمة كل الدرجات على العدد الموجب نفسه تصغّرها أو تكبّرها جميعًا بالنسبة نفسها، ولا يمكن أن تغيّر أيّها الأكبر. قيمة argmax لا تتغير، لذلك نحذف المقام.

There is a practical bonus. Computing $P(x)$ properly would mean summing $P(x \mid w)\,P(w)$ over every possible $w$. Dropping it saves that whole sum. The price is that the remaining scores are no longer probabilities that add to one; they are only useful for ranking. That is all the corrector needs.

وهناك فائدة عملية إضافية. حساب $P(x)$ بشكل صحيح يعني جمع $P(x \mid w)\,P(w)$ على كل $w$ ممكنة. وحذفه يوفّر هذا المجموع كله. والثمن أن الدرجات المتبقية لم تعد احتمالات مجموعها واحد؛ فهي مفيدة للترتيب فقط. وهذا كل ما يحتاجه المصحّح.

Name the two factorsسمِّ العاملين

What survives is a product of two very different pieces of knowledge. Learn the names; exams use all of them interchangeably.

ما يتبقى هو حاصل ضرب نوعين مختلفين جدًا من المعرفة. احفظ الأسماء؛ فالاختبارات تستخدمها كلها بالتبادل.

$P(x \mid w)$ is the channel model, also called the error model, and in Bayesian language the likelihood. It is about typing: how likely is a writer who meant actress to produce acress? Part 04 estimates it from a confusion matrix of real typing mistakes. $P(w)$ is the prior probability, supplied by a language model. It is about the language: how common is actress as a word, or after the word that precedes it? This is exactly the n-gram machinery of lecture 03; a unigram prior uses single-word counts, a bigram language model brings in the previous word.

الحد $P(x \mid w)$ هو channel model (نموذج القناة)، ويسمّى أيضًا نموذج الخطأ (error model)، وفي لغة بايز هو الاحتمال الشرطي (likelihood). موضوعه الكتابة: ما مدى احتمال أن يكتب شخص قصد actress النص acress؟ والجزء 04 يقدّره من confusion matrix (مصفوفة الالتباس) لأخطاء كتابة حقيقية. أما $P(w)$ فهو prior probability (الاحتمال المسبق)، ويوفّره نموذج لغة. موضوعه اللغة: ما مدى شيوع actress كلمةً، أو بعد الكلمة التي تسبقها؟ وهذه بالضبط آلية n-gram من المحاضرة 03؛ فـ unigram prior يستخدم أعداد الكلمات المفردة، وbigram language model يُدخل الكلمة السابقة في الحساب.

The noisy channel did not start with spelling. Shannon modelled communication as a source passing through a noisy channel in 1948, and IBM researchers combined a prior with a likelihood for optical character recognition in the 1960s. Spelling correction adopted the full prior times likelihood recipe around 1990, at two labs almost at the same time.

لم تبدأ القناة المشوّشة مع الإملاء. فقد نمذج Shannon الاتصال على أنه مصدر يمر عبر قناة مشوّشة سنة 1948، وجمع باحثو IBM بين احتمال مسبق واحتمال شرطي في التعرف الضوئي على الحروف (OCR) في 1960s (الستينيات). وتبنّى تصحيح الإملاء الوصفة الكاملة، الاحتمال المسبق مضروبًا في الاحتمال الشرطي، نحو سنة 1990، في مختبرين في الوقت نفسه تقريبًا.

• AT&T Bell Labs. Kernighan, Church and Gale, “A spelling correction program based on a noisy channel model”, COLING 1990. They scored candidates for non-word errors with a channel model built from confusion counts, the Kernighan, Church and Gale channel model you will compute in part 04 for the acress example.AT&T Bell Labs. Kernighan وChurch وGale، «A spelling correction program based on a noisy channel model»، COLING 1990. أعطوا درجات للمرشحين في أخطاء الكلمات غير الموجودة (non-word errors) باستخدام نموذج قناة مبني من أعداد الالتباس (confusion counts)، وهو Kernighan, Church and Gale channel model الذي ستحسبه في الجزء 04 لـ acress example.
• IBM. Mays, Damerau and Mercer, “Context based spelling correction”, Information Processing and Management 27(5), 517 to 522, 1991. They generated candidate sentences by editing each word, scored them with a word language model as the prior, and so applied the channel idea to every word in a sentence. That is how real-word errors are handled in part 06.IBM. Mays وDamerau وMercer، «Context based spelling correction»، Information Processing and Management 27(5), 517 to 522، 1991. ولّدوا جملًا مرشحة بتعديل كل كلمة، وأعطوها درجات باستخدام نموذج لغة على مستوى الكلمات بوصفه الاحتمال المسبق، فطبّقوا بذلك فكرة القناة على كل كلمة في الجملة. وهكذا تُعالَج real-word errors (أخطاء الكلمات الحقيقية) في الجزء 06.

One equation, three fieldsمعادلة واحدة، ثلاثة مجالات

Strip away the word “spelling” and the rule says: to recover a hidden source from a noisy observation, multiply a model of how the source gets distorted by a model of what sources are likely. That recipe is the backbone of classical speech recognition and of the IBM statistical machine translation models. Brown, Della Pietra, Della Pietra and Mercer (1993) call $\hat{e} = \operatorname{argmax}_e \Pr(e)\,\Pr(f \mid e)$ the Fundamental Equation of Machine Translation, derived exactly as on slide 11: Bayes' rule, then drop the denominator because it does not depend on $e$.

انزع كلمة «إملاء» وستجد القاعدة تقول: لاستعادة مصدر خفي من ملاحظة مشوّشة، اضرب نموذجًا لكيفية تشوّه المصدر في نموذج لما هو مرجّح من المصادر. هذه الوصفة هي العمود الفقري للتعرف على الكلام الكلاسيكي ولنماذج الترجمة الآلية الإحصائية من IBM. ويسمّي Brown وDella Pietra وDella Pietra وMercer (1993) الصيغة $\hat{e} = \operatorname{argmax}_e \Pr(e)\,\Pr(f \mid e)$ «المعادلة الأساسية للترجمة الآلية» (Fundamental Equation of Machine Translation)، وتُشتق تمامًا كما في الشريحة 11: قاعدة بايز، ثم حذف المقام لأنه لا يعتمد على $e$.

In all three, the prior is a language model, the very n-gram model from lecture 03. That is why one good language model can be reused across spelling, speech and translation, while each task brings its own channel. It also explains how this lecture is organised: parts 03 and 04 build the channel side, parts 04 and 05 the language model side, and parts 06 to 08 extend the same product to context and to real systems.

في المهام الثلاث كلها، الاحتمال المسبق نموذج لغة، وهو نموذج n-gram نفسه من المحاضرة 03. ولهذا يمكن إعادة استخدام نموذج لغة جيد واحد في الإملاء والكلام والترجمة، بينما تأتي كل مهمة بقناتها الخاصة. وهذا يفسّر أيضًا تنظيم هذه المحاضرة: الجزآن 03 و04 يبنيان جانب القناة، والجزآن 04 و05 جانب نموذج اللغة، والأجزاء من 06 إلى 08 توسّع حاصل الضرب نفسه ليشمل السياق والأنظمة الحقيقية.

Someone types acress. No English dictionary contains it, so this is a Non-word error: detection is a simple lookup. Correction is the hard half. What did they mean? Your mind probably offers actress or across within a second, and maybe acres. You did not search a dictionary alphabetically. You searched the neighbourhood of the typo, words that look like it.

يكتب شخص ما acress. لا يحتوي أي قاموس إنجليزي على هذه الكلمة، لذا فهذا non-word error (خطأ ينتج كلمة غير موجودة): اكتشافه مجرد بحث بسيط في القاموس. التصحيح هو النصف الصعب. ماذا كان يقصد؟ غالبًا يقترح عليك ذهنك actress أو across خلال ثانية، وربما acres. لم تبحث في القاموس أبجديًا. بل بحثت في جوار الخطأ، أي الكلمات التي تشبهه.

From a typo to a list of suspectsمن الخطأ الإملائي إلى قائمة من المشتبه بهم

Candidate generation is that neighbourhood search made explicit. It turns one observed string x into a short list of real words w, and only those words go on to the Noisy channel model, where each is scored by P(x|w)P(w). The argmax in that formula ranges over the candidate list, not over the whole vocabulary. That is the first thing to understand about this step: it decides which answers are even possible. If the right word is not generated, no amount of good scoring can recover it.

Candidate generation (توليد المرشحين) هو هذا البحث في الجوار وقد صار صريحًا. فهو يحوّل سلسلة واحدة مرصودة x إلى قائمة قصيرة من الكلمات الحقيقية w، وهذه الكلمات وحدها تنتقل إلى noisy channel model، حيث تُعطى كل منها درجة بالقيمة P(x|w)P(w). الـ argmax في هذه الصيغة يمتد على قائمة المرشحين، لا على المفردات كلها. هذا أول ما يجب فهمه عن هذه الخطوة: إنها تحدد أي الإجابات ممكنة أصلًا. إذا لم تُولَّد الكلمة الصحيحة، فلن يستطيع أي قدر من حساب الدرجات الجيد استعادتها.

The lecture names two ways a real word can be near a typo.

تذكر المحاضرة طريقتين يمكن أن تكون بهما كلمة حقيقية قريبة من خطأ إملائي.

• Similar spelling. The word has a small Edit distance to the error: a few letters inserted, deleted, replaced or swapped turn one into the other. This catches typographical errors, slips of the fingers such as actress typed as acress.تهجئة متشابهة. للكلمة edit distance (مسافة تعديل) صغيرة إلى الخطأ: بضعة أحرف تُدرج أو تُحذف أو تُستبدل أو تُبدَّل مواضعها فتحوّل إحداهما إلى الأخرى. هذا يلتقط typographical errors (أخطاء الطباعة)، وهي زلّات الأصابع مثل كتابة actress على شكل acress.
• Similar pronunciation. The word sounds like the error. Each string is first mapped to an approximate pronunciation, and candidates are words whose pronunciation is a small edit distance from the pronunciation of the typo. This catches cognitive errors, where the writer spells by sound, which letter edits alone can miss when the spelling is far off but the sound is close.نطق متشابه. الكلمة تبدو في صوتها مثل الخطأ. تُحوَّل كل سلسلة أولًا إلى نطق تقريبي، والمرشحون هم الكلمات التي يبعد نطقها مسافة تعديل صغيرة عن نطق الخطأ. هذا يلتقط cognitive errors (الأخطاء الإدراكية)، حين يتهجّى الكاتب الكلمة بحسب صوتها، وهي أخطاء قد تفوت تعديلات الأحرف وحدها عندما تكون التهجئة بعيدة لكن الصوت قريب.

Both routes use the same tool, edit distance, applied to different strings: letters in one case, pronunciation symbols in the other. GNU aspell, for example, generates candidates by comparing Metaphone keys, and later systems fold this into a Phonetic error model. Part 8 returns to those. For the rest of this part we work with spelling, which is what the acress example and the Kernighan, Church and Gale data use.

يستخدم الطريقان الأداة نفسها، مسافة التعديل، مطبّقة على سلاسل مختلفة: الأحرف في حالة، ورموز النطق في الأخرى. فبرنامج GNU aspell مثلًا يولّد المرشحين بمقارنة مفاتيح Metaphone، والأنظمة اللاحقة تدمج ذلك في phonetic error model (نموذج أخطاء صوتي). يعود الجزء 8 إلى هذه الأنظمة. في بقية هذا الجزء نعمل على التهجئة، وهي ما يستخدمه مثال acress وبيانات Kernighan وChurch وGale.

Take the intended word actress and imagine the typist hurrying. Their finger skips the t, and acress comes out. Now take caress: the typist hits a before c, and acress comes out again. Six different real words can turn into the same typo with a single slip each. The table on slide 15 lists every one of them and names the slip.

خذ الكلمة المقصودة actress وتخيّل الكاتب مستعجلًا. يتخطى إصبعه الحرف t، فتخرج acress. والآن خذ caress: يضغط الكاتب a قبل c، فتخرج acress مرة أخرى. ست كلمات حقيقية مختلفة يمكن أن تتحول إلى الخطأ نفسه بزلّة واحدة لكل منها. الجدول في الشريحة 15 يسرد كل واحدة منها ويسمّي الزلّة.

Four kinds of single slipأربعة أنواع من الزلّة الواحدة

Spelling correction uses Damerau-Levenshtein distance, which counts four operations, each at cost 1:

يستخدم تصحيح التهجئة Damerau-Levenshtein distance، التي تحتسب أربع عمليات، تكلفة كل منها 1:

• Deletion: a letter of the intended word is left out (actress becomes acress).Deletion (حذف): يُترك حرف من الكلمة المقصودة دون كتابة (actress تصبح acress).
• Insertion: an extra letter is typed (cress becomes acress).Insertion (إدراج): يُكتب حرف زائد (cress تصبح acress).
• Substitution: one letter is typed in place of another (across becomes acress).Substitution (استبدال): يُكتب حرف مكان حرف آخر (across تصبح acress).
• Transposition: two adjacent letters are swapped (caress becomes acress).Transposition (تبديل مواضع): يتبادل حرفان متجاوران موضعيهما (caress تصبح acress).

The convention that decides exam answersالاصطلاح الذي يحسم إجابات الامتحان

The type always names what the typist did to the correct word to produce the error. Read every row as intended word → typo, never the other way. That is why the columns are called correct letter and error letter: the correct letter is what should have been typed, the error letter is what was typed, and a dash means nothing. So actress has correct letter t and error letter dash: a t should have been there and nothing was typed, a deletion. cress has correct letter dash and error letter a: nothing should have been there and an a was typed, an insertion.

يسمّي النوعُ دائمًا ما فعله الكاتب بالكلمة الصحيحة لينتج الخطأ. اقرأ كل صف على أنه intended word → typo (من الكلمة المقصودة إلى الخطأ)، لا العكس أبدًا. لهذا سُمّي العمودان correct letter (الحرف الصحيح) وerror letter (الحرف الخاطئ): الحرف الصحيح هو ما كان يجب أن يُكتب، والحرف الخاطئ هو ما كُتب فعلًا، والشرطة تعني لا شيء. إذن لـ actress حرف صحيح t وحرف خاطئ شرطة: كان يجب أن يوجد t ولم يُكتب شيء، أي حذف. ولـ cress حرف صحيح شرطة وحرف خاطئ a: لم يكن يجب أن يوجد شيء وكُتب a، أي إدراج.

Why transposition gets its own operationلماذا يحصل تبديل المواضع على عملية خاصة به

In lecture 2 you computed minimum edit distance with three operations only, insertion, deletion and substitution. That is Levenshtein distance. Under it, caress and acress are two edits apart: two substitutions, or a deletion plus an insertion. Damerau observed in 1964 that swapping two neighbouring keys is one of the commonest typing mistakes, so he counted it as a single edit. Adding that one operation is the only difference, and it is what makes caress a distance-1 candidate.

في المحاضرة 2 حسبت مسافة التعديل الدنيا (minimum edit distance) بثلاث عمليات فقط: الإدراج والحذف والاستبدال. هذه هي مسافة Levenshtein. وفقها، تبعد caress وacress تعديلين: استبدالين، أو حذفًا مع إدراج. لاحظ Damerau عام 1964 أن تبديل مفتاحين متجاورين من أكثر أخطاء الطباعة شيوعًا، فاحتسبه تعديلًا واحدًا. إضافة هذه العملية الواحدة هي الفرق الوحيد، وهي ما يجعل caress مرشحًا على مسافة 1.

How does a program actually find those six words? It does not compare acress against every dictionary entry. It runs the four operations in reverse on the typo itself, every possible way, and then asks the dictionary which of the results exist. Peter Norvig's well-known corrector does exactly this in a few lines. The number of strings it produces is worth computing once, because it explains the whole design.

كيف يجد البرنامج هذه الكلمات الست فعلًا؟ إنه لا يقارن acress بكل مدخل في القاموس. بل يشغّل العمليات الأربع بالعكس على الخطأ نفسه، بكل طريقة ممكنة، ثم يسأل القاموس أي النتائج موجود. مصحح Peter Norvig المعروف يفعل هذا بالضبط في بضعة أسطر. عدد السلاسل التي ينتجها يستحق أن يُحسب مرة واحدة، لأنه يفسّر التصميم كله.

This is why the dictionary filter, not the edit operations, is the key step. Generating strings is trivial and cheap; almost all of them are nonsense. Intersecting them with the dictionary is what turns a few hundred strings into a handful of real candidates, each with its edit type and position recorded for the channel model. Because the count is linear in n, edit-1 generation is fast for any realistic word.

لهذا السبب فإن فلتر القاموس، لا عمليات التعديل، هو الخطوة الأساسية. توليد السلاسل أمر تافه ورخيص؛ وكلها تقريبًا بلا معنى. تقاطعها مع القاموس هو ما يحوّل بضع مئات من السلاسل إلى حفنة من المرشحين الحقيقيين، مع تسجيل نوع التعديل وموضعه لكل منها لصالح نموذج القناة. ولأن العدد خطي في n، فإن توليد السلاسل على بُعد تعديل واحد سريع لأي كلمة واقعية.

Why stop at one or two editsلماذا نتوقف عند تعديل واحد أو تعديلين

The radius is set by data on real errors. Damerau's 1964 study found that more than 80% of the misspellings he examined were a single insertion, deletion, substitution or transposition, and the slide's rule follows: about 80% of errors are within edit distance 1, almost all within 2. Norvig's experiment agrees on the second half: in his development set only 3 of 270 errors were further than two edits from the correction.

يُحدَّد نصف القطر ببيانات الأخطاء الحقيقية. وجدت دراسة Damerau عام 1964 أن أكثر من 80% من الأخطاء الإملائية التي فحصها كانت إدراجًا واحدًا أو حذفًا أو استبدالًا أو تبديل مواضع، ومنها تأتي قاعدة الشريحة: نحو 80% من الأخطاء ضمن مسافة تعديل 1، وكلها تقريبًا ضمن 2. وتجربة Norvig تتفق مع الشطر الثاني: في مجموعة التطوير لديه كان 3 فقط من 270 خطأ أبعد من تعديلين عن التصحيح.

Going further is expensive and rarely useful. Applying the generator twice squares the work: for acress the edit-2 set has on the order of 335 × 349 ≈ 117,000 raw strings, and the number of real words inside that wider ring grows too, so the channel model has more distractors to separate. Norvig's corrector therefore tries distance 1 first and widens to distance 2 only when distance 1 finds no known word.

الذهاب أبعد مكلف ونادرًا ما يفيد. تطبيق المولّد مرتين يربّع العمل: لكلمة acress تضم مجموعة التعديلين ما يقارب 335 × 349 ≈ 117,000 سلسلة خام، ويزداد أيضًا عدد الكلمات الحقيقية داخل هذه الحلقة الأوسع، فيكون أمام نموذج القناة مشتّتات أكثر عليه التمييز بينها. لذلك يجرّب مصحح Norvig المسافة 1 أولًا، ولا يتوسع إلى المسافة 2 إلا عندما لا تجد المسافة 1 أي كلمة معروفة.

Space and hyphen as extra editsالمسافة والشرطة كتعديلات إضافية

Some errors are not inside a word at all. A typist who misses the space bar produces thisidea for this idea; one who drops a hyphen produces inlaw for in-law. Neither is one letter edit from a single dictionary word, so the plain generator returns nothing. Allowing the generator to insert a space or a hyphen between two letters fixes this, as long as the lookup then checks each piece. It adds only 2(n - 1) strings.

بعض الأخطاء ليست داخل كلمة أصلًا. الكاتب الذي يخطئ مفتاح المسافة ينتج thisidea بدلًا من this idea؛ ومن يُسقط شرطة ينتج inlaw بدلًا من in-law. لا يبعد أي منهما تعديل حرف واحد عن كلمة واحدة في القاموس، لذا لا يعيد المولّد العادي شيئًا. السماح للمولّد بإدراج مسافة أو شرطة بين حرفين يحل المشكلة، بشرط أن يفحص البحث بعد ذلك كل جزء على حدة. وهذا لا يضيف إلا 2(n - 1) سلسلة.

Try the generator below. Start with acress and check that the counts match the worked example and that the survivors match slide 15, both acres rows included. Then try teh, graffe, and the two run-together presets. Notice that the survivor column names the typist's error even though the generator ran the opposite operation. The run-together presets switch the space and hyphen option on; switch it on for acress too and a cress appears as an eighth row, a small reminder that every extra kind of edit also admits extra distractors.

جرّب المولّد أدناه. ابدأ بـ acress وتحقق من أن الأعداد تطابق المثال المحلول وأن الناجين يطابقون الشريحة 15، بما في ذلك صفّا acres كلاهما. ثم جرّب teh وgraffe والإعدادين المسبقين للكلمات الملتصقة. لاحظ أن عمود الناجين يسمّي خطأ الكاتب رغم أن المولّد نفّذ العملية المعاكسة. الإعدادان المسبقان للكلمات الملتصقة يفعّلان خيار المسافة والشرطة؛ فعّله مع acress أيضًا وستظهر a cress صفًا ثامنًا، تذكيرًا صغيرًا بأن كل نوع إضافي من التعديل يُدخل أيضًا مشتّتات إضافية.

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.

Take the acress example. Candidate generation gave us actress, cress, caress, access, across and acres, each one edit away from the typed string. Two candidates look strong to a human: actress, if a t was dropped, and across, if an o was typed as an e. Which one should a machine choose?

خذ مثال acress. أعطانا توليد المرشّحين الكلمات actress وcress وcaress وaccess وacross وacres، وكل منها على بُعد تعديل واحد من السلسلة المكتوبة. يبدو مرشّحان قويين للإنسان: actress إذا سقط حرف t، وacross إذا كُتب حرف o على أنه e. فأيهما يجب أن تختار الآلة؟

The score is a product of two columnsالدرجة حاصل ضرب عمودين

The noisy channel model answers by Bayes. For each candidate w it multiplies two numbers. The channel model P(x|w) says how likely the typist was to produce acress when they meant w; it comes from the Kernighan, Church and Gale confusion matrices. The prior P(w) says how likely w is in the first place. Here the prior is a unigram prior: the word's count in COCA divided by the corpus size. The decision is the argmax of the product.

يجيب نموذج القناة المشوشة (noisy channel model) بقاعدة بايز. فلكل مرشّح w يضرب عددين. نموذج القناة (channel model) P(x|w) يقول ما مدى احتمال أن يكتب الكاتب acress وهو يقصد w، ويأتي من مصفوفات الالتباس (confusion matrices) عند Kernighan, Church and Gale. أما الاحتمال المسبق (prior) P(w) فيقول ما مدى احتمال w أصلًا. والاحتمال المسبق هنا احتمال مسبق أحادي الكلمة (unigram prior): عدد مرات ظهور الكلمة في COCA مقسومًا على حجم المدوّنة. والقرار هو argmax لحاصل الضرب.

The table below is that product for every candidate. The edit column uses the slide's x|w notation: typed letters on the left, intended letters on the right. So c|ct is a deletion (the t after c was lost), e|o is a substitution, ac|ca is a transposition, and both acres rows are an insertion of an extra s. The last column is multiplied by 10⁹ only to make the tiny products readable.

الجدول التالي هو حاصل الضرب هذا لكل مرشّح. يستخدم عمود التعديل ترميز الشريحة x|w: الحروف المكتوبة على اليسار والحروف المقصودة على اليمين. فـ c|ct هو حذف (deletion) (ضاع حرف t بعد c)، وe|o هو استبدال (substitution)، وac|ca هو تبديل مواقع (transposition)، وكلا صفَّي acres هما إدراج (insertion) لحرف s زائد. والعمود الأخير مضروب في 10⁹ فقط لتسهيل قراءة حواصل الضرب الصغيرة جدًا.

Why the answer is wrong, and what the model could not seeلماذا الإجابة خاطئة، وما الذي لم يستطع النموذج رؤيته

The sentence this misspelling came from reads "a stellar and versatile acress whose combination of sass and glamour". Any reader knows the writer meant actress. The model chose across because its prior asks only how common a word is in general, and across is a very common word. Nothing in P(w) looks at the neighbors. The two factors also see different evidence: the channel looks at letters, the prior at word frequency, and neither one looks at the sentence.

الجملة التي جاء منها هذا الخطأ الإملائي هي "a stellar and versatile acress whose combination of sass and glamour". وأي قارئ يعرف أن الكاتب قصد actress. اختار النموذج across لأن احتماله المسبق لا يسأل إلا عن مدى شيوع الكلمة عمومًا، وacross كلمة شائعة جدًا. لا شيء في P(w) ينظر إلى الكلمات المجاورة. كما أن العاملين يريان أدلة مختلفة: القناة تنظر إلى الحروف، والاحتمال المسبق إلى تكرار الكلمة، ولا أحد منهما ينظر إلى الجملة.

Put acress back in its sentence: "versatile acress whose". Ask two questions a reader asks without thinking. Does the candidate follow versatile naturally? Does whose follow the candidate naturally? A versatile actress whose career is a normal phrase. A versatile across whose is not English.

أعد acress إلى جملتها: "versatile acress whose". واطرح سؤالين يطرحهما القارئ دون تفكير. هل يأتي المرشّح بعد versatile بشكل طبيعي؟ وهل تأتي whose بعد المرشّح بشكل طبيعي؟ عبارة "a versatile actress whose career" عبارة عادية، أما "a versatile across whose" فليست إنجليزية.

Replace P(w) with the bigrams on both sidesاستبدل P(w) بالـ bigrams على الجانبين

A bigram language model turns those two questions into numbers. The candidate sits between two bigrams, one with the word before it and one with the word after it, so the prior for the candidate in this position is P(w | versatile) × P(whose | w). The counts come from COCA with add-1 smoothing, so a bigram never seen in the corpus still gets a small nonzero probability.

يحوّل نموذج اللغة ثنائي الكلمات (bigram language model) هذين السؤالين إلى أرقام. يقع المرشّح بين اثنين من الـ bigrams: واحد مع الكلمة التي قبله وواحد مع الكلمة التي بعده، لذا فإن الاحتمال المسبق للمرشّح في هذا الموضع هو P(w | versatile) × P(whose | w). وتأتي الأعداد من COCA مع التنعيم بإضافة واحد (add-1 smoothing)، فيحصل حتى الـ bigram الذي لم يظهر قط في المدوّنة على احتمال صغير غير صفري.

• P(actress | versatile) = .000021 and P(across | versatile) = .000021. The left bigram is a tie, so it tells the two candidates apart not at all.P(actress | versatile) = .000021 وP(across | versatile) = .000021. الـ bigram الأيسر متعادل، فلا يميّز بين المرشّحين على الإطلاق.
• P(whose | actress) = .0010 and P(whose | across) = .000006. The right bigram is where the evidence lives: whose follows a person noun often and follows a preposition almost never.P(whose | actress) = .0010 وP(whose | across) = .000006. الـ bigram الأيمن هو مكان الدليل: تأتي whose كثيرًا بعد اسم يدل على شخص، ولا تأتي تقريبًا أبدًا بعد حرف جر.

The slides stop at the language model numbers. Jurafsky and Martin's appendix, where this example comes from, adds one sentence: combining the language model with the error model, the bigram noisy channel now chooses actress. That combining step multiplies by the channel term P(x|w). Here it is.

تتوقف الشرائح عند أرقام نموذج اللغة. أما ملحق Jurafsky and Martin، الذي أُخذ منه هذا المثال، فيضيف جملة واحدة: بدمج نموذج اللغة مع نموذج الخطأ، تختار القناة المشوشة ثنائية الكلمات الآن actress. وخطوة الدمج هذه تعني الضرب في حدّ القناة P(x|w). وإليك هذه الخطوة.