Christophe Jacquet

Ahmed Mohamed

Frédéric Boulanger

Cécile Hardebolle

Yacine Bellik

Building Heterogeneous Models at Runtime to Detect Faults in Ambient-Intelligent Environments

Keywords: Heterogeneous modeling, models@run.time, models of computation, ambient intelligence

This paper introduces an approach for fault detection in ambient-intelligent environments. It proposes to compute predictions for sensor values, to be compared with actual values. As ambient environments are highly dynamic, one cannot pre-determine a prediction method. Therefore, our approach relies on (a) the modeling of sensors, actuators and physical effects that link them, and (b) the automatic construction at run-time of a heterogeneous prediction model. The prediction model can then be executed on a heterogeneous modeling platform such as ModHel'X, which yields predicted sensor values.

Introduction

Ambient intelligence is a vision in which physical environments are equipped with electronic devices that make them sensitive and responsive to the presence of people [START_REF] Ducatel | Scenarios for ambient intelligence in[END_REF]. Overall, it comprises systems that activate some actuators based on data provided by some sensors, applying reasoning and decision techniques.

However, software and hardware may suffer failures, and ambient intelligent systems are at risk because of their vast number of sensors and actuators. As people are expected to rely on these systems more and more in the future, being able to detect faults is a major concern. This paper focuses specifically on the detection of hardware faults. It does not investigate the precise identification of the faulty component(s), nor does it deal with software faults.

In software, mechanisms such as exceptions can report failures. Likewise, an actuator can provide a return code, but this reflects only the transmission of orders to the hardware, not the final result. For instance, when the system activates a light bulb, it receives an acknowledgement that confirms the switch-on of the electrical circuit, but this does not necessarily mean that the bulb is really on (the bulb may be damaged for instance). Therefore, a reliable ambient-intelligent application needs to assess at run-time the real status of its actuators.

To address the issue, the designer could pre-determine control loops using designated sensors. However, the particularity of ambient systems is that physical resources, mainly sensors and actuators, are not necessarily known at design time: instead, they are dynamically discovered at run-time. In consequence, such control loops cannot be pre-determined. The diagnosis strategy, the links between sensors and actuators, need to be automatically determined at run-time.

We have proposed a fault-detection approach that relies only on sensors discovered at run-time, thereby not requiring the addition of specific devices for diagnosis purposes. To achieve this, we have introduced a metamodel for describing ambient-intelligent systems, in which actuators and sensors are modeled independently, and are loosely coupled. The links between them are deduced automatically at run-time thanks to the thorough modeling of the physical effects involved, i.e. the physical laws such as light propagation or heat diffusion.

More precisely, we build a prediction model automatically at run-time. Executing this model, the system determines what values are expected to be read on sensors. Comparing the output of this prediction model with the actual output of sensors, it is able to detect faults. As the prediction model applies physical laws, it contains calculations. Besides, it must also model the behavior of objects. For example, an actuator such as a light bulb has state: it may be switched off, switched on but warming up, or switched on with full brightness. Therefore, the prediction model must also contain state, for instance state machines. In consequence the prediction model is heterogeneous, so we use a heterogeneous modeling tool, ModHel'X, to represent it and to execute it.

This overall approach for diagnosis has already been presented; see [START_REF] Mohamed | A fault Detection and Diagnosis Framework for Ambient Intelligent Systems[END_REF][START_REF] Jacquet | An Ambient Assisted Living Framework with Automatic Self-Diagnosis[END_REF] for more details. The contribution of this paper is the explicit construction and execution of a heterogeneous prediction model at run-time. We show that a heterogeneous modeling tool such as ModHel'X is well adapted for this.

The paper is structured as follows. Section 2 summarizes our approach. It relies on an example to show the need for building a heterogeneous model. The automated methodology for generating such a model is detailed in Section 3. Section 4 discusses the benefits and limitations of our current approach; Section 6 summarizes the paper and gives some perspectives.

Our Approach

As seen above, ambient intelligent environments being dynamic by nature, the designers cannot pre-determine links between actuators and sensors. Therefore we introduce an approach in which such links can be determined automatically.

Throughout this paper, we assume that all objects can communicate with the system. They send notifications to an object management process when entering or leaving the environment and they can describe themselves. We suppose that an object identifies itself as an instance of a given class, which completely describes its features and possible behaviors (see Sections 2.1 and 2.2). In addition, an object may report its coordinates each time it moves. A system such as Ubisense [START_REF] Steggles | The Ubisense smart space platform[END_REF] can provide such communication and localization capabilities off-the-shelf.

A Loosely Coupled Meta-Model for Ambient Systems

