An Unsupervised Parameter Estimation Algorithm
for a Generative Dependency N-gram Language Model
Chenchen Ding and Mikio Yamamoto
Department of Computer Science
University of Tsukuba
1-1-1 Tennodai, Tsukuba, 305-8573, Japan{tei@mibel.,myama@}cs.tsukuba.ac.jp
Abstract
We design a language model based on a
generative dependency structure for sentences. The parameter of the model isthe probability of a dependency N-gram,which is composed of lexical words withfour kinds of extra tags used to model thedependency relation and valence. We further propose an unsupervised expectationmaximization algorithm for parameter estimation, in which all possible dependency
structures of a sentence are considered. As
the algorithm is language-independent, it
can be used on a raw corpus from any language, without any part-of-speech annotation, tree-bank or trained parser. We conducted experiments using four languages:
English, German, Spanish and Japanese.
The results illustrate the applicability andthe properties of the proposed approach.

1

Figure 2: The constituency-based parsing (A)and the dependency-based parsing (B)1 for the
English sentence “all things pass”.
On the other hand, revealing the structure of asentence is the task of parsing, which is based on
linguistically oriented formulations and focuses on
generating the likeliest structure for a given sentence. For this purpose, there are constituencybased and dependency-based formulations (Fig.
2). The former organizes continuous word sequences in a hierarchy of small range to large
range groups with linguistically oriented labels;
the latter links words with dependency relations2 .

Introduction

Figure 3: All possible dependency structures for
the English sentence “all things pass”. (I) is the
linguistically correct structure while the originalN-gram language model handles the sentence as
if it has the structure labeled (II). We consider allthese structures in our unsupervised estimation
algorithm.
In this paper, we focus on introducing sentence
structure into language modeling. We propose
a generative dependency N-gram language modelthat integrates a generative dependency structureof a sentence into the original N-gram language
model. We prefer the dependency-based formula-

Statistical language models are a fundamental
component of speech recognition systems, machine translation systems, and so forth. Presently,
the N-gram language model is the most widelyused approach. This model focuses on sequencesof neighboring lexical words (Fig. 1), and uses theprobabilities of these sequences as model parameters. Due to the full lexicalization of the N-gram
language model, local features of word sequences
can be well modeled. However, an N-gram language model cannot capture relatively long-range
features, because it regards a sentence as a flat
string and ignores its structure.

1
For the illustrations in this paper, we use the following representation to show the dependency structure. If twoaligned words are on different levels, the upper one is thehead of the lower one; if they are on the same level, they are
siblings.
2
In general, the dependency relations can be further classified using linguistically oriented labels. However, they are
not indispensable and we do not use them in our approach.

Figure 1: The N-gram language model treats the
English sentence “all things pass” composed of(all, things) and (things, pass), for N = 2.

516
International Joint Conference on Natural Language Processing, pages 516–524,
Nagoya, Japan, 14-18 October 2013.

these approaches need a trained dependency parser
because they construct a language model based on
the decisive best structure produced by the parser.
In our approach, we utilize a generative dependency model to guarantee the constituency of alanguage model5 , but our model and algorithm canhandle arbitrary numbers of lexical words. Furthermore, our approach needs no extra parser togenerate the best structure of a sentence but, instead, takes all possible dependency structures into
consideration.

tion because it can directly model the relations between words. In the proposed model, the parameter is the probability of the dependency N-gram,which is a sequence of words along the dependency structure rather than along a flat left-to-rightstring. The proposed model is thus as fully lexical
as the original N-gram language model. We further propose an expectation-maximization (EM)algorithm for estimating the probability of arbitrary order3 dependency N-grams, by considering
all possible dependency structures4 of a sentence(Fig. 3). The proposed algorithm is unsupervised,language-independent and needs no linguistic information.

