Variational Bayesian Grammar Induction
for Natural Language
Kenichi Kurihara and Taisuke Sato
Tokyo Institute of Technology, Tokyo, Japan,{kurihara,sato}@mi.cs.titech.ac.jp

Abstract. This paper presents a new grammar induction algorithm forprobabilistic context-free grammars (PCFGs). There is an approach to
PCFG induction that is based on parameter estimation. Following thisapproach, we apply the variational Bayes to PCFGs. The variational
Bayes (VB) is an approximation of Bayesian learning. It has been empirically shown that VB is less likely to cause overfitting. Moreover, thefree energy of VB has been successfully used in model selection. Ouralgorithm can be seen as a generalization of PCFG induction algorithms
proposed before. In the experiments, we empirically show that induced
grammars achieve better parsing results than those of other PCFG induction algorithms. Based on the better parsing results, we give examplesof recursive grammatical structures found by the proposed algorithm.

1

Introduction

Grammar induction is one of the most challenging tasks in natural language
processing as Chomsky’s “the poverty of the stimulus” says. Nonetheless, applications have already been proposed. For example, van Zaanen [18] applied grammar induction to build treebanks. Bockhorst and Craven [3] improved models of
RNA sequences using grammar induction.
There is one practical approach to induce context-free grammars in natural language processing, which exploits parameter estimation of probabilistic
context-free grammars (PCFGs) [13, 15, 4, 7]. Although this approach is not
optimal, the empirical results showed good performance, e.g. over 90 % bracketing accuracy on the Wall Street Journal [15, 7]. They also utilize bracketed
sentences. Brackets explicitly indicate the boundaries of constituents. One may
criticize using brackets because making brackets have been expensive in terms oftime and cost. However, unsupervised induction algorithms have been proposed
to annotate brackets [8, 9].
This paper presents a variational Bayesian PCFG induction algorithm. Parameterestimation-based induction has mainly two procedures. One is to estimate parameters, and the other is to choose a better grammatical structure based on acriterion. In previous work, parameter estimation is done with the Inside-Outsidealgorithm [2], which is an EM algorithm for PCFGs, and grammars are chosen
by an approximate Bayesian posterior probability [16, 4]. Our algorithm can

2

be seen as a Bayesian extension of parameter-estimation-based grammar induction. Moreover, our criterion to choose a grammar generalizes the approximate
Bayesian posterior.
We experimentally show that our algorithm achieves better parsing results
than other PCFG induction algorithms. One may be afraid that rule-based grammars do not parse some sentences due to the lack of rules. We propose an engineering approach to achieve 100% parsing coverage based on semi-supervised
clustering that mixes labeled and unlabeled data [19]. As the better parsing results supports that induced grammars are well-organized, we give the examplesof grammatically meaningful structures in induced grammars.

2

Parameter-Estimation-Based Grammar Induction

Since Lari and Young [11] empirically showed the possibility of statistical induction of PCFGs using the Inside-Outside algorithm [2], parameter-estimationbased grammar induction has received a great deal of attention. Largely speaking, there are two main issues. One is eﬃciency, and the other is a criterion tochoose a grammatical structure.
In terms of eﬃciency, Pereira and Schabes [13] extended the Inside-Outsidealgorithm to take advantage of constituent bracketing information in a training
corpus. Brackets help the algorithm improve parameter estimation and eﬃciency.
While Pereira and Schabes [13] ﬁxed the number of non-terminals, an incremental grammar induction algorithm has been proposed for more eﬃciency [7].
Grammar induction can be seen as a search problem whose search spaceis possible grammars. From this viewpoint, a criterion to choose a grammaticalstructure plays a critical role. Stolcke and Omohundro [16], Chen [4] use Bayesianposterior probabilities as a criterion where the posterior is approximated by
Viterbi parses. This approximation is a special case of the variational Bayes.
Our algorithm exploits the variational Bayes. Therefore, our algorithm is a
Bayesian extension of an eﬃcient algorithm proposed by Hogenhout and Matsumoto [7] and the generalization of Bayesian induction studied by Stolcke andOmohundro [16], Chen [4].

3Variational Bayesian Learning

