\documentclass[twoside,11pt]{llncs}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{epsfig}
\usepackage{natbib}
\usepackage{graphicx}
\bibliographystyle{plainnat}
%\input{localdeclarations}
\input epsf

\newtheorem{construction}{Construction}
\newtheorem{slaim}{Claim}
\newtheorem{sublemma}{Sublemma}

\newcommand{\commentout}[1]{}
\newcommand{\naturals}{\ensuremath{\mathbb N}}
\newcommand{\cX}{\ensuremath{{\cal X}}}
\newcommand{\cY}{\ensuremath{{\cal Y}}}
\newcommand{\cZ}{\ensuremath{{\cal Z}}}
\newcommand{\cC}{\ensuremath{{\cal C}}}
\newcommand{\cP}{\ensuremath{{\cal P}}}
\newcommand{\cA}{\ensuremath{{\cal A}}}
\newcommand{\cB}{\ensuremath{{\cal B}}}
\newcommand{\cD}{\ensuremath{{\cal D}}}
\newcommand{\condent}{H}
\newcommand{\erateS}{\hat{e}_S}
%peter2-added
\newcommand{\erateShard}{\hat{e}_{S,\text{h}}}
\newcommand{\erateSeasy}{\hat{e}_{S,\text{easy}}}
\newcommand{\Shard}{S_{\text{h}}}
%
\newcommand{\erateD}{e_D}
\newcommand{\ebad}{e_{\text{bad}}}
\newcommand{\KL}{\text{\sc KL}}
\newcommand{\cbayesopt}{c_{D \text{\sc -opt}}}
\newcommand{\ebayes}{e_D(c_{\text{\sc Bayes}(P,S)})}
\newcommand{\emap}{e_D(c_{\text{\sc map}(P,S)})}
\newcommand{\esmap}{e_D(c_{\text{\sc smp}(P,S)})}
\newcommand{\hesmapb}{\hat{e}_S(c^*)}
\newcommand{\he}{\hat{e}_S(c)}
\newcommand{\emdl}{e_D(c_{\text{\sc mdl}(P,S)})}
\newcommand{\eorb}{e_D(c_{\text{\sc orb}(P,S)})}
\newcommand{\cbayes}{c_{\text{\sc Bayes}(P,S)}}
\newcommand{\cbayesi}{c_{\text{\sc Bayes}(P,S^{i-1})}}
\newcommand{\cmap}{c_{\text{\sc map}(P,S)}}
\newcommand{\csmap}{c_{\text{\sc smp}(P,S)}}
\newcommand{\csmapb}{c_{\text{\sc smp}}}
\newcommand{\cmdl}{c_{\text{\sc mdl}(P,S)}}
\newcommand{\corb}{c_{\text{\sc orb}(P,S)}}

\newcommand{\femdl}{e_{f(c)}(c_{\text{\sc mdl}(P,S)})}
\newcommand{\feorb}{e_{f(c)}(c_{\text{\sc orb}(P,S)})}
\newcommand{\febayes}{e_{f(c)}(c_{\text{\sc Bayes}(P,S)})}
\newcommand{\femap}{e_{f(c)}(c_{\text{\sc map}(P,S)})}
\newcommand{\fesmap}{e_{f(c)}(c_{\text{\sc smp}(P,S)})}

\newcommand{\phard}{p_{\text{h}}}
%\newcommand{\muhard}{\mu_{\text{h}}}
\newcommand{\Mhard}{M_{\text{h}}}
\newcommand{\mhard}{m_{\text{h}}}


\newcommand{\psmall}{p_{\text{small}}}
\newcommand{\pmiddle}{p_{\text{middle}}}
\newcommand{\plarge}{p_{\text{large}}}


% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

% Short headings should be running head and authors last names

\title{Suboptimal Behavior of Bayes and MDL \\
in Classification under Misspecification}

%\author{Peter Gr\"unwald (pdg@cwi.nl), CWI Amsterdam, The Netherlands \\
%  John Langford (jl@hunch.net), TTI-Chicago, Chicago, USA}
\author{Peter Gr\"unwald\inst{1} \and John Langford\inst{2}}
\institute{CWI Amsterdam,
\email{pdg@cwi.nl}, \texttt{www.grunwald.nl}.
\and TTI-Chicago,  \email{jl@hunch.net}, \texttt{hunch.net/\~\/jl/}.}

\setcounter{secnumdepth}{3}
%to make sure that subsubsections get a number again!
\pagestyle{plain}
\thispagestyle{plain}
%remove again in final version!

\begin{document} 
\maketitle 
 
\begin{abstract} 
  We show that forms of Bayesian and MDL inference that are often
  applied to classification problems can be {\em inconsistent}.  This
  means that there exists a learning problem such that for all amounts
  of data the generalization errors of the MDL classifier and the
  Bayes classifier relative to the Bayesian posterior both remain
  bounded away from the smallest achievable generalization error. From
  a Bayesian point of view, the result can be reinterpreted as saying
  that Bayesian inference can be inconsistent under misspecification,
  even for countably infinite models. We extensively discuss the
  result from both a Bayesian and an MDL perspective.
\end{abstract}

\section{Introduction}
Overfitting is a central concern of machine learning and
statistics. Two frequently used learning methods that in many cases
`automatically' protect against overfitting are Bayesian inference
\citep{BernardoS94} and the Minimum Description Length (MDL) Principle
\citep{Rissanen89,BarronRY98,Grunwald05,Grunwald07}.  We show that, when applied
to classification problems, some of the standard variations of these
two methods can be {\em inconsistent\/} in the sense that they {\em
asymptotically overfit\/}: there exist scenarios where, no matter how
much data is available, the generalization error of a classifier based
on MDL or the full Bayesian posterior does not converge to the minimum
achievable generalization error within the set of classifiers under
consideration.

This result may be viewed as a challenge to Bayesian inference.  Given
a powerful piece of information (an objectively correct ``prior'' on a
set of {\em classifiers\/}), transforming this information into a
Bayesian prior on a set of {\em distributions\/} in a straightforward
manner and applying Bayes rule yields significantly suboptimal
behavior -- while another simple approach yields optimal behavior.  The key is
the transformation from classifiers (functions mapping each input $X$
to a discrete class label $Y$) to (conditional) distributions. Such a
transformation is necessary because Bayes rule cannot be directly
applied to classifiers.  We do the conversion in a straightforward
manner, crossing a prior on classifiers with a prior on error rates
for these classifiers. 
%peter2 This conversion method is completely standard 
This conversion method is a completely standard tool for Bayesians
active in the field of machine learning
%
-- we tested this with some professing Bayesians, see
Section~\ref{sec:bayestest} -- yet it inevitably leads to (sometimes
subtly) `misspecified' probability models not containing the `true'
distribution $D$. The result may therefore be re-interpreted as
`Bayesian inference can be inconsistent under
misspecification for common classification probability models'.
Since, in practice, Bayesian inference for classification tasks is
frequently and inevitably based on misspecified probability models,
the result remains relevant even if (as many Bayesians do, especially
those not active in the field of machine learning) one insists
that inference starts directly with a probability model, rather than a
classification model that is then transformed into a probability model
-- see Section~\ref{sec:bayes}. 


There are two possible resolutions to this challenge.  Perhaps
Bayesian inference is an incomplete characterization of learning:
there exist pieces of information (e.g. prior information on
deterministic classifiers rather than distributions) which can not be well
integrated into a prior distribution and so learning algorithms other
than Bayesian inference are sometimes necessary.  Or, perhaps there is
some less naive method allowing a prior to express the available
information. We discuss this issue further in Section~\ref{sec:bayes}.
%peter1 end of changed part


\commentout{
%peter1 we are so careful now that this is not needed any more.
\paragraph{Some Caveats and Warnings} Our result must be interpreted
carefully. There exist many different versions of MDL and Bayesian
inference, only some of which are covered. For the case of MDL, we
show the result for a two-part form of MDL that has often been used
for classification, see Section~\ref{sec:mdl}.  For the case of Bayes,
the result may appear to contradict some well-known Bayesian
consistency results \citep{BlackwellD62}.  Indeed, the result only
applies to a `pragmatic' use of Bayes involving a transformation of classifiers to conditional distributions. 
%peter1 moved this piece up
  Indeed, the result only applies to a `pragmatic' use of Bayes, where
  the set of hypotheses under consideration are {\em classifiers}:
  functions mapping each input $X$ to a discrete class label $Y$. To
  apply Bayes rule, these classifiers must be converted into
  conditional probability distributions.  We do this conversion in a
  standard manner, crossing a prior on classifiers with a prior on
  error rates for these classifiers.  } 
\subsection{A Preview}
\subsubsection{Classification Problems}
A classification problem is defined on an input (or feature) domain
$\cX$ and output domain (or class label) $\cY = \{0,1\}$.  The problem
is defined by a probability distribution $D$ over $\cX
\times \cY$. A classifier is a function
$c: \cX \rightarrow \cY$.  The error
rate of any classifier is quantified as:
$$\erateD(c) = E_{(x,y) \sim D} I(c(x) \neq y)$$ 
where $(x,y) \sim D$ denotes
a draw from the distribution $D$ and $I(\cdot)$ is the indicator
function which is $1$ when its argument is true and $0$ otherwise.

The goal is to find a classifier which, as often as possible according to $D$,
correctly predicts the class label given the input feature.
Typically, the classification problem is solved by searching for some
classifier $c$ in a limited subset $\cC$ of all classifiers using a
sample $S = (x_1,y_1), \ldots, (x_m,y_m) \sim D^m$ 
generated by $m$ independent draws from
the distribution $D$.  Naturally, this search is guided by the
{\em empirical error rate}. This is the error rate on the subset $S$ defined by:
$$
\erateS(c) := 
E_{(x,y) \sim S} I(c(x)\neq y) = \frac{1}{|S|} \sum_{(x,y)\in S} I(c(x) \neq y).
$$ where $(x,y) \sim S$ denotes a sample drawn from the uniform
distribution on $S$.  Note that $\erateS(c)$ is a random variable
dependent on a draw from $D^m$. In contrast, $\erateD(c)$ is a number (an
expectation) relative to $D$.

\subsubsection{The Basic Result}
The basic result is that certain classifier learning algorithms may
not behave well as a function of the information they use, even when
given infinitely many samples to learn from.  The learning algorithms
we analyze are ``Bayesian classification'' (Bayes), ``Maximum a
Posteriori classification'' (MAP), ``Minimum Description Length
classification'' (MDL) and ``Occam's Razor Bound classification''
(ORB).  These algorithms are precisely defined later. Functionally
they take as arguments a training sample $S$ and a ``prior'' $P$ which
is a probability distribution over a set of classifiers $\cC$.  The
result applies even when the process creating classification problems
draws the optimal classifier from $P(c)$.  In Section~\ref{sec:result}
we state the basic result, Theorem~\ref{thm:bayesinconsistent}. The
theorem has the following corollary, indicating suboptimal behavior of
Bayes and MDL:
\commentout{
\begin{corollary}
  \label{cor:inconsistent}
        {\bf (Classification Inconsistency) \ } There exists an input
        domain ${\cal X}$ and an (objectively correct) prior $P(c)$ on
        a countable set of classifiers $\cC$ such that the Bayesian
        classifier $\cbayes$, the MAP classifier $\cmap$, and the MDL
        classifier $\cmdl$ are asymptotically suboptimal with respect
        to the ORB classifier $\corb$. That is:
\begin{multline}
\lim_{m \rightarrow \infty} \Pr_{S \sim D^m} \left(
 \eorb + 0.1 < \min \{ \ebayes, \emap, \emdl \}  \right) = 1.
\end{multline}
\end{corollary}
}
\begin{corollary}
  \label{cor:inconsistent}
        {\bf (Classification Inconsistency) \ } There exists an input
        domain ${\cal X}$ and a prior $P(c)$ on
        a countable set of classifiers $\cC$ such that:
\begin{description}
\item[\rm 1. (inconsistency according to true distribution)] There exists a learning problem (distribution) $D$ such that the Bayesian
        classifier $\cbayes$, the MAP classifier $\cmap$, and the MDL
        classifier $\cmdl$ are asymptotically suboptimal with respect
        to the ORB classifier $\corb$. That is, for $c^* \in \{ \cbayes, \cmap, \cmdl \}$, 
\end{description}
\begin{equation}
\label{eq:hulk}
\lim_{m \rightarrow \infty} \Pr_{S \sim D^m} \left(
 \eorb + 0.05 < e_D(c^*) \right) = 1.
\end{equation}
\begin{description}
\item[\rm 2. (inconsistency according to prior)] 
There exists a randomized algorithm selecting learning problems $D$ in
such a way that
\subitem(a) the prior $P(c)$ is `objectively correct' in the
sense that, for all $c \in \cC$, with probability $P(c)$, $c$ is the optimal classifier,
achieving $\min_{c \in \cC} e_D(c)$.
\subitem(b) {\rm (\ref{eq:hulk})} holds no matter what learning problem $D$/classifier
$c$ is selected. In particular, {\rm (\ref{eq:hulk})} holds with prior
probability 1.
\end{description}
\end{corollary}
How dramatic is this result? We may ask
\begin{enumerate}
\item Are the priors $P$ for
which the result holds natural? 
\item How large can the suboptimality
become and how small can $\eorb$ be? 
\item Does this matter for logarithmic loss (which is what MDL approaches seek to minimize \citep{Grunwald07}) rather than 0-1 loss? 
\item Is $\corb$ an algorithm which
contains information specific to the distribution $D$? 
\item Is this
theorem relevant at small (and in particular noninfinite) sample
sizes?  
\end{enumerate}
We will ask a number of more detailed questions from a Bayesian
perspective in Section~\ref{sec:bayes} and from an MDL perspective in
Section~\ref{sec:mdl}.  The short answer to (1) and (2) is: the priors
$P$ have to satisfy several requirements, but they correspond to
priors often used in practice. The size of the suboptimality can be
quite large, at least for the MAP and MDL classifiers (the number of
$0.05$ 
%peter1 changed this.
was just chosen for concreteness;
other values are possible) and $\eorb$ can be quite small - see
Section~\ref{sec:technical} and Figure~\ref{fig:allowed}.  The short
answer to (3) is ``yes''.  A similar result holds for logarithmic
loss,  see Section~\ref{sec:bayescons}.

The answer to (4) is ``no''.  The algorithm $\corb$, which minimizes
the Occam's Razor bound (ORB) (see \citep{BlumerEHW87} or
Section~\ref{sec:orb}), is asymptotically consistent for any $D$:
\begin{theorem}
  \label{thm:consistent}
        {\bf (ORB consistency) \ } For all priors $P$ nonzero on a set
        of classifiers $\cC$, for all learning problems $D$, and all constants
        $K> 0$ the ORB classifier $\corb$ 
is asymptotically $K$-optimal:
        
        $$ 
        \lim_{m \rightarrow \infty} \Pr_{S \sim D^m} \left(\eorb > K + \inf_{c \in \cC} \erateD(c) \right) = 0.$$
\end{theorem}

The answer to (5) is that the result is very relevant for small sample
sizes because the convergence to the probability 1 event occurs at a
speed exponential in $m$.  Although the critical example uses a
countably infinite set of classifiers, on a finite set of $n$
classifiers, the analysis implies that for $m < \log n$, Bayesian
inference gives poorer performance than Occam's Razor Bound
optimization.
\paragraph{Overview of the Paper}
The remainder of this paper first defines precisely what we mean by
the above classifiers. It then states the main inconsistency theorem
which implies the above corollary, as well as a theorem that provides
an upper-bound on how badly Bayes can behave. In
Section~\ref{sec:proofs} we prove the theorems.  Technical discussion,
including variations of the result, are discussed in
Section~\ref{sec:technical}. A discussion of the result from a
Bayesian point of view is given in Section~\ref{sec:bayes}, and from
an MDL point of view in Section~\ref{sec:mdl}.
\section{Some Classification Algorithms}
\label{sec:algorithms}
The basic inconsistency result is about particular classifier learning
algorithms which we define next.
\subsection{The Bayesian Classification algorithm}
The Bayesian approach to inference starts with a prior probability
distribution $P$ over a set of distributions $\cP$. $P$  typically
represents a measure of ``belief'' that some $p \in \cP$ is the
process generating data.  Bayes' rule states that, given sample data $S$, 
the posterior
probability $P(\cdot \mid S)$ 
that some $p$ is the process generating the data
is:
\begin{equation}
\label{eq:bayesrules}
P(p \mid S) =\frac{p(S)P(p)}{P(S)}.
\end{equation}
where $P(S) := E_{p \sim P} [p(S)] = \sum_{p \in \cP} P(p)p(S)$, the sum being replaced by an integral when $\cP$ is continuous and $P$ admits a density. 
Note that in Bayesian statistics, $p(S)$ is usually denoted as $P(S \mid p)$.

