Proceedings of the Third NTCIR Workshop

Waterloo at NTCIR-3:
Using Self-supervised Word Segmentation
Xiangji Huang Fuchun Peng Dale Schuurmans Nick Cercone
School of Computer Science, University of Waterloo
Waterloo, Ontario, Canada, N2L 3G1{jhuang, f3peng, dale, ncercone}@cs.uwaterloo.ca

Abstract
In this paper, we describe the system we use
in the NTCIR-3 CLIR (cross language IR)task. We participate the SLIR (single language IR) track. In our system, we use
a self-supervised word-segmentation techniquefor Chinese information retrieval, which combines the advantages of traditional dictionary based approaches with character based
approaches, while overcoming many of theirshortcomings. This method is completely language independent and unsupervised, which
provides a promising avenue for constructing
accurate multi-lingual or cross-lingual information retrieval systems that are ﬂexible andadaptive.

1

Introduction

In this paper, we propose an EM-based
method for Chinese information retrieval
which has many of the advantages of boththe character based approach and the dictionary based approach, while overcoming manyof the shortcomings of both methods. We
call our approach self-supervised segmentation. In self-supervised segmentation, no predeﬁned lexicon is required. Instead, all thatis needed is a large unsegmented training
corpus—which is almost always easy to obtain. We automatically learn a lexicon andlexical distribution from the training corpus
by using the EM algorithm [10], and thensegment the collections using the Viterbi algorithm [24]. Unlike previous EM word segmentation methods [11], where one lexicon
is learnt, we learn two lexicons (for reasons© 2003 National Institute of Informatics

outlined below). Since our segmentation approach is completely unsupervised and language independent, it can be easily adapted
to other languages.
The rest of the paper is organized as follows. Section 2 ﬁrst introduces the selfsupervised word segmentation algorithm, andSection 3 then brieﬂy describes the weighting
methods we use in the experiments. Section 4then presents the experiments we have conducted on the NTCIR data set. Conclusions
are given in Section 5.

2

Self-supervised Segmentation

In a general word segmentation task where
there are no identifying markers between
words, one could eﬀectively exploit known
words to guide the segmentation of unknown
words. For example, if the word “computer ”
is already known then upon seeing the text
“computerscience” it is natural to segment“science” as a possible new word. To exploit this observation, we develop an EM
based word discovery method that is a variant of standard EM training, but avoids getting trapped in local maxima by keeping two
lexicons: a core lexicon which contains words
that are judged to be trustworthy, and a candidate lexicon which contains all other candidate words that are not in the core lexicon.
Assume we have a sequence of characters
C = c1 c2 ...cT that we wish to segment into
chunks S = s1 s2 ...sM , where T is the numberof characters in the sequence and M is thenumber of words in the segmentation. Herechunks si will be chosen from the core lex-

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

icon V1 = {si , i = 1, ..., |V1 |} or the candidate lexicon V2 = {sj , j = 1, ..., |V2 |}. If
we already have the probability distributions
θ = {θi |θi = p(si ), i = 1, ..., |V1 |} deﬁned overthe core lexicon and φ = {φj |φj = p(sj ), j =1, ..., |V2 |} over the candidate lexicon, thenwe can recover the most likely segmentationof the sequence C = c1 c2 ...cT into chunks
S = s1 s2 ...sM as follows. First, for any given
segmentation S of C, we can calculate thejoint likelihood of S and C byprob(S, C|θ, φ) =M1Mp(si ) 2 p(sj )
i=1

2

j=1

2

M

=

1 
p(sk )
2M
k=1

where M1 is the number of chunks occurring in the core lexicon, M2 is the numberof chunks occurring in the candidate lexicon, and sk can come from either lexicon.
(Note that each chunk sk must come from exactly one of the core or candidate lexicons.)
Our task is to ﬁnd the segmentation S ∗ that
achieves the maximum likelihood:S ∗ = argmax{prob(S, C|θ, φ)}S(1)Given a probability distribution deﬁned by θand φ over the lexicon, the Viterbi algorithm
can be used to eﬃciently compute the best
segmentation S of character string C. Estimation of the probabilities can be done by the
EM algorithm. The parameter re-estimation
formulas are as follows.

