Max-Margin Tensor Neural Network for Chinese Word Segmentation

The idea of distributed representation for symbolic data is one of the most important reasons why the neural network works. It was proposed by Hinton [11] and has been a research hot spot for more than twenty years [1, 6, 21, 16]. Formally, in the Chinese word segmentation task, we have a character dictionary $D$ of size $\left|D\right|$. Unless otherwise specified, the character dictionary is extracted from the training set and unknown characters are mapped to a special symbol that is not used elsewhere. Each character $c\in D$ is represented as a real-valued vector (character embedding) $Embed\left(c\right)\in {ℝ}^d$ where $d$ is the dimensionality of the vector space. The character embeddings are then stacked into a embedding matrix $M\in {ℝ}^{d\times \left|D\right|}$. For a character $c\in D$ that has an associated index $k$, the corresponding character embedding $Embed\left(c\right)\in {ℝ}^d$ is retrieved by the Lookup Table layer as shown in Figure 1:

Here $e_k\in {ℝ}^{\left|D\right|}$ is a binary vector which is zero in all positions except at $k$-th index. The Lookup Table layer can be seen as a simple projection layer where the character embedding for each context character is achieved by table lookup operation according to their indices. The embedding matrix $M$ is initialized with small random numbers and trained by back-propagation. We will analyze in more detail about the effect of character embeddings in Section 4.

The most common tagging approach is the window approach. The window approach assumes that the tag of a character largely depends on its neighboring characters. Given an input sentence $c_{[1:n]}$, a window of size $w$ slides over the sentence from character $c_1$ to $c_n$. We set $w=5$ in all experiments. As shown in Figure 1, at position $c_i,1\le i\le n$, the context characters are fed into the Lookup Table layer. The characters exceeding the sentence boundaries are mapped to one of two special symbols, namely “start” and “end” symbols. The character embeddings extracted by the Lookup Table layer are then concatenated into a single vector $a\in {ℝ}^{H_1}$, where $H_1=w\cdot d$ is the size of Layer 1. Then $a$ is fed into the next layer which performs linear transformation followed by an element-wise activation function $g$ such as tanh, which is used in our experiments:

where $W_1\in {ℝ}^{H_2\times H_1}$, $b_1\in {ℝ}^{H_2\times 1}$, $h\in {ℝ}^{H_2}$. $H_2$ is a hyper-parameter which is the number of hidden units in Layer 2. Given a set of tags $T$ of size $\left|T\right|$, a similar linear transformation is performed except that no non-linear function is followed:

where $W_2\in {ℝ}^{\left|T\right|\times H_2}$, $b_2\in {ℝ}^{\left|T\right|\times 1}$. $f\left(\text{<em xmlns="http://www.w3.org/1999/xhtml" class="ltx\_emph ltx\_font\_bold">t</em>}\right|c_{[i-2:i+2]})\in {ℝ}^{\left|T\right|}$ is the score vector for each possible tag. In Chinese word segmentation, the most prevalent tag set $T$ is BMES tag set, which uses 4 tags to carry word boundary information. It uses B, M, E and S to denote the Beginning, the Middle, the End of a word and a Single character forming a word respectively. We use this tag set in our method.

Despite sharing commonalities mentioned above, previous work models the segmentation task differently and therefore uses different training and inference procedure. Mansur et al. [15] modeled Chinese word segmentation as a series of classification task at each position of the sentence in which the tag score is transformed into probability using softmax function:

The model is then trained in MLE-style which maximizes the log-likelihood of the tagged data. Obviously, it is a local model which cannot capture the dependency between tags and does not support to infer the tag sequence globally.

To model the tag dependency, previous neural network models [6, 35] introduce a transition score $A_{ij}$ for jumping from tag $i\in T$ to tag $j\in T$. For a input sentence $c_{[1:n]}$ with a tag sequence $t_{[1:n]}$, a sentence-level score is then given by the sum of transition and network scores:

where $f_{\theta }\left(t_i\right|c_{[i-2:i+2]})$ indicates the score output for tag $t_i$ at the $i$-th character by the network with parameters $\theta =\left(M,A,W_1,b_1,W_2,b_2\right)$. Given the sentence-level score, Zheng et al. [35] proposed a perceptron-style training algorithm inspired by the work of Collins [5]. Compared with Mansur et al. [15], their model is a global one where the training and inference is performed at sentence-level.

Workable as these methods seem, one of the limitations of them is that the tag-tag interaction and the neural network are modeled seperately. The simple tag-tag transition neglects the impact of context characters and thus limits the ability to capture flexible interactions between tags and context characters. Moreover, the simple non-linear transformation in equation (2) is also poor to model the complex interactional effects in Chinese word segmentation.

