Journal of Machine Learning Research 7 (2006) 551–585

Submitted 5/05; Published 3/06

Online Passive-Aggressive Algorithms
Koby Crammer∗
Ofer Dekel
Joseph Keshet
Shai Shalev-Shwartz
Yoram Singer†

CRAMMER @ CIS . UPENN . EDU
OFERD @ CS . HUJI . AC . IL
JKESHET @ CS . HUJI . AC . IL
SHAIS @ CS . HUJI . AC . IL
SINGER @ CS . HUJI . AC . IL

School of Computer Science and Engineering
The Hebrew University
Jerusalem, 91904, Israel

Editor: Manfred K. Warmuth

Abstract
We present a family of margin based online learning algorithms for various prediction tasks. In
particular we derive and analyze algorithms for binary and multiclass categorization, regression,
uniclass prediction and sequence prediction. The update steps of our different algorithms are allbased on analytical solutions to simple constrained optimization problems. This unified view allows us to prove worst-case loss bounds for the different algorithms and for the various decision
problems based on a single lemma. Our bounds on the cumulative loss of the algorithms are relative
to the smallest loss that can be attained by any fixed hypothesis, and as such are applicable to both
realizable and unrealizable settings. We demonstrate some of the merits of the proposed algorithms
in a series of experiments with synthetic and real data sets.

1. Introduction
In this paper we describe and analyze several online learning tasks through the same algorithmic
prism. We first introduce a simple online algorithm which we call Passive-Aggressive (PA) for online binary classification (see also (Herbster, 2001)). We then propose two alternative modifications
to the PA algorithm which improve the algorithm’s ability to cope with noise. We provide a unified
analysis for the three variants. Building on this unified view, we show how to generalize the binary
setting to various learning tasks, ranging from regression to sequence prediction.
The setting we focus on is that of online learning. In the online setting, a learning algorithm observes instances in a sequential manner. After each observation, the algorithm predicts an outcome.
This outcome can be as simple as a yes/no (+/−) decision, as in the case of binary classification
problems, and as complex as a string over a large alphabet. Once the algorithm has made a prediction, it receives feedback indicating the correct outcome. Then, the online algorithm may modify
its prediction mechanism, presumably improving the chances of making an accurate prediction on
subsequent rounds. Online algorithms are typically simple to implement and their analysis often
provides tight bounds on their performance (see for instance Kivinen and Warmuth (1997)).
∗. Current affiliation: Department of Computer and Information Science, University of Pennsylvania, 3330 Walnut
Street, Philadelphia, PA 19104, USA.
†. Current affiliation: Google, Moutain View, CA 94043, USA.
c 2006 Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz and Yoram Singer.

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

Our learning algorithms use hypotheses from the set of linear predictors. While this class may
seem restrictive, the pioneering work of Vapnik (1998) and colleagues demonstrates that by using Mercer kernels one can employ highly non-linear predictors and still entertain all the formal
properties and simplicity of linear predictors. For concreteness, our presentation and analysis are
confined to the linear case which is often referred to as the primal version (Vapnik, 1998; Cristianiniand Shawe-Taylor, 2000; Schölkopf and Smola, 2002). As in other constructions of linear kernel
machines, our paradigm also builds on the notion of margin.
Binary classification is the first setting we discuss in the paper. In this setting each instanceis represented by a vector and the prediction mechanism is based on a hyperplane which divides
the instance space into two half-spaces. The margin of an example is proportional to the distance
between the instance and the hyperplane. The PA algorithm utilizes the margin to modify the current
classifier. The update of the classifier is performed by solving a constrained optimization problem:
we would like the new classifier to remain as close as possible to the current one while achieving
at least a unit margin on the most recent example. Forcing a unit margin might turn out to be too
aggressive in the presence of noise. Therefore, we also describe two versions of our algorithm whichcast a tradeoff between the desired margin and the proximity to the current classifier.
The above formalism is motivated by the work of Warmuth and colleagues for deriving online
algorithms (see for instance (Kivinen and Warmuth, 1997) and the references therein). Furthermore,an analogous optimization problem arises in support vector machines (SVM) for classification (Vapnik, 1998). Indeed, the core of our construction can be viewed as finding a support vector machine
based on a single example while replacing the norm constraint of SVM with a proximity constraint
to the current classifier. The benefit of this approach is two fold. First, we get a closed form solution
for the next classifier. Second, we are able to provide a unified analysis of the cumulative loss forvarious online algorithms used to solve different decision problems. Specifically, we derive andanalyze versions for regression problems, uniclass prediction, multiclass problems, and sequence
prediction tasks.
Our analysis is in the realm of relative loss bounds. In this framework, the cumulative loss
suffered by an online algorithm is compared to the loss suffered by a fixed hypothesis that may bechosen in hindsight. Our proof techniques are surprisingly simple and the proofs are fairly shortand easy to follow. We build on numerous previous results and views. The mere idea of deriving an
update as a result of a constrained optimization problem compromising of two opposing terms, hasbeen largely advocated by Littlestone, Warmuth, Kivinen and colleagues (Littlestone, 1989; Kivinen and Warmuth, 1997). Online margin-based prediction algorithms are also quite prevalent. The
roots of many of the papers date back to the Perceptron algorithm (Agmon, 1954; Rosenblatt, 1958;
Novikoff, 1962). More modern examples include the ROMMA algorithm of Li and Long (2002),
Gentile’s ALMA algorithm (Gentile, 2001), the MIRA algorithm (Crammer and Singer, 2003b), andthe NORMA algorithm (Kivinen et al., 2002). The MIRA algorithm is closely related to the work
presented in this paper, and specifically, the MIRA algorithm for binary classification is identical to
our basic PA algorithm. However, MIRA was designed for separable binary and multiclass problems whereas our algorithms also apply to nonseparable problems. Furthermore, the loss bounds
derived in Crammer and Singer (2003b) are inferior and less general than the bounds derived in thispaper. The NORMA algorithm also shares a similar view of classification problems. Rather thanprojecting the current hypothesis onto the set of constraints induced by the most recent example,
NORMA’s update rule is based on a stochastic gradient approach (Kivinen et al., 2002). Of all thework on online learning algorithms, the work by Herbster (2001) is probably the closest to the work
552

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

presented here. Herbster describes and analyzes a projection algorithm that, like MIRA, is essentially the same as the basic PA algorithm for the separable case. We surpass MIRA and Herbster’salgorithm by providing bounds for both the separable and the nonseparable settings using a unified
analysis. As mentioned above we also extend the algorithmic framework and the analysis to more
complex decision problems.
The paper is organized as follows. In Sec. 2 we formally introduce the binary classification
problem and in the next section we derive three variants of an online learning algorithm for thissetting. The three variants of our algorithm are then analyzed in Sec. 4. We next show how tomodify these algorithms to solve regression problems (Sec. 5) and uniclass prediction problems(Sec. 6). We then shift gears to discuss and analyze more complex decision problems. Specifically,in Sec. 7 we describe a generalization of the algorithms to multiclass problems and further extend
the algorithms to cope with sequence prediction problems (Sec. 9). We describe experimental resultswith binary and multiclass problems in Sec. 10 and conclude with a discussion of future directionsin Sec. 11.

2. Problem Setting
As mentioned above, the paper describes and analyzes several online learning tasks through thesame algorithmic prism. We begin with binary classification which serves as the main building blockfor the remainder of the paper. Online binary classification takes place in a sequence of rounds. On
each round the algorithm observes an instance and predicts its label to be either +1 or −1. After theprediction is made, the true label is revealed and the algorithm suffers an instantaneous loss whichreflects the degree to which its prediction was wrong. At the end of each round, the algorithm uses
the newly obtained instance-label pair to improve its prediction rule for the rounds to come.
We denote the instance presented to the algorithm on round t by xt , and for concreteness weassume that it is a vector in Rn . We assume that xt is associated with a unique label yt ∈ {+1, −1}.
We refer to each instance-label pair (xt , yt ) as an example. The algorithms discussed in this paper
make predictions using a classification function which they maintain in their internal memory andupdate from round to round. We restrict our discussion to classification functions based on a vectorof weights w ∈ Rn , which take the form sign(w · x). The magnitude |w · x| is interpreted as thedegree of confidence in this prediction. The task of the algorithm is therefore to incrementally learn
the weight vector w. We denote by wt the weight vector used by the algorithm on round t, and referto the term yt (wt · xt ) as the (signed) margin attained on round t. Whenever the margin is a positive
number then sign(wt · xt ) = yt and the algorithm has made a correct prediction. However, we are notsatisfied by a positive margin value and would additionally like the algorithm to predict with highconfidence. Therefore, the algorithm’s goal is to achieve a margin of at least 1 as often as possible.
On rounds where the algorithm attains a margin less than 1 it suffers an instantaneous loss. This
loss is defined by the following hinge-loss function,0y(w · x) ≥ 1ℓ w; (x, y) =.
(1)
1 − y(w · x) otherwise
Whenever the margin exceeds 1, the loss equals zero. Otherwise, it equals the difference between
the margin value and 1. We note in passing that the choice of 1 as the margin threshold below whicha loss is suffered is rather arbitrary. In Sec. 5 we generalize the hinge-loss function in the context
of regression problems, by letting the threshold be a user-defined parameter. We abbreviate the loss
553

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER


suffered on round t by ℓt , that is, ℓt = ℓ wt ; (xt , yt ) . The algorithms presented in this paper will
be shown to attain a small cumulative squared loss over a given sequence of examples. In otherTwords, we will prove different bounds on ∑t=1
ℓt2 , where T is the length of the sequence. Notice that2
whenever a prediction mistake is made then ℓt ≥ 1 and therefore a bound on the cumulative squared
loss also bounds the number of prediction mistakes made over the sequence of examples.

3. Binary Classification Algorithms
In the previous section we described a general setting for binary classification. To obtain a concretealgorithm we must determine how to initialize the weight vector w1 and we must define the update
rule used to modify the weight vector at the end of each round. In this section we present threevariants of an online learning algorithm for binary classification. The pseudo-code for the threevariants is given in Fig. 1. The vector w1 is initialized to (0, . . . , 0) for all three variants, howevereach variant employs a different update rule. We focus first on the simplest of the three, which on
round t sets the new weight vector wt+1 to be the solution to the following constrained optimization
problem,1
wt+1 = argmin kw − wt k2 s.t. ℓ(w; (xt , yt )) = 0.
(2)w∈Rn 2
Geometrically, wt+1 is set to be the projection of wt onto the half-space of vectors which attain ahinge-loss of zero on the current example. The resulting algorithm is passive whenever the hingeloss is zero, that is, wt+1 = wt whenever ℓt = 0. In contrast, on those rounds where the loss is
positive, the algorithm aggressively forces wt+1 to satisfy the constraint ℓ(wt+1 ; (xt , yt )) = 0 regardless of the step-size required. We therefore name the algorithm Passive-Aggressive or PA for
short.
The motivation for this update stems from the work of Helmbold et al. (Helmbold et al., 1999)
who formalized the trade-off between the amount of progress made on each round and the amountof information retained from previous rounds. On one hand, our update requires wt+1 to correctlyclassify the current example with a sufficiently high margin and thus progress is made. On the other
hand, wt+1 must stay as close as possible to wt , thus retaining the information learned on previous
rounds.
The solution to the optimization problem in Eq. (2) has a simple closed form solution,
wt+1 = wt + τt yt xt where τt =ℓt.
kxt k2(3)

We now show how this update is derived using standard tools from convex analysis (see for instance(Boyd and Vandenberghe, 2004)). If ℓt = 0 then wt itself satisfies the constraint in Eq. (2) and isclearly the optimal solution. We therefore concentrate on the case where ℓt > 0. First, we define theLagrangian of the optimization problem in Eq. (2) to be,

