\documentstyle[nips99,psfig,rotate]{article}
\input{code-macros.tex}

\title{Robust Learning with FeatureBoost}

\author{Joseph O'Sullivan, John Langford, Rich Caruana, Avrim Blum \\
School of Computer Science\\ 
Carnegie-Mellon University\\
Pittsburgh, PA 15213 \\
{\it \{josullvn,jcl,caruana,blum\}@cs.cmu.edu} \\
}

\newcommand{\takeout}[1]{}       %% use 'takeout' to comment regions
\newcommand{\percent}{{\% }}     %% I can't stand the way xemacs font locks.. 
\newcommand{\jos}[1]{{\bf jos:}{\em #1}}
% The \author macro works with any number of authors.
% There are two commands used to separate the names and addresses of
% multiple authors: \And and \AND.
%
% Using \And between authors leaves it to \LaTeX{} to determine where
% to break the lines.  Using \AND forces a linebreak at that point.
% So, if \LaTeX{} puts 3 of 4 authors names on the first line, and the
% last on the second line, try using \AND instead of \And before
% the third author name.


\begin{document}

\maketitle

\begin{abstract}
PAC learning typically assumes that the training and test sets are
drawn from the same distributions.  This assumption often is violated
in practice.  How can machine learning algorithms be biased to output
hypotheses that are robust to alterations in the test distribution?
We create a framework for learning in environments where the test and
training distributions differ because features in the test sets are
likely to be missing or corrupted.  Motivated by this framework, we
present a new meta-learning algorithm, FeatureBoost.  We demonstrate
FeatureBoost on three learning problems using backprop nets, k-nearest
neighbor, and decision trees.
\end{abstract}

\section{Motivation}

Consider a backprop net learning to steer a car in Pomerleau's ALVINN
system~\cite{alvinn}. The principle internal features learned by
ALVINN nets detect the left and right edges of the road.  ALVINN nets
do not learn internal features that detect road centerlines.  This
creates a problem when the left or right edges of the road are
obstructed by passing vehicles, or are missing as on bridges.  Yet
human steering is remarkably robust to the loss of these features
because human drivers can fall back on a number of alternate features
as different subsets of road features come in and out of view.
Backprop nets do learn to steer better if they are {\em forced} to
learn to recognize centerlines\cite{centerlines}. Why do ALVINN nets
not automatically learn to use a variety of road features (such as
centerlines) when learning to steer?

A related problem arises in pneumonia risk
prediction\cite{pneumonia}. Here there are a number of basic inputs
available for patients before they enter the hospital (e.g., age,
gender, blood pressure), as well as a number of lab features that
become available after patients enter the hospital (e.g., RBC counts,
oxygenation, Albumin).  Models trained to predict risk from both the
pre and in-hospital features are more accurate than models trained
from only the pre-hospital inputs, but perform poorly on patients not
yet admitted to the hospital (marginalizing over the missing
in-hospital features).  Models trained to predict risk from only the
pre-hospital inputs are more accurate on patients not yet admitted to
the hospital than marginalized models trained on all the features.
If we can train models to make good predictions from only the
pre-hospital inputs, why don't models trained with all the features
work this well when some of the features are missing?

In ALVINN and pneumonia above, problems arise when the training and
test set distributions differ because features are missing or obscured
in the test set.  In the real world, it is common for training sets to
be drawn from different distributions than the test sets on which the
models must perform well. The distributions differ for a variety of
reasons:
\begin{enumerate}
\item Temporal drift in the underlying distributions with the test set
drawn later.
\item The training set is 'cleaned' more than future test sets.
\item The training sample is too small to capture all the phenomena
that will occur in future test sets.
\item Unanticipated uses of the models (e.g. use upon partial
examples)
\end{enumerate}

This paper introduces FeatureBoost, a meta-learning algorithm that
trains models to use different sets of features.  Because the final
prediction will combine predictions from models depending on different
(often overlapping) sets of features, it will be more robust to
missing or obscured features.  We develop the paper as follows:

\begin{enumerate}
\item Present a simple model that suggests how robustness can be
improved.
\item Develop a meta-learning algorithm inspired by the model (FeatureBoost). 
\item Test FeatureBoost on a variety of learning problems and
algorithms.
\end{enumerate}

\section{A Robust Learning Model}

The model we present is similar to PAC models in machine learning
theory.  Assume there exists some unknown underlying distribution, \(
D \), from which \( n \) examples with \( m \) features, \(
x^n=(x_{1},...,x_{m})^n \) are drawn.  These examples are labeled
according to an unknown target function, \( y=c(x) \).

Further assume that \( q \) disjoint subsets of the features can
predict the label, \(
y=c_{1}(x_{1},...,x_{i})=c_{2}(x_{i+1},...,x_{j})=...=c_{q}(x_{k+1},...,x_{m})
\).  Co-training~\cite{cotrain} makes a similar assumption.

\takeout{For simplicity, assume that each of the \( m \) features can predict
the label, \( y=c_{1}(x_{1})=c_{2}(x_{2})=...=c_{m}(x_{m}) \).
Equivalently, we could assume that disjoint subsets of the features
can predict the target, but that complicates the discussion.
Co-training~\cite{cotrain} makes a similar assumption.}

The learning algorithm is presented with \( n \) labeled examples, \(
(x,y)^{n} \), and asked to produce a hypothesis, \( h:X\rightarrow Y
\), used for future predictions. The goal is to minimize the
disagreement between \( h(x) \) and \( c(x) \) according to some loss
function such as squared error or hamming loss.  We focus on the
hamming loss function, \( E_{h}=P_{D}(h(x)\neq c(x)) \).

Assume that an unbiased estimate of the error under the unknown
distribution \( D \) can be found.  We wish to understand how this
error may change with an alteration in the test distribution.
Specifically, consider a test distribution in which some percentage of
the disjoint feature sets are corrupted uniform randomly.  Corruption
of a feature set in an example, \( x \), is accomplished by picking a
second example, \( z \), from \( D \) and substituting the values of
the feature set from \( z \) into \( x \).  This approach leaves
the distribution of the feature unchanged by corruption.

\takeout{Assume that an unbiased estimate of the error under the unknown
distribution \( D \) can be found.  We wish to understand how this
error changes with an alteration in the test distribution.
Specifically, consider a test distribution in which some percentage of
features are corrupted uniform randomly.  Corruption of a feature in
an example, \( x \), is accomplished by picking a second example, \( z
\), from \( D \) and substituting the value of the feature from \( z
\) into \( x \).  This approach leaves the distribution of  features
unchanged by corruption.}

There are two extreme cases to consider. The first is an Occam's razor
motivated learner such as a decision tree, which attempts to find a
small set of features that can predict the label.  If we assume that
a decision tree focuses on a particular \( 1 \) of the \( q \) feature
sets, then when \( k\% \) of the feature sets are corrupted, the
decision tree is effected \( k\% \) of the time.  If there are just
two labels and the decision tree outputs a random value when it relies
on a corrupted feature set, this results in error linearly increasing
from \( E_{h} \) to \( 50\% \) as \( k \) increases from \( 0\% \) to
\( 100\% \).

\takeout{There are two extremes to consider. The first is an Occam's razor
learner such as a decision tree which attempts to find a small set of
features that can predict the label.  Assume a decision tree focuses
on a particular \( 1 \) of the \( m \) features, then when \( k\% \)
of the features are corrupted, the decision tree is effected \( k\% \)
of the time.  If there are just two labels and the decision tree
outputs a random value when it relies on a corrupted feature, this
results in error linearly increasing from \( E_{h} \) to \( 50\% \) as
\( k \) increases from \( 0\% \) to \( 100\% \).}

The second extreme case occurs when the model uses all feature sets to
predict the label. It's difficult to state how this will effect
accuracy without making assumptions about the learning algorithm.
Assume that a decision tree is used on each disjoint feature set with
the resulting tree outputs passed through a majority voting function
and that errors by one decision are independent of errors by all other
decision trees.  From \( k = 0\%-100\% \), the error will increase
from \( E_{h} \) to \( 50\% \) at a rate dependent on the value of \(
q \), the number of feature sets.  Each decision tree error can be viewed
as flipping a random coin with some bias.  If enough random coins come
up with the wrong label, they will overwhelm the good predictors in
the vote. The probability of error is distributed as the cumulative
distribution of a binomial tail.

The second learning algorithm dominates the first one, always doing at
least as well under any \( k\% \) feature set corruption and often
doing significantly better.  We are motivated to create a learning
algorithm using a mixture of experts with each expert focusing on a
different set of features.

\takeout{The second extreme case occurs when the model uses all features to
predict the label. It's difficult to know how this will effect
accuracy without making assumptions about the learning algorithm.
Assume that a decision tree is used on each feature with the resulting
tree outputs passed through a majority voting function and that errors
by one decision are independent of errors by all other decision trees.
From \( k = 0\%-100\% \), the error will increase from \( E_{h} \) to
\( 50\% \) at a rate dependent on the value of \( m \), the number of
features.  Each decision tree error can be viewed as flipping a random
coin with some bias.  If enough random coins come up with the wrong
label, they will overwhelm the good predictors in the vote. The
probability of error is distributed as the cumulative distribution of
a binomial tail.

The second learning algorithm dominates the first one, always doing at
least as well under any \( k\% \) feature corruption and often doing
significantly better.  We are motivated to create a learning algorithm
using a mixture of experts with each expert focusing on different
features.}

\section{FeatureBoost}

The algorithm we present is a variant of boosting where features are
boosted rather than examples. Think of examples as a matrix of inputs
with each row a particular example. Whereas AdaBoost and other boosting
algorithms emphasize particular rows (examples) in the matrix,
FeatureBoost emphasizes particular columns (features) in the matrix
instead. This is similar to Bay's work with k nearest
neighbors~\cite{knnrandomfeatsel}, though the goals and algorithms
differ considerably.

The goal of FeatureBoost is to search for alternative explanations for
the target amongst the features. This is accomplished by conducting a
sensitivity analysis on the features used by previously learned
models, and then biasing future learning away from the features used
most. This process is repeated and a weighted mixture of experts is
output (see Table~\ref{t:featureboost}).

\begin{table}[htbp]
\caption{Pseudocode describing the FeatureBoost algorithm.}
\label{t:featureboost}
\begin{center}
\codebox{%
\< $\procdecl{FeatureBoost}(e,D,\proc{WeakLearn},T)$ 	
\\ {\bf Input}: \>\> $e$: $N$ examples each containing $M$ features 
\\ \>\>$D$: Distribution over features (say, uniform)
\\ \>\>$\proc{WeakLearn}$: Weak Learning algorithm 
\\ \>\>$T$: Number of iterations
\\ \li \For $i \in \{1..M\}$ {\bf do} $w^1_i$ $\gets$ $D(i)$
\\ \li \For $t$ $\in$ $\{1..T\}$  {\bf do}
\\ \li \> $p^t$ $\gets$ $w^t/{\sum^M_{i=1} w^t_i}$
\\ \li \> $h_t$ $\gets$ hypothesis of $\proc{WeakLearn}$ under $p^t$
\\ \li \> $I^t$ $\gets$ importance of each of $M$ features to $\proc{WeakLearn}$
\\ \li \> $\beta_t$ $\gets$ $max({\epsilon_t}/({1-\epsilon_t}),0.01)$
\\ \li \> $\epsilon_t$ $\gets$ $\sum^N_{i=1} \mid h_t(i) - c(i) \mid$
\\ \li \> \For $i \in \{1..M\}$ {\bf do}
		$w^{t+1}_i$  $\gets$ $w^{t}_i$ + $I^i_i*(0.5\takeout{\footnote{We believe that using
$\epsilon_{fm}$, the full marginalization error, instead of
the constant $0.5$, is more appropriate, but have not yet tested this.}}- \epsilon_t)$
\\ {\bf Output}: \>\>\> $h_f(i) = \sum^T_{t=1}(\log \frac{1}{\beta_t})h_t(i) 
		\ge
	\frac{1}{2}\sum^T_{t=1}\log \frac{1}{\beta_t}$
}
\end{center}
\end{table}

It is interesting to contrast FeatureBoost with AdaBoost. To make this
simpler, we used the same variable names as in \cite{AdaBoost}. In
FeatureBoost, the distribution $D$ is over {\em features} and {\sc
WeakLearn} must accept a bias in the form of a probability
distribution $p^t$ over {\em features}.  In AdaBoost, the distribution
$D$ is over examples, {\sc WeakLearn} must accept a bias in the form
of a probability distribution $p^t$ over {\em examples}, there is no
need to calculate the importance of features as in line $5$, and the
weights in line $7$ are updated by:\\ \centerline{ {\bf for} $i \in
\{1..N\}$ {\bf do} \( w^{t+1}_i \gets w^{t}_i \beta^{1-\mid h_t(i) -
c(i) \mid}_t.\) }

It is not obvious how best to bias {\sc WeakLearn} by a probability
distribution over features. We have considered several approaches,
including scaling individual features and adding noise to individual
features. Here we use a progressive feature masking procedure for
$t>1$. Before calling {\sc WeakLearn}, we calculate the current full
marginalization error, $\epsilon_{fm}$ from $t-1$. We then marginalize
the most important features from the training data, until the
marginalized performance of {\sc WeakLearn} is worse than \(
((T-t)*0.1 + t*\epsilon_{fm})/T \).\footnote{We believe that using
$\epsilon_{t-1}$, the error of {\sc WeakLearn} from $t-1$, instead of
the constant $0.1$, is more appropriate, but have not yet tested this.}
In practice, we observe that occasionally it is too easy or too hard
to do worse than this bound, so we also require that at least
15\percent\ of the features are removed, and at least 10\percent\ of
the features remain.

The calculation of the importance of individual features is performed
by repeatedly picking a random training example and assigning a random
value to the feature according to the distribution of values for that
feature in the training set.  The error of the hypothesis on this
example is then calculated.  After many iterations (we use $500$), the
change in the average error of the hypothesis is detected.  These
error changes yield an importance vector over features that is scaled
to have entries in $ (0,1) $. For some weak learners the importance
of features can be directly calculated.

%% Maybe we should spell it out in algorithmic form like FeatureBoost.
%% Good idea.  The text is intelligible with effort, but do we have space?

\section{Results}

Figure~\ref{f:res1} shows the performance of FeatureBoost on a
synthetic domain ({\sc Threshold}) using boosted decision trees. In
this domain, a threshold function is drawn uniformly from the interval
\([25,75]\). Examples are drawn uniformly from \( [0,100] \) and
example values are coded in several ways: with a grey code, a
``peaks'' code, a binary code, a unary code, and the value divided by
\( 100 \). Grey code is a similar to binary code except that only one
feature changes at a time when counting from \( 0 \) to \( 100
\). Peaks code consists of \( 100 \) features with values calculated
by a Gaussian centered on the example value\cite{centerlines}. Unary
code (``thermometer code'') outputs as many \( 1 \)'s as the example
value, then fills in \( 0 \)'s to reach 100 features. Coding the
inputs these different ways yields data that satisfies the assumption
that there are multiple disjoint subsets of the features which can
predict the target.  Each trial trains on 100 examples and tests on
300.

\begin{figure}[htbp]
\centerline{
%\hbox{\psfig{file=ind_largethresholda.eps,width=2.5in}}
%\hbox{\psfig{file=ind_largethresholdb.eps,width=2.5in}}
\hbox{\psfig{file=ind_large.eps,width=5in,height=1.8in}}
}
\caption{The improvement from boosting {\sc DT} by FeatureBoost,
Mixture Models, and AdaBoost on {\sc Threshold}. On the left,
individual features are randomly corrupted.  On the right, corruption
happens to entire {\em sets} of features. Results are presented with
95\percent confidence intervals from 100 trials using 20
experts. \label{f:res1}}
\end{figure}

The graphs in Figure~\ref{f:res1} compare the error of the decision
tree ``weak'' learner ({\sc DT}) to that of several voting algorithms
as corruption increases: {\sc Mixture} (a simple mixture of experts),
{\sc AdaBoost}~\cite{AdaBoost}, and {\sc FeatureBoost}. The results
show how robust each method is to random corruption of the test
data. The left graph in Figure~\ref{f:res1} shows results for uniform
feature corruption: where each feature is corrupted individually
(feature sets contain only one feature).  The right graph shows
results for uniform feature set corruption: entire feature sets (the
grey, binary, or thermometer coding) are corrupted at one time.
Feature set corruption simulates clusters of features tending to be
occluded or corrupted together, as when parts of an image are occluded,
or when an event such as not being admitted to the hospital causes an
entire set of features to be missing.

We now demonstrate FeatureBoost applied to artificial neural nets
({\sc ANN}), k-nearest neighbor ({\sc kNN}), and decision trees ({\sc
DT}).  For {\sc DT} we used Buntine's IND. For {\sc ANN} we use three
layer backprop nets with 5 hidden units, conjugate gradient descent,
and early stopping using hold-out sets.  For {\sc kNN} we use
unweighted Euclidean distance with $k=2$.

We test each FeatureBoosted algorithm on three domains: the UCI Vote
domain, a real pneumonia problem, and a synthetic problem we created
to demonstrate FeatureBoosting.  The Voting domain consists of a
congressman's voting record on 16 votes. The label is the party,
democrat or republican, which the congressman belongs to. In each
trial, 100 examples were used for training, 335 for testing. The
Pneumonia domain uses real patient data consisting of 30 pre-hospital
and 35 in-hospital features.  The label is the risk of death. In each
trial 1000 examples were used for training, 2000 for testing.

\begin{figure}[htb]
\begin{tabular}{rccc}
	&	{\sc kNN}&{\sc ANN}&{\sc DT} \\
\rotate[l]{\hspace{0.2in} \sc Pneumonia}
&
	\hbox{\psfig{file=knn_pneumoniaa.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=nn_pneumoniaa.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=ind_pneumoniaa.eps,width=1.45in,height=1.3in}} \\
\rotate[l]{\hspace{0.2in} \sc Threshold}&
	\hbox{\psfig{file=knn_thresholda.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=nn_thresholda.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=ind_thresholda.eps,width=1.45in,height=1.3in}} \\
\rotate[l]{\hspace{0.3in} \sc Voting}   &
	\hbox{\psfig{file=knn_votinga.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=nn_votinga.eps,width=1.45in,height=1.3in}} &
	\hbox{\psfig{file=ind_votinga.eps,width=1.45in,height=1.3in}} \\
\end{tabular}
\caption{Percent improvement over weak learning in three
domains ({\sc Pneumonia}, {\sc Threshold}, and {\sc Voting}) for three
weak learners ({\sc kNN}, {\sc ANN} and {\sc DT}) and for three ways
of generating experts.  Results are presented with 95\percent
confidence intervals from 100 or more trial using 20
experts. \label{f:res2}}
\end{figure}

The results in Figure~\ref{f:res2} suggest that FeatureBoost dominates
AdaBoost and simple mixtures of experts when features in the test set
are corrupted. Simple mixtures of experts improve robustness because a
mixture of experts is not an Occam's razor learner, but not as much as
FeatureBoost because a simple mixture of experts does not focus
learning to use different sets of features.  The graphs also suggest
that the effect of FeatureBoost is most pronounced for {\sc DT} and
least pronounced for {\sc kNN}.  This is expected because {\sc DT} is
biased to use few features, whereas {\sc kNN} with unweighted Euclidean
distance uses all features.

\section{Discussion}

The basic problem FeatureBoost addresses is how to benefit from
redundancy in the input features.  Most machine learning methods are
what we might call ``abridged'' learners.  They learn the simplest
models that are accurate on the training data.  Because simple models
often depend on fewer features, these models are not very robust when
applied to test sets in which important features are missing,
occluded, or corrupted.

FeatureBoost makes an learning algorithm less abridged by learning
multiple models that use different (possibly overlapping) sets of
features.  The ultimate unabridged learning procedure would be to
train separate models on the power set of the input features, and
combine these models weighted by their estimated accuracy.  This
approach is impractical, of course, for problems having more than a
few attributes.

Despite the success of FeatureBoost on these problems, there are
difficulties using it. The optimal schedule for biasing feature use
depends on the learning algorithm and target function. FeatureBoost
can be considered a heuristic search through the space of ``ideal''
subsets of features.  The goal of this search is to find diverse sets
of explanations for the output.  If, as with the synthetic threshold
function, features are encoded with multiple redundant disjoint
subsets of inputs, we would not want use the same feature in two
different models. In real world problems, however, this separation is
rarely so clean and it may be best to user overlapping subsets of
features.

We compare FeatureBoost to AdaBoost because AdaBoost should improve
robustness in some circumstances.  Suppose when training ALVINN nets
to steer, most of the training data contains unobstructed views of the
left and right sides of the road, and only a few training cases have
obstructed views of the sides of the road.  The first models trained
with AdaBoost will use the sides of the road as their main features.
AdaBoost, however, will then focus it's effort on training cases where
these models fail.  In these training cases, the centerlines may be
the next best features.  AdaBoost probably will no learn to use
centerlines as well as FeatureBoost, however, because AdaBoost will
learn about centerlines from the small fraction of training cases in
which edges are not visible.  If centerlines are visible in most
images, including those with unobstructed views of road edges,
FeatureBoost will learn about centerlines using the full training set.
Combining AdaBoost with FeatureBoost may yield the best of both
methods. We do not yet have theoretical guarantees for FeatureBoost
comparable to those for AdaBoost.

The difference between corrupted features and missing features is
important.  If values are missing, a technique similar to ``sleeping
experts''\cite{sleeping} may be more effective.  In this setting,
there are many sub-hypotheses that combine to form an unabridged
hypothesis using weighted majority (only hypotheses with no missing
values vote).  A softer form of this where sub-hypotheses vote with
strength proportional to their confidence may work well in real world
settings.

Corrupted test data is not the only model for Robust learning.  Robust
learning can also be thought of as PAC learning with a loss function
that varies with the examples. When learning to drive a car, you don't
care so much about how perfectly the car drives on open highway, but
you care very much about how well it avoids crashes in more difficult
situations. A PAC learner that is told which examples are riskier
might also create more robust hypotheses.

There are many approaches one might use to make machine learning
algorithms more unabridged.  This paper presents just one.  Another
approach we are testing is to use feature selection to train models on
compact sets of features, then remove the features selected (hard or
soft removal), and train additional models on the remaining features.
Just as there are a number of algorithms for boosting examples, there
may be several good algorithms for boosting features.

FeatureBoost is one way of creating more robust learning. It should be
most effective when applied to Occam's razor-style learners such as
decision trees.  Our results show that it is also effective with
neural nets and kNN.

\small{
\bibliographystyle{chicagoa}
\begin{thebibliography}{10}

\bibitem{knnrandomfeatsel}  Bay, S. (1998) Combining Nearest Neighbor
Classifiers Through Multiple Feature Subsets. {\it Proceedings of the
Fifteenth International Conference on Machine Learning (ICML98) }
pp. 37-45.  Morgan Kaufmann.

\bibitem{cotrain} Blum, A. \& Mitchell, T.  (1998) Combining Labeled and
Unlabeled Data with Co-Training. In {\it Proceedings of the 11th Annual
Conference on Computational Learning Theory}, pp. 92-100. 

\bibitem{buntine} Buntine, W.  (1992) Learning Classification Trees.  {\it
Statistics and Computing} {\bf 2}:63-73.

\bibitem{centerlines} Caruana, R. (1997) Multitask
Learning. Ph.D. Thesis, School of Computer Science, CMU.

\bibitem{AdaBoost} Freund, Y. \& Schapire, R. (1995) A Decision
Theoretic Generalization of On-Line Learning and an Application to
Boosting. {\it Proceedings of the Second European Conference on
Computational Learning Theory.}  

\bibitem{sleeping} Freund, Y. \& Schapire, R. \& Singer, Y. \&
Warmuth, M.  (1997) Using and Combining Predictors that Specialize.
{\it STOC97}.

\bibitem{alvinn} Pomerleau, D. (1993) {\it Neural Network Perception for Mobile 
Robot Guidance.} Kluwer Academic Publishers.

\bibitem{pneumonia} Cooper, G. F., Aliferis, C. F., Ambrosino, R.,
Aronis, J., Buchanan, B. G., Caruana, R., Fine, M. J., Glymour, C.,
Gordon, G., Hanusa, B.  H., Janosky, J. E., Meek, C., Mitchell, T.,
Richardson, T., and Spirtes, P. (1997) An Evaluation of Machine
Learning Methods for Predicting Pneumonia Mortality. {\it Artificial
Intelligence in Medicine 9}, pp.  107-138.

\end{thebibliography}
\end{document}

### scrap
\takeout{
\begin{table}[t]
\caption{
\label{t:res1}
\begin{center}
\small{
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline 
Domain             & Corrupt & \multicolumn{3}{|c|}{\sc kNN}&\multicolumn{3}{|c|}{\sc Neural}&\multicolumn{3}{|c|}{\sc IND} \\
	           &            & F & A & M & F & A & M &  F & A & M   \\ 
\hline
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
{\sc Pneumonia}&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
\hline
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
{\sc Threshold}&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
\hline
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
{\sc Voting}   &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
	       &0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent&0.0\percent\\
\hline
\end{tabular}
}
\takeout{
\small{
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline 
Domain             & Corruption & \multicolumn{3}{c}{\sc }&\multicolumn{3}{c}{\sc Neural}&\multicolumn{3}{c}{\sc IND} \\
	           &            & Feature & AdaBoost & Mixture & Feature & AdaBoost & Mixture &  Feature & AdaBoost & Mixture   \\ 
\hline
	           &            &         &          &         &         &          &         &          &          &           \\ 
{\sc Pneumonia}    &            &         &          &         &         &          &         &          &          &           \\ 
	           &            &         &          &         &         &          &         &          &          &           \\ 
\hline
	           &            &         &          &         &         &          &         &          &          &           \\ 
{\sc Syn-Threshold}&            &         &          &         &         &          &         &          &          &           \\ 
	           &            &         &          &         &         &          &         &          &          &           \\ 
\hline
	           &            &         &          &         &         &          &         &          &          &           \\ 
{\sc Voting}       &            &         &          &         &         &          &         &          &          &           \\ 
	           &            &         &          &         &         &          &         &          &          &           \\ 
\hline
\end{tabular}
}
}
\end{center}
\end{table}
}

\takeout{
\codebox{%
\< $\procdecl{FeatureBoost}()$ 	
\\ \< {\bf Input}: 
\\ \>$N$ examples each containing $M$ features
\\ \>\> $N$ labels, one for each example
\\ \> Weak Learning algorithm ``WeakLearn''
\\ \> Number of iterations, $T$
\\ \< {\bf Output}: 
\\ \>A hypothesis, $H(x_1,...,x_M)$
\\ \< {\bf Algorithm}:
\\ \li  $\{W_1,...,W_M\}$ $\gets$ $\{1/M,...,1/M\}$ 
\\ \li \For $t$ $\gets$ $1..T$  
\\ \li \Do  $\id{H[t]}$ $\gets$ $\proc{WeakLearn}(e, l)$
}
}

\takeout{
\begin{minipage}[l]{2.5in}
\codebox{%
\< $\procdecl{AdaBoost}(e,D,WeakLearn,T)$ 	
\\ \< {\bf Input}: 
\\ \< $N$ examples each containing $M$ features 
\\ Distribution $D$ over examples (say, uniform)
\\ \< Weak Learning algorithm ``WeakLearn'' 
\\ \< Number of iterations, $T$ 
\\ \< {\bf Algorithm}: 
\\ \li  $w^1_i$ $\gets$ $D(i)$, $i \in \{1..N\}$  
\\ \li \For $t$ $\in$ $\{1..T\}$   
\\ \li \Do $p^t$ $\gets$ $\frac{w^t}{\sum^N_{i=1} w^t_i}$
\\ \li \>\> $h_t$ $\gets$ $\proc{WeakLearn}(p^t)$
\\ \li \>\> $\epsilon_t$ $\gets$ $\sum^N_{i=1} p^t_i \mid h_t(i) - c(i) \mid$
\\ \li \>\> $\beta_t$ $\gets$ $\epsilon_t/(1-\epsilon_t)$
\\ \li \>\> $w^{t+1}_i$  $\gets$ $w^{t}_i$ $\beta^{1-\mid h_t(i) - c(i) \mid}_t$
\\ \< {\bf Output}: 
\\ \< $h_f(i) = \sum^T_{t=1}(\log \frac{1}{\beta_t})h_t(i) 
		\ge
	\frac{1}{2}\sum^T_{t=1}\log \frac{1}{\beta_t}$
}
\end{minipage}
\begin{minipage}[r]{2.4in}
\codebox{%
\< $\procdecl{FeatureBoost}(e,D,WeakLearn,T)$ 	
\\ \< {\bf Input}: 
\\ \< $N$ examples each containing $M$ features 
\\ Distribution $D$ over features (say, uniform)
\\ \< Weak Learning algorithm ``WeakLearn'' 
\\ \< Number of iterations, $T$ 
\\ \< {\bf Algorithm}: 
\\ \li  $w^1_i$ $\gets$ $D(i)$, $i \in \{1..M\}$  
\\ \li \For $t$ $\in$ $\{1..T\}$   
\\ \li \Do $p^t$ $\gets$ $\frac{w^t}{\sum^N_{i=1} w^t_i}$
\\ \li \>\> $h_t$ $\gets$ $\proc{WeakLearn}(p^t)$
\\ \li \>\> $\epsilon_t$ $\gets$ $\sum^N_{i=1} p^t_i \mid h_t(i) - c(i) \mid$
\\ \li \>\> $\beta_t$ $\gets$ $\epsilon_t/(1-\epsilon_t)$
\\ \li \>\> $w^{t+1}_i$  $\gets$ $w^{t}_i$ $\beta^{1-\mid h_t(i) - c(i) \mid}_t$
\\ \< {\bf Output}: 
\\ \< $h_f(i) = \sum^T_{t=1}(\log \frac{1}{\beta_t})h_t(i) 
		\ge
	\frac{1}{2}\sum^T_{t=1}\log \frac{1}{\beta_t}$
}
\end{minipage}
}

