Support Vector Machines

Perceptron and Linear Separability

假设存在一个 linear decision boundary，它可以完美地对 training dataset 进行分割。那么，经由上述 Perceptron Algorithm 计算，它将返回哪一条 linear separator？

当 linear separator（即一个给定的超平面）的 margin (gamma) 越大，则该模型的归纳与概括的性能越强。从几何的角度（二维）的角度来理解非常直观，我们需要这么一条 linear separator，即，它既能对 training dataset 进行完美的分割，同时，我们希望距它最近的数据点距它的距离最大化（如上图中间的那根直线）。否则，如果存在一个数据点距该 linear separator 的距离不是那么远，从直觉来说，围绕在该数据点附近且与它 label 相同的一个新数据点随意体现出的一个随机波动，将使得这个新数据点越过 linear separator，导致分类错误。

因此，现在的问题是，如何将 margin 纳入考量以求得这条最佳的 linear boundary？支持向量机将很好地解决这个问题。

Motivation（Why SVM？）

以下是 SVM 体现出的眼见的优势：

SVM 返回一个 linear classifier，并且由于其算法使 margin solution 最大化，故这个 linear classifier 是一个稳定的解。
对 SVM 稍加改变，则能提供一种解决当数据集 non-separable 情况的方法。
SVM 同样给出了进行非线性分类的隐性方法（implicit method，即上述的 kernel transformation）。

SVM Formula

假设存在一些 margin (gamma in Gamma) 使得 training dataset (mathcal{S} = mathcal{X} times mathcal{Y}) 线性可分（但注意 linear separator 不一定穿过空间的原点）。

那么，decision boundary：

[g(vec{x}) = vec{w} cdot vec{x} – b = 0
]

Linear classifier：

[begin{align*}
f(vec{x}) & = text{sign}big( g(vec{x}) big) \
& = text{sign} big( vec{w} cdot vec{x} – b big)
end{align*}
]

思路

我们先分别求两个平行的超平面，使得它们对所有的 training data point 进行正确的分类，再使这两个超平面之间的距离最大化。

这也是所谓 “支持向量机（Support Vector Machine）” 名称的由来，我们最终选定的支持向量 (vec{w}) 就像千斤顶一样将上述两个平行的超平面 “支撑” 开来，并且支撑开的距离也将是尽可能的最大，如下图所示。

Derivation

如上图，两个超平面的 decision boundary 可以写作：

[begin{cases}
vec{w} cdot vec{x} – b = 1 \
vec{w} cdot vec{x} – b = -1
end{cases}
]

则两个超平面之间的距离为：

[frac{2}{||vec{w}||}
]

对于初学者的直观理解，推导可以通过二维平面上点到直线的距离进行类比，已知点 ((x_{0}, y_{0})) 到直线 (Ax + By + C = 0) 的计算公式为：

[frac{|Ax_{0} + By_{0} + C|}{sqrt{A^{2} + B^{2}}}
]

因此，设 (vec{w} cdot vec{x} – b = 1) 上任意一点的坐标为 (vec{x_{0}})，故满足：

[vec{w} cdot vec{x_{0}} – b – 1 = 0
]

那么两平行超平面之间的距离为该点到另一超平面 (vec{w} cdot vec{x} – b = -1) 的距离，即：

[begin{align*}
frac{|vec{w} cdot vec{x_{0}} – b + 1|}{sqrt{||vec{w}||^{2}}} & = frac{|big( vec{w} cdot vec{x_{0}} – b – 1 big) + 2|}{sqrt{||vec{w}||^{2}}} \
& = frac{2}{||vec{w}||}
end{align*}
]

因此，对于 (forall i in mathbb{N}^{+})，当：

[begin{cases}
vec{w} cdot vec{x_{i}} – b geq 1 qquad qquad text{if } y_{i} = 1 \
vec{w} cdot vec{x_{i}} – b leq -1 qquad quad text{if } y_{i} = -1
end{cases}
]

则 training data 全部被正确地分类。

理解

参考上图，此处 (vec{w} cdot vec{x_{i}} – b geq 1) 和 (vec{w} cdot vec{x_{i}} – b leq -1) 的几何意义是，将对于 label 为 (1) 和 (-1) 的 data point 分别排除在超平面 (vec{w} cdot vec{x} – b = 1) 和 (vec{w} cdot vec{x} – b = -1) 的两边外侧，从而留下两个超平面之间的空档。

我们合并上面两式为一个式子，则 training data 全部被正确地分类等价于：

