支持向量机

支持向量：支持平面把两类类别划分开的超平面的向量点
机：一种算法
SVM 是一种二分类模型
线性可分支持向量机：通过硬间隔最大化，学习一个线性分类器
线性支持向量机：通过软间隔最大化，学习一个线性分类器
非线性支持向量机：通过核技巧，学习一个非线性分类器

线性可分支持向量机

几何间隔

函数间隔

见：Python机器学习笔记：SVM（2）——SVM核函数 - 知乎 (zhihu.com)

拉格朗日乘子法

第一种情况：最小值在可行区域内
$g(x^*)<0 \\ \nabla _x f(x^*) =0$
第二种情况：最小值在可行区域外
$g(x^*)=0 \\ -\nabla _x f(x^*) = \alpha \nabla_x g(x^*) \\ \alpha>0$
著名的KKT条件，整合了上面两种情况的条件
$\nabla_xL(x^*, \alpha ^*)=0 \\ \alpha ^*>0\\ \alpha^*g(x^*)=0 \\g(x^*) \le 0$

SVM目标函数求解

目标函数：

$\min _{w, b} \frac 1 2||w||^2 \\ \text { s.t. }\quad 1-y^{(i)}\left(w \cdot x^{(i)}+b\right) \leq 0, \quad \mathrm{i}=1,2, \ldots, \mathrm{m}$

构造拉格朗日函数：

$\alpha)=\frac{1}{2}\|w\|^{2}-\sum_{i=1}^{m} \alpha^{(i)} y^{(i)}\left(w \cdot x^{(i)}+b\right)+\sum_{i=1}^{m} \alpha^{(i)}$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$原始问题:\qquad \qquad \min _{w, b} \max _{\alpha} L(w, b, \alpha) \\ 对偶问题:\qquad \qquad \max _ \alpha \min _{w,b} L(w, b, \alpha)$

线性支持向量机

非线性支持向量机

核技巧

原空间： $x=(x_1,x_2)^T$

新空间： $z=(z_1,z_2)^T$

设原空间到新空间的变换 $z=\phi (x) =(x_1^2+x_2^2)^T$

则把原空间中的椭圆 $w_1x_1^2+w_2 x_2^2+b=0$ 变换为新空间中的直线 $w_1z_1+w_2 z_2+b=0$

高斯核公式：
$z)=\exp \left(-\frac{\|x-z\|^{2}}{2 \sigma^{2}}\right)$

def gauss_kernel(x,z,delta):m,n = np.shape(x)k = np.mat(np.zeros((m,1)))for i in range(m):delta_row=x[i,:] - zk[i] = delta_row * delta_row.Tk = np.exp(k/(-2*delta)**2)return k

数值实验

在平面 $R^2$ 上取矩形 $\times [-5,5]$ ,并在 $I$ 中随机产生100个样本点，作为训练样本点，得到训练样本集 $\Omega =\{(x_i,y_i)|i=1,2,...,100 \} \subset I \times \{-1,+1 \}$ ,其中，如果 $x_i$ 落在圆 $t^2_1+t^2_2=16 ((t_1,t_2)) \in \bf R^2$ 内，则取 $y_i=-1$ , 否则取 $y_i=+1$