0 引言

模型组合按一定准则和方式整合假设空间中多个模型, 提高学习系统的泛化性和稳定性, 是机器学习研究的重要课题之一。

基于统计学习理论发展起来的支持向量机(support vector machines, SVM)已广泛应用于模式识别^[1]和数据挖掘^[2]等领域。SVM的性能主要取决于核函数和正则化参数的选择, 常采用交叉验证方法^[3]或根据某个模型选择准则^[4-10]确定最优的SVM模型。然而, 交叉验证方法的计算开销相对较大, 采用不同模型选择准则确定的最优模型之间差异可能很大, 并且模型复杂性不容易度量和计算。无论采用交叉验证方法, 还是应用某一模型选择准则, 都不可避免地存在过拟合或欠拟合的风险。模型组合注重有效整合并充分利用所有的候选模型, 可有效提升SVM性能^[11-17]。

已有的模型组合方法, 如Bagging^[11-13]或Boosting^[14-16], 通常基于数据采样在不同训练样本子集上产生候选模型集合。这种候选模型产生方法, 一方面需要较大规模的训练样本, 在不同训练样本子集上运行多次, 计算开销较大; 另一方面, 子集划分策略直接影响候选模型的性能, 使得选择子集划分策略成为新的困难。此外, 测试过程中, 已有的模型组合方法一般应用全模型集进行预测, 由于性能较差的模型也参与组合预测, 组合模型的预测性能会有所降低, 并且, 全模型集规模过大也会增加组合预测的计算时间。

针对以上问题, 本研究研究正则化路径上的支持向量回归(support vector regression, SVR)模型组合方法。SVR正则化路径算法能在相当于一次SVR求解的时间复杂度内, 获得正则化参数的所有可能取值及对应的最优解^[18-19]。利用这一特性, 可有效地构造出完全的假设空间。已完成的正则化路径上二分类SVM及SVR模型组合方法, 利用正则化路径有效整合假设空间中的模型, 可提高模型的泛化性能^{[17, 20]}。正则化路径上三步式SVM模型组合中, 在预测或测试阶段, 采用输入最近邻方法确定组合模型集^[17]。在正则化路径的基础上, 本文研究ε-不敏感SVR (ε-SVR)模型组合, 并采用输入K-近邻方法确定组合模型集, 以降低最近邻方法潜在的风险。首先, 对ε-SVR模型组合的合理性给出基于样本的理论分析, 证明正则化路径上ε-SVR模型组合的一致性, 奠定正则化路径上模型组合的理论基础。然后, 提出基于正则化路径的三步式ε-SVR模型组合方法。

1 SVR模型组合一致性

本研究首先给出SVR模型贝叶斯组合方式, 然后证明正则化路径上SVR模型组合一致性。

1.1 SVR模型贝叶斯组合

令输入空间为$\mathscr{X}$⊂R^p, 输出空间为$\mathscr{Y}$⊂R, 假设空间$\mathscr{H}$_κ是由正定核κ: $\mathscr{X}$×$\mathscr{X}$→R生成的再生核Hilbert空间, 现假设有训练集

$ T = \left\{ {\left( {{\mathit{\boldsymbol{x}}_1},{y_1}} \right), \cdots ,\left( {{\mathit{\boldsymbol{x}}_n},{y_n}} \right)} \right\} \subset \mathscr{X} \times \mathscr{Y} $

式中: x_i为输入的观测值, 称其为“输入”或“实例”; y_i是输出的响应值; (x_i, y_i)∈T独立同分布于$\mathscr{X}$×$\mathscr{Y}$上的某未知联合分布P, i=1, …, n。

回归问题中, SVR的目标是给出决策函数f, 使其对任意输入x都给出相应的预测输入ŷ=f(x)。令ε >0, 取ε-不敏感损失函数

$ \begin{array}{l} {L_\varepsilon }\left( {y,f\left( x \right)} \right) = {\left| {y - f\left( x \right)} \right|_\varepsilon } = \\ max\left\{ {0,\left| {y - f\left( x \right)} \right| - \varepsilon } \right\}, \end{array} $

正则化项为核κ导出的范数‖f‖${\mathscr{H}_\kappa }$, ε-SVR的正则化形式为

