生物医学工程 | 机器学习 - 支持向量机 SVM

Linear SVM

set up

给了n个数据点 $(x_1, y_1), ..., (x_n, y_n)$，$y_i$ 是1或者-1，指示 $x_i$ 属于哪个class。每个 $x_i$ 都是为p-dimension real vector。

SVM的目标是找到一个maximum-margin hyperplane，能够将所有点 $x_i$ 都按照 $y_i=1$ 和 $y_i=-1$ 分成两组，且使得hyperplane到两组点的nearest point的距离都最大。

SVM目的：找到一个hyperplane能够maximize margin

hyperplane定义

$\omega^\top x_i+b=0$

margin定义：距离hyperplane最近的那个点的距离

$\gamma(w,b)=\min_{i\in[m]}\frac{|w^\top x_i+b|}{\|w\|_2}$

Hard Margin SVMs

假设：数据是可以被hyperplane $\omega_*^\top x+b_*=0$ 完全分隔的。

目标：找到一个classifier可以获得maximum margin

思路1：从几何的角度来理解（wiki思路）

首先，我们对 $y_i=1$ 和 $y_i=-1$ 这两组 $x_i$ 各自创建一个hyperplanes：

对 $y_i=1$ 的x而言，

hyperplane 1为 $\omega^\top x-b=1$，包含了高于这个hyperplane的所有数据点

对 $y_i=-1$ 的x而言，

hyperplane 2为 $\omega^\top x-b=-1$，包含了低于这个hyperplane的所有数据点。

hyperplane 1和hyperplane 2之间的距离为 $\frac{2}{\|\omega\|}$，所以为了最大化这俩之间的距离，我们需要 $\min \|\omega\|$。

而且这两个hyperplane相互平行， 而我们要找的maximum-margin hyperplane $\omega^\top x-b=0$ 处于这两个hyperplane的正中间。

其次，我们将所有数据点都用公式表示为

$y_i=1$ 的所有数据点都满足 $\omega^\top x_i-b\geq 1$

$y_i=-1$ 的所有数据点都满足 $\omega^\top x_i-b\leq -1$

上面两个式子可以综合一下，写成 $y_i(\omega^\top x_i -b)\geq 1$，for all $1\leq i \leq n$

最后，我们可以得出需要min的式子及其条件

这也可以写成sign函数的形式，$\text{sgn}(\omega^\top x-b)$

思路2：从公式方面推导（上课思路）

将我们的目标写成数学公式就是

化简一下变成

同时为了解决不同scale会导致相同的solution的问题，我们通过增加下面这个条件将solution变得unique

$\min_{i\in [m]}|\omega^\top x_i+b|=1$

将上述条件带入原式

化简得到

可以发现这是一个quadratic optimization problem，通过化简使其变成convex quadratic optimization problem（obj func和constraint都是convex的）

求 $omega$ 和 $b$

然后为了解决上面这个式子，也就是找到w和b可以min objective function，我们可以通过Dual formulation获得 $\omega$，然后通过Support vectors获得b

通过Dual formulation获得 $\omega$

初始化和思路

第一步，写出Lagrangian函数（注意$\alpha_i>0$）

第二步，通过对$\omega$和$b$求偏导，并令其等于0得到

第三步，带回原式并化简得到

并满足

第四步，把dual function写出来就是

第五步，通过解第四步的式子，我们可以得到 $\alpha$ 。将 $\alpha$ 带入下式，得到 $\omega$。

通过Support Vectors获得b

support vector定义：任何 $\alpha_i>0$ 的数据点。也就是恰好落在边界上的点，满足 $1=y_i(w^\top x_i+b)$

我们假设$SV = \{i\in [m]: \alpha_i >0\}$，也就是所有使得$\alpha_i$大于0的i的集合。

$\omega$ 进化为下式

$\omega=\sum_{i\in SV}\alpha_i y_i x_i$

通过KKT条件里面的complementary slackness condition得到下式

从而求出b

人话：我们有一堆可以使 $\alpha>0$ 的i，然后根据上面那个公式，每一个i都可以得到一个b（因为他们对应的 $x_i$ 和 $y_i$ 不一样），我们可以求平均来减少noise，得到更加准确的b

DUAL的结果

