Learning Common Grammar from Multilingual Corpus
Tomoharu Iwata

Daichi Mochihashi
Hiroshi Sawada
NTT Communication Science Laboratories
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto, Japan{iwata,daichi,sawada}@cslab.kecl.ntt.co.jp

Abstract
We propose a corpus-based probabilistic framework to extract hidden common
syntax across languages from non-parallel
multilingual corpora in an unsupervised
fashion. For this purpose, we assume agenerative model for multilingual corpora,
where each sentence is generated from alanguage dependent probabilistic contextfree grammar (PCFG), and these PCFGs
are generated from a prior grammar thatis common across languages. We also develop a variational method for efficient inference. Experiments on a non-parallel
multilingual corpus of eleven languages
demonstrate the feasibility of the proposed
method.

1 Introduction
Languages share certain common properties (Pinker, 1994). For example, the word orderin most European languages is subject-verb-object(SVO), and some words with similar forms areused with similar meanings in different languages.
The reasons for these common properties can be
attributed to: 1) a common ancestor language,2) borrowing from nearby languages, and 3) the
innate abilities of humans (Chomsky, 1965).
We assume hidden commonalities in syntax
across languages, and try to extract a common
grammar from non-parallel multilingual corpora.
For this purpose, we propose a generative model
for multilingual grammars that is learned in an
unsupervised fashion. There are some computational models for capturing commonalities at thephoneme and word level (Oakes, 2000; BouchardCôté et al., 2008), but, as far as we know, no attempt has been made to extract commonalities insyntax level from non-parallel and non-annotatedmultilingual corpora.

In our scenario, we use probabilistic contextfree grammars (PCFGs) as our monolingual grammar model. We assume that a PCFG for eachlanguage is generated from a general model thatare common across languages, and each sentence
in multilingual corpora is generated from the language dependent PCFG. The inference of the general model as well as the multilingual PCFGs canbe performed by using a variational method for
efficiency. Our approach is based on a Bayesian
multitask learning framework (Yu et al., 2005;
Daumé III, 2009). Hierarchical Bayesian modeling provides a natural way of obtaining a joint regularization for individual models by assuming thatthe model parameters are drawn from a common
prior distribution (Yu et al., 2005).

2 Related work
The unsupervised grammar induction task has
been extensively studied (Carroll and Charniak,
1992; Stolcke and Omohundro, 1994; Klein andManning, 2002; Klein and Manning, 2004; Lianget al., 2007). Recently, models have been proposed that outperform PCFG in the grammar induction task (Klein and Manning, 2002; Klein andManning, 2004). We used PCFG as a first stepfor capturing commonalities in syntax across languages because of its simplicity. The proposed
framework can be used for probabilistic grammar
models other than PCFG.
Grammar induction using bilingual parallel corpora has been studied mainly in machine translation research (Wu, 1997; Melamed, 2003; Eisner,
2003; Chiang, 2005; Blunsom et al., 2009; Snyder et al., 2009). These methods require sentencealigned parallel data, which can be costly to obtainand difficult to scale to many languages. On theother hand, our model does not require sentences
to be aligned. Moreover, since the complexity of
our model increases linearly with the number oflanguages, our model is easily applicable to cor-pora of more than two languages, as we will show
in the experiments. To our knowledge, the only
grammar induction work on non-parallel corpora
is (Cohen and Smith, 2009), but their method does
not model a common grammar, and requires priorinformation such as part-of-speech tags. In contrast, our method does not require any such priorinformation.

3

Proposed Method

z1

θ θ
a,b

αθA

θ lA

φ φ
a,b

αφA

φ lA

z2

z3

ψlA
|L|
|K|

x2

x3
|L|

αψ

Figure 1: Graphical model.

