
\section{Introduction} \label{sec:intro}

Boosting, and in particular AdaBoost \cite{schapire2012,freund1996,freund1997}, is an effective method of aggregating classifiers. 
AdaBoost produces a reliable binary classifier and often avoids overfitting.
Nevertheless, it can be sensitive to ``noisy'' data and may severely underperform as a result.
In this paper, we embed binary classification in a Bayesian model and show how it interfaces with the boosting paradigm.
With this model, we can address the vulnerability to noise in a principled way.

Real-world data will almost always include noise, even with binary labels.
In the U.S. Presidential election of 2000, the country was kept in suspense for more than a month while votes were recounted in the state of Florida.
During the recount it had become apparent that the use of the ``butterfly ballot'' had confused voters \cite{toobin2002}.
Probabilistically, we can model a confused voter as one who casts a vote that is \textit{independent} of his/her actual intention.
These votes---borne out of confusion---are considered ``noisy'' and any attempt to learn a voter-to-vote connection, e.g., via boosting, becomes difficult.
However, this does not preclude the extraction of important noise information.
If we can \textit{detect and quantify} the noise properties of a given dataset, then it should be reflected in our expectations of constructing a good classifier.  

In addressing label noise, we have chosen to interpret aggregating classifiers in a fully-Bayesian model.
Once in place, this model lets us incorporate additional latent variables to account for noise.
In our context, noise means that the true label is ignored and randomly reassigned, i.e., it may be inverted.
A learning algorithm such as AdaBoost is sensitive to this type of label perturbation because it focuses on the examples that pose a greater difficulty of classification.
Using this augmented model, we construct an algorithm that performs approximate inference of the posterior distribution associated with the latent variables.
Although the intent is inference, the algorithm is able to produce a binary classifier accompanied by noise statistics that reflect the quality of the learned classifier.
We also show that the algorithm---in its simplest form---reduces to a smoothed version of AdaBoost. 

In developing a Bayesian model for aggregating binary classifiers, we begin with the logistic regression model proposed by \cite{friedman2000}.
Given a set of base classifiers, the latent variables of the model are the weights placed on these base classifiers. 
We then introduce variables to account for label perturbations.
Finally, we use variational inference to estimate the posterior distributions.

Our ideas lead to a new boosting-like algorithm called \textit{VIBoost}---boosting stemming from \underline{v}ariational \underline{i}nference. 
AdaBoost employs a greedy search for incorporating new base classifiers.
Similarly, in VIBoost each main-loop iteration introduces a new base classifier, which induces a new model.
With this new model, variational inference is applied using previous values for a warm start.  
In the process, noise statistics are cultivated.
Our experiments reveal that VIBoost performs on par with AdaBoost and supplies meaningful characterizations of the label perturbations.

Much has been done to cast boosting in a statistical setting.
Friedman~et~al.~\cite{friedman2000} leveraged the logistic regression model and then used a functional gradient to derive a boosting update.
Collins~et~al.~\cite{collins2002} used information geometry to derive AdaBoost and algorithms emerged with exponential and logistic loss objectives. 
Lebanon~\&~Lafferty~\cite{lebanon2002} solidified the relationship between AdaBoost and maximum likelihood via duality.
These ideas led to a Bayesian perspective of boosting and provided a way to incorporate prior knowledge \cite{schapire2002}.

There have been many approaches for handling noise.
For example, Servedio addressed label noise in a PAC learning framework and developed SmoothBoost \cite{servedio2003}. 
Through a statistical formulation, Krause~\&~Singer~\cite{krause2004} addressed noise in the context of symmetric, random label inversions, and devised algorithms to alleviate the resulting adverse effects.
In one of these algorithms they used expectation maximization to construct a classifier while simultaneously updating a noise parameter.
Building on this work, we use variational inference and address label noise in the process.

The paper is organized as follows:
the initial groundwork for the Bayesian model is given in \S\ref{sec:core}.
In \S\ref{sec:logistic} we introduce two probability distributions that will play a role in the model. 
The proposed model is presented in \S\ref{sec:model} and variational inference is applied in \S\ref{sec:vi}.
We discuss the connection to AdaBoost in \S\ref{sec:adaboost}.
We give experimental results in \S\ref{sec:exp} and we conclude in \S\ref{sec:con}.


\section{The Core Model} \label{sec:core}

In the binary classification problem we are given a set of $N$ labeled examples $\{(\mathbf{x}_n,y_n)\}_{n=1}^N$.
Each example is an element of some space $\mathcal{X}$ and the labels are elements of $\{-1,+1\}$.
In addition to the labeled examples, we also have a set of $M$ base classifiers $\mathcal{F} = \{f_1,\ldots,f_M\}$.
Each element of $\mathcal{F}$ is a function that maps $\mathcal{X}$ to $\{-1,+1\}$.
Additionally, we assume that (a) $h \in \mathcal{F} \Rightarrow -h \notin \mathcal{F}$ and (b) $h_1, h_2 \in \mathcal{F} \Rightarrow \exists \ i \in \{1,\ldots,N\}$ such that $h_1(\mathbf{x}_i) \neq h_2(\mathbf{x}_i)$.
These assumptions ensure a finite number of classifiers and prevent identifiability problems.

