Figure 17: Constraint Dependencies in Sample Sentence
A more complex version of Figure 13 is repeated here as
Figure 17. In this figure, constraint ``tendencies'' are given for
each possible combination of value assignments on an arc. Each tendency is rated
on a scale of 0 to 1, with 1 being a perfect (literal) semantic match.
Some of the values assigned in Figure 17 are explained
below:
Figure 18: Constraint Circles in Sample Sentence
The key observation that enables the application of branch-and-bound to solution synthesis problems is that some variables in a synthesis group, or circle, are uneffected by variables outside the circle. For example, in Circle 1 of Figure 18, (Adquirir, Grupo-Roche, Dr-Andrew), both Grupo-Roche and Dr-Andrew are not connected (by constraints) to any other variables outside the circle. This will allow us to optimize, or reduce, Circle 1 with respect to these two variables. Branch-and-bound techniques are used in this reduction.
Implementing this type of branch-and-bound is quite simple once the apparatus created in previous sections has been produced. Recall that when creating circles, all nodes constrained outside the circle were identified. To implement SS-GATHERER with branch-and-bound, we add this list of constrained variables to the inputs. That is, SS-GATHERER will now accept as input a list of Circles. Each circle is in the form:
(List-of-Vars List-of-Sub-Circles List-of-Constrained-Vars)
Again, the list is ordered from smaller circles to larger circles.
For the example sentence, the following would be the list of input
circles:
(¯((adquirir grupo-roche dr-andrew)
NIL
(adquirir))
((adquirir a-traves-de compania)
NIL
(adquirir compania))
((en compania espana)
NIL
(compania))
((adquirir a-traves-de compania en espana su)
((adquirir a-traves-de compania) (en compania espana))
(adquirir))
((adquirir grupo-roche dr-andrew a-traves-de compania en espana su)
((adquirir grupo-roche dr-andrew)
(adquirir a-traves-de compania en espana su))
NIL)
)
In the last circle, no variables are identified in the List-of-Constrained-Vars. This last circle contains the entire problem and thus has no variables outside of it. The result of processing it will be the optimal solution for all variables. The second to last circle identifies only adquirir in the List-of-Constrained-Vars. Its solution set will contain plans for each possible value of adquirir, with each plan being optimized with respect to all its other variables.
All that is needed to upgrade SS-GATHERER as presented earlier is the addition of one procedure call (and the procedure, of course). It should be pointed out, however, that SET-UP-CONSTRAINTS must be modified somewhat. Instead of setting up the NEEDED and FAILS arrays based on yes-no constraints, these arrays must recognize constraint scores from 0 to 1. The best approach is to set a threshold below which a constraint score should be considered ``not satisfied.'' That is, line 8 in Set-Up-Constraints should be changed to something like:
IF 
> THRESH THEN
This will allow the CSP solving mechanism to eliminate combinations with low-scoring constraint scores. All other combinations will be allowed to go forward, and will be reduced by REDUCE-PLANS:
1 PR¯)CEDURE PROCESS-CIRCLE(Circle)...
18a REDUCE-PLANS(Output-Plans List-of-Constrained-Vars)
18 RETURN Output-Plans
19 PROCEDURE REDUCE-PLANS(Plans Constrained-Vars)
20 FOR each Plan in Plans
21 Effected-Assignments <-- all possible value
assignments from Plan that involve a Constrained-Var
22 IF Effected-Assignments is NIL THEN
;;This will only happen for the topmost circle
23 Effected-Assignments <-- TOP
24 This-Score <-- Get-Score(Plan)
25 Best-Score <-- Best-Score[Effected-Assignments]
26 IF ¯ (This-Score > Best-Score) THEN
27 Best-Score[Effected-Assignments] <-- This-Score
28 Best-Plan[Effected-Assignments] <-- Plan
29 RETURN the list of all Best-Plans stored in Best-Plan array
Why does this work? First of all, each previously processed circle has been reduced, so that the input Circle-Combos will only contain reduced plans. In REDUCE-PLANS, then, we want to retain all combinations of value assignments for variables that are effected outside the circle. Line 21 calculates what these effected combinations are for the input plan. The Best-Score and Best-Plan arrays are then indexed by this (consistently ordered) list of value assignment combinations. The goal is that, for each possible combination of assignments of variables effected outside the circle, find the Plan that maximizes that combination. Because all of the other, Non-Constrained-Vars, are not effected outside the circle, we can find the Plan that maximizes each of the combinations that are effected outside the circle.
This is how SS-GATHERER works for the example sentence. The first Circle input to PROCESS-CIRCLE is
((adquirir grupo-roche dr-andrew)NIL
(adquirir))
That is, the Circle Name is (adquirir grupo-roche dr-andrew),
there are no Incoming-Circles, and the List-of-Non-Constrained-Vars is
(adquirir). There will be no Circle-Combos, but
Non-Circle-Combos will be produced for each combination of value assignments
possible:
((<A,acq>,<G,org>,<D,hum>) (<A,acq>,<G,org>,<D,org>) (<A,learn>,<G,org>,<D,hum>) (<A,learn>,<G,org>,<D,org>))
Assuming that the THRESH in SET-UP-CONSTRAINTS is 0 so that all
possible combinations will be passed through to REDUCE-PLAN, this
entire list of plans will be sent to REDUCE-PLAN. Each plan will be
scored as follows (consult
Figure 18 to see where constraint scores come from):
(<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]
Because adquirir is the only Constrained-Vars, only combinations of value assignments involving it will be in Effected-Assignments. 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 circle 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 circle 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 circles proceed along the same lines. The (adquirir a-traves-de compania) circle produces the following list of Output-Plans (in this case, adquirir and compania are both effected outside the circle, so we need to find optimal plans for all combinations of their possible values):
((<A,acq>,<A-T,instr>,<C,corp>) (<A,acq>,<A-T,instr>,<C,soc-ev>) (<A,learn>,<A-T,instr>,<C,corp>) (<A,learn>,<A-T,instr>,<C,soc-ev>))
The (en compania espana) circle produces:
((<E,loc>,<C,corp>,ES,nat>) (<E,loc>,<C,soc-ev>,ES,nat>))
It becomes more interesting when smaller circles are synthesized into larger ones. For the following circle:
((adquirir a-traves-de compania en espana su) ((adquirir a-traves-de compania) (en compania espana)) (adquirir))
there are two input Circles, (adquirir a-traves-de compania) and (en compania espana), and one input Non-Circle, su. Line 9 of SS-GATHERER calculates the Non-Circle-Combos, which amounts to a single plan because su has only one word sense:
((<S,own>))
Line 10, where Combine-Circles is called, synthesizes compatible plans for the smaller circles into larger circles. Recall that the Output-Plans for the two circles were:
((<A,acq>,<A-T,instr>,<C,corp>) and ((<E,loc>,<C,corp>,<ES,nat>) (<A,acq>,<A-T,instr>,<C,soc-ev>) (<E,loc>,<C,soc-ev>,<ES,nat>)) (<A,learn>,<A-T,instr>,<C,corp>) (<A,learn>,<A-T,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>,<A-T,instr>,<C,corp>) and (<E,loc>,<C,soc-ev>,<ES,nat>) are not compatible because a different value is assigned for C. The result, Circle-Combos, is showed below:
((<A,acq>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>) (<A,acq>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>) (<A,learn>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>) (<A,learn>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>))
Each of these Circle-Combos is then combined with the single Non-Circle-Combo in the FOR loops in lines 11 and 12. This will, in effect, add the assignment <S,own> onto each of the Circle-Combos:
((<A,acq>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>) (<A,acq>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>,<S,own>) (<A,learn>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>) (<A,learn>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>,<S,own>))
Arc-Consistency is then checked in line 15, but in our case, since THRESH was set to 0, it will have no effect and all possible combinations will be sent through to REDUCE-PLANS.
The input circle (<A,acq>,<A-T,instr>,<C,corp>) only had A-T as a Non-Constraind-Var, while (<E,loc>,<C,soc-ev>,<ES,nat>) had both E and ES as Non-Constrained-Vars. In the plans input to REDUCE-PLANS for this synthesis, those NON-Constrained-Variables are already reduced to optimal values for the plans they are in. For this synthesis, only A (adquirir) is identified in the input Circle description as a Constrained-Var. Therefore, for the plan (<A,acq>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>), (<A,acq>) will all be identified as Effected-Assignments in line 21 of REDUCE-PLANS. The Get-Score procedure is then called for the plan, with the result stored in an array indexed by this Effected-Assignments.
The Get-Score procedure in line 24 calculates the combined score for each of the constraints in the circle. In practice, a list of scores for input Circles should be maintained so that each test is not repeated for each Plan. Only the constraints involving Non-Circle variables and constraints between input circles 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 circles. If there were any cross-constraints between circles, such as between A (adquirir) and E (en), those constraints would need to be added. In summary, PROCESS-CIRCLE, and thus REDUCE-PLANS, should only need to calculate constraint scores for constraint interactions new to the circle.
The score for the first plan is calculated as:
(<A,acq>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>) = (0.9 * 1.0 * 1.0) = 0.9
where 0.9 is the score for the (<A,acq>,<A-T,instr>,<C,corp>) circle (calculated above), the first 1.0 is the score for the (<C,corp>,<E,loc>,<ES,nat>) circle, and the second 1.0 is the score of the constraint added by S (su). This score is stored in the Best-Score as the high score (since it is the first) indexed on the Effected-Assignments (<A,acq>).
The second input plan to REDUCE-PLANS is (<A,acq>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>,<S,own>). This also has an Effected-Assignments = (<A,acq>).
The score for this plan is calculated as
(<A,acq>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>,<S,own>) = (0.27 * 1.0 * 1.0) = 0.27
where the score 0.27 is the score of the (<A,acq>,<A-T,instr>,<C,soc-ev>) circle, the first 1.0 is the score of the (<C,soc-ev>,<E,loc>,<ES,nat>) circle, and, again, the second 1.0 is the score of the constraint added by S (su). Because this plan has the same Effected-Assignments and it has a lower score than the previous plan, it is discarded.
The third input plan, (<A,learn>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>), has Effected-Assignments = (<A,learn>). A total score of 0.27 is calculated and stored in the Best-Score array indexed on this Effected-Assignments.
The last input plan, (<A,learn>,<A-T,instr>,<C,soc-ev>,<E,loc>,<ES,nat>,<S,own>), has the same Effected-Assignments, and receives a total score of 0.27. It is, therefore, discarded, since it has a lower score than the previous plan with the same Effected-Assignments.
The output of REDUCE-PLANS, and therefore the output of PROCESS-CIRCLE for this circle, is:
((<A,acq>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>) (<A,learn>,<A-T,instr>,<C,corp>,<E,loc>,<ES,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 circle.
The final circle, the solution to the whole problem, is then synthesized from Circle 1 and Circle 4, the circle just created. PROCESS-CIRCLE, in this case, combines all the compatible plans from Circle 1 and Circle 4, then, because the arc consistency will do nothing with THRESH set to 0, sends them on to REDUCE-CIRCLE. 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>,<A-T,instr>,<C,corp>,<E,loc>,<ES,nat>,<S,own>)
In this example, THRESH was set to 0. In effect, this by-bassed the arc consistency checking process, unless there were some specific yes-no constraints present. The whole process can be further optimized by picking a reasonable value for THRESH such as 0.5. If no solutions can be found using that THRESH, it could be lowered further.