太原天气:数据挖掘入门系列教程(八点五)之SVM先容以及从零开始推导公式

admin 2个月前 (04-13) 科技 6 0

目录
  • SVM先容
  • 线性分类
  • 距离
  • 最大距离分类器
  • 拉格朗日乘子法(Lagrange multipliers)
    • 拉格朗日乘子法推导
    • KKT条件(Karush-Kuhn-Tucker Conditions)
    • 拉格朗日乘子法对偶问题
    • Slater 条件
  • 最大距离分类器与拉格朗日乘子法
  • 核技巧
    • 核函数
  • 软距离
    • 软距离支持向量机推导
  • SMO算法
    • SMO变量的选择方式
  • 总结
    • 参考

照样老例子,这一篇博客是对SVM举行先容,下一篇博客就是使用SVM举行详细的使用。

SVM先容

首先先容SVM是什么,SVM(support vector machine)名为支持向量机,又名支持向量网络,是一个异常经典且高效的分类模子,是一种监视式的学习方式。

从名字上面来明白,SVM分为两个部门,"支持向量(support vector)"以及“机(machine)”。“machine”很简单的明白,就是算法的意思,那么“support vector”是什么呢? 这个现在不举行先容,待我逐步的引入。

线性分类

在先容SVM之前,我们得先对线性分类器举行先容。下面是一个二维平面的的分类问题,红色代表类别为+1,蓝色的代表类别是-1。中心的线就代表支解这两类问题的超平面。对于分类问题来说,红色和蓝色的点都是数据集中已知的,而我们的目的就是找到一个最适合的超平面,将数据举行分类。

对于线性二分类模子,给定一组数据\(\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}\), 其中\(\boldsymbol{x}_{i} \in \mathbb{R}^{d}, y \in\{-1,1\}\),二分类义务的目的是希望从数据中学得一个假设函数\(h: \mathbb{R} \rightarrow\{-1,1\}\),使得\(h(x_i) = y_i\)

