支持向量机的介绍

1. 支持向量机的介绍

支持向量机(Support Vector Machine，SVM)是Corinna Cortes和Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。在机器学习中，支持向量机（SVM，还支持矢量网络）是与相关的学习算法有关的监督学习模型，可以分析数据，识别模式，用于分类和回归分析。

2. 支持向量机的简介

支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折中，以求获得最好的推广能力 。

3. 什么是支持向量机？

什么是支持向量机？支持向量机基本概念 
SVM算法是一种学习机制，是由Vapnik提出的旨在改善传统神经网络学习方法的理论弱点，最先从最优分类面问题提出了支持向量机网络。SVM学习算法根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的泛化能力。SVM在形式上类似于多层前向网络，而且已被应用于模式识别、回归分析、数据挖掘等方面。
支持向量机这些特点是其他学习算法(如人工神经网络)所不及的。对于分类问题，单层前向网络可解决线性分类问题，多层前向网络可解决非线性分类问题。但这些网络仅仅能够解决问题，并不能保证得到的分类器是最优的；而基于统计学习理论的支持向量机方法能够从理论上实现对不同类别间的最优分类，通过寻找最坏的向量，即支持向量，达到最好的泛化能力。
SVM总的来说可以分为线性SVM和非线性SVM两类。线性SVM是以样本间的欧氏距离大小为依据来决定划分的结构的。非线性的SVM中以卷积核函数代替内积后，相当于定义了一种广义的趾离，以这种广义距离作为划分依据。
模糊支持向量机有两种理解:一种是针对多定义样本或漏分样本进行模糊后处理;另一种是在训练过程中引入模糊因子作用。
SVM在量化投资中的应用主要是进行金融时序数列的预测。根据基于支持向量机的时间序列预测模型，先由训练样本对模型进行训练和完备，然后将时间序列数据进行预测并输出预测结果。
本章介绍的第一个案例是一种基于最小二乘法的支持向最机的复杂金融数据时间序列预测方法，大大提高了求解问题的速度和收敛精度。相比于神经网络预测方法，该方法在大批量金融数据时间序列预测的训练时间、训练次数和预测误差上都有了明显提高，对复杂金融时间序列具有较好的预测效果。
第二个案例是利用SVM进行大盘拐点判断，由于使用单一技术指标对股价反转点进行预测存在较大的误差，所以使用多个技术指标组合进行相互验证就显得特别必要。SVM由于采用了结构风险最小化原则，能够较好地解决小样本非线性和高维数问题，因此通过构造一个包含多个技术指标组合的反转点判断向最，并使用SVM对技术指标组合向量进行数据挖掘，可以得到更加准确的股价反转点预测模型。
 
支持向量机基本概念
SVM算法是一种学习机制，是由Vapnik提出的旨在改善传统神经网络学习方法的理论弱点，最先从最优分类面问题提出了支持向量机网络。
SVM学习算法根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的泛化能力。SVM在形式上类似于多层前向网络，而且己被应用于模式识别、回归分析、数据挖掘等方面。支持向量机方法能够克服多层前向网络的固有缺陷，它有以下几个优点：
(1)它是针对有限样本情况的。根据结构风险最小化原则，尽量提高学习机的泛化能力，即由有限的训练样本得到小的误差，能够保证对独立的测试集仍保持小的误差，其目标是得到现有信息下的最优解，而不仅仅是样本数趋于无穷大时的最优值。
(2)算法最终将转化成一个二次型寻优问题，从理论上说，得到的将是全局最优点。
(3)算法将实际问题通过非线性变换转换到高维的特征空间，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，这一特殊的性质能保证机器有较好的泛化能力，同时它巧妙地解决了维数灾难问题，使得其算法复杂度与样本维数无关。

4. 支持向量机原理

