【机器学习】算法原理详细推导与实现(五):支持向量机(下)

【机器学习】算法原理详细推导与实现(五):支持向量机(下)

【机器学习】算法原理详细推导与实现(五):支持向量机(下)

上一章节介绍了支持向量机的生成和求解方式，能够根据训练集依次得出\(\omega\)、\(b\)的计算方式，但是如何求解需要用到核函数，将在这一章详细推导实现。

核函数

在讲核函数之前，要对上一章节得到的结果列举出来。之前需要优化的凸函数为：

\[min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2 \]

\[y^{(i)}(\omega^Tx^{(i)}+b) \geq 1 ,i=1,2,...,m \]

这里假设数据是线性可分隔的，对于这个优化项目，给定一个训练集合，这个问题的算法会找到一个数据集合的最优间隔分类器，可以使训练样本的几何间隔最大化。

在上一章节​​【机器学习】算法原理详细推导与实现(四):支持向量机(上)​​中，我们推出了这个问题的对偶问题，也就是要使这个式子最大化：

\[max_{\alpha}\Gamma(\omega,b,\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)} \]

\[\alpha_i \geq 0,i=1,2,...,m \]

\[\sum_{i=1}^m\alpha_iy^{(i)}=0 \]

上面是我们的原始问题，且根据拉格朗日对偶步骤计算得到参数\(\omega\)：

\[\omega=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \]

\[b=\frac{max_{i:y^{(i)}=-1}\omega^Tx^{(i)}+min_{i:y^{(i)}=1}\omega^Tx^{(i)}}{2} \]

当需要做分类预测时，需要对新来的输入值\(x\)进行计算，计算其假设的值是否大于零，也就是做一次线性运算来判断是正样本还是负样本，有如下计算函数：

\[\begin{split} h_{\omega,b}(x)&=g(\omega^Tx+b) \\ &=g(\sum^m_{i=1}\alpha_iy^{(i)}+b) \end{split} \]

核函数概念

接下来要介绍“核”的概念，这个概念具有这样的性质：

算法对于x的依赖仅仅局限于这些内积的计算，甚至在整个算法中，都不会直接使用到向量x的值，而是只需要用到训练样本与输入特征向量的内积

而“核”的概念是这样的，考虑到最初在​​【机器学习】算法原理详细推导与实现(一):线性回归​​中提出的问题，比如有一个输入\(x\in R\)是房屋的面积，\(y\)是房子的价格。假设我们从样本点的分布中看到\(x\)和\(y\)符合3次曲线，那么我们会希望使用\(x\)的三次多项式来逼近这些样本点。首先将特征\(x\)扩展到三维\((x,x^2,x^3)\)，这里将这种特征变换称作特征映射，映射函数为\(\varphi(x)\)：

\[\varphi(x)=\begin{bmatrix} x \\ x^2 \\ x^3 \end{bmatrix} \]

用\(\varphi(x)\)代表原来的特征\(x\)映射成的，这里希望得到映射后的特征应用于​​svm​​分类，而不是最初的一维特征，只需要将前面\(\omega^Tx+b\)公式中的内积从\(\)映射到\(<\varphi(x)^{(i)},\varphi(x)^{(j)}>\)。至于为什么需要映射后的特征而不是最初的特征来参与计算，上面提到的一个原因：为了更好的拟合，另外一个原因是样本可能存在线性不可分的情况，而特征映射到高维过后往往就可分了。

如果原始特征的内积为\(\)，映射后为\(<\varphi(x),\varphi(z)>\)，那么一般核函数定义为：

\[K(x,z)=\varphi(x)^T\varphi(z) \]

为什么会那么定义核函数？有些时候\(\varphi(x)\)的维度将会非常的高，可能会包含非常高维的多项式特征，甚至会到无限维。当\(\varphi(x)\)的维度非常高时，可能无法高效的计算内积，甚至无法计算。如果要求解前面所提到的凸函数，只需要先计算\(\varphi(x)\)，然后再计算\(\varphi(x)^T\varphi(z)\)即可，但是这种常规方法是很低效的，比如最开始的特征是\(n\)维，并将其映射到\(n^2\)维度，这时候计算需要\(O(n^2)\)的时间复杂度。这里假设\(x\)和\(z\)都是\(n\)维的：

\[K(x,z)=(x^Tz)^2 \]

