TL;DR
This paper tackles the challenge of making computer systems more natural conversational partners by introducing a "dialogue moderator" for mixed-initiative program specification dialogues. The core idea is to decouple question generation from the system's reasoning process, allowing for more coherent and flexible dialogues. This approach is demonstrated in the PSI program synthesis system, showing improved user experience and system maintainability.
What Problem Does This Paper Address?
When humans specify a computer program, they often engage in a "mixed-initiative dialogue" where either participant can take the lead. This is more natural than a rigid, system-driven interaction. A key aspect of such dialogues is the ability to ask questions in a coherent order. The paper addresses the problem of how a computer system can effectively ask questions during a program specification dialogue to ensure the conversation flows logically and efficiently. Traditional approaches often tie question ordering directly to the system's internal reasoning process, making it rigid and difficult to modify. This paper proposes a solution that separates the "what to ask" (reasoning) from the "when to ask it" (dialogue moderation).
Methods
The paper introduces a "dialogue moderator" (DM) as a separate module responsible for question ordering. Instead of asking questions as they arise during the system's reasoning process, the system first generates all possible questions it can. The DM then selects the most appropriate question to ask next.
DM represents the program specification as a network of objects (algorithms and data structures) and their relationships (subpart/superpart, uses/used-by). Each object has a list of associated questions. The DM determines the next question by:
- Identifying the "present topic": This is the object currently being discussed, often assumed to be the object the system last asked about.
- Searching the network: Starting from the present topic, the DM searches the network using a set of heuristic rules. These rules guide the search along specific arcs (relationships) or focus on particular types of questions related to the current object.
- Rule-based selection: When the search encounters an object, specific rules are applied to find a relevant question. If a question is found, the search stops, and that question is asked. If the search reaches a dead end or no question is found, it backtracks and continues the search.
This approach is described as simple and flexible, allowing for easier modification of question ordering independently of the reasoning process.
Datasets
Not discussed in the paper. The work was tested using logs of existing PSI dialogues and a simulated dialogue.
Key Insights and Ideas
- Decoupling Question Generation and Ordering: The most significant insight is the benefit of separating the system's reasoning process (which generates potential questions) from the dialogue moderator's task (which orders and selects the next question). This separation leads to more flexible and maintainable dialogue systems.
- Dialogue Moderator as a Network Searcher: Representing the program specification as a network and using a rule-based search mechanism for question ordering is an elegant and effective approach.
- Program Structure as a Dialogue Guide: In the context of program specification, the structure of the program itself can serve as a sufficient model for guiding dialogue, eliminating the need for complex models of user goals and plans.
- Simplicity and Flexibility: The proposed method is highlighted for its simplicity and flexibility, making it potentially transferable to other domains where task structure can guide dialogue.
Key Results
The paper reports on two evaluation methods:
- Log Analysis: A survey of 42 complete PSI dialogues found that DM's question ordering was "correct" in all but one instance, with no user complaints about the ordering.
- Simulated Dialogue: In a simulated dialogue where the author played the role of PSI and a programmer acted as the user, DM correctly chose the next question in 13 out of 16 instances where a choice was required. The errors were attributed to limitations that could be addressed by maintaining a history of the dialogue's progression.
Limitations and Future Work
- Determining the "Present Topic": The paper acknowledges that determining the current topic of discussion is a difficult problem that was not fully addressed. The current heuristic of assuming the last-asked object is the present topic is a simplification.
- History of Dialogue: The analysis of errors in the simulated dialogue suggests that maintaining a history of how the dialogue reached its current state could improve question ordering.
- Extensions to the Method: The authors suggest that straightforward extensions, particularly those related to dialogue history, could resolve the identified errors.
The paper implies that this general scheme of rule-based search for question ordering is applicable to other domains where task structure can be tied to dialogue structure.
Summary updated