D

China-USA Business Review, ISSN 1537-1514
September 2013, Vol. 12, No. 9, 911-917

DAVID

PUBLISHING

Multi-valued Document Classification Based on Generalized
Bradley-Terry Classifiers Utilizing Accuracy Information*
Tairiku Ogihara, Kenta Mikawa, Masayuki Goto
Waseda University, Tokyo, Japan

Gou Hosoya
Tokyo University of Science, Tokyo, Japan

Due to the development of computer network, a large amount of documents are treated in many fields. The numberof digital document data stored in databases is enormous, accordingly it is difficult for analysts to read all
documents and classify it by hand. Therefore, it is necessary to develop the technology of automatic documentclassification by using computers these days. From the above needs, many classifiers with good performance havebeen proposed, i.e., Relevance Vector Machine (RVM) and Support Vector Machine (SVM) that are known as
good binary classifiers. For multi-valued document classification problems, it is known that a multi-valued
classifier by combining several binary classifiers has a good performance. In this study, the method to construct anefficient combination of binary classifiers based on improving Generalized Bradley-Terry (GBT) model, which has
high extensibility, is focused. This model is an expansion of Bradley-Terry (BT) model. Though the BT model has
a limitation on combination of classes, the GBT model enables us to utilize any binary classifier which classifies
into two arbitrary subsets in the class set. Generally, when several binary classifiers learn from the training dataset,there would be the difference of accuracy between these binary classifiers, due to the existence of categories thatcannot be easily classified. However, the conventional method of multi-valued classification by GBT binaryclassifiers does not take the accuracy of each classifier into consideration. To avoid this problem, a new way ofmulti-valued classification method by considering each classifier’s accuracy is proposed. The purpose of this study
is to construct a good multi-valued classifier by calculating the accuracy of each classifier and utilizing it as theweight. In order to verify the effectiveness of the proposed method, the simulation experiment by using newspaper
articles is conducted.
Keywords: Generalized Bradley-Terry (GBT) model, multi-valued classification, Relevance Vector Machine(RVM), document classification, the accuracy of each classifier, combination of binary classifiers*

KAKENHI, Grant-in-Aid for Scientific Research (C), No. 23510192.
Tairiku Ogihara, B.E. degree, Department of Industrial and Management Science, Faculty of Science and Engineering, Waseda
University.
Kenta Mikawa, M.E. degree, Department of Industrial and Management Science, Faculty of Science and Engineering, Waseda
University.
Masayuki Goto, Dr.E. degree, Department of Industrial and Management Science, Faculty of Science and Engineering, Waseda
University.
Gou Hosoya, Dr.E. degree, Department of Management Science, Faculty of Engineering, Tokyo University of Science.
Correspondence concerning this article should be addressed to Tairiku Ogihara, 3-4-1 Okubo Shinjuku-ku Tokyo 169-8555,
Japan. E-mail: i.w.g.p-land@akane.waseda.jp.

912

MULTI-VALUED DOCUMENT CLASSIFICATION

