Boosting with structural sparsity

ABSTRACT

We derive generalizations of AdaBoost and related gradient-based coordinate descent methods that incorporate sparsity-promoting penalties for the norm of the predictor that is being learned. The end result is a family of coordinate descent algorithms that integrate forward feature induction and back-pruning through regularization and give an automatic stopping criterion for feature induction. We study penalties based on the l₁, l₂, and l∞ norms of the predictor and introduce mixed-norm penalties that build upon the initial penalties. The mixed-norm regularizers facilitate structural sparsity in parameter space, which is a useful property in multiclass prediction and other related tasks. We report empirical results that demonstrate the power of our approach in building accurate and structurally sparse models.

REFERENCES

• 1: Bertsekas, D. (1999). Nonlinear programming. Athena Scientific.
• 2: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002 [doi>10.1023/A:1013912006537]
• 3: Ofer Dekel , Shai Shalev-Shwartz , Yoram Singer, Smooth ε-Insensitive Regression by Loss Symmetrization, The Journal of Machine Learning Research, 6, p.711-741, 12/1/2005
• 4: Miroslav Dudík , Steven J. Phillips , Robert E. Schapire, Maximum Entropy Density Estimation with Generalized Regularization and an Application to Species Distribution Modeling, The Journal of Machine Learning Research, 8, p.1217-1260, 12/1/2007
• 5: Friedman, J., Hastie, T., & Tibshirani, R. (2000). Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28, 337--374.
• 6: Friedman, J., Hastie, T., & Tibshirani, R. (2007). Pathwise coordinate optimization. Annals of Applied Statistics, 1, 302--332.
• 7: Kwangmoo Koh , Seung-Jean Kim , Stephen Boyd, An Interior-Point Method for Large-Scale l₁-Regularized Logistic Regression, The Journal of Machine Learning Research, 8, p.1519-1555, 12/1/2007
• 8: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 9: Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
• 10: Negahban, S., & Wainwright, M. (2008). Phase transitions for high-dimensional joint support recovery. Advances in Neural Information Processing Systems 22.
• 11: Obozinski, G., Taskar, B., & Jordan, M. (2007). Joint covariate selection for grouped classification (Technical Report 743). Dept. of Statistics, University of California Berkeley.
• 12: Spiegelhalter, D., & Taylor, C. (1994). Machine learning, neural and statistical classification. Ellis Horwood.
• 13: Manfred K. Warmuth , Jun Liao , Gunnar Rätsch, Totally corrective boosting algorithms that maximize the margin, Proceedings of the 23rd international conference on Machine learning, p.1001-1008, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143970]
• 14: Zhang, T. (2008). Adaptive forward-backward greedy algorithm for sparse learning with linear models. Advances in Neural Information Processing Systems 22.
• 15: Zhang, T., & Yu, B. (2005). Boosting with early stopping: Convergence and consistency. Annals of Statistics, 33, 1538--1579.
• 16: Peng Zhao , Bin Yu, On Model Selection Consistency of Lasso, The Journal of Machine Learning Research, 7, p.2541-2563, 12/1/2006

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.6 Optimization
          Subjects: Gradient methods

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory