A Stochastic Morphological Analysis for Japaneseemploying Character n-Gram and k-NN Method
Kenji Nagamatsu

andHidehiko Tanaka

University of Tokyo, Faculty of Engineering
Kougaku-bu 13-goukan, University of Tokyo,
Hongo 7-3-1, Bunkyo-ku, Tokyo, Japan, 113

1

Introduction

Because Japanese corpora have been developed recently, it has become possible to perform stochastic morphological analysis for Japanese(Nagata,
1994; Takeuchi and Matsumoto, 1995; Mori andNagao, 1996; Yamamoto et al., 1997). Although
the same Hidden Markov Model-based approachas English can be fundamentally applicable withword/part-of-speech n-gram data, some problems
peculiar to Japanese make the approach indirect. Before calculating the most likely part-ofspeech(abbreviated to 'pos') sequence, it is required to segment input sentences into morphemesreferring to word dictionaries.
On the other hand, there are a few researches on stochastic morphological analysis ofJapanese WITHOUT word dictionaries (Papageorgiou, 1994; Yamamoto and Masuyama, 1997;
Kageura, 1997). However, they require much computational power because they employ charactern-gram data in the HMM-based method.
This paper proposes a new method of stochastic
morphological analysis for Japanese texts which
utilizes character n-gram data(thus, no need
for word dictionaries) and a k-Nearest Neighbormethod. Because the k -NN method is fundamental in memory-based reasoning and it does not require so much computational power as the HMM
method, this new method is fast and achieves highaccuracy in word segmentation and pos tagging.
First, section 2 describes the details of stochastic morphological analysis of Japanese texts andclari es the problems in these researches. Next,
section 3 describes our new k-NN based method
and it is evaluated in section 4. Section 5 discusses
the e ectiveness and the problems of our method.
Finally, after mentioning the future works in section 6, section 7 concludes this paper.

2
2.1

Related Researches

A Stochastic Approach with n-Gram
Data and Hidden Markov Model

In English many researches on pos tagging havebeen performed with statistical data, such as ngram, extracted from corpora(DeRose, 1988; Cutting et al., 1992; Merialdo, 1994; Dermatas andKokkinakis, 1995). Now the accuracy of stochastic pos tagging has achieved 95% or higher.
The method of the pos tagging with HMM canbe considered as the minimization process in thefollowing production of probabilities. Then themost likely combination of pos tags, which has theminimum probability in the equation, is attachedto the words in the input sentence.
Pr(W; T ) =Y

