The Projectron: a Bounded Kernel-Based Perceptron

Francesco Orabona
Joseph Keshet
Barbara Caputo
IDIAP Research Institute, Centre du Parc, CH-1920 Martigny, Switzerland
Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne, Switzerland

Abstract
We present a discriminative online algorithmwith a bounded memory growth, which isbased on the kernel-based Perceptron. Generally, the required memory of the kernelbased Perceptron for storing the online hypothesis is not bounded. Previous work
has been focused on discarding part ofthe instances in order to keep the memory
bounded. In the proposed algorithm the instances are not discarded, but projected onto
the space spanned by the previous online hypothesis. We derive a relative mistake boundand compare our algorithm both analyticallyand empirically to the state-of-the-art Forgetron algorithm (Dekel et al, 2007). The
first variant of our algorithm, called Projectron, outperforms the Forgetron. The second variant, called Projectron++, outperforms even the Perceptron.

1. Introduction
One of the most important aspects of online learning
methods is their ability to work in an open-ended fashion. Autonomous agents, for example, need to learn
continuously from their surroundings, to adapt to theenvironment and maintain satisfactory performances.
A recent stream of work on artificial cognitive systems
have signaled the need for life-long learning methods
and the promise of discriminative classifiers for thistask (Orabona et al., 2007, and references therein).
Kernel-based discriminative online algorithms havebeen shown to perform very well on binary classification problems (see for example (Kivinen et al., 2004;
Crammer et al., 2006)). Most of them can be seen as
belonging to the Perceptron algorithm family. They
Appearing in Proceedings of the 25 th International Conference on Machine Learning, Helsinki, Finland, 2008. Copyright 2008 by the author(s)/owner(s).

forabona@idiap.ch
jkeshet@idiap.ch
bcaputo@idiap.ch

construct their classification function incrementally,
keeping a subset of the instances called support set.
Each time an instance is misclassified it is added tothe support set, and the classification function is defined as a kernel combination of the observations inthis set. It is clear that if the problem is not linearly
separable, they will never stop updating the classification function. This leads eventually to a memory
explosion, and it concretely limits the usage of thesemethods for all those applications where data must be
acquired continuously in time.
Several authors tried in the past to address this problem, mainly by bounding a priori the memory requirements. The first algorithm to overcome the unlimited
growth of the support set was proposed by Crammer etal. (2003). The algorithm was then refined by Weston
et al. (2005). The idea of the algorithm was to discard
a vector of the solution, once the maximum dimension
has been reached. The strategy was purely heuristic
and no mistake bounds were given. A similar strategy
has been used also in NORMA (Kivinen et al., 2004)
and SILK (Cheng et al., 2007). The very first online
algorithm to have a fixed memory “budget” and at thesame time to have a relative mistake bound has been
the Forgetron (Dekel et al., 2007). A stochastic algorithm that on average achieves similar performances,and with a similar mistake bound has been proposed
by Cesa-Bianchi et al. (2006).
In this paper we take a different route. We modify
the Perceptron algorithm so that the number of stored
samples is always bounded. Instead of fixing a priori
the maximum dimension of the solution, we introduce
a parameter that can be tuned by the user, to tradeaccuracy for sparseness, depending on the needs of thetask at hand. We call the algorithm, that constitutes
the first contribution of this paper, Projectron. The
Projectron is an online, Perceptron-like method thatis bounded in space and in time complexity. We derivefor it a mistake bound, and we show experimentallythat it outperforms consistently the Forgetron algorithm. The second contribution of this paper is theThe Projectron: a Bounded Kernel-Based Perceptron

derivation of a second algorithm, that we call Projectron++. It achieves better performances than the Perceptron, retaining all the advantage of the Projectron
listed above. Note that this is opposite to previous
budget online learning algorithms, delivering performances at most as good as the original Perceptron.
The rest of the paper is organized as follows: in Section
2 we state the problem and we introduce the necessary
background theory. Section 3 introduces the Projectron, Section 4 derives its properties and Section 4.1
derives the Projectron++. We report experiments in
Section 5, and we conclude the paper with an overall
discussion.

Algorithm 1 Perceptron Algorithm
Initialize: S0 = ∅, f0 = 0
for t = 1, 2, . . . , T do
Receive new instance xt
Predict ŷt = sign(ft−1 (xt ))Receive label yt
if yt 6= ŷt thenft = ft−1 + yt k(xt , ·)St = St−1 ∪ {t}else
ft = ft−1
St = St−1
end ifend for

