Figure 20: Example Semantic Representation
Figure 20 is a representation of the semantic content of a simple natural language sentence. In English the sentence could be rendered ``Grupo Roche acquired Dr. Andreu through a subsidiary in Spain.'' The node names are semantic concepts taken from a language-independent ontology. Arc labels correspond to relations between concepts. The ontology defines for each concept the set of arcs that are allowed/expected, as well as the appropriate filler concepts. For simplicity, additional semantic information such as temporal relationships are not shown. Please consult (Beale, Nirenburg & Mahesh, 1995; Onyshkevych & Nirenburg, 1994 and Mahesh & Nirenburg, 1995) for more information about semantic representation in the Mikrokosmos system. For our purposes, the details of the semantic representation and generation lexicon entries to follow are unimportant; they serve only as simple examples of control concepts that will apply to more complex problems.
Figure 21: Lexicon Entry for acquire
Generation lexicon entries attempt to match parts of the input semantic structures and map them into target language surface structures. For instance, a lexicon entry for the concept ACQUIRE might look like Figure 21. The VARs in the entry will be bound to the corresponding semantic structures in the input, and their target realization will be planned separately and inserted into the output structure as shown. Typically, lexicon entries also contain semantic and pragmatic constraints. For instance, VAR1 might be constrained to be HUMAN. The entry could also be constrained to apply only to texts with certain stylistic characteristics. Collocational constraints are also important in generation. Any of these constraints can apply locally or can be propagated down to the VARs. The interplay of constraints is a major factor in determining the best overall plan.
Figure 22: Three entries for ACQUIRE
Figure 23: An entry for INSTRUMENT
Figure 24: Two entries for CORPORATION
Planning for Machine Translation comes in when we try to combine information in various lexicon entries to best match the input semantics with as little redundancy as possible and maximal adherence to the constraints. Figures 22, 23 and 24 represent some possible lexicon entries that might be used in planning target English sentences for the structure in Figure 20.
A typical means-end, hierarchical planner
uses the following algorithm:
PROC PLAN(SEMANTIC-CONTENT)1 Pick one PLAN that implements base
meaning in SEMANTIC-CONTENT
2 FOR each PRECONDITION in PLAN not
already satisfied
3 PLAN(PRECONDITION)
4 FOR each unrealized VAR in PLAN
5 PLAN(VAR)
6 FOR each unplanned RELATION in
SEMANTIC-CONTENT
7 PLAN(RELATION)
8 IF FAILURE THEN BACKTRACK
For example, to generate text for Figure 20, the ACQUIRE concept would be passed to PLAN. Three possible entries exist for ACQUIRE (Figure 22). The first, ACQUIRE-1, expects a semantic environment with agent and theme relations, both of which are in the input semantics. There are no preconditions in these simplified entries, so the procedure skips to line 4. There are two VARs that are not realized in the first entry. These VARs are bound to the input semantics, VAR1 to a GRUPO-ROCHE instance of an ORGANIZATION concept, VAR2 to a DR-ANDREU instance of ORGANIZATION, and PLAN is called recursively for each, leading eventually to surface strings like Grupo Roche and Dr. Andreu. There is still an unplanned relation of the input ACQUIRE node, namely the instrument link to a CORPORATION concept. This relation is therefore recursively planned in line 7. ``FAILURE'' in line 8 can refer to a number of possible outcomes, such as over-generation of semantic content or an inability to plan one of the VARs or RELATIONs. This type of planner can be made to find all possible solutions by storing successful overall plans and then backtracking.
Depending on which lexicon entries are used, plans will be more or less complex. The second entry that realizes an ACQUIRE concept, ACQUIRE-2, has a ``built-in'' instrument relation. Because of this, there will be no unplanned RELATIONs in line 6. Similarly, the second CORPORATION entry encorporates the ownership relation. The first entries for both ACQUIRE and CORPORATION need to specifically plan for those links. ACQUIRE-3 is an example of over-generation. It expects a price relation in the input semantics. This can either be made to cause FAILURE (line 8) or simply penalize any plans that utilize it.
The optimal overall plan can be determined by scoring all of the constraints
present in each of the sub-plans, adding in penalties for over-generation,
and adding in rewards for shorter plans. The best English
sentence using the entries given on the example semantic input would
combine ACQUIRE-2 and CORPORATION-2 to give something like
``Grupo Roche procured Dr. Andreu with a subsidiary in Spain.''
This would be better than
using ACQUIRE-1, which requires the extra INSTRUMENT-1
plan and CORPORATION-1, which requires an extra plan for the
ownership link. ACQUIRE-3 contains unwanted semantics (a
price relation) and would thus be penalized.
There are two problems with PLAN. First, it cannot be guaranteed to be sound. Preconditions satisfied at a higher level of processing can be undone by side effects at lower levels. This is the problem that Young and Moore tackled with DPOCL. Second, PLAN is horribly inefficient. Local solutions are planned again and again as backtracking moves up and down the input semantic tree. Preconditions and constraints must be continually rechecked because each combination of sub-plans may be different. This is the problem tackled by Tenenberg with abstractions. PICARD identifies local areas of dependency and plans them separately. It uses constraint satisfaction techniques to ensure soundness. It recasts the means-end planning paradigm into an abstract system of independent sub-plans connected by usage constraints, so that efficient solution synthesis procedures can combine them. It is this last concept that is explored in the remainder of this paper.
It must be noted that text planning for machine translation is somewhat easier than for many Natural Language text planning problems, primarily because the semantic content is given. The main goals of an MT text planner are lexical choice and word and sentence ordering. In general, communicative goals are inherent in the input semantic content, although pragmatic features must be taken into account to a greater or lesser degree. In addition, appropriate generation of discourse structure, figurative language, anaphora and ellipsis serve to complicate matters. Text planners for question-answering systems have the added complexity of starting from communicative goals. This makes for more complex planning; nevertheless, the PICARD principles to be explained below can be applied in exactly the same manner.