展开后得到：

\[\begin{split} K(x,z)&=(x^Tz)^2 \\ &=(\sum^n_{i=1}x_iz_i)(\sum^n_{j=1}x_jz_j) \\ &=\sum^n_{i=1}\sum^n_{j=1}x_ix_jz_iz_j \\ &=\sum^n_{i=1}\sum^n_{j=1}(x_ix_j)(z_iz_j) \\ &=\varphi(x)^T\varphi(z) \end{split} \]

也就是说，如果开始的特征是\(n\)维，并将其映射到\(n^2\)维度后，其映射后的计算量为\(O(n^2)\)。而如果只是计算原始特征\(x\)和\(z\)的内积平方，时间复杂度还是\(O(n)\),其结果等价于映射后的特征内积。

回到之前的假设，当\(n=3\)时，这个核\(K(x,z)\)对应的特征映射\(\varphi(x)\)为：

\[\varphi(x)=\begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \end{bmatrix} \]

这是时间复杂度为\(O(n^2)\)计算方式，而如果不计算\(\varphi(x)\)，直接计算\(\)从而得到<\(\varphi(x)\),\(\varphi(z)\)>的内积，时间复杂度将缩小\(O(n)\)。

同理将核函数定义为：

\[\begin{split} K(x,z)&=(x^Tz+c) \\ &=\sum^n_{i,j=1}(x_ix_j)(z_iz_j)+\sum^n_{i=1}(\sqrt{2cx_i})(\sqrt{2cx_j})+c^2 \end{split} \]

当\(n=3\)时，这个核\(K(x,z)\)对应的特征映射\(\varphi(x)\)为：

\[\varphi(x)=\begin{bmatrix} x_1x_1 \\ x_1x_2 \\ x_1x_3 \\ x_2x_1 \\ x_2x_2 \\ x_2x_3 \\ x_3x_1 \\ x_3x_2 \\ x_3x_3 \\ \sqrt{2c}x_1 \\ \sqrt{2c}x_2 \\ \sqrt{2c}x_3 \\ c \end{bmatrix} \]

总结来说，核的一种一般化形式可以表示为：

\[K(x,z)=(x^Tz+c)^d \]

对应着\(\begin{bmatrix} n+d \\ d \end{bmatrix}\)

假如给定一组特征\(x\)，将其转化为一个特征向量\(\varphi(x)\);给定一组特征\(z\)，将其转化为一个特征向量\(\varphi(z)\)，所以核计算就是两个向量的内积\(<\varphi(x),\varphi(z)>\)。如果\(\varphi(x)\)和\(\varphi(z)\)向量夹角越小，即两个向量越相似(余弦定理)，那么\(\varphi(x)\)和\(\varphi(z)\)将指向相同的方向，因此内积会比较大；相反的如果\(\varphi(x)\)和\(\varphi(z)\)向量夹角越大，即两个向量相似度很低，那么\(\varphi(x)\)和\(\varphi(z)\)将指向不同的方向，因此内即将会比较小。

如果有一个核函数如下:

\[K(x,z)=exp^{(-\frac{||x-z||^2}{2\sigma^2})} \]

如果\(x\)和\(z\)很相近(\(||x-z||\approx0\))，那么核函数的值为1；如果\(x\)和\(z\)相差很大(\(||x-z||>>0\))，那么核函数的值约等于0。这个核函数类似于高斯分布，所以称为高斯核函数，能够把原始特征映射到无穷维。

在前面说了：为什么需要映射后的特征而不是最初的特征来参与计算？

上面提到了两个原因：

为了更好的拟合样本可能存在线性不可分的情况，而特征映射到高维过后往往就可分了

第二种情况如下所示：

左边使用线性的时候，使用​​svm​​学习出\(\omega\)和\(b\)后，新来样本\(x\)就可以代入到\(\omega^Tx+b\)中进行判断，但是像图中所示是无法判断的；如果使用了核函数过后，\(\omega^Tx+b\)变成了\(\omega^T\varphi(x)+b\)，直接可以用下面的方式计算：

\[\begin{split} \omega^Tx+b&=(\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)})^Tx+b \\ &=\sum^m_{i=1}\alpha_iy^{(i)}+b \\ &=\sum^m_{i=1}\alpha_iy^{(i)}K(x^{(i)})+b \end{split} \]

