sources for spelling mistakes, e.g. typing too fast, unintentional key In this paper, we reformulated the spelling correction problem asstroke, phonetic ambiguity among others. Lastly, in certain context a machine translation task under the encoder-decoder framework. (e.g. in a search engine) it is not easy to obtain clean training data This reformulation enabled us to use a single model for solvifnogr language model as the input does not follow what is typical in this problem that is traditionally formulated as learning a langnuaatgueral language. model and an error model. This model employs multi-layer recur- Since the goal is to get text that maximP (ixz|xe˜), can we directly rent neural networks as an encoder and a decoder. We demonstrate model this conditional distribution instead? In this work, we exthe efectiveness of this model using an internal dataset, where theplore this route, which by passes the need to have multiple models training data is automatically obtained from user logs. The moadneld avoid getting errors from multiple sources. We achieve this ofers competitive performance as compared to the state of the art by applying the sequence to sequence learning framework using methods but does not require any feature engineering nor hand recurrent neural networks [16] and reformulate the spelling cortuning between models. rection problem as a neural machine translation problem, where the misspelled input is treated as a foreign language.
forward neural network for modeling sequential data. More
formally, le(tx1, x2, . . . , xT ), xt ∈ Rd be the input, an RNN update its
ct = ft ⊙ ct −1 + (1 − ft ) ⊙ tanh(Wc xt + Ucht −1 + bc )
internal recurrent hidden states by doing the following computwa-here the input is the misspelled text and the output is the
cortion: responding correct spellings. One challenge for this formulation
ht = ψ (ht −1, xt ) (
One problem with standard RNN is that it is diicult for them to learn long term dependencie2s,[9], and therefore in practice more between too large output vocabulary and too much learning burden sophisticated funct iψoanre often used to alleviate this problem. for decoders. In this scheme, the vocabulary is built by recursively For example the long short term memory (LSTM)1[0] is one widely merging most frequent pairs of strings starting from character, and the vocabulary size is controlled by the number of merging used recursive unit that is designed to learn long term dependencies.
A layer LSTM consists of three gates and one memory cell, the iterations.
computation of LSTM is as follo1w: ing As shown in papers1[], encoding the whole input string to a
single ixed length vector is not optimal, since it may not reserve all
it = σ (Wi xt + Uiht −1 + bi ) (
T
ci = Õ λi jhj
j=1
(
The attentional decoder irst obtain the context veccttorbased on equation 10, and then learns a functifodnthat decodes yt from the context vector ct where fe and fd are implemented using multi-layer LSTMs. 4 SPELLING CORRECTION AS A FOREIGN
LANGUAGE p(yt |st ) = softmax(W st + bd ) s0 = U hT st = fd (st −1, ct ; θd ) It is easy to see that spelling correction problem can be formulatedwhere W and bd are the output matrix and biaUs, is a matrix that as a sequence to sequence learning problem as mentioned in sectionmake sure that the hidden states of encoder would be consistent 3. In this sense, it is very similar to a machine translation probwleimth, the decoder’s. In our implementation, bfoethand fd are 1Sometimes additional weight matrix and vector are added to generate output from2The vocabulary is limited in a sense that the number of words are upper bounded, in ht for LSTM, we choose to stick with the original formulation for simplicity. general h1 … x1 h2 … x2
Encoder … … … … hT … EOS
Y1 s1 … EOS Y2 s2 … y1
… … … …
EOS sT’ … yT’ notice that in equation 18 the context vecctioris a function of the encoding functifoen, so we are not left the encoder isolated. Since all components are smooth and diferentiable, the model can be easily trained with gradient based method to maximize the likelihood on the dataset.
62.0% 59.9 % 62.5 % 55.1% 5 EXPERIMENTS We test our model in the setting of correcting e-commerce queries. We use beam search to obtain the inal result from the model. The Unlike machine translation problem, there is no public datasreetssult is illustrated in table 1, it is clear that our albeit much simpler, for e-commerce spelling correction, and therefore we collect bothour RNN based model ofers competitive performance as compare training and evaluation data internally. For training data, wetuostehe previous methods. It is interesting to note that, the BPE based the event logs that tracks user behavior on an e-commerce website. encoder and decoder performs the best. The better performance may attribute to the shorter resultant sequence as compared to the Our heuristic for inding potential spelling related queries is based on consecutive user actions in one search session. The hypothesischaracter case, and possibly more semantic meaningful segments from the sub-words as compared to the characters. Surprisingly, is that users will try to modify the search query until the search result is desirable with the search intent, and from this sequentchee character based decoder performs quite well considering the complexity of the learning task. This demonstrated the beneit from of action on queries we can potentially extract the misspelling and correct spelled query pair. Obviously, this includes a lot moerned-to-end training and the robustness of the framework. diversity on query activities besides spelling mistakes, and thus additional iltering is required to obtain representative dat6a foCrONCLUSION spelling correction. We use the same techniques as Hasan e8t].al.[ In this paper, we reformulated the spelling correction problem as Filtering multiple months of data from our data warehouse, wea machine translation task under the encoder-decoder framework. got about 70 million misspelling and spell correction pairs aTshoeurreformulation allowed us to use a single model for solving the training data. For testing, we use the same dataset as in paper problem and can be trained from end-to-end. We demonstrate the [8], where it contains 4602 queries and the samples are labeled by efectiveness of this model using an internal dataset, where the human. training data is automatically obtained from user logs. Despite the simplicity of the model, it performed competitively as compared to the state of the art methods that require a lot of feature engineering and human intervention.