CUHK’S  link detection system  FOR the TDT2001 Evaluation

Wai Lam,    Chong-Ki Tsang,   Tak-Lam Wong    and   Helen M. Meng  

Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
Shatin
Hong Kong 
{wlam,cktsang,wongtl,hmmeng}@se.cuhk.edu.hk

1.	System OverVIEW
Our group participated in the topic detection task and link detection task this year.  The topic detection approach is similar to last year.  The link detection system is a new development for our group this year.  Both detection approaches employ the same story representation scheme and term translation technique. The story representation involves named entities and content terms components. Named entities including person names, geographical location names, and organization names are extracted by transformation-based linguistic taggers, one for English and one for Chinese. This representation is able to capture important terms conveying useful context for topic and link detection purposes. Gloss translation using a parallel corpus is performed on the Chinese story representation so that both detections can be conducted under a uniform representation scheme.
Link detection uses the cosine similarity formula to measure the similarity between two stories. To control the influence of different language pairs during the similarity calculation, a Language Normalization scheme is introduced in the link detection to adjust the similarity.  In this report, we summarize the story representation scheme and term translation technique.  Then we describe our link detection approach.
2. STORY REPRESENTATION AND GlOSS TRANSLATION
Each raw story only comes in a sequence of tokens. We first need to identify sentence boundaries for named entity recognition in the later phase. Lexical clues, such as punctuation marks, are used to locate the sentence boundaries for newswire stories.  The length of silence period is used to locate the sentence boundaries for broadcast news. For Chinese stories, word segmentation is performed using the tool provided by Linguistic Data Consortium (LDC) to locate word boundaries.
The next step is to automatically extract named entities from the news. In particular, we extract three kinds of entities, namely, people names, geographical location names and organization names. We utilize a transformation-based linguistic tagger which tags a sentence according to a set of transformation rules, one set for English and one set for Chinese. Each set of rules is learned from a training corpus, also one for English [1] and one for Chinese [2]. Each training corpus contains sample annotations of named entities. We apply the transformation-based error-driven learning algorithm on the training corpus.
Traditionally, a story is represented by a set of weighted terms. In our approach, we adopt a semantic representation, which comprises named entity feature representation and content term representation. Named entity feature representation is composed of three components: people name component, geographical location name component and organization name component. Each component is represented by a set of terms with corresponding weights.
There are several factors determining the weight of the terms. The first factor is the relative location of the terms in the story. Those terms appearing in the first few sentences will get a higher weight. The other factors are traditional term frequency and incremental document frequency. The top ranked terms are selected as the basis for the named entity feature representation and content term representation.
One requirement of the multilingual topic or link detection problem is to determine whether stories, regardless of the language, are topically related. To tackle this problem, we conduct translation on the story representation of Chinese stories to English so that we can perform unsupervised learning on a uniform data representation. Gloss translation will be performed on the Chinese story terms to allow for direct comparison between stories.
In order to obtain the English translation of the Chinese terms, a bilingual dictionary and a pin-yin file provided by Linguistic Data Consortium (LDC) are used. We first look up the Chinese term in the bilingual dictionary and retrieve the corresponding set of English translation terms. If there is no dictionary entry for a term in the people name component or the geographical location name component, we obtain the translation by means of the pin-yin of the Chinese terms. In general, a set of English terms is obtained when looking up the bilingual dictionary for a Chinese term. The translated English terms will then replace the original Chinese terms to represent the story. The weights of translated English terms are adjusted using a term disambiguation technique which makes use of a parallel corpus. A typical parallel corpus is usually aligned by stories. We currently make use of the parallel corpus collection on Chinese and English news items collected by LDC. This corpus contains news from the Information Services Department of Hong Kong Special Administration Region (HKSAR) of the People's Republic of China. The current collection contains news items, which are story-aligned, released by HKSAR from July 1, 1997 to April 30, 2000.
We propose to transform a typical story-aligned parallel corpus into a passage-aligned corpus via an automated procedure. A statistical length-based approach is employed to identify matching passages between English and Chinese stories. A passage is basically a sentence or a sequence of related sentences. The details of the alignment process are described in [3]. 
3. Link Detection
Our system uses the cosine similarity formula and adopts language normalization to measure the similarity between two stories. At the beginning of the link detection task, the system reads a story pair. The next step is to calculate the similarity of  this story pair. We consider two factors in our similarity formulation. The first factor is the named entity relevance score, sn, computed by processing the weights in the named entity feature representation. The second factor is the content term relevance score, ss, computed by processing the weights in the content term representation. The final similarity score, sf, is a weighted sum of these two scores controlled by a 