The variational Bayes (VB) [1, 6] has succeeded in many applications [12, 17].
It is empirically shown that VB is less likely to cause overﬁtting than the EM
algorithm, and the free energy calculated by VB can be exploited as a criterionof model selection1 .
1

The minimum description length (MDL) and Bayesian information criterion (BIC)
are also often used as criteria for model selection. However, they are not proper to
non-identifiable probabilistic models, s.t. hidden Markov models, maximum entropy
models, PCFGs, etc., due to their singular Fisher information matrices. Although
VB is still an approximation of true Bayesian learning, its free energy is free fromthis problem.

3

Let X = (x1 , ..., xN ), Y = (y1 , ..., yN ) and θ be observed data, hidden variables and the set of parameters, respectively. VB estimates the variational posterior distribution q(θ, Y ) which approximates the true posterior distributionp(θ, Y |X) whereas the EM algorithm conducts the point estimation of parameters. The objective function of q(θ, Y ) is free energy F , which is deﬁned as an
upper bound of a negative log likelihood,− log p(X) = − logdθ q(θ, Y )

Y

≤−


Y

dθ q(θ, Y ) log

p(X, θ, Y )q(θ, Y )p(X, θ, Y )≡ F(X).
q(θ, Y )(1)

It is easy to see that the diﬀerence between the free energy and the negative
log marginal likelihood2 is KL-divergence between the posterior q(θ, Y ) and thetrue posterior p(θ, Y |X),
F (X) + log p(X) = KL(q(θ, Y )||p(θ, Y |X)).

(2)

Since minimizing the free energy leads to minimizing the distance betweenq(θ, Y ) and p(θ, Y |X), the optimal q(θ, Y ) as an approximation of p(θ, Y |X)
is given at the minimum free energy.
Assuming a factorization, q(θ, Y ) = q(θ)q(Y ), we ﬁnd the following equations
by taking variation of the free energy with respect to q(θ, Y ) and setting to zero.
q(θ) ∝ exp E[log p(X, Y, θ)]q(Y ) ,q(Y ) ∝ exp E[log p(X, Y, θ)]q(θ) ,

(3)
(4)


where E[f (x)]q(x) = dxf (x)q(x). The optimal q(θ, Y ) is iteratively estimatedby updating q(θ) and q(Y ) alternately. Notethat if we give an
 constraints on,q(θ) = δ(θ, θ∗ ) where θ ∗ = arg maxθ exp E[log p(X, Y, θ)]q(Y ) , the above algorithm will be the EM algorithm. Therefore, the EM algorithm is a special caseof VB.
Next, we explain the important property of the free energy, capability ofmodel selection. Let’s assume that we have many models which can describe
probabilistic events. What we want to do here is to choose the most likely model.
In the Bayesian approach, people choose one which maximizes a marginal likelihood, p(X). In VB, we choose one which minimizes the free energy, which is anupper bound of the negative log marginal likelihood, Eqn.1.
2

When a probabilistic
R model gives event x with probability p(x|θ), the marginal
likelihood is p(x) = dθp(x|θ)p(θ).

44Proposed Algorithm

4.1

Variational Bayes for PCFGs

In our previous work, we proposed a VB algorithm for PCFGs, and empirically showed that VB is less likely to cause overﬁtting than the Inside-Outsidealgorithm[10]. In this section, we brieﬂy explain the VB for PCFGs, then derive
the free energy as a criterion to search for a grammatical structure.
Let G = (VN , VT , R, S, θ) be a PCFG where VN , VT , R and θ are the setsof non-terminals, terminals, derivation rules and parameters, respectively, andS denotes the start symbol. Assuming the prior of parameters to be a productof Dirichlet distributions, the learning algorithm estimates the hyperparametersof the posterior. Let u = {ur |r ∈ R} be the hyperparameters of the prior. The
hyperparameters of the posterior are the converged values of u(k) (k = 0, 1, ...)
deﬁned as,u(0) = uu(k+1)= ur +
r

N






(5)
(k)

c(r;r)π (r) (k) c(r;r  ) c(r; r)
π (r)

r∈R



n=1 r∈Φ(xn ) r ∈Φ(xn )r∈R





(6)





