2.1 Symbols

Terminal and nonterminal symbols of the context-free grammar are represented as instances of the JAVA class Symbol.Footnote ¹ Symbols bear a name field of type String and an annotation field of type int [] (an integer array). The name field of a terminal refers to the full surface string of this terminal word and its annotation field is empty (refers to the null value). A nonterminal also has a name and encodes the HPSG rule name (e.g., hcomp or measure_np). The annotation of a nonterminal symbol groups several type identifers which originate from (possibly deep-nested) values under pre-specified paths (the so-called annotation paths) within the instantiated rule TFS for this nonterminal symbol. Thus an annotation is quite similar to a feature specification in GPSG (Gazdar et al. Reference Gazdar, Klein, Pullum and Sag1985) or a quick-check vector (Kiefer, Krieger, Spilker and Weber 1996; Malouf, Carroll and Copestake Reference Malouf, Carroll and Copestake2000).

During the more formal parts of this article, we need two fundamental concepts: symbol and annotation.

Definition 1 (SYMBOL)

We refer to a symbol s in the abstract syntax by a pair 〈n, a〉, consisting of name n and an annotation a. We write N(s) to depict the first projection of s (the name) and A(s) to access the annotation part of s. When using concrete syntax, we write a symbol in the more GPSGish notation n [a].

Definition 2 (ANNOTATION)

An annotation a = 〈t. . ., t _n〉 is a n-tuple of type names or type IDs t _i ε , i ε{1,. . .,n}. We write π_i(a) to denote value t _i of the i-th projection of a. Using the GPSG-like concrete syntax, we write [t ₁,. . .,t _n] to depict annotation a.

Given two symbols, we define a subsumption relation ≼ which turns out to be useful in a moment.

Definition 3 (SYMBOL SUBSUMPTION)

Let s ₁ and s ₂ be two annotated context-free symbols, s ₁ is said to be subsumed by s ₂ (written as s ₁ ≼ s ₂) iff N(s ₁) = N(s ₂) N(s ₂) and π_i(A(s ₁)) ≼ π_i,((s ₂)), for all i ε {1,. . .,n}. Alternatively, we say that s ₂ subsumes (or is more general than) s ₁. Assuming that s ₁ and s ₂ are terminal symbols, their annotation must be empty (A(s ₁) = A(s ₂) = 〈 〉), thus the second condition above is trivially satisfed.Footnote ²

Let us give an example. Assume we have the four CF symbols (concrete syntax) N[sg, fem], N [pl, fem], N[num, fem], D[num, fem] and assume that sg ≼ num and pl ≼ num is the case. We can then infer that N[sg, fem] ≼ N [num, fem] and N [pl, fem] ≼ N[num, fem] holds. However, N[sg, fem] and N[pl, fem] are not related by the subsumption relation. Consequently, we say that these symbols are incomparable and use the ⋈ sign to indicate this: N[sg, fem] ⋈ N [pl, fem]. Furthermore, D [num, fem] is incomparable with every other symbol, due to its name: D ¬ N.

2.2 Rules

We represent context-free grammar rules by the class Rule whose instances have a left-hand side (lhs) and a right-hand side (rhs) field. The left-hand side is (from a CFG point of view) a nonterminal symbol, which we represent as an instance of the class Symbol. The right hand-side is an array of Symbol objects (JAVA notation: Symbol []). The length of rhs is encoded in an additional field length of type int. A Rule object also possesses a frequency field, telling us how often that rule has been applied during parsing of a given corpus. It is worth noting that the frequency counter might gain importance when we move from the extracted CFG to a PCFG which will predicts probabilities for CFG trees.

Next, we need the formal notation of a grammar rule.

Definition 4 (CONTEXT-FREE GRAMMAR RULE)

Let l, r ₁,. . .,r_n be (annotated) context-free symbols and let furthermore l be a nonterminal symbol. We then call the expression l → r ₁. . .r_n a context-free grammar rule. l is usually referred to as the left-hand side (LHS) of the rule, whereas the sequence r ₁. . .r _n is called the right-hand side (RHS). Given a CF rule α, the projection L yields the LHS of α, i.e., L(α) = l. R delivers the RHS: R(α) = r ₁. . . r_n.

Given the above apparatus, defiling a subsumption relation ≼ on rules is relatively straightforward.

Definition 5 (RULE SUBSUMPTION)