In the physical world, actuators and sensors are linked through the phenomena generated by the former and detected by the latter. To reflect this, we have created a metamodel in which we model actuators, sensors and physical phenomena (called effects). We model the fact that (a) a certain category of actuators produce a given effect, and that (b) a certain category of sensors detect a given physical property, consequence of a given effect.

For instance, we model that any light actuator (e.g. a lamp) produces light, more precisely an effect that we call luminous flux. Conversely, any light sensor detects a physical property called illuminance. Illuminance at a given position can easily be calculated knowing the light sources and their luminous fluxes.

This approach is translated into an abstract metamodel (see Fig. 1 left), which is specialized for every kind of effect, for instance for light (see Figure 1 right). The formulae that describe an effect are structured as a set of functions attached to the effect. For the propagation of light they are as follows:

distance(A, B) = (A.x -B.x) 2 + (A.y -B.y) 2
(1)

illum(A, B) = A.flux (distance(A, B)) 2 (2)
B.illuminance = A∈LightActuators illum(A, B) (3)
The notation Obj.prop refers to the property prop of the object Obj. Some properties define an effect (e.g., the flux emitted by a light bulb, its position in space); we suppose that they are known. Some are observable by a sensor (e.g., the illumination received by a light sensor ) and we wish to predict them.

In the formulae above, A and B are free variables that stand for any object. LightActuators is the set of light actuators. Formula (1) defines a function, called distance, that computes the 2D distance between two ambient objects A and B. In formula (2), illum(A, B) is the illuminance contributed by object A onto object B. Formula (3) states that the total illuminance on object B is the sum of the individual contributions of every light actuator onto object B.

In this example, the light effect is defined quite precisely. More generally, depending on the application's needs, an effect can be defined at various levels of granularity. For instance, we could have used a simple boolean rule ("if a light bulb is on in a room then the light sensors in that room normally detect light").

Using the Models to Predict Expected Behavior

At run-time, the specialized metamodel is instantiated to reflect the actual objects present in the environment. For instance, let us suppose that at some point a room contains two light actuators la1 and la2, and a light sensor ls1. Initially, there is no link between the actuator and sensors. The links will be deduced automatically using available information about their types. For a given

Fig. 1. Abstract metamodel describing the objects of the ambient environment (left), and a specialization of it to account for a specific effect: the emission of light (right).

(1), ( 2) and ( 3) refer to the corresponding formulae defined in the text.

configuration of the environment, these links make up a prediction model that may be used at will to compute new expected sensor output when some known properties change.

In this section, we show on the example with the light sensors and actuators how to build a prediction model, before studying the general automatic method in Section 3. We want to predict the output of a sensor, so we look for the formula that can calculate it. It gives us an expression that may contain function calls. So we recursively use the formulas to apply functions and to eventually determine a simple mathematical expression that gives the result. We need to determine the illuminance perceived by ls1, so we start by applying formula (3) symbolically:

ls1.illuminance = illum(la1, ls1) + illum(la2, ls1) (4)
Then we process the two function calls to illum recursively using formula (2), and after that we do the same with distance using formula (1):

ls1.illuminance = la1.flux (distance(la1, ls1)) 2 + la2.flux (distance(la2, ls1)) 2 (5) = la1.flux (la1.x -ls1.x) 2 + (la1.y -ls1.y) 2 + la2.flux (la2.x -ls1.x) 2 + (la2.y -ls1.y) 2 (6)
We obtain a symbolic expression that contains no function call, and that depends only on object properties. These properties are of two kinds: (a) structural properties supposed to be known, such as the x and y coordinates of objects, (b) properties depending on the current state of objects, such as la1.flux and la2.flux. If at each instant we know the fluxes emitted by la1 and la2, then we can use formula [START_REF] Mohamed | A fault Detection and Diagnosis Framework for Ambient Intelligent Systems[END_REF] to predict the value reported by ls1. An inconsistency between the expected value and the actual value would indicate a fault.

If at some point the expansion of a formula cannot eliminate remaining free variable, this means that the set of formulae is not complete. It denotes an issue in the design of the model of an effect.

We note that actuator characteristics such as the luminous fluxes are not necessarily known directly at all times. For instance, a Compact Fluorescent Lamp (CFL) has warming up and cooling periods that have an impact on its flux. To account for this, a behavioral model can be associated with the actuators. For example, Figure 2 is a timed finite state machine that coarsely models a CFL. Upon entry in the system, an actuator is supposed to be in its initial state. Now that we have seen our approach on an example, let us formalize it.

A Workflow for Fault Detection

