机器学习中最最好用的提升方法:Boosting 与 AdaBoost

在 Kaggle 及其它机器学习任务中,集成方法非常流行,不论是 XGBoost 还是随机森林,它们都强大无比。而本文作者从最基础的 Boosting 概念到 AdaBoost 算法进行了详细的介绍,并展示了如何实现 AdaBoost,这些都是走进集成方法大家族的敲门砖。

最近,Boosting 技术在 Kaggle 竞赛以及其它预测分析任务中大行其道。本文将尽可能详细地介绍有关 Boosting 和 AdaBoost 的相关概念。

本文将涉及:

  • 对 bagging(装袋法)的快速回顾

  • bagging 的局限性

  • Boosting 的概念细节

  • boosting 的计算效率

  • 代码示例

Bagging 的局限性

接下来,我们不妨考虑一个二元分类问题。我们把一个观测结果分类为 0 或 1。尽管这并不是本文的目的,但是为了清晰起见,让我们回顾一下 Bagging 的概念。

Bagging 指的是一种叫做「Bootstrap Aggregating」(自助聚合)的技术。其实质是选取 T 个 bootstrap 样本,在每个样本安装一个分类器,然后并行训练模型。通常,在随机森林中,决策树是并行训练的。然后,将所有分类器的结果平均化,得到一个 bagging 分类器:


Bagging 分类器的公式

该过程可以通过以下方式来说明。让我们考虑 3 个分类器,它们生成一个分类结果,该结果可能是对的也可能是错的。如果我们绘制 3 个分类器的结果,会有一些区域代表分类器的结果是错误的。在下图中,这样的区域用红色表示:

Bagging 适用场景的示例

这个示例可以很好地起到说明作用,其中有一个分类器的结果是错误的,而另外两个分类器的结果是正确的。通过对分类器进行投票,你可以获得很高的分类准确率。但正如你可能会猜到的那样,bagging 机制有时并不能很好地起作用,这时所有的分类器都会在同一个区域内获得错误的分类结果。

出于这个原因,对 boosting 方法背后的直观想法是:

  • 我们需要串行训练模型,而不是并行训练。

  • 每个模型需要重点关注之前的分类器表现不佳的地方。

Boosting 简介

概念

上述想法可以诠释为:

  • 在整个数据集上训练模型 h1

  • 对 h1 表现较差的区域的数据加权,并在这些数据上训练模型 h2

  • 对 h1 ≠ h2 的区域的数据加权重,并在这些数据上训练模型 h3

  • ...

我们可以串行地训练这些模型,而不是并行训练。这是 Boosting 的本质!

Boosting 方法会随着时间的推移,通过调整误差度量来训练一系列低性能算法,称之为弱学习器。弱学习器指的是那些误差率略低于 50% 的算法,如下图所示:

误差率略低于 50% 的弱分类器

加权误差

我们如何才能实现这样的分类器呢?实际上,我们是通过在整个迭代过程中加权误差做到的。这样,我们将为之前分类器表现较差的区域赋予更大的权重。

不妨想想二维图像上的数据点。有些点会被很好地分类,有些则不会。通常,在计算误差率时,每个误差的权重为 1/n,其中 n 是待分类的数据点个数。

未加权的误差

现在让我们对误差进行加权!

加权后的误差

现在,你可能注意到了,我们对没有被很好地分类的数据点赋予了更高的权重。加权的过程如下图所示:

加权过程示例

最终,我们希望构建如下图所示的强分类器:

强分类器

决策树桩

你可能会问,我们需要实现多少个分类器才能让整个 Boosting 系统很好地工作呢?在每一步中如何选择分类器?

答案是所谓的「决策树桩」!决策树桩是指一个单层决策树。主要思想是,我们在每一步都要找到最好的树桩(即得到最佳的数据划分),它能够使整体的误差最小化。你可以将一个树桩看做一个测试,其中,我们假设位于树桩某一侧的所有数据点都属于 1 类,另一侧的所有数据点都属于 0 类。

决策树桩的组合可能有很多种。接下来,让我们看看在这个简单的示例中有多少种树桩组合?

待划分的 3 个数据点

实际上,本例中有 12 种树桩组合!这看起来可能有些令人惊讶,但其实很容易理解。

12 个决策树桩

我们可以对上面的情况做 12 种可能的「测试」。每条分割线边上的数字「2」简单地表示了这样一个事实:位于分割线某一侧的所有点都可能属于 0 类或 1 类。因此,每条分割线嵌入了 2 个「测试」。

在每一轮迭代 t 中,我们将选择能够最好地划分数据的弱分类器 ht,该分类器能够最大限度地降低整体误差率。回想一下,这里的误差率是一个经过加权修正之后的误差率版本,它考虑到了前面介绍的内容。

寻找最佳划分

如上所述,通过在每轮迭代 t 中识别最佳弱分类器 ht(通常为具有 1 个节点和 2 片叶子的决策树(决策树桩))来找到最佳划分。假设我们试图预测一个想借钱的人是否会是一个好的还款人:

找出最佳划分

在这种情况下,t 时刻的最佳划分是将「支付历史」作为树桩,因为这种划分的加权误差是最小的。

