论文部分内容阅读
好的泛化能力是分类器研究的最根本目的。集成多个基本分类器以获好的泛化性能是近些年分类器研究领域的热点。AdaBoost算法是提出较早,并且泛化性能也很好,获得很大成功的集成分类器算法。它在大量标准数据集和实际应用中显示了优异的效果,吸引了众多学者进行研究,并得到的大量成果。最有影响的工作之一是margin理论。此理论建立了投票分类器的泛化错误的上界,该上界依赖于训练样本的margin分布,而不依赖于迭代次数。这个理论与实践、与直观都很符合。但是,Breiman证明了一个更紧的上界,只与最小margin相关,从而强调更应该只关注最小margin。Breiman的算法arc-gv即优化了最小margin,其泛化能力却不能与最小maxrgin理论预测相一致,常常比AdaBoost的泛化能力差。这使得margin理论受到强烈质疑。平衡margin(简称Emargin)对Breiman的质疑给出回答:Emargin是一种新的margin度量,基于Emargin的新上界较之Breiman的基于最小margin的上界一致紧。说明最小margin对于泛化能力不是最重要的,Emargin是更好的泛化能力衡量标准。
为验证Emargin理论在实际数据集上对泛化能力的指导作用及优化Emargin上界,本文进行以下工作。第一,在标准数据集上比较AdaBoost和LP-AdaBoost,实验结果显示,Emargin理论的预测结果比最小margin的预测结果更符合实际错误率大小,这与我们的理论基本相符。第二,我们最小化Emargin上界,对现有投票分类器的组合系数进行优化,使得新组合的Emargin上界值更小,具更好的泛化能力。本文设计了LP-MME和LP-MEM算法来直接优化Emargin上界。优化基于坐标下降方法和用hinge loss来近似0-1损失,将组合优化问题转化为线性规划,使得计算效率很高。第三,不同于之前优化margin分布的算法,这两个算法可以确保margin分布的左侧分位数得到优化。又由于算法优化了已知的最紧上界--Emargin上界,所以从理论上算法得到的组合系数是最优的。第四,算法在大量标准数据集与多种投票分类器上进行的测试既进一步验证了Emargin理论,又取得了更好的泛化能力。