next up previous contents
Next: Generalizing Pereira and Warren's Up: Overview of Earley Deduction Previous: Blocking new lemmas

Use of a restrictor

 

The prediction rule is used for predicting new instantiations of grammar rules using the selected element of a non-unit lemma. As known from the work of [Shieber1985] prediction can lead to arbitrary numbers of consequents through repeated application when used with a grammar with an infinite structured nonterminal domain. For example, if a grammar handles subcategorization with list value features (such as in or the rule tex2html_wrap_inline11771 of the grammar given in appendix A), then non-termination can arise since the subcategorization rule is able to produce instantiations with successively increasing lengths of subcategorization lists, which do not stand in a subsumption relation. Hence, neither of the lemmas is blocked.

The solution proposed in Shieber's work is to use only a restricted amount of information for predicting the element. Thus before the predictor is evaluated a restrictor function is applied that computes from the constraints of the selected element a bounded subset of the information of these constraints. The restrictor function serves to specify how much information is to be used in the top-down phase of a uniform algorithm. For example, if we use the identity function, all information would be predicted and if we use simply the constant function yielding the trivial model, no top-down information is used.

In Shieber's original work, a grammar-oriented version of a restriction function is presented, where only those features are predicted which have been chosen by the user as most useful for prediction. Following [Shieber1985] restriction is defined on the basis of a given restrictor R, which is a finite set of paths through a feature structure. The restriction of a feature structure F relative to R is the most specific feature structure tex2html_wrap_inline11779 , such that every path in F' has either an atomic value or is an element of R.

A more general definition of is given in [Haas1989]. In this approach, for a given set of constraints tex2html_wrap_inline10669 a restricted form tex2html_wrap_inline10763 is computed by replacing all cyclic constraints with new variables. Applying this definition to the subcategorization rule would break the cycle (caused by the variable Tail) of the subcategorization feature SC.gif

In [Shieber1989] it is shown that any function can be used, with the prerequisite that the range of the function is finite. Then termination of prediction can be guaranteed because divides an infinite number of categories into a finite number of equivalence classes. Thus, after a finite number of applications of prediction, a previously generated item would be built and the subsumption check would prune further applications [Shieber1989]. Using a restriction of a feature structure instead of the original feature structure weakens the predicting power of the top-down prediction step in the sense, that it can over predict lemmas. However, it does not affect the correctness of the algorithm, since these unnecessary prediction will never be completed.

In our system we use a restrictor function similar to that of [Shieber1985]. However, instead of specifying which constraints should be used to build a restrictor, we specify which information of a specified set of features should be ignored (i.e., set to the top variable). For the grammar in appendix A this is basically the subcategorization feature SC. Thus, before the predictor is applied, then if this feature is present its value is set to the top variable. Any other information is unchanged. In this way, we use as much top-down information as possible, however by being able to ignore ``dangerous'' features.


next up previous contents
Next: Generalizing Pereira and Warren's Up: Overview of Earley Deduction Previous: Blocking new lemmas

Guenter Neumann
Mon Oct 5 14:01:36 MET DST 1998