Toward Better Chinese Word Segmentation for SMT via Bilingual Constraints

The gainful supervisions toward a better segmentation solution for SMT are naturally extracted from MT training resources, i.e., bilingual parallel data. This study employs an approximated method introduced in [24, 12, 5] to learn bilingual segmentation knowledge. This relies on statistical character-based alignment: first, every Chinese character in the bitexts is divided by a white space so that individual characters are regarded as special “words” or alignment targets, and second, they are connected with English words by using a statistical word aligner, e.g., GIZA++ [15]. Note that the aligner is restricted to use an $n$-to-1 alignment pattern. The primary idea is that consecutive Chinese characters are grouped to a candidate word, if they are aligned to the same foreign word. It is worth mentioning that prior works presented a straightforward usage for candidate words, treating them as golden segmentations, either dictionary units or labeled resources. But this study treats the induced candidate words in a different way. We propose to extract the word boundary distributions¹¹The distribution is on four word boundary labels indicating the character positions in a word, i.e., B (begin), M (middle), E (end) and S (single character). for character-level trigrams (type)²²A word boundary distribution corresponds to the center character of a type. In fact, it aims at reducing label ambiguities to collect boundary information of character trigrams, rather than individual characters [1]., as shown in Figure 1, instead of the very specific words. There are two main reasons to do so. First, it is a more general expression which can reduce the impact amplification of erroneous character alignments. Second, boundary distributions can play more flexible roles as constraints over labelings to bias the model learning.

The type-level word boundary extraction is formally described as follows. Given the $i$th sentence pair $⟨x_i^c,x_i^f,{𝒜}_i^{c\to f}⟩$ of the aligned bilingual corpus ${𝒟}^{c\leftrightarrow f}$, the Chinese sentence $x_i^c$ consisting of $m$ characters $\left\{x_{i,1}^c,x_{i,2}^c,\mathrm{\dots },x_{i,m}^c\right\}$, and the foreign language sentence $x_i^f$, consisting of $n$ words $\left\{x_{i,1}^f,x_{i,2}^f,\mathrm{\dots },x_{i,n}^f\right\}$, ${𝒜}_i^{c\to f}$ represents a set of alignment pairs $a_j=⟨C_j,x_{i,j}^f⟩$ that defines connections between a few Chinese characters $C_j=\left\{x_{i,j_1}^c,x_{i,j_2}^c,\mathrm{\dots },x_{i,j_k}^c\right\}$ and a single foreign word $x_{i,j}^f$. For an alignment $a_j=⟨C_j,x_{i,j}^f⟩$, only the sequence of characters $C_j=\left\{x_{i,j_1}^c,x_{i,j_2}^c,\mathrm{\dots },x_{i,j_k}^c\right\}\forall d\in \left[1,k-1\right],j_{d+1}-j_d=1$ constitutes a valid candidate word. For the whole bilingual corpus, we assign each character in the candidate words with a word boundary tag $T\in \left\{B,M,E,S\right\}$, and then count across the entire corpus to collect the tag distributions $r_i=\{r_{i,t};t\in T\}$ for each type $x_{i,j-1}^c{x}_{i,j}^c{x}_{i,j+1}^c$.

The previous step contributes to generate bilingual segmentation supervisions, i.e., type-level word boundary distributions. An intuitive manner is to directly leverage the induced boundary distributions as label constraints to regularize segmentation model learning, based on a constrained learning algorithm. This study, however, makes further efforts to elevate the positive effects of the bilingual knowledge via the graph propagation technique. We adopt a similarity graph to encode the learned type-level word boundary distributions. The GP expression will be defined as a PR constraint in Section 3.3 that reflects the interactions between the graph and the CRFs model. In other words, GP is integrated with estimation of parametric structural model. This is greatly different from the prior pipelined approaches [20, 6, 27], where GP is run first and its propagated outcomes are then used to bias the structural model. This work seeks to capture the GP benefits during the modeling of sequential correlations.

In what follows, the graph setting and propagation expression are introduced. As in conventional GP examples [7], a similarity graph $𝒢=\left(V,E\right)$ is constructed over $N$ types extracted from Chinese training data, including treebank ${𝒟}_l^c$ and bitexts ${𝒟}_u^c$. Each vertex $V_i$ has a $\left|T\right|$-dimensional estimated measure $v_i=\{v_{i,t};t\in T\}$ representing a probability distribution on word boundary tags. The induced type-level word boundary distributions $r_i=\{r_{i,t};t\in T\}$ are empirical measures for the corresponding $M$ graph vertices. The edges $E\in V_i\times V_j$ connect all the vertices. Scores between pairs of graph vertices (types), $w_{ij}$, refer to the similarities of their syntactic environment, which are computed following the method in [20, 6, 27]. The similarities are measured based on co-occurrence statistics over a set of predefined features (introduced in Section 4.1). Specifically, the point-wise mutual information (PMI) values, between vertices and each feature instantiation that they have in common, are summed to sparse vectors, and their cosine distances are computed as the similarities. The nature of this similarity graph enforces that the connected types with high weights appearing in different texts should have similar word boundary distributions.

The quality (smoothness) of the similarity graph can be estimated by using a standard propagation function, as shown in Equation 1. The square-loss criterion [33, 3] is used to formulate this function:

The first term in this equation refers to seed matches that compute the distances between the estimated measure $v_i$ and the empirical probabilities $r_i$. The second term refers to edge smoothness that measures how vertices $v_i$ are smoothed with respect to the graph. Two types connected by an edge with high weight should be assigned similar word boundary distributions. The third term, a ${\mathrm{\ell }}_2$ norm, evaluates the distribution sparsity [7] per vertex. Typically, the GP process amounts to an optimization process with respect to parameter $v$ such that Equation 1 is minimized. This propagation function can be used to reflect the graph smoothness, where the higher the score, the lower the smoothness.

Our learning problem belongs to semi-supervised learning (SSL), as the training is done on treebank labeled data $\left({\mathrm{X}}_L,{\mathrm{Y}}_L\right)=\left\{\left({\mathrm{x}}_1,{\mathrm{y}}_1\right),\mathrm{\dots },\left({\mathrm{x}}_l,{\mathrm{y}}_l\right)\right\}$, and bilingual unlabeled data $\left({\mathrm{X}}_U\right)=\left\{{\mathrm{x}}_1,\mathrm{\dots },{\mathrm{x}}_u\right\}$ where ${\mathrm{x}}_i=\left\{x^1,\mathrm{\dots },x^m\right\}$ is an input word sequence and ${\mathrm{y}}_i=\left\{y^1,\mathrm{\dots },y^m\right\},y\in T$ is its corresponding label sequence. Supervised linear-chain CRFs can be modeled in a standard conditional log-likelihood objective with a Gaussian prior:

The conditional probabilities $p_{\theta }$ are expressed as a log-linear form:

Where $Z_{\theta }\left({\mathrm{x}}_i\right)$ is a partition function that normalizes the exponential form to be a probability distribution, and $f\left(y_i^{k-1},y_i^k,{\mathrm{x}}_i\right)$ are arbitrary feature functions.

In our setting, the CRFs model is required to learn from unlabeled data. This work employs the posterior regularization (PR) framework³³The readers are refered to the original paper of Ganchev et al. [9].  [9] to bias the CRFs model’s learning on unlabeled data, under a constraint encoded by the graph propagation expression. It is expected that similar types in the graph should have approximated expected taggings under the CRFs model. We follow the approach introduced by [10] to set up a penalty-based PR objective with GP: the CRFs likelihood is modified by adding a regularization term, as shown in Equation 4, representing the constraints:

Rather than regularize CRFs model’s posteriors $p_{\theta }\left(𝒴\right|{\mathrm{x}}_i)$ directly, our model uses an auxiliary distribution $q\left(𝒴\right|{\mathrm{x}}_i)$ over the possible labelings $𝒴$ for ${\mathrm{x}}_i$, and penalizes the CRFs marginal log-likelihood by a KL-divergence term⁴⁴The form of KL term: $\mathrm{KL}\left(q\right|\left|p\right)={\sum }_{q\in 𝒴}q\left(\mathrm{y}\right)\log \frac{q\left(\mathrm{y}\right)}{p\left(\mathrm{y}\right)}$., representing the distance between the estimated posteriors $p$ and the desired posteriors $q$, as well as a penalty term, formed by the GP function. The hyperparameter $\lambda$ is used to control the impacts of the penalty term. Note that the penalty is fired if the graph score computed based on the expected taggings given by the current CRFs model is increased vis-a-vis the previous training iteration. This nature requires that the penalty term $𝒫\left(v\right)$ should be formed as a function of posteriors $q$ over CRFs model predictions⁵⁵The original PR setting also requires that the penalty term should be a linear (Ganchev et al., 2010) or non-linear [10] function on $q$., i.e., $𝒫\left(q\right)$. To state this, a mapping $ℳ:\left(\left\{1,\mathrm{\dots },u\right\},\left\{1,\mathrm{\dots },m\right\}\right)\to V$ from words in the corpus to vertices in the graph is defined. We can thus decompose $v_{i,t}$ into a function of $q$ as follows:

The final learning objective combines the CRFs likelihood with the PR regularization term: $𝒥\left(\theta ,q\right)=ℒ\left(\theta \right)+{ℛ}_U\left(\theta ,q\right)$. This joint objective, over $\theta$ and $q$, can be optimized by an expectation maximization (EM) style algorithm as reported in [9]. We start from initial parameters ${\theta }^0$, estimated by supervised CRFs model training on treebank data. The E-step is to minimize ${ℛ}_U\left(\theta ,q\right)$ over the posteriors $q$ that are constrained to the probability simplex. Since the penalty term $𝒫\left(v\right)$ is a non-linear form, the optimization method in [9] via projected gradient descent on the dual is inefficient⁶⁶According to [10], the dual of quadratic program implies an expensive matrix inverse.. This study follows the optimization method [10] that uses exponentiated gradient descent (EGD) algorithm. It allows that the variable update expression, as shown in Equation 6, takes a multiplicative rather than an additive form.

where the parameter $\eta$ controls the optimization rate in the E-step. With the contributions from the E-step that further encourage $q$ and $p$ to agree, the M-step aims to optimize the objective $𝒥\left(\theta ,q\right)$ with respect to $\theta$. The M-step is similar to the standard CRFs parameter estimation, where the gradient ascent approach still works. This EM-style approach monotonically increases $𝒥\left(\theta ,q\right)$ and thus is guaranteed to converge to a local optimum.

The experiments in this study evaluated the performances of various CWS models in a Chinese-to-English translation task. The influence of the word segmentation on the final translation is our main investigation. We adopted three state-of-the-art metrics, BLEU [17], NIST [8] and METEOR [2], to evaluate the translation quality.

The monolingual segmented data, ${\mathrm{train}}_{\mathrm{TB}}$, is extracted from the Penn Chinese Treebank (CTB-7) [25], containing 51,447 sentences. The bilingual training data, ${\mathrm{train}}_{\mathrm{MT}}$, is formed by a large in-house Chinese-English parallel corpus [21]. There are in total 2,244,319 Chinese-English sentence pairs crawled from online resources, concentrated in 5 different domains including laws, novels, spoken, news and miscellaneous⁷⁷The in-house corpus has been manually validated, in a long process that exceeded 500 hours.. This in-house bilingual corpus is the MT training data as well. The target-side language model is built on over 35 million monolingual English sentences, ${\mathrm{train}}_{\mathrm{LM}}$, crawled from online resources. The NIST evaluation campaign data, MT-03 and MT-05, are selected to comprise the MT development data, ${\mathrm{dev}}_{\mathrm{MT}}$, and testing data, ${\mathrm{test}}_{\mathrm{MT}}$, respectively.

