Learning for Deep Language Understanding

1 Introduction

Recently, several machine learning approaches have been proposed for mapping sentences to their formal meaning representations [Ge and Mooney, 2005; Zettlemoyer and Collins, 2005; He and Young, 2006; Wong and Mooney, 2007; Poon and Domingos, 2009; Muresan, 2008; Kwiatkowksi et al., 2010]. These approaches differ in the meaning representation languages they use and the integration, or lack thereof, of the meaning representations with grammar formalisms. λ-expressions and Combinatory Categorial Grammars (CCGs) [Steedman, 1996] are used by [Zettlemoyer and Collins, 2005; Kwiatkowksi et al., 2010], and ontologybased representations and Lexicalized Well-Founded Grammars (LWFGs) [Muresan, 2006; Muresan and Rambow, 2007] are used by [Muresan, 2008].

An advantage of the LWFG formalism, compared to most grammar formalisms for deep language understanding such as Head-Driven Phrase Structure Grammar (HPSG) [Pollard and Sag, 1994], Tree Adjoining Grammars (TAGs) [Joshi and Schabes, 1997], Lexical Functional Grammars (LFGs) [Bresnan, 2001], is that it is accompanied by a learnability guarantee, the search space for LWFG induction being a complete grammar lattice [Muresan, 2006; Muresan and Rambow, 2007]. Some classes of CCGs has been proven to be learnable, however, to our knowledge no tractable learning algorithms have been proposed. Moreover, LWFG is suited to learning in data-poor settings. Building large treebanks annotated with complex representations needed to learn deep In this paper we introduce tractable algorithms for LWFG induction. The theoretical learning model proposed by Muresan and Rambow [2007] characterizes the importance of substructures in the model not simply by frequency, but rather linguistically, by defining a notion of "representative examples" that drives the acquisition process. Informally, representative examples are "building blocks" from which larger structures can be inferred via reference to a larger generalization corpus [Muresan and Rambow, 2007]. The first algorithm assumes that the learner has access to an ordered set of representative examples. In the second algorithm introduced in this paper, the learner does not have a-priori knowledge of the order of the examples, nor of which are the representative examples, learning being done from the entire generalization corpus. We compare these algorithms in terms of their complexity and hypothesis space for grammar induction. We present an experiment of learning tense, aspect, modality and negation of verbal constructions using these algorithms, and show they cover well-established benchmarks for these phenomena developed for deep linguistic formalisms. Proposing tractable learning algorithms for a deep linguistic formalism and learning methods from small amount of training data, opens the door for large scale deep language understanding.

In Section 2, we give a background on Lexicalized WellFounded Grammars [Muresan and Rambow, 2007], including their formal definition. In Section 3, we present our two grammar learning algorithms, as well as the definition of a LWFG parser, which is used as an innate inference engine during learning. In Section 4, we compare the two algorithms in terms of complexity and hypothesis space for grammar induction. In Section 5, we describe our experiment for learning tense, aspect, modality and negation of verbal constructions. We conclude in Section 6.

2 LexicalizedWell-Founded Grammar

Lexicalized Well-Founded Grammar (LWFG) is a recently developed formalism for deep language understanding that balances expressiveness with provable learnability results [Muresan, 2006; Muresan and Rambow, 2007; Muresan, 2010]. Formally, Lexicalized Well-Founded Grammar is a type of Definite Clause Grammars (Pereira and Warren, 1980) that is decidable and learnable. In LWFG, there is a partial ordering relation among nonterminals, which allows LWFG learning from a small set of examples. Grammar nonterminals are augmented with strings and their syntactic-semantic representations, called semantic molecules, and grammar rules can have two types of constraints, one for semantic composition and one for semantic interpretation. Thus, LWFGs are a type of syntactic-semantic grammars.

1 Statistical syntactic parsers for CCGs [Hockenmaier and Steedman, 2002; Clark and Curran, 2007] have been learned from CCGBank [Hockenmaier and Steedman, 2007], a large treebank derived from the Penn Treebank [Marcus et al., 1994].

A semantic molecule associated with a natural language string w, is a syntactic-semantic representation, w′ = (hb ), where h (head) encodes compositional information (e.g., the string syntactic category cat), while b (body) is the actual semantic representation of the string w, which in LWFG is ontology-based - the variables are either concepts or slots identifiers in an ontology. An example of a semantic molecule for the noun phrase formal proposal is given below:

