Support Vector Regression（SVR）

上一篇中的内容是 KLR（kernel logistic regression） <script type="math/tex" id="MathJax-Element-1">KLR（kernel\ logistic\ regression）</script>。这个问题的出发点是我们想要把 SVM <script type="math/tex" id="MathJax-Element-2">SVM</script>这个强大的工具用在 soft binary classification <script type="math/tex" id="MathJax-Element-3">soft\ binary\ classification</script>上，我们有两种选择： 第一种方法可以称之为 two level learning <script type="math/tex" id="MathJax-Element-4">two\ level\ learning</script>：第一阶段做 SVM <script type="math/tex" id="MathJax-Element-5">SVM</script>；第二阶段将 SVM <script type="math/tex" id="MathJax-Element-6">SVM</script>的结果使用 logistic regression <script type="math/tex" id="MathJax-Element-7">logistic\ regression</script>进行微调。第二种方法是使用 representer theorem <script type="math/tex" id="MathJax-Element-8">representer\ theorem</script>理论直接将 logistic regression <script type="math/tex" id="MathJax-Element-9">logistic\ regression</script>转换为一个 kernel <script type="math/tex" id="MathJax-Element-10">kernel</script>的形式。这篇将简单讲述如何将一般的 regression <script type="math/tex" id="MathJax-Element-11">regression</script>变为 kernel <script type="math/tex" id="MathJax-Element-12">kernel</script>的形式。

Kernel Ridge Regression

回顾Representer Theorem

如果求解的问题是带有 regularized <script type="math/tex" id="MathJax-Element-13">regularized</script>（ L2 <script type="math/tex" id="MathJax-Element-14">L2</script>- regularization <script type="math/tex" id="MathJax-Element-15">regularization</script>）的 linear model <script type="math/tex" id="MathJax-Element-16">linear\ model</script>，那么最佳的 w <script type="math/tex" id="MathJax-Element-17">w</script>将是z<script type="math/tex" id="MathJax-Element-18">z</script>的线性组合。即任何的 L2 <script type="math/tex" id="MathJax-Element-19">L2</script>- regularized <script type="math/tex" id="MathJax-Element-20">regularized</script>的 linear model <script type="math/tex" id="MathJax-Element-21">linear\ model</script>都可以变为 kernel <script type="math/tex" id="MathJax-Element-22">kernel</script>的形式。那么如何利用这个理论基础把之前学习过的 regression <script type="math/tex" id="MathJax-Element-23">regression</script>变为 kernel <script type="math/tex" id="MathJax-Element-24">kernel</script>的形式将是我们这节的重点。

线性回归

在线性回归中我们使用平方误差来衡量真实值和预测值之间的 error( <script type="math/tex" id="MathJax-Element-25">error(</script>称为 square error) <script type="math/tex" id="MathJax-Element-26">square\ error)</script>，然后通过最小化这个 error <script type="math/tex" id="MathJax-Element-27">error</script>来得到最佳的解。

err(y,wTz)=(y−wTz)2
<script type="math/tex; mode=display" id="MathJax-Element-28">err(y, w^Tz) = (y - w^Tz)^2</script>
如果在线性回归的基础上加上 regularization <script type="math/tex" id="MathJax-Element-29">regularization</script>的话得到的模型我们称之为 ridge regression <script type="math/tex" id="MathJax-Element-30">ridge\ regression</script>，即有 regularization <script type="math/tex" id="MathJax-Element-31">regularization</script>的 linearregression <script type="math/tex" id="MathJax-Element-32">linear regression</script>的形式。这节将讲述的是， 怎么把 ridge regression <script type="math/tex" id="MathJax-Element-33">ridge\ regression</script>加上 kernel <script type="math/tex" id="MathJax-Element-34">kernel</script>得到我们想要的 kernel ridge regression <script type="math/tex" id="MathJax-Element-35">kernel\ ridge\ regression</script>。

在 linear regression <script type="math/tex" id="MathJax-Element-36">linear\ regression</script>或者是 ridge regression <script type="math/tex" id="MathJax-Element-37">ridge\ regression</script>中，我们可以得到问题的 analytic solution <script type="math/tex" id="MathJax-Element-38">analytic\ solution</script>。即解析解。同样我们希望 kernel ridge regression <script type="math/tex" id="MathJax-Element-39">kernel\ ridge\ regression</script>也可以有 analytic solution <script type="math/tex" id="MathJax-Element-40">analytic\ solution</script>。

Kernel Ridge Regression问题

ridge regression <script type="math/tex" id="MathJax-Element-41">ridge\ regression</script>问题可以由如下的 (1) <script type="math/tex" id="MathJax-Element-42">(1)</script>式描述：

minw最佳解满足：λNwTw+1N∑n=1N(yn−wTzn)2w∗=∑n=1Nβnzn(1)
<script type="math/tex; mode=display" id="MathJax-Element-43">\begin{align} \mathop{min}\limits_{w}\quad &\frac{\lambda}{N}w^Tw+\frac1N\sum_{n=1}^{N}(y_n - w^Tz_n)^2 \tag1\\ 最佳解满足：\quad & w_* = \sum_{n=1}^{N}\beta_nz_n \end{align}</script>

因为已经知道了最佳解的形式，所以我们可以将最佳解带入原始的问题当中，这样就将问题从求解 w <script type="math/tex" id="MathJax-Element-44">w</script>变为求解β<script type="math/tex" id="MathJax-Element-45">\beta</script>。

minβλN∑n=1N∑m=1NβnβmzTnzm+1N∑n=1N(yn−∑m=1NβmzTmzn)2
<script type="math/tex; mode=display" id="MathJax-Element-46">\mathop{min}\limits_{\beta}\quad \frac{\lambda}{N}\sum_{n=1}^{N}\sum_{m=1}^{N}\beta_n\beta_mz_n^Tz_m + \frac{1}{N}\sum_{n=1}^{N}\bigg(y_n - \sum_{m=1}^{N}\beta_mz_m^Tz_n\bigg)^2</script>
这样就可以使用 核技巧得到如下的 Kernel Ridge Regression <script type="math/tex" id="MathJax-Element-47">Kernel\ Ridge\ Regression</script>问题：
minβλN∑n=1N∑m=1NβnβmK(xn,xm)□+1N∑n=1N(yn−∑m=1NβmK(xm,xn))2◯
<script type="math/tex; mode=display" id="MathJax-Element-48">\mathop{min}\limits_{\beta}\quad \frac{\lambda}{N} \underbrace{\sum_{n=1}^{N}\sum_{m=1}^{N}\beta_n\beta_mK(x_n, x_m)}_{\square} + \frac{1}{N}\underbrace{\sum_{n=1}^{N}\bigg(y_n - \sum_{m=1}^{N}\beta_mK(x_m, x_n)\bigg)^2}_{\bigcirc}</script>