3.1 Model
Let X = {X l }l∈L be a non-parallel and nonannotated multilingual corpus, where X l is a setof sentences in language l, and L is a set of languages. The task is to learn multilingual PCFGs
G = {Gl }l∈L and a common grammar that generates these PCFGs. Here, Gl = (K, W l , Φl )represents a PCFG of language l, where K is aset of nonterminals, W l is a set of terminals, andΦl is a set of rule probabilities. Note that a set of
nonterminals K is shared among languages, but
a set of terminals W l and rule probabilities Φl
are specific to the language. For simplicity, we
consider Chomsky normal form grammars, whichhave two types of rules: emissions rewrite a nonterminal as a terminal A → w, and binary productions rewrite a nonterminal as two nonterminals A → BC, where A, B, C ∈ K and w ∈ W l .
The rule probabilities for each nonterminal
A of PCFG Gl in language l consist of: 1)
θ Al = {θlAt }t∈{0,1} , where θlA0 and θlA1 represent probabilities of choosing the emission ruleand the binary production rule, respectively, 2)
φlA = {φlABC }B,C∈K , where φlABC represents the probability of nonterminal production
A → BC, and 3) ψ lA = {ψlAw }w∈W l , whereψlAw represents the probability of terminal emission∑ A → w. Note that θlA0 + θlA1∑= 1, θlAt ≥ 0,
B,C φlABC = 1, φlABC ≥ 0,w ψlAw = 1,and ψlAw ≥ 0. In the proposed model, multinomial parameters θ lA and φlA are generated from
Dirichlet distributions that are common across languages: θlA ∼ Dir(αθA ) and φlA ∼ Dir(αφA ),since we assume that languages share a common
syntax structure. αθA and αφA represent the parameters of a common grammar. We use the Dirichletprior because it is the conjugate prior for the multinomial distribution. In summary, the proposedmodel assumes the following generative process
for a multilingual corpus,
1. For each nonterminal A ∈ K:(a) For each rule type t ∈ {0, 1}:
i. Draw common rule type parametersθαAt∼ Gam(aθ , bθ )(b) For each nonterminal pair (B, C):
i. Draw common production parametersφαABC∼ Gam(aφ , bφ )2. For each language l ∈ L:(a) For each nonterminal A ∈ K:
i. Draw rule type parameters
θlA ∼ Dir(αθA )ii. Draw binary production parametersφlA ∼ Dir(αφA )iii. Draw emission parameters
ψ lA ∼ Dir(αψ )(b) For each node i in the parse tree:
i. Choose rule typetli ∼ Mult(θ lzi )ii. If tli = 0:
A. Emit terminal
xli ∼ Mult(ψ lzi )iii. Otherwise:
A. Generate children nonterminals(zlL(i) , zlR(i) ) ∼ Mult(φlzi ),where L(i) and R(i) represent the left and rightchildren of node i. Figure 1 shows a graphical model representation of the proposed model,
where the shaded and unshaded nodes indicate observed and latent variables, respectively.
3.2 Inference
The inference of the proposed model can be efficiently computed using a variational Bayesian
method. We extend the variational method tothe monolingual PCFG learning of Kurihara andSato (2004) for multilingual corpora. The goal
is to estimate posterior p(Z, Φ, α|X), where Z
is a set of parse trees, Φ = {Φl }l∈L is aset of language dependent parameters, Φl =φ{θ lA , φlA , ψ lA }A∈K , and α = {αθA , αA}A∈K
is a set of common parameters. In the variational
method, posterior p(Z, Φ, α|X) is approximatedby a tractable variational distribution q(Z, Φ, α).

We use the following variational distribution,∏∏q(Z, Φ, α) =q(αθA )q(αφA )q(z ld )
A

×

∏

l,d

