{'fraction_non_alphanumeric': 0.02466748696314525, 'fraction_numerical': 0.007587742426905725, 'mean_word_length': 4.707239592041464, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Empirical Study of Non-Stationary Ngram Model and its Smoothing Techniques

Recently many new techniques have been proposed for language modeling, such as ME, MEMM and CRF. However, the ngram model is still a staple in practical applications. It is well worthy of studying how to improve the performance of the ngram model. This paper enhances the traditional ngram model by relaxing the stationary hypothesis on the Markov chain and exploiting the word positional information. Such an assumption is made that the probability of the current word is determined not only by history words but also by the words positions in the sentence. The non-stationary ngram model (NS ngram model) is proposed. Several related issues are discussed in detail, including the definition of the NS ngram model, the representation of the word positional information and the estimation of the conditional probability. In addition, three smoothing approaches are proposed to solve the data sparseness problem of the NS ngram model. Several smoothing algorithms are presented in each approach. In the experiments, the NS ngram model is evaluated on the pinyin-to-character conversion task which is the core technique of the Chinese text input method. Experimental results show that the NS ngram model outperforms the traditional ngram model significantly by the exploitation of the word positional information. In addition, the proposed smoothing techniques solve the data sparseness problem of the NS ngram model effectively with great error rate reduction.


Introduction
Statistical language model plays an important role in natural language processing. It has a wide range of applications in many domains, such as speech recognition [Jelinek 1997], OCR [Kolak et al. 2003], machine translation , and pinyin-to-character conversion [Gao et al. 2005;Xiao et al. 2005] etc. In recent years, great efforts are devoted to the research of language modeling. Many novel techniques are proposed, such as maximum entropy model [Rosenfeld 1994], maximum entropy Markov model [McCallum et al. 2000] and conditional random field model [Lafferty et al. 2001]. However, the ngram model is still a staple in practical applications. Therefore, it is well worthy of studying how to improve the performance of the ngram model.
The ngram model takes the word sequence as a Markov chain. It makes the Markov hypothesis on the sequence so as to simplify the probability inference. There are actually two hypotheses implied by the Markov hypothesis, named the limited history hypothesis and the stationary hypothesis [Manning and Schutze 1999]. The first one assumes that the probability of the current word is determined only by a few of previous words, but irrelevant to the whole history of words. The second one assumes that the word probability is irrelevant to the actual word positions in the sentence.
The most obvious extension to the traditional ngram model is simply to enlarge the number of history words and build up the higher-order ngram model [Carpenter 2005].
However, the high-order ngram model suffers from the curse of dimensionality [Novak and Ritter 1998]. The bigram model and the trigram model are currently two prevalent language models.
From another point of view, the paper relaxes the stationary hypothesis and enhances the traditional ngram model by exploiting the word positional information. It is based on the philosophy that most words are not only constrained by their contextual information, but also influenced by their positions in the sentence. For example, the Chinese word "首先" (first of all) is usually used to start a sentence, but rarely occurs elsewhere in the sentence. Then higher probability should be assigned to it by a language model when it is in the front of a sentence, and lower probability elsewhere. Moreover, some of punctuations, such as full stop and exclamation, always appear at the end of a sentence. So it may be mistaken for a Chinese sentence that the exclamation appears in the middle of it. Therefore, a language model can benefit from modeling the word positional information.
NS ngram model effectively with great error rate reduction.
The remaining part of the paper is organized as follows. The related works are outlined in section 2. In section 3, the NS ngram model is proposed and several related issues are discussed in detail. In section 4, the data sparseness problem of the NS ngram problem is addressed and three smoothing approaches are proposed. The experimental results and discussions are presented in section 5 and the conclusion is drawn in section 6.

Related Works
There are many ways to improve the performance of the ngram model. The most obvious way is to relax the limited history hypothesis and build up the high-order ngram model, which has been discussed in the above section. Another way is to construct the skipping ngram model [Rosenfeld 1994;Ney et al. 1994], in which the current word is constrained by the skipped words in the word history, other than the adjacent words. The skipping ngram model can exploit more information of history words and avoid the curse of dimensionality meanwhile.
In the experiments, it yields limited improvements by interpolating with the traditional ngram model.
The class-based ngram model ] is constructed based on word cluster instead of word. The syntax and semantic information can be well captured in this way.
Meanwhile, the parameter space is reduced greatly and the data sparseness problem is alleviated. However, the predictive capability of the class-based ngram model is much lower than the traditional ngram model due to its small parameter space. It usually achieves limited improvements by interpolating with the traditional ngram model.
The cache-based ngram model [Kuhn 1988;Kuhn and Mori 1990] assumes that people tends to use words as few as possible in the article. If a word has been used, it would possibly be used again in the future. The cache-based ngram model is usually utilized to construct a self-adaptive language model.

