1 Introduction
Topic segmentation of a text concerns the detection of its overall organization into themes or topics, and the identification of text segments that correspond to the topics. Once the segments are identified, they can be described by key terms or headline-type descriptors. Sentences are concatenated in typical patterns of thematic progression. Detection of these patterns, identification of segment boundaries and extraction of descriptive terms make it possible to automatically generate a detailed table of contents of a text.
Humans often rely on tables of contents for selecting information. A table of contents breaks a text into segments, reflects the patterns of topical organization of the text (e.g. hierarchical, sequential), provides pointers to the start of each segment, and describes a segment with a headline. The table of contents assists its users in quickly finding information, or zooming in and out on content. It informs them about the salience of a topic (e.g. by considering the level in a hierarchically structured table on which the topic appears or by considering the amount of text devoted to it), and its hierarchical structures show the broader and narrower context in which a topic is treated.
Building a table of contents of a text is useful initial step in text summarization, which aims at showing salient content up to a certain level of detail. It is particularly useful in situations where it is crucial that information is displayed as economically as possible (e.g. on small screens of mobile phones or PDAs). A table of contents is also convenient in systems that assist in information retrieval and selection. It can be used in passage retrieval and for weighting the importance of a topic. It can be practical in information extraction and question answering tasks as it points the user to topical segments and to the contexts in which these topics are treated.
The tables of contents that accompany text are traditionally manually built. When they are automatically generated, they rely on the heading structures (e.g. available in large texts). This article focuses on the automatic construction of a table of contents when it is not possible to rely on heading structures. Our approach to topic segmentation is based on the distribution of topic and comment in sentences, and on patterns of thematic progression in text. Linguistic theories of topic and comment are modeled both deterministically and probabilistically, the latter referring to the training of probabilistic classifiers. Our algorithm has been tested on English texts of various text genres and is integrated in our text summarization system SUMMA, which participated in the Document Understanding Conferences (DUC), organized by the National Institute of Standards and Technology (NIST), USA.
The article reports on research into topic segmentation and content presentation in the context of a project on generic technologies for information extraction from texts. It is organized as follows. The first section discusses the linguistic and cognitive background of our approach, and sets the research goals. The next section discusses the methods and the algorithms. A third section describes our experiments and results. It is followed by the discussion of the results and by recommendations for future improvements. Before the conclusion, related research is described.
2 Linguistic-cognitive background and research goals
The mental representation that humans make of the topics of a text – its macrostructure – gives them an insight into the global text topic (the kernel of the content) and its subtopics (more detailed meanings of the content) (Kintsch and van Dijk Reference Kintsch and van1978; van Dijk Reference Van Dijk and van Dijk1997). Although the thematic structure of a particular text often relies on unwritten guidelines for a specific text type, the author of a text has great freedom in choosing the thematic structure that best conveys this macrostructure. Document collections that contain different text types (e.g. the World Wide Web) confront us with many instances of thematic organization. Among the most prominent thematic patterns in human discourse are: The hierarchical structuring of the main topic into subtopics, which in their turn can be divided recursively into smaller units (Grosz and Sidner Reference Grosz, Sidner, Walker, Joshi and Prince1998); the progressive or sequential pattern that describes different concatenated topics; and the recurrent pattern or semantic return, in which a topic is suspended at one point and resumed later in the discourse (Hinds Reference Hinds and Givón1979; Kononenko, Kononenko, Popov and Zagorulko Reference Kononenko, Kononenko, Popov and Zagorulko2000). Real texts exhibit combinations of these patterns. For instance, one can tell a story in successive episodes, each of which is composed of subtopic sequences. The topics of a text are closely related to the linguistic surface phenomena of a text. Its creator explicitly signals topicality in order to achieve the text correct interpretation by its users (van Dijk Reference Van Dijk1988).
Apart from the ordering of thematic content through schemata that are typical for certain text genres (e.g. the lead of a news story signals the main topic), and the use of cue words or phrases that introduce a topic or that are an indication of its salience (e.g. the important point is that), the main surface cues for topicality are content words, their frequency and their position. Content terms (especially the ones contained in noun phrases) that occur extensively throughout a text will also be remembered by the readers of the text as referring to important topics. Terms that are only marginally covered can be remembered as detailed topics in the context of the important topics. However, the purpose or background knowledge of a reader might cause a topic that is only marginally covered to be remembered by the reader as crucial (Kintsch Reference Kintsch, Louwerse and van Peer2002). By means of a semantic return, the writer of a text often resumes a topic as a way of stressing it.
We can also judge the topicality of a term at the sentence level. A sentence is composed of a sentence topic and of additions to the topic (e.g. properties of the topic, relationships with other items, modifications of the topic) (Givón Reference Givón and Givón1983; Kieras 1997; Peregrin 1996; Tomlin, Forrest, Pu and Kim Reference Tomlin, Forrest, Pu and Kim1997). These additions are usually called foci or comments. The topical deep structure is closely connected to the way that humans communicate (Haji
ová and sgall 1988). In the topicality structure of a sentence, the topic is what the sentence is about (Reinhart Reference Reinhart1982). It is the starting point of the utterance, the object or person about which or whom something will be communicated, while the comment usually introduces new information that is ascribed to the topic (Halliday Reference Halliday, Kress and Halliday1976; Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988; Fries Reference Fries and Coulthard1994). The transitional element between topic and comment might be a verb, although the verb is often considered as part of the comment. For an in-depth discussion of topic and comment, we refer to Hajiová (1994) and Meinunger Meinunger (Reference Meinunger2000). Another analysis of the sentence is made by the dichotomy between theme and rheme. According to Meinunger (2000) theme Footnote 1 refers to the old, vehicular part of the sentence, which is opposed to the new informative part, the rheme.
We find in the literature the following heuristics for detecting the topic of a sentence.
2.1 Within-sentence position
Noun phrases are stressed when they occur in a sentence initial position (Givón Reference Givón and Givón1983; Givón Reference Givón, Hammond, Moravcsik and Wirth1988; Givón Reference Givón2001; Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988; Meinunger Reference Meinunger2000). This phenomenon is called topicalization. In Subject-Verb-Object (SVO) languages such as English or Dutch the grammatical subject often has a prominent position in the sentence (Halliday Reference Halliday1967), which makes that in very simple English sentences, the topic is usually identical to the subject of the sentence and the comment corresponds to the predicate. In other cases, the topic corresponds to an adverbial phrase in initial position (e.g. As for swimming, Waikiki is good.)Footnote 2 (Paducheva 1996). The only exception to this rule is the case in which the comment to the topic receives an important stress, but studies have shown that this might occur when the topic is already very familiar, so there is no problem in ordering topic after comment (Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988). Left-dislocation (i.e., taking a phrase out of its grammatical order and moving it to the beginning of its clause) often has the effect of topicalization (e.g. Barcelona, people find it a very nice city.) (Givón Reference Givón and Givón1983; Gregory Reference Gregory and Michaelis2001; Grosz Reference Grosz, Sidner, Walker, Joshi and Prince1998). This first heuristic refers to the general rule that importance goes hand in hand with a prominent position in the sentence.
2.2 Topic persistency
The persistency of the topic in a discourse is another important cue for detecting the main topic of a sentence (Givón Reference Givón and Givón1983; Givón Reference Givón, Hammond, Moravcsik and Wirth1988; Givón Reference Givón2001; Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988). A main sentence topic often occurs as the main topic in consecutive sentences, and, if the candidate topic occurs multiple times in a single sentence, this is an extra indication of its salience. Persistency can be expressed with the help of pronouns (Sidner Reference Sidner, Brady and Berwick1983) or other noun phrase coreferents (e.g. Hillary Clintonwrote a biography. Sheis now senator. The former first ladyhas presidential ambitions). Two noun phrase entities are coreferent when they refer to the same person or thing in the situation described in the text.
2.3 Thematization of the rheme
The comment of a sentence might contain new information, which can become the topic of the next sentence (e.g. John found a cat. The catwas very hungry.) (Hahn Reference Hahn1990).
2.4 Contextual binding
A sentence might contain different topics and some of these are more important than others (Givón Reference Givón and Givón1983). In such a case, the most important topic is the one that is most contextually bound, i.e., that is mentioned in the immediate previous context of the discourse (e.g. John came to see me. Johnand his sister used to live in our neighborhood.) or belongs to the shared common background knowledge of the writer and reader (Peregrin 1996).
2.5 Definiteness
A definite noun phrase or its coreferent has more chances of being a topic of a sentence (Givón Reference Givón and Givón1983; Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988; Roberts Reference Roberts, Walker, Joshi and Prince1998) than indefinite phrases, and indefinites are often introduced in the comment to the topic (e.g. We saw a homeless man. The manwas very sick and was already quite old.). Similarly, the fact that a noun phrase is made definite by means of a restricted relative clause is an indication of topicality (Gundel Reference Gundel, Bosch and Sandt1999).
2.6 Contrast
When a noun phrase is in contrastive stress, it is usually the topic of a sentence (Gundel Reference Gundel, Bosch and Sandt1999). Contrastive focal points can be detected through rhetorical cues (e.g. Now, in Europeone does not cultivate bananas.).
2.7 Animateness
Noun phrases that refer to humans are sometimes more important than noun phrases that refer to animate entities and these are usually more important than noun phrases that refer to inanimate things (Croft Reference Croft1990). However, this cue might not be very reliable as it depends on the subject domain or genre (e.g. in political news persons are important, while in financial news institutions become important; in fairy tales animals play sometimes a significant role).
2.8 Foreground/background
Noun phrases that occur in main clauses usually contain foreground information, while noun phrases than only occur in subordinate clauses in many cases contain less important or less familiar background information (Hopper Reference Hopper and Givón1979).
The above heuristics have been explored, for example, by Gundel (Reference Gundel, Hammond, Moravcsik and Wirth1988) who studied examples in 30 languages including among others important Indo-European (e.g. English, German, French, Russian), Afro-Asiatic (e.g. Arabic, Hebrew), Altaic (e.g. Japanese, Korean) and Sino-Tibetan (e.g. Mandarin) languages. Givón (Reference Givón and Givón1983) studied topic continuity in several languages (e.g. English, Spanish and Hebrew). Some languages have explicit morphological topic markers (e.g. Japanese) (Gundel Reference Gundel, Hammond, Moravcsik and Wirth1988). According to Dane
(1974) three types of thematic progression rely on the topics and comments of individual utterances:
• Simple linear thematic progression (also called thematic progression with linear thematization of rhemes): The comment R m of the utterance m, becomes the topic T n of a (the) next utterance n.
• Thematic progression with a continuous (constant) topic: The same topic or its coreferent T appears in a series of utterances, to which different comments R i are linked.
• Thematic progression with derived topics: The topic T m of an utterance m, as well as the topic T n of an utterance n, and possibly more topics all refer to an overall topic called the hypertheme T h.
The goal of our research is to design, implement and test a novel algorithm for topic segmentation and for building a table of contents of a text that gives an objective estimation of the salience of the text's topic and subtopics, and that is based on the above discourse theories of thematic patterns and their progression in a text. An important focus of our research is the detection of the main topic of a sentence, for which we have developed both a deterministic and a probabilistic approach.
3 Methods
3.1 Algorithm
Our algorithm (Figure 1) uses generic topical cues for detecting the topic structure of a document text. Apart from a first preprocessing step covering tokenization and morphosyntactical tagging (Module 1), the topic segmentation algorithm relies on three text analysis processes. One module detects term positions and distributions in a text (Module 2). Another concerns the detection of a sentence topic (Module 3) and one optional process resolves noun phrase coreferents (Module 4). Based on the knowledge that is generated in these analyses, Module 5 calculates the topic hierarchy, segments the text and constructs its table of contents. In the following subsections we describe the steps in detail except for the coreferent resolution module, which is not yet included in the experiments described below.Footnote 3
Schematic representation of the modules responsible for the hierarchical topic segmentation.
3.1 Input
The aim is that the system can process texts of various genres that contain fairly coherent content (e.g. news stories, encyclopedia articles but not e.g. lists, poems). The system has been designed for relatively short texts up to a few pages of length. We assume that longer texts can be broken into large segments based on their heading structure (Yang and Wang Reference Yang and Wang2003), which in their turn can be processed by the topic segmentation algorithm. An example input is given in Figure 2. The system has actually been tested on news stories, encyclopedia articles and Web texts (see section 4).
Short example text (APW19981004.0146 DUC-2003 Document set d30028t).
3.3 Tokenization and morphosyntactical tagging
We break the text into sentences and words, and tag each word with its part-of-speech. For English texts we have used the LTCHUNK software, developed by Andrei Mikheev at the University of Edinburgh. LTCHUNK consists of a noun and verb phrase chunker built on top of a part-of-speech tagger (LTPOS) that uses a Hidden Markov Model disambiguation strategy (Mikheev Reference Mikheev1998). It assigns part-of-speech tags to individual words and orders them into basic noun or verb chunks. A noun phrase chunk (or shortly noun chunk) is a noun phrase that is not modified by another prepositional noun phrase. In the output of the chunker it is enclosed in double square brackets and might also comprise a pronoun as it is shown in the following example:
It has been demonstrated that nouns properly represent the content of a text (Hahn Reference Hahn1990). The tagger allows identifying proper names. We also identify the head noun of each noun chunk by using language dependent knowledge, and store a description of the noun chunk. The latter is composed of the head or of the head with modifiers in case they form a collocation or proper name. Collocations are terms of which the constitutive parts typically co-occur more often than by chance and are characterized by limited compositionality, i.e., there is usually an element of meaning added to the collocation that cannot be predicted from the meanings of the composing parts (e.g. joint venture). A collocation is identified, when the independence of the composing words of the collocation can be rejected with a certain significance level in a training corpus. We used the likelihood ratio for a binomial distribution to reject or accept the hypothesis of independence (Dunning Reference Dunning1993) and to detect collocations of bigrams or trigrams composed of nouns or of adjectives followed by nouns (for details on our implementation see (Mens and Angheluta (Reference Moens and Angheluta2003)).
3.4 Calculate word distribution
The calculate word distribution module computes for each term (single word or collocational term) its position in the text given by the sentence number and its location within the sentence. It also contains the functions for computing word distributions needed for the probabilistic classifier.
3.5 Determine main sentence topic
The input of this module is the set of sentences that form the input text in reading order. Each sentence is broken into its noun chunks. For each noun chunk a number of features are extracted in accordance with the first four linguistic heuristics formerly described. We choose these features because of their easy and unambiguous detection in text. These features include:
• First noun chunk (FNC): The noun chunk is the first one in the sentence.
• Noun chunk before verb phrase (NCBVP): The noun chunk is located before the first verb phrase in the sentence.
• Persistency (P): The noun chunk has a member noun that also occurs in the previous sentence.
• Persistent main topic (PMT): The noun chunk has a member noun that is a member of the main topic of the previous sentence.
• Multiple occurrences (MO): The noun chunk has a member noun that occurs more than once in the current sentence.
These features are used in both our deterministic and probabilistic classifiers for detecting the main sentence topic. At this moment the topic analysis does not go down to the clausal level, which implies that coordinated and subordinated clauses are not properly treated. Sentences containing zero noun chunks do not have a main topic.
3.5.1 A deterministic approach
In the deterministic approach (referred to as DET in the tables) we have implemented an algorithm that selects the noun chunk representing the main topic of a sentence based on the heuristic rules that are applied in a chosen order of priority.
Schematic representation of the algorithm:
In case of ties (e.g. two terms occur in the previous sentence), the algorithm gives higher priority to a noun chunk whose noun member is part of the main topic of the previous sentence (nc.MT == true), or to the first occurrence of the chunk in the current sentence.
3.5.2 A probabilistic approach
Although the discourse cues modeled in the deterministic algorithm are evidenced by the linguistic literature as being relevant for sentence topic detection, the implementation of the priority in which these cues apply, is rather intuitive and ad hoc. Moreover, the dependency of features that occur together is modeled quite simplistically. In information retrieval there is currently a considerable interest in probabilistically modeling textual contents. World models in a probabilistic approach are conditional probability distributions describing the dependence of certain variables on other variables in probabilistic terms. It seemed useful to us to model the detection of the main topic of the sentence probabilistically.
For the probabilistic approach, we rely on a training corpus of example sentences with their main topics manually assigned to them. We have implemented several approaches. First, we estimate the probability distributions of the various parameters involved in main sentence topic assignment from the training set, and combine the strengths of the various distributions in a mixture model in order to obtain an estimate of the overall distribution. We use a linear interpolation method for this combination. The interpolation weights are equally chosen, or are estimated by the expectation maximization (EM) algorithm. The estimate of the full distribution is used to find the most probable main topic of a sentence in a test example. Additionally, we have trained and tested a Maximum Entropy Modeling (MEM) classifier.
Distribution estimation with the EM algorithm: To automatically classify a noun chunk nc into the classes main topic or not main topic (C), we estimate a probability distribution indicating how likely the noun chunk is to be assigned each possible class given its features:
(1)
It would be possible to calculate this distribution directly from the training data by counting the number of times a term appears as a main topic with this combination of features, and by dividing this number by the total number of times the combination of features appears.
(2)
In many cases, we might never see a particular combination of features in the training data, and in other cases, we might see the combination only very rarely, providing a poor estimate for the probability. We expect that the features interact in various ways and we cannot train directly on the full feature set. For this reason, we have built a classifier by combining probabilities from distributions conditioned on a variety of subsets of the features. We compute the relative occurrence of noun chunks with each possible combination of features, and choose the subset of features for which the occurrence with noun chunks is more than 1% in the training set, and compute the probability distribution conditioned on each chosen feature set from the training set. For our training set (see section 4), this resulted in the computation of ten distributions. To compute the general distribution given in (1), we have to combine the strengths of various distributions. A possible combination method is linear interpolation of the probability distribution that apply for the constituent features of the test example nc.
(3)
where
In a first approach we use equal interpolation weights (referred to as PROB-EQ in the tables). A more sophisticated method of estimating interpolation weights is by using the Expectation Maximization (EM) algorithm (referred to as PROB-EM in the tables). The EM algorithm (Dempster, Laird and Rubin Reference Dempster, Laird and Rubin1977) is an iterative algorithm, which can be used for calculating maximum likelihood parameter estimates of a model, where some of the random variables are observed, and some others are hidden (here the interpolation weights are hidden). It is theoretically guaranteed that the EM algorithm converges to a local maximum.
(4)
(5)
Each iteration l estimates μi a new value by first computing the E-step and then the M-step until the new value is not anymore significantly different from the old one.
Maximum Entropy Modeling (MEM) computes the probability distribution with maximum entropy that satisfies the constraints set by the training examples (Berger et al. Reference Berger, Della Pietra and Della1996; Ratnaparkhi Reference Ratnaparkhi1998). The training examples are represented by k binary-valued feature functions f j(nc, C), where C refers to the class and nc to the noun chunk context. These indicator functions represent meaningful statistics from the training data a modeler wishes to include. For example, a useful feature function for main sentence topic detection might be the following: If the noun chunk has a member that also occurs in the previous sentence, than the noun chunk is a main sentence topic:
The statistics of a feature function are captured by ensuring that the model adheres to the following constraint:
(6)
where
is the expectation of the feature function f j and
is the empirical expectation of f j estimated from the training data.
From all the models p ∈ P (7) that satisfy constraint (6) the model p* is chosen that maximizes the entropy or the uncertainty (9).
(7)
(8)
(9)
This distribution has an exponential form:
(10)
where C refers to the class; nc to the noun chunk context; Z is a normalizing constant; and k is the number of contextual features.
The Maximum Entropy Modeling first determines the empirical distribution from the training data via maximum likelihood estimation and uses this expectation to adjust the model parameter αj of the feature function f j(nc, C), while simultaneously matching the rest of the feature functions and their expectations. As such, the modeling estimates p* (10) by adjusting the k model parameters αj, 1 <= j <= k, subject to the constraints imposed by the k feature functions. The model uses an iterative procedure such as generalized iterative scaling (GIS) to estimate the model parameters αj. For a new noun chunk instance, the membership for being a main topic and for not being a main topic is computed and the class with the highest probability is assigned. The model takes into account possible dependencies between features and also accurately discriminates relevant from irrelevant features during training, thus relieving the implementer from selecting accurate features manually. We did not implement this MEM classifier ourselves but used open-source software.
3.6 Coreferent resolution
Ideally, our algorithm should include a tool for noun phrase coreference resolution, which detects when two noun phrase entities (nouns, proper noun phrases and pronouns) refer to the same entity in the situation described in the text. Such a tool has not been integrated yet. An anaphoric reference such as a pronoun can refer to the main topic of a sentence, and is often used to stress the persistency of a topic in the discourse (Sidner Reference Sidner, Brady and Berwick1983).
3.7 Calculation topic hierarchy
The algorithm for calculating the topic hierarchy consists of two main steps.
A first step consists of the detection of topically coherent segments. We define a topically coherent segment as a passage of which the consecutive sentences have the same main sentence topic. For detecting coherent segments, the head noun of the noun chunk that is designated as main topic of the sentence (further called segment topic term) is selected. A coherent segment is formed by consecutive sentences that have the same segment topic term, or by one isolated sentence, if none of the neighboring sentences has the same segment topic term. A coherent segment is thus formed by sentences that are linked by patterns of thematic progression with a continuous topic.
In the second step, topical relationships between segments are computed, they regard more specifically hierarchical and sequential relationships and semantic returns. Each segment is described by key terms, and a table of contents is built. The input is a list of topically coherent segments in reading order; the output is a table of contents representing topical segments which are described by their key terms and file pointers. Here follows the schematic representation of this step of the algorithm:
During the second step of the algorithm, each coherent segment in the list of coherent segments receives the necessary attributes (i.e., level of topicality, segment boundaries and description), so that a table of contents can be easily generated from this list. In an alternative implementation (not shown in the schematic representation of the algorithm), in case there is evidence of a previous topic (rule *), the coherent segment of the previous topic and the current coherent segment are merged. Here follows a simple example (main sentence topics are underlined):Footnote 4
The output of the first step of the algorithm comprises 4 segments (one formed by sentence a, a second formed by sentence b and c, a third formed by sentence d and e, and a fourth formed by sentence f). The initialization of the second step causes sentence a to be assigned to topical level 1. Rule ** causes sentences b and c to be assigned to topical level 2 (Barcelona is a subtopic mentioned in the context of John). Rule * will cause sentence d and e to be assigned to topical level 1 and to join the segment formed by sentence a. Rule *** makes a totally novel segment at topical level 1 composed of sentence f.
The generation of a table of contents is illustrated with the above simple example:
The assignment of a subtopical relationship might be ambiguous in that it can be based on different terms that previously occur in the text and that belong all to different levels of topicality. In this case the level of topicality closest to the current segment (closest in context) is chosen. When selecting a hypertheme topic term, a term that is also a main sentence topic has always priority over a comment term. Each topical segment in the hierarchy is described by its textual boundaries by means of character pointer positions that signal the start and end of a segment in the text, and by one or more key terms.
The key terms are composed of the segment topic terms and are sometimes augmented by comment terms (e.g. bases in Figure 3). Terms from comments are only added to a segment description when the comment terms are the cause of a subtopic. One of the characteristic thematic patterns of a text is that the comment of a topic becomes the main topic in the next sentence. This phenomenon regards a pattern of thematic progression with linear thematization of a rheme. In this case this topic is seen as a subtopic of the topic of the previous sentence (e.g. when processing sentence b, Barcelona becomes the subtopic of John: The text speaks about Barcelona in the context of John). However, the writer might draft the text in such a way that a subtopic of the comment becomes the main topic of the next sentence (e.g. in our simple example above when sentence b is replaced by Gaudi art attracts many people.). In this case, the comment Barcelona causes the subtopic Gaudi art. So, adding the comment term Barcelona to the description of the segment to which the comment term belongs is preferable (rule ****). Note that in this algorithm a hierarchical relationship between segments is based on a thematization of a rheme or on thematic progression with derived topics. The example also illustrates the pattern of thematic progression with continuous or constant topic (e.g. John in sentences d and e) and thus shows the detection of the patterns of thematic progression as defined by Dane (1974).
Example of table of contents (APW19981004.0146 DUC-2003 Document set d30028t).
The assignment of subtopic segments requires the update of the boundaries of the parent segments. Similarly, the merging of segments with identical main segment terms that are separated by subtopic(s) into one hypertheme segment causes adaptations of the segment boundaries.
3.8 Output
By computing the topic hierarchy, we have constructed a table of contents of the text, which in case of the illustrated text has a treelike structure and which indicates the topics and more detailed subtopics (Figure 3). For each topic, the text segment that covers the topic is represented by its boundaries, i.e., begin and end positions in the text (see the numbers in Figure 3). Each segment is described with one or more terms extracted from the segment (when the extracted terms do not follow each other in the segment, they are separated by a tab in Figure 3). Each topic term is positioned at a certain level of topicality in the hierarchy (indicated by the indentations in Figure 3).
4 Experiments and results
We performed an intrinsic evaluation based on a number of texts randomly selected from the DUC-2002 (6 texts) and DUC-2003 (60 texts) corpora, the World Wide Web (1 text) and the Encyclopedia Columbia (5 texts). The DUC-corpora contain news texts and are of different lengths (they usually contain between 10 and 35 sentences). The Power of Accutane, a three page long text found on the World Wide Web discusses in about 100 sentences the treatment of Acne with the medication Accutane. In addition, the role of the FDA (US Food and Drug Administration) in informing patients is discussed. These scientific data are interwoven with a story of an individual Acne patient. Some of the DUC-2002 texts and the text on the treatment of Acne contain a substantial amount of speech. The short encyclopedia articles (10-20 sentences) discuss different subjects (see Table 3). Both the identified main sentence topics and the constructed table of contents were evaluated.
For the evaluation of the main sentence topics, each text was annotated by an English language student and by a researcher with a computational linguistics background. They independently marked the noun chunk that expresses the main sentence topic. This was done for all sentences in the above corpora. Sentences that consist of multiple clauses, or coordinated (and to a lesser extent also subordinated) clauses, might contain multiple topics. In this case, the annotators were asked to consider the topic that they considered to be most important with regard to the previous discourse context. Agreement between the two annotators on the main sentence topic was quite high (kappa statistic of Carletta (Reference Carletta1996) of 0.928 where the number of samples is 7798 and the number of categories is 2). The noun chunks to be classified were already automatically detected. Afterwards, the annotators discussed the cases on which there was disagreement until a consensus was reached, which was used as the model.
Because the accuracy of the classification of a noun chunk benefits from the many correct non main sentence topic assignments, we only give here the precision results of the main sentence topic classification. We compute the precision of the main sentence topic assignment as the percentage of correct main topic assignments to a noun chunk among the main topic assignments in a corpus or text. Because we assign only one main topic per sentence, precision equals recall.
Table 1 shows the results in terms of the precision of the classification of a noun chunk into a main sentence topic of the DUC-2003 texts. A total of 5750 noun chunks were classified. Using a deterministic approach (DET), the probabilistic approach that equally weights the probability distributions (PROB-EQ), the probabilistic approach that estimates the interpolation weights by using the Expectation Maximization algorithm (PROB-EM) (convergence threshold is empirically set to 0.0000l), and the Maximum Entropy Modeling classifier (MEM). For the probabilistic approaches, we performed 5-fold cross validation of the DUC-2003 corpus. Because the main sentence topic of English sentences is often the subject of the sentence and another important heuristic for topicality is prominent position, we choose as a valuable baseline for our approach the detection of the noun chunk that occurs just before the first verb phrase in the sentence (or the one just after this first verb chunk in case a preceding one is missing). This noun chunk should not be preceded by a preposition. This analysis aims at detecting the first occurring subject in the sentence in the lack of sentence parse information (the subject was in 93.2% of the cases correctly detected).
Precision results for the DUC-2003 corpus
Table 2 shows the results in terms of average precision of the classification of a noun chunk into a main sentence topic for the DUC-2002 corpus, the Web text and the encyclopedia texts. A total of 2048 noun chunks were classified. The probabilistic classifiers are all trained on the DUC-2003 corpus. The results are shown per text. In the above experiments we allow pronouns to be classified as a main sentence topic, which is the case in real texts. Table 1 and 2 realistically demonstrate the correctness of the assignments of the main topic of a sentence. However, when building the table of contents, the lack of a correct resolution of coreferent noun phrases might entail errors with regard to the detection of segment boundaries and segment relationships.
Precision results for the DUC-2002, World Wide Web and Encyclopedia Columbia texts
Our precision results relate to the correct identification of the noun chunk that acts as main topic. This noun chunk can contain modifiers (e.g. the expensive social welfare system), or can be part of a larger phrase in the sentence (e.g. the nationwide death toll of at least 150 people). In the table of contents our system outputs only the head of a main topic chunk (possibly augmented with proper name modifiers), when this chunk acts as the main topic of a segment, or the collocation of which this head word is part. For a limited set of texts (the 6 news stories from the DUC-2002 corpus, 1 text from the World Wide Web and the 5 texts from the Encyclopedia Columbia), we asked the annotators to restrict or expand the noun chunk that acts as main sentence topic to a suitable topic description. We compare this identified description with the description extracted as main sentence topic by the system. A much stricter precision (which we call precision-S) considers the assignment as being correct only if the correct sequence of words that were manually annotated by the expert is detected as topic term. This evaluation measures both the correctness of the identification of a noun chunk that acts as main sentence topic and the extracted description of this topic. The collocations that the system extracts are learned per corpus.
The level of topicality of a topic is defined by its depth in the tree. Knowledge of the main topic of each sentence, its level of topicality and of the order of the topics in the text allows constructing the table of contents. For the DUC-2002 corpus, the Web text and the encyclopedia texts the annotators designated the level of topicality for each main sentence topic.
To evaluate the level of topicality of each topic, we give a score which is 100% if the level assigned by the machine equals the level assigned by the expert. We compute |machine level| – |expert level|/ number of expert levels, where number of expert levels refers to the number of levels of topicality for a particular text. Ideally this score should be close to one. We compute the topic level divergence error as the complement of this score with one.
Table 3 shows the strict precision for the main topic assignment in which also the extraction of representative terms is computed. This table also shows the average topic level divergence error. We give the results per text.
Precision-S results and average topic level divergence error for the DUC-2002, World Wide Web and Encyclopedia Columbia texts
Given the main sentence topics, given the level of a topic in the discourse tree expressed by a main sentence topic, given the fact that consecutive sentences with a common main sentence topic can be grouped in a coherent segment of the same topical level, and given that a table of contents shows topical segments in reading order and at the correct topical level, we can easily construct the table of contents of a text. Evaluating the performance of the individual steps does not give a global evaluation score for the tables of contents that are automatically generated (such a score could be obtained by combining the individual evaluation scores with interpolation weights), but it gives a good indication what the capabilities and problems of the proposed approach are.
We acknowledge that consensus among two annotators is not a guarantee for an ideal model on which the intrinsic evaluation is based, and that our empirical results suffer from this shortcoming. Especially, the detection of an informative topic description (used for the computation of the Precision-S results in Table 3) and of the level of topicality of a segment (used for the computation of the average topic level divergence error in Table 3) are sensitive to this shortcoming. Similarly, as an alternative for the topic level divergence error, more sophisticated evaluation measures when ranking segments according to salience could have been tried (Marcu Reference Marcu2000) in case of the availability of a larger set of annotated examples and of more annotators. The results shown in Table 3 serve as an illustration of the difficulty of the tasks and should be an incentive for further research.
On the other hand, our methods – especially these for the detection of the main topic of a sentence, which is the main focus of our work – are grounded in firm linguistic and cognitive theories that are sustained by multiple independent studies.
Ideally, the tables of contents should be evaluated extrinsically in different tasks, among which the most important being information retrieval and text summarization.
Our text summarization system SUMMA, which integrates the topic segmentation tool for computing the salience of a segment in the discourse, was tested by our participation in the Document Understanding Conferences (DUC) 2002, 2003 and 2004 (Angheluta et al. Reference Angheluta, Mitra, Jing and Moens2004; Moens et al. Reference Moens, Angheluta and Dumortier2005). We have exploited the tables of contents for making generic, viewpoint-oriented and question-oriented summaries of single and multiple documents. Both the level of topicality of a segment and its coverage in the text are an indication of salience of a topical segment (in the DUC experiments we used the level of topicality). Salient segments are chosen up to a certain level of detail as indicated by the table of contents. The first sentence of a salient segment (or its key terms) can be extracted to form a summary. Single-document summaries obtained in this way were concatenated and used as input in our tool for multi-document summarization. In DUC 2003, we were second in terms of average usefulness of our single-document headline summary and fourth in terms of average coverage of our multi-document viewpoint-oriented summaries. In DUC-2004 we scored second in terms of average coverage of the multi-document question-oriented summaries and fourth with our generic multi-document summaries. Apparently, salient content from individual texts is valuable in multi-document summarization. The usefulness of a headline was evaluated as a score that is inversely proportional to the rank of each summary of the document in making two assessors to select the document (e.g. in a retrieval task) assuming that the content of the document is relevant. Coverage is a measure of recall, i.e., the percentage of units of a model summary found in the system-made summary (Over and Yen Reference Over and Yen2003).
5 Discussion of the results and directions for future improvements
The table of contents gives the user of an information system the possibility to assess the content of a text. The output of the algorithm is a structure in the form of a tree or of several parallel trees (in case there are multiple distinct, main topics). The character positions indicate the segments that treat a topic in the text. The level of topicality of a segment in the tree and the length of a segment are indicative of its importance. The segments are described by topic terms. The table of contents also indicates the context in which topic terms are used in texts (e.g. which term can be the subtopic of another term). It also indicates topic shifts and semantic returns at different levels of topicality. In contrast to a bag of words approach of a text, the table of contents representation contains certain discourse relationships that hold between the terms of the texts.
An important step in the construction of this table is the detection of the main sentence topic, on which we focused our proposed methods and evaluation. Additionally, representative topic terms and the level of topicality of a sentence are identified. Our evaluation gives us a number of findings with regard to the thematic structure of a text and to the usefulness of linguistic cues of a sentence topic and comment. With regard to the detection of the main topic of a sentence, a limited number of heuristics found in the linguistic literature on topic and comment are sustained, and the impact or weight of the individual cue or combination of cues can be learned from a training corpus. The probabilistic approaches perform better than the deterministic one. For instance, for the fourth sentence in the text shown in Figure 2, the deterministic algorithm will identify Syrian government as the main sentence topic based on the persistence of government compared to the previous sentence. The probabilistic approaches learn that persistency of a main topic term in combination with a prominent position in the sentence is an important cue for the topicality. In addition, the results indicate that the learned probability distributions are probably portable across text genres and domains. In a limited experiment we processed encyclopedia texts and a Web text by relying on the probability distributions learned from the DUC-2003 corpus.
The best precision of main sentence topic assignment (see Tables 1 and 2) is obtained by the probabilistic classifier that learns various probability distributions of combined features and assigns the most probable class to a new instance by interpolated summation of the individual distributions that apply for the new instance, where the interpolation weights are learned with the Expectation Maximization algorithm. It seems that this classifier more finely detects the weighting of the probability distributions found in the training set. If we have a reliable technique for noun phrase coreference resolution and especially pronoun resolution, we might improve our topic trees. We have developed a tool for coreference resolution based on a fuzzy clustering of the entities found in the text and on semantic knowledge found in WordNet (Mitra et al. Reference Mitra, Angheluta, Jeuniaux and Moens2003). Upon good results for pronoun resolution, we will integrate the tool into the topic segmentation system.
As we could expect from the linguistic studies, left-dislocated adverbial phrases might occasionally act as a topic of a sentence. When manually analyzing the errors made by our best classifier for the DUC-2003 corpus, we could not detect errors caused by the negligence of this cue. In all cases that an adverbial phrase acts as a main sentence topic, it was correctly detected. However, for this classifier about 15% percent of the errors were caused by a faulty assignment of main sentence topic to left-dislocated prepositional phrases (about half of them concern time or place circumstances e.g. Saturday in Figure 3). A considerable part of errors (23%) that are made by the algorithm arises from the fact that we presently take sentences as a primary unit for sentence topic analysis, whereas from a purely linguistic point-of-view it could be argued that topic-comment structures primarily reside at the level of the clause. However, we have tried to keep our approach as generic and portable as possible, and therefore only used a limited amount of shallow language processing. An accurate break-down of a sentence in its constituent clauses would require full parsing. Another cause of errors (about 20%) is that the classifier assigns the main topic to a noun chunk which should be completed by its modifying noun phrase (e.g. thousands in thousands of inhabitants). In one instance the deterministic classifier performed better than its probabilistic counterparts: A noun chunk occurring at the end of a sentence, which was annotated by the human as a main topic and which also occurred in the previous sentence, was only correctly detected by the deterministic classifier. Very few errors (less than 1%) are caused by incorrect part-of-speech tagging or noun phrase chunking. An important problem is finding the topic terms that best reveal the content when displaying the segment descriptors in the table of contents. Currently, our table of contents displays the head of the noun chunk that is designated as main sentence topic. In case this head is part of a collocation or of a proper name, the complete term is shown. Proper name modifiers that are part of the chunk are also shown. The detection of a good descriptive phrase that gives the complete but still condensed information on the topic (as reflected by the Precision-S results) is a difficult task. Our results indicate that we can fairly correctly define the noun chunk that contains the main topic, but our approach is not always good at extracting the right descriptive terms from this phrase, or additional modifiers of the phrase are needed. Automatic recognition of collocations was very helpful, but not sufficient to detect phrases such as pregnancy exposures instead of only exposures, relationship between Accutane and depression instead of solely relationship, or efforts to head off military conflict (Figure 3) instead of only efforts. The inability of our system to identify, for instance, the importance of the contrasting topic descriptions noncooperative games and cooperative games (the system recognizes one topic: games), or simple mobile robots and complex mobile robots (the system recognizes one topic: robots) causes a low Precision-S. The techniques used for identifying collocational compound terms are currently insufficient to identify convenient descriptors. To resolve these problems a better semantic understanding of the text is needed. Other shortcomings of the current descriptors are that they are in the form of a list of topic terms and that they do not make explicit the relationships between topic terms as regular headlines or headings would do when describing a segment. Here, techniques for headline generation that compress sentences or fuse information from different sentences could be investigated.
The deficiency in providing good segment descriptors makes that the constructed tables of contents are merely an organization of topics or keywords in the text, but not yet a real table of contents. We also evaluated the level of topicality, i.e., whether a topic acts in the text as a subtopic of another segment and consequently by defining the parent topic we could establish the hierarchical and sequential relationships between topic segments. For expository texts (e.g. Encyclopedia articles), the construction of the hierarchy and of the sequence of segments is quite correct, because these texts are usually well structured according to topics and subtopics. For narrative texts and especially when the texts contain a lot of speech parts and dialogues, the hierarchical topic segmentation is less reliable, and one can argue whether hierarchical topic segmentation for these texts is a suitable format to condense their content for easy information selection. Some of the DUC news stories are just a collection of unrelated statements in which case it is very difficult to manually and automatically construct a table of contents. For instance, we manually identified two topic levels in document AP880912-0095: One for the main topic statements and one for the other statements. The machine detected levels of topicality of this document that with 54% diverged from the topic levels manually constructed. It is also difficult – especially when dealing with very detailed topics – to distinguish subtopics of a topic from topics that follow each other within the same hierarchical level on the basis of lexical distributional patterns of words. For a further improvement of the performance of the algorithm, we might have to consider additional heuristics such as definiteness of a noun phrase and thematic continuity within a paragraph (Hahn Reference Hahn1990) and possibly to model these phenomena probabilistically. Using additional dictionary knowledge on synonymy, meronymy, hypo- and hypernymy relationships between words – if available – might improve the results of this task, but needs further investigation.
The main contribution of our work lies in a hierarchical segmentation of texts. Our segmentation algorithm relies on discourse patterns of thematic progression in texts. From a linguistic point of view, we have shown that patterns of thematization of rhemes, thematic progression with a continuous topic and thematic progression with derived topics can automatically be detected. An important improvement of our algorithm might be attained through the incorporation of discourse theories on the rhetorical structure of a text as a complementary way of detecting the salience of a sentence or clause, and consequently of its main topic (Marcu Reference Marcu2000).
The table of contents of a text can be used in many text processing tasks, such as text summarization (cf. above), text filtering, indexing and retrieval. They can be usefully integrated in systems that visualize information in small and large screens. Moreover, because a tree-like organization of topic terms indicates the broader or narrower context in which a term is used, it could also be valuable for word sense disambiguation and might help in automatic thesaurus construction (Sanderson and Croft Reference Sanderson and Croft1999), but we need further studies to confirm these assumptions.
6 Related research
Existing text segmentation algorithms usually produce what is called a linear segmentation of the text assuming that the main topics are sequentially organized, e.g. (Hearst Reference Hearst1997; Ponte and croft Reference Ponte and Croft1997; Kan et al. Reference Kan, Klavans and McKeown1998; Choi et al. Reference Choi2000). The aim is to detect topic breaks in a text and not necessarily to zoom in and out on content. The oldest approaches group sentences, sentence blocks or paragraphs based on the similarity of their term vectors, an approach which was first advocated by Prikhod'ko and Skorokhod'ko (Reference Prikhod'ko and Skorokhod'ko1982) and elaborated by Hearst (Reference Hearst, Plaunt, Korfhage, Rasmussen and Willett1993) and Salton (Reference Salton, Allan, Buckley and Singhal1994). The most famous linear segmenter is probably the one of Hearst (Reference Hearst1997). Terms might be selected based on their part-of-speech tag and include noun phrase entities, e.g. (Kan et al. Reference Kan, Klavans and McKeown1998). Newer approaches learn topic breaks from segmented examples, for instance, based on the lexical items, cue words and topicality features that use adaptive language models to detect broad changes of topic, e.g. Beeferman et al. Reference Beeferman, Berger and Lafferty1999). Other approaches assume that a segment is generated by a word cluster composed of an individual topic term and related words, e.g. (Li and Yamanishi Reference Li and Yamanishi2003).
Our innovative topic segmentation algorithm allows detecting the hierarchical and sequential topical segments including semantic returns of a topic at different levels of topical detail. It allows computing the level of topicality of a topical entity or sentence. The number of approaches that hierarchically segment loosely structured or unstructured text is very much limited. An existing hierarchical segmentation algorithm produces a hierarchical clustering of the sentences (Yaari Reference Yaari2000). This approach requires that a subtopic sentence contains the terms or their coreferents of its more general topics, which is not always the case. This drawback might be alleviated by grouping of paragraphs (Salton et al. Reference Salton, Singhal, Buckley and Mitra1996) or segments found by linear topic segmentation (Kan Reference Kan2003) where the last author uses the algorithm of Yaari (Reference Yaari2000). Additionally, clustering also often relies on threshold similarity values for cluster membership, which might be difficult to set across heterogeneous texts. (Marcu Reference Marcu2000) detects the salience of a sentence or clause by analyzing the rhetorical structure of a text based on rhetorical signaling cues, when they are available in the text in a non-ambiguous way. Detection of the hierarchy of topics and subtopics is also accomplished by a knowledge-rich (and therefore domain-dependent) semantic parsing of the text (Hahn Reference Hahn1990).
To detect the topics of a text, lexical chains of topic terms (Morris Hirst Reference Morris and Hirst1991) are often computed per segment (Barzilay Elhadad Reference Barzilay, Elhadad, Mani and Maybury1999: Chali et al. Reference Chali, Kolla, Singh, Zhang, Radev and Teufel2003). The chains are built with the repeated terms or with related terms, and the salience of a topic term can be computed based on the number of members of its chain. Our algorithm combines topic segmentation and detection and can identify the broader or narrower context in which a term is used in the discourse in hierarchically nested text segments. Our approach uses a set of simple linguistic features that are applicable to many domains and possibly across languages. The use of thematic discourse patterns especially with regard to sentence topicality in segmentation and topic detection is a very novel, but promising approach. Despite the extensive literature on the linguistic phenomena, they are seldom taken into account in the design of information systems. Sormunen et al.(Reference Sormunen, Kekäläinen, Koivisto and Järvelin2001) acknowledge the value of thematic textual patterns when ranking documents in information retrieval. Hierarchical topic segmentation is acknowledged to be very valuable for generic and view-point oriented text summarization, text searching and navigation (Zizi Beaudouin-Fafon Reference Zizi and Beaudouin-Fafon1995; Kan et al. Reference Kan, McKeown and Klavans2001; Yang and Wang Reference Yang and Wang2003). It allows zooming in and out on the content of a text, which is very helpful when displaying text on small screens or when skimming large amounts of texts on regular screens. Current approaches that zoom in and out on the content of documents exploit their layout structure of headings, but ignore hierarchical, sequential and semantic return relationships between topical segments that can be found in unstructured natural language text (Yang and Wang Reference Yang and Wang2003), or allow just selecting text based on key terms or on summary sentences that contain terms that are highly weighted because of their high frequency in this text and low frequency in a reference corpus (Buyukkokten et al. Reference Buyukkokten, Garcia-Molina and Paepcke2001). The work of these last authors shows the need for zooming in and out into textual content when searching and navigating in information via small screens. Compared to their work, our method allows showing key terms in context (e.g. the table of contents of a text indicates that the subtopic prevention is mentioned in the context of the topic AIDS, while the subtopic treatment is mentioned in the context of the topic diabetes), which can be exploited when precisely searching for information passages or sentences that are relevant for a query, or when navigating the information contained in a text.
7 Conclusions
In this article we have presented a novel approach to topic segmentation based on generic linguistic patterns of sentence topic and comment and of thematic progression across sentences. Each segment is described by its start and end position in the text and by descriptive key terms. The segment descriptions are organized in a table of contents that indicates the hierarchical, sequential and semantic return relationships between segments. Our main contribution is the design of algorithms for detecting the main topic of a sentence – both from a deterministic and probabilistic perspective – and for detecting patterns of thematic progression across sentences. The topic segmentation gives also valuable information, about the salience of a text segment and its topic terms, and in case of a hierarchical segment structure on the broader and narrower context of a topic. In the future we want to expand the proposed techniques with other valuable approaches for content recognition of texts such as coreference resolution and reliance on the rhetorical relations between text spans, when they are signaled in the text. Finally, we could further research the automatic generation of concise and informative phrases that describe the topical segments and that better correspond to the headings of traditional tables of contents.
Acknowledgments
This research was sponsored by the Institute for the Promotion of Innovation by Science and Technology in Flanders (IWT), Belgium. We thank Rik De Busser and Isolde De Scheemaeker for annotating the corpora and their valuable comments. We are also grateful to the anonymous reviewers for their very relevant remarks.