$ \mathop {\min }\limits_{f \in {\mathscr{H}_\kappa }} \frac{1}{n}\sum\limits_{i = 1}^n {{{\left| {{y_i} - f\left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right|}_\varepsilon } + \frac{\lambda }{2}\left\| f \right\|_{{\mathscr{H}_\kappa }}^2} , $

(1)

式中:λ为正则化参数, 用于折衷经验风险与模型的复杂度。对于任意给定的正则化参数λ, ε-SVR最优解的有限形式为

$ f\left( \mathit{\boldsymbol{x}} \right) = {\beta _0} + \frac{1}{\lambda }\sum\limits_{i = 1}^n {{\theta _i}\kappa \left( {\mathit{\boldsymbol{x}},{\mathit{\boldsymbol{x}}_i}} \right)} , $

式中, θ_i∈[-1, +1], i=1, …, n, 其向量形式为θ=(θ₁, …, θ_n)^T。

ε-SVR正则化路径算法能求解并记录正则化参数λ的所有取值及对应ε-SVR的解^[18], 可记作

$ {\rm{RP}} = \left\{ {{\theta _\lambda }|\infty > \lambda \ge 0} \right\}. $

根据上述正则化路径RP可获得正则化参数所有取值下对应的拟合模型f_λ, 由此得到完全模型空间, 记作

$ {\mathscr{M}_{{\rm{RP}}}} = \left\{ {{f_\lambda }|0 \le \lambda < \infty } \right\}. $

定义完全模型空间${\mathscr{M}_{{\rm{RP}}}}$中m (1≤m < ∞)个ε-SVR模型的贝叶斯组合为

$ \bar g\left( \mathit{\boldsymbol{x}} \right) = \sum\limits_{j = 1}^m {{\rm{Pr}}\left( {{f_{{\lambda _j}}}|T} \right){f_{{\lambda _j}}}\left( \mathit{\boldsymbol{x}} \right)} , $

(2)

式中:模型f_λj∈${\mathscr{M}_{{\rm{RP}}}}$; Pr (f_λj|T)为模型f_λj的后验概率, j=1, …, m, 且$\sum\limits_{j = 1}^m {{\rm{Pr}}\left( {{f_{{\lambda _j}}}|T} \right)} = 1$。本研究采用基于模型BIC值的SVR模型后验概率估计方法^[17]

$ {\rm{Pr}}\left( {{{\hat f}_{{\lambda _j}}}|T} \right) = \frac{{{{\rm{e}}^{ - \frac{1}{2} \cdot {\rm{BIC}}\left( {{{\hat f}_{{\lambda _j}}}} \right)}}}}{{\sum\limits_{{{\hat f}_{{\lambda _m}}} \in \mathscr{M}} {{{\rm{e}}^{ - \frac{1}{2} \cdot {\rm{BIC}}\left( {{{\hat f}_{{\lambda _m}}}} \right)}}} }}. $

(3)

ε-SVR模型BIC值的计算将在2.2节详细论述。现将正则化路径上SVR贝叶斯组合模型构成的集合记作$\mathscr{G}$, 即

$ \mathscr{G} = \left\{ {\bar g\left( \mathit{\boldsymbol{x}} \right) = \sum\limits_{j = 1}^m {{\rm{Pr}}\left( {{f_{{\lambda _j}}}|T} \right){f_{{\lambda _j}}}\left( \mathit{\boldsymbol{x}} \right)|{f_{{\lambda _j}}} \in {\mathscr{M}_{\rm{RP}}}} } \right\}. $

1.2 L_ε-风险一致性

对于学习问题来说, 假设空间中存在“真”模型, 则学习得到的模型应该尽可能地逼近“真”模型。

定义1 [一致性]    假设A为某个学习算法, T为训练数据集, n为集合T的规模, f_T是A通过T在模型假设空间$\mathscr{H}$中学习得到的模型。令P表示任意分布, R_P(f_T)表示模型f_T在分布P上的期望风险, R_P^*表示分布P上的Bayes风险。若

$ \mathop {\lim }\limits_{n \to \infty } {R_P}\left( {{f_T}} \right) = R_P^*, $

则称算法A是一致的, 并且模型f_T是“令人满意的”。由ε-SVR的正则化路径可以得到一个完全模型空间${\mathscr{M}_{{\rm{RP}}}}$, 一个非常重要的问题是要保证${\mathscr{M}_{{\rm{RP}}}}$中至少有一个模型是令人满意的。现令损失函数为ε-不敏感损失函数

$ {L_\varepsilon }\left( {y,{\rm{ }}f\left( \mathit{\boldsymbol{x}} \right)} \right) = {\left| {y - f\left( \mathit{\boldsymbol{x}} \right)} \right|_\varepsilon }, $

对于$\mathscr{X}$×$\mathscr{Y}$上的任意分布P, 模型f的L_ε-风险定义为

$ {R_{{L_\varepsilon },P}}\left[ f \right]: = {{\rm{\mathbb{E}}}_{\left( {\mathit{\boldsymbol{x}},y} \right)\sim P}}{L_\varepsilon }\left( {y,f\left( \mathit{\boldsymbol{x}} \right)} \right), $

正则化L_ε-风险定义为

$ {R_{{L_\varepsilon },P,\lambda }}\left[ f \right]: = {R_{{L_\varepsilon },P,\lambda }}\left[ f \right] + \lambda \Omega ({\left\| f \right\|_{{\mathscr{H}_\kappa }}}), $

(4)

定义最优L_ε-风险

$ R_{{L_\varepsilon },P}^*: = {\rm{inf}}\left\{ {{R_{{L_\varepsilon },P}}\left[ f \right]|f:\mathscr{X} \to {\rm{measuable}}} \right\}。 $

若P是关于训练数据集T的经验分布, 则

$ {R_{{L_\varepsilon }}},T\left[ f \right]: = \frac{1}{n}{L_\varepsilon }\left( {{y_i},{\rm{ }}f\left( {{\mathit{\boldsymbol{x}}_i}} \right)} \right), $

和

$ R_{{L_\varepsilon },T,\lambda }^{{\rm{reg}}}\left[ f \right]: = {R_{{L_\varepsilon },T}}\left[ f \right] + \lambda \Omega \left( {{{\left\| f \right\|}_{\mathscr{H}\kappa }}} \right), $

(5)

分别表示模型f的经验L_ε-风险和正则化经验L_ε-风险。可以看出, 若正则化函数${\Omega }({\left\| f \right\|_{{\mathscr{H}_K}}}) = {\left\| f \right\|^2}_{{\mathscr{H}_K}}$, 则正则化经验L_ε-风险(5)与优化问题(1)的目标函数相同。

由以上定义, 定义组合模型的L_ε-风险

$ {R_{{L_\varepsilon },P}}[\bar g]: = {{\rm{\mathbb{E} }}_{\left( {\mathit{\boldsymbol{x}},y} \right)\sim P}}{L_\varepsilon }\left( {y,\bar g\left( \mathit{\boldsymbol{x}} \right)} \right), $

定义经验L_ε-风险

$ {R_{{L_\varepsilon },T}}[\bar g]: = \frac{1}{n}\sum\limits_{i = 1}^n {{L_\varepsilon }({y_i},({\mathit{\boldsymbol{x}}_i}))} 。 $

应用以上各类风险, 在定义1的基础上定义L_ε -风险一致性。

定义2 [L_ε-风险一致性]    设A是一个学习算法, T是训练数据集, n为集合T的势, f_T是A通过T在假设空间$\mathscr{H}$中得到的模型。对任意分布P, 若

$ \mathop {\lim }\limits_{n \to \infty } {R_{{L_\varepsilon },P}}\left[ {{f_T}} \right]{ \to _{\rm{P}}}R_{{L_\varepsilon },P}^*, $

则A为L_ε-风险一致的。

1.3 模型组合的L_ε-风险一致性

对输入空间$\mathscr{X}$及假设空间${\mathscr{H}_\kappa }$的基本假设为:

(1) 输入空间$\mathscr{X}$⊂R^p为紧集;

(2) 输出y的一阶矩有限, 即|y|≤∞;

(3) 假设空间${\mathscr{H}_{{\kappa _\varepsilon }}}$是由有界普适核^[21]κ导出再生核Hilbert空间, 即

$ \bar \kappa = {\left\| \mathit{\boldsymbol{\kappa }} \right\|_\infty }: = \mathop {{\rm{sup}}}\limits_{\mathit{\boldsymbol{x}} \in X} \sqrt {\kappa \left( {\mathit{\boldsymbol{x}},\mathit{\boldsymbol{x}}} \right)} {\rm{ }} < \infty . $

作为Christmann和Steinwart^[22]提出的基于凸风险最小化的核回归方法一致性的一个实例, 引理1说明了ε-SVR的一致性。

引理1    假设(1)~(3), 若存在序列(λ_n)使得λ_n→0且nλ_n² →∞, 则ε-SVR是L_ε-风险一致的, 对任意分布P:

$ \mathop {\lim }\limits_{n \to \infty } {R_{{L_\varepsilon },P}}\left[ {{f_T}} \right]{ \to _{\rm{P}}}R_{{L_\varepsilon },P}^* $

式中f_T为ε-SVR优化问题(1)的最优解。

由于本研究讨论的是正则化路径ε-SVR的模型组合, 因此有必要考查ε-SVR正则化路径上是否存在L_ε -风险一致的模型。

命题1    假设(1)~(3), 由ε-SVR正则化路径得到的全模型集中至少包含一个模型是L_ε-风险一致的。

证明    由引理1可知, ε-SVR在假设条件(1)~(3)下是L_ε-风险一致的。已知Karush-Kuhn-Tucker (KKT)最优化条件是求解ε-SVR优化问题最优解的充分必要条件^[18], 且正则化路径算法是遵循KKT条件的, 所以对于任意给定的正则化参数λ, ε-SVR优化问题的最优解必出现在正则化路径上, 由此命题得证。

下面证明基于正则化路径的ε-SVR贝叶斯模型组合的L_ε-风险一致性。

定理1    假设(1)~(3), 若存在序列(λ_n)使得λ_n→0且nλ_n² →∞, 则基于正则化路径的ε-SVR贝叶斯模型组合是L_ε-风险一致的, 即

$ \mathop {\lim }\limits_{n \to \infty } {R_{{L_\varepsilon },P}}\left[ {\bar g} \right]{ \to _{\rm{P}}}R_{{L_\varepsilon },P}^*。 $

证明    损失函数L_ε是Lipschitz连续的, 其Lipschitz常数|L_ε|₁=1, 结合假设(3), 对于任意两个模型f, f′∈${\mathscr{H}_\kappa }$, 两者的期望风险之差与${\mathscr{H}_\kappa }$中范数之间的关系为

$ \begin{array}{l} {R_{{L_\varepsilon },P}}\left( f \right) - {R_{{L_\varepsilon },P}}\left( {f\prime } \right)| \le \\ \;\;\;\;\smallint \left| {{L_\varepsilon }\left( {y,{\rm{ }}f\left( \mathit{\boldsymbol{x}} \right)} \right) - {L_\varepsilon }\left( {y,{\rm{ }}f\prime \left( \mathit{\boldsymbol{x}} \right)} \right)} \right|{\rm{d}}P\left( {\mathit{\boldsymbol{x}},y} \right) \le \\ \;\;\;\;\smallint \left| {{L_\varepsilon }\left( {y,{\rm{ }}f\left( \mathit{\boldsymbol{x}} \right)} \right) - {L_\varepsilon }\left( {y,{\rm{ }}f\prime \left( \mathit{\boldsymbol{x}} \right)} \right)} \right|{\rm{d}}P\left( {\mathit{\boldsymbol{x}},y} \right) \le \\ \;\;\;\;{\left| {{L_\varepsilon }} \right|_1}{\left\| {f - f\prime } \right\|_\infty } \le {\left\| {f - f\prime } \right\|_\infty } \le \\ \;\;\;\bar \kappa \;{\left\| {f - f\prime } \right\|_{{\mathscr{H}_\kappa }}}。 \end{array} $

(6)

由f, f′的任意性, 现讨论组合模型g的期望风险与正则化期望风险最小化模型f_{P, λ}的期望风险之间的关系。将g和f_{P, λ}分别替换f和f′, 由式(6)可以得到

$ \begin{array}{l} \left| {{R_{{L_\varepsilon },P}}({\bar g}) - {R_{{L_\varepsilon },P}}\left( {{f_{P,\lambda }}} \right)} \right|{\rm{ }} \le \bar \kappa {\left\| {{\bar g} - {f_{P,\lambda }}} \right\|_{{\mathscr{H}_\kappa }}} = \\ \;\;\;\;\bar \kappa {\left\| {\sum\limits_{j = 1}^m {{w_j}{f_{T,{\lambda _j}}} - {f_{P,\lambda }}} } \right\|_{{\mathscr{H}_\kappa }}} = \\ \;\;\;\;\bar \kappa {\left\| {\sum\limits_{j = 1}^m {{w_j}{f_{T,{\lambda _j}}}} - \sum\limits_{j = 1}^m {{w_j}{f_{P,\lambda }}} } \right\|_{{\mathscr{H}_\kappa }}} = \\ \;\;\;\;\bar \kappa {\left\| {\sum\limits_{j = 1}^m {{w_j}\left( {{f_{T,{\lambda _j}}} - {f_{P,\lambda }}} \right)} } \right\|_{{\mathscr{H}_\kappa }}} = \\ \;\;\;\;\bar \kappa {\left\| {{w_1}\left( {{f_{T,{\lambda _1}}} - {f_{P,\lambda }}} \right) + \ldots + {w_m}\left( {{f_{T,{\lambda _m}}} - {f_{P,\lambda }}} \right)} \right\|_{{\mathscr{H}_\kappa }}} \le \\ \;\;\;\;\bar \kappa ({w_1}{\left\| {{f_{T,{\lambda _1}}} - {f_{P,\lambda }}} \right\|_{{\mathscr{H}_\kappa }}} + \ldots + \\ \;\;\;\;{w_m}{\left\| {{f_{T,{\lambda _m}}} - {f_{P,\lambda }}} \right\|_{{\mathscr{H}_\kappa }}}) = \\ \;\;\;\;\bar \kappa \sum\limits_{j = 1}^m {{w_j}} {\left\| {{f_{T,{\lambda _j}}} - {f_{P,\lambda }}} \right\|_{{\mathscr{H}_\kappa }}}, \end{array} $

再结合凸函数次微分定义、性质^[22]及|L_ε|₁=1, 可得存在ε > 0使得${\left\| {{f_{T,{\lambda _j}}} - {f_{P,\lambda }}} \right\|_{{\mathscr{H}_\kappa }}} \le \varepsilon $, 由此,

$ \left| {{R_{{L_\varepsilon },P}}({\bar g}) - {R_{{L_\varepsilon },P}}\left( {{f_{P,\lambda }}} \right)} \right|{\rm{ }} \le \bar \kappa \sum\limits_{j = 1}^m {{w_j}} \varepsilon = \bar \kappa \varepsilon , $

于是可以得到

$ \begin{array}{l} \left| {{R_{{L_\varepsilon },P}}(\bar g) - R_{{L_\varepsilon },P}^*} \right|{\rm{ }} \le \\ \;\;\;\;\left| {{R_{{L_\varepsilon },P}}(\bar g) - {R_{{L_\varepsilon },P}}\left( {{f_{P,\lambda }}} \right)} \right| + \\ \;\;\;\;\left| {{R_{{L_\varepsilon },P}}\left( {{f_{P,\lambda }}} \right) - R_{{L_\varepsilon },P}^*{\rm{ }}} \right| \le 2\bar \kappa \varepsilon 。 \end{array} $

再结合引理1可得本定理结论。

由定理1的证明过程可以看出, 关键是考查组合模型g的期望风险能否依概率收敛到最优风险, 这虽然在实践中无法验证, 但是对模型组合的统计特性进行了数学证明, 为模型组合方法奠定理论基础。

2 三步式贝叶斯组合

本节设计并实现正则化路径上基于输入K-近邻的三步式ε-SVR贝叶斯组合。

2.1 初始模型集

由ε-SVR正则化路径可得到完全模型集${\mathscr{M}_{{\rm{RP}}}}$。由正则化路径建立过程可知^[17], ε-SVR的正则化路径上相邻两个拐点之间, 支持向量集并不发生变化。由此, 根据正则化路径上的拐点, 从完全模型集${\mathscr{M}_{{\rm{RP}}}}$中选择有限个ε-SVR模型组成初始模型集, 并将其记作

$ {\mathscr{M}_{{\rm{init}}}} = \left\{ {{f_{{\lambda _1}}}, \ldots ,{\rm{ }}{f_{{\lambda _l}}}} \right\}, $

式中l为正则化路径上拐点个数。初始模型集${\mathscr{M}_{{\rm{init}}}}$中包含了所有可能复杂度的模型。大量试验表明, 预测性能差的模型参与模型组合, 会降低组合模型的泛化性, 因此需要对初始模型集进行修剪, 采用一定的策略从初始模型集合中剔除预测性能较差的模型, 以得到候选模型集。

2.2 平均BIC准则修剪策略

BIC (Bayesian information criterion)是一种常用的模型选择准则, BIC模型的一般形式为

$ {\rm{BIC}} = - 2\cdot{\rm{log}}\;{\rm{lik}} + \frac{{{\rm{log}}\left( n \right)}}{n}\cdot{\rm{d}}f, $

其中:log lik为模型的对数似然; df为模型自由度。对于正则化路径上的ε-SVR模型, 本文采用

$ - 2\cdot{\rm{log}}\;{\rm{lik}} = \frac{1}{{n{\sigma ^2}}}\sum\limits_{i = 1}^n {{{\left( {{y_i} - {f_\lambda }\left( {{\boldsymbol{x}_i}} \right)} \right)}^2}} , $

近似计算模型的对数似然, 方差σ²通过低偏差模型的均方差获得。对模型自由度的估计, 本研究沿用Gunter Lacey和Zhu Ji提出的无偏估计方法^[18]。给定输入x, 以分布y~(μ(x), σ²)生成输出y, 其中μ为真实均值, σ²为方差。定义SVR模型f的自由度

$ {\rm{d}}f\left( f \right) = \sum\limits_{i = 1}^n {{\rm{cov}}\left( {f\left( {{\boldsymbol{x}_i}} \right),{y_i}} \right)/{\sigma ^2}} , $

该值的无偏估计为$\sum\limits_{i = 1}^n {\frac{{\partial f\left( {{\boldsymbol{x}_i}} \right)}}{{\partial {y_i}}}} $。

ε-SVR的正则化路径上对于某个固定的正则化参数λ :

$ {\rm{d}}f(f) \equiv \sum\limits_{i = 1}^n {\frac{{\partial f\left( {{\boldsymbol{x}_i}} \right)}}{{\partial {y_i}}}} = \left| {{\mathscr{E}_\mathscr{R}}} \right| + \left| {{\mathscr{E}_\mathscr{L}}} \right|, $

其中$\left| {{\mathscr{E}_\mathscr{R}}} \right| + \left| {{\mathscr{E}_\mathscr{L}}} \right|$为活动集的规模。因此, 模型集合${\mathscr{M}_{{\rm{init}}}}$中任意模型f_λ的BIC值的近似为:

$ {\rm{BIC}}\left( {{f_\lambda }} \right) = \frac{{{{\left\| {\boldsymbol{y} - {\boldsymbol{f}_\lambda }} \right\|}^2}}}{{n{\sigma ^2}}} + \frac{{{\rm{log}}\left( n \right)}}{n}{\rm{df}}\left( {{f_\lambda }} \right), $

式中: f_λ=(f_λ(x₁), …, f_λ(x_n))^T, y=(y₁, …, y_n)^T。

模型的BIC值越小, 模型在误差和模型参数的要求达到越佳, 模型越好, 因此可以用平均BIC的方法从初始模型集中将BIC值较大的模型剔除。对于初始模型集${\mathscr{M}_{{\rm{init}}}}$, 平均BIC的计算为

$ {B_{{\rm{aBIC}}}} = \frac{1}{l}\sum\limits_{j = 1}^l {{\rm{BIC}}\left( {{f_{{\lambda _j}}}} \right)} . $

考查初始模型集${\mathscr{M}_{{\rm{init}}}}$的所有模型, 将BIC值大于平均值BIC的模型从候选模型中剔除, 由此得到的候选模型集合为${\mathscr{M}_{{\rm{aBIC}}}}$。基于平均BIC准则的模型集修剪过程如算法1所示, 该算法在求解ε -SVR正则化路径过程中完成, 计算每个模型BIC值的时间复杂度为O(n), 则该算法时间复杂度为O(cn²), 其中, c为某常数。

算法1平均BIC算法

Input: ${\mathscr{M}_{{\rm{init}}}}$={fλ1, …, fλk} Output: ${\mathscr{M}_{{\rm{aBIC}}}}$ for j∈{1, …, k}do     Compute BIC (fλj) end ${B_{{\rm{aBIC}}}} = \frac{1}{l}\sum\limits_{j = 1}^l {{\rm{BIC}}\left( {{f_{{\lambda _j}}}} \right)} $ ${\mathscr{M}_{{\rm{tmp}}}} = \emptyset $ for j∈{1, …, l} do     if BIC (fλj) > BaBIC then         ${\mathscr{M}_{{\rm{tmp}}}}$=${\mathscr{M}_{{\rm{tmp}}}}$∪{fλj}     end end ${\mathscr{M}_{{\rm{aBIC}}}}$=${\mathscr{M}_{{\rm{init}}}}$\${\mathscr{M}_{{\rm{tmp}}}}$ Return ${\mathscr{M}_{{\rm{aBIC}}}}$

2.3 输入K-近邻模型组合算法

对于SVR来说, 学习的目标是通过在训练集上学习找到一个模型f, 使其具有良好的泛化性, 应用平均BIC准则已得到候选模型集。为了能对新输入x_new有更好预测, 需要在已有候选模型集基础上, 根据x_new选择多个模型, 实现组合预测。由此, 本研究提出基于输入K-近邻的SVR贝叶斯模型组合算法SVRBMC_KNN。

模型组合的泛化性可通过对新输入x_new的预测来衡量。由于数据的分布未知, 因此无法计算组合误差的期望。本研究中应用K-近邻方法来估计对新输入x_new的预测误差, 用欧式距离度量输入之间的距离, 即x和x′之间的距离为

$ d\left( {\mathit{\boldsymbol{x}},\mathit{\boldsymbol{x}}\prime } \right) = {\left\| {\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{x}}\prime } \right\|_2}。 $

