A New Efficient Probabilistic Modelfor Mining Labeled Ordered Trees
Kosuke Hashimoto, Kiyoko F. Aoki-Kinoshita, Nobuhisa Ueda,
Minoru Kanehisa, Hiroshi Mamitsuka
Bioinformatics Center, Institute for Chemical Research, Kyoto University
Gokasho Uji, 611-0011 Japan{khashimo,kiyoko,ueda,kanehisa,mami} at kuicr.kyoto-u.ac.jp

ABSTRACT
Mining frequent patterns is a general and important issue indata mining. Complex and unstructured (or semi-structured)datasets have appeared in major data mining applications,
including text mining, web mining and bioinformatics. Mining patterns from these datasets is the focus of many of thecurrent data mining approaches. We focus on labeled ordered trees, typical datasets of semi-structured data in data
mining, and propose a new probabilistic model and its eﬃcient learning scheme for mining labeled ordered trees. The
proposed approach signiﬁcantly improves the time and spacecomplexity of an existing probabilistic modeling for labeledordered trees, while maintaining its expressive power. We
evaluated the performance of the proposed model, comparing it with that of the existing model, using synthetic as well
as real datasets from the ﬁeld of glycobiology. Experimental
results showed that the proposed model drastically reduced
the computation time of the competing model, keeping thepredictive power and avoiding overﬁtting to the training
data. Finally, we assessed our results using the proposedmodel on real data from a variety of biological viewpoints,
verifying known facts in glycobiology.
Categories and Subject Descriptors: I.2.6 [Artiﬁcial
Intelligence]: Learning–knowledge acquisition, parameter learning ; I.5.1 [Pattern Recognition]: Models–Statistical
General Terms: Algorithms and Experimentation
Keywords: Labeled Ordered Trees, Probabilistic Models,Maximum Likelihood, Expectation-Maximization

1.

INTRODUCTION

Mining frequent patterns is a general and important issue
in data mining. The data in conventional data mining iswell structured, and so relatively simple patterns, such as
associations and sequences, are targeted. However, datasets

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
KDD’06, August 20–23, 2006, Philadelphia, Pennsylvania, USA.
Copyright 2006 ACM 1-59593-339-5/06/0008 ...$5.00.

of more complex and unstructured (or semi-structured) datasuch as trees and graphs have recently appeared in major
data mining applications, such as text mining [21], web mining [4] and bioinformatics [2]. A typical example is a treestructured text format called XML on the web [1]. Mining
XML documents has become an important domain in theﬁeld of data mining [22]. XML documents are datasets ofsemi-structured data, or more speciﬁcally, labeled ordered
trees, and methods based on kernel functions [11] and frequent pattern mining [23] have appeared in recent years.
Probabilistic modeling and learning is a noise-robust, powerful and eﬃcient approach in machine learning and data
mining. Bayesian networks [16], which can handle directed
acyclic graphs, have been used quite frequently since its introduction. However, directed acyclic graphs are much more
complex than labeled ordered trees, and so simpler probabilistic models and more eﬃcient learning algorithms fortrees have been proposed. For example, the hidden tree
Markov model (HTMM) [6] is a probabilistic model for labeled trees that handles parent-child dependencies in a given
tree. However, it does not handle sibling dependencies,
meaning that HTMM is not applicable to labeled ordered
trees. The probabilistic sibling-dependent Tree Markov Model(PSTMM) [18, 19] has been developed for labeled ordered
trees, containing both parent-child and sibling dependencies. These models, which are subclasses of Bayesian networks, signiﬁcantly reduce the high complexity of Bayesian
networks by restricting the target to labeled trees or labeledordered trees [19]. The extension of HTMM to PSTMM
for trees is equivalent to that of the hidden Markov model(HMM) [3, 17] to the probabilistic context free grammars(PCFGs) [12, 14] for sequences (strings). Consequently,
the time and space complexity of the learning algorithmof HTMM roughly increases by a factor of the number ofstates in PSTMM. This is a sizable diﬀerence, since labeledordered trees in the real world, such as XML documents, areoften large (or long), while natural language sentences dealt
with by PCFG are rather short. Applying PSTMM to suchlarge data would make it intractable due to its high time andspace complexity. On the other hand, for small-sized datasuch as those found in glycobiology, PSTMM would overﬁt.
Thus, it is necessary to reduce its complexity in order for
it to be applicable to real-world problems involving labeledordered trees.
In light of the above, we propose a new and eﬃcient
probabilistic model, which we call the ordered tree Markov

model (OTMM). We present the time and space eﬃcient algorithms for the three problems arising when OTMM is applied to real-world problems: likelihood computation, learning (estimating) the probabilistic parameters based on maximum likelihood, and parsing (ﬁnding the most likely path).
OTMM has sibling dependencies as well as parent-child dependencies, but the parent-child dependencies are conﬁned
to those between just the eldest siblings and their parents.
Consequently, our model reduces the complexity of PSTMM
to the same level as that of HTMM. The maximum likelihood estimation of the parameters of OTMM is based onan EM (Expectation-Maximization) algorithm [5, 15]. Thisis an extension of the Baum-Welch (Forward-Backward) algorithm for HMMs, which updates the forward and backward probabilities based on dynamic programming. Thisextension is similar to that of HTMM and PSTMM, but
we emphasize that these estimation algorithms are signiﬁcantly diﬀerent from each other. HTMM deals with parentchild dependencies only, and so the learning algorithm ofHTMM is a straightforward modiﬁcation of the forward andbackward algorithm in a string to compute the parent-tochild (downward) and child-to-parent (upward) probabilities. On the other hand, PSTMM handle both the parentchild and sibling dependencies, and so the algorithm must
deal with both upward and downward probabilities as well
as forward and backward probabilities. In PSTMM, every
child depends on its parent, and the upward (downward)
probability of a node can be directly updated from its child(parent) easily. In contrast, the parent-child dependencies in
OTMM are limited to the dependencies of the eldest siblingson their parents. Thus, for OTMM, we needed to develop
an algorithm by which we could compute the four (upward,
downward, forward and backward) probabilities under theconstraint of using the limited parent-child dependencies.
We empirically evaluated the eﬀectiveness of our proposed
scheme using synthetically generated datasets as well as real
datasets in bioinformatics. From the results we obtained, we
found that for any test setting, our approach signiﬁcantly
reduced the computation time for learning PSTMM andavoided overﬁtting to the training data, while either maintaining or even improving the predictive power of PSTMM.
In particular, we emphasize that a typical increase in computation time ranged from four- to seven-fold in our experimental setting, and that this factor increases as the number ofstates increase. In addition to these comparison results, weanalyzed biological data by our method using data from glycobiology, which is the study of carbohydrate sugar chains,or glycans, that can be modeled as labeled ordered trees.
Glycans are considered the third major class of biomolecules
next to DNA and proteins [20], and it is known that the ordering of their leaves is used in recognition and signaling
events in various biological processes. Thus we studied thepatterns learned from this data and veriﬁed known facts related to sibling-dependencies in glycans that were captured
by our model.

