集成回归的有效性证明（更新）

本文提供集成回归的有效性证明

我们在集成分类有效性证明上证明集成学习于分类问题的有效性，今天我们证明集成学习在回归问题上的有效性。

1 集成回归模型

设有集成回归模型

$\begin{align} H_T(x) = \sum_{i=1}^{T}\omega_{i}f_{i}(x) \newline \text{s.t.} \sum_{i=1}^{T}\omega_{i} = 1 \end{align}$

基模型集合为 $F=\left \{ f_{1},f_{2},...,f_{T} \right \}$ ，它们分别从数据集 $\left \{ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n}) \right \}$ 训练得到。容易计算这些模型的误差

$\begin{align} e_1 &= y - f_1 \newline e_2 &= y - f_2 \newline & \vdots \newline e_T &= y - f_T \end{align}$

假定预测模型的误差都是无偏的，即

$\begin{align} E[e_1] &= 0 \newline E[e_2] &= 0 \newline &\vdots \newline E[e_T] &= 0 \newline \end{align}$

预测模型误差的方差为

$var(e_1) = \sigma_1^{2} \\ var(e_1) = \sigma_2^{2} \\ ... \\ var(e_T) = \sigma_T^{2} \\$

2 集成预测的有效性证明

2.1 有效性证明

假设有随机过程：

$\left \{ Y_{t} | t \in T \right \}$

从监控平台获得观察样本：

$\left \{ (t_{1},y_{1}),(t_{2},y_{2}),...,(t_{n},y_{n}) \right \}$

通过样本训练得到 T 个预测模型：

$\left \{ f_{1},f_{2},...,f_{T} \right \}$

容易计算这些模型的误差：

$e_1 = y - f_1 \\ e_2 = y - f_2 \\ ... \\ e_T = y - f_T$

假定预测模型的误差都是无偏的，有：

$E[e_1] = 0 \\ E[e_2] = 0 \\ ... \\ E[e_T] = 0 \\$

预测模型的方差：

$var(e_1) = \sigma_1^{2} \\ var(e_1) = \sigma_2^{2} \\ ... \\ var(e_T) = \sigma_T^{2} \\$

现在，我们把所有预测模型进行线性组合：

$H(T) = \sum_{i=1}^{T}\omega_{i}f_{i} \\ s.t. \sum_{i=1}^{T}\omega_{i} = 1$

$H(T)$ 成为一个新的机器学习模型，其假设空间为：

$Span\{f_{1}, f_{2},...,f_{T}\}$

该空间的代数性质我们有空再分析。模型的学习策略是一个凸最优化过程，并且有解析解，等会我们提到。

有集成模型的误差：

$\begin{align} e = y - H(T) \end{align}$

不难计算这个组合模型的误差的均值：

$\begin{align} E[e] &= E[y-H(T)] \\ &= E[y-\sum_{i=1}^{T}\omega_{i}f_{i}] \\ &= E[y \cdot 1-\sum_{i=1}^{T}\omega_{i}f_{i}] \\ &= E[y\sum_{i=1}^{T}\omega_{i} - \sum_{i=1}^{T}\omega_{i}f_{i}] \\ &= E[\sum_{i=1}^{T}\omega_{i}(y-f_{i})] \\ &= \sum_{i=1}^{T}\omega_{i}E[y-f_{i}] \\ &= 0 \end{align}$

也就是说，无偏的预测模型的线性组合是无偏的。

不难计算组合模型的方差：

$\begin{align} var(e) &= var(y-H(T)) \\ &= var(y\sum_{i=1}^{T}\omega_{i} - \sum_{i=1}^{T}\omega_{i}f_{i}) \\ &= var(\sum_{i=1}^{T}\omega_{i}(y-f_{i})) \\ &= \sum_{i,j=1}^{T}cov(\omega_{i},e_{i}) \\ &= \sum_{i=1}^{T}\omega_{i}^{2}\sigma_{i}^{2} + \sum_{i\neq j}^{T}cov(\omega_{i},e_{i}) \end{align}$

假定预测模型之间没有关系，即所有模型均为集成模型的假设空间的基，那么协方差取值均为 0，则有：

$var(e) = \sum_{i=1}^{T}\omega_{i}^{2}\sigma_{i}^{2}$

现在有两个问题：

组合后的模型的权重如何分配？
组合后的模型的预测效果怎么样？

对于第一个问题，通过最优化方法求解，对于第二个问题，自定义指标并评估它的下限来估计预测效果。下面我们一一分析。

根据上述组合模型的无偏特点以及方差的性质，不难有：

$\begin{align} var(e) &= E[e^{2}] - E^{2}[e] \\ &= E[e^{2}] \end{align}$

也就是说，为了让组合模型的误差最小，我们只需要让方差最小即可，因此不同预测模型的权重的求解就成了最优化问题。我们有如下优化问题：