For a fixed $\mathbf{x} \in \mathcal{X}$, suppose the logarithm of the ``$+1$''-to-``$-1$'' label odds is given by $F(\mathbf{x}) = \log \frac{ p(y=+1 \mid \mathbf{x}) }{ p(y=-1 \mid \mathbf{x}) }$.
Thus, we can form the conditional probability mass function for the labels as ${ p(y \mid \mathbf{x}, F) = \frac{ 1 }{ 1 + \exp(-y F(\mathbf{x})) } }$.
 
A label sampled in this way shall be called a \textit{true} label.
Logistic regression models the spatially-variant log-odds-ratio as a weighted sum over all base classifiers, i.e.,  $F(\mathbf{x}) = \sum_{m=1}^M c_m f_m(\mathbf{x})$. 

Consider a model defined by the following generative process:
\begin{samepage}
\begin{ENUM}
  \item Draw $c_m \stackrel{\text{iid}}{\sim} \mathcal{P}_C$ \ ($m=1,\ldots,M$) \ .
  \item Construct $F = \sum_{m=1}^M c_m f_m$ \ .
  \item Draw $\mathbf{x}_{1:N}$ independently according to some distribution over $\mathcal{X}$ \ .
  \item Draw $y_n \in \{-1,+1\}$ independently according to ${  p(y_n \mid \mathbf{x}_n, F) = \frac{1}{1 + \exp[-y_n F(\mathbf{x}_n) ]} }$ \ . 



\end{ENUM}
\end{samepage}
The graphical model is shown in Figure~\ref{fig:core}.

The latent variables are the base classifier weights $c_{1:M}$.
Using the labeled examples, we seek the posterior distribution over the weights.
A similar approach was posed by Minka \cite{minka2001} with the Bayes Point Machine \cite{herbrich2001}.  
In contrast with our work, the author considered (i) a linear classifier without the notion of base classifiers, (ii) expectation propagation as opposed to variational inference, and (iii) a Gaussian prior for the weights.

The posterior distribution over the weights reflects a compromise of the observed data (\,$\{\mathbf{x}_n,y_n\}_{n=1}^N$\,) with our prior beliefs (\,$\mathcal{P}_C$\,).
It also has the potential of yielding a classifier via the $M$-dimensional mean or mode, for example.
Combining prior beliefs with observed data is made easier through conjugacy, which is how we propose a distribution for $\mathcal{P}_C$. 
This is the subject of the next section.


\begin{figure}[t!]
\begin{minipage}[b]{0.48\linewidth}
\centering
                \includegraphics[width=0.50\columnwidth]{coregraphicalmodel8.pdf}
                \caption{The core graphical model for the boosting problem. Each label depends on the example and log-odds-ratio function. The only latent variables are the base classifier weights.}
                \label{fig:core}
