机器学习入门|支持向量机(一)

简介: 主要是对周志华老师的西瓜书《机器学习》的学习笔记整理,希望能有所收获( ̄︶ ̄)↗ 

昨天给自己打了一针鸡血之后,今天说干就干!上午粗略地扫了一下周志华的西瓜书,感觉《支持向量机》这章写的数学公式有点多,有点懵那啥(ノへ ̄、)

由于阿里云对wordpress博客搬家还在完善中,欢迎访问我和朋友的博客白水东城-支持向量机(一)

一、一些概念

支持向量机在高维或无限维空间中构造超平面或超平面集合,其可以用于分类、回归或其他任务。直观来说,分类边界距离最近的训练资料点越远越好,因为这样可以缩小分类器的泛化误差。说白了,就是要基于训练集在样本空间中找一个划分超平面,将不同类别的样本分开。也可以理解为对原空间进行升维,把在本来维度上不可用一个平面分割的类别在更高的维度可分。为了更直观的理解一下,请看下图!
6298996_4fc35cedc0742800_1_

什么是支持向量?

支持向量 (Support Vector)是指在训练集 (Training data set)中,在分类时给予最多信息的点集合,如下图,被红色框围起来的这四个训练资料点就被称之为支持向量机。 支持向量就是与分类边界距离最近的训练资料点。从支持向量机的最佳化问题可以推导出一个重要性质:支持向量机的分类边界可由支持向量决定,而与其他资料点无关。这也是它们称为“支持向量”的原因。
20160317144454115_1_

什么是超平面(hyperplane)?

对于二维数据集,将数据集分隔开的直线称为分隔超平面,如果分隔的是三维的,分类的就是面,如果是更高维的就是超平面。支持向量机建构一个或多个高维(甚至是无限多维)的超平面来分类资料点,将分类的决策边界统称为超平面。分布在超平面一侧的所有数据都属于某个类别,而分布在另一侧的所有数据都属于另一个类别。好的分类边界(也就是求的超平面)要距离最近的训练点越远越好,因为这样可以减低分类器的泛化误差。在支持向量机中,分类边界与最近的训练资料点之间的距离称为间隔(margin),支持向量机的目标即为找出间隔最大的超平面来作为分类边界。线性可分SVM就是在训练集中学习得到一个线性分类器,也就是得到一个超平面:$f(x)=sign(\boldsymbol{\omega}^{T}\boldsymbol{x}+b)$,线性可分表明当$\boldsymbol{\omega}^{T}\boldsymbol{x}+b>0$时,对应的$f(x)=1$,相应的当$\boldsymbol{\omega}^{T}\boldsymbol{x}+b<0$时,对应的$f(x) = -1$,而$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=0$就是所要寻找的超平面,此时对应的超平面为硬间隔超平面。(关于硬间隔和软间隔后文细说)
什么是间隔(margin)?
对于于训练样本集$D = \{ (\boldsymbol{x_{1}},y_{1}),(\boldsymbol{x_{2}},y_{2}),...,(\boldsymbol{x_{m}},y_{m})\},y_{i}\epsilon\{-1 , +1\}$.在样本空间$D$中,划分超平面可通过如下线性方程来描述:

$$ \boldsymbol{\omega}^{T}\boldsymbol{x}+b=0, $$

其中$\boldsymbol{\omega}=(\omega_{1};\omega_{2};...;\omega_{d})$为法向量,决定了超平面的方向;$b$为位移项,决定了超平面与原点的距离。显然,划分超平面可以由$\boldsymbol{\omega}$和$b$唯一确定。设空间中任意一个样本点到达超平面的距离 $λ$ , 假定对于一个点$x$ 它投影到超平面上对应的点为$x_{0}$,我们可以得出

$$ x = x_{0} + \lambda\frac{\boldsymbol{\omega}}{||\boldsymbol{\omega}||}, $$

其中$||\boldsymbol{\omega}||$为$\boldsymbol{\omega}$的二范数,可以理解为长度,$\frac{\boldsymbol{\omega}}{||\boldsymbol{\omega}||}$可以理解为单位法向量,又因为$x_{0}$是超平面上的点,所以有$\boldsymbol{\omega}^{T}\boldsymbol{x}_{0}+b = 0$,结合上式可以求得点$x$与超平面之间的距离关系

