Olivier Ferret
email: [ferret@limsi.fr

Brigitte Grau
email: grau]@limsi.fr

A bootstrapping approach for thematic analysis

Thematic analysis is important for a lot of applications dealing with texts, such as text summarisation or information extraction. But it can be done with a great precision only if it relies on structured knowledge, which is difficult to produce. In this paper, we propose using bootstrapping in order to solve this problem: a first thematic analysis based on a weakly structured source of knowledge, a collocation network, is used for learning explicit topic representations that then support a more precise and a more reliable thematic analysis.

Introduction

Applications on large text bases, as information retrieval systems, have to deal with topic identification and tracking if they aim at improving their results by presenting retrieved texts in a better way, by highlighting the most relevant passages or the thematic structure of the texts. Information extraction systems would also benefit of a precise topic identification in order to delimit a context for the searched information that gives a mean to reduce ambiguities. A problem such systems have to face consists of detecting thematically coherent pieces of text and identifying their topic, without limitation about the topics that are likely to be found. Detecting coherent pieces of text refers to text segmentation, and when it is applied to large text collections, segmentation method are based on lexical knowledge [START_REF] Hearst | TextTiling: Segmenting Text into Multi-paragraph Subtopic Passages[END_REF][START_REF] Salton | Automatic Text Decomposition Using Text Segments and Text Themes[END_REF] or on non specialized knowledge as collocation networks, thesaurus or dictionary [START_REF] Kozima | Text Segmentation Based on Similarity between Words[END_REF] when dealing with narratives. However, these methods cannot identify topics as this problem requires specialized knowledge. In order to develop methods keeping the same coverage, such knowledge bases have to result from a learning module. The main works in this field have been realized for the TDT (Topic Detection and Tracking) task and are generally based on a probabilistic approach trained on a tagged corpus as in [START_REF] Bigi | Detecting topic shifts using a cache memory[END_REF][START_REF] Beeferman | Statistical Models for Text Segmentation[END_REF]. However, we wanted to develop a method without constraints about resources to possess or to build manually, other than having texts and a general lexicon that is quite easy to obtain. Thus, our system implements an incremental clustering process to learn topic representation. These representations are called semantic domains, and are made of weighted words [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF]. Domains result from the aggregation of similar thematic units, made of a set of words. This units are provided by a first segmentation method that relies on lexical cohesion computed from a collocation network. In a further step, domains are used to develop a topic analyzer [START_REF] Ferret | A Topic Segmentation of Texts based on Semantic Domains[END_REF], that is more precise in its segmentation capacity than the first process, and, overall, that is able to identify topics and track them along the texts if they are not linearly developed. Thus, the approach we propose consists of learning a first kind of knowledge from texts and then using this knowledge to develop a better thematic analysis. We claim that it is possible to improve knowledge and processes in an incremental way: a weakly structured knowledge and a shallow analysis both lead to bootstrap a better analysis by providing more structured knowledge. By applying this method, we are able to go towards in-depth analysis of text, while keeping the great coverage of word-based methods. In this paper, we detail the implementation of this process by the ROSA system and we will show its performances on a classical task of evaluation for topic segmentation algorithms in order to give evidence of the contribution of such an approach.

Overview of the ROSA system

The ROSA system (see Figure 1) has two main components: SEGCOHLEX [START_REF] Ferret | How to thematically segment texts by using lexical cohesion?[END_REF], which segments texts by relying on lexical cohesion and SEGAPSITH, that incrementally learns topic representations from the most cohesive segments [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF] from SEGCOHLEX and use them for supporting another thematic analysis module

SEGCOHLEX

Segmentation Module text segments

SEGAPSITH Segmentation Module

Learning Semantic Domain Module

Collocation network

Semantic domains

ROSA

Figure 1: The architecture of the ROSA system SEGCOHLEX only uses a general knowledge base that is automatically built, the collocation network. This kind of knowledge allows the development of a process that only delimits text segments with rather average performances and does not identify topics. However, this rough analysis generates text segments made of weighted words that are aggregated altogether when they refer to the same topic. This aggregation process produces representations of semantic domains, also made of weighted words. This new knowledge, more precise relative to the kind of analysis, allows the elaboration of a more competent segmentation module, able to identify topics and to follow topic developments. The performances of this second module are also better than SEGCOHLEX performances, as it is grounded on more structured knowledge. We will also show that grounding SEGAPSITH on SEGCOHLEX, i.e. on a first segmentation process, is better than learning domains from the whole texts.

SEGCOHLEX

The topic segmentation of SEGCOHLEX, as the one of SEGAPSITH, handles texts that have been pre-processed to only keep their lemmatized content words (adjectives, single or compound nouns and verbs). This segmentation is based on a large collocation network, built from 24 months of Le Monde newspaper, where a link between two words aims at capturing semantic and pragmatic relations between them. The strength of such a link is evaluated by the mutual information between its two words. The segmentation process relies on these links for computing a cohesion value for each position of a text. As in Kozima's work, this computation operates on words belonging to a focus window that is moved all over the text. It assumes that a discourse segment is a part of text whose words, referring to the same topic, are strongly linked to each other in the collocation network and yield a high cohesion value. In contrast, low cohesion values indicate topic shifts. Segments are finally delimited by an automatic analysis of the resulting cohesion graph (see [START_REF] Ferret | How to thematically segment texts by using lexical cohesion?[END_REF]) for details about the whole process and its evaluation). Such a method leads to delimit small segments, whose size is equivalent to a paragraph, i. e. capable of retrieving topic variations in short texts, as newswires for example. Nevertheless, that does not mean that our topic segmentation aim at retrieving paragraph marks. These kinds of marks are often non relevant to segment texts in their different topics. Table 1 shows an extract of the words belonging to a cohesive segment about a dedication of a book.

Semantic Domain learning in SEGAPSITH

