An improved Bayesian TRIE based model for SMS text normalization

SMS text normalization focuses on translating texting language, often filled with abbreviations and marred by typing errors into plain English text. With the smartphone revolution and massive popularisation of social media platforms, users often transmit messages consisting of up to thousands of words in a single day. However, these text messages consist of numerous abbreviations and errors. This often arises due to a lack of formalities between users, human error, and in more severe cases due to disabilities. With an increase in the screen sizes, this is becoming more of a concern especially when the user resorts to one handed typing. Thus, shorter message length and semantic unambiguity end up working antagonistically which gives shape to a compressed, non-standard form of language called NetSpeak [1], commonly known as the texting language. Unfortunately, traditional NLP methods perform rather poorly when dealing with these kinds of texts [2]. As described in [3], texting language contains many non-standard abbreviations, have unique characteristics and behave quite differently which may be the reason for poor performance of traditional NLP methods.

In [4] the problem was approached by leveraging the phonetic information but required a dictionary for phonetic transcription. [5] used a dictionary for erroneous words but used an ambiguous ranking mechanism. [6] used a completely heuristic rule based model and employed a dictionary for typos as well which in all the three cases caused the time complexity to grow with the size of the dictionary. [7] compared machine translation models such as SMT and NMT and showed their critical dependence on high quality training data. In [8], a Hidden Markov Model based approach was used for each word present in the corpus to model all possible normalized or corrected texts and their probabilities of occurrence. This was further used to rank all the possible normalised words and the highest ranking word would be selected for output as the semantically correct word. In [9], a Trie based probability generation model was proposed, and was shown to outperform HMM-based models whenever the incorrect word was within an edit distance one after prepossessing for phonetic errors. However, in some cases the target word did not end up having the highest rank. For example, ‘mate’, the intended target word was ranked $4^{th}$ in the suggestions list for the word ‘m8’.
Through this work we address the limitations of this Trie based probability generation model. We make a set of improvements over the scheme proposed in [9] which we consider to be the baseline system for the present work. Firstly, unlike [9] where a new word is added in a Trie only once when it is encountered for the first time during the training phase, a dynamic training environment is used in the proposed model. In the proposed model the Trie is initially constructed with a certain corpus of most commonly used words and is then deployed. After deployment, the tries learns dynamically from the texting habits of the users over time i.e. it keeps adding the same words repeatedly as and when they are encountered. We show that the new model in the described environment is able to estimate the real probability of occurrence of a word through its own new probability generating algorithm. Hence it facilitates 0-1 loss minimisation in a decision theoretic setup. This in turn minimizes the chances of the target word not being ranked as the highest one.
Additionally, as explained in [10] , it is computationally infeasible to generate all the words which are at an edit distance two from a given word. This limited the spelling correction abilities of the baseline model. In this work we propose some novel heuristics that help in overcoming the above shortcoming significantly.
The contributions of the present work are

1. 1.

   We suggest a structural modification to the Trie-based reasoning scheme to improve model accuracy and performance.

2. 2.

   We prove mathematically that in the described dynamic environment, the expectation of the thus generated Trie probability equals the occurrence probability for each word.

3. 3.

   We further prove that the Trie probability of each word in the corpus almost surely(a.s.) converges to its occurrence probability.

4. 4.

   Develop a set of heuristics for error correction.

5. 5.

   Provide empirical results through simulations to support the presented theorems and highlight the superiority of the new model.

From existing literature on the behaviour of users while using texting language [11], one can classify most of the linguistic errors as:

1. 1.

   Insertion Error: Insertion of an extra alphabet in the word. Eg. ‘hoarding’$\rightarrow$‘hoardingh’

2. 2.

   Deletion Error: Deletion of an alphabet from the word. Eg. ‘mobile’$\rightarrow$‘moble’

3. 3.

   Replacement Error: Replacement of an alphabet by another in the word. Eg. ‘amazing’$\rightarrow$‘anazing’

4. 4.

   Swap Error: Swapping of two adjacent characters in the word. Eg. ‘care’$\rightarrow$‘caer’

5. 5.

   Phonetic Error: A group of alphabets is replaced by another group of alphabets or numbers having the same sound. Eg. ‘tomorrow’$\rightarrow$‘2morrow’

To deal with these errors, an elaborate error correction algorithm has already been proposed in the baseline model wherein given an erroneous/non-lexical word, a suggestion list of possible target words was prepared. The probability of occurrence for each word in the list was generated using a Trie based algorithm as described in Section 2.2 which was used for ranking the words in the suggestion list. The highest ranking word was given out as the likely intended word.