2.

NOTATIONSWe describe the notations that will be used throughout
this paper. A tree is an acyclic connected graph. In thispaper, we refer to a vertex of a tree as a node of the tree. A
rooted tree is a tree that has a special node called the root.
Any node x on a unique path from the root to a node yis called an ancestor of node y, in which case y is called adescendant of x. Each of the closest descendants of x (thatis, a node that is only one edge away from node x) is calleda child of x, in which case x is called the parent of the child.
We call nodes x and y siblings if x and y have the same
parent. We call a node having no children a leaf. A subtreeof tree T is a tree consisting of all descendants of a node.
An ordered tree is a rooted tree in which the children of eachnode are ordered. A labeled tree is a tree in which a label is
attached to each node. We will often simply use the term
tree in place of an ordered, labeled and rooted tree.
Let T = {T1 , . . . , T|T| } be a set of labeled ordered trees,
where Tu = (Vu , Eu ) and Vu (= {xu1 , . . . , xu|Vu | }) and Eu ⊆Vu × Vu are a set of nodes and a set of edges, respectively.
Let xu1 be the root of tree Tu , and |V | = maxu |Vu |. We
assume that nodes are indexed by level order, which canbe done by traversing the tree in breadth-ﬁrst order. An
example of trees with their indices is shown in Figure 1.
From this indexing of nodes, for a node j, we can refer tothe immediately elder and younger siblings of j as j − 1 andj + 1, respectively. Let tu (i) be a subtree of Tu , having xui
as the root of tu (i). Let xu← (p) and xu→ (p) be the eldest
and youngest children of node p, respectively. Let Cu (p) ⊆{1, . . . , |Vu |} be a set of indices of children of xup in Tu and|C| = maxu,p |Cu (p)|. Let Xu (j) be a set of indices of all
the younger siblings of xuj in Tu . Each node xuj has label
ouj ∈ Σ, where Σ = {σ1 , . . . , σ|Σ| } is a set of labels. For
simplicity, we will often use node j instead of xuj and p as aparent node, if understood from the context.
Let θ denote a set of parameters of a probabilistic model.
For simplicity, we may use θ = {θ1 , . . . , θn } as a set of paP i|
rameters, such that θi = {θi,1 , . . . , θi,|θi | } and |θ
j=1 θi,j = 1
for i = 1, . . . , n. A probabilistic model has ‘states,’ each ofwhich is a so-called latent (or hidden) variable that cannot
be seen directly, and each state has a probabilistic parameter which probabilistically generates a label at a node. Let
S = {s1 , . . . , s|S| } be a set of states, and zju ∈ S be the stateof node j in a tree. For simplicity, we may also use j insteadof zju and q as the state of a parent node, if understood fromthe context.

3. PROPOSED MODEL: ORDERED TREEMARKOV MODEL (OTMM)
We propose a new eﬃcient probabilistic model for mininglabeled ordered trees which we hereafter call OTMM, for Ordered Tree Markov model. Here we brieﬂy describe the differences between OTMM and two other similar tree Markov
models, called the Hidden Tree Markov Model (HTMM) [6]and the Probabilistic Sibling-dependent Tree Markov Model(PSTMM) [18, 19].
OTMM is a ﬁrst-order Markov chain model, meaning thata state depends on only one state. This is also true of
HTMM, which is a probabilistic model for labeled trees.
Figure 2 illustrates the dependencies in HTMM for the tree
Tu in Figure 1 (a), where the state of a node depends on
the state of its parent node. In OTMM, the state of a nodedepends on either the state of its parent or its immediately
elder sibling. Figure 3 shows the dependencies in OTMM
for the tree Tu in Figure 1 (a). As shown in the ﬁgure, if thenode of a state is the eldest sibling, this state depends on
its parent; otherwise, this state depends on its immediately
elder sibling. Thus an important diﬀerence between OTMM
and HTMM is that sibling dependencies are considered in

(a)

(b)

x

u

u
1 o1

Tu

x2u ou2 x

u u
3 o3

x4u o4pu

x5u ou5 x6u ou6 x7u ou7 x8u ou8 x9u ou9

j 1

j

j +1

Figure 1: Notations for labeled ordered trees. (a) Labeled ordered tree Tu . (b) Indices for a parent and its
children.
u

z1

u

z2

u

z5

u

u

z3

u

z7

o2

u

u

o5

z6

u

u

z4

u

z8

o3

u

o6

u

z1

u

o1
u

u

o7

z2

u

o4
u

u

o8

z9

u

u

o1

Figure 2: Graphical representation of HTMM fortree Tu in Figure 1.
u

z1

u

z2

u

z5

u

u

z3

u
o6

z7

o2

u

u
o5

z6

u

o1
u

u

z4

u
o7

z8

o3

u

u

o4

u

u

u
o8

z9

u

o1