2. Problem Setting
The basis of our study is the well known Perceptron
algorithm (Rosenblatt, 1958). The Perceptron algorithm learns the mapping f : X → R based on a set ofexamples S = {(x1 , y1 ), . . . , (xT , yT )}, where xt ∈ X
is called an instance and yt ∈ {−1, +1} is called a label.
We denote the prediction of Perceptron as sign(f (x))
and we interpret |f (x)| as the confidence in the prediction. We call the output f of the Perceptron algorithma hypothesis, and we denote the set of all attainable
hypotheses by H. In this paper we assume that H isa Reproducing Kernel Hilbert Space (RKHS) with apositive definite kernel function k : X × X → R implementing the inner product h·, ·i. The inner productis defined so that it satisfies the reproducing property,hk(x, ·), f (·)i = f (x)The Perceptron algorithm is an online algorithm, inwhich the learning takes place in rounds. At eachround a new hypothesis function is estimated, basedon the previous one. We denote the hypothesis estimated after the t-th round by ft . The algorithm starts
with the zero hypothesis f0 = 0. On each round t, an
instance xt ∈ X is presented to the algorithm. The
algorithm predicts a label ŷt ∈ {−1, +1} by using thecurrent function, ŷt = sign(ft (xt )). Then, the correct label yt is revealed. If the prediction ŷt differsfrom the correct label yt , it updates the hypothesis
ft = ft−1 + yt k(xt , ·), otherwise the hypothesis is left
intact, ft = ft−1 . Practically, the hypothesis ft can be
written as a kernel expansion (Schölkopf et al., 2000),X
αi k(xi , x) ,(1)
ft (x) =i∈St

where αi = yi and St is defined to be the set of instanceindices for which an update of the hypothesis occurred,i.e., St = {0 ≤ i ≤ t | ŷi 6= yi }. The set St is called the
support set. The Perceptron algorithm is summarizedin Algorithm 1.

Although the Perceptron is a very simple algorithm, it
is considered to produce very good results. Our goal
is to derive and analyze a new algorithm which attains
the same results as the Perceptron but with a minimal
size of support set. In the next section we present our
Projectron algorithm.

3. The Projectron Algorithm
Let us first consider a finite dimensional RKHS H induced by a kernel such as the polynomial kernel. Since
H is finite dimensional, there is a finite number of linearly independent hypotheses in this space. Hence,
any hypothesis in this space can be expressed using afinite number of examples. We can modify the Perceptron algorithm to use only one set of independent
instances as follows. On each round the algorithm receives an instance and predicts its label. On a prediction mistake, if the instancecan be spanned by the
Pt−1
support set, namely, xt = i=1 di xi , it is not added
to the support set. Instead, the coefficients {αi } in the
expansion Eq. (1) are not merely yi , i ∈ St−1 , but they
are changed to reflect the addition of this instance tothe hypothesis, that is, αi = yi + yt di , 1 ≤ i ≤ t − 1. If
the instance and the support set are linearly independent, the instance is added to the set with αt = yt as
before. This technique reduces the size of the support
set without changing the hypothesis in any way, andwas used by Downs at al. (2001) to simplify Support
Vector Machine solutions.
Let us consider now the more elaborate case of an infinite dimensional RKHS H induced by kernels suchas the Gaussian kernel. In this case, it is not possible to find a finite number of linearly independentvectors which span the whole space, and hence there
is no guarantee that the hypothesis can be expressedby a finite number of instances. However, we can approximate the concept of linear independence with a

The Projectron: a Bounded Kernel-Based Perceptron

Algorithm 2 Projectron Algorithm
Initialize: S0 = ∅, f0 = 0
for t = 1, 2, . . . , T do
Receive new instance xt
Predict ŷt = sign(ft−1 (xt ))Receive label yt
if yt 6= ŷt thenft′ = ft−1 + yt k(xt , ·)ft′′ = ft′ projected onto the space St−1
δt = ft′′ − ft′
if kδt k ≤ η thenft = ft′′
St = St−1
else
ft = ft′
St = St−1 ∪ {t}end ifelse
ft = ft−1
St = St−1
end ifend forfinite number of vectors (Csató & Opper, 2001; Engel et al., 2002; Orabona et al., 2007). In particularassume that at round t of the algorithm there is a prediction mistake and the mistaken instance xt should
be added to the support set. Before adding the instance to the support, we construct two hypotheses:
a temporal hypothesis ft′ using the function k(xt , ·),that is, ft′ = ft−1 + yt k(xt , ·), and a projected hypothesis ft′′ , which is the projection of ft′ onto the spacespanned by St−1 . That is, the projected hypothesis isa hypothesis from the support set St−1 which is theclosest to the temporal hypothesis. Denote by δt the
distance between the hypotheses δt = ft′′ − ft′ . If thenorm of distance kδt k is below some threshold η, we
use the projected hypothesis as our next hypothesis,
i.e., ft = ft′′ , otherwise we use the temporal hypothesis
as our next hypothesis, i.e., ft = ft′ . As we show in thenext section, this strategy assures that the maximum
size of the support set is always finite, regardless of thedimension of the RKHS H. Guided by these considerations we can design a new Perceptron-like algorithm
that projects the solution onto the space spanned by
the previous support vectors whenever possible. We
call this algorithm Projectron. The algorithm is given
in Algorithm 2.

