Applying Conditional Random Fields to Japanese Morphological Analysis
Taku Kudo †∗ Kaoru Yamamoto‡ Yuji Matsumoto ††Nara Institute of Science and Technology
8916-5, Takayama-Cho Ikoma, Nara, 630-0192 Japan‡CREST JST, Tokyo Institute of Technology
4259, Nagatuta Midori-Ku Yokohama, 226-8503 Japan
taku-ku@is.naist.jp, kaoru@lr.pi.titech.ac.jp, matsu@is.naist.jp

Abstract
This paper presents Japanese morphological analysis based on conditional random fields (CRFs). Previous work in CRFs assumed that observation sequence (word) boundaries were fixed. However,word boundaries are not clear in Japanese, andhence a straightforward application of CRFs is notpossible. We show how CRFs can be applied tosituations where word boundary ambiguity exists.
CRFs offer a solution to the long-standing problems in corpus-based or statistical Japanese morphological analysis. First, flexible feature designs
for hierarchical tagsets become possible. Second,
influences of label and length bias are minimized.
We experiment CRFs on the standard testbed corpus
used for Japanese morphological analysis, and evaluate our results using the same experimental dataset
as the HMMs and MEMMs previously reported inthis task. Our results confirm that CRFs not only
solve the long-standing problems but also improve
the performance over HMMs and MEMMs.

1

Introduction

Conditional random fields (CRFs) (Lafferty et al.,2001) applied to sequential labeling problems areconditional models, trained to discriminate the correct sequence from all other candidate sequences
without making independence assumption for features. They are considered to be the state-of-the-art
framework to date. Empirical successes with CRFs
have been reported recently in part-of-speech tagging (Lafferty et al., 2001), shallow parsing (Shaand Pereira, 2003), named entity recognition (McCallum and Li, 2003), Chinese word segmentation (Peng et al., 2004), and Information Extraction(Pinto et al., 2003; Peng and McCallum, 2004).
Previous applications with CRFs assumed thatobservation sequence (e.g. word) boundaries are
fixed, and the main focus was to predict label∗

At present, NTT Communication Science Laboratories,
2-4, Hikaridai, Seika-cho, Soraku, Kyoto, 619-0237 Japantaku@cslab.kecl.ntt.co.jp

sequence (e.g. part-of-speech). However, wordboundaries are not clear in non-segmented languages. One has to identify word segmentation as
well as to predict part-of-speech in morphologicalanalysis of non-segmented languages. In this paper, we show how CRFs can be applied to situations
where word boundary ambiguity exists.
CRFs offer a solution to the problems in Japanesemorphological analysis with hidden Markov models(HMMs) (e.g., (Asahara and Matsumoto, 2000)) orwith maximum entropy Markov models (MEMMs)(e.g., (Uchimoto et al., 2001)). First, as HMMs are
generative, it is hard to employ overlapping features stemmed from hierarchical tagsets and nonindependent features of the inputs such as surrounding words, word suffixes and character types. Thesefeatures have usually been ignored in HMMs, despite their effectiveness in unknown word guessing.
Second, as mentioned in the literature, MEMMs
could evade neither from label bias (Lafferty etal., 2001) nor from length bias (a bias occurring
because of word boundary ambiguity). Easy sequences with low entropy are likely to be selectedduring decoding in MEMMs. The consequence isserious especially in Japanese morphological analysis due to hierarchical tagsets as well as wordboundary ambiguity. The key advantage of CRFs istheir flexibility to include a variety of features while
avoiding these bias.
In what follows, we describe our motivations ofapplying CRFs to Japanese morphological analysis(Section 2). Then, CRFs and their parameter estimation are provided (Section 3). Finally, we discuss experimental results (Section 4) and give conclusions with possible future directions (Section 5).

2 Japanese Morphological Analysis
2.1 Word Boundary Ambiguity
Word boundary ambiguity cannot be ignored when
dealing with non-segmented languages. A simple
approach would be to let a character be a token(i.e., character-based Begin/Inside tagging) so thatboundary ambiguity never occur (Peng et al., 2004).

“Input:
Lattice:

BOS

[Noun]
” (I live in Metropolis of Tokyo .)(Kyoto)(east)[Noun](capital)[Noun]

(Metro.)[Suffix](in)[Particle](resemble)

 (live)[Verb]

EOS[Verb](Tokyo)[Noun]