原来要求解的是一个关于 w <script type="math/tex" id="MathJax-Element-49">w</script>的问题，现在根据representer theorem<script type="math/tex" id="MathJax-Element-50">representer\ theorem</script>转换为一个求解关于 β <script type="math/tex" id="MathJax-Element-51">\beta</script>的问题，这样就隐含的将原来关于 w <script type="math/tex" id="MathJax-Element-52">w</script>的问题求解了， 在求解β<script type="math/tex" id="MathJax-Element-53">\beta</script>的问题时可以使用 kernel trick <script type="math/tex" id="MathJax-Element-54">kernel\ trick</script>将所有 z <script type="math/tex" id="MathJax-Element-55">z</script>和z<script type="math/tex" id="MathJax-Element-56">z</script>的乘积换成是 Kernel <script type="math/tex" id="MathJax-Element-57">Kernel</script>的形式。这样就得到了 Kernel Ridge Regression <script type="math/tex" id="MathJax-Element-58">Kernel\ Ridge\ Regression</script>。
可以将 kernel ridge regression <script type="math/tex" id="MathJax-Element-59">kernel\ ridge\ regression</script>看做是 β <script type="math/tex" id="MathJax-Element-60">\beta</script>的线性模型，其中 □ <script type="math/tex" id="MathJax-Element-61">\square</script>和 β <script type="math/tex" id="MathJax-Element-62">\beta</script>的复杂度有关； ◯ <script type="math/tex" id="MathJax-Element-63">\bigcirc</script>则是 β <script type="math/tex" id="MathJax-Element-64">\beta</script>的线性组合，组合的项是经过 kernel <script type="math/tex" id="MathJax-Element-65">kernel</script>转换之后的特征。所以 □ <script type="math/tex" id="MathJax-Element-66">\square</script>是 β <script type="math/tex" id="MathJax-Element-67">\beta</script>的一个 regularizer <script type="math/tex" id="MathJax-Element-68">regularizer</script>， ◯ <script type="math/tex" id="MathJax-Element-69">\bigcirc</script>是 error <script type="math/tex" id="MathJax-Element-70">error</script>的部分。

化简为矩阵的形式：

minβλNβTKβ+1N(βTKTKβ−2βTKTy+yTy)
<script type="math/tex; mode=display" id="MathJax-Element-71">\mathop{min}\limits_{\beta}\frac{\lambda}{N}\beta^TK\beta + \frac1N (\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty)</script>

如果我们可以求得这个问题的解，那么就可以将之前学到过的 kernel <script type="math/tex" id="MathJax-Element-72">kernel</script>（多项式核，高斯核等）用在 ridge regression <script type="math/tex" id="MathJax-Element-73">ridge\ regression</script>上，

如何求解Kernel Ridge Regression

Kernel Ridge Regression

minβλNβTKβ+1N(βTKTKβ−2βTKTy+yTy)
<script type="math/tex; mode=display" id="MathJax-Element-74">\mathop{min}\limits_{\beta}\frac{\lambda}{N}\beta^TK\beta + \frac1N (\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty) </script>
这个问题是一个无约束的最优化问题，所以先求梯度
Eaug(β)=λNβTKβ+1N(βTKTKβ−2βTKTy+yTy)
<script type="math/tex; mode=display" id="MathJax-Element-75">E_{aug}(\beta) = \frac{\lambda}{N}\beta^TK\beta + \frac1N (\beta^TK^TK\beta-2\beta^TK^Ty+y^Ty)</script>
▽Eaug(β)=2λNKβ+1N(2KTKβ−2KTy)=2N(λKTIβ+KTKβ−KTy)=2NKT((λI+K)β−y)
<script type="math/tex; mode=display" id="MathJax-Element-76">\begin{align} \triangledown E_{aug}(\beta) & = \frac{2\lambda}{N}K\beta+\frac1N(2K^TK\beta-2K^Ty) \\ & = \frac{2}{N}(\lambda K^TI\beta + K^TK\beta - K^Ty) \\ & = \frac2NK^T\bigg((\lambda I + K)\beta - y\bigg) \end{align}</script>

我们想要求解 β <script type="math/tex" id="MathJax-Element-77">\beta</script>使得梯度为0，即 ▽Eaug(β)=0 <script type="math/tex" id="MathJax-Element-78">\triangledown E_{aug}(\beta) = 0</script>，所以可以使得 (λI+K)β−y=0 <script type="math/tex" id="MathJax-Element-79">(\lambda I + K)\beta - y = 0</script>， 解得：

β=(λI+K)−1y
<script type="math/tex; mode=display" id="MathJax-Element-80">\beta = (\lambda I+K)^{-1}y</script>

  • 当 λ>0 <script type="math/tex" id="MathJax-Element-81">\lambda>0</script>时 (⋅)−1 <script type="math/tex" id="MathJax-Element-82">(\centerdot)^{-1}</script>总是存在的，因为 K <script type="math/tex" id="MathJax-Element-83">K</script>是半正定的（根据Mercer’s condition），λI+K<script type="math/tex" id="MathJax-Element-84">\lambda I+K</script>是正定的。

这样就可以求出最佳的 β <script type="math/tex" id="MathJax-Element-85">\beta</script>，这样就得到了 ridge regression <script type="math/tex" id="MathJax-Element-86">ridge\ regression</script>在 Z <script type="math/tex" id="MathJax-Element-87">Z</script>空间中的解。

所以理论上，我们现在可以很轻易的做non linear regression<script type="math/tex" id="MathJax-Element-88">non\ linear\ regression</script>。之前为了做 non linear regression <script type="math/tex" id="MathJax-Element-89">non\ linear\ regression</script>，需要先使用非线性的转化，然后做 linear regression <script type="math/tex" id="MathJax-Element-90">linear\ regression</script>，就可以做一个 nonlinearregression <script type="math/tex" id="MathJax-Element-91">non linear regression</script>；现在知道了另一种做 non linear regression <script type="math/tex" id="MathJax-Element-92">non\ linear\ regression</script>的方法，直接通过 kernel <script type="math/tex" id="MathJax-Element-93">kernel</script>求解在 Z <script type="math/tex" id="MathJax-Element-94">Z</script>空间中的最优解。

最终得到的kernel ridge regression<script type="math/tex" id="MathJax-Element-95">kernel\ ridge\ regression</script>的模型：

g(x)=∑n=1NβnK(xn,x)
<script type="math/tex; mode=display" id="MathJax-Element-96">g(x) = \sum_{n=1}^{N}\beta_nK(x_n, x)</script>

实例结果对比


这里写图片描述

  • 左边是 linear ridge regression <script type="math/tex" id="MathJax-Element-370">linear\ ridge\ regression</script>的解
    • w=(λI+XTX)−1XTy <script type="math/tex" id="MathJax-Element-371">w = (\lambda I + X^TX)^{-1}X^Ty</script>
  • 右边是 kernel ridge regression <script type="math/tex" id="MathJax-Element-372">kernel\ ridge\ regression</script>的解
    • β=(λI+K)−1y <script type="math/tex" id="MathJax-Element-373">\beta = (\lambda I + K)^{-1}y</script>

在 linear ridge regression <script type="math/tex" id="MathJax-Element-374">linear\ ridge\ regression</script>中 (λI+XTX) <script type="math/tex" id="MathJax-Element-375"> (\lambda I + X^TX)</script>是 d×d <script type="math/tex" id="MathJax-Element-376">d\times d</script>的，该算法时间复杂度可以记为 O(d3+d2N) <script type="math/tex" id="MathJax-Element-377">O(d^3+d^2N)</script>；在 kernel ridge regression <script type="math/tex" id="MathJax-Element-378">kernel\ ridge\ regression</script>中 (λI+K) <script type="math/tex" id="MathJax-Element-379"> (\lambda I + K)</script>是 N×N <script type="math/tex" id="MathJax-Element-380">N\times N</script>的。时间复杂度为 O(N3) <script type="math/tex" id="MathJax-Element-381">O(N^3)</script>。

小结

所以当 N>d <script type="math/tex" id="MathJax-Element-109">N>d</script>的时候，使用 linear ridge regression <script type="math/tex" id="MathJax-Element-110">linear\ ridge\ regression</script>比较有效；当资料量 N <script type="math/tex" id="MathJax-Element-111">N</script>很大的时候，kernel ridge regression<script type="math/tex" id="MathJax-Element-112">kernel\ ridge\ regression</script>是比较难做的，但是它有很大的自由度，可以做出复杂的曲线。所以使用线性的模型，通常关注的是模型的复杂度和效率；但是当问题很复杂的时候，通常会使用 kernel <script type="math/tex" id="MathJax-Element-113">kernel</script>来对数据进行建模，只是缺点就是要付出计算上的复杂度。

Support Vector Regression Primal

软间隔SVM和LSSVM

linear regression <script type="math/tex" id="MathJax-Element-421">linear\ regression</script>可以用来做 classification <script type="math/tex" id="MathJax-Element-422">classification</script>，所以 kernel ridge regression <script type="math/tex" id="MathJax-Element-423">kernel\ ridge\ regression</script>也可以用来做 classification <script type="math/tex" id="MathJax-Element-424">classification</script>。用于 classification <script type="math/tex" id="MathJax-Element-425">classification</script>的 kernel ridge regression <script type="math/tex" id="MathJax-Element-426">kernel\ ridge\ regression</script>有一个特别的名字叫做 least squares SVM(LSSVM) <script type="math/tex" id="MathJax-Element-427">least\ squares\ SVM(LSSVM)</script>， least squares <script type="math/tex" id="MathJax-Element-428">least\ squares</script>在强调的是，它所使用的是 error <script type="math/tex" id="MathJax-Element-429">error</script>是 square error <script type="math/tex" id="MathJax-Element-430">square\ error</script>。

对同样的资料分别利用使用 soft margin Gaussian SVM <script type="math/tex" id="MathJax-Element-431">soft\ margin\ Gaussian\ SVM</script>和 Gaussian LSSVM <script type="math/tex" id="MathJax-Element-432">Gaussian\ LSSVM</script>进行分类的结果如下：


这里写图片描述

从图中可以看出，分隔边界没有几乎是一致的，但是相比 soft margin Gaussian SVM <script type="math/tex" id="MathJax-Element-433">soft\ margin\ Gaussian\ SVM</script>来说， Gaussian LSSVM <script type="math/tex" id="MathJax-Element-434">Gaussian\ LSSVM</script>得到的支持向量 SV <script type="math/tex" id="MathJax-Element-435">SV</script>（使用方框框起来的点）会更多一些，右图中的每一个都是 support vector <script type="math/tex" id="MathJax-Element-436">support\ vector</script>。为什么会有这样的结果呢？ kernel ridge regression <script type="math/tex" id="MathJax-Element-437">kernel\ ridge\ regression</script>中的 β <script type="math/tex" id="MathJax-Element-438">\beta</script>是使用 β=(λI+K)−1y <script type="math/tex" id="MathJax-Element-439">\beta = (\lambda I+K)^{-1}y</script>算出来，并没有通过加什么限制条件使得这些 β <script type="math/tex" id="MathJax-Element-440">\beta</script>很稀疏。所以得到的每一个 β <script type="math/tex" id="MathJax-Element-441">\beta</script>几乎都不是0，那么所有的点就都是 support vector <script type="math/tex" id="MathJax-Element-442">support\ vector</script>。当 support vector <script type="math/tex" id="MathJax-Element-443">support\ vector</script>很多的时候，在做 predict <script type="math/tex" id="MathJax-Element-444">predict</script>的时候，靠的是和每一个 SV <script type="math/tex" id="MathJax-Element-445">SV</script>算出 kernel <script type="math/tex" id="MathJax-Element-446">kernel</script>然后和 β <script type="math/tex" id="MathJax-Element-447">\beta</script>的乘积和，即， g(x)=∑Nn=1βnK(xn,x) <script type="math/tex" id="MathJax-Element-448">g(x) = \sum_{n=1}^{N}\beta_nK(x_n, x)</script>， 会多花很多的时间。
kernel logistic regression <script type="math/tex" id="MathJax-Element-449">kernel\ logistic\ regression</script>和 kernel ridge regression <script type="math/tex" id="MathJax-Element-450">kernel\ ridge\ regression</script>求出来的都是很 dense <script type="math/tex" id="MathJax-Element-451">dense</script>的 β <script type="math/tex" id="MathJax-Element-452">\beta</script>。而 soft margin SVM <script type="math/tex" id="MathJax-Element-453">soft\ margin\ SVM</script>就具有比较好的性质，最后得到的 α <script type="math/tex" id="MathJax-Element-454">\alpha</script>就是 sparse <script type="math/tex" id="MathJax-Element-455">sparse</script>的，即很多是0，只有少数不是0。这是从 KKT condition <script type="math/tex" id="MathJax-Element-456">KKT\ condition</script>得到的结果。