q(θ lA )q(φlA )q(ψ lA ), (1)l,Awhere we assume that hyperparameters q(αθA ) andq(αφA ) are degenerated, or q(α) = δα∗ (α), andinfer them by point estimation instead of distribution estimation. We find an approximate posterior
distribution that minimizes the Kullback-Leibler
divergence from the true posterior. The variational
distribution of the parse tree of the dth sentence inlanguage l is obtained as follows,q(z ld ) ∝)C(A→BC;z ld ,l,d)
∏ (
φ
θ
πlA1
πlABC
A→BC

×

)C(A→w;z ld ,l,d)
∏ (
ψ
θ
πlA0
πlAw
, (2)

A→w

where C(r; z, l, d) is the count of rule r that occurs in the dth sentence of language l with parsetree z. The multinomial weights are calculated asfollows,
])
[
(
θ
(3)
πlAt
= exp Eq(θ lA ) log θlAt ,
(
φ
πlABC
= exp Eq(φ(ψπlAw
= exp Eq(ψ

[

])

[

])
log ψlAw .

log φlABC
lA )
lA )

,

(4)
(5)

The variational Dirichlet parameters for q(θ lA ) =Dir(γ θlA ), q(φlA ) = Dir(γ φlA ), and q(ψ lA ) =Dir(γ ψlA ), are obtained as follows,

described in (Minka, 2000). The update rule is asfollows,)( ∑ θ
θ L Ψ(
θaθ −1+αAt
θ(new)
t0 αAt0 )−Ψ(αAt )) ,αAt← θ ∑( ∑ θθ )b + l Ψ( t0 γlAt0 ) − Ψ(γlAt(9)
where L is the number of languages, and Ψ(x) =∂ log Γ(x)is the digamma function. Similarly, the∂xφcommon production parameter αABCcan be updated as follows,φ(new)

αABC ←

φaφ − 1 + αABC
LJABC
∑
,
0
φ
b + l JlABC

(10)

∑
φ
φ
where JABC = Ψ( B 0 ,C 0 αAB
0 C 0 ) − Ψ(αABC ),∑φφ
0
and JlABC= Ψ( B 0 ,C 0 γlAB
0 C 0 ) − Ψ(γlABC ).
Since factored variational distributions dependon each other, an optimal approximated posterior
can be obtained by updating parameters by (2) (10) alternatively until convergence. The updating of language dependent distributions by (2) (8) is also described in (Kurihara and Sato, 2004;
Liang et al., 2007) while the updating of common
grammar parameters by (9) and (10) is new. The
inference can be carried out efficiently using theinside-outside algorithm based on dynamic programming (Lari and Young, 1990).
After the inference, the probability of a common grammar rule A → BC is calculated byφ̂A→BC = θ̂1 φ̂ABC , where θ̂1 = α1θ /(α0θ + α1θ )∑φ
φand φ̂ABC = αABC
/ B 0 ,C 0 αAB
0 C 0 represent
the mean values of θl0 and φlABC , respectively.

4 Experimental results

We evaluated our method by employing the EuroParl corpus (Koehn, 2005). The corpus conθθq(z ld )C(A, t; z ld , l, d), (6)
γlAt
= αAt
+
sists of the proceedings of the European Parliad,z ld
ment in eleven western European languages: Dan∑φφ
γlABC = αABC +q(z ld )C(A → BC; z ld , l, d), ish (da), German (de), Greek (el), English (en),Spanish (es), Finnish (fi), French (fr), Italian (it),d,z ldDutch (nl), Portuguese (pt), and Swedish (sv), and
(7)
∑
ψ
ψ
it contains roughly 1,500,000 sentences in eachγlAw = α +q(z ld )C(A → w; z ld , l, d),language. We set the number of nonterminals at
d,z ld|K| = 20, and omitted sentences with more than(8)
ten words for tractability. We randomly sampled
where C(A, t; z, l, d) is the count of rule type t
100,000 sentences for each language, and anathat is selected in nonterminal A in the dth senlyzed them using our method. It should be noted
tence of language l with parse tree z.
θ that minthat our random samples are not sentence-aligned.
The common rule type parameter αAt
Figure 2 shows the most probable terminals ofimizes the KL divergence between the true posemission for each language and nonterminal withterior and the approximate posterior can be oba high probability of selecting the emission rule.
tained by using the fixed-point iteration method∑

2: verb and auxiliary verb (V)

5: noun (N)7: subject (SBJ)

0 → 16 11 (R → S . )0.11
16 → 7 6(S → SBJ VP) 0.06
6 → 2 12
(VP → V NP) 0.04
12 → 13 5 (NP → DT N) 0.19
15 → 17 19 (NP → NP N) 0.07
17 → 5 9(NP → N PR) 0.07
15 → 13 5 (NP → DT N) 0.06
Figure 3: Examples of inferred common grammar rules in eleven languages, and their probabilities. Hand-provided annotations have the following meanings, R: root, S: sentence, NP: nounphrase, VP: verb phrase, and others appear in Figure 2.
We named nonterminals by using grammatical categories after the inference. We can see that words
in the same grammatical category clustered acrosslanguages as well as within a language. Figure 3 shows examples of inferred common grammar rules with high probabilities. Grammar rulesthat seem to be common to European languages
have been extracted.

5 Discussion
9: preposition (PR)11: punctuation (.)

13: determiner (DT)

Figure 2: Probable terminals of emission for eachlanguage and nonterminal.

We have proposed a Bayesian hierarchical PCFG
model for capturing commonalities at the syntax
level for non-parallel multilingual corpora. Although our results have been encouraging, a number of directions remain in which we must extend
our approach. First, we need to evaluate our model
quantitatively using corpora with a greater diversity of languages. Measurement examples include
the perplexity, and machine translation score. Second, we need to improve our model. For example, we can infer the number of nonterminals
with a nonparametric Bayesian model (Liang etal., 2007), infer the model more robustly basedon a Markov chain Monte Carlo inference (Johnson et al., 2007), and use probabilistic grammar
models other than PCFGs. In our model, all themultilingual grammars are generated from a general model. We can extend it hierarchically using
the coalescent (Kingman, 1982). That model may
help to infer an evolutionary tree of languages interms of grammatical structure without the etymological information that is generally used (Grayand Atkinson, 2003). Finally, the proposed approach may help to indicate the presence of a universal grammar (Chomsky, 1965), or to find it.

References
Phil Blunsom, Trevor Cohn, and Miles Osborne. 2009.
Bayesian synchronous grammar induction. In D. Koller,
D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21,
pages 161–168.
Alexandre Bouchard-Côté, Percy Liang, Thomas Griffiths,
and Dan Klein. 2008. A probabilistic approach to language change. In J.C. Platt, D. Koller, Y. Singer, and
S. Roweis, editors, Advances in Neural Information Processing Systems 20, pages 169–176, Cambridge, MA.
MIT Press.
Glenn Carroll and Eugene Charniak. 1992. Two experiments
on learning probabilistic dependency grammars from corpora. In Working Notes of the Workshop StatisticallyBased NLP Techniques, pages 1–13. AAAI.
David Chiang. 2005. A hierarchical phrase-based model forstatistical machine translation. In ACL ’05: Proceedingsof the 43rd Annual Meeting on Association for Computational Linguistics, pages 263–270, Morristown, NJ, USA.
Association for Computational Linguistics.
Norm Chomsky. 1965. Aspects of the Theory of Syntax. MIT
Press.
Shay B. Cohen and Noah A. Smith. 2009. Shared logistic
normal distributions for soft parameter tying in unsupervised grammar induction. In NAACL ’09: Proceedings of
Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association
for Computational Linguistics, pages 74–82, Morristown,
NJ, USA. Association for Computational Linguistics.
Hal Daumé III. 2009. Bayesian multitask learning with latent hierarchies. In Proceedings of the Twenty-Fifth Annual Conference on Uncertainty in Artificial Intelligence(UAI-09), pages 135–142, Corvallis, Oregon. AUAI Press.
Jason Eisner. 2003. Learning non-isomorphic tree mappings
for machine translation. In ACL ’03: Proceedings of the
41st Annual Meeting on Association for Computational
Linguistics, pages 205–208, Morristown, NJ, USA. Association for Computational Linguistics.
Russell D. Gray and Quentin D. Atkinson. 2003. Languagetree divergence times support the Anatolian theory of
Indo-European origin.
Nature, 426(6965):435–439,
November.
Mark Johnson, Thomas Griffiths, and Sharon Goldwater.
2007. Bayesian inference for PCFGs via Markov chain
Monte Carlo. In Human Language Technologies 2007:
The Conference of the North American Chapter of the
Association for Computational Linguistics; Proceedingsof the Main Conference, pages 139–146, Rochester, New
York, April. Association for Computational Linguistics.
J. F. C. Kingman. 1982. The coalescent. Stochastic Processes and their Applications, 13:235–248.
Dan Klein and Christopher D. Manning. 2002. A generative
constituent-context model for improved grammar induction. In ACL ’02: Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, pages
128–135, Morristown, NJ, USA. Association for Computational Linguistics.

Dan Klein and Christopher D. Manning. 2004. Corpusbased induction of syntactic structure: models of dependency and constituency. In ACL ’04: Proceedings of the
42nd Annual Meeting on Association for Computational
Linguistics, page 478, Morristown, NJ, USA. Association
for Computational Linguistics.
Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Proceedings of the 10th
Machine Translation Summit, pages 79–86.
Kenichi Kurihara and Taisuke Sato. 2004. An application of the variational Bayesian approach to probabilistic
context-free grammars. In International Joint Conference
on Natural Language Processing Workshop Beyond Shallow Analysis.
K. Lari and S.J. Young. 1990. The estimation of stochastic
context-free grammars using the inside-outside algorithm.
Computer Speech and Language, 4:35–56.
Percy Liang, Slav Petrov, Michael I. Jordan, and Dan Klein.
2007. The infinite PCFG using hierarchical dirichlet processes. In EMNLP ’07: Proceedings of the Empirical
Methods on Natural Language Processing, pages 688–
697.
I. Dan Melamed. 2003. Multitext grammars and synchronous parsers. In NAACL ’03: Proceedings of the 2003
Conference of the North American Chapter of the Association for Computational Linguistics on Human Language
Technology, pages 79–86, Morristown, NJ, USA. Association for Computational Linguistics.
Thomas Minka. 2000. Estimating a Dirichlet distribution.
Technical report, M.I.T.
Michael P. Oakes. 2000. Computer estimation of vocabulary in a protolanguage from word lists in four daughter
languages. Journal of Quantitative Linguistics, 7(3):233–
243.
Steven Pinker. 1994. The Language Instinct: How the Mind
Creates Language. HarperCollins, New York.
Benjamin Snyder, Tahira Naseem, and Regina Barzilay.
2009. Unsupervised multilingual grammar induction. In
Proceedings of the Joint Conference of the 47th Annual
Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP,
pages 73–81, Suntec, Singapore, August. Association for
Computational Linguistics.
Andreas Stolcke and Stephen M. Omohundro. 1994. Inducing probabilistic grammars by Bayesian model merging. In ICGI ’94: Proceedings of the Second International
Colloquium on Grammatical Inference and Applications,pages 106–118, London, UK. Springer-Verlag.
Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Comput.
Linguist., 23(3):377–403.
Kai Yu, Volker Tresp, and Anton Schwaighofer. 2005.
Learning gaussian processes from multiple tasks. In
ICML ’05: Proceedings of the 22nd International Conference on Machine Learning, pages 1012–1019, New York,NY, USA. ACM.