when the kernel induces a finite dimensional RKHS
H. In case η is greater than zero we trade precision
for sparseness. Moreover, as shown in the next section, this implies a bounded algorithmic complexity,
namely, the memory and time requirements for eachstep are bounded. We will also derive mistake bounds
to analyze the effect of η on the classification accuracy.
We now consider the problem of deriving the projected
hypothesis ft′′ in a Hilbert space H, induced by a kernel
function k(·, ·). Denote by Pt−1 ft the projection offt ∈ H onto the subspace Ht−1 ⊂ H spanned by theset St−1 . The projected hypothesis ft′′ is defined asft′′ = Pt−1 ft′ . Expanding ft′ we haveft′′ = Pt−1 ft′ = Pt−1 (ft−1 + yt k(xt , ·)) .

(2)

2
The projection is an idempotent (Pt−1= Pt−1 ) andlinear operator, hence,ft′′ = ft−1 + yt Pt−1 k(xt , ·) .

(3)

Recall that δt = ft′′ − ft′ . Substitute ft′′ from Eq. (3)and ft′ we haveδt = ft′′ − ft′ = yt Pt−1 k(xt , ·) − yt k(xt , ·) .

(4)

Recall that the projection of ft′ ∈ H onto a subspace Ht−1 ⊂ H
P is the hypothesis in Ht−1 closest toft′ . Hence, let j∈St−1 dj k(xj , ·) be an hypothesis in
Ht−1 , where (d1 , . . . , dt−1 ) is a set of coefficients. The
closest hypothesis is the one for which22kδt k =Xmin

(d1 ,...,dt−1 )dj k(xj , ·) − k(xt , ·).

j∈St−1(5)
Expanding Eq. (5) we get
2kδt k =min(d1 ,...,dt−1 )

−2



X

X

dj di k(xj , xi )i,j∈St−1j∈St−1
dj k(xj , xt ) + k(xt , xt ) .

(6)

Define Kt−1 to be the matrix generated by the instances in the support set St−1 , that is, {Kt−1 }i,j =k(xi , xj ) for every i, j ∈ St−1 . Define kt to be thevector whose i-th element is kti = k(xi , xt ). We havekδt k2 = min dT Kt−1 d − 2dT kt + k(xt , xt ) , (7)dIn our algorithm the parameter η plays an importantrole. If η is equal to zero, we obtain exactly the same
solution of the Perceptron algorithm. In this case,however, the Projectron solution can still be sparser
when some of the instances are linearly dependent or

where d = (d1 , . . . , dt−1 )T . Solving Eq. (7), that is,applying the extremum conditions with respect to d,
we obtaind⋆ = K−1(8)
t−1 ktThe Projectron: a Bounded Kernel-Based Perceptronand, by substituting Eq. (8) into Eq. (7),kδt k2 = k(xt , xt ) − kTt d⋆ .

(9)Furthermore, substituting Eq. (8) into Eq. (3) we getXd⋆j k(xj , ·) .
ft′′ = ft−1 + yt
(10)

The next theorem provides a mistake bound. The
main idea is to bound the maximum number of mistakes of the algorithm, relatively to the best hypothesisg ∈ H chosen in hindsight. Let us define D1 as
D1 =In order to make the computation more tractable, we
introduce an efficient method to calculate the matrix
inversion K−1
iteratively. This method was first int
troduced in (Cauwenberghs & Poggio, 2000), and wegive it here only for completeness. We would like tonote in passing that the matrix Kt−1 can be safely inverted since, by incremental construction, it is always
full-rank. After the addition of a new sample, K−1tbecomes


0
 ⋆ 