\[\begin{equation} h\left(\boldsymbol{x}_{i}\right)=\left\{\begin{array}{ll} 1 & 若 y_{i}=1 \\ -1 & 若 y_{i}=-1\\\tag{1} \end{array}\right. \end{equation} \]

那么问题来了,我们若何去寻找一个能够将\(y_i = \pm1\)划离开的超平面?首先我们可以设超平面的函数是:

\[\begin{equation}f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\end{equation} \tag{2} \]

这里有一个值得注意的点,下面的这个公式会在后面的推导中经常用到。

\[y_i^2 = 1 \tag{3} \]

只管有许多的问题都是线性不可分的,然则呢,现在我们只讨论线性可分问题,到后面我们再讨论若何将非线性问题转成线性问题。因此,暂时我们不需要去纠结若是是非线性问题怎么办。

我们可以直观的从图中举行感受,这样的超平面是有多个的,那么若何寻找一个最合适的超平面呢(也就是寻找最合适的\(w^{\mathrm{T}}\)\(b\))?接下来引出距离的观点来寻找最合适的超平面。

距离

如下图所示,超平面\(\begin{equation}f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\end{equation}\),则\(x\)\(x_0\)到超平面的投影,\(x_0\)对应的类别是\(y_0\)\(w\)为超平面的法向量,\(\gamma\)\(x_0\)到超平面的距离(带正负号)。

因此

\[\begin{aligned} & \gamma = \frac{f(x_0)}{||w||} \\ & 因此距离(不带正负号)的为: \\ & \tilde{\gamma} = y_0\gamma \end{aligned} \]

这样我们就推出了距离的表达式\(\tilde{\gamma} = y_0\gamma\)。对于给定的数据集,我们固然是希望数据集中的数据离超平面越远越好,由于这样所能够容忍的误差也就越大。那么这个远若何来确定呢?接下来让我们讨论什么是最大距离分类器。

最大距离分类器

若是我们给定如下的数据集,那么对于下面的数据集,哪一些最不可能分类乐成呢?毋庸置疑的,就是最靠近\(\begin{equation}f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\end{equation}\)超平面的数据点(好比下图中被红色和黄色圈出来的点)。而被圈出来的点也就是被称之为“支持向量”。由于在模子中我们思量他们就可以了。

首先我们假设支持向量漫衍在\(\omega^Tx+b=\pm 1\)超平面上,这里取值为1只是为了利便,该值并不影响后面的优化效果。很显然,支持向量到超平面\(\omega^Tx+b=\pm 1\)的距离为\(\frac{1}{\|\omega\|}\)。两侧的距离加起来就是\(\frac{2}{\|\omega\|}\)。在前面我们说过,我们希望距离越大越好,也就是说\(\frac{2}{\|\omega\|}\)越大越好,同时对于数据集中数据的漫衍知足\(y(\omega^T+b)x \geqslant 1\)。因此,我们获得了如下的优化问题:

\[\left \{ \begin{matrix} \begin{align*} & \max \quad \frac{2}{\Vert \omega \Vert} \\ & s.t. \quad y_i(\omega^T x_i + b) \geqslant 1 ,\quad i=1,2,...,m \end{align*} \end{matrix} \right. \tag{4} \]

为了利便后续的推导,该优化问题等价于:

\[\left \{ \begin{matrix} \begin{align*} & \min \quad \frac{1}{2}\| \omega \|^2 \\ & s.t. \quad y_i(\omega^T x_i + b) \geqslant 1 ,\quad i=1,2,...,m \end{align*} \end{matrix} \right. \tag{5} \]

拉格朗日乘子法(Lagrange multipliers)

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方式。通过引拉格朗日乘子,可将有 \(d\)个变量与\(k\)个约束条件的最优化问题转化为具有\(d+k\)个变量的无约束优化问题求解。下面让我们来举行推导。

拉格朗日乘子法推导

如下图所示\(z=f(x,y)\)\(g(x,y)=0\),若是我们需要求\(z\)\(g(x,y)\)条件下的极值。从几何角度来说,我们可以画出\(z = C_i\)的等高线,等高线与\(g(x,y)\)相切的点\((x_0,y_0)\)即为极值点。如下图所示:

进入申博Sunbet官网  第1张由于在点\((x_0,y_0)\)取得极值,那么,\(\nabla{f(x_0, y_0)} // \nabla{g(x_0, y_0)}\),也就是说此时梯度平行。也就是说\(({f_x}'(x_0,y_0),{f_y}'(x_0,y_0)) // ({g_x}'(x_0,y_0),{g_y}'(x_0,y_0))\)(这个是可以证实的,然则在这里就不证实了)因此有:

\[\frac{{f_x}'(x_0,y_0)}{{g_x}'(x_0,y_0)}=\frac{{f_y}'(x_0,y_0)}{{g_y}'(x_0,y_0)}=-\lambda_0 (\lambda_0可以为0) \]

即:

\[\left\{\begin{matrix} {f_x}'(x_0,y_0)+\lambda_0{g_x}'(x_0,y_0)=0\\ \\ {f_y}'(x_0,y_0)+\lambda_0{g_y}'(x_0,y_0)=0\\ \\ g(x,y)=0 \end{matrix}\right. \tag{6} \]

若是此时我们有一个辅助函数\(L(x,y, \lambda)=f(x,y)+\lambda g(x,y)\),对其求偏导然后求极值点可得:

\[\left\{\begin{matrix} \frac{\partial L(x,y, \lambda)}{\partial x}={f_x}'(x,y)+\lambda{g_x}'(x,y)=0\\ \\ \frac{\partial L(x,y, \lambda)}{\partial y}={f_y}'(x,y)+\lambda{g_y}'(x,y)=0\\ \\ \frac{\partial L(x,y, \lambda)}{\partial \lambda}=g(x,y)=0 \end{matrix}\right. \tag{7} \]

显而易见公式\((6)\)和公式\((7)\)相等。因此我们对\(z = f(x,y)\)在条件\(f(x,y) = 0\)的条件下求极值\((x_0,y_0)\)的问题酿成了求拉格朗日函数\(L(x,y, \lambda)=f(x,y)+\lambda g(x,y)\)偏导数为0的解。

KKT条件(Karush-Kuhn-Tucker Conditions)

上面我们讨论的是在等式约束条件下求函数极值的问题(也就是\(g(x,y)=0\))but,若是若是是不等式条件下,我们应该若何来使用拉格朗日函数来求解呢?下面引出KKT条件。

什么是KKT条件呢?它是在知足一些有规则的条件下,一个非线性计划问题能有最优化解法的一个必要条件。也就是说优化问题在最优值处必须知足KKT条件

例如我们有以下优化问题:

\[\begin{equation}\begin{aligned} \min _{x} & f(x) \\ \text { s.t. } & h_{i}(x)=0 \quad(i=1, \ldots, m) \\ & g_{j}(x) \leqslant 0 \quad(j=1, \ldots, n) \end{aligned}\end{equation} \]

其拉格朗日函数为:

\[\begin{equation}L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} g_{j}(\boldsymbol{x})\end{equation} \tag{8} \]

则其KKT条件为:

\[\begin{equation}\left\{\begin{array}{l} g_{j}(\boldsymbol{x}) \leqslant 0 \\ \mu_{j} \geqslant 0 \\ \mu_{j} g_{j}(\boldsymbol{x})=0 \\ h(x) =0 \end{array}\right.\end{equation} \]

接下来让我们来解释一下为什么是这样的。(纷歧定是数学证实)。

下面我们只讨论\(f(x)\)在不等式\(g_i(x)<0\)条件下取\(min\)情形。这里可能有人会说,若是我要求\(max\)怎么办?很简单那,将\(f(x)\)取反即可,就酿成了求\(min\)的情形。同样对于\(g_i(x) > 0\)的情形,我们取反就酿成了\(g^{'}(x) = -g_i(x) \lt 0\)

对于上述讨论,有两种情形如下图(图中\(x^*\)代表极小值点):

  • 情形一:极小值点\(x^*\)\(g_i(x)<0\)的区域内
  • 情形二:极小值点\(x^*\)\(g_i(x)=0\)

进入申博Sunbet官网  第2张

首先我们先讨论情形二,对于情形二很好明白,此时的“不等式约束”酿成了“等式约束”。那么其在极值点知足以下条件:

\[h(x)=0\\ g(x)=0\\ \mu \geq 0 \tag{9} \]

\(h(x)=0,g(x)=0\)我们很好明白,然则为什么我们对\(\mu\)还要举行限制呢?然后为什么限制还为\(\mu \geq 0\)呢?首先我们来思量一下\(f(x)\)\(g(x)\)\(x^*\)点的梯度偏向(首先\(f(x)\)\(g(x)\)\(x^*\)点的梯度偏向肯定是平行的【梯度的偏向代表函数值增添最快的偏向】)。

  • 对于\(f(x)\)来说,等值线巨细由中心到周围逐渐增大,因此它的梯度偏向指向可行域。为图中红色的箭头号。
  • 对于\(g(x)\)来说,梯度偏向肯定是指向大于0的一侧,那么就是要背离可行域。为图中黄色的箭头号。

进入申博Sunbet官网  第3张

在前面拉格朗日乘子法中我们有以下推导:

\[\frac{{f_x}'(x_0,y_0)}{{g_x}'(x_0,y_0)}=\frac{{f_y}'(x_0,y_0)}{{g_y}'(x_0,y_0)}=-\lambda_0 (\lambda_0可以为0) \]

又由于\(g(x)\)\(f(x)\)梯度偏向相反,因此\(\lambda_0 \geq0\)。 因此对于\(公式9\)\(\mu \geq 0\)

接下来让我们来讨论情形一。情形一是极小值$x^* \(在\)g(x)$的可行域中,因此,我们可以将其看成没有不等式约束条件。那么其在极值点知足以下条件:

\[h(x)=0\\ g(x) \leq 0\\ \mu =0 \]

对比两种情形:

  • 情形一:\(\mu = 0,g(x) \leq 0\)
  • 情形二:\(\mu \geq 0,g(x)=0\)

综合情形一和情形二,可获得KKT条件为:

\[\begin{equation}\left\{\begin{array}{l} g_{j}(\boldsymbol{x}) \leqslant 0 \quad(主问题可行)\\ \mu_{j} \geqslant 0 \quad(对偶问题可行)\\ \mu_{j} g_{j}(\boldsymbol{x})=0 \quad(互补松懈)\\ h(x) =0 \end{array}\right.\end{equation} \]

拉格朗日乘子法对偶问题

对于如下优化问题:

\[\begin{equation}\begin{aligned} \min _{x} & f(x) \\ \text { s.t. } & h_{i}(x)=0 \quad(i=1, \ldots, m) \\ & g_{j}(x) \leqslant 0 \quad(j=1, \ldots, n) \end{aligned}\end{equation} \tag{10} \]

其拉格朗日函数为:

\[\begin{equation} L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} h_{i}(\boldsymbol{x})+\sum_{j=1}^{n} \mu_{j} g_{j}(\boldsymbol{x}) \\ s.t. \mu_j \ge0 \end{equation} \]

对于上述的优化问题(\(公式10\))我们可以等价于(下面的称之为主问题):

\[\begin{equation}\begin{aligned} \min _{x} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} & \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \\ \text { s.t. } & \mu_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \]

证实如下:

\[\begin{equation}\begin{aligned} & \min _{x} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}}\mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \\ =& \min _{\boldsymbol{x}}\left(f(\boldsymbol{x})+\max _{\boldsymbol{\lambda}, \boldsymbol{\mu}}\left(\sum_{i=1}^{m} \mu_{i} g_{i}(\boldsymbol{u})+\sum_{j=1}^{n} \lambda_{j} h_{j}(\boldsymbol{u})\right)\right) \\ =& \min _{\boldsymbol{x}}\left(f(\boldsymbol{x})+\left\{\begin{array}{l} 0 \text{ 若x知足约束}\\ \infty \text{否则} \end{array}\right)\right.\\ =& \min _{\boldsymbol{u}} f(\boldsymbol{u}) \end{aligned}\end{equation} \]

其中, 当\(g_i(x)\)不知足约束时, 即\(g_i(x)\gt0\), 我们可以令\(\mu=\infty\), 使得\(\mu_ig_i(x) = \infty\); 当\(h_j(x)\)不知足约束时, 即 \(h_j(x)\ne0\), 我们可以取\(\lambda_j = \infty\), 使得\(\lambda_jh_j(x) = \infty\)。当\(x\)知足约束时, 由于 \(\mu_i\ge0\)\(g_i(x)\le0\), 则 \(\mu_ig_j(x)\le0\),因此我们可以取最大值0。 实际上也就是说若是\(公式10\)存在最优解,则最优解必须知足KKT条件。

对于\(公式10\)其对偶问题为:

\[\begin{equation}\begin{aligned} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \min _{x}& \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \\ \text { s.t. } & \mu_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \]

对偶问题是主问题的下界(他们两个具有弱对偶性):

\[p^* = \min _{x} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \ge \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \min _{x} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = g^* \]

你可以影象成“廋死的骆驼比马大”,还看到一个影象方式为“宁为凤尾不为鸡头”。hhh

证实如下:

\[\max _{x} \min _{y} f(x, y) \leq \min _{y} \max _{x} f(x, y)\\ \text{let } g(x)=\min _{y} f(x, y)\\ \text{then }g(x) \leq f(x, y), \forall y\\ \therefore \max _{x} g(x) \leq \max _{x} f(x, y), \forall y\\ \therefore \max _{x} g(x) \leq \min _{y} \max _{x} f(x, y) \]

Slater 条件

前面我们讨论了弱对偶性,这里我们将举行讨论Slater条件,然则为什么我们要讨论Slater条件呢?缘故原由很简单,我们想让上面的弱对偶问题转成强对偶问题。

Slater定理是说,当Slater条件建立且原问题是凸优化问题时,则强对偶性建立。这里有几个名词值得注意:

  • 凸优化问题

    若是一个优化问题知足如下花样,我们就称该问题为一个凸优化问题:

    \[\begin{array}{} \text{min}&f(x)\\ \text{s.t}&g_i(x)\le0,&i=1,...,m \\ \text{ }&h_i(x)=0,&i=1,...,p \end{array} \]

    其中\(f(x)\)是凸函数,不等式约束\(g(x)\)也是凸函数,等式约束\(h(x)\)是仿射函数。

    1. 凸函数是具有如下特征的一个界说在某个向量空间的凸子集\(C\)(区间)上的实值函数\(f\):对其界说域上随便两点\(x_1,x_2\)总有\(f\left(\frac{x_{1}+x_{2}}{2}\right) \leq \frac{f\left(x_{1}\right)+f\left(x_{2}\right)}{2}\)

      进入申博Sunbet官网  第4张

    2. 仿射函数

      仿射函数,即最高次数为1的多项式函数。

  • 强对偶性

    弱对偶性是\(p* = \min _{x} \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) \ge \max _{\boldsymbol{\lambda}, \boldsymbol{\mu}} \min _{x} \mathcal{L}(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = g*\),也就是\(p^* \ge g^*\),则强对偶性是\(p^* = g^*\)

说了这么多,那什么是Slater条件呢?

  1. 原问题是凸优化问题
  2. 存在\(x\)使得\(g(x) \le0\)严酷建立。(换句话说,就是存在\(x\)使得\(g(x) \lt0\)建立)

值得注意的是线性支持向量机知足Slater条件(由于\(\frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}\)\(1-y_{i}(w^Tx_i+b)\)均为凸函数),也就是它知足强对偶性。

最大距离分类器与拉格朗日乘子法

前面说了这么多,实际上也就是为这个地方做铺垫。我们可以将最大距离分类问题转化成在KKT条件下的拉格朗日函数的极值问题,然后又由于其知足Slater条件,我们可以转化成强对偶问题。

在最大距离分类中,我们获得如下结论:

\[\left \{ \begin{matrix} \begin{align*} & \min \quad \frac{1}{2}\| \omega \|^2 \\ & s.t. \quad y_i(\omega^T x_i + b) \geqslant 1 ,\quad i=1,2,...,m \end{align*} \end{matrix} \right. \tag{11} \]

其拉格朗日函数为:

\[\begin{equation} \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\alpha}):=\frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)\right) \\ s.t. \alpha_i \ge0,\quad i=1,2,...,m \end{equation} \]

其对偶问题(知足强对偶性)为:

\[\begin{equation}\begin{aligned} &\max _{\alpha} \min _{\boldsymbol{w}, b}\left(\frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)\right)\right)\\ &\text { s.t. } \quad \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation}\tag{12} \]

