【机器学习算法】Adaboost原理及实现

Adaboost

一、基本内容

[!note]

实现思路：在每一轮训练中，记录每一次由$f(x)={\sum }_{m=1}^{i-1}{\alpha }_m{G}_m(x)$【错误\正确】分类的样本，在加入新的弱学习器中【提高\降低】分类【错误\正确】样本的权值（即改变样本的比例，类似过采样与降采样）

• 加法模型：多个弱分类器$G_m(x)$与对应权值${\alpha }_m$的叠加：

$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

• 样本权值的初始设计（权值平等）：

$$w_{1,i}=\frac{1}{N}$$

• 二分类损失函数，指数损失函数：

$$L(y,f(x))=exp[-yf(x)]=exp[-y\cdot (f_{m-1}(x_i)+{\alpha }_m{G}_m(x))]$$

二、样本权值更新

​ 可以发现，指数损失函数在【正确\错误】分类的样本的值【小于\大于】1，正好符合Adaboost加法模型的实现思路，在加入新的弱学习器中【提高\降低】分类【错误\正确】样本的权值，所以第$m$个弱分类器，第$i$个样本的权值更新可以设计为：
$${\omega }_{m,i}=exp[-y_i{f}_{m-1}(x_i)]$$
​ 在Adaboost模型中，$f_{m-1}(x_i)=a_{m-1}{G}_{m-1}$，所以，权值更新的公式为：
$$w_{m,i}=exp(y_i(-a_{m-1})G_{m-1}(x_i))$$
​ 为了加强不同弱分类器之间的依赖性，在更新权值时是在上一个弱分类器模型的基础上进行更新的：
$$w_{m,i}=w_{m-1,i}\cdot exp(-a_{m-1}{y}_i{G}_{m-1}(x_i))$$
​ 最后加入$Z_{m-1}$，得到最终的权值更新式子：
$$w_{m,i}=\frac{w_{m-1,i}}{z_{m-1}}exp(-a_{m-1}{y}_i{G}_{m-1}(x_i))$$
​ 其中，规范化因子$Z_{m-1}$表示为：
$$Z_{m-1}=\sum _{i=1}^N{\omega }_{m-1,i}exp(-a_{m-1}{y}_i{G}_{m-1}(x_i))$$

[!important]

分类正确时,$y_i=G_{m-1}(x_i)$, $exp(-a_{m-1}{y}_i{G}_{m-1}(x_i))=exp(-a_{m-1})<1$, 其中$a_{m-1}>1$,对应正确样本的权值会减少，同理当错误分类时，$exp(-a_{m-1})>1$，对应样本的权值增加

三、弱分类器权值更新

​ 目标损失函数：
$$L(y,f(x))=exp[-yf(x)]=exp[-y\cdot (f_{m-1}(x_i)+{\alpha }_m{G}_m(x))]$$
​ 在模型优化更新权重的过程中，并不是与传统模型一样采用梯度下降法，因为弱分类器的数量多，更新的参数多，难以实现，在Adaboost模型中采用的前向分布算法，只更新当前弱分类器$G_m$的参数，优化目标：
$$(a_m,G_m(x)=argma{x}_{a,G}\sum _{i=1}^{N}exp[-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))])$$
​ 对$a$求导的结果，表示损失最小的$\alpha$：
$${\alpha }_m=\frac{1}{2}log\frac{1-e_m}{e_m}$$

​ 其中$e_m$表示误差率:
$$e_m^{\prime }=\sum _{i=1}^{N}P(G_m(x_i\ne y_i))=\sum _{i=1}^N{\omega }_{mi}I(G_m(x_i\ne y_i))=\sum _{G_m(x_i)\ne y_i}{\omega }_{mi}$$

​ 最后还需要实现归一化：
$$e_m=\frac{{\sum }_{G_m(x_i)\ne y_i}{\omega }_{mi}}{{\sum }_{i=1}^N}{\omega }_i^m$$

四、代码实现

• 定义弱分类器，采用决策树

model = DecisionTreeClassifier(max_depth=1)
model.fit(X, y, sample_weight=w)
y_pred = model.predict(X)

• 权重更新

​ 权重初始化：$w_{1,i}=\frac{1}{N}$

# 权重初始化
w = np.ones(n_samples) / n_samples # 初始化权重

​ 误差率计算：$e_m=\frac{{\sum }_{G_m(x_i)\ne y_i}{\omega }_{mi}}{{\sum }_{i=1}^N}{\omega }_i^m$

​ 弱分类器$\alpha$更新：${\alpha }_m=\frac{1}{2}log\frac{1-e_m}{e_m}$

# 误差率计算以及更新权重
err = np.sum(w * (y_pred != y)) / np.sum(w)
alpha = 0.5 * np.log((1 - err) / max(err, 1e-10))

​ 样本权重更新：$w_{m,i}=\frac{w_{m-1,i}}{z_{m-1}}exp(-a_{m-1}{y}_i{G}_{m-1}(x_i))$

# 更新样本权重
norm = np.sum(w)
w = w * np.exp(-alpha * y * y_pred)
w /= norm 

• 加法模型预测：$f(x)={\sum }_{m=1}^M{\alpha }_m{G}_m(x)$

for alpha, model in zip(self.alphas, self.models):pred += alpha * model.predict(X)
return np.sign(pred)

• 完整代码：

class AdaBoost:def __init__(self, n_estimators=50):self.n_estimators = n_estimatorsself.alphas = []  # 每个弱分类器的权重self.models = []  # 弱分类器列表def fit(self, X, y):n_samples, n_features = X.shape# 初始化样本权重w = np.ones(n_samples) / n_samples # 初始化权重for _ in range(self.n_estimators):# 使用样本权重训练一个弱分类器model = DecisionTreeClassifier(max_depth=1)model.fit(X, y, sample_weight=w)y_pred = model.predict(X)# 计算分类误差率err = np.sum(w * (y_pred != y)) / np.sum(w)if err >= 0.5:break# 计算弱分类器的权重alpha = 0.5 * np.log((1 - err) / max(err, 1e-10))self.alphas.append(alpha)self.models.append(model)norm = np.sum(w)# 更新样本权重w = w * np.exp(-alpha * y * y_pred)w /= normdef predict(self, X):pred = np.zeros(X.shape[0])for alpha, model in zip(self.alphas, self.models):pred += alpha * model.predict(X)return np.sign(pred)