For the settings of our model, we adopted the standard feature templates introduced by Zhao et al. [30] for CRFs. The character-based alignment for achieving the “chars-to-word” mappings is accomplished by GIZA++ aligner [15]. For the GP, a 10-NNs similarity graph was constructed⁸⁸We evaluated graphs with top $k$ (from 3 to 20) nearest neighbors on development data, and found that the performance converged beyond 10-NNs.. Following [20, 27], the features used to compute similarities between vertices were (Suppose given a type “ $w_2{w}_3{w}_4$” surrounding contexts “$w_1{w}_2{w}_3{w}_4{w}_5$”): unigram ($w_3$), bigram ($w_1{w}_2$, $w_4{w}_5$, $w_2{w}_4$), trigram ($w_2{w}_3{w}_4$, $w_2{w}_4{w}_5$, $w_1{w}_2{w}_4$), trigram+context ($w_1{w}_2{w}_3{w}_4{w}_5$) and character classes in number, punctuation, alphabetic letter and other ($t\left(w_2\right)t\left(w_3\right)t\left(w_4\right)$). There are four hyperparameters in our model to be tuned by using the development data (${\mathrm{dev}}_{\mathrm{MT}}$) among the following settings: for the graph propagation, $\mu \in \left\{0.2,0.5,0.8\right\}$ and $\rho \in \left\{0.1,0.3,0.5,0.8\right\}$; for the PR learning, $\lambda \in \{0\le {\lambda }_i\le 1\}$ and $\sigma \in \{0\le {\sigma }_i\le 1\}$ where the step is 0.1. The best performed joint settings, $\mu =0.5,\rho =0.5,\lambda =0.9$ and $\sigma =0.8$, were used to measure the final performance.

The MT experiment was conducted based on a standard log-linear phrase-based SMT model. The GIZA++ aligner was also adopted to obtain word alignments [15] over the segmented bitexts. The heuristic strategy of grow-diag-final-and [11] was used to combine the bidirectional alignments for extracting phrase translations and reordering tables. A 5-gram language model with Kneser-Ney smoothing was trained with SRILM [19] on monolingual English data. Moses [11] was used as decoder. The Minimum Error Rate Training (MERT) [16] was used to tune the feature parameters on development data.

To provide a thorough analysis, the MT experiments in this study evaluated three baseline segmentation models and two off-the-shelf models, in addition to four variant models that also employ the bilingual constraints. We start from three baseline models:

• •

  Character Segmenter (CS): this model simply divides Chinese sentences into sequences of characters.

• •

  Supervised Monolingual Segmenter (SMS): this model is trained by CRFs on treebank training data (${\mathrm{train}}_{\mathrm{TB}}$). The same feature templates [30] are used. The standard four-tags (B, M, E and S) were used as the labels. The stochastic gradient descent is adopted to optimize the parameters.

• •

  Unsupervised Bilingual Segmenter (UBS): this model is trained on the bitexts (trainMT) following the approach introduced in [12]. The optimal set of the model parameter values was found on ${\mathrm{dev}}_{\mathrm{MT}}$ to be $k=3,t_{AC}=0.0$ and $t_{COOC}=15$.

The comparison candidates also involve two popular off-the-shelf segmentation models:

• •

  Stanford Segmenter: this model, trained by Chang et al. [4], treats CWS as a binary word boundary decision task. It covers several features specific to the MT task, e.g., external lexicons and proper noun features.

• •

  ICTCLAS Segmenter: this model, trained by Zhang et al. [28], is a hierarchical HMM segmenter that incorporates parts-of-speech (POS) information into the probability models and generates multiple HMM models for solving segmentation ambiguities.

