A Generative Dependency N-gram Language Model:
Unsupervised Parameter Estimation and Application
Chenchen Ding† and Mikio Yamamoto†We design a language model based on a generative dependency structure for sentences.
The parameter of the model is the probability of a dependency N-gram, which iscomposed of lexical words with four types of extra tag used to model the dependency
relation and valence. We further propose an unsupervised expectation-maximization
algorithm for parameter estimation, in which all possible dependency structures of asentence are considered. As the algorithm is language-independent, it can be used ona raw corpus from any language, without any part-of-speech annotation, tree-bankor trained parser. We conducted experiments using four languages, i.e., English,
German, Spanish and Japanese, to illustrate the applicability and the properties of the
proposed approach. We further apply the proposed approach to a Chinese microblog
data set to extract and investigate Internet-based, non-standard lexical dependency
features of user-generated content.
Key Words: N-gram language model, Generative dependency structure, Unsupervised algorithm, Microblog

1 Introduction
Statistical language models are a fundamental component of speech recognition systems, machine translation systems and so forth. At present, the N-gram language model is the most widelyused approach. This model focuses on sequences of neighboring lexical words (Figure 1) and uses
the probabilities of these sequences as model parameters. Due to the complete 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 considers asentence as a ﬂat string and ignores its structure.
Revealing a sentence structure is the task of parsing, which is based on linguistically oriented formulations, and it focuses on generating the likeliest structure for a given sentence,using constituency- or dependency-based formulations. The former organizes continuous word
sequences in a hierarchy of small to large range groups with linguistically oriented labels, while
the latter directly links words with dependency relations1 (Figure 2).
† Department of Computer Science, University of Tsukuba
1 In general, the dependency relations can be further classiﬁed using linguistically oriented labels.

However,they are not indispensable, and we do not use them in our approach. For the ﬁgures in this study, we use thefollowing representation to show the dependency structure. If two aligned words are on diﬀerent levels, theupper one is the head of the lower one; if they are on the same level, they are siblings.

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

In this study, we focus on introducing sentence structure into language modeling. We propose a generative dependency N-gram language model that integrates the generative dependency
structure of a sentence into the original N-gram language model. We prefer the dependencybased formulation because it can directly model the relations between words. In the proposedmodel, the parameter is the probability of the dependency N-gram, which is a sequence of words
along the dependency structure rather than along a ﬂat left-to-right string. The proposed modelis thus as completely lexical as the original N-gram language model. We further propose an
expectation-maximization (EM) algorithm for estimating the probability of arbitrary order2 dependency N-grams, by considering all possible dependency structures3 of a sentence (Figure 3).

Fig. 1 N-gram language model. For N = 2, the model treats the English sentence “all things pass” asbeing constructed from the bi-grams (all, things) and (things, pass).

Fig. 2 Constituency-based parsing (A) and dependency-based parsing (B) of the English sentence“all things pass”.

Fig. 3 All possible dependency structures for the English sentence “all things pass”. (I) is the linguistically correct structure, while the original N-gram language model handles the sentence as if it
has the structure labeled (II). We consider all these structures in our unsupervised estimation
algorithm.

2 In this study, the term “order” of a dependency N-gram means the number of lexical words (N ) in a head-

modiﬁer chain, which is used as an extension of the original N-gram. In the context of dependency parsing,“order” generally means the number of words in a treelet, which can contain relations such as siblings, ancestors
and descendants. That is, the “order” in this study is restricted to include only ancestors.
3 Only projective dependency structures are considered.

982

Ding and Yamamoto

A Generative Dependency N-gram Language Model

The proposed algorithm is unsupervised, language-independent and needs no linguistic information.

2 Related Work
The technical report by (Chen and Goodman 1998) has compared various approaches to theN-gram language model and the modiﬁed Kneser-Ney (KN) discounting proposed in it is still thestate-of-the-art. Since the N-gram language model only captures local lexical features, there havebeen proposals to generalize the lexical N-gram by word class (Brown, deSouza, Mercer, Pietra,and Lai 1992) or to model long-range word co-occurrences by word triggers (Tillmann and Ney
1997). However, these models are unaware of the sentence structure, and they basically take asentence as a ﬂat string.
Many approaches have been proposed for constituency-based parsing (Collins 1998; Klein andManning 2003, 2004) and for dependency-based parsing (Eisner 1996; Lee and Choi 1997; Kudo
and Matsumoto 2002; Klein and Manning 2004; Nivre 2008; Koo and Collins 2010; Zhang and
McDonald 2012). Discriminative approaches (Kudo and Matsumoto 2002; Nivre 2008) are used
more than 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-modiﬁer pairs). Speciﬁc
algorithms have been designed to handle more complex dependency relations (Koo and Collins
2010; Zhang and McDonald 2012), and these allow the consideration of more lexical information
in a generative model.
There have been attempts to integrate sentence structure into language modeling. (Chelba andJelinek 2000) have proposed a constituency-based approach, but the use of language-dependent
non-terminals cannot be avoided. There are also dependency-based approaches. One straightforward method is to construct a language model based on the decisively best structure produced
by a parser (Stolcke, Chelba, Engle, Jimenez, Mangu, Printz, Ristad, Rosenfeld, Wu, Jelinek,
and Khudanpur 1997; Gao and Suzuki 2003; Graham and van Genabith 2010). These approaches
can be considered to convert the left-to-right string in the original N-gram model to a completely
syntax-driven tree structure. A more reasonable method is to consider all dependency structuresof a sentence. One such attempt is the bi-gram head-modiﬁer model of (Lee and Choi 1998),
which is based on the parsing approach of (Lee and Choi 1997).
In our approach, we consider all dependency structures of a sentence and try to include
more lexical information. We extend the approach of (Lee and Choi 1997) to head-modiﬁer
chains of arbitrary words, rather than head-modiﬁer pairs. We also use extra tags of the type983

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

typically found in parsing models. These tags are treated as general lexical words and are used
to model the valence of a head word. The parsing approaches of (Koo and Collins 2010) also
handle more lexical information in a dependency structure, including complex relations, suchas the sibling relation. However, the use of high-order dependency patterns in the approach islimited. As described in (Zhang and McDonald 2012), arbitrary orders of lexical information
with arbitrary dependency relations can be handled only if the proper algorithms are designed,
and designing these becomes more complex with the increasing number of lexical words anddependency relations. Our approach concentrates only on the head-modiﬁer chain, that is, asequence of parent-child relations. Therefore, our approach is a direct extension of the originalN-gram model, which models a lexical word sequence, without branching. We will also show thata head-modiﬁer chain of arbitrary order can be modeled in a uniform algorithm, which will notincrease in formulation complexity when the order increases.

