Perceptron, Support Vector Machine and Dual Optimization Problem (3)
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:
\]
Linear classifier:
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 可以写作:
\vec{w} \cdot \vec{x} - b = 1 \\
\vec{w} \cdot \vec{x} - b = -1
\end{cases}
\]
则两个超平面之间的距离为:
\]
对于初学者的直观理解,推导可以通过二维平面上点到直线的距离进行类比,已知点
\((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}^{+}\)
,当:
\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 全部被正确地分类等价于:
\]
现在我们得到了两个超平面的距离表达式
\(\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.,
\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 如下:
\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 如下所示:
& \text{minimize: } \quad \frac{1}{2} ||\vec{w}||^{2} + C \sum\limits_{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})\)
为拉格朗日函数,
\(\lambda_{i}\)
为拉格朗日变量(或对偶变量,dual variables)。
对于此类函数,我们所需要的目标的 canonical form 为:
\text{minimize: } \quad & f(\vec{x}) \\
\text{subject to: } \quad & g_{i}(\vec{x}), \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\)
,都有:
\]
因此:
\]
注意到上式中的
\(\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda})\)
,这代表我们在
\(\vec{\lambda}\)
所在的空间
\([0, ~ \infty)^{n}\)
中搜索使拉格朗日函数最大的
\(\vec{\lambda}\)
,即搜索各个对应的
\(\lambda_{i} \in [0, ~ \infty)\)
。
尤其注意上式
是针对 feasible
\(\vec{x}\)
成立。因为
\(\max\limits_{\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*}
\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda}) & = \max\limits_{\lambda_{i} \geq 0} \Big( f(\vec{x}) + \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \Big) \\
& = f(\vec{x}) + \max\limits_{\lambda_{i} \geq 0} \sum\limits_{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\)
),从而
\(\sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \rightarrow \infty\)
,故
\(L(\vec{x}, \vec{\lambda}) = f(\vec{x}) + \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \rightarrow \infty\)
。所以此时不满足
\(\max\limits_{\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 \quad\sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \leq 0
\]
因此
\(\max\limits_{\lambda_{i} \geq 0} \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) = 0\)
,即令所有
\(\lambda_{i}\)
都为
\(0\)
,故:
\[\begin{align*}
\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda}) & = \max\limits_{\lambda_{i} \geq 0} \Big( f(\vec{x}) + \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \Big) \\
& = f(\vec{x}) + \max\limits_{\lambda_{i} \geq 0} \Big( \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x}) \Big) \\
& = f(\vec{x})
\end{align*}
\]
根据上述结论,给定任意 feasible
\(\vec{x}\)
以及任意
\(\lambda_{i} \geq 0\)
,有:
\]
且:
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 为:
\]
如何理解
\(\min\limits_{\vec{x}} \max\limits_{\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}^{*}\)
)。因此内层
\(\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda})\)
返回一个对于任意给定的
\(\vec{x_{0}}\)
,使得
\(L(\vec{x_{0}}, \vec{\lambda})\)
最大的
\(\vec{\lambda}\)
的集合。那么,
\(\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda})\)
是一个仅关于
\(\vec{x}\)
的函数,再在外层求使得这个函数最小的
\(\vec{x}^{*}\)
,即
\(\min\limits_{\vec{x}} \Big( \max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda}) \Big)\)
,其结果可以写为:
\[\min\limits_{\vec{x}} \max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda}) = L(\vec{x}^{*}, \vec{\lambda_{(\vec{x}^{*})}}^{*})
\]
解释(为什么它是 optimal solution?):
因为,对于任意的
\(\vec{x}\)
(无论是否 feasible),
\(\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda})\)
计算出的结果可能为
\(f(\vec{x})\)
(当
\(\vec{x}\)
为 feasible),也可能为
\(\infty\)
(当
\(\vec{x}\)
为 infeasible)。但没关系,在最外层的
\(\min\limits_{\vec{x}}\)
可以对
\(\vec{x}\)
进行筛选,使最终选出的
\(\vec{x}^{*}\)
不可能为 infeasible,否则相当于
\(\min\limits_{\vec{x}}\)
计算出的结果为
\(\infty\)
,这是只要存在 feasible region 就不可能发生的事情。