Journal of Machine Learning Research 10 (2009) 2643-2666

Submitted 12/08; Revised 9/09; Published 11/09

Bounded Kernel-Based Online Learning∗
Francesco Orabona
Joseph Keshet†
Barbara Caputo

FORABONA @ IDIAP. CH
JKESHET @ IDIAP. CH
BCAPUTO @ IDIAP. CH

Idiap Research InstituteCH-1920 Martigny, Switzerland

Editor: Yoav Freund

Abstract
A common problem of kernel-based online algorithms, such as the kernel-based Perceptron algorithm, is the amount of memory required to store the online hypothesis, which may increase without bound as the algorithm progresses. Furthermore, the computational load of such algorithms
grows linearly with the amount of memory used to store the hypothesis. To attack these problems,
most previous work has focused on discarding some of the instances, in order to keep the memory
bounded. In this paper we present a new algorithm, in which the instances are not discarded, but are
instead projected onto the space spanned by the previous online hypothesis. We call this algorithm
Projectron. While the memory size of the Projectron solution cannot be predicted before training,
we prove that its solution is guaranteed to be bounded. We derive a relative mistake bound for the
proposed algorithm, and deduce from it a slightly different algorithm which outperforms the Perceptron. We call this second algorithm Projectron++. We show that this algorithm can be extended
to handle the multiclass and the structured output settings, resulting, as far as we know, in the first
online bounded algorithm that can learn complex classification tasks. The method of bounding the
hypothesis representation can be applied to any conservative online algorithm and to other online
algorithms, as it is demonstrated for ALMA2 . Experimental results on various data sets show theempirical advantage of our technique compared to various bounded online algorithms, both in termsof memory and accuracy.
Keywords: online learning, kernel methods, support vector machines, bounded support set

1. Introduction
Kernel-based discriminative online algorithms have been shown to perform very well on binary
and multiclass classification problems (see, for example, Freund and Schapire, 1999; Crammer andSinger, 2003; Kivinen et al., 2004; Crammer et al., 2006). Each of these algorithms works in rounds,
where at each round a new instance is provided. On rounds where the online algorithm makes aprediction mistake or when the confidence in the prediction is not sufficient, the algorithm adds theinstance to a set of stored instances, called the support set. The online classification function isdefined as a weighted sum of kernel combination of the instances in the support set. It is clear that if
the problem is not linearly separable or the target hypothesis is changing over time, the classification
function will never stop being updated, and consequently, the support set will grow unboundedly.
∗. A preliminary version of this paper appeared in the Proceedings of the 25th International Conference on Machine
Learning under the title “The Projectron: a Bounded Kernel-Based Perceptron”.
†. Current affiliation: Toyota Technological Institute at Chicago, 6045 S Kenwood Ave., Chicago, IL 60637.
c 2009 Francesco Orabona, Joseph Keshet and Barbara Caputo.

O RABONA , K ESHET AND C APUTOThis leads, eventually, to a memory explosion, which limits the applicability of these algorithms
for those tasks, such as autonomous agents, for example, where data must be acquired continuously
over time.
Several authors have tried to address this problem, mainly by bounding a priori the size ofthe support set with a fixed value, called a budget. The first algorithm to overcome the unlimited
growth of the support set was proposed by Crammer et al. (2003), and refined by Weston et al.
(2005). In these algorithms, once the size of the support set reaches the budget, an instance from the
support set that meets some criterion is removed, and replaced by the new instance. The strategy
is purely heuristic and no mistake bound is given. A similar strategy is also used in NORMA(Kivinen et al., 2004) and SILK (Cheng et al., 2007). The very first online algorithm to have a fixed
memory budget and a relative mistake bound is the Forgetron algorithm (Dekel et al., 2007). A
stochastic algorithm that on average achieves similar performance to Forgetron, and with a similar
mistake bound was proposed by Cesa-Bianchi et al. (2006). Unlike all previous work, the analysis
presented in the last paper is within a probabilistic context, and all the bounds derived there are in
expectation. A different approach to address this problem for online Gaussian processes is proposedin Csató and Opper (2002), where, in common with our approach, the instances are not discarded,
but rather projected onto the space spanned by the instances in the support set. However, in that
paper no mistake bound is derived and there is no use of the hinge loss, which often produces
sparser solutions. Recent work by Langford et al. (2008) proposed a parameter that trades accuracy
for sparseness in the weights of online learning algorithms. Nevertheless, this approach cannot
induce sparsity in online algorithms with kernels.
In this paper we take a different route. While previous work focused on discarding some of
the instances in order to keep the support set bounded, in this work the instances are not discarded.
Either they are projected onto the space spanned by the support set, or they are added to the support
set. By using this method, we show that the support set and, hence, the online hypothesis, is guaranteed to be bounded, although we cannot predict its size before training. Instead of using a budget
parameter, representing the maximum size of the support set, we introduce a parameter trading accuracy for sparseness, depending on the needs of the task at hand. The main advantage of this setup
is that by using all training samples, we are able to provide an online hypothesis with high online
accuracy. Empirically, as suggested by the experiments, the output hypotheses are represented withrelatively small number of instances, and have high accuracy.
We start with the most simple and intuitive kernel-based algorithm, namely the kernel-based
Perceptron. We modify the Perceptron algorithm so that the number of stored samples needed torepresent the online hypothesis is always bounded. We call this new algorithm Projectron. The
empirical performance of the Projectron algorithm is on a par with the original Perceptron algorithm. We present a relative mistake bound for the Projectron algorithm, and deduce from it a new
online bounded algorithm which outperforms the Perceptron algorithm, but still retains all of its
advantages. We call this second algorithm Projectron++. We then extend Projectron++ to the moregeneral cases of multiclass and structured output. As far as we know, this is the first bounded multiclass and structured output online algorithm, with a relative mistake bound.1 Our technique forbounding the size of the support set can be applied to any conservative kernel-based online algorithm and to other online algorithms, as we demonstrate for ALMA2 (Gentile, 2001). Finally, we
present some experiments with common data sets, which suggest that Projectron is comparable to
1. Note that converting the budget algorithms presented by other authors, such as the Forgetron, to the multiclass or the
structured output setting is not trivial, since these algorithms are inherently binary in nature.

2644

B OUNDED K ERNEL -BASED O NLINE L EARNING

Perceptron in performance, but it uses a much smaller support set. Moreover, experiments with Projectron++ shows that it outperforms all other bounded algorithms, while using the smallest support
set. We also present experiments on the task of phoneme classification, which is considered to bedifficult and naturally with a relatively very high number of support vectors. When comparing the
Projectron++ algorithm to the Passive-Aggressive multiclass algorithm (Crammer et al., 2006), it
turns out that the cumulative online error and the test error, after online-to-batch conversion, of bothalgorithms are comparable, although Projectron++ uses a smaller support set.
In summary, the contributions of this paper are (1) a new algorithm, called Projectron, which isderived from the kernel-based Perceptron algorithm, which empirically performs equally well, but
has a bounded support set; (2) a relative mistake bound for this algorithm; (3) another algorithm,
called Projectron++, based on the notion of large margin, which outperforms the Perceptron algorithm and the proposed Projectron algorithm; (4) the multiclass and structured output Projectron++online algorithm with a bounded support set; and (5) an extension of our technique to other online
algorithms, exemplified in this paper for ALMA2 .
The rest of the paper is organized as follows: in Section 2 we state the problem definition andthe kernel-based Perceptron algorithm. Section 3 introduces Projectron, along with its theoreticalanalysis. Next, in Section 4 we derive Projectron++. Section 5 presents the multiclass and structured
learning variant of Projectron++. In Section 6 we apply our technique for another kernel-based
online algorithm, ALMA2 . Section 7 describes experimental results of the algorithms presented, on
different data sets. Section 8 concludes the paper with a short discussion.