Figure 1: Example of lattice for Japanese morphological analysis
However, B/I tagging is not a standard method in
20-year history of corpus-based Japanese morphological analysis. This is because B/I tagging cannot
directly reflect lexicons which contain prior knowledge about word segmentation. We cannot ignore
a lexicon since over 90% accuracy can be achieved
even using the longest prefix matching with the lexicon. Moreover, B/I tagging produces a numberof redundant candidates which makes the decoding
speed slower.
Traditionally in Japanese morphological analysis,
we assume that a lexicon, which lists a pair of aword and its corresponding part-of-speech, is available. The lexicon gives a tractable way to build alattice from an input sentence. A lattice represents
all candidate paths or all candidate sequences of tokens, where each token denotes a word with its partof-speech 1 .
Figure 1 shows an example where a total of 6
candidate paths are encoded and the optimal pathis marked with bold type. As we see, the set of labels to predict and the set of states in the lattice aredifferent, unlike English part-of-speech tagging thatword boundary ambiguity does not exist.
Formally, the task of Japanese morphologicalanalysis can be defined as follows. Let x be an
input, unsegmented sentence. Let y be a path, asequence of tokens where each token is a pair ofword wi and its part-of-speech ti . In other words,
y = (hw1 , t1 i, . . . , hw#y , t#y i) where #y is thenumber of tokens in the path y. Let Y(x) be a set ofcandidate paths in a lattice built from the input sentence x and a lexicon. The goal is to select a correct
path ŷ from all candidate paths in the Y(x). The
distinct property of Japanese morphological analysis is that the number of tokens y varies, since theset of labels and the set of states are not the same.
1

If one cannot build a lattice because no matching word canbe found in the lexicon, unknown word processing is invoked.
Here, candidate tokens are built using character types, such as
hiragana, katakana, Chinese characters, alphabets, and numbers.

2.2 Long-Standing Problems
2.2.1 Hierarchical Tagset
Japanese part-of-speech (POS) tagsets used in
the two major Japanese morphological analyzers
ChaSen2 and JUMAN3 take the form of a hierarchical structure. For example, IPA tagset4 usedin ChaSen consists of three categories: part-ofspeech, conjugation form (cform), and conjugate
type (ctype). The cform and ctype are assigned only
to words that conjugate, such as verbs and adjectives. The part-of-speech has at most four levels of
subcategories. The top level has 15 different categories, such as Noun, Verb, etc. Noun is subdivided
into Common Noun, Proper Noun and so on. Proper
Noun is again subdivided into Person, Organization
or Place, etc. The bottom level can be thought as
the word level (base form) with which we can completely discriminate all words as different POS. If
we distinguish each branch of the hierarchical tree
as a different label (ignoring the word level), the total number amounts to about 500, which is muchlarger than the typical English POS tagset such as
Penn Treebank.
The major effort has been devoted how to interpolate each level of the hierarchical structure aswell as to exploit atomic features such as word suffixes and character types. If we only use the bottom level, we suffer from the data sparseness problem. On the other hand, if we use the top level,
we lack in granularity of POS to capture fine differences. For instance, some suffixes (e.g., san orkun) appear after names, and are helpful to detectwords with Name POS. In addition, the conjugation
form (cfrom) must be distinguished appearing onlyin the succeeding position in a bi-gram, since it isdominated by the word appearing in the next.
Asahara et al. extended HMMs so as to incorporate 1) position-wise grouping, 2) word-level statis2

http://chasen.naist.jp/
http://www.kc.t.u-tokyo.ac.jp/nl-resource/juman.html
4
http://chasen.naist.jp/stable/ipadic/
3

tics, and 3) smoothing of word and POS level statistics (Asahara and Matsumoto, 2000). However, theproposed method failed to capture non-independentfeatures such as suffixes and character types and selected smoothing parameters in an ad-hoc way.
2.2.2 Label Bias and Length Bias
It is known that maximum entropy Markov models (MEMMs) (McCallum et al., 2000) or other discriminative models with independently trained nextstate classifiers potentially suffer from the label bias
(Lafferty et al., 2001) and length bias. In Japanesemorphological analysis, they are extremely serious
problems. This is because, as shown in Figure 1,
the branching variance is considerably high, andthe number of tokens varies according to the output
path.

(a) Label bias

C
D

0.4

BOS

0.6

A

0.6

B

0.4

1.0

1.0

1.0

E

