Sparse regression ensembles in infinite and finite hypothesis spaces

作     者：Rätsch, G Demiriz, A Bennett, KP 

作者机构：GMD FIRST D-12489 Berlin Germany Rensselaer Polytech Inst Dept Decis Sci & Engn Syst Troy NY 12180 USA Rensselaer Polytech Inst Dept Math Sci Troy NY 12180 USA 

出 版 物：《MACHINE LEARNING》 (机器学习)

年 卷 期：2002年第48卷第1-3期

页      面：189-218页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (970923, 9979860) National Science Foundation, NSF Deutsche Forschungsgemeinschaft, DFG, (JA 379/71, JA 379/91, MU 987/1-1) Deutsche Forschungsgemeinschaft, DFG 

主　　题：ensemble learning boosting regression sparseness semi-infinite programming 

摘      要：We examine methods for constructing regression ensembles based on a linear program (LP). The ensemble regression function consists of linear combinations of base hypotheses generated by some boosting-type base learning algorithm. Unlike the classification case, for regression the set of possible hypotheses producible by the base learning algorithm may be infinite. We explicitly tackle the issue of how to define and solve ensemble regression when the hypothesis space is infinite. Our approach is based on a semi-infinite linear program that has an infinite number of constraints and a finite number of variables. We show that the regression problem is well posed for infinite hypothesis spaces in both the primal and dual spaces. Most importantly, we prove there exists an optimal solution to the infinite hypothesis space problem consisting of a finite number of hypothesis. We propose two algorithms for solving the infinite and finite hypothesis problems. One uses a column generation simplex-type algorithm and the other adopts an exponential barrier approach. Furthermore, we give sufficient conditions for the base learning algorithm and the hypothesis set to be used for infinite regression ensembles. Computational results show that these methods are extremely promising.