When associated with lexical items, the semantic molecules are called elementary semantic molecules.

In addition to a lexicon, a LWFG has a set of constraint grammar rules, where the nonterminals are augmented with pairs of strings and their semantic molecules. These pairs are called syntagmas, and denoted by σ = (w,w′ ) = (w, (hb )). LWFG rules have two types of constraints, one for semantic composition (Φc) - defines how the meaning of a natural language expression is composed from the meaning of its parts - and one for semantic interpretation (Φi) - validates the semantic constructions based on a given ontology. An example of a LWFG rule for a simple noun phrase is given below:

The composition constraints Φc are applied to the heads of the semantic molecules and are a simplified version of "path equations" [Shieber et al., 1983] (see Figure 3 for examples). These constraints are learned together with the grammar rules [Muresan, 2010]. The semantic interpretation constraints, Φi, represent the validation based on an ontology and are not learned. Φi is a predicate which can succeed or fail -when it succeeds, it instantiates the variables of the semantic representation with concepts/slots in the ontology. For example, given the phrase formal proposal, Φi succeeds and returns 〈 X1.isa=formal, X.manner=X1, X.isa=proposal 〉, while given the phrase fair-hair proposal it fails. The semantic interpretation constraint, Φi serves as a local semantic interpreter at the grammar rule level.

Muresan and Rambow [2007] formally defined LWFGs. We present below their formal definition, slightly changed by Muresan [2010], and introduce other key concepts that are needed for presenting the learning algorithms. We keep their notation for consistency.

Definition 1. A LexicalizedWell-FoundedGrammar (LWFG) is a 7-tuple, G = 〈Σ, Σ′ , NG, ⪰, PG, PΣ, S〉, where:

1. Σ is a finite set of terminal symbols.
2. Σ′ is a finite set of elementary semantic molecules corresponding to the terminal symbols.
3. NG is a finite set of nonterminal symbols. NG ∩ Σ = ∅. We denote pre(NG) ⊆ NG, the set of pre-terminals (a.k.a, parts of speech)
4. ⪰ is a partial ordering relation among nonterminals.
5. PG is the set of constraint grammar rules. A rule is written A(σ) → B1(σ1), . . . ,Bn(σn): Φ(¯σ), where A ∈ (NG - pre(NG)), Bi ∈ NG, ¯σ = (σ, σ1, ..., σn) such that σ = (w, w′ ), σi = (wi, wi ′ ), 1 ≤ i ≤ n, w = w1 · · · wn, w′ = w′1 ◦ · · · ◦ w′n , and ◦ is the composition operator for semantic molecules. 2 For brevity, we denote a rule by A → β : Φ, where A ∈ (NG - pre(NG)), β ∈ N + G .
6. PΣ is the set of constraint grammar rules whose lefthand side are pre-terminals, A(σ) →, A ∈ pre(NG). We use the notation A → σ for these grammar rules.
7. S ∈ NG is the start nonterminal symbol, and ∀A ∈ NG, S ⪰ A (we use the same notation for the reflexive, transitive closure of ⪰).

In LWFG due to partial ordering among nonterminals we can have ordered constraint grammar rules and nonordered constraint grammar rules (both types can be recursive or non-recursive). A grammar rule A(σ) → B1(σ1), . . . ,Bn(σn): Φ(¯σ), is an ordered rule, if for all Bi, we have A ⪰ Bi. In LWFGs, each nonterminal symbol is a left-hand side in at least one ordered non-recursive rule and the empty string cannot be derived from any nonterminal symbol.

2.1 Derivation in LWFG

The derivation in LWFG is called ground syntagma derivation, and it can be seen as the bottom up counterpart of the usual derivation. Given a LWFG, G, the ground syntagma derivation relation, ∗G ⇒, is defined as: A→σ A∗G ⇒σ (if σ = (w,w′ ),w ∈ Σ,w′ ∈ Σ′ , i.e., A is a preterminal), and Bi ∗G ⇒σi, i=1,...,n, A(σ)→B1(σ1),...,Bn(σn): Φ(¯σ) A∗G ⇒σ . In LWFGs all syntagmas σ = (w,w′ ) derived from a nonterminal A have the same category of their semantic molecules w′ (hA.cat = A). This property is used for determining the left hand side nonterminal of the learned rule.

