The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins
The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins
复制标题
DOI：
10.5555/1005332.1044712
复制
发表时间：
2004-12
期刊：
影响因子：
--
通讯作者：
C. Rudin;I. Daubechies;R. Schapire
中科院分区：
文献类型：
--
作者：
C. Rudin;I. Daubechies;R. Schapire
为了研究AdaBoost算法的收敛性，我们将AdaBoost算法简化为一个非线性迭代映射，并研究了其权向量的演化。这种动态系统方法使我们能够在某些情况下完全理解AdaBoost的收敛特性；对于这些情况，我们找到了稳定的周期，使我们能够明确地求解AdaBoost的输出。使用这种不寻常的技术，我们能够证明AdaBoost并不总是收敛到最大边际组合分类器，回答了一个开放的问题。此外，我们表明，“非最优”AdaBoost（弱学习算法不一定在每次迭代中选择最佳弱分类器）可能无法收敛到最大边界分类器，即使“最优”AdaBoost产生最大边界。此外，我们表明，如果AdaBoost循环，它在“支持向量”之间循环，即实现相同最小边际的示例。
In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach allows us to understand AdaBoost's convergence properties completely in certain cases; for these cases we find stable cycles, allowing us to explicitly solve for AdaBoost's output.Using this unusual technique, we are able to show that AdaBoost does not always converge to a maximum margin combined classifier, answering an open question. In addition, we show that "non-optimal" AdaBoost (where the weak learning algorithm does not necessarily choose the best weak classifier at each iteration) may fail to converge to a maximum margin classifier, even if "optimal" AdaBoost produces a maximum margin. Also, we show that if AdaBoost cycles, it cycles among "support vectors", i.e., examples that achieve the same smallest margin.