3 Generative Dependency Model
We model the marginal probability of a sentence S over set D of all possible dependency∑
structures of S: P (S) = d∈D P (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 completely lexical word sequences with dependency relations.
However, the term P (d), which is the probability of a dependency graph without lexical words,
is diﬃcult to model. In earlier studies , the P (d) term is taken as a constant or omitted (i.e.,taken as 1) for simplicity, as in (Paskin 2002; Lee and Choi 1998). For example, in (Lee and Choi∑∏
1998), the probability of a sentence S is calculated as P (S) = d∈D (x→y)∈d P (x → y), where
the element (x → y) is a lexical head-modiﬁer pair in a given dependency structure d. Thus, the∏term x→y∈d P (x → y) is equivalent to P (S|d).
To combine the dependency structure and lexicalization, the valence, which represents themodiﬁer numbers of a head word, should be modeled. A dependency model with valence (DMV)
is proposed by (Klein and Manning 2004). DMV is a generative model that includes a special
mark, STOP, to terminate the modiﬁer sequence of a head word. With the help of the STOP
mark, the number of modiﬁers can be controlled. It is necessary to distinguish the two typesof parameters, i.e., PSTOP and PCHOOSE in the bi-gram estimation, which makes it diﬃcult toextend the approach to higher orders.
In a similar approach to that used in DMV, we introduce four types of tag to normalize
the distribution of modiﬁer numbers (the valence) of a head word. In this study, we use ⟨L⟩984

Ding and Yamamoto

A Generative Dependency N-gram Language Model(resp. ⟨/L⟩) and ⟨R⟩ (resp. ⟨/R⟩) to show the start (resp. end) of the left and right modiﬁerword sequences of a head word. The dependency structure can thus be organized as nested word
sequences. Speciﬁcally, modiﬁer word sequences of a head word are of the form M = mϕ+1≡0
m0 , m1 , · · · , mϕ+1 , where m0 ≡ ⟨O⟩, mϕ+1 ≡ ⟨/O⟩ (O ∈ {L, R}), and mϕ1 is a lexical ϕ-wordsequence. We show an example of the dependency structure in Figure 4. For example, in Figure 4,
the word get has a left modiﬁer word sequence “⟨L⟩ i ⟨/L⟩” and a right modiﬁer word sequence“⟨R⟩ book f rom ⟨/R⟩”. In contrast to the treatment in DMV, we treat tags as ordinary words inthe parameter estimation. This means parameters of our model have a uniform representation,by which our approach can be easily extended to arbitrary high orders.
Our model is essentially equivalent to the generative Model C in (Eisner 1996). In otherwords, the sequence ⟨O⟩mϕ1 ⟨/O⟩ (O ∈ {L, R}) is generated as a Markov sequence to serve as themodiﬁer word sequences (left/right separately) of the head word. The “start tag” ⟨O⟩ always
satisﬁes P (m0 = ⟨O⟩) ≡ 1 to represent the nested structure. The “end tag” ⟨/O⟩ terminates
the generation process: the larger P (mϕ+1 = ⟨/O⟩) is, the smaller ϕ, which is the number ofgenerated words, becomes and vice versa.4
can beWithout loss of generality, the probability of mκ+1 (0 < κ ≤ ϕ) in M = mϕ+10
represented by P (mκ+1 |mκ0 , H), where H is the history of M along the generated path5 . We use

Fig. 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} (marked by dashed lines).

4 As to the consistency of our language model, that is, whether∑

S∈L P (S) = 1 for every possible sentence
S in a language L, we note that it cannot be guaranteed by the generative structure alone. As discussedin (Wetherell 1980), a language generated by a probabilistic context-free grammar cannot be guaranteed tobe consistent, because the generation process cannot be guaranteed to ﬁnish, even when the probabilities arenormalized. However, in this situation, the probabilities of terminal sequences (i.e. sentences) will be very
low, which will lead to a poor performance of the language model. Thus, the results for the proposed approachreported in this study may underestimate probabilities but will not overestimate them.
5 The generation process can be realized in a depth-ﬁrst or a breadth-ﬁrst way, but distinction is not essential.

985

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

the independent assumption that the probability of a word in the generation process only depends
on its direct ancestors and the orientation between them. The probability can be simpliﬁed to:
P (h0 |o1 , h1 , . . . , on−1 , hn−1 ),(1)where hk (k ∈ [1, n − 1]) is the head word of hk−1 and ok (k ∈ [1, n − 1]) shows the orientation
between them. Speciﬁcally, hk (k ∈ [0, n − 1]) can be any of the following:•a lexical word in a given sentence,•a ⟨/O⟩ (O ∈ {L, R}) tag,•the sentence-ending tag ⟨/s⟩, which is taken as the root of a sentence, or•the sentence-beginning tag ⟨s⟩, which is taken as a trivial placeholder,and ok (k ∈ [1, n − 1]) is a ⟨O⟩ (O ∈ {L, R}) tag.
The “slash” tags, ⟨/s⟩, ⟨/L⟩ and ⟨/R⟩, are taken as lexical words, which are represented by
h . The “no-slash” tags, ⟨L⟩ and ⟨R⟩, show the direction of a modiﬁer word against its headkword, which is represented by ok . Speciﬁcally, for k ∈ [1, n − 1], we have ok = ⟨L⟩ when hk−1
is on the left side of hk , and ok = ⟨R⟩ when hk−1 is on the right side of hk .6 Further, thesentence-beginning tag ⟨s⟩ is used as a trivial placeholder to increase the order of Exp. (1) ton. It is used only when hk = ⟨/s⟩ for some k < n − 1.7 For the tags, there are some noticeable
properties, such as the following:•

if hk = ⟨/O⟩ (O ∈ {L, R}), then k ≡ 0; because ⟨/O⟩ (O ∈ {L, R}) cannot have modiﬁers,•

if h0 = ⟨/L⟩, then o1 ≡ ⟨L⟩, and if h0 = ⟨/R⟩, then o1 ≡ ⟨R⟩,

• if hk = ⟨/s⟩ (k ∈ [1, n − 1]), then ok ≡ ⟨L⟩,• if hk = ⟨/s⟩ (k ∈ [1, n − 2]), then both ok+1 ≡ ⟨R⟩ and hk+1 = ⟨s⟩,
• if hk = ⟨s⟩ (k ∈ [1, n − 2]), then both ok+1 ≡ ⟨R⟩ and hk+1 = ⟨s⟩.
For example, a dependency N-gram is (⟨/L⟩, ⟨L⟩, him, ⟨R⟩, from, ⟨R⟩, get, ⟨L⟩, ., ⟨L⟩, ⟨/s⟩)in the dependency structure illustrated in Figure 4. We can see ⟨O⟩ (O ∈ {L, R}) tags between
words show the relevant position between head and modiﬁer words. In fact, all words in a modiﬁer
sequence share the same ⟨O⟩ (O ∈ {L, R}). For example, in Figure 4, the “book ” and “from”
share the same ⟨R⟩ tag as they are both in the right modiﬁer word sequence of the head word“get”.
The sequence (h0 , o1 , h1 , . . . , on−1 , hn−1 ) in Exp. (1) is referred as a dependency N-gram.

6 The use of an index in Exp.

(1) can be interpreted as h0 is on the o1 side of its head word h1 , which is on
the o2 side of its head word h2 , and continue this pattern to hn−2 , which is on the on−1 side of its head wordhn−1 .
7 Hence, we omit the ⟨s⟩ tag in Figure 4 as it adds nothing to the structure.