支持向量机方法的基本思想是：定义最优线性超平面，并把寻找最优线性超平面的算法归结为求解一个凸规划问题。进而基于Mercer核展开定理，通过非线性映射φ，把样本空间映射到一个高维乃至于无穷维的特征空间（Hilbert空间），使在特征空间中可以应用线性学习机的方法解决样本空间中的高度非线性分类和回归等问题（Nello Cristianini，2005）。简单地说就是升维和线性化。一般的升维都会带来计算的复杂化。这里自然发生的两个问题是如何求得非线性映射φ和解决算法的复杂性。SVM方法巧妙地解决了这两个难题：由于应用了核函数的展开定理，所以根本不需要知道非线性映射的显式表达式；由于是在高维特征空间中应用线性学习机的方法，所以与线性模型相比不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾”。另外，SVM是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度的定义及大数定律等，因此不同于现有的统计方法。从本质上看，它避开了从归纳到演绎的传统过程，实现了高效的从训练样本到预报样本的“转导推理”（transductive inference），大大简化了通常的分类和回归等问题。SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾”。如果说神经网络方法是对样本的所有因子加权的话，SVM方法是对只占样本集少数的支持向量样本“加权”。当预报因子与预报对象间蕴涵的复杂非线性关系尚不清楚时，基于关键样本的方法可能优于基于因子的“加权”。少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本，而且注定了该方法不但算法简单，而且具有较好的“鲁棒”性。由于有较为严格的统计学习理论做保证，应用SVM方法建立的模型具有较好的推广能力。SVM方法可以给出所建模型的推广能力的确定的界，这是目前其它任何学习方法所不具备的。
随着支持向量机理论的深入研究，出现了许多变种的支持向量机，如Sheng-wei Fe（2009）提出的两类重要的预测技术：分类和回归。其中分类问题预测要求观察值是离散的，而回归问题主要针对决策属性值是连续的情况，它通过学习训练样本集建立一个回归器，然后在条件属性给定的情况下进行预测。
支持向量机回归分为线性回归和非线性回归，其原理如下：
（1）支持向量机线性回归
设样本集为：（x1，y1），…，（xi，yi），x∈Rn，y∈R，回归函数用下列线性方程来表示：
f（x）=w·x＋b （4.14）
假设所有训练数据在ε精度下如图4.5所示无误差地用线性函数拟合，即

基坑降水工程的环境效应与评价方法


图4.5 支持向量机回归

考虑到允许误差的情况，引入松弛因子ξi，  ，则式（4.13）变为

基坑降水工程的环境效应与评价方法

其中常数C＞0，表示对超出误差ε的样本的惩罚程度，ξi，  为松弛变量的上限与下限。为此构造拉格朗日函数：

基坑降水工程的环境效应与评价方法

得到其对偶问题为：

基坑降水工程的环境效应与评价方法


基坑降水工程的环境效应与评价方法


基坑降水工程的环境效应与评价方法

可以得到回归函数为：
其中，αi，  将只有一小部分小为零，它们对应的样本就是支持向量。
（2）支持向量机非线性回归
以上讨论的是线性问题，对于非线性问题，把输入样本xi通过ψ：x→H映射到高维特征空间H（可能是无穷维）。当在特征空间中构造最优超平面时，实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数来实现的，没有必要知道ψ的形式。因为只要核函数K（xi，xj）满足Mercer条件，它就对应某一变换空间的内积即K（xi，xj）=ψ（i）·ψ（xj）。这一点提供了可能导致的“维数灾难”问题解决方法。
由线性支持向量回归可知，二次规划的拉格朗日目标函数：

基坑降水工程的环境效应与评价方法

其对偶形式：

基坑降水工程的环境效应与评价方法

可以得到回归函数为：

基坑降水工程的环境效应与评价方法

传统的拟合方法通常是在线性方程后面加高阶项。由此增加的可调参数增加了过拟合的风险。支持向量回归用核函数即能作非线性回归，达到了“升维”的目的，增加的可调参数很少，过拟合仍能控制。

5. 支持向量机原理

支持向量机原理SVM简介
支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。



SVM算法原理
SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。如下图所示，  \boldsymbol{w}\cdot x+b=0  即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。


在推导之前，先给出一些定义。假设给定一个特征空间上的训练数据集

 T=\left\{ \left( \boldsymbol{x}_1,y_1 \right) ,\left( \boldsymbol{x}_2,y_2 \right) ,...,\left( \boldsymbol{x}_N,y_N \right) \right\} 

其中， \boldsymbol{x}_i\in \mathbb{R}^n  ，  y_i\in \left\{ +1,-1 \right\} ,i=1,2,...N  ， x_i 为第  i  个特征向量，  y_i  为类标记，当它等于+1时为正例；为-1时为负例。再假设训练数据集是线性可分的。

几何间隔：对于给定的数据集  T  和超平面 w\cdot x+b=0 ，定义超平面关于样本点  \left( x_i,y_i \right)  的几何间隔为

 \gamma _i=y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right) 

