SVM

作者: 0xFFFFFG | 来源:发表于2019-06-10 15:12 被阅读0次

Profile

FullName: Support Vector Machine

vs Logistic Regression

Logistic Regression

$声明损失函数: L(\theta)=\sum_{i=1}^N(y_i(1-\ln{(\sigma(\theta·X_b^{(i)}})) + (1-y_i)(\ln{(\sigma{(\theta·X_b^{(i)})})}))$
$其中:\hat{y} = \sigma(t) = \frac{1}{1+exp(-t)}$
$求解:argmin_{\theta}L({\theta})$
Logistic回归的决策边界可以使得向量 $(ln(\hat{y})-ln(y))$ 的范数尽可能小,即尽可能保证阳性事件的预测概率尽可能大,阴性事件的预测概率尽可能小

Support Vector Machine

hard-margin:找到一个超平面f(θ),使这个超平面两边的最近的两个点(Support Vector)与这个超平面的距离(margin/2)最远,f(θ)作为分类边界,并且不允许有点落在margin区域内

soft-margin:允许部分向量落在margin区域或者margin对岸,并将这些点距离margin的距离作为损失函数的一部分.

svm的数学表达

hard-margin-SVM

$二维空间中(x_0,y_0)到直线l(Ax+By+C=0)的距离 d = \frac{(Ax_0+By_0+C)}{\sqrt{A^2+B^2}}$
$拓展到N维空间,向量x_b到超平面\theta^T·x=0的距离d_b = \frac{| w_0^Tx+b_0|}{\|w_0\|}$
设 margin = 2d
$\begin{equation} \begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}>=d & \forall y^{(i)} =1\\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|}<=-d & \forall y^{(i)}=-1 \end{cases} \end{equation}$ => $\begin{cases} \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d} >= 1 & \forall y^{(i)} = 1 \\ \frac{w_0^Tx^{(i)}+b_0}{\|w_0\|d}<=-1 & \forall y^{(i)}=-1 \end{cases}$ => $\frac{y^{(i)}(w_0^Tx^{(i)}+b_0)}{\|w_0\|d} >= 1$
$令w = \frac{w_0^T}{\|w_0\|d},b=\frac{b_0}{\|w_0\|d},约束条件可表示为y^{(i)}(w·x^{(i)}+b) >= 1$
$对于任意支撑向量x_s,x_s到l的距离d = \frac{|w·x_s+b|}{\|w\|}=\frac{1}{\|w\|}$
$d=d_{max} 时w= \|w\|_{min},所以svm问题可转化为有条件的最优值问题$
$min\frac{1}{2}\|w\|^2 \\ s.t. \quad\forall(x^{(i)},y^{(i)}) \in trainDataSet \quad y^{(i)}(w·x^{(i)}+b)>=1$

soft-margin-SVM

允许部分点越过支撑向量,越过的部分会作为损失函数的一部分,最优值问题转化为
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^m\eta_i) \\ s.t.\qquad y^{(i)}(w·x^{(i)}+b) >= 1-\eta_i\qquad (\eta_{i} >=0)\\ 特别的,当C\to+∞时,soft-margin-SVM会转化为hard-margin-SVM$
以上模型成为L1正则,L2正则目标表达式为
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i^2)$

Kernel Function(核函数,Kernel Check)

SVM可以视为求解
$min(\frac{1}{2}\|w\|^2+C\sum_{i=1}^{m}\eta_i) \\ s.t. \qquad y^{{i}}(w^Tx^{(i)}+b) \ge 1-\eta_i\quad (\eta_i\ge0)$
的最优化问题,这个问题可以等价于它的对偶问题
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_ix_j \qquad(1)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$
有时分类边界是非线性的,需要对x,y进行某种变形
$def\ function\ K:(x,y)\rightarrow (x'y') ,其中x',y'是x,y进行某种变形后的结果$
目标问题可转化为
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) \qquad(2)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$

多项式核函数

最高系数为2的多项式核函数为例,
$K(x,y)=(x·y+1)^2=(\sum_{i=1}^{n}x_iy_i+1)^2\\=\sum_{i=1}^{n}(x_i^2)(y_i^2)+\sum_{i=2}^{n}\sum_{j=1}^{i-1}(\sqrt2x_ix_j)(\sqrt2y_iy_j)+\sum_{i=1}^{n}(\sqrt2x_i)(\sqrt2y_i)+1=x'·y'\qquad(3)\\ 其中x'=(x_n^2,...,x_1^2,\sqrt2x_nx_{n-1},...,\sqrt2x_n,...,\sqrt2x_1,1),\\y'=(y_n^2,...,y_1^2,\sqrt2y_ny_{n-1},...,\sqrt2y_n,...,\sqrt2y_1,1)$
(3)带入(2)可得
$max\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j(x_iy_i+1)^2 \qquad(4)\\ s.t. \qquad 0\le \alpha_i\le C \ and\ \sum_{i=1}^{m}\alpha_iy_j=0$
将二次核函数推广到一般情况,
$K_{c,d}(x,y)=(x·y+c)^d$
特别地,当c=0,d=1时候,多项式核函数可称为线性核函数
$K_{0,1}(x,y)=x·y$
多项式核函数可以认为是向量点乘推广到更一般的形式
$x·y=K_{0,1}(x,y)=\sum_{i=1}^{m}x_iy_i \\ K_{c,d}(x,y)=(x·y+c)^d$

高斯核函数

$高斯分布(正态分布)\qquad g(x)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{x-\mu}{\sigma})^2}=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{1}{2}(\frac{1}{\sigma})^2({x-\mu})^2}$
又称RBF核(Radial Basis Function Kernel),形态如下
$K_{\gamma}(x,y)=e^{-\gamma\|x-y\|^2}$
其中y是每一个数据点,即每一个数据点都作为landmark
由于和高斯分布的形态一致,所以得名高斯核函数
高斯核函数可以将一个m*n的样本映射为一个m*m的样本,是一种维度拓展的方法
$\gamma$ 越大,高斯分布越窄,越容易过拟合
$\gamma$ 越小,高斯分布越宽,越容易欠拟合
可以认为 $\gamma$ 和模型复杂度正相关

SVM

Profile

vs Logistic Regression

Logistic Regression

Support Vector Machine

svm的数学表达

hard-margin-SVM

soft-margin-SVM

Kernel Function(核函数,Kernel Check)

多项式核函数

高斯核函数

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读