Large-Scale Patent Classiﬁcation with Min-Max Modular Support
Vector Machines
Xiao-Lei Chu, Chao Ma, Jing Li, Bao-Liang Lu∗ Senior Member, IEEE, Masao Utiyama, and Hitoshi Isahara

Abstract— Patent classiﬁcation is a large-scale, hierarchical,
imbalanced, multi-label problem. The number of samples in areal-world patent classiﬁcation typically exceeds one million,
and this number increases every year. An effective patentclassiﬁer must be able to deal with this situation. This paper
discusses the use of min-max modular support vector machine (M3 -SVM) to deal with large-scale patent classiﬁcation
problems. The method includes three steps: decomposing alarge-scale and imbalanced patent classiﬁcation problem intoa group of relatively smaller and more balanced two-classsubproblems which are independent of each other, learningthese subproblems using support vector machines (SVMs) inparallel, and combining all of the trained SVMs according to
the minimization and the maximization rules. M3 -SVM has two
attractive features which are urgently needed to deal with largescale patent classiﬁcation problems. First, it can be realized in a
massively parallel form. Second, it can be built up incrementally.
Results from experiments using the NTCIR-5 patent data set,
which contains more than two million patents, have conﬁrmed
these two attractive features, and demonstrate that M3 -SVM
outperforms conventional SVMs in terms of both training timeand generalization performance.

I. I NTRODUCTIONCURRENT patent classiﬁcation mainly relies on humanexperts. The whole process is inefﬁcient and imprecise.
Automatic classiﬁcation systems based on machine learningtechniques can greatly reduce the workload, and humanexperts could provide a further breakdown, if needed, ofautomatic classiﬁcation. Moreover, patent classiﬁcation isa fundamental of patent analysis. Through the analysis ofcompetitors’ patents, valuable information pertaining to market strategy, product development direction, and so on canbe obtained. Related patents can also be mined for speciﬁc
information such as the identity of technical leaders and the
key technologies in a ﬁeld.
Because of its great importance, automatic patent classiﬁcation has received much attention [1], [2], [3], [4], [5],[6]. The European Patent Ofﬁce (EPO) tried a variety of
preprocessing methods on patent data, such as assigning
different weights to patent sections and, utilizing the cocitation between patents. They also redeﬁned the evaluation
standards for patent classiﬁcation, and pointed out that precision levels of the order of 80% are required for practicalusage [1]. Larkey [2] [3] designed a system for searching andXiao-Lei Chu, Chao Ma, Jing Li and Bao-Liang Lu are with the Department of Computer Science and Engineering, Shanghai Jiao Tong University,
800 Dong Chuan Rd., Shanghai, 200240 China. Masao Utiyama and Hitoshi
Isahara are with the Knowledge Creating Communication Research Center,
National Institute of Information and Communications Technology, 3-5
Hilaridai, Seika-cho, Soraku-gun, Kyoto, 619-0289 Japan. ∗ Corresponding
author (email: blu@cs.sjtu.edu.cn).

classifying U.S. patent documents based on query, and used
a K-nearest-neighbor algorithm in this system because of its
scalability to larger data sets. The Japan Patent Ofﬁce [4]developed a patent classiﬁcation system based on keywords,
and used about 310,000 patents in the training procedure.
They achieved 96% classiﬁcation accuracy in 38 categories
and 82.5% classiﬁcation accuracy in 2,815 subcategories.
Their experiments also indicated that in order to ensure
higher classiﬁcation accuracy, each subcategory should contain at least 1,000 training samples. Fall et. al. compared
the most commonly used classiﬁers, such as naive Bayes, kNN, support vector machines (SVM), neural networks, anddecision rules, and reported that SVM provides the best
performance [5], [6].
The above research mainly dealt with small data sets, but
real-world patent classiﬁcation problems may contain morethan a million samples. The time and space complexities
of SVM limit its application in such large-scale patentclassiﬁcation.
In this paper, we use min-max modular support vector
machines (M3 -SVM) [7], [8], [9], [10] to tackle large-scale
patent classiﬁcation problems. M3 -SVM includes three steps:
1) a large-scale pattern classiﬁcation problem is divided
into a number of smaller and more balanced subproblems
according to decomposition strategies; 2) all of the subproblems are solved by support vector machines in a massively
parallel way; 3) all of the trained support vector machines
are combined according to minimization and maximization
rules [11]. To speed up training and maintain the generalization performance of M3 -SVM for patent classiﬁcation, aprior-knowledge-based task decomposition strategy is used.
We also analyze the incremental learning ability of M3 -SVM.
Results from experiments using the NTCIR-5 database [12]demonstrate that M3 -SVM could surpass traditional SVM
in terms of both classiﬁcation accuracy and training time.
We have also found that if a newly introduced training data
set is incrementally learned, the training time can be greatly
shortened.
The rest of the paper is organized as follows. Section II
provides background knowledge regarding patents and theirclassiﬁcation. In Section III, the min-max modular networkmodel is brieﬂy introduced, and the incremental learning
ability of M3 -SVM is analyzed. In Section IV, the experiments using a large-scale patent data set are described andexperimental results are presented in detail. The conclusionand future work are presented in Section V.