超平面关于所有样本点的几何间隔的最小值为

 \gamma =\underset{i=1,2...,N}{\min}\gamma _i 

实际上这个距离就是我们所谓的支持向量到超平面的距离。

根据以上定义，SVM模型的求解最大分割超平面问题可以表示为以下约束最优化问题

 \underset{\boldsymbol{w,}b}{\max}\ \gamma 

 s.t.\ \ \ y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert} \right) \ge \gamma \ ,i=1,2,...,N 

将约束条件两边同时除以  \gamma  ，得到

 y_i\left( \frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}\cdot \boldsymbol{x}_{\boldsymbol{i}}+\frac{b}{\lVert \boldsymbol{w} \rVert \gamma} \right) \ge 1 

因为  \lVert \boldsymbol{w} \rVert \text{，}\gamma  都是标量，所以为了表达式简洁起见，令

\boldsymbol{w}=\frac{\boldsymbol{w}}{\lVert \boldsymbol{w} \rVert \gamma}

b=\frac{b}{\lVert \boldsymbol{w} \rVert \gamma} 

得到

y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N

又因为最大化  \gamma  ，等价于最大化  \frac{1}{\lVert \boldsymbol{w} \rVert} ，也就等价于最小化  \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2  （ \frac{1}{2} 是为了后面求导以后形式简洁，不影响结果），因此SVM模型的求解最大分割超平面问题又可以表示为以下约束最优化问题

 \underset{\boldsymbol{w,}b}{\min}\ \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2 

 s.t.\ \ y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1,\ i=1,2,...,N 

这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。

首先，我们将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数

L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\lVert \boldsymbol{w} \rVert ^2-\sum_{i=1}^N{\alpha _i\left( y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right)} 

其中  \alpha _i  为拉格朗日乘子，且  \alpha _i\ge 0  。现在我们令

 \theta \left( \boldsymbol{w} \right) =\underset{\alpha _{_i}\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) 

当样本点不满足约束条件时，即在可行解区域外：

 y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) <1 

此时，将 \alpha _i  设置为无穷大，则  \theta \left( \boldsymbol{w} \right)  也为无穷大。

当满本点满足约束条件时，即在可行解区域内：

y_i\left( \boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) \ge 1 

此时，  \theta \left( \boldsymbol{w} \right)  为原函数本身。于是，将两种情况合并起来就可以得到我们新的目标函数

 \theta \left( \boldsymbol{w} \right) =\begin{cases} \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2\ ,\boldsymbol{x}\in \text{可行区域}\\ +\infty \ \ \ \ \ ,\boldsymbol{x}\in \text{不可行区域}\\ \end{cases} 

于是原约束问题就等价于

 \underset{\boldsymbol{w,}b}{\min}\ \theta \left( \boldsymbol{w} \right) =\underset{\boldsymbol{w,}b}{\min}\underset{\alpha _i\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =p^* 

看一下我们的新目标函数，先求最大值，再求最小值。这样的话，我们首先就要面对带有需要求解的参数  \boldsymbol{w}  和  b 的方程，而  \alpha _i 又是不等式约束，这个求解过程不好做。所以，我们需要使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了：

 \underset{\alpha _i\ge 0}{\max}\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =d^* 

要有  p^*=d^*  ，需要满足两个条件：

① 优化问题是凸优化问题

② 满足KKT条件

首先，本优化问题显然是一个凸优化问题，所以条件一满足，而要满足条件二，即要求

 \begin{cases} \alpha _i\ge 0\\ y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1\ge 0\\ \alpha _i\left( y_i\left( \boldsymbol{w}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) -1 \right) =0\\ \end{cases} 

为了得到求解对偶问题的具体形式，令  L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right)  对  \boldsymbol{w} 和  b  的偏导为0，可得

\boldsymbol{w}=\sum_{i=1}^N{\alpha _iy_i\boldsymbol{x}_{\boldsymbol{i}}} 

\sum_{i=1}^N{\alpha _iy_i}=0 

将以上两个等式带入拉格朗日目标函数，消去  \boldsymbol{w} 和  b  ， 得

 L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}-\sum_{i=1}^N{\alpha _iy_i\left( \left( \sum_{j=1}^N{\alpha _jy_j\boldsymbol{x}_{\boldsymbol{j}}} \right) \cdot \boldsymbol{x}_{\boldsymbol{i}}+b \right) +}\sum_{i=1}^N{\alpha _i} 

