ICS 582Lecture 05المحاضرة 05Part 07الجزء 07
The 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.
- Conceptsالمفاهيم
- 4
- Slidesالشرائح
- 34-39
- Readingمدة القراءة
- 24 min24 دقيقة
Why this part mattersلماذا يهمّ هذا الجزء
A non-word like acress announces itself: it is not in the dictionary, so you know where the error is and only have to pick the fix. A Real-word error gives no such signal. In two of thew apples, every word is a real English word, so any of them might be the mistake, and any of them might be exactly what the writer meant.
This part turns that problem into a search you can draw and count. First, a lattice that lays out every sentence the writer might have meant. Second, the one-error simplification that cuts that search from a product to a sum. Third, the one probability the real-word channel needs that the non-word channel never did: the chance that a word was typed correctly. Fourth, Norvig's thew table, where that chance meets real numbers. On the exam, expect to count candidate sentences, to interpret a value of α, and to multiply out a row of the table. For your own work, this is the cleanest small example of a design choice that every noisy channel system has to make: how much to trust the input as it is.
كلمة غير موجودة مثل acress تكشف نفسها بنفسها: هي ليست في القاموس، فأنت تعرف مكان الخطأ ولا يبقى عليك إلا اختيار التصحيح. أما real-word error (خطأ الكلمة الحقيقية) فلا يعطي أي إشارة من هذا النوع. في two of thew apples كل كلمة هي كلمة إنجليزية حقيقية، فقد تكون أي واحدة منها هي الخطأ، وقد تكون أي واحدة منها هي بالضبط ما قصده الكاتب.
هذا الجزء يحوّل تلك المشكلة إلى بحث يمكنك رسمه وعدّه. أولا، شبكة (lattice) تعرض كل جملة ربما قصدها الكاتب. ثانيا، تبسيط الخطأ الواحد (one-error) الذي يقلّص هذا البحث من حاصل ضرب إلى مجموع. ثالثا، الاحتمال الوحيد الذي تحتاجه قناة الكلمات الحقيقية ولم تحتجه قناة الكلمات غير الموجودة أبدا: احتمال أن الكلمة كُتبت صحيحة. رابعا، جدول Norvig لكلمة thew، حيث يلتقي هذا الاحتمال بأرقام حقيقية. في الامتحان، توقّع أن يُطلب منك عدّ الجمل المرشحة، وتفسير قيمة α، وحساب صف من الجدول بالضرب. وفي عملك الخاص، هذا أوضح مثال صغير على قرار تصميمي لا بد أن يتخذه كل نظام قناة صاخبة (noisy channel): إلى أي حد تثق في المدخل كما هو.
By the end you canفي نهاية هذا الجزء ستستطيع
- Draw the candidate lattice for a short sentence and read every path through it as one candidate sentence.رسم شبكة المرشحات (candidate lattice) لجملة قصيرة، وقراءة كل مسار فيها على أنه جملة مرشحة واحدة.
- Count the candidate sentences in the full lattice (a product) and under the one-error assumption (a sum), and explain why the assumption is needed.عدّ الجمل المرشحة في الشبكة الكاملة (حاصل ضرب) وتحت افتراض الخطأ الواحد (one-error، مجموع)، وشرح سبب الحاجة إلى هذا الافتراض.
- Explain where the two probabilities of the real-word noisy channel come from, and why it needs a new term, P(w|w).شرح مصدر الاحتمالين في القناة الصاخبة (noisy channel) لأخطاء الكلمات الحقيقية، ولماذا تحتاج إلى حد جديد هو P(w|w).
- Translate a value of α such as .95 or .99 into an error rate in words, and say who chooses it.تحويل قيمة α مثل .95 أو .99 إلى معدل أخطاء بالكلمات، وتحديد من يختارها.
- Rebuild Norvig's thew table: name each edit, multiply channel by prior, and decide when thew itself would win.إعادة بناء جدول Norvig لكلمة thew: تسمية كل تعديل، وضرب احتمال القناة في الاحتمال المسبق (prior)، وتحديد متى تفوز thew نفسها.
Take the typed phrase two of thew and, for each word on its own, write down every word the writer might have intended. Under two: to, tao, too and two itself. Under of: off, on, of. Under thew: threw, thaw, the and thew.
خذ العبارة المكتوبة two of thew، ولكل كلمة على حدة اكتب كل كلمة ربما قصدها الكاتب. تحت two: to وtao وtoo وtwo نفسها. تحت of: off وon وof. تحت thew: threw وthaw وthe وthew.
Each list is that word's Candidate set: real words within one edit, plus homophones such as too for two, plus the typed word itself. Now put the lists side by side as columns and connect every node in one column to every node in the next. The result is the Candidate lattice. Its key property is simple: pick one node per column, left to right, and you have spelled out one possible intended sentence. two of the is one path. too off thaw is another. The corrector's job is to find the path with the highest noisy channel score.
كل قائمة هي candidate set (مجموعة المرشحات) لتلك الكلمة: الكلمات الحقيقية التي تبعد تعديلا واحدا، مع الكلمات المتشابهة في النطق (homophones) مثل too بدل two، مع الكلمة المكتوبة نفسها. الآن ضع القوائم جنبا إلى جنب على شكل أعمدة، واربط كل عقدة في عمود بكل عقدة في العمود التالي. النتيجة هي candidate lattice (شبكة المرشحات). خاصيتها الأساسية بسيطة: اختر عقدة واحدة من كل عمود، من اليسار إلى اليمين، وستكون قد كتبت جملة واحدة محتملة قصدها الكاتب. two of the مسار واحد، وtoo off thaw مسار آخر. مهمة المصحِّح هي إيجاد المسار الذي له أعلى درجة في القناة الصاخبة (noisy channel).
The best path the lecture highlights is two of the. Notice what that path does: it keeps two and of exactly as typed and changes only thew. That is why each candidate set must contain the typed word itself. If two were missing from its own column, the lattice could not express “this word was fine”, and every path would be forced to change every word.
أفضل مسار تبرزه المحاضرة هو two of the. لاحظ ما يفعله هذا المسار: يُبقي two وof كما كُتبتا تماما، ويغيّر thew فقط. لهذا يجب أن تحتوي كل مجموعة مرشحات على الكلمة المكتوبة نفسها. لو غابت two عن عمودها، لما استطاعت الشبكة أن تعبّر عن أن «هذه الكلمة كانت سليمة»، ولاضطر كل مسار إلى تغيير كل كلمة.
Recall
Why must every column of the lattice contain the word that was actually typed?لماذا يجب أن يحتوي كل عمود في الشبكة على الكلمة التي كُتبت فعلا؟
Because most words in a sentence are correct. A path that keeps a word unchanged has to pass through that word's own node. Without it, the lattice could only produce sentences in which that word was an error.
لأن معظم الكلمات في الجملة صحيحة. المسار الذي يُبقي كلمة دون تغيير لا بد أن يمر بعقدة تلك الكلمة نفسها. وبدونها لن تنتج الشبكة إلا جملا تكون فيها تلك الكلمة خطأ.
Count the paths in the lattice above. There are 4 choices in the first column, 3 in the second and 4 in the third, and any choice can follow any other, so there are 4 × 3 × 4 = 48 candidate sentences for a three-word phrase.
عُدّ المسارات في الشبكة السابقة. هناك 4 خيارات في العمود الأول، و3 في الثاني، و4 في الثالث، وأي خيار يمكن أن يتبعه أي خيار آخر، فيكون عدد الجمل المرشحة 4 × 3 × 4 = 48 لعبارة من ثلاث كلمات.
That product is the problem. Add only at the front and apples at the end, as slide 36 does, and you multiply again by the size of each new set. A twenty-word sentence with four candidates per word has 4²⁰ ≈ 1.1 × 10¹² paths. Each one needs a language model score, so the full search is hopeless, and most of those sentences assume the writer made many errors at once, which is rare.
حاصل الضرب هذا هو المشكلة. أضف only في البداية وapples في النهاية، كما تفعل الشريحة 36، فتضرب مرة أخرى في حجم كل مجموعة جديدة. جملة من عشرين كلمة بأربعة مرشحات لكل كلمة لها 4²⁰ ≈ 1.1 × 10¹² مسارا. كل مسار يحتاج إلى درجة من النموذج اللغوي، فالبحث الكامل ميؤوس منه، كما أن معظم تلك الجمل تفترض أن الكاتب ارتكب أخطاء كثيرة في وقت واحد، وهذا نادر.
The simplificationالتبسيط
The One error per sentence assumption assumption, from Mays, Damerau and Mercer (1991), keeps only sentences that differ from the typed one in at most one word. In the lattice, that means a path may leave the typed node in at most one column. For two of thew:
افتراض one error per sentence (خطأ واحد في كل جملة)، من Mays وDamerau وMercer (1991)، يُبقي فقط الجمل التي تختلف عن الجملة المكتوبة في كلمة واحدة على الأكثر. في الشبكة، يعني ذلك أن المسار يجوز له أن يترك العقدة المكتوبة في عمود واحد على الأكثر. بالنسبة لـ two of thew:
- The typed sentence itself, unchanged: two of thew. That is 1.الجملة المكتوبة نفسها دون تغيير: two of thew. هذه 1.
- Change only the first word: to, tao, too. That is 3, for example too of thew (slide notation w‴₁ w₂ w₃).تغيير الكلمة الأولى فقط: to وtao وtoo. هذه 3، مثل too of thew (بترميز الشريحة w‴₁ w₂ w₃).
- Change only the second word: off, on. That is 2, for example two off thew (w₁ w″₂ w₃).تغيير الكلمة الثانية فقط: off وon. هذه 2، مثل two off thew (w₁ w″₂ w₃).
- Change only the third word: threw, thaw, the. That is 3, for example two of the (w₁ w₂ w′₃).تغيير الكلمة الثالثة فقط: threw وthaw وthe. هذه 3، مثل two of the (w₁ w₂ w′₃).
The twenty-word example drops from about 10¹² sentences to 1 + 20 × 3 = 61. The primes in the slide's notation only mark which position was replaced; w″₂ is “some other candidate for the second word”, not a second derivative or a second error.
مثال العشرين كلمة ينخفض من نحو 10¹² جملة إلى 1 + 20 × 3 = 61. علامات الشَّرطة (primes) في ترميز الشريحة تحدد فقط أي موضع استُبدل، فـ w″₂ تعني «مرشحا آخر للكلمة الثانية»، وليست مشتقة ثانية ولا خطأ ثانيا.
Quick checkاختبار سريع
Candidate sets for two, of and thew have sizes 4, 3 and 4. Under one error per sentence, how many candidate sentences are scored?أحجام مجموعات المرشحات لـ two وof وthew هي 4 و3 و4. تحت افتراض خطأ واحد في كل جملة، كم جملة مرشحة تُحسب درجتها؟
Recall
Why does the one-error assumption turn a product into a sum?لماذا يحوّل افتراض الخطأ الواحد حاصل الضرب إلى مجموع؟
In the full lattice every column varies independently, so the choices multiply. With at most one change, only one column varies in any sentence, so you count each column's alternatives separately and add them, then add the one sentence where nothing changes.
في الشبكة الكاملة يتغير كل عمود باستقلال عن غيره، فتتضاعف الخيارات بالضرب. ومع تغيير واحد على الأكثر، لا يتغير في أي جملة إلا عمود واحد، فتعدّ بدائل كل عمود على حدة وتجمعها، ثم تضيف الجملة الواحدة التي لا يتغير فيها شيء.
Score two of the nine sentences: two of the and two of thew. The first changes thew into the, so its channel term is the probability of that edit, which the confusion matrices already give you. The second changes nothing. What channel probability belongs to “the writer meant thew and typed thew”?
احسب درجة جملتين من الجمل التسع: two of the وtwo of thew. الأولى تغيّر thew إلى the، فحد القناة فيها هو احتمال ذلك التعديل، وهذا تعطيك إياه مصفوفات الالتباس (confusion matrices) مسبقا. الثانية لا تغيّر شيئا. فما احتمال القناة المناسب لحالة «الكاتب قصد thew وكتب thew»؟
For non-word errors this question never came up: the typed string was not a word, so it could not be the answer. With real words it is the most important candidate of all, because most typed words are correct. So the two probabilities of the noisy channel are filled in as follows.
في أخطاء الكلمات غير الموجودة لم يُطرح هذا السؤال أبدا: النص المكتوب لم يكن كلمة، فلا يمكن أن يكون هو الجواب. أما مع الكلمات الحقيقية فهو أهم مرشح على الإطلاق، لأن معظم الكلمات المكتوبة صحيحة. لذلك يُملأ احتمالا القناة الصاخبة على النحو الآتي.
| Termالحد | What it measuresما الذي يقيسه | Where it comes fromمن أين يأتي |
|---|---|---|
| P(W), the language modelP(W)، النموذج اللغوي | How likely the whole candidate sentence isمدى احتمال الجملة المرشحة كاملة | Unigram, bigram or trigram counts from a corpus, smoothed (for example with stupid backoff)عدّات unigram أو bigram أو trigram من مدوّنة، مع التنعيم (مثلا بطريقة stupid backoff) |
| P(x|w), x different from wP(x|w)، حيث x تختلف عن w | How likely the typist turned w into xمدى احتمال أن يحوّل الكاتب w إلى x | The same confusion-matrix channel as for non-word errors (Kernighan, Church and Gale)قناة مصفوفة الالتباس نفسها المستخدمة لأخطاء الكلمات غير الموجودة (Kernighan وChurch وGale) |
| P(w|w), the new termP(w|w)، الحد الجديد | How likely the typist typed w correctlyمدى احتمال أن يكتب الكاتب w صحيحة | Not counted from a corpus. Chosen per application, called αلا تُعدّ من مدوّنة. تُختار لكل تطبيق، وتُسمى α |
The Prior probability is any language model you already know: a Unigram prior in the slide's table, or a Bigram language model or trigram over the whole sentence in practice. The Channel model for an actual edit is the same one used for non-words, built from the Kernighan, Church and Gale channel model confusion matrices. The one new value is the Probability of no error, written P(w|w) and usually called α.
prior probability (الاحتمال المسبق) هو أي نموذج لغوي تعرفه: unigram prior في جدول الشريحة، أو bigram language model أو trigram على الجملة كلها في التطبيق العملي. وchannel model (نموذج القناة) للتعديل الفعلي هو نفسه المستخدم للكلمات غير الموجودة، والمبني من مصفوفات الالتباس في Kernighan, Church and Gale. القيمة الجديدة الوحيدة هي probability of no error (احتمال عدم الخطأ)، وتُكتب P(w|w) وتُسمى عادة α.
Who sets α, and what it meansمن يحدد α، وماذا تعني
Ask what P(the|the) should be. There is no corpus count for it; it is a statement about the typist. If people mistype one word in twenty, then a given word comes out as intended with probability 19/20 = .95. In general, α = 1 − error rate, and an error rate of one in N words gives α = 1 − 1/N.
اسأل نفسك: كم يجب أن تكون P(the|the)؟ لا يوجد لها عدّ في المدوّنة (corpus)، فهي عبارة عن وصف للشخص الذي يكتب. إذا كان الناس يخطئون في كلمة واحدة من كل عشرين، فإن أي كلمة تخرج كما قُصدت باحتمال 19/20 = .95. وبشكل عام α = 1 − error rate، ومعدل خطأ قدره واحد في كل N كلمة يعطي α = 1 − 1/N.
| α = P(w|w)α = P(w|w) | Errorsالأخطاء | 1 − α1 − α | Might suit, for exampleقد تناسب، على سبيل المثال |
|---|---|---|---|
| .90.90 | 1 in 10خطأ واحد في كل 10 | 0.100.10 | Fast chat typing on a phone, no proofreadingالكتابة السريعة في المحادثات على الجوال، دون مراجعة |
| .95.95 | 1 in 20خطأ واحد في كل 20 | 0.050.05 | Norvig's and SLP3's choice for web textاختيار Norvig وSLP3 لنصوص الويب |
| .99.99 | 1 in 100خطأ واحد في كل 100 | 0.010.01 | Careful drafting, such as a thesis chapterالكتابة المتأنية، مثل فصل من رسالة دكتوراه |
| .995.995 | 1 in 200خطأ واحد في كل 200 | 0.0050.005 | Edited, proofread text such as a published bookنص محرَّر ومُراجَع، مثل كتاب منشور |
The slide's own phrase is “obviously this depends on the application”. The same corrector should behave differently on hasty phone messages and on a proofread manuscript, and α is the knob that says which one it is looking at. A low α tells the system that errors are common, so it is quick to change words. A high α tells it to trust the input, so a change has to be strongly supported by the language model.
عبارة الشريحة نفسها هي «من الواضح أن هذا يعتمد على التطبيق» (obviously this depends on the application). المصحِّح نفسه يجب أن يتصرف بشكل مختلف مع رسائل الجوال المكتوبة على عجل ومع مخطوطة مُراجَعة، وα هي المفتاح الذي يخبره بأيهما يتعامل. قيمة α المنخفضة تخبر النظام أن الأخطاء شائعة، فيسارع إلى تغيير الكلمات. وقيمة α المرتفعة تخبره أن يثق في المدخل، فلا يحدث التغيير إلا إذا دعمه النموذج اللغوي بقوة.
Mays and colleagues first split 1 − α evenly among the other candidates. SLP3 replaces the even split with the confusion-matrix edit probabilities. Either way, the probabilities over all ways of typing w add up to one: α for no error, 1 − α for all errors together. Keep that sum in mind; it decides the puzzle at the end of this part.
وزّع Mays وزملاؤه في البداية 1 − α بالتساوي على المرشحات الأخرى. ثم استبدل SLP3 التوزيع المتساوي باحتمالات التعديل من مصفوفات الالتباس. وفي الحالتين، مجموع الاحتمالات على كل طرق كتابة w يساوي واحدا: α لعدم الخطأ، و1 − α لكل الأخطاء مجتمعة. احفظ هذا المجموع في ذهنك، فهو الذي يحسم اللغز في نهاية هذا الجزء.
Quick checkاختبار سريع
A system sets P(w|w) to .99. What does that say about the text it expects?نظام يضبط P(w|w) على .99. ماذا يقول ذلك عن النص الذي يتوقعه؟
Recall
Why did non-word correction never need P(w|w), while real-word correction does?لماذا لم يحتج تصحيح الكلمات غير الموجودة إلى P(w|w) أبدا، بينما يحتاجه تصحيح الكلمات الحقيقية؟
A non-word cannot be the intended word, so the typed string is never a candidate. A real word can be exactly what the writer meant, so it competes with its corrections and needs its own channel probability: the chance that it was typed without error.
الكلمة غير الموجودة لا يمكن أن تكون الكلمة المقصودة، فالنص المكتوب لا يكون مرشحا أبدا. أما الكلمة الحقيقية فقد تكون بالضبط ما قصده الكاتب، فهي تتنافس مع تصحيحاتها وتحتاج إلى احتمال قناة خاص بها: احتمال أنها كُتبت دون خطأ.
Peter Norvig worked this exact case. For the typed word x = thew he lists five intended words w: thew itself (an old word for muscle or sinew), and one candidate for each kind of single edit. For each, multiply the channel probability by a unigram prior.
عمل Peter Norvig على هذه الحالة بالذات. للكلمة المكتوبة x = thew يذكر خمس كلمات مقصودة w: thew نفسها (كلمة قديمة تعني العضلة أو الوتر)، ومرشحا واحدا لكل نوع من أنواع التعديل الواحد. لكل منها، اضرب احتمال القناة في احتمال مسبق من نوع unigram.
| ww | x|wx|w | Editالتعديل | P(x|w)P(x|w) | P(w)P(w) | 10⁹ P(x|w) P(w)10⁹ P(x|w) P(w) |
|---|---|---|---|---|---|
| thethe | ew|eew|e | Insertion: w typed after eإدراج (insertion): كُتبت w بعد e | 0.0000070.000007 | 0.020.02 | 140 (slide: 144)140 (في الشريحة: 144) |
| thewthew | noneلا يوجد | No edit: typed as intendedلا تعديل: كُتبت كما قُصدت | α = 0.95α = 0.95 | 0.000000090.00000009 | 85.5 (slide: 90)85.5 (في الشريحة: 90) |
| thawthaw | e|ae|a | Substitution: e typed for aاستبدال (substitution): كُتبت e مكان a | 0.0010.001 | 0.00000070.0000007 | 0.70.7 |
| threwthrew | h|hrh|hr | Deletion: r dropped after hحذف (deletion): سقطت r بعد h | 0.0000080.000008 | 0.0000040.000004 | 0.032 (slide: 0.03)0.032 (في الشريحة: 0.03) |
| thwethwe | ew|weew|we | Transposition: we typed as ewتبديل موضعين (transposition): كُتبت we على شكل ew | 0.0000030.000003 | 0.000000040.00000004 | 0.00012 (slide: 0.0001)0.00012 (في الشريحة: 0.0001) |
The x|w column uses the confusion-matrix notation: typed letters on the left, intended letters on the right. ew|e means the writer intended e and typed ew, an Insertion of w after e. e|a is a Substitution. h|hr means hr was intended and only h typed, a Deletion of r. ew|we is a Transposition. Each edit is conditioned on the letter before it, which is why ew|e carries the e along.
عمود x|w يستخدم ترميز مصفوفة الالتباس: الحروف المكتوبة على اليسار، والحروف المقصودة على اليمين. ew|e تعني أن الكاتب قصد e وكتب ew، أي insertion (إدراج) لـ w بعد e. وe|a هي substitution (استبدال). وh|hr تعني أن hr كانت مقصودة ولم يُكتب إلا h، أي deletion (حذف) لـ r. وew|we هي transposition (تبديل موضعين متجاورين). كل تعديل مشروط بالحرف الذي قبله، ولهذا تحمل ew|e الحرف e معها.
Worked exampleمثال محلول
Scoring the two leaders at α = .95حساب درجة المتصدّرَين عند α = .95
The candidate theالمرشح the
P(thew|the) × P(the) = 0.000007 × 0.02 = 1.4 × 10⁻⁷, which is 140 after scaling by 10⁹. The edit is rare, but the is the most common word in English.
P(thew|the) × P(the) = 0.000007 × 0.02 = 1.4 × 10⁻⁷، أي 140 بعد الضرب في 10⁹. التعديل نادر، لكن the هي أكثر كلمة شيوعا في الإنجليزية.
The candidate thewالمرشح thew
P(thew|thew) × P(thew) = 0.95 × 0.00000009 = 8.55 × 10⁻⁸, which is 85.5. The channel is generous (no edit happened), but the word is rare.
P(thew|thew) × P(thew) = 0.95 × 0.00000009 = 8.55 × 10⁻⁸، أي 85.5. القناة سخية (لم يحدث أي تعديل)، لكن الكلمة نادرة.
The restالبقية
thaw: 0.001 × 7 × 10⁻⁷ = 7 × 10⁻¹⁰ (0.7). threw: 8 × 10⁻⁶ × 4 × 10⁻⁶ = 3.2 × 10⁻¹¹ (0.032). thwe: 3 × 10⁻⁶ × 4 × 10⁻⁸ = 1.2 × 10⁻¹³ (0.00012).
thaw: 0.001 × 7 × 10⁻⁷ = 7 × 10⁻¹⁰ (0.7). threw: 8 × 10⁻⁶ × 4 × 10⁻⁶ = 3.2 × 10⁻¹¹ (0.032). thwe: 3 × 10⁻⁶ × 4 × 10⁻⁸ = 1.2 × 10⁻¹³ (0.00012).
Resultالنتيجة
the wins with 140 against 85.5, a ratio of about 1.6. The corrector rewrites two of thew as two of the, the best path of slide 35.تفوز the بـ 140 مقابل 85.5، أي بنسبة تقارب 1.6. فيعيد المصحِّح كتابة two of thew على أنها two of the، وهو أفضل مسار في الشريحة 35.
Could a different α make thew win?هل يمكن لقيمة مختلفة من α أن تجعل thew تفوز؟
Read the formula naively, with the edit probabilities held fixed and only α moving. thew wins when α × 9 × 10⁻⁸ > 1.4 × 10⁻⁷, which needs α > 1.56. A probability cannot exceed one, so under that reading the wins for every α.
اقرأ الصيغة قراءة ساذجة، مع تثبيت احتمالات التعديل وتحريك α وحدها. تفوز thew عندما α × 9 × 10⁻⁸ > 1.4 × 10⁻⁷، وهذا يتطلب α > 1.56. والاحتمال لا يمكن أن يتجاوز واحدا، فبهذه القراءة تفوز the مع كل قيمة لـ α.
But the previous concept showed that α and the edits share one total: the edits get 1 − α. The 0.000007 for ew|e was estimated with 1 − α = 0.05. If the writer is more careful, every edit becomes less likely too, so the edit probability scales by (1 − α) / 0.05. Now the comparison is
لكن المفهوم السابق بيّن أن α والتعديلات تتقاسم مجموعا واحدا: التعديلات تحصل على 1 − α. القيمة 0.000007 لـ ew|e قُدّرت عند 1 − α = 0.05. فإذا كان الكاتب أكثر حرصا، يصبح كل تعديل أقل احتمالا أيضا، فيُضرب احتمال التعديل في (1 − α) / 0.05. وتصبح المقارنة الآن
That is Norvig's own remark: had he assumed one error in fifty words (α = .98), thew would have become the most probable answer. Check it: the = 1.4 × 10⁻⁷ × 0.4 = 5.6 × 10⁻⁸, and thew = 0.98 × 9 × 10⁻⁸ = 8.8 × 10⁻⁸. SLP3 makes the same point: when α is high enough, the model may decide thew was intended. The other lever is the prior. In a corpus about anatomy or old poetry, P(thew) would be larger, and α would tip the balance much earlier.
وهذه ملاحظة Norvig نفسه: لو افترض خطأ واحدا في كل خمسين كلمة (α = .98)، لأصبحت thew هي الجواب الأعلى احتمالا. تحقق من ذلك: the = 1.4 × 10⁻⁷ × 0.4 = 5.6 × 10⁻⁸، وthew = 0.98 × 9 × 10⁻⁸ = 8.8 × 10⁻⁸. ويقول SLP3 الشيء نفسه: عندما تكون α مرتفعة بما يكفي، قد يقرر النموذج أن thew هي المقصودة. والرافعة الأخرى هي الاحتمال المسبق. في مدوّنة عن التشريح أو الشعر القديم، تكون P(thew) أكبر، فتقلب α الكفة في وقت أبكر بكثير.
| w | edit | P(x|w) | P(w) | 10⁹ score | |
|---|---|---|---|---|---|
| the | ew|e insertion of w after e | 7.0e-6 | 2e-2 | 140.0 | |
| thew | none typed as intended | 0.950 | 9e-8 | 85.5 | |
| thaw | e|a substitution of e for a | 1.0e-3 | 7e-7 | 0.7000 | |
| threw | h|hr deletion of r after h | 8.0e-6 | 4e-6 | 0.0320 | |
| thwe | ew|we transposition of we | 3.0e-6 | 4e-8 | 1.20e-4 |
Only the thew slot is scored, with the unigram priors and edit probabilities from slide 39. In the shared mode, every edit probability is rescaled by (1 − α) / 0.05, so the edits together always keep the probability that α leaves over. Bars use a log scale.تُحسب الدرجة لخانة thew وحدها، باستخدام احتمالات unigram المسبقة واحتمالات التعديل من الشريحة 39. في الوضع المشترك يُعاد تحجيم كل احتمال تعديل بالمعامل (1 − α) / 0.05، فتحتفظ التعديلات مجتمعةً دائمًا بالاحتمال الذي تتركه α. تستخدم الأشرطة مقياسًا لوغاريتميًا.
Try it. With “Edits fixed”, slide α from .90 to .995: thew climbs from 81 to about 90 but never reaches 140. Switch to “Edits share 1 − α” and the the score falls as α rises, until the winning sentence flips to two of thew just below α = .97. Toggle the search space to watch the lattice shrink from 48 paths to 9.
جرّبها. مع خيار «Edits fixed» (التعديلات ثابتة)، حرّك α من .90 إلى .995: ترتفع thew من 81 إلى نحو 90 لكنها لا تصل أبدا إلى 140. انتقل إلى «Edits share 1 − α» (التعديلات تتقاسم 1 − α) فتنخفض درجة the كلما ارتفعت α، حتى تنقلب الجملة الفائزة إلى two of thew قبل α = .97 بقليل. بدّل فضاء البحث لترى الشبكة تتقلص من 48 مسارا إلى 9.
Recall
Name the edit behind each of the, thaw, threw and thwe as corrections of thew.سمِّ التعديل الذي وراء كل من the وthaw وthrew وthwe بوصفها تصحيحات لـ thew.
the: insertion of w after e (ew|e). thaw: substitution of e for a (e|a). threw: deletion of r after h (h|hr). thwe: transposition of we into ew (ew|we).
the: إدراج (insertion) لـ w بعد e (ew|e). thaw: استبدال (substitution) e مكان a (e|a). threw: حذف (deletion) لـ r بعد h (h|hr). thwe: تبديل موضعين (transposition) لـ we إلى ew (ew|we).
Quick checkاختبار سريع
Edits share 1 − α. Raising α from .95 to .99 does what to the thew decision?التعديلات تتقاسم 1 − α. ماذا يحدث لقرار thew عند رفع α من .95 إلى .99؟
Recapالخلاصة
If you remember nothing elseإن لم تتذكر شيئاً آخر فتذكّر هذا
- Each typed word gets a candidate set: itself plus real words one edit away. Stack the sets in columns and every left-to-right path is a candidate sentence: the candidate lattice.كل كلمة مكتوبة تحصل على مجموعة مرشحات (candidate set): الكلمة نفسها مع الكلمات الحقيقية التي تبعد عنها تعديلا واحدا. ضع المجموعات في أعمدة متجاورة، فيصبح كل مسار من اليسار إلى اليمين جملة مرشحة: هذه هي شبكة المرشحات (candidate lattice).
- The full lattice for two of thew holds 4 × 3 × 4 = 48 sentences, and the count multiplies with sentence length.الشبكة الكاملة لعبارة two of thew تحتوي على 4 × 3 × 4 = 48 جملة، والعدد يتضاعف بالضرب كلما طالت الجملة.
- One error per sentence keeps only the typed sentence plus every single-word substitution: 1 + 3 + 2 + 3 = 9. The count now adds instead of multiplying.افتراض خطأ واحد في كل جملة يُبقي فقط الجملة المكتوبة مع كل استبدال لكلمة واحدة: 1 + 3 + 2 + 3 = 9. صار العدد يُجمع بدل أن يُضرب.
- Each candidate sentence W is scored by P(X|W) P(W): a language model (unigram, bigram, trigram) for P(W), and the non-word channel model for the changed word.كل جملة مرشحة W تُقيَّم بـ P(X|W) P(W): نموذج لغوي (unigram أو bigram أو trigram) لـ P(W)، ونموذج القناة نفسه المستخدم للكلمات غير الموجودة للكلمة التي تغيّرت.
- Real words need one more channel value, P(w|w) = α, the probability that a word was typed as intended. α is set by the application: .90, .95, .99, .995 mean 1 error in 10, 20, 100, 200 words.الكلمات الحقيقية تحتاج إلى قيمة قناة إضافية، P(w|w) = α، وهي احتمال أن الكلمة كُتبت كما قُصدت. التطبيق هو الذي يحدد α: القيم .90 و.95 و.99 و.995 تعني خطأ واحدا في كل 10 و20 و100 و200 كلمة.
- Norvig's thew table at α = .95 gives the = 0.000007 × 0.02 = 1.4 × 10⁻⁷ against thew = 0.95 × 9 × 10⁻⁸ = 8.55 × 10⁻⁸, so the wins.جدول Norvig لكلمة thew عند α = .95 يعطي the = 0.000007 × 0.02 = 1.4 × 10⁻⁷ مقابل thew = 0.95 × 9 × 10⁻⁸ = 8.55 × 10⁻⁸، لذلك تفوز the.
- Raising α alone cannot rescue thew while the edit probabilities stay fixed. If the edits share the leftover 1 − α, as Norvig and SLP3 intend, thew wins above about α = .969.رفع α وحده لا ينقذ thew ما دامت احتمالات التعديلات ثابتة. أما إذا تقاسمت التعديلات الباقي 1 − α، كما يقصد Norvig وSLP3، فإن thew تفوز عندما تتجاوز α قرابة .969.
Sourcesالمصادر
- Natural Language Corpus Data (Beautiful Data, chapter 14)BookPeter Norvig, O'ReillyThe thew table, the edit notation, the one-in-twenty choice for P(w|w), and the remark that one in fifty would make thew win.جدول thew، وترميز التعديلات، واختيار واحد من عشرين لـ P(w|w)، وملاحظة أن واحدا من خمسين كان سيجعل thew تفوز.(opens in a new tab)(يفتح في تبويب جديد)
- Speech and Language Processing, Appendix B: Spelling Correction and the Noisy Channel (Oct 2019 draft)BookDaniel Jurafsky and James H. MartinSection B.2: the Mays et al. candidate sentences, one error per sentence, α = P(w|w), and the trigram version of the thew table.القسم B.2: الجمل المرشحة عند Mays وزملائه، وافتراض خطأ واحد في كل جملة، والقيمة α = P(w|w)، ونسخة trigram من جدول thew.(opens in a new tab)(يفتح في تبويب جديد)
- Detection is the central problem in real-word spelling correctionPaperL. Amber Wilcox-O'Hearn, arXivWhy deciding which real words are errors is harder than choosing their correction.لماذا يكون تحديد أي الكلمات الحقيقية خطأ أصعب من اختيار تصحيحها.(opens in a new tab)(يفتح في تبويب جديد)
- Real-Word Error Correction with Trigrams: Correcting Multiple Errors in a SentencePaperSeyed MohammadSadegh Dashti, arXivRevisits the Mays, Damerau and Mercer model and extends it beyond one error per sentence.يعيد النظر في نموذج Mays وDamerau وMercer ويوسّعه ليتجاوز خطأ واحدا في كل جملة.(opens in a new tab)(يفتح في تبويب جديد)