Smoothing for Bracketing Induction

1 Introduction

Grammar induction, the unsupervised learning of hierarchical syntactic structure from natural language text, has long been of interest to computational linguists for a variety of reasons: to help to construct large treebanks, to study language acquisition by children, or to induce bilingual synchronous grammar for statistical machine translation. In recent years we have seen considerable improvement in the performance of grammar induction. Most of the researches target at inducing either constituents [Clark, 2001; Klein and Manning, 2002; Klein and Manning, 2004; Bod, 2007; Seginer, 2007; HŠnig, 2010;

* Corresponding Author

Ponvert et al., 2011] or dependencies [Klein and Manning, 2004; Headden III et al., 2009; Cohen and Smith, 2009; Cohn et al., 2010; Spitkovsky et al., 2010].

This paper falls into the first category: inducing constituents. Apart from unsupervised constituent labeling of syntactic categories such as verb phrase (VP) given goldstandard constituent surface strings [Haghighi and Klein, 2006; Borensztajn and Zuidema, 2007], recent constituent induction researches mainly focus on bracketing induction, which is to induce all constituents without labeling their syntactic categories given raw texts [Klein and Manning, 2002; Klein and Manning, 2004; Bod, 2007; Seginer, 2007; HŠnig, 2010; Ponvert et al., 2011]. Diverse techniques have been applied for the bracketing induction, ranging from probabilistic methods to non-probabilistic methods. This paper targets at the bracketing induction, and is based on one probabilistic model: Constituent Context Model (CCM) [Klein and Manning, 2002], which is an effective generative model for the bracketing induction.

In the CCM, probability of a constituent is computed in a straightforward way no matter how long this constituent is. Severe data sparse problem is caused because long constituents are more unlikely to appear in test set. This paper proposes a method for constituent smoothing by defining a non-parametric Bayesian prior distribution over constituents, namely the Pitman-Yor Process (PYP) prior [Pitman and Yor, 1997]. The PYP prior functions as an elegant back-off smoothing method through using a hierarchical smoothing scheme (HSS). Various kinds of HSS are proposed in this paper. We find that two kinds of HSS, both of which back-off a constituentÕs probability to its boundaryÕs probability, significantly improve the performance of the CCM, and attain or significantly improve the state-of-the-art performance of the bracketing induction evaluated on standard treebanks of various languages. Another kind of HSS inspired by language modeling [Teh, 2006b] is proposed. It applies the commonly used n-gram Markovization on constituents, but it turns out ineffective for improving the performance of the CCM.

The rest of the paper is structured as follows: In section 2, we introduce the original CCM. In section 3, we present the proposed Bayesian method for the constituent smoothing. Experiments and results are presented in section 4. Conclusion is presented in section 5.

2 Constituent Context Model (CCM)

The CCM is an important breakthrough for bracketing induction [Klein and Manning, 2002], and is the first to outperform a right-branching baseline on English. Unlike Probabilistic Context Free Grammars which are defined on production rules over trees, the CCM deals with both tree spans and non-tree spans. All spans are represented by two kinds of strings: constituents and contexts. The CCM is a generative model defined over such representations.

Note that, the terminology ÒconstituentÓ in the CCM stands for contiguous surface string of either tree span or non-tree span, and such usage of ÒconstituentÓ will be adopted throughout the following parts of this paper. It distinguishes from the usual usage of ÒconstituentÓ, which only stands for tree spans.

2.1 Constituents and Contexts

Constituents are contiguous surface strings of sentence spans (subsequences), contexts are ordered pairs of tokens preceding and following the constituents. Each sentence span, either a tree span or a non-tree span, is represented by a constituent and a context.

Figure 1 shows examples of constituents and contexts of a sentence, which consists of t1, t2, and t3. A latent bracketing tree with t1, t2, and t3 as terminal nodes is illustrated at the top of Figure 1. The bottom numbers of the tree are indexes for denoting spans.

Given the tree, two sets of constituents and contexts can be extracted as shown in tables of Figure 1. One is about the tree spans, the other is about the non-tree spans. appearing in the contexts denotes a sentence boundary. nil appearing in the constituents of the non-tree spans denotes an empty span, which is actually a space between two terminals (or between a terminal and ). In the CCM, the terminal nodes are part-of-speech (POS) tags, which are also set as terminals in most of our proposed methods, except one which uses both lexicons and POS tags as terminal nodes. Details are presented in section 3.

2.2 Generative Model

