Question

5.1 误差-分歧分解

1. 假定有 $ MathJax-Element-180 $ 个个体学习器 $ MathJax-Element-181 $ ，通过加权平均法组合产生集成学习器 $ MathJax-Element-192 $ 来完成回归学习任务。即： $ MathJax-Element-194 $ 。

   • 对于某个样本 $ MathJax-Element-189 $ ，定义学习器 $ MathJax-Element-262 $ 的分歧ambiguity为： $ MathJax-Element-186 $ 。

     分歧刻画了个体学习器在某个样本 $ MathJax-Element-189 $ 上的不一致性，在一定程度上反映了个体学习器的多样性。

   • 定义集成学习器的分歧为 : $ MathJax-Element-188 $ 。

2. 设样本 $ MathJax-Element-189 $ 的真实标记为 $ MathJax-Element-190 $ ，则个体学习器 $ MathJax-Element-262 $ 和集成学习器 $ MathJax-Element-192 $ 的平方误差分别为：

   $ e_i(\mathbf {\vec x})=\left(\tilde y-h_i(\mathbf {\vec x})\right)^{2}\\ e_H(\mathbf {\vec x})=\left(\tilde y-H(\mathbf {\vec x})\right)^{2} $

   令个体学习器误差的加权均值为： $ MathJax-Element-193 $ 。根据 $ MathJax-Element-194 $ ，则有：

   $ \bar A(H \mid \mathbf{\vec x})=\sum_{i=1}^{M} w_ie_i(\mathbf {\vec x})-e_H(\mathbf {\vec x})=\bar e_h(\mathbf {\vec x})-e_H(\mathbf {\vec x}) $

3. 令 $ MathJax-Element-195 $ 为样本的概率密度。则在全样本上有：

   $ \int\bar A(H \mid \mathbf{\vec x})p(\mathbf {\vec x})d\mathbf {\vec x} =\int\bar e_h(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x}-\int e_H(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x} $

   代入各变量，则有：

   $ \int \sum_{i=1}^{M}w_iA(h_i \mid \mathbf{\vec x}) p(\mathbf {\vec x})d\mathbf {\vec x} =\int \sum_{i=1}^{M}w_ie_i(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x}-\int e_H(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x}\\ \rightarrow \sum_{i=1}^{M}w_i\int A(h_i \mid \mathbf{\vec x}) p(\mathbf {\vec x})d\mathbf {\vec x}=\sum_{i=1}^{M}w_i\int e_i(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x}-\int e_H(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x} $

4. 定义个体学习器 $ MathJax-Element-262 $ 在全体样本上的泛化误差和分歧项为：

   $ E_i= \int e_i(\mathbf {\vec x})\;p(\mathbf {\vec x})d\mathbf {\vec x}\\ A_i=\int A(h_i \mid \mathbf{\vec x}) \;p(\mathbf {\vec x})d\mathbf {\vec x} $

   定义集成的泛化误差为： $ MathJax-Element-197 $ 。则有： $ MathJax-Element-198 $ 。

5. 定义个体学习器泛化误差的加权均值为 $ MathJax-Element-199 $ 。定义个体学习器的加权分歧值为 $ MathJax-Element-200 $ 。则有： $ MathJax-Element-201 $ 。这就是集成学习的误差-分歧分解。

   • 该式针对回归学习，难以直接推广到分类学习任务中去。

   • 该式难以直接作为优化目标，因为现实任务中很难直接对 $ MathJax-Element-202 $ 进行优化：

     • 一方面是它们是定义在整体样本空间上的。
     • 另一方面是 $ MathJax-Element-205 $ 不是一个可以直接操作的值，它是当集成学习器构造之后才能进行估计的。

6. 从误差-分歧分解中看出：要想降低集成学习的泛化误差 $ MathJax-Element-204 $ ，要么提高个体学习器的加权分歧值 $ MathJax-Element-205 $ ，要么降低个体学习器的泛化误差的加权均值 $ MathJax-Element-206 $ 。

   因此：个体学习器准确性越高、多样性越大，则集成越好。

5.2 多样性度量

1. 多样性度量diversity measure是用于刻画集成模型中的个体分类器的多样性的程度。通常是考虑个体分类器的两两相似/不相似程度。

2. 给定数据集 $ MathJax-Element-207 $ 。考虑分类器 $ MathJax-Element-208 $ 的预测结果联表contingency table为：

   	$ MathJax-Element-209 $	$ MathJax-Element-210 $
   $ MathJax-Element-211 $	$ MathJax-Element-217 $	$ MathJax-Element-223 $
   $ MathJax-Element-214 $	$ MathJax-Element-220 $	$ MathJax-Element-226 $

   其中：

   • $ MathJax-Element-217 $ 表示： $ MathJax-Element-262 $ 预测为 +1，且 $ MathJax-Element-263 $ 预测为 +1 的样本的数量。
   • $ MathJax-Element-220 $ 表示： $ MathJax-Element-262 $ 预测为 +1，且 $ MathJax-Element-263 $ 预测为 -1 的样本的数量。
   • $ MathJax-Element-223 $ 表示： $ MathJax-Element-262 $ 预测为 -1，且 $ MathJax-Element-263 $ 预测为 +1 的样本的数量。
   • $ MathJax-Element-226 $ 表示： $ MathJax-Element-262 $ 预测为 -1，且 $ MathJax-Element-263 $ 预测为 -1 的样本的数量。

   根据定义有： $ MathJax-Element-229 $

