Linear Programming Boosting (LPBoost) is a supervised classifier from the boosting family of classifiers. LPBoost maximizes a margin between training samples of different classes and hence also belongs to the class of margin-maximizing supervised classification algorithms. Consider a classification function
Contents
- LPBoost overview
- Linear program
- Column Generation for LPBoost
- LPBoost dual problem
- Convergence criterion
- Penalization constant D displaystyle D
- Algorithm
- Realized margin
- Convergence guarantee
- Base learners
- References
which classifies samples from a space
LPBoost overview
As in all boosting classifiers, the final classification function is of the form
where
LPBoost constructs
The property that all classifier weights are adjusted in each iteration is known as totally-corrective property. Early boosting methods, such as AdaBoost do not have this property and converge slower.
Linear program
More generally, let
The primal linear program of LPBoost, optimizing over the non-negative weight vector
Note the effects of slack variables
Here we adopted the notation of a parameter space
When the above linear program was first written down in early publications about boosting methods it was disregarded as intractable due to the large number of variables
Column Generation for LPBoost
In a linear program a column corresponds to a primal variable. Column generation is a technique to solve large linear programs. It typically works in a restricted problem, dealing only with a subset of variables. By generating primal variables iteratively and on-demand, eventually the original unrestricted problem with all variables is recovered. By cleverly choosing the columns to generate the problem can be solved such that while still guaranteeing the obtained solution to be optimal for the original full problem, only a small fraction of columns has to be created.
LPBoost dual problem
Columns in the primal linear program corresponds to rows in the dual linear program. The equivalent dual linear program of LPBoost is the following linear program.
For linear programs the optimal value of the primal and dual problem are equal. For the above primal and dual problems, the optimal value is equal to the negative 'soft margin'. The soft margin is the size of the margin separating positive from negative training instances minus positive slack variables that carry penalties for margin-violating samples. Thus, the soft margin may be positive although not all samples are linearly separated by the classification function. The latter is called the 'hard margin' or 'realized margin'.
Convergence criterion
Consider a subset of the satisfied constraints in the dual problem. For any finite subset we can solve the linear program and thus satisfy all constraints. If we could prove that of all the constraints which we did not add to the dual problem no single constraint is violated, we would have proven that solving our restricted problem is equivalent to solving the original problem. More formally, let
That is, we search the space
Penalization constant D {displaystyle D}
The positive value of penalization constant
Algorithm
- Initialization
- Weights, uniform
λ n ← 1 ℓ , n = 1 , … , ℓ - Edge
γ ← 0 - Hypothesis count
J ← 1
- Weights, uniform
- Iterate
-
h ^ ← argmax ω ∈ Ω ∑ n = 1 ℓ y n h ( x n ; ω ) λ n - if
∑ n = 1 ℓ y n h ^ ( x n ) λ n + γ ≤ θ then- break
-
h J ← h ^ -
J ← J + 1 -
( λ , γ ) ← solution of the LPBoost dual -
α ← Lagrangian multipliers of solution to LPBoost dual problem
-
-
f ( x ) := sign ( ∑ j = 1 J α j h j ( x ) )
Note that if the convergence threshold is set to
Realized margin
The actual margin separating the training samples is termed the realized margin and is defined as
The realized margin can and will usually be negative in the first iterations. For a hypothesis space that permits singling out of any single sample, as is commonly the case, the realized margin will eventually converge to some positive value.
Convergence guarantee
While the above algorithm is proven to converge, in contrast to other boosting formulations, such as AdaBoost and TotalBoost, there are no known convergence bounds for LPBoost. In practise however, LPBoost is known to converge quickly, often faster than other formulations.
Base learners
LPBoost is an ensemble learning method and thus does not dictate the choice of base learners, the space of hypotheses
The number of base learners commonly used with Boosting in the literature is large. For example, if
The above decision stumps looks only along a single dimension
Given weights for the training samples, constructing the optimal decision stump of the above form simply involves searching along all sample columns and determining