Using Multiple Discriminant Analysis Approach for Linear Text Segmentation

R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 292 – 301, 2005. © Springer-Verlag Berlin Heidelberg 2005 Using Multiple Discriminant Analysis Approach for Linear Text Segmentation Zhu Jingbo1, Ye Na 1, Chang Xinzhi 1, Chen Wenliang 1, and Benjamin K Tsou2 1 Natural Language Processing Laboratory, Institute of Computer Software and Theory, Northeastern University, Shenyang, P.R. China {zhujingbo, chenwl}@mail.neu.edu.cn {yena, changxz}@ics.neu.edu.cn 2 Language Information Sciences Research Centre, City University of Hong Kong, HK rlbtsou@cityu.edu.hk Abstract. Research on linear text segmentation has been an on-going focus in NLP for the last decade, and it has great potential for a wide range of applications such as document summarization, information retrieval and text understanding. However, for linear text segmentation, there are two critical problems involving automatic boundary detection and automatic determination of the number of segments in a document. In this paper, we propose a new domain-independent statistical model for linear text segmentation. In our model, Multiple Discriminant Analysis (MDA) criterion function is used to achieve global optimization in finding the best segmentation by means of the largest word similarity within a segment and the smallest word similarity between segments. To alleviate the high computational complexity problem introduced by the model, genetic algorithms (GAs) are used. Comparative experimental results show that our method based on MDA criterion functions has achieved higher Pk measure (Beeferman) than that of the baseline system using TextTiling algorithm. 1 Introduction Typically a document is concerned with more than one subject, and most texts consist of long sequences of paragraphs with very little structural demarcation. The goal of linear text segmentation is to divide a document into topically-coherent sections, each corresponding to a relevant subject. Linear text segmentation has been applied in document summarization, information retrieval, and text understanding. For example, in recent years, passage-retrieval techniques based on linear text segmentation, are becoming increasingly popular in information retrieval as relevant text passages often provide better answers than complete document texts in response to user queries[1]. In recent years, many techniques have been applied to linear text segmentation. Some have used linguistic information[2,3,4,5,6,9] such as cue phrases, punctuation marks, prosodic features, reference, and new words occurrence. Others have used statistical methods[7,8,10,11,12,13,14,15] such as those based on word co- occurrence, lexical cohesion relations, semantic network, similarity between adjacent parts of texts, similarity between all parts of a text, dynamic programming algorithm, and HMM model. Using Multiple Discriminant Analysis Approach for Linear Text Segmentation 293 In linear text segmentation study, there are two critical problems involving automatic boundary detection and automatic determination of the number of segments in a document. Some efforts have focused on using similarity between adjacent parts of a text to solve topic boundary detection. In fact, the similarity threshold is very hard to set, and it is very difficult to identify exactly topic boundaries only according to similarity between adjacent parts of a text. Other works have focused on the similarity between all parts of a text. Reynar[7] and Choi[13] used dotplots technique to perform linear …

Content truncated to 500 words