上节课把原始的优化问题改写成二次规划的形式，通过软件包来求解参数。这节课通过研究原问题的对偶问题，在一定条件下，对偶问题的最优解和解参数和原问题一致，继而得到原问题的解。
Motivation of Dual SVM
[x,x2,x3]→[z1,z2,z3]
[
x
,
x
2
,
x
3
]
→
[
z
1
,
z
2
,
z
3
]
)。此时，z域是线性的，可以使用上节课的线性SVM求解最优解(这话听着怪怪的，我说下我的理解吧)。回忆基石的课，拟合回归问题时。可以通过增加x
x
高次方项增加模型的复杂度，继而减小EinEin。同样的，对于SVM问题，也可以通过这样的方式减少Ein
E
i
n
，并且SVM的large-margin能够减少有效的VC Dimension，相当于加了一个惩罚项。但是做变换的时候特征维度往往会变得很大，由d→d^
d
→
d
^
，此时求解QP问题会比较复杂。对偶问题在求解时，不依赖d^
d
^
，这就是提出对偶问题的原因。(后面会讲到对偶问题依赖的是训练集大小，一般来说都是样本数量大于特征数量吧，奇怪了。这个疑惑，暂且留着吧–据说和核函数升维有关系，升维之后特征会变得特别多)。
经过变换之后，QP问题的形式如下：
前面说过SVM相当于加了个惩罚项，基石的正则化课程讲到通过拉格朗日乘子法求解，同样的dual SVM问题也可以通过引入拉格朗日乘子的方式，把原问题转化为非条件问题。
那么如何讲条件问题转化成非条件问题呢？拉格朗日乘子法熟悉的话，应该很直观:
下面利用拉格朗日函数构造非条件问题：
为什么这样构造之后，两个问题就等价了呢？可以这样理解：
把max L(b,w,α)
m
a
x
L
(
b
,
w
,
α
)
记为f
f
，转化之后的问题就是在(w,b)(w,b)的参数空间中找一个使得f
f
最小的值
对于ff，是要找到一个α
α
使得L(b,w,α)
L
(
b
,
w
,
α
)
最大。观察拉格朗日函数，显然如果原问题的约束条件不满足，则1−yn(wTzn+b)>0
1
−
y
n
(
w
T
z
n
+
b
)
>
0
，f
f
趋于正无穷，那么minmin时，这样的参数取不到最优解。所以先对L
L
取关于αα的极小，再取关于w,b
w
,
b
的极大和原问题是等价的。
Lagrange Dual SVM
αn>0
α
n
>
0
，那么对于固定的α′
α
′
且α′n≥0
α
′
n
≥
0
，一定有如下不等式成立：
上式显然成立，对不等式两边同时取Max，不等式同样成立：
上式表明对等价问题的min和max做了一个对调，满足这样的关系叫做Lagrange dual problem。≥
≥
称为弱对偶关系，=
=
称为强对偶关系。在二次规划QP问题中，强对偶关系需要满足下面三个条件：
1. 函数是凸的(convex primal)
2. 函数有可行解(feasible primal)
3. 条件是线性的(linear constraints)
即存在满足条件的解(b,w,α)(b,w,α)使得等式左右都成立，这样就可以通过直接解对偶问题求原问题。
关于拉格朗日对偶性，李航的《统计学习方法》有较为完整的介绍。并且强对偶要求的是约束和目标函数都是凸函数，有点差异的。此处存疑！
这里原问题满足这三个条件，所以我们可以直接求对偶问题，经过推导对偶问题转化为无条件形式：
先求上式括号里的部分，即对拉格朗日函数求最小值，那么必要条件是梯度为0。首先，令L(b,w,α) L ( b , w , α ) 对参数b b 的偏导为0：
∂L∂b=0→−∑n=1Nαnyn=0∂L∂b=0→−∑n=1Nαnyn=0
把上述求偏导得到的等式带入并化简：
同样的对w w 求偏导：
∂L∂w=0→w−∑n=1Nαnynzn=0→w=∑n=1Nαnynzn∂L∂w=0→w−∑n=1Nαnynzn=0→w=∑n=1Nαnynzn
把上述求偏导得到的等式带入并化简：
这样，表达式里面消去了w w ，问题进一步简化。这时候的条件有3个：
其中满足最佳化条件称为Karush-Kuhn-Tucker(KKT)：
这里有个逻辑问题没搞明白，就SVM问题而言，是因为原问题和对偶问题满足一些条件所以他们有相同的最优解，然后一定会满足KKT条件，不知道是不是这个逻辑，回头再查查资料吧。
Solveing Dual SVM
进一步简化，把MAX问题转化为Min问题，把部门条件放到约束中：
w=∑n=1Nαnynzn
w
=
∑
n
=
1
N
α
n
y
n
z
n
这个条件暂时不考虑，因为目标函数中没有出现w
w
。然后改写成QP问题的形式，用软件包求解即可。
这里没有看懂，主要αn≥0αn≥0拆到约束里怎么表达，存疑吧~
计算Q
Q
矩阵时，如果样本量特别大，计算量也会很大。所以计算QQ时会采用一些特殊的方法。
得到αn
α
n
之后，根据KKT条件就可以计算w
w
和bb。
首先w=∑n=1Nαn
w
=
∑
n
=
1
N
α
n
其次根据αn(1−yn(wTzn+b))=0
α
n
(
1
−
y
n
(
w
T
z
n
+
b
)
)
=
0
得到b=yn−wTzn
b
=
y
n
−
w
T
z
n
计算b b 时，如果αn>0αn>0成立，那么yn(wTzn+b)=1 y n ( w T z n + b ) = 1 成立，那说明这个点正好在分解线上，即fat boundary上，这些点就是support vector。
Messages behind Dual SVM
前面讲到如果αn>0
α
n
>
0
成立，那么yn(wTzn+b)=1
y
n
(
w
T
z
n
+
b
)
=
1
成立，那说明这个点就是支持向量，但是分类线上的点不一定都是支持向量，但满足αn>0
α
n
>
0
的点一定都是支持向量。
比较PLA和SVM的公式：
两者形式上十分相似，但是wSVM w S V M 由fattest hyperplane边界上所有的SV决定(非支持向量点对应α α 为0)，wPLA w P L A 由所有当前分类错误的点决定。wSVM w S V M 和wPLA w P L A 都是原始数据点yn,zn y n , z n 的线性组合形式，是原始数据的代表。
Summary
比较原始问题和对偶问题：
对偶问题的引进是为了避免计算中对d^ d ^ 的依赖，约束由d^ d ^ 个条件转换成N N 个约束条件。但是计算QQ矩阵时候已经引入了。下节课将研究探讨如何消除对d^ d ^ 的依赖。
存疑
有两个疑问，记录下：
1. 对偶问题QP问题的改写
2. KKT条件的逻辑，是因为对偶问题和原问题满足三个条件，所以有共同的最优解，继而满足KKT条件？
Ref
[1] 《机器学习技法》第二周课程
2018-03-28 于杭州