To better model the tag-tag interaction given the context characters, distributed representation for tags instead of traditional discrete symbolic representation is used in our model. Similar to character embeddings, given a fixed-sized tag set $T$, the tag embeddings for tags are stored in a tag embedding matrix $L\in {ℝ}^{d\times \left|T\right|}$, where $d$ is the dimensionality of the vector space (same with character embeddings). Then the tag embedding $Embed\left(t\right)\in {ℝ}^d$ for tag $t\in T$ with index $k$ can be retrieved by the lookup operation:

where $e_k\in {ℝ}^{\left|T\right|\times 1}$ is a binary vector which is zero in all positions except at $k$-th index. The tag embeddings start from a random initialization and can be automatically trained by back-propagation. Figure 2 shows the new Lookup Table layer with tag embeddings. Assuming we are at the $i$-th character of a sentence, besides the character embeddings, the tag embeddings of the previous tags are also considered¹¹We also tried the architecture in which the tag embedding of current tag is also considered, but this did not bring much improvement and runs slower. For a fast tag inference, only the previous tag $t_{i-1}$ is used in our model even though a longer history of tags can be considered. The concatenation operation in Layer 1 then concatenates the character embeddings and tag embedding together into a long vector $a$. In this way, the tag representation can be directly incorporated in the neural network so that the tag-tag interaction and tag-character interaction can be explicitly modeled in deeper layers (See Section 3.2). Moreover, the transition score in equation (4) is not necessary in our model, because, by incorporating tag embedding into the neural network, the effect of tag-tag interaction and tag-character interaction are covered uniformly in one same model. Now equation (4) can be rewritten as follows:

where $f_{\theta }\left(t_i\right|c_{[i-2:i+2]},t_{i-1})$ is the score output for tag $t_i$ at the $i$-th character by the network with parameters $\theta$. Like Collobert et al. [6] and Zheng et al. [35], our model is also trained at sentence-level and carries out inference globally.

A tensor is a geometric object that describes relations between vectors, scalars, and other tensors. It can be represented as a multi-dimensional array of numerical values. An advantage of the tensor is that it can explicitly model multiple interactions in data. As a result, tensor-based model have been widely used in a variety of tasks [20, 12, 23].

In Chinese word segmentation, a proper modeling of the tag-tag interaction, tag-character interaction and character-character interaction is very important. In linear models, these kinds of interactions are usually modeled as features. In conventional neural network models, however, the input embeddings only implicitly interact through the non-linear function which can hardly model the complexity of the interactions. Given the advantage of tensors, we apply a tensor-based transformation to the input vector. Formally, we use a 3-way tensor $V^{[1:H_2]}\in {ℝ}^{H_2\times H_1\times H_1}$ to directly model the interactions, where $H_2$ is the size of Layer 2 and $H_1=\left(w+1\right)\cdot d$ is the size of concatenated vector $a$ in Layer 1 as shown in Figure 2. Figure 3 gives an example of the tensor-based transformation²²The bias term is omitted in Figure 3 for simplicity. The output of a tensor product is a vector $z\in {ℝ}^{H_2}$ where each dimension $z_i$ is the result of the bilinear form defined by each tensor slice $V^{\left[i\right]}\in {ℝ}^{H_1\times H_1}$:

Since vector $a$ is the concatenation of character embeddings and the tag embedding, equation (7) can be written in the following form:

where $E_j^{\left[p\right]}$ is the $j$-th element of the $p$-th embedding in Lookup Table layer and $V_{\left(p,q,j,k\right)}^{\left[i\right]}$ is the corresponding coefficient for $E_j^{\left[p\right]}$ and $E_k^{\left[q\right]}$ in $V^{\left[i\right]}$. As we can see, in each tensor slice $i$, the embeddings are explicitly related in a bilinear form which captures the interactions between characters and tags. The multiplicative operations between tag embeddings and character embeddings can somehow be seen as “feature combination”, which are hand-designed in feature-based models. Our model learns the information automatically and encodes them in tensor parameters and embeddings. Intuitively, we can interpret each slice of the tensor as capturing a specific type of tag-character interaction and character-character interaction.

Combining the tensor product with linear transformation, the tensor-based transformation in Layer 2 is defined as:

where $W_1\in {ℝ}^{H_2\times H_1}$, $b_1\in {ℝ}^{H_2\times 1}$, $h\in {ℝ}^{H_2}$. In fact, equation (2) used in previous work is a special case of equation (8) when $V$ is set to 0.

