提升方法

发表于 | 更新于: | 分类于 | | 阅读量: 次

提升(boosting)方法是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。

本章的内容如下几点：

  1. 首先介绍提升方法的思路和具有代表性的提升算法AdaBoost。
  2. 然后通过训练误差分析探讨AdaBoost为什么能够提供学习精度；从前向分步加法模型的角度解释AdaBoost；
  3. 最后叙述提升方法更具体的实例——提升树(boosting tree)。

10.1 提升方法AdaBoost算法

10.1.1 提升方法的基本思路

提升方法基于这样一种思想:对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。

强可学习(strongly learnable)和弱可学习(weakly learnable)：在概率近似正确(probably approximately correct，PAC)学习的框架中，一个概念(一个类)，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称为这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称为这个概念是弱可学习的。在PAC学习的框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

所以，现在的问题变成了:如果已经发现了“弱学习算法”，那么如何将它提升为“强学习算法”。

大多数的提升方法都是改变训练数据的概率分布(训练数据的权值分布)，针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

对提升方法来说，有两个问题需要回答:

  1. 在每一轮如何改变训练数据的权值或概率分布。
  2. 如何将弱分类器组合成一个强分类器。

对于以上两个问题，AdaBoost算法的解决方案如下:

  1. 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。(目的:那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，相当于分类问题被一些列的弱分类器”分而治之”。)
  2. 采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

10.1.2 AdaBoost算法

假设给定一个二类分类的训练数据集，其中，每个样本点由实例与标记组成。实例，标记，是实例空间，是标记集合。

AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。

算法10.1(AdaBoost)

输入：训练数据集，其中，；弱学习算法；

输出：最终分类器

(1)初始化训练数据的权值分布

(2)对m=1,2,…,M(表示有 M个弱分类器)

​ (a)使用具有权值分布的训练数据集学习，得到基本分类器:

​ (b)计算在训练数据集上的分类误差率

​ (c)计算的系数

​ 这里的对数是自然对数。

​ (d)更新训练数据集的权值分布

​ 这里，是规范化因子

(3)构建基本分类器的线性组合

得到最终分类器

对AdaBoost算法作如下说明:

步骤(1) 假设训练数据集具有均匀的权值分布(即每个训练样本在基本分类器的学习中作用相同)；在此权值分布下，基于原始数据训练出基本分类器

步骤(2)AdaBoost反复学习基本分类器，在每一轮m=1,2,…,M顺次的执行下列操作:

​ (a)使用当前分布加权的训练数据集，学习基本分类器。

​ (b)计算基本分类器在加权训练数据集上的分类误差率:

​ 这里，表示第m轮第i个样本点的权值，。这表明，在加权的训练数据集上的分类误差率是被误分类的样本的权值之和。

​ (c)计算基本分类器的系数，表示在最终分类器中的重要性。由式(10.2)可知，当时，，并且随着的减小而增大。相当于误分类率越小的基本分类器在最终分类器中的重要性越大。

​ (d)更新训练数据的权值分布。式(10.4)可以写成:

​ 由此可知，被基本分类器误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。

​ 由式(10.2)可知误分类样本的权值被放大倍。

步骤(3) 线性组合实现M个基本分类器的加权表决。系数表示了基本分类器重要性，这里，所有之和并不为1。的符号决定实例x的类，的绝对值表示分类的确信度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#分类提升树(基本分类器为单节点决策树) 算法的实现
class AdaBoost(object):
    def __init__(self, n_estimators=50, learning_rate=1.0):
        self.clf_num = n_estimators
        self.learning_rate = learning_rate
        
    def init_args(self, datasets, labels):
        self.X = datasets
        self.Y = labels
        
        self.M, self.N = datasets.shape
        
        #弱分类器数目和集合
        self.clf_sets = []
        
        #初始化weights(对应adaboost算法中的D向量)
        self.weights = [1.0/self.M]*self.M #D1
        
        #G(x)系数alpha
        self.alpha = []
        
    def _G(self, features, labels, weights):
        '''
        找到使得误分类率最小的阈值v；
        因为对于基本分类器G(x)为：根据x与阈值v的大小关系来判断样本标签
        所有阈值的选择非常重要
        '''
        m = len(features)
        error = 1e5 #表示无穷大
        best_v = 0.0 #阈值
        
        #单维features
        features_min = min(features)
        features_max = max(features)
        #寻找阈值的迭代次数
        n_step = (features_max-features_min+self.learning_rate)//self.learning_rate
        
        direct, compare_array = None,None
        for i in range(1,int(n_step)):
            v = features_min+self.learning_rate*i
            
            #误分类计算
            compare_array_positive = np.array([1 if features[k]>v else -1 for k in range(m)])
            weight_error_positive = sum([weights[k] for k in range(m) if compare_array_positive[k]!=labels[k]])
                
            compare_array_nagetive = np.array([-1 if features[k]>v else 1 for k in range(m)])
            weight_error_nagetive = sum([weights[k] for k in range(m) if compare_array_nagetive[k]!=labels[k]])
                
            if weight_error_positive<weight_error_nagetive:
                weight_error = weight_error_positive
                _compare_array = compare_array_positive
                direct = 'positive'
            else:
                weight_error = weight_error_nagetive
                _compare_array = compare_array_nagetive
                direct = 'nagetive'
                    
            if weight_error<error:
                error = weight_error
                compare_array = _compare_array
                best_v = v
        
        return best_v,direct,error,compare_array
    
    def _alpha(self, error):
        '''
        计算alpha，式(10.2)
        '''
        return 0.5*np.log((1-error)/error)
    
    def _Z(self, weights, a, clf):
        '''
        规范化因子：式(10.5)
        '''
        return sum([weights[i]*np.exp(-1*a*self.Y[i]*clf[i]) for i in range(self.M)])
    
    def _w(self, a, clf, Z):
        '''
        样本权值更新：式(10.4)
        '''
        for i in range(self.M):
            self.weights[i] = self.weights[i]*np.exp(-1*a*self.Y[i]*clf[i])/Z
            
    
    def G(self, x, v, direct):
        '''
        基本分类器G(x)
        '''
        if direct == 'positive':
            return 1 if x>v else -1
        else:
            return -1 if x>v else 1
        
    def fit(self,X,y):
        self.init_args(X,y)
        
        for epoch in range(self.clf_num):
            #逐个生成clf_num个基本分类器
            axis,final_direct,best_clf_error, best_v, clf_result =-1,'positive', 1e5,None,None
            
            #根据特征维度，选择误差最小的
            for j in range(self.N):
                features = self.X[:,j]
                #分类阈值，分类误差，分类结果
                v,direct,error,compare_array = self._G(features, self.Y, self.weights)
                
                if error<best_clf_error:
                    best_clf_error = error
                    best_v = v
                    final_direct = direct
                    clf_result = compare_array
                    axis=j
                    
                if best_clf_error==0:
                    break
                    
            #计算G(x)系数
            a = self._alpha(best_clf_error)
            self.alpha.append(a)
            self.clf_sets.append((axis,best_v,final_direct))
            #归一化因子
            Z = self._Z(self.weights,a,clf_result)
            #权值更新
            self._w(a, clf_result, Z)
            
    def predict(self, X):
        '''
        分类器；式(10.6)
        '''
        labels = []
        for item in X:
            result = 0.0
            for i in range(len(self.clf_sets)):
                axis, clf_v, direct = self.clf_sets[i]
                f_input = item[axis]
                result += self.alpha[i]*self.G(f_input, clf_v, direct)
            
            result = 1 if np.sign(result)>0. else -1
            labels.append(result)
            
        return np.array(labels)
    
    def score(self, X_test, y_test):
        labels = self.predict(X_test)
        right_count = sum(labels!=y_test)
        return right_count/float(len(y_test))