L (w, τ) =

1kw − wt k2 + τ 1 − yt (w · xt ) ,2(4)

where τ ≥ 0 is a Lagrange multiplier. The optimization problem in Eq. (2) has a convex objectivefunction and a single feasible affine constraint. These are sufficient conditions for Slater’s condition
to hold therefore finding the problem’s optimum is equivalent to satisfying the Karush-Khun-Tucker
554

O NLINE PASSIVE -AGGRESSIVE A LGORITHMSI NPUT: aggressiveness parameter C > 0
I NITIALIZE : w1 = (0, . . . , 0)
For t = 1, 2, . . .
• receive instance: xt ∈ Rn
• predict: ŷt = sign(wt · xt )• receive correct label: yt ∈ {−1, +1}• suffer loss: ℓt = max{0 , 1 − yt (wt · xt )}• update:
1. set:(PA)τt = kxℓttk2noτt = min C , kxℓttk2(PA-I)

τt = kx kℓ2t+ 1
t(PA-II)

2C

2. update: wt+1 = wt + τt yt xt
Figure 1: Three variants of the Passive-Aggressive algorithm for binary classification.
conditions (Boyd and Vandenberghe, 2004). Setting the partial derivatives of L with respect to theelements of w to zero gives,
0 = ∇w L (w, τ) = w − wt − τyt xt=⇒

w = wt + τyt xt .

(5)

Plugging the above back into Eq. (4) we get,1
2

L (τ) = − τ2 kxt k2 + τ 1 − yt (wt · xt ) .
Taking the derivative of L (τ) with respect to τ and setting it to zero, we get,0 =

∂L (τ)= − τkxt k2 + 1 − yt (wt · xt )
∂τ

=⇒

τ=

1 − yt (wt · xt ).
kxt k2Since we assumed that ℓt > 0 then ℓt = 1 − yt (w · xt ). In summary, we can state a unified update forthe case where ℓt = 0 and the case where ℓt > 0 by setting τt = ℓt /kxt k2 .
As discussed above, the PA algorithm employs an aggressive update strategy by modifying theweight vector by as much as needed to satisfy the constraint imposed by the current example. In
certain real-life situations this strategy may also result in undesirable consequences. Consider for
instance the common phenomenon of label noise. A mislabeled example may cause the PA algorithm to drastically change its weight vector in the wrong direction. A single mislabeled example
can lead to several prediction mistakes on subsequent rounds. To cope with such problems, we
present two variations on the PA update that employ gentler update strategies. We adopt the technique previously used to derive soft-margin classifiers (Vapnik, 1998) and introduce a non-negative
slack variable ξ into the optimization problem defined in Eq. (2). This variable can be introduced in
two different ways. First, we consider the update where the objective function scales linearly with555

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

ξ, namely,1
wt+1 = argmin kw − wt k2 + Cξw∈Rn 2s.t. ℓ(w; (xt , yt )) ≤ ξ and ξ ≥ 0.

(6)

Here C is a positive parameter which controls the influence of the slack term on the objective function. Specifically, we will show that larger values of C imply a more aggressive update step and wetherefore refer to C as the aggressiveness parameter of the algorithm. We term the algorithm which
results from this update PA-I .
Alternatively, we can have the objective function scale quadratically with ξ, resulting in thefollowing constrained optimization problem,1
wt+1 = argmin kw − wt k2 + Cξ2w∈Rn 2s.t. ℓ(w; (xt , yt )) ≤ ξ.

(7)

Note that the constraint ξ ≥ 0 which appears in Eq. (6) is no longer necessary since ξ2 is always
non-negative. We term the algorithm which results from this update PA-II . As with PA-I , C is apositive parameter which governs the degree to which the update of PA-II is aggressive. The updatesof PA-I and PA-II also share the simple closed form wt+1 = wt + τt yt xt , where


ℓt
ℓt
(PA-I)orτt =τt = min C ,(PA-II).
(8)
1
2
2
kxt k
kxt k + 2C
A detailed derivation of the PA-I and PA-II updates is provided in Appendix A. It is worth notingthat thep
PA-II update is equivalent to increasing the dimension of each xt from n to n + T , setting
xn+t = 1/2C, setting the remaining T − 1 new coordinates to zero, and then using the simple
PA update. This technique was previously used to derive noise-tolerant online algorithms in (Klasner and Simon, 1995; Freund and Schapire, 1999). We do not use this observation explicitly in thispaper, since it does not lead to a tighter analysis.
Up until now, we have restricted our discussion to linear predictors of the form sign(w · x). We
can easily generalize any of the algorithms presented in this section using Mercer kernels. Simply
note that for all three PA variants,
t−1

wt = ∑ τt yt xt ,i=1

and therefore,
t−1

wt · xt = ∑ τt yt (xi · xt ).
i=1

The inner product on the right hand side of the above can be replaced with a general Mercer kernel
K(xi , xt ) without otherwise changing our derivation. Additionally, the formal analysis presented in
the next section also holds for any kernel operator.

4. Analysis
In this section we prove relative loss bounds for the three variants of the PA algorithm presented in
the previous section. Specifically, most of the theorems in this section relate the cumulative squared
loss attained by our algorithms on any sequence of examples with the loss attained by an arbitrary
556

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

fixed classification function of the form sign(u · x) on the same sequence. As previously mentioned,
the cumulative squared hinge loss upper bounds the number of prediction mistakes. Our bounds
essentially prove that, for any sequence of examples, our algorithms cannot do much worse than thebest fixed predictor chosen in hindsight.
To simplify the presentation we use two abbreviations throughout this paper. As before wedenote by ℓt the instantaneous loss suffered by our algorithm on round t. In addition, we denoteby ℓt⋆ the loss suffered by the arbitrary fixed predictor to which we are comparing our performance.
Formally, let u be an arbitrary vector in Rn , and defineℓt = ℓ wt ; (xt , yt )andℓt⋆ = ℓ u; (xt , yt ) .

(9)

We begin with a technical lemma which facilitates the proofs in this section. With this lemma
handy, we then derive loss and mistake bounds for the variants of the PA algorithm presented in theprevious section.
Lemma 1 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ Rn and yt ∈ {+1, −1} forall t. Let τt be as defined by either of the three PA variants given in Fig. 1. Then using the notation
given in Eq. (9), the following bound holds for any u ∈ Rn ,T

∑ τt 2ℓt − τt kxt k2 − 2ℓt⋆t=1

≤ kuk2 .

Proof Define ∆t to be kwt − uk2 − kwt+1 − uk2 . We prove the lemma by summing ∆t over all t
in 1, . . . , T and bounding this sum from above and below. First note that ∑t ∆t is a telescopic sum
which collapses to,
T

T

∑ ∆t

t=1

=

∑ kwt − uk2 − kwt+1 − uk2

t=1= kw1 − uk2 − kwT +1 − uk2 .

Using the facts that w1 is defined to be the zero vector and that kwT +1 − uk2 is non-negative, we
can upper bound the right-hand side of the above by kuk2 and conclude that,T∑ ∆t ≤ kuk2 .

(10)

t=1

We now turn to bounding ∆t from below. If the minimum margin requirement is not violated onround t, i.e. ℓt = 0, then τt = 0 and therefore ∆t = 0. We can therefore focus only on rounds forwhich ℓt > 0. Using the definition wt+1 = wt + yt τt xt , we can write ∆t as,∆t= kwt − uk2 − kwt+1 − uk2= kwt − uk2 − kwt − u + yt τt xt k2= kwt − uk2 − kwt − uk2 + 2τt yt (wt − u) · xt + τt2 kxt k2= −2τt yt (wt − u) · xt − τt2 kxt k2 .
557



(11)

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

Since we assumed that ℓt > 0 then ℓt = 1 − yt (wt · xt ) or alternatively yt (wt · xt ) = 1 − ℓt . In addition,
the definition of the hinge loss implies that ℓt⋆ ≥ 1 − yt (u · xt ), hence yt (u · xt ) ≥ 1 − ℓt⋆ . Using these
two facts back in Eq. (11) gives,∆t≥ 2τt ((1 − ℓt⋆ ) − (1 − ℓt )) − τt2 kxt k2
= τt 2ℓt − τt kxt k2 − 2ℓt⋆ .

(12)Summing ∆t over all t and comparing the lower bound of Eq. (12) with the upper bound in Eq. (10)proves the lemma.
We first prove a loss bound for the PA algorithm in the separable case. This bound was previously presented by Herbster (2001) and is analogous to the classic mistake bound for the Perceptron
algorithm due to Novikoff (1962). We assume that there exists some u ∈ Rn such that yt (u · xt ) > 0
for all t ∈ {1, . . . , T }. Without loss of generality we can assume that u is scaled such that thatyt (u · xt ) ≥ 1 and therefore u attains a loss of zero on all T examples in the sequence. With thevector u at our disposal, we prove the following bound on the cumulative squared loss of PA .
Theorem 2 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ Rn , yt ∈ {+1, −1} andkxt k ≤ R for all t. Assume that there exists a vector u such that ℓt⋆ = 0 for all t. Then, the cumulativesquared loss of PA on this sequence of examples is bounded by,T∑ ℓt2 ≤ kuk2 R2 .

t=1

Proof Since ℓt⋆ = 0 for all t, Lemma 1 implies that,T∑ τt 2ℓt − τt kxt k2

t=1

≤ kuk2 .

(13)

Using the definition of τt for the PA algorithm in the left-hand side of the above gives,T∑ ℓt2 /kxt k2 ≤ kuk2 .

t=1

Now using the fact that kxt k2 ≤ R2 for all t, we get,T

∑ ℓt2 /R2 ≤ kuk2 .

t=1

Multiplying both sides of this inequality by R2 gives the desired bound.
The remaining bounds we prove in this section do not depend on a separability assumption.
In contrast to the assumptions of Thm. 2, the vector u which appears in the theorems below is anarbitrary vector in Rn and not necessarily a perfect separator. The first of the following theorems
bounds the cumulative squared loss attained by the PA algorithm in the special case where all of558

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

the instances in the input sequence are normalized so that kxt k2 = 1. Although this assumption
is somewhat restrictive, it is often the case in many practical applications of classification that the
instances are normalized. For instance, certain kernel operators, such as the Gaussian kernel, imply
that all input instances have a unit norm. See for example (Cristianini and Shawe-Taylor, 2000).
Theorem 3 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ Rn , yt ∈ {+1, −1} andkxt k = 1 for all t. Then for any vector u ∈ Rn the cumulative squared loss of PA on this sequenceof examples is bounded from above by,
T

∑


2
q
T
⋆
2
≤ kuk + 2 ∑t=1 (ℓt )
.

ℓt2

t=1

Proof In the special case where kxt k2 = 1, τt and ℓt are equal. Therefore, Lemma 1 gives us that,
T

T

t=1

t=1

∑ ℓt2 ≤ kuk2 + 2 ∑ ℓt ℓt⋆ .

Using the Cauchy-Schwartz inequality to upper bound the right-hand side of the above inequality,and denoting
q
q
LT =

T
ℓt2
∑t=1

and

UT =

T
(ℓt⋆ )2 ,
∑t=1

(14)

we get that LT2 ≤ kuk2 + 2LT UT . The largest value of LT for which this inequality is satisfied is thelarger of the two values for which this inequality holds with equality. That is, to obtain an upperbound on LT we need to find the largest root of the second degree polynomial LT2 − 2UT LT − kuk2 ,which is,q
UT +Using the fact that

UT2 + kuk2 .

pp√
α + β ≤ α + β, we conclude thatLT ≤ kuk + 2UT .

