落园 » 统计学习精要(The Elements of Statistical Learning)课堂笔记(二十):SVM|专注经济视角下的互联网

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十):SVM

这节课主要是讲线性优化的对偶问题。感觉这东西貌似在运筹学的时候被折腾过一遍,现在又来了-_-||

附赠个老的掉牙的段子...

有人问经济学家一个数学问题,经济学家表示不会解...

然后那个人把这个数学问题转成了一个等价的最优化问题,经济学家立马就解出来了...

好吧,我还是乖乖的赘述一遍对偶问题吧,表示被各种经济学最优化问题折磨过的孩子这点儿真是不在话下。

--------------------------------------------------------------------

1. 对偶问题的一般情况

1) 优化问题

一个典型的最优化问题形如:

\min f_{0}(x)

s.t.\, f_{i}(x)\leq0,\ i\in\left\{ 1,\dots,m\right\} (不等式约束)

h_{i}(x)=0,\ i\in\left\{ 1,\dots,p\right\} (等式约束)

2) 优化问题的Lagrange (拉格朗日)函数

\mathcal{L}(x,\lambda,\nu)=f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}\nu_{i}h_{i}(x).

\lambda_{i},\nu_{i}>0,\forall i

3) 对偶函数

g(\lambda,\nu)=\inf_{x\in\mathcal{D}}\mathcal{L}(x,\lambda,\nu)=\inf_{x\in\mathcal{D}}\left(f_{0}(x)+\sum_{i=1}^{m}\lambda_{i}f_{i}(x)+\sum_{i=1}^{p}\nu_{i}h_{i}(x)\right)称为该优化问题的对偶函数。此时,

\nabla x\mathcal{L}(x,\lambda,\nu)=0,显然这个时候一阶偏导数为0。

4) 对偶问题

我们称\max g(\lambda,\nu),s.t.\lambda\geq0为原优化问题的对偶问题,可化为最优化问题的标准形式\min-g(\lambda,\nu),s.t.-\lambda\leq0

如果原优化问题为凸优化,则g(\cdot)必为凹函数,从而最终的标准形式依旧是一个凸优化问题。

5) 弱对偶性

x*为原问题的解,则p*=f_{0}(x*),且f_{i}(x^{*})\leq0h_{i}(x*)=0.

(\lambda*,\nu*)为对偶问题的解,则d*=g(\lambda*,\nu*); \lambda*\geq0.

定理(弱对偶性)d*\leq p*,即对偶问题的优化值必然小于等于原问题优化值。

6) 强对偶性

d*=p*时,两者具有强对偶性;满足该条件的称之为constraint qualifications,如Sliter定理

强对偶性满足的时候,原优化问题就可以化为一个二步优化问题了。

7) KTT条件(库恩-塔克条件)

局部最优化成立的必要条件:

\nabla x\mathcal{L}(x,\lambda,\nu)=\nabla f(x^{*})+\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(x^{*})+\sum_{j=1}^{l}\nu{}_{j}\nabla h_{j}(x^{*})=0(一阶条件)

\lambda_{i}f_{i}(x^{*})=0,\;\forall i=1,\ldots,m.

\lambda_{i}\geq0,\forall i

f_{i}(x^{*})\le0,\;\forall i=1,\ldots m

h_{j}(x^{*})=0,\;\forall j=1,\ldots,p

注:SVM满足强对偶性,所以可以直接解对偶问题。

2. 对偶问题应用于SVM

1) SVM的最优化问题

上节课可知,SVM的最优化问题为:

\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}

s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i},\forall i

写成标准形式就是

\min\frac{1}{2}\left\Vert w\right\Vert ^{2}+C\sum_{i}\xi_{i}

s.t.\,1-\xi_{i}-y_{i}(w_{i}+b)\leq0,\forall i

-\xi_{i}\leq0,\forall i

这样这里总计有2N个约束条件。

