Two-Phase LMR-RC Tagging for Chinese Word Segmentation

In this paper we present a Two-Phase LMR-RC Tagging scheme to perform Chinese word segmentation. In the Regular Tagging phase, Chinese sentences are processed similar to the original LMR Tagging. Tagged sentences are then passed to the Correctional Tagging phase, in which the sentences are re-tagged using extra information from the first round tagging results. Two training methods, Separated Mode and Integrated Mode, are proposed to construct the models. Experimental results show that our scheme in Integrated Mode performs the best in terms of accuracy, where Separated Mode is more suitable under limited computational resources.


Introduction
The Chinese word segmentation is a non-trivial task because no explicit delimiters (like spaces in English) are used for word separation. As the task is an important precursor to many natural language processing systems, it receives a lot of attentions in the literature for the past decade (Wu and Tseng, 1993;Sproat et al., 1996). In this paper, we propose a statistical approach based on the works of (Xue and Shen, 2003), in which the Chinese word segmentation problem is first transformed into a tagging problem, then the Maximum Entropy classifier is applied to solve the problem. We further improve the scheme by introducing correctional treatments after first round tagging. Two different training methods are proposed to suit our scheme.
The paper is organized as follows. In Section 2, we briefly discuss the scheme proposed by (Xue and Shen, 2003), followed by our additional works to improve the performance. Experimental and bakeoff results are presented in Section 3. Finally, We conclude the paper in Section 4.

Chinese Word Segmentation as Tagging
One of the difficulties in Chinese word segmentation is that, Chinese characters can appear in different positions within a word (Xue and Shen, 2003), and LMR Tagging was proposed to solve the problem. The basic idea of LMR Tagging is to assign to each character, based on its contextual information, a tag which represents its relative position within the word. Note that the original tag set used by (Xue and Shen, 2003) is simplified and improved by (Ng and Low, 2004) . We shall then adopt and illustrate the simplified case here.
The tags and their meanings are summarized in Table 1. Tag L, M, and R correspond to the character at the beginning, in the middle, and at the end of the word respectively. Tag S means the character is a "single-character" word. Figure 1 illustrates a Chinese sentence segmented by spaces, and the corresponding tagging results.
After transforming the Chinese segmentation problem to the tagging problem, various solutions can be applied.
Maximum Entropy model (MaxEnt) (Berger, S. A. Della Pietra, and V. J. Della Pietra, 1996;Ratnaparkhi, 1996) was proposed in the original work to solve the LMR Tagging problem. In order to make MaxEnt success in LMR Tagging, feature templates used in capturing useful contextual information must be carefully designed. Furthermore, it is unavoidable that invalid tag sequences will occur if we just assign the tag with the highest probability. In the next subsection, we describe the feature templates and measures used to correct the tagging. Character is at the beginning of the word (or the character is the leftmost character in the word) M Character is in the middle of the word R Character is at the end of the word (or the character is the rightmost character in the word) S Character is a "single-character" word

Two-Phase LMR-RC Tagging
In this section, we introduce our Two-Phase LMR-RC Tagging used to perform Chinese Text Segmentation. The first phase, R-phase, is called Regular Tagging, in which similar procedures as in the original LMR Tagging are performed. The difference in this phase as compared to the original one is that, we use extra feature templates to capture characteristics of Chinese word segmentation. The second phase, C-phase, is called Correctional Tagging, in which the sentences are retagged by incorporating the regular tagging results. We hope that tagging errors can be corrected under this way. The models used in both phases are trained using MaxEnt model.

Regular Tagging Phase
In this phase, each character is tagged similar to the original approach. In our scheme, given the contextual information (x) of current character, the tag (y * ) with highest probability will be assigned: The features describing the characteristics of Chinese segmentation problem are instantiations of the feature templates listed in Table 2. Note that feature templates only describe the forms of features, but not the actual features. So the number of features used is much larger than the number of templates.
" 3 Previous and next characters 4 Current character is punctuation -5 ASCII characters within window of ±2 A−2, A−1 (as "3" and "2" are ASCII) 6 Current and character in window ±1 belong to different types D−1 (as "2" is digit, but " " is letter) Additional feature templates as compared to (Xue and Shen, 2003) and (Ng and Low, 2004) are template 5 and 6. Template 5 is used to handle documents with ASCII characters. For template 6, as it is quite common that word boundary occurs in between two characters with different types, this template is used to capture such characteristics.

