支持向量机教程


1 数学基础

    1.1 什么是支持向量?

    1.2 什么是超平面?

    1.3 超平面数学方程

    1.4 点到平面的距离

    1.5 函数间隔和几何间隔

2 SVM内容

    2.1 SVM的数学表达式

    2.2 对偶问题

    2.3 拉格朗日函数

    2.4 拉格朗日乘子法

3 扩展服务

    3.1 扩展服务

拉格朗日函数

阅读次数:1267 次

拉格朗日简介

拉格朗日全名为约瑟夫·路易斯·拉格朗日,法国著名数学家、物理学家。他在数学、力学和天文学三个学科领域中都有历史性的贡献,其中尤以数学方面的成就最为突出。在19岁的时候,拉格朗日发表了自己的第一篇论文《极大和极小的方法研究》,发展了欧拉所开创的变分法,为变分法奠定了理论基础。变分法的创立,使拉格朗日的声名大振,并使他在19岁时就当上了都灵皇家炮兵学校的教授,成为当时欧洲公认的第一流数学家。拉格朗日总结了18世纪的数学成果,同时又为19世纪的数学研究开辟了道路,堪称法国最杰出的数学大师。

变分法

在微积分出现以前,已有许多学者开始研究用数学方法解决最优化问题。例如阿基米德证明:给定周长,圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是,最优化方法真正形成为科学方法则在17世纪以后。17世纪,牛顿和莱布尼茨在他们所创建的微积分中,提出求解具有多个自变量的实值函数的最大值和最小值的方法,以后又进一步讨论具有未知函数的函数极值,从而形成变分法。

最优化问题

在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。

我们这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化,即最大值问题可以转化成最小值问题)。提到KKT条件一般会附带的提一下拉格朗日乘子,二者均是求解最优化问题的方法,不同之处在于应用的情形不同。

拉格朗日乘法

拉格朗日乘法的总体思路是:通过将约束移动到目标函数中,将约束优化目标转换为无约束优化目标。

我们来看一个简单的例子。假设你想找到函教$f(x,y)=x^2+2y$受等式$3x+2y+1=0$约束时,取得最小值时$x$和$y$的值。

使用拉格朗日乘法,我们首先定义拉格朗日函数: $g(x,y, a)=f(x,y)-a(3x+2y+1)$。原始目标减去每个约束乘以一个被称为拉格朗日乘子的新变量。

约瑟夫-路易斯-拉格朗日证明,如果$(x^*,y^*)$是约束优化问题的一个解,那么肯定存在一个$a$,使得$(x^*,y^*,a^*)$是一个拉格朗日稳定点,稳定点是所有偏导都等于零的点。

换句话说,我们可以计算$g(x,y,a)$对于$$x、$y$和$a$的偏导。我们可以找到使这些偏导为零的取值,并且约束优化问题(如果存在的话)的解必须在这些平稳点之间。

在这个例子中,偏导数是:

$\left \{ \begin{aligned} \frac{ \partial}{\partial x}g(x,y,\alpha) = 2x - 3\alpha \\ \frac{ \partial}{\partial y}g(x,y,\alpha) = 2 - 2\alpha \\ \frac{ \partial}{\partial \alpha}g(x,y,\alpha) = - 3x - 2y -1 \end {aligned} \right.$

当所有偏导数都为0时,我们发现$2x^*-3a=2-2a^*=-3x-2y^*-1=0$,从中可以很容易得出$x^*=\frac{3}{2}$,$y^*=-\frac{11}{4}$和$a=1$。这是唯一的平衡点,由于它满足约束条件,所以它肯定是约束优化问题的解。

然而,这个方法只应用于等式约束。幸运的是,在一些正则条件下(同样可以将这种方法推广到不等式约束,例如,$ 3x+2y+1 \geqslant 0$,而这种情况只好适用于SVM的求解。