Let α = (l _α → r _1α. . .r_nα) and β = (l _β → r _1β. . .r_nβ) be two context-free grammar rules. We say that α is subsumed by β and write α ≼ β iff l _α ≼ l _β, n _α = n _β, and r_iα ≼ r _iβ; for all 1 ≤ i ≤ n _α. Alternatively, we say that β subsumes (or is more general than) α.

We say that two CF rules α and β are equivalent iff they both subsume each other: α ≡ β : ⇔ α ≼ β and β ≼ α.

Let α ⋠ β abbreviate ¬(α ≼ β). Two rules are said to be incomparable iff they are not related by rule subsumption: α ⋈ β:⇔ α ⋠ β and β ⋠ α.

An example. Given the symbols from the example at the end of subsection 2.1, we defiie a subsumption order over the following three rules (we use again the concrete syntax in which the implemented algorithm delivers the rules). Let α = (NP[sg, fem] -> N[sg, fem]), β = (NP[pl,fem] -> N[pl, fem]), and γ = (NP[num, fem] -> N[num, fem]). Then α ≼ γ and β ≼ γ, however α ⋈ β.

2.3 Edges

The edges which are transmitted by the HPSG parser in plain text (see figure 1) are reconstructed in main memory within the JAVA virtual machine. At the moment, we are using a modifcation of the freely available PET parser (Callmeier Reference Callmeier2000). The set of all passive edges for a single parsed sentence are grouped in a text file (see next section).

Edges are represented as instances of the JAVA class Edge, consisting of the instance fields id, ruleName, immDtrs, noOfDtrs, and annotation. The id of an edge is a handle to the edge object and allows other edges to refer to this edge in their immediate daughters array immDtrs. id is of type int, thus immDtrs must be of type int []. The string in the ruleName field of the edge leads to the primary category symbol of the LHS of the context-free rule later. As already described, annotations are represented as int vectors. The extraction algorithm in the next section produces for each given edge exactly one context-free rule. Due to the ruleName field, we know the name of the UBG rule from which the edge has been derived. Exactly this information is utilized during the deterministic second phase of two-stage parsing.

3.1 Interface to HPSG

The interface to HPSG is established via the creation of text files: for every input sentence of the corpus, a new file is created that contains exactly the passive edges produced by PET. Although not every deep passive edge contributes to a deep reading, we have decided to take all passive edges into account (one can think of other options as well; see section 5). Since the passive edges of the deep parser are objects in main memory and since our extraction runs in a separate thread, we have defined an ASCII-based exchange format for chart edges that is given by the EBNF in figure 1. Figure 2 then displays the stripped-down chart for the sentence Kim loves Sandy. Due to the fact that features and types are represented as integers in PET, it is important that both PET and the extraction process operate on the same (Krieger and Schafer Reference Krieger and Schafer1994) grammar.

Fig. 1.

The external exchange format of a chart as delivered by a modifbd version of the PET system. The meta characters and express optionality, | enforces the choice of exactly one alternative, and * and ⁺ refer to Kleene star and Kleene plus, resp. integer denotes the set of all integers, i.e., sequences of numeric decimal characters, string denotes the set of all strings, i.e., sequences of plain text characters, enclosed by double quotes. Note that each chart edge must be separated by the newline character <CR> at the end. At the moment, we do not benefit from the start and end position of an edge, rulename serves as the main category symbol, imdtrs refers to the immediate daughters of an edge. Since the delivered passive edges are topologically sorted, it is not necessary to reencode an edge that has already been introduced earlier. Thus the immediate daughters imdtrs of an edge are referred to by integer numbers id. The only exception are terminal symbols (the surface form) which are written as pure strings.

Fig. 2.

Parts of the chart for the sentence Kim loves Sandy. Note that the chart is topologically sorted, i.e., it is guaranteed that edge ids are introduced before they are referred to in the immediate daughters list. For instance, edge 13 refers to edge 11 (i.e., originating from a unary rule), edge 30 to edges 17 and 28 (a binary rule), etc. The edges 1–11 can be thought of as realizing the lexicon lookup. Notice that loves is assigned nine readings (different senses & morphosyntactic variations). The unary rules 12, 13, 15, 19, and 22 are morpholexical rules. The unary rule proper_np (17, 18) raises a noun to an NP. Some passive edges (40–42) result in useless CF rules for this sentence, since they represent dead branches in the search space.