986

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Exp. (1) is the probability of the dependency N-gram and thus the parameter of our model,
where the dependency relation and valence are modeled uniformly for arbitrary orders.
From the probability of the dependency N-gram of Exp. (1), the probability of a given de∏pendency structure d of a sentence S can be calculated as h0 ∈d p(h0 |o1 , h1 , . . . , on−1 , hn−1 ).
∏Because of how we use ⟨/O⟩ (O ∈ {L, R}) tags, the h0 ∈d p(h0 |o1 , h1 , . . . , on−1 , hn−1 ) is equivalent to P (S, d) rather than to P (S|d), as in (Lee and Choi 1998). We show an example of the
P (S, d) from Exp. (2) to Exp. (6) according to the structure in Figure 4, proceeding layer bylayer8 . We can see there are many terms of the type h0 = ⟨/O⟩ (O ∈ {L, R}) in the calculation.
This can be considered a “discount” for the product of lexical terms to represent the “structure
probability” p(d), although p(d) is never separated as an individual term because we merge thelexicalization and dependency structure in our calculations.
P (S, d) =P (.|⟨L⟩ ⟨/s⟩)(2)·P (get|⟨L⟩ . ⟨L⟩ ⟨/s⟩)P (⟨/L⟩|⟨L⟩ . ⟨L⟩ ⟨/s⟩)P (⟨/R⟩|⟨R⟩ . ⟨L⟩ ⟨/s⟩)(3)·P (i|⟨L⟩ get ⟨L⟩ . · · · )P (⟨/L⟩|⟨L⟩ get ⟨L⟩ . · · · )· P (book|⟨R⟩ get ⟨L⟩ . · · · )P (f rom|⟨R⟩ get ⟨L⟩ . · · · )P (⟨/R⟩|⟨R⟩ get ⟨L⟩ . · · · )(4)·P (⟨/L⟩|⟨L⟩ i ⟨L⟩ get · · · )P (⟨/R⟩|⟨R⟩ i ⟨L⟩ get · · · )· P (a|⟨L⟩ book ⟨R⟩ get · · · )P (⟨/L⟩|⟨L⟩ book ⟨R⟩ get · · · )P (⟨/R⟩|⟨R⟩ book ⟨R⟩ get · · · )· P (⟨/L⟩|⟨L⟩ f rom ⟨R⟩ get · · · )P (him|⟨R⟩ f rom ⟨R⟩ get · · · )P (⟨/R⟩|⟨R⟩ f rom ⟨R⟩ get · · · )(5)·P (⟨/L⟩|⟨L⟩ a ⟨L⟩ book · · · )P (⟨/R⟩|⟨R⟩ a ⟨L⟩ book · · · )· P (⟨/L⟩|⟨L⟩ him ⟨R⟩ f rom · · · )P (⟨/R⟩|⟨R⟩ him ⟨R⟩ f rom · · · )The probability of a sentence S can then be calculated by P (S) =(6)∑d∈D P (S, d), where theleft-to-right generation of the original N-gram model is naturally included, and the probabilityof it will be discounted by the terms of the form h0 = ⟨/O⟩ (O ∈ {L, R}).

4 Parameter Estimation
4.1

Notation

We denote a sentence with l words as S = w0l+1 ≡ w0 , w1 , · · · , wl+1 , where w0 ≡ ⟨s⟩ andwl+1 ≡ ⟨/s⟩; each wk (k ∈ [1, l]) is an ordinary lexical word. In a sentence S = w0l+1 , we denotea dependency N-gram (h0 , o1 , h1 , . . . , on−1 , hn−1 ) by an N-tuple d = (d0 , d1 , . . . , dn−1 ) according
to the following deﬁnition.

dk =



hk , if k = 0 and hk is a ⟨/O⟩ (O ∈ {L, R})i such that hk = wi , otherwise

8 From Exp. (4), we omit part of the histories for brevity.

987

(7)

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

The deﬁnition of dk in Exp. (7) thus shows the relation between hk and dk . Because the ⟨s⟩,⟨/s⟩, ⟨/L⟩ and ⟨/R⟩ tags are taken as lexical words in a dependency N-gram, they can appear
in a d. In our notation, ⟨s⟩ and ⟨/s⟩ are assigned absolute positions of 0 and l + 1, respectively,
in an l-word sentence, so they can be trivially integrated in a d. Conversely, as ⟨/L⟩ and ⟨/R⟩
tags are attached to every word in a sentence, we cannot assign absolute positions to them, so,they remain in a d with no transformation to absolute position. Consequently, dk in a d canbe an integer in [0, l + 1] or a ⟨/O⟩ (O ∈ {L, R}) tag. In fact, because ⟨/L⟩ and ⟨/R⟩ tags canappear only as h0 in a dependency N-gram, they only appear as d0 in a d. The N-tuple d witha d0 = ⟨/O⟩ (O ∈ {L, R}) will play a special role in the recursive deﬁnition in Section 4.2.
Because the magnitudes of dk and dk+1 (k ∈ [0, n − 2]) show the orientation, ok+1 can beomitted. In addition, ok+1 can be unambiguously omitted for the ⟨/L⟩ and ⟨/R⟩ tags because of
the properties we mentioned in the previous section. Consequently, the ⟨L⟩ and ⟨R⟩ tags neverneed to appear in a d. As an example, the dependency N-gram (⟨/L⟩, ⟨L⟩, him, ⟨R⟩, from, ⟨R⟩,
get, ⟨L⟩, ., ⟨L⟩, ⟨/s⟩) in the dependency structure illustrated in Figure 4 can be denoted by ad = (⟨/L⟩, 6, 5, 2, 7, 8) given the sentence “i (1) get (2) a (3) book (4) from (5) him (6) . (7)”.
(Lee and Choi 1997) propose the complete-link set and complete-sequence set for head-modiﬁer
pairs (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 theirdeﬁnitions to adapt them to our dependency N-gram model. We use Link (d) to denote thecomplete-link set of an N-tuple d and Seq(d) for the complete-sequence set.
In (Lee and Choi 1997), the complete-link set of a span [i, j] in a sentence is composed of
all possible dependency structures within the span, with the directional dependency link of thetwo words wi and wj . The complete-sequence set of a span [i, j] is deﬁned as the set of all
possible sequences with any number (including zero) of adjacent complete-link sets having thesame direction within the span. By our notation, the word 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 for Seq(d0 , d1 ). The two types of set can be deﬁned recursively, and the set of all possible
dependency structures of a sentence S = w0l+1 is the complete-sequence set over the span [1, l + 1]
or is the complete-link set over the span [0, l + 1]9 . We illustrate these recursive relations inFigure 5 and 6.10

9 Because p(⟨/s⟩|⟨R⟩ ⟨s⟩) ≡ 1, which is one of the properties we have described, the two complete sets have thesame probability. This is also mentioned in (Lee and Choi 1997).
10 By our notation, there is no necessity to show the head-modiﬁer relation by arrows in Figure 5 to 8.

ﬁgures show the relation between N-tuples, rather than directional pairs.

988

These

Ding and Yamamoto

A Generative Dependency N-gram Language Model

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

Fig. 6 Seq(d = (i, j)). In (Lee and Choi
1997), for a span [i, j], Seq(i, j) is
composed of all possible pairs ofcomplete-sequence set Seq(i, x) andcomplete-link set Link (x, j).

Fig. 7 Link (d = (i, j, k)). In our model, an extended high-order (three-order is shownhere) complete-link set Link (i, j, k) is composed of the N-tuple d, and all possible
pairs of complete-sequence sets Seq(x, i, j)
and Seq(x + 1, j, k).

Fig. 8 Seq(d = (i, j, k)). In our model,
an extended high-order (three-orderis shown here) complete-sequence
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).

Because more than two words are involved in the proposed dependency N-gram, we generalize
the two types of set for the N-tuples d, rather than just spans. The generalization still retains
the properties of d0 and d1 in Link (d) and Seq(d), as well as the recursive properties of the two
types of set. We show the examples of a dependency tri-gram in Figure 7 and 8.

