AdaBoost 算法
【输入】
- 训练数据集
- 能够根据数据集权重进行学习的弱学习算法
- 终止条件：正确率限制
【输出】
- 最终分类器
【算法】
- 初始化数据集权重
- 循环
- 根据权重学习一个弱分类器
- 计算错误率
- 计算分类器
- 更新权值分布
- 构建基本分类器线性组合
- 根据权重学习一个弱分类器
- 输出，由每一步得到的弱分类器组合为最终的分类器：
【说明】
更新权值分布的公式可以写为：
也即误分类样本权值被放大
课本 P140 该公式有误。
收敛性证明
注意：
对于二分类问题：
也即如果弱学习算法总能保证一定的正确率，则训练集分类误差指数下降。
前向分步算法
考虑加法模型：
课本上 P144，从 8.16 可以反推 8.15 式有误
AdaBoost 可以视为损失函数为指数损失函数时的前向加法模型。此时：
注意
取定
这里 $\overline{w}{m,i} = \overline{w}{m-1,i} \exp[-\alpha_m y_i G_m(x_i)]$ 与 AdaBoost 算法中的定义只差一个归一化常数。
提升树算法
提升树算法被认为是最有效的机器学习算法之一。
提升树算法使用基函数为分类树的前向分布算法。应用于分类问题（使用指数损失函数）时类似于 AdaBoost 算法。应用于回归问题时，因为损失函数变得稍复杂。根据前向算法：
对于 MSE 或者其他范数损失函数：
对于一般的损失函数，启发式算法梯度提升算法将残差替换为了梯度：
当然，学习回归树的时候不能基于梯度值决定回归树的输出，而是只在回归树学习阶段决定树的形状时使用梯度值决定，决定叶节点
习题
1.
import numpy as np
def aw_entropy(x, weight):
"""
entropy (bit) for array with weight.
"""
entropy = 0
w_sum = np.sum(weight)
for value in np.unique(x):
frac = np.sum(weight[x == value]) / w_sum
entropy -= frac * np.log2(frac)
return entropy
def aw_cross_entropy(x, y, weight):
entropy = 0
w_sum = np.sum(weight)
for value in np.unique(y):
index = y == value
wi, xi = weight[index], x[y==value]
entropy += np.sum(wi) / w_sum * aw_entropy(xi, wi)
return entropy
def aw_relative_entropy(x, y, weight):
return aw_entropy(x, weight) - aw_cross_entropy(x, y, weight)
def aw_relative_entropy_regular(x, y, weight):
return aw_relative_entropy(x, y, weight) / aw_entropy(y, weight)
# test
# textbook, P59
test_x = np.asarray([
[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2],
[0,0,1,1,0,0,0,1,0,0,0,0,1,1,0],
[0,0,0,1,0,0,0,1,1,1,1,1,0,0,0],
[0,1,1,0,0,0,1,1,2,2,2,1,1,2,0],
])
test_y = np.asarray(
[0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]
)
test_y[test_y==0] = -1
test_w = np.ones_like(test_y, dtype=float)
test_w /= np.sum(test_w)
ans1 = aw_entropy(test_y, test_w)
ans2 = [aw_relative_entropy(text_x[i, :], test_y, test_w) for i in range(3)]
assert np.allclose(ans1, 0.97095059)
assert np.allclose(ans2, [0.08300749, 0.32365019, 0.41997309])
def decision_stump(x, y, weight, mark=aw_relative_entropy):
"""
ID3 algorithm for decision tree.
just run one time and get a decision stump.
return: classification result for train data x.
"""
mark_list = [mark(x[i, :], y, weight) for i in range(x.shape[0])]
best_mark_index = np.argmax(mark_list)
res_dict = {}
for xv in np.unique(x[best_mark_index, :]):
index = x[best_mark_index, :] == xv
yv, wv = y[index], weight[index]
wcount = {}
for yi, wi in zip(yv, wv):
if yi in wcount: wcount[yi] += wi
else: wcount[yi] = wi
kv = sorted(list(wcount.items()), key=lambda e: e[1])
most_case = kv[-1][0]
res_dict[xv] = most_case
def _stump(x):
return res_dict[x[best_mark_index]]
def _stump_array(x_array):
return np.apply_along_axis(_stump, 0, x_array)
return _stump_array
# test
print(decision_stump(test_x, test_y, test_w)(test_x))
# output:
# [-1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1]
def adaboost(x, y, weak_algo=decision_stump, max_err=0.01, max_classifier_num=20):
classifier_list, alpha_list, y_pred_list = [], [], []
weight = np.ones_like(y) / y.size
def _tolabel(y_float):
y_float[y_float < 0] = -1
y_float[y_float >= 0] = 1
return y_float.astype(int)
for i in range(max_classifier_num):
classifier = weak_algo(x, y, weight)
y_pred = classifier(x)
err_rate = np.sum((y_pred != y) * weight)
alpha = 0.5 * np.log( (1-err_rate) / err_rate)
weight *= np.exp(-alpha*y*y_pred)
weight /= np.sum(weight)
classifier_list.append(classifier)
alpha_list.append(alpha)
y_pred_list.append(y_pred)
y_pred_f = np.asarray(y_pred_list).T.dot(np.asarray(alpha_list))
y_pred_f = _tolabel(y_pred_f)
err_f = np.sum(y_pred_f != y) / y.size
if err_f < max_err:
break
def _cla(x):
y_pred = np.zeros(x.shape[1])
for c, a in zip(classifier_list, alpha_list):
y_pred += a * c(x)
return _tolabel(y_pred)
return _cla
# test
print(test_y)
print(adaboost(test_x, test_y)(test_x))
# output:
# [-1 -1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1]
# [-1 -1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1]
x = np.asarray([
[0,0,1,1,1,0,1,1,1,0],
[1,3,2,1,2,1,1,1,3,2],
[3,1,2,3,3,2,2,1,1,1]
])
y = np.asarray([
-1,-1,-1,-1,-1,-1,1,1,-1,-1
])
print(adaboost(x, y)(x))
print(y)
# output:
# [-1 -1 -1 -1 -1 -1 1 1 -1 -1]
# [-1 -1 -1 -1 -1 -1 1 1 -1 -1]