3972
c
978-1-4244-1821-3/08/$25.002008
IEEE

$

*

$

$%

+ 

$+

$% 

+$+ 

6(& 7,2 1

+ 

+ %

& /$66

68% & /$66

+ %

+ % 

+ % 

* 5 2 83

Fig. 1. A sample of IPC taxonomy. Here ‘A’ is the SECTION category label, ‘A01’ is the CLASS category label, ‘A01B’ is the SUBCLASS categorylabel, and ’A01B 13/08’ is the GROUP category label.

II. PATENT C LASSIFICATION BACKGROUND
The International Patent Classiﬁcation (IPC) provides acommon classiﬁcation for patents and inventions, including
published patent applications, utility models and certiﬁcations. The IPC is a hierarchically structured system including
SECTION, CLASS, SUBCLASS, and GROUP layers as
illustrated in Fig. 1. The SECTION layer is the top layer,
and it has eight categories denoted by letters from A to
H. The CLASS layer is under the SECTION layer andhas 120 categories. The CLASS layer is expressed as a
SECTION label followed by two digits; for example, ‘A01’.
The third layer is the SUBCLASS layer, which is represented
as a CLASS label followed by a capital letter; for example,‘A01B’. The number of categories in the SUBCLASS layer is630. SUBCLASS can be further divided into GROUP, but ingeneral current research has mainly concentrated on the top
three layers since the deﬁnitions of layers below SUBCLASS
are still frequently changed.
Patent documents are generally stored in XML format asshown in Fig. 2. A patent is composed of three main sections: Abstract, Claim, and Description, and other descriptive
information such as Title and IPC.

Fig. 2. A sample Japanese patent document selected from NTCIR-5. Here,this patent has two IPC labels, and the main IPC label is represented in Fig.
1.

(i)III. M IN -M AX M ODULAR S UPPORT V ECTOR M ACHINE
Before using M3 -SVM, we should divide a K-class problem into K(K − 1)/2 two-class subproblems according
to a one-against-one strategy. The work procedure of M3 SVM consists of three steps: task decomposition, SVM
training, and module combination. Figure 3 shows this idea
of ﬁne decomposition and module combination for a twoclass problem. Mini,∗ expresses the MIN unit for the ith
subset of the positive class.
A. Task Decomposition
Let Tij be the given training data set for a two-classclassiﬁcation problem,
(i)

(j)

L

j
i
Tij = {(Xl , +1)}L
l=1 ∪ {(Xl , −1)}l=1

for i = 1, · · · , K and j = i + 1, · · · , K

(1)

(j)

where Xl ∈ Xi and Xl ∈ Xj are the training inputs
belonging to class Ci and class Cj , respectively; Xi is theset of training inputs belonging to class C
i ; Li denotes theKnumber of data in Xi ; ∪K
i=1 Xi = X ; andi=1 Li = L. In
this paper, the training data in a two-class subproblem arecalled positive training data if their desired outputs are +1.
Otherwise, they are called negative training data.
Although the two-class subproblems deﬁned by Eq. (1) aresmaller than the original K-class problem, this partition may
not be adequate for parallel learning. To speed up training,
all the large and imbalanced two-class subproblems should
be further divided into smaller and more balanced two-classsubproblems.
Assume that Xi is partitioned into Ni subsets in the form(j)(ij) Li}l=1