(k)
(k)
π (k) (A → α) = exp ψ(uA→α ) − ψ uA→α  ,α;A→α∈R(7)

where Φ(xn ) is the set of all the derivations of sentence xn , c(r; r) is the numberof occurrences of derivation rule r in derivation r and ψ(·) is the digammafunction3 . The computational complexity of updating k is equal to that of one
iteration of the Inside-Outside algorithm, which is O(N maxn (|xn |)3 ) where |xn |is the length of sentence xn .
As we discussed in section 3, the free energy can be a criterion for model
selection. Here, we derive the free energy of PCFGs as a criterion to choose agrammar,

F(X, G) = −

N
X

2
log 4

n=1

−

X
r∈R

X

Y

3
π(r)c(r;r) 5 +r∈Φ(xn ) r∈R

log

X

Γ
log

A∈VN

Γ

“P

”

“P

”

∗
α;A→α∈R uA→α
α;A→α∈R uA→αX
X
Γ (u∗r )(u∗A→α − uA→α ) log π(A → α),+Γ (ur ) A∈V α;A→α∈R(8)N

where ur and u∗r are the hyperparameters of the prior and the posterior of ruler, respectively. Although the ﬁrst term of Eqn.8 is the most expensive, it can be
3∂
The digamma function is defined as ψ(x) = ∂xlog Γ (x).

598
S→ A B >
>
>
8
>
9
>
>
>
=
< A→ A B >< S→ A A =merging
A→ a
A→ A A
→
>
>
:
;
>
>
B
→
B
B
A→ a
>
>
>
>
;
:
B→ a

9
8
S → A1 B >
>
>
>
>
>
> S → A2 B >
>
>
>
>
>
>
>
>
8
9
A1
→
A1
B
>
>
>
>
S→
A
B
>
>
>
>
>
>
>
>
A1
→
A2
B
=
<
<
=
A→ A B splitting
A1→ a
→
A→ a
>
>
>
>
>
>
>
>
>
:
;
>
> A2→ A1 B >
B→ a
>
>
>
A2→ A2 B >
>
>
>
>
>
>
>
>
>
>
A2→ a
>
>
;
:
B→a

Fig. 1. The examples of merging and splitting. The left figure is merging, and the rightis splitting.

computed eﬃciently by dynamic programming just as the Inside-Outside algorithm. Therefore, the computational complexity of Eqn.8 is O(N maxn (|xn |)3 ).
Note that the free energy is reduced to the approximate posterior which
Stolcke and Omohundro [16] and Chen [4] used, provided that q(θ) = δ(θ, θ∗ )where θ∗ = arg maxθ p(θ|X) , and the Viterbi approximation is taken. Therefore,
their approximate posterior is a special case of the free energy, Eqn.8.
In the following section, we will show three procedures to search for a more
likely grammar in the sense of this free energy.
4.2

Grammar Induction Algorithm

Grammar induction can be seen as a search problem whose search space is possible grammars. Several heuristics to search for a grammar have been proposed[4, 7, 3].
Our grammar induction algorithm has three procedures to search for a better
grammar, which are merging non-terminals, splitting a non-terminal and deletionof a derivation rule. Merging was studied in [16], and split was proposed in [7].
Every time applying one of these procedures, we calculate the free energy, thenwe accept the modiﬁed grammar if the free energy is decreased.
Merging non-terminals generalizes a grammar, and Splitting a non-terminal
specializes a grammar. Figure.1 is an example. The left hand side ﬁgure shows
merging non-terminal A and B to A, and the right hand side shows splitting
non-terminal A into A1 and A2.
The number of pairs of non-terminals to be merged is 12 (|VN | − 1)|VN |. Since
it is not tractable to try all the pairs, we restrict the number of candidates to bemerged. The measure to choose candidates is the cosine between the parameter
vectors of two non-terminals,
T

cos(A, B) =θ̂A θ̂ B||θ̂A || ||θ̂ B ||

,

(9)

6

where θ̂A is a parameter vector consisting of all available rules whose left handside is A. Letting θ(A → α) be the parameter of rule A → α, θ̂A becomes4θ̂A = (θ̂(A → α), θ̂(A → β), ...)Tdθ q(θ)θ(A → α)
θ̂(A → α) =0