然后我们来求:

\[\begin{equation}\begin{aligned} &\min _{\boldsymbol{w}, b}\left( \frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{x}_{i}+b\right)\right)\right)\\ &\text { s.t. } \quad \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \]

上式对于\((\omega,b)\)属于无约束优化问题,令偏导为零可得:

\[\begin{equation} \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}}=\mathbf{0} \Rightarrow \boldsymbol{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ \frac{\partial \mathcal{L}}{\partial b}=0 \Rightarrow \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \end{equation} \tag{13} \]

代入\(公式(12)\)消去\((\omega,b)\)可得:

\[\begin{equation}\begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\top} \boldsymbol{x}_{j}-\sum_{i=1}^{m} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \tag{14} \]

因此问题酿成了寻找合适的\(\alpha\)使得\(公式(12)\)建立。

又由于\(公式(11)\)在极值点肯定知足KKT条件。也就是说\(\alpha_i(1-y_{i}({w}^{\top} {x}_{i}+b))=0\),当\(\alpha_i \gt 0\)时必有\(1-y_{i}({w}^{\top} {x}_{i}+b) =0\)。因此对于\(\alpha_i \gt0\)对应的样本是支持向量,对于非支持向量,则\(\alpha_i =0\)

进入申博Sunbet官网  第5张

