vlambda博客
学习文章列表

  今天趁着 高走减仓了  只剩下 30%仓位  并且接下来 不大跌  不加仓 

 

    昨天选的股  表现一般  今天抛了一大半   以后还是老老实实买etf吧 这是我自选的可融ETF  

        有写过常用机器学习算法的原理简介。一直没写过数学推导过程。

在这详细的学习SVM一下。 （间隔）（对偶）（核技巧）

1.1 简介

SVM是什么? 先来看下SVM的定义:

    支持向量机（英语：support vector machine，常简称为SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

     维基的这一大段解释肯定会让你一头雾水。简单点讲，SVM就是一种二类分类模型，他的基本模型是的定义在特征空间上的间隔最大的线性分类器，SVM的学习策略就是间隔最大化。

1.2 直观理解 ：下面来看几个图

    

        最后这张图中 ，有两类二维数据点和三条直线。如果三条直线分别代表三个分类器的话，请问哪一条线比较好？

        我们凭直观感受应该觉得答案是红线H3，

        H1不能把类别分开，最差，

        H2可以分开，但分割线与最近的数据点只有很小的间隔，如果测试数据有一些噪声的话可能就会被H2错误分类(即对噪声敏感、泛化能力弱)。

        H3以较大间隔将它们分开，这样就能容忍测试数据的一些噪声而正确分类，是一个泛化能力不错的分类器。

 

        这只是二维问题。数据点若是维向量，我们用维的超平面来分开这些点。但是可能有许多超平面可以把数据分类。最佳超平面的一个合理选择就是以最大间隔把两个类分开的超平面。因此，SVM选择能够使离超平面最近的数据点的到超平面距离最大的超平面。

    以上介绍的SVM只能解决线性可分的问题，为了解决更加复杂的问题，支持向量机学习方法有一些由简至繁的模型:

• 线性可分SVM

当训练数据线性可分时，通过硬间隔(hard margin，什么是硬、软间隔下面会讲)最大化可以学习得到一个线性分类器，即硬间隔SVM，如上图的的H3。

• 线性SVM

当训练数据不能线性可分但是可以近似线性可分时，通过软间隔(soft margin)最大化也可以学习到一个线性分类器，即软间隔SVM。

• 非线性SVM

当训练数据线性不可分时，通过使用核技巧(kernel trick)和软间隔最大化，可以学习到一个非线性SVM。

约束条件（1）

在确定点集之后，多维点到直线的距离最大化 。

  

最大化 分母小。

总结一下，间隔最大化问题的数学表达就是

支持向量的由来（即只有部分点起作用）

      在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的数据点称为支持向量(support vector)，支持向量是使中的约束条件取等的点，即满足

    的点。也即所有在直线或直线的点。如下图所示:

    在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用(具体推导见2.4节最后)。如果移动非支持向量，甚至删除非支持向量都不会对最优超平面产生任何影响。也即支持向量对模型起着决定性的作用，这也是“支持向量机”名称的由来。

三、有约束最优化问题的数学模型

如何求解式上数学公式呢？ 

        因为有约束问题 不能直接求偏导   所以转换为无约束问题

 （1）可以应用拉格朗日乘子法构造拉格朗日函数(Lagrange function)

 （2）再通过求解其对偶问题(dual problem)得到原始问题的最优解。

转换为对偶问题来求解的原因是:

• 对偶问题更易求解，由下文知对偶问题只需优化一个变量且约束条件更简单；

• 能更加自然地引入核函数，进而推广到非线性问题。

一 ：构造拉格朗日函数：注意是

            根据拉格朗日对偶性，所述问题即原始问题的对偶问题是:

           为了求得对偶问题的解，需要先求得对和的极小再求对的极大。

    （1）   求: 对拉格朗日函数求导并令导数为0，有:

将上面两式代入：

所以得到

（2）求对a的极大:

    等价于式对求极大，也等价于式取负数后对求极小，即

在满足Slater定理的时候，且过程满足KKT条件的时候。

    KKT条件，即

所以至少存在一个, 使, 即可求得最优:

    

          因为, 所以SVM的解中的求和项中第项就为0，所以SVM的解、可简化为如下形式:类似的，判别函数也可转换成如下形式:       整个SVM的解只与支持向量SV有关，与非支持向量无关。这也就解释了2.3节的结论，即在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用。

    3.     软间隔

    在前面的讨论中，我们一直假定训练数据是严格线性可分的，即存在一个超平面能完全将两类数据分开。但是现实任务这个假设往往不成立，例如下图所示的数据。

        因此，我们放宽对样本的要求，允许少量样本分类错误。这样的想法就意味着对目标函数的改变，之前推导的目标函数里不允许任何错误，并且让间隔最大，现在给之前的目标函数加上一个误差，就相当于允许原先的目标出错，引入松弛变量 ，公式变为：

       那么这个松弛变量怎么计算呢，最开始试图用0，1损失去计算，但0，1损失函数并不连续，求最值时求导的时候不好求，所以引入合页损失（hinge loss）：