训练样本集中, 新输入x_new的K个近邻输入记作x^K={x_k1, …, x_kk}, k₁, …, k_k∈[1, n]。

首先, 计算候选模型集${\mathscr{M}_{{\rm{aBIC}}}}$中所有ε-SVR模型在新输入x_new的K个近邻构成的样本点集T^K={(x_k1, y_k1), …, (x_kk, y_kk)}上的平均预测误差

$ {e_K}\left( f \right) = \frac{1}{K}\sum\limits_{j = 1}^K {{{\left| {{y_{{k_j}}} - f\left( {{\boldsymbol{x}_{{k_j}}}} \right)} \right|}_\varepsilon }} f \in {\mathscr{M}_{{\rm{aBIC}}}}. $

然后, 对${\mathscr{M}_{{\rm{aBIC}}}}$中所有模型的平均预测误差按升序排列。最后, 按平均预测误差从低到高的顺序依次将${\mathscr{M}_{{\rm{aBIC}}}}$中模型加入最终组合模型集${\mathscr{M}_{{\rm{com}}}}$中。

建立最终组合模型集过程中, 每加入一个模型就要计算组合模型的平均误差, 直到误差不再下降, 选择过程结束。组合模型的平均误差

$ {e_K}(\bar g) = \frac{1}{K}\sum\limits_{j = 1}^K {{{\left| {{y_{{k_j}}} - \bar g\left( {{\boldsymbol{x}_{{k_j}}}} \right)} \right|}_\varepsilon }} 。 $