Non-Stationary Ngram Model
This section firstly reviews the traditional ngram model briefly. Secondly, it defines the NS ngram model formally. Thirdly, the word positional information is formalized. Finally, the estimation method is provided for the conditional probability of the NS ngram model.

Ngram Model
Language model aims to determine the probability of the sequence of words. The sequence probability is usually decomposed into the conditional probabilities of words which are where , ij lp w is the i th word in the lexicon and appears at the j th position in sequence S.
The ngram model makes the Markov hypothesis on the sequence so as to simplify formula (1). The procedures are described in formula (2) Actually, there are two hypotheses implied by the Markov hypothesis: 1. The limited history hypothesis: the probability of current word is dependent only on the previous n-1 words, but irrelevant to the whole history of words.
2. The stationary hypothesis: the word transition probability is determined only by the words which consist of the transition probability, but irrelevant to the positions where these words possess in the sequence.
Formula (1) is firstly simplified by the limited history hypothesis, resulted in the second item of formula (2). Then, the stationary hypothesis is applied on it and the final form of the ngram model is obtained, as represented by the last item of formula (2). The paper substitutes i l w for , ij lp w since the conditional probability is irrelevant to word position. In literature, the limited history hypothesis is referred to frequently, but seldom is the stationary hypothesis.
The most obvious way to extend the ngram model is simply to relax the limited history hypothesis and involve more history information of words. The higher-order ngram model is built up. However, the high-order ngram model suffers from the curse of dimensionality. As the model order increases, the parameter space explodes at an exponential rate. The data sparseness problem becomes very severe which hampers its applications gravely. From another point of view, the paper relaxes the stationary hypothesis and enhances the ngram model by the exploitation of the word positional information. The NS ngram model is proposed. It is described in the following sections.

NS Ngram Model
As presented in section 1, the occurrence of words is relevant to their positional information in sentence. It is beneficial for the language model to exploit the positional information to determine the word probability. However, the Markov hypothesis is too restricted to exploit the positional information due to its stationary assumption. The paper relaxes the stationary hypothesis of the traditional ngram model and proposes a non-stationary ngram model. The NS ngram model is formulized in as below: In the NS ngram model, formula (1) is simplified merely by the limited history hypothesis, rather than the stationary hypothesis. The conditional probability of the current word is determined not only by history words but also by the words' positions in sentence. The paper uses a single positional variable of t to denote the word positional information in formula (3).
The traditional ngram model is a special case of the NS ngram model in which t is a constant.
Important things for the NS ngram model are how to calculate the value of t and how to estimate the conditional probability of word in formula (3).

Representation of t
Since t denotes the word positional information in a sentence, it is a natural way to take the word position index as the concrete value of t. However, there are two serious problems with this method. Firstly, index has different meanings in sentences of different lengths. For example, there are two English sentences: "Yesterday I saw you" and "Yesterday I saw you were looking around here". In both of the sentences, the word "you" has the same position index -4. However, "you" appears at the end of the first sentence, while it is in the middle in the second. It possesses completely different positional information in these two sentences.
Secondly, since a sentence may have arbitrary length, the t value can be any natural number.
But computer can not deal with infinite value.
A refined method is to use the ratio of the word position index to the sentence length, which maps t into a real number in the range of [0, 1]. But there are infinite real numbers in that range and it can not make statistics based on each real number.
This paper divides the above range into several equivalent classes (bins). It assumes that the words in each bin share the same positional information. The value of t is set to the index of the according class. More formally, the above procedures are described as below: 1. Calculate the ratio of the word position index to the sentence's length, which maps t into the range of [0, 1].
2. Divide the range into several bins. The words in each bin share the same positional information.
3. Set the t value of current word as the index of the according bin. Figure 1 shows an example of the above procedures:

Figure 1. Calculation of the t value in NS ngram model
From the above procedures, the more number of bins it divides of the word sequence, the more accuracy of the positional information is extracted from the sentence.

