SegGen: A Genetic Algorithm for Linear Text Segmentation

1 Introduction

The purpose of automatic text segmentation is to identify the most important thematic breaks in a document in order to cut it into homogeneous units, disconnected from other adjacent parts [Salton et al., 1996]. More precisely, segmentation partitions a text by determining boundaries between contiguous segments related to different topics, defining so semantically coherent parts of text that are sufficiently large to expose some aspect of a given subject. Thematic segmentation of texts can also be seen as a grouping process of basic units (words, sentences, paragraphs...) in order to highlight local semantical coherences [Kozima, 1993]. The granularity level of the segmentation depends on the size of the units.

The increasing interest in text segmentation is mainly explained by the number of its applications such as text alignment, document summarization, information extraction, or information retrieval [Baeza-Yates and Ribeiro-Neto, 1999]. Text segmentation can be indeed very useful for these tasks by providing the structure of a document in terms of the different topics it covers [McDonald and Chen, 2002].

Many segmentation methods have been proposed and we focus here on the most general and significant methods that rely on statistical approaches such as Text Tiling [Hearst, 1997], C99 [Choi, 2000], DotPlotting [Reynar, 2000] or Segmenter [Kan et al., 1998]. These methods perform an analysis of the distribution of the words in the text, in order to determine the thematic changes by means of lexical inventory variations in fixed size windows and thus create boundaries in the text where the local cohesion is the lowest.

In this paper, we introduce SegGen a genetic algorithm to achieve a statistical linear segmentation of texts. Section 2 presents the main motivations of our work. Our segmentation algorithm is described in section 3. Then, section 4 describes an experimental study of the algorithm in order to tune its parameters. Finally, section 5 evaluates SegGen by comparing it with other segmentation systems.

2 Motivations and PreliminaryWorks

In most of existing segmentation approaches, the relationships between sentences are usually very local. For example, the methods addressing segmentation by means of lexical chains 1 mainly use the repetitions of the terms in order to define thematic boundaries. More precisely, these methods cut the texts where the number of lexical chains is minimal. Nevertheless, the context of these multiple occurrences is not addressed neither the significance of simultaneous lexical chains at a given position in the text.

According to the preceding remark, we attempted to propose an alternative approach to the segmentation of texts by taking into account a more complete view of the texts. In [Bellot, 2000], P. Bellot has shown that there exists a strong relationship between clustering and text segmentation. His hypothesis states that it is possible to set a boundary between two adjacent sentences belonging to two different semantic classes. This assumption seems too strong since text segmentation not only depends on the similarity of the sentences, but must also consider their layout in the text. Indeed, discourse structures of documents may be very diverse and a part of a text related to a particular topic may contain sentences deviating somewhat from it. These sentences are likely to be classified differently from their neighbors. However, this certainly does not imply that a boundary has necessarily to be set there. Moreover, this assumption is too dependent on the chosen clustering mechanism, no existing clustering method being fully reliable.

1 Lexical chains are formed between two occurrences of a same term [Galley et al., 2003] [Utiyama and Isahara, 2001] and occasionally between synonyms and terms having statistical associations such as generalization/specialization or part-whole/whole-part relationships [Morris and Hirst, 1991]

However, we were convinced that a preliminary clustering could provide a more complete view of the sentences relations. Therefore, we have defined a first segmentation method, called ClassStruggle, that uses an initial clustering of the sentences of the text based on their similarity, in order to have a global view on their semantic relations. In this approach, the resulting clusters evolve by taking into account their proximity in the text. Considering the clusters as topics of the text, ClassStruggle performs a linear traversal of the document in order to determine the most appropriate class assignment for each sentence, depending on their context of occurrence. This process goes on as long as modifications occur in the clusters. Finally, boundaries are created between sentences belonging to different classes. Due to a lack of space, ClassStruggle cannot be fully described but is nevertheless used for the evaluation of SegGen (section 5).