(10)
if A → α ∈ Rotherwise.

(11)

The larger cos(A, B) suggests that the roles of non-terminals A and B are closer.
We also restrict the number of candidates to be split based on #VN (·),
u∗A→α − uA→α .
(12)#VN (A) =α;A→α∈R

Since #VN (A) is the expected number of occurrences of non-terminal A in observed sentences, non-terminal A which has large #VN (A) may have overloaded
syntactic roles.
We make a grammar compact by deleting redundant derivation rules. The
candidates to be deleted are chosen based on #R (·),#R (r) = u∗r − ur .

(13)

The less #R (r) is, the fewer derivation rule r is used.
The input of our algorithm is an initial grammar and hyperparameters of theprior, u. Although they are arbitrary, in the experiments, we use initial grammar
G = (VN , VT , R, S) where VN = {S}, VT = {terminals in a training corpus} andR = {S → SS} ∪ {S → a|a ∈ VT }.
Finally, we summarize our grammar induction algorithm in Fig.2. Csplit andCmerge in step 4 and 6 are the maximum number of trials of merging and splitting, respectively. Although the total computational complexity depends on thenumber of iteration, the complexity in one iteration is equal to O(N maxn (|xn |)3 )as we see in section 4.1.

5

Experiments: Parsing Results

We conducted parsing experiments. First, we compared our algorithm withother grammar induction algorithms. We also conducted an experiment of semisupervised induction, that achieved 100% parsing coverage.
In every experiment, the Wall Street Journal (WSJ) in Penn Treebank isused for training and test. Training and test corpora consist of part-of-speech(POS) tag sequences. We ﬁx the hyperparameter of the prior, ur , to 1.0 for all
derivation rule r ∈ R. This hyperparameter is known as an uninformative prior.
4

To evaluate the cosine of any two non-terminals, the dimensionality of θ̂ A must be thesame for any non-terminal A. Therefore, θ̂ A consists of any possible rules in Chomsky
normal form regardless of their existence in R. Therefore, the dimensionality of θ̂ A
is |VT | + |VN |2 for all A.

7

1. Input: an initial grammar and the hyperparameters, u, of the prior.
2. Estimate hyperparameters u∗ of posteriors.
3. Sort non-terminals in descending order of #VN (·).
4. for i in 1...Csplit(a) Split the ith candidate.
(b) Estimate hyperparameters u∗ of posteriors.
(c) Delete derivation rules while the free energy decreases.
(d) If the free energy is smaller than that in step 4a, accept the grammar, and go
to step 3.
5. Sort pairs of non-terminals in descending order of their cosines.
6. for i in 1...Cmerge(a) Merge the ith candidate.
(b) Estimate hyperparameters u∗ of posteriors.
(c) Delete derivation rules while the free energy decreases.
(d) If the free energy is smaller than that in step 6a, accept the grammar, and go
to step 3.
7. Output: an induced grammar.

Fig. 2. Grammar Induction Algorithm

Since our algorithm belongs to Bayesian learning, the most likely parse, r ∗ ,is given by summing out parameters,r ∗ = arg max = dθ p(r, x|θ)q(θ|u∗ ).
(14)r∈Φ(x)

Note that it is impossible to apply Viterbi-style parsing to Eqn.14. We therefore
exploit reranking [5]. First, 10 Viterbi parses with θ̂ are collected, then the most
likely derivation is chosen by calculating Eqn.14 of each derivation.
5.1

Comparison with Other Grammar Induction

We compared our algorithm with Schabes et al. [15] and Hogenhout and Matsumoto [7]. We followed their experimental setting. The training and test corpora
are subsets of WSJ. The training corpus had 1,000 sentences of 0-15 words. Test
were done on diﬀerent sentence length, 0-10, 0-15, 10-19 and 20-30 words. Eachtest corpus had 250 sentences5 . We conducted these experiments ﬁve times.
5

Schabes et al. used 1042 sentences of 0-15 words for training, and 84 sentences fortest. Hogenhout and Matsumoto used 1000 sentences for training and 100 sentences
for test. Hogenhout and Matsumoto used 31 POS tags after merging some rare POS
tags for larger parsing coverage while Penn Treebank has 46 POS tags. In experiment“Hogenhout & Matsumoto (15)” and “Hogenhout & Matsumoto (18)” in Table 1,
the training corpus contained sentences of 0-15 and 0-20 words, respectively.

8bracketing accuracy
0-10 0-15 10-19 20-30
98.1 95.9 93.7 89.4
Hogenhout & Matsumoto (15) 92.0 91.7 83.8 72.0
Hogenhout & Matsumoto (18) 94.1 91.5 86.9 81.8
Schabes et al.
94.4 90.2 82.5 71.5
Right Linear
76 70 63
50
Treebank grammar
46 31 25
N/A
Table 1. Comparison of bracketing accuracies with other methods on various sentence
lengths.
#wordsproposed algorithm

Table 1 compares the results. “Hogenhout & Matsumoto (15)” and “Hogenhout & Matsumoto (18)” are induced grammars which have 15 and 18 nonterminals, respectively. The results are taken from [7]. “Schabes et al.”, “Right
Linear” and “Treebank grammar” mean Schabes’s grammar induction, a systematic right linear branching except for the last punctuation and a grammar
extracted from tree labels in WSJ, respectively. These results are from Schabes
et al. [15]. Bracketing accuracy in Table 1 is the ration of predicted brackets
which is consistent with correct brackets [13].
As Table 1 shows, the proposed algorithm achieved the best score in every
test corpus. The parsing coverage of our method was over 99% (see Table 2).
Induced grammars had average 22.4 non-terminals and 509.8 derivation rules.
The algorithm converged in less than one hour on Pentium 4 3.8 GHz (SuSE
10.0).
One possible reason why our parsing results were better than others might
be because the number of terminals in our induced grammars was larger thanthat of others. The larger number of non-terminals could capture language more
appropriately. Hogenhout and Matsumoto [7] ﬁxed the number of non-terminals
to 15 or 18. Although our algorithm stops when the free energy converged, theiralgorithm does not have any criteria to stop. Moreover, it is straightforward tocombine our algorithm with search algorithms, e.g. beam search, but it is unclear
for their algorithm due to lack of the criteria of model selection. Although we did
not compare our free energy with an approximate Bayesian posterior [16, 4], itis well known that the free energy of VB is a tighter bound to the true posterior
than their approximate posterior.
5.2

Semi-Supervised Induction as Robust Grammar Induction

In machine learning, semi-supervised learning has received considerable attention. Semi-supervised clustering [19] in grammar induction is to combine a bracketed training corpus and an unbracketed test corpus. Since the proposed algorithm accepts unbracketed sentences also, such a combined corpus leads to 100%
parsing coverage on a test corpus even when a training corpus does not have someterminals which occur in a test corpus. We conducted an experiment to show

9
#words0-10
0-15 10-19 20-30
proposed algorithm 0-CB
85.6
66.6
45.6
12.1
BA
98.1
95.9
93.7
89.4
coverage
99.8
99.4 100.0
99.6
failure 3/1250 8/1250 0/1250 5/1250
proposed algorithm 0-CB
86.0
65.9
44.0
11.4
+ semi-supervised(100) (87.5) N/A (0.0)
BA
98.2
95.8
93.6
89.6
(100) (98.1) N/A (79.5)
coverage 100.0 100.0 100.0 100.0
failure 0/1250 0/1250 0/1250 0/1250
Table 2. Grammar Induction and Semi-Supervised Induction.

how semi-supervised induction works. We used the same training and test corpora as Section 5.1. Our semi-supervised induction has two steps. First, we run
the proposed algorithm only on a training corpus, then we add the following
derivation rules to make the induced grammar redundant,{S → SS} ∪ {S → a|a ∈ {terminals in a test corpus}}where S is a start symbol. After that, we run the algorithm on training andtest corpora. Table 2 shows the results. “failure” is the number of sentences
which were not parsed by the induced grammar. In semi-supervised part, digits
in parentheses show the results of the failed sentences in bracketed induction6 .
The digits in parentheses are comparable with the average of all. This demonstrates grammars learned by semi-supervised induction work well also on sentences failed before. Although semi-supervised induction does not improve zerocrossing brackets (0-CB)7 and bracketing accuracy (BA), this would be because
failed sentences are few, i.e. 3, 8, 0 and 5 sentences in 0-10, 0-15, 10-19 and 20-30
words test corpora, respectively.
We have proposed an approach to combine training and test corpora. However, this might be untractable when test corpora are very large. On-line learning
is another approach. It is straightforward to apply on-line learning based on thevariational Bayes [14]. This would turn the proposed algorithm into an eﬃcientincremental semi-supervised induction algorithm.

