On the Dual Formulation of Regularized Linear Systems with Convex Risks.
In this paper, we study a general formulation of linear prediction algorithms including a number of known methods as special cases. We describe a convex duality for this class of methods and propose numerical algorithms to solve the derived dual learning problem. We show that the dual formulation is closely related to online learning algorithms. Furthermore, by using this duality, we show that new learning methods can be obtained. Numerical examples will be given to illustrate various aspects of the newly proposed algorithms.
Introduction
We consider the statistical learning problem: to find a parameter from random observations
to minimize the expected loss (risk): given a loss function L(ff; x) and n observations
independently drawn from a fixed but unknown distribution D, we want to find
ff that minimizes the expected loss over x:
Z
any assumption of the underlying distribution on x, the most natural method
for solving (1) using a limited number of observations is by the empirical risk minimization
(ERM) method (cf. [13]). That is, we choose a parameter ff that minimizes the observed
risk:n
More specifically, we consider the following type of regularized linear system with convex
loss:
where we shall assume that both f and g are convex functions. - is an appropriately chosen
positive regularization parameter to balance the two terms. We typically choose g(w) - 0
as a function that penalizes large w.
This formulation naturally arises in many statistical learning applications. For example,
in order to apply this formulation to linear regression, we can let
However, other formulations can also be of interests. For example, in robust estimation, one
is interested in using In order to apply this formulation for the purpose of training
linear classifiers, we can choose f as a decreasing function, such that f(\Delta) - 0. Examples
include support vector machines and the logistic regression where
One interesting theoretical result from the VC analysis concerning this (primal) formulation
is that dimensional independent generalization error can be obtained with
[14]. This VC analysis was extended in [16]. However, it turns out that a careful non-VC
analysis [17] can actually be more suitable for this particular problem (both for its primal
form and for its dual form - which we will introduce later in this paper).
In this paper, we study some numerical and learning aspects of a dual form of (3), which
has certain attractive properties compared with the primal formulation. This duality of
certain learning problems in the general game-theoretical sense can also lead to the discovery
of new learning methodologies. The paper is organized as follows. In Section 2, we derive
the dual formulation of (3) and propose a relaxation algorithm to solve the dual problem.
Section 3 generalizes the derivation to include equality constraints. Section 4 provides some
applications of the proposed algorithms in machine learning. In Section 5, we provide some
numerical examples. In Section 6, we study the learning aspect of the dual formulation.
Conclusions and some final remarks are made in Section 7.
Dual formulation
Since (3) is a convex programming problem involving linear transformations of the primal
variable w, a dual form can be obtained by introducing auxiliary variables - i for each data
point
sup
-n
where k(\Delta) is the dual transform of f(\Delta) (assume f is lower semi-continuous, see [11]):
It is well known that k is convex. By switching the order of inf w and sup - , which is valid for
the above minimax convex-concave programming problem (a proof of this interchangeability,
i.e. strong duality, is given in Appendix A), we obtain
-n
where w minimizes (5) for fixed - at:
-n
where we use rg to denote the gradient of g with respect to w. Note that in the main body
of the paper, we assume that the gradient of a convex function exists when required. In this
case, constraints need to be dealt with by introducing appropriate Lagrangian multipliers as
in Section 3. The main reason of this treatment is for numerical considerations. However,
for the mathematical proof of strong duality in Appendix A which does not have any direct
numerical consequence, we use the generalized definition of convex functions and duality in
[11] without assuming differentiability. For example, in the general case, a constraint on a
convex function c(z) can be regarded as a modification of c(z) so that c(z) = +1 when z
does not satisfies the constraint.
Substituting (6) into (5), we obtain
-n
s:t: rg(w) =-n
To simplify notations, we now consider the dual transform of g(\Delta):
where h(\Delta) is also a convex function. It follows that
We can thus rewrite (7) as the following dual formulation:
-n
The optimal solution -
w to the primal problem can be obtained from
-n
When this system is non-degenerate (also see Section 3), it gives the following solution:
-n
As a comparison, we also have the following equation from (4) when f is differentiable at
Note that we have derived equation (8) by using two Legendre transforms: k is the dual
of f and h is the dual of g. If we write X as the matrix with each data x i as a row, then
from the Legendre transformation point of view, the dual transform of - is Xw with respect
to f and k; the dual transform of w is 1
with respect to g and h. Consequently, we can
regard X as an interaction between the dual variables w and -. This interaction is a linear
interaction which is the simplest possible interaction between w and -.
In this paper, we propose the following generic relaxation algorithm to solve the dual
problem (8), where we denote the dimension of w as d:
Algorithm 1 (Dual Gauss-Seidel)
find \Delta- i by approximately minimizing
update v:
-n
\Delta-
update
At each inner iteration i of Algorithm 1, the algorithm essentially fixes all other dual
variables - j with j 6= i and find a perturbation \Delta- i of the dual variable - to reduce the
objective function (8). Since the objective function is reduced at each step, the algorithm
will always converge. If exact optimization is used for ( ), then - converges to the true
optimal solution -
- of (8). Also if the Hessian of (8) exists and is well-behaved around the
optimal solution -
-, then (8) can be locally approximated by a quadratic function. It follows
that the asymptotic convergence rate of Algorithm 1 is linear if ( ) is minimized exactly
[4]. The rate of convergence depends on the spectrum of the Hessian matrix of (8) at the
optimal solution -
-. The main attractive feature of Algorithm 1 is its simplicity. One might
also consider a preconditioned conjugate gradient acceleration [4] with Algorithm 1 as a
preconditioner. However, in many interesting cases, k(\Delta) can be non-smooth (containing
simple bounds), and hence CG might not help.
An interesting aspect of the dual formulation is that each dual variable - i corresponds
to a data point x i . In Algorithm 1, at each step, one looks at only one data point - i , which
is very similar to online update algorithms. The difference is that in Algorithm 1, we keep
the dual variable - that has been computed so far, while for a typical online algorithm,
this information is not kept. It is actually not very difficult to convert Algorithm 1 into an
online learning method by setting use an appropriate scaling factor n at each
step. Minimax style mistake bounds can also be derived accordingly. However, a full-scale
study of related issues will be left to another report. In this paper, we shall only provide a
simple analysis on the mistake bounds of the empirical risk estimator in Appendix B, which
illustrates the basic idea and demonstrates the theoretical connection of the dual batch
formulation and online learning.
Note that the primal form (3) and the dual form (8) have a striking similarity. Besides the
connection with online algorithms, there are several other reasons why we are interested in
studying the dual form. For example, we will later see in this paper that if g is the quadratic
regularization function Algorithm 1 has an especially simple form. Another
reason is that if f is non-smooth but g is smooth, then the one-dimensional optimization
problem in the dual Gauss-Seidel algorithm is easier than the one-dimensional optimization
problem in the primal Gauss-Seidel algorithm. Furthermore, even if the primal problem
is infinite dimensional (that is, d is infinity), the dual problem is still finite dimensional
(assuming a finite sample size). This elimination of the primal dimensionality has important
generalization performance consequences in machine learning (see Section 6 and Section 7).
Finally, the dual form (8) with the relationship (9) generalizes the kernel form of SVM
originally investigated by Vapnik [14].
Constraints
In order for the dual formulation (8) to be valid, equation (9) has to have a solution. However,
in certain circumstances, it is possible that (8) is singular, and hence it has a solution only
when the right hand side lies in the range of rg(w) for w 2 R d . This imposes a constraint
on X T - where X is the matrix with each row i consisted of data x i . For simplicity, we shall
only discuss the case of equality constraint. Inequality constraints can be handled similarly.
Since the original problem is a convex optimization problem, therefore the dual problem is
also a convex optimization problem. This implies that such an equality constraint on the
dual variable - must be a linear constraint. This situation usually arises when g(w) is flat
under a linear transformation of w:
where C is a matrix and d is a vector. Since Crg(w) j d, therefore by (9), the corresponding
constraint imposed on the dual variable is of the following form:
Equation (10) has to be modified as
-n
s:
In order to preserve the structure of the dual formulation (8) so that we can employ the
Gauss-Seidel update in Algorithm 1, we propose to use the augmented Lagrangian method
[3]. This method modifies the dual h(v) of the primal regularization term g(w) in (8) as
where s is the Lagrangian multiplier vector corresponding to the constraint (13) and is the
same s as in (14). - is a small positive penalty parameter. The following algorithm solves
(8) with constraint (13) by utilizing the modified dual h s;- (cf. [3], page 292):
Algorithm 2 (Dual Augmented Lagrangian)
solve (8) with h(\Delta) replaced by h s;- (\Delta) using Algorithm 1
(use the current (-; v) as the initial point, and update (-; v))
else
\Deltas
One nice property of the Augmented Lagrangian approach is that if the augmented dual
problem can be solved by Algorithm 1 to a sufficiently high accuracy, then the step -=4
can only be executed finitely number of times. This means that upon termination, - is
bounded away from zero.
Next, we would like to briefly discuss the situation when the primal problem (3) has a
convex constraint c(w) - 0, where each component of c(\Delta) is a convex function. Let -
- be the
corresponding Lagrangian multiplier, then the primal problem can be rewritten as
It is well known that - 0 [3], and - for each component c j (w) ! 0. This indicates
that -
- T c(w) is convex and thus can be regarded as a regularization term similar to -g(w).
If we can select the appropriate Lagrangian multiplier -, then we essentially solve the same
problem with regularization term -g(w) replaced by -g(w)
For learning problems, the exact value Lagrangian -
- is either known (for example, for
entropy regularized probability distributions investigated later), or non-crucial (since the
most appropriate way to determine such a Lagrangian regularization parameter should be
some kind of cross-validation anyway). Also in many cases, a constraint on the primal
variable w becomes a flat segment in the dual variable -. In such cases, we can apply the
unmodified Algorithm 1 to compute - but the relationship to obtain w should be modified
accordingly.
If we regard a primal inequality constraint as a regularization term, observe that when a
parameter -
increases, the corresponding c j (w) decreases at the optimal solution, it is thus
also possible to use the algorithms suggested in this paper as an inner solution engine and
adjust - j appropriately by examining c j ( -
w) at the optimal solution. This idea is similar to the
modified Lagrangian method we propose to deal with the dual constraint (13). Although
a modification of the Augmented Lagrangian method can be applied in many cases, it is
usually not recommended due to a variety of reasons. Some other more subtle methods can
be employed. However, due to the limitation of space (also because this issue is non-crucial
for learning problems), we shall skip further discussions.
4.1 Useful dual pairs
In this section, we list a few examples of convex Legendre dualities that are relevant to
learning problems. We use p(u) to denote the primal function with primal variable u, and
use q(v) to denote the dual function with dual variable v.
1.
We assume that K is a symmetric positive definite operator.
2.
are dual pairs: 1=p
3.
are dual pairs: 1=p are dual pairs:
4.
is a set of positive prior.
5.
Note that p(u) has a flat dimension p(u a when a is a vector with
identical components, therefore v satisfies a constraint
and the dual
transformation
s contains a free Lagrangian parameter s.
7.
where s - 0 is a non-negative Lagrangian parameter.
8.
9.
are dual pairs: 1=p
Note that many of the above examples contain constraints on the dual (some also on
the primal) variables. In such case, we can also ignore the constraint and consider the
corresponding function when the constraint is not satisfied. The
last few examples are of interests because they are relevant to classification problems.
It is also very useful to note that the dual of a linear transform of either the primal
variable or the primal convex function can be easily computed:
a
where we assume that S is a non-singular linear transformation.
4.2 The regularization term
In this section, we briefly discuss a few regularization conditions for (3) that are of interests.
Square regularization
One of the most important regularization conditions is the square penalty:
where K is a symmetric positive definite operator. In many applications, one choose
- the identity matrix. In this case,
and hence ( ) in Algorithm 1 can be replaced by minimizing:
where
Note that system (16) is particularly simple. It has actually been reduced to a small problem
of constant size which can be solved in constant time once the inner product a and b are
computed. For large problems, the computation of a and b (a can actually be pre-computed)
dominates.
p-norm regularization
We let
This is of interests when the data is q-norm bounded since x T w is bounded. The generalization
performance is also dimensional independent [16, 17]. In this case,
then an approximate Newton's method can be employed to solve ( ). In each
of the Newton's iteration for (\Lambda) (usually one may use only one Newton's iteration), we need
to compute the derivative part
and the second derivative part
i;j . In many cases, this computation can be more costly than the evaluation of a
and b in the square regularization formulation. However, tricks can be employed to alleviate
this problem since an accurate estimate of the second derivative part
i;j is
less important - we can safely use a good upper-bound on the second derivative.
Note that if essentially a constraint on v. In order to obtain w from -,
equation (10) has to be modified. Similarly, if is essentially a constraint on
The regularization term is given by
This is of interests when the data is 1-norm (or entropy) bounded. Typically, we can let
be a large number. In this case,
Again, an approximate Newton's method is required. The derivative part requires the evaluation
of
In addition, the second derivative part
requires the evaluation of
i;j .
Entropy regularization
This is usually of interests when either the data is infinite-norm bounded or when the weight
vector w gives a probability distribution. In this case, unlike using the 1-norm regularization
condition which leads to a generalization performance degrading logarithmically on
the dimension, the generalization performance of the entropy regularization is dimensional
independent [16, 17].
We first consider the normalized entropy for probability distributions:
the prior distribution. The dual is
where we choose the Lagrangian parameter The derivative term of h(v) in ( ) is
The second derivative term of h(v) in ( ) is
-n
-n
Therefore the two terms correspond to the expectation and the variance of x i under the
distribution w. Note that if the second derivative (variance) vanishes, a small positive
number can be used to regularize the solution.
We now consider non-normalized entropy with positive weight w (one can easily deal
with general situation by adding a negative weight part):
(w
The dual is
The Newton's approximation of ( ) is straight-forward.
Remarks
In practice, there is absolutely no reason why we need to choose a regularization term based
on a simple primal form. It is perfectly reasonable (and highly recommended) that we design
a learning algorithm based on a simple choice of the dual function h(v). Whether its dual
g(w) is complicated or not is irrelevant as far as dual algorithms are concerned.
For example, consider the dual of the Huber's function having a simple form of h(v) =2 v 2 (jvj - 1), which can be solved relatively easily. The regularization condition g(w) is a
good replacement for 1-norm regularization. In general, one can choose h(v) as a piecewise
linear or quadratic function.
If we would like w to be concentrated around 0, then an appropriate form for h(v)
should also have a shape that is concentrated around 0. However, because of the uncertainty
principal, the freedom of a dual dimension should be inversely proportional to the freedom
of a primal dimension. This can be easily seen in the case of square regularization since the
kernel K \Gamma1 for the dual problem is the inverse of the kernel K for the primal problem.
If on the other hand, we would like to design an algorithm with w biased toward some
nonzero prior - as in the case of entropy regularization, then one only needs to use a h(v)
that is monotone increasing. Such a function can be easily constructed by using piece-wise
quadratic functions.
4.3 The loss term
Regression
We first consider the standard square-loss regression where regularization
term (15), the line search step ( ) in Algorithm 1 can be solved analytically as:
For robust estimation, we are interested in the case that regularization
term (15), the line search step ( ) in Algorithm 1 can be solved analytically as:
The robustness of naturally explained in the above dual update: since - i is
bounded for each i, therefore the contribution of any one data point - i to the final weight w
is well under control. This principle can be used to directly design the dual form of a robust
regression without resorting to the primal form.
For distribution estimation, we consider a modification of the maximum-entropy method
with
given by the normalized entropy regularization (19). The formulation
becomes the maximum-entropy method when - ! 0. However, we conjecture this
modification has advantage over the standard maximum-entropy method for the same reason
that the soft-margin SVM formulation is often preferred to the optimal-separating hyper-plane
method in practice (in the sense of choosing a nonzero regularization parameter -).
For SVM, the theoretical advantage of an appropriate nonzero regularization parameter has
been demonstrated in [17], even for linearly separable classification problems: it is possible
to achieve exponential rates of convergence with appropriate non-zero regularization param-
eters. No similar results are known for the optimal-separating hyper-plane method. It has in
fact been conjectured in [17] that the generalization performance of the optimal-separating
hyper-plane method is slower than exponential in the worst case.
In this case of modified maximum-entropy method, the Newton's update corresponding
to the line search step ( ) in Algorithm 1 is given by
Note that if - ! 0 (the standard maximum-entropy method), then the update fails. The
reason is that the quadratic penalty method becomes ill-conditioned when the penalty parameter
is close to zero. An easy remedy is to use the modified Lagrangian method which
we have already discussed.
Likelihood
Consider the mixture model estimation problem, where we want to find a distribution w so
that the log-likelihood
maximized. In this case,
the normalized entropy regularization (19). Note that the initial value of - should not be
set as zero anymore since We shall thus start with a positive value 1. the
Newton's update corresponding to the line search step ( ) in Algorithm 1 is given by
If w corresponds to a nicely behaved probability density of a vector random variable in R n ,
then instead of the entropy regularization, a 2-norm based regularization with appropriate
kernel (such as the Fisher kernel) can also be utilized.
Next, we consider the logistic regression for classification problems derived from a maximum-likelihood
estimate: given by (15). In this case,
the Newton step corresponding to ( ) in Algorithm 1 becomes
Again we should start with a non-zero initial value of - 2 (0; 1). For example, 0:5 is a
good choice.
Binary classification
For binary classification, we typically choose a non-negative decreasing f such that f(0) ? 0.
One example is the logistic regression investigated above. In this section, we examine a few
other examples.
We let
Choose g(w) as (15). In this case,
an exact analytical solution can be obtained:
With the same f(u), if we replace the square regularization condition with the normalized
entropy regularization, then the Newton's update for ( ) becomes
shall be chosen based on class label to maximize the margin (see Section 5), and x i shall
be the data vector for an in-class member and the negative data vector for an out-of-class
member. This algorithm corresponds to the normalized Winnow (exponentiated gradient)
update [9] with positive weights in the same way that a support vector machine corresponds
to the Perceptron update [10].
To better understand this, observe that the Perceptron update corresponds to the square
norm regularization and the Winnow update corresponds to the entropy regularization (for
example, see the proofs of both methods in [5], or the comparison of exponentiated gradient
versus gradient descent in [8]). The optimal margin SVM for linearly separable problems
modifies a Perceptron as minimizing the 2-norm under a margin constraint, which corresponds
to the minimization of entropy under the same margin constraint for the Winnow (or
exponentiated gradient) family of algorithms. The soft-margin SVM then modifies the optimal
margin method by introducing a decreasing loss function f with square regularization in
(3). In the case of the Winnow algorithm, this translates to a choice of entropy regularization
with a soft margin SVM-like loss function f in the above update rule. In addition, we can
use other forms of f(u) such as the standard one used in the standard SVM formulation
which we discuss shortly.
From the algorithmic point of view, the relationship of SVM and the Perceptron algorithm
has been mentioned in [12], chapter 12, where Platt has compared the SVM dual update
rule related to (29) to the Perceptron update algorithm. The same analogy of (28) and the
Winnow (or exponentiated gradient) family of algorithms can be readily observed due to
the normalized exponential form of rh(\Delta). It shall be noted that many discussions of the
exponentiated gradient algorithms have emphasized proper matching loss functions (see [6]
for example). In our formulation, a careful choice of matching loss is replaced by a proper
regularization condition which can be combined with any loss function. Also notice that if
non-normalized entropy is used as a regularization condition, then we obtain an algorithm
that corresponds to the non-normalized exponentiated gradient update.
In a SVM, we choose f as:
let g(w) be given by (15). The update is the exact solution for
As mentioned above, Platt has derived the same update rule as (29) in [12]. However, his
derivation employs Bregman's technique [1] suitable only for some specific problems. In
particular, the technique of convex duality which we have adopted in this paper generalizes
Bregman's approach. Also, Platt's comment that (29) does not maximize margin is not true.
In fact, we have found no statistically significant difference of this method from a standard
SVM in our applications. Although special care has to be taken to avoid the potential
zero-denominator problem. See the discussion at the end of Section 5 for implementation
considerations. It shall also be interesting to mention that in [7], the authors have already
adopted the update (29) in their applications.
It is worthwhile to mention that in the standard SVM, there is a shift b which is non-
regularized, we absorb this b into the last component of w by appending a constant feature
(typically 1), then the regularization condition g(w) has a symmetry: g(w
where c is the vector with one in the last component and zero elsewhere. In this case,
Algorithm 2 has to be employed. The corresponding dual constraint (13) is
exact solution for ( ) is modified as:
. The introduction of a non-regularized shift b in the standard SVM
formulation created some complexity in optimization, although not significantly as illustrated
in Section 5. It also seems to have an adverse effect on the generalization analysis by a log(n)
factor. Note that the expected generalization performance of O(1=n) with full regularization
(see Section 6 and [17]) cannot be achieved if there is a non-regularized dimension, because it
is very well known that a non-regularized dimension, with a VC-dimension of 1, contributes a
logarithmic factor into the generalization performance term O(1=n) which is worst case tight
(for example, see [14]). However, this increased variance may be compensated by potentially
reduced bias. The practical difference of using a non-regularized shift versus a regularized
shift is unclear.
5 Experiments
The goal of this section is to illustrate the proposed algorithms by examples, so that the
reader can develop a feeling of the convergence rate of the proposed algorithms in the context
of some existing algorithms. Due to the broad scope of this paper and its theoretical nature,
it is not illuminating to provide examples for every specific instance of learning formulations
we have mentioned in Section 4. We thus only provide two examples, one for Algorithm 1
and one for Algorithm 2. Other instances of the algorithms have similar behaviors.
Since our research interests are mainly in natural language processing, we shall illustrate
the algorithms by text categorization examples. The standard data set for comparing text
categorization algorithms is the Reuters set of news stories, publicly available at
http://www.research.att.com/-lewis/reuters21578.html.
We use Reuters-21578 with ModApte split to partition the documents into training and
validation sets. This data contains 118 classes, with 9603 documents in the training set and
documents in the test set.
In our experiments, we use word stemming without any stop-word removal. We also use
the information gain criterion in [15] to select 1000 most informative word-count features
and use only the binary values of the selected features (which indicates that the word either
appears, or not appears in the document). In text categorization, the performance is usually
measured by precision and recall rather than classification error:
positive
true positive positive
\Theta 100
positive
true positive negative \Theta 100
Since a linear classifier contains a threshold parameter that can be adjusted to trade-off the
precision and the recall, it is conventional to report the break-even point, where precision
equals recall. Since each document in the Reuters dataset can be multiply categorized, it is
common to study the dataset as separate binary classification problems, each corresponding
to a category. The overall performance can be measured by the micro-averaged precision, recall
and the break-even point computed from the overall confusion matrix defined as the sum
of individual confusion matrices corresponding to the categories. In the following examples,
we only use the top ten categories (the remaining categories are typically very small). The
experiments are done on a Pentium II 400 PC under Linux. The timings include training
using the training data with feature selection and testings on the test data, but not the
parsing of documents.
Winnow versus Regularized Winnow
In this example, we study the performances of the regularized Winnow corresponding to
update (28) and of the standard Winnow algorithm with positive weights. We use a learning
rate of 0:001 for the standard Winnow algorithm (approximately optimal for this example):
that is, if a prediction is wrong, we shrink the weight by exp(\Gamma0:001x) if the data x is out
of class; or multiply the weight by exp(0:001x) if the data x is in class. The prediction rule
is: w T x - ' implies out-of-class, and w in-class. w is normalized such that
is a predefined parameter. In the regularized winnow algorithm (28), we let
out-of-class data with the sign of the data
reversed in the training phase. ff is a parameter that attempts to maximize the decision
margin between the in-class and the out-of-class data, which is fixed as 0:1 in our examples
for illustration. Intuitively this corresponds to let the starting point of weight update with
an in-class data be ' ff, and the starting point of weight update with an out-of-class data
be our goal is to achieve a margin of size 2ff. The regularization parameter
in (28) is fixed as 10 \Gamma4 .
We run both algorithms 100 iterations over the data for comparison. Note that kwk
and the data x has f0; 1g components, thus w T x - 1. Also taken the sparsity of the data
into account, it is reasonable for us to pick 0:3 to reflect a good range of
threshold choice.
0:1, the micro-averaged break-even point for Winnow is 83:0, with a CPU time
of 23 seconds; the micro-averaged break-even point for the regularized Winnow is 86:3, with
a CPU time of 26 seconds. At 0:3, the micro-averaged break-even point for Winnow is
81:6, with a CPU time of 23 seconds; the micro-averaged break-even point for the regularized
Winnow is 85:0, with a CPU time of 26 seconds. To have a better feeling of the reported
timing, one notes that a C4.5 decision tree inducer with even 500 features (1000 features
cannot be handled) take hours to finish training (partly because the sparse structure cannot
be utilized). The SMO algorithm for SVM which is one of the fast text categorization
algorithms [2] requires more than three minutes.

Table

1 shows the break-even points for both algorithms for all the ten categories at
0:1. The regularized Winnow is consistently superior. This difference is statistically sig-
nificant, and is comparable of the difference between the SVM and the Perceptron algorithms
indicated in Table 2.
category Winnow Regularized Winnow
acq 82.8 85.4
money-fx 58.7 62.8
grain 78.4 84.7
crude 78.1 78.7
trade 65.3 71.1
interest 61.7 72.5
ship 63.7 75.0
wheat 76.4 83.1
corn 65.5 80.4
micro-average 83.0 86.3

Table

1: Break-even points: Winnow versus Regularized Winnow at
Although the results are not as good as those from a SVM (which achieves a state of
the art performance on text categorization), this comparison is unfair since we only allow
positive weights in our implementation of Winnow style algorithms. This indicates that we
only try to find the most indicative words for a particular topic, but ignore all other words
even though their appearances in a document may strongly suggest that the document does
not belong to the topic. To utilize the additional features, we need a regularized version of
the standard Winnow algorithm with both positive and negative weights. Such a conversion
can be obtained from a vector version of the duality formulation (the weight w is a matrix
and the dual - i at a data point is a vector). Since such an extension is not investigated in
this work, we shall thus skip such a comparison.
Perceptron versus SVMs
In this example, we compare the Perceptron algorithm, the proposed SVM method (30), and
the SMO method for SVM described in chapter 12 of [12], which is currently the preferred
method for solving a SVM problem in text-categorization [2]. The regularization parameter
for the SVMs is fixed as 10 \Gamma3 . The learning rate of the Perceptron is 0:001: that is, if a
prediction is wrong, we update the weight by if the data x is out of class;
or by 0:001x if the data x is in class. The prediction rule is: w T x - 0 implies
out-of-class, and w T x ? 0 implies in-class. We also normalize the weight so that kwk
at the end of each iteration over the data, which enhances the performance.
The total running time for Perceptron (100 iterations over the training data) is 13 seconds.
Its faster speed compared with the Winnow algorithm indicates that Winnow algorithms
spend most time in the normalization step 1 . The proposed formulation (30) is exactly
implemented as described. We use 50 iterations in each call of Algorithm 1, and only 4
iterations in Algorithm 2. Therefore totally we use 200 iterations over the training data.
The running time is 33 seconds. The SMO algorithm is tricky to implement. We have made
our best judgment for trade-offs among its internal parameters with the suggestions given
in [12] as the starting point. The running time for our particular implementation is 191
seconds.

Table

2 includes the comparison (break-even points) of the three algorithms over all ten
categorizes and the micro-averaged break-even points. It can be observed that both SVMs
are consistently better than the Perceptron algorithm. However, there are some statistically
insignificant random discrepancies among the SVMs due to different convergence criteria. It
shall also be useful to point out that j
is in the order of 10 \Gamma6 at the end
of Algorithm 2 for all ten categories. This implies that the dual constraint
largely satisfied. Results similar to SVMs (micro-averaged break-even of 91) can be obtained
by using (27) and 100 iterations of Algorithm 1, with a total run time of 19 seconds. In this
case, a constant feature of value 1 is appended to each data point.
category Perceptron SMO Algorithm 2
acq 92.4 95.5 95.0
money-fx 68.7 69.8 75.4
grain 87.9 91.3 88.6
crude 81.0 81.5 84.1
trade 68.6 73.5 73.5
interest 63.4 74.8 77.1
ship 82.0 82.0 80.9
wheat 77.8 83.1 84.7
corn 77.2 87.5 83.9
micro-average 88.5 91.0 91.2

Table

2: Break-even points: Perceptron versus SVMs
We would like to mention that although in our examples, we have faithfully implemented
the suggested algorithms, it is not important to stick to the specific formulations given in
this paper. For example, there are no magic reasons for the starting value of
or the 50% decrease in the constraint value, or the update -=4 in Algorithm 2. It is
also recommended to use an update value of \Delta- i in ( ) that is smaller than the quantity
In our implementation, Winnows are normalized more frequently in the inner iterations to avoid numerical
instability.
suggested by the Newton's method to gain better numerical stability. For example, we have
observed that for Algorithm 1 with (27) and (29), it is useful to use a small fraction of
the exact \Delta-updates given by the equations. This is especially important for (29) since
the denominator x T
can be zero which causes a large change of - (one can replace
by a regularized version such as 1
smaller increment alleviates the
problem of heavy - oscillation. This phenomenon is less a problem for (30) since a small -
gives a large denominator 1
6 Some learning consequences
For any (differentiable) convex function h, we can define a distance function d h (w; w 0 ) (also
called Bregman divergence [1]) as
It has the property that d h (w; w strictly convex, d h (w; w only
We now consider any n samples X n
1 of (x; y), let ~
we partition this ~ n
samples into m batches of subsamples, with each batch X(i) containing n i data. Let -
denote the optimal solution of (8) with the ~
1 , and let - i denotes the solution of
approximate minimizing of (8) with the i-th batch of subsamples:
denotes the empirical expectation with respect to the i-th batch of n i samples as
in (8). ffl i is a positive approximation error which can be controlled in practice by checking
the duality gap with the primal problem (3).
Now let - i
be the restraint of -   to the i-th batch of subsamples, then
~
~
n-
~
~
h(-
~
~
h(-
~
h(-
~
Note that the first order condition of (8) at the optimal solution implies the following estimation
equation which is another form of (11):
We thus obtain the following inequality:
[-d
Similar to our analysis of the primal problem in [17], we shall ignore the contribution
simplicity. We thus obtain the following fundamental inequality for the dual
~
~
[d
We shall define v
x. Then (33) bounds the
convergence of v i to v   (in terms of the h-Bregman divergence) by the convergence of v i
to
It is also interesting to compare this inequality with its primal form in [17], where the
approximate empirical risk minimizer w n of the primal problem satisfies:
d g (w   ; w
By using the duality of Bregman divergence in [17] and the relationship (11), we have
Note that (33) gives better constants. In fact, it is asymptotically tight in constants compared
with the asymptotic estimates given in [16, 17].
Although learning bounds of the primal formulation has been investigated in [17], it is
insightful to study the implications in terms of the dual variable -. One such bound was
given by Vapnik in term of the number of "support-vectors", i.e. the number of nonzero dual
variables (see [14]). Although Vapnik's bound is very interesting, it has two fundamental
drawbacks.
One drawback is that the bound is not asymptotically "correct" in the sense it gives an
expected generalization error bound slower than O(1=n) with n samples (since the number
of support vectors should usually grow unbounded). However, it has been demonstrated in
[17] the expected generalization error should grow at a rate of O(1=n) in the general case;
furthermore, the misclassification error of training a linear classifier when the problem is
linearly separable can be exponential in n. Note that the later situation is clearly what
Vapnik's bound is intended for, therefore the bound can be asymptotically far inferior than
the correct rate.
The other drawback of Vapnik's bound is that it only handles the situation that the
number of support vectors is small. Although there is no indication that when the number
of support vectors is large, the generalization performance becomes poor, the bound itself
tends to lead the statistical learning community towards thinking that to obtain a good
generalization performance, it is somewhat desirable to reduce the number of support vectors
- for example, this is clearly the case in the design of support vector machines. However,
our analysis, which leads to the "correct" large sample convergence rate, indicates that
minimizing the number of support vectors is not so important. In addition to these drawbacks
of the support vector concept, we also do no have a characterization of learning problems
that can predictably lead to a small number of support vectors. Therefore up to now, the
non-trivialness of the bound solely relies on some empirical evidences, which is not entirely
satisfactory in theory.
The goal of this section is to study the learning aspect of the dual problem more carefully,
so that we can characterize the generalization performance in terms of the dual variables.
This analysis complements the primal analysis studied in [17].
We let ~
n !1 in (33) and X n
1 is chosen in such a way that it approximates the underlying
distribution D. Let -   denote the optimal solution in the limit which can be regarded as
a random variable with respect to D (that is, we shall assume that the solution to the
continuous version of (8) exists. Assume that n simplicity, we denote
them by n. By taking expectations EX nover n randomly chosen data X n
1 , we obtain
denotes the empirical estimation with data X n
1 , and - n denotes the approximate
solution of (8) with error ffl in (31).
The random variable -   is usually very well-behaved. This is because that in the continuous
case, the estimation equation (32) is given by the relationship (11):
if the derivative exists (and a subgradient otherwise, see Appendix A), where w   is the
optimal solution of the primal problem.
Note that the right hand side of (34) becomes the convergence of the empirical expectation
of a random variable to its mean, which can be estimated by standard probability techniques
as illustrated in [17]. For a typical d h that is square-like, the right hand side is variance-like,
thus converges at a rate of O(1=n). Detailed case studies have been given in [17], which we
shall not repeat.
In addition to the expected h-Bregman divergence, we can also obtain an expected exponential
lim
~
~
(d
Using the independence assumption of X ~ n
1 , and taking the limit, we obtain that 8ff ? 0:
which can be used to obtain a large deviation type exponential probability bound. Moment
bounds can also be similarly obtained. See [17] for examples.
With (34) and (36), we can obtain an expected generalization error bound and a large
deviation style probability bound by using techniques in [17]. As we have pointed out earlier,
the primal estimates and the dual estimates are rather similar up to a constant factor of 2
which we shall regard as non-significant for the purpose of deriving generalization bounds.
Therefore we shall not repeat the analysis on those examples given in [17].
In order to see that the expected error bound of (33) cannot be improved, we consider
(34) with linear loss and quadratic regularization:
and
In this case,
Solving the primal problem, we obtain
- KEx, For the dual problem, we have - j b.
becomes:
which is an equality. Since locally g can usually be approximately by a quadratic regularization
and f by a linear loss where b can be (x; y) dependent (we shall intentionally remove
the quadratical term in the f expansion which corresponds to the dropped d k term in (33)),
therefore asymptotically (33) is tight.
7 Concluding remarks
In this paper, we have introduced a dual formulation for a class of regularized linear learning
methods with convex risks. This new formulation is related to online learning algorithms
and stochastic gradient descent methods. The dual form also leads to a generalization of the
kernel formulation for support vector machines. While in a kernel formulation, one usually
substitute the primal-dual relationship (10) into the primal formulation (3), our approach
emphasizes the completely different dual risk (8). This dual formulation leads to new learning
algorithms as well as new insights into certain learning problems.
The intermediate primal-dual formulation is related to the minimax online mistake bound
framework. However, we pose the problem in a PAC style batch setting. This relationship
thus bridges the online learning mistake bound analysis and the PAC analysis. From the
numerical point of view, we are able to obtain new batch learning methods from the dual
formulation. More importantly, these methods can be derived in a very systematic way. As
we have mentioned, it is possible to transform the derived batch learning methods into online
learning algorithms, which we shall leave to another report. Appendix B demonstrates the
basic ideas for obtaining mistake bounds using (33).
It is very natural to ask how general is this duality in machine learning. The primal-dual
formulation views the learning problem in a game-theoretical setting: the learner chooses a
primal weight variable w to minimize a certain risk; the opponent chooses a dual variable that
controls the random sample behavior to maximize the risk. Although the strong duality for
convex-concave programming is difficult to extend to general problems, the game-theoretical
point of view can still be adopted. We conjecture that even when the strong duality is
violated, it may still be possible to design a dual formulation that is appropriate as a learning
method. However, there are many open issues in this area requiring future study.
We have also studied the learning aspect of the dual formulation (8). Specifically we are
able to obtain generalization bounds that have better (asymptotically tight) constants than
those from the primal analysis in [17].
An interesting consequence from the dual analysis is that there is no evidence that the
number of non-zero dual variables (or support vectors) is of any significance. This may not
be very surprising since this number is not stable under even a slight perturbation of the loss
function. The generalization performance bound based on the number of support vectors
can be asymptotically sub-optimal, especially for linearly separable classification problems
the bound was intended for.
The dual formulation also provides valuable insights into learning problems. For exam-
ple, since the number of dual variables is always independent of the dimensionality of the
primal problem, therefore under appropriate regularity assumptions, the dimensionality of
the primal problem should not appear in the learning bounds. This suggests that the frequently
mentioned notion of "the curse of dimensionality" is not really an issue for many
learning problems.
This might seem surprising at first. To understand the implications, we consider the
high dimensional density estimation problem. The standard argument for "the curse of
dimensionality" is that in high dimension, in order to approximate the density function,
one needs to fill out a number of points in a box that is exponential in the dimensionality.
However, this reasoning is only partially valid. This is because that an appropriate way
to measure whether two distributions are similar is by comparing the expectations of a
bounded function with respect to these two distributions. Therefore instead of the point-wise
convergence criterion, we shall consider the convergence in weak topology where the
closeness of two densities are measured by the closeness of their actions on a set of test
functions. This implies that the proper question to ask is that given a fixed number of data,
how many test functions we can utilize to obtain a stable density estimate. This methodology
is used in the maximum entropy method. Note that with appropriate regularity conditions,
the number of test functions we can use is dimensional independent.
However, since we choose the weak topology for the density estimate, we need to determine
the topology of test functions. For a given family of test functions, we need to find
an appropriate structure hierarchy to approximate this family. A proper norm can always
be defined on the test functions so that a dimensional independent partition is obtainable.
The induced dual metric on the density can then be used to measure the convergence of
the density estimate. For example, a typical partition of bounded test function is based on
a log-exponential criterion that induces the entropy metric on the density space (see the
analysis in [17]).
This duality between test functions and density weights is essentially the same duality we
have investigated in this paper. Furthermore, this method of measuring the complexity of a
learning problem is dual to the VC point of view that directly measures the complexity of
the parameter space (in our example, the density function to be estimated). The advantage
of this dual point of view is that we do not rely on the specific parametric function family one
chooses. More importantly, for many learning problems, this complexity can be measured
by the convergence rates of random test functions to their means in the test space (see [17]).
This indicates that well-established probability tools can be applied to obtain the complexity
measurement that is dimensional independent.
A Proof of strong duality
We would like to show that it is valid to interchange the order of inf w and sup - in the
primal-dual formulation (4). We assume that g(w) (as well as other functions involved in
the analysis) can take value as +1 which is equivalent to a data-independent constraint on
We also assume that the solution to the primal problem exists (unique for simplicity).
For notational purposes, let
Then our goal is to show that there exists ( -
-) such that
sup
It is well-known (for example, see [11]) that the duality gap
sup
and (37) is valid if That is, we can find ( -
w) such that
In this case, ( -
w) is called a saddle point.
In the following, we demonstrate the existence of a saddle point by construction. Consider
w that minimizes the primal problem. It is known ([11], page 264) that there exist
subgradients (which is a generalization of the gradient concept for convex functions: see
definitions in [11], Section 23), denoted by @(\Delta) 2 , so thatn
For readers who are not familiar with convex analysis, the above equation becomes the
following estimation equation if the empirical risk is differentiable at -
w:n
-n
By the relationship of subgradients and duality (see [11], page 218), -
w achieves the minimum
of
-n
That is,
Also by the definition of \Gamma -
- i as a subgradient of f(\Delta) at -
and the same relationship
of subgradients and duality ([11], page 218), -
achieves the maximum of
That is,
This finishes the proof.
Conventionally, a subgradient is a set denoted by @(\Delta). However, for notational convenience, we use @(\Delta)
to denote a member of a subgradient set in the proof.
Online mistake bounds
Consider the following scenario: we are given samples
the primal variable w i be the weight obtained by the exact solution of the dual problem (8),
and v i be its dual v
i be the projection of v i onto the first
and v i
i be the projection of v i onto the i-th sample, as in the case of (33). Then by the same
proof of (33):
That is
This inequality is the fundamental bridge of the online learning formulation and the batch
(dual) formulation we have referred to in the paper. To see why this inequality is important:
note that if d h is a square like distance (which is usually true), then the right hand side is of
the order O(1=k 2 ), which implies that kd h (v small. The standard online learning
telescoping technique can then be applied to derive mistake bounds. In our case, this can be
done in a fashion that is similar and parallel to the examples studied in [17]. However, the
general case will be treated in another dedicated report. In the following, we shall merely
provide an illustration by using the square regularization term (15) and draw a conclusion.
For
(v k
That is:
(w
(v k
Now we make an assumption that
That is, the Bregman divergence of L is square like (which is true for smooth loss functions).
Then by using the estimation equation (32):
(v k
Summing over from
(v k
This gives a typical mistake bound that has the correct growth order of log(n) under some
standard assumptions; for example: assume that c i - c and v's are K \Gamma1 norm bounded by
b, then
It is well known that this logarithmic growth is optimal. To see this, consider the one-dimensional
It is easy to verify
that
If we let x then for large k: (w hence the growth
rate of log(n) is achieved by simply summing the above equality over k.
Note that this logarithmic factor indicates that the correct batch learning rate of O(1=n)
cannot be obtained by the typical randomization technique (for example, see [8]) for modifying
online algorithms (and mistake bounds) as batch algorithms. It is also important
to note that the matching loss function concept (cf. [6]) is not important in our analysis,
which allows us to analyze problems with any loss function. The role of the matching loss
function corresponds to a proper choice of the regularization term in our analysis which is
data dependent rather than loss function dependent.



--R

The relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming.
Inductive learning algorithms and representations for text categorization.
Practical methods of optimization.
Matrix computations.
General convergence results for linear discriminant updates.
Relative loss bounds for single neurons.
A discriminative framework for detecting remote protein homologies.
Additive versus exponentiated gradient updates for linear prediction.
Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm
MIT press
Convex analysis.
Smola., editors. Advances in Kernel Methods
Estimation of dependences based on empirical data.
Statistical learning theory.
A comparative study on feature selection in text categoriza- tion
Analysis of regularized linear functions for classification problems.
On the primal formulation of regularized linear systems with convex risks.
--TR

--CTR
Fred J. Damerau , Tong Zhang , Sholom M. Weiss , Nitin Indurkhya, Text categorization for a comprehensive time-dependent benchmark, Information Processing and Management: an International Journal, v.40 n.2, p.209-221, March 2004
Tong Zhang , Fred Damerau , David Johnson, Text chunking based on a generalization of winnow, The Journal of Machine Learning Research, 2, 3/1/2002
Zhang , Yue Pan , Tong Zhang, Focused named entity recognition using machine learning, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
Tong Zhang, Leave-one-out bounds for kernel methods, Neural Computation, v.15 n.6, p.1397-1437, June
Ron Meir , Tong Zhang, Generalization error bounds for Bayesian mixture algorithms, The Journal of Machine Learning Research, 4, 12/1/2003
Tong Zhang, Covering number bounds of certain regularized linear function classes, The Journal of Machine Learning Research, 2, p.527-550, 3/1/2002
Qiang Wu , Yiming Ying , Ding-Xuan Zhou, Multi-kernel regularized classifiers, Journal of Complexity, v.23 n.1, p.108-134, February, 2007
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
logistic regression;support vector machine;linear model;regulation;augmented Lagrangian;convex duality