0n+1 ; : : : ; ti01 ) Pr(wi jti ) (1)Pr(ti jti

W is a word sequence of an input sentence and
T is a pos tag sequence corresponding to W .

Although this process is eciently performed
with forward DP backward A3 search algorithm(Nagata, 1994), the computational complexity of the process is proportional to the number ofcandidates for each tag pattern to the power n.
With pos n-gram data this complexity is almost
insigni cant because the number of possible tag
patterns is small and the length of the word(pos)sequence is also small(2030 in English).
Another problem arises when no probability
data exists for a given word(pos) pattern. This
problem originates in the sparseness of corpora
and the probability for the unknown patternmust be estimated from other probabilities(Katz,
1987; Brown et al., 1992; Dagan and Pereira,
1994; McMahon and Smith, 1996). The back-omethod(Katz, 1987) interpolates the value using
the probabilities of more general patterns. It will
be showed that this interpolation is automaticallyintegrated into our method.

2.2

Japanese-peculiar Problems
in the HMM Approach

Japanese is an agglutinative language and all morphemes in sentences adhere to each other. Thus,
pos tagging for Japanese texts requires a preliminary processing which segments sentences intomorphemes by referring to word dictionaries.
Because every position between characters canbe a boundary of morphemes, the word segmentation of Japanese texts cannot be performed
uniquely and produces many variations of segmented sequences. This results in the decline oftagging accuracy and the ineciency in speed.
After segmenting sentences the same HMMbased method as English is applicable to
Japanese(Nagata, 1994; Takeuchi and Matsumoto, 1995; Mori and Nagao, 1996; Yamamoto
et al., 1997). These researches have achieved morethan 90% in the tagging precision. The precisionof (Yamamoto et al., 1997) is reported to be morethan 97% but because it has no unknown wordmodel, this research cannot be directly applied tosentences containing unknown words.
This fact clari es the importance of an unknown
word model. In English the existence of unknown
words does not interfere with other words. In
Japanese, however, because all morphemes adhereto each other, the existence of unknown words
may lead to the uncertainty in segmentation anddirectly to the decline of the maximum likelihood
probability in the equation (1). With unknown
word models more precise tagging will be achieved
because in English there are some cases that prexes or suxes of unknown words show their pos
tags. It is true in the case of Japanese because of
the existence of Kanji and Katakana words1 .
2.3

A Stochastic Approach with
Character n-Gram Data

On the other hand, there are a few researchon stochastic morphological analysis of Japanese
WITHOUT dictionaries(Papageorgiou, 1994; Yamamoto and Masuyama, 1997; Kageura, 1997).
Because of employing character n-gram data these
do not require to segment sentences in advance.
(Yamamoto and Masuyama, 1997) tackled onthese problems by employing extended charactern-gram data2 in the HMM-based method.
1 In Japanese, foreign words are spelled with special
characters(Katakana) and we call them Katakana words.

2 'Extended character' contains the character, the pos

This method achieved 95.91% in segmenting
precision and 94.13% in tagging precision. To
process 1000 sentences, however, it took about
670sec(UltraSPARC 140MHz) because the computational complexity of the HMM-based method
is proportional to the number of possible extended
characters for one character to the power n.
3
3.1

A Stochastic Approachwith k -NN Methodk -NN Method in Fundamentals

Although the Nearest Neighbor method is basically a searching method for the similar examples, it can be also utilized as a classi cation
method(Dasarathy, 1991).
Given both an example database and a similarity metric sim(ei; ej ) over examples, the k -NN
method decides the class of an input data by majority from the classes of the k nearest examples.
This method is simple enough to be implemented easily and has been reported to be effectively superior to other methods(such as decision tree, neural network, etc.) in some benchmarks(Michie et al., 1994). (Zavrel and Daelemans, 1997) also reports that the weighted k-NN
method is comparable to or better than the backo method in PP attachment and POS tagging.
3.2

Extended Character n-Gram Data

Before providing a detailed description of the proposed method, it is required to introduce our
n-gram data format. This format is based on
character n-gram and extended for the k-NN
method(called extended character n-gram data).
A raw n-gram data is formulated as a triplet
hCi ; Bj ; Ti i. Ci is a list of characters in an ngram and i ranges from 1 to n. Bj is a list ofbooleans which tells whether a position j in the
n-gram is a boundary of morphemes or not (0 for
false, 1 for true) and the index j ranges from 0 ton, where a position j denotes the position betweena character Cj and a character Cj 01 . Ti denotes
the pos tag of the word containing a character Ci .
After extracting all raw data from some corpus,
two probabilities for Bj and Ti are calculated withthe data which share a same surface string Ci .
Extended character n-gram data is de ned by thisBt
new triplet hCi ; pB
j ; pi i, where pj is probability
tag of the word containing this character and the information whether the word terminates at the right position ofthis character.

+ÍõüÑÜÍ8¹OU U U P

Probability of breaking in each position
p0 = 0.964912
B
p1 = 1.0B
p2 = 0.1358…

Bü Ñ  ÜPY Ñ  ÅP…

Sentencesin a corpus

p1

Noun

C2

= 0.964912

Conjunctio n

p1

C1= 0.035087

Noun= 0.526316

Verb= 0.45614

p2
p2
p2

Adjective= 0.0175439

Probability that Ci has a POS tag t

Figure 1: Extended Character n-Gram (in thecase of 2-gram)that a position j is a boundary of morphemes andpti is probability that t is the pos tag of the word
which contains a character Ci (see Figure 1).
3.3

Applying k-NN Method

to Japanese Morphological Analysis

Without a priori knowledge about Kanjis withsimilar meaning or collocations, it is acceptablethat the more characters are shared between two
strings, the more similar are these. Thus, the simplest similarity metric is employed in this paper.
nsim(e1 ; e2 ) =wi (ei1 ; ei2 )(2)i=1, where  (ei1 ; ei2 ) is 1 when ei1 = ei2 ; otherwise 0.
ei1 is the i-th character in an extended n-gram e1 .
There are many candidates(window patterns)
when searching near examples around some position in an input sentence(see Figure 2). Some patterns, however, are useless because they contain\*" between the position and meaningful characters. By ignoring these useless patterns, you have
only to consider those patterns in Figure 3. Oneof the known problems in the k-NN method is thatthe number of examples compared with an input
data becomes too large. With this pruning thenumber of the possible window patterns becomesequal to (n + 1)(n + 2)=2 for pB
i or n(n + 1)=2
for pti , which is actually equal to the number ofreference to dictionaries and it is insigni cant.
With these pruned window patterns and thesimilarity metric(equation (2)), the procedure of
the morphological analysis employing the k-NN
method is summarized as follows, where p^Bi denotes the probability of boundary at a position iin an input sentence and p^ti denotes the probabil-

X

a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12

õüÑ
üÑ
ÑÜ
ÜÍ
£üÑ
õ£Ñ
õü£
££Ñ
£ü£
õ££
£Ü
Ñ£Ü

U
U
U

+ÍõüÑÜÍ8¹OU U U P
b1
b2
b3
b4
b5
b6
b7
b8
b9
b10
b11
b12

üÑ
ÑÜ
ÜÍ
£Ñ
ü£
üÑ£
££
£Ñ£
ü££
£Ü
Ñ£Ü

U
U
U

a27
a28

£Ü£
££

b20
b21

£Ü£
££

Figure 2: Possible Window Patterns. The left isa gure for calculating pB
i and the right is one forpti . \*" means `don't care' and grayed patterns
are useless for calculating similarity.

+ÍõüÑÜÍ8¹OU U U P
a1
a2
a3
a4
a5
a6
a7
a8
a9

õüÑ
üÑ
ÑÜ
ÜÍ
üÑ
Ñ
Ü
Ñ


+ÍõüÑÜÍ8¹OU U U P
b1
b2
b3
b4
b5
b6

üÑ
ÑÜ
ÜÍ
Ñ
Ü


Figure 3: Pruned Window Patterns
ity that a character Ci in an input sentence has a
pos tag t.
1. Search all extended n-gram data from thedatabase which matches with substrings
around the position i of the input sentence.
2. Calculate similarity values between every ngram and an input sentence with the equation(2) and choose the most similar n-gram eo .
B
3. (Estimate of p^Bi ) Assign the value pj of eoBto p^i , where j corresponds to the position i.
4. (Estimate of p^ti ) Assign the list of valuesptj (t = N oun; V erb; :::) to p^ti .
5. Loop step 1. through step 4. until all pBi andpti in the input sentence are determined.
6. (Segmentation)If the value p^B
i is more than0.5, consider the position i as a boundary ofmorphemes and segment the input sentence.
7. (POS tagging) To each segmented morpheme, assign the pos tag t with the maximum p^ti in the morpheme.

4.1

Extraction of Extended n-Gram Data

In these experiments we utilized the EDR corpus(Electronic Dictionary Research Institute Ltd.,
1995), which contains 207,802 Japanese sentences
which are already segmented into morphemes andtagged. The number of pos tags employed in this
corpus is 15.
To perform both open-data evaluation andclose-data evaluation, we selected 1000 sentencesfrom the corpus and call the set \test data set".
The data set containing the remaining 206,802
sentences is called \training data set" and the data
set containing all sentences(207,802) of the EDR
corpus is called \all data set".
From both the all data set and the training dataset, extended n-gram data have been extracted
for n = 1; 2; 3; 4. The statistics of the data are
showed in Table 1. The n-gram data extracted
from the all data set is employed in the close-data
evaluation and the other n-gram data is employedin the open-data evaluation.
Table 1 shows that the data size of 3-gram and4-gram is very large. It is also known that thesize of example databases is one of the problems
in the k-NN method. This problem does no harmin the accuracy of pos tagging but may a ect theprocessing time. This is also mentioned later insection 4.4 and discussed in section 5.
4.2

Experiment 1: Word Segmentation

With the extracted n-gram data we evaluated theaccuracy of segmenting sentences into morphemesby the proposed method. Thus, this experimentevaluates the accuracy of p^Bi obtained in step 3.
The procedure of the experiment is as follows.
1. Store all the extended n-gram data whose n
is equal to or less than N into the database.
2. Choose one sentence from the test data set
and segment it with our method.

¶´«°³¢

Accuracy Rate¶´«¯´¢¶³«´¶¢¶³«¯­¢¶²«´±¢
95%¶²«¯®¢¶±«´­¢¶±«°µ¢¶²«®µ¢¶±«²µ¢¶°«µ¶¢¶°«±´¢¶¯«´¯¢

recall

en

en

en

op
2

1

=

N

=

op

e

en

op
3
N

N

=

op

e
N

4

os

´°«±­¢

=

os

cl
1

=

os

cl
2

cl
3

=

N

N

N

=

os
cl

e

e

)

)