$$ \lambda = \frac{|\boldsymbol{\omega}^{T}\boldsymbol{x}+b|}{||\boldsymbol{\omega}||} $$

注:$||\omega||_{2}(or ||\omega||)=(\sum_{i=1}^{n}|x_{i}|^{2})^{\frac{1}{2}}$
好了,假设我们得到了超平面$(\boldsymbol{\omega},b)$,那么就可以进行以下的神操作来求间隔了!
440px_Svm_max_sep_hyperplane_with_margin_1_
首先,在左图中找到两个和这个超平面平行且距离相等的超平面:$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=-1$和$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$,保证在这两个超平面之间没有任何样本点,这两个超平面势必包含的是距离分隔超平面最近的点(也就是支持向量),那么问题就可转化为最大化这两个超平面之间的距离。它们之间的距离可表示为:$\gamma = \frac{2}{||\mathbf{w}||}$。这就是所谓的“间隔”了!那么问题就是最大化$\left \| \boldsymbol{\omega}\right \|^{-1}$,可以转化为最小化$\left \| \boldsymbol{\omega}\right \|^{2}$。最后结合两个超平面之间没有任何样本点这个约束,则有:对于任何一个正样本$y_{i}=+1$,它都要处在$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$这个超平面的右边,即要保证:$y=\boldsymbol{\omega}^{T}\boldsymbol{x}+b\geqslant +1$,同理对于任何一个负样本$y_{i}=-1$,它都要处于$\boldsymbol{\omega}^{T}\boldsymbol{x}+b=1$的左边,也就是要保证:$y=\boldsymbol{\omega}^{T}\boldsymbol{x}+b\leqslant -1$,于是可以合并为:$y_{i}(\boldsymbol{\omega}^{T}\boldsymbol{x}+b)\geqslant 1$。
于是寻找最优超平面的问题就可以转化为二次规划问题:

$$ \left\{\begin{matrix} \underset{\boldsymbol{\omega},b}{min}\frac{1}{2}||\boldsymbol{\omega}||^{2}\\ s.t. y_{i} (\boldsymbol{\omega}^{T}\boldsymbol{x}+b ) \geqslant 1 ,i = 1,2,...,m\end{matrix}\right.\;(3) $$

这就是支持向量机(SVM)的基本型。

二、支持向量的拉格朗日对偶求法

上文说到寻找最优超平面的问题就可以转化为二次规划问题,准确的来讲,因为目标函数是一个二次的,约束条件是线性的,所以它是一个凸的二次规划(convex quadratic programming)问题。能直接用二次规划函数包解决,但是对于这个问题的求解我们有更高效的解法——拉格朗日对偶(Langrange Dual),原因如下:

  • 原问题下,求解算法的复杂度与样本维度(等于权值$\boldsymbol{\omega}$的维度)有关,而在对偶问题下,求解算法的复杂度与样本数量(等于拉格朗日算子a的数量)有关
  • 如果做线性分类,且样本维度低于样本数量的话,在原问题下求解就好了;但如果做非线性分类,那就会涉及到升维(比如使用高斯核做核函数,其实是将样本升到无穷维),升维后的样本维度往往会远大于样本数量,此时显然在对偶问题下求解会更好。
  • 支持向量机中用到了高维映射,但是映射函数的具体形式几乎完全不可确定,而求解对偶问题之后,可以使用核函数来解决这个问题。

好吧,说了这么多优点,还是来见识一下“拉格朗日对偶”吧!

拉格朗日对偶

拉格朗日乘子法很多人在大一的高数课就应该学过,当时是用来求极值的(其实这里也是求极值(/▽\)),是一种寻找多元函数在一组等式约束下极值的方法,通过引入拉格朗日乘子,可以将有$d$个变量与$k$个约束条件的最优化问题转化为具有转化为具有$d+k$个变量的无约束优化问题求解。所谓对偶问题,简单来说就是要求这个问题的解可以通过求另外一个问题来得出。
首先将原模型的每条约束添加拉格朗日乘子$\alpha_{i}$,则该问题的拉格朗日函数可以写为

$$ L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) = \frac{1}{2}\left \| \boldsymbol{\omega} \right \|^{2} + \sum_{i = 1}^{m}\alpha_{i}(1-y_{i}(\boldsymbol{\omega}^{T}\boldsymbol{x}_{i}+b)),\;(2) $$

