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

AOverviewنظرة عامة

This lecture takes one everyday tool, the spell checker, and uses it to teach the most reusable piece of probabilistic reasoning in classical NLP: the noisy channel model. You type acress, and the system has to decide what you meant. To do that it must find a short list of plausible words, ask how likely each one was to come out as acress, ask how likely each one was to be written at all, and multiply. Along the way the lecture shows why that simple product picks the wrong word, how context fixes it, and why errors that land on real words need a whole sentence to be found.

تأخذ هذه المحاضرة أداة نستخدمها كل يوم، وهي المدقق الإملائي (spell checker)، وتستعملها لتعليم أكثر أدوات الاستدلال الاحتمالي قابلية لإعادة الاستخدام في معالجة اللغة الطبيعية الكلاسيكية: نموذج القناة المشوشة (noisy channel model). تكتب acress، وعلى النظام أن يقرر ماذا كنت تقصد. ولكي يفعل ذلك عليه أن يجد قائمة قصيرة من الكلمات المعقولة، ثم يسأل: ما احتمال أن تخرج كل كلمة منها على شكل acress؟ وما احتمال أن تُكتب كل كلمة منها أصلًا؟ ثم يضرب الاحتمالين. وفي الطريق تبيّن المحاضرة لماذا يختار هذا الضرب البسيط الكلمة الخطأ، وكيف يصلح السياق ذلك، ولماذا تحتاج الأخطاء التي تقع على كلمات حقيقية إلى جملة كاملة لاكتشافها.

As a PhD student you need it in three places. Exam questions here are computational: name the edit behind a typo, read a confusion matrix cell in the right direction, fill in a channel times prior table with powers of ten, count candidate sentences in a lattice, and say what α or λ does to the winner. In research, the same decomposition of a hidden cause into a likelihood and a prior reappears in speech recognition, statistical machine translation and OCR post-correction, so being fluent with it lets you read those papers quickly. And any system you build on noisy user text, including Arabic or mixed-script input, needs a normalisation step whose errors you can explain and measure on a held-out test set.

بصفتك طالب دكتوراه تحتاج هذا الموضوع في ثلاثة مواضع. أسئلة الامتحان هنا حسابية: سمِّ التعديل (edit) الذي يقف خلف الخطأ الإملائي، واقرأ خلية مصفوفة الالتباس (confusion matrix) بالاتجاه الصحيح، واملأ جدول القناة مضروبة في الاحتمال المسبق (channel × prior) مع قوى العشرة، وعُدّ الجمل المرشحة في الشبكة (lattice)، وقل ماذا يفعل α أو λ بالكلمة الفائزة. وفي البحث العلمي، يتكرر التفكيك نفسه للسبب الخفي إلى احتمال مشروط (likelihood) واحتمال مسبق (prior) في التعرف على الكلام، والترجمة الآلية الإحصائية، وتصحيح مخرجات OCR، لذلك فإن إتقانه يتيح لك قراءة تلك الأوراق بسرعة. وأي نظام تبنيه على نصوص مستخدمين مليئة بالأخطاء، بما في ذلك النصوص العربية أو المختلطة الحروف، يحتاج إلى خطوة تطبيع (normalisation) تستطيع أن تفسر أخطاءها وتقيسها على مجموعة اختبار محجوزة (held-out test set).

The path has seven stops. You first separate non-word errors, which dictionary lookup catches, from real-word errors, which it cannot see. You model typing as a noisy channel and derive ŵ = argmax P(x|w) P(w) with Bayes' rule. You generate candidates by edit distance, then estimate the channel from the four confusion matrices of Kernighan, Church and Gale. You score acress with a unigram prior, watch it pick across, and let bigram context restore actress. You extend the model to whole sentences with a candidate lattice, the one-error assumption and the no-error probability α. Finally you see what real systems add: a weight λ on the prior, phonetic keys, richer edits, keyboard features and confusion-set classifiers.