对于\(公式13\)有:

\[\begin{equation}\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ &=\sum_{i: \alpha_{i}=0}^{m} 0 \cdot y_{i} \boldsymbol{x}_{i}+\sum_{i: \alpha_{i}>0}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ &=\sum_{i \in S V} \alpha_{i} y_{i} \boldsymbol{x}_{i}\quad(SV 代表所有支持向量的聚集) \end{aligned}\end{equation} \]

然后我们可以求\(b\)了,对于支持向量有\(y_k =\omega^{\top}x+b\),因此:

\[\begin{equation}\begin{aligned} b&=y_k-\boldsymbol{w}^{\top} \boldsymbol{x} \\ &=y_{k}-(\sum_{i \in S V} \alpha_{i} y_{i} \boldsymbol{x}_{i})^{\top}x_k \\ &=y_k-\sum_{i \in S V} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\top}x_k \end{aligned} \end{equation} \]

通过上面的推导,我们能够知道支持向量机的\((\omega,b)\)仅由支持向量决议。实践中, 为了获得对 $b \(更稳健的估量, 通常使用对所有支持向量求解获得\)b$的平均值。

综上,我们想盘算出合适的\(\omega\)\(b\),就必须盘算出\(\alpha_i\),然后我们就可以获得支持向量,在然后我们我们通过支持向量和\(\alpha_i\)就可以盘算出\(\omega\)\(b\)

至于怎么求\(\alpha_i\),我们使用可以使用后面先容的SMO算法求解,首先我们来先容一下核方式。

核技巧

在前面的讨论中,我们对样本的思量都是线性可分的。然则实际上,大部门的情形下,数据都是非线性可分的。好比说异或问题。在前面的章节神经网络中,我们是通过使用增添一层隐层来解决这个问题,那么对于SVM我们应该怎么解决呢?SVM中使用核技巧(kernel trick)来解决非线性问题。

进入申博Sunbet官网  第6张

既然在原始的特征空间\(\mathbb{R}^{d}\)不是线性可分的,支持向量机希望通过一个映射\(\phi: \mathbb{R}^{d} \rightarrow \mathbb{R}^{\tilde{d}}\), 使得数据在新的空间\(\mathbb{R}^{\tilde{d}}\)是线性可分的。可以证实(然则我证实不出),当\(d\)有限时, 一定存在\(\tilde{d}\), 使得样本在空间$ \mathbb{R}^{\tilde{d}}$中线性可分。

核函数

\(\phi(x)\)\(x\)映射后的特征向量,因此划分的超平面可以示意为\(f(x)=\phi(x)+b\)。同时\(公式(11)\)可以改为:

\[\begin{equation}\begin{array}{l} \min _{w,b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array}\end{equation} \]

然后\(公式14\)可以写成如下的形式:

\[\begin{equation}\begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi(\boldsymbol{x}_{i}^{\top}) \phi(\boldsymbol{x}_{j})-\sum_{i=1}^{m} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \tag{15} \]

求解\(公式15\)面临一个很大的问题,那就是\(\phi(\boldsymbol{x}_{i}^{\top})\)\(\phi(\boldsymbol{x}_{j})\)很难盘算(一样平常来说它们都是高维的甚至无限维),首先需要盘算特征在\(\mathbb{R}^{\tilde{d}}\)的映射,然后又要盘算在他的内积,复杂度为$$\mathcal{O}(\tilde{d})$$。因此我们通过使用核技巧,将这两步并将复杂度降低到\(\mathbb{R}^{d}\)。即核技巧希望组织一个核函数\(\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)\),使得:

\[\begin{equation}\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{j}\right)\end{equation} \]

实际上核函数不仅仅只用于SVM,对于所有涉及到向量内积的运算,我们都可以使用核函数来解决。

因此\(公式15\)可以改写成:

\[\begin{equation}\begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)-\sum_{i=1}^{m} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \tag{15} \]

对于核函数来说,我们可以自己造,然则通常我们会从一些常见的核函数中举行选择:凭据差别问题选择差别的参数。下图是是一些常见的核函数。

进入申博Sunbet官网  第7张

软距离

前面我们讨论的情形都是超平面都是能够完善的将数据举行离开(即使是非线性数据,我们使用核函数举行骚操作然后举行支解),这种所有样本都知足约束的情形称之为硬距离(hard margin),但实际上数据是有噪音的,若是使用核函数举行骚操作,然后在找到一个线性可分超平面,可能就会造成模子过拟合,同样也可能我们找不到合适的核函数。因此,我们将尺度放宽,允许一定的“错误”,称之为软距离(soft margin):

进入申博Sunbet官网  第8张

我们希望在优化距离的同时,允许错误样本的泛起,然则我们同样希望泛起错误的样本越少越好。因此优化目的\(公式(5)\)可写成:

\[\left \{ \begin{matrix} \begin{align*} & min _{\boldsymbol{w}, b} \left(\frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)\right)\\ & s.t. \quad y_i(\omega^T x_i + b) \geqslant 1 ,\quad i=1,2,...,m \end{align*} \end{matrix} \right. \tag{16} \]

其中\(C \gt 0\)是一个常数,\(\ell_{0 / 1}\)是“0/1损失函数”。

\[\begin{equation}\ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right.\end{equation} \]

可以很简单的知道,\(C\)取无限大时,\(公式(16)\)迫使所有样本均知足约束。当\(C\)取有限值时,允许一些样本不知足约束。but,照样有些问题,\(\ell_{0 / 1}\)是非凸,非延续的一个函数,会使得上式\((16)\)变得欠好求解,因此人们通常使用其他的函数来替换\(\ell_{0 / 1}\),称之为“替换损失(surrogate loss)”。下面是几种常用的替换损失函数:

\[\begin{equation}\begin{aligned} &\text {hinge 损失}:\ell_{\text {hinge}}(z)=\max (0,1-z) \\ &\text { 指数损失(exponential loss): } \ell_{\exp }(z)=\exp (-z)\\ &\text { 对率损失(logistic loss): } \ell_{\log }(z)=\log (1+\exp (-z)) \end{aligned}\end{equation} \]

对应的图如下:

进入申博Sunbet官网  第9张

下面将以\(hinge函数\)为例子先容软距离支持向量机的推导。

软距离支持向量机推导

\(\text {hinge函数}:\ell_{\text {hinge}}(z)=\max (0,1-z)\)等价于:

\[\begin{equation}\xi_{i}=\left\{\begin{array}{ll}0 & \text { if } y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)+b\right) \geq 1 \\1-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)+b\right) & \text { otherwise }\end{array}\right.\end{equation} \]

\(\xi_{i}\)我们称之为松懈变量(slack variable),样本违反约束越远,则松懈变量值越大。因此优化目的式\((5)\)可以写成:

\[\begin{equation}\begin{aligned}\min _{\boldsymbol{w}, b, \boldsymbol{\xi}} &( \frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}+C \sum_{i=1}^{m} \xi_{i} )\\\text { s.t. } & y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)+b\right) \geq 1-\xi_{i}, \quad i=1,2, \ldots, m \\& \xi_{i} \geq 0, \quad i=1,2, \ldots, m\end{aligned}\end{equation} \tag{17} \]

同样在这里\(C\)越大,代表我们希望越多的样本知足约束。软距离的拉格朗日函数为:

\[\begin{equation}\begin{aligned} \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta}):=& \frac{1}{2} \boldsymbol{w}^{\top} \boldsymbol{w}+C \sum_{i=1}^{m} \xi_{i} \\ &+\sum_{i=1}^{m} \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)+b\right)\right) \\ &+\sum_{i=1}^{m} \beta_{i}\left(-\xi_{i}\right) \end{aligned}\end{equation} \tag{18} \]

其KKT条件为:

\[\begin{equation}\left\{\begin{array}{l} 1 - \xi_{i}-y_{i}\left(\boldsymbol{w}^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)+b\right) \leq 0,-\xi_{i} \leq 0 \quad(主问题可行)\\ \alpha_{i} \geq 0, \beta_{i} \geq 0 \quad(对偶问题可行)\\ \alpha_{i}\left(1-\xi_{i}-y_{i}\left(\boldsymbol{w}^{\top} \phi\left(\boldsymbol{x}_{i}\right)+b\right)\right)=0, \beta_{i} \xi_{i}=0 \quad(互补松懈)\\ \end{array}\right.\end{equation} \]

其对偶问题为:

\[\begin{equation}\begin{aligned} \max _{\boldsymbol{\alpha}, \boldsymbol{\beta}} \min _{\boldsymbol{w}, b, \boldsymbol{\xi}} & \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \\ \text { s.t. } & \alpha_{i} \geq 0, \quad i=1,2, \ldots, m \\ & \beta_{i} \geq 0, \quad i=1,2, \ldots, m \end{aligned}\end{equation} \]

\(\min _{\boldsymbol{w}, b, \boldsymbol{\xi}} \mathcal{L}(\boldsymbol{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\beta})\)的优化属于无约束的优化问题,我们通过将偏导置零的方式获得\((\boldsymbol{w}, b, \boldsymbol{\xi})\)的最优值:

\[\begin{equation}\begin{aligned} \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}}=\mathbf{0} & \Rightarrow \boldsymbol{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right) \\ \frac{\partial \mathcal{L}}{\partial b} &=0 \Rightarrow \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ \frac{\partial \mathcal{L}}{\partial \boldsymbol{\xi}} &=\mathbf{0} \Rightarrow \alpha_{i}+\beta_{i}=C \end{aligned}\end{equation}\tag{19} \]

由于\(\beta_{i}=C -\alpha_{i} \ge0\),因此我们约束\(0 \le \alpha_i \le C\),将\(\beta_{i}=C -\alpha_{i},{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)\),代入式\((18)\)可得:

\[\begin{equation}\begin{array}{ll} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\top} \boldsymbol{\phi}\left(\boldsymbol{x}_{j}\right)-\sum_{i=1}^{m} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0,\\ & 0 \le \alpha_i \le C \end{array}\end{equation} \tag{20} \]

若是我们将式\((17)\)看成如下一样平常形式:

\[\begin{equation}\min _{f} (\Omega(f)+C \sum_{i=1}^{m} \ell\left(f\left(\boldsymbol{x}_{i}\right), y_{i}\right))\end{equation} \]

对于\(\Omega(f)\)我们称之为“结构风险(structural risk)”,第二项\(\sum_{i=1}^{m} \ell\left(f\left(\boldsymbol{x}_{i}\right), y_{i}\right)\)称之为“履历分享(empirical risk)“,而\(C\)的作用就是对两者举行折中。

SMO算法

前面说了这么多,终于终于,我们要最先说SMO(Sequential minimal optimization,序列最小化)算法了。首先说一下这个算法的目的,这个算法就是用来求\(\alpha_i\)的。SMO算法是一种启发式算法,基本思路是若是所有变量的解都知足最优化问题的KKT条件,则该最优化问题的解就获得了。

对于式\((19)\)若是我们将\(\phi({x}_{i})^{\top} {\phi}(\boldsymbol{x}_{j})\)使用核函数来示意则有:

\[\begin{equation}\begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} K\left(x_{i}, x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \cdots, N \end{aligned}\end{equation} \tag{21} \]

如果我们选择\(\alpha_1,\alpha_2\)作为变量(至于为什么不是只选择一个变量是由于存在$\sum_{i=1}^{N} \alpha_{i} y_{i}=0 \(这个约束条件),牢固其他变量\)\alpha_{i}(i=3,4, \cdots, N)\(,则式\)(20)$问题可以酿成:

\[\begin{equation}\begin{array}{rl} \min _{\alpha_{1}, \alpha_{2}} & W\left(\alpha_{1}, \alpha_{2}\right)=\frac{1}{2} K_{11} \alpha_{1}^{2}+\frac{1}{2} K_{22} \alpha_{2}^{2}+y_{1} y_{2} K_{12} \alpha_{1} \alpha_{2}- \\ & \left(\alpha_{1}+\alpha_{2}\right)+y_{1} \alpha_{1} \sum_{i=3}^{N} y_{i} \alpha_{i} K_{i 1}+y_{2} \alpha_{2} \sum_{i=3}^{N} y_{i} \alpha_{i} K_{i 2} \\ \text { s.t. } & \alpha_{1} y_{1}+\alpha_{2} y_{2}=-\sum_{i=3}^{N} y_{i} \alpha_{i}=\varsigma \\ & 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2 \end{array}\end{equation} \tag{22} \]

在式\((21)\)中省略了\(\sum_{i=3}^N\alpha_i\)这个式子,是由于该式为常数项。

由于\(\alpha_{1} y_{1}+\alpha_{2} y_{2} = 常数,y_1 = \pm1,y_2=\pm1\),因此有:

\[\begin{equation}\left\{\begin{array}{l} \alpha_1 - \alpha_2 = k \quad(y_1 \ne y_2)\\ \alpha_1 + \alpha_2 = k \quad(y_1 = y_2)\\ \end{array} \right. \end{equation} \quad \text { s.t. }0 \leqslant \alpha_{1} \leqslant C,0 \leqslant \alpha_{2} \leqslant C\\ \tag{23} \]

我们可以将式\((22)\)用图示意出来:

进入申博Sunbet官网  第10张

由于\(\alpha_1\)\(\alpha_2\)存在线性关系,这样两个变量的最优化问题成为了实质上单变量的最优化问题,因此,我们可以看成其为变量\(\alpha_2\)的最优化问题。

\(式(22)\)的初始可行解为\(\alpha_{1}^{\text {old }}, \alpha_{2}^{\text {old }}\),最优解为\(\alpha_{1}^{\text {new }}, \alpha_{2}^{\text {new}}\)。对于\(\alpha_i^{new}\)来说,其取值局限必须知足:

\[L \leqslant \alpha_{i}^{\text {new }} \leqslant H \]

  • 情形1:\(L=\max \left(0, \alpha_{2}^{\text {old }}-\alpha_{1}^{\text {old }}\right), \quad H=\min \left(C, C+\alpha_{2}^{\text {old }}-\alpha_{1}^{\text {old }}\right)\)
  • 情形2:\(L=\max \left(0, \alpha_{2}^{\text {old }}+\alpha_{1}^{\text {old }}-C\right), \quad H=\min \left(C, \alpha_{2}^{\text {old }}+\alpha_{1}^{\text {old }}\right)\)

设我们盘算出来的\(\alpha_2\)\(\alpha_2^{new,unc}\),则有:

\[\alpha_2^{new}= \begin{cases} H& { \alpha_2^{new,unc} > H}\\ \alpha_2^{new,unc}& {L \leq \alpha_2^{new,unc} \leq H}\\ L& {\alpha_2^{new,unc} < L} \end{cases} \]

那么问题就回到了若是我们有\(\alpha_2^{old}\)我们若何获得\(\alpha_2^{new,unc}\)呢?

首先我们设一个超平面函数\(g(x)\)如下:

\[设:g(x) = w^{*} \bullet \phi(x) + b\\ 由式(19)可知{w}=\sum_{i=1}^{m} \alpha_{i} y_{i} {\phi}({x}_{i}) \\ 因此有: g(x)=\sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x, x_j)+ b^{*} \]

然后我们令

\[\begin{equation}E_{i}=g\left(x_{i}\right)-y_{i}=\left(\sum_{j=1}^{N} \alpha_{j} y_{j} K\left(x_{j}, x_{i}\right)+b\right)-y_{i}, \quad i=1,2\end{equation} \]

同时引进记号:

\[\begin{equation}v_{i}=\sum_{j=3}^{N} \alpha_{j} y_{j} K\left(x_{i}, x_{j}\right)=g\left(x_{i}\right)-\sum_{j=1}^{2} \alpha_{j} y_{j} K\left(x_{i}, x_{j}\right)-b, \quad i=1,2\end{equation} \]

因此式\((22)\)可以改写成:

\[\begin{equation}\begin{array}{c} W\left(\alpha_{1}, \alpha_{2}\right)=| \frac{1}{2} K_{11} \alpha_{1}^{2}+\frac{1}{2} K_{22} \alpha_{2}^{2}+y_{1} y_{2} K_{12} \alpha_{1} \alpha_{2}- \\ \left(\alpha_{1}+\alpha_{2}\right)+y_{1} v_{1} \alpha_{1}+y_{2} v_{2} \alpha_{2} \end{array}\end{equation} \tag{24} \]

又由于\(\alpha_{1} y_{1}+\alpha_{2} y_{2}=\varsigma,\quad y_iy_i = 1\),因此\(\alpha_1\)可以示意为:

\[\begin{equation}\alpha_{1}=\left(\varsigma-y_{2} \alpha_{2}\right) y_{1}\end{equation} \]

代入式\((24)\)中,我们有:

\[\begin{equation}\begin{aligned} W\left(\alpha_{2}\right)=& \frac{1}{2} K_{11}\left(s-\alpha_{2} y_{2}\right)^{2}+\frac{1}{2} K_{22} \alpha_{2}^{2}+y_{2} K_{12}\left(s-\alpha_{2} y_{2}\right) \alpha_{2}-\\ &\left(s-\alpha_{2} y_{2}\right) y_{1}-\alpha_{2}+v_{1}\left(s-\alpha_{2} y_{2}\right)+y_{2} v_{2} \alpha_{2} \end{aligned}\end{equation} \]

然后,我们对\(\alpha_2\)求导数:

\[\begin{equation}\begin{aligned} \frac{\partial W}{\partial \alpha_{2}}=& K_{11} \alpha_{2}+K_{22} \alpha_{2}-2 K_{12} \alpha_{2}-\\ & K_{11 S} y_{2}+K_{12} s y_{2}+y_{1} y_{2}-1-v_{1} y_{2}+y_{2} v_{2} \end{aligned}\end{equation} \]

令其导数为0可得:

\[\begin{equation}\begin{aligned} \left(K_{11}+K_{22}-2 K_{12}\right) \alpha_{2}=& y_{2}\left(y_{2}-y_{1}+\varsigma K_{11}-\varsigma K_{12}+v_{1}-v_{2}\right) \\ =& y_{2}\left[y_{2}-y_{1}+\varsigma K_{11}-\varsigma K_{12}+\left(g\left(x_{1}\right)-\sum_{j=1}^{2} y_{j} \alpha_{j} K_{1 j}-b\right)-\right.\\ &\left.\left(g\left(x_{2}\right)-\sum_{j=1}^{2} y_{j} \alpha_{j} K_{2 j}-b\right)\right] \end{aligned}\end{equation} \tag{25} \]

