     Baoliang LU      

1,2 , Xiaolin WANG1 , Masao UTIYAMA3

1 Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
2 MOE-Microsoft Key Lab for Intelligent Computing and Intelligent Systems, Shanghai Jiao Tong University, Shanghai 200240, China
3 National Institute of Information and Communications Technology (NICT), Kyoto 619-0288, Japanc Higher Education Press and Springer-Verlag 2009


Abstract In most large-scale real-world pattern classification problems, there is always some explicit information
besides given training data, namely prior knowledge, withwhich the training data are organized. In this paper, we
proposed a framework for incorporating this kind of priorknowledge into the training of min-max modular (M3 ) classifier to improve learning performance. In order to evaluate the proposed method, we perform experiments on alarge-scale Japanese patent classification problem and consider two kinds of prior knowledge included in patent documents: patent’s publishing date and the hierarchical structure of patent classification system. In the experiments, traditional support vector machine (SVM) and M3 -SVM without prior knowledge are adopted as baseline classifiers. Experimental results demonstrate that the proposed method issuperior to the baseline classifiers in terms of training costand generalization accuracy. Moreover, M3 -SVM with priorknowledge is found to be much more robust than traditional
support vector machine to noisy dated patent samples, whichis crucial for incremental learning.
Keywords prior knowledge, patent classification, support
vector machine, min-max modular network, task decomposition  
The automated classification has witnessed a new trend in
Received June 29, 2008; accepted November 25, 2008
E-mail: bllu@sjtu.edu.cn, mutiyama@nict.go.jp

the last few years. The previous dorminant way of building a classifier purely from labeled samples, namely training
data set, turns out to be less attractive since it seems to havereached a plateau in accuracy. To build more accurate classifiers, many researchers are now trying to incorporate priorknowledge into learning.
A variety of methods have been reported on this topic.
Overall these methods differ widely as they are tightly boundto the forms of the prior knowledge and the classification
tasks. Liu et al. [1] worked on the text classification taskof 20 New Groups† , and they adopted a combined approachof estimation maximum and naive Bayes to build a classifier
from prior knowledge, which is in the form of key words fortarget classes. Wu and Srihari [2] transferred prior knowledge into the weights of each training data point, and theclassifier of weighted margin support vector machine wasapplied on this enhanced training data set. Schapire et al.
[3] worked on audio classification, and they emerged theprior knowledge, which were some rough rules of classifying
samples proposed by domain experts, into the boosting algorithm. Zhu and Chen [4] took a domain dictionary as priorknowledge in classifying Chinese documents. If certain term
appeared in the document, the explanation of this term in the
dictionary was also taken into consideration when classifying this document by means of some mathematical formula.
Dayanik et al. [5] used the prior knowledge of the target
classes, which was in the form of textual descriptions, whileworking on several well-known benchmarks of text classification, including TREC 2004, Reuters-21578 and RCV1.
In their method, terms mentioned by prior knowledge wereendowed priority over the rest to be powerful features.

† http://www.cs.cmu.edu/afs/cs/project/theo-11/naive-bayes/20 newsgroups.tar.gz

110

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

Min-max modular (M3 ) network is an ensemble learning approach proposed by Lu and Ito [6,7]. The intuitionof this method is to handle complex classification problem
by divide-and-conquer strategy, that is, decomposing a complex problem into a series of simple subproblems, and using
one classifier for each subproblem. Meanwhile, this method
has the merit of speeding up the training of the classifiers
since subproblems can be processed in parallel, which isprecious for real-world applications. Though theoreticallyan M3 -classifier can solve any complex classification problem, yet it still reach a plateau of accuracy like many otherclassification methods in practical use, partly due to the generalization error. Therefore, some other ways still need to betried so as to improve it, such as incorporating prior knowledge into learning.
Now let us explain how we come to the idea of incorporating prior knowledge into dividing the training data. On
one side, how to decompose the data set of a class for an
M3 -classifier is not perfectly solved so far. On the otherside, there is always some extra information, namely priorknowledge, for most large-scale pattern classification problems, with which the training data are organized. We merge
these two sides of consideration, and find out that such priorknowledge about the training data is actually precious clue todecompose the data set. Thus a new decomposition methodwith the prior knowledge incorporated into is composed.
In this paper, the experimental demonstration is performed on a database of Japanese patent documents, andtwo kinds of information are taken as prior knowledge: publishing date and labels’ hierarchical structure. However, ourmethod can be applied to any other data set, only if it is wellorganized by some extra information.
The rest of this paper is organized as follows. The necessary background knowledge are presented at first in thenext two sections, Section 2 for M3 -classifier and Section 3
for patent classification task. Then the following Section 4
describes our method of incorporating prior knowledge into
task decomposition in detail. After that, Sections 5 and 6
present the experimental settings and results, and Section 7
presents some further analysis on these results. At last we
give the conclusions in Section 8.

   
The M3 -network was first introduced by Lu and Ito [6]. Before training this network, a K-class problem needs to be
divided intoK 
two-class subproblems by one-against-rest
2
strategy, or
two-class subproblems by a one-againstK
one strategy. Then the work procedure of M3 -network canbe launched, which consists of three steps: task decomposition, training base classifiers, and module combination.
Before the formal description of M3 -network, we will first
briefly explain its mechanism (see Fig. 1). Suppose that
Fig. 1(a) is the classification problem to be solved, in whichsmall disks represent positive samples and small rectangles
represent negative ones. Though simple at the first sight,
it’s actually a non-linear problem. To launch M3 -network
learning, the samples of each class are first divided into two
subsets, surrounded by dashed lines in the drawing. Thenby pairing, four smaller classification subproblems shown in
Figs. 1(b) through (e) are generated. One classifier is trainedon each of the subproblems, and dashed lines represent thediscriminant surfaces. Then with the minimum operator,
Fig. 1(f) is derived from Figs. 1(b) and (c), resulting in negative zone expanding; and in the same way, Fig. 1(g) is derived from Figs. 1(d) and (e). In the end, with the maximum
operator, Fig. 1(h) is derived from Figs. 1(f) and (g), resulting in positive zone expanding. In the outcomes of Fig.1(h),it can be found that a correct discriminant surface is generated.