.. 
 ⋆T

−1
1
d


K
.
t−1
d
−1
+

2
−1
kδ
k


t
0
0

···

0 0

(11)
where d⋆ and kδt k2 are already evaluated during theprevious steps of the algorithm. Thanks to this incremental evaluation, the time complexity of the linear
independence check is O(|St−1 |2 ), as one can easily
see from Eq. (8).

4. Analysis
In this section we analyze the performance of the Projectron algorithm in the usual framework of online
learning with a competitor. First, we present a theorem which states that the size of the support set isbounded.
Theorem 1. Let k : X × X → R a continuous Mercer
kernel, with X a compact subset of a Banach space.
Then, for any training sequence (xi , yi ), i = 1, · · · , ∞and for any η > 0, the size of the support set of the
Projectron algorithm is finite.
The proof of this theorem goes along the same lines
as the proof of Theorem 3.1 in (Engel et al., 2002),
and we omit it for brevity. Note that this theorem
guarantees that the size of the support set is bounded,however it does not state that the size of the support
set is fixed or can be estimated before training.

ℓ(g(xt ), yt )

(12)

t=1

j∈St−1

We have shown how to calculate both the distance δt
and the projected hypothesis ft′′ . In summary, one
needs to compute d⋆ according to Eq. (8), plug theresult either into Eq. (9) and obtain δt or into Eq. (10)and obtain the projected hypothesis.

TX

where ℓ(g(xt ), yt ) is the hinge loss suffered by the function g on the example (xt , yt ), that is, max{0, 1 −yt g(xt )}. With these definitions we can state the following bound for the Projectron Algorithm.
Theorem 2. Let (x1 , y1 ), · · · , (xT , yT ) be a sequenceof instance-label pairs where xt ∈ X , yt ∈ {−1, +1},
and k(xt , xt ) ≤ R for all t. Let g be an arbitrary function in H. Assume that the Projectron algorithm is2
run with 0 ≤ η < 2−R
2kgk . Then the number of prediction mistakes the Projectron makes on the sequence is
at most2
kgk + 2D1
2 − R2 − 2ηkgk
The proof of this theorem is based on the following
lemma.
Lemma 1. Let (x, y) be an example, with x ∈ X andy ∈ {+1, −1}. Denote by f an hypothesis in H, suchthat yf (x) < 1. Let f ′ = f + τ yq(·), where q(·) ∈ H.
Then the following bound holds for any τ ≥ 0:
kf − gk2 − kf ′ − gk2 ≥ τ 2ℓ(f (x), y) − 2ℓ(g(x), y)−τ kq(·)k2 −2hf, q(·)−k(x, ·)i−2kq(·)−k(x, ·)k·kgk
Proof.
kf − gk2 − kf ′ − gk2 = 2τ yhg − f, q(·)i − τ 2 kq(·)k2= 2τ y(g(x) − f (x)) − τ 2 kq(·)k2+ 2τ yhg − f, q(·) − k(x, ·)i≥ τ 2ℓ(f (x), y) − 2ℓ(g(x), y) − τ kq(·)k2− 2yhf, q(·) − k(x, ·)i − 2kq(·) − k(x, ·)k · kgk
With this bound we are ready to prove Thm. 2.
Proof. Define the relative progress in each round as∆t = kft−1 − gk2 − kft − gk2 . We bound the progressfrom above and below. On rounds in which there isno mistake ∆t is 0. On rounds in which there is a
mistake there are two possible updates: either ft =ft−1 + yt Pt−1 k(xt , ·) or ft = ft−1 + yt k(xt , ·). In thefollowing we bound the progress from below, when the
update is of the former type (the same bound can beobtained for the latter type as well, but the derivationis omitted). In particular we set q(·) = Pt−1 k(xt , ·) inThe Projectron: a Bounded Kernel-Based Perceptron

Lemma 1 and use δt = yt Pt−1 k(xt , ·) − yt k(xt , ·) from
Eq. (4)∆t = kft−1 − gk2 − kft − gk2≥ τt 2ℓ(ft−1 (xt ), yt ) − 2ℓ(g(xt ), yt )− τt kPt−1 k(xt , ·)k2 − 2hft−1 , δt i − 2kδt kkgk .

