3.1 Constraint handling in user queries to database

A query is composed of a (non-empty) set of constraints. This set needs to contain at least the category of the objects sought, for example restaurants (hasCategory=restaurant) or MP3 songs (hasCategory=MP3). Effectively, this allows us to identify the database table relevant to the query. The type is usually explicitly given by the user in the form of a base noun (‘restaurant’, ‘song’) but may also be apparent from the dialogue/application context. The ‘lifecyle’ of a constraint in the dialogue is determined by three phases:

1. 1. Introduction

2. 2. Generalization (relaxation) and specialization (constraining)

3. 3. Removal

Generalization and specialization may be performed repeatedly, or not at all. Every constraint consists of a name and value, e.g., hasDressCode=casual. The nature of the value determines how a constraint is organized in a specific ‘shape’:

1. 1. hierarchical: for example, hasCuisineType=Italian or French or Thai or Korean, . . ., where Thai and Korean are subtypes of Asian, and Italian and French are subtypes of European. Similarly, the music domain distinguishes Classic and Popular at the top level; popular music specializes into Rock, 80sPop, etc.

2. 2. linear-ordinal: for example, hasPriceLevel=cheap (USD 0–9) or moderate (USD 10–19) or expensive (USD 20–29)

3. 3. binary: for example, acceptsCreditcards=true or false

The shape of a constraint determines how constraint relaxation and specialization are performed; other shapes of constraint organization are possible in principle. Constraint operations can be described w.r.t. the underlying model (the database, in practice). This model contains ground and, in case of hierarchical constraints, most specific values for the various constraints of each data point.

Consider, for example, a query for a mid-range Italian restaurant. Figure 2(a) shows the required values that a suitable restaurant needs to ‘match’. If the original query does not return any result, the query may be relaxed to any Mediterranean restaurant in the medium to moderately high price range (Figure 2b). The interpretation of ‘matching’ is as a disjunction since any given restaurant has only one specific value in each category. In the example at hand, ‘any Mediterranean restaurant’ can be interpreted as hasCuisineType=Italian ∨ hasCuisineType=French. Since nothing is said about acceptance of credit cards, both values are acceptable in both queries. Generally, if a constraint that yields an empty result set is relaxed so that any of the values is permitted, this has the same effect as removing the constraint altogether. For example, in the binary case this results in a disjunct such as true ∨ false.

Fig. 2.

Example of constraint relaxation in query in terms of underlying model.

Constraint specialization can similarly be characterized with respect to the model, namely as a reduction in the number of disjuncts. We note that the characterization of constraint operations with respect to a model is independent of particular implementation choices such as mapping constraints to SQL queries. For example, checks for non-empty bit vector intersection could be used to match queries against data items. A simple optimization that is available in both these cases is to remove checks for constraints for which all values are acceptable.

3.2 Implementation specifics

Our general goal is a configurable, standards-based framework for managing knowledge sources in dialogue systems. Domain knowledge is structured according to domain-dependent ontologies. The knowledge manager makes use of OWL, a W3C standard, to represent the ontological relationships between domain entities. In example (1b), restaurant refers to a class of domain entities. PriceLevel, Cuisine and Reservations are properties of the restaurant class. japanese is a subclass of restaurant. The actual restaurant entries in the database inherit properties from all their superclasses. Protégé (Gennari et al. Reference Gennari, Musen, Fergerson, Grosso, Crubézy, Eriksson, Noy and Tu2002), a domain-independent ontology tool, is used to maintain the ontology offline.

In addition to the KM module, we employ a content optimization (CO) module that acts as an intermediary between dialogue and knowledge management during the query process. It receives query constraints from the dialogue manager, modifies them if necessary and queries the knowledge manager. The decision about constraint modifications is based on the number of items in the query result set and a number of configurable properties, in particular the domain-dependent relaxation strategy (e.g., restaurant.relaxationStrategy.cuisine = strategies.OntologyStrategy), thresholds for different DB result set sizes (see also Section 4.2) and the default feature/constraint order, to be used in lieu of a user-tailored feature order in selecting constraints to modify. Relaxing a hierarchical constraint entails replacing it with its parent-concept in the domain ontology. A linear constraint is relaxed by replacing the current value with an adjacent value, and a binary constraint is relaxed by replacing its value with the opposite value.