We can picture diagnosis as a process that runs in parallel with the actual system. This process must have access to all the events of the process responsible for object management: notifications for object addition or removal, object movements, and commands sent to objects such as actuators. In response, the diagnosis process can build, update and execute a prediction model.

We have just seen that a prediction model may contain parts of different natures: (a) formulae, for instance formula ( 6), (b) behavioral sub-models, for instance the state machine of Figure 2. Therefore, a prediction model is a heterogeneous model, and the adaptation between its heterogeneous parts must be defined carefully. For this reason, we have chosen to model it explicitly using ModHel'X, a heterogeneous modeling tool that is being developed at Supélec (see Section 3.1). The whole run-time workflow may be as follows (see Figure 3):

(1) The object management process maintains the run-time, dynamic model of the system's objects of interest, that conforms to the metamodel in Figure 1. The main focus of this paper is step (2), described in Section 3.2. First the heterogeneous modeling tool ModHel'X is introduced in Section 3.1, which gives some insights on step (3). Steps ( 1) and ( 4) are out of the scope of this paper.

Generation of a Heterogeneous Prediction Model

Heterogeneous Modeling with ModHel'X

ModHel'X [START_REF] Boulanger | Semantic adaptation for models of computation[END_REF] is an experimental framework for heterogeneous model execution. ModHel'X allows one (a) to describe the structure of heterogeneous models, (b) to define the semantics of each modeling language used, and (c) to define the semantic adaptation between heterogeneous parts of a model.

ModHel'X relies on a metamodel that defines a common abstract syntax for the structure of all models. As we can see on Figure 6, a model contains blocks (gray rectangles with rounded corners) that are connected through relations (arrows) between their pins (black circles).

One attaches semantics to a model using models of computation (MoCs). A MoC is a set of rules that define the nature of the components of a model and how their behaviors are combined to produce the behavior of the model. ModHel'X comes with off-the-shelf MoCs including Timed Finite State Machines (TFSM), Discrete Events (DE) and Synchronous Data Flow (SDF). TFSM are state machines with timed transitions. DE and SDF work like their implementations in Ptolemy II [START_REF] Eker | Taming heterogeneity -the Ptolemy approach[END_REF]: in DE, blocks are processes that exchange timestamped events that can contain data; in SDF, blocks are data-flow operators that consume and produce a fixed number of data samples on their pins each time they are activated. On Figure 6, the MoC of the overall model is DE, represented by a diamond-shaped label.

Heterogeneity is handled through hierarchy: ModHel'X introduces special blocks called interface blocks whose internal behavior is described by a model obeying a specific MoC. Figure 6 contains three interface blocks. They act as adapters between the outer MoC and their inner MoC, which may differ. Three aspects must be adapted [START_REF] Boulanger | Semantic adaptation for models of computation[END_REF]: data (which may not have the same form in the inner and outer models), time (the notion of time and the time scales may differ in the inner and outer models) and control (the instants at which it is possible or necessary to communicate with a block through its interface).

Using Effects to Deduce a Prediction Model

In input, the prediction model receives updates about non-structural changes in the environment: movements of objects, commands sent to actuators, etc. In contrast, structural changes, such as the removal or the addition of an object, trigger a re-build of the prediction model. In output, the prediction model sends expected sensor values to a fault detection layer that compares them to actual values and decides which differences are abnormal.

The remainder of this section describes the fully-automated procedure used to build the prediction model.

The first step is to use the effects as pivots between sensors and actuators, as explained on the example of Section 2.2. The procedure starts at sensor outputs and recursively applies functions so as to build a symbolic expression without function calls. This symbolic expression constitutes a computational model to be evaluated at each instant. We use Synchronous Dataflow (SDF) as its model of computation. SDF treats the computational model as a sampled system, computing its new outputs regularly, for instance each second. When recursively applying the functions, two cases can occur:

-If a function contains iterating operators, such as the sigma notation for a sum, then this operator must be expanded depending on the current situation of the environment. For instance, when processing the summation operator that iterates over "all the light sources" in formula (3), we actually perform this iteration and create as many branches in the computational model as there are light sources. So a function with an iterating operator is decomposed into elementary operators, each represented by an SDF block. -If a function contains no iterating operator, then we choose to translate it into a single SDF block. We could further decompose it into elementary operators, but our choice generates simpler models.

Figure 4 depicts the SDF model obtained for the running example. The upper part deals with light actuator la1, the lower part deals with la2. This shows how the current situation of the environment determines the structure of the model. The second step is to include the actuators' behavioral models into the larger prediction model. This is necessary because some input of the computational model may depend on the current state of some actuator. For instance, the luminous flux of a light bulb depends its current state, as shown on Figure 2.