又由于\(\varsigma=\alpha_{1}^{\mathrm{old}} y_{1}+\alpha_{2}^{\mathrm{old}} y_{2}\)代入式\((25)\)可得:

\[\begin{equation}\begin{aligned} \left(K_{11}+K_{22}-2 K_{12}\right) \alpha_{2}^{\text {new }, \text { unc }} &=y_{2}\left(\left(K_{11}+K_{22}-2 K_{12}\right) \alpha_{2}^{\text {old }} y_{2}+y_{2}-y_{1}+g\left(x_{1}\right)-g\left(x_{2}\right)\right) \\ &=\left(K_{11}+K_{22}-2 K_{12}\right) \alpha_{2}^{\text {old }}+y_{2}\left(E_{1}-E_{2}\right) \end{aligned}\end{equation} \tag{26} \]

令:

\[\begin{equation}\eta=K_{11}+K_{22}-2 K_{12}=\left\|\Phi\left(x_{1}\right)-\Phi\left(x_{2}\right)\right\|^{2}\end{equation} \]

因此式\((26)\)可化简为:

\[\begin{equation}\alpha_{2}^{\text {new }, \mathrm{unc}}=\alpha_{2}^{\text {old }}+\frac{y_{2}\left(E_{1}-E_{2}\right)}{\eta}\end{equation} \tag{27} \]

同时有:

\[\alpha_2^{new}= \begin{cases} H& { \alpha_2^{new,unc} > H}\\ \alpha_2^{new,unc}& {L \leq \alpha_2^{new,unc} \leq H}\\ L& {\alpha_2^{new,unc} < L} \end{cases} \]

由于我们已经获得\(\alpha_2^{new}\),凭据\(\alpha_1^{new}\)\(\alpha_2^{new}\)之间的线性关系,我们可以就可以获得\(\alpha_1^{new}\)了。

我们每次完成两个变量的优化之后,都需要重新更新阈值。详细更新可以看下面部门。

SMO变量的选择方式

通过前面部门我们知道SMO算法就是选择两个变量举行优化,其中至少有一个变量是违反了KKT条件(如果没有违反的话,我们也就没必要举行盘算了)。我们可以使用\(\alpha_1\)代表第一个变量,\(\alpha_2\)代表第二个变量。

  1. 第一个变量的选择

    我们称第一个变量的选择为外层循环,外层循环在训练样本中选择违反KKT条件最严重的样本点。对于KKT条件,我们可以转成以下的形式:

    \[\begin{equation}\begin{aligned} \alpha_{i} &=0 \Leftrightarrow y_{i} g\left(x_{i}\right) \geqslant 1 &\quad(1)\\ 0<\alpha_{i} &<C \Leftrightarrow y_{i} g\left(x_{i}\right)=1 &\quad(2)\\ \alpha_{i} &=C \Leftrightarrow y_{i} g\left(x_{i}\right) \leqslant 1 &\quad(3)\\ 其中g(x_{i}) &= \sum_{j=1}^{N}\alpha_{j}y_{j}K(x_{i},x_{j})+b\\ \end{aligned}\end{equation} \tag{28} \]

    证实如下:

    对于上式\((1)\)

    \[\begin{equation}\begin{aligned} &\because\alpha_i = 0,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\ &\therefore \beta_i = C,\therefore\xi_i = 0\\ 又&\because 由KTT条件可知:1-\xi_i\le y_ig(x_i),\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\ &\therefore y_ig(x_i) \ge 1 \end{aligned}\end{equation} \]

    对于上式\((2)\)

    \[\begin{equation}\begin{aligned} &\because0<\alpha_{i} <C ,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\ &\therefore 0 \lt\beta_i \lt C,\therefore\xi_i = 0\\ 又&\because 由KTT条件可知:1-\xi_i\le y_ig(x_i),\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\ &\therefore y_ig(x_i) = 1-\xi_i = 1 \end{aligned}\end{equation} \]

    对于上式\((3)\)

    \[\begin{equation}\begin{aligned} &\because\alpha_i = C,\alpha_i + \beta_i = C ,且在KKT条件\beta_{i}\xi_{i}=0\\ &\therefore \beta_i = 0,\xi_i \ge0\\ 又&\because 由KTT条件可知:1-\xi_i\le y_ig(x_i),\alpha_{i} [y_{i}g(x_{i})-(1-\xi_{i})]=0\\ &\therefore y_ig(x_i) = 1-\xi_i \le 1 \end{aligned}\end{equation} \]

    固然我们也可以给定一定的精度局限\(\varepsilon\),此时KKT条件就酿成了:

    \[\begin{equation}\begin{array}{l} a_{i}=0 \Leftrightarrow y_{i} g\left(x_{i}\right) \geq 1-\varepsilon \\ 0<a_{i}<C \Leftrightarrow 1-\varepsilon \leq y_{i} g\left(x_{i}\right) \leq 1+\varepsilon \\ a_{i}=C \Leftrightarrow y_{i} g\left(x_{i}\right) \leq 1+\varepsilon \end{array}\end{equation} \]

    然后我们通过变形后的KKT条件,获得违反的样本点违反最严重的作为第一个变量就了。那么若何器量这个严重性呢?emm,就看\(g\left(x_{i}\right)\)距离KKT条件有多远就行了。

  2. 第二个变量的选择

    第二个变量选择的历程称之为内层循环,其尺度是希望能够使\(\alpha_2\)有足够大的转变。由式\((27)\)我们知道:

    \[\begin{equation}\alpha_{2}^{\text {new }, \mathrm{unc}}=\alpha_{2}^{\text {old }}+\frac{y_{2}\left(E_{1}-E_{2}\right)}{\eta}\end{equation} \]

    也就是说\(\alpha_2\)的转变量依赖于\(|E_1 - E_2|\),因此我们可以选择式\(|E_1 - E_2|\)最大的\(\alpha_2\)。由于\(\alpha_1\)已经确定,以是\(E_1\)也就已经确定,因此我们只需要确定\(E_2\)即可。若是\(E_1\)为正,则选取\(\alpha_2\)使\(E_2\)最小,若是\(E_1\)为负,则选取\(\alpha_2\)使\(E_2\)最大。

