Text Processing Techniques - Text Error Correction

Text Error Correction Techniques

Text error correction is also called spelling correction or spell checking. There are generally two major types of errors to correct:

1. Non-word spelling errors
2. Real-word spelling errors

Non-word Spelling Errors

This means the word itself does not exist in the dictionary, for example the Chinese word “yaoqiu” (requirement) written with a wrong, similar-sounding first character, or correction written as corrction

The procedure has two steps:

1. Find candidate words
2. Based on a specific algorithm, pick the one or more words most closely associated with the misspelled word as correction options

How do we determine the candidates?

English: edit distance

Chinese: similar pronunciation, similar character shapes (elderly people typing by handwriting input, or people typing with Wubi)

Once the candidates are found, the next step is to find the most relevant one. According to Bayes’ theorem, we get the following expression:

P(candidate|misspelled word) is proportional to P(candidate) * P(misspelled word|candidate)

To explain: P(candidate) refers to the probability of this option itself appearing in the corpus, and P(misspelled word|candidate) refers to the probability that people who intend to type the candidate mistype it as the misspelled word

Considering only the candidate itself is a first-order (unigram) model, which requires counting how often words occur. Of course, it can also be extended to second or third order, for example counting how often “word to the left of the misspelled word + candidate + word to the right of the misspelled word” appears in the corpus.

Real-word Correction Techniques

The word itself is not wrong, but it does not fit the context. This often involves semantic and grammatical errors, for example “wo xianzai zai gongsi li” (“I’m at the company now”) mistakenly written as “wo xianzai zai gongshi li” (“I’m in the formula now”), since “gongsi” (company) and “gongshi” (formula) sound alike

Procedure:

1. First, for each word, select candidates (including the word itself) by means such as edit distance, homophones, and similar-looking words
2. The subsequent computation is based on a language model over the candidates, and also computes the probability of the word itself appearing in the sentence. If, overall, the probability of the word itself is relatively high, no correction is made; otherwise a correction is recommended.

PS: If I checked every single word, the complexity would be extremely high, so in practice it’s impossible to check all words. Instead, we first apply a language model or similar methods to do a coarse-grained preliminary screening of the sentence.

Generally, given a sentence, we compute its probability of occurring, and if it’s not high, we then screen it further.

Assignment: Text Error Correction Task: Non-word English Correction

Assignment hints:

1. Find candidates: use edit distance
2. Language model, first-order or second-order
3. Conditional probability model: mapping between misspelled words and correct words (if not available, treat it as 1)

Wrong approach: compute the probability of every word for each candidate; this has very high complexity

Right approach: from the misspelled word, generate strings with edit distance 1 or 2, and then match them against words

Low-frequency Preprocessing: Low-frequency Words

For NLP applications, we usually filter out words that occur very rarely

Reasons:

1. Words that occur extremely rarely generally contribute little to the analysis
2. They have little impact on the amount of training data
3. It effectively reduces computational complexity

Points 2 and 3 above are based on a linguistic phenomenon called Zipf’s law, proposed by the Harvard linguist Zipf:

In a natural-language corpus, the frequency of a word is inversely proportional to its rank in the frequency table

My understanding: low-frequency words make up a large share of the vocabulary, so removing them effectively reduces complexity; moreover, although there are many low-frequency words, they don’t account for much data, so removing them has little impact.

Zipf’s law is also known as the long-tail phenomenon: the more common something is, the more frequently it occurs; the more special, the less frequently.

There is also the similar 80/20 rule.

Stop Word Preprocessing

Modal particles and auxiliary words can be treated as stop words, but the specific application scenario should also be taken into account