Xij = {Xl(2)

for j = 1, · · · , Ni and i = 1, · · · , K,

2008 International Joint Conference on Neural Networks (IJCNN 2008)3973

B. Module Combination

Min1,*

M 1,1

M 1, 2After training, all the individual SVMs are integrated intoa M3 -SVM with MIN and MAX units according to two
combination principles: the minimization principle and the
maximization principle [11].
Minimization Principle: Suppose a two-class problem
B is divided into P smaller two-class subproblems, Bi for
i = 1, · · · , 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 subproblems arecorrectly learned by the corresponding P individual SVMs,
Mi for i = 1, · · · , 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 ﬁnd a minimum value from its multiple inputs. The
transfer function of the MIN unit is given byMIN

M 1, N2

X

MAX
N1 ,*

N1 ,1

Min

M N1 , 2

MIN

M

M N1 ,N2

P

Fig. 3. Fine Decomposition and Module Composition of a Two-Class
Problem. Here the two-class problem is further decomposed into N1 × N2
subproblems. Therefore, the M3 network consists of N1 × N2 individual
network modules, N1 MIN units, and one MAX unit.

iwhere 1 ≤ Ni ≤ Li and ∪N
j=1 Xij = Xi .
After partitioning Xi into Ni subsets, every two-classsubproblem Tij deﬁned 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(3)

for u = 1, · · · , Ni , v = 1, · · · , Nj ,i = 1, · · · , K, and j = i + 1, · · · , K(jv)∈ Xiu and Xl∈ Xjv are the training
where
inputs belonging to class Ci and class Cj , respectively;
Nj
Ni
(u)
(v)
= Li ; and v=1
Lj = Lj .
u=1 LiAfter task decomposition, each of the two-class subproblems can be treated as a completely independent, noncommunicating problem in the learning phase. Therefore,
all the two-class subproblems deﬁned by Eq. (3) can be
efﬁciently 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)
i=1 j=i+1

two-class subproblems. The number of training data for eachof the two-class subproblems is about(6)

where x denotes the input variable.
Maximization Principle: Suppose a two-class problem
B is divided into P smaller two-class subproblems, Bi for
i = 1, · · · , P , and also suppose that all the two-class subproblems have the same negative training data and different
positive training data. If the P two-class subproblems arecorrectly learned by the corresponding P individual SVMs,
Mi for i = 1, · · · , 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 ﬁnd a maximum value from its multiple inputs.
The transfer function of the MAX unit is given by
q(x) = max Mi (x)
i=1

(7)

C. Incremental Learning
Patent classiﬁcation is a typical incremental learning problem, because new patents are issued continuously. Incremental learning could be used to learn the novel knowledge fromin-coming patents, and models which have been trained canbe reused. M3 -SVM has such incremental learning ability
if a decomposition strategy, such as prior-knowledge-based
decomposition, can be used to divide each new data set independently of the learned datasets whereas random decomposition can-not be accommodated within the incremental
learning architecture. Figure 4 shows M3 -SVM models after
addition of a new data set. Previously trained models arereused in M3 -SVM.
First, the number of training models in the original data
set can be easily calculated using(5)

Since Li /Ni  + Lj /Nj  is independent of the number ofclasses K, the size of each of the two-class subproblems
is much smaller than the original K-class problem forreasonable values of Ni and Nj .

3974

i=1

P

(iu)
Xl

Li /Ni  + Lj /Nj q(x) = min Mi (x)M (1) =


0<i<j≤K(

LiLj ×  )
ai
aj

(8)

where Li is the sample number in the ith category, andai is the sample number in each subset of the ith category.

2008 International Joint Conference on Neural Networks (IJCNN 2008)

i ,*Minnew

M i ,1'i ,*Minnew'

M i ,1

M i ,N2,*
Min1new'

M i ,N2XMIN

M i , N2 +1

N1 ,*Minnew

X

MIN

M

X

MAX

i ' , N2 +1

N1 +1,*
Minnew'

M i , N2 + N2

M i , N2 + N2

(a)

(b)

'

'

N1 + N1 ,*Minnew'(c)Fig. 4. Modiﬁcation of modules in the case where new training data is added to existing classes. Here N1 and N2 are the module number of newly introduced




i ,∗
positive and negative data sets, respectively. (a) modiﬁed old ith MIN units(Mini,∗new ),i = 1, 2, . . . , N1 . (b) newly created i th MIN units(Minnew ),
i = N1 + 1, . . . , N1 + N1 (c) Fig. 3 after incremental learning.

K denotes the category number. After the introduction of a
new data set, the number of models increases to M (2) :
M

