Nathalie Camelin

Boris Detienne

Stéphane Huet

Dominique Quadri

Fabrice Lefèvre

Concept Discovery for Language Understanding in an Information-Query Dialogue System

Keywords: concept discovery, language understanding, latent Dirichlet analysis, dialogue systems

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Generally, information-query spoken dialogue systems are used to interface a database with users orally. Once a speech recogniser has transcribed the signal, the meaning of the user's queries is extracted by a Spoken Language Understanding (SLU) module. The very first step of this module is the identification of literal concepts. These concepts are applicationdependent and fine-grained so as to provide efficient and usable information to the following reasoning modules (e.g. the dialogue manager). To this respect they can also be composed in a global tree-based structure to form the overall meaning of the sentence.

To address the issue of concept tagging several techniques are available. Some of these techniques now classical rely on probabilistic models, which can be either discriminant or generative. To obtain good performance when probabilistic models are used in such systems, field data are to be collected, transcribed and annotated at the semantic level. It is then possible to train efficient models in a supervised manner. However, the annotation process is costly and constitutes a real hindrance to a widespread use of the systems. Therefore any means to avoid it would be highly appreciable.

It seems out of reach to derive the concept definitions from a fully automatic procedure. Anyhow the process can be bootstrapped, for instance by induction of semantic classes such as in [START_REF] Siu | Semi-automatic acquisition of domain-specific semantic structures[END_REF] or [START_REF] Iosif | Unsupervised combination of metrics for semantic class induction[END_REF]. Our assumption here is that the most time-consuming parts of concept inventory and data tagging could be obtained in an unsupervised way, even though a final (but hopefully minimal) manual procedure is still required to tag the derived classes so as to manually correct the automatic annotation.

Unlike the previous attempts cited before, which developed ad-hoc approaches, in the work described here we investigate the use of broad-spectrum knowledge discovery techniques. In this context the notion most related to that of concept in SLU seems to be the topic, as used in information retrieval systems. For a long time, the topic detection task was limited to the association of a single topic to a document and thus did not fit our requirements. The recently proposed latent Dirichlet allocation (LDA) technique has the capacity to derive a probabilistic representation of a document as a mixture of topics. As such LDA can consider that several topics can co-occur inside a single document or sentence and that the same topic can be repeated.

From these favorable characteristics we consider the application of LDA to concept discovery for SLU. Anyhow, LDA does not take into account the sequentiality of the data (due to the exchangeability assumption). It is then necessary to introduce constraints for a better segmentation of the data: assignment of topics proposed by LDA is modified to be more coherent in a segmental way.

The paper is organised as follows. Principles of automatic induction of semantic classes are presented in Section 2, followed by the presentation of an induction system based on LDA and the additional step of segmentation using integer linear programming (ILP). Then evaluations and results are reported in Section 3 on the French MEDIA dialogue task.

AUTOMATIC INDUCTION OF SEMANTIC CLASSES AND ANNOTATION

Context modelization

The main idea of automatic induction of semantic classes is based on the assumption that concepts often share the same context (syntactic or lexical) [START_REF] Siu | Semi-automatic acquisition of domain-specific semantic structures[END_REF], [START_REF] Pargellis | Metrics for measuring domain independence of semantic classes[END_REF]. While there may be still room for improvement in these techniques we decided instead to investigate general knowledge discovery approaches in order to evaluate their potentiality.

In that purpose a global two-steps strategy is proposed: first semantic classes (topics) are induced; then topics are assigned to words with segmental constraints. The major interest of the approach is to separate the tasks of detecting topics and aligning topics with words. It is then possible to introduce additional constraints (such as locality, number and types of segments, etc) in the second task which would otherwise hinder topic detection in the first place.

Several approaches are available for topic detection in the context of knowledge discovery and information retrieval. In this work we were motivated by the recent development of a very attractive technique which has interesting distinct features such as the detection of multiple topics in a single document. LDA [START_REF] Blei | Latent Dirichlet allocation[END_REF] is the first principled description of a Dirichlet-based model of mixtures of latent topic variables. It generates a set of topics with probabilities for each topic to be associated with a word in a sentence. In our case this knowledge is thereafter used to infer a segmentation of the sentence using integer linear optimisation.

Implementation of an automatic

induction system based on LDA A topic mixture vector θ is drawn from the Dirichlet distribution (with parameter α). The corresponding topic sequence κ = [k 1 , k 2 , . . . , k N ] is generated for the whole document accordingly to a multinomial distribution (with parameter θ). Finally each word is generated by the word-topic multinomial distribution (with parameter β, that is p(w i |k i , β)). After this procedure, the joint probability of θ, κ and d is then:

p(θ, κ, d|α, β) = p(θ|α) N ∏ i=1 p(k i |θ)p(w i |k i , β) (1)
To obtain the marginal probability of d, a final integration over θ and a summation over all possible topics considering a word is necessary:

p(d|α, β) = p(θ|α) N ∏ i=1 ∑ k i p(k i |θ)p(w i |k i , β) (2)
The framework is comparable to that of probabilistic latent semantic analysis, but the topic multinomial distribution in LDA is assumed to be sampled from a Dirichlet prior and is not linked to training documents.

In recent years, several studies have been carried out in language processing using LDA. For instance, [START_REF] Tam | Unsupervised language model adaptation using latent semantic marginals[END_REF] worked on unsupervised language model adaptation, [START_REF] Celikyilmaz | LDA based similarity modeling for question answering[END_REF] ranked candidate passages in a question-answering system and [START_REF] Phan | Learning to classify short and sparse text & web with hidden topics from large-scale data collections[END_REF] implemented LDA to classify short and sparse web texts.

We chose to use an implementation of LDA, GIBBSLDA++ tool,1 to annotate each user's utterance of a dialogue corpus with topics. Each utterance of more than one word is included in the training set as its sequence of words. Once the models are trained, inference on data corpus assigns each word in a document with the highest probability topic. [LDA] system executes 2,000 iterations with the default parameters for α and β.

Notice that single-word utterances are processed separately using prior knowledge. Names of cities, month, day or short answers (e.g. "yes", "no", "yeah") and numbers are parsed in these utterances. Indeed, LDA cannot be applied on such utterances where no co-occurrences can be observed.

Alignment with integer linear programming (ILP)

The topic alignment problem we have to solve in this paper can be considered as a combinatorial optimization problem. ILP is a basic method to deal with such problems.

