{'fraction_non_alphanumeric': 0.038496452946911876, 'fraction_numerical': 0.012776115388494772, 'mean_word_length': 4.6365359105552395, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Joint Model for Unsupervised Chinese Word Segmentation

In this paper, we propose a joint model for unsupervised Chinese word segmentation (CWS). Inspired by the “products of experts” idea, our joint model firstly combines two generative models, which are word-based hierarchical Dirichlet process model and character-based hidden Markov model, by simply multiplying their probabilities together. Gibbs sampling is used for model inference. In order to further combine the strength of goodness-based model, we then integrated nVBE into our joint model by using it to initializing the Gibbs sampler. We conduct our experiments on PKU and MSRA datasets provided by the second SIGHAN bakeoff. Test results on these two datasets show that the joint model achieves much better results than all of its component models. Statistical significance tests also show that it is significantly better than stateof-the-art systems, achieving the highest F-scores. Finally, analysis indicates that compared with nVBE and HDP, the joint model has a stronger ability to solve both combinational and overlapping ambiguities in Chinese word segmentation.


Introduction
Unlike English and many other western languages, there are no explicit word boundaries in Chinese sentences. Therefore, word segmentation is a crucial first step for many Chinese language processing tasks such as syntactic parsing, information retrieval and machine translation. A great deal of supervised methods have been proposed for Chinese word segmentation. While successful, they require manually labeled resources and often suffer from issues like poor domain adaptability. Thus, unsupervised word segmentation methods are still attractive to researchers due to its independence on domain and manually labeled corpora.
Previous unsupervised approaches to word segmentation can be roughly classified into two types. The first type uses carefully designed goodness measure to identify word candidates. Popular goodness measures include description length gain (DLG) (Kit and Wilks, 1999), accessor variety (AV) , boundary entropy (BE) (Jin and Tanaka-Ishii, 2006) and normalized variation of branching entropy (nVBE) (Magistry and Sagot, 2012) etc. Goodness measure based model is not segmentation model in a very strict meaning and is actually strong in generating word list without supervision. It inherently lacks capability to deal with ambiguous string, which is one of main sources of segmentation errors and has been extensively explored in supervised Chinese word segmentation.
The second type focuses on designing sophisticated statistical model, usually nonparametric Bayesian models, to find the segmentation with highest posterior probability, given the observed character sequences. Typical statistical models includes Hierarchical Dirichlet process (HDP) model (Goldwater et al., 2009), Nested Pitman-Yor process (NPY) model (Mochihashi et al., 2009) etc, which are actually nonparametric language models and therefor can be categorized as word-based model. Word-based model makes decision on wordhood of a candidate character sequence mainly based on information outside the sequence, namely, the wordhood of character sequences being adjacent to the concerned sequence.
Inspired by the success of character-based model in supervised word segmentation, we propose a Bayesian HMM model for unsupervised Chinese word segmentation. With the Bayesian HMM model, we formulate the unsupervised segmentation tasks as procedure of tagging positional tags to characters. Different from word-based model, character-based model like HMM-based model as we propose make decisions on wordhood of a candidate character sequence based on information inside the sequence, namely, ability of characters to form words. Although the Bayesian HMM model alone does not produce competitive results, it contributes substantially to the joint model as proposed in this paper.
Our joint model takes advantage from three different models: namely, a character-based model (HMM-based), a word-based model (HDP-based) and a goodness measure based model (nVBE model). The combination of HDP-based model and HMM-based model enables to utilize information of both word-level and character-level. We also show that using nVBE model as initialization model could further improve the performance to outperform the state-of-the-art systems and leads to improvement in both wordhood judgment and disambiguation ability.
Word segmentation systems are usually evaluated with metrics like precision, recall and F-Score, regardless of supervised or unsupervised. Following normal practice, we evaluate our model and compare it with state-of-the-art systems using F-Score. However, we argue that the ability to solve segmentation ambiguities is also important when evaluating different types of unsupervised word segmentation systems. This paper is organized as follows. In Section 2, we will introduce several related systems for unsupervised word segmentation. Then our joint model is presented in Section 3. Section 4 shows our experiment results on the benchmark datasets and Section 5 concludes the paper.

Related Work
Unsupervised Chinese word segmentation has been explored in a number of previous works and by various methods. Most of these methods can be divided into two categories: goodness measure based methods and nonparametric Bayesian methods.
There have been a plenty of work that is based on a specific goodness measure. Zhao and Kit (2008) compared several popular unsupervised models within a unified framework. They tried various types of goodness measures, such as Description Length Gain (DLG) proposed by Kit and Wilks (1999), Accessor Variety (AV) proposed by  and Boundary Entropy (Jin and Tanaka-Ishii, 2006). A notable goodness-based method is ESA: "Evaluation, Selection, Adjustment", which is proposed by Wang et al. (2011) for unsupervised Mandarin Chinese word segmentation. ESA is an iterative model based on a new goodness algorithm that adopts a local maximum strategy and avoids threshold setting. One disadvantage of ESA is that it needs to iterate the process several times on the corpus to get good performance. Another disadvantage is the requirement for a manually segmented training corpus to find best value for parameters (they called it proper exponent). Another notable work is nVBE: Magistry and Sagot (2012) proposed a model based on the Variation of Branching Entropy. By adding normalization and viterbi decoding, they improve performance over Jin and Tanaka-Ishii (2006) and remove most of the parameters and thresholds from the model.
Nonparametric Bayesian models also achieved state-of-the-art performance in unsupervised word segmentation. Goldwater et al. (2009) introduced a unigram and a bigram model for unsupervised word segmentation, which are based on Dirichlet process and hierarchical Dirichlet process (Teh et al., 2006) respectively. The main drawback is that it needs almost 20,000 iterations before the Gibbs sampler converges. Mochihashi et al. (2009) extended this method by introducing a nested character model and an efficient blocked Gibbs sampler. Their method is based on what they called nested Pitman-Yor language model. One disadvantage of goodness measure based methods is that they do not have any disambiguation ability in theory in spite of their competitive performances. This is because once the goodness measure is given, the decoding algorithm will segment any ambiguous strings into the same word sequences, no matter what their context is. In contrast, nonparametric Bayesian language models aim to segment character string into a "reasonable" sentence according to the posterior probability. Thus, theoretically, this method should have better ability to solve ambiguities over goodness measure based methods.

Joint Model
In this section, we will discuss our joint model in detail.

Combining HDP and HMM
In supervised Chinese word segmentation literature, word-based approaches and characterbased approaches often have complementary advantages (Wang et al., 2010).Since the two types of model try to solve the problem from different perspectives and by utilizing different levels of information (word level and character level). In unsupervised Chinese word segmentation literature, the HDP-base model can be viewed as a typical word-based method. And we can also build a character-based unsupervised model by using a hidden Markov model. We believe that the HDPbased model and the HMM-based model are also complementary with each other, and a combination of them will take advantage of both and thus capture different levels of information.
Now the problem we are facing is how to combine these two models. To keep the joint model simple and involve as little extra parameters as possible, we combine the two baseline models by just multiplying their probabilities together and then renormalizing it. Let C = c 1 c 2 · · · c |C| be a string of characters and W = w 1 w 2 · · · w |W | is the corresponding segmented words sequence. Then the conditional probability of the segmentation W given the character string C in our joint model is defined as: where P D (W |C) is the probability from the HDP model as given in Equation 6 and P M (W |C) is the probability given by the Bayesian HMM model as given in Equation 2. Z(C) is a normalization term to make sure that P J (W |C) is a probability distribution. The combining method is inspired by Hinton (1999), which proved that it is possible to combine many individual expert models by multiplying the probabilities and then renormalizing it. They called it "product of experts". We can see that combining models in this way does not involve any extra parameters and Gibbs sampling can be easily used for model inference.

Bayesian HMM
The dominant method for supervised Chinese word segmentation is character-based model which was first proposed by Xue (2003). This method treats word segmentation as a tagging problem, each tag indicates the position of a character within a word. The most commonly used tag set is {Single, Begin, Middle, End}. Specifically, S means the character forms a single word, B/E means the character is the begining/ending character of the word, and M means the character is in the middle of the word. Existing models are trained on manually annotated data in a supervised way based on discriminative models such as Conditional Random Fields (Peng et al., 2004;Tseng et al., 2005). Supervised character-based methods make full use of character level information and thus have been very successful in the last decade. However, no unsupervised model has utilized character level information in the way as supervised method does. We can also build a character-based model for Chinese word segmentation using hidden Markov model(HMM) as formulated in the following equation: where C and W have the same meaning as before. P t (t i |t i−1 ) is the transition probability of tag t i given its former tag t i−1 and P e (c i |t i ) is the emission probability of character c i given its tag t i . This model can be easily trained with Maximum Likelihood Estimation (MLE) on annotated data or with Expectation Maximization (EM) on raw texts. But using any of this methods will make it difficult to combine it with the HDP-based model. Instead, we propose a Bayesian HMM for unsupervised word segmentation. The Bayesian HMM model is defined as follows: where p t and e t are transition and emission distributions, θ and σ are the symmetric parameters of Dirichlet distributions. Now suppose we have observed tagged text h, then the conditional probability P M (w i |w i−1 = l, h) can be obtained: where < w i−1 , w i > is a word bigram, l is the index of word w i−1 , c j is the jth character in word w i and t j is the corresponding tag.P t (t j |t j−1 , h) and P e (c j |t j , h) are the posterior probabilities, they are given as: where n <t j−1 ,t j > is the tag bigram count of < t j−1 , t j > in h, n <t j ,c j > denotes the number of occurrences of tag t j and character c j , and * means a sum operation. T and V are the size of character tag set (we follow the commonly used {SBME} tag set and thus T = 4 in this case) and character vocabulary.

HDP Model
Goldwater et al. (2009) proposed a nonparametric Bayesian model for unsupervised word segmentation which is based on HDP (Teh et al., 2006). In this model, the conditional probability of the segmentation W given the character string C is defined as: where w i is the ith word in W . This is actually a nonparametric bigram language model. This bigram model assumes that each different word has a different distribution over words following it, but all these different distributions are linked through a HDP model: where DP denotes a Dirichlet process. Suppose we have observed segmentation result h, then we can get the posterior probability P D (w i |w i−1 = l, h) by integrating out G l : where n <w i−1 ,w i > denotes the total number of occurrences of the bigram < w i−1 , w i > in the observation h. And P D (w i |h) can be got by integrating out G 0 : where t w i denotes the number of tables associated with w i in the Chinese Restaurant Franchise metaphor (Teh et al., 2006), t is the total number of tables and H(w i ) is the base measure of G 0 . In fact, H(w i ) is the prior distribution over words, so prior knowledge can be injected in this distribution to enhance the performance. In Goldwater et al. (2009)'s work, the base measure H(w i ) are defined as a character unigram model: where, p s is the probability of generating a word boundary. P (c ij ) is the probability of the jth character c ij in word w i , this probability can be estimated from the training data using maximum likelihood estimation.

Initializing with nVBE
Among various goodness measure based models, we choose nVBE (Magistry and Sagot, 2012) to initialize our Gibbs sampler with its segmentation results. nVBE achieved a relatively high perfomance over other goodness measure based methods. And it's very simple as well as efficient.
Theoretically, the Gibbs sampler may be initialized at random or using any other methods. Initialization does not make a difference since the Gibbs sampler will eventually converge to the posterior distribution if it iterates as much as possible. This is an essential attribute of Gibbs sampling. However, we believe that initializing the Gibbs sampler with the result of nVBE will benefit us in two ways. On one hand, in consideration of its combination of nonparametric Bayesian method and goodness-based method, it will improve the overall performance as well as solve more segmentation ambiguities with the help of HDP-based model. On the other hand, it makes the convergence of Gibbs sampling faster. In practice, random initialization often leads to extremely slow convergence.

Inference with Gibbs Sampling
In our proposed joint model, Gibbs sampling (Casella and George, 1992) can be easily used to identify the highest probability segmentation from among all possibilities. Following Goldwater et al. (2009), we can repeatedly sample from potential word boundaries. Each boundary variable can only take on two possible values, corresponding to a word boundary or not word boundary.
For instance, suppose we have obtained a segmentation result β|c i−2 c i−1 c i c i+1 c i+2 |γ, where β and γ are the words sequences to the left and right and c i−2 c i−1 c i c i+1 c i+2 are characters between them. Now we are sampling at location i to decide whether there is a word boundary between c i and c i+1 . Denote h 1 as the hypothesis that it forms a word boundary (the corresponding result is βw 1 w 2 γ where w 1 = c i−2 c i−1 c i and w 2 = c i+1 c i+2 ), and h 2 as the opposite hypothesis (then the corresponding result is βwγ where w = c i−2 c i−1 c i c i+1 c i+2 ). The posterior probability for these two hypotheses would be: where P D (h|h − ) and P M (h|h − ) are the posterior probabilities in HDP-based model and in HMM-based model, and h − denotes the current segmentation results for all observed data except c i−2 c i−1 c i c i+1 c i+2 . Note that the normalization term Z(C) can be ignored during inference. The posterior probabilities for these two hypotheses in the HDP-based model is given as: where w l (w r ) is the first word to the left (right) of w. And the posterior probabilities for the Bayesian HMM model is given as: where P t (t j |t j−1 , h − ) and P e (c j |t j , h − ) are given in Equation 4 and 5. The difference is that under hypothesis h 1 , c i−2 c i−1 c i c i+1 c i+2 are tagged as "BMEBE" and under hypothesis h 2 as "BM-MME".
Once the Gibbs sampler is converged, a natural way to is to treat the result of last iteration as the final segmentation result, since each set of assignments to the boundary variables uniquely determines a segmentation.

Experiments
In this section, we test our joint model on PKU and MSRA datesets provided by the Second Segmentation Bake-off (SIGHAN 2005) (Emerson, 2005). Most previous works reported their results on these two datasets, this will make it convenient to directly compare our joint model with theirs.

Setting
The second SIGHAN Bakeoff provides several large-scale labeled data for evaluating the performance of Chinese word segmentation systems. Two of the four datasets are used in our experiments. Both of the dataset contains only simplified Chinese. Table 1 shows the statistics of the two selected corpus. For development set, we randomly select a small subset (about 10%) of the training data. Specifically, 2000 sentences are selected for PKU corpus and 8000 sentences for MSRA corpus. The rest training data plus the test set is then combined for segmentation but only test data is used for evaluation. The development set is used to tune parameters of the HDP-based model and HMM-based model separately. Since our joint model does not involve any additional parameters, we reuse the parameters of the HDP-based model and HMM-based model in the joint model. Specifically, we set α 1 = 1000.0, α = 10.0, p s = 0.5 for the HDP-based model and set θ = 1.0, σ = 0.01 for the HMM-based model.
For evaluation, we use standard F-Score on words for all following experiments. F-Score is the harmonic mean of the word precision and recall. Precision is given as: #correct words in result #total words in result and recall is given as: R = #correct words in result #total words in gold corpus then F-Score is calculated as:  Huang and Zhao (2007) provided an empirical method to estimate the consistency between the four different segmentation standards involved in the Bakeoff-3. A lowest consistency rate 84.8% is found among the four standards. Zhao and Kit (2008) considered this figure as the upper bound for any unsupervised Chinese word segmentation systems. We also use it as the topline in our comparison.

Prior Knowledge Used
When it comes to the evaluation and comparison for unsupervised word segmentation systems, an important issue is what kind of pre-processing steps and prior knowledge are needed. To be fully unsupervised, any prior knowledge such as punctuation information, encoding scheme and word length could not be used in principle. Nevertheless, information like punctuation can be easily injected to most existing systems and significantly enhance the performance. The problem we are faced with is that we don't know for sure what kind of prior information are used in other systems. One may use a small punctuation set to segment a long sentence into shorter ones, while another may write simple regular expressions to identify dates and numbers. Lot of work we compare to don't even mention this subject.
Fortunately, we notice that Wang et al. (2011) provided four kinds of preprocessings (they call settings). In their settings 1 and 2, punctuation and other encoding information are not used. In setting 3, punctuation is used to segment character sequences into sentences, and both punctuation and other encoding information are used in setting 4. Then the results reported in Magistry and Sagot (2012) relied on setting 3 and setting 4. In order to make the comparison as fair as possible, we use setting 3 in our experiment, i.e., only a punctuation set for simplified Chinese is used in all our experiments. We will compare our experiment results to previous work on the same setting if they are provided .

Experiment Results
Table 2 summarizes the F-Scores obtained by different models on PKU and MSRA corpus, as well as several state-of-the-art systems. Detailed information about the presented models are listed as follows: • nVBE: the model based on Variation of Branching Entropy in Magistry and Sagot (2012). We re-implement their model on setting 3 1 .
• HDP+HMM: the model combining HDPbased model and HMM-based model as proposed in Section 3, initialized randomly.
• HDP+nVBE: the HDP-based model, initialized with the results of nVBE model.
• ESA: the model proposed in Wang et al. (2011), as mentioned above, the conducted experiments on four different settings, we report their results on setting 3.
For all of our Gibbs samplers, we run 5 times to get the averaged F-Scores. We also give the variance of the F-Scores in Table 2. For each run, we find that random initialization takes around 1,000 iterations to converge, while initialing with nVBE only takes as few as 10 iterations. This makes our joint model very efficient and possible to work in practical applications as well. At last, a single sample (the last one) is used for evaluation.
From Table 2, we can see that the joint model (Joint) outperforms all the presented systems in F-Score on all testing corpora. Specifically, comparing "HDP+HMM" with "HDP", the former model increases the overall F-Score from 68.7% to 75.3% (+6.6%) in PKU corpora and from 69.9% to 76.3% (+6.4%) in MSRA corpora, which proves that the character information in the HMM-based model can actually enhance the performance of the HDP-based model. Comparing "HDP+nVBE" with "HDP", the former model also increases the overall F-Score by 10.6%/9.6% in PKU/MSRA corpora, which demonstrates that initializing the HDP-based model with nVBE will improve the performance by a large margin. Finally, the joint model "Joint" take advantage from both from the character-based HMM model and the nVBE model, it achieves a F-Score of 81.1% on PKU and 81.7% on MSRA. This result outperforms all its component baselines such as "HDP", "HDP+HMM" and "HDP+nVBE".
Our joint model also shows competitive advantages over several state-of-the-art systems. Compared with nVBE,the F-Score increases by 3.2% on PKU corpora and by 3.5% on MSRA corpora. Compared with ESA, the F-Score increases by 3.7%/3.3% in PKU/MSRA corpora. Lastly, compared to the nonparametric Bayesian models (NPY(n)), our joint model still increases the F-Score by 1.5% (NPY(2)) and 1.0% (NPY(3)) on MSRA corpora. Moreover, compared with the empirical topline figure 84.8%, our joint model achieves a pretty close F-Score. The differences are 3.7% on PKU corpora and 3.1% on MSRA corpora.
An phenomenon we should pay attention to is the poor performance of the HMM-based model. With our implementation of the Bayesian HMM, we achieves a 34.3% F-Score on PKU corpora and a 34.9% F-Score on MSRA corpora, just slightly better than random segmentation. The result show that the hidden Markov Model alone is not suitable for character-based Chinese word segmentation problem. However, it still substantially contributes to the joint model.
We find that the variance of the results are rather small, this shows the stability of our Gibbs samplers. From the segmentation results generated by the joint model, we also found that quite a large amount of errors it made are related to dates, numbers (both Chinese and English) and English words. This problem can be easily addressed during preprocessing by considering encoding information as previous work, and we believe this will bring us much better performance.

Disambiguation Ability
Previous unsupervised work usually evaluated their models using F-score, regardless of goodness measure based model or nonparametric Bayesian model. However, segmentation ambiguity is a very important factor influencing accuracy of Chinese word segmentation systems (Huang and Zhao, 2007). We believe that the disambiguation ability of the models should also be considered when evaluating different types of unsupervised segmentation systems, since different type of models shows different disambiguation ability. We will compare the disambiguation ability of dif-ferent systems in this section.
In general, there are mainly two kinds of ambiguity in Chinese word segmentation problem: • Combinational Ambiguity: Given character strings "A" and "B", if "A", "B", "AB" are all in the vocabulary, and "AB" or "A-B" (here "-" denotes a space) occurred in the real text,then "AB" can be called a combinational ambiguous string.
• Overlapping Ambiguity: Given character strings "A", "J" and "B", if "A", "B", "AJ" and "JB" are all in the vocabulary, and "A-JB" or "AJ-B" occurred in the real text, then "AJB" can be called an overlapping ambiguous string.
We count the total number of mistakes different systems made at ambiguous strings (the vocabulary is obtained from the gold standard answer of testing set). As we have mentioned in Section 2, goodness measure based methods such as nVBE do not have any disambiguation ability in theory. Our observation is identical to this argument. We find that nVBE always segments ambiguous strings into the same result. Take a combinational string " " as an example, " (just)", " (have)" and " (only)" are all in the vocabulary. In the PKU test set, this string occurs 14 times as " -(just have)" and 18 times as " (only)", 32 times in total. nVBE segments all the 32 strings into " (only)" (i.e. 18 of them are correct), while the joint model segments it 22 times as " (only)" and 10 times as " -(just have)" according to its context, and 24 of them are correct. Table 3 and 4 show the statistics of combinational ambiguity and overlapping ambiguity respectively. The numbers in parentheses denote the total number of ambiguous strings. From these tables, we can see that HDP+nVBE makes less mistakes than nVBE in most circumstances, except that it solves less combinational ambiguities on MSRA corpora. But our proposed joint model solves the most combinational and overlapping ambiguities, on both PKU and MSRA corpora. Specifically, compared to nVBE, the joint model correctly solves 171/871 more combinational ambiguities on PKU/MSRA corpora, which is a 0.6%/13.8% relative error reduction. It also solves 28/45 more overlapping ambiguities on PKU/MSRA corpora, which is a 11.5%/23.4% relative error reduction. This indicates that the joint model has a stronger ability of disambiguation over the compared systems.

Statistical Significance Test
The main results presented in Table 2 has shown that our proposed joint model outperforms the two baselines as well as state-of-the-art systems. But it is also important to know if the improvement is statistically significant over these systems. So we conduct statistical significance tests of F-scores among these various models. Following Wang et al. (2010), we use the bootstrapping method (Zhang et al., 2004).
Here is how it works: suppose we have a testing set T 0 to test several word segmentation systems, there are N testing examples (sentences or line of characters) in T 0 . We create a new testing set T 1 with N examples by sampling with replacement from T 0 , then repeat these process M − 1 times. And we will have a total M + 1 testing sets. In our test procedures, M is set to 2000.
Since we just implement our joint model and its component models, we can not generate paired samples for other models (i.e. ESA and NPY(n)). Instead, we follow Wang et al. (2010)'s method and first calculate the 95% confidence interval for our proposed model. Then other systems can be compared with the joint model in this way: if the F-score of system B doesn't fall into the 95% confidence interval of system A, they are considered as statistically significantly different from each other.
For all significant tests, we measure the 95% confidence interval for the difference between two models. First, the test results show that "HDP+nVBE" and "HDP+HMM" are both significantly better than "HDP". Second, the "Joint" model significantly outperforms all its component models, including "HDP", "nVBE", "HDP+nVBE" and "HDP+HMM". Finally, the comparison also shows that the joint model significantly outperforms state-of-the-art systems like ESA and NPY(n).

Conclusion
In this paper, we proposed a joint model for unsupervised Chinese word segmentation. Our joint model is a combination of the HDP-based model, which is a word-based model, and HMM-based model, which is a character-based model. The way we combined these two component baselines makes it natural and simple to inference with Gibbs sampling. Then the joint model take advantage of a goodness-based method (nVBE) by using it to initialize the sampler. Experiment results conducted on PKU and MSRA datasets provided by the second SIGHAN Bakeoff show that the proposed joint model not only outperforms the baseline systems but also achieves better performance (F-Score) over several state-of-the-art systems. Significance tests showed that the improvement is statistically significant. Analysis also indicates that the joint model has a stronger ability to solve ambiguities in Chinese word segmentation. In summary, the joint model we proposed combines the strengths of character-based model, nonparametric Bayesian language model and goodness-based model.