Olivier Ferret

Brigitte Grau

A Thematic Segmentation Procedure for Extracting Semantic Domains from Texts

Thematic analysis is essential for a lot of Natural Language Processing (NLP) applications, such as text summarization or information extraction. It is a two-dimensional process which has both to identify the thematic segments of a text and to recognize the semantic domain concerned by each of them. This second task requires having a representation of these domains. Such representations are built in Information Retrieval or Text Categorization fields by grouping together the words of a set of texts which have been manually linked to the same domain. We claim that this kind of method can only be apply to characterize very general topics. We propose here a method for building the representation of narrower semantic domains without any manual intervention. First, we present a procedure for the thematic segmentation of texts which relies on lexical cohesion evaluated from a collocation network. This procedure allows us to have basic units that are more thematically coherent than a whole text. Then, we show how these units can be aggregated together, according to a similarity measure, to build the representation of semantic domains in an incremental and unsupervised way. 1 1.

INTRODUCTION

Thematic analyzis is a necessary process when analyzing discourse. Different tasks as story understanding, text summarization or text classification for example requires to recognize discourse topics, as a step towards their achievement, or as their final purpose. Thematic analyzis involves decomposing a text in parts relative to a same topic and to identify these topics.

Approaches to solve this problem can roughly be categorized in two classes, knowledge-based approaches or word-based approaches.

Knowledge-based systems [ Grau, 1984 #42;[START_REF] Grosz | Attention, Intentions and the Structure of Discourse[END_REF] #52] lead to a precise decomposition and identification of the discourse topics, by using in-depth understanding processes. They required an extensive manual knowledge engineering effort to create the knowledge base, represented by semantic network and/or frames, and this is only possible in very limited and well-known domains.

To overcome this limitation, and be able to treat a large amount of texts, word-based approaches have been developed [START_REF] Kozima | Text Segmentation Based on Similarity between Words[END_REF] #72; Morris, 1991 #73;Ferret, 1997 #121] . The purpose of these systems is to segment texts, but not to recognize topics in terms of associating discourse segments to classes. Such a problem is close to text categorization, where a system must find the appropriate domain of a text. Domain descriptions are either hand-coded or computed by the systems [ Lehnert, 1994 #164] , but it always requires an a priori classification of the texts constituting the training corpus. Furthermore, these systems consider texts as a whole, and do not proceed to a finer analyzis for identifying different topics inside the texts.

At the opposite, automated summarization requires to segment texts and to recognize their related topics. For this latter task, Hovy and Lin [ Hovy, 1997 #136] The definition of such classes result from a study of a lot of text contents and this task is too tedious and time consuming to be done by human beings.

So, even if systems perform robust text analyzis and can be applied to a wide range of texts, their performance always depends on human interventions to define domain representations or at least to classify texts. In order to go towards a finer analyzis of texts without restriction about domains, the system we present here aims at learning specialized semantic domains. It automatically segments texts, and topic representations, described by weighted words, are incrementally built from these discourse segments. It works without any a priori classification or hand-coded pieces of knowledge. Our approach merges statistical techniques and the use of knowledge about word proximity that are also learned from a corpus.

OVERVIEW OF THE SYSTEM

Studied texts are newspaper articles coming from two corpora: "Le Monde" and "AFP". They are pre-processed to only keep lemmatized content words (adjective, single or compound nouns and verbs). A part of these texts has been used to build a lexical network where links between two words represent an evaluation of their mutual information to capture semantic and pragmatic relations between them, computed from their co-occurrence number.

Text segmentation is based on the use of this network. A discourse segment is a part of text whose words refer to the same topic. A topic is detected by computing a cohesion value for each word resulting from the relations found in the network between these words and their neighbours in a text. These values lead to build a graph and by successive transformations applied to it, texts are automatically divided in discourse segments. Only highly cohesive segments are kept to learn topic representations.

Discourse segments in texts, even related to the same topic, often develop different points of view. To incrementally learn a complete description of a topic, all successive points of view have to be merged in a single memorized thematic unit. As each segment contains from twenty to forty words, which is low according to the number of words belonging to a same domain, we have to face here two problems : a) recognizing the similarity of two units, even described by few identical words in the original texts and b) building thematic unit complete enough without having to process too numerous texts. A solution is to go beyond the words really used in the processed texts by inferring missing information. So, correlated words coming from the network are selected and added to the representation of a discourse segment; this leads to the formation of a discourse unit described by weighted words. Weights represent the importance of each word relative to the topic, and result from the number of occurrences of a word in the segment and the weights found in the network.

The memorization process then selects memorized units. If one is sufficiently close to the current discourse unit, topic descriptions are aggregated, otherwise a new unit is created. Each aggregation leads to augment the system's knowledge about one topic by reinforcing recurrent words and adding new ones. An aggregated thematic unit is then also represented by weighted words. Similarity is based on the number of common words and their weights. The retrieval process is akin to a propagation in one step, departing from the words belonging to a discourse unit towards the memorized topics.

The whole process has been applied to 5949 texts and we detail in this paper each of its components and an evaluation of the results.

3.

THE THEMATIC SEGMENTATION

Preprocessing of the texts

As we are interested in the thematic dimension of the texts, texts have to be represented by their significant features from that point of view. So, we only hold for each text the lemmatized form of its nouns, verbs and adjectives. This has been done by combining existing tools. MtSeg from the Multext project is used for segmenting the raw texts.

