---
abstract: 'Boosting algorithms have been widely used to tackle a plethora of problems. In the last few years, a lot of approaches have been proposed to provide standard AdaBoost with cost-sensitive capabilities, each with a different focus. However, for the researcher, these algorithms shape a tangled set with diffuse differences and properties, lacking a unifying analysis to jointly compare, classify, evaluate and discuss those approaches on a common basis. In this series of two papers we aim to revisit the various proposals, both from theoretical (Part I) and practical (Part II) perspectives, in order to analyze their specific properties and behavior, with the final goal of identifying the algorithm providing the best and soundest results.'
address: 'Signal Theory and Communications Department, University of Vigo, Maxwell Street, 36310, Vigo, Spain'
author:
- 'Iago Landesa-Vázquez, José Luis Alba-Castro'
---

AdaBoost ,Classification ,Cost ,Asymmetry ,Boosting

Introduction {#sec:Intro1}
============

The classical approach to solve a classification problem is based on the use of a single expert that must be able to build a solution classifier. However, in the last few decades, a new classification paradigm, based on the combination of several experts in a distributed decision process, has arisen and attracted the attention of the Machine Learning community. The success of this paradigm relies on several theoretical, practical and even biological reasons (such as generalization properties, complexity, data handling, data source fusion, etc.) making these *Ensemble Classifiers* [@Polikar06] preferable to classical ones in many scenarios.

One of the milestones on the history of ensemble methods was the work published by Robert E. Schapire in 1990 [@Schapire90], in which the author proves the equivalence between *weak* learners, algorithms able to generate classifiers performing only slightly better than random guessing, and *strong* learners, those generating classifiers which are correct in all but an arbitrarily small fraction of the instances. This new model of learnability, in which weak learners can be *boosted* to achieve strong performance when they are properly combined, paved the way to one of the most prominent families of algorithms within the ensemble classifiers paradigm: *boosting*.

In 1997, Yoav Freund and Robert E. Schapire [@FreundSchapire97] proposed a more general boosting algorithm called AdaBoost (from Adaptive Boosting). Unlike previous approaches, AdaBoost does not require any prior knowledge on weak hypothesis space, and it iteratively adjusts to weak hypothesis that become part of the ensemble. Apart from theoretical guarantees and practical advantages over its predecessors, early experiments on AdaBoost also showed a surprising resistance to overfitting. As a consequence of all these qualities, AdaBoost has received an attention “rarely matched in computational intelligence” [@Polikar06] being an active research topic in the fields of machine learning, pattern recognition and computer vision [@Schapire98; @SchapireSinger99; @Opitz99; @Friedman00; @MeaseWyner08a; @ViolaJones04; @MasnadiVasconcelos11; @LandesaAlba12] till present.

Throughout this time, several studies have been conducted to analyze AdaBoost from different points of view, relating the algorithm with different theories: margin theory [@Schapire98], entropy [@Kivinen99], game theory [@FreundSchapire96], statistics [@Friedman00], etc. In the same way, numerous AdaBoost and boosting variants have been proposed for the two-class and multiclass problems: Real AdaBoost [@SchapireSinger99; @Friedman00], LogitBoost [@Friedman00], Gentle AdaBoost [@Friedman00], AsymBoost [@ViolaJones02], AdaCost [@Fan99], AdaBoost.M1 [@FreundSchapire96b], AdaBoost.M2 [@FreundSchapire96b], AdaBoost.MH [@SchapireSinger99], AdaBoost.MO [@SchapireSinger99], AdaBoost.MR [@SchapireSinger99], JointBoosting [@Torralba04], AdaBoost.ECC [@GuruswamiSahai99] etc.

Among the different kinds of classification problems, one common subset is that of tasks with clearly different costs depending on each possible decision, or scenarios with very unbalanced class priors in which one class is extremely more frequent or easier to sample than the other one. In such *cost-sensitive* or *asymmetric* conditions (disaster prediction, fraud detection, medical diagnosis, object detection, etc.) classifiers must be able to focus their attention in the rare/most valuable class. Many works in the literature have been devoted to cost-sensitive learning [@Elkan01; @Provost97; @Weiss03], including a significant set of proposals on how to provide AdaBoost with asymmetric properties (e.g. [@Fan99; @Ting00; @ViolaJones04; @ViolaJones02; @Sun07; @MasnadiVasconcelos07; @MasnadiVasconcelos11; @LandesaAlba12; @LandesaAlba13]). The link between AdaBoost and Cost-Sensitive learning has special interest since AdaBoost is the learning algorithm inside the widespread Viola-Jones object detector framework [@ViolaJones04], a seminal work in computer vision dealing with a markedly asymmetric problem and a enormous number of weak classifiers (the order of hundred of thousands).

The different AdaBoost asymmetric variants proposed in the literature are very heterogeneous, and their related works are focused on emphasizing the possible advantages of each respective method, rather than building a common framework to jointly classify, analyze and discuss the different approaches. The final result is that, for the researcher, these algorithms shape a confusing set with no clear theoretical properties to rule their application in practical problems.

In this series of two papers we try to classify, analyze, compare and discuss the different proposals on Cost-Sensitive AdaBoost algorithms, in order to gain a unifying perspective. Our final goal is finding a definitive scheme to directly translate any cost-sensitive learning problem to the AdaBoost framework and shedding light on which algorithm can ensure the best performance.

The current article is focused on the theoretical part of our work and it is organized as follows: next section focuses on standard AdaBoost and its related theoretical framework, Section \[sec:CSvar\] is devoted to cluster and explain, in an homogeneous notational framework, the different cost-sensitive AdaBoost variants proposed in the literature, and in Section \[sec:Discuss\] we analyze in depth those algorithms with a fully theoretical derivation scheme. Finally, we present the preliminary conclusions (Section \[sec:Conclusions1\]) that will be culminated in the accompanying paper “” covering the experimental part of our work.

AdaBoost {#sec:AdaBoost}
========

Let us define $\mathbf{X}$ as the random process from which our observations $\mathbf{x}=\left(x_{1},\ldots,x_{N}\right)^{T}$ are sampled, and $Y$ the random variable governing the related labels $y \in \{-1,1\}$. In this scenario, a *detector* $H(\mathbf{x})$ (we will also refer to it as *classifier* or *hypothesis*) is a function trying to guess the label $y$ of a given sample $\mathbf{x}$, and it can be defined in terms of a more generic function $f\left(\mathbf{x}\right) \in \mathbb{R}$ which we will call *predictor*.

$$\label{pred_eqn}
H(\mathbf{x})=\mathrm{sign}\left[f\left(\mathbf{x}\right)\right]$$

Suppose we have a training set of $n$ examples $\mathbf{x}_i$ with its respective labels $y_i$, a weight distribution $D(i)$ over them and a *weak learner* able to select, according to labels and weights, the best detector $h(\mathbf{x})$ from a predefined collection of weak classifiers. In this scenario, the role of AdaBoost is to compute a goodness measure $\alpha$ depending on the performance obtained by the selected weak classifier, and to update, accordingly, the weight distribution to emphasize misclassified training examples. Then, with a different weight distribution, the weak learner can make a new hypothesis selection and the process restarts. By iteratively repeating this scheme (, , , ) with $t$ indexing the number of learning rounds, AdaBoost obtains an ensemble of weak classifiers with respective goodness parameters $\alpha_{t}$.

$$\label{alphat_eqn}
%\begin{split}
\alpha_{t}=
%\frac{1}{2} \ln \left(\frac{1+\sum D_{t}(i) y_{i} h_{t}(x_{i})}{1-\sum D_{t}(i) y_{i} h_{t}(x_{i})}\right)
\frac{1}{2} \log \left(\frac{1+r_{t}}{1-r_{t}}\right)
%=\frac{1}{2} \ln \left( \frac{1-\epsilon_{t}}{\epsilon_{t}}\right)
%\end{split}$$

$$\label{rt_eqn}
r_{t}=
\sum_{i=1}^{n}D_{t}(i) y_{i} h_{t} (\mathbf{x}_{i})$$

$$\label{weight_rule_eqn}
D_{t+1}(i)=
\frac{D_{t}(i)\exp\left(-\alpha_{t} y_{i} h_{t}(\mathbf{x}_{i})\right)}{Z_{t}}$$

$$\label{zt_eqn}
Z_{t}=
\sum_{i=1}^{n} D_{t}(i) \exp\left(-\alpha_{t} y_{i} h_{t}(\mathbf{x}_{i})\right)$$

Weak hypothesis searching in AdaBoost is guided to maximize goodness $\alpha_{t}$ of each selected classifier, which is equivalent to maximize, at each iteration, weighted correlation $r_{t}$ () between labels $y_{i}$ and predictions $h_{t}$. This iterative searching process can continue until a predefined number $T$ of training rounds have been completed or some performance goal is reached. The final AdaBoost *strong detector* $H(\mathbf{x})$ is defined () in terms of a boosted *predictor* $f(\mathbf{x})$ built as an ensemble of the selected weak classifiers weighted by their respective goodness parameters $\alpha_{t}$.

$$\label{stradb_eqn}
H(\mathbf{x})=\mathrm{sign}\left(f(\mathbf{x})\right)=\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{x})\right)$$