Fig. 1Illustration of M3 -network

Now we will formally introduce the learning algorithmof M3 -network. Fig. 2 briefly illustrates the fine task
decomposition and the corresponding module combination
for a two-class problem. Here the learning of original twoclass problem is first decomposed into N1 ×N2 subproblems.
Then each subproblem yields a classifier, namely module,
through the training of base classifier. Eventually an M3 network, which can be used to classify new inputs, is generated by combining these modules. In this case, the M3 network consists of N1 × N2 individual modules, N1 MIN

Front. Comput. Sci. China 2009, 3(1): 109–122

units, and one MAX unit. Mini,∗ shown in Fig. 2 expresses
the MIN unit for the ith subset of the positive class. In thefollowing three subsections, we will describe the procedureof training M3 -network.

111

and imbalanced two-class problems should be further divided into smaller and more balanced two-class problems.
Assume that Xi is partitioned into Ni subsets in the form
Lji,
Xij = {Xlij }l=1

for j = 1, 2, . . . , Ni and i = 1, 2, . . . , K, (2)where 1  Ni  Li andNi

Xij = Xi .

j=1

After partitioning Xi into Ni subsets, every two-classproblem Tij defined by Eq. (1) can be further divided into
Ni × Nj smaller and more balanced two-class subproblems
as follows:(u, v)Tij(iu)= {(Xl

L

(u)

(jv)

i
, +1)}l=1∪ {(XlL(v)j, −1)}l=1,

for u = 1, 2, . . . , Ni , v = 1, 2, . . . , Nj ,i = 1, 2, . . . , K, and j = i + 1, i + 2 . . . , K (3)
(iu)

(jv)

where Xl
∈ Xiu and Xl∈ Xjv are the training inputs
belonging to class Ci and class Cj , respectively;
Fig. 2

Task decomposition and module composition of a two-class prob-

lem

Ni


(u)
Li = Li and

u=1

Nj


(v)

Lj

= Lj .

v=1

2.1 Task decomposition

2.2 Training base classifiers

Let Tij be the given training data set for a two-class classification problem,

After task decomposition, each of the two-class subproblems can be treated as a completely independent, noncommunicating task in the learning phase. Therefore, all thetwo-class subproblems defined by Eq. (3) can be efficiently
learned in a massively parallel way.
From Eqs. (1) and (3), we see that a K-class problem isdivided into
K−1
K
 
Ni × Nj ,
(4)

L

j
j
i
Tij = {(Xli , +1)}L
l=1 ∪ {(Xl , −1)}l=1 ,for i = 1, 2, . . . , K and j = i+1, i+2, . . . , K (1)where Xli ∈ Xi and Xlj ∈ Xj are the training inputs belonging to class Ci and class Cj , respectively; Xi is the set oftraining inputs belonging to class Ci ; Li denotes the numberKK
Xi = X ; andLi = L. In this paper,of data in Xi ;
i=1

i=1

the training data in a two-class problem are called positive
training data if their desired outputs are +1. Otherwise, they
are called negative training data.
Although the two-class problems defined by Eq. (1) aresmaller than the original K-class problem, yet this partition
may be not adequate for parallel learning. Since the numberof samples in each class may vary largely, the sizes of thesetwo-class problems can be quite different. Thus the training
period can be delayed by some larger problems. Moreover,a large class and a small class will form an imbalanced classification problem – too many samples in one side – which
will raise the difficult in training the classifiers [8]. To speed
up training and improve classification accuracy, all the large

i=1 j=i+1

two-class subproblems. The number of training data for eachof the two-class subproblems is aboutLi /Ni  + Lj /Nj .

(5)Since Li /Ni  + Lj /Nj  is independent of the number ofclasses K, the size of each of the two-class subproblems ismuch smaller than the original K-class problem for reasonable values of Ni and Nj . In this paper, traditional SVMs are
selected as base classifiers and used to learn all the two-classsubproblems.
2.3 Module combination
After all of the two-class subproblems defined by Eq. (3)have been learned by base classifiers, all the trained SVMs
are integrated into an M3 -SVM with the MIN and MAX

112

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

units according to the following two combination principles:the minimization principle and the maximization principle[9].
• Minimization principle
Suppose a two-class problem B is divided into P smaller
two-class subproblems, Bi for i = 1, 2, . . . , P , and also
suppose that all the two-class subproblems have the same
positive training data and different negative training data. If
the P two-class sub-problems are correctly learned by thecorresponding P individual SVMs, Mi for i = 1, 2, . . . , P ,then the combination of the P trained SVMs with a MIN unit
will produce the correct output for all the training inputs in
B, where the function of the MIN unit is to find a minimum
value from its multiple inputs. The transfer function of the
MIN unit is given byP

q(x) = min Mi (x),
i=1

(6)

where x denotes the input variable.
• Maximization principle
Suppose a two-class problem B is divided into P smaller
two-class sub-problems, Bi for i = 1, 2, . . . , P , and also
suppose that all the two-class subproblems have the samenegative training data and different positive training data.
If the P two-class subproblems are correctly learned by thecorresponding P individual SVMs, Mi for i = 1, 2, . . . , P ,then the combination of the P trained SVMs with a MAX
unit will produce the correct output for all the training input
in B, where the function of the MAX unit is to find a maximum value from its multiple inputs. The transfer function of
the MAX unit is given byP

q(x) = max Mi (x).
i=1

(7)

     
The classification task discussed in this paper is to classify
Japanese patent documents on the section level of International Patent Classification (IPC). In this section, we will
present the necessary background knowledge of patent classification, including the related work, the database we workon, and the IPC taxonomy.
3.1 Related work
Patents are playing more and more important roles in the
progress of science and technology nowadays. As a result,automatic patent classification, which is a basic data min† http://research.nii.ac.jp/ntcir/index-en.html

