Kernels for Semi-Structured Data
Hisashi Kashimahkashima@jp.ibm.com
Teruo Koyanagi
Teruok@jp.ibm.com
IBM Tokyo Research Laboratory, 1623-14, Shimotsuruma, Yamato-shi, Kanagawa 242-8502, Japan

Abstract
Semi-structured data such as XML andHTML is attracting considerable attention.
It is important to develop various kinds ofdata mining techniques that can handle semistructured data. In this paper, we discuss applications of kernel methods for semistructured data. We model semi-structured
data by labeled ordered trees, and present
kernels for classifying labeled ordered trees
based on their tag structures by generalizing
the convolution kernel for parse trees introduced by Collins and Duffy (2001). We givealgorithms to efficiently compute the kernels
for labeled ordered trees. We also apply ourkernels to node marking problems that are
special cases of information extraction fromtrees. Preliminary experiments using artificial data and real HTML documents show
encouraging results.

1. Introduction
Recently, semi-structured data (Abiteboul et al., 2000)
such as XML and HTML is attracting considerable attention. Not only relational databases, but also semistructured databases are likely to increase in the future. Also, the WWW can be seen as a huge semistructured database whose instances are HTML documents. Since semi-structured data can be modeled bylabeled ordered trees, it is important to develop various kinds of data mining techniques that can handle
labeled ordered trees.
In this paper, we aim to develop solutions to two-classclassification problems of labeled ordered trees by exploiting their structural information. In general learning problems, objects are represented as vectors in afeature space. Training a classifier is reduced to deciding on rules to separate vectors that belong to positive examples from vectors that belong to negative
examples. If we can properly define the bases of thefeature space for classification, we can just pass thevectors to learning algorithms such as decision trees
and neural networks. However, when we handle more
complex objects such as sequences, trees, and graphsthat have structures among their constituent elements,

the proper vector representation is not obvious, andthe step of feature definition can be difficult and timeconsuming.
One of the strategies for handling such complex objects is to use local structures of the objects as features. Relational learning (Mitchell, 1997) is a general
method that can handle local structures in objects. In
relational learning, several relationships among constituent elements are defined, and the relationships
constitute local structures. The local structures usedas features are incrementally built up in the processof training on examples. However, since the problem
of searching for the best hypothesis is generally NPhard, we must use heuristic methods. Another method
is based on pattern discovery algorithms that find local structures appearing frequently (Inokuchi et al.,2000), and these structures are used as features. The
pattern-discovery-based method has an advantage inthat it can make use of unlabelled data. However, theprocess of discovering patterns is again almost always
NP-hard.
Yet another approach is to use kernel methods suchas support vector machines (SVMs) (Vapnik, 1995).
One of the important properties of kernel methods istheir access to examples via kernels. Kernel methods
use only the inner products of the vector representations when they access the examples. This means thateven in cases where the dimension of the vector representations is extremely large, the dimensions do not
explicitly appear in the process of training and classification as long as an efficient procedure to computethe inner products is available. The function giving theinner products is called the ’kernel’, and kernel methods can work efficiently in high dimensional feature
spaces by using kernels. Moreover, SVMs are known
to have good generalization properties, both theoretically and experimentally, and overcome the ’curse ofdimensionality’ problem in high dimensional feature
spaces (Vapnik, 1995).
Haussler (1999) introduced ’convolution kernels’, ageneral framework for handling discrete data structures by kernel methods. In convolution kernels, objects are decomposed into parts, and kernels are defined in terms of the parts. In the context of convolution kernels, convolution kernels specialized for several
discrete data structures have been proposed. Gärtner
et al. (2002) introduced kernels for sets, cosets andmulti-instances. Watkins (1999) developed a sequencekernel that considers all possible substrings in text sequences. Of special interest here, Collins and Duffy(2001) developed a convolution kernel for parse trees
for natural language texts. Their kernel is also viewed
as an instance of coset kernels for multisets (Gärtner
et al., 2002). In Collins and Duffy (2001), each elementof a vector is the number of times a particular subtree
appears in a parse tree. However, since the number ofsubtrees appearing in a tree can grow exponentially as
the size of the tree grows, their explicit enumeration iscomputationally problematic. They proposed an efficient way of recursively computing the kernels. However, the trees that their kernel can handle are limited
to trees where all children of a given node are distinguishable. Since their recursive rules to efficiently
compute the parse tree kernel are strongly based on
this assumption, the kernel cannot be used for moregeneral trees. In this paper, we develop an efficientalgorithm applicable to labeled ordered trees. Furthermore, we extend our kernel to be able to flexibly
decide whether a subtree appears in a tree. The extended kernels can allow some mutations of node labelsand elastic subtree structures. The time complexities
of computing our kernels are still the same as for theparse tree kernel.
Next, we consider node marking problems for labeledordered trees. The node marking problems are tasks
to learn which nodes are to be marked in a tree. After being trained on example trees, each having somemarked nodes, the learning machine must correctly
mark the nodes of new trees that have not yet been
seen. The node marking problems can be considered as
special cases of information extraction (Cowie & Lehnert, 1996) from tree structures. Information extraction
is a technology for analyzing documents and extracting information that users want, for example, for constructing a relational database automatically by extracting job descriptions and salaries from HTML documents describing jobs. Several research projects havediscussed the node marking problem in the context of
information extraction. Craven et al. (2000) employed
relational learning (Mitchell, 1997). Sakamoto et al.
(2001) proposed a method based on the idea of wrapper induction (Kushmerick, 2000). Their algorithm
generalizes paths from roots to marked nodes. Our
approach is similar to that of (Craven et al., 2000), inthat we reduce a node marking problem to a classification problem of marked trees.
Finally, we performed some computational experiments of classification and node marking on artificial
data and on real HTML data to demonstrate thatstructural information has some predictive power forsome data and that our kernel can efficiently capture
this information. The artificial data is generated sothat learning machines make mistakes if they can nothandle local structures, and the results prove that ourkernel can successfully handle them. The results for
the HTML documents imply our kernel is promising
for real world data.