Figure 3: Graphical representation of OTMM fortree Tu in Figure 1.
OTMM but not in HTMM. Obviously, this diﬀerence makes
the expressive power of OTMM for labeled ordered trees
greater than that of HTMM.
On the other hand, PSTMM is a probabilistic model forlabeled ordered trees, and the state of a node always depends on two diﬀerent states, except for the eldest siblings.
Figure 4 illustrates the dependencies in PSTMM for the tree
in Figure 1 (a). As shown in the ﬁgure, the dependencies
on the immediately elder sibling and on the parent are bothconsidered in PSTMM. This feature gives PSTMM rich expressive power, but it is computationally expensive and requires more memory space in estimating the probabilistic
parameters of PSTMM. In addition, this high complexity of
PSTMM has the additional risk of overﬁtting to data. In
fact, these problems have appeared when applying PSTMM
to real data. OTMM avoids these problems and achieves
better performance in practical situations where PSTMM
suﬀers from the above problems.
In addition, recall that hidden Markov models (HMMs)
enable the indirect capture of distant (long-range) dependencies in a sequence. We emphasize that OTMM can also
capture such indirect dependencies in a similar manner. For
example, a dependency between a node and its distant sibling, which cannot be captured by HTMM, may be detectedby OTMM (and PSTMM). A dependency between a nodeand its distant sibling’s descendant may also be captured

z5

u

u

z3

u

z7

o2

u

u

o5

z6

u

o1
u

u

z4

u

z8

o3

u

o6

u

o4

u

o7

u

u

o8

z9

u

o1

Figure 4: Graphical representation of PSTMM fortree Tu in Figure 1.
by OTMM (and PSTMM) but clearly not by HTMM. Fromthe viewpoint of capturing such indirect dependencies, we
can say that the expressive power of OTMM is at the samelevel as that of PSTMM and that it is greater than that ofHTMM.
The algorithms for OTMM are derived by making somesigniﬁcant modiﬁcations to the algorithms of PSTMM, although OTMM is a simpliﬁcation of PSTMM. These modiﬁcations are necessary to account for the reduced dependencies between parent and child. Thus in OTMM, the ancestor information cannot be transfered through parent-childdependencies directly except to the eldest siblings, although
before, this information was easily (and directly) sent froma parent to all its children in PSTMM. As a result, it wasnecessary to reconstruct both the deﬁnitions of some probabilities and the equations using these probabilities in the
dynamic programming procedure for learning PSTMM.
OTMM has three types of probability parameters, π, a,and b. The initial state probability π[l] (= P (z1u = sl ; θ)) is
the probability that the state z1u of the root node xu1 is sl .
The state transition probability a further takes two types:
α[q, m](= P (zju = sm |zpu = sq ; θ)) and β[l, m](= P (zju =u= sl ; θ)). α[q, m] is the conditional probability thatsm |zj−1
the state of a node is sm given that the state of its parent
is sq . β[l, m] is the conditional probability that the state ofa node is sm given that the state of the immediately elder
sibling is sl . The label output probability b[l, σh ](= P (ouj =σh |zju = sl ; θ)) is the conditional probability that the output
label of a nodeP that the state ofPthis node is sl .
P is σh given
NotePthatl π[l] = 1,m α[q, m] = 1,m β[l, m] = 1,
and h b[l, σh ] = 1.
Given the probabilistic model, there are three key problems of interest that must be solved for the model to be
used in real world applications [17]: 1) Likelihood computation: computing the likelihood of a given tree, 2) Learning:
estimating the probability parameters from a set of given
trees, and 3) Parsing (Prediction): ﬁnding the most likely
state transition for a given tree using the estimated probability parameters. In the following three subsections, weuct of the likelihood for each tree in the set.

xp s qα[q,m]

xj s msm xj:eldest

L(T) =

β[m, l]xj+1 sl

u=1

sibling

Uu(m, j)Bu(m, j)|T|
Y

Bu(l, j+1)

Figure 5:Updating (left) Uu (q, p) and (right)
Bu (m, j). The sparse shaded node is p for Uu (q, p)
and j for Bu (m, j). Dense shaded areas are used for
updating.

L(Tu ) =|T| |S|YX

π[l]Uu (l, 1).

u=1 l=1

The above computation is relatively similar to that of
PSTMM. A signiﬁcant diﬀerence is that the backward probability of OTMM is a tri-tuple, while that of PSTMM is aquatro-tuple. This feature of OTMM reduces both the timeand space complexity of PSTMM.

3.2 Learning: Maximum Likelihood Estimation

will explain our eﬃcient algorithms for OTMM for each of
the above three problems.

Maximum likelihood is a general criterion used to estimate
the probability parameters of a probabilistic model from thegiven training examples. We employ an EM algorithm [5,15], a general and popular scheme to maximize the likelihood
for a given set of examples.

3.1 Likelihood Computation

3.2.1 Forward and Downward Probabilities

3.1.1 Upward and Backward Probabilities
We deﬁne an upward probability and a backward probability. The upward probability Uu (q, p) is the probability
that all labels of subtree tu (p) are generated and the stateof node p is sq . The backward probability Bu (l, j) is theprobability that for node j, all labels of a subtree for eachof the younger siblings and node j are generated, and thestate of j is sl .
We can compute these two probabilities using a bottomup (B-up) dynamic programming (DP) procedure. This
computation is formulated as follows:8
If Cu (p) = ∅ then b[q, oup ]>>>> otherwise
>
<
|S|
X
(1)
Uu (q, p) =
u
>
b[q,
o
]
α[q, m]Bu (m, j)
p
>
>
>
m=1
>
:
(s.t. xuj = xu← (p))

Bu (m, j)

We deﬁne forward and downward probabilities and use
them with the backward and upward probabilities, bothof which were deﬁned in the previous section. The forward probability Fu (l, j) is the probability that all labels oftree Tu except for those of subtree tu (j) and of all subtreestu (k) (k ∈ Xu (j)) are generated and that the state of node
xuj is sl . The downward probability Du (l, j) is the probability that all labels of tree Tu except for those of subtree tu (j)are generated and that the state of xuj is sl .
We can compute these two probabilities using a top-down(T-down) dynamic programming procedure. This computation is formulated as follows:
8
|S|
X
>
>
u
u
>
If
x
=
x
(p)
then
α[q, l]Du (q, p)b[q, oup ],
>
←
j
>
>
<
q
Fu (l, j) =otherwise
>
>
|S|
>
X
>
>
>
β[m, l]Fu (m, j − 1)Uu (m, j − 1):m=1

8
If xuj = xu→ (p) then Uu (m, j),>>> otherwise
<
=

|S|