This work also evaluated four variant models⁹⁹Note that there are two variant models working with GP. To be fair, the same similarity graph settings introduced in this paper were used. that perform alternative ways to incorporate the bilingual constraints based on two state-of-the-art graph-based SSL approaches.

• •

  Self-training Segmenters (STS): two variant models were defined by the approach reported in [20] that uses the supervised CRFs model’s decodings, incorporating empirical and constraint information, for unlabeled examples as additional labeled data to retrain a CRFs model. One variant (STS-NO-GP) skips the GP step, directly decoding with type-level word boundary probabilities induced from bitexts, while the other (STS-GP-PL) runs the GP at first and then decodes with GP outcomes. The optimal hyperparameter values were found to be: STS-NO-GP ($\alpha =0.8$) and $\eta =0.6$) and STS-GP-PL ($\mu =0.5,\rho =0.3,\alpha =0.8$ and $\eta =0.6$).

• •

  Virtual Evidences Segmenters (VES): Two variant models based on the approach in [27] were defined. The type-level word boundary distributions, induced by the character-based alignment (VES-NO-GP), and the graph propagation (VES-GP-PL), are regarded as virtual evidences to bias CRFs model’s learning on the unlabeled data. The optimal hyperparameter values were found to be: VES-NO-GP ($\alpha =0.7$) and VES-GP-PL ($\mu =0.5,\rho =0.3$ and $\alpha =0.7$).

Table 1 summarizes the final MT performance on the MT-05 test data, evaluated with ten different CWS models. In what follows, we summarized four major observations from the results. Firstly, as expected, having word segmentation does help Chinese-to-English MT. All other nine CWS models outperforms the CS baseline which does not try to identify Chinese words at all. Secondly, the other two baselines, SMS and UBS, are on a par with each other, showing less than 0.36 average performance differences on the three evaluation metrics. This outcome validated that the models, trained by either the treebank or the bilingual data, performed reasonably well. But they only capture partial segmentation features so that less gains for SMT are achieved when comparing to other sophisticated models. Thirdly, we notice that the two off-the-shelf models, Stanford and ICTCLAS, just brought minor improvements over the SMS baseline, although they are trained using richer supervisions. This behaviour illustrates that the conventional optimizations to the monolingual supervised model, e.g., accumulating more supervised data or predefined segmentation properties, are insufficient to help model for achieving better segmentations for SMT. Finally, highlighting the five models working with the bilingual constraints, most of them can achieve significant gains over the other ones without using the bilingual constraints. This strongly demonstrates that bilingually-learned segmentation knowledge does helps CWS for SMT. The models working with GP, STS-GP-PL, VES-GP-PL and ours outperform all others. We attribute this to the role of GP in assisting the spread of bilingual knowledge on the Chinese side. Importantly, it can be observed that our model outperforms STS-GP, VES-GP, which greatly supports that joint learning of CRFs and GP can alleviate the error transfer by the pipelined models. This is one of the most crucial findings in this study. Overall, the boldface numbers in the last row illustrate that our model obtains average improvements of 1.89, 1.76 and 1.61 on BLEU, NIST and METEOR over others.

This section aims to further analyze the three primary observations concluded in Section 4.3: $i$) word segmentation is useful to SMT; $ii$) the treebank and the bilingual segmentation knowledge are helpful, performing segmentation of different nature; and $iii$) the bilingual constraints lead to learn segmentations better tailored for SMT.

The first observation derives from the comparisons between the CS baseline and other models. Our results, showing the significant CWS benefits to SMT, are consistent with the works reported in the literature [24, 4]. In our experiment, two additional evidences found in the translation model are provided to further support that NO tokenization of Chinese (i.e., the CS model’s output) could harm the MT system. First, the SMT phrase extraction, i.e., building “phrases” on top of the character sequences, cannot fully capture all meaningful segmentations produced by the CS model. The character based model leads to missing some useful longer phrases, and to generate many meaningless or redundant translations in the phrase table. Moreover, it is affected by translation ambiguities, caused by the cases where a Chinese character has very different meanings in different contextual environments.