其中,$\boldsymbol{\alpha}=(\alpha_{1};\alpha_{2};...;\alpha_{m}).$令$L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) $对$\boldsymbol{\omega}$和$b$求偏导为零可得

$$ \frac{\partial L}{\partial \boldsymbol{\omega}} = 0 \rightarrow w = \sum_{i = 1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i} $$

$$ \frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i = 1}^{m}\alpha_{i}y_{i} = 0 $$

证明过程如下

$$ \frac{\partial L (\boldsymbol{\omega},b,\boldsymbol{\alpha})}{\partial \boldsymbol{\omega}} $$

$$ = \frac{\partial \frac{1}{2}\boldsymbol{\omega}^{T}\boldsymbol{\omega}}{\partial \boldsymbol{\omega}}-\sum_{i = 1}^{m}\frac{\partial \alpha_{i}y_{i}\boldsymbol{\omega}^{T}\boldsymbol{x}_{i}}{\partial \boldsymbol{\omega}} $$

$$ =\boldsymbol{\omega}-\sum_{i = 1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}=0 $$

注:求解过程要用到矩阵求导,之前写过写过一篇矩阵求导总结,强力推荐看!不是自吹自擂,反正,现在遇到的所有矩阵(向量)求导问题都能解决了!
将求导结果带入对偶式$L$,可以得到

$$ L (\boldsymbol{\omega},b,\boldsymbol{\alpha}) = \sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j} $$

于是,我们就得到了原式的对偶问题