(15)Taking the square of both sides of this inequality and plugging in the definitions of LT and UT from
Eq. (14) gives the desired bound.
Next we turn to the analysis of PA-I . The following theorem does not provide a loss bound but
rather a mistake bound for the PA-I algorithm. That is, we prove a direct bound on the number oftimes yt 6= sign(wt · xt ) without using ∑ ℓt2 as a proxy.
Theorem 4 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ Rn , yt ∈ {+1, −1} andkxt k ≤ R for all t. Then, for any vector u ∈ Rn , the number of prediction mistakes made by PA-I on
this sequence of examples is bounded from above by,!
T 2
kuk2 + 2C ∑ ℓt⋆ ,max R , 1/C
t=1

where C is the aggressiveness parameter provided to PA-I (Fig. 1) .
559

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

Proof If PA-I makes a prediction mistake on round t then ℓt ≥ 1. Using our assumption thatkxt k2 ≤ R2 and the definition τt = min{ℓt /kxt k2 ,C}, we conclude that if a prediction mistake occurs
then it holds that,min{1/R2 ,C} ≤ τt ℓt .
Let M denote the number of prediction mistakes made on the entire sequence. Since τt ℓt is always
non-negative, it holds that,T

min{1/R2 ,C} M ≤ ∑ τt ℓt .

(16)

t=1

Again using the definition of τt , we know that τt ℓt⋆ ≤ Cℓt⋆ and that τt kxt k2 ≤ ℓt . Plugging these two
inequalities into Lemma 1 gives,
T

T

t=1

t=1

∑ τt ℓt ≤ kuk2 + 2C ∑ ℓt⋆ .

(17)

Combining Eq. (16) with Eq. (17), we conclude that,T

min{1/R2 ,C} M ≤ kuk2 + 2C ∑ ℓt⋆ .
t=1

The theorem follows from multiplying both sides of the above by max{R2 , 1/C}.
Finally, we turn to the analysis of PA-II . As before, the proof of the following theorem is based on
Lemma 1.
Theorem 5 Let (x1 , y1 ), . . . , (xT , yt ) be a sequence of examples where xt ∈ Rn , yt ∈ {+1, −1} andkxt k2 ≤ R2 for all t. Then for any vector u ∈ Rn it holds that the cumulative squared loss of PA-II on
this sequence of examples is bounded by,
!


T
T
1
∑ ℓt2 ≤ R2 + 2C kuk2 + 2C ∑ (ℓt⋆ )2 ,t=1
t=1
where C is the aggressiveness parameter provided to PA-II (Fig. 1) .
Proof Recall that Lemma 1 states that,T
kuk2 ≥ ∑ 2τt ℓt − τt2 kxt k2 − 2τt ℓt⋆ .
t=1√
Defining α = 1/ 2C, we subtract the non-negative term (ατt − ℓt⋆ /α)2 from each summand on theright-hand side of the above inequality, to get
kuk2 ≥=

T∑ 2τt ℓt − τt2 kxt k2 − 2τt ℓt⋆ − (ατt − ℓt⋆ /α)2t=1T

∑ 2τt ℓt − τt2 kxt k2 − 2τt ℓt⋆ − α2 τt2 + 2τt ℓt⋆ − (ℓt⋆ )2 /α2

t=1
T

=



∑ 2τt ℓt − τt2 (kxt k2 + α2 ) − (ℓt⋆)2 /α2 .


t=1

560



O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

Plugging in the definition of α, we obtain the following lower bound,
T





1
2
2
⋆ 2
− 2C(ℓt ) .
kuk ≥ ∑ 2τt ℓt − τt kxt k +
2C
t=1
2

Using the definition τt = ℓt /(kxt k2 + 1/(2C)), we can rewrite the above as,
!
T
ℓt2
⋆ 2
2
− 2C(ℓt ) .
kuk ≥ ∑
1
2
t=1 kxt k + 2C
Replacing kxt k2 with its upper bound of R2 and rearranging terms gives the desired bound.
We conclude this section with a brief comparison of our bounds to previously published bounds
for the Perceptron algorithm. As mentioned above, the bound in Thm. 2 is equal to the bound of
Novikoff (1962) for the Perceptron in the separable case. However, Thm. 2 bounds the cumulativesquared hinge loss of PA , whereas Novikoff’s bound is on the number of prediction mistakes.
Gentile (2002) proved a mistake bound for the Perceptron in the nonseparable case which can becompared to our mistake bound for PA-I in Thm. 4. Using our notation from Thm. 4, Gentile bounds
the number of mistakes made by the Perceptron by,r
R2 kuk22T+ ∑t=1ℓt⋆ +T
R2 kuk2 ∑t=1ℓt⋆ +R2 kuk2
2

At the price of a slightly loosening this bound, we can use the inequality
the simpler bound,
q

2

.

√
√
√
a + b ≤ a + b to get

T
T
ℓt⋆ .
R2 kuk2 + ∑t=1
ℓt⋆ + Rkuk ∑t=1

With C = 1/R2 , our bound in Thm. 4 becomes,

TR2 kuk2 + 2 ∑ ℓt⋆ .
t=1

q

T
Thus, our bound is inferior to Gentile’s when Rkuk < ∑t=1
ℓt⋆ , and even then by a factor of at
most 2.
The loss bound for PA-II in Thm. 5 can be compared with the bound of Freund and Schapire(1999) for the Perceptron algorithm. Using the notation defined in Thm. 5, Freund and Schapire
bound the number of incorrect predictions made by the Perceptron by,

2

q
T
(ℓt⋆ )2 .
Rkuk + ∑t=1
It can be easily verified that the bound for the PA-II algorithm given
p in Thm. 5 exactly equals theabove bound of Freund and Schapire when C is set to kuk/(2R ∑t (ℓt⋆ )2 ). Moreover, this is the
optimal choice of C. However, we bound the cumulative squared hinge-loss of PA-II whereas thebound of Freund and Schapire is on the number of mistakes.
561

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

5. Regression
In this section we show that the algorithms described in Sec. 3 can be modified to deal with online
regression problems. In the regression setting, every instance xt is associated with a real target
value yt ∈ R, which the online algorithm tries to predict. On every round, the algorithm receives
an instance xt ∈ Rn and predicts a target value ŷt ∈ R using its internal regression function. We
focus on the class of linear regression functions, that is, ŷt = wt · xt where wt is the incrementallylearned vector. After making a prediction, the algorithm is given the true target value yt and suffers
an instantaneous loss. We use the ε-insensitive hinge loss function:
0|w · x − y| ≤ εℓε w; (x, y) =,(18)
|w · x − y| − ε otherwise

where ε is a positive parameter which controls the sensitivity to prediction mistakes. This loss iszero when the predicted target deviates from the true target by less than ε and otherwise grows
linearly with |ŷt − yt |. At the end of every round, the algorithm uses wt and the example (xt , yt ) to
generate a new weight vector wt+1 , which will be used to extend the prediction on the next round.
We now describe how the various PA algorithms from Sec. 3 can be adapted to learn regression
problems. As in the case of classification, we initialize w1 to (0, . . . , 0). On each round, the PA
regression algorithm sets the new weight vector to be,1(19)
wt+1 = argmin kw − wt k2 s.t. ℓε w; (xt , yt ) = 0,w∈Rn 2In the binary classification setting, we gave the PA update the geometricinterpretation of projecting
wt onto the linear half-space defined by the constraint ℓ w; (xt , yt ) = 0. For regression problems,
the set {w ∈ Rn : ℓε (w, zt ) = 0} is not a half-space but rather a hyper-slab of width 2ε. Geometrically, the PA algorithm for regression projects wt onto this hyper-slab at the end of every round.
Using the shorthand ℓt = ℓε (wt ; (xt , yt )), the update given in Eq. (19) has a closed form solution
similar to that of the classification PA algorithm of the previous section, namely,
wt+1 = wt + sign(yt − ŷt )τt xt

whereτt = ℓt /kxt k2 .

We can also obtain the PA-I and PA-II variants for online regression by introducing a slack
variable into the optimization problem in Eq. (19), as we did for classification in Eq. (6) and Eq. (7).
The closed form solution for these updates also comes out to be wt+1 = wt + sign(yt − ŷt )τt xt whereτt is defined as in Eq. (8). The derivations of these closed-form updates are almost identical to thatof the classification problem in Sec. 3.
We now turn to the analysis of the three PA regression algorithms described above. We would
like to show that the analysis given in Sec. 4 for the classification algorithms also holds for theirregression counterparts. To do so, it suffices to show that Lemma 1 still holds for regression problems. After obtaining a regression version of Lemma 1, regression versions of Thm. 2 throughThm. 5 follow as immediate corollaries.
Lemma 6 Let (x1 , y1 ), . . . , (xT , yT ) be an arbitrary sequence of examples, where xt ∈ Rn and yt ∈ R
for all t. Let τt be as defined in either of the three PA variants for regression problems. Then using
the notation given in Eq. (9), the following bound holds for any u ∈ Rn ,T

∑ τt 2ℓt − τt kxt k2 − 2ℓt⋆

t=1

562



≤ kuk2 .

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

Proof The proof of this lemma follows that of Lemma 1 and therefore subtleties which were discussed in detail in that proof are omitted here. Again, we use the definition∆t = kwt − uk2 − kwt+1 − uk2
and the same argument used in Lemma 1 implies that,T∑ ∆t ≤ kuk2 ,t=1

We focus our attention on bounding ∆t from below on those rounds where ∆t 6= 0. Using therecursive definition of wt+1 , we rewrite ∆t as,∆t= kwt − uk2 − kwt − u + sign(yt − ŷt )τt xt k2= −sign(yt − ŷt )2τt (wt − u) · xt − τt2 kxt k2

We now add and subtract the term sign(yt − ŷt )2τt yt from the right-hand side above to get the bound,∆t ≥ − sign(yt − ŷt )2τt (wt · xt − yt ) + sign(yt − ŷt )2τt (u · xt − yt ) − τt2 kxt k2 .

(20)

Since wt · xt = ŷt , we have that −sign(yt − ŷt )(wt · xt − yt ) = |wt · xt − yt |. We only need to consider
the case where ∆t 6= 0, so ℓt = |wt · xt − yt | − ε and we can rewrite the bound in Eq. (20) as,∆t ≥ 2τt (ℓt + ε) + sign(yt − ŷt )2τt (u · xt − yt ) − τt2 kxt k2 .
We also know that sign(yt − ŷt )(u · xt − yt ) ≥ −|u · xt − yt | and that −|u · xt − yt | ≥ −(ℓt⋆ + ε). This
enables us to further bound,∆t ≥ 2τt (ℓt + ε) − 2τt (ℓt⋆ + ε) − τt2 kxt k2 = τt (2ℓt − τt kxt k2 − 2ℓt⋆ ).
Summing the above over all t and comparing to the upper bound discussed in the beginning of thisproof proves the lemma.

6. Uniclass Prediction
In this section we present PA algorithms for the uniclass prediction problem. This task involves
predicting a sequence of vectors y1 , y2 , · · · where yt ∈ Rn . Uniclass prediction is fundamentally different than classification and regression as the algorithm makes predictions without first observing
any external input (such as the instance xt ). Specifically, the algorithm maintains in its memory avector wt ∈ Rn and simply predicts the next element of the sequence to be wt . After extending thisprediction, the next element in the sequence is revealed and an instantaneous loss is suffered. We
measure loss using the following ε-insensitive loss function:0kw − yk ≤ εℓε (w; y) =.
(21)
kw − yk − ε otherwise
As in the regression setting, ε is a positive user-defined parameter. If the prediction is within ε of thetrue sequence element then no loss is suffered. Otherwise the loss is proportional to the Euclidean563

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