When the content optimizer obtains a semantic frame from the dialogue manager, it performs the following operations:

1. 1. Resolve ambiguous property names

2. 2. Merge with previous frame, if this is a query revision

3. 3. Send query to KM

4. 4. Select top-level strategy (e.g., processEmpty, processMedium, processLarge, none) based on number of items returned

5. 5. If top-level strategy=none, return query result

6. 6. Else: select constraint to modify, select specific modification strategy, perform modification and return to step 3.

The merging of frames (step 2) refers to user dialogue turns that modify a previous query, for example by adding or ‘overwriting’ a constraint, rather than beginning a new query. In our system, user utterances are usually interpreted as revisions, unless the user explicitly issues a new query. For example, if the user's follow-up turn to (1a) is ‘How about a Thai restaurant?’, this changes the value of constraint restaurant:Cuisine from restaurant:japanese to restaurant:thai but keeps the other constraints rather than ‘forgetting’ them. The distinction between revision moves and new queries is made by the dialogue manager. However, we do not address the general issue of dialogue move recognition in this paper. More details can be found in (Purver et al. Reference Purver, Ratiu and Cavedon2006).

The content optimizer also calculates statistics for every set of items returned by the knowledge manager in response to a user's query. If the result set is large, these figures can be used by the dialogue manager to give meaningful summary responses (e.g., in the MP3 domain, ‘There are 85 songs. Do you want to list them by a genre such as Rock, Pop or Soul?’). However, the ultimate goal of our dialogue strategies is to arrive at a single item.

The content optimizer also produces constraints that represent meta-knowledge about the ontology:

1. (2)

This constraint is produced for a user input ‘What cuisines are there?’ and allows the system to list meta-knowledge in ways similar to object-level knowledge.

4.1 General dialogue considerations

Quite separate from the general characterization of constraint handling (Section 3.1) is its application during dialogue: the system relaxes constraints automatically, but does not introduce new ones or specialize existing ones unless explicitly triggered by user input. This is motivated by the desire to reduce the burden on the user: without automatic constraint relaxation, the system can only report an empty result set (and make a suggestion; see below). On the other hand, automatically specializing constraints (a) seems risky since it may result in costly correction turns by the user and (b) violates the general HCI guideline to let the user be in control of the interaction. The dialogue strategies are currently manually defined.