$$ \underset{\alpha}{max}\sum_{i = 1}^{n}\alpha_{i}- \frac{1}{2} \sum_{i= 1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\boldsymbol{x}_{i}^{T}\boldsymbol{x}_{j}\;(1) $$

$$ s.t.\;\sum_{i=1}^{m}\alpha_{i}y_{i}=0,\;\alpha_{i}\geqslant0,i=1,2...,m. $$

解出$\boldsymbol{\alpha}$后,求出$\boldsymbol{\omega}$与$b$即可得到模型

$$ f(\boldsymbol{x})=\boldsymbol{\omega}^{T}\boldsymbol{x}+b $$

$$ =\sum_{i=1}^{m}\alpha_{i}y_{i}\boldsymbol{x}_{i}^{T}\boldsymbol{x}+b.\;(4) $$

从对偶问题(1)解出的$\alpha_{i}$是式(2)中的拉格朗日乘子,它恰对应着训练样本$(\boldsymbol(x)_{i},y_{i}$。因为式(3)中有约束不等式,所以上述过程需满足KKT条件,即要求

$$ \left\{\begin{matrix}\alpha_{i} \geqslant 0\\y_{i}f(\boldsymbol{x}_{i})-1 \geqslant 0 \\ \alpha_{i}(y_{i}f(\boldsymbol{x}_{i})-1) = 0\end{matrix}\right. $$

于是,对于任意训练样本$\boldsymbol{x}_{i},y_{i}$,总有$\alpha_{i}=0$或$y_{i}f(\boldsymbol{x}_{i})=1$。若$\alpha_{i}=0$,则该样本将不会在式(4)的求和中出现,也就不会对$f(x)$有任何影响;若$\alpha_{i}>0$,则必有$y_{i}f(\boldsymbol{x}_{i})=1$,所对应的样本点位于最大间隔边界上,是一个支持向量(可以看看前文的图)。这显示出支持向量机的一个充要性质:训练完成后,大部分的训练样本都不需要保留,最终模型仅与支持向量有关。

前文在提到过拉格朗提对偶的优势,在看完原始模型到对偶问题以及对偶模型化简的推导,再次说明一下:原问题下,求解算法的复杂度与样本维度(等于权值$\boldsymbol{\omega}$的维度)有关,而在对偶问题下,求解算法的复杂度与样本数量(等于拉格朗日算子a的数量)有关。从推到的最后结果来看,我们是消除了$\boldsymbol{\omega}$,并将优化函数变为了关于拉格朗日乘子的二次规划问题。

好了,总该说说怎么求这个二次规划问题吧?

周志华《机器学习》中提到了一个高效的算法——SMO(Sequential Minimal Optimization)。还在学习中(→_→).......

一边学看周志华的这本《机器学习》里“显然”就给出的公式,一边还要复习高数。。。尤其是SVM这章,就恨没把高数书带回家(ノへ ̄、)

参考:
安东的技术博客
维基百科
oYabea-机器学习(三)—支持向量机(1)
周志华《机器学习》

目录
相关文章
|
2月前
|
机器学习/深度学习 数据采集 算法
深入了解机器学习:从入门到应用
【10月更文挑战第6天】深入了解机器学习:从入门到应用
|
18天前
|
机器学习/深度学习 数据采集
机器学习入门——使用Scikit-Learn构建分类器
机器学习入门——使用Scikit-Learn构建分类器
|
18天前
|
机器学习/深度学习 数据采集 算法
机器学习在医疗诊断中的前沿应用,包括神经网络、决策树和支持向量机等方法,及其在医学影像、疾病预测和基因数据分析中的具体应用
医疗诊断是医学的核心,其准确性和效率至关重要。本文探讨了机器学习在医疗诊断中的前沿应用,包括神经网络、决策树和支持向量机等方法,及其在医学影像、疾病预测和基因数据分析中的具体应用。文章还讨论了Python在构建机器学习模型中的作用,面临的挑战及应对策略,并展望了未来的发展趋势。
54 1
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
探索AI的奥秘:机器学习入门指南
【10月更文挑战第30天】本篇文章是一份初学者友好的机器学习入门指南,旨在帮助读者理解并开始实践机器学习。我们将介绍机器学习的基本概念,包括监督学习、无监督学习和强化学习等。我们还将提供一些实用的代码示例,以帮助读者更好地理解和应用这些概念。无论你是编程新手,还是有一定经验的开发者,这篇文章都将为你提供一个清晰的机器学习入门路径。
37 2
|
1月前
|
机器学习/深度学习 人工智能 算法
机器学习基础:使用Python和Scikit-learn入门
机器学习基础:使用Python和Scikit-learn入门
34 1
|
21天前
|
机器学习/深度学习 数据采集 人工智能
机器学习入门:Python与scikit-learn实战
机器学习入门:Python与scikit-learn实战
34 0
|
23天前
|
机器学习/深度学习 算法 Python
机器学习入门:理解并实现K-近邻算法
机器学习入门:理解并实现K-近邻算法
31 0
|
2月前
|
机器学习/深度学习 人工智能 算法
机器学习基础:使用Python和Scikit-learn入门
【10月更文挑战第12天】本文介绍了如何使用Python和Scikit-learn进行机器学习的基础知识和入门实践。首先概述了机器学习的基本概念,包括监督学习、无监督学习和强化学习。接着详细讲解了Python和Scikit-learn的安装、数据处理、模型训练和评估等步骤,并提供了代码示例。通过本文,读者可以掌握机器学习的基本流程,并为深入学习打下坚实基础。
24 1
|
2月前
|
机器学习/深度学习 人工智能 算法
机器学习基础:使用Python和Scikit-learn入门
本文介绍了如何使用Python和Scikit-learn进行机器学习的基础知识和实践。首先概述了机器学习的基本概念,包括监督学习、无监督学习和强化学习。接着详细讲解了Python和Scikit-learn的安装、数据处理、模型选择与训练、模型评估及交叉验证等关键步骤。通过本文,初学者可以快速上手并掌握机器学习的基本技能。
64 2
|
2月前
|
机器学习/深度学习 人工智能 数据挖掘
机器学习基础:使用Python和Scikit-learn入门
【10月更文挑战第6天】在人工智能领域,机器学习已成为核心技术。本文指导初学者使用Python与Scikit-learn入门机器学习,涵盖基本概念、环境搭建、数据处理、模型训练及评估等环节。Python因简洁性及其生态系统成为首选语言,而Scikit-learn则提供了丰富工具,简化数据挖掘与分析流程。通过实践示例,帮助读者快速掌握基础知识,为进一步深入研究奠定坚实基础。
32 4