5.2.1 不合度量

1. 不合度量disagreement measure ： $ MathJax-Element-230 $ 。

   其范围为 [0,1]，值越大则多样性越大 。

5.2.2 相关系数

1. 相关系数correlation coefficient： $ MathJax-Element-231 $ 。

   其范围是 [-1,+1]。

   • 如果 $ MathJax-Element-262 $ 与 $ MathJax-Element-263 $ 无关，则值为 0。
   • 如果 $ MathJax-Element-262 $ 与 $ MathJax-Element-263 $ 正相关，则值为正。
   • 如果 $ MathJax-Element-262 $ 与 $ MathJax-Element-263 $ 负相关，则值为 负。

5.2.3 Q 统计量

1. Q统计量Q-statistic： $ MathJax-Element-238 $ 。

   $ MathJax-Element-239 $ 与相关系数 $ MathJax-Element-240 $ 符号相同，且 $ MathJax-Element-241 $

5.2.4 kappa 统计量

1. $ MathJax-Element-261 $ 统计量 ( $ MathJax-Element-261 $ -statistic)： $ MathJax-Element-244 $ 。

   其中：

   • $ MathJax-Element-247 $ 是两个分类器取得一致的概率： $ MathJax-Element-246 $ 。

     根据：

     $ p(h_i=h_j)=p(h_i=1,h_j=1)+p(h_i=-1,h_j=-1)=\frac aN+\frac dN=p_1 $

     所以 $ MathJax-Element-247 $ 刻画了两个分类器取得一致的概率。

   • $ MathJax-Element-252 $ 是两个分类器偶然达成一致的概率： $ MathJax-Element-249 $ 。

     根据：

     $ p(h_i=1)=\frac{a+b}{N},\quad p(h_i=-1)=\frac{c+d}{N}\\ p(h_j=1)=\frac{a+c}{N},\quad p(h_j=-1)=\frac{b+d}{N} $

     如果假设 $ MathJax-Element-250 $ 与 $ MathJax-Element-251 $ 相互独立，则 ：

     $ \hat p(h_i=h_j)=\hat p(h_i=1,h_j=1)+\hat p(h_i=-1,h_j=-1)\\ =p(h_i=1)(h_j=1)+p(h_i=-1)P(h_j=-1)=p_2 $

     所以 $ MathJax-Element-252 $ 刻画了假设两个分类器的预测结果相互独立，则两个分类器取得一致的概率。

2. $ MathJax-Element-261 $ 的取值：

   • 若两个分类器在数据集 $ MathJax-Element-254 $ 上完全一致，则 $ MathJax-Element-255 $ 。

     因为此时 $ MathJax-Element-256 $ ，则 $ MathJax-Element-257 $ 。

   • 如果两个分类器仅仅是偶然达成一致，则 $ MathJax-Element-258 $ 。

     因为此时 $ MathJax-Element-259 $ ，则 $ MathJax-Element-260 $ 。

   • 通常 $ MathJax-Element-261 $ 取非负值，仅在 $ MathJax-Element-262 $ 与 $ MathJax-Element-263 $ 达成一致的概率甚至低于偶然性的情况下才取负值。

5.3 多样性增强

1. 集成学习中，需要有效地生成多样性较大的个体学习器。

   一般的思路是在学习过程中引入随机性。常见的做法是：对数据样本、输入属性、输出表示、算法参数进行扰动。

2. 数据样本扰动：给定初始数据集，可以从中产生出不同的数据子集。再利用不同的数据子集训练出不同的个体学习器。

   • 数据样本扰动通常是基于采样法，此类做法简单高效、使用最广。

   • 对于常见的基学习器，如决策树、神经网络等，训练样本稍加变化就会导致学习器有显著的变动，数据样本扰动法对这样的“不稳定基学习器”很有效。

   • 对于一些基学习器对数据样本的扰动不敏感，如线性学习器、支持向量机、朴素贝叶斯、 $ MathJax-Element-264 $ 近邻学习器等，这样的基学习器称作稳定基学习器。

     对于此类的基学习器进行集成往往需要使用输入属性扰动等其他机制。

3. 输入属性扰动：训练样本通常由一组属性描述，不同的“子空间”提供了观察数据的不同视角。显然从不同子空间训练出来的个体学习器必然有所不同。

   • 对于包含了大量冗余属性的数据，在子空间中训练个体学习器不仅能够产生多样性大的个体，还会因为属性数量的减少而大幅节省时间开销。

     同时由于冗余属性多，减少一些属性之后训练的个体学习器也不至于太差。

   • 对于只包含少量属性的数据，或者冗余属性较少，则不宜采用输入属性扰动法。

4. 输出表示扰动：此类做法的思路是对输出表示进行操纵以增强多样性。

   如：可以对训练样本的类标记稍作变动，如翻转法Flipping Output随机改变一些训练样本的标记。

5. 算法参数扰动：基学习算法一般都有超参数需要设置。可以通过随机设置不同的超参数，从而产生差别较大的个体学习器。

   使用单一学习器时通常需要使用交叉验证等方法来确定最佳的超参数值。这种做法实际上是用了不同的超参数训练出来了多个学习器，只不过最终挑选出来效果最好的那个学习器来使用。

   集成学习则是相当于把所有这些学习器都利用起来。

6. 不同的多样性增强机制可以同时使用。如随机森林同时是用了数据样本扰动和输入属性扰动。