<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% 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.
\newcommand{\noun}[1]{\textsc{#1}}
\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{definition}
 \newtheorem{defn}[thm]{Definition}
 \theoremstyle{plain}    
 \newtheorem{cor}[thm]{Corollary} %%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{Sensitive Error Correcting Output Codes}

\begin{abstract}
Sensitive error correcting output codes are a reduction from cost
sensitive classification to binary classification. They are a modification
of error correcting output codes \cite{ecoc} which satisfy an additional
property: $\epsilon$ regret for binary classification implies at
most $2\epsilon$ $l_{2}$ regret for cost-estimation. This has a
number of important implications:

1) Any $0/1$ regret minimizing online algorithm is (via the reduction)
a regret minimizing online cost sensitive algorithm. In particular,
this means that online learning can be made to work for arbitrary
(i.e. totally unstructured) loss functions.

2) The output of the reduction can be thresholded so $\epsilon$ regret
for binary classification implies at most $4\sqrt{\epsilon}$ regret
for cost sensitive classificaiton.

3) Using the canonical embeding of multiclass classifcation into cost
sensitive classification, this reduction implies that $\epsilon$
binary regret implies at most $2\epsilon$ $l_{2}$ error in the estimation
of class probabilities. When thresholded, this implies at most $4\sqrt{\epsilon}$
multiclass regret.
\end{abstract}
\maketitle

\section{Introduction}

\noun{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. Furthermore (in the most general case) each prediction
may have a different associated loss. For example, consider the commuting
problem: Given information in the form of the current weather and
radio reports, we must predict which of several routes to take. The
goal in this task is to minimize the expected time of travel. We could
think of this as a multiclass problem (predict which route is fastest),
but this can make the problem more difficult%
\footnote{For example, it's easy to design a problem where there are several
paths that are good except they are occasionally very slow. If there
is another path which is never the best but never slow it may provide
the best expected time of all choices. If this is altered into a multiclass
problem of {}``predict the best path'', the {}``never the best
but never slow'' option will never be the correct label. %
} due to throwing away information. 

\noun{General Warning:} Attempts to understand the contents of this
paper in terms of sample complexity results such as PAC learning \cite{valiant}
or uniform convergence \cite{VC} will fail. This is an orthogonal
theory where we define leaning problems as measures over certain sets
and analyze the transformation of losses under mappings between these
measures.

\noun{Motivation:} Reductions allow us to translate performance
on well-studied binary problems into performance on the more general
problems arising in practice. We provide a reduction (SECOC) from
cost sensitive classification to binary classification with the property
that small regret on the created binary problem(s) implies small regret
on the original cost sensitive classification problem. This is particularly
compelling because \emph{any} loss function on single examples can
be expressed with cost sensitive classification. Therefore, this reduction
can be used (at least theoretically) to solve a very broad set of
learning problems. In addition, there is significant empirical evidence
(see \cite{Probing,wap,costing}) that analysis in this style results
in algorithms providing good performance.

The basic SECOC reduction can be reused in several ways.

\begin{enumerate}
\item \noun{General Online Learning:} Any $0/1$ regret minimizing online
algorithm is (via the reduction) a regret minimizing online cost sensitive
algorithm. In particular, this means that online learning can be made
to work for arbitrary (i.e. totally unstructured) loss functions.
\item \noun{General Regret Minimizing Boosting:} Since the binary learning
algorithm might be a version of boosting which can boost to the regret
to $0$ (as in \cite{KS}), the composition of boosting with SECOC
can boost to zero regret on arbitrary (i.e. totally unstructured)
loss functions.
\item \noun{Cost Sensitive Classification:} The output of the reduction
can be thresholded so a small regret for binary classification implies
a small regret for cost sensitive classification. This implies that
any consistent binary classifier is a consistent cost sensitive classifier. 
\item \noun{Multiclass Probability Estimation:} Using the canonical embeding
of multiclass classifcation into cost sensitive classification, this
reduction implies that small binary regret implies small $l_{2}$
error in the estimation of class probabilities. 
\item \noun{Multiclass classification:} When the multiclass probability
estimates are thresholded, this implies a small multiclass regret.
Note that this implies \emph{any} consistent binary classifier is
(via the reduction) a consistent multiclass classifier. This is particularly
important because generalization of SVMs to multiple classes \cite{Wahba}
have been done wrong. 
\end{enumerate}
\noun{Context:} SECOC is a variation of error-correcting output
codes (ECOC) \cite{ecoc}. Later in section \ref{sub:Inconsistency-of-ECOC}
we show that this variation is necessary in order to satisfy a regret
transform. The ECOC 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.

For the ECOC reduction, a basic statement \cite{Venkat} can be made:
with a good code, for all training sets, the error rate of the multiclass
classifier on the training set is at most $4$ times the error rate
of the individual binary classifiers. The proof of this statement
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 the theorem via the pigeonhole principle.

This theorem can be generalized \cite{wap} to quantify {}``for all
measures'' rather than {}``for all training sets''. This generalization
is not as significant as it might at first seem because the measure
implicit in a very large training set can approximate other measures
(and it can do so arbitrarily well when the feature space is finite).
Nevertheless, it is convenient to quantify over all measures so the
statement holds for the process generating each individual example.
Since there is always some process generating examples, the result
is applicable even to adversarial processes.

The weighted all pairs algorithm of \cite{wap} intuitively guarantees
that a small error rate on created classification problems implies
a small cost sensitive loss. The core result here is similar except
that small binary \emph{regret} implies small cost sensitive \emph{regret}.
Regret is the error rate minus the minimum error rate. Consequently,
the results here can have important implications even when (for example)
the binary error induced from a multiclass problem is $0.25$. SECOC
does not supercede this earlier result because the regret bounds are
weaker, roughly according to $\epsilon$ error rate $\rightarrow$
$\sqrt{\epsilon}$ regret. 

ECOC was modified \cite{marginecoc} to consider 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 because the notion of loss is a specification
of the optimization used by the binary learning algorithm rather than
the loss given by the problem, as is used in the rest of the paper.%
} distance is used instead of the Hamming distance. Roughly speaking,
SECOC uses the motivation behind this approach although not the approach
itself. Instead of working with margins, we define binary classification
problems for which the optimal solution computes the expected cost
(rather than the margin) of choices. This approach allows us to accomplish
several things:

