The noisy channel modelنموذج القناة المشوشة (Noisy channel)

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 توسّع حاصل الضرب نفسه ليشمل السياق والأنظمة الحقيقية.