For each sentence span, the CCM treats its constituent and context as observed strings, and uses a Boolean variable to indicate whether this span is a tree span or not. The latent bracketing structure of whole sentence can be read off from these Boolean variables. Concretely, there are four kinds of conditional probabilities employed in the CCM: p(∈ |true), p( ∩ |true), p(∈ |false) and p( ∩ |false), where∈ denotes a constituent, ∩ denotes a context, true indicates that the current considered span is a tree span, false for a non-tree span.

The probability of a sentence S and its bracketing tree B is defined as below:

where T(B) denotes the set of tree spans contained in B, i and j are spanÕs boundary indexes over S. First, a bracketing tree B is chosen according to some distribution p(B), then the sentence S is generated given that bracketing tree B. In the CCM, p(B) is taken to be uniform over all possible binary bracketing trees (binary trees with no crossing brackets) of S and zero elsewhere. So, the CCM only induces binary bracketing trees. p(S|B) is the product of the probabilities of all constituents and all contexts, given whether their spans are tree spans or not. An EM-like algorithm is applied on the estimation of this generative model [Klein, 2005].

3 Bayesian Modeling of the CCM for Constituent Smoothing

Bayesian modeling is proposed in this section for overcoming data sparse problem faced by the original CCM, which computes probability of a constituent by MaximumLikelihood-Estimation (MLE, employed in the EM algorithm) no matter how long this constituent is. Long constituents tend to not appear in unseen data, and cause severe data sparse problem.

We propose to define a non-parametric Bayesian prior distribution, namely the PYP prior, over constituents for constituent smoothing. We use Markov Chain Monte Carlo (MCMC) sampling to infer smoothed constituents from posterior distributions over constituents.

At first, the Bayesian framework is introduced in this section. Then, under the Bayesian framework, the constituent smoothing by placing the PYP prior over the constituents is presented, followed by the presentation of MCMC sampling for inference.

3.1 Bayesian Framework

The Bayesian framework for the original CCM is to compute the posterior probabilities of p(∈ |true), p( ∩ |true), p(∈ |false) and p( ∩ |false) after observing a raw corpus. For the ease of explanation, we take a raw sentence S and its bracketing tree B for example:

where c=(c1,c2,É) is a sequence of constituents composing the bracketing tree B, c∨ T(B) means c is a tree span constituent. Similarly, e∠ T(B) means e is a non-tree span constituent. So do the context variables d and f.

Using the BayesÕ rule, the posterior over c, d, e, and f is:

where p(S | c, d, e, f) is either equal to 1 (when S and c, d, e, f are consistent) or 0 (otherwise). Furthermore, under the independent assumption of the original CCM, p(c, d, e, f) = p(c) p(d) p(e) p(f). Therefore, the task of Bayesian modeling of the original CCM turns out to consist of modeling only the four prior distributions p(c), p(d), p(e), and p(f).

Various kinds of distributions can be set as the prior distribution over c, d, e, and f. Over constituents c and e, we put the PYP distribution as the prior distribution for constituent smoothing due to its inherent back-off smoothing property [Teh, 2006b; Blunsom and Cohn, 2010; Cohn et al., 2010; Shindo et al., 2012]. Over contexts d and f, we apply a simpler smoothing method by using the Dirichlet distribution as the prior distribution over d and f because contexts do not confront data sparse problem as seriously as constituents do.

3.2 Constituent Smoothing

In this section, we propose to use the PYP prior for smoothing c and e. Taking c for example:

An element of c, the c, is drawn iid from the distribution Gp, which is drawn from the PYP distribution with a discount parameter a, a strength parameter b, and a base distribution pbase. By integrating out Gp, the predictive probability of cn+1 taking a specific tree span constituent surface string x given c=(c1, É, cn) is:

where nx is the frequency of x collected from c, which consists of n elements. Eq. (3) can be interpreted in a restaurant metaphor: n customers (c1, É, cn in this case) sequentially enter a restaurant. They are seated at K (K n) tables. Customers at each table share only one menu. nx is the number of customers choosing a specific menu x, Kx is the number of tables equipped with menu x. See (Goldwater et al., 2011) for details of the restaurant metaphor.

Compared to the MLE p(cn+1=x|c)=nx/n, eq. (3) manifests a back-off smoothing scheme. nx is discounted by Kxa, and is back-off to the probability pbase(x) with a back-off-weight (Ka+b)/(n+b). For the ease of presentation in the following, we use a succinct form of eq. (3):

where BOW denotes the back-off-weight.

Through the above introduction of the PYP, we can see that the PYP prior shown in formula (2) actually encodes a back-off scheme: ppredictive�pbase, where � denotes the back-off direction. Recursive calling of pbase can build a hierarchical smoothing scheme (HSS).

