言語処理学会 第24回年次大会 発表論文集 (2018年3月)

Automatic Flick Keyboard Error Correction Based on
GMM-LR-LM
Gang Qiao, Yihua Huang, Yabo Li, Jianmin Wu, Tianhuang SuEBG, Baidu Inc, China, 518052{qiaogang01, huangyihua, liyabo01, wujianmin01, sutianhuang}@baidu.com

1.Introduction
With the rapid development of mobile Internet,
Social apps is becoming more and more
important. As an indispensable app ofintelligent equipment, the input method is very
important and because of the limited size ofsmartphones, the auto-correction function hasbeen paid more and more attention by users.
Currently the most popular Japanese input
method in touch screen smartphone is flick
keyboard with kana-kanji convert. As showed inFigure 1, kanas and functional keys are assigned
to 12 keys. Each key expresses 3~5 kanas thatshare
generally
thesameconsonantcorresponding to one line in the gojūon order. A
user is supposed to enter a kana with vowel “a”
by tapping the key face, and rest kanas of thesame gojūon line by swiping to certain direction
for sub-keys. Although flick keyboard hasbigger key face size than QWERTY keyboard,the combination of tapping and swiping makes
errors happen more frequently. The probabilityof kana error is near to 10% per word according
to volunteers’ feedbacks，most of which aresubstitution errors. The substitution could be
any combination of neighboring keys and are
too hard to be enumerated by hand-written
rules.

Auto-correction [1] has been proposed
very early, with the purpose to find the users’
errors and correct them. Edit distance [2] is stillwidely used today. This algorithm is simple andeasy to understand. For example, if you type
“あ” but truly to have “か”, the substitution will
analyze the probability 𝑝(か|あ) which can betrained from corpus. But the performance is notvery good because of few features. [3] adopted
machine learning in spelling correction, but it
only applies to search engines.
Fortunately, we found that most of thesubstitution errors fall into two categories. One
is by tapping on or swiping to a wrong key, andthe other is by taking a tapping operation as aswiping one or vice versa. Therefore, theauto-correction problem consists of two parts.
Firstly, given a sequence of touch operations
that may contain substitution error, the most
likely button sequence should be identified.
Secondly, a series of kana sequences withprobability should be generated based on thebutton sequence. To address this problem, we
exploit the characteristics of touch screeninteraction and propose a probabilistic model
for flick keyboard auto-correction.

2. Methods
The GMM-LR-LM model is proposed to solve
this problem. GMM (Gaussian Mixture Model)
is used to map the input touch sequence to thebutton sequence set. LR (Logistic Regression)is used to map the button sequence to the kanasequence and the LM (Language Model such asN-gram) is used to adjust the final probability ofkana sequence.

Figure 1: The most popular Japanese Input Method― 947 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

formula below, where 𝑢, 𝜎 are the mean andstandard deviation of feature 𝑓.
𝑓−𝑢𝑓K =4
𝜎2.2 Correction ModelFigure 2: The framework of the proposed method

The paper framework is showed in Figure2, which can be divided into three parts:
Preprocessing, Correction Model and LM. In
the first part, the raw touch sequence data isextracted as a feature vector and normalized to astandard one. The correction work in done in
the second part and the third part deals withLM.

2.1. Preprocessing
2.1.1 Feature representation
In order to predict kana exactly, features arecollected such as touch point coordinate (𝑥, 𝑦)and touch duration. Different feature
combinations are used in different models.
Generally, a touch point can be represented as,𝑣 = 𝑥, 𝑦, 𝑑𝑢𝑟𝑎𝑡𝑖𝑜𝑛

1In our correction model GMM-LR, for a given
touch sequences 𝐸 = 𝑒O 𝑒P , … , 𝑒R , the output isto generate a number of kana sequences
𝐶T = 𝑐O 𝑐P , … , 𝑐R with probability 𝑝(𝐶V |𝐸). We
assume that each type activity is independent,
then we get,𝑝WRR=; 𝐶V 𝐸 ≈𝑝WRR=; 𝑐V 𝑒V𝑝WRR=; 𝑐V 𝑒V = 𝑝WRR 𝑏V |𝑒V 𝑝=; 𝑐V 𝑒V , 𝑏V