The state machines are modeled using the TFSM MoC. Using timed state machines is necessary, because some transitions fire spontaneously after some time (for instance on Figure 2, the state machine transitions to state "on" 30 seconds after entering state "heating up").

At this point we have two parts in the model: a computational dataflow model using the SDF MoC, and a number of state machines using the TFSM MoC. These two parts must be interconnected. The discrete events (DE) MoC is well-suited to compose SDF and TFSM models. Discrete events allow state changes to be propagated to the SDF model. Therefore, in all cases we build automatically a top-level model conforming to the DE MoC. The TFSMs and the SDF model are embedded into this DE model, and semantic adaptation is performed using interface blocks generated from standard patterns.

At the boundary between DE and TFSM, in input, events such as "switch on this lamp" have to be forwarded to the TFSM. In output, the TFSM produces events such as "Light flux now at 1500 lm" that also just have to be forwarded to DE. ModHel'X provides a generic DE/TFSM adapter, to be parameterized with a mapping between DE and TFSM events. Figure 5 shows how the state machine for la2, an incandescent lamp, is embedded into a DE interface block (in gray). A similar interface block is added around la1's state machine. A similar adaptation is added around the SDF model of Figure 4. However, in input, an event such as "Light flux now at 1500 lm" cannot be taken into account immediately in general, because an SDF model is a sampled system that reacts at specific instants. Therefore, events are translated into values that are memorized so as to be provided to the model at its next activation instant. For example, "Light flux now at 1500 lm" creates a new value of 1500 on the pin corresponding to the actuator's light flux, and after receiving this event, this new value is emitted at each SDF instant. In output, the adapter sends an event in DE only when a value changes in SDF, so as not to create irrelevant events.

The overall prediction model for our example is depicted on Figure 6. It uses data from an object management service to update the computations. These data models. However, our theoretical approach is not linked with ModHel'X specifically; it could use other modeling tools such as Ptolemy II or Matlab/Simulink as well.

One could argue that the behavioral models used in the example are very rudimentary: for instance a real CFL does not suddenly switch to full light after the warming up time. A more accurate model would represent a continuous increase of the luminous flux from switch on. Integrating such a model in our framework is possible indeed: as the behavioral models of actuator are executed onto a versatile heterogeneous modeling platform, one can use any MoC and not just TFSM, one could use for instance the continuous time (CT) MoC.

Currently, uncertainties are not taken into account. However for the approach to scale to real-world scenarios it will be necessary to do so, as sensors and actuators have limited accuracy. Their margin of error is generally known, so a possible approach would be to calculate uncertainty explicitly along with the calculation of the expected results. Also, the model of a physical effect may be too simplistic. For instance the simple light model described in this paper does not model reflections, transmission of light from one room to another, etc. Such perturbations can have an impact on the actual values measured by the sensors, adding to the uncertainties.

Related Work

[2] underlines the importance of failure detection for ambient (or pervasive) systems, especially when they are used in to support healthcare. Devices that cease to function are easy to detect using heartbeat messages, but detecting Byzantine faults (devices yielding erroneous results) is deemed much harder. This is the kind of faults that we try to detect here. Fault detection is an important matter in the related field of autonomic computing too. Most methods learn to recognize faults from data sets: some of them recognize patterns characteristic of faults, others construct a set of normal behaviors [START_REF] Shevertalov | Using search methods for selecting and combining software sensors to improve fault detection in autonomic systems[END_REF]. Here, instead of learning techniques, we use automatic model transformations.

Some approaches use static analysis to detect defects in the adaptation logic of context-aware systems [START_REF] Sama | Model-based fault detection in context-aware adaptive applications[END_REF]. Contrariwise, we perform fault detection at runtime, in order to detect hardware failures. To account for the highly dynamic nature of ambient environments, we do not rely on a pre-existing model of system behavior.

Conclusions and Perspectives

This paper has introduced an approach for generating predictions of sensor values in an ambient intelligent environment. These predictions are to be compared with actual values, in order to detect faults. As ambient environments are highly dynamic, one cannot pre-determine a prediction method. Instead, the system must determine at run-time how predictions can be made. Our approach relies on (a) the modeling of sensors, actuators and physical effects that link them, and (b) the automatic construction of a heterogeneous prediction model. This model can then be executed on the heterogeneous modeling platform ModHel'X. We have shown that this approach is well adapted for taking into account both physical laws and behavioral models of objects, namely actuators.

We have implemented the automatic procedure described in Section 3.2 in a demonstrator that has enabled us to validate this approach in simulated conditions. The simulator uses the ModHel'X API to directly instantiate the prediction model. A next step would be to test it in real-scale in an ambient intelligent environment.

