内容简介：本篇博客主要详细介绍两种具有一定相似性的机器学习算法——感知机Perceptron和支持向量机SVM，该两种算法都是在特征空间中寻找划分平面从而对数据集进行划分的思想，但寻找划分平面的算法不同。划分平面的定义也有差距。本篇博客主要叙述思路为算法模型，代价函数，学习算法，最后的算法模型使用实例介绍。这两种机器学习的算法的实例都是基于一般来说，对于一个机器学习算法的理解，主要是从三个方面入手理解，算法模型(假设函数)，代价函数的定义，学习算法(求解算法模型中的参数的算法)。感知机是一个二类分类的
本篇博客主要详细介绍两种具有一定相似性的机器学习算法——感知机Perceptron和支持向量机SVM，该两种算法都是在特征空间中寻找划分平面从而对数据集进行划分的思想，但寻找划分平面的算法不同。划分平面的定义也有差距。本篇博客主要叙述思路为算法模型，代价函数，学习算法，最后的算法模型使用实例介绍。这两种机器学习的算法的实例都是基于 Titanic数据集 ,关于数据集的特征工程部分就不具体介绍，笔者在其他博文中已经详细描述了,此篇博客将直接使用已经经过特征工程处理后的数据集进行模型训练。
一般来说，对于一个机器学习算法的理解，主要是从三个方面入手理解，算法模型(假设函数)，代价函数的定义，学习算法(求解算法模型中的参数的算法)。
2感知机
2.1感知机介绍
感知机是一个二类分类的 线性分类模型 ，作为一个算法模型，它的输入是样本的特征向量，输出是样本的类别，分别为 -1和1 两个值。如果label是1,0的情况，可以对输出的-1,1进行相应的转换。
2.2感知机算法模型
了解感知机模型之前，先得知道什么是 数据集的线性可分 。简单的说，就是在特征空间(维度是由各个特征组成的空间)中,存在某个 超平面S 能够将数据集中的正例和负例 完全正确 的划分到超平面的两边。则称该数据集的可以进行线性划分。————此处的S是线性超平面。
用数学的解释来说就是，特征空间中的样本集将被超平面w*x i +b进行划分，当超平面>0，是属于y i 为1的样本，当超平面<0，是属于y i 为-1的样本。
于是可以定义出 感知机的算法模型 为如下：
2.3代价函数
代价函数主要来自于算法模型预测样本时的预测值和样本真实值直接的差距，感知机的损失函数定义为样本集中误分类点到超平面的距离。 这样定义的原因为 如果定义为误分类点的个数时，使用梯度下降算法更新参数时，需要对各个参数求偏导，定义为个数时，不可导。所以转而将代价函数定义为为样本集中误分类点到超平面的距离。这里可以联想到Adaboost的加法模型的代价函数，代价函数是分类误差率，而后对其代价函数的值上限进行了转换为指数函数具体查看前篇博客。
2.3.1感知机的代价函数的由来
x i +b的距离为(其中||W||为w的L2范式,即w中各个元素的平方和再开方)：
2.3.2误分类点(x i ,y i )的特性
可以推出该误分类点到超平面的距离为(注意|y i |=1,所以下面计算距离的公式有y i 不影响最后的距离值)：
进而可以得出总的样本集合中所有的误分类点的总距离为(其中 M 属于总的样本集合中所有的误分类点集合)：
李航的<<统计学习方法>>中代价函数没有考虑1/||w||,从而将上式进行了化简：
能这样化简的原因(个人理解)：
在使用梯度下降更新参数w时，每一步迭代过程中1/||w||是相同的，都是大于0的正数。在每一步迭代更新参数过程中，由于1/||w||是相同的，所以可以通过比较-y i (w x i +b)来比较误分类点到超平面的距离，也就是说能通过误分类点的-y i (w x i +b)值评价代价的大小。
2.4学习算法
机器学习算法模型的学习算法的目的就是求解出模型中的参数w,b.感知机使用的是梯度下降算法来求解参数。通过极小化代价函数来求解出参数。
这里使用的是 随机梯度下降算法 ，其中误分类集中的点可以通过误分类点的特性来判断。 随机 拿取出误分类点来更新参数。
具体梯度下降算法的每一步参数更新为如下：
2.5学习算法的收敛性
需要证明的是，对于线性可分数据集感知机学习算法原始形式收敛，即经过有限次的梯度下降法的迭代可以得到一个将训练数据集完全正确的划分的超平面S。
证明的方法和重点，这里不具体证明。
1.实现需要定义出K的值，即假设已经计算好前k-1次的迭代，于是可以得出第K步迭代的相应公式。
2.抓住误分类点的特性y i (w x i +b)<0的，当得到超平面的时候，所有的点都是y i (w x i +b)>=0的存在。
2.6基于感知机的Titanic数据集预测实例
def train(self,train_X,train_y):
feature_size = train_X.shape[1]
sample_size = train_X.shape[0]
# 初始化w,b参数
self.w = np.zeros((feature_size,1))
self.b = 0
update_count = 0
correct_count = 0
while True:
if correct_count > self.nochange_count_limit:
break
# 随机选取一个误分类点
sample_select_index = random.randint(0,sample_size-1)
sample = train_X[[sample_select_index]]
sample_y = train_y[sample_select_index]
# 将labe分类为0，1转换为-1，1，其中0对应-1，1对应着1
y_i = -1
if sample_y == 1:
y_i = 1
# 计算该样本的distance距离yi(xi*w)+b
distance = - (np.dot(sample,self.w)[0][0] + self.b) * y_i
if distance >= 0:
# 挑选出误分类点，更新w,b
correct_count = 0;
sample = np.reshape(sample,(feature_size,1))
add_w = self.alpha * y_i * sample
self.w = self.w + add_w
self.b += (self.alpha * y_i)
update_count += 1
if update_count > self.updata_count_total:
break;
else:
correct_count = correct_count + 1
3支持向量机SVM
支持向量机也是在特征空间中寻找一个划分样本实例类别的超平面，这点和感知机相似，但是不同的是，支持向量机支持在特征空间中寻找出非线性的平面(非线性支持向量机).支持向量机寻找出的超平面唯一且最优，而感知机是根据误分类点定义出的代价函数求得的超平面不唯一，包含多个。
3.1支持向量机的类型介绍
支持向量机是一种二类分类模型，该算法的基本模型是在特征空间中寻找出一个最优的分隔超平面，使得样本集实例按照类别分开。由于数据集是有线性可分和不可分性质的，所以可将寻找最优分割平面的支持向量机算法分为3种类型，当数据集线性可分(能找到超平面将数据集完全按类别划分开)时，有 线性可分支持向量机 。当数据集近似线性可分(能找到超平面将大部分数据集按类别划分开)，有 线性支持向量机 。当数据集线性不可分的时候，有 非线性支持向量机 。
那么， 如何定义划分的最优超平面？ 这个疑问将在后续的过程中一一解开。
3.2线性可分支持向量机
给出一个在特征空间(二维)中的样本数据集的示例，如下图：
说明，图中 p 是划分数据集的一个超平面,d 2 =d 3 ,d 3 不一定等于d 1 . A 表示X类别实例在特征空间中到超平面 P 距离最近的一个样本实例点。同理 B 和 C 表示O类别在特征空间中到超平面 P 距离最近的一个样本实例.
对于 线性可分支持向量机 来说，图中数据集是线性可分的， p 是划分的一个超平面，但不一定是最优的，这样的超平面通过迭代算法可以查找到很多个(感知机模型)，感知机模型这样找出的超平面泛化能力不强，如果能找到一个最优超平面将提供模型的泛化能力。线性可划分支持向量机的做法是通过移动超平面 P 使得d 3 =d 1 ，此时的 P 将是最优超平面。那么特征空间中的样本点 A、B、C 将会是对最优超平面起决定性作用,这些样本实例点称为 支持向量 。
—》》 那么具体的如何寻找这个最优超平面呢，还是需要通过优化算法模型的代价函数来求解。
3.2.1代价函数的由来
首先，特征空间中样本实例到超平面wx i +b的 距离 为如下图:(其中||W||为w的L2范式,即w中各个元素的平方和再开方)：
然后，要在众多可以正确划分数据集实例类别的超平面之中找到一个最优超平面P，需要先找到上面所说的 支持向量 A、B、C 。寻找 支持向量 的数学表达为：
其次，上面我们已经表明过最优超平面是使得d 3 =d 1 ，寻找支持向量的过程中是找到离超平面最近的点，假设是A样本点，则此时最小的距离是d 1 ,要使得d 3 =d 1 ，则需要把d 1 极大化，此时便能求出参数W，b。数学公式为：
问题来了，是需要在众多可以正确划分数据集实例类别的超平面之中找到一个最优超平面P，怎么获取和保证是可以正确划分数据集实例类别的超平面呢？？？怎么保证寻找的支持向量的样本点到超平面的距离是所有样本中的最小呢？
感知机模型中判断是否是误分类点是通过y i (w x i +b)<0来判断的。正确分类的样本点满足y i (w x i +b)>=0.
为了解决上述问题，需要满足的数学公式为：
最后，在满足上面问题的条件后，需要做的就是移动超平面使的 距离最小的支持向量样本点 到超平面P’的距离d 1 最大。
最后的数学公式为：
最后的数学公式也就是线性可分支持向量机的 代价函数 。 说明部分， 上面的代价函数的推导过程是根据最初的最优超平面的定义来的。
接下来就是对代价函数(上面的数学公式进行 化简 )：
最后的再进行优化变换为：
说明
第7步可能会有疑问——为什么函数距离可以取1，第5步中的w,b是经过伸缩变化后的不等式和等式两边进行约分的，化简后的第8步中的w,b是第5步中伸缩变化后的w,b.也就是经过了我们的第6步变化。
第9步也可能会有疑问，为什么优化变化成二次的||W||,主要是为了构造成一个凸二次规划问题。更容易求解出极值,从而求解出参数w,b.
3.2.2学习算法
主要是求解代价函数中的参数w,b的过程。最终我们的代价函数经过一些数学变化成凸二次规划问题。φ(x i )为xi的一个映射函数。此时φ(x i )=x i .
上面这个优化问题中，自变量是w，而目标函数是w的二次函数，共有N(样本总数量)个约束条件，每个约束条件都是线性函数，并且它的可行域是一个凸集，所以该优化问题是一个 凸二次规划问题 。
为了求解上面的 凸二次规划问题 ，需要使用到高等数学中的 拉格朗日函数和KTT条件优化公式 ：
3.2.2.1高等数学知识——拉格朗日函数及对偶性
为了把凸优化的问题变得易于处理，需要把目标函数和约束全部融入一个新的函数，即 拉格朗日函数 。再通过这个函数来寻找最优点。
1.一般的有(包含目标函数和约束条件(此时的约束为多个等式约束条件))：
转换为一个自变量为W和β i 的 拉格朗日函数L ，其中β i 为 拉格朗日算子 ：
然后分别对w和β i 求偏导，使得偏导数等于0，然后解出w和β i 。
为什么可以求出极值可参考图：
2.其次还有(包含目标函数和约束条件(此时的约束为不等式约束和等式约束))：
同样可以转换为一个函数表达式，但函数最终的最优值需要满足如下 KTT条件 ：
KTT条件如下：
解释获取极值图：
将带约束的原函数进行对偶性转换过程如下：
3.2.2.2代价函数的拉格朗日对偶转换及参数求解
在理解上述凸优化数学知识后，便可对SVM的数学代价函数进行参数求解。还有对该部分数学不理解的可以查看下面的 参考链接 。
满足不等式的拉格朗日函数为：
将带约束的原函数进行对偶性转换：
原始问题：
对偶问题：
接下来就是对对偶问题的求解：主要有两步第一步先求L(W,b,α)对w,b的极小，第二步再求α的极大值。
第一步L(W,b,α)对w,b的极小将L对w,b求偏导并令其等于0得，称为 结果1 ：
第二步再求α的极大值，将 结果1 代入L(W,b,α)中：
第二步的结果为(在要求的式子上取反就相当于求极小了)：
此时便可以用只含有等式的拉格朗日函数求解出最优值 α ,将 α 的值结合KTT条件，求出w,b：
3.3线性支持向量机
如果数据集本身线性不可分(但近似线性可分？)这个时候应该怎么解决分类问题呢？———— 线性支持向量机
3.3.1代价函数的由来
我们知道 线性可分支持向量机的凸优化问题为 ：
线性支持向量机针对的是数据集不可划分问题(近似可划分)。这里的显示不可划分是指数据集中存在某些样本点不能满足线性可分支持向量机的约束条件：
为了使造成数据集不可划分的样本点也满足约束条件(这样的目的 是让整个数据集又重新可以线性划分 )，给每个样本点(x i ,y i )引入一个松弛变量ξ i >=0.如此一来，可以容忍部分样本点的函数间隔是负数即错误分类了，或者部分样本点能落在最大间隔区间。
由于对每个样本都在函数间隔上添加了松弛变量ξ i ，需要支付一个代价ξ i 。线性支持向量机目标函数就变为：
最终加上约束条件， 最终的代价函数 为：
3.3.2学习算法
线性支持向量机的代价函数和线性可分支持向量机的代价函数都是凸二次规划问题，都需要使用拉格朗日函数及其对偶函数来求解参数。先将目标原函数和约束条件转换为 拉格朗日函数 (其中α和μ大于等于0)：
此处根据拉格朗日函数的对偶性转换(拉格朗日对偶函数对拉格朗日乘子极大值和原目标函数的关系，线性可分支持向量机那节中有说明)有：
步骤1：求解对参数w,b,ξ的极小，求解的最后值称为 结果2
步骤2：将 结果2 代入拉格朗日函数，求解代入后的值对拉格朗日乘子的极大。
对上面这个式子求极大。
再次进行化简(对上式子的极大就是求该式子的负数的极小)：
步骤3，此时可以理解为只有等式约束的优化问题，对变量求偏导等于0，再验证值是否满足 C>=α>=0 ,此处使用 SMO算法 求解，最后将α值代入 结果2 中：
3.4非线性支持向量机
前面叙述的数据集都是在当前维度的特征空间中，可以进行线性划分和近似线性划分。但是如果当前维度的特征空间无法近似划分，就是一个完全不可划分的数据集时，这时候会使用到 核函数 将当前维度的特征空间映射到高维空间，让数据集在高维空间中线性可分。
3.4.1核函数
1.此处具体分析居然核函数是怎样发挥它的作用呢？
我们的最终目标是希望 数据集线性可分 ，这样才能寻找出一个可划分的最优超平面。我们都知道，样本点数据在低维度特征空间中不可划分，但是如果将样本数据点映射到高维特征空间中，数据集将可进行线性划分。
2.映射函数
上式是线性可分支持向量机的凸优化问题的式子。其中有个φ(x i )，它是x i 的一个 映射函数 。当数据集在当前维度的特征空间中线性可分时候，φ(x i )=x i 。如果不可划分时候，此时φ(x i )将x i 样本点映射到更高的特征空间中让数据集线性可分。比如说x i =(1,2),是一个二维向量。经过φ(x i )=(1,2,4),映射到三维向量了。
3.核函数的映射方式
核函数并不是直接定义φ(x i )来将当前维度的特征空间里的样本点映射到高维度特征空间。而是采用 间接 的方式映射。
为什么采用间接的方式映射？？
我们的凸二次规划原问题的对偶问题为：
1.从上面式子来看，每次我们求极值的时候都需要计算(φ(x i )·φ(x j ))的，为了简化每次将x i 映射到φ(x i 再运算φ(x i )·φ(x j )的点乘以，我们可以直接定义K(x i ,x j )=φ(x i )·φ(x j )的表达式，从而不定义φ(x i )，但是这之间是隐含着一个φ(x i )映射的过程的。其中K(x i ,x j )就是我们的核函数。这样一来便简化了计算过程。
2.映射函数的存在是为了便于我们了解低维度空间到高维度空间的映射的理解，其实可以通过函数K(x i ,x j )反推出映射函数φ(x i )。只是对于凸优化求极值的过程中只关注核函数的表达式。
3. 注意 ，核函数间接是可以将低维特征空间映射到无穷维特征空间，具体证明需要使用到泰勒展开式。
4.常用的核函数
3.4.2学习过程
求解原问题的对偶问题时，我们需要选取核函数，根据情况来选取核函数，当我们不知道先验知识的时候，优先选用高斯核函数。选取好后，我们便可以将(x i ,x j )代入到核函数，从而求解出凸优化的极值点。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 支持向量机（一）：支持向量机的分类思想
- 算法工程师的数学基础：线性代数中的向量和向量空间
- 庖丁解LevelDB之整体感知
- 态势感知之Malware Callback
- 统计学习方法-感知机笔记
- Istio 负载均衡的区域感知
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
勇敢新世界‧互聯網罪與罰
許煜、劉細良 / CUP / 2005 / $48
我天天上網數小時，為的是要在節目裡面介紹世界的最新動態，尤其是網絡這個世界本身日新月異的變化。所以我不可能不注意到BT、共享軟件、 Wikipedia、網絡監管等各種影響政治、社會、經濟及文化的重要網絡現象。但是我發現市面上一直沒有一本內容充實全面，資料切時的中文參考書，直到這本《互聯網罪與罰》。而且，最大的驚喜是它易讀好看，簡直就像故事書。 梁文道 鳳凰衛視 《網羅天下......一起来看看 《勇敢新世界‧互聯網罪與罰》 这本书的介绍吧!