2 Semantic molecule bodies are just concatenated b = [b1, . . . , bn]ν, where ν - variable substitution- is the most general unifier of b and b1, . . . , bn, being a particular form of the commonly used substitution [Lloyd, 2003]. The composition of the semantic molecule heads is given by the composition constraints Φc(h, h1, . . . , hn).

2.2 Language/Sublanguage in LWFG

The set of all syntagmas generated by a grammar G is Lσ(G) = {σ|σ = (w,w′ ),w ∈ Σ+, ∃A ∈ NG,A ∗G ⇒ σ}. Given a LWFG G, Eσ ⊆ Lσ(G) is called a sublanguage of G. Extending the notation, given a LWFG G, the set of syntagmas generated by a rule (A → β : Φ) ∈ PG is Lσ(A → β : Φ) = {σ|σ = (w,w′ ),w ∈ Σ+, (A → β : Φ) ∗G ⇒ σ}, where (A → β : Φ) ∗G ⇒ σ denotes the ground derivation A ∗G ⇒ σ obtained using the rule A → β : Φ in the last derivation step.

Given a LWFG G and a sublanguage Eσ (not necessarily of G), S(G) = Lσ(G)∩Eσ is the set of syntagmas generated by G reduced to the sublanguage Eσ. Given a grammar rule r ∈ PG, S(r) = Lσ(r)∩Eσ is the set of syntagmas generated by r reduced to the sublanguage Eσ. These concepts will be used during learning as performance criteria.

2.3 Chains

A property of Lexicalized Well-Founded Grammars is that the category of a nonterminal is the name of the nonterminal: ∀A ∈ NG we have hA.cat = A. As a consequence, for unary branching rules, A → B: Φ, where A,B ∈ NG, the syntagmas which are ground-derived from (A → B : Φ) ∗G ⇒ σA and B ∗G ⇒ σB have the same string w and the same semantic representation b, but have different semantic molecule heads hA ̸= hB. These syntagmas are called equivalent and denoted by σA ≡ σB.

Informally, we can define a chain as a set of ordered unary branching rules: {Bk → Bk-1,Bk-1 → Bk-2, . . . ,B2 → B1,B1 → β} such that syntagmas generated by these rules are equivalent. The notion of chain is similar to the concept of spines in Tree Adjoining Grammars [Carreras et al., 2008], but not limited to just lexical anchors. The chain nonterminal set for equivalent syntagmas σi = (w,w′i ) is the set of nonterminals in the chain, chs(w) = {Bk, . . . ,B1,B0}, where Bk ≻ Bk-1 · · · ≻ B1 and B0 = β, such that Bi ∗G ⇒ σi for 0 ≤ i ≤ k. Chains and chain nonterminal sets will be used to generalize grammar rules during LWFG learning.

2.4 Representative Examples

The partial ordering relation among nonterminals makes the set of nonterminals well-founded, which allows the ordering of the grammar rules, as well as the ordering of the syntagmas generated by LWFGs. This allows the definition of the representative examples of a LWFG. Muresan and Rambow [2007] informally define the representative examples ER of a LWFG, G, as the simplest syntagmas ground-derived by the grammar G. That is, for each grammar rule there exist a syntagma which is ground-derived from it in the minimum number of steps.

3 Grammar Induction Algorithms

The theoretical learning model for LWFG induction, Grammar Approximation by Representative Sublanguage (GARS), together with a learnability theorem was introduced in [Muresan and Rambow, 2007]. LWFG induction is formulated as an Inductive Logic Programming (ILP) learning problem 〈⊢, LB, LE, LH〉 [Kietz and Dˇzeroski, 1994], where the provability relation, ⊢, is given by robust parsing and denoted ⊢rp 3 ; the language of background knowledge,LB, is the set of LWFG rules that are already learned and the elementary syntagmas corresponding to the lexicon; the language of examples, LE are syntagmas of the generalization sublanguage, which are ground atoms; and the hypothesis language, LH, is a complete LWFG lattice which preserves the parsing of representative examples, ER.