distance between the prediction and the true vector. At the end of each round wt is updated in orderto have a potentially more accurate prediction on where the next element in the sequence will fall.
Equivalently, we can think of uniclass prediction as the task of finding a center-point w such that as
many vectors in the sequence fall within a radius of ε from w. At the end of this section we discussa generalization of this problem, where the radius ε is also determined by the algorithm.
As before, we initialize w1 = (0, . . . , 0). Beginning with the PA algorithm, we define the update
for the uniclass prediction algorithm to be,1
wt+1 = argmin kw − wt k2
w∈Rn 2s.t. ℓε (w; yt ) = 0,(22)

Geometrically, wt+1 is set to be the projection of wt onto a ball of radius ε about yt . We now showthat the closed form solution of this optimization problem turns out to be,




ℓt
ℓt
wt +
yt .
(23)
wt+1 = 1 −kwt − yt k
kwt − yt k
First, we rewrite the above equation and express wt+1 by,
wt+1 = wt + τtyt − wt,
kyt − wt k

(24)

where τt = ℓt . In the Uniclass problem the KKT conditions are both sufficient and necessary for
optimality. Therefore, we prove that Eq. (24) is the minimizer of Eq. (22) by verifying that the KKT
conditions indeed hold. The Lagrangian of Eq. (22) is,1
kw − wt k2 + τ (kw − yt k − ε) ,(25)
2where τ ≥ 0 is a Lagrange multiplier. Differentiating with respect to the elements of w and settingthese partial derivatives to zero, we get the first KKT condition, stating that at the optimum (w, τ)
must satisfy the equality,

L (w, τ) =0 = ∇w L (w, τ) = w − wt + τ

w − yt.
kw − yt k(26)

In addition, an optimal solution must satisfy the conditions τ ≥ 0 and,
τ (kw − yt k − ε) = 0.

(27)

Clearly, τt ≥ 0. Therefore, to show that wt+1 is the optimum of Eq. (22) it suffices to prove that
(wt+1 , τt ) satisfies Eq. (26) and Eq. (27). These equalities trivially hold if ℓt = 0 and therefore fromnow on we assume that ℓt > 0. Plugging the values w = wt+1 and τ = τt in the right-hand side ofEq. (26) gives,
wt+1 − yt
yt − wt
wt+1 − yt
.
(28)
= τt
+
wt+1 − wt + τt
kwt+1 − yt kkyt − wt k kwt+1 − yt k
Note that,
wt+1 − ytyt − wt
1= wt + τt− yt = (wt − yt ) 1 − τtkyt − wt kkyt − wt kε
wt − yt(kwt − yt k − τt ) =(wt − yt ).
=kwt − yt k
kwt − yt k
564

(29)

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

Combining Eq. (29) with Eq. (28) we get that,
wt+1 − wt + τt

wt+1 − yt= 0,
kwt+1 − yt k

and thus Eq. (26) holds for (wt+1 , τt ). Similarly,
kwt+1 − yt k − ε = ε − ε = 0,
and thus Eq. (27) also holds. In summary, we have shown that the KKT optimality conditions holdfor (wt+1 , τt ) and therefore Eq. (24) gives the desired closed-form update.
To obtain uniclass versions of PA-I and PA-II , we add a slack variable to the optimization
problem in Eq. (22) in the same way as we did in Eq. (6) and Eq. (7) for the classification algorithms.
Namely, the update for PA-I is defined by,1
wt+1 = argmin kw − wt k2 +Cξ
w∈Rn 2s.t. kw − yt k ≤ ε + ξ, ξ ≥ 0,(30)

and the update for PA-II is,1
wt+1 = argmin kw − wt k2 +Cξ2nw∈R 2

s.t. kw − yt k ≤ ε + ξ.

The closed form for these updates can be derived using the same technique as we used forderiving the PA update. The final outcome is that both PA-I and PA-II share the form of update
given in Eq. (24), with τt set to be,τt = min { C , ℓt } (PA-I)

or

τt =

ℓt
(PA-II).
1
1 + 2CWe can extend the analysis of the three PA variants from Sec. 4 to the case of uniclass prediction.
We do so by proving a uniclass version of Lemma 1. After proving this lemma, we discuss anadditional technical difficulty which needs to be addressed so that Thm. 2 through Thm. 5 carryover smoothly to the uniclass case.
Lemma 7 Let y1 , . . . , yT be an arbitrary sequence of vectors, where yt ∈ Rn for all t. Let τt be as
defined in either of the three PA variants for uniclass prediction. Then using the notation given in
Eq. (9), the following bound holds for any u ∈ Rn ,T

∑ τt (2ℓt − τt − 2ℓt⋆ ) ≤ kuk2 .

t=1

Proof We prove this lemma in much the same way as we did Lemma 1. We again use the definition,∆t = kwt − uk2 − kwt+1 − uk2 , along with the fact stated in Eq. (10) thatT

∑ ∆t ≤ kuk2 .

t=1

565

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

We now focus our attention on bounding ∆t from below on those rounds where ∆t 6= 0. Using therecursive definition of wt+1 , we rewrite ∆t as,
∆t




2
τt
τt
wt +
yt − ukwt − yt k
kwt − yt k


2
τt
2
(yt − wt )= kwt − uk − (wt − u) +kwt − yt k


τt
= −2
(wt − u) · (yt − wt ) − τt2 .
kwt − yt k= kwt − uk − 1 −2

We now add and subtract yt from the term (wt − u) above to get,τt∆t = −2(wt − yt + yt − u) · (yt − wt ) − τt2
kwt − yt kτt
(yt − u) · (yt − wt ) − τt2 .
= 2τt kwt − yt k − 2
kwt − yt kNow, using the Cauchy-Schwartz inequality on the term (yt − u) · (yt − wt ), we can bound,∆t ≥ 2τt kwt − yt k − 2τt kyt − uk − τt2 .
We now add and subtract 2τt ε from the right-hand side of the above, to get,∆t ≥ 2τt (kwt − yt k − ε) − 2τt (kyt − uk − ε) − τt2 .
Since we are dealing with the case where ℓt > 0, it holds that ℓt = kwt − yt k − ε. By definition,ℓt⋆ ≥ ku − yt k − ε. Using these two facts, we get,∆t ≥ 2τt ℓt − 2τt ℓt⋆ − τt2 .
Summing the above inequality over all t and comparing the result to the upper bound in Eq. (10)gives the bound stated in the lemma.
As mentioned above, there remains one more technical obstacle which stands in the way of
applying Thm. 2 through Thm. 5 to the uniclass case. This difficulty stems from the fact xt is notdefined in the uniclass whereas the term kxk2 appears in the theorems. This issue is easily resolved
by setting xt in the uniclass case to be an arbitrary vector of a unit length, namely kxt k2 = 1. This
technical modification enables us to write τt as ℓt /kxt k2 in the uniclass PA algorithm, as in theclassification case. Similarly, τt can be defined as in the classification case for PA-I and PA-II .
Now Thm. 2 through Thm. 5 can be applied verbatim to the uniclass PA algorithms.
Learning the Radius of the Uniclass Predictor In the derivation above we made the simplifying
assumption that ε, the radius of our uniclass predictor, is fixed beforehand and that the online algorithm can only move its center, w. We now show that learning ε and w in parallel is no harder thanlearning w alone. We do so by using a simple reduction argument. For technical reasons, we stillrequire an upper bound on ε, which we denote by B. Although B is specified ahead of time, it can
566

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

be arbitrarily large and does not appear in our analysis. Typically, we will think of B as being far
greater than any conceivable value of ε. Our goal is now to incrementally find wt and εt such that,kwt − yt k ≤ εt ,(31)

as often as possible. Additionally, we would like εt to stay relatively small, since an extremely
large value of εt would solve the problem in a trivial way. We do so by reducing this problem to adifferent uniclass problem where the radius is fixed and where yt is in Rn+1 . That is, by adding an
additional dimension to the problem, we can learn ε using the same machinery developed for fixedradius uniclass problems. The reduction stems from the observation that Eq. (31) can be written
equivalently as,(32)kwt − yt k2 + (B2 − εt2 ) ≤ B2 .
If we were to concatenate a 0 to the end of every yt (thus increasing
p its dimension to n + 1) and
if we considered the n + 1’th coordinate of wt to be equivalent to B2 − εt2 , then Eq. (32) simply
becomes kwt − yt k2 ≤ B2 . Our problem has reduced to a fixed-radius uniclass problem where theradius is set to B. w1,n+1 should be initialized to B, which is equivalent to initializing ε1 = 0. On
each round, εt can be extracted from wt by,q2.
εt = B2 − wt,n+1

Since wt+1,n+1 is defined to be a convex combination of wt,n+1 and yt,n+1 (where the latter equalszero), then wt,n+1 is bounded in (0, B] for all t and can only decrease from round to round. Thismeans that the radius εt is always well defined and can only increase with t. Since the radius isinitialized to zero and is now one of the learned parameters, the algorithm has a natural tendency
to favor small radii. Let u denote the center of a fixed uniclass predictor and let ε denote its radius.
Then the reduction described above enables us to prove loss bounds similar to those presented inSec. 4, with kuk2 replaced by kuk2 + ε2 .

7. Multiclass Problems
We now address more complex decision problems. We first adapt the binary classification algorithms described in Sec. 3 to the task of multiclass multilabel classification. In this setting, every
instance is associated with a set of labels Yt . For concreteness we assume that there are k different
possible labels and denote the set of all possible labels by Y = {1, . . . , k}. For every instance xt , theset of relevant labels Yt is therefore a subset of Y . We say that label y is relevant to the instance xt if
y ∈ Yt . This setting is often discussed in text categorization applications (see for instance (Schapire
and Singer, 2000)) where xt represents a document and Yt is the set of topics which are relevant to
the document and is chosen from a predefined collection of topics. The special case where there
is only a single relevant topic for each instance is typically referred to as multiclass single-label
classification or multiclass categorization for short. As discussed below, our adaptation of the PA
variants to multiclass multilabel settings encompasses the single-label setting as a special case.
As in the previous sections, the algorithm receives instances x1 , x2 , . . . in a sequential mannerwhere each xt belongs to an instance space X . Upon receiving an instance, the algorithm outputs
a score for each of the k labels in Y . That is, the algorithm’s prediction is a vector in Rk where
each element in the vector corresponds to the score assigned to the respective label. This formof prediction is often referred to as label ranking. Predicting a label ranking is more general and567

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

flexible than predicting the set of relevant labels Yt . Special purpose learning algorithms such as
AdaBoost.MR (Schapire and Singer, 1998) and adaptations of support vector machines (Crammer
and Singer, 2003a) have been devised for the task of label ranking. Here we describe a reduction
from online label ranking to online binary classification that deems label ranking as simple as binary
prediction. We note that in the case of multiclass single-label classification, the prediction of thealgorithm is simply set to be the label with the highest score.
For a pair of labels r, s ∈ Y , if the score assigned by the algorithm to label r is greater than thescore assigned to label s, we say that label r is ranked higher than label s. The goal of the algorithm
is to rank every relevant label above every irrelevant label. Assume that we are provided with a setof d features φ1 , . . . , φd where each feature φ j is a mapping from X × Y to the reals. We denoteby Φ(x, y) = (φ1 (x, y), . . . , φd (x, y)) the vector formed by concatenating the outputs of the features,
when each feature is applied to the pair (x, y). The label ranking function discussed in this section
is parameterized by a weight vector, w ∈ Rd . On round t, the prediction of the algorithm is the
k-dimensional vector,
(wt · Φ(xt , 1)) , . . . , (wt · Φ(xt , k)) .
We motivate our construction with an example from the domain of text categorization. We describe
a variant of the Term Frequency - Inverse Document Frequency (TF-IDF) representation of documents (Rocchio, 1971; Salton and Buckley, 1988). Each feature φ j corresponds to a different word,
denoted µ j . Given a corpus of documents S, for every x ∈ S and for every potential topic y, thefeature φ j (x, y) is defined to be,|S|
φ j (x, y) = TF(µ j , x) · log,
DF(µ j , y)where TF(µ j , x) is the number of times µ j appears in x and DF(µ j , y) is the number of times µ j
appears in all of the documents in S which are not labeled by y. The value φ j grows in proportion to
the frequency of µ j in the document x but is dampened if µ j is a frequent word for topics other thany. In the context of this paper, the important point is that each feature is label-dependent.
After making its prediction (a ranking of the labels), the algorithm receives the correct set of
relevant labels Yt . We define the margin attained by the algorithm on round t for the example (xt ,Yt )as,
γ wt ; (xt ,Yt ) = min wt · Φ(xt , r) − max wt · Φ(xt , s).
r∈Yt

