GZ Cloudhome Logo

流形约束框架下的 LapSVR 和 LapESVR

发布于：2023 年 6 月 30 日 at 16:18

RKHS（再生核希尔伯特空间）中的流形约束函数估计

我们在 再生核希尔伯特空间 中已经较详细地讲过了 RKHS 中的函数估计，基于 RKHS 的流形约束函数估计是在其上的一个扩展。

基于 RKHS 的流形约束函数估计框架为

min⁡f∈HK1N∑i=1Nl(yi,f(xi))+γA∥f∥HK2+γIN2fTLf,\min_{f \in \mathcal{H}_K} \frac{1}{N} \sum_{i=1}^N l(y_i, f(x_i)) + \gamma_A \| f \|_{\mathcal{H}_K}^2 + \frac{\gamma_I}{N^2} \boldsymbol{f}^T \mathbf{L} \boldsymbol{f},

或者采用另一组常见的超参数 CC 和 μ\mu，表示为

min⁡f∈HKC∑i=1Nl(yi,f(xi))+12∥f∥HK2+12μfTLf,\min_{f \in \mathcal{H}_K} C \sum_{i=1}^N l(y_i, f(x_i)) + \frac{1}{2} \| f \|_{\mathcal{H}_K}^2 + \frac{1}{2} \mu \boldsymbol{f}^T \mathbf{L} \boldsymbol{f},

其中 HK\mathcal{H}_K 是由一个 Mercer 核函数 KK 诱导的 RKHS。

这两组超参数有互相对应关系，可以互相转换：

γA=12NCγI=Nμ2C.\begin{align*} \gamma_A &= \frac{1}{2 N C} \\ \gamma_I &= \frac{N \mu}{2 C}. \end{align*}

可以证明（通过投影理论和核再生特性或 Riesz 表示定理来证明）上述的最优化问题的最优解 ff 可以表示为

f(x)=∑i=1NαiK(xi,x),f(x) = \sum_{i=1}^N \alpha_i K(x_i, x),

这意味着 ff 是中心点在所有训练样本点的核片段的线性组合。在后文中，我将用“新表示定理”表示这个结论。

通常我们还希望有一个偏置项 bb。加入了偏置项 bb 之后，最优的函数可以表示为

f∗(x)=∑i=1NαiK(xi,x)+b.f^*(x) = \sum_{i=1}^N \alpha_i K(x_i, x) + b.

基于不同的损失函数 ll，我们可以得到不同形式的函数。

ϵ\epsilon-insensitive 损失

拉普拉斯支持向量回归 (LapSVR)

ϵ\epsilon-insensitive 损失定义为