只需要将\(\)替换成\(K(x^{(i)})\)就能将低维特征转化为高维特征，将线性不可分转化成高维可分。

规则化和不可分情况处理

我们之前讨论的情况都是建立在样例线性可分的假设上，当样例线性不可分时，我们可以尝试使用核函数来将特征映射到高维，这样很可能就可分了。然而，映射后我们也不能100%保证可分。那怎么办呢，我们需要将模型进行调整，以保证在不可分的情况下，也能够尽可能地找出分隔超平面。

看下面的图可以解释：

在右边的图可以可以看到上面一个离群点（可能是噪声），会造成超平面的移动改变，使集合间隔的间隔距离缩小，可见以前的模型对噪声非常敏感。再有甚者，如果离群点在另外一个类中，那么这时候就是线性不可分了。 这时候我们应该允许一些点游离在模型中违背限制条件（函数间隔大于 1）。我们设计得到新的模型如下（也称软间隔）：

\[min_{\gamma,\omega,b}->\frac{1}{2}||\omega||^2+C\sum^m_{i=1}\xi_i \]

\[y^{(i)}(\omega^Tx^{(i)}+b) \geq 1-\xi_i ,i=1,2,...,m \]

\[\xi_i \geq 0,i=1,...,m \]

引入非负参数\(\xi_i\)(松弛变量)过后，也就意味着允许某些样本的函数间隔小于1，甚至是负数，负数就代表样本点在对方区域中，如上方右边图的虚线作为超平面，一个空心圆点的函数间隔为负数。

增加新的条件后，需要重新调整目标函数，增加对离群点进行处罚，也就是在求最小值的目标函数后面加上\(C\sum^m_{i=1}\xi_i\)，因为定义\(\xi_i \geq 0\)，所以离群点越多，那么目标函数的值越大，就等于违背求最小值的初衷。而\(C\)是离群点的权重，\(C\)越大表明离群点对于目标函数的影响越大，也就是越不希望看到离群点。

修改目标函数后，原式子变成：

\[\Gamma(\omega,b,\xi,\alpha,r)=\frac{1}{2}\omega^T\omega+C\sum^m_{i=1}\xi_i-\sum^m_{i=1}\alpha_i[y^{(i)}(x^T\omega+b)-1+\xi_i]-\sum^m_{i=1}r_i\xi_i \]

这里的\(\alpha\)和\(r\)都是拉格朗日算子，根据上一章节拉格朗日的求解步骤：

构造出拉格朗日函数后，将其看作是变量\(\omega\)和\(b\)的函数分别对其求偏导，得到\(\omega\)和\(b\)的表达式然后带入上述拉格朗日式子中，求带入后式子的极大值

最后化简得到的结果是：

\[max_{\alpha}W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)} \]

\[C \geq \alpha_i \geq 0,i=1,2,...,m \]

\[\sum_{i=1}^m\alpha_iy^{(i)}=0 \]

这里唯一不同的地方是限制条件多了一个离群点的权重\(C\)。

SMO优化算法

​​SMO​​ 是一个求解对偶问题的优化算法，目前还剩下最后的对偶问题还未解决：

\[max_{\alpha}W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)} \]

\[C \geq \alpha_i \geq 0,i=1,2,...,m \]

\[\sum_{i=1}^m\alpha_iy^{(i)}=0 \]

我们需要根据上述问题设计出一个能够高效解决的算法，步骤如下：

首先选择两个要改变的\(\alpha\)值\(\alpha_i\)、\(\alpha_j\)其次保持除了\(\alpha_i\)、\(\alpha_j\)之外的所有参数固定最后同时相对于这两个参数使\(\omega\)取最优，且同时满足所有约束条件

怎样在满足所有约束条件的情况下，相对于选出来的两个参数\(\alpha_i\)、\(\alpha_j\)使\(\omega\)取最优值？​​SMO​​​优化算法能够高效完成这个工作。​​SMO​​算法非常的高效，只需要更多次数的迭代以达到收敛，而且每次迭代所需要的代价都非常小。

为了推出这个步骤，我们需要相对于\(\alpha_i\)、\(\alpha_j\)进行更新，假设取值是\(\alpha_1\)、\(\alpha_2\)，即假设\(\alpha_1\)、\(\alpha_2\)不再是变量（可以由其他值推出），可以根据约束条件推导得到：

