Linear programming boosting via column generation
Linear programming boosting via column generation
复制标题
DOI：
10.1023/a:1012470815092
复制
发表时间：
2002-01-01
期刊：
影响因子：
7.5
通讯作者：
Shawe-Taylor, J
中科院分区：
文献类型：
--
作者：
Demiriz, A;Bennett, KP;Shawe-Taylor, J
我们研究线性规划（LP）的方法，以提高和证明他们的有效解决方案，使用LPBoost，列生成基于单纯形法。我们将问题表述为好像所有可能的弱假设都已经产生了。由弱假设产生的标签成为问题的新特征空间。提升任务变成在标签空间中构造学习函数，使误分类误差最小化并使软余量最大化。我们证明了分类，最小化1-范数软边际误差函数直接优化的泛化误差界。等效的线性规划可以有效地解决使用列生成技术开发的大规模优化问题。由此产生的LPBoost算法可以用来解决任何LP提升公式迭代优化的双重错误分类成本在一个限制的LP和动态生成弱假设，使新的LP列。我们提供了软边缘分类，置信度和回归提升问题的算法。与梯度提升算法不同，它可能只收敛于极限，LPBoost在有限次数的迭代中收敛到满足数学上定义良好的最优性条件的全局解。与基于梯度的方法相比，LPBoost的最优解非常稀疏。在计算方面，LPBoost在质量和计算成本方面与AdaBoost具有竞争力。
We examine linear program (LP) approaches to boosting and demonstrate their efficient solution using LPBoost, a column generation based simplex method. We formulate the problem as if all possible weak hypotheses had already been generated. The labels produced by the weak hypotheses become the new feature space of the problem. The boosting task becomes to construct a learning function in the label space that minimizes misclassification error and maximizes the soft margin. We prove that for classification, minimizing the 1-norm soft margin error function directly optimizes a generalization error bound. The equivalent linear program can be efficiently solved using column generation techniques developed for large-scale optimization problems. The resulting LPBoost algorithm can be used to solve any LP boosting formulation by iteratively optimizing the dual misclassification costs in a restricted LP and dynamically generating weak hypotheses to make new LP columns. We provide algorithms for soft margin classification, confidence-rated, and regression boosting problems. Unlike gradient boosting algorithms, which may converge in the limit only, LPBoost converges in a finite number of iterations to a global solution satisfying mathematically well-defined optimality conditions. The optimal solutions of LPBoost are very sparse in contrast with gradient based methods. Computationally, LPBoost is competitive in quality and computational cost to AdaBoost.