(2)

=





0<i<j≤K



Lj
Li
L
Lj
((  +  i ) × (  +   )) (9)
ai
aj
ai
aj



where Li is the sample number in the ith category in the
newly introduced data set, and ai is the sample number ineach subset of the ith category in the newly introduced data
set. Assuming the newly introduced data set is equal in sizesto the original data set, we let all ai and ai be equal to aand all Li and Li be equal to L. Equations (8) and (9) thenbecomeK(K − 1) L 2
 (10)
M (1) =2a4K(K − 1) L 2
 
(11)
2
a
The number of models which should be incrementallylearned is3K(K − 1) L 2(12)M (2) − M (1) = 
2aAfter we introduce another data set (equal in size to the ﬁrst
data set),
9K(K − 1) L 2
 (13)
M (3) =
2a
The number of models which should be incrementallylearned becomes
5K(K − 1) L 2
 (14)
M (3) − M (2) =2aThus, we can infer that after the introduction of the ith newdata set (equal in size to the ﬁrst data set),
M (2) =

M (i) = i2 W

(15)

K(K−1) L 2
a
2

is a constant. The number ofwhere W =models which should be incrementally learned is
M (i) − M (i−1) = i2 W − (i − 1)2 W = (2i − 1)W(16)

Equations (15) and (16) show that when incremental learning
is used, the number of models which should be incrementallylearned decreases from O(i2 ) to O(i)This theoretical analysis has been veriﬁed by our experimental results, which are given in Section IV.
IV. PATENT C LASSIFICATION E XPERIMENTS
A. Data Set
The data set used in our experiment was collected fromthe NTCIR-5 patent data set [12] which follows the IPC
taxonomy. There are about 350,000 new patents in per year,
and new patents from a 7-year period were used in our
experiment. The total number of patents is 2,399,884. We
use the patents from the ﬁrst ﬁve years’ as training data, andthose from the ﬁnal two years’ as test data. The number ofpatents in each year and in each class are listed in Table I.
We used the hierarchical text classiﬁcation model to solve
the patent classiﬁcation problem, and focused on using M3 SVMs to solve the large-scale problem in the SECTION
layer. The SECTION layer has eight categories from A to
H, and the distribution of patents in eight categories is listed
in Table I. Note that a patent has one main category label
and may also have several compensatory labels. Here, we
simplify the multi-label problem into a unique label problem
by only considering the main label of the patent.
B. Feature Selection Method
First, the raw Japanese patent was segmented usingchasen [13], a Japanese morphological analyzer, and all
auxiliary words and punctuation were removed. A patentconsists mainly of three sections - Abstract, Claim, and
Description. In our experiment, the three sections were
weighted equally and wholly indexed into a single vector
using the TFIDF method. Other researchers have proved thatχavg , χmax and Information Gain [14] are the top feature
selection methods for text classiﬁcation. We compared thesethree methods in our experiment. The results showed that thethree methods are approximately equal in performance. We

2008 International Joint Conference on Neural Networks (IJCNN 2008)

3975

TABLE I
N UMBER OF PATENTS PER YEAR IN EIGHT SECTIONSSECTION
A
B
C
D
E
F
G
H
TOTAL

1993
30,58365,53830,747
4,904
18,60530,296
77,692
72,589330,954

1994
31,316
68,474
31,834
5,228
18,00031,18881,691
72,164
339,895

1995
28,357
68,13034,163
5,794
16,11429,35881,67772,544
336,137

1996
25,444
68,27837,996
6,127
13,69028,25888,716
81,486
349,995