Other perspectives include a focus on managing the evolution of the prediction model when its structure changes, and using various MoCs for finer-grained behavioral models, beyond simple state machines. The uncertainties stemming from limited component accuracy and simplifications made when modeling physical effects will need to be dealt with too. Future work could also investigate the decisional process involved when eventually making a diagnosis.

Fig. 2 .

 2 Fig. 2. Simple timed finite state machine for modeling the behavior of a CFL.

( 2 )( 4 )Fig. 3 .

 243 Fig. 3. Overall workflow of the approach.

Fig. 4 .

 4 Fig. 4. SDF computational model for the running example.

Fig. 5 .

 5 Fig. 5. The TFSM model of an incandescent lamp, embedded into a DE interface block.

may be simple values, fed directly to the computations, or events that trigger state changes of some of the TFSMs, in turn generating new values fed to the computations. The results of the computational model are provided to a fault detection layer that is not described here.

Discussion

We have shown a method for generating a prediction model automatically. The model is regenerated each time the structure of the environment changes, namely when a new object is introduced in the ambient environment, and each time an object is removed. These events are relatively infrequent compared to values changes. When only property values change, it is not necessary to regenerate the model because the structure does not change; we must only continue model execution with new input values.

Another problem arises here: how can we maintain the state of the model when its structure changes? For instance, if in our example at some point a third light actuator la3 appears in the room, the prediction model is regenerated. While doing so, the states of la1 and la2 should be preserved. ModHel'X does not support model evolution currently; this issue has not been addressed yet.

We used ModHel'X to build and run the prediction model because it allows one to specify semantic adaptation explicitly at the border between heterogeneous


Claire Gardent
email: claire.gardent@loria.fr

Lina M Rojas Barahona

Using Paraphrases and Lexical Semantics to Improve the Accuracy and the Robustness of Supervised Models in Situated Dialogue Systems

This paper explores to what extent lemmatisation, lexical resources, distributional semantics and paraphrases can increase the accuracy of supervised models for dialogue management. The results suggest that each of these factors can help improve performance but that the impact will vary depending on their combination and on the evaluation mode.

Introduction

One strand of work in dialog research targets the rapid prototyping of virtual humans capable of conducting a conversation with humans in the context of a virtual world. In particular, question answering (QA) characters can respond to a restricted set of topics after training on a set of dialogs whose utterances are annotated with dialogue acts [START_REF] Leuski | A statistical approach for text processing in virtual humans[END_REF].

As argued in [START_REF] Sagae | Towards natural language understanding of partial speech recognition results in dialogue systems[END_REF], the size of the training corpus is a major factor in allowing QA characters that are both robust and accurate. In addition, the training corpus should arguably be of good quality in that (i) it should contain the various ways of expressing the same content (paraphrases) and (ii) the data should not be skewed. In sum, the ideal training data should be large (more data is better data) ; balanced (similar amount of data for each class targeted by the classifier) and varied (it should encompass the largest possible number of paraphrases and synonyms for the utterances of each class).

In this paper, we explore different ways of improving and complementing the training data of a supervised QA character. We expand the size and the quality (less skewed data) of the training corpus using paraphrase generation techniques. We compare the performance obtained on lemmatised vs. non lemmatised data. And we investigate how various resources (synonym dictionaries, WordNet, distributional neighbours) can be used to handle unseen words at run time.

Related work

Previous work on improving robustness of supervised dialog systems includes detecting and handling out of domain utterances for generating feedback [START_REF] Richard Lane | Example-based training of dialogue planning incorporating user and situation models[END_REF] ; using domain-restricted lexical semantics [START_REF] Hardy | Data-driven strategies for an automated dialogue system[END_REF] ; and work on manual data expansion [START_REF] Devault | Toward learning and evaluation of dialogue policies with text examples[END_REF]. Our work follows up on this research but provides a systematic investigation of how data expansion, lemmatisation and synonym handling impacts the performance of a supervised QA engine.

Experimental Setup

We run our experiments on a dialog engine developed for a serious game called Mission Plastechnologie. In this game, the player must interact with different virtual humans through a sequence of 12 subdialogs, each of them occurring in a different part of the virtual world.

