Neural network models have been actively applied to word segmentation, especially Chinese, because of the ability to minimize the effort in feature engineering. Typical segmentation models are categorized as character-based, for conducting exact inference, or word-based, for utilizing word-level information. We propose a character-based model utilizing word information to leverage the advantages of both types of models. Our model learns the importance of multiple candidate words for a character on the basis of an attention mechanism, and makes use of it for segmentation decisions. The experimental results show that our model achieves better performance than the state-of-the-art models on both Japanese and Chinese benchmark datasets. 1 1 Introduction Word segmentation is the first step of natural language processing (NLP) for most East Asian languages, such as Japanese and Chinese. In recent years, neural network models have been widely applied to word segmentation, especially Chinese, because of their ability to minimize the effort in feature engineering. These models are categorized as character-based or word-based. Word-based models (Zhang et al., 2016; Cai and Zhao, 2016; Cai et al., 2017; Yang et al., 2017) directly segment a character sequence into words and can easily achieve the benefits of word-level information. However, these models cannot usually conduct exact inference because of strategies, such as beam-search decoding and constraints of maximum word length, which are necessary as the number of candidate segmentations increases exponentially with the sentence length. On the other hand, character-based models (Zheng et al., 2013; 1 We have released our code at https://github. com/shigashiyama/seikanlp . Mansur et al., 2013; Pei et al., 2014; Chen et al., 2015a) treat word segmentation as sequence labeling. These models typically predict optimal label sequences while considering adjacent labels. Limited efforts have been devoted to leveraging the advantages of both types of models, such as utilizing word information and conducting exact inference, which are complementary characteristics. In particular, the candidate word information for a character is beneficial to disambiguate word boundaries because a character in the sentence has multiple candidate words that contain the character. For example, there are three or four candidate words for characters x 3 , x 4 and x 5 in a sentence x 1:5 in Figure 1. A feasible solution to develop a model with both characteristics is to incorporate word information into a character-based framework. An example of such work is that of Wang and Xu (2017). They concatenated embeddings of a character and candidate words and used it in their convolutional neural network (CNN)-based model. They treated candidate words equivalently, although the plausibility of a candidate word differs in the context of a target character. In this paper, we propose a character-based word segmentation model that utilizes word information. Our model is based on a BiLSTM-CRF architecture that has been successfully applied to sequence labeling tasks (Huang et al., 2015; Chen et al., 2015b). Differing from the work of Wang and Xu (2017), our model learns and distinguishes the importance of candidate words for a character in a context, by applying an attention mechanism (Bahdanau et al., 2015). Our contributions are as follows:  We introduce word information and an attention mechanism into a character-based word segmentation framework, to distinguish and leverage the importance of candidate words Sentence: x 1:5 =   kare wa nihonjin  (He is a Japanese.) Candidate words f w j g for characters f x i g in the sentence: j 1 2 3 4 5 6 7 8 No. We empirically reveal that accurate attention to proper candidate words leads to correct segmentations. Our model outperforms the state-of-the-art word segmentation models on both Japanese and Chinese datasets. Word segmentation can be regarded as a character-level sequence labeling task. Given a sentence x = x 1: n := ( x 1 , . . . , x n ) of length n , each character x i will be assigned a segmentation label y i of tag set T , and a label sequence y = y 1: n will be predicted. We employ tag set T = { B , I , E , S } , where B, I and E, respectively, represent the beginning, inside and end of a multi-character word, and S represents a single character word (Xue, 2003). We use a BiLSTM-CRF architecture for our baseline model. The model consists of a character embedding layer, recurrent layers based on long short-term memory (LSTM) and a conditional random fields (CRF) layer as in Figure 2. Character Embedding Layer Let V c be a character vocabulary. Each character in a given sentence is transformed into a character embedding e c of d c -dimensional vector by a lookup operation that retrieves the corresponding column of the embedding matrix E c  R d c |V c | . Recurrent Layers for Character Representation A sequence of character embeddings e c 1: n is fed into a recurrent neural network (RNN) to derive contextualized representations h 1: n , which Recurrent layers for char Char embedding layer Recurrent layers for word+char CRF layer x 1 x n x i   w 1 w m w j  y 1 y n y i   Concat !" # ! we call character context vectors . We adopt a stacked (multi-layer) and bidirectional variant of an LSTM (Hochreiter and Schmidhuber, 1997) network, which addresses the issue of learning long-term dependencies and the gradient vanishing problem. Hidden vectors h ( l ) 1: n of l -th bidirectional LSTM (BiLSTM) layer are calculated by forward LSTM ( LSTM f ) and backward LSTM ( LSTM b ): h ( l ) i = BiLSTM( h ( l  1) 1: n , i ) (1) := LSTM f ( h ( l  1) 1: n , i )  LSTM b ( h ( l  1) n :1 , n  i + 1) , where h (0) i = e ci and  denotes a concatenation operation, and h ( l  1) n :1 denotes the reversed sequence of the original vectors h ( l  1) 1: n . More concretely, each forward or backward LSTM calculates hidden vectors h 1: n from an input sequence v 1: n of d v -dimensional vectors as follows: h i = LSTM( v 1: n , i ) := o i (cid:12) tanh( c i ) , c i = i i (cid:12) t i + f i (cid:12) c i  1 , g i =  ( W g v i + U g h i  1 + b g ) , t i = tanh( W t v i + U t h i  1 + b t ) , where  is sigmoid function, (cid:12) denotes element-wise multiplication, g indicates an input gate i , a forget gate f or an output gate o , W g , U g  R d r  d v and b g  R d r are trainable parameters for each gate g  { i, f, o } , and d r is a hyperparameter. CRF Layer A character context vector h i is mapped into a |T | -dimensional vector representing scores of segmentation labels: s i = W s h i + b s , where W s  R |T | 2 d r and b  R |T | are trainable parameters. Following previous sequence labeling work (Collobert et al., 2011), we introduce a CRF (Lafferty et al., 2001) layer, which has a transition matrix A  R |T ||T | to give transition scores of adjacent labels. Thus, the score of a label sequence y = y 1: n for a sentence x = x 1: n is calculated as follows: score( x, y ;  ) = n (cid:88) i =1 ( A y i  1 ,y i + s i [ y i ]) , where  denotes all the parameters and s [ y ] indicates the dimension of a vector s corresponding to a label y . We can find the best label sequence y (cid:63) by maximizing the sentence score: y (cid:63) = argmax y T n score( x, y ;  ) . Training Objective During training, parameters  of the network are learned by minimizing the negative log likelihood over all the sentences in training data D w.r.t  : To disambiguate word boundaries more effectively, we integrate word information into the character-based framework. More concretely, we transform embeddings of multiple candidate words for each character into a fixed size word vector, which we call a word summary vector , by a word feature composition function . We show the architecture of our model in Figure 2. In addition to the layers of the baseline model, the model comprises a word embedding layer, a word feature composition function, and additional recurrent layers. Word Embedding Layer Given a character sequence x = x 1: n , we search for all words corresponding to subsequences of the input sequence from a word vocabulary V w within a maximum word length. Then, we obtain a unique list 2 W x of candidate words of size m . For example, for a given sentence x 1:5 in Figure 1, candidate words { w 1 ,    , w 8 } will be found. Each word w  W x  V w is transformed into a d w dimensional vector e w by the embedding matrix E w  R d w | V w | . We can construct a word vocabulary to search candidate words by using external dictionaries or auto-segmented texts processed by any segmenter. Regarding the construction method used in our experiments, refer to  5.1. Composition Functions of Word Features For a character x i , the embeddings of all the candidate words that contain it are aggregated into a word summary vector a i by a composition function. We introduce two attention-based composition functions, weighted average (WAVG) and 2 List indicates set where each element has a unique number from 1 to the size of the set. weighted concatenation (WCON), which enable a model to pay more or less attention according to the importance of candidate words. Both functions calculate the importance score u ij from a character x i to a word w j in W x by a bilinear transformation, which indicates the interaction between the character context vector h i and the word embedding e wj . Then the weight  ij  [0 , 1] is obtained by a softmax operation to normalize the scores: u ij = h Ti W a e wj ,  ij =  ij exp( u ij ) (cid:80) mk =1  ik exp( u ik ) , (4) where W a  R 2 d r  d w is a trainable parameter. For simplification of equations, we introduce an indicator variable  ij  { 0 , 1 } that indicates whether the character x i is included in the word w j as Figure 1 illustrates. Next, WAVG and WCON calculate a word summary vector a i as the weighted average and the weighted concatenation of word embeddings, respectively: a i = WAVG( x i , { w j } mj =1 ) = m (cid:88) j =1  ij e wj , (5) a i = WCON( x i , { w j } mj =1 ) = L (cid:77) l =1  i,i l e wi l , (6) where { w j } = W x and (cid:76) (  ) indicates concatenation of given arguments. Let K be the maximum word length, L = (cid:80) Kk =1 k , and i l for the character x i denotes the corresponding index in W x of l -th words w (cid:48) l in the list { w (cid:48) 1 , . . . , w (cid:48) L } = (cid:83) Kk =1 (cid:83) 0 p =  k +1 { x i + p : i + p + k  1 } . If w (cid:48) l /  V w , we use a zero vector as the l -th argument in Eq. (6). For example, if K = 3 , WCON concatenates embeddings of words corresponding to x i (length 1), x i  1: i , x i : i +1 (length 2), x i  2: i , x i  1: i +1 and x i : i +2 (length 3) in this order, into a single vector for the character x i . WAVG and WCON finally output a summary vector of size d w and Ld w , respectively. Note that we use zero vector as a summary vector if no candidate words are found for a character. We also use two more variants of composition functions without the attention mechanism, the average function (AVG) and the concatenation function (CON). AVG is a special case of WAVG, where  ij =  ij / (cid:80) k  ik for all ( i, j ) in Eq. (5). CON is the equivalent function to the word features used in Wang and Xu (2017) and a special case of WCON, where  i,i l = 1 for all ( i, i l ) in Eq. Recurrent Layers for Word-Integrated Character Representation The summary vector a i and the context vector h i for a character are together fed into additional recurrent layers, which are BiLSTM layers, to further contextualize character representations using word information of surrounding characters. Given the input h i  a i , BiLSTMs calculate hidden vectors, and the hidden vectors z 1: n of the last BiLSTM layer are fed into the CRF layer. Datasets We evaluated our model on three datasets, CTB6 and MSR for Chinese word segmentation and BCCWJ (short unit word annotation) for Japanese word segmentation. CTB6 is Chinese Penn Treebank 6.0 (Xue et al., 2005). MSR is provided by the second International Chinese Word Segmentation Bakeoff (Emerson, 2005). BCCWJ is Balanced Corpus of Contemporary Written Japanese 1.1 (Maekawa et al., 2014). We followed the same training/development/test split as in previous work (Yang and Xue, 2012; Chen et al., 2015b) for CTB6, official training/test split for MSR, and the same training/test split as in the Project Next NLP 3 for BCCWJ. We randomly selected 90% of the sentences in the training data as a training set and used the other 10% as a development set, respectively for MSR and BCCWJ. Word Vocabulary Construction Apart from the given training and development sets for each dataset, we assumed no annotated information, including external dictionaries and third-party seg-menters, was available in our experiments. Therefore, we used the training set and large unlabeled texts to obtain a word vocabulary to be used in our proposed model. First, we trained a baseline model from each training set and applied it to large unlabeled texts. Then we collected auto-segmented words appearing in the texts 4 and gold words in the training set, and regarded the union of both kinds of words as a 3 http://www.ar.media.kyoto-u.ac.jp/ mori/research/topics/PST/NextNLP.html 4 We discarded words occurring less than five times in auto-segmented texts, since their pre-trained embeddings were not learned by Word2Vec with the default minimum frequency of five as described later. word vocabulary. We used the non-core section of BCCWJ (BCCWJ-NC) 5 for the Japanese dataset and Chinese Gigaword Fifth Edition 6 for the Chinese datasets as unlabeled texts. Pre-training of Embedding Parameters Following previous work (Collobert et al., 2011), we pre-trained word embeddings from large texts and used them to initialize the word embedding matrix in our proposed segmenter. To pre-train word embeddings, we used the gensim ( Rehurek and So-jka, 2010) implementation of Word2Vec (Mikolov et al., 2013) and applied it to the same texts as ones used to construct the word vocabularies, i.e., the auto-segmented BCCWJ-NC or Chinese Gigaword texts processed by the baseline segmenters. We used the toolkit with a skip-gram model, embedding size 300, the number of iterations one, and other default parameters. For words occurring only in a training set, we randomly initialized their embeddings. We fine-tuned all word embeddings during training of the proposed segmenter. In contrast, we randomly initialized all character embeddings, since pre-trained character embeddings did not improve performance in our preliminary experiments. Hyperparameter Setting Table 1 gives the hyperparameters for the proposed model. The same dropout strategy as in Zaremba et al. (2015) was applied to non-recurrent connections of recurrent layers. We used word vector dropout, which ran-5 We restored provided auto-segmented texts to the original raw sentences and used them as unlabeled texts. domly replaces a word embedding e w to a zero vector when calculating a word summary vector in Eq. (5) or (6). A mini-batch stochastic gradient descent was used to optimize parameters and decayed the learning rate with a fixed decay ratio every epoch after the first five epochs. We trained models for up to 20 epochs and selected the best model on the development set. We evaluated our baseline and proposed model variants on the test sets of the three benchmark datasets. Table 2 shows the mean of F1 scores of three runs for each dataset and each model. Among the proposed model variants, WCON achieved the best performance in almost all cases. We observed the following three findings from the results. First, all the word-integrated model variants consistently outperformed the pure character-based baseline. We conducted McNemar's tests in a similar manner to Kudo et al. (2004), and the improvement of each variant over the base-Attention Segmentation Method NoC Lower Upper Acc F1 Acc Acc-CA Acc-IA BCCWJ WAVG 2.09 30.09 94.53 79.69 99.14 99.22 99.74 97.18 WCON 90.97 99.21 99.29 99.88 93.98 CTB6 WAVG 2.39 18.01 94.54 82.97 95.98 96.64 98.72 86.50 WCON 86.65 96.35 96.99 99.24 82.37 MSR WAVG 2.24 21.61 91.76 83.42 98.53 98.75 99.65 94.26 WCON 85.02 98.51 98.72 99.63 93.53 Table 4: Attention accuracy, segmentation accuracy and F1-score on the development sets. line was significant at 0.001 level. Second, the attention-based variants further boosted performance in comparison with their counterparts without attention. The improvements of WCON over CON on BCCWJ and CTB, and that of WAVG over AVG were statistically significant according to the McNemar's tests. We discuss the reason for the slight and insignificant performance difference between CON and WCON on MSR in  5.3. Third, the concatenation-based variants performed better than the average-based counterparts in almost all cases. This is probably because CON and WCON keep word length and character position information. For example, ( d w +1 )-th to 2 d w -th dimensions of a summary vector always represent a word whose length is two and which ends with a target character (namely x i  1: i for x i ), while AVG and WAVG lose this kind of information. Table 3 shows the performance of state-of-the-art models without additional annotated data. We listed only the WCON results in Table 3 since it performed the best among all variants on the development sets. In comparison with the best previous models, we obtained better performance on BCCWJ and CTB6, and achieved approximately 31% and 3% error reductions, respectively. On MSR, we obtained a comparable performance with the character-based model with word features in Wang and Xu (2017), which used different unlabeled texts from ours to pre-train word embeddings. To our knowledge, our model is the first neural network-based model that has achieved state-of-the-art results on both Japanese and Chinese word segmentation. To analyze how the attention mechanism affected segmentation performance, we show in Table 4 attention accuracy of the proposed model with the attention-based functions of the development sets. Attention accuracy regards a predicted result as correct if a character x i most strongly attends to the word corresponding to the gold segmentation. The table also shows the segmentation performance, where accuracy indicates character-level accuracy of segmentation label prediction. Note that the attention accuracy of a model falls between lower and upper bounds shown in the table. The upper bound indicates the ratio of characters whose candidate words contain the gold word (then attention can be correctly paid) and the lower bound indicates the ratio of characters whose candidate words consist only of the gold word (then attention is always correctly paid). For example, assuming that the gold segmentation of the sentence in Figure 1 is  x 1 | x 2 | x 3 x 4 x 5 (= w 1 | w 2 | w 8 ) , candidate words for all characters contain their gold words, and those for characters x 1 and x 2 consist only of respective gold words w 1 and w 2 . Thus, the upper and lower bounds for the sentence are 5 / 5 and 2 / 5 , respectively. Both WAVG and WCON achieved approximately  80% attention accuracy over more than two candidate words on average. The Acc-CA (Acc-IA) column denotes the segmentation accuracy in cases where the attention was correctly (incorrectly) paid. We obtained particularly high segmentation accuracy (close to or higher than 99%). However, incorrect attention led to a large drop in segmentation accuracy. Moreover, we can see a clear tendency for WCON resulting in poorer segmentation accuracy in cases with incorrect attention, compared with WAVG. This suggests that attention by WCON is more sensitive to segmentation decisions; information on attended words is more directly propagated to succeeding layers. As for the slight performance difference between CON and WCON on MSR in Table 2, a possible explanation is that existence of fewer gold words (observed from the upper bound of accuracy) leads to inaccurate attention and segmentation. To examine segmentation results of actual sentences by different methods, we picked up sentence segments (a)-(f) from the BCCWJ development set. We show in Figure 3 the results obtained by BASE, WCON, and CON, which are selected as the character-based baseline, the best of our model variants, and its counterpart without attention, respectively. In addition, we also show values of weight  ij learned by WCON in Figure 4. In examples (a) and (b), BASE resulted in a wrong segmentation. However, both word-integrated methods correctly segmented words with the benefit of word information corresponding to gold segmentations ( adoresu , bar and hitewa ). This suggests that word information enables a model to utilize information on distant characters with target characters directly. From WCON results, we confirmed that all characters strongly attended to correct words, as in Figure 4. This suggests that accurate attention contributed to predicting correct segmentations. In examples (c) and (d), only WCON predicted correct segmentations. The existence of correct words in the vocabulary and correct attention probably resulted in the correct segmentation for (c). As for (d), although parts of characters attended to a wrong word ( kankin ), correct attention regarding surrounding characters ( hikikae and kingaku ) seems to lead to the correct segmentation. In examples (e) and (f), WCON predicted the wrong results. The wrong results of (e) by CON and WCON are probably due to the non-existence of the gold word ochanomizu , which is a location name, in the vocabulary. As for (f), WCON paid incorrect attention and predicted the wrong segmentation, even though the correct word chuya exists in the vocabulary. The model learned the incorrect weights likely due to the infrequent occurrence of the correct words; the single words hiru and yoru occur in the training set tens or hundreds of times while the compound word chuya occurs only twice. We may reduce these errors due to no or infrequent occurrences of gold words by increasing word vocabulary size, e.g., using larger texts to pre-train word embeddings. Word Segmentation For both Chinese and Japanese, word segmentation has been traditionally addressed by applying linear statistical algorithms, such as maximum entropy (Xue, 2003), CRF (Peng et al., 2004; Kudo et al., 2004; Zhao and Kit, 2008), and logistic regression (Neubig et al., 2011). Various neural network architectures have been explored for Chinese word segmentation to reduce the burden of manual feature engineering. Specifically, character-based neural models have been developed to model the task as a sequence labeling problem, starting with earlier work by (Zheng et al., 2013) and (Mansur et al., 2013), which applied feed-forward neural networks. Pei et al. (2014) used a neural tensor network to capture interactions between tags and characters. More sophisticated architectures have also been used as standard components of word segmentation models to derive effective features automatically. Chen et al. (2015a) proposed gated recursive neural networks to model complicated combinations of characters. Chen et al. (2015b) used LSTM to capture long distance dependencies. Xu and Sun (2016) combined LSTM and GRNN to capture long term information better by utilizing chain and tree structures. CNNs have been used to extract complex features such as character n -grams (Chen et al., 2017) and graphical features of Chinese characters (Shao et al., 2017). On the other hand, word-based neural models have also been proposed. Typical word-based models (Zhang et al., 2016; Cai and Zhao, 2016; Cai et al., 2017; Yang et al., 2017) sequentially determine whether or not to segment each character on the basis of word-level features and segmentation history, while keeping multiple segmentation candidates by beam search decoding. Liu et al. (2016) combined neural architectures for segment (i.e., word) representations into a semi-CRF framework, which searches for an optimal segmentation sequence consisting of variable length segments. Sun et al. (2017) proposed a gap-based model to predict whether or not to segment two consecutive characters, using a deep CNN consisting of more than ten layers. Recent works utilized word information on a character-based framework. Zhou et al. (2017) pre-trained character embeddings using word boundary information from auto-segmented texts. Wang and Xu (2017) explicitly introduced word information into their CNN-based model. They concatenated embeddings of a character and multiple words corresponding to n -grams ( n ranging from 1 to 4) that include the target character. For Japanese, less work employed neural models for word segmentation than for Chinese. Morita et al. (2015) integrated an RNN language model into a statistical Japanese morphological analysis framework, which simultaneously segments a sentence into words and predicts word features, such as POS and lemma. Kitagawa and Ko-machi (2018) applied a pure neural model based on LSTM and achieved a better performance than a popular statistical Japanese segmenter (Neubig et al., 2011). Around the same time as our work, two other character-based models for word segmentation have been proposed. Ma et al. (2018) showed a standard BiLSTM model can achieve state-of-the-art results when combined with deep learning best practices, including dropout to recurrent connections (Gal and Ghahramani, 2016) and pre-trained embeddings of character bigrams. These techniques can also be applied to and can further boost performance of our model. Yang et al. (2018) proposed a lattice LSTM-based model with subsequence (word or subword) information. Their model also considers the importance of multiple words by integrating character and word information into an LSTM cell vector using a gate-mechanism. However, their model might not fully exploit word information, since word information is given to only the first and last characters of the word. LSTM-CRF LSTM-CRF is a popular neural architecture, which has been applied to various tagging tasks, including word segmentation (Chen et al., 2015b), POS tagging and NER (Huang et al., 2015; Ma and Hovy, 2016; Rei et al., 2016). Ma and Hovy (2016) and Rei et al. (2016) introduced the internal character information of words on word-level labeling tasks in contrast to our work introducing candidate word information of characters in the character-level labeling task. Attention Mechanism An attention mechanism (Bahdanau et al., 2015) was first introduced in machine translation to focus on appropriate parts of a source sentence during decoding. This mechanism has been widely applied to various NLP tasks, including question answering (Sukhbaatar et al., 2015), constituency parsing (Vinyals et al., 2015), relation extraction (Lin et al., 2016) and natural language inference (Parikh et al., 2016). Rei et al. (2016) introduced a gate-like attention mechanism on their word-based sequence labeling model to determine the importance between the word itself and the internal characters for each word. In this paper, we proposed a word segmentation model that integrates word-level information into a character-based framework, aiming to take the advantages of both characterand word-based models. The experimental results show that our model with an attention-based composition function outperforms the state-of-the-art models on both Japanese and Chinese benchmark datasets. Our analysis suggests that a word vocabulary with larger coverage can reduce errors deriving from unknown words. In future work, we will explore (1) the relationship between vocabulary coverage and segmentation performance, and (2) the effect of using pre-trained word vectors learned from different domain texts in domain adaptation scenarios. We would like to thank Atsushi Fujita, Rui Wang, and the anonymous reviewers for their helpful feedback on this work.
abstain abstain objective abstain result abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain objective method abstain objective abstain abstain abstain abstain method method abstain abstain abstain abstain method other other abstain method other abstain abstain abstain method abstain method abstain abstain abstain method method abstain abstain abstain abstain abstain abstain other other method abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain other abstain abstain abstain abstain abstain abstain abstain abstain result result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain abstain result abstain result result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other other other other other other other other other other other other other other other other other other objective other method other other other other abstain other other other objective result method objective other