1

Improving Classifier Performanceusing Data with Different Taxonomies
Tomoharu Iwata, Toshiyuki Tanaka, Member, IEEE, Takeshi Yamada, Member, IEEE,
and Naonori Ueda Member, IEEE,
Abstract—We propose a framework for improving classifier performance by effectively using auxiliary samples. The auxiliary samples
are labeled not in terms of the target taxonomy according to which we wish to classify samples, but according to classification schemesor taxonomies that are different from the target taxonomy. Our method finds a classifier by minimizing a weighted error over thetarget and auxiliary samples. The weights are defined so that the weighted error approximates the expected error when samples areclassified into the target taxonomy. Experiments using synthetic and text data show that our method significantly improves the classifier
performance in most cases compared to conventional data augmentation methods.
Index Terms—transfer learning, semi-supervised learning, text classification

F

1

I

I NTRODUCTION
N general, performance of a classifier can be improved

as the number of training samples is increased. In
real applications, however, one does not necessarily
have enough training samples to achieve a reasonable
performance. In order to circumvent such difficulties,
there has been great interest in methods that augment
and effectively increase training samples, such as semisupervised learning [1] and domain adaptation [2],where the former augments a set of training samples
with unlabeled samples and the latter with samples fromdifferent domains. Another way to improve performancewith fewer training samples is active learning [3], whichconstructs a set of training samples by actively selecting
unlabeled samples and making queries for their labels,
thereby effectively reducing required labeled samples fortraining.
In this paper we consider a related but different setting, in which we have not only target samples thatare labeled using the same taxonomy as the one wewant to classify samples, but also auxiliary samples
that are labeled using different taxonomies. In many
applications, there are few target samples but a lotof auxiliary samples. For example, suppose that one
wants to classify web pages automatically according to
her personal taxonomy. It is almost always the casethat one has only a few web pages labeled with her
taxonomy, since labeling web pages is a tiresome andtime-consuming task. On the other hand, there are ahuge collection of web pages available that have alreadybeen categorized according to various taxonomies bysomebody else, such as directory search engines or users
in social bookmark sites. Such auxiliary samples can be
useful, because there may be classes in the auxiliary• T. Iwata, T. Yamada, and N. Ueda are with NTT Communication Science
Laboratories.
• T. Tanaka is with Graduate School of Informatics, Kyoto University.

samples that are similar in their classification criteria
to those in the target samples, and samples in theseclasses may be helpful in training a classifier for thetarget taxonomy. However, supervised learning methods
cannot utilize such auxiliary samples, since class labels
given to the auxiliary samples are semantically different
from those given to the target samples; even if labels
are nominally the same, the classification criteria may
be different.
Our solution, proposed in this paper, is a simple
framework for making efficient use of auxiliary samples
with different taxonomies in order to improve performance of a classifier. Our method automatically finds
auxiliary classes that are similar to target classes, andtrains a classifier by using not only target samples but
also auxiliary samples with class-dependent weights.
The weights represent similarities between the target
and auxiliary classes, and it is important to set themappropriately for improving classifier performance. Our
method sets the weights so that the error with theseweights over the target and auxiliary samples approximates the expected error when samples are classified
into target classes. Therefore, we can learn a classifier
for target classes by minimizing the weighted error. We
call our framework class adaptation. Our framework ofmaking use of auxiliary samples is widely applicable inconjunction with a variety of existing classifiers simply
by introducing weights without modifying the classifiers
themselves.

2

P ROBLEM SETTING

Let T be a set of target classes, and A be a set of auxiliary
classes. The goal is to find a classifier f : x 7→ y, y ∈ TTusing target samples DT = {(xn , yn )}N
n=1 , where yn ∈ T ,and auxiliary samples DA = {(xn , yn )}N
n=NT +1 , whereyn ∈ A. Here, xn is the feature vector of the nth sample,
yn is the class label of the nth sample, NT is the number

2of samples with target class labels, and N is the numberof all samples. We assume that y is a discrete variable.
We also assume that x is a vector of discrete variables
throughout this paper. Note that the following analysis isunchanged if some or all of elements in x are continuous,
except that the summations should be replaced withintegrations.
In general, a classifier is trained by minimizing thefollowing empirical error over the given target samples:ET (f ) =NT
1 ∑J(xn , yn ; f ),NT n=1(1)where the error function J(x, y; f ) represents error of
the classifier f given the sample (x, y). Typical error
functions include negative log likelihood J(x, y; f ) =− log P (y|x; f ), and 0-1 loss function, J(x, y; f ) = 0 if
f (x) = y and J(x, y; f ) = 1 otherwise. As the number oftarget samples NT grows to infinity, ET (f ) converges tothe expected error. Therefore, the minimization of ET (f )will lead to the minimization of expected error if wehave sufficient numbers of target samples. However, if
we have only a few target samples, the trained classifier
can overfit the given target samples, which results inpoor performance.

error approximates the expected error for target classes:∑∑
E(f ) ≈
P (x, t)J(x, t; f ) ≡ E(f ).
(3)
x t∈T

In order to accomplish this approximation, we consider
the following generative model for the whole samples
DT ∪ DA . We regard that each sample consists of thetriplet (x, y, t), and that only the pair (x, y) is observed
as a sample, where y ∈ Y and t ∈ T represent observed
and target classes of the sample, respectively. Thus, t isa latent, or hidden, variable of our generative model.
Assuming that x and t are conditionally independent
given y, i.e. P (x|y, t) = P (x|y), the joint distribution ofx and t is written as follows:∑
P (x, t) =P (t)P (y|t)P (x|y),(4)y∈Y

where P (t) is a prior distribution of the target classt, where P (y|t) is a conditional distribution which describes how the observed class y depends on the target
class t, and where P (x|y) is a distribution of the sample
attributes x given the observed class y.
By using (4), the expected error is rewritten as follows:
E(f )

3

=
=

3.1 Weighted error

∑∑

N
1 ∑∑

=

J(x, t; f )P (x|y)P (y)P (t|y)P (x, y)

P (x, y)∑J(x, t; f )P (t|y),

(5)

t∈T

∑
which is the expected value of t∈T J(x, t; f )P (t|y) withrespect to P (x, y). The expected value can be approximated by an empirical expected value over the samples
as:N∑∑ 1 ∑
x y∈Y

(2)

N n=1

δ(xn ,yn ) (x, y)∑J(x, t; f )P (t|y)

t∈T

1 ∑∑
P (t|yn )J(xn , t; f ),
N n=1
N

t∈T