3 Generative Dependency Model
We model the marginal probability of a sentence
S over the set D of all possible
dependency struc∑tures of S, P (S) =Pd∈D (S, d). As described in Klein and Manning (2004), if we separate ∑the dependency structure
and lexicalization,∑then d∈D P (S, d) = d∈D P (d)P (S|d). The
term P (S|d) is given by a model of fully lexical
word sequences with dependency relations. However, the term P (d) is difficult to model and is usually taken to be a constant, as in Paskin (2002). To
deal with this problem, the dependency model withvalence (DMV)6 proposed by Klein and Manning(2004) introduces a special mark STOP. However,
it is necessary to distinguish two kinds of parameters, PSTOP and PCHOOSE in the bi-gram estimation, which makes it difficult to extend the approach to higher orders.
In a similar approach to that used in the DMV,
we introduce four kinds of tags to normalize the
distribution of modifier numbers (the valence) ofa head word. In this paper, we use ⟨L⟩, ⟨/L⟩, ⟨R⟩
and ⟨/R⟩ to show the start and end of the left andright modifier word sequences of a head word, respectively. The dependency structure can thus beorganized as nested word sequences. Specifically,a modifier word sequences of a head word is in
a form of M = mϕ+1
≡ m0 , m1 , · · · , mϕ+1 ,0where m0 ≡ ⟨O⟩, mϕ+1 ≡ ⟨/O⟩ (O ∈ {L, R})
and mϕ1 is a lexical ϕ-word sequence. We show
an example of the dependency structure in Fig. 4.
On the other hand, in contrast to the DMV, wetreat the tags as ordinary words in the parameter
estimation. So the parameters of our model havea uniform representation, by which our approach
can be easily extended to arbitrary high orders.

2 Related Work
The technical report by Chen and Goodman(1998) has compared various approaches to the Ngram language model and the modified KneserNey discounting proposed in it is still the stateof-the-art approach. Since the N-gram language
model only captures local lexical features, there
have been proposals to generalize the lexical Ngram by word-class (Brown et al., 1992) or tomodel long-range word co-occurrences by word
triggers (Tillmann and Ney, 1997). However,these models are unaware of the sentence structure
and basically take a sentence as a flat string.
Many approaches have been proposed forconstituency-based parsing (Collins, 1998; Klein
and Manning, 2003; Klein and Manning, 2004)
and for dependency-based parsing (Eisner, 1996;
Lee and Choi, 1997; Kudo and Matsumoto,2002; Klein and Manning, 2004; Nivre, 2008).
Presently, discriminative approaches (Kudo andMatsumoto, 2002; Nivre, 2008) are used morethan generative ones for dependency-based parsing, because a generative model is usually restricted to being bi-lexical (i.e., the components
are bi-grams of head-modifier pairs) and it is hard
to handle more lexical information.
There have been some attempts to integrate sentence structure into language modeling.
Chelba and Jelinek (2000) have proposed a constituency-based approach, but the useof language-dependent non-terminals cannot be
avoided. There are also dependency-based approaches (Stolcke et al., 1997; Gao and Suzuki,
2003; Graham and van Genabith, 2010). However,
3
4

5∑S∈L P (S) = 1 for the set L composed of all the sen-tences S in a language.
6
A generative model.

“Order” here means the number of lexical words (N ).
Only projective dependency structures are considered.

517

Figure 4: A dependency structure for the English sentence “i get a book from him .”, with ⟨L⟩, ⟨R⟩,⟨/L⟩, ⟨/R⟩ tags. The root of the sentence is marked as ⟨/s⟩ and for a word without modifiers, its
modifier word sequences are ⟨O⟩⟨/O⟩ where O ∈ {L, R}.

4 Parameter Estimation