P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36
P(B, E | x) = 0.4 * 1.0 * 1.0 = 0.4(b) Length bias
0.6

BOS
0.4

A

C
D

0.4

0.6

B

P(A, D | x) = 0.6 * 0.6 * 1.0 = 0.36
P(B | x) = 0.4 * 1.0
= 0.4

EOS

1.0

P(A,D|x) < P(B,E|x)

1.0

1.0

EOS

1.0

P(A,D|x) < P(B |x)

Figure 2: Label and length bias in a lattice
An example of the label bias is illustrated in Figure 2:(a) where the path issearched by sequential combinations ofmaximum entropy models (MEMMs), i.e.,
Q#y
P (y|x) =Even
i=1 p(hwi , ti i|hwi−1 , ti−1 i).
if MEMMs learn the correct path A-D with independently trained maximum entropy models,the path B-E will have a higher probability andthen be selected in decoding. This is because thetoken B has only the single outgoing token E, andthe transition probability for B-E is always 1.0.
Generally speaking, the complexities of transitions
vary according to the tokens, and the transition
probabilities with low-entropy will be estimatedhigh in decoding. This problem occurs because thetraining is performed only using the correct path,

ignoring all other transitions.
Moreover, we cannot ignore the influence of thelength bias either. By the length bias, we mean thatshort paths, consisting of a small number of tokens,are preferred to long path. Even if the transition
probability of each token is small, the total probability of the path will be amplified when the path isshort 2:(b)). Length bias occurs in Japanese morphological analysis because the number of output
tokens y varies by use of prior lexicons.
Uchimoto et al. attempted a variant of MEMMs
for Japanese morphological analysis with a numberof features including suffixes and character types(Uchimoto et al., 2001; Uchimoto et al., 2002;
Uchimoto et al., 2003). Although the performanceof unknown words were improved, that of known
words degraded due to the label and length bias.
Wrong segmentation had been reported in sentences
which are analyzed correctly by naive rule-based or
HMMs-based analyzers.

3

Conditional Random Fields