Note that hft−1 , δt i = 0, because ft−1 belongs to
the space spanned by the functions indexed by St−1 .
Moreover, on every projection update kδt k ≤ η andusing the theorem assumption kPt−1 k(xt , ·)k ≤ R, wethen have∆t ≥ τt 2 (ℓ(ft−1 (xt ), yt ) − ℓ(g(xt ), yt ))−τt R2 −2ηkgk .
We can further bound ∆t by noting that on every prediction mistake ℓ(ft−1 (xt ), yt ) ≥ 1. Overall we havekft−1 − gk2 − kft − gk2 ≥τt 2 (1 − ℓ(g(xt ), yt )) − τt R2 − 2ηkgk .
We sum over t both sides. Let τt be an indicator function for a mistake on the t-th round, that is, τt is 1 if
there is a mistake on round t and 0 otherwise, hence
it can be upper bounded by 1. The left hand side ofthe equation is a telescopic sum, hence it collapses to
kf0 − gk2 − kfT − gk2 , which can be upper bounded by
kgk2 , using the fact that f0 = 0 and that kfT − gk2 is
non-negative. Finally, we have
kgk2 + 2D1 ≥ M 2 − R2 − 2ηkgk ,where M is the number of mistakes.

To compare with other similar algorithms it can be
useful to change the formulation of the algorithm inorder to use the maximum norm of g as parameter
instead of η. Hence we can fix an upper bound, U ,on kgk and then we set η to have a positive progress.
Specifically, on each round we set η to be
1 
2ℓ(ft−1 (xt ), yt ) − kPt−1 k(xt , ·)k2 − 0.5 . (13)2U
The next corollary, based on Thm. 2, provides a mistake bounds in terms of U rather than η.
Corollary 1. Let (x1 , y1 ), · · · , (xT , yT ) be a sequenceof instance-label pairs where xt ∈ X , yt ∈ {−1, +1},
and k(xt , xt ) ≤ 1 for all t. Let g be an arbitrary function in H, whose norm kgk is bounded by U . Assume
that the Projectron algorithm is run with a parameter
η, which is set in each round according to Eq. (13).
Then, the number of prediction mistakes the Projectron makes on the sequence is at most2

2kgk + 4D1 .

Notice that the bound in Corollary 1 is similar to Thm.
5.1 in (Dekel et al., 2007) of the Forgetron algorithm.
The difference is in the assumptions made: in the Forgetron, the size of the support set is guaranteed to beless than a fixed size B that depends on U , while in the
Projectron we choose the value of η or, equivalently, U ,and there is no guarantee on the exact size of the support set. However, the experimental results suggest
that, with the same assumptions used in the derivation of the Forgetron bound, the Projectron needs asmaller support set and produces less mistakes.
It is also possible to give yet another bound by slightly
changing the proof of Thm. 2. This theorem is a worstcase mistake bound for the Projectron algorithm. We
state it here without the proof, leaving it for a long
version of this paper.
Theorem 3. Let (x1 , y1 ), · · · , (xT , yT ) be a sequenceof instance-label pairs where xt ∈ X , yt ∈ {−1, +1},
and k(xt , xt ) ≤ R for all t. Let g an arbitrary functionin H. Assume that the Projectron algorithm is run
1. Then, M , the number of prediction
with 0 ≤ η < kgk
mistakes the Projectron makes on the sequence is at
most
q

2
2
Rkgk + R2 kgk + 4D1

2(1 − ηkgk)
The last theorem suggests that the performance of
the Projectron are slightly worse than the Perceptron (Shalev-Shwartz & Singer, 2005). Specificallythe degradation in the performance of Projectron compared to the Perceptron are related to 1/(1−ηkgk)2 . In
the next subsection we present a variant to the Projectron algorithm, which attains even better performance.
4.1. Going Beyond the Perceptron
The proof of Thm. 2 and Corollary 1 direct us how
to improve the Projectron algorithm to go beyond theperformance of the Perceptron algorithm, while maintaining a bounded support set.
Let us start from the algorithm in Corollary 1. Wechange it so an update takes place not only if there isa prediction mistake, but also when the prediction iscorrect with a low confidence. We indicate this lattercase as a margin error, that is, 0 < yt ft−1 (xt ) < 1.
This strategy improves the classification rate but also
increases the size of the support set (Crammer et al.,2006). A possible solution to this obstacle is not to
update every round a margin error occurs, but also
when the new instance can be projected onto the support set. Hence, the update on margin error rounds

The Projectron: a Bounded Kernel-Based Perceptron

would be in the general form
ft = ft−1 + yt τt Pt−1 k(xt , ·) ,(14)