As compound nouns are less polysemous than single ones, we have added to MtSeg the ability of identifying 2300 compound nouns. We have retained the most frequent compound nouns in 11 years of the Le Monde newspaper. They have been collected with the INTEX tool [ Silberztein, 1994 #165] . The part of speech tagger TreeTagger [ Schmid, 1994 #163] ,as for it, is applied to disambiguate the category of the words and to provide their lemmatized form. The selection of the meaningful words, which do not include proper nouns and abbreviations, ends the pre-processing. This one is applied to the texts both for building the collocation network and for their thematic segmentation.

Building the collocation network

Our segmentation mechanism relies on lexical cohesion. In order to evaluate it, we have built a network of lexical collocations from a large corpus. Our corpus, whose size is around 39 million words, is made up of 24 months of the Le Monde newspaper taken from 1990 to 1994. The collocations have been calculated according to the method described in [ Church, 1990 #67] by moving a window on the texts. The corpus was pre-processed as described above, what induces a 63% cut. The window in which the collocations have been collected is 20 words wide and takes into account the boundaries of the texts. Moreover, the collocations here are indifferent to order. These three choices are motivated by our task point of view. We are interested in finding if two words belong to the same thematic domain. As a topic can be develop in a large textual unit, it requires a quite large window to detect these thematic relations. But the process must avoid jumping across the texts boundaries as two adjacent texts from the corpus are rarely related to a same domain. Lastly, the collocation w1-w2 is equivalent to the collocation w2-w1 if we only try to characterize a thematic relation between w1 and w2.

After filtering of the non-significant collocations (collocations with less than 6 occurrences, which represent 2/3 of the whole), we obtain a network with approximately 31000 words and 14 million relations.

The cohesion between two words is measured as in [START_REF] Church | Word Association Norms, Mutual Information, And Lexicography[END_REF] #67] by an estimation of the mutual information based on their collocations frequency. This value is normalized by the maximal mutual information with regard to the corpus, which is given by : Imax = log 2 N 2 (Sw -1) with N : corpus size S w : window size

The segmentation algorithm

The segmentation algorithm we propose includes two steps. First, the evaluation of the cohesion of the different parts of a text, and second, the location of the major breaks in this cohesion to detect the thematic shifts and to select the most coherent segments useful for domain learning.

Evaluating the cohesion of a text

The method for evaluating textual cohesion is close to Kozima's work about this matter [ Kozima, 1993 #72] . A cohesion value is computed at each position of a window in a text from words in this window. The collocation network is used for determining how close together the words in the window are. We suppose that if these words are strongly connected in the network, it means that they belong to the same domain and so, that the cohesion in this part of text is high.

On the other hand, if they are not very much linked together, we can infer that the words of the window belong at least to two different domains. It means that the window is located across the transition from one theme to another.

In practice, the cohesion inside the window is evaluated by the sum of the weights of the words in this window and the words selected from the collocation network as well. For each word in the window, the system collects the words in the network linked to it and it only selects those that are common to at least one other word of the window. Thus, it makes words related to the same topic as the one referred by the words in the window explicit and produces a more stable description of this topic when the window moves. Words are weighted by combining the cohesion values of the words they are linked to and their initial weight, equal to their number of occurrences in the window, as shown in figure 1. The more the words belong to a same topic, more they are linked together and the higher their weights are. Finally, the value of the cohesion for one position of the window is the result of the following weighted sum:

coh( p) = sign( wi) i ∑ ⋅wgth(wi)
where wgth(w i ) is the weight of the word w i computed as described above, sign(w i ) is the significance of the word w i.

The significance of a word is defined as in [ Kozima, 1993 #72] as its normalized information in a corpus (here, the corpus used for building the collocation network):

sign( w) = -log 2( fw Sc) -log2(1 Sc) , with sign( w ) ∈ 0,1 [ ]
where f w is the number of instances of the word w in the corpus, S c is the number of words in the corpus.

The figure 2 shows the result of the cohesion computation for the text below with a window of 19 words wide. A manual analyzis of the graph shows three zones. A first thematic segment goes from the beginning of the text to approximately the word 'pointed'. It is related to the dedicate situation mentioned by the text. The second segment, which stops around the word 'converse' is about the murder attempt and its direct consequences. The last segment, which is only about a detail of the second situation, can not be considered as interesting for us because of its too low cohesion. In fact, this means that this detail is too specific in relation to the thematic knowledge implicitly held by the collocation network.

Detecting the thematic shifts and selecting the most coherent segments

Our method for building thematic segments from the cohesion graph is simple. First, the graph is smoothed to more easily detect the main minima and maxima. This operation is done again by moving a window on the text. At each position, the cohesion associated to the center of the window is re-evaluated as the mean of all the cohesion values in the window. After this smoothing, the derivative of the graph is calculated to locate the maxima and the minima. We consider that a minimum marks a thematic shift. So, a segment is characterized by the following sequence: minimum -maximum -minimum. The final step is to transform the graph so that each segment is represented by a plateau with its cohesion value equal to the value of the maximum between the two minima that surround it. The figure 3 shows the results for the above text. In order to make the delimitation of the segments more acute, a segment can be stopped before the next (or the previous) minimum if there is a brutal break of the graph and after this, a very slow descent. This is done by detecting that the cohesion values fall under a given percentage of the maximum value. On the figure 3, we see the same three parts we had previously found by a manual analyzis of the initial cohesion graph. For eliminating segments such as the third one here, which are not coherent enough to be considered in the learning stage, we have defined an adaptive threshold: the cohesion of a segment must not be under the mean of the cohesion values of all the segments minus their standard deviation.

EMERGENCE OF SEMANTIC DOMAINS

Thematic Unit and domain representation

The segmentation process produces a set of segments, that are lists of words. In the purpose of learning semantic domain representations, each segment leads to a description of the topic it refers to, named Thematic Unit (TU). Each TU is then memorized, according to the existing domains previously created. If it is similar to an existing domain, then an aggregation occurs between them, otherwise a new domain appears. A TU is represented by a set of words, weighted by the following product: wght( wi) = nbOcc( wi) ⋅sign( wi)

where nbOcc(w i ) is the number of occurrences of the word w i in the segment.

The square root of the number of occurrences is taken because, without this kind of modulation, the importance of this factor is too high in the similarity measure in comparison with its true meaning. Moreover, a TU does not only contain the words coming from the text but also some of the words from the collocation network that have been used to compute the cohesion during the segmentation process. For every position in the text, all the words selected from the collocation network are retained but, for building a TU, only the words common to at least 75% of all the positions within the segment are hold. These words, also called inferred words, maintain their special status in a TU, but a weight is assigned to them similarly. In computing the similarity between a TU and a domain or in selecting domains from a TU, they are useful to bypass the fact that a theme can be expressed by different sets of words.

A domain is the result of the aggregation of several TUs. So, it is also called an aggregated TU. Its structure is exactly the same as the TU structure. The only difference between them lies in the weight of their words. This one for an aggregated TU is given by: wght( wi) = nbOcc( wi) nbAgr ⋅sign( wi) ⋅ nbAgr 4 (nbAgr +1) 4 where nbOcc(w i ) is the number of occurrences of the word w i in the TU and nbAgr, the number of the aggregations that have produced the TU.

The first factor takes into account the importance of the word in the TU. The last one is a modulator that prevents from favouring too much the new aggregated TUs in similarity or in selection.

Selecting domains

After a new TU has been built, the system has to search which already existing domain the TU can complete. As the memory may contain a very large number of domains, it has first to efficiently select those for which a more comprehensive similarity will be evaluated. Our selection method is equivalent to a one step activation propagation. The activation of an aggregated TU which has at least one word in common with the new TU is given by: activ(agrTUi) = wght(agrTUi,wj ) ⋅wght(TU,wj

) j ∑
where the first factor is the weight of the word w j in the aggregated TU and the second one is the weight of the same word in the new TU.

Because of their status, the influence of the inferred words is voluntarily reduced to the half of the influence of the other words. Moreover, the words which have too low a weight (under 0.1) are not used for activation because they are supposed to represent only noise. After this activation step, the selected aggregated TUs are those whose activation is greater than the average of all the activation values plus their standard deviation.

Similarity and aggregation

Once the domains have been selected, they can be compared to the new TU. In order to do that, a similarity measure is applied between the new TU and each of the selected aggregated TUs. If one of these similarity values is greater than a given threshold, the new TU is aggregated to the domain which is the most similar to it. Otherwise, a new domain is created.

The similarity measure takes into account only the words that are shared by the TU and the domain. It does not look at the differences between them because our learning method intrinsically generates a lot of noise. A TU contains many words that are not peculiar to its theme and a domain results from the aggregation of a lot of TUs. Only the recurrence of a word through these aggregations shows its importance for characterizing the domain. More precisely, the similarity measure is a combination of the importance of those common words in the new TU and in the aggregated TU. Unlike the activation process, the evaluation of these ratios does not only rely on the weights of the words. It also makes use of the number of common words between the new TU and the domain. This ensures that a high similarity is not found with only two or three words in common having a very high weight in comparison to the others. Actually, the similarity is given by:

ratioagrTU = wght(wagrTU( c)) c ∑ wgth( wagrTU(t)) t ∑ ⋅ nbOcc(wagrTU (c)) c ∑ nbOcc( wagrTU(t)) t ∑ ratioTU = wght( wTU(c)) c ∑ wgth(wTU(t)) t ∑ ⋅ nbOcc( wTU(c)) c ∑ nbOcc(wTU(t)) t ∑ sim(TU,agrTU) = ratioTU ⋅ratioagrTU
where the c index is used for indicating common words between the TU and the aggregated TU and the t index, for indicating all the words of the TU or the aggregated TU.

The square roots aim at offsetting the effect of the products not to have too small values. We apply the same principles as for the activation process concerning the inferred words and the words with a low weight. The value of the threshold under which a new domain is created is 0.25.

The aggregation of a TU to a domain is a very simple operation since both have the same structure. It mainly consists in merging two lists of weighted words. As the weight of a word is dynamically evaluated from a number of occurrences, the aggregation can be viewed as an addition. If a word of the TU does not already exist in the domain, it is added to it with its modulated number of occurrences in the TU. If it already exists, its number of occurrences is added to the domain's one. This is done separately for the words from the texts and for the inferred words.

EXPERIMENTS

Experiments with a large set of texts

The validation of our method has been done by processing one month (may 1994) of AFP news wires, that is to say a set of 5949 texts that are 190 words long on average. Following the segmentation stage, 8601 TUs have been built. As for the example in the figure 2, we have used a window of 19 words wide. Experiments with a small set of texts has showed that the segmentation is quite the same for windows from 11 to 19 words wide. The learning stage has produced 3240 aggregated TUs. 691 are the result of at least two aggregations. The more aggregated TU gathers 413 TUs but most of the significant aggregated TUs results from 10 to 100 aggregations. Table 1 gives an example of one of these aggregated TUs, which gathers 61 text segments about terrorism. We have observed that such domains seem to be reliable as their most representative words are coherent from a thematic point of view and stable after some aggregations. More precisely, the domains become stabilized after about twenty aggregations. This is illustrated by the figure 4 which shows the change rate of the first 30 words of the aggregated TU in table 1. This rate takes into account at the same time the words, their weight and their rank.

Figure 4 The evolution of the head of the aggregated TU in table 1 If we look more closely at the evolution of individual words in a domain, we recognize the same trends as for the whole domain. We can see on the figure 5 that during a first stage, the evolution is rather erratic and fast. After about twenty aggregations, it is more steady. Moreover, the significance of meaningful words such as 'kill' or 'attack' increases while more general words such as 'night' or 'Sunday' that have no special role in the domain become less and less important.

Figure 5 The evolution of some words of the aggregated TU in table 1 We have observed, as it was expected, that the aggregated TUs contain a lot of noise. The aggregated TU in table 1 for example holds 705 text words and 401 inferred words 2 but only 12 text words and 66 inferred words have a weight high enough to be used for domain activation or similarity computing.

Evaluation and discussion

2 On average, the inferred words are as numerous as the text ones but there may be quite large variations.

We have evaluated more particularly the three main principles of the method. First, as learning is incremental, we have tried to study the influence of the order of the texts. As a first attempt in this way, we have extracted from the initial set of texts a subset corresponding to some of the domains that had been built and we have processed them as it had previously been done with different changes in the order of the texts. Of course, we have not obtained exactly the same results but these differences mainly concern the domains that do not result from many aggregations. For those which are better confirmed, no significant difference can be observed. So, these elements lead to think that this method is not too sensitive to the order of the texts.

The second point we have tested is the benefit of the inferred words. Globally, when no inferred word is considered, we get many more aggregated TUs, that, of course, gather less TUs. For example, the aggregated TU in table 1 is still built but gathers only 34 TUs even though the 61 TUs grouped by taking the inferred words into account were relevant. Moreover, most of the 27 TUs that are not aggregated any more together are memorized each one as a new aggregated TU. So, as expected, we can say that the inferred words help in having a better similarity between TUs.

The last point we have tested, but perhaps the most important, is to confirm that segmenting texts leads to build finer domain representations. In order to prove this, we have processed all the texts of our corpus without segmenting any one of them. So, each TU was produced from a whole text. The same kind of phenomenon got with the second test about the inferred words has been also obtained, but with a stronger effect. The aggregated TU in table 1 was thus reduced to only 21 TUs. So, by segmenting texts, the system builds a stabilized representation of a domain that can be detected as a good one (cf. figure 4 and5) when without this segmentation, the doamin representation is less distinct and less stabilized, so more difficult to detect as a good one.

RELATED WORKS

Although similar to Kozima's work, our method to segment texts, that consists in moving a window through a text and computing cohesion values from a knowledge source, differs in its application. As Kozima uses word definitions and a propagation of activation process to select related words, we use a collocation network with a selection of the neighbours. In fact these two kinds of networks do not really encode the same knowledge. Our system goes further and automatically segments texts. This enables us to run it on a large amount of texts.

For the learning part, Hovy and Lin propose a method to learn signatures of domains. It requires a pre-classification of texts in the foreseen domains. As this kind of classification is only possible for very large domains, as banking, environment, etc., they form 32 classes made of 300 terms with their relative frequency in the corpus. As the authors say, hundreds or even thousands of different topics are needed for a robust summarization. With our system, signatures for more specialized topics, described by 80 significant words in average, are learned. The number of topics only depends on the subjects developed in the corpus. Descriptions are stable when around 20 discourse segments about a topic are processed. By this way, no a priori classification is needed. As the system is incremental, when new texts are processed, topics are learned or completed without having to process again previous texts.

CONCLUSION

We have developed a complete system that segments texts in thematic units and learn semantic description of specialized domain from the higher cohesive units. We have shown that steady units emerge quite rapidly with an incremental learning. Thematic units can also be viewed as an upper level to the collocation network that enables to structure it. We envisage to pursue on this way by studying the abstraction of the aggregated units and their formation into a hierarchy to build a more powerful knowledge source. Another project is to improve the thematic analyzis process by the feedback of the learned topics. By this way, the system would be able to better analyze currently low cohesive segments and also to recognize and learn domains that were less present in the texts used to build the collocation network.

  are developing automatic construction of text signatures, based on a classification of newspaper texts in very general domains. But a precise analyzis of text topic requires more specialized classes difficult to establish by advance. 1 LIMSI-CNRS. BP 133 -91403 Orsay Cedex. France

Figure 1

 1 Figure 1 Computation of word weight

AFigure 2 A

 2 Figure 2 A text and its cohesion graph (computed for the French text)

Figure 3

 3 Figure 3 The segmented graph

Table 1

 1 The most representative words of an aggregated TU about terrorism

	text words	inferred words
	attack (0.435)	trapped car (0.551)
	bomb (0.244)	bomb attack (0.441)
	police (0.226)	security forces (0.416)
	explosion (0.222)	grenade (0.407)
	to claim responsibility (0.209)	curfew (0.364)


Olivier Ferret
email: ferret@limsi.fr

Brigitte Grau
email: grau@limsi.fr

Nicolas Masson
email: masson@limsi.fr

Thematic segmentation of texts: two methods for two kinds of texts

To segment texts in thematic units, we present here how a basic principle relying on word distribution can be applied on different kind of texts. We start from an existing method well adapted for scientific texts, and we propose its adaptation to other kinds of texts by using semantic links between words. These relations are found in a lexical network, automatically built from a large corpus. We will compare their results and give criteria to choose the more suitable method according to text characteristics.

Introduction

Text segmentation according to a topical criterion is a useful process in many applications, such as text summarization or information extraction task. Approaches that address this problem can be classified in knowledge-based approaches or word-based approaches. Knowledge-based systems as [ Grosz, 1986 #52] require an extensive manual knowledge engineering effort to create the knowledge base (semantic network and/or frames) and this is only possible in very limited and well-known domains.

To overcome this limitation, and to process a large amount of texts, word-based approaches have been developed. [ Hearst, 1997 #57] and [ Masson, 1995 #74] make use of the word distribution in a text to find a thematic segmentation. These works are well adapted to technical or scientific texts characterized by a specific vocabulary. To process narrative or expository texts such as newspaper articles,

[ Kozima, 1993 #72] and [ Morris, 1991 #73] are based on lexical cohesion computed from a lexical network. These methods depend on the presence of the text vocabulary inside their network. So, to avoid any restriction about domains in such kinds of texts, we present here a mixed method that augments [ Masson, 1995 #74] , based on word distribution, by using knowledge represented by a lexical cooccurrence network automatically built from a corpus. By making some experiments with these two latter systems, we show that adding lexical knowledge is not sufficient on its own to have an all-purpose method, able to process either technical texts or narratives. We will then propose some solutions to choose the more suitable method.

Overview

In this paper, we propose to apply one and the same basic idea to find topic boundaries in texts, whatever kind they are, scientific/technical articles or newspaper articles. This main idea is to consider smallest textual units, here the paragraphs, and try to link them to adjacent similar units to create larger thematic units. Each unit is characterized by a set of descriptors, i.e. single and compound content words, defining a vector. Descriptor values are the number of occurrences of the words in the unit, modified by the word distribution in the text. Then, each successive units are compared through their descriptors to know if they refer to a same topic or not. This kind of approach is well adapted to scientific articles, often characterized by domain technical term reiteration since there is often no synonym for such specific terms. But, we will show that it is less efficient on narratives.

Although the same basic principle about word distribution applies, topics are not so easily detectable. In fact, narrative or expository texts often refer to a same entity with a large set of different words. Indeed, authors avoid repetitions redundancies by using hyperonyms, synonyms and referentially equivalent expressions.

To deal with this specificity, we have developed another method that augments the first method by making use of information coming from a lexical co-occurrence network. This network allows a mutual reinforcement of descriptors that are different but strongly related when occurring in the same unit. Moreover, it is also possible to create new descriptors for units in order to link units sharing semantically close words.

In the two methods, topic boundaries are detected by a standard distance measure between each pair of adjacent vectors. Thus, the segmentation process produces a text representation with thematic blocks including paragraphs about the same topic. The two methods have been tested on different kinds of texts. We will discuss these results and give criteria to choose the more suitable method according to text characteristics.

Pre-processing of the texts

As we are interested in the thematic dimension of the texts, they have to be represented by their significant features from that point of view. So, we only hold for each text the lemmatized form of its nouns, verbs and adjectives. This has been done by combining existing tools. MtSeg from the Multext project presented in [START_REF] Véronis | Étiquetage grammatical multilingue: le projet MULTEXT[END_REF] is used for segmenting the raw texts. As compound nouns are less polysemous than single ones, we have added to MtSeg the ability to identify 2300 compound nouns. We have retained the most frequent compound nouns in 11 years of the French Le Monde newspaper. They have been collected with the INTEX tool of [START_REF] Silberztein | INTEX: A Corpus Processing System[END_REF] . The part of speech tagger TreeTagger of [ Schmid, 1994 #163] is applied to disambiguate the lexical category of the words and to provide their lemmatized form. The selection of the meaningful words, which do not include proper nouns and abbreviations, ends the preprocessing. This one is applied to the texts both for building the collocation network and for their thematic segmentation.

Building the collocation network

Our segmentation mechanism relies on semantic relations between words. In order to evaluate it, we have built a network of lexical collocations from a large corpus. Our corpus, whose size is around 39 million words, is made up of 24 months of the Le Monde newspaper taken from 1990 to 1994. The collocations have been calculated according to the method described in

[ Church, 1990 #67] by moving a window on the texts. The corpus was pre-processed as described above, which induces a 63% cut. The window in which the collocations have been collected is 20 words wide and takes into account the boundaries of the texts. Moreover, the collocations here are indifferent to order. These three choices are motivated by our task point of view. We are interested in finding if two words belong to the same thematic domain.

As a topic can be developed in a large textual unit, it requires a quite large window to detect these thematic relations. But the process must avoid jumping across the texts boundaries as two adjacent texts from the corpus are rarely related to a same domain. Lastly, the collocation w1-w2 is equivalent to the collocation w2-w1 as we only try to characterize a thematic relation between w1 and w2.

After filtering the non-significant collocations (collocations with less than 6 occurrences, which represent 2/3 of the whole), we obtain a network with approximately 31000 words and 14 million relations. The cohesion between two words is measured as in [ Church, 1990 #67] by an estimation of the mutual information based on their collocation frequency. This value is normalized by the maximal mutual information with regard to the corpus, which is given by:

Imax = log2 N 2 (Sw -1)
with N: corpus size and S w : window size

Thematic segmentation without lexical network

basic discourse unit, here a paragraph, is represented as a term vector Gi = gi1 ,gi 2, ...,git ( ) where gi is the number of occurrences of a given descriptor in Gi . The descriptors are the words extracted by the pre-processing of the current text. Term vectors are weighted. The weighting policy is tf.idf which is an indicator of the importance of a term according to its distribution in a text. It is defined by:

w ij = tf ij . log N df i
where tf ij is the number of occurrences of a descriptor T j in a paragraph i; df i is the number of paragraphs in which T j occurs and N the total number of paragraphs in the text. Terms that are scattered over the whole document are considered to be less important than those which are concentrated in particular paragraphs. Terms that are not reiterated are considered as non significant to characterize the text topics. Thus, descriptors whose occurrence counts are below a threshold are removed. According to the length of the processed texts, the threshold is here three occurrences. The topic boundaries are then detected by a standard distance measure between all pairs of adjacent paragraphs: first paragraph is compared to second paragraph, second one to third one and so on. The distance measure is the Dice coefficient, defined for two vectors X= (x 1 , x 2 , … , x t ) and Y= (y 1 , y 2 , … , y t ) by:

C X,Y ( ) = 2 w x i ( ) w y i ( ) i =1 t ∑ w x i ( ) 2 + w y i ( ) 2 i =1 t ∑ i = 1 t ∑
where w(x i ) is the number of occurrences of a descriptor x i weighted by tf.idf factor Low coherence values show a thematic shift in the text, whereas high coherence values show local thematic consistency.

Thematic segmentation with lexical network

Texts such as newspaper articles often refer to a same notion with a large set of different words linked by semantic or pragmatic relations. Thus, there is often no reiteration of terms representative of the text topics and the first method described before becomes less efficient. In this case, we modify the vector representation by adding information coming from the lexical network. Modifications act on the vectorial representation of paragraphs by adding descriptors and modifying descriptor values. They aim at bringing together paragraphs which refer to the same topic and whose words are not reiterated. The main idea is that, if two words A and B are linked in the network, then " when A is present in a text, B is also a little bit evoked, and vice versa ". That is to say that when two descriptors of a text A and B are linked with a weight w in the lexical network, their weights are reinforced into the paragraphs to which they simultaneously belong. Moreover, the missing descriptor is added in the paragraph if absent. In case of reinforcement, if the descriptor A is really present k times and B really present n times in a paragraph, then we add wn to the number of A occurrences and wk to the number of B occurrences. In case of descriptor addition, the descriptor weight is set to the number of occurrences of the linked descriptor multiplied by w. All the couples of text descriptors are processed using the original number of their occurrences to compute modified vector values. These vector modifications favor emergence of significant descriptors. If a set of words belonging to neighboring paragraphs are linked each other, then they are mutually reinforced and tend to bring these paragraphs nearer. If there is no mutual reinforcement, the vector modifications are not significant. These modifications are computed before applying a tf.idf like factor to the vector terms. The descriptor addition may add many descriptors in all the text paragraphs because of the numerous links, even weak, between words in the network. Thus, the effect of tf.idf is smoothed by the standard-deviation of the current descriptor distribution. The resulting factor log(

N dfj ⋅ (1+ (tfjk -tfj) 2 k ∑ dfj ))
with k, the paragraphs where T j occurs.

Experiments and discussion

We have tested the two methods presented above on several kinds of texts. Figure 1 shows the results for a newspaper article from Le Monde made of 8 paragraphs. The cohesion value associated to a paragraph i indicates the cohesion between paragraphs i and i+1. The graph for the first method is rather flat, with low values, which would a priori mean that a thematic shift would occur after each paragraph. But significant words in this article are not repeated a lot although the paper is rather thematically homogeneous. The second method, by the means of the links between the text words in the collocation network, Figure 1 -Improvement by the second method with low word reiteration is able to find the actual topic similarity between paragraphs 4 and 5 or 7 and 8. The improvement resulting from the use of lexical cohesion also consists in separating paragraphs that would be set together by the only word reiteration criterion. It is illustrated in Figure 2 for a passage of a book by Jules Verne 1 . A strong link is found by the first method between paragraphs 3 and 4 although it 1 De la Terre à la Lune.

is not thematically justified. This situation occurs when too few words are left by the low frequency word and tf.idf filters.

Figure 2 -Improvement by the second method when too many words are filtered More generally, the second method, even if it has not so impressive an effect as in Figures 1 and2, allows to refine the results of the first method by proceeding with more significant words. Several tests have been made on newspaper articles that show this tendency. Experiments with scientific texts2 have also been made. These texts use specific reiterated vocabulary (technical terms). By applying the first method, significant results are obtained because of this specificity (see Figure 3, the coherence graph in solid line).

Figure 3 -Test on a scientific paper 2 in a specialized domain the contrary, by applying the second method to the same text, poor results are sometimes observed (see Figure 3, the coherence graph in dash line). This is due to the absence of highly specific descriptors, used for Dice coefficient computation, in the lexical network. It means that descriptors reinforced or added are not really specific of the text domain and are nothing but noise in this case. The two methods have been tested on 16 texts including 5 scientific articles and 11 expository or narrative texts. They have been chosen according to their vocabulary specificity, their size (between 1 to 3 pages) and their paragraphs size. Globally, the second method gives better results than the first one: it modulates some cohesion values. But the second method cannot always be applied because problems arise on some scientific papers due to the lack of important specialized descriptors in the network. As the network is built from the recurrence of collocations between words, such words, even belonging to the training corpus, would be too scarce to be retained. So, specialized vocabulary will always be missing in the network. This observation has lead us to define the following process to choose the more suitable method:

Apply method 1; If x% of the descriptors whose value is not null after the application of tf.idf are not found in the network, then continue with method 1 otherwise apply method 2.

According to our actual studies, x has been settled to 25.

Related works

Without taking into account the collocation network, the methods described above rely on the same principles as [ Hearst, 1997 #57] and [ Nomoto, 1994 #70] . Although Hearst considers that paragraph breaks are sometimes invoked only for lightening the physical appearance of texts, we have chosen paragraphs as basic units because they are more natural thematic units than somewhat arbitrary sets of words. We assume that paragraph breaks that indicate topic changes are always present in texts. Those which are set for visual reasons are added between them and the segmentation algorithm is able to join them again. Of course, the size of actual paragraphs are sometimes irregular. So their comparison result is less reliable. But the collocation network in the second method tends to solve this problem by homogenizing the paragraph representation.

As in [ Kozima, 1993 #72] , the second method exploits lexical cohesion to segment texts, but in a different way. Kozima's approach relies on computing the lexical cohesiveness of a window of words by spreading activation into a lexical network built from a dictionary. We think that this complex method is specially suitable for segmenting small parts of text but not large texts. First, it is too expensive and second, it is too precise to clearly show the major thematic shifts. In fact, Kozima's method and ours do not take place at the same granularity level and so, are complementary.

Conclusion

From a first method that considers paragraphs as basic units and computes a similarity measure between adjacent paragraphs for building larger thematic units, we have developed a second method on the same principles, making use of a lexical collocation network to augment the vectorial representation of the paragraphs. We have shown that this second method, if well adapted for processing such texts as newspapers articles, has less good results on scientific texts, because the characteristic terms do not emerge as well as in the first method, due to the addition of related words. So, in order to build a text segmentation system independent of the kind of processed text, we have proposed to make a shallow analysis of the text characteristics to apply the suitable method.

The first method, based on a numerical analysis of the vocabulary distribution in the text, is derived from the method described in[ Masson,

Le vin jaune, Pour la science (French edition of Scientific American),October 1994, p. 18


Olivier Ferret

Brigitte Grau

An Aggregation Procedure for Building Episodic Memory

When dealing with narrative texts, a system must possess a strong domain theory, and especially knowledge about situations occurring in the world. Otherwise the system must envisage comprehension as a complex process including learning from the texts themselves to improve its capabilities. This requires managing past solutions and completing them when analoguous situations happen in other texts, with the purpose of creating general situations. We propose a system, MLK (Memorization for Learning Knowledge), that organizes specific situations in an episodic memory by aggregating the similar ones in a single unit. This aggregation process leads to a progressive enrichment and generalization of the overall situations and of their specific features. MLK is a system conceived to allow the emergence of structures, their accessing being realized by a propagation process. It also maintains a case basis in the purpose of doing a case based reasoning (CBR). Therefore, with MLK, we are able to address the problem of understanding and learning even when a domain theory is lacking.

Introduction

Modeling and using the experience of a system is central for text understanding. All the necessary background knowledge cannot be known by a machine. So a system which takes advantage of the information present in texts and reuses it will be able to improve itself. Psychological studies [Vygotsky, 1962], [Bartlett, 1932] show that, when experiences are memorized, they are grouped according to ressemblance criteria to form a unit, and abstract classes then progressively emerge. The possibility of using known situations related to a new one for understanding it, allows human to complete his own knowledge about this situation and to improve his capacities of understanding. A system applying such a method is permanently evolving and as a result, a same story may be analyzed in different ways at two different times. We are mostly interested in pragmatic knowledge representing concrete situations occuring in the world, traditionnally represented by schemas. This kind of knowledge is necessary to integrate sentences in a context and to infer causal chains between events.

There exist studies about memorizing, understanding and learning as components of a whole process. These systems learn new specialized situations, SWALE [START_REF] Schank | [END_REF] and AQUA [Ram, 1993] by explanation based learning (EBL) and OCCAM [START_REF] Pazzani | [END_REF] by integrating empirical learning and EBL. A common point in these systems is the presence of general knowledge to guide the explanation process.

In contrast, our goal is to build a system able to work even when lacking general pragmatic knowledge about concrete situations. In this context, text analysis rely on linguistic clues, such as causal and temporal information, and on other known similar situations if they exist. These weak methods do not lead to a causal explanation of all the events of a text, and thus their pertinence is not fully justified. In only two particular cases, their presence is not sufficient to conclude on their belonging to a possible general situation. It is by the conjunction of their recurrence and the presence of causal clues in different texts, that abstraction will be possible. Furthermore, all the events describing a situation are not specified in a text, only those which are relevant to the story. That is why a learning process must recognize similar situations to complete them text after text, and not just memorize these situations independantly of each other.

To allow the emergence of pertinent features from all similar situations, our system MLK uses an incremental learning. When memorizing, MLK groups similar situations together to form an aggregated structure, in which similar features are reinforced while rare events become weaker. This aggregation process leads to a progressive enrichment and generalization of the overall situations and of their specific features. This kind of memorization is conceived to build structures on which abstraction of general units will be based and to provide an adaptative retrieval process by propagating activation. The retrieval of situations analoguous to a new one is always dependent on the state of the memory. This approach has several advantages related to the management and the retrieval of similar cases and provides a more psychologically-plausible model of memorization and learning when general background knowledge is lacking.

The MLK system

MLK is initially given a semantic representation of sentences organized in situations. The segmentation currently is done by hand. We use linguistic criteria (causal clues, sentences order and temporal marks) plus the kind of the predicates in each clause. Situations are named thematic units (TUs), because they gather the specific knowledge about a same topic, and representations of texts form episodes: a set of TUs related by thematic links, such as topic shift (another subject) and topic deviation (a particular point). The episodes define more global contexts containing specific situations. A TU is a causal structuration of events. Features contained in each slot are represented by conceptual graphs [Sowa, 1984]. They are derived from the semantic knowledge of the system which is represented by a lattice of types of concepts associated to canonical and definition graphs. The canonical graphs contain semantic constraints on the casual roles fillers. In definition graphs, more precisions about the roles are available, as well as the predicate consequences.

The aggregation process relies on similarities between situations. Two situations are similar if their causal structure and their features are analoguous. A similarity measure has been defined on the basis of the features of the structure and of the structure itself. The process leads to gathering similar features and to reinforcing them by augmenting a weight. Other features are simply added. The reinforcement of elements implies the weakening of the others. By iterating this process, a situation will be progressively completed and the most recurrent features describing it will emerge. They will be the candidates for the description of the abstracted situation.

We treat short narratives texts, such as those found in newspapers, that may reference more than one situation. For example, an airport murder attempt, an aggression, a quarrel, politic murders, all describe analoguous situations that lead to progressively build a single aggregated TU about an attempted murder, described in figure 3 (section 3).

The aggregation process also provides a good answer to the case retrieval problem. In most CBR systems, cases are indexed by predetermined features. In [START_REF] Kolodner | [END_REF], cases are classified according to general situations and the access mode is based on the traversal of a network of discriminent indices. In AQUA, cases are indexed by several features, especially by the general situations (MOPs) involved. But when lacking general situations, the system does not know what it is learning about and indices cannot be used. Another approach is to perform the retrieval of cases by a propagation process, as presented in REMIND [Lange and Wharton, 1993]. Propagation requires weighting the features of the structure. In REMIND, this task is made by hand when given the domain knowledge. In MLK, the aggregation leads to computing all the weights and to dynamically modifying them according to the experience. Retrieval criteria evolve while the memory content changes without maintaining an explicit structure of indexation features. The problem of deciding what features are pertinent for retrieving a structure does not occur. The spreading activation network encodes knowledge about concepts and situations. Concepts can be viewed as indices for situations, because they are part of the conceptual graphs that represent the features of the TUs. Furthermore they create links between TUs, other than the thematic links.

When analyzing a text, sentences are decomposed in clauses, and the MLK retrieval process is given each concept of a clause. Units in the network representing these concepts are clamped to high level of activation. Activation is then spread into the network. As the activation function encodes the prior context, situations that fit with the current clause and are coherent with the context are highly activated.

Thus the aggregation mechanism provides an answer to the organization and structuration of cases in an episodic memory in the purpose of learning from texts, even when general situations do not guide the process. Our model satisfies two constraints: the need for allowing incremental learning independantly of the domain and for being a case basis for CBR.

The aggregating episodic memory

TUs representation, or encoding of episodes

A text is represented by an episode which is a structured by a set of TUs. One of them encodes the main topic of the episode, the others are linked to this main situation by thematic links. TUs can be considered as instances of schemas. They encode causal and temporal knowledge between events of a specific situation issued from a text analysis. Their representation formalism is derived from the schema representation choosen, which is close to MOPs [START_REF] Schank | Dynamic Memory: a Theory of Reminding and Learning in Computers and People[END_REF]. Figure 1 shows the segmentation of a text, the distribution of the clauses in the TUs and details the Attempted_Murder TU.

A few years ago, [I was in a department store in Harlem](1) [with a few hundred people around me](2). [I was signing copies of my book "Stride toward Freedom"](3) [which relates the boycott of buses in Montgomery in 1955-56](4). Suddenly, while [I was appending ma signature to a page](5), [I felt a pointed thing sinking brutally into my chest](6). [I had just been stabbed with a paper knife by a woman](7) [who was acknowledged as mad afterwards](8). [I was taken immediately to the Harlem Hospital](9) [where I stayed on a bed during long hours](10) while [many preparations were made](11) [in order to remove the weapon from my body](12).

Main Topic

(1), ( 2), ( 4)

[ (6) (7) ] (10) (11) MLK Attempted Murder TU Dedication meeting TU Hospital TU shift deviation (8) C D (9) C D (12) D [ (3) (5) ] Circumstances [Located] - (experiencer) -> [Man:MLK] (location) -> [Store] [Mad] - (experiencer) -> [Woman] Description [Stab] - (agent) -> [Woman] (recipient) -> [Chest] - (part) -> [Man:MLK] (instrument) -> [PaperKnife] (manner) -> [Brutally] [Take_Hospital] - (agent) -> [HumanBeeing] (patient) -> [Man:MLK] (destination) -> [Hospital] (manner) -> [Quickly] Outcomes [Wounded] - (experiencer) -> [Man:MLK] [Patient] - (experiencer) -> [Man:MLK]
Figure 1: A text and its representation A TU is described by three slots: Circumstances, Description and Outcomes. The slot Circumstances is valued by a set of conceptual graphs that represent the states known when the situation occurs. Conceptual graphs in the Description slot represent the events which take place and are partially ordered by chronological links. The Outcomes slot contains the resulting states and is also valued by a set of graphs. We can see that some conceptual graphs are issued from semantic inferences, as Patient and Wounded. The conceptual graphs are build around a predicate. The predicate is the central concept when describing an event; its type is a sub-type of action, processus or state. The other concepts in the graphs fill the casual roles linked to the predicate, whose type values must be specializations of the types coming from the canonical or definitions graphs (we will call these latter types 'reference types').

Similarity

The aggregation process requires that MLK has found known situations in memory similar to the new TUs. Situations in memory result from preceding aggregations and are named aggregated TUs. The aggregation takes place at two levels. At the episode level, its purpose is that global contexts emerge by the mean of recurrent sets of situations. At the TU level, its purpose is to learn about a situation by incrementally completing it, while recurrent events emerge. At both level, the aggregation process has to evaluate the similarity of TUs with aggregated ones.

The similarity measure we use [START_REF] Ferret | An episodic memory for understanding and learning[END_REF] is decomposed in two steps. Global similarity is based on the number of similar events, according to the slots they belong to. The exact degrees of similarity of slots and events are examined when this global similarity gives a medium result. Two events are similar if their predicates contain the same type and if at least one of their concepts filling casual roles is similar. This occurs if their types share a supertype inferior to the reference type of the casual role. The degree of similarity of events and TUs is computed respectively on the basis of the weights of concepts and graphs. An example is given in section 5.

This similarity measure results in gathering features that belong to a same topic, without consideration of a description level. Situations in texts which refer to the same topic are often different specializations, in which some events are the same and roles are different. An aggregated TU is conceived to be the basic structure on which abstraction will rest. It will be in charge of this latter process to eventually split a memorized situation into several units, general and specialized schemas, according to the weights of the events and concepts. If the similarity criteria were more closed, each aggregated TU would be too specific, and the common points of a general unit would not emerge.

Episode aggregation

At the episode level, MLK reinforces configurations of similar situations. Aggregation in these cases consists in the reinforcement of the common thematic links and the aggregation of the related TUs.

At the TU level, the graphs of events that have the same predicate are aggregated, the others are added. Same causal or temporal relations between graphs are also reinforced. Aggregation of graphs leads to progressively generalizing their concepts.

As previously mentionned, aggregated TUs result from successive aggregations in the episodic memory. So, they are structures like the TUs, whose features are weighted aggregated graphs. This kind of graphs is defined as an extension of conceptual graphs in such a way as to maintain the capability of applying the basic derivational operations. We have added to them the similarity computation and the aggregation process. The aggregation process is defined as a maximal join where predicates must join: same casual roles are joined and their types of concepts are abstracted as in figure 2. New relations and concepts are added.

(part) [1,2] Head-of-State [1], Young-Man [2] (instrument) (1.0) -> [Knife] (1.0) (instrument) [1,2] Bayonet [1], Flick knife [2]
Figure 2: An aggregated graph Types of aggregated concepts are computed at each aggregation. They are the most specific concept abstraction (msca), different from the reference type, of all the aggregated instances. If such a type does not exist in the lattice, we choose the msca that groups the maximum of instances if it is possible. To compute it, each aggregated concept keeps the instances it comes from. For each of these instances, we also keep the specific episode it is part of (as [1] in the figure). This way, we can rebuild all the specific situations which have contributed to the formation of an aggregated TU. This capability is preserved with the purpose of retrieving specific links between graphs. It will be useful to justify a reasoning based on the aggregated situation, TU aggregation being done irrespective of shared instances between graphs. For example, if an agent of an event is also the patient of another event in the same situation, this piece of knowledge is not maintained at the aggregat level since each aggregated concept type evolves inside its own graph regardless of the evolution in the other graphs. This kind of knowledge is also basic to schemas abstraction; it prepares the formation of roles. The last characteristic added on the aggregated concepts is a counter to compute their weight. Weights on the predicates represent the importance of the event inside the TU and weights on the other concepts the importance of the concept in the graph. These counters are equal to the number of aggregations. Thus, the weight of an event is computed by dividing the counter of the predicate by the number of times the TU has been aggregated. In the same way, the weight of a concept is the counter of the concept divided by the number of aggregations of the predicate. Weights on relations between two graphs are the number of aggregations divided by the number of common episodes between the two graphs. This example, in which five TUs have been aggregated, only show the predicates of the graphs with their weights and the episodes they belong to. Events in the description slot are chronologically ordered. For presentation purpose,these relations, and the aggregated concepts have not been mentionned. Only causal relations between actions and their results are precised. States staging a situation are extremely various in texts, and often without explicit causal relations, so they are all considered as possible circumstances. At this state of the memorization, none emerge completely, but we can note that some are semantically close, Located vs Live and Disagree vs Threatened. Events in the description slot are more interesting with a characteristic event always reinforced, Stab. Others have to be confirmed before deciding of their relevance, like Arrest. Notice that the reinforcement of a causal relation between two events is also an indication of their interest. Weak weights on events can be interpreted as anecdotes (Stumble) or events that do not really belong to the situation. Outcomes are often linked to an action and are significative. A discussion about the formation of this TU is presented in section 5.

The retrieval process

A spreading activation mechanism makes possible to use the episodic memory as an associative memory in order to select the relevant knowledge for processing the clauses coming from the texts. The figure 4 shows activations of four aggregated graphs resulting from the network after it successively receives as input the clauses of the following little story: are part of the GoingSupermarket TU. On the contrary, the graphs of the RepairingCar aggregated TU are not activated because nothing is mentioned about the situation of repairing a car. When the second sentence is introduced (after cycle ##), the graphs of the GoingSupermarket TU are still highly activated. This is the result of two influence streams. First the previous activation state of the memory created a context which constrains its evolution. Second, concepts coming from the sentence (in this case, the concept Buy) confirm the previous topic. But we can see also that others concepts (SparePart, Car, Repair) make another topic appear. This explains why the graphs of the RepairingCar TU, and the TU itself, begin to be activated. After the processing of the third sentence (after cycle ##), the context effect of the memory for the first topic is not significant any more (the previous confirmation was not very strong) and no element of this third sentence is specifically linked to it. On the contrary, it strenghtened the second topic. This explains why we can observe that the activation of the elements of the GoingSupermarket TU decreases rather strongly and that the opposite effect happens for the elements of the RepairingCar TU.

The spreading activation mechanism which supports this selecting process is divided in two steps.

The first step consists in defining a subset of the memory in which the selection will be done. The episodic memory may be very large if the system has a great amount of experiences. Hence it is not realistic on a computational point of view to involve the whole of the memory in the core selection mechanism. Moreover, this could be a source of noise and disturb the selection process. It is of course necessary in this task to bypass some similarity failures: the above little story does not tell us about a supermarket but the GoingSupermarket TU, which is the best thematically related TU of the memory, has been nevertheless retrieved. This is due to the spreading of the activation flow towards more general or more specific concepts than the ones initially clamped. But this flow has to stay around the initial concepts. Thus it is not interesting to select a surtype of Supermarket as PublicPlace because we do not want to activate all the situations which take place in a public place.

The definition of this subset of the memory is based on the propagation of a constant flow of activation in the network, a flow that starts from the concepts that make up the clauses of the texts. As the global amount of activation that can be used for the propagation is always the same, the activation level of the units is less and less high as these units are more and more distant. When the activation level of an unit is under a given threshold, the propagation towards its next units is stopped. In the lattice of concepts type, a specific mechanism makes more activation going towards subtypes of a concept type than toward its surtypes.

The second step of the spreading activation mechanism aims at selecting the aggregated TUs in the episodic memory that are the most relevant with regard to the clauses which are considered at a given stage of the analysis of a text. This process is akin to the evidential activation in REMIND. When this working mode is active, the network mentioned above, which is a recurrent one due to the symmetry of the connections, has a two-phases dynamics: at the beginning, it has great liberty to explore the space of possible states and this liberty is restrained progressively in order to make the network converge on one state. This is achieved locally by the activation function of the units through its divisor term:

A i (t + 1) = w ij ⋅ A j (t) j ∑ t 2 + A i (t)
with A i (t): activation level of unit i after t cycles w ij : weight of the connection between unit i and unit j The second term of this function is particularly significant since it is the support of the context effect mentioned above which makes the network take into account the result of the previous spreading activation sessions.

Discussion

Processing of texts

We give here a complete example of the treatment done by MLK. The memory contains in particular the TU Attempted_Murder described in figure 5 resulting from the processing of five texts. The creation of the TU comes from the first episode, Airport_Murder_Attempt because none similarity has been found with existing TUs. The other texts, a Quarrel [2], two Politic_Murders [3] and [4] and an Aggression [5], contain a situation matching with the evolutionary aggregated Attempted_Murder TU. With the episodes [2] and [3], the similarity results from a deep comparison of the graphs while with the two last episodes, it results more from the global measure. Thus, more the TU is growing, more the similarity becomes obvious. The new processed text has been given in figure 1. We will focus on the processing of the TU MLK_Attempted_Murder. Each graph causes a propagation and leads to highly activate the Attempted_Murder unit. The Circumstances and Outcomes slots are strongly similar while the Description slot has been found similar after a deep evaluation. Therefore aggregation is done; results are given in figure 5.

The aggregated TU has been enriched by new events. Comparison of the weights before and after aggregation, shows that they increase with reinforcement while decreasing in the opposite case. Even with only six examples, a structure begins to emerge, and overall makes sense. Our method gathers events that are thematically linked, and even if misunterstandings occurs when segmenting texts, the aggregation will remedie them in the long term. Aggregation provides a strong process where some noises are allowed.

Towards abstraction

At this state of structuration, we can notice in the evolution of the aggregated TU some indications about further abstraction. Strongly weighted events will belong to a general situation, as Stab, events as Arrest have to be confirmed. When events, such as Dead and Wounded, are not simultaneously present in the different episodes but are causally linked to a same action, this will suggest creating a generalized event for them in the general structure, with two specializations including these specific events. Thus, an aggregated structure will lead to create schemas hierachically structured.

Generalization of concepts, see figure 2 , also prepares the abstraction phase. Information that will be used are weights, but also the distribution of the episodes and the aggregated relations.

A reasoning medium

The episodic memory is build in the purpose of learning and improving the comprehension. We have also conceived it as a case basis. Enrichment of TUs will allow to better understand and make inferences. For example, when analyzing the fifth episode, it is said that the agressor is imprisonned. Because this kind of fact has been memorized as the outcome of the Arrest event with an important weight, the arrestation of the agressor could be inferred. This kind of inference can be justified because the roles are identical in the specific situations.

Comparison with other models

AQUA is the closest system to MLK in term of their goals. It learn explanation patterns (XPs), even if incomplete. These XPs are completed when finding the lacking explanation in further texts. But processes are quite different. AQUA needs a strong domain theory to build its explanations. This knowledge is represented by MOPs and abstract explanation patterns, and AQUA learns new specializations. Learning and generalization occur at each new case. Generalization relies on the explicative structure even if some actions need further explanations. In MLK, to avoid the need of general descriptions in all domains, causal links come from linguistic clues, from the assumption that texts are coherent by themselves and from semantic knowledge. If these links are recurrent, they will be confirmed. On the other hand, if they are unusual or result from a misinterpretation, they will desappear by nonreinforcement. So generalization is done in two steps. The aggregation principle allows pertinent events to appear with their inter-relations. It replaces the explanation mechanism needed to justify events and solves the incremental aspect of learning. The second step of abstraction, where events and roles are abstracted to produce general situations must be realized by another process, when situations in the episodic memory are stabilized.

Case retrieval is quite different in MLK and problems of misindexation solved by AQUA do not occur. It is closer to REMIND which integrates episodic memory retrieval and comprehension in the same propagation process. Comparison is only done on the episode retrieval results, since comprehension is quite different when dealing with incomplete knowledge. Differences come from the integration and the structuration of episodes. First, updating of the weights in MLK is automatically done. Second, frames in REMIND are intermediate between our semantic graphs and the TUs; episodes in REMIND are analoguous to our TUs. TUs are much more structured units where all the frames explaining an episode are gathered. In MLK, weights on events code the importance of the frame in the episode. Thus, this upper level influences the spreading of the activation and selected TUs are thematically close, not only superficially, as they can be in REMIND.

Conclusion

In this article, we have presented MLK, an episodic memory model which has been designed to support a comprehension process tightly tied to learning. In this model, text representations built by the comprehension process are stored in a memory in order to be used later by this same process to analyse other texts. But unlike traditional CBR systems, the memorization here does not consist in tidying up a new element in an already existing box. By aggregating the text representations, the similar situations they mention form aggregated units containing events having a weight which characterizes their recurrence degree. This allows a new sort of knowledge to emerge. Weights are used in order to support the retrieval process in the episodic memory: a spreading activation mechanism which relies on these weights selects the aggregated units of the memory that are the most relevant according to both the current input and the context settled by the previous inputs. So, even when a strong domain theory is absent, the MLK model is able to memorize what a comprehension process produces and to organize it in such a way that it will be able to recall it later in a contextually relevant way. Moreover, knowledge that support this capability evolve progressively as new text representations are memorized.

On its present state, our memory model is implemented in Smalltalk and has been tested with a set of 500 conceptual frames (type concepts and the canonical graphs associated to them) and 30 TUs coming from 15 text representations. For these tests, the text representations were produced by hand but an algorithm for segmenting a text according to the situation it mentions has been developped and is now under testing. It relies on the episodic memory and its selection mechanism. It is associated to a linguistic based module more specifically in charge of building the internal representation of the TUs. So, in the future, we intend to integrate all these aspects in order to explore more deeply the interest of linking strongly learning and understanding.

Figure 4 :

 4 Figure 4: Activation level of TUs

  Figure 5: A resulting TU after the aggregation process