Introduction
Due to the development of computer networks, a large amount of digital documents have become to beable to be treated in every field. The number of document data stored in databases is enormous, accordingly, it
is difficult for analysts to read all documents and classify it by hand. Therefore, the necessity of automatic
document classification by using computers has risen these days. From the above needs, many methods byapplying binary classifiers with good performance have been proposed. For example, Relevance Vector
Machine (RVM) and Support Vector Machine (SVM) are known as good binary classifiers and these methods
can be applied to the binary document classification problems (Tipping, 2001; Cortes & Vapnik, 1995).
However, it is sometimes difficult to acquire a unique multi-valued classifier with both high performance andpractical computational complexity. Thus, the formulation of the multi-valued classification problem by a
combination of several binary classifiers has been proposed. The most basic idea is the one versus the rest
method which prepares the binary classifiers to classify each category and others. Though the one versus therest method is a very simple way, it is known that a combination of appropriate number of binary classifiers ismore efficient than the one versus the rest method and a unique multi-valued classifier. Therefore, several
works using binary classifiers for multi-valued classification problems have been studied (Rumelhart &McClelland, 1986; Quinlan, 1993). One of these methods by combining binary classifiers is theError-Collecting Output Codes (ECOC) (Dietterich & Bakiri, 1995; Hastie & Tibshirani, 1998; Allwein,
Schapire, & Singer, 2000). Another effective idea is to apply the Bradley-Terry (BT) model (Ikeda, 2010;
Huang, Weng, & Lin, 2006). The BT model is a statistical model and has broad applications in many fields.
The application of the BT model to the multi-valued classification is an attractive way and has a possibility todevelop this research field.
In this study, the method to construct an efficient combination of binary classifiers based on Generalized
Bradley-Terry (GBT) model (Huang et al., 2006) with high extensibility is focused. This model is an expansion of
BT model (Bradley & Terry, 1952). Though the original BT model has a limitation on combination of classes, theGBT model enables us to utilize arbitrary binary classifier which divides into an arbitrary size of two subsets inthe class set. Generally, when several binary classifiers are combined to implement multi-valued classification,
there exists the difference of accuracy between binary classifiers, due to the existence of categories that cannot beeasily classified. However, the conventional method of multi-valued classification by GBT binary classifiers does
not take the accuracy of each classifier into consideration. Therefore, classifiers with bad performance can makethe gross accuracy decrease. In short, a direct use of those bad classifiers leads to degrade the classification
performance. To avoid this problem, a new way of multi-valued classification method by considering eachclassifier’s accuracy is proposed. The purpose of this study is to develop the effective method by estimating theaccuracy of each classifier and utilizing it as the weight of classifier. The proposed method gives the large weights
to good classifiers with high accuracy and gives the small weights to bad performance classifiers. The
improvement of performance by applying these weights in classification rule is expected. To verify theeffectiveness of the proposed method, the simulation experiment by using newspaper articles is conducted.

Preliminaries
Multi-valued Classification Problems
Let the number of categories be K, and the set of categories be C = {c1, …, cK}. x is an input vector which

913

MULTI-VALUED DOCUMENT CLASSIFICATION

has an unknown category. A classifier is adaptively modeled by a learning rule with the training data set. Whena new test data is provided, its class is predicted by the trained classifier. The classification problem is defined
as a prediction of the category c  C to which a new input x belongs. The classification problem is referred toas multi-valued classification problems in the case of K  3 , and is also referred to as binary classification
problems in the case of K = 2.
Classifications by Using RVM
In this study, the RVM classifier is applied by performing soft decision to estimate the posterior
probability of each category. The binary RVM classifier has a lot of same characteristics as the SVM which is agood binary classifier with high accuracy. The RVM was proposed by Tipping (2001), which is a sparselearning algorithm applied to regression and classification problems. Silva and Ribeiro (2006) talked about theapplication to the text classification problem. The RVM is similar to the SVM (Cortes & Vapnik, 1995) inmany respects but is capable of expressing a fully probabilistic model.
First, a binary classification model (K = 2) by the RVM is explained. Let x be an input vector andNc {c1 , c2 } be a category label. A set of N training document samples is denoted by {xn , tn }n 1 ,tn  {c1 , c2 } . The probability of category label c takes ck (k = 1, 2) conditioned on x is expressed by using
logistic regression as follows:p (c  ck | x) f RVM ( x) 1
1  exp( f RVM ( x))(1)N w K ( x, x )i 1,ti  ck

i

(2)

i

