- 函数间隔Functional margin与几何间隔Geometrical margin
假设我们的超平面可以用公式表示： w T x b = 0 w^Tx b=0 wTx b=0， ∣ w T x b ∣ |w^Tx b| ∣wTx b∣对于样本，可以表示点x到超平面的距离 ( x 1 ， y 1 ) (x^1，y^1) (x1，y1)，我们将其定义为超平面的函数间隔 γ ^ = y 1 ( w T x 1 b ) \hat\gamma=y^1(w^Tx^1 b) γ^=y1(wTx1+b) 那么对于这个平面上任意两个点 x i ， x j x^i，x^j xi，xj都有 w T x i = − b w T x j = − b w^Tx^i=-b\\ w^Tx^j=-b wTxi=−bwTxj=−b
把上面两个点做差，可以得到 w T ( x i − x j ) = 0 w^T(x^i-x^j)=0 wT(xi−xj)=0
这两个点的差还是在这个平面上，所以可以得到 w w w是这个超平面的一个法向量，垂直于这个超平面。
对于空间中任意一个不属于这个超平面的点 x k x^k xk，我们可以连接点 x i x^i xi和点 x k x^k xk,得到 x k − x i x^k-x^i xk−xi，把它与超平面的法向量 w w w做向量乘法，然后再除以法向量的长度，可以得到它到这个超平面的距离： γ = w T ( x k − x i ) ∣ ∣ w ∣ ∣ = w T x k + b ∣ ∣ w ∣ ∣ \gamma=\frac{w^T(x^k-x^i)}{||w||}=\frac{w^Tx^k+b}{||w||} γ=∣∣w∣∣wT(xk−xi)=∣∣w∣∣wTxk+b
这里没有考虑到式子的正负，因为距离都是正的，所以结合向量机本身的假设把 y k y^k yk乘上去。就得到超平面关于特征空间中某点 x k x^k xk的几何间隔了： γ ~ = y k ∗ w T x k + b ∣ ∣ w ∣ ∣ \widetilde\gamma=y^k*\frac{w^Tx^k+b}{||w||} γ =yk∗∣∣w∣∣wTxk+b
几何距离在一个数据集上的定义是超平面跟数据集中所有点的间隔中最小的那个间隔。
函数间隔与几何间隔相比，其实就是少一个 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣而已。函数间隔不是严格意义上的点到平面的距离，因为它没有除掉法向量的长度，如果我们现在改变 w w w和 b b b，函数间隔就会跟着改变的，而几何间隔不会。但另一方面，如果我们把 ∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣定为1，函数间隔和几何间隔其实就是一回事儿了。
- 最大间隔分类器Maximum Margin Classifier
最大间隔分类器（maximum margin classifier）的目标函数为： m a x γ ~ max\widetilde\gamma maxγ
同时需满足一些条件，根据间隔的定义，有 γ ^ i = y i ( w T x i + b ) ≥ γ ， i = 1 , . . . , n \hat\gamma_i=y_i(w^Tx_i+b)\ge\gamma，i=1,...,n γ^i=yi(wTxi+b)≥γ，i=1,...,n
另 γ ^ = 1 \hat\gamma=1 γ^=1， 则 γ ~ = γ ^ ∣ ∣ w ∣ ∣ = 1 ∣ ∣ w ∣ ∣ \widetilde\gamma=\frac{\hat\gamma}{||w||}=\frac{1}{||w||} γ =∣∣w∣∣γ^=∣∣w∣∣1 此时，目标函数变为： m a x 1 ∣ ∣ w ∣ ∣ max\frac{1}{||w||} max∣∣w∣∣1
m i n 1 2 ∣ ∣ w ∣ ∣ 2 min\frac{1}{2}||w||^2 min21∣∣w∣∣2
由于这个问题的特殊结构，还可以通过拉格朗日对偶性（Lagrange Duality）变换到对偶变量 (dual variable) 的优化问题，即通过求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
- 拉格朗日对偶性
拉格朗日对偶性，通过给每一个约束条件加上一个拉格朗日乘子（Lagrange multiplier），定义拉格朗日函数（通过拉格朗日函数将约束条件融合到目标函数里去，从而只用一个函数表达式便能清楚的表达出我们的问题）
在数学中的最优化问题中，拉格朗日乘数法（以数学家约瑟夫·拉格朗日命名）是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值的方法。这种方法可以将一个有n个变量与k个约束条件的最优化问题转换为一个解有n+ k个变量的方程组的解的问题。这种方法中引入了一个或一组新的未知数，即拉格朗日乘数，又称拉格朗日乘子，或拉氏乘子，它们是在转换后的方程，即约束方程中作为梯度（gradient）的线性组合中各个向量的系数。 比如，要求 f ( x , y ) f(x, y) f(x,y)，在 g ( x , y ) = c g(x,y)=c g(x,y)=c时的最大值时，我们可以引入新变量拉格朗日乘数 λ \lambda λ，这时我们只需要下列拉格朗日函数的极值： L ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) \mathcal L(x,y,\lambda)=f(x,y)+\lambda(g(x,y)-c) L(x,y,λ)=f(x,y)+λ(g(x,y)−c)
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 ) \mathcal L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{n}\alpha_i(y_i(w^Tx_i+b)-1) L(w,b,α)=21∣∣w∣∣2−i=1∑nαi(yi(wTxi+b)−1)
θ ( w ) = m a x α i ≥ 0 L ( w , b , α ) \theta(w)=\mathop{max}\limits_{\alpha_i\ge0}\mathcal L(w,b,\alpha) θ(w)=αi≥0maxL(w,b,α)
容易验证，当某个约束条件不满足时，例如 y i ( w T x i + b ) < 1 y_i(w^Tx_i+b)<1 yi(wTxi 标签： kyk连接器