SVM 支持向量机
1. SVM 基本模型
1.1 线性可分问题
给定一个训练样本集 \(D = \{(x_1, y_1), (x_2, y_2), ... , (x_n, y_n)\}, \; y_i \in \{-1, +1\}\)。假设两个点集 \(D_0\) 和 \(D_1\)，且 \(D_0 \subset D, D_1 \subset D\) , 若存在一个 \(d\) 维向量 \(w\) 和实数 \(b\)，使得对于所有属于 \(D_0\) 的样本点 \(x_i\) 都有 \(wx_i + b > 0\) 同时 对于所有属于 \(D_1\) 的样本点 \(x_j\) 都有 \(wx_j + b < 0\)，那么称 \(D_0\) 和 \(D_1\) 线性可分。
简单得说，就是最佳划分，能够使得 \(D\) 中的样本点分为两个类别。
1.2 划分超平面
有时候问题是二维甚至是多个维度的，而这样一个划分，通常被称为 划分超平面。在样本空间中，划分超平面 可通过如下线性方程去描述：
\[w^T x + b = 0
\]
其中 \(w = [w_1; w_2; ... ; w_d]\) ，\(w\) 决定了超平面的方向；\(d\) 为偏移量，决定了超平面与原点之间的距离。
显然在样本空间 \(D\) 中的任意点 \(x\) 到超平面的距离可以用以下公式来描述：
\[r = \frac{|w^T x + b|}{||w||}
\]
记为 \((w, b)\)
其中 \(||w|| = \sqrt{\sum_{i=1}^{d}w_i^2}\)，即向量的 L2 范数。
划分超平面 所产生的分类结果是最具鲁棒性的，对未见示例的泛化能力最强。
1.3 支持向量
假设超平面 \((w, b)\) 能够将训练集 \(D\) 进行正确分类，且有距离 \(\text{dist}\) ，使得每一个样本点 \((x_i, y_i) \in D\)，当 \(y_i = +1\) 时，\(w^Tx + b \ge \text{dist}\) ；当 \(y_i = -1\) 时，\(w^Tx + b \le \text{dist}\) 。
由于 \(||w||\) 和 \(\text{dist}\) 都满足 大于 0（当然有可能时无限趋近于0的），可以令：
\[\begin{cases}
w^Tx_i + b \ge +1, \quad y = +1
\\
w^Tx_i + b \le -1, \quad y = -1
\end{cases}
\]
可以将上述方程组合并：
\[y_i(w^Tx_i + b) \ge 1, \quad i \in \{1, 2, ... , n \}
\]
距离超平面 最近 的几个训练样本点使得上述不等式 等号成立，这些点被称为 支持向量 。
两个 不同类支持向量 到超平面的距离之和为：
\[\gamma = \frac{2}{||w||}
\]
\(\gamma\) 也被称之为 间隔 (\(\text{margin}\))
1.4 最大化间隔
\(\text{SVM}\) 要解决的，就是找到 最大间隔的划分超平面 \((w, b)\)，即找到最优参数 \(w\) 和 \(b\) 使得 间隔 \(\gamma\) 最大。
形式化表述为：
\[\begin{split}
& \max_{w, b} \frac{2}{||w||} \qquad \text{s.t.} \;\; y_i(w^Tx_i + b) \ge 1, \quad i = \{1, 2, ... , n\}
\end{split}
\]
显然，为了最大化间隔(\(\text{margin}\))，只需最大化 \(||w||^{-1}\)，也即 最小化 \(||w||\)。
那么为了方便计算，我们往往会除去的根号，转换成 最小化 \(||w||^2\) 的最优化问题。可以形式化表述为：
\[\begin{split}
& \min_{w, b} \frac{1}{2}||w||^2 \qquad \text{s.t.} \;\; y_i(w^Tx_i + b) \ge 1, \quad i = \{1, 2, ... , n\}
\end{split}
\]
这就是基本的 支持向量机 \(\text{SVM}\) (\(\text{Support} \; \text{Vector} \; \text{Machine}\)) 模型。
2. 对偶问题
2.1 拉格朗日乘子法求解SVM
前面了解了 最大间隔划分超平面，令：
\[f(x) = w^Tx + b
\]
对于上面的 最大化间隔 问题，也即 最小化 \(||w||^2\) 问题，使用 拉格朗日乘子法 得到其 对偶问题 (\(\text{dual} \; \text{problem}\))。
具体来说，对上面的问题中的每条约束添加 拉格朗日乘子 \(\alpha_i \ge 0\)，则此问题的 拉格朗日函数 可写为：
\[L(w, b, \alpha) = \frac{1}{2}||w||^2 + \sum_{i=1}^n \alpha_i (1 - y_i(w^Tx_i + b))
\]
其中 \(\alpha = [\alpha_1; \alpha_2, ... , \alpha_n]\)
令 \(L(w, b, \alpha)\) 对 \(w\) 和 \(b\) 的偏导为 \(\text{0}\):
\[\begin{split}
& \frac{\partial L}{\partial w} = w - \sum_{i=1}^n \alpha_i y_i x_i = 0
\\\\
& \frac{\partial L}{\partial b} = - \sum_{i=1}^n \alpha_i y_i = 0
\end{split}
\]
可得
\[\begin{split}
& w = \sum_{i = 1}^n \alpha_i y_i x_i
\\\\
& \sum_{i=1}^n \alpha_i y_i = 0
\end{split}
\]
将上面的等式带入 \(L(w, b, \alpha)\)
\[\begin{split}
& L(w, b, \alpha) = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x^T_ix_j + \sum_{i=1}^n \alpha_i - \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x^T_ix_j
\\\\
& \qquad \qquad = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x^T_ix_j
\end{split}
\]
由此可以得到 对偶问题:
\[\begin{split}
& \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j x^T_ix_j
\\\\
& \qquad \qquad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0,
\\\\
& \qquad \qquad \quad \quad \;\; \alpha_i \ge 0, \quad i = \{1, 2, ... , n\}
\end{split}
\]
解出 \(\alpha\) 后，求出 \(w\) 和 \(b\) 即可得到 最大间隔划分超平面:
\[f(x) = w^Tx + b = \sum^m_{i=1} \alpha_i y_ix^T_i x + b
\]
对于对偶问题解出的 \(\alpha_i\)，称为 \(L(w, b, \alpha)\) 中的 拉格朗日乘子，对应每一个样本 \((x_i, y_i)\)。
上述过程满足 \(\text{KKT}\) 条件：
\[\begin{cases}
& \alpha_i \ge 0
\\
& y_if(x_i) - 1 \ge 0
\\
& \alpha_i (y_if(x_i) - 1) = 0
\end{cases}
\]
对于任意样本 \((x_i, y_i) \in D\)，总有 \(\alpha_i = 0\) 或者 \(y_if(x_i) = 1\)。
当 \(\alpha_i = 0\)，则不会对 \(f(x_i)\) 造成任何影响；当 \(\alpha_i > 0\)，此时必有 \(y_if(x_i) = 1\)，即样本点在最大间隔的边界上，也就是一个 支持向量 。
3. SVM 与 核函数
3.1 线性不可分问题
前面我们讨论了SVM求解线性可分问题，然而显示生活中，样本往往是 线性不可分的，即原本的样本空间不存在一个可以正确划分两类样本的划分超平面。
经典的线性不可分问题（异或问题）
对于 线性不可分 问题，可以将样本空间映射到一个 更高维度 的空间，使得样本在此特征空间内线性可分。
原始样本空间是 有限维 的，那么 一定存在一个高维度空间使得样本可分。
3.2 对偶问题（线性不可分）
令 \(\phi(x)\) 为 \(x\) 映射到高维空间的特征向量，则 特征空间的划分超平面 可以表示为：
\[f(x) = w^T \phi(x) + b
\]
其对应的 对偶问题 为：
\[\begin{split}
& \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \phi(x_i)^T\phi(x_j)
\\\\
& \qquad \qquad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0,
\\\\
& \qquad \qquad \quad \quad \;\; \alpha_i \ge 0, \quad i = \{1, 2, ... , n\}
\end{split}
\]
3.3 核函数的作用
在上面求解式中涉及到计算 $\phi(x_i)^T\phi(x_j) $，由于特征空间维数可能很高，计算往往会非常困难。
所以这里可以设想一个函数：
\[\kappa(x_i, x_j) = \left \langle \phi(x_i),\phi(x_j) \right \rangle = \phi(x_i)^T\phi(x_j)
\]
即 \(x_i\) 和 \(x_j\) 在 特征空间的内积等于它们在原始的样本空间中通过 函数 \(\kappa\) 计算得出的结果。这就避免了高维度的计算。
由此 对偶问题 可以重写为：
\[\begin{split}
& \max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j y_i y_j \kappa(x_i, x_j)
\\\\
& \qquad \qquad \text{s.t.} \quad \sum_{i=1}^n \alpha_i y_i = 0,
\\\\
& \qquad \qquad \quad \quad \;\; \alpha_i \ge 0, \quad i = \{1, 2, ... , n\}
\end{split}
\]
求解后得到：
\[\begin{split}
f(x) & = w^T\phi(x) + b
\\\\
& = \sum_{i=1}^n\alpha_iy_i\phi(x_i)^T \phi(x) + b
\\\\
& = \sum_{i=1}^n\alpha_iy_i\kappa(x_i, x) + b
\end{split}
\]
此处的 \(\kappa\) 其实就是所谓的 核函数。
未完待续...