lϵ(e)={0,∣e∣≤ϵ∣e∣−ϵ,∣e∣>ϵ.l_\epsilon(e) = \left\{ \begin{align*} & 0, && |e| \le \epsilon \\ & |e| - \epsilon, && |e| > \epsilon. \end{align*} \right.

基于这个损失应用流形约束函数估计框架，我们可以得到优化问题

min⁡f∈HKC∑i=1N(ξi+ξi∗)+12∥f∥HK2+μ2fTLfsubject tof(xi)+b−yi≤ϵ+ξiyi−f(xi)−b≤ϵ+ξi∗ξi≥0ξi∗≥0,    i=1,2,…,N.\begin{align*} \min_{f \in \mathcal{H}_K} && & C \sum_{i=1}^N (\xi_i + \xi^*_i) + \frac{1}{2} \| f \|_{\mathcal{H}_K}^2 + \frac{\mu}{2} \boldsymbol{f}^T \mathbf{L} \boldsymbol{f} \\ \mathrm{subject~to} && & f(x_i) + b - y_i \le \epsilon + \xi_i \\ && & y_i - f(x_i) - b \le \epsilon + \xi^*_i \\ && & \xi_i \ge 0 \\ && & \xi_i^* \ge 0, ~~~~ i = 1, 2, \dots, N. \end{align*}

根据新表示定理，我们可以推得对偶问题

max⁡β,β∗∈Rn−12(β∗−β)TQ(β∗−β)+(β∗−β)Ty−ϵ(β∗+β)T1subject to0≤β≤C10≤β∗≤C11T(β−β∗)=0,\begin{align*} \max_{\boldsymbol{\beta}, \boldsymbol{\beta}^* \in \mathbb{R}^n} && & -\frac{1}{2} (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \mathbf{Q} (\boldsymbol{\beta}^* - \boldsymbol{\beta}) + (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T y - \epsilon (\boldsymbol{\beta}^* + \boldsymbol{\beta})^T \boldsymbol{1} \\ \mathrm{subject~to} && & \boldsymbol{0} \le \boldsymbol{\beta} \le C \boldsymbol{1} \\ && & \boldsymbol{0} \le \boldsymbol{\beta}^* \le C \boldsymbol{1} \\ && & \boldsymbol{1}^T (\boldsymbol{\beta} - \boldsymbol{\beta}^*) = 0, \end{align*}

其中

Q=K(I+μLK)−1\mathbf{Q} = \mathbf{K} \big( \mathbf{I} + \mu \mathbf{LK} \big)^{-1}

是新的核矩阵，同时我们可以基于 β\boldsymbol{\beta} 计算 α\boldsymbol{\alpha}：

α=(I+μLK)−1(β∗−β).\boldsymbol{\alpha} = \big( \mathbf{I} + \mu \mathbf{LK} \big)^{-1} (\boldsymbol{\beta}^* - \boldsymbol{\beta}).

我们可以基于 KKT 最优性条件（KKT optimality conditions）来计算偏置项 bb。下面的等式基于 KKT 条件中的互补松弛（complementary slackness）条件：

(f(xi)+b−yi−(ϵ+ξi))βi=0(yi−f(xi)−b−(ϵ+ξi∗))βi∗=0(C−βi)ξi=0(C−βi∗)ξi∗=0.\begin{align*} \big( f(x_i) + b - y_i - (\epsilon + \xi_i) \big) \beta_i &= 0 \\ \big( y_i - f(x_i) - b - (\epsilon + \xi^*_i) \big) \beta_i^* &= 0 \\ \big( C - \beta_i \big) \xi_i &= 0 \\ \big( C - \beta_i^* \big) \xi_i^* &= 0. \end{align*}

因此， bb 可以基于满足

0<βi<C.0 < \beta_i < C.

的 βi\beta_i（或 βi∗\beta_i^*）求出。

在极端情形下，这样的 βi\beta_i 或 βi∗\beta_i^* 不存在。不过这个时候我们仍然可以基于 KKT 条件得到 bb 需要满足的几个不等式条件：

βi=0⇒ξi=0⇒b≤ϵ+yi−f(xi)βi∗=0⇒ξi∗=0⇒b≥yi−f(xi)−ϵβi=C⇒ξi≥0⇒b≥ϵ+yi−f(xi)βi∗=C⇒ξi∗≥0⇒b≤yi−f(xi)−ϵ.\begin{align*} \beta_i = 0 &\Rightarrow \xi_i = 0 \\ &\Rightarrow b \le \epsilon + y_i - f(x_i) \\ \beta_i^* = 0 &\Rightarrow \xi_i^* = 0 \\ &\Rightarrow b \ge y_i - f(x_i) - \epsilon \\ \beta_i = C &\Rightarrow \xi_i \ge 0 \\ &\Rightarrow b \ge \epsilon + y_i - f(x_i) \\ \beta_i^* = C &\Rightarrow \xi_i^* \ge 0 \\ &\Rightarrow b \le y_i - f(x_i) - \epsilon. \end{align*}

这种情况下，bb 会有很多的可行解，都对应多个最优的 f∗f^*，它们有相同的最优化问题取值。仔细想一下，这是可以预见的，因为 ϵ\epsilon-insensitive 损失在 0 附近是平的（取值全为 0）。

当 μ=0\mu = 0（或 γI=0\gamma_I = 0），这个模型将会退化成支持向量回归（SVR）。

在文献中一般把 ϵ\epsilon-不敏感损失得到的模型称作 LapSVR。

解的稀疏性

在 SVR 中，得到的 α\boldsymbol{\alpha} 是稀疏的。然而，对于 LapSVR α\boldsymbol{\alpha} 却不再稀疏。不过，基于 KKT 最优化条件，β∗−β\boldsymbol{\beta}^* - \boldsymbol{\beta} 仍然是稀疏的。

不稀疏的 α\boldsymbol{\alpha} 会降低模型的可解释性。后文中将的 LapESVR 将会解决这个问题。

使用 sklearn 的 SVR API 来求解上面的优化问题

虽然上述的对偶问题可以使用二次规划（QP）求解器来求解，在求解的时候我们很容易会陷入数值问题，同时启动一个 QP 求解器的求解流程是非常耗时的。另外一方面来说，SMO（Sequential Minimal Optimization）是一个可以高效解决 SVR 的对偶问题的优化算法，在 SMO 的每一个最优迭代步骤中，都通过闭式解来解决自问题，因此 SMO 不容易陷入数值问题；此外，SMO 的速度也非常快。我们能否将 SMO 算法应用到前面最优化问题的求解中呢？

我们可以观察到，前面得到的对偶问题和 SVR 的对偶问题有着相同的形式以及相同的 KKT 条件。它们只有一点不同，即核矩阵的不同，

K~=K(I+μLK)−1.\tilde{\mathbf{K}} = \mathbf{K} \big( \mathbf{I} + \mu \mathbf{LK} \big)^{-1}.

同时，我们也可以检验互补松弛条件是仍然满足的：

f=K(I+μLK)−1(β∗−β)=K~(β∗−β).\begin{align*} \boldsymbol{f} &= \mathbf{K} \big( \mathbf{I} + \mu \mathbf{LK} \big)^{-1} (\boldsymbol{\beta}^* - \boldsymbol{\beta}) \\ &= \tilde{\mathbf{K}} (\boldsymbol{\beta}^* - \boldsymbol{\beta}). \end{align*}

因此，这个对偶问题是可以通过 SMO 算法来求解的。SMO 算法在 LIBSVM 库中实现，而 sklearn 对 SVR 的实现也是用了这个库。我们可以调用 sklearn 的 SVR 接口来实现 SMO 算法的调用。具体地，在生成 SVR 类的实例时，我们传入 kernel='precomputed' 参数，然后把新的核矩阵 K~\tilde{\mathbf{K}} 喂给这个实例的 fit 方法，然后我们就可以使用 SMO 算法来求解这个问题了。

LIBSVM 和 sklearn 的 SVR 在训练完毕后都会给出 β∗−β\boldsymbol{\beta}^* - \boldsymbol{\beta} 和 bb。对于 SVR，这两个变量保存在 dual_coef_ and intercept_ 属性里。可以证明，SMO 得到的 bb 恰恰是我们 LapSVR 的主问题中的 bb。得到 β∗−β\boldsymbol{\beta}^* - \boldsymbol{\beta} 和 bb 之后，我们可以基于同样的方式来计算 α\boldsymbol{\alpha}，然后得到训练好的模型。

嵌入图拉普拉斯矩阵的支持向量回归（LapESVR）

和 LapSVR 不同，LapESVR（Laplacian Embedded Support Vector Regression）得到的 α\boldsymbol{\alpha} 是稀疏的。这要归功于 LapESVR 在流形约束函数估计的最优化问题中引入了新的项。新的最优化问题为

min⁡b∈R,α,ξ,ξ∗,g∈Rl+uC1T(ξ+ξ∗)+12(g−y)TΛ(g−y)+12αTKα+μ2gTLgsubject toKα+b1−g≤ϵ1+ξg−Kα−b1≤ϵ1+ξ∗ξ,ξ∗≥0.\begin{align*} \min_{b \in \mathbb{R}, \boldsymbol{\alpha},\boldsymbol{\xi}, \boldsymbol{\xi}^*, \boldsymbol{g} \in \mathbb{R}^{l+u}} && & C \boldsymbol{1}^T (\boldsymbol{\xi} + \boldsymbol{\xi}^*) + \frac{1}{2} (\boldsymbol{g} - \boldsymbol{y})^T \mathbf{\Lambda}(\boldsymbol{g} - \boldsymbol{y}) + \frac{1}{2} \boldsymbol{\alpha}^T \mathbf{K} \boldsymbol{\alpha} + \frac{\mu}{2} \boldsymbol{g}^T \mathbf{L} \boldsymbol{g} \\ \mathrm{subject~to} && & \mathbf{K}\boldsymbol{\alpha} + b \boldsymbol{1} - \boldsymbol{g} \le \epsilon \boldsymbol{1} + \boldsymbol{\xi} \\ && & \boldsymbol{g} - \mathbf{K}\boldsymbol{\alpha} - b \boldsymbol{1} \le \epsilon \boldsymbol{1} + \boldsymbol{\xi}^* \\ && & \boldsymbol{\xi}, \boldsymbol{\xi}^* \ge 0. \end{align*}

基于新表示定理，这样的主问题可以转化为对偶形式，

max⁡β,β∗∈Rl+u−12(β∗−β)TQ(β∗−β)+(β∗−β)Ty~−ϵ(β∗−β)T1subject to0≤β,β∗≤C1T(β−β∗)=0,\begin{align*} \max_{\boldsymbol{\beta}, \boldsymbol{\beta}^* \in \mathbb{R}^{l+u}} && & - \frac{1}{2} (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \mathbf{Q} (\boldsymbol{\beta}^* - \boldsymbol{\beta}) + (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \tilde{\boldsymbol{y}} - \epsilon (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \boldsymbol{1} \\ \mathrm{subject~to} && & 0 \le \boldsymbol{\beta}, \boldsymbol{\beta}^* \le C \\ && & \boldsymbol{1}^T(\boldsymbol{\beta} - \boldsymbol{\beta}^*) = 0, \end{align*}

附带一些等式：

α=β∗−βg=(Λ+μL)−1(Λy−(β∗−β)),\begin{align*} \boldsymbol{\alpha} &= \boldsymbol{\beta}^* - \boldsymbol{\beta} \\ \boldsymbol{g} &= \big( \mathbf{\Lambda} + \mu \mathbf{L} \big)^{-1} \big( \mathbf{\Lambda} \boldsymbol{y} - (\boldsymbol{\beta}^* - \boldsymbol{\beta}) \big) , \end{align*}

其中

Q=K+(Λ+μL)−1y~=(Λ+μL)−1Λy.\begin{align*} \mathbf{Q} &= \mathbf{K} + \big( \mathbf{\Lambda} + \mu \mathbf{L} \big)^{-1} \\ \tilde{\boldsymbol{y}} &= \big( \mathbf{\Lambda} + \mu \mathbf{L} \big)^{-1} \mathbf{\Lambda} \boldsymbol{y}. \end{align*}

此时，α=β∗−β\boldsymbol{\alpha} = \boldsymbol{\beta}^* - \boldsymbol{\beta}，因此 α\boldsymbol{\alpha} 将会继承 β∗−β\boldsymbol{\beta}^* - \boldsymbol{\beta} 的稀疏性。

为了高效地计算新的核矩阵 Q\mathbf{Q}，我们可以把流形嵌入的思想应用到这个模型上面来。我们知道，在 拉普拉斯特征映射（LE） 中，我们对 L\mathbf{L} 做了一个特征值分解，然后就可以得到最能保持图（流形）结构的低维嵌入。 假设 Φ∈R(u+l)×nev\mathbf{\Phi} \in \mathbb{R}^{(u+l) \times n_{ev}} 的各列分别对应最小的 nevn_{ev} 个特征值，我们可以约束 g=Φζ\boldsymbol{g} = \mathbf{\Phi} \boldsymbol{\zeta}，即 g\boldsymbol{g} 在由拉普拉斯特征映射的嵌入向量所张成的一个空间内。那么，原问题就可以表示成

min⁡b∈R,α,ξ,ξ∗∈Rl+u,ζ∈RnevC1T(ξ+ξ∗)+12(Φζ−y)TΛ(Φζ−y)+12αTKα+μ2ζTΦTLΦζsubject toKα+b1−Φζ≤ϵ1+ξΦζ−Kα−b1≤ϵ1+ξ∗ξ,ξ∗≥0.\begin{align*} \min_{b \in \mathbb{R}, \boldsymbol{\alpha},\boldsymbol{\xi}, \boldsymbol{\xi}^* \in \mathbb{R}^{l+u}, \boldsymbol{\zeta} \in \mathbb{R}^{n_{ev}}} && & C \boldsymbol{1}^T (\boldsymbol{\xi} + \boldsymbol{\xi}^*) + \frac{1}{2} (\mathbf{\Phi} \boldsymbol{\zeta} - \boldsymbol{y})^T \mathbf{\Lambda}(\mathbf{\Phi} \boldsymbol{\zeta} - \boldsymbol{y}) + \frac{1}{2} \boldsymbol{\alpha}^T \mathbf{K} \boldsymbol{\alpha} + \frac{\mu}{2} \boldsymbol{\zeta}^T \mathbf{\Phi}^T \mathbf{L} \mathbf{\Phi} \boldsymbol{\zeta} \\ \mathrm{subject~to} && & \mathbf{K}\boldsymbol{\alpha} + b \boldsymbol{1} - \mathbf{\Phi} \boldsymbol{\zeta} \le \epsilon \boldsymbol{1} + \boldsymbol{\xi} \\ && & \mathbf{\Phi} \boldsymbol{\zeta} - \mathbf{K}\boldsymbol{\alpha} - b \boldsymbol{1} \le \epsilon \boldsymbol{1} + \boldsymbol{\xi}^* \\ && & \boldsymbol{\xi}, \boldsymbol{\xi}^* \ge 0. \end{align*}

以及它的对偶问题

max⁡β,β∗∈Rl+u−12(β∗−β)TQ(β∗−β)+(β∗−β)Ty~−ϵ(β∗−β)T1subject to0≤β,β∗≤C1T(β−β∗)=0,\begin{align*} \max_{\boldsymbol{\beta}, \boldsymbol{\beta}^* \in \mathbb{R}^{l+u}} && & - \frac{1}{2} (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \mathbf{Q} (\boldsymbol{\beta}^* - \boldsymbol{\beta}) + (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \tilde{\boldsymbol{y}} - \epsilon (\boldsymbol{\beta}^* - \boldsymbol{\beta})^T \boldsymbol{1} \\ \mathrm{subject~to} && & 0 \le \boldsymbol{\beta}, \boldsymbol{\beta}^* \le C \\ && & \boldsymbol{1}^T(\boldsymbol{\beta} - \boldsymbol{\beta}^*) = 0, \end{align*}

和一些等式

α=β∗−βζ=S−1[ΦTΛy−ΦT(β∗−β)],\begin{align*} \boldsymbol{\alpha} &= \boldsymbol{\beta}^* - \boldsymbol{\beta} \\ \boldsymbol{\zeta} &= \mathbf{S}^{-1} \big[ \mathbf{\Phi}^T \mathbf{\Lambda} \boldsymbol{y} - \mathbf{\Phi}^T (\boldsymbol{\beta}^* - \boldsymbol{\beta}) \big], \end{align*}

其中

S=ΦTΛΦ+μΣLΣL=ΦTLΦQ=K+ΦS−1ΦTy~=ΦS−1ΦTΛy.\begin{align*} \mathbf{S} &= \mathbf{\Phi}^T \mathbf{\Lambda} \mathbf{\Phi} + \mu \mathbf{\Sigma}_\mathbf{L} \\ \mathbf{\Sigma}_\mathbf{L} &= \mathbf{\Phi}^T \mathbf{L} \mathbf{\Phi} \\ \mathbf{Q} &= \mathbf{K} + \mathbf{\Phi} \mathbf{S}^{-1} \mathbf{\Phi}^T \\ \tilde{\boldsymbol{y}} &= \mathbf{\Phi} \mathbf{S}^{-1} \mathbf{\Phi}^T \mathbf{\Lambda} \boldsymbol{y}. \end{align*}

LapESVR 的对偶问题和 SVR 同样具有相同的形式。因此，参考 前文，β∗\boldsymbol{\beta}^*，β\boldsymbol{\beta} 和 bb 都可以通过 sklearn 的 SVR API 来求得。