s6∈Yt

This definition generalizes the definition of margin for binary classification and was employed byboth single-label and multilabel learning algorithms for support vector machines (Vapnik, 1998;
Weston and Watkins, 1999; Elisseeff and Weston, 2001; Crammer and Singer, 2003a). In words,
the margin is the difference between the score of the lowest ranked relevant label and the scoreof the highest ranked irrelevant label. The margin is positive only if all of the relevant labels areranked higher than all of the irrelevant labels. However, in the spirit of binary classification, we are
not satisfied by a mere positive margin as we require the margin of every prediction to be at least 1.
After receiving Yt , we suffer an instantaneous loss defined by the following hinge-loss function,
ℓMC w; (x,Y ) =0 γ w; (x,Y ) ≥ 1 .
1 − γ w; (x,Y ) otherwise
568

(33)

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS


As in the previous sections, we use ℓt as an abbreviation for ℓMC wt ; (xt ,Yt ) . If an irrelevant label isTℓt2 upper
ranked higher than a relevant label, then ℓt2 attains a value greater than 1. Therefore, ∑t=1
bounds the number of multiclass prediction mistakes made on rounds 1 through T .
One way of updating the weight vector wt is to mimic the derivation of the PA algorithm forbinary classification defined in Sec. 3 and to set
1
wt+1 = argmin kw − wt k22w∈Rds.t. ℓMC (w; (xt ,Yt )) = 0.

(34)

Satisfying the single constraint in the optimization problem above is equivalent to satisfying thefollowing set of linear constraints,∀r ∈ Ytw · Φ(xt , r) − w · Φ(xt , s) ≥ 1.

∀s 6∈ Yt

(35)

However, instead of attempting to satisfy all of the |Y t | × (k − |Y t |) constraints above we focus only
on the single constraint which is violated the most by wt . We show in the sequel that we can stillprove a cumulative loss bound for this simplified version of the update. We note that satisfying allof these constraints simultaneously leads to the online algorithm presented in (Crammer and Singer,
2003a). Their online update is more involved and computationally expensive, and moreover, theiranalysis only covers the realizable case.
Formally, let rt denote the lowest ranked relevant label and let st denote the highest ranked
irrelevant label on round t. That is,
rt = argmin wt · Φ(xt , r)andst = argmax wt · Φ(xt , s).

(36)

s6∈Yt

r∈Yt

The single constraint that we choose to satisfy is w · Φ(xt , rt ) − w · Φ(xt , st ) ≥ 1 and thus wt+1 is set
to be the solution of the following simplified constrained optimization problem,1
wt+1 = argmin kw − wt k22
ws.t. w · (Φ(xt , rt ) − Φ(xt , st )) ≥ 1.

(37)

The apparent benefit of this simplification lies in the fact that Eq. (37) has a closed form solution.
To draw the connection between the multilabel setting and binary classification, we can think of thevector Φ(xt , rt ) − Φ(xt , st ) as a virtual instance of a binary classification problem with a label of+1. With this reduction in mind, Eq. (37) becomes equivalent to Eq. (2). Therefore, the closed form
solution of Eq. (37) is
wt+1 = wt + τt (Φ(xt , rt ) − Φ(xt , st )).
(38)
with,
τt =

ℓt
.
kΦ(xt , rt ) − Φ(xt , st )k2

Although we are essentially neglecting all but two labels on each step of the multiclass update, we
can still obtain multiclass cumulative loss bounds. The key observation in our analysis it that,ℓMC wt ; (xt ,Yt ) = ℓ wt ; (Φ(xt , rt ) − Φ(xt , st ), +1) .

To remind the reader, ℓ on the right-hand side of the above equation is the binary classification loss
defined in Eq. (1). Using this equivalence of definitions, we can convert Thm. 2 into a bound for569

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

the multiclass PA algorithm. To do so we need to cast the assumption that for all t it holds thatkΦ(xt , rt ) − Φ(xt , st )k ≤ R. This bound can immediately be converted into a bound on the normof the feature set since kΦ(xt , rt ) − Φ(xt , st )k ≤ kΦ(xt , rt )k + kΦ(xt , st )k. Thus, if the norm of the
mapping Φ(xt , r) is bounded for all t and r then so is kΦ(xt , rt ) − Φ(xt , st )k. In particular, if we
assume that kΦ(xt , r)k ≤ R/2 for all t and r we obtain the following corollary.
Corollary 8 Let (x1 ,Y1 ), . . . , (xT ,YT ) be a sequence of examples with xt ∈ Rn and YT ⊆ {1, . . . , k}.
Let Φ be a mapping Φ : X × Y → Rd such that kΦ(xt , r)k ≤ R/2 for all t and r. Assume that there
exists a vector u such that ℓ(u; (xt ,Yt )) = 0 for all t. Then, the cumulative squared loss attained by
the multiclass multilabel PA algorithm is bounded from above by,T∑ ℓt2 ≤ R2 kuk2 .

t=1

Similarly, we can obtain multiclass versions of PA-I and PA-II by using the update rule in Eq. (38)but setting τt to be either,


ℓt
ℓt
τt = min C ,
or
τt =
,
1
kΦ(xt , rt ) − Φ(xt , st )k2
kΦ(xt , rt ) − Φ(xt , st )k2 + 2C
respectively. The analysis of PA-I and PA-II in Thms. 4-5 also carries over from the binary case to
the multilabel case in the same way.
Multi-prototype Classification In the above discussion we assumed that the feature vector Φ(x, y)is label-dependent and used a single weight vector w to form the ranking function. However, inmany applications of multiclass classification this setup is somewhat unnatural. Many times, there
is a single natural representation for every instance rather than multiple feature representations foreach individual class. For example, in optical character recognition problems (OCR) an instancecan be a gray-scale image of the character and the goal is to output the content of this image. In thisexample, it is difficult to find a good set of label-dependent features.
The common construction in such settings is to assume that each instance is a vector in Rn and toassociate a different weight vector (often referred to as prototype) with each of the k labels (Vapnik,
1998; Weston and Watkins, 1999; Crammer and Singer, 2001). That is, the multiclass predictor is
now parameterized by wt1 , . . . , wtk , where wtr ∈ Rn . The output of the predictor is defined to be,(wt1 · xt ), . . . , (wtk · xt ) .
To distinguish this setting from the previous one we refer to this setting as the multi-prototype multiclass setting and to the previous one as the single-prototype multiclass setting. We now describe
a reduction from the multi-prototype setting to the single-prototype one which enables us to use allof the multiclass algorithms discussed above in the multi-prototype setting as well. To obtain thedesired reduction, we must define the feature vector representation Φ(x, y) induced by the instancelabel pair (x, y). We define Φ(x, y) to be a k · n dimensional vector which is composed of k blocks ofsize n. All blocks but the y’th block of Φ(x, y) are set to be the zero vector while the y’th block is set
to be x. Applying a single prototype multiclass algorithm to this problem produces a weight vector
wt ∈ Rkn on every online round. Analogous to the construction of Φ(x, y), the vector wt is composed570

O NLINE PASSIVE -AGGRESSIVE A LGORITHMSI NPUT: cost function ρ(y, y′ )I NITIALIZE : w1 = (0, . . . , 0)
For t = 1, 2, . . .
• receive instance: xt ∈ Rn
• predict: ŷt = arg maxy∈Y (wt · Φ(xt , y))• receive correct label: yt ∈ Yp• define: ỹt = arg maxr∈Y wt · Φ(xt , r) − wt · Φ(xt , yt ) + ρ(yt , r)
• define:ŷt (PB)qt =ỹt (ML)p• suffer loss: ℓt = wt · Φ(xt , qt ) − wt · Φ(xt , yt ) + ρ(yt , qt )ℓt
• set: τt = kΦ(xt ,yt )−Φ(x2t ,qt )k
• update: wt+1 = wt + τt (Φ(xt , yt ) − Φ(xt , qt ))Figure 2: The prediction-based (PB) and max-loss (ML) passive-aggressive updates for costsensitive multiclass problems.

of k blocks of size n and denote block r by wtr . By construction, we get that wt · Φ(xt , r) = wtr · xt .
Equipped with this construction we can use verbatim any single-prototype algorithm as a proxy forthe multi-prototype variant. Namely, on round t we find the pair of indices rt , st which corresponds
to the largest violation of the margin constraints,rt= argmin wt · Φ(xt , r) = argmin wtr · xt ,
r∈Yt

st

r∈Yt

= argmax wt · Φ(xt , s) = argmax wts · xt .

(39)

s6∈Yt

s6∈Yt

Unraveling the single-prototype notion of margin and casting it as a multi-prototype one we get thatthe loss in the multi-prototype case amounts to,ℓ wt1 , . . . , wtk ; (xt ,Yt ) =

0
1 − wtrt · xt + wtst · xt

wtrt · xt − wtst · xt ≥ 1.
otherwise(40)

Furthermore, applying the same reduction to the update scheme we get that the resulting multiprototype update is,
rt
rt
st
st
wt+1
= wt+1+ τt xt and wt+1
= wt+1− τt xt .
(41)
For the PA algorithm, the value of τt is the ratio of the loss, as given by Eq. (40), and the squared
norm of Φ(xt , rt ) − Φ(xt , st ). By construction, this vector has k − 2 blocks whose elements are zeros
and two blocks that are equal to xt and −xt . Since the two non-zero blocks are non-overlapping we
get that,kΦ(xt , rt ) − Φ(xt , st )k2 = kxt k2 + k − xt k2 = 2kxt k2 .
Finally, due to our reduction we also get multi-prototype versions of Thm. 4 and Thm. 5.
571

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

8. Cost-Sensitive Multiclass Classification
Cost-sensitive multiclass classification is a variant of the multiclass single-label classification setting
discussed in the previous section. Namely, each instance xt is associated with a single correct labelyt ∈ Y and the prediction extended by the online algorithm is simply,ŷt = argmax (wt · Φ(xt , y)) .

(42)

y∈Y

A prediction mistake occurs if yt 6= ŷt , however in the cost-sensitive setting different mistakes incur
different levels of cost. Specifically, for every pair of labels (y, y′ ) there is a cost ρ(y, y′ ) associatedwith predicting y′ when the correct label is y. The cost function ρ is defined by the user and takes
non-negative values. We assume that ρ(y, y) = 0 for all y ∈ Y and that ρ(y, y′ ) ≥ 0 whenever y 6= y′ .
The goal of the algorithm is to minimize the cumulative cost suffered on a sequence of examples,
namely to minimize ∑ ρ(yt , ŷt ).
The multiclass PA algorithms discussed above can be adapted to this task by incorporating thecost function into the online update. Recall that we began the derivation of the multiclass PA updateby defining a set of margin constraints in Eq. (35), and on every round we focused our attention
on satisfying only one of these constraints. We repeat this idea here while incorporating the costfunction into the margin constraints. Specifically, on every online round we would like for thefollowing constraints to hold,p∀r ∈ {Y \ yt } wt · Φ(xt , yt ) − wt · Φ(xt , r) ≥ ρ(yt , r).
(43)