2. Problem Setting and the Kernel-Based Perceptron Algorithm
The basis of our study is the well known Perceptron algorithm (Rosenblatt, 1958; Freund andSchapire, 1999). The Perceptron algorithm learns the mapping f : X → R based on a set of examples T = {(x1 , y1 ), (x2 , y2 ), . . .}, where xt ∈ X is called an instance and yt ∈ {−1, +1} is calleda label. We denote the prediction of the Perceptron algorithm as sign( f (x)) and we interpret | f (x)|as the confidence in the prediction. We call the output f of the Perceptron algorithm a hypothesis, and we denote the set of all attainable hypotheses by H . In this paper we assume that H is a
Reproducing Kernel Hilbert Space (RKHS) with a positive definite kernel function k : X × X → R
implementing the inner product h·, ·i. The inner product is defined so that it satisfies the reproducing
property, hk(x, ·), f (·)i = f (x).
The Perceptron algorithm is an online algorithm, where learning takes place in rounds. At eachround a new hypothesis function is estimated, based on the previous one. We denote the hypothesis
estimated after the t-th round by ft . The algorithm starts with the zero hypothesis, f0 = 0. At eachround t, an instance xt ∈ X is presented to the algorithm, which predicts a label ŷt ∈ {−1, +1} using
the current function, ŷt = sign( ft (xt )). Then, the correct label yt is revealed. If the prediction ŷtdiffers from the correct label yt , the hypothesis is updated as ft = ft−1 + yt k(xt , ·), otherwise thehypothesis is left intact, ft = ft−1 . The hypothesis ft can be written as a kernel expansion according
to the representer theorem (Schölkopf et al., 2001),
ft (x) = ∑ αi k(xi , x),(1)

xi ∈Stwhere αi = yi and St is defined to be the set of instances for which an update of the hypothesis
occurred, that is, St = {xi , 0 ≤ i ≤ t | ŷi 6= yi }. The set St is called the support set. The Perceptron
algorithm is summarized in Figure 1.
2645

O RABONA , K ESHET AND C APUTO/ f0 = 0
Initialize: S0 = 0,
For t = 1, 2, . . .
Receive new instance xt
Predict ŷt = sign( ft−1 (xt ))Receive label yt
If yt 6= ŷtft = ft−1 + yt k(xt , ·)St = St−1 ∪ xt

(update the hypothesis)(add instance xt to the support set)

Else
ft = ft−1

St = St−1
Figure 1: The kernel-based Perceptron Algorithm.
Although the Perceptron algorithm is very simple, it produces an online hypothesis with good
performance. Our goal is to derive and analyze a new algorithm, which outputs a hypothesis thatattains almost the same performance as the Perceptron hypothesis, but can be represented using
many fewer instances, that is, an online hypothesis that is “close” to the Perceptron hypothesis but
represented by a smaller support set. Recall that the hypothesis ft is represented as a weighted sum
over all the instances in the support set. The size of this representation is the cardinality of the
support set, |St |.

3. The Projectron Algorithm
This section starts by deriving the Projectron algorithm, motivated by an example of a finite dimensional kernel space. It continues with a description of how to calculate the projected hypothesis
and describes some other computational aspects of the algorithm. The section concludes with atheoretical analysis of the algorithm.
3.1 Definition and Derivation
Let us first consider a finite dimensional RKHS H induced by a kernel such as the polynomial
kernel. Since H is finite dimensional, there are a finite number of linearly independent hypotheses inthis space. Hence, any hypothesis in this space can be expressed using a finite 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, we
check if the instance xt can be spanned by the support set, namely, for scalars di ∈ R, 1 ≤ i ≤ |St−1 |,not all zeros, such thatk(xt , ·) = ∑ di k(xi , ·) .
xi ∈St−1

If we can find such scalars, the instance is not added to the support set, but instead, the coefficients{αi } in the expansion Equation (1) are changed to reflect the addition of this instance to the support
2646

B OUNDED K ERNEL -BASED O NLINE L EARNING

set. Namely, for every i
αi = yi + yt di .
On the other hand, 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. A similar approach was used by Downs et al. (2001) to simplify SVM solutions.
Let us consider now the more elaborate case of an infinite dimensional RKHS H induced by akernel such as the Gaussian kernel. In this case, it is not possible to find a finite number of linearly
independent vectors which span the whole space, and hence there is no guarantee that the hypothesis
can be expressed by a finite number of instances. However, we can approximate the concept of linear
independence with a finite number of vectors (Csató and Opper, 2002; Engel et al., 2004; Orabona
et al., 2007).
In particular, let us assume that at round t of the algorithm there is a prediction mistake, and thatthe mistaken instance xt should be added to the support set, St−1 . Let Ht−1 be an RKHS which isthe span of the kernel images of the instances in the set St−1 . Formally,Ht−1 = span ({k(x, ·)|x ∈ St−1 }) .

(2)

Before adding the instance to the support set, we construct two hypotheses: a temporary hypothesis,
ft′ , using the function k(xt , ·), that is, ft′ = ft−1 + yt k(xt , ·), and a projected hypothesis, ft′′ , thatis the projection of ft′ onto the space Ht−1 . That is, the projected hypothesis is that hypothesis
from the space Ht−1 which is the closest to the temporary hypothesis. In a later section we will
describe an efficient way to calculate the projected hypothesis. Denote by δt the distance between
the hypotheses, δt = ft′′ − ft′ . If the norm of distance kδt k is below some threshold η, we use
the projected hypothesis as our next hypothesis, that is, ft = ft′′ , otherwise we use the temporary
hypothesis as our next hypothesis, that is, ft = ft′ . As we show in the following theorem, this strategy
assures that the maximum size of the support set is always finite, regardless of the dimension of the
RKHS H . Guided by these considerations we can design a new Perceptron-like algorithm thatprojects the solution onto the space spanned by the previous support vectors whenever possible. We
call this algorithm Projectron. The algorithm is given in Figure 2.
The parameter η plays an important role in our algorithm. If η is equal to zero, we obtain
exactly the same solution as the Perceptron algorithm. In this case, however, the Projectron solution
can still be sparser when some of the instances are linearly dependent or when the kernel induces afinite dimensional RKHS H . If η 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 each step are bounded. We analyze the effect of η on the classification
accuracy in Subsection 3.3.
3.2 Practical Considerations
We now consider the problem of deriving the projected hypothesis ft′′ in a Hilbert space H , induced
by a kernel function k(·, ·). Recall that ft′ is defined as ft′ = ft + yt k(xt , ·). Denote by Pt−1 ft′ theprojection of ft′ ∈ H onto the subspace Ht−1 ⊆ H . The projected hypothesis ft′′ is defined asft′′ = Pt−1 ft′ . Schematically, this is depicted in Figure 3.
Expanding ft′ we haveft′′ = Pt−1 ft′ = Pt−1 ( ft−1 + yt k(xt , ·)) .
2647

O RABONA , K ESHET AND C APUTO/ f0 = 0
Initialize: S0 = 0,
For t = 1, 2, . . .
Receive new instance xt
Predict ŷt = sign( ft−1 (xt ))Receive label yt
If yt 6= ŷt
Set ft′ = ft−1 + yt k(xt , ·)(temporary hypothesis)

Set ft′′ = ft′ projected onto the space Ht−1
Set δt = ft′′ − ft′(projected hypothesis)

If kδt k ≤ ηft = ft′′

St = St−1
Else
ft = ft′

St = St−1 ∪ xt

(add xt to the support set)

Else
ft = ft−1

St = St−1
Figure 2: The Projectron Algorithm.
The projection is a linear operator, henceft′′ = ft−1 + yt Pt−1 k(xt , ·) .