\begin{enumerate}
\item We can use arbitrary classifiers rather than margin-based classifiers. 
\item We remove the mismatch between the margin and the motivations. Optimizations
of hinge loss (for SVMs) or exponential loss (for Adaboost) cause
a distortion where the optimization increases the margin of small-margin
examples at the expense of the margin on large-margin examples. The
efficacy of 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 deficiency of margins as probability
estimates. 
\item We can generalize the approach to tackle all cost sensitive problems
rather than just multiclass problems. This generalization comes at
no cost in multiclass performance.
\end{enumerate}
\noun{Outline:} The next sections of this paper do the following:

\begin{enumerate}
\item We define the basic SECOC reduction.
\item We define and then prove the main theorem.
\item We prove corollaries of the main theorem for different applications.
\item We prove some structural lower bounds: that ECOC can not achieve the
regret transform we prove and that no tighter bound can be proved
for SECOC.
\end{enumerate}

\section{The SECOC Reduction}

We work in an assumption-free learning setting. To define the reduction,
we first define the problems that we reduce to and from. We will actually
reduce to importance weighted binary classification. Since importance
weighted binary classification can be reduced to binary classification
\cite{costing}, a reduction all the way to binary classification
is achievable. 

\begin{defn}
(Importance Weighted Binary Classification) An Importance weighted
binary classification problem is defined by a measure $D$ on a set
$X\times\{0,1\}\times[0,\infty)$, where $X$ is some arbitrary feature
space,$\{0,1\}$ is the correct binary label and $[0,\infty)$ is
the importance of correct classification. The goal in solving binary
classification is to find a binary classifer $b:X\rightarrow\{0,1\}$
which minimizes the expected importance weighted loss, $E_{(x,y,i)\sim D}iI(b(x)\neq y)$
where $I()$ is $1$ when the argument true and $0$ otherwise. 
\end{defn}
SECOC reduces from cost sensitive classification.

\begin{defn}
(Cost Sensitive Classification) A cost sensitive problem is defined
by a measure $D$ on a set $X\times[0,\infty)^{k}$, where $X$ is
some arbitrary feature space and the additional information $[0,\infty)^{k}$
is the cost of each choice. . The goal in solving cost sensitive classification
is to find a multiclass classifer $m:X\rightarrow\{1,...,k\}$ which
minimizes the expected cost, $E_{(x,\vec{c})\sim D}c_{m(x)}$.
\end{defn}
A cost sensitive learning algorithm typically takes as input a sequence
of training examples in $(X\times[0,\infty)^{k})^{*}$ as advice in
constructing $h(x)$. The SECOC reduction is a cost sensitive learning
algorithm given a binary learning algorithm. 