X
>
>
β[m, l]Bu (l, j + 1)>
: Uu (m, j)

(2)

l=1

Figure 5 depicts the above calculation of the upward andbackward probabilities. The upward probability at a node iscomputed using the backward probability of its eldest child,so this computation is repeated from the (eldest) child to
its parent. The backward probability at a node is computed
using the backward probability of its immediately younger
sibling, meaning that this computation is successively repeated from a node to its immediately elder sibling. So thewhole computation proceeds from the leaves to the root, inreverse breadth-ﬁrst order, going bottom-up and right-toleft (R-to-L) using dynamic programming.
We can compute the likelihood for a given tree Tu by using
the upward probability at the root of the tree, as follows:
L(Tu ) =|S|
X

π[l]Uu (l, 1).

l=1

The likelihood for a given set of trees is deﬁned as the prod-

Du (l, j)=

8
If j = 1 then π[l],
>
>
>
u
u
>
>
< else if xj = x→ (p) then Fu (l, j),otherwise
|S|
>
X
>
>
>
F
(l,
j)
β[l, m]Bu (m, j + 1)
>
u
:
m=1

Figure 6 depicts these calculations for the forward probability at the eldest sibling and at another node. The forward probability at the eldest sibling is computed using thedownward probability of its parent, meaning that this computation is repeated from a parent to its eldest child. The
forward probability at another node is computed using theforward and upward probabilities of its immediately elder
sibling, meaning that this computation is repeated from anode to its immediately younger sibling. Figure 7 depicts
the calculation of the downward probability. The downward
probability at a node is computed using its forward probability (and the backward probability of its younger sibling),and so at each node the downward probability must be computed after the forward probability is computed. Overall,the entire computation proceeds from the root to the leaves,in breadth-ﬁrst order, in a top-down and left-to-right (L-toR) dynamic programming procedure.

E-step:Du(q, p)sq x p

We compute the expectation values µu (α[q, l]), µu (β[q, l]),µu (b[m, σh ]) and µu (π[m]) from the current probability parameters and from the auxiliary probabilities Fu ,Bu , Uu , Du .

Fu(m,j-1)

α[q,l]sl
xj: eldest sibling

β[m,l]slxjµu (α[q, l]) =Uu(m,j-1)

1
L(Tu )

Figure 6: Updating Fu (l, j) (left) at the eldest sibling and (right) at another node. The sparse shaded
node is j, and dense shaded areas are used for updating.

slFu(l, j)xj

Du (q, p)b[q, oup ]α[q, l]Bu (l, j)

p:Cu (p)=∅(s.t. xuj = xu← (p))µu (β[q, l]) =1
L(Tu )

β[l,m]XX

Fu (q, j)β[q, l]Bu (l, j + 1)Uu (q, j)

j:Xu (j)=∅µu (b[m, σh ])=1
L(Tu )sm
xj+1

Bu(m,j+1)
Figure 7: Updating Du (l, j). The sparse shaded nodeis j, and dense shaded areas are used for updating.
The updating rules of the forward and downward probabilities are signiﬁcantly diﬀerent from those of PSTMM.
In PSTMM, the downward probability of a node was easily
computed by using the downward probability of its parent.
However, in OTMM, the state of a node (except the eldest
siblings) does not depend on the state of its parent. Therefore, the downward probability needed to be computed fromsomewhere else, either the forward and/or backward probabilities. That is, we needed to incorporate the downward(i.e. parent to child) dependencies into either the forwardor the backward probabilities. This was not possible for the
backward probabilities, because the parent-child dependencies are limited to the eldest siblings only. Thus, at theeldest sibling, we compute the forward probability using thedownward probability of its parent, and the forward probability carries the downward dependencies from parent tochild. As a result, the forward probability of OTMM contains richer dependency information than that of PSTMM,
making it completely diﬀerent from that of PSTMM.
We note that the forward probability of OTMM is a trituple, while it is a quatro-tuple in PSTMM. Thus we can
expect that the algorithms for OTMM will run faster thanthose for PSTMM. We also note that the likelihood of a tree
can be computed by OTMM using the upward and downward probabilities at node i as follows:
X
L(Tu ) =Uu (l, i)Du (l, i).

µu (π[m]) =X

Du (m, i)Uu (m, i),

i:ou
i =σh

1
π[m]Uu (m, 1),
L(Tu )

M-step:
We update the probability parameters using these expectation values computed in the E-step:Xα̂[q, l] =µu (α[q, l])

u

XX

X

XX

µu (β[q, l ])

,

l

X

µu (b[m, σh ])

u

XX
u

µu (b[m, σi ])µu (π[m])

u

XX
u

,

i

X
π̂[m] =µu (β[q, l])uub̂[m, σh ] =

,

l

u

β̂[q, l] =µu (α[q, l ])µu (π[k]).

k

3.2.2 EM (Expectation-Maximization) Algorithm

We repeat these E- and M-steps alternately until a certain
convergence criterion is satisﬁed1 . A possible criterion isthat the increase of the likelihood at an iteration is less thana minimal threshold value.
Figure 8 is sample pseudocode for this EM algorithm for
OTMM. This algorithm starts with parameter initializationand likelihood L(T) computation using the initial parameter values (lines 1-2). The parameters can be randomly

The EM algorithm for OTMM iterates the following Eand M-steps alternately, using the above four probabilities.

1
Note that it has been proven that the EM algorithm theoretically converges to a local maximum solution [15].

l1:for each θi,j do Initialize θ;
2:Calculate L(0) (T) using the initial θ;
3:t := 0;
4:repeat
5: for each θi,j do µT (θi,j ) := 0;
6: for u := 1 to |T| do
7:for k := |Vu | downto 1 do /* B-up & R-to-L DP */8:for each q ∈ S do Calculate Uu (q, k);
9:for each m ∈ S do Calculate Bu (m, k);
10:
for k := 1 to |Vu | do /* T-down & L-to-R DP */11:
for each q ∈ S do Calculate Du (q, k);
12:
for each m ∈ S do Calculate Fu (m, k);13:
for each θi,j do Calculate µu (θi,j );14:
for each θi,j do µT (θi,j ) := µT (θi,j ) + µu (θi,j );15: for each θi,j do Update θi,j using µT (θi,j );16: t := t + 1;
17: Calculate L(t) (T) using the current θ;18:until |L(t) (T) − L(t−1) (T)| < 
19:output θ;Figure 8:
OTMM.