also tuned the dimension parameter from 2,500 to 160,000,
and found that 5,000 was the smallest value that enabledclose to the top performance. Thus, we used the χavg method
and a dimension size of 5000 in the experiments discussed
in this paper.
C. Classiﬁer
The M3 framework can use support vector machine, K
nearest neighbor, or neural network classiﬁers as the baseclassiﬁer. In the experiments of other researchers, the support
vector machine has proved to be the optimal classiﬁer for
most text classiﬁcation problems, so we used SVMlight [15],[16] in our experiment as the baseline algorithm and baseclassiﬁer of M3 . SVMlight is designed to solve large-scale
text classiﬁcation problems. It optimizes the speed of boththe training and the testing, while also ensuring classiﬁcation
accuracy. Because of the outstanding capability of SVMlight ,we considered it the most appropriate classiﬁer for our
experiment. We also used the linear kernel for SVM, because
the linear kernel enables the shortest training and test times.
We attempted to use other types of kernel, but the training
seemed endless in the same experimental environment.
D. Decomposition Strategies
Effective task decomposition is vital for M3 -SVMs toachieve satisfactory performance [7]. We use three decomposition strategies in our experiments.
1) Random task decomposition is quite straightforward.
After the subset sizes are decided, patents are randomly
selected to form subsets. In our experiment, we set thesubset size to 2000 based on our experience.
2) Year&Random task decomposition ﬁrst divides patents
into subsets according to year, and then each year’s
patents are further divided into subsets using theRandom Algorithm according to the predeﬁned subset
size(2000 in our experiments).
3) Year&CLASS task decomposition ﬁrst divides patents
into subsets according to year, and then each year’s
patents are further divided into subsets according totaxonomy. The CLASS layer is used in our experiments. The CLASS number in each SECTION isshown in Table II.

3976

1997
22,47562,43635,7005,604
11,09926,671
95,67986,834346,498

1998
32,427
68,14831,198
4,642
18,604
31,40379,15875,305
340,885

1999
33,126
69,64831,494
4,968
18,81032,93883,94280,594355,520

TOTAL
203,728
470,652
233,132
37,267
114,922
210,112588,555
541,516
2,399,884

TABLE II
CLASS NUMBER IN EACH IPC SECTIONSECTION
CLASS number

A
15

B
36

C
19

D
8

E
7

F
17

G
13

H
5

Among the three decomposition strategies, Year&CLASS
decomposition provided the best performance, as shownin Fig. 5. In the following discussion, we therefore only
consider M3 -SVM based on Year&CLASS decomposition.
E. Baseline Comparison
As noted, SVMlight performed well for most of the textclassiﬁcation problems, including our patent data set, in
terms of both speed and classiﬁcation accuracy. We compared M3 -SVM based on Year&CLASS decomposition with
SVMlight , and found that our method could surpass even
SVMlight in the following four regards:
1) Classiﬁcation Accuracy: We use the 1998-1999 patents
as a test set, and the 1997, 1996-1997, 1995-1997, 19941997, and 1993-1997 sets in turn as the training set . Figure 5
shows the classiﬁcation results with M3 -SVM and SVMlight .
As the training data number increased, the performance of
M3 -SVM surpassed that of SVMlight . In addition, the performance of SVMlight dropped sharply with the introduction of
distant years’ patents, which would complicate the decisionboundary. M3 -SVM can simplify the decision boundary by
dividing the original complex problem into a group of much
simpler subproblems.
2) Parameters Independence: The support vector machine
algorithm can achieve advanced performance only when the
training parameters are properly set. For large-scale classiﬁcation problems, it could require several days or more toﬁnish one round of training, so parameter tuning is unrealistic
for this kind of problem. Although we can select part of the
training data to use for parameter tuning, whether this subset
will accurately represent the whole data set is not guaranteed. In our experiment using the SVMlight classiﬁer, theperformance of SVMlight changed dramatically along withthe parameter tuning. In contrast, M3 -SVM could provide
satisfactory performance regardless of parameter changes.

2008 International Joint Conference on Neural Networks (IJCNN 2008)

0.825

0.815

0.81

0.82

0.805

Macro recall

Macro precision

0.815

0.81

0.805

0.8

0.795

0.79
0.8
0.785

Random M3

3

Random M
3
Year&Random M
3
Year&CLASS M
SVM

3

Year&Random M

0.795

0.78

3

Year&CLASS M
SVM
0.79

1

2

3

4

0.775

5

1

2

3

Year

Year

(a)

(b)

0.82

4

5

0.83

0.825

0.815

0.82
0.81

Micro F1

Macro F1

0.815
0.805

0.8

0.81

0.805
0.795
0.8

3

Random M
3
Year&Random M
3
Year&CLASS M
SVM

0.79

0.785

1

2

Fig. 5.

3

4

3

Random M
3
Year&Random M
3
Year&CLASS M
SVM

0.795

5

0.79

1

2

3

Year

Year

(c)

(d)

4

5

Performance of different classiﬁers, (a) Macro precision, (b) Macro recall, (c) Macro F1, (d) Micro F1.