The SECOC reduction use a code, just as the ECOC reduction. An $n\times k$
binary coding matrix $M$ with columns corresponding to multiclass
labels defines the code. 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 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 classification problems
needed is less than $2k$. 

To define a SECOC, we create a set of importance weighted classification
problems for each subset $s$ of the labels. Since importance weighted
classification can be reduced to binary classification \cite{costing}
this reduction can actually be done all the way to binary classification.
The particular importance weighted classification problems are defined
so that from their optimal solution we can compute the expected cost
of each subset.

To make a prediction, for each label the SECOC reduction adds up the
expected cost of the subsets containing the label and outputs the
label with the largest probability.

The training and prediction algorithms are given in Figure \ref{fig:SECOC}
and Figure \ref{fig:SECOC_predict}.

%
\begin{algorithm}

\caption{\label{fig:SECOC} \textbf{SECOC-train} (Set of $k$-class cost sensitive
examples $S$, importance weighted binary classifier learning algorithm
$B$, range $\left[\min_{t},\max_{t}\right]$ for $t$)}

\begin{enumerate}
\item For each subset $s$ defined by the rows of $M$: 

\begin{enumerate}
\item For $(x,\,\vec{c})\in S$, let $|\vec{c}|=\sum_{y}c_{y}$ and $c_{s}=\sum_{y\in s}c_{y}$.
\item For each $t$ in $\left[\min_{t},\max_{t}\right]$:


Let $b_{st}=\textrm{B(}\{(x,\,\, I(c_{s}\geq t|\vec{c}|),|c_{s}-t|\vec{c}||):(x,\,\vec{c})\in S\})$.

\end{enumerate}
\item return $\{ b_{st}\}$\end{enumerate}

\end{algorithm}


%
\begin{algorithm}

\caption{\label{fig:SECOC_predict} \textbf{SECOC-predict} (Binary classifiers
$\{ b_{st}\}$, $n\times k$ binary matrix $M$, test example $x\in X$)}