Despite tensor-based transformation being effective for capturing the interactions, introducing tensor-based transformation into neural network models to solve sequence labeling task is time prohibitive since the tensor product operation drastically slows down the model. Without considering matrix optimization algorithms, the complexity of the non-linear transformation in equation (2) is $O\left(H_1{H}_2\right)$ while the tensor operation complexity in equation (8) is $O\left(H_1^2{H}_2\right)$. The tensor-based transformation is $H_1$ times slower. Moreover, the additional tensor could bring millions of parameters to the model which makes the model suffer from the risk of overfitting. To remedy this, we propose a tensor factorization approach that factorizes each tensor slice as the product of two low-rank matrices. Formally, each tensor slice $V^{\left[i\right]}\in {ℝ}^{H_1\times H_1}$ is factorized into two low rank matrix $P^{\left[i\right]}\in {ℝ}^{H_1\times r}$ and $Q^{\left[i\right]}\in {ℝ}^{r\times H_1}$:

where $r\ll H_1$ is the number of factors. Substituting equation (9) into equation (8), we get the factorized tensor function:

Figure 4 illustrates the operation in each slice of the factorized tensor. First, vector $a$ is projected into two $r$-dimension vectors $f_1$ and $f_2$. Then the output $z_i$ for each tensor slice $i$ is the dot-product of $f_1$ and $f_2$. The complexity of the tensor operation is now $O\left(r{H}_1{H}_2\right)$. As long as $r$ is small enough, the factorized tensor operation would be much faster than the un-factorized one and the number of free parameters would also be much smaller, which prevent the model from overfitting.

We use the Max-Margin criterion to train our model. Intuitively, the Max-Margin criterion provides an alternative to probabilistic, likelihood-based estimation methods by concentrating directly on the robustness of the decision boundary of a model [27]. We use $Y\left(x_i\right)$ to denote the set of all possible tag sequences for a given sentence $x_i$ and the correct tag sequence for $x_i$ is $y_i$. The parameters of our model are $\theta =\left\{W_1,b_1,W_2,b_2,M,L,P^{[1:H_2]},Q^{[1:H_2]}\right\}$. We first define a structured margin loss $△\left(y_i,\widehat{y}\right)$ for predicting a tag sequence $\widehat{y}$ for a given correct tag sequence $y_i$:

where $n$ is the length of sentence $x_i$ and $\kappa$ is a discount parameter. The loss is proportional to the number of characters with an incorrect tag in the proposed tag sequence, which increases the more incorrect the proposed tag sequence is. For a given training instance $\left(x_i,y_i\right)$, we search for the tag sequence with the highest score:

where the tag sequence is found and scored by the Tensor Neural Network via the function $s$ in equation (6). The object of Max-Margin training is that the highest scoring tag sequence is the correct one: $y^{*}=y_i$ and its score will be larger up to a margin to other possible tag sequences $\widehat{y}\in Y\left(x_i\right)$:

This leads to the regularized objective function for $m$ training examples:

By minimizing this object, the score of the correct tag sequence $y_i$ is increased and score of the highest scoring incorrect tag sequence $\widehat{y}$ is decreased.

The objective function is not differentiable due to the hinge loss. We use a generalization of gradient descent called subgradient method [19] which computes a gradient-like direction. The subgradient of equation (13) is:

where ${\widehat{y}}_{max}$ is the tag sequence with the highest score in equation (13). Following Socher et al. [22], we use the diagonal variant of AdaGrad [8] with minibatchs to minimize the objective. The parameter update for the $i$-th parameter ${\theta }_{t,i}$ at time step $t$ is as follows:

where $\alpha$ is the initial learning rate and $g_{\tau }\in {ℝ}^{\left|{\theta }_i\right|}$ is the subgradient at time step $\tau$ for parameter ${\theta }_i$.

We use the PKU and MSRA data provided by the second International Chinese Word Segmentation Bakeoff [9] to test our model. They are commonly used by previous state-of-the-art models and neural network models. Details of the data are listed in Table 1. For evaluation, we use the standard bake-off scoring program to calculate precision, recall, F1-score and out-of-vocabulary (OOV) word recall.

For model selection, we use the first $90\mathrm{\%}$ sentences in the training data for training and the rest $10\mathrm{\%}$ sentences as development data. The minibatch size is set to 20. Generally, the number of hidden units has a limited impact on the performance as long as it is large enough. We found that $50$ is a good trade-off between speed and model performance. The dimensionality of character (tag) embedding is set to 25 which achieved the best performance and faster than 50- or 100-dimensional ones. We also validated on the number of factors for tensor factorization. The performance is not boosted and the training time increases drastically when the number of factors is larger than 10. We hypothesize that larger factor size results in too many parameters to train and hence perform worse. The final hyperparameters of our model are set as in Table 2.

We first perform a close test³³No other material or knowledge except the training data is allowed on the PKU dataset to show the effect of different model configurations. We also compare our model with the CRF model [13], which is a widely used log-linear model for Chinese word segmentation. The input feature to the CRF model is simply the context characters (unigram feature) without any additional feature engineering. We use an open source toolkit CRF++⁴⁴http://crfpp.googlecode.com/svn/trunk/doc/index.html?source=navbar to train the CRF model. All the neural networks are trained using the Max-Margin approach described in Section 3.4. Table 3 summarizes the test results. As we can see, by using Tag embedding, the F-score is improved by +0.6% and OOV recall is improved by +1.0%, which shows that tag embeddings succeed in modeling the tag-tag interaction and tag-character interaction. Model performance is further boosted after using tensor-based transformation. The F-score is improved by +0.6% while OOV recall is improved by +3.2%, which denotes that tensor-based transformation captures more interactional information than simple non-linear transformation.