Error Bound Minimization {#subsec:GeneralizedVersion}
------------------------

Robert E. Schapire and Yoram Singer proposed [@SchapireSinger99], from the original derivation of AdaBoost, a generalised and simplified analysis that models the algorithm as an additive (round-by-round) minimization process of an exponential bound on the strong classifier training error ($E_{T}$). This bounding process is explained in equation[^1] () from which all AdaBoost equations we have presented, weight update rule included, can be derived [@LandesaAlba12].

$$\label{bound_ineq_eqn} 
{\begin{array}{c} 
\underbrace{\strut H(\mathbf{x}_{i})\neq y_{i} \:\Rightarrow\: y_{i} f(\mathbf{x}_{i}) \leq 0 \:\Rightarrow\: \exp\left(-y_{i} f(\mathbf{x}_{i})\right) \geq 1}\\
\Downarrow\\
E_{T}= \sum_{i=1}^{n} D_{1}(i) \llbracket H(\mathbf{x}_{i}) \neq y_{i}\rrbracket \leq \sum_{i=1}^{n} D_{1}(i) \exp \left( -y_{i} f(\mathbf{x}_{i}) \right)
\end{array}
}$$

After (), the final bound of the training error obtained by AdaBoost can be expressed as (), and the additive minimization of the exponential bound $\tilde{E}_{T}$ can be seen as finding, in each round, the weak hypothesis $h_{t}$ that maximizes $r(t)$, the weighted correlation between labels $(y_{i})$ and predictions $(h_{t})$.

$$\label{et_bound_eqn}
E_{T}\leq
\prod_{t=1}^{T}Z_{t}\leq
\prod_{t=1}^{T}\sqrt{1-{r_{t}}^2}=\tilde{E}_{T}$$

When weak hypothesis are binary, $h_{i}\in\{-1,+1\}$, the last inequality on () becomes an equality, and parameter $\alpha_{t}$ can be directly rewritten () in terms of the weighted error $\epsilon_{t}$ of the current weak classifier. As can be seen, the minimization process turns out to be equivalent to simply selecting the weak classifier with less weighted error.

$$\label{round_err_eqn}
\epsilon_{t}=
\sum_{i=1}^{n} D_{t}(i) \llbracket h_{t}(\mathbf{x}_{i}) \neq y_{i}\rrbracket=
\sum_{\textrm{err}}D_{t}(i)$$

$$\label{alphat2_eqn}
%\begin{split}
\alpha_{t}=
\frac{1}{2} \log \left( \frac{1-\epsilon_{t}}{\epsilon_{t}}\right)
%\end{split}$$

In line with other works, for the sake of simplicity and clarity, we will focus our analysis on this *Discrete* version of AdaBoost using binary weak classifiers, which does not prevent our conclusions from being extended to other variations of the algorithm. Also, trying to define an homogeneous notational framework for our work, we have unified the different notations found in the literature to that used by Schapire and Singer [@SchapireSinger99]. A summary of AdaBoost can be found on Algorithm \[adb\_algorithm\] (all the algorithms discussed in this paper are detailed, with homogeneous notation, in Appendix \[app:algorithms\]).

Statistical View of Boosting {#subsec:Statistical View}
----------------------------

One of the milestones in boosting research and the foundation of many variations of AdaBoost is the highly-cited contribution by Jerome H. Friedman et al. [@Friedman00] in which a statistical reinterpretation of boosting is given. Following the exponential criterion seen in the last subsection, Friedman et al. showed that AdaBoost can be motivated as an iterative algorithm building an additive logistic regression model $f(\mathbf{x})$ that minimizes the expectation of the exponential loss, $J(f(\mathbf{x}))$:

$$\label{loss_eqn}
J(f(\mathbf{x}))=\E\left[\exp(-yf(\mathbf{x}))\right]$$

This defined loss is effectively minimized at $$\label{regress_eqn}
f(\mathbf{x})=\frac{1}{2}\log\left(\frac{\Prob(y=1|\mathbf{x})}{\Prob(y=-1|\mathbf{x})}\right)$$ so a direct connection between boosting and additive logistic regression models is drawn. According to this statistical perspective, AdaBoost predictions can be seen as estimations of the posterior class probabilities, which has served as basis to develop many extensions and variants of the algorithm (among them, the Cost-Sensitive Boosting scheme [@MasnadiVasconcelos07; @MasnadiVasconcelos11]).

It is important to mention that, despite the huge and unquestionable value of the statistical view, some enriching controversy, revealed by empirical evidences [@MeaseWyner08a; @Bennet08; @MeaseWyner08b], has arisen about inconsistencies of this interpretation.

Cost-Sensitive Variants of AdaBoost {#sec:CSvar}
===================================

Cost-sensitive classification problems can be fully portrayed by a cost matrix [@Elkan01] whose components map the loss of each possible result. For two-class problems there are four kinds of results: true positives, true negatives, false positives and false negatives; so the cost matrix $\mathbf{C}$ can be defined as follows:

$$\label{cost_matrix}
\begin{tabular} {c c c c c c l l l}
&  & \multicolumn{2}{c}{Actual} & & & \\
&  &  Negative & Positive & & &\\
\multirow{2}{*}{$\mathbf{C}=$} & \multirow{2}{*}{{\Huge(}} & $c_{nn}$ & $c_{np}$ & \multirow{2}{*}{{\Huge)}} & Negative & \multirow{2}{*}{Classified}\\
&  & $c_{pn}$ & $c_{pp}$ & & Positive & &
\end{tabular}$$

The optimal decision for a given cost matrix will not change if all its coefficients are added a constant, or if they are multiplied by a constant positive factor. As a result, a cost matrix for two-class classification problems only has two degrees of freedom and can be parametrized by only two coefficients: false negatives normalized cost ($\overline{c}_{np}$) and true positives normalized cost ($\overline{c}_{pp}$):

$$\label{simple_C}
\mathbf{C}=\left(
\begin{array} {c c}
0 & \overline{c}_{np}\\
1 & \overline{c}_{pp}\\
\end{array}
\right)$$

In the most common case correct decisions have null related costs ($c_{nn}=c_{pp}=0$), so $\mathbf{C}$ has eventually only one degree of freedom: the ratio between cost of errors on positives ($c_{np}$) and cost of errors on negatives ($c_{pn}$). In the literature and most practical problems, cost requirements are usually specified by these two error parameters, which, for simplicity, we will denote as $C_P$ and $C_N$ respectively.

$$\label{simple_C2}
\mathbf{C}=\left(
\begin{array} {c c}
0 & C_P/C_N\\
1 & 0\\
\end{array}
\right)
\rightarrow \left(
\begin{array} {c c}
0 & C_P\\
C_N & 0\\
\end{array}
\right)$$

The coefficients of a cost matrix may not be constant in general. While constant coefficients model a scenario where all the examples of each class have the same cost (class-level asymmetry), variable coefficients mean that examples belonging to the same class can have different costs (example-level asymmetry). Whatever the scenario, it is also important to notice that, for “reasonableness” [@Elkan01], correct predictions in a cost matrix should have lower associated costs than mistaken ones ($c_{nn}<c_{np}$ and $c_{pp}<c_{pn}$).

Bearing in mind that class-level asymmetry is the most common for detection problems, and that example-level asymmetry can be modeled by a class-level asymmetry scheme with a resampled training dataset, for our analysis we have homogenized the different Asymmetric AdaBoost approaches to the class-level scheme. Thus, we will follow a prototypical cost-sensitive detection statement specified by two constant coefficients $C_P$ and $C_N$, that can be alternatively described by the “normalized cost asymmetry” of the problem $\gamma \in (0,1)$:

$$\gamma=\frac{C_{P}}{C_{P}+C_{N}}$$

Despite the widespread use of these particularizations, in Appendix \[app:cost\_scen\] we will extend our conclusions to example-level asymmetry and also cases in which correct classification costs are nonzero.

It is also important to emphasize that this work is focused on AdaBoost and its cost-sensitive variants, a realm of methods in the literature that are based on a exponential loss minimization criterion, analogous to that giving rise to the original algorithm (as we have seen in Sections \[subsec:GeneralizedVersion\] and \[subsec:Statistical View\] from different points of view) . Other boosting algorithms based on other kinds of losses beyond the exponential paradigm, like the binomial log-likelihood [@Friedman00] or the p-norm loss [@LozanoAbe08], are outside the scope of the current study.

Classification {#subsec:Classification}
--------------

In order to give a clear overview of the cost-sensitive variants of AdaBoost proposed in the literature, we suggest an analytical classification scheme to cluster them into three categories according to the way asymmetry is reached: *A posteriori*, *Heuristic* and *Theoretical*.

### A Posteriori {#subsec:APosteriori}

The seminal face/object detector framework by Paul Viola and Michael J. Jones [@ViolaJones04] uses a validation set to modify, after training, the threshold of the original (cost-insensitive) AdaBoost strong classifier. The goal is to adjust the balance between false positive and detection rates, building, that way, a cost-sensitive boosted classifier:

$$\label{vjmod_eqn}
\tilde{H}(\mathbf{x})=\mathrm{sign}\left(f(\mathbf{x})-\phi\right)=\mathrm{sign}\left({\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{x})}-\phi\right)$$

Besides the great success of the detection framework, the authors themselves acknowledge that neither this a posteriori cost-sensitive tuning ensures that the selected weak classifiers are optimal for the asymmetric goal [@ViolaJones02], nor their modifications preserve the original AdaBoost training and generalization guarantees [@ViolaJones04].

An useful insight on this can be drawn from the analysis by Masnadi-Shirazi and Vasconcelos [@MasnadiVasconcelos11]. According to the Bayes Decision Rule, the optimal predictor $f^{*}(\mathbf{x})$ can be expressed in terms of the optimal predictor for a cost-insensitive scenario $f^{*}_{0}(\mathbf{x})$ and a threshold $\phi$ depending on costs.

$$\label{pred_thresh}
f^{*}\left(\mathbf{x}\right)=\log\left(\frac{\Prob_{Y|\mathbf{X}}\left(1|\mathbf{x}\right)C_{P}}{\Prob_{Y|\mathbf{X}}\left(-1|\mathbf{x}\right)C_{N}}\right)=\log\left(\frac{\Prob_{Y|\mathbf{X}}\left(1|\mathbf{x}\right)}{\Prob_{Y|\mathbf{X}}\left(-1|\mathbf{x}\right)}\right)-\log\left(\frac{C_N}{C_P}\right)=f^*_0(\mathbf{x})-\phi$$

As a consequence, for any cost requirements, the optimal cost-sensitive *detector* $H^{*}(\mathbf{x})$ can also be expressed as a threshold on the cost-insensitive optimal *predictor* $f^{*}_{0}(\mathbf{x})$.

$$\label{optimal_detector}
H^*\left(\mathbf{x}\right)=\mathrm{sign}\left[f^*(\mathbf{x})\right]=\mathrm{sign}\left[f^*_0(\mathbf{x})-\phi\right]$$

In practical terms, however, learning algorithms do not have access to the exact probability distributions and they must approximate this optimal detector rule. Thus, AdaBoost can be seen as an algorithm obtaining an approximation ($\hat{H}_0(\mathbf{x})$) to the optimal cost-insensitive *detector*, built by means of an estimation ($\hat{f}_0(\mathbf{x})$) of the cost-insensitive *predictor* ().

$$\label{adaboost_estimation}
\hat{H}_0(\mathbf{x})=\mathrm{sign}\left[\hat{f}_0(\mathbf{x})\right]=\mathrm{sign}\left({\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{x})}\right) \approx  H^*_0(\mathbf{x})$$

By definition, the purpose of AdaBoost is to obtain a *detector* as close as possible to the optimal one, and this optimality is ensured if the learned *predictor* satisfies two necessary and suficient conditions:

$$\label{costinsens_cond}
{\begin{array}{c} 
\hat{H}_0(\mathbf{x})=H_0^*(\mathbf{x}) \\
\Updownarrow \\
\begin{cases}
\hat{f}_0\left(\mathbf{x}\right)=f_0^*(\mathbf{x})=0 & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x})=\Prob_{Y|\mathbf{X}}(-1|\mathbf{x})\\
\mathrm{sign}\left[\hat{f}_0\left(\mathbf{x}\right)\right]=\mathrm{sign}\left[f_0^*(\mathbf{x})\right] & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x}) \neq \Prob_{Y|\mathbf{X}}(-1|\mathbf{x})
\end{cases}
\end{array}
}$$