Learning a semantic domain consists of aggregating all the most cohesive thematic units that are related to a same subject, i. e. a same kind of situation. We only retain segments whose cohesion value is upper than a threshold, in order to ground our learning on the more reliable units. Similarity between thematic units is evaluated from their common words. Each aggregation of a new TU increases the system's knowledge about one topic by reinforcing recurrent words and adding new ones. Weights on words represent their importance relative to the topic and are computed from the number of occurrences of these words in the TUs. Units related to a same topic are found in different texts and often develop different points of view of a same type of subject. To ensure a better similarity between them, SEGAPSITH enriches a particular description given by a text segment by adding to these units those words of the collocation network that are particularly linked to the words found in the segment. Table 2 gives an extract of the words added to the segment of Table 1. This method leads SEGAPSITH to learn specific topic representations (see Table 3) as opposed to [START_REF] Lin | Robust Automated Topic Identification[END_REF] for example, whose method builds general topic descriptions as for economy, sport, etc. Moreover, it does not depend on any a priori classification of the texts. We have applied the learning module of SEGAPSITH on one month (May 1994) of AFP newswires, corresponding to 7823 TUs. The learning stage has produced 1024 semantic domains. Table 1 shows an example of a domain about justice that gathers 69 TUs. The segmentation module of SEGAPSITH only works with the most reliable of these domains. Thus, we have selected those whose number of aggregations is upper than 4. Moreover, we have selected in these 193 domains words whose weight is greater than 0.1, as below this limit a lot of words only represent noise.

The topic segmentation in SEGAPSITH

In accordance with works on discourse segmentation as (Grosz and Sidner, 1996), this module processes texts linearly and detects topic shifts without delaying its decision, i.e. by only taking into account the data extracted from the part of text already analyzed. A window that delimits the current focus of the analysis is moved over the text to be segmented. The segmentation algorithm locates topic shifts by detecting a significant difference between the set of domains selected for each position of the text -this set defines the topic context of the window -and the set of domains associated with the segment that is currently active at this time, which defines the topic context of the segment.

Topic contexts

A topic context aims at characterizing the entity it is associated with from the thematic point of view and is represented by a vector of weighted semantic domains. The weight of a domain expresses the importance of this domain with regard to the other domains of the vector. A context contains several semantic domains because domains are rather specific. Thus, having several of them that are close to each other allows us to cover a larger thematic field. Secondly, SEGAPSITH handles representations made of words whose meaning may be ambiguous and refer to different topics. By putting several domains into a context, we cope with ambiguity without having to explicitly choose one interpretation.

Topic context of the focus window