\begin{enumerate}
\item For each label $y$ return $2\left(E_{s}E_{t}I(l\in s)b_{st}(x)+I(l\not\in s)(1-b_{st}(x)\right)-1$\end{enumerate}

\end{algorithm}


It might appear that SECOC-train requires several invocations of the
oracle learning algorithm $B$, 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 name of the call, $X\rightarrow X\times\{0,1\}^{k}\times[0,1]$,
and then learn a classifier $c$ on (a random subset of) the union
of all training data. With this classifier, we can define $h_{st}(x)\equiv h(x,s,t)$,
and all of our results hold for this single invocation classifier. 

The implication of this observation is that we can regard SECOC-train
as a machine which maps cost sensitive samples to importance weighted
binary samples. Thus, we can regard SECOC-train as having type $\textrm{SECOC-train}:(X\times[0,\infty)^{k})^{*}\rightarrow(X'\times\{0,1\}\times[0,\infty))^{*}$,
and the learned binary classifier is simply $B(\textrm{SECOC-train}(S))$.
The range$\left[\min_{t},\max_{t}\right]$ can be set to $\left[\min_{D,s}\frac{{c_{s}}}{|\vec{c}|},\max_{D,s}\frac{{c_{s}}}{|\vec{c}|}\right]$


\section{The Main Theorem}

Before stating the theorem, we need to define loss and regret. Given
any distribution $D$ on examples $X\times\{0,1\}\times[0,\infty)$,
the importance weighted error rate of a binary classifier $b$ is
given by\[
e(D,b)=E_{(x,y,i)\sim D}iI(b(x)\neq y).\]
Similarly, given any distribution $D$ on examples $X\times[0,\infty)^{k}$,
the cost sensitive loss of a multiclass classifier $m$ is given by\[
e(D,m)=E_{(x,\vec{c})\sim D}c_{m(x)}.\]
For each of these notions of loss, the regret is the difference between
the achieved performance and best possible performance:

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

We also must define the induced distribution on the binary classifier.
To draw a sample from this distribution, we first draw a cost sensitive
sample $(x,\vec{c})$ from $D$, and then apply SECOC-train to the
singleton set $\{(x,\vec{c})\}$ to get a sequence of importance weighted
binary examples. Now, we just sample uniformly from this set. We overload
and denote the induced distribution by $\textrm{SECOC-train}(D)$. 

It will also be useful to talk about the distribution $D_{st}$ over
$X\times\left\{ 0,1\right\} \times[0,\infty)$ for given $s\subseteq\left\{ 1,\ldots,k\right\} $
and $t\in[0,1]$, induced by the process in Algorithm \ref{fig:SECOC}.
For a cost vector $\vec{c}\in[0,\infty)^{k}$ and a subset $s\subseteq\left\{ 1,\ldots,k\right\} $,
let $c_{s}=\sum_{y\in s}c_{y}$. Also let $|\vec{c}|=\sum_{y=1}^{k}c_{y}$.
To draw from $D_{st}$, we draw $(x,\vec{c})$ from $D$ and output
$(x,I(c_{s}\geq t|\vec{c}|),\left|c_{s}-t|\vec{c}|\right|)$.

\begin{thm}
\label{thm:(SECOC-Regret-Transform)}\emph{(}SECOC Regret Transform\emph{)}
For any importance weighted binary learning algorithm $B$ and a cost-sensitive
dataset $S$ in $(X\times[0,\infty)^{k})^{*}$, let $b=B(\textrm{SECOC-train}(S))$.
The \emph{SECOC} reduction satisfies the following regret transform
for all test distributions $D$ over $X\times[0,\infty)^{k}$: For
every label $y\in\left\{ 1,\ldots,k\right\} $,\[
E_{(x,\vec{c})\sim D}\left(\textrm{SECOC-predict}(b,x,\vec{c})-\frac{E_{\vec{c}|x}c_{y}}{E_{\vec{c}|x}|\vec{c}|}\right)^{2}\leq4(\textrm{max}-\textrm{min})r(\textrm{SECOC-train}(D),b).\]

\end{thm}
First note that the dependence on $B$ and $S$ can be removed by
proving the theorem for all $b$ (which is of equivalent generality). 

\begin{proof}
We first analyze what happens when no regret is suffered, and then
analyze the case with regret. For any choice of $s$ and $t$, the
optimal classifier is given by

\[
b_{st}^{*}=\arg\min_{b}E_{(x,y,i)\sim D_{st}}iI(b(x)\neq y)\]
\[
=\arg\min_{b}E_{(x,\vec{c})\sim D}I\left(b(x)\not=I(c_{s}\geq t|\vec{c}|)\right)\cdot\left|c_{s}-t|\vec{c}|\right|.\]
For any $x$, the optimal value of $b(x)$ is either $0$ or $1$.
When it is $0$, the expected cost equals\begin{equation}
E_{\vec{c}\sim D|x}\max{\left\{ (c_{s}-t|\vec{c}|),0\right\} }.\label{eq:foo}\end{equation}
Otherwise, the expected cost equals\begin{equation}
E_{\vec{c}\sim D|x}\max{\left\{ (t|\vec{c}|-c_{s}),0\right\} }.\label{eq:foo2}\end{equation}
To simplify notation, let $Z_{x}=E_{\vec{c}\sim D|x}|\vec{c}|$. Equations
\ref{eq:foo} are \ref{eq:foo2} are continuous in $t$; the first
decreases while the second increases monotonically with $t$, so we
need only find the (single) equality point to describe the optimal
behavior for all $t$. This equality point is given by \[
E_{\vec{c}\sim D|x}\max{\left\{ (c_{s}-t|\vec{c}|),0\right\} }=E_{\vec{c}\sim D|x}\max{\left\{ (t|\vec{c}|-c_{s}),0\right\} },\]
or\[
E_{\vec{c}\sim D|x}(c_{s}-t|\vec{c}|)=0,\]
yielding\[
t=\frac{E_{\vec{c}\sim D|x}c_{s}}{Z_{x}},\]
and thus $b_{st}^{*}(x)=I(E_{\vec{c}\sim D|x}c_{s}\geq tZ_{x})$. 

For any choice of $s$, we have \[
E_{t}b_{st}^{*}(x)=E_{t}I\left(E_{\vec{c}\sim D|x}c_{s}\geq tZ_{x}\right)=\frac{E_{\vec{c}\sim D|x}c_{s}}{Z_{x}}\]
since the $E_{t\in[0,1]}I(K\geq t)=K$ for all $K\in[0,1]$. 

Since decoding is symmetric with respect to all labels, we need analyze
only one label $y$. Furthermore, since step 1 in Figure \ref{fig:SECOC_predict}
is symmetric with respect to set inclusion or complement set inclusion,
we can assume that $y$ is in every subset. This can be done by complementing
all subsets not containing $y$ and observing that doing so does not
change the deconding properties of the code.

Consequently, \[
\hat{c}_{y}=E_{s}E_{t}b_{st}(x)=E_{s}\frac{\frac{{1}}{2}E_{\vec{c}\sim D|x}(c_{y}+|\vec{c}|)}{Z_{x}}=\frac{{1}}{2}\left(\frac{E_{\vec{c}\sim D|x}c_{y}}{Z_{x}}+1\right),\]
 where the second equality follows from the fact that every other
label appears in $s$ half the time in expectation over $s$. Consequently,
step 1 outputs $\frac{1}{Z_{x}}E_{\vec{c}\sim D|x}c_{y}$ for each
$y$, when the classifiers are optimal.

Now we analyze the regret transformation properties. The remainder
of this proof characterizes the most efficient way that any adversary
can induce estimation regret with a fixed budget of importance weighted
regret. 

Examining equations \ref{eq:foo} and \ref{eq:foo2}, notice that
the importance weighted loss grows linearly with the distance of $tZ_{x}$
from $E_{\vec{c}\sim D|x}c_{s}$, but on the other hand, each error
has equal value in disturbing the expectation in line 1 of Figure
\ref{fig:SECOC_predict}. There are two consequences for an adversary
attempting to disturb the expectation the most while paying the least
importance weighted cost.

1) It is {}``cheapest'' for an adversary to err on the $t$ closest
to $\frac{{1}}{Z_{x}}E_{\vec{c}\sim D|x}c_{s}$ first. (Any adversary
can reduce the importance weighted regret by swapping errors at large
values of $|t-\frac{{1}}{Z_{x}}E_{\vec{c}\sim D|x}c_{s}|$ for errors
at small values without altering the estimation regret.) 

2) It is {}``cheapest'' to have a small equal disturbance for each
$s$ rather than a large disturbance for a single $s$. (The cost
any adversary pays for disturbing the overall expectation can be monotonically
decreased by spreading errors uniformly over subsets $s$.) 

