SVM as a Convex Optimization Problem
Leon Gu
CSD, CMU
Convex Optimization
I Convex set: the line segment between any two points lies in the set.
I Convex function: the line segment between any two points (x, f (x))
and (y, f (y)) lies on or above the graph of f .
I Convex optimization
minimize f0 (x) (1)
s.t. fi (x) ≤ 0 i = 1, . . . , m (2)
hi (x) = 0 i = 1, . . . , p (3)
I f0 and fi convex, hi linear.
I convex objective function, convex domain (feasible set).
I any local optimum is also a global optimum.
I Operations preserve convexity
I (for convex sets) intersection, affine transformation,
perspective transformation, ...
I (for convex functions) nonnegative weighted sum, maximum
and supremum, composition with affine functions,
composition with monotonic convex/concave functions, ...
Optimal Separating Hyperplane
Suppose that our data set {xi , yi }N
i=1 is linear separable. Define a
hyperplane by
{x : f (x) = β T x + β0 = β T (x − x0 ) = 0} where kβk = 1.
I f (x) is the sign distance to the hyperplane.
I we can define a classification rule induced by f (x): sgn[β T (x − x0 )];
Define the margin of f (x) to be the minimal yf (x) through the data
C = min yi f (xi )
i
A optimal separating hyperplane is the hyperplane that maximizes the
margin,
max C, s.t. yi (β T xi + β0 ) ≥ C, i = 1, . . . , N
β,β0 ,kβk=1
We can get rid of the norm constraint on β,
1
yi (β T xi + β0 ) ≥ C
kβk
and arbitrarily set kβk = 1/C, then we can rephrase the problem as
min kβk , s.t. yi (β T xi + β0 ) ≥ 1, i = 1, . . . , N
β,β0
This is a convex optimization problem.
Soft Margin SVM
The data is not always perfect. We need to extend optimal separating
hyperplane to non-separable cases. The trick is to relax the margin
constraints by introducing some “slack” variables.
minimize kβk over β, β0 (4)
s.t. yi (β T xi + β0 ) ≥ 1 − ξi , i = 1, . . . , N (5)
N
X
ξi ≥ 0; ξi ≤ Z (6)
i=1
I still convex.
I ξi > 1 – misclassification
ξi > 0 – the data is correctly classified but lies in the margin.
I Z is a tuning parameter.
How to solve it? Use Lagrange/duality theory.
Lagrangian Theory
Lagrangian theory characterizes the solution of a constrained
optimization problem. Recall the primal problem:
minimize f0 (x) (7)
s.t. fi (x) ≤ 0 i = 1, . . . , m (8)
hi (x) = 0 i = 1, . . . , p (9)
The stationary points are given by
m p
df0 (x) X dfi (x) X dhi (x)
+ λi + νi =0
dx i=1
dx i=1
dx
where λ, ν are free parameters called Lagrange multipliers. Accordingly,
we define Lagrangian prime function (or Lagrangian) as
m
X p
X
L(x, λ, ν) = f0 (x) + λi fi (x) + νi hi (x).
i=1 i=1
We define Lagrangian dual function g(λ, ν) as
g(λ, ν) = inf L(x, λ, ν).
x∈X
The so-called Lagrangian dual problem is the following:
maximize g(λ, ν) (10)
s.t. λ > 0. (11)
The weak duality theorem says
g(λ, ν) ≤ f0 (x∗ ) for all λ and ν
In other words, maximizing g(λ, ν) over λ and ν produce a bound on
f0 (x∗ ) (Note that g(λ, ν) is piecewise linear and convex). The difference
between g(λ∗ , ν ∗ ) and f0 (x∗ ) is called the “duality gap”.
K.K.T. Conditions
Slater’s Theorem (Strong Duality Theorem) says: if the constraint
functions are affine, the duality gap is zero.
Then, K.K.T. conditions provide necessary and sufficient conditions for
a point x∗ to be an optimum
∂L(x,λ∗ ,ν ∗ )
∂x =0 first-order derivative of optimality
x∗
λ∗i fi (x∗ ) =0 complementary slackness conditions
λ∗i ≥0 dual constraints
fi (x∗ ) ≤0 prime constraints
hi (x∗ ) =0 prime constraints
Remarks: complementary slackness conditions are directly related to
support vectors.
The Dual Problem
Recall the prime problem (soft-margin SVM)
minimize kβk over β, β0 (12)
s.t. yi (β T xi + β0 ) ≥ 1 − ξi , i = 1, . . . , N (13)
N
X
ξi ≥ 0; ξi ≤ Z (14)
i=1
Obviously strong duality holds. So we can find its dual problem by the
following steps
1. Define Lagrange primal function (and Lagrange multipliers).
2. Take the first-order derivatives w.r.t. β, β0 and ξi , and set to zero.
3. Substitute the results into the primal function.
N N N
X 1XX
Maximize LD = αi − αi αi0 yi yi0 hxi , xi0 i (15)
i=1
2 i=1 0
i =1
s.t. 0 ≤ αi ≤ γ, i = 1, . . . , N (16)
N
X
αi yi = 0 (17)
i=1
Solution : (18)
N
X
β̂ = α̂i yi xi (19)
i=1
N
X
f (x) = β T x + β0 = α̂i yi hxi , xi + β0 (20)
i=1
I Sparse representation: the separating hyperplane f (x) is spanned
those data points i where αi 6= 0, called Support Vectors.
I follows directly from complementary slackness conditions:
αi yi (β T xi + β0 ) + ξi − 1 = 0
I Both the estimation and the evaluation of f (x) only involve dot
product.