As can be seen, in order to reach optimal *detection* the predictor learned by AdaBoost should match the optimal predictor in the boundary region, but only its sign elsewhere. Analogously, optimal detection for the cost-sensitive case, would be ensured by two equivalent conditions:

$$\label{costsens_cond}
{\begin{array}{c} 
\hat{H}(\mathbf{x})=H^*(\mathbf{x}) \\
\Updownarrow \\
\begin{cases}
\hat{f}\left(\mathbf{x}\right)=f^*(\mathbf{x})=0 & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x})C_P=\Prob_{Y|\mathbf{X}}(-1|\mathbf{x})C_N\\
\mathrm{sign}\left[\hat{f}\left(\mathbf{x}\right)\right]=\mathrm{sign}\left[f^*(\mathbf{x})\right] & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x})C_P \neq \Prob_{Y|\mathbf{X}}(-1|\mathbf{x})C_N
\end{cases}
\end{array}
}$$

Thus, optimality conditions required by the *a posteriori* modification of the AdaBoost threshold would be as follows:

$$\label{threshmod_cond}
{\begin{array}{c} 
\hat{H}(\mathbf{x})=H^*(\mathbf{x}) \\
\Updownarrow \\
\begin{cases}
\hat{f}_0\left(\mathbf{x}\right)=f_0^*(\mathbf{x})=\phi & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x})C_P=\Prob_{Y|\mathbf{X}}(-1|\mathbf{x})C_N\\
\mathrm{sign}\left[\hat{f}_0\left(\mathbf{x}\right)-\phi\right]=\mathrm{sign}\left[f_0^*(\mathbf{x})-\phi\right] & \text{if } \Prob_{Y|\mathbf{X}}(1|\mathbf{x})C_P \neq \Prob_{Y|\mathbf{X}}(-1|\mathbf{x})C_N
\end{cases}
\end{array}
}$$

Bearing in mind that AdaBoost predictor $\hat{f}_0(\mathbf{x})$ is geared to satisfy (), the optimality conditions for *threshold modification* are not necessarily fulfilled. The only way to meet these requirements for any cost would be that the predictor obtained by AdaBoost matched the optimal one along the whole space, which is an obviously stronger condition than actually required (). Moreover, recalling the exponential bounding equation in which AdaBoost is based (), we can see that, once the sign of the obtained predictor matches the right label, the error bound is further minimized for increasing absolute values of the estimated predictor, no matter how close they are (or not) to the optimal predictor value.

As a consequence, there are no guarantees that a threshold change on the classical AdaBoost predictor will give us a cost-sensitive detector oriented to be optimal. Nonetheless, this non-optimality has not prevented that asymmetric detectors obtained by the Viola-Jones framework have been very successfully used for object detection.

### Heuristic {#subsec:Heuristic}

Most of the proposed cost-sensitive variations of AdaBoost [@Fan99; @Ting00; @ViolaJones02; @Sun07] try to deal with asymmetry through direct manipulations of the weight update rule (), but they are not full reformulations of AdaBoost for cost-sensitive scenarios. Masnadi-Shirazi and Vasconcelos pointed out that this kind of manipulations “provide no guarantees of asymptotic convergence to a good cost-sensitive decision rule” [@MasnadiVasconcelos11], considering those algorithms as “heuristic” modifications of AdaBoost [@MasnadiVasconcelos07; @MasnadiVasconcelos11].

Although these proposals have, in greater or lesser extent, some theoretical basis, for the sake of clarity and distinctiveness in our analysis, we will maintain the term *heuristic*, as used in [@MasnadiVasconcelos07; @MasnadiVasconcelos11], to label this group of approaches based on the arbitrary modification of the weight update rule, as opposed to the full *theoretical* derivations we will delve into in the next subsection.

### AsymBoost {#subsubsec:AsymBoost .unnumbered}

Assuming the non-optimality of the strong classifier threshold adjustment procedure in their object detector framework (Section \[subsec:APosteriori\]), Paul Viola and Michael J. Jones proposed a different scheme, coined as AsymBoost [@ViolaJones02], trying to optimize AdaBoost for cost-sensitive classification problems.

Discarding the asymmetric weight initialization to be “naive” and only “somewhat effective” due to “AdaBoost’s balanced reweighting scheme” (we will discuss on this point in Section \[subsec:weight\]), AsymBoost proposes to distributedly emphasize weights by an asymmetric modulation before each round. In practical terms, the only change is multiplying weights $D(i)$ by a constant factor $(C_P/C_N)^{y_i/2T}$ before every learning step of a $T$-round process. As a consequence, the overall asymmetric factor seen by positive elements across the whole process is $C_P/C_N$ times the factor seen by negatives.

$$\label{asb_equation}
D(i)_{t+1} = \frac{D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)\left(\frac{C_P}{C_N}\right)^{\frac{y_{i}}{2T}}}{\sum_{i=1}^{n}D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)\left(\frac{C_P}{C_N}\right)^{\frac{y_{i}}{2T}}}$$

AsymBoost, that reduces to AdaBoost when costs are uniform, is detailed in Algorithm \[asb\_algorithm\] (Appendix \[app:algorithms\]).