Correctional Tagging Phase
In this phase, the sequence of characters is retagged by using the additional information of tagging results after R-phase. The tagging procedure is similar to the previous phase, except extra features (listed in Table 3) are used to assist the tagging. Table 3: Additional feature templates used in Cphase. Example used is "32 " with tagging results after R-phase as "SSLMR".

Training Method
Two training methods are proposed to construct models used in R-and C-phase: (1) Separated Mode, and (2) Integrated Mode. Separated Mode means the models used in two phases are separated. Model for R-phase is called R-model, and model for C-phase is called C-model. Integrated Mode means only one model, I-model is used in both phases.
The training methods are illustrated now. First of all, training data are divided into three parts, (1) Regular Training, (2) Correctional Training, and (3) Evaluation. Our method first trains using observations extracted from Part 1 (observation is simply the pair (context, tag) of each character). The created model is used to process Part 2. After that, observations extracted from Part 2 (which include previous tagging results) are used to create the final model. The performance is then evaluated by processing Part 3.
Let O be the set of observations, with subscripts R or C indicating the sources of them. Let T rainM odel : O → P , where P is the set of models, be the "model generating" function. The two proposed training methods can be illustrated as follow: 1. Separated Mode

Integrated Mode
The advantage of Separated Mode is that, it is easy to aggregate different sets of training data. It also provides a mean to handle large training data under limited resources, as we can divide the training data into several parts, and then use the similar idea to train each part. The drawback of this mode is that, it may lose the features' characteristics captured from Part 1 of training data, and Integrated Mode is proposed to address the problem, in which all the features' characteristics in both Part 1 and Part 2 are used to train the model.

Experimental Results and Discussion
We conducted closed track experiments on the Hong Kong City University (CityU) corpus in The Second International Chinese Word Segmentation Bakeoff to evaluate the proposed training and tagging methods. The training data were split into three portions. Part 1: 60% of the data is trained for R-phase; Part 2: 30% for C-phase training; and Part 3: the remaining 10% for evaluation. The evaluation part was further divided into six parts to simulate actual size of test document. The MaxEnt classifier was implemented using Java opennlp maximum entropy package from (Baldridge, Morton, and Bierner, 2004), and training was done with feature cutoff of 2 and 160 iterations. The experiments were run on an Intel Pentium4 3.0GHz machine with 3.0GB memory. To evaluate our proposed scheme, we carried out four experiments for each evaluation data. For Experiment 1, data were processed with R-phase only. For Experiment 2, data were processed with both R-and C-phase, using Separated Mode as training method. For Experiment 3, data were processed similar to Experiment 2, except Integrated Mode was used. Finally for Experiment 4, data were processed similar to Experiment 1, with both Part 1 and Part 2 data were used for Rmodel training. The purpose of Experiment 4 is to determine whether the proposed scheme can perform better than just the single Regular Tagging under the same amount of training data. Table 4 summarizes the experimental results measured in F-measure (the harmonic mean of precision and recall).
From the results, we obtain the following observations. 1. Both Integrated and Separated Training modes  Table 5. We have submitted multiple results for CityU, MSR and PKU corpora by applying different tagging methods described in the paper.

Conclusion
We present a Two-Phase LMR-RC Tagging scheme to perform Chinese word segmentation. Correctional Tagging phase is introduced in addition to the original LMR Tagging technique, in which the Chinese sentences are re-tagged using extra information of first round tagging results. Two training methods, Separated Mode and Integrated Mode, are introduced to suit our scheme. Experimental results show that Integrated Mode achieve the highest accuracy in terms of Fmeasure, where Separated Mode shows its advantages in constructing and aggregating multimodels under limited resources.