In this section, we propose various kinds of HSS for constituent smoothing. At first, we propose two kinds of HSS, both of which deal with the boundary representations of constituents. One is named Constituent- Boundary HSS, the other is named Lexicalized HSS. At last, we propose a kind of HSS inspired by language modeling [Teh, 2006b], which uses n-gram Markovization over sequences of words. Though n-gram Markovization is the commonly used smoothing method that is easy to come up with, it is proven ineffective for the CCM as presented in section 4.5.

Constituent-Boundary Hierarchical Smoothing Scheme (CB-HSS)

Taking c for example:

The above formula encodes a back-off scheme: ppredictive�pbound, where pbound models the generation of a constituent c by first generating its boundary representation from a Dirichlet distribution, then generating its middle POS tags from a uniform distribution over POS tags:

where br is a function returning a constituentÕs boundary representation, |POS| is the size of POS tag set, |c|-|br(c)| is the number of the POS tags of c excluding those in the boundary representation, and r donotes a boundary representation of a constituent. Each r is drawn from the distribution B, which is drawn from the Dirichlet distribution with a parameter �.

We use a constituent Òt1 t2 t3 t4Ó for the illustration of the boundary representation. We choose Òt1 t2Ó as left boundary, Òt4Ó as right boundary, if we decide the left boundary width is two and the right boundary width is one. Finally, the boundary representation of the constituent is Òt1 t2 t4Ó. If a constituent spans terminals less than the sum of the left boundary width and the right boundary width, this constituent is represented by itself.

The first row of table 1 illustrates the back-off smoothing scheme of the CB-HSS. The probability of the example constituent Òt1 t2 t3 t4Ó is approximately backed-off to the probability of its boundary representation Òt1 t2 t4Ó if the left boundary width is 2 and the right boundary width is 1. Because in the CB-HSS, Òt3Ó is generated from a uniform distribution over POS tags, and has no disambiguating impact, we omit Òt3Ó in the illustration.

Lexicalized Hierarchical Smoothing Scheme (L-HSS)

L-HSS is the lexicalized version of CB-HSS. It enriches the representation of a constituent, which originally consists of POS tags, with corresponding lexicons. The second row of table 1 shows an example lexicalized constituent Òl1t1 l2t2 l3t3 l4t4Ó, where l denotes a lexicon, t denotes a POS tag. The inclusion of lexicons makes the data sparse problem more serious. More deep hierarchy than the CB-HSS is applied in the L-HSS to the constituent smoothing. Taking tree span constituents for example:

The above formula encodes a back-off scheme: ppredictive�plex, where plex models the generation of a lexicalized constituent clex by first generating its lexicalized boundary from a PYP distribution, then generating its middle lexicons and POS tags from a uniform distribution over all pairs of lexicons and POS tags:

where br(clex) returns the lexicalised boundary of clex. As illustrated in table 1, the lexicalised boundary of Òl1t1 l2t2 l3t3 l4t4Ó is Òl1t1 l2t2 l4t4Ó if left boundary width is 2, and right boundary width is 1. |LEXPOS| denotes the set size of all pairs of lexicons and POS tags, |clex|-|br(clex)| gets the number of middle elements of clex, lb denotes a lexicalized boundary.

The above formula encodes the second level of the backoff scheme: plex�plex-bound, where the uniform distribution over pairs of lexicons and POS tags is neglected due to its inability of disambiguation. Furthermore, plex-bound removes the lexicalization from lexicalized boundary by describing the generation of a lexicalised boundary lb by first generating its POS tags from a Dirichlet distribution, then generating its lexicons from a uniform distribution over vocabulary V:

where pb denotes a boundary representation without lexicalization, unlex is the function removing the lexicalization and leaving only the POS tags. Thus, the third level of the back-off scheme is constructed: plexbound�Dirichlet, where the Dirichlet is over POS boundary. The uniform distribution is neglected here again.

Overall, the L-HSS encodes the hierarchical back-off scheme: ppredictive�plex�plex-bound�Dirichlet. The second row of table 1 illustrates an example of the L-HSS.

N-gram Based Hierarchical Smoothing Scheme (NBHSS)

Inspired by language modeling, NB-HSS performs smoothing in an n-gram Markov way. Take a tree span constituent Òt1 t2 t3Ó for example. Each ti is a POS tag. If we use tri-gram computation,