where wi ~ N (0,  i1 ) and  i1 are obtained by maximizing a posterior probability of , which is hyper
parameter that controls the distribution of parameters. Moreover K(...) denotes a kernel function whichcalculates inner product of two input data points mapped on a higher dimensional space, and wi expresses aweight parameter. By maximizing a posterior probability, almost all i1 becomes zero. xi having non-zero wi
value the Relevance Vector (RV) is called. The decision function fRVM (x) is determined by these RVs. The
RVM has several desirable properties and good performance in classification accuracy. On the other hand, theRVM needs to spend more times in learning phase compared to the SVM. If the RVM is performed for a modelwith M basis functions, the computational complexity of evaluating inverse matrix of size M takes O(M3)(Bishop, 2006).
For a multi-valued classification problem ( K  3 ), a probabilistic method of combining G linear models
is used. The parameter i1 is calculated in the same way as a case of two categories. It is a quite
straightforward extension to the multi-valued classification problem, but there exists a disadvantage that thecomputational complexity for learning is K3 times larger than that of the binary RVM (Bishop, 2006). Assumethat the classifier r (r = 1, …, R) classifies input vectors x into the two category sets, Cr and Cr . Here,
















assume that Cr , Cr  C , Cr , Cr  0 , Cr Cr  0 , and Cr  Cr  Cr . The binary classifier is reduced to914

MULTI-VALUED DOCUMENT CLASSIFICATION








the 1-vs-1 classifier when | Cr || Cr | 1 . If | Cr | 1 and | Cr | K  1 , then the binary classifier isreferred as to the 1-vs-the-rest-classifier. Let the performance of classifier r be qr (x) (0  qr (x) 1) , then qr (x)and1 qr (x) can be seen as the estimations of p(c  Cr | c  Cr , x) and p (c  Cr | c  Cr , x) ,respectively.

Conventional Study
Basic Explanation of BT Model
The BT model has been widely applied in many areas, especially in sports statistics (Ikeda, 2010). The BTmodel is a model to quantify the strength of each player when many people play a lot of one-to-one match.
Assume that there are K players and a player k (k = 1, …, K) has non-negative parameter pk called strength.
Probability that player k wins against player l (l = 1, …, K, l  k) by pk/(pk + pl) is denoted, and probability
that player l wins against player k by pl/(pk + pl) is denoted. Let nkl be the number of matches between players k
and l. Let rkl be a winning rate of player k against player l, and it is given by:rkl 

the number of mathches that player k wins against player l
nkl

(3)

We assume there is no tie so the equation rkl + rlk = 1 holds. Let F(p) be a log-likelihood function, and it isdefined as follows:
K
K

pk
pl 
 (1  rkl ) ln
F ( p )     rkl ln


p
p
p
k 1 l  k 1 klk  pl (4)where p  ( p1 , ..., pK ) denotes a strength vector. By maximizing F(p) in equation (4) with respect to p  1, p  0, the maximum likelihood estimator pˆ  ( pˆ , ..., pˆ ) is acquired. The players according to
K

k 1

k

k

1

K

their strength from p̂ are ranked.
Multi-valued Classifier by BT Model
Consider applying the BT model to multi-valued classification by combining binary classifiers. The
log-likelihood function of BT model, FBT ( p, x) , is defined as follows:
R 

pkr
plr
FBT ( p, x )    qr ( x) ln
 (1  qr ( x)) ln
pkr  plrpkr  plr r 1 

(5)

where qr ( x) denotes the output of the 1-vs-1 classifier, kr and lr denote the numbers of category in Cr andCr , respectively. Similar to the previous subsection, the maximum likelihood estimatorpˆ  ( pˆ1 ,..., pˆ K ) ,  k 1 pˆ k  1, pˆ k  0, is obtained by maximizing FBT ( p, x) in equation (5) with respectK

to p . Then it can be treated p̂k as p (ck | x) . Since p̂k represents an estimation of category ck , theclassification rule of x from cˆ  arg max c k C pˆ k is formulated.

915

MULTI-VALUED DOCUMENT CLASSIFICATION
Multi-valued Classification by GBT Model