现在我们想要做的事情是， regression <script type="math/tex" id="MathJax-Element-457">regression</script>能不能像 SVM <script type="math/tex" id="MathJax-Element-458">SVM</script>一样得到比较 sparse <script type="math/tex" id="MathJax-Element-459">sparse</script>的解？

Tube Regression

在使用平方误差 square error <script type="math/tex" id="MathJax-Element-153">square\ error</script>的时候，不管真实值 y <script type="math/tex" id="MathJax-Element-154">y</script>和预测值s=wTx<script type="math/tex" id="MathJax-Element-155">s=w^Tx</script>相差多远，哪怕只是相差一点点，也要记录在 error <script type="math/tex" id="MathJax-Element-156">error</script>中。现在我们对真实值和预测值之间的误差给一个容忍阈值 ϵ <script type="math/tex" id="MathJax-Element-157">\epsilon</script>，也把这个称为 tube <script type="math/tex" id="MathJax-Element-158">tube</script>，当真实值和预测值的差值不超过这个容忍阈值的时候，就不记录该差值。 结合下图就是说：假设容忍阈值的大小为紫色的宽度，那么所有出现在紫色中的点，虽然真实值和预测值之间存在差距，但是不予计较。

也就是说：

  • 如果 |s−y|≤ϵ,⟶error=0 <script type="math/tex" id="MathJax-Element-159">|s - y| \le \epsilon, \longrightarrow error = 0</script>
  • 如果 |s−y|>ϵ,⟶error=|s−y|−ϵ <script type="math/tex" id="MathJax-Element-160">|s - y| > \epsilon, \longrightarrow error = |s-y|-\epsilon</script>

结合以上的讨论得到，如果错的超过了我们的阈值，不计较，此时 |s−y|−ϵ<0 <script type="math/tex" id="MathJax-Element-161">|s - y| - \epsilon < 0</script>，即 err=0 <script type="math/tex" id="MathJax-Element-162">err = 0</script>；如果错的超过了我们的阈值，就将 err <script type="math/tex" id="MathJax-Element-163">err</script>记为超过的部分。

err(y,s)=max(0,|s−y|−ϵ)
<script type="math/tex; mode=display" id="MathJax-Element-471">err(y, s) = max(0, |s-y|-\epsilon)</script>

这个 error <script type="math/tex" id="MathJax-Element-472">error</script>通常被称为 ϵ insensitive error <script type="math/tex" id="MathJax-Element-473">\epsilon\ insensitive\ error</script>，形式很像在 SVM <script type="math/tex" id="MathJax-Element-474">SVM</script>中的 hinge error <script type="math/tex" id="MathJax-Element-475">hinge\ error</script>。这样做也是为了让 regression <script type="math/tex" id="MathJax-Element-476">regression</script>和有 sparse <script type="math/tex" id="MathJax-Element-477">sparse</script>解的 SVM <script type="math/tex" id="MathJax-Element-478">SVM</script>取得关联。


这里写图片描述

我们现在要做的事情是，将带有 L2 regularized <script type="math/tex" id="MathJax-Element-479">L2\ regularized</script>的 tube regression <script type="math/tex" id="MathJax-Element-480">tube\ regression</script>进行一系列的推到得到它的稀疏的解 β <script type="math/tex" id="MathJax-Element-481">\beta</script>。

Tube和Squared Regression对比

  • tube：err(y,s)=max(0,|y−s|−ϵ) <script type="math/tex" id="MathJax-Element-495">tube：err(y, s) = max(0, |y-s|-\epsilon)</script>
    这里写图片描述
  • squared：err(u,s)=(s−y)2 <script type="math/tex" id="MathJax-Element-496">squared：err(u, s) = (s - y)^2</script>
    这里写图片描述

将两种 error <script type="math/tex" id="MathJax-Element-497">error</script>画在下图中，可以看出，当 |y−s| <script type="math/tex" id="MathJax-Element-498">|y-s|</script>比较小的时候， tube <script type="math/tex" id="MathJax-Element-499">tube</script>和 squared <script type="math/tex" id="MathJax-Element-500">squared</script>的 error <script type="math/tex" id="MathJax-Element-501">error</script>其实是很接近的。当 |y−s| <script type="math/tex" id="MathJax-Element-502">|y-s|</script>比较大的时候， squared <script type="math/tex" id="MathJax-Element-503">squared</script>会上升的比较快，而 tube <script type="math/tex" id="MathJax-Element-504">tube</script>则比较平缓。所以 squared <script type="math/tex" id="MathJax-Element-505">squared</script>更容易受到噪音的影响，相对来说可能 tube <script type="math/tex" id="MathJax-Element-506">tube</script>会好一点。稍后会看到，使用 ϵ insensitive error <script type="math/tex" id="MathJax-Element-507">\epsilon\ insensitive\ error</script>这样的方式会让我们得到稀疏的解。


这里写图片描述

L2-Regularized Tube Regression

