IEICE Transactions on Information and Systems,
vol.E94-D, no.6, pp.1337–1340, 2011.

Improving the Accuracy of
Least-Squares Probabilistic Classifiers
Makoto Yamada
Tokyo Institute of Technology, Japan
Masashi Sugiyama
Tokyo Institute of Technology and JST PRESTO, Japan
Gordon Wichern
Arizona State University, U.S.A.
Jaak Simm
Tokyo Institute of Technology, Japan

Abstract
The least-squares probabilistic classifier (LSPC) is a computationally-eﬃcient alternative to kernel logistic regression. However, to assure its learned probabilities
to be non-negative, LSPC involves a post-processing step of rounding up negative
parameters to zero, which can unexpectedly inﬂuence classiﬁcation performance.
In order to mitigate this problem, we propose a simple alternative scheme that directly rounds up the classiﬁer’s negative outputs, not negative parameters. Throughextensive experiments including real-world image classiﬁcation and audio tagging
tasks, we demonstrate that the proposed modiﬁcation signiﬁcantly improves classiﬁcation accuracy, while the computational advantage of the original LSPC remains
unchanged.
Keywords
Least-Squares Probabilistic Classiﬁer, Kernel Logistic Regression, Density Ratio,
PASCAL VOC 2010, Freesound1

Improving the Accuracy of Least-Squares Probabilistic Classifiers

12

Introduction

The least-squares probabilistic classifier (LSPC) [1] is an eﬃcient non-linear probabilisticclassiﬁcation method that learns class-posterior probabilities. In LSPC, a linear combination of kernels centered at training points is employed as a model of class-posterior
probabilities. Then the LSPC model is trained so that the squared diﬀerence to thetrue class-posterior probability is minimized. An advantage of this linear least-squares
formulation is that the global optimal solution can be obtained analytically (cf. kernel
logistic regression [2, 3], which can be used for similar purposes, but requires iterative
optimization such as Newton’s method). However, since LSPC involves a post-processing
step of rounding up negative model parameters to zero for assuring the non-negativity ofprobability estimates, learned class-posterior probabilities can change unexpectedly.
In order to mitigate this problem, we propose a simple alternative scheme that directly rounds up the classiﬁer’s negative outputs, as opposed to its negative parameters. While the original parameter-rounding scheme inﬂuences learned class-posterior
probabilities globally through the change of parameters for basis functions, the proposed
output-rounding scheme conﬁnes the inﬂuence to only those points where probabilities
are negative (see Figure 1, which will be explained in detail later). This localization eﬀect
is expected to prevent the degradation of classiﬁcation performance. Through extensive
experiments on real-world image classiﬁcation and automatic audio tagging tasks, wedemonstrate that the proposed modiﬁcation to LSPC signiﬁcantly contributes to improving classiﬁcation accuracy, while maintaining the computational advantage of the original
LSPC algorithm.

2

Least-Squares Approach to Probabilistic Classification

In this section, we review the least-squares probabilistic classifier 1 (LSPC) [1].

2.1

Problem Formulation

Suppose we are given n paired samples of input x ∈ X ⊂ Rd and its label y ∈ {1, . . . , c}(c denotes the number of classes):{(xi , yi )}ni=1 ,1More precisely, the LSPC method we are reviewing here was referred to as ‘LSPC(full)’ in the originalLSPC paper [1], where ‘full’ means that all kernels are used for learning (cf. Eq.(2)). On the other hand,a computationally more eﬃcient variant of LSPC where irrelevant kernels are removed was also proposedin the original paper. However, since the range of application of this model simpliﬁcation idea is limited
to localized kernels such as Gaussian kernels, we decided to adopt the more general ‘LSPC(full)’ methodin this paper. We note that the results we present in this paper can also be applied to the simpliﬁed
LSPC method.

Improving the Accuracy of Least-Squares Probabilistic Classifiers

3

which are independently drawn from a joint probability distribution with densityp(x, y). Our goal is to estimate the class-posterior probability p(y|x) from the samples {(xi , yi )}ni=1 . The class-posterior probability allows us to classify a test sample x tothe class yb with conﬁdence p(by |x):yb := argmax p(y|x).
yLet us denote the marginal density of x by p(x). Then the class-posterior probability canbe expressed asp(y|x) =p(x, y),p(x)(1)where we assume p(x) > 0 for all x ∈ X . This density-ratio expression is utilized in thederivation of LSPC.

2.2

Least-Squares Probabilistic Classifier

Let us model the class-posterior probability p(y|x) for class y by the following linear
model:
n∑αy,l ϕl (x) = α⊤y ϕ(x),
l=1⊤