It is difficult to attain high performance by multi-valued classifier using the BT model, since the numberof learning data of 1-vs-1 classifier in this model is lower than that of 1-vs-the-rest-classifier. As a result,classification accuracy of 1-vs-1 classifier is not so good. However, the GBT model can use any combination of
1-vs-1 classifiers and 1-vs-the-rest-classifier (Huang et al., 2006). The Log-likelihood function of GBT model,

FGBT ( p, x) , is defined as follows:R  ck Cr pk  (1  q ( x)) ln  ck Cr pk 
FGBT ( p, x)    qr ( x) lnrr 1 
 cl Cr pl cl Cr pl (6)Similar to the case of multi-valued classifier by BT model in the previous subsection, the maximumK
likelihood estimator pˆ  ( pˆ1 , ..., pˆ K ) ,  k 1 pˆ k  1, pˆ k  0, is obtained by maximizing FGBT ( p, x) inequation (6) with respect to p. Then the classification rule of x from cˆ  arg max c k C pˆ k is formulated.

Proposed Method
In the conventional multi-valued classification based on the GBT model, this model assumes the same
weight for all binary classifiers. Therefore, there is a possibility that a bad classifier affects the total decision by
all classifiers. The proposed method takes the estimated accuracy of classifier in consideration. It is necessary
to determine the weights of the classifiers. By applying these weights to the GBT model, the modified GBT(MGBT) model which is a new way of multi-valued classification method by considering each classifier’s
accuracy is proposed.
Method for Calculating the Weight of Each Classifier
Usually, the reliability of each classifier can be different because it classifies different categories and islearned individually. Therefore, in order to verify the reliability of each classifier, qr ( x) 1 is regarded asconfidence of classifier r. Classifier accuracy can be estimated from the output of training data. The accuracy ofclassifier r is derived as follows:

Ar 

where

 q ( x ')x ' 'c ( x ')Cr(7)r

 ' denotes a training data set, and c( x' ) denotes the category of a training data x' ( x'   ' ). If thetotal confidence Ar is large, the classifier r is easy to classify. On the other hand if Ar is small, the classifier r isdifficult to classify the training data. As a result, the weight of each classifier which corresponds to its accuracyRis calculated. In order to normalize the confidence Ar based on its maximum value max r '1 Ar , the weight ofthe classifier r,  r is calculated as follows:

r 

1

Ar
max rR'1 Ar 'In this research, qr ( x) is treated as output of classifier, the performance of classifier, or confidence of classifier.

(8)

916

MULTI-VALUED DOCUMENT CLASSIFICATIONClassification Considering the Variation in Accuracies of Classifiers on GBT Model
By applying the weights accuracy of GBT classifiers, a new classification rule considering the variation in
accuracies of classifiers is proposed on GBT model. Like equation (6), the log-likelihood function FMGBT ( p, x)
can be formulated as a follows:Rck Cr pk  (1  q ( x)) ln ck Cr pk 
FMGBT ( p, x )    r  qr ( x ) lnrr 1clCr pl 
clCr pl(9)Similar to the case of multi-valued classifier by GBT model in the previous section, the maximum
likelihood estimator pˆ  ( pˆ1,..., pˆ K ) ,



K
k 1

pˆ k  1, pˆ k  0, is obtained by maximizing FMGBT ( p, x) inequation (9) with respect to p. Then the classification rule of x is formulated by cˆ  arg max c k C pˆ k .

