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:

    “President Lowell of Harvard appealed to students ‘to prepare themselves for such services as the Governor may call upon them to render.’ Dean Greenough organized an ‘emergency committee,’ and Coach Fisher was reported by the press as having declared, ‘To hell with football if men are needed.’”
    —For the State of Massachusetts, U.S. public relief program (1935-1943)