\end{minipage}
\hspace{0.4cm}
\begin{minipage}[b]{0.48\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{logoneplusz.pdf}
                \caption{For a given versatile logistic with unit multiplicities, the negative logarithm of one of the product terms is shown above ($\beta\!=\!1$ , $\gamma\!=\!2$). Each curve of this form is tightly lower-bounded by a piecewise-linear function with one knot at $z\!=\!\gamma$. The slopes are $0$ and $\beta$.}
                \label{fig:log1pez}
\end{minipage}
\end{figure}

\section{The Versatile Logistic \& Binary Logistic Distributions} \label{sec:logistic}

We use two conjugate distributions to specify the model described in Figure~\ref{fig:core}.
The first distribution is used as a prior for the weights $c_{1:M}$, and the second is associated with label generation.
For vectors ${\boldsymbol{\beta}},{\boldsymbol{\gamma}} \in {\mathbb{R}}^K$ and ${\boldsymbol{\mu}} \in {\mathbb{R}}^K_+$, we define the density over the reals
\begin{align}
  p(z) &\propto \textstyle{\prod_{k=1}^K} \left( \frac{1}{1+\exp[\beta_k (z - \gamma_k)]} \right)^{\mu_k}
  \label{eq:vlog}
\end{align}
to be the \textit{Versatile Logistic Distribution}---written $\text{v-Log}({\boldsymbol{\beta}},{\boldsymbol{\gamma}},{\boldsymbol{\mu}})$--- with \textit{slope vector} ${\boldsymbol{\beta}}$, \textit{knot vector} ${\boldsymbol{\gamma}}$, and \textit{multiplicity vector} ${\boldsymbol{\mu}}$.
Figure~\ref{fig:log1pez} provides the motivation behind this nomenclature.
Define $\bar{\mathbf{u}} \triangleq \left[ \begin{smallmatrix} +1 \\ -1 \end{smallmatrix} \right] \in {\mathbb{R}}^2$.
A familiar density is $\text{v-Log}(\bar{\mathbf{u}},{\mathbf{0}},{\mathbf{1}})$, which is a logistic distribution.

The density described in \eqref{eq:vlog} is valid if and only if there exists both a positive and negative slope with corresponding positive multiplicity.
Consequently, we must have $K \geq 2$.
Additionally, this distribution is unimodal, so it is reasonable to estimate its mean with an approximate mode.
We prove these facts in \S\ref{supp:sec:vlog}.
The product represented in \eqref{eq:vlog} relates to a Product of Experts \cite{hinton2002}; however, each factor by itself does not correspond to a valid density.

We now define a probability mass function for the binary random variable $Y$ taking values in $\{-1,+1\}$. 
For scalars $z$, $\beta$, and $\gamma$ we define 
\begin{align}
  p(y) &= \frac{1}{1 + \exp[-y \beta (z - \gamma) ]}
  \label{eq:binarylogistic}
\end{align}
to be the corresponding \textit{Binary Logistic Distribution}, written $\text{b-Log}(z,\beta,\gamma)$.
In comparing \eqref{eq:binarylogistic} to label generation in our model, we see that $\beta$ and $\gamma$ encode base classifier information.   
The versatile logistic and binary logistic are conjugate in the following way:
if $z \sim \text{v-Log}({\boldsymbol{\beta}},{\boldsymbol{\gamma}},{\boldsymbol{\mu}})$ and $y_n | z \sim \text{b-Log}(z,\theta_n,\phi_n)$---drawn independently for $n=1,\ldots,N$---then the posterior of $z$ given $y_{1:N}$ is also a versatile logistic with parameters
\begin{align}
  {\boldsymbol{\beta}}' &= [ \beta_1,\ldots,\beta_K,-y_1\theta_1,\ldots,-y_N\theta_N]^T \in {\mathbb{R}}^{K+N} \\
  {\boldsymbol{\gamma}}' &= [ \gamma_1,\ldots,\gamma_K,\phi_1,\ldots,\phi_N]^T \in {\mathbb{R}}^{K+N} \\
  {\boldsymbol{\mu}}' &= [ \mu_1,\ldots,\mu_K,1,\ldots,1]^T \in {\mathbb{R}}^{K+N} \ .
\end{align}
In the binary classification problem, the b-Log--v-Log conjugacy relationship helps with posterior inference.
By construction, the posterior distribution of the weights is a versatile logistic.



\begin{figure}[t!]
\begin{minipage}[b]{0.48\linewidth}
\centering
                \includegraphics[width=0.95\columnwidth]{graphicalmodel5.pdf}
                \caption{The graphical model for Bayesian boosting.}
                \label{fig:gm}
\end{minipage}
\hspace{0.4cm}
\begin{minipage}[b]{0.48\linewidth}
\centering
                \includegraphics[width=0.95\columnwidth]{graphicalmodel8.pdf}
                \caption{The dynamic graphical model for Bayesian boosting.}
                \label{fig:gmu}
\end{minipage}
\end{figure}


\section{Incorporating Noise} \label{sec:model}

We will now build upon the model presented in \S\ref{sec:core}.
Suppose we fix an instance $\mathbf{x} \in \mathcal{X}$ and repeatedly generate labels from $p(y \mid \mathbf{x} , F)$.
If the labels are \textit{true}, then the empirical ratio of plus-to-minus labels will converge to $\exp[F(\mathbf{x})]$, i.e., the odds ratio.

On the other hand, according to our model, if the labels are \textit{noisy}, the empirical odds ratio converges to some fixed value, which is independent of $\mathbf{x}$. 
Let $e^\xi$ be this noise-related odds ratio.
Equivalently, $\xi$ is an instance-independent, static log-odds-ratio, which we refer to as the \textit{noise grade}.
For example, noise grades of $-\infty$, $0$, and $+\infty$, translate to random label assignments of $+1$ with probability $0$, $1/2$, and $1$, respectively.

Let $w$ take on values in $\{0,1\}$ and encode whether a label is true or noisy.
We can merge the two label types into the following conditional label probability:
\begin{align}
 
  \!\!\!
  p(y \mid w, \mathbf{x}, \xi, F) &= \frac{1}{1+\exp[-y(w F(\mathbf{x}) + (1{-}w) \xi)]}
  = \frac{w}{1+\exp[-y F(\mathbf{x})]} + \frac{1{-}w}{1 + \exp[-y \xi]} .
  \label{eq:merge}
\end{align}
The role of $w$ selects the label type: true or noisy.
Treating $w$ as a latent variable, we embellish the model of \S\ref{sec:core}:
\begin{samepage}
\begin{ENUM}
  \item Draw $c_m \stackrel{\text{iid}}{\sim} \text{v-Log}(\bar{\mathbf{u}},{\mathbf{0}},\mu_0 {\mathbf{1}})$\ ($m=1,\ldots,M$) \ .
  \item Construct $F = \sum_{m=1}^M c_m f_m$ \ .
  \item Draw $\mathbf{x}_{1:N}$ independently according to some distribution over $\mathcal{X}$ \ .
  \item Draw $\xi \sim \text{v-Log}(\bar{\mathbf{u}},{\mathbf{0}},\mu_0' {\mathbf{1}})$ \ .
  \item Draw $\theta \sim \text{Beta}(\zeta_1,\zeta_2)$ \ \ \ (${\boldsymbol{\zeta}} \in {\mathbb{R}}^2_+$) \ .
  \item Draw $w_n | \theta \stackrel{\text{iid}}{\sim} \text{Bernoulli}(\theta)$ \ ($n=1,\ldots,N$) \ .
  \item Draw $y_n \in \{-1,+1\}$ independently according to
	\begin{align}
	  p(y_n \mid w_n, \mathbf{x}_n, \xi, F) &=  \frac{1}{1+\exp[-y_n(w_{n}F(\mathbf{x}_n) + (1{-}w_{n})\xi)]}  \ .

	\end{align}
\end{ENUM}
\end{samepage}
There is now a prior assigned to $c_m$, and the new steps (4-6) model noise. 
The graphical model is depicted in Figure~\ref{fig:gm}.
Although not immediately apparent, this model subsumes label inversion as a form of noise (\S\ref{supp:sec:inversion}).

From the classification standpoint, the primary latent variables of the above generative process are still $c_{1:M}$, or the \textit{weights}.
The latent $w_{1:N}$, or \textit{type selectors}, are responsible for the type of label generated. 
They are drawn independently from $\theta$, the \textit{type prior}.
We can reason that $\theta/(1-\theta)$ represents a signal-to-noise ratio (SNR).
This stems from the expected value of $N\theta$ true labels and $N(1{-}\theta)$ noisy labels (see \S\ref{supp:sec:inversion} for full details).
Alternatively, we can use the prior of $\theta$ for the SNR estimate, yielding $\mathbb{E}\{\Theta\}/\mathbb{E}\{1{-}\Theta\} = \zeta_1/\zeta_2$.  


\section{Variational Inference} \label{sec:vi}

With a Bayesian model in place, our focus turns to the posterior distribution of the latent variables.
This allows us to construct a classifier by estimating the mean or mode of the posterior weights ($c_m$).
We accomplish this with stagewise variational inference.\footnote{The common approach in this situation is to use a Gibbs sampler. The Gibbs sampler for the graphical model of Figure~\ref{fig:gm} is given in \S\ref{supp:sec:gibbs}. We used Adaptive Rejection Sampling \cite{gilks1992} to sample a v-Log. In practice, this approach was too time consuming, which is why we turned to inference.}


\paragraph{Full Variational Inference.}

Before motivating our stagewise approach, we first review variational inference.
In our model we have the observed variables $\langle \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} \rangle$ and the latent variables $\langle c_{1:M} , \xi , w_{1:N} , \theta \rangle$.
We are interested in the posterior $p(c_{1:M} , \xi , w_{1:N} , \theta \,|\, \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} )$, which is proportional to the joint $p(c_{1:M} , \xi , w_{1:N} , \theta , \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} )$.
In variational inference, we introduce a distribution $q(c_{1:M} , \xi , w_{1:N} , \theta)$ to bound the log of the marginal probability of the observations \cite{wainwright2008},
\begin{align}
  \!\!
   \log  p(  \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} \! ) 
  
	  &\!\geq\! \textstyle{\int} q(c_{1:M} , \xi , w_{1:N} , \theta) \log p(c_{1:M} , \xi , w_{1:N} , \theta , \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} \! ) \text{d} c_{1:M} \text{d} \xi \text{d} w_{1:N} \text{d} \theta \notag \\ 
  & \qquad \quad - \textstyle{\int} q(c_{1:M} , \xi , w_{1:N} , \theta) \log q(c_{1:M} , \xi , w_{1:N} , \theta) \text{d} c_{1:M} \text{d} \xi \text{d} w_{1:N} \text{d} \theta \label{eq:elbo}
				  \ .
