Mining Textual Associations in Text Corpora

Gaël Dias
Universidade da Beira Interior
Dept. de Matematica e Informatica
6200-001 Covilha Portugal
00 351 93 328 37 60
ddg@di.fct.unl.pt

Sylvie Guilloré
Université d’Orléans
LIFO
45061 Orléans France
00 33 2 38 41 72 65
guillore@lifo.univ-orleans.fr

José Gabriel Pereira Lopes
Universidade Nova de Lisboa
Dept. de Informatica
2725-114 Caparica Portugal
00 3511 295 44 64
gpl@di.fct.unl.pt

ABSTRACT
Identifying textual associations from text corpora is a useful pre-processing step for many applications in Natural Language Processing. In this paper, we will present an innovative system that extracts relevant sequences of characters, words and part-of-speech tags from corpora. We will show that the combination of a new association measure (Mutual Expectation) with a new acquisition process (LocalMaxs) proposes an integrated solution to the problems of bootstrapping techniques and global thresholds highlighted by previous researches.
Keywords
Textual Associations, Positional n-grams, Mutual Expectation.
1.	INTRODUCTION
Identifying textual associations from corpora is a useful pre-processing step for many applications in Natural Language Processing. For instance, "Bill of Rights", "as well as" and "to comply with" are multiword lexical units that should be identified within the process of text normalisation. But, textual associations are not restricted to word associations. It is clear that systems that may identify meaningful part-of-speech tags associations such as "AT JJ NN", "JJ NP CC JJ NP", "NP $ JJ NN", "NP CO NP CO NP CC NP" and "HV RB BEN" would greatly benefit specific tasks like Bilingual Alignment or Text Summarisation. Finally, in the context of character associations, it is convenient to define morphological segments as meaningful sequences of characters that should be automatically extracted from corpora. For instance, the following words belong to the same semantic family as they share the same stem: oceanography, oceanarium, oceanic and ocean. In order to identify and extract meaningful sequences of words, part-of-speech tags and characters, we present a statistically-based architecture called SENTA (Software for the Extraction of N-ary Textual Associations) that retrieves, from naturally occurring text, relevant contiguous and non-contiguous textual associations. For that purpose, we combine a new association measure called the Mutual Expectation with a new acquisition process called the LocalMaxs algorithm. 
2.	DATA PREPARATION
Most relations between textual units (TUs) occur within a local context (span) of at most six other textual units. As a consequence, a textual association can be defined in terms of structure as a specific n-gram calculated in an immediate span of three TUs to the left hand side and three TUs to the right hand side of a focus TU, as illustrated in Figure (1).

Figure 1: Local context of a focus TU
By definition, an n-gram is a vector of n TUs where each TU is indexed by the signed distance that separates it from its associated focus TU. Consequently, an n-gram can be contiguous or non-contiguous whether the TUs involved in the n-gram represent or not a continuous sequence in the corpus. By convention, the focus TU is always the first element of the vector and its signed distance is equivalent to zero. We represent an n-gram by a vector of TUs [p11 u1 p12 u2 ... p1i ui ... p1n un] where p11 is equal to zero and p1i (for i=2 .. n) denotes the signed distance that separates the TU, ui, from the focus TU, u1. 
3.	MUTUAL EXPECTATION
In order to evaluate the degree of cohesiveness existing between Tus in an n-gram, various mathematical models have been proposed [1] [4] [5] [8]. However, most of these models only evaluate the degree of cohesiveness between two TUs and do not generalise for the case of n individual TUs (i.e. n, n  2). As a consequence, these association measures only allow the acquisition of binary associations and bootstrapping techniques have to be applied to acquire associations with more than two TUs. Unfortunately, such techniques have shown their limitations as their retrieval results mainly depend on the identification of suitable 2-grams for the initiation of the iterative process. On the other hand, these models have shown to be over-sensitive to frequent TUs [2]. In particular, in the context of word associations, this has lead researchers to regard function words like determinants or prepositions as meaningless to the sake of the statistical evaluation process. In order to overcome both problems, we present a new association measure called the Mutual Expectation, introduced by [3], that evaluates the degree of cohesiveness that links together all the TUs contained in an n-gram (n, n  2) based on the concept of Normalised Expectation.
3.1	Normalised Expectation
The basic idea of the Normalised Expectation (NE) is to evaluate the cost of loosing one TU in a given n-gram. Thus, the less an n-gram would accept the loss of one of its components, the higher its NE value should be. The extraction of one textual unit at a time from a generic n-gram  [p11 u1 p12 u2 ... p1i ui ... p1n un] gives rise to the occurrence of any of the n events shown in Table (1) where the underline (i.e. "___") denotes the missing TU from the n-gram. 