ing technique on patents, has received much more attention.
The European Patent Office tried a variety of preprocessing
methods on patent data such as assigning different weights
to patent sections and utilizing the citation between patents[10]. Larkey designed a system for searching and classifying
U. S. patent documents based on query, and the K-nearestneighbor algorithm was adopted in this system [11,12]. The
Japan Patent Office developed a patent classification system
based on keywords and used about 310000 patents in the
training procedure. They achieved 96% classification accuracy in 38 categories and 82% classification accuracy in
2815 subcategories [13]. Fall and his colleagues compared
the most commonly used classifiers on patent classification,such as naive Bayes, K-nearest-neighbor algorithm, support
vector machine, neural networks, and decision rules, and reported that SVM provides the best performance [14,15].
3.2 Patent database
The corpus we work on here is provided by Japanese National Information Institutes’ Testing Corpus for Information
Retrieval (NTCIR): an organization which aims to evaluate
the effectiveness of patent retrieval and classification from ascientific point of view. The corpus is publicly available forresearch purpose† . It includes Japanese patent applications
over 10 years from 1993 to 2002 (approximately 3500000
documents), and each patent’s document has a title and threefields: abstract, claim and description (see Table 1), among
which the title and the claim are reported to be more valuable
for classification.
3.3 IPC taxonomy
Once a patent application is submitted to a government
patent office, it is usually assigned to one or more classification codes by human experts according to IPC. A patent
has at least one IPC code, called main code, and maybe a setof secondary codes relating to other aspect expressed in thepatent [16,17].
IPC is a complex hierarchical classification system, which
divides all the technological fields into 8 sections, 120classes, 630 subclasses and approximately 69000 groups.
Fig. 3 illustrates the first four layers of IPC. The section layer
is the top layer, and it has eight categories denoted by lettersfrom A to H. The class layer is under the section layer andexpressed as a section label followed by two digits. For example, ‘A01’. The third layer is the subclass layer, which isrepresented as a class label followed by a capital letter. For
example, ‘A01B’. In general, current research has mainly
concentrated on the top three layers since the definitions oflayers below subclasses are still frequently changed.

Front. Comput. Sci. China 2009, 3(1): 109–122

113

Table 1 The structure of Japanese patent documents
PATENT-JA-UPA-1998-000001
Bibliography
[publication date](43)

[title of invention](54)

Abstract[purpose] . . .

[solution]

 . . .

Claims
[claim1] 

 . . .

[claim2]  

 . . .

Description
[technique field][prior art]
[problem to be solved][means of solving problems][effects of invention]...

  . . .
 ...

  . . .
   . . .
 . . .
...

 Explanation of Drawing [figure1]...

Fig. 3

...

Illustration of IPC taxonomy. Here, ‘A’ is the SECTION category label, ‘A01’ is the CLASS category label, ‘A01B’ is the SUBCLASS

category label, and ’A01B 13/08’ is the GROUP category label.

             
To justify our proposed method, let us first consider what
an ideal division of a class’s training data, so as to decompose the original classification task? Fig. 4 gives us a direct
idea, that is, within the scope of a class, the similar samples
should be together and put into the same subset. Therefore,
the transferred problem is how to recognize the similarity

among the samples?
In our previous work, we have proposed various division
strategies. These methods fall into the following three categories. 1) random approach; 2) clustering based approach;and 3) explicit prior knowledge based approach. The random
approach is a straightforward way and no any similarity concerning the training data is considered [7,9]. The clustering
based approach is carried out in the feature space, and neighbouring is taken as similarity [18]. Explicit prior knowl-

114

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

Fig. 4 Illustration of an efficient task decomposition way for M3 -network.
(a) Original task, (b) sub-task I, (c) sub-task II, (d) solution of M3 - networkedge based apporoach make use of extra information abount
the samples, which is usually acquired during collecting thesamples. For example, when training a classifier to recognize the gender from human’s facial images, we divided thetraining data by the human’s age [19].
In this paper,we take the deep prior knowledge as clues,
which makes the division much more reasonably. Our solution is that the samples with same attributes, which are derived from the prior knowledge, are similar ones and shouldbe put together. This solution is kind of similar with the previous explicit prior knowledge based division approach, andthe difference is the sorts of prior knowledge being used. In
this paper, the deep knowledge of hieratical labels itself isutilized.
Fig. 4(a) shows the original classification problem, where
small disks and small rectangles denote positive samples andnegative samples, respectively. All the positive samples are
divided into two subsets (surrounded by dotted lines), thus
two subtasks are generated. In Figs. 4(b) and (c), two classifiers are trained on these two subtasks (dotted line for dis-

criminant interface). Finally, in Fig. 4(d), M3 -network integrates the two classifiers and learns the original classification
problem.
To simplify the description, we present our method in thecontext of patent classification. Note that our method can beeasily applied to other databases with the substitution of theprior knowledge. Now suppose that we want to train an M3 classifier to classify patent samples in the section level (seeSection 3), the training data decomposition with publishingdate and subclass label as prior knowledge, namely M3 -YC,
can be described as the following three steps:
Step 1 Divide the data set of each section by publisheddate, each subset for one year;
Step 2 Further divide the subsets by class, thus eachsubset for one class published in one year;
Step 3 Further divide the remained large subsets into
subsets of fixed size randomly.
Figure 5 also illustrates this process. Different attributes
among the samples are shown by colors and shapes. The
colors are corresponding to publish dates, red samples being published in the same year and blue ones in another.
The shapes are corresponding to the sub-categories, rectangles and triangles for two sub-categories of category A, andthe circles and diamonds for two sub-categories of category
B. The task decomposition consists of three steps, first by
the prior knowledge of publish year (b), then by the subcategories (c), at last by random for some remained large
subsets (d). Typically, if the first two steps are removed fromthe above procedure, that is, the data set of each section isdivided randomly at first, then it becomes the conventional
M3 -SVM, namely M3 -Rand. In this paper, M3 -Rand to-Fig. 5 Task decomposition with prior knowledge. (a) Original task, (b) first step decomposition result by publish year, (c) second step decomposition result by sub-categories, (d) third step decomposition result by random