Pseudocode of the EM algorithm forP
initialized, satisfying
j θi,j = 1 for all i. We then start
repeating the E- and M-steps (lines 3-4). In each iteration,
we ﬁrst initialize the expectation value to µT (θi,j ) := 0 (line5). In the E-step, we compute the upward and backward
probabilities by a bottom-up and right-to-left dynamic programming procedure (lines 7-9) and the downward and forward probabilities by a top-down and left-to-right dynamic
programming procedure (lines 10-12). We then update theexpectation values µT (θi,j ) (lines 13-14). In the M-step,
we update the probability parameters using the expectation
values (line 15). At the ﬁnal part of the iteration, we compute the likelihood L(T) (line 17) and conﬁrm whether someﬁxed convergence criterion is satisﬁed (line 18). After the iterations, we output the probability parameters learned fromthe given trees (line 19).

3.3 Parsing (Finding the Most Likely State
Transition)
Once the model is trained, we need to retrieve what waslearned by retrieving the most likely state paths. Let Zu∗ (=∗{q1∗ , · · · , q|V}) be the most likely state transition of a givenu|tree Tu . We ﬁrst reformulate the upward and backward
probabilities to ﬁnd the maximum probabilities, φU
u (q, p)Uand φBu (m, j), respectively. That is, φu (q, p) is the maximum probability that all labels of subtree tu (p) are generated and the state of node p is sq (maximum probability ofUu (q, p)), and φB
u is the corresponding maximum probability for Bu (m, j). In order to obtain these
P two “maximum
probability” values, we ﬁrst replace thein Equations (1)and (2) with max and then iteratively compute these probabilities using the bottom-up and right-to-left dynamic programming procedure. This procedure is generally called theViterbi algorithm, and the probability that all labels are
outputted along the most likely state transition is given as
P ∗ = maxl π[l]φUu (l, 1).
We further deﬁne two functions ψuU (q, p) and ψuB (m, j),each of which returns the most likely state
P for the givennode, and it can be computed by replacingin (1) and (2)Table 1: Time and space complexity
Time
Space
U
O(|T| · |S|2 · |V |) O(|S| · |V |)B
O(|T| · |S|2 · |V |) O(|S| · |V |)F
O(|T| · |S|2 · |V |) O(|S| · |V |)D
O(|T| · |S|2 · |V |) O(|S| · |V |)µ(a) O(|T| · |S|2 · |V |)O(|S|2 )µ(b)O(|T| · |S| · |V |) O(|S| · |Σ|)µ(π) O(|T| · |S| · |V |)O(|S|)â
O(|T| · |S|2 )O(|S|2 )O(|T| · |S| · |V |) O(|S| · |Σ|)b̂π̂
O(|T| · |S|)
O(|S|)

Table 2: Time and Space Complexity Comparisonof HTMM and PSTMM
OTMM
HTMM
PSTMM

Time
O(|T| · |S|2 · |V |)O(|T| · |S|2 · |V |)O(|T| · |S|3 · |V | · |C|)

OTMM
HTMM
PSTMM