\end{align}
The right-hand side of \eqref{eq:elbo} is referred to as the \underline{e}vidence \underline{l}ower \underline{bo}und (ELBO).
Using the KL-divergence, we can also write
\begin{align}
 
 
\log  p(  \mathcal{F} , \mathbf{x}_{1:N} , y_{1:N} \! ) = \textsc{kl}(\ q(c_{1:M} , \xi , w_{1:N} , \theta) \parallel \text{posterior}\ ) + \textsc{elbo} \ .
\end{align}
The KL divergence provides a measure of closeness between the auxiliary distribution and the posterior.
We maximize the ELBO with respect to the parameters of $q$, thereby minimizing the KL divergence to the posterior.
We use \textit{mean-field variational inference}, i.e., we assume a factorized $q$:
\begin{align}
  q(c_{1:M} , \xi , w_{1:N} , \theta) = \textstyle{\prod_{m=1}^M} q(c_m) \cdot q(\xi) \cdot \textstyle{\prod_{n=1}^N} q(w_n) \cdot q(\theta) \ .
  \label{eq:factor}
\end{align}
Each component of the factorized variational distribution has a form and variational parameters.
For example, a reasonable form of $q(c_m)$ is a versatile logistic with variational parameters given by some slope, knot and weight vectors.
Typically, we optimize the parameters with coordinate ascent, updating each in turn, holding the others fixed.  
In our model, this yields the following updates \cite{bishop2006}:
\begin{align}
  \log q^*(c_m) &\leftarrow \mathbb{E}_q [ \log p( C_{1:m-1}, c_m, C_{m+1:M}, \Xi, W_{1:N}, \Theta, \mathcal{F}, \mathbf{x}_{1:N}, y_{1:N} ) ] +\text{const} \label{eq:qc} \\
  \log q^*(\xi) &\leftarrow \mathbb{E}_q [ \log p( C_{1:M}, \xi, W_{1:N}, \Theta, \mathcal{F}, \mathbf{x}_{1:N}, y_{1:N} ) ] +\text{const} \\
  \log q^*(w_n) &\leftarrow \mathbb{E}_q [ \log p( C_{1:M}, \Xi, W_{1:n-1}, w_n, W_{n+1:N}, \Theta, \mathcal{F}, \mathbf{x}_{1:N}, y_{1:N} ) ] +\text{const} \\
  \log q^*(\theta) &\leftarrow \mathbb{E}_q [ \log p( C_{1:M}, \Xi, W_{1:N}, \theta, \mathcal{F}, \mathbf{x}_{1:N}, y_{1:N} ) ] +\text{const}  \ .