Training Data. The training corpus consists of around 1250 Human-Human dialogues which were manually annotated with dialog moves. As the following dialog excerpt illustrates, the dialogs are conducted in French and each dialog turn is manually annotated using a set of 28 dialog acts. For a more detailed presentation of the training corpus and of the annotation scheme, the reader is referred to (Rojas- Barahona et al., 2012a) Dialog Systems For our experiments, we use a hybrid dialog system similar to that described in (Rojas Barahona et al., 2012b;Rojas Barahona and Gardent, 2012). This system combines a classifier for interpreting the players utterances with an information state dialog manager which selects an appropriate system response based on the dialog move assigned by the classifier to the user turn. The classifier is a logistic regression classifier1 which was trained for each subdialog in the game. The features used for training are the set of content words which are associated with a given dialog move and which remain after TF*IDF2 filtering. Note that in this experiment, we do not use contextual features such as the dialog acts labeling the previous turns. There are two reasons for this. First, we want to focus on the impact of synonym handling, paraphrasing and lemmatisation on dialog management. Removing contextual features allows us to focus on how content features (content words) can be improved by these mechanisms. Second, when evaluating on the H-C corpus (see below), contextual features are often incorrect (because the system might incorrectly interpret and thus label a user turn). Excluding contextual features from training allows for a fair comparison between the H-H and the H-C evaluation.

Test Data and Evaluation Metrics We use accu-racy (the number of correct classifications divided by the number of instances in the testset) to measure performance and we carry out two types of evaluation. On the one hand, we use 10-fold crossvalidation on the EmoSpeech corpus (H-H data). On the other hand, we report accuracy on a corpus of 550 Human-Computer (H-C) dialogues obtained by having 22 subjects play the game against the QA character trained on the H-H corpus. As we shall see below, performance decreases in this second evaluation suggesting that subjects produce different turns when playing with a computer than with a human thereby inducing a weak out-of-domain effect and negatively impacting classification. Evaluation on the H-H corpus therefore gives a measure of how well the techniques explored help improving the dialog engine when used in a real life setting. Correspondingly, we use two different tests for measuring statistical significance. In the H-H evaluation, significance is computed using the Wilcoxon signed rank test because data are dependent and are not assumed to be normally distributed. When building the testset we took care of not including paraphrases of utterances in the training partition (for each paraphrase generated automatically we keep track of the original utterance), however utterances in both datasets might be generated by the same subject, since a subject completed 12 distinct dialogues during the game. Conversely, in the H-C evaluation, training (H-H data) and test (H-C data) sets were collected under different conditions with different subjects therefore significance was computed using the McNemar sign-test [START_REF] Thomas | Approximate statistical tests for comparing supervised classification learning algorithms[END_REF].

Paraphrases, Synonyms and Lemmatisation

We explore three main ways of modifying the content features used for classification : lemmatising the training and the test data ; augmenting the training data with automatically acquired paraphrases ; and substituting unknown words with synonyms at run time.

Lemmatisation We use the French version of Treetagger 3 to lemmatise both the training and the test data. Lemmas without any filtering were used to train classifiers. We then compare performance with and without lemmatisation. As we shall see, the lemma and the POS tag provided by TreeTagger are also used to lookup synonym dictionaries and EuroWordNet when using synonym handling at run time.

Paraphrases : [START_REF] Devault | Toward learning and evaluation of dialogue policies with text examples[END_REF] showed that enriching the training corpus with manually added paraphrases increases accuracy. Here we exploit automatically acquired paraphrases and use these not only to increase the size of the training corpus but also to better balance it 4 . We proceed as follows.

First, we generated paraphrases using a pivot machine translation approach where each user utterance in the training corpus (around 3610 utterances) was translated into some target language and back into French. Using six different languages (English, Spanish, Italian, German, Chinese and Arabian), we generated around 38000 paraphrases. We used Google Translate API for translating. Second, we eliminate from these paraphrases, words that are likely to be incorrect lexical translations by removing words with low normalized term 4. The Emospeech data is highly skewed with some classes being populated with many utterances and others with few.

Algorithm extendingDataWithParaphrases(trainingset ts) 1. Let c be the set of categories in ts. 2. µ be the mean of train instances per category 3. σ be the standard deviation of train instances per category 4. Let N pc be the number of paraphrases per category 5. Let lp ← min N pc j 6. Repeat 7.

set i ← 0 8.

N instc i be the number of instances per category c i 9.

d i ← N instc i -µ 10. if d i < σ then 11.
N instc i ← lp 12. else 13.

N instc i ← frequency (< 0.001) across translations i.e., lexical translations given by few translations and/or translation systems. We then preprocessed the paraphrases in the same way the utterances of the initial training corpus were preprocessed i.e., utterances were unaccented, converted to lower-case and stop words were removed, the remaining words were filtered with TF*IDF. After preprocessing, duplicates were removed.

