Query Generation for Interactive Constraint Acquisition

In many practical applications users often find it difficult to articulate their constraints. While users can recognize examples of where a constraint should be satisfied or violated, they cannot articulate the constraint itself. In these situations we would like the computer to take an active role in acquiring the user’s constraints. In this paper we present an approach to interactive constraint acquisition based on techniques from the field of machine learning. During interactive constraint acquisition we would like to employ a strategy which minimizes the dialog length between the user and the computer. In this paper, we compare a number of different heuristics for interactive query generation. We demonstrate that the interactive strategy used to acquire constraints depends on the topology of the hypothesis space and the degree to which the human user is being helpful.