集成学习总结：Boosting

Posted on |

最近了解了集成学习中的Boosting，以及衍生算法AdaBoost。在此对他们进行总结。

集成学习

首先，什么是集成学习（ensemble learning）？通过构建并结合多个学习器来完成学习任务的方法，通常被称为集成学习。这样的学习器，可以是同种学习器（同质），其亦可被称为基学习器。学习器也可以是不同的（异质），例如C4.5决策树，BP神经网络。此时基学习器不再存在，我们称每个学习器为个体学习器。

集成学习有个特点：结合多个学习器的效果，往往会比单个弱学习器的效果好的多。然而，从生活经验出发，当我们把一些效果很差的东西（例如，运行速度很慢的代码）结合在一起的时候，效果往往会更差。那集成学习是如何达到这种更好的效果的呢？下面参照西瓜书给出证明。

现在有一个二分类问题 $y\in\{+1,-1\}$，真实函数为 $f$。有$T$个分类器，且基分类器的误差为 $\epsilon$。我们使用投票法来决定最后的输出，也就是说如果有超过半数基分类器输出为-1，那最后结果$H(x)$就为-1。那么，我们就可以得到学习的误差为

那么，假设分类器的预测相互独立，根据Hoeffding不等式，我们有

其中，$G(x)$是指预测结果为真的分类器的个数。

Hoeffding不等式：假某抛硬币朝上的概率为$p$，且相互独立，若连续抛 $n$次且最多朝上$k$次，即$P(G(n)\leq k)$。存在 $c>0, k=(p-c)n$，使得$P(G(n)\leq (p-c)n) \leq exp(-2c^2 n)$

由此我们可见，随着$T$增大，误差会呈指数级下降。这也就解释了为什么学习器越多，整体的学习效果会越好。

然而，学习器的预测实际上不满足Hoeffding不等式相互独立的条件。为了尽量满足相互独立的条件，我们需要使学习器尽可能多样。但这种多样性则往往会带来准确性的下降。于是，如何产生“好而不同”的学习器，就成为了集成学习的核心问题。

Boosting

Boosting就是集成学习的一种，它采用强依赖的学习器，而且通过序列化生成结果。也就是说，Boosting并不具有丰富的多样性，它通过提高学习器的预测准确性，来提高集成学习的效果。

具体来说，Boosting增大对预测错误的数据的关注，赋予他们更大的权重，然后通过更新的数据，序列化生成新学习器，在达到设定值后，对所有学习器做加权结合。

AdaBoost(adaptive boosting)是Boosting族中具有代表性的算法，接下来我们具体研究下。

AdaBoost

简单来说，AdaBoost做了两件事情: 一是像我们上面说的，在增大对预测错误的数据的关注；二是增大预测效果好的学习器的权重。具体算法流程如下下图所示：
其中$D_t(x)$是在第$t$轮数据集的权值分布，$h_t$就是在第$t$轮中最优学习器预测的结果。

在第6步中，我们首先根据误差得到一个正参数$\alpha_t$。在第7步中，数据集中预测正确的数据都要和$-\alpha_t$的指数相乘，而预测正确的数据则和$\alpha_t$的指数相乘，这样预测错误的数据就得到了更大的权值，最后每个权值除以权值之和$Z_t$，就得到了下一轮的权值分布。在迭代结束，或者误差率超过阈值的时候，开始最后的输出。我们观察到，$h_t$的预测误差越低，$\alpha_t$越大，它在最后输出中占的比重就越大，这就实现了上面所说的增大预测效果好的学习器的权重。我们把这种得到$H(x)$的方法叫做线性加法模型。

OK，这样设置是很有道理，但设计者是咋想出来这种方法的呢？实际上，$\alpha_t$和权值分布$D_t$的更新都可以通过推导得到，由于过程过于繁琐，请参考西瓜书具体章节。

Example

好啦，下面我们来看个具体的例子。
假设我们有一个这样的数据集

x 0 1 2 3 4 5
y 1 1 -1 -1 1 -1

