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:

    “To the cry of “follow Mormons and prairie dogs and find good land,” Civil War veterans flocked into Nebraska, joining a vast stampede of unemployed workers, tenant farmers, and European immigrants.”
    —For the State of Nebraska, U.S. public relief program (1935-1943)