↑ arvau

Wikipedia / LPBoost

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 thus also belongs to the class of margin classifier algorithms.

into one of two classes, labelled 1 and -1, respectively. LPBoost is an algorithm for learning such a classification function, given a set of training examples with known class labels. LPBoost is a machine learning technique especially suited for joint classification and feature selection in structured domains.

LPBoost overview

As in all boosting classifiers, the final classification function is of the form

are non-negative weightings for weak may be just a little bit better than random, but the resulting linear combination of many weak classifiers can perform very well.

by starting with an empty set for the current set of weak classifiers are adjusted. This is repeated until no weak classifiers to add remain.

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

be the possibly infinite set of weak classifiers, also termed hypotheses. One way to write down the problem LPBoost solves is as a linear program with infinitely many variables.

of slack variables and the margin is the following.

, which—if small enough—always leads to a primal feasible linear program.

is uniquely defined.

. Only later it was discovered that such linear programs can indeed be solved efficiently using the classic technique of column generation.

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

as

for a single decision stump maximizing the left hand side of the dual constraint. If the constraint cannot be violated by any choice of decision stump, none of the corresponding constraint can be active in the original problem and the restricted problem is equivalent.

D

has to be found using model selection has the following properties.

  • .

  • is a lower bound on the fraction of training samples outside or on the margin.

Algorithm

Input:

Output:

Initialization

Iterate

then

  1. break

  2. solution of the LPBoost dual

  3. Lagrangian multipliers of solution to LPBoost dual problem

is set to a small positive value in order obtain a good solution quickly.

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. Demiriz et al. showed that under mild assumptions, any base learner can be used. If the base learners are particularly simple, they are often referred to as decision stumps.

, a base learner could be a linear soft margin support vector machine. Or even more simple, a simple stump of the form

for a positive or negative class.

Given weights for the training samples, constructing the optimal decision in order to optimize the gain function.

References