(3)

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

(4)

The projection of ft′ ∈ H onto a subspace Ht−1 ⊂ H is defined as the hypothesis in Ht−1 closest
to ft′ . Hence, let ∑x j ∈St−1 d j k(x j , ·) be an hypothesis in Ht−1 , where d = (d1 , . . . , d|St−1 | ) is a set of
coefficients, with di ∈ R. The closest hypothesis is the one for which it holds that22kδt k = mind∑ d j k(x j , ·) − k(xt , ·).

(5)x j ∈St−1

Expanding Equation (5) we getkδt k2 = mind∑d j di k(x j , xi ) − 2∑ d j k(x j , xt ) + k(xt , xt )x j ∈St−1

xi ,x j ∈St−1

2648

!

.

B OUNDED K ERNEL -BASED O NLINE L EARNING

ft′

δt

ft′′
ft−1

Ht−1

Figure 3: Geometrical interpretation of the projection of the hypothesis ft′′ onto the subspace Ht−1 .
Let us define Kt−1 ∈ Rt−1×t−1 to be the matrix generated by the instances in the support set St−1 ,that is, {Kt−1 }i, j = k(xi , x j ) for every xi , x j ∈ St−1 . Let us also define kt ∈ Rt−1 to be the vector
whose i-th element is kti = k(xi , xt ). We havekδt k2 = min dT Kt−1 d − 2dT kt + k(xt , xt ) .
(6)dSolving Equation (6), that is, applying the extremum conditions with respect to d, we obtain−1d⋆ = Kt−1
kt(7)

and, by substituting Equation (7) into Equation (6),kδt k2 = k(xt , xt ) − ktT d⋆ .

(8)Furthermore, by substituting Equation (7) back into Equation (3) we getft′′ = ft−1 + yt

∑ d⋆j k(x j , ·) .

(9)x 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 Equation (7), and plug the result either into Equation (8) toobtain δt , or into Equation (9) to obtain the projected hypothesis.
In order to make the computation more tractable, we need an efficient method to calculate thematrix inversion Kt−1 iteratively. The first method, used by Cauwenberghs and Poggio (2000) for
incremental training of SVMs, directly updates the inverse matrix. An efficient way to do this,
exploiting the incremental nature of the approach, is to recursively update the inverse matrix. Using
the matrix inversion lemma it is possible to show (see, e.g., Csató and Opper, 2002) that after the
addition of a new sample, Kt−1 becomes


0
 ⋆ 

.. 

 ⋆T
−1
1
d


−1
K
.
t−1
Kt = 
−1
d
+
2
−1

0  kδt k
0 ··· 0 02649

O RABONA , K ESHET AND C APUTO−1
Input: new instance xt , Kt−1
, and the support set St−1
- Set kt = k(x1 , xt ), k(x2 , xt ), . . . , k(x|St−1 | , xt )−1
- Solve d⋆ = Kt−1
kt

- Set kδt k2 = k(xt , xt ) − ktT d⋆- The projected hypothesis is ft′′ = ft−1 + yt ∑x j ∈St−1 d⋆j k(x j , ·)- Kernel inverse matrix for the next round


0
 ⋆ 

.. 
 ⋆T
−1
1
d


−1
K
.
t−1
Kt = d+2−1

0  kδt k
0 ··· 0 0−1

Output: the projected hypothesis ft′′ , the measure δt and the kernel inverse
matrix Kt−1 .
Figure 4: Calculation of the projected hypothesis ft′′ .
where d⋆ and kδt k2 are already evaluated during the previous steps of the algorithm, as given by
Equation (7) and Equation (8). Thanks to this incremental evaluation, the time complexity of thelinear independence check is O(|St−1 |2 ), as one can easily see from Equation (7). Note that thematrix Kt−1 can be safely inverted since, by incremental construction, it is always full-rank.
An alternative way to derive the inverse matrix is to use the Cholesky decomposition of Kt−1
and to update it recursively. This is known to be numerically more stable than directly updating theinverse. In our experiments, however, we found out that the method presented here is as stable as
the Cholesky decomposition.
Overall, the time complexity of the algorithm is O(|St |2 ), as described above, and the spacecomplexity is O(|St |2 ), due to the storage of the matrix Kt−1 , similar to the second-order Perceptron
algorithm (Cesa-Bianchi et al., 2005). A summary of the derivation of ft′′ , the projection of ft′ onto
the space spanned by St−1 , is described in Figure 4.
3.3 Analysis
We now analyze the theoretical aspects of the proposed algorithm. First, we present a theorem
which states that the size of the support set of the Projectron algorithm is bounded.
Theorem 1 Let k : X × X → R be a continuous Mercer kernel, with X a compact subset of a Banach
space. Then, for any training sequence T = {(xi , yi )}, i = 1, 2, · · · and for any η > 0, the size of the
support set of the Projectron algorithm is finite.
Proof The proof of this theorem follows the same lines as the proof of Theorem 3.1 in Engel et al.
(2004). From the Mercer theorem it follows that there exists a mapping φ : X → H ′ , where H ′ is2650

B OUNDED K ERNEL -BASED O NLINE L EARNING

an Hilbert space, k(x, x′ ) = hφ(x), φ(x′ )i and φ is continuous. Given that φ is continuous and that X
is compact, we obtain that φ(X ) is compact. From the definition of δt in Equation (5) we get thatevery time a new basis vector is added we have2

η ≤ kδt k = min22d∑ d j k(x j , ·) − k(xt , ·)≤ min d j k(x j , ·) − k(xt , ·)x j ∈St−1= min d j φ(x j ) − φ(xt )
dj

2

2

dj

≤ φ(x j ) − φ(xt )2for any 1 ≤ j ≤ |St−1 |. Hence from the definition of packing numbers (Cucker and Zhou, 2007,
Definition 5.17), we get that the maximum size of the support set in the Projectron algorithm isbounded by the packing number at scale η of φ(X ). This number, in turn, is bounded by thecovering number at scale η/2, and it is finite because the set is compact (Cucker and Zhou, 2007,
Proposition 5.18).
Note that this theorem guarantees that the size of the support set is bounded, however it does notstate that the size of the support set is fixed or that it can be estimated before training.
The next theorem provides a mistake bound. The main idea is to bound the maximum numberof mistakes of the algorithm, relative to any hypothesis g ∈ H , even chosen in hindsight. First, we
define the loss with a margin γ ∈ R of the hypothesis g on the example (xt , yt ) asℓγ (g(xt ), yt ) = max{0, γ − yt g(xt )},(10)and we define the cumulative loss, Dγ , of g on the first T examples asT

Dγ = ∑ ℓγ (g(xt ), yt ) .
t=1

Before stating the bound, we present a lemma that will be used in the rest of our proofs. We will use
its first statement to bound the scalar product between a projected sample and the competitor, andits second statement to derive the scalar product between the current hypothesis and the projected
sample.
Lemma 2 Let (x̂, ŷ) be an example, with x̂ ∈ X and ŷ ∈ {+1, −1}. If we denote by f (·) an hypothesis in H , and denote by q(·) any function in H , then the following holdsŷh f , qi ≥ γ − ℓγ ( f (x̂), ŷ) − k f k · kq − k(x̂, ·)k .
Moreover, if f (·) can be written as ∑mi=1 αi k(xi , ·) with αi ∈ R and xi ∈ X , i = 1, · · · , m, and q(·) isthe projection of k(x̂, ·) onto the space spanned by k(xi , ·), i = 1, · · · , m, thenŷh f , qi = ŷ f (x̂) .
Proof The first inequality comes from an application of the Cauchy-Schwarz inequality and thedefinition of the hinge loss in Equation (10). The second equality follows from the fact that h f , q −k(x̂, ·)i = 0, because f (·) is orthogonal to the difference between k(x̂, ·) and its projection onto thespace in which f (·) lives.
With these definitions at hand, we can state the following bound for Projectron.
2651