We consider the user to be modelled as a corpus of words denoted by $\mathcal{S}$ where each word $w_{i}\in\mathcal{S}$ has an occurrence probability of $p_{i}$. Note that then the training and probability calculations as proposed in the baseline Trie does not account for an important case. This is when the corpus of words $\mathcal{S}$ contains two words say $w_{1}$ and $w_{2}$ with occurrence probabilities $p_{1}$ and $p_{2}$, $p_{1}\neq p_{2}$ such that $w_{1}$ is a prefix of $w_{2}$ or vice versa. For example consider the two words ’bill’ and ’bills’ in Fig.1. No matter what the occurrence probabilities of those two words are, they will always end up with the same Trie probability¹¹1Generally, in more branched Tries, whenever $w_{1}$ is a prefix of $w_{2}$, Trie probability of $w_{2}$ $\leq$ Trie probability of $w_{1}$ even after training the Trie a large number of times after random sampling from $\mathcal{S}$. While the deviation from occurrence probabilities might not vary a lot in the example considered since one word happens to be the plural of the other, it will matter much more in words such as ’lips’ & ’lipstick’ and ‘dear’ & ‘dearth’.
To overcome this we propose the introduction of a dummy node. This dummy node is added as a child of every node which has End-Of-Word set as True but has at least one non-dummy node as its child. The Count variable of this dummy node is set to be the count variable of the parent reduced by the count variable of all the siblings of the new dummy node.

Where $D$ denotes the dummy node and $P$ denotes the parent of the dummy node. Algorithm I in this section outlines the procedure for training the new Trie as described above.
In addition to the training algorithm, we also propose Algorithm II which is used to generate the Trie probability of a given string.
Further, to justify usage of the new Trie mathematically, the proposed training algorithm and the algorithm for the Trie probability generation, we present Theorem 3.1, Theorem 3.2 and Corollary 3.3.

  Algorithm I: The Training   Input: $w$, root
Initialization: $str\leftarrow w$, $m\leftarrow str$.length, $parent\leftarrow$ root, $Flag\leftarrow 0$
For $j\leftarrow 1$ to $m$

1. 1.

   If $parent$.children does not contain $str$.charAt[$j$] node

   1. 1..1

      Insert new node corresponding to $str$.charAt[$j$]

   2. 1..2

      $Flag\leftarrow 1$

2. 2.

   $parent\leftarrow$ child corresponding to $str$.charAt[$j$]

3. 3.

   $parent$.Counter $\leftarrow parent$.Counter$+1$

$parent$.End-Of-Word$\leftarrow$True
If a dummy node $D$ is already a child of $parent$

1. 1.

   Increment Counter of $D$ by 1

Else if $Flag$ is 0 and $parent$ has at least 1 non-dummy child

1. 1.

   Insert new dummy node as a child of $parent$

2. 2.

   set Counter of dummy as in Eqn.(3)

End     Algorithm II: The Trie Probability Generation   Input: $w$, root
Output: Trie probability of $w$
Initialization: $str\leftarrow w$, $m\leftarrow str$.length, $parent\leftarrow$ root, $probab\leftarrow 1$
For $j\leftarrow 1$ to $m$

1. 1.

   If $parent$.children does not contain str.charAt[j] node

   1. 1..1

      return $0$

2. 2.

   $child\leftarrow$ child corresponding to str.charAt[j]

3. 3.

   Update $probab$ using Eqn.(1) & Eqn.(2) for $child$

4. 4.

   $parent\leftarrow child$

If $parent$.End-Of-Word is True

1. 1.

   If $parent$ has dummy node

   1. 1..1

      Update $probab$ using Eqn.(1) & Eqn.(2) for $parent$

2. 2.

   return $probab$

return $0$
End  

Theorem 3.1: Let $\mathcal{S}$ denote a corpus of finite words. Let $w_{i}\in\mathcal{S}$ be a word of the corpus with an occurrence probability $p_{i}$ and let $\hat{p}_{i}$ denote the word probability generated by the Trie. Let the Trie be trained $n$ number of times after randomly sampling(with replacement) from $S$ such that the Trie is trained with each $w_{i}\in\mathcal{S}$ at least once. Then, $\mathbb{E}[\hat{p}_{i}]=p_{i}$.