where denotes the transpose of a matrix or a vector and αy = (αy,1 , . . . , αy,n )⊤ areparameters to be learned from training samples. The basis function is written asϕ(x) = (k(x, x1 ), . . . , k(x, xn ))⊤ ,where(2)()∥x − x′ ∥2k(x, x ) = exp −2σ 2′is the Gaussian kernel with width σ.
Then, an empirical and regularized solution of LSPC is given as][1 ⊤c⊤⊤b αy + λα αy ,e y := argmin αy Hαy − hαyy2αy(3)where λα⊤y αy for λ > 0 is a regularizer, andn∑c := 1H
ϕ(xi )ϕ(xi )⊤ ,n i=1∑b y := 1hϕ(xi ).
n i:y =yi

Since Eq.(3) is an unconstrained quadratic minimization problem, the global optimale y can be obtained assolution αb y,c + λIn )−1 he y = (HαImproving the Accuracy of Least-Squares Probabilistic Classifiers

40.25
TrueLSPC−new
LSPCLSPC′p(y = 1|x)=0.5
Class1Class2Class−Posterior Probability

1.2
1
0.8

0.2
0.15
0.1

0.6

0.05

0.4
0.2

00

−0.05

−0.2
−505(a) p(y = 1|x) as a function of x.

−0.1
0100200300

400500e 1 as a function of sample index l.
(b) αFigure 1: (a): True class-posterior probability, and class-posterior probabilities estimatedby LSPC-new (negative outputs are rounded up to zero), LSPC (negative parameters arerounded up to zero), and LSPC’ (negative parameters are used as they are). (b): Thee 1 , where the training samples were sorted as x1 ≤ x2 ≤ · · · ≤ x500 .
parameter values of α
where In denotes the n-dimensional identity matrix.
ey
By deﬁnition, the class-posterior probability should be non-negative. However, αobtained above can take negative values. In order to assure the learned probabilities toe y are rounded up to zero as follows:
be non-negative, the negative elements in α
b y := max(0n , αe y ),αwhere 0n denotes the n-dimensional vector with all zeros, and the ‘max’ operation forvectors is applied in an element-wise manner.
Finally, given a test input point, an estimator of the class-posterior probability is
obtained via normalization asb⊤
αy ϕ(x).
pb(y|x) = ∑cb⊤y ′ ϕ(x)y ′ =1 α3(4)Improving Accuracy of LSPCe y are usually
In the original LSPC paper, it was claimed that the learned parameters α
non-negative when the basis functions and the regularization parameter value are chosen
appropriately, e.g., by cross-validation. In this section, we point out that the above claim
is not always true through a numerical example, and illustrate that rounding up negative
parameters can actually have strong inﬂuence on the learned class-posterior probabilities.
Then we describe a simple alternative scheme for assuring the learned probabilities to benon-negative, and illustrate its usefulness.

Improving the Accuracy of Least-Squares Probabilistic Classifiers

3.1

5

Influence of Rounding-Up Negative Parameters

First, we illustrate how the class-posterior probabilities are learned by LSPC, and investigate the inﬂuence of rounding-up negative model parameters.
Let us consider a one-dimensional binary classiﬁcation problem (i.e., d = 1 and c =2). We independently draw samples in each class from the following class-conditional
densities:p(x|y = 1) = N (x; 0, 1) ,11p(x|y = 2) = N (x; −2, 1) + N (x; 2, 1) ,22
where N (x; µ, τ 2 ) denotes the Gaussian density with mean µ and variance τ 2 . We used
250 training samples per class (500 samples in total), and 250 test samples per class (500samples in total). The kernel width σ and regularization parameter λ in LSPC werechosen based on 2-fold cross-validation.
e y (i.e,. without theLet pe(y|x) be an estimator of the class-posterior probability for αrounding-up operation), which we refer to as LSPC’:e⊤αy ϕ(x).
e⊤y ′ ϕ(x)y ′ =1 αpe(y|x) = ∑c(5)Note that the output of LSPC’ is not necessarily a probability since it can be negativeor larger than one. Figure 1(a) shows the true class-posterior probability and the classposterior probabilities estimated by LSPC (4) and LSPC’ (5). The graph shows that,without the rounding-up operation, the class-posterior probability estimates take negativevalues around x ∈ (−5, −3) and x ∈ (3, 5) in Figure 1(a). On the other hand, the LSPC
solution always takes non-negative values thanks to the rounding-up operation. However,the LSPC estimate of the class-posterior probability are signiﬁcantly diﬀerent from thetrue class-posterior probability.
In order to investigate the eﬀect of rounding-up negative parameters to zero in moree 1 in Figure 1(b), where the training samples were sorted
detail, we plotted the values of α
as x1 ≤ x2 ≤ · · · ≤ x500 . The graph shows that many parameters actually took negativevalues, even though the estimate of class-posterior probabilities take negative values onlylocally. This shows that, rounding-up negative parameters to zero can actually have astrong inﬂuence on the learned class-posterior probability even when negative values aretaken only locally.

3.2

Rounding-Up Negative Outputs

In order to overcome the above drawback, we propose to locally modify the solution asfollows:{1e⊤max(0, αx)) if Z > 0,y ϕ(ee) = Z1p(y|x = x(6)otherwise,cImproving the Accuracy of Least-Squares Probabilistic Classifiers

6∑e⊤where Z = cy′ =1 max(0, αx)). Below, we refer to this method as ‘LSPC-new’.
y ′ ϕ(eFigure 1(a) also includes the class-posterior probabilities estimated by LSPC-new.
As shown in the graph, the class-posterior probability estimated by LSPC-new and thetrue-class posterior probability have almost the same proﬁle. On the other hand, theclass-posterior probability obtained by the original LSPC has been strongly inﬂuenced byrounding-up negative parameters to zero.

4Experiments

In this section, we compare the performance of LSPC-new, LSPC, and kernel logistic
regression (KLR) on a real-world image classiﬁcation task using the PASCAL VisualObject Classes (VOC) 2010 dataset [4] and a real-world automatic audio-tagging taskusing te data collected by the Freesound project [5]. All tuning parameters (i.e., the kernel
width σ and regularization parameter λ) were chosen based on 2-fold cross-validation.
RWe used the MATLAB⃝
implementation of KLR included in the ‘minFunc’ package [6].
Comparison is carried out in terms of classiﬁcation performance and CPU computation
time required for training each classiﬁer after the Gaussian width and the regularization
parameter are chosen by cross-validation.

4.1

PASCAL VOC 2010 Datasets

The VOC 2010 dataset consists of 20 binary classiﬁcation tasks of identifying the existenceof a person, aeroplane, etc. in each image. The total number of images in the dataset is11319, and we used 1000 randomly chosen images for training and the rest for testing.
We ﬁrst extracted visual features from each image with the Speed Up Robust Features (SURF) algorithm [7]. We then ran the k-means clustering algorithm [8] in theSURF space and obtained 500 cluster centers as visual words. Then, we computed a
500-dimensional bag-of-feature vector by counting the number of visual words in eachimage.
When evaluating the image classiﬁcation performance, it is important to take into
account both the false positive rate and true positive rate. Here we adopted the area
under the ROC curve (AUC) as our error metric [9]. We randomly sampled the training
and test data 50 times, and computed the means and standard deviations of the AUC.
Table 1 shows the mean AUC values (with standard deviations in brackets) over 50
trials. The best method in terms of the mean AUC and comparable methods according
to the t-test at the signiﬁcance level 5% are speciﬁed by bold face. The results showedthat LSPC-new outperforms LSPC for all tasks and is slightly more accurate than KLR
with much less computational cost.

4.2

Freesound Datasets

The Freesound dataset [5] consists of various audio ﬁles annotated with word tags suchas ‘people’, ‘noisy’, and ‘restaurant’. Note that such tags are not exclusive, meaning that

Improving the Accuracy of Least-Squares Probabilistic Classifiers

7Table 1: Mean AUC values (with standard deviations in brackets) over 50 trials for thePASCAL VOC dataset. The best method in terms of the mean AUC and comparable
methods according to the t-test at the signiﬁcance level 5% are speciﬁed by bold face.
Datasets
Aeroplane
BicycleBirdBoatBottleBusCarCat
Chair
Cow
Diningtable
Dog
Horse
Motorbike
PersonPottedplant
Sheep
Sofa
Train
Tvmonitor
Average
Train time [sec]LSPC-new82.6 (1.0)
77.7 (1.7)
68.7 (2.0)
74.4 (2.0)
65.4 (1.8)
85.4 (1.4)
73.0 (0.8)
73.6 (1.4)
71.0 (1.0)
71.7 (3.2)
75.0 (1.6)
69.6 (1.0)
64.4 (2.5)
77.0 (1.7)
67.6 (0.9)
66.2 (2.6)
77.8 (1.6)
67.4 (2.7)
79.2 (1.3)
76.7 (2.2)
73.2—
0.7—

LSPC
78.8 (1.3)
60.0(12.4)
49.1 (5.7)
62.1 (4.1)
63.0 (2.0)
80.3 (2.6)
69.0 (2.6)
68.6 (5.0)
64.8 (2.0)
53.5 (9.0)
69.1 (2.4)
58.6 (6.0)
54.6 (4.4)
73.2 (2.5)
65.9 (1.2)
58.0 (4.6)
57.6(12.9)
66.1 (1.7)
67.0 (7.7)
70.1 (2.4)
64.5 —
0.7—

KLR
83.0 (1.3)
76.6 (3.4)
70.8 (2.2)
72.8 (2.6)
62.1 (4.3)
85.6 (1.4)
72.1 (1.2)
74.1 (1.7)
70.5 (1.0)
69.3 (3.6)
71.4 (2.7)
69.4 (1.8)
61.2 (3.2)
75.9 (3.3)
67.0 (0.8)
61.9 (3.2)
74.0 (3.8)
65.4 (4.6)
78.4 (3.0)
76.6 (2.3)
71.9
—
24.6
—

each audio ﬁle can have multiple tags.
We extracted audio ﬁles from among all ﬁles in the dataset containing any of the 50
most used tags and between 3-60 seconds in length. We then used 180 randomly selecteduncompressed audio ﬁles with a sampling rate greater than 44.1kHz as our training set,and 1500 randomly selected audio ﬁles which were stored in a compressed format fortesting. We used the hidden Markov kernel [10], instead of the simple Gaussian kernel
due to the sequential nature of audio ﬁles. We repeat the audio-tagging experiment 50times, by changing the random seed.
We computed the AUC value over all 1500 test samples for each tag, and this wasaveraged over all 50 trials and all 50 tags. Table 2 summarizes the performance of LSPCnew, LSPC, and KLR. The results show that LSPC-new is more accurate than LSPCwith comparable computation time, and LSPC-new provides comparable classiﬁcation
performance to KLR with signiﬁcantly less computation time.

Improving the Accuracy of Least-Squares Probabilistic Classifiers

8Table 2: Mean AUC values (with standard deviations in brackets) over all audio ﬁles for
the Freesound dataset.
AUC
Train time [sec]5LSPC-new70.1 (9.6)
0.005

LSPC
64.4 (9.5)
0.005

KLR
66.7 (10.3)
0.612

Conclusions

Least-squares probabilistic classifier (LSPC) has been demonstrated to be acomputationally-eﬃcient alternative to kernel logistic regression (KLR). However, since
LSPC involves a post-processing step of rounding-up negative parameters to zero, its performance can be degraded if many parameters take negative values. In this paper, weproposed not to round-up negative parameters, but to directly round-up negative outputs of LSPC. This localizes the inﬂuence of the rounding-up operation on the learnedclass-posterior probabilities. Through extensive experiments including real-world image
classiﬁcation and audio tagging tasks, we showed that the proposed modiﬁcation signiﬁcantly improves classiﬁcation accuracy, while the computational advantage of LSPC
remains unchanged.

Acknowledgement
MY acknowledges the JST PRESTO program for ﬁnancial support, and MS acknowledges
SCAT, AOARD, and the JST PRESTO program for ﬁnancial support.

References[1] M. Sugiyama, “Superfast-trainable multi-class probabilistic classiﬁer by least-squares
posterior ﬁtting,” IEICE Transactions on Information and Systems, vol. E93-D,
no. 10, pp. 2690–2701, 2010.
[2] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning:DataMining, Inference, and Prediction. New York: Springer, 2001.
[3] T. Minka, “A comparison of numerical optimizers for logistic regression,” MicrosoftResearch, Tech. Rep., 2007.
[4] M. Everingham, L. V. Gool, C. K. I. Williams, J. Winn, and A. Zisserman, “The PASCAL Visual Object Classes Challenge 2010 (VOC2010) Results,” http://www.pascalnetwork.org/challenges/VOC/voc2010/workshop/index.html.
[5] “Freesound,” http://www.freesound.org.
[6] “minFunc,” http://people.cs.ubc.ca/˜chmidtm/Software/ minFunc.html.

Improving the Accuracy of Least-Squares Probabilistic Classifiers

9[7] H. Bay, A. Ess, T. Tuytelaars, and L. V. Gool, “Surf: Speeded up robust features,”
Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346–359, 2008.
[8] C. M. Bishop, Pattern recognition and machine learning. New York: Springer-Verlag,2006.
[9] A. P. Bradley, “The use of the area under the roc curve in the evaluation of machinelearning algorithms,” Pattern Recognition, vol. 30, pp. 1145–1159, 1997.
[10] G. Wichern, J. Xue, H. Thornburg, B. Mechtley, and A. Spanias, “Segmentation,indexing and retrieval of environmental and natural sounds,” IEEE Transactions on
Audio, Speech and Language Processing, vol. 18, no. 3, pp. 688–707, 2010.