%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[10pt,oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{float}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\floatstyle{ruled}
\newfloat{algorithm}{tbp}{loa}
\floatname{algorithm}{Algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{plain}
 \theoremstyle{plain}    
 \newtheorem{cor}[thm]{Corollary} %%Delete [thm] to re-start numbering
 \theoremstyle{plain}    
 \newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{float}

\usepackage{latexsym,amsmath,amssymb}

\newtheorem{theorem}{Theorem}
\newtheorem{claim}{Claim}[section]
\newtheorem{remark}{Remark}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{observation}{Observation}
\newcommand{\Proof}{\noindent{\bf Proof.}\ \ }
\renewcommand{\baselinestretch}{1}

\usepackage{babel}
\makeatother
\begin{document}

\title{Probabilistic Error Correcting Output Codes}

\begin{abstract}
Probabilistic error correcting output codes are a reduction from multiclass
classification to binary classification. They are a modification of
error correcting output codes \cite{ecoc} with an additional property:
$\epsilon$ regret for binary classification implies at most $4\sqrt{2\epsilon}$
regret for multiclass classification.

The probabilistic error correcting output code can also be used to
predict the probability of a class label. Used in this mode, the PECOC
reduction has the property that $\epsilon$ regret for binary classification
implies at most $4\epsilon$ $l_{2}$ regret for class probability
predictions.
\end{abstract}
\maketitle

\section{Background}

The goal of classification is to predict labels on test examples given
a set of labeled training examples. Binary classification, where the
number of labels is two, is the most basic learning task as it involves
predicting just a single bit for each example. Due to this simplicity,
binary learning is (perhaps) better understood theoretically than
any other prediction task, and several empirically good binary learning
algorithms exist.

Practical machine learning, on the other hand, often requires predicting
more than one bit, and some successful binary learning algorithms
(most notably AdaBoost \cite{adaboost} and support-vector machines
\cite{svms}) are extended to the multiclass case only with difficulty.
This motivates a question: {}``Can multiclass problems be solved
using binary classifier learners?''

A general approach to such reductions from multiclass to binary classification
is based on error-correcting output codes (ECOC), first described
in \cite{ecoc}. This reduction works by learning a binary classifier,
which decides membership of a label amongst subsets of labels. Given
a sequence of subsets, each label corresponds to a binary string (or
a \emph{codeword}) defined by the inclusion of this label in the sequence
of subsets. A multiclass prediction is made by finding the codeword
closest in Hamming distance to the sequence of binary predictions
on the test example.

GENERAL WARNING: Attempts to understand this theorem in terms of sample
complexity based learning will fail. This is an orthogonal theory
addressing how best to preserve learning across reductions and not
how to train (or how many samples are needed for training).

\begin{thm}
\cite{wap} For all distributions $D$ over multiclass test examples,
for all learned binary classifiers, the error rate of the ECOC reduction
is at most $4$ times the binary error rate. 
\end{thm}
We discuss the precise definition of the binary error rate later.
Intuitively, it is the binary error rate of the learned classifier
on the distribution over binary examples induced by the ECOC reduction
and the multiclass distribution $D$.

The proof of this statement (which appeared with weaker quantifications
in \cite{Venkat},\cite{marginecoc}) is essentially the observation
that there exist codes where the distance between any two codewords
is at least $\frac{1}{2}$. Consequently, at least $\frac{1}{4}$
of the classifiers must err to induce a multiclass classification
error, implying that the multiclass error rate is at most $4$ times
the binary error rate. 

This theorem is vacuous when the binary error rate is $0.25$ or more.
The probabilistic error correcting output codes (PECOC) we present
here address this problem. 

Allwein, Shapire, and Singer \cite{marginecoc} modified ECOC by considering
margins of the binary classifiers -- numbers internal to some classification
algorithms that provide a measure of confidence in a binary prediction.
Decoding proceeds in the same way as for ECOC except a {}``loss''-based%
\footnote{{}``Loss'' is in quotes here because the notion of loss here is
a specification of the optimization used by the binary learning algorithm
rather than the loss given by the problem.%
} distance is used instead of the Hamming distance. 

There are several drawbacks of Margin ECOC that we address in this
paper:

\begin{enumerate}
\item It only works on margin-based classifiers. This limitation seems significant
because several non-margin based classifiers (for example, decision
trees) work quite well. 
\item The margin is not a very good estimate of the probability of a class.
The common heuristic {}``find a large minimum margin'' causes a
distortion where the optimization increases the margin of small-margin
examples at the expense of the margin on large-margin examples. The
existence of the Platt scaling \cite{Platt} (i.e., fitting a sigmoid
to a margin to get a probabilistic prediction) can be thought of as
a strong empirical evidence of the probabilistic deficiency of margins.
\end{enumerate}
Note that a modified version of Margin ECOC which uses Platt scaling
on the margins is still not quite satisfactory because the margin
is not generally a sufficient statistic with the necessary information
to make good probabilistic predictions. 

PECOC functions in the same way as Margin ECOC, except we use a reduction
from probabilistic classification to classification \cite{Probing}
to estimate the binary class probabilities and decode a probability
for each class label. If we define \emph{regret} as the difference
between the loss achieved and the best possible loss (i.e., the loss
rate of the {}``Bayes optimal'' classifier), the PECOC reduction
guarantees the following regret transform:

\begin{thm}
(PECOC Regret Transform) For all distributions $D$ over test examples
$(x,y)$, if the learned binary classifier has regret $\epsilon$
the \emph{PECOC} reduction satisfies: \[
\forall l\in\{1,...,k\}:\,\,(\textrm{PECOC}(x)-D(l|x))^{2}\leq2\epsilon\]

\end{thm}
Intuitively, the regret of the learned binary classifier is defined
with respect to the distribution on binary examples induced by $D$
and PECOC as a sampling process.

When the most likely class under the PECOC reduction is reported,
this implies the following regret for multiclass classification:

\begin{cor}
(PECOC Regret Transform) For all distributions over test examples,
if the learned binary classifier has regret $\epsilon$ the \emph{PECOC}
multiclass classifier has regret at most $4\sqrt{2\epsilon}$. 
\end{cor}
A regret transform has stronger implications than an error transform,
such as for ECOC. For our example, on a problem with an unremovable
error rate of $1/4$ we might learn a binary classifier with error
rate of $1/4+\epsilon$. The regret is $\epsilon$, so the theorem
implies that the regret of the derived multiclass classifier would
be at most $4\sqrt{2\epsilon}$. Working with the regret (rather than
the absolute error rate) allows us to make meaningful statements even
when the problem has large amounts of noise. 

One implication of this theorem is that asymptotic consistency of
binary classification implies asymptotic consistency of multiclass
classification. This is true for neither Margin ECOC nor ECOC. 

The paper has the following structure:

\begin{enumerate}
\item We define the basic PECOC reduction. 
\item We prove the relative error transform of the PECOC reduction. 
\item We prove the inconsistency of ECOC and Margin ECOC. Consequently,
no theorem similar to our main theorem can be proved for these techniques.
\end{enumerate}

\section{The PECOC Reduction}

We work in an assumption-free multiclass classification setting. A
multiclass learning algorithm takes as input a sequence of training
examples in $(X\times\{1,...,k\})^{*}$, where $X$ is some arbitrary
feature space and $\{1,...,k\}$ is a set of labels. The learning
algorithm outputs a multiclass classifier $c:X\rightarrow\{1,...,k\}$
which labels arbitrary new elements of $X$. The PECOC reduction uses
as a black box a binary learning algorithm $B$.

The PECOC reduction uses an $n\times k$ binary coding matrix $M$
with columns corresponding to multiclass labels. Each of $n$ rows
defines a binary classification problem by specifying a subset of
labels and asking whether the label is in the subset. The Probing
reduction \cite{Probing} from probabilistic binary classification
to binary classification is then used to estimate the probability
of this answer. The columns of $M$ form a subset of any $k$ codewords
of a Hadamard code of length $n$, which has the property that any
two distinct codewords differ in at least $n/2$ bit positions. Such
codes exist and are easy to construct when $k$ is a power of 2. Thus,
for Hadamard codes, the number $n$ of classifiers needed is less
than $2k$. 

To make a prediction, for each label the PECOC reduction adds up the
probability of the subset containnig the label for each probabilistic
classifier and outputs the label with the largest probability.

The training algorithm is given in Figure \ref{fig:PECOC}. There
are two methods of predicting: getting a probabilistic prediction
as in Figure \ref{fig:PECOCp_predict} or taking an argmax to make
a hard prediction as in Figure \ref{fig:PECOC_predict}.

%
\begin{algorithm}

\caption{\label{fig:PECOC} \textbf{PECOC-train} (Set of $k$-class examples
$S$, $n\times k$ binary matrix $M$, probabilistic binary classifier
learning algorithm $\textrm{PB}$)}

\begin{enumerate}
\item For each row $i$ of $M$:


Let $h_{i}=\textrm{PB(}\{(x,M(i,y)):(x,y)\in S\})$

\item return $\{ h_{i}\}$\end{enumerate}

\end{algorithm}


%
\begin{algorithm}

\caption{\label{fig:PECOCp_predict} \textbf{PECOC-predict} (Probabilistic
binary classifiers $\{ h_{i}\}$, $n\times k$ binary matrix $M$,
test example $x\in X$)}

\begin{enumerate}
\item For each row $i$ of $M$:

\begin{enumerate}
\item Let $p_{i}=c_{i}(x).$
\end{enumerate}
\item For each label $l\in\{1,\ldots,k\}$:

\begin{enumerate}
\item Let $\hat{p}(l)={\displaystyle \Sigma}_{i=1}^{n}M(i,l)p_{i}+(1-M(i,l))(1-p_{i})$ 
\end{enumerate}
\item For each label $l$, return $\frac{2\hat{p}(l)}{n}-1$.\end{enumerate}

\end{algorithm}


%
\begin{algorithm}

\caption{\label{fig:PECOC_predict} \textbf{PECOC-hard-predict}(Probabilistic
Binary classifiers $\{ h_{i}\}$, $n\times k$ binary matrix $M$,
test example $x\in X$)}

\begin{enumerate}
\item Let $\{\hat{p}(l)\}=$\textbf{PECOC-predict}($\{ h_{i}\}$, $M$,
$x$)
\item return $\arg\max_{l}\textrm{$\hat{p}$}(l)$\end{enumerate}

\end{algorithm}


It might appear that PECOC-train requires several invocations of the
oracle learning algorithm $A$, but a standard trick \cite{wap,marginecoc}
allows this to be collapsed to one classifier. The trick is to augment
the feature space with the number of the call, $X\rightarrow X\times\{1,...,n\}$,
and then learn a classifier $c$ on (a random subset of) the union
of all training data. With this classifier, we can define $c_{i}(x)\equiv c(x,i)$,
and all of our results hold for this single invocation classifier. 

The implication of this observation is that we can regard PECOC-train
as a machine which maps multiclass samples to binary samples (using
probing as a subroutine). Thus, we can regard PECOC-train as having
type $\textrm{PECOC-train}:(X\times\{1,...,k\})^{*}\rightarrow(X'\times\{0,1\})^{*}$,
and the learned binary classifier is simply $B(\textrm{PECOC-train}(S))$.


\section{The Main Theorem}

Before stating the theorem, we define exactly what error and regret
means. Given any distribution $D$ on examples $X\times Y$, the error
rate of a classifier is given by \[
e(D,c)=\Pr_{x,y\sim D}(c(x)\neq y)\]
The regret is the difference between the error rate and the best possible
error rate:

\[
r(D,c)=e(D,c)-\min_{c'}e(D,c')\]
(Note that we mean the minimum over \emph{all} $c'$ not over some
subset.) 

We also must define exactly what the induced distribution on the binary
classifier is. To do this, we simply define how to draw one sample
from the induced distribution. To draw from the induced distribution,
first draw a multiclass sample $(x,y)$ from $D$. Then apply PECOC-train
to the singleton set $\{(x,y)\}$ to get a sequence of binary examples
$(x',y')^{n}$. Now, to draw from $D'$, sample uniformly from this
set. We overload notion and denote the induced distribution as $\textrm{PECOC-train}(D)$.

First, we restate the main theorem, and then prove it. 

\begin{thm}
\label{thm:(Full-PECOC-Regret}(Full PECOC Regret Transform) For all
distributions $D$ over multiclass test examples $(x,y)$, for all
binary learning algorithms $B$ and multiclass datasets $S$, let
$c=B(\textrm{Probing}(\textrm{PECOC-train}(S)))$. The \emph{PECOC}
reduction satisfies: \[
\forall l\in\{1,...,k\}:\,\, E_{x,y\sim D}(\textrm{PECOC-predict}(\textrm{Probing-predict}(c,.),x)-D(l|x))^{2}\leq8r(\textrm{Probing-train}(\textrm{PECOC-train}(D)),c)\]

\end{thm}
For the proof, first note that the dependence on $A$ and $S$ can
be removed by proving the theorem $\forall c$ (this is of equivalent
generality). 


\subsection{The Probing Lemma}

The proof uses the composability of reductions for two reductions.
The first reduction is the probing regret transform theorem \cite{Probing}
which we restate here. The probing reduction divides into a training
part Probing-train and a testing part Probing-test in the same way
as PECOC, and a similar theorem holds for a binary classifier.

\begin{lem}
(Probing Regret Transform) For all distributions $D$ over binary
test examples $(x,y)$, for all Binary learning algorithms $B$ and
binary datasets $S$, let $c=B(\textrm{Probing-train}(S))$ \[
E_{x,y\sim D}(D(y=1|x)-\textrm{Probing-predict}(c,x))^{2}\leq2r(\textrm{Probing-train}(D),c)\]
where $r$ is the regret of the learned binary classifiers.
\end{lem}

\subsection{The PECOC Lemma}

The second lemma is specific to the PECOC reduction. It states that
the ability to learn binary class probabilities up to an $l_{2}$
regret implies the ability to learn multiclass class probabilities
up to an $l_{2}$ regret. 

\begin{lem}
(PECOC Regret Transform module) For all Distributions $D$ over multiclass
test examples $(x,y)$, for all probabilistic binary classifiers $c$\[
\forall l:\,\,\, E_{x,y\sim D}(D(y=l|x)-\textrm{PECOC-predict}(l,c,x))^{2}\leq4E_{x,y\sim D'\equiv\textrm{PECOC-train}(D)}(D'(y=1|x)-c(x))^{2}\]

\end{lem}
\begin{proof}
We first analyze what happens when no regret is suffered, and then
analyze the case with regret.

Let $p_{l}=D(y=l|x)$ be the probability of label $l$ according to
the underlying process generating the test example. We identify sets
with their characteristic functions, so each row of the coding matrix
corresponds to a subset. Then define\[
P_{l}(x)=\sum_{l\in s}p_{l}(x)\]
 as the probability of a subset of labels $s$.

First observe that the code is symmetric with respect to all labels,
so we need analyze only one label $l$. Since 2(a) in Figure \ref{fig:PECOCp_predict}
is symmetric with respect to 0s and 1s, we can assume that $l$ is
in every subset. This can be done simply by complementing all rows
$i$ for which $M(i,l)=0$ and observing that the resulting set of
codewords still satisfies the distance property. For any other label
$l'$, half the time $l'$ is in $s$ and half the time it is not
in $s$. When the probabilistic classifiers have $0$ error, the value
of $\hat{p}(l)$ is given by\[
\hat{p}(l)=\sum_{s}P_{s}(x)=\sum_{s}\sum_{l\in s}p_{l}(x)=\frac{n}{2}(p_{l}(x)+\sum_{l'}p_{l'}(x))=n\frac{p_{l}(x)+1}{2}\]
 The last equality uses the fact that $\sum_{l=1}^{n}p_{l}=1$. Consequently,
step 3 outputs the exact probability when the probabilistic classifiers
are correct.

Now we analyze the regret transformation properties. In general, $\hat{P}_{s}(x)$
returned by the probabilistic binary classifier is not correct, so
we have $\sum_{s}\hat{P}_{s}(x)=\sum_{s}P_{s}(x)\pm n\epsilon=n\frac{p_{l}(x)+1}{2}\pm n\epsilon$,
so step 3 outputs $p_{l}(x)\pm2\epsilon$. Since the probing error
transform is concave, the most efficient method to induce a final
error of $2\epsilon$ is for each individual classifier to err by
$\epsilon$ to create $n\epsilon$ error in the sum and $2\epsilon$
error in the returned value. For this error scenario, the probabilistic
binary classifiers suffer a regret of $\epsilon^{2}$ and the probabilistic
multiclass classifier suffers a regret of $4\epsilon^{2}$

This implies the lemma.
\end{proof}
Since one of the rows can be made an all-one row (with membership
probability 1), we actually have a slightly tighter bound of\[
\frac{n}{2}(p_{l}(x)+1)+(n-1)\sqrt{2\epsilon}.\]



\subsection{The theorem proof}

Composing the two lemmas gives the proof.


\subsection{The corollary proof}

To prove the corollary, suppose the correct label has probability
$p_{l}$ and some other label has probability $p_{l'}<p_{l}$. In
order to cause an error, the probability estimate $\hat{p}_{l}$ for
the correct must be less than the probably estimate $\hat{p}_{l'}$.
Again, due to the concavity of the square root, the most efficient
way to create an error is for $\hat{p}_{l}=\frac{p_{l'}+p_{l}}{2}\simeq\hat{p}_{l'}$,
implying that the adversary must pay the regret necessary to induce
a probabilistic error of size $\frac{p_{l}-p_{l'}}{2}$. By theorem
\ref{thm:(Full-PECOC-Regret}, this is $\epsilon=\frac{1}{8}\left(\frac{p_{l}-p_{l'}}{2}\right)^{2}$.
On the other hand, the amount of multiclass regret induced by choosing
$l'$ rather than $l$ is just $p_{l}-p_{l'}$. Solving for $p_{l}-p_{l'}$
finishes the corollary.


\section{Lower Bounds?}


\section{Inconsistency of ECOC}

This proof relies on the observation (1) that ECOC can use at most
$2^{n}$ bits to distinguish among classes. However, predicting optimally
requires an arbitrary number of bits.


\section{Inconsistency of MarginECOC}

This proof relies on the ill-definedness of {}``margin''. Optimal
binary margin based classifiers might (for example) always have a
margin of $-1$ or $1$ implying the ECOC inconsistency theorem.


\section{Practical Variants}

The above algorithm provides nice theoretical guarantees, but has
some obvious deficiencies. These deficiencies can be addressed without
significantly weakening the theoretical guarantees.

\begin{enumerate}
\item When $k$ is very large, we can instead use a code defined by picking
a random subset of $O(\frac{1}{\epsilon^{2}}\log\frac{2k}{\delta})$
codewords. Hoeffding bounds imply that the estimates $\hat{p}[l]$
vary by at most $\epsilon$ with probability $1-\delta$. 
\item Learning intractability. Intuitively, learning to distinguish a random
subset may be significantly harder than learning to distinguish (say)
one label from all other labels. This intuition is born out by experiments
\cite{marginecoc}. This observation suggest that PECOC should be
applied on sparse codes (i.e. codes where each classifier learns to
predict a small subset). The exact choice of code is a subtle affair
not fully addressed here. 
\end{enumerate}

\section{Conclusion}

\begin{thebibliography}{1}
\bibitem{marginecoc}Erin Allwein, Robert Schapire, and Yoram Singer. Reducing multiclass
to binary: A unifying approach for margin classifiers. \emph{Journal
of Machine Learning Research}, 1:113--141, 2000. 
\bibitem{wap}Alina Beygelzimer, Varsha Dani, Tom Hayes, and John Langford. Reductions
between classification tasks. \emph{Electronic Colloquium on Computational
Complexity}, TR04-077, 2004.
\bibitem{ecoc}Thomas Dietterich and Ghulum Bakiri. Solving multiclass learning problems
via error-correcting output codes. \emph{Journal of Artificial Intelligence
Research}, 2:263--286, 1995. 
\bibitem{adaboost}Yoav Freund and Robert Schapire. A decision-theoretic generalization
of online learning and an application to boosting. \emph{Journal of
Computer and System Sciences}, 55(1), 119--139, 1997.
\bibitem{Venkat}Venkat Guruswami and Amit Sahai. Multiclass learning, boosting, and
error-correcting codes. In \emph{Proceedings of the 12th Annual Conference
on Computational Learning Theory (COLT)}, 145--155,1999.
\bibitem{Probing}John Langford and Bianca Zadrozny. Estimating class membership probabilities
using classifier learners. In \emph{Proceedings of the 10th International
Workshop on Artificial Intelligence and Statistics}, 2005. 
\bibitem{Platt}John Platt. Probabilistic outputs for support vector machines and
comparisons to regularized likelihood methods. In A. Smola, P. Bartlett,
B. Schölkopf, and D. Schuurmans, editors, \emph{Advances in Large
Margin Classifiers}, 61--74, 1999.
\bibitem{svms}Vladimir Vapnik. \emph{The Nature of Statistical Learning Theory}.
Springer, 1995.\end{thebibliography}

\end{document}
