高级算法—AdaBoost算法

status

Published

type

Post

date

Jan 15, 2026

slug

aa-adaboost

summary

本文从博弈论的视角，证明了多个略优于随机猜测的弱分类器组合的模型可以收敛到强分类器，并对 AdaBoost 算法的工作原理给出严格数学证明。

题目

Problem 8 In binary classification, we are given a set of data points and an unknown true classification . There is a family of classifiers where each , and a weak learning algorithm that, given any weight vector , returns a classifier such that

That is, the chosen classifier is correct on a weighted majority of the data.

(8a) Prove that there is a vector such that for every , we have

where is if , if and if .

(8b) Give an algorithm that outputs the vector , listing only its non-zero coordinates. The algorithm should use only standard computational steps, and calls to . Notice that the time complexity of the algorithm should not depend on .

解答

(8a)

将问题建模为一个零和游戏. 玩家选择分类器的权重分布 , 策略空间为单纯形:

玩家选择数据点的权重分布 , 策略空间为单纯形:

当分类器分类正确时, 收益 , 分类错误则收益 . 游戏中, 一个数据点的收益为所有分类器在该数据点收益的加权和. 设收益函数表示总收益:

玩家希望最大化收益, 玩家希望最小化收益.

根据 Minimax Theorem, 博弈值满足:

若玩家先手, 选择 , 然后玩家选择 . 玩家的最优策略是将所有权重放在一个分类器上, 使得最大:

根据弱学习算法的定义, 存在分类器使得:

即的加权正确率至少是 . 代入得:

因此, 对于任何 , 玩家可以保证收益 .

若玩家先手, 选择 , 然后玩家选择 . 根据 Minimax Theorem, . 因此存在一个玩家的最优策略 , 使得对于任意的 :

因此玩家选择这个 . 当玩家将权重集中在一个数据点上时:

上式对任意都成立. 选择为 , 得:

即和同号:

证毕.

(8b)

计算的算法 (AdaBoost):

输入: 数据集 , 真分类 , 弱学习算法

输出: 的非零坐标集合

流程:

初始化: 令 . 对所有 , 令 . ( 表示权重分布的分量在第轮的值)

设参数令

对 :

调用弱学习器:
计算加权错误率:

其中为指示变量.

设系数
更新权重分布并归一化:

其中为使的归一化常数.

将加入 . 若已在中, 则累加系数:

可以利用算法的输出还原出 , 构建强分类器 :

为了证明算法的正确性, 需要证明两个定理:

定理 : 算法在步之后收敛, 使得

定理 : 计算步数和调用的次数均为

首先证明 : 算法在步得到的强分类器分类错误样本数为 .

引理 : 算法的任一轮都有

证明 :

由弱学习算法的性质, 满足:

因此:

代入得:

引理证毕.

引理 : 设强分类器的训练误差为

则 .

证明 :

设辅助函数使得 , 即:

因此, 等价于 , 即 , 所以:

代入得:

对于 , 有:

根据及函数在单调递增的性质:

所以:

引理证毕.

由于 , 所以 , 根据引理 :

而是整数, 只能有 . 定理证毕.

算法的复杂度分析:

由于 , 因此调用的次数为 , 属于 . 在循环内, 计算和更新都需要遍历数据集 , 因此时间复杂度均为 . 总计算步数为 , 属于 . 且算法的时间复杂度不依赖 . 定理证毕.

🍵高级算法—AdaBoost算法

题目

解答

(8a)

(8b)