Because HPSG requires all relevant information to be contained in the synsem feature of the mother structure, the unnecessary daughters (which are part of the TFS) only increase the size of the overall feature structure without constraining the search space. Due to the Locality Principle of HPSG (Pollard and Sag Reference Pollard and Sag1987), they can therefore be legally removed in fully instantiated items, i.e., passive edges which are delivered by the PET parser. To be independent from a certain grammatical theory or implementation, we use restrictors similar to Shieber (Reference Shieber1985) as a fbxible and easy-to-use specification to perform this deletion. In case we are trying to work with a larger tree context and not limiting ourselves to context-free rules (= trees of depth 1), the restrictor is the right means to accomplish this (see section 5).

3.2 Quick-check paths

Quick-check paths (QC) are used during unifbation-based parsing to quickly and correctly filter out failing unifications without applying the more costly unification operation (Kiefer et al. 1999; Malouf et al. Reference Malouf, Carroll and Copestake2000). Such a filter is extremely important since most of the unifications usually fail (95–99% of all unifications). The quick-check filter exploits the fact that unification fails more often at certain points in feature structures than at others. In order to determine the most prominent failure points, we parse a large test corpus in an offline stage (to be precise, we use a part of the corpus from which we extract the CFG), using a special unification engine that records all failures instead of exiting after the first failing unification.Footnote ³ These failure points, more exactly, the types of the feature structures at these points, constitute the quick-check (QC) vector. When executing unification during parsing, those points are efficiently accessed and checked using type unification prior to the rest of the structure. QC filtering heavily relies on type unification being very fast, which in fact is the case since it can be cached or even precompiled (Kiefer et al. Reference Kiefer, Krieger, Carroll and Malouf1999; Kiefer, Krieger and Nederhof Reference Nederhof2000). Figure 3 displays the ten most prominent failure paths for a specific corpus we have used in our experiments (cf. section 6).

Fig. 3.

The ten most prominent failure points for the English HPSG grammar (June 2002) in decreasing order.

As already said in section 2.1, the annotation of a context-free symbol bears a close resemblance to a QC vector – an annotation is a subvector of a QC vector., i.e., we might not take all vector positions into account. The reason for using (parts of) the QC vector as an annotation is due to the fact that we are interested in fast and modestly overgenerating context-free recognition grammars. Exactly the failure points in a QC vector are of this property, viz., heavily contributing to failures which rule out parts of the search space during unification-based parsing.

We note here that not every QC path has to be present in every feature structure, since only certain features are appropriate for certain TFSs. Let us give an example. Given the above set of QC paths, it turns out that the original head-complement rule hcomp is undefined for the ninth QC path. To account for this problem, we introduce a type U to express such undefnedness. U clearly only unites with the most general type T, and of course with itself. Using concrete syntax, we write *undef *. Consequently, we obtained instantiations of the binary head-complement rule schema hcomp, schema 1 in Pollard and Sag (Reference Pollard and Sag1994), such as

To circumvent such undef values, it might be a good idea to work with different annotation vectors for each primary category symbol. This means that we have to partition the set of rule names R = R ₁ U . . . R _n, such that each. R _i (1 < i < n) is associated with a set of defined quick-check paths. We have not tried this strategy yet.

3.3 Algorithm

The idea behind the context-free extraction is relatively straightforward and is given in pseudo code in Figure 4.

Fig. 4.

The overall structure of the extraction algorithm.

As we already said, the HPSG parser produces for each input sentence an output file that contains an external representation of the passive edges of the chart for this sentence, encoded in the format given by Figure 1. The extraction HPSG2CFG then works as follows. Given a directory D and a vector of quick check paths Q, we iterate over the files in D (line 3). For each file, we then construct a vector edges of internal edges (i.e., JAVA objects) for the set of external passive edges stored in this file, using makeEdges (line 4). This includes the in-memory reconstruction of the TFSs for the mother structures (the LHSs). For each vector position, i.e., for each edge e, we build up a LHS symbol (i.e., a pair, see section 2.1), consisting of a name field (via getName) and an annotation vector (via get Annotation), given the quick-check paths Q (line 7). The same is done for every RHS symbol, but since we usually have more than one RHS symbol, we collect them in a vector rhs of length equal to the number of the immediate daughters dtrs of the passive chart edge (lines 8–13). For every passive edge, we finally generate a context-free rule object (see section 2.2), given the LHS and the RHS (line 14). The new CF rules are adjoined to the result set (line 14). After we have processed all files in directory D, the result set is returned at last (line 17).

The subscript ≡ of the union operator in line 14 of the algorithm should indicate that new rules are added to the result set using rule equivalence. That is, a new rule only contributes to the final CFG if no structural equivalent rule has already been introduced earlier during the extraction process. Even for a small corpus, a large number of structural equivalent rules are generated, resulting either from reappearing words or from reappearing linguistic constructions. The non-astonishing observation is that the smaller the annotation gets, the larger the number of equivalent rules becomes. Clearly, by taking more quick-check paths into account, we obtain more specific CF grammars, consisting of more rules. In the next subsection, we will slightly modify line 14, replacing the rule equivalence test by rule subsumption.

