SVM可以称之为最大间隔分类器，其目标是将两类样本分开，且间隔最大。对于线性可分问题，间隔是通过两条直线\[\omega^T x+b=\pm1\] 可以计算为\(\frac{2}{\omega}\),同时应满足条件各点被分类正确，即\[y_i *(\omega^T X_{i}+b)\ge1\] 那么最大化间隔等价于最小化\(\omega\)，所以其目标函数可以表示为\[min \frac{1}{2}\omega^2,s.t.1-y_i *(\omega^T X_i+b)\le0\] 由于该函数是条件极值问题,所以可以通过拉格朗日乘子法来计算。假设每个样本点满足的条件\(1-y_i (\omega^T X_{i}+b)\le0\)前的系数为\(\alpha_{i}\),则拉格朗日函数为\[L(\omega,b,\alpha_i)=\frac{1}{2}\omega^{2}+\sum\limits_{i=1}^{n}\alpha_i(1-(\omega^T X_i +b))\] 令\[\theta_p(\omega)=\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha_i)\] 则当\(\omega\)满足原始条件时，函数\(\theta_p(\omega)\)与原函数\(\frac{1}{2}\omega^2\)等价。因为当满足条件时，要使上式最大，只能令\(\alpha_i=0\)，即为\(\frac{1}{2}\omega^2\)；当不满足原始条件时，上式为\(\infty\) 求\(\frac{1}{2}\omega^2\)的最小值等价为求\(\theta_p(\omega)\)的最小值。即\[\min\limits_{\omega,b}\max\limits_{\alpha_i\ge0}L(\omega,b,\alpha_i)\] 则原始的最优化问题转化为广义拉格朗日的极小极大问题。 原来的极小极大问题可以转化其对偶问题极大极小问题。一般而言，对于凸函数，两者的最优值是等价的，则其对偶问题为\[\max\limits_{\alpha_i\ge0}\min\limits_{\omega,b}L(\omega,b,\alpha_i)\]
而如果\((\omega,b)\)是原始问题的解和\(\alpha^{*}\)对偶问题的解的必要条件时其满足以下KKT条件（KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。）
L对\(\omega\)和b的偏导为0；\(\alpha_i\)大于等于0；\(\alpha_i*(1-(\omega^T X_i+b))=0\)；满足原始约束； 由KKT条件3和4可知，对于非支持向量的样本，其系数\(\alpha_i\)都为0。首先求关于\((\omega)\)和b的极小 由KKT条件知对于\(\omega\)和b的偏导都应该为0，即\[\frac{\partial L}{\partial \omega} = \omega - \sum\limits_{i=1}^{n}\alpha_i X_i=0\]\[\frac{\partial L}{\partial b} = \sum \alpha_i y_i = 0 \] 将\(\omega\)的值代入，即得\[\sum\alpha_i-\frac{1}{2}\sum\limits_{i,j=1}^{n}\alpha_i\alpha_j y_i y_j X_i^T X_j\] 然后求上式关于\(\alpha_i\)的极大，当求得\(\alpha_i\)的值后，就可以计算出\(\omega\)和b，进而得到目标函数 那么 SVM的目标函数： SVM的损失函数：
SMO算法
转载于:https://www.cnblogs.com/fcyblogs/p/8727190.html
相关资源：各显卡算力对照表！