A Robust Linear Programming Based Boosting Algorithm

AdaBoost has been successfully used in many signal processing systems for data classification. It has been observed that on highly noisy data AdaBoost leads to overfitting. In this paper, a new regularized boosting algorithm LP_norm2-AdaBoost (LPNA), arising from the close connection between AdaBoost and linear programming, is proposed to mitigate the overfitting problem. In the algorithm, the data distribution skewness is controlled during the learning process to prevent outliers from spoiling decision boundaries by introducing a smooth convex penalty function (l₂ norm) into the objective of the minimax problem. A stabilized column generation technique is used to transform the optimization problem into a simple linear programming problem. The effectiveness of the proposed algorithm is demonstrated through experiments on a wide variety of datasets