3.4 A variation

Rule subsumption, defined in section 2.2, now comes into play to potentially scale down generated grammars. We apply this operation online during the extraction process in that we replace line 14 of the algorithm by

The intention behind ∪_≼ is that a new rule is only added to the result set iff it is more general than at least one rule already in the set. If so, the old rule and perhaps further other rules are removed. If it is more specific, the new rule is clearly not added. The application of that operation guarantees that the rules from the result set result are pairwise incomparable, i.e.,

∪_≼ is somewhat related to the specialized union operation ∪_⊆ in Kiefer and Krieger (Reference Kiefer, Krieger, Oepen, Flickinger, Tsuji and Uszkoreit2002). Whereas ∪_⊆ operates over typed feature structures representing context-free symbols, our operation is directly applied to annotated CF rules.

Of course, ∪_≼ does change the context-free language

when compared to the language

, resulting from the application of ∪_≡:

Given the number of rules for the two grammars

and

, we have

A simple example clearly shows this. Assume that the temporary result set contains the following three CF rules

and assume that the new rule

subsumes both β₁ and β₂. ∪_≼ would thus delete β₁ and β₂ from the result set and will add β to it. Furthermore, since B ₁ and B ₂ are no longer valid (β₁ and β₂ have been deleted!), we must replace every occurrence of B ¹ and B₂ by the new nonterminal B, introduced in production β. This, however, has the effect that at least the modifed rule (α′ = A ↦. . .B . . .), derived from a, overgenerates.

Our approach keeps track of such rule deletions by implementing a symbol subsumption maintenance graph. In the above example, we establish two associations between B ₁, B ₂ and B: (B ₁ ↦ B), (B₂ ↦ B). Given the example, it is possible that the new rule β might even be deleted by a newer, more general rule B′ → . . . later. In this case, we have to further specify a new association: (B ↦ B′).

In the end, such substitution chains will be dereferenced, so that we can immediately substitute a dead RHS symbol by its correct and existing LHS counterpart. In the example, for instance, we must then know that B should not be substituted by B, but instead by B′.

We also have to make associations for the converse case - if a new special rule y is not added due to an existing more general rule l we must record this fact by creating the association (L(y) ↦ L(y′)), since L(y) might occur on the RHS of final CF rules.

We note here that the substitutions are of course not restricted to the LHS symbols only. Consider the following three toy CF rules which we might have acquired so far

and assume that the new, more general rule β′

now comes in, substituting β. The result set then changes to

Since we substitute the dead symbols at the very end of the approximation, the resulting CFG is clearly not optimal, i.e., not minimal. A proper treatment here would require that we have to update the symbol substitution graph (and potentially perform substitutions) each time a new passive edge is checked against the temporary CF rule set. Since we might process several millions of edges during the approximation of a grammar, we do not apply this technique at the moment.

At this point of our investigation, we already note here that favoring rule subsumption does not have any significant advantage over rule equivalence (about 10% less rules only), but mostly disadvantages (complex handling of dead symbols and rule frequencies, worst running time and space consumption of the approximation, overgeneration). Our measurements in section 6 show that even for the largest English HPSG and for two different huge training corpora, the number of approximated CF rules under rule equivalence can still be handled by a properly implemented CF parser (less than 60,000 rules). It is worth mentioning that the closely related subsumption operation U_⊑ in Kiefer and Krieger (Reference Kiefer, Krieger, Oepen, Flickinger, Tsuji and Uszkoreit2002) was ultimately necessary to made their purely grammar-driven approximation tractable. Kiefer and Krieger noticed that the use of equivalence had led to a massive explosion of CF rules in their setting. We were pretty sure to obtain similar results, but luckily rule equivalence gave us the best results and is nevertheless tractable.Footnote ⁴ We still hope that practical UBGs exist which will take advantage of rule subsumption. One can easily imagine a synthetic unification grammar which result in a CFG under rule subsumption that has exponentially-less rules than another CFG, obtained under equivalence from the same UBG.

3.5 Computing start productions