In classification problems with sample size $m = |S|$, 
each $p \in \cP$ is a distribution  on $(\cX \times \cY)^m$ 
and the outcome $S=(x_1,y_1), \ldots, (x_m,y_m)$ is the sequence
of labeled examples.

If we intend to perform classification based on a set of classifiers
$\cC$ rather than distributions $\cP$, it is natural to introduce a
``prior'' $P(c)$ that a particular classifier $c: \cX \rightarrow
\{0,1\}$ is the best classifier for solving some learning problem.
This, of course, is \emph{not} a Bayesian prior in the conventional
sense because classifiers do not induce a measure over the training
data. 
%peter: I felt a few lines were missing here! Added some extra explanation
In order to apply Bayesian inference, we somehow need to convert the
set of classifiers into a corresponding set of distributions $\cP$.
With such a conversion, the prior $P(c)$ will induce a conventional
Bayesian prior on $\cP$ after all.  
%peter: end of added part
%It is the standard method of converting a ``prior'' over
%classifiers into a Bayesian prior over distributions on the
%observations which the inconsistency result applies to.

One common conversion \citep{Jordan95,Tipping01,Grunwald98b}
transforms the set of classifiers $\cC$ into a simple logistic
regression model -- the precise relationship to logistic regression is
discussed in Section~\ref{sec:trafo}.  In the special case 
considered in this paper, $c(x) \in \{0,1\}$ is binary valued.
Then (but only then) the conversion amounts to
assuming that the error rate $\theta$ of the optimal classifier is
independent of the feature value $x$. This is known as
``homoskedasticity'' in statistics and ``label noise'' in learning
theory.  More precisely,
%peter3 changed
we let ${\cal P}$ consist of the set of distributions $p_{c,\theta}$,
where $c \in {\cal C}$ and $\theta \in [0,1]$. These are defined as
conditional probability distributions over the labels given the
unlabeled data:
\begin{equation}
\label{eq:regmodel}
p_{c,\theta}(y^m  \mid x^m) =
\theta^{m \hat{e}_S(c)} (1- \theta)^{m - m \erateS(c)}.
\end{equation}
This expresses that there exists some $\theta$ such that  $\forall
x\,\,\, P_{c,\theta}(c(X) \neq y \mid  X=x) = \theta$. (homoskedasticity). 
Note that
$$p_{c,\theta}(y |x) = \begin{cases} 
\theta & \text{if $c(x) \neq y$} \\
1- \theta & \text{if $c(x) = y$}.
\end{cases}
$$ 
For each fixed $\theta < 0.5$, the log likelihood
$\log p_{c,\theta}(y^m \mid x^m)$ is linearly decreasing in the empirical
error that $c$ makes on $S$. 
By differentiating with respect to
$\theta$, we see that for fixed $c$, the likelihood
(\ref{eq:regmodel}) is maximized by setting $\theta :=
\erateS(c)$, giving
\begin{equation}
\label{eq:safe}
 \log \frac{1}{p_{c,\erateS(c)}(y^m \mid x^m)} = m H(\hat{e}_S(c)),
\end{equation}
where $H$ is the binary entropy $H(\mu) = \mu \log \frac{1}{\mu} + (1-
\mu) \log \frac{1}{1- \mu}$, which is strictly increasing for $\mu \in
[0,0.5)$. Here, as everywhere else in the paper, $\log$ stands for
binary logarithm.
%peter: added
Thus, the conversion is ``reasonable'' in the sense that, both with
fixed $\theta < 0.5$ and with the likelihood-maximizing $\theta =
\erateS(c)$ which varies with the data, the likelihood is a decreasing
function in the empirical error rate of $c$, so that classifiers which
achieve small error on the data correspond to a large likelihood of
the data.
%

We further assume that {\em some\/} distribution $p_x$ on
${\cal X}^m$ generates the $x$-values, and, in particular that
this distribution is independent of $c$ and $\theta$. With this assumption, 
we can apply
Bayes rule to get a posterior on $p_{c,\theta}$, denoted as
$P(c,\theta \mid S)$, without knowing $p_x$, since the
$p_x(x^m)$-factors cancel:
\begin{equation}
\label{eq:bayes}
P({c,\theta} \mid S) = \frac{p_{c,\theta}(y^m | x^m)p_x(x^m)P(c,\theta)}{P(y^m \mid x^m) p_x(x^m)} =
\frac{p_{c,\theta}(y^m|x^m)P(c,\theta)}{E_{{c,\theta} \sim P}
  [p_{c,\theta}(y^m \mid x^m)] }.
\end{equation}
As is customary in Bayesian statistics, here as well as in the
remainder of this paper we defined the prior $P$ over $(c,\theta)$
rather than directly over $p_{c,\theta}$. The latter choice would be
equivalent but notationally more cumbersome.

To make (\ref{eq:bayes})
applicable, we need to specify a prior measure on the joint space $\cC
\times [0,1]$ of classifiers and $\theta$-parameters. In the next
section we discuss the priors under which the theorems hold. 

Bayes rule (\ref{eq:bayes}) is formed into a classifier learning
algorithm by choosing the most likely label given the input $x$ and
the posterior $P(\cdot|S)$:
\begin{equation}
\label{eq:bayesact}
\cbayes(x) := \begin{cases}
1 & \text{if} \ E_{{c,\theta} \sim P(\cdot \mid S)} \/[ p_{c,\theta}(Y =
1|X=x) ] > 
\frac{1}{2}, \\
0  & \text{if} \ E_{{c,\theta} \sim P(\cdot \mid S)} \/[ p_{c,\theta}(Y =
1|X=x) ] < 
\frac{1}{2}.
\end{cases}
\end{equation}
%peter2 changed (need this extended formulation now in proof of theorem 2)
If $E_{{c,\theta} \sim P(\cdot \mid S)} \/[ p_{c,\theta}(Y =
1|X=x) ] = 
\frac{1}{2}$, then the value of $\cbayes$ is determined by 
an independent toss of a fair coin. 
\subsection{The MAP classification algorithm}
The integrations of the full Bayesian classifier can be too
computationally intensive, so in practice one often predicts using the 
Maximum A Posteriori (MAP) classifier.  This classifier is given by:
$$
\cmap = 
\arg \max_{c \in \cC} \max_{\theta \in [0,1]} P(c,\theta \mid S) = 
\arg \max_{c \in \cC} \max_{\theta \in [0,1]} 
p_{c,\theta}(y^m \mid x^m)P(c,\theta)
$$
with ties broken arbitrarily. Integration over $\theta \in [0,1]$ 
is easy compared to summation over $c \in
\cC$, so one sometimes uses a 
learning algorithm (SMP) which integrates over 
$\theta$ (like full Bayes) but maximizes over $c$ (like MAP):
$$
\csmap  = 
\arg \max_{c \in \cC} P(c \mid S) =
\arg \max_{c \in \cC}
E_{\theta \sim P(\theta)} p_{c,\theta}(y^m \mid x^m) P(c \mid \theta).
$$
\subsection{The MDL Classification algorithm}
The MDL approach to classification is transplanted from the MDL
approach to density estimation.  There is no such thing as a
`definition' of MDL for classification because the
transplant has been performed in various ways by various authors.
Nonetheless, as we discuss in Section~\ref{sec:mdl}, many implementations are essentially equivalent to the
following algorithm \citep{QuinlanR89,Rissanen89,KearnsMNR97,Grunwald98b}:
\begin{equation}
\label{eq:cmdl}
\cmdl = 
\arg \min_{c \in \cC} \ \left\{ \ 
\log \frac{1}{P(c)} + \log \binom{m}{m\hat{e}_S(c)} \ \right\}.
\end{equation}
The quantity minimized has a coding
interpretation: it is the number of bits required to describe the
classifier plus the number of bits required to describe the labels on
$S$ given the classifier and the unlabeled data. We call $- \log
P(c) + \log \binom{m}{m \hat{e}_S(c)}$ the {\em two-part MDL
  codelength\/} for encoding data $S$ with classifier $c$.


\section{Main Theorems} 
\label{sec:result}
We prove inconsistency for some countable set of classifiers
${\cal C} = \{c_0, c_1, \ldots \}$ which we define later. The
inconsistency is attained for priors with `heavy tails'. Formally, for
Theorem~\ref{thm:bayesinconsistent} (inconsistency of Bayes, MDL, MAP
and SMP), we
require $P(c_k)$ to be such 
that  for all $k$,
\begin{equation}
\label{eq:priora}
\log \frac{1}{P(c_k)} \leq \log k + o( \log k).
\end{equation} 
This condition is satisfied, for example, by Rissanen's (1983) \nocite{Rissanen83} {\em
  universal prior for the integers}. Another simple
prior satisfying (\ref{eq:priora}) can be defined as follows:
group the classifiers $c_1, c_2, \ldots$ as $\cC_0 := \{ c_1 \}$,
$\cC_1 := \{ c_2, c_3 \}$, $\cC_2 := \{ c_4, \ldots, c_7 \}$ and so
on, so that $\cC_a$ contains $2^a$ classifiers. Then the prior of any
classifier in $\cC_a$ is defined as $$P(c) = \frac{1}{a(a+1)}
2^{-a}.$$
The sensitivity of our results to the choice of prior is
analyzed further in Section~\ref{sec:technical}.  The prior on
$\theta$ can be any distribution $P$ on $[0,1]$ with a 
density $w$ that is continuously
differentiable and bounded away from $0$ on $[0,0.5)$, i.e. for some
$\gamma > 0$,
\begin{equation}
\label{eq:priorb}
\text{for all $\theta \in [0,0.5)$}, w(\theta ) > \gamma.
\end{equation} 
For example, we may take the uniform distribution on $[0,1]$ with $w(\theta)
\equiv 1$. We can also take the uniform distribution on $[0,0.5)$,
with $w(\theta) \equiv 2$. 

For our result concerning the full Bayesian classifier,
Theorem~\ref{thm:bayesinconsistent}, Part (b), we need to make the
further restriction\footnote{Without this restriction, we may put
  nonzero prior on distributions $p_{c,\theta}$ with $\theta > 1/2$.
  For such distributions, the log likelihood of the data increases
  rather than decreases as a linear function of the error that $c$
  makes on the data. This implies that with a uniform prior, under our
  definition of the Bayes MAP classifier, in some cases the MAP
  classifier may be the classifier with the largest, rather than the
  smallest empirical error. As pointed out by a referee, for this
  reason the term ``Bayes MAP classifier'' may be somewhat of a
  misnomer: it does not always coincide with the Bayes act
  corresponding to the MAP distribution. If one insists on defining
  the Bayes MAP classifier as the Bayes act corresponding to the MAP
  distribution, then one can achieve this simply by restricting oneself to priors
  satisfying (\ref{eq:restrictedprior}), since all our results still
  hold under the restriction (\ref{eq:restrictedprior}).}
%peter2 added the above
\begin{equation}
\label{eq:restrictedprior}
P(\theta \geq 0.5) = 0.
\end{equation}
For ease of comparison
with other results (Section~\ref{sec:bayes}), we shall also allow
discrete priors on $\theta$ that put all their mass on a countable
set, $[0,1] \cap {\mathbb Q}$. For such priors, we require that they satisfy, for all $a \in
\naturals$, all $b \in \{0, 1, \ldots, \lfloor a/2 \rfloor \}$:
\begin{equation}
\label{eq:discreteprior}
P\left(\theta = \frac{b}{a}\right) \geq K_1 a^{-K_2}
\end{equation}
for some fixed constants $K_1, K_2 > 0$. An example of a prior
achieving (\ref{eq:discreteprior}) is $P(\theta = b/ a) =
1/(a(a+1)\lfloor a/2 +1 \rfloor)$.

