支持向量机教程


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 扩展服务

拉格朗日乘子法(Lagrange Multiplier)

阅读次数:1204 次

在学习过程中,有时会遇到一些最优化问题。所谓“最优化问题”通常是指对于给定的某一函数,求其在指定作用域上的全局最小值(无论最大最小值都可以转化为最小值)。

一般情况下,最优化问题分为下面三种类型:

  • 无约束条件

  • 等式约束条件

  • 不等式约束条件

什么是拉格朗日乘子法?

基本的拉格朗日乘子法就是求函数$f(x_1,x_2,...)$在约束条件$g(x1,x2,...)=0$下的极值的方法。其主要思想是将约束条件函数与原函数联立,从而求出使原函数取得极值的各个变量的解。

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

1、无约束条件

例如,$minf(x)$这是最简单的情况,解决方法是函数对变量求导,令求导函数等于0的点可能是极值点,最后将结果带回原函数进行验证。

2、等式约束条件

设目标函数为$f(x)$,约束条件为$h_k(x)$,$s.t.$表示$subject to$,“受限于”的意思,$l$表示有$l$个约束条件。

$$minf(x)$$

$$s.t. \quad h_k(x)=0 \quad k=1,2,...,l$$

则解决方法是消元法或者拉格朗日法。本文主要讲拉格朗日法,后文提到的KKT条件是对拉格朗日乘子法的一种泛化。

例如,给定椭球:

$$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$$

求这个椭球的内接长方体的最大体积。

我们将这个问题转化为条件极值问题,即在条件$\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1$下,求$f(x,y,z)=8xyz$的最大值。

当然,这个问题实际可以先根据条件消去$z$(消元法),然后带入转化为无条件极值问题来处理,但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。

首先,定义拉格朗日函数$F(x)$:

$$F(x,\lambda)=f(x)+\sum_{k-1}^l\lambda_kh_k(x)$$

其中:$\lambda_k$是各个约束条件的待定系数

然后,解变量的偏导方程:

$$\frac{\partial F}{\partial x_i}=0...\frac{\partial F}{\partial\lambda_k}$$

如果有$l$个约束条件,就应该有$l+1$个方程。求出的方程组的解就可能是最优化值(高等数学中提到的极值),将结果带回原方程验证就可得到解。

回到上面的题目,通过拉格朗日乘数法将问题转化为:

$$F(x,y,z,\lambda)=f(x,y,z)+\lambda\psi(x,y,z)=8xyz+\lambda(\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1)$$

对$F(x,y,z,\lambda)$求偏导得:

$$\frac{\partial F(x,y,z,\lambda)}{\partial x}=8yz+\frac{2\lambda x}{a^2}=0$$

$$\frac{\partial F(x,y,z,\lambda)}{\partial y}=8xz+\frac{2\lambda y}{b^2}=0$$

$$\frac{\partial F(x,y,z,\lambda)}{\partial z}=8xy+\frac{2\lambda z}{c^2}=0$$

$$\frac{\partial F(x,y,z,\lambda)}{\partial \lambda}=\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0$$

联立前面三个方程得到$bx=ay$和$az=cx$,带入第四个方程解得:

$$x = \frac{\sqrt{3}}{3}a \quad x = \frac{\sqrt{3}}{3}b \quad x = \frac{\sqrt{3}}{3}c$$

带入解最大体积为:

$$V_{max}=f(\frac{\sqrt{3}}{3}a,\frac{\sqrt{3}}{3}b,\frac{\sqrt{3}}{3}c)=\frac{8\sqrt{3}}{9}abc$$

3、不等式约束条件

设目标函数$f(x)$,不等式约束为$g(x)$,有的还会添加上等式约束条件$h(x)$,此时的约束优化问题描述如下:

$$minf(x)$$

$$s.t. \quad h_j(X)=0 \quad j=1,2,...,p$$

$$g_k(X) \leq 0 \quad k=1,2,...,q$$

则我们定义不等式约束下的拉格朗日函数$L$,则$L$表达式为:

$$L(X,\lambda,\mu)=f(X)+\sum^p_{j=1}\lambda_jh_j(X)+\sum^p_{k=1}\mu_kg_k(X)$$

其中$f(x)$是原目标函数,$h_j(x)$是第$j$个等式约束条件,$λ_j$是对应的约束系数,$g_k$是不等式约束,$\mu_k$是对应的约束系数。常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子

$$L(a,b,x)=f(x)+ag(x)+bh(x)$$

KKT条件是说最优值必须满足以下条件:

  • $L(a,b,x)$对$x$求导为零;
  • $h(x)=0$;
  • $a*g(x)=0$;

求取这些等式之后就能得到候选最优值该方法适用于约束条件下求极值的问题。对于没有约束的极值问题,显然,如果某一点是极值的必要条件是该点的各方向的偏导数皆为零,也就是说,如果偏导数不全为零,那么就不可能是极值。