Table 1. (n-1)-grams and missing textual units.
 (n-1)-gram	Missing TU	
[ ____ p12 u2  p23  u3 ... p2i  ui ... p2n  un]	p11 u1	
[p11 u1 ___  p13 u3 ... p1i ui ... p1n un]	p12 u2
	
...	...	
[p11 u1 p12 u2 ... p1(i-1) u(i-1) ___ p1(i+1) u(i+1) ... p1n un]	P1i ui	
...	...	
[p11 u1 p12 u2 p13 u3 ... p1i ui ... p1(n-1) u(n-1)  ___ ]	p1n un	

Each event may be associated to a respective conditional probability that evaluates the expectation to occur the missing textual unit knowing its corresponding (n-1)-gram. So, the normalisation of the conditional probability is realised by the Normalised Expectation which is defined in Equation (1).

where 

Equation 1.  Normalised Expectation.
In particular, the "^" corresponds to a convention frequently used in Algebra that consists in writing a "^" on the top of the omitted term of a given succession indexed from 2 to n.
3.2	Mutual Expectation
Many applied works in Natural Language Processing have shown that frequency is one of the most relevant statistics to identify relevant textual associations. From this assumption, we deduce that between two n-grams sharing the same NE, the most frequent n-gram is more likely to be a relevant textual association. So, the Mutual Expectation of an n-gram is the product between its NE and its relative frequency as defined in Equation (2).

Equation 2.  Mutual Expectation.
4.	LOCALMAXS
Most of the approaches have based their selection process on the definition of global thresholds of frequency and/or association measure [1] [4] [7] [8]. However, these thresholds are prone to error as they mainly depend on experimentation. Furthermore, they highlight evident constraints of flexibility, as they need to be re-tuned when the type, the size, the domain and the language of the input corpus change. In order to deal with both problems, [3] has introduced the LocalMaxs algorithm that concentrates the acquisition process on the identification of local maxima of association measure values. The LocalMaxs is defined in Algorithm (1) being assoc any association measure, W an n-gram, n-1 the set of all the (n-1)-grams contained in W, n+1 the set of all the (n+1)-grams containing W  and sizeof a function that returns the number of TUs in an n-gram.

xn-1 , yn+1  W  is a Textual Association if		
(sizeof(W)=2    assoc(W) > assoc(y)) 
(sizeof(W)2   assoc(W)  assoc(x)    assoc(W) > assoc(y))		
Algorithm 1.The LocalMaxs algorithm.
The LocalMaxs algorithm has interesting properties as it allows the election of overcomposed n-grams (i.e. n-grams that contain other elected sub-ngrams).
5.	CONCLUSION
SENTA has been applied over three data sets (words, tags, characters) built from the part-of-speech tagged version of the Brown corpus (1 million words). In the context of word associations, the results point at the extraction of compound nouns and verbs, and various types of multiword locutions. Analogously, the system retrieves NP, VP, SV and VO chunks from the corpus of part-of-speech tags. And prefixes, suffixes and stems have been identified in the context of characters.
6.	REFERENCES
[1]	Church K. and P. Hanks, “Word association norms mutual information and lexicography”, Computational Linguistics, 16(1):23-29 (1990).
[2]	Dias G., S. Guilloré and J.G.P. Lopes, “Normalisation of Association Measures for Multiword Lexical Unit Extraction”, Proc. International Conference on Artificial and Computational Intelligence for Decision, Control and Automation in Engineering and Industrial Applications, Monastir, Tunisia (2000).
[3]	Dias G., S. Guilloré and J.G.P. Lopes, “Language Independent Automatic Acquisition of Rigid Multiword Units from Unrestricted Text corpora”, Proc. Traitement Automatique des Langues Naturelles, France (1999).
[4]	Dunning T., “Accurate methods for the statistics of surprise and coincidence”, Association for Computational Linguistics, 19(1) (1993).
[5]	Gale W., “Concordances for parallel texts”, Proc. 7th Annual Conference  of the UW Center for the new OED and Text Research using corpora (1991). 
[6]	Silva J., G. Dias, S. Guilloré and J.G.P. Lopes, “Using LocalMaxs Algorithm for the Extraction of Contiguous and Non-contiguous Multiword Lexical Units”, Proc. 9th Portuguese Conference in Artificial Intelligence, Lecture Notes, Springer-Verlag, Évora, Portugal (1999).
[7]	Shimohata S., “Retrieving collocations by co-occurrences and word order constraints”, Proc. ACL-EACL (1997).
[8]	Smadja F., “Retrieving collocations from text: XTRACT”, Association for Computational Linguistics, 19(1), (1993).