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:

    “In 1869 he started his work for temperance instigated by three drunken men who came to his home with a paper signed by a saloonkeeper and his patrons on which was written “For God’s sake organize a temperance society.””
    —Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)