4.2

Recursive Definition

Here, we provide the formulation of the recursive deﬁnition of the complete-link set andcomplete-sequence set for an arbitrary order dependency N-gram.
In the description of the calculation example shown from Exp. (2) to Exp. (6) in Section 3,
we mentioned that those terms h0 = ⟨/O⟩ (O ∈ {L, R}) can be considered as a “discount” of the
product of lexical terms. By the deﬁnition in Exp. (7) in Section 4.1, we can further see thath0 = ⟨/O⟩ (O ∈ {L, R}) terms are represented by the N-tuple d with d0 = ⟨/O⟩ (O ∈ {L, R})
and the other lexical terms are represented by the N-tuple d in which all the dk (k ∈ [0, n − 1])
are integers. For clarity, in this section, we will ﬁrst describe the recursion deﬁnition of lexical
terms without d0 = ⟨/O⟩ (O ∈ {L, R}) involved up to Exp. (17). Next, we turn to the “discount”
terms, that is, the case of d0 = ⟨/O⟩ (O ∈ {L, R}), from Exp. (18) to Exp. (21).
989

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

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 of Exp. (8) toguarantee that a head word is outside the range covered by a chain of its descendants.
dk > max(d0 , · · · , dk−1 ), or dk < min(d0 , · · · , dk−1 )(8)The max(·) and min(·) operations are used to get the maximum and minimum from a tuplecomposed of integers.
Trivially, we take ⟨/s⟩ as the root mark of a sentence S = w0l+1 , and the ⟨s⟩ as the head ofitself or as the head of the ⟨/s⟩. So, we have the following constraints:
if dk−1 = l + 1 or dk−1 = 0, then dk = 0, for k ∈ [1, n − 1]

(9)

To reveal the relations between N-tuples, we introduce three basic operations, Push, Coverand Insert, over an index x (absolute word position) and an N-tuple d = (d0 , d1 , . . . , dn−1 ):Push(x, d) = (x, d0 , d1 , . . . , dn−2 )(10)Cover (x, d) = (x, d1 , d2 , . . . , dn−1 )(11)Insert(x, d) = (d0 , x, d1 , . . . , dn−2 )(12)With the three operations, we can express the relation shown in Figure 7 as follows:
Link (i, j, k) =∪{Seq(Push(x, (i, j, k))) × Seq(Cover (x + 1, (i, j, k))) × {(i, j, k)}}.

(13)

i≤x<j

Here, the symbol × indicates the direct product of sets. That Seq(Push(x, (i, j, k))) ≡ Seq(x, i, j)
and Seq(Cover (x + 1, (i, j, k))) ≡ Seq(x + 1, j, k) follows from their deﬁnitions.
Moreover, the relation shown in Figure 8 can be expressed as follows:
Seq(i, j, k) =∪{Seq(Insert(x, (i, j, k))) × Link (Cover (x, (i, j, k)))}.

(14)

i≤x<j

Here, that Seq(Insert(x, (i, j, k))) ≡ Seq(i, x, j) and Link (Cover (x, (i, j, k))) ≡ Link (x, j, k) follows from the deﬁnitions.
Then, we can provide the formal deﬁnition of the Link (d) and Seq(d) for an arbitrary orderd by Exp. (15) and Exp. (17) below.

990

Ding and Yamamoto

A Generative Dependency N-gram Language Model∪

Link (d) ={Seq(Left(i, d)) × Seq(Right(i + 1, d)) × {d}}(15)

if d1 =l+1, then i=d1 −1;else i∈[min(d0 ,d1 ),max(d0 ,d1 )−1]
(Cover , Push), if d0 > d1

(16)

{Seq(Insert(i, d)) × Link (Cover (i, d))}(17)

where (Left, Right) =∪Seq(d) =(Push, Cover ), if d0 < d1i∈[min(d0 ,d1 ), max(d0 ,d1 )]and i̸=d1

Exp. (15) shows that a complete-link set is recursively composed of the direct product ofall possible complete-sequence set pairs, with the N-tuple d itself.11 Exp. (17) shows that acomplete-sequence set is recursively composed of the direct product of all possible pairs of acomplete-link set and a smaller complete-sequence set.
In Exp. (15) and Exp. (17), if d0 = d1 , which violates the restriction of Exp. (8), we thenreplace d0 by ⟨/L⟩ and ⟨/R⟩ as follows. In fact, in this situation alone, ⟨/L⟩ and ⟨/R⟩ can appear
in a d as d0 , which is mentioned in the deﬁnition of Exp. (7) and related properties. The complete
sets containing ⟨/O⟩ (O ∈ {L, R}) tags start the recursive deﬁnition.

4.3

Left(x, d) = Left(⟨/R⟩, d),if x = min(d0 , d1 ) in Exp. (15)(18)

Right(x, d) = Right (⟨/L⟩, d),if x = max(d0 , d1 ) in Exp. (15)(19)

Insert(x, d) = Push(⟨/L⟩, d),if x = d0 , and d0 < d1 in Exp. (17)(20)

Insert(x, d) = Push(⟨/R⟩, d),if x = d0 , and d0 > d1 in Exp. (17)(21)

Estimation