Training Method
The section discusses how to estimate the conditional probability in formula (3) In order to calculate the probability of a sentence, the t value is firstly obtained for each word. Then, the conditional probability of word is computed according to formula (4). Finally, the sentence probability is calculated by formula (3). The traditional ngram model is a special case of the NS ngram model in which there is only one bin.

Smoothing Techniques
As shown in section 3.4, there are totally k traditional ngram models in the NS ngram model with k bins. The space complexity of the NS ngram model is consequently k times more than the traditional ngram model. Data sparseness problem is an inherent and severe problem in the traditional ngram model . Therefore, it is more severe in the NS ngram model. Figure 2 illustrates the data sparseness problem in the NS ngram model.

Figure 2. Data sparseness problem in NS ngram model
In Figure 2, the color of deep shade indicates that the data sparseness problem is severe in the NS ngram model, while the color of light shade means that the problem is not severe.
As shown in Figure 2, there are two main factors in determining the degree of the data sparseness problem in the NS ngram model. They are the model order n and the bin number k.
As n (or k) increases, the problem becomes more severe, and the estimated probability becomes more unreliable.
It is necessary to start with these two factors to solve the data sparseness problem of the NS ngram model. Considering the factor of the model order which is represented as the vertical axis in Figure 2, the high-order NS ngram model can be smoothed by lower-order NS ngram model, just as the traditional smoothing techniques do. It is our first smoothing approach. Considering the factor of the bin number which is shown as the horizontal axis, there are two ways to design the smoothing methods. The first way, the NS ngram model with larger value of k can be smoothed by the NS ngram model with smaller value of k. In particular, the traditional ngram model (k=1) can be utilized to smooth the NS ngram model (k>1). It is our second smoothing approach. The second way, the paper builds up a more compact form of the NS ngram model. It firstly constructs some statistical variables of the word positional information from the bins of the NS ngram model. Then, it calculates a weight from these variables for the traditional ngram probability. The weight is used to substitute for the concrete positional information which tends to cause the data sparseness problem in the NS ngram model. It is our third approach to smooth the NS ngram model. Until now, three smoothing approaches have been provided in sketch. They will be described in the following sections in detail.

The First Approach
Since the NS ngram model is composed of several traditional ngram models, each of these component ngram models can be smoothed separately by the traditional smoothing techniques.
The traditional smoothing techniques have been well studied before. Many smoothing algorithms have been proposed, such as the additive smoothing [Jeffreys 1948], the Good-Turing smoothing [Good 1953], the back-off smoothing [Katz 1987], the linear interpolation smoothing [Jelinek and Mercer 1980], the Kneser-Ney smoothing [Kneser and Ney 1995], and so on. Generally, they smooth the unreliable probabilities in the high-order ngram model by the reliable probabilities in the low-order ngram model. The paper can not try each existent smoothing algorithm on the NS ngram model. Three popular algorithms are taken in the paper. They are the additive smoothing, the back-off smoothing and the linear interpolation smoothing. The NS bigram model is taken as an example and the formulas are listed as below.
Additive smoothing: Cwwtis calculated to be zero according to formula (9) because N(C+1) is equal to zero. It is obviously wrong. In this paper, a simple strategy is adopted to address the problem. Formula (7) and formula (9) are adopted only for the small value of C (i.e. below a threshold). For the large value of C, it is regarded that the bigram probabilities can be estimated reliably according to the word frequencies and they need not to be smoothed. The MLE principle is applied on them directly.
In formula (6), α is the coefficient for normalization and it is calculated as below: P is the probability of the NS bigram model which is estimated by formula (4); l(t) is the coefficient which is a function of t and can be estimated by the EM algorithm on the held-out corpus.

The Second Approach
As shown in Figure 2, when the value of k increases, there are more probability distributions in the NS ngram model to be estimated on the training corpus. The conditional probability becomes more specific and unreliable, and the data sparseness problem of the NS ngram model becomes more severe. Usually, the smoothing techniques utilize the general and reliable probability distributions to smooth the specific and unreliable ones. Therefore, it can make use of the reliable probability of the NS ngram model with small k, to smooth the unreliable probability of the NS model with large k. In particular, it can utilize the traditional ngram model (k=1) to smooth the NS ngram model (k>1). However, the traditional ngram model also suffers from the data sparseness problem. Actually, the paper utilizes the smoothed traditional ngram model in this approach.
Totally, three smoothing methods are investigated. They are the back-off method, the linear interpolation method and the hybrid method. The formulas are listed as below.
Back-off smoothing: α 1 is the coefficient for normalization, and it can be calculated as below: Pwwis the traditional bigram probability smoothed by the linear interpolation method, and it is calculated by formula (20): The coefficients of l(t) and q can be optimized by the EM algorithm on the held-out corpus.
Hybrid smoothing: Pwwtis the NS bigram probability smoothed by the back-off method, and it can be calculated by formula (6)