现在我们要求解的是一个带有 L2 <script type="math/tex" id="MathJax-Element-188">L2</script>- regularize <script type="math/tex" id="MathJax-Element-189">regularize</script>正则化因子的 tube regression <script type="math/tex" id="MathJax-Element-190">tube\ regression</script>问题。

minwλNwTwregularize+1N∑n=1Nmax(0,|wTzn−y|−ϵ)tube error
<script type="math/tex; mode=display" id="MathJax-Element-191">\mathop{min}\limits_{w} \quad \underbrace{\frac{\lambda}{N}w^Tw}_{regularize} + \frac1N\sum_{n=1}^{N} \underbrace{max(0, |w^Tz_n - y| - \epsilon)}_{tube\ error}</script>

回想一下 soft margin SVM <script type="math/tex" id="MathJax-Element-192">soft\ margin\ SVM</script>问题的求解过程， SVM <script type="math/tex" id="MathJax-Element-193">SVM</script>问题解决的是 L2 <script type="math/tex" id="MathJax-Element-194">L2</script>- Regularize <script type="math/tex" id="MathJax-Element-195">Regularize</script>加上 margin violation <script type="math/tex" id="MathJax-Element-196">margin\ violation</script>的最小化问题： min12wTw+C∑margin violation <script type="math/tex" id="MathJax-Element-197">min \frac12w^Tw + C\sum margin\ violation</script>，我们发现直接解决这样的一个问题是困难的，因为同样也会碰到 max <script type="math/tex" id="MathJax-Element-198">max</script>函数无法微分的问题，所以我们重新将其写成了一个 quadratic programming <script type="math/tex" id="MathJax-Element-199">quadratic\ programming</script>的问题，这样就比较容易求解。然后通过求解该问题的对偶问题可以使用 kernel <script type="math/tex" id="MathJax-Element-200">kernel</script>技巧。同时 KKT conditional <script type="math/tex" id="MathJax-Element-201">KKT\ conditional</script>会保证解的稀疏性。

所以我们现在要做的事情就是模仿 SVM <script type="math/tex" id="MathJax-Element-202">SVM</script>的解法来解决 tube regression <script type="math/tex" id="MathJax-Element-203">tube\ regression</script>。所以先要将 tube regression <script type="math/tex" id="MathJax-Element-204">tube\ regression</script>表示成一个 quadratic programming <script type="math/tex" id="MathJax-Element-205">quadratic\ programming</script>的问题。

所以为了使得 tube regression <script type="math/tex" id="MathJax-Element-206">tube\ regression</script>问题和 SVM <script type="math/tex" id="MathJax-Element-207">SVM</script>长的比较像，首先做如下的效的调整， SVM <script type="math/tex" id="MathJax-Element-208">SVM</script>中习惯用的参数是 C <script type="math/tex" id="MathJax-Element-209">C</script>而不是λ<script type="math/tex" id="MathJax-Element-210">\lambda</script>，将 w0 <script type="math/tex" id="MathJax-Element-211">w_0</script>独立出来写作 b <script type="math/tex" id="MathJax-Element-212">b</script>。这样就得到了如下的问题：

Standard Support Vector Regression Primal

SVR Primal

minw,b12wTw+C∑n=1Nmax(0,|wTzn+b−y|−ϵ)
<script type="math/tex; mode=display" id="MathJax-Element-213">\mathop{min}\limits_{w, b} \quad \frac12w^Tw + C\sum_{n=1}^{N}max\big(0, |w^Tz_n + b - y| - \epsilon \big)</script>

变成一个二次规划问题的关键是将 max <script type="math/tex" id="MathJax-Element-214">max</script>变形，为此我们引进了一个新的变量 ξn <script type="math/tex" id="MathJax-Element-215">\xi_n</script>， ξn <script type="math/tex" id="MathJax-Element-216">\xi_n</script>记录了真实值和预测值的差值比 ϵ <script type="math/tex" id="MathJax-Element-217">\epsilon</script>大多少，且 ξn≥0 <script type="math/tex" id="MathJax-Element-218">\xi_n\ge0</script>。

minb,w,ξs.t.12wTw+C∑n=1Nξn|wTzn+b−yn|≤ϵ+ξnξn≥0
<script type="math/tex; mode=display" id="MathJax-Element-219">\begin{align} \mathop{min}\limits_{b,w,\xi} \quad &\frac12w^Tw + C\sum_{n=1}^{N}\xi_n \\ s.t. \quad &|w^Tz_n + b - y_n| \le \epsilon + \xi_n \\ & \xi_n\ge0 \end{align}</script>

还不是 QP <script type="math/tex" id="MathJax-Element-220">QP</script>问题，因为条件不是线性的，需要去掉绝对值。

minb,w,ξs.t.12wTw+C∑n=1N(ξ∧n+ξ∨n)−ϵ−ξ∨n≤yn−wTzn−b≤ϵ+ξ∧nξ∨n≥0,ξ∨n≥0
<script type="math/tex; mode=display" id="MathJax-Element-534">\begin{align} \mathop{min}\limits_{b,w,\xi} \quad &\frac12w^Tw + C\sum_{n=1}^{N}(\xi_n^{\land}+\xi_n^{\lor}) \\ s.t. \quad &-\epsilon - \xi_n^{\lor} \le y_n - w^Tz_n - b \le \epsilon + \xi_n^{\land} \\ & \xi_n^{\lor}\ge0, \xi_n^{\lor}\ge0 \end{align}</script>

现在就得到了一个标准的 QP <script type="math/tex" id="MathJax-Element-535">QP</script>问题。我们将这个问题成为称为标准的 Support Vector Regression(SVR) <script type="math/tex" id="MathJax-Element-536">Support\ Vector\ Regression(SVR)</script>的 Primal <script type="math/tex" id="MathJax-Element-537">Primal</script>问题。

SVR：minimizeregularizer+(upper tube violation ξ∧nand lower tube violations ξ∨n) <script type="math/tex" id="MathJax-Element-538">SVR：minimize \quad regularizer + (upper\ tube\ violation\ \xi_n^{\land} and\ lower\ tube\ violations\ \xi_n^{\lor})</script>

SVR <script type="math/tex" id="MathJax-Element-539">SVR</script>的 Primal <script type="math/tex" id="MathJax-Element-540">Primal</script>问题如下：