6

Discussion: Induced Grammars

So far, we have shown the parsing results of our grammar induction algorithm.
However, we believe strongly that grammar induction is not only for obtaining
a parser but also can be a tool for grammatical structure understanding.
6

The corpus of length 10-19 does not have parentheses because the coverage wasoriginally 100%.
70-CB is the ratio of sentences whose brackets are completely consistent with correct
brackets.

10
S
VP

Treebank
PP-CLR

NP-SBJNP

I (PRP) believe (VBP) in (IN) the (DT) system (NN) . (.)
12

6

4

0

3

11

15
9
5
7

Induced Grammar

S

Fig. 3. A parse tree from Treebank and a parse tree predicted by an induced grammar.

Fig.3 is an illustrative example of a parse tree predicted by an induced grammar. Fig.4 lists a subset of the induced grammar used in Fig.3. In this example,
non-terminal 15 derives “DT JJ∗ NN” where DT is determiner, JJ is adjective
and NN is noun. Therefore, non-terminal 15 can be interpreted as a noun phrase(NP). We can also ﬁnd that start symbol S derives the following grammaticalstructure (see Appendix A),
S ⇒ (PRP|DT JJ∗ NN) (VBD|VBZ|VBP)


 


subjectverb∗∗
 NN IN DT JJ
 NN .
DT JJ
noun-phrase

noun-phrase

where (·|·), ∗, ? are the usual notations of regular expressions, PRP is personalpronoun, VBD is verb (past tense), VBZ is verb (third person singular present),
VBP is verb (non-third person singular present) and IN is preposition or subordinating conjunction. Clearly, this structure captures typical English sentences.
The above discussion is based on selected examples, and nonsense structures
can also be found due to redundant derivation rules. Actually, it is not trivial
how to ﬁnd meaningful grammatical structures. But, the parsing results support
that induced grammars have meaningful structures.

7

Conclusion

We have proposed a variational Bayesian PCFG induction algorithm in the context of parameter-estimation-based grammar induction. Experimental results
showed that the proposed algorithm induced more well-structured grammars interms of parsing results than other PCFG induction algorithms. We also showedthat induced PCFGs in fact had meaningful recursive structures.
As future work, we may need to exploit a dependency model to improveparsing results. Since our algorithm is greedy, we might combine our algorithm

11left hand side θ̂ derivation rule
non-terminal
15
0.28 15 → 0 3
.
.
.

0

0.62 0 → DT
0.11 0 → 0 10
.
.
.

10

0.47 10 → JJ
.
.
.

3

0.81 3 → NN.
.
.

Fig. 4. The induced grammar in Fig.3. Using shown derivation rules, non-terminal 15
derives “DT JJ∗ NN”, where DT is determiner, JJ is adjective and NN is noun.

with a search algorithm such as beam search. Although we constrained ourselves
to PCFGs, we should explore other types of grammars as well. Moreover, how to
ﬁnd meaningful structures from induced grammars remains to be investigated.

Acknowledgments
Special thanks to Dr. Kameya for helpful comments. This research was fundedby the 21st Century COE Program “Framework for Systematization and Application of Large-scale Knowledge Resources.”