The second observation shifts the emphasis to SMS and UBS, based on the treebank and the bilingual segmentation, respectively. Our results show that both segmentation patterns can bring positive effects to MT. Through analyzing both models’ segmentations for ${\mathrm{train}}_{\mathrm{MT}}$ and ${\mathrm{test}}_{\mathrm{MT}}$, we attempted to get a closer inspection on the segmentation preferences and their influence on MT. Our first finding is that the segmentation consensuses between SMS and UBS are positive to MT. There have about 35% identical segmentations produced by the two models. If these identical segmentations are removed, and the experiments are rerun, the translation scores decrease (on average) by 0.50, 0.85 and 0.70 on BLEU, NIST and METEOR, respectively. Our second finding is that SMS exhibits better segmentation consistency than UBS. One representative example is the segmentations for “{CJK}UTF8gbsn孤零零 (lonely)”. All the outputs of SMS were “{CJK}UTF8gbsn孤零零”, while UBS generated three ambiguous segmentations, “{CJK}UTF8gbsnå­¤(alone)_{CJK}UTF8gbsn零零(double zero)”, “{CJK}UTF8gbsn孤零(lonely)_{CJK}UTF8gbsn零(zero)” and “{CJK}UTF8gbsnå­¤(alone)_{CJK}UTF8gbsn零(zero)_{CJK}UTF8gbsn零(zero)”. The segmentation consistency of SMS rests on the high-quality treebank data and the robust CRFs tagging model. On the other hand, the advantage of UBS is to capture the segmentations matching the aligned target words. For example, UBS grouped “{CJK}UTF8gbsn国(country)_{CJK}UTF8gbsn际(border)_{CJK}UTF8gbsn间(between)” to a word “{CJK}UTF8gbsn国际间(international)”, rather than two words “{CJK}UTF8gbsn国际(international)_{CJK}UTF8gbsn间(between)” (as given by SMS), since these three characters are aligned to a single English word “international”. The above analysis shows that SMS and UBS have their own merits and combining the knowledge derived from both segmentations is highly encouraged.

The third observation concerns the great impact of the bilingual constraints to the segmentation models in the MT task. The use of the bilingual constraints is the prime objective of this study. Our first contribution for this purpose is on using the word boundary distributions to capture the bilingual segmentation supervisions. This representation contributes to reduce the negative impacts of erroneous “chars-to-word” alignments. The ambiguous types (having relatively uniform boundary distribution), caused by alignment errors, cannot directly bias the model tagging preferences. Furthermore, the word boundary distributions are convenient to make up the learning constraints over the labelings among various constrained learning approaches. They have successfully played in three types of constraints for our experiments: PR penalty (Our model), decoding constraints in self-training (STS) and virtual evidences (VES). The second contribution is the use of GP, illustrated by STS-GP-PL, VES-GP-PL and Our model. The major effect is to multiply the impacts of the bilingual knowledge through the similarity graph. The graph vertices (types)¹⁰¹⁰This experiment yielded a similarity graph that consists of 11,909,620 types from ${\mathrm{train}}_{\mathrm{TB}}$ and ${\mathrm{train}}_{\mathrm{MT}}$, where there have 8,593,220 (72.15%) types without any empirical boundary distributions., without any supervisions, can learn the word boundary information from their similar types (neighborhoods) having the empirical boundary probabilities. The segmentations given by the three GP models show about 70% positive segmentation changes, affected by the unlabeled graph vertices, with respect to the ones given by the NO-GP models, STS-NO-GP and VES-NO-GP. In our opinion, the learning mechanism of our approach, joint coupling of GP and CRFs, rather than the pipelined one as the other two models, contributes to maximizing the graph smoothness effects to the CRFs estimation so that the error propagation of the pipelined approaches is alleviated.