Space
P
max{O(|S| · |V |), O(|S|2 ), O(|S| · | |)}P
2
max{O(|S| · |V |), O(|S| ), O(|S| · | P|)}
2
3
2
max{O(|S| · |V |), O(|S| ), O(|S| · | |)}with arg max. The most likely state transition starts withthe most likely state for the root, which can be obtained by
q1∗ = arg maxl π[l]φUu (l, 1). We can then retrieve the most
likely state transition by computing the following equationsin the top-down and left-to-right manner as done for theforward and downward probabilities: qj∗ = ψuU (qp∗ , p) if xj =∗, j − 1).
xu← (p); otherwise qj∗ = ψuB (qj−1

3.4 Time and Space Complexity
Table 1 summarizes the time and space complexity of theabove algorithms for OTMM, including the likelihood computation and parameter estimation. We note that the complexity of the parsing is the same as that of the likelihood
computation. As clearly shown in the table, the time complexity of the most time consuming parts is O(|T|·|S|2 ·|V |),and the space complexity
P is upper-bounded by max{O(|S| ·|V |), O(|S|2 ), O(|S| · | |)}.
Table 2 shows the comparison of the time and space complexities between OTMM and the other two tree Markov
models, HTMM and PSTMM. This table illustrates thatthe space and time complexity of OTMM are kept at thesame as those of HTMM and are signiﬁcantly lower thanthose of PSTMM.
Furthermore, we note that algorithms used for estimating probability parameters of probabilistic models for moregeneral (complex) objects like graphs have higher computational complexity. For example, both the time and spacecomplexity of the junction tree algorithm [13] for probabilistic inference in a Bayesian network reaches O(|T| · |S|3 · |V |)for a directed acyclic graph with |V | nodes. Thus we can saythat our model and its learning algorithm can provide a relatively low complexity by conﬁning them in labeled ordered
trees.

EXPERIMENTAL RESULTS

We examined the performance of our proposed model onboth synthetic and real datasets, comparing it with that of
PSTMM in terms of predictive accuracy and computation
time. The predictive accuracy was computed in a supervised
learning manner. That is, we trained the model using a
set of positive examples and examined the ability of the
trained model to discriminate the positive examples from thenegatives. Using the real dataset, we conﬁrmed the validityof our method by examining the results from a variety of
biological viewpoints.

4.1 Synthetic Data
The models were trained using positive examples only, andso we synthetically generated three datasets, i.e. positive
training, positive test and negative test datasets. We kept
the size of each of these three datasets the same, which isdenoted by |T|, and in our experiments, we tested
Pvarious
values of |T| and numbers of states |S|. We set | | = 10
and |Vu | = 20 in all of our experiments.
Each positive example contains a tree fragment as a pattern. Figure 9 shows the six tree fragments Q1 to Q6 that
we used in our experiments. In each tree fragment in Figure 9, the solid circle indicates a ﬁxed label, and the dashedcircle indicates that the label is randomly selected. So, forexample, in Q5, the labels of the eldest and third siblings
are ﬁxed, whereas the labels of the parent and the second
sibling are randomly applied. We generated K diﬀerent label patterns for each tree fragment. In positive example
generation for a particular tree fragment pattern, a positive
example was generated by the following two steps. First, we
generated a random tree by iteratively: randomly generating zero to ﬁve children and randomly assigning a label toeach of the children, until the number of generated nodes
reached twenty. Second, we randomly embedded one of the
K label patterns of the tree fragment into the tree. A negative example was generated in the same manner as the ﬁrst
step above, except that the random generation of labels follows the distribution of parent-child labels in the positive
examples.

4.1.2 Performance Comparison with PSTMM
We evaluated the discriminative performance of the models by AUC, the area under the ROC (Receiver Operator
Characteristic) curve [7, 8]. We can compute the AUC byﬁrst sorting examples by their computed likelihoods andthen by using Equation (3).
Rn − nn ·(n2n +1),
nn · np(3)

where nn (np ) is the number of negative (positive) examples
and Rn is the sum of the ranks of the negative examples.
We note that nn = np in our experiments.
We ﬁrst evaluated the amount of overﬁtting to the training data that occurred, using Q1 as the tree fragment. In
this experiment, |T| = 100 and K = 1, such that the complexity of the data was relatively low and the tendency to
overﬁt would be higher. Figure 10 shows the AUC for the
training2 and test datasets, setting the range of |S| between
2

PSTMM (train)
OTMM (train)

95
90
85

OTMM (test)

80
75

PSTMM (test)

70
2

4

6
8
10
# states (|S|)

12

Figure 10: Performance comparison of OTMM with
PSTMM when |T| = 100.

4.1.1 Data Generation Procedure

AUC =

100

AUC (%)

4.

We used the negative examples in the test set to compute

two and twelve. The AUCs of the two models for the training examples increased with |S| and reached around 100%
when |S| was eight or more. On the other hand, the AUCs
for the test examples decreased with |S|. In particular, the
AUC of PSTMM for the test data went down to 70% fromaround 95%, which was the highest obtained when |S| wasfour. This phenomenon clearly illustrates overﬁtting to thetraining data. A similar tendency was found with the AUC
of OTMM but it was always more than 85%, which wasaround 15% better than the worst AUC of PSTMM. Thus,
can say that OTMM reduced the overﬁtting problems of
PSTMM. We can infer from these results that PSTMM withmore than four states is too complex to be trained from thedataset we used in this experiment and that OTMM is more
appropriate for this dataset.
Figure 11 shows how the AUC and computation time forthe test examples change with diﬀerent values of |T| and|S|, using K = 3 and Q1 as the tree fragment. We notethat the complexity of the dataset increases with |T|, andthe complexity of the model increases with |S|. So when
|T| was relatively small, say 100, and |S| was large, say ten,
overﬁtting occurred. However, when |T| was large, say 400
and 600, and |S| was small or a moderate size, say 2 to 6, theAUCs remained at the maximum, meaning that overﬁtting
was avoided. Under such conditions, e.g. |T| = 400 and|S| = 6, we can see that the two models achieved almost
the same predictive performance, indicating that OTMM
kept approximately the same predictive power as that of
PSTMM. On the other hand, regarding the computation
time, the two models were clearly diﬀerent. For example, for|T| = 400 and |S| = 10, the computation time of PSTMM
reached 4,000 seconds while that of OTMM was just under
1,000 seconds. OTMM clearly reduces the computational
cost of PSTMM greatly, keeping its predictive power andavoiding overﬁtting. This result indicates that OTMM ismore practical for mining from large datasets of labeled ordered trees compared to PSTMM.
We next ﬁxed |T| at 200 and changed K, still using Q1 as
the tree fragment. As |T| increases with K, so does the complexity of the data, and so the results in Figure 12 are similar
to those in Figure 11. However, we note that in this case,under the conditions when overﬁtting did not occur, OTMM
achieved better performance than PSTMM. That is, when
K was set between two and four, we found that PSTMM
achieved the highest AUC at |S| = 6, where overﬁtting did
not occur, and that the AUC of OTMM was clearly better
than that of PSTMM. This indicates that in this experithe AUC of the training data.

Q1

Q2

Q3

Q4

Q5

Q6

eldestsibling
Figure 9: Six patterns of tree fragments used in our experiments.

70

400
PSTMM ->

65

200

OTMM ->

60
2

4

6

8

0
10

# states (|S|)

90

1800

<- PSTMM

80

1200
PSTMM ->

70600

OTMM ->

60
2

4

6

8

0
10

# states (|S|)<- OTMM
90

3000<- PSTMM

80

2000
PSTMM ->

70

1000
OTMM ->

60
2

4

6

8

0

10

100

10000
<- OTMM90 <- PSTMM

7500

80

5000
PSTMM ->

70

2500
OTMM ->

602# states (|S|)

4

6

8

0
10

Computation Time (in seconds)

600

4000

AUC (%)

800<- PSTMM

75<- OTMM|T| = 600

100

Computation Time (in seconds)

AUC (%)

80

2400

AUC (%)<- OTMM|T| = 400

100

AUC (%)

1000

Computation Time (in seconds)|T| = 20085

Computation Time (in seconds)|T| = 100

# states (|S|)

4.2 Real Data: Carbohydrate Sugar Chains
4.2.1 About the Data
We used real data derived from glycobiology (an overview
of this ﬁeld is provided in a book by Varki et al. [20]), whichis the study of carbohydrate sugar chains, or glycans. Glycans can be modeled as branched and directed tree structures. The basic component of glycans is the monosaccharide unit (or sugar), which corresponds to a label, and eachsugar may have one or more child sugars bound to it, suchthat they are ordered. Thus glycans can be considered labeled ordered trees. The glycans we used in our experiments
are all derived from the KEGG GLYCAN database [9, 10].

100
AUC (%)

mental setting, OTMM had better predictive power than
PSTMM.
Finally, we checked the predictive performance and computation time of the two models for all the six tree fragments, Q1 to Q6. The parameter settings we used in thisexperiment were K = 3, |T| = 400 and |S| = 6, the same
conditions as when overﬁtting did not occur for Q1 using
both OTMM and PSTMM. Table 3 shows the AUC andcomputation time. The predictive performances of the twomodels were almost equivalent except for Q6, where the
AUC of OTMM was roughly seven percent better than thatof PSTMM. Thus we can say that OTMM has almost thesame or better predictive power compared to PSTMM. On
the other hand, the diﬀerence in computation time between
the two models was signiﬁcant. In Table 3, we indicate theratio of the computation time of OTMM to that of PSTMM
in parentheses, which shows that the typical computation
time improved by a factor of at least three to at most six,which increases as |S| increases. Consequently, we haveclearly demonstrated the advantage of OTMM in computation time and that it is more practical than PSTMM formining complex labeled ordered trees.

<- OTMM

90600

PSTMM ->

300<- PSTMM
OTMM ->
80

0
2

4

6

8

10

Computation Time (in seconds)

Figure 11: AUC and computation time for K = 3.

# states (|S|)

Figure 13: Performance comparison of OTMM with
PSTMM using real datasets.

4.2.2 Performance Comparison with PSTMM
Glycans are classiﬁed based on their structural properties,
and we selected two of the major classes called “N-Glycans”
and “O-glycans,” which were used as the positive and negative datasets, respectively. We examined whether N-Glycans
could be discriminated from O-Glycans by the model trainedusing N-Glycans. We performed a ﬁve-fold cross-validation
to evaluate the performance of OTMM and PSTMM. Thatis, we randomly divided a given dataset into ﬁve blocks ofroughly equal size. Then the ﬁrst block would be reserved
as test data while the remaining four were used as training
data. This was repeated for each of the ﬁve blocks. We repeated this random division ﬁve times, and the results wereaveraged over the total 25 (= 5 × 5) runs. We used thoseglycans containing ﬁve to eighteen sugars only, because thedataset of the other glycans was very small. In total, we
used 1,826 N-Glycans and 606 O-Glycans. In this experiment, |S| = 6 since the predictive performance of OTMM
and PSTMM was always the best under this setting in thesynthetic data experiments.
Figure 13 shows the AUC and computation time of thetwo models for the real datasets. The two models achieved
approximately the same AUC values for all |S| we used.
However, the amount of computation time of OTMM wasmuch smaller than that of PSTMM. That is, at |S| = 8,
the computation time improvement reached a factor of approximately six to seven. Thus, from the real datasets, we

800
PSTMM ->

70

OTMM ->

60
2

4
6
8
# states (|S|)

10

400
0

1800
<- PSTMM

80

1200
PSTMM ->

70600

OTMM ->

60
2

4
6
8
# states (|S|)

0
10

2400
<- OTMM

90

1800<- PSTMM

80

1200
PSTMM ->

70600

OTMM ->

60
2

4
6
8
# states (|S|)

0
10

90

2400
<- OTMM

80

1800<- PSTMM

70

1200
PSTMM ->

60600
OTMM ->

50
2

4
6
8
# states (|S|)

010Computation Time (in seconds)

80

90

100

AUC (%)

1200

2400<- OTMM

K=4
Computation Time (in seconds)<- PSTMM

100

AUC (%)

90
AUC (%)

1600<- OTMM

AUC (%)

100

K=3Computation Time (in seconds)

K=2
Computation Time (in seconds)

K=1

Figure 12: AUC and computation time for |T| = 200.

AUC(%)
Comp. Time(in seconds)

Table 3: AUC and computation time for the six tree fragments in Figure 9.
Model
Q1
Q2
Q3
Q4
Q5
OTMM
93.4
87.2
88.6
96.6
81.8
PSTMM
92.3
89.9
91.8
95.0
79.9
OTMM 438.7 (0.204) 583.8 (0.269) 608.8 (0.309) 379.5 (0.193) 829.8 (0.239)
PSTMM
2145.6 (1.0)
2173.8 (1.0)
1970.8 (1.0)
1961.9 (1.0)
3475.4 (1.0)

5.

b1
G0402562
4

b1

4.2.3 Results with Biological Significance
Next, we veriﬁed the actual patterns learned in the data
to verify the biological characteristics retrieved. We focus
on the set of N-Glycan structures because it is the most wellstudied among all the glycan classes. Using the N-Glycan
data set from the previous experiment, we extracted themost likely state paths and found some interesting patterns
reﬂecting the biological properties of sugars. Figure 14 is an
example a glycan tested and the most likely state transitions
for it. Here we see reﬂected the fact that the Gal (galactose)
residues and GalNAc (N-acetylgalactosamine) residues end
up with the same state. This corresponds with the fact that
GalNAc is a modiﬁcation of Gal, such that they may beconsidered very similar and sometimes appear in place ofeach other. Thus they may be aligned together as well. A
rather large number of glycans have this pattern of sugars
at the leaves, where Gals may be GalNAcs and vice versa.
In another trial, we assessed the most likely state transitions for glycans representing the three sub-classes of NGlycans: High-mannose, Complex, and Hybrid, given in
Figure 15. Here we see these three classes being distinguished based on the states learned. In particular, the statesat the tri-mannose core distinguishes these three sub-classes.
The High-mannose type is characterized by state 2 appearing at both child mannoses. For the Complex type, thesemannoses are both state 1. Consequently, the Hybrid type,which is a hybrid of these two types having one each ofa High-mannose type subtree and a Complex-type subtree,
receives state 1 on one mannose, and state 2 on the other.
Thus, the states learned at just the core N-Glycan structure
can determine the sub-class without needing to actually traverse the rest of the structure.

4

b1

conﬁrmed that the time eﬃciency of OTMM was consistent
with the results using the synthetic datasets.

a1

b1
6
3

b1

4

9

4

b1

4

b1

b1

4

Galactose
4
2

b1

Q6
82.0
75.2
581.4 (0.179)
3257.1 (1.0)

Mannosea1

N-acetylglucosamine
N-acetylgalactosamine

b1

5
3

9

5
7

9

8

5
3

9

0

State diagram for G04025

5

Figure 14: Example of the states learned using
OTMM for a specific glycan structure.
that in all of the experimental settings we conducted, OTMM
achieved equivalent or better performance compared to themore complex probabilistic model, PSTMM, for mining labeled ordered trees. In particular, the amount of computation time of OTMM is signiﬁcantly less than that of PSTMM
in all experimental settings.
The key property of our method that contributes to these
improvements is its concise model structure, in which thestate of a node depends on only one state, and the eﬃcient learning algorithm by which the model captures boththe sibling and parent-child dependencies in labeled ordered
trees. Thus, we have developed the ultimate model in terms
of eﬃciency and accuracy for mining labeled ordered trees.

CONCLUDING REMARKSIn summary, we have developed a new probabilistic model,
OTMM, and an eﬃcient learning scheme for mining labeledordered trees. We empirically evaluated the eﬀectivenessof OTMM using both synthetic and real datasets and found

6. REFERENCES[1] S. Abiteboul, P. Buneman, and D. Suciu. Data on the
Web: from relations to semistructured data and XML.
Morgan Kaufmann, 2000.

High-mannose
a1

3

a1

2

Hybrid

6
3

a1

2

4

3

a1

2

2

b1

b1

4

6
4

a2
a1

a1
6
3

a1

a1
6
2

a1

b1

b1

4

b1

6
2

6
3
6
3

3

4

a1

a1

a1

a1

Complex
b1

a1

3

b1

4

b1

2

b1

4

b1

a1
a1
6
3

4
4
2

MannoseN-acetylglucosamine

N-acetylglucosamine
Neu5Ac

a1

4

b1

4

N-acetylgalactosamine

8

3

8

3

Fucose

1

4

0

6
4

9

4

4

0

0

9

3

4

6

5

3

1

1

2
2

6
4

N-acetylglucosamine

b1

2

4

b1

Mannose
a1

4

4

2

4

b1

Galactose

a1

Mannose

2

4

b1

4



8

3

Figure 15: (top) The actual glycans, and (bottom) the most likely state paths.
[2] K. F. Aoki, N. Ueda, A. Yamaguchi, T. Akutsu,
M. Kanehisa, and H. Mamitsuka. Managing andanalyzing carbohydrate data. ACM SIGMOD Record,
33(2), 2004.
[3] E. Baum and T. Petrie. Statistical inference forprobabilistic functions of inﬁnite state Markov chains.
Ann. Math. Stat., 37:1554–1563, 1966.
[4] S. Chakrabarti. Mining the Web: Analysis ofHypertext and Semi Structured Data. Morgan
Kaufmann, 2002.
[5] A. Dempster, N. Laird, and D. Rubin. Maximum
likelihood from incomplete data via the EM
algorithm. J. Royal Stat. Soc., B, 39:1–38, 1977.
[6] M. Diligenti, P. Frasconi, and M. Gori. Hidden tree
Markov models for document image classiﬁcation.
IEEE Trans. PAMI, 25(4):519–523, 2003.
[7] D. J. Hand and R. J. Till. A simple generalisation of
the area under the ROC curve for multiple classclassiﬁcation problems. Mach. Learn., 45:171–186,
2001.
[8] J. A. Hanley and B. J. McNeil. The meaning and useof the area under a receiver operating characteristic(ROC) curve. Radiology, 143:29–36, 1982.
[9] K. Hashimoto, S. Goto, S. Kawano,
K. Aoki-Kinoshita, N. Ueda, M. Hamajima,
T. Kawasaki, and M. Kanehisa. KEGG as a glycome
informatics resource. Glycobiology, 16(5):63R–70R,
2005.
[10] M. Kanehisa, S. Goto, M. Hattori, K. F.
Aoki-Kinoshita, M. Itoh, S. Kawashima,
T. Katayama, M. Araki, and M. Hirakawa. From
genomics to chemical genomics: New developments in
KEGG. Nucl. Acids Res., 34:D354–D357, 2006.
[11] H. Kashima and T. Koyanagi. Kernels forsemi-structured data. In Proc. 19th ICML, pages
291–298, 2002.
[12] K. Lari and S. J. Young. The estimation of stochastic
context-free grammars using the inside-outsidealgorithm. Computer Speech and Language, 4:35–56,
1990.

[13] S. L. Lauritzen and D. J. Spiegelhalter. Local
computations with probabilities on graphicalstructures and their application to expert systems(with discussion). J. Royal Stat. Soc. B,
50(2):157–224, 1988.
[14] C. Manning and H. Schütze. Foundations of Statistical
Natural Language Processing. MIT Press, 1999.
[15] G. J. McLachlan and T. Krishnan. The EM Algorithm
and Extensions. Wiley-Interscience, 1996.
[16] J. Pearl. Probabilistic Reasoning in Intelligent
Systems: Networks of Plausible Inference. Morgan
Kaufmann, 1988.
[17] L. R. Rabiner and B. H. Juang. An introduction tohidden Markov models. IEEE ASSP Magazine,
3(1):4–16, 1986.
[18] N. Ueda, K. F. Aoki, and H. Mamitsuka. A generalprobabilistic framework for mining labeled ordered
trees. In Proc. Fourth SDM, pages 357–368, 2004.
[19] N. Ueda, K. F. Aoki-Kinoshita, A. Yamaguchi,
T. Akutsu, and H. Mamitsuka. A probabilistic model
for mining labeled ordered trees: Capturing patterns
in carbohydrate sugar chains. IEEE Trans. Know.
Data Eng., 17(8):1051–1064, 2005.
[20] A. Varki, R. Cummings, J. Esko, H. Freeze, G. Hart,
and J. Marth, editors. Essentials of Glycobiology. Cold
Spring Harbor Laboratory Press, New York, 1999.
[21] S. M. Weiss, N. Indurkhya, T. Zhang, and F. J.
Damerau. Text Mining: Predictive Methods forAnalyzing Unstructured Information. Springer, 2005.
[22] M. Zaki and C. Aggarwal. Xrules: An eﬀective
structural classiﬁer for XML data. In Proc. NinthACM KDD, pages 316–325, 2003.
[23] M. J. Zaki. Eﬃciently mining frequent trees in aforest: Algorithms and applications. IEEE Trans.
Know. Data Eng., 17(8):1021–1035, 2005.

9