10.2 AdaBoost算法的训练误差分析

AdaBoost最基本的性质是它能在学习过程中不断减少训练误差，即在训练数据集上的分类误差率。

定理10.1(AdaBoost的训练误差界) AdaBoost算法最终分类器的训练误差为：

这里，和分别由式(10.7)、式(10.6)和式(10.5)给出。

证明 当时，，因而。由此直接推导出前半部分。

后半部分的推导要用到的定义式(10.5)及式(10.4)的变形:

现推导如下:

此定理说明：可以在每一轮选取适当的使得最小，从而使训练误差下降最快。

定理10.2(二类分类问题AdaBoost的训练误差界)

这里，。

证明：由的定义式(10.5)及式(10.8)得

至于不等式

则可先由和在点x=0的泰勒展开式推出不等式，进而得到。

推论10.1 如果存在，对所有m有，则

这表明在此条件下AdaBoost的训练误差是以指数速率下降的。

10.3 AdaBoost算法的解释

AdaBoost算法还可以理解为:模型为加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。

10.3.1前向分步算法

考虑加法模型:

其中，为基函数，为基函数的参数，为基函数的系数。由此可见，式(10.6)是加法模型。

在给定训练数据及损失函数的条件下，学习加法模型称为经验风险极小化即损失函数极小化问题:

前向分步算法的求解思路是：因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式(10.14)，那么就可以简化优化的复杂度。具体地，每步只需优化如下损失函数:

给定训练数据集，，。损失函数和基函数的集合，学习加法模型的前向分步算法如下:

算法10.2(前向分步算法)

输入:训练数据集；损失函数；基函数集；

输出:加法模型。

(1)初始化

(2)对m=1,2,…,M

​ (a)极小化损失函数

​ 得到参数，。

​ (b)更新

(3)得到加法模型

这样，前向分步算法将同时求解从m=1到M所有参数，的优化问题简化为逐次求解各个，的优化问题。

10.3.2 前向分步算法与AdaBoost

定理10.3 AdaBoost算法是前向分步加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

证明：前向分步算法学习的是加法模型，当基函数为基本分类器时，该加法模型等价于AdaBoost的最终分类器：

由基本分类器及其系数组成，m=1,2,…,M。前向分步算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基本分类器的过程一致。

接下来证明前向分步算法的损失函数是指数损失函数：

时，其学习的具体操作等价于AdaBoost算法学习的具体操作。

假设经过m-1轮迭代前向分步算法已经得到:

在第m轮迭代得到，和。

目标是使前向分步算法得到的和使在训练数据集T上的指数损失最小，即

式(10.20)可以表示为:

其中，。因为既不依赖也不依赖于G，所以与最小化无关。但依赖于，随着每一轮迭代而发生改变。

证明式(10.21)的解和就是AdaBoost算法所得到的和。

求解式(10.21):

  1. 求。对任意，使式(10.21)最小的由下式得到：

    其中，。

    此分类器即为AdaBoost算法的基本分类器，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。

  2. 求。参照式(10.11)，式(10.21)中

将已求得的代入式(10.22)，可得：

对求导并使导数为0，即得到使式(10.21)最小的。

其中，是分类误差率:

这里的与AdaBoost算法第2(c)步的完全一致。

最后来看每一轮样本权值的更新。由

以及，可得

这与AdaBoost算法第2(d)步的样本权值的更新，只相差规范化因子，因而等价。

参考资料