O RABONA , K ESHET AND C APUTO

Theorem 3 Let (x1 , y1 ), · · · , (xT , yT ) be a sequence of instance-label pairs where xt ∈ X , yt ∈{−1, +1}, and k(xt , xt ) ≤ 1 for all t. Assume that the Projectron algorithm is run with η ≥ 0.
Then the number of prediction mistakes it makes on the sequence is bounded by
s
kgk2
D1
D1
kgk
+
+
2
(1 − ηkgk)
1 − ηkgk 1 − ηkgk 1 − ηkgk
where g is an arbitrary function in H , such that kgk < η1 .
Proof Define the relative progress in each round as ∆t = k ft−1 − λgk2 − k ft − λgk2 , where λ is apositive scalar to be optimized. We bound the progress from above and below, as in Gentile (2003).
On rounds where there is no mistake, ∆t equals 0. On rounds where 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 the following westart bounding the progress from below, when the update is of the former type. In particular we set
q(·) = Pt−1 k(xt , ·) in Lemma 2 and use δt = yt Pt−1 k(xt , ·) − yt k(xt , ·) from Equation (4). 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. We have∆t = k ft−1 − λgk2 − k ft − λgk2 = 2τt yt hλg − ft−1 , Pt−1 k(xt , ·)i − τt2 kPt−1 k(xt , ·)k2
≥ τt 2λ − 2λℓ1 (g(xt ), yt ) − τt kPt−1 k(xt , ·)k2 − 2λkgk · kδt k − 2yt ft−1 (xt ) .

(11)

Moreover, on every projection update kδt k ≤ η, and kPt−1 k(xt , ·)k ≤ 1 by the theorem’s assumption,so we have∆t ≥ τt 2λ − 2λℓ1 (g(xt ), yt ) − τt − 2ηλkgk − 2yt ft−1 (xt ) .
We can further bound ∆t by noting that on every prediction mistake yt ft−1 (xt ) ≤ 0. Overall we have
(12)k ft−1 − λgk2 − k ft − λgk2 ≥ τt 2λ − 2λℓ1 (g(xt ), yt ) − τt − 2ηλkgk .
When there is an update without projection, similar reasoning yields thatk ft−1 − λgk2 − k ft − λgk2 ≥ τt 2λ − 2λℓ1 (g(xt ), yt ) − τt ,hence the bound in Equation (12) holds in both cases.
We sum over t on both sides, remembering that τt can be upper bounded by 1. The left handside of the equation is a telescoping sum, hence it collapses to k f0 − λgk2 − k fT − λgk2 , which canbe upper bounded by λ2 kgk2 , using the fact that f0 = 0 and that k fT − λgk2 is non-negative. Finally,
we have
λ2 kgk2 + 2λD1 ≥ M (2λ − 2ηλkgk − 1) ,(13)
where M is the number of mistakes. The last equation implies a bound on M for any choice of λ > 0,
D1
hence we can take the minimum of these bounds. From now on we can suppose that M > 1−ηkgk.
D1then the theorem trivially holds. The minimum of Equation (13) as a function
In fact, if M ≤ 1−ηkgkof λ occurs at
M(1 − ηkgk) − D1
.
λ∗ =
kgk2

2652

B OUNDED K ERNEL -BASED O NLINE L EARNING

D1
we have that λ∗ is positive. Substituting λ∗ into Equation (13)
By our hypothesis that M > 1−ηkgk
we obtain(D1 − M(1 − ηkgk))2−M ≤ 0 .
kgk2

Solving for M and overapproximating concludes the proof.
This theorem suggests that the performance of the Projectron algorithm is slightly worse thanthat of the Perceptron algorithm. Specifically, if we set η = 0, we recover the best known bound for
the Perceptron algorithm (see for example Gentile, 2003). Hence the degradation in the performance1. Empirically, the Projectron algorithm andof Projectron compared to Perceptron is related to 1−ηkgk
the Perceptron algorithm perform similarly, for a wide range of settings of η.

4. The Projectron++ Algorithm
The proof of Theorem 3 suggests how to improve the Projectron algorithm to improve upon theperformance of the Perceptron algorithm, while maintaining a bounded support set. We can change
the Projectron algorithm so that an update takes place not only if there is a prediction mistake, butalso when the confidence of the prediction is low. We refer to this latter case as a margin error, thatis, 0 < yt ft−1 (xt ) < 1. This strategy is known to improve 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 on every round in which a margin error occurs, but only when there is a margin error and the
new instance can be projected onto the support set. Hence, the update on round in which there is amargin error would in general be of the form
ft = ft−1 + yt τt Pt−1 k(xt , ·) ,with 0 < τt ≤ 1. The last constraint comes from the proof of Theorem 3, where we upper bound τtby 1. Note that setting τt to 0 is equivalent to leaving the hypothesis unchanged.
In particular, disregarding the loss term in Equation (11), the progress ∆t can be made positive
with an appropriate choice of τt . Whenever this progress is non-negative the worst-case numberof mistakes decreases, hopefully along with the classification error rate of the algorithm. With thismodification we expect better performance, that is, fewer mistakes, but without any increase of the
support set size. We can even expect solutions with a smaller support set, since new instances canbe added to the support set only if misclassified, hence having fewer mistakes should result in asmaller support set. We name this algorithm Projectron++. The following theorem states a mistakebound for Projectron++, and guides us in how to choose τt .
Theorem 4 Let (x1 , y1 ), · · · , (xT , yT ) be a sequence of instance-label pairs where xt ∈ X , yt ∈{−1, +1}, and k(xt , xt ) ≤ 1 for all t. Assume that Projectron++ is run with η > 0. Then thenumber of prediction mistakes it makes on the sequence is bounded by
D1
kgk
kgk2
+
+
(1 − ηkgk)2 1 − ηkgk 1 − ηkgk
2653

s


max 0,

D1−B
1 − ηkgkO RABONA , K ESHET AND C APUTO

where g is an arbitrary function in H , such that kgk < η1 ,

and



 ℓ1 ( ft−1 (xt ), yt ) − kδt k 
η,1
0 < τt < min 2
kPt−1 k(xt , ·)k2



kδt k
2
>0.
τt 2ℓ1 ( ft−1 (xt ), yt ) − τt kPt−1 k(xt , ·)k − 2B=∑η{t:0<y f (x )<1}
t t−1

t

Proof The proof is similar to the proof of Theorem 3, where the difference is that during rounds inwhich there is a margin error we update the solution whenever it is possible to project ensuring an
improvement of the mistake bound. Assume that λ ≥ 1. On rounds when a margin error occurs, as
in Equation (11), we can write∆t + 2τt λℓ1 (g(xt ), yt ) ≥τt 2λ − τt kPt−1 k(xt , ·)k2 − 2λkδt k · kgk − 2yt ft−1 (xt )
 


kδt k
2
>
τt 2 1 −− τt kPt−1 k(xt , ·)k − 2yt ft−1 (xt )
η


kδt k
,
(14)
=
τt 2ℓ1 ( ft−1 (xt ), yt ) − τt kPt−1 k(xt , ·)k2 − 2ηwhere we used the bounds on kgk and λ. Let βt be the right hand-side of Equation (14). A sufficientcondition to have βt positive isτt < 2ℓ1 ( ft−1 (xt ), yt ) − kδηt k
kPt−1 k(xt , ·)k2.

