<PAPER>
	<ABSTRACT>
		<S sid ="1" ssid = "1">Given the lack of word delimiters in written Japanese, word segmentation is generally consid­ ered a crucial first step in processing Japanese texts.</S>
		<S sid ="2" ssid = "2">Typical Japanese segmentation algorithms rely ei­ ther on a lexicon and grammar or on pre-segmented data.</S>
		<S sid ="3" ssid = "3">In contrast, we introduce a novel statistical method utilizing unsegmentd training data, with performance on kanji sequences comparable to and sometimes surpassing that of morphological analyz­ ers over a variety of error metrics.</S>
	</ABSTRACT>
	<SECTION title="Introduction" number = "1">
			<S sid ="4" ssid = "4">Because Japanese is written without delimiters be­ tween words, 1 accurate word segmentation to re­ cover the lexical items is a key step in Japanese text processing.</S>
			<S sid ="5" ssid = "5">Proposed applications of segmentation technology include extracting new technical terms, indexing documents for information retrieval, and correcting optical character recognition (OCR) er­ rors (Wu and Tseng, 1993; Nagao and Mori, 1994; Nagata, 1996a; Nagata, 1996b; Sproat et al., 1996; Fung, 1998).</S>
			<S sid ="6" ssid = "6">Typically, Japanese word segmentation is per­ formed by morphological analysis based on lexical and grammatical knowledge.</S>
			<S sid ="7" ssid = "7">This analysis is aided by the fact that there are three types of Japanese characters, kanji, hiragana, and katakana: changes in character type often indicate word boundaries, al­ though using this heuristic alone achieves less than 60% accuracy (Nagata, 1997).</S>
			<S sid ="8" ssid = "8">Character sequences consisting solely of kanji pose a challenge to morphologically-based seg­ menters for several reasons.</S>
			<S sid ="9" ssid = "9">First and most importantly, kanji sequences often contain domain terms and proper nouns: Fung (1998) notes that5085% of the terms in various technical dictio 1The analogous situation in English would be if words were written without spaces between them.</S>
			<S sid ="10" ssid = "10">Figure 1: Statistics from 1993 Japanese newswire (NIKKEI), 79,326,406 characters total.</S>
			<S sid ="11" ssid = "11">naries are composed at least partly of kanji.</S>
			<S sid ="12" ssid = "12">Such words tend to be missing from general-purpose lexicons, causing an unknown word problem for morphological analyzers; yet, these terms are quite important for information retrieval, information extraction, and text summarization, making correct segmentation of these terms critical.</S>
			<S sid ="13" ssid = "13">Second, kanji sequences often consist of compound nouns, so grammatical constraints are not applicable.</S>
			<S sid ="14" ssid = "14">For instance, the sequence shachohjkenjgyoh-mujbu­ choh (presidentjandjbusinessjgeneral manager = &quot;a president as well as a general manager of business&quot;) could be incorrectly segmented as: sha­ chohjkengyohjmujbu-choh (presidentjsubsidiary business!Tsutomu [a name]jgeneral manager); since both alternatives are four-noun sequences, they cannot be distinguished by part-of-speech information alone.</S>
			<S sid ="15" ssid = "15">Finally, heuristics based on changes in character type obviously do not apply to kanji-only sequences.</S>
			<S sid ="16" ssid = "16">Although kanji sequences are difficult to seg­ ment, they can comprise a significant portion of Japanese text, as shown in Figure 1.</S>
			<S sid ="17" ssid = "17">Since se­ quences of more than 3 kanji generally consist of more than one word, at least 21.2% of 1993 Nikkei newswire consists of kanji sequences requiring seg­ mentation.</S>
			<S sid ="18" ssid = "18">Thus, accuracy on kanji sequences is an important aspect of the total segmentation process.</S>
			<S sid ="19" ssid = "19">As an alternative to lexica-grammatical and su­pervised approaches, we propose a simple, effi cient segmentation method which learns mostly from very large amounts of unsegmented training data, thus avoiding the costs of building a lexicon or grammar or hand-segmenting large amounts of training data.</S>
			<S sid ="20" ssid = "20">Some key advantages of this method are: • No Japanese-specific rules are employed, en­ hancing portability to other languages.</S>
			<S sid ="21" ssid = "21">• A very small number of pre-segmented train­ ing examples (as few as 5 in our experiments) are needed for good performance, as long as large amounts of unsegmented data are avail­ able.</S>
			<S sid ="22" ssid = "22">• For long kanji strings, the method produces re­ sults rivalling those produced by Juman 3.61 (Kurohashi and Nagao, 1998) and Chasen 1.0 (Matsumoto et al., 1997), two morphological analyzers in widespread use.</S>
			<S sid ="23" ssid = "23">For instance, we achieve 5% higher word precision and 6% bet­ ter morpheme recall.</S>
			<S sid ="24" ssid = "24">Figure 2: Collecting evidence for a word boundary - are the non-straddling n-grams 8 1 and 82 more frequent than the straddling n-grams t 1, t2, and t3?</S>
			<S sid ="25" ssid = "25">Let I&gt; (y, z) be an indicator function that is 1 when y &gt; z, and 0 otherwise.2 In order to compensate for the fact that there are more n-gram questions than (n -1)-gram questions, we calculate the fraction of affirmative answers separately for each n in N: 2 n-1</S>
	</SECTION>
	<SECTION title="Algorithm. " number = "2">
			<S sid ="26" ssid = "1">Our algorithm employs counts of character n-grams Vn(k) = 2(n 1 L L I&gt;(#(8f), #(tj)) i=l j=l in an unsegmented corpus to make segmentation de­ cisions.</S>
			<S sid ="27" ssid = "2">We illustrate its use with an example (see Then, we average the contributions of each n-gram order: Figure 2).</S>
			<S sid ="28" ssid = "3">Let &quot;A B C D W X Y Z&quot; represent an eight-kanji · VN(k) = 1 INI L Vn(k) nEN sequence.</S>
			<S sid ="29" ssid = "4">To decide whether there should be a word boundary between D and W, we check whether n­ grams that are adjacent to the proposed boundary, such as the 4-grams s1 =&quot;A B C D&quot; and 82 =&quot;W X Y Z&quot;, tend to be more frequent than n-grams that straddle it, such as the 4-gram t 1 =&quot;BCD W&quot;.</S>
			<S sid ="30" ssid = "5">If so, we have evidence of a word boundary between D and W, since there seems to be relatively little cohesion between the characters on opposite sides of this gap.</S>
			<S sid ="31" ssid = "6">The n-gram orders used as evidence in the seg­ mentation decision are specified by the set N. For instance, if N = {4} in our example, then we pose the six questions of the form, &quot;Is #(8i) &gt; #(tj)?&quot;, where #(x) denotes the number of occurrences of x in the (unsegmented) training corpus.</S>
			<S sid ="32" ssid = "7">If N = {2,4}, then two more questions (Is &quot;#(CD) &gt; #(D W)?&quot; and &quot;Is #(W X) &gt; #(D W)?&quot;) are added.</S>
			<S sid ="33" ssid = "8">More formally, let 8 and 8 be the non­ straddling n-grams just to the left and right of lo­ cation k, respectively, and let tj be the straddling n-gram with j characters to the right of location k. After vN (k) is computed for every location, bound­ aries are placed at all locations f such that either: • VN(f) &gt; VN(f- 1) and VN(£) &gt; VN(f. + 1) (that is, R. is a local maximum), or • vN (R.)t, a threshold parameter.</S>
			<S sid ="34" ssid = "9">The second condition is necessary to allow for single-character words (see Figure 3).</S>
			<S sid ="35" ssid = "10">Note that it also controls the granularity of the segmentation: low thresholds encourage shorter segments.</S>
			<S sid ="36" ssid = "11">Both the count acquisition and the testing phase are efficient.</S>
			<S sid ="37" ssid = "12">Computing n-gram statistics for all possible values of n simultaneously can be done in 0(m log m) time using suffix arrays, where m is the training corpus size (Manber and Myers, 1993; Nagao and Mori, 1994).</S>
			<S sid ="38" ssid = "13">However, if the set N of n gram orders is known in advance, conceptually simpler algorithms suffice.</S>
			<S sid ="39" ssid = "14">Memory allocation for 2Note that we do not take into account the magnitude of the difference between the two frequencies; see section 5 for discussion.</S>
			<S sid ="40" ssid = "15">v,./k) A BI C DI W XI Y1 Z the word level, a stem and its affixe s are brack eted toget her as a single unit.</S>
			<S sid ="41" ssid = "16">At the morp heme level, stems are divid ed from their affixe s. For exam ple, altho ugh both naga no (Naga no) and shi (city) can appea r as indivi dual words , nagano shi (Nag ano city) is brack eted as [[naga no][s hi]], since here shi Figure 3: Determining word boundaries.</S>
			<S sid ="42" ssid = "17">The X- Y boundary is created by the threshold criterion, the other three by the local maximum condition.</S>
			<S sid ="43" ssid = "18">count tables can be significantly reduced by omit­ ting n-grams occurring only once and assuming the count of unseen n-grams to be one.</S>
			<S sid ="44" ssid = "19">In the applica­ tion phase, the algorithm is clearly linear in the test corpus size if INI is treated as a constant.</S>
			<S sid ="45" ssid = "20">Finally, we note that some pre-segmented data is necessary in order to set the parameters N and t. However, as described below, very little such data was required to get good performance; we therefore deem our algorithm to be &quot;mostly unsupervised&quot;.</S>
	</SECTION>
	<SECTION title="Experimental Framework. " number = "3">
			<S sid ="46" ssid = "1">Our experimental data was drawn from 150 megabytes of 1993 Nikkei newswire (see Figure I).</S>
			<S sid ="47" ssid = "2">Five 500-sequence held-out subsets were ob­ tained from this corpus, the rest of the data serv­ ing as the unsegmented corpus from which to derive character n-gram counts.</S>
			<S sid ="48" ssid = "3">Each held-out subset was hand-segmented and then split into a 50-sequence parameter-training set and a 450-sequence test set.</S>
			<S sid ="49" ssid = "4">Finally, any sequences occurring in both a test set and its corresponding parameter-training set were discarded from the parameter-training set, so that these sets were disjoint.</S>
			<S sid ="50" ssid = "5">(Typically no more than five sequences were removed.)</S>
			<S sid ="51" ssid = "6">3.1 Held-out set annotation.</S>
			<S sid ="52" ssid = "7">Each held-out set contained 500 randomly-extracted kanji sequences at least ten characters long (about twelve on average), lengthy sequences being the most difficult to segment (Takeda and Fujisaki, 1987).</S>
			<S sid ="53" ssid = "8">To obtain the gold-standard annotations, we segmented the sequences by hand, using an observa­ tion of Takeda and Fujisaki (1987) that many kanji compound words consist of two-character stem words together with one-character prefixes and suf­ fixes.</S>
			<S sid ="54" ssid = "9">Using this terminology, our two-level bracket­ serves as a suffix.</S>
			<S sid ="55" ssid = "10">Loosely speaking, word-level bracketing demarcates discourse entities, whereas morpheme-level brackets enclose strings that cannot be further segmented without loss of meaning.4 For instance, if one segments naga-no in naga-no-shi into naga (long) and no (field), the intended mean­ ing disappears.</S>
			<S sid ="56" ssid = "11">Here is an example sequence from our datasets: [&apos;J&apos; f&apos;.X:J [mli&apos;JJ [[iiibJ [J J [ J Three native Japanese speakers participated in the annotation: one segmented all the held-out data based on the above rules, and the other two reviewed 350 sequences in total.</S>
			<S sid ="57" ssid = "12">The percentage of agree­ ment with the first person&apos;s bracketing was 98.42%: only 62 out of 3927 locations were contested by a verifier.</S>
			<S sid ="58" ssid = "13">Interestingly, all disagreement was at the morpheme level.</S>
			<S sid ="59" ssid = "14">3.2 Baseline algorithms.</S>
			<S sid ="60" ssid = "15">We evaluated our segmentation method by com­ paring its performance against Chasen 1.05 (Mat­ sumoto et al., 1997) and Juman 3.61,6 (Kurohashi and Nagao, 1998), two state-of-the-art, publically­ available, user-extensible morphological analyzers.</S>
			<S sid ="61" ssid = "16">In both cases, the grammars were used as distributed without modification.</S>
			<S sid ="62" ssid = "17">The sizes of Chasen&apos;s and Ju­ man&apos;s default lexicons are approximately 115,000 and 231,000 words, respectively.</S>
			<S sid ="63" ssid = "18">Comparison issues An important question that arose in designing our experiments was how to en­ able morphological analyzers to make use of the parameter-training data, since they do not have pa­ rameters to tune.</S>
			<S sid ="64" ssid = "19">The only significant way that they can be updated is by changing their grammars or lexicons, which is quite tedious (for instance, we had to add part-of-speech information· to new en­ tries by hand).</S>
			<S sid ="65" ssid = "20">We took what we felt to be a rea­ sonable, but not too time-consuming, course of cre­ ating new lexical entries for all the bracketed words in the parameter-training data.</S>
			<S sid ="66" ssid = "21">Evidence that this ing annotation may be summarized as follows.3 At 4This level of segmentation is consistent with Wu&apos;s (1998) 3A complete description of the annotation policy, including the treatment of numeric expressions, may be found in a tech­ nical report (Ando and Lee, 1999).</S>
			<S sid ="67" ssid = "22">Monotonicity Principle for segmentation.</S>
			<S sid ="68" ssid = "23">5http://cactus.aistnara.ac.jp/lab/nltlchasen.html 6http://pine.kuee.kyoto-u.ac.jp/nl-resource/juman-e.html Word accuracy 90 CHASEN JUMAN opllnizt oplnuo recall opiJTozt F Figure 4: Word accuracy.</S>
			<S sid ="69" ssid = "24">The three rightmost groups represent our algorithm with parameters tuned for different optimization criteria.</S>
			<S sid ="70" ssid = "25">was appropriate comes from the fact that these ad­ ditions never degraded test set performance, and in­ deed improved it by one percent in some cases (only small improvements are to be expected because the parameter-training sets were fairly small).</S>
			<S sid ="71" ssid = "26">It is important to note that in the end, we are com­ paring algorithms with access to different sources of knowledge.</S>
			<S sid ="72" ssid = "27">Juman and Chasen use lexicons and grammars developed by human experts.</S>
			<S sid ="73" ssid = "28">Our al­ gorithm, not having access to such pre-compiled knowledge bases, must of necessity draw on other information sources (in this case, a very large un­ segmented corpus and a few pre-segmented exam­ ples) to compensate for this lack.</S>
			<S sid ="74" ssid = "29">Since we are in­ terested in whether using simple statistics can match the performance of labor-intensive methods, we do not view these information sources as conveying an unfair advantage, especially since the annotated training sets were small, available to the morpho­ logical analyzers, and disjoint from the test sets.</S>
	</SECTION>
	<SECTION title="Results. " number = "4">
			<S sid ="75" ssid = "1">We report the average results over the five test sets using the optimal parameter settings for the corre­ sponding training sets (we tried all nonempty sub­ sets of {2, 3, 4, 5, 6} for the set of n-gram orders N and all values in {.05, .1, .15, ...</S>
			<S sid ="76" ssid = "2">, 1} for the thresh­ old t)7.</S>
			<S sid ="77" ssid = "3">In all performance graphs, the &quot;error bars&quot; represent one standard deviation.</S>
			<S sid ="78" ssid = "4">The results for Chasen and Juman reflect the lexicon additions de 7 For simplicity, ties were deterministically broken by pre­ ferring smaller sizes of N, shorter n-grams in N, and larger threshold values, in that order.</S>
			<S sid ="79" ssid = "5">scribed in section 3.2.</S>
			<S sid ="80" ssid = "6">Word and morpheme accuracy The standard metrics in word segmentation are word precision and recall.</S>
			<S sid ="81" ssid = "7">Treating a proposed segmentation as a non-nested bracketing (e.g., &quot;IABICI&quot; corresponds to the bracketing &quot;[AB][C]&quot;), word precision (P) is defined as the percentage of proposed brackets that exactly match word-level brackets in the annotation; word recall (R) is the percentage of word-level an­ notation brackets that are proposed by the algorithm in question; and word F combines precision and re­ call: F = 2PR/(P + R)..</S>
			<S sid ="82" ssid = "8">One problem with using word metrics is that morphological analyzers are designed to produce morpheme-level segments.</S>
			<S sid ="83" ssid = "9">To compensate, we al­ tered the segmentations produced by Juman and Chasen by concatenating stems and affixes, as iden­ tified by the part-of-speech information the analyz­ ers provided.</S>
			<S sid ="84" ssid = "10">(We also measured morpheme accu­ racy, as described below.)</S>
			<S sid ="85" ssid = "11">Figures 4 and 8 show word accuracy for Chasen, Juman, and our algorithm for parameter settings optimizing word precision, recall, and F-measure rates.</S>
			<S sid ="86" ssid = "12">Our algorithm achieves 5.27% higher preci­ sion and 0.26% better F-measure accuracy than Ju­ man, and does even better (8.8% and 4.22%, respec­ tively) with respect to Chasen.</S>
			<S sid ="87" ssid = "13">The recall perfor­ mance falls (barely) between that of Juman and that of Chasen.</S>
			<S sid ="88" ssid = "14">As noted above, Juman and Chasen were de­ signed to produce morpheme-level segmentations.</S>
			<S sid ="89" ssid = "15">We therefore also measured morpheme precision, recall, and F measure, all defined analogously to their word counterparts.</S>
			<S sid ="90" ssid = "16">Figure 5 shows our morpheme accuracy results.</S>
			<S sid ="91" ssid = "17">We see that our algorithm can achieve better recall (by 6.51%) and F-measure (by 1.38%) than Juman, and does better than Chasen by an even wider mar­ gin (11.18% and 5.39%, respectively).</S>
			<S sid ="92" ssid = "18">Precision was generally worse than the morphological analyz­ ers.</S>
			<S sid ="93" ssid = "19">Compatible Brackets Although word-level accu­ racy is a standard performance metric, it is clearly very sensitive to the test annotation.</S>
			<S sid ="94" ssid = "20">Morpheme ac­ curacy suffers the same problem.</S>
			<S sid ="95" ssid = "21">Indeed, the au­ thors of Juman and Chasen may well have con­ structed their standard dictionaries using different notions of word and morpheme than the definitions we used in annotating the data.</S>
			<S sid ="96" ssid = "22">We therefore devel­ oped two new, more robust metrics to measure the number of proposed brackets that would be incor [[data][base]][system](annotation brackets) Pr op os ed se g m en tat io n w o r d e rr o r s m o r p h e m e e r r o r s c o m p a t i b l e b r a c k e t e r r o r s cr os sin g m o r p h e m e d i v i d i n g [ d a t a ] [ b a s e ] [ s y s t e m ] [ d a t a ] [ b a s e s y s t e m ] [ d a t a b a s e ] [ s y s ] [ t e r n ] 2 2 2 0 1 3 0 1 0 0 0 2 Figure 6: Examples of word, morpheme, and compatible-bracket errors.</S>
			<S sid ="97" ssid = "23">The sequence &quot;data base&quot; has been annotated as &quot;[[data][base]]&quot; because &quot;data base&quot; and &quot;database&quot; are interchangeable.</S>
			<S sid ="98" ssid = "24">BS , I M o r p h e m e a c c u r a c y CHASEN JUMAN opJrrlze rocal oplmlzo F p r e d l i o n Fi g ur e 5: M or p h e m e ac c ur ac y. segme ntatio ns can be count ed as correc t. W e also use the all comp atibl e brac kets rate, whic h is the fracti on of seque nces for whic h all the prop osed brack ets are comp atible . Intuit ively, this funct ion meas ures the ease with whic h a huma n could corre ct the outpu t of the segm entati on algo­ rithm : if the all comp atible brack ets rate is high, then the error s are conc entrat ed in relati vely few seque nces; if it is low, then a huma n doing post­ proce ssing woul d have to corre ct many sequ ences . Fi gure 7 depic ts the comp atible brack ets and all­ comp atible brack ets rates.</S>
			<S sid ="99" ssid = "25">Our algor ithm does bet­ ter on both metri cs (for insta nce, when F meas ure is opti mize d, by 2.16 % and 1.9% , respe ctivel y, in rect with respect to any reasonable annotation.</S>
			<S sid ="100" ssid = "26">Our novel metrics account for two types of er­ rors.</S>
			<S sid ="101" ssid = "27">The first, a crossing bracket, is a proposed bracket that overlaps but is not contained within an annotation bracket (Grishman et al., 1992).</S>
			<S sid ="102" ssid = "28">Cross­ ing brackets cannot coexist with annotation brack­ ets, and it is unlikely that another human would create such brackets.</S>
			<S sid ="103" ssid = "29">The second type of er­ ror, a morpheme-dividing bracket, subdivides a morpheme-level annotation bracket; by definition, such a bracket results in a loss of meaning.</S>
			<S sid ="104" ssid = "30">See Fig­ ure 6 for some examples.</S>
			<S sid ="105" ssid = "31">We define a compatible bracket as a proposed bracket that is neither crossing nor morpheme­ dividing.</S>
			<S sid ="106" ssid = "32">The compatible brackets rate is simply the compatible brackets precision.</S>
			<S sid ="107" ssid = "33">Note that this met­ ric accounts for different levels of segmentation si­ multaneously, which is beneficial because the gran­ ularity of Chasen and Juman&apos;s segmentation varies from morpheme level to compound word level (by our definition).</S>
			<S sid ="108" ssid = "34">For instance, well-known university names are treated as single segments by virtue of be­ ing in the default lexicon, whereas other university names are divided into the name and the word &quot;uni­ versity&quot;.</S>
			<S sid ="109" ssid = "35">Using the compatible brackets rate, both comparison to Chasen, and by 3.15% and 4.96%, respectively, in comparison to Juman), regardless of training optimization function (word precision, re­ call, or F -we cannot directly optimize the com­ patible brackets rate because &quot;perfect&quot; performance is possible simply by making the entire sequence a single segment).</S>
			<S sid ="110" ssid = "36">Compatible and all-compatible bracket.s rates CHASEN JUIAAH cpWnizo Pf&quot;&quot;&quot;&quot;&quot; O!)lllnllt riCIII CJI&apos;IINZ!</S>
			<S sid ="111" ssid = "37">F l!!</S>
			<S sid ="112" ssid = "38">conpaliblebroclr!!Urtlos _brad&lt;JIUIIU Figure 7: Compatible brackets and all-compatible bracket rates when word accuracy is optimized.</S>
			<S sid ="113" ssid = "39">Juman5 vs. Juman50 Our50 vs Juman50 Our5 vs. Juman5 Our5 vs. Juman50 precision recall F-measure -1.040.630.84 +5.274.39 +0.26 +6.183.73 +1.14 +5.144.36 +0.30 Figure 8: Relative word accuracy as a function of training set size.</S>
			<S sid ="114" ssid = "40">&quot;5&quot; and &quot;50&quot; denote training set size before discarding overlaps with the test sets.</S>
			<S sid ="115" ssid = "41">4.1 Discussion.</S>
			<S sid ="116" ssid = "42">Minimal human effort is needed.</S>
			<S sid ="117" ssid = "43">In contrast to our mostly-unsupervised method, morphological analyzers need a lexicon and grammar rules built using human expertise.</S>
			<S sid ="118" ssid = "44">The workload in creating dictionaries on the order of hundreds of thousands of words (the size of Chasen&apos;s and Juman&apos;s de­ fault lexicons) is clearly much larger than annotat­ ing the small parameter-training sets for our algo­ rithm.</S>
			<S sid ="119" ssid = "45">We also avoid the need to segment a large amount of parameter-training data because our al­ gorithm draws almost all its information from an unsegmented corpus.</S>
			<S sid ="120" ssid = "46">Indeed, the only human effort involved in our algorithm is pre-segmenting the five 50-sequence parameter training sets, which took only 42 minutes.</S>
			<S sid ="121" ssid = "47">In contrast, previously proposed supervised approaches have used segmented train­ ing sets ranging from 10005000 sentences (Kash­ ioka et al., 1998) to 190,000 sentences (Nagata, l996a).</S>
			<S sid ="122" ssid = "48">To test how much annotated training data is actu­ ally necessary, we experimented with using minis­ cule parameter-training sets: five sets of only five strings each (from which any sequences repeated in the test data were discarded).</S>
			<S sid ="123" ssid = "49">It took only 4 minutes to perform the hand segmentation in this case.</S>
			<S sid ="124" ssid = "50">As shown in Figure 8, relative word performance was not degraded and sometimes even slightly better.</S>
			<S sid ="125" ssid = "51">In fact, from the last column of Figure 8 we see that even if our algorithm has access to only five anno­ tated sequences when Juman has access to ten times as many, we still achieve better precision and better F measure.</S>
			<S sid ="126" ssid = "52">Both the local maximum and threshold condi­ tions contribute.</S>
			<S sid ="127" ssid = "53">In our algorithm, a location k is deemed a word boundary if vN (k) is either (1) a local maximum or (2) at least as big as the thresh­ old t. It is natural to ask whether we really need two conditions, or whether just one would suffice.</S>
			<S sid ="128" ssid = "54">We therefore studied whether optimal perfor­ mance could be achieved using only one of the con­ ditions.</S>
			<S sid ="129" ssid = "55">Figure 9 shows that in fact both contribute to producing good segmentations.</S>
			<S sid ="130" ssid = "56">Indeed, in some cases, both are needed to achieve the best perfor­ mance; also, each condition when used in isolation yields suboptimal performance with respect to some performance metrics.</S>
			<S sid ="131" ssid = "57">a c c ur a c y o p ti m i z e p r e c i s i o n o p t i m i z e r e c a l l o p ti m iz eF m ea su re w or d M M &amp; T M m or p h e m e M &amp; T T T Figure 9: Entries indicate whether best performance is achieved using the local maximum condition (M), the threshold condition (T), or both.</S>
	</SECTION>
	<SECTION title="Related Work. " number = "5">
			<S sid ="132" ssid = "1">Japanese Many previously proposed segmenta­ tion methods for Japanese text make use of either a pre existing lexicon (Yamron et al., 1993; Mat­ sumoto and Nagao, 1994; Takeuchi and Matsumoto, 1995; Nagata, 1997; Fuchi and Takagi, 1998) or pre-segmented training data (Nagata, 1994; Papa georgiou, 1994; Nagata, 1996a; Kashioka et al., 1998; Mori and Nagao, 1998).</S>
			<S sid ="133" ssid = "2">Other approaches bootstrap from an initial segmentation provided by a baseline algorithm such as Juman (Matsukawa et al., 1993; Yamamoto, 1996).</S>
			<S sid ="134" ssid = "3">Unsupervised, non-lexicon-based methods for Japanese segmentation do exist, but they often have limited applicability.</S>
			<S sid ="135" ssid = "4">Both Tomokiyo and Ries (1997) and Teller and Batchelder (1994) explicitly avoid working with kanji charactes.</S>
			<S sid ="136" ssid = "5">Takeda and Fujisaki (1987) propose the short unit model, a type of Hidden Markov Model with linguistically­ determined topology, to segment kanji compound words.</S>
			<S sid ="137" ssid = "6">However, their method does not handle three-character stem words or single-character stem words with affixes, both of which often occur in proper nouns.</S>
			<S sid ="138" ssid = "7">In our five test datasets, we found that 13.56% of the kanji sequences contain words that cannot be handled by the short unit model.Nagao and Mori (1994) propose using the heuris tic that high-frequency character n-grams may rep­ resent (portions of) new collocations and terms, but the results are not experimentally evaluated, nor is a general segmentation algorithm proposed.</S>
			<S sid ="139" ssid = "8">The work of Ito and Kohda (1995) similarly relies on high-frequency character n-grams, but again, is more concerned with using these frequent n-grams as pseudo-lexicon entries; a standard segmentation algorithm is then used on the basis of the induced lexicon.</S>
			<S sid ="140" ssid = "9">Our algorithm, on the hand, is fundamen­ tally different in that it incorporates no explicit no­ tion of word, but only &quot;sees&quot; locations between characters.</S>
			<S sid ="141" ssid = "10">Chinese According to Sproat et al.</S>
			<S sid ="142" ssid = "11">(1996), most prior work in Chinese segmentation has exploited lexical knowledge bases; indeed, the authors assert that they were aware of only one previously pub­ lished instance (the mutual-information method of Sproat and Shih (1990)) of a purely statistical ap­ proach.</S>
			<S sid ="143" ssid = "12">In a later paper, Palmer (1997) presents a transformation-based algorithm, which requires pre-segmented training data.</S>
			<S sid ="144" ssid = "13">To our knowledge, the Chinese segmenter most similar to ours is that of Sun et al.</S>
			<S sid ="145" ssid = "14">(1998).</S>
			<S sid ="146" ssid = "15">They also avoid using a lexicon, determining whether a given location constitutes a word boundary in part by deciding whether the two characters on either side tend to occur together; also, they use thresholds and several types of local minima and maxima to make segmentation decisions.</S>
			<S sid ="147" ssid = "16">However, the statis­ tics they use (mutual information and t-score) are more complex than the simple n-gram counts that we employ.</S>
			<S sid ="148" ssid = "17">Our preliminary reimplementation of their method shows that it does not perform as well as the morphological analyzers on our datasets, al­ though we do not want to draw definite conclusions because some aspects of Sun et al&apos;s method seem incomparable to ours.</S>
			<S sid ="149" ssid = "18">We do note, however, that their method incorporates numerical differences between statistics, whereas we only use indicator functions; for example, once we know that one trigram is more common than another, we do not take into account the difference between the two frequencies.</S>
			<S sid ="150" ssid = "19">We conjecture that using absolute differences may have an adverse effect on rare sequences.</S>
	</SECTION>
	<SECTION title="Conclusion. " number = "6">
			<S sid ="151" ssid = "1">In this paper, we have presented a simple, mostly­unsupervised algorithm that segments Japanese se quences into words based on statistics drawn from a large unsegmented corpus.</S>
			<S sid ="152" ssid = "2">We evaluated per­ formance on kanji with respect to several metrics, including the novel compatible brackets and all­ compatible brackets rates, and found that our al­ gorithm could yield performances rivaling that of lexicon-based morphological analyzers.</S>
			<S sid ="153" ssid = "3">In future work, we plan to experiment on Japanese sentences with mixtures of character types, possibly in combination with morphologi­ cal analyzers in order to balance the strengths and weaknesses of the two types of methods.</S>
			<S sid ="154" ssid = "4">Since our method does not use any Japanese-dependent heuristics, we also hope to test it on Chinese or other languages as well.</S>
	</SECTION>
	<SECTION title="Acknowledgments">
			<S sid ="155" ssid = "5">We thank Minoru Shindoh and Takashi Ando for reviewing the annotations, and the anonymous re­ viewers for their comments.</S>
			<S sid ="156" ssid = "6">This material was sup­ ported in part by a grant from the GE Foundation.</S>
	</SECTION>
</PAPER>