Proof: We use strong induction over the number of words present in the corpus to prove the theorem.
Base Case: Consider a corpus $\mathcal{S}$ consisting of two words $w_{1}$ and $w_{2}$ with occurrence probabilities $p_{1}$ and $p_{2}$. Then three cases are possible as shown in Fig.2.
Case I: The starting characters of $w_{1}$ and $w_{2}$ are different. Then, after using the random sample from $\mathcal{S}$ to train the Trie $n$ number of times. The Trie along with all the expected values of the Count variables are shown in Fig.2(a). Clearly,

and

Case II: Both $w_{1}$ and $w_{2}$ have a common string of characters in the front. For illustration, ‘more’ and ‘most’ have ‘mo’ common at the front. Hence similar to Case I, it can be argued from Fig.2(b). that Eqn.(4) and Eqn.(5) hold true.
Case III: $w_{1}$ can be obtained by appending a string of characters at the end of $w_{2}$ or vice versa. Here, as described earlier we introduce a dummy node, seen as the blue box in Fig.2(c). Similar to previous arguments, it can be seen that Eqn.(4) and Eqn.(5) hold.
Hence, for the base case when $|\mathcal{S}|=2$, the theorem is true.

Induction: Assume that the theorem holds whenever $|\mathcal{S}|\leq k$ for some positive integer $k$. We now show that the theorem holds true for any corpus of size $k+1$. Hence assume that we are given the words $w_{1},w_{2},\ldots,w_{k+1}$ with occurence probabilities $p_{1},p_{2},\ldots p_{k+1},$ respectively.

Case I: Similar to Case I and Case II of the base case, all the words branch out at the same node together as in Fig.3. The figure also shows the expected values of the $Counter$ variables after training the Trie $n$ number of times.

Hence we can easily conclude that for each $i=1,2,\ldots k,k+1$,

since $\sum_{i=1}^{k+1}{p_{i}}=1$.
Case II: In this case, consider all such possible Tries which are not covered by Case I. These Tries are in a way “more branched” than the ones considered in Case I. Consider $T$ to be any such Trie and denote its root by $R$. Notice that there must exist a subtree $T^{\prime}$, which contains strictly less than $k+1$ and at least two nodes which have their End-Of-Word set as True. It is easy to see that if not so, then $T$ lies in Case I which is a contradiction. Let us denote the root of $T^{\prime}$ by $R^{\prime}$. Let us assume that the nodes in $T^{\prime}$ for which $End-Of-Word$ is set to $True$ represent the words $w_{(1)},w_{(2)},\ldots,w_{(r)}$ with probabilities $p_{(1)},p_{(2)},\ldots,p_{(r)}$ respectively where $2\leq r<k+1$. Now suppose that $T$ instead of having the words $w_{(1)},w_{(2)},\ldots,w_{(r)}$, has a word whose characters are defined by travelling from $R$ to $R^{\prime}$ in the Trie as shown in Fig.4. Let this prefix word be $w_{\alpha}$ with a probability of $p_{\alpha}=p_{(1)}+p_{(2)}+\ldots+p_{(r)}$. Hence $T$ now practically contains strictly less than $k+1$ words. Hence by the induction hypothesis, when we train $T$, such that each one of the $k+2-r$ words is used for training at least once, the expectation of the Trie probabilities matches the occurrence probabilities. This means for each $w_{i}\in T$ whose last node doesn’t lie in $T^{\prime}$, Eqn.(6) holds true. Also, at the end of the training,

where $\alpha=n\times(p_{(1)}+p_{(2)}+\ldots+p_{(r)})$. We can now consider $T^{\prime}$ to be a standalone Trie by itself, consisting of words $w_{(1)},w_{(2)},\ldots,w_{(r)}$ but truncated from the front so as to remove the characters of $w_{\alpha}$. Let these truncated words in $T^{\prime}$ be denoted by $w^{\prime}_{(1)},w^{\prime}_{(2)},\ldots,w^{\prime}_{(r)}$ with occurrence probabilities $p^{\prime}_{(1)}+p^{\prime}_{(2)}+\ldots+p^{\prime}_{(r)}$. Now notice that $T^{\prime}$ has been trained $\alpha$ number of times and since $r<k+1$, the expectation of probabilities of $T^{\prime}$ will be the same as occurrence probabilities of the truncated words which from $T$ are given by:

Hence, as described earlier, using induction, for each $w^{\prime}_{(i)}$, $i=1,\ldots,r$

Let us consider the entire tree $T$ with its original words $w_{(1)},w_{(2)},\ldots,w_{(r)}$ and not $w_{\alpha}$. Note that for each $w_{(i)}$, $i=1,2,\ldots,r$