If we choose weights so that w(t|y) = 1 if t = y
and w(t|y) = 0 otherwise, then the weighted error
E(f ) coincides up to the overall factor NT /N with theempirical error over the target samples ET (f ) in (1),which means that the weighted error (2) includes theempirical error (1) as a special case. In general, w(t|y)
takes a value between 0 and 1. If we wish, we can impose
a constraint that the weight between a target class andanother target class is zero: w(t|y) = 0 if y ∈ T andy 6= t. We do not use the constraint, however, because
one can improve classifier performance by making use of
relationships among target classes if target classes forma hierarchical structure [4].
Since we want a classifier that classifies a sample into
one of the target classes with as small error as possible,
we need to set weights {w(t|y)} so that the weighted

∑

P (y)

y∈Y

x y∈Y

E(f ) ≈
w(t|yn )J(xn , t; f ).

∑∑∑ P (t)P (y|t)
y∈Y

x t∈T

We assume that the number of available target samples
is small, and consider how to make efficient use of auxiliary samples in order to improve classifier performance.
Let Y = T ∪ A be a set of all classes. Assume that
we have weight w(t|y) that represents correlation orsimilarity viewed from class y ∈ Y to class t ∈ T . We
learn a classifier by minimizing the following weighted
error over the given target and auxiliary samples:

N n=1

J(x, t; f )x t∈TP ROPOSED METHOD

E(f ) =

∑∑

=

(6)

t∈T

where P (x, y) is approximated by the empirical distribu∑Ntion P (x, y) ≈ N1 n=1 δ(xn ,yn ) (x, y). Here, δ(xn ,yn ) (x, y)
represents Kronecker’s delta, i.e. δ(xn ,yn ) (x, y) = 1 if
(xn , yn ) = (x, y) and 0 otherwise. Identifying the approximated E(f ) with the weighted error E(f ), we seethat the weights w(t|y) should be set equal to P (t|y), thatis, we have:
P (t)P (y|t),(7)
w(t|y) =
P (y)
(y|t)
where the Bayes rule P (t|y) = P (t)Pis used. The
P (y)above formula shows that one can calculate the proper
weights w(t|y) once we have estimates for P (t), P (y),and P (y|t).

3

TABLE 1
The algorithm of our method.

3.2 Estimation of weights
The maximum likelihood estimate of P (y) is given
straightforwardly by P̂ (y) = Ny /N , where Ny denotes
the number of samples with class y.
In order to obtain an estimate of P (t), we assume
that P (t), which is the probability of the target classt in the whole samples DT ∪ DA , is the same as theprobability of the class t in the target samples DT . It
is reasonable because the target taxonomy should be
regarded as somehow personal in our assumed scenario,
and it is unlikely that the external sources of auxiliary
samples are affected by the target taxonomy in theirclassification of samples. Under this assumption, we canobtain a maximum likelihood estimate of P (t), which
is given by P̂ (t) = Nt /NT , where Nt is the number ofsamples with class t.
We can estimate a set of conditional probabilities{Pt }t∈T , where Pt = (P (y|t))y∈Y , using the EM algorithm. Under our generative model (4), the log likelihoodfor class t being maximized is written as follows:∑∑log
P (y|t)P̂−n (xn |y),(8)
L(Pt ) =n:yn =ty∈Ywhere we use leave-one-out cross-validation (LOO) andthus P̂−n (x|y) represents an estimate of the model distribution of class y that is estimated in advance using samples with class y excluding the nth sample.
For the model distributions, one can arbitrarily assume
a generative model that is appropriate for the given
samples, such as Gaussian or multinomial distribution.
If we estimate the conditional probabilities Pt using
training samples that are also used for estimating themodel distribution, the estimation will become biased.
Specifically, we will obtain w(t|y) = 0 if y 6= t, so that
auxiliary samples will not be used at all. Therefore, we
use LOO. Note that P̂−n (x|y) for y ∈ A is the same as
the respective non-LOO estimate. Note also that when
we use an exponential family for the model distribution,
the computational cost required for the LOO estimation
is no greater than that of non-LOO estimation if sufficient
statistics are calculated in advance. When the model
distributions P̂−n (x|y) are fixed, the global optimalityof the estimate is guaranteed since L(Pt ) is convex withrespect to Pt .
(τ )Let Pt be an estimate at τ th step of the EM algorithm. The conditional expectation of the complete-data
log likelihood being maximized is:(τ )Q(Pt |Pt )
∑ ∑
(τ )
=
P (y|xn , t; Pt ) log P (y|t)P̂−n (xn |y).(9)n:yn =t y∈Y

Here, the class posterior probability of xn given the(τ )current estimate Pt can be computed via the Bayes
rule:
(τ )

P (y|xn , t; Pt ) = ∑P (τ ) (y|t)P̂−n (xn |y)y 0 ∈Y P(τ ) (y 0 |t)P̂0−n (xn |y )

.

(10)

Input: target samples DT , auxiliary samples DA
Output: classifier f1) Compute the estimation of the prior probabilities P̂ (t) for t ∈ T
and P̂ (y) for y ∈ Y2) Compute the LOO estimation of the model distributionsP̂−n (x|y) for y ∈ Y , n = 1, · · · , N
3) Compute the estimation of the conditional probabilities P̂ (y|t)
for t ∈ T , y ∈ Y using EM algorithm as in (10) and (11)P̂ (t)P̂ (y|t)4) (weight estimation) Set weights w(t|y) =for t ∈ T ,P̂ (y)y∈Y5) (classifier training)P
Find classifier
f by minimizing the weighted
PN1
error E(f ) = N
n=1t∈T w(t|yn )J(xn , t; f ) while fixing
weights

An estimate of the conditional probabilities at the next
(τ +1)
step, Pt
= (P (τ +1) (y|t))y∈Y , is obtained by maxi(τ )mizing Q(Pt |Pt ) with respect to Pt , yielding:1 ∑(τ )P (τ +1) (y|t) =P (y|xn , t; Pt ).
(11)
Nt n:y =tn

By iterating these steps until a convergence criterion issatisfied, we obtain the global optimum solution of Pt .
Table 1 shows the algorithm of our method for improving classifier performance by using auxiliary samples. Our method has two parts, weight estimation andclassifier training. This modularity enables us to extend
existing classifiers easily to utilize auxiliary samples by
the simple sample weighting method. The classifier tobe trained does not have to be based on the generativemodel that is used in weight estimation: It can be basedon a different generative model, or even on a discriminative model.
The classifier to be used in step 5) should be capable ofdealing with weighted samples. It is not a severe limitation of our approach because many common classifiers
are able to learn with a weighted error. For example,
for learning a classifier that is based on an exponential family, such as that with multinomial or Gaussianclass-conditional distributions, one has only to calculate
weighted sufficient statistics.
Intuitively speaking, our method finds relationships
between target and auxiliary classes, assigns target-classweights to each of the target and auxiliary samples, andthen uses the weighted auxiliary samples for training to
improve classifier performance.