由于整个选择过程是动态变化的, 按照本研究提出的模型后验概率的计算方法(式(2)), 一旦组合模型集中有模型加入, 就需要更新组合模型集中所有的模型的后验概率。

基于输入K-近邻方法的SVR贝叶斯模型组合实现过程如算法2所示。确定组合模型集过程中包括在训练样本集中搜索新输入的K-近邻和对所有模型的预测误差排序, 由此该过程的时间复杂度为O(cnlog (cn))。另外, 模型后验概率估计的时间复杂度为O(n), 则计算初始模型集中所有模型后验概率的时间复杂度为O(cn²)。综上所述, 基于输入的K-近邻的三步式贝叶斯模型组合的时间复杂度为O(cn²)。

由此, 对新输入x_new的组合预测为

$ {{\hat y}_{{\rm{new}}}} = \bar g({\mathit{\boldsymbol{x}}_{{\rm{new}}}}) = \sum\limits_{f \in {\mathscr{M}_{{\rm{com}}}}} {f\left( {{\mathit{\boldsymbol{x}}_{{\rm{new}}}}} \right)} {\rm{Pr}}(f|T). $

算法2 SVRBMCKNN算法

Input: ${\mathscr{M}_{{\rm{aBIC}}}}$       $\mathscr{P}$={Pr (f|T)|f∈${\mathscr{M}_{{\rm{aBIC}}}}$}       T={(x1, y1), …, (xn, yn)}, xnew Output: ${{\mathscr{M}_{{\rm{com}}}}}$, g, ŷnew ${\mathscr{M}_{{\rm{com}}}} = \emptyset $ Find the K-nearest neighbor set xK of xnew in T Compute average prediction error for model set TK while ${\mathscr{M}_{{\rm{aBIC}}}} = \emptyset $ do   fm=f∈${\mathscr{M}_{{\rm{aBIC}}}}$ with lowest prediction error   ${{\mathscr{M}_{{\rm{com}}}}}$=${{\mathscr{M}_{{\rm{com}}}}}$∪{fm}   ${\mathscr{M}_{{\rm{aBIC}}}}$=${\mathscr{M}_{{\rm{aBIC}}}}$\{fm}   Update $\mathscr{P}$   Compute g(xk1), …, (xkk)   if eK(g) is greater than last time do     break   end end $\bar g({\mathit{\boldsymbol{x}}_{{\rm{new}}}}) = \sum\limits_{f \in {M_{{\rm{com}}}}} {f\left( {{\mathit{\boldsymbol{x}}_{{\rm{new}}}}} \right)} {\rm{Pr}}(f|T)$ Return: ${{\mathscr{M}_{{\rm{com}}}}}$, g, ŷnew

