%% 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[landscape,english]{slides}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\pagestyle{empty}
\usepackage{color}
\usepackage{graphicx}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Bold symbol macro for standard LaTeX users
\newcommand{\boldsymbol}[1]{\mbox{\boldmath $#1$}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \newcounter{slidetype}
 \setcounter{slidetype}{0}
 \newif\ifLyXsNoCenter
 \LyXsNoCenterfalse
 \newcommand{\noslidecentering}{
    \LyXsNoCentertrue%
 }
 \newcommand{\slidecentering}{
    \LyXsNoCenterfalse%
 }
 \newcommand{\lyxendslide}[1]{
    \ifLyXsNoCenter%
         \vfill%
    \fi%
    \ifcase \value{slidetype}%
         \or % no action for 0
         \end{slide} \or%
         \end{overlay} \or%
         \end{note}%
    \fi%
    \setcounter{slidetype}{0}
\visible
 }
 \AtEndDocument{\lyxendslide{.}}
 \newcommand{\lyxnewslide}[1]{
    \lyxendslide{.}
    \setcounter{slidetype}{1}
    \begin{slide}
 }

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

\lyxnewslide{af}

\begin{center}Probabilistic Error Correcting Output Codes\end{center}

\begin{center}John Langford\end{center}

\begin{center}(and Alina Beygelzimer)\end{center}


\lyxnewslide{ada}

\begin{center}Outline\end{center}

\begin{enumerate}
\item The Problem: Multiclass classification
\item A past approach: ECOC 
\item A new approach: PECOC
\item Proof of optimality
\end{enumerate}

\lyxnewslide{adfa}

\begin{center}Multiclass Classification\end{center}

Given: \textcolor{blue}{$(X,\{1,...,k\})^{*}$} = sequence of training
examples

Find: \textcolor{blue}{$c_{M}:X\rightarrow\{1,...,k\}$} = multiclass
classifier approximately minimizing \textcolor{blue}{$\Pr_{x,y\sim D}(c_{M}(x)\neq y)$}
= probability of error.

Note: \textcolor{blue}{$D$} is unknown. (Key difference between learning
and optimization)

Note: No assumption here that \textcolor{blue}{$D$} generating training
examples = \textcolor{blue}{$D$} tested on. 


\lyxnewslide{adfa}

\begin{center}ECOC: A Tempting Solution\end{center}

Use Binary learning algorithms \textcolor{blue}{$A:(X,\{0,1\})^{*}\rightarrow(X\rightarrow\{0,1\})$}
to solve Multiclass classification.

\vspace{-0.5cm}

\includegraphics{ecoc.eps}

\vspace{-1cm}

Binary training data = \textcolor{blue}{$\{(x,I(y_{M}\in\textrm{set}):(x,y_{M})\in\textrm{multiclass data}\}$}

Multiclass prediction = closest label vector (ties $\Rightarrow$
randomize).


\lyxnewslide{adfa}

\begin{center}ECOC Analysis and Issues\end{center}

Theorem: For all \textcolor{blue}{$k$}, For all \textcolor{blue}{$D$}
on \textcolor{blue}{$(x,y_{M})$}, \textcolor{blue}{\[
\Pr(\textrm{ECOC errs})\leq4\textrm{(average binary error rate)}\]
}

Proof: Exists code such that \textcolor{blue}{$<\frac{1}{4}$} binary
errs $\Rightarrow$ no error

Caveats:

\begin{enumerate}
\item Arbitrary ECOC may make {}``impossible'' binary problems.
\item For arbitrary \textcolor{blue}{$D$} binary error rate \textcolor{blue}{$\leq0.25$}
might be impossible.
\end{enumerate}
PECOC addresses 2 but not 1.


\lyxnewslide{adfaf}

\begin{center}ECOC Inconsistency\end{center}

Theorem: There exists a family of \textcolor{blue}{$D$} s.t. ECOC
is suboptimal even with perfect binary classifiers.

Suppose: \textcolor{blue}{$D(1|x)=0.46$}, \textcolor{blue}{$D(2|x)=0.45$},
\textcolor{blue}{$D(3|x)=0.09$}

\includegraphics{ecoc_imperfect.eps} \vspace{-1cm}

Finite set of bits $\Rightarrow$ not enough bits to make optimal
decision. PECOC fixes this.


\lyxnewslide{adfaf}

\begin{center}PECOC, Defined\end{center}

As ECOC, except binary classifiers make \emph{probabilistic} predictions.

Still reduction to binary classification with Probing subroutine.

To predict: Use \textcolor{blue}{$l_{1}$} closest label/codeword.

\includegraphics{pecoc_perfect.eps}


\lyxnewslide{adfa}

\begin{center}PECOC Optimality\end{center}

Theorem: For all \textcolor{blue}{$k$}, For all \textcolor{blue}{$D$}
on \textcolor{blue}{$(x,y_{M})$}, \textcolor{blue}{\[
\Pr(\textrm{PECOC errs})-\Pr(\textrm{Optimal errs)}\]
\[
\leq2\sqrt{2(\textrm{average Binary error}-\textrm{minimum average Binary error})}\]
\[
\equiv2\sqrt{2(\textrm{relative Binary error}})\]
}

- Binary consistency $\Rightarrow$ Multiclass consistency

- Binary error rate $=0.25$ OK whe minimum error rate $=0.25$


\lyxnewslide{sf}

\begin{center}Proof: when things are perfect\end{center}

Proof: Pick code using all \textcolor{blue}{${k \choose k/2}$} subsets.

For all labels \textcolor{blue}{$l$}, without errors, \textcolor{blue}{\[
\sum_{b\in\textrm{Binary Problems}}\textrm{Probing}_{b}(\textrm{set containing }l|x)\]
\[
=\sum_{b\in\textrm{Binary Problems}}\left[\sum_{l'\in\textrm{set containing l}}\Pr(l'|x)\right]\]
\[
=|\{ b\}|(\Pr(l|x)+\frac{1}{2}\sum_{l'\neq l}\Pr(l'|x))=|\{ b\}|\frac{\Pr(l|x)+1}{2}\]
}


\lyxnewslide{d}

\begin{center}Proof: The real case\end{center}

From Probing analysis, \textcolor{blue}{\[
E_{x,y\sim D}|D(1|x)-\textrm{Probing}(x)|\leq\sqrt{2\textrm{relative Binary error}}\]
}

Most efficient method to disturb \textcolor{blue}{$\sum$} by \textcolor{blue}{$|\{ b\}|\frac{\epsilon}{2}$}
is for each call to probing to err by \textcolor{blue}{$|D(1|x)-\textrm{Probing}(x)|=\frac{\epsilon}{2}$}.

Changing sum by \textcolor{blue}{$|\{ b\}|\frac{\epsilon}{2}$} $\Rightarrow$
choosing class with error rate at most \textcolor{blue}{$2\epsilon$}
worse than minimum.

Adding pieces together $\Rightarrow$ proof.


\lyxnewslide{adfaf}

\begin{center}Bonus: Probabilistic Output\end{center}

Instead of outputting \textcolor{blue}{\[
\arg\max_{l}\sum_{b\in\textrm{Binary Problems}}\textrm{Probing}_{b}(\textrm{set containing }l|x)\]
}

Output \textcolor{blue}{$\hat{p}(l|x)=\frac{2\sum_{b\in\textrm{Binary Problems}}\textrm{Probing}_{b}(\textrm{set containing }l|x)}{\{|b|\}}-1$}

Bonus Theorem: For all \textcolor{blue}{$k$}, For all \textcolor{blue}{$D$}
on \textcolor{blue}{$(x,y_{M})$},\textcolor{blue}{\[
\forall l\,\,|\hat{p}(l|x)-D(l|x)|\leq\sqrt{2(\textrm{relative Binary error}}\]
 }

Proof: Already done.


\lyxnewslide{dafa}

\begin{center}Remaining Issues\end{center}

Experiments: How well does this work in practice?

Which code do you use in practice?

Shannon $\Rightarrow$ a random code of size \textcolor{blue}{$O(\log k)$}
is near optimal for above theory.

... but a random code may make hard binary problems.
\end{document}