Conditional random fields (CRFs) (Lafferty et al.,2001) overcome the problems described in Section 2.2. CRFs are discriminative models and canthus capture many correlated features of the inputs.
This allows flexible feature designs for hierarchicaltagsets. CRFs have a single exponential model forthe joint probability of the entire paths given the input sentence, while MEMMs consist of a sequential
combination of exponential models, each of which
estimates a conditional probability of next tokens
given the current state. This minimizes the influences of the label and length bias.
As explained in Section 2.1, there is word boundary ambiguity in Japanese, and we choose to use
a lattice instead of B/I tagging. This implies thatthe set of labels and the set of states are different, and the number of tokens #y varies according to a path. In order to accomodate this, we define CRFs for Japanese morphological analysis as
the conditional probability of an output path y =(hw1 , t1 i, . . . , hw#y , t#y i) given an input sequencex:

P (y|x) =

#y X
X

1
exp
λk fk (hwi−1 , ti−1 i, hwi , ti i) ,
Zx
i=1
k

where Zx is a normalization factor over all candidate paths, i.e.,Zx =X
y0 ∈Y(x)

#y0 X
X

0
exp
λk fk (hwi−1, t0i−1 i, hwi0 , t0i i) ,i=1k

fk (hwi−1 , ti−1 i, hwi , ti i) is an arbitrary feature function over i-th token hwi , ti i, and its previous token
hwi−1 , ti−1 i 5 . λk (∈ Λ = {λ1 , . . . , λK } ∈ RK ) is alearned weight or parameter associated with featurefunction fk .
Note that our formulation of CRFs is different
from the widely-used formulations (e.g., (Sha andPereira, 2003; McCallum and Li, 2003; Peng etal., 2004; Pinto et al., 2003; Peng and McCallum,2004)). The previous applications of CRFs assign
a conditional probability for a label sequence y =y1 , . . . , yT given an input sequence x = x1 , . . . , xT
as:
T X
X

1
P (y|x) =exp
λk fk (yi−1 , yi , x)
Zx
i=1
k

In our formulation, CRFs deal with word boundary
ambiguity. Thus, the the size of output sequence T
is not fixed through all candidates y ∈ Y(x). The
index i is not tied with the input x as in the original
CRFs, but unique to the output y ∈ Y(x).
Here, we introduce the global feature vector F(y, x) = {F1 (y, x), . . . , FK (y, x)}, whereP#y
Fk (y, x) =i=1 fk (hwi−1 , ti−1 i, hwi , ti i). Using
the global feature vector, P (y|x) can also be represented as P (y|x) = Z1x exp(Λ · F(y, x)). The
most probable path ŷ for the input sentence x is thengiven byŷ = argmax P (y|x) = argmax Λ · F(y, x),y∈Y(x)y∈Y(x)

which can be found with the Viterbi algorithm.
An interesting note is that the decoding process of
CRFs can be reduced into a simple linear combinations over all global features.
3.1 Parameter Estimation
CRFs are trained using the standard maximum
likelihood estimation, i.e., maximizing the loglikelihood LΛ of a given training set T ={hxj , yj i}N
j=1 ,To maximize LΛ , we have to maximize the difference between the inner product (or score) of thecorrect path Λ · F(yj , xj ) and those of all othercandidates Λ · F(y, xj ), y ∈ Y(xj ). CRFs isthus trained to discriminate the correct path fromall other candidates, which reduces the influencesof the label and length bias in encoding.
At the optimal point, the first-derivative of the
log-likelihood becomes 0, thus,
δLΛ
δλk

X

=



Fk (yj , xj ) − EP (y|xj ) Fk (y, xj )j= Ok − Ek = 0,

P
where Ok =j Fk (yj , xj ) is the count of featurekobservedinthe training data T , and Ek =
P
E
[F
(y,
xj )] is the expectation of feak
P
(y|x
)
j
j
ture k over the model distribution P (y|x) and T .
The expectation can efficiently be calculated using
a variant of the forward-backward algorithm.
EP (y|x) [Fk (y, x)] =P
X αhw0 ,t0 i · fk∗ · exp( k0 λk0 fk∗0 ) · βhw,tiZx{hw0 ,t0 i,hw,ti}∈B(x),where fk∗ is an abbreviation for fk (hw0 , t0 i, hw, ti),B(x) is a set of all bi-gram sequences observedin the lattice for x, and αhw,ti and βhw,ti are theforward-backward costs given by the following recursive definitions:
αhw,ti=X

αhw0 ,t0 i · exp

hw0 ,t0 i∈LT (hw,ti)

βhw,ti=X

βhw0 ,t0 i · exp

hw0 ,t0 i∈RT (hw,ti)

X
k

X


λk fk (hw0 , t0 i, hw, ti)
λk fk (hw, ti, hw0 , t0 i) ,kwhere LT (hw, ti) and RT (hw, ti) denote a set of
tokens each of which connects to the token hw, ti
from the left and the right respectively. Note that
initial costs of two virtual tokens, αhwbos ,tbos i andβhweos ,teos i , are set to be 1. A normalization constantΛ̂ = argmax LΛ , whereis then given by Zx = αhweos ,teos i (= βhwbos ,tbos i ).
Λ∈RKX
We attempt two types of regularizations in orderLΛ =log(P (yj |xj ))toavoid overfitting. They are a Gaussian prior (L2j
h

i
X
X
norm) (Chen and Rosenfeld, 1999) and a Laplacian=log
exp Λ · [F(yj , xj ) − F(y, xj )]prior (L1-norm) (Goodman, 2004; Peng and Mcjy∈Y(xj )Callum, 2004)
iXh=

Λ · F(yj , xj ) − log(Zxj ) .

j5

We could use trigram or more general n-gram feature functions (e.g., fk (hwi−n , ti−n i, . . . , hwi , ti i)), however we restrict
ourselves to bi-gram features for clarity.

LΛ = CX
jlog(P (yj |xj )) −1
2

P
Pk |λk |2
k |λk |

(L1-norm)(L2-norm)Below, we refer to CRFs with L1-norm and L2norm regularization as L1-CRFs and L2-CRFs respectively. The parameter C ∈ R+ is a hyperparameter of CRFs determined by a cross validation.
L1-CRFs can be reformulated into the constrained optimization problem below by letting−
λ k = λ+k − λk :
max :

C

X

log(P (yj |xj )) −

j

s.t.,

X

−
(λ+
k + λk )/2

k−λ+k ≥ 0, λk ≥ 0.

At the optimal point, the following Karush-KuhunTucker conditions satisfy: λ+k · [C · (Ok − Ek ) −−1/2] = 0, λk · [C · (Ek − Ok ) − 1/2] = 0, and|C · (Ok − Ek )| ≤ 1/2. These conditions mean−that both λ+k and λk are set to be 0 (i.e., λk = 0),
when |C · (Ok − Ek )| < 1/2. A non-zero weightis assigned to λk , only when |C · (Ok − Ek )| =1/2. L2-CRFs, in contrast, give the optimal solutionΛwhen δLδλk = C · (Ok − Ek ) − λk = 0. Omitting theproof, (Ok − Ek ) 6= 0 can be shown and L2-CRFs
thus give a non-sparse solution where all λk have
non-zero weights.
The relationship between two reguralizations
have been studied in Machine Learning community.
(Perkins et al., 2003) reported that L1-regularizer
should be chosen for a problem where most of givenfeatures are irrelevant. On the other hand, L2regularizer should be chosen when most of givenfeatures are relevant. An advantage of L1-based
regularizer is that it often leads to sparse solutions
where most of λk are exactly 0. The features assigned zero weight are thought as irrelevant features to classifications. The L2-based regularizer,
also seen in SVMs, produces a non-sparse solution
where all of λk have non-zero weights. All features
are used with L2-CRFs.
The optimal solutions of L2-CRFs can be obtained by using traditional iterative scaling algorithms (e.g., IIS or GIS (Pietra et al., 1997)) or more
efficient quasi-Newton methods (e.g., L-BFGS (Liuand Nocedal, 1989)). For L1-CRFs, constrained optimizers (e.g., L-BFGS-B (Byrd et al., 1995)) can beused.

4 Experiments and Discussion
4.1 Experimental Settings
We use two widely-used Japanese annotated corpora in the research community, Kyoto University Corpus ver 2.0 (KC) and RWCP Text Corpus(RWCP), for our experiments on CRFs. Note thateach corpus has a different POS tagset and details(e.g., size of training and test dataset) are summarized in Table 1.

One of the advantages of CRFs is that they are
flexible enough to capture many correlated features, including overlapping and non-independentfeatures. We thus use as many features as possible, which could not be used in HMMs. Table 2
summarizes the set of feature templates used in the
KC data. The templates for RWCP are essentiallythe same as those of KC except for the maximum
level of POS subcatgeories. Word-level templates
are employed when the words are lexicalized, i.e.,
those that belong to particle, auxiliary verb, or suffix6 . For an unknown word, length of the word, up
to 2 suffixes/prefixes and character types are usedas the features. We use all features observed in thelattice without any cut-off thresholds. Table 1 also
includes the number of features in both data sets.
We evaluate performance with the standard Fscore (Fβ=1 ) defined as follows:

where

Fβ=1

=

Recall

=P recision =2 · Recall · P recision,
Recall + P recision# of correct tokens# of tokens in test corpus# of correct tokens.
# of tokens in system output

In the evaluations of F-scores, three criteria of correctness are used: seg: (only the word segmentation
is evaluated), top: (word segmentation and the top
level of POS are evaluated), and all: (all information is used for evaluation).
The hyperparameters C for L1-CRFs and L2CRFs are selected by cross-validation. Experiments
are implemented in C++ and executed on Linuxwith XEON 2.8 GHz dual processors and 4.0 Gbyte
of main memory.
4.2 Results
Tables 3 and 4 show experimental results using
KC and RWCP respectively. The three F-scores(seg/top/all) for our CRFs and a baseline bi-gram
HMMs are listed.
In Table 3 (KC data set), the results of a variantof maximum entropy Markov models (MEMMs)(Uchimoto et al., 2001) and a rule-based analyzer(JUMAN7 ) are also shown. To make a fare comparison, we use exactly the same data as (Uchimoto etal., 2001).
In Table 4 (RWCP data set), the result of an extended Hidden Markov Models (E-HMMs) (Asa6These lexicalizations are usually employed in Japanesemorphological analysis.
7
JUMAN assigns “unknown POS” to the words not seen in
the lexicon. We simply replace the POS of these words withthe default POS, Noun-SAHEN.

Table 1: Details of Data Set
sourcelexicon (# of words)
POS structure# of training sentences# of training tokens# of test sentences# of test tokens# of features

KC

RWCP

Mainich News Article (’95)
JUMAN ver. 3.61 (1,983,173)

Mainich News Article (’94)
IPADIC ver. 2.7.0 (379,010)

2-levels POS, cfrom, ctype, base form

4-levels POS, cfrom, ctype, base form

7,958 (Articles on Jan. 1st - Jan. 8th)
198,5141,246 (Articles on Jan. 9th)
31,302
791,798

10,000 (first 10,000 sentences)
265,631
25,743 (all remaining sentences)655,710580,032

Table 2: Feature templates: fk (hw0 , t0 i, hw, ti)

t0 = hp10 , p20 , cf 0 , ct, bw0 i, t = hp1, p2, cf, ct, bwi, where p10 /p1

and p20 /p2 are the top and sub categories of POS. cf 0 /cf and ct0 /ct
are the cfrom and ctype respectively. bw0 /bw are the base form of thewords w0 /w.
type

template

hp1i
hp1, p2i
hbwi
hbw, p1i
hbw, p1, p2i
w is unknown
length of the word w
up to 2 suffixes × {φ, hp1i, hp1, p2i}
up to 2 prefixes × {φ, hp1i, hp1, p2i}
character type × {φ, hp1i, hp1, p2i}
Bigram
hp10 , p1i
basic features
hp10 , p1, p2i
hp10 , p20 , p1i
hp10 , p20 , p1, p2i
hp10 , p20 , cf 0 , p1, p2i
hp10 , p20 , ct0 , p1, p2i
hp10 , p20 , cf 0 , ct0 , p1, p2i
hp10 , p20 , p1, p2, cf i
hp10 , p20 , p1, p2, cti
hp10 , p20 , p1, p2, cf, cti
hp10 , p20 , cf 0 , p1, p2, cf i
hp10 , p20 , ct, p1, p2, cti
hp10 , p20 , cf 0 , p1, p2, cti
hp10 , p20 , ct0 , p1, p2, cf i
hp10 , p20 , cf 0 , ct0 , p1, p2, cf, cti
0
w is lexicalized
hp10 , p20 , cf 0 , ct0 , bw0 , p1, p2i
hp10 , p20 , cf 0 , ct0 , bw0 , p1, p2, cf i
hp10 , p20 , cf 0 , ct0 , bw0 , p1, p2, cti
hp10 , p20 , cf 0 , ct0 , bw0 , p1, p2, cf, cti
w is lexicalized
hp10 , p20 , p1, p2, cf, ct, bwi
hp10 , p20 , cf 0 , p1, p2, cf, ct, bwi
hp10 , p20 , ct0 , p1, p2, cf, ct, bwi
hp10 , p20 , cf 0 , ct0 , p1, p2, cf, ct, bwi
0w /w are lexicalized hp10 , p20 , cf 0 , ct0 , bw 0 , p1, p2, cf, ct, bwi
Unigrambasic features
w is known

hara and Matsumoto, 2000) trained and tested withthe same corpus is also shown. E-HMMs is applied
to the current implementation of ChaSen. Details of
E-HMMs are described in Section 4.3.2.
We directly evaluated the difference of these systems using McNemar’s test. Since there are nostandard methods to evaluate the significance of Fscores, we convert the outputs into the character-based B/I labels and then employ a McNemar’s
paired test on the labeling disagreements. This evaluation was also used in (Sha and Pereira, 2003). The
results of McNemar’s test suggest that L2-CRFs issignificantly better than other systems including L1CRFs8 . The overall results support our empirical
success of morphological analysis based on CRFs.
4.3 Discussion
4.3.1 CRFs and MEMMs
Uchimoto el al. proposed a variant of MEMMs
trained with a number of features (Uchimoto et al.,2001). Although they improved the accuracy for unknown words, they fail to segment some sentences
which are correctly segmented with HMMs or rulebased analyzers.
Figure 3 illustrates the sentences which are incorrectly segmented by Uchimoto’s MEMMs. The correct paths are indicated by bold boxes. Uchimoto etal. concluded that these errors were caused by nonstandard entries in the lexicon. In Figure 3, “ロマンは ” (romanticist) and “ない心” (one’s heart) are
unusual spellings and they are normally written as“ロマン派” and “内心” respectively. However, we
conjecture that these errors are caused by the influence of the length bias. To support our claim, thesesentences are correctly segmented by CRFs, HMMs
and rule-based analyzers using the same lexicon as(Uchimoto et al., 2001). By the length bias, shortpaths are preferred to long paths. Thus, single token “ロマンは ” or “ない心” is likely to be selectedcompared to multiple tokens “ロマン / は ” or “ない / 心”. Moreover, “ロマン ” and “ロマンは ” haveexactly the same POS (Noun), and transition probabilities of these tokens become almost equal. Consequentially, there is no choice but to select a shortpath (single token) in order to maximize the wholesentence probability.
Table 5 summarizes the number of errors in
HMMs, CRFs and MEMMs, using the KC data set.
Two types of errors, l-error and s-error, are given in
8

In all cases, the p-values are less than 1.0 × 10−4 .

Table 3: Results of KC, (Fβ=1 (precision/recall))systemseg
top
L2-CRFs (C = 1.2)
98.96 (99.04/98.88)
98.31 (98.39/98.22)
L1-CRFs (C = 3.0)
98.80 (98.84/98.77)
98.14 (98.18/98.11)
MEMMs (Uchimoto 01)
96.44 (95.78/97.10)
95.81 (95.15/96.47)
JUMAN (rule-based)
98.70 (98.88/98.51)
98.09 (98.27/97.91)
HMMs-bigram (baseline)
96.22 (96.16/96.28)
94.96 (94.90/95.02)

all
96.75 (96.83/96.67)
96.55 (96.58/96.51)
94.27 (93.62/94.92)
93.73 (93.91/93.56)
91.85 (91.79/91.90)

Table 4: Results of RWCP, (Fβ=1 (precision/recall))systemseg
top
all
L2-CRFs (C = 2.4)
99.11 (99.03/99.20)
98.73 (98.65/98.81)
97.66 (97.58/97.75)
L1-CRFs (C = 3.0)
99.00 (98.86/99.13)
98.58 (98.44/98.72)
97.30 (97.16/97.43)
98.87 (98.77/98.97)
98.33 (98.23/98.43)
96.95 (96.85/97.04)
E-HMMs (Asahara 00)
HMMs-bigram (baseline)
98.82 (98.69/98.94)
98.10 (97.97/98.22)
95.90 (95.78/96.03)

sea





particlebetMEMMs select 

4.3.2 CRFs and Extended-HMMs

romanticist

Asahara et al. extended the original HMMs by 1)
position-wise grouping of POS tags, 2) word-levelstatistics, and 3) smoothing of word and POS levelstatistics (Asahara and Matsumoto, 2000). All ofthese techniques are designed to capture hierarchical structures of POS tagsets. For instance, in theposition-wise grouping, optimal levels of POS hierarchies are changed according to the contexts. Besthierarchies for each context are selected by handcrafted rules or automatic error-driven procedures.

