SVM 推导

1. Intuition

（每个）样本点距离分类面越远，说明分类面选得越好。为了度量这一点，我们引入函数间隔和几何间隔。这里的间隔（margin）指的是点与分类面的间隔。

函数间隔

• 单个样本
  \[ \hat{\gamma}_i=y_i(\omega^Tx+b) \]

• 样本集
  \[ \hat{\gamma}=\min_{1..m}\hat{\gamma}_i \]

• 性质
  由于没有对 w 和 b 进行归一化，函数间隔在两者 scale 时候，将会成倍变化。

几何间隔

• 单个样本
  \[ \gamma_i = \hat{\gamma}_i / ||\omega||\]

• 样本集
  \[ \gamma=\min_{1..m}\gamma_i \]

• 性质
  对 w 进行了归一化，这样，在最优化的时候，我们可以针对 w 的长度施加各种限制，但不影响最终结果。

2. 最优化问题

问题化简

1. 基础形态
   \[ \max_{\gamma,\omega,b}\gamma \\ y_i(\omega^tx+b)\ge\gamma \\ ||w||=1\]
   最优化条件非凸

2. 基础形态2
   \[ \max_{\hat{\gamma},\omega,b}\hat{\gamma}/||w|| \\ y_i(\omega^tx+b)\ge\hat{\gamma} \]
   最优化目标非凸

3. QP形态（施加限制，函数间隔为1，且最大变最小）
   \[ \min_{\omega,b}1/2||w||^2 \\ y_i(\omega^tx+b)\ge1 \]
   二次规划（凸）

对偶问题

对于最优化问题：

\[ \min_\omega f(\omega) \\ g_i(\omega)\le0\ (i=1...k) \\ h_i(\omega)=0\ (i=1..l)\]

有广义拉格朗日函数:

\[ L(\omega,\alpha,\beta) = f(\omega)+\Sigma\alpha_ig_i(\omega) + \Sigma\beta_ih_i(\omega) \]

其中要求 alpha 大等于0（显然，否则 Primal 问题不成立）

• Primal 问题 (p*)
  \[ \min_\omega\max_{\alpha,\beta}L(\omega,\alpha,\beta) \]
  一旦 w 超出限定范围，内层的 max 立马飙到正无穷

• Dual 问题 (d*)
  \[ \max_{\alpha,\beta}\min_\omega L(\omega,\alpha,\beta) \]

• 两者关系
  \[ d^*\le p^*\]
  根据alpha,beta,g,h的取值范围，在可行域内，拉格朗日函数必须小等于f(w)，自然也小等于p*，无论它怎么min，max，依然小等于。

在f,g是凸函数，h是仿射函数（wx+b)，且g包围的区域不为空的时候

w*是原问题的解，alpha*，beta*是对偶问题的解，且
\[ d^*=p^*=L(\omega^*,\alpha^*,\beta^*)\]

此时，有KKT条件成立（充要？）

\[ \frac{\partial}{\partial \omega_i}L(\omega^*,\alpha^*,\beta^*)=0 \\
\frac{\partial}{\partial \beta_i}L(\omega^*,\alpha^*,\beta^*)=0 \\
\alpha^*_ig_i(\omega^*)=0 \\
g_i(\omega^*)\le0 \\
\alpha^*\ge0
\]

3. 将QP转换为Dual形式

重写限制条件

\[ g_i(\omega)=1-y_i(\omega^Tx_i+b)\le0\]
性质：根据KKT条件，当alpha_i大于0时，g_i(w)=0，此时xi是支撑矢量。

构造广义拉格朗日函数

\[ L(\omega,b,\alpha)=1/2||w||^2+\Sigma\alpha_ig_i(\omega)\\
= 1/2||w||^2+\Sigma_{i=1..m}\alpha_i[1-y_i(\omega^Tx_i+b)]\\
= 1/2||w||^2+\Sigma\alpha_i-\Sigma\alpha_iy_i\omega^Tx_i-\Sigma\alpha_i y_i b
\]

对于 w 求最小值

令
\[
\frac{\partial}{\partial\omega}L(\omega,b,\alpha)\\
=\omega-\Sigma\alpha_iy_ix_i=0
\]
所以有：
\[
\omega^*=\Sigma\alpha_iy_ix_i
\]
将其代入到拉格朗日函数中：
\[
L(\omega^*,b,\alpha)=1/2(\Sigma\alpha_iy_ix_i^T)(\Sigma\alpha_iy_ix_i)+\Sigma\alpha_i-\Sigma\alpha_iy_i(\Sigma\alpha_iy_ix_i^T)x_i-\Sigma\alpha_iy_ib\\
=1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i-\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\Sigma\alpha_iy_ib
\\
=-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i-\Sigma\alpha_iy_ib
\]

对于 b 求最小值

令
\[
\frac{\partial}{\partial b}L(\omega,b,\alpha)\\
=-\Sigma a_iy_i=0
\]
带入到上一步中，消掉最后一项，得到：
\[
L(\omega^*,b,\alpha)=-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i
\]

得到对偶问题

整理得到以下最终的最优化问题：

\[
\max_\alpha-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i\\
\alpha_i\ge0\ (i=1..m)\\
\Sigma a_iy_i=0\ (i=1..m)
\]

在得到alpha后，w可以根据上面的推导得到，对于b，在w得到后，将正负样本中最接近超平面的两个加起来取平均（根据图示可以很容易看出来）

\[
b^*=-\frac{\min{\omega^*}^Tx_++\max{\omega^*}^Tx_-}{2}
\]

在预测时，我们可以不用 w，而是采用如下的公式（kernel trick的基础）

\[
\omega^Tx+b=\Sigma\alpha_iy_i(x_i^Tx)+b
\]

因为只有支撑矢量的alpha才非零，所以，我们只需要保存支撑矢量（和b），就能进行分类。

4. 核函数

给定一个feature mapping（x->phi(x)），核函数K定义为：

\[
K(x,z)=\phi(x)^T\phi(z)
\]

可以看出，当x和z相近时，核函数取值越大，x和z越相似。我们可以直接找核函数，而不用找到显式的 feature mapping，为了做到这一点，必须规定核函数所需要满足的条件。

Mercer定理

给定函数K，对于任意m个向量，它们构成的核矩阵对称半正定 <=> K是一个核函数

5. 软间隔策略

为了处理线性不可分情况，SVM可以改写为：

\[
\min_{\omega,b}1/2||w||^2 + C\Sigma\xi_i\\
y_i(\omega^tx+b)\ge1-\xi_i\ (i=1..m)\\
\xi_i\ge0 (i=1..m)
\]

化简成对偶问题后，和之前的形式惊人相近，除了alpha的范围

\[
\max_\alpha-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i\\
C\ge\alpha_i\ge0\ (i=1..m)\\
\Sigma a_iy_i=0\ (i=1..m)
\]

此时，b的计算也变了（略），且KKT条件有如下推论：

\[
\alpha_i=0 ⇒ y_i(\omega^Tx+b)\ge1\\
\alpha_i=C ⇒ y_i(\omega^Tx+b)\le1\\
0\le\alpha_i\le C ⇒ y_i(\omega^Tx+b)=1
\]