According to the recursive deﬁnitions, it is natural to derive an inside-outside algorithm (Lariand Young 1990), which is an adaption of the EM algorithm (Dempster, Laird, and Rubin 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. (15) and Exp. (17) to Exp. (22) and Exp. (23), respectively. In Exp. (22), Sub1 and Sub2 mean the Seq(Left(·)) and the Seq(Right(·)), respectively,on the right-hand side of Exp. (15). In Exp. (23), Sub1 and Sub2 mean the Seq(Insert(·)) andthe Link (Cover (·)), respectively, on the right-hand side of Exp. (17). The notation ⟨·, ·⟩ in Exp.
(22) and Exp. (23) represents an unordered two-tuple of a complete-set pair.
11 We further restrict the root mark ⟨/s⟩ to take only one modiﬁer (the situation when daccording to the general restrictions of the dependency grammar.

991

1 = l + 1 in Exp. (15)),

Journal of Natural Language Processing

Link (d) =Vol. 21 No. 5∪

September 2014

{Sub 1 × Sub 2 × {d}}(22)∀⟨Sub 1 ,Sub 2 ⟩Seq(d) =∪{Sub 1 × Sub 2 }(23)∀⟨Sub 1 ,Sub 2 ⟩We further deﬁne RLink (Link (d), ⟨Sub 1 , Sub 2 ⟩) as a relation for Link (d), ⟨Sub 1 , Sub 2 ⟩ satisfying
Exp. (22). Similarly, RSeq (Seq(d), ⟨Sub 1 , Sub 2 ⟩) is a relation for Seq(d), ⟨Sub 1 , Sub 2 ⟩ satisfying
Exp. (23). Then, the inside probability β and outside probability α of the two types of complete
set can be calculated by Exp. (24) to Exp. (27), where p(d) is the probability of the lexical
dependency N-gram, represented by d in a sentence.
β(Link (d)) =∑β(Sub 1 ) · β(Sub 2 ) · p(d)(24)⟨Sub1 ,Sub 2 ⟩, s.t.
RLink (Link (d),⟨Sub 1 ,Sub 2 ⟩)β(Seq(d)) =∑β(Sub 1 ) · β(Sub 2 )(25)⟨Sub 1 ,Sub 2 ⟩, s.t.
RSeq (Seq(d),⟨Sub 1 ,Sub 2 ⟩)α(Link (d)) =∑α(Sup) · β(Con)(26)⟨Sup,Con⟩, s.t.
RSeq (Sup,⟨Link (d),Con⟩)α(Seq(d)) =∑α(Sup) · β(Con) · p(d′ ) +⟨Sup,Con⟩, s.t.
RLink (Sup,⟨Seq(d),Con⟩)∑α(Sup) · β(Con)⟨Sup,Con⟩, s.t.
RSeq (Sup,⟨Seq(d),Con⟩)(27)(where d′ is the N-tuple of Sup)
Speciﬁcally, Exp. (24) and Exp. (25) can be directly derived from the respective deﬁnitionsof Exp. (15) and Exp. (17). Further, a complete-link set can only be a component of a completesequence set from Exp. (17), while a complete-sequence set can be both a component of acomplete-link set from Exp. (15) and a component of a complete-sequence set from Exp. (17).
Consequently, Exp. (26) and Exp. (27) can both be derived.
For all Seq(d) with ⟨/L⟩ or ⟨/R⟩, we useβ(Seq(d)) = p(d)(28)

as the start of the calculation. At the end of the calculation, the probability of the entire sentence
S = w0l+1 can be obtained as follows:
P (S) = β(Seq(d = (1, l + 1, 0, · · · , 0)))

992

(29)

Ding and Yamamoto

A Generative Dependency N-gram Language Model

For re-estimation, we can obtain the probabilistic counts12 of a dependency N-gram represented by d in a sentence using:β(Link (d)) · α(Link (d))
P (S)

13

(30)

according to the inside-outside algorithm. Finally, all the counts of the dependency N-gram in
the training corpus are added and normalized using Exp. (1) to update the model parameters.
We show the details of the re-estimation algorithm with pseudocode in Appendix A.

5 Experiments
5.1

Experiment Setting

As the proposed dependency N-gram model and estimation algorithm are independent fromlanguage, we conduct experiments using four diﬀerent languages, i.e., English, German, Spanish
and Japanese. The corpora we use for English, German and Spanish are sets of sentences with
5–15 words from the corresponding single-language corpora of Europarl14 (Koehn 2005). The
corpus for Japanese is a set of sentences with 5–20 words from the Japanese side of the NTCIR8 corpus (Fujii, Utiyama, Yamamoto, Utsuro, Ehara, Echizen-ya, and Shimohata 2010). We
1
take 200of the sentences from a corpus to form each of the development and test sets usedin experiments, and the remaining sentences are used for training. The details of training,development (denoted dev.) and test sets are shown in Table 1 and 2.
To investigate the fundamental properties of the model and algorithm, we do not use any
pruning or approximating methods in the parameter estimation. Speciﬁcally, we collect all possible lexical dependency N-grams15 from the raw corpora without any cut-oﬀ thresholds for models
Table 1 Training setslanguage
EnglishGermanSpanishJapanesesentences
400, 100
422, 951
370, 791
477, 118

types
40, 913105, 303
58, 31447, 930

Table 2 Sentences in dev. and test setstokens4, 355, 333
4, 545, 263
4, 007, 816
7, 758, 437

language
EnglishGermanSpanishJapanesedev. set
2, 0202, 136
1, 872
2, 409test set
2, 0212, 136
1, 8732, 41012 They are no longer integers.
13 For the situation in Exp. (28), we use β(Seq(d))·α(Seq(d)) .
P (S)14 http://www.statmt.org/europarl/
15 As Japanese is a typical head-ﬁnal language, that is, the head word always comes after its modiﬁers, we only

take the left-oriented (from head to modiﬁer) dependency links into account. For the other three languages,
dependency links of both orientations are considered. The parameter collection and initialization do not takethe structure into account.

993

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014of any order. Before estimation, we use relative frequency to initialize the probabilities.

5.2

Results

5.2.1

Algorithm Convergence

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 be observed. For the dependency bi-gram,the training set perplexity becomes nearly stable after ﬁve iterations. However, for the dependency tri-gram, the ﬁrst iteration is at very low training set perplexity, and it does not changemuch in further iterations. This phenomenon suggests that the non-pruned dependency tri-grammodel may be complex with many parameters, so the features of the training set are represented
well, resulting in a low perplexity. This suggests the model is overﬁtting the data. We discuss
this in Section 5.3.
5.2.2

Test Set Perplexity

As well as the training set perplexity, the perplexity of a test set which has not been used inparameter estimation should be investigated in evaluation. Because diﬀerent order dependency
N-gram models are trained separately, we use linear interpolation in calculating the test set perplexity. Speciﬁcally, we use the held-out development set to tune the interpolation coeﬃcients(weights) and to select the iteration times of diﬀerent order models to minimize the development
set perplexity. Next we use the tuned weights to combine the iteration-time-selected models in
the test set perplexity calculation. The reason for using simple and straightforward linear interpolation is that we want to discover the essential aspects of the proposed model 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 model with modiﬁed KN discounting to handle the unknown words. The
uni-gram model is interpolated with the dependency bi-gram model. Furthermore, as the ⟨/L⟩

Fig. 9 English training set perplexities before each iteration (y-axis is logarithmic)

994

Ding and Yamamoto

A Generative Dependency N-gram Language Modeland ⟨/R⟩ tags are taken as general words, which never really appear in a training set, we treat
them separately, and interpolate them with the uni-gram model. Because the ⟨s⟩, ⟨L⟩ and ⟨R⟩tags only appear in the history, no other model is needed to handle them.
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, and the other is constructed by the state-of-the-art
interpolated modiﬁed KN discounting. We calculate the test set perplexities of the two N-gram
language models on the same test sets. The results are listed in Table 4. In both Table 3 and4, the perplexities are calculated according to the number of lexical words, and the tags used fornormalization are not counted17 . We discuss these results in Section 5.3.

Table 3 Development set perplexities (dev-ppl) and test set perplexities (test-ppl) of dependency Ngram models (N = 2 (bi), 3 (tri))
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

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 , respectively. (1 − λbi )and (1 − λtri ) are assigned to the interpolated lower order models and (1 − λuni ) is assigned to the ⟨/L⟩and ⟨/R⟩ tags.
Table 4 Test set perplexities of the original N-gram models
language
EnglishGermanSpanishJapanese

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

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

MLE is the maximum likelihood estimation, realized by setting the adding delta to 0 in adding smoothing.
MKN is the interpolated modified KN discounting.

16 http://www.speech.sri.com/projects/srilm/
17 That is, we do not count the ⟨/s⟩ tag in the original N-gram language models, or ⟨/L⟩ and ⟨/R⟩, in our models.

If they are included, the perplexities decrease. In the original N-gram model, this is because a ⟨/s⟩ tag nearly
always appears after the period mark. The eﬀect is even more dramatic in our model, as each word in a
sentence has a ⟨/L⟩ and a ⟨/R⟩ tag to normalize its modiﬁer numbers, so the token number in a sentence ismultiplied. Therefore, for fairness, we only count the lexical words in the perplexity calculation.

995

Journal of Natural Language Processing

5.3

Discussion

5.3.1

Parameter Number

Vol. 21 No. 5

September 2014

For a sentence with l words, the number of dependency N-grams that can be collected increases exponentially as O(lN ) if we consider all possible combinations. Although for a given
N , the proposed algorithm takes a time which is polynomial in sentence length l, a large N will
be practically intractable, especially for long sentences. In Figure 10, we show the number ofcomplete sets of diﬀerent order dependency N-gram models for diﬀerent sentence lengths.
This behavior is also related to the overﬁtting problem, because our algorithm is essentiallyan iterative maximum likelihood estimation. A model that is very complex will be extremely
speciﬁc to the training set. From Table 3, we see that the performance of a dependency tri-grammodel will saturate after only one iteration, which is also indicated in Figure 9, and does little
to improve the test set perplexities. The exception is Japanese, where the dependency tri-gram
does improve the performance. The linguistic reason for this is that Japanese is a head-ﬁnal
language with a simpler syntactic structure, so we restrict the dependency link in Japanese to“left only”, which leads to a model with fewer parameters. Consequently, the high order model
performs better. From the experimental results, we can see that the proposed algorithm has theusual strengths and weaknesses of an EM algorithm.
5.3.2

Test Set Perplexity

Comparing the test set perplexities in Table 3 and 4, we can see the dependency bi-grammodel achieves the same, or sometimes better, performance as the original N-gram language
models. However, when we look at the tri-grams, the interpolated modiﬁed KN discounting
method, which is the state-of-the-art, shows its strength, and our dependency model does notproduce much improvement for the reasons we described above18 . As the modiﬁed KN method

Fig. 10 Number of complete sets (y-axis is logarithmic)
18 For Japanese, the result is improved by the dependency tri-gram model, but the original tri-gram model withinterpolated modiﬁed KN discounting method performs much better.

996

Ding and Yamamoto

A Generative Dependency N-gram Language Model

uses an eﬃcient discounting to avoid the overﬁtting problem and our model has no smoothing, thediﬀerence in performance is reasonable for complex models. Conversely, the competitive resultsof our bi-gram model and its performance on Japanese show that our model is a promising one,particularly if the number of parameters can be reduced.
5.3.3

Model Preference

In Figure 11 to 23, we present the examples of the best dependency structures of sentences intest set generated by our approach. We used the settings in Table 3 and generated them using theViterbi algorithm (Viterbi 1967). It can be seen that the proposed approach can reveal featuresof speciﬁc languages, even though it is unsupervised, such as for the ﬁnal-position verb “stellen”
and its relation with the second-position auxiliary verb “möchte” in the German sentence inFigure 15. The results also show a preference for associating semantic relations and making thefunction words19 of a language the modiﬁers of the content words. This tendency is noticeable in
the English examples, such as the particle “to” in Figure 12 and 14 and the “’s” in Figure 14. In
addition, the arrangement of commas around “however” in Figure 11 and around “therefore” inFigure 14 is impressive. Another example is in the Spanish sentence in Figure 19. Syntactically,
the preposition “a” is the head of the noun “respecto”, but in unsupervised training, our model
prefers to assign “a” to be the modiﬁer of “respecto” and directly link two content words, i.e.
“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 modiﬁers. This tendency, however, is correct for articles, such as the “der” inGerman and “la” in Spanish. Furthermore, an interesting phenomenon can be observed in theJapanese sentence in Figure 23. In the example, the verb stem 応用 is linked to the auxiliaryverb できる , and the words of する こと が are arranged as a dependency chain and attached
to できる as well. Semantically, the expressions of 応用 できる (literally: can apply) and
応用 する こと が できる (literally: the thing, that applies, can) have nearly the same meaning

and are generally interchangeable. Consequently, the model prefers to designate する こと が ,which has a weak semantic function, as a branch and link the semantically-crucial words 応用
and できる directly. All these examples suggest that the proposed model with unsupervised
training has a strong preference for organizing a sentence by semantic relations and for assigning
relations between those words that play a central role in such a semantic unit.

19 Articles, prepositions, etc.

997

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Example of English Sentences

Fig. 11 Best dependency structure of the sentence “i would , however , add one important caveat .”Fig. 12 Best dependency structure of the sentence “let us remember what we are trying to do .”Fig. 13 Best dependency structure of the sentence “we have , therefore , voted against your selfcongratulation .”Fig. 14 Best dependency structure of the sentence “you are too late to change today ’s agenda .”998

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Example of German Sentences

Fig. 15 Best dependency structure of the sentence “trotzdem möchte ich der kommission einige
fragen stellen .”Fig. 16 Best dependency structure of the sentence “vielen dank , ich emphehle die annahmen desbericht .”Fig. 17 Best dependency structure of the sentence “sonst verlieren die bürger in den mitgliedstaaten
das vertauen .”Fig. 18 Best dependency structure of the sentence “zum beitritt techechiens habe ich mich der stimme
enthalten .”999

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Example of Spanish Sentences

Fig. 19 Best dependency structure of the sentence “la comisión está haciendo muchas cosas a este
respecto .”Fig. 20 Best dependency structure of the sentence “el tratado de lisboa contiene una cláusula social
horizontal .”Example of Japanese Sentences

Fig. 21 Best dependency structure of the sentence 図 3 は 、 その 実際 の 配置 例 で ある 。

Fig. 22 Best dependency structure of the sentence 以下 に 、 この 設定 方法 を 説明 する 。

1000

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Fig. 23 Best dependency structure of the sentence この よう な 場合 に も 本発明 を 応用 する ことが できる 。

6 Application to Microblog Data
6.1

Task and Corpus

Microblogging is an emerging application that provides a new platform for communicating.
Postings on microblogs are usually brief due to restrictions on message length such that no morethan 140 characters may be used. Moreover, microblogs use many non-standard expressions andInternet-based neologisms. These words and expressions are hard for general natural language
processing tools, which are usually trained on standard data sets, to handle. Therefore, tasks
using microblogs as a huge data source must consider the characteristics of user-generated content. One example of this is the part-of-speech tagging task on microblogs (Gimpel, Schneider,
O’Connor, Das, Mills, Eisenstein, Heilman, Yogatama, Flanigan, and Smith 2010). However, themore explicit and structured we want the information extracted from a microblog to be, the morediﬃcult the task turns out to be, due to the ﬂexible and non-standard use of the expressions.
Because our proposed approach is completely data driven, we think it can eﬃciently capture features in user-generated content. In this section, using our proposed model, we focus on
extracting and investigating lexical dependency features from Chinese microblog data.
We use the NLPIR Chinese Weibo corpus20 in our experiment. The corpus contains 230, 000
posts collected from Sina Weibo and Tencent Weibo. During preprocessing, we split the posts into
sentences, delete the tags beginning with @ and # and all the URLs. We use the Stanford Chinese
Word Segmenter21 (Tseng, Chang, Andrew, Jurafsky, and Manning 2005) with the Chinese Penn
Treebank standard to segment each Chinese sentence and take those sentences with 5–30 words
as the training corpus in our experiment. We further normalize the punctuation marks in the

20 http://www.nlpir.org/download/weibo content corpus.rar
21 http://www-nlp.stanford.edu/software/segmenter.shtml

1001

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Table 5 Chinese Weibo corpus
sentences
304,667

types
95,239tokens4,427,543

Fig. 24 Training set perplexities before each iteration (y-axis is logarithmic)

training corpus and replace all words appearing fewer than ﬁve times with a symbolic UNK token.
The details of the training corpus are shown in Table 5.
We collect all possible lexical dependency N-grams from the training corpus and use relative
frequency to initialize the probabilities. Figure 24 shows the change of training corpus perplexities
before each iteration for 2 (bi-) and 3 (tri-) order dependency N-gram models. We can observe thesame trend shown in Figure 9. However, our interest is the learned features of the training set.
We discuss the examples of lexical parameters and parsing using a three-time iterated dependency
bi-gram model and a one-time iterated dependency tri-gram model in the next section.

6.2

Discussion

In Table 6, 7 and 8, we show the examples of lexical dependency features with high estimatesof logarithmic probability (log-prob.) with our unsupervised approach.
In Table 6, the examples of dependency bi-grams around general words are shown. We cansee that the dependency relations between them are well modeled. Moreover, in Table 6, weshow the features of the root mark ⟨/s⟩ of sentences. We can see that the ﬁnal punctuation
marks and ﬁnal-position particles are automatically learned as modiﬁers of the root mark (i.e.,of the root word of a sentence). In Table 7, we show an example of a special Chinese expression
on the Internet. The word “神马”, read as shén-mǎ, means “what” on the basis of similarity inpronunciation to the original word shén-me. Our unsupervised data-driven approach reveals the
behaviors of this neologism, which is natural for a Chinese native speaker.
In Table 8, we show an example of a dependency tri-gram. The expression “有木有” (yǒumù-yǒu) is also an Internet-based neologism, which means “to exist or not”, because the original1002

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Table 6 Dependency bi-grams for the root mark (⟨/s⟩) and some general Chinese words
bi-gramlog-prob.

bi-gramlog-prob.

bi-gramlog-prob.

bi-gramlog-prob.

−0.520−1.358−2.278−1.371−1.098−1.628−2.755−1.436−1.235−1.915−2.892−1.925−1.928−2.139−3.058−2.085−1.955−2.261−3.262−2.102The top five highest estimates for each history (given o1 and h1 in (h0 , o1 , h1 )) are shown. The h0 shown
here excludes UNK, ⟨/L⟩, ⟨/R⟩ and punctuation marks for lexical h0 .
Table 7 Dependency bi-grams for a Chinese Internet neologism “神马”
bi-gramlog-prob.

bi-gramlog-prob.

bi-gram1

bi-gramlog-prob.

−0.972−1.343−1.343−0.713−0.537−1.552−1.532−0.736−0.732−1.741−1.803−0.840−1.555−1.832−0.957−1.746In (h , o , h ), h = 神马, o = ⟨L⟩ or ⟨R⟩. The top
five highest estimates are shown.
1

log-prob.

−1.327−1.8130

Table 8 Dependency tri-grams for a ChineseInternet neologism “有木有” and forthe corresponding standard expression “有没有”11The estimates of all four possible structure patterns of both expressions are shown.

expression “有没有” (yǒu-méi-yǒu) has a similar pronunciation in some dialects. We show all
four possible structure patterns for both of them. We can see that all of these structures haverelatively high estimates, which shows strong dependency relations. However, if we use a general
Chinese parser22 , the character “木” is always treated as a noun due to its original meaning of“wood”, and the tri-order relation of the expression “有木有” is not recognized.
In Figure 25, we show the best dependency structure given by the Viterbi algorithm for a
22 http://nlp.stanford.edu:8080/parser/index.jsp

1003

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Fig. 25 Best dependency structure of the sentence “毎 道 菜 都 真心 好吃 呢。” generated by the
proposed approach

Fig. 26 Dependency structure of the sentence “毎 道 菜 都 真心 好吃 呢。” generated by the Stanford
Dependency Parser

sentence in the training set. Figure 26 is the dependency structure generated by the Stanford
Dependency Parser6.2 . Although there are no neologisms in this sentence, the Chinese word
“真心” is a general word and ordinarily used as a noun or an adjective, meaning “sincerity” or“sincere” respectively. However, it has recently been used as an adverb to express the meaning of“really” in a slightly emphatic manner. This feature is also captured by our approach from training data and contextualized within the entire sentence structure, resulting in a correct analysis.
A standard parser cannot eﬃciently handle this type of ﬂexible usage of general words.

7 Conclusion and Future WorkIn this study, we focused on introducing sentence structure into language modeling. We
proposed a generative dependency N-gram language model, which extends the original N-gram
language model to include sentence dependency structures, as well as a deﬁnition of complete
sets for arbitrary order, which facilitates an unsupervised parameter estimation algorithm. The
experimental results demonstrate the applicability and the properties of the proposed approach.
We also applied a complete data-driven approach for lexical dependency feature extraction toa textual microblog data set. The experimental results show that our approach can handle
non-standard linguistic phenomena in user-generated content.
In future, we will develop methods for parameter pruning and discounting to handle the1004

Ding and Yamamoto

A Generative Dependency N-gram Language Model

overﬁtting problem. As the proposed dependency language model is intrinsically complex, we
also plan more fundamental simpliﬁcations. In addition, although our proposed algorithm isunsupervised, the output of a trained parser, which would provide clear and lexical heuristics,
can be integrated in it. We plan to investigate this possibility and evaluate the performanceachieved by using linguistically motivated criteria.

Acknowledgement
An earlier version of this study has been presented at the 6th International Joint Conference
on Natural Language Processing (IJCNLP 2013) (Ding and Yamamoto 2013). We would like tothank the anonymous reviewers for their valuable comments and suggestions. This study was
supported by JSPS KAKENHI Grant Number 24650063.

Reference
Brown, P. F., deSouza, P. V., Mercer, R. L., Pietra, V. J. D., and Lai, J. C. (1992). “Class-based
N-gram Models of Natural Language.” Computational Linguistics, 18 (4), pp. 467–479.
Chelba, C. and Jelinek, F. (2000). “Structured Language Modeling.” Computer Speech andLanguage, 14 (4), pp. 283–332.
Chen, S. F. and Goodman, J. (1998). “An Empirical Study of Smoothing Techniques for Language
Modeling.” Tech. rep., TR-10-98, Computer Science Group, Harvard Univ.
Collins, M. (1998). “Three Generative, Lexicalised Models for Statistical Parsing.” In Proceedingsof ACL 1998, pp. 16–23.
Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). “Maximum Likelihood from Incomplete
Data via the EM Algorithm.” Journal of the Royal Statistical Society. Series B (Methodological), 39 (1), pp. 1–38.
Ding, C. and Yamamoto, M. (2013).