The topic context of the focus window is made of the N th semantic domains that are activated the most strongly by the words of the window, N being a fixed size for all the contexts. The activation process is equivalent to a one-step activity propagation based on the number and the weight of the words common to the window and a domain. The activation value of a semantic domain is given by: ) ( ) , ( ) (

j j i j i w nbOcc w dom ght w dom activ ⋅ ∑ = (1)
where the first factor is the weight of the word w j in the domain dom i (see [START_REF] Ferret | A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts[END_REF] for more details) and the second one is the number of occurrences of w j in the focus window. The weight of a domain in this context is then equal to its activation value.

Topic context of a segment

The topic context of a segment contains the semantic domains that were activated the most strongly when the focus window was moving in the segment space. This is achieved by combining the contexts associated with each position of the focus window inside the segment (see Figure 2).

⋅ + ⋅ = + β α (2)
with Cw, the context of the window, Cs, the context of the segment and wght(dom i ,Cx,t), the weight of the domain dom i in the context Cx for the position t. The results we present in section 6 were obtained with α(t)=1 and β(t)=1. These functions are a solution halfway between a fast and a slow evolution of the context of segments. The context of a segment has to be stable because if it follows too narrowly the thematic evolution given by the context of the window, topic shifts could not be detected. However, it must also adapt itself to small variations in the way a topic is expressed when progressing in the text in order not to detect false topic shifts. After weight reevaluation, the joined domains are sorted in decreasing order of weight and finally, the N th first of them are selected for building the new version of the segment context.

Similarity of a window context and a segment context

In order to determine whether the content of the focus window is thematically coherent with the currently active segment, the topic context of the window is compared with the topic context of the segment. This comparison is achieved using a similarity measure between the two contexts taking into account the following four factors (see ( 4)):

• The significance of the domains shared by the two contexts (dom c ) with regard to those of the window (C w ) in terms of weight;

• The significance of the domains shared by the two contexts (dom c ) with regard to those of the segment (C s ) in terms of weight;

• The significance of the number of domains shared by the two contexts with regard to the size of contexts. This ensures that a high similarity is not found with only a few common domains having a very high weight (term p/N in ( 4));

• The difference in order among the domains shared by the two contexts. This difference is given by:

p N Cs dom rank Cw dom rank Cs Cw rankDiff p c c c ⋅ - ∑ - = = ) 1 ( ) , ( ) , ( ) , ( 1 (3)
with p, the number of common domains, dom c , one of these common domains and rank(dom c ,Cx), the rank of this domain in the context Cx. The sum of the rank differences in the two contexts is normalized by an upper bound assuming that the difference in rank is maximal (N-1) for each common domain. These four factors are combined by using a geometric mean (the four terms that represent them in (4) appear in the same order): The last term is the complement of the fourth factor, as two contexts are more similar if they share domains in the same order. Two contexts are similar if the value of the similarity measure is above a fixed threshold, equal here to 0.5.

4 1 4 1 1 1 1 1 )) , ( 1 ( ) , ( ) , ( ) , ( ) , ( ) , (       - ⋅ ⋅             ∑ ∑ ⋅ ∑ ∑ = = = = =

Cs

Topic shift detection

The basic algorithm that detects topic shifts computes the similarity between the context of the window and the context of the current segment at each position of a text. If this value is lower than a fixed threshold, a topic shift is assumed and a new segment is opened. Otherwise, the active segment is extended up to the current position. This basic algorithm assumes that the transition phase between two segments is punctual. Because such a precision is not achieved, it must in fact rely on a short delay before deciding that the active segment really ends and similarly, before deciding that a new segment with a stable topic begins. Thus, the segmentation algorithm takes the form of an automaton (see Figure 3) whose transitions between its four states are controlled by three parameters:

• The current state of the algorithm;

• The similarity between the context of the focus window and the context of the current segment: Sim or non Sim;

• The number of successive positions of the focus window for which the current state stays the same: confirmNb, which must be above the T confirm threshold for going away from the states NewTopicDetection and EndTopicDetection. The usual processing of a segment starts with the OutOfTopic state, after the end of the previous segment or at the beginning of the text. As soon as the set of semantic domains of the focus window does not change too much between two successive positions, the topic segmenter enters into the NewTopicDetection state. The InTopic state can then be reached only if the same stability among the domains of the window context is found for the next confirmNb-1 positions. Otherwise, the segmenter assumes that it is a false alarm and returns to the OutOfTopic state. The detection of the end of a segment is symmetrical to the detection of its beginning. The segmenter goes into the EndTopicDetection state as soon as the content of the window context begins to significantly change between two successive positions; but the transition towards the OutOfTopic state is done only if this change is confirmed for the confirmNb-1 next positions. This general algorithm is completed by two specific mechanisms. The first of them takes into account the fact that several segments of a text may refer to the same topic, which is interesting to detect for making the structure of a text explicit. Hence, when the topic segmenter goes from the NewTopicDetection state to the InTopic state, it first checks whether the current context of the new segment is similar, according to (4), to one of the contexts of the previous segments. If such a similarity is found, the new segment is linked to the corresponding segment and it takes the context of this one as its own context. It assumes that the new segment continues to develop a previous topic.

NewTopic

The second mechanism is related to the OutOfTopic state. When the topic segmenter stays in this state for too long (10 positions of the focus window in our experiments), it assumes that the topic of the current part of text is not represented among the available semantic domains and creates a new segment with an unknown topic that covers all the positions concerned. Of course, this mechanism can not separate several connected segments of this kind but it allows us to segment texts without having all the topic representations that should be necessary.

Experiments

Qualitative results and discussion

A first qualitative test of the second segmentation method was done with a small set of texts and without a formal protocol as in [START_REF] Passonneau | Discourse Segmentation by Human and Automated Means[END_REF]. We have tested several range of values for the different parameters of the method and have found that for the kind of texts as the one given in Figure 4, the best results are obtained with a size of 19 words for the focus window and a value of 3 positions for the confirmNb parameter. Furthermore, results are rather stable around these values. Figure 4 shows the value of the similarity measure between the context of the focus window and the context of the current segment for each position of the given text. The two topic shifts, from the Miss Universe topic to the terrorism topic and then the return to the Miss Universe topic, are clearly detected through significant falls of the similarity values (positions 62-63 for the first et 89 to 91 for the second; these shifts are marked in bold in the text). On the other hand, the method misses the last topic shift (from the Miss Universe topic to the demonstration topic) because it is expressed very shortly and not in a very specific way. Note that in the text, the foreseen topic shifts, marked by (<ST>, </ST>) tags do not correspond to paragraph boundaries.

<ST> An 18 year old Indian model, Sushmita Sen, caused a surprise on Sunday in Manilla when winning the Miss Universe 1994 title ahead of two South-American beauties, Miss Colombia, Carolina Gomez Correa, and above all Miss Venezuela, Minorka Mercado, who appeared as favorite in the competition. The young Indian, a brown beauty, hazel eyed and 1.75 meters tall, is the first candidate of her country to win this title. She succeeds to Miss Porto Rico, Dayanara Torres, 22, who gave her her crown in front of a television hearing estimated to six hundred million people all over the world. Among the six finalists also appeared Miss United States, Frances Louis Parker, Miss Philippines, Charlene Gonzales, and Miss Slovak Republic, Silvia Lakatosova. The new miss was chosen among a group of ten finalists that also included the representatives of Italy, Greece, Sweden and Switzerland. </ST> <ST> A few hours before the ceremony, a man was killed by the explosion of an appliance he carried, at about one kilometer from the Congress Center where the beauty competition was being held, in front of the Manilla bay. The police was not immediately able to establish if this incident was in relation with this competition. On Thursday, a weak-power craft bomb had exploded in a garbage can of the congress center without any damages. </ST> <ST> The new Miss Universe, who won more than 150,000 Dollars in different prizes, declared that she intended to do theater, publicity or writing. However, her most cherished wish, she assured, was to meet Mother Teresa because she was "a perfect example of a person totally devoted, unselfish and completely involved". The analysis of this example also illustrates two important characteristics of our method. As it makes use of an explicit representation of topics, it allows us to recognize that two disconnected segments are related to the same topic, as it is done here for the segments 1 and 3 about the Miss Universe topic. Our method also segments texts without having an exact representation of the topics of the texts. Thus, the newswire above was segmented without having a semantic domain related to beauty competitions. This topic was represented here by only one of its dimensions, competition, through a set of domains about sport competitions. More generally, as a context is a set of domains, a topic representation can be dynamically built by associating several domains related to different dimensions of this topic. If we now compare the results given by SEGAPSITH and SEGCOHLEX when analyzing the same text, we see in Figure 5 that SEGCOHLEX detects 6 small units, made of few words, within the first part of the text (until the 52 nd word), where SEGAPSITH only finds one segment. The boundaries of its main segment (words 53 to 80) recognized by SEGCOHLEX are also less precise. When evaluating SEGCOHLEX [START_REF] Ferret | How to thematically segment texts by using lexical cohesion?[END_REF], we have shown that this Topic shift threshold method was comparable to the other works in the field and can be considered as a baseline. Thus, the better results of SEGAPSITH can be attributed to the exploitation of a dedicated source of knowledge.

Quantitative evaluation

In order to evaluate the interest of bootstrapping objectively, we have applied the segmentation methods of SEGCOHLEX and SEGAPSITH to the classical task of discovering boundaries between concatenated texts. As we are interested in segmenting texts at the paragraph level, our evaluation has been performed with short texts, more precisely 49 texts from Le Monde newspaper that are 133 words long on average. Like [START_REF] Hearst | TextTiling: Segmenting Text into Multi-paragraph Subtopic Passages[END_REF], we have defined precision as N t / N b and recall as N t / D, where N t is the number of boundaries that match with document breaks (within an interval of 9 words around each document break, after pre-processing), N b , the number of found boundaries, and D, the number of document breaks. Results shown in table 2 are means computed from 10 trials, the order of texts being changed from one trial to another. These results clearly show that SEGAPSITH has better performances than SEGCOHLEX. Furthermore, they show the interest of bootstrapping: SEGAPSITH(1), which relies on semantic domains built from TUs, has better results -its little inferiority in precision is greatly balanced by its superiority in recall -than SEGAPSITH(2), whose domains were built from texts without any segmentation or enrichment. Although a meaningful comparison is not easy to do, our best results seem at least comparable to the other works in the field. In a similar evaluation with 44 texts (average length of 16 paragraphs), Hearst [START_REF] Hearst | TextTiling: Segmenting Text into Multi-paragraph Subtopic Passages[END_REF] gets 0.95 as precision and 0.59 as recall. However, a direct comparison is not completely relevant as Hearst's method cannot be applied to texts as smaller as ours. The work in [START_REF] Bigi | Detecting topic shifts using a cache memory[END_REF] is more similar to ours although its evaluation method is slightly different. The differences between its results -0.75 as precision and 0.80 as recall -and ours can be explained by the nature of topics: this work focuses on a small set of very general topics (business, politics, ...) while we focus on a large set of specific topics. As our topic representations are closer to the topics of texts, we have a better recall; but we also are likely to have more noise, which explains our lower precision.

Related works

Thematic analysis able to identify topics must rely on explicit topic representations, as [START_REF] Bigi | Detecting topic shifts using a cache memory[END_REF] or works done in the Topic Detection and Tracking (TDT) framework [START_REF] Fiscus | NIST's 1998 Topic Detection and Tracking Evaluation (TDT2)[END_REF]. Like these methods, the one of SEGAPSITH makes use of explicit topic representations but it exploits them with tools similar to text segmentation works based on lexical cohesion as [START_REF] Kozima | Text Segmentation Based on Similarity between Words[END_REF] or [START_REF] Hearst | TextTiling: Segmenting Text into Multi-paragraph Subtopic Passages[END_REF] and not with the probabilistic approach generally found in TDT or in [START_REF] Beeferman | Statistical Models for Text Segmentation[END_REF]. Works done in the TDT framework also differ from ours in the delay for deciding if a topic shift occurs: from 100 up to 10000 words in TDT but only 3 content words in SEGAPSITH. Moreover, topics in TDT represent events. On the contrary, they are very general in [START_REF] Bigi | Detecting topic shifts using a cache memory[END_REF]. Semantic domains in SEGAPSITH are halfway between these two extremes: they aim at describing specific topics but not events. Topic representations clearly allow working at a finer grain than methods based on lexical cohesion. But on a large scale, they also require to be automatically built, preferably in an unsupervised way. This problem is tackled to some extent in the Detection task of the TDT evaluation but not in the segmentation one. On the contrary, SEGAPSITH includes an unsupervised learning of the topic representations that support its segmentation module. Moreover, its association with SEGCOHLEX allows to progressively bootstrap a fine-grained segmentation module based on topic representations from a rougher segmentation module based on lexical cohesion.

Conclusion

Developing reliable NLP processes requires large bases of structured knowledge that are very difficult to build. In order to overcome this problem for thematic analysis, we adopted a bootstrapping approach: we implemented a first process, based on automatically acquired knowledge, used its results to build finer topic representations and then developed another process that exploits the new base in order to get better performances. The evaluation of this method shows that results obtained with structured and specialized knowledge are better than with general one and moreover, that learning knowledge from the results of text segmentation is more reliable than learning it from non processed texts.

Figure 2 :

 2 Figure 2: Building of the context segment

Figure 3 :

 3 Figure 3: The automaton for topic shift detection

Figure 4 :

 4 Figure 4: A text and its context similarity graph (for the French text)

Figure 5 :

 5 Figure 5: SEGCOHLEX results on the same text than in Figure 4

Table 2 :

 2

Extract of words selected in the collocation network for the segment Table

1

Table 3 :

 3 The most representative words of a domain about justice

Table 2 :

 2 Results of the evaluation for the different methods

	segmentation procedure	recall	precision f-measure
	SEGOHLEX	0.675	0.374	0.481
	SEGAPSITH(1)	0.920	0.523	0.666
	SEGAPSITH(2)	0.810	0.535	0.644


Gaël De Chalendar

Brigitte Grau
email: grau@limsi.fr

Olivier Ferret
email: ferret@limsi.fr

A Cost-bounded Algorithm to Control Events Generalization

In order to build descriptions of prototypical situations, we first developed a system, MLK (Memorization for Learning Knowledge), allowing us to gather events related to similar situations starting from descriptions found in texts, these events being represented by conceptual graphs. One of the stages to build these prototypes consists of generalizing some similar graphs in order to produce a description. In this paper, we present a cost bounded algorithm of conceptual graph generalization, proceeding by ascending clustering. The use of costs on the operations of generalization allows us to control the growth of the search space.

Introduction

Text understanding requires knowledge about concrete situations that are developed in order to recognize links between the different events. Such knowledge is often represented by schemas whose content describes characters and events involved in a situation. However handcoding schemas is a very difficult task, even on a limited domain. Automatic acquisition of situation descriptions has been [START_REF] Mooney | Learning schemata for natural language processing[END_REF], [START_REF] Michael | Integrating explanation-based and empirical learning methods in OCCAM[END_REF] and [START_REF] Ram | Indexing, elaboration and refinement: incremental learning of explanatory cases[END_REF], but essentially to learn new specialized situations of predefined ones. Inside a framework that does not make any hypothesis on the existence of general knowledge, we have first conceived the system MLK (Memorization for Learning Knowledge) [START_REF] Ferret | An Aggregation Procedure for Building Episodic Memory, 15 th IJCAI[END_REF], [START_REF] Ferret | Construire une mémoire épisodique à partir de textes : pourquoi et comment ?[END_REF], able to learn from the accumulation of its own experience. MLK memorizes each specific situation found in texts by aggregating it with an already memorized description if a similarity between their events is recognized. This process leads to incrementally build aggregated Thematic Units (TU) that are precursors of general schemas. Each event inside a TU is represented by a weighted conceptual graph (CG) [START_REF] Sowa | Conceptual Structures: Information Processing in Mind and Machine[END_REF]. In order to build a general description of a situation from a TU, we have studied how to generalize these events, i.e. conceptual graphs, to find a description level accounting for different formulations of a same event. This kind of problem is dependant on ascending clustering methods from positive examples. Generalization algorithms of conceptual graphs have already been proposed [START_REF] Mineau | Induction on Conceptual Graphs: Finding Common Generalizations and Compatible Projections. Conceptual Structures -current research and practice[END_REF], [START_REF] Bournaud | Construction de hiérarchies conceptuelles pour l'organisation de connaissances[END_REF], but they only generalize concepts, and not the graph itself. Generalizing both concepts and graphs entail a combinatory explosion when searching for all the possibilities. Therefore, we have developed a cost-bounded generalization algorithm that limits the search space and leads us to propose informative generalizations. A cost is associated with each generalization operator, and we take advantage of semantic knowledge to produce meaningful descriptions of events.

System Overview

The system input is made of a set of conceptual graphs describing events related to a situation of the same kind, for example to come in a house, to attack a woman, to stab a man with a knife, to arrest the murderer, etc. In order to elaborate a description of the situation from these events, a main stage is to find a right level of description leading to generalize those specific graphs describing a same kind of event. In the preceding example, it would consist of proposing a description where the woman attack and the man stabbing are generalized, whereas the two other events are left as it. Then the problem can be formulated as follows: given a set of conceptual graphs, find among them those that can be generalized while keeping an informative description level. Our purpose is not to find the common generalization of all the events, but a description level keeping the specificity of the kinds of events represented by the graphs. Coming back to the example, our goal is not to generalize the four events in a single one that would be to carry out an action. The method we propose consists of developing a sub-set of the possible generalizations of each graph, by generalizing concepts and removing relations. Generalization is controlled by the use of semantic knowledge: a lattice of concept types and constraints on the arguments related to some concepts, given by canonical graphs. It avoids overgeneralizations that would not have any meaning. Developing all the generalizations of a graph is unconceivable, even if limiting them by comparison with domain knowledge. Therefore, in order to limit the size of the generalization space, a cost is associated to the generalization operators, allowing the system to associate a cost to each graph produced and to limit their formation by fixing a threshold. Costs are defined according to the task and encode the generalization level that is searched. All the generalizations are organized in configurations allowing the system to know which initial graphs are generalized. These configurations represent the different possibilities to describe the initial situation. The choice of one of them is done according to the number of initial graphs that are generalized and to the cost of the different configurations. Thus, the description level that is built is constrained both by the semantic knowledge and by the costs associated to the generalized graphs. This method allows us to bypass the difficulty coming from the impossibility to define negative examples in our task and then to use classical learning algorithms.

Conceptual Graphs

Semantic knowledge is represented in a lattice of types of concept and by canonical graphs associated to some types in order to precise their thematic roles (i.e. relations), as agent, object, etc., and semantic constraints on concepts that might fill them (see Fig. 1). We do not follow the Conceptual Graphs standard draft NCITS.T2/98-003. The "syntactic" knowledge held by star graphs is coded by our canonical graphs. Conceptual graphs that represent events (see Fig. 2) are obtained by application of formation rules to one or several canonical graphs, as described in Sowa [START_REF] Sowa | Conceptual Structures: Information Processing in Mind and Machine[END_REF]. So, these graphs are built with respect to the constraints defined in the knowledge base. A graph resulting from the application of these rules is a specialization of one (or several) initial graph(s). In Fig. 2, the graph results from a maximal joint between two graphs produced after restrictions on types of concept in the canonical graphs associated to stab and body. See [START_REF] Ellis | Compiled Hierarchical Retrieval. Conceptual Structures -current research and practice[END_REF] for a detailed presentation of the formation rules and their relation with subsumption. The class of CGs we consider is the class of simple CGs derived from canonical graphs, with n-ary relations and with a distinguished concept node explained below.

[Stab]- [Stab]- (agent) → [Human] (agent) → [Man] (dest.) → [Body ] (dest.) → [Body ] - (instrument) → [CuttingEdge] (partOf) → [Man] (instrument) → [Knife]
Fig. 1. A canonical graph Fig. 2. An event

As our graphs represent events, we distinguish a concept that is significant for the event type, named predicate (Stab in Fig. 2), this concept playing a particular role inside our application. Other kinds of concept result from abstractions done during the aggregation process in MLK. They already generalize instances linked to a same predicate that are found in texts. See [START_REF] Ferret | An Aggregation Procedure for Building Episodic Memory, 15 th IJCAI[END_REF] and [START_REF] Ferret | Construire une mémoire épisodique à partir de textes : pourquoi et comment ?[END_REF] to find details about the process that build these graphs.

Graphs Generalization

Method

Some graphs belonging to the initial set may contain different predicates while being very similar, as in Fig. 3. If graphs are identical except for their predicate, and if these predicates are semantically close, these graphs have to be replaced by a graph that generalize them. The same principle applies if the graphs only differ by some details in the predicate arguments. The problem is then to find the least common generalization of several graphs, given one does not a priori know which graphs in the initial set have to be generalized.

Fig. 3. Similar conceptual graphs with different structures and concepts

Such a problem is similar to conceptual clustering, with conceptual graphs as the description language of the concepts to be learned [START_REF] Michalski | Learning from observation: Conceptual clustering[END_REF]. Initial conceptual graphs are equivalent to first order logic formulas, made of a conjunction of positive predicates, the concepts and the relations of the graphs. This problem is close to the work of Mineau and Bournaud. Even if we do not search for a classification, which is the problem they have to solve, the generalization space has also to be generated in order to choose the generalization level we want to reach. In their work, a graph is represented by the set of its relations to avoid comparison of graphs, that is a NPcomplete problem. However, this approach cannot be applied in our application given that the structure of the graphs may be modified during the generalization process when removing relations. We have to reason on graphs themselves in order to keep specific links between a predicate and its arguments, i.e. to maintain their connectedness. It is then impossible to generate meaningful generalizations in a limited time without controlling the growth of the generalization space. The process we propose is a cost-bounded algorithm that associates a cost to each generalization operator and uses domain knowledge to avoid overgeneralizations. This algorithm has been conceived without taking into account the specificity of our application other than the presence of a central concept in conceptual graphs. So we consider that types of relations are organized in a lattice, even if our knowledge representation does not use this possibility.

We have defined three primitive generalization operators:

1. concept generalization: replacing a type of concept by its supertype in the lattice, 2. relation generalization: replacing a type of relation by its supertype in the lattice, 3. relation removing: removing a relation in the graph, and some associated concepts.

We have not defined an operator for removing concepts because removing a concept entails the removal of all the relations it is linked to. If we come back to the example in Fig. 3, removing the concept Shop leads to remove the relation Loc, and conversely removing the relation Loc leads to remove the concept Shop in order to keep a connected graph (in such a case, we keep the connected component that contains the predicate). Removing relations is then sufficient since removing concepts is strictly included in the results of the removal of relations, which may entail the removal of several concepts and relations.

These operators create a partial order between the resulting graphs, as defined in [START_REF] Sowa | Conceptual Structures: Information Processing in Mind and Machine[END_REF] and [START_REF] Ellis | Compiled Hierarchical Retrieval. Conceptual Structures -current research and practice[END_REF]. Precisely, the subsumption relation defined for conceptual graphs is the relation induced by the existence of a projection between two graphs [START_REF] Champesme | Using Empirical Subsumption to Reduce Search Space in Learning[END_REF].

We associate a cost to each operator since we dispose neither a domain theory (general knowledge about situations for example), nor a characterization of the pieces of knowledge we want to learn that would give us a formal proof of the quality of the generalization. We use an empirical evaluation based on semantics and the estimation of the loss of information when generalizing.

In order to find this cost, we have reasoned on the effect of each operation in terms of loss of information it entails. In our context, the cost of each operator is related to the concept it applies to: predicate or not, concept derived from the canonical graph of the predicate or not. When generalizing a concept that is not derived from the canonical graph of the predicate, named common concept, the generalization is made on characteristics that are peripheral to the event. Removing relations, that, as already said, causes the removal of concepts, entails the suppression of some of these characteristics. As a matter of fact other concepts cannot be removed, as one cannot remove relations belonging to the canonical graph of the predicate without losing the meaning of the graph (the canonicity of the resulting graph is no more verified). Lastly, the operation we consider as very costly is the generalization of the predicate, since, as we have seen in part 2, we want to avoid many generalizations of the predicates in order to keep kinds of events specific to the described situation. So the least common generalization is a graph achieved by preferentially generalizing concepts other than the predicates.

We have defined the following order of the costs of the operators, this ordering characterizing the loss of information: generalization of a common concept ≤ generalization of a concept derived from the canonical graph ≤ removal of a relation ≤ generalization of the predicate The relative order is more significant than absolute values that defines costs. The value given to each operator is connected to the threshold that is fixed to compute generalizations for a given application, the number of operations it is likely to realize, and the importance of each operation in relation to the others. These values have to be fixed experimentally according to the application.

Let us now present some specificity due to the conceptual graph formalism and our application. Firstly, it is not possible to suppress the predicate, since the resulting graph(s) would no longer refer to the described event. Secondly, if two non-connected graphs result from a suppression, we only keep the graph containing the predicate. Thirdly, a concept is never generalized in a concept more general than the one in the canonical graph. And last, when generalizing a predicate, a verification is done using the new canonical graph to ensure the canonicity of the resulting graph. A consequence of having this distinguished concept is that the complexity of the operations on CGs is reduced due to less possible matching between two graphs. But that does not reduce a lot the size of the effectively searched space.

The Generalization Algorithm

One stage of the algorithm consists in building the generalization space which contains, at the beginning, the conceptual graphs to be generalized, i. e. the root nodes. During the processing, each node resulting from a generalization is inserted in this space only if it does not already exist. A node of depth n is the result of n generalizations of a root node. For example, a conceptual graph that contains 3 concepts and 2 relations may be processed by applying 5 generalizations of concept or relation and 2 removal of relation. It would generate, at most, 7 new nodes. The cost associated to each node, related to the path towards the root node, is equal to the cost of its father plus the cost of the operation which has given it birth. The cost of a root node is zero. Applying such an algorithm until a common generalization is found, if it exists, is exponential in the general case. Bounding the set of the possible generalizations by fixing a maximal cost on the nodes entails a quite reasonable practical complexity (this latter point will be detailed in the following section) and all the generalizations having a cost less than this threshold are computed.

Fig. 4 shows an example where three conceptual graphs (the root nodes x1, x2 and x3) have been generalized in the graphs (a, b, c, d), (c, b, e) and(e, f, g, d) respectively. Values on the branches are the costs of the applied operators.

Costs which stop the generalization process, more than maintaining the semantics of the graphs, yield the possibility to control the growth of the generalization space. In order to improve more effectively the performance of the algorithm, we have implemented some principles. For example, if the cost to find a supertype common to the predicate of a graph and the predicates of each other graph of the initial set oversteps the given threshold, this graph is removed from the initial set. By using this principle, the algorithm applies on graphs that may be a generalization of two root graphs, and not on the very initial graphs, given they all contain a different predicate (see Initialization part of the algorithm in Fig. 6). On another hand, graphs are indexed by their predicate and their number of relations and concepts, such as comparison of graphs is only done if these characteristics are identical. The aim of the algorithm is to generate all the possible descriptions of the initial set, the set of configurations. A configuration is a set of conceptual graphs, generalized or not, that represents a partition of the initial examples, the root graphs. After application of the algorithm, only the graphs that generalize several root graphs with the root graphs themselves are kept. Other nodes, that just generalize a unique initial conceptual graph, are useless for our purpose (for the example in Fig. 4, retained nodes appear in the first column in Fig. 5). The generalization cost of a node is the average cost of the generalization costs of this node, these latter costs correspond to the different path issued from the different root nodes. Finding the set of configurations consists of building all the subsets of nodes such as each initial node is generalized once and only once in the subset. Each configuration is evaluated by the average cost of its elements. If more than one configuration has been built at the end of the processing, we choose the one that verifies the following criteria, applied in this order: a) the configuration that corresponds to the generalization of the maximum number of root graphs; b) the configuration containing less numerous elements; and c) the configuration having the minimal cost, other than zero, considering it is the most likely to be the most common specific description of the initial events. By means of these criteria, we encode that the best description of the initial situation corresponds to the maximal regrouping of graphs, whose cost is less than the limit. In the example of Fig. 4, these criteria lead to choose the configuration [b, x3] having an average cost equal to 1. These criteria fit our application, even if, for other kinds of applications, another order or other criteria may have to be found.

Nodes

Fig. 6. The generalization algorithm

The algorithm we propose is general enough to be used in other applications. We will see in the latter sections that heuristics coming from the application domain and expressed with simple numeric values, entail the considerable pruning of the search space, allowing the algorithm to find only the more informative generalizations. As for all algorithms depending on heuristics, it is not easy to formally demonstrate the complexity of our algorithm, thus we have worked on a demonstration of the adequacy and the efficiency of this method by extensive tests.

Results

The process has been applied with success to the results of MLK, but this does not entail a validation on a quantity of data sufficiently large, because text representations that compose the input of MLK are handcoded at this moment. That is why, in order to test our algorithm in a better way, we conceived a test generator. Its knowledge (lattice of types and canonical graphs) is compatible with our application and the generator is parameterizable so that it can simulate different kinds of application.

Domain Knowledge

Our application exploits a lattice of types of concepts and a set of canonical graphs. The lattice (see Fig. 8), results from the work of Chibout [START_REF] Chibout | Computational Processing of Verbal Polysemy with Conceptual Structures[END_REF] who created an ontology of approximately 3,000 concepts for verbs and entities. We extracted a subpart from this ontology so that to obtain a lattice regular enough in depth and in breadth. Thus, 368 concepts were extracted and distributed in a lattice with an average depth of 5.59 for a branching factor of 2.75. We have selected 8 verbs from the 128 verbs retained to assign canonical graphs to them. These canonical graphs are defined relative to the types retained in the lattice and to produce homogeneous bench tests, so that global results will have a signification.

ToDrink Function

Liquid Agent Object Fig. 7. Canonical graph of the concept denoted by the verb "to drink"

The 8 types are ToCauseDeath, ToCauseToFeel, ToDivide, ToBreak, ToFly, ToAbsorb, ToEat and ToDrink. Subtypes inherit of the canonical graph of their father. Figure 7 shows the canonical graph of ToDrink. The Function concept is the supertype of 55 concepts. Some of them are Artisan, Killer or Deputy. Liquid is the supertype of, among others, Water, Alcohol and Syrup

The lattice of relation types is limited in our application to a flat lattice: all the relations have the same supertype (T) and the same subtype (⊥). For our tests, we have used four relations: Relation, Agent, Object and Place.

Bench Test Generation

We have generated sets of graphs with controllable properties for the generalization. By specializing canonical graphs in directions randomly chosen and in different depths, our task is then to retrieve the original common graphs, or, better, some specialization of them that might not have appeared during the generation phase. So, our generator builds sets of graphs such as each set possesses a partition of its graphs where each part (named family) is made of graphs that are specialized from a graph more specific than their common canonical graph. This definition of the searched generalizations comes from our application for which it is not suitable to generalize events by their canonical graph: it does not fit an informative description.

A Borderline Case

We produced 33 sets of 4 graphs containing 3 to 5 concepts and belonging to 2 families. These graphs were produced by applying 3 to 8 specialization operations on canonical graphs. The threshold for the generalization was set to 10 and a limit of processing time was fixed to 1 hour by case. For this data set, we set low values to costs of operations in order to test the borderline case: the costs allow the system to compute all the ancestor graphs. These costs are the following: 1. any concept generalization: 1, 2. generalization of one concept of the canonical graph: 1, 3. predicate generalization: 2, 4. relation suppression: 1.

