FNLP: 8: Spelling Correction, Edit Distance and Expectation Maximisation

This folder introduces uses a particular NLP application, namely spelling correction, to introduce you to some algorithms (dynamic programming to calculate minimum edit distance) and machine learning methods ( expectation maximisation, or EM)  that are widely used in NLP.  Here, we look at how they contribute to learning an error model forms a part of a noisy channel model, together with a language model, for doing spell checking.  It consists of:
  • three videos of short lectures. They cover:
    1. Spelling Correction
    2. Spelling Correction and Edit Distance
    3. Expectation Maximisation
  • some required reading from Jurafsky and Martin
  • a quiz that tests your understanding of the material presented here.
Please do the required reading, and attempt the quiz.  If there is anything you don't understand, then please ask questions in the lecture or on piazza.

Lecture 8 Slides: Whole!

8a: Spelling Correction


8b: Spelling Correction and Edit Distance

 

8c: Expectation Maximisation (EM)


Recommended Reading

J&M Appendix B (2nd edition: 5.9--5.10), 2.5 (2nd edition 3.11 and 5.9) and Appendix A (2nd edition 6.5)

NOTE: The abbreviation J&M refers to the textbook: 
Dan Jurafsky and James H. Martin, Speech and Language Processing.

When we specify 2nd edition, we are referring to the version of the book that was published by Pearson International in 2008.

When we specify 3rd edition, then we will supply links to the drafts of the relevant parts of that book (since the third editiion isn't published yet, but the current draft is available here).


Quiz 8: Spelling Correction and Edit Distance

These questions are designed to test your understanding of the above course content; doing this quiz does not contribute to your overall grade.  Some questions require a text answer.  You can ask for formative feedback on these from your tutor or on piazza.  Other questions are multiple choice or they require a numeric answer: you will get immediate feedback for these. Please don't attempt this quiz until you have acquainted yourself with this lecture and the required reading.

You must be logged onto Learn to do this quiz.

License
All rights reserved The University of Edinburgh