We assume that the priors $P(\theta)$ on
$[0,1]$ and the prior $P(c)$ on $\cC$ are fully dependent so that
every classifier can have its own error rate. We require each
classifier to have the same prior for $\theta$. Thus, $P(c,\theta) =
P(c) P(\theta|c)$ where for every $c$, $P(\theta |c)$ is set to
$P(\theta)$.  Note that given a sample $S$, the posterior $P(\theta
\mid c, S)$ can depend on $c$.  In the theorem, $H(\mu) = \mu \log
\frac{1}{\mu} + (1- \mu) \log \frac{1}{1- \mu}$ stands for the binary
entropy of a coin with bias $\mu$.
%peter2 added
The function $g(\mu)$ appearing in Part (b) of the theorem is defined
as
\begin{equation}
g(\mu) = \mu + \sup \ \{\nu \mid \nu \geq 0 \; ; \; H(\nu) < H(\mu) - 2 \mu
\}.
\end{equation}
%
This function will be analyzed later. 
\begin{theorem}
\label{thm:bayesinconsistent}
{\bf (Classification Inconsistency) \ } There exists an input space
${\cal X}$ and a countable set of classifiers ${\cal C}$ such that the
following holds: let $P$ be any prior satisfying (\ref{eq:priora}) and
(\ref{eq:priorb}).
%peter2 TODO CHECK DEFINITION 
Then, for all $\mu \in (0,0.5)$,
\begin{description}
\item[(a)] For all $\mu' \in
[\mu,H(\mu)/2)$, there exists a $D$ with $\min_{c\in \cC} \erateD(c) =
\erateD(c_0) =
\mu$ such that, for all large $m$, with $a_m =  3 \exp(- 2 \sqrt{m})$,
\begin{eqnarray}
\label{eq:batman}
\Pr_{S \sim D^m} \left( \emap = \mu' \right) & \geq & 1 - a_m 
\nonumber \\
\Pr_{S \sim D^m} \left(\esmap = \mu' \right) & \geq & 1 - a_m 
\nonumber \\
\Pr_{S \sim D^m} \left(\emdl = \mu' \right) & \geq & 1 - a_m. 
\end{eqnarray}
\item[(b)]  If the prior $P$ further satisfies (\ref{eq:restrictedprior}), then for all $\mu' \in
[\mu,g(\mu))$, there exists a $D$ with $\min_{c\in \cC} \erateD(c) =
\erateD(c_0) =
\mu$ such that, for all large $m$,  with $a_m =  (6+o(1)) \exp(-(1- 2 \mu) \sqrt{m})$,
\begin{equation}
\Pr_{S \sim D^m} \left(
        \ebayes \geq \mu' \right) \geq  1 -a_m.
\end{equation}
\end{description}
\end{theorem}
%peter2 changed statement of theorem to reflect changed result for
%full Bayes
%peter2 added some text
Since $H(\mu)/2 > \mu$ for all $\mu \in (0,0.5)$
(Figure~\ref{fig:allowed}), inconsistency of $\cmap$, $\csmap$ and
$\cmdl$  can occur for all $\mu \in (0,0.5)$. 
%
The theorem states that Bayes is inconsistent for \emph{all large} $m$
on a fixed distribution $D$.  This is a significantly more difficult
statement than ``for all (large) $m$, there exists a learning problem
where Bayes is inconsistent''.\footnote{In fact, a meta-argument can be
  made that \emph{any} nontrivial learning algorithm is `inconsistent'
  in this sense for finite $m$.} Differentiation of $0.5 H(\mu) -\mu$
shows that the maximum discrepancy between $\emap$ and $\mu$ is
achieved for $\mu = 1/5$. With this choice of $\mu$, $0.5 H(\mu) - \mu
= 0.1609\ldots$ so that, by choosing $\mu'$ arbitrarily close to
$H(\mu)$, the discrepancy $\mu' - \mu$ comes arbitrarily close to $
0.1609\ldots$. These findings are summarized in
Figure~\ref{fig:allowed}.
%peter2 added
Concerning $\cbayes$, since $H(\mu) - 2\mu > 0$ for all $\mu \in
(0,0.5)$, $H(0) = 0$ and $H(\nu)$ is monotonically increasing between
$0$ and $0.5$, we have $g(\mu) > \mu$ for all $\mu \in (0, 0.5)$.
Hence, inconsistency can occur for all such $\mu$. Since $H(\nu)$ is
monotonically increasing in $\nu$, the largest value of $\nu$ can be
obtained for the $\mu$ for which $H(\mu) - 2\mu$ is largest. We
already noted that this is maximized for $\mu=0.2$. Then the largest
$\nu$ such that $H(\nu) < H(\mu) - 2 \mu = 2 \cdot 0.1609...$ can be
numerically calculated as $\nu_{\max} = 0.0586...$. Thus, in that case we can get $\erateD(\cbayes)$ arbitrarily close to $\mu + \nu_{\max} = 0.2586...$.\footnote{While we have no formal proof, we  strongly suspect that $g(\mu)$
can be replaced by $H(\mu)/2$ in Part 2 of the theorem, so that the
suboptimality for $\cbayes$ would be just as large as for the other
three classifiers. For this reason we did not bother to draw the
function $g(\mu)$ in Figure~\ref{fig:allowed}.}
%peter 2 end of added part

How large can the discrepancy between $\mu = \inf_c \erateD(c)$ and
$\mu' = \erateD(\cbayes)$ be in the large $m$ limit, for general
learning problems? The next theorem, again summarized in
Figure~\ref{fig:allowed}, gives an upper bound which holds for all
learning problems (distributions $D$), namely, $\mu' < H(\mu)$:
\begin{theorem}{\bf \ (Maximal Inconsistency of Bayes)}
\label{thm:bayesbound}
Let $S^i$ be the sequence consisting of the first $i$ examples
$(x_1,y_1), \ldots, (x_i,y_i)$.  For all priors $P$ nonzero on a set
of classifiers $\cC$,
for all learning problems $D$ with $0 < \inf_{c \in \cC} \erateD(c) = \mu< 0.5$, 
for all $\delta >
0$, for all large $m$, 
with $D^m$-probability $\geq 1 - 2 \exp(- 2 \sqrt{m})$,
$$
\frac{1}{m} \sum_{i=1}^m \bigl| y_i - \cbayesi(x_i) \bigr| \leq 
H(\mu) + \delta.
$$
\end{theorem}
The theorem says that for large $m$, the total number of mistakes when
successively classifying $y_i$ given $x_i$ made by the Bayesian
algorithm based on $S^{i-1}$, divided by $m$, is not
larger than $H(\mu)$. By the law of large numbers, it follows that
for large $m$,
$\erateD(\cbayesi(x_i))$, {\em averaged\/} over all $i$, is no larger than
$H(\mu)$. Thus, it is not ruled out that sporadically, for some
$i$, $\erateD(\cbayesi(x_i)) > H(\mu)$; but this must be `compensated'
for by most other $i$.  We did not find a proof that $\erateD(\cbayesi(x_i)) < H(\mu)$
for {\em all\/} large $i$.
\begin{figure}[tb]
\includegraphics[angle=270]{full_allowed.ps}
\caption{\label{fig:allowed} A graph depicting the set of
  asymptotically allowed error rates for different classification
  algorithms. The $x$-axis depicts the optimal classifier's error rate
  $\mu$ (also shown as the straight line).  The lower curve is just
  $0.5 H(\mu)$ and the upper curve is $H(\mu)$.
Theorem~\ref{thm:bayesinconsistent} says that any $(\mu,\mu')$ 
between the straight line and
  the lower curve can be achieved for some learning
  problem $D$ and prior $P$. Theorem~\ref{thm:bayesbound} shows that
  the Bayesian learner can never have asymptotic 
error rate $\mu'$ above the upper curve.}
\end{figure}
\section{Proofs}
\label{sec:proofs}
\commentout{
%peter1 replaced by new, much 'cleaner' lemma; and moved to appendix. It seemed important to directly start with the most interesting and easiest part of the proof, namely 'the learning problem'
In this section we present the proofs of the three theorems.
Theorem~\ref{thm:bayesinconsistent} and~\ref{thm:bayesbound} both make
use of the following lemma:
\begin{lemma}
\label{pro:basicbayes}
There exists $\gamma > 0$ such that 
for all classifiers $c$, $\alpha > 0$, $m > 0$, all $S \sim D^m$
satisfying $\alpha + 1/\sqrt{m} < \hat{e}_S(c) \leq 0.5$, all priors
satisfying (\ref{eq:priorb}): \\
\begin{multline}
\label{eq:bayesbound}
%\ \ \ \ \ $\text{\ \ \ \ \ } 
\log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))}
\leq  \log \frac{1}{P(y^m \mid x^m, c)} 
\leq \\
%$ \ \\ 
%\ \ \ \ \ \ \ \ \ \ $\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } 
\log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))} + \frac{1}{2} \log {m} +
\frac{1}{2} \frac{1}{\alpha (1- \alpha)} 
- \log \gamma.
%$ \ 
\end{multline}
\end{lemma}
\begin{proof}{\bf (sketch)\ }
For the first inequality, note
\begin{multline}
\log \frac{1}{P(y^m \mid x^m, c)} = 
\log \frac{1}{\int P(y^m \mid x^m, c,\theta) P(\theta) d\theta}
\geq 
\log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))}, \nonumber
\end{multline}
since the likelihood $P(y^m \mid x^m, c, \theta)$ is maximized
at $\theta = \hat{e}_S(c)$. 
For the second inequality, note that
$$
%\begin{multline}
%\int_{\theta \in [0,1]} 
\int_0^1 
P(y^m \mid x^m, c,\theta) P(\theta) d \theta 
\geq 
%\int_{\theta: |\theta - \hat{e}_S(c)| \leq  1 /\sqrt{m} } 
\int_{\hat{e}_S(c) - 1/ \sqrt{m}}^{\hat{e}_S(c) + 1 /\sqrt{m}}
\exp \bigl( \log P(y^m \mid x^m,
c,\theta) + \log P(\theta) \bigr) d \theta. 
%\nonumber
%\end{multline}
$$
We obtain (\ref{eq:bayesbound}) by expanding $ \log P(y^m \mid
x^m, c,\theta)$ around the maximum $\theta = \hat{e}_S(c)$ using a
second-order Taylor approximation. See, \citep{BarronRY98} for further details.
\end{proof}
}
\subsection{Inconsistent Learning Algorithms:
Proof of Theorem~\ref{thm:bayesinconsistent}}
\label{sec:inconsistencyproof}
Below we first define the particular learning
problem that causes inconsistency. We then analyze the performance of the
algorithms on this learning problem.

\subsubsection{The Learning Problem}
\label{sec:learningproblem}
For given $\mu$ and $\mu' \geq \mu$, we construct a learning problem
and a set of classifiers ${\cal C} = \{ c_0, c_1, \ldots \}$ such that
$c_0$ is the `good' classifier with $\erateD(c_0) = \mu$ and $c_1,
c_2, \ldots$ are all `bad' classifiers with $\erateD(c_j) = \mu' \geq
\mu$.  $x = x_0 x_1 \ldots \in {\cal X} = \{0,1\}^\infty$ consists of one binary feature per classifier, and the
classifiers simply output the value of their special feature.  The
underlying distribution $D$ depends on two parameters $0 < \phard < 1$ and 
$\eta \in [0,1/2)$. These are defined in terms of the $\mu$ and $\mu'$ mentioned in the theorem, in a way to be described later. 
%peter2 removed in terms of $\mu$ and $\mu'$, 
%peter2 added