The Third Approach
The above sections provide two smoothing approaches for the NS ngram model. They are mainly based on the traditional smoothing techniques. This section proposes a novel smoothing method and constructs a more compact model to solve the data sparseness problem of the NS ngram model. Figure 2, the model order and the bin number are two main factors in determining the degree of the data sparseness problem in the NS ngram model. The first one is also the dominant factor of the traditional ngram model. Then, the data sparseness in the NS ngram model, which is brought forth by the first factor, can be regarded as inheriting from the traditional ngram model. The second factor is specific to the NS ngram model. It brings forth the data sparseness problem when the positional information is modeled. Based on the above analysis, the smoothing method for the NS ngram model can be decomposed into two steps.

As shown in
The first step is to solve the data sparseness problem which is brought forth by modeling the word positional information. Some statistical variables are constructed to substitute for the concrete positional information. A more compact model is built up. The second step is to solve the data sparseness problem which is inherited from the traditional ngram model. The traditional smoothing techniques are utilized.
After describing the motivation and the technique sketch, the formula is presented as below:   for the bigram probability according to these variables. Such an assumption is made that more weight should be awarded if the current word position fits in better with the training corpus, and less weight vice versa. According to the assumption, the term of t-E(w li ), which defines the difference between the current word position and its average position in the training corpus, is adopted in formula (22). As the value decreases, t fits in with the training corpus better and more weight should be awarded. Henceforth, the weight function is descendent with the value of t-E(w li ) as formula (22) shows. Moreover, the weight function is ascendant with the variance V(w li ). The term V(w li ) is mainly used to balance the value of the term t-E(w li ) for some active words. For example, some adjectives can appear at any position in a sentence.
Then it is unreasonable to decrease the weight just as the term t-E(w li ) increases. In such a situation, the value of V(w li ) of the active word is usually bigger than that of the inactive. Then it can provide a balance for the value of t-E(w li ). Until now, the section has described the method to solve the data sparseness problem which is brought forth by modeling the word positional information. It is the first step of this approach to smooth the NS ngram model. It should be noticed that the way to constructing the weight is a purely empirical method. There is no theoretic foundation on it. However, it performs pretty well in the experiments, as presented later in section 5.4.3. In the second step, the traditional smoothing techniques can be adopted to solve the data sparseness problem which inherits from the traditional ngram model.
The paper investigates two smoothing techniques: the back-off smoothing and the linear interpolation smoothing.
Moreover, the coefficients of α and β can be optimized by some automatic methods on the held-out corpus. The genetic algorithm is adopted in this paper. It is presented as below: Algorithms: Genetic algorithm to optimize α and β

Input: The held-out corpus
Output: The optimal value of α and β 1. Initiation: generate the initial population of α and β randomly 2. Evolution of population Step 1: calculate fitness for each individual Step 2: selection Step 3: crossover Step 4: mutation Step 5: if termination criterion is met go to 3 else go to step 1

Choose the best individual as the solution
The actual performance of formula (22) on the held-out corpus is taken as the fitness function in the above algorithm.
Until now, a compact NS ngram model has been built up in the section. The parameter space is reduced by substituting the statistical variables for the concrete positional information, which results in a space complexity of O(l n +2l+2). The data sparseness problem is alleviated.
However, the predictive capability is also lowered to some extent due to the small parameter space, which is the limitation of this smoothing approach. To overcome the above drawback, the paper constructs the statistical variables for the word ngram other than for the word itself.
It results in a larger space complexity of O(3´l n ), and therefore yields a more powerful predictive capability. In addition, the compact model has a slight higher time complexity than the normal NS ngram model by calculation of the weight function.

