A Joint Graph Model for Pinyin-to-Chinese Conversion
with Typo Correction^††thanks:   This work was partially supported by the National Natural Science Foundation of China (Grant No.60903119, Grant No.61170114, and Grant No.61272248), the National Basic Research Program of China (Grant No.2013CB329401), the Science and Technology Commission of Shanghai Municipality (Grant No.13511500200), and the European Union Seventh Framework Program (Grant No.247619).

The daily life of Chinese people heavily depends on Chinese input method engine (IME), no matter whether one is composing an E-mail, writing an article, or sending a text message. However, every Chinese word inputted into computer or cellphone cannot be typed through one-to-one mapping of key-to-letter inputting directly, but has to go through an IME as there are thousands of Chinese characters for inputting while only 26 letter keys are available in the keyboard. An IME is an essential software interface that maps Chinese characters into English letter combinations. An efficient IME will largely improve the user experience of Chinese information processing.

Nowadays most of Chinese IMEs are pinyin based. Pinyin is originally designed as the phonetic symbol of a Chinese character (based on the standard modern Chinese, mandarin) , using Latin letters as its syllable notation. For example, the pinyin of the Chinese character “\song爱”(love) is “ài”. Most characters usually have unique pinyin representations, while a few Chinese characters may be pronounced in several different ways, so they may have multiple pinyin representations. The advantage of pinyin IME is that it only adopts the pronunciation perspective of Chinese characters so that it is simple and easy to learn. But there are only less than 500 pinyin syllables in standard modern Chinese, compared with over 6,000 commonly used Chinese characters, which leads to serious ambiguities for pinyin-to-character mapping. Modern pinyin IMEs mostly use a “sentence-based” decoding technique [4] to alleviate the ambiguities. “Sentence based” means that IME generates a sequence of Chinese characters upon a sequence of pinyin inputs with respect to certain statistical criteria.

Written in Chinese characters but not alphabets, spell checking for Chinese language is quite different from the same task for other languages. Since Chinese characters are entered via IME, those user-made typos do not immediately lead to spelling errors. When a user types a wrong letter, IME will be very likely to fail to generate the expected Chinese character sequence. Normally, the user may immediately notice the inputting error and then make corrections, which usually means doing a bunch of extra operations like cursor movement, deletion and re-typing. Thus there are two separated sub-tasks for Chinese spell checking: 1. typo checking for user typed pinyin sequences which should be a built-in module in IME, and 2. spell checking for Chinese texts in its narrow sense, which is typically a module of word processing applications [36]. These two terms are often confused especially in IME related works such as [4] and [34].

Pinyin typos have always been a serious problem for Chinese pinyin IMEs. The user may fail to input the completely right pinyin simply because he/she is a dialect speaker and does not know the exact pronunciation for the expected character. This may be a very common situation since there are about seven quite different dialects in Chinese, among which being spoken languages, six are far different from the standard modern Chinese, mandarin. With the boom of smart-phones, pinyin typos worsen due to the limited size of soft keyboard, and the lack of physical feedback on the touch screen. However, existing practical IMEs only provide small patches to deal with typos such as Fuzzy Pinyin [33] and other language specific errors [45].

Typo checking and correction has an important impact on IME performance. When IME fails to correct a typo and generate the expected sentence, the user will have to take much extra effort to move the cursor back to the mistyped letter and correct it, which leads to very poor user experience [15].

It is a rather long journey from the first English letter typed on the keyboard to finally a completed Chinese sentence generated by IME. We will first take an overview of the entire process.

The average length of pinyin syllables is about 3 letters. There are about 410 pinyin syllables used in the current pinyin system. Each pinyin syllable has a bunch of corresponding Chinese characters which share the same pronunciation represented by the syllable. The number of those homophones ranges from 1 to over 300. Chinese characters then form words. But word in Chinese is a rather vague concept. Without word delimiters, linguists have argued on what a Chinese word really is for a long time and that is why there is always a primary word segmentation treatment in most Chinese language processing tasks [40, 13, 41, 39, 42, 43]. A Chinese word may contain from 1 to over 10 characters due to different word segmentation conventions. Figure 1 demonstrates the relationship of pinyin and word, from pinyin letters “nihao” to the word “\song你好 (hello)”. Typically, an IME takes the pinyin input, segments it into syllables, looks up corresponding words in a dictionary and generates a sentence with the candidate words.