Soft Margin SVMs

假设：数据是无法被超平面完全分割的

由于是non-separable的，则 $y_i(\omega^\top x_i+b)\geq 1$ 是infeasible的，则我们可以通过添加slack variable来使其变得feasible

通过添加slack variable $\xi_i$（$\xi_i\geq 0$）来relax constraint我们得到

其中，

$\xi_i=0$ 表示点i被正确分类，且满足最大边界条件 large margin constraint

$0<\xi_i<1$ 表示点i被正确分类，但不满足最大边界条件 large margin constraint

$\xi_i>1$ 表示点i没有被正确分类

为了保证 $\xi_i$ 不是很大，我们在原式增加了penalty

其中C控制penalty的大小，如果C很大，则退化为hard-margin

上面这个式子还是convex quadratic optimization
problem，我们可以誊写dual为

然后按照和hard margin类似的步骤，通过dual来求解

从Min Loss的角度来看

Soft-SVM也可以写成min hinge loss的形式

$l_{hinge}(y,y)=\max(0,1-yy)=\max(0,1-y_i(\omega^\top x_i-b))$

如果 $y_i = sgn(w^Tx_i-b)$ 的话，即 $x_i$ 在正确的class里面，则输出为0，否则输出 $1-y_i(\omega^\top x_i-b)$，即点到margin的距离

则SVM可以写成（其中$\lambda>0$）

$\min_{w,b}\frac{1}{m}\sum_{i=1}^m \max(0,1-y_i(w^\top x_i+b))+\lambda \|w\|^2$

通过引入slack variables后，可以写成

此时我们可以发现，如果令 $C=\frac{1}{2\lambda m}$ ，则这个式子就是soft-SVM

小结

Hard-Margin SVM

最优化函数

classification vector $\omega$

$\omega=\sum_{i=1}^m\alpha_iy_ix_i$

supply vector

$SV=\{i\in [m]: 0<\alpha_i\}$

求解b

$b=y_i-\omega^\top x_i$

prediction function

$\text{sign}(\omega^\top x+b)\\ = \text{sign}(\sum_{i=1}^m \alpha_iy_ix_i^\top x+b)$

Soft-Margin SVM

最优化函数

classification vector $\omega$

$\omega=\sum_{i=1}^m\alpha_iy_ix_i$

supply vector

$SV=\{i\in [m]: 0<\alpha_i<C=\frac{1}{2n\lambda}\}$

求解b

$b=y_i-\omega^\top x_i$

prediction function

$\text{sign}(\omega^\top x+b)\\ = \text{sign}(\sum_{i=1}^m \alpha_iy_ix_i^\top x+b)$

Non-Linear Kernel SVM

概念

目的：解决non-linear separable的数据，且不是添加slack就可以解决的，比如两个圆圈。

思路：为了separate，我们通过feature map $\phi$将data 映射map到更高的维度，即$x\mapsto \phi(x)$

方法：通过将dot product替换为non-linear kernel

例子

通过 $\phi$ 线性化数据，得到新的predictor function

通过feature map$\phi$，将training data从non-linear的input space，投射到linear 的feature space：

$\{(x_1,y_1),...,(x_m,y_m)\} \mapsto \{(\phi(x_1),y_1),...,(\phi(x_m),y_m)\}$

因此我们获得了linear predictor function：

$\omega^\top \phi(x)+b$

其中$\phi(x)$为下式，d表示x的维度

$\phi(x) = [1,x_1,...,x_d,x_1^2,x_1x_2,...,x_d^2]^\top$

用Soft-SVM的方法，求解最优化的function

因为直接求解维度太大了，所以通过Soft-SVM的方法来求解

