Introduction
In the early 1990s, Natural Language Generation (NLG) faced a significant hurdle: moving beyond rigid templates to create explanations that felt logically fluid and adaptive. This paper, presented at AAAI-93, introduced a sophisticated method for organizing technical explanations by treating discourse structure as a global optimization problem. By modeling how humans draw inferences between statements, the authors developed a system capable of generating text that mirrors the pedagogical flow of instructional textbooks.
The Challenge of Coherent Explanation
When a computer generates an explanation—such as teaching an algebraic concept—the sequence of facts is as critical as the facts themselves. Traditional NLG systems of the era typically relied on two methods:
- Schemas: Pre-defined templates or scripts. While efficient, these are rigid and cannot adapt to a user's specific knowledge gaps.
- Goal-based planning: Using Rhetorical Structure Theory (RST) to build a tree of goals. Though flexible, these systems often struggle with "opportunistic" information—side notes or examples that are crucial for understanding but don't fit a strict top-down hierarchy.
The authors identified a specific gap in these approaches: the management of inferential links. These are the "Aha!" connections a reader makes when seeing an example and realizing a general rule. Existing systems lacked a mechanism to organize these "by-the-way" or "for-instance" statements into a coherent, logically sound flow.
The WISHFUL System: Discourse as Optimization
The authors’ system, WISHFUL, generates concept explanations using a multi-step optimization pipeline designed to maximize connectivity between ideas.
RD-Graph Construction
The process begins by identifying a set of "Rhetorical Devices" (RDs). These are actions such as Asserting a rule, Mentioning a term, or Instantiating an example. The system maps these actions to specific propositions to be communicated.
Constraint-Relation Graph (CRG) and Weighted Connectivity
Once the RDs are identified, WISHFUL builds a graph where nodes represent RDs and edges represent their relationships. The system distinguishes between hard constraints (e.g., a definition must precede its use) and soft relations such as CAUSE, REALIZE, ADD, and VIOLATE.
To prioritize the most logical flow, relations are assigned weights based on their inferential strength. For instance, a "CAUSE" relation is weighted more heavily than a simple "ADD." The "VIOLATE" relation is used to handle contrastive statements, such as explaining exceptions to a rule.
A* Search Optimization
To determine the final sentence order, WISHFUL treats discourse as a pathfinding problem. It employs the A* search algorithm to find a traversal through the graph that maximizes the total "connectivity" weight while respecting all hard ordering constraints. This global optimization approach ensures that the entire explanation is coherent, rather than just picking the next best sentence at each step.
Evaluation and Key Insights
The system was evaluated in two specialized domains: Algebra (14 test cases) and Zoology (7 test cases). These served as micro-worlds to test the logic of the discourse planner across different types of knowledge.
Key findings from the research include:
- Inference Soundness: The system prioritizes "sound" logical deductions and "acceptable" generalizations over superficial similarities, guiding the user toward correct conclusions.
- Handling Evocative Information: WISHFUL recognizes that introducing a new term creates a prerequisite constraint, automatically ensuring the concept is explained or "evoked" nearby in the text.
- Qualitative Success: Tutors and staff at Monash University reviewed the output, concluding that the generated text closely mirrored the layout and flow found in published instructional textbooks.
Conclusion and Future Work
By framing discourse as a global optimization problem, WISHFUL demonstrated that NLG systems could produce explanations that feel naturally constructed rather than "choppy." While the authors noted that the search space for discourse organization grows exponentially with complexity, the success of the A* approach provided a foundation for future interactive dialogue systems and multi-paragraph technical explanations.
Summary updated