[forall i in mathbb{N}^{+}: ~ y_{i} big( vec{w} cdot vec{x_{i}} – b big) geq 1
]

现在我们得到了两个超平面的距离表达式 (frac{2}{||vec{w}||})，同时需要满足 constraints (y_{i} big( vec{w} cdot vec{x_{i}} – b big) geq 1) for (forall i in mathbb{N}^{+})，我们希望在约束条件下使 (frac{2}{||vec{w}||}) 最大，那么 SVM 转变为运筹问题的求解，i.e.，

[begin{align*}
text{maximize: } quad & frac{2}{||vec{w}||} \
text{subject to: } quad & y_{i} big( vec{w} cdot vec{x_{i}} – b big) geq 1, quad forall i in mathbb{N}^{+}
end{align*}
]

SVM Standard (Primal) Form

注意到，(||vec{w}|| geq 0) 恒成立，且若 (||vec{w}|| = 0) 时，支持向量（即权重向量）(vec{w}) 为零向量，使得 linear separator 无意义。故最大化 (frac{2}{||vec{w}||}) 等价于最小化 (frac{1}{2} ||vec{w}||)。类似于线性回归中使用 Mean Square Error 而非 Mean Absolute Error 作为 loss function 的原因，(||vec{w}||) 在原点处不可微，因此我们选择 minimize (frac{1}{2} ||vec{w}||^{2})，而非原形式 (frac{1}{2}||vec{w}||)，这当然是等价的。

故 SVM Standard (Primal) Form 如下：

[begin{align*}
text{minimize: } quad & frac{1}{2} ||vec{w}||^{2} \
text{subject to: } quad & y_{i} big( vec{w} cdot vec{x_{i}} – b big) geq 1, quad forall i in mathbb{N}^{+}
end{align*}
]

SVM When Training Dataset is Non-separable

当 training dataset 无法被全部正确地分类时（即，不存在一个 margin (gamma in Gamma) 使得 training dataset (mathcal{S} = mathcal{X} times mathcal{Y}) 线性可分），可以引入 slack variables 求解问题。

SVM Standard (Primal) Form with Slack

SVM Standard (Primal) Form with Slack 如下所示：

[begin{align*}
& text{minimize: } quad frac{1}{2} ||vec{w}||^{2} + C sumlimits_{i=1}^{n} xi_{i} \
& text{subject to: } quad begin{cases}
y_{i} big( vec{w} cdot vec{x_{i}} – b big) geq 1 – xi_{i}, quad forall i in mathbb{N}^{+} \
xi_{i} geq 0, qquad qquad qquad qquad forall i in mathbb{N}^{+} \
end{cases}
end{align*}
]

问题：如何求解最优的 (vec{w}, ~ b, ~ vec{xi}) ？

由于涉及边界问题，我们不能在目标函数中直接对 (vec{w}, ~ b, ~ vec{xi}) 求偏导。我们有以下两种解决办法：

Projection Methods

从一个满足 constraints 的解 (vec{x_{0}}) 开始，求能使得 objective function 略微减小的 (vec{x_{1}})。如果所求到的 (vec{x_{1}}) 违反了 constraints，那么 project back to the constraints 进行迭代。这种方法偏向于利用算法求解，从原理上类似于梯度下降算法以及前文介绍的 Perceptron Algorithm。
Penalty Methods

使用惩罚函数将 constraints 并入 objective function，对于违反 constraints 的解 (vec{x}) 予以惩罚。

The Lagrange (Penalty) Method：拉格朗日（惩罚）方法

考虑增广函数：

[L(vec{x}, vec{lambda}) = f(vec{x}) + sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x})
]

其中，(L(vec{x}, vec{lambda})) 为拉格朗日函数，(lambda_{i}) 为拉格朗日变量（或对偶变量，dual variables）。

对于此类函数，我们所需要的目标的 canonical form 为：

[begin{align*}
text{minimize: } quad & f(vec{x}) \
text{subject to: } quad & g_{i}(vec{x}) leq 0, quad forall i in mathbb{N}^{+}
end{align*}
]

由于 (g_{i}(vec{x}) leq 0) for (forall i in mathbb{N}^{+})，则对于任意的 feasible (vec{x}) 以及任意的 (vec{lambda_{i}} geq 0)，都有：

[L(vec{x}, vec{lambda}) leq f(vec{x})
]

因此：

[maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) leq f(vec{x})
]

