We present an application of Formal Concept Analysis in the domain of Natural Language Processing: We give a general overview of the framework, describe its goals, the data it is based on, the way it works and we illustrate the kind of data we expect as a result. More speci cally, we examine the ability of the stability, separation and probability indices to select the most relevant concepts with respect to our FCA application. We show that the sum of stability and separation gives results close to those obtained when using the entire lattice.
Ideally natural language processing (NLP) applications need to analyse texts to
answer the question of \Who did What to Whom". For computers to e ectively
extract this information from texts, it is essential that they be able to detect
the events that are being described and the event participants. Because events
are mostly lexicalised using verbs, one ingredient that is essential for such
systems is detailed knowledge about their syntactic and semantic behaviour. It has
been shown (
To help computer systems in this task of understanding and representing the full meaning of a text, verb classi cations have been proposed which group together verbs with similar syntactic and semantic behaviour, ie. which associate groups of verbs with subcategorisation frames showing the syntactic constructions the verbs may appear in and sets of thematic roles which represent the participants in an event described by the verbs in the group.
For English, there exist several large scale resources providing verb classes
(eg. Framenet
For French however, existing verb classes are either too restricted in scope
(Volem Saint-Dizier (1999)) or not su ciently structured (the LADL tables
In this paper we present a method for providing a VerbNet style classi cation of French verbs which associates verbs with syntactic constructions on the one hand and sets of semantic role sets (the set of semantic roles participating in the event described by the verb) on the other. To obtain this classi cation, we build and combine two independent classi cations. The rst is semantic and is obtained from the English VerbNet (VN) by translation, the second is syntactic and is obtained by building an FCA (Formal Concept Analysis) lattice from three, manually validated syntactic lexicons for French. The rst associates groups of French verbs with the semantic roles of the English VN class. The second associates groups of French verbs (the concept extent) with syntactic constructions (concept intent). We then merge both classi cations by associating with each translated VN class, the FCA concept whose verb set yields the best F-measure with respect to the verb sets contained in each translated VN class. We thus e ectively associate the set of semantic roles of the VN class to the group of French verbs and the syntactic information given by the FCA concept.
In the past several linguistic FCA applications have been presented, as Priss
(2005) shows in her overview. For example, Sporleder (2002) describes an FCA
based approach to build structured class hierarchies starting from unstructured
lexicon entries while the features used for building classes in the approach
presented in
In the following we rst introduce the terminology and data used in our
application domain. Next we describe how we associate groups of French verbs
with syntactic information using Formal Concept Analysis (Section 3). As the
resulting concept lattice has a very large number of concepts which are mostly
not useful verb classes we explore methods to select the concepts most relevant
to our application (Section 4). We show in particular that selecting only 10%
of the concepts of the lattice using indices proposed in
Our aim is to build a lexicon associating groups of French verbs with: 1) the syntactic constructions the verbs of this group may appear in, 2) the semantic roles participating in an event described by a verb of this group. Syntactic constructions a verb may occur in are described using subcategorisation frames (SCF) and are usually part of a lexical entry describing the verb. A subcategorisation frame (SCF) characterises the number and the type of the syntactic arguments expected by a verb. Each frame describes a set of syntactic arguments and each argument is characterised by a grammatical function (eg. SUJ - subject, OBJ - direct object etc.) and a syntactic category (NP indicates a noun phrase, PP a prepositional phrase, etc.). For example John throws a ball to Mary. is a possible realisation of the subcategorisation frame SUJ:NP V OBJ:NP POBJ:PP.
The semantic (thematic) roles are the participants in an event described by
a particular verb. To date there is no consensus about a set of semantic roles
or a set of tests determining them. There may be a general agreement on a
set of Semantic Roles (eg. Agent, Patient, Theme, Instrument, Location, etc.)
but there is substantial disagreement on when and where they can be assigned
(Palmer et al., 2010). Thus each of the well known resources (FrameNet
Thus, from this data an English NLP system analysing the sentence John threw a ball to Mary could infer the semantic roles involved in the event, namely those given by the VerbNet class. It could also detect the possible semantic roles realised by the syntactic arguments: It would know that the subject is a realisation of the Agent semantic role, the object of the Theme or Destination semantic roles, etc.
To associate French verbs with syntactic frames, we use the FCA classi cation approach where the objects are verbs and the attributes are the subcategorisation frames associated with these verbs by the subcategorisation lexicon to be described below. 3.1
Subcategorisation information is retrieved from three existing lexicons for French:
Dicovalence van den Eynde and Mertens (2003), the LADL tables
SUJ:NP,OBJ:NP,POBJ:PP,POBJ:PP LA:38L
Table 1: Sample entries in subcategorisation lexicon for verb expedier (send). a concept lattice based on the formal context hV; F; Ri such that: { V is the set of verbs in our subcategorisation lexicon. We ignore verbs with only one SCF as they will result in classes associating verbs with a unique frame. { F is the set of subcategorisation frames (SCFs) present in the subcategorisation lexicon, { R is the mapping such that (v; f ) 2 R i the subcategorisation lexicon associates the verb v with the SCF f .
The resulting formal context is made of 2091 objects (verbs) and 238 attributes (frames), giving rise to a lattice of 12802 concepts. Clearly however not all these concepts are interesting verb classes. Classes aim to factorise information and express generalisations about verbs. Hence, concepts with few (1 or 2) verbs can hardly be viewed as classes and similarly, concepts with few frames are less interesting.
To select from this lattice those concepts which are most likely to provide
the most relevant verb-frame associations, we explore the use of three indices for
concept selection: concept stability, separation and probability which have been
proposed and analysed in
The lattices we have to deal with are very large and many of the concepts do not
represent valid verb classes. To select those concepts which are most relevant in
the context of our application the concept lattice needs to be ltered.
V j A0 = F gj 5: 2jV j Intuitively, a more stable concept is less dependant on any individual object in its extent and is therefore more resistant to outliers or other noisy data items. Concept separation indicates the signi cance of the di erence between the objects covered by a given concept from other objects and, simultaneously, between its attributes and other attributes: s((V; F )) = Pv2V jfvg0j + Pf2F jff g0j jV j jF j
: jV j jF j Intuitively we expect a concept with high separation index to better sort out the verbs it covers from other verbs and simultaneously the frames it covers from other frames. Whereas concept stability is a measure concerned with either objects or attributes, separation gives information about objects and attributes at the same time.
Concept probability. For an attribute a 2 A, the attribute set, we denote by pa the probability of an object to have the attribute a. In practise it is the proportion of objects having a: pa = jfag0j ; where O denotes the set of objects.
jOj For B A, we de ne pB as the probability of an arbitrary object having all attributes from B: pB = Y pa. This formulation assumes the mutual indepena2B dence of attributes. Based on this, and denoting n = jOj we obtain the following formula for the probability of B being closed: p(B = B00) = k=0 n X p(jB0j = k; B = B00) k=0 = Xn " n pkB(1 k 5 Here and in the following 0 represents the operator on the power sets of objects: 0 : 2O ! 2A; X0 = fa 2 A j 8o 2 X: (o; a) 2 Rg and dually on that of attributes. A small p(B = B00) suggests a small probability of the attribute combination B to be a concept intent by chance only (and p(B = B00) 1 that there is a high probability that the combination is a concept intent by chance). However, this reasoning is based on the independence of the attributes, which in our particular case can not be warranted. 4.1
Computing Stability, Separation and Probability Indices.
Stability. Calculating stability is known to be NP-complete (Kuznetsov, 2007),
however
Probability.
n As X k=0 n k pk(1
p)n k = 1, Term (6) can be rewritten as: F (k; n; p) = Xk n i pi(1
p)n 1 is the cumulative distribution function of the i=0 binomial distribution6 and can be computed using various statistical software packages. Term (5) can also be computed more easily considering that nk pkB(1 pB)n k are binomial densities the computation of which is also provided by statistics software7 6 Source Wikipedia: http://en.wikipedia.org/wiki/Binomial_distribution 7 We used the R software environment for statistical computing (http://www. r-project.org/).
a2B p(B = B00) = X40 " n
k k=0
n + X
k=41 1
In the following we measure the performance of the three concept selection indices with respect to our data. The experimental setting is as follows:
We rst select a number of N (1500) concepts with best selection index. The selected concepts are aligned with the classes translated from VerbNet (see Section 5): For each translated class, we select the concept with best precision/recall f-measure. Then we associate to the concept with best f-measure the thematic roles of the translated VN class. Next we compare the obtained hverb, thematic role seti associations with those given by a reference. As for our task recall is more important than precision, we use the F 2 measure, which gives more weight to recall, for comparison.
As reference we use the data used for training the classi er for learning
the translated VN classes (see Section 5): we are checking which index selects
the most relevant concepts, that is those best matching the translated classes.
The reference consists of the hverb, semantic role seti pairs marked as positive
examples in the training set, ie. those for which we considered that the French
verbs could have the semantic roles given by the English VN class. Table 2 shows
the F2 scores and coverage when using only one index at a time. For stability
and separation we applied the method above on the top ranking 1500 concepts.
Regarding probability, at rst sight, we should consider best the concepts with
lowest probability { because the probability of their intents of being closed by
chance only is accordingly low. However, looking at the data we found that these
concepts have very few verbs and large intent (frame) sets - which rather suggest
improbable or rare verb groups. On the other hand, the interpretation of concept
probability suggests that a concept with a probability close to 1 could occur by
chance only. For these reasons, to assess probability separately we settled on the
6th 10 quantile. The results con rm the observations of
As we only select 10% of the total number of concepts we also have to make sure that the selected concepts cover at least a reasonable amount of verbs. The cov column gives the percentage of verbs in the lattice covered by the selected concepts. It shows that using only one index at a time the pre-selected concepts would contain only 35% 40% of the verbs in the entire lattice, which is unsatisfactory.
In the following we start from the assumption that the most e ective index for selecting relevant concepts is given by a linear combination of stability, separation and probability: kstab stability + ksep separation kprob probability, and empirically determine the coe cients kstab; ksep and kprob such that the selected concepts perform best with respect to our task.
We proceed as follows: We choose kstab; ksep and kprob. We then compute the corresponding linear combination for the concepts and select the 1500 concepts ranking highest. As in the previous experiments, we measure the relevance of the selected concepts by aligning the concepts with the translated VN classes and by comparing the alignments with the same reference as before. We consider the \best" kstab; ksep; kprob combination the one giving highest F2 scores and good coverage.
Table 3a shows the results for a rst series of experiments where kstab and ksep were assigned the values 0.5 and 1 and kprob 0.25 and 0.5 (The lines are sorted by decreasing F2 score). They suggest that the stability and separation coe cients had less impact on coverage and F2 score than the probability coefcient. Interestingly the coverage is correlated with the F2 score.
In the second series of experiments, shown in Table 3b, we kept the stability and separation coe cients xed and varied only the probability coe cient. These results suggest that the probability coe cient may not help at selecting the most relevant concepts in our setting. This may be due rst to the fact that our attributes are not independent (we assumed independence of attributes when setting up the formula for computing the probability index) and second to the fact that we had to approximate the probability index and this approximation may not be accurate enough.
In the next series of experiments we investigated the impact of the number of preselected concepts (500). The results showed that with this smaller number of concepts the selected concepts reached a slightly smaller F2 score but a substantially lower coverage. Also, in this con guration the probability index did seem to be helpful. Preselecting 1000 concepts con rmed the previously observed tendencies: The F2 score and coverage were only slightly lower than when preselecting 1500 concepts and again the probability index seemed to have only a small impact on the overall results. (a) F2 and coverage when kstab; ksep 2(b) F2 and coverage when kstab and ksep f0:5; 1g; kprob 2 f0:25; 0:5g. are kept xed and kprob varies.
From these experiments we conclude the following: First they suggest that the best linear combination is the sum of the stability and separation indices as the F2 measure and the coverage for this combination are similar to those of an upper bound, ie. the alignment obtained without ltering. They show that selecting only 10% of the original lattice gives a verb, frame, semantic role set alignment which is close to the alignment obtained when using the entire lattice and that the pre-selected concepts also have a similar coverage.
Second, it does not seem evident that probability has a positive e ect on the selected concepts. However, it does improve f-measure when the number of selected concepts is lower (500 or 1000 vs. 1500 in our experiments). Hence, for our application we concluded that it is a better strategy to select a larger number of concepts (1500) and not take probability into account. This is even more so as the probability index in our case should be taken with caution because rst we had to use an approximation to compute it which may be too rough, and second the computation of probability is based on the independence of attributes which is not warranted in our case. 5
We associate French verbs with thematic role sets by translating the English VerbNet classes to French using 3 English-French dictionaries. In the following we rst brie y describe the relevant resources, ie. VerbNet and the dictionaries before giving the translation methodology. As for this paper only the translated classes, but not the method to produce them is relevant8 we only very brie y sketch the methodology. 8 Of course better translated classes will result in a better performance of our method, but it is not straight forward to evaluate the quality of the translated classes.
VerbNet (Schuler (2006)) is the largest electronic verb classi cation for English. It was created manually and classi es 3626 verbs using 411 classes. Each VN class includes among other things a set of verbs, a set of subcategorisation frames and a set of thematic roles. Figure 2 shows an excerpt of the amuse-31.1 class, with its verbs, thematic roles and subcategorisation frames. verbs (242): abash, a ect, a ict, amuse, annoy, . . . thematic roles: Experiencer, Cause
NP V NP Experiencer V Cause frames (6): NNPP VV ANPD-VP-RMOid-AdlReB ECxapueseriVencer V Adv . . .
English-French dictionaries. We use the following resources to translate the verbs in the English VN classes to French: Sci-Fran-Euradic, a French-English bilingual dictionary, built and improved by linguists , Google dictionary9 and Dicovalence van den Eynde and Mertens (2003)10. The merged dictionary contains 51242 French-English verb pairs.
In the following we describe our method for translating the English VerbNet classes to French.
The translation of VerbNet classes is bound to be very noisy because verbs are polysemous and the dictionaries typically give translations for several readings of the verb: Thus the dictionary may give several translations vfr which do not correspond to the meaning given by the hven; classi pair or this meaning may even not be covered at all by the dictionary. To get more accurate translated VN classes we use a machine learning method, namely Support Vector Machines (SVM)11. We follow a straight forward SVM application scenario: we build all the French verb, VN class pairs hvfr; CV N i where vfr is a translation of an English verb in CV N . The classi er has to give a probability estimate about whether this association is correct or not.
For training the classi er we use the 160 verbs appearing in the gold standard proposed by Sun et al. (2010)12. We build the pairs hvfr; CV N i where vfr is a verb in the gold standard which is a translation of a verb in CV N . For each of these pairs we assessed whether or not there was a meaning of vfr where the semantic roles involved in the event described by the verb were those given by CV N . The features associated to the hverb, classi pairs are numeric and are extracted from the dictionaries and VerbNet. 9 http://www.google.com/dictionary. We obtained 13824 French-English verb pairs. 10 The number of French-English verb pairs we obtained is 11351 11 We used libsvm, the software package and methodology presented on http://www.
csie.ntu.edu.tw/~cjlin/libsvm/,
The trained classi er is then used to produce probability estimates for all verb, class instances. We select the 6000 pairs with highest probability estimates13 and nally obtain the translated classes by assigning each verb in a selected pair to the corresponding class.
To give an idea of the quality of the obtained classes: The accuracy of the classi er on the held out test set was 90%, compared to a maximum accuracy of 93.84% for ve fold cross-validation on the development set. The frequency distribution of the translated classes obtained this way is much closer to the distribution of verbs in VerbNet classes as when using an approach based only on translation frequencies, thus providing more accurate verb groups to guide the FCA concept - thematic roles associations. 6
The French Verb $ Thematic Role Sets $ Syntactic
As a detailed and thorough evaluation of the verb, thematic role sets and syntactic frames associations would be out of the scope of this paper we only give here an intuition of the type of information provided by our method. Following the preliminary investigations in the previous sections we associated French verbs with subcategorisation frames and thematic role sets according to the scheme listed below: { We group the VerbNet thematic roles and assign to one class all the VN verbs whose class have the same role set. We then translate the obtained classes using the methods described in Section 5. { We use FCA to group French verbs and syntactic frames associated to these verbs by the lexicons described in Section 3. The concept lattices we create are based on the formal contexts consisting of French verbs as objects and SCFs as attributes. { We then select the 1500 concepts where the sum of the stability and separation indices is highest because in Section 4 we found this combination of concept selection indices to work best for our application. { For each translated VN class we identify among the 1500 ltered FCA concepts the one(s) with best f-measure between precision and recall. The translated VerbNet class is then associated with this FCA concept(s). Thus the verbs in the FCA concept are e ectively associated with the thematic role set of the translated class and at the same time with the syntactic frames in the intent (attribute set) of the FCA concept. Figure 3 shows the associations between concepts, thematic role sets and frames generated by our method for some VN classes14. The gure shows the concepts associated to these thematic role sets and for each of these concepts: their attribute set (syntactic frames), 13 In VerbNet there are 5726 verb, class pairs 14 These are the classes occuring in the gold standard proposed by Sun et al. (2010), mentioned in Section 5.
AgvEeAxrpgSb-EUIsxJnep:sNt-1t:ErP2u1n,4Om7d80B-eT6Jn:htNv-ePePmraebtisent AgvEerxbp-sLeSotU:c3Ja92:tN7ioP7n-vTehrbemse SSUUJAvJ:eN:gNrEPbP,xO,spOeB-B5tSJ:0J:tN:a32NrP02tP,0-D,TPvEhOeOeBrmBbJesJ:P:PPP
7191 SUJ:NP,OBJ:Ssub AgExp-PredAtt-Theme verb set: 343 verbs 4584 vAegSrbEUxJsp:eN-1tP:P2a,12Ot2i7Be2nJ:vtNSePyrbms veSSrUAbUJg:JsSE:e1Nstx8u:Ppb8,3-O,6CO5B84aBJu:JvsN:eeNPrPbs AgExp-SBSUUeJnJ:SN:eSNUSfPUiUPJ,cJ:O,JiN:O:NaSBNPrBUPJy,PJ:D,J-NA,::OENENPOxBOP,PBtD,JBeP:JEnNJO:P:OtPPB-PBSPJtJ:aP:PrPtP-Theme verb set: 17 verbs
7190 SUJ:NP,OBJ:NP SUJ:NP,OBJ:Ssub AgExp-Theme verb set: 326 verbs the associated thematic role set(s), the number of verbs in the concept and the hierarchical relations between the concepts as given by the concept lattice.
Thus for example the following 11 verbs (occuring in the gold standard) bouger, deplacer, emporter, passer, promener, envoyer, expedier, jeter, porter, transmettre, transporter are in concept 5312 and thereby may be used in the construction SUJ:NP,OBJ:NP,POBJ:PP,POBJ:PP15 (according to our lexical resources). When they occur in this construction they are associated with the thematic role set AgExp, End, Start, Theme, i.e. the semantic roles involved are an Agent or Experiencer, a Start point, an End point and a Theme. The listed verbs are all verbs of movement where an agent may move a theme from a start point to an end point { therefore in this case the associations with the syntactic frame and thematic role set seem to be correct. An NLP system which encounters the verb deplacer for example, used in the construction SUJ:NP,OBJ:NP,POBJ:PP,POBJ:PP could infer that possible thematic roles involved in the described event are an Agent (or Experiencer), a Theme, an End point and a Start point. However, it still would not know which thematic role is realised by which syntactic argument.
There are also some problems with these associations. As can be seen in Figure 3, there is one case where the classi cation maps the same concept to two distinct VerbNet classes (AgExp-End-Theme and AgExp-Instrument-Patient ). In addition, verbs in sub-concepts inherit the class label of the super-concept. Although there are verbs which belong to several VN classes, in many cases this multiple mapping was not warranted. Improving the precision of these mappings requires further investigations. 7
We introduced a new approach to verb clustering which involves the combined
use of the English VerbNet, a bilingual English-French lexicon and a merged
subcategorisation lexicon for French. Using these resources, we built two
classications, one derived from the English VN by translation and the other, from
the subcategorisation lexicons via the construction of a formal concept lattice.
We then use the translated VN to associate FCA concepts with VN classes
15 a transitive construction with two additional prepositional objects
and thereby associate verbs with both syntactic frames and a thematic role
set. We explored the performance of the concept selection indices introduced
by
Palmer, M., Gildea, D., and Xue, N. (2010). Semantic Role Labeling. Synthesis lectures on human language technologies. Morgan & Claypool Publishers. Palmer, M., Kingsbury, P., and Gildea, D. (2005). The proposition bank: An annotated corpus of semantic roles. Computational Linguistics, 31(1):71{106. Priss, U. (2005). Linguistic Applications of Formal Concept Analysis. In Ganter, B., Stumme, G., and Wille, R., editors, Formal Concept Analysis, volume 3626 of Lecture Notes in Computer Science, pages 149{160{160. Springer Berlin / Heidelberg.
Roth, C., Obiedkov, S. A., and Kourie, D. G. (2006). Towards concise representation for taxonomies of epistemic communities. In CLA, pages 240{255. Saint-Dizier, P. (1999). Alternation and verb semantic classes for french: Analysis and class formation. In Predicative forms in natural language and in lexical knowledge bases. Kluwer Academic Publishers.
Schuler, K. K. (2006). VerbNet: A Broad-Coverage, Comprehensive Verb Lexicon. PhD thesis, University of Pennsylvania.
Sporleder, C. (2002). A Galois Lattice based Approach to Lexical Inheritance Hierarchy Learning. In 15th European Conference on Arti cial Intelligence (ECAI'02): Workshop on Machine Learning and Natural Language Processing for Ontology Engineering, Lyon, France.
Sun, L., Korhonen, A., Poibeau, T., and Messiant, C. (2010). Investigating the cross-linguistic potential of VerbNet-style classi cation. In Proceedings of the 23rd International Conference on Computational Linguistics, COLING '10, pages 1056{1064, Stroudsburg, PA, USA. Association for Computational Linguistics.
Tolone, E. (2011). Analyse syntaxique a l'aide des tables du Lexique-Grammaire du francais. PhD thesis, LIGM, Universite Paris-Est, France, Laboratoire d'Informatique Gaspard-Monge, Universite Paris-Est Marne-la-Vallee, France. (326 pp.). van den Eynde, K. and Mertens, P. (2003). La valence : l'approche pronominale et son application au lexique verbal. Journal of French Language Studies, 13:63{104.