%% 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[oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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}

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

\title{Cost Sensitive Error Correcting Output Codes}

\maketitle

\section{The Algorithm}

For all subsets $s$, for all thresholds $t$, $\{(x,I(\frac{\sum_{y\in s}c_{y}}{\sum_{y}c_{y}}\geq t),\sum_{y}c_{y}:(x,c_{1},...,c_{k})\in S\}$

Apply $A$ to get hypothesis $h$

To predict, choose: \[
\arg\min_{y}E_{t}E_{s}c(x)I(y\in s)+(1-c(x))I(y\not\in s)\]



\section{The Analysis}

\begin{thm}
Error rate $\epsilon$ for binary classification implies loss rate
at most $2\epsilon E_{(x,c_{1},...,c_{k})}\sum_{y}c_{y}$
\end{thm}
\begin{proof}
We only need to show the reduction to importance weighted classification.
Since we use as an importance $\sum_{y}c_{y}$, we need only show
that the statement holds when $\sum_{y}c_{y}=1$. To do the prove,
we first analyze the expected sum for some prediction $y'$. Without
loss of generality(since we can always consider the complement of
any set), we can assume for all $s$ and $y'\in s$. 

$E_{t}E_{s}c_{st}(x)$ 

$=\frac{1}{|\{ s\}|}\sum_{s}E_{t}c_{st}(x)$

$=\frac{1}{|\{ s\}|}\sum_{s}\sum_{y\in s}c_{y}$

$=\frac{1}{|\{ s\}|}\sum_{s}c_{y'}+\frac{1}{2}\sum_{y\neq y'}c_{y}$

$=c_{y'}+\frac{1}{2}\sum_{y\neq y'}c_{y}$

$=c_{y'}+\frac{1}{2}(1-c_{y'})$

$=\frac{1}{2}(c_{y'}+1)$

So the expected value is $\frac{1}{2}(c_{y'}+1)$ when the classifiers
are perfectly correct. When an $\epsilon$ fraction err, the expected
value changes by at most $\epsilon$. Consequently, an $\epsilon$
fraction erring implies at most a $2\epsilon$ increase in cost since
we might reduce one expectation by $\epsilon$ and increase another
by $\epsilon$ simultaneously.
\end{proof}

\section{What's wrong here?}

If we consider the embedding of multiclass classification into cost
sensitive classification, we get $\sum_{y}c_{y}=k-1$ where $k$ is
the number of labels. Applying the above reduction implies $\epsilon$binary
errors $\Rightarrow$ $2\epsilon(k-1)$ multiclass errors or less.
This is not very impressive in comparison to standard ECOC ($\epsilon\rightarrow4\epsilon$).
Can we find an as-efficient cost sensitive reduction?

If we know the problem is an embedded multiclass problem, then we
can choose $t=0.5$. In this case we have:

$E_{t}E_{s}c_{st}(x)$ for $y'$

$=\frac{1}{|\{ s\}|}\sum_{s}E_{t}c_{st}(x)$

$=0$ or $\frac{1}{2}$ depending on whether $y'$ = the target.

So $\epsilon$ error rate $\Rightarrow4\epsilon$ multiclass error
rate, as expected.

The essential difference here is the range of $t$. When the decision
is between balanced sets, having $t$ near the boundary of balance
is important. However, this does not cover the range of interest in
cost sensitive classification.

Is there a modification of the cost sensitive error correcting code
algorithm which achieves optimality on the multiclass problem? The
best I can think of is letting $t$ range over the set of {}``interesting
values'' observed in the training set, but I am not sure this is
reasonable. 
\end{document}