This paper is organized as follows. In Section 2, we
describe the parse tree kernel (Collins & Duffy, 2001)
that our kernels are based on. In Section 3, we introduce the kernels for labeled ordered trees. In Section
4, we describe how to make use of our kernels for nodemarking problems for labeled ordered trees. In Section 5, we summarize the results of our experiments
on artificial data and on real HTML data. We conclude with Section 6 in which we provide a summaryand discussion.

2. Parse Tree Kernel
In this section, we briefly review the convolution kernel for parse trees for context-free languages suggested
by Collins and Duffy (2001). The parse tree kernel is a
specialized convolution kernel introduced by Haussler(1999). In their vector representation of a parse tree,
the features correspond to the subtrees that can possibly appears in a parse tree (Figure 1), and the valueof a given feature is the number of appearances of thesubtree in the parse tree. However, since the numberof subtrees appearing in a tree can grow exponentiallyas the size of the tree grows, their explicit enumeration is computationally problematic. They proposed amethod to compute the inner product of two vectors
without accessing the large vectors directly.
Let subtree1 , subtree2 , . . . be all subtrees possibly appearing in parse trees. A parse tree T is represented
as a vectorVT=(#subtree1 (T ), #subtree2 (T ),#subtree3 (T ), . . .)(1)

where #subtreei (T ) is the number of appearances ofsubtreei in T . Then the inner product of the vector
representations of two trees, T1 and T2 , becomes< VT1 , VT2 >X=#subtreei (T1 ) · #subtreei (T2 )
i

=

X
i

=




X

 
X

Isubtreei (n1 ) · 

n1 ∈NT1

X
X

Isubtreei (n2 )

n2 ∈NT2

C(n1 , n2 )(2)

n1 ∈NT1 n2 ∈NT2

where NT1 and NT2 are the sets of nodes in T1 andT2 respectively, and Isubtreei (n1 ) is a function that returns the number of appearance of subtreei rooted at
n1 in T1 , and C(n1 , n2 ) is the sum of the product of
the numbers of times each subtree appears at n1 andn2 , i.e.
X
C(n1 , n2 ) =Isubtreei (n1 ) · Isubtreei (n2 ).
(3)i

C(n1 , n2 ) can be recursively calculated by using thefollowing recursive rules:

i1 < j1 and i2 < j2 hold whenever the i1 -th child of
n1 matches against the i2 -th child of n2 and the j1 -thchild of n1 matches against the j2 -th child of n2 . Fora certain node pair, n1 and n2 , let Sn1 ,n2 (i, j) be thesum of the products of the numbers of times each subtree appears at n1 and n2 when we consider only thenodes up to the i-th child of n1 and the nodes up to
the j-th child of n2 . Apparently,
C(n1 , n2 ) = Sn1 ,n2 (nc(n1 ), nc(n2 )).
Figure 1. (a) Parse tree (b) Subtrees appearing below theright NP

1. If the productions at n1 and n2 are different,C(n1 , n2 ) := 0.
2. Else if both n1 and n2 are pre-terminals,
C(n1 , n2 ) := 1.
3. Else,nc(n1 )

C(n1 , n2 ) :=Y

(1 + C(ch(n1 , i), ch(n2 , i))), (4)iwhere nc(n1 ) is the number of children of node n1
and ch(n1 , i) is the i-th child of node n1 . The recursive equation (4) is based on the fact that all subtrees
rooted at a certain node can be constructed from combining some of the subtrees rooted at each of its children. The time complexity of computing this kernel isO(|NT1 ||NT2 |).

3. Labeled Ordered Tree Kernels(5)

Since all correspondences preserve the left-to-right ordering, Sn1 ,n2 (i, j) can be recursively defined as
Sn1 ,n2 (i, j) = Sn1 ,n2 (i − 1, j) + Sn1 ,n2 (i, j − 1) (6)−Sn1 ,n2 (i − 1, j − 1)
+Sn1 ,n2 (i − 1, j − 1) · C(ch(n1, i), ch(n2, j)).
Therefore, we can efficiently compute C(n1 , n2 ) by dynamic programming. The algorithm for computing thekernel of two labeled ordered trees T1 and T2 is shownin Appendix A.
Finally, we consider the time complexity of computing the kernel. The computation time for an arbitraryC(n1 , n2 ) is proportional to the product of the numbers of children of n1 and n2 . The following simple
analysis shows the time complexity of computing thekernel of two labeled ordered trees is the product of
their sizes, which is as same as for the parse tree kernel.
X
X
O(nc(n1 ) · nc(n2 ))n1 ∈NT1 n2 ∈NT2=

X

O(nc(n1 )) ·n1 ∈NT1

X

O(nc(n2 ))n2 ∈NT2= O(|NT1 | · |NT2 |)(7)

3.1 A Labeled Ordered Tree Kernel
In this subsection, we give a kernel for labeled ordered
trees by generalizing the parse tree kernel. The vector
representation and kernel definition of labeled ordered
trees are the same as those stated for the parse tree
in Equations (1) and (2). Unfortunately, we cannot
use the recursive rules for the parse tree kernel forcomputing this kernel since the use of the parse tree
kernel is limited to trees where no node shares its labelwith any of its siblings. In the parse tree kernel, therecursive equation (4) is invoked only when the production rules used at n1 and n2 are the same. Since
the production rule derives both of the two groups ofchildren of n1 and n2 , the one-to-one correspondences
between the two groups of children can be uniquelydetermined, and therefore we can recursively computeC(n1 , n2 ) by Equation (4). However, since such correspondences are not unique in general trees, we have toconsider all the ways of correspondences.
Since we are interested in labeled ordered trees,
we only have to consider one-to-one correspondenceswhere the order of the children is preserved, that is,

3.2 Extension to Allow Label Mutations
In the previous subsection, subtrees were required tomatch some portion of the labeled ordered tree perfectly. In this subsection, we loosen the condition
for the appearance of a subtree by allowing some label mutations. When we count the number of occurrences of subtreei in T , we penalize the count forlabel mutations. In other words, we modify the criteria by which a subtree is said to appear. Let Σ
be a set of labels and f : Σ × Σ → [0, 1] be a mutation score function. For ∀l1 , l2 ∈ Σ, a low valueof f (l2 |l1 ) indicates a low acceptance of the mutationfrom l1 to l2 . For example, if subtreei were to structurally match the portion of T as shown in Figure 3,
the shaded nodes would be interpreted as mutations.
Supposing f (A|A) = 1, f (A|D) = 0.5, f (C|B) = 0.8
and f (C|C) = 1, the penalized score is defined as theirproduct f (A|A) · f (A|D) · f (C|B) · f (C|C) = 0.4. This
is interpreted as subtreei appearing 0.4 times for thematching shown in Figure (2). The i-th element of
the vector representation of T is defined as the sum ofFigure 2. An example of mutation of labels

the penalized scores of subtreei over all positions in T
where a structural matching occurs.
Since the penalized score is defined by the product,
we have only to modify the computation of C(n1 , n2 )in the algorithm. By introducing a kind of similarity
between the labels of two nodes asX
Sim(l(n1 ), l(n2 )) =f (l(n1 )|a)f (l(n2 )|a) , (8)a∈ΣFigure 3. Example of embedding subtreei into T−Sn1 ,n2 (i − 1, j − 1)
(11)
+Sn1 ,n2 (i − 1, j − 1) · Ca(ch(n1 , i), ch(n2 , j)).
We can maintain Ca (n1 , n2 ) efficiently since Ca (n1 , n2 )can also be recursively defined as

we can compute C(n1 , n2 ) as

Ca (n1 , n2 )C(n1 , n2 ) = Sim(l(n1 ), l(n2 )) · Sn1 ,n2 (nc(n1 ), nc(n2 )).
(9)
The reason for summing over all labels is to take all
the possibilities of label mutations into account. The
modified algorithm is shown in Appendix B.

=

3.3 Extension to Allow Elastic Structure
Matchings
In this subsection, we further extend our kernel to beable to recognize the occurrence of subtrees even more
flexibly by allowing the structures of the subtrees tobe elastic. We say that a subtree appears in a tree if
the subtree is ’embedded’ in the tree while the relative positions of the nodes of the subtree are preserved(Figure 3). If a node is a descendant of another nodein the subtree, that relationship between them must
hold in the embedding of the subtrees into the tree.
Similarly, if a node is to the left of another node in
the subtree, the same relationship must hold in theembedding. In Figure 3, we can say that subtreei appears at the shaded node.
In the case of non-elastic structures, all subtrees rooted
at a certain node can be constructed by combiningsome of the subtrees rooted at each of its children.
However, for allowing elastic structures, they can beconstructed by combining some of the subtrees rooted
at each of its descendants. For this reason, we should
introduce new variables Ca (n1 , n2 ) defined as
XX
Ca (n1 , n2 ) =C(na , nb )(10)
na ∈Dn1 nb ∈Dn2

where Dni is the set of nodes including ni and all thedescendant nodes of ni in Ti . By using Ca (n1 , n2 ), therecursive equation (7) is modified as
Sn1 ,n2 (i, j) = Sn1 ,n2 (i − 1, j) + Sn1 ,n2 (i, j − 1)

(12)

nc(n2 )

Xnc(n1 )Ca (n1 , ch(n2 , j)) +j=1

X

Ca (ch(n1 , i), n2 )i=1

nc(n2 ) nc(n1 )

−

X

X

j=1

i=1

Ca (ch(n1 , i), ch(n2 , j)) + C(n1 , n2 ).

The algorithm for computing the kernel allowing such
elastic structures is shown in Appendix C. The timecomplexity of the algorithm still remains the same as
for the parse tree kernel.

4. Application to Node Marking
Problems
While only classification problems have been discussed
up to now, in this section, we consider node marking
problems, especially for labeled ordered trees. The
node marking problems are tasks to learn which nodes
to mark from example trees, some of whose nodes aremarked. After being trained, the learning machinemust correctly mark the nodes of trees that have notyet been evaluated. The node marking problems canbe considered as special cases of information extraction from trees by regarding marked nodes as either
leaves or the roots of subtrees to be extracted fromthe trees. The input of a node marking problem is aset of trees Tm , some of whose nodes are marked, anda set of trees Tu that have not yet been evaluated. The
output is Tu with appropriate marks.
Our approach is similar to that of Craven et al. (2000),in that we reduce a node marking problem to a classification problem of marked trees. Figure 4 shows theprocedure of our reduction. We regard the trees whose
nodes are correctly marked as positive examples andthe trees whose nodes are incorrectly marked as negative examples. In Step 3, the transformation from

1 Receive correctly marked trees Tp .
2 From Tp , make incorrectly marked trees Tn .
3 Make a set of positive examples Ep from Tp
and make a set of negative examples En from Tn .
4 From Ep and En , construct a kernel classifier.
5 Receive a set of new trees Tu .
6 For each node n in each tree t ∈ Tu ,6.1 Make a tree where the node n is marked.
6.2 Classify the tree using the kernel classifier.
6.3 If the classification result is positive, mark n.
Figure 4. Node marking as classification

Figure 6. Two substructures included in positive examples

Table 1. Classification results for the artificial data
Poly
1
2
3
4
5

BoL Kernel

Strict Tree Kernel

57.8%
55.6%
56.7%
57.8%
55.0%

80.5%
84.4%
80.6%
76.1%
76.1%

5.1 Classification
5.1.1 Artificial Data
Figure 5. Transformation of a tree

a tree to the examples is done by inserting a special
node indicating a mark between a marked node andits parent node (Figure 5). After training on the examples, each of the new trees is evaluated. One of
the candidate nodes is hypothetically marked and themarked tree is classified by the trained kernel classifier. We actually mark the node if the tree is classified
as positive. Each of the candidate nodes in the tree isevaluated in turn.

5. Experiments
In this section, we describe our computational experiments in classification and node marking on artificial
data and real HTML data to confirm the ability of
our kernel to exploit structural information. For easeof implementation, we implemented our method using
the voted kernel perceptron (Freund & Shapire, 1999),
whose performance is known to be competitive withthat of SVMs. We refer to the tree kernel that allows
only strict checking of the occurrence of subtrees as
the ’strict tree kernel’, and the tree kernel that allows
elastic structures as the ’elastic tree kernel’. For both,
we do not allow label mutations. The performance ofeach method was measured by leave-one-out cross validation where the learning machines were trained on
all but one of the trees, and attempted to predict for
the remaining tree.

First, we performed experiments on artificial data sets.
They were designed so that learning machines would
fail in learning unless they considered local structures.
A positive example is a tree including both of the twotrees in Figure 6 as subtrees. We generated A total of
30 trees as positive examples and 30 as negative examples. The size of each tree was between 30 and 50
nodes, and 10 different labels were used. As a tree kernel, we used the strict tree kernel. We also performedexperiments with a ’bag of labels (BoL)’ kernel. In
the vector representation of the BoL kernel, the elements were just the numbers of each label appearing
in a tree. Since the BoL kernel can not use any structural information, we use this kernel as the baseline.
Each kernel was combined with the polynomial kernel(Vapnik, 1995).
Table 1 shows the classification accuracy averaged over
several experiments. POLY means the degree of thepolynomial kernel combined with the tree kernels or
the BoL kernel. POLY=1 means the tree kernel or the
BoL kernel alone. The bold font indicates the best result for each kernel. We can see that the tree kernel
made good use of the structural information.
5.1.2 HTML Documents
In this experiment, we performed classification of realHTML documents based on their structures. We recognize that the state-of-the-art text classification approaches are based on the ’bag-of-words’ vector representation (Salton & Buckley, 1988; Joachim, 1998)
in which each element of a vector is the number oftimes a particular word appears in a document, andthat the same strategy is usually used for HTML documents. However, besides textual information, HTML
documents have structural and visual information as-Table 2. Classification results for the HTML data
Poly

BoL

Strict Tree

Elastic Tree

1
2
3
4
5

41.7%
55.0%
58.3%
51.7%
51.7%

63.3%
71.7%
75.0%
80.0%
71.7%

61.7%
60.0%
66.7%
60.0%
63.3%

sociated with tags, and our kernels make use of thestructure of the tags. In this experiment, we randomly chose 30 HTML documents in the IBM Japansite1 and 30 HTML documents in the IBM US site2
and classified them. Although they are very similar toeach other, we hypothesize that the subtle differences
between the templates for the two sites or the differences among the designers would be reflected in thedetails of the tag structures. Since we were concentrating on structural classification, we used only thetags and omitted the attributes and text3 . The sizesof the obtained trees were from 10 to 1,500 nodes, but
mostly ranging from 200 to 400, and there were about
90 distinct tags included. Each kernel was combinedwith the polynomial kernel. Table 2 shows the classification accuracy. The strict tree kernel performed thebest, being about 20% more accurate than the BoL
kernel.
5.2 Node Marking
5.2.1 Artificial Data
We also started with artificial data for the node marking experiments. Each node to be marked had either of
the two local structures shown in Figure 7. The nodes
to be marked are represented as double circles. A setof 30 trees with such nodes were randomly generated.
The size of each tree was between 30 and 50 nodes and10 labels were used. The average number of negative
examples generated from them was 142. We used thestrict tree kernel combined with the polynomial kernel.
The tests were performed for only the nodes labeled
C.
Table 3 shows the results averaged over several trials.
The precision, recall and F1 -measure are defined asfollows:
precision = 100 ·1#true positive predictions(13)#false positive predictions

http://www.ibm.com/jp/
http://www.ibm.com/
3
In this data set, the HTML documents in IBM Japansite are written in Japanese, while those in IBM US site are
written in English. The bag-of-words representation trivially achieves 100% classification accuracy since a learning
machine only needs to verify the language a particular document is written in.
2

Table 3. Node marking result for the artificial data
Poly

Precision

RecallF1 -measure

1
2
3
4
5

98.6%
100.0%
100.0%
100.0%
99.1%

55.9%
80.8%
83.4%
90.0%
94.1%

0.713
0.899
0.910
0.947
0.965

Figure 7. The local structures around the nodes to bemarked#true positive predictions(14)#false negative predictions
2 · precision · recall(15)
F1 -measure =precision + recall
recall = 100 ·We can see that the tree kernel also made good use of
the structural information for node marking tasks.
5.2.2 HTML Documents
Finally, we performed an experiment on information
extraction. Concretely, we tried to extract productimages from catalogues written in HTML. We used
54 randomly selected pages of product catalogues fordesktop PCs and notebook PCs in the IBM Japan Web
site (Figure 8) with the text removed. Besides productimages, the pages included images for product names,
buttons, logos such as ’Intel inside’, and so on. Eachpage had just one image to be extracted. The size ofthe each tree was from 200 to 800, but mainly from
300 to 400, and again, 90 kinds of tags were used inthese pages. From these trees, we generated negative
examples that were trees where an inappropriate image node was marked. The number of the generated
negative examples was 2,668. Both the strict tree kernel and the elastic tree kernel were used. The tests
were performed for only the image nodes.
The results are shown in Table 4. The results for
combinations of our kernels and the polynomial kernel are not shown since they did not improve the results. While the elastic tree kernel showed good performance, the precision of the strict tree kernel was
low. However, investigating the result, almost all false
positives for the strict tree kernel were caused by 6
documents which were only 11% of the entire set of
documents. Considering this, we feel the result forthe strict kernel is reasonable. Therefore, we feel that
our kernel-based methods show promise for information extraction tasks.

In some experiments of node marking, we sometimes
observed that a relatively small number of trees caused
many false positives, which resulted in low precisions.
It is also an open problem to decrease such burst false
positives. The advantage of using SVMs for the nodemarking problem is their good generalization performance for small datasets. This advantage is important, especially for such problems as information extraction, since it costs too much to label many examples by hand.

Acknowledgements
We would like to thank Michael Houle and Takeshi
Fukuda for helpful discussions. We would also like tothank the reviewers for their helpful suggestions.

References
Figure 8. An example of the catalogue pages

Abiteboul, S., Buneman, P., & Suciu, D. (2000). Dataon the Web. Morgan Kauffman.

Table 4. Node marking result for the HTML documents

Collins, M., & Duffy, N. (2001). Convolution kernel
for natural language. Proceedings of the Fourteenth
Neural Information Processing Systems.

Kernel

Cowie, J., & Lehnert, W. (1996). Information extraction. Communications of the ACM, 88–91.

Precision

RecallF1 -measure

11.9%
99.3%

79.6%
68.6%

0.207
0.811

Strict Tree
Elastic Tree

6. Conclusion
In this paper, we discussed the applicability of the kernel methods to semi-structured data mining problems
such as classification and information extraction. We
modeled semi-structured data by labeled ordered trees,and gave kernels for labeled ordered trees by generalizing the convolution kernel for parse trees (Collins &Duffy, 2001), and applied our kernels to classificationand node marking problems. The time complexities
of computing our kernels are still the same as for theparse tree kernel.
Next, we performed some experiments of classificationand node marking on artificial data and real HTML
documents. Although the experiments performed inthis paper were limited, to some extent, we could
demonstrate that structural information has some predictive power for some data, and that our kernel canefficiently capture this information. The results wereencouraging and showed the potential of the applicability of our method to more complex authentic semistructured data. However, it is still not clear how much
performance is improved by using structural information in addition to textual information. In future experiments, we plan to extend our kernel method tohandle textual information. We believe that this canbe achieved by further developing the techniques of label mutation.

Craven, M., DiPasquo, D., Freitag, D., McCallum,A., Mitchell, T., Nigam, K., & Slattery, S. (2000).
Learning to construct knowledge bases from theWorld Wide Web. Artificial Intelligence, 118, 69–
113.
Freund, Y., & Shapire, R. (1999). Large margin classification using the perceptron algorithm. Machine
Learning, 37.
Gärtner, T., Flach, P. A., Kowalczyk, A., & Smola,
A. J. (2002). Multi-instance kernels. Proceedings of
the Ninteenth International Conference on Machine
Learning.
Haussler, D. (1999). Convolution kernels on discrete structures (Technical Report UCSC-CRL-9910). University of Calfornia in Santa Cruz.
Inokuchi, A., Washio, T., & Motoda, H. (2000). An
Apriori-based algorithm for mining frequent substructures from graph data. The Fourth European
Conference on Principles and Practice of Knowledge
Discovery in Databases (pp. 13–23).
Joachim, T. (1998). Text categorization with support
vector machines. Proceedings of the tenth European
Conference on Machine Learning.
Kushmerick, N. (2000). Wrapper induction: efficiency
and expressiveness. Artificial Intelligence, 118, 15–68.
Mitchell, T. (1997). Machine learning. McGraw-Hill.

Sakamoto, H., Murakami, Y., Arimura, H., & Arikawa,S. (2001). Extracting partial structures from HTML
documents. Proceedings of the Fourteenth Florida
Artificial Intelligence Research Symposium.
Salton, G., & Buckley, C. (1988). Term weighting approaches in automatic text retrieval. Information
Processing and Management, 24, 513–523.
Vapnik, V. (1995). The nature of statistical learningtheory. Springer Verlag.
Watkins, C. (1999). Kernels from matching operations(Technical Report CSD-TR-98-07). University of
London, Computer Science Department, Royal Holloway.

Appendix
We describe our algorithms for computing kernels forlabeled ordered trees. Note that the nodes are postordered, and l(n) is the label of n.
A. Algorithm for The Labeled Ordered Tree
KernelTree Kernel(T1 ,T2 ):for n1 = 1, . . . , |NT1 |,for n2 = 1, . . . , |NT2 |,if l(n1 ) and l(n2 ) are distinct,
C(n1 , n2 ) := 0
else if both n1 and n2 are leaves,C(n1 , n2 ) := 1
else,
for i = 0, . . . , nc(n1 ),for j = 0, . . . , nc(n2 ),if i = 0 or j = 0,
Sn1 ,n2 (i, j) := 1
else,
compute Sn1 ,n2 (i, j) by Equation (7)end ifend forend forC(n1 , n2 ) := Sn1 ,n2 (nc(n1 ), nc(n2 ))end ifend forend forP|NT1 | P|NT2 |returnn1 =1
n2 =1 C(n1 , n2 )B. Algorithm for The Labeled Ordered Tree
Kernel Allowing Label Mutations
Tree Kernel(T1 ,T2 ):for n1 = 1, . . . , |NT1 |,for n2 = 1, . . . , |NT2 |,if both n1 and n2 are leaves,C(n1 , n2 ) := Sim(l(n1 ), l(n2 ))else,
for i = 0, . . . , nc(n1 ),for j = 0, . . . , nc(n2 ),if i = 0 or j = 0,
Sn1 ,n2 (i, j) := 1
else,
compute Sn1 ,n2 (i, j) by Equation (7)end ifend forend forcompute C(n1 , n2 ) by Equation (9)end ifend forend forP|NT1 | P|NT2 |returnn1 =1
n2 =1 C(n1 , n2 )C. Algorithm for The Labeled Ordered Tree
Kernel Allowing Elastic Structure Matchings
Tree Kernel(T1 ,T2 ):for n1 = 1, . . . , |NT1 |,for n2 = 1, . . . , |NT2 |,if both n1 and n2 are leaves,C(n1 , n2 ) := Sim(l(n1 ), l(n2 ))else ,
for i = 0, . . . , nc(n1 ),for j = 0, . . . , nc(n2 ),if i = 0 or j = 0,
Sn1 ,n2 (i, j) := 1
else,
compute Sn1 ,n2 (i, j) by Equation (12)end ifend forend forC(n1 , n2 ) :=Sim(l(n1 ), l(n2 )) · Sn1 ,n2 (nc(n1 ), nc(n2 ))compute Ca (n1 , n2 ) by Equation (13)end ifend forend forP|NT1 | P|NT2 |returnn1 =1
n2 =1 C(n1 , n2 )