The generalization process finds 32.15 configurations on average by bench test, in an average time of 28mn, 30% of the generalization processes reaching the time limit. The 70% solved cases are solved in an average time of 15mn.

Costs Utilization

To show the efficiency of mindfully chosen costs, we carried out the same kind of tests, but with costs multiplied by 2. We generated 60 bench test with 4 graphs each. With a time limit set to 1 hour, we obtained 12,2 configurations on average by case. With 20mn., we obtained 11.9. So, 97.5% of the configurations obtainable in 1 hour were obtained in less than 20mn. The following results were obtained in this time limit: 96.7% of the bench tests lead to at least one solution and 73,3% of the cases did not reach the time limit. Figure 11 shows the percentage of configurations obtained for all bench tests in function of the time. It shows that in a reasonable time of 7mn., 90% of the solutions obtainable in 20mn (92.3% of those obtainable in 1 hour) are already obtained. Thus, according to task requirements, if it is possible to miss some solutions, then one can parameterize the generalization system with processing times really acceptable.

For these tests, the relevant solutions (i.e. informative) are thus those that contain generalized graph(s) equal to the ancestor graphs from which the graphs of the tests are issued. This relevant solution can only be found if, for each graph, the sum of the costs of the specialization operations applied to them is lower or equal to the generalization limit, here 10. The number of bench tests in this case is 22 (37%). With a processing time set to one hour, the relevant solution is found for all these cases and in 20mn., 20 solutions are found (90.9%). In the other 63%, for which the theoretical cost of the optimum solution is higher than the limit, we find nevertheless 15.8% of configurations in which the number of generalized graphs is the same as the number of families. This can be explained by the fact that cousin graphs are randomly generated. If by chance the specialization process goes the same way for some graphs, then the effective relevant solution is more specific than the ancestor graph.

