BrownBoost

Algorithm description

BrownBoost uses a non-convex potential loss function, thus it does not fit into the AdaBoost framework. The non-convex optimization provides a method to avoid overfitting noisy data sets. However, in contrast to boosting algorithms that analytically minimize a convex loss function (e.g. AdaBoost and LogitBoost), BrownBoost solves a system of two equations and two unknowns using standard numerical methods.

The only parameter of BrownBoost (${\displaystyle c}$ in the algorithm) is the "time" the algorithm runs. The theory of BrownBoost states that each hypothesis takes a variable amount of time (${\displaystyle t}$ in the algorithm) which is directly related to the weight given to the hypothesis ${\displaystyle \alpha }$. The time parameter in BrownBoost is analogous to the number of iterations ${\displaystyle T}$ in AdaBoost.

A larger value of ${\displaystyle c}$ means that BrownBoost will treat the data as if it were less noisy and therefore will give up on fewer examples. Conversely, a smaller value of ${\displaystyle c}$ means that BrownBoost will treat the data as more noisy and give up on more examples.

During each iteration of the algorithm, a hypothesis is selected with some advantage over random guessing. The weight of this hypothesis ${\displaystyle \alpha }$ and the "amount of time passed" ${\displaystyle t}$ during the iteration are simultaneously solved in a system of two non-linear equations ( 1. uncorrelated hypothesis w.r.t example weights and 2. hold the potential constant) with two unknowns (weight of hypothesis ${\displaystyle \alpha }$ and time passed ${\displaystyle t}$). This can be solved by bisection (as implemented in the JBoost software package) or Newton's method (as described in the original paper by Freund). Once these equations are solved, the margins of each example (${\displaystyle r_i(x_j)}$ in the algorithm) and the amount of time remaining ${\displaystyle s}$ are updated appropriately. This process is repeated until there is no time remaining.

The initial potential is defined to be ${\displaystyle \frac{1}{m}\sum _{j=1}^{m}1-\text{erf}(\sqrt{c})=1-\text{erf}(\sqrt{c})}$. Since a constraint of each iteration is that the potential be held constant, the final potential is ${\displaystyle \frac{1}{m}\sum _{j=1}^{m}1-\text{erf}(r_i(x_j)/\sqrt{c})=1-\text{erf}(\sqrt{c})}$. Thus the final error is likely to be near ${\displaystyle 1-\text{erf}(\sqrt{c})}$. However, the final potential function is not the 0–1 loss error function. For the final error to be exactly ${\displaystyle 1-\text{erf}(\sqrt{c})}$, the variance of the loss function must decrease linearly w.r.t. time to form the 0–1 loss function at the end of boosting iterations. This is not yet discussed in the literature and is not in the definition of the algorithm below.

The final classifier is a linear combination of weak hypotheses and is evaluated in the same manner as most other boosting algorithms.

BrownBoost learning algorithm definition

Input:

• ${\displaystyle m}$ training examples ${\displaystyle (x_1,y_1),\dots ,(x_m,y_m)}$ where ${\displaystyle x_j\in X,y_j\in Y=\{-1,+1\}}$
• The parameter ${\displaystyle c}$

Initialise:

• ${\displaystyle s=c}$. (The value of ${\displaystyle s}$ is the amount of time remaining in the game)
• ${\displaystyle r_i(x_j)=0}$ ${\displaystyle \mathrm{\forall }j}$. The value of ${\displaystyle r_i(x_j)}$ is the margin at iteration ${\displaystyle i}$ for example ${\displaystyle x_j}$.

While ${\displaystyle s>0}$:

• Set the weights of each example: ${\displaystyle W_i(x_j)=e^{-\frac{(r_i(x_j)+s{)}^2}{c}}}$, where ${\displaystyle r_i(x_j)}$ is the margin of example ${\displaystyle x_j}$
• Find a classifier ${\displaystyle h_i:X\to \{-1,+1\}}$ such that ${\displaystyle \sum _j{W}_i(x_j)h_i(x_j)y_j>0}$
• Find values ${\displaystyle \alpha ,t}$ that satisfy the equation:
  ${\displaystyle \sum _j{h}_i(x_j)y_j{e}^{-\frac{(r_i(x_j)+\alpha h_i(x_j)y_j+s-t{)}^2}{c}}=0}$.
  (Note this is similar to the condition ${\displaystyle E_{W_{i+1}}[h_i(x_j)y_j]=0}$ set forth by Schapire and Singer. In this setting, we are numerically finding the ${\displaystyle W_{i+1}=\exp \left(\frac{\cdots }{\cdots }\right)}$ such that ${\displaystyle E_{W_{i+1}}[h_i(x_j)y_j]=0}$.)
  This update is subject to the constraint
  ${\displaystyle \sum \left(\mathrm{\Phi }\left(r_i(x_j)+\alpha h(x_j)y_j+s-t\right)-\mathrm{\Phi }\left(r_i(x_j)+s\right)\right)=0}$,
  where ${\displaystyle \mathrm{\Phi }(z)=1-\text{erf}(z/\sqrt{c})}$ is the potential loss for a point with margin ${\displaystyle r_i(x_j)}$
• Update the margins for each example: ${\displaystyle r_{i+1}(x_j)=r_i(x_j)+\alpha h(x_j)y_j}$
• Update the time remaining: ${\displaystyle s=s-t}$

Output: ${\displaystyle H(x)=\text{sign}\left(\sum _i{\alpha }_i{h}_i(x)\right)}$

Empirical results

In preliminary experimental results with noisy datasets, BrownBoost outperformed AdaBoost's generalization error; however, LogitBoost performed as well as BrownBoost. An implementation of BrownBoost can be found in the open source software JBoost.