Third, we added the paraphrases to the training data seeking to improve the balance between dialog moves per dialog, as shown in Figure 1. To this end, we look for the category c with the lowest number of paraphrases l p (line 5). We then compute the deviation d i for each dialog move c i from the mean µ in the original training set (line 9). If the deviation d i is lower than the standard deviation then we add l p number of paraphrases instances (line 11). Conversely, if d i is higher than the standard deviation, we reduce the number of instances to be added by half lp 2 (line 13). Table 1 shows the original and the extended training data for the third sub-dialog in the Emospeech game. In this dialogue the player is supposed to ask information about the joystick plans (f ind_plans, which is the mandatory goal). The categories cover mandatory and optional goals and general dialogue acts, such as greetings, asking for help, confirm and disconfirm, acknowledgment and out of topic questions (i.e. other).

Substituting Synonyms for Unknown Words A word is unknown, if it is a well-formed French word 5 and if it does not appear in the training corpus. Conversely, a word is known if it is not unknown.

When an unknown word w is detected in a player utterance at runtime, we search for a word w which occurs in the training data and is either a synonym of w or a distributional neighbour. After disambiguation, we substitute the unknown word for the synonym.

To identify synonyms, we make use of two lexical resources namely, the French version of EuroWord-Net (EWN) [START_REF] Vossen | EuroWordNet : a multilingual database with lexical semantic networks[END_REF], which includes 92833 synonyms, hyperonyms and hyponyms pairs, and a synonym lexicon for French (DIC) 6 which contains 38505 lemmas and 254149 synonym pairs. While words are categorised into Noun, Verbs and Adjectives in EWN, DIC contains no POS tag information.

To identify distributional neighbours, we constructed semantic word spaces for each subdialog in the EmoSpeech corpus 7 using random indexing (RI) 8 on the training corpus expanded with paraphrases. Using the cosine measure as similarity metrics, we then retrieve for any unknown word w, the word w which is most similar to w and which appear in the training corpus.

For lexical disambiguation, two methods are compared. We use the POS tag provided by TreeTagger. In this case, disambiguation is syntactic only. Or we pick the synonym with highest probability based on a trigram language model trained on the H-H corpus 9 .

Results and Discussion