Front. Comput. Sci. China 2009, 3(1): 109–122

gether with traditional SVMs serve as the baseline methods
for comparing with our proposed method, M3 -YC.
Both M3 -Rand and M3 -YC have the process of random
decomposition, through which the task of learning the original classification problem is eventually decomposed into
sub-tasks with expected size. Normally a parameter, the target subset size, needs to be set to tune this process. If target
size is too small, it will result in too many subproblems. If
there are no enough number of CPUs available under thissituation, the training and test time cost will be raised rather
than being reduced. On the contrary, if the target size is toolarge, some subproblems will be too large and complicatedfor one base classifier to learn. According to our preliminary experiments, we eventually decided that the target sizeof subset is 2000 samples.

115• Tokenization
This step is to generate a list of clean and informative words
from each patent document. Four fields of raw patent text –Title, Abstract, Claim and Description – are extracted fromeach structured patent document (see Table 1), as they are
the parts most informative about the patent’s content. Thenthese texts are segmented into isolated words by using thesoftware Chasen† . After that, the stop words need to be removed from the results. The remained words, namely terms
in the research domain of text categorization, are the features
for successor classification task. Table 3 shows the result we
get from the example illustrated in Table 1.
Table 3The structure of Japanese patent documents

 (soil)  (improve)  (methods)  (working) (machine) % title (subsoil)  (crack)  (snow)       · · · % abstract (subsoiler)      · · · %claim

5.1 Data sets
We had an extended version of NTCIR-5 Japanese patent
database at hand, which consists of all the patent applications published by Japanese Patent Office from 1993 to 2002.
So as to systematically evaluate three methods: SVMs, M3 Rand, and M3 -YC, we made eight pairs of data sets (see Table 2). The test sets were fixed as we wanted all the results tobe comparable. The training set ended just before the test set
as the most recent patent records were the most useful. The
start points of training sets varied so the sizes of training setschanged.
Table 2

Description of training and test data sets

number of years
for training

years
training

set size
test

training

test

1

2000

2001,2002

3580727335702

1999,2000

2001,2002

7140047335703

1998–2000

2001,2002

10553917335704

1997–2000

2001,2002

13868507335705

1996–2000

2001,2002

17273567335706

1995–2000

2001,2002

20643257335707

1994–2000

2001,2002

24152367335708

1993–2000

2001,2002

27625637335705.2 Feature extraction and filtering
Several steps of preprocessing need to be done so as to get
the vector representation of the Japanese text. They are tokenization, term filtering, and term indexing.
† http://chasen.naist.jp/hiki/ChaSen/ (patent)    · · · %description• Term filtering
This step is to remove the useless terms for classification
task. Not all the terms occurring in a document can provide information on the document’s class. With these terms
removed, the number of the representation vectors’ dimensions is reduced, thus the computational cost will be cut
down and the generalization error will be reduced. There arethree popular judgment criteria of terms in the TC domains–χavg , χmax and Information Gain (IG) [20].
The χ2 is a statistic measurement of the lack of independence between two random variables, the term t and the classc. It can be compared to the χ2 distribution with one degreeof freedom to judge extremeness. The formula of χ2 for abinary classification problem is:χ2 (t, c) =Tr (ntc nt̄c̄ − ntc̄ nt̄c )2,
nt nt̄ nc nc̄

(8)where Tr is the training corpus, ntc is the number of samples
that belong to c and have t, nt̄c is the number of samples thatbelong to c but don’t have t, and the rest may be deduced byanalogy. As for the multiclass problem, there are two extensions based on the mechanism to integrate the measurement
on each class:χ2max (t) = max χ2 (t, c),(9)

χ2avg (t) = avg χ2 (t, c),

(10)

c∈C

c∈C

116

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

where C is the whole set of classes.
IG measures the decreased bits of the information of adocument’s classes by knowing the presence or absence of
certain term in this document.
IG(t) = Inf o(c) − Inf o(c|t)
m=−Pr (c)logPr (c) + Pr (t)Pr (c|t)logc∈CPr (c|t) + Pr (t̄)

c∈CPr (c|t̄)logPr (c|t̄),

(11)

c∈C

where Inf o(c) is the bits of information of c, Inf o(c|t) isthe bits of conditional information of c knowing t, and Pr (x)is the possibility of x occurrence.
We first decide which criterion to adopt by the pilot experiments, with certain number of top terms under one criterion
being used for training and test. The χ2avg approach turned
out to be the best. Then we decide the number of features
to use by trying the figures 2500, 5000, 7500, . . . , 160000,
and 5000 is found to be the smallest number which could
give nearly top performance. Table 4 shows the top 10 terms
sorted by χ2avg , most of which are technique terms as patentdocuments mainly deal with technological stuffs.
Top 10 terms selected by χ2avg

Table 4

terms


data

10384.72



information

10199.42

circuit9561.67

signal8387.75record7901.17

article7528.72

contain

7374.12connect

7324.43

insulation

7194.85

baseplate

7076.72|Tr |,nTr (t)No.

Vectors

1

72 : 0.730

98 : 1.790

138 : 1.310

141 : 4.495...

2

28 : 26.353

29 : 9.232

31 : 2.795

71 : 1.463...

371 : 1.463

79 : 2.441

85 : 2.993

113 : 11.393...

4

42 : 2.164

60 : 0.905

109 : 2.061

138 : 2.947...

5

28 : 7.529

72 : 6.577

139 : 8.103

167 : 8.728...

5.3 Computational platform

5.4 Training base classifier• Term indexing
This step is to generate the real numerical vectors. Suppose
there are n unique terms occurring in the training corpus,
then the vectors of the samples will be n in length, with eachdimension corresponding to one term. As to compute theweight – extent of importance – of a term to a document,
there exist several methods and we adopt the dominant one– TFIDF [21]:tf idf (t, d) = n(t, d) log