3 试验结果与分析

本节设计试验测试正则化路径上ε-SVR贝叶斯组合的预测性能和算法运行效率。本研究试验采用的普适核为高斯核

$ \kappa \left( {\mathit{\boldsymbol{x}},{\rm{ }}\mathit{\boldsymbol{x}}\prime } \right) = {\rm{exp}}( - {\left\| {\mathit{\boldsymbol{x}} - \mathit{\boldsymbol{x}}\prime } \right\|^2}/2{\sigma ^2}). $

试验中, 核参数σ和不敏感参数ε在每个数据集上的最优组合取值由3折交叉验证确定, 如表 1所示。

本研究选用University of California Irvine (UCI)机器学习数据库中的5个标准数据集作为试验中的数据集。每组试验中, 从数据集abalone的4 177个样本中随机选择1 000个样本组成试验数据; 从数据集cpusmall的8 192个样本中随机选择1 000个样本组成试验数据; 从数据集space_-ga的3 107个样本中随机选择1 000个样本组成试验数据。各数据集的试验样本规模及特征维数如表 1所示。每组试验中, 从每个试验数据集中随机抽取80%作为训练样本, 20%作为测试样本。每个算法在各数据集上重复实验50次并统计平均测试结果。

3.1 性能测试

本研究以测试集上的预测误差作为预测性能评价标准, 测试误差定义