56where, p]^^ bT |eT is the probability ofbutton bT and p`a cT eT , bT is the conditional
probability of kana cT based on bT . Both willbe discussed in details below.
2.2.1 GMM: Probability of buttons.
Given a start point feature vector v, theprobability of button 𝑏V is denoted as 𝑝(𝑏V |𝑣).
In flick keyboard, we assume that the touchpoint coordinates of the button follow a twodimensional Gaussian distribution which provedby the stat of button “あ” from volunteers’
feedback, as shown in Figure 3.

The representation of a flick track only
consider a start point v5 and an end point v6 ,which is shown as,
𝑒 = 𝑣8 , 𝑣92

2.1.2 Normalization
As we know, smartphone screen resolution
varies and the inputs scale differently. But they
can be normalized to a standard one according
to the keyboard width and height.
𝑥;9<= 𝑦;9<=𝑥, 𝑦 =,3𝑤𝑖𝑑𝑡ℎ ℎ𝑒𝑖𝑔ℎ𝑡
where (𝑥;9<= , 𝑦;9<= ) is the real data
coordinate; (width, height) are the keyboard
width and keyboard height.
Different features have different units. Inorder to make the model training more efficient,continuous features are normalized by theFigure 3: The button touch coordinates

Therefore, GMM [4] with K Gaussian isadopted in our model, where K=12 according tothe flick keyboard. The probability of vector 𝑣
can be formulated as below,― 948 ―f𝑝 𝑣 =𝜙V 𝑁 𝑣|𝑢V , 𝛴V7VgOCopyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

𝑁 𝑣|𝑢V , 𝛴V =𝑒𝑥𝑝 −𝑣 − 𝑢V i 𝛴 jO (𝑣 − 𝑢V )282𝜋 𝛴The parameter 𝜙V is the weight of every
Gaussian distribution and 𝑢V , 𝛴V are the meanand variance of Gaussian distribution. For a
new given v, the probability of 𝑝 𝑏V 𝑣 can beformulated as,𝑝 𝑏V 𝑣 =𝜙V ∗ 𝑁 𝑣 𝑢V , 𝛴VfngO 𝜙n ∗ 𝑁 𝑣 𝑢n , 𝛴n

92.2.2 LR: conditional probability of kanas
Given a flick track 𝑒 , it is a key point todetermine the input is a tapping or a swiping.
The flick track can be represented as a vector inthe formula (1).
This problem can be modeled as a binaryclassification. LR [5] is adopted in the part.
1𝑝=; 𝑒 =101 + 𝑒𝑥𝑝 −𝑤 ∗ 𝑒
W is the parameters in LR model. Theoutput 𝑝=; 𝑒 can be regard as the swiping
probability, and thus typing probability is(1 − 𝑝=; 𝑒 ).

between the flick direction and corresponding
axis direction.
𝜋0𝑖𝑓 𝜃V >𝑤𝑒𝑖𝑔ℎ𝑡V =2 12𝑐𝑜𝑠𝑖𝑛𝑒 𝜃V𝑒𝑙𝑠𝑒

2.3 Language Model
Through the above model ， the touch point
sequences 𝐸 are converted to the kanas
sequences 𝐶V = (𝑐O , 𝑐P , … 𝑐R ) with probability
𝑝WRR=; 𝐶V |𝐸 . But in fact, the kanas itself are
not independent. The relations of kanas show inthe Figure 5,

Figure 5: Language model of kanas

So we can build the transition probability
model between kanas，and use this model tooptimize the probability. A character-levelN-gram language model for kana is calculatedbelow,
Rj•€O𝑝 𝐶V =𝑝 𝑐V 𝑐Vj•€O , … , 𝑐VjO

13VgO

The final model GMM-LR-LM can beseen as a linear combination of Language modeland Correction model. The probability kanasequence p CT E is formulated below,𝑝 𝐶V 𝐸 = 𝛼𝑝WRR=; 𝐶V 𝐸 +1 − 𝛼 𝑝•W;<R 𝐶V

Figure 4: the swiping axis

After we get the probability of swiping,which should be assigned to the four direction
kanas. It can be measured by the similarity ofvectors. As the Figure 4 shows, the −1, 0 ,0, 1 , 1, 0 , (0, −1) can be used to represent
the left, up, right and down direction vector
while (x6 − x5 , y6 − y5 ) is the flick direction
vector. Then the conditional probability
assignation can be formulated as below,
𝑝 𝑐V 𝑒, 𝑏 = 𝑝=; 𝑒 ∗𝑒𝑥𝑝t9VWuvw
t9VWuvx
yngO 𝑒𝑥𝑝

11

The weight T is determined by the angle θT

14

Finally ， we can search the words in
dictionary according to the kana sequence. The
model will generate more different kanasequences, and every sequence has a proper
probability. These probabilities can affect theorder of words.

3 Experiment
3.1 Data and Evaluation
The training dataset is constructed fromvolunteers’ feedbacks. An entry consists of the― 949 ―Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.

raw input trajectory and the original button thatthe keyboard recognizes. 101K entries are used
to train the GMM-LR model. Regarding the test
dataset, we invited a group of colleagues toinput specified sentences in hiragana by
conventional flick keyboard. If input error
happens, they are asked to keep it. Finally 5350
entries are collected for test dataset，including
510 wrong entries.
The test set of data are mapped to the samekeyboard layout input method, according to theauto-correction model of the input method,combined with the language model, calculate
the correct entry number of words and wrong
correct entry number. In fact, we only pay
attention on the first candidate from input
method applications. So if one case is good, thefirst candidate must equal to the target, else thiscase is bad. The evaluation measure isconventional Recall, Precision and F-score.

3.2 Experiment and Result
In Correction model, the conventional EM
algorithm is used to train the GMM model andK is set to 12 in MM. LR learning algorithm isSGD, and the loss function is cross-entropy.
N-gram is set to 3.
Table 1: The result of the contrast experiment

RecallPrecisionF-scoreThird-Party

58.8%

93.75%

72.3%

Rule-based

19.6%

90.5%

39.2%

GMM-LR-LM

72.5%

94.8%

82.2%

This table shows that GMM-LR-LM
improves the correction obviously. Comparison
to the traditional rule-based method, the recall
rate and F-score have been improved greatly,
the accuracy also has a certain promotion.
Meanwhile, compared with the third-party input
method (tens of millions of users), theindicators of new auto-correction model are
better, but the method of the third-party input
method is not published. However, the wrong
rate is still above 5%，these errors affect theuser experience very much. We need to consider
more advanced models to improve accuracy andrecall.

In the model, some of the features areassumed to be independent, ignoring theirinternal relations, but in practice this is not good
assumption. Therefore, more advanced models
can be considered and the potential
relationships between these features can beconstructed. For example, the GMM model andthe LR are calculated separately and can be
combined into a higher-dimensional GMM. Inaddition，the features are manually selected, we
can consider using deep learning models [6] tointroduce more hidden features.

4 Conclusion
In this research，we propose the GMM-LR-LM
auto-correction model for flick keyboard input.
The model adopts features originated fromtouch screen interaction and context featuresfrom language model to perform errorcorrection. The performance of auto-correction
has been greatly improved. Our future work willcontinue to optimize the model and to learn thelocal self-adaption of auto- correction.

Reference[1] Kukich K. Techniques for automatically correcting
words in text[J]. ACM Computing Surveys (CSUR),
1992, 24(4): 377-439.
[2] Wagner R A, Fischer M J. The string-to-stringcorrection problem[J]. Journal of the ACM (JACM),
1974, 21(1): 168-173.
[3] Cai F, De Rijke M. A survey of query autocompletion in information retrieval[J]. Foundationsand Trends® in Information Retrieval, 2016, 10(4):273-363.
[4] Ding Q, Han J, Zhao X, et al. Missing-dataclassification with the extended full-dimensional
Gaussian mixture model: Applications to EMG-based
motion recognition[J]. IEEE Transactions on
Industrial Electronics, 2015, 62(8): 4994-5005.
[5] Menard S. Applied logistic regression analysis[M].
Sage, 2002.
[6] Zhao, Dan, and Jian Sun. "Research on the
Automatic Error Correction Model Combined withArtificial Intelligence for College English Essays."
Journal of Residuals Science & Technology 13.5
(2016).

― 950 ―

Copyright(C) 2018 The Association for Natural Language Processing.
All Rights Reserved.