支持向量机（6）：支持向量回归

脊回归

有正则化项的回归称为脊回归（ridge regression）。脊回归的核模型有解析解么？

脊回归的最优化模型为 \[ \min_{\mathbf w}\left({\lambda\over N}\mathbf w^T\mathbf w+{1\over N}\sum_{n=1}^N\left(y_n-\mathbf w^T\mathbf z_n\right)^2\right)， \] 根据表示定理可知，存在形如$\mathbf w_*=\sum_{n=1}^N\beta_n\mathbf z_n$的最优解，将其带入并表示为核形式 \begin{equation} \min_\beta\left({\lambda\over N}\sum_{n=1}^N\sum_{m=1}^N\beta_n\beta_mK(\mathbf x_n,\mathbf x_m)+{1\over N}\sum_{n=1}^N\left(y_n-\sum_{n=1}^N\beta_mK(\mathbf x_n,\mathbf x_m)\right)\right)。 \end{equation} 脊回归的核模型就是利用表示定理将脊回归核化。目标函数写为矩阵的形式 \begin{equation} E_{aug}(\boldsymbol\beta)={\lambda\over N}\boldsymbol\beta^T\mathbf K\boldsymbol\beta + {1\over N}\left(\boldsymbol\beta^T\mathbf K^T\mathbf K\boldsymbol\beta-2\boldsymbol\beta^T\mathbf K^T\mathbf y + \mathbf y^T\mathbf y\right)， \end{equation} 无约束最优化问题可以通过 \[ \nabla E_{aug}(\boldsymbol\beta)={2\over N}\left(\lambda\mathbf K^T\mathbf I\boldsymbol\beta+\mathbf K^T\mathbf K\boldsymbol\beta-\mathbf K^T\right)={2\over N}\mathbf K^T\left((\lambda\mathbf I+\mathbf K)\boldsymbol\beta-\mathbf y\right) \] 令$\nabla E_{aug}(\boldsymbol\beta)=0$求解， \begin{equation} \boldsymbol\beta=(\mathbf K+\lambda\mathbf I)^{-1}\mathbf y。 \label{eq:analytic-solution-ridge-regression} \end{equation} 根据Mercer条件可知$\mathbf K$半正定，并且$\lambda>0$，因此矩阵总可逆。稠密矩阵求逆的时间复杂度为$O\left(N^3\right)$。

图 1: ［左］：脊回归的线性模型；［右］：脊回归的核模型 [PNG]

上图中的蓝线是脊回归的效果。线性模型与核模型的选择是速度与效率的折中权衡，它们之间的对比如下表：

当参数获得后，回归函数就可以用核表示为 \begin{equation} g(\mathbf x)=\sum_{n=1}^N\beta_nK\left(\mathbf x_n, \mathbf x\right)。 \end{equation}

将脊回归的核模型用于分类就是最小二乘支持向量机（LSSVM，least-squares SVM），也就是用回归解决分类问题，虽然分类性能可能不佳，但用解析方法\eqref{eq:analytic-solution-ridge-regression}可“容易”求解系数。

图 2: 最小二乘与soft-margin支持向量机的对比 [PNG]

上图可以看出，最小二乘与soft-margin支持向量机的分类面很相似，但是LSSVM的支持向量要多得多，预测速度会很慢。

LSSVM和logistic回归的核模型得到的参数$\boldsymbol\beta$是稠密的，标准支持向量机的参数$\boldsymbol\alpha$是稀疏的。能否得到像标准支持向量机一样稀疏的$\boldsymbol\beta$呢？

支持向量回归

定义tube回归的误差为 \begin{equation} err(y, s) = \max(0, \lvert s-y\rvert-\epsilon)， \end{equation} 在tube区域内不计误差，在该区域外到tube的距离记为误差。

图 3: tube与平方误差对比 [PNG]

如上图所示，tube与平方误差很相似，尤其是在$\lvert s-y\rvert$很小的区域内，当$\lvert s-y\rvert$很大时，tube误差不如平方误差变化陡峭，因此受噪声影响更小。

基于tube误差的模型能否得到稀疏的系数呢？