4

R ELATED WORKS

A number of methods have been proposed for improving classifier performance by using auxiliary samples.
There are three general approaches. The first approach
utilizes auxiliary samples as unlabeled samples, such as
semi-supervised learning [1], [5]. It ignores the auxiliary
class information that can be helpful for improving
classifier performance. The second approach uses theauxiliary class information, but requires the classes to4

be the same as the classes in the target samples, suchas domain adaptation [2]. It cannot use samples withdifferent taxonomies. The third approach uses the auxiliary class information even if the classes are different
from those given to the target samples. Examples of thethird approach include transfer learning, catalog integration, cross-training, ontology matching, and featureaugmentation as well as our method. Transfer learning [6] utilizes problems similar to a target problem inorder to improve classifier performance. Our method isdifferent from previous transfer learning methods in that
we train a target classifier using relationships between
classes. Catalog integration [7] addresses the problem
of integrating samples from different taxonomies intoa target taxonomy, in which the samples need to belabeled with different taxonomies. In contrast, we do
not assume the samples to be labeled. Cross-training [8]improves classifier performance by using samples with
two taxonomies. Our method can utilize samples withmore than two taxonomies. We compared our method
and cross-training by text classification experiments in
Section 6. Ontology matching [9] finds similar classes indifferent taxonomies. It is different from our method inthat the similarity measure is not defined for improving classifier performance. In feature augmentation [10],[11], [12], class information in different taxonomies isaugmented into each feature vector in target samples.
The augmentation values are calculated by a classifier
trained with auxiliary samples. Our method is different
from them in that we find the correspondence between
target and auxiliary classes. We compared our method
and a feature augmentation method by experiments in
Section 6.
The method proposed in [13] improves classifier performance by using proximity between classes in the ontology. The method and ours are similar in the sense thatboth methods incorporate contributions from samples
with related classes. The difference is that we propose
a principled procedure to calculate the similarities, or
weights, so that the weighted error approximates the
expected error by assuming a generative model as in (4),rather than assuming that the similarities are given.

5

TOY EXAMPLE

We demonstrate performance of our method using simple synthetic data for a toy binary classification problem.
In the toy problem, target samples are generated fromtwo 100-dimensional Gaussian distributions where theirmeans are µW∗ = (−1, 0, · · · , 0) and µE∗ = (1, 0, · · · , 0),
respectively, and their covariances are identity matrices.
For auxiliary samples, we consider the following four
scenarios:• Identical where class distributions are identical tothose of the target samples, µW = (−1, 0, · · · , 0),µE = (1, 0, · · · , 0);• Diagonal where the class relationship is correlated to that of the target samples, µNW =1111(−2− 2 , 2− 2 , 0, · · · , 0), µSE = (2− 2 , −2− 2 , 0, · · · , 0);

Orthogonal where the class relationship is orthogonal to that of the target samples, µN =(0, 1, 0, · · · , 0), µS = (0, −1, 0, · · · , 0); and• Mix where the mixture of Identical and Orthogonal
scenarios, µW = (−1, 0, · · · , 0), µE = (1, 0, · · · , 0),µN = (0, 1, 0, · · · , 0), µS = (0, −1, 0, · · · , 0).
The elements of the mean vectors except the first twoelements are set equal to zero and covariances are
identity matrices in all scenarios. Figure 1(a) schematically shows the distribution of the target samples, andFigs. 1(b)∼(e) show those of the auxiliary samples for thefour scenarios considered, in which the circles represent
the contours of the standard deviation of the first andsecond dimensions. The number of auxiliary classes isfour in the Mix scenario, and two in the others. We
generated 2, 4, 8, 16, 32, 64, 128, 256 target samples, 256
auxiliary samples, and 100 test samples for each class.
We used the Gaussian classifier, that is, we used theerror function J(x, t; f ) = 21 k x − µt k2 , which amounts
to assuming Gaussian with isotropic covariance as themodel distribution and adopting negative log likelihoodof the Gaussian as the error function.
Table 2 shows the classification accuracies achieved byour method with auxiliary samples for the four scenarios
considered, and accuracies without auxiliary samples(labeled as “Target-only”). The values in the table represent the average accuracies over 100 experiments. The
accuracies achieved by our method with the Identicalscenario are significantly improved compared to those of
the Target-only scenario, especially in the case where thenumber of target samples is small. When the distributionof an auxiliary class is identical to that of a target class,the auxiliary samples can be used as target samples
if we find the correspondence between the target andauxiliary classes. Since finding the correspondence usually needs smaller number of samples than modelingthe distribution itself, the classifier performance can be
improved with the small number of target samples as
is observed in this result. The accuracies achieved with
the Diagonal scenario are also better than those with theTarget-only scenario. This result implies that our method
can improve classifier performance if there is somecorrelation between target and auxiliary classes, eventhough the distributions are not identical. When there isno correlation as in the Orthogonal scenario, our method
is not helpful in improving classifier performance, andmay worsen the performance. However, if there are also
auxiliary classes that are correlated to the target classes
as well as orthogonal classes as in the Mix scenario,
our method can improve classifier performance by using
samples in correlated classes and ignoring samples inorthogonal classes.
Figure 2 shows the estimated conditional probabilities
P (y|t). The probabilities in highly correlated classes are
high, such as (W∗ , W) and (E∗ , E) elements in Identicaland Mix scenarios, and they match with the characteristics of generative models of the auxiliary samples.
This trend becomes stronger with the number of target
•

5

N

NW
W*

E*

W

W
SE

(a) Target

NE(b) Identical(c) Diagonal

E

S

S

(d) Orthogonal(e) Mix

Fig. 1. Synthetic target data (a) and auxiliary data (b)∼(e). The circles represent the contours of the standard deviationof the first and second dimensions.
TABLE 2Average accuracies (%) over 100 experiments with the synthetic data (Gaussian). The value in the parenthesis
represents the standard deviation. The value is in bold face when it is better than that of Target-only.
#target samples
2
4
8
16
32
64
128
256
average

Target-only
56.2 (4.4)
60.9 (4.9)
63.9 (4.3)
68.5 (4.1)
73.0 (3.7)
77.6 (3.5)
80.3 (3.0)
82.2 (2.6)
70.3 (9.7)