parameters, wn, as shown below:

where wn is a user-defined parameter, in the range of [0,1], controlling the relative degree of contribution for the named entity component and the content term component. After similarities are calculated, each story pair has a similarity value.
Language normalization is then applied to adjust the similarity. The normalization is based on the variation of different language combination of story pairs. We design three types of normalization factors in handling Chinese and English stories. They are Chinese Normalization Factor, English Normalization Factor and Multilingual Normalization Factor. According to the language combination of the story pair, the system applies the corresponding normalization factors on the similarity. Let sf be the similarity score calculated on the story pair as described above. Then the final similarity, sF , is:
sF = sf * α
where α is the corresponding language Normalization Factor. If the final similarity is larger than a user-defined threshold, qF, the story pair is assumed to discuss the same topic and to be linked. By changing this threshold, we can adjust the sensitivity of our link detection system. After the system makes the decision on whether the story pair is linked or not, the system processes the next story pair.
4. Link Detection EXPERIMENTAL RESULTS 
4.1 Results for TDT2 Corpus
Five sets of experiments have been conducted on the TDT2 corpus (Jan–June, 1998) to investigate the performance of our link detection approach. Reference story boundaries and native languages were used in all experiments. We have carried out the experiment on the multilingual stories. In the first set of experiments, we ran our link detection system under different similarity thresholds. In Fig.4.1, we summarize the results on detecting multilingual stories by varying the similarity threshold, qF, from 0.01 to 0.05. From the graph, it shows that our approach has a lower detection cost of 0.3744 when qF is set as 0.03. 

Fig. 4.1 Performance on Multilingual Link Detection Under Different Similarity Thresholds
In the second set of experiments, we ran our link detection system under different number of content terms. In Fig.4.2, we summarize the results by varying the number of content terms from 50 to 250. From the graph, it shows that our approach has a lower detection cost of 0.3749 when the number of content terms is set to 150.

Fig. 4.2 Performance on Multilingual Link Detection Under Different Numbers of Content Terms
In the third set of experiments, we ran our link detection system under different values of the English Normalization Factor. In Fig.4.3, we summarize the results on detecting multilingual stories by varying the values of the English Normalization Factor from 0.1 to 0.5. By comparing their detection cost, it shows that our approach with the English Normalization Factor of 0.3 has a lower detection cost of 0.3744. Similarly, by varying the values of the Chinese Normalization Factor from 0.4 to 0.8 as illustrated in Fig. 4.4, we found that the Chinese Normalization Factor of 0.6 has a relatively lower detection cost.

Fig. 4.3 Performance on Multilingual Link Detection Under Different Values of English Normalization Factor

Fig. 4.4 Performance on Multilingual Link Detection Under Different Values of Chinese Normalization Factor
Finally, we ran our system under different values of the Multilingual Normalization Factor from 0.6 to 1.0. The results are summarized in Fig. 4.5. We found that the approach with the value of 0.9 has a lower detection cost.

Fig. 4.5 Performance on Multilingual Link Detection Under Different Values of Multilingual Normalization Factor
The best detection cost from our experiment is 0.3744, which is obtained with the following parameter sets: the similarity threshold is set to 0.3; the number of content terms is set to 150; the Language Normalization Factors are set to 0.3, 0.6, and 0.9 for English, Chinese, and Multilingual stories respectively.

4.2 Results for TDT3 Evaluation Corpus
We have also conducted link detection experiments on the TDT3 corpus (Jul-Dec, 1998). We submitted an experiment run under the conditions of reference story boundaries and native languages as requested. The detection cost for multilingual stories is 0.4263.
REFERENCES

1.	E. Brill. Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part of Speech Tagging. In 1995 Association for Computational Linguistics, Volume 21, Number 4, pages 543 - 565, 1995.
2.	H. Meng and C. W. Ip. An Analytical Study of Transformational Tagging for Chinese Text. In Proceedings of Research on Computational Linguistics Conference  (ROCLING XII), Taipei, Taiwan, ROC., pages 101 - 122, 1999.
3.	W. Lam and H. Meng and K. Hui. Multilingual Topic Detection Using a Parallel Corpus. In Proceedings of the DARPA TDT 2000 Workshop, November 2000.