with 0 < τt ≤ 1. The last constraint comes from proofsof Thm. 2 and Corollary 1 in which we upper boundτt by 1. Note that setting τt to 0 is equivalent to leave
the hypothesis unchanged. The bound in Corollary 1
becomesX2
M ≤ 2(kgk + 2D1 −βt ) ,(15){t:0<yt ft−1 (xt )<1}

where βt bounds the progress made on margin error
round t. In particular it is easy to see from Lemma 1
that βt isτt 2ℓ(ft−1 (xt ), yt )−τt kPt−1 k(xt ,·)k2 −2U kδt k , (16)for 0 < τt ≤ 1, and is 0 when there is no update. Whenever βt is non-negative the worst-casenumber of mistakes in Eq. (15) decreases, hopefully
along with the classification error rate of the algorithm. Hence, we determine the optimal τt which
maximizes βt . In particular, the expression of βt
in Eq. (16) is quadratic in τt , and is maximized forτt = ℓ(ft−1 (xt ), yt )/kPt−1 k(xt , ·)k2 . Constraining τt
to be less than or equal to 1, we have1
τt = min{ℓ(ft−1 (xt ), yt )/kPt−1 k(xt , ·)k2 , 1} .

(17)

In summary, at every round t with margin error we
calculate τt according to Eq. (17), and check that βt
is non-negative. If so we update the hypothesis using
Eq. (14), otherwise we leave it untouched.
With this modification we expect better performance,that is, fewer mistakes, but without any increase of the
support set size. We can even expect solutions with asmaller support set, since new instances can be added
to the support set only if misclassified, hence having
less mistakes should result in a smaller support set.
We name this variant Projectron++, and in the next
section we compare it to the original version.

5. Experimental Results
In this section we present experimental results that
demonstrate the effectiveness of the Projectron and
the Projectron++. We compare both algorithms to
the Perceptron and to the budget algorithms Forgetron (Dekel et al., 2007) and Randomized Budget
Perceptron (RBP) (Cesa-Bianchi et al., 2006). For theForgetron, we choose the state-of-the-art “self-tuned”
1

This update rule gives τt = 1 on rounds in which there
is a mistake.

variant, which outperforms its other variants. We also
use two other baseline algorithms: the first one is a
Perceptron algorithm which stops updating the solution once the support size has reached some limit, and
it is used to verify that the Projectron is better thanjust stop learning. We name it Stoptron. The secondbaseline algorithm is the PA-I variant of the PassiveAggressive learning algorithm (Crammer et al., 2006),
which gives an upper bound to the classification performance that Projectron++ can reach.
We tested the algorithms with two standard machinelearning datasets: Adults9 and Vehicle 2 and a synthetic dataset, all of them with more than 10000 samples. The synthetic dataset is built in the same way
as in (Dekel et al., 2007). It is composed with samples taken from two separate bi-dimensional Gaussian
distributions. The means of the positive and negative samples are (1, 1) and (−1, −1), respectively, while
the covariance matrix for both is diagonal matrix with
(0.2, 2) as its diagonal. Then the labels are flippedwith a probability of 0.1 to introduce noise.
All the experiments were performed over 5 different
permutations of the training set. All algorithms useda Gaussian kernel with σ 2 equals 25, 4, and 0.5 for
Adults9, Vehicle, and the synthetic datasets, respectively. The C parameter of the PA-I was set to 1,
to have an update similar to the Perceptron and Projectron. Due to the different nature of our algorithm
compared to the budget ones, we cannot select the support set size in hindsight. Hence, we compared themusing the proper conditions to obtain the same bounds.
That is, we selected the maximum support size B for
the Forgetron algorithm, which implies a maximum
value U , the norm of g, forp its bound to hold. In particular U is equal to 1/4 (B + 1)/ log (B + 1) (Dekel
et al., 2007), where B is the budget parameter thatsets the maximum size of the support set. We then selected the parameter η in the Projectron in each roundaccording to Eq. (13). Hence the final size of the Projectron solution will depend on U and on the particularclassification problem at hand. We have set B on eachdataset roughly to 1/2 and 1/4 of the size of the Perceptron support set, for a total of 6 experiments. Notethat Projectron can also be used without taking into
account the norm of the competitor and considering η
just as a parameter. In particular η should be set totrade accuracy for sparseness.
In Tables 1–3 we summarize the results of our experiments. The cumulative number of mistakes as percentage of the training size (mean ± std) and the size of the2
Downloadedfrom
http://www.sie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.