Because our model is essentially equivalent to
the generative Model C in Eisner (1996), the consistence of the language model can be guaranteed. That is, ⟨O⟩mϕ1 ⟨/O⟩ (O ∈ {L, R}) is generated as a Markov sequence to serve as the modifier word sequences (left/right separately) of thehead word. The “start tag” ⟨O⟩ always satisfies
P (m0 = ⟨O⟩) ≡ 1 to represent the nested structure. The “end tag” ⟨/O⟩ terminates the generation process, so: the larger P (mϕ+1 = ⟨/O⟩) is,
the smaller ϕ, which is the number of generated
words, becomes, and vice versa.
Without loss of generality, the probability ofmκ+1 (0 ≤ κ ≤ ϕ) in M = mϕ+1
can be rep0
resented by P (mκ+1 |mκ0 , H), where H is the history of M along the generated path7 . We use theindependent assumption that the probability of aword in the generation process depends on only its
direct ancestors and the orientation between them.
So, the general probability can be simplified to:
P (h0 |o1 , h1 , . . . , on−1 , hn−1 )4.1 Notation
For a sentence S = w0l+1 ≡ w0 , w1 , · · · , wl+1 ,where w0 ≡ ⟨s⟩ and wl+1 ≡ ⟨/s⟩, a dependency
N-gram (h0 , o1 , h1 , . . . , on−1 , hn−1 ) can be denoted by d = (d0 , d1 , . . . , dn−1 ) where hk = wdk .
That is, a dependency N-gram can be denoted byan N-tuple of the absolute positions of words in agiven sentence. As the magnitudes of dk and dk+1
show the orientation, ok+1 can be omitted.9
Lee and Choi (1997) propose the complete-link
set and complete-sequence set for head-modifier
pair (i.e., a dependency bi-gram in our model) to
handle all possible projective dependency structures of a sentence in a recursive manner. We follow the terms they use and extend their definitions
to adapt them to our dependency N-gram model.
We use Link (d) to denote the complete-link setof an N-tuple d, and Seq(d) for the completesequence set.
In Lee and Choi (1997), the complete-link setof a span [i, j] in a sentence is composed of all
possible dependency structures within the span,with the directional dependency link of the twowords wi and wj . The complete-sequence set ofa span [i, j] is defined as the set of all possible sequences with any number (including zero) of adjacent complete-link sets having the same direction within the span. By our notation, i.e. theword at d1 is the direct head of the word at d0
for Link (d0 , d1 ); but the word at d1 is an ancestor (not only a direct head) of the word at d0 forSeq(d0 , d1 ). The two kinds of sets can be definedrecursively and the set of all possible dependency(1)

where hk is a lexical word, hk+1 is the head wordof hk , and ok ∈ {⟨L⟩, ⟨R⟩} is retained in the history to show the dependency orientation. ⟨/L⟩ and⟨/R⟩ tags can and only can8 take the place of h0 .
The sequence (h0 , o1 , h1 , . . . , on−1 , hn−1 ) in
Exp. (1) is referred as a dependency N-gram inthis paper. For example, a dependency N-gram is(⟨/L⟩, ⟨L⟩, him, ⟨R⟩, from, ⟨R⟩, get, ⟨L⟩, ., ⟨/s⟩)in the dependency structure illustrated in Fig. 4.
Exp. (1) is the probability of the dependency Ngram and thus the parameter of our model, where
the dependency relation and valence are modeled
uniformly for arbitrary order parameters.
7

The generation process can be realized in a depth-first ora breadth-first way but the distinction is unessential.
8
Because they cannot have further modifiers.

9
If h0 is ⟨/L⟩ or ⟨/R⟩, we retain them in d. The orientations can also be unambiguously omitted for these two tags.

518

Figure 5: Link (d = (i, j)). In Lee and Choi
(1997), for a span [i, j], Link (i, j) is composedof the dependency link of wi and wj , and all possible pairs of complete-sequence sets Seq(x, i)
and Seq(x + 1, j).

Figure 7: Link (d = (i, j, k)). In our model, an
extended high-order (3 is shown here) completelink set Link (i, j, k) is composed of the N-tupled, and all possible pairs of complete-sequence
sets Seq(x, i, j) and Seq(x + 1, j, k).

Figure 6: Seq(d = (i, j)). In Lee and Choi
(1997), for a span [i, j], Seq(i, j) is composedof all possible pairs of complete-sequence set
Seq(i, x) and complete-link set Link (x, j).

Figure 8: Seq(d = (i, j, k)). In our model, an
extended high-order (3 is shown here) completesequence set Seq(i, j, k) is composed of all possible pairs of complete-sequence set Seq(i, x, j)
and complete-link set Link (x, j, k).

structures of a sentence S = w0l+1 is the completesequence set over the span [1, l + 1]. We illustratethese recursive relations in Fig. 5 and Fig. 6.
Because more than two words are involved in
the proposed dependency N-gram, we generalize
the two kinds of sets for the N-tuples d rather
than just spans. The generalization still retains theproperties of d0 and d1 in Link (d) and Seq(d), as
well as the recursive properties of the two kinds ofsets. We show examples of a dependency tri-gramin Fig, 7 and Fig. 8.