One point in the algorithm is still missing, viz., the generation of start productions. We have decided to employ only a single synthetic start symbol s in our grammars. This symbol has to be fresh, i.e., for all symbols 〈n, a〉 of the extracted grammar, we demand that N(s) ≠ n. In the implementation, the user must specify a nonempty list of start (or root) types, types which subsume original rule definitions, and thus subsumes potential rule instantiations. These types specify wellformedness conditions that a feature structure must satisfy to be a legal utterance (e.g., empty subcategorization list). Now let T be the set of all start types, R the set of extracted CF rules so far, and s the new top-level start symbol.

In the English ERG/LinGO HPSG grammar developed at CSLI, sentential phrases are subsumed by the type root-strict, and thus a start symbol in the extracted CFG can be determined by checking whether the name of a LHS symbol is subsumed by this start type. Non-sentential saturated phrases in ERG (e.g., PPs and NPs) are characterized by root-phr, thus if we want fnd all saturated phrases in the approximated CFG, we have to declare these two types to be start types.

3.6 Rule frequency

As we said in section 2.2, rule objects possess a frequency field which will gain importance if we are interested in a simple PCFG model which predicts probability distributions over CFG derivations. Since the counter is updated during the approximation process, we obtain a very basic and indirect disambiguation of UBGs for free, exploiting the fact, that ranked CF trees can be deterministically replayed by a deep unification parser; see Kiefer et al. (Reference Kiefer, Krieger and Prescher2002).

Exactly the frequency counter is set to 1 during the initialization of a rule object and is incremented by 1 in case a structural equivalent rule has been detected.

Concerning the frequency field f of a new rule α that has replaced more specific rules α₁. . .α_n, we have

since the more general rule now acts as a representative for the deleted specialized rules. Assuming the contrary, the frequency counters of truly general rules α_i (1 ≤ i ≤ n) are incremented by 1 when penalizing a:

Considering the unary start productions from section 3.5, the frequency counter of a start production s →l is set to the sum of the frequencies of those rules α € R, whose LHS is exactly l given the set of all CF rules R:

To obtain a proper probability distribution, we have to normalize the rule frequency counter in the standard way (Charniak Reference Charniak1993). Now let R(l) := {I → r _{i 1}. . .r _{i n} | i, n ε N} be the set of all extracted CF rules sharing the same LHS l, f(α) be the value of the frequency counter for rule α € R(l), and F(l): = Σ^{α∈ R(l)}f(α). We then compute the probability p(α) for a context-free rule α = l → r ₁. . .r _n as

which gives us

As we said above, by using the likelihood of a rule, we obtain a simple PCFG model for free. At this moment of writing, we have not tested its disambiguation capability, but it is very likely that it outperforms an oracle which randomly chooses a CF rule in case more than one rule is applicable. We want to make some further remarks here.

Firstly, such a model should usually take only complete HPSG derivations into account, i.e., only sets of deep passive edges which fully cover the input and which are true readings. But because we are very practically interested to have a robust CFG, we have decided for every passive edge of the deep parser.

Secondly, obtaining lexicalized PCFGs from the approximated CFGs is not hard, since we can easily stuff word-specific information into the context-free symbols (with the disadvantage of having more rules, of course).

Thirdly, as an extension of the last point, CFGs (and so PCFGs) in our setting can embody dependecies that go beyond the capabilities of hand-written and trained (P)CFGs, reminding us of N-gram models and extensions thereof. This is due to the fact that the deep passive edges in the unification parser capture (unbound) dependencies (SUBCAT, SLASH), so that specific instantiations of such constructions can show up in the annotated CF symbols of the rules of the approximated grammars (if this is desired).

Finally, it is clear that the above simple statistical model can be replaced by a more advanced model, using, e.g., the inside-outside algorithm for unsupervised training of PCFGs (Lari and Young Reference Lari and Young1990; Pereira and Schabes Reference Pereira and Schabes1992). Kiefer et al. (Reference Kiefer, Krieger and Prescher2002) have shown that the disambiguation quality of approximated grammars clearly benefit from such a treatment.Footnote ⁵

5.7 Elimination of useless rules

Since the extracted annotated grammars are still context-free, we can remove those symbols which will never contribute to a reading. These symbols and the productions using them are called useless and there exist a fast decidable algorithm that, given a grammar, produces a smaller grammar which does not contain useless productions (Hopcroft and Ullman Reference Hopcroft and Ullman1979). The runtime efficiency of a CF parser clearly benefits from the removal of such useless productions, helping the parser to avoid dead derivation branches. Note that, in general, unsuccessful rule instantiations in the unification parser can not be computed beforehand, due to the infinite number of ‘categories’ in a unification-based grammar (the set of all feature structures produced by a UBG is usually infinite).