للمسار سبع محطات. أولًا تفصل بين أخطاء الكلمات غير الموجودة (non-word errors)، التي يكشفها البحث في القاموس، وأخطاء الكلمات الحقيقية (real-word errors)، التي لا يراها القاموس. ثم تنمذج الكتابة على أنها قناة مشوشة وتشتق ŵ = argmax P(x|w) P(w) باستخدام قاعدة بايز (Bayes' rule). ثم تولّد المرشحين باستخدام مسافة التعديل (edit distance)، وتقدّر القناة من مصفوفات الالتباس الأربع لـ Kernighan وChurch وGale. بعدها تحسب درجات acress باحتمال مسبق أحادي (unigram prior)، فتراه يختار across، ثم تدع سياق الثنائيات (bigram) يعيد actress. ثم توسّع النموذج إلى جمل كاملة باستخدام شبكة المرشحين، وافتراض الخطأ الواحد (one-error assumption)، واحتمال عدم وجود خطأ α. وأخيرًا ترى ما تضيفه الأنظمة الحقيقية: وزنًا λ على الاحتمال المسبق، ومفاتيح صوتية (phonetic keys)، وتعديلات أغنى، وخصائص لوحة المفاتيح، ومصنفات مجموعات الالتباس (confusion-set classifiers).

Success looks likeعلامات النجاح

• Classify any misspelling as a non-word or real-word error, and a real-word error as typographical or cognitive, and explain why only the first kind is found by lookup.أن تصنّف أي خطأ إملائي على أنه خطأ كلمة غير موجودة أو خطأ كلمة حقيقية، وأن تصنّف خطأ الكلمة الحقيقية على أنه مطبعي (typographical) أو إدراكي (cognitive)، وأن تشرح لماذا لا يكشف البحث في القاموس إلا النوع الأول.
• Derive ŵ = argmax P(x|w) P(w) from argmax P(w|x) line by line, say why P(x) can be dropped, and name each factor.أن تشتق ŵ = argmax P(x|w) P(w) من argmax P(w|x) سطرًا بسطر، وأن تقول لماذا يمكن حذف P(x)، وأن تسمّي كل عامل.
• Generate the candidates of a typo with Damerau-Levenshtein edits, label each edit from the typist's side, and count edit-1 strings with 54n + 25.أن تولّد مرشحي خطأ إملائي باستخدام تعديلات Damerau-Levenshtein، وأن تسمّي كل تعديل من جهة الكاتب، وأن تعدّ السلاسل التي تبعد تعديلًا واحدًا بالصيغة 54n + 25.
• Write the Kernighan, Church and Gale formula for P(x|w) with the right cell and denominator for deletion, insertion, substitution and transposition.أن تكتب صيغة Kernighan وChurch وGale لـ P(x|w) بالخلية والمقام الصحيحين للحذف (deletion) والإدراج (insertion) والاستبدال (substitution) والتبديل (transposition).
• Fill in the acress table with unigram and bigram priors, state the winner and the margin each time, and avoid counting P(w) twice.أن تملأ جدول acress باحتمالات مسبقة أحادية وثنائية، وأن تذكر الفائز والفارق في كل مرة، وأن تتجنب حساب P(w) مرتين.
• Build the candidate lattice for a short sentence, count the full and one-error candidate sentences, and decide the thew example for a given α.أن تبني شبكة المرشحين لجملة قصيرة، وأن تعدّ الجمل المرشحة في الشبكة الكاملة وفي حالة الخطأ الواحد، وأن تحسم مثال thew لقيمة معطاة من α.
• Explain what λ, Metaphone keys, multi-letter edits, keyboard features and confusion-set classifiers each add to the basic model.أن تشرح ما يضيفه كل من λ، ومفاتيح Metaphone، والتعديلات متعددة الحروف، وخصائص لوحة المفاتيح، ومصنفات مجموعات الالتباس إلى النموذج الأساسي.

How to study this lectureكيف تذاكر هذه المحاضرة

1. Choose your route. Read the full guide in one sitting for the big picture, or work through one part at a time when you want depth. Parts 02 to 05 (the model, candidates, the two factors, scoring) form one natural session, and parts 06 and 07 (real-word errors) another.اختر طريقك. اقرأ الدليل الكامل في جلسة واحدة لترى الصورة الكبيرة، أو اعمل على جزء واحد في كل مرة عندما تريد العمق. الأجزاء من 02 إلى 05 (النموذج، والمرشحون، والعاملان، والتقييم) تشكّل جلسة واحدة طبيعية، والجزءان 06 و07 (أخطاء الكلمات الحقيقية) جلسة أخرى.
2. Answer every recall prompt in your head, or on paper, before you reveal it. Confusion matrix indices and powers of ten only stick once you have written them yourself.أجب عن كل سؤال استرجاع في ذهنك أو على الورق قبل أن تكشف الإجابة. فمؤشرات مصفوفة الالتباس وقوى العشرة لا تثبت إلا بعد أن تكتبها بنفسك.
3. Take each quiz and read the explanation even when you are right. The explanations carry the distinctions an examiner probes, such as typed versus intended in x|w.حلّ كل اختبار قصير واقرأ الشرح حتى عندما تكون إجابتك صحيحة. فالشروح تحمل الفروق التي يختبرها الممتحن، مثل الفرق بين المكتوب والمقصود في x|w.
4. Use the interactive pieces: run the candidate generator on your own typos, look up channel cells, re-score acress, and move α and λ until the winner flips.استخدم الأجزاء التفاعلية: شغّل مولّد المرشحين على أخطائك الإملائية، وابحث عن خلايا القناة، وأعد حساب درجات acress، وحرّك α وλ حتى يتغير الفائز.
5. Mark a concept as understood only when you could explain it to a classmate without looking. Unmarked concepts show you where to return.لا تعلّم مفهومًا على أنه مفهوم إلا عندما تستطيع شرحه لزميل دون أن تنظر. والمفاهيم غير المعلّمة تريك أين يجب أن تعود.
6. Keep the glossary and the reference sheet open as you revise. The reference sheet collects every formula, table and slide correction on one printable page.أبقِ المسرد (glossary) وورقة المراجعة مفتوحين أثناء المراجعة. تجمع ورقة المراجعة كل صيغة وجدول وتصحيح للشرائح في صفحة واحدة قابلة للطباعة.
7. Come back after a few days and retry the recall prompts and quizzes cold. Spaced practice builds the long-term memory an exam needs.عد بعد بضعة أيام وأعد محاولة أسئلة الاسترجاع والاختبارات القصيرة دون تحضير. فالتدريب المتباعد يبني الذاكرة طويلة المدى التي يحتاجها الامتحان.

BThe 8 partsالأجزاء الـ8

1. 01Spelling tasks and the two kinds of errorsمهام الإملاء ونوعا الأخطاءWhere spelling correction shows up, detection versus correction, the non-word versus real-word split, how often people actually misspell, and the outline of how each kind of error is fixed.أين يظهر التصحيح الإملائي، والاكتشاف مقابل التصحيح، والتقسيم بين أخطاء الكلمات غير الموجودة وأخطاء الكلمات الحقيقية، وكم مرة يخطئ الناس فعلا في الإملاء، وخطوط عريضة لكيفية إصلاح كل نوع.6 concepts6 مفاهيمSlides 1-8الشرائح 1-836 min36 دقيقة
   1. 1.1Spelling correction in the tools you already useتصحيح الإملاء في الأدوات التي تستخدمها أصلا
   2. 1.2Detection versus correction, and how much to trust the fixالكشف مقابل التصحيح، ومقدار الثقة في الإصلاح
   3. 1.3Non-word and real-word errorsأخطاء الكلمات غير الموجودة وأخطاء الكلمات الحقيقية
   4. 1.4How often people misspell, and why the numbers disagreeكم مرة يخطئ الناس في الإملاء، ولماذا تختلف الأرقام
   5. 1.5The pipeline for non-word errorsخط المعالجة لأخطاء الكلمات غير الموجودة
   6. 1.6The pipeline for real-word errorsخط المعالجة لأخطاء الكلمات الحقيقية
2. 02The noisy channel modelنموذج القناة المشوشة (Noisy channel)Treat the misspelling as a correct word sent through a noisy channel, then decode with Bayes' rule: pick the word that maximizes channel probability times prior.نعامل الخطأ الإملائي على أنه كلمة صحيحة أُرسلت عبر قناة مشوشة، ثم نفك الترميز بقاعدة Bayes: نختار الكلمة التي تعظّم احتمال القناة مضروبا في الاحتمال المسبق (prior).3 concepts3 مفاهيمSlides 9-12الشرائح 9-1218 min18 دقيقة
   1. 2.1A misspelling as a word sent through a noisy channelالخطأ الإملائي كلمة أُرسلت عبر قناة مشوّشة
   2. 2.2Deriving the decoding rule: argmax P(x|w) P(w)اشتقاق قاعدة فك الترميز: argmax P(x|w) P(w)
   3. 2.3Where the model came from and where else it worksمن أين جاء النموذج وأين يعمل أيضًا
3. 03Generating candidates with edit distanceتوليد المرشحين بمسافة التحريرTurning a misspelling like acress into a short list of real words: Damerau-Levenshtein edits of distance one, the four edit types, and why distance one or two is enough.تحويل خطأ مثل acress إلى قائمة قصيرة من الكلمات الحقيقية: تعديلات Damerau-Levenshtein بمسافة واحد، وأنواع التعديل الأربعة، ولماذا تكفي المسافة واحد أو اثنان.3 concepts3 مفاهيمSlides 13-16الشرائح 13-1618 min18 دقيقة
   1. 3.1Where candidates come from: similar spelling, similar soundمن أين يأتي المرشحون: تهجئة متشابهة، ونطق متشابه
   2. 3.2The four edits and the acress tableالتعديلات الأربعة وجدول acress
   3. 3.3Why one or two edits is enough, and why the dictionary does the workلماذا يكفي تعديل واحد أو تعديلان، ولماذا يقوم القاموس بالعمل
4. 04The prior and the channel modelالاحتمال المسبق (Prior) ونموذج القناةEstimating the two factors: P(w) from corpus counts, and P(x|w) from the Kernighan, Church and Gale confusion matrices for deletion, insertion, substitution and transposition.تقدير العاملين: P(w) من عدّ المدونة، وP(x|w) من مصفوفات الالتباس لـ Kernighan وChurch وGale للحذف والإدراج والاستبدال والتبديل (transposition).3 concepts3 مفاهيمSlides 17-24الشرائح 17-2418 min18 دقيقة
   1. 4.1The prior: how common is each candidateالاحتمال المسبق: ما مدى شيوع كل مرشح
   2. 4.2The channel model and its four confusion matricesنموذج القناة ومصفوفات الالتباس الأربع
   3. 4.3From confusion counts to P(x|w): the formula on acressمن عدّات الالتباس إلى P(x|w): الصيغة مطبّقة على acress
5. 05Scoring acress: unigram vs bigram contextتقييم acress: سياق unigram مقابل bigramMultiply channel and prior for every candidate, see the unigram model pick across, then watch a bigram context flip the answer to actress, and how such systems are evaluated.نضرب احتمال القناة في الاحتمال المسبق لكل مرشح، فنرى نموذج unigram يختار across، ثم نشاهد سياق bigram يقلب الإجابة إلى actress، وكيف تُقيَّم مثل هذه الأنظمة.3 concepts3 مفاهيمSlides 25-29الشرائح 25-2918 min18 دقيقة
   1. 5.1Scoring every candidate: channel times unigram priorتقييم كل مرشّح: احتمال القناة مضروبًا في الاحتمال المسبق أحادي الكلمة
   2. 5.2Context flips the answer: a bigram prior picks actressالسياق يقلب الإجابة: الاحتمال المسبق ثنائي الكلمات يختار actress
   3. 5.3Evaluating a corrector on lists of real misspellingsتقييم المصحّح على قوائم أخطاء إملائية حقيقية
6. 06Real-word spelling errorsأخطاء الكلمات الحقيقيةErrors that are themselves dictionary words, why they are common, and the candidate-set recipe that treats every word in the sentence as possibly wrong.أخطاء تكون هي نفسها كلمات موجودة في القاموس، ولماذا هي شائعة، وطريقة مجموعة المرشحين التي تعامل كل كلمة في الجملة على أنها قد تكون خاطئة.3 concepts3 مفاهيمSlides 30-33الشرائح 30-3318 min18 دقيقة
   1. 6.1Typos that are real words, and why a dictionary cannot see themأخطاء مطبعية تنتج كلمات حقيقية، ولماذا لا يراها القاموس
   2. 6.2Candidate sets that keep the original wordمجموعات المرشحين التي تُبقي الكلمة الأصلية
   3. 6.3Choosing the best sentence, not the best wordاختيار أفضل جملة، لا أفضل كلمة
7. 07The candidate lattice, one error per sentence, and P(w|w)شبكة المرشحين وخطأ واحد في الجملة وP(w|w)Searching the candidate lattice for 'two of thew', the one-error-per-sentence simplification, the channel probability of typing a word correctly, and Norvig's thew example.البحث في شبكة المرشحين لعبارة two of thew، وتبسيط خطأ واحد في كل جملة، واحتمال القناة لكتابة الكلمة بشكل صحيح، ومثال thew عند Norvig.4 concepts4 مفاهيمSlides 34-39الشرائح 34-3924 min24 دقيقة
   1. 7.1The candidate lattice: every path is a sentenceشبكة المرشحات: كل مسار جملة
   2. 7.2One error per sentence: from 48 sentences to 9خطأ واحد في كل جملة: من 48 جملة إلى 9
   3. 7.3The probability of no error, P(w|w) = αاحتمال عدم الخطأ، P(w|w) = α
   4. 7.4Norvig's thew table: a word scored against itselfجدول Norvig لكلمة thew: كلمة تُقارَن بنفسها
8. 08State-of-the-art spelling systemsأنظمة الإملاء الحديثةWhat real systems add: confidence-driven HCI, weighting the language model with lambda, phonetic (Metaphone) error models, richer edits, keyboard and context features in the channel, and classifiers for confusable pairs.ما تضيفه الأنظمة الحقيقية: تفاعل بين الإنسان والحاسب (HCI) قائم على الثقة، وترجيح نموذج اللغة بـ lambda، ونماذج الأخطاء الصوتية (Metaphone)، والتعديلات الأغنى، وخصائص لوحة المفاتيح والسياق في القناة، والمصنِّفات للأزواج الملتبسة.5 concepts5 مفاهيمSlides 40-48الشرائح 40-4830 min30 دقيقة
   1. 8.1Confidence decides what the interface doesالثقة تحدد ما تفعله الواجهة
   2. 8.2Weighting the prior with lambdaوزن الاحتمال المسبق بـ lambda
   3. 8.3Finding candidates by sound with Metaphoneإيجاد المرشحين بالصوت باستخدام Metaphone
   4. 8.4Richer channel models: multi-letter edits, keys and soundنماذج قناة أغنى: تعديلات متعددة الحروف، والمفاتيح، والصوت
   5. 8.5Classifiers for confusable pairsمصنّفات للأزواج القابلة للالتباس

CGlossary and referenceالمصطلحات والمرجع

• GlossaryالمصطلحاتEvery term from the lecture, defined once, with links back to the slides that use it.كل مصطلح في المحاضرة معرّف مرة واحدة، مع روابط تعيدك إلى الشرائح التي تستخدمه.
• Reference sheetالورقة المرجعيةThe lecture on one printable page, for revision before a quiz or exam.المحاضرة كاملة في صفحة واحدة قابلة للطباعة، للمراجعة قبل الاختبار القصير أو الامتحان.