$ {\rm{PredE}}: = \frac{1}{m}\sum\limits_{j = 1}^m {{{\left( {{y_j} - \hat g\left( {{\boldsymbol{x}_j}} \right)} \right)}^2}} , $

式中:m为测试集规模; ĝ为组合模型或单模型。

首先, 选用3-折交叉验证法和BIC准则分别从ε-SVR正则化路径选择最优模型, 贝叶斯模型组合分别应用1-近邻、3-近邻和5-近邻3种方式实现SVRBMC_KNN算法, 然后对比上述5种方法的预测性能。5种方法测试误差的平均值及标准差统计结果如表 2所示, 其中, Pred_CV为应用3-折交叉验证选择的最优模型的预测误差, Pred_BIC为基于BIC准则选择的最优模型的预测误差, Pred_1-com为基于1-近邻方法的组合模型集${{\mathscr{M}_{{\rm{com}}}}}$上模型组合的预测误差, Pred_3-com为基于3-近邻方法的组合模型集${{\mathscr{M}_{{\rm{com}}}}}$上模型组合的预测误差, Pred_5-com为基于5-近邻方法的组合模型集${{\mathscr{M}_{{\rm{com}}}}}$上模型组合的预测误差; Mean表示预测误差的平均值, SD表示预测误差的标准差。