\end{align}
Each term on the right is a leave-one-out expectation over the latent variables, resulting in a function of the corresponding left-out latent variable.
Running the variational inference algorithm repeatedly cycles through these updates.


This algorithm is not convenient.
The chosen form of the approximate posterior weight distributions is a versatile logistic.
From conjugacy, the number of parameters required to specify each distribution is linear in the number of examples ($N$).
Additionally, we hope to use a large number of base classifiers, even for small datasets.
Thus, for our classification problem, cycling through all auxiliary weight distributions is impractical because integrating over the weights is too much of a computational burden.

\begin{algorithm}[tb]
   \caption{VIBoost}
   \label{alg:viboost}
\begin{algorithmic}
   \STATE {\bfseries Input:} $\{(\mathbf{x}_n,y_n)\}_{n=1}^N$, $\mathcal{F}$, $\mu_0\in{\mathbb{R}}_+$, $\mu_0'\in{\mathbb{R}}_+$, ${\boldsymbol{\zeta}}\in{\mathbb{R}}_+^2$
  
   \STATE Initialize $H : \mathcal{X} \to \{-1,+1\}$ to the zero function
   \STATE Initialize ${\boldsymbol{\eta}} \in {\mathbb{R}}_+^2$, ${\boldsymbol{\omega}} \in {\mathbb{R}}_+^2$, and ${\boldsymbol{\phi}} \in [0,1]^N$
   \STATE Define ${\boldsymbol{\beta}}(h) \triangleq [+1,-1,-y_1 h(\mathbf{x}_1),\ldots,-y_N h(\mathbf{x}_N)]^T$
   \STATE Define ${\boldsymbol{\gamma}}(H,h) \triangleq [0,0,-H(\mathbf{x}_1) h(\mathbf{x}_1),\ldots,-H(\mathbf{x}_N) h(\mathbf{x}_N)]^T$
   \STATE Define ${\boldsymbol{\mu}}({\boldsymbol{\phi}}) \triangleq [\mu_0,\mu_0,\phi_{1},\ldots,\phi_{N}]^T$
   \FOR{$t=1$ {\bfseries to} $T$}
   \vskip 0.4ex
  
   \STATE $h_t \leftarrow \argmax_{h \in \mathcal{F}} \ \vert \text{Mode}[\text{v-Log}({\boldsymbol{\beta}}(h),{\boldsymbol{\gamma}}(H,h),{\boldsymbol{\mu}}({\boldsymbol{\phi}}))] \vert$
   \vskip 0.4ex
   \WHILE{\textsc{ELBO} increases significantly}
   \vskip 0.4ex
   \STATE $\alpha_t \leftarrow \text{Mode}[\text{v-Log}({\boldsymbol{\beta}}(h_t),{\boldsymbol{\gamma}}(H,h_t),{\boldsymbol{\mu}}({\boldsymbol{\phi}}))]$
   \vskip 0.4ex
   \STATE $\omega_1 \leftarrow \mu_0' + \textstyle{\sum_{n=1}^N} (1-\phi_{n}) \mathds{1}} %\text{I\!\!\!\!1}\{y_n = -1\}$ 
   \vskip 0.4ex
   \STATE $\omega_2 \leftarrow \mu_0' + \textstyle{\sum_{n=1}^N} (1-\phi_{n}) \mathds{1}} %\text{I\!\!\!\!1}\{y_n = +1\}$ 
   \vskip 0.4ex
   \STATE $\kappa_n \stackrel{1:N}{\leftarrow} \displaystyle{\frac{ \exp\left[ \uppsi(\eta_1) - \uppsi(\eta_2) + \uppsi(\omega_0) - \uppsi(\omega_2)\mathds{1}} %\text{I\!\!\!\!1}{\{y_n=+1\}} - \uppsi(\omega_1)\mathds{1}} %\text{I\!\!\!\!1}{\{y_n=-1\}} \right] }{ 1 + \exp[-y_n(H(\mathbf{x}_n) + \alpha_t h_t(\mathbf{x}_n))]}}$
   \vskip 0.4ex
   \STATE $\phi_{n} \stackrel{1:N}{\leftarrow} \kappa_n / (1 + \kappa_n)$
   \vskip 0.4ex
   \STATE $\eta_1 \leftarrow \zeta_1 + \textstyle{\sum_{n=1}^N} \phi_{n}$
   \vskip 0.4ex
   \STATE $\eta_2 \leftarrow \zeta_2 + \textstyle{\sum_{n=1}^N} (1-\phi_{n})$
   \vskip 0.4ex
   \ENDWHILE
   \STATE $H \leftarrow H + \alpha_t h_t$
   \ENDFOR
   \STATE {\bfseries Output:} classifier\ \ $\sign\{H(\cdot)\}$
