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

Support Vector Machines

Perceptron and Linear Separability

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

Motivation（Why SVM？）

SVM 返回一个 linear classifier，并且由于其算法使 margin solution 最大化，故这个 linear classifier 是一个稳定的解。

SVM 同样给出了进行非线性分类的隐性方法（implicit method，即上述的 kernel transformation）。

SVM Formula

那么，decision boundary：

\[g(\vec{x} = \vec{w} \cdot \vec{x} - b = 0 \]

\[\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 进行正确的分类，再使这两个超平面之间的距离最大化。

Derivation

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

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

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

\[\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 \]

\[\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 全部被正确地分类等价于：

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

\[\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}||\，这当然是等价的。

\[\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

\[\begin{align*} & \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}\ ？

Projection Methods

Penalty Methods

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

考虑增广函数：

\[L(\vec{x}, \vec{\lambda} = f(\vec{x} + \sum\limits_{i=1}^{n} \lambda_{i} g_{i}(\vec{x} \]

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

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

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

因此：

\[\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda} \leq f(\vec{x} \]

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

\[\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*} \]

所以此时不满足 \(\max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda} \leq f(\vec{x}\。

\[\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*} \]

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

且：

\[\max\limits_{\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} \]

\[p^{\star} = \min\limits_{\vec{x}} \max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda} \]

如何理解 \(\min\limits_{\vec{x}} \max\limits_{\lambda_{i} \geq 0} L(\vec{x}, \vec{\lambda}\？

\[\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 就不可能发生的事情。

编程笔记 » Perceptron, Support Vector Machine and Dual Optimization Problem (3)