romanceparticle

The romance on the sea they bet is …

 

MEMMs select




 

rough waves

particle

los e



one’s heart

not



heart

A heart which beats rough waves is …

Figure 3: Errors with MEMMs(Correct paths are marked with bold boxes.)

Table 5: Number of errors in KC dataset# of l-errors# of s-errors
CRFs
79 (40%)120 (60%)HMMs
306 (44%)387 (56%)
MEMMs
416 (70%)
183 (30%)l-error: output longer token than correct one
s-error: output shorter token than correct one

this table. l-error (or s-error) means that a system
incorrectly outputs a longer (or shorter) token thanthe correct token respectively. By length bias, long
tokens are preferred to short tokens. Thus, larger
number of l-errors implies that the result is highly
influenced by the length bias.
While the relative rates of l-error and s-error arealmost the same in HMMs and CRFs, the numberof l-errors with MEMMs amounts to 416, which
is 70% of total errors, and is even larger than thatof naive HMMs (306). This result supports ourclaim that MEMMs is not sufficient to be applied toJapanese morphological analysis where the lengthbias is inevitable.

CRFs can realize such extensions naturally andstraightforwardly. In CRFs, position-wise grouping
and word-POS smoothing are simply integrated into
a design of feature functions. Parameters λk foreach feature are automatically configured by general maximum likelihood estimation. As shown in
Table 2, we can employ a number of templates tocapture POS hierarchies. Furthermore, some overlapping features (e.g., forms and types of conjugation) can be used, which was not possible in the extended HMMs.
4.3.3 L1-CRFs and L2-CRFs
L2-CRFs perform slightly better than L1-CRFs,
which indicates that most of given features(i.e., overlapping features, POS hierarchies, suffixes/prefixes and character types) are relevant toboth of two datasets. The numbers of active (nonzero) features used in L1-CRFs are much smaller(about 1/8 - 1/6) than those in L2-CRFs: (L2CRFs: 791,798 (KC) / 580,032 (RWCP) v.s., L1CRFs: 90,163 (KC) / 101,757 (RWCP)). L1-CRFs
are worth being examined if there are some practical constraints (e.g., limits of memory, disk or CPU
resources).