等价于求解inner product$\phi(x)^\top \phi(x')$

我们可以将其化为

$\phi(x)^\top \phi(x') = 1+x^\top x'+(x^\top x')^2$

构建kernel

为了简化求解过程，我们设kernel $k\in\mathbb{R}$为

$k(x_i,x_j)=<\phi(x_i),\phi(x_j)>=\phi(x_i)\cdot \phi(x_j)$

对于$x_1,x_2,...,x_m$，由k组成的kernel matrix $K\in \mathbb{R}^{m\times m}$为

$K_{ij}=k(x_i,x_j)=<\phi(x_i),\phi(x_j)>$

其中K为symmetric and positive semi-definite matrix，满足下列是三个条件1）$K=K^\top$，2） $x^\top K x\geq 0$，3）所有eigenvalues都是non-negative的

常见的kernel有

Linear

$k(x_i,x_j)=x_i^\top x_j=x_i\cdot x_j$

Polynomial (homogeneous)

$k(x_i,x_j)=（x_i^\top x_j)^r=(x_i\cdot x_j)^r$

Polynomial (inhomogeneous)

$k(x_i,x_j)=（x_i^\top x_j+d)^r=(x_i\cdot x_j+d)^r$

Gaussian/Random Radial Basis Function(RBF): for $\sigma>0$

$k(x,x')=\exp(-\frac{\|x-x'\|^2}{2\sigma^2})$

kernalize，用k表示原式

1. 证明结论一定在span of training points $\omega=\sum_{i=1}^{m}\alpha_ix_i$
2. 将算法和predictor rewrite为 $x_i^\top x_j$ 的形式
3. 用k替换，将 $x_i^\top x_j\Rightarrow \phi(x_i)^\top \phi(x_j)$ 替换为 $k(x_i,x_j)$，将 $x_i$ 替换为 $\phi(x_i)$

！！迭代求解（对比SVM和Kernel）

Soft-SVM

最优化函数

classification vector $\omega$

$\omega=\sum_{i=1}^m\alpha_iy_ix_i$

supply vector

$SV=\{i\in [m]: 0<\alpha_i<\frac{1}{2n\lambda}\}$

求解b

$b=y_i-\omega^\top x_i$

prediction function

$\text{sign}(\omega^\top x+b)\\ = \text{sign}(\sum_{i=1}^m \alpha_iy_ix_i^\top x+b)$

Perceptron Algrithm

**Kernel **

最优化函数

classification vector $\omega$

$\omega=\sum_{i=1}^m\alpha_iy_i\phi(x_i)$

supply vector

$SV=\{i\in [m]: 0<\alpha_i<\frac{1}{2n\lambda}\}$

求解b

$b=y_i-\omega^\top \phi(x_i)\\ =y_i-[\sum_{i=1}^m\alpha_iy_i\phi(x_i)\cdot \phi(x_j)]\\ = y_i-[\sum_{i=1}^m\alpha_iy_i\phi(x_i)^\top \phi(x_j)]\\ = y_i-[\sum_{i=1}^m\alpha_iy_ik(x_i,x_j)]\\$

prediction function

$\text{sign}(\omega^\top \phi(x)+b)\\ = \text{sign}(\sum_{i=1}^m \alpha_iy_i k(x_i,x)+b)$

Perceptron Algrithm

Rigid Regression的kernel表示方法

SVM的Rigid Regression

Rigid Regression原本表达方式

$\min_w \quad \frac{1}{m}\sum_{i=1}^m(y_i-w^\top x_i)^2+\lambda\|w\|^2_2$

用 $w = \sum_{i=1}^m\alpha_ix_i=X^\top \alpha$ 替换 $w$，其中 $XX^\top$ 里的所有元素都是 $x_i^\top x_j$ 的inner product

$\min_w \quad \frac{1}{m}\|Y-XX^\top \alpha\|^2+\lambda\alpha^\top X X^\top \alpha$

Prediction是 $w^\top x=\sum_{i=1}^m\alpha_ix_i^\top x=\alpha^\top X x$

Kernel的Rigid Regression

用K替代 $XX^\top$，其中 $K_{ij}=k(x_i,x_j)$

$\min_\alpha \quad \frac{1}{m}\|Y-K \alpha\|^2+\lambda\alpha^\top K \alpha$

Prediction是 $w^\top \phi(x)=\sum_{i=1}^m\alpha_ik(x_i,x)=\alpha^\top k_x$

其中 $k_x = [k(x,x_1), ..., k(x,x_m)]^\top$

optimal $\alpha = (K+\lambda m I)^{-1}Y$

---

声明：此blog内容为上课笔记，仅为分享使用。部分图片和内容取材于课本、老师课件、网络。如果有侵权，请联系aursus.blog@gmail.com删除。