This is shown in Fig. 6, and calculated mean and standard
deviation values are shown in Table III. In general, M3 -SVM
provided the best performance without parameter selection,and this capability is important for large-scale problems.
3) Time Cost: We also compared the training and test
times between M3 -SVM and SVMlight . SVMlight provides
greatly improved training and test times compared withthose of traditional SVM classiﬁers. Our experiments weredone on a Lenovo cluster composed of three fat nodes andthirty thin nodes. Each fat node had 32G RAM and two
3.2GHz Intel(R) Xeon(TM) CPUs, while each thin node had
8G RAM and two 2.0GHz Intel(R) Xeon(TM) CPUs witheach CPU having four cores. The SVMlight experiments
were done on the fat nodes, and the M3 -SVM experiments
were done on the thin nodes. The results are shown in Fig.
7. We found that although running on slower CPUs, M3 -SVM can greatly reduce the training time. However, M3 SVM needed more testing time than SVMlight . For a ﬁxed
subproblem size, the M3 -SVM model number will grow withthe training set size, so the test time will also increase.
In the SVMlight test process with a linear kernel, though,only the distance between the test vectors and the dividing
hyperplane needs to be calculated, which is independent of
the training set size. Although the test time was greater, M3 SVM needed only 2ms to test a patent, and can be used inreal-time. Moreover, we used just 240 CPU cores to do thecomputation in parallel in the M3 -SVM experiment, but all
the training of subproblems could be done in parallel. Using
the Year&CLASS decomposition method, the original ﬁve
years’ of patents were divided into almost 150,000 subsets
according to CLASS as shown in Table II. With enoughcomputation nodes, the M3 -SVM training and test times

2008 International Joint Conference on Neural Networks (IJCNN 2008)

3977

0.82

0.83

0.81

0.82

0.80
0.81
0.79
0.80

Micro F1

Macro F1

0.78

0.77

0.79

0.76

0.78

0.75

0.77

0.74

0.76

3

0.72

3

Year&CLASS M
SVM

0.73

0

5

10

Year&CLASS M
SVM

0.75
15

0

5

10

Log(C)

Log(C)(a)(b)

Fig. 6.

15

Performance under different training parameters: (a) Macro F1, (b) Micro F1.

4

2.5

x 10

1400

Year&CLASS M
SVM

3

Year&CLASS M
SVM

3

1200
2

Test time (s)Train time (s)

1000

1.5

1

800

600

400
0.5
200

0

1

2

3

Fig. 7.

4

5

Macro F1
Micro F1

3978

2

3

(a)

(b)

4

5

Training and test times for M3 -SVM and SVMlight . (a) Training time, (b) Test time

M EAN AND STANDARD DEVIATION VALUES FOR M 3 -SVM AND
SVMlight

Macro recall

1

Year

TABLE III

Macro precision

0

Year

classiﬁer
M3 -SVMs
SVMlight
M3 − SV M s
SVMlight
M3 -SVMs
SVMlight
M3 -SVMs
SVMlight

mean
0.81370.79170.80680.77470.80970.78180.81780.7906SD
0.00350.01800.00390.03200.00400.02680.00730.0219

could be greatly reduced to 240/150, 000 ≈ 1/625, much
shorter than those of SVMlight . The scalability of M3 -SVMs
is illustrated in Fig. 8.
4) Incremental Learning: We also tested the M3 -SVM incremental learning ability by successively adding one year’s
patents to the training set. The results are shown in Fig. 9. As
we expected, the training time of incremental learning grewlinearly, while the training time of no incremental learning
grew quadratically.
V. C ONCLUSION
We have used M3 -SVM to address a large-scale patentclassiﬁcation problem on the IPC top layer. M3 -SVM provides better generation performance than conventional SVM,

2008 International Joint Conference on Neural Networks (IJCNN 2008)

VI. ACKNOWLEDGEMENTS

2500

3

We sincerely thank Zhifei Ye and Feng Zhou for theirhelpful advices, and Cong Hui for his coding help.
This work was supported in part by the National Natural
Science Foundation of China via the grant NSFC 60773090,
the Microsoft Laboratory for Intelligent Computing andIntelligent Systems of Shanghai Jiao Tong University, andthe Okawa Foundation Research Grant.

M test time3
M training time
2000

Time (s)1500

R EFERENCES

1000

500

0

16

32

64

128

230

CPU cores

Fig. 8. Training and test times are inversely proportional to the number ofCPU cores.

5500

5000

4500

4000

Time (s)