Experiments
In order to verify the effectiveness of the proposed method, classification experiments by using newspaper
articles and evaluating the classification accuracy are performed. In this study, the combination of
1-vs-the-rest-classifiers which are the most basic configuration of binary classifiers is focused.
Experimental Conditions
In this experiments, four categories (Economic, Social, Sports, and Entertainment) of the Mainichi
Newspapers article published in 2000 are used. Every article belongs to only one category. For the numbers of
training data 100, 300, and 500, the average values of classification accuracy are evaluated. Each experiment isrepeated five times and the numbers of test data are equally 200. To estimate the parameters of the
log-likelihood, the gradient method is applied. We use the word “frequency” as features of documents. The
feature space is configured by words with more than 10 times appearance in whole documents. To evaluate theperformance of the proposed method, we compare its accuracy with that of the original GBT model that does
not take the accuracy of the classifier into account.
Result of Experiments
Figure 1 shows the results obtained by averaging the accuracies of experiments. In each experiment, thenumber of training data was set in three patterns: 100, 300, and 500. From the results, in the cases of 100 and
300 training data, the proposed method has statistically significantly higher classification accuracy than theconventional methods. In the case of 500 training data, there is no significant difference between two methods.
It can be clarified that the proposed method is effective when using a small number of training data.

Classification accuracy

0.82
Conventional method
0.8Proposed method
0.78
0.76
0.74
0.72

100*

300*

500

Figure 1. Classification accuracy by each number of training data (* shows that there is a 5% significant difference).

MULTI-VALUED DOCUMENT CLASSIFICATION

917

Discussion
The proposed method is an effective method when only a small number of training data are used inlearning phase. If a large number of training data are used, the effectiveness of the proposed method is
diminished because classification accuracy of each classifier can be improved and the effect of weighting is
diminished. If we have to treat the more complex data structure, this characteristic is desirable in practice.

Conclusion and Future WorkIn this study, the new multi-valued classification method by the GBT model considering the variation in
the accuracy of each classifier is proposed and shows the effectiveness of the proposal by the experiments. The
proposed method is effective in accuracy especially for the case only a small number of training data can beused for learning phase. The idea to use the information of accuracy of each classifier is useful for othermethods with a combination of classifiers.
The proposed weighting method is based on a heuristic way. As future work, an examination of a method
to investigate the optimum weight is remained.

References
Allwein, E. L., Schapire, R. E., & Singer, Y. (2000). Reducing multiclass to binary: A unifying approach for margin classifiers.
Journal of Machine Learning Research, 1, 113-141.
Bishop, C. M. (2006). Pattern recognition and machine learning (pp. 56-67). New York: Springer-Verlag.
Bradley, R. A., & Terry, M. E. (1952). Rank analysis of incomplete block designs: The method of paired comparisons. Biometrika,
39, 324-345.
Cortes, C., & Vapnik, V. (1995). Support-vector networks. Journal of Machine Learning Research, 20, 273-297.
Crammer, K., & Singer, Y. (2002). On the learnability and design of output codes for multiclass problems. Machine Learning, 47,
201-233.
Dietterich, T. G., & Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes. Journal of Artificial
Intelligence Research, 2, 263-286.
Hastie, T., & Tibshirani, R. (1998). Classification by pairwise coupling. The Annals of Statistics, 26, 451-471.
Huang, T. K., Weng, R. C., & Lin, C. J. (2006). Generalized bradley-terry models and multi-class probability estimates. Journalof Machine Learning Research, 7, 85-115.
Ikeda, S. (2010). Combining binary machines for multiclass: Statistical model and parameter estimation. The Institute of
Statistical Mathematics, 58, 157-166.
Lee, Y., Lin, Y., & Wahba, G. G. (2001). Multicategory support vector machines. Technical Report 1040, Department of
Statistics, University of Madison, Wisconsin.
Quinlan, J. R. (1993). Programs for machine learning. San Mateo, C.A.: Morgan Kaufmann.
Rumelhart, D. E., & McClelland, J. L. (1986). Parallel distributed processing explorations in the microstructure of cognition.
Cambridge, M.A.: MIT Press.
Silva, C., & Ribeiro, B. (2006). Scaling text classification with relevance vector machines (pp. 4186-4191). Proceedings from
SMC2006: IEEE International Conference on Systems, Man, and Cybernetics.
Tipping, M. E. (2001). Sparse Bayesian learning and the relevance vector machine. Journal of Machine Learning Research, 1,
211-244.