Non-Chinese users may feel confused or even surprised if they know that when typing pinyin through an IME, Chinese IME users will never enter delimiters such as “Space” key to segment either pinyin syllables or pinyin words, but just input the entire un-segmented pinyin sequence. For example, if one wants to input “\song你好世界 (Hello world)”, he will just type “nihaoshijie” instead of segmented pinyin sequence “ni hao shi jie”. Nevertheless, pinyin syllable segmentation is a much easier problem compared to Chinese word segmentation. Since pinyin syllables have a very limited vocabulary and follow a set of regularities strictly, it is convenient to perform pinyin syllable segmentation by using rules. But as the pinyin input is not segmented, it is nearly impossible to adopt previous spell checking methods for English to pinyin typo checking, although techniques for English spell checking have been well developed. A bit confusing but interesting, pinyin typo correction and segmentation come as two sides of one problem: when a pinyin sequence is mistyped, it is unlikely to be correctly segmented; when it is segmented in an awkward way, it is likely to be mistyped.

Inspired by [36] and [14], we adopt the graph model for Chinese spell checking for pinyin segmentation and typo correction, which is based on the shortest path word segmentation algorithm [1]. The model has two major steps: segmentation and correction.

PTC conversion has long been viewed as a decoding problem using HMM. We continue to follow this formalization. The best Chinese character sequence $W^{*}$ for a given pinyin syllable sequence $S$ is the one with the highest conditional probability $P\left(W\right|S)$ that

In the HMM for pinyin IME, observation states are pinyin syllables, hidden states are Chinese words, emission probability is $P\left(s_i\right|w_i)$, and transition probability is $P\left(w_i\right|w_{i-1})$. Note the transition probability is the conditional probability between words instead of characters. PTC conversion is to decode the Chinese word sequence from the pinyin sequence. The Viterbi algorithm [26] is used for the decoding.

The shortest path algorithm for typo correction and Viterbi algorithm for PTC conversion are very closely related. It has been strictly proven by [8] that the sequence decoding problem on HMM is formally identical to finding a shortest path on a certain graph, which can be constructed in the following manner.

Consider a first order HMM with all possible observations $𝕆=\left\{o_1,o_2,\mathrm{\dots },o_M\right\}$, hidden states $𝕊=\left\{s_1,s_2,\mathrm{\dots },s_N\right\}$, a special start state $s_0$, emission probabilities $\left({ℰ}_{s_i,o_k}\right)=P\left(o_k\right|s_i)$, transition probabilities $\left({𝒯}_{s_i,s_j}\right)=P\left(s_j\right|s_i)$, and start probabilities $\left({𝒮}_{s_i}\right)=P\left(s_i\right|s_0)$. For an observation sequence of $T$ time periods $Y=\left\{y_1,y_2,\mathrm{\dots },y_T|y_t\in 𝕆,t=1,\mathrm{\dots },T\right\}$, the decoding problem is to find the best corresponding hidden state sequence $X^{*}$ with the highest probability, i.e.,

Then we will construct a DAG $G=\left(𝕍,𝔼\right)$ upon the HMM. The vertex set $𝕍$ includes:

• •

  Virtual start vertex $v_0$ and end vertex $v_E$ with vertex weight of 0;

• •

  Normal vertices $v_{x_t}$, where $t=1,\mathrm{\dots },T$, and $\forall x_t\in 𝕊$. The vertex weight is the negative logarithm of emission probability:

  $$w_{v_{x_t}}=-\log {ℰ}_{x_t,y_t}.$$

The edge set $𝔼$ includes:

• •

  Edges from the start vertex $E(v_0\to v_{x_1})$ with edge weight

  $$W_{E(v_0\to v_{x_1})}=-\log {𝒮}_{x_1},$$

  where $\forall x_1\in 𝕊$;

• •

  Edges to the end vertex $E(v_{x_T}\to v_E)$ with vertex weights of 0;

• •

  Edges between adjacent time periods $E(v_{x_{t-1}}\to v_{x_t})$ with edge weight

  $$W_{E(v_{x_{t-1}}\to v_{x_t})}=-\log {𝒯}_{x_{t-1},x_t},$$

  where $t=2,\mathrm{\dots },T$, and $\forall x_t,x_{t-1}\in 𝕊$.

The shortest path $P^{*}$ from $v_0$ to $v_E$ is the one with the least sum of vertex and edge weights, i.e.,

The optimization goal of $P^{*}$ in Equation (3.3) is identical to that of $X^{*}$ in Equation (1).

Given HMM decoding problem is identical to SSSP problem on DAG, we propose a joint graph model for PTC conversion with typo correction. The joint graph model aims to find the global optimal for both PTC conversion and typo correction on the entire input pinyin sequence. The graph $G=\left(𝕍,𝔼\right)$ is constructed based on graph $G_c$ for typo correction in Section 3.2. The vertex set $𝕍$ consists of the following parts:

• •

  Virtual start vertex $V_0$ and end vertex $V_E$ with vertex weight of 0;

• •

  Adjacent pinyin syllables in $G_c$ are merged into pinyin words. Corresponding Chinese words are fetched from a PTC dictionary ${𝔻}_c$, which is a dictionary maps pinyin words to Chinese words, and added as vertices:

  $$\left\{V_{i,j}|\forall V_{i,j}\in {𝔻}_c\left[S_i^{\prime }\mathrm{\dots }{S}_j^{\prime }\right],i\le j\right\};$$

  The vertex weight consists of two parts: 1. the vertex weights of syllables in $G_c$, and 2. the emission probability:

  	$w_{V_{i,j}}=$	$\beta {\displaystyle \sum _{k=i}^j}ℒ\left(S_k^{\prime },S_k\right)$
  		$-\gamma \log P\left(S_i^{\prime }\mathrm{\dots }{S}_j^{\prime }\right|V_{i,j});$

If the corresponding pinyin syllables in $G_c$ have an edge between them, the vertices in $G$ also have an edge:

The edge weights are the negative logarithm of the transition probabilities:

Although the model is formulated on first order HMM, i.e., the LM used for transition probability is a bigram one, it is easy to extend the model to take advantage of higher order $n$-gram LM, by tracking longer history while traversing the graph.

Computing the shortest path from $V_0$ to $V_E$ on $G$ yields the best pinyin-to-Chinese conversion with typo correction result. Considering our running example, the graph $G$ is shown in Figure 4.

The joint graph is rather huge and density. According to our empirical statistics, when setting threshold $T=2$, for a sentence of $M$ characters, the joint graph will have $\left|𝕍\right|=M\times 1,000$, and $\left|𝔼\right|=M\times 1,000,000$.

To reduce the scale of graph $G$, we filter graph $G_c$ by searching its $K$-shortest paths first to get $G_c^{\prime }$ and construct $G$ on top of $G_c^{\prime }$. Figure 5 shows the 3-shortest paths filtered graph $G_c^{\prime }$ and Figure 6 shows the corresponding $G$ for our running example. The scale of graph may be thus drastically reduced.

An efficient heap data structure is required in $K$-shortest paths algorithm [7] for backtracking the best paths to current vertex while traversing. The heap is implemented as a priority queue of size $K$ sorted according to path length that should support efficient push and pop operations. Fibonacci heap [9] is adopted for the heap implementation since it has a push complexity of $O\left(1\right)$ which is better than the $O\left(K\right)$ for other heap structures.

Another benefit provided by $K$-shortest paths is that it can be used for generating $N$-best candidates of PTC conversion, which may be helpful for further performance improvement.

The corpus for evaluation is the one provided in [35], which is originally extracted from the People’s Daily corpus and labeled with pinyin. The corpus has already been split into training \mscTrain, development \mscDev and test \mscTest sets as shown in Table 1.

SRILM [25] is adopted for language model training and KenLM [12, 11] for language model query. The Chinese part of the corpus is segmented into words before LM training. Maximum matching word segmentation is used with a large word vocabulary $𝒱$ extracted from web data provided by [28]. The pinyin part is segmented according to the Chinese part. This vocabulary $𝒱$ also serves as the PTC dictionary. The original vocabulary is not labeled with pinyin, thus we use the PTC dictionary of sunpinyin¹¹http://code.google.com/p/sunpinyin/ which is an open source Chinese pinyin IME, to label the vocabulary $𝒱$ with pinyin. The emission probabilities are estimated using the lexical translation module of MOSES [17] as “translation probability” from pinyin to Chinese.

We will use conventional sequence labeling evaluation metrics such as sequence accuracy and character accuracy²² We only work on the PTC conversion part of IME, thus we are unable to use existing evaluation systems [15] for full Chinese IME functions..

Chinese characters in a sentence may be separated by digits, punctuation and alphabets which are directly inputted without the IME. We follow the so-called term Max Input Unit (MIU), the longest consecutive Chinese character sequence proposed by [15]. We will mainly consider MIU accuracy (MIU-Acc) which is the ratio of the number of completely corrected generated MIUs over the number of all MIUs, and character accuracy (Ch-Acc), but the sentence accuracy (S-Acc) will also be reported in evaluation results.

