Automatic Knowledge Representation using a Graph-based Algorithm for Language-Independent Lexical Chaining

Proceedings of the Workshop on Information Extraction Beyond The Document, pages 36–47, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Automatic Knowledge Representation using a Graph-based Algorithm for Language-Independent Lexical Chaining Ga¨el Dias HULTIG University of Beira Interior Covilh˜a, Portugal ddg@di.ubi.pt Cl´audia Santos HULTIG University of Beira Interior Covilh˜a, Portugal claudia@dmnet.ubi.pt Guillaume Cleuziou LIFO University of Orl´eans Orl´eans, France cleuziou@univ-orleans.fr Abstract Lexical Chains are powerful representa- tions of documents. In particular, they have successfully been used in the field of Automatic Text Summarization. How- ever, until now, Lexical Chaining algo- rithms have only been proposed for Eng- lish. In this paper, we propose a greedy Language-Independent algorithm that au- tomatically extracts Lexical Chains from texts. For that purpose, we build a hier- archical lexico-semantic knowledge base from a collection of texts by using the Pole-Based Overlapping Clustering Algo- rithm. As a consequence, our method- ology can be applied to any language and proposes a solution to language- dependent Lexical Chainers. 1 Introduction Lexical Chains are powerful representations of doc- uments compared to broadly used bag-of-words rep- resentations. In particular, they have successfully been used in the field of Automatic Text Summa- rization (Barzilay and Elhadad, 1997). However, un- til now, Lexical Chaining algorithms have only been proposed for English as they rely on linguistic re- sources such as Thesauri (Morris and Hirst, 1991) or Ontologies (Barzilay and Elhadad, 1997; Hirst and St-Onge, 1997; Silber and McCoy, 2002; Galley and McKeown, 2003). Morris and Hirst (1991) were the first to propose the concept of Lexical Chains to explore the dis- course structure of a text. However, at the time of writing their paper, no machine-readable thesaurus was available so they manually generated Lexical Chains using Roget’s Thesaurus (Roget, 1852). A first computational model of Lexical Chains is introduced by Hirst and St-Onge (1997). Their biggest contribution to the study of Lexical Chains is the mapping of WordNet (Miller, 1995) relations and paths (transitive relationships) to (Morris and Hirst, 1991) word relationship types. However, their greedy algorithm does not use a part-of-speech tag- ger. Instead, the algorithm only selects those words that contain noun entries in WordNet to compute Lexical Chains. But, as Barzilay and Elhadad (1997) point at, the use of a part-of-speech tagger could eliminate wrong inclusions of words such as read, which has both noun and verb entries in WordNet. So, Barzilay and Elhadad (1997) propose the first dynamic method to compute Lexical Chains. They argue that the most appropriate sense of a word can only be chosen after examining all possible Lexi- cal Chain combinations that can be generated from a text. Because all possible senses of the word are not taken into account, except at the time of inser- tion, potentially pertinent context information that is likely to appear after the word is lost. However, this method of retaining all possible interpretations until the end of the process, causes the exponential growth of the time and space complexity. As a consequence, Silber and McCoy (2002) pro- pose …

Content truncated to 500 words