%% 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}
 \theoremstyle{plain}    
 \newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering

\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. 

The method we use depends on a free parameter $w_{x}$ for every value
of $x$. This parameter, roughly speaking, controls how optimistic
we are about the effectiveness of our classifier. If we believe the
classifier can choose the correct label from a large set, then a small
$w_{x}$ makes sense.

We map the example $(x,c_{1},c_{2},...,c_{k})$ to a binary example
with feature $x_{l}=(x,l)$, label $y_{l}=\textrm{sign}(w-c_{l})$
(where $w$ is a free parameter we worry about specifying later),
and an importance $i_{l}$ specified later. In order to use a binary
classifier for multiclass classification, we must specify a method
for producing the multiclass label. The following simple procedure
seems reasonable.

Predict($h,$$x$)

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

\begin{enumerate}
\item if $h(x)=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.

One fundamental quantity for any example $(x,c_{1},...,c_{k})$ and
weight $w_{x}$ is the size of the set $n_{w}=|\{ l:c_{l}<w\}|$.
Another is the expected cost given that no errors occur:\[
c_{w}=\frac{1}{n_{w}}\sum_{l:c_{l}<w}c_{l}\]
. Notice that in this notation $c_{\infty}=\frac{1}{k}\sum_{l=1}^{k}c_{l}$
is the average cost.

There are two basic failure modes: either we have a false positive
or a false negative. We want to analyze these failure modes in terms
of the parameters $c_{w}$ (cost when everything works out) and $c_{l}$
(the cost of the label $l$ that we err on). 

False positive: For some label $l$ which should have $h(x,l)=0$
we instead get $h(x,l)=1$. In this case, the expected cost is:\[
\frac{n_{w}c_{w}+c_{l}}{n_{w}+1}=c_{w}+\frac{c_{l}-c_{w}}{n_{w}+1}\]


This analysis is misleading because it only deals with the one error
case. If we have $n_{w}$ false negatives, then the cost of a false
positive might be as high as $c_{l}-c_{\infty}$ (notice that this
might be negative). A simple upper bound which always holds is $c_{l}-c_{w}$.

False, negative: For some $l$ which should have $h(x,l)=1$ we instead
get $h(x,l)=0$. In this case, the expected cost breaks down into
two possibilities. 

\begin{enumerate}
\item $n_{w}\geq2$. The expected cost is $\frac{n_{w}c_{w}-c_{l}}{n_{w}-1}=c_{w}+\frac{c_{w}-c_{l}}{n_{w}-1}$
($c_{w}-c_{l}$ can be positive or negative: some false negatives
can improve performance). 
\item $n_{w}=1$. The expected cost is $c_{w}+c_{\infty}-c_{l}$ (note that
$c_{l}=c_{w}$ in this case). 
\end{enumerate}
When multiple false negatives occur the {}``bad failure mode'' of
$n_{w}=1$ can occur even when there are many possible {}``right''
answers, $n_{w}>1$. One efficient way to account for this effect
is to divide the bad failure mode across all of the {}``right''
answers. 

A good importance weight is proportional to the deviation of our final
cost from $c_{w}$. When our example is of the form $x_{l}=(x,l)$,
label $y_{l}=0$ we set $i_{l}=c_{l}-c_{w}$. When our example is
of the form feature = $x_{l}=(x,l)$, label = $y_{l}=1$ we set $i_{l}=\max\left\{ \frac{c_{\infty}-c_{l}}{n_{w}},c_{w}-c_{l}\right\} $.
We can prove that these importances are sufficient to upper bound
the loss of our multiclass classifier. 

\begin{lem}
The importances of errors upper bounds the loss:\[
\forall(x,c_{1},c_{2},...,c_{k}),\,\,\, h:X\times Y\rightarrow\{0,1\}\,\,\,\,\sum_{l=1}^{k}i_{l}I(h(x,l)\neq y_{l})\geq E_{l\sim\textrm{Predict}(h,x)}c_{l}-c_{w}\]

\end{lem}
\begin{proof}
Each side is $0$ when there are no errors so the inequality is satisfied
so we need only consider the case of errors. 

There are two error cases to consider. In the first, there are no
positives, and the expected cost is $c_{\infty}$ and the difference
is $E_{l\sim\textrm{Predict}(h,x)}c_{l}-c_{w}=c_{\infty}-c_{w}$.
In this case, we must have {}``false negative'' errors for every
example which must be positive implying: \[
\sum_{l=1}^{k}i_{l}I(h(x,l)\neq y_{l})\geq\sum_{l:y_{l}=1}\frac{c_{\infty}-c_{l}}{n_{w}}=c_{\infty}-c_{w}\]


The other case is when there are $l$ for which $h(x,l)=1$. In this
case, $E_{l\sim\textrm{Predict}(h,x)}c_{l}-c_{w}=\frac{1}{\{ l:h(x,l)=1\}}\sum_{l:h(x,l)=1}c_{l}-c_{w}$.
In this setting, we can have false positives (where $y_{l}=0$ but
$h(x,l)=1$). Each false positive has a term in the leftside sum which
dominates it's contribution to the expectation on the right side:
$i_{l}=c_{l}-c_{w}\geq\frac{c_{l}-c_{w}}{\{ l:h(x,l)=1\}}$. All that
remains is proving the following when there is at least one label
$l$ for which $h(x,l)=1$ and $y_{l}=1$.\[
\sum_{l:h(x,l)=0\wedge y_{l}=1}i_{l}\geq\frac{1}{\{ l:h(x,l)=1\}}\sum_{l:h(x,l)=1\wedge y_{l}=1}c_{l}-c_{w}\]
The basic argument is that $\frac{1}{\{ l:h(x,l)=1\}}\sum_{l:h(x,l)=1\wedge y_{l}=1}c_{l}-c_{w}$
changes by less than the importance for every error. Changes are maximized
when $\{ l:h(x,l)=1\}=1$, so we will actually prove:\[
\sum_{l:h(x,l)=0\wedge y_{l}=1}i_{l}\geq\sum_{l:h(x,l)=1\wedge y_{l}=1}c_{l}-c_{w}\]


If $c_{l}>c_{w}$, then a false negative error actually decreases
the right side sum (i.e. lowers this portion of the expected cost).
Since $i\geq0$, we are done. When $c_{l}>c_{w}$, we know that $i_{l}\geq c_{w}-c_{l}$
which upper bounds the change in the right-hand side sum.
\end{proof}

\subsection{Practical Use}

To put this to practical use, we must handle two things. One of these
is coping with the lack of independence (we produce one example for
every label) associated with the map. This is can be handled by drawing
from the weighted distribution of importances over the labels on each
example. 

The other issue is $w_{x}$. It is not clear in advance how optimistic
we can reasonably be that the classifier can distinguish good classes.
Updating methods similar to the ones that Naoki is playing with seem
like a plausibly right answer.
\end{document}