$\left\{\begin{matrix} \min \displaystyle \sum_{i=1}^{T}\omega_{i}^{2}\sigma_{i}^{2} \\ s.t. \displaystyle \sum_{i=1}^{T}\omega_{i} = 1 \end{matrix}\right.$

不难看出，目标函数为凸函数，因此极值点即为目标函数的最小值点。根据目标函数，从几何直观上，我们不难理解权重具有某种对称性。（如果相反，保留最大方差会怎样？）

为求解权重，我们使用拉格朗日乘子，得：

$L(\omega_{1},\omega_{2},...\omega_T,\lambda) = \sum_{i=1}^{T}\omega_{i}^{2}\sigma_{i}^{2} - \lambda(\sum_{i=i}^{T}\omega_{i}-1)$

分别对各个权重求偏导数且零取值为 0，得：

$\frac{\partial L(\omega_{1},\omega_{2},...,\omega_T,\lambda)}{\partial \omega_{i}} = 2\omega_{i}\sigma_{i}^2 - \lambda = 0$

解得：

$\omega_{i} = \frac{\lambda}{2\sigma_{i}^{2}}$

由于 $\sum_{i=i}^{T}\omega_{i}=1$ ，代入消除 $\lambda$ ，得到：

$\omega_{i} = \frac{\sigma_{i}^{-2}}{\displaystyle \sum_{i=1}^{T}\sigma_{i}^{-2}}$

这个结论是否能用于 Pooling 池化

正如我们上述的直观判断，解有对称性。不难发现，这个解说明如果一个模型的方差越小，其在集成模型中占的权重越大。另外，我们可以知道每个模型在集成模型中占的权重是唯一的，这一点为集成模型的假设空间看做线性空间提供依据，后期我们有空再讨论。

因此，我们有集成模型的方差：

$\begin{align} var(e) &= \sum_{i=1}^{T}\omega_{i}^{2}\sigma_{i}^{2} \\ &= \sum_{i=1}^{T}(\frac{\sigma_{i}^{-2}}{\sum_{i=1}^{T}\sigma_{i}^{-2}})^{2}\sigma_{i}^{2} \\ &= \frac{1}{\sum_{i=1}^{T}\frac{1}{\sigma_{i}^{2}}} \end{align}$

不难估计这个方差的上界，不难得到下式：

$\sum_{i=1}^{T}\frac{1}{\sigma_{i}^2} \geqslant \max(\frac{1}{\sigma_{1}^{2}},...,\frac{1}{\sigma_{T}^{2}}) \\$

易知：

$\max(\frac{1}{\sigma_{1}^{2}},...,\frac{1}{\sigma_{T}^{2}}) = \frac{1}{\min(\sigma_{1}^{2},...,\sigma_{T}^2)} \\$

对上述不等式左右两边分别取倒数，改变符号，有：

$var(e) = \frac{1}{\sum_{i=1}^{T}\frac{1}{\sigma_{i}^{2}}} \leqslant \min(\sigma_{1}^{2},...,\sigma_{T}^2)$

这说明，不同性能的预测模型通过恰当的线性组合得到的集成预测模型比预测性能最好的模型还要好！这证明我们的直觉判断是错误的。

2.2 评估（补充）

现在我们要评估集成模型的预测性能比预测性能最好的模型好多少，为此定义如下两个指标：

$D = min(\sigma_{1}^{2},...,\sigma_{T}^2) - \frac{1}{\sum_{i=1}^{T}\frac{1}{\sigma_{i}^{2}}} \\ Q = min(\sigma_{1}^{2},...,\sigma_{T}^2) \sum_{i=1}^{T}\frac{1}{\sigma_{i}^{2}}$

D 越大，集成模型的性能越好，Q 越大，集成模型的性能越好。接下来分别评估这两个指标的下界，以获得模型选择有关的信息。

现在，我们对模型 $f_{1}, f_{2},...,f_{T}$ 的方差重新排序并标号，使其满足如下关系：

$\sigma{'}_{1}^{2} \geqslant \sigma{'}_{2}^{2} \geqslant ... \geqslant \sigma{'}_{T}^{2}$

因此，有：

$\begin{align} Q &= min(\sigma{'}_{1}^{2},...,\sigma{'}_{T}^2) \sum_{i=1}^{T}\frac{1}{\sigma{'}_{i}^{2}} \\ &= \sigma{'}_{T}^{2}\sum_{i=1}^{T}\frac{1}{\sigma{'}_{i}^{2}} \\ &= 1 + \sigma{'}_{T}^{2}\sum_{i=1}^{T-1}\frac{1}{\sigma{'}_{i}^{2}} \\ &\geqslant 1 \end{align}$

最后一项，当 $T=1$ ，即只有一个模型时取等号。这说明，我们我们选择进行集成的候选模型的预测性能越好，集成后的预测性能越好。

类似地，对于指标 D 使用调和-均值不等式有：

$\begin{align} D &= \sigma{'}_{T}^{2} - \frac{1}{\sum_{i=1}^{T}\frac{1}{\sigma{‘}_{i}^{2}}} \\ &\geqslant \sigma{'}_{T}^{2} - \frac{1}{T^{2}}\sum_{i=1}^{T}\sigma{'}_{i}^{2} \\ &\geqslant 0 \end{align}$

这个不等式表明，当我们使用的模型数量越多时，集成模型的预测性能越好。

类似地，在分类问题上，根据Hoeffding不等式可得类似的结论：

$\begin{align} P(H(x)\neq f(x)) &= \sum_{i=0}^{[T/2]}\binom{T}{k}(1-\varepsilon)^{k}\varepsilon^{T-k} \\ &\leqslant \exp(-\frac{1}{2}T(1-2\varepsilon)^2) \end{align}$

更多概率不等式可参看漫谈概率论与信息论中的不等式。那么，现在的问题是，我们应该使用怎样的模型进行集成？使用多少个模型进行集成？这个留作读者思考。

通过以上思路，我们证明了，不同性能的预测模型通过恰当的线性组合得到的集成预测模型比预测性能最好的模型还要好！

总结

以上我们证明了不同性能的预测模型通过恰当的线性组合得到的集成预测模型比预测性能最好的模型还要好，这正是集成模型的魅力。在这个基础上可以设计集成时间序列预测模型。

转载请包括本文地址：https://allenwind.github.io/blog/10114/

更多文章请参考：https://allenwind.github.io/blog/archives/