Though the global AsymBoost procedure seems to be theoretically sound, the *equitable* asymmetry sharing among a *fixed* number of rounds entails significant problems: Why such a rigid equitable sharing procedure should be optimal inserted in an adaptive framework such as AdaBoost? Why should we have to know in advance the number of training rounds while standard AdaBoost does not require that? Note that standard AdaBoost allows flexible performance tests to decide when to stop training, since any change in the total number of rounds is directly performed by training new additional rounds or trimming the current ensemble. However, a change in the size of the final ensemble (number of rounds) would strictly require Asymboost to re-train the whole classifier with a new asymmetry distribution.

### AdaCost {#adacost .unnumbered}

Wei Fan et al. proposed [@Fan99] a cost-sensitive variation of AdaBoost called AdaCost. The idea behind AdaCost is to modify the weight update rule, so examples with higher costs have sharper increases of their weights after misclassification but lighter decreases when are succesfully classified. This scheme is essentially addresed by introducing a misclassification adjustment function $\beta(i)$ into the weight update rule ().

$$\label{adc_weights}
D_{t+1}(i) = \frac{D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\beta(i)\right)}{\sum_{i=1}^{n}D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\beta(i)\right)}$$

The misclassification adjustment function must depend on the cost ($C(i)$) of each example/class and the success/fail of its classification. As a result, $\beta(i)$ is imposed to be non-decreasing respect to $C(i)$ when classification fails, and non-increasing when classification succeeds. This opens the door to a huge amount of functions satisfying such requirements, from which authors chose the next:

$$\beta(i)=
\left\{
\begin{array}{ll}
0.5 \left(1-C(i)\right) & \mbox{$\text{if } h_{f}(\mathbf{x}_{i}) = y_{i}$},\\
0.5 \left(1+C(i)\right) & \mbox{$\text{if } h_{f}(\mathbf{x}_{i}) \neq y_{i}$}.
\end{array} \right.$$

As can be seen, AdaCost does not match with AdaBoost for uniform costs and also applies a cost-dependent weight pre-emphasis (see Algorithm \[adc\_algorithm\]).

### CSB0, CSB1 and CSB2 {#csb0-csb1-and-csb2 .unnumbered}

Following the same idea of modifying the weight update rule, the CSB (acronym from Cost-Sensitive Boosting) family of algorithms [@Ting98; @Ting00] propose three different updating schemes depending on which parameters are involved, resulting in CSB0, CSB1 and CSB2 algorithms (see respective Algorithms \[csb0\_algorithm\], \[csb1\_algorithm\] and \[csb2\_algorithm\]). These rules are complemented, for all the three alternatives, by an asymmetric weight initialization and a minimum expected cost criterion for strong classification replacing the usual weighted voting scheme:

$$H(\mathbf{x})=\mathrm{sign}\left(\sum_{t=1}^{T}\alpha_{t}h_{t}(\mathbf{x}) \left( C_P \llbracket h_{t}(\mathbf{x})=+1 \rrbracket + C_N \llbracket h_{t}(\mathbf{x})=-1 \rrbracket \right)\right)$$

This new voting rule gives emphasis, in run time, to weak hypothesis deciding in favor of the costly class. Of the three alternatives, only the last one, CSB2, is reduced to standard AdaBoost when costs are equal.

### AdaC1, AdaC2 and AdaC3 {#adac1-adac2-and-adac3 .unnumbered}

Defining new ways to modify the weight update rule, Yanmin Sun et al. [@Sun05; @Sun07] proposed another family of asymmetric AdaBoost alternatives called AdaC1, AdaC2 and AdaC3. These variants couple the cost factor in different parts of the update equation: inside the exponent (AdaC1), outside the exponent (AdaC2) and both (AdaC3):

$$\label{ac1_update}
D_{t+1}(i) = \frac{D_{t}(i)\exp\left(-\alpha_{t}c_{i}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}{\sum_{i=1}^{n}D_{t}(i)\exp\left(-\alpha_{t}c_{i}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}$$

$$\label{ac2_update}
D_{t+1}(i) = \frac{c_{i}D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}{\sum_{i=1}^{n}c_{i}D_{t}(i)\exp\left(-\alpha_{t}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}$$

$$\label{ac3_update}
D_{t+1}(i) = \frac{c_{i}D_{t}(i)\exp\left(-\alpha_{t}c_{i}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}{\sum_{i=1}^{n}c_{i}D_{t}(i)\exp\left(-\alpha_{t}c_{i}y_{i}h_{t}\left(\mathbf{x}_i\right)\right)}$$

As a difference from previous approaches, these changes in the weight update are also propagated to the way goodness parameter $\alpha_t$ is defined and, as a consequence, have influence on how the weak classifier error is computed (see Algorithms \[ac1\_algorithm\], \[ac2\_algorithm\], \[ac3\_algorithm\]). All these variants reduce to AdaBoost when the cost function $C(i)$ is 1 for all examples.

### Theoretical {#subsec:Theoretical}

The methods in the previous subsection have one key point in common: the starting point of their derivations is an arbitrary modification of the weight update rule. However, as can be easily shown following the work by Schapire and Singer [@SchapireSinger99], weight update in standard AdaBoost is actually a *consequence* of the error minimization procedure () and not an arbitrary starting point of it. Thus, the way to reach theoretically sound cost-sensitive boosting algorithms should be to walk the path in the opposite direction: designing a new asymmetric derivation scheme to obtain a new full formulation (that may include a new weight update rule), instead of partially adapting previous equations.

There are three alternatives in the literature that follow different theoretically sound derivation schemes reaching cost-sensitive variants of AdaBoost: Cost-Sensitive AdaBoost [@MasnadiVasconcelos07; @MasnadiVasconcelos11], AdaBoostDB [@LandesaAlba13] and Cost-Generalized AdaBoost [@LandesaAlba12].

### Cost-Sensitive AdaBoost {#cost-sensitive-adaboost .unnumbered}

The Cost-Sensitive Boosting framework proposed by Hamed Masnadi-Shirazi and Nuno Vasconcelos [@MasnadiVasconcelos07; @MasnadiVasconcelos11] has its roots in the Statistical View of Boosting [@Friedman00], by adapting the standard loss in equation () with asymmetric exponential arguments for each class component.

$$\label{csloss_eqn}
J(f(\mathbf{x}))=\E\left[\llbracket y=1 \rrbracket \mathrm{e}^{-C_{P}f(\mathbf{x_i})} + \llbracket y=-1 \rrbracket \mathrm{e}^{C_{N}f(\mathbf{x_i})}\right]$$

This asymmetric loss is theoretically minimized by the asymmetric logistic transform of $\Prob\left(y=1|\mathbf{x}\right)$ (see Section \[subsec:Statistical View\]), which should ensure cost-sensitive optimality.

$$\label{stat_sol_asym}
\begin{split}
f(x)=\frac{1}{C_{P}+C_{N}}\log\frac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}
\end{split}$$

The empirical minimization of the asymmetric loss proposed by Masnadi-Shirazi and Vasconcelos follows a gradient descent scheme on the space of boosted (combined and modulated) binary weak classifiers, resulting in the Cost-Sensitive Adaboost algorithm shown in Algorithm \[csa\_algorithm\]. As can be seen, the final solution involves hyperbolic functions and scalar search procedures, being extremely more complex and computing demanding than the original AdaBoost.

### AdaBoostDB {#adaboostdb .unnumbered}

Following the generalizad analysis of AdaBoost [@SchapireSinger99] instead of the Statistical View of Boosting, a different approach to provide AdaBoost with Cost-Sensitive properties through a fully theoretical derivation procedure is presented in [@LandesaAlba13]. This algorithm, coined as AdaBoostDB (from Double Base), is based on the use of different exponential bases $\beta_P$ and $\beta_N$ for each class error component, thus defining a class-dependent error bound to minimize.

$$\label{exp_bound_eqn_asym}
%\begin{split}
E_{T} \leq \tilde{E}_T = \sum_{i=1}^{m} D_{1}(i){\beta_P}^{ -y_{i} f(\mathbf{x_{i}})} + \sum_{i=m+1}^{n} D_{1}(i){\beta_N}^{ -y_{i} f(\mathbf{x_{i}})}
%\end{split}$$

On the one hand, the derivation scheme followed and the polynomial model used to address the problem, enable a different and extremely efficient formulation, able to achieve over 99% training time saving with respect to Cost-Sensitive AdaBoost (see Algorithm \[abdb\_algorithm\]). On the other hand, this class-dependent error is fully equivalent to the cost-sensitive loss () defined for Cost-Sensitive Boosting, so both minimizations will converge to the same solution and ensure the same formal guarantees.

As a result, AdaBoostDB is a much more efficient framework to reach the same solution as Cost-Sensitive Boosting (except for numerical errors related to the different models adopted, hyperbolyc vs. polynomial). However, despite its large improvement in training complexity and performance, AdaBoostDB is still much more complex than standard AdaBoost.

### Cost-Generalized AdaBoost {#cost-generalized-adaboost .unnumbered}

The Asymmetric AdaBoost problem is addressed in [@LandesaAlba12] from a different theoretical perspective, realizing that one kind of modification have systematically been either overlooked or undervalued in the related literature: weight initialization.

Even though some preliminary studies by Freund and Schapire [@FreundSchapire97], creators of AdaBoost, left the initial weight distribution free to be controlled by the learner, AdaBoost is “de facto” defined, almost everywhere in the literature (e.g. [@Schapire98; @SchapireSinger99; @Fan99; @FreundSchapire99; @Ting00; @Friedman00; @Polikar06; @Sun07; @Polikar07; @MasnadiVasconcelos11]), with a fixed initial uniform weight distribution. From there, some asymmetric boosting algorithms (like AdaCost or CSB) use cost-sensitive initialization as a lateral or secondary strategy respect to their proposed weight update rules, while others (like AsymBoost or Cost-Sensitive Boosting), immediately discard asymmetric weight initialization to be “naive” and ineffective, arguing that the first boosting round would absorb the full introduced asymmetry and the rest of the process would keep entirely symmetric.

In [@LandesaAlba12], following a different insight to analyze AdaBoost and obtaining a novel error bound interpretation, asymmetric weight initialization is shown to be an effective way to reach cost-sensitiveness, and, as occurs with everything related to boosting, it is achieved in an additive round-by-round (asymptotic) way. All, with the added advantage that weight initialization is the only needed change to gain asymmetry with regard to standard AdaBoost (even weight update rule is unchanged). Hence, for whatever desired asymmetry, both complexity and formal guarantees of the original AdaBoost remain intact.

In this work, we will refer to the algorithm underlying this perspective as Cost-Generalized AdaBoost (see Algorithm \[adbg\_algorithm\]).

Theoretical Algorithms: Analysis and Discussion {#sec:Discuss}
===============================================

Though in the experimental part of our work (see the accompanying paper [@LandesaAlba??b]) we will show comparative results of all the alternatives presented in the previous section, at this point we will focus our attention on the three proposals with a fully theoretical derivation scheme: Cost-Sensitive AdaBoost [@MasnadiVasconcelos07; @MasnadiVasconcelos11], AdaBoostDB [@LandesaAlba13] and Cost-Generalized AdaBoost [@LandesaAlba12]. The first important aspect we should notice is that these three proposals can be effectively analyzed as if they were only two, since Cost-Sensitive AdaBoost and AdaBoostDB, despite following different perspectives and obtaining markedly different algorithms, share an equivalent theoretical root and drive to the same solution [@LandesaAlba13]. As a consequence, if not otherwise specified, in this section we will refer to one or another interchangeably, giving priority to the name Cost-Sensitive AdaBoost due to its chronological precedence.

The Question of Weight Initialization {#subsec:weight}
-------------------------------------

As commented in Section \[subsec:Theoretical\], despite some initial studies pointing to free initial weight distributions [@FreundSchapire97] or works proposing cost-proportional weighting as an effective way to transform generic cost-insensitive learning algorithms into cost-sensitive ones [@Zadrozny03], subsequent works on boosting have insisted on two recurrent ideas: On the one hand, uniform distribution has been assumed as the “de facto” standard for weight initialization when defining AdaBoost (e.g. [@Schapire98; @SchapireSinger99; @Fan99; @FreundSchapire99; @Ting00; @Friedman00; @Polikar06; @Sun07; @Polikar07; @MasnadiVasconcelos11]); on the other hand, asymmetric weight initialization has been systematically rejected as a valid method to achieve cost-sensitive boosted classifiers, arguing that it is insufficient [@Fan99; @Ting00] or ineffective [@ViolaJones02; @MasnadiVasconcelos07; @MasnadiVasconcelos11].

However, in [@LandesaAlba12], AdaBoost is demonstrated to have inherent and sound cost-sensitive properties embedded in the way the weight distribution is initialized. In fact, the method we are referring to as Cost-Generalized AdaBoost, was not even originally proposed as a new algorithm: “it is just AdaBoost” [@LandesaAlba12] with appropriate initial weights. Such an analysis, supported by a novel class-conditional interpretation of AdaBoost, is, thus, in clear contradiction to the supposed ineffectiveness of cost-sensitive weight initialization underlying previous works.

In order to definitely clarify this contradiction, we will connect both perspectives by demonstrating the validity of asymmetric weight initialization in the same scenarios and lines of reasoning that have been previously used in the literature to decline its use.

### The Supposed Symmetry {#subsubsec:supposed_symmetry}

Masnadi-Shirazi and Vasconcelos [@MasnadiVasconcelos11] when explaining their Cost-Sensitive Boosting framework, immediately discard the unbalanced weight initialization (calling it “naive implementation”) with the argument that iterative weight update in AdaBoost “quickly destroys the initial asymmetry” obtaining a “predictor” which “is usually not different from that produced with symmetric initial conditions”. Though their statement is not explicitly supported for any further test or bibliographic reference, it seems to be extracted from the work by Viola and Jones [@ViolaJones02] in which AsymBoost is presented. In that work, the initial weight modification technique is rejected arguing that “the first classifier selected absorbs the entire effect of the initial asymmetric weights”, and assuming the rest of the process as “entirely symmetric”. It is because of this seeming problem that AsymBoost was designed for distributing an equitable asymmetry among a fixed number of rounds.

The cost-sensitive analysis by Viola and Jones [@ViolaJones02] is illustrated by a four-round boosted classifier graphic representation that supports their conclusions against asymmetric weight initialization. However, this example can be misleading: what would happen if boosting were run for more than those four rounds? An answer can be found in Figure \[counter\_example\_1\_fig\], where we have reproduced and extended that illustrative experiment.

![Synthetic counterexample to the example by Viola and Jones [@ViolaJones02], with costs $C_P=4$ and $C_N=1$, and the same polarity as the original:(a) training set with the first four weak classifiers superimposed; (b) weak classifiers after 50 training rounds; (c) Global error evolution through 50 training rounds. Weak classifiers are stumps in the linear 2D space. Positive examples are marked as ‘$+$’, ‘$\circ$’ are the negative ones, and ‘1’ denotes the first selected weak classifier. Positives are the costly class.[]{data-label="counter_example_1_fig"}](Fig01.pdf){width="0.8\columnwidth"}

Strictly following Viola and Jones [@ViolaJones02], after Figure \[counter\_example\_1\_fig\]a we could reach the seeming conclusion that, once an initial asymmetric weak classifier has been selected, the selection of the remaining weak classifiers is not guided by an asymmetric goal. However, as showed by Schapire and Singer [@SchapireSinger99], AdaBoost is an additive minimization process and, as such, it has an *asymptotic* behavior, a kind of behavior that can not be properly judged by stopping after only a few training rounds. Running the algorithm for many more rounds in the same example (see Figure \[counter\_example\_1\_fig\]b), we appreciate that many other subsequent selected classifiers are, at least, as asymmetric as the first one.

The class-conditional interpretation of AdaBoost in [@LandesaAlba12] shows that the asymmetry encoded by the initial weight distribution is actually translated to a cost-sensitive global error (a weighted error), and what AdaBoost is actually minimizing is a bound on that global error. Thus, instead of inspecting the individual asymmetry of each single hypothesis, the cost-sensitive behavior of AdaBoost should be evaluated, for correctness, in terms of the *cumulative contribution* of *all* the selected weak classifiers giving rise to the strong one. Figure \[counter\_example\_1\_fig\]c shows how, even in a scenario like the one proposed by Viola and Jones [@ViolaJones02], the classifier obtained by AdaBoost after an asymmetric weight initialization follows a real cost-sensitive iterative profile.

Moreover, postulates by Viola and Jones [@ViolaJones02] and Masnadi-Shirazi and Vasconcelos [@MasnadiVasconcelos11] can also be refuted by simply inverting labels on the same set (see Figure \[counter\_example\_2\_fig\]). As can be seen, no weak classifier is able to satisfy, by itself, the requirements of that “supposed” initial round absorbing the full asymmetry of the problem. However, even in such an unfavorable scenario, the desired asymmetry is effectively achieved, from cost-proportionate initial weights, after a (boosted) round-by-round cumulative process.

![Synthetic counterexample to the example by Viola and Jones [@ViolaJones02], with costs $C_P=4$ and $C_N=1$, and with opposite polarity to the original:(a) training set with the first four weak classifiers superimposed;(b) weak classifiers after 50 training rounds; (c) Global error evolution through 50 training rounds. Weak classifiers are stumps in the linear 2D space. Positive examples are marked as ‘$+$’, ‘$\circ$’ are the negative ones, and ‘1’ denotes the first selected weak classifier. Positives are the costly class.[]{data-label="counter_example_2_fig"}](Fig02.pdf){width="0.8\columnwidth"}

Further comments on these experiments can be found in Appendix \[app:comments\_figures\].

### Weight Initialization inside the Cost-Sensitive Boosting Framework {#subsubsec:weight_cost_sensitive}

Cost-Sensitive AdaBoost [@MasnadiVasconcelos11] is an algorithm that, despite having a rigorous theoretical derivation, is built upon the belief that cost-sensitive initial weighting is not a valid method to achieve asymmetric boosted classifiers. However, as we have already mentioned, the theoretical analysis in [@LandesaAlba12] refutes that supposed invalidity. A clarifying experiment at this point is to introduce asymmetric weight initialization inside the Cost-Sensitive AdaBoost theoretical framework, to assess the theoretical validity of the former with the tools used by the latter.

Based on the Statistical View of Boosting [@Friedman00], the cost-sensitive expected loss (i.e. the risk function) proposed by Masnadi-Shirazi and Vasconcelos to derive Cost-Sensitive AdaBoost, consists on two class-dependent exponential components with asymmetry embedded in its exponents:

$$\label{csloss_eqn1}
J_{CSA}(f(\mathbf{x}))=\E\left[\llbracket y=1 \rrbracket \exp(-C_{P}f(\mathbf{x})) + \llbracket y=-1 \rrbracket \exp(C_{N}f(\mathbf{x}))\right]$$

Following the proof derivation scheme in [@MasnadiVasconcelos11], if the derivatives of this loss are set to zero, we will obtain the function of minimum expected loss (minimum risk) conditioned on $\mathbf{x}$ for Cost-Sensitive AdaBoost, that, as can be seen, is based on the asymmetric logistic transform of $\Prob(y=1|\mathbf{x})$.

$$\label{statistical_deriv_cda}
{\begin{array}{c} 
J_{CSA}(f(\mathbf{x}))=\Prob\left(y=1|\mathbf{x}\right)\exp(-C_{P}f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)\exp(C_{N}f(\mathbf{x}))\\
\Downarrow\\
\dfrac{\partial J_{CSA}(f(\mathbf{x}))}{\partial f(\mathbf{x})}= -C_{P}\Prob\left(y=1|\mathbf{x}\right)\exp(-C_{P}f(\mathbf{x}))+C_{N}\Prob\left(y=-1|\mathbf{x}\right)\exp(C_{N}f(\mathbf{x}))=0\\
\Downarrow\\
\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}=\exp((C_{P}+C_{N})f(\mathbf{x}))\\
\Downarrow\\
f_{CGA}(\mathbf{x})=\dfrac{1}{C_{P}+C_{N}}\log\left(\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}\right)
\end{array}
}$$

Now, let us suppose that the two cost parameters $C_P$ and $C_N$, rather than in the exponents, are incorporated as direct modulators of the exponentials (). This procedure is equivalent to model the initial weight distribution by means of two uniform *class-conditional* distributions, respectively modulated by $C_{P}/\left(C_{P}+C_{N}\right)$ and $C_{N}/\left(C_{P}+C_{N}\right)$, i.e. an asymmetric weight initialization as the one proposed giving rise to Cost-Generalized AdaBoost.

$$\label{csloss_exp}
J_{CGA}(f(\mathbf{x}))=\E\left[\llbracket y=1 \rrbracket C_{P} \exp(-f(\mathbf{x})) + \llbracket y=-1 \rrbracket C_{N} \exp(f(\mathbf{x}))\right]$$

If we repeat the above derivation scheme on this new loss, we will find the function of minimum expected loss (minimum risk) conditioned on $\mathbf{x}$ for Cost-Generalized AdaBoost:

$$\label{statistical_deriv_cga}
{\begin{array}{c} 
J_{CGA}(f(\mathbf{x}))=\Prob\left(y=1|\mathbf{x}\right)C_{P}\exp(-f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)C_{N}\exp(f(\mathbf{x}))\\
\Downarrow\\
\dfrac{\partial J_{CGA}(f(\mathbf{x}))}{\partial f(\mathbf{x})}= -\Prob\left(y=1|\mathbf{x}\right)C_{P}\exp(-f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)C_{N}\exp(f(\mathbf{x}))=0\\
\Downarrow\\
\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}=\exp(2f(\mathbf{x}))\\
\Downarrow\\
f_{CGA}(\mathbf{x})=\dfrac{1}{2}\log\left(\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}\right)
\end{array}
}$$

As can be seen, the obtained minimizer is also based on the asymmetric logistic transform of $\Prob(y=1|\mathbf{x})$, showing us that, even from the Cost-Sensitive AdaBoost derivation perspective, there is no reason to discard asymmetric weight initialization as a valid approach to build cost-sensitive boosted classifiers[^2].

Comparative Analysis of the Theoretical Approaches {#subsec:algorithms_cmp}
--------------------------------------------------

As we have seen, among the three asymmetric AdaBoost algorithms with a full theoretical derivation, two of them (Cost-Sensitive AdaBoost and AdaBoostDB) drive to the same solution, while the other one (Cost-Generalized AdaBoost) has been shown to guarantee the same theoretical validity than its counterparts. At this point, we may wonder if Cost-Generalized AdaBoost is also obtaining the same solution as Cost-Sensitive AdaBoost/AdaBoostDB. As we will see in the experimental part of our work (in the second part of this series of two papers [@LandesaAlba??b]) the answer to this question is “no”: classifiers obtained by Cost-Sensitive AdaBoost and Cost-Generalized AdaBoost in the same scenarios are markedly different. In this section, from a theoretical perspective, we will analyze the differences between the two algorithms, with the aim of achieving the intrinsic distinctivenesses of their respective classifiers.

### Error Bound Minimization {#subsubsec:error_bound_cmp}

As commented in Section \[sec:CSvar\], the most common detection problem can be parametrized by the next cost matrix:

$$\mathbf{C}
=\left(
\begin{array} {c c}
c_{nn} & c_{np}\\
c_{pn} & c_{pp}\\
\end{array}
\right)
=\left(
\begin{array} {c c}
0 & C_P\\
C_N & 0\\
\end{array}
\right)$$

We will start our comparative analysis by following the error bound minimization perspective originally proposed by Schapire and Singer [@SchapireSinger99], also used in the derivation of Cost-Generalized AdaBoost and AdaBoostDB. From that point of view, classical AdaBoost, with its initial uniform weight distribution, is an algorithm driven to minimize an exponential bound ($\tilde{E}_T$) on the training error ($E_T$) (), as illustrated in Figure \[std\_adb\_bound\_fig\]. In that figure, the horizontal axis ($y_if(\mathbf{x}_i)$) represents the *performance score* of a classification, whose sign indicates the success (if $y_if(\mathbf{x}_i)>0$) or failure (if $y_if(\mathbf{x}_i)<0$) of the decision, and whose magnitude indicates the confidence expected by the classifier on its decision. The exponential bound is decreasing for increasing performance scores, so the classical AdaBoost minimization process is aimed to maximize correct classifications and their margin (distance to the boundary), in a scenario where all the training examples follow a common cost scheme.

$$\label{std_adb_bound}
E_{T}= \sum_{i=1}^{n} \frac{1}{n} \llbracket H(\mathbf{x}_{i}) \neq y_{i}\rrbracket \leq \sum_{i=1}^{n} \frac{1}{n} \exp \left( -y_{i} f(\mathbf{x}_{i}) \right) = \tilde{E}_{T}$$

![Training error bound of AdaBoost. The loss (y-axis) associated to each decision has an exponential dependency on the performance score of the strong classifier (x-axis).[]{data-label="std_adb_bound_fig"}](Fig03.pdf){width="7.5cm"}

Cost-Sensitive AdaBoost and AdaBoostDB, assumming that the training set is divided into two significant subsets (positives and negatives), define two different exponential bounds ($\tilde{E}_{TP}$ and $\tilde{E}_{TN}$) with different associated costs ($C_P$ and $C_N$) over each subset. These costs are inserted as exponent modulators into each class-dependent exponential bound (), reaching a cost-sensitive behavior that can be graphically interpreted as shown in Figure \[csb\_bound\_fig\]. The goal is, again, to maximize correct classifications and their margin, but this time in a scenario where positives and negatives have different associated losses.

$$\label{csb_bound}
\begin{split}
E_{T} &= \sum_{i=1}^{n} \frac{1}{n} \llbracket H(\mathbf{x}_{i}) \neq y_{i}\rrbracket\\
& \leq \sum_{i=1}^{m} \frac{1}{n} \exp \left( -C_{P}y_{i} f(\mathbf{x}_{i}) \right) + \sum_{i=m}^{n} \frac{1}{n} \exp \left( -C_{N}y_{i} f(\mathbf{x}_{i}) \right)\\
& =\tilde{E}_{TP} + \tilde{E}_{TN} = \tilde{E}_{T}
\end{split}$$

![Training error bound of Cost-Sensitive AdaBoost and AdaBoostDB for $C_P=2$ and $C_N=1$. Loss has a class-dependent definition and is composed of two different exponential functions.[]{data-label="csb_bound_fig"}](Fig04.pdf){width="7.5cm"}

As can be seen, asymmetric modifications in Cost-Sensitive AdaBoost (and AdaBoostDB) are based on new bounds for the training error, while the error definition itself remains unchanged from original (cost-insensitive) AdaBoost.

Cost-Generalized AdaBoost, on the other hand, is based on redefining the training error and then applying the standard exponential bounding process. To achieve this, training error in positives (${E}_{TP}$) and in negatives (${E}_{TN}$) are computed separately, and then are modulated by its respective normalized costs. The resulting class-dependent weighted error components (${E}_{TP}'$ and ${E}_{TN}'$) jointly define the *cost-sensitive global training error* ($E_{T}'$). The same way as in standard AdaBoost, each of these weighted error components can be exponentially bounded ($\tilde{E}_{TP}$ and $\tilde{E}_{TN}$), and the combination of the two resulting *class-dependent* bounds will define a cost-sensitive global bound ($\tilde{E}_{T}$) (), that is the function being minimized by Cost-Generalized AdaBoost. The scenario is graphically depicted in Figure \[cgb\_bound\_fig\].

$$\label{cgb_bound}
\begin{split}
E_{T}' &= E_{TP}' + E_{TN}' = \frac{C_{P}}{C_{P}+C_{N}} E_{TP} + \frac{C_{N}}{C_{P}+C_{N}} E_{TN} \\
& = \frac{C_{P}}{C_{P}+C_{N}} \sum_{i=1}^{m} \frac{1}{m} \llbracket H(\mathbf{x}_{i}) \neq y_{i}\rrbracket + \frac{C_{N}}{C_{P}+C_{N}} \sum_{i=m+1}^{n} \frac{1}{n-m} \llbracket H(\mathbf{x}_{i}) \neq y_{i}\rrbracket  \\
& \leq \frac{C_{P}}{C_{P}+C_{N}} \sum_{i=1}^{m} \frac{1}{m} \exp \left( -y_{i} f(\mathbf{x}_{i}) \right) + \frac{C_{N}}{C_{P}+C_{N}} \sum_{i=m}^{n} \frac{1}{n-m} \exp \left( -y_{i} f(\mathbf{x}_{i}) \right)\\
& =\tilde{E}_{TP} + \tilde{E}_{TN} = \tilde{E}_{T}
\end{split}$$

![Training error bound of Cost-Generalized AdaBoost for $C_P=2$ and $C_N=1$. Loss keeps again an exponential dependency, but now modulated by a class-dependent behavior.[]{data-label="cgb_bound_fig"}](Fig05.pdf){width="7.5cm"}

It is important to notice that, by definition, all these algorithms have the goal of obtaining the best possible classifier able to deal with the problem in a cost-sensitive sense, and that the bounding loss functions $\tilde{E}_{T}$ are a mere mathematical tool to make the minimization problem tractable. Thus, from a formal point of view, the direct definition of a cost-sensitive error to be subsequently bounded, as proposed by Cost-Generalized AdaBoost, seems to be more suitable than using the standard cost-insensitive error and manipulate its bound to be asymmetric, as suggested by Cost-Sensitive AdaBoost or AdaBoostDB.

Figure \[preval\_fig\] illustrates the prevalence of the class-dependent error bounds of the two algorithms, assuming, without loss of generality, that positives have a greater cost than negatives $C_P>C_N$ (the opposite case can be modeled by a simple label swap). As can be seen, in Cost-Generalized AdaBoost (Figure \[preval\_fig\]a) the loss associated to positives is always greater than the loss associated to negatives, and the ratio between the two class-dependent losses remains constant along the performance scores. However, in Cost-Sensitive AdaBoost (Figure \[preval\_fig\]b), the ratio between losses varies according to the score, to the extent that class prevalence is inverted depending on which side of the success boundary ($y_if(\mathbf{x}_i)=0$) we are.

![Class prevalence of error bounds for Cost-Generalized AdaBoost (a) and Cost-Sensitive AdaBoost (b) ($C_P=2$, $C_N=1$).[]{data-label="preval_fig"}](Fig06.pdf){width="0.9\columnwidth"}

The iterative learning process behind AdaBoost builds a predictor function $f(\mathbf{x}_i)$ aimed to progressively (round by round) minimize the respective loss function over the training dataset. In terms of classification, this means that AdaBoost classifiers are trained not only to maximize the accuracy of the classifier over the training set, but also to maximize the margin of its decisions. So, once one training example is correctly classified, the tendency of the learner will be to continue increasing the confidence of its prediction ($\mathrm{abs}(f(\mathbf{x}_i))$) to move it away from the decision boundary ($f(\mathbf{x}_i)=0$). For Cost-Generalized AdaBoost, this means that any positive training example will always be more costly (and in the same ratio) than any negative example with its same performance score, whatever this score is. However, in the case of Cost-Sensitive AdaBoost, prevalence ratio varies exponentially with performance scores. So, when scores are positive, negative training examples become the prevalent ones.

Bearing in mind that the performance score of any training example, at any iteration of the learning process, is determined by the evaluation over the example of the boosted predictor learned so far, and that the weight of this example for the next learning round will depend on the value of the related bounding loss for that particular score, we can draw the two following consequences:

-   In Cost-Generalized AdaBoost positives will always be the costly class, and the same cost asymmetry is preserved throughout the whole learning process.

-   In Cost-Sensitive AdaBoost cost asymmetry changes. While the classifier is wrong, positives are the costly class (learning is positive-driven), but when classification is correct, negatives are prevalent (learning is negative-driven). The more accurate the classifier obtained is, the more costly will be negatives over positives in subsequent training rounds.

In terms of training error, these differences seem to be anecdotal, since the change of class prevalence occurs once the classifier succeeds for each example. However, what is really relevant, is the effect in terms of generalization error: when the classifier works on unseen instances it will make mistakes and it is essential, from a cost-sensitive perspective, to characterize which class is the most prone to errors and to what extent.

As the iterative training process progresses, the performance scores associated to the training examples tend to increase, and their respective losses tend to decrease moving along the Y axis on Figures \[csb\_bound\_fig\] and \[cgb\_bound\_fig\], so, the more rounds we train, the more on the right of these figures we will be. In the case of Cost-Sensitive AdaBoost this trend will increasingly emphasize negatives at the expense of positives, while Cost-Generalized AdaBoost keeps the ratio between classes intact throughout the whole learning process. Thus, due to its changing emphasis, Cost-Sensitive AdaBoost may run the risk of obtaining classifiers in which the supposed costly class is the most prone to errors: just the opposite of what was originally intended!

In the companion paper of the series [@LandesaAlba??b] we will see empirical evidences confirming this *asymmetry swapping* behavior that, by definition, is expected to be more noticeable the closer the system is to overfitting, but that may have an implicit detrimental effect on the performance reached by all classifiers trained by Cost-Sensitive AdaBoost.

### Statistical View of Boosting {#subsubsec:statistical_cmp}

Instead of the exponential error bound minimization perspective that originally gave rise to AdaBoost (and that also is the derivation core of Cost-Generalized AdaBoost and AdaBoostDB) we will now adopt a different point of view: the Statistical View of Boosting [@Friedman00], the other major analytical framework to interpret and derive AdaBoost that, in addition, is the foundation of Cost-Sensitive AdaBoost.

As we have seen in Section \[subsec:Statistical View\], from the Statistical View of Boosting perspective, AdaBoost can be interpreted as an algorithm that iteratively builds an additive regression model based on the following loss function:

$$\label{loss_ab_eqn}
l_{AB}(f(\mathbf{x}),y)=\exp\left(-yf(\mathbf{x})\right)$$

From that loss, an associated risk function $J_{AB}(f(\mathbf{x}))$ (the expected loss) is defined:

$$\label{risk_ab_eqn}
\begin{split}
J_{AB}(f(\mathbf{x}))&=\E\left[l_{AB}(f(\mathbf{x}),y)\right]\\
&=\Prob\left(y=1|\mathbf{x}\right)\exp(-f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)\exp(f(\mathbf{x}))
\end{split}$$

If we minimize that risk we will obtain the optimal predictor $f_{AB}(\mathbf{x})$, that turns out to be the symmetric logistic transform of $\Prob\left(y=1|\mathbf{x}\right)$.

$$\label{min_ab_eqn}
f_{AB}(\mathbf{x})=\dfrac{1}{2}\log\dfrac{\Prob\left(y=1|\mathbf{x}\right)}{\Prob\left(y=-1|\mathbf{x}\right)}$$

AdaBoost is geared to approximate, in an additive way, that optimal predictor without embedded costs. Thus, the obtained model will be cost-insensitive, only depending on the likelihood of each class (see Figure \[stat\_cmp\_ab\_fig\]).

![Risk minimizing function (optimal predictor) for AdaBoost ($f_{AB}(\mathbf{x})$). It only depends on the likelihood of each class.[]{data-label="stat_cmp_ab_fig"}](Fig095a.pdf){width="7.5cm"}

In the case of Cost-Generalized AdaBoost, from this same perspective, we will have a loss function in which costs are included as modulators of the exponentials.

$$\label{loss_cga_eqn}
l_{CGA}(f(\mathbf{x}),y)=\llbracket y=1 \rrbracket C_{P} \exp(-f(\mathbf{x})) + \llbracket y=-1 \rrbracket C_{N} \exp(f(\mathbf{x}))$$

Thus, as explained in Section \[subsubsec:weight\_cost\_sensitive\], the respective risk function $J_{CGA}(f(\mathbf{x}))$ and its minimizer $f_{CGA}(\mathbf{x})$ will be the following ones:

$$\label{risk_cga_eqn}
\begin{split}
J_{CGA}(f(\mathbf{x}))&=\E\left[l_{CGA}(f(\mathbf{x}),y)\right]\\
&=\Prob\left(y=1|\mathbf{x}\right)C_{P}\exp(-f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)C_{N}\exp(f(\mathbf{x}))
\end{split}$$

$$\label{min_cga_eqn}
f_{CGA}(\mathbf{x})=\dfrac{1}{2}\log\left(\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}\right)$$

As can be seen, now we have a cost-sensitive risk function with a cost-sensitive minimizer gearing to an optimal predictor $f_{CGA}(\mathbf{x})$ based on the asymmetric logistic transform of $\Prob\left(y=1|\mathbf{x}\right)$. Thus, in contrast to AdaBoost, the model pursued by Cost-Generalized AdaBoost will not exclusively depend on the likelihood of each class, but also on the related costs.

![Risk minimizing function (optimal predictor) for Cost-Generalized AdaBoost ($f_{CGA}(\mathbf{x})$). It depends on the likelihood of each class and on the related costs, having a homogeneous and continuous cost-sensitive behavior for whatever likelihood.[]{data-label="stat_cmp_cga_fig"}](Fig095b.pdf){width="7.5cm"}

On the other hand, the loss function of Cost-Sensitive AdaBoost embeds the costs inside the exponents $$\label{loss_csa_eqn}
l_{CSA}(f(\mathbf{x}),y)=\llbracket y=1 \rrbracket \exp(-C_{P} f(\mathbf{x})) + \llbracket y=-1 \rrbracket \exp(C_{N}f(\mathbf{x}))$$ so the risk function and its associated minimizer will be as follows (see Section \[subsubsec:weight\_cost\_sensitive\]): $$\label{risk_csa_eqn}
\begin{split}
J_{CSA}(f(\mathbf{x}))&=\E\left[l_{CSA}(f(\mathbf{x}),y)\right]\\
&=\Prob\left(y=1|\mathbf{x}\right)\exp(-C_{P}f(\mathbf{x}))+\Prob\left(y=-1|\mathbf{x}\right)\exp(C_{N}f(\mathbf{x}))
\end{split}$$ $$\label{min_csa_eqn}
f_{CSA}(\mathbf{x})=\dfrac{1}{C_{P}+C_{N}}\log\left(\dfrac{C_{P}\Prob\left(y=1|\mathbf{x}\right)}{C_{N}\Prob\left(y=-1|\mathbf{x}\right)}\right)$$

Then, Cost-Sensitive AdaBoost is also aimed to fit a model based on the asymmetric logistic transform of $\Prob\left(y=1|\mathbf{x}\right)$, depending both on the likelihood of each class as well as on the related costs (see Figure \[stat\_cmp\_csa\_fig\]).

![Risk minimizing function (optimal predictor) for Cost-Sensitive AdaBoost ($f_{CSA}(\mathbf{x})$). It depends on the likelihood of each class and on the related costs, but in this case the cost-sensitive behavior is not homogeneous with respect to likelihood (solutions for different costs cross each other depending on $\Prob\left(y=1|\mathbf{x}\right)$).[]{data-label="stat_cmp_csa_fig"}](Fig095c.pdf){width="7.5cm"}

Notwithstanding, the optimal predictors guiding Cost-Sensitive AdaBoost and Cost-Generalized AdaBoost, despite being both cost-sensitive, have different equations. Such differences become apparent in their graphic representations (see Figures \[stat\_cmp\_cga\_fig\] and \[stat\_cmp\_csa\_fig\]).

To delve into the consequences of these differences, we will analyze the optimal predictors of Cost-Generalized AdaBoost and Cost-Sensitive AdaBoost as functions depending on two magnitudes: likelihood and cost asymmetry [^3]. In Figure \[stat\_cmp\_cgacsamap\_fig\] we have represented the outputs of the optimal predictors as colormaps (we have used isolines for the sake of clarity) onto the plane defined by the likelihood and the cost asymmetry. As can be seen, the optimal predictor of Cost-Generalized AdaBoost (Figure \[stat\_cmp\_cgacsamap\_fig\]a) obtains higher predictor values for increasing $\Prob\left(y=1|\mathbf{x}\right)$ and increasing $C_P$ (vice versa for negatives). However, that is not the case for Cost-Sensitive AdaBoost (Figure \[stat\_cmp\_cgacsamap\_fig\]b) where, for a given likelihood, we can find lower predictor outputs for increasing positive costs (and vice versa for negatives). This inhomogeneous behavior can explain the *asymmetry swapping* effect we have commented in Section \[subsubsec:error\_bound\_cmp\], and to which we will come back in the companion paper of the series [@LandesaAlba??b] when analyzing the experimental behavior of Cost-Sensitive AdaBoost.

[ \[training\_set\_nonover\_fig\] ![Isolines of the optimal predictors for Cost-Generalized AdaBoost (a), and Cost-Sensitive AdaBoost (b), with respect to the likelihood ($\Prob\left(y=1|\mathbf{x}\right)$) and the normalized cost asymmetry ($\gamma=C_P/(C_P+C_N)$).[]{data-label="stat_cmp_cgacsamap_fig"}](Fig095d1.pdf "fig:"){width="5.5cm"} ]{} [ \[training\_classifiers\_nonover\_fig\] ![Isolines of the optimal predictors for Cost-Generalized AdaBoost (a), and Cost-Sensitive AdaBoost (b), with respect to the likelihood ($\Prob\left(y=1|\mathbf{x}\right)$) and the normalized cost asymmetry ($\gamma=C_P/(C_P+C_N)$).[]{data-label="stat_cmp_cgacsamap_fig"}](Fig095d2.pdf "fig:"){width="5.5cm"} ]{}

Summary and Conclusions {#sec:Conclusions1}
=======================

In this first paper of the series we have introduced our working scenario, presenting the algorithms under study (AdaBoost with threshold modification [@ViolaJones04]; AsymBoost [@ViolaJones02]; AdaCost [@Fan99]; CSB0, CSB1 and CSB2 [@Ting98; @Ting00]; AdaC1, AdaC2 and AdaC3 [@Sun05; @Sun07]; Cost-Sensitive AdaBoost [@MasnadiVasconcelos07; @MasnadiVasconcelos11]; AdaBoostDB [@LandesaAlba13]; and Cost-Generalized AdaBoost [@LandesaAlba12]) in a homogeneous notational framework and proposing a clustering scheme for them based on the way asymmetry is inserted in the learning process: *theoretically*, *heuristically* or *a posteriori*. Then, for those algorithms with a fully theoretical derivation, we performed a thorough theoretical analysis and discussion, adopting the different perspectives that have been used to explain and derive the related approaches in the literature (Error Bound Minimization perspective [@SchapireSinger99] and Statistical View of Boosting [@Friedman00]).

The presented analysis clearly shows that the asymmetric weight initialization mechanism used by Cost-Generalized AdaBoost, from whatever point of view, is definitely a valid mechanism to build theoretically sound cost-sensitive boosted classifiers, despite having being recurrently overlooked or rejected in many previous works (e.g. [@Fan99; @Ting00; @ViolaJones02; @MasnadiVasconcelos07; @MasnadiVasconcelos11]). In addition, and besides being the simplest algorithm, Cost-Generalized AdaBoost exhibits the most consistent error bound definition and it is able to preserve the class-dependent loss ratio regardless of the training round whereas Cost-Sensitive AdaBoost and AdaBoostDB, the other theoretical alternatives, may end up emphasizing the least costly class.

After this purely theoretical study, an empirical analysis of the different approaches, also including the non-fully-theoretical methods (a posteriori and heuristic), is needed to reach global conclusions and culminate the analysis we have started in this paper. Such experimental part can be found in the next article of the series: “” [@LandesaAlba??b].

[^1]: Notation: $\llbracket a \rrbracket$ is $1$ when $a$ is true and $0$ otherwise.

[^2]: As analyzed in Appendix \[app:weight\], the way asymmetry is applied across the different boosting variants covered by the Cost-Sensitive Boosting framework [@MasnadiVasconcelos11] is not homogeneus either. In fact, despite having discarded cost-proportionate weight initialization as a valid method, one of the algorithms (Cost-Sensitive LogitBoost) proposed in the same work is actually based on that strategy.

[^3]: In the case of Cost-Sensitive AdaBoost (and AdaBoostDB) we can actually distinguish three different involved magnitudes (likelihood, cost of positives and cost of negatives), since the optimal predictor changes when costs are multiplied by a positive factor. This behavior (that does not happen for Cost-Generalized AdaBoost) violates the rules of the cost matrix [@Elkan01] explained at the beginning of Section \[sec:CSvar\]. In order to tackle this problem for our analysis, we have restricted the possible costs to combinations $(C_P, C_N)$ in which one of the coefficients is always 1, and the other one is $\geq1$. This decision allows us to homogeneously interpret the scenarios in which negatives are the costliest class as label inversions.