5.2 Automatic lexicon extension

New utterances not covered by the corpus are only recognized by the extracted CFG if they can be mapped to already parsed syntactic constructions and to already seen words. One can imagine that the relevant domain-specific syntactic constructions can be covered by a sufficiently large training corpus. Lexical gaps, however, should not be attacked by taking more samples into account. One way to enlarge the CF lexicon is by mapping lexicon entries from the HPSG to related terminal symbols in the CFG, originating from parsing the training corpus. Assume, the training corpus contains

Bill gives Mary a book

but does not mention the word cookie. A sentence such as

Bill gives Mary a cookie

will then not be recognized.

The extraction process has represented book by the unary production

where book_nl can be seen as a preterminal, speaking in terms of CFGs.

By inspecting the HPSG lexicon, we will then fhd that book is of the same lexical type as cookie, viz., book_nl. Thus we can enlarge the CF lexicon by

By exploiting this procedure, we can at least guarantee that the CFG will have the same lexical coverage than the UBG.Footnote ⁶

5.3 Grammar postprocessing

Lexicon extension is related to a postprocessing step which ‘taassages” the approximated CFGs, more precisely, the rules which have a preterminal symbol such as in [prep*, . . .] on their RHS. For instance, we might have

Now assume that our training corpus does not contain the preposition on and that automatic lexicon extension has added the following ‘lexicon lookup” (or lexical) rule

However, we are still missing the very likely CF rule

Constructing such new rules, however, is not that difficult. Clearly, when addressing this topic properly, the need for a larger training corpus is probably no longer that demanding.

A much simpler way to achieve more generality is, however, to omit the primary category symbol, so that the above example reduces to

Clearly, this strategy can also be applied to every nonterminal, resulting in smaller grammars, since a lot of rules will probably collapse. The results of deleting the primary category symbol of each nonterminal are presented for a small test corpus insection 6.3.

5.4 Constructing meaningful output

In case we are not only interested in a context-free boolean recognizer, but would like to see some useful output, e.g., MRS-like structures (Copestake, Lascarides and Flickinger Reference Copestake, Lascarides and Flickinger2001), we can either apply two-stage parsing here (see above), letting the UBG deterministically replay the CF parse trees, or (automatically) equip the approximated CFGs by ‘semantic rules’, similar to attribute grammars, a framework extensively used in syntax-directed translation, dating back to the early sixties (Aho, Sethi and Ullman Reference Aho, Sethi and Ullman1986).Footnote ⁷ The latter approach completely obviates UBG parsing and has the further advantage that overgeneration within the extracted CFG will not be prohibited by a subsequent, more restrictive UBG reparse.

Such semantic rules can not be obtained directly from the passive edges of a chart (or even from the extracted CF rules), but instead must be reconstructed from the CF rules with the help of the HPSG rule schemata, together with the total surjective mapping from CF rules to HPSG rule schemata.

Let us give an example. Assume that the training corpus contains the sentence

Tigger meows

for which we obtain, among other rules,

The unique (slightly simplifed) HPSG rule schema associated with the LHS of subjh[verb, . . .] plus the inherited HPSG principles gives us a feature structure which exactly specifes the ‘transport’ of information from the daughters to the mother (⊕ denotes list append):

This transport is expressed through coreferences (

and

) and has to be remodeled in the semantic rules attached to the CF rule. We thus enrich the above extracted CF production by the following two simplifed semantic rules (we use a kind of PATR-II notation, where 0 denotes the LHS, 1 the first RHS daughter, etc.):

The process of semantic composition must be grounded in the lexicon, thus we equip each lexicon entry of the CFG by the relevant semantic rules which can be obtained from the corresponding lexicon entries of the HPSG (let {. . .} denotes a list of elements):

But perhaps the much simpler procedure of annotating CF symbols with additional, semantically-relevant information from the feature structures might suffice. In this case, successful CF derivation trees will be reinspected in a second phase, where the according semantic information is reconstructed. This approach could also be the starting point for approximating not only recognition grammars, but even useful generation grammars.

6.1 aged

We used the aged test suite (Oepen and Callmeier Reference Oepen and Callmeier2000), consisting of 96 syntactically highly diverse sentences to measure the quality of our approximation (average sentence length: 8.4; maximal length: 19). aged consists of 202 stems that cover a great deal of morphological and lexical variation. 719 full forms were computed from these stems. The PET parser which produced the input charts of passive edges (section 3.1) ran under no restrictions and computed 267,651 passive edges overall. One of the sentence from aged even contributed 139,028 edges. Approximation was performed under rule equivalence and rule subsumption. The length of the annotation vector was varied between 0 and 32.