\end{algorithmic}
\end{algorithm}

\paragraph{Stagewise Variational Inference.}

To address these issues, we propose a dynamic model over the current static one: with a current estimate of $F = \sum_m c_m f_m$, we introduce a single base classifier and then run variational inference on the latent $\langle c,\xi, w_{1:N}, \theta \rangle$.
The regression counterpart would be Forward Stagewise Regression, a greedy algorithm which finds a sparse subset of covariates and is structurally similar to AdaBoost \cite{friedman2009}.

In each main loop iteration, let $H(\cdot)$ be the current estimate of the true log-odds-ratio $F(\cdot)$ and suppose we have a ``promising'' candidate $h \in \mathcal{F}$ that we wish to merge with $H$.
This promising classifier is found greedily (details below) and, once found, becomes a fixed variable in the model.
Now, rather than $M$ latent weights, we have a single latent weight $c$ corresponding to $h$.
Every update of $H$ induces a new model to which we apply variational inference.
This new, time varying graphical model is featured in Figure~\ref{fig:gmu}.

Let $\mathcal{D}$ denote the evidence, i.e., the observed variables $\mathbf{x}_{1:N}$, $y_{1:N}$, $H$, and $h$.
At each stage we assume the following distributions:
\begin{align}
  p(c \mid \mathcal{D}) &\approx q( c \mid {\boldsymbol{\beta}},{\boldsymbol{\gamma}},{\boldsymbol{\mu}} ) 
                        \sim \text{v-Log}({\boldsymbol{\beta}},{\boldsymbol{\gamma}},{\boldsymbol{\mu}}) 
						&
  p(\xi \mid \mathcal{D}) &\approx q( \xi \mid {\boldsymbol{\omega}} )
                        \sim \text{v-Log}(\bar{\mathbf{u}},{\mathbf{0}},{\boldsymbol{\omega}}) \\
  p(w_n \mid \mathcal{D}) &\approx q( w_n \mid \phi_n )
                        \sim \text{Bernoulli}(\phi_n) 
						&
  p(\theta \mid \mathcal{D}) &\approx q( \theta \mid {\boldsymbol{\eta}} ) 
                        \sim \text{Beta}({\boldsymbol{\eta}}) \ .
\end{align}
 
 
 
   

   
 
 
	       
 
 
 
  
  

The variational updates and the ELBO are derived in \S\ref{supp:sec:vi} and \S\ref{supp:sec:elbo}, respectively.
The general approach is to isolate the terms of the log-likelihood that feature the variable of interest---all other terms will cancel after normalization and are extraneous.
We then take expectations and attempt to identify a distribution.

The resulting algorithm, \textit{VIBoost}, is presented in Algorithm~\ref{alg:viboost} (\ $\uppsi(\cdot)$ is the digamma function ).
Possible modifications include (a) fixing the number of variational inference iterations so that ELBO calculations are avoided, and (b) setting the $\alpha_t$ once and skipping its update in the variational inference loop.

We greedily select the next base classifier by finding the v-Log posterior with maximal mode.
A large mode suggests that the corresponding weight possesses discriminative classification strength.
We opted for the mode rather than the mean; we now justify this choice.

A v-Log distribution with more than two slope/knot/multiplicity terms has the advantage of being a one-dimensional density, but is cumbersome when evaluating statistics of interest.
Computing the normalization constant, mode and mean require iterative techniques, which can bog down any algorithm.
However, if we replace $\mu_k \log(1 + e^{\beta_k(z-\gamma_k)})$, a summand of the log-density, with the single-tail approximation $\mu_k e^{\beta_k \tau (z - \gamma_k)}$  ($\tau > 0$) we arrive at the modal estimate of
\begin{align}
  \textstyle{
  \alpha =
  \frac{1}{2\tau\beta} \log \left( \frac{ 
           \sum_{k:\beta_k<0} \mu_k e^{\tau\beta\gamma_k}
     }{ 
           \sum_{k:\beta_k>0} \mu_k e^{-\tau\beta\gamma_k}
		   } \right) } \ ,
		\label{eq:appxmode}
\end{align}
where $\beta = \vert \beta_k \vert$ is constant (\S\ref{supp:sec:cupdate} and \cite{friedman2000}).
For a unimodal distribution, this closed-form expression provides an efficient way of estimating expectations.
Thus, in avoiding numerical integration, Algorithm~\ref{alg:viboost} is performing approximate variational inference.




\section{Relation to AdaBoost} \label{sec:adaboost}

We now compare our algorithm to AdaBoost.
Consider the simpler model of \S\ref{sec:core}, a true-label dataset with prior assignments (Figure~\ref{fig:core}).
This leaves the greedy step of finding the maximal mode in Algorithm~\ref{alg:viboost} and updating $H$ without the variational inference.
We now investigate the approximation supplied by \eqref{eq:appxmode} with $\mu_0 = \tau=1$.
Let $Z=\sum_{n=1}^N e^{-y_n H(\mathbf{x}_n)}$ and $d_n=e^{-y_n H(\mathbf{x}_n)} /Z$ so that $\sum_{n=1}^N d_n=1$. 
The approximate mode $\alpha$ is
\begin{align}
  \textstyle{
  \frac{1}{2}
  \log \left( \frac{ 1/Z + (1 - \varepsilon) }{ 1/Z + \varepsilon } \right) }
  \ ,  \label{eq:1oz}
\end{align}
where $\varepsilon =  \sum_{n} d_n \mathds{1}} %\text{I\!\!\!\!1}\{h(\mathbf{x}_n) \neq y_n\} $ is a weighted error ascribed to the new classifier (\S\ref{supp:sec:modeappx}).
When compared to AdaBoost, the update is identical when the $1/Z$ term is not present.
Effectively, the $1/Z$ term results in a shrinkage of the assigned weights (see Figure~\ref{fig:1Z}).

The variable $Z$ is equal to the current exponential loss.
If $Z$ is small then $1/Z$ is large which leads to a dampened weight assignment (and vice versa).
Assuming the exponential loss decreases with more iterations, the algorithm acts like AdaBoost early on and then becomes more conservative with each iteration.
Quinlan \cite{quinlan1996} incorporated similar smoothing for AdaBoost and described it as ``necessarily ad-hoc''.
In the proposed model, this smoothing results from the prior assignment.
We also note that AdaBoost selects the base classifier that minimizes $\varepsilon$.
From \eqref{eq:1oz}, this coincides with the largest approximation-based mode

The slopes ${\boldsymbol{\beta}}(h)$ as defined in Algorithm~\ref{alg:viboost} contain individual [mis]matches of the base classifier with the labels, whereas the knots contain individual, weighted [mis]matches of the base classifier with the current log-odds-ratio estimate.
The prior effectively augments the data by inserting two phantom examples.
Each example lies in the zero level set of $H$ as indicated by a knot of $0$ ($H(\mathbf{x})h(\mathbf{x}) = 0 \Rightarrow H(\mathbf{x}) = 0$).
The slopes of $\pm 1$ presume that the base classifier succeeds in correctly labeling one of the pseudo-examples, while failing with the other. 

Finally, leveraging $d_{1:N}$ we can rewrite Algorithm~\ref{alg:viboost} to use the weighted error $\varepsilon$ rather than a mode search.
Using these errors for ranking the base classifiers---as done in AdaBoost---decreases computation time significantly when searching for a new candidate base classifier.
The greedy search in VIBoost would then closely match AdaBoost's in computation time, thereby leading to an efficient algorithm with a similar runtime to AdaBoost.




\begin{figure}[t]
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{oneoverz.pdf}
                \caption{\small The effects of the versatile logistic prior on classifier weights ($\mu_0\!=\!w_{n}\!=\!\tau\!=\!1$)}
                \label{fig:1Z}
\end{minipage}
\hspace{0.03\linewidth}
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{spamerr.pdf}
                \caption{\small Spam dataset, classification error \\ \ }
                \label{fig:spamerr}
\end{minipage}
\hspace{0.03\linewidth}
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{techerr.pdf}
                \caption{\small State dataset, classification error \\ \ }
                \label{fig:texterr}
\end{minipage}
\end{figure}


\section{Experiments}  \label{sec:exp}

We studied VIBoost on real and synthetic data.
We found that VIBoost works as well as AdaBoost for binary classification.
More importantly, we show that the variables accounting for label noise are a meaningful diagnostic of misfit.
For all experiments, our VIBoost initialization was $\mu_0\!=\!\mu'_0\!=\!\phi_{n}\!=\!\zeta_j\!=\!\eta_j\!=\!\tau\!=\!1$. 
Setting $\tau\!=\!1$ provides the closest means of comparison with AdaBoost. 
For all experiments we used decision stumps as our base classifiers.
Using the variational parameters of the type prior, we use $\eta_1/\eta_2$ for the SNR.
For the noise grade we use $\log(\omega_2/\omega_1)$, the mode associated with the approximate posterior.
All results presented are average values calculated over $40$ runs. 