5Conclusions and Future WorkIn this paper, we present how conditional random
fields can be applied to Japanese morphologicalanalysis in which word boundary ambiguity exists.
By virtue of CRFs, 1) a number of correlated features for hierarchical tagsets can be incorporated
which was not possible in HMMs, and 2) influencesof label and length bias are minimized which caused
errors in MEMMs. We compare results between
CRFs, MEMMs and HMMs in two Japanese annotated corpora, and CRFs outperform the other approaches. Although we discuss Japanese morphological analysis, the proposed approach can be applicable to other non-segmented languages such as
Chinese or Thai.
There exist some phenomena which cannot be analyzed only with bi-gram features in Japanese morphological analysis. To improve accuracy, tri-gramor more general n-gram features would be useful.
CRFs have capability of handling such features.
However, the numbers of features and nodes in thelattice increase exponentially as longer contexts arecaptured. To deal with longer contexts, we need apractical feature selection which effectively trades
between accuracy and efficiency. For this challenge,
McCallum proposes an interesting research avenue
to explore (McCallum, 2003).

Acknowledgments
We would like to thank Kiyotaka Uchimoto and
Masayuki Asahara, who explained the details of
their Japanese morphological analyzers.

References
Masayuki Asahara and Yuji Matsumoto. 2000. Extended models and tools for high-performancepart-of-speech tagger. In Proc of COLING, pages
21–27.
Richard H. Byrd, Peihuang Lu, Jorge Nocedal, andCi You Zhu. 1995. A limited memory algorithm
for bound constrained optimization. SIAM Journal on Scientific Computing, 16(6):1190–1208.
Stanley F. Chen and Ronald. Rosenfeld. 1999. A
gaussian prior for smoothing maximum entropy
models. Technical report, Carnegie Mellon University.
Joshua Goodman. 2004. Exponential priors
for maximum entropy models. In Proc. of
HLT/NAACL.
John Lafferty, Andrew McCallum, and Fernando
Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML, pages 282–289.