minb,w,ξ∨n,ξ∧ns.t.12wTw+C∑n=1N(ξ∧n+ξ∨n)−ϵ−ξ∨n≤yn−wTzn−b≤ϵ+ξ∧nξ∨n≥0,ξ∨n≥0
<script type="math/tex; mode=display" id="MathJax-Element-541">\begin{align} \mathop{min}\limits_{b,w,\xi_n^{\lor},\xi_n^{\land}} \quad &\frac12w^Tw + C\sum_{n=1}^{N}(\xi_n^{\land}+\xi_n^{\lor}) \\ s.t. \quad &-\epsilon - \xi_n^{\lor} \le y_n-w^Tz_n - b \le \epsilon + \xi_n^{\land} \\ & \xi_n^{\lor}\ge0, \xi_n^{\lor}\ge0 \end{align}</script>


这里写图片描述

从图中可以看出，就是通过最小化所有的红线长度的和加上规则化因子来得到一条比较好的分割线。

  • 参数 C <script type="math/tex" id="MathJax-Element-542">C</script>用来衡量对误差的重视程度，越大则表明想要更小的误差，与此同时就会带来更大的模型复杂度；C<script type="math/tex" id="MathJax-Element-543">C</script>越小相对来说 12wTw <script type="math/tex" id="MathJax-Element-544">\frac12w^Tw</script>占有的比重就越大，正则化起到的作用就越大，即想要更加简单的模型复杂度。
  • 参数 ϵ <script type="math/tex" id="MathJax-Element-545">\epsilon</script>用来决定 tube <script type="math/tex" id="MathJax-Element-546">tube</script>的宽度， tube <script type="math/tex" id="MathJax-Element-547">tube</script>的宽度是2 ϵ <script type="math/tex" id="MathJax-Element-548">\epsilon</script>。所以可以用来调节容忍的程度，越大表明对预测值和真实值的差值有越大的容忍度。

所以 SVR <script type="math/tex" id="MathJax-Element-549">SVR</script>和 SVM <script type="math/tex" id="MathJax-Element-550">SVM</script>相比来说多一个可以调节的参数 ϵ <script type="math/tex" id="MathJax-Element-551">\epsilon</script>。
这个二次规划问题的变数有 2N+1+d~ <script type="math/tex" id="MathJax-Element-552">2N+1+\tilde{d}</script>，约束的个数 2N+2N <script type="math/tex" id="MathJax-Element-553">2N+2N</script>个。那么接下来我们关心的问题是怎么把 d~ <script type="math/tex" id="MathJax-Element-554">\tilde{d}</script>的影响移除掉。和 SVM <script type="math/tex" id="MathJax-Element-555">SVM</script>的做法一样，需要把这个问题转换成一个对偶问题，在转换为一个对偶问题之后，就可以使用 kernel trick <script type="math/tex" id="MathJax-Element-556">kernel\ trick</script>避免在 Z <script type="math/tex" id="MathJax-Element-557">Z</script>空间中的运算，也就是说就和Z<script type="math/tex" id="MathJax-Element-558">Z</script>空间的维度 d~ <script type="math/tex" id="MathJax-Element-559">\tilde{d}</script>没有关系了。

Support Vector Regression Dual

SVR <script type="math/tex" id="MathJax-Element-247">SVR</script>的 Primal <script type="math/tex" id="MathJax-Element-248">Primal</script>问题如下：

minb,w,ξ∨n,ξ∧ns.t.12wTw+C∑n=1N(ξ∧n+ξ∨n)−ϵ−ξ∨n≤yn−wTzn−b≤ϵ+ξ∧nξ∨n≥0,ξ∨n≥0
<script type="math/tex; mode=display" id="MathJax-Element-249">\begin{align} \mathop{min}\limits_{b,w,\xi_n^{\lor},\xi_n^{\land}} \quad &\frac12w^Tw + C\sum_{n=1}^{N}(\xi_n^{\land}+\xi_n^{\lor}) \\ s.t. \quad &-\epsilon - \xi_n^{\lor} \le y_n-w^Tz_n - b \le \epsilon + \xi_n^{\land} \\ & \xi_n^{\lor}\ge0, \xi_n^{\lor}\ge0 \end{align}</script>

现在有了 SVR <script type="math/tex" id="MathJax-Element-250">SVR</script>的 Primal <script type="math/tex" id="MathJax-Element-251">Primal</script>形式，接下来我们希望可以得到 SVR <script type="math/tex" id="MathJax-Element-252">SVR</script>的 Dual <script type="math/tex" id="MathJax-Element-253">Dual</script>形式。所以我们引入 Lagrange multiplier <script type="math/tex" id="MathJax-Element-254">Lagrange\ multiplier</script>，

  • 针对条件： yn−wTzn−b≤ϵ+ξ∧n <script type="math/tex" id="MathJax-Element-255">y_n-w^Tz_n - b \le \epsilon + \xi_n^{\land}</script>，引入乘子 α∧n <script type="math/tex" id="MathJax-Element-256">\alpha_n^{\land}</script>；
  • 针对条件： −ϵ−ξ∨n≤yn−wTzn−b <script type="math/tex" id="MathJax-Element-257">-\epsilon - \xi_n^{\lor} \le y_n-w^Tz_n - b</script>，引入乘子 α∨n <script type="math/tex" id="MathJax-Element-258">\alpha_n^{\lor}</script>。

那么接下来就是写出 Lagrange <script type="math/tex" id="MathJax-Element-259">Lagrange</script>函数，然后对里面的变量求微分，使用KKT条件对 Lagrange <script type="math/tex" id="MathJax-Element-260">Lagrange</script>函数做替换得到一个新的问题，这个新的问题就是我们想要得到的对偶问题。类似于SVM的对偶问题的推导。