\ \ \ \ \ \ \ \ \ \ \ =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\alpha _jy_iy_j\left( \boldsymbol{x}_{\boldsymbol{i}}\cdot \boldsymbol{x}_{\boldsymbol{j}} \right)}}+\sum_{i=1}^N{\alpha _i} 

即
\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) =-\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{\alpha _i\al

6. 支持向量机的基本原理

支持向量机的主要思想是：建立一个最优决策超平面，使得该平面两侧距离该平面最近的两类样本之间的距离最大化，从而对分类问题提供良好的泛化能力。
对于一个多维的样本集，系统随机产生一个超平面并不断移动，对样本进行分类，直到训练样本中属于不同类别的样本点正好位于该超平面的两侧，满足该条件的超平面可能有很多个，SVM正式在保证分类精度的同时，寻找到这样一个超平面，使得超平面两侧的空白区域最大化。
支持向量机中的支持向量是指训练样本集中的某些训练点，这些点最靠近分类决策面，是最难分类的数据点。SVM中最优分类标准就是这些点距离分类超平面的距离达到最大值；“机”是机器学习领域对一些算法的统称，常把算法看做一个机器，或者学习函数。
SVM是一种有监督的学习方法，主要针对小样本数据进行学习、分类和预测，类似的根据样本进行学习的方法还有决策树归纳算法等。

支持向量机的应用实例
支持向量机是一种监督模式识别和机器学习方法，采用最大分类间隔准则实现有限训练样本情况下推广能力的优化。
通过核函数间接实现非线性分类或函数回归，支持向量机通常简写作SVM。
支持向量机使用铰链损失函数计算经验风险并在求解系统中加入了正则化项以优化结构风险，是一个具有稀疏性和稳健性的分类器。
支持向量机可以通过核方法进行非线性分类，是常见的核学习方法之一。
支持向量机在人像识别、文本分类等模式识别问题中有得到应用。

7. 通俗易懂的解释支持向量机

 作 者： Wang Shuyang        a bachelor's degree candidate.
    导 语 ：相信有很多刚入坑机器学习的小伙伴会和我一样，感觉 SVM 是一道劝退的坎儿，而消除恐惧的最好办法就是微笑着面对它，本篇文章中我会用朴实的“人话”帮助大家迈过这道坎！
   本文成文思路如下：   1.SVM原始模型构建   2.对偶形式的推导   3.求解的方法   4.软间隔SVM及核方法   5.SVM优缺点及应用
   首先，让我们来对SVM产生一个直观的认识： 支持向量机(Support Vector Machine,SVM) ，二类分类器，它最终能告诉你一个东西是属于A还是属于B。在由样本点构成的向量空间内，SVM通过找到一个可以将两类数据正确分隔在两侧的划分超平面，达到对数据分类及预测的效果。而这个超平面是通过支持向量确定的，机的意思呢就是算法，故支持向量机就是通过支持向量确定划分超平面，从而做到分类及预测的算法。
                                           SVM由线性分类开始，所以我们首先来了解一下什么是线性可分。简单来说，在二维空间上，两类点能够被一条 直线 完全分开则叫做线性可分。如下图左边是线性不可分的，而右边即为线性可分。
                                           数学上我们可以表述为：对于 n 维欧氏空间中的两个点集  和  ，若存在 n 维向量    和实数   ，使得：   满足   ，而    满足   ，则称  和  线性可分。
   给定线性可分的训练样本集  ,  ，线性分类器将基于训练样本  在二维空间中找到一个超平面来正确划分两类样本。显然，满足条件的超平面有很多，而我们旨在找到鲁棒性最好的。
   首先，我们要明确该模型中 “距离” 的概念。由于划分超平面并不确定，所以我们需要比较同一个点到不同超平面的距离，为了使之具有可比性，我们使用 欧式几何距离 。
   相信大家不陌生的是，一个二维空间点  到直线  的距离公式为：  
   而扩展到 n 维空间后，点  到超平面  的距离公式为：  ,其中  
   既然我们要找出与两类数据间隔最大的划分超平面，很直观地就会考虑从两类数据最靠近的地方下手，因为它们各自最边缘位置的点才有可能成为最靠近划分超平面的那几个点，而其他点对确定超平面的最终位置是起不了作用的，所以我们认为是这些边缘点支持了超平面的确立。而在数学里点又可以叫向量，比如二维点 (x, y) 就可以看成是一个二维向量，同理 n 维点就是一个 n 维向量，所以我们将这些有用的边缘点称为 “支持向量”(support vector) 。
                                           如图2所示，标红的点就是支持向量，它们确定出了两条虚线，我们称之为 “支撑超平面” ，并将它们之间的距离称为 “间隔”(margin) ，用希腊字母    表示，而它们“正中间”的位置就是我们要找的最优划分超平面的位置。显然， 间隔 越大我们的划分超平面鲁棒性就越好。所以在开始推导SVM的原始公式之前，请在脑海里跟我默念三遍SVM的核心思想 ——  “ 最大化间隔！” 
   假设超平面  能将训练样本  正确分类，那么任一数据点  到该超平面的距离为：  显然  ，否则超平面变为  ，失去意义。
   考虑到此式中含有绝对值会对后续数学计算带来不便，所以我们利用数据点自带的标签  去绝对值。结合1.1.1中讲过的线性可分的数学定义可知：     
   所以任一数据点到超平面的距离可表示为：  则最接近超平面的距离为：  调整平面位置，找到最大距离：  则最大间隔为：  至此，我们已经将问题用数学语言表述出来了，即要找到一组使得    最大的  确立最优划分超平面，但形式上任较为复杂。
   我们知道，对于二维空间中的一条直线  ，等比例地放缩  是不影响它的位置的，比如  仍代表同一条直线。
   扩展到 n 维空间中，等比例地放缩  也是不影响解平面  位置的。又已知   （超平面外一点与之距离大于  得出），所以我们不妨令   表达式中的  ，则问题简化为，求：     显然，最大化  等价于最小化  ，为了便于求导，我们继续将问题转化为，求：     至此，我们便得到了SVM的基本型。
   介绍了这么多，但构建出来的模型到底能不能用呢？接下来，我们就从理论上验证它的可行性。
    定理 ：若训练数据集  线性可分，则可将  中的样本点完全正确分开的最大间隔划分超平面 存在且唯一 。
    证明 ：    (1)存在性    由于训练数据集线性可分，又目标函数存在下界，所以必存在最优解，由此得知最大间隔划分超平面的存在性。    (2)唯一性    首先证明最优解中  的唯一性。假设存在两个最优解  和  ，由目标函数的形式可知必有  ，其中  是一个常数。令  ，则  必然也是一个可行解，试想两个可正确划分样本点的超平面中间夹的一个超平面必然也可以正确划分样本点。但由于  不一定是最优解，则有  (中间那个“  ”关系由 “三角形两边之和大于第三边” 拓展到 n 维得到)。   由上式可得，  ，从而有  ，  （想象若强行令三角形两边之和等于第三边，则三条线段将会共线）。若  ,则  ，与  是可行解相矛盾；因此必有  ，则  ，  的唯一性得证。   接下来证明  的唯一性。假设存在两个最优解  和  ，不妨设  和  对应的  值都为  ，且它们分别是两个最优解的 支撑超平面 上的点，满足与自己对应的划分超平面距离为  ，即满足   同时与另一个划分超平面距离大于等于  ，即  整理得出  所以  带入第一对等式方程即可得  ，则  的唯一性得证。   至此，我们得知SVM基本型的最优解存在且唯一。
    线性可分支持向量机——最大间隔法（maximum margin method） 
    输入 ：线性可分训练数据集  ,         其中  ,  ,  ；    输出 ：最大间隔划分超平面和分类决策函数；
   （1）构造并求解约束最优化问题：         求得最优解  ;   （2）由此得到划分超平面：      分类决策函数：  
   首先顺带一提，上面的基本型是一个凸二次规划问题，可以直接用现成的优化计算包求解。但若利用“对偶问题”来求解会更高效，所以我们来推导SVM的对偶形式。
   拉格朗日函数是  拉格朗日乘子法  的核心组成部分，此法思想为：将 有约束 优化问题从形式上转化为等价的 无约束 优化问题。（建议对此法陌生的同学进去看看图文并茂的讲解）
   优化问题存在很多形式，比如目标函数有求最大值的，也有求最小值的；约束条件有用大于式表示的，也有用小于式的。而上面说到凸优化问题具有 “局部最优值必定是全局最优值” 这一良好性质，所以我们可以通过移项将SVM基本型写成凸优化问题的标准形式：  SVM原始形式：  只含有不等式约束，将其改写成：  则其拉格朗日函数为：  接下来到了关键的一步，所以我们需要再明确一遍，将问题改写成拉格朗日函数仅仅只是从形式上改变它，而实质上必须是等价的。那么接下来我要说明以下两个问题是等价的：   ① 求  ，在   这个条件下；   ② 求  ，在   这个条件下；
   从问题②入手，当它满足自身约束条件时，拉格朗日函数  表达式中的累加项内容为非负常数    和    的乘积，那么欲求其最大值必须满足   ，否则调整    可以达到无穷大，失去意义，所以我们发现问题②是自带问题①的约束条件的（这里希望读者可以从中体会原始规定不等式约束的拉格朗日乘子  的巧妙)；   接下来我们会注意到,   作为一个非正项，其最大值就是  ，所以求  的值就是求  的值。至此，我们发现问题②是与问题①等价的。   所以我们可以将原问题做如下转变：          
   这时我们再用上凸优化问题的强对偶性，即不管局部还是全局都只有同一个最优解，可将极小极大的求解顺序换成求极大极小以便于运算：
     
   前面点开了  朗格朗日乘子法  这个链接的同学可能会发现，其中介绍的是仅含有等式约束的优化问题。实际上此法的原始形式中就只包含等式约束，而为了将其泛化到可求带有不等式约束的优化问题，我们引入 KKT条件 。
   首先来看不等式约束优化问题最简单的形式：     其对应的拉格朗日函数为：  我们利用图形来对其产生一个直观的认识：
                                           图中画出了目标函数  的等高线和约束区域  ，我们的可行解（相当于局部最优解，在凸优化中即必为最优解）需落在约束区域内，且最接近  的 “中心”，即无约束解。至于无约束解和约束区域的相对位置，有以下两种可能：
                                           此时，可行解  在  内取到无约束解，必然满足  ，相当于失去这一约束，即  中的拉格朗日乘子  取为  。
                                           此时，可行解  必然落在约束区域的边界上，即满足  。至此我们可以得到一个 重要的结论 （记为 “结论  ” ），即无论哪种情况下都有：  接着继续考虑可行解  落在边界上的位置，为了尽量靠近无约束解，直观上我们就可以看出，必然要取无约束解与约束区域中心的连线交于边界上的那一点。从函数梯度方面来考虑的话，目标函数的负梯度方向（下图中蓝色小箭头  ）应远离约束区域朝向无约束解，即我们要找到目标函数的负梯度方向与约束函数的梯度方向（  ）相同的那一点：  也即：  
                                           这里我想举一个例子帮助大家理解：假设山坡上有一只被圈养的小羊，它想去山顶看看，但不幸的是有一圈栅栏限制了它的活动范围。所以它只能沿着栅栏走到尽可能靠近山顶的位置，然后望着山顶咩咩叹气。这里的山顶便是目标函数的无约束解，栅栏便是约束函数的边界，此时羊头的朝向一定是指向山顶的，且与栅栏的梯度同向。
   回到凸优化问题的标准形式：  列出拉格朗日函数得到无约束优化问题：  结合之前的分析，我们将可行解  需满足的条件汇总，即为 “KKT条件”（Karush-Kuhn-Tucker Conditions） ：
                  ①            ②          ③           ④          ⑤
   这一组方程看似很复杂，但其实很好理解：   ①式：拉格朗日函数取得可行解的必要条件(羊爬山的例子)；   ②式：不等式约束对应的拉格朗日乘子的初始条件；   ③~④式：优化问题的初始约束条件；   ⑤式：前面得到的那个 重要“结论  ” ；
   总结一下， KKT条件 是“一个凸优化问题存在最优解”的充要条件，通过KKT条件我们即可求得凸优化问题的最优解。用数学语言表述一下就是：   若目标函数  和不等式约束  都是凸函数，而等式约束  是仿射函数（即形如  的线性函数），且不等式约束  的等号都能成立（这一条件称为 Slater条件 ），那么满足KKT条件的  点即为全局最优解。
   在引入KKT条件之前，我们已经将SVM转化成了如下形式:  其中，  我们发现，求解   是可以利用KKT条件的。
   对于 条件① ：  ，我们这里的变量为  和  ，所以有：  那么接下来我们就可以进行一波愉快的数学计算了。。。(还没学过 向量函数求导 的小伙伴们，快进来现学一下吧~)      通过这一波求偏导我们得到：   将其带入  即可得到最小值： 

8. 支持向量机是什么意思

支持向量机（SVM）是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。
通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。
具体请看：网页链接