从表 2中可以看出, 正则化路径上贝叶斯组合方法的预测性能比单模型的预测性能好, 且具有较好的稳定性; 3种近邻方法的模型组合中, 1-近邻方法的预测误差的平均值较低, 标准差较高, 5-近邻方法的预测误差的平均值较高, 标准差较低, 说明基于5-近邻方法的模型组合的稳定性较高。

然后, 设计试验对比SVRBMC_SNN模型组合与Bagging模型组合的预测性能。该试验中Bagging组合算法各参数采用默认值。预测误差的平均值及标准差的统计结果分别如表 3所示, 其中Pred_Bag为Bagging模型组合的预测误差。

从表 3中可以看出, 在数据集housing和mpg上Bagging的预测误差平均值较低, 而在另外3个数据集上, 1-近邻、3-近邻和5-近邻的SVRBMC_SNN模型组合的预测误差平均值较低。所有数据集上SVRBMC_SNN模型组合预测误差的标准差都比Bagging的要低, 说明SVRBMC_SNN模型组合的稳定性要高。

3.2 运行效率

首先, 设计试验对比正则路径上基于输入K-近邻ε -SVR贝叶斯组合方法与3折交叉验证模型选择方法的运行时间, 包括训练时间和测试时间。试验统计结果如表 4所示, 其中, t_3CV为3折交叉验证模型选择方法的运行时间, t_com为ε-SVR贝叶斯组合方法的运行时间。从表 4中可以看出, 组合方法的运行时间较短。

综合以上试验结果可以看出, 正则化路径上基于输入K-近邻的模型组合具有较好的预测性能及较高计算效率。

4 结语

SVR正则化路径的分段线性性质为选择基模型提供了便利。本研究提出的正则化路径上基于输入K-近邻的三步式ε-SVR模型组合, 以简单有效的方法实现了基模型的产生、候选模型集的构建以及组合预测。通过对输入空间及假设空间作基本假设, 证明了正则化路径上ε -SVR组合模型的L_ε-风险可收敛到最优L_ε-风险。ε -SVR模型组合一致性的证明发展了SVR模型组合的理论研究。模型集构造过程中, 首先根据ε-SVR正则化路径的分段线性性质, 选择正则化路径上所有拐点处模型构成初始模型集, 然后应用平均BIC准则确定候选模型。测试阶段, SVRBMC_KNN模型组合算法应用K-近邻方法确定输入敏感的最终组合模型集, 并实现贝叶斯组合预测。标准数据集上的试验验证了正则化路径上基于输入K-近邻的三步式ε-SVR模型组合方法的稳定性和计算效率。