“An Unsupervised Parameter Estimation Algorithm

for a Generative Dependency N-gram Language Model.” In Proceedings of IJCNLP2013,
pp. 516–524.
Eisner, J. M. (1996). “Three New Probabilistic Models for Dependency Parsing: An Exploration.”
In Proceedings of COLING1996, pp. 340–345.
Fujii, A., Utiyama, M., Yamamoto, M., Utsuro, T., Ehara, T., Echizen-ya, H., and Shimohata, S.
(2010). “Overview of the Patent Translation Task at the NTCIR-8 Workshop.” In Proceedingsof NTCIR-8, pp. 371–376.
1005

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Gao, J. and Suzuki, H. (2003). “Unsupervised Learning of Dependency Structure for Language
Modeling.” In Proceedings of ACL2003, pp. 521–580.
Gimpel, K., Schneider, N., O’Connor, B., Das, D., Mills, D., Eisenstein, J., Heilman, M., Yogatama, D., Flanigan, J., and Smith, N. A. (2010). “Part-of-Speech Tagging for Twitter:
Annotation, Features, and Experiments.” Tech. rep., DTIC Document.
Graham, Y. and van Genabith, J. (2010). “Deep Syntax Language Models and Statistical MachineTranslation.” In Proceedings of SSST at COLING2010, pp. 118–126.
Klein, D. and Manning, C. D. (2003). “Accurate Unlexicalized Parsing.” In Proceedings of
ACL2003, pp. 423–430.
Klein, D. and Manning, C. D. (2004). “Corpus-based Induction of Syntactic Structure: Modelsof Dependency and Constituency.” In Proceedings of ACL2004, pp. 478–485.
Koehn, P. (2005). “Europarl: A Parallel Corpus for Statistical Machine Translation.” In Proceedings of MT summit 2005, pp. 79–86.
Koo, T. and Collins, M. (2010). “Eﬃcient Third-order Dependency Parsers.” In Proceedings of
ACL2010, pp. 1–11.
Kudo, T. and Matsumoto, Y. (2002). “Japanese Dependency Analysis using Cascaded Chunking.”
In Proceedings of COLING2002, pp. 1–7.
Lari, K. and Young, S. J. (1990). “The Estimation of Stochastic Context-free Grammars using
the Inside-Outside Algorithm.” Computer Speech and Language, 4 (1), pp. 35–56.
Lee, S. and Choi, K.-S. (1997). “Reestimation and Best-ﬁrst Parsing Algorithm for Probabilistic
Dependency Grammars.” In Proceedings of WVLC1997, pp. 41–55.
Lee, S. and Choi, K.-S. (1998). “Automatic Acquistion of Language Model Based on Headdependent Relation between Words.” In Proceedings of COLING-ACL1998, pp. 723–727.
Nivre, J. (2008). “Algorithms for Deterministic Incremental Dependency Parsing.” Computational Linguistics, 34 (4), pp. 513–553.
Paskin, M. A. (2002). “Grammatical Bigrams.” Advances In Neural Information Processing
Systems 14, 1, pp. 91–97.
Stolcke, A. (2002). “SRILM—An Extensible Language Modeling Toolkit.” In Proceedings of
ICSLP2002, pp. 901–904.
Stolcke, A., Chelba, C., Engle, D., Jimenez, V., Mangu, L., Printz, H., Ristad, E., Rosenfeld, R.,
Wu, D., Jelinek, F., and Khudanpur, S. (1997). “Dependency Language Modeling.”.
Tillmann, C. and Ney, H. (1997). “Word Triggers and the EM Algorithm.” In Proceedings of
CoNNL 1997, pp. 117–124.
Tseng, H., Chang, P., Andrew, G., Jurafsky, D., and Manning, C. (2005). “A Conditional Random
1006

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Field Word Segmenter.” In SIGHAN2005, Workshop on Chinese Language Processing, Vol.
171.
Viterbi, A. (1967). “Error Bounds for Convolutional Codes and an Asymptotically Optimum
Decoding Algorithm.” Information Theory, IEEE Transactions on Information Theory, 13(2), pp. 260–269.
Wetherell, C. S. (1980). “Probabilistic Languages: A Review and Some Open Questions.” ACM
Computing Surveys (CSUR), 12 (4), pp. 361–379.
Zhang, H. and McDonald, R. (2012). “Generalized Higher-order Dependency Parsing with Cube
Pruning.” In Proceedings of EMNLP2012, pp. 320–331.

