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

\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{MultiClass Cost-Sensitive Learning}

\maketitle

\section{Problem Model}

In multiclass learning, given an input $X$ from some arbitrary-but-fixed
space, we want to produce an action $a\in\{1,...,A\}$. After choosing
the label, we incur some cost (or loss), $l_{a}$.

Suppose that there is some unknown distribution $D$, generating examples,
on the space $X\times R^{+l}$. Each example has the form $(x,l_{1},l_{2},...,l_{A})$.
The goal in cost-sensitive multiclass learning is to produce a (multiclass)
classifier $c$ which minimizes the expected cost, $E_{(x,l_{1},l_{2},...,l_{A})\sim D}l_{c(x)}$.

Our goal is to reduce thie multiclass cost sensitive learning problem
to the multiclass learning problem. In the multiclass learning problem,
the distribution $D$ is over $X\times\{1,...,A\}$. In the multiclass
learning problem we seek to find a classifier $c$ which minimizes
$E_{x,a\sim D}I(c(x)\neq a)$.


\section{Method of Reduction}

Our primary tool for accomplishing a reduction is shifting the distribution
over examples. The basic difficulty with using this tool is that it
is unclear how we should shift the distribution, as there are multiple
ways that a classifier could err. Should we err against the first
failure mode, the second, or the $A-1$th? The correct answer appears
fundamentally dependent upon the classifier learning algorithm and
the example. Given this dependence, we must extract information from
the learning algorithm in order to find the correct weighting. The
proposed method for doing this is an iterative procedure.

\textbf{Cost\_to\_importance(multiclass learning algorithm A, multiclass
cost sensitive dataset $S$ )}

\textbf{Initialization}

\begin{enumerate}
\item For every $(x,l_{1},l_{2},...,l_{A})\in S$, set 
\item $i_{x}\leftarrow\max_{a}l_{a}-\min_{a}l_{a}$
\item $k_{x}\leftarrow1$
\item $a_{x}\leftarrow\textrm{argmin}_{a}l_{a}$
\end{enumerate}
\textbf{Iteration}

\begin{enumerate}
\item Let $\hat{S}$ = $\{((x,a_{x}),i_{x}):(x,l_{1},...,l_{A})\in S\}$. 
\item Let $c=A(\hat{S})$.
\item For each $(x,l_{1},l_{2},...,l_{A})\in S$ 

\begin{enumerate}
\item if $c(x)\neq a_{x}$

\begin{enumerate}
\item $i_{x}\leftarrow\frac{i_{x}k+l_{c(x)}-\min_{a}l_{a}}{k+1}$
\item $k\leftarrow k+1$
\end{enumerate}
\end{enumerate}
\item If the $l_{1}$ distance between the old $i_{x}$and the new $i_{x}$
is small then terminate. 
\item Goto 1
\end{enumerate}
\textbf{Termination}

\begin{enumerate}
\item Output the classifer $c$.
\end{enumerate}

\section{Things you can Prove}

We want to prove that this is a good reduction to importance weighted
classification. Very little can be said theoretically. In particular,
if the importance weighted classification algorithm is inimical, then
\textbf{Cost\_to\_importance} may never converge. Even when converges
happens, we can not generally guaratnee that the values $i_{x}$ are
the {}``right'' values. However, we can show these are the {}``right''
values for every example where the final solution errs.

Assume that the loss rate for any importance weighted problem is:
\[
\epsilon=E_{x,y,i\sim D}iI(c(x)\neq y)\]
There is one obvious problem with this statement: it isn't normalized.
In particular, with no constraint on the value of $i$, doubling the
value of every $i$ while keeping $\epsilon$ reduces the number of
errs. It seems unreasonable to believe that good learning algorithms
halve (in some sense) the quantity of errors when $i$ is doubled.
To remove this effect, let's assume that the above condition holds
only when: \[
E_{x,y,i\sim D}i=1\]


\begin{thm}
If $A$ has loss rate $\epsilon$ and \textbf{Cost\_to\_importance}
converges, then:\[
E_{x,c_{1},c_{2},...,c_{l}\sim D}l_{c(x)}-\min_{a}l_{a}=E_{x,y,i_{x}\sim\hat{D}}i_{x}=\epsilon\]

\end{thm}
\begin{proof}
The strong learning assumption for $A$ implies that for all $i_{x}$:\[
E_{(x,y,i_{x})}i_{x}I(c(x)\neq y)=\epsilon\]


Convergence, implies that for every example where $c(x)\neq y$, we
have $l_{c(x)}-\min_{a}l_{a}=i_{x}$. Furthermore, when $c(x)=y$,
we have $0=l_{c(x)}-\min_{a}l_{a}$. 

Since $i_{x}I(c(x)\neq y)=l_{c(x)}-\min_{a}l_{a}$ regardless of whether
$c(x)\neq y$, the expectations are the same.
\end{proof}
From the perspective of the proof, we could instead use the method:

\begin{enumerate}
\item Guess a choice of $i_{x}$
\item Check that it is consistent with the observed losses.
\end{enumerate}
Using the proposed update mechanism is hopefully more efficient than
guess-and-check, and if the learning algorithm cooperates, $i_{x}$
may converge.

What is a natural way to specify {}``the algorithm is nice and so
\textbf{Cost\_to\_importance} converges''?

Nonconvergence may motivate averaging over the nonconvergent solutions.
\end{document}