dex x (absolute word position) and an N-tupled = (d0 , d1 , . . . , dn−1 ):Here, we give the formulation of the recursive
definition of the complete-link set and completesequence set for an arbitrary order dependency Ngram. First, due to the properties of the projective
dependency structure, any dk (k ∈ [1, n−1]) in the
N-tuple d = (d0 , d1 , . . . , dn−1 ) needs to satisfy
the following constraint to guarantee that a head
word is outside of the range covered by a chain ofits descendants.
dk < min(d0 , · · · , dk−1 )Cover (x, d) = (x, d1 , d2 , . . . , dn−1 )(5)Insert(x, d) = (d0 , x, d2 , . . . , dn−1 )(6)∪Link (d) =if d1 =l+1, then i=d1 −1;else i∈[min(d0 ,d1 ), max(d0 ,d1 )−1]

{Seq(Left(i, d))×(7)

Seq(Right(i + 1, d)) × d}
where
(Left, Right) ={(Push, Cover ), if d0 < d1
(Cover , Push), if d0 > d1

(2)

Trivially, we take ⟨/s⟩ as the root mark of a sentence S = w0l+1 , and the ⟨s⟩ as the head of itself
or the ⟨/s⟩. So, we have the following constraints.
dk+1 = 0, if dk = l + 1, or dk = 0(4)Then, the Link (d) and Seq(d) can be defined byExp. (7) and Exp. (9) below, where “×” indicatesthe direct product of sets.

4.2 Recursive Definition

dk > max(d0 , · · · , dk−1 ), orPush(x, d) = (x, d0 , d1 , . . . , dn−2 )Seq(d) =∪i∈[min(d0 ,d1 ), max(d0 ,d1 )]and i̸=d1(3){Seq(Insert(i, d))×

For convenience, we introduce three kinds ofoperations, Push, Cover, and Insert over an in-

Link (Cover (i, d))}

519

(8)

(9)

where p(d) is the probability of the lexical dependency N-gram represented by d in a sentence.

Exp. (7) shows that a complete-link set is recursively composed of the direct product of all
possible complete-sequence set pairs, with the Ntuple d itself.10 Exp. (9) shows that a completesequence set is recursively composed of the direct
product of all possible pairs of a complete-link set
and a smaller complete-sequence set.
To start the recursive definition, we replace d0by ⟨/L⟩ and ⟨/R⟩ for all Seq(d) with d0 = d1 11 .
Left(x, d) = Left(⟨/R⟩, d),if x = min(d0 , d1 ) in Exp. (7)Right(x, d) = Right (⟨/L⟩, d),if x = max(d0 , d1 ) in Exp. (7)Insert(x, d) = Push(⟨/L⟩, d),if x = d0 , and d0 < d1 in Exp. (9)Insert(x, d) = Push(⟨/R⟩, d),if x = d0 , and d0 > d1 in Exp. (9)β(Link (d)) =∑β(Seq(d)) =∑(10)α(Link (d)) =
∑
(11)
(12)

α(Seq(d)) =∑(13)α(Sup)β(Con)(18)α(Sup)β(Con)p(d′ )⟨Sup,Con⟩, s.t.
RLink (Sup,⟨Seq(d),Con⟩)

∑

(19)

α(Sup)β(Con)⟨Sup,Con⟩, s.t.
RSeq (Sup,⟨Seq(d),Con⟩)

According to the recursive definition, it is natural to derive an inside-outside algorithm (Lari andYoung, 1990), which is an adaption of the EM algorithm (Dempster et al., 1977) to tree structures,to conduct parameter re-estimation by calculating
the inside and outside probabilities of all complete
sets in sentences.
We generalize the expressions in Exp. (7) andExp. (9) to Exp. (14) and Exp. (15) respectively,
where the notation ⟨·, ·⟩ stands for an unordered
2-tuple of a complete-set pair.
∪
Link (d) ={Sub 1 × Sub 2 × d} (14)(where d′ is the N-tuple of Sup)
Specifically, Exp. (16) and Exp. (17) can be directly derived from the definitions of Exp. (7) andExp. (9), respectively. Further, a complete-link set
can only be a component of a complete-sequence
set from Exp. (9), while a complete-sequence set
can be both a component of a complete-link set
from Exp. (7), and a component of a completesequence set from Exp. (9). As a result, Exp. (18)and Exp. (19) can be derived respectively.
For all Seq(d) with ⟨/L⟩ or ⟨/R⟩, we use:∀⟨Sub 1 ,Sub 2 ⟩{Sub 1 × Sub 2 }(17)⟨Sup,Con⟩, s.t.
RSeq (Sup,⟨Link (d),Con⟩)+∪β(Sub 1 )β(Sub 2 )⟨Sub 1 ,Sub 2 ⟩, s.t.
RSeq (Seq(d),⟨Sub 1 ,Sub 2 ⟩)4.3 Estimation

Seq(d) =β(Sub 1 )β(Sub 2 )p(d) (16)⟨Sub1 ,Sub 2 ⟩, s.t.
RLink (Link (d),⟨Sub 1 ,Sub 2 ⟩)β(Seq(d)) = p(d)
(15)

(20)

as the start of the calculation. At the end of thecalculation, the probability of the whole sentence
S = w0l+1 can be obtained as:∀⟨Sub 1 ,Sub 2 ⟩We further define RLink (Link (d), ⟨Sub 1 , Sub 2 ⟩)as a relation for Link (d), ⟨Sub 1 , Sub 2 ⟩ satisfying
Exp. (14). Similarly, RSeq (Seq(d), ⟨Sub 1 , Sub 2 ⟩)is a relation for Seq(d), ⟨Sub 1 , Sub 2 ⟩ satisfying
Exp. (15). Then, the inside probability β and outside probability α of the two kinds of complete
sets can be calculated by Exp. (16) to Exp. (19),P (S) = β(Seq(d = (1, l + 1, 0, · · · , 0))) (21)
For the re-estimation, we can get the probabilistic counts12 of a dependency N-gram represented
by d in a sentence using:β(Link (d)) · α(Link (d)) · P (S)−1

10
We further restrict the root mark ⟨/s⟩ to take only one
modifier (the situation when d1 = l + 1 in Exp. (7)), according to the general restrictions of the dependency grammar.
11
From the restriction in Exp. (2), d0 should not be equalto d1 . This is only possible for those Seq(d) at the start of therecursive definition, where the word at d0 is actually a ⟨/L⟩
tag or a ⟨/R⟩ tag, which does not have an absolute position
in a sentence.

13

(22)

according to the inside-outside algorithm. Finally,
all the counts of a dependency N-gram in the training corpus are added and normalized using Exp.
(1), to update the model parameters.
12
13

520

They are no longer integers.
For the situation in Exp. (20), we use β(Seq(d))·α(Seq(d))
.
P (S)

5

Experiments

5.2 Results
Algorithm Convergence

5.1 Experiment Setting
CorpusAs the proposed dependency N-gram model andestimation algorithm are language-independent,
we conduct experiments using four different languages: English, German, Spanish and Japanese.
The corpora we use for English, German, andSpanish are the sets of sentences with 5 – 15 words
from the corresponding single-language corporaof Europarl14 (Koehn, 2005). The corpus forJapanese is the set of sentences with 5 – 20 words
from the Japanese side of the NTCIR-8 corpus(Fujii et al., 2010). We take one two-hundredthof the sentences from a corpus to form each of thedevelopment and test sets used in experiments, andthe remaining sentences are used for training. The
details of training, development and test sets areshown in Tables 1 and 2.
language
EnglishGermanSpanishJapanesesentences
400, 100
422, 951
370, 791
477, 118

types
40, 913105, 303
58, 31447, 930

Figure 9: The English training set perplexities
before each iteration. (The y-axis is logarithmic.)
Figure 9 shows the change of English training
set perplexities before each iteration by the proposed estimation algorithm, for 2 (bi-) and 3 (tri-)order dependency N-gram models. The convergence trend along with the iteration times can beobserved. For the dependency bi-gram, the training set perplexity becomes nearly stable after 5 iterations. However, for the dependency tri-gram,the first iteration already reaches a very low training set perplexity and it does not change much infurther iterations. This phenomenon suggests thatthe non-pruned dependency tri-gram model may
already be too complex a model with too many parameters, so the features of the training set are represented well, resulting in a low perplexity. Thissuggests the model is over-fitting the data. We discuss this in Sec. 5.3.

tokens4, 355, 333
4, 545, 263
4, 007, 816
7, 758, 437

Table 1: The training sets.
language
EnglishGermanSpanishJapanesedevelopment set
2, 0202, 136
1, 872
2, 409test set
2, 0212, 136
1, 8732, 410

Test Set Perplexity
As well as the training set perplexity, the perplexity of a test set which has not been used in parameter estimation should be investigated in evaluation.
Because different order dependency N-gram models are trained separately, we use linear interpolation in calculating the test set perplexity. Specifically, we use the hand-out development set to tune
the interpolation coefficients (weights) and to select the iteration times of different order models
to minimize the development set perplexity. Then
we use the tuned weights to combine the iterationtime-selected models in the test set perplexity calculation. The reason for using simple and straightforward linear interpolation is also that we want
to discover the essential aspects of the proposedmodel and algorithm, so we use no further smoothing approaches. As the lowest order of a dependency N-gram is two, we use a uni-gram modelwith modified Kneser-Ney discounting to handle
the unknown words. The uni-gram model is interpolated with the dependency bi-gram model. Fur-

Table 2: The numbers of sentences in development and test sets.
Parameter Collection and Initialization
In order to investigate the fundamental propertiesof the model and algorithm, we do not use any
pruning or approximating methods in the parameter estimation. Specifically, we collect from theraw corpora all possible lexical dependency Ngrams15 without any cut-off thresholds for modelsof every order. Before estimation, we use relative
frequency to initialize the probabilities.
14

http://www.statmt.org/europarl/
As Japanese is a typical head-final language, that is, thehead word always comes after its modifiers, we only take theleft-oriented (from head to modifier) dependency links into
account. For the other three languages, dependency links ofboth two orientations are considered. The parameter collection and initialization do not take the structure into account.
15521

language
EnglishGermanSpanishJapanese (left-only)

dev-ppl (bi / tri)
145 / 143
268 / 256
165 / 164
88 / 67

test-ppl (bi / tri)
159 / 156
265 / 261
159 / 158
88 / 67

iter bi612
7
4iter tri
1
1
1
1

λuni
0.93
0.88
0.92
0.86

λbi
0.99
0.98
0.99
0.99

λtri
0.13
0.04
0.04
0.70

Table 3: The development set perplexities (dev-ppl) and test set perplexities (test-ppl) of dependency
N-gram models (N = 2 (bi), 3 (tri)). The iteration times in dependency bi- and tri-gram model training
are iter bi and iter tri , respectively. The weights of uni-gram, dependency bi- and tri-gram models are
λuni , λbi and λtri . (1 − λbi ) and (1 − λtri ) are assigned to the interpolated lower order models and(1 − λuni ) is assigned to the ⟨/L⟩ and ⟨/R⟩ tags.
thermore, as the ⟨/L⟩ tag and ⟨/R⟩ tag are taken
as general words but they never really appear in a
training set, we treat them separately, and interpolate them with the uni-gram model.
language
EnglishGermanSpanishJapanese

MLE (bi / tri)
162 / 457
396 / 1371
176 / 499
62 / 87

5.3 Discussion
Parameter Number
For a sentence with l words, the number of dependency N-gram that can be collected increases
exponentially as O(lN ) if we consider all possiblecombinations. Although for a given N , the proposed algorithm takes a time which is polynomialin the sentence length l, a large N will be practically intractable, especially for long sentences. In
Fig. 10, we show the numbers of complete setsof different order dependency N-gram models fordifferent sentence lengths.

MKN (bi / tri)
157 / 86
252 / 139
161 / 86
91 / 39

Table 4: The test set perplexities of the originalN-gram models. MLE is the maximum likelihood estimation realized by setting the adding
delta to 0 in adding smoothing. MKN is the interpolated modified Kneser-Ney discounting.
In Table 3, we show the development and test
set perplexities of the linear-interpolated dependency bi- and tri-gram models. For comparison,
we used SRILM16 (Stolcke, 2002) to build two
original N-gram language models on the same
training sets: one is constructed by maximum
likelihood estimation without any smoothing, theother one is constructed by state-of-the-art interpolated modified Kneser-Ney discounting. We
calculate the test set perplexities of the two Ngram language models on the same test sets. The
results are listed in Table 4. In both Table 3 andTable 4, the perplexities are calculated according
to the number of lexical words, and the tags used
for normalization are not counted17 . We discussthese results in Sec. 5.3.

Figure 10: The numbers of complete sets. (They-axis is logarithmic.)
This behavior is also related to the over-fitting
problem because our algorithm is essentially an iterative maximum likelihood estimation. A modelthat is too complex will be too specific to the training set. From Table 3, we see that the performance of a dependency tri-gram model will saturate after only one iteration, which is also indicated in Fig. 9, and does little to improve thetest set perplexities. The exception is Japanese,
where the dependency tri-gram does improve theperformance. The linguistic reason for this is thatJapanese is a head-final language with a simpler
syntactic structure, so we restrict the dependency
link in Japanese to “left only”, which leads to amodel with fewer parameters. Consequently, thehigh order model performs better. From the experimental results, we can see that the proposed
algorithm has the usual strengths and weaknessesof an EM algorithm.

16

http://www.speech.sri.com/projects/
srilm/
17
That is, we do not count the ⟨/s⟩ tag in the original Ngram language models, or ⟨/L⟩ and ⟨/R⟩ in our models. Ifthey are included, the perplexities decrease. In the original Ngram model, this is because a ⟨/s⟩ tag nearly always appears
after the period mark. The effect is even more dramatic in
our model, as each word in a sentence has a ⟨/L⟩ and a ⟨/R⟩
tag to normalize its modifier numbers, so the token number
in a sentence is multiplied by. Therefore, we only count thelexical words in perplexity calculation for fairness.

522

Figure 11: The best dependency structure of the
English sentence “i would , however , add one
important caveat .”Figure 13: The best dependency structure of the
Spanish sentence “la comisión está haciendomuchas cosas a este respecto .”Figure 12: The best dependency structure of theGerman sentence “trotzdem möchte ich der kommission einige fragen stellen .”Figure 14: The best dependency structure of theJapanese sentence “図 3 は 、 その 実際 の 配
置 例 で ある 。”

Test Set Perplexity
Comparing the test set perplexities in Tables 3
and 4, we can see the dependency bi-gram model
achieves the same, or sometimes better performance of the original N-gram language models.
However, when we look at the tri-grams, the interpolated modified Kneser-Ney (KN) discounting method, which is state-of-the-art, shows its
strength and our dependency model does not produce much improvement for the reasons we described above18 . As the modified KN method uses
an efficient discounting to avoid the over-fitting
problem, and our model has no smoothing, the difference in performance is reasonable for complex
models. On the other hand, the generally competitive results of our bi-gram model and its performance on Japanese show that our model is apromising one, particularly if the number of parameters can be reduced.

is the head of the noun “respecto”, but in unsupervised training, our model prefers to assign “a”
to be the modifier of “respecto” and directly link
two content words: “respecto” and the verb “haciendo”. We think this is because the probabilities of ⟨/L⟩ and ⟨/R⟩ tags have large estimates,
especially when they appear after function words,
which prevents them from having modifiers20 .

6 Conclusion and Future WorkIn this paper, we proposed a generative dependency N-gram language model and the definitionof the complete sets for arbitrary order, by which
an unsupervised parameter estimation algorithm isfacilitated. The experimental results demonstrate
the applicability and the properties of the proposed
approach. In future work, we will develop methods of parameter pruning and discounting to handle the over-fitting problem. As the the proposed
dependency language model is intrinsically complex, we also plan to do more fundamental simplifications. On the other hand, although our proposed algorithm is unsupervised, the output of a
trained parser, which can provide clear and lexical
heuristics, can be integrated in it. We will investigate this possibility and evaluate the performanceby linguistically motivated criteria.

Model Preference
In Fig. 11 to Fig. 14, we present examples of thebest dependency structures generated by our approach of sentences in test sets. We used the settings in Table 3 and generated them by the Viterbi
algorithm (Viterbi, 1967). It can be seen the proposed approach can reveal features of specific languages even though it is unsupervised: e.g. thefinal-position verb “stellen” and its relation withthe second-position auxiliary verb “möchte” in theGerman sentence. The results also show a preference for associating semantic relations and making the function words19 of a language the modifiers of the content words. For example, in the
Spanish sentence, syntactically the preposition “a”

Acknowledgment
We would like to thank anonymous reviewers fortheir valuable comments and suggestions. This
work was supported by JSPS KAKENHI Grant
Number 24650063.

18
For Japanese, the result is improved by the dependency
tri-gram model, but the original tri-gram model with interpolated modified KN discounting method performs much better.
19
Articles, prepositions, etc.

20This tendency, however, is correct for articles, such as
the “der” in German and “la” in Spanish.

523

References

Seungmi Lee and Key-Sun Choi. 1997. Reestimation
and best-first parsing algorithm for probabilistic dependency grammars. In Proc. of WVLC 1997, pages
41–55.

Peter F. Brown, Peter V. deSouza, Robert L. Mercer,
Vicent J. Della Pietra, and Jenifer C. Lai. 1992.
Class-based n-gram models of natural language.
Computational Linguistics, 18(4):467–479.

Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553.

Ciprian Chelba and Frederick Jelinek. 2000. Structured language modeling. Computer Speech andLanguage, 14(4):283–332.

Mark A. Paskin. 2002. Grammatical digrams. Advances In Neural Information Processing Systems
14, 1:91–97.

Stanley F. Chen and Joshua Goodman. 1998. An empirical study of smoothing techniques for language
modeling. Technical report, TR-10-98, Computer
Science Group, Harvard Univ.

Andreas Stolcke, Ciprian Chelba, David Engle, Victor
Jimenez, Lidia Mangu, Harry Printz, Eric Ristad,Roni Rosenfeld, Dekai Wu, Frederick Jelinek, andSanjeev Khudanpur. 1997. Dependency language
modeling.

Michael Collins. 1998. Three generative, lexicalisedmodels for statistical parsing. In Proc. of ACL 1998,
pages 16–23.

Andreas Stolcke. 2002. SRILM–an extensible language modeling toolkit. In Proc. of ICSLP 2002,
pages 901–904.

Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin . 1977. Maximum likelihood from incomplete
data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological), 39(1):1–
38.