The reason for using the square root function in the equation above will be justified shortly. As
mentioned above, the online update focuses on a single constraint out of the |Y | − 1 constraints in
Eq. (43). We will describe and analyze two different ways to choose this single constraint, whichlead to two different online updates for cost-sensitive classification. The two update techniques arecalled the prediction-based update and the max-loss update. Pseudo-code for these two updates ispresented in Fig. 2. They share an almost identical analysis and may seem very similar at first,
however each update possesses unique qualities. We discuss the significance of each update at theend of this section.
The prediction-based update focuses on the single constraint in Eq. (43) which corresponds tothe predicted label ŷt . Concretely, this update sets wt+1 to be the solution to the following optimization problem,1
wt+1 = argmin kw − wt k2
w∈Rn 2s.t. wt · Φ(xt , yt ) − wt · Φ(xt , ŷt ) ≥pρ(yt , ŷt ),(44)

where ŷt is defined in Eq. (42). This update closely resembles the multiclass update given in
Eq. (37). Define the cost sensitive loss for the prediction-based update to be,pℓPB w; (x, y) = w · Φ(x, ŷ) − w · Φ(x, y) + ρ(y, ŷ).
(45)

Note that this loss equals zero if and only if a correct prediction was made, namely if ŷt = yt . On
the other hand, if a prediction mistake occurred it means that wt ranked ŷt higher than yt , thus,ppρ(yt , ŷt ) ≤ wt · Φ(xt , ŷt ) − wt · Φ(xt , yt ) + ρ(yt , ŷt ) = ℓPB (wt ; (xt , yt )).
(46)
572

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

As in previous sections, we will prove an upper bound on the cumulative squared loss attained by
our algorithm, ∑t ℓPB (wt ; (xt , yt ))2 . The cumulative squared loss in turn bounds ∑t ρ(yt , ŷt ) which is
the quantity we are trying to minimize. This explains the rationale behind our choice of the margin
constraints in Eq. (43). The update in Eq. (44) has the closed form solution,
wt+1 = wt + τt (Φ(xt , yt ) − Φ(xt , ŷt )) ,(47)

where,τt =ℓPB (wt ; (xt , yt )).
kΦ(xt , yt ) − Φ(xt , ŷt )k2(48)

As before, we obtain cost sensitive versions of PA-I and PA-II by setting,ℓPB (wt ; (xt , yt ))τt = min C ,(PA-I)kΦ(xt , yt ) − Φ(xt , ŷt )k2ℓPB (wt ; (xt , yt ))τt =(PA-II),1kΦ(xt , yt ) − Φ(xt , ŷt )k2 + 2C

(49)

where in both cases C > 0 is a user-defined parameter.
The second cost sensitive update, the max-loss update, also focuses on satisfying a single constraint from Eq. (43). Let ỹt be the label in Y defined by,p(50)ỹt = argmax wt · Φ(xt , r) − wt · Φ(xt , yt ) + ρ(yt , r) .
r∈Yỹt is the loss-maximizing label. That is, we would suffer the greatest loss on round t if we were to
predict ỹt . The max-loss update focuses on the single constraint in Eq. (43) which corresponds to ỹt .
Note that the online algorithm continues to predict the label ŷt as before and that ỹt only influences
the online update. Concretely, the max-loss update sets wt+1 to be the solution to the following
optimization problem,1
wt+1 = argmin kw − wt k2
w∈Rn 2s.t. wt · Φ(xt , yt ) − wt · Φ(xt , ỹt ) ≥pρ(yt , ỹt ),(51)

The update in Eq. (51) has the same closed form solution given in Eq. (47) and Eq. (48) with ŷtreplaced by ỹt . Define the loss for the max-loss update to be,pℓML w; (x, y) = w · Φ(x, ỹ) − w · Φ(x, y) + ρ(y, ỹ),(52)
where ỹ is defined in Eq. (50). Note that since ỹ attains the maximal loss of all other labels, it follows
that,ℓPB (wt ; (xt , yt )) ≤ ℓML (wt ; (xt , yt )).
p
From the above inequality and Eq. (46) we conclude that ℓML is also an upper bound on ρ(yt , ŷt ).
A note-worthy difference between ℓPB and ℓML is that ℓML (wt ; (xt , yt )) = 0 if and only if Eq. (43)holds for all r ∈ {Y \ yt }, whereas this is not the case for ℓPB .
The prediction-based and max-loss updates were previously discussed in Dekel et al. (2004a), in
the context of hierarchical classification. In that paper, a predefined hierarchy over the label set wasused to induce the cost function ρ. The basic online algorithm presented there used the predictionbased update, whereas the max-loss update was mentioned in the context of a batch learning setting.
573

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

Dekel et al. (2004a) evaluated both techniques empirically and found them to be highly effective on
speech recognition and text classification tasks.
Turning to the analysis of our cost sensitive algorithms, we follow the same strategy used in theanalysis of the regression and uniclass algorithms. Namely, we begin by proving a cost sensitive
version of Lemma 1 for both the prediction-based and the max-loss updates.
Lemma 9 Let (x1 , y1 ), . . . , (xT , yT ) be an arbitrary sequence of examples, where xt ∈ R and yt ∈ Y
for all t. Let u be an arbitrary vector in Rn . If τt is defined as in Eq. (48) or Eq. (49) then,T∑ τt 2ℓ (wt ; (xt , yt )) − τt kΦ(xt , yt ) − Φ(xt , ŷt )k2 − 2ℓ (u; (xt , yt ))≤ kuk2 .

∑ τt 2ℓ (wt ; (xt , yt )) − τt kΦ(xt , yt ) − Φ(xt , ỹt )k2 − 2ℓ (u; (xt , yt ))≤ kuk2 .

PB

ML

t=1

If τt is defined as in Eq. (48) or Eq. (49) with ŷt replaced by ỹt then,
T

ML

ML

t=1



Proof We prove the first statement of the lemma, which involves the prediction-based update rule.
The proof of the second statement is identical, except that ŷt is replaced by ỹt and ℓPB (wt ; (xt , yt )) is
replaced by ℓML (wt ; (xt , yt )).
As in the proof of Lemma 1, we use the definition ∆t = kwt − uk2 − kwt+1 − uk2 and the fact
that,T

∑ ∆t ≤ kuk2 .

(53)

t=1

We focus our attention on bounding ∆t from below. Using the recursive definition of wt+1 , werewrite ∆t as,∆t= kwt − uk2 − kwt − u + τt (Φ(xt , yt ) − Φ(xt , ŷt ))k2

= −2τt (wt − u) · (Φ(xt , yt ) − Φ(xt , ŷt )) − τt2 kΦ(xt , yt ) − Φ(xt , ŷt )k2 .

(54)

By definition, ℓML (u; (xt , yt )) equals,
max u · (Φ(xt , r) − Φ(xt , yt )) +r∈Ypρ(yt , r) .

Since ℓML (u; (xt , yt )) is the maximum over Y , it is clearly greater than u · (Φ(xt , ŷt ) − Φ(xt , yt )) +p
ρ(yt , ŷt ). This can be written as,u · (Φ(xt , yt ) − Φ(xt , ŷt )) ≥Plugging the above back into Eq. (54) we get,∆t ≥ − 2τt wt · (Φ(xt , yt ) − Φ(xt , ŷt )) + 2τtp
ρ(yt , ŷt ) − ℓML (u; (xt , yt )).

pρ(yt , ŷt ) − ℓML (u; (xt , yt ))− τt2 kΦ(xt , yt ) − Φ(xt , ŷt )k2 . (55)574

O NLINE PASSIVE -AGGRESSIVE A LGORITHMSp
Rearranging terms in the definition of ℓPB , we get that wt · (Φ(xt , yt ) − Φ(xt , ŷt )) = ρ(yt , ŷt ) −ℓPB (wt ; (xt , yt )). This enables us to rewrite Eq. (55) as,p∆t ≥ −2τtρ(yt , ŷt ) − ℓPB (wt ; (xt , yt )) +p2τtρ(yt , ŷt ) − ℓML (u; (xt , yt )) − τt2 kΦ(xt , yt ) − Φ(xt , ŷt )k2= τt 2ℓPB (wt ; (xt , yt )) − τt kΦ(xt , yt ) − Φ(xt , ŷt )k2 − 2ℓML (u; (xt , yt )) .
Summing ∆t over all t and comparing this lower bound with the upper bound provided in Eq. (53)gives the desired bound.
This lemma can now be used to obtain cost sensitive versions of Thms. 2,3 and 5 for bothprediction-based and max-loss updates. The proof of these theorems remains essentially the same as
before, however one cosmetic change is required: kxt k2 is replaced by either kΦ(xt , yt )−Φ(xt , ŷt )k2
or kΦ(xt , yt ) − Φ(xt , ỹt )k2 in each of the theorems and throughout their proofs. This provides cumulative cost bounds for the PA and PA-II cost-sensitive algorithms.
Analyzing the cost-sensitive version of PA-I requires a slightly more delicate adaptation ofThm. 4. For brevity, we prove the following theorem for the max-loss variant of the algorithm
and note that the proof for the prediction-based variant is essentially identical.
We make two simplifying assumptions: first assume that kφ(xt , yt ) − φ(xt , ỹt )k is upper boundedby 1. Second, assume that C, the aggressiveness parameter given to the PA-I algorithm, is an upperbound on the square root of the cost function ρ.
Theorem 10 Let (x1 , y1 ), . . . , (xT , yT ) be a sequence of examples where xt ∈ Rn , yt ∈ Y and kφ(xt , yt )−φ(xt , ỹt )k ≤ 1 for all t. Let ρ be a cost function from Yp× Y to R+ and let C, the aggressivenessparameter provided to the PA-I algorithm, be such that ρ(yt , ŷt ) ≤ C for all t. Then for any vectoru ∈ Rn , the cumulative cost obtained by the max-loss cost sensitive version of PA-I on the sequenceis bounded from above by,
T

T

t=1

t=1

∑ ρ(yt , ŷt ) ≤ kuk2 + 2C ∑ ℓ (u; (xt , yt )).
ML

Proof We abbreviate ρt = ρ(yt , ŷt ) and ℓt = ℓML (wt ; (xt , yt )) throughout this proof. ℓt ≥every round t, as discussed in this section. τt is defined as,


ℓt
,C ,
τt = minkφ(xt , yt ) − φ(xt , ỹt )k2

√
ρt on

and due to our assumption on kφ(xt , yt ) − φ(xt , ỹt )k2 we get that τt ≥ min{ℓt ,C}. Combining these
two facts gives,√min{ρt ,C ρt } ≤ τt ℓt .
√Using our assumption on C, we know that C ρt is at least ρt and therefore ρt ≤ τt ℓt . Summing over
all t we get the bound,
T

T

t=1

t=1

∑ ρt ≤ ∑ τt ℓt .
575

(56)

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

Again using the definition of τt , we know that τt ℓML (u; (xt , yt )) ≤ CℓML (u; (xt , yt )) and that τt kφ(xt , yt )−φ(xt , ỹt )k2 ≤ ℓt . Plugging these two inequalities into the second statement of Lemma 9 gives,
T

T

t=1

t=1

∑ τt ℓt ≤ kuk2 + 2C ∑ ℓ (u; (xt , yt )).
ML

(57)