对应的Lagrange函数为:\min_{\mathbf{w},\mathbf{\xi},b}\left\{ \frac{1}{2}\|\mathbf{w}\|^{2}+C\sum_{i=1}^{n}\xi_{i}+\sum_{i=1}^{n}\lambda_{i}[1-y_{i}(\mathbf{w'}\cdot\mathbf{x_{i}}-b)-\xi_{i}]-\sum_{i=1}^{n}\mu_{i}\xi_{i}\right\}

这样一阶条件就是

\frac{\partial L}{\partial w_{k}}=w_{k}+\sum_{i=1}^{n}\lambda_{i}(-y_{i}x_{i}^{k})=0
\Rightarrow\mathbf{w}=\sum_{i=1}^{n}\lambda_{i}(y_{i}x_{i})

\frac{\partial L}{\partial b}=\begin{subarray}{c}\sum_{i=1}^{n}\lambda_{i}(-y_{i})=0\end{subarray}\Rightarrow\sum_{i=1}^{n}\lambda_{i}y_{i}=0

\frac{\partial L}{\partial\xi_{k}}=C-\lambda_{k}-\mu_{k}=0\Rightarrow C-\lambda_{k}-\mu_{k}=0,\forall k

这样最后我们有\mathcal{L}^{*}=-\frac{1}{2}\sum_{i}\lambda_{i}y_{i}(\mathbf{w'}x_{i})+\sum_{i}\lambda_{i}(1-b).

3) 对偶函数

这里的对偶函数就是g(\lambda,\mu)=-\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})+\sum_{i}\lambda_{i}

4) 对偶问题

\min-g(\lambda,\mu)=\frac{1}{2}\sum_{i}\sum_{j}(\lambda_{i}y_{i})(\lambda_{j}y_{j})(x_{i}'x_{j})-\sum_{i}\lambda_{i}

s.t.\sum_{i}\lambda_{i}y_{i}=0

0\leq\lambda_{i}\leq C

\mu_{i}\geq0

5) KKT条件

w=\sum\lambda_{i}y_{i}x_{i}

\lambda_{i}(1-y_{i}(w'x_{i}+b)-\xi_{i})=0

\sum\lambda_{i}y_{i}=0

0\leq\lambda_{i}\leq C

\lambda_{i}[y_{i}(w'x_{i}+b)-\xi_{i}]=0

\mu_{i}\xi_{i}=0

\mu_{i}\geq0

6) SVM分类器

  • 解对偶问题,得到\lambda*, \mu*
  • 计算w^{*}=\sum_{i}\lambda_{i}y_{i}x_{i}
  • 计算b^{*}:找到一个<0\lambda_{i}<C(非边界上),从而满足\begin{cases}1-y_{i}(\mathbf{w'}\cdot\mathbf{x_{i}}-b)=0\\\xi_{i}=0\end{cases}。由y_{i}=\pm1,我们可得(\mathbf{w'}\cdot\mathbf{x_{i}}-b)=y_{i}\Rightarrowb=y_{i}-\mathbf{w'}\cdot\mathbf{x_{i}}=y_{i}-\sum_{j}\lambda_{j}y_{j}(x_{j}'x_{i})
  • 平面分类器: y=w^{*}x+b, \hat{y}=sign(w*x+b)=sign(\sum_{j}\lambda_{j}y_{j}(x_{j}'x_{i})),故只与内积有关。

这样下节课就会讲到解对偶问题的方法,以及SVM和kernel methods的联系。


Comments

  • MichaelMoore says:

    看课堂笔记还附带笑话的,表示笑话看到笑点了,数学公式严重地表示不能理解。
    这课的内容不是老教授上的吧,如果是的话,真心给跪了。突然想起,要么还有助教这一角色的存在?


  • ningyu says:

    有几个问题,
    1.拉格朗日函数中vi为什么要大于0?
    2.对偶函数中的inf是求无穷大还是无穷小还是别的啊


    • liyun says:

      1. lambda_i?这个是库恩塔克条件规定的...因为已经都化为标准形式了所以这里一定要求大于0。见: https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
      2. inf是最小下界(下确界)吧...有点类似于min,但不要求一定达到。见: http://zh.wikipedia.org/zh/%E6%9C%80%E5%A4%A7%E4%B8%8B%E7%95%8C


      • ningyu says:

        对于第一个问题,kkt条件中只要求lambda_{i}>=0,没有说nu_{i}也要大于0啊,而且你在文章中写的是>0,不是大于等于0,不知道我说的对不。
        第二个问题,维基说是“下确界或最大下界被指示为 inf(S),并被定义为小于等于在 S 中的所有数的最大实数”,应该是max minL(x,r,v)吧(不会写latex……)
        多谢回复


        • liyun says:

          KTT是对所有的约束条件都适用的,所以所有的拉格朗日乘子都要大于等于0.至于是不是严格的大于0,如果严格的大于就是紧约束(达到约束的边界),否则就是松约束(有没有都没有差别)。我觉得这里影响不大吧...
          至于inf还是min...我觉得这里也没太大差别... -_-|| 不过对偶问题一定是最小化的(如果原问题是最大化的).


Leave a Reply

Your email address will not be published. Required fields are marked *