According to the definition of text segmentation by Salton [Salton et al., 1996], the internal cohesion of the segments and their semantical proximity with their neighborhood constitute important factors of an efficient segmentation method. But, in the case of a sequential creation of boundaries, these characteristics cannot be computed since, when a boundary is created, the concerned segment is not yet entirely delimited. Therefore, sequential methods need to introduce a concept of window in which cohesion measures can be achieved. Nevertheless, it is difficult to determine the size of the window: a too short window may lead the algorithm not to consider some cohesion clues and a too long one may take into account some repetitions of terms that should indeed not be associated, since used in different contexts.

From this second remark, we decided to consider an approach where the boundaries are considered globally. Based on an evaluation of the possible segmentation schemes, such a method would have a complete view of the text and would be able to compute coherence without using windows. Considering the segmentation problem as a combinatorial problem, SegGen is an evolutionary algorithm that evaluates the segmentations of the whole text rather than setting boundaries incrementally. The lack of knowledge on the structure of the text or on the number of segments to create, induces a huge search space and leads us to consider a genetic algorithm to cope with complexity.

3 SegGen: a Genetic Algorithm for Text Segmentation

Inspired by the mechanisms of natural selection and evolution, genetic algorithms [Holland, 1975; Goldberg, 1989] have been successfully applied to the resolution of numerous combinatorial optimization problems. The general principle of genetic algorithms consists in managing a population of individuals, which represents potential configurations of the problem to be solved. Genetic algorithms have been used for several text mining purposes (such as document clustering [Raghavan and Agarwal, 1987]).

As mentioned above, text segmentation can be viewed as finding parts of text with strong intrinsic relationships, disconnected from other adjacent parts. Therefore, we consider text segmentation as a multi-objective problem with two criteria to optimize: the internal cohesion of the segments and the dissimilarity between adjacent ones. As usual for multiobjective problems, these two criteria are negatively correlated. Indeed, the internal cohesion tends to increase with the number of boundaries whereas the dissimilarity between adjacent segments tends to decrease with it. Following the multi-objective optimization principles, we consider the objective functions separately in order to allow our algorithm to preserve enough diversity in the search process and to extract good segmentation proposals.

Our SegGen algorithm is a variant of the "Strength Pareto Evolutionary Algorithm" (SPEA) [Zitzler, 1999], an elitist algorithm for multi-objective problems. The method uses an external archive ¯ P to memorize the non-dominated 2 individuals w.r.t. both criteria and a current population Pt. Individuals are selected from these two populations in order to generate new individuals thanks to genetic operators. These new individuals constitute the next Pt and are used to update ¯ P . ¯ P constitutes, at the end of the process, a set of potential segmentations of the text. The algorithm has then to extract an unique solution from this set (see section 3.5). All documents do not need the same number of generations to reach a satisfactory segmentation. Therefore, our stop criterion corresponds to a stagnation of the population evaluation.

Algorithm 1 Pseudo-code of the Seggen algorithm

Similarities computation and populations initialization;

while Stop Criterion not yet encountered do

¯

• Fitness evaluation of each individual of Pt ∪ P ;
• Selection, Crossover, Mutation;

¯

• Replacement of Pt by the set of new individuals;
• Update of P w.r.t. the non-dominated individuals;

end while

¯

Selection of the best individual in P .

3.1 ProblemRepresentation

Given a text of ns sentences, the individuals are binary vectors ⃗x of (ns - 1) elements xi; xi = 1 indicates that there is a boundary between sentence i and i + 1. For an individual ⃗x, we consider two evaluation criteria: C(⃗x) ∈ [0, 1], which corresponds to the internal cohesion of its segments, and D(⃗x) ∈ [0, 1], which evaluates the dissimilarity between its adjacent segments. Our optimization problem consists in approximating the set of optimizers O:

2 An individual is dominated if there exists an other individual in the populations having a better score on one criterion and at least the same score on the others.

According to this definition, the optimum is not a unique solution but a set of compromises, called the Pareto Front.