Constraining τt to be less than or equal to 1 yields the update rule in the theorem.
Let B = ∑{t:0<yt ft−1 (xt )<1} βt . Similarly to the proof of Theorem 3, we have
λ2 kgk2 + 2λD1 ≥ M (2λ − 2ηλkgk − 1) + B .

(15)

Again, the optimal value of λ isλ∗ =M(1 − ηkgk) − D1
.
kgk2
2

+D1
We can assume that M(1 − ηkgk) − D1 ≥ kgk2 . In fact, if M < kgk
1−ηkgk , then the theorem triviallyholds. With this assumption, λ∗ is positive and greater than or equal to 1, satisfying our initialconstraint on λ. Substituting this optimal value of λ into Equation (15), we have

(D1 − M(1 − ηkgk))2−M+B ≤ 0 .
kgk2
Solving for M concludes the proof.

2654

B OUNDED K ERNEL -BASED O NLINE L EARNING

The proof technique presented here is very general, in particular it can be applied to the PassiveAggressive algorithm PA-I (Crammer et al., 2006). In fact, removing the projection step and updating on rounds in whichn there is a margino error, with ft = ft−1 + yt τt k(xt , ·), we end up with theℓ1 ( ft−1 (xt ),yt )
condition 0 < τt < min 2 kk(xt ,·)k2 , 1 . This rule generalizes the PA-I bound whenever R = 1
and C = 1, however the obtained bound substantially improves upon the original bound in Crammer
et al. (2006).
The theorem gives us some freedom for the choice of τt . Experimentally we have observed that
we obtain the best performance if the update is done with the following rule ℓ ( f (x ), y ) ℓ1 ( ft−1 (xt ), yt ) − kδt k η
1 t−1 tt,2
,1 .
τt = min kPt−1 k(xt , ·)k2
kPt−1 k(xt , ·)k2
The added term in the minimum comes from ignoring the term −2 kδηt k and in finding the maximumof the quadratic equation. Notice that the term kPt−1 k(xt , ·)k2 in the last equation can be practicallycomputed as ktT d⋆ , as can be derived using the same techniques presented in Subsection 3.2.
We note in passing that the condition on whether xt can be projected onto Ht−1 on margin error
may stated as ℓ1 ( ft−1 (xt ), yt ) ≥ kδηt k . This means that if the loss is relatively large, the progress isalso large and the algorithm can afford “wasting” a bit of it for the sake of projecting.
The algorithm is summarized in Figure 2. The performance of the Projectron++ algorithm, theProjectron algorithm and several other bounded online algorithms are compared and reported in
Section 7.

5. Extension to Multiclass and Structured Output
In this section we extend Projectron++ to the multiclass and the structured output settings (note that
Projectron can be generalized in a similar way). We start by presenting the more complex decision
problem, namely the structured output, and then we derive the multiclass decision problem as a
special case.
In structured output decision problems the set of possible labels has a unique and defined structure, such as a tree, a graph or a sequence (Collins, 2000; Taskar et al., 2003; Tsochantaridis et al.,2004). Denote the set of all labels as Y = {1, . . . , k}. Each instance is associated with a label from
Y . Generally, in structured output problems there may be dependencies between the instance andthe label, as well as between labels. Hence, to capture these dependencies, the input and the output
pairs are represented in a common feature representation. The learning task is therefore defined asfinding a function f : X × Y → R such thatyt = arg max f (xt , y) .
y∈Y

(16)

Let us generalize the definition of the RKHS H introduced in Section 2 to the case of structured
learning. A kernel function in this setting should reflect the dependencies between the instances
and the labels, hence we define the structured kernel function as a function on the domain of theinstances and the labels, namely, kS : (X × Y )2 → R. This kernel function induces the RKHSH S , where the inner product in this space is defined such that it satisfies the reproducing property,
hkS ((x, y), ·), f i = f (x, y).
2655

O RABONA , K ESHET AND C APUTO/ f0 = 0
Initialize: S0 = 0,
For t = 1, 2, . . .
Receive new instance xt
Predict ŷt = sign( ft−1 (xt ))Receive label yt
If yt 6= ŷt(prediction error)

Set ft′ = ft−1 + yt k(xt , ·)Set ft′′ = Pt−1 ft′
Set δt = ft′′ − ft′If kδt k ≤ ηft = ft′′

St = St−1
Else
ft = ft′

St = St−1 ∪ xt
Else If yt = ŷt and yt ft−1 (xt ) ≤ 1(margin error)

Set δt = Pt−1 k(xt , ·) − k(xt , ·)(check if the xt can be projected onto Ht−1 )If ℓ1 ( ft−1 (xt ), yt ) ≥ kδηt kℓ1 ( ft−1 (xt ),yt )− kδηt kℓ1 ( ft−1 (xt ),yt )Set τt = min kPt−1 k(xt ,·)k2 , 2 kPt−1 k(xt ,·)k2 , 1
Set ft = ft−1 + yt τt Pt−1 k(xt , ·)St = St−1
Else
ft = ft−1

St = St−1
Else
ft = ft−1

St = St−1
Figure 5: The Projectron++ Algorithm.

As in the binary classification algorithm presented earlier, the structured output online algorithm
receives instances in a sequential order. Upon receiving an instance, xt ∈ X , the algorithm predicts alabel, yt′ , according to Equation (16). After making its prediction, the algorithm receives the correctlabel, yt . We define the loss suffered by the algorithm on round t for the example (xt , yt ) asℓSγ ( f , xt , yt ) = max{0, γ − f (xt , yt ) + max
f (xt , yt′ )},′yt 6=yt2656

B OUNDED K ERNEL -BASED O NLINE L EARNING

and the cumulative loss DSγ as
T

DSγ = ∑ ℓSγ ( f , xt , yt ) .
t=1

Note that sometimes it is useful to define γ as a function γ : Y × Y → R describing the discrepancy
between the predicted label and the true label. Our algorithm can handle such a label cost function,
but we will not discuss this issue here (see Crammer et al., 2006, for further details).
As in the binary case, on rounds in which there is a prediction mistake, yt′ 6= yt , the algorithm
updates the hypothesis ft−1 by adding k((xt , yt ), ·) − k((xt , yt′ ), ·) or its projection. When there isa margin mistake, 0 < ℓSγ ( ft−1 , xt , yt ) < γ, the algorithm updates the hypothesis ft−1 by adding
τt Pt−1 (k((xt , yt ), ·) − k((xt , yt′ ), ·)), where 0 < τt < 1 and will be defined shortly. Now, for the structured output case, δt is defined asδt = k((xt , yt ), ·) − k((xt , yt′ ), ·) − Pt−1 k((xt , yt ), ·) − k((xt , yt′ ), ·) .

The analysis of the structured output Projectron++ algorithm is similar to that provided for thebinary case. We can easily obtain the generalization of Lemma 2 and Theorem 4 as follows
Lemma 5 Let (x̂, ŷ) be an example, with x̂ ∈ X and ŷ ∈ Y . Denote by f (·) an hypothesis in H S .
Let q(·) ∈ H S . Then the following holds for any y′ ∈ Y :
h f , qi ≥ γ − ℓSγ ( f , x̂, ŷ) − k f k · q − k((x̂, ŷ), ·) − k((x̂, y′ ), ·) .

Moreover if f (·) can be written as ∑mi=1 αi k((xi , yi ), ·) with αi ∈ R and xi ∈ X , i = 1, · · · , m, and q is
the projection of k((x̂, ŷ), ·) − k((x̂, y′ ), ·) in the space spanned by k((xi , yi ), ·), i = 1, · · · , m, we havethat
h f , qi = f (x̂, ŷ) − f (x̂, y′ ) .
Theorem 6 Let (x1 , y1 ), · · · , (xT , yT ) be a sequence of instance-label pairs where xt ∈ X , yt ∈ Y ,and kk((xt , y), ·)k ≤ 1/2 for all t and y ∈ Y . Assuming that Projectron++ is run with η > 0, thenumber of prediction mistakes it makes on the sequence is bounded by
DS1
kgk2
kgk
+
+
2
(1 − ηkgk)
1 − ηkgk 1 − ηkgk