ILP is a mathematical method for determining the best way to optimize a given objective. More specifically, an integer linear model aims at optimizing a linear objective function (for instance representing a cost, a benefit, a probability...) subject to linear equalities or inequalities (named the constraints). Both the objective function and the constraints are expressed using integer unknown variables (called decision variables). The coefficients of the objective function and the constraints are the input data of the model. Consequently, solving an ILP consists in assigning integer values to decision variables, such that all constraints are satisfied and the objective function is optimized (maximized or minimized). We report the interested reader to [START_REF] Chen | Applied Integer Programming: Modeling and Solution[END_REF] for an introduction on approaches and applications of ILP.

We propose an ILP formulation for solving the topic alignment problem for one document. The input data are: an ordered set d of words (indexed from 1 to N), a set of K available topics and, for each word w i ∈ d and topic k = 1...K, the natural logarithm of the probability p(w i |k) that k is assigned to w i in the considered document. Model [ILP] determines the highest-probability assignment of one topic to each word in the document, such that at most χ max different topics are assigned.

[ILP] : max

∑ N i=1 ∑ K k=1 p(w i |k)x ik (3) ∑ K k=1 x ik = 1 i = 1...N (4) y k -x ik ≥ 0 i = 1...N, k = 1...K (5) ∑ k∈κ y k ≤ χ max k = 1...K (6) x ik ∈ {0, 1} i = 1...N, k = 1...K y k ∈ {0, 1} k = 1...K
Decision variable x ik is equal to 1 if topic k is assigned to word w i , and equal to 0 otherwise. Constraints (4) ensure that exactly one topic is assigned to each word. Decision variable y k , is equal to 1 if topic k is used. Constraints (5) force variable y k to take a value of 1 if at least one variable x ik is not null. Moreover, constraints (6) limit the total number of topics used. The objective function (3) merely states that we want to maximize the total probability of the assignment. Through this model, our assignment problem is identified as a p-centre problem (see e.g. [START_REF] Revelle | Location analysis: A synthesis and survey[END_REF] for a survey on such location problems).

Since the number of instances considered in this work is small, [ILP] can be straightforwardly solved to optimality using a ILP solver as ILOG-CPLEX. Numerical results are reported in Section 3. The considered system is denoted [LDA + ILP] since p(w i |k) are given by [LDA]. χ max has been chosen according to the desired concept annotation. As on average a concept support contains 2.1 words, χ max is defined empirically according to the number of words: with i = [[2, 4]] :χ max = i with i = [[5, 10]] words: χ max = i -2 and for utterances containing more than 10 words:

χ max = i/2.

EVALUATION AND RESULTS

MEDIA corpus

The MEDIA corpus is used to evaluate the proposed approach. MEDIA is a French corpus related to the domain of tourism information and hotel reservation [START_REF] Bonneau-Maynard | Semantic annotation of the French MEDIA dialog corpus[END_REF]. 1257 dialogues were recorded from 250 speakers with a WoZ technique (a human simulating an automatic phone server). In our experiments we only consider the 17k user utterances. This dataset contains 123,538 words, for a total of 2470 distinct words.

The MEDIA data have been manually transcribed and semantically annotated. The semantic annotation is rich of 75 concepts (e.g.: location, hotel-state, timemonth. . . ). Each concept is supported by a sequence of words, the concept support. The null concept is used to annotate every word segment that does not support any of the 74 other concepts. Concepts do not appear at the same frequency as shown in Table 1. For example, 33 concepts (44% of the concepts) are supported by 100 occurences at most, while 15 concepts (21% of the concepts) present more than 1,000 occurences (only null is above 9,000).

