Using Gene Expression Programming to Construct Sentence Ranking Functions for Text Summarization

Using Gene Expression Programming to Construct Sentence Ranking Functions for Text Summarization Zhuli Xie, Xin Li, Barbara Di Eugenio, Peter C. Nelson Department of Computer Science University of Illinois at Chicago Chicago, IL 60607, U.S.A. zxie@cs.uic.edu, xli1@cs.uic.edu, bdieugen@cs.uic.edu, nelson@cs.uic.edu Weimin Xiao, Thomas M. Tirpak Physical Realization Research Center of Motorola Labs Schaumburg, IL 60196, U.S.A. awx003@motorola.com, T.Tirpak@motorola.com Abstract In this paper, we consider the automatic text summarization as a challenging task of ma- chine learning. We proposed a novel summari- zation system architecture which employs Gene Expression Programming technique as its learning mechanism. The preliminary experi- mental results have shown that our prototype system outperforms the baseline systems. 1 Introduction Automatic text summarization has been studied for decades (Edmundson 1969) and is still a very active area (Salton et al. 1994; Kupiec et al. 1995; Bran- dow et al. 1995; Lin 1999; Aone et al. 1999; Sekine and Nobata 2001; Mani 2001; McKeown et al. 2001; Radev et al. 2003). Only a few have tried using ma- chine learning to accomplish this difficult task (Lin 1999; Aone et al. 1999; Neto et al. 2002). Most re- search falls into combining statistical methods with linguistic analysis. We regard the summarization as a problem of empowering a machine to learn from human-summarized text documents. We employ an evolutionary algorithm, Gene Expression Program- ming (GEP) (Ferreira 2001), as the learning mecha- nism in our Adaptive Text Summarization (ATS) system to learn sentence ranking functions. Even though our system generates extractive summaries, the sentence ranking function in use differentiates ours from that of (Edmundson 1969; Sekine and Nobata. 1999; Goldstein et al. 1999) who specified it to be a linear function of sentence features. We used GEP to generate a sentence ranking function from the training data and applied it to the test data, which also differs from (Lin 1999) who used decision tree, (Aone et al. 1999; Kupiec et al. 1995) who used Bayes’s rule, and (Neto et al. 2002) who imple- mented both Naïve Bayes and decision tree C4.5. This paper presents our approach, details the sys- tem architecture, and discusses preliminary experi- mental results. Conclusions and future work are outlined at the end. 2 Background 2.1 Gene Expression Programming Gene Expression Programming (GEP), first intro- duced by (Ferreira 2001), is an evolutionary algo- rithm that evolves computer programs and predicts mathematical models from experimental data. The algorithm is similar to Genetic Programming (GP), but uses fixed-length character strings (called chro- mosomes) to represent computer programs which are afterwards expressed as expression trees (ETs). GEP begins with a random population of candidate solutions in the form of chromosomes. The chromosomes are then mapped into ETs, evaluated based on a fitness function and selected by fitness to reproduce with modification via genetic operations. The new generation of solutions goes through the same process until the stop condition is satisfied. The fittest individual serves as the final solution. GEP has been used to solve symbolic regression, sequence induction, and classification problems effi- ciently (Ferreira …

Content truncated to 500 words