Experiments and Discussions
This section evaluates the NS ngram model and its smoothing techniques on the pinyin-to-character conversion task which is the core technique of the Chinese keyboard input method. The section is organized as follows. Firstly, the task and the data set are described.
Secondly, the non-stationary property of words is investigated in a statistical way so as to verify the motivation of the paper. Thirdly, the performance of the NS ngram model is presented and compared with the traditional ngram model. Finally, the smoothing algorithms proposed in the paper are evaluated and the performances of the smoothed NS ngram model are provided.

Task and Data Set Description Task Description
The standard keyboard is initially designed for native English speakers. In Asia, such as China, Japan and Thailand, people can not input their language through the standard keyboard directly. Asian text input becomes the challenge for the computer users in Asia. Asian language input method is one of the most important techniques in Asian language processing.
The pinyin-based input method is the most important Chinese text input method. There are over 97% of Chinese computer users using pinyin to input Chinese text [Chen 1997].
According to the scale of the input unit, the pinyin-based input method can be categorized into three types: the character-level input method, the word-level or phrase-level input method and the sentence-level input method respectively. The sentence-level input method becomes the most prevalent pinyin-based input method due to its high precision. The pinyin-to-character conversion task aims to convert the sequence of pinyin strings into one Chinese sentence. It is the core technique of the sentence-level pinyin-based Chinese text input method. Therefore, the improvement on the pinyin-to-character conversion task has a great effect on Chinese text input method.
In Chinese, there are totally 410 pinyin symbols (without the tone information) which correspond to more than 30,000 Chinese characters. For a certain inputted pinyin sequence, there are many candidates of Chinese character sequence corresponding to it, but only one is what the user really wants to obtain. Language model is to select the most probable one among these candidates. Error rate is usually used to evaluate the performance of a language model on this task.
The pinyin-to-character conversion task can also be taken as a simplified automatically speech recognition task [Gao et al. 2005]. Both of the two tasks aim to convert the phonetic information into the character sequence. However, unlike the speech recognition task, the pinyin-to-character conversion task doesn 't have to deal with the acoustic ambiguity because the pinyin strings are directly inputted on the keyboard by user. Therefore, our techniques also illuminate to the speech recognition task.

Text Corpus
The paper chooses the 6763 Chinese frequent characters as lexicon.

People's Daily corpus in 2000
1-11 months 2.27´10 7 1/3 of 12 th month 7.01´10 5 2/3 of 12 th month 1.40´10 6 The paper chooses the large scale of corpus for the NS trigram model since its parameter space is much larger than that of the NS bigram model. In what follows, the paper presents the distributions of the lengths of the sentences in those corpora. The information is crucial to evaluating the NS ngram model which exploits the positional information of word in the sentences. The distributions are presented in Figure 3.

Pinyin Corpus
The pinyin corpus is necessary for evaluating the NS ngram models on the pinyin-to-character conversion task. The paper gets the pinyin corpus from the above text corpus by a conversion toolkit 1 which yields 99.7% accuracy evaluated on a golden corpus. When the NS ngram models are evaluated, the pinyin corpus is firstly converted into the text corpus by the NS ngram model. Then, the converted results are compared with the standard text corpus and the error rate is calculated. As the pinyin corpus is not a golden corpus, the errors in the pinyin corpus could lead to the conversion error of the NS ngram model. Therefore, the actual error rate of the NS ngram model is a little lower than the reported results in the paper and the NS ngram model could get a little better performance in the real system. However, since there are not many errors in the pinyin corpus because of the high precision of the conversion toolkit, the reported error rate of the NS ngram model can be regarded to be close enough to the actual error rate.

Non-Stationary Property of Words
Section 1 has provided some intuitive examples for the non-stationary property (NS property) of words. However, the intuition is not enough for our motivation of the paper. The section will further present some statistical evidences.
The NS property assumes that word behaves differently in different portions of sentences.
Then their probability distributions would be different in different portions. The more differences between these distributions, the more positional information has been implied by word. The section investigates the probability distributions in the NS bigram model, and presents their differences by comparing them with the distribution in the traditional bigram model. The Kullback-Leibler (KL) distance [Cover and Thomas 1991]     According to the experimental results in Table 2, it is found that as k increases, the average KL distance becomes larger and larger, indicating that there are more and more differences between the distributions of the NS bigram model and that of the traditional bigram model. Therefore, more and more positional information is modeled by the NS bigram model, and more predictive capability is expected. Moreover, focusing on a certain column in   The NS trigram model is also investigated. The experimental results are presented in Table 4. The experimental results are similar to those of the NS bigram model. As presented in Table 4, the NS trigram model outperforms the traditional trigram model significantly in the close test, and has achieved as much as 28.96% error rate reduction. It proves that the NS trigram model is more powerful than the traditional trigram model. Moreover, the error rate decreases along with the k value, proving that the improvements of the NS trigram model are