Figure 6 shows the asymptotic behavior for the number of nonterminal and rules, when compared to the length of the annotation (see also Figure 3). The explosion of rules from fve to six annotations is due to the path SYNSEM | LOCAL | KEYS | KEY who potentially results in more than 4,000 possible values, representing relatively word-specific information. It is usually a good idea not to use such path values as annotations in case the rule set gets too large. Furthermore, approximated CF rules will get too specific when incorporating such information. An optional strategy to cope with such a value overload is described in Kiefer and Krieger (Reference Kiefer, Krieger, Oepen, Flickinger, Tsuji and Uszkoreit2002), viz., type generalization.Footnote ⁸

Fig. 6.

Total number of rules for the aged test suite, obtained under both equivalence (E-rules) and subsumption (S-rules). The explosion in the number of rules from 5 to 6 is due to the path SYHSEMI|LOCAL|KEYS|KEY.

Fig. 7.

Useful and useless rules for aged, obtained under rule equivalence (without lexicon lookup rules). All measurements were conducted on a 833 MHz Linux workstation under Allegro Common Lisp 6.0.1. ppedges refers to packed passive edges.

Fig. 8.

Useful and useless rules for aged, obtained under rule subsumption (without lexicon lookup rules). The runtime is measured for the first stage of two-step parsing, i.e., for the CF stage.

The next two tables present runtime measurement and show that the useless rules outweigh when moving to larger annotation vectors. The numbers also show (at least for aged and csli, see next section) that the grammars obtained under rule equivalence are nearly of the same size as those obtained under rule subsumption, but are overall better when regarding the number of readings (readings). This will clearly gain importance in the second stage of an UBG-replay approach. Considering the UBG parser, 1,589 readings for aged were found. PET failed for 17 of the 96 sentences when using the English HPSG.

A plot of the number of rules obtained under rule equivalence against the number of samples is shown in Figure 9.

Fig. 9.

Fig. 9. Plot of the number of all rules obtained under rule equivalence against the number of samples from aged. Note that we depict the sum of useful and useless rules without start productions here. The table clearly shows that, at least for 226 symbol annotations, the training corpus is too small.

We also conducted measurements for two grammars under rule equivalence. The pure HPSG parser, fully equipped with quick-check fltering, resulted in an overall parse time of 1,361.5 seconds. Total time of two-stage parsing (CF parsing plus UBG replay using the full HPSG) for aged was

• • 110 annotations: 59.4 sec = 22.9 ×speedup

• • 226 annotations: 52.8 sec = 25.8 × speedup

Considering runtime, the grammar with 226 annotations was better, since HPSG replay had carried out less unifications.

6.2 csli