Appendix
A Calculation of the Estimation Algorithm
In Section 4.3, we provide a re-estimation method as an inside-outside algorithm. When theorder is restricted to two, as in (Lee and Choi 1997), the calculation of all the inside (β(·)) andoutside (α(·)) probabilities can be conducted on a CKY-wise triangle table. Speciﬁcally, theinside probabilities are ﬁrst calculated from small to large spans in a bottom-up way; then theoutside probabilities are calculated in a top-down way by using the calculated inside probabilities.
Because the proposed approach extends the dependency N-gram to an arbitrary order, a twodimensional triangle table is not suﬃcient. In general, the re-estimation of a model with N-orderlexical parameters needs an N-dimension table, which ceases to be intuitive.
A naive method of calculating the inside-outside probability of a sentence can be performedby the pseudocode of Naive-Inside-Outside. More eﬃciently, we can ﬁrst generate a processlist to record the processing order for all the necessary inside and outside probabilities of a sentence, and then calculate them according to the process list. In practice, the process given in
Naive-Inside-Outside, which identiﬁes the processing order, needs to execute only once, which
can be performed during pre-processing. The generation of the process list is shown by the pseudocode of Process-List. This code is basically identical to the process Naive-Inside-Outside;
instead of calculating, the “name” tokens (generated by Get-Tuple) of all the inside and outside
probabilities are recorded. For creating the process list, the calculation step of Inside-Outside istrivial, because the calculation is found from the recorded “name” by using Get-Probability.