s

DS1
−B
max 0,
1 − ηkgk
where g is an arbitrary function in H S , such that kgk < η1 ,
a = Pt−1 k((xt , yt ), ·) − k((xt , yt′ ), ·) ℓS ( ft−1 , xt , yt ) − kδt k 1η
0 < τt < min 2
,1
2


kak


kδt k
S
2
>0.
B =
τt 2ℓ1 ( ft−1 , xt , yt ) − τt kak − 2∑
η{t:0<ℓS ( f ,x ,y )<1}
1

t−1

t

t

2657

O RABONA , K ESHET AND C APUTO

As in Theorem 4 there is some freedom in the choice of τt , and again we set it to ℓS ( f , x , y ) ℓS ( ft−1 , xt , yt ) − kδt k 1
η
1 t−1 t t,2
,1 .
τt = min
2
2


kak
kak

In the multiclass decision problem case, the kernel k((x1 , y1 ), (x2 , y2 )) is simplified toδy1 y2 k(x1 , x2 ), where δy1 y2 is the Kronecker delta. This corresponds to the use of a different prototype for each class. This simplifies the projection step, in fact k((xt , yt ), ·) can be projected only
onto the functions in St−1 belonging to yt , the scalar product with the other functions being zero.
−1
So instead of storing a single matrix Kt−1
, we need to store m matrices, where m is the number ofclasses, each one being the inverse matrix of the Gram matrix of the functions of one class. This
results in improvements in both memory usage and computational cost of the algorithm. To see
this suppose that we have m classes, each with n vectors in the support set. Storing a single matrix
means having a space and time complexity of O(m2 n2 ) (cf. Section 3), while in the second case thecomplexity is O(mn2 ). We use this method in the multiclass experiments presented in Section 7.

6. Bounding Other Online Algorithms
It is possible to apply the technique in the basis of the Projectron algorithm to any conservative
online algorithm. A conservative online algorithm is an algorithm that updates its hypothesis only
on rounds on which it makes a prediction error. By applying Lemma 2 to a conservative algorithm,
we can construct a bounded version of it with worst case mistake bounds. As in the previous proofs,
the idea is to use Lemma 2 to bound the scalar product of the competitor and the projected function.
This yields an additional term which is subtracted from the margin γ of the competitor.
The technique presented here can be applied to other online kernel-based algorithms. As an
example, we apply our technique to ALMA2 (Gentile, 2001). Again we define two hypotheses: atemporary hypothesis ft′ , which is the hypothesis of ALMA2 after its update rule, and a projected
hypothesis, which is the hypothesis ft′ projected on the set Ht−1 as defined in Equation (2). Define
the projection error δt as δt = ft′ − ft′′ . The modified ALMA2 algorithm uses the projected hypothesis ft′′ whenever the projection error is smaller than a parameter η, otherwise it uses the temporary
hypothesis ft′ . We can state the following boundTheorem 7 Let (x1 , y1 ), · · · , (xT , yT ) be a sequence of instance-label pairs where xt ∈ X , yt ∈{−1, +1}, and k(xt , xt ) ≤ 1 for all t. Let α, B and C ∈ R+ satisfy the equation
C2 + 2(1 − α)BC = 1 .
Assume ALMA2 (α;B,C) projects every time the projection error kδt k is less than η ≥ 0, then thenumber of prediction mistakes it makes on the sequence is bounded by
s
Dγ
ρ4
ρ2
ρ2
+ +
+
Dγ + ρ2
γ−η
2
4
γ−η
1
where γ > η, ρ = C2 (γ−η)
2 , and g is an arbitrary function in H , such that kgk ≤ 1.

Proof The proof follows the original proof presented in Gentile (2001). Specifically, according
to Lemma 2, one can replace the relation yt hg, k(xt , ·)i ≥ γ − ℓγ (g(xt ), yt ) with yt hg, Pt−1 k(xt , ·)i ≥2658

B OUNDED K ERNEL -BASED O NLINE L EARNING

Data Set
a9a (Platt, 1999)
ijcnn1 (Prokhorov, 2001)
news20.binary (Keerthi et al., 2005)
vehicle (Duarte and Hu, 2004)
synthetic (Dekel et al., 2007)
mnist (Lecun et al., 1998)
usps (Hull, 1994)
timit (subset) (Lemel et al., 1986)

Samples
32561
49990
19996
78823
10000
60000
7291
∼ 150000

Features123
221355191
100
2
780
256
351

Classes
2
2
2
2
2
10
10
39

KernelGaussian
GaussianLinearGaussian
Gaussian
Polynomial
Polynomial
GaussianParameters
0.04
8
0.125
1
7
13
80

Table 1: Data sets used in the experimentsγ − η − ℓγ (g(xt ), yt ), and further substitute γ − η for γ.

7. Experimental Results
In this section we present experimental results that demonstrate the effectiveness of the Projectron and the Projectron++ algorithms. We compare both algorithms to the Perceptron algorithm,
the Forgetron algorithm (Dekel et al., 2007) and the Randomized Budget Perceptron (RBP) algorithm (Cesa-Bianchi et al., 2006). For Forgetron, we choose the state-of-the-art “self-tuned” variant,which outperforms all of its other variants. We used the PA-I variant of the Passive-Aggressive algorithm (Crammer et al., 2006) as a baseline algorithm, as it gives an upper bound on the classification
performance of the Projectron++ algorithm. All the algorithms were implemented in MATLAB using the DOGMA library (Orabona, 2009).
We tested the algorithms on several standard machine learning data sets:2 a9a, ijcnn1, news20.binary,
vehicle (combined), usps, mnist. We also used a synthetic dataset and the acoustic-phonetic dataset
timit. The synthetic dataset was built in the same way as in Dekel et al. (2007). It is composed of10000 samples taken from two separate bi-dimensional Gaussian distributions. The means of thepositive and negative samples are (1, 1) and (−1, −1), respectively, while the covariance matrices
for both are diagonal matrices with (0.2, 2) as their diagonal. The labels are flipped with a probability of 0.1 to introduce noise. The list of the data sets, their characteristics and the kernels used,
are given in Table 1. The parameters of the kernels were selected to have the best performancewith the Perceptron and were used for all the other algorithms to result in a fair comparison. The
C parameter of PA-I was set to 1, to give an update similar to Perceptron and Projectron. All theexperiments were performed over five different permutations of the training set.
Experiments with one setting of η. In the first set of experiments we compared the online
average number of mistakes and the support set size of all algorithms. Both Forgetron and RBP
work by discarding vectors from the support set, if the size of the support set reaches the budget
size, B. Hence for a fair comparison, we set η to some value and selected the budget sizes ofForgetron and RBP to be equal to the final size of the support set of Projectron. In particular, inFigure 6, we set η = 0.1 in Projectron and ended up with a support set of size 793, hence B = 793.
In Figure 6(a) the average online error rate for all algorithms on the a9a data set is plotted. Notethat Projectron closely tracks Perceptron. On the other hand Forgetron and RBP stop improving
2. Downloaded from http://www.sie.ntu.edu.tw/˜cjlin/libsvmtools/datasets/.

2659

14000Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

0.28

0.26

12000

Size of the active set

Online average number of mistakes

O RABONA , K ESHET AND C APUTO

0.24

0.22

0.2

0.18

0.16
0

10000

Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

8000

6000

4000

2000

0.5

1

1.5

2