Christoph Tillmann and Hermann Ney. 1997. Word
triggers and the EM algorithm. In Proc. of CoNNL
1997, pages 117–124.

Jason M. Eisner. 1996. Three new probabilistic models for dependency parsing: an exploration. In Proc.
of COLING 1996, pages 340–345.

Andrew Viterbi. 1967. Error bounds for convolutional
codes and an asymptotically optimum decoding algorithm. Information Theory, IEEE Transactions on
Information Theory, 13(2):260–269.

Atsushi Fujii, Masao Utiyama, Mikio Yamamoto,Takehito Utsuro, Terumasa Ehara, Hiroshi Echizenya, and Sayori Shimohata. 2010. Overview of thepatent translation task at the NTCIR-8 workshop. In
Proc. of NTCIR-8, pages 371–376.
Jianfeng Gao and Hisami Suzuki. 2003. Unsupervised
learning of dependency structure for language modeling. In Proc. of ACL 2003, pages 521–580.
Yvette Graham and Josef van Genabith. 2010. Deep
syntax language models and statistical machinetranslation. In Proc. of SSST at COLING 2010,
pages 118–126.
Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proc. of ACL 2003,
pages 423–430.
Dan Klein and Chirstopher D. Manning.
2004.
Corpus-based induction of syntactic structure: models of dependency and constituency. In Proc. of ACL
2004, pages 478–485.
Philipp Koehn. 2005. Europarl: a parallel corpus forstatistical machine translation. In Proc. of MT summit 2005, pages 79–86.
Taku Kudo and Yuji Matsumoto. 2002. Japanese
dependency analysis using cascaded chunking. In
Proc. of COLING 2002, pages 1–7.
K. Lari and S. J. Young. 1990. The estimation ofstochastic context-free grammars using the insideoutside algorithm. Computer Speech and Language,4(1):35–56.

524