Combining Eq. (57) with Eq. (56) proves the theorem.
This concludes our analysis of the cost-sensitive PA algorithms. We wrap up this section with a
discussion on some significant differences between the prediction-based and the max-loss variantsof our cost-sensitive algorithms. Both variants utilize the same prediction function to output thepredicted label ŷt however each variant follows a different update strategy and is evaluated withrespect to a different loss function. The loss function used to evaluate the prediction-based variant
is a function of yt and ŷt , whereas the loss function used to evaluate the max-loss update essentiallyignores ŷt . In this respect, the prediction-based loss is more natural.
On the other hand, the analysis of the prediction-based variant lacks the aesthetics of the maxloss analysis. The analysis of the max-loss algorithm uses ℓML to evaluate both the performance of
the algorithm and the performance of u, while the analysis of the prediction-based algorithm usesℓPB to evaluate the algorithm and ℓML to evaluate u. The prediction-based relative bound is to someextent like comparing apples and oranges, since the algorithm and u are not evaluated using thesame loss function. In summary, both algorithms suffer from some theoretical disadvantage andneither of them is theoretically superior to the other.
Finally, we turn our attention to an important algorithmic difference between the two updatestrategies. The prediction-based update has a great advantage over the max-loss update in that thecost function ρ does not play a role in determining the single constraint which the update focuses on.
In some cases, this can significantly speed-up the running time required by the online update. For
example, in the following section we exploit this property when devising algorithms for the complex
problem of sequence prediction. When reading the following section, note that the max-loss update
could not have been used for sequence prediction in place of the prediction-based update. This isperhaps the most significant difference between the two cost sensitive updates.

9. Learning with Structured Output
A trendy and useful application of large margin methods is learning with structured output. In
this setting, the set of possible labels are endowed with a predefined structure. Typically, the setof labels is very large and the structure plays a key role in constructing efficient learning and inference procedures. Notable examples for structured label sets are graphs (in particular trees) andsequences (Collins, 2000; Altun et al., 2003; Taskar et al., 2003; Tsochantaridis et al., 2004). We
now overview how the cost-sensitive learning algorithms described in the previous section can beadapted to structured output settings. For concreteness, we focus on an adaptation for sequence prediction. Our derivation however can be easily mapped to other settings of learning with structured
output. In sequence prediction problems we are provided with a predefined alphabet Y = {1, . . . , k}.
Each input instance is associated with a label which is a sequence over Y . For simplicity we assume
that the output sequence is of a fixed length m. Thus, on round t, the learning algorithm receives an
instance xt and then predicts an output sequence ŷt ∈ Y m . Upon predicting, the algorithm receives
576

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

the correct sequence yt that is associated with xt . As in the cost-sensitive case, the learning algorithm is also provided with a cost function ρ : Y m × Y m → R+ . The value of ρ(y, y′ ) represents
the cost associated with predicting y′ instead of y. As before we assume that ρ(y, y′ ) equals zero if
y = y′ . Apart from this requirement, ρ may be any computable function. Most sequence prediction
algorithms further assume that ρ is decomposable. Specifically, a common construction (Taskar′
et al., 2003; Tsochantaridis et al., 2004) is achieved by defining, ρ(y, y′ ) = ∑mi=1 ρ̃(yi , yi ) where ρ̃
is any non-negative (local) cost over Y × Y . In contrast, we revert to a general cost function overpairs of sequences.
As in the multiclass settings discussed above, we assume that there exists a set of features
φ1 , . . . , φd each of which takes as its input an instance x and a sequence y and outputs a real number.
We again denote by Φ(x, y) the vector of features evaluated on x and y. Equipped with Φ and ρ, we
are left with the task of finding,ŷt = argmax (wt · Φ(xt , y)) ,

(58)

y∈Y m

on every online round. With ŷt on hand, the PA update for string prediction is identical to theprediction-based update described in the previous section. However, obtaining ŷt in the generalcase may require as many as km evaluations of wt · Φ(xt , y). This problem becomes intractable as m
becomes large. We must therefore impose some restrictions on the feature representation Φ which
will enable us to find ŷt efficiently. A possible restriction on the feature representation is to assume
that each feature φ j takes the form,mφ j (xt , y) = ψ0j (y1 , xt ) + ∑ ψ j (yi , yi−1 , xt ),

(59)

i=2

where ψ0j and ψ j are any computable functions. This construction is analogous to imposing a firstorder Markovian structure on the output sequence. This form paves the way for an efficient inference, i.e. solving Eq. (58), using a dynamic programming procedure. Similar yet richer structures
such as dynamic Bayes nets can be imposed so long as the solution to Eq. (58) can be computed
efficiently. We note in passing that similar representation of Φ using efficiently computable featuresets were proposed in (Altun et al., 2003; Taskar et al., 2003; Tsochantaridis et al., 2004).
The analysis of the cost-sensitive PA updates carries over verbatim to the sequence prediction
setting. Our algorithm for learning with structured outputs was successfully applied to the task ofmusic to score alignment in (Shalev-Shwartz et al., 2004a).

10. Experiments
In this section we present experimental results that demonstrate different aspects of our PA algorithms and their accompanying analysis. In Sec. 10.1 we start with two experiments with synthetic
data which examine the robustness of our algorithms to noise. In Sec. 10.2 we investigate the effectof the aggressiveness parameter C on the performance of the PA-I and PA-II algorithms. Finally,in Sec. 10.3, we compare our multiclass versions of the PA algorithms to other online algorithms
for multiclass problems (Crammer and Singer, 2003a) on natural data sets.
The synthetic data set used in our experiments was generated as follows. First a label was chosen
uniformly at random from {−1, +1}. For positive labeled examples, instances were chosen byrandomly sampling a two-dimensional Gaussian with mean (1, 1) and a diagonal covariance matrix
577

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

0.4
0.35

1.5

PA
PA−I
PA−II

PA
PA−I
PA−II

0.3
1

Loss

Error

0.25
0.2
0.15
0.5
0.1
0.05
0
0

0.05

0.1

0.15

0
0

0.2

Error of optimal linear classifier

0.05

0.1

0.15

0.2

Error of optimal linear classifier
0.9

0.3

PA
PA−I
PA−II

0.8

PA
PA−I
PA−II

0.7
0.25

Loss

Error

0.6
0.2

0.15

0.5
0.4
0.3

0.1
0.2
0.05

0
0

0.1

0.05

0.1

0.15

0.2

Error of optimal linear classifier

0
0

0.05

0.1

0.15

0.2

Error of optimal linear classifier

Figure 3: The average error (left) and the average loss (right) of PA, PA-I and PA-II as a functionof the error of the optimal fixed linear classifier, in the presence of instance noise (top)and label noise (bottom).

with (0.2, 2) on its diagonal. Similarly, for negative labeled examples, instances were sampledfrom a Gaussian with a mean of (−1, −1) and the same covariance matrix as for positive labeled
examples. To validate our results, we repeated each experiment 10 times where in each repetition
we generated 4,000 random examples. The results reported are averaged over the 10 repetitions.
10.1 Robustness to Noise
Our first experiments examine the robustness of our algorithms to both instance noise and label
noise. To examine instance noise, we contaminated each instance with a random vector sampledfrom a zero-mean Gaussian with a covariance matrix σI, where σ varied from 0 to 2. We set
the parameter C of PA-I and PA-II to be 0.001. We then ran PA, PA-I and PA-II on the resulting
sequence of examples. To evaluate our results, we used a brute-force numerical method to findthe optimal fixed linear classifier, that is, the linear classifier that makes the fewest classification
mistakes on the entire sequence of examples. We define the average error of an online learningalgorithm on a given input sequence to be the number of prediction mistakes the algorithm makeson that sequence normalized by the length of the sequence. Similarly, we define the average loss ofan online learning algorithm on a given sequence.
In the plots at the top of Fig. 3 we depict the average error and average loss of the three PA
variants as a function of the average error of the optimal linear classifier. The plots underscore
578

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

1.6

0.6

p=0.0
p=0.1
p=0.2

p=0.0
p=0.1
p=0.2

1.4
1.2

0.5

Loss

Error

1

0.4

0.3

0.8
0.6

0.2

0.4

0.1

0
−10

0.2

−8

−6

−4

−2

0

2

4

0
−10

6

−8

−6

−4

log(C)

−2

0

2

4

6

0

2

4

6

log(C)
1.6

0.6

p=0.0
p=0.1
p=0.2

p=0.0
p=0.1
p=0.2

1.4
1.2

0.5

Loss

Error

1

0.4

0.3

0.8
0.6

0.2

0.4

0.1

0
−10

0.2

−8

−6

−4

−2

0

2

4

6

log(C)

0
−10

−8

−6

−4

−2

log(C)

Figure 4: The average error (left) and the average loss (right) of PA-I (top) and PA-II (bottom) as afunction of log(C) with different levels of label noise probability p.

several interesting phenomena. First note that for low levels of noise, all three PA variants make asimilar number of errors. Our bounds from Sec. 4 suggest that as the noise level increases, PA-I and
PA-II should outperform the basic PA algorithm. It is clear from the graphs that our expectations
are met and that PA-I and PA-II outperform the basic PA algorithm when the noise level is high.
Finally, in this experiment PA-I and PA-II performed equally well for all levels of noise.
In our second experiment we left the instances intact and instead flipped each label with aprobability p, where p was set to different values in [0, 0.3]. As in the previous experiment, we set
C = 0.001 for both PA-I and PA-II . The results are depicted at the bottom of Fig. 3. It is apparent
from the graphs that the behavior observed in the previous experiment is repeated here as well.
10.2 The Effect of C
In our second set of experiments, we examine the effect of the aggressiveness parameter C on theperformance of PA-I and PA-II . Again we flipped the label of each instance in our synthetic data
set with probability p, this time with p set to 0, 0.1 and 0.2. We then ran PA-I and PA-II on the
resulting sequence of examples with different values of the parameter C. The average error andaverage loss of the algorithms as a function of the parameter C are depicted in Fig. 4579

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

0.2

0.2

C = 0.001
C = 100

0.16

0.16

0.14

0.14

0.12

0.12

0.1

0.1

0.08

0.08

0.06

0.06

0.04

0.04

0.02

0.02

0

1000

2000

3000

4000

5000

6000

7000

8000

C = 0.001
C = 100

0.18

Error

Error

0.18

0

9000

T

1000

2000

3000

4000

5000

6000

7000

8000

9000

T

Figure 5: The average error of PA-I (left) and PA-II (right) as a function of the number of online
rounds, T , for different values of C.

As can be seen from the graphs, the value of the parameter C significantly effects the resultsof the algorithms. The graphs can be explained using our loss bounds in Thm. 4 and Thm. 5. For
concreteness, let us focus on the loss bound of the PA-II algorithm, given in Thm. 5. The boundon the cumulative loss of the algorithm is comprised of two terms, the first depends on the squared
norm of the competitor, (kuk2 ), while the second depends on the cumulative (squared) loss ofthe competitor (∑t (ℓt⋆ )2 ). The parameter C divides the first term and multiplies the second term.
Therefore, when C is small the bound is dominated by the first term (kuk2 ) and when C is large thebound is dominated by the second term (∑t (ℓt⋆ )2 ). Since the label noise applied to the data effects
only the second term, we expect that for very small values of C the loss of PA-I and PA-II will behigh, regardless of the noise level. On the other hand, as we increase the value of C, the difference
between different noise levels becomes apparent. As a general rule-of-thumb, C should be small
when the data is noisy.
So far, the length of the sequence of examples presented to the online algorithms was fixed.
In the following, we discuss the effect of C on the performance of the algorithms as a function ofsequence length (T ). We generated a synthetic data set consisting of 104 examples with label noiseprobability p = 0.02. We ran the PA-I and PA-II algorithms on the data set, once with C = 100 andonce with C = 0.001. At the end of each online round we calculated the average error attained sofar. The results are given in Fig. 5. For both PA-I and PA-II , setting C to be a small number leads
to a slow progress rate, since each online update changes the online hypothesis by a small amount.
On the other hand, when C is large, the error rate decreases much faster, but at the price of inferior
performance later on.
10.3 Multiclass Experiments
Our last experiment demonstrates the efficiency of the PA algorithms on multiclass problems. This
experiment was performed with standard multiclass data sets: the USPS and MNIST data setsof handwritten digits. We compared the multiclass versions of PA, PA-I and PA-II to the online
580

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