k
k
k+1
S #(si , S) × prob(S, C|θ , φ )
= 
θi
k
k
si
S #(si , S) × prob(S, C|θ , φ )
(2)


k
k
S #(sj , S) × prob(S, C|θ , φ )


=
φk+1
j
k
k
sj
S #(sj , S) × prob(S, C|θ , φ )(3)where #(si , S) is the number of times si occurring the segmentation S.
The two lexicons are constructed automatically as follows. Let us deﬁne C1 , C2 as thetraining corpus and the validation corpus respectively, and let V1 and V 2 be the core candidate lexicons respectively. Initially, V1 is set
to be empty and V2 is initialized to containall candidate “words” that are generated fromthe training corpus by enumerating contiguous character strings of lengths 1 to L for somepredeﬁned maximum length L. In a ﬁrst pass,starting from the uniform distribution, EM is
used to increase the likelihood of the training corpus C1 . When the training process
stabilizes, the M words with highest probability are selected from V2 and moved to V1 ,after which all the probabilities are rescaled
so that V1 and V2 each contain half the total probability mass. EM is then run again.
The rationale for shifting half of the probability mass to V1 is that this increases theinﬂuence of core words in determining segmentations and allows them to act as more
eﬀective guides in processing the training sequence. We call this procedure of successively
moving the top M words to V1 forward selection. Forward selection is repeated until
the segmentation performance of Viterbi on
the validation corpus C2 leads to a decreasein F-measure (which means we must have included some erroneous words in the core lexicon). After forward selection terminates, M
is decremented and we carry out a process of
backward deletion, where the M words withthe lowest probability in V1 are moved back to
V2 , and EM training is successively repeateduntil F-measure again decreases on the validation corpus C2 (which means we must havedeleted some correct core words). The twoprocedures of forward selection and backward
deletion are alternated, decrementing M ateach alternation, until M ≤ 0;

3

Probabilistic Term Weighting

In an attempt to ensure that the phenomena we observe are not speciﬁc to a particular
retrieval technique, we experimented with aparameterized term weighting scheme whichallowed us to control the quality of retrieval
performance. We considered a reﬁned term
weighting scheme based on the the standard
term weighting function
w0 = log

N − n + 0.5
n + 0.5(4)where N is the number of indexed documents in the collection, and n is the numberof documents containing a speciﬁc term [26].

Proceedings of the Third NTCIR Workshop

Many researchers have shown that augmenting this basic function to take into accountdocument length, as well as within-document
and within-query frequencies, can be highly
beneﬁcial in English text retrieval [2]. For example, one standard augmentation is to use
w1 = w0 ∗where(c1 + 1) ∗ tf (c2 + 1 ) ∗ qtf∗
K + tfc2 + qtf

(5)



dl
K = c1 ∗ 1 − c3 + c3
avdl

Here tf is within-document term frequency,
qtf is within-query term frequency, dl is thelength of the document, avdl is the average
document length, and c1 , c2 , c3 are tuning
constants that depend on the database, thenature of the queries, and are empirically determined. However, to truly achieve stateof-the-art retrieval performance, and also toallow for the quality of retrieval to be manipulated, we further augmented this standard
term weighting scheme with an extra correction term

to control the inﬂuence of correction factor,
and hence control the retrieval quality. By
setting kd to diﬀerent values, we have diﬀerent
term weighting methods in our experiments.
In our experiments, we tested kd set to valuesof 0, 6, 8, 10, 15, 20, 50.

4Experiments and Analyses

4.1

Experiment setup and data sets

The document collection used in NTCIR03 include CIRB011 and CIRB020. CIRB011 documents come from Central Daily News, China
Daily News Chinatimes Commercial, Chinatimes Express and China Times. The statistics of CIRB011 are listed in Table 1.
News Agency
Chinatimes
Chinatimes Commercial
Chinatimes Express
Central Daily News
China Daily News
Total

# of Document
38,16325,812
5,747
27,77034,728132,173

