Gentle Ada Boost for CARTs

The Gentle Ada Boost Algorithm [5] is used to select a set of simple CARTs to achieve a given detection and error rate [13]. In the following, a detection is referred to as a hit and an error as a false alarm.

The learning is based on $N$ weighted training examples $(x_1,y_1), \ldots, (x_N,y_N)$, where $x_i$ are the images and $y_i \in \{-1,1\}, i \in \{1,\ldots,N\}$ the classified output. At the beginning of the learning phase the weights $w_i$ are initialized with $w_i = 1/N$. The following three steps are repeated to select CARTs until a given detection rate $d$ is reached:

1. Every classifier, i.e., a CART, is fit to the data. Hereby the error $e$ is calculated with respect to the weights $w_i$.
2. The best CART $h_t$ is chosen for the classification function. The counter $t$ is incremented.
3. The weights are updated with $w_i := w_i \cdot e^{-y_i h_t(x_i)}$ and renormalized.

The final output of the classifier is sign$(\sum_{t=1}^T h_t(x)) > 0$, with $h_t(x)$ the weighted return value of the CART. Next, a cascade based on these classifiers is built.