基于$L_2$正则化的tube回归模型为 \begin{equation*} \min\limits_{\mathbf w}\left({\lambda\over N}\mathbf w^T\mathbf w+{1\over N}\sum_{n=1}^N\max\left(0, \left\lvert \mathbf w^T\mathbf z_n-y_n\right\rvert-\epsilon\right)\right)， \end{equation*} 虽无约束，但$\max$导致不可微；利用表示定理可核化，但无法明确得到稀疏的系数。仿照无约束形式的soft-margin支持向量机，分离出$b$后改写为 \begin{equation*} \min\limits_{b,\mathbf w}\left({1\over 2}\mathbf w^T\mathbf w+C\sum_{n=1}^N\max\left(0, \left\lvert \mathbf w^T\mathbf z_n+b-y_n\right\rvert-\epsilon\right)\right)， \end{equation*} 虽然不可微，但是QP问题；对偶问题可核化，KKT条件能得到系数稀疏。再对比约束形式的soft-margin支持向量机，改写为带约束的优化问题 \begin{equation*} \begin{aligned} \min\limits_{b,\mathbf w,\boldsymbol\xi}&\quad\frac{1}{2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\xi_n\\ \mbox{s.t.}&\quad \left\lvert\mathbf w^T\mathbf z_n+b-y_n\right\rvert\leq \epsilon+\xi_n\\ &\quad\xi_n\geq 0 \mbox{ for all }n， \end{aligned} \end{equation*} 约束条件线性化 \begin{equation} \begin{aligned} \min\limits_{b,\mathbf w,\boldsymbol\xi^\vee,\boldsymbol\xi^\wedge}&\quad\frac{1}{2}\mathbf w^T\mathbf w + C\sum_{n=1}^N\left(\xi_n^\vee+\xi_n^\wedge\right)\\ \mbox{s.t.}&\quad -\epsilon-\xi_n^\vee\leq y_n - \mathbf w^T\mathbf z_n-b\leq \epsilon+\xi_n^\wedge\\ &\quad\xi_n^\vee\geq 0,\xi_n^\wedge\geq 0\mbox{ for all }n， \end{aligned} \end{equation} 这就是标准的支持向量回归（SVR，support vector regression）原问题，$\xi_n^\vee$和$\xi_n^\wedge$分别记录tube下届和上界违规，如上图左所示的分界线下边和上边标红的线段。通过$C$对正则化和tube违规进行折中，调节参数$\epsilon$可控制tube的高度。该QP模型有$\tilde d+1+2N$个变量，$2N+2N$个约束条件。

将支持向量回归的原问题转成对偶问题，可移除对$\tilde d$的依赖。

支持向量回归的对偶模型

通过拉格朗日乘子法的KKT条件${\partial\mathcal L\over\partial\mathbf w}=0$可得 \begin{equation} \mathbf w = \sum_{n=1}^N\left(\alpha_n^\wedge-\alpha_n^\vee\right)\mathbf z_n = \sum_{n=1}^N\beta_n\mathbf z_n， \end{equation} 通过${\partial\mathcal L\over\partial b}=0$可得 \[ \sum_{n=1}^N\left(\alpha_n^\wedge-\alpha_n^\vee\right)＝0， \] 互补松弛条件（complementary slackness）为 \begin{equation} \left\{ \begin{aligned} \alpha_n^\wedge\left(\epsilon+\xi_n^\wedge-y_n+\mathbf w^T\mathbf z_n+b\right)=&0\\ \alpha_n^\vee\left(\epsilon+\xi_n^\vee+y_n-\mathbf w^T\mathbf z_n-b\right)=&0。 \end{aligned} \right. \label{eq:complementary-slackness-svm-regession} \end{equation}

图 4: QP原问题与对偶问题的对比 [PNG]

上图左上和左下分别表示soft-margin支持向量机的原问题和对偶问题的QP模型；上图右上和右下分别表示支持向量回归的原问题和对偶问题的QP模型。上图中，相同颜色的符号展示了如何从原问题变化到对偶问题。

当数据点位于tube中有$\left\lvert\mathbf w^T\mathbf z_n+b-y_n\right\rvert<\epsilon$，不计误差，$\xi_n^\wedge=\xi_n^\vee=0$，根据互补松弛条件\eqref{eq:complementary-slackness-svm-regession}可知 \[ \left\{ \begin{aligned} \epsilon+\xi_n^\wedge-y_n+\mathbf w^T\mathbf z_n+b\neq &0\\ \epsilon+\xi_n^\vee+y_n-\mathbf w^T\mathbf z_n-b\neq &0， \end{aligned} \right. \] 以及$\alpha_n^\wedge=\alpha_n^\vee＝0$，因此可得$\beta_n=0$。由此可知，支持向量回归问题中$\beta_n\neq 0$的支持向量刚好位于tube的边界上或在tube之外。

参考soft-margin支持向量机可得 \begin{equation} b= \left\{ \begin{aligned} y_n-\mathbf w^T\mathbf z_n-\epsilon&\quad(0<\alpha_n^\wedge<C)\\ y_n-\mathbf w^T\mathbf z_n+\epsilon&\quad(0<\alpha_n^\vee<C)。 \end{aligned} \right. \end{equation}