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

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

上一章节介绍了支持向量机的生成和求解方式,能够根据训练集依次得出(\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)}

核函数概念

接下来要介绍”核”的概念,这个概念具有这样的性质:

算法对于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)公式中的内积从(映射到(。 至于为什么需要映射后的特征而不是最初的特征来参与计算,上面提到的一个原因: 为了更好的拟合,另外一个原因是 样本可能存在线性不可分的情况,而特征映射到高维过后往往就可分了

如果原始特征的内积为(,映射后为(,那么一般核函数定义为:

[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))将指向不同的方向,因此内即将会比较小。

如果有一个核函数如下:

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

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

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

上面提到了两个原因:

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

第二种情况如下所示:

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

左边使用线性的时候,使用 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)}

只需要将(替换成(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)都是拉格朗日算子,根据上一章节拉格朗日的求解步骤:

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

最后化简得到的结果是:

[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 ]

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

  1. 首先选择两个要改变的(\alpha)值(\alpha_i)、(\alpha_j)
  2. 其次保持除了(\alpha_i)、(\alpha_j)之外的所有参数固定
  3. 最后同时相对于这两个参数使(\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优化算法的核心思想:

  1. 首先选择两个要改变的(\alpha)值(\alpha_i)、(\alpha_j)
  2. 其次保持除了(\alpha_i)、(\alpha_j)之外的所有参数固定
  3. 最后同时相对于这两个参数使(\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的步骤总结如下:

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

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

实例

有一份数据 svm_data1,加载读取:

import pandas as pd
import matplotlib.pyplot as plt
from scipy.io import loadmat
from sklearn import svm

# &#x52A0;&#x8F7D;data1
raw_data = loadmat('./svm_data1.mat')
# print(raw_data)

# &#x8BFB;&#x53D6;data1&#x7684;&#x6570;&#x636E;
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)

# &#x67E5;&#x770B;data1&#x7684;&#x6570;&#x636E;&#x5206;&#x5E03;
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核分类:

# &#x505A;svm&#x5206;&#x7C7B;&#xFF0C;&#x4F7F;&#x7528;RBF&#x6838;
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,因此设置了网格调参:

# &#x7B80;&#x5355;&#x7684;&#x7F51;&#x683C;&#x8C03;&#x53C2;
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 = 0
best_params = {'C': None, 'gamma': None}

# &#x7F51;&#x683C;&#x8C03;&#x53C2;&#x5F00;&#x59CB;
for C in C_values:
    for gamma in gamma_values:

        # &#x505A;svm&#x5206;&#x7C7B;&#xFF0C;&#x4F7F;&#x7528;RBF&#x6838;
        svc = svm.SVC(C=C, gamma=gamma, probability=True)
        svc.fit(data[['X1', 'X2']], data['y'])

        # &#x4EA4;&#x53C9;&#x9A8C;&#x8BC1;
        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}

数据和代码下载请关注公众号【 机器学习和大数据挖掘 】,后台回复【 机器学习 】即可获取

Original: https://www.cnblogs.com/TTyb/p/12234186.html
Author: TTyb
Title: 【机器学习】算法原理详细推导与实现(五):支持向量机(下)

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/8070/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

发表回复

登录后才能评论
免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部