这里只给出一些最后推到的结果：

  • 利用 KKT <script type="math/tex" id="MathJax-Element-261">KKT</script>条件对 wi <script type="math/tex" id="MathJax-Element-262">w_i</script>进行求导并令结果为0可以得到：
    ∂L∂wi=0⟶w=∑n=1N(α∧n−α∨n)zn
    <script type="math/tex; mode=display" id="MathJax-Element-263">\frac{\partial L}{\partial w_i} = 0 \longrightarrow w = \sum_{n=1}^{N}(\alpha_n^{\land} - \alpha_n^{\lor})z_n</script>这个和在 SVM <script type="math/tex" id="MathJax-Element-264">SVM</script>得到的结果是一样的， 即 w <script type="math/tex" id="MathJax-Element-265">w</script>会是z<script type="math/tex" id="MathJax-Element-266">z</script>的线性组合。
  • 利用 KKT <script type="math/tex" id="MathJax-Element-267">KKT</script>条件对 b <script type="math/tex" id="MathJax-Element-268">b</script>进行求偏导并令结果为0可以得到：
    ∂L∂b=0⟶∑n=1N(α∧n−α∨n)=0
    <script type="math/tex; mode=display" id="MathJax-Element-269">\frac{\partial L}{\partial b} = 0 \longrightarrow \sum_{n=1}^{N}(\alpha_n^{\land} - \alpha_n^{\lor}) = 0</script>
  • 利用 KKT <script type="math/tex" id="MathJax-Element-270">KKT</script>条件得最佳解满足：
    α∧n(ϵ+ξ∨n−yn+wTzn+b)=0,α∧n(ϵ+ξ∨n−yn+wTzn+b)=0
    <script type="math/tex; mode=display" id="MathJax-Element-271">\alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0, \quad \alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0</script>

经过推导之后，SVR的对偶形式如下：

mins.t.12∑n=1N∑m=1N(α∧n−α∨n)(α∧m−α∨m)K(xn,xm)+∑n=1N((ϵ−yn)⋅α∧n+(ϵ+yn)⋅α∨n)∑n=1N1⋅(α∧n−α∨n)=0C≥α∧n≥0,C≥α∨n≥0
<script type="math/tex; mode=display" id="MathJax-Element-272">\begin{align} min & \frac12\sum_{n=1}^{N}\sum_{m=1}^{N}(\alpha_{n}^{\land} - \alpha_n^{\lor})(\alpha_{m}^{\land} - \alpha_m^{\lor})K(x_n, x_m) + \sum_{n=1}^{N}((\epsilon - y_n)\centerdot \alpha_{n}^{\land}+(\epsilon + y_n)\centerdot \alpha_{n}^{\lor})\\ s.t. & \sum_{n=1}^{N} 1 \centerdot (\alpha_{n}^{\land} - \alpha_{n}^{\lor}) = 0 \\ & C\ge\alpha_{n}^{\land}\ge0, C\ge\alpha_{n}^{\lor}\ge0 \end{align}</script>

我们推导 SVR <script type="math/tex" id="MathJax-Element-273">SVR</script>的最初的目的是为了得到稀疏的解。现在我们就来看看我们有没有达到目的。现在我们已经知道了最佳的解 w <script type="math/tex" id="MathJax-Element-274">w</script>可以表示为 z<script type="math/tex" id="MathJax-Element-275">z</script> 的线性组合，那么在什么情况下 βn <script type="math/tex" id="MathJax-Element-276">\beta_n</script>是 0 <script type="math/tex" id="MathJax-Element-277">0</script> 呢？

w=∑n=1N(α∧n−α∨n)βnzn
<script type="math/tex; mode=display" id="MathJax-Element-278"> w = \sum_{n=1}^{N}\underbrace{(\alpha_n^{\land} - \alpha_n^{\lor})}_{\beta_n}z_n</script>

从 KKT <script type="math/tex" id="MathJax-Element-279">KKT</script>条件告诉我们的如下的两个 complementary slackness <script type="math/tex" id="MathJax-Element-280">complementary\ slackness</script>出发，

α∧n(ϵ+ξ∨n−yn+wTzn+b)=0,α∧n(ϵ+ξ∨n−yn+wTzn+b)=0
<script type="math/tex; mode=display" id="MathJax-Element-281">\alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0, \quad \alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0</script>

我们考虑严格位于 tube <script type="math/tex" id="MathJax-Element-282">tube</script>中的数据点： |wTzn+b−yn|<ϵ <script type="math/tex" id="MathJax-Element-283">|w^Tz_n + b - y_n| < \epsilon</script>

when|wTzn+b−yn|<ϵ⟶ξ∨n=ξ∧n=0⟶ϵ+yn+wTzn+b≠0,ϵ−yn+wTzn+b≠0⟶α∨n=α∧n=0⟶βn=0
<script type="math/tex; mode=display" id="MathJax-Element-284">\begin{align} when\quad & |w^Tz_n + b - y_n| < \epsilon \\ & \longrightarrow \xi_n^{\lor} = \xi_n^{\land} = 0 \\ & \longrightarrow \epsilon+y_n+w^Tz_n+b \ne 0, \epsilon-y_n+w^Tz_n+b\ne 0 \\ &\longrightarrow \alpha_n^{\lor} = \alpha_n^{\land} = 0 \\ & \longrightarrow \beta_n = 0 \end{align}</script>
所以当预测值和真实值的差值的绝对值小于 ϵ <script type="math/tex" id="MathJax-Element-285">\epsilon</script>，即位于 tube <script type="math/tex" id="MathJax-Element-286">tube</script>之间的时候，这些数据点对于最佳解 w <script type="math/tex" id="MathJax-Element-287">w</script>没有贡献。所以只有在tube<script type="math/tex" id="MathJax-Element-288">tube</script>外面或者是边界上的点才对 w <script type="math/tex" id="MathJax-Element-289">w</script>有影响的点，也就是support vectors<script type="math/tex" id="MathJax-Element-290">support\ vectors</script>。到这里我们就证明了可以用 SVR <script type="math/tex" id="MathJax-Element-291">SVR</script>这样的模型得到 sparse <script type="math/tex" id="MathJax-Element-292">sparse</script>的解。

Summary of Kernel Models

线性模型