The GARS model, as defined by Muresan and Rambow [2007], takes as input a set of representative examples, ER, and a generalization sublanguage Eσ (finite and conformal 4 ), and learns a grammar G using the above ILP-setting, such that G is unique and Eσ ⊆ Lσ(G). ER is used to construct the most specific hypotheses (grammar rules), and thus all the grammars should be able to generate these representative examples, ER (this property is equivalent to ILP consistency property, which states that all the learned hypotheses need to be consistent with all the positive examples, and none of the negative examples [Kietz and Dˇzeroski, 1994]). The generalization sublanguage Eσ is used during generalization, only the most general grammar being able to generate the entire sublanguage.

In this section we describes two tractable algorithms for the GARS model. The first algorithm uses an ordered set of representative examples (examples in ER are ordered from the simplest to the most complex) (see Section 3.2). The reader should remember that for a LWFG G, there exists a partial ordering among the grammar nonterminals, which allows a total ordering of the representative examples of the grammar G. Thus, in this algorithm, the learner has access to the ordered set when learning the grammar. In the second algorithm, the learner does not have a-priori knowledge of the order of the examples, nor of which are the representative examples, learning being done from the entire generalization sublanguage (see Section 3.3).

The assumption that all the algorithms rely on is that the rules corresponding to pre-terminals (PΣ in Definition 1) are given, i.e., they are not learned. These rules can be constructed from the lexicon. Only the set of rules corresponding to nonterminals NG - pre(NG) (i.e., PG in Definition 1) are learned.

Both learning algorithms use a robust parser as an innate inference engine introduced in the next section.

3.1 Robust Parser as Innate Inference Engine for Grammar Induction

The LWFG parser is a bottom-up active chart parser [Kay, 1973] that is an effectively r-reversible program [Neumann and van Noord, 1994], i.e., it is capable of both parsing and generation and it is guaranteed to terminate.

3⊢rp is equivalent to ground syntagma derivation ∗G ⇒.

4 The property of conformal introduced in [Muresan and Rambow, 2007] is similar to the notion of structural completeness of a positive sample w.r.t. an automaton [Dupont et al., 1994]. This allows learning based only on positive examples.

The semantics of the LWFG parser is given by the definitions presented below. Let us consider (w,w′ ) ∈ Eσ ⊆ Lσ(G) a syntagma derived by a grammar G, such that w = w1 · · ·wn is a string, w′ = (hb ) is its semantic molecule, and b = b1 · · · bn is the string semantic representation. The parser is used both during the generation of candidate hypotheses (Definition 3), and during their evaluation in order to choose the best performing one (Definition 2).

Definition 2 (Parsing for performance criteria). We define the set of syntagmas returned by the robust parser by: Lσ(w) = {σ|σ = (wij,w′ij ), with wij = wiwi+1 · · ·wj-1, wi, . . . ,wj-1 ∈ Σ, 1 ≤ i ≤ j ≤ n + 1, s.t. ∃A ∈ NG, A ∗G ⇒ σ}

Moreover, for all syntagmas σ ∈ Lσ(w), the parser returns the ground derivation length, gdlG(σ), which is the minimum number of ground-derivation steps used to derive σ from grammar G.

Definition 3 (Parsing for hypothesis generation). When both the string (w) and its semantic representation (b) are given, we define the set of syntagmas parsed by the robust parser by Lσ(w, b) = {σ|σ = (wij,w′ij ),with wij = wi · · ·wj-1,w′ij = (hij bij ), bij = (bibi+1 · · · bj-1)νij, wi, . . . ,wj-1 ∈ Σ, w′i = (hi bi ) ∈ Σ′ , . . . , w′j-1 = (hj-1 bj-1 ) ∈ Σ′ 1 ≤ i ≤ j ≤ n+ 1, s.t. ∃A ∈ NG, A ∗G ⇒ σ}

It can be noticed that the parser returns all the subsyntagmas (chunks), and thus it is robust, which is essential for hypothesis generation during learning.

3.2 Grammar Learning fromOrdered Representative Examples

Algorithm 1 describes the LWFG induction based on an ordered set of representative examples. The algorithm visits each representative example in turn, learning a new grammar rule from the current representative example σ ∈ ER using the procedure LearnRule. This rule is added to the grammar rule set PG (PG is added to the background knowledge K, but for clarity, in the algorithm, we give G explicitly as an argument, and not part of K). The process continues until all the representative examples are covered.

Algorithm 1: Grammar Induction(ER,Eσ,K)