我们使用二分类决策树作为基分类器，验算第一轮过程：
1.首先初始化$D_1=(0.167, 0.167, 0.167, 0.167, 0.167, 0.167)$
2.获得最优$h_1$与误差
若按0.5切分数据，得弱分类器x < 0.5,则 y = 1; x > 0.5, 则 y = -1。此时误差为2 * 0.167 = 0.334

若按1.5切分数据，得弱分类器x < 1.5,则 y = 1; x > 1.5, 则 y = -1。此时误差为1 * 0.167 = 0.167

若按2.5切分数据，得弱分类器x < 2.5,则 y = 1; x > 2.5, 则 y = -1。此时误差为2 * 0.167 = 0.334

若按3.5切分数据，得弱分类器x < 3.5,则 y = 1; x > 3.5, 则 y = -1。此时误差为3 * 0.167 = 0.501

若按4.5切分数据，得弱分类器x < 4.5,则 y = 1; x > 4.5, 则 y = -1。此时误差为2 * 0.167 = 0.334

则最优弱分类器为x < 1.5,则 y = 1; x > 1.5, 则 y = -1。

3.计算得$\alpha_1=0.5 * ln((1 – 0.167) / 0.167) = 0.8047$
4.随后根据$\alpha_1$和预测结果，即可进行权重的更新。

Coding

那代码改怎么写呢？
我们首先把函数设计成这样:

1
2
3
4
5
if __name__ == '__main__':
    x = [0, 1, 2, 3, 4, 5]
    y = [1, 1, -1, -1, 1, -1]
    fx = trainAdaBoost(x, y, T) #训练得到的学习器
    print(fx)

然后我们按照算法流程顺序，首先计算可能的划分点:

1
2
3
4
5
def separatePoint(x):
	sp = []
	for i in range(len(x)-1):
		sp.append((x[i]+x[i+1])/2)
	return sp

然后，我们找出最优的划分点:

1
2
3
4
5
6
7
8
9
10
11
12
def findBestSp(sp,x,y,D_t):
	error=1;
	bestsp=-1;
	for i in range(sp):
		error_i=0;
		for j in range(x):
			if x[j] < sp[i] and y[j] != 1: error_i += D_t[j]
			if x[j] > sp[i] and y[j] != -1: error_i += D_t[j]
		if error_i < error: 
			error = error_i
			bestsp = i
	return bestsp, error

开始计算alpha，并更新权值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def alphaAndWeight(x,y,D_t):
	sp = separatePoint(x)
	bestsp, error = findBestSp(sp,x,y,D_t)
	if error > 0.5
		return -1,-1,-1
	alpha = (1/2)*log((1-error)/error)
	D_tn = D_t
	Z=0
	for i in range(x):
		if x[i] < sp[bestsp] and y[i]!=1: D_tn[i]=D_tn[i]*exp(alpha)
		elif x[i] > sp[bestsp] and y[i]!=-1: D_tn[i]=D_tn[i]*exp(alpha)
		else: D_tn[i]=D_tn[i]*exp(-alpha)
		Z+=D_tn[i]
	D_tn/=Z
	return sp, alpha, D_tn

训练函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def trainAdaBoost(x, y, T):
	D_1 = [1 for i in range(x)]
	D_1 /= len(x)
	Alpha = []
	D = [D_1]
	SP = []
	D_tn = D_1
	for i in xrange(1:T):
		sp, alpha, D_tn = alphaAndWeight(x,y,D_tn)
		if sp==-1 and alpha==-1 and D_tn==-1: break
		SP.append(sp)
		D.append(D_tn)
		Alpha.append(alpha)
	#接下来计算结果
	test=[]
	for i in range(x):
		test_y=0
		for j in range(SP):
			if x[i] < SP[j]: test_y += D_tn[j][i]
			else: test_y -= D_tn[j][i]
		if test_y>0: test.append(1)
		else: test.append(0) 
	return test

最后运行，就可以把最后的test输出打印出来啦

参考资源

[1]机器学习西瓜书，周志华
[2]机器学习 第十二章 集成学习（1） 提升学习
[3]手把手教你实现一个 AdaBoost