Dong C. Liu and Jorge Nocedal. 1989. On thelimited memory BFGS method for large scale
optimization. Math. Programming, 45(3, (Ser.
B)):503–528.
Andrew McCallum and Wei Li. 2003. Early results for named entity recognition with conditional random fields, feature induction and webenhanced lexicons. In In Proc. of CoNLL.
Andrew McCallum, Dayne Freitag, and Fernando
Pereira. 2000. Maximum entropy markov models for information and segmentation. In Proc. of
ICML, pages 591–598.
Andrew McCallum. 2003. Efficiently inducing features of conditional random fields. In Nineteenth
Conference on Uncertainty in Artificial Intelligence (UAI03).
Fuchun Peng and Andrew McCallum. 2004. Accurate information extraction from research papers.
In Proc. of HLT/NAACL.
Fuchun Peng, Fangfang Feng, and Andrew McCallum. 2004. Chinese segmentation and new word
detection using conditional random fields (to appear). In Proc. of COLING.
Simon Perkins, Kevin Lacker, and James Thiler.
2003. Grafting: Fast, incremental feature selection by gradient descent in function space. JMLR,
3:1333–1356.
Della Pietra, Stephen, Vincent J. Della Pietra, andJohn D. Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393.
David Pinto, Andrew McCallum, Xing Wei, and
W. Bruce Croft. 2003. Table extraction using
conditional random fields. In In Proc. of SIGIR,
pages 235–242.
Fei Sha and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of
HLT-NAACL, pages 213–220.
Kiyotaka Uchimoto, Satoshi Sekine, and Hitoshi
Isahara. 2001. The unknown word problem: amorphological analysis of Japanese using maximum entropy aided by a dictionary. In Proc. of
EMNLP, pages 91–99.
Kiyotaka Uchimoto, Chikashi Nobata, Atsushi
Yamada, Satoshi Sekine, and Hitoshi Isahara.
2002. Morphological analysis of the spontaneous
speech corpus. In Proc of COLING, pages 1298–
1302.
Kiyotaka Uchimoto, Chikashi Nobata, Atsushi Yamada, and Hitoshi Isahara Satoshi Sekine. 2003.
Morphological analysis of a large spontaneous
speech corpus in Japanese. In Proc. of ACL,
pages 479–488.