Data: Ordered representative examples, ER generalization sublanguage, Eσ

Background Knowledge, K Result: Learned grammar (rules+constraints), PG PG ← ∅ foreach σ ∈ ER do rσ ← LearnRule(σ, G, Eσ , K) PG ← PG ∪ {rσ} return PG

We describe below the process of learning a grammar rule from the current representative example (i.e., LearnRule procedure).

Procedure LearnRule(σ, G, Eσ , K)

Let σ = (w, (hb ))

• 1 Most Specific Grammar Rule Generation
• w ← min(w1 . . . wn) s.t b = (b1, . . . , bn)ν /* w = w1 . . .wn, (wj, (hj bj )) ∈ Lσ(w, b), 1 ≤ j ≤ n; n is the min num of chunks given by robust parser */
• chs(wj ) = {Bj |σj ≡ (wj , (hj bj )), Bj ∗G ⇒ σj}, 1 ≤ j ≤ n chain(wj ) = {BKj j → BKj -1 j , . . . ,B1 j → B0 j }
• r ← (A → B0 1 , . . . , B0n : Φr)
• 2 Grammar Rule Generalization

return r

Procedure LearnRule has two main steps: 1) generation of the most specific grammar rule r from the current representative example σ, and 2) generalization of this rule using as performance criterion the coverage of the generalization sublanguage Eσ.

Most specific rule generation. In order to generate the most specific grammar rule, the robust parser first produces the minimum number of chunks that cover σ = (w, (hb )) - starting from the string w and its semantic representation b (see Definition 3). Let us assume that our current representative example is σ = (formal proposal, (hb )), where the semantic molecule (hb ) was given in Section 2. And let us assume that the background knowledge contains the pre-terminal rules PΣ for the adjective formal and the noun proposal (i.e., Adj → (formal, (h1 b1 )); Noun → (proposal, (h2 b2 ))), as well as previously learned grammar rules and constraints PG (e.g., N1 → Noun: Φ1). 5 Using this background knowledge, the robust parser returns the chunks that cover the example, namely the adjective formal, and the noun proposal, respectively. Next, in step 1b, for each chunk wj, the robust parser determines the set of nonterminals from which σj = (wj,w′j ) is ground-derived, i.e., chs(wj), as well as the corresponding chains. In our example, we have that syntagma corresponding to the adjective formal can be derived only from the pre-terminal Adj, while the noun proposal can be derived from the nonterminal N1 and the pre-terminal Noun. Thus, the only chain that we have is for the noun proposal, and it only contains one unary branching rule: chain(proposal) = {N1 → Noun}. In step 1c, the most specific rule r is generated such that its left-hand side nonterminal is determined from the category annotated in the representative example σ, h.cat = A and the arguments of each nonterminal B0 j from its right-hand side are generalized. In our example, the most specific rule is N1 → Adj Noun: Φ2, where the left-hand side nonterminal is given by the category of the representative example, in this case n1 (see Section 2). The compositional constraints Φ2 are learned as well (Muresan [2010] gave an algorithm for constraint learning, which we used in this paper).

5 For readability we only provide the context-free backbone of the grammar rules, and the semantic composition constraints. Notations and examples are similar to the ones used by Muresan and Rambow [2007] to exemplify the search space, for reference.

Grammar Rule Generalization. In the second step, the rule r is generalized by unary branching rules to a new rule

rg, as long as S(r) ⊂ S(rg). We denote by r j ⊣ rg the generalization of r by unary branching rule Bi j → Bi-1 j in chain(wj). In other words, the most specific rule is generalized based on unary branching rules, obtaining thus a set of candidate grammar rules. The performance criterion in choosing the best grammar rule among these candidate hypotheses is the number of examples in the generalization sublanguage Eσ that can be parsed using the candidate grammar rule rgi in the last ground derivation step, together with the previous learned rules, i.e., |S(rgi)|. In our example, we obtain two candidate grammar rules: rg1 = (N1 → Adj Noun: Φ2) and rg2 = (N1 → Adj N1: Φ3). Given the generalization sublanguage Eσ={ formal proposal, loud clear noise, the loud noise} the learner will generalize to the recursive rule rg2, since this rule covers more examples in Eσ .

3.3 General Grammar Learning

