Catalogue of Artificial Intelligence Techniques
Aliases: Discrimination Tree
Keywords: PLANNER, directed acyclic graph, generation, learning, natural language generation
Categories: Knowledge Representation , Learning , Natural Language , Search
Author(s): Karen Sp\"arck Jones
A mechanism for allocating an input data item to its class by applying successive tests for different individual predicates; the terminal nodes of the net represent the results to be returned for the various possible sequences of predicates. A discrimination net (D-net) is thus a nest of IF...THEN...ELSE tests all applicable to one data item, or more formally, a binary, directed, acyclic graph with unary predicates at non-terminal nodes. An example of the use of a discrimination net of this basic kind is in natural language generation in choosing an output word for an input meaning representation. The basic mechanism can be extended by, for instance, using n-ary rather than binary graphs, with the corresponding replacement of simple feature tests by more complex branch selection functions, by the use of variables in the data item descriptions and net patterns, and by the use of sophisticated means of indexing. With such extensions, a net can be used, for example, to implement a PLANNER-style database optimised for retrieving individual assertions. Discrimination nets have an obvious attraction when the set of classes involved is high; but clearly a prerequisite for their effective application is being able to identify clear test sequences for data items.
- Charniak, E., Riesbeck, C.K., McDermott, D.V. and Meechan, J.R.
, Artificial Intelligence Programming, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1988 (second edition