Bibliography[1] Hagai Attias. A variational Bayesian framework for graphical models. In Advancesin Neural Information Processing Systems, volume 12, 2000.
[2] J. K. Baker. Trainable grammars for speech recognition. In D. H. Klatt and J. J.
Wolf, editors, Speech Communication Papers for the 97th Meeting of the AcousticalSociety of America, pages 547–550, 1979.
[3] Joseph Bockhorst and Mark Craven. Refining the structure of a stochastic contextfree grammar. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, 2001.
[4] Stanley F. Chen. Bayesian grammar induction for language modeling. In Meetingof the Association for Computational Linguistics, pages 228–235, 1995.
[5] Michael Collins. Discriminative reranking for natural language parsing. In Proc.
17th International Conf. on Machine Learning, pages 175–182, 2000.
[6] Zoubin Ghahramani and Matthew J. Beal. Variational inference for Bayesian mixtures of factor analysers. In Advances in Neural Information Processing Systems,
volume 12, 2000.
[7] Wide R. Hogenhout and Yuji Matsumoto. A fast method for statistical grammar
induction. Natural Language Engineering, 4(3):191–209, 1998.
[8] Dan Klein and Christopher D. Manning. A generative constituent-context model
for improved grammar induction. In Proceedings of the 40th Annual Meeting of
the ACL, 2002.
[9] Dan Klein and Christopher D. Manning. Corpus-based induction of syntactic
structure: Models of dependency and constituency. In Proceedings of the 42nd
Annual Meeting of the ACL, 2004.
[10] Kenichi Kurihara and Taisuke Sato. An application of the variational Bayesian
approach to probabilistic context-free grammars, 2004. IJCNLP-04 Workshop
beyond shallow analyses.
[11] Karim Lari and Steve Young. The estimation of stochastic context-free grammars
using the inside-outside algorithm. Computer Speech and Language, 4:35–56, 1990.
[12] David J.C. MacKay. em ensemble learning for hidden markov models. Technicalreport, 1997.
[13] Fernando C. N. Pereira and Yves Schabes. Inside-outside reestimation from partially bracketed corpora. In Meeting of the Association for Computational Linguistics, pages 128–135, 1992.
[14] Masaaki Sato. Online model selection based on the variational bayes. In NeuralComputation, volume 13, pages 1649–1681, 2001.
[15] Yves Schabes, Michal Roth, and Randy Osborne. Parsing the wall street journal
with the inside-outside algorithm. In ACL, pages 341–347, 1993.
[16] Andreas Stolcke and Stephen Omohundro. Inducing probabilistic grammars by
Bayesian model merging. In International Conference on Grammatical Inference,
1994.
[17] Naonori Ueda and Zoubin Ghahramani. Bayesian model search for mixture models
based on optimizing variational bounds. Neural Networks, 15(10):1223–1241, 2002.
[18] Menno van Zaanen. Abl: Alighment-based learning. In COLING, volume 18,
pages 961–967, 2000.

13
θ̂ derivation rule0.80 S → 7 11
0.64 7 → 12 50.23 12 → PRP
0.19 12 → 0 3
0.62 0 → DT
0.11 0 → 0 10
0.47 10 → JJ
0.81 3 → NN
0.79 5 → 6 9
0.30 6 → VBD
0.26 6 → VBZ
0.15 6 → VBP
0.26 9 → 8 1
0.24 8 → 0 3
0.48 1 → 4 15
0.55 4 → IN
0.28 15 → 0 3
0.85 11 → .
Fig. 5. A subset of the induced grammar in Fig.3.

[19] Kiri Wagsta, Claire Cardie, Seth Rogers, and Stefan Schroedl. Constrained kmeans clustering with background knowledge. In Proceedings of 18th International
Conference on Machine Learning, pages 577–584, 2001.

AppendixA

A Grammatical Structure in an Induced Grammar

Fig.5 lists a subset of the induced grammar used in Fig.3. These derivation rules
leads a grammatical structure,S ⇒ (PRP|DT JJ∗ NN) (VBD|VBZ|VBP)


 


subjectverb∗∗
 NN IN DT JJ
 NN .
DT JJ
noun-phrase

noun-phrase

where PRP is personal noun, DT is determiner, JJ is adjective, NN is noun,
VBD is verb (past tense), VBZ is verb (third person singular present), VBP
is (non-third person singular present) and IN is preposition or subordinating
conjunction. “DT JJ∗ NN” can be interpreted as a noun phrase. Therefore,(PRP|DT JJ∗ NN) is also a noun phrase. In this example, (PRP|DT JJ∗ NN)
makes the subject of the sentence.