Algorithm 1 presented in the previous section requires the learner to have knowledge of the representative examples, and the "true" order of those examples (i.e., from simpler to more complex). In this section we introduce a new general algorithm for LWFG induction, which does not require such a-priori knowledge. This algorithm has big practical implications, since when modeling complex language phenomena it might not be realistic to provide the right order of examples, or even to know which are the representative examples, without relying on deep linguistic knowledge. Algorithm 2 is an iterative grammar induction algorithm, which learns based on a set of examples E∗ that can be either an unordered representative example set EuR (when we have knowledge of the representative examples), or the entire generalization corpus Eσ (when we do not have such knowledge).

Initially, for each example σ ∈ E∗ , a rule rσ is learned using the LearnRule procedure (stage 1). Each rule covers at least the example from which it was learned (ILP consistency property), and we have that |PG| = |E∗ |, property which will remain true at each iteration step of the algorithm (stage 2).

At each iteration step (stage 2), the rule corresponding to the current example σ is deleted from the existing set of grammar rules (PG- ← PG-{rσ} ). If by deletion of rσ we have that |S(G-)| = |S(G)| (step 3) - i.e., there exist a more general rule rσ′ that covers the current example σ, as well as the example it was learned from σ′ - we keep in PG only this more general rule, and we delete from E∗ the example with the maximum ground derivation length (σmax). In other words, we keep the most general rule in PG and the simplest example in E∗ . Otherwise, the algorithm (re)learns the rule

Data: E∗ can be either EuR or Eσ generalization sublanguage Eσ Background Knowledge, K Result: Learned grammar (rules+constraints), PG, Representative examples,ER PG ← ∅ 1 foreach σ ∈ E∗ do rσ ← LearnRule(σ, G, Eσ , K) PG ← PG ∪ {rσ} 2 repeat OG ← PG foreach σ ∈ E∗ do PG- ← PG - {rσ} // σ ∈ S(rσ) 3 if S(G) = S(G-) then Let σ′ ̸= σ s.t. σ ∈ S(rσ′ ) // σ′ ∈ S(rσ′ ) if gdlG-(σ) ≥ gdlG-(σ′ ) then σmax ← σ else σmax ← σ′ E∗ ← E∗ - {σmax} 4 elserσ ← LearnRule(σ, G-, Eσ , K) PG ← PG- ∪ {rσ} until OG = PG ER ← E∗ return PG, ER

from the current example σ based on all the other rules, using the procedure LearnRule, and then it adds the new rule to the set of grammar rules PG (step 4). The algorithm iterates until the grammar learned during the last step is the same as the grammar learned in the previous step (PG = OG). At the end, E∗ will contain just the representative examples.

Algorithm 2 is an instance of "theory revision", because after a grammar ("theory") is learned during the first stage, the grammar ("theory") is revised (by deleting and adding rules). In the next section we discuss the complexity of these two algorithms and the property of the hypothesis space.

4 Hypothesis Space and Algorithm Complexity

Muresan and Rambow [2007] have proven that the search space for LWFG induction is a complete grammar lattice, giving a learnability theoremwhich states that: if ER is the set of representative examples associated with a LWFG G conformal with respect to a sublanguage Eσ ⊇ ER, then G can always be learned from ER and Eσ as the top element (⊤ = G) of the complete grammar lattice. In Figure 1 the complete grammar lattice is shown in blue, and we have |PG| = |ER|. This property of the search space holds for algorithms where the learner has knowledge of the representative examples, being it ordered or unordered.

However, in the case of Algorithm 2 when we learn directly from Eσ, the search space only converges to a complete grammar lattice (Figure 1). Initially when we have that |PG| = |E∗ | > |ER|, the search space is not a complete grammar lattice since we have grammar rules that do not preserve the parsing of the representative examples. For example, let us assume that we start with Eσ={loud clear noise, loud noise, noise} and we only have as background knowledge the pre-terminal rules. The grammar rule first learned by Algorithm 2 for the example loud clear noise would be N1 → Adj Adj Noun: Φ. This rule will not parse the representative example loud noise, and will be outside the complete grammar lattice, as given in [Muresan and Rambow, 2007]. However these rules will be eliminated (stage 2), and in the end only the rules which preserve the parsing of the representative examples are kept. Thus, the search space will converge to a complete grammar lattice (|PG| = |ER|). The algorithm is guaranteed to converge to the lattice top element (⊤), since the rule generalization in LearnRule is the inverse of the rule specialization operator used by Muresan and Rambow [2007] to define the complete grammar lattice.