注意到上式中的 (maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}))，这代表我们在 (vec{lambda}) 所在的空间 ([0, ~ infty)^{n}) 中搜索使拉格朗日函数最大的 (vec{lambda})，即搜索各个对应的 (lambda_{i} in [0, ~ infty))。

尤其注意上式 是针对 feasible (vec{x}) 成立。因为 (maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda})) 会导致：

当 (vec{x}) infeasible 时，意味着 (vec{x}) 不全满足所有约束条件 (g_{i}(vec{x}) leq 0) for (forall i in mathbb{N}^{+})，这意味着：

[exists i: ~ g_{i}(vec{x}) > 0
]

那么：

[begin{align*}
maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) & = maxlimits_{lambda_{i} geq 0} Big( f(vec{x}) + sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) Big) \
& = f(vec{x}) + maxlimits_{lambda_{i} geq 0} sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) \
& = infty
end{align*}
]

这是因为：只要对应的 (lambda_{i} rightarrow infty)，则 (lambda_{i} g_{i}(vec{x}) rightarrow infty)（因为 (g_{i}(vec{x}) > 0)），从而 (sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) rightarrow infty)，故 (L(vec{x}, vec{lambda}) = f(vec{x}) + sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) rightarrow infty)。

所以此时不满足 (maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) leq f(vec{x}))。
当 (vec{x}) feasible 时，即对于 (forall i in mathbb{N}^{+})，约束条件 (g_{i}(vec{x}) leq 0) 都成立，那么：

[forall i in mathbb{N}^{+}: ~ g_{i}(vec{x}) quad implies quadsumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) leq 0
]

因此 (maxlimits_{lambda_{i} geq 0} sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) = 0)，即令所有 (lambda_{i}) 都为 (0)，故：

[begin{align*}
maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) & = maxlimits_{lambda_{i} geq 0} Big( f(vec{x}) + sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) Big) \
& = f(vec{x}) + maxlimits_{lambda_{i} geq 0} Big( sumlimits_{i=1}^{n} lambda_{i} g_{i}(vec{x}) Big) \
& = f(vec{x})
end{align*}
]

根据上述结论，给定任意 feasible (vec{x}) 以及任意 (lambda_{i} geq 0)，有：

[L(vec{x}, vec{lambda}) leq f(vec{x})
]

且：

[maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) = begin{cases}
f(vec{x}) qquad text{if } vec{x} text{ feasible} \
infty qquad quad text{if } vec{x} text{ infeasible}
end{cases}
]

因此，原先的 constrained optimization problem 的 optimal solution 为：

[p^{star} = minlimits_{vec{x}} maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda})
]

如何理解 (minlimits_{vec{x}} maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}))？

(L(vec{x}, vec{lambda})) 是向量 (vec{x}) 和 (vec{lambda}) 的函数，从向量角度可以抽象为一个二元函数。因此，计算逻辑是，对于每一个给定的 (vec{x_{0}})，可以得到仅关于 (vec{lambda}) 的函数 (L(vec{x_{0}}, vec{lambda}))，然后求出使对应的 (L(vec{x_{0}}, vec{lambda})) 最大的各 (vec{lambda_{(vec{x_{0}})}}^{*})（i.e.，各 (lambda_{i}^{*})）。因此内层 (maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda})) 返回一个对于任意给定的 (vec{x_{0}})，使得 (L(vec{x_{0}}, vec{lambda})) 最大的 (vec{lambda}) 的集合。那么，(maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda})) 是一个仅关于 (vec{x}) 的函数，再在外层求使得这个函数最小的 (vec{x}^{*})，即 (minlimits_{vec{x}} Big( maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) Big))，其结果可以写为：

[minlimits_{vec{x}} maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda}) = L(vec{x}^{*}, vec{lambda_{(vec{x}^{*})}}^{*})
]

解释（为什么它是 optimal solution？）：

因为，对于任意的 (vec{x})（无论是否 feasible），(maxlimits_{lambda_{i} geq 0} L(vec{x}, vec{lambda})) 计算出的结果可能为 (f(vec{x}))（当 (vec{x}) 为 feasible），也可能为 (infty)（当 (vec{x}) 为 infeasible）。但没关系，在最外层的 (minlimits_{vec{x}}) 可以对 (vec{x}) 进行筛选，使最终选出的 (vec{x}^{*}) 不可能为 infeasible，否则相当于 (minlimits_{vec{x}}) 计算出的结果为 (infty)，这是只要存在 feasible region 就不可能发生的事情。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net

Perceptron, Support Vector Machine and Dual Optimization Problem (3)