Table 5 The vector representations of patent documents. The format of The vectors adopted by SVMlight is taken, that is, vetor:=(dimension:value)+

All of the experiments were performed on a Lenovo cluster
system consisting of three fat nodes and thirty thin nodes.
Each fat node has 32 GB of RAM and two 3.2-GHz quadcore CPUs, while each thin node has 8 GB of RAM and two
2.0-GHz quad-core CPUs. Experiments with the conventional SVMs were performed on the fat nodes, because theyneed large memory, while experiments with the M3 -SVMs
were done on the thin nodes, because each sub-problem was
small and a lot of processors were required for parallel training.

χ2avg

explanation

the training corpus, n(t, d) denotes the number of times t
occurs in d, namely term frequency, and nT r (t) denotes thenumber of documents where t occurs, namely document frequency. TFIDF is actually in the style of Information Retrieval, which embodies two intuitions that (i) the more often
a term occurs in a document, the more it is representative of
its content, and (ii) the more documents a term occurs in, theless discriminating it is. Table 5 shows the vector representations of some patent documents.

(12)

where t denotes a term, d denotes a document, Tr denotes

M3 -network is just a general framework for pattern classification, and some classifiers, namely base classifiers, need tobe embedded into it. There were several alternative choices,such as artificial neural networks [6,7], naive Bayes, Knearest-neighbor algorithm [22,23], and SVMs. Here conventional SVMs were adopted for its well-known excellent
performance on classification tasks as well as text categorization. For the trade-off of performance and cost, the linear
kernel was taken. The kernels of Radius Base Function and
Polynomial would hopefully provided better performance,
but they would cost overwhelmingly long time in training
conventional SVMs. The SVMlight , an implement of SVM
by Joachims [24], was adopted for it has been specially optimized on text categorization tasks. It actually played tworoles in this paper, the baseline method and the base classi-

Front. Comput. Sci. China 2009, 3(1): 109–122

fiers for M3 -SVMs.

As a result, M3 -SVMs have fulfilled the learning on all
the training sets with the accuracies of nearly 100%.

5.4 Performance measurement
The convention performance measurement of accuracy inmachine learning domain turns out to be less rational for
most TC tasks. Instead, the function F1 is usually used in
TC domain. The formula of F1 of one class is [21]:
2P R
,
P +R
TP
P=
,
TP + FPTPR=,
TP + FN

F1 =

(13)
(14)
(15)

where T P is the number of classifier’s true positive predictions, F P is the number of false positive predictions, andF N is the number of false negative predictions. P is named
the precision, and R is named the recall. In practise, there
are the two following versions of F1 , depending on the strategy of integrating all the results of individual samples:
2P R
,
P +R
2Pc Rcmacro − F1 = avg,
Pc∈C c + Rc
micro − F1 =

(16)
(17)

where P and R are computed with all the classes, while Pc
and Rc are computed on only classes c. For example, samples actually belongs to classes c1 and c2 , while the classifier’s
predictions is c2 and c3 , then in computing micro − F1 , T P ,F P and F N will be increased by 1, while in computing Pc1
and Rc1 for macro − F1 , only F N will be increased by 1.

!     
6.1 Accuracy
Figure 6 presents the experimental results, with micro − F1
and macro − F1 as accuracy measurement.
The following conclusions can be drawn from these results:
1) On the aspect of test accuracy, the two M3 -SVM methods, M3 -Rand and M3 -YC, are both superior to conventional SVMs. We can learn from the training scoresthat SVMs with linear kernel are unable to learn the
training set completely, because its micro − F 1 andmacro − F 1 are only about 80%. On the contrary, as
an ensemble learning algorithm, M3 -SVMs can generate powerful classifier by combining simple classifiers.

2) M3 -Rand and M3 -YC show superior robustness to conventional SVMs over dated samples. Along the moving backward of the starting time point of training set,more and more dated samples are added, thus the performance of conventional SVMs decreases. Contrarily,
the performance of two M3 -SVMs algorithms become
better and better at the same time. Though their performance deceases a little in the 5th year point and 7thyear point, yet the ranges are very small and have little
impact on the curves’ overall trend.
3) M3 -YC over-performs M3 -rand on each year point,
which indicates incorporating prior knowledge of publishing date and subclass into task decomposition willundoubtedly improve the classification performance.
Something needs to be addressed here. The differenceof M3-YC and M3-Rand in performance is small, which
is kind of disappointing. The reason may be that the label
information of training samples in subclass is not adequate
for division. In fact, subclasses of IPC are extremely imbalanced, and many subsets are larger than predefined set
size, in which randomly dividing has to be performed. For
example, in the training set of eight years, class G contains
216105 samples and 13 subclasses. However, the two largest
subclass of G06 (62767 samples, 29%) and G01 (48700 samples, 23%) own more than a half of the overall samples,
which have no choice but to be divided randomly. Thus, M3YC and M3-Rand will lead to similar training subsets, which
draw their performance close. Anyhow, from the experimental results here, incorporating prior knowledge into division
does undoubtedly improve the classification accuracy. IPC
is a hierarchical structure with six levels, and with the information of these deep subclasses, the training set can be adequately divided, thus less random division will be needed.
We are to carry out these experiments soon, and more improvement can be expected.
In addition, the data sets that our method applies to are
required to have hierarchical structures (temporal information may also be used if existing). Nowadays, many data setsother than patent documents are organized in such structures.
For example, the new version of Reuters corpus – RCV1–
employs a hierarchical structure and the detailed description
can be found in its release page† [25]. Another example isweb pages where a uniform hierarchical structure of ODP isusually adopted (Open Directory Program‡) [26].

† http://jmlr.csail.mit.edu/papers/volume5/lewis04a/lyrl2004 rcv1v2 README.htm‡ http://www.dmoz.org/about.html

