CS229 笔记07
Optimal Margin Classifier
-
回顾SVM
\[
\begin{eqnarray*}
h_{w,b}&=&g(w^{\rm T}x+b)\\[1em]
g(z)&=&\begin{cases}1&z\geq0\\[1em]-1&z<0\end{cases}\\[1em]
y&\in&\{-1,1\}\\[1em]
\hat\gamma^{(i)}&=&y^{(i)}\left(w^{\rm T}x+b\right)\tag{Functional Margin}\\[1em]
\gamma^{(i)}&=&y^{(i)}\left(\frac{w^{\rm T}}{||w||}x+\frac{b}{||w||}\right)\tag{Geometric Margin}\\[1em]
\hat\gamma&=&\min_i \hat\gamma^{(i)}\\[1em]
\gamma&=&\min_i \gamma^{(i)}\\[1em]
\end{eqnarray*}
\] -
Optimal Margin Classifier（最大间隔分类器）
由于函数间隔 \(\hat\gamma\) 是可以通过改变 \(w\) 和 \(b\) 来任意缩放的，所以这里说的“最大间隔”指的是几何间隔 \(\gamma\) ，而几何间隔所需要满足的条件是，对于任意的样本 \((x^{(i)},y^{(i)})\) ，都有 \(\gamma^{(i)}\geq\gamma\) ，即：
\[
\max \gamma\\
{\text{s.t. }}y^{(i)}\left(\frac{w^{\rm T}}{||w||}x+\frac{b}{||w||}\right)\geq\gamma
\]这就是最大间隔分类器最原始的想法，在满足所有样本到超平面的距离都大于 \(\gamma\) 的前提下，最大化这个 \(\gamma\) 。但是这就有一个问题，当找到这么一组 \((w,b)\) 满足上面的最优化条件后， \((2w,2b)\) 也将满足上面的最优化条件（因为 \((w,b)\) 和 \((2w,2b)\) 其实就是同一个超平面），所以需要限定一下缩放的原则，比如规定 \(||w||=1\) ，或者 \(w_1=1\) 等等，这个原则可以有多种方式选定。假设约定 \(||w||=1\) ，那么上面的优化问题就转变成以下的形式：
\[
\max \gamma\\
{\text{s.t. }}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq\gamma {\text{ and }} ||w||=1
\]然而这并不是一个很好的优化问题，因为这个 \(||w||=1\) 是一个很糟糕的非凸性约束（ \(w\) 将在一个球面上取值，而球面集并不是一个凸集），所以还需要把优化问题再换一种表达方式。既然在约束条件里面很难给 \(W\) 作一个约束（因为很难找到一个约束条件既能防止 \(w\) 任意缩放，又能保证 \(w\) 的取值集合是一个凸集），那么可以尝试把 \(w\) 放到目标优化函数里面：
\[
\max \gamma=\max \frac{\hat\gamma}{||w||}\\
{\text{s.t. }}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq\hat\gamma
\]但是这时候目标函数 \(\hat\gamma/||w||\) 又不是一个凸函数了。注意到 \(\hat\gamma\) 是可以任意缩放的，那么可以令 \(\hat\gamma=1\) ，得到：
\[
\max \frac{1}{||w||}\\
{\text{s.t. }}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1
\]把最大化目标函数转为最小化其倒数，并平方：
\[
\min ||w||^2\\
{\text{s.t. }}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1
\]这就是最大间隔分类器的最终形式，其目标优化函数是一个凸函数，约束集是一个凸集。
Lagrange Multiplier
-
Lagrange Multiplier（拉格朗日常数法）的一般形式
要解决的问题为：
\[
\min f(w)\\
{\text{s.t. }}h_i(w)=0,\,(i=1,2,\cdots,l)
\]要求解以上问题，首先要创建一个拉格朗日算子：
\[
{\mathcal L}(w,\beta)=f(w)+\sum_i\beta_ih_i(w)
\]其中的 \(\beta_i\) 被称为Lagrange Multiplier（拉格朗日乘数）。
然后令它的偏导数为0，求解方程组即可：
\[
\begin{eqnarray*}
\frac{\partial{\mathcal L}(w,\beta)}{\partial w}&=&0\\[1em]
\frac{\partial {\mathcal L}(w,\beta)}{\partial\beta}&=&0\\[1em]
\end{eqnarray*}
\] -
Lagrange Multiplier（拉格朗日常数法）的扩展形式
要求解的问题为：
\[
\min_w f(w)\\
\begin{eqnarray*}
{\text{s.t. }}g_i(w)&\leq&0,\,(i=1,2,\cdots,k)\tag{1}\\
h_i(w)&=&0,\,(i=1,2,\cdots,l)\tag{2}\\
\end{eqnarray*}
\]拉格朗日算子为：
\[
{\mathcal L}(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^l\beta_ih_i(w)\tag{3}
\]定义 \(\Theta_P(w)\) 为：
\[
\Theta_P(w)\xlongequal{def}\max_{\alpha,\beta,\,{\text{s.t.}}\,\alpha\geq0}{\mathcal L}(w,\alpha,\beta)\tag{4}
\]现在考虑另一个优化问题：
\[
p^*=\min_w\max_{\alpha,\beta,\,{\text{s.t.}}\,\alpha\geq0}{\mathcal L}(w,\alpha,\beta)=\min_w\Theta_P(w)
\]若 \(g_i(w)>0\) ，不满足条件 \((1)\) ，那么根据等式 \((3)\) 和 \((4)\) ， \(\Theta_P(w)\) 将是一个无穷大值。若 \(h_i(w)\neq0\) ，不满足条件 \((2)\) ，同理 \(\Theta_P(w)\) 也将是一个无穷大值。
若同时满足条件 \((1)\) 和条件 \((2)\) ，那么显然：
\[
\Theta_P(w)=f(w)
\]所以原来的优化问题也转变成新的优化问题：
\[
\min_w f(w)=\min_w \Theta_P(w)=p^*
\]
Dual Problem
-
Dual Problem（对偶问题）
定义：
\[
\Theta_D(\alpha, \beta)=\min_w{\mathcal L}(w,\alpha,\beta)\\
d^*=\max_{\alpha,\beta,\,{\text{s.t.}}\,\alpha\geq0}\min_w{\mathcal L}(w,\alpha,\beta)=\max_{\alpha,\beta,\,{\text{s.t.}}\,\alpha\geq0}\Theta_D(\alpha,\beta)
\]
则 \(d^*\) 就是 \(p^*\) 的对偶问题，其实就是交换了 \(\min\) 和 \(\max\) 的位置。在通常情况下， \(d^*\leq p^*\) ，而这两个优化问题会有相同的解。 -
以上问题的完整表述
令 \(f\) 是凸函数，假设 \(h_i(w)\) 是仿射函数，即 \(h_i(w)=\alpha_i^{\rm T}w+b_i\) 。再假设：
\[
\exists w, {\text { s.t. }} \forall_i\, g_i(w)<0
\]那么，将存在 \(w^*\) ， \(\alpha^*\) ， \(\beta^*\) ，使得 \(w^*\) 是原始问题 \(p^*\) 的解， \(\alpha^*\) 和 \(\beta^*\) 是对偶问题 \(d^*\) 的解，并且 \(p^*=d^*={\mathcal L}(w^*,\alpha^*,\beta^*)\) ，且：
\[
\begin{eqnarray*}
\frac{\partial}{\partial w}{\mathcal L}(w^*,\alpha^*,\beta^*)&=&0\\[1em]
\frac{\partial}{\partial \beta}{\mathcal L}(w^*,\alpha^*,\beta^*)&=&0\\[1em]
\alpha_i^*g_i(w^*)&=&0\\[1em]
g_i(w*)&\leq&0\\[1em]
\alpha_i^*&\geq&0\\[1em]
\end{eqnarray*}
\]
重新回到最大间隔分类器
-
准备工作
回顾一下最大间隔分类器要优化的目标：
\[
\min \frac{1}{2}||w||^2\\
{\text {s.t. }}y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\geq1
\]令 \(g(w,b)=1-y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)\leq0\) 。
拉格朗日算子为（由于只有不等式约束，没有等式约束，所以只有参数 \(\alpha\) ，没有参数 \(\beta\) ：
\[
{\mathcal L}(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1\right]
\]其对偶问题为：
\[
\Theta_D(\alpha)=\max_{w,b}{\mathcal L}(w,b,\alpha)
\]要想最小化目标函数，只要用目标函数对 \(w\) 求偏导，令偏导等于0，解方程即可：
\[
\begin{eqnarray*}
&&\frac{\partial}{\partial w}{\mathcal L}(w,b,\alpha)\\[1em]
&=&\frac{\partial}{\partial w}\left\{\frac{1}{2}||w||^2-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1\right]\right\}\\[1em]
&=&w-\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\xlongequal{set}0\\[1em]
\therefore\,w&=&\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)} \\[1em]
\end{eqnarray*}\\[1em]
\]用目标函数对 \(b\) 求导，得到：
\[
\begin{eqnarray*}
&&\frac{\partial}{\partial b}{\mathcal L}({w,b,\alpha})\\[1em]
&=&\frac{\partial}{\partial b}\left\{\frac{1}{2}||w||^2-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1\right]\right\}\\[1em]
&=&-\sum_{i=1}^m\alpha_iy^{(i)}\xlongequal{set}0\\[1em]
&\therefore&\,\sum_{i=1}^m\alpha_iy^{(i)}=0 \tag{5} \\[1em]
\end{eqnarray*}
\]这是一个约束条件，现在暂时还无法解出 \(b\) 。
将上面的结果代入 \({\mathcal L}(w,b,\alpha)\) ：
\[
\begin{eqnarray*}
&&{\mathcal L}(w,b,\alpha)\\[1em]
&=&\frac{1}{2}||w||^2-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1\right]\\[1em]
&=&\frac{1}{2}w^{\rm T}w-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(w^{\rm T}x^{(i)}+b\right)-1\right]\\[1em]
&=&\frac{1}{2}\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)^{\rm T}\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)-\sum_{i=1}^m\alpha_i\left[y^{(i)}\left(\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)^{\rm T}x^{(i)}+b\right)-1\right]\\[1em]
&=&\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right)-\sum_{i=1}^m\alpha_iy^{(i)}\left(\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\right)^{\rm T}x^{(i)}-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i\\[1em]
&=&\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right)-\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle-\sum_{i=1}^m\alpha_iy^{(i)}b+\sum_{i=1}^m\alpha_i\tag{Eq.5}\\[1em]
&=&\sum_{i=1}^m\alpha_i-\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right)\\[1em]
&\xlongequal{def}&W(\alpha)\\[1em]
\end{eqnarray*}
\]所以对偶问题为：
\[
\begin{eqnarray*}
\Theta_D(\alpha)&=&\max_{w,b}{\mathcal L}(w,b,\alpha)\\[1em]
&=&\max_{w,b}\left\{\sum_{i=1}^m\alpha_i-\frac{1}{2}\left(\sum_{i,j}^m\alpha_i\alpha_jy^{(i)}y^{(j)}\left\langle x^{(i)},x^{(j)}\right\rangle\right)\right\}\\[1em]
&=&\max_{w,b}W(\alpha)\\[1em]
{\text{s.t. }}&&\alpha_i\geq0\\[1em]
&&\sum_{i=1}^m\alpha_iy^{(i)}=0\\[1em]
\end{eqnarray*}
\] -
解决SVM最大间隔分类器问题的步骤
首先解决对偶问题，求出 \(\alpha^*\)
然后代入 \(w=\sum_{i=1}^m\alpha_iy^{(i)}x^{(i)}\) 求出 \(w\)
最后由于 \(b\) 代表着超平面的截距，所以只需将 \(b\) 设置在最大间隔的中间即可。
-
模型训练之后的预测过程：
对于一个新样本 \(x\) ，预测函数 \(h_{w,b}(x)\) 为：
\[
\begin{eqnarray*}
h_{w,b}(x)&=&g(w^{\rm T}x+b)\\
&=&g\left(\sum_{i=1}^m\alpha_iy^{(i)}\left\langle x^{(i)},x \right\rangle+b\right)
\end{eqnarray*}
\]