Analysis

It has to be noted that in the first series of tests, the obtainable relevant solutions are obtained in 70% of the cases (23/33). In the second series, 100% of the obtainable solutions are found in one hour, however it contains a least number or test cases. So, with low costs, a great number of solutions is found and we also miss some good solutions. On the contrary, with high costs, the number of possible solutions is lower and the system finds all of them. When we will apply the system on real data, we will have to choose costs according to these two extremes.

These tests show that a cost-bounded algorithm allows us to generalize conceptual graphs in a reasonable time, in tasks where costs on the generalization operators are definable. Differences between the two series of tests show the benefits of modulating the costs and the limit threshold in order to produce interesting generalizations and to avoid the production of graphs corresponding to overgeneralizations in the application, i.e. valid graphs with a too general description level.

It is not an easy task to show the validity of solutions obtained with unsupervised learning. Thus, we have conceived our test protocol in such a way that the searched solution can be characterized. In our application framework, the validation could be done externally by an expert who would answer the following question: "Does the produced solution seem coherent to you: are events described at a correct description level compared to the described situation?". In case of non-satisfaction, it is possible to execute the process again to search for new generalizations. Another possibility would be to validate a system using the learned knowledge.

Previous Works

Mineau [START_REF] Mineau | Induction on Conceptual Graphs: Finding Common Generalizations and Compatible Projections. Conceptual Structures -current research and practice[END_REF] and Bournaud [START_REF] Bournaud | Construction de hiérarchies conceptuelles pour l'organisation de connaissances[END_REF] have conceived algorithms to build a classification from an initial set of conceptual graphs. Even if we do not want to classify data, finding a generalization level can be seen as an equivalent problem as it requires the algorithm to compute possible generalizations. The major difference comes from the generalization operators used. Suppression of relations entails the necessity of a complete description of each generalized graph and not only a partial description by their relations. To limit the effective complexity, we have introduced costs associated with operators. These costs have to be fixed relative to the type of generalizations expected in the application. As in [START_REF] Bournaud | Construction de hiérarchies conceptuelles pour l'organisation de connaissances[END_REF], we also use domain knowledge to constrain generalization.

