精读西瓜书(第八章-集成学习)-个体与集成

写在前面

  • 昨天, 我们结束了对贝叶斯分类器章节的学习; 今天, 我们将继续学习集成学习中的个体与集成.

个体与集成

  • 集成学习(Ensemble Learning)通过构建并结合多个学习器来完成学习任务, 有时也会被称为多分类器系统(Multi-Classifier System), 基于委员会的学习(Committee-Based Learning)等.
  • 如下图, 显示出集成学习的一般结构: 先产生一组’个体学习器’(Individual Learner), 再用策略将它们结合起来. 个体学习器通常由一个现有的学习算法从训练数据产生, 例如C4.5决策树算法, BP神经网络算法等, 此时集成中值包含同种类型的个体学习器, 例如’决策树集成’中全是决策树, ‘神经网络集成’中全是神经网络, 这样的集成是’同质’的(Homogeneous). 同质集成中的个体学习器亦称’基学习器’(Base Learner), 相应的学习算法称为’基学习算法’(Base Learning Algorithm). 集成也可包含不同类型的个体学习器, 例如同事包含决策树和神经网络, 这样的集成是’异质’的(Heterogenous). 异质集成中的个体学习器由不同的学习算法生成, 这是就不在有基学习算法; 相应地, 个体学习器一般不称为基学习器, 常称为’组件学习器’(Component Learner)或直接称为个体学习器.

  • 集成学习通过将多个学习器进行结合, 长可获得比单一学习器显著优越的泛化性能. 这对’弱学习器’(Weak Learner)尤为明显, 因此集成学习的很多理论研究都是针对若学习器进行的, 而基学习器有时也被直接成为弱学习器. 但需注意的是, 虽然从理论上来说使用弱学习器集成足以获得好的性能, 但在实践中出于种种考虑, 例如希望使用较少的个体学习器, 或是重用关于常见学习器的一些经验等, 人们往往会使用比较强的学习器. 在一般经验中, 如果把好坏不等的东西掺到一起, 那么通常结果会是比最坏的要好一些, 比最好的要坏一些. 集成学习把多个学习器结合起来, 如何能获得比最好的单一学习器更好的性能呢?
  • 考虑一个简单的例子: 在二分类任务中, 假定三个分类器在三个测试样本上的表现如下图, 其中 \(\surd\) 表示分类正确, \(\times\) 表示分类错误, 集成学习的结果通过投票法(Voting)产生, 即’少数服从多数’. a图中每个分类器都只有 \(66.6%\) 的精度, 但集成学习却高达了 \(100%\) ; 在b图中, 三个分类器没有差别, 集成之后性能没有提高; 在c图中, 每个分类器的精度都只有 \(33.3\) , 集成学习的结果变得更糟. 这个简单的例子显示出: 要获得好的集成, 个体学习器应’好而不同’, 即个体学习器要有一定的’准确性’, 即学习器不能太坏, 并且要有’多样性’(Diversity), 即学习器间具有差异.

  • 我们来做个简单的分析. 考虑二分类问题 \(y \in \lbrace -1, +1 \rbrace\) 和真实函数 \(f\) , 假定基分类器的错误率为 \(\epsilon\) , 即对每个基分类器 \(h_{i}\) 有:

  • 假设集成通过简单投票法结合 \(T\) 个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确:

  • 假设基分类器的错误率相互独立, 则由Hoeffding不等式可知, 集成的错误率为:

  • 上式显示出, 随着集成中个体分类器数目 \(T\) 的增大, 集成的错误率将指数级下降, 最终趋向于零. 然而我们必须注意到, 上面的分析有一个关键假设: 及学习期的误差相互独立. 在现实任务中, 个体学习器是为解决同一个问题训练出来的, 他们显然不可能互相独立! 事实上, 个体学习器的’准确性’和’多样性’本身就存在冲突. 一般的, 准确性很高之后, 要增加多样性就需要牺牲准确性. 事实上, 如何产生并结合’好而不同’的个体学习器, 恰是集成学习研究的核心. 更具个体学习器的生成方式, 目前的集成学习方法大致可分为两大类, 即个体学习器间存在强依赖关系, 必须串行生成的序列化方法, 以及个体学习器间不存在强依赖关系, 可同时生成的并行化方法; 前者代表是Boosting, 后者的代表是Bagging和’随机森林’(Random Forest).

写在后面

  • 今天, 我们学习了集成学习中的个体与集成; 明天, 我们将继续学习集成学习中的Boosting.