Experiments of Smoothing Techniques
This section firstly investigates the three smoothing approaches separately. Then, these

The Second Approach
In the second approach, the paper smoothes the NS bigram model by the traditional bigram model. Three smoothing algorithms are provided. They are the back-off method, the linear interpolation method and the hybrid method, as described in section 4.2. The experimental results are presented in Table 6. According to the experimental results, the second smoothing approach is more effective in smoothing the NS bigram model than the first one. For example, the hybrid method yields as much as 31.8% error rate reduction which is much higher than the best result of the first smoothing approach (which is 15.77% yielded by the back-off method). Moreover, for the linear interpolation method and the hybrid method, the error rate of the smoothed NS bigram model no longer increases along with the k value as the un-smoothed NS bigram model does, but decreases constantly. It proves that the NS bigram model smoothed by these methods can make full use of the increasing positional information of word and get further improvements.
It can be concluded that these smoothing methods can really solve the data sparseness problem of the NS bigram model, rather than just alleviate the problem. The back-off smoothing method does not perform as well as the above two methods because it is based on the model selection methodology and can not make full use of each component model.

The Third Approach
The

Comparisons
This section compares the performances of the three smoothing approaches with each other. In each approach, it presents the smoothing algorithm which yields the best experimental results.
The smoothed traditional bigram model is also presented for comparison. The results are summarized in Figure 4.
According to Figure 4, several conclusions can be drawn as follows. Firstly, the smoothed NS bigram model outperforms the smoothed traditional bigram model significantly by the exploitation of the word positional information. Secondly, all the smoothing approaches smooth the NS bigram model effectively with great error rate reduction. Thirdly, the second and the third approaches perform better than the first one. They can make full use of the positional information and really solve the data sparseness problem of the NS bigram model.
Focusing on a certain column in Table 9, the error rates of the probability distributions in the marginal positions are generally lower than those in the middle positions in the NS bigram model. For example, in the NS bigram model with k=5, the error rates of t=1(10.7%) and t=5(6.13%) are much lower than the error rate of t=3 (11.5%). It is more obvious for the larger values of k. The experimental results verify our speculations in section 5.2 and prove that the distributions in the marginal positions have more predictive capabilities than the middle ones, and consequently contribute more to the ultimate performance of the NS bigram model. In addition, it is found that the error rate at the end position is much lower than those in other positions. In the above example, the error rate of t=5(6.13%) is much lower than others. It is because many of punctuations are modeled in this probability distribution. These punctuations, such as full stop and exclamation, always appear at the end of the sentence.
Their positional information is much richer than words '. Therefore, the predictive capability of the probability distribution at the end position is much more powerful than other distributions in the NS bigram model, and it yields much higher performance.

Conclusions
This paper enhances the traditional ngram model by relaxing the stationary hypothesis and exploring the word positional information. The non-stationary ngram model is proposed.
Several related issues are discussed in detail, including the definition of the NS ngram model, the representation of the word positional information and the estimation of the conditional probability. In addition, three smoothing approaches are proposed to solve the data sparseness problem of the NS ngram model. Several smoothing algorithms are presented in each approach. In the experiments, the NS ngram model and its smoothing techniques are evaluated on the pinyin-to-character conversion task which is the core technique of Chinese text input method. According to the experimental results, several conclusions are drawn as follows: 1. The NS ngram model outperforms the traditional ngram model significantly by the exploitation of the word positional information; however, it suffers from severe data sparseness problem.

2.
The traditional smoothing techniques are effective in smoothing the NS ngram model; however, they can only alleviate the data sparseness problem without solving it completely.
3. The traditional ngram model is utilized to smooth the NS ngram model. Combined with the traditional smoothing techniques, this smoothing approach can solve the data sparseness problem completely and achieve the best experimental results.

4.
The third smoothing approach can also solve the data sparseness problem of the NS ngram model, and it yields a comparable experimental result to the second approach at the cost of a smaller parameter space.

5.
Among the probability distributions in the NS ngram model, the distributions in the marginal positions have more predictive capability than the middle ones, and therefore contribute more to the ultimate performance of the NS ngram model.