All algorithms introduced in this paper are polynomial. This result provides an advance in practical grammar learning for deep language understanding. While learnability results have been proven for some classes of Combinatorial Categorial Grammars [Steedman, 1996], to our knowledge no tractable learning algorithm has been proposed.

First, the procedure LearnRule is linear on the length of the learned rules and has the complexity O(|β| ∗ max(|chs(wj)|) ∗ |Eσ| ∗ |σ|3 ), where β is the right hand side of grammar rules. We assume a constant bound on the length of the grammar rules. Given this, the complexity of Algorithm 1 is |ER| multiplied with the complexity of the procedure LearnRule, i.e., O(|ER| ∗ |β| ∗max(|chs(wj)|) ∗ |Eσ| ∗ |σ|3 ).

Algorithm 2 terminates after |ER| iterations in the worst case. The complexity of each iteration step is |E∗ | multiplied with the complexity of the procedure LearnRule, thus the overall complexity of Algorithm 2 is O(|ER| ∗ |E∗ | ∗ |β| ∗ max(|chs(wj)|) ∗ |Eσ| ∗ |σ|3 ).

Annotation Effort: Algorithm 1 and Algorithm 2 when E∗ = EuR require a small amount of annotation since only the representative examples ER need to be fully annotated - the sublanguage Eσ used for generalization can be just weakly annotated (i.e., bracketed) or even unannotated. In turn, Algorithm 2 when E∗ = Eσ, requires a larger annotation effort since the entire Eσ set needs to be fully annotated (i.e., utterances and their semantic molecules). To alleviate this effort, we have developed an annotation tool that integrates the parser and the lexicon in order to provide the user with the utterance and the semantic molecules of the chunks, so the user does not need to write the semantic representation by hand.

5 Experiments

An advantage of providing polynomial algorithms for LWFG learning is that instead of writing grammars for deep linguistic processing by hand, we can learn such grammars from examples. Capturing tense, aspect, modality and negation of verbal constructions has been one of the classic benchmarks for deep linguistic processing grammar formalisms, since modeling these phenomena is crucial for temporal reasoning and interpretation of facts and beliefs.

In our experiment, to learn sentence structures with subject and verbal constructions including auxiliary verbs - which capture tense, aspect, modality and negation -- we used 20 representative examples ER (phrases annotated with their semantic molecules, similarly to the example in Section 2), and 106 examples in the generalization sublanguage Eσ. All examples were derived from Quirk et al.'s English grammar [Quirk et al., 1972].

All algorithms converged to the same grammar, which contains 20 rules, including the compositional constraints, also learned. Convergence of the algorithms to the same target grammar is guaranteed by the theoretical results presented in Section 4.

In Figure 3, we show a sample from our learned grammar corresponding to auxiliary constructions dealing with modals, negation, subject-verb agreement, tense and aspect, as well as the corresponding learned constraints for two of the rules. We have 4 nonterminals for auxiliaries. AV 0 models simple form of auxiliaries "be" and "have" as well as modal auxiliaries and the periphrastic auxiliary "do", together with subject agreement and inversion; AV 0 is also used for modeling constructions with relative pronouns used either in questions or relative clause constructions; AV 1 introduces negation; AV 2 introduces the modals and future tense; AV 3 introduces the perfect aspect; while AV 4 introduces the progressive form of the auxiliary "to be", which will be used in conjunction with the passive constructions (e.g., "she may have been being examined by ..."). In this grammar we have the following chain of nonterminals {AV 4, AV 3, AV 2, AV 1, AV 0}. Even if for this grammar of auxiliaries the rules of the grammar seem simple, and someone might wonder if they could have been written by hand, the complexity of the task is emphasized in the learned constraints. Moreover, the grammar becomes more complex as we introduce complex noun phrases that could generalize to Sbj, as well as other verbal constructions. In Figure 2, we show the representative examples used to learn the 8th and 14th grammar rules and constraints, respectively. The examples in the generalization sublanguage used for the 8th rule are {someone is not, who is not, he is not, he can not, he has not}.