117

118

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

Fig. 6 Performance comparison of SVMs, M3 -Rand and M3 -YC: (a) micro − F1 on test data; (b) macro − F1 on test data; (c) micro − F1 on
training data; and (d) macro − F1 on training data

6.2 Time cost
As mentioned in Section 1, M3 -SVMs (both M3 -Rand andM3 -YC) have the merit of parallel computing, which can
speed up the learning of classification problems. However,the Lenovo parallel computer was actually being shared byother users while we were conducting the experiments, so
the accurate time cost of M3 -SVMs could not be measured,
while the time cost of SVMs was recorded since it didn’t
involved parallel running.
We evaluate the time cost of M3 -YC by using the following formula:tM 3 =

nmod × t0,
ncpu

experiment, and the eventual value we get is 0.025 second
per module.
Figure 7 presents the time costs of SVMs and M3 -YC in
our experiments. From these results, we can find out that theM3 -YC’s time cost is only about 1/10 of the SVM’s, which
agrees with our expectation well.

(18)

where nmod is the number of modules (or subproblems) generated by M3 -SVMs, t0 is the average time cost of per module, and ncpu is the number of CPUs. During our experiments, nmod have been recorded automatically and ncpu is
30 on Lenovo computer. As for t0 , it must be measured by

Fig. 7

Time cost of SVMs and M3 -YC

Front. Comput. Sci. China 2009, 3(1): 109–122

We would follow these two viewpoints respectively in thediscussions below.

" #$    
In this section, we analyze the experimental results mentioned above by observing and comparing the outputs ofthree methods on certain samples. Our object is to find out
M3 -YC’s advantages and disadvantages, so as to seek any
possibility to further improve it. In the first half of this section we work on the contingency tables, and in the second
half we go deep into analysis of individual patent samples.
7.1 Contingency table
In statistics, contingency tables are used to record and analyze the relationship between two or more variables, mostusually categorical variables. They can be taken as usefultools in analyzing the results of classification experiments[21]. The contingency tables of three different methods arepresented in Tables 6, 7, and 8. The values in the diagonalline represent the proportion† of samples correctly categorized, while the others represent the proportions of the samples wrongly categorized by the way corresponding to theirpositions in the table. From these tables, the following two
observations can be obtained.
1) From the viewpoint of data set, we can find out whichclasses of samples are easy to be recognized and whichclasses of samples are confusing, specially, with whichclasses they are likely to mix.
2) From the viewpoint of classification methods, we cantell on which classes a classification method is strong,and on which classes it is weak, further, for whichclasses it might mistake these samples.
Table 6

SVM’s contingency table
A

B

C

D

E

119

F

G

H

A

743

34

22

5

15

14

33

6

B

101

1389

69a)

16

51

81

92

49

C

38

94

734

11

7

16

33

24
1

D

8

8

3

83b)

1

1

1

E

23

27

8

1

349

22

14

6

F

23

71

14

2

21

645

18

20

G

54

124

32

2

15

38

2056

234

H

25

85

61

2

11

40

289

1884

Note:
a) The samples involved by B-th row and C-th column are the samples ofclass B and wrongly categorized into class C. The ratio of such samples
over the whole data set is 0.0069;b) The samples involved by D-th row and D-th column are the samples ofclass D being correctly categorized.

Table 7

M3 -Rand’s contingency table
A

B

C

D

E

F

G

H

A

797

50

22

6

17

15

38

8

B

75

1450

85

11

40

86

110

66

C

29

68

754

5

5

12

30

34

D

8

11

5

97

1

2

2

1

E

20

28

6

1

373

18

14

7

F

20

59

12

1

18

671

20

26

G

47

107

23

1

10

28

2092

240

H

18

59

38

1

6

26

232

1843

Table 8

M3 -YC’s contingency table
A

B

C

D

E

F

G

H

A

789

45

20

5

16

14

33

7

B

79

1461

83

11

40

83

98

60

C

29

64

757

5

5

11

27

32

D

8

10

5

97

1

2

2

1

E

20

26

6

1

372

17

12

6

F

21

57

11

1

18

674

19

23

G

51

108

24

2

10

28

2126

228

H

18

60

38

1

6

27

220

1868

• Viewpoint of data setsThough these contingency tables, Tables 6, 7 and 8, are computed from the results of different classification methods, yettheir similarity are obvious. Such similarity, which lies under various classification systems, can be considered as theinside characteristics of data set. So as to simplify the analysis, we come up with a new table, Table 9 by averaging thevalues of the three previous tables.
A discovery from Table 9 is that the values of (G,H) and(H,G) are the largest among all the fault cases, which indicates these two classes are easy to mixed up. According to
the authority documents of IPC, class G is Physics Instruments, and class H is Electricity. Since both of these two arefoundation of modern technology, it is understandable that
there exist lots of intersections between them. For example,
G08, a subclass of G, was signaling which contains collecting, transmission, and display of signals, while electronics isundoubtedly the main technique to fulfill these tasks. On thecontrary, H03, a subclass of H, is basic electronic circuitry
which contains making electronic component, designing amplifying circuits, and these subjects are all based on physicaltechniques.

† The number is multiplied by 104 for pretty printing, e.g. 15 means the ratio of 0.0015

120

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training data

Table 9 The averaged contingency Table of SVMs, M3 -Rand, and M3 -Table 11

YC
A

B

C

D

E

F

G

H

A

777

43

21

5

16

14

35

7

B

85

1433

79

13

44

84

100

58

C

32

75

748

7

6

13

30

30

D

8

10

4

93

1

2

1

1

E

21

27

7

1

364

19

13

6

F

21

63

13

1

19

663

19

23

G

51

113

26

2

12

31

2091

234

H

20

68

46

1

8

31

247

1865

• Viewpoint of classification methods
To simplify the comparison between classification methods,
differential contingency tables are made (see Tables 10 and
11).
The differential contingency table of M3 -YC and SVM

Table 10

A