Per.
28.8%
19.5%
4.4%
21.0%
26.3%
200MB

Table 1: statistics of CIRB011

w2 = w1 ⊕ kd ∗ y(6)This correction allows us to more accurately
CIRB020 are news articles published byaccount for the length of the document. Here
United Daily News (udn.com) from 1998-01⊕ indicates that the component is added only
01 to 1999-12-31. CIRB020 contains 249,508
once per document, rather than for each term,news articles in total. In total, the NTCIR
andChinese collection consists of 381,681 docu
1dlln( avdl ) + ln(c4 )if dl ≤ rel avdl ments and 50 topics encoded using BIG5

coding scheme and marked with XML. The
minimum, maximum and average documenty=avdl
dl−rel avdl
) + ln(c4 ) 1 − c5 ∗avdl−relln( relavdl

avdl sizes are 0, 29,540 and 1,223 bytes. Each topic

if dl > rel avdl has several ﬁelds: T (Topic) ﬁeld, D (Desc)ﬁled, N (Narr) ﬁled and C (Conc) ﬁeld. Keywhere rel avdl is the average relevant docuwords can be extracted from the combination
ment length calculated from previous queriesof these ﬁelds.
based on the same collection of documents.
The NTCIR relevance judgments for each
Overall, this term weighting formula has ﬁve
topic came from the human assessors The reltuning constants, c1 to c5 , which are all set
evance judgments will be done in four grades,from previous research on English text rehighly relevant, relevant, partially relevant
trieval and some initial experiments on Chiand irrelevant. Several measures are used tonese text retrieval. In our experiments, theevaluate the retrieval result which is an orvalues of the ﬁve arbitrary constants c1 , c2 ,dered set of retrieved documents. The meac3 , c4 and c5 were set to 2.0, 5.0, 0.75, 3 andsures include Average Precision: average pre26 respectively.
cision over all 11 recall points (0.0, 0.1, 0.2,...,The key constant is the quantity k , whichdis the new tuning constant that we manipulate

1

Actually, there are only 42 valid topics

The Third NTCIR Workshop, Sep.2001 - Oct. 20021.0); R-Precision: precision after the numberof documents retrieved is equal to the number of known relevant documents for a query;and Precision at # docs: precision after #documents have been retrieved. Detailed descriptions of these measures can be found in[28].
Our segmenter is trained on the training
set C1 with validation set C2 (see section 2),
where C1 is 90M data which contains one
year of People’s Daily news service stories(www.snweb.com) and corpus C2 used here
is a randomly selected 2000 sentence subsetof the Chinese Treebank from LDCwhich ishas been segmented by hand. Our segmentation accuracy is around 70-74% on the Chinese Treebank.

4.2

Avg. Pre.
R-Pre.
PreAt10PreAt100
PreAt1000

Avg. Pre.
R-Pre.
PreAt10PreAt100
PreAt1000
Table 2:
TDNC-01

Experimental Results

WATERLOO-C-C-TDNC-01

In this run, the query keywords are extracted
from the combination of ﬁelds title (T), desc
(D), narr (N) and conc (C). In Table 2, weshow the results of this run and also include
the overall statistics of NTCIR3: maximum
value (Max.), minimum value (Min.) and average value (Avg.).
In summary, the average precision is a little
below the average, and P-Precision and thePrecisions at a speciﬁc number are above theaverages.
4.2.2

WATERLOO-C-C-D-03

In this run, the query key words are extracted
from the desc (D) ﬁeld. The evaluation results
are given in Table 3. The overall statistics are
not available.

WATERLOO

0.22510.24990.31900.1526
0.0335
WATERLOO

0.27630.32620.43810.22480.0541Results of WATERLOO-C-C-

Rigid Evaluation
Avg. Pre. 0.1764
R-Pre.
0.2118PreAt100.2976
PreAt1000.1198PreAt1000 0.0257
Relax Evaluation
Avg. Pre. 0.2138
R-Pre.
0.2631
PreAt100.3952
PreAt100
0.1800
PreAt1000 0.0423

We submitted 4 runs: WATERLOO-C-CTDNC-01 (Run 1), WATERLOO-C-C-C-02(Run 2), WATERLOO-C-C-D-03 (Run 3) and
WATERLOO-C-C-C-04 (Run 4). However,
due to some reason, our WATERLOO-C-CC-02 did not have evaluation results, so weare not discussing it here. The name formatof the runs follows the NTCIR3 dry run submission instruction.
4.2.1

Rigid Evaluation
Max.
Min.
Avg.
0.3435 0.0347 0.2263
0.3463 0.0327 0.2493
0.4405 0.0405 0.3130
0.2017 0.0162 0.1452
0.0408 0.0050 0.0317
Relax Evaluation
Max.
Min.
Avg.
0.4165 0.0443 0.2806
0.4330 0.0526 0.3134
0.5833 0.0619 0.4298
0.2867 0.0293 0.2142
0.0660 0.0093 0.0513

Table 3: Results of WATERLOO-C-C-C-03

4.2.3

WATERLOO-C-C-C-04

In this run, the query keywords are extracted
only from conc (C) ﬁeld. The evaluation results are given in Table 4. The overall statistics are not available.
4.2.4

Comparison

Figures 1 and 2 show the comparison resultsin terms of Precision at 10, 100 and 1,000 for
the Run 1, 2 and 3 with respect to the Relax and Rigid evaluations respectively. Eachﬁgure contains three groups. In each group,
the ﬁrst and second bars represent the resultsfrom Run 1 and Run 2. The third bar repre-

Proceedings of the Third NTCIR Workshop

Rigid Evaluation
Avg. Pre. 0.1831
R-Pre.
0.2057
PreAt100.2595
PreAt1000.1295
PreAt1000 0.0325
Relax Evaluation
Avg. Pre. 0.2406
R-Pre.
0.2727
PreAt100.3786
PreAt100
0.1967
PreAt1000 0.0530

TDNC

D

C

0.35
0.3

Precision (%)

0.25
0.2
0.15
0.1
0.05
0
Precision at 10

Precision at 100

Precision at 1000

Table 4: Results of WATERLOO-C-C-C-04

Figure 2: Precision at 10, 100 and 1000 for
Rigid Evaluation

sents the results from Run 3.

ters. The maximum word length could be set
arbitrarily to suit the application. In fact, ourbest results are achieved when L = 3. Second, the statistics we used were optimized byan iterative EM process, which is guaranteedto achieve at least a local optimum. This approach should be more reliable than the statistics direct from the corpus. Our further experiments on TREC data sets shows our EM
approach outperforms the mutual information
based approach under the same experimental environment setting (results are not shownhere).
Using EM for word segmentation has many
advantages, and has in fact been consideredin previous research [11, 22]. However, due tothe low segmentation accuracies these methods obtain, they still do not tend to be regarded as good methods for Chinese IR. However, we have shown that the accuracies obtained by EM word segmentation is enoughto achieve good results in Chinese IR systems[20].
However, our overall results are onlyaround the average. It is much worse thanthe best results where query expansion andinteractive retrieval methods are used. In our
retrieval system, we did not use any query expansion and our keywords extraction is simple and completely automatically. Because
our previous experiments [21] show that EM
based word segmentation can achieve comparable results to other segmentation methods,
we conjecture the the reason why our perfor-

TDNC

D

C

0.5
0.45

Precision (%)

0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0
Precision at 10

Precision at 100

Precision at 1000

Figure 1: Precision at 10, 100 and 1000 for
Relax Evaluation

4.3

Discussion

Our work is most related to the work of Chen[7]. There too it was proposed that Chinese
IR could be conducted without using a dictionary. In their method, one ﬁrst collects occurrence frequencies for uni-grams and bi-gramsfrom the corpus, and then uses a mutual information based criterion to segment Chinese
text [27]. To use mutual information, they
limit the word length to at most 2 characters.
Similarly, we also use the frequencies from thecorpus and also use mutual information during the process. However, our work diﬀers
from theirs in many respects [20, 21]. First
we do not limit the word length to 2 charac-

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

mance is not good here is due to the query
processing.
Figure 3 compares TDNC, C and D runs
in terms of average precision and R-precision
with respect to Relax evaluation. Figure 4
compares TDNC, C and D runs in terms of average precision and R-precision with respect
to Rigid evaluation. We can observe that theresults from the TDNC run are better than
the results from the C run or the D rune only.
This means the information provided by T (Topic ) and N (Narr) ﬁelds can provide positive contribution to retrieval performance.

TDNC

D

C

0.35
0.3

Precision (%)

0.25
0.2
0.15
0.1
0.05
0
Average Precision

R-Precision

Figure 3: Average Precision and R-Precision
for Relax Evaluation

TDNC

D

C

5

Conclusions
work

and

FutureWe have proposed a novel EM based method
for segmenting Chinese words for the purposes of Chinese information retrieval, andpresented experimental results on recent NTCIR data. Our method has the advantagesof both the character based and dictionary
based methods, while overcoming many of
their shortcomings. However, our overall results on the NTCIR data set are not good.
We are analyzing our experimental results.
We have experimented with a single word
weighting strategy, and are currently investigating alternative strategies involving wordpair weighting, which can greatly increase theperformance [7, 14, 16]. Building a Chinese IR
system encompasses many research problems,
and the performance of such systems can beinﬂuenced by several factors. As the overall NTCIR3 results show, keyword extraction
also plays an important role in IR systems.
Our current keyword extraction method isvery rough, and we are investigating more sophisticated extraction methods such as thoseused in [7, 8].

6

Acknowledgements

This Research is supported by Mathematics
of Information Technology and Complex Systems, and Bell University Labs.

0.3

References

Precision (%)

0.25
0.2

[1] R. Ando and L. Lee.
MostlyUnsupervised Statistical Segmentation ofJapanese: Application to Kanji. In Proceedings ANLP-NAACL, 2000.

0.15
0.1
0.05
0

Figure 4: Average Precision and R-Precision
for Rigid Evaluation[2] M. Beaulieu, M. Gatford, X. Huang,
S. Robertson,
S. Walker,
andP. Williams. Okapi at TREC-5. In
D.K.Harman (ed):Proceedings of
TREC-5, pages 143–166, 1997.

Another thing worth pointing out is that
our results are far worse than those we got on
the TREC data sets [21]. Further investigation needs to be conducted.

[3] M. Brent and X. Tao. Chinese Text Segmentation With MBDP-1: Making theMost of Training Corpora. In Proceedings of ACL2001, France, 2001.

Average Precision

R-PrecisionProceedings of the Third NTCIR Workshop[4] C. Buckley, A. Singhal, and M. Mitra. Using Query Zoning and Correlation
within SMART: TREC-5. In Proceedingsof TREC-5, pages 105–118, 1997.

22th Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval. ACM,
1999.

[5] C. Buckley, J. Walz, M. Mitra, and
C. Cardie. Using Clustering and SuperConcepts Within SMART: TREC-6. In
Proceedings of TREC-6, pages 107–124,
1998.

[13] X. Huang and S. Roberton.
Okapi
Chinese Text Retrieval Experiments at
TREC-6. In Proceedings of TREC-6,
pages 137–142, 1998.

[6] J.-S. Chang and K.-Y. Su. An Unsupervised Iterative Method for Chinese New
Lexicon Extraction. International Journal of Computational Linguistics & Chinese Language Processing, 1997.
[7] A. Chen, J. He, L. Xu, F. C. Gey, and
J. Meggs. Chinese Text Retrieval Without Using a Dictionary. In Proceedings ofthe 20th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages
42–49. ACM, 1997.
[8] L.-F. Chien, T.-I. Huang, and M.-C.
Chien. Pat-tree-based Keyword Extraction for Chinese Information Retrieval.
In Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in Information
Retrieval, pages 50–58. ACM, 1997.
[9] D. Dahan and M. Brent. On the Discovery of Novel Word-like Units from Utterances: An Artiﬁcial-language Study with
Implications for Native-language Acquisition. Journal of Experimental Psychology: General, 128:165–185, 1999.
[10] A. Dempster, N. Laird, and D. Rubin. Maximum-likelihood from Incomplete Data via the EM algorithm. J.
Royal Statist. Soc. Ser., B(39), 1977.
[11] X. Ge, W. Pratt, and P. Smyth. Discovering Chinese Words from Unsegmented
Text. In Proceedings of the 22th Annual
International ACM SIGIR Conference
on Research and Development in Information Retrieval, pages 271–272, 1999.
[12] T. Hofmann. Probabilistic Latent Semantic Indexing. In Proceedings of the[14] X. Huang and S. Roberton. A Probabilistic Approach to Chinese Information
Retrieval: Theory and Experiments. In
Proceedings of the BCS-IRSG 2000: the22nd Annual Colloquium on Information
Retrieval Research, Cambridge, England,
2000.
[15] W. Jin. Chinese Segmentation and its
Disambiguation. In MCCS-92-227, Computing Research Laboratory, New Mexico State University, Las Cruces, New
Mexico, 1992.
[16] K. L. Kwok. Comparing Representations in Chinese Information Retrieval.
In Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in Information
Retrieval, pages 34–41. ACM, 1997.
[17] C. Manning and H. Schütze. Foundations of Statistical Natural Language
Processing. MIT Press, Cambridge, Massachusetts, 1999.
[18] J. Nie and F. Ren. Chinese information
retrieval: using characters or words? Information Processing and Management,
35:443–462, 1999.
[19] J. Nie, X. Ren, and M. Brisebois. On
Chinese text retrieval. In Proceedings ofthe 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages
225–233. ACM, 1996.
[20] F. Peng, X. Huang, D. Schuurmans, andN. Cercone. Investigating the Relationship of Word Segmentation Performanceand Retrieval Performance in Chinese

The Third NTCIR Workshop, Sep.2001 - Oct. 2002

IR. In Proceedings of the 19th International Conference on Computational Linguistics (COLING2002), Taipei, Taiwan,
2002.
[21] F. Peng, X. Huang, D. Schuurmans,
N. Cercone, and S. Robertson. Using Self-supervised Word Segmentationin Chinese Information Retrieval. In
Proceedings of 25th Annual International
ACM SIGIR Conference on Researchand Development in Information Retrieval (SIGIR2002), Tampere, Finland,
2002. ACM.
[22] F. Peng and D. Schuurmans.
Selfsupervised Chinese Word Segmentation.
In F. Hoﬀman et al. (Eds.): Advancesin Intelligent Data Analysis, Proceedingsof the Fourth International Conference(IDA-01), LNCS 2189, pages 238–247,
Cascais, Portugal, 2001. Springer-Verlag
Berlin Heidelberg.
[23] J. Ponte and W. Croft. Useg: A Retargetable Word Segmentation Procedure
for Information Retrieval. In Symposium
on Document Analysis and Information
Retrival 96 (SDAIR), 1996.
[24] L. Rabiner.
A Tutorial on Hidden
Markov Models and Selected Applications in Speech Recognition. Proceedingsof IEEE, 77(2), 1989.
[25] S. E. Robertson and S. Walker. Some
Simple Eﬀective Approximations to
the 2-Poisson Model for Probabilistic
Weighted Retrieval. In Proceedings of the
17th Annual International ACM-SIGIR
Conference on Research and Development in Information Retrieval, pages
232–241, 1994.
[26] K. Sparck-Jones.
Search Relevance
Weighting Given Little Relevance Information. Journal of Documentation,35(1), 1979.
[27] R. Sproat and C. Shih. A statisticalmethod for ﬁnding word boundaries inchinese text. Computer Proceedings ofChinese and Oriental Languages, 4:336–
351, 1990.

[28] E. Voorhees and D. Harman. Overview
of the Sixth Text REtrieval Conference(TREC-6). In Proceedings of the sixth
Text REtrieval Conference (TREC-6).
NIST Special Publication, 1998.
[29] R. Wilkinson. Chinese Document Retrieval at TREC-6. In Proceedings of
TREC-6, 1998.