0.07

0.06

0.05

Multiclass Perceptron
MIRA
PA−I

0.045
0.04
0.035
0.03

0.04

Error

Error

0.05

Multiclass Percetron
MIRA
PA−I

0.03

0.025
0.02
0.015

0.02

0.01
0.01

0.005
0

1000

2000

3000

4000

5000

6000

7000

T

0
0

1

2

3

T

4

5

6
4

x 10

Figure 6: The number of prediction mistakes made by different multiclass online algorithms as afunction of the online round index, on the USPS (left) and MNIST (right) data sets.

multiclass algorithms described in (Crammer and Singer, 2003a). Specifically, Crammer and Singer(2003a) present three multiclass versions of the Perceptron algorithm and a new margin based online
multiclass algorithm named MIRA. As a preprocessing step, we shifted and scaled the instancesof each data set so that its mean equals zero and its average squared Euclidean norm is 1. We
used Mercer kernels in all of the algorithms, namely, we replaced the standard dot product witha polynomial kernel K(xi , x j ) = (a + xi · x j )d , where a = 0 and d = 3 for the USPS data set anda = 0.5 and d = 5 for the MNIST data set. These kernel parameters were set rather arbitrarily,
based on previous experience with these data sets using different algorithms. We set the parameter
C of PA-I and PA-II to 100 (we note that similar results hold for any C > 100). The parameter β of
MIRA was set to 0.01, following (Crammer and Singer, 2003a).
The plots in Fig. 6 depict the number of online prediction mistakes made on the two data sets by
three different algorithms: PA-I , the uniform-update version of multiclass Perceptron and MIRA.
The performance of PA and PA-II is not presented in this figure, since it is virtually indistinguishable from that of PA-I . For the same reason, only the uniform-update version of the multiclass
Perceptron is presented in the figure. It is apparent that both PA-I and MIRA outperform the Perceptron. In addition, the performance of PA-I is comparable to that of MIRA with a slight advantage
to the latter. However, while each online update of MIRA requires solving a complex optimization
problem, each update of PA has a simple closed-form expression and is thus much faster and easier
to implement.

11. Discussion
We described an online algorithmic framework for solving numerous prediction problems ranging from classification to sequence prediction. We derived several loss bounds for our algorithms(Thms. 2-5). The proofs of all of the bounds are based on a single lemma (Lemma 1). There
are several possible extensions of the work presented in this paper. We already conducted further research on applications of the PA algorithmic framework for learning margin-based suffix
581

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

trees (Dekel et al., 2004b), pseudo-metrics (Shalev-Shwartz et al., 2004b), hierarchical classification (Dekel et al., 2004a), and segmentation of sequences (Shalev-Shwartz et al., 2004a). While
the focus of this paper is on online settings, online algorithms can also serve as building blocks inthe construction of well performing batch algorithms. Online to batch conversions of the proposed
algorithms are yet another important future research direction. The update taken by our algorithms
is aggressive in the sense that even a small loss forces an update of the hypothesis. When using
kernels, this property often results in the use of many examples for representing the learned predictor. Thus, the memory requirements imposed when using kernels can be quite demanding. We are
currently pursuing extensions of the PA framework that operate in the realm of bounded memory
constraints.

Acknowledgments
This research was funded by the Israeli Science Foundation under grant number 522/04. Most of
this work was carried out at the Hebrew University of Jerusalem.

Appendix A. Derivation of the PA-I and PA-II Updates
As in Sec. 3, whenever ℓt = 0 no update occurs and τt equals zero. If ℓt > 0 we derive these
updates by defining the Lagrangian of the respective optimization problem and satisfying the KKT
conditions. The Lagrangian of the PA-I optimization problem is,

L (w, ξ, τ, λ) ==1kw − wt k2 + Cξ + τ(1 − ξ − yt w · xt ) − λξ21
kw − wt k2 + ξ (C − τ − λ) + τ(1 − yt w · xt ) ,2(60)

where τ ≥ 0 and λ ≥ 0 are Lagrange multipliers. We now find the minimum of the Lagrangian withrespect to the (unconstrained) primal variables w and ξ. As in the previously discussed PA update,differentiating this Lagrangian with respect to the elements of w and setting these partial derivatives
to zero gives Eq. (5) and we can write w = wt + τyt xt . Next, note that the minimum of the termξ(C − τ − λ) with respect to ξ is zero whenever C − τ − λ = 0. If however C − τ − λ 6= 0 thenξ(C − τ − λ) can be made to approach −∞. Since we need to maximize the dual we can rule out thelatter case and pose the following constraint on the dual variables,C − τ − λ = 0.

(61)

The KKT conditions confine λ to be non-negative so we conclude that τ ≤ C. We now discuss two
possible cases: if ℓt /kxt k2 ≤ C then we can plugging Eq. (61) back into Eq. (60) and we return to
the Lagrangian of the original PA algorithm (see Eq. (4)). From this point and on, we can repeat
the same derivation as in the original PA update and get τt = ℓt /kxt k2 . The other case is whenℓt /kxt k2 > C. This condition can be rewritten as
Ckxt k2 < 1 − yt (wt · xt ).

(62)

We also know that the constraint in Eq. (6) must hold at the optimum, so 1 − yt (w · xt ) ≤ ξ. Using
the explicit form of w given in Eq. (5), we can rewrite this constraint as 1 − yt (wt · xt ) − τkxt k2 ≤ ξ.
582

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

Combining this inequality with the inequality in Eq. (62) gives,
Ckxt k2 − τkxt k2 < ξ.
We now use our earlier conclusion that τ ≤ C to obtain 0 < ξ. Turning to the KKT complementarity
condition, we know that ξλ = 0 at the optimum. Having concluded that ξ is strictly positive, we getthat λ must equal zero. Plugging λ = 0 into Eq. (61) gives τ = C. Summing up, we used the KKT
conditions to show that in the case where ℓt /kxt k2 > C, it is optimal to select τ = C. Folding all of
the possible cases into a single equation, we define τt to be,τt = min C , ℓt /kxt k2 .
(63)

The update of PA-I is like the update of PA clipped at C.
Turning to the update of PA-II , we again recall that ℓt = 0 leads to τt = 0, and deal with thoserounds where ℓt > 0. The Lagrangian of the optimization problem in Eq. (7) equals,

L (w, ξ, τ) =

1kw − wt k2 + Cξ2 + τ 1 − ξ − yt (w · xt ) ,2(64)

where τ ≥ 0 is a Lagrange multiplier. Again, differentiating this Lagrangian with respect to theelements of w and setting these partial derivatives to zero gives Eq. (5) and we can write w =wt + τyt xt . Differentiating the Lagrangian with respect to ξ and setting that partial derivative to zero
results in,τ∂L (w, ξ, τ)= 2Cξ − τ
=⇒
ξ=
.
0 =
∂ξ
2C
Expressing ξ as above and replacing w in Eq. (60) with wt + τyt xt , we rewrite the Lagrangian as,



τ2
1
2
L (τ) = −kxt k +
+ τ 1 − yt (wt · xt ) .
2
2C

Setting the derivative of the above to zero gives,∂L (τ)12
0 =+ 1 − yt (wt · xt )= − τ kxt k +
∂τ
2C

=⇒

τ=

1 − yt (wt · xt ).
1
kxt k2 + 2C

As in PA and PA-I , we can give a definition of τt which holds in all cases,
τt =

ℓt
.
1
kxk2 + 2C(65)

References
S. Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6(3):382–392, 1954.
Y. Altun, I. Tsochantaridis, and T. Hofmann. Hidden markov support vector machines. In Proceedings of the Twentieth International Conference on Machine Learning, 2003.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
583

C RAMMER , D EKEL , K ESHET, S HALEV-S HWARTZ AND S INGER

M. Collins. Discriminative reranking for natural language parsing. In Machine Learning: Proceedings of the Seventeenth International Conference, 2000.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector
machines. Jornal of Machine Learning Research, 2:265–292, 2001.
K. Crammer and Y. Singer. A new family of online algorithms for category ranking. Jornal of
Machine Learning Research, 3:1025–1058, 2003a.
K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Jornal of
Machine Learning Research, 3:951–991, 2003b.
N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000.
O. Dekel, J. Keshet, and Y. Singer. Large margin hierarchical classification. In Proceedings of theTwenty-First International Conference on Machine Learning, 2004a.
O. Dekel, S. Shalev-Shwartz, and Y. Singer. The power of selective memory: Self-bounded learningof prediction suffix trees. In Advances in Neural Information Processing Systems 17, 2004b.
A. Elisseeff and J. Weston. A kernel method for multi-labeled classification. In Advances in Neural
Information Processing Systems 14, 2001.
Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine
Learning, 37(3):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), 2002.
D.P Helmbold, J. Kivinen, and M. Warmuth. Relative loss bounds for single neurons. IEEE Transactions on Neural Networks, 10(6):1291–1304, 1999.
M. Herbster. Learning additive models online with fast evaluating kernels. In Proceedings of the
Fourteenth Annual Conference on Computational Learning Theory, pages 444–460, 2001.
J. Kivinen, A. J. Smola, and R. C. Williamson. Online learning with kernels. IEEE Transactions on
Signal Processing, 52(8):2165–2176, 2002.
J. Kivinen and M. Warmuth. Exponentiated gradient versus gradient descent for linear predictors.
Information and Computation, 132(1):1–64, January 1997.
N. Klasner and H.U. Simon. From noise-free to noise-tolerant and from on-line to batch learning.
In Proceedings of the Eighth Annual Conference on Computational Learning Theory, pages 250–
264, 1995.
Y. Li and P. M. Long. The relaxed online maximum margin algorithm. Machine Learning, 46(1–3):
361–387, 2002.
584

O NLINE PASSIVE -AGGRESSIVE A LGORITHMS

N. Littlestone. Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis,
U. C. Santa Cruz, March 1989.
A. B. J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the
Mathematical Theory of Automata, volume XII, pages 615–622, 1962.
J. Rocchio. Relevance feedback information retrieval. In Gerard Salton, editor, The Smart retrieval
system—experiments in automatic document processing, pages 313–323. Prentice-Hall, Englewood Cliffs, NJ, 1971.
F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in
the brain. Psychological Review, 65:386–407, 1958. (Reprinted in Neurocomputing (MIT Press,
1988).).
G. Salton and C. Buckley. Term weighting approaches in automatic text retrieval. Information
Processing and Management, 24(5), 1988.
R.E. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated predictions.
In Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pages
80–91, 1998. To appear, Machine Learning.
R.E. Schapire and Y. Singer. BoosTexter: A boosting-based system for text categorization. Machine
Learning, 32(2/3), 2000.
B. Schölkopf and A. J. Smola. Learning with Kernels: Support Vector Machines, Regularization,
Optimization and Beyond. MIT Press, 2002.
S. Shalev-Shwartz, J. Keshet, and Y. Singer. Learning to align polyphonic music. In
Proceedings of the 5th International Conference on Music Information Retrieval, 2004a.
http://www.cs.huji.ac.il/∼shais/.
S. Shalev-Shwartz, Y. Singer, and A. Ng. Online and batch learning of pseudo-metrics. In Proceedings of the Twenty-First International Conference on Machine Learning, 2004b.
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 Proceedings of the Twenty-First International
Conference on Machine Learning, 2004.
V. N. Vapnik. Statistical Learning Theory. Wiley, 1998.
J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.

585