%% 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{Reducing Multiclass Cost Sensitive Classification to Binary Cost
Sensitive Classification}

\maketitle

\section{Goals}

The goal here is to find a good reduction from multiclass cost sensitive
classification to binary cost sensitive classification. These two
problems are summarized next, then a method is discussed.


\subsection{Multiclass Cost Sensitive Classification}

In multiclass cost sensitive classification, labeled examples have
the form $(x,c_{1},c_{2},...,c_{k})$ where $x\in X$ is an arbitrary
feature and $c_{l}\in[0,\infty)$ is the {}``cost'' of choosing
label $l$. Since the value of a good classifier is independent of
a global offset, we'll assume that there is at least one label $l$
which satisfies $c_{l}=0$.

To solve this problem, we must find a hypothesis $h:X\rightarrow\{1,...,k\}$
which produces low cost labels given the input feature. With respect
to some measure $D$ producing these examples we want to do the optimization:
\[
\min_{h}E_{(x,c_{1},c_{2},...,c_{k})\sim D}c_{h(x)}\]


Here the optimization (or heuristic optimization) is over some unspecified
and algorithm dependent set of classifiers.


\subsection{Binary Cost Sensitive Classification}

In binary cost sensitive classification, labeled examples have the
form $(x,y,i)$ where $x\in X$ is an arbitrary feature, $y\in\{0,1\}$
is a binary label and $i\in[0,\infty)$ is the {}``importance''
of classifying correctly. To solve this problem, we must find a hypothesis
$h:X\rightarrow\{0,1\}$ which is correct on high importance examples.
With respect to some measure $D$ producing these examples, we want
to solve the optimization: \[
\min_{h}E_{x,y,i\sim D}iI(h(x)\neq y)\]
Again, this (heuristic) optimization is according to some learning
algorithm.


\section{A Reduction}

Let's attempt a reduction of Multiclass Cost Sensitive Classification
to a single instance of Binary cost sensitive classification. In order
to do this prediction, we must settle on a method for converting a
binary classification into a multiclass classification. The following
algorithm seems reasonable:

Predict(classifier $h,$ example $x$)

\begin{enumerate}
\item $P=\{\}$
\item for every $l=1$ to $k$ do 

\begin{enumerate}
\item if $h(x,l)=1$ then $P\leftarrow P\cup\{ l\}$ 
\end{enumerate}
\item if $|P|>0$ then return a uniform draw from $P$ 
\item else return a uniform draw from $\{1,...,k\}$
\end{enumerate}
This procedure implicitly specifies how errors in the binary classification
transform into errors for the multiclass classification. This transformation,
in turn, can tell us what the good values for the importance $i$
in the binary classification problem are.

Our reduction maps a multiclass cost sensitive example $(x,c_{1},c_{2},...,c_{k})$
to a set of binary cost sensitive examples. We start by creating one
example for every label. The input feature is $(x,l)$ and the output
feature is $y_{l}=I(\frac{1}{k}\sum_{l'=1}^{k}c_{l'}-c_{l}\geq0)$
and the importance is $i_{l}=|\frac{1}{k}\sum_{l'=1}^{k}c_{l'}-c_{l}|$%
\footnote{The logic here is that this initial choice is always discriminative
(at least one label is $1$ and one label is $0$) whenever the costs
differ. In addition, this seems reasonable for the binary case.%
}. 

These are not necessarily the {}``right'' values for the importance
and label because, for example, our classifier might be capable of
distinguishing the best possible label from all other labels. We can't
know in advance how powerful our classifier is, so we need an adaptive
system to improve our classification. Therefore, we define an iterative
process which optimizes according to the ability of our learning algorithm. 

Iterate(binary cost sensitive learning algorithm $A$, multiclass
cost sensitive dataset $S$)

\begin{enumerate}
\item For every $(x,c_{1},...,c_{k})\in S$ 

\begin{enumerate}
\item For every $l\in\{1,...,k\}$ let $x_{l}=(x,l)$, $y_{x,l}=I(\frac{1}{k}\sum_{l'=1}^{k}c_{l'}-c_{l}\geq0)$,
$i_{x,l}=\frac{1}{k}\sum_{l'=1}^{k}c_{l'}-c_{l}|$
\end{enumerate}
\item Let $S'=\{\forall x,l\in\{1,...,k\}\,\,\,(x_{l},y_{x,l},i_{x,l})\}$
(Note that for algorithms which are sensitive to requiring i.i.d.
data, we'll only include one sample drawn uniformly from $l=\{1,...,k\}$.)
\item Let $h=A(S')$
\item For every $(x,c_{1},...,c_{k})\in S$

\begin{enumerate}
\item For every $l\in\{1,...,k\}$

\begin{enumerate}
\item $h_{bad}$ = $h$ except that it always errs on the input $x_{l}$.
\item $h_{good}=h$ except that it always succeeds on the input $x_{l}$.
\item $i_{l}=E_{l\sim Predict(h_{\textrm{bad}},x)}c_{l}-E_{l\sim Predict(h_{\textrm{good}},x)}c_{l}$
\item $y_{l}=I(i_{l}>0)$
\item $i_{l}=|i_{l}|$
\end{enumerate}
\end{enumerate}
\item If $E_{(x,c_{1},...,c_{k})\sim S}E_{l\sim Predict(h,x)}c_{l}$ did
not improve much then terminate otherwise go to 2
\end{enumerate}
This process has the following properties.

\begin{thm}
(optimality) If the above process halts, then the chosen importance
weights are optimal for any fixed error rate.
\end{thm}
\begin{proof}
Essentially the same as for the multiclass cost sensitive to multiclass
proof.
\end{proof}
\begin{thm}
(convergence) For any fixed error rate, $E_{(x,c_{1},...,c_{k})\sim D}E_{l\sim Predict(h,x)}c_{l}$
decreases with each iteration until convergence.
\end{thm}
\begin{proof}
I'm not sure how to prove this yet, but something like this should
hold. \end{proof}

\end{document}
