支持向量机SVM Support Vector Machine

线性可分

找到一个比较好的分割器，即一个超平面（Hyper Plane）。需要最大化之间的 margin。

是支持向量：$y(w^Tx+b)=1$，不是支持向量：$y(w^Tx+b)>1$。

升维转换和核技巧

转换为：

minimize $||\vec w||$，s.t. $y_i \times (\vec w \cdot \vec x_i +b )\ge 1$，其中 $y_i$ 代表点的类型，取值 $-1,1$。

如果是等式，可以使用拉格朗日乘子法，但是这里是不等式，所以引入变量 $p_i$，转化为：

$y_i \times(\vec w \cdot \vec x_i+b) -1 =p_i^2$

$L(w,b,\lambda_i,p_i)=\frac{||\vec w||^2}{2} - \sum_{i=1}^s \lambda_i \times(y_i \times(\vec w \cdot \vec x_i+b) -1 -p_i^2)$

对 $w,b,\lambda_i,p_i$ 求偏导，得到：

$\vec w -\sum_{i=1}^s \lambda_i y_i \vec x_i=0$

$-\sum_{i=1}^s \lambda_i y_i=0$

$y_i \times (\vec w \cdot \vec x_i+b) -1- p_i^2=0$

$2\lambda_ip_i=0$

推出：$\lambda_i=0$ 或 $p_i=0$。

得到

$y_i \times (\vec w \cdot \vec x_i+b)-1 \ge 0,\lambda_i=0$

或

$y_i \times (\vec w \cdot \vec x_i+b)-1=0,\lambda_i\not=0$

KKT 条件 Karush–Kuhn–Tucker conditions

$-\sum_{i=1}^s \lambda_i y_i=0$

$\vec w -\sum_{i=1}^s \lambda_i y_i \vec x_i=0$

$\lambda_i(y_i \times (\vec w \cdot \vec x_i+b)-1)=0$

$\lambda_i \ge 0,y_i \times (\vec w \cdot \vec x_i+b)-1 \ge 0$

有条件极值的 Lagrange 乘数法

有不等式的 Lagrange 函数

1. $\mu_1=0,a_1 \not=0$，等于 $g_1$ 约束不起作用。
2. $\mu_1 \not=0,a_1 =0$，等于约束 $g_1$ 起作用，而且必须要求 $g_1=0$。

这其实就是代表了取极值一定需要某个约束最靠近边界，或舍弃某个约束。

于是转化为：

对于多元多次不等式来说，形式如下：

$-\nabla f(x^*)=\sum_{j \in J} \mu_j \nabla g_j(x^*)$

其中 $J$ 代表起约束作用的集合。

可以看做梯度向量 $-\nabla f(x^*)$ 由 $\nabla g_j(x^*)$ 线性组合而成。而往下走，就需要 $-\nabla f(x^*)>0$，因此组合系数 $\mu_j$ 应该 $\ge0$。

因此，要判断解 $x^*$ 是否最优，只需要代入以上表达式即可。

拉格朗日对偶性

广义拉格朗日函数

$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_jh_j(x)$

其中 $\alpha,\beta$ 是向量。

考虑

$\theta_P(x)=\max_{\alpha,\beta;\alpha_i\geq0}L(x,\alpha,\beta)$

当 $x$ 满足问题约束时，$x$ 满足 KTT 条件，因此，$\alpha_i c_i(x)=0$，$h_j=0$。

$\theta_P(x)=f(x)$

因此问题等价于

$\min_{x}\theta_P(x)=\min_{x}\max_{\alpha,\beta;\alpha_i\geq0}L(x,\alpha,\beta)$

原问题的最优值：

$p^*=\min_{x}\theta_P(x)$

对于对偶问题，我们首先定义：

$\theta_D(\alpha,\beta)=\min_{x}L(x,\alpha,\beta)$

再考虑：

$\max_{\alpha,\beta;\alpha_i\geq0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta;\alpha_i\geq0}\min_{x}L(x,\alpha,\beta)$

对偶问题的最优值：

$d^*=\max_{\alpha,\beta;\alpha_i\geq0}\theta_D(\alpha,\beta)$

则：

$d^*=\max_{\alpha,\beta;\alpha_i\geq0}\min_{x}L(x,\alpha,\beta)\leq\min_{x}\max_{\alpha,\beta;\alpha_i\geq0}L(x,\alpha,\beta)=p^*$

原因是先作用 $\max$，结果一定大。

我们有定理：

假设函数 $f(x)$ 和 $c_i$ 是凸函数，而且不等式约束 $c_i(x)$ 严格可行，则：

$p^*=d^*=L(x^*,\alpha^*,\beta^*)$

称为满足强对偶条件。

SVM 中的拉格朗日对偶性

对于每个 $\lambda_i$，

$q(\lambda_i)=\operatorname{minmize}(L(w,b,\lambda_i))=\operatorname{minmize}(f(w)-\sum_{i=1}^s \lambda_i g_i(w,b))$

对于最优解 $w^*,b^*$，

$q(\lambda_i) \le f(w^*)-\sum_{i=1}^s \lambda_ig_i(w^*,b^*)$

根据 $\lambda_i \ge0,g_i(w^*,b^*)\ge0$，

很多 $q(\lambda_i)$，里面存在一个最优值，因此我们寻找 $\lambda_i^*$

$q(\lambda_i) \le q(\lambda_i^*) \le f(w^*) \le f(w)$

对偶问题：

maximize $q(\lambda_i) =\operatorname{maximize}(\operatorname{minimize}(L(w,b,\lambda_i)))$。

s.t. $\lambda_i \ge0$。

等号成立，强对偶成立。

对对偶问题的化简

首先，由 $\vec w-\sum_{i=1}^s \lambda_i y_i \vec x_i=0$，代入原式，再注意到 $\sum_{i=1}^s \lambda_i y_i=0$，可以消掉常数项 $b$，最终得到：

$\max_{\lambda_i}=\max_{\lambda_i} (\sum_{I=1}^s \lambda_i - \frac{1}{2} \sum_{i=1}^s \sum_{j=1}^s \lambda_i \lambda_j y_i y_j \vec x_i \cdot \vec x_j)$

然后代会求得 $\vec w$，然后由 $\vec w$，就可以求解 $b$。

Kernel Trick

原维度向量 $x$ 转换为新维度向量 $T(x)$。

$\max_{\lambda_i}=\max_{\lambda_i} (\sum_{I=1}^s \lambda_i - \frac{1}{2} \sum_{i=1}^s \sum_{j=1}^s \lambda_i \lambda_j y_i y_j T(\vec x_i) \cdot T(\vec x_j))$

定义 $K(\vec x_i,\vec x_j)=T(\vec x_i) \cdot T(\vec x_j)$。

多项式核函数。

高斯核函数 RBF

$K(\vec x_i,\vec x_j)=e^{-\gamma||\vec x_i-\vec x_j||^2}$

$\gamma$ 越小，相似度越大，越容易被分割。

可以发现 $K(\vec x_i,\vec x_j)$ 展开式中包含

$e^{\vec x_i\cdot \vec x_j}$

因此，对于泰勒展开来说，包含了无穷项 $\vec x_i\cdot\vec x_j$。

软间隔最优化问题

$\min_w \frac{||\vec w||^2}{2}+C\times \sum_{i=1}^s \varepsilon_i$

其中

$\varepsilon_i= \max(0,1-y_i\times(\vec w\cdot \vec x_i+b))$