Nonparametric Bayesian Semi-supervised Word Segmentation
Daichi Mochihashi
Ryo Fujii Ryo Domoto
The Institute of Statistical Mathematics
Hakuhodo Inc. R&D Division
10-3 Midori-cho, Tachikawa city, Tokyo
5-3-1 Akasaka, Minato-ku, Tokyo{ryo.b.fujii,ryo.domoto}@hakuhodo.co.jp daichi@ism.ac.jp
Abstract
This paper presents a novel hybrid generative/discriminative model of word segmentation based on nonparametric Bayesian methods. Unlike ordinary discriminative word segmentation which relies only on labeled data,
our semi-supervised model also leverages ahuge amounts of unlabeled text to automatically learn new “words”, and further constrains them by using a labeled data to segment non-standard texts such as those foundin social networking services.
Specifically, our hybrid model combines adiscriminative classifier (CRF; Lafferty et al.
(2001) and unsupervised word segmentation(NPYLM; Mochihashi et al. (2009)), with atransparent exchange of information between
these two model structures within the semisupervised framework (JESS-CM; Suzuki and
Isozaki (2008)). We confirmed that it canappropriately segment non-standard texts likethose in Twitter and Weibo and has nearlystate-of-the-art accuracy on standard datasets
in Japanese, Chinese, and Thai.

1 Introduction
For any unsegmented language, especially East
Asian languages such as Chinese, Japanese andThai, word segmentation is almost an inevitable firststep in natural language processing. In fact, it is becoming increasingly important lately because of thegrowing interest in processing user-generated media, such as Twitter and blogs. Texts in such media
are often written in a colloquial style that contains
many new words and expressions that are not present
in any existing dictionaries. Since such words aretheoretically infinite in number, we need to leverage unsupervised learning to automatically identify
them in corpora.
For this purpose, ordinary supervised learning isclearly unsatisfactory; even hand-crafted dictionar-

ies will not suffice because functional expressions
more complex than simple nouns need to be recognized through their relationship with other words in
text, which also might be unknown in advance. Previous studies of this issue used character and word
information in the framework of supervised learning(Kruengkrai et al., 2009; Sun et al., 2009; Sun andXu, 2011). However, they(1) did not explicitly model new words, or(2) did not give a seamless combination with discriminative classifiers (e.g., they just used athreshold to discriminate between known andunknown words).
In contrast, unsupervised word segmentation
methods (Goldwater et al., 2006; Mochihashi etal., 2009) use nonparametric Bayesian generativemodels for word generation to infer the “words”
only from observations of raw input strings. Thesemethods work quite well and have been used not
only for tokenization but also for machine translation (Nguyen et al., 2010), speech recognition (Leeand Glass, 2012; Heymann et al., 2014), and evenrobotics (Nakamura et al., 2014).
However, from a practical point of view, such
purely unsupervised approaches do not suffice.
Since they only aim to maximize the probability of
the language model on the observed set of strings,
they sometimes yield word segmentations that areãôO¦·¢{{ã:YÅèQBSUZØ$^|º{{{VV¤$•GV^Þ—×&NJOFN!á\$7BñÂ|×b·ö•i•i•°bi| KHËbº·i|äØ®{{{¹¹péýCPCPü{Öóyy${D1®A·p7'D.LýÕ<ÝúNzìí+ˆ$7Figure 1: Excerpt of Weibo tweets. It contains many “unknown” words such as novel proper nouns, terms fromlocal dialects, etc., that cannot be covered by ordinary labeled data or dictionaries.

different from human standards on low frequency
words.
To solve this problem, this paper describes a novel
combination of a nonparametric Bayesian generative model (NPYLM; Mochihashi et al. (2009))
and a discriminative classifier (CRF; Lafferty et al.
(2001)). This combination is based on a semisupervised framework called JESS-CM (Suzuki and
Isozaki, 2008), and it requires a nontrivial exchange
of information between these two models. In thisapproach, the generative and discriminative models
will “teach each other” and yield a novel log-linear
model for word segmentation.
Experiments on standard datasets of Chinese,
Japanese, and Thai indicate that this hybrid model
achieves nearly state-of-the-art accuracy on standard
corpora, and, thanks to our nonparametric Bayesianmodel of infinite vocabulary it can accurately segment non-standard texts like those in Twitter andWeibo (the Chinese equivalent of Twitter) without
any human intervention.
This paper is organized as follows. Section 2 introduces NPYLM which will be leveraged in theframework of JESS-CM, described in Section 3.
Section 4 introduces our model, NPYCRF, andthe necessary exchange of information, while Section 5 is devoted to experiments on datasets in Chinese, Japanese, and Thai. We analyze the results
and discuss future directions of research on semisupervised learning in Section 6 and conclude in
Section 7.

2 Unsupervised Word Segmentation
To acquire new words from an observation consisting of raw strings, a generative model of words
can be extremely useful for word segmentation.
Goldwater et al. (2006) showed that a bigram hierarchical Dirichlet process (HDP) model basedon Gibbs sampling can effectively find “words” insmall corpora. In extending this work, Mochihashi
et al. (2009) proposed a nested Pitman-Yor language
model (NPYLM), a hierarchical Bayesian language
model, where character n-grams (actually, ∞-grams(Mochihashi and Sumita, 2008)) are embedded inword n-grams, and an efficient dynamic programming algorithm for inference exists. Conceptually,NPYLM posits that an infinite number of spellings,

Character HPYLM
Word HPYLM

Figure 2: The structure of NPYLM by a Chinese Restaurant Process representation (replicated from Mochihashi
et al. (2009)). The word and character HPYLM are drawn
as suffix trees; the character HPYLM is a base measurefor the word HPYLM, and the two are learned as a single
model. Each black customer is a count in HPYLM, and awhite customer is a latent proxy customer initiated fromeach black customer: see Teh (2006) for details.

i.e., “words”, are probabilistically generated fromcharacter n-grams, and a word unigram is drawn using the character n-grams as the base measure. Thenbigram and trigram distributions are hierarchicallygenerated and the final string is yielded from the“word” n-grams, as shown in Figure 2.
Practically, NPYLM can be considered as a hierarchical smoothing of the Bayesian n-gram language model, HPYLM (Teh, 2006). In HPYLM, thepredictive distribution of a word w = wt given a history h = wt−(n−1) · · · wt−1 is expressed asp(w|h) =c(w|h)−d·thw θ+d·th ·+·p(w|h′ ) (1)θ+c(h)
θ+c(h)

where c(w|h) denotes the observed counts,
P θ and d
are model parameters, and thw and th· = w thw arelatent variables estimated in the model.
The probability of w given h is recursively interpolated using a shorter historyh′ = wt−(n−2) · · · wt−1 . If h is already empty
at the unigram level, NPYLM employs a back-off
distribution using character n-grams for p(w|h′ ):p0 (w) = p(c1 · · · ck )Q
= ki=1 p(ci |c1 · · · ci−1 ) .

(2)
(3)

In this way, NPYLM can assign appropriate probabilities to every possible sequence of segmentation and learn the word and character n-grams at
the same time by using a single generative model(Mochihashi et al., 2009).
Semi-Markov view of NPYLM NPYLM formulates unsupervised word segmentation as learningwith a semi-Markov model (Figure 3). Here, eachnode corresponds to an inside probability α[t][k]1
that equals the probability of a substring ct1 =
c1 · · · ct with the last k characters ctt−k+1 being aword. This inside probability can be computed recursively as follows:LX
p(ctt−k+1 |ct−k
α[t][k] =t−k−j+1 ) · α[t−k][j] (4)j=1Here, 1 ≤ L ≤ t−k is the maximum allowed length ofa word. With these inside probabilities, we can makeuse of Markov Chain Monte Carlo (MCMC) methodwith an efficient forward filtering-backward sampling algorithm (Scott, 2002), namely a “stochastic Viterbi” algorithm to iteratively sample “words”
from raw strings in a completely unsupervised fashion, while avoiding local minima.
Problems and Beyond Unsupervised word segmentation with NPYLM works surprisingly well formany languages (Mochihashi et al., 2009); however,it has certain issues. First, since it optimizes theperformance of the language model, its segmentation does not always conform to human standards
and depends on subtle modeling decisions. For example, NPYLM often separates inflectional suffixes
in Japanese like “る” in “見–る” from the rest of
the verb, when it is actually a part of the verb itself. Second, it can produce deficient segmentations for low-frequency words and the beginning or
ending of a string where the available information
comes from only one direction. These issues canbe alleviated by using naı̈ve semi-supervised learning method (Mochihashi et al., 2009) that simply

Figure 3: Semi-Markov model representation of NPYLM(simplest case of segment length ≤ 3). Each node corresponds to a substring ending at time t, and its length k isindexed by each row.
1
While we consider only bigrams in this paper for simplicity, the theory can be naturally extended to higher-order ngrams. However, it requires quite a complicated implementation, and the expected gain in performance will not be large,
even if we use trigrams (Mochihashi et al., 2009).

Figure 4: Semi-supervised learning of the same model
structure (HMM and CRF) with JESS-CM. Discriminative and generative potentials are given relative weights
1 : λ0 , and added together in the log probability domain.

adds n-gram counts from supervised segmentationsin advance. However, this solution is not perfectbecause these supervised counts will eventually beoverwhelmed by the unsupervised counts, because
the overall objective function remains unsupervised.
To resolve this issue, we must resort to an explicit
semi-supervised learning framework that combines
both discriminative and generative models. We used
JESS-CM (Suzuki and Isozaki, 2008), currently thebest such framework for this purpose, which we will
briefly introduce below.

3 Integration with a Discriminative Model
JESS-CM (Joint probability model Embedding styleSemi-Supervised Conditional Model) is a semisupervised learning framework that outperforms
other generative and log-linear models (Druck and
McCallum, 2010). In JESS-CM, the probability of alabel sequence y given an input sequence x is written as follows:p(y|x) ∝ pDISC (y|x; Λ) pGEN (y, x; Θ)λ0(5)where pDISC and pGEN are respectively the discriminative and generative models, and Λ and Θ are theircorresponding parameters. Equation (5) is the product of the experts, where each expert works as a“constraint” to the other with a relative geometricalinterpolation weight 1 : λ0 . If we take pDISC to be alog-linear model like CRF (Lafferty et al., 2001):
P

K
pDISC (y|x) ∝ exp
λ
f
(y,
x)
, (6)
k
k
k=1
Equation (5) can be also expressed as a loglinear model with a new “feature function”
log pGEN (y, x):Pp(y|x) ∝ exp λ0 log pGEN (y, x) + K
λ
f
(y,
x)
k=1 k k= exp (Λ · F (y, x)) .

(7)

東 京 都 の “都” 東 京 都 のHere, the parameter Λ = (λ0 , λ1 , · · · , λK ) includes
1
the interpolation weight λ0 and“京都”⇐⇒
F (y, x) = (log pGEN (y, x), f1 (y, x), · · · , fK (y, x)).
0“東京都”
JESS-CM interleaves the optimization of Λ and Θ
to maximize the objective functionp(Yl , Xu |Xl ; Λ, Θ) = p(Yl |Xl ; Λ) · p(Xu ; Θ) (8) Figure 5: Equivalence of semi-Markov (left) and Markov

where hXl , Yl i is the labeled dataset and Xu is theunlabeled dataset.
Suzuki and Isozaki (2008) conducted semisupervised learning on a combination of a CRF andan HMM, as shown in Figure 4. Since CRF and
HMM have the same Markov model structure, theyinterpolate two weightsPK(9)
k=1 λk fk (yt , yt−1 , x) and
λ0 log pGEN (yt |yt−1 , x)

(10)on the corresponding path, altenately• fixing Θ and optimizing Λ of CRF on hXl , Yl i,and• fixing Λ and optimizing Θ of HMM on Xu
until convergence, and thereby iteratively maximizing the two terms in (8).
Through this optimization, pDISC and pGEN will“teach each other” to make the feature log pGEN
more accurate, and further rectified by pDISC withrespect to the labeled data. Note that the interpolation weight λ0 is automatically computed throughthis process.

4 Connecting Two Worlds: NPYCRF
We wish to integrate NPYLM and CRF, applying
semi-supervised learning via JESS-CM. Note that
Suzuki and Isozaki (2008) implicitly assumed thatthe discriminative and generative models have thesame structure as shown in Figure 4. Since NPYLM
is a semi-Markov model as described in Section 2, anaı̈ve approach would be to combine it with a semiMarkov CRF (Sarawagi and Cohen, 2005) as the discriminative model.
However, this strategy does not work well for
two reasons: First, since a semi-Markov CRF is amodel for transitions between segments, it cannot
deal with character-level transitions and thus performs suboptimally on its own. In fact, our preliminary supervised word segmentation experiments
showed a F1 measure of around 95%, whereas a(right) potentials. The potential of substring “東京都”(Tokyo prefecture) being a word on the left is equivalent
to the sum of potentials along the U-shaped path on theright.

character-wise Markov CRF achieves >99%. Second, the semi-Markov CRF was originally designed
to chunk at most a few words (Sarawagi and Cohen,2005). However, in word segmentation of Japanese,for example, we often encounter long proper nouns
or Katakana sequences that are more than ten characters, requiring a huge amount of memory even fora small dataset.
In this paper we instead transparently exchange
information between the Markov model (CRF) on
characters and the semi-Markov model (NPYLM)
on words to perform a semi-supervised learning on
different model structures. Called NPYCRF, thisunified statistical model makes good use of the discriminative model (CRF) from the labeled data andthe generative model (NPYLM) from the unlabeled
data.
4.1

CRF→NPYLM

To convert from a CRF to NPYLM, we can easilytranslate Markov potentials into semi-Markov potentials as shown in Andrew (2006) for the supervised learning case.
Consider the situation depicted in Figure 5. Here
we can see that the potential of the substring “東京都” (Tokyo prefecture) in the semi-Markov model(left) corresponds to the sum of the potentials in
the Markov model (right) along the path shown inbold. Here, we introduce binary hidden states in theMarkov model for each character, similarly to the BI
tags used in supervised learning, where state 1 represents the beginning of a word and state 0 represents
a continuation of the word.
Mathematically, we define γ[a, b) as the sum of
the potentials along a U-shaped path over an interval [a, b) (a < b) as shown in Figure 5, which begins
with state 1 and ends with (but does not include) 1.

t−kt−k−j +1 t−k+1 tjkt−k+1 t

k

t+1
t+j

j

Figure 6: Substring transitions for marginalization.

Using this notation, the potential that corresponds toα[t][k] is γ[t − k + 1, t + 1) covering ct−k+1 · · · ct ,and thus the forward recursion of the inside probability α[t][k] that incorporates the information fromthe CRF can be written as follows, instead of (4):LhX
exp λ0 log p(ctt−k+1 |ct−k
α[t][k] =t−k−j+1 )i
j=1+ γ[t−k+1, t+1) · α[t−k][j]. (11)Backward sampling can be performed in a similar
fashion. In this way, we can incorporate informationfrom the character-wise discriminative model (CRF)
into the language model segmentation of NPYLM.
4.2

NPYLM→CRF

On the other hand, translating the information fromthe semi-Markov to Markov model, i.e., translating a potential from the word-based language model
into the character-wise discriminative classifier, is
not trivial. However, as we describe below, it is actually possible to do so by extending the techniqueproposed in Andrew (2006).
Note that for the inference of CRF, from the standard theory of log-linear models we only have tocompute its gradient with respect to the expectationof each feature in the current model. This reduces
the problem to a computation of the marginal probability of each path, which can be derived within theframework of semi-Markov models as follows:
Semi-Markov feature λ0 . Following the line ofargument presented in the Section 4.1, the potential with respect to the semi-Markov feature
weight λ0 that is associated with the word transit
tion ct−kt−k−j+1 → ct−k+1 , shown in Figure 6, canbe expressed as an expectation using the standard
forward-backward formula:bility similar to (11) computed byLhXt
exp λ0 log p(ct+j
β[t][k] =t+1 |ct−k+1 )i
j=1
γ[t+1, t+j +2) · β[t+j][j] . (13)Markov features λ1 , · · · , λK . Note that the features associated with label bigrams in our binary
CRF can be divided into four types: 1-1,1-0,0-1, and
0-0, as shown in Figure 7.
Case 1-1: As shown in Figure 8(a), this case meansthat a word of length 1 begins at time t, which isequivalent to the probability of substring ctt beinga word:p(zt = 1, zt+1 = 1|s) = p(ctt |s).

(14)

Here, p(ckℓ |s) is the marginal probability of a substring cℓ · · · ck being a word, which can be derived
from equation (12):
X
ℓ−1
|s)
p(ckℓ |s) =p(ckℓ , cℓ−jjX=
α[ℓ−1][j] · β[k][k−ℓ+1] ·
j h
i
ℓ−1
) + γ[ℓ, k+1) /Z(s)exp λ0 log p(ckℓ |cℓ−j
β[k][k−ℓ+1] Xℓ−1)·
exp λ0 log p(ckℓ |cℓ−j
=
Z(s)
j

+ γ[ℓ, k+1) α[ℓ−1][j]α[k][k−ℓ+1] · β[k][k−ℓ+1]
=
(15)
Z(s)
Case 1-0: As shown in Figure 8(b), this case meansthat a word begins at time t and has length atleast 2. Since we do not know the endpoint of
this word, we can obtain the probability p(zt =1, zt+1 = 0) by marginalizing over the endpoint j(· · · means values all 0):p(zt = 1, zt+1 = 0|s)X=p(zt = 1, zt+1 = 0, · · · , zt+j = 1|s)
j=2

=

X

p(ctt+j−1 |s)

(16)

j=2

p(ctt−k+1 , ct−kt−k−j+1 |s) = α[t−k][j] β[t][k] ·hi
exp λ0 log p(ctt−k+1 |ct−k)+
γ[t−k+1,
t+1)
t−k−j+1/Z(s) (12)Here, Z(s) is a normalizing constant associated witheach input string s, and β[t][k] is a backward proba-

Figure 7: Four types of label transitions in Markov CRF.

(a) Case of 1–1(b) Case of 1–0(c) Case of 0–1

Figure 8: Label bigram potentials for marginalization.
The probability of each label bigram (bold) of the Markov
model can be obtained by marginalizing the probabilityof the U-shaped path including it, which is computed in
the semi-Markov model.

where p(ctt+j−1 |s) is obtained from (15).
Case 0-1: Similarly, as shown in Figure 8(c) thiscase means that a word of length at least 2 begins
before time t and ends at time t. Therefore, we
can marginalize over the start point of a possible
word to obtain the marginal probability:p(zt = 0, zt+1 = 1|s)X=p(zt−j = 1, · · · , zt = 0, zt+1 = 1|s) (17)
j=1

=

X

p(ctt−j |s) .

(18)

j=1

Case 0-0: In principle, this means that a word begins before time t and ends later than (and including) time t + 1. Therefore, we can marginalize
over both the start and end time of a possible word
spanning [t, t+1] to obtain:XXp(zt = 0, zt+1 = 0|s) =p(ct+kt−j |s) . (19)j=1 k=1

However, in fact we can avoid this nested computation because the probability of p(zt , zt+1 ) overthe possible values of zt and zt+1 must sum to
1. We can therefore simply calculate it as follows(Andrew, 2006):

and Tanner, 1990) shown in Figure 9.2 In learning ofa NPYLM, we add the CRF potentials as describedin Section 4.1, and sample a possible segmentation from the posterior through Forward filteringBackward sampling to update the model parameters.
On the basis of this improved language model, theCRF weights are then optimized by incorporating
language model features as explained in Section 4.2.
We iterate this process until convergence.
Note that we first have to learn an unsupervised
segmentation in Step 2 before training the CRF.
Since our inference algorithm includes an optimization of CRF and thus is not a true MCMC, the learning of word segmentation after the supervised information will be severely constrained and likely to getstuck in local minima.
In practice, we found that the EM-style batchlearning of CRF described above often fails because
our objective function is non-convex. Therefore, we
switched to ADF below (Sun et al., 2014), an adaptive stochastic gradient descent that yields state-ofthe-art accuracies for natural language processing
problems including word segmentation. In this case,Λ in Figure 9 was optimized with each minibatch
through the labeled data hXl , Yl i, while incorporating information from the unlabeled data Xu by thelanguage model.
Because of its heavy computational demands,
1: Add hYl , Xl i to NPYLM.
2: Optimize Λ on hYl , Xl i. (pure CRF)
3: for j = 1 · · · M do
4:
for i = randperm(1 · · · N ) do
5:
if j > 1 then(i)6:Remove customers of Xu from NPYLM Θ
7:
end if(i)
8:Draw segmentations of Xu from NPYCRF(i)

9:
Add customers of Xu to NPYLM Θ
10:
end for11:
Optimize Λ of NPYCRF on hYl , Xl i.
12: end for(i)Figure 9: Basic learning algorithm for NPYCRF. Xu
denotes the i-th sentence in the unlabeled data Xu . Wep(zt = 0, zt+1 = 0|s) = 1−p(1, 1)−p(1, 0)−p(0, 1) can also iterate steps 4 to 10 several times until Θ approx(20) imately converges, before updating Λ.

where p(x, y) means p(zt = x, zt+1 = y|s).
4.3

Inference

Finally, we obtain the inference algorithm for NPYCRF as a variant of the MCMC-EM algorithm (Wei2
It is possible to fix NPYLM and just use this as a feature
to CRF: this amounts to running only the first iteration (j = 1)of the EM algorithm. However, it still requires NPYLM→CRF
conversion in Section 4.2, and we found that the performance is
not optimal while slightly better than plain CRF.

Language

Dataset Labeled Unlabeled
Test
MSR
86,924
865,679 3,985
Chinese
Weibo 10K-40K 880,9203 30,000
Japanese
Twitter
59,931600,000
444
ThaiInterBEST 10,000
30,133 10,000
Table 1: Statistics of the datasets for the experiments.

we parallelized the NPYLM sampling over several processors and because of the possible correlation of segmentations within the samples, used theMetropolis-Hastings algorithm to correct them. The
acceptance rate in our experiments was over 99%.
For decoding, we can simply find a Viterbi path in
the integrated semi-Markov model while fixing all
the sampled segmentations on the unlabeled data.

5 Experiments
We conducted experiments on several corpora of unsegmented languages: Japanese, Chinese, and Thai.
The corpora included standard corpora as well astext from Twitter and its equivalent, Weibo, in Chinese.
5.1

Data

Chinese For Chinese, we first used a standard
dataset from the SIGHAN Bakeoff 2005 (Emerson,2005) for the labeled and test data, and Chinese gigaword version 2 (LDC2009T14) for the unlabeled
data. We chose the MSR subset of SIGHAN Bakeoff
written in simplified Chinese together with the provided training and test splits, which contain about
87K/40K sentences, respectively. For the unlabeled
data, i.e., a collection of raw strings, we used a random subset of 880K sentences from Chinese gigaword with all spaces removed. We chose this size tobe about 10 times larger than the labeled data, considering current computational requirements. We
used the part from the Xinhua news agency 2004 andsplit the data into sentences at the end-of-sentence
character “。”.
Because the MSR and Xinhua datasets were compiled from newspapers, to meet our objective on informal text we conducted further experiments using

Name
Sun+ (2009)
Sun+ (2014)
Chen+ (2015)
Zhang+ (2016)
NPYCRFNPYCRF

Labels2
3
4 (Neural)
2 (Neural)
2
3

F
N/A
N/A
0.976
0.977
0.970
0.973

Filtered
0.973
0.975
–
–
0.973
0.976

Table 2: Accuracies of Bakeoff MSR dataset in Chinese.
“Filtered” are the results with a simple post-hoc filter described in Sun et al. (2009).

Label Unlabel IV OOVF
Data
Topline880K–
0.981 0.699 0.977
Sup 10K
10K–
0.949 0.690 0.928
Sup 20K
20K–
0.957 0.683 0.941
40K–
0.963 0.682 0.951
Sup 40K
Semi 10K 10K 870K 0.954 0.698 0.933
Semi 20K 20K 860K 0.961 0.690 0.945
Semi 40K 40K 840K 0.970 0.648 0.955
Table 3: Accuracies on Leiden Weibo corpus in Chinese.
‘Label’ and ‘Unlabel’ are the amounts of labeled and unlabeled data, respectively. “Topline” is an ideal situationof complete supervision, and K= 103 sentences.

the Leiden Weibo corpus4 from Weibo, a Twitter
equivalent in China. From this dataset, we used thesentences that have exact correspondence between
the provided segmented-unsegmented pair, yielding
about 880K sentences. Since we did not know how
much supervision would be necessary for a decent
performance, we conducted experiments with different amounts of labeled data: 10K, 20K, 40K and
880K(all). Note that the final case amounts to complete supervision, an ideal situation that is not likely
in practice.
Japanese Word segmentation accuracies around
99% have already been reported for newspaper domains in Japanese (Kudo et al., 2004). Therefore, weonly conducted experiments on segmenting Twitter
text. In addition to our random Twitter crawl in April
2014, we used a corpus of Japanese Twitter text
compiled by the Tokyo Metropolitan University5 .
This corpus is actually very small, 944 sentences. It
mainly targets transfer learning and is segmented according to BCCWJ (Basic Corpus of Contemporary

3

This is the total number of sentences in the experiment: theactual number of unsupervised sentences is this set minus thedifferent number of supervised sentences.

4
5

http://www.leidenweibocorpus.nl/openaccess.php
https://github.com/tmu-nlp/TwitterCorpus

Written Japanese) standards from the National Institute of Japanese Language (Maekawa, 2007). Therefore, for the labeled data we used the “core” subset
of BCCWJ consisting of about 59K sentences plus
500 random sentences from the Twitter dataset. We
used the remaining 444 sentences for testing. For
the unlabeled data, we used a random crawl of 600K
Japanese sentences collected from Twitter in MarchApril, 2014.
Thai Unsegmented languages, such as Thai, Lao,
Myanmar, and Kumer, are also prevalent in South
East Asia and are becoming increasingly important
targets of natural language processing. Thus we also
conducted an experiment on Thai, using the standard
InterBEST 2009 dataset (Kosawat, 2009). Since itis reported that the “novel” subset of InterBEST has
relatively low precision, we used this part with a random split of 10K sentences for supervised learning,
30K sentences for unsupervised learning, and a further 10K sentences for testing.
5.2

东软集团
19
游景玉
17
任尧森
17
南昆铁路
16
东方红三号”卫星
13刘积仁13ｉｎｔｅｒｎｅｔ
11
东宝
11
张肇群
10
彭云
10
玲英
10
抚州
10
亚仿
10
南丁格尔
9
中远香港集团
7
海尔-波普彗星7
第九届全国人民代表大会 6
巨型机
6

にゃん
セフレ
フォロワー
https
December
トナカイ
アオサギ
フォロバ
じゅん
環奈
リプ
トッキュウジャー
リフォロー
酔っ払い
ツイート
クシャミ
エタフォ
まじかよ
ググれ
ふりふり

6
6
5
4
4
3
3
3
3
3
3
2
2
2
2
2
2
2
2
2

(a) MSR (Simplified Chinese) (b) Twitter (Japanese)
Figure 10: New words acquired by NPYCRF. For eachfigure, the left column is the words that did not appear
in the provided labeled data, and the right column is thefrequencies NPYCRF recognized in the test data. In Chinese, we found many proper names including company
and person name, and in Japanese, we found many novel
slang words and proper names.

Training Settings

Because Sun et al. (2012) report increased accuracy
with three tags, {B,I,E}6 , we also tried these tagsin place of the binary tags described in Section 4.2.
This modification resulted in 6 possible transitions
out of 32 = 9 transitions, whose computation follows from the binary case in Section 4.2. We usednormal priors of truncated N (1, σ 2 ) and N (0, σ 2 )for λ0 and λ1 · · · λK , respectively, and fixed the
CRF regularization parameter C to 1.0, and σ to 1.0
by preliminary experiments on the same data.
For the feature templates, we followed Sun et al.
(2012). In addition to those templates, we used character type bigrams, where the ‘character type’ wasdefined by Unicode blocks (like Hiragana or CJK
Unified Ideographs for Chinese and Japanese) or
Unicode character categories (Thai).
To reduce computations by restricting the search
space appropriately, we employed a Negative Binomial generalized linear model on string features(Uchiumi et al., 2015) to predict the maximum
length of a possible word for each character positionin the training data. Therefore, the upper limit of Lin (11) and (13) was Lt for each position t, obtained
6
The B, I, and E tags mean the beginning, internal part, andend of a word, respectively.

from this statistical model trained on labeled segmentations. We observed that this prediction madethe computation several times faster than, for example, using a fixed threshold in Japanese where quite
long words are occasionally encountered.
5.3

Experimental results

Chinese Tables 2 and 3 show IV (in-vocabulary)and OOV (out-of-vocabulary) precision and Fmeasure, computed against segmented tokens. The
results for standard newspaper text indicate that
NPYCRF is basically comparable in performance tostate-of-the-art supervised neural networks (Chen etal., 2015; Zhang et al., 2016) that require hand tuning of hyperparameters or model architectures. Figure 10 shows some of the learned words in the testset of the Bakeoff MSR corpus. As shown in Table 3, NPYCRF also yields higher precision than supervised learning on non-standard text like Weibo,
which is the main objective for this study. Contrary to ordinary supervised learning, we can see that
NPYCRF effectively learns many “new words” fromthe large amount of unlabeled data thanks to the generative model, while observing human standards ofsegmentation by the discriminative model. Note thatin Weibo segmentation, complete supervision is not

CRF

NPYLM

NPYCRF

Gold

有些
大学生
眼
高手
低
，
不屑
于
做
小
事情
。
王思斌

有些
大学生
眼高手低

有些
大学生
眼
高手
低
，
不屑于

有些
大学生
眼高手低

做
小
事情
。
王思斌

做
小
事情
。
王思斌

，
男
，

做
小
事情
。
王
思
斌
，
男
，

，
男
，

，
男
，

１９４９年１０月

１９４９年

１９４９年１０月

１９４９年１０月

生
。

生
。

生
。

，
不屑于

１０月

生
。

，
不屑于

Figure 11: Example of segmentation of the SIGHAN
Bakeoff MSR dataset made with supervised (CRF), unsupervised (NPYLM), and semi-supervised (NPYCRF)
models in comparison with gold segmentations (Gold).
“眼高手低” is a proverb and “王思斌” is a full name of aperson.

available in practice. In fact, we realized that the
Weibo segmentations were given automatically byan existing classifier, and contain many inappropriate segmentations, while NPYCRF finds much “better” segmentations.
Figure 11 compares the results of CRF, NPYLM,
and NPYCRF with the gold segmentation. While
proverbs like “眼高手低” (wide vision without action) are correctly captured from the unlabeled data
by NPYLM, it is sometimes broken by CRF throughintegration. In another case, the name of a person is properly connected because of the information provided by the CRF. This comparison showsthat there is still room for improvement in NPYCRF.
Section 6 discusses future research directions for improvements.
Japanese and Thai Figure 12 shows an exampleof the analysis of Japanese Twitter text. Shaded
words are those that are not contained in labeleddata (BCCWJ core) but were found by NPYCRF.
Many segmentations, including new words, are correct. We expect NPYCRF would perform better withmore unlabeled data that are easily obtained.
Tables 4 and 5 show the segmentation accuraciesof the Twitter data in Japanese and novel data in

いや 他 で も 普通 に する よ シシルス サーチ 用 に
ボーナス 持ちピン と か も ある し
誰 だ スズカ エルフォトン に ぶっこん だ の…
電車 で 座っ て ん だ けど 、 目 の 前 が 酔っ払い が吊革 で フラフラ し て て ハラハラ する … 手遅れ に な
ら ない うち に 離脱 する か …
ひこ にゃん 音頭 だ にゃん ♪ ひこ にゃん ひこにゃん ひこ にゃん にゃん っ
ほんと です よ ほんと 嬉しい くっそ 倍率 やば そう 、、 、 ほんと それ ！ ！ みほりん と 参戦 し たい まぢ で
みほりんまま に も 会い たい
初めまして ♪ 私 は 絢瀬 絵里 役 の 鈴々 蝶 です ♪ 似て ない です が 、 応援 し て くれる と 嬉しい です ♪
ちょくちょく 絡みだす なら な w w w これ から も ちょ
くちょく 絡む から よろしく (｀ω´)

Figure 12: Samples of NPYCRF segmentation of Twitter text in Japanese that are difficult to analyze by ordinary supervised segmentation. It contains a lot of novel
words, emoticons, and colloquial expressions that are notcontained in the BCCWJ core text (shaded).

Thai. While there are no publicly available results
for these data (the InterBEST testset is closed during competition), NPYCRF achieved better accuracies than vanilla supervised segmentation based on
CRF. Considering that many new words were foundin Figure 12, for example, we believe NPYCRF isquite competitive thanks to its ability to learn the infinite vocabulary, which it inherits from NPYLM.

6 Analysis
As shown in Figure 11, NPYCRF makes good useof NPYLM but sometimes ignores its prediction byfalling back to CRF, yielding suboptimal performance. This is mainly because the geometric interpolation weight λ0 is always constant and does
not vary according to the input. For example, even
if the substring to segment is very rare in the labeled data, NPYCRF trusts the supervised classifier (CRF) with a constant rate of 1/(1+ λ0 ) in thelog probability domain. To alleviate this problem,
Model
CRF
NPYCRF

IV
0.939
0.947

OOV
0.706
0.708

F
0.916
0.921

Table 4: Accuracies for Twitter text in Japanese.

Model
CRF
NPYCRF

IV
0.961
0.959

OOV
0.409
0.362

F
0.948
0.954

Table 5: Accuracies for InterBEST novel dataset in Thai.

it is necessary to change λ0 depending on the input string in a log-linear framework.7 While thismight be achieved through Density Ratio estimation
framework (Sugiyama et al., 2012; Tsuboi et al.,2009), we believe it is a general problem of semisupervised learning and is beyond the scope of thispaper.
This issue also affects the estimation of λ0 as ascalar: that is, we found that λ0 often fluctuates during training because Λ (which includes λ0 ) is estimated using only limited hXl , Yl i. In practice, we
terminated the EM algorithm in Figure 9 early after a few iterations. Therefore, with a more adaptive
semi-supervised learning framework, we expect that
NPYCRF will achieve higher accuracy than the current performance.

7 Conclusion
In this paper, we presented a hybrid generative/discriminative model of word segmentation,leveraging a nonparametric Bayesian model for unsupervised segmentation. By combining CRF andNPYLM within the semi-supervised framework of
JESS-CM, our NPYCRF not only works as wellas the state-of-the-art neural segmentation without
hand tuning of hyperparameters on standard corpora, but also appropriately segments non-standard
texts found in Twitter and Weibo, for example, byautomatically finding “new words” thanks to a nonparametric model of infinite vocabulary.
We believe that our model lays the foundation fordeveloping a methodology of combining nonparametric Bayesian models and discriminative classifiers, as well as providing an example of semisupervised learning on different model structures,
i.e. Markov and semi-Markov models for word segmentation.

Acknowledgments
We are deeply grateful to Jun Suzuki (NTT CS
Labs) for important discussions leading to this research, Xu Sun (Peking University) for details of
his experiments in Chinese. We would also like tothank anonymous reviewers and the action editor,
7

This is reminiscent of context-dependent Bayesian smoothing of MacKay (1994) in the probability domain, as opposed to
the fixed Jelinek-Mercer smoothing (Goodman, 2001).

especially the editors-in-chief for the thorough comments for the final manuscript.

References
Galen Andrew. 2006. A Hybrid Markov/Semi-Markov
Conditional Random Field for Sequence Segmentation. In EMNLP 2006, pages 465–472.
Xinchi Chen, Xipeng Qiu, Chenxi Zhu, and Xuanjing
Huang. 2015. Gated Recursive Neural Network for
Chinese Word Segmentation. In ACL 2015, pages
1744–1753.
Gregory Druck and Andrew McCallum. 2010. HighPerformance Semi-Supervised Learning using Discriminatively Constrained Generative Models. In
ICML 2010, pages 319–326.
Tom Emerson. 2005. The Second International Chinese
Word Segmentation Bakeoff. In Proceedings of the
Fourth SIGHAN Workshop on Chinese Language Processing.
Sharon Goldwater, Thomas L. Griffiths, and Mark Johnson. 2006. Contextual Dependencies in Unsupervised
Word Segmentation. In Proceedings of ACL/COLING
2006, pages 673–680.
Joshua T. Goodman. 2001. A Bit of Progress in Language Modeling, Extended Version. Technical Report
MSR–TR–2001–72, Microsoft Research.
Jahn Heymann, Oliver Walter, Reinhold Häb-Umbach,and Bhiksha Raj. 2014. Iterative Bayesian Word
Segmentation for Unsupervised Vocabulary Discovery from Phoneme Lattices. In ICASSP 2014, pages
4057–4061.
Krit Kosawat. 2009. InterBEST 2009: Thai Word Segmentation Workshop. In Proceedings of 2009 EighthInternational Symposium on Natural Language Processing (SNLP2009), Thailand.
Canasai Kruengkrai, Kiyotaka Uchimoto, Junichi
Kazama, Kentaro Torisawa, Hiroshi Isahara, andChuleerat Jaruskulchai. 2009. A word and charactercluster hybrid model for Thai word segmentation. In
Eighth International Symposium on Natural Lanugage
Processing.
Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto.
2004.
Applying Conditional Random Fields toJapanese Morphological Analysis. In EMNLP 2004,
pages 230–237.
John Lafferty, Andrew McCallum, and Fernando Pereira.
2001. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In
Proc. of ICML 2001, pages 282–289.
Chia-ying Lee and James Glass. 2012. A Nonparametric
Bayesian Approach to Acoustic Model Discovery. In
ACL 2012, pages 40–49.

David J. C. MacKay and L. Peto. 1994. A Hierarchical
Dirichlet Language Model. Natural Language Engineering, 1(3):1–19.
Kikuo Maekawa. 2007. Kotonoha and BCCWJ: Development of a Balanced Corpus of Contemporary Written Japanese. In Corpora and Language Research:
Proceedings of the First International Conference on
Korean Language, Literature, and Culture, pages 158–
177.
Daichi Mochihashi and Eiichiro Sumita. 2008. The Infinite Markov Model. In Advances in Neural Information Processing Systems 20 (NIPS 2007), pages 1017–
1024.
Daichi Mochihashi, Takeshi Yamada, and Naonori Ueda.
2009. Bayesian Unsupervised Word Segmentation
with Nested Pitman-Yor Language Modeling. In Proceedings of ACL-IJCNLP 2009, pages 100–108.
Tomoaki Nakamura, Takayuki Nagai, Kotaro Funakoshi,
Shogo Nagasaka, Tadahiro Taniguchi, and Naoto Iwahashi. 2014. Mutual Learning of an Object Concept
and Language Model Based on MLDA and NPYLM.
In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’14), pages 600–607.
ThuyLinh Nguyen, Stephan Vogel, and Noah A. Smith.
2010. Nonparametric Word Segmentation for Machine Translation. In COLING 2010, pages 815–823.
Sunita Sarawagi and William W. Cohen. 2005. SemiMarkov Conditional Random Fields for Information
Extraction. In Advances in Neural Information Processing Systems 17 (NIPS 2004), pages 1185–1192.
Steven L. Scott. 2002. Bayesian Methods for Hidden
Markov Models. Journal of the American Statistical
Association, 97:337–351.
Masashi Sugiyama, Taiji Suzuki, and Takafumi
Kanamori. 2012. Density Ratio Estimation in
Machine Learning. Cambridge University Press.
Weiwei Sun and Jia Xu. 2011. Enhancing Chinese Word
Segmentation using Unlabeled Data. In EMNLP 2011,
pages 970–979.
Xu Sun, Yaozhong Zhang, Takuya Matsuzaki, Yoshimasa
Tsuruoka, and Jun’ichi Tsujii. 2009. A Discriminative Latent Variable Chinese Segmenter with Hybrid
Word/Character Information. In NAACL 2009, pages
56–64.
Xu Sun, Houfeng Wang, and Wenjie Li. 2012. Fast Online Training with Frequency-Adaptive Learning Rates
for Chinese Word Segmentation and New Word Detection. In ACL 2012, pages 253–262.
Xu Sun, Wenjie Li, Houfeng Wang, and Qin Lu. 2014.
Feature-Frequency-Adaptive Online Training for Fast
and Accurate Natural Language Processing. Computational Linguistics, 40(3):563–586.

Jun Suzuki and Hideki Isozaki. 2008. Semi-Supervised
Sequential Labeling and Segmentation Using GigaWord Scale Unlabeled Data. In ACL:HLT 2008, pages
665–673.
Yee Whye Teh. 2006. A Hierarchical Bayesian Language Model based on Pitman-Yor Processes. In Proceedings of ACL/COLING 2006, pages 985–992.
Yuta Tsuboi, Hisashi Kashima, Shohei Hido, Steffen
Bickel, and Masashi Sugiyama. 2009. Direct Density Ratio Estimation for Large-scale Covariate Shift
Adaptation. Information and Media Technologies,
4(2):529–546.
Kei Uchiumi, Hiroshi Tsukahara, and Daichi Mochihashi. 2015. Inducing Word and Part-of-speech with
Pitman-Yor Hidden Semi-Markov Models. In ACLIJCNLP 2015, pages 1774–1782.
Greg C.G. Wei and Martin A. Tanner. 1990. A Monte
Carlo Implementation of the EM Algorithm and thePoor Man’s Data Augmentation Algorithms. Journalof the American Statistical Association, 85(411):699–
704.
Meishan Zhang, Yue Zhang, and Guohong Fu. 2016.
Transition-Based Neural Word Segmentation. In ACL
2016.