CS229 笔记 07

Nov 20 2017

Optimal Margin Classifier

  • 回顾 SVM

    hw,b=g(wTx+b)g(z)={1z≥0−1z<0y∈{−1,1}ˆγ(i)=y(i)(wTx+b)γ(i)=y(i)(wT||w||x+b||w||)ˆγ=miniˆγ(i)γ=miniγ(i)

  • Optimal Margin Classifier（最大间隔分类器）

    由于函数间隔 ˆγ​ 是可以通过改变 w 和 b​ 来任意缩放的，所以这里说的「最大间隔」 指的是几何间隔 γ​ ，而几何间隔所需要满足的条件是，对于任意的样本 (x(i),y(i))​ ，都有 γ(i)≥γ​ ，即：

    maxγs.t.y(i)(wT||w||x+b||w||)≥γ

    这就是最大间隔分类器最原始的想法，在满足所有样本到超平面的距离都大于 γ 的前提下，最大化这个 γ 。但是这就有一个问题，当找到这么一组 (w,b) 满足上面的最优化条件后， (2w,2b) 也将满足上面的最优化条件（因为 (w,b) 和 (2w,2b) 其实就是同一个超平面），所以需要限定一下缩放的原则，比如规定 ||w||=1 ，或者 w1=1 等等，这个原则可以有多种方式选定。假设约定 ||w||=1 ，那么上面的优化问题就转变成以下的形式：

    maxγs.t.y(i)(wTx(i)+b)≥γ and ||w||=1

    然而这并不是一个很好的优化问题，因为这个 ||w||=1 是一个很糟糕的非凸性约束（ w 将在一个球面上取值，而球面集并不是一个凸集），所以还需要把优化问题再换一种表达方式。既然在约束条件里面很难给 W 作一个约束（因为很难找到一个约束条件既能防止 w 任意缩放，又能保证 w 的取值集合是一个凸集），那么可以尝试把 w 放到目标优化函数里面：

    maxγ=maxˆγ||w||s.t.y(i)(wTx(i)+b)≥ˆγ

    但是这时候目标函数 ˆγ/||w|| 又不是一个凸函数了。注意到 ˆγ 是可以任意缩放的，那么可以令 ˆγ=1 ，得到：

    max1||w||s.t.y(i)(wTx(i)+b)≥1

    把最大化目标函数转为最小化其倒数，并平方：

    min||w||2s.t.y(i)(wTx(i)+b)≥1

    这就是最大间隔分类器的最终形式，其目标优化函数是一个凸函数，约束集是一个凸集。

Lagrange Multiplier

  • Lagrange Multiplier（拉格朗日常数法）的一般形式

    要解决的问题为：

    minf(w)s.t.hi(w)=0,(i=1,2,⋯,l)

    要求解以上问题，首先要创建一个拉格朗日算子：

    L(w,β)=f(w)+∑iβihi(w)

    其中的 βi 被称为 Lagrange Multiplier（拉格朗日乘数）。

    然后令它的偏导数为 0，求解方程组即可：

    ∂L(w,β)∂w=0∂L(w,β)∂β=0

  • Lagrange Multiplier（拉格朗日常数法）的扩展形式

    要求解的问题为：

    minwf(w)s.t.gi(w)≤0,(i=1,2,⋯,k)hi(w)=0,(i=1,2,⋯,l)

    拉格朗日算子为：

    L(w,α,β)=f(w)+k∑i=1αigi(w)+l∑i=1βihi(w)

    定义 ΘP(w) 为：

    ΘP(w)def=maxα,β,s.t.α≥0L(w,α,β)

    现在考虑另一个优化问题：

    p∗=minwmaxα,β,s.t.α≥0L(w,α,β)=minwΘP(w)

    若 gi(w)>0 ，不满足条件 (1) ，那么根据等式 (3) 和 (4) ， ΘP(w) 将是一个无穷大值。若 hi(w)≠0 ，不满足条件 (2) ，同理 ΘP(w) 也将是一个无穷大值。

    若同时满足条件 (1) 和条件 (2) ，那么显然：

    ΘP(w)=f(w)

    所以原来的优化问题也转变成新的优化问题：

    minwf(w)=minwΘP(w)=p∗

Dual Problem

  • Dual Problem（对偶问题）

    定义： ΘD(α,β)=minwL(w,α,β)d∗=maxα,β,s.t.α≥0minwL(w,α,β)=maxα,β,s.t.α≥0ΘD(α,β)

    则 d∗ 就是 p∗ 的对偶问题，其实就是交换了 min 和 max 的位置。在通常情况下， d∗≤p∗ ，而这两个优化问题会有相同的解。

  • 以上问题的完整表述

    令 f 是凸函数，假设 hi(w) 是仿射函数，即 hi(w)=αTiw+bi 。再假设：

    ∃w, s.t.∀igi(w)<0

    那么，将存在 w∗ ， α∗ ， β∗ ，使得 w∗ 是原始问题 p∗ 的解， α∗ 和 β∗ 是对偶问题 d∗ 的解，并且 p∗=d∗=L(w∗,α∗,β∗) ，且：

    ∂∂wL(w∗,α∗,β∗)=0∂∂βL(w∗,α∗,β∗)=0α∗igi(w∗)=0gi(w∗)≤0α∗i≥0

重新回到最大间隔分类器

  • 准备工作

    回顾一下最大间隔分类器要优化的目标：

    min12||w||2s.t.y(i)(wTx(i)+b)≥1

    令 g(w,b)=1−y(i)(wTx(i)+b)≤0 。

    拉格朗日算子为（由于只有不等式约束，没有等式约束，所以只有参数 α ，没有参数 β ：

    L(w,b,α)=12||w||2−m∑i=1αi[y(i)(wTx(i)+b)−1]

    其对偶问题为：

    ΘD(α)=maxw,bL(w,b,α)

    要想最小化目标函数，只要用目标函数对 w 求偏导，令偏导等于 0，解方程即可：

    ∂∂wL(w,b,α)=∂∂w{12||w||2−m∑i=1αi[y(i)(wTx(i)+b)−1]}=w−m∑i=1αiy(i)x(i)set=0∴w=m∑i=1αiy(i)x(i)

    用目标函数对 b 求导，得到：

    ∂∂bL(w,b,α)=∂∂b{12||w||2−m∑i=1αi[y(i)(wTx(i)+b)−1]}=−m∑i=1αiy(i)set=0∴m∑i=1αiy(i)=0

    这是一个约束条件，现在暂时还无法解出 b 。

    将上面的结果代入 L(w,b,α) ：

    L(w,b,α)=12||w||2−m∑i=1αi[y(i)(wTx(i)+b)−1]=12wTw−m∑i=1αi[y(i)(wTx(i)+b)−1]=12(m∑i=1αiy(i)x(i))T(m∑i=1αiy(i)x(i))−m∑i=1αi[y(i)((m∑i=1αiy(i)x(i))Tx(i)+b)−1]=12(m∑i,jαiαjy(i)y(j)⟨x(i),x(j)⟩)−m∑i=1αiy(i)(m∑i=1αiy(i)x(i))Tx(i)−m∑i=1αiy(i)b+m∑i=1αi=12(m∑i,jαiαjy(i)y(j)⟨x(i),x(j)⟩)−m∑i,jαiαjy(i)y(j)⟨x(i),x(j)⟩−m∑i=1αiy(i)b+m∑i=1αi=m∑i=1αi−12(m∑i,jαiαjy(i)y(j)⟨x(i),x(j)⟩)def=W(α)

    所以对偶问题为：

    ΘD(α)=maxw,bL(w,b,α)=maxw,b{m∑i=1αi−12(m∑i,jαiαjy(i)y(j)⟨x(i),x(j)⟩)}=maxw,bW(α)s.t.αi≥0m∑i=1αiy(i)=0

  • 解决 SVM 最大间隔分类器问题的步骤

    1. 首先解决对偶问题，求出 α∗

    2. 然后代入 w=∑mi=1αiy(i)x(i) 求出 w

    3. 最后由于 b 代表着超平面的截距，所以只需将 b 设置在最大间隔的中间即可。

  • 模型训练之后的预测过程：

    对于一个新样本 x ，预测函数 hw,b(x) 为：

    hw,b(x)=g(wTx+b)=g(m∑i=1αiy(i)⟨x(i),x⟩+b)

Machine Learning