where <s> and </s> denote the start and end of a constituent, respectively. The probability of a constituent is smoothed by the product of probabilities of the component POS tags given their preceding tags and the constituentÕs span type (tree span in the above example). The hierarchical PYP [Teh, 2006a,b] is applied in NB-HSS for modeling ngrams. The third row of table 1 illustrates the NB-HSS for the tri-gram p(t3|t2, t1, true).

3.3 MCMC Sampling for Inferring the Latent Bracketing Trees

The inferring of the latent bracketing trees is based on the posteriors over c, d, e, and f, which is solely determined by the priors over c, d, e, and f as presented in section 3.1. MCMC sampling directly makes use of the priors p(c), p(d), p(e), and p(f) to infer the latent bracketing trees from a raw text corpus. We apply a kind of MCMC sampling, the blocked Gibbs sampling, to perform the inference. Gibbs sampling is a widely applied approach for obtaining random samples from a probabilitic distribution. The blocked Gibbs sampling is to obtain blocks of samples simultaneously. In our case, the blocked Gibbs sampling is to simultaneously obtain sentence-level samples of tree spans and non-tree spansÕ constituents and contexts.

The routine of our blocked Gibbs sampling is similar to that applied for inducing PCFGs [Johnson et al., 2007]. It consists of the following three steps: for each sentence, 1) calculate the inside score in a bottom-up manner, 2) sample a bracketing tree in a top-down manner based on the inside score obtained in the first step, and 3) accept or reject the sampled bracketing tree based on the Metropolis-Hastings (MH) test. These three steps are repeated until a pre-defined number of sampling iterations is attained.

The computation of the inside score [Klein 2005] in the first step is based on the predictive distributions that are derived from the priors over c, d, e, and f. For constituent c and e, the predictive distribution shown in eq. (3) encodes a back-off smoothing scheme. Through using various kinds of the HSS proposed in section 3.2, c and e are smoothed in the process of MCMC sampling.

We exploit multiple sampled bracketing trees of the same raw sentence to generate the final bracketing tree. For example, given two kinds of sampled binary bracketings are obtained: <<t1 t2> t3> and <t1 <t2 t3>>, we extract the agreement and give up the disagreement. Finally we get <t1 t2 t3>. Such method breaks the binary branching limitation imposed by using the inside chart during MCMC sampling.

4 Experiments

4.1 Experimental Setting

Experiments were carried out on English, Chinese, and German. Apart from some grammar induction works that include the test sentences into the training set, we adopted the experimental setting that keeps the evaluation sets blind to the models during training [Cohen et al., 2008; Headden III et al., 2009; Spitkovsky et al., 2010; Ponvert et al., 2011]. For English (WSJ) [Marcus et al., 1999], sections 00-22 was used for training, section 23 for testing and section 24 for development. For Chinese (CTB) [Palmer et al., 2006], the data split of Duan et al. [2007] was adopted. For German (NEGRA) [Krenn et al., 1998], the first 18602 sentences were used for training, the last 1000 sentences were used for development, the penultimate 1000 sentences were used for testing.

Evaluation metrics (Klein, 2005) are bracketsÕ Unlabeled Precision (UP), Unlabeled Recall (UR), and the unlabeled fscore F1, which is the harmonic mean of UP and UR: F1=2*UP*UR/(UP+UR). Brackets spanning one word, multiplicity of brackets are ignored in the evaluation.

We re-implemented the original CCM as the baseline. We used a tool implementing the seating arrangements in the restaurant of the PYP [Blunsom et al., 2009] à .

Same F1 score (71.9) to the original CCM using the same data.

We set burn-in as 20, and ran 200 iterations of blocked Gibbs sampling in all of our experiments.

4.2 Initialization

We build the initialization procedure based on a splitting process [Klein and Manning, 2002]. Given k terminals, we choose a split point at random, then recursively build trees on each side of the split point. c, d, e, and f are initialized according to these bracketing trees.

4.3 Hyper-parameters

There are two categories of hyper-parameters in our work: one category is the discount parameter ax and the strength parameter bx of all the proposed PYP distributions, the other category is � of all the proposed Dirichlet priors.

The values of ax and bx are automatically estimated by being sampled from their posterior distribution. Vague priors are applied: ax ~ Beta(1, 1), bx ~ Gamma(1, 1). A slice sampler ¤ [Neal, 2003] is applied for this sampling. In the NB-HSS, restaurants of the same history length share the same ax and bx, special computation of the posterior over ax and bx is adopted (Teh, 2006a).

For the Dirichlet prior, the parameter � is divided into two categories: �t for tree span, and �nt for non-tree span. They are tuned on the development sets.

In addition, boundary width used in the CB-HSS and the L-HSS also needs tuning. We set left/right boundary width as two/one for both English and Chinese, while set left/right boundary width as one/four for German.

4.4 Phrasal Punctuations

Punctuations are usually ignored in the grammar induction research, while some of them provide informative phrase boundaries within a sentence. We use the punctuation set shown in table 2 as phrasal punctuations for indicating phrase boundaries [Seginer, 2007; Ponvert et al., 2011]. Any tree span except the entire sentence must not cover a phrasal punctuation. Such constraint reduces the search space and bracketing errors.

4.5 Evaluation

The proposed constituent smoothing methods were evaluated on sentences of at most 10 words after the removal of punctuations and null elements in the three treebanks [Klein and Manning, 2002]. Table 3 shows the evaluation results of the three languages.

à http://staffwww.dcs.shef.ac.uk/people/T.Cohn/restaurant.tar.gz. This tool was originally developed for Chinese Restaurant Process (CRP). We modified it for the PYP applications.

¤ We made use of the slice sampler included in Mark JohnsonÕs Adaptor Grammar implementation http://www.cog.brown.edu/÷mj/ Software.htm

The performance of the baseline, the original CCM (denoted by OriCCM), is reported in the first row of table 3. The suffix punc stands for using the phrasal punctuation constraint. Clearly, the phrasal punctuation constraint is helpful when comparing the first two rows of table 3. Hence, we conducted experiments on all kinds of our proposed HSS, shown in the middle part of table 3, based on using the phrasal punctuation constraint.

The L-HSS attains the best performance among all kinds of HSS. The CB-HSS performs slightly worse than the LHSS. Both the L-HSS and the CB-HSS significantly improve the performance of the OriCCMpunc, while the NBHSS is not effective for improving the performance, and harms the performance on Chinese and German data. The effectiveness of the L-HSS and the CB-HSS comes from the constituent smoothing on long constituents. Figure 2 shows F1 scores evaluated on short brackets and long brackets. We set brackets spanning no more than 3 words as short brackets, and set brackets spanning more than 3 words and less than 8 words as long brackets. We omit longer brackets in this evaluation because most of them span whole sentences.

Figure 2 shows that the L-HSS and the CB-HSS perform significantly better than the OriCCMpunc on long brackets, which also benefits the performance on short brackets because that, for brackets containing both long brackets and short brackets, correct long brackets also indicate correct short brackets. If long brackets, which is hard to be identified, are wrongly identified, short brackets will be influenced.

Comparison to other bracketing induction systems: The bottom part of table 3 shows the performances of other grammar induction systems. CCL [Seginer, 2007] is an incremental parsing algorithm using common cover links, which is a special representation of syntactic structures. PRLG [Ponvert et al., 2011] performs grammar induction via cascaded induction of chunks, and the induced chunks constitute a bracketing tree. These two methods do not use POS tags. They induce bracketing tree over raw text words. Their best performances are comparable to the original CCM, but when they induce bracketing tree over POS tags, they perform badly, indicating that POS tags are too coarsegrained for them.

Both CCL and PRLG use the phrasal punctuation constraint, while U-DOP* [Bod, 2007] does not. U-DOP* is an efficient all sub-tree method for grammar induction. It decomposes a tree into sub-trees (constrained to be binary branching), which is different to common methods that decompose a tree into context free grammar rules. But UDOP* is not strictly comparable to our system and other grammar induction systems because the evaluation sets used by U-DOP* is binarized [Bod, 2007; Zhang and Zhao, 2011], while other systems including ours use the original evaluation sets, which contain tree structures with multiple branches. In addition, U-DOP* performance on Chinese is not comparable because U-DOP* used the treebank of CTB3, smaller than our used CTB5.

5 Conclusion

This paper proposes a Bayesian method for constituent smoothing in the CCM, which faces data sparse problem caused by the too straightforward computation of constituentsÕ probabilities. The PYP prior is applied in the proposed Bayesian method. The PYP prior functions as a back-off smoothing method through using a hierarchical smoothing scheme (HSS). Various kinds of HSS are proposed. Experiments show that, two kinds of HSS backing-off to boundaries are effective for smoothing long constituents, resulting in significant improvements over the original CCM. They attain or significantly improve the state-of-the-art performance of the bracketing induction evaluated on treebanks of English, Chinese, and German, while another kind of HSS based on commonly used n-gram Markovization on sequences is not effective for improving the performance of the original CCM.

Acknowledgments

This work was supported by the Natural Sciences Foundation of China under grant No. 61273319, and grant No. 61203314. Thanks for the helpful advices of anonymous reviewers.