什么是SVM

• 支持向量：在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。
• 支持向量机（Support Vector Machine，SVM）：其含义是通过支持向量运算的分类器。

支持向量机为一个二分类模型,它的基本模型定义为特征空间上的间隔最大的线性分类器。而它的学习策略为最大化分类间隔,最终可转化为凸二次规划问题求解。

SVM可以用于解决二分类或者多分类问题，此处以二分类为例。

SVM的目标是寻找一个最优化超平面在空间中分割两类数据，这个最优化超平面需要满足的条件是：离其最近的点到其的距离最大化，这些点被称为支持向量。

点到超平面距离
SVM对偶问题推导

由简至繁的模型包括：

• 当训练样本线性可分时，通过硬边界（hard margin）最大化，学习一个线性可分支持向量机；
• 当训练样本近似线性可分时，通过软边界（soft margin）最大化，学习一个线性支持向量机；
• 当训练样本线性不可分时，通过核技巧和软边界最大化，学习一个非线性支持向量机；

SVM 为什么采用间隔最大化（与感知机的区别）：

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

为何转为对偶问题

目的有两个：

• 方便核函数的引入；
• 对偶问题将原始问题中的约束转为了对偶问题中的等式约束，对偶问题往往更加容易求解。
• 原问题的求解复杂度与特征的维数相关，而转成对偶问题后只与问题的变量个数有关。

SVM有两个目标，第一个是使间隔最大化，第二个是使样本正确分类，由此推出目标函数：
w是超平面参数，目标一是从点到面的距离公式化简来的，具体不展开，目标二就相当于感知机，只是把大于等于0进行缩放变成了大于等于1，为了后面的推导方便。
上式的拉格朗日函数为：:

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

先求内部最小值，对$w$ 和 $b$ 求偏导并令其等于 0 可得：

将其代入到上式中去可得到

此时需要求解$\alpha$，利用SMO（序列最小优化）算法：
SMO算法的基本思路是每次选择两个变量${\alpha }_i$和${\alpha }_j$，选取的两个变量所对应的样本之间间隔要尽可能大，因为这样更新会带给目标函数值更大的变化。SMO算法之所以高效，是因为仅优化两个参数的过程实际上仅有一个约束条件，其中一个可由另一个表示，这样的二次规划问题具有闭式解。

SVM的变量个数为支持向量的个数。

例题

已知一个训练集，现在有正例 $x_1=(3,3{)}^T$ , $x_2=(4,3{)}^T$ ,负例 $x_3=(1,1{)}^T$ ,试求最大间隔分离超平面。
答：按照上述算法，构建训练集约束最优化问题：







=
其中(对b求导的那一项)

将

代入上式，得：

为了求 $L({\lambda }_1,{\lambda }_2)$最小值,分别对 ${\lambda }_1,{\lambda }_2$求偏导:

得到在点 $(\frac{3}{2},-1{)}^T$取极值。但因为该点不符合约束条件，所以最小值应该在边界上。
当${\lambda }_1=0$ 时，在点 $(0,\frac{2}{13}{)}^T$ 取最小值$-\frac{2}{13}$，

当${\lambda }_2=0$时，在点 $(\frac{1}{4},0{)}^T$ 取最小值 $-\frac{1}{4}$，

因此在点 $(\frac{1}{4},0{)}^T$ 取最小值，此时 ${\lambda }_1=\frac{1}{4}$ ， ${\lambda }_2=0$ ，${\lambda }_3=\frac{1}{4}$，相对应的，点 $x_1,x_3$ 为支持向量 。

最终：


因此最大间隔超平面为

软间隔

不管直接在原特征空间，还是在映射的高维空间，我们都假设样本是线性可分的。虽然理论上我们总能找到一个高维映射使数据线性可分，但在实际任务中，寻找一个合适的核函数核很困难。此外，由于数据通常有噪声存在，一味追求数据线性可分可能会使模型陷入过拟合，因此，我们放宽对样本的要求，允许少量样本分类错误。这样的想法就意味着对目标函数的改变，之前推导的目标函数里不允许任何错误，并且让间隔最大，现在给之前的目标函数加上一个误差，就相当于允许原先的目标出错，引入松弛变量 $\xi$，公式变为：
那么这个松弛变量怎么计算呢，最开始试图用0，1损失去计算，但0，1损失函数并不连续，求最值时求导的时候不好求，所以引入合页损失（hinge loss）：

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

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

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

其中：

上式的拉格朗日函数为：

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

先求内部最小值，对 $w$, $b$ 和 $\xi$ 求偏导并令其等于 0 可得：

此时需要求解$\alpha$，同样利用SMO（序列最小优化）算法。

核函数特点及其作用

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

用自己的话说就是，在SVM不论是硬间隔还是软间隔在计算过程中，都有X转置点积X，若X的维度低一点还好算，但当我们想把X从低维映射到高维的时候（让数据变得线性可分时），这一步计算很困难，等于说在计算时，需要先计算把X映射到高维的的ϕ(x)，再计算ϕ(x1)和ϕ(x2)的点积，这一步计算起来开销很大，难度也很大，此时引入核函数，这两步的计算便成了一步计算，即只需把两个x带入核函数，计算核函数

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

引入核函数目的：把原坐标系里线性不可分的数据用核函数Kernel投影到另一个空间，尽量使得数据在新的空间里线性可分

• 核函数的引入避免了“维数灾难”，大大减小了计算量。而输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入。
• 无需知道非线性变换函数Φ的形式和参数。
• 核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。
• 核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。

SVM主要特点