One may further notice that this is the same as $P_{Trie}(w_{(i)})=P_{Trie}(w_{(i)}|w_{\alpha})\times P_{Trie}(w_{\alpha})$, which implies that $\mathbb{E}[P_{Trie}(w_{(i)})]=\mathbb{E}[P_{Trie}(w_{(i)}|w_{\alpha})]\times\mathbb{E}[P_{Trie}(w_{\alpha})]$ since both of the random variables on the RHS are independent by definition. Also since $\mathbb{E}[\hat{p}_{\alpha}]=p_{(1)}+p_{(2)}+\ldots+p_{(r)}$, we can use Eqn.(9) and Eqn.(10) to get that, for each $w_{(i)}$, $i=1,\ldots,r$

Hence for each $w_{i}\in T$, $\mathbb{E}[\hat{p}_{i}]=p_{i}$ when $|\mathcal{S}|=k+1$.
\qed

While Theorem 3.1 justifies the use of Trie through equality of occurrence probability and the expected Trie probability at any stage of training, the next theorem provides a more desired result.

Theorem 3.2: For each $w_{i}\in\mathcal{S}$, $\hat{p}_{i}\xrightarrow{a.s.}p_{i}$ as $n\rightarrow\infty$.

Proof: Let $\eta_{j}$ denote a node of the Trie such that each time any one of the words $w_{(1)},\ldots w_{(\eta_{j})}$ from $\mathcal{S}$ is sampled and used for training, its $Counter$ variable is incremented by 1. Let $W_{\eta_{j}}=\{w_{(1)},\ldots w_{(\eta_{j})}\}$.
Define, a random variable $\mathbbm{1}_{n}^{\eta_{j}}$ such that,

For a fixed node $\eta_{j}$, $\mathbbm{1}_{n}^{\eta_{j}}$ are i.i.d random variables for $n\in\mathbbm{N}$. Also for each $n\in\mathbbm{N}$, $\mathbb{E}[\mathbbm{1}_{n}^{\eta_{j}}]=p_{(1)}+\ldots+p_{(\eta_{j})}$. Note that the $Counter$ variable of $\eta_{j}$ is actually $\sum_{i=1}^{n}{\mathbbm{1}_{i}^{\eta_{j}}}$. Hence by using the Strong Law Of Large Numbers,

With the above in mind, we proceed for induction over the number of words in $\mathcal{S}$.

Base Case: Let $\mathcal{S}$ contain two words $w_{1}$ and $w_{2}$ with occurrence probabilities $p_{1}$ and $p_{2}$. Then as in the previous theorem, we can get three cases which can be for our purposes be depicted by Fig.5. It is possible for $\eta_{0}$ to be the root note as well. It is also possible for exactly one of $\eta_{1}$ or $\eta_{2}$ to be a dummy node. This would cover all the three cases.
Now for $w_{1},$

Note that $Counter(\eta_{1},n)/n\xrightarrow[n\rightarrow\infty]{a.s.}p_{1}$ and that $Counter(\eta_{2},n)/n\xrightarrow[n\rightarrow\infty]{a.s.}p_{2}$. Hence, by using the Continuous Mapping Theorem [12], we get that

We can similarly show that $\hat{p}_{2}\xrightarrow[n\rightarrow\infty]{a.s.}p_{2}.$ Hence our base case i.e. $|\mathcal{S}|=2$ holds true.
The proof of the induction step is similar to that of Theorem 3.1 and is being skipped due to page constraint.
\qed

From Theorem 3.1 and Theorem 3.2 we conclude that from the perspective of Theory of Estimation and using the fact that almost sure convergence is stronger than convergence in probability, we get the following corollary

Corollary 3.3: For each $w_{i}\in\mathcal{S}$, the Trie probability $\hat{p}_{i}$ is an unbiased and consistent estimator of the occurrence probability $p_{i}$.

Through the results above, we can infer that the new Trie can learn the occurrence probabilities for any set of words through sufficient training which in turn implies that the new Trie can adapt to the texting and typing style of any user when deployed on either a mobile phone, laptop or any such other device.

In this section, we built upon the error correction schemes used in the baseline model.

In the paper, we first pointed out a a limitation in the Trie based probability generating model proposed in existing literature, to overcome which, we proposed a structural modification, a training algorithm and a probability generating scheme. We further proved rigorously that the new Trie generated probabilities are an unbiased and consistent estimator of the occurrence probabilities. These occurrence probabilities vary user to user which the new Trie is capable of adapting to. We performed simulations, the results of which strongly support both the presented theorems and demonstrated superiority in error correction.