[ On average, a concept support contains 2.1 words, 3.4 concepts are included in a turn and 32% of the utterances are single-word turns (generally yes or no).

Automatic evaluation protocol

As MEDIA reference concepts are very fine-grained, we introduce a high-level concept hierarchy containing 18 clusters of concepts. For example, a high-level concept payment is created, corresponding to the four concepts payment-meansOfPayment, payment-currency, payment-total-amount, paymentapprox-amount, a high-level concept location corresponds to 12 concepts (location-country, locationdistrict, location-street, . . . ). Thus, two levels of concepts are considered for the evaluation: the high-level (18 classes) and the fine-level (75 classes).

To evaluate the unsupervised procedure in a fully automatic way, it is necessary to associate each induced topic with a MEDIA concept. To that purpose, topics are aligned with concepts based on their word support for each utterance according to the reference annotation. A co-occurrence matrix is computed and each topic is associated to its most co-occurring concept. Table 2 analyses this automatic association for two values of K, the number of topics induced by LDA. Some concepts may not be associated with any topic, the CC column (Concept Coverage) gives the percentage of concepts that are associated with a topic. The NNT column (Not Null Topic) computes the percentage of topics not associated with the null concept. Considering [LDA] and fine-level concepts, only one fifth of the MEDIA concepts are retrieved for K = 50 and up to one third for K = 200. Though 72% of the high-level concepts are retrieved with K = 200. Considering [ILP + LDA], this value even increases to 82%. This "lost concept" phenomenom at highlevel can be explained by the fact that 72% of the concepts are supported by less than 500 concept supports, which seems a bit low for [LDA] to modelize them as a topic. [LDA + ILP] helps to cover more concepts. Obviously, when more topics are induced, more concepts are covered. It is also interesting to notice that about half of the topics are associated with the null concept. When the number of topics is increased, more concepts are discovered but also more topics are associated with null.

Generated topic observations

In Table 3, six topics generated by [LDA] are represented by their 8 highest probability words. For topic 13, it is interesting noting that words have quite similar weights. The most represented words are "du" ("from") and "au" ("to") and other words are numbers or month that a priori leads to a "time-date" topic. For topic 43, the word "oui" ("yes") is given a 0.62 probability, other words are "absolutely" or "okay" leading to an a priori "answer-yes" topic.

To observe which MEDIA concept is associated to these topics, the list of the 3 most co-occurring concepts and the number of co-occurrences are shown in Table 4. The 2 first most co-occurring concepts in a topic are the same in [LDA] and [LDA + ILP]. However, the number of co-occurrence is higher in [LDA + ILP] than in [LDA]. An entropy measure Ent(t) is computed for each topic t in order to evaluate the reliability of the topic-concept association over all the possible concepts. It is computed as follows:

Ent(t) = -∑ concepts c p(c|t) log p(c|t) (7) with p(c|t) = #(c t) #t The topic entropy is always smaller considering [LDA + ILP] than [LDA]
. This indicates that the reassignment due to ILP alignment improves the reliability of the topic-concept association. Entropies measured with high-level concepts are always lower than with fine-level concepts, in particular because less classes are considered (18 instead of 75). For topic 18, we can see that high-level enables to consider this topic as a Location concept and not a null one but the entropy is quite high. On the over hand, topic 43 shows a low entropy, specifically in [LDA + ILP]. This shows that word "yes" is strongly associated with concept "Answer". Other topics representing the null concept can show an entropy of 0.47 like the 6th topic ("there", "is", "what", "how", "does", . . . )

Results

The evaluation is presented in terms of F-measure, combining precision and recall measures. Quality of topic assignment is considered also according to 2 levels:

• alignment corresponds to a full evaluation where each word is considered and associated with one topic,

• generation corresponds to the set of topics generated for a turn (no order, no word-alignment). Plots comparing the different systems implemented w.r.t. the different evaluation in terms of F-measure are reported in Figures 1 and2.

The [LDA] system generates topics which are correctly correlated with the high-level concepts. It can be observed that the bag of 75 topics reaches an Fmeasure of 61.6% (Figure 1), corresponding to a pre- cision of 59.4% and a recall of 64%. When [LDA] is asked to generate too few topics, induced topics are not specific enough to fit the fine-grained concept annotation of MEDIA.

On the other hand, Figure 2 shows that a too high increase of the number of topics does not affect the bag of high-level topics significantly but induces a substantial decrease of the F-measure for the alignment evaluation. This effect can be explained by the automatic alignment method chosen to transpose topics into reference concepts. When there are too many topics, they co-occur with many concepts and are assigned to the most co-occurring one when some other concepts can co-occur only slightly less. In such situations, it is likely that null is the most co-occurring concept and the other concepts because they are too much scattered are not associated to enough topics. So they appear in the utterance but not on enough words to be retained by the segmentation process.

From the high-level to fine-level concept evaluation, results globally decrease of 10%. A loss of 12% is observed from the generation to the alignment evaluation. In the fine-level evaluation, a maximum Fmeasure of 52.5% is observed for the generation of 75 topics (Figure 1), corresponding to 54.9% in precision and 50.3% in recall whereas the F-measure decreases to 41% (precision=46.7% and recall=36.7%) in the alignment evaluation (Figure 2).

To conclude on the [LDA] system, we can see that it generates topics having a good correlation with the high-level concepts, seemingly the best representation level between topics and concepts. It is obvious that an additional step is needed to obtain a more accurate segmental annotation, what is expected with the use of ILP.

[LDA + ILP] performs better whatever the level of evaluation. For instance, an F-measure of 66% is observed considering the high-level concept generation for 75 topics (Figure 2). As for [LDA], the same losses are observed between high-level and fine-level concepts and generation and alignment paradigms. Nevertheless, an F-measure of 54.8% is observed at the high-level concept in alignment evaluation (Figure 2) that corresponds to a precision of 56.2% and a recall of 53.5%, which is not so low considering a fullyautomatic high-level annotation system.

CONCLUSIONS

In this paper an approach has been presented for concept discovery and segmental semantic annotation of user's turns in an information-query dialogue system. An evaluation based on an automatic association between generated topics and expected concepts has been shown that topics by LDA are close to high-level task-dependent concepts. The segmental annotation process increases performance both for the generation and alignment evaluations. On the whole these results confirm the applicability of the technique to practical tasks with expected gain in data produc-tion.

Future work will investigate the use of n-grams to extend LDA and to increase its accuracy for providing better hypotheses to the following segmentation techniques. Also another technique for automatic realignment, based on IBM models used in stochastic machine translation, will be examined.

Figure 1 :

 1 Figure 1: F-measure of the concept generation as a function of the number of topics.

Figure 2 :

 2 Figure 2: F-measure of the concept alignment as a function of the number of topics.

Table 2 :

 2 Analysis of the automatic association between topics and concepts. CC: concept coverage by the topics. NNT: % of topics not associated with null.

			K=50 topics K=200 topics
			CC	NNT CC	NNT
	high LDA	61	60	72	51
		LDA+ILP	67	62	82	57
	fine	LDA	21	50	34	47
		LDA+ILP	24	58	39	53

Table 3 :

 3 Examples of topics discovered by LDA (K = 100).

	Topic 0	Topic 13	Topic 18	Topic 35	Topic 33	Topic 43
	information	time-date	sightseeing	politeness	location	answer-yes
	words	prob.	words	prob. words prob. words	prob.	words	prob. words	prob.
	d'	0.28	du	0.16	de	0.30	au	0.31	de	0.30	oui	0.62
	plus	0.17	au	0.11	la	0.24	revoir	0.27	Paris	0.12	et	0.02
	informations 0.16	quinze	0.08	tour	0.02	madame 0.09	la	0.06	absolument	0.008
	autres	0.10	dix-huit	0.07	vue	0.02	merci	0.08	près	0.06	autre	0.008
	détails	0.03	décembre 0.06	Eiffel	0.02	bonne	0.01	proche 0.05	donc	0.007
	obtenir	0.03	mars	0.06	sur	0.02	journée	0.01	Lyon	0.03	jour	0.005
	alors	0.01	dix-sept	0.04	mer	0.01	villes	0.004 aux	0.02	Notre-Dame 0.004
	souhaite	0.003 nuits	0.04	sauna 0.01	bientôt	0.003 gare	0.02	d'accord	0.004
			Topic 18			Topic 33			Topic 43
			sightseeing			location			answer-yes
		#occ. concept		Ent(t) #occ. concept		Ent(t) #occ. concept	Ent(t)
		high 292	Location			571	Location			705	Answer
	LDA	258	null		2.25 156	null		1.72 107	null	1.10
		94	Name			87	Comparative		27	Location
		fine 258	null			226	loc.-distanceRel.		705	answer
		136	loc.-placeRel.	2.78 190	location-city		2.57 107	null	1.19
		100	loc.-distanceRel.		156	null			17	object
		high 300	Location			661	Location			846	Answer
	LDA	200	null		2.19 123	null		1.52 109	null	0.76
	+	102	Name			115	Comparative		24	Location
	ILP	fine 200	null			234	loc.-distanceRel.		846	answer
		163	loc.-placeRel.	2.64 223	location-city		2.44 109	null	0.80
		98	name-hotel			129	loc.-placeRel.		16	name-hotel

Table 4 :

 4 Topic repartitions among the high or fine-level concepts for [LDA] and [LDA + ILP] (K = 100).

		68
		66
		64
		62
	Fmeasure	54 56 58 60
		52 50		[LDA+ILP] high [LDA] high
		46 48		[LDA+ILP] fine [LDA] fine
		50	100	150	200
			Number of topics

http://gibbslda.sourceforge.net/


Nathalie Camelin

Boris Detienne

Stéphane Huet

Dominique Quadri

Fabrice Lefèvre

Concept Discovery and Automatic Semantic Annotation for Language Understanding in an Information-Query Dialogue System Using Latent Dirichlet Allocation and Segmental Methods

Keywords: concept discovery, segmental semantic annotation, language understanding, latent Dirichlet analysis, dialogue systems

whether they are published or not. The documents may come

Introduction

Spoken dialogue systems in the field of information query are basically used to interface a database with users using speech. When probabilistic models are used in such systems, good performance is at the price of collecting a large set of field data, which must be transcribed and annotated at the semantic level. These data allow then efficient models to be trained in a supervised way. However, the annotation process is costly and as a consequence represents a real difficulty hindering the widespread development of these systems. Therefore devising automatic methods for the annotation would be highly beneficial for portability to new tasks, domains or languages.

To give a full description of the architecture of a dialogue system is out of the scope of this paper. Instead we limit ourselves to briefly recall the main information pipeline: once a speech recognizer has transcribed the signal it is common (though avoidable for very simple tasks) to use a module dedicated to extract the meaning of the user's queries. This meaning representation is then conveyed to an interaction manager that decides upon the next best action to perform considering the current user's input and the dialogue history (defining the dialogue state all together). One of the very first steps to build the spoken language understanding (SLU) module is the identification of literal concepts in the word sequence hypothesised by the speech recogniser. An example of a semantic representation in terms of literal concepts is given in Figure 1. Once the concepts have been identified they can be further composed to form the overall meaning of the sentence, for instance by means of a tree representation based on hierarchical semantic frames [START_REF] Meurs | Spoken language interpretation: On the use of dynamic bayesian networks for semantic composition[END_REF].

To address the issue of concept tagging several techniques are available. Some of these techniques now classical rely on probabilistic models, that can be either discriminative or generative. Among these, the following models have been studied in the last decade: hidden Markov models, finite state transducers, maximum entropy Markov models, support vector machines, dynamic Bayesian networks and conditional random fields (CRF). In [START_REF] Hahn | Comparing stochastic approaches to spoken language understanding in multiple languages[END_REF] it is shown that CRFs obtain the best performance on a tourist information retrieval task in French (Media [START_REF] Bonneau-Maynard | Semantic annotation of the french media dialog corpus[END_REF]), but also in two other comparable corpora in Italian and Polish.

To be able to apply any such technique, basic concept units have to be defined by an expert. In the best case, most of these concepts can be derived straightforwardly from the pieces of information lurking in the database tables (mainly table fields but not exclusively). Some others are general (dialogue units but also generic entities such as number, dates etc.). However, to provide efficient and usable information to the reasoning modules (the dialogue manager in our case) concepts have to be fine-grained enough and application-dependent (even general concepts might have to be tailored to peculiar uses). To that extent it seems out of reach to derive the concept definitions using a fully automatic procedure. Anyhow the process can be bootstrapped, for instance by induction of semantic classes such as in [START_REF] Siu | Semi-automatic acquisition of domain-specific semantic structures[END_REF] or [START_REF] Iosif | Unsupervised combination of metrics for semantic class induction[END_REF]. Our assumption here is that the most time-consuming parts of concept inventory and data tagging could be obtained in an unsupervised way, even though a final (but hopefully minimal) manual procedure is still required to tag the classes so as to manually correct automatic annotation.

Unlike the previous attempts cited above which developed ad hoc approaches, we investigate here the use of broad-spectrum knowledge extraction methods. Topic as used in information retrieval systems is a notion related to that of concept in SLU. For a long time, the topic detection task was limited to associate a single topic with a document and thus was not fitted to the SLU task requirements. The recently proposed LDA technique allows a document to have a probabilistic representation as a mixture of topics. Then multiple topics can co-occur inside a document and the same topic can be repeated. From these characteristics it is possible to consider the application of LDA to unsupervised concept inventory and concept tagging for SLU. A shortcoming is that LDA does not take into account at all the sequentiality of the data. To address this issue we propose to conclude the procedure with a final step introducing specific constraints for a correct segmentation of the data: the assignments of topics proposed by LDA are modified to be more segmentally coherent. Heretwo variants are evaluated to derive an optimal concept segmentation using the probabilities output by the LDA inference step. First the recourse to a technique used in the Machine Translation field is considered: stochastic word alignment with IBM models. Then a more general framework for global optimisation under constraints is also investigated: integer linear programming.

The paper is organised as follows. Principles of automatic induction of semantic classes are presented in Section 2, followed by the presentation of an induction system based on LDA. The additional segmentation step is presented in Section 3 with two variants: stochastic word alignment with IBM models (GIZA) and integer linear programming (ILP). Then evaluations and results are reported in Section 4 on the French Media dialogue task.

Automatic Induction of Semantic Classes

Context Modelling

The idea of automatic induction of semantic classes is based on the assumption that concepts often share the same context (syntactic or lexical). Implemented systems are based on the observation of co-occurring words according to two different ways. The observation of consecutive words (bigrams or trigrams) allows for the generation of lexical compounds supposed to follow syntactic rules. The comparison of right and left contexts considering pairs of words allows for the clustering of words and compound words into semantic classes.

In [START_REF] Siu | Semi-automatic acquisition of domain-specific semantic structures[END_REF] and [START_REF] Pargellis | Metrics for measuring domain independence of semantic classes[END_REF], iterative systems are presented. Their implementations differ in the metrics chosen to evaluate the similarity during the generation of syntactic rules and semantic classes, but also in the number of words taken into account in a word context and the order of successive steps (which ones to generate first: syntactic rules or semantic classes?). An iterative procedure is executed to obtain a sufficient set of rules in order to automatically extract knowledge from the data.

While there may be still room for improvement in these techniques we decided to skip them and to focus instead on general knowledge extraction approaches in order to evaluate their potential. For that purpose a global strategy based on an unsupervised machine learning technique is adopted in our work to produce semantic classes.

Implementation of an Automatic Induction System Based on Latent Dirichlet Allocation

Several approaches are available for topic detection in the context of knowledge extraction and information retrieval. They all more or less rely on the projection of the documents of interest in a semantic space to extract meaningful information. However, as the considered spaces (initial document words and latent semantics) are discrete performance of the proposed approaches for the topic extraction tasks are pretty unstable, and also greatly depend on the quantity of data available. In this work we were motivated by the recent development of a very attractive technique with major distinct features such as the detection of multiple topics in a single document. LDA [START_REF] Blei | Latent dirichlet allocation[END_REF] is the first principled description of a Dirichlet-based model of mixtures of latent variables. LDA will be used in our work to annotate the dialogue data in terms of topics in an unsupervised manner.

Basically LDA is a generative probabilistic model for text documents. LDA follows the assumption that a set of observations can be explained by latent variables. More specifically documents are represented by a mixture of topics (latent variables) and topics are characterized by distributions over words. The LDA parameters are {α, β}. α represents the Dirichlet parameters of K latent topic mixtures as α = [α 1 , α 2 , . . . , α K ]. β is a matrix representing a multinomial distribution in the form of a conditional probability table β k,w = P (w|k), where k and w represent resp. a topic and a word. Based on this representation, LDA can estimate the probability of a new document d of N words d = [w 1 , w 2 , . . . , w N ] using the following procedure.

A topic mixture vector θ is drawn from the Dirichlet distribution (with parameter α). The corresponding topic sequence κ = [k 1 , k 2 , . . . , k N ] is generated for the whole document accordingly to a multinomial distribution (with parameter θ). Finally each word is generated by the word-topic multinomial distribution (with parameter β, that is p(w i |k i , β)). After this procedure, the joint probability of θ, κ and d is then:

p(θ, κ, d|α, β) = p(θ|α) N i=1 p(k i |θ)p(w i |k i , β) (1)
Fig. 2. Graphical representation for LDA variables (from [START_REF] Blei | Latent dirichlet allocation[END_REF]). The grey circle is the only observable variable.

To obtain the marginal probability of d, a final integration over θ and a summation over all possible topics considering a word is necessary:

p(d|α, β) = p(θ|α) N i=1 ki p(k i |θ)p(w i |k i , β) dθ ( 2
)
The framework is comparable to that of probabilistic latent semantic analysis, but the topic multinomial distribution in LDA is assumed to be sampled from a Dirichlet prior and is not linked to training documents. This approach is illustrated in Figure 2.

Training of the α and β parameters is possible using a corpus of M documents, with a fixed number K of topics to predict. A variational inference procedure is described in [START_REF] Blei | Latent dirichlet allocation[END_REF] which alleviates the intractability due to the coupling between θ and β in the summation over the latent topics. Once the parameters for the Dirichlet and multinomial distributions are available, topic scores can be derived for any given document or word sequence.

In recent years, several studies have been carried out in language processing based on LDA. For instance, [START_REF] Tam | Unsupervised language model adaptation using latent semantic marginals[END_REF] worked on unsupervised language model adaptation; [START_REF] Celikyilmaz | LDA based similarity modeling for question answering[END_REF] ranked candidate passages in a question-answering system; [START_REF] Phan | Learning to classify short and sparse text & web with hidden topics from large-scale data collections[END_REF] implemented LDA to classify short and sparse web texts.

In our work, LDA is employed to annotate each user's utterance of a dialogue corpus with topics. Utterances longer than one word are included in the training set as its sequence of words. Once the model has been trained, inference on data corpus assigns the topic with the highest probability to each word in a document. This probability is computed from the probability of the topic to appear in the document and the probability of the word to be generated by the topic. As a consequence we obtain a full topic annotation of the utterance.

Notice that LDA considers a user utterance as a bag of words. This implies that each topic is assigned to a word without any consideration for its immediate context. An additional segmental process is required if we want to introduce some context information in the topic assignment.

Segmental Annotation

Benefits of a Segmental Annotation

The segmental annotation of the data is not a strict requirement for language understanding. Up to quite recently, most approaches for literal interpretation were limited to lexical-concept relations; for instance this is the case of the Phoenix system [START_REF] Ward | Understanding spontaneous speech[END_REF] based on the detection of keywords. However, in an NLP perspective, the segmental approach allows the various levels of sentence analysis (lexical, syntactic and semantic) to be connected. Even though, in order to simplify its application, segments are generally designed specifically for the semantic annotation and do not have any constraint on their relation with the actual syntactic units (chunks, phrasal groups etc.). Ignoring such constraints not only simplifies the annotation process but also increases the robustness of the interpretation module, which will ultimately be used inside a spoken dialogue system and will have to deal with noisy data. In particular, highly spontaneous and ungrammatical utterances from the users, combined with errors from the speech recognizer are likely to severely decrease the performance of syntactic analysers.

Another interesting property of segmental approach is to offer a convenient way to dissociate the detection of a conceptual unit from the extraction of its associated value. The value corresponds to the normalisation of the surface form (see last column in Fig. 1); for instance if the segment "not more than" is associated to the concept comparative-payment, its value is "less than". The same value would be associated with the word sequences "not exceeding" or "inferior to". Value extraction requires therefore a link between concepts and words; the normalisation problem can be addressed by means of regular expressions or concept-dependent language models (even using integrated approaches such as described in [START_REF] Lefèvre | Dynamic bayesian networks and discriminative classifiers for multistage semantic interpretation[END_REF]). In the case of global approaches (i.e. not segmental), value extraction must be done directly at the level of the conceptual unit tagging, as in [START_REF] Mairesse | Spoken language understanding from unaligned data using discriminative classification models[END_REF]. This additional level is very complex (as some values may not be enumerable, such as numbers and dates) and is only affordable when the number of authorised values (for the enumerable cases) is low.

To refine the LDA output, the topic-to-word alignment proposed by LDA is discarded and an automatic procedure is used to derive the best alignment between topics and words. While the underlying probabilistic models are pretty comparable, the major interest of this approach is to separate the tasks of detecting topics and aligning topics with words. It is then possible to introduce additional constraints (such as locality, total number of segments, limits on repetitions etc.) in the latter task which would otherwise hinder topic detection. Conversely the alignment is self-coherent and able to question the associations proposed during topic detection with respect to its own constraints only. Two approaches were designed to this purpose: one based on IBM alignment models and another one based on integer linear optimisation.

Alignment with IBM Models (GIZA)

LDA is able to generate one topic k i by word w i from the probability p(k i |w i , d) that k i is associated with w i of the document d. However, this method has the drawback of considering a document as a bag-of-words and it ignores the effect of k i on the choice of the topics of the surrounding words w i-1 and w i+1 . This independence assumption between consecutive topics tends to generate too many distinct topics for each utterance. To tackle this problem, we resorted to a statistical word-alignment method based on the so-called IBM models, widely used in Machine Translation [START_REF] Brown | The mathematics of statistical machine translation: Parameter estimation[END_REF].

The use of the IBM models in our context offers several interests. First, the output of LDA generates a topic sequence for each word sequence and can be thus seen as a translation pair of a word-topic parallel corpus. Contrary to LDA, the HMM model [START_REF] Vogel | HMM-based word alignment in statistical translation[END_REF] as well as IBM models 2-4 take into account the word order in the translation pairs to align. Finally, the IBM models can be trained in an unsupervised way without providing any alignment between words and topics.

To refine the assignment of topics in the documents with the IBM models, we adopted the following approach. Since LDA tends to produce a too high number of different topics for each utterance, a filtering process is applied on the LDA outputs to keep only the most relevant topics for each document. We keep the χ max topics with the highest probabilities p(k i |w i , d) computed by LDA, where χ max is a value empirically fixed from the expected set of topics according to the number of words in an utterance. The IBM models are expected to correct some errors made by LDA, and in particular to assign words associated with the discarded topics to more likely topics. Two additional processing steps are applied on the topic sequences. Only the first occurrence is kept for consecutive repetitions of the same topic, as the IBM models can align several words with a single topic. Besides, the null concept (for out-of-domain or irrelevant word segments) is removed since this concept disturbs the alignments between words and concepts, as shown by a previous experiment done in a similar setup [START_REF] Huet | Unsupervised alignment for segmental-based language understanding[END_REF]. The IBM models already incorporate an empty word to account for source words that are not aligned with any target word; this empty word can be considered as the null concept for our task. This of course supposes that a manual tagging of LDA topics has allowed to define task-dependent concepts from topics (but can also be limited to identify the topics corresponding to the null concept).

In our experiments the statistical word alignment toolkit GIZA++ [START_REF] Och | A systematic comparison of various statistical alignment models[END_REF] is used to train the IBM models 1-4 as well as the HMM model. The IBM models are built using the expectation-maximization algorithm from a word-topic parallel corpus, where the topic sequences generated from LDA are disconnected from the words. To be able to train the most informative IBM model 4, the following training pipeline was considered: 5 iterations of IBM1, 5 iterations of HMM, 3 iterations of IBM3 and 3 iterations of IBM4. The IBM4 model obtained at the last iteration is finally used to align words and topics. In order to improve alignment, IBM models are usually trained in both directions (words towards concepts and vice versa) then symmetrised by combining them. For this purpose, we resorted to the default symmetrization heuristics used in Moses, a widely used machine translation system toolkit [START_REF] Koehn | Moses: Open source toolkit for statistical machine translation[END_REF].

Alignment with Integer Linear Programming (ILP)

Another approach to the re-alignment of LDA outputs is based on a general optimisation technique. Integer Linear Programming (ILP) is a widely used tool for modelling and solving combinatorial optimisation problems. It broadly aims at formulating a decision process as a set of equations or inequations (called constraints) which are linear with regards to some decision variables. An ILP is also composed of a linear objective function which represents the criterion (for instance a cost, a profit or like in this study a probability). Solving an ILP consists in assigning values to decision variables, such that all constraints are satisfied and the objective function is optimized. Readers may refer to [START_REF] Chen | Applied Integer Programming: Modeling and Solution[END_REF] for an overview of applications and methods of ILP.

We provide two ILP formulations for solving the topic assignment problem related to a given document. They both take as input data an ordered set d of words w i , i = 1...N , a set of K available topics and, for each word w i ∈ d and topic k = 1...K, the natural logarithm of the probability p(k|w i , d) that k is assigned to w i in the considered document d. Model [ILP ] simply finds the highest-probability assignment of one topic to each word in the document, such that at most χ max different topics are assigned.

[ILP ] : max

N i=1 K k=1 ln(p(k|w i , d)) x ik (3)
K k=1 x ik = 1 i (4)
y k -x ik ≥ 0 i, k (5)
K k=1 y k ≤ χ max (6)
x ik ∈ {0, 1} i, k

y k ∈ {0, 1} k
In this model, decision variable x ik is equal to 1 if topic k is assigned to word w i , and equal to 0 otherwise. Constraints 4 ensure that exactly one topic is assigned to each word. Decision variable y k is equal to 1 if topic k is used. Constraints 5 force variable y k to take a value of 1 if at least one variable x ik is not null. Moreover, constraints 6 limit the total number of topics used. The objective function 3 merely states that we want to maximize the total probability of the assignment. Through this model, our assignment problem is identified as a p-centre problem (see [START_REF] Revelle | Location analysis: A synthesis and survey[END_REF] for a survey on such location problems).

Numerical experiments show that [ILP ] tends to give sparse assignments: most of the time, adjacent words are assigned to different topics even if the total number of topics is correct. To prevent this unnatural behaviour, we modified [ILP ] to consider groups of consecutive words instead of isolated words. Model [ILP seg] partitions the document into segments of consecutive words, and assigns one topic to each segment, such that at most χ max segments are created. For the sake of convenience, we denote by p(k|w ij , d) = j l=i ln(p(k|w l , d)) the logarithm of the probability that topic k is assigned to all words from i to j in the current document.

[ILP seg] : max

N i=1 N j=i K k=1 p(k|w ij , d) x ijk (7) i j=1 N l=i K k=1 x jlk = 1 i (8) N i=1 N j=i K k=1
x ijk ≤ χ max (9)

x ijk ∈ {0, 1} i, j, k
In this model, decision variable x ijk is equal to 1 if topic k is assigned to all words from i to j, and 0 otherwise. Constraints 8 ensure that each word belongs to a segment that is assigned a topic. Constraints 9 limit the number of segments. Due to the small size of the instances considered in this paper, both [ILP ] and [ILP seg] are well solved by a direct application of an ILP solver.

Evaluation and Results

Media Corpus

The Media corpus is used to evaluate the proposed approach and to compare the various configurations. Media is a French corpus related to the domain of tourism information and hotel booking [START_REF] Bonneau-Maynard | Semantic annotation of the french media dialog corpus[END_REF]. 1,257 dialogues were recorded from 250 speakers with a wizard of Oz technique (a human agent mimics an automatic system). This dataset contains 17k user utterances and 123,538 words, for a total of 2,470 distinct words.

The Media data have been manually transcribed and semantically annotated. The semantic annotation uses 75 concepts (e.g. location, hotel-state, timemonth. . . ). Each concept is supported by a sequence of words, the concept support. The null concept is used to annotate every words segment that does not support any of the 74 other concepts (and does not bear any information wrt the task). On average, a concept support contains 2.1 words, 3.4 concepts are included in an utterance and 32% of utterances are restrained to a single word (generally "yes" or "no"). Table 1 gives the proportions of utterances according to the number of concepts in the utterance.

Notice that each utterance contains at least one concept (the null label being considered as a concept). As shown in Table 2, some concepts are supported by few segments. For example, 33 concepts are represented by less than 100 concept supports. Considering that, we can foresee that finding these poorly represented concepts will be extremely hard if not impossible for LDA. # concept supports [1,100[ [100,500[ [500,1k[ [1k,9k[ [9k,15k] # concepts 33 21 6 14 1 (null )

Evaluation Protocol

Unlike previous studies, we chose a fully automatic way to evaluate the systems.

In [START_REF] Siu | Semi-automatic acquisition of domain-specific semantic structures[END_REF], a manual process is introduced to reject induced classes or rules that are not relevant to the task and also to name the semantic classes with the appropriate label. Thus, they were able to evaluate their semi-supervised annotation on the Atis corpus. In [START_REF] Pargellis | Metrics for measuring domain independence of semantic classes[END_REF], the relevance of the generated semantic classes was manually evaluated giving a mark to each induced semantic rule.

To evaluate the unsupervised procedure it is necessary to associate each induced topic with a Media concept. To that purpose, the reference annotation is used to align topics with Media concepts at the word level. A co-occurrence matrix is computed and each topic is associated with its most co-occurring concept.

As Media reference concepts are very fine-grained, we also define a highlevel concept hierarchy containing 18 clusters of concepts. For example, a highlevel concept payment is created from the 4 concepts payment-meansOfPayment, payment-currency, payment-total-amount, payment-approx-amount; a high-level concept location corresponds to 12 concepts (location-country, location-district, location-street, . . . ). Thus, two levels of concepts are considered for the evaluation: high-level and fine-level.

The evaluation is presented in terms of the classical F-measure, defined as a combination of precision and recall measures. Two levels are also considered to measure topic assignment quality:

alignment corresponds to a full evaluation where each word is considered and associated with one topic/concept; generation corresponds to the set of topics/concepts generated for a turn (no order, no word-alignment).

System Descriptions

Four systems are evaluated in our experiments.

[LDA] is the result of the unsupervised learning of LDA models using Gibb-sLDA++ tool3 . It assigns the most probable topic to each word occurrence in a document as described in Section 2.2. This approach requires prior estimation of the number of clusters that are expected to be found in the data. To find an optimal number of clusters, we varied the number K of topics around 75, which is the number of reference concepts. 2k training iterations were made using default values for α and β.

[GIZA] is the system based on the GIZA++ toolkit4 which re-aligns for each utterance the topic sequence assigned by [LDA] to word sequence as described in Section 3.2.

[ILP ] and [ILP seg] systems are the results of the ILP solver IBM ILOG CPLEX5 applied to the models described in Section 3.3.

For the three last systems, the χ max value has to be fixed according to the desired concept annotation. As on average a concept support contains 2.1 words, χ max is defined empirically according to the number of words in the sequence: if i ∈ [START_REF] Bonneau-Maynard | Semantic annotation of the french media dialog corpus[END_REF][START_REF] Celikyilmaz | LDA based similarity modeling for question answering[END_REF]: χ max = i; if i ∈ [START_REF] Chen | Applied Integer Programming: Modeling and Solution[END_REF][START_REF] Lefèvre | Dynamic bayesian networks and discriminative classifiers for multistage semantic interpretation[END_REF] words: χ max = i -2; and for utterances containing more than 10 words: χ max = i/2.

For the sake of simplicity, single-word utterances are processed separately with prior knowledge. City names, months, days or answers (e.g. "yes", "no", "yeah") and numbers are identified in these one-word utterances.

Generated Topic Observations

In Table 3, six topics generated by [LDA] are represented by their 8 highest probability words. For topic 13, it is interesting noting that words have quite similar weights. The most represented words are "du" ("from") and "au" ("to") and other words are numbers or months, which a priori corresponds to a "timedate" concept. For topic 43, the word "oui" ("yes") is given a 0.62 probability, other words are "absolutely" or "okay" leading to an a priori "answer-yes" concept.

To observe which Media concept is associated with these topics, the list of the 3 most co-occurring concepts and the number of co-occurrences are shown in Table 4. The 2 most co-occurring concepts in a topic are the same in [LDA] and [LDA + ILP ]. However, the number of co-occurrences is higher in [ILP ] than in [LDA]. An entropy measure Ent(k) is computed for each topic k in order to evaluate the reliability of the topic-concept association over all the possible concepts. It is computed as follows:

Ent(k) = - concepts c p(c|k) log p(c|k) (10)
with

p(c|k) = #(c k) #k
The topic entropy is always smaller considering [ILP ] than [LDA]. This indicates that the re-assignment due to ILP alignment improves the reliability of the topic-concept association. Entropies measured with high-level concepts is always lower than with fine-level concepts, mainly because less classes are considered (18 instead of 75). Topic 18 is associated with the Location concept using the high-level configuration instead of the null one using the fine-level configuration, but the entropy is quite high. On the over hand, topic 43 has a low entropy, specifically with [ILP ]. This shows that word "yes" is strongly associated with the concept "Answer". Other topics representing the null concept can show entropies as low as 0.47 for topic 6 ("il", "y", "a", "qu'", "est-ce". . . ).

Results

Plots comparing the different systems implemented wrt the different evaluation levels in terms of F-measure are reported in Figures 3,4, 5 and 6 (high-level vs fine-level, alignment vs generation).

The [LDA] system generates topics which are correctly correlated with the high-level concepts. It can be observed that the bag of 75 topics reaches an Fmeasure of 61.5% (Fig. 3). When not enough topics are required from [LDA], induced topics are too wide to fit the fine-grained concept annotation of Media. On the other hand if too many high-level topics are required, the generation performance stays the same while a substantial decrease of the F-measure is observed in the alignment evaluation (Fig. 4). This effect can be explained by the automatic process to associate generated topics with reference concepts. Indeed, the increase of the number of topics makes them co-occur with many concepts, which often leads to assign them to the most frequent concept (null ) in the studied corpus.

From the high-level to fine-level concept evaluations, results globally decrease by 10%. An additional global loss of 10% is also observed between the generation and alignment scoring methods. In the fine-level evaluation, a maximum Fmeasure of 52.2% is observed for the generation of 75 topics (Fig. 5) whereas the F-measure decreases to 41.5% in the alignment evaluation (Fig. 6).

To conclude on the [LDA] system, we can see that it generates topics having a good correlation with the high-level concepts, seemingly the best representation level between topics and concepts. From these results it seems obvious that an additional step is needed to obtain a more accurate segmental annotation, which is expected with the following systems.

The [GIZA] system improves the [LDA] results. It is very likely that the filtering process helps to discard the irrelevant topics. Therefore, the automatic alignment between words and the filtered topics induced by [LDA] with IBM models seems more robust when more topics (a higher value for K) is required from [LDA], specifically in high-level concept alignment (Fig. 4).

Systems based on the ILP technique perform better than other systems whatever the evaluation. Considering [LDA] as the baseline, we can expect significant gains of performance. For example, an F-measure of 66% is observed for the ILP systems considering the high-level concept generation for 75 topics (Fig. 3), in which case the maximum for [LDA] was 61.5%, and an F-measure of 55% is observed (instead of 50.5% for [LDA]) considering the high-level concept alignment (Fig. 4).

No significant difference was finally measured between both ILP models for the concept generation evaluations. Even though [ILP seg] seems to obtain slightly better results in the alignment evaluation. This could be expected since [ILP seg] intrinsically yields alignments with grouped topics, closer to the reference alignment used for the evaluation.

It is worth noticing that unlike [LDA] system behaviour, the results of [ILP ] are not affected when more topics are generated by [LDA]. A large number of topics enables [ILP ] to pick up the best topic for a given segment in a longer selection list. As for [LDA], the same losses are observed between high-level and fine-level concepts and the generation and alignment paradigms. Nevertheless, an F-measure of 54.8% is observed with high-level concepts in the alignement evaluation (Fig. 4) that corresponds to a precision of 56.2% and a recall of 53.5%, which is not so low considering a fully-automatic high-level annotation system.

Conclusions and Perspectives

In this paper an approach has been presented for concept discovery and segmental semantic annotation of user's turns in an information-query dialogue system. An evaluation based on an automatic association between generated topics and expected concepts has shown that topics induced by LDA are close to high-level task-dependent concepts. The segmental annotation process increases performance both for the generation and alignment evaluations. On the whole these results confirm the applicability of the technique to practical tasks with expected gains in data production.

Future work will investigate the use of n-grams to extend LDA and to increase its accuracy for providing better hypotheses to the following segmentation techniques. Besides, other levels of data representation will be examined (use of lemmas, a priori semantic classes like city names. . . ) in order to better generalise on the data.

Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .

 3456 Fig.3. F-measure of the high-level concept generation as a function of the number of topics.

  Semantic concept representation for the query "give me the rate since I'd like a room charged not more than fifty euros".

	words	concept	normalized value
	donnez-moi	null
	le	refLink-coRef	singular
	tarif	object	payment-amount-room
	puisque	connectProp	imply
	je voudrais	null
	une chambre	number-room	1
	qui coûte	object	payment-amount-room
	pas plus de	comparative-payment	less than
	cinquante	payment-amount-integer-room 50
	euros	payment-unit	euro
	Fig. 1.

Table 1 .

 1 Proportion of user utterances as a function of the number of concepts in the utterance.

	# concepts	1	2 3 [4,72]
	% utterances 49.4 14.1 7.9 28.6

Table 2 .

 2 Number of concepts according to their occurrence range.

Table 3 .

 3 Examples of topics discovered by LDA (K = 100).

	Topic 0	Topic 13	Topic 18	Topic 35	Topic 33	Topic 43
	information	time-date	sightseeing	politeness	location	answer-yes
	words prob words	prob words prob words prob words prob words prob.
	d'	0.28 du		0.16 de	0.30 au	0.31 de	0.30 oui	0.62
	plus	0.17 au		0.11 la	0.24 revoir	0.27 Paris 0.12 et	0.02
	infor-							abso-
	mations 0.16 quinze	0.08 tour 0.02 madame 0.09 la	0.06 lument 0.008
	autres 0.10 dix-huit 0.07 vue 0.02 merci	0.08 près 0.06 autre	0.008
	détails 0.03 décembre 0.06 Eiffel 0.02 bonne 0.01 proche 0.05 donc	0.007
	obtenir 0.03 mars	0.06 sur	0.02 journée 0.01 Lyon 0.03 jour	0.005
								Notre-
	alors	0.01 dix-sept 0.04 mer 0.01 villes	0.004 aux	0.02 Dame 0.004
	souhaite 0.003 nuits	0.04 sauna 0.01 bientôt 0.003 gare 0.02 d'accord 0.004

Table 4 .

 4 Topic repartitions among the high-level or fine-level concepts for [LDA] and [ILP ] (K = 100).

		Topic 18		Topic 33		Topic 43
		sightseeing		location		answer-yes
	#occ concept	Ent(k) #occ concept	Ent(k) #occ concept	Ent(k)
				[LDA]
	292 Location	571 Location	705 Answer
	high 258 null	2.25 156 null	1.72 107 null	1.10
	94	Name	87	Comparative	27	Location
	258 null	226 loc.-distRel.	705 answer
	fine 136 loc.-placeRel.	2.78 190 loc.-city	2.57 107 null	1.19
	100 loc.-distRel.	156 null	17	object
				[ILP]
	300 Location	661 Location	846 Answer
	high 200 null	2.19 123 null	1.52 109 null	0.76
	102 Name	115 Comparative	24	Location
	200 null	234 loc.-distRel.	846 answer
	fine 163 loc.-placeRel.	2.64 223 loc.-city	2.44 109 null	0.80
	98	name-hotel	129 loc.-placeRel.	16	name-hotel

http://gibbslda.sourceforge.net/

http://code.google.com/p/giza-pp/

http://www-01.ibm.com/software/integration/optimization/ cplex-optimizer/

Acknowledgements

This work is supported by the ANR funded project PORT-MEDIA (www.port-media. org) and the LIA OptimNLP project (www.lia.univ-avignon.fr).