3.2 Initial Population Generation

Initial solutions are randomly and incrementally created but, in order to start with an heterogeneous population, individuals are created w.r.t. the boundaries of others. The size of the population is determined empirically (see section 4).

Genetic algorithms may converge easier if the individuals of the initial population are closer to the optimum [Goldberg, 1989]. Therefore, we tried to insert in the population an individual created by an external segmentation method. Experiments w.r.t. this strategy will be described in section 5.

3.3 Fitness Function

Two criteria are used to evaluate the individuals: internal cohesion and external dissimilarity. Both use similarities between sentences computed beforehand. According to the vectorial representation of the sentences, inspired by the vectorial model [Baeza-Yates and Ribeiro-Neto, 1999] (i.e., a vector of weights w.r.t. the set of meaningful terms), the similarity sim(s1, s2) between two sentences s1 and s2 is computed with a cosine measure:

where t is the number of meaningful terms, wi,sj the weight of the term i in the sentence sj.

Internal Cohesion

The internal cohesion of segments can be computed in two different ways by using the sentence similarities. First, it can be seen as the average internal cohesion of segments:

with nbseg being the number of segments of the individual, segi the segment i of the individual, SumSim(segi) the sum of the sentence similarities of segi and NbCouples(segi) the number of possible couples of sentences in segi.

Since the distribution of similarities in the text is not likely to be homogeneous, one may probably find very cohesive small areas. In this case, individuals representing small segments would have a really greater chance to obtain a good score of cohesion. A normalization of the score could be performed according to the size of the segments but may induce some bias. Therefore, we propose to realize the sum of each cohesion divided by the number of couples:

In presence of long segments, the number of couples is greater than if all the segments have the same size (for example, (n+1 2 ) + (n-1 2 ) > (n2 ) + (n2 )). Therefore, individuals having a lower variance in their segment size will be preferred. However, this bias is limited by the second objective function.

Dissimilarity Between Adjacent Segments

The similarity of a segment w.r.t. its successor is computed as follows:

with segi being a segment, sj a sentence, S(segi) the set of the sentences of the segment segi and |S(segi)| the cardinality of this set. This formula allows us to define the computation of the general dissimilarity between adjacent segments in an individual:

with nbseg being the number of segments of ⃗x and segi a segment of this individual.

Fitness of the Individuals

Following [Zitzler, 1999], the computation of the fitness value of each individual is realized in two steps. A hardness value H is given to each individual of the external archive ¯ P. This value is computed according to the number of individuals of Pt (the current population) that an element ⃗x ∈ ¯ P slightly dominates on both objective functions:

¯

The fitness value of an individual ⃗x ∈ P is equal to the inverse of its hardness value: F (⃗x) = 1 H(⃗x) . The fitness value of an individual ⃗y ∈ Pt is computed by summing the hardness scores of individuals ⃗x of ¯ P dominating ⃗y:

This fitness function, allowing us to select individuals for mutation and crossover, aims to diversify the search (from ¯ P point of view).

3.4 Exploration Operators

Three operators are used in the evolution process: selection, crossover and mutation (see fig.1). At each generation, the algorithm select NbIndiv individuals and produces NbIndiv new individuals to maintain a fixed size of population.

¯

The individuals are selected from P and Pt according to their fitness value by "roulette wheel" [Holland, 1975]. This method first sums all the fitness scores of the individuals. Each individual gets a probability of selection equal to their percentage of contribution in this sum.

Among the selected individuals, while the number of NbIndiv new individuals has not been reached yet, two parents are randomly chosen in order to produce two new individuals (the offsprings) by crossover. Here, we use a classical single point crossover: a position is randomly chosen in the parents and the two corresponding parts of the parents are exchanged to form two children.

Two different mutation operators are applied to these children: a mutation that replaces a parent by a randomly produced individual with a probability Pms and a mutation used with a probability Pmc that shifts a boundary of the individual to the next or the previous sentence. Both mutation operators appear complementary since the first enables to explore new areas while the second refines the existing solutions.

