【概述】 SVM训练分类器的方法是寻找到超平面，使正负样本在超平面的两侧（分类正确性即“分得开”），且样本到超平面的几何间隔最大（分类确信度即“分得好”）。 每个样本点xi的几何间隔至少是γ，要求γ首先是>0（分类正确），然后尽力求γ的最大值（分得好，要γ>1）。
另外γ值是由少数在margin上的点决定的（引出支持向量的概念，名字还挺形象的！这些向量“撑”起了分界线）。
注：SVM算法的特点是巧妙地利用了很多零散的数学知识和技巧，所以要消化学习如何针对分类继续优化、追求分离平面唯一性的需求，如何构造约束最优化问题（通过构造目标函数，充分利用已有的数学计算技巧）
7.1.2 函数间隔和几何间隔
“间隔”的作用和意义：一个点距离分离超平面的远近，可以用来表示分类预测的确信程度，有以下原则：在超平面w.x+b=0确定的情况下：|w.x+b|能够相对表示点x距离超平面的远近，而w.x+b的符号与类标记的符号是否一致（例如：点在正侧，w.xi+b大于0，而yi为1，yi大于0，分类正确；点在负侧，w.xi+b小于0，yi为-1，符号一致，分类正确；反之符号不一致）。
1、函数间隔（又称函数距离）
进而引出函数间隔functional margin的概念，用函数距离y(w.x+b)来表示分类的正确性（符号，大于0表示分类正确）和确信度（距离大小）
1）分类正确性：如果y(w.x+b)>0,则认为分类正确，否则错误。
2）分类确信度：且y(w.x+b)的值越大，分类结果的确信度越大，反之亦然
定义超平面(w,b)关于训练集T的函数间隔为超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔的最小值，γ^=min(i=1,...,N)下的γ^
2、几何间隔（又称几何距离）
如上述函数间隔的概念，样本点(xi,yi)与超平面(w,b)之间的函数间隔定义为γ^=yi(w.xi+b)
但这样带来一个问题，w和b同时缩小或放大m倍，"这时超平面没有变化"，但函数间隔却变化了。所以需要将w的大小固定下来，例如||w||=1，使得函数间隔固定-->这时得出几何间隔。
几何间隔的定义如下：ri=yi(w/||w||.xi+b/||w||)
几何间隔
实际上，几何间隔就是点到超平面的距离，点(xi,yi)到直线ax+by+c=0的距离公式是
点到超平面距离
因此在二维空间，几何间隔就是点到直线的距离，在三维或以上空间中，几何间隔就是点到超平面的距离。而函数距离就是上述公式的分子，没有归一化。
注：对于yi这些标签，如果在分离超平面的负侧，yi=-1，运算时要留意
举例1：如果训练集中的点A在超平面的负侧，即yi=-1，那么点与超平面的距离为：
ri=-(w/||w||.xi+b/||w||)
定义超平面(w,b)关于样本点(xi,yi)的几何间隔一般是实例点到超平面的“带符号”的距离（signed distance），只有当样本点被超平面正确分类时，几何间隔才是“实例点到超平面的距离”。
注：以上描述的含义是，当不正确分类时得出r=yi(w/||w||.xi+b/||w||)小于0，例如yi=-1，wx+b大于0 或者 yi=1，wx+b小于0
为何关注几何间隔？
因为几何间隔与样本的误分类次数存在关系（见《统计学习方法》第二章“感知机”的证明）
误分类次数≤(2R/δ)^2，其中其中δ就是样本集合到分类超平面的距离
R=max||xi||，i=1,...,n，即R是所有样本中（xi是以向量表示的第i个样本）向量长度最长的值（即代表样本的分布有多么广）。结论是“当样本已知的情况下”，误分类次数的上界由几何间隔决定。”
为何要选择几何间隔评价“解”（系数组）是否最优的指标？
因为几何间隔越大的解，误差的上界越小。因此最大化几何间隔，就成为学习的目标。
注：必须反复强调的是，xi不是要求的变量，而是已知的样本，而要求的主要是w、a、b这些系数和算子（在这里，不要将xi当成变量，xi代表样本，是已知的（训练集中的样本已知是哪些标签分类，是用来学习的））
7.1.3 间隔最大化
1、最大间隔分离超平面（助记：找到γ，或者找到间隔最小的点，再求超平面使得γ的值最大）
SVM的基本想法是“除了分得开，更要分得好”，所以引出了“有约束”的“最优化问题”，式子如下：
argmax(w,b) γ (7.9) #最大化几何间隔γ
s.t. yi(w/||w||.xi+b/||w||)大于等于γ， (7.10) #超平面跟每个样本点的几何间隔至少是γ
这里隐含的意义：
每个样本点xi的几何间隔至少是γ，说明γ首先是>0（分类正确），然后尽力求γ的最大值（分得好），另外γ值是由少数在margin分割线上的点决定的（引出支持向量的概念）。
考虑到几何间隔和函数间隔的关系（7.8）
γ=γ^/||w|| （7.8）
【得出】
argmax(w,b) γ^/||w|| （7.11）#希望最大化超平面(w,b)对训练集T的间隔
s.t. yi(w.xi+b)≥γ^ （7.12）#要求(w,b)对每个训练样本点的间隔至少是γ
有以下几点设定：
1）最大化-->最小化：对凸函数来说，求最大值往往需要转化为求最小值，注意到“最大化1/||w||”和"最小化1/2||w||^2"是等价的
2）函数间隔γ^取“1”：函数间隔取值不影响最优化问题的解（例如将w和b按比例改为λw和λb，这时函数间隔成为λγ^）；函数间隔的这个变更对上述最优化问题的不等式约束没有影响（大于等于的关系不变）。这样，就可以取γ^=1，将γ^=1代入上面的最优化问题
经过上述设定，所以得出以下“线性可分SVM的最优化问题”：
argmin(w,b) 1/2||w||^2 (7.13)
s.t. yi(w.xi+b)-1≥0 （7.14）
算法7.1（线性可分SVM学习算法-最大间隔法）
输入：线性可分训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)},其中xi∈χ=Rn，yi∈Υ={-1,+1}，i=1,2,...,N；
输出：最大间隔分离超平面和分类决策函数
1）构造并求解约束最优化问题
argmin 1/2||w||^2
s.t. yi(w.xi+b)-1≥0,i=1,2,...,N
求得最优解w*，b*。
2)由此得到最佳分离超平面：w*.x+b*=0
由此得到分类决策函数：f(x)=sign(w*.x+b*)
2、支持向量和间隔边界
引出“支持向量”概念：支持向量是训练数据集中的样本点跟分离超平面距离最近的样本点的实例（support vector）
这种点满足几何间隔=γ-->yi(w.xi+b)=γ，因为γ取值1，即
yi(w.xi+b)-1=0
1）对于yi=+1的正例点，支持向量在超平面H1:w.x+b=1
2）对于yi=-1的负例点，支持向量在超平面H2:w.x+b=-1
由于γ^取值1，所以两个超平面的几何距离依赖于超平面H0的法向量w，即几何距离是是2/||w||，详见图7.3（支持向量），H1和H2成为间隔边界
【重要】在决定分离超平面时，只有支持向量起作用，而其他实例点不起作用。由于支持向量在确定分离超平面中起到决定性作用，所以将这种分类模型成为“支持向量机”。
习题7.1 已知一个如图7.4的训练数据集，正例点是x1=(3,3)^T，x2=(4,3)^T，负例点是x3=(1,1)^T，试求最大间隔分离超平面H0.
7.1.4 学习的对偶算法
1、带约束的线性分类器问题如下
min 1/2||w||^2 （7.13）
s.t. yi(w.xi+b)-1≥0 （7.14）
下面进行重要的推导，带约束的最小值问题如何通过拉格朗日的对偶算法来解决。那什么是拉格朗日对偶性呢？简单来讲，就是通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题。
求解SVM基本型不太方便，于是乎求解其对偶问题，对偶问题是一个不等式约束问题，求不等式约束问题采用KKT条件，KKT条件中有一个条件很有意思，就是 a*g（x）=0，要么拉格朗日乘子为0，要么g（x）=0，g（x）=0，表示样本是支持向量，也就是只有支持向量才使得g（x）=0，而a=0的样本就不需要了。
转化如下：
(7.18)
求解策略：为了得到对偶问题的解，先求L(w,b,a)对w、b的极小，再求对a的极大
1）求min(w,b)L(w,b,a)
将拉格朗日函数L(w,b,a)分别对w、b求偏导并令其等于0
▽wL(w,b,a) = w-Σaiyixi=0
▽bL(w,b,a) = - Σaiyi=0
得到
w=Σaiyixi （7.19）
Σaiyi=0 （7.20）
将(7.19)代入拉格朗日函数(7.18)，即得
L(w,b,a)
=1/2 ||w||^2 - Σaiyi(w.xi+b)+Σai
=1/2 ΣΣaiajyiyj(xi.xj)
因为这时候，L函数取最小值，所以得出
min(w,b) L(w,b,a) = -1/2 ΣΣaiajyiyj(xi.xj) + Σai
2）求min(w,b) L(w,b,a) 对 a的极大，也就是对偶问题
对偶问题 min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)=min(x)f(x)
max(a) -1/2ΣΣaiajyiyj(xi.xj) +Σai （7.21）
s.t. Σaiyi=0
将式（7.21）的目标函数由求极大值转换为求最小值，就转化为下面与之等价的对偶最优化问题（将前面的-号变成+号）
max(a) -1/2ΣΣaiajyiyj(xi.xj) + Σai
===> min(a) 1/2ΣΣaiajyiyj(xi.xj) - Σai （7.22）
s.t. Σaiyi=0 （7.23）
ai ≥0，I=1,2,...,N （7.24）
通过上述处理，原始问题求w解转化为对偶问题求a解，并引出内积 （7.22）--（7.24）
这个问题中变量是w，目标函数是w的二次函数，所有的约束条件都是w的线性函数（再次强调不要将xi看成是自变量，xi代表已知的样本），这种规划问题成为“二次规划”（Quadriatic Progamming,QP）；同时由于可行域是一个凸集，因此是一个“凸二次规划”。
定理7.2 设a*= (a1*，a2*，...，ai*)^T，是对偶最优化问题（7.22）-（7.24）的解，则存在下标j，使得aj*>0，并可按照下列式子求得原始最优化问题（7.13）-（7.14）的解w*、b*
w* = Σai*yixi （7.25）注：w*是解
b* =Σyj -Σai*yi(xi.xj) （7.26）
从7.25和7.26可知，w*和b*只依赖于训练数据中对应于a*>0的样本点(xi,yi)，而其他样本点对w*和b*没有影响，所以称“训练数据中对应于ai* > 0的实例点xi∈R”为支持向量。
证明如下：
▽wL(w,b,a) = w-Σaiyixi=0
▽bL(w,b,a) = -Σaiyi=0
得到：
w* = Σai*yixi
其中至少有一个aj不为0（aj>0），对此j有yj(w*xj+b*)-1=0 （7.28）
将(7.25) w* = Σai*yixi 代入 （7.28）得到
有yj(Σai*yixi*xj+b*) =1
=> Σai*yjyixi*xj+yj.b*=yj^2 （注：yj^2=1）
=>(两边都除以yj) yj=b*- Σai*yixi*xj
=>b*= yj - Σai*yi(xi*xj)
由此定理可知，
由于g(x)=<w.x>+b，代入w* =Σai*yixi
这里只有x才是变量，同时注意到式子中x和xi是向量，将不是向量的量从内积符号拿出来，得到g(x) 的式子为：
g(x)= Σaiyi<xi,x>+b
由此分离超平面可以写成： Σai*yi(xi*xj) + b* =0 （7.29）
分类决策函数可以写成： f(x)=sign[Σai*yi(xi*xj)+b*] （7.30） （对偶形式）
（7.29）和 （7.30）的含义：分类决策函数只依赖于输入x和训练样本输入的内积（xi.xj）也写作<xi,xj>，式（7.30）称为线性可分支持向量机的对偶形式。
注意：上述变换中，看到式子中x才是变量，也就是你要分类哪篇文档，就把该文档的向量表示代入到 x的位置，而所有的xi统统都是已知的样本。还注意到式子中只有xi和x是向量，因此一部分可以从内积符号中拿出来。
算法7.2（线性可分支持向量机学习算法）
输入：线性可分训练集T={(x1,y1),(x2,y2),...,(xN,yN)},其中xi∈χ=Rn，yi∈Υ={-1,+1}，i=1,2,...,N；
输出：分离超平面和分类决策函数
1）构造并求解约束最优化问题
min 1/2
Σ Σaiajyiyj(xi.xj) - Σai
s.t. Σaiyi=0
a ≥ 0，i=1,2,...,N
求得最优解a*=(a1,a2,...,an)^T
2）计算
w* = Σaiyixi
并选择a*的一个正分量aj*>0，计算
b*=yj-Σai*yi<xi,xj> 注：xi和xj的内积
3）求得分离超平面
w*x+b*=0
4）求得分类决策函数
f(x)=sign(w*.x+b*)
7.3 非线性支持向量机与核函数
1)引入核函数(满足对称性和半正定型的函数是某高维希尔伯特空间的内积）
只要是满足了Mercer条件的函数，都可以作为核函数。如果有很多基的话维度势必会很高，计算内积的花销会很大，有些是无限维的，核函数能绕过高维的内积计算，直接用核函数得到内积。
核函数的基本想法：
1）通过一个非线性变换将输入空间(欧式空间Rn或离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机)。
2）核函数必须满足对称性(K(x,y) = K(y, x))及半正定性(K(x,y)>=0)。根据Mercer法则，我们知道任何满足对称性和半正定型的函数都是某个高维希尔伯特空间的内积。
核函数定义：设X是输入空间(欧式空间Rn或离散集合)，又设H为特征空间(希尔伯特空间)，如何存在一个从X到H的映射：
Ф(x): X --> H
使得对所有的x, z∈X，函数K(x, z)满足条件:
K(x,z) =Ф(x)·Ф(z)
那么就称K(x, z)为核函数，Ф(x)为映射函数，式中Ф(x)·Ф(z)为Ф(x)和Ф(z)的内积。
注：引入核函数的原因是直接计算K(x,z)容易，而通过Ф(x)和Ф(z)计算K(x,z)有点困难。
例题：
假设输入空间是R²，核函数是K(x, z)=(x.z)²，试找出相关的特征空间H（希尔伯特空间）和映射Φ(x)：R²------>H。
解：取特征空间H=R^3，记x=(x1,x2)^T，z=(z1,z2)^T,由于
(x, z)²=(x1z1+x2z2)² = (x1z1)²+2 x1z1x2z2+ (x2z2)²
可以取映射
Φ(x) = [(x1)²,√2x1x2,(x2)²]^T
Φ(x).Φ(z) = (x1z1)²+2 x1z1x2z2+ (x2z2)²
注意：原空间R²，而用核技巧后的空间是R^3，实际上是升维了
2）核技巧在支持向量机中的应用：
对支持向量机的对偶问题中跟，无论是目标函数还是决策函数（分离超平面）都只涉及实例和实例之间的内积。所以在对偶问题的目标函数 1/2 ΣΣaiajyiyj(xi.xj) -Σai 中的内积xi.xj 可以用核函数K(xi.xj) = Φ(xi).Φ(xj) 来代替。此时对偶问题的目标函数成为
W(a) = 1/2 ΣΣaiajyiyj K(xi.xj) -Σai中 (7.67)
同样分类决策函数中的内积也可以用核函数来代替，而分类决策函数成为：
f(x) = sign [ΣaiyiΦ(xi).Φ(x) + b*] = sign [ΣaiyiK(xi.xj) + b*] （7.68）
这样一来：原来输入空间中的高维度内积（升维是为了实现分离“超曲面”变成高维度空间的分离“超平面”）xi.xj经过映射函数Φ转换为特征空间（高维度空间，H空间）中的内积Φ(xi).Φ(xj)，并在新的H空间中学习线性向量机
附录A：最优化问题种类
通常我们需要求解的最优化问题有如下几类：
1、无约束优化问题，可以写为:
min f(x);
对此类优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。
2、有等式约束的优化问题，可以写为:
min f(x),
s.t. h_i(x) = 0; i =1, ..., n
对此类优化问题，常使用拉格朗日乘子法（Lagrange Multiplier) ，即把等式约束h_i(x)用一个系数与f(x)写为一个式子，称为拉格朗日函数，而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导，令其为零，可以求得候选值集合，然后验证求得最优值。
3、有不等式约束的优化问题，可以写为：
min f(x),
s.t. g_i(x) <= 0; i =1, ..., n
h_j(x) = 0; j =1, ..., m
对第3类优化问题，常用KKT条件。
同样地，我们把所有的等式、不等式约束与f(x)写为一个式子，也叫拉格朗日函数，系数也称拉格朗日乘子，通过一些条件，可以求出最优值的必要条件，这个条件称为KKT条件。
KKT条件是说最优值必须满足以下条件：
1. L(a, b, x)对x求导为零；
2. h(x) =0;
3. a*g(x) = 0;
求取这三个等式之后就能得到候选最优值。
其中第三个式子非常有趣，因为g(x)<=0，如果要满足这个等式，必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源，如支持向量的概念。
根据拉格朗日方法，对应的拉格朗日函数为
求函数z=f(x,y)在满足φ(x,y)=0的条件极值，可以转化求为函数F(x,y,λ)=f(x,y)+λφ(x,y)的无条件极值问题。
附录B KKT对偶解释（为何min max=max min=f(x)?）
http://blog.csdn.net/wusnake123/article/details/58635726 拉格朗日数乘法
【KKT的定义】KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件.这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker 最优化条件，就是指上式的最优点x∗必须满足下面的条件:
1)约束条件满足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q
2).∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇为梯度算子;
3)λj≠0且不等式约束条件满足μi≥0,μigi(x∗)=0,i=1,2,…,p。
KKT条件第一项是说最优点x∗必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的.
第二项表明在最优点x∗, ∇f必须是∇gi和∇hj的线性組合, μi和λj都叫作拉格朗日乘子. 所不同的是不等式限制条件有方向性, 所以每一个μi都必须大于或等于零, 而等式限制条件没有方向性，所以λj没有符号的限制, 其符号要视等式限制条件的写法而定.
以下举例介绍KTT 的由来
推导思路：从上述三个条件（凑出这些条件就能实现对偶，形成KTT条件求最优解）
令L(x,μ)=f(x)+Σμkgk(x) #注：这里f(x)代表目标函数，g(x)表示约束函数
∵ μk≥0，gk(x)≤0 ====> μkg(x)≤0
∴ max(μ)L(x,μ)=f(x) （公式2）
∴ min(x)f(x)=min(x)max(μ)L(x,μ) （公式3）
代入
max(μ)min(x)L(x,μ)
=max(μ)[min(x)f(x)+min(x)μg(x)]
=max(μ)min(x)f(x)+max(μ)min(x)μg(x)
=min(x)f(x)+max(μ)min(x)μg(x)
？为何max(μ)min(x)f(x)=min(x)f(x)
又∵ μk≥0，gk(x)≤0
∴ min(x)μg(x)有以下两个条件的取值
1）取值为“0” 当μ=0 或 g(x)=0
2）取值为“-∞”（负无穷） 当μ>0 或g(x)<0
所以当取值“0”的时候有最大值
==>
∴ max(μ)min(x)μg(x)=0，此时μ=0 或 g(x)=0.
∴ max(μ)min(x)L(x,μ)=min(x)f(x)+max(μ)minxμg(x)=minxf(x) （公式4）
联合（公式3）和（公式4）我们得到min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)，也就是
min(x)max(μ)L(x,μ)=max(μ)min(x)L(x,μ)=min(x)f(x)
我们把maxμminxL(x,μ)称为原问题minxmaxμL(x,μ)的对偶问题
上式表明“当满足一定条件时”，原问题（prmial）的解、对偶问题（duality）的解、以及min(x)f(x)是相同的，且在最优解x*处，μ=0或g(x*)=0。
将x*代入(公式2)得到max(μ)L(x*,μ)=f(x*)，由(公式4)得到max(μ)min(x)L(x*,μ)=f(x*)，（对"max(μ)min(x)L(x*,μ)=max(μ)L(x*,μ)”)两边消去max(μ)，所以L(x*,μ)=min(x)L(x*,μ)（式子表示x*的时候，L(x,μ)得到最小值），说明x*也是L(x,μ)的极值点。
【小结】
KKT条件是拉格朗日乘子法的泛化（见附录B说明），如果我们将等式约束和不等式约束一并纳进来如下所示：
注：由于下标x输入不方便，min(x)是指对x求最小值（常通过偏导操作实现）等同于
附录C：从||w||引出范数的定义
||w||是什么符号？||w||叫做向量w的范数，范数是对向量长度的一种度量。
我们常说的向量长度其实指的是它的L2范数，范数最一般的表示形式为p-范数，可以写成如下表达式
向量w=(w1, w2, w3,…… wn)
它的p级范数为
附录E：python实现SVM实例（LIBSVM）
http://www.cnblogs.com/luyaoblog/p/6775342.html
http://www.cnblogs.com/harvey888/p/5852687.html
http://blog.csdn.net/zouxy09/article/details/17292011
数据文件CSV的链接
附录E：工程实践
总的来说实验一、二，其结果验证了Vapnik等人的结论，即不同的核函数对SVM性能的影响不大，反而核函数的参数和惩罚因子C是影响SVM性能的关键因素，因此选择合适的核函数参数和惩罚因子C对学习机器的性能至关重要
附录F：数学符号表（用于输入公式）
2 3 ± × ÷ ∽ ≈ ≌ ≒ ≠ ≡ ≤ ≥ Σ ∈ ∞ ∝ ∩ ∪ ∫ √
б μ ? δ ε γ α β γ Ω Ψ Σ θ η λ π τ φ ω ψ ‰←↑→↓↖↗↘↙∴∵
∠∟∥∣∶∷⊥⊿⌒□△◇○?◎☆?①②③④⑤⑥⑦⑧⑨⑩°‰?℃℉№
¹²³≈≡≠＝≤≥＜＞≮≯∷±∓＋－×÷／
∫∮∝∞∧∨∑∏∪∩∈∵∴⊥∥∠⌒⊙≌∽√ ▽
αβγδεζηθικλμνξοπρστυφχψω ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩ
§№☆★○●◎◇◆□℃‰■△▲※→←↑↓↖↗↘↙
〓¤°＃＆＠＼︿＿￣―♂♀～Δ▽▽▽▽▽▽▽▽
㈠㈡㈢㈣㈤㈥㈦㈧㈨㈩①②③④⑤⑥⑦⑧⑨⑩▽▽▽▽▽▽
∂²f/∂x²=2y²，∂²f/∂x∂y=4xy，∂²f/∂y²=2x²，∂²f/∂y∂x=4xy。∂求偏导符号
附录G
一般来说，求最小值问题就是一个优化问题（规划），由两部分组成：目标函数和约束条件
min f(x) #目标函数
s.t. ci(x)≤0，i=1,2,...,p #注意这里是hi不等式约束
cj(x)=0，j=p+1,p+2,...,p+q #注意这里是等式约束
#p个是不等式约束，q个是等式约束
#上式中的x是自变量，但不限于x的维度数（例如文本分类的维度数可能达到上万个维度）
#要求f(x)在某个点找到最小值，但不是在整个空间中寻找，而是在约束的条件所限定的空间找，这个有限的空间就是优化理论提到的“可行域”
#注意到可行域中的每一个点都是要求满足p+q个条件，同时可行域边界上的点有一个优秀的特性，就是可以使不等式约束。注意，这个特性后续求解起到关键作用，例如以下例子：
max(μ)min(x)L(x,μ)
=max(μ)[min(x)f(x)+min(x)μg(x)]
=max(μ)min(x)f(x)+max(μ)min(x)μg(x)
=min(x)f(x)+max(μ)min(x)μg(x)
又∵ μk≥0，gk(x)≤0 ∴min(x)μg(x)有以下两个条件的取值
1)取值为“0” 当μ=0 或 g(x)=0；2)取值为“-∞”（负无穷） 当μ>0 或g(x)<0
所以当取值“0”的时候有最大值，因此这时μ=0 或 g(x)=0
按照定理7.2，分离超平面可以写成
Σai*yi(xi.xj）+ b* = 0 （7.29）
分类决策函数可以写成
f(x) = sign(Σai*yi（7.29）
注：这里为何是ai和aj，xi和xj，yi和yj？
2、重新审视线性分类器问题（原始问题求w解转化为对偶问题求a解，并引出内积）
min 1/2||w||^2 #注意自变量是w
s.t. yi(w.xi+b)-1≥0
需要求w的解，凸二次规划问题的优点是“容易找到解”，有全局最优解。
下来的重要思路是将“带不等式约束的问题”转化为“只带等式约束的问题--就能用拉氏算子轻松解决”（在这里，凸集边界的点就起到关键作用）
1)需要求得一个线性函数（n维空间中的线性函数），
g(x)=wx+b，
使得所有属于正类的点x+，代入后有g(x+)≥1
使得所有属于负类的点x-，代入之后有g(x)≤1
注：g(x).x-或g(x).x+都会大于1，类似yi(w.xi+b)
2）求解的过程就是“求解w的过程”，w是n维向量
3）可以看出，求出w之后，就能得出超平面H、H1和H2的解
4）w如何推导？w是由样本xi决定，这样w就可以表示为样本xi的某种组合
w=a1.x1+a2.x2+...+an.xn.
注：ai是实数值系数，又成为拉格朗日乘子；xi是样本点因而是向量，n就是总样本的个数
5）以下区别“数字和向量的乘积”以及“向量之间的乘积”，并用尖括号代表向量x1和x2的内积（也是点积，注意跟向量叉积的区别）
6）g(x)的表达式修改为：g(x)=+b（林轩田视频中，干脆就是，b为w0）
7）进一步优化表达式
w=a1.y1.x1+a2.y2.x2+...+an.y3.xn （式1）
注：yi是第i个样本的标签，yi=+1或yi=-1
8) 对求和号Σ进行简写：w=Σ（aiyixi）
9）因此原来的g(x)表达式可以写为：g(x)=+b=<Σ(aiyixi),x>+b
10）将上述公式的非向量提取出来，修改成以下式子：
g(x)=Σaiyi+b（式2）
11）至此，完成了将“求w”转化成“求a”的过程
网友评论