本系列中涉及的线性模型主要有三个

  • PLA/pocket <script type="math/tex" id="MathJax-Element-603">PLA/pocket</script>用于分类，直接优化 err0/1 <script type="math/tex" id="MathJax-Element-604">err_{0/1}</script>；
  • Logistic Regression <script type="math/tex" id="MathJax-Element-605">Logistic\ Regression</script>用于 soft <script type="math/tex" id="MathJax-Element-606">soft</script>分类，其方法是最小化 cross entropy error <script type="math/tex" id="MathJax-Element-607">cross\ entropy\ error</script>或者说是 logistic error <script type="math/tex" id="MathJax-Element-608">logistic\ error</script>- errCE <script type="math/tex" id="MathJax-Element-609">err_{CE}</script>，通常使用 SGD <script type="math/tex" id="MathJax-Element-610">SGD</script>或者 GD <script type="math/tex" id="MathJax-Element-611">GD</script>。如果加上正则化项就是 regularized logistic regression <script type="math/tex" id="MathJax-Element-612">regularized\ logistic\ regression</script>。
  • Linear Regression <script type="math/tex" id="MathJax-Element-613">Linear\ Regression</script>用于对实数的回归分析，通过最小化 errsquare <script type="math/tex" id="MathJax-Element-614">err_{square}</script>可以得到解析解。如果加上正则化项就是 linear ridge regression <script type="math/tex" id="MathJax-Element-615">linear\ ridge\ regression</script>。
  • 之后介绍了另外一种线性模型 linear soft margin SVM <script type="math/tex" id="MathJax-Element-616">linear\ soft\ margin\ SVM</script>，也是用于解决线性的分类问题，使用的 error function <script type="math/tex" id="MathJax-Element-617">error\ function</script>被称为是 hinge error <script type="math/tex" id="MathJax-Element-618">hinge\ error</script>，通过求解一个 QP <script type="math/tex" id="MathJax-Element-619">QP</script>问题得到最优解。
  • Regression <script type="math/tex" id="MathJax-Element-620">Regression</script>的另一种做法是 linear SVR <script type="math/tex" id="MathJax-Element-621">linear\ SVR</script>，同样是使用二次规划最小化 errtube <script type="math/tex" id="MathJax-Element-622">err_{tube}</script>。


这里写图片描述

LIBLINEAR <script type="math/tex" id="MathJax-Element-623">LIBLINEAR</script>中实现了第二行的三种模型。

以上线性的模型只要加上 regularizer <script type="math/tex" id="MathJax-Element-624">regularizer</script>都可以延伸成 kernel <script type="math/tex" id="MathJax-Element-625">kernel</script>的模型。


这里写图片描述

linear soft margin SVM <script type="math/tex" id="MathJax-Element-626">linear\ soft\ margin\ SVM</script>延伸成 SVM <script type="math/tex" id="MathJax-Element-627">SVM</script>， SVM <script type="math/tex" id="MathJax-Element-628">SVM</script>解决的不再是 primal <script type="math/tex" id="MathJax-Element-629">primal</script>问题，而是对偶问题；
linear SVR <script type="math/tex" id="MathJax-Element-630">linear\ SVR</script>的 kernel <script type="math/tex" id="MathJax-Element-631">kernel</script>延伸是 SVR <script type="math/tex" id="MathJax-Element-632">SVR</script>，同样也是解决对偶问题；
通过 representer theorem <script type="math/tex" id="MathJax-Element-633">representer\ theorem</script>可以将 linear ridge regression <script type="math/tex" id="MathJax-Element-634">linear\ ridge\ regression</script>变为 kernel ridge regression <script type="math/tex" id="MathJax-Element-635">kernel\ ridge\ regression</script>；
可以将 regularized logistic regression <script type="math/tex" id="MathJax-Element-636">regularized\ logistic\ regression</script>变为 kernel logistic regression <script type="math/tex" id="MathJax-Element-637">kernel\ logistic\ regression</script>；
kernel logistic regression <script type="math/tex" id="MathJax-Element-638">kernel\ logistic\ regression</script>通常会被 Probabilistic SVM <script type="math/tex" id="MathJax-Element-639">Probabilistic\ SVM</script>，也就是 two level learning <script type="math/tex" id="MathJax-Element-640">two\ level\ learning</script>取代；

LIBSVM <script type="math/tex" id="MathJax-Element-641">LIBSVM</script>实现了最后一行的所有的三种模型。

针对上图中模型的实用度做简单的记录：第一行 PLA/pocket <script type="math/tex" id="MathJax-Element-642">PLA/pocket</script>和 linear SVR <script type="math/tex" id="MathJax-Element-643">linear\ SVR</script>很少被使用，通常会被它们下面的两个模型分别取代；第三行的 kernel ridge regression <script type="math/tex" id="MathJax-Element-644">kernel\ ridge\ regression</script>和 kernel logistic regression <script type="math/tex" id="MathJax-Element-645">kernel\ logistic\ regression</script>也比较少用，因为这两个模型的解不是稀疏的，通常会被它们下面的两个模型分别取代。

总结

本篇主要讲解了 Support Vector Regression <script type="math/tex" id="MathJax-Element-336">Support\ Vector\ Regression</script>，我们一开始的出发点是如何将 Ridge Regression <script type="math/tex" id="MathJax-Element-337">Ridge\ Regression</script>变为 kernel <script type="math/tex" id="MathJax-Element-338">kernel</script>的形式， representer theorem <script type="math/tex" id="MathJax-Element-339">representer\ theorem</script>理论帮助我们完成了这个工作，但是通过这样的方法得到的解不是稀疏的，我们想要的 sparse <script type="math/tex" id="MathJax-Element-340">sparse</script>的解，所以我们通过推导带有 regularizer <script type="math/tex" id="MathJax-Element-341">regularizer</script>的 tube error <script type="math/tex" id="MathJax-Element-342">tube\ error</script>得出了 SVR <script type="math/tex" id="MathJax-Element-343">SVR</script>的原始问题，进一步推导了 SVR <script type="math/tex" id="MathJax-Element-344">SVR</script>的对偶问题。最后根据 KTT <script type="math/tex" id="MathJax-Element-345">KTT</script>条件得到了稀疏的解。

回顾

# 机器学习
Logo
CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

更多推荐

cover

Kaldi之父，IEEE Fellow，小米首席语音科学家Daniel Povey将出席2024全球机器学习技术大会并发表演讲！

avatar CSDN学习社区
cover

探索神经网络在商品销售和图像识别中的应用

avatar CSDN学习社区
cover

基于stm32F103的座面声控台灯

avatar CSDN学习社区