The Projectron: a Bounded Kernel-Based Perceptron
Table 1. Adult9 dataset, 32561 samples.
Algorithm% Mistakes
Size Support Set
Perceptron
20.99% ± 0.06
6835.6 ± 20.28
PA-I
18.11% ± 0.1012537 ± 36.2
B=1500
Projectron
20.95% ± 0.12
1094.6 ± 16.06
Projectron++ 20.04% ± 0.14
992.8 ± 9.73
Forgetron
21.90% ± 0.23
1500
RBP
22.05% ± 0.21
1500
Stoptron
22.73% ± 2.82
1500
B=3000
Projectron
20.97% ± 0.13
1499.6 ± 13.58
Projectron++ 20.16% ± 0.11
1364.2 ± 4.76
Forgetron
21.41% ± 0.13
3000
RBP
21.49% ± 0.11
3000
Stoptron
21.04% ± 1.54
3000

Table 2. Vehicle dataset, 78823 samples.
Algorithm% Mistakes
Size Support Set
Perceptron
19.58% ± 0.09
15432.0 ± 69.62
PA-I
15.27% ± 0.05
30131.4 ± 21.07
B=4000
Projectron
19.63% ± 0.08
3496.4 ± 18.39
Projectron++ 18.27% ± 0.06
3187.0 ± 13.64
Forgetron
20.40% ± 0.04
4000
RBP
20.32% ± 0.04
4000
Stoptron
19.49% ± 3.56
4000
B=8000
Projectron
19.62% ± 0.04
4668.2 ± 32.88
Projectron++ 18.53% ± 0.07
4309.6 ± 28.67
Forgetron
19.98% ± 0.06
8000
RBP
19.94% ± 0.06
8000
Stoptron
20.17% ± 2.03
8000

support set are reported. In all the experiments boththe Projectron and the Projectron++ outperform theForgetron and the RBP with a smaller support size.
Moreover, the Projectron++ always outperforms the
Projectron and has smaller support set. Due to its
theoretically derived formulation, it achieves better results even if being bounded, and it has better performance than the Perceptron. In particular it gets closer
to the classification rate of the PA-I, without paying
the price of a large support set. It is interesting to notethe performances of the Stoptron: it has an accuracy
close to the other bounded algorithms in average, butwith much bigger variance. This indicates that all theexamined strategies for bounded learning are always
better than the simple procedure to stop learning, atleast to have stable performances.

Table 3. Synthetic dataset, 10000 samples.
Algorithm% Mistakes
Size Support Set
Perceptron
18.80% ± 0.25
1880.0 ± 25.12
PA-I
12.58% ± 0.05
3986.8 ± 42.83
B=1000
Projectron
18.71% ± 0.14
108.6 ± 2.97
Projectron++ 14.09% ± 0.10
104.2 ± 2.39
Forgetron
18.96% ± 0.32
1000
RBP
18.86% ± 0.29
1000
Stoptron
17.49% ± 1.77
1000
B=500
Projectron
18.70% ± 0.21
98.6 ± 3.05
Projectron++ 14.23% ± 0.10
98.6 ± 2.30
Forgetron
19.20% ± 0.19
500
RBP
19.27% ± 0.20
500
Stoptron
21.96% ± 4.62
500

Last, we show the behavior of the algorithms over time.
In Fig. 1 we show the average online error rate, thatis, the total numbers of errors on the examples seen
as a function of the number of samples for all algorithms on the Adult9 dataset with B = 1500. Note
how the Projectron algorithm closely tracks the Perceptron. On the other hand the Forgetron and the
RBP stop improving after reaching the support set size
B, around 7500 samples. The growth of the support
set as a function of the number of samples is depicted
in Fig. 2. While for PA-I and Perceptron the growthis clearly linear, it is sub-linear for Projectron and for
the Projectron++ and they will reach a maximum size
and then they will stop growing (as stated in Thm. 1).
In Fig. 3 we show the average online error rate as afunction of the size of the support set. It is clear that
the Projectron and the Projectron++ outperform thePerceptron with smaller support set.

6. Discussion
This paper presented two different versions of abounded online learning algorithm. The algorithms
depend on a parameter that allows to trade accuracy

