This is how HG works for the example sentence. Refer to Figure 16 for references to variable and function names. The first Subgraph input to PROCESS-SUBGRAPH is
((adquirir grupo-roche dr-andrew)NIL
(adquirir))
That is, the In-Vertices are (adquirir grupo-roche dr-andrew), there are no In-Subgraphs, and the list of Constrained-Vertices is (adquirir). The COMBINE-INPUTS function has no input subgraphs to combine, so it simply creates an exhaustive list of possible combinations of the In-Vertices:
((<A,acq>,<G,org>,<D,hum>) (<A,acq>,<G,org>,<D,org>) (<A,learn>,<G,org>,<D,hum>) (<A,learn>,<G,org>,<D,org>))
We will refer in what follows to any possible combination of values as
a plan. For each plan, all of the constraints relevant to it are
extracted and evaluated. For instance, in Figure 33,
we can see there is a constraint between adquirir and
Dr-Andreu. When the assignments <A,acq> (the ACQUIRE meaning of
adquirir) and <D,hum> (the HUMAN meaning of Dr-Andreu) are
made, the score is 0.4. Again, this reflects the fact that HUMANs are
not usually the THEME of ACQUIRE events. Each of the scores for each
plan are combined
with the results shown below:
(<A,acq>,<G,org>,<D,hum>) [0.9 * 0.4 * 1.0 = 0.36] (<A,acq>,<G,org>,<D,org>) [0.9 * 1.0 * 1.0 = 0.9] (<A,learn>,<G,org>,<D,hum>) [0.8 * 0.2 * 1.0 = 0.16] (<A,learn>,<G,org>,<D,org>) [0.8 * 0.2 * 1.0 = 0.16]
Arc consistency functions are run at this point. For semantic analysis, however, constraints give rise to scores between 0 and 1. These ``fuzzy'' constraint values cannot be used by traditional arc consistency routines; however, a threshold could be set to some reasonable value (possibly 0.5), below which a constraint score is considered a definite violation. Arc consistency routines could then be used to propagate these failures. For this example we will assume that arc consistency is not used.
Because adquirir is the only Constrained-Vertices, only combinations of value assignments involving it will be returned by REDUCE-COMBOS. Only two such possible assignments exist: <A,acq> and <A,learn>. The plan (<A,acq>,<G,org>,<D,org>) maximizes <A,acq> with a score of 0.9. The two possible plans for <A,learn> have identical scores. Both could be kept; the algorithm above simply chooses the first. Therefore, the list of Output-Plans for the first subgraph is:
((<A,acq>,<G,org>,<D,org>) (<A,learn>,<G,org>,<D,hum>))
The other plans are discarded. It must be stressed here that discarding the other plans in no way incurs risk of finding sub-optimal solutions. The only variable that could be effected further outside this subgraph is adquirir, so plans that maximize each of its possible assignments were chosen. Nothing can happen later on to cause, for instance, the (<A,acq>,<G,org>,<D,hum>) plan to become better than the (<A,acq>,<G,org>,<D,org>) plan, since all interactions involving G and D have been accounted for.
The other subgraphs proceed along the same lines. The (adquirir a-traves-de compania) subgraph produces the following list of Output-Combos (in this case, adquirir and compania are both effected outside the subgraph, so we need to find optimal plans for all combinations of their possible values):
((<A,acq>,<ATD,instr>,<C,corp>) (<A,acq>,<ATD,instr>,<C,soc-ev>) (<A,learn>,<ATD,instr>,<C,corp>) (<A,learn>,<ATD,instr>,<C,soc-ev>))
The (en compania espana) subgraph produces:
((<E,loc>,<C,corp>,ESP,nat>) (<E,loc>,<C,soc-ev>,ESP,nat>))
It becomes more interesting when smaller subgraphs are synthesized into larger ones. For the following subgraph:
((su) ((adquirir a-traves-de compania) (en compania espana)) (adquirir))
there are two In-Subgraphs, (adquirir a-traves-de compania) and (en compania espana), and one In-Vertices, su. COMBINE-INPUTS synthesizes compatible plans for the smaller subgraphs into larger subgraphs. Recall that the Output-Combos for the two subgraphs were:
((<A,acq>,<ATD,instr>,<C,corp>) and ((<E,loc>,<C,corp>,<ESP,nat>) (<A,acq>,<ATD,instr>,<C,soc-ev>) (<E,loc>,<C,soc-ev>,<ESP,nat>)) (<A,learn>,<ATD,instr>,<C,corp>) (<A,learn>,<ATD,instr>,<C,soc-ev>))
``Compatible'' plans are then synthesized. ``Compatible'' plans include all those for which like-variables have the same assignment. For instance, (<A,acq>,<ATD,instr>,<C,corp>) and (<E,loc>,<C,soc-ev>,<ESP,nat>) are not compatible because a different value is assigned for C. The result is showed below:
((<A,acq>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>) (<A,acq>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>) (<A,learn>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>) (<A,learn>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>))
Each of these combinations is then combined with the single In-Vertices. This will, in effect, add the assignment <S,own> onto each of the combinations:
((<A,acq>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>) (<A,acq>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>,<S,own>) (<A,learn>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>) (<A,learn>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>,<S,own>))
For the input subgraph (<A,acq>,<ATD,instr>,<C,corp>) only ATD was not in Constrained-Vertices, while for (<E,loc>,<C,soc-ev>,<ESP,nat>) both E and ESP were not Constrained-Vertices. In the plans input to REDUCE-COMBOS for this synthesis, those NON Constrained-Vertices are already reduced to optimal values for the plans they are in. For the output of this synthesis, only A (adquirir) is identified in the input Subgraph description as a member of Constrained-Vertices. Therefore, REDUCE-COMBOS should return only two plans, corresponding to the two possible values of A, each of which will have all the other variables optimized with respect to the value of A chosen.
REDUCE-COMBOS calculates the combined score for each of the constraints in the subgraph. In practice, a list of scores for input Subgraphs should be maintained so that each test is not repeated for each Plan. Only the constraints involving In-Vertices and constraints between input subgraphs should have to be calculated. In this case, all constraints involving S (su) need to be calculated since it was not involved in any input subgraphs. If there were any cross-constraints between subgraphs, such as between A (adquirir) and E (en), those constraints would need to be added. In summary, PROCESS-SUBGRAPH, and thus REDUCE-COMBOS, should only need to calculate constraint scores for constraint interactions new to the subgraph.
The score for the first plan is calculated as:
(<A,acq>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>) = (0.9 * 1.0 * 1.0) = 0.9
where 0.9 is the score for the (<A,acq>,<ATD,instr>,<C,corp>) subgraph (calculated above), the first 1.0 is the score for the (<C,corp>,<E,loc>,<ESP,nat>) subgraph, and the second 1.0 is the score of the constraint added by S (su).
The second input plan to REDUCE-COMBOS is (<A,acq>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>,<S,own>). The score for this plan is calculated as
(<A,acq>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>,<S,own>) = (0.27 * 1.0 * 1.0) = 0.27
where the score 0.27 is the score of the (<A,acq>,<ATD,instr>,<C,soc-ev>) subgraph, the first 1.0 is the score of the (<C,soc-ev>,<E,loc>,<ESP,nat>) subgraph, and, again, the second 1.0 is the score of the constraint added by S (su). Because this plan has the same value assignment for A as the previous plan, and it has a lower score, it is discarded.
The third input plan, (<A,learn>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>), receives a total score of 0.27.
The last input plan, (<A,learn>,<ATD,instr>,<C,soc-ev>,<E,loc>,<ESP,nat>,<S,own>), has the same value assignment for A as the third plan, and receives a total score of 0.081. It is, therefore, discarded, since it has a lower score than the previous plan with the same assignment of A.
The output of REDUCE-COMBOS, and therefore the output of PROCESS-SUBGRAPH for this subgraph, is:
((<A,acq>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>) (<A,learn>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>))
The only variable that was not explicitly maximized in these plans is adquirir. This makes sense because adquirir is the only variable that interacts outside the subgraph.
The final subgraph, the solution to the whole problem, is then synthesized from Subgraph 1 and Subgraph 4, the subgraph just created. PROCESS-SUBGRAPH, in this case, combines all the compatible plans from Subgraph 1 and Subgraph 4, then, because the arc consistency will do nothing, sends them on to REDUCE-COMBOS. Because all of the variables except adquirir were optimized for the plans they were in, only adquirir must be reduced here. This produces a single optimal plan:
(<A,acq>,<G,org>,<D,org>,<ATD,instr>,<C,corp>,<E,loc>,<ESP,nat>,<S,own>)