Linear Programming Boosting via Column Generation

By Ayhan Demiriz, Kristin P. Bennett, John Shawe-Taylor. 2002

481 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

The Boosting Approach to Machine Learning An Overview (2003, background): “This connection has led to new algorithms and insights as explored by R¨atsch et al. [62], Grove and Schuurmans [37] and Demiriz, Bennett and Shawe-Taylor [17].”
Rule learning with monotonicity constraints (2009, methodology): “Finally, LPBoost is known to directly maximize the minimum margin, which guarantees a good out of sample accuracy of the ensemble.”
Rule Covering for Interpretation and Boosting (2020, methodology): “Unlike LPBoost, we use the duals as sample weights in our column generation routine.”
Hyperparameter Optimization and Boosting for Classifying Facial Expressions: How good can a "Null" Model be? (2013, methodology): “Ensemble methods such as Bagging (Breiman, 1996a), Boosting (Demiriz et al., 2002), Stacking (Wolpert, 1992; Breiman, 1996b; Sill et al., 2009), and Bayesian Model Averaging (Hoeting et al., 1999) are also commonly employed to exact every last drop of accuracy from a given set of algorithmic…”
An Introduction to Boosting and Leveraging (2002, methodology): “Additionally, we briefly discuss approaches to solve the resulting linear program [48, 154, 147].”
Multi-group support vector machines with measurement costs: A biobjective approach (2008, background): “[14, 17], in which C = {1, 2} and a set of primitive classifiers φk : X → {0, 1} φk(x) = 1 iff x is allocated to class 1 via the k-th classifier, (6)”
On the Dual Formulation of Boosting Algorithms (2009, methodology): “Motivated by the success of the margin theory associated with support vector machines (SVMs), LPBoost was invented by [9], [10] with the intuition of maximizing the minimum margin of all training examples.”
Advance and Prospects of AdaBoost Algorithm (2013, unknown): “在这一思想下 , LPBoost 将最大化训练样本的软间隔与线性规划联系起来 , 用为解大规模优化问题而设计的列生成技术求解算法关键参数 [39 , 44 − 45] .”
Supervised classification and mathematical optimization (2013, methodology): “For instance, in [77] [206] a column generation approach, [105], is used in the boosting environment, whereas a quadratic programming model is used in [174] .”
Binarized Support Vector Machines (2010, methodology): “…initially introduced for the cutting-stock problem (Gilmore and Gomory 1961) and successfully used, under different variants, in different works on support vector machines such as Bi et al. (2004), Bradley and Mangasarian (2000), Demiriz et al. (2002), and Mangasarian and Thompson (2006).”
IPBoost - Non-Convex Boosting via Integer Programming (2020, methodology): “Linear Programming (LP) based boosting procedures have been already explored with LPBoost (Demiriz et al., 2002), which also relies on column generation to price the learners.”
Exact Rule Learning via Boolean Compressed Sensing (2013, methodology): “We could also use all the sample values as thresholds: while it would increase complexity, column generation could be used to mitigate it (Demiriz et al., 2002).”
Column-generation boosting methods for mixture of kernels (2004, methodology): “Hence the duality gap at (α̂, ξ̂, û) is 1 2 ∑ j∈N ( ∑ i ûiyiKij) 2.”