for sparseness of the solution. The size of the solutionis always guaranteed to be bounded, therefore it solves
the memory explosion problem of the Perceptron andsimilar algorithms. Although the size of the support
set is guaranteed to be bounded, the actual size of the
support set cannot be determined in advance, like in
the Forgetron algorithm, and it is not fixed. Practically, the size of the support set of the Projectron
algorithms is much smaller than that of the budget
algorithms.
Compared to budget algorithms it has the advantage
of a bounded support set size without removing or scaling instances in the set. This keeps performance high.
We call this algorithm Projectron. Its second variant,
the Projectron++, always outperforms the standard
Perceptron algorithm, while assuring a bounded solution. Another advantage over budget algorithms isthe possibility to obtain bounded batch solutions using standard online-to-batch conversion. In fact using
the averaging conversion (Cesa-Bianchi et al., 2004)
we get a bounded solution. This is not true for budget algorithms, where more sophisticated techniques
have to be used (Dekel & Singer, 2005). A similar approach has been used in (Csató & Opper, 2001) in theframework of the Gaussian Processes. However in that

Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

0.28

0.26

Online average number of mistakes

Online average number of mistakes

The Projectron: a Bounded Kernel-Based Perceptron

0.24

0.22

0.2

0.18

0.16
0

0.5

1

1.5

2

2.5

3

Number of samples

3.5
4

x 10

Figure 1. Average online error for the different algorithms
on Adult9 dataset as a function of the number of training
samples. B is set to 1500.
14000

Size of the active set

12000

10000

Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

8000

6000

4000

2000

0
0

0.5

1

1.5

2

Number of samples

2.5

3

3.5
4

x 10

Figure 2. Size of the support set for the different algorithms
on Adult9 dataset as a function of the number of training
samples. B is set to 1500.

paper no mistake bounds were derived and the use of
the hinge loss allows us to have sparser solution.
Acknowledgments. This work was supported by EU
project DIRAC (FP6-0027787).

References
Cauwenberghs, G., & Poggio, T. (2000). Incremental anddecremental support vector machine learning. Advancesin Neural Information Processing Systems 14.
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004). On
the generalization ability of on-line learning algorithms.
IEEE Trans. on Information Theory, 50, 2050–2057.
Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2006).
Tracking the best hyperplane with a simple budget Perceptron. Proc. of the 19th Conference on Learning Theory (pp. 483–498).
Cheng, L., Vishwanathan, S. V. N., Schuurmans, D.,
Wang, S., & Caelli, T. (2007). Implicit online learningwith kernels. Advances in Neural Information Processing
Systems 19.

Perceptron
PA−I
Projectron
Projectron++

0.28

0.26

0.24

0.22

0.2

0.18

0.16
0

500

1000

1500

Size of the active set

Figure 3. Average online error for the different algorithms
on Adult9 dataset as a function of the size of the support
set. B is set to 1500.
Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., &Singer, Y. (2006). Online passive-aggressive algorithms.
Journal of Machine Learning Research, 7, 551–585.
Crammer, K., Kandola, J., & Singer, Y. (2003). Online
classification on a budget. Advances in Neural Information Processing Systems 16.
Csató, L., & Opper, M. (2001). Sparse representation forgaussian process models. Advances in Neural Information Processing Systems 13.
Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2007). The
Forgetron: A kernel-based perceptron on a budget.
SIAM Journal on Computing, 37, 1342–1372.
Dekel, O., & Singer, Y. (2005). Data-driven online to batch
conversions. Advances in Neural Information Processing
Systems 18.
Downs, T., Gates, K. E., & Masters, A. (2001). Exact
simplification of support vectors solutions. Journal of
Machine Learning Research, 2, 293–297.
Engel, Y., Mannor, S., & Meir, R. (2002). Sparse online
greedy support vector regression. Proceedings 13th European Conference on Machine Learning.
Kivinen, J., Smola, A., & Williamson, R. (2004). Online
learning with kernels. IEEE Trans. on Signal Processing,52, 2165–2176.
Orabona, F., Castellini, C., Caputo, B., Luo, J., & Sandini,G. (2007). Indoor place recognition using online independent support vector machines. Proc. of the British
Machine Vision Conference 2007 (pp. 1090–1099).
Rosenblatt, F. (1958). The Perceptron: A probabilistic
model for information storage and organization in thebrain. Psychological Review, 65, 386–407.
Schölkopf, B., Herbrich, R., Smola, A., & Williamson, R.
(2000). A generalized representer theorem. Proc. of the
13th Conference on Computational Learning Theory.
Shalev-Shwartz, S., & Singer, Y. (2005). A new perspective on an old perceptron algorithm. Proc. of the 18th
Conference on Learning Theory (pp. 264–278).
Weston, J., Bordes, A., & Bottou, L. (2005). Online (andoffline) on an even tighter budget. Proceedings of AISTATS 2005 (pp. 413–420).