Identical
65.0 (9.3)
75.5 (7.4)
80.4 (3.4)
81.1 (2.8)
81.2 (2.7)
82.0 (2.7)
82.8 (2.9)
83.0 (2.1)
78.9 (7.5)

Diagonal
60.4 (7.7)
65.0 (8.3)
69.8 (6.6)
74.2 (4.0)
76.7 (3.5)
78.3 (3.0)
80.9 (2.7)
81.7 (3.1)
73.4 (8.9)

Orthogonal
49.5 (4.2)
49.9 (4.9)
51.9 (6.2)
59.4 (7.3)
70.0 (5.0)
77.2 (3.4)
80.3 (3.4)
81.9 (3.0)
65.0 (13.9)

Mix64.0 (8.7)
73.0 (7.7)
78.8 (4.0)
79.9 (2.7)
81.6 (3.1)
82.4 (2.4)
82.7 (2.7)
83.0 (2.7)
78.2 (7.8)

4 target samples
t=W*

W*

W*

W*

t=E*

E*

E*

E*

y=W* y=E*

y=W

y=E

W*

E*

NW

SE

W*

E*

N

S

W*

E*

W

E

N

S

W*

E*

W

E

N

S

W*

E*

W

E

N

S

32 target samples
W*

W*

W*

W*

E*

E*

E*

E*

W*

E*

W

E

W*

E*

NW

SE

W*

E*

N

S

256 target samples
W*

W*

W*

W*

E*

E*

E*

E*

W*

E*

W

E

(a) Identical

W*

E*

NW

SE

(b) Diagonal

W*

E*

N

(c) OrthogonalS(d) Mix

Fig. 2. Estimated conditional probabilities P (y|t) for the synthetic data (Gaussian). The (t, y) element represents
P (y|t). Darker color indicates higher coefficient.

samples increases.

6

A PPLICATION TO TEXT CLASSIFICATION

6.1 Weight estimation
We describe application of our method to a text classification problem. We assume that a document is represented by a word count vector x = (xj )Vj=1 where
xj is the count of word j in the document, and V
is the vocabulary size of the entire collection. We use
the multinomial∏V distribution for the model distribution
P (x|y) ∝ j=1 θyj xj where θyj is the probability thatthe word j appears in a document whose class is y. The
LOO maximum likelihood estimation of parameter θyj
without the nth sample, denoted by θ̂−n,yj , is obtainedby:∑xmj − xnj
m =y
(m:y
),
θ̂−n,yj = ∑
(12)
∑
V
k=1
m:ym =y xmk − xnk
where m is a document index, 1 ≤ m ≤ N . The
estimates θ̂−n,yj are allowed to be zero by definition, but
it causes difficulty in our formulation. In order to avoid
the zero probability problem, we employ the following

6smoothing operation with a uniform distribution:θ̃−n,yj = αθ̂−n,yj + (1 − α)

1
,
V

(13)

where 0 ≤ α < 1 is a hyper-parameter, and use θ̃−n,yj
as the estimate of θyj . It should be noted that thissmoothing is equivalent to using a Dirichlet prior forthe multinomial parameters.
We can estimate the unknown conditional probabilities {Pt } and the hyper-parameter α simultaneously by
maximizing the following complete-data log likelihoodusing the generalized EM algorithm:
∑ ∑
(τ )
(τ )
Qt
=
P (y|xn , t; Pt , α(τ ) )n:yn =t y∈YV()∑× log P (y|t) +xnj log θ̃−n,yj , (14)
j=1
(τ )
(τ )
where, and hereafter, Qt represents Q(Pt , α|Pt , α(τ ) ).

The E-step and the update of conditional probabilities in
the M-step follow the same procedures as the standard
EM algorithm described in (10) and (11), respectively. In
the M-step, we update the hyper-parameter α using the
Newton method:()(τ ) −1(τ )∂ 2 Qt∂Qt(τ +1)
(τ )
,
(15)
α
=α −
∂α
∂α2
where the derivatives are evaluated as:
(τ )
∑ ∑
∂Qt
(τ )
=
P (y|xn , t; Pt , α(τ ) )∂αn:yn =t y∈Y)(V∑θ̂−n,yj − V1×xnj,
θ̃−n,yj
j=1

(16)

∑ ∑

(τ )

= −
×

(

xnj

N
V
∑
1 ∑∑
w(t|yn )xnj log φtj
N n=1
j=1
t∈T

−

β

V
∑∑

log φtj .

(19)t∈T j=1

Here β is a hyper-parameter characterizing the Dirichletprior. The estimation of φtj that minimizes this weighted
error is as follows:∑N1
n=1 w(t|yn )xnj + βNφ̂tj = 1 ∑V ∑
.
(20)
N
k=1
n=1 w(t|yn )xnk + βV
N
The maximum entropy model is a discriminativemodel, and it estimates a probability distribution thatmaximizes entropy under the constraints in the given
samples. This model has been used in various research
fields such as text classification [14] and collaborative
filtering [15]. The maximum-entropy distribution of thetarget class t given the word count vector x is represented as follows:exp(λ>
t x)
,
> x)
exp(λ
t0
t0 ∈T

P (t|x) = ∑(21)

where λt is an unknown parameter vector for class t,
and where λ>t represents the transpose of λt . When
we use negative log likelihood for the error function
and Gaussian prior for λt with mean 0 and covarianceγ −1 I [16], the weighted error becomes:N∑
1 ∑∑exp(λ>
w(t|yn )(λ>t0 xn ))
t xn − log
N n=1
t0 ∈T
t∈T
γ∑
+
k λt k2 .
(22)
2

(τ )

P (y|xn , t; Pt , α(τ ) )θ̂−n,yj − V1θ̃−n,yj

j=1

)2

t∈T

.

(17)

Since the second-order derivative is always negative orzero, we can obtain the global optimum solution of α byiterating the update (15) in the M-step.
6.2 Text classifiers
We consider three representative text classifiers, thenaive Bayes model, the maximum entropy model, andthe support vector machine. The naive Bayes model assumes that each word is generated independently givena class, which is the same generative model as that used
for the weight estimation. The probability of the word
count vector x in the target class t is represented by:
P (x|t) ∝−= −n:yn =t y∈Y
V∑

E(fNB ) =E(fME )

and∂ 2 Qt∂α2where φtj represents the probability that the word j occurs in the class t. When we use negative log likelihoodfor the error function, and a Dirichlet prior for φtj , theweighted error becomes:

V
∏
j=1

φtj xj ,(18)

Here γ is a hyper-parameter of the Gaussian prior for
λt . We can estimate the unknown parameters {λt }t∈Tby minimization via the quasi-Newton method [17]. The
global optimality of the estimate is guaranteed due tothe concavity of the weighted error.
The support vector machine (SVM) is a discriminativemodel, and it finds the decision boundary so as to maximize the margin between classes [18]. The multiclass
SVM introduced in [18], [19], [20] employs the following
generalized hinge loss for the loss function:∑[1 − (f (xn , yn ) − f (xn , y))]+ , (23)Jhin (xn , yn ; f ) =y6=yn

where f (x, y) is a decision function, and [v]+ =max(0, v). Given the decision function, it classifies aninput vector x to class ŷ having the highest decisionfunction value, ŷ = arg maxy f (x, y). In the linear kernel
SVM, the decision function is represented by f (x, y) =7λ>y x. The weighted error function of the multiclass
SVM with the generalized hinge loss (23) based on ourframework is as follows:
1 ∑∑η∑k λt k2 ,w(t|yn )Jhin (xn , t; f )+
N n=1
2
t∈T
t∈T
(24)
where η is a hyper-parameter. The SVM with weights
for each sample as in (24) is called the fuzzy SVM [21]or weighted SVM [22]. The optimization can be performed by solving a quadratic programming problem
as described in [21], [22].
N

E(fSVM ) =6.3 Methods compared
We considered the following nine methods for the comparison of performance in this section: NB, ME, SVM,
SEMI, CT, FA, CA-NB, CA-ME, and CA-SVM.
NB is the naive Bayes model, ME is the maximum
entropy model, and SVM is the linear kernel support
vector machine. 1 They use only the target samples fortraining.
SEMI is semi-supervised learning with generativemodels as described in [1]. We used a mixture of multinomial distributions for the generative model, and a
Dirichlet distribution for the prior. Unknown parameters
were estimated by maximizing the log likelihood forlabeled (target) samples and unlabeled (auxiliary) samples using the EM algorithm, where target classes in theauxiliary samples are assumed to be hidden variables.
A parameter for discounting unlabeled samples were
estimated by leave-one-out cross-validation.
CT is generative cross-training described in [8], inwhich a document is generated from a mixture of multinomial distributions over pairs of target and auxiliary
classes. The parameters were estimated using the EM
algorithm by maximizing the log likelihood, where auxiliary classes are assumed to be hidden variables for target
samples, and target classes are assumed to be hidden
variables for auxiliary samples. After this estimation, aclassifier for target classes was trained by minimizing theweighted error, where auxiliary samples were weighted
by posterior probability. 2 We show the results when weused NB as the classifier because NB was better than
ME. We estimated a parameter for discounting auxiliary
samples by cross-validation.
FA is a feature augmentation method, in which outputs of an auxiliary classifier are augmented into afeature vector for a target classifier [10]. The training
procedure is as follows. First, an auxiliary classifier is
1. We used the linear SVM because we obtained better resultswith the linear SVM than the nonlinear SVM in our preliminary
experiments.
2. The approach is called EM2D-D in [8]. We also evaluated performance of a variant of EM2D-D, which is called EM2D-G. But
the accuracy of EM2D-G was lower than that of EM2D-D in our
preliminary experiments, so that it is excluded from the comparisons.
This result can be explained as follows: EM2D-D could reduce data
sparsity and improve the reliability of its parameter estimates as
described in [8] and data used here were very sparse.

trained by using auxiliary samples. Next, each feature
vector of a target sample is augmented by auxiliary classposteriors that are outputs of the auxiliary classifier. 3
Finally, a target classifier is trained by using the augmented target samples. We used ME as the classifiers. FA
is similar to the discriminative cross-training describedin [8] although we used ME as the classifier instead of
SVM.
CA-NB, CA-ME, and CA-SVM are our methods (classadaptation) using NB, ME, and SVM as the classifiers,
respectively.
NB, ME, and SVM do not use auxiliary samples at all.
SEMI uses auxiliary samples as unlabeled samples. CT,
FA, CA-NB, CA-ME, CA-SVM use auxiliary samples aslabeled samples with different taxonomies. We normalized the feature vector x for ME so that its elements sum
to one. In each experiment, we sampled target samples
while setting the number of samples for each class to 2,
4, 8, 16, 32, 64, 128, and 256. We used 100 test samples
for each class. We evaluated performance via the average
accuracies over 100 experiments. The hyper-parameters
βN and γN were chosen among {10−3 , 10−2 , 10−1 , 1},and ηN was chosen among {1, 10, 102 , 103 } so that theymaximize the accuracy for a development data generated
separately from training and test data.
6.4

Data

We used the following two sets of data in the evaluations: 20News and Web.
In 20News data, we used documents in the 20 Newsgroups corpus [23]. The corpus contains about 20,000 articles categorized into 20 discussion groups. We omitted
stop-words and words that occurred only once in theentire collection. The vocabulary size was 52,647. We set
the following four groups in the 20 Newsgroups corpus
as the target classes: comp.graphics, rec.sport.baseball,sci.electronics, and talk.religion.misc. These target classes
were selected so that they have different higher-level
categories. We set the other 16 classes as the auxiliary
classes, and used all samples in the auxiliary classes
as auxiliary samples. No articles in the corpus were
multi-posted, which means that there were no samples
classified into multiple categories. The number of theauxiliary samples was 15,211.
In Web data, we used web pages that are categorized in goo category and yahoo category, which are
Japanese directory search engines. We used those words
as features that occurred more than nine times in bothcategories. The vocabulary size was 43,200. We set toplevel 13 classes in goo category as the target classes andtop-level 14 classes in yahoo category as the auxiliary
classes, and used all samples in yahoo category as theauxiliary samples. The number of the auxiliary samples
was 51,728.
3. We can also augment a feature vector by a vector that represents
the predicted label by the auxiliary classifier. However, we found thatthe accuracy was lower than that of the posterior augmentation in our
preliminary experiments.

8

TABLE 3
Average accuracies (%) over 100 experiments for text classification. The value in the parenthesis represents thestandard deviation.
#target samples
2
4
8
16
32
64
128
256
average#target samples
2
4
8
16
32
64
128
256
averageNB
52.4 (4.9)
62.5 (5.3)
72.9 (3.5)
80.9 (2.7)
87.4 (2.1)
91.9 (1.3)
94.7 (1.2)
96.3 (1.0)
79.9 (15.3)
NB
20.0 (2.5)
25.8 (2.4)
32.7 (2.2)
39.8 (1.6)
46.3 (1.5)
51.8 (1.6)
56.1 (1.3)
59.1 (1.3)
41.5 (13.5)

ME
53.7 (5.1)
64.9 (4.6)
73.8 (3.3)
81.1 (2.3)
86.6 (1.8)
90.8 (1.3)
93.3 (1.3)
95.2 (1.0)
79.9 (14.1)
ME
18.5 (2.5)
23.5 (2.0)
29.9 (2.0)
37.4 (1.7)
45.0 (1.5)
51.3 (1.4)
56.7 (1.4)
61.1 (1.2)
40.4 (14.8)

SVM
52.6 (5.6)
62.5 (4.8)
72.7 (5.9)
80.1 (2.9)
86.2 (2.0)
90.0 (1.5)
92.2 (1.5)
94.1 (1.2)
78.8 (14.6)
SVM
16.8 (3.8)
22.1 (3.7)
27.1 (3.6)
34.5 (4.0)
40.1 (4.3)
46.5 (4.0)
52.4 (4.3)
57.4 (4.6)
37.1 (14.2)(a) 20News
SEMI
CT
73.0 (5.3) 74.1 (7.2)
77.3 (4.4)
79.9 (6.1)
79.6 (4.2)
83.2 (3.7)
82.8 (3.4) 85.7 (2.7)
84.9 (2.9) 87.2 (1.9)
88.1 (2.3) 89.1 (1.6)
91.4 (1.8) 90.9 (1.5)
94.1 (1.6) 93.2 (1.3)
83.9 (7.6) 85.4 (7.0)

FA
73.7 (5.4)
77.8 (3.7)
79.6 (3.3)
81.4 (2.2)
82.0 (2.3)
82.7 (2.0)
83.5 (1.8)
84.0 (1.6)
80.6 (4.4)

CA-NB
74.3 (7.3)
79.0 (4.5)
81.5 (3.6)
86.1 (2.4)
89.7 (1.8)
92.9 (1.1)
95.2 (1.2)
96.4 (1.0)
86.9 (8.3)

CA-ME
69.7 (7.1)
72.7 (4.8)
75.4 (3.7)
80.8 (3.0)
86.5 (2.4)
91.2 (1.3)
93.9 (1.2)
95.8 (1.0)
83.2 (10.1)

CA-SVM
69.7 (7.7)
72.0 (4.6)
76.7 (3.0)
79.9 (2.5)
84.5 (2.3)
88.9 (1.6)
92.1 (1.4)
94.0 (1.2)
82.2 (9.3)(b) Web
SEMI
CT
21.3 (4.3)
21.4 (4.4)
28.0 (4.0)
29.4 (4.3)
33.8 (3.3)
36.1 (3.6)
38.8 (2.9)
42.1 (2.7)
42.5 (2.2)
46.5 (1.9)
45.8 (2.1)
49.9 (1.7)
49.1 (1.8)
53.4 (1.4)
52.6 (1.8)
56.5 (1.3)
39.0 (10.5) 41.9 (11.8)

FA
27.5 (4.7)
32.3 (2.7)
36.0 (2.0)
38.5 (1.5)
40.9 (1.4)
43.4 (1.5)
45.5 (1.4)
46.8 (1.1)
38.9 (6.6)

CA-NB
27.8 (4.6)
33.4 (3.3)
40.0 (2.8)
45.5 (2.4)
50.5 (1.6)
53.7 (1.7)
57.1 (1.5)
59.2 (1.3)
45.9 (10.9)

CA-ME
26.7 (4.6)
31.0 (3.1)
37.2 (2.7)
43.4 (2.6)
49.5 (1.7)
53.7 (1.7)
58.5 (1.5)
62.4 (1.3)
45.3 (12.4)

CA-SVM
24.8 (5.1)
28.6 (4.9)
33.7 (4.3)
39.5 (3.7)
43.8 (4.4)
46.8 (3.8)
51.3 (4.1)
54.0 (4.3)
40.3 (10.8)

TABLE 4
Average computational time (second) over 100 experiments for text classification. The rightmost column represents
the computational time for the weight estimation in our class adaptation framework.
#target samples
2
4
8
16
32
64
128
256
#target samples
2
4
8
16
32
64
128
256

NB
0.052
0.052
0.052
0.052
0.052
0.052
0.053
0.054

NB
0.893
0.897
0.889
0.890
0.902
0.926
0.945
0.992

ME
1.433
1.517
1.602
1.747
1.937
2.204
2.230
2.571

ME
40.53346.86648.95858.92270.50796.620128.851
180.232

SVM
4.881
6.030
7.234
7.799
8.355
8.981
9.792
11.017SEMI
51.74550.82548.22950.13446.96644.67445.88544.910SVM
543.972590.406
689.073824.4761036.839
1277.893
1567.900
2059.920

SEMI
3507.865
3408.127
3309.457
2986.989
2686.255
2622.598
2411.877
2198.670(a) 20NewsCTFA
1.298 19.457
1.313 18.319
1.279 18.767
1.254 18.457
1.241 19.148
1.260 19.118
1.350 19.527
1.522
18.688

CA-NB
0.083
0.084
0.087
0.096
0.121
0.176
1.626
2.785

(b) WebCTFA
35.232419.759
31.825 444.964
27.708 455.161
26.962 450.371
27.709469.524
28.527 463.319
29.129455.730
31.668 450.188

6.5 Results
Table 3 shows the average classification accuracies on
20News and Web data. The accuracies achieved by our
methods (CA-NB, CA-ME, and CA-SVM) are higher
than those by the methods that use only target samples(NB, ME, and SVM), especially in the case of the small
number of target samples. This result implies that our
method can improve classifier performance by using
auxiliary samples effectively. SEMI, CT, and FA also
improve the accuracies. However, their improvements
are smaller than that of our method. This can be understood from the following reasons. SEMI treats auxiliary
samples as unlabeled samples and estimates their target

CA-ME
5.770
7.285
6.713
4.576
3.525
3.031
3.336
3.896

CA-NB
1.115
1.081
1.131
1.232
1.446
1.961
3.258
6.723

CA-SVM
13.806
14.58012.062
8.249
6.373
6.025
7.194
8.411

CA-ME
421.825
262.214115.517103.268
138.920179.198237.886
318.102

Weight Estimation
0.032
0.033
0.038
0.048
0.064
0.097
0.144
0.196

CA-SVM3903.446
2499.104
1051.766
682.612949.600
1456.495
2395.531
4191.200

Weight Estimation
0.119
0.138
0.173
0.243
0.377
0.661
1.191
2.263

classes; it does not use their class information at all. On
the other hand, in our method the auxiliary samples
are already clustered by the class labels. CT estimates a
distribution for each pair of target and auxiliary classes,
and the required number of models is |T ||A|, where| · | represents the number of elements of a set. On theother hand, our method estimates a distribution for eachclass, and the required number of models is |T | + |A|.
Therefore, our method can train classifiers more robustlywith a smaller number of models to be trained than CT.
FA improves the performance well when the numberof target samples is small. However, as the number oftarget samples increases, the performance improvement

9of FA decreases. This result indicates that the augmented
features, which are outputs of the auxiliary classifier,would have a negative effect to train classifiers because
the auxiliary classes are different from the target classes.
We also performed an experiment with the following target classes: sci.crypt, sci.electronics, sci.med, andsci.space. We observed that the performance of the
proposed method was not improved in this case. Thissituation is the same as the Orthogonal scenario in
the toy example experiments presented in Section 5:
Indeed, all the other classes in the corpus were withhigh-level categories different from sci. This experimentdemonstrates that the performance will be improved
only when some of the classes in different taxonomies
are correlated with the target classes.
Table 4 shows the average computational time (second) on 20News and Web data. It was measured oncomputers having 2.66-GHz Xeon CPUs. The computational complexity for the weight estimation in ourframework is small, and it took only a few second
even for large data with 256 target samples per eachclass and 51,728 auxiliary samples in Web data. Error
function J(x, y; f ) is added NT times in the objectivefunction for only target samples (1), and it is added N |T |times in our framework (2). Therefore, our framework
can be regarded as using at most N |T | samples fortraining. If the classifier used in our framework canhandle large scale data, our framework is feasible asshown in the experiments. There are some cases where
the computational time becomes shorter as the numberof target samples increases. This is because that theweights estimated with large target samples are likely
to be sparse, and thus, the effective number of samples
decreases.
Table 5 shows the classes with high conditional probabilities P (y|t) for each target class on 20News data; thenumber of target samples was 32. The classes that havethe same parents are likely to have high coefficients suchas comp.windows.x for comp.graphics target class, andrec.sport.hockey for rec.sport.baseball target class. Even
if the parents are not the same, classes that are closely related have high coefficients such as soc.religion.christian
and alt.atheism for talk.religion.misc target class. Similartendencies can be observed for Web data as well, as in
Table 6. For example, hobby&sport in yahoo has a highcoefficient for sports&hobby&travel target class, andhealth&medicine in yahoo for health&medicine&beauty
target class.

7

C ONCLUSION

We have proposed a simple and promising learning
framework for improving classifier performance by using auxiliary samples with different taxonomies. We
have experimentally confirmed that when some of theclasses in different taxonomies are correlated to thetarget classes, such labeled samples can significantly

improve classifier performance. We have also shown experimentally the advantage of our method over conventional data augmentation methods. These results encourage us to believe that our data augmentation approach,class adaptation, will become a useful tool for designingrobust classifiers.
We plan a wide-ranging exploration of the application area of our method. For example, many people
put tags on many words or sentences for the wide
variety of natural language processing tasks. However,these tagged data are not sufficiently utilized for similartasks. These tagged data may improve the performanceof other tasks. In our framework, weight estimationand classifier training are separated. We would like toconsider the simultaneous estimation of the weights
and the classifier. We used simple model distributions
and classifiers in the experiments. We need to verify
our framework further by applying it to other types ofmodel distributions and classifiers. We also used simple
features in our text classification experiments. Since thefeature design or feature extraction might improve theclassification performance further in our framework, it
would be important to extend our framework to be able
to extract features automatically in the future work.

R EFERENCES[1]

K. Nigam, A. K. McCallum, S. Thrun, and T. M. Mitchell, “Textclassification from labeled and unlabeled documents using EM,”
Machine Learning, vol. 39, no. 2/3, pp. 103–134, 2000.
[2] H. Daume III and D. Marcu, “Domain adaptation for statisticalclassifiers,” Journal of Artificial Intelligence Research, vol. 26, pp.
101–126, 2006.
[3] D. A. Cohn, Z. Ghahramani, and M. I. Jordan, “Active learningwith statistical models,” Journal of Artificial Intelligence Research,
vol. 4, pp. 129–145, 1995.
[4] A. K. McCallum, R. Rosenfeld, T. M. Mitchell, and A. Y. Ng,“Improving text classification by shrinkage in a hierarchy ofclasses,” in ICML ’98: Proceedings of the 15th International Conference
on Machine Learning, 1998, pp. 359–367.
[5] A. Fujino, N. Ueda, and K. Saito, “Semisupervised learning fora hybrid generative/discriminative classifier based on the maximum entropy principle,” IEEE Transactions on Pattern Analysis andMachine Intelligence, vol. 30, no. 3, pp. 424–437, 2008.
[6] R. Raina, A. Y. Ng, and D. Koller, “Constructing informative
priors using transfer learning,” in ICML ’06: Proceedings of the 23rd
International Conference on Machine learning, 2006, pp. 713–720.
[7] R. Agrawal and R. Srikant, “On integrating catalogs,” in WWW’01: Proceedings of the 10th International Conference on World Wide
Web, 2001, pp. 603–612.
[8] S. Sarawagi, S. Chakrabarti, and S. Godbole, “Cross-training:learning probabilistic mappings between topics,” in KDD ’03:
Proceedings of the 9th ACM SIGKDD International Conference on
Knowledge Discovery and Data mining, 2003, pp. 177–186.
[9] A. Doan, J. Madhavan, P. Domingos, and A. Halevy, “Learning
to map between ontologies on the semantic web,” in WWW ’02:
Proceedings of the 11th International Conference on World Wide Web,
2002, pp. 662–673.
[10] R. Florian, A. Ittycheriah, H. Jing, and T. Zhang, “Named entity
recognition through classifier combination,” in Proceedings of theseventh conference on Natural language learning at HLT-NAACL 2003.
Morristown, NJ, USA: Association for Computational Linguistics,
2003, pp. 168–171.
[11] E. Gabrilovich and S. Markovitch, “Harnessing the expertise of
70,000 human editors: Knowledge-based feature generation for
text categorization,” Journal of Machine Learning Research, vol. 8,
pp. 2297–2345, 2007.

10

TABLE 5High conditional probability classes for each target class on 20News data when the number of target samples foreach class is 32. The value in the parenthesis represents the conditional probability.
target classcomp.graphics
rec.sport.baseballsci.electronics
talk.religion.misc

high conditional probability classescomp.windows.x (0.56), sci.space (0.19), comp.sys.ibm.pc.hardware (0.13)
rec.sport.hockey (0.58), rec.sport.baseball (0.13)
comp.sys.ibm.pc.hardware (0.24), rec.autos (0.22), sci.space (0.13), misc.forsale (0.12)
soc.religion.christian (0.56), alt.atheism (0.33)

TABLE 6
High conditional probability classes for each target class on Web data when the number of target samples for eachclass is 32. The value in the parenthesis represents the conditional probability. “g:” and “y:” indicate that the class isin goo category and yahoo category, respectively.
target classentertainment
sports&hobby&travel
life&society
broadband
media&news&politics
shopping
education&academics&culturescience&technology
computer&internet
document&source
regionalbusiness&economics
health&medicine&beauty

high conditional probability classes
y:entertainment (0.24), y:life&culture (0.22), y:computer&internet (0.21)
y:hobby&sports (0.59)
y:life&culture (0.26), y:regional (0.26), y:business&economics (0.23)
y:computer&internet (0.18), y:life&culture (0.17), y:regional (0.15), y:politics (0.11)
g:media&news&politics (0.19), y:life&culture (0.19), y:politics (0.17)
y:business&economics (0.42), g:shopping (0.25), y:computer&internet (0.10)
y:education (0.28), y:art&humanism (0.18), y:life&culture (0.12)
y:science&technology (0.72)
y:computer&internet (0.57), g:computer&internet (0.34)
y:business&economics (0.26), y:life&culture (0.18), y:computer&internet (0.16)
y:regional (0.46), g:regional (0.13), y:life&culture (0.11), y:business&economics (0.10)
y:business&economics (0.59)
y:health&medicine (0.75)[12] ——, “Wikipedia-based semantic interpretation for natural language processing,” Journal of Artificial Intelligence Research, vol. 34,
pp. 443–498, 2009.
[13] G. Pandey, C. L. Myers, and V. Kumar, “Incorporating functional
inter-relationships into protein function prediction algorithms,”
BMC Bioinformatics, vol. 10, no. 142, 2009.
[14] K. Nigam, J. Lafferty, and A. McCallum, “Using maximum entropy for text classification,” in Proceedings of IJCAI-99 Workshop
on Machine Learning for Information Filtering, 1999, pp. 61–67.
[15] T. Iwata, K. Saito, and T. Yamada, “Recommendation method
for extending subscription periods,” in KDD ’06: Proceedings of
the ACM SIGKDD Conference on Knowledge Discovery and Data
Miniining, 2006, pp. 574–579.
[16] S. F. Chen and R. Rosenfeld, “A Gaussian prior for smoothing maximum entropy models,” Computer Science Department,
Carnegie Mellon University, Tech. Rep. CMUCS–99–108, 1999.
[17] D. C. Liu and J. Nocedal, “On the limited memory BFGS method
for large scale optimization,” Mathematical Programming, vol. 45,
no. 3, pp. 503–528, 1989.
[18] V. Vapnik, Statistical Learning Theory. New York: Wiley, 1998.
[19] E. J. Bredensteiner and K. P. Bennett, “Multicategory classification by support vector machines,” Computational Optimization andApplications, vol. 12, no. 1-3, pp. 53–79, 1999.
[20] J. Weston and C. Watkins, “Support vector machines for multiclass pattern recognition,” in Proceedings of the Seventh European
Symposium On Artificial Neural Networks, 1999, pp. 219–224.
[21] C.-F. Lin and S.-D. Wang, “Fuzzy support vector machines,” IEEE.
Transactions on Neural Networks, vol. 13, no. 2, pp. 464–471, 2002.
[22] X. Yang, Q. Song, and Y. Wang, “Weighted support vector
machine for data classification,” International Journal of Pattern
Recognition and Artificial Intelligence, vol. 21, no. 5, pp. 961–976,
2007.
[23] K. Lang, “NewsWeeder: learning to filter netnews,” in ICML ’95:
Proceedings of the 12th International Conference on Machine Learning,
1995, pp. 331–339.

PLACE
PHOTO
HERE

Tomoharu Iwata received the B.S. degree in environmental information from Keio University in
2001, the M.S. degree in arts and sciences fromthe University of Tokyo in 2003, and the Ph.D.
degree in informatics from Kyoto University in2008. He is currently a researcher at Learning and Intelligent Systems Research Group of
NTT Communication Science Laboratories, Kyoto, Japan. His research interests include data
mining, machine learning, information visualization, and recommender systems.

Toshiyuki Tanaka received the B. Eng., M.
Eng., and Dr. Eng. degrees in Electronics Engineering from the University of Tokyo, Tokyo,
Japan, in 1988, 1990, and 1993, respectively.
PLACE
From 1993 to 2005, he was with the Department
PHOTO
of Electronics and Information Engineering at
HERE
Tokyo Metropolitan University, Tokyo, Japan. He
is currently a professor of the Graduate Schoolof Informatics, Kyoto University, Kyoto, Japan.
His research interests are in the areas of neural networks, machine learning, and informationand communication theory. He received DoCoMo Mobile Science Prizein 2003, and Young Scientist Award from the Minister of Education,
Culture, Sports, Science and Technology, Japan, in 2005.

11

Takeshi Yamada received the B.S. degree inmathematics from the University of Tokyo in
1988 and the Ph.D. degree in informatics from
Kyoto University in 2003. He was a Leader
PLACEof Emergent Learning and Systems Research
PHOTO
Group of NTT Communication Science LaboHERE
ratories and is currently a Senior Manager of
NTT Science and Core Technology Laboratory
Group. His research interests include Data Mining, Statistical Machine Learning, Graph Visualization, Metaheuristics and Combinatorial Optimization. He is a member of the ACM and IEEE.

Naonori Ueda received the B.S., M.S., andPh D degrees in Communication Engineeringfrom Osaka University, Osaka, Japan, in 1982,
1984, and 1992, respectively. In 1984, he joined
PLACE
the Electrical Communication Laboratories, NTT,
PHOTO
Japan, where he was engaged in research on
HERE
image processing, pattern recognition, and computer vision. In 1991, he joined the NTT Communication Science Laboratories, where he has
invented a significant learning principle for optimal vector quantizer design and has developed
some novel models and learning algorithms. His current research interests include parametric and non-parametric Bayesian approach to machine learning, pattern recognition, data mining, signal processing, andcyber-physical systems. From 1993 to 1994, he was a visiting scholar
at Purdue University, West Lafayette, USA. Currently, he is a directorof NTT Communication Science Laboratories. He is an associate editorof Neurocomputing and Journal of Neural Networks, and is a fellow of
the Institute of Electronics, Information, and Communication Engineers(IEICE).