Improved Iterative Correction for Distant Spelling Errors

Noisy channel is a probabilistic model that defines posterior probability $P\left(q_0\right|q_1)$ of $q_0$ being the intended word, given the observed word $q_1$; for such model, the optimal decision rule $\mu$ is the following:

where $P_{\mathrm{LM}}$ is the source (language) model, and $P_{\mathrm{dist}}$ is the error model. Given $P\left(q_0\right|q_1)$ defined, to correct the word $q_1$ we could iterate through all ever-observed words, and choose the one, that maximizes the posterior probability. However, the practical considerations demand that we do not rank the whole list of words, but instead choose between a limited number of hypotheses $h_1,\mathrm{\dots },h_K$:

1. 1.

   Given $q_1$, generate a set of hypotheses $h_1,\mathrm{\dots },h_K$, such that

   $$\sum _{k=1}^{K}P(q_0=h_k|q_1)\approx 1;$$

   (2)

2. 2.

   Choose the hypothesis $h_k$ that maximizes $P(q_0=h_k|q_1)$.

If hypotheses constitute a major part of the posterior probability mass, it is highly unlikely that the intended word is not among them.

In baseline speller we use a substring-based error model $P_{\mathrm{dist}}(q_0\to q_1)$ described in [1], the error model training method and the hypotheses generator are similar to [4].

For building language ($P_{{\mathrm{LM}}^{\prime }}$) and error ($P_{{\mathrm{dist}}^{\prime }}$) models, we use words collected from the 6-months query log of a commercial search engine.

Hypotheses generator is based on A* beam search in a trie of words, and yields $K$ hypotheses $h_k$, for which the noisy channel scores $P_{\mathrm{dist}}(h_k\to q_1)P_{\mathrm{LM}}\left(h_k\right)$ are highest possible. Hypotheses generator has high K-best recall (see Section 4.2) — in 91.8% cases the correct hypothesis is found when $K=30$, which confirms the assumption about covering almost all posterior probability mass (see Equation 2).

Iterative spelling correction with $E$ iterations uses standard noisy-channel to correct the query $q$ repeatedly $E$ times. It is motivated by the assumption, that we are more likely to successfully correct the query if we take several short steps instead of one big step [3] .

Iterative correction is hill climbing in the space of possible corrections: on each iteration we make a transition to the best point in the neighbourhood, i.e. to correction, that has maximal posterior probability $P\left(c\right|q)$. As any local search method, iterative correction is prone to local minima, stopping before reaching the correct word.

A common method of avoiding local minima in optimization is the simulated annealing algorithm, key ideas from which can be adapted for spelling correction task. In this section we propose such an adaptation. Consider: we do not always transition deterministically to the next best correction, but instead transition randomly to a (potentially any) correction with transition probability being equal to the posterior $P\left(c_i\right|c_{i-1})$, where $c_{i-1}$ is the correction we transition from, $c_i$ is the correction we transition to, and $P(\cdot |\cdot )$ is defined by Equation 1. Iterative correction then turns into a random walk: we start at word $c_0=q$ and stop after $E$ random steps at some word $c_E$, which becomes our answer.

To turn random walk into deterministic spelling correction algorithm, we de-randomize it, using the following transformation. Described random walk defines, for each word $w$, a probability $P(c_E=w|q)$ of ending up in $w$ after starting a walk from the initial query $q$. With that probability defined, our correction algorithm is the following: given query $q$, pick $c=\arg {max}_{c_E}P\left(c_E\right|q)$ as a correction.

Probability of getting from $c_0=q$ to some $c_E=c$ is a sum, over all possible paths, of probabilities of getting from $q$ to $c$ via specific path $q=c_0\to c_1\to \mathrm{\dots }\to c_{E-1}\to c_E=c$:

where $W$ is the set of all possible words, and $P_{\mathrm{observe}}\left(w\right)$ is the probability of observing $w$ as a query in the noisy-channel model.

Example: if we start a random walk from vobemzin and make 3 steps, we most probably will end up in the correct form wobenzym with $P=0.361$. A few of the most probable random walk paths are shown in Table 2. Note, that despite the fact that most probable path does not lead to the correct word, many other paths to wobenzym sum up to 0.361, which is greater than probability of any other word. Also note, that the method works only because multiple misspellings of the same word are presented in our model; for related research see [2].

Also note, that while Equation 3 uses noisy-channel posteriors, the method can use an arbitrary discriminative model, for example the one from [5], and benefit from a more accurate posterior estimate.

This section describes some common heuristic improvements, that, where possible, were applied both to the baseline methods and to the proposed algorithm.

Basic building block of every mentioned algorithm is one-step noisy-channel correction. Each basic correction proceeds as described in Section 2.1: a small number of hypotheses $h_1,\mathrm{\dots },h_K$ is generated for the query $q$, hypotheses are scored, and scores are recomputed into normalized posterior probabilities (see Equation 5). Posterior probabilities are then either used to pick the best correction (in baseline and simple iterative correction), or are accumulated to later compute the score defined by Equation 3.