Our work comes under Inductive Logic Programming (ILP) domain [START_REF] Muggleton | Inductive Logic Programming: Theory and Methods[END_REF] and our problem is particularly close to the work of Esra Erdem and Pierre Flener [START_REF] Erdem | A Re-Definition of Least Generalizations, and Construction Modes as a New Declarative Bias for ILP[END_REF], who redefine the minimal generalization in order to find a minimal set of generalized clauses in function of an over-generalization criterion. In the field of ILP and conceptual graphs, our kind of problem is studied in the work of Marc Champesne on the reduction of the search space by the use of the notion of "empirical subsumption" [START_REF] Champesme | Using Empirical Subsumption to Reduce Search Space in Learning[END_REF]. However his results can only be applied to non-connected graphs whereas our algorithm handles connected ones. About our application itself, i.e. learning descriptions of prototypical situations, our work is different of [START_REF] Mooney | Learning schemata for natural language processing[END_REF], [START_REF] Michael | Integrating explanation-based and empirical learning methods in OCCAM[END_REF] and [START_REF] Ram | Indexing, elaboration and refinement: incremental learning of explanatory cases[END_REF] essentially because we do not hypothesize the existence of previous knowledge about situations and learning is completely unsupervised. The system MLK, which implements this application, gathers and selects events and their relevant characteristics when recurrent situations are found in texts, and the system proposed in this paper assumes the construction of a general description with respect to semantic knowledge.

Conclusion

Learning structures in order to describe concrete situations has lead us to construct the system MLK, able to identify events linked to a same situation. In the purpose of generating general descriptions for these situations, we have studied the generalization of events represented by conceptual graphs. However the generalization algorithm we propose is independent enough of our particular context and could be used with other applications.

This algorithm is completely implemented in Smalltalk. The tests made show the benefit of fixing costs on generalization operators in applications having only a weak domain theory.

The protocol of bench tests generation we have developed allows us to control different parameters such as the definition of an optimal solution, the number of operations to be applied in order to find this solution and the homogeneity of the bench tests. It presents two major advantages: testing the efficiency of our approach and allowing us to find values for the diverse parameters of the generalization algorithm by successive tests.

At this time, we are working on the automatic acquisition of ontologies from partial syntactic analysis of phrases. This work will allow us, in a middle-term prospect, to apply the described generalization process to a great amount of data very similar to Thematic Units. In a more long-term prospect, this should entail the application of the complete MLK system on data automatically extracted from large volumes of texts.

Fig. 4 .

 4 Fig. 4. A generalization space built from 3 root graphs

Fig. 5 .

 5 Fig. 5. Results of the generalization algorithmConfigurations are computed during the generalization process (cf. Updating configurations in the algorithm). At each step, partial configurations, corresponding to the retained generalizations, are updated if the new graph generalizes at least two root graphs.

Fig. 11 .

 11 Fig. 11. Percentage of computed configurations relatively to the processing time

Fig. 8. Extracts from the concept ontology

To produce a bench test, the generator randomly chooses n predicates (P1 and P2 in Fig. 9), each one being the origin of one family. The canonical graph of each predicate is then specialized several times (s1 times in family 1 and s2 times in family 2) to generate n graphs, named ancestor graphs. Each ancestor graph is differently specialized (k1, k2, …, k5 times in family 1 and k1, k2 and k3 times in family 2), creating different specializations named cousin graphs.

Fig. 9. Bench test generation framework

Input data of the generalization process are the set of all the cousin graphs of different families (the 8 cousin graphs), the goal being to retrieve the set made of the ancestor graphs. The numbers of specialization operations applied (restriction of type belonging to the canonical graph or not, addition of a relation) are set at the time of the bench test specification.

We can see below an example of test containing four graphs with two families of two graphs each. The graphs have been obtained following the parameters presented in Fig. 10. Graph 1:

Specializations for ancestors

Specializations for cousins Predicates

Canonical Graphs

predicate canonical graph concepts predicate canonical graph concepts concept adding

Fig. 10. Parameters for generating a set of graphs This example entails the construction of 6 configurations in a total time of 115s. We can see below the optimal solution obtained in 15 seconds and a non-optimal solution. Costs of operations are specified in section 5.4. Optimal Solution: If we look again at the definition of a good solution given section 4.2, the optimal solution in this example respects the established criteria: maximum of root graphs generalized, minimum number of graphs in the configuration and minimal cost in the case of configuration equality. In the non-optimal configuration, the concept Nurse in the two graphs of the first family has been overgeneralized in MedicalProfession. So, we really have obtained the best solution for a cost inferior to those of the other solution. The four other solutions, not presented here, have inferior costs but do not generalize all the graphs.

We will now describe two bench tests. The first one tests a difficult case with very specialized graphs and little generalization costs. It entails the generation of a great number of configurations and high computation times. The second one shows the efficiency of the system with higher costs.