3500

3000

2500

2000

1500

No incremental learning
Incremental learning

1000

500

1

2

3

4

5

Year

Fig. 9.

Incremental learning ability of M3 -SVMs.

and more stable performance than conventional SVM withregard to parameter tuning. The training time of M3 -SVM
can be greatly reduced. Experimental results showing thattraining and test times are inversely proportion to the numberof CPU cores demonstrate the scalability of the parallel
M3 -SVM system. We also veriﬁed the incremental learning
ability of M3 -SVM, which is a valuable property for largescale patent Consequently, the training time is reduced from
quadratic complexity to linear complexity. In the future,
the multi-label and hierarchical structure of patents will beconsidered with the goal of solving the patent classiﬁcation
problem integrally.

[1] M. Krier and F. Zaccà, “Automatic categorisation applications at theEuropean patent ofﬁce,” World Patent Information Elsevier, vol. 24, pp.
187-196, 2002.
[2] L. Larkey, “Some Issues in the Automatic Classiﬁcation of US Patents,”
In Learning for Text Categorization. Papers from the 1998 Workshop.
AAAI Press, Technical Report WS-98-05, pp. 87-90, 1998.
[3] L. S. Larkey, “A patent search and classiﬁcation system,” Proceedingsof the fourth ACM conference on Digital libraries, pp. 179-187, 1999.
[4] H. Mase, H. Tsuji, H. Kinukawa, M. Ishihara, “ Automatic Patents
Categorization and Its Evaluation,” Information Processing Society ofJapan Journal, vol. 39, 1998.
[5] C. J. Fall and K. Benzined, “Literature survey: Issues to be consideredin the automatic classiﬁcation of patents,” World Intellectual Property
Organization, vol. 29, 2002.
[6] C. J. Fall, A. Törcsvári, K. Benzineb and G. Karetka, “Automatedcategorization in the international patent classiﬁcation,” ACM SIGIR
Forum ACM Press New York, NY, USA, vol. 37, pp. 10-25, 2003.
[7] B. L. Lu, K. A. Wang, M. Utiyama, and H. Isahara, “A part-versuspart method for massively parallel training of support vector machines,”
Proceedings of IEEE/INNS Int. Joint Conf. on Neural Networks (IJCNN2004), pp. 735-740, 2004.
[8] B. L. Lu, J. H. Shin, M. Ichikawa, “Massively parallel classiﬁcationof single-trial EEG signals using a min-max modular neural network,”
IEEE Transactions on biomedical engineering, pp. 551-558, 2004.
[9] Y. Yang, B. L. Lu, “Prediction of protein subcellular multi-locations
with a min-max modular support vector machine,” Proceedings of theThird International Symposium on Neural Networks, pp. 667-673, 2006.
[10] H. C. Lian and B. L. Lu, “Gender Recognition Using a Min-Max
Modular Support Vector Machine,” Proceedings of ICNC’05-FSKD’05,
LNCS 3611, Changshai, China, pp. 433-436, 2005.
[11] B. L. Lu and M. Ito, “Task decomposition and module combination
based on class relations: a modular neural network for pattern classiﬁcation,” IEEE Transactions on Neural Networks, vol. 10, pp. 1244–1256,
1999.
[12] M. Iwayama and A. Fujii and N. Kando, “Overview of Classiﬁcation
Subtask at NTCIR-5 Patent Retrieval Task,” Proceedings of NTCIR-5
Workshop Meeting, 2005.
[13] Y. Matsumoto, A. Kitauchi, T. Yamashita, Y. Hirano, O. Imaichi and
T. Imamura, “Japanese morphological analysis system ChaSen manual,”
Nara Institute of Science and Technology Technical Report NAIST-ISTR, vol. 97007, pp. 232–237, 1997.
[14] Y. Yang and J. O. Pedersen, “A comparative study on feature selectionin text categorization,” Proceedings of ICML-97, 14th International
Conference on Machine Learning, pp. 412-420, 1997.
[15] T. Joachims, “Making large-Scale SVM Learning Practical,” In B.
Scoelkopf, C. Burges, A. Smola, editor, Advances in Kernel MethodsSupport Vector Learning. MIT Press, 1999.
[16] T. Joachims, “SVMLight: Support Vector Machine,” Software available from http://svmlight. joachims. org, 1999.

2008 International Joint Conference on Neural Networks (IJCNN 2008)3979