Suggestions in our implementation are restricted to new constraints. The system does not make suggestions for constraint value specializations, e.g., ‘You could look for a Italian or French restaurant’, if the user was originally looking for Mediterranean cuisine. However, the user can always state a more specialized constraint explicitly, which ‘overrides’ the previous constraint value. Furthermore, explicit removal of constraints is currently not supported (‘Forget about cuisine type. I'm hungry!’). However, the user can always explicitly start a new query.

4.2 Presenting query results

Verbalizing the constraints used in a query is crucial for robustness and usability. It provides feedback to the user about what the system understood and what actions it performed (for example, constraint relaxations). This is important since the system may miss or misinterpret constraints, leading to uncertainty on the user's side about what constraints were used. For this reason, a generic system response such as ‘I found 9 items’ is not sufficient.

In addition to specifying the understood query constraints, the system needs to present the results of the query. Consider the following interaction that follows user turn (1a) (which is shown again below):

1. (3)

While the example query has a relatively small result set which can be listed directly, this is not always the case, and we thus need dialogue strategies that deal with different result set sizes. For example, it does not seem sensible to produce ‘I found 2,500 restaurants. Here are the first few: . . .’. At what point does it become unhelpful to list items? We do not have a final answer to this question – however, it is instructive that the (human) wizard in our data collection experiments (Cheng et al. Reference Cheng, Bratt, Mishra, Shriberg, Upson, Chen, Weng, Peters, Cavedon and Niekrasz2004) did not start listing when the result set was larger than about ten items. In the implemented system, we define dialogue strategies that are activated at adjustable thresholds.

Even if the result set is large and the system does not list any result items, the user may still want to see some example items returned for the query. This observation is based on comments by subjects in pilot experiments that in some cases it was difficult to obtain any query result at all. For example, speech recognition errors may make it difficult to build up a sufficiently complex query. In response to this, we always give some example items even if the result set is large. (An alternative would be to start listing items after a certain number of dialogue turns.) Furthermore, the system should encourage the user to refine the query by suggesting constraints that have not been used yet. This is done by maintaining a list of unused constraints that gets smaller as the dialogue progresses. This list is roughly ordered according to the frequency of constraint use. For example, using cuisine type is suggested before proposing to ask for information about reservations or credit cards.

Table 1 summarizes the main dialogue strategies for presenting the results of database queries. The strategies are conditioned on the size of the final result set and whether or not any modifications were performed. The dialogue strategies represent implicit confirmations and are used if NLU has a high confidence in its analysis of the user utterance; see Varges and Purver (Reference Varges and Purver2006) for more details on our handling of robustness issues.

Table 1.

Dialogue strategies for dealing with query results

For empty result sets, the system states that it has not found any matching items (Table 1, s1a,b). Small result sets up to a threshold t ₁ are listed in a single sentence (s2a,b). For medium-sized result sets up to a threshold t ₂, the system starts listing immediately (s3a,b). For large result sets, the generator shows example items and makes suggestions as to what constraint the user may use next (s4a,b). If the CO module performs any constraint modification, the first sentence of the system turns reflects the modification (s1b,s2b,s3b,s4b). ‘NP-original’ and ‘NP-optimized’ in Table 1 are used for brevity and are explained in the next section.

5.1 Generation of candidate system turns

The core of the base generator is a set of productions. Productions are ‘if-then’ rules that operate over a shared knowledge base of facts. Productions map individual database constraints to phrases such as ‘open for lunch’, ‘within 3 miles’ or ‘a formal dress code’, and recursively combine them into NPs. This includes the use of coordination to produce ‘restaurants with a 5-star rating and a formal dress code’, for example. NP generation for query constraints can be seen as a form of referring expression generation (see Dale and Reiter Reference Dale and Reiter1995, for example). In contrast to Varges (Reference Varges2004), the phrases produced by the chart generator are not directly associated with their extension (the set of objects they denote) since these are held in the database backend rather than in-memory.

The decision of the CO module to relax or remove constraints also affects the generator: there are two sets of constraints, an ‘original’ one directly constructed from the user utterance and optionally an ‘optimized’ one produced by the CO module to modify the original constraints (Section 3).

The NPs are integrated into sentence templates that realize dialogue moves. For example, original and relaxed NPs are used to describe a constraint modification: ‘I found no [NP-original] but there are [NUM] [NP-optimized] in my database’. Several dialogue moves can can be combined to form a candidate system turn. For example, the constraint realizing sentence above can be combined with a follow-up sentence such as ‘You could try to look for [NP-constraint-suggestion]’.

The selection of sentence templates is determined by the dialogue move scripts. Typically, a move-realizing production produces several alternative sentences. The NP generation rules realize constraints regardless of the specific dialogue move at hand. This allows us to also use them for clarification questions based on constraints constructed from classifier information if the parser and associated parse-matching patterns fail; all that is required is a new sentence template, for example ‘Are you looking for [NP]?’.

We use 283 productions overall in the restaurant, MP3 and navigation domains, 73 of them to generate NPs and VPs that realize 41 possible input constraints (for all domains). Other productions serve to integrate phrases into sentence templates and also perform tasks such as lexical lookup and consistency checking of the NLG input for robustness.

5.2 Ranking

Ranking of candidate system turns is done by using a combination of factors:

1. 1. Alignment: Alignment is a key to successful natural language dialogue (Brockmann et al. Reference Brockmann, Isard, Oberlander and White2005). We perform alignment of system utterances with user utterances by computing an ngram-based overlap score. For example, a user utterance ‘I want to find a Chinese restaurant’ is presented by the bag-of-words {‘I’, ‘want’, ‘to’, ‘find’. . .} and the bag-of-bigrams {‘I want’, ‘want to’, ‘to find’. . .}. We compute the overlap with candidate system utterances represented in the same way and combine the unigram and bigram match scores. Words are lemmatized and proper nouns of example items removed from the utterances.

2. 2. Variation: We use a variation score to ‘cycle’ over sentence-level paraphrases. Alternative candidates for realizing a certain input move are given a unique alternation number in increasing order. The actual alternation score is inversely related to recency and normalized to [0. . .1].

3. 3. Ngram filtering: We use an ngram filter based on ngrams extracted from ‘bad’ examples, removing, for example, ‘Chinese cheap restaurants’ but keeping ‘cheap Chinese restaurant’. For generalization, we replace constraint realizations with semantic tags derived from the constraint names (except for the head noun), for example the trigram ‘CUISINE PRICE restaurants’. An alternative is to use a more complex grammar formalism to prevent ungrammatical candidate system utterances.

4. 4. Score combination: The final candidate score is a linear combination of alignment and variation scores:

   1. (1)

   2. (2)

   where λ₁, λ₂ ∈ {0,. . ., 1}. A high value of λ₁ places more emphasis on alignment, a low value yields candidates that are more different from previously chosen ones. In our experience, alignment should be given a higher weight than variation, and, within alignment, bigrams should be weighted higher than unigrams, i.e., λ₁ > 0.5 and λ₂ < 0.5. (Deriving weights empirically from corpus data is an avenue for future research.)

A major benefit of using an overgeneration-and-ranking approach to NLG in dialogue is the possibility of performing alignment with the user utterance. This is possible even in situations where no corpus data is available. (However, we do have wizard-of-oz data to inform the system design; see Section 7.2.)

Alignment allows us to prefer ‘restaurants that serve Chinese food’ over ‘Chinese restaurants’ if the user used a wording more similar to the first. The Gricean Maxim of Brevity, applied to NLG in Dale and Reiter (Reference Dale and Reiter1995) suggests a preference for the second, shorter realization. However, if the user thought it necessary to use ‘serves’, maybe to correct an earlier mislabeling by the classifier/parse-matching patterns, then the system should make it clear that it understood the user correctly by using those same words. On the other hand, a general preference for brevity is desirable in spoken dialogue systems: users are generally not willing to listen to lengthy synthesized speech.

Mild overgeneration combined with alignment also allows us to map the constraint PriceLevel=0-10 in example (1b) above to both ‘cheap’ and ‘inexpensive’, and use alignment to ‘play back’ the original word choice to the user.

6.1 General evaluation on restaurant selection

In the general evaluation, twenty subjects were recruited for the experiment. Each subject in the restaurant selection task was given nine scenario descriptions involving three constraints. Subjects were instructed to use their own words to find a fitting restaurant. The following is an example task:

A particular challenge is to induce the subjects to use their own language but on the other hand not be too imprecise – however, this is not the focus of this paper.

We use a backend database of 2,500 restaurants containing the following information for each restaurant: restaurant name, cuisine type, city and street names, service level, rating, whether they accept credit cards or reservations, price level, open hours, dress code, additional information (e.g., vegetarian food) and distance from current location. Some of these constraints have a fixed number of values (e.g., service level and dress code), whereas those taking named entities as values are obviously open-ended. Recall from Section 3 that the constraints are organized in different ways (hierarchically, linearly, binary) to trigger different constraint handling rules in the CO module.

Figures 3 and 4 show extracts of two of the dialogues from the experiments. To exemplify the challenges the system is faced with, user turns are shown in the form of the output of the speech recognizer (we currently use the best ASR hypothesis as input to the parser). The task of the first dialogue (Figure 3) was to find a restaurant that has the following constraints: [Reservations=yes, ServiceLevel=excellent, Rating=5star]. Despite some minor speech recognition errors, the system correctly builds a query for the two constraints provided by the user in (1.1) and verbalizes these in (1.2) to show its understanding of the user input. It also gives some example items and makes a suggestion. This suggestion is not taken up by the user – in fact, we find that suggestions are generally not taken up by the user. % We explain this by the fact that the tasks determine what queries the % subjects pose. We believe this is due to the nature of the tasks, which specified exactly which criteria to match. On the other hand, in more open application scenarios, where users may not know what questions can be asked, suggestions may be useful. In (1.3) the user issues a subquery that further constrains the result set. By again summarizing the constraints used, the system confirms in (1.4) that it has interpreted the new constraint as a revision of the previous query. The alternative is for the system to initiate a new query, which would be wrong in this context.

Fig. 3.

Example dialogue 1 from evaluation (extract; ASR output for user turns).

Fig. 4.

Example dialogue 2 from evaluation (extract; ASR output for user turns).

The task of the second dialogue (Figure 4) was to find a restaurant that meets the constraints [BusinessHours=breakfast, StreetName=‘bower street’, DressCode=casual]. This user tends to give shorter, keyword-style input to the system (2.1, 2.8). In (2.3), the user reacts to a clarification question and adds another constraint which the system summarizes in (2.4). The user turn (2.5) is an ASR error which the system cannot handle (2.6, 2.7). The user constraint of (2.8) is correctly used to revise the query (2.9), but the system/ASR misrecognizes ‘yes’ as ‘british’ (2.10). This additional constraint yields an empty result set from which the system recovers automatically by relaxing the hierarchically organized cuisine constraint to ‘European food’. In (2.11) the system uses dialogue strategy s3b for medium-sized result sets with constraint modifications (Table 1). The result of both dialogues is that all task constraints are met.

In this experiment with twenty subjects, two of them were restarted in the middle. Overall, 180 tasks were performed involving 1,144 user turns and 1,818 system turns. Two factors contributing to the higher number of system turns are (a) some system turns are counted as two turns, such as 2.6, 2.7 in Figure 4, and (b) restaurants in longer enumerations of result items are counted as individual turns. On average, user utterances are significantly shorter than system utterances (x=4.9 words, standard deviation σ=3.82 versus x=15.4 words, σ=13.53). This is a result of the ‘constraint summaries’ produced by the generator. The high standard deviation of the system utterances can be explained by the above-mentioned listing of individual result items (e.g., utterance (2.12) in Figure 4).

We collected usage frequencies for the dialogue strategies presented in Section 4.2: there was no occurrence of empty final result sets (strategy s1a/b) because the system successfully relaxed constraints if it initially obtained no results. Strategy s2a (small result sets without modifications) was used for 61 inputs, i.e., constraint sets constructed from user utterances. Strategy s3a/b (medium-sized result sets) was used for 217 times and required constraint relaxations in five cases. Strategy s4a/b (large result sets) was used for 316 inputs and required constraint relaxations in sixteen cases. Thus, the system performed constraint modifications in twenty-one cases overall. All of these yielded non-empty final result sets. For 573 inputs, no modification was required. There were no empty final result sets despite modifications. The 550 user turns that did not involve any constraints comprised utterances such as ‘yes’, ‘tell me more’ or restaurant names, for example.

On average, the generator produced 16 candidate system turns for inputs of two constraints, 160 candidates for typical inputs of three constraints and 320 candidates for four constraints. Such numbers can easily be handled by simply enumerating candidates and selecting the ‘best’ one. One could handle much larger numbers of generation candidates either by using packing (Langkilde Reference Langkilde2000) or by interleaving rule-based generation with corpus-based pruning (Varges and Mellish Reference Varges and Mellish2001) if complexity should become an issue when doing overgeneration.

Task completion in the experiments was high: the subjects met all target constraints in 170 out of 180 tasks, i.e., completion rate was 94.44 per cent. An error analysis revealed that the reasons for only partially meeting the task constraints were varied. For example, in one case a rating constraint (‘five stars’) was interpreted as a service constraint by the system, which led to an empty result set. The system recovered from this error by means of constraint relaxation but the user seems to have been left with the impression that there are no restaurants of the desired kind with a five star rating.

After the experimental study, the subjects were given a questionnaire. To the question ‘The responses of the system were appropriate, helpful, and clear’ (where, in line with Walker et al. (Reference Walker, Whittaker, Stent, Maloor, Moore, Johnston and Vasireddy2004), 1 = ‘strongly agree’, 5 = ‘strongly disagree’), the subjects gave the following ratings: 1: 7, 2: 9, 3: 2, 4: 2 and 5: 0, i.e., the mean user rating is 1.95. The subjects were somewhat more critical of the quality of the speech feedback (x=2.41, σ=1.18) and most critical of the ‘pace of interaction’ (x=3.14, σ=1.08; all responses were on a scale of 1–5).

6.2 Evaluating the use of suggestions

We ran an experiment comparing two response strategies that varied in the suggestions given to the user. One strategy made use of the CO module and gave suggestions about how to proceed when a user query returned no results or many results (for this experiment ‘many’ means ‘greater than 30’). The second strategy gave responses without such suggestions. Example responses are shown below. Aside from the times a user query returned many results or no results, the two response strategies were identical.

Suggestions strategy (S):

1. a. Many matches: ‘I found 656 cheap restaurants. You can refine your query by adding criteria such as cuisine type’.

2. b. No matches: ‘I found no restaurants in Jackson that serve Indonesian food. However, there are 25 restaurants in Jackson that serve Southeast Asian food’.

No Suggestions strategy (NS):

1. a. Many matches: ‘I found 656 cheap restaurants’.

2. b. No matches: ‘I found no restaurants in Jackson that serve Indonesian food’.

6.2.1 Experimental design

Participants were sixteen native English speakers, ranging between 19 and 65 years of age. The experimental procedure included three warm-up tasks followed by six evaluation tasks. For each task, participants read a short scenario description containing three criteria, and were instructed to use their own language to talk to the system and find a restaurant. The six evaluation tasks were designed so that a query containing the three criteria would return (a) few matching restaurants, (b) no matching restaurants or (c) many matching restaurants.

Each participant was randomly assigned to Group A or Group B. Group A received suggestions (S) for tasks 1–3 and no suggestions (NS) for tasks 4–6. To counterbalance, Group B received suggestions (S) for tasks 4–6 and no suggestions (NS) for tasks 1–3. The experiment design is summarized in Table 2.

Table 2.

Experiment design

We predicted that users would prefer strategy S over NS in the tasks with no matches and many matching restaurants, and that there would be no difference in preferences for the tasks with few matching restaurants.

To ensure that task pairs (1, 4), (2, 5) and (3, 6) would be comparable, each pair contained the same three criteria (e.g., cuisine type, location and rating) but differed in the values.

6.2.2 Results

Data was collected for a total of ninety-six dialogues. User satisfaction was gauged by asking users to indicate on a 5-point Likert scale their agreement or disagreement with the following statement: ‘The system utterances in this task were easy to understand and provided exactly the information I was interested in when choosing a restaurant’, where 1 = strongly disagree and 5 = strongly agree.

The user satisfaction results indicate that responses with suggestions are preferred over responses with no suggestions for queries with no matches and many matches, in line with our predictions. Mean user ratings are summarized in Table 3. Paired sample t-tests were performed for each task category. The difference in means was not significant for the few matches and no match categories, but differences were significant (indicated with an ‘*’) for the many matches category (p < 0.1). Contrary to our prediction that S and NS would be equally preferred for the few matches category, NS responses were rated slightly higher.

Table 3.

Mean user satisfaction ratings

We ran an ANOVA to determine whether any of the user satisfaction ratings differed as a function of subject group, and found that this was not the case (i.e., the order in which users saw the two response strategies did not affect their ratings).

Within the ‘many matches’ category, we looked at means for individual tasks. The mean user ratings are shown in Table 4. Interestingly, S was rated significantly higher than NS for task 3 (p < 0.1), but for task 6, there was no difference.

Table 4.

Mean ratings for ‘many matches’ category

We also measured whether response strategies had any effect on dialogue length (number of turns). Across all ninety-six dialogues, the mean number of turns per dialogue was 14.37 for S and 16.69 for NS. For S dialogues, mean user turns was 5.29 and mean system turns was 9.08; for NS dialogues, mean user turns was 6.48 and mean system turns was 10.21. These results are shown in Table 5. A paired sample t-test was run on each of the S–NS pairs. The difference in means for user turns per dialogue was significant (p < 0.01) (marked with an ‘*’) while the differences among the system turns and the total turns were not significant.

Table 5.

Mean number of turns per task

8.1 Information presentation in spoken dialogue systems

Qu and Green (Reference Qu and Green2002) present a constraint-based approach to cooperative information dialogue that identifies candidates for constraint relaxation in overconstrained queries and restriction candidates in underconstrained ones. In contrast to our approach, constraint relaxation is not done automatically but instead suggested (in textual form).

Demberg and Moore (Reference Demberg and Moore2006) describe an approach to structuring complex options in the air travel domain by means of content clustering (see also Pellom, Ward and Pradhan Reference Pellom, Ward and Pradhan2000) in combination with a user model. These techniques could be incorporated into our system to generate more sophisticated summaries of large result sets. However, the length of the summaries may be an issue that needs to be investigated using a spoken dialogue system. Kruijff-Korbayova, Karagjosova and Larsson (Reference Kruijff-Korbayova, Karagjosova and Larsson2002) propose to use conditional responses that could be used to present complex options.

Chung (Reference Chung2004) focuses on the use of simulation techniques for rapid application development. Dialogue management is concerned with relaxation strategies in overconstrained queries, e.g., relaxing a geographical constraint according to a geography ontology. These strategies are also available to our system (in manually specified form). Rieser and Lemon (Reference Rieser and Lemon2007) show how information presentation can be automatically adapted to, for example, different levels of noise and screen sizes, by using reinforcement learning and user simulation.

8.2 Question answering

Work on question answering in the 1970s and 1980s focused on natural language interfaces to databases, for example the LUNAR (Woods, Kaplan and Nash-Webber Reference Woods, Kaplan and Nash-Webber1972) and COOP (Kaplan Reference Kaplan, Brady and Berwick1983) systems. Kaplan describes ‘suggestive indirect responses’ that also relax query constraints to present the user with a non-empty result set. In contrast to our approach, the structure of the ontology is not used to determine the constraint relaxation strategy. On the other hand, Kaplan's ‘corrective indirect responses’ (based on the detection of presupposition failure) go beyond the capabilities of the CHAT system.

Frank et al. (Reference Frank, Krieger, Xu, Uszkoreit, Crysmann, Jörg and Schäfer2005) describe a recent system in this tradition that uses deep linguistic analysis of the question to access structured knowledge sources in restricted domains. Our approach can be seen as complementary to this line of work: we provide query refinement in dialogue and answer presentation in the speech modality that could be used in combination with more sophisticated QA backends. However, more research is needed on how to interface these components, especially if the QA system is operating in open domains.

Kruschwitz and Al-Bakour (Reference Kruschwitz and Al-Bakour2005) describe a web-search interface that suggests query refinements and relaxations. It uses a domain model constructed from a text collection to, for example, back-off to a root node in the concept hierarchy. This seems similar to our relaxation of hierarchically organized constraints (although we do not back-off to the root node directly). Relaxations are suggested whenever no refinements are available, i.e., the actual size of the result set matters less than in our system. Furthermore, suggestions for query refinements are based on concrete terms (say, ‘Iraq’), whereas we suggest the use of a concept (‘search by country’).