1. 最优化理论(Optimization Theory)
最优化理论是研究函数在给定一组约束条件下的最小值(或者最大值)的数学问题. 一般而言, 一个最优化问题具有如下的基本形式:
其中. f(x)
为目标函数, gi(x)≤0,i=1,2,…,p 为不等式约束条件, hj(x)=0,k=1,2,…,q 为等式约束条件.在很多情况下, 不等式约束条件可以通过引入新的变量而转化为等式约束条件, 因此最优化问题的一般形式可以简化为仅仅包含等式约束条件的形式
最优化问题可以根据目标函数和约束条件的类型进行分类:
1). 如果目标函数和约束条件都为变量的线性函数, 称该最优化问题为线性规划;
2). 如果目标函数为变量的二次函数, 约束条件为变量的线性函数, 称该最优化问题为二次规划;
3). 如果目标函数或者约束条件为变量的非线性函数, 称该最优化问题为非线性规划.
2. KKT(Karush-Kuhn-Tucker)
KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点x?
必须满足下面的条件:1). 约束条件满足gi(x?)≤0,i=1,2,…,p
, 以及,hj(x?)=0,j=1,2,…,q2). ?f(x?)+∑i=1pμi?gi(x?)+∑j=1qλj?hj(x?)=0
, 其中? 为梯度算子;3). λj≠0
且不等式约束条件满足μi≥0,μigi(x?)=0,i=1,2,…,pKKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出来的. 这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视, 因此许多书只记载成「Kuhn-Tucker 最优化条件 (Kuhn-Tucker conditions)」.
KKT条件第一项是说最优点x?
必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的. 第二项表明在最优点x? , ?f 必须是?gi 和?hj 的线性組合, μi 和λj 都叫作拉格朗日乘子. 所不同的是不等式限制条件有方向性, 所以每一个μi 都必须大于或等于零, 而等式限制条件没有方向性,所以λj 没有符号的限制, 其符号要视等式限制条件的写法而定.3. 关于duality
一位博友对duality的总结很通俗易懂, http://blog.pluskid.org/?p=702 这里就不再重复复述
支持向量机:Duality
本文是“支持向量机系列”的番外篇(1),参见本系列的其他文章。
在之前关于 support vector 的推导中,我们提到了 dual ,这里再来补充一点相关的知识。这套理论不仅适用于 SVM 的优化问题,而是对于所有带约束的优化问题都适用的,是优化理论中的一个重要部分。简单来说,对于任意一个带约束的优化都可以写成这样的形式:
形式统一能够简化推导过程中不必要的复杂性。其他的形式都可以归约到这样的标准形式,例如一个 maxf(x) 可以转化为 min?f(x) 等。假如 f0,f1,…,fm 全都是,并且 h1,…,hp 全都是(就是形如 Ax+b 的形式),那么这个问题就叫做凸优化(Convex Optimization)问题。凸优化问题有许多优良的性质,例如它的极值是唯一的。不过,这里我们并没有假定需要处理的优化问题是一个凸优化问题。
虽然约束条件能够帮助我们减小搜索空间,但是如果约束条件本身就是比较复杂的形式的话,其实是一件很让人头痛的问题,为此我们希望把带约束的优化问题转化为无约束的优化问题。为此,我们定义 Lagrangian 如下:
它通过一些系数把约束条件和目标函数结合在了一起。当然 Lagrangian 本身并不好玩,现在让我们来让他针对 λ 和 ν 最大化,令:
这里 λ?0 理解为向量 λ 的每一个元素都非负即可。这个函数 z(x) 对于满足原始问题约束条件的那些 x 来说,其值等于 f0(x) ,这很容易验证,因为满足约束条件的 x 会使得hi(x)=0 ,因此最后一项消掉了,而 fi(x)≤0 ,并且我们要求了 λ?0 ,因此 λifi(x)≤0 ,所以最大值只能在它们都取零的时候得到,这个时候就只剩下 f0(x)了。因此,对于满足约束条件的那些 x 来说,f0(x)=z(x) 。这样一来,原始的带约束的优化问题其实等价于如下的无约束优化问题:
因为如果原始问题有最优值,那么肯定是在满足约束条件的某个 x? 取得,而对于所有满足约束条件的 x ,z(x) 和 f0(x) 都是相等的。至于那些不满足约束条件的 x ,原始问题是无法取到的,否则极值问题无解。很容易验证对于这些不满足约束条件的 x 有 z(x)=∞,这也和原始问题是一致的,因为求最小值得到无穷大可以和“无解”看作是相容的。
到这里,我们成功把带约束问题转化为了无约束问题,不过这其实只是一个形式上的重写,并没有什么本质上的改变。我们只是把原来的问题通过 Lagrangian 写作了如下形式:
这个问题(或者说原始的带约束的形式)称作 primal problem 。如果你看过之前关于 SVM 的推导,那么肯定就知道了,相对应的还有一个 dual problem ,其形式非常类似,只是把 min 和 max 交换了一下:
交换之后的 dual problem 和原来的 primal problem 并不相等,直观地,我们可以这样来理解:胖子中最瘦的那个都比瘦骨精中最胖的那个要胖。当然这是很不严格的说法,而且扣字眼的话可以纠缠不休,所以我们还是来看严格数学描述。和刚才的 z(x) 类似,我们也用一个记号来表示内层的这个函数,记:
并称 g(λ,ν) 为 Lagrange dual function (不要和 L 的 Lagrangian 混淆了)。g 有一个很好的性质就是它是 primal problem 的一个下界。换句话说,如果 primal problem 的最小值记为 p? ,那么对于所有的 λ?0 和 ν ,我们有:
因为对于极值点(实际上包括所有满足约束条件的点)x?,注意到 λ?0 ,我们总是有
因此
于是
这样一来就确定了 g 的下界性质,于是
实际上就是最大的下界。这是很自然的,因为得到下界之后,我们自然地就希望得到最好的下界,也就是最大的那一个——因为它离我们要逼近的值最近呀。记 dual problem 的最优值为 d? 的话,根据上面的推导,我们就得到了如下性质:
这个性质叫做 weak duality ,对于所有的优化问题都成立。其中 p??d? 被称作 duality gap 。需要注意的是,无论 primal problem 是什么形式,dual problem 总是一个 convex optimization 的问题——它的极值是唯一的(如果存在的话),并且有现成的软件包可以对凸优化问题进行求解(虽然求解 general 的 convex optimization 实际上是很慢并且只能求解规模较小的问题的)。这样一来,对于那些难以求解的 primal problem (比如,甚至可以是 NP 问题),我们可以通过找出它的 dual problem ,通过优化这个 dual problem 来得到原始问题的一个下界估计。或者说我们甚至都不用去优化这个 dual problem ,而是(通过某些方法,例如随机)选取一些 λ?0 和 ν ,带到 g(λ,ν) 中,这样也会得到一些下界(只不过不一定是最大的那个下界而已)。当然要选 λ 和 ν 也并不是总是“随机选”那么容易,根据具体问题,有时候选出来的 λ 和 ν 带入 g 会得到 ?∞ ,这虽然是一个完全合法的下界,然而却并没有给我们带来任何有用的信息。
故事到这里还没有结束,既然有 weak duality ,显然就会有 strong duality 。所谓 strong duality ,就是
这是一个很好的性质,strong duality 成立的情况下,我们可以通过求解 dual problem 来优化 primal problem ,在 SVM 中我们就是这样做的。当然并不是所有的问题都能满足 strong duality ,在讲 SVM 的时候我们直接假定了 strong duality 的成立,这里我们就来提一下 strong duality 成立的条件。不过,这个问题如果要讲清楚,估计写一本书都不够,应该也有不少专门做优化方面的人在研究这相关的问题吧,我没有兴趣(当然也没有精力和能力)来做一个完整的介绍,相信大家也没有兴趣来看这样的东西——否则你肯定是专门研究优化方面的问题的了,此时你肯定比我懂得更多,也就不用看我写的介绍啦。
所以,这里我们就简要地介绍一下 Slater 条件和 KKT 条件。Slater 条件是指存在严格满足约束条件的点 x ,这里的“严格”是指 fi(x)≤0 中的“小于或等于号”要严格取到“小于号”,亦即,存在 x 满足
让我们回到 duality 的话题。来看看 strong duality 成立的时候的一些性质。假设 x? 和 (λ?,ν?) 分别是 primal problem 和 dual problem 的极值点,相应的极值为 p? 和 d?,首先 p?=d? ,此时我们可以得到
由于两头是相等的,所以这一系列的式子里的不等号全部都可以换成等号。根据第一个不等号我们可以得到 x? 是 L(x,λ?,ν?) 的一个极值点,由此可以知道 L(x,λ?,ν?)在 x? 处的梯度应该等于 0 ,亦即:
此外,由第二个不等式,又显然 λ?ifi(x?) 都是非正的,因此我们可以得到
这个条件叫做 complementary slackness 。显然,如果 λ?i>0,那么必定有 fi(x?)=0;反过来,如果 fi(x?)<0 那么可以得到 λ?i=0 。这个条件正是我们在介绍支持向量的文章末尾时用来证明那些非支持向量(对应于 fi(x?)<0)所对应的系数 αi (在本文里对应 λi )是为零的。 :) 再将其他一些显而易见的条件写到一起,就是传说中的 KKT (Karush-Kuhn-Tucker) 条件: