支持向量机

作者: no0758 | 来源:发表于2019-02-27 21:08 被阅读0次

图来源：《机器学习》周志华著
超平面用方程表示为

图中红色样本是被分错的

前面介绍的支持向量机形式是要求所有样本均满足约束 $y_i(w^Tx+b)>=1,i=1,2,...,m$ ，即所有样本都必须划分正确，这称为"硬间隔" (hard margin)，而软间隔则是允许某些样本不满足约束。当然我们是希望这样不满足约束的样本越少越好。因此目标函数定义为
$\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{0/1}( y_i(w^Tx+b)-1)$ ,其中
$l_{0/1}(z)=\begin{cases} 1\quad ,if\quad z<0 \\ 0\quad ,otherwise \end{cases}$

由于 $l_{0/1}$ 非凸、非连续，常用其他损失函数替代，如下图所示:

三种常见的替代损失函数:hinge损失，指数损失，对率损失
采用hinge损失得到：

落入间隔带的样本被认为是预测正确的
目标函数：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{\varepsilon}( f(x_i)-y_i)

l_{\varepsilon}(z)=\begin{cases} 0\quad ,if\quad |z|<=\varepsilon \\|z|-\varepsilon\quad ,otherwise \end{cases}

可允许间隔带两侧的松弛程度有所不同，故引入松弛变量

\xi

和

\overset{\wedge}{\xi}

,得到SVR问题：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

s.t. f(x_i)-y_i<=\varepsilon+\xi_i

y_i- f(x_i)<=\varepsilon+\overset{\wedge}{\xi}_i

\xi_i>=0,\overset{\wedge}{\xi}_i>=0,i=1,2,...,m

拉格朗日乘子法

L(w,b,\xi,\overset{\wedge}{\xi},\alpha,\overset{\wedge}{\alpha},\mu,\overset{\wedge}{\mu})=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

+\sum_{i=1}^{m}\alpha_i( f(x_i)-y_i-\varepsilon-\xi_i)+\sum_{i=1}^{m}\overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)

-\sum_{i=1}^{m}\mu_i\xi_i-\sum_{i=1}^{m}\overset{\wedge}{\mu}_i\overset{\wedge}{\xi}_i

，求极值，令

\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i=0 \Rightarrow w=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i

\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i

\frac{\partial{L}}{\partial{\overset{\wedge}{\xi}_i}}=C-\overset{\wedge}{\alpha}_i-\overset{\wedge}{\mu}_i=0 \Rightarrow C=\overset{\wedge}{\alpha}_i+\overset{\wedge}{\mu}_i

代入L,得到SVR的对偶问题：

\underset{\alpha,\overset{\wedge}{\alpha}}{argmax}\sum_{i=1}^{m}y_i(\overset{\wedge}{\alpha}_i-\alpha_i)-\varepsilon(\overset{\wedge}{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)(\overset{\wedge}{\alpha}_j-\alpha_j)x_i^Tx_j

s.t. \sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

0<=\alpha_i,\overset{\wedge}{\alpha}_i<=C,i=1,2,...,m

KKT条件为：

\begin{cases} \alpha_i(f(x_i)-y_i-\varepsilon-\xi_i)=0 \\ \overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)=0 \\ \alpha_i \overset{\wedge}{\alpha}_i=0,\xi\overset{\wedge}{\xi}_i=0\\(C-\alpha_i)\xi=0,(C-\overset{\wedge}{\alpha}_i)\overset{\wedge}{\xi}_i=0 \end{cases}

当且仅当 $f(x_i)-y_i-\varepsilon-\xi_i=0$ , $\alpha_i$ 为非零；当且仅当 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ , $\overset{\wedge}{\alpha}_i$ 为非零.换言之，样本 $(x_i,y_i)$ 没有落在 $\varepsilon$ -间隔带时， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 为非零。此外， $f(x_i)-y_i-\varepsilon-\xi_i=0$ 和 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ 不能同时成立。因此， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 至少有一个为零。
由 $f(x)=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i^Tx+b$ 可知，只有 $(\overset{\wedge}{\alpha}_i-\alpha_i)$ 非零时， $(x_i,y_i)$ 为SVR的支持向量，且落在 $\varepsilon$ -间隔带之外。落在 $\varepsilon$ -间隔带中的样本，满足 $\alpha_i=\overset{\wedge}{\alpha}_i=0$

支持向量机

5.支持向量机与KNN

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读