1007

Journal of Natural Language Processing

Vol. 21 No. 5

September 2014

Naive-Inside-Outside(Sentence)
1
2
3
4
5
6
7
8
9
10
11
12
13

calculate β(Set) according to Exp. (28)repeatfor all inside probabilities β(Set) of Sentence
do  according to Exp. (24), Exp. (25)if all β(Sub1 ), β(Sub2 ) on the right side are available
then calculate β(Set)until all inside probabilities β(Set) are calculated
repeatfor all outside probabilities α(Set) of Sentence
do  according to Exp. (26) or Exp. (27)if all α(Sup) on the right side are available
then calculate α(Set)until all outside probabilities α(Set) are calculated

Inside-Outside(Sentence, ProcessList)
1
2

for i ← 1 to length (ProcessList)
do Get-Probability(ProcessList[i])Get-Probability(X, Y, Z)
1

return X (Y (Z)) according to Exp. (24), Exp. (25), Exp. (26), Exp. (27) or Exp. (28)Process-List()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Process-List ← []for all Seq(d) of Exp. (28)
do append Get-Tuple(β(Seq(d))) to Process-List
repeatfor all complete sets Set
do  according to Exp. (24) or Exp. (25)if all Get-Tuple(β(Sub1 )), Get-Tuple(β(Sub2 )) ∈ Process-Listthen append Get-Tuple(β(Set)) to Process-List
until Get-Tuple(β(Set)) ∈ Process-List for all Set
repeatfor all complete sets Set
do  according to Exp. (26) or Exp. (27)if all Get-Tuple(α(Sup)) ∈ Process-Listthen append Get-Tuple(α(Set)) to Process-List
until Get-Tuple(α(Set)) ∈ Process-List for all Set
return Process-List

Get-Tuple(X (Y (Z)))
1

return (X, Y, Z)

1008

Ding and Yamamoto

A Generative Dependency N-gram Language Model

Chenchen Ding: He received a B.S. degree in Mathematics from Shandong
University, China, in 2009. He received an M.E. degree in Computer Sciencefrom the University of Tsukuba, Japan, in 2012. Currently, he is a doctoral
student of the University of Tsukuba, working on natural language processing.
Mikio Yamamoto: He received the B.E, M.E and D.E degrees in informationand computer sciences from Toyohashi University of Technology, Japan, in
1984, 1986 and 1992, respectively. In 1988, he joined the Toyohashi University of Technology as a technical oﬃcial. In 1995, he moved to the Universityof Tsukuba as an assistant professor. Currently, he is a professor in the Department of Computer Science, University of Tsukuba, working on statisticalmethods for processing text.
(Received October 29, 2013)(Revised February 4, 2014)(Rerevised April 12, 2014)(Accepted May 22, 2014)1009