只需注意,实际上,像这样的决策树分类器可能具备比简单的树桩更深的结构。这将会是一个超参数。

融合分类器

自然而然地,下一步就应该是将这些分类器融合成一个符号分类器。根据某个数据点处于分割线的哪一侧,将其分类为 0 或 1。该过程可以通过如下方式实现:

融合分类器

你发现了可能提升分类器性能的方法吗?

通过为每个分类器加权,可以避免赋予不同的分类器相同的重要性。

AdaBoost

小结一下

让我们把到目前为止本文已经介绍过的内容总结在一段小小的伪代码中。

伪代码

其中需要记住的关键点是:

  • Z 是一个常数,其作用是对权重进行归一化,使得它们加起来等于 1!

  • α_t 是应用于每个分类器的权重 

大功告成!这种算法就是「AdaBoost」。如果你想充分理解所有的 boosting 方法,那么这是你需要理解的最重要的算法。

计算

Boosting 算法训练起来非常快,这太棒了。但是我们考虑到了所有树桩的可能性并且采用了递归的方法计算指数,为什么它还会训练地这么快?

现在,神奇的地方来了!如果我们选择了恰当的 α_t 和 Z,本该在每一步变化的权重将简化成如下的简单形式:

选择了恰当的 α 和 Z 之后得到的权重

这是一个非常强的结论,这与权重应该随着迭代而变化的说法并不矛盾。因为错误分类的训练样本数量减少了,它们的总权重仍然是 0.5!

  • 无需计算 Z

  • 无需计算 α

  • 无需计算指数

另外一个小诀窍是:任何试图将两个已经被很好地分类的数据点划分开的分类器都不会是最优的。我们甚至不需要对其进行计算。

动手编程试一下吧!

现在,本文将带领读者快速浏览一个代码示例,看看如何在 Python 环境下使用 Adaboost 进行手写数字识别。

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

from sklearn.metrics import accuracy_score
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import cross_val_predict
from sklearn.model_selection import train_test_split
from sklearn.model_selection import learning_curve

from sklearn.datasets import load_digits

首先,载入数据:

dataset = load_digits()
X = dataset['data']
y = dataset['target']

X 包含长度为 64 的数组,它们代表了简单的 8x8 的平面图像。使用该数据集的目的是为了完成手写数字识别任务。下图为一个给定的手写数字的示例

如果我们坚持使用深度为 1 的决策树分类器(决策树桩),以下是如何在这种情况下实现 AdaBoost 分类器:

reg_ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1))
scores_ada = cross_val_score(reg_ada, X, y, cv=6)
scores_ada.mean()

这样得到的分类准确率的结果应该约为 26%,还具有很大的提升空间。其中一个关键的参数是序列决策树分类器的深度。那么,决策树的深度如何变化才能提高分类准确率呢?

score = []
for depth in [1,2,10] : 
    reg_ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=depth))
    scores_ada = cross_val_score(reg_ada, X, y, cv=6)
    score.append(scores_ada.mean())

在这个简单的例子中,当决策树的深度为 10 时,分类器得到了最高的分类准确率 95.8%。

结语

研究人员已经针对 AdaBoost 是否会过拟合进行了深入的探讨。近来,AdaBoost 被证明在某些时候会发生过拟合现象,用户应该意识到这一点。同时,Adaboost 也可以作为回归算法使用。

在人脸识别任务中,AdaBoost 被广泛用于评估视频中是否存在人脸。本文作者将就此话题在近期内撰写另外一篇文章!在后续文章中,还将介绍梯度增强方法!

原文链接:https://towardsdatascience.com/boosting-and-adaboost-clearly-explained-856e21152d3e

入门梯度人脸识别AdaBoost
92
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

迭代 技术

模型的权重在训练期间的一次更新。迭代包含计算参数在单个批量数据上的梯度损失。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

人脸识别技术

广义的人脸识别实际包括构建人脸识别系统的一系列相关技术,包括人脸图像采集、人脸定位、人脸识别预处理、身份确认以及身份查找等;而狭义的人脸识别特指通过人脸进行身份确认或者身份查找的技术或系统。 人脸识别是一项热门的计算机技术研究领域,它属于生物特征识别技术,是对生物体(一般特指人)本身的生物特征来区分生物体个体。

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

伪代码技术

伪代码,又称为虚拟代码,是高层次描述算法的一种方法。它不是一种现实存在的编程语言;它可能综合使用多种编程语言的语法、保留字,甚至会用到自然语言。 它以编程语言的书写形式指明算法的职能。相比于程序语言它更类似自然语言。它是半形式化、不标准的语言。

随机森林技术

在机器学习中,随机森林是一个包含多个决策树的分类器,并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。而"Random Forests"是他们的商标。这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林(random decision forests)而来的。这个方法则是结合Breimans的"Bootstrap aggregating"想法和Ho的"random subspace method" 以建造决策树的集合。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

分类问题技术

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

过拟合技术

过拟合是指为了得到一致假设而使假设变得过度严格。避免过拟合是分类器设计中的一个核心任务。通常采用增大数据量和测试样本集的方法对分类器性能进行评价。

推荐文章
海信集团有限公司・算法工程师
小编,最近文章的图都看不到
机器之心・产品经理
收到~我们尽快修复!