To construct an example $(x,y)$, we first flip a fair coin to
determine $y$, so $y =1$ with probability $1/2$.  We then flip a coin with bias
$\phard$ which determines if this is a ``hard''
example or an ``easy'' example. Based upon these two coin flips, for
$j \geq 1$, each $x_j$ is independently generated according to the following $2$ cases.
\begin{enumerate}
\item For a ``hard'' example, and for each classifier $c_j$ 
with $j \geq 1$, set $x_j = |1 - y|$ with probability $1/2$ and
$x_j = y$  otherwise. Thus, $x_1, x_2, \ldots$ becomes an infinite sequence of realizations of i.i.d. uniform Bernoulli random variables.  
\item For an ``easy'' example, we flip a third coin $Z$ with bias
  $\eta$. If $Z=0$ (`example ok'), we set, for every $j \geq 1$, $x_j
  = y$. If $Z=1 $, we set, for all $j \geq 1$, $x_j = |1- y|$
  otherwise. Note that for an ``easy'' example, all bad classifiers make
  the same prediction. 
\end{enumerate}
The bad classifiers essentially predict $Y$ by random guessing on hard
examples. On easy examples, they all make the same prediction, which
is correct with probability $1- \eta > 0.5$.  It remains to define the
input $x_0$ of the ``good'' classifier $c_0$ with true error rate
$\mu$. This is done simply by setting $x_0 = |1- y|$ with probability
$\mu$ and $x_0 = y$ otherwise.

The setting of $\phard$ and $\eta$ is different for, on the one hand,
the (S)MAP and MDL inconsistency proofs, and on the other hand, the
full Bayes inconsistency proof. To get a
first, intuitive idea of the proof, it is best to ignore, for the time
being, the parameter values for the full Bayes proof.

In the MAP and MDL inconsistency proof, we set $\phard := 2\mu'$ and
$\eta = 0$. In the Bayes proof, we first set $\phard := 2 \mu$. We
then define $\nu:= \mu' - \mu$ and we set $\eta := \nu/(1- 2 \mu)$. By
the conditions of the theorem, we have $0 < H(\nu) < H(\mu) - 2\mu$.
Note that for such $\nu$, $H(\nu) < 1 - 2 \mu$ and therefore $2\nu
\leq 1- 2\mu $ so that $\eta < 1/2$. As is easily checked in the
(S)MAP and MDL case, and somewhat harder to check in the full Bayes
case, the error rate of each `bad' classifier is $\erateD(c_j) = \mu'$
for all $j \geq 1$.

{\em Discussion\/} The inputs $x$ are infinite-dimensional vectors.
Nevertheless, the Bayesian posterior can be arbitrarily well
approximated in finite time for any finite sample size \( m \) if we
order the features according to the prior of the associated
classifier. We need only consider features which have an associated
prior greater than \( \frac{1}{2^{m}} \) since the minus
log-likelihood of the data is always less than \( m + O(\log m) \)
bits. This follows because by (\ref{eq:priorb}) and
(\ref{eq:discreteprior}), the prior $P(\theta)$ puts sufficient mass
in a neighborhood of $\theta = 0.5$. For such $\theta$,  the distribution
$p_{c,\theta}(y|x)$ becomes uniform, independently of $c$.

The (constructive) proof of Theorem~\ref{thm:bayesinconsistent} 
relies upon this problem, but it's worth
mentioning that other hard learning problems exist and that this hard learning problem can be
viewed in two other ways:
\begin{enumerate}
\item The input space has two bits (the hardness bit and the ``correct
value'' bit) and the classifiers are stochastic.  Stochastic
classifiers might be reasonable (for example) if the task is inferring
which of several stock ``experts'' are the best on average.  The stock
pickers occasionally make mistakes as modeled by the stochasticity.
\item The input space consists of one real valued feature.  Each bit
in the binary expansion of the real number is used by a different
classifier as above.
\end{enumerate}

\subsubsection{Bayes and MDL are inconsistent}
We now prove Theorem~\ref{thm:bayesinconsistent}. Stage 1 and 2 
do not depend on the specific choices for $\phard$ and
$\eta$, and are common to the proofs for MAP, SMP, MDL and full Bayes. 
In Stage 1 we show that for some function $k(m)$, for every
value of $m$, with probability converging to 1, there exists
some `bad' classifier $c^* = c_j$ with $0 < j \leq k(m)$ that has $0$
empirical error on hard examples, whereas the good classifier has empirical error close to its expected generalization error. Up to sublinear terms, we find that
\begin{equation}
\label{eq:delft}
\log k(m) = {m\phard}.
\end{equation}
The precise expression is given in (\ref{eq:montventoux}).
In Stage 2 we rewrite the log posterior odds ratio between the good
classifier $c_0$ and $c^*$. Up to sublinear terms (see
(\ref{eq:calvados})), this ratio turns out to be equal to
\begin{equation}
\label{eq:leiden}
m H(\erateS(c^*)) - m H(\erateS(c_0)) +  m \phard.
\end{equation}
In Stage 3 we combine (\ref{eq:delft}) and (\ref{eq:leiden}) to show
that, with the choice $\phard = 2 \mu'$, $\eta = 0$, the posterior on
$c^*$ becomes exponentially larger than the posterior on $c_0$, from
which inconsistency of MAP, SMP and MDL readily follows. In Stage 4,
we show that with the choice $\phard = 2 \mu$, $\eta = \nu/(1-2 \mu)$, the
posterior on $c^*$ still becomes exponentially larger than the
posterior on $c_0$, but now additionally, the classification
performance of the Bayesian classifier (a mixture that puts nearly all
its weight on bad classifiers), cannot exceed that of $c^*$.
\paragraph{Stage 1}
Let $\mhard$ denote the number of hard examples generated within a
sample $S$ of size $m$. 
%peter2 added
Let $\erateShard(c)$ be the number of mistakes that the classifier $c$
makes on the subset $\Shard$ 
of $S$ of hard examples, divided by $\mhard = |\Shard|$. 
%
Let $k$ be a positive integer and $\cC_k =
\{c_j \in \cC: 1 \leq j \leq k  \}$.  For all $\epsilon > 0$
and $m \geq 0$, we have:
\begin{eqnarray}
\lefteqn{\Pr_{S \sim D^m}(\forall c \in \cC_k: \ \erateShard(c) > 0)} & &
\nonumber  \\ 
& \overset{(a)}{=} & 
\Pr_{S \sim D^m} \left( \forall c \in \cC_k: \ \erateShard(c) > 0 
\mid \frac{\mhard}{m} > \phard + \epsilon \right) 
\Pr_{S\sim D^m} \left( \frac{\mhard}{m} > \phard + \epsilon \right) 
\nonumber \\
& + & \Pr_{S \sim D^m} \left( \forall c \in \cC_k: \ \erateShard(c) > 0 
\mid \frac{\mhard}{m} \leq \phard + \epsilon \right) 
\Pr_{S \sim D^m} \left( \frac{\mhard}{m} \leq  \phard + \epsilon
\right) 
\nonumber  \\
& \overset{(b)}{\leq} & e^{-2m \epsilon^2} + 
\Pr_{S \sim D^m}\left( \forall c \in \cC_k: \ \erateShard(c) > 0 \mid
  \frac{\mhard}{m} \leq \phard + \epsilon \right) 
\nonumber \\
\label{eq:monday}
& \overset{(c)}{\leq} &  e^{-2m \epsilon^2} + 
(1 - 2^{-m \left( \phard + \epsilon \right)})^k 
%\nonumber \\
%& 
\overset{(d)}{\leq} 
%&  
e^{-2m \epsilon^2} + e^{-k 2^{- m\left( \phard +
      \epsilon \right)}}.
\end{eqnarray}
Here (a) follows because $P(a)= \sum_b P(a|b)P(b)$.
(b) follows by $\forall a,P:\,\,P(a) \leq 1$ and the Chernoff bound.
(c) holds from independence and 
since $(1 - 2^{-m(\phard + \epsilon)})^k$ is monotonic in
$\epsilon$, and (d) by 
$\forall x \in [0,1], k>0:\,\,\, (1-x)^k \leq e^{-kx}$.
We now set $\epsilon_m := m^{-0.25}$ and 
\begin{equation}
\label{eq:montventoux}
k = 
k(m) = \frac{2m \epsilon_m^2}{2^{-m\left( \phard + \epsilon_m \right)}}.
\end{equation} 
Note that, up to sublinear terms, this is equal to (\ref{eq:delft}).
With (\ref{eq:montventoux}),
(\ref{eq:monday}) becomes
\begin{equation}
\label{eq:friday}
\Pr_{S \sim D^m}(\forall c \in \cC_{k(m)}: 
\ \erateShard(c) > 0) \leq  2 e^{-2\sqrt{m}}
\end{equation}
On the other hand, by the Chernoff bound we have
%\begin{eqruation}
%\label{eq:sprite}
$
\Pr_{S \sim D^m}(\erateS(c_0) < \erateD(c_0) - \epsilon_m) \leq 
e^{-2 \sqrt{m}} 
$
%\end{eqruation}
for the optimal classifier $c_0$.
Combining this
with (\ref{eq:friday}) using the union bound, we get that, with
$D^m$-probability larger than $1- 3 e^{-2\sqrt{m}}$, the following
event holds:
\begin{equation}
\label{eq:saturday}
\exists c \in \cC_{k(m)}: 
\ \erateShard(c) = 0 \text{\ and \ } \erateS(c_0) \geq \erateD(c_0) -
\epsilon_m.
\end{equation}
\paragraph{Stage 2}
In this stage, we calculate, for large $m$, the log
ratio between the posterior on some $c^* \in \cC_{k(m)}$ with
$\erateShard(c^*) = 0$ and the posterior on $c_0$. We have:
\begin{multline}
\label{eq:odds}
\log \frac{\max_{\theta}
P(c_0, \theta \mid x^m,y^m)}{\max_{\theta} P(c^*, \theta \mid x^m,y^m)} = 
\log  
\frac{\max_{\theta} P(c_0) P(\theta) P(y^m \mid x^m, c_0,  \theta)}
{\max_{\theta} P(c^*) P(\theta) P(y^m \mid x^m, c^*, \theta)}
= \\
\log \max_{\theta} P(c_0) P(\theta) P(y^m \mid x^m, c_0,  \theta)
-
\log \max_{\theta} P(c^*) P(\theta) P(y^m \mid x^m, c^*, \theta).
\end{multline}
Using (\ref{eq:safe}), (\ref{eq:priorb}) and (\ref{eq:discreteprior}), 
we see that, uniformly for all samples $S$ with $\erateS(c_0) < 1/2$, 
the leftmost term is no larger than
\begin{multline}
\label{eq:reftie}
\log \ \bigl( \max_{\theta} P(c_0) P(\theta) \bigr) \cdot 
\bigl(\max_{\theta'}  P(y^m \mid x^m, c_0, {\theta'}) \bigr)
= - m H(\erateS(c_0)) + O(1).
\end{multline}
Similarly, uniformly for all samples $S$ with $\erateShard(c^*) = 0,
\erateS(c^*) < 1/2$, 
the rightmost term in (\ref{eq:odds}) satisfies
\begin{equation}
\label{eq:rightie}
-
\log \max_{\theta} P(c^*) P(\theta) P(y^m \mid x^m, c^*, \theta) \leq
- \log P(c^*) + m H(\erateS(c^*)) +O(1), 
\end{equation}
where the constant in the $O$-notation does not depend on $c^*$.
%TODO WHY DOES MARCUS ASK?
Using
condition (\ref{eq:priora}) on  prior $P(c^*)$ and using
$c^* \in \cC_{k(m)}$, we find:
\begin{equation}
\label{eq:priorc}
- \log P(c^*) = \log \frac{1}{P(c^*)} \leq \log k(m) + o ( \log k(m)),
\end{equation}
where $\log k(m) = \log {2}{\sqrt{m}} + 
m \phard + m^{0.75}$, so that
\begin{equation}
\label{eq:key}
 \log
\frac{1}{P(c^*)} \leq m \phard + o(m) 
\end{equation}
which implies that (\ref{eq:rightie}), is no larger than $ m \phard +
m H(\erateS(c^*))+
o(m)$.  Thus, for 
all large $m$, the difference between the leftmost term
and the rightmost term  in
(\ref{eq:odds}) satisfies
\begin{equation}
\label{eq:calvados}
\log \frac{\max_{\theta}
P(c_0, \theta \mid x^m,y^m)}{\max_{\theta} P(c^*, \theta \mid x^m,y^m)} \leq 
- m H(\erateS(c_0)) +  m \phard + mH(\erateS(c^*)) + o(m),
\end{equation}
as long as $\erateS(c_0)$ and $\erateS(c^*)$ are both less than $0.5$.
\paragraph{Stage 3(a)} {\bf (MAP)}
Recall that, for the MAP result, we set $\eta := 0$ and $\phard := 2
\mu'$. Let us assume that the large probability
event (\ref{eq:saturday}) holds. This will allow us to replace the two
`empirical entropies' in (\ref{eq:calvados}), which are random
variables, by corresponding ordinary entropies, which are constants.
By (\ref{eq:saturday}),  $\erateShard(c^*) = 0$, so that
we have (since $\eta = 0$) that $\erateS(c^*) = 0$ and then also
$H(\erateS(c^*)) = 0$. Because $H(\mu)$ is continuously differentiable 
in a small enough neighborhood around $\mu$, by (\ref{eq:saturday}) we
also have, for some constant $K$, 
$$
H(\erateS(c_0)) \geq H(\erateD(c_0)) - K \epsilon_m + O(1)
=  H(\mu) + O(m^{-1/2}).$$
Plugging these expressions for $H(\erateS(c^*))$ and  $H(\erateS(c_0))$
into (\ref{eq:calvados}), and using the fact that we set $\phard = 2
\mu'$, we see that, as long as $\mu' < H(\mu)/2$, there exists a $c >
0$ such that for all large $m$, (\ref{eq:calvados}), and hence (\ref{eq:odds}) is smaller than $-
cm$.  
Thus, (\ref{eq:odds}) is less than $0$ for large $m$, implying that
then $\emap = \mu'$. 
We
derived all this from (\ref{eq:saturday}) which holds with
probability $\geq 1 - 3 \exp(- 2 \sqrt{m})$. Thus, 
for all large $m$,
$ \Pr_{S \sim D^m} \left( \emap = \mu' \right) \geq 1-
3 \exp(- 2 \sqrt{m}),$
and the result follows.

\paragraph{Stage 3(b)} {\bf (SMP)}
We are now interested in evaluating, instead of the posterior ratio (\ref{eq:odds}), the posterior ratio with the error rate 
parameters integrated out: 
\begin{equation}
\label{eq:smapodds}
\log \frac{
P(c_0 \mid x^m,y^m)}{P(c^* \mid x^m,y^m)} =
\log P(c_0) P(y^m \mid x^m, c_0)
-
\log P(c^*) P(y^m \mid x^m, c^*).
\end{equation}
By Proposition~\ref{prop:uniboem} in the appendix, we see that, if
(\ref{eq:saturday}) holds, then (\ref{eq:odds}) is no larger than
(\ref{eq:smapodds}) plus an additional term of order $O(\log m)$. To see this, apply the first inequality of (\ref{eq:bayesbound})
to the term involving $c_0$, and the second inequality of
(\ref{eq:bayesbound}) to the term involving $c^*$.  The result now
follows by exactly the same reasoning as in Stage 3(a).
%We already showed in
%Stage 3(a) that, (b)  if (\ref{eq:saturday}) holds, then, as long as $\mu' <
%H(\mu)/2$, there exists a $c > 0$ such that for all large $c$,
%(\ref{eq:odds}) is smaller than $- cm$. Since (\ref{eq:saturday}) holds with
%probability $\geq 1 - 3 \exp(- 2 \sqrt{m})$, the result follows.

\paragraph{Stage 3(c)} {\bf (MDL)}
By part (1) of Proposition~\ref{prop:uniboem} in the appendix, the MDL
procedure is equal to SMP with the uniform prior $w(\theta) \equiv 1$.
Thus, the MDL case is a special case of the SMP case for which we
already proved inconsistency above.  

\paragraph{Stage 3(d)} {\bf (Bayes)}
%peter2 rewrote completely
In order to prove the inconsistency for the full Bayesian classifier,
we construct a setup where on on hard examples, all classifiers, even
the `good' classifier $c_0$, predict $c(X)=1$ with probability 1/2,
independently of the true value of $Y$. To this end, we refine our
learning problem by setting $x_0 = |1-y|$ with probability 1/2 for a
``hard'' example, and $x_0 = y$ with probability 1 for an ``easy''
example. By setting $\phard := 2\mu$, we still get that $\erateD(c_0)
= \mu$. In order to make the error rate for the bad classifiers $c_1,
c_2, \ldots$ still larger than for $c_0$, we now set $\eta$ to a value
larger strictly than $0$.

We let $\erateSeasy(c)$ denote the empirical error that classifier $c$
achieves on the easy examples in $S$, i.e. the number of mistakes on
the easy examples in $S$ divided by $|S| - |\Shard|$. Now set
$\epsilon_m$ as in Stage 1 and define the events (sets of samples
$S^m$ of length $m$) ${\cal A}$ and ${\cal B}$ as
%\begin{eqarray}
$${\cal A}  =  \{S^m \; : \;  \exists j > 0 :  
| \erateSeasy(c_j) - \eta | >   \epsilon_m \}  
%\nonumber \\
\ ; \ 
{\cal B}  =  \{ S^m \; : \; \frac{\mhard}{m} \geq \phard +  \epsilon_m \},
$$
%\nonumber
%\end{eqnarray}
and let ${\cal A}^c$ and ${\cal B}^c$ be their respective complements.
We have
\begin{multline}
\Pr_{S \sim D^m}\left( {\cal A} \cup {\cal B}  \right) = \\
\Pr \left( {\cal A} \cup {\cal B} \mid 
{\cal B} \right) \Pr\left({\cal B} \right)  + 
\Pr \left( {\cal A} \cup {\cal B} \mid 
{\cal B}^c \right) \Pr\left({\cal B}^c \right) 
\leq   \Pr\left({\cal B} \right) + 
\Pr \left( {\cal A} \mid 
{\cal B}^c \right) \\ \leq 
e^{- 2 \sqrt{m}} + 2 e^{- 2 m (1- \phard - \epsilon_m) \epsilon_m^2} = 
e^{- 2 \sqrt{m}} + 2 e^{- 2 \sqrt{m}(1- \phard) + 2 m^{0.25}} 
\leq \\
3 e^{- (1- \phard) \sqrt{m}} (1+ o(1)), 
\end{multline}
where the second inequality follows by applying the Chernoff bound to
both terms (recall that on easy examples, all classifiers $c_j$ with $j > 1$ output the same prediction for $Y$).  Combining this with the result of Stage 1 using the union
bound and using $\phard = 2 \mu$, we get that, with $D^m$-probability
at least $1- 6 (1+ o(1))e^{-\sqrt{m}(1- 2 \mu)}$, (\ref{eq:saturday})
and ${\cal A}^c$ and ${\cal B}^c$ all hold at the same time.  Let us
assume for now that this large probability
event holds. We must then have that some $c^* \in {\cal C}_{k(m)}$ achieves empirical error $0$
on hard examples (which occur with probability $2 \mu$) and at least
$\eta + O(m^{-1/2})$ on easy examples (which occur with probability $1- 2
\mu$), so that 
\begin{equation}
\label{eq:nyons}
\erateS(c^*) = (1- 2\mu) \eta + O(m^{-1/2}) = \nu  + O(m^{-1/2}), 
\end{equation}
where $\nu =
\mu' - \mu$. By continuity of $H$, we also have that $H(\erateS(c^*))
= H(\nu) + O(m^{-1/2})$.

Entirely analogously to the reasoning in Stage 3(a), we can now replace the
empirical entropies in the expression (\ref{eq:calvados}) for the
log-likelihood ratio between $c^*$ and $c_0$ by the corresponding 
ordinary entropies. This gives
\begin{equation}
\label{eq:calvadosb}
\log \frac{\max_{\theta}
P(c_0, \theta \mid x^m,y^m)}{\max_{\theta} P(c^*, \theta \mid x^m,y^m)} \leq 
- m H(\mu) +  m 2 \mu + mH(\nu) + o(m),
\end{equation}
By definition of $\nu$, $\nu = \mu' - \mu$ satisfies $-H(\mu) + H(\nu) + 2\mu <
0$, so that there exists a $c > 0$ such that for all large $m$,
(\ref{eq:calvadosb}) is smaller than $- c m$. 
Reasoning entirely analogously to Stage 3(b), we see that
(\ref{eq:calvadosb}) still holds if we integrate out $\theta$, rather than
maximize over it: there exists a $c > 0$ such that for all
large $m$,
\begin{equation}
\label{eq:calvadosc}
\log \frac{
P(c_0 \mid x^m,y^m)}{P(c^* \mid x^m,y^m)} \leq 
- m H(\mu) +  m 2 \mu + mH(\nu) + o(m) \leq - cm.
\end{equation}
Furthermore, by (\ref{eq:nyons}) and our condition on the prior,
the posterior on $\theta$ given $c^*$ must concentrate on $\nu$ (even
though $c^*$ varies with $m$): 
we must have that, for every open set $A$ containing
$\nu$, the posterior distribution of $\theta$ given $c^*$ and sample
$S$ satisfies 
\begin{equation}
\label{eq:calvadosd}
P(\theta \in A \mid c^*, S) \overset{m \rightarrow
  \infty}{\rightarrow} 1.
\end{equation}
We now show that (\ref{eq:calvadosc}) and (\ref{eq:calvadosd}), both
of which hold with high probability, imply that the full Bayesian
classifier based on sample $S$ errs with probability at least
$\mu + \nu = \mu'$: 
\begin{multline}
\label{eq:wagen}
\Pr_{X,Y \sim D}(Y \neq \cbayes(X)) = 
 \Pr_{X,Y \sim D}(Y \neq \cbayes(X) \mid \text{Ex. hard}) \phard + \\
\Pr_{X,Y \sim D}(Y \neq \cbayes(X) \mid \text{Ex. easy}) (1- \phard)
\geq \\
\frac{1}{2} 2 \mu + \Pr_{X,Y \sim D}(Y \neq \cbayes(X) \mid
\text{Ex. easy}) (1 - 2 \mu)  \geq \\
\mu + \Pr_{X,Y \sim D}(Y \neq \cbayes(X) \mid
\text{Ex. easy, corrupted}) (1- 2\mu) \eta = \\
\mu + \Pr_{X,Y \sim D}(Y \neq \cbayes(X) \mid
\text{Ex. easy, corrupted}, Y=1) (1- 2\mu) \eta.
\end{multline}
Here the first inequality follows by symmetry: on hard examples, $Y=1$
with probability $1/2$ and all classifiers independently output $Y=1$
with probability $1/2$. The final equality follows again by symmetry
between the case $Y=1$ and $Y=0$.  Depending on the sample $S$, the probability in the final line
of (\ref{eq:wagen}) is either equal to $1$ or to $0$. It is equal to 1
if $\cbayes(X) = 0$. By (\ref{eq:bayesact}), a sufficient condition
for this to happen is if $S$ is such that 
\begin{equation}
\label{eq:maker}
E_{{c,\theta} \sim P(\cdot \mid S)} \/[ p_{c,\theta}(Y =
1|X=x) ] < 
\frac{1}{2}.  
\end{equation}
This expectation can be rewritten as 
\begin{multline}
\label{eq:huiler}
\sum_{c \in \cC} \int_{\theta \in [0,0.5)} P(\theta \mid c, S)  
P( c \mid S) p_{c,\theta} (Y =1|X=x) d \theta = \\
\sum_{c \in \cC}P( c \mid S)  u(c,S,x) = \\
P(c_0 \mid S) u(c_0 ,S,x) + P(c^* \mid S) u(c^* ,S,x)
+ \sum_{c \not \in \{c_0,c^*\} } P( c \mid S)  u(c,S,x),
\end{multline}
where
$
u(c,S,x) := 
\int_{\theta  \in [0,0.5)} 
P(\theta \mid c, S) 
p_{c,\theta} (Y = 1|X=x) d \theta.
$
Note that we integrate here over $[0,0.5)$, reflecting the extra
condition (\ref{eq:restrictedprior}) that we required for the full
Bayesian result. Since the example in the final line (\ref{eq:wagen}) is corrupted,
for the $x$ occurring there we have that $c_j(x) = 0$ for $j \geq 1$,
so that $p_{c_j,\theta}(Y=1 \mid X = x) < 1/2$ for all $\theta <
1/2$. It follows that for this $x$, (\ref{eq:huiler}) is no greater than
$$
P(c_0 \mid S) + P(c^* \mid S) u(c^* ,S,x) + \sum_{c \not \in
  \{c_0,c^*\} } P( c \mid S) \frac{1}{2}.
$$
By (\ref{eq:calvadosc}) and (\ref{eq:calvadosd}), for all $\delta >
0$, for all large $m$ this is no greater
than 
\begin{equation}
\label{eq:isere}
a(e^{- c m} \cdot 1 + (1- e^{- cm}) (\nu + \delta))  + (1-a) \frac{1}{2}.
\end{equation}
for some $a$ that may depend on $m$ but that  satisfies $0 < a < 1$ for all $m$. Therefore, and since $\nu < 1/2$, (\ref{eq:isere}) is less than $1/2$ for all large $m$. But this implies (by the reasoning above
(\ref{eq:maker})) that $\cbayes(x) =0$. It follows by (\ref{eq:wagen})
that, for large $m$,
$$
\Pr_{X,Y \sim D}(Y \neq \cbayes(X)) \geq \mu + (1- 2 \mu) \eta = 
\mu + \nu = \mu'.
$$
All this is implied under an event that holds with probability at
least  $1- 6 (1+ o(1))e^{-\sqrt{m}(1- 2 \mu)}$ (see above), so that
the result follows.
\subsection{A Consistent Algorithm: Proof of Theorem~\ref{thm:consistent}}
\label{sec:orb}
In order to prove the theorem, we first state
the Occam's Razor Bound classification algorithm, based on minimizing the bound given by the following theorem.
\begin{theorem} (Occam's Razor Bound) {\rm  \citep{BlumerEHW87}} 
\label{thm:orb}
For all priors $P$ on a countable set of classifiers $\cC$, 
for all distributions $D$, with
probability $1-\delta$:
$$ \forall c:\,\,\,\,\erateD(c) \leq \erateS(c) + \sqrt{\frac{\ln \frac{1}{P(c)} + \ln \frac{1}{\delta}}{2m}}.$$
\end{theorem}
The algorithm stated here is in a suboptimal form, which is good
enough for our purposes (see \citep{McAllester99} for more
sophisticated versions):
$$ \corb := \arg \min_{c \in \cC} \ \left\{ 
\erateS(c) + \sqrt{\frac{\ln
    \frac{1}{P(c)} + 
\ln {m}}{2m}}\ \right\}.$$
\paragraph{Proof of Theorem~\ref{thm:consistent}}
Set $\delta_m := 1/m$. It is easy to see that 
$$
\min_{c \in \cC} \erateD(c) + \sqrt{\frac{\ln
    \frac{1}{P(c)} + 
\ln {m}}{2m}}
$$
is achieved for at least one $c \in \cC = \{ c_0, c_1, \ldots
\}$. Among all $c_j \in \cC$ achieving the minimum, let 
$\tilde{c}_{m}$ be the one with smallest index $j$. By the Chernoff
bound, we have with probability at least $1-
\delta_m = 1- 1/m$,
\begin{equation}
\label{eq:chernoccam}
\erateD(\tilde{c}_{m}) \geq \erateS(\tilde{c}_{m}) -
\sqrt{\frac{\ln (1/\delta_m)}{2m}} = 
\erateS(\tilde{c}_{m}) -
\sqrt{\frac{\ln m}{2m}},
\end{equation}
whereas by Theorem~\ref{thm:orb}, with probability at least
$1 - \delta_m = 1- 1/m$,
%\begin{eqruation}
%\label{eq:occhern}
\begin{multline}
\erateD(\corb) \leq \min_{c \in \cC} 
\erateS(c) + \sqrt{\frac{- \ln
    {P(c)} + 
\ln {m}}{2m}} \leq \\ \erateS(\tilde{c}_{m}) +
\sqrt{\frac{- \ln {P(\tilde{c}_{m})} + 
\ln {m}}{2m}}. \nonumber
\end{multline}
%\end{eqruation}
Combining this with (\ref{eq:chernoccam}) using the union bound, we find that 
$$\erateD(\corb) \leq \erateD(\tilde{c}_{m}) +  \sqrt{\frac{- \ln
    {P(\tilde{c}_{m})} + 
\ln {m}}{2m}} + \sqrt{\frac{\ln m}{2m}},$$
with probability at least $1 - 2/m$.
The theorem follows upon noting that the right-hand side of this
expression converges to $\inf_{c \in \cC} \erateD(c)$ with increasing $m$. 

\subsection{Proof of Corollary~\ref{cor:inconsistent}}
%peter1 added a lot here
The corollary relies on Theorem~\ref{thm:consistent} and a slight
generalization of the proof of Theorem \ref{thm:bayesinconsistent}.
For Theorem \ref{thm:consistent} pick $K < 0.05$.
In Theorem \ref{thm:bayesinconsistent} choose $\mu =
1/5$, $\mu' = 1/5 + .15$. Now part 1 follows.
For part 2, consider Theorem \ref{thm:bayesinconsistent} with the
same $\mu$ and $\mu'$. From the  theorem 
we see that for the learning problem   for which
(\ref{eq:batman}) holds, $c_0$ is the optimal
classifier. Denote this learning problem by $D_0$. We define $D_j$ as
the learning problem (distribution) in the proof (see
Section~\ref{sec:learningproblem}), but with the role of $x_0$ and $x_j$
interchanged. As a result, $c_j$ will be the `good' classifier with
error rate $\mu$ and $c_0$ will be one of the bad classifiers with
rate $\mu'$. Then the good classifier and one of the bad
classifiers will have a different prior probability, 
but otherwise nothing changes. Since the proof of Theorem
\ref{thm:bayesinconsistent} does not depend on the prior probability
of the good classifier -- it can be as large or small as we like as
long as it is greater than $0$ --, the proof goes through unchanged, and for all
learning problems $D_j$, (\ref{eq:batman}) will hold.

We now generate a learning problem $D_j$ by first sampling a
classifier $c_j$ according to $P(c)$, and then generating data
according to $D_j$. Then, no matter what $c_j$ we chose,  
it  will be the optimal (`good')
classifier, and, as we just showed, (\ref{eq:batman}) will
hold. Theorem~\ref{thm:consistent} (with $K < 0.05$) can now be
applied with $D = D_j$, and the result follows.
\subsection{Proof of Theorem~\ref{thm:bayesbound}}
%\enlargethispage{\baselineskip}
Without loss of generality assume that $c_0$ achieves $\min_{c \in \cC} \erateD(c)$. Consider both the $0/1$-loss and the log loss of sequentially
  predicting with the Bayes predictive distribution $P(Y_i =  \cdot
  \mid X_i = \cdot , S^{i-1})$ given by
$P(y_i  \mid  x_i, S^{i-1}) =  
E_{c,\theta \sim P(\cdot \mid S^{i-1})} \/ p_{c,\theta}(y_i|x_i).$
Every time $i \in
  \{1, \ldots, m \}$ that the Bayes classifier based on $S^{i-1}$
  classifies $y_i$ incorrectly,
  $P(y_i \mid x_i, S^{i-1})$ must be $\leq 1/2$ so that 
$ - \log P(y_i \mid x_i, S^{i-1}) \geq 1$.
Therefore, if for some $\alpha > 0$, $\erateS(c_0) < 0.5 - \alpha$, then
\begin{equation}
\label{eq:champagne}
\sum_{i=1}^m  - \log P(y_i \mid x_i,  S^{i-1}) \geq 
\sum_{i=1}^m | y_i - \cbayesi(x_i)|.
\end{equation}
On the other hand we have
\begin{multline}
\label{eq:coffee}
\sum_{i=1}^m  -\log P(y_i \mid x_i, S^{i-1}) = 
 -\log \prod_{i=1}^m P(y_i \mid x_i, x^{i-1},y^{i-1}) =  \\
 -\log \prod_{i=1}^m P(y_i \mid x^m, y^{i-1}) = 
- \log \prod_{i=1}^m \frac{P(y^i | x^m)}{P(y^{i-1}| x^{m})} {=}
  - \log P(y^m \mid x^m) = \\
 - \log \sum_{j = 0,1,2 \ldots} P(y^m \mid x^m, c_j)
P(c_j)   \overset{(a)}{\leq} \\ 
 - \log P(y^m \mid x^m, c_0) - \log P(c_0) \overset{(b)}{\leq}
m H(\erateS(c_0)) + O(\log m),
\end{multline}
where the constant in the $O(\log m)$ term may depend on $\alpha$.
Here inequality (a) follows because a sum is larger than each of its
terms, and (b) follows by Proposition~\ref{prop:uniboem} in the appendix. By the Chernoff bound, for all small enough $\epsilon > 0$,
with probability larger than $1 - 2 \exp(-2 m \epsilon^2)$, we have $|
\erateS(c_0) - \erateD(c_0) | < \epsilon$. We now set $\epsilon_m =
m^{-0.25}$. Using the fact that $H(\mu)$ in (\ref{eq:coffee}) is continuously
differentiable in a neighborhood of $\mu$ and $\mu < 1/2$, 
it follows that with probability larger than $1- 2 \exp(- 2 \sqrt{m})$,
for all large $m$,
\begin{equation}
\label{eq:tea}
\sum_{i=1}^m  -\log P(y_i \mid x_i, S^{i-1}) \leq 
m H(\erateD(c_0)) + Km^{0.75}  + O(\log m),
\end{equation}
where $K$ is a constant not depending on $m$. 
Combining (\ref{eq:tea}) with (\ref{eq:champagne}) 
we find  that with probability $\geq 1 - 2 \exp(- 2 \sqrt{m})$,
$
\sum_{i=1}^m | y_i - \cbayesi(x_i)| \leq 
m H(\erateD(c_0)) + o(m)$, which is what we had to prove.

\section{Technical Discussion} 
\subsection{Variations of Theorem~\ref{thm:bayesinconsistent} and 
dependency on the prior}
\label{sec:technical}
%\enlargethispage{\baselineskip}
\paragraph{Prior on classifiers}
The requirement (\ref{eq:priora}) that
$- \log P(c_k) \geq \log k +  o ( \log k)$
is needed to obtain (\ref{eq:key}), which is the key inequality in the proof of 
Theorem~\ref{thm:bayesinconsistent}.  If $P(c_k)$ decreases at polynomial rate, 
but at a degree $d$ larger than one, i.e. if 
\begin{equation}
\label{eq:dtail}
-\log P(c_k) = d \log k +  o ( \log k),
\end{equation} 
then a variation of Theorem~\ref{thm:bayesinconsistent} still applies
but the maximum possible discrepancies between $\mu$ and $\mu'$ become
much smaller: essentially, if we require $\mu \leq \mu' < \frac{1}{2d}
H(\mu)$ rather than $\mu \leq \mu' < \frac{1}{2} H(\mu)$ as in
Theorem~\ref{thm:bayesinconsistent}, then the argument works for all
priors satisfying (\ref{eq:dtail}). Since the derivative $d H(\mu) /
d\mu \rightarrow \infty$ as $\mu \downarrow 0$, by setting $\mu$ close
enough to $0$ it is possible to obtain inconsistency for any fixed
polynomial degree of decrease $d$. However, the higher $d$, the smaller $\mu =
\inf_{c \in \cC} \erateD(c)$ must be to get any inconsistency with this
argument. 
\paragraph{Prior on error rates}
Condition (\ref{eq:priorb}) on the prior on the error rates is
satisfied for most reasonable
priors. 
Some approaches to applying MDL to classification problems amount to
assuming priors of the form $p(\theta^*) = 1$ for a single $\theta^*
\in [0,1]$ (Section~\ref{sec:mdl}). In that case, we can still
prove a version of Theorem~\ref{thm:bayesinconsistent}, but the
maximum discrepancy between $\mu$ and $\mu'$ may now be either larger
or smaller than $H(\mu)/2 - \mu$, depending on the choice of
$\theta^*$.
\subsection{Properties of the transformation 
  from classifiers to distributions} 
\label{sec:trafo}
\paragraph{Optimality and Reliability}
Assume that the conditional distribution of $y$ given $x$ according to the 
`true' underlying distribution $D$ is defined for all $x \in \cX$, and let $p_D(y|x)$ denote its mass function. 
Define $\Delta(p_{c,\theta})$ as the Kullback-Leibler (KL) divergence \citep{CoverT91} between 
$p_{c,\theta}$ and the `true' conditional distribution $p_D$:
$$
\Delta(p_{c,\theta}) := 
 \KL(p_D \| p_{c,\theta}) =
E_{(x,y) \sim D} [ - \log p_{c,\theta}(y|x) + \log p_{D}(y|x)], 
$$
and note that for each fixed $c$,
$\min_{\theta \in
  [0,1]} \Delta(p_{c,\theta})$ is uniquely achieved for $\theta =
\erateD(c)$ (this follows by differentiation) and satisfies
\begin{equation}
\label{eq:turnaround}
\min_{\theta} \Delta(p_{c,\theta}) = \Delta(p_{c,\erateD(c)}) =
H(\erateD(c)) - K_D, 
\end{equation}
where $K_D = E [-\log p_{D}(y|x)]$ does not
depend on $c$ or $\theta$, and $H(\mu)$ is the binary entropy.
\begin{proposition}
\label{pro:trafo}
Let $\cC$ be any set of classifiers, and let $c^*
\in \cC$ achieve \\ $\min_{c \in \cC} \erateD(c)$ $= \erateD(c^*)$.
\begin{enumerate}
\item If $\erateD(c^*) < 1/2$, then 
$$\min_{c,\theta} \Delta(p_{c,\theta}) \text{\ is uniquely achieved for 
\ } (c,\theta) = (c^*,\erateD(c^*)).$$
\item $\min_{c,\theta} \Delta(p_{c,\theta}) = 0$ iff $p_{c^*,\erateD(c^*)}$ is `true', i.e. if
$\forall x, y: \/ p_{c^*,\erateD(c^*)}(y|x) = p_D(y|x)$.
\end{enumerate}
\end{proposition}
\begin{proof}
Property 1 follows from (\ref{eq:turnaround}) and the fact that
$H(\mu)$ is monotonically increasing for $\mu < 1/2$. Property 2 follows
directly from the information inequality \citep{CoverT91}, using the
fact that we assume $p_D(y|x)$ to be well-defined for all $x$, which
implies that $X$ has a density $p_D(x)$ with $p_D(x) > 0$ for all $x$.
\end{proof}
Proposition~\ref{pro:trafo} implies that the transformation is a good
candidate for turning classifiers into probability distributions.

Namely, let $\cP = \{ p_\alpha : \alpha \in A \}$ be a set of i.i.d.
distributions indexed by parameter set $A$ and let $P(\alpha)$ be a
prior on $A$.  By the law of large numbers, for each $\alpha \in A$,
$- m^{-1} \log p_{\alpha}(y^m \mid x^m)P(\alpha) - K_D \rightarrow \KL(p_D \|
p_{\alpha})$. By Bayes rule, this implies that if the class $\cP$ is
`small' enough so that the law of large numbers holds {\em
uniformly\/} for all $p_{\alpha} \in \cP$, then for all $\epsilon >
0$, the Bayesian posterior will concentrate, with probability 1, on
the set of distributions in $\cP$ within $\epsilon$ of the $p^* \in
\cP$ minimizing KL-divergence to $D$. In this case, if $\cC$ is
`simple' enough so that the corresponding $\cP = \{ p_{c,\theta} : c
\in \cC, \theta \in [0,1] \}$ admits uniform convergence
\citep{Grunwald98b}, then the Bayesian posterior asymptotically
concentrates on the $p_{c^*,\theta^*} \in \cP = \{ p_{c,\theta} \}$
closest to $D$ in KL-divergence. By Proposition~\ref{pro:trafo}, this
$p_{c^*,\theta^*}$ corresponds to the $c^* \in \cC$ with smallest
generalization error rate $\erateD(c^*)$ ($p_{c^*,\theta^*}$ is {\em
optimal\/} for $0/1$-loss), and for the $\theta^* \in [0,1]$ with
$\theta^* = \erateD(c^*)$ ($p_{c^*,\theta^*}$ gives a {\em reliable\/}
impression of its prediction quality). This convergence to an optimal
and reliable $p_{c^*,\theta^*}$ will happen if, for example, $\cC$ has
finite VC-dimension \citep{Grunwald98b}. We can only get trouble as in
Theorem~\ref{thm:bayesinconsistent} if we allow $\cC$ to be of
infinite VC-dimension.

\paragraph{Analogy to Regression} In ordinary (real-valued) 
regression, ${\cal Y } = {\mathbb R}$,
and one tries to learn a function $f \in {\cal F}$ from the data. Here ${\cal F}$ is 
a set of candidate functions
${\cal X} \rightarrow {\cal Y}$. In order to apply Bayesian inference
to this problem, one assumes a probability model $\cP$ expressing 
$Y = f(X) + Z$, where
$Z$ is independent noise with mean $0$ and variance $\sigma^2$. $\cP$ then 
consists of conditional density functions $p_{f,\sigma^2}$, one for each $f \in {\cal F}$ and $\sigma^2 > 0$. It is
well known that if one assumes $Z$ to be normally distributed
independently of $X$, then the $p_{f,\sigma^2}$ become Gaussian densities and 
the log likelihood becomes {\em a linear function of
  the mean squared error\/} \citep{Rissanen89}:
\begin{equation}
\label{eq:gauss}
- \ln p_{f,\sigma^2}(y^n \mid x^n) = \beta_{\sigma} \sum_{i=1}^n (y_i - f(x_i))^2 + 
n \ln Z(\beta_{\sigma}).
\end{equation}
where we wrote $\beta_{\sigma} = 1/2 \sigma^2$ and 
$Z(\beta) = \int_{y \in \cY}
\exp(- \beta y^2)d y$. Because least squares is an intuitive,
mathematically well-behaved and easy to perform procedure, it is often
assumed in Bayesian regression that the noise is normally distributed
-- even in cases where in reality, it is not
\citep{Grunwald98b,KleijnvdV04}.

Completely analogously to the Gaussian case, the transformation
used in this paper maps classifiers $c$ and noise rates
$\theta$ to distributions $p_{c,\theta}$ so that the log likelihood
becomes a {\em linear function of the $0/1$-error}, since it can be
written as:
\begin{equation}
\label{eq:entrop}
- \ln p_{c,\theta}(y^n \mid x^n) = \beta_{\theta} 
\sum_{i=1}^n |y_i - c(x_i)| + 
n \ln Z(\beta_{\theta}).
\end{equation}
where we wrote $\beta_\theta = \ln (1- \theta) - \ln \theta$ and $Z(\beta) =
\sum_{y \in \cY} \exp(- \beta y)$ \citep{Grunwald98b,MeirM95}.  Indeed, the
models $\{ p_{c,\theta} \}$ are a special case of {\em
  logistic regression models}, which we now define:

\paragraph{Logistic regression interpretation}
let $\cC$ be a
set of functions $\cX \rightarrow \cY$, where $\cY \subseteq {\mathbb
  R}$ ($\cY$ does not need to be binary-valued). The corresponding
logistic regression model is the set of conditional distributions $\{
p_{c,\beta} : c \in {\cal C} ; \beta \in {\mathbb R} \}$ of the
form
\begin{equation}
\label{eq:logit}
p_{c,\beta}(y \neq x \mid x) := \frac{e^{-\beta | y - c(x)|}}{1 + e^{-\beta}} 
\end{equation}
This is the standard construction used to convert classifiers with
real-valued output such as support vector machines and neural networks
into conditional distributions \citep{Jordan95,Tipping01}, so that
Bayesian inference can be applied.  By setting $\cC$ to be a set of
$\{0,1\}$-valued classifiers, and substituting $\beta = \ln (1-
\theta) - \ln \theta$ as in (\ref{eq:entrop}), we see that the
construction is a special case of the logistic regression transformation
(\ref{eq:logit}). It may seem that (\ref{eq:logit}) does not treat $y
= 1$ and $y= 0$ on equal footing, but this is not so: we can
alternatively define a symmetric version of (\ref{eq:logit}) by
defining, for each $c \in \cC$, a corresponding $c': \cX \rightarrow
\{-1,1\}$, $c'(x) := 2c(x) -1$. Then we can set
\begin{equation}
\label{eq:logitb}
p_{c,\beta}(1 \mid x) := \frac{e^{\beta c(x)}}{e^{\beta c(x)} + e^{-\beta c(x)}} \ \ ; \ \ 
p_{c,\beta}(-1 \mid x) := \frac{e^{-\beta c(x)}}{e^{\beta c(x)} + e^{-\beta c(x)}}.
\end{equation}
By setting $\beta = 2 \beta'$ we see that $p_{c,\beta}$ as in
(\ref{eq:logit}) is identical to $p_{c,\beta'}$ as in
(\ref{eq:logitb}), so that the two models really coincide.  

\section{Interpretation from a Bayesian perspective}
\label{sec:bayes}
We already addressed several questions concerning the relevance of our result 
directly below Corollary~\ref{cor:inconsistent}. Here we provide a more in-depth analysis from a Bayesian point of view.
\subsection{Bayesian Consistency}
\label{sec:bayescons}
It is well-known that Bayesian inference is strongly consistent under very
broad conditions (\citep{Doob49,BlackwellD62}; see also \citep{Barron85}). Such Bayesian
consistency results take on a particularly strong form if the set of
distributions under consideration is {\em countable}. In our
setting we can achieve this by adopting a discrete prior satisfying
(\ref{eq:discreteprior}). In that case, 
the celebrated \citep{Doob49} 
consistency theorem\footnote{In particular, see Eq. (3.6) in \citep{Doob49} combined with the
remark at the end of Section 3 of Doob's paper.} says the following for our setting. Let $\cC$
be countable and suppose
$D$ is such that, for some $c^* \in \cC$ and $\theta^* \in [0,1] \cap
{\mathbb Q}$,
$p_{c^*,\theta^*}$ is equal to $p_D$, the true distribution/ mass function of $y$ given
$x$. 
Then with $D$-probability
1,  the Bayesian posterior concentrates on $c^*$:
$ \lim_{m \rightarrow \infty} 
P( c^* \mid S^m) = 1$.

Consider now the learning problem underlying
Theorem~\ref{thm:bayesinconsistent} as described in
Section~\ref{sec:inconsistencyproof}. Since $c_0$ achieves $\min_{c
\in \cC} \erateD(c)$, it follows by part 1 of
Proposition~\ref{pro:trafo} that $\min_{c,\theta} \Delta(p_{c,\theta})
= \Delta(p_{c_0,\erateD(c_0)})$. {\em If\/} $
\Delta(p_{c_0,\erateD(c_0)})$ were $0$, then by part 2 of
Proposition~\ref{pro:trafo}, Doob's theorem would apply, and we
would have $P(c_0 \mid S^m) \rightarrow
1$. Theorem~\ref{thm:bayesinconsistent} states that this does {\em
not\/} happen.  It follows that the premise
$\Delta(p_{c_0,\erateD(c_0)}) = 0$ must be false. But since
$\Delta(p_{c,\theta})$ is minimized for $(c_0,\erateD(c_0))$, the
Proposition implies that for {\em no\/} $c \in \cC$ and {\em no\/}
$\theta \in [0,1] \cap {\mathbb Q}$, $p_{c,\theta}$ is equal to $p_D(\cdot|\cdot)$ - in
statistical terms, the model $\cP = \{ p_{c,\theta} : c \in \cC,
\theta \in [0,1] \cap {\mathbb Q} \}$ is {\em misspecified}.  Thus, the result can be
interpreted in two ways:
\begin{enumerate}
\item {\em `ordinary' Bayesian inference can be inconsistent under
    misspecification\/}: We exhibit a simple logistic regression model
  $\cP$ and a true distribution $D$ such that, with probability 1, the
  Bayesian posterior does not converge to the distribution
  $p_{c_0,\erateD(c_0)} \in \cP$ that minimizes, among all $p \in
  \cP$, the KL-divergence to $D$ (equivalently, $p_{c_0,\erateD(c_0)}$
  minimizes the $D$-expected log loss among all distributions in
  $\cP$).  Thus, the posterior does not converge to the optimal
  $p_{c_0,\erateD(c_0)}$ even though $p_{{c}_0,\erateD(c_0)}$ has
  substantial prior mass and is {\em partially\/} correct in the sense
  that $c_0$, the Bayes optimal classifier relative to
  $p_{{c}_0,\erateD(c_0)}$, has true error rate $\erateD(c_0)$, which
  is the {\em same\/} true error rate that it would have if
  $p_{{c}_0,\erateD(c_0)}$ were `true'.
\item {\em `pragmatic' Bayesian inference for classification can be
    suboptimal\/}: a standard way to turn classifiers into
  distributions so as to make application of Bayesian
  inference possible may give rise to suboptimal performance. 
\end{enumerate}

\subsection{Two types of misspecification} 
$p_{c_0,\erateD(c_0)}$ can be misspecified in
  {\em two different ways}. To see this, note that 
$p_{c_0,\erateD(c_0)}$ expresses that 
\begin{equation}
\label{eq:znoise}
y =
  c_0(x) \ {\tt xor} \ z,
\end{equation}
where $z$ is a noise bit generated
  independently of $x$.  This statement may be wrong under distribution $D$ either because
  (a) $c_0$ is not the Bayes optimal classifier according to $D$; or
  (b) $c_0$ is Bayes optimal, but $z$ is dependent on $x$ under $D$.
Let us consider both of them in more detail.  
\begin{description}
\item[(a) no Bayes optimal classifier in $\cC$]
The way we defined the learning problem $D$ 
used in the proof of Theorem~\ref{thm:bayesinconsistent}
(Section~\ref{sec:inconsistencyproof}) is an example of this case. 

This type of misspecification is subtle, because if we consider the
optimal $c_0$ {\em in isolation}, ignoring the features $X_i$ which do
not influence the prediction made by $c_0$, then the conditional
distribution $P(Y=1 \mid c_0(X), \theta^*)$ becomes correct after all,
in the sense that it is identical to the true conditional probability.
That is: for all $x_0 \in \{0,1\}$, we have
$$p_{c_0,\erateD(c_0)}(Y=1 \mid  X_0 = x_0) = 
\Pr_{X,Y \sim D}(Y=1 \mid
 c_0(X) = x_0, X_0 = x_0),$$
so $p_{c_0,\erateD(c_0)}(\cdot \mid X_0 = x_0)$ is `true'. This may 
imply that the set of distributions corresponding to $\cC$ is well-specified,  
since $c_0$ only `listens' to feature $X_0$. 
Yet still,  misspecification occurs because for some $x \in\{0,1\}^\infty$,
$$p_{c_0,\erateD(c_0)}(Y=1 \mid  X = x) {\mathbf \neq}
\Pr_{X,Y \sim D}(Y=1 \mid c_0(X) = x_0, X= x).$$
\item[(b) $\cC$ contains Bayes act, but $D$ is heteroskedastic] 
  It may seem that our theorem is only applicable to misspecification
  of type (a). But it is easy to see that it is just as applicable to
  the - arguably less serious - misspecification of type (b). Namely,
  in the proof of Theorem~\ref{thm:bayesinconsistent}
  (Section~\ref{sec:inconsistencyproof}), we could have equally used
  the following slightly modified learning problem : step 1 and step 2
  remain identical, so $c_1, c_2, \ldots$ are defined as before. The
  optimal $c_0$ is now defined by modifying step 3 as follows: for an
  easy example, we set $x_0 = y$. For a hard example, we set $x_0 =
  |1- y|$ with probability $\mu/ 2 \mu'$.  Then the proof of
  Theorem~\ref{thm:bayesinconsistent} holds unchanged.  But now $c_0$
  {\em is\/} the Bayes optimal classifier relative to $D$, as is easy
  to see.
\end{description}
\subsection{Why is the result interesting for a Bayesian?}
Here we answer several objections that a cautious Bayesian might have
to this work.
\renewcommand{\thesubsubsection}{\thesubsection.\arabic{subsubsection}}
\subsubsection{Bayesian inference has never been designed to work
under misspecification. So why is the result relevant?} \ 
\\
We would maintain that in {\em practice}, Bayesian inference is applied
{\em all the time\/} under misspecification in classification
problems \citep{Grunwald98b}. It is
very hard to avoid misspecification with Bayesian classification,
since the modeler often has no idea about the noise-generating
process. Even though it may be known that noise is not
homoskedastic, it may be practically impossible to incorporate 
all ways in which the noise may depend on $x$ into the prior.

\subsubsection{It is already  well-known that Bayesian inference
can be inconsistent even if $\cP$ is {\em well-specified}, i.e. if it
contains $D$ \citep{DiaconisF86,Barron98}. So why is this result interesting?} \
\\ \label{sec:diaconis} The (in)famous inconsistency results by 
\citep{DiaconisF86} are based on nonparametric inference with
uncountable sets $\cP$. It follows from  \citep{Barron98}
that their theorems require that the true
distribution $D$ has
`extremely small' prior density in the following sense: 
the prior mass of
$\epsilon$-Kullback-Leibler balls around $D$ is exponentially
small in $1 / \epsilon$. Since such priors do not allow
one to compress the data, from an MDL perspective it is not at all
surprising that they lead to inconsistent inference \citep{Barron98}.
In contrast, in our result, rather than small prior densities 
we require misspecification. Since Diaconis and Freedman do not
require misspecification, in a 
sense, our result is weaker. On the other hand, in our setting,
the prior on the $p \in \cP$ closest in KL divergence to the true
conditional distribution $p_D$ can be arbitrarily close to $1$,
whereas Diaconis and Freedman require the prior of the `true' $p_D$ to
be exponentially small in the sense explained above. In this sense,
our result is stronger than theirs.

\cite{Barron98} exhibits an example of Bayesian inconsistency that is
closer in spirit to ours. In his example, the prior {\em density\/}
of KL-neighborhoods of the true $D$ can be substantial. Nevertheless,
his example requires that $\cP$ contains uncountably many
distributions. It is not possible to extend Barron's example to a case with
only countably many distributions, since in that
case, the posterior {\em must\/}  concentrate\footnote{More precisely,
  the posterior mass on the set of all distributions in $\cP$ that are
  mutually singular with $D$ must go to $0$ with $D$-probability 1.} on the true $D$  by Doob's result. Our result shows that even in the countable case, as
soon as one allows for slight misspecification, the posterior may not
converge to the best distribution in $\cP$. Indeed, by an appropriate setting of the parameters
$\mu$ and $\mu'$ it is seen from Theorem~\ref{thm:bayesinconsistent}  
that for every $\epsilon > 0$, no matter
how small, we can exhibit a $D$ with
$$
\min_{c,\theta} {\rm KL}(p_D \| p_{c,\theta}) = \epsilon
$$
for which Bayes is inconsistent with
$D$-probability 1.  This is interesting because even under
misspecification, Bayes is consistent under fairly broad conditions
\citep{BunkeM98,KleijnvdV04}, in the sense that the posterior
concentrates on a neighborhood of the distribution that minimizes
KL-divergence to the true $D$. We showed that if such conditions are
violated, then consistency may fail dramatically. Thus, we feel our result is relevant
at least from the {\em inconsistency under misspecification\/}
interpretation.
\subsubsection{So how can the result co-exist with theorems establishing
  Bayesian consistency under misspecification?} \ 
\\ \label{sec:consistmis}
Such results are typically proved under either one of the following
two assumptions:
\begin{enumerate}
\item The set of distributions $\cP$ is `simple', for example,
  finite-dimensional parametric. In such cases, ML estimation is
  usually also consistent - thus, for large $m$ the role of the prior
  becomes negligible. In case $\cP$ corresponds to a classification
  model $\cC$, this would occur if $\cC$ were finite or had finite VC-dimension for example.
\item $\cP$ may be arbitrarily large or complex, but it is {\em
    convex\/}: any finite mixture of elements of $\cP$ is an element
  of $\cP$. An example is the family of Gaussian mixtures with an
  arbitrary but finite number of components. 
%peter3 added 
Theorem 5.5 of \citep{Li97} shows that for general convex i.i.d. families (not just
  Gaussian mixtures), under conditions on the priors, two-part MDL
  (essentially the version of MDL that we consider here) is consistent
  in the sense of expected Kullback-Leibler risk. 
Although we have no
  formal proof, Li's result strongly suggests that with such priors,
  the Bayesian MAP and full Bayesian approach will also be consistent.
\end{enumerate}
Our setup violates both conditions: $\cC$ has infinite VC-dimension,
and the corresponding $\cP$ is not closed under taking mixtures. The latter issue is discussed further in Example~\ref{ex:mix}. 

\subsubsection{How `standard' is the conversion from classifiers to
  probability distributions on which the results are based?}\label{sec:bayestest} \ \\ One may argue that the notion of `converting'
classifiers into probability distributions is not always what
Bayesians do in practice.  For classifiers which produce {\em
  real-valued} output, such as neural networks and support vector
machines, the transformation coincides with the logistic regression
transformation, which is a standard Bayesian tool; see for example
\citep{Jordan95,Platt99,Tipping01}. But the theorems are based on
classifiers with $0/1$-output. With the exception of decision trees,
such classifiers have not been addressed frequently in the Bayesian
literature. Decision trees have usually been converted to conditional
distributions somewhat differently: one uses the same logistic
transformation as we do, but one assumes a different noise rate {\em
  in each leaf\/} of the decision tree \citep{HeckermanCMRK00}; thus,
the transformation is done locally for each leaf rather than globally
for the whole hypothesis.  Since the noise rate can depend on the
leaf, the set of all decision trees of arbitrarily length
on a given input space $\cX$ coincides with the set of all conditional
distributions on $\cX$. Thus it avoids the misspecification, and
therefore the inconsistency problem, but at the cost of using a much
larger model space.

Thus, here is a potentially weak point in the analysis: we use a
transformation that has mostly been applied to real-valued
classifiers, whereas here the classifiers are $0/1$-valued.
Nevertheless, to get an idea of how reasonable our transformation is,
we simply {\em tested\/} it with three professing Bayesians. We did this in
the following way: we first described the set of classifiers ${\cal
  C}$ used in the learning problem, and we said that we would like to
perform Bayesian inference based on some prior over ${\cal C}$. We
then asked the Bayesian how (s)he would handle this problem. All three
Bayesians said that they would construct conditional distributions
according to the logistic transformation, just as we did.
We take this as evidence that the logistic 
transformation is reasonable, even for classifiers with binary outputs.

Whether the inconsistency results can be extended in a natural way to
classifiers with real-valued output such as support vector machines
remains to be seen. The fact that the Bayesian model corresponding to
such neural networks will still typically be misspecified strongly
suggests (but does not prove) that similar scenarios may be
constructed.

\subsubsection{Is there an alternative, more sophisticated transformation that avoids inconsistencies?}
Even though the transformation we perform is standard, there may exist
some other method of transforming a set of classifiers$+$prior into a
set of distributions$+$prior that avoids the problems. There are only
two obvious options which suggest themselves:
\begin{description}
\item[1. Avoiding Misspecification] First, we can try to avoid
  misspecification; then by the strong Bayesian consistency theorems
  referred to in Question~\ref{sec:diaconis}, we should be guaranteed
  to converge to the optimal classifier.  However, as we explain
  below, this is often not practical.
\item[2. Ensuring $\cP$ is Convex] Second, rather than using the set
  of transformed classifiers $\cP$, we could put a prior on its convex
  closure $\overline{\cP}$ (this is the set of all finite and infinite
  mixture distributions that can be formed from elements of $\cP$.
  Note in particular that $\cP$ and $\overline{\cP}$ are sets of
  distributions defined on one outcome, not on a sample of $m > 1$
  outcomes).  Then, we can once again apply the consistency theorem
  for convex $\cP$ referred to in Question~\ref{sec:consistmis}, and
  we should be guaranteed to converge to the optimal distribution.
  Computational difficulties aside, this approach will not work,
  because now the distribution we converge to may not be the
  distribution we are interested in, as we describe further below.
\end{description}
Thus, the only two straightforward solutions to the transformation
problem are either impractical or do not work. We discuss both of
these in detail below. There may of course exist some clever
alternative method that avoids all problems, but we have no idea how
it would look like.
\paragraph{1. Can we ensure consistency by avoiding misspecification?}
>From a subjective Bayesian perspective, one might require the learning
agent to think hard enough about his or her prior probabilities so
that the set of conditional distribution $\cP$ does contain $D$, the
true state of nature. In practice this means that one should ensure
that $\cC$ contains the Bayes optimal classifier with respect to $D$,
and that $\cP$ should contain distributions in which the noise $z$
(Equation (\ref{eq:znoise})) can depend on the feature value $x$. In
practical machine learning applications one will often have no idea
how the Bayes optimal classifier behaves or how the noise
depends on $x$. Thus, the only way to proceed seems to design a prior
on {\em all\/} possible classifiers and {\em all\/} possible noise
rate functions. Now the inconsistency problem is solved, because the
(`nonparametric') model thus constructed is guaranteed to contain the
true (conditionalized) distribution $D$, so common Bayesian
consistency theorems (see above) apply.  However, the cost may be
enormous: the model space is now {\em much\/} larger and it seems that a
lot more data may be needed before a reasonable approximation of $D$
is learned -- although interestingly, recent work by M.
\cite{Hutter05} suggests that under suitable priors, reasonable approximations
may be learned quite fast. It is not clear whether or not something
like this can be done in our context. 
% (Nevertheless, such a
%`nonparametric Bayes' approach is sometimes successfully applied in
%practice -- it can be argued that Gaussian process models for
%classification \cite{} try to achieve just this).
\paragraph{2. Can we ensure consistency by using convex models?}
Suppose we first use the logistic transformation to transform the 
classifiers $\cC$ into a set of conditional distributions $\cP$, and we then 
put a prior on its convex
  closure $\overline{\cP}$ and use Bayesian inference based on
  $\overline{\cP}$. Now , Li's result (Section~\ref{sec:consistmis})
  suggests that the Bayesian posterior predictive distribution is 
(under weak conditions on the prior) guaranteed to converge to the closest distribution $p^*$ to $D$ within $\overline{\cP}$, as measured in KL-divergence. However, 
as the following example shows, $p^*$ may end up having {\em larger\/}
generalization error (expected $0/1$-loss) than the optimal classifier
$c^*$ in the set $\cC$ on which $\cP$ was based. Thus, existing
theorems suggest that 
with a prior on $\overline{\cP}$, the Bayesian posterior will
{\em converge}, but below we show that if it does converge, then it
will sometimes converge  to a distribution that is
suboptimal in the performance measure we are interested in.
\begin{example}[classification error and taking mixtures]
\label{ex:mix}
\rm  %peter1 this example shows that there is NO EASY FIX 
% to making the transformation
% between classifiers and distributions work.
% we can perhaps leave out some of the details to shorten it; but i would really 
% like to keep it in. Also because we should have some extra meat 
% in the journal paper as compared to the conference paper!
We consider the following learning problem. There are three
  classifiers $\cC = \{c_1, c_2, c_3\}$ and three features $X_1, X_2,
  X_3$ taking values in $\{0,1\}$. Each classifier simply outputs the
  value of the corresponding feature. The underlying distribution $D$
  is constructed as follows. We distinguish between three `situations'
  $s_1, s_2, s_3$ (these are the values of some random variable $S'
  \sim D$ that is not observed). To construct an example $(x,y)$, we
  first flip a fair coin to determine $y$, so $y =1$ with probability
  $1/2$. We then flip a fair three-sided coin to determine what
  situation we are in, so $S'= s_j$ with probability $1/3$, for $j \in
  \{1,2,3\}$. Now if we happen to be in situation $s_j$, we
\begin{enumerate}
\item Set $x_j = y$ (so $c_j$ will predict $Y$ correctly).
\item Flip a fair coin, determine the outcome $z \in \{0,1\}$, and set $x_{j'} = z$ for the two values of $j' \in \{1,2,3\}$ that are not equal to $j$. 
\end{enumerate} 
Thus, the value of $x_{j'}$ is determined completely at random, but must be the same for both features not equal to $j$. We thus have for $j = 1,2,3$:
\begin{eqnarray}
\label{eq:snowy}
\erateD(c_j) & = & 
\frac{1}{3} \cdot 0 + \frac{2}{3} \cdot \frac{1}{2} = \frac{1}{3}, \\
\label{eq:boxz}
\KL(p_D \| p_{c_j,\erateD(c)}) & = &  
E_{(x,y) \sim D} [ - \log p_{c_j,\erateD(c_j)}(y|x) + \log p_{D}(y|x)] = 
\nonumber \\ & & 
H(\erateD(c_j)) - K_D = 
H(\frac{1}{3}) - K_D 
%= \log 3 - \frac{2}{3} - K_D 
> .9 - K_D.
\end{eqnarray}
Equation (\ref{eq:boxz}) follows by (\ref{eq:turnaround}), and as in that equation, $H$ is the binary entropy as defined above
Theorem~\ref{thm:bayesinconsistent}, and $K_D$ is the conditional
entropy of $y$ given $x$ according to $D$, which does not depend on $j$.
 
Thus, the distribution(s) in $\cP := \{ p_{c_j,\theta} \mid j \in
\{1,2,3\}, \theta \in [0,1 ] \}$ closest to the underlying $D$ in
KL-divergence have KL divergence $H(\frac{1}{3}) - K_D$ to $D$.

Now consider the set of conditional distributions $\overline{\cP}$
defined as the convex closure of $\cP$. It is easy to see that each element of
$\overline{\cP}$ can be written as a three-component mixture
$$
\overline{p}_{\vec{\alpha},\vec{\theta}} := \alpha_1 p_{c_1,\theta_1} + \alpha_2 p_{c_2,\theta_2} + \alpha_3 p_(c_3,\theta_3),
$$
for some vector $\vec{\alpha} = (\alpha_1, \alpha_2,\alpha_3)$ with
nonnegative entries summing to $1$, and $(\theta_1,
\theta_2,\theta_3)$ with nonnegative entries $\leq 1$.  Thus, the
distribution in $\overline{P}$ that is closest to $D$ in KL divergence
is the distribution 
%$\overline{p}^* :=
%\overline{p}_{\vec{\alpha},\vec{\theta}}$ 
that achieves the minimum
over $\vec{\alpha}$ and $\vec{\theta}$ of the expression
\begin{equation}
\label{eq:boxy}
 \KL(p_D \| p_{\vec{\alpha},\vec{\theta}}) = 
E_{(x,y) \sim D} [\log \frac{1}{p_{\vec{\alpha},\vec{\theta}}(y|x)}] 
- K_D. 
\end{equation}
\commentout{
%peter1 probably we don't want this in explicitly. Too long
\begin{multline}
= \\
\frac{1}{3}\left[ 
\frac{1}{2} \log 
\frac{1}{\alpha_1 (1- \theta_1) + \alpha_2 (1- \theta_2) + \alpha_3 (1- \theta_3)} 
+ \frac{1}{2} \log 
\frac{1}{\alpha_1 (1- \theta_1) + \alpha_2 (\theta_2) + \alpha_3 (\theta_3)} 
\right] + \\
\frac{1}{3}\left[ 
\frac{1}{2} \log 
\frac{1}{\alpha_2 (1- \theta_2) + \alpha_1 (1- \theta_1) + \alpha_3 (1- \theta_3)} 
+ \frac{1}{2} \log 
\frac{1}{\alpha_2 (1- \theta_2) + \alpha_1 (\theta_1) + \alpha_3 (\theta_3)} 
\right] + \\
\frac{1}{3}\left[ 
\frac{1}{2} \log 
\frac{1}{\alpha_3 (1- \theta_3) + \alpha_2 (1- \theta_2) + \alpha_1 (1- \theta_1)} 
+ \frac{1}{2} \log 
\frac{1}{\alpha_3 (1- \theta_3) + \alpha_2 (\theta_2) + \alpha_1 (\theta_1)} 
\right] \\
- K_D.
\end{multline}
where we split out the sum in the expectation over the three possible
situations $s_1,s_2$ and $s_3$.  } 
This expression is uniquely
minimized for some $\overline{p}^*$ with parameters
\begin{equation}
\label{eq:frutsel}
\alpha^*_1 = \alpha^*_2 = \alpha^*_3 = \frac{1}{3}
\text{\ and some $\theta^* \in [0,1]$ with \ } 
\theta^* =
\theta_1 = \theta_2 = \theta_3. 
\end{equation}
To see this, note that by symmetry of
the problem, $ \KL(p_D \| p_{\vec{\alpha},\vec{\theta}}) = \KL(p_D \|
p_{\vec{\alpha}',\vec{\theta}'})$ where 
$\vec{\alpha}' := (\alpha_2,\alpha_1,\alpha_3)$ and 
%\text{\ and \ }
$\vec{\theta}' :=  (\theta_2, \theta_1,\theta_3) 
$.
Since $\overline{\cP}$ is closed under mixing, for any $\gamma \in
[0,1]$, $p_\gamma := \gamma p_{\vec{\alpha},\vec{\theta}} + (1-
\gamma) p_{\vec{\alpha}',\vec{\theta}'}$ must be in $\overline{\cP}$.
By strict convexity of KL divergence \citep{CoverT91} and symmetry of the
problem, $\KL(p_D \| p_{\gamma})$ is uniquely minimized for $\gamma =
1/2$, and then $p_{\gamma}$ satisfies $\alpha_1 = \alpha_2$ and
$\theta_1 = \theta_2$.  In the same way one shows that the minimizing
$\vec{\alpha}$ and $\vec{\theta}$ have to satisfy $\alpha_2 =
\alpha_3$, $\theta_2 = \theta_3$ and $\alpha_1 = \alpha_3, \theta_1 =
\theta_3$, and (\ref{eq:frutsel}) follows.  Now plugging the
minimizing parameters (\ref{eq:frutsel}) into (\ref{eq:boxy}) gives
\begin{multline}
 \KL(p_D \| \overline{p}^*) =
\min_{\theta \in [0,1]} 
\KL(p_D \| p_{\vec{\alpha}^*,\vec{\theta}^*}) = \\
\min_{\theta}
-\frac{1}{2} \left [\log (1 - \theta)  + \log (1 +\theta) - \log 3 \right] 
- K_D = \frac{1}{2} \log 3 - K_D < .8 - K_D,
\end{multline}
which is  strictly smaller than (\ref{eq:boxz}).  Therefore, while (a)
Li's consistency result (Section~\ref{sec:consistmis}) for convex
$\overline{P}$ suggests that  both the
Bayesian posterior and Bayesian MAP conditional distribution will
converge (in expected KL-divergence), to
$\overline{p}^*$, it turns out that, (b)  
the classification error rate of the 
Bayes classifier $c_{p^*}$ corresponding to the resulting
conditional distribution $\overline{p}^*$ is equal to
$$
E_{x,y \sim D}[|y - c_{p^*}(x)| ]=
\left[ \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 0 \right] = \frac{1}{2},
$$
which is {\em worse\/} than the optimal classification error rate
that can be obtained within $\overline{\cP}$: since $\cP \subset
\overline{\cP}$, by (\ref{eq:snowy}) this error rate must be $\leq
1/3$.

Concluding, with $D$-probability 1, for large $m$, the error rate of
the Bayes classifier based on the Bayesian posterior relative to
$\overline{\cP}$ will have classification error that is {\em larger\/}
than that of the Bayesian posterior relative to ${\cP}$: it
is clear that by enlarging the model $\cP$ to its convex closure,
rather than sometimes not converging at all, we may now converge to a
suboptimal distribution: instead of solving the problem, we merely
replaced it by another one.
\end{example}
\subsubsection{Isn 't the example just ''unnatural''?}
Upon hearing our results, several people objected that our learning
problem is ``unnatural''. We agree that it is unlikely that one will
ever deal with such a scenario in practice. However, this does not
rule out the possibility that related phenomena do occur in more
practical settings; see \citep{Clarke04} for an example in a regression
context. Part of the problem here is of course that it is not really
clear what ``unnatural'' means. Indeed, it is certainly not our aim to
show that ``Bayesian inference is bad''. Instead, one of our main messages is that  more research is needed to determine under what types of
misspecification Bayes performs well, and under what types it does
not.
\section{Interpretation from an MDL Perspective}
\label{sec:mdl}
We now discuss the interpretation of our result from an MDL
Perspective. Similar to the Bayesian analysis, we do this by answering
objections that a cautious description length minimizer might have to
this work. 
\addtocounter{subsection}{1}
\addtocounter{subsubsection}{-6}
\subsubsection{Why is the two-part code (\ref{eq:cmdl}) the appropriate formula to work with? Shouldn't we use more advanced versions of MDL based on one-part codes?}
Equation (\ref{eq:cmdl}) has been used for classification by various
authors; see, e.g., \citep{Rissanen89,QuinlanR89} and
\citep{KearnsMNR97}.  \citep[Chapter 5]{Grunwald98b} first noted that
in this form, by using Stirling's approximation, (\ref{eq:cmdl}) is
essentially equivalent to MAP classification based on the models
$p_{c,\theta}$ as defined in Section~\ref{sec:algorithms}.  Of course,
there exist more refined versions of MDL based on one-part rather than
two-part codes \citep{BarronRY98}. To apply these to classification,
one somehow has to map classifiers to probability distributions
explicitly. This was already anticipated by \cite{MeirM95} who used
the transformation described in this paper to define one-part MDL
codes. The resulting approach is closely related to the Bayesian
posterior approach $\cbayes$, suggesting that a version of the
inconsistency Theorem~\ref{thm:bayesinconsistent} still applies.
\cite{Rissanen89} considered mapping classifiers $\cC$ to
distributions $\{ p_{c,\theta^*} \}$ to a {\em single\/} value of
$\theta^*$, e.g., $\theta^* = 1/3$. As discussed in
Section~\ref{sec:technical}, a version of
Theorem~\ref{thm:bayesinconsistent} still applies to the resulting
distributions.

We should note that both \cite{WallaceP93} and \cite{QuinlanR89}
really use an extension of the coding scheme expressed by
(\ref{eq:cmdl}), rather than the exact formula (\ref{eq:cmdl}) itself: both
publications deal with decision trees, and apply (\ref{eq:cmdl}) on
the level of the leaf nodes of the decision trees.  The actual
codelength for the data given a decision tree becomes a sum of
expressions of the form (\ref{eq:cmdl}), one for each leaf.  This
means that they are effectively estimating error rates separately for
each leaf. Since their model consists of the set of all decision trees
of arbitrary depth, they can thus essentially model almost any conditional
distribution of $Y$ given $X$. This makes their approach
nonparametric, and therefore, broadly speaking, immune to
misspecification as long as data are i.i.d., and therefore immune to
our results: inconsistency can only arise if the coding scheme
(\ref{eq:cmdl}) is applied to a model that can only present
homoskedasticity, whereas the data generating distribution is
heteroskedastic.  It is not clear though whether the use of
nonparametric models such as decision trees always solves the problem
in {\em practice}, as we already discussed in Section 6.3.5., Question
1.  As a further (but inessential) difference, \cite{QuinlanR89} use
one extra bit on top of (\ref{eq:cmdl}) for each leaf node of the
decision tree.  \cite{WallaceP93} point out that this is unnecessary,
and use more general codes based on Beta-priors, of which our code
(\ref{eq:cmdl}) is a special case, obtained with the uniform prior
(see Proposition~\ref{prop:uniboem} in the Appendix). As can be seen
from the proof of Theorem 2, the use of general Beta-priors in the
definition of MDL will not affect the inconsistency result.



\subsubsection{Does the coding scheme for hypotheses make sense from an MDL perspective?}
MDL theory prescribes the design of codes for hypothesis spaces
(roughly corresponding to priors) that minimize worst-case regret or
redundancy \citep{BarronRY98,Grunwald07} of the resulting codelength of
hypothesis $+$ data. It may seem that our coding scheme for hypotheses
does not satisfy this prescription. But in fact, it does: if no
natural grouping of the hypotheses in subclasses exists (such as with
Markov chains, the class of $k$-th order Markov chains being a natural
subclass of the class of $k+1$-st order chains), then the `best', from
an MDL perspective, code one can assign is a code such that the code
length of $c_i$ goes to infinity as slowly as possible with increasing
index $i$ \citep{Grunwald07}, such as Rissanen's universal code for the
integers (Equation~\ref{eq:priora}).  But this is exactly the type of
codes to which our Theorem~\ref{thm:bayesinconsistent} applies!

Lest the reader disagree with this: according to `standard' MDL
theory, if $\cP$ is well-specified and countable then the coding
scheme should even be asymptotically irrelevant: {\em any\/} coding
scheme for the hypothesis where the codelength of any $P \in \cP$ does
not depend on $n$, will lead to asymptotically consistent MDL
inference under very weak conditions \citep{BarronC91}; 
see also Chapter 5, Theorem 5.1 of \citep{Grunwald07}. Special
types of codes minimizing worst-case regret are only needed to {\em
  speed up\/} up learning with small samples; for large samples, any
code will do.  Thus, our result shows that if a set of classifiers
$\cC$ is used (corresponding to a misspecified probability model
$\cP$), then the choice of prior becomes of crucial importance, even
with an infinite amount of data.
\subsubsection{It seems that MDL can already be inconsistent even if ${\cal P}$ is well-specified. So why is the result interesting?}
This question mirrors Question 6.3.2. In Section 1.2 of
\citep{WallaceD99b}, a very simple problem is discussed for which a
straightforward implementation of a two-part code estimator behaves
quite badly, even though the true distribution is contained in the
model ${\cal P}$, and ${\cal P}$ only contains 1 continuous-valued
parameter. This suggests that MDL may be inconsistent in a setting
that is much simpler than the one we discuss here. But this is not
quite the case: if the true distribution is contained in
${\cal P}$, then {\em any\/} two-part code will be asymptotically
consistent, as long as the code is `universal'; see Theorem 15.3 in Chapter 15
of \citep{Grunwald07}.  Under the definition of MDL that has generally
been adopted since \cite{BarronRY98}, an estimator based on a two-part
code can only be called `MDL estimator' if the code is universal. Thus, it may either be the case that the
two-part code defined by \cite{WallaceD99b} is not universal, and
hence not an MDL code, or their two-part code must be asymptotically
consistent after all. We suspect that the latter is the case. From an
MDL perspective, the interest in our example is that, under
misspecification, we can get inconsistency, even though we do
use a universal two-part code.

\subsubsection{Haven't \cite{KearnsMNR97} already shown that MDL is no good for classification?}
It may seem that the results are in line with the investigation of
\cite{KearnsMNR97}. This, however, is not clear -- Kearns et al.
consider a scenario in which two-part code MDL for classification
shows quite bad experimental performance for large (but not infinite!)
sample sizes.  However, according to \cite{ViswanathanWDK99}, this is
caused by the coding method used to encode hypotheses. This method
does not take into account the precision of parameters involved
(whereas taking the precision into account is a crucial aspect of
MDL!).  In the paper \citep{ViswanathanWDK99}, a different
coding scheme is proposed. With this coding scheme, MML (an inference method that is related to MDL, see  below) apparently behaves quite well on the
classification problem studied by Kearns et al.  In contrast to
Kearns' example, in our case (a) there is no straightforward way to
improve the coding scheme; (b) MDL fails even on an infinite sample.
\subsubsection{What about MML?}
The {\em Minimum Message Length (MML) Principle\/}
\citep{WallaceB68,ComleyD05,Wallace05} is a method for inductive
inference that is both Bayesian and compression-based. The similarities and differences with MDL are subtle; see, for example, Section 10.2 of \citep{Wallace05} or Section 17.4 of \citep{Grunwald07}, or \citep{WallaceD99a,WallaceD99b}. An anonymous
referee raised the possibility that MML may be consistent for the
combination of the learning problem and the misspecified probability
model discussed in this paper.  We suspect that this is not the case,
but we are not sure of this, and for the time being, the question of
whether or not MML can be inconsistent under misspecification in
classification contexts remains open. For the well-specified case, it
is conjectured on page 282 of \citep{WallaceD99a} that only MML or
closely related techniques can infer fully-specified models with both
statistical consistency and invariance under one-to-one
parameterization.
\paragraph{Related Work}
\cite{Yamanishi98} and \cite{Barron91} proposed
modifications of the two-part MDL coding scheme so that it would be
applicable for inference with respect to general classes of predictors
and loss functions, including classification with $0/1$-loss as a
special case. Both Yamanishi and Barron prove the consistency (and
give rates of convergence) for their procedures.  Similarly,
McAllester's (1999) PAC-Bayesian method can be viewed as
a modification of Bayesian inference that is provably consistent for
classification, based on sophisticated extensions of the Occam's Razor
bound, 
Theorem~\ref{thm:orb}.
%Both Yamanishi's and
%Barron's schemes are provably consistent; (very roughly speaking they
%modify the two-part code criterion by multiplying the description
%length $L_1(c)$ by a factor of order $O(\sqrt{m})$ or $O(\sqrt{m}/
%\log m)$. 
These modifications anticipate our result, since it must have been
clear to the authors that without the modification, MDL (and discrete
Bayesian MAP) are not consistent for classification. Nevertheless, we
seem to be the first to have explicitly formalized and proved this.
\section{Conclusion and Future Work}
We showed that some standard versions of MDL and Bayesian inference
can be inconsistent for a simple classification problem, and we
extensively discussed the interpretation of this result. As possible
future work, it would be interesting to investigate
\begin{enumerate}
\item Whether there is a more natural learning problem, especially a
  more natural feature space, with respect to which an analogue to our
  result still holds.
\item Whether a similar result holds for regression rather than
  classification problems. We conjecture that the answer is {\em yes,
    but the suboptimality will be less dramatic}.
\end{enumerate}
\section{Acknowledgments}
The ideas in this paper were developed in part during the workshop
{\em Complexity and Inference}, held at the DIMACS center, Rutgers
University, June 2003.  We would like to thank Mark Hansen, Paul
Vit\'anyi and Bin Yu for organizing this workshop, and Dean Foster and
Abraham Wyner for stimulating conversations during the workshop. 
%peter3 added
We would especially like to thank Marcus Hutter who pointed out an
error in a previous version of Theorem 2.

This work was supported in part by the IST Programme of the European
Community, under the PASCAL Network of Excellence,
IST-2002-506778. This publication only reflects the authors' views.
%\bibliographystyle{plain} 
\bibliography{master,MDL,peter}
\appendix
\section*{Appendix: Proposition~\ref{prop:uniboem} and its Proof}
\begin{proposition}
\label{prop:uniboem}
Consider any given sample $S$ of arbitrary size $m$. 
\begin{enumerate} 
\item Let $c \in \cC$ be an arbitrary classifier and let 
$P(\theta|c)$ be given by the
uniform prior with $P(\theta \mid c) \equiv 1$. 
Then
\begin{multline}
\label{eq:uniboem}
- \log P(y^m \mid x^m, c) = - \log \int_0^1 P(y^m \mid x^m, c, \theta) d \theta
= \\ \log (m+1) + \log \binom{m}{m\hat{e}_S(m)}.
\end{multline}
so that, if the uniform prior is used, then $\cmdl = \csmapb$.
\item Suppose that $P(\theta \mid c)$ satisfies  (\ref{eq:priorb}) or (\ref{eq:discreteprior}), and that for some $\alpha > 0$, $\hat{e}_S(c) < 0.5 - \alpha$. Then
\begin{multline}
\label{eq:bayesbound}
m H(\hat{e}_S(c)) = \log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))}
\leq   \log \frac{1}{P(y^m \mid x^m, c)} 
\leq \\
 \log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))} +
f_{\alpha}(m) =
%$ \ \\ 
%\ \ \ \ \ \ \ \ \ \ $\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } 
m H(\hat{e}_S(c)) + f_{\alpha}(m), 
%$ \ 
\end{multline}
where $f_{\alpha}(m) = O(\log m)$, and the constant in the $O$-term
may depend on $\alpha$.
\end{enumerate}
\end{proposition}
\begin{proof}
We recognize the integral in (\ref{eq:uniboem}) as being a
  beta-integral. Straightforward evaluation of the integral (e.g. by
  partial integration) gives the result of part (1).
For part (2), the leftmost and rightmost equalities follow by straightforward
rewriting. The first inequality follows because 
\begin{multline}
\log \frac{1}{P(y^m \mid x^m, c)} = 
\log \frac{1}{\int P(y^m \mid x^m, c,\theta) P(\theta) d\theta}
\geq 
\log \frac{1}{P(y^m \mid x^m, c, \hat{e}_S(c))}, \nonumber
\end{multline}
since the likelihood $P(y^m \mid x^m, c, \theta)$ is maximized
at $\theta = \hat{e}_S(c)$. 
For the second inequality, we first consider the case that 
$P(\theta|c)$ satisfies (\ref{eq:priorb}). Then using (\ref{eq:uniboem}),
\begin{multline}
\log \frac{1}{P(y^m \mid x^m, c)} \leq 
 - \log \int_0^{0.5} P(y^m \mid x^m, c, \theta) d \theta - \log \gamma 
\leq \\ - \log 
\int_0^{1} P(y^m \mid x^m, c, \theta) d \theta
+ \log \frac{\int_0^{1} P(y^m \mid x^m, c, \theta) d \theta}{
\int_0^{0.5} P(y^m \mid x^m, c, \theta) d \theta}  - \log \gamma = \\
\log (m+1) + \log
\binom{m}{m\hat{e}_S(m)} - \log \gamma + o(1),
\end{multline}
where the constant in the $o(1)$ depends on $\alpha$.
The result for $P(\theta)$ satisfying (\ref{eq:priorb}) now follows
upon noting that for all $s \in \{0, 1, \ldots, m \}$, $m H(s/m) \geq
\log \binom{m}{s}$. This is the case because $m H(s/m)$ is the number
of bits needed to encode $m$ outcomes with $s$ ones, using a Bernoulli
distribution with parameter $s/m$; whereas $\log \binom{m}{s}$ is the
number of bits needed to encode $m$ outcomes with $s$ ones, using a
Bernoulli distribution with parameter $s/m$, conditioned on the
relative frequency of $1$s being $s/m$ -- thus, the same sequence is
encoded using the same code, but conditioned on extra information, so
that equally many or less bits are needed.

Now consider the case that $P(\theta| c)$ satisfies (\ref{eq:discreteprior}). Then \begin{multline}
P(y^m \mid x^m, c) = \sum_{\theta \in [0,1] \cap {\mathbb Q}} 
P(y^m \mid x^m, c, \theta) P(\theta | c) \geq \\
P(y^m \mid x^m, c, \hat{e}_S(c) )P(\hat{e}_S(c) = \theta | c) \geq
P(y^m \mid x^m, c, \hat{e}_S(c) ) K_1 m^{-K_2},
\end{multline} 
for some constants $K_1$ and $K_2$. The result now follows by taking negative 
logarithms.
\end{proof}
\end{document}