函数图张这样：

理解起来就是，原先制约条件是保证所有样本分类正确，    ，现在出现错误的时候，一定是这个式子不被满足了，即 ，衡量一下错了多少呢？因为左边一定小于1，那就跟1比较，因为1是边界，所以用1减去 来衡量错误了多少，所以目标变为（正确分类的话损失为0，错误的话付出代价）：

        

        但这个代价需要一个控制的因子，引入C>0，惩罚参数，即：

       可以想象，C越大说明把错误放的越大，说明对错误的容忍度就小，反之亦然。当C无穷大时，就变成一点错误都不能容忍，即变成硬间隔。实际应用时我们要合理选取C，C越小越容易欠拟合，C越大越容易过拟合。

所以软间隔的目标函数为：

其中：

    与硬间隔类似：

    上式的拉格朗日函数为：

    在满足Slater定理的时候，且过程满足KKT条件的时候，原问题转换成对偶问题：

根据KKT条件，即

可求得整个软间隔SVM的解，即:

其中需满足。

    对于任意样本，若，此样本点不是支持向量，该样本对模型没有任何的作用；若，此样本是一个支持向量。

    若满足，进一步地，若, 由式得，即刚好，样本恰好在最大间隔边界上；若，有，此时若则该样本落在最大间隔内部，若则该样本落在最大间隔内部即被错误分类。

3.3 惩罚参数

对于不同惩罚参数，SVM结果如下图所示

4. 非线性SVM——核技巧

        为什么要引入核函数：

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。而引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。即在特征空间的内积等于它们在原始样本空间中通过核函数 K 计算的结果。一方面数据变成了高维空间中线性可分的数据，另一方面不需要求解具体的映射函数，只需要给定具体的核函数即可，这样使得求解的难度大大降低。

看看核函数的定义，

设 是输入空间 左 (欧式空间 的子集或离散集合)，又设 是特征空间 右(希尔伯特空间)，如果存在一个 到 的映射 使得对所有 ，函数 满足条件 则称 为核函数， 为映射函数，式中 为 和 的內积。

       当我们想把X从低维映射到高维的时候（让数据变得线性可分时），这一步计算很困难，等于说在计算时，需要先计算把X映射到高维的的ϕ(x)，再计算ϕ(x1)和ϕ(x2)的点积，这一步计算起来开销很大，难度也很大，此时引入核函数，这两步的计算便成了一步计算，即只需把两个x带入核函数，计算核函数，举个列子一目了然

    个人对核函数的理解：核函数就是一个函数，接收两个变量，这两个变量是在低维空间中的变量，而核函数求的值等于将两个低维空间中的向量映射到高维空间后的内积。

      核函数的选择 ：高斯核 线性核 多项式核  kernel

SVM的优缺点：

优点：

1. 由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。

2. 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。

3. 拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。

4. 理论基础比较完善(例如神经网络就更像一个黑盒子)。

缺点：

1. 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)

2. 只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)。

面试 常考：

1. SVM 原理

    SVM 是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。

• 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；

• 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；

• 当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

以上各种情况下的数学推到应当掌握，硬间隔最大化（几何间隔）、学习的对偶问题、软间隔最大化（引入松弛变量）、非线性支持向量机（核技巧）。

2. SVM 为什么采用间隔最大化

    当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。可以借此机会阐述一下几何间隔以及函数间隔的关系。

3. 为什么要将求解 SVM 的原始问题转换为其对偶问题

    一是对偶问题往往更易求解，当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。二是可以自然引入核函数，进而推广到非线性分类问题。

4. 为什么 SVM 要引入核函数

    当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。而引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。核函数的定义：K(x,y)=<ϕ(x),ϕ(y)>，即在特征空间的内积等于它们在原始样本空间中通过核函数 K 计算的结果。一方面数据变成了高维空间中线性可分的数据，另一方面不需要求解具体的映射函数，只需要给定具体的核函数即可，这样使得求解的难度大大降低。

5. 为什么SVM对缺失数据敏感

        这里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

6. SVM 核函数之间的区别

       一般选择线性核和高斯核，也就是线性核与 RBF 核。线性核：主要用于线性可分的情形，参数少，速度快，对于一般数据，分类效果已经很理想了。    RBF 核：主要用于线性不可分的情形，参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。如果 Feature 的数量很大，跟样本数量差不多，这时候选用线性核的 SVM。如果 Feature 的数量比较小，样本数量一般，不算大也不算小，选用高斯核的 SVM。

    以上是几个问题在面试中遇到 SVM 算法时，几乎是必问的问题，另外，大家一定要做到自己可以推导集合间隔、函数间隔以及对偶函数，并且理解对偶函数的引入对计算带来的优势。