x到线性判别平面距离

image.png线性分类面:支持向量机(SVM) - 图2
图中x到分类面的距离是r
则有支持向量机(SVM) - 图3 ,支持向量机(SVM) - 图4

线性判别函数支持向量机(SVM) - 图5利用一个超平面把特征空间分隔成两个区域。 超平面的方向由法向量w确定，它的位置由阈值w0确定。 当x点在超平面的正侧时，f(x)>0； 当x点在超平面的负侧时，f(x)<0 x点到超平面的距离支持向量机(SVM) - 图6 可视为对x判别的“置信度” 支持向量机(SVM) - 图7

最大间隔

image.png
支持向量机(SVM) - 图9

支持向量机(SVM) - 图10

支持向量机(SVM) - 图11

最大化间隔的超平面为 支持向量机(SVM) - 图12 等价于支持向量机(SVM) - 图13 二次规划问题(目标函数为二次函数，约束为线性约束) , 变量数为W的维数D+1，约束项的数目为样本数N

SVM的对偶表示

拉格朗日函数支持向量机(SVM) - 图14
求使得目标支持向量机(SVM) - 图15最小的支持向量机(SVM) - 图16和支持向量机(SVM) - 图17:
支持向量机(SVM) - 图18 支持向量机(SVM) - 图19
将支持向量机(SVM) - 图20 从 支持向量机(SVM) - 图21 消去,得到对偶表示支持向量机(SVM) - 图22
支持向量机(SVM) - 图23
因为支持向量机(SVM) - 图24
支持向量机(SVM) - 图25
支持向量机(SVM) - 图26
支持向量机(SVM) - 图27

仍然是一个QP问题：变量数为N，约束项的数目为(N+1) 当N较大时，对偶问题的复杂度可能比原问题更高,但对偶问题可利用kernel trick与核方法结合 可使用SMO(sequential minimal optimization) 高效求解 ,每次选取一对支持向量机(SVM) - 图28 做优化 求解出支持向量机(SVM) - 图29后,再求出支持向量机(SVM) - 图30和支持向量机(SVM) - 图31,可以得到判别函数支持向量机(SVM) - 图32

KKT条件

原问题:支持向量机(SVM) - 图33
拉格朗日函数:支持向量机(SVM) - 图34
对偶问题:D = 支持向量机(SVM) - 图35
拉格朗日对偶通常是凹的（即使原问题非凸），可能更容 易优化求解 ,

  • 弱对偶性 原问题P的解≥对偶问题D的解总是成立
  • 强对偶性 原问题P的解≥对偶问题D的解不总是成立,对凸问题通常成立,对SVM QP 问题总是成立

如果强对偶条件成立,则对最优的支持向量机(SVM) - 图36,必须满足下述KKT条件

  • 原问题的可行域:支持向量机(SVM) - 图37
  • 对偶问题的可行域:支持向量机(SVM) - 图38
  • 平稳条件:支持向量机(SVM) - 图39

  • 互补松弛条件:支持向量机(SVM) - 图40

    SVM解的稀疏性

    拉格朗日函数:支持向量机(SVM) - 图41

  • 对偶问题的可行域:支持向量机(SVM) - 图42

  • 原问题的可行域:支持向量机(SVM) - 图43
  • 互补松弛条件:支持向量机(SVM) - 图44
  • 平稳条件:支持向量机(SVM) - 图45 支持向量机(SVM) - 图46

根据KKT中的互补松弛条件,对每个点 支持向量机(SVM) - 图47 当支持向量机(SVM) - 图48的时候,该点在判别函数支持向量机(SVM) - 图49中不起作用
其他点即满足支持向量机(SVM) - 图50的点对应位于最大间隔超平面上的点,称为支持向量

模型训练好后，大多数点可以抛掉，只需保留支持向量 即SVM解的稀疏性

w0的计算

任意支持向量满足支持向量机(SVM) - 图51,又由于支持向量机(SVM) - 图52,代入得到
支持向量机(SVM) - 图53, 即用任意一个支持向量即可求得支持向量机(SVM) - 图54
两边同时乘以支持向量机(SVM) - 图55,因为支持向量机(SVM) - 图56所以得到 支持向量机(SVM) - 图57,为了得到更稳定的解,通常使用所有的支持向量求平均,得到
支持向量机(SVM) - 图58