A standard log-linear weighing trick was applied to noisy-channel model components, see e.g. [9]. $\lambda$ is the parameter that controls the trade-off between precision and recall (see Section 4.2) by emphasizing the importance of either the high frequency of the correction or its proximity to the query.

We have also found, that resulting posterior probabilities emphasize the best hypothesis too much: best hypothesis gets almost all probability mass and other hypotheses get none. To compensate for that, posteriors were smoothed by raising each probability to some power and re-normalizing them afterward:

In a sense, $\gamma$ is like temperature parameter in simulated annealing – it controls the entropy of the walk and the final probability distribution. Unlike in simulated annealing, we fix $\gamma$ for all iterations of the algorithm.

Finally, if posterior probability of the best hypothesis was lower than threshold $\alpha$, then the original query $q$ was used as the spell-checker output. (Posterior is defined by Equation 6 for the baseline and simple iterative methods and by Equations 3 and 6 for the proposed method). Parameter $\alpha$ controls precision/recall trade-off (as well as $\lambda$ mentioned above).

To evaluate the proposed algorithm we have collected two datasets. Both datasets were randomly sampled from single-word user queries from the 1-week query log of a commercial search engine. We annotated them with the help of professional analyst. The difference between datasets is that one of them contained only queries with low search performance: for which the number of documents retrieved by the search engine was less than a fixed threshold (we will address it as the ”hard” dataset), while the other dataset had no such restrictions (we will call it ”common”). Dataset statistics are shown in Table 3.

Increased average error model score and error rate of ”common” dataset compared to ”hard” shows, that we have indeed managed to collect hard-to-correct queries in the ”hard” dataset.

First of all, we evaluated the recall of hypotheses generator using K-best recall — the number of correct spelling corrections for misspelled queries among $K$ hypotheses divided by the total number of misspelled queries in the test set. Resulting recall with $K=30$ is 91.8% on ”hard” and 98.6% on ”common”.

Next, three spelling correction methods were tested: noisy channel, iterative correction and our method (stochastic iterative correction).

For evaluation of spelling correction quality, we use the following metrics:

• •

  Precision: The number of correct spelling corrections for misspelled words generated by the system divided by the total number of corrections generated by the system;

• •

  Recall: The number of correct spelling corrections for misspelled words generated by the system divided by the total number of misspelled words in the test set;

For hypotheses generator, $K=30$ was fixed: recall of 91.8% was considered big enough. Precision/recall tradeoff parameters $\lambda$ and $\alpha$ (they are applicable to each method, including baseline) were iterated by the grid $\left(0.2,0.25,0.3,\mathrm{\dots },1.5\right)\times \left(0,0.025,0.05,\mathrm{\dots },1.0\right)$, and $E$ (applicable to iterative and our method) and $\gamma$ (just our method) were iterated by the grid $\left(2,3,4,5,7,10\right)\times \left(0.1,0.15,\mathrm{\dots }1.0\right)$; for each set of parameters, precision and recall were measured on both datasets. Pareto frontiers for precision and recall are shown in Figures 1 and 2.

We were not able to reproduce superior performance of the iterative method over the noisy channel, reported by [3]. Supposedly, it is because the iterative method benefits primarily from the sequential application of split/join operations altering query decomposition into words; since we are considering only one-word queries, such decomposition does not matter.

On the ”hard” dataset the performance of the noisy channel and the iterative methods is inferior to our proposed method, see Figure 1. We tested all three methods on the ”common” dataset as well to evaluate if our handling of hard cases affects the performance of our approach on the common cases of spelling error. Our method performs well on the common cases as well, as Figure 2 shows. The performance comparison for the ”common” dataset shows comparable performance for all considered methods.

Noisy channel and iterative methods’ frontiers are considerably inferior to the proposed method on ”hard” dataset, which means that our method works better. The results on ”common” dataset show, that the proposed method doesn’t work worse than baseline.

Next, we optimized parameters for each method and each dataset separately to achieve the highest $F_1$ measure. Results are shown in Tables 4 and 5. We can see, that, given the proper tuning, our method can work better on any dataset (but it cannot achieve the best performance on both datasets at once). See Tables 4 and 5 for details.

Next, each parameter was separately iterated (by a coarser grid); initial parameters for each method were taken from Table 4. Such iteration serves two purposes: to show the influence of parameters on algorithm performance, and to show differences between datasets: in such setup parameters are virtually tuned using ”hard” dataset and evaluated using ”common” dataset. Results are shown in Table 6.

The proposed method is able to successfully correct distant spelling errors with edit distance of 3 characters (see Table 7).

However, if our method is applied to shorter and more frequent queries (as opposed to ”hard” dataset), it tends to suggest frequent words as false-positive corrections (for example, grid is corrected to creed – Assassin’s Creed is popular video game). As can be seen in Table 5, in order to fix that, algorithm parameters need to be tuned more towards precision.