\[\begin{split} \sum_{i=1}^m\alpha_iy^{(i)}&=0 \\ \alpha_1y_1+\alpha_2y_2&=-\sum_{i=3}^m\alpha_iy^{(i)} \end{split} \]

由于\(\alpha_3\)、\(\alpha_4\)、...、\(\alpha_m\)都是已知固定值，因此为了方便将等式右边，可将等式右边标记成\(\zeta\)：

\[\alpha_1y^{(1)}+\alpha_2^{(2)}=\zeta \]

还有一个约束条件：

\[C \geq \alpha_i \geq 0,i=1,2,...,m \]

这个约束条件被称作为“方形约束”，如果将\(\alpha_1\)、\(\alpha_2\)画出来：

那么\(\alpha_1\)、\(\alpha_2\)表示的值应该都在\([0,C]\)之间，也就是在方框里面，这意味着：

\[\alpha_1=\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}} \]

然后带入到需要求解的式子中：

\[W(\alpha_1,\alpha_2,...,\alpha_m)=W(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}},\alpha_2,...,\alpha_m) \]

在前面我们认为\(\alpha_3\)、\(\alpha_4\)、...、\(\alpha_m\)都是已知固定值，只有\(\alpha_1\)、\(\alpha_2\)是未知需要求解的。那么把\(W(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}},\alpha_2,...,\alpha_m)\)展开后可以表示成\(a\alpha_2^2+b\alpha_2+c\)的形式，其中\(a\)、\(b\)、\(c\)是由\(\alpha_3\)、\(\alpha_4\)、...、\(\alpha_m\)表示出来，即\(W\)是一个二次函数。而其实对于所有的\(\alpha\)，如果保持其他参数都固定的话，都可以表示成\(W\)关于某个\(\alpha\)的一元二次函数：

\[\begin{split} W(\alpha_1,\alpha_2,...,\alpha_m)&=W(\frac{\zeta-\alpha_2y^{(2)}}{y^{(1)}},\alpha_2,...,\alpha_m) \\ &=a\alpha_2^2+b\alpha_2+c \end{split} \]

由于上面式子是一个标准的一元二次函数，所以很容易求解出最优值，从而可以得到\(\alpha_2\)的最优值，而这个最优值一定会在上图中\(\alpha_1-\alpha_2=\zeta\)这条线上，且在“方形约束”中。按照这种方式解除\(\alpha_2\)后，之后根据\(\alpha_1\)和\(\alpha_2\)的关系求解出\(\alpha_1\)，这样子就求解出了相对于\(\alpha_1\)和\(\alpha_2\)关于\(W\)，且满足所有约束条件的最优值，该算法的关键是对一个一元二次函数求最优解，这个求解非常简单，这就使得​​SMO​​算法的内嵌计算非常高效。

如何求解\(\alpha_2\)的值呢？只需要对式子进行求导\(a\alpha_2^2+b\alpha_2+c\)，即对\(W\)进行求导，然而要保证\(\alpha_2\)即在方形约束内，也在\(\alpha_1-\alpha_2=\zeta\)这条线上，那么就要保证\(H \geq \alpha_2 \geq L\)，这里使用\(\alpha_2^{new,unclipped}\)来表示求导出来的\(\alpha_2\)，然后最后\(\alpha_2^new\)的迭代更新方式如下所示：

\[\alpha_2^new=\begin{cases} H, & \text {if $\alpha_2^{new,unclipped}>H$} \\ \alpha_2^{new,unclipped}, & \text{if $H \geq \alpha_2^{new,unclipped} \geq L$} \\ L, & \text{if $\alpha_2^{new,unclipped} < L$} \end{cases} \]

得到\(\alpha_2\)后，由此可以返回求解\(\alpha_1\)得到新值\(\alpha_1\)，这里就是​​SMO​​​优化算法的核心思想。根据​​SMO​​优化算法的核心思想：

首先选择两个要改变的\(\alpha\)值\(\alpha_i\)、\(\alpha_j\)其次保持除了\(\alpha_i\)、\(\alpha_j\)之外的所有参数固定最后同时相对于这两个参数使\(\omega\)取最优，且同时满足所有约束条件

可以求解出所有的\(\alpha\)，使得\(W\)取得最大值，即原问题将得到解决：

\[max_{\alpha}W(\alpha)=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum^m_{i=1,j=1}\alpha_i\alpha_jy^{(i)}y^{(j)} \]