Consequently, the optimal strategy for an adversary wanting to disturb
the expectation by $\Delta$ is to disturb the expectation for each
$s$ by $\Delta$. The importance weighted regret of erring (with
a {}``$1$'') for $t=\Delta+\frac{{1}}{Z_{x}}E_{\vec{c}\sim D|x}c_{s}$
can be found by subtracting equation \ref{eq:foo2} from equation
\ref{eq:foo}.\[
E_{\vec{c}\sim D|x}(t|\vec{c}|-c_{s})I(c_{s}&lt;t|\vec{c}|)-E_{\vec{c}\sim D|x}(c_{s}-t|\vec{c}|)I(c_{s}\geq t|\vec{c}|)\]
\[
=E_{\vec{c}\sim D|x}\left(\left(\Delta+\frac{E_{\vec{c}\sim D|x}c_{s}}{Z_{x}}\right)|\vec{c}|-c_{s}\right)\]
\[
=\Delta Z_{x}.\]
The same quantity holds for $t=-\Delta+\frac{E_{\vec{c}\sim D|x}c_{s}}{Z_{x}}$.
Since we take an expectation with respect to the continuous variable
$t$, this is really an observation about the \emph{differential}
regret. We must integrate to find the total regret. The minimum importance
weighted regret suffered by an adversary disturbing the quantity by
$\Delta$ is thus\[
\int_{u=0}^{u=\Delta}uduZ_{x}=\frac{{\Delta^{2}}}{2}Z_{x}.\]
It is necessary to normalize this quantity by the average importance
to get sensible results. The average importance is: $\frac{\int_{\textrm{min}}^{\textrm{max}}|Z_{x}-tE_{\vec{c}\sim D|x}c_{s}|dt}{\textrm{max}-\textrm{min}}$.
This quantity is maximized when $E_{\vec{c}\sim D|x}c_{s}=Z_{x}$
where we get: $\frac{(\textrm{max}-\textrm{min})^{2}}{2(\textrm{max}-\textrm{min})}=\frac{(\textrm{max}-\textrm{min})}{2}$.
Consequently, the normalized importance weighted regret is at least:
$\frac{{\Delta^{2}}}{(\textrm{max}-\textrm{min})}Z_{x}$.

Using observation (2), this implies that the expectation over $s$
is disturbed by at most $\Delta$ with the same (average) budget of
importance weighted errors. Consequently, the predicted value for
the relative cost is disturbed by at most $2\Delta$ using the equation
from line 1 of Figure \ref{fig:SECOC_predict}. 
\end{proof}

\section{Applications}