Number of samples

2.5

3

3.5

0
0

0.5

1

1.5

2

Number of samples

4

x 10

(a)

2.5

3

3.5
4

x 10

(b)

Figure 6: Average online error (left) and size of the support set (right) for the different algorithms
on a9a data set as a function of the number of training samples (better viewed in color).
B is set to 793, η = 0.1.

after reaching the support set size B, around 3400 samples. Moreover, as predicted by its theoreticalanalysis, Projectron++ achieves better results than Perceptron, even with fewer number of supports.
Figure 6(b) shows the growth of the support set as a function of the number of samples. Whilefor the PA-I and the Perceptron the growth is clearly linear, it is sub-linear for Projectron and Projectron++: they will reach a maximum size and then they will stop growing, as stated in Theorem 1.
Another important consideration is that Projectron++ outperforms Projectron both with respect tothe size of the support set and number of mistakes. Using our MATLAB implementation, the running times for this experiment are ∼ 35s for RBP and Forgetron, ∼ 40s for Projectron and Projectron++, ∼ 130s for Perceptron, and ∼ 375s for PA-I. Hence Projectron and Projectron++ have arunning time smaller than Perceptron and PA-I, due to their smaller support sets.
The same behavior can be seen in Figure 7, for the synthetic data set. Here the gain in performance of Projectron++ over Perceptron, Forgetron and RBP is even greater.
Experiments with a range of values for η - Binary. To analyze in more detail the behavior of
our algorithms we decided to run other tests using a range of values of η. For each value we obtaina different size of the support set and a different number of mistakes. We used the data to plot a
curve corresponding to the percentage of mistakes as a function of the support set size. The same
curve was plotted for Forgetron and RBP, where the budget size was selected as described before.
In this way we compared the algorithms along the continuous range of budget sizes, displaying thetrade-off between sparseness and accuracy. For the remaining experiments we chose not to show
the performance of Projectron, as it was always outperformed by Projectron++.
In Figure 8 we show the performance of the algorithms on different binary data sets: (a) ijcnn1,(b) a9a, (c) news20.binary, and (d) vehicle (combined). Because Projectron++ used a different
support set size for each permutation of the training samples, we plotted five curves, one for eachof the five permutations. RBP and Forgetron have fixed budget sizes set in advance, hence for thesealgorithms we just plotted standard deviation bars, that are very small so they can be hardly seenin the figures. In all of the experiments Projectron++ outperforms Forgetron and RBP. One may
2660

B OUNDED K ERNEL -BASED O NLINE L EARNING

4000

Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

0.26
0.24

3500

3000

Size of the active set

Online average number of mistakes

0.28

0.22
0.2
0.18
0.16

Perceptron
PA−I
Forgetron
RBP
Projectron
Projectron++

2500

2000

1500

1000

0.14
500

0.12
0.1
0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

Number of samples

0
0

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

Number of samples

(a)

(b)

Figure 7: Average online error (left) and size of the support set (right) for the different algorithms
on the synthetic data set as a function of the number of training samples (better viewed incolor). B is set to 103, η = 0.04.

note that there is a point in all the graphs where the performance of Projectron++ is better than
Perceptron, and has a smaller support set. Projectron++ gets closer to the classification rate of thePA-I, without paying the price of a larger support set. Note that the performance of Projectron++is consistently better than RBP and Forgetron, regardless of the kernel used, particularly, on the
database news20.binary, which is a text classification task with linear kernel. In this task the samples
are almost mutually orthogonal, so finding a suitable subspace on which to project is difficult.
Nevertheless Projectron++ succeeded in obtaining better performance. The reason is probably due
to the margin updates, which are performed without increasing the size of the solution. Note thata similar modification would not be trivial in Forgetron and in RBP, because the proofs of their
mistake bounds strongly depend on the rate of growth of the norm of the solution.
Experiments with a range of values for η - Multiclass. We have also considered multiclassdata sets, using the multiclass version of Projectron++. Due to the fact that there are no otherbounded online algorithms with a mistake bound for multiclass, we have extended RBP in thenatural manner to multiclass. In particular we used the max-score update in Crammer and Singer(2003), for which a mistake bound exists, discarding a vector at random from the solution each timea new instance is added and the number of support vectors is equal to the budget size. We name it
Multiclass Random Budget Perceptron (MRBP). It should be possible to prove a mistake bound forthis algorithm, extending the proof in Cesa-Bianchi et al. (2006). In Figure 9 we show the resultsfor Perceptron, Passive-Aggressive, Projectron++ and MRBP trained on (a) usps, and (b) mnist data
sets. The results confirm the findings found for the binary case.
The last data set used in our experiments is a corpus of continuous natural speech for the task ofphoneme classification. The data we used is a subset of the TIMIT acoustic-phonetic data set, which
is a phonetically transcribed corpus of high quality continuous speech spoken by North American
speakers (Lemel et al., 1986). The features were generated from nine adjacent vectors of MelFrequency Cepstrum Coefficients (MFCC) along with their first and second derivatives. The TIMIT
corpus is divided into a training set and a test set in such a way that no speakers from the training set
2661

O RABONA , K ESHET AND C APUTOIJCNN − Gaussian Kernel

A9A − Gaussian Kernel

0.25

RBP
Forgetron
Plain Perceptron
PA−I
Projectron++

0.35
Number of Mistakes (%)

0.2
Number of Mistakes (%)

0.4

RBP
Forgetron
Plain Perceptron
PA−I
Projectron++

0.15

0.1

0.05

0.3

0.25

0.2
Size of the support set = 10493±52.7500

Size of the support set = 12510±36.9

1000
1500
Size of the Support Set

2000

1000

2000
3000
4000
5000
Size of the Support Set

(a)

0.45

RBP
Forgetron
Plain Perceptron
PA−I
Projectron++

0.5

Number of Mistakes (%)

Number of Mistakes (%)

Vehicle − Gaussian Kernel
0.55

RBP
Forgetron
Plain Perceptron
PA−I
Projectron++

0.5

7000

(b)

News binary − Linear Kernel
0.55

6000

0.4
0.35
0.3
0.25
0.2
0.15

0.45
0.4
0.35
0.3
0.25
0.2

0.1

0.15 Size of the support set = 30167±67.6

0.05 Size of the support set = 9291±59.5
500

1000
1500
Size of the Support Set

2000

(c)

2000

4000

6000 8000 10000 12000 14000 16000
Size of the Support Set(d)Figure 8: Average online error for the different algorithms as a function of the size of the support
set on different binary data sets.

appear in the test set (speaker independent). We randomly selected 500 training utterances from thetraining set. The average online errors are shown in Figure 10 (a). We also tested the performanceof the algorithm on the proposed TIMIT core test set composed of 192 utterances, the results ofwhich are in Figure 10 (b). We used online-to-batch conversion (Cesa-Bianchi et al., 2004) togive a bounded batch solution. We did not test the performance of MRBP on the test set because forthis algorithm the online-to-batch conversion does not produce a bounded solution. We compare thebatch solution to the online-to-batch conversion of the PA-I solution. The results of Projectron++ arecomparable to those of PA-I, while the former uses a smaller support set. These results also suggestthat the batch solution is stable when varying the value of η, as the difference in performance on
test set is less than 3%.
2662

B OUNDED K ERNEL -BASED O NLINE L EARNING

MNIST − Polynomial Kernel

USPS − Polynomial Kernel
MRBP
Plain Perceptron
PA−I
Projectron++

0.5
Number of Mistakes (%)

Number of Mistakes (%)

0.5

0.4

0.3

0.2

0.4

0.3

0.2

0.1

0.1

0

MRBP
Plain Perceptron
PA−I
Projectron++Size of the support set = 3317±13.4

100

