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:

    “Along the highway, all but lost among blatant neon lights flashing ‘Whiskey’ and ‘Dance and Dine,’ are crudely daubed warnings erected by itinerant evangelists, announcing that ‘Jesus is soon coming,’ or exhorting the traveler to ‘prepare to meet thy God.’”
    —For the State of Florida, U.S. public relief program (1935-1943)