3.5 Extraction of a Solution

¯

When the algorithm meets the stop criterion, the archive P contains a set of potential segmentations. We have then to extract the best individual from this set. This choice can be guided by an aggregation of both objective functions:

The extracted solution is the one having the best score w.r.t. this aggregation function. The coefficient α weights the second objective compared to the first. It acts upon the features of the final segmentation of the text and is thus tuned experimentally in section 4.

4 Experiments

4.1 Experimental Process

The experiments were carried out on articles from the corpus of texts of the international conference TREC-1 [Harman, 1993], which includes full articles from the Associated Press published between 1988 and 1989. Those articles have been gathered to form different sets of 350 documents. Separations between articles constitute the segmentation of reference. These tests based on concatenated articles may be less conclusive than tests performed on more homogeneous texts but this evaluation seems to be the most commonly used in the literature (see for example [Choi, 2000]) and this kind of boundaries appears to be difficult enough to recognize. According to this principle, four corpuses have thus been created in order to test the behavior of the algorithmwith regards to different kinds of text. We note T (ns, nb) a corpus composed by texts of ns sentences and an average of nb boundaries.We use the corpuses T(50, 2), T(50, 4), T(100, 4), T(100, 8). The segmentation algorithms are evaluated w.r.t. three criteria: the precision (number of exact boundaries found / number of boundaries found ), the recall (number of exact boundaries found / number of boundaries of the reference) and a criterion, called WindowDiff [Pevzner and Hearst, 2002], which takes into account the number of boundaries between two sentences separated from a distance k.

where b (xi, xj) is the number of boundaries between i and j in a segmented text x containing N sentences, ref corresponds to the segmentation of reference and hyp the one found with the method to evaluate. The size k of the window has to be set to half of the average true segment size. This criterion enables to consider the near-misses.

4.2 Parameters Tuning

The quality of the population is evaluated with a function Eval( ¯ P) that returns the score of the best individual in ¯ P w.r.t the aggregation function (section 3.5):

¯

¯

A study of different P, issued from executions of SegGen on multiples texts after various numbers of generations, has shown that a weight α = 6 enables the selection of a good individual in the majority of cases. The following tests will use this value.

In order to adjust the probabilities of mutation Pms and Pmc, SegGen has been ran for each couple of (Pms, Pmc) between (0, 0) and (1, 1), using a step of 0.2 for each. These experiments have been carried out on the set of 350 documents of the corpus T(50, 2), 10 times each in order to limit random variations. The number of individuals in the population is set to 10, value which appears to provide good results. Results of figure 2 are averages of the population evaluation function Eval( ¯ P) on these multiple executions.

¯

The figure 2 shows the evolution of Eval( P) according to some different combinations of mutation probabilities 3 . We may first notice the influence of both mutation operators since the curves that corresponds to a single mutation operator are the lowest. The couple Pms = 0.4 and Pmc = 0.8 seems to be the best compromise.

3 The legends correspond to the values Pms, Pmc (times 100) and are given in the same order than the obtained score at the end of the process (the greatest is the best).

A study on the number of individuals NbIndiv has shown that values greater than 10 allow the algorithm to converge more quickly in term of generations but induce a greater computation cost in term of evaluation. For instance, on the corpus T(50, 2), with NbIndiv = 20, the algorithm needs only 150 generations to reach the score of evaluation of 6.04 against 250 with 10 individuals. However, the number of generated individuals is greater (250 × 10 < 150 × 20). On the other hand, a lower number of individuals leads to the opposite problem, the number of generations is too high, which implies a loss of time.

Concerning the stop criterion, long texts may need more time to be segmented but the quality of segmentation can be the same than for shorter ones. A value of 100 iterations without any improvement seems to be sufficient enough to reach a good solution.