We will also report the conversion error rate (ConvER) proposed by [44], which is the ratio of the number of mistyped pinyin word that is not converted to the right Chinese word over the total number of mistyped pinyin words³³ Other evaluation metrics are also proposed by [44] which is only suitable for their system since our system uses a joint model.

Firstly we build a baseline system without typo correction which is a pipeline of pinyin syllable segmentation and PTC conversion. The baseline system takes a pinyin input sequence, segments it into syllables, and then converts it to Chinese character sequence.

The pinyin syllable segmentation already has very high (over 98%) accuracy with a trigram LM using improved Kneser-Ney smoothing. According to our empirical observation, emission probabilities are mostly 1 since most Chinese words have unique pronunciation. So in this step we set $\gamma =0$. We consider different LM smoothing methods including Kneser-Ney (KN), improved Kneser-Ney (IKN), and Witten-Bell (WB). All of the three smoothing methods for bigram and trigram LMs are examined both using back-off models and interpolated models. The number of $N$-best candidates for PTC conversion is set to 10. The results on \mscDev are shown in Figure 7 in which the “-i” suffix indicates using interpolated model. According to the results, we then choose the trigram LM using Kneser-Ney smoothing with interpolation.

The choice of the number of $N$-best candidates for PTC conversion also has a strong impact on the results. Figure 8 shows the results on \mscDev with different $N$s, of which the $N$ axis is drawn in logarithmic scale. We can observe that MIU-Acc slightly decreases while $N$ goes up, but Ch-Acc largely increases. We therefore choose $N=10$ as trade-off.

The parameter $\gamma$ determines emission probability. Results with different $\gamma$ on \mscDev is shown in Figure 9, of which the $\gamma$ axis is drawn in logarithmic scale. $\gamma =0.03$ is chosen at last.

We compare our baseline system with several practical pinyin IMEs including sunpinyin and Google Input Tools (Online version)⁴⁴http://www.google.com/inputtools/try/. The results on \mscDev are shown in Table 2.

Based upon the baseline system, we build the joint system of PTC conversion with typo correction.

We simulate user typos by randomly generating errors automatically on the corpus. The typo rate is set according to previous Human-Computer Interaction (HCI) studies. Due to few works have been done on modeling Chinese text entry, we have to refer to those corresponding results on English [32, 22, 6], which show that the average typo rate is about 2%. [44] performed an experiment that 2,000 sentences of 11,968 Chinese words were entered by 5 native speakers. The collected data consists of 775 mistyped pinyin words caused by one edit operation, and 85 caused by two edit operations. As we observe on \mscTrain that the average pinyin word length is 5.24, then typo rate in the experiment of [44] can be roughly estimated as:

which is similar to the conclusion on English. Thus we generate corpora from \mscDev with typo rate of 0% (0-P), 2% (2-P), and 5% (5-P) to evaluate the system.

According to [44] most mistyped pinyin words are caused by one edit operation. Since pinyin syllable is much shorter than pinyin word, this ratio can be higher for pinyin syllables. From our statistics on \mscTrain, with 2% randomly generated typos, . Thus we set the threshold $T$ for $ℒ$ to 2.

We first set $K$-shortest paths filter to $K=10$ and tune $\beta$. Results with different $\beta$ are shown in Figure 13.

With $\beta =3.5$, we select $K$. Results with different $K$ are shown in Figure 17. We choose $K=20$ since there is no significant improvement when $K>20$.

The selection of $K$ also directly guarantees the running time of the joint model. With $K=20$, on a normal PC with Intel Pentium Dual-Core E6700 CPU, the PTC conversion rate is over 2000 characters-per-minute (cpm), which is much faster than the normal typing rate of 200 cpm.

With all parameters optimized, results on \mscTest using the proposed joint model are shown in Table 3 and Table 4. Our results are compared to the baseline system without typo correction and Google Input Tool. Since sunpinyin does not have typo correction module and performs much poorer than our baseline system, we do not include it in the comparison. Though no direct proofs can be found to indicate if Google Input Tool has an independent typo correction component, its outputs show that such a component is unlikely available.

Since Google Input Tool has to be accessed through a web interface and the network connection cannot be guaranteed. we only take a subset of 10K sentences of \mscTest to perform the experiments, and the results are shown in Table 3.

The scores reported in [44] are not listed in Table 4 since the data set is different. They reported a ConvER of 53.56%, which is given here for reference.

Additionally, to further inspect the robustness of our model, performance with typo rate ranges from 0% to 5% is shown in Figure 18. Although the performance decreases while typo rate goes up, it is still quite satisfying around typo rate of 2% which is assumed to be the real world situation.