LPBoost - Linear Program

Linear Program

More generally, let 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.

The primal linear program of LPBoost, optimizing over the non-negative weight vector, the non-negative vector of slack variables and the margin is the following.

\begin{array}{cl} \underset{\boldsymbol{\alpha},\boldsymbol{\xi},\rho}{\min} & -\rho + D \sum_{n=1}^{\ell} \xi_n\\ \textrm{sb.t.} & \sum_{\omega \in \Omega} y_n \alpha_{\omega} h(\boldsymbol{x}_n ; \omega) + \xi_n \geq \rho,\qquad n=1,\dots,\ell,\\ & \sum_{\omega \in \Omega} \alpha_{\omega} = 1,\\ & \xi_n \geq 0,\qquad n=1,\dots,\ell,\\ & \alpha_{\omega} \geq 0,\qquad \omega \in \Omega,\\ & \rho \in {\mathbb R}. \end{array}

Note the effects of slack variables : their one-norm is penalized in the objective function by a constant factor, which -- if small enough -- always leads to a primal feasible linear program.

Here we adopted the notation of a parameter space, such that for a choice the weak classifier is uniquely defined.

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 . Only later it was discovered that such linear programs can indeed be solved efficiently using the classic technique of column generation.

Read more about this topic:  LPBoost

Famous quotes containing the word program:

    “Utah is the only State that gives condemned men a choice between death by hanging or before a firing squad. Most prisoners prefer the firing squad, but one obstinate convict in 1912 elected to be hanged because “hanging is more expensive to the state.””
    —State of Utah, U.S. public relief program (1935-1943)