A

B

C

D

E

F

G

H

+46

+11

−2

0

+2

0

0

+1

−5

−11

+3

+6

+10

B

−22

+72

+15a)

C

−9

−29

+22

−6

−1

−4

−6

+7

D

0

+2

+2

+14

0

+1

+1

0

E

−2

−1

−2

0

+23

−5

−1

0

F

−2

−14

−3

−1

−3

+28

0

+3

G

−3

−16

−8

0

−5

−10

+70

−5

H

−7

−25

−23

−1

−5

−413

−69

−16

Note: a) e.g., This figure meant the ratio of classifying class B’s samples
into class C is increased by 0.0015 in M3 -YC compared to SVM

From the differential table between M3 -YC and SVM,
it can be found that the values in the diagonal line are all
positive, which indicates M3 -YC raise accuracy on all theclasses. Moreover, the value of (A,B) is positive and thatof (B,A) is negative, which indicates M3 -YC classified moreclass A’s samples into class B and less class B’s samples intoclass A, which can be interpreted as it raises the recall ofclass B and lowers that of class A.
Similar analysis can be performed on the differential tables of M3 -YC and M3 -Rand. M3 -YC shows a rise in theclasses of B, C, E, F, G and H, while it shows decent in class
A. Besides, more samples of class B and F are wrongly classified into class A by M3 -YC. It should be noted that thevalues of both (G,H) and (H,G) are negative, which indicates that M3 -YC can handle the samples of classes F and H
much better. This improvement plays an key role in raising
the global classification accuracy.

A

The differential contingency table of M3 -YC and M3 -RAND
A

B

C

D

E

F

G

H

−8

−5

−2

0

−1

−1

−5

−1

B

+4

+11

−1a)

0

+1

−3

−12

−6

C

0

−4

+3

0

0

0

−3

−2

D

0

−1

0

0

0

0

0

0

E

0

−1

0

0

−1

−1

−1

−1

F

+1

−2

−1

0

0

+3

−2

−3

G

+4

+1

+1

0

+1

0

+35

−12

H

0

+1

0

0

0

+2

-12

+25

Note: a) e.g., This figure meant the ratio of wrongly classifying class B’s
samples into class C is decreased by 0.0001 in M3 -YC compared to M3 Rand

7.2 Individual patent documents
We have already known some global characteristics of patentdocuments, such as which two classes are easy to be mixed
up, and on which classes the classification methods tend to
make mistakes. In this section we will directly read somepatent documents, so as to find the cause of these phenomena. After some analysis, we categorize the puzzle patentdocuments into two sorts.
The first sort is the kind of patent documents which are ofgreat possibility of being wrongly classified. In most cases
they contain typical words of irrelevant classes, so any classification method with terms as features tends to make wrong
predictions on them. On the contrary, there exist some otherpatent documents which were only partly similar to someirrelevant classes. As they lie in the margin zone of beingclassified wrongly and being classified correctly, we named
them marginal patent documents. The patent documents ofthe first sort are wrongly classified by all the classification
methods, while the patent documents of the second sort are
correctly classified by some methods and wrongly classified
by the others.
• Mistakable patent documents
Class G and class H are found to be easily mixed up in previous analysis on contingency tables (Section 7.1). So we pickout two patent documents of class H, which were wrongly
classified into class G by all the three methods, SVMs, M3 Rand and M3 -YC (Tables 12 and 13)
Example I is certainly very confusing, for the physicaltechnique term of harden (  ), insulation (  ) andintensity (  ) frequently appear in this patent document,
so it is not strange at all that it is mistaken as class G. Example II belongs to both class G and class H, which can bedetected from its IPC labels. As a result, it is acceptable that

Front. Comput. Sci. China 2009, 3(1): 109–122
Table 12

Example I: class H’s sample wrongly classified into class G

121

Table 14 Example III: class H’s sample mistaken for class G only by SVM

ID

PATENT-JA-UPA-2001-006462

ID

PATENT-JA-UPA-2001-006480

Title    

Title

   (switch ) 

IPC

H01H/13/02 B60R/16/02 . . .

      
IPC

H01B/13/16 C08F/2/58 . . .

Abstract           

Abstract                    ...
Claim  Claim

                                        . . .

 %                 . . .
Description            







   ...

Description   &'                  !              

 . . .

 ...
Table 13

Example II: class H’s sample wrongly classified into class G

ID

PATENT-JA-UPA-2001-006485

Title    (Switch)

IPC

H01H/13/14 G07F/9/00 . . .

Abstract    

M3 -RandID       Table 15 Example IV: class H’s sample mistaken for class G by SVM and      

Title  IPC

H01J/9/227 H01J/31/00

Abstract                !"         #
$ 



 
 



 ...

Description         !"                 ...

this patent document is classified into class G, which is considered to be a correct prediction in the context of multi-label
classification.
• Marginal patent documents
Here we also give two examples, both of which belong toclass H and were mistaken for class G by SVMs or M3 Rand, while correctly classified by M3 -YC (see Tables 14
and 15). Example III contains many common words whichhave moderate tendency towards some other classes, such asmechanism (  ), discrimination (  ) and model (  ), and those words together make it become a marginal
patent document. Example IV’s topic electron tub (  ) happens to be a typical word for both class G (physicalinstruments) and class H (electronics), which is the reason
why it became a marginal patent document of both class G
and class H.



Claim



   

Description 



 

   (  



 




 



 . . .

  











 

  . . .

    

 !        &    . . .
Claim

PATENT-JA-UPA-2001-006544

      (  . . .

% &  
In this paper, we have investigated the idea of incorporating
prior knowledge into learning by dividing the training data.
We have proposed a new task decomposition method for M3 SVMs. To testify our proposed method, we apply it to thetask of patent classification with samples’ publishing dateand labels’ hierarchical structure as prior knowledge, namely
M3 -YC. Two other methods, conventional SVMs and conventional M3 -SVM with random task decomposition strategy, namely M3 -Rand, are taken as baseline methods. The
experimental results show that M3 -YC always over-performs
SVMs and M3 -Rand, which demonstrate incorporating priorknowledge into learning can efficiently raise the classification accuracy.
Moreover, the research with the new method on patent

122

Baoliang Lu, et al. Incorporating prior knowledge into learning by dividing training dataclassification brings us the following two conclusions, which
may be useful for further real-world applications.

ceedings of International Joint Conference on Neural Networks, 2004,
735–740
10. Krier M, Zaccá F. Automatic categorization applications at the Euro-

1) The problem of patent classification is not linear separable, since conventional SVMs with linear kernel canonly achieve training accuracies about 80%, while both
M3 -Rand and M3 -YC reach training accuracy of nearly
100%. As a result, the M3 -SVMs methods are superior
to conventional SVMs in generalization accuracy.
2) The dated patent samples actually contain noises, which
can harm the classification performance. It may becaused by the revise of IPC standard, evolvement of
the language style, or the shift of research focus. Both
M3 -Rand and M3 -YC methods are robust to such noises
while conventional SVMs are not. Along with more andmore samples added into the training set, the classification accuracy of conventional SVMs decreases, while
those of M3 -Rand and M3 -YC increase instead.

pean patent office. World Patent Information. Elsevier, 2002, 24(3):
187–196
11. Larkey L. Some issues in the automatic classification of US patents.
Learning for Text Categorization. Technical Report WS-98-05, 1998,
87–90
12. Larkey L. A patent search and classification system. In: Proceedingsof the fourth ACM conference on Digital libraries, 1999, 179–187
13. Mase H, Tsuji H, Kinukawa H, Ishihara M. Automatic patents categorization and its evaluation. Transactions of Information Processing
Society of Japan(IPSJ), 1998
14. Fall C J, Benzineb K. Literature survey: Issues to be considered in theautomatic classification of patents. World Intellectual Property Organization, 2002, 29
15. Fall C J, Torcsvári A, Benzineb K, Karetka G. Automated categorization in the international patent classification. In: Proceedings of
ACM’S Special Interest Group on Information Retrieval. New York:ACM Press, 2003, 37: 10–25
16. Fujii A, Iwayama M, Kando N. Test collections for patent retrieval andpatent classification in the 5th NTCIR workshop. In: Proceedings of

Acknowledgements This research was partially supported by the National Natural Science Foundation of China (Grant No. 60773090) and the
Fujitsu Research and Development Center Co., Ltd., Beijing, China.

the 5th international conference on language resources and evaluation,
2004, 1643–1646
17. Fujii A, Iwayama M, Kando N. Introduction to the special issue on
patent processing. Information Processing and Management, 2007,! 
1. Liu B, Li X L, Lee W S, Yu P S. Text classification by labeling words.
AAAI, 2004
2. Wu X Y, Srihari R. Incorporating prior knowledge with weighted margin support vector machines. In: Proceedings of International Conference on Knowledge Discovery and Data Mining, 2004, 326–333
3. Schapire R E, Rochery M, Rabim M, Gupta N. Boosting with priorknowledge for call classification. IEEE Transactions on Speech andAudio Processing, 2005, 13, 174–181
4. Zhu J B, Chen W L. Improving text categorization using domain
knowledge In: Proceedings of International Conference on Applications of Natural Language to Information Systems, 2005, 103–113
5. Dayanik A, Lewis D D, Madigan D, Menkov V, Genkin A. Constructing informative prior distributions from domain knowledge in textclassification. In: Proceedings of ACM’S Special Interest Group on
Information Retrieval, 2006
6. Lu B L, Ito M. Task decomposition based on class relations: a modular
neural network architecture for pattern classification. Biological andArtificial Computation: From Neuroscience to Technology. Springer,
LNCS, 1997, 1240: 330–339
7. Lu B L, Ito M. Task decomposition and module combination based onclass relations: A modular neural network for pattern classification.
IEEE Transactions on Neural Networks, 1999, 10: 1244–1256
8. Anand R, Mehrotra K G, Mohan C K, Ranka S. An improved algorithm for neural network classification of imbalanced training sets.
IEEE Transaction on Neural Netwook, 1993, 4: 962–969
9. Lu B L, Wang K A, Utiyama M, Isahara H. A part-versus-part method
for massively parallel training of support vector machines. In: Pro-

1149–1153
18. Wen Y M, Lu B L, Zhao H. Equal clustering makes min-max modular
support vector machine more efficient. In: Proceedings of International Conference on Neural Information Processing, 2005, 77–82
19. Lian H C, Lu B L, Takikawa E, Hosoi S. Gender recognition using a
min-max modular support vector machine. In: Proceedings of International Conference on Natural Computation, 2005, 438–441
20. Yang Y M, Pedersen J O. A comparattive study on feature selectionin text categorization. In: Proceedings of International Conference on
Machine Learning, 1997, 187–196
21. Sebastiani F. Machine learning in automated text categorization. ACM
Computing Surveys, 2002, 34: 1–47
22. Zhao H, Lu B L. A modular k-nearest neighbor classification method
for massively parallel text categorization. In: Proceedings of FirstInternational Symposium on Computational and Information Science.
Springer, LNCS, 2004, 3314: 867–872
23. Wu K, Lu B L, Uchiyama M, Isahara H. An empirical comparisonof min-max-modular k-NN with different voting methods to largescale text categorization. Soft Computing − A Fusion of Foundations,
Methodologies and Applications, 2008, 12(7): 647–655
24. Joachims T. Making large-scale support vector machine learning practical. Advances in Kernel Methods: Support Vector Learning. Cambridge: MIT Press, 1998
25. Lewis D D, Yang Y, Rose T, Li F. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning
Research, 2004, 5: 361–397
26. Liu W, Xue G R, Yu Y, Zeng H J. Importance-based web page classification using cost-sensitive SVM. In: Proceedings of International
Conference on Web-Age Information Management, 2005, 127–137