Another important result in Table 3 is that our neural network models perform much better than CRF-based model when only unigram features are used. Compared with CRF, there are two differences in neural network models. First, the discrete feature vector is replaced with dense character embeddings. Second, the non-linear transformation is used to discover higher level representation. In fact, CRF can be regarded as a special neural network without non-linear function [30]. Wang and Manning [30] conduct an empirical study on the effect of non-linearity and the results suggest that non-linear models are highly effective only when distributed representation is used. To explain why distributed representation captures more information than discrete features, we show in Table 4 the effect of character embeddings which are obtained from the lookup table of MMTNN after training. The first row lists three characters we are interested in. In each column, we list the top 5 characters that are nearest (measured by Euclidean distance) to the corresponding character in the first row according to their embeddings. As we can see, characters in the first column are all Chinese number characters and characters in the second column and the third column are all Chinese family names and Chinese punctuations respectively. Therefore, compared with discrete feature representations, distributed representation can capture the syntactic and semantic similarity between characters. As a result, the model can still perform well even if some words do not appear in the training cases.

We further compare our model with previous neural network models on both PKU and MSRA datasets. Since Zheng et al. [35] did not report the results on the these datasets, we re-implemented their model and tested it on the test data. The results are listed in the first three rows of Table 5, which shows that our model achieved higher F-score than the previous neural network models.

Previous work found that the performance can be improved by pre-training the character embeddings on large unlabeled data and using the obtained embeddings to initialize the character lookup table instead of random initialization [15, 35]. Mikolov et al. [17] show that pre-trained embeddings can capture interesting semantic and syntactic information such as $king-man+woman\approx queen$ on English data. There are several ways to learn the embeddings on unlabeled data. Mansur et al. [15] used the model proposed by Bengio et al. [1] which learns the embeddings based on neural language model. Zheng et al. [35] followed the model proposed by Collobert et al. [7]. They constructed a neural network that outputs high scores for windows that occur in the corpus and low scores for windows where one character is replaced by a random one. Mikolov et al. [16] proposed a faster skip-gram model word2vec⁵⁵https://code.google.com/p/word2vec/‎ which tries to maximize classification of a word based on another word in the same sentence. In this paper, we use word2vec because preliminary experiments did not show differences between performances of these models but word2vec is much faster to train. We pre-train the embeddings on the Chinese Giga-word corpus [10]. As shown in Table 5 (last three rows), both the F-score and OOV recall of our model boost by using pre-training. Our model still outperforms other models after pre-training.

Although we focus on the question that how far we can go without using feature engineering in this paper, the study of deep learning for NLP tasks is still a new area in which it is currently challenging to surpass the state-of-the-art without additional features. To incorporate features into the neural network, Mansur et al. [15] proposed the feature-based neural network where each context feature is represented as feature embeddings. The idea of feature embeddings is similar to that of character embeddings described in section 2.1. Formally, we assume the extracted features form a feature dictionary $D_f$. Then each feature $f\in D_f$ is represented by a $d$-dimensional vector which is called feature embedding. Following their idea, we try to find out how well our model can perform with minimal feature engineering.

A very common feature in Chinese word segmentation is the character bigram feature. Formally, at the $i$-th character of a sentence $c_{[1:n]}$, the bigram features are . In our model, the bigram features are extracted in the window context and then the corresponding bigram embeddings are concatenated with character embeddings in Layer 1 and fed into Layer 2. In Mansur et al. [15], the bigram embeddings are pre-trained on unlabeled data with character embeddings, which significantly improves the model performance. Given the long time for pre-training bigram embeddings, we only pre-train the character embeddings and the bigram embeddings are initialized as the average of character embeddings of $c_k$ and $c_{k+1}$. Further improvement could be obtained if the bigram embeddings are also pre-trained. Table 6 lists the segmentation performances of our model as well as previous state-of-the-art systems. When bigram features are added, the F-score of our model improves from 94.0% to 95.2% on PKU dataset and from 94.9% to 97.2% on MSRA dataset. It is a competitive result given that our model only use simple bigram features while other models use more complex features. For example, Sun et al. [25] uses additional word-based features. Zhang et al. [32] uses eight types of features such as Mutual Information and Accessor Variety and they extract dynamic statistical features from both an in-domain corpus and an out-of-domain corpus using co-training. Since feature engineering is not the main focus of this paper, we did not experiment with more features.