+ Disjunctive LVs

Summary: To take advantage of certain performance optimizations, you should write constraints in a particular way.

Analyzing language in WCDG amounts to solving a constraint optimization problem. The variables in the problem are taken from the cross product of analysis levels and word forms in the sentence. Each value of one of these variables is called an LV (levelvalue), for no good reason except brevity.

Each LV consists of a modifier word, a modifiee word (unless it is a NIL binding), and a label that annotates the relation between the words. When different lexical variants of the same word form are possible, individual LVs must be established for each of the variants, like this:

 
#0   der_nom(0-1)/SYN--DET-->parkplatz_nom(1-2) [1.000e+00]
#13  der_gen_sg(0-1)/SYN--DET-->fleischerei(5-6) [1.000e+00]
#14  der_dat(0-1)/SYN--DET-->fleischerei(5-6) [1.000e+00]
#12  der_nom(0-1)/SYN--DET-->fleischerei(5-6) [8.000e-02]
#3   der_gen_sg(0-1)/SYN--DET-->parkplatz_nom(1-2) [7.200e-03]
#6   der_dat(0-1)/SYN--DET-->parkplatz_nom(1-2) [7.200e-03]
#15  der_gen_pl](0-1)/SYN--DET-->fleischerei(5-6) [1.000e-01]
#9   der_gen_pl](0-1)/SYN--DET-->parkplatz_nom(1-2) [9.000e-03]
#1   der_nom(0-1)/SYN--DET-->parkplatz_acc(1-2) [9.000e-02]
#2   der_nom(0-1)/SYN--DET-->parkplatz_dat(1-2) [9.000e-02]
#8   der_dat(0-1)/SYN--DET-->parkplatz_dat(1-2) [8.000e-02]
#10  der_gen_pl](0-1)/SYN--DET-->parkplatz_acc(1-2) [9.000e-03]
#11  der_gen_pl](0-1)/SYN--DET-->parkplatz_dat(1-2) [9.000e-03]
#4   der_gen_sg(0-1)/SYN--DET-->parkplatz_acc(1-2) [7.200e-03]
#5   der_gen_sg(0-1)/SYN--DET-->parkplatz_dat(1-2) [7.200e-03]
#7   der_dat(0-1)/SYN--DET-->parkplatz_acc(1-2) [7.200e-03]

#21  der_nom(0-1)/SEM--DUMMY-->NIL [1.000e+00]
#22  der_gen_sg(0-1)/SEM--DUMMY-->NIL [1.000e+00]
#23  der_dat(0-1)/SEM--DUMMY-->NIL [1.000e+00]
#24  der_gen_pl(0-1)/SEM--DUMMY-->NIL [1.000e+00]

The advantage is that by selecting one of these LVs, the choice between homonyms is made automatically. There is no separate "resolve homonyms" step.

The first disadvantage is that not every LV can be added to or inserted into a WCDG analysis because the lexical selection might be incompatible. Elaborate machinery is in place to detect and prevent this from happening.

The other disadvantage is that the number of LVs increases combinatorially, instead of additively, with the number of homonyms. But homonyms are plentiful in natural language; German, for instance, has at least three identical forms for each verb, many pronouns that are homonymous to articles, etc. Therefore, associating LVs with individual lexical items increases the number of variables in the problem considerably. Although the same solutions are possible it takes longer to find them, simply because more alternatives must be tried.

As early as 1999, this problem was recognized and partially solved as described here.

Briefly, when several LVs can be proved to behave identically in every respect, they can be amalgamated into one disjunctive LV. In the above example, we can combine all four SEM LVs into one:

#20  der_nom/der_gen_sg/der_dat/[der_gen_pl](0-1)/SEM--DUMMY-->NIL [1.000e+00]

The decision whether or not to build a disjunctive LV depends on the exact lexical features of the homonyms in question. Assume the following constraints:

{X/SYN} : syn_subj_case : syn_subjekt :  0.05 : 
  X.label=SUBJ -> X@case=nom;

{X:SYN} : syn_sv_agr_num : syn_subjekt : 0.1 : 
  X.label=SUBJ -> X@num=X^num;

{X:SYN} : syn_sv_agr_pers : syn_subjekt : 0.07 : 
  X.label=SUBJ -> X@pers=X^pers;

{X:SEM} : sem_nil_root : sem_init : 0.0 :
   X@type=NIL -> X.label=DUMMY & root(X^id);

This means that SYN LVs only care about case, number and person, whereas SEM LVs only care about the type, and are therefore indifferent to case variants.

This principle can be refined to include the direction and label of an LV. Note that the only constraint that accesses the `person' feature in the example actually only talks about LVs with the label SUBJ, and only about LVs that modify a word to the right. If this is the only constraint of the kind in the entire grammar, we can consider the feature `person' irrelevant for all other edges. This allows us to combine LVs with different modifiees that differ only in their `person' features, like this:

#540  Brief_acc(7-8)/SYN--OBJA-->schreibt_2/schreibt_3(1-2) [1.000e+00]

To take advantage of this optimization, all feature accesses have to be guarded by restricting the type of edge that they apply to. For instance, this constraint would disable all optimization of the `person' feature:

{X} : bad_example : 0.5 : 
 X@person = X^person;

Much better is to qualify the access like this:

{X/SYN} : better_example : 0.5 : 
 X.label = SUBJ -> X@person = X^person;

The constraint analyzer that determines what features are relevant is good but not perfect. It detects access qualifications like this:

X.label = APPO -> X^case = X@case

or this:

X\ & X@cat=NN & subsumes(Labels, Nominalobjekt, X.label)
->
X^case=acc

or this:

X@from < Y^from & X^from > Y^from & Y@from > X^from
->
Y.label = OBJA &
(Y@word = als & (exists(Y^case) & Y^case = nom))

But it is fooled if you say

~(X.label = SUBJ) -> X@case = nom

or

X@case = nom <-> X.label = SUBJ

Moral: To get your LVs more compact, write the edge type test first and then access the feature. Also, avoid explicit negations, use = instead (or improve the optimizer by hacking inputCollectFeatures() ).

The paper cited above contains an evaluation of the speedup achieved by building disjunctive LVs based on relevance to a particular level. Also, Ingo Schröder's Ph.D. thesis (not online) contains a section on the topic.

An experiment on the effect of the additional compaction is online as DisjunctionExperiments.

-- KilianAFoth - 17 Jan 2003