\subsection{Reduction all the way to Classification}

The basic SECOC reduction above reduces to importance weighted binary
classification. However, there are easy reductions from importance
weighted classification to importance weighted binary classification.
For example, {}``Costing'' \cite{costing} uses repeated rejection
sampling to alter the measure. When SECOC is composed with these reductions
we get:

\begin{cor}
\label{thm:(SECOC-Regret-Transform)}\emph{(}SECOC Regret Transform\emph{)}
For any importance weighted binary learning algorithm $B$ and a cost-sensitive
dataset $S$ in $(X\times[0,\infty)^{k})^{*}$, let $b=B(\textrm{Costing}(\textrm{SECOC-train}(S)))$.
For all test distributions $D$ over $X\times[0,\infty)^{k}$: For
every label $y\in\left\{ 1,\ldots,k\right\} $,\[
E_{(x,\vec{c})\sim D}\left(\textrm{SECOC-predict}(\textrm{Costing}(b),x,\vec{c})-\frac{E_{\vec{c}|x}c_{y}}{E_{\vec{c}|x}|\vec{c}|}\right)^{2}\leq4(\textrm{max}-\textrm{min})r(\textrm{Costing}(\textrm{SECOC-train}(D)),b)E_{x,\vec{c}\sim D}|\vec{c}|.\]

\end{cor}
\begin{proof}
The Costing transformation has the guarantee that the $0/1$ regret
times the expected importance bounds the importance weighted regret.
\end{proof}

\subsection{Cost Sensitive Classification}


\subsection{Multiclass Probability Estimation}

SECOC can be used to predict the probability of class labels using
the training algorithm in Figure \ref{fig:PECOC}. The prediction
algorithm remains unchanged.

%
\begin{algorithm}

\caption{\label{fig:PECOC} \textbf{PECOC-train} (Set of $k$-class multiclass
examples $S$, importance weighted binary classifier learning algorithm
$B$)}