To test our learned grammar we have used the Test Suites for Natural Language Processing (TSNLP) [Lehmann et al., 1996], since it includes specific benchmarks for tense, aspect and modality (C Tense Aspect Modality) and negation (C Negation), and it has been used for testing grammars for deep linguistic processing. Using our learned grammar, our parser correctly recognized the 157 positive examples for tense, aspect and modality, and rejected all 38 ungrammatical examples. For negation, out of 289 positive examples

Sample Representative Examples

1. (someone is not, [cat:av1,stype:s,vtype:aux,vft:fin,int:no,dets:y,aux:be,neg:y,tense:pr,pers:( ,3),nr:sg,pf:no,pg:no,headS:X,head:Y]▷◁ 〈X.isa=someone,Y.tense=pr,Y.neg=y 〉)
2. (someone is being),[cat:av4,stype:s,vtype:aux,vft:fin,int:no,dets:y,aux:be,neg:no,tense:pr,pers:( ,3),nr:sg,pf:no,pg:y,headS:X,head:Y] ▷◁ 〈 X.isa=someone, Y.tense=pr,Y.pg=y 〉)

Sample learned compositional constraints Φc

Φc8(h, h1, h2) = {h.cat=av1,h.stype=h1.stype,

h.vtype=h1.vtype,h.vtype=h2.vtype,

h.vft=fin,h1.vft=fin,h.int=h1.int,

h.dets=h1.dets,h.aux=h1.aux,h.neg=h2.neg,

h.tense=h1.tense,h.pers=h1.pers,h.nr=h1.nr,

h.pf=h1.pf,h.pg=h1.pg,h.headS=h1.headS,

h.head=h1.head,h.head=h2.head,h1.cat=av0,

h1.neg=no, h2.cat=aux, h2.aux=not}

Φc14(h, h1, h2) = {h.cat=av4,h.stype=h1.stype,

h.vtype=h1.vtype,h.vtype=h2.vtype,

h.vft=fin,h1.vft=fin,h.int=h1.int,

h.dets=h1.dets,h.aux=be,h1.aux=be,

h2.aux=be,h.neg=h1.neg,

h.tense=h1.tense,h.pers=h1.pers,h.nr=h1.nr,

h.pf=h1.pf,h.pg=h2.pg,h.headS=h1.headS,

h.head=h1.head,h.head=h2.head,h1.cat=av3,

h1.pg=no,h2.cat=aux,h2.vft=nfin}

Table 1: Example of grammatical(G) and ungrammatical(UG) utterances, accepted and rejected by the learned grammar, repectively

the parser covered 288 6 and rejected all the negative examples (129). Example of correct utterances and ungrammatical utterances are given in Table 1.

Our parser returns the semantic representation of the utterance. For example, for the utterance She might not have been being seen the parser returns 〈1.isa = she, 2.mod = might, 2.neg = y, 2.tense = pr, 2.pg = y, 2.pf = y, 2.isa = see, 2.ag = 1〉 (where pg and pf relates to verb's aspect: progressive and perfective, respectively; and ag refers to the semantic role agent of the verb see, which is she).

6 The example not covered was He not might have been succeeding, which we believe should not be part of the grammatical examples, since it has negation before the modal might.

6 Conclusions and FutureWork

We have described two polynomial algorithms for Lexicalized Well-Founded Grammar learning, which are guaranteed to learn the same unique target grammar. We have discussed these algorithms in terms of their search space, complexity and a priori knowledge that the learner needs to have (ordered vs. unordered representative examples, knowledge of the representative examples vs. absence of such knowledge). We have described an experiment of learning tense, aspect, modality and negation of verbal constructions using these algorithms, and show they covered well-established benchmarks for these phenomena developed for deep linguistic formalisms. Proposing tractable learning algorithms for a deep linguistic grammar formalism opens the door for large scale deep language understanding. Moreover, being able to learn from a small amount of data will enable rapid adaptation to different domains or text syles.

We are currently extending the grammar with probabilities in two ways: 1) adding probabilities at the rule level similar to other probabilistic grammars, and 2) modeling a weighted ontology (thus Φi behaves as a soft constraint, rather than a hard one).

Acknowledgements

The author acknowledges the support of the NSF (SGER grant IIS-0838801). Any opinions, findings, or conclusions are those of the author, and do not necessarily reflect the views of the funding organization.