200
300
Size of the Support Set

0 Size of the support set = 18924±66.7
400

500

500

(a)

1000
1500
2000
Size of the Support Set

2500

(b)

Figure 9: Average online error for the different algorithms as a function of the size of the support
set on different multiclass data sets.

Phoneme recognition − Gaussian kernel

Phoneme recognition − Gaussian kernel

0.44
0.42
0.4

Projectron++
PA−I
0.445

0.38

Error on Test Set (%)

Number of Mistakes (%)

0.45

Projectron++
MRBP
PA−I

0.36
0.34
0.32
0.3
0.28

0.44

0.435

0.43

0.425

0.26
0.24
1

1.5

2
2.5
3
Size of the Support Set

3.5

4
4

x 10

(a)

0.42
1

1.5

2
2.5
3
Size of the Support Set

3.5

4
4

x 10

(b)

Figure 10: Average online error (a) and test error (b) for the different algorithms as a function of
the size of the support set on a subset of the timit data set.

8. Discussion
This paper presented two different versions of a bounded online learning algorithm. The algorithms
depend on a parameter that allows one to trade accuracy for sparseness of the solution. The sizeof the solution is always guaranteed to be bounded, although the size of this bound is unknown
before the training begins. Therefore, these algorithms solve the memory explosion problem of
the Perceptron and similar algorithms. Although the size of the support set cannot be determined2663

O RABONA , K ESHET AND C APUTO

before training, practically, for a given target accuracy, the size of the support sets of Projectron or
Projectron++ are much smaller than those of other budget algorithms such as Forgetron and RBP.
The first algorithm, Projectron, is based on the Perceptron algorithm. The empirical performance of Projectron is comparable to that of Perceptron, but with the advantage of a bounded
solution. The second algorithm, Projectron++, introduces the notion of large margin and, for somevalues of η, outperforms the Perceptron algorithm, while assuring a bounded solution. The experimental results suggest that Projectron++ outperforms other online bounded algorithms such as
Forgetron and RBP, with a similar hypothesis size.
There are two unique advantages of Projectron and Projectron++. First, these algorithms canbe extended to the multiclass and the structured output settings. Second, a standard online-to-batch
conversion can be applied to the online bounded solution of these algorithms, resulting in a boundedbatch solution. The major drawback of these algorithms is their time and space complexity, whichis quadratic in the size of the support set. Trying to overcome this acute problem is left for futurework.

Acknowledgments
The authors would like to thank the anonymous reviewers for suggesting a way to improve Theorem
3. This work was supported by EU project DIRAC (FP6-0027787). The authors would like to thankAndy Cotter for proofreading the manuscript.

References
G. Cauwenberghs and T. Poggio. Incremental and decremental support vector machine learning. In
Advances in Neural Information Processing Systems 14, pages 409–415, 2000.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. On the generalization ability of on-line learningalgorithms. IEEE Trans. on Information Theory, 50(9):2050–2057, 2004.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. A second-order perceptron algorithm. SIAM Journal
on Computing, 34(3):640–668, 2005.
N. Cesa-Bianchi, A. Conconi, and C. Gentile. Tracking the best hyperplane with a simple budget
Perceptron. In Proc. of the 19th Conference on Learning Theory, pages 483–498, 2006.
L. Cheng, S. V. N. Vishwanathan, D. Schuurmans, S. Wang, and T. Caelli. Implicit online learningwith kernels. In Advances in Neural Information Processing Systems 19, pages 249–256, 2007.
M. Collins. Discriminative reranking for natural language parsing. In Proc. of the 17th International
Conference on Machine Learning, pages 175–182, 2000.
K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Journalof Machine Learning Research, 3:951–991, 2003.
K. Crammer, J. Kandola, and Y. Singer. Online classification on a budget. In Advances in Neural
Information Processing Systems 16, 2003.
2664

B OUNDED K ERNEL -BASED O NLINE L EARNING

K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and Y. Singer. Online passive-aggressivealgorithms. Journal of Machine Learning Research, 7:551–585, 2006.
L. Csató and M. Opper. Sparse on-line gaussian processes. Neural Computation, 14:641–668, 2002.
F. Cucker and D. X. Zhou. Learning Theory: An Approximation Theory Viewpoint. Cambridge
University Press, New York, NY, USA, 2007.
O. Dekel, S. Shalev-Shwartz, and Y. Singer. The Forgetron: A kernel-based perceptron on a budget.
SIAM Journal on Computing, 37(5):1342–1372, 2007.
T. Downs, K. E. Gates, and A. Masters. Exact simplification of support vectors solutions. Journalof Machine Learning Research, 2:293–297, 2001.
M. F. Duarte and Y. H. Hu. Vehicle classification in distributed sensor networks. Journal of Paralleland Distributed Computing, 64:826–838, 2004.
Y. Engel, S. Mannor, and R. Meir. The kernel recursive least-squares algorithm. IEEE Transactions
on Signal Processing, 52(8):2275–2285, 2004.
Y. Freund and R. E. Schapire. Large margin classification using the Perceptron algorithm. Machine
Learning, pages 277–296, 1999.
C. Gentile. A new approximate maximal margin classification algorithm. Journal of Machine
Learning Research, 2:213–242, 2001.
C. Gentile. The robustness of the p-norm algorithms. Machine Learning, 53(3):265–299, 2003.
J. J. Hull. A database for handwritten text recognition research. IEEE Transactions on PatternAnalysis and Machine Intelligence, 16(5):550–554, 1994.
S. S. Keerthi, D. Decoste, and T. Joachims. A modified finite newton method for fast solution oflarge scale linear svms. Journal of Machine Learning Research, 6:2005, 2005.
J. Kivinen, A. Smola, and R. Williamson. Online learning with kernels. IEEE Trans. on Signal
Processing, 52(8):2165–2176, 2004.
J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient. In Advances in
Neural Information Processing Systems 21, pages 905–912, 2008.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324, November 1998.
L. Lemel, R. Kassel, and S. Seneff. Speech database development: Design and analysis. Report no.
SAIC-86/1546, Proc. DARPA Speech Recognition Workshop, 1986.
F. Orabona. DOGMA: A MATLAB Toolbox for Online Learning, 2009. Software available at http://dogma.sourceforge.net.
F. Orabona, C. Castellini, B. Caputo, J. Luo, and G. Sandini. Indoor place recognition using online
independent support vector machines. In Proc. of the British Machine Vision Conference 2007,
pages 1090–1099, 2007.
2665

O RABONA , K ESHET AND C APUTO

J. C. Platt. Fast training of support vector machines using sequential minimal optimization. In
B. Schölkopf, C. Burges, and A. Smola, editors, Advances in kernel methods – support vector
learning, pages 185–208. MIT Press, Cambridge, MA, USA, 1999.
D. Prokhorov. IJCNN 2001 neural network competition. Technical report, 2001.
F. Rosenblatt. The Perceptron: A probabilistic model for information storage and organization in
the brain. Psychological Review, 65:386–407, 1958.
B. Schölkopf, R. Herbrich, and A. J. Smola. A generalized representer theorem. In Proc. of the 14th
Conference on Computational Learning Theory, pages 416–426, London, UK, 2001. SpringerVerlag.
B. Taskar, C. Guestrin, and D. Koller. Max-margin Markov networks. In Advances in Neural
Information Processing Systems 17, 2003.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun. Support vector machine learning forinterdependent and structured output spaces. In Proc. of the 21st International Conference on
Machine Learning, pages 823–830, 2004.
J. Weston, A. Bordes, and L. Bottou. Online (and offline) on an even tighter budget. In Robert G.
Cowell and Zoubin Ghahramani, editors, Proc. of AISTATS 2005, pages 413–420, 2005.

2666