• SVM方法的理论基础是非线性映射，SVM利用内积核函数代替向高维空间的非线性映射。
• SVM的目标是对特征空间划分得到最优超平面，SVM方法核心是最大化分类边界。
• 支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。
• SVM是一种有坚实理论基础的新颖的适用小样本学习方法。它基本上不涉及概率测度及大数定律等，也简化了通常的分类和回归等问题。
• SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
• 少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单，而且具有较好的“鲁棒性”。这种鲁棒性主要体现在：
  ①增、删非支持向量样本对模型没有影响;
  ②支持向量样本集具有一定的鲁棒性;
  ③有些成功的应用中，SVM方法对核的选取不敏感
• SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
• SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
• SVM在小样本训练集上能够得到比其它算法好很多的结果。SVM优化目标是结构化风险最小，而不是经验风险最小，避免了过拟合问题，通过margin的概念，得到对数据分布的结构化描述，减低了对数据规模和数据分布的要求，有优秀的泛化能力。
• 它是一个凸优化问题，因此局部最优解一定是全局最优解的优点

SVM主要缺点

• SVM算法对大规模训练样本难以实施
  SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。
  如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用简单的朴素贝叶斯分类器，或者是使用逻辑回归模型分类。
• 用SVM解决多分类问题存在困难
  经典的支持向量机算法只给出了二类分类的算法，而在实际应用中，一般要解决多类的分类问题。
  可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；
  再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗糙集理论结合，形成一种优势互补的多类问题的组合分类器。
• 对缺失数据敏感，对参数和核函数的选择敏感
  支持向量机性能的优劣主要取决于核函数的选取，所以对于一个实际问题而言，如何根据实际的数据模型选择合适的核函数从而构造SVM算法。目前比较成熟的核函数及其参数的选择都是人为的，根据经验来选取的，带有一定的随意性。在不同的问题领域，核函数应当具有不同的形式和参数，所以在选取时候应该将领域知识引入进来，但是目前还没有好的方法来解决核函数的选取问题。

SVM与LR的区别?

LR是参数模型,SVM为非参数模型。
LR采用的损失函数为logisticalloss,而SVM采用的是hingeloss。
在学习分类器的时候,SVM只考虑与分类最相关的少数支持向量点。
LR的模型相对简单,在进行大规模线性分类时比较方便。
LR与SVM的区别
相同点：

1. 都是线性分类器。本质上都是求一个最佳分类超平面。
2. 都是监督学习算法。
3. 都是判别模型。通过决策函数，判别输入特征之间的差别来进行分类。
   常见的判别模型：KNN、SVM、LR
   常见的生成模型：朴素贝叶斯、隐马尔可夫模型。

不同点：
1）本质上是损失函数不同
LR的损失函数是交叉熵：

SVM的目标函数是：

逻辑回归基于概率理论，假设样本为正样本的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值。
支持向量机基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面。

2）两个模型对数据和参数的敏感程度不同
SVM考虑分类边界线附近的样本（决定分类超平面的样本）。在支持向量外添加或者减少任何样本点对分类决策面没有任何影响；
LR受所有数据点的影响。直接依赖于数据分布，每个样本点都会影响决策面的结果。如果训练数据不同类别严重不平衡，则一般需要先对数据做平衡处理，让不同类别的样本尽量平衡。

3）SVM基于距离分类，LR基于概率分类
SVM依赖数据表达的距离测度，所以需要对数据先做normalization；LR不受其影响

4）在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法
SVM中只有少数几个代表支持向量的样本参与到分类决策计算，也就是只有少数几个样本需要参与核函数的计算。
LR算法里，每个样本都必须参与分类决策的计算过程，也就是说，假设我们在LR里也运用核函数的原理，那么每个样本都必须参与核运算，这带来的计算复杂度是相当高的，尤其是数据量很大的时候，我们无法承受。所以，在具体应用时，LR很少运用核函数机制。

5）在小规模数据集上，Linear SVM要略好于LR，但差别也不是特别大，而且Linear SVM的计算复杂度受数据量限制，对海量数据LR使用更加广泛。

6）SVM的损失函数自带正则项，而LR必须另外在损失函数之外添加正则项

红框内为正则项。这就是为什么SVM是结构风险最小化算法的原因！！！LR则是经验风险最小化。而LR必须另外在损失函数上添加正则项！！！

SVM中什么时候用线性核什么时候用高斯核?

当数据的特征提取的较好,所包含的信息量足够大,很多问题是线性可分的那么可以采用线性核。若特征数较少,样本数适中,对于时间不敏感,遇到的问题是线性不可分的时候可以使用高斯核来达到更好的效果。

当样本的特征很多且维数很高时可考虑用SVM的线性核函数。当样本的数量较多,特征较少时,一般手动进行特征的组合再使用SVM的线性核函数。当样本维度不高且数量较少时,且不知道该用什么核函数时一般优先使用高斯核函数,因为高斯核函数为一种局部性较强的核函数,无论对于大样本还是小样本均有较好的性能且相对于多项式核函数有较少的参数。

核函数隐含着一个从低维空间到高维空间的映射,这个映射可以把低维空间中线性不可分的两类点变成线性可分的。

为什么样本随着维度的升高一定是线性可分的？有没有存在无穷维也不可分的情况呢？

没有，样本之间只要存在差异，也就是说只要不是相同的样本点，一定能在某种程度上对其进行区分。我们无法划分，只是维度太低观察到的信息不够。随着维度的上升，我们的信息量越来越充足，只要是有差异的样本并且找到其差异，一定能够使用该差异来划分的。

为什么大于N维也可以？会不会存在大于N维的某一维又突然线性不可分了呢？

不会，就像上一个问题一样，当你在某一维突然获取到了能够划分样本的足够多的信息后，随着维度的上升，我们得到的信息量只会越来越多，而第N维的信息量就足够我们划分了，更多的信息量并不会出现问题中的这种情况。