当我们完成两个变量的优化后(优化后的变量),我们就需要来更新阈值\(b\)

  • 若更新后的\(0<\alpha_{1} <C\)由式\((28)\)中的式\((2)\)可知:

\[\begin{equation}\sum_{i=1}^{N} \alpha_{i} y_{i} K_{i 1}+b=y_{1}\end{equation} \]

​ 于是有:

\[\begin{equation}b_{1}^{\mathrm{new}}=y_{1}-\sum_{i=3}^{N} \alpha_{i} y_{i} K_{i 1}-\alpha_{1}^{\mathrm{new}} y_{1} K_{11}-\alpha_{2}^{\mathrm{new}} y_{2} K_{21}\end{equation} \]

​ 由\(E_i\)的界说式\(\begin{equation}E_{i}=g\left(x_{i}\right)-y_{i}=\left(\sum_{j=1}^{N} \alpha_{j} y_{j} K\left(x_{j}, x_{i}\right)+b\right)-y_{i}, \quad i=1,2\end{equation}\),有:

\[\begin{equation}E_{1}=\sum_{i=3}^{N} \alpha_{i} y_{i} K_{i 1}+\alpha_{1}^{\mathrm{old}} y_{1} K_{11}+\alpha_{2}^{\mathrm{old}} y_{2} K_{21}+b^{\mathrm{old}}-y_{1}\end{equation} \]

​ 因此则有:

\[\begin{equation}y_{1}-\sum_{i=3}^{N} \alpha_{i} y_{i} K_{i 1}=-E_{1}+\alpha_{1}^{\text {old }} y_{1} K_{11}+\alpha_{2}^{\text {old }} y_{2} K_{21}+b^{\text {old }}\end{equation} \]

​ 最终:

\[\begin{equation}b_{1}^{\text {new }}=-E_{1}-y_{1} K_{11}\left(\alpha_{1}^{\text {new }}-\alpha_{1}^{\text {old }}\right)-y_{2} K_{21}\left(\alpha_{2}^{\text {new }}-\alpha_{2}^{\text {old }}\right)+b^{\text {old }}\end{equation} \]

  • 同理若$0<\alpha_{2} \lt C $,则有

    \[\begin{equation}b_{2}^{\text {new }}=-E_{2}-y_{1} K_{12}\left(\alpha_{1}^{\text {new }}-\alpha_{1}^{\text {old }}\right)-y_{2} K_{22}\left(\alpha_{2}^{\text {new }}-\alpha_{2}^{\text {old }}\right)+b^{\text {old }}\end{equation} \]

  • \(\alpha_1^{new},\alpha_2^{new}\)同时知足\(0<\alpha_{i}^{new} \lt C\),则最终:

\[b^{new} = \frac{b_1^{new}+b_2^{new}}{2} \]

  • \(\alpha_1^{new},\alpha_2^{new}\)\(0\)或者\(C\),那么最终:

    \[b^{new} = \frac{b_1^{new}+b_2^{new}}{2} \]

    综上:

    \[\begin{equation}b=\left\{\begin{array}{ll} b_{1}^{new}, & 0<\alpha_{1}<C \\ b_{2}^{new}, & 0<\alpha_{2}<C \\ \frac{1}{2}\left(b_{1}^{new}+b_{2}^{new}\right), & \text { others } \end{array}\right.\end{equation} \]

更新完\(\alpha_1\)\(\alpha_2\)后我们需要将\(E_i\)举行更新,以便后续的\(\alpha_i\)\(b\)的求解。

\[\begin{equation} E_{1}=\sum_{i=3}^{N} \alpha_{i} y_{i} K_{i 1}+\alpha_{1}^{\mathrm{new}} y_{1} K_{11}+\alpha_{2}^{\mathrm{new}} y_{2}K_{21}+b^{\mathrm{new}}-y_{1}\\ E_{2}=\sum_{i=3}^{N} \alpha_{i} y_{i} K_{i 2}+\alpha_{1}^{\mathrm{new}} y_{1} K_{12}+\alpha_{2}^{\mathrm{new}} y_{2}K_{22}+b^{\mathrm{new}}-y_{2}\\ \end{equation} \]

总结

综上,SVM就先容了,SVM看起来很简单,就是找到一条合适的线能够比较好的支解数据集。为了数值化“比较好”这个词,我们引出了距离的观点,然后我们希望这个距离足够大,而且所有的数据完善的星散在距离的双方。于是这个问题就酿成了在一定条件下的极值问题。然后我们选择使用拉格朗日乘子法去解决这个问题,其中在极值点会知足KKT条件。为了简化求解,我们通过Slater条件将问题转成了对偶问题。面临非线性问题,我们选择使用核技巧去解决,同时为了制止过拟合,我们选择使用软距离;并最终使用SMO算法取获得合适的解。

说实话,原本只是想稍微的先容一下SVM以及它的原理,自己实在对SVM也是属于之听过没真正的领会过的情形。听别人说SVM不是很难,然则最后却发现emm,越推感受数学越巧妙。也许上面的内容看起来并不难,然则它却是由前人花费无数的日日夜夜最终才得出了谜底,也许这就是科学的魅力吧!

下面是参考的内容,其中强烈推荐《统计学习方式第2版》

参考

  • 【机械学习】支持向量机SVM原理及推导
  • 拉格朗日乘子法——剖析推导
  • 真正明白拉格朗日乘子法和 KKT 条件
  • Karush–Kuhn–Tucker conditions
  • Affine Functions
  • 《西瓜书》
  • 从零推导支持向量机 (SVM)——张皓
  • 序列最小优化算法wiki
  • 《统计学习方式第2版》
  • 支持向量机原理(四)SMO算法原理
  • 关于SVM中SMO算法第一个向量选择的问题
  • 支持向量机通俗导论(明白SVM的三层境界)
,

Sunbet

www.0379st.com信誉来自于每一位客户的口碑,Sunbet贴心的服务,让你尊享贵宾通道,秒速提现,秒速到账,同行业中体验最佳。

申博声明:该文看法仅代表作者自己,与本平台无关。转载请注明:太原天气:数据挖掘入门系列教程(八点五)之SVM先容以及从零开始推导公式

网友评论

  • (*)

最新评论

站点信息

  • 文章总数:927
  • 页面总数:0
  • 分类总数:8
  • 标签总数:2136
  • 评论总数:58
  • 浏览总数:6655