\begin{enumerate}
\item Let $S'=\{(x,\forall i\,\, c_{i}=I(i\neq y)):(x,y)\in S\}$For each
subset $s$ defined by the rows of $M$: 
\item return $\textrm{SECOC-Train}(S',B,\left\lfloor \frac{k-1}{2}\right\rfloor ,\left\lfloor \frac{k}{2}\right\rfloor )$\end{enumerate}

\end{algorithm}


\begin{cor}
\emph{\label{cor:(Multiclass-Probability-Regret}(}Multiclass Probability
Regret Transform\emph{)} For any importance weighted binary learning
algorithm $B$ and a multiclass dataset $S$ in $(X\times\{1,...,k\})^{*}$,
let $b=B(\textrm{PECOC-train}(S))$. For all test distributions $D$
over $X\times\{1,..,k\}$: For every label $y\in\left\{ 1,\ldots,k\right\} $,\[
E_{(x,y)\sim D}\left(\textrm{SECOC-predict}(b,x,y)-D(y|x)\right)^{2}\leq4r(\textrm{PECOC-train}(D),b).\]

\end{cor}
This corollary implies that probability estimates (up to an $l_{2}$
loss) are accurate whenever the classifier has small regret.

\begin{proof}
The proof just uses the main theorem \ref{thm:(SECOC-Regret-Transform)}.
In this case, $\textrm{max}-\textrm{min}=\frac{1}{k-1}$ and the sum
of the costs is always $k-1$ so the regret simplifies.
\end{proof}

\subsection{Multiclass Classification}

Using $\textrm{SECOC-Hard-predict}$, we achieve a consistent multiclass
classifier. 

\begin{cor}
\emph{(}Multiclass Classification Regret Transform\emph{)} For any
importance weighted binary learning algorithm $B$ and multiclass
dataset $S$ in $(X\times\{1,...,k\})^{*}$, let $b=B(\textrm{PECOC-train}(S))$.
For all test distributions $D$ over $X\times\{1,..,k\}$: For every
label $y\in\left\{ 1,\ldots,k\right\} $,\[
r\left(D,\textrm{SECOC-hard-predict}(b,x)\right)\leq4\sqrt{r(\textrm{PECOC-train}(D),b)}\]

\end{cor}
This guarantee can not be satisfied by ECOC (as we show in Section
\ref{sub:Inconsistency-of-ECOC}). A guarantee of this sort may be
provable with other variants of ECOC (such as \cite{marginecoc}),
but this seems to be strongest statement. It should be noted that
consistent generalizations of binary classifiers to multiclass classifiers
has historically been problematic \cite{Wahba}. This result shows
that \emph{any} consistent binary classifier can be used as a consistent
multiclass classifier. 

\begin{proof}
The regret of a multiclass prediction is proportional to the difference
in probability of the best prediction and the prediction made. We
can weaken corollary \ref{cor:(Multiclass-Probability-Regret} as:\[
E_{(x,y)\sim D}|\textrm{SECOC-predict}(b,x,y)-D(y|x)|\leq2\sqrt{r(\textrm{PECOC-train}(D),b)}\]
since for all $X$, $\sqrt{E(X)}\geq E\sqrt{X}$. When doing a hard
prediction according to these outputs, our regret at most doubles
because the probability estimate of the correct class can be reduced
by the same amount that the probability estimate of the wrong class.
\end{proof}

\subsection{Online Learning and Loss}

It might appear that that SECOC only works for batch learning, but
this is not true---the basic transformations are applied to individual
examples as in line 1(b) of algorithm SECOC-train. Consequently, the
transformation can be done online. The theorems apply to any measure
on $(x,\vec{c})$, so they also apply to the uniform measure over
past examples. Consequently, online regret minimizing binary predictors
can be used with SECOC to minimize cost sensitive regret online. 

Therefore SECOC can be used with online learning algorithms such as
weighted majority \cite{weighted majority} in order to optimize regret
with respect to \emph{any} loss function. 

Note that the notion of regret in online learning is typically defined
with respect to some set of {}``experts'' rather than the set of
all possible experts as here. This distinction is not essential. 


\subsection{Boosting Any Loss}

Boosting \cite{adaboost} is a technique for minimizing loss (and
hence regret = loss - minimum loss) for binary classification by adaptively
altering the measure over examples, learning with respect to the altered
measures, and combining the learned predictions. Since SECOC can be
reduced all the way to binary classification, boosting can be used
on the binary classifiers to minimize regret. The main theorem guarantees
that this is equivalent to minimizing regret with respect to any loss
function.

Note that some of the created binary problems may be inherently noisy,
and boosting tends to focus measure on these noisy examples. The basic
guarantee of boosting: that doing $\epsilon$ better than random can
be used to improve performance still holds, it is just that at some
point it becomes impossible to do better than random with respect
to the induced measure. Some work \cite{KS} has been done with alternate
boosting algorithms to weaken the sensitivity to noise, and these
approaches may be particularly valuable here due to the amount of
induced noise 


\section{ECOC Can Not Transform Regret}

\label{sub:Inconsistency-of-ECOC} Is it possible to do the same with
ECOC? The answer is no, and the proof is actually quite simple. Intuitively,
what we mean by inconsistency here is that even using an optimal binary
classifier, the reduction fails to provide an optimal multiclass classifier.

\begin{thm}
(ECOC Inconsistency) For all $k&gt;2$, there exists a distributions
$D$ over multiclass test examples $(x,y)$, such that for all codes
$M$, with $c^{*}=\arg\min_{c}r(\textrm{ECOC-train}(D),c)$ 

\[
r(D,\textrm{ECOC-test}(c^{*}))&gt;\frac{1}{10}\]

\end{thm}
\begin{proof}
The proof is constructive. We choose a $D$ which places probability
on $3$ labels, {}``1'', {}``2'', and {}``3''.

A few observations about symmetry greatly simplify the proof. The
first observation is that since only 3 labels have probability we
can rewrite any code $M$ as a new \emph{weighted} code $M'$ over
the $3$ labels where each subset has a weight $w_{s}$=the number
of times that subset of the $3$ labels exists in $M$ after projection.
The second observation is that the symmetry with respect to complementarity
implies each row (and each code word) has one '1' in it.

These observations imply that ECOC essentially uses the binary classifier
to ask {}``is the probability of label $i&gt;0.5$?'' for each $i\in\{1,2,3\}$.
These answers are then combined with a weighted sum. If we let the
probability of one label be $0.5-\epsilon$ and the probability of
the other labels be $0.25+\frac{\epsilon}{2}$, the answer to every
question will be {}``no'' (i.e. 0).

Since we have a weighted sum, the exact weighting determines the outcome
(possibly with randomization to break ties). The exact distribution
therefore picks a label at random to have probability $0.5-\epsilon$,
encodes that choice in the $x$ value, and then draws the label at
random. 

Under any code, the probability of predicting the label with greatest
probability is at most $\frac{1}{3}$ implying a regret of $\frac{2}{3}[0.5-\epsilon-(0.25+\frac{\epsilon}{2})]$
can be made arbitrarily close to $\frac{1}{6}$.
\end{proof}
A margin-based version of ECOC \cite{marginecoc} has the same lower
bound whenever the coding matrices are limited to {}``-1'' and {}``1''
entries. This is because consistent binary classifiers might have
margin $1$ or $-1$ for each example, and the proof above holds. 

However, this version of ECOC also allows {}``don't cares'' in the
code matrix. The existence of {}``don't cares'' allows questions
of the form {}``is the probability of this label greater than that
label?'' which are (in general) sufficiently powerful to support
regret transformation consistency, with the exact quantity of regret
transformation efficiency dependent on the coding matrix. We have
not yet found a margin based code with {}``don't cares'' with a
better regret transform than SECOC with the Hadamard Code. 

Take as an example, the all-pairs code, which is consistent. The all-pairs
code creates a classifier for every pair which (for an optimal classifier)
decides {}``Is class i more probable than class j?'' The problem
with this question is that the classifier is applied when class i
and class j each have $0$ probability. In this situation, an adversarial
classifier can freely choose to report either $p_{i}&gt;p_{j}$ or $p_{j}&gt;p_{i}$.
Consequently, an adversarial binary classifier could make some label
with $0$ conditional probability {}``beat'' all labels except for
the correct label without paying any regret. This is not robust, because
one error in one classifier (out of $k-1$ active classifiers) can
alter the result. Consequently, the regret transform for this code
scales with $k$.


\subsection{SECOC Theorem Can Not be Improved Much}


\section{Discussion}

This is the final section where we discuss various details and modifications
of the core algorithm.


\subsection{Variants}

There are several variants of the basic SECOC algorithm. One simple
variant code is {}``pick a random subset $s$ and pick a random $t$''.
This code has essentially the same analysis as the Hadamard code presented
here in the limit of infinitely many picks. 

For small values of $k$ (the number of classes), it is possible to
derive a better regret transform. For example, when $k=2$ there is
only one useful subset (up to symmetry in complementation), so the
prediction algorithm can simply output the cost estimate for that
one subset rather than 2{*}(average predicted cost) - 1. This removes
a factor of $2$ loosening in the last paragraph of the proof of the
main theorem. Similar although smaller improvements are possible for
small $k&gt;2$.

When used for class probability prediction the above observation improves
on the regret transform analysis of the probing algorithm \cite{Probing}
by a factor of $\sqrt{2}$. The reason for this improvement is (essentially)
the use of a unified measure over the classification problem rather
than many different measures for different problems. 


\subsection{Practical Matters}

The SECOC 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 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 SECOC 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.
\end{enumerate}

\subsection{Why regret isn't everything}

Other work \cite{wap} defines a reduction with the property that
small \emph{error} on the subproblem implies small \emph{error} on
the original problem. The definition of regret we use here is superior
because the theorems can apply nontrivially even on problems with
large inherent noise. However, the mathematical form of the regret
transforms is weaker, typically by $\epsilon$ loss changing to $\sqrt{\epsilon}$
regret. Tightening the regret transform by removal of the square root
seems to require a different construction. Understanding what, exactly,
is possible here is open work. 

\begin{thebibliography}{10}
\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{KS}Adam Kalai and Rocco Servedio, Boosting in the Presence of Noise,
\emph{Symposium on the Theory of Computing (STOC)}, 2003.
\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{valiant}L. G. Valiant, A Theory of the Learnable, Communications of the ACM
27(11):1134-1142, November 1984.
\bibitem{Vapnik}Vladimir Vapnik. \emph{The Nature of Statistical Learning Theory}.
Springer, 1995.
\bibitem{VC}V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of
relative frequencies of events to their probabilities. Theory of Probability
and it's Applications, 16(2):264-280, 1971.
\bibitem{costing}Bianca Zadrozny, John Langford, and Naoki Abe. Cost Sensitive Learning
by Cost-Proportionate Example Weighting ICDM 2003.
\bibitem{Wahba}Yoonkyung Lee, Yi Lin, and Grace Wahba. Multicategory Support Vector
Machines: Theory and Application to the Classification of Microarray
Data and Satelite Radiance Data, Journal of the American Statistical
Association, 99, 465 (2004) 67-81.
\bibitem{weighted majority}Nick Littlestone and Manfred Warmuth, The Weighted Majority Algorithm,
Foundations of Computer Science, 1992.\end{thebibliography}

\end{document}
</pre></body></html>