As VIBoost outputs a classifier, we investigate classifier quality on two real-world, text datasets.
The first dataset is the $57$-feature \textit{spam} dataset \cite{ucimlr}.
With 6,401 examples, each run trained on a random $10\%$ and tested on the remaining $90\%$.  
The second dataset is a \textit{state} dataset \cite{gabrilovich2004} comprising 145 documents with 22,648 features (bag of words).
Instead of the word count, however, we used a present/absent binary value.
Each document relates to Illinois or Michigan.
We trained on $30\%$ and tested on the remaining $70\%$ (random splits).
Error results are featured in Figures \ref{fig:spamerr} and \ref{fig:texterr} and reveal that VIBoost and AdaBoost performed similarly.


In addition to a classifier, VIBoost also provides noise statistics.
Using a synthetic dataset, we now look at the algorithm's estimate of the posterior SNR ($\eta_1/\eta_2$) and the posterior noise grade (\,$\log(\omega_2/\omega_1)$\,) after $50$ iterations.
We simulated 100 examples on the real line with $\mathcal{X} = \{-99,-97,-95,\ldots,+99\}$.
Following the generative process of \S\ref{sec:model}, we constructed the \textit{step} dataset with $F(x)=+\infty$ for $x$ positive and $-\infty$ for $x$ negative ($+1$ label for $x$ positive and $-1$ label for $x$ negative).
With a noise grade of $\log 3 \approx 1.1$, we varied the type prior, $\theta$, of the generative process.
Figures \ref{fig:stepsnr} and \ref{fig:stepxi} respectively show the SNR and noise grade with varying $\theta$.
In a pure-noise situation ($\theta = 0$) the SNR is at its lowest and the noise grade is best estimated.
Conversely, in the absence of noise ($\theta = 1$) the SNR is at its greatest, rendering the noise grade estimate irrelevant. 


The last dataset we considered in this paper was also simulated.
Inspired by \cite{long2010}, we constructed a 1,200-example, 31-feature \textit{Long-Servedio} dataset---a dataset that provably ``breaks'' AdaBoost and many other algorithms with a convex loss minimization.
The details can be found in \cite[\S12.3]{schapire2012} and Matlab code is included in \S\ref{supp:sec:longserv}.
Each run comprised $200$ training examples and $1000$ testing examples (random splits).
Following \cite{schapire2012}, the noise level was set to $0.20$.  
In our context, this translates to a type prior of $0$ (always reassigning a random label) and a noise grade of $\approx -1.4$.
Not surprisingly, AdaBoost and VIBoost do not succeed in finding a decent classifier for this set.
However, the SNR values produced by VIBoost indicate that poor classification should be expected (Figure~\ref{fig:lssnr}).
As a result, the algorithm shifts its focus from classification to noise quantification.


As variational inference navigates through a vast set of auxiliary distributions, our only verifiable means of efficacy is provided by the ELBO (\S\ref{supp:sec:elbo}).
Empirically, we have noticed that ELBO increases are larger in the beginning main-loop iterations.
As the algorithm progresses, changes in the ELBO are quite small and sometimes negative (and small).
The small changes are expected because the composite classifier's accuracy is improving.
We hypothesize that the negative changes stem from the modal approximation used in a $w_n$-update expectation.
Alternatively, the ELBO requires a v-Log normalization constant, which we compute numerically and may be inexact.


\begin{figure}[t]
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{stepsnr1.pdf}
                \caption{\small Step dataset, Signal-to-noise ratio}
                \label{fig:stepsnr}
\end{minipage}
\hspace{0.03\linewidth}
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{stepxi.pdf}
                \caption{\small Step dataset, Noise Grade}
                \label{fig:stepxi}
\end{minipage}
\hspace{0.03\linewidth}
\begin{minipage}[b]{0.30\linewidth}
\centering
                \includegraphics[width=1.0\columnwidth]{lslogsnr.pdf}
                \caption{\small Long-Servedio dataset, Signal-to-noise ratio}
                \label{fig:lssnr}
\end{minipage}
\end{figure}


  
  
  


  
  
  


  
  
  

\section{Conclusion}  \label{sec:con}

We have developed a new boosting-like algorithm.
VIBoost attempts to fit a posterior distribution by applying variational inference to a dynamic model.
We began with a model centered around the binary classification problem and augmented it hierarchically to account for noise.

We did not set out to improve AdaBoost.
In addition to forming a binary classifier, the Bayesian model facilitated a label noise extension and we were able to extract information beyond classification.
We have observed experimentally that a good classifier is accompanied by a large SNR.
The SNR may explain why a poor classifier is returned by the learning algorithm.
We demonstrated this by analyzing the Long-Servedio dataset.

This model and accompanying algorithm are fertile ground for future work.
This paper did not address multi-class problems or regression.
We can also extend our model by forming connections between instances, base classifiers, and classifier weights (currently, these three features are conditionally independent given the labels).
We can also form dependencies between instances and label types, modeling varying levels of noise throughout the instance space.

\nocite{jordan1995}
\nocite{chen1995}
{ \small