Concerning the value of the α parameter used in the aggregation function in order to extract a good individual from ¯ P , we have to remark that the first objective function C favorizes individuals that generate a lot of boundaries, small segments having more chances to be cohesive. At the contrary, the second objective function D is in favor of individuals having few boundaries, since long segments have more chances to own sentences faraway the following. The parameter α has thus an influence on the number of detected boundaries (figure 3). The best results according to WindowDiff are obtained around α = 5. Nevertheless, an higher value enables to obtain a better precision and a lower a better recall. This value may be set between 4 and 6 w.r.t. the frequency of the required segmentation.

5 Evaluation

5.1 Experimental Process

In order to evaluate the methods, we use benchmarks created similarly to those described in section 4. Of course, in order not to skew the results, the selected articles are different from those used for tuning purposes. SegGen has been compared to the following methods to evaluate its efficiency:

• TT: TextTiling 4 [Hearst, 1997] is based on the distribution of the terms in the text, according to several criteria (number of common words, new words, active chains).
• C99: C99 5 [Choi, 2000], which seems to be the most efficient existing approach, uses a "local ranking" by determining, for each pair of textual units, the number of surrounding pairs having a lower similarity.
• CS: ClassStruggle, mentioned in section 2, is based on a clustering process to segment the texts.

As mentioned in section 3.2, we tried to improve the initial population by inserting a good solution. Therefore, two versions of the algorithm, S5 and SC5, have been evaluated. In SC5, a segmentation scheme, computed by C99, has been inserted in the initial population. Both use a coefficient α = 5 (see section 4.2).

Since SegGen uses stochastic parameters in mutation and crossover, the range of error has been evaluated by computing the standard deviations, on ten executions, of the average of scores obtained on each corpus. Standard deviation of WindowDiff is located around 0.015, of recall around 0.01 and of precision around 0.012. These values are really low w.r.t. the ranges of scores given in table 1.

5.2 Results

According to results given in table 1, ClassStruggle, having a more complete view of the relations of the sentences thanks to the use of a clustering process, is globally more efficient than C99 and TextTiling. However, its incremental process reduces its ability to take into account the segment cohesion and the similarity between adjacent segments. SegGen overrides this problem and obtains really better results for all accuracy criteria, especially on corpuses that do not have a lot of boundaries to retrieve (i.e. T(50, 2) and T(100, 4)). TextTiling and C99 seem to have difficulties to adapt themselves w.r.t the number of boundaries to retrieve, the length of the text has a great impact on their number of detected boundaries. SegGen seems to better follow these variations.

However, on corpora that have a lot of boundaries to retrieve, i.e. T (50, 4) and T (100, 8), SegGen seems to have difficulties to product individuals sufficiently segmented. This is due to the fact that good individuals with a lot of boundaries are more difficult to find than others. The insertion of a good individual in the initial population (SC5), obtained by C99, seems to solve this problem. C99, providing segmentations with a lot of boundaries, helps SegGen to find solutions when the search space is huge.

Additionally, a Student t-test 6 has shown that these differences are really significant with a 99% confidence rate, all of the values being higher than the p-value 2.57.

4 Available on: www.sims.berkeley.edu/˜hearst/.

5 Available on: www.freddychoi.me.uk.

6 The 99% Student t-test is based on the average, the standard deviation and the cardinality of a set of runs. It uses a p-value equal to 2.57 to insure with a rate of confidence of 99% that the difference in means of two sets is significant.

6 Conclusion

The experiments have shown that our approach appears to realize a really more accurate segmentation of the texts than existing incremental methods. Moreover, SegGen seems to adapt itself much better than other methods according to the number of boundaries to retrieve.

Nevertheless, the fitness function can be improved, in particular by a more sophisticated calculus of similarity, overpassing the sole repetitions of words. Finally, SegGen will be at term integrated as a preliminary step in an ongoing project of information retrieval that aims to furnish composite documents as responses to user's queries.

Acknowledgments

This work was supported by "Angers Loire Metropole".