Table 2 summarises the results obtained in four main configurations : (i) with and without paraphrases ; (ii) with and without synonym handling ; (iii) with and without lemmatisation ; and (iv) when 5. A word is determined to be a well-formed French word if it occurs in the LEFFF dictionary, a large-scale morphological and syntactic lexicon for French [START_REF] Sagot | The Lefff, a freely available and large-coverage morphological and syntactic lexicon for French[END_REF] 6. DICOSYN (http ://elsap1.unicaen.fr/dicosyn.html). 7. We also used distributional semantics from the Gigaword corpus but the results were poor probably because of the very different text genre and domains between the the Gigaword and the MP game.

8. Topics are Dialog acts while documents are utterances ; we used the S-Space Package http://code.google.com/p/ airhead-research/wiki/RandomIndexing 9. We used SRILM (http://www.speech.sri.com/ projects/srilm) combining lemmatisation with synonym handling. We also compare the results obtained when evaluating using 10-fold cross validation on the training data (H-H dialogs) vs. evaluating the performance of the system on H-C interactions.

Overall Impact The largest performance gain is obtained by a combination of the three techniques explored in this paper namely, data expansion, synonym handling and lemmatisation (+8.9 points for the cross-validation experiment and +2.3 for the H-C evaluation).

Impact of Lexical Substitution at Run Time Because of space restrictions, we do not report here the results obtained using lexical resources without lemmatisation. However, we found that lexical resources are only useful when combined with lemmatisation. This is unsurprising since synonym dictionaries and EuroWordNet only contain lemmas. Indeed when distributional neighbours are used, lemmatisation has little impact (e.g., 65.11% using distributional neighbours without lemmatisation on the H-H corpus without paraphrases vs. 66.41% when using lemmatisation).

Another important issue when searching for a word synonym concerns lexical disambiguation : the synonym used to replace an unknown word should capture the meaning of that word in its given context. We tried using a language model trained on the training corpus to choose between synonym candidates (i.e., selecting the synonym yielding the highest sentence probability when substituting that synonym for the unknown word) but did not obtain a significant improvement. In contrast, it is noticeable that synonym handling has a higher impact when using EuroWordNet as a lexical resource. Since Eu-roWordNet contain categorial information while the synonym dictionaries we used do not, this suggests that the categorial disambiguation provided by Tree-Tagger helps identifying an appropriate synonym in EuroWordNet.

Finally, it is clear that the lexical resources used for this experiment are limited in coverage and quality. We observed in particular that some words which are very frequent in the training data (and thus which could be used to replace unknown words) do not occur in the synonym dictionaries. For instance when using paraphrases and dictionaries (fourth row and fourth column in Table 2) 50% of the unknown words were solved, 17% were illformed and 33% remained unsolved. To compensate this deficiency, we tried combining the three lexical resources in various ways (taking the union or combining them in a pipeline using the first resource that would yield a synonym). However the results did not improve and even in some cases worsened due probably to the insufficient lexical disambiguation. Interestingly, the results show that paraphrases always improves synonym handling presumably because it increases the size of the known vocabulary thereby increasing the possibility of finding a known synonym.

In sum, synonym handling helps most when (i) words are lemmatised and (ii) unknown words can be at least partially (i.e., using POS tag information) disambiguated. Moreover since data expansion increases the set of known words available as potential synonyms for unknown words, combining synonym handling with data expansion further improves accuracy.

Impact of Lemmatisation When evaluating using cross validation on the training corpus, lemmatisation increases accuracy by up to 3.42 points indicating that unseen word forms negatively impact accuracy. Noticeably however, lemmatisation has no significant impact when evaluating on the H-C corpus. This in turn suggests that the lower accuracy obtained on the H-C corpus results not from unseen word forms but from unseen lemmas.

Impact of Paraphrases

On the H-H corpus, data expansion has no significant impact when used alone. However it yields an increase of up to 8.27 points and in fact, has a statistically significant impact, for all configurations involving lemmatisation. Thus, data expansion is best used in combination with lemmatisation and their combination permits creating better, more balanced and more general training data. On the H-C corpus however, the impact is negative or insignificant suggesting that the decrease in performance on the H-C corpus is due to content words that are new with respect to the training data i.e., content words for which neither a synonym nor a lemma can be found in the expanded training data.

Conclusion

While classifiers are routinely trained on dialog data to model the dialog management process, the impact of such basic factors as lemmatisation, automatic data expansion and synonym handling has remained largely unexplored. The empirical evaluation described here suggests that each of these factors can help improve performance but that the impact will vary depending on their combination and on the evaluation mode. Combining all three techniques yields the best results. We conjecture that there are two main reasons for this. First, synonym handling is best used in combination with POS tagging and lemmatisation because these supports partial lexical semantic disambiguation. Second, data expansion permits expanding the set of known words thereby increasing the possibility of finding a known synonym to replace an unknown word with.

  : 01_dialogDirecteur-Tue Jun 14 11 :04 :23 2011 >M.Jasper : Bonjour, je suis M.Jasper le directeur. || greet (Hello, I am the director, Mr. Jasper.) >M.Jasper : Qu'est-ce que je peux faire pour vous ? || ask(task(X))

	(What can I do for you ?)
	>Lucas : je dois sauver mon oncle || first_step
	(I must rescue my uncle)
	>M.Jasper : Pour faire votre manette, il vous faut
	des plans. Allez voir dans le bureau d'études,
	ils devraient y être. || inform(do(first_step))
	(To build the joystick you will need the plans.
	You will find them in the Designing Office.)
	>M.Jasper : Bonne Chance ! || quit
	(Good Luck !)

dialog

TABLE 1 :

 1 Skewed and Balanced Data on a sample subdialog. The category with lowest number of paraphrases is greet, with 62 paraphrases, hence l p = 62. All categories were increased by 62 except find_plans and yes that were increased by half : 31.

TABLE 2 :

 2 Accuracy on the H-H and on the H-C corpus. The star denotes statistical significance with the Wilcoxon test (p < 0.005) used for the HH corpus and the McNemar test (p < 0.005) for the HC corpus.

		H		Lemmatisation
	H-H	Orig.	Lemmas	+EWN	+DIC	+RI
	Orig.	65.70% ± 5.62	66.04% ± 6.49	68.17% ± 6.98	67.92% ± 4.51	66.83% ± 5.92
	Parap. 70.89% ± 6.45	74.31% ± 4.78* 74.60% ± 5.99*	73.07% ± 7.71*	72.63% ± 5.82*
	H-C	Orig.	Lemmas	+EWN	+DIC	+RI
	Orig.	59.71% ± 16.42 59.88% ± 7.19	61.14% ± 16.65	61.41% ± 16.59	60.75% ± 17.39
	Parap. 59.82% ± 15.53 59.48% ± 14.02	61.70% ± 14.09* 62.01% ± 14.37* 61.16% ± 14.41*

We usedMALLET (McCallum, 2002) for the LR classifier with L1 Regularisation.

2. TF*IDF = Term Frequency*Inverse Document Frequency

http://www.ims.uni-stuttgart.de/projekte/ corplex/TreeTagger/

Acknowledgments

This work was partially supported by the EU funded Eurostar EmoSpeech project. We thank Google for giving us access to the University Research Program of Google Translate.