\[C \geq \alpha_i \geq 0,i=1,2,...,m \]

\[\sum_{i=1}^m\alpha_iy^{(i)}=0 \]

总结

​​svm​​的步骤总结如下：

先确定间隔器，这里svm一般默认是几何间隔由间隔器确定间隔函数从间隔函数查看是否包含不等式约束形式根据拉格朗日对偶步骤计算得到参数w、b规则化不可分的参数，即在原对偶式子中加入离群点权重\(C\)，问题转换为\(max_{\alpha}W(\alpha)\)利用​​SMO​​优化算法求解\(W(\alpha)\)最优值，首先选择两个要改变的\(\alpha\)值\(\alpha_i\)、\(\alpha_j\)其次保持除了\(\alpha_i\)、\(\alpha_j\)之外的所有参数固定最后同时相对于这两个参数使\(\omega\)取最优，且同时满足所有约束条件，最后确定选取的这两个\(\alpha_i\)、\(\alpha_j\)的值重复步骤6-9直到所有参数\(\alpha\)求解完成

​​svm​​在神经网络出来之前一直是最优的算法。相比于之前的算法推导复杂一些，但是逻辑并不难，它不想逻辑回归那样去拟合样本点，而是根据几何空间去寻找最优的分割超平面，为了判断哪个超平面最好，引入几个平面间隔最大化目标，从而求解出结果。

实例

有一份数据​​svm_data1​​，加载读取：

import pandas as pdimport matplotlib.pyplot as pltfrom scipy.io import loadmatfrom sklearn import svm# 加载data1raw_data = loadmat('./svm_data1.mat')# print(raw_data)# 读取data1的数据data = pd.DataFrame(raw_data['X'], columns=['X1', 'X2'])data['y'] = raw_data['y']positive = data[data['y'].isin([1])]negative = data[data['y'].isin([0])]print(positive.shape)print(negative.shape)# 查看data1的数据分布fig, ax = plt.subplots(figsize=(12, 8))ax.scatter(positive['X1'], positive['X2'], s=50, marker='x', label='Positive')ax.scatter(negative['X1'], negative['X2'], s=50, marker='o', label='Negative')ax.legend()plt.show()

数据分布如下所示：

可以看到数据分在两边很好区分，用一般的分类器例如逻辑回归、朴素贝叶斯即可区分，这里就用​​svm​​的线性核进行分类，设置离群点的权重\(C=1\)，即不区分离群点：

svc = svm.LinearSVC(C=1, loss='hinge', max_iter=1000)svc.fit(data[['X1', 'X2']], data['y'])data1_score_1 = svc.score(data[['X1', 'X2']], data['y'])print(data1_score_1)

得到的准确率为​​0.980392156863​​，分类的图如下：

可以看到左上角有一个点原来是正样本，但是被分类为蓝色(负样本)，所以正样本21个，负样本30个，被误分的概率刚好是\(\frac{1}{51}=‭0.01960784313‬\)，所以准确率是\(1-‭0.01960784313‬=0.980392156863\)，刚好对的上。现在这里设置离群点的权重\(C=100\)用以区分离群点，得到的准确率为​​1.0​​，分类图像为：

再看第二份数据分布图如下：

这次就不能用线性核分类，需要用到​​RBF​​核分类：

# 做svm分类，使用RBF核svc = svm.SVC(C=100, gamma=10, probability=True)svc.fit(data[['X1', 'X2']], data['y'])data['Probability'] = svc.predict_proba(data[['X1', 'X2']])[:, 0]

分类的结果图如下所示：

结果得到的准确率只有​​0.769228287521​​，因此设置了网格调参：

# 简单的网格调参C_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]gamma_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]best_score = 0best_params = {'C': None, 'gamma': None}# 网格调参开始for C in C_values: for gamma in gamma_values: # 做svm分类，使用RBF核 svc = svm.SVC(C=C, gamma=gamma, probability=True) svc.fit(data[['X1', 'X2']], data['y']) # 交叉验证 data2_score = cross_validation.cross_val_score(svc, data[['X1', 'X2']], data['y'], scoring='accuracy', cv=3) print(data2_score.mean())

最后准确率提高到​​0.858437379017​​​，调整到的最优参数为​​{'C': 10, 'gamma': 100}​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。