xt

xt

(e

(e
3

4

an

=

m

N

en

1

en

´°«±¯¢

en
ju

en

op
2

1

=

=
N

as
ch

N

3

op

e

en

e

=

op

op
N

4

os
cl
=

os
cl

1
N

N

=

os
2

os
3

=
N

N

=

cl

e

e

)

)

xt

xt

cl

(e

(e
3

4

an

=

m

´¶«­³¢´¶«­µ¢

90%

N

Experiments¶µ«´µ¢¶´«µ´¢

ju4¶¶«­°¢

1

Table 1: Summary of Extracted n-Gram Data
for All Data Set. (1):Total # of n-gram, (2):#of n-gram patterns, (3):Ave. freq. per pattern,(4):Data size.

Segmentation into Morphemes
100%

en

4-gram7,724,156
3,319,892
2.3266294M

asAll Data Set
2-gram3-gram
8,799,431
8,172,812
345,108
1,572,361
25.4985.1978
18.5M
111M

ch

(1)
(2)
(3)
(4)

1-gram
9,448,229
5710
1654.68
250K

precision

Figure 4: Accuracy in Word Segmentation
3. Compare the output and the answer in the
corpus.
4. With the number of the matched morphemes,
calculate the precision and the recall.
5. Loop step 3. through step 5. until all sentences in the test data set are processed.
6. Calculate the average precision rate and theaverage recall rate.
The result of this experiment is showed in Figure 4. For simplicity's sake the weight values inthe equation (2) are set to 1.0 in the experiments.
Section 5 discusses the problem of optimal weight.
In Figure 4 `chasen'(Matsumoto et al., 1997)and `juman'(Matsumoto et al., 1994) are traditional morphological analyzers based on connectivity rules and costs. Because `chasen' and `juman' employ their own morpheme system, it is
impossible to compare their output and the answers in the EDR corpus directly. `(ext)' meansthat the outputs of the analyzers were modi ed byhand and compared with the answers manually.
4.3

Experiment 2: POS Tagging

The experiment of pos tagging is also performedin the same way as the experiment of word segmentation. Figure 5 shows the result of this experiment.
4.4

Experiment 3: Processing Time

This evaluates the time to process 10000 sentencesin the EDR corpus. We measured the sum of theuser and the system time with the Unix `time'command. The employed workstation was SUN
SPARCserver 1000(SuperSPARC 85MHz). The
average times of 5 trials are showed in Figure 6.

Pos Tagging to Morphemes
100%¶µ«±¶¢¶µ«¯±¢

Accuracy Rate¶³«´­¢¶³«®¶¢

95%¶°«¯±¢¶°«¯¯¢¶¯«³­¢¶¯«±µ¢¶®«±²¢¶­«³²¢

en
op

en

en
op

1

op
N

=

2
N

=

e

en
3

op

=
N

=

4

cl

recallµ¶«²®¢ ³¯«²¶¢

N

e

os

e

os
cl
N

=

1

e

os
cl

2
=
N

en

os
cl

3

4

=
N

en

op
1
=

N

N

=

=

en

op
2

op

N

N

4

3

op

en

e

³¯«³°¢³´«°¶¢

=

e

os
cl
=
N

e

os
cl

1
=

=

2
N

e

os

os

cl

cl

3
=
N

N

4
=
N

¶­«²³¢³´«±±¢

90%

precision

Figure 5: Accuracy in POS Tagging
Processing Time

Processing Time(sec)

30

20

¯µ«µ
¯°«³
¯­«³

10

®´«³
®¯«­

0

chasen 1

N=4

N=3

N=2

N=1

Figure 6: Processing time of 10000 sentences
5

Discussion

First, Figure 4 shows that in the close-data evaluation the larger N becomes, the higher rises its
accuracy. It is almost true also in the open-data
evaluation except for the reversal between N = 3
and N = 4(described later). This fact is a wellknown characteristic of the k-NN method | themore examples are there in the database, the moreaccurate this method becomes.
The accuracy in the close-data evaluation ismuch higher than the accuracy in the open-data.
This means that if input sentences have similar
expressions to the stored examples, their analysis
results become almost correct. This fact is also theadvantage of the k-NN method. Because no intermediate calculation interferes, it can make themost of the stored examples, or the knowledge.
The best accuracy(95.18%) in the open-data
evaluation is achieved with N = 3. (Yamamoto
and Masuyama, 1997) achieved 95.91% under the
open-data evaluation with the same corpus. Thesemethods are comparable in word segmentation.
Next, Figure 5 shows the same tendency as Figure 4. The method with N = 3 achieved the best
precision(93.22%) in the open-data evaluation but
this is slightly lower than (Yamamoto and Masuyama, 1997). It is because the weight values inthe equation (2) are all set to 1.0 in the experiments. In the word segmentation task the output
labels of the k-NN method are only two and thein uence of the weight is small. In the pos tagging, however, the number of the output labels is
15 and it is assumed that the selection of the mostsimilar example was inadequate(see Section 6).
Finally, Figure 6 shows that our approach isvery fast. It is natural because the main parts ofthe method, the search of strings and the estimate
of probabilities are lightweight. Even the methodwith N = 3, which achieved the best result in theexperiments, is much faster than `chasen' | oneof the fastest Japanese morphological analyzers.
Compared with (Yamamoto and Masuyama,1997) employing the HMM-based method, ourmethod is much faster. While the paper reported
the processing time for 1000 sentences was 670sec
with UltraSPARC 140MHz, in our method with
N = 3 it took 2.06sec with SuperSPARC 85MHz.
As the size of the database becomes larger, thesearch of strings becomes slower. This decline of
speed is inevitable and known as one of the problems in the k -NN method. To answer this problem
some techniques such as pruning non-informative
examples have been proposed(see Section 6).
6

Future Works Pruning non-informative examples

The data extracted in section 4.1 containall the possible examples along with noninformative ones. These non-informative examples are harmful not only to the processing
speed but also to the accuracy in estimatingtp^B
i and p^i . The pruning of non-informative
examples is required(Aha et al., 1991).
 Acquisition of the optimal weight parameters

The weight parameters in the equation (2)were not fully utilized in this paper. (Zavrel and Daelemans, 1997) utilized the kNN method with the weight parameters calculated by the information gain and has
achieved relatively good result in PP attachment and POS tagging tasks.

7Conclusion

Slava M. Katz. 1987. Estimation of probabilities from

A stochastic approach based on HMM has someproblems when applied to Japanese morphological analysis. In order to answer the problems, thispaper proposed a new method of stochastic morphological analysis for Japanese texts employing
the k-NN method and character n-gram data.
This method was evaluated thoroughly and it
was showed that the method achieved high accuracy in word segmentation and pos tagging. Its accuracy is comparable to or better than other traditional morphological analyzers or other HMMbased stochastic methods. Moreover, it was also
showed that the processing time of this method
was much faster than the `chasen' which is one of
the fastest Japanese morphological analyzers.
From the experiments it is concluded that thestochastic approach employing character n-gramdata and the k -NN method is practically competent for Japanese morphological analysis.

sparse data for the language model component of aIEEE Transactions on Acoustics, Speech and Signal Processing, 35(3):400{401.

speech recognizer.

Yuji Matsumoto, Sadao Kurohashi, Takehito Utsuro,

JapaneseMorphological Analysis System JUMAN Manual.

Yutaka Taeki, and Makoto Nagao, 1994.
University of Kyoto.

Yuji Matsumoto, Akira Kitauchi, Tatsuo Yamashita,
Osamu Imaichi,

and Tomoaki Imamura,

1997.

Japanese Morphological Analysis System ChaSen
Manual. Nara Institute of Science and Technology.
NAIST Technical Report NAIST-IS-TR97007.
John G. McMahon and Francis J. Smith.

1996.

Improving statistical language model performancewith automatically generated word hierarchies.

Computational Linguistics, 22(2):217{247.

Bernard Merialdo. 1994. Tagging english text witha probabilistic model.

Computational Linguistics,

20(2):155{171.
D. Michie, D. Spiegelhalter, and C. Taylor.

1994.

Machine Learning, Neural and Statistical Classi cation. Prentice Hall.

Shinsuke Mori and Makoto Nagao. 1996. Japanesemorphological analysis by superposition of mor-

References

pheme bi-gram and part-of-speech bi-gram. In Nat-D. W. Aha, D. Kibler, and M. K. Albert.
Instance-basedlearning

Learning, 6:37{66.

1991.

Machinealgorithms.

Masaaki Nagata. 1994. A stochastic japanese mor-Peter F. Brown, Della Vincent J. Pietra, Peter V.
deSouza, Jenifer C. Lai, and Robert L. Mercer.
1992.

Class-based n-gram models of natural lan-

guage. Computational Linguistics, 18(4):467{479.

D. Cutting, J. Kupiec, J. Pedersen, and P. Sibun.
1992.

ural Language Processing SIG(Information Processing Society of Japan), pages 37{44. 112-6.

A practical part-of-speech tagger.

In Pro-phological analyzer using a forward-dp backwarda* n-best search algorithm. In Proceedings of COL-

ING, pages 201{207.

Constantine P. Papageorgiou. 1994. Japanese word
segmentation by hidden markov model. In Proceedings of the Human Language Technology Workshop,

ceedings of the Third Conference of Applied Natural
Language Processing, pages 133{143.

Kouichi Takeuchi and Yuji Matsumoto. 1995. Learn-

Ido Dagan and Fernando Pereira. 1994. Similarity-

ing parameters of japanese morphological analyzer

based estimation of word cooccurrence probabilities. In Proceedings of ACL-94.

B. V. Dasarathy. 1991. Nearest Neighbor(NN) Norms:

NN Pattern Classi cation Techniques. IEEE Computer Society Press.
1995.

Automatic stochastic tagging of natural language
texts. Computational Linguistics, 21(2):137{163.
1988.

based-on hidden markov model. In NLP Special
Interest Group(Information Processing Society ofJapan), pages 13{19. 108-3.
Mikio Yamamoto and Masakazu Masuyama.

1997.

(japanese morphological analysis employing theEvangelos Dermatas and George Kokkinakis.

S.J. DeRose.

pages 283{288.

Grammatical category disam-

biguation by statistical optimization.

tional Linguistics, 14(1):31{39.

Computa-chain probability of extended character with pos

and breaking information). In Proceedings of The

3rd Annual Meeting of The Association for Natural
Language Processing, pages 421{424, mar.

Kazuhide Yamamoto, Jun Kawai, Sumita Eiichiro,
and Osamu Furuse. 1997. Morphological analysis

Kyo Kageura. 1997. bigram (a method of segmenting

utilizing n-gram of mixed category. In Proceedingsof the 54th annual meeting of Information Processing Society of Japan, pages 2.51{2{52, March.

compound kanji strings based on character bigram).

Jakub Zavrel and Walter Daelemans. 1997. Memory-

Japan Electronic Dictionary Research Institute Ltd.
1995. Edr electronic dictionary technical guide.

In Proceedings of The 3rd Annual Meeting of The

Association for Natural Language Processing, pages
477{480, mar.

based learning: Using similarity for smoothing. In

Proceedings of ACL/EACL(To appear).