The csli test suite which originated from the old HP test suite developed at Hewlett Packard Labs (Oepen and Flickinger Reference Oepen and Flickinger1998), consists of 5,720 grammatical and ungrammatical samples. It is intended to cover a great deal of the syntactical constructions of English. Average sentence length is 5.0, maximal length 20. 585 full forms (= #CF terminal symbols), e.g., “little”, and 3269 lexicon lookup rules (= #preterminal symbols or lexical categories), e.g.,

can be found in every approximated grammar (i.e., average ambiguity rate per stem ≈ 5.6). The maximal number of passive chart edges in the PET parser was set to 100,000. 7,981 readings were found by PET. 3,246 sentences of 5,720 could not be analyzed by PET, given the HPSG and the edge limitation. 91 sentences of csli contain a lexical gap not covered by the lexicon of the HPSG.

For csli, we obtained the following measurements for the approximated CFGs (see Figures 10 and 11).

Fig. 10.

Number of rules (including start productions and lexicon lookup rules) and nonterminals for the csli test suite, obtained both under equivalence (E-rules, E-nonterms) and subsumption (S-rules, S-nonterms). The rule set both contains useful and useless rules.

Some of the numbers from Figure 11 were astounding on first sight. Firstly, the decrease of useful rules from 10 to 18 annotations seems to contradict to what has already been said before. However, we have always argued that the total number of all rules increases when moving to a larger annotation. This decrease is due to the fact that “older” useful rules have been outdated, i.e., have become useless through the specialization of some of their CF symbols (more annotations).

Fig. 11.

Useful and useless rules for csli, obtained under rule equivalence (without lexicon ‘lookup” rules). Less than a fourth of all rules are useful under the most specifb CFG. Note the decrease of useful rules when moving from 10 to 18 annotations, although the total number of rules increases. Note also the increase of readings from 110 to 226 annotations, even though the recognized language gets smaller (cf. number of errors). Overgeneration against the UBG (7,981 readings) w.r.t. training corpus was between 2.29 and 2.82 for the two largest grammars. Recall that the original HPSG produces 3,246 errors which are properly approximated by the most specifb CFG above (viz., 3,065). The runtime is measured for the first stage of two-step parsing, i.e., for the CF stage.

Secondly, the number of readings might increase when we equip the CF symbols with more information. Again, this does not stand in contrast to what has already been said. Clearly, a more specialized CF grammar (226 annotations) recognizes a smaller language than a more general CFG (110 annotations). This fact is supported by the number of errors in Figure 11 (more errors). ‘Older” CF rules, here, are split up into new specialized instances when adding more annotations. In a certain sense, new information might add spurious ambiguities. Thus, the CFG with 110 annotations can be seen to better approximate the UBG than the bigger CFG. This behavior should be taken into consideration in the context of two-stage UBG replay parsing.

However, the measurements for two-stage parsing (110 and 226 annotations) are of a different kind and show that the restrictedness of the CFG (= number of errors) should be taken into account when judging the practical usefulness of a grammar. The grammar with 226 annotations per symbol leads to fewer unification in the UBG replay stage. HPSG baseline for the 5,720 sentences was 2,777.3 seconds (again, quick-check fltering was switched on).

• • 110 annotations: 30.7 sec = 90.5x speedup

• • 226 annotations: 28.5 sec = 97.4x speedup

This speedup of nearly two magnitudes shows the enormous potential of our method. We fnish this section with a plot of the number of rules obtained under rule equivalence against the number of samples (Figure 12).

Fig. 12.

Plot of the number of all rules obtained under rule equivalence against the number of samples for csli. Note that we depict the sum of useful and useless rules without start productions here. Again, the table clearly shows that, at least for 226 symbol annotations, the training corpus is too small.

6.3 Putting it to the test

Similar to Kiefer et al. (Reference Kiefer, Krieger and Prescher2002), we chose a sample of sentences from csli as input to a test run. The corpus was divided into a training set (90% = 5148 sentences) and a test set (10% = 572 sentences) to measure the quality of the approximated CFG w.r.t. overgeneration, recognition of ungrammatical sentences, and speedup (see Figure 13).

Fig. 13.

Useful and useless rules for the 90% training corpus from csli, obtained under rule equivalence (without lexicon ‘lookup” rules). Runtime measurements (#ppedges, readings, errors, runtime[s]) are performed against the 10% test corpus (572 sentences) for full two-stage parsing (sum of both stages). Row 3 and 4 presents the results for the two grammars after deleting the main category symbols in CF rules (-CAT). Speedup is more than 100 here (compare this with the results from last subsection), since failed CF parses are, of course, not replayed by the second HPSG stage.

As already indicated by Figure 12, the training corpus is clearly too small for the approximated grammar with 226 annotations (and probably also too small for 110 annotations). Nevertheless, we conducted a test with both grammars to see how far the two-step approach is away from the HPSG baseline. The HPSG alone resulted in 382 readings and 384 errors for the 572 test sentences (= 188 well-formed sentences w.r.t. the HPSG). Two-step parsing with the approximated grammars resulted in 459 and 494 errors, resp. That is, 75/110 (= 459/494 − 384) of 188 (= 572 − 384) grammatical sentences were classifed as ungrammatical according to the missing rules hidden in the training corpus (see figure 13). The results are not as bleak as it seems, since csli is a highly diverse test suite, where the deletion of a single training sentence (and its specific syntactic structure) usually results in an approximated grammar that does not recognize this sentence. More redundant, homogeneous real-world data (say, newsgroups) will probably show a better adaption of the approximated grammars to a test sample.

The situation, however, can be improved by omitting the main category symbol in each nonterminal (of each rule). As a result, original incompatible rules suddenly collapse into a new rule (see section 5.3). This strategy in part compensates the unseen data, yielding slightly better results: 444/480 errors have now been detected (see Figure 13).

Overall, the relatively small amount of training material is responsible for recognizing only half of the grammatical sentences (recall the curves for the two most restrictive grammars in figure 11). In case we do not have enough training material, a more ‘liberal grammar” might be a good compromise here for two-stage parsing, since it produces less errors (see the first line in Figure 13 for the CFG with 32 annotations). However, such a grammar clearly shifts a larger workload to the HPSG side.