• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

SVM中强对偶关系的简单推导

开发技术 开发技术 1周前 (05-04) 5次浏览

定义原问题(Primal Problem)

  • 最小化:(f(w))
  • 限制条件:
    • (g_i(w)le0 (i=1,2,…,K))
    • (h_i(w)=0 (i=1,2,…,M))

不难看出这是一个非常普适性的定义,因为:

如果要求的是最大化 (f(w)) 问题,其实也是求最小化 (-f(w)) 问题;

限制条件的 (g_i(w)le 0) 也包含了大于0的情况,即 (-g_i(w)ge0)

同样 (h_i(w)=0) 也包含了不等于0的情况: (h_i(w)=C) ,其也可以转化为等于0的问题:(h_i(w)-C=0)

对偶问题(Dual Problem)

先定义一个函数 (L)

[L(omega,alpha,beta)=f(omega)+sum_{i=1}^K{alpha_i g_i(omega)}+sum_{i=1}^M{beta_i h_i(omega)} \
=f(omega)+alpha^Tg(omega)+beta^Th(omega)(向量形式)
]

其中:(alpha)(K) 维,(beta)(M) 维(分别对应前面原问题的 (K)(g) 限制条件和 (M)(h) 限制条件。

对偶问题的定义

  • 最大化:(theta(alpha,beta)=mathrm{inf_{所有omega}}{L(omega,alpha,beta})

    (mathrm{inf})(mathrm{infimum}) ,下确界,这里理解为在限定 (alpha、beta)遍历每一个 (omega) 求出 (L) 的最小值。

  • 限制条件:

    • (alpha_i ge 0 (i=1, 2, …, K))

      也可以写为向量形式: (alpha succeq 0)

定理:如果 (w^*) 是原问题的解,而 (alpha^*,beta^*) 是其对偶问题的解,则有:

[f(omega^*) ge theta(alpha^*,beta^*)
]

证明如下:

  • (theta(alpha^{*}, beta^{*}))(=mathrm{inf})({L ( omega,)(alpha^*)(,beta^*)()}le L()(omega^*)(,)(alpha^*)(,)(beta^*)()) · · · · · · · · · · · ·

    (= f(omega^*)+sum_{i=1}^K{alpha^*_i g_i(omega^*)}+sum_{i=1}^M{beta^*_i h_i(omega^*)})

    (le f(omega^*)) · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·

    ①:(mathrm{inf}{L(omega,alpha^*,beta^*)})遍历所有的 (omega) 求得 (L) 最小值,一定是小于等于任一个 (omega^*)(L(omega^*,alpha^*,beta^*))

    ②:由于 (omega^*) 是原问题的解,故一定满足原问题的限制条件:(g_i(w)le0, h_i(w)=0)

    (alpha^*,beta^*) 是对偶问题的解,则满足对偶问题的限制条件:(alpha_i ge 0)

    ​ 由以上限制条件可得出:(sum_{i=1}^K{alpha^*_i g_i(omega^*)} le 0)(sum_{i=1}^M{beta^*_i h_i(omega^*)}=0) ,即

    (f(omega^*)) 加上一个小于等于 0 的项一定是小于等于其自身的。

间距(Duality Gap)

公式:

[G=f(omega^*)-theta(alpha^*,beta^*) ge 0
]

(G) 叫做原问题与其对偶问题的间距。

对于某些特定的优化问题,可以证明出 (G=0)

这个条件可以查阅《Convex Optimization》一书中,里面有非常详细的推导过程。

强对偶定理

(f(omega)) 为凸函数,且 (g(omega)=Aomega+b)(h(omega)=Comega+d) ,则此优化问题的原问题与其对偶问题的间距为 0 ((G = 0)),即 (f(omega)=theta(alpha,beta))

有了此结论后,上面定理 (f(omega^*) ge theta(alpha^*,beta^*)) 的证明过程中的①②的 “(le)” 就为 “(=)” 了,此时不难得出 (sum_{i=1}^K{alpha^*_i g_i(omega^*)}=0) ,则可以进一步得出下面的条件:

对于 (forall i (i=1,2,…,K))

  • 或者 (alpha^*_i =0)
  • 或者 (g_i(omega^*)=0)

上面的条件就称为 KKT 条件。


程序员灯塔
转载请注明原文链接:SVM中强对偶关系的简单推导
喜欢 (0)