
\documentclass[jair,11pt,letterpaper]{article}

\usepackage{jair}
\usepackage{theapa}

\usepackage{amsmath,amssymb}
\usepackage{graphics,epsfig}
\usepackage[usenames,dvipsnames]{color}
\usepackage{color,epsfig}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{url}
%\usepackage{jmlr2e}
\usepackage[usenames,dvipsnames]{color}
%\usepackage{boxit}


\begin{document}

\jairheading{22}{2004}{117-142}{07/03}{10/04}
\ShortHeadings{Explicit Learning Curves for Transduction}
{Derbeko, El-Yaniv, \& Meir} \firstpageno{117}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% titles/headings
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Explicit Learning Curves for Transduction and
Application to Clustering and Compression Algorithms}

\author{\name Philip Derbeko \email philip@cs.technion.ac.il
        \AND
        \name Ran El-Yaniv \email rani@cs.technion.ac.il\\
         \addr Department of Computer Science\\
            Technion - Israel Institute of Technology\\
            Haifa 32000, Israel
        \AND
        \name Ron Meir \email rmeir@ee.technion.ac.il \\
       \addr Department of Electrical Engineering\\
            Technion - Israel Institute of Technology\\
            Haifa 32000, Israel }


\maketitle

%\bibliographystyle{unsrt}

% shamelessly copied from JMLR - START
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                               PROOF, THEOREM, and FRIENDS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\BlackBox}{\rule{1.5ex}{1.5ex}}  % end of proof
\newenvironment{proof}{\par\noindent{\bf Proof\ }}{\hfill\BlackBox\\[2mm]}
\newtheorem{example}{Example}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
%\newtheorem{remark}{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{axiom}[theorem]{Axiom}
% shamelessly copied from JMLR - END

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{observation}[theorem]{Observation}

%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{assumption}[theorem]{Assumption}

%ZZZ
%\environment{proof}[1][Proof:]{\begin{trivlist} \item[\hskip
%\labelsep {\bfseries #1}]}{\hfill{$\Box$}\end{trivlist}}
%\newenvironment{definition}[1][Definition:]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{example}[1][Example]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{remark}[1][Remark]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newcommand{\qed}{\nobreak \ifvmode \relax \else
%    \ifdim\lastskip<1.5em \hskip-\lastskip
%    \hskip1.5em plus0em minus0.5em \fi \nobreak
%    \vrule height0.75em width0.5em depth0.25em\fi}


\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\cnt}[3]{\ensuremath{{#1}(\cup{#2})(\cup({#2}\cap{#3}))}}
\newcommand{\bq}{\begin{quote}}
\newcommand{\eq}{\end{quote}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\vareps}{\varepsilon}
\newcommand{\veps}{\varepsilon}    \newcommand{\lam}{\lambda}
\newcommand{\sig}{\sigma}
\newcommand{\sub}{\mathrm{sub}}

\newcommand{\Red}{\color{red}}
\newcommand{\Blue}{\color{blue}}
\newcommand{\Green}{\color{green}}
\newcommand{\Black}{\color{black}}
\newcommand{\Magenta}{\color{Magenta}}
\newcommand{\Orange}{\color{Orange}}

\def\l({\left(}      \def\r){\right)}
\def\lc{\left\{}     \def\rc{\right\}}
\newcommand{\hR}{\hat{R}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cA}{{\cal A}}
\newcommand{\Real}{\mathbb{R}}
\newcommand{\rE}{\mathbf{E}}
\newcommand{\Var}{\mathbf{Var}}
\newcommand{\pig}{\tilde\pi_{\gamma/k}}
\newcommand{\al}{\alpha}
\newcommand{\hDelta}{\hat{\Delta}}
\newcommand{\hL}{\widehat{L}}
\newcommand{\eps}{\varepsilon}
\newcommand{\QED}{\hfill{$\Box$}}
%\newenvironment{proof}[1][Proof]{\textbf{#1} }{\ \rule{0.5em}{0.5em}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\HHH}{\mathcal{H}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\XXX}{\mathcal{X}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cZ}{\mathcal{Z}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\YYY}{\mathcal{Y}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\TTT}{\mathcal{T}}
\newcommand{\pmone}{\{ \pm 1 \}}
\newcommand{\ellhat}{\hat{\ell}}
\newcommand{\ppp}{\mathbf{p}}
\newcommand{\qqq}{\mathbf{q}}
\newcommand{\www}{\mathbf{w}}
\newcommand{\sgn}{\textrm{sgn}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\bI}{\mathbb{I}}

\newcommand{\mc}[1]{\ensuremath{\mathcal{{#1}}}}
\newcommand{\model}[3]{\ensuremath{{#1}=({#2},{#3})}}
\newcommand{\mon}[2]{\ensuremath{{#1}MON{#2}}}
\newcommand{\powerset}[1]{\ensuremath{\wp({#1})}}
\newcommand{\sih}[1]{\ensuremath{[ \! [ \mbox{#1} ] \! ]}}
\newcommand{\nlidb}{\textsc{Nlidb}}

\newcommand{\Err}{\ensuremath{\mbox{Err}}}
\newcommand{\X}{\ensuremath{\mathbf{X }}}
\newcommand{\gbar}{\overline{g}}
% remarks

%\newcommand{\todo}[1]{\textcolor{red}{\large{TODO: #1}}}
%\newcommand{\HERE}{\textcolor{green}{\large{HERE}}}

% these are the normal commands
%\newcommand{\ran}[2]{\textcolor{red}{#1} \textcolor{blue}{#2}}
%\newcommand{\ranissue}[1]{\marginpar{\textcolor{red}{\small{#1}}}}

\newcommand{\philip}[2]{\textcolor{red}{#1} \textcolor{green}{#2}}
%\newcommand{\pissue}[1]{\marginpar{\textcolor{cyan}{\small{#1}}}}
% \newcommand{\pnote}[1]{{~\emph{\Green [R: #1]\Black}}}

\newcommand{\rnote}[1]{{~\emph{\Blue  #1\Black}}}
\newcommand{\rmnote}[1]{{~\emph{\Orange #1\Black}}}
\newcommand{\ron}[2]{\textcolor{red}{#1} \textcolor{blue}{#2}}
%\newcommand{\radd}[2]{{\Red #1}{\Blue #2}}
%\newcommand{\rnew}[2]{{\Red #1}{\Green #2}}

% these are empty commands
\newcommand{\ran}[2]{}
\newcommand{\ranissue}[1]{}

%\newcommand{\philip}[2]{#2}
\newcommand{\pissue}[1]{}
\newcommand{\pnote}[1]{}

\newcommand{\rannote}[1]{{\Red Ran: #1}}
\newcommand{\radd}[2]{}
\newcommand{\rnew}[2]{}

% end of empty commands

% Making Margins narrower
%\newlength{\HorizontalMargin}
%\newlength{\TopMargin}
%\newlength{\FooterBuffer}
%\newlength{\BottomMargin}

%\HorizontalMargin 2cm %Space left on both sides of the paper.
%\TopMargin 1.5cm        %Space left empty on top of page
%\FooterBuffer 2cm     %Space left for footer (usually page number)
%\BottomMargin 2cm     %Space left below the footer.

%\textwidth \paperwidth \addtolength \textwidth
%{-\HorizontalMargin} \addtolength \textwidth {-\HorizontalMargin}
%\oddsidemargin \HorizontalMargin \addtolength \oddsidemargin
%{-1in} \evensidemargin \oddsidemargin

%\textheight \paperheight \addtolength \textheight {-\TopMargin}
%\addtolength \textheight {-\BottomMargin} \addtolength \textheight
%{-\FooterBuffer} \topmargin \TopMargin \addtolength \topmargin
%{-1in} \footskip \FooterBuffer

%\tableofcontents

%===================================================================
\begin{abstract}
Inductive learning is based on inferring a general rule from a
finite data set and using it to label new data. In
\emph{transduction} one attempts to solve the problem of using a
labeled training set to label a set of unlabeled points, which are
given to the learner prior to learning. Although transduction
seems at the outset to be an easier task than induction, there
have not been many \emph{provably useful} algorithms for
transduction. Moreover, the precise relation between induction and
transduction has not yet been determined. The main theoretical
developments related to transduction were presented by Vapnik more
than twenty years ago. One of Vapnik's basic results is a rather
tight error bound for transductive classification based on an
exact computation of the hypergeometric tail. While tight, this
bound is given \emph{implicitly} via a computational routine. Our
first contribution is a somewhat looser but \emph{explicit}
characterization of a slightly extended PAC-Bayesian version of
Vapnik's transductive bound. This characterization is obtained
using concentration inequalities for the tail of sums of random
variables obtained by sampling without replacement. We then derive
error bounds for compression schemes such as (transductive)
support vector machines and for transduction algorithms based on
clustering. The main observation used for deriving these new error
bounds and algorithms is that the unlabeled test points, which in
the transductive setting are known in advance, can be used in
order to construct useful \emph{data dependent} prior
distributions over the hypothesis space.
\end{abstract}

%===================================================================
\section{Introduction}\label{sec:intro}

The bulk of work in Statistical Learning Theory has dealt with the
\emph{inductive} approach to learning. Here one is given a finite
set of labeled  training examples, from which a rule is inferred.
This rule is then used to label new examples. As pointed out by
\citeA{Vap98} in many realistic situations one actually faces an
easier problem where one is given a training set of labeled
examples, together with an unlabeled set of points which needs to
be labeled. In this \emph{transductive} setting, one is not
interested in inferring a general rule, but rather only in
labeling this unlabeled set as accurately as possible. One
solution is of course to infer a rule as in the inductive setting,
and then use it to label the required points. However, as argued
by \citeA{Vap82,Vap98}, it makes little sense to solve what
appears to be an easier problem by `reducing' it to a more
difficult one. While there are currently no formal results stating
that transduction is indeed easier than induction\footnote{There
may be various ways to state this in a meaningful manner.
Essentially, we would like to know if for some learning problems a
particular transductive algorithm can achieve better performance
than any inductive algorithm, where performance may be
characterized by learning rates and/or computational complexity.}
it is plausible that the relevant information carried by the test
points can be incorporated into an algorithm, potentially leading
to superior performance. Since in many practical situations we are
interested in evaluating a function only at some points of
interest, a major open problem in statistical learning theory is
to determine precise relations between induction and transduction.

%Indeed, a number of papers have demonstrated empirically
%that transduction can offer substantial
%advantage over induction whenever the training set
%is small or moderate (see e.g.
%\cite{Joa99,blum01learning,El-Yaniv01}).
%However, unlike the current state of affairs in induction,
%the question of what are provably effective learning \emph{principles}
%for transduction is quite far from being resolved.

In this paper we present several general error bounds
for transductive learning.\footnote{In the paper we use
the terms `error bound' and `risk bound' interchangeably. Strictly speaking,
the term `generalization bound' is not appropriate in the transductive
setting.}
 We also present a general technique for
establishing error bounds for transductive learning algorithms
based on compression and clustering.
%The main contribution of this work is in the establishment of
%tight error bounds for the transductive setting.
Our bounds can be viewed as extensions of McAllester's
PAC-Bayesian framework \cite{McA99,McA03,McAllester03b} to
transductive learning. The main advantage of using the
PAC-Bayesian approach in transduction, as opposed to
induction, is that here prior beliefs on hypotheses can be formed
\emph{based on the unlabeled test data}. This flexibility allows
for the choice of ``compact priors'' (with small support) and
therefore, for tight bounds. We use the established bounds and
provide tight error bounds for ``compression schemes'' such as
(transductive) SVMs and transductive learning algorithms based on
clustering. While precise relations between induction and
transduction remain a major challenge, our new bounds and
technique offer some new insights into transductive learning.

The problem of transduction was formulated as long ago as 1982 in
Vapnik's classic book \cite{Vap82}, where the precise setting was
formulated, and some implicit error bounds were
derived.\footnote{Vapnik refers to transduction also as
``estimating the values of a function at given points of
interest''.} In recent years the problem has been receiving an
increasing amount of attention, due to its applicability to many
real world situations. A non-exhaustive list of recent
contributions includes
\cite{Vap82,Vap98,Joa99,BenDem98,Demiriz00,BenCriSha99,LanCriGhaBarJor02},
and \cite{BlumL03}. Most of this work, with the exception of
Vapnik's bounds \citeyear{Vap82,Vap98} and the results
of Lanckriet et al. \citeyear{LanCriGhaBarJor02}, has dealt with
algorithmic issues, rather than with performance bounds. Implicit
performance bound, in the spirit of \citeA{Vap82,Vap98} has
recently been presented by \citeA{BlumL03}. We mention this result
again later in Section~\ref{sec:Vapnik_implicit}.

We present \emph{explicit} PAC-Bayesian bounds for a transductive
setting that considers sampling \emph{without replacement} of the
training set from a given `full sample' of unlabeled points. This
setting is proposed by Vapnik and it turns out that error bounds
for learning algorithms, within this setting, imply the same
bounds within another setting which may appear more practical (See
Section~\ref{sec:setup} and Theorem~\ref{thm:vapnik_1_2} for
details). Sampling without replacement of the training set leads
to the training points being \emph{dependent} (see
Section~\ref{sec:setup} for details). Our first goal is to provide
uniform bounds on the deviation between the training error and the
test error. To this end, we study two types of bounds that utilize
two different bounding techniques. The first approach is based on
an observation made in Hoeffding's classic paper \cite{Hoe63}.
This approach was recently alluded to by \citeA{Lug03}. As
pointed out by \citeA{Hoe63}, the sampling without replacement
problem can be reduced to an equivalent problem involving
independent samples, for which standard techniques suffice. We
refer to this approach as `reduction to independence'. A second
approach involves derivations of large deviation bounds for
sampling \emph{without replacement} such as those developed by
\citeA{Serfling74}, \citeA{Vap98}, \citeA{HushS03}, and
\citeA{DemZei98}. We refer to such bounds as `direct'. We consider
these two approaches in Section \ref{sec:reduction} and
\ref{sec:direct}, respectively. Using these two approaches we
derive general PAC-Bayesian bounds for transduction. It turns out
that the direct bounds lead to tighter and more explicit learning
curves for transduction.

We then show how to utilize PAC-Bayesian transductive bounds to
derive error bounds for specific learning schemes. In particular,
we show how to choose priors, based on the given unlabeled data,
and derive bounds for ``compression schemes'' and learning
algorithms based on clustering. Compression schemes are algorithms
that select the same hypothesis using only a subset of the
training data. The main example of a compression scheme is a
(transductive) Support Vector Machine (SVM). The
compression level achieved by such schemes typically depends on
the (geometric) complexity of the learning problem at hand, which
sometimes does not allow for significant compression. A stronger
type of compression can be often achieved using clustering. A
natural approach in the context of transduction (and
semi-supervised learning) is to apply a clustering algorithm over
the set of all available (unlabeled) points and then to use the
labeled points to determine the classifications of points in the
resulting clusters. We formulate this scheme in the context of
transduction and derive for it rather tight error
bounds by utilizing an appropriate prior in our transductive
PAC-Bayesian bounds. For practical applications a similar but
tighter result is obtained by using the implicit bounds of
\citeA{Vap98} (or the bound of \citeR{BlumL03}).


%A particularly nice feature of using
%data-dependent priors is that arbitrarily complex
%hypothesis spaces may always be
%reduced to finite sets (see Section \ref{sec:multiple_priors}).
%We apply this new technique to derive tight bounds for
%(transductive) SVMs, for
%an ensemble of kernel machines and to derive a new transductive
%learning scheme based on clustering.

%===================================================================
\section{Problem Setup and Vapnik's Basic Results}\label{sec:definitions}

\subsection{Problem Setup}\label{sec:setup}

The problem of transduction can be informally described as
follows. A learner is given a set of labeled examples
$\{(x_1,y_1),\ldots,(x_m,y_m)\}$,
$x_i \in \cX$, $y_i \in \cY$,
and a set of unlabeled points
$\{x_{m+1},\ldots,x_{m+u}\}$. Based on this data, the objective is
to label the unlabeled points. In order to formalize the scenario, we
 consider the setting proposed by \citeA[Chap. 8]{Vap98}, which
for simplicity is described in the context of
binary classification.\footnote{Note that the bound of
Theorem~\ref{thm:serfling_sqrt} does hold for general bounded loss functions.}
Let $\cH$
be a set of binary hypotheses consisting of functions from the input
space $\cX$ to $\YYY = \pmone$. Let $\mu(x,y)$ be any
distribution over $\cX \times \cY$. For each $h \in \cH$ and a set $Z =
x_1, \ldots, x_{|Z|}$ of samples define
\begin{equation}
\label{eq:risk_def}
R_h(Z) \eqdef \frac{1}{|Z|} \sum_{i=1}^{|Z|} \rE_{\mu(y|x_i)} \left\{\ell(h(x_i),y) \right\}
 = \frac{1}{|Z|} \sum_{i=1}^{|Z|} \int_{y \in \YYY} \ell(h(x_i),y) d\mu(y|x_i),
\end{equation}
where, unless otherwise specified, $\ell(\cdot,\cdot)$ is the 0/1
loss function. \citeA{Vap98} considers the following two
transductive ``protocols''.

\newpage
\noindent
\textbf{\emph{Setting 1}}:
\begin{itemize}
\item[(i)]
A full sample $X_{m+u} = \{x_1,\ldots,x_{m+u}\}$
consisting of arbitrary
 $m+u$ points is given.\footnote{The original Setting 1, as proposed
 by Vapnik, discusses a full sample whose points are
chosen independently at
random according to some source distribution $\mu(x)$.}
\item[(ii)]
We then choose uniformly at random the training
sample $X_m \subseteq X_{m+u}$ and receive its labels $Y_m$ where
the label $y$ of $x$ is chosen according to $\mu(y|x)$; the
resulting training set is $S_m = (X_m, Y_m)$ and the remaining set
$X_{u}$ is the  \emph{unlabeled (test) sample},
$X_u = X_{m+u} \setminus
X_m$.
\item[(iii)]
Using both $S_m$ and $X_u$ we select a classifier $h \in \cH$.
The quality of $h$ is measured by $R_h(X_u)$.
\end{itemize}

\noindent
\textbf{\emph{Setting 2}}:
\begin{itemize}
\item[(i)] We are given a
training set $S_m = (X_m, Y_m)$ selected i.i.d according to
$\mu(x,y)$.
\item[(ii)]
An independent  test set $S_u = (X_u, Y_u)$ of $u$ samples is then
selected in the same manner.
\item[(iii)]
We are required to choose our best $h\in \cH$ based
on $S_m$ and $X_u$ so as to minimize
\begin{equation}
\label{eq:second_setting_risk}
R_{m,u}(h) \eqdef \int \frac{1}{u} \sum_{i=m+1}^{m+u} \ell\left(h(x_i),y_i\right)
d\mu(x_1,y_1)\cdots d\mu(x_{m+u},y_{m+u}).
\end{equation}
\end{itemize}

\begin{remark}
\label{rem:dependent}
Notice that the choice of the sub-sample $X_m$ in Setting 1
is equivalent
to sampling $m$ points from $X_{m+u}$ uniformly at random
\emph{without replacement}. This leads to the samples being
\emph{dependent}.
Also, Setting 1 concerns an ``individual sample''
$X_{m+u}$ and there are no
assumptions regarding its underlying source. The only element
of chance in this setting is the
random choice of the training set from the full sample.
\end{remark}


Setting 2 may appear more applicable in some practical situations
than Setting 1. However, derivation of theoretical results can be
easier within Setting 1. The following useful theorem
(\citeR<Theorem 8.1 in>{Vap98}) relates the two transduction settings. For
completeness we present Vapnik's proof in the appendix.



\begin{theorem}[Vapnik]\label{thm:vapnik_two_models}
\label{thm:vapnik_1_2}
If for some learning algorithm choosing an hypothesis $h$
it is proved within Setting 1 that with
probability at least $1-\delta$, the deviation between the risks
$R_h(X_m)$ and $R_h(X_u)$ does not depend on the composition of the
full sample and does not exceed $\veps$, then with the same
probability, in Setting 2 the deviation between $R_h(X_m)$ and the
risk given by formula (\ref{eq:second_setting_risk}) does not exceed $\veps$.
\end{theorem}

\begin{remark}
The learning algorithm in Theorem~\ref{thm:vapnik_1_2} is implicitly
assumed to be deterministic. The theorem can be extended straightforwardly to the
case where the algorithm is randomized and chooses an hypothesis
$h \in \cH$ randomly, based on $S_m \cup X_u$.
A particular type of randomization is the one used by Gibbs
algorithms, as discussed in Section~\ref{sec:PAC-Bayes-Gibbs}.
\end{remark}

\begin{remark} \label{rem:setting2} The basic quantity of
interest in Setting 2 is $R_{m,u}(h)$ defined in
(\ref{eq:second_setting_risk}). Assuming $h$ is selected based on
the sample $S_m\cup X_u$, one is often interested in its expectation
over a random selection of this sample. In inductive learning, one
considers the sample $S_m$ and a single new point $(x,y)$, and the
average is taken with respect to $S_m \cup\{X\}$. It should be noted
that the random variable $R_{m,u}(h)$ is `more concentrated' around
its mean than the random variable $\ell(h(x),y)$ corresponding to a
single new point $(x,y)$.
Therefore, one may expect transduction to lead to tighter bounds in Setting
2 as well.
\end{remark}




In view of Theorem~\ref{thm:vapnik_two_models} we restrict ourselves
in the sequel to Setting 1. Also, for simplicity we focus on the
case where there exists a \emph{deterministic} target function
$\phi: \cX \to \cY$, so that $y = \phi(x)$ is a fixed target label
for $x$; that is, $\mu(\phi(x)|x)=1$ (there is no requirement that
$\phi \in \cH$). Note that it is possible to extend our results to the
the general case of stochastic targets $y \sim \mu(y|x)$.

We make use of the following quantities, which are all instances of
(\ref{eq:risk_def}). The quantity $R_h(X_{m+u})$ is called the
\emph{full sample risk} of the hypothesis $h$, $R_h(X_u)$ is
referred to as the \emph{transduction risk} (of $h$), and $R_h(X_m)$
is the \emph{training error} (of $h$). Note that in the case where
our target function $\phi$ is deterministic,
$$
R_h(X_m) = \frac{1}{m} \sum_{i=1}^{m}
\rE_{\mu(y|x_i)} \left\{\ell(h(x_i),y) \right\}
 = \frac{1}{m} \sum_{i=1}^{m} \ell(h(x_i),\phi(x_i)).
$$
Thus, $R_h(X_m)$ is the standard training error denoted
interchangeably by $\hR_h(S_m)$. It is important to observe
that while $R_h(X_{m+u})$ is \emph{not} a random variable, both
$R_h(X_m)$ and $R_h(X_u)$ are random variables, due to the random
selection of the samples $X_m$ from $X_{m+u}$.

While our objective in transduction is to achieve small error over
the unlabeled  sample (i.e. to  minimize $R_h(X_u)$),
we find that it is sometimes easier to derive error bounds for the full sample
risk. The following simple lemma translates an error bound on
$R_h(X_{m+u})$, the full sample risk, to an error bound on the
transduction risk $R_h(X_u)$.

\begin{lemma}\label{lem:trans_reduction}
For any $h \in \cH$ and any $C$
\begin{equation}
\label{eq:lemma_trans_equivalence} R_h(X_{m+u}) \le \hR_h(S_m) +
C \ \ \ \Leftrightarrow \ \ \
 R_h(X_{u}) \le \hR_h(S_m) +
\frac{m+u}{u}\cdot C.
\end{equation}
\end{lemma}

\begin{proof}
For any $h$
\begin{equation}\label{full_risk}
R_h(X_{m+u}) = \frac{m R_h(X_{m}) + uR_h(X_u)}{m+u}.
\end{equation}
Substituting $\hR_h(S_m)$ for $R_h(X_{m})$ in (\ref{full_risk}) and
then substituting the result for the left-hand side of
(\ref{eq:lemma_trans_equivalence}) we get
$$
   R_h(X_{m+u}) = \frac{m \hR_h(S_{m}) + uR_h(X_u)}{m+u} \le \hR_h(S_m) +
C.
$$
The equivalence (\ref{eq:lemma_trans_equivalence}) is now obtained
by isolating $R_h(X_u)$ on the left-hand side.
\end{proof}

\begin{remark}
In applications of Lemma~\ref{lem:trans_reduction}, the
 term $C=C(m)$ is typically a function $m$ (and of
some of the other problem parameters such as $\delta$). In
meaningful bounds $C(m) \to 0$ with $m\rightarrow\infty$. Observe
that in order for the bound on $R_h(X_u)$ to converge it must be
that $u = \omega(m C(m))$.
% suppose that $u=f(m)$. Then we need that
%$$
%\frac{m+f(m)}{f(m)} C(m) = \frac{m C(m)}{f(m)} + C(m),
%$$
%will converge.
%
%lead to rates
%of convergence which are not much worse than those of $R_h(X_{m+u})$ one
%needs that $u=\Omega(m)$, i.e. the unlabeled  sample should be
%sufficiently large.
\end{remark}

Consider a hypothesis class $\cH$. In the context of transduction,
we are only interested in labeling the test set $X_u$, which is
given in advance. Thus, we may in principle regard hypotheses in
$\cH$ which label $X_{m+u}$ identically as belonging to the same
equivalence class. Since for fixed values of $m$ and $u$ the number
of equivalence classes is finite (in the case of binary hypotheses,
it is at most $2^{m+u}$) we may, without loss of generality,
restrict ourselves to a finite hypothesis class
\cite<see, for example>[Sec. 8.5]{Vap98}. Note that this freedom is \emph{not}
available in the inductive setting, where the test set is not known
in advance.

\begin{remark}
\label{rem:real-valued}
 The above procedure is clearly not possible in the case of
real-valued loss functions. However, in this case one can still
use the availability of the full data set $X_{m+u}$ in order to
construct an empirical $\epsilon$-cover of $\cH$ based on the
empirical $\ell_1$ norm, namely $\ell_1(f,g)=(m+u)^{-1}
\sum_{i=1}^{m+u} |f(x_i)-g(x_i)|$ for any $f,g\in\cH$. We
restrict ourselves here to the binary case here.
\end{remark}

\subsection{Vapnik's Implicit Bounds}
\label{sec:Vapnik_implicit}

% Thus, in the sequel we
%restrict ourselves to countable hypotheses classes (since we do not
%wish to restrict the size of this set in advance).\footnote{In fact, our results
%in Sections~\ref{sec:compression} and~\ref{sec:clustering} only require that
%Theorems~\ref{thm:mcallester_trans_easy},
%\ref{thm:realizable_not_realizable} and~\ref{thm:McAllesterDKL} hold
%for finite hypothesis classes.} Recall that in Setting 1 we select a
%sub-sample of $m$ points from the set $X_{m+u}$ of cardinality
%$m+u$. This corresponds to a selection of $m$ points \emph{without}
%replacement from a set of $m+u$ points, leading to the $m$ selected
%points being \emph{dependent}.
%A naive utilization of large
%deviation bounds (say, for bounding binomial distributions)
%would therefore not be directly applicable in this
%setting. However, the following result by \cite{Hoe63} is very
%useful in the present context.\footnote{The resulting
%distribution when we sample without replacements is
%hypergeometric. There are a few large deviations bounds
%for hypergeometric distributions which could be used
%instead; see e.g. \citep{Chvatal79}.}
%%{\Blue While a proof of this result
%%appears in \cite[]{Hoe63}, the proof is rather terse. For
%%completeness we have included a full proof in the appendix.}



Fix some hypothesis $h\in \cH$ and suppose that $h$ makes $k_h$
errors on the full sample (i.e. $k_h = (m+u)R_h(X_{m+u})$). Consider
a random choice of the training set $S_m$ from the full sample, and
let $B(r,k_h,m,u)$ be the probability that $h$ makes exactly $r$
errors over the training set $S_m$. This probability is by definition the
hypergeometric distribution, given by
$$
B(r,k_h,m,u) \eqdef \frac{
{k_h\choose{r}} {{m+u-k_h}\choose{m-r}}
}{{{m+u}\choose{m}}}.
$$
Since $m$ and $u$ are fixed,
throughout this discussion we abbreviate $B(r,k_h) \eqdef
B(r,k_h,m,u)$.
Define
\begin{align*}
C(\veps,k_h) &\eqdef \Pr \left\{ R_h(X_u) - R_h(X_m) > \veps  \right\}\\
&=
\Pr \left\{\frac{k_h-r}{u}  - \frac{r}{m}  > \veps  \right\}\\
&= \sum_r B(r,k_h),
\end{align*}
where the summation is over all values of $r$ such that
$\max\{k_h-u,0\} \leq r \leq \min \{m,k_h\}$ and
\begin{equation}
\label{eq:vapnik_condition} \frac{k_h -r}{u} -
\frac{r}{m} > \veps.
\end{equation}
Define
\begin{equation}
\label{eq:Gamma_def}
\Gamma(\veps)  \eqdef \max_k C\left(\sqrt{\frac{k}{m+u}} \cdot
\veps,k\right).
\end{equation}
%Clearly,
%$$
%R_h(X_{m+u}) = \frac{m}{m+u} R_h(X_m) + \frac{u}{m+u} R_h(X_u).
%$$
We now state Vapnik's implicit bound for transduction. The bound
is slightly adapted to incorporate a prior probability over $\cH$
(the original bound deals with a uniform prior).
Also, the original bound is two-sided and the
following theorem is one-sided.\footnote{Specifically,
in the original bound \cite{Vap82} the two-sided condition
$| \frac{k_h -r}{u} - \frac{r}{m} | > \veps$ is used instead of
condition (\ref{eq:vapnik_condition}).}

\begin{theorem}[Vapnik 1982]
\label{thm:vapnik_relative} Let $\delta$ be given, let $\ppp$ be a
prior distribution over $\cH$, and let $\veps^*(h)$ be the minimal
value of $\veps$ that satisfies $\Gamma(\veps) \leq \ppp(h) \delta$.
Then, with probability at least $1-\delta$, for all $h \in \cH$,
\begin{equation}
\label{eq:vapnik_rel} \frac{R_h(X_u) -
R_h(X_m)}{\sqrt{R_h(X_{m+u})}} < \veps^*(h).
\end{equation}
\end{theorem}

\begin{proof}
Using the union bound we have,
\begin{align}
Q &= \Pr \left\{ \exists h \in \cH \ :
        \frac{R_h(X_u) - R_h(X_m)}{\sqrt{R_h(X_{m+u})}} > \veps^*(h)
    \right\} \nonumber \\
&= \Pr \left\{ \exists h \in \cH \ :
        R_h(X_u) - R_h(X_m) > \sqrt{R_h(X_{m+u})}\veps^*(h)
    \right\} \nonumber \\
&= \Pr \left\{ \exists h \in \cH \ :
        R_h(X_u) - R_h(X_m) > \sqrt{\frac{k_h}{m+u}}\veps^*(h)
    \right\} \nonumber \\
&\leq \sum_{h \in \cH}
C\left(\sqrt{\frac{k_h}{m+u}} \veps^*(h),k_h\right)  \label{eq:vap_union} \\
&\leq \sum_{h \in \cH}
\Gamma(\veps^*(h))  \nonumber \\
&\leq \sum_{h \in \cH} \ppp(h) \delta = \delta. \nonumber
\end{align}
Note: The convention $\frac{R_h(X_u) -
R_h(X_m)}{\sqrt{R_h(X_{m+u})}} = 0$ is used whenever $R_h(X_u) = R_h(X_m)
= R_h(X_{m+u}) = 0$.
\end{proof}
It is not hard to convert the bound (\ref{eq:vapnik_rel}) to the
``standard'' form (i.e. expressed as empirical error plus some
complexity term). Squaring both sides of (\ref{eq:vapnik_rel}) and
then substituting $\frac{m}{m+u} R_h(X_m) + \frac{u}{m+u}
R_h(X_u)$ for $R_h(X_{m+u})$ we get a quadratic inequality where
the ``unknown'' variable is $R_h(X_u)$. Solving for $R_h(X_u)$
yields the following result \cite<as in>[Equation~(8.15)]{Vap98}.

\begin{corollary}
\label{cor:vapnik_relative} Under the conditions of
Theorem~\ref{thm:vapnik_relative},
$$
R_h(X_u) \leq R_h(X_m) + \frac{\veps^*(h)^2 u}{2(m+u)} +
\veps^*(h)\sqrt{R_h(X_m) + \left(\frac{\veps^*(h)
u}{2(m+u)}\right)^2}.
$$
\end{corollary}

\begin{remark}
Theorem~\ref{thm:vapnik_relative} focuses on the relative
deviation of the divergence $R_h(X_u) - R_h(X_m)$, and
generates a bound that is particularly tight in cases
where the empirical error $R_h(X_m)$ is very small.
A very similar but
simpler version of Vapnik's bound concerns the
``absolute'' deviation is tighter in other cases of interest.
The absolute bound is obtained as follows.
Define, instead of~(\ref{eq:Gamma_def}),
$$
\Gamma(\veps)  \eqdef \max_k C\left(\veps,k\right),
$$
and let $\veps^*(h)$ be the minimal
value of $\veps$ that satisfies $\Gamma(\veps) \leq \ppp(h) \delta$, for any given
$\delta$.
Then, the absolute bound states that with confidence at least $1-\delta$,
\begin{equation}
\label{eq:vapnik_absolute}
R_h(X_u)  < R_h(X_m) + \veps^*(h).
\end{equation}
This result is presented by \citeA{BottouCV94}.
\end{remark}



\begin{remark}
The bound of Corollary~\ref{cor:vapnik_relative}, and the bound
(\ref{eq:vapnik_absolute}), are rather tight. Possible sources of
slackness are only introduced through the utilization of the union
bound in (\ref{eq:vap_union}) and the definition of $\Gamma$ in
(\ref{eq:Gamma_def}). However, note that $\veps^*(h)$ is a
complicated implicit function of $m$, $u$, $\ppp(h)$ and $\delta$
leading to a bound that is difficult to interpret and (as noted
also by Vapnik) must be tabulated by a computer in order to be
used.
\end{remark}

Note that a related result has recently been presented by
\citeA{BlumL03}. Specifically, Theorem 6 in that paper states a
similar implicit bound, based on direct calculation of the
hypergeometric tail. However, Vapnik's bound was originally proved
for a uniform prior over the hypothesis class, and the extension
to general priors was first proposed by
\citeA{BlumL03}.\footnote{Also, the bound of \citeA{BlumL03} may
be tighter than the Vapnik's bounds in some
cases of interest. A careful numerical comparison should be
conducted to determine the relative advantage of each of these
bounds.}


%=======================================================================
\section{Concentration Inequalities for Sampling without Replacement}
\label{sec:pac-bayesian results} \label{sec:sampling}

In this section we present several concentration inequalities that
will be used in Section~\ref{sec:pac-bayes-trans} to develop
PAC-Bayesian bounds for transduction. As discussed in Section
\ref{sec:definitions} (see Remark~\ref{rem:dependent}), sampling
without replacement leads to dependent data, precluding direct
application of standard large deviation bounds devised for
independent samples. Here we present several
concentration inequalities for sampling without
replacement.


\subsection{Inequalities Based on Reduction to Independence}
\label{sec:reduction}

%Consider an urn containing $N$ balls among which there are $\ell$
%``large'' balls (and the other $N-\ell$ balls are small).
%We randomly draw $m \leq N$ balls without replacement.
%Let $X$ be a random variable giving the number of large
%balls among the $m$ sampled balls. Clearly,
%\begin{equation}
%\label{eq:hypergeometric}
%\Pr \left\{ X = k \right\} =
%\frac{ {{\ell}\choose{k}} \cdot {{N-\ell}\choose {m-k}}}{{N\choose{m}}}.
%\end{equation}
%This distribution precisely models the transduction game.
%Consider a transductive classification problem (i.e. the 0-1 loss function)
%and suppose we have some hypothesis $h$ that makes $\ell$ errors on the
%full sample ($X_{m+u}$). Taking $N=m+u$ and letting $\ell$
%be the number of errors $h$ makes on the full sample
%we see that the probability that $h$ makes $k$
%errors over a randomly chosen training set of size $m$ is given by
%(\ref{eq:hypergeometric}).
%
%
%Explicit error bounds for transduction can be devised using large deviation bounds
%for the hypergeometric distribution.
%Perhaps the first such bound is the following theorem by \citep{Hoe63}

Even though sampling without replacement leads to dependent samples,
\citeA{Hoe63} pointed out a simple procedure to transform the problem
into one involving independent data. While this procedure leads to
non-trivial bounds it
involves some loss in tightness (see Section~\ref{sec:direct}).

\begin{lemma}[Hoeffding 1963]
\label{lem:hoeffding} Let $\cC= \{c_1,\ldots,c_N\}$ be a finite set
with $N$ elements, let $\{X_1,\ldots,X_m\}$ be chosen uniformly at
random \textbf{with replacement} from $\cC$, and let
$\{Z_1,\ldots,Z_m\}$ be chosen uniformly at random \textbf{without
replacement} from $\cC$.\footnote{Note that the variables
$\{X_1,\ldots,X_m\}$ are \emph{independent}, while
$\{Z_1,\ldots,Z_m\}$ are \emph{dependent}.} Then, for any continuous
and convex real-valued function $f(x)$, $ \rE f\left( \sum_{i=1}^m
Z_i \right) \leq \rE f\left( \sum_{i=1}^m X_i \right).$
\end{lemma}
Lemma~\ref{lem:hoeffding} can be used in order to generate
standard exponential bounds, as proposed by \citeA{Hoe63}. We first
introduce some notation which will be used in the sequel. Let
$\nu$ and $\mu$ be two real numbers in $[0,1]$. We
use the following definitions for the binary entropy and binary
KL-divergence, respectively.
\begin{align*}
  H(\nu) &\eqdef -\nu\log\nu - (1-\nu)\log(1-\nu), \\
  D(\nu \| \mu) &\eqdef \nu\log\frac{\nu}{\mu} +
  (1-\nu)\log\frac{1-\nu}{1-\mu}.
\end{align*}

\begin{theorem}[Hoeffding, 1963]
\label{thm:hoeffding} Let ${\cal C} = \{c_1,\ldots,c_N\}$ be a
finite set of non-negative bounded real numbers, $c_i \leq B$, and
set $\bar c = (1/m)\sum_{i=1}^m c_i$. Let $Z_1,\ldots,Z_m$, be
random variables obtaining their values by sampling ${\cal C}$
uniformly at random \textbf{without} replacement. Set $Z =
(1/m)\sum_{i=1}^m Z_i$. Then, for any $\veps \leq  1 - {\bar c}/B$,
\begin{align}
  \Pr \{ Z - \rE Z \geq \eps \}
  &\le \exp\lc -mD\l(\frac{\bar c}{B} +
  \eps\left\| \frac{\bar c}{B}\right.\r)\rc   \label{eq:Hoeffding_DKL}\\
  &\le \exp\lc -\frac{2m\eps^2}{B^2}\rc \label{eq:Hoeffding}
\end{align}
%Setting
%$\sig^2 = (1/N)\sum_{i=1}^N (c_i-\bar c)^2$, where $\bar
%c=(1/N)\sum_{i=1}^N c_i$, we also have
%\begin{equation}\label{eq:Bernstein}
%  \Pr \{ Z - \rE Z \geq \eps \} \le
%    \exp \left( -\frac{m\eps^2}{2\sig^2 + 2B\eps/3}\right)~.
%\end{equation}
Similar bounds hold for $\Pr \{ \rE Z - Z \geq \eps \}$.
\end{theorem}
The key to the
proof Theorem~\ref{thm:hoeffding} is the application
of Lemma \ref{lem:hoeffding} with $f(\sum_i
Z_i)=\exp\{\sum_i (Z_i-\rE Z_i)\}$ and the utilization of the
Chernoff-Hoeffding bounding technique \cite<see>[for the details]{Hoe63}.


%As shown in \citep{Hoe63} \citep[and also recently discussed
%in][]{Lug03}, Theorem~\ref{thm:hoeffding} can be easily established
%using a standard Chernoff-Hoeffding tail bound for the
%\emph{binomial} distribution \citep{Hoe63} and the following lemma
%that can translate bounds for i.i.d. sampling to bounds on sampling
%without replacement as done in the hypergeometric
%distribution.\footnote{A direct (and substantially simpler)
%derivation of Theorem~\ref{thm:hoeffding} can be found in
%\citep{Chvatal79}.}

%Let $\bar X =
%(1/m)\sum_{i=1}^m X_i$ and $\bar Z = (1/m)\sum_{i=1}^m Z_i$, and set
%\begin{equation*}
%  \mu = \frac{1}{N} \sum_{i=1}^N c_i \qquad ; \qquad
%  \sig^2 = \frac{1}{N} \sum_{i=1}^N (c_i-\mu)^2 .
%\end{equation*}
%Then from \cite[]{Hoe63} we have that
%\begin{align*}
%  \rE[\bar X]  &= \rE[\bar Z] = \mu  \\
%  \Var[\bar Z] &=  \frac{\sig^2}{n}\\
%  \Var[\bar X] &= \l(\frac{N-m}{N-1}\r) \frac{\sig^2}{n} .
%\end{align*}

%Theorem~\ref{thm:hoeffding} can be used to prove the following
%theorem, which is analogous to McAllester's Theorem~1 in
%\citep{McA99} for the case of Induction. {\Blue We present the
%theorem without proof, as the proof is identical to the one used for
%induction, and follows many of the lines of proof in Section
%\ref{sec:direct} below.}

%\rmnote{We probably don't need this theorem here, as it will follow
%from the Gibbs Theorem}
%\begin{theorem}
%\label{thm:sqrt1} Let $X_{m+u} = X_m \cup X_u$ be the full sample
%and let $\ppp = \ppp(X_{m+u})$ be a (prior) distribution over $\cH$
%that may depend on the full sample. {\Blue Assume further that
%$\ell(h(x),y) \in [0,B]$} and let $\delta \in (0,1)$ be given. Then,
%with probability at least $1-\delta$ over choices of $S_m$ (from the
%full sample) the following bound holds for any $h \in \cH$,
%\begin{equation}\label{eq:pac_sqrt}
%R_h(X_{u}) \leq \hR_h(S_m) + \left(\frac{m+u}{m}\right)
%  \sqrt{\frac{B\ln\frac{1}{\delta
%  p(h)}}{2m}}~.
%\end{equation}
%Alternatively, using the Bernstein
%inequality we have
%\begin{equation}
% R_h(X_{u}) \leq \hR_h(S_m) + \left(\frac{m+u}{m}\right)
%   \sqrt{\frac{2B\hR_h(S_m) \ln\frac{1}{\delta p(h)}}{m}}
%   + \frac{3B\ln\frac{1}{\delta p(h)}}{m}
%\label{eq:pac_interp}
%\end{equation}
%\end{theorem}
%Note that this bound is effective only when $\frac{m+u}{m} = o(\sqrt{m})$.
%Otherwise the complexity term does not vanish with $m$.
%In other words, the bound is effective as long as $u = \omega(\sqrt{m})$.
%The bound in (\ref{eq:pac_interp}) improves on (\ref{eq:pac_sqrt})
%when the empirical error term $\hR_h(S_m)$ is small.

\subsection{Sampling Without Replacement - Direct Inequalities}
\label{sec:direct} In this section we consider approaches which
directly establish exponential bounds for sampling without
replacement. As opposed to Vapnik's results \citeyear{Vap82,Vap98}, which
provide tight but implicit bounds, we aim at bounds which depend
\emph{explicitly} on all parameters of interest. Note that the
bound of Theorem~\ref{thm:hoeffding} does not depend on all the
parameters (in particular, the population size $N$ does not appear
and clearly, small population size should affect the convergence
rate). One may expect that bounds developed directly for sampling
without replacement should be tighter than those based on
reduction to independence. The reason for this is as follows.
Assume, we have sampled $k$ out of $N$ points without replacement.
The next point is to be sampled from a set of $N-k$ rather than
$N$ points, which would be the case in sampling with replacement
(where the samples are independent). The successive reduction in
the size of the sampled set reduces the `randomness' of the newly
sampled point as compared to the independent case. This intuition
is at the heart of Serfling's improved bound \cite{Serfling74},
which is stated
next. This result holds for general bounded loss functions and is
established by a careful utilization of martingale techniques
combined with Chernoff's bounding method.

\begin{theorem}{\bf\cite{Serfling74}}
\label{thm:serfling} Let ${\cal C} = \{c_1,\ldots,c_{N}\}$ be a
finite set of bounded real numbers, $|c_i| \leq B$. Let
$Z_1,\ldots,Z_m$, be random variables obtaining their values by
sampling ${\cal C}$ uniformly at random \textbf{without}
replacement. Set $Z = \frac{1}{m} \sum_{i=1}^m Z_i$. Then,
\begin{equation}\label{eq:Serfling}
\Pr \{ Z - \rE Z \geq \eps \} \le \exp \left\{
-\left(\frac{2m\eps^2}{B^2}\right)\left(\frac{N}{N-m+1}\right)
\right\} ~,
\end{equation}
and similarly for $\Pr \{ \rE Z_m - Z_m \geq \eps \}$.
\end{theorem}
Compared to the bound of Theorem~\ref{thm:hoeffding}, the bound in
(\ref{eq:Serfling}) is always tighter than Hoeffding's second bound
(\ref{eq:Hoeffding}) when $N/(N-m+1)>1$ (i.e. when $m > 1$). When
applied to our transduction setup (see
Section~\ref{sec:PAC-Bayes-Gibbs}) we take $N= m+u$ and the
advantage is maximized when $(m+u)/(u+1)$ is maximized. Thus,
considering only the convergence rate obtained by sampling without replacement,
one may expect that
the fastest rates should be obtained when $u$ assumes the smallest
possible value (e.g. $u =1$) and not surprisingly, the advantage
over the bound of Theorem~\ref{thm:hoeffding} vanishes as $u \to
\infty$.

In the case where the $c_i$ are binary variables, the bound in
Theorem \ref{thm:serfling} can be improved, by using a proof based
on a counting argument. The following theorem and proof is based on
a simple consequence of Lemma 2.1.33 by \citeA{DemZei98}.

\begin{theorem}\label{thm:DemZei}
Let ${\cal C} = \{c_1,\ldots,c_N\}$, $c_i \in \{0,1\}$, be a finite
set of binary numbers, and set ${\bar c} = (1/N)\sum_{i=1}^N c_i$.
Let $Z_1,\ldots,Z_m$, be random
variables obtaining their values by sampling ${\cal C}$ uniformly at
random \textbf{without} replacement. Set $Z = (1/m)\sum_{i=1}^m Z_i$
and $\beta=m/N$. Then, if \footnote{The second condition,
$\veps \leq {\bar c}(1-\beta)/\beta$,
simply guarantees that the number of `ones' in the sub-sample does
not exceed their number in the original sample.}
$\veps \leq \min\{1- \bar c,  {\bar c}(1-\beta)/\beta \}$,
\begin{equation*}
  \Pr\lc Z - \rE Z > \veps \rc \le \exp\lc-m D(\bar c + \veps \| \bar c) -
  (N-m) \left. D\l(\bar c - \frac{\beta \veps}{1-\beta} \right \| \bar c \r) +
  7\log(N+1)\rc ~.
\end{equation*}
%Note that the condition on $\veps$
%implies
%$0 \leq \bar c - \beta \veps/ (1-\beta) \leq 1$.
\end{theorem}
%
\begin{proof}
Denote by $N_0$ and $N_1$ the number of appearances
in ${\cal C}$ of $c_i=0$ and $c_i=1$, respectively. Let $m_0$ and
$m_1$ be integers $0 \le m_0,m_1 \le m$, such that $m_0+m_1=m$. The
probability of observing $m_1$ appearances of `1' (and thus $m_0$
appearances of `0' ) in a random sub-sample selected without
replacement is the number of $m$-tuples resulting in $m_0(m_1)$
appearances of $0(1)$ in the subsample, divided by the overall
number of $m$-tuples,
\begin{equation*}
    \Pr\lc \sum_{i=1} Z_i = m_1 \rc =
    \frac{{{N_1}\choose{m_1}}{{N_0}\choose{m_0}}}{{{N}\choose{m}}}~.
\end{equation*}
Setting $\mu = \bar c$, the probability that $Z=(1/m)\sum_{i=1}^m
Z_i$ is greater than $\nu \eqdef \mu + \veps = m_1/m$ (for some
natural number $m_1$)
 is then given by
\begin{equation*}
    \Pr\lc \frac{1}{m}\sum_{i=1} Z_i > \nu \rc = \sum_{m_1=\lceil m\nu\rceil}^m
    \frac{{{N_1}\choose{m_1}}{{N_0}\choose{m_0}}}{{{N}\choose{m}}}.
\end{equation*}
Using the Stirling bound we have that
\begin{equation*}
    \max_{1 \le m \le N}\left| \log{N\choose{m}} - N
        H\l(\frac{m}{N}\r)\right| \le 2\log(N+1).
\end{equation*}
We thus find that
\begin{align*}
    \Pr\lc \frac{1}{m}\sum_{i=1} Z_i > \nu \rc &\le \sum_{m_1=m\nu}^m
    \exp\lc N_0 H\l(\frac{m_0}{N_0}\r) + N_1 H\l(\frac{m_1}{N_1}\r)
    - N H\l(\frac{m}{N}\r) + 6\log(N+1)\rc \\
    &= \sum_{m_1=m\nu}^m \exp\lc-m D(\nu \| \mu) -
        (N-m) D\left. \l(\frac{\mu-\beta\nu}{1-\beta}\right\| \mu
         \r) + 6\log(N+1)\rc .
\end{align*}
The claim is concluded by upper bounding the sum by the product of
the number of terms in the sum and the maximal term. It is easy to
verify that the maximal summand is attained at $\nu=\mu$. Assuming
that $\nu> \mu$, and using the convexity of $D(\nu\|\mu)$ with
respect to $\nu$, we conclude that the largest contribution to the
sum is attained at $m_1=m\nu$, yielding the bound
\begin{align*}
    \Pr\lc \frac{1}{m}\sum_{i=1} Z_i > \nu \rc &\le m(1-\nu)
     \exp\lc-m D(\nu \|\mu) -
        (N-m) \left. D \l(\frac{\mu-\beta\nu}{1-\beta}\right\| \mu \r) +
        6\log(N+1)\rc \\
        &\le \exp\lc-m D(\nu\|\mu) -
        \left. (N-m)D \l(\frac{\mu-\beta\nu}{1-\beta} \right\| \mu \r) +
        7\log(N+1)\rc,
\end{align*}
which establishes the claim upon setting $\nu = \bar c + \veps$.
\end{proof}
Note that the proof of the last bound does not rely
on the Chernoff-Hoeffding bounding technique
as used by \citeA{Hoe63} and in many other
derivations, but rather on a direct counting argument.

%\rmnote{Expand on the importance of the second term}

\begin{remark}
We are aware of another concentration inequality for
sampling without replacement, which also applies to binary
variables. This inequality, by \citeA{HushS03}, is an extension of
a result by Vapnik \citeyear[Sec. 4.13]{Vap98}. While Vapnik's result
concerns the case $m = N/2$ ($u=m$ in the transduction setup), the
Hush and Scovel result considers the general case of arbitrary
$m$ and $N$.
The transduction bound we obtain using the Hush and Scovel
concentration inequality
is more complex
but is qualitatively the same as the bound
of Corollary~\ref{cor:dembo} that we later present.
We therefore omit this bound.
\end{remark}


%The last concentration inequality we present, again for
%binary variables, is by \citep{HushS03} and as noted in that paper
%it is an extension of a result by \citet[][Sec. 4.13]{Vap98}.
%While Vapnik's result concerns the case $m = N/2$
%($u=m$ in the transduction setup),
%the following theorem
%considers the general case (of arbitrary $m$ and $N$).
%
%\begin{theorem}[Vapnik, Hush \& Scovel]
%\label{thm:vapnik_hush} Let ${\cal C} = \{c_1,\ldots,c_N\}$ be a
%finite set of binary variables (i.e. $c_i \in \{0,1\}$) among which
%$\ell$ are ones. Let $Z_1,\ldots,Z_m$, be random variables obtaining
%their values by sampling ${\cal C}$ uniformly at random
%\textbf{without} replacement. Set $Z = (1/m) \sum_{i=1}^m Z_i$.
%Then, for $\eps \geq 2/m$,
%$$
%\Pr \{ Z_m - \rE Z_m \geq \eps \} \le \exp \left\{-2\beta(N,m,\ell)((m\eps)^2-1)
%\right\} ~,
%$$
%where
%\begin{equation}
%\label{eq:max}
%\beta(N,m,\ell) = \max \left\{
%\left(\frac{1}{m+1} +\frac{1}{N-m+1}\right), \
%\left(\frac{1}{\ell+1} +\frac{1}{N-\ell+1}\right)
%\right\},
%\end{equation}
%and similarly for $\Pr \{ \rE Z_m - Z_m \geq \eps \}$.
%\end{theorem}

%Finally, we present a concentration result for the general case of
%sampling without replacement. The proof is based on an elegant
%demonstration of equivalence between the problem of sampling
%without replacement and a second problem involving independently
%sampled data. This equivalence is demonstrated by the following
%Lemma, which appears as part of the proof of Theorem 7.2.1 in
%\cite[]{DemZei98}.
%
%\begin{lemma}\label{lem:DemZeiEq}
%Let the conditions of Theorem \ref{thm:hoeffding} hold. Let
%$X=\{X_1,\ldots,X_N\}$ be be a sequence of Bernoulli$(\beta)$
%i.i.d.\ random variables. Let $V_m$ be the number of times that
%$X_i=1$, for $X_i\in X$. Then
%\begin{equation}\label{eq:equiv}
%    \Pr\lc \frac{1}{m}\sum_{i=1}^m Z_i - \bar c > \eps \rc
%    = \Pr\lc \frac{1}{m}\sum_{i=1}^N c_i X_i - \bar c > \eps
%    \left| V_m = m \right.\rc~.
%\end{equation}
%\end{lemma}
%
%Since the random variables $\{X_i\}$ in Lemma \ref{lem:DemZeiEq} are
%independent we may use the Hoeffding or Bernstein inequalities to
%derive a concentration result. We provide a result using the
%Bernstein bound (\ref{eq:Bernstein}).
%
%\begin{theorem}\label{thm:DZBernst}
%Let the conditions of Lemma \ref{lem:DemZeiEq} hold, and set $s^2 =
%(1/N)\sum_{i=1}^N c_i^2$. Then
%\begin{equation*}
%    \Pr\lc \frac{1}{m}\sum_{i=1}^m Z_i - \bar c > \eps \rc
%    \le (N+1) \exp\lc - \frac{\l(\frac{N}{N-m}\r) m\eps^2}
%        {2s^2 + 2B\eps/3(1-m/N)}\rc .
%\end{equation*}
%\end{theorem}
%\begin{proof}
%Based on the equivalence (\ref{eq:equiv}) we have that
%\begin{align*}
%  \Pr\lc \frac{1}{m}\sum_{i=1}^m Z_i - \bar c > \eps \rc
%    &= \Pr\lc \frac{1}{m}\sum_{i=1}^N c_i X_i - \bar c > \eps
%    ,~V_m=m \rc {\Huge /} \Pr(V_m = m) ~, \\
%    &\le \Pr\lc \frac{1}{m}\sum_{i=1}^N c_i X_i - \bar c > \eps
%    \rc {\Huge /} \Pr(V_m = m)~.
%    \end{align*}
%The probability that $V_m=m$ is given by the binomial distribution
%\begin{equation*}
%  \Pr (V_m  = m) = \binom{N}{m} \beta^m (1-\beta)^{N-m} .
%\end{equation*}
%Using the bound $\binom{N}{m} \ge \frac{1}{N+1}2^{NH(m/N)}$ we
%conclude that $\Pr(V_m  = m) \ge \frac{1}{N+1}$. Recalling that
%$\beta=m/N$ we then find that
%\begin{align*}
%  \Pr\lc \frac{1}{m}\sum_{i=1}^m Z_i - \bar c > \eps \rc
%  &\le (N+1) \Pr\lc \frac{1}{N}\sum_{i=1}^N c_i X_i -
%        \beta\bar c > \beta\eps \rc \\
%  &\le (N+1)\exp\lc-\frac{-N\beta\eps^2}{2(1-\beta)s^2 + 2B\eps/3}\rc
%\end{align*}
%where the final line follows from an application of the Bernstein
%inequality (\ref{eq:Bernstein}). The claim follows upon substituting
%$\beta=m/N$.
%\end{proof}
%===========================================================

\section{PAC-Bayesian Transduction Bounds}
\label{sec:pac-bayes-trans}

In this section we present general error bounds for transductive
learning. Our bounds can be viewed as extensions of McAllester's
PAC-Bayesian inductive bounds
\citeyear{mcallester99,McA03,McAllester03b}. In
Section~\ref{sec:PAC-Bayes-Gibbs} we focus on simple randomized
learning algorithms which are typically referred to as `Gibbs
algorithms'. Then in Section~\ref{sec:deterministic} we consider a
standard deterministic setting. In the case of binary classification
the bounds for deterministic learning are comparable to Vapnik's
bounds presented in Section~\ref{sec:Vapnik_implicit}. Unlike the
implicit but tight PAC-Bayesian bound of
Theorem~\ref{thm:vapnik_relative} (and
Corollary~\ref{cor:vapnik_relative}), the new bounds are somewhat
looser but explicit.

\subsection{Bounds for Transductive Gibbs Learning}
\label{sec:PAC-Bayes-Gibbs}

We present two bounds. The first is
a rather immediate extension of McAllester's bound
\citeyear[equation (6)]{McAllester03b}, using
a reduction to independence, as discussed in Section~\ref{sec:reduction}.
The second bound is based on the `direct approach' and is considerably tighter
in many cases of interest.

Within the original inductive setting, the selection of the prior
distribution $\ppp$ in the PAC-Bayesian bounds must be made prior to
observing the data. As we later show, in the present transductive
setting it is possible to obtain much more compact (and effective)
priors by first observing the full input sample $X_{m+u}$ and using
it to construct a prior $\ppp = \ppp(X_{m+u})$.
However, as shown by
\citeA{McA03}, under certain conditions it is possible to provide
performance guarantees even if we select a ``posterior''
distribution over the hypothesis space \emph{after} observing the
labels of the training points $X_m$. The guarantee is provided for a
\emph{Gibbs algorithm}, which is simply
 a \emph{stochastic} classifier defined as follows.
 Let $\qqq$ be
any distribution over $\cH$. The corresponding Gibbs classifier,
denoted by $G_{\qqq}$, classifies any new instance using a randomly chosen
hypothesis $h \in \cH$, with $h \sim \qqq$ (i.e. each new instance is classified with
a potentially new random classifier).

For Gibbs classifiers we now extend definition (\ref{eq:risk_def})
as follows. Let $Z = x_1,\ldots,x_{|Z|}$ be any set of samples and
let $G_{\qqq}$ be a Gibbs classifier over $\cH$. The (expected) risk
of $G_{\qqq}$ over $Z$ is
\begin{equation*}
  R_{G_{\qqq}}(Z) \eqdef
 \rE_{h \sim \qqq}
 \left\{ \frac{1}{|Z|}\sum_{i=1}^{|Z|} \ell(h(x_i),\phi(x_i)) \right\}.
\end{equation*}
As before, when $Z = X_m$ (the training set) we use the standard
notation $\hR_{G_{\qqq}}(S_m) = R_{G_{\qqq}}(X_m)$.

The first risk bound we state for transductive Gibbs classifiers
is a simple extension of the recent inductive generalization bound
for Gibbs classifiers presented by \citeA{McAllester03b}. The new
transductive bound relies on reduction to independence and its
proof follows almost exactly the proof of the original inductive
result. We therefore omit the proof but note that the inductive
bound relies on the variant of Theorem~\ref{thm:hoeffding}
(inequality~(\ref{eq:Hoeffding_DKL})) for sampling with
replacement. The new bound is obtained by bounding the divergence
between the $R_h(X_{m+u})$ and $\hR_h(S_m)$ now relying on
inequality~(\ref{eq:Hoeffding_DKL}), which concerns sampling
without replacement. The bound on the transductive risk $R_h(X_u)$
is obtained using the following simple generalization of
Lemma~\ref{lem:trans_reduction}, stating that for all $\qqq$ and $C$,
\begin{equation}
\label{eq:lemma_trans_equivalence_gibbs} R_{G_{\qqq}}(X_{m+u}) \le
\hR_{G_{\qqq}}(S_m) + C \ \ \ \Leftrightarrow \ \ \
R_{G_{\qqq}}(X_{u}) \le \hR_{G_{\qqq}}(S_m) + \frac{m+u}{u}\cdot
C.
\end{equation}

\begin{theorem}[Gibbs Classifiers]
\label{thm:McAllesterDKL_sqrt} Let $X_{m+u} = X_m \cup X_u$ be the
full sample. Let $\ppp = \ppp(X_{m+u})$ be a (prior) distribution
over $\cH$ that may depend on the full sample. Let $\delta \in
(0,1)$ be given. Then with probability at least $1-\delta$ over the
choices of $S_m$ (from the full sample) the following bound holds
for any distribution $\qqq$,
\begin{equation}
R_{G_{\qqq}}(X_{u}) \leq \hR_{G_{\qqq}}(S_m) +
\left(\frac{m+u}{u}\right) \left( \sqrt{\frac{2\hR_{G_{\qqq}}(S_m)
\l(D(\qqq || \ppp) + \ln \frac{m}{\delta}\r)}{m-1}} + \frac{2\left(
D(\qqq || \ppp) + \ln \frac{m}{\delta}\right)}{m-1}  \right),
\label{eq:second theorem}
\end{equation}
where $D(\cdot || \cdot)$ is the familiar Kullback-Leibler (KL)
divergence \cite<see e.g.>{cover91}.
\end{theorem}
Notice that when $\hR_{G_{\qqq}}(S_m) = 0$ (the so-called ``realizable case'')
fast
convergence rates
of order $1/m$ are possible when $u$ is sufficiently large
(i.e. $u=\omega(m)$).

The next risk bound we present for transductive  Gibbs
\emph{binary} classifiers
relies on the ``direct'' concentration inequality of
Theorem~\ref{thm:DemZei}, for sampling without replacement.
The proof is
based on the proof technique
recently presented by \citeA{McAllester03b}, which, in turn,
is based on the results of \citeA{LanSha02} and \citeA{See03}.

\begin{theorem}[Binary Gibbs Classifiers]
\label{thm:GibbsBinary}
Let the conditions of Theorem \ref{thm:McAllesterDKL_sqrt} hold, and
assume the loss is binary. Then with probability at least $1-\delta$
over the choices of $S_m$ (from the full sample) the following bound
holds for any distribution $\qqq$,
\begin{align*}
    R_{G_\qqq}(X_u) &\le  \hat R_{G_\qqq}(S_m) +
    \sqrt{\l(\frac{2\hat R_{G_\qqq}(S_m)(m+u)}{u}\r)
    \frac{D(\qqq\|\ppp) + \ln\frac{m}{\delta} + 7\log(m+u+1)}{m-1}} \\
    &+
    \frac{2\l(D(\qqq\|\ppp) + \ln\frac{m}{\delta} +
    7\log(m+u+1)\r)}{m-1} \quad
\end{align*}
\end{theorem}
Before we prove Theorem~\ref{thm:GibbsBinary}
observe that when $\hR_{G_\qqq}(S_m) = 0$ (the ``realizable case'')
the bound
converges even if $u=1$. In contrast,
the bound of Theorem~\ref{thm:McAllesterDKL_sqrt} diverges
in the realizable case for any $u = O(\sqrt{m})$.


For proving Theorem~\ref{thm:GibbsBinary} we quote without proof two
results by \citeA{McAllester03b}.
\begin{lemma}[\citeR<Lemma 5, >{McAllester03b}]
\label{lem:McA03_5}
Let $X$ be a random variable satisfying
%\begin{equation*}
    $\Pr\lc X > x\rc \le e^{-mf(x)}$
%\end{equation*}
where $f(x)$ is non-negative. Then
%\begin{equation*}
    $\rE\left[ e^{(m-1)f(X)}\right] \le m$.
%\end{equation*}
\end{lemma}
\begin{lemma}[\citeR<Lemma 8, >{McAllester03b}]
\label{lem:McA03_8}
%\begin{equation*}
    $\rE_{x\sim \qqq}[f(x)] \le D(\qqq\|\ppp) + \ln \rE_{x\sim\ppp}
    e^{f(x)}$.
%\end{equation*}
\end{lemma}

\noindent \textbf{Proof of Theorem~\ref{thm:GibbsBinary}:}
The proof is based on the ideas by \citeA{McAllester03b}.
Define
\begin{equation*}
    \hat\nu_h \eqdef \hat R_h(S_m) \quad ; \quad \mu_h \eqdef R_h(X_{m+u}).
\end{equation*}
Let
\begin{equation*}
  f_h(\nu) \eqdef D(\nu\|\mu_h) +
  \frac{u}{m}D\l(\frac{\mu_h-\beta\nu}{1-\beta}\|\mu_h\r)
        -\frac{7}{m} \log(m+u+1).
\end{equation*}
>From Lemma \ref{lem:McA03_8} we have that
\begin{equation}\label{eq:Ehq}
  \rE_{h\sim \qqq} \left[(m-1)f_h(\nu)\right]
  \le D(\qqq\|\ppp) + \ln\rE_{h\sim \ppp} \left[e^{(m-1)f_h(\nu)}\right].
\end{equation}
An upper bound on $\rE_{h\sim \ppp} \left[e^{(m-1)f_h(\nu)}\right]$
may be obtained by the following argument. From Theorem
\ref{thm:DemZei} we have that
\begin{equation*}
    \Pr\lc\hat \nu_h > \nu \rc \le \exp\{-mf_h(\nu)\}.
\end{equation*}
Lemma \ref{lem:McA03_5} then implies that for any $h$
\begin{equation*}
    \rE_{\Sigma_m} \left[ e^{(m-1) f_h(\hat\nu_h)}\right] \le m ,
\end{equation*}
which implies that
\begin{equation*}
    \rE_{\Sigma_m} \rE_{h\sim\ppp} \left[ e^{(m-1) f_h(\hat\nu_h)}\right] \le m ,
\end{equation*}
from which we infer that with probability at least $1-\delta$,
\begin{equation*}
    \rE_{h\sim\ppp} \left[ e^{(m-1) f_h(\hat\nu_h)}\right] \le \frac{m}{\delta}
\end{equation*}
by using Markov's inequality. Substituting in (\ref{eq:Ehq}) we find
that with probability at least $1-\delta$,
\begin{equation}
  \rE_{h\sim \qqq} \left[(m-1)f_h(\hat\nu_h)\right]
  \le D(\qqq\|\ppp) + \frac{m}{\delta}~ .
\end{equation}
Substituting for $f_h(\hat\nu_h)$, and using the convexity of the
function $x\log x$,  we find that
\begin{align}\label{eq:KLlower}
    &D(\hat R_{G_\qqq}(S_m)\|R_{G_\qqq}(X_{m+u})) +
    \frac{u}{m} D\l(\frac{R_{G_\qqq}(X_{m+u})-
    \beta\hat R_{G_\qqq}(S_m)}{1-\beta}\|R_{G_\qqq}(X_{m+u}) \r)
    -\frac{7}{m} \log(m+u+1) \notag \\
     &\le \frac{D(\qqq\|\ppp) + \ln\frac{m}{\delta}}{m-1} ~.
\end{align}
In order to obtain an explicit bound, we use the inequality
\begin{equation*}
    D(\nu\|\mu) \ge \frac{(\nu-\mu)^2}{2\mu} ,
\end{equation*}
and substitute this in (\ref{eq:KLlower}) obtaining
\begin{equation*}
    \underbrace{R_{G_\qqq}(X_{m+u})}_z \le  \underbrace{\hat R_{G_\qqq}(S_m)}_a +
    \sqrt{\underbrace{R_{G_\qqq}(X_{m+u})}_z
    \underbrace{\l(\frac{2u}{m+u}\r)\frac{D(\qqq\|\ppp) +
    \ln\frac{m}{\delta} + 7\log(m+u+1)}{m-1}}_b}.
\end{equation*}
Thus we have (with probability at least $1-\delta$), $z \leq a +
\sqrt{zb}$ (where $z=R_{G_\qqq}(X_{m+u})$). Solving for $z$ we get
$z \le a+b+\sqrt{ab}$, and using Lemma \ref{lem:trans_reduction}
yields the desired result.
%which holds iff $f(z) = z^2 - (2a+b)z +
%a^2 \leq 0$. The solutions of $f(z)$ are $z_{1,2} =
%\frac{1}{2}(2a+b) \pm \frac{1}{2}\sqrt{b^2 + 4ab}$. Therefore, if
%$f(z) \leq 0$ then $z \leq z_1 = \frac{1}{2}(2a+b)+
%\frac{1}{2}\sqrt{b^2 + 4ab} \leq a + \frac{1}{2}b + \frac{1}{2}b +
%\sqrt{ab}$. This leads to the desired result.
\QED

\begin{remark}
It is interesting to compare the bound of Theorem
\ref{thm:McAllesterDKL_sqrt}, based on the reduction to
independence approach, and that of Theorem \ref{thm:GibbsBinary}
which is based on a direct concentration inequality for sampling
without replacement. The complexity term in Theorem
\ref{thm:McAllesterDKL_sqrt} is multiplied by $(m+u)/u$, while the
corresponding term in Theorem \ref{thm:GibbsBinary} is multiplied
by $\sqrt{(m+u)/u}$. This clearly displays the advantage of using
the direct concentration bound, even though it does \emph{not}
lead to improved convergence rates in general. More importantly,
for the realizable case, $\hat R_{G_\qqq}(S_m)=0$, the bound of
Theorem \ref{thm:GibbsBinary} converges to zero even for $u=1$.
This is not the case for the bound of Theorem
\ref{thm:McAllesterDKL_sqrt}.
\end{remark}



%-----------------------------------------------------------------
\subsection{Bounds for Deterministic Learning Algorithms}
\label{sec:deterministic}

In this section we present three transductive PAC-Bayesian error
bounds for deterministic learning algorithms. Note that the two
bounds we present for the (stochastic) Gibbs algorithms in the
previous subsection can be specialized to deterministic
algorithms. This is done by choosing a ``posterior'' $\qqq$ which
assigns probability 1 to one desired hypothesis $h \in \cH$. In
doing so the term $D(\qqq \| \ppp)$ reduces to $\log(1/\ppp(h))$. For
example, the bound of Theorem~\ref{thm:McAllesterDKL_sqrt} reduces
to
\begin{equation}
R_{h}(X_{u}) \leq \hR_{h}(S_m) +
\left(\frac{m+u}{u}\right) \left( \sqrt{\frac{2\hR_{h}(S_m)
\l(\log\frac{1}{\ppp(h)} + \ln \frac{m}{\delta}\r)}{m-1}} + \frac{2\left(
\log(\frac{1}{\ppp(h)} + \ln \frac{m}{\delta}\right)}{m-1}  \right),
\label{eq:deterministic_McAllester}
\end{equation}
which applies to any bounded loss function.

The following bound relies of the Serfling concentration inequality
presented in Theorem~\ref{thm:serfling} and applies to
any bounded loss function.\footnote{Although we have not utilized
the Serfling inequality for devising a bound for the Gibbs
algorithm, it can be done as well.}

\begin{theorem}
\label{thm:serfling_sqrt} Let $X_{m+u} = X_m \cup X_u$ be the full
sample and let $\ppp = \ppp(X_{m+u})$ be a (prior) distribution over
$\cH$ that may depend on the full sample. Assume that $\ell(h(x),y)
\in [0,B]$ and let $\delta \in (0,1)$ be given. Then, with
probability at least $1-\delta$ over choices of $S_m$ (from the full
sample) the following bound holds for any $h \in \cH$,
\begin{equation}\label{eq:pac_sqrt2}
R_h(X_{u}) \leq \hR_h(S_m) + B
\sqrt{\left(\frac{m+u}{u}\right)
\left(\frac{u+1}{u}\right)\left(\frac{\ln\frac{1}{\ppp(h)} +\ln
\frac{1}{\delta} }{2m} \right)}~.
\end{equation}
\end{theorem}

\begin{proof}
In our transduction setting the set $X_m$ (and
therefore $S_m$) is obtained by sampling the full sample $X_{m+u}$
uniformly at random without replacement. It is not hard to see that
$\rE_{\Sigma_m} \hR_h(S_m) = R_h(X_{m+u})$. Specifically,
\begin{equation}
\label{eq:expectation_of_Sm}
\rE_{\Sigma_m} \hR_h(S_m) =
\frac{1}{{{m+u}\choose{m}} }\sum_{S_m} \hR_h(S_m)
=
\frac{1}{{{m+u}\choose{m}} }\sum_{X_m \subseteq X_{m+n}} \frac{1}{m} \sum_{x \in S_m}
\ell(h(x),\phi(x)).
\end{equation}
By symmetry, all points $x \in X_{m+u}$ are counted on the
right-hand side an equal number of times; this number is precisely
${{m+u}\choose{m}} - {{m+u-1}\choose{m}} = {{m+u-1}\choose{m-1}}$.
The result is obtained by considering the definition of
$R_h(X_{m+u})$ and noting that
${{m+u-1}\choose{m-1}}/{{m+u}\choose{m}} = \frac{m}{m+u}$. Using
the fact that our loss function is bounded in $[0,B]$
we apply Theorem~\ref{thm:serfling} (for a
fixed $h$ and $N=m+u$),
\begin{equation}\label{eq:chernoff bound}
\Pr_{\Sigma_m} \left\{ \rE \hR_h(S_m) - \hR_h(S_m)  > \veps \right\}
\leq e^{-\frac{2m\veps^2}{B^2}\left(\frac{m+u}{u+1}\right)}.
\end{equation}
Setting $\veps(h) = B\sqrt{{{(u+1)(\ln{1\over{\ppp(h)}} +
\ln{1\over{\delta}})}\over{(m+u)2m}}}$ and using the union bound we
find
\begin{align*}
  \Pr_{\Sigma_m} \left\{ \exists h\in\cH~\mbox{s.t.~}
    R_h(X_{m+u}) - \hR_h(S_m)  > \veps(h) \right\}
    &\leq \sum_h \exp\left\{-\frac{2m\veps(h)^2}{B^2}\left(\frac{m+u}{u+1}\right)\right\} \\
    &= \sum_h \ppp(h) \delta \\
    &= \delta.
%    \sqrt{{{(u+1)(\ln{1\over{\ppp(h)}} +
%    \ln{1\over{\delta}})}\over{2m(m+u)}}}\right\} \le
%    \delta. \qquad\qquad
\end{align*}
We thus obtain that
\begin{equation}
R_h(X_{m+u}) \leq \hR_h(S_m) + B
\sqrt{\left(\frac{u+1}{m+u}\right)
\left(\frac{\ln\frac{1}{\ppp(h)} +\ln \frac{1}{\delta}
}{2m} \right)}~. \label{eq:pac_sqrt3}
\end{equation}
The proof is then completed using Lemma~\ref{lem:trans_reduction}.
\end{proof}

For classification using the 0/1 loss function
we present one bound, which is a specialization of
Theorem~\ref{thm:GibbsBinary}.

\begin{corollary}
\label{cor:dembo}
Let the conditions of Theorem~\ref{thm:serfling_sqrt} hold
and assume the loss is binary. Then with probability at least $1-\delta$
over the choices of $S_m$ (from the full sample) the following bound
holds for any distribution $\qqq$,
\begin{align*}
    R_{h}(X_u) &\le  \hat R_{h}(S_m) +
    \sqrt{\l(\frac{2\hat R_{h}(S_m)(m+u)}{u}\r)
    \frac{\log\frac{1}{\ppp(h)} + \ln\frac{m}{\delta} + 7\log(m+u+1)}{m-1}} \\
    &+
    \frac{2\l(\log\frac{1}{\ppp(h)} + \ln\frac{m}{\delta} +
    7\log(m+u+1)\r)}{m-1} \quad.
\end{align*}
\end{corollary}


Figures~\ref{fig:realizable_bounds} and~\ref{fig:emp_20_bounds}
compare the two bounds presented in this section with Vapnik's
bound of Corollary~\ref{cor:vapnik_relative}. Throughout the
discussion here the bound of Theorem~\ref{thm:serfling_sqrt} is
referred to as the ``Serfling bound''.
Figure~\ref{fig:realizable_bounds} focuses on the realizable case
(i.e. empirical error $= 0$). According to the statements of
Theorem~\ref{thm:serfling_sqrt} and Corollary~\ref{cor:dembo}, the
Serfling bound has a significantly slower rate of convergence in
the realizable case. However, the constants (and logarithmic
terms) are larger in the bound of Corollary~\ref{cor:dembo}.
Panels (a) and (b) in Figure~\ref{fig:realizable_bounds} indicate
that the Serfling bound is significantly better than the bound of
Corollary~\ref{cor:dembo} when $u = \Omega(m)$ for the range of
$m$ we consider. However, even in these cases, we know that the
bound of Corollary~\ref{cor:dembo} will eventually outperform the
Serfling bound. We also see that the Serfling bound tracks
Vapnik's bound quite well when $u = \Omega(m)$. On the other hand,
Panels (c) and (d) indicate that the bound of
Corollary~\ref{cor:dembo} is significantly better than the
Serfling bound when $u=o(m)$. The examples given are $u=\sqrt{m}$
in Panel (c) and $u=10$ in Panel (d).
Figure~\ref{fig:emp_20_bounds} shows these bounds for the case
$\hR_h(S_m) = 0.2$. Here again the Serfling bound nicely tracks
Vapnik's bound and we see that the bound of
Corollary~\ref{cor:dembo} converges much more slowly. All the
curves in Figures~\ref{fig:realizable_bounds}
and~\ref{fig:emp_20_bounds} consider the case $\ppp(h) = 1$. This
assignment of the prior eliminates the influence of the union
bound that is used to derive these bounds. In
Figure~\ref{fig:variable_p} we show, for both the Vapnik and
Serfling bounds, the complexity term as a function of the prior
$\ppp(h)$, with $0.01 \leq \ppp(h) \leq 1$. Note that such prior
assignments are realistic in the case of the transduction
algorithm based on clustering that is introduced in
Section~\ref{sec:clustering}.

While these plots indicate that our bounds approximate Vapnik's
bound quite well in many cases of interest, we also see that for
small values of $m$ (similar to those considered in
the plots) one will gain in applications by using the implicit but
tighter Vapnik bound (or the Blum and Langford,\citeyearR{BlumL03}, bound).


%For example, Figure~\ref{fig:clustering_bounds} illustrates
%these bounds (adapted to bounds on $X_u$ as required in Setting 1, using
%Lemma~\ref{lem:trans_reduction})
%for a binary classification problem
%using realistic values of the bound parameters.
%
\begin{figure}[htb!]
\begin{center}
\begin{tabular}{ccc}
        \epsfig{file=Figs/realizable_u_10m.eps,width=3in} &
        \epsfig{file=Figs/realizable_m_u.eps,width=3in} \\
        (a) & (b) \\
        \epsfig{file=Figs/realizable_u_sqrt.eps,width=3in} &
        \epsfig{file=Figs/realizable_u_10.eps,width=3in} \\
        (c) & (d)
\end{tabular}
\end{center}
%\vspace{.5cm}
\caption{A comparison of Vapnik's bound
(Corollary~\ref{cor:vapnik_relative}), the bound of
Theorem~\ref{thm:serfling_sqrt} (denoted here by
``Serfling bound'') and the bound of Corollary~\ref{cor:dembo}.
All bounds assume zero empirical error, $\delta=0.01$ and $\ppp(h) = 1$.
(a) $u = 10m$; (b) $u = m$; (c) $u = \sqrt{m}$; and (d) $u=10$.}
\label{fig:realizable_bounds}
\end{figure}
%


\begin{figure}[htb!]
\begin{center}
\begin{tabular}{ccc}
        \epsfig{file=Figs/emp_20_u_10m.eps,width=3in} &
        \epsfig{file=Figs/emp_20_u_m.eps,width=3in} \\
        (a) & (b)
\end{tabular}
\end{center}
%\vspace{.5cm}
\caption{A comparison of Vapnik's bound
(Corollary~\ref{cor:vapnik_relative}), the bound of
Theorem~\ref{thm:serfling_sqrt} (denoted here by
``Serfling bound'') and the bound of Corollary~\ref{cor:dembo}.
All bounds assume empirical error of $0.2$, $\delta=0.01$ and $\ppp(h) = 1$.
(a) $u = 10m$; (b) $u = m$.}
\label{fig:emp_20_bounds}
\end{figure}
%

\begin{figure}[htb!]
\begin{center}
        \epsfig{file=Figs/emp0_varp_UequalM50.eps,width=3in}
\end{center}
%\vspace{.5cm}
\caption{The complexity term of the Vapnik and Serfling
bounds as a function of $\ppp(h)$ with $0.01 \leq \ppp(h) \leq 1$, $\delta
= 0.01$ and $m=u=50$.} \label{fig:variable_p}
\end{figure}






%The last bound we present relies on the
%concentration inequality given by
%Theorem~\ref{thm:vapnik_hush} we now obtain the following
%bound for transduction under the 0/1 loss function.
%
%\begin{theorem}\label{thm:trans_sharper}
%Let $\cH$ be a class of binary classifiers, and set
%$\ell(h(x),y)=I(y\ne h(x))$ to be the $0/1$ loss. Under the
%conditions of Theorem~\ref{thm:serfling_sqrt}, with probability at
%least $1-\delta$, for any $h \in \cH$,
%$$
%R_h(X_{m+u}) \leq \hR_h(S_m) +
%  \left(\frac{m+u}{u}\right)\sqrt{\frac{
%  C(m,u,\ell_h) \cdot \left(\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}\right)
%  +2(m+u+2)}
%  {
%  2m^2(m+u+2)
%  }},
%$$
%where
%$$
%C(m,u,\ell_h)
%= \min \left\{
%\begin{array}{l}
%  (m+1)(u+1),\\
%  (\ell_h+1) (m+u-\ell_h+1),\\
%\end{array}
%\right\},
%$$
%and $\ell_h = (m+u)R_h(X_{m+u})$.
%\end{theorem}
%
%\begin{proof}
%The proof is very similar to the proof of
%Theorem~\ref{thm:serfling_sqrt} so we only note
%the differences.
%For $h \in \cH$, such that $\ell_h = (m+u)R_h(X_{m+u})$,
%and noting that $N = m+u$
%we write the two arguments of the $\max$ in (\ref{eq:max}) as follows
%\begin{align*}
%\beta_1 &\eqdef \frac{1}{m+1} + \frac{1}{u+1} = \frac{m+u+2}{(m+1)(u+1)},\\
%\beta_2 &\eqdef \frac{1}{\ell_h+1} + \frac{1}{m+u-\ell_h+1} = \frac{m+u+2}{(\ell_h+1)(m+u-\ell_h+1)}.
%\end{align*}
%Thus, instead of inequality~(\ref{eq:chernoff bound})
%we now have, using Theorem~\ref{thm:vapnik_hush},
%\begin{equation}\label{eq:max bound}
%\Pr_{\Sigma_m} \left\{ \rE \hR_h(S_m) - \hR_h(S_m)  > \veps \right\}
%\leq \exp \left\{ -2 \max\{ \beta_1, \beta_2 \}(m^2 \veps^2 -1) \right\}.
%\end{equation}
%If $\beta_1 \geq \beta_2$ by taking
%$$
%\veps(h) = \sqrt{\frac{
%\left(\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}\right)(m+1)(u+1)
%+ 2(m+u+2)}
%{2m^2(m+u+2)}},
%$$
%and using the union bound we get
%\begin{equation*}
%  \Pr_{\Sigma_m} \left\{ \exists h\in\cH~\mbox{s.t.~}
%    R_h(X_{m+u}) - \hR_h(S_m)  > \veps(h) \right\} \le
%    \delta.
%\end{equation*}
%In the other case ($\beta_1 < \beta_2$) we take
%$$
%\veps(h) = \sqrt{\frac{
%\left(\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}\right)(\ell_h+1)(m+u-\ell_h+1)
%+ 2(m+u+2)}
%{2m^2(m +u+2)}}.
%$$
%The proof is complete using Lemma~\ref{lem:trans_reduction}
%\end{proof}
%
%Theorem~\ref{thm:trans_sharper} provides significantly
%faster rates of convergence in some special cases.
%For example when $m = \Theta(u)$ (e.g. $m = u$) and
%$\ell_h$ constant, it is easy to verify that we get
%$$
%R_h(X_u) \leq \hR_h(S_m) + O\left( \frac{\sqrt{\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}}}
%{m}\right).
%$$
%When $\ell_h = O(\sqrt{m})$ (and $m=u$) we get
%$$
%R_h(X_u) \leq \hR_h(S_m) + O\left( \frac{\sqrt{\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}}}
%{m^{3/2}}\right).
%$$
%Nevertheless, recall that the quantity $\ell_h$ is not available to
%us and therefore the bound, as stated, cannot be used without
%observing the labels of the test points. For the special case $m=u$
%we provide the following corollary, the proof of which appears in
%the appendix.
%
%\begin{corollary}
%\label{cor:hush}
%Let the conditions of Theorem~\ref{thm:trans_sharper} hold but now assume that
%$m=u$. Set $\lambda_h = \log\frac{1}{p(h)} + \log\frac{1}{\delta}$.
%Then,
%\begin{align}
%R_h(X_u) &\leq \hR_h(S_m) +
%\frac{\lambda_h(1-2\hR_h(S_m))}{m+\lambda_h+1}\\ \nonumber
%&\ \ \ \ \ \ \ \ +\frac{\sqrt{(m+1)
%\left(
%4\lambda_h m^{2}\hR_h(S_m)(1-\hR_h(S_m))+m(2\lambda_h+\lambda_h^{2}+4)+
%\lambda_h^{2}+5\lambda_h+4\right) }}{\left( m+\lambda_h+1\right) m}
%\label{eq:cor_hush} \\
%&\leq \hR_h(S_m) + \frac{\lambda_h}{m+\lambda_h+1}
%+O\left(
%\frac{\sqrt{\lambda_h m^{2}\hR_h(S_m)+m\lambda_h^{2} }}{\left( m+\lambda_h+1\right) \sqrt{m}}
%\right). \nonumber
%\end{align}
%\end{corollary}
%We see that when $m=u$ we obtain convergence at rate $1/m$ when
%$\hR_h(S_m)=0$ (the so called `realizable case'). However, when the
%empirical error is non-negligible we are back with the ``standard''
%$1/\sqrt{m}$ rate. The nice feature of this bound is that it
%smoothly interpolates between the realizable case and the general
%case.\rmnote{But we've seen examples of this before}
%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%\label{cor:McAllesterDKL}

%\begin{remark}
%By taking $(2m-1)$ instead of $m$ in the exponents in the left hand side
%of inequality~(\ref{eq:hoeffding_exp}),
%Lemma~\ref{lem:dkl} can be modified to
%$$
%\Pr_{\Sigma_m} \lc \rE_{h\sim \ppp}e^{(2m-1)\hDelta_h^2} >
%    \frac{2m}{\delta}\rc < \delta.
%$$
%Consequently, the complexity term in Theorem~\ref{thm:McAllesterDKL}
%achieves a faster rate; namely this term becomes
%$$
%\sqrt{\frac{D(\qqq || \ppp) + \log \frac{2m}{\delta}}{2m-1}}.
%$$
%\end{remark}

%%==================================================================
%% A version of the KL-thm with rate $m$ instead of $2m-1$
%Theorem~\ref{thm:McAllesterDKL} that follows is analogous to Theorem~1
%in \citep{McA03}. The proof we present (including the statement
%and proof of the following Lemma~\ref{lem:dkl})
%is a simplified version
%of the proofs in \citep{McA03} and in \citep{SeegerN02,See02}.
%For each $h \in \cH$ and training set $S_m$
%define
%$$
%\hDelta_h = \Delta_h(S_m) = R_h(X_{m+u}) - \hR_h(S_m).
%$$
%\begin{lemma}\label{lem:dkl}
%Let $\ppp$ be any prior distribution over
%$\cH$ and let $\delta \in (0,1)$ be given. Then, with probability at
%least $1 - \delta$ over the random choices of $S_m$ from the full
%sample
%\begin{equation}
%\label{eq:seeger8}
%    \Pr_{\Sigma_m} \lc \rE_{h\sim \ppp}e^{m\hDelta_h^2} >
%    \frac{2}{\delta}\rc < \delta.
%\end{equation}
%\end{lemma}
%
%\begin{proof}
%Fix any hypothesis $h\in\cH$.
%Noting that
%$\rE_{\Sigma_m} \hR_h(S_m) = R_h(X_{m+u})$
%(recall Equation~(\ref{eq:expectation_of_Sm}))
%we have from Lemma~\ref{lem:hoeffding2} that
%\begin{equation*}
%  \Pr_{\Sigma_m} \lc \hDelta_h > t \rc \le e^{-2mt^2},
%\end{equation*}
%which implies that
%\begin{equation}
%\label{eq:hoeffding_exp}
%  \Pr_{\Sigma_m} \lc
%  e^{m\hDelta_h^2} > e^{m t^2} \rc \le e^{-2mt^2}.
%\end{equation}
%We then have
%\begin{align}
%  \rE_{\Sigma_m} e^{m \hDelta_h^2} &=
%      \int_0^\infty \Pr_{\Sigma_m} \lc e^{m \hDelta_h^2} \ge s\rc ds \nonumber\\
%  &= \l(\int_0^u + \int_u^\infty\r)\Pr_{\Sigma_m}\lc e^{m\hDelta_h^2}
%              \ge s\rc ds \nonumber \\
%  &\le u + \int_u^\infty \Pr_{\Sigma_m}\lc e^{m\hDelta_h^2}
%              \ge s\rc ds \nonumber \\
%  &\le u + \int_u^\infty s^{-2} ds  \label{eq:integ_step} \\
%  &= u + \frac{1}{u} \label{eq:upper_bound},
%\end{align}
%where (\ref{eq:integ_step}) follows from
%(\ref{eq:hoeffding_exp}) with $s=e^{mt^2}$ (which
%implies that $t^2 = \ln s / m$ and therefore, $e^{-2mt^2} = s^{-2}$).
%Since $u$ is arbitrary, we select it to minimize the
%upper bound (\ref{eq:upper_bound}). It is easy to see that the
%function $f(u) = u + \frac{1}{u}$ attains its global minimum at $u=1$.
%We thus have that
%\begin{equation*}
%    \rE_{\Sigma_m} e^{m\hDelta_h^2} \le 2 .
%\end{equation*}
%Averaging this result over $\ppp$ we have that
%\begin{equation}\label{eq:expec_expec}
%    \rE_{\Sigma_m} \rE_{h\sim \ppp}e^{m\hDelta_h^2}
%    = \rE_{h\sim \ppp}\rE_{\Sigma_m} e^{m\hDelta_h^2} \le 2 .
%\end{equation}
%Defining the random variable $Z = \rE_{h\sim \ppp}e^{m\hDelta_h^2}$
%and taking $v = 2/\delta$ we have
%from Markov's inequality and from (\ref{eq:expec_expec}) that
%$$
%\Pr_{\Sigma_m} \lc Z \geq v \rc \leq \frac{\rE_{\Sigma_m} Z}{v} \leq \delta.
%$$
%In other words,
%\begin{equation*}
%    \Pr_{\Sigma_m} \lc \rE_{h\sim \ppp}e^{m\hDelta_h^2} >
%    \frac{2}{\delta}\rc < \delta.
%\end{equation*}
%\end{proof}
%
%
%
%
%\begin{theorem}\label{thm:McAllesterDKL}
%Let $X_{m+u} = X_m \cup X_u$ be the full sample. Let $\ppp =
%\ppp(X_{m+u})$ be a (prior) distribution over $\cH$ that may depend
%on the full sample. Let $\delta \in (0,1)$ be given. Then with
%probability at least $1-\delta$ over the choices of $S_m$ (from the
%full sample) the following bound holds for any distribution $\qqq$,
%\begin{equation}
%R_{G_{\qqq}}(X_{m+u}) \leq \hR_{G_{\qqq}}(S_m) +
%\sqrt{\frac{D(\qqq || \ppp) + \ln \frac{2}{\delta}}{m}},
%\label{eq:second theorem}
%\end{equation}
%where $D(\cdot || \cdot)$ is the familiar Kullback-Leibler (KL)
%divergence \citep[see e.g.][]{cover91}.\footnote{Note that the
%complexity term in McAllester's original proof \citep{McA03} is
%$\sqrt{ \frac{D(\qqq||\ppp)+ \log \frac{1}{\delta} +\log m + 2} {2m-1} }$.}
%\end{theorem}
%
%\begin{proof}
%The proof closely follows the proof of a similar theorem
%in \citep{SeegerN02} (for an inductive PAC-Bayesian result).
%For any choice of the training set $S_m$
%define the following probability mass function over $\cH$,
%$$
%P_G(h) = \frac{p(h)e^{m\hDelta_h^2}}{\rE_{h\sim \ppp}
%\left\{e^{m\hDelta_h^2}\right\}}.
%$$
%It is well known \citep[see e.g.][]{cover91} that
%$D(\qqq || P_G) \geq 0$.
%Noting that $\log()$ denotes the base 2 logarithm,
%we therefore have
%\begin{align*}
%0 \leq D(\qqq || P_G) &=
%\sum_{h \in \cH} q(h)
%\log \frac{q(h) \rE_{h\sim \ppp}\left\{e^{m\hDelta_h^2}\right\}}
%{p(h) e^{m\hDelta_h^2}} \\
%&= D(\qqq || \ppp) + \log \rE_{h\sim \ppp}\left\{e^{m\hDelta_h^2}\right\}
% - \log e \cdot \rE_{h \sim \qqq} \left\{m\hDelta_h^2\right\}.
%\end{align*}
%Thus,
%\begin{equation}\label{eq:seeger6}
%\rE_{h\sim \qqq}\left\{m\hDelta_h^2\right\} \le D(\qqq || \ppp)
%    + \log\rE_{h\sim \ppp}\left\{e^{m\hDelta_h^2}\right\}
%\end{equation}
%From Lemma~\ref{lem:dkl}
%we have that
%\begin{equation*}
%    \Pr_{\Sigma_m} \lc \log \rE_{h\sim \ppp}e^{m\hDelta_h^2} \geq
%    \log \frac{2}{\delta}\rc < \delta.
%\end{equation*}
%Upon adding $D(\qqq || \ppp)$ to both sides of the inequality
%inside the curly brackets, and using (\ref{eq:seeger6})
%we find that
%\begin{align*}
%  \Pr_{\Sigma_m} \lc m \cdot \rE_{h\sim \qqq}\left[\hDelta_h^2\right]
%    \ge D(\qqq || \ppp) + \log \frac{2}{\delta}\rc < \delta.
%\end{align*}
%Therefore, with probability
%at least $1-\delta$, for all $\qqq$,
%\begin{equation}
%\label{eq:square_roots}
%\sqrt{\rE_{h\sim Q}\lc \hDelta_h^2\rc }
%    \leq \sqrt{\frac{D_(\qqq || \ppp) + \log \frac{2}{\delta}}{m}}.
%\end{equation}
%Noting that $\sqrt{x}$ is concave and using
%Jensen's inequality we have
%\begin{equation}
%\label{eq:jensen}
%\rE_{h\sim \qqq} \lc \hDelta_h \rc \leq
%\sqrt{\rE_{h\sim \qqq}\lc \hDelta_h^2\rc}.
%\end{equation}
%Combining equations~(\ref{eq:square_roots}) and~(\ref{eq:jensen})
%we conclude that with probability
%at least $1-\delta$, for all $\qqq$,
%\begin{align*}
%\rE_{h\sim \qqq} \lc \hDelta_h \rc &=
%\rE_{h\sim \qqq} \lc R_h(X_{m+u}) - \hR_h(S_m) \rc \\
%&=
%R_{G_{\qqq}}(X_{m+u}) - \hR_{G_{\qqq}}(S_m)
%\leq \sqrt{\frac{D(\qqq || \ppp) + \log \frac{2}{\delta}}{m}},
%\end{align*}
%which completes the proof.
%\end{proof}
%
%As before, using Lemma~\ref{lem:trans_reduction} we have that with
%probability at leats $1-\delta$
%$$
%R_{G_{\qqq}}(X_{u}) \leq \hR_{G_{\qqq}}(S_m) +
%\left(\frac{m+u}{u}\right)
%\sqrt{\frac{D(\qqq || \ppp) + \log \frac{2}{\delta}}{m}}.
%$$
%%\label{cor:McAllesterDKL}
%
%\begin{remark}
%By taking $(2m-1)$ instead of $m$ in the exponents in the left hand side
%of inequality~(\ref{eq:hoeffding_exp}),
%Lemma~\ref{lem:dkl} can be modified to
%$$
%\Pr_{\Sigma_m} \lc \rE_{h\sim \ppp}e^{(2m-1)\hDelta_h^2} >
%    \frac{2m}{\delta}\rc < \delta.
%$$
%Consequently, the complexity term in Theorem~\ref{thm:McAllesterDKL}
%achieves a faster rate; namely this term becomes
%$$
%\sqrt{\frac{D(\qqq || \ppp) + \log \frac{2m}{\delta}}{2m-1}}.
%$$
%\end{remark}
%


%====================================================================
%\subsection{On Priors and Prior Decompositions}
%\label{sec:multiple_priors}
%
%ZZZ
%PAC-Bayesian generalization (inductive) bounds or transductive risk bounds
%(as we present here) are interesting because they provide a very simple
%yet general formulation of learning. However, in order to provide more
%concrete statements (e.g. about specific learning algorithms) one must apply
%such bounds with some concrete priors (and posteriors, in the case of
%Gibbs learning, see Theorems~\ref{thm:McAllesterDKL_sqrt}
%and~\ref{thm:GibbsBinary}).
%In the context of inductive learning, a major obstacle in deriving
%effective bounds\footnote{Informally, we say that a bound is ``effective''
%if its complexity term vanishes with $m$ (the size of the
%training sample) and it is sufficiently small for ``reasonable'' values $m$.}
% using the PAC-Bayesian framework is
%the construction of ``compact priors''. For example, the McAllester
%generalization bound in \citep{McA99} contains a complexity term
%which includes a component of the form $\ln(1/p(h))$ where $\ppp$ is
%a prior over $\cH$
%(as in Theorem~\ref{thm:serfling_sqrt} and
%Corollary~\ref{cor:dembo}).
%The more sophisticated
%bounds in \citep{McA03,McAllester03b}
%include a Kullback-Leibler (KL) divergence
%complexity component $D(\qqq||\ppp)$ where $\ppp$ is a prior over
%$\cH$ and $\qqq$ is a posterior over $\cH$ (as in
%Theorems~\ref{thm:McAllesterDKL_sqrt} and~\ref{thm:GibbsBinary}).
%However, many hypothesis classes of
%interest are very large and even uncountably infinite. Therefore,
%despite the fact that these bounds apply in principle to very large
%$\cH$, in a straightforward application of these PAC-Bayesian
%bounds, when choosing priors with a very large support (and possibly
%a posterior with a small support), the complexity terms in these
%bounds can diverge or at least be too large to form effective
%generalization bounds.\footnote{Saying that we should also note that
%sophisticated prior choices within the PAC-Bayesian framework can
%also lead to state-of-the-art bounds as presented in \citep{McAllester03b}.}
%
%In contrast, the transductive setup provides a very
%convenient setting for applying PAC-Bayesian
%bounds. Here priors can be chosen after observing and analyzing
%the full sample. As already mentioned, in the case of the 0/1-loss,
%even if we consider a very
%large hypothesis space $\cH$, after observing the full sample, the
%effective size of equivalence classes of hypotheses in $\cH$ is
%always finite and not larger than the number of dichotomies of the
%full sample (see also Remark~\ref{rem:real-valued}).
%Moreover, as we later show one can form substantially
%more compact priors by analyzing the geometry of the full sample.
%
%We now discuss a very simple technique that allows for the
%decompositions of priors into a collection of simpler
%priors.
%In subsequent sections we use this technique
%and easily derive new bounds for specific (transductive) learning
%algorithms.
%The (simple) observation is that instead of a single prior $\ppp$ in
%``standard'' PAC-Bayesian bounds (for deterministic algorithms)
%one can use any
%PAC-Bayesian bound with a number of priors $\ppp_1,\ldots,\ppp_k$
%and then replace the complexity term $\ln(1/p(h))$
%by $\min_i\ln(1/\ppp_i(h))$, at a cost of an additional $\ln k$ term
%(see below). Similarly,
%in PAC-Bayesian bounds for the Gibbs algorithm
%(e.g. Theorem~\ref{thm:McAllesterDKL_sqrt}) we can
%replace the KL-divergence term in the bound with $\min_i
%D(\qqq||\ppp_i)$. The penalty for using $k$ priors is logarithmic in
%$k$ (specifically the $\ln(1/\delta)$ term in the original bound
%becomes $\ln(k/\delta)$). Thus, one can decompose a complex
%prior into a very large number of
%components and as long as $k$ is sub-exponential in $m$ we still obtain
%useful generalization bounds.
%This can be formulated by a minor extension of
%the PAC-Bayesian bounds, which for simplicity is stated here
%as the following extension of Theorem~\ref{thm:serfling_sqrt}.
%Similar extensions hold for all the PAC-Bayesian error bounds presented
%here and elsewhere.
%%Theorems~\ref{thm:sqrt1}, \ref{thm:serfling_sqrt}, \ref{thm:trans_sharper}
%%and~\ref{thm:McAllesterDKL}
%%as follows. Suppose
%%that instead of a single prior $\ppp$ over $\cH$ we want to utilize
%%$k$ priors, $\ppp_1,\ldots,\ppp_k$, and in retrospect choose the best
%%among the $k$ corresponding PAC-Bayesian bounds. The following
%%theorem shows that one
%%can use polynomially many priors with a minor
%%(logarithmic in $m$) penalty.
%%As long as $k
%%= o(\exp(m))$ the resulting bound will still be effective (i.e.
%%converge to zero with the sample size).
%
%%Consider $k$ applications of
%%Theorem~\ref{thm:Mcallester} (resp. Theorem~\ref{thm:revised_McAllester})
%%each applied with $\delta' = \delta/k$ we can choose the
%%best bound obtained (among the $k$)
%%such that the resulting bound holds with
%%probability at least $1-\delta$.
%
%\begin{theorem}[Multiple Priors]
%\label{thm:multi}
%Let the conditions of Theorem~\ref{thm:serfling_sqrt}
%hold, except that we now have $k$ prior distributions
%$\ppp_1,\ldots,\ppp_k$ defined over $\cH$, each of which may depend
%on $X_{m+u}$. Let $\delta \in (0,1)$ be given. Then, with
%probability at least $1-\delta$ over random choices of sub-samples
%of size $m$ from the full-sample, for all $h\in\cH$,
%\begin{equation*}
%R_h(X_{u}) \leq \hR_h(S_m) + \sqrt{
%\left(\frac{m+u}{u}\right) \left(\frac{u+1}{u}\right)
%\left(\frac{ \min_{1\le i \le k}
%\left\{ \ln\frac{1}{\ppp_i(h)} \right\} +\ln \frac{k}{\delta}
%}{2m} \right)}~.
%\end{equation*}
%\end{theorem}
%
%\begin{proof}
%The proof uses a standard ``multiple testing'' argument. Consider $k$
%applications of Theorem~\ref{thm:serfling_sqrt} such
%that each application is with $\delta'=\delta/k$ and the $i$th
%application uses $\ppp_i$ as prior. The complexity term in the bound
%corresponding to the $i$th prior is
%$$
%\sqrt{
%\left(\frac{m+u}{u}\right) \left(\frac{u+1}{u}\right)
%\left(\frac{
% \ln\frac{1}{\ppp_i(h)} +\ln \frac{k}{\delta}
%}{2m} \right)}.
%$$
%Each of the $k$ bounds holds with probability at least
%$1-\frac{\delta}{k}$ (and violated with probability at most
%$\frac{\delta}{k}$). Therefore, by the union bound the probability
%that at least one of these bounds is violated is at most $\delta$
%and the probability that they all hold is at least $1-\delta$ as
%required.
%\end{proof}
%
%\begin{remark}
%As noted by one of the reviewers, when the supports of the $k$ priors in
%Theorem~\ref{thm:multi} intersect (i.e. there is at least one pair of priors
%$\ppp_i$ and $\ppp_j$
%with overlapping support), then one can do better by utilizing the
%``super prior'' $\ppp = \frac{1}{k}\sum_i \ppp_i$ within the
%original Theorem~\ref{thm:serfling_sqrt}.
%However, note that when the supports are disjoint, these two
%views (of multiple priors and a super prior) are equivalent.
%\end{remark}
%
%====================================================================

\section{Bounds for Specific Algorithms}

PAC-Bayesian error bounds (both inductive and
transductive) are interesting because they provide a very simple
yet general formulation of learning. However, in order to provide
more concrete statements (e.g. about specific learning algorithms)
one must apply such bounds with some concrete priors (and
posteriors, in the case of Gibbs learning, see
Theorems~\ref{thm:McAllesterDKL_sqrt} and~\ref{thm:GibbsBinary}).
In the context of inductive learning, a major obstacle in deriving
effective bounds\footnote{Informally, we say that a bound is
``effective'' if its complexity term vanishes with $m$ (the size
of the training sample) and it is sufficiently small for
``reasonable'' values $m$.} using the PAC-Bayesian framework is
the construction of ``compact priors''. For example,
McAllester's generalization bound \cite{McA99} contains a
complexity term which includes a component of the form
$\ln(1/\ppp(h))$ where $\ppp$ is a prior over $\cH$ (as in
Theorem~\ref{thm:serfling_sqrt} and Corollary~\ref{cor:dembo}).
The more sophisticated inductive bounds for Gibbs classifiers
\cite{McA03,McAllester03b}
include a Kullback-Leibler (KL) divergence complexity component
$D(\qqq||\ppp)$, where $\ppp$ is a prior over $\cH$ and $\qqq$ is a
posterior over $\cH$ (as in Theorems~\ref{thm:McAllesterDKL_sqrt}
and~\ref{thm:GibbsBinary}). However, many hypothesis classes of
interest are very large and even uncountably infinite. Therefore,
despite the fact that these bounds apply in principle to very
large $\cH$, in a straightforward application of these
PAC-Bayesian bounds, when choosing priors with a very large
support (and possibly a posterior with a small support), the
complexity terms in these bounds can diverge or at least be too
large to form effective generalization bounds.\footnote{Saying
that we should also note that sophisticated prior choices within
the inductive PAC-Bayesian framework can also lead to
state-of-the-art bounds \cite{McAllester03b}.}

In contrast, the transductive framework provides a very
convenient setting for applying PAC-Bayesian
bounds. Here priors can be chosen after observing and analyzing
the full sample. As already mentioned, in the case of the 0/1-loss,
even if we consider a very
large hypothesis space $\cH$, after observing the full sample, the
effective size of equivalence classes of hypotheses in $\cH$ is
always finite and not larger than the number of dichotomies of the
full sample (see also Remark~\ref{rem:real-valued}).


In this section we present bounds for specific learning
algorithms. The first class of algorithms we consider in
Section~\ref{sec:compression} are ``compression schemes''. The
second class, are algorithms based on clustering. In both cases we
show how to form effective priors by considering
the structure of the full sample.



%In this section we apply our extended PAC-Bayesian technique and
%derive generalization bounds for bagging of kernel machines. As a
%direct corollary we also obtain a new data dependent bound on the
%generalization error of support vector machines given in terms of
%the \emph{observed} number of support vectors.
%
%We begin with a discussion of \emph{bagging}, which works as
%follows. We generate $T$ bootstrap samples (or ``replicas'')
%$B_1,\ldots,B_T$ from the training set $S$. Each bootstrap sample is
%generated by randomly and uniformly sampling with replacement $m$
%points from $S$. We train $T$ classifiers $h_j \in \cH$,
%$j=1,\ldots,T$, such that $h_j$ is trained using the sample $B_j$.
%Given a new point $x \in \cX$ we use the composite classifier
%$\textrm{sign}\left(\frac{1}{T}\sum_{j=1}^T h_j(x)\right)$ to
%predict its label. Thus, the aggregated classifier is simply a
%threshold applied to a uniform average of the base classifiers
%$h_j$. We call the resulting set of base classifiers $\{h_j \}$ the
%\emph{bagging ensemble} and denote the composite bagging classifier
%by $H^T$. For the rest of the paper we focus on base classifiers
%which are linear (kernel) machines and assume familiarity with the
%basics of support vector machine (SVM) induction. Thus, our
%hypothesis class $\cH$ is the set of all possible kernel machines
%(for some fixed kernel).
%
%Clearly, the cardinality of $\cH$ is uncountably infinite. The size
%of the bagging ensemble is not greater than $T$. It can be smaller
%than $T$ since two bootstrap samples $B_i$ and $B_j$ can give rise
%to identical kernel machines (in Section~\ref{sec:stability} we
%discuss this behavior and relate it to stability). Our goal now is
%to derive a generalization bound for $H^T$ using the PAC-Bayesian
%approach. Application of the ``standard''
%Theorem~\ref{thm:Mcallester} in this setting appears to be
%impossible: Any prior over $\cH$ that we choose will cause the
%KL-divergence to diverge. Instead we can rather easily construct a
%set of data dependent priors, each with finite support, and use
%Theorem~\ref{thm:second_revised_McAllester}.



\subsection{Bounds for Compression Algorithms}\label{sec:compression}
We propose a technique for selecting a prior $\ppp(h)$ over $\cH$,
based on the full (unlabeled) sample $X_{m+u}$. Given $m$,  the
learner constructs $m$ ``sub-priors'' $\ppp_{\tau}$, $\tau =
1,2,\ldots,m$, based on the full sample $X_{m+u}$, and for the
final prior, takes a uniform mixture of all these ``sub-priors''.

This technique generates transductive error bounds for ``compression''
algorithms.
Let $\cA$ be a learning algorithm.
%(viewed as a function from samples into some hypothesis class).
Intuitively, $\cA$ is a ``compression scheme''
if it outputs the same hypothesis using a subset of the
(labeled) training data.
\begin{definition}\label{def:compress}
A learning algorithm $\cA$ (viewed as a function from samples to
some hypothesis class) is a compression scheme with respect to a
sample $Z$ if there is a sub-sample $Z'$, $|Z'|< |Z|$, such that
$\cA(Z')=\cA(Z)$.
\end{definition}
Observe
that the Support Vector Machine (SVM) approach is a compression scheme,
where the set $Z'$ is determined by the set of support vectors.


%We begin
%with a simple assumption, which restricts the discussion to
%algorithms which uniquely determine a hypothesis $h\in\cH$ (given a
%fixed training set).
%\begin{assumption}\label{ass:unique}
%Any set of points $Z=\{(x_1,y_1),\ldots,(x_k,y_k)\}$ uniquely
%determines a classifier $h\in\cH$.
%\end{assumption}
%\rnote{Does uniqueness always hold for SVM? Need to verify this.}


%
%\begin{assumption}\label{ass:compress}
%The algorithm $A$ used is a compression scheme.
%\end{assumption}
%
Let $\cA$ be a deterministic compression scheme  and
consider the full sample $X_{m+u}$. For each integer
$\tau=1,\ldots,m$, consider all subsets of $X_{m+u}$ of size $\tau$,
and for each subset construct all possible dichotomies of that
subset (note that we are not proposing this approach as a useful
algorithm, but rather as a means to derive bounds;
in practice one need not construct all these dichotomies).
A deterministic algorithm $\cA$ generates at most one hypothesis $h\in\cH$
for each dichotomy.\footnote{It might be that for some dichotomies
the learning algorithm will fail to construct a classifier.
For example, a linear SVM in feature space without
``soft margin'' will fail to classify non linearly-separable dichotomies
of $X_{m+u}$.}
For each $\tau$, let the set of hypotheses
generated by this procedure be denoted by $\cH_\tau$.
For the rest of this discussion
we assume the worst case where $|\cH_\tau| = 2^{\tau}\binom{m+u}{\tau}$
(i.e. if $\cH_\tau$ does not contains one hypothesis for
each dichotomy the bounds we propose below improve).
The ``sub-prior''
$\ppp_\tau$ is then defined to be a uniform distribution over $\cH_\tau$.

In this way we have $m$ ``sub-priors'', $\ppp_1,\ldots,\ppp_m$, which are
constructed using only $X_{m+u}$ (and are independent of the
labels of the training set $Y_m$; also note that this construction
takes place before choosing the subset $X_m$). Any hypothesis
selected by the learning algorithm $\cA$ based on the labeled sample
$S_m$ and on the test set $X_u$ belongs to $\cup_{\tau=1}^m
\cH_\tau$. The motivation for this construction is as follows.
Each $\tau$ can be viewed as our ``guess'' for the maximal number
of compression points that will be utilized by a resulting
classifier. For each such $\tau$ the distribution $\ppp_\tau$ is
constructed over all possible classifiers that use $\tau$
compression points. By systematically considering all possible
dichotomies of $\tau$ points we can characterize a relatively
small subset of $\cH$ without observing labels of the training
points. Thus, each ``sub-prior'' $\ppp_\tau$ represents one such guess.
The final prior is
\begin{equation}
\label{eq:super-prior}
\ppp(h) = \frac{1}{m} \sum_{\tau=1}^m \ppp_{\tau}(h).
\end{equation}

%\begin{theorem}
%\label{thm:bagging_generalization}
%Let $S=(X,Y)$ be a training set drawn i.i.d. from $\mu$.
%For $\tau=2,\ldots,m$ let $\ppp_\tau$ be priors as defined above.
%Let $h_i$, $i=1,\ldots,T$ be the base classifiers generated
%using $T$ bootstrap replicas of $S$ (note that the $h_i$ are
%not necessarily distinct). Let $H^T$
%be the resulting composite bagging classifier and let $\qqq_H$
%to be the ``posterior'' distribution over $\{h_i\}$ where each
%$h_i$ is assigned a weight $1/T$.
%Then for any
%$\delta \in (0,1)$, with probability $1-\delta$ over choices of
%$S$,
%$$
%\ell(H^T) \leq 2\ellhat(H^T) + 2\sqrt{\frac{\min_\tau D(\qqq_H ||
%\ppp_\tau) + \ln(1/\delta) + 2\log m + 2}{2m -1}},
%$$
%\end{theorem}
%
%\begin{proof}
%Apply Theorem~\ref{thm:second_revised_McAllester}
%(and Lemma~\ref{lem:bayesian_factor_two}) with the
%priors $\ppp_2,\ldots,\ppp_m$ as defined above.
%$\Box$
%\end{proof}
%
%The bound of Theorem~\ref{thm:bagging_generalization}
%is data-dependent and the variable part of the bound
%(in addition to the empirical error term) is
%$\min_\tau D(\qqq_H || \ppp_\tau)$, which depends on the
%data. Later, in Section~\ref{sec:stability} we analyze the
%dependence of this KL-divergence factor on $T$ and the
%``stability'' of the base classifiers.

The following corollary is obtained by an application of
Theorem~\ref{thm:serfling_sqrt} using the prior $\ppp(h)$
in (\ref{eq:super-prior}). This results characterizes an
upper bound on the divergence in terms of the observed size of the
compression set of the final classifier.

%\rannote{The corollary should be revised and state the bound
%that follows from Theorem~\ref{thm:realizable_not_realizable}.
%Also, the bound that appears below (our previous general bound)
%should be stated in a remark after
%Theorem~\ref{thm:realizable_not_realizable}.}

\begin{corollary}[Transductive Compression Bound]
\label{cor:compress}
Let the conditions of Theorem \ref{thm:serfling_sqrt} hold.
Let $\cA$ be a deterministic learning algorithm leading to a
hypothesis $h\in\cH$ based on a compression set of size $s$. Then,
with probability at least $1-\delta$,
\begin{equation}
\label{eq:compression}
  R_h(X_{u}) \le \hat R_h(S_m) +
 \sqrt{
 \left(\frac{m+u}{u}\right)\left(\frac{u+1}{u}\right)
 \left(
 \frac{s\ln\left(\frac{2e(m+u)}{s}\right) + \ln(m/\delta))}{m}
 \right)
 }.
\end{equation}
\end{corollary}
\begin{proof}
Recall that $\cH_s \subseteq \cH$ is the support set of $\ppp_s$
and that $\ppp_s(h) = 1/|\cH_s|$ for all $h\in\cH_s$, implying that
$\ln(1/\ppp_s(h)) = |\cH_s |$. Using the inequality
$\binom{m+u}{s}\le (e(m+u)/s)^s$ we have that $|\cH_s | = 2^{s}
\binom{m+u}{s} \leq (2e(m+u)/s)^s$. Using the prior~(\ref{eq:super-prior})
and substituting $\ln(m/\ppp_s(h))$ in Theorem~\ref{thm:serfling_sqrt}
leads to the desired result.
\end{proof}

\begin{remark}
We can use Corollary~\ref{cor:dembo} to get a similar result,
which is sometimes tighter. Also note that compression bounds can
be easily stated and proved for Gibbs learning.
\end{remark}

The bound~(\ref{eq:compression})
can be easily computed
once the classifier is trained. If the size of the compression set
happens to be small, we obtain a tight bound.
We note that these bounds are applicable to the transductive SVM
algorithms discussed by \citeA{Vap98}, \citeA{BenDem98}
and \citeA{Joa99}. However,
our bounds motivate a different strategy than the one that drives
these algorithms; namely, reduce the number of support vectors!
(rather than enlarge the margin, as attempted by those algorithms).

Observe the conceptual similarity of our bound to Vapnik's bound for
consistent SVMs \cite<>[Theorem 5.2]{Vap95}, which bounds the
generalization error of an SVM by the ratio between the average
number of support vectors  and the sample size $m$. However,
Vapnik's bound can only be estimated while this bound is
truly data dependent. Finally, it is interesting to compare our
result to a recent inductive bound for compression schemes. In
this context, Graepel {\it et al.} \cite<see Theorem 5.18 in>{Her02}
have derived a bound of the form
\begin{equation}
\label{eq:compression_graepel}
    R(\textsf{SVM}) \leq \frac{m}{m-s}\hR(\textsf{SVM}) +
    \sqrt{\frac{s\log(2em/s) + \ln (1/\delta) + 2\ln m}{2(m-s)}},
\end{equation}
where $R(\textsf{SVM})$ and $\hR(\textsf{SVM})$ denote the true
and empirical errors, respectively, and $s$ is the number of
observed support vectors (over the training set).
%The bound (\ref{eq:compression_graepel}) is very similar to (\ref{eq:1SVM}), the main difference
%being in the factor $m/(m-s)$ multiplying the empirical error, and
%the factor of $2(m-s)$ instead of $2m-1$ in the denominator of the
%square root term. This difference may be substantial when the
%number of support vectors is large.
%A closer inspection of the bounds~(\ref{eq:compression}), (\ref{eq:1SVM})
%and~(\ref{eq:compression_graepel}) reveals that (\ref{eq:compression}) is
%tighter than (\ref{eq:compression_graepel}) when the number of
%compression points $s$ is very small and (\ref{eq:1SVM}) is tighter
%than (\ref{eq:compression_graepel}) when this number is very large
%but except for these extreme ends of the range, the inductive bound
%(\ref{eq:compression_graepel}) is tighter.

%Keep in mind, though, that the compression bound presented is more general
%than our bound based on the number of support vectors.

%\rannote{We should probably explicitly mention here that the
%bounds are applicable to the transductive SVM algorithms
%of Vapnik and Joachims.}

%\subsection{Ensemble Classifiers}\label{sec:consistent}
%
%We briefly mention an application of Theorem \ref{thm:McAllesterDKL}
%and its extension to multiple priors to the case of ensemble
%classifiers. Known aggregation algorithms such as bagging and
%boosting cannot be described as Gibbs classifiers but rather as
%\emph{Bayesian mixtures} over ensembles of base classifiers.
%Denoting by $B_\qqq$ such a mixture where $\qqq$ is a distribution
%over $\cH$, the classification of a new point $x$ by $B_\qqq$ is
%given by $B_\qqq(x) = \sgn\{\rE_{h\sim \qqq}[h(x)]\}$. That is, this
%composite classifier is deterministic and takes a thresholded
%(weighted) majority vote between its ensemble members.
%A simple modification of Lemma 5.3 in \cite{Her02} shows that
%$ R_{B_\qqq}(X_{m+u}) \le 2 R_{G_\qqq}(X_{m+u})$.
%%\begin{equation*}
%%  R_{B_\qqq}(X_{m+u}) \le 2 R_{G_\qqq}(X_{m+u}).
%%\end{equation*}
%Combining this result with Theorem \ref{thm:McAllester1_multi} leads
%to a bound on the error of the Bayes mixture algorithm. The only
%troublesome issue here is the factor of $2$ multiplying the error
%$\hat R_{G_\qqq}(S_m)$ in the bound.
%
%%However, using a construction
%%from \cite{ShaCri02} allows one to show that a proper design of the
%%kernel can guarantee that this term vanishes rapidly with the number
%%of iterations in Boosting and Bagging algorithms that use kernel
%%classifiers as base learners, and thus does not pose a major
%%concern. We defer discussion of this issue to the full paper.
%
%However, in some cases it is possible to ensure that the empirical
%error term in (\ref{thm:McAllesterDKL}) rapidly decreases to zero.
%As an example consider a bagging algorithm (\cite{breiman96})
%where each base classifier is trained on a bootstrap sub-sample of
%the training set. Using an SVM as a base classifier and utilizing
%a construction from \cite{ShaCri02} one can ensure that each base
%classifier is consistent with its bootstrap sample. For the
%bagging algorithm it is possible to prove that using consistent
%base classifiers the empirical error of the composite classifier
%decreases exponentially fast to zero with the size of the
%ensemble. We defer further discussion of this issue to the full
%paper.
%
%\begin{lemma}
%\label{lem:chernoff_one}
%Set $\eta = (1-\frac{1}{m})^m$ and
%let $H^T$ be the composite bagging classifier over the ensemble
%$\{ h_i \}$ based on the bootstrap samples $B_i$, $i=1,\ldots,T$.
%Then
%$$
%\ellhat(H^T) \leq 2e^{-2T(\eta-1/2)^2},
%$$
%\end{lemma}
%where $\eta = \eta_m= (1-\frac{1}{m})^m \to \frac{1}{e} \approx 0.368$
%is a probability of a particular point in $S$ not to appear in some
%bootstrap sample.
%
%\rnote{I think we have enough material without this section. If
%Phillip has time he can try incorporating the previous stuff
%(commented below). I think it's superfluous.}
%
%\ran{}{After removing all the color notes I think we have almost 1/2
% a page for that; Philip, if you can do that
%I think it would be good. Also, it may be important to highlight
%the bound on the SVM explicitly using a corollary. As it is now it can ``disappear''.}
%
%%In the case of classification, where $\ell$ is the zero-one loss (or
%%an upper bound on the zero-one loss), the following simple variation
%%of a result from \cite{Her02} can be used.
%%
%%\begin{lemma}[Herbrich and Graepel \cite{Her02}]
%%\label{lem:bayesian_factor_two} $R(B_\qqq) \leq 2 \ell(G_\qqq)$.
%%\end{lemma}
%%
%%In this section we use the result of Shawe-Taylor and Christianini
%%\cite{ShaCri02}, which guarantees that our (SVM) base classifiers
%%will be consistent with their training sets. Using this result we
%%improve the bounds of the previous section and essentially eliminate
%%the empirical error term of the composite bagging classifier.
%%
%The method proposed in \cite{ShaCri02} applies to kernel machines
%and uses a manipulation of the kernel matrix guaranteeing that after
%training the empirical error of the learned SVM is zero. Whenever
%this property holds we say that the classifier is \emph{consistent}
%with the training set. In effect, the method transforms a
%non-linearly separable problem into a separable problem by mapping
%the data into a higher dimensional space. Given a kernel $K(x,x')$
%we generate a modified kernel $K'$ via the following transformation
%to the kernel matrix $K' = K + \Delta^2 I$, where $\Delta>0$ should
%be optimized with respect to the data. A model based on this
%modified kernel can be optimized using standard algorithms for
%kernel machines. Moreover, it is shown in \cite{ShaCri02} that the
%resulting optimization problem is equivalent to optimization based
%on slack variables originally proposed for SVMs by Cortes and Vapnik
%\cite{CorVap95}.
%
%For sufficiently large $\Delta$ the resulting classifier is
%consistent with the training set. For such consistent classifiers a
%generalization error bound is provided in \cite{ShaCri02}. This
%bound, which is stated below, involves a complexity component given
%in terms of the distribution of margin values (rather than the
%minimum margin used in many other bounds). This property makes the
%bound more robust and can in principle compensate for the margins
%lost by the kernel transformation.
%
%%\begin{theorem}[Shawe-Taylor and Christianini \cite{ShaCri02}]
%%\label{thm:Shawe}
%%Fix $\Delta >0$. Consider a fixed but unknown distribution over
%%$\cX \times \pmone$ with support in the ball of radius $R$ about the
%%origin in $\cX$. Then, with probability $1-\delta$ over randomly drawn
%%training sets $S$ of size $m$, for all $\gamma >0$, the generalization
%%error of a linear classifier $\www$ on $\cX$, with $\| \www \| =1$
%%is bounded above by $\eps(m,d,\delta)=\max(\epsilon(m,d,\delta), 2/m)$,
%%where
%%$$
%%\epsilon(m,d,\delta) = \frac{2}{m}
%%\left(d \log_2\left( \frac{8em}{d}\right) \log_2(32m)
%%+ \log_2\left(\frac{8m}{\delta}\right)
%%\right),
%%$$
%%and where
%%\begin{align*}
%%d&=\left\lfloor
%%\frac{64.5(R^2+\Delta^2)(1+D(S\www,\gamma)^2/Delta^2}{\gamma^2}
%%\right\rfloor \\
%%D(S,\www,\gamma) &= \sqrt{\sum_{(x,y)\in S}
%%        (\max\{0,\gamma-yh_\www(x)\})^2} ~.
%%\end{align*}
%%\end{theorem}
%
%\paragraph{Remark.}
%The construction of \cite{ShaCri02} used for proving
%Theorem~\ref{thm:Shawe} relies on a data dependent mapping of the
%original problem into a higher dimensional space. In particular,
%this mapping depends on the labels of the training points. We note
%that our prior construction technique as described in
%Section~\ref{sec:bagging_bounds} accommodates this mapping since our
%construction relies on arbitrary (known) dichotomies of subsets of
%the training data.
%
%We now proceed with analysis of the empirical error of the composite
%bagging classifier. Recall that each of the base classifiers $h_i$,
%$i=1,\ldots,T$, is learned by training over the bootstrap sample
%$B_i$. Throughout this section we assume that our learning algorithm
%for classifiers in $\cH$ uses the above kernel manipulation
%technique and generates consistent base classifiers. The results of
%\cite{ShaCri02} guarantees that for any positive $\Delta$ the
%empirical error of $h_i$ over $B_i$ is zero while the generalization
%error of $h_i$ is bounded above by $\eps(m,d,\delta)$ (the reader is
%referred to \cite{ShaCri02} for further details).
%
%Nevertheless, each bootstrap sub-sample is a subset of the training
%sample $S$ and therefore, it is highly likely that there
%are points in $S$ which do not appear in every $B_i$. Consequently,
%the composite classifier $H^T$ can err on training points in $S$.
%Since $H^T$ decides via a majority vote between the base classifiers,
%$H^T$ can only err on a point $(x,y) \in S$ if a majority of the $T$
%bootstrap samples $B_1,\ldots,B_T$ do not include the point $(x,y)$.
%The probability that a particular point in $S$ will not appear in a
%bootstrap is sample is $\eta = \eta_m= (1-\frac{1}{m})^m \to
%\frac{1}{e} \approx 0.368$. Therefore, on average each bootstrap
%sample contains approximately $(1-\eta) m$ distinct points from $S$.
%As $1-\eta_m > 0.632$ for all $m>1$ we always have on average a
%majority of correct voters. The following simple large deviation
%lemma states that the empirical error of $H^T$ vanishes with $T$
%exponentially fast.
%
%\begin{lemma}
%\label{lem:chernoff_one}
%Set $\eta = (1-\frac{1}{m})^m$ and
%let $H^T$ be the composite bagging classifier over the ensemble
%$\{ h_i \}$ based on the bootstrap samples $B_i$, $i=1,\ldots,T$.
%Then
%$$
%\ellhat(H^T) \leq 2e^{-2T(\eta-1/2)^2}.
%$$
%\end{lemma}
%
%\begin{proof}
%Consider a particular training point $(x,y) \in S$. Let $Z$ be a
%random variable denoting the number of bootstrap samples which do
%not include $(x,y)$. Thus, $E[Z]=\eta T$ and by a Chernoff bound
%$$
%\Pr(|Z-\eta T| \geq \nu) \leq 2e^{-2\nu^2/T}.
%$$
%The classifier $H^T$ will err on $(x,y)$ if the majority
%of bootstrap samples do not include $(x,y)$ or in other words,
%if $Z < T/2$. Clearly, this happens if
%$\Pr(|Z-\eta T| \geq \nu)$ with
%$\nu \geq \eta T - T/2$, which proves the lemma.
%$\Box$
%\end{proof}
%
%Thus, by increasing the ensemble size we can ensure that
%the empirical error of the composite bagging classifier will rather
%quickly drop to zero.
%By utilizing the bound of Theorem~\ref{thm:Shawe}
%the following lemma provides a slightly stronger result
%giving a better vanishing rate for $\ellhat(H^T)$, which improves
%as a function of the sample size $m$.
%
%\begin{lemma}
%\label{lem:chernoff_two} Set $\eta = (1-\frac{1}{m})^m$ as before,
%let $\delta \in (0,1)$ be given and set $\eps = \eps(m,d,\delta)$ be
%the bound on the generalization error of each base classifier as
%given in Theorem~\ref{thm:Shawe}. Under the conditions of
%Theorem~\ref{thm:Shawe}, $\ellhat(H^T) \leq 2e^{-2T(\rho-1/2)^2}$
%where $\rho = \eta(1+(1-\eps)(1-\delta))$.
%\end{lemma}
%
%\begin{corollary}
%\label{cor:all_corollaries}
%The conclusions of Theorem~\ref{thm:bagging_generalization}
%and Corollaries~\ref{cor:bagging_generalization}
%and~\ref{cor:single_svm}
%hold with $2\ellhat(H^T)$ replaced by $4e^{-2T(\eta-1/2)^2}$.
%Under the conditions of Theorem~\ref{thm:Shawe},
%$2\ellhat(H^T)$ can be replaced by $4e^{-2T(\rho-1/2)^2}$
%($\rho$ is defined in Lemma~\ref{lem:chernoff_two}).
%\end{corollary}
%
%%====================================================================

%The technique developed in Section~\ref{sec:compression}
%is applicable in several interesting cases.
%Due to lack of space all the results in this section are
%sketched (details will be provided in the full paper).

%\par{\bf Ensemble Classifiers}
%We briefly mention an application of Theorem \ref{thm:McAllesterDKL}
%and its extension to multiple priors to the case of ensemble
%classifiers. Known aggregation algorithms such as bagging and
%boosting cannot be described as Gibbs classifiers but rather as
%\emph{Bayesian mixtures} over ensembles of base classifiers.
%Denoting by $B_\qqq$ such a mixture where $\qqq$ is a distribution
%over $\cH$, the classification of a new point $x$ by $B_\qqq$ is
%given by $B_\qqq(x) = \sgn\{\rE_{h\sim \qqq}[h(x)]\}$. That is, this
%composite classifier is deterministic and takes a thresholded
%(weighted) majority vote between its ensemble members.
%A simple modification of Lemma 5.3 in \cite{Her02} shows that
%$ R_{B_\qqq}(X_{m+u}) \le 2 R_{G_\qqq}(X_{m+u})$.
%%\begin{equation*}
%%  R_{B_\qqq}(X_{m+u}) \le 2 R_{G_\qqq}(X_{m+u}).
%%\end{equation*}
%Combining this result with Theorem \ref{thm:McAllester1_multi} leads
%to a bound on the error of the Bayes mixture algorithm. The only
%troublesome issue here is the factor of $2$ multiplying the error
%$\hat R_{G_\qqq}(S_m)$ in the bound.
%%However, using a construction
%%from \cite{ShaCri02} allows one to show that a proper design of the
%%kernel can guarantee that this term vanishes rapidly with the number
%%of iterations in Boosting and Bagging algorithms that use kernel
%%classifiers as base learners, and thus does not pose a major
%%concern. We defer discussion of this issue to the full paper.
%However, in some cases it is possible to ensure that the empirical
%error term in (\ref{thm:McAllesterDKL}) rapidly decreases to zero.
%As an example consider a bagging algorithm (\cite{breiman96})
%where each base classifier is trained on a bootstrap subsample of
%the training set. Using an SVM as a base classifier and utilizing
%a construction from \cite{ShaCri02} one can ensure that each base
%classifier is consistent with its bootstrap sample. For the
%bagging algorithm it is possible to prove that using consistent
%base classifiers the empirical error of the composite classifier
%decreases exponentially fast to zero with the size of the
%ensemble. We defer further discussion of this issue to the full
%paper.
%
%\begin{lemma}
%\label{lem:chernoff_one}
%Set $\eta = (1-\frac{1}{m})^m$ and
%let $H^T$ be the composite bagging classifier over the ensemble
%$\{ h_i \}$ based on the bootstrap samples $B_i$, $i=1,\ldots,T$.
%Then
%$$
%\ellhat(H^T) \leq 2e^{-2T(\eta-1/2)^2},
%$$
%\end{lemma}
%where $\eta = \eta_m= (1-\frac{1}{m})^m \to \frac{1}{e} \approx 0.368$
%is a probability of a particular point in $S$ not to appear in some
%bootstrap sample.

%In the case of classification, where $\ell$ is the zero-one loss (or
%an upper bound on the zero-one loss), the following simple variation
%of a result from \cite{Her02} can be used.
%
%\begin{lemma}[Herbrich and Graepel \cite{Her02}]
%\label{lem:bayesian_factor_two} $R(B_\qqq) \leq 2 \ell(G_\qqq)$.
%\end{lemma}
%
%In this section we use the result of Shawe-Taylor and Christianini
%\cite{ShaCri02}, which guarantees that our (SVM) base classifiers
%will be consistent with their training sets. Using this result we
%improve the bounds of the previous section and essentially eliminate
%the empirical error term of the composite bagging classifier.
%
%The method proposed in \cite{ShaCri02} applies to kernel machines
%and uses a manipulation of the kernel matrix guaranteeing that after
%training the empirical error of the learned SVM is zero. Whenever
%this property holds we say that the classifier is \emph{consistent}
%with the training set. In effect, the method transforms a
%non-linearly separable problem into a separable problem by mapping
%the data into a higher dimensional space. Given a kernel $K(x,x')$
%we generate a modified kernel $K'$ via the following transformation
%to the kernel matrix $K' = K + \Delta^2 I$, where $\Delta>0$ should
%be optimized with respect to the data. A model based on this
%modified kernel can be optimized using standard algorithms for
%kernel machines. Moreover, it is shown in \cite{ShaCri02} that the
%resulting optimization problem is equivalent to optimization based
%on slack variables originally proposed for SVMs by Cortes and Vapnik
%\cite{CorVap95}.
%
%For sufficiently large $\Delta$ the resulting classifier is
%consistent with the training set. For such consistent classifiers a
%generalization error bound is provided in \cite{ShaCri02}. This
%bound, which is stated below, involves a complexity component given
%in terms of the distribution of margin values (rather than the
%minimum margin used in many other bounds). This property makes the
%bound more robust and can in principle compensate for the margins
%lost by the kernel transformation.
%
%%\begin{theorem}[Shawe-Taylor and Christianini \cite{ShaCri02}]
%%\label{thm:Shawe}
%%Fix $\Delta >0$. Consider a fixed but unknown distribution over
%%$\cX \times \pmone$ with support in the ball of radius $R$ about the
%%origin in $\cX$. Then, with probability $1-\delta$ over randomly drawn
%%training sets $S$ of size $m$, for all $\gamma >0$, the generalization
%%error of a linear classifier $\www$ on $\cX$, with $\| \www \| =1$
%%is bounded above by $\eps(m,d,\delta)=\max(\epsilon(m,d,\delta), 2/m)$,
%%where
%%$$
%%\epsilon(m,d,\delta) = \frac{2}{m}
%%\left(d \log_2\left( \frac{8em}{d}\right) \log_2(32m)
%%+ \log_2\left(\frac{8m}{\delta}\right)
%%\right),
%%$$
%%and where
%%\begin{align*}
%%d&=\left\lfloor
%%\frac{64.5(R^2+\Delta^2)(1+D(S\www,\gamma)^2/Delta^2}{\gamma^2}
%%\right\rfloor \\
%%D(S,\www,\gamma) &= \sqrt{\sum_{(x,y)\in S}
%%        (\max\{0,\gamma-yh_\www(x)\})^2} ~.
%%\end{align*}
%%\end{theorem}
%
%\paragraph{Remark.}
%The construction of \cite{ShaCri02} used for proving
%Theorem~\ref{thm:Shawe} relies on a data dependent mapping of the
%original problem into a higher dimensional space. In particular,
%this mapping depends on the labels of the training points. We note
%that our prior construction technique as described in
%Section~\ref{sec:bagging_bounds} accommodates this mapping since our
%construction relies on arbitrary (known) dichotomies of subsets of
%the training data.
%
%We now proceed with analysis of the empirical error of the composite
%bagging classifier. Recall that each of the base classifiers $h_i$,
%$i=1,\ldots,T$, is learned by training over the bootstrap sample
%$B_i$. Throughout this section we assume that our learning algorithm
%for classifiers in $\cH$ uses the above kernel manipulation
%technique and generates consistent base classifiers. The results of
%\cite{ShaCri02} guarantees that for any positive $\Delta$ the
%empirical error of $h_i$ over $B_i$ is zero while the generalization
%error of $h_i$ is bounded above by $\eps(m,d,\delta)$ (the reader is
%referred to \cite{ShaCri02} for further details).
%
%Nevertheless, each bootstrap sub-sample is a subset of the training
%sample $S$ and therefore, it is highly likely that there
%are points in $S$ which do not appear in every $B_i$. Consequently,
%the composite classifier $H^T$ can err on training points in $S$.
%Since $H^T$ decides via a majority vote between the base classifiers,
%$H^T$ can only err on a point $(x,y) \in S$ if a majority of the $T$
%bootstrap samples $B_1,\ldots,B_T$ do not include the point $(x,y)$.
%The probability that a particular point in $S$ will not appear in a
%bootstrap is sample is $\eta = \eta_m= (1-\frac{1}{m})^m \to
%\frac{1}{e} \approx 0.368$. Therefore, on average each bootstrap
%sample contains approximately $(1-\eta) m$ distinct points from $S$.
%As $1-\eta_m > 0.632$ for all $m>1$ we always have on average a
%majority of correct voters. The following simple large deviation
%lemma states that the empirical error of $H^T$ vanishes with $T$
%exponentially fast.
%
%\begin{lemma}
%\label{lem:chernoff_one}
%Set $\eta = (1-\frac{1}{m})^m$ and
%let $H^T$ be the composite bagging classifier over the ensemble
%$\{ h_i \}$ based on the bootstrap samples $B_i$, $i=1,\ldots,T$.
%Then
%$$
%\ellhat(H^T) \leq 2e^{-2T(\eta-1/2)^2}.
%$$
%\end{lemma}
%
%\begin{proof}
%Consider a particular training point $(x,y) \in S$. Let $Z$ be a
%random variable denoting the number of bootstrap samples which do
%not include $(x,y)$. Thus, $E[Z]=\eta T$ and by a Chernoff bound
%$$
%\Pr(|Z-\eta T| \geq \nu) \leq 2e^{-2\nu^2/T}.
%$$
%The classifier $H^T$ will err on $(x,y)$ if the majority
%of bootstrap samples do not include $(x,y)$ or in other words,
%if $Z < T/2$. Clearly, this happens if
%$\Pr(|Z-\eta T| \geq \nu)$ with
%$\nu \geq \eta T - T/2$, which proves the lemma.
%$\Box$
%\end{proof}
%
%Thus, by increasing the ensemble size we can ensure that
%the empirical error of the composite bagging classifier will rather
%quickly drop to zero.
%By utilizing the bound of Theorem~\ref{thm:Shawe}
%the following lemma provides a slightly stronger result
%giving a better vanishing rate for $\ellhat(H^T)$, which improves
%as a function of the sample size $m$.
%
%\begin{lemma}
%\label{lem:chernoff_two} Set $\eta = (1-\frac{1}{m})^m$ as before,
%let $\delta \in (0,1)$ be given and set $\eps = \eps(m,d,\delta)$ be
%the bound on the generalization error of each base classifier as
%given in Theorem~\ref{thm:Shawe}. Under the conditions of
%Theorem~\ref{thm:Shawe}, $\ellhat(H^T) \leq 2e^{-2T(\rho-1/2)^2}$
%where $\rho = \eta(1+(1-\eps)(1-\delta))$.
%\end{lemma}
%
%\begin{corollary}
%\label{cor:all_corollaries}
%The conclusions of Theorem~\ref{thm:bagging_generalization}
%and Corollaries~\ref{cor:bagging_generalization}
%and~\ref{cor:single_svm}
%hold with $2\ellhat(H^T)$ replaced by $4e^{-2T(\eta-1/2)^2}$.
%Under the conditions of Theorem~\ref{thm:Shawe},
%$2\ellhat(H^T)$ can be replaced by $4e^{-2T(\rho-1/2)^2}$
%($\rho$ is defined in Lemma~\ref{lem:chernoff_two}).
%\end{corollary}

%\par{\bf Transductive Learning via Clustering}

\subsection{Transductive Learning via Clustering}
\label{sec:clustering}

Some learning problems do not allow for
high compression rates using compression schemes such
as SVMs \shortcite<i.e. the number of support vectors can sometimes
be very large, see e.g.>[Table 1]{BaramEL03}.
A considerably stronger type of compression
can often be achieved by clustering algorithms.
While there is lack of formal links between
entirely unsupervised clustering and classification,
within a transductive setting we can provide a principled
approach to using clustering algorithms for classification.

In particular, we propose the following approach: The learner
applies a clustering algorithm (or a number of clustering
algorithms) over the unlabeled data to generate several
(unsupervised) models. The learner then utilizes the labeled data
to guess labels for entire clusters (so that all points in the
same cluster have the same label). In this way, a number
of hypotheses are generated, one of which is then selected based
on a PAC-Bayesian error bound for transduction, applied with an appropriate
prior.

The natural idea
of first clustering the unlabeled data and then assigning labels
to clusters has been around for a long time and there are plenty
of heuristic procedures that attempt to learn using this approach
within a semi-supervised or transductive settings
\cite<see, e.g., >[Sec. 2.1]{seeger02learning}. However, to the best of
our knowledge, none of the existing procedures was theoretically
justified in terms of provable reduction of the true risk. In
contrast, the clustering-based transduction method we propose here
relies on a solid theoretical ground.

Let $\cA$ be any (deterministic) clustering algorithm which, given
the full sample $X_{m+u}$, can cluster this sample into any desired
number of clusters. We use $\cA$ to cluster $X_{m+u}$ into
$1,\ldots,c$ clusters where $c\le m$.  Thus, the algorithm
generates a collection of partitions of $X_{m+u}$ into
$\tau=1,2,\ldots,c$ clusters, where each partition is denoted by
$C_\tau$. For each value of $\tau$, let $\cH_\tau$ consist of those
hypotheses which assign an identical label to all points in the same
cluster of partition $C_{\tau}$, and define the ``sub-prior''
$\ppp_\tau(h)=1/2^\tau$ for each $h\in\cH_\tau$ and zero otherwise
(note that there are $2^\tau$ possible dichotomies).
The final prior is a uniform mixture of all these sub-priors,
$\ppp(h) = \frac{1}{c} \sum_{\tau} \ppp_{\tau}(h)$.

The learning
algorithm selects a hypothesis as follows. Upon observing the
labeled sample $S_m=(X_m,Y_m)$, for each of the clusterings
$C_1,\ldots,C_c$ constructed above, it assigns a label to each cluster
based on the majority vote from the labels $Y_m$ of points falling
within the cluster (in case of ties, or if no points from $X_m$
belong to the cluster, choose a label arbitrarily). Doing this leads
to $c$ classifiers $h_\tau$, $\tau=1,\ldots,c$.
We now apply Theorem~\ref{thm:serfling_sqrt} with the above prior
$\ppp(h)$ and can choose the
classifier (equivalently, number of clusters) for which the best
bound holds. We thus have the following corollary of
Theorem~\ref{thm:serfling_sqrt}.

\begin{corollary}
\label{cor:clustering}
Let $\cA$ be any clustering
algorithm and let $h_\tau$, $\tau = 1,\ldots,c$ be classifications of
the test set $X_u$ as determined by clustering of the full
sample $X_{m+u}$ (into $\tau$ clusters)
and the training set $S_m$, as described above.
Let $\delta \in (0,1)$ be given.
Then, with probability at least $1-\delta$ over choices of $S_m$
the following bound holds for all $\tau$,
\begin{equation}\label{eq:full_bound}
% R_{h_\tau}(X_{u}) \leq \hR_{h_\tau}(S_{m}) + \left(\frac{m+u}{u}\right)
R_{h_\tau}(X_{u}) \leq \hR_{h_\tau}(S_{m}) +
     \sqrt{
     \left(\frac{m+u}{u}\right)\left(\frac{u+1}{u}\right)
     \left(\frac{\tau+ \ln \frac{c}{\delta}}{2m}
     \right)}
 \end{equation}
\end{corollary}
\noindent
\textbf{Remark:} Note that when $m=u$ we get the bound
$$
R_{h_\tau}(X_{u}) \leq \hR_{h_\tau}(S_{m}) +
     \sqrt{
     \frac{\left(1+\frac{1}{m}\right)\left(\tau+ \ln \frac{c}{\delta}\right)}{m}
     }.
$$
Also, in the case of the 0/1 loss we can use
Corollary~\ref{cor:dembo} to obtain significantly faster rates in
the realizable case or when the training error is very small. We
see that these bounds can be rather tight when the clustering
algorithm is successful (e.g. when it captures the class structure
in the data using a small number of clusters). Note however, that
in practice one can significantly benefit by the faster
rates that can be achieved utilizing Vapnik's implicit bounds presented in
Section~\ref{sec:Vapnik_implicit} (or the bound of Blum and Langford,
\citeyearR{BlumL03}).
Clearly, any PAC-Bayesian bound for transduction can
be plugged-in within this scheme and tighter bounds should
yield better performance.


Corollary~\ref{cor:clustering} can be extended in a number of ways.
One simple extension is the use of an \emph{ensemble} of clustering algorithms.
Specifically, we can concurrently apply $k$ different clustering algorithms
(using each algorithm to cluster the data into $\tau=1,\ldots,c$ clusters).
We thus obtain $kc$ hypotheses (partitions of $X_{m+u}$).
By a simple application of the union bound we can replace
$\ln \frac{c}{\delta}$ by $\ln \frac{kc}{\delta}$
in
Corollary~\ref{cor:clustering} and guarantee that
$k$ bounds hold simultaneously for all the $k$ clustering algorithms
(with probability at least $1-\delta$). We thus choose the hypothesis which
minimizes the resulting bound.\footnote{A better approach to combine
the $k$ clustering algorithms, especially if we expect
that some of the algorithms will generate identical
clusterings, is to construct one ``big'' prior for all of them.}
This extension is particularly attractive since
typically without prior knowledge we do not know
which clustering algorithm will be effective for the
dataset at hand.


To conclude this section we note that \citeA{ElyanivG04}
recently
%and \cite{BanerjeeL04}
presented empirical studies of the above
clustering approach. These empirical evaluations on a variety of
real world datasets demonstrate the effectiveness of
the proposed approach.

%\subsection{Transductive Learning via Clustering}
%
%Let $A$ be any (deterministic) clustering algorithm which, given the
%full sample $X_{m+u}$, can cluster this sample into
%any desired number of clusters. We use $A$ to cluster
%$X_{m+u}$ into $2,3\ldots,c$ clusters
%where $c\le m$.  Thus, the algorithm generates a collection of
%partitions of $X_{m+u}$ into $\tau=2,3,\ldots,c$ clusters, where
%each partition is denoted by $C_\tau$. For each value of $\tau$, let
%$\cH_\tau$ consist of those hypotheses which assign an identical
%label to all points in the same cluster of partition $C_{\tau}$, and define the prior
%$\ppp_\tau(h)=1/2^\tau$ for each $h\in\cH_\tau$ and zero otherwise
%(note that there are $2^\tau$ possible dichotomies).
%
%The learning algorithm selects a hypothesis as follows. Upon
%observing the labeled sample $S_m=(X_m,Y_m)$, for each of the
%clusterings $C_2,\ldots,C_c$ constructed above, assign a label
%to each cluster based on the majority vote from the labels $Y_m$ of
%points falling within the cluster (in case of ties, or if the no
%points from $X_m$ belong to the cluster, choose a label
%arbitrarily). Doing this leads to $c-1$ classifiers. For each of these
%classifiers there is a valid error bound as given by
%Theorem~\ref{thm:McAllester1_multi} and all these bounds are
%valid simultaneously.
%Thus we choose the best
%classifier (equivalently, number of clusters) for which the best bound holds.
%For example if we choose the classifier which was constructed from the
%clustering into $16$ clusters, the complexity term for this cluster
%is $\log(2^{16}) = 16$. Therefore, if our clustering algorithm is effective,
%we can get a tight performance guarantee for its errors on the test set.
%
%Some possible extensions include the following. {\it (i)} Determine
%the value of $c$ before-hand. For example, there is no use in
%considering partitions into $c=m$ clusters because their complexity
%terms will be $\log(2^m) = m$ and our error bound will be useless.
%Given $m$ and a desired error bound (say 10\%) we can calculate the
%complexity term for each $c=2,3,...$ until we get a complexity which
%is larger than 10\% and stop there. {\it (ii)} We can concurrently use
%an ensemble of $N$ different clustering algorithms (in
%which case we get an additional $\log(N)$ in the complexity term).

%====================================================================



%\section{Some Extensions}
%\label{sec:stochastic_target}
%
%\rannote{In this section we should discuss a number of extensions:
%\begin{itemize}
%\item
%Stochastic targets
%\item
%General loss functions
%\item
%Non-binary problems (multi-class)
%\item
%Extensions of the basic bounds to uncountable hypothesis classes?
%\end{itemize}
%}
%====================================================================
\section{Concluding Remarks}

We presented general explicit PAC-Bayesian bounds for
transductive learning. We also developed a new prior construction
technique which effectively derives tight data-dependent error
bounds for compression schemes and for transductive learning
algorithms based on clustering.

With the exception of Theorem~\ref{thm:serfling_sqrt}, which holds
for any bounded loss function,
all our transductive error bounds were presented within the simplest binary
classification setting (i.e. with the 0/1-loss function and
with non-stochastic labels). However, these results can be easily extended
to multi-class problems and to stochastic
labels.
We hope that these bounds and the prior construction technique
will be useful as a starting point for deriving error bounds for other known
algorithms and for developing new types of transductive learning algorithms.

We emphasize, however, that in the case of classification (i.e.
the 0/1 loss), implicit but tighter error bounds for transduction
were already known (e.g. Vapnik's result as stated in
Corollary~\ref{cor:vapnik_relative}). Our bounds are
explicit and can therefore be useful for interpreting and
characterizing  the functional dependency on the problem
parameters.

%\rmnote{I would remove the next sentence. Let the work
%speak for itself} As far as we know, in the case of general
%bounded loss functions (e.g. regression) and the transductive
%Gibbs algorithm, our error bounds are the first general results
%for the transductive setting.

In applications, when using compression schemes or our
clustering-based transduction approach,
%, as described in Section~\ref{sec:clustering},
one can plug-in any other
PAC-Bayesian transductive bound (implicit or explicit). For example, one can benefit
by using the tighter Vapnik bound. In
\cite{ElyanivG04} and \cite{BanerjeeL04}, the authors
present empirical studies of the clustering approach of Section~\ref{sec:clustering}
by plugging in the Vapnik implicit bound and the similar
implicit bound from \cite{BlumL03}, respectively.
These empirical studies indicate that the proposed clustering-based transductive scheme
can lead to state-of-the-art algorithms.

An interesting feature of any transduction error bound for Setting
1, is that it holds for ``individual samples''; that is, the full
sample $X_{m+u}$ need not be sampled i.i.d. from a
distribution and moreover, in this setting one cannot assume that
it is sampled from a fixed distribution at all! Therefore, results
for this setting must hold for any given sample. In this sense,
the transductive bounds within Setting 1 are considerably more
robust than standard bounds in the inductive setting.


%It would
%be interesting to see if tighter transduction bounds can be obtained by reducing the
%``slack'' in the inequalities we use in our analysis.
%One particular slack that
%may be reduced in some cases is the one introduced by Lemma~\ref{lem:hoeffding}. While in the
%worst case this inequality holds as an equality,
%it might be possible to provide a
%tighter inequality in particular cases by better exploiting the fact that in
%transduction we generate the training set $S_m$ by sampling \emph{without replacement}.
%Alternatively, instead of utilizing bounds for sums of independent
%variables (e.g. binomial distribution) as we do here, one can directly consider
%bounds for tails of hypergeometric distributions (which are the resulting
%distributions when sampling without replacements). See for example
%the hypergeometric tail bound of \citet{Chvatal79}.
%

\noindent
We conclude with some open questions and research
directions.
\begin{enumerate}
\item
All our results are obtained within Vapnik's ``Setting 1'' of
transduction, which must consider any arbitrary choice of the full
sample. Considering Theorem~\ref{thm:vapnik_1_2} and
Remark~\ref{rem:setting2}, it would be interesting to see
if tighter results are possible within the probabilistic Setting
2.
\item
An interesting direction for future research could be the
construction of more sophisticated priors. For example, in our
compression bound (Corollary~\ref{cor:compress}), for each number
$s$ of compression points we assigned the same prior to each
dichotomy of every $s$-subset. However, in practice, when
there is structure in the data, the vast majority of all these
subsets and dichotomies cannot ``explain'' the data and should not
be assigned a large prior.
\item
The bounds derived in this paper are based on a contribution from
the deviation of a single hypothesis and a utilization of the
union bound in the PAC-Bayesian style. More refined approaches,
for example those based on McDiarmid's inequality \cite{McD89}
and the entropy method \cite{BouLugMas03}, are able to eliminate
the union bound altogether. It would be interesting to see if such
approaches can lead to tighter bounds in the current setting.
\item
When considering arbitrary (bounded) loss functions, the
basic observation for transduction (due to Vapnik) that the
effective cardinality of the hypothesis class (in the case of
classification) is finite, is not necessarily valid. However, it is
likely that one can still benefit from the availability of the
full sample. One possible approach, mentioned in
Remark~\ref{rem:real-valued}, would be to construct an empirical
$\epsilon$-cover of $\cH$ based on the $\ell_1$ norm.
\item
Finally, we note that the major challenge, of determining a precise
relation between the inductive and transductive learning schemes
remains open.
Of particular interest would be to determine the relation between
the inductive \emph{semi-supervised} setting (where the learner is also given a
set of unlabeled points, but is required to induce an hypothesis for the
entire space) and transduction.
Our bounds suggest that transduction does not allow
for learning rates that are faster than induction (as a function of
$m$). On the other hand, it appears that the bounds we obtain for clustering-based
transduction can be tighter than any known bound for a specific
inductive learning effective algorithm.
\end{enumerate}


\section*{Acknowledgments}
The work of Ran El-Yaniv and Ron Meir was partially
supported by the Technion V.P.R. fund for the promotion of sponsored
research and the partial support of the PASCAL network of excellence.
Support from the Ollendorff center of the department of
Electrical Engineering at the Technion is also acknowledged. We also
thank anonymous referees and Dmitry Pechyony for their useful comments.





%====================================================================
%\newpage
\begin{appendix}

\section{Proof of Theorem \ref{thm:vapnik_two_models}}

\begin{proof}
The
proof we present is identical to Vapnik's original proof and is
provided for the sake of self-completeness. Let $\cA$ be some learning
algorithm choosing an hypothesis $h_{\cA} \in \HHH$ based on $S_m \cup
X_u$. Define
\begin{align*}
C_{\cA}(x_1,y_1;\ldots;x_{m+u},y_{m+u}) &= \left| \frac{1}{m}
\sum_{i=1}^m \ell\left(y_i,h_{\cA}(x_i)\right) - \frac{1}{u}
\sum_{j=m+1}^{m+u} \ell\left(y_i,h_{\cA}(x_i)\right) \right| \\
 &= \left| R_{h_{\cA}}(X_m) - R_{h_{\cA}}(X_u) \right|.
\end{align*}
Consider Setting 2. The probability that $C_{\cA}$ deviates from zero by
an amount greater than $\veps$ is
$$
P = \int_{\XXX,\YYY} \bI(C_{\cA} - \veps) d \mu(x_1,y_1)\cdots d
\mu(x_{m+u},y_{m+u}),
$$
where $\bI$ is an indicator step function, $\bI(x)=1$ iff $x>0$ and
$\bI(x)=0$ otherwise. Let $\cT_p$, $p=1,\ldots,(m+u)!$ be the
permutation operator for the sample
$(x_1,y_1);\ldots;(x_{m+u},y_{m+u})$. It is not hard to see that
$$
P = \int_{\XXX,\YYY} \left\{ \frac{1}{(m+u)!} \sum_{p=1}^{(m+u)!}
\bI\left(C_{\cA}(\cT_p(x_1,y_1;\ldots;x_{m+u},y_{m+u})) - \veps\right)
\right\} d \mu(x_1,y_1)\cdots d \mu(x_{m+u},y_{m+u}).
$$
The expression in curly braces is the quantity estimated in Setting
1 and by our assumption, for any choice of the full sample, it does
not exceed $\delta$. Therefore,
$$
P \leq \int_{\XXX,\YYY} \delta d \mu(x_1,y_1)\cdots d
\mu(x_{m+u},y_{m+u}) = \delta.
$$
\end{proof}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{theorem}
%\label{thm:trans_sharper2} Let $\cH$ be a class of binary
%classifiers. Under the conditions of
%Theorem~\ref{thm:serfling_sqrt}, with probability at least
%$1-\delta$, for any $h \in \cH$,
%$$
%R_h(X_{m+u}) \leq \hR_h(S_m) +
%  \left(\frac{m+u}{u}\right)\sqrt{\frac{
%  C(m,u,\ell_h) \cdot \left(\ln\frac{1}{p(h)} + \ln\frac{1}{\delta}\right)
%  +2(m+u+2)}
%  {
%  2m^2(m+u+2)
%  }},
%$$
%where
%$$
%C(m,u,\ell_h)
%= \min \left\{
%\begin{array}{l}
%  (m+1)(u+1),\\
%  (\ell_h+1) (m+u-\ell_h+1),\\
%\end{array}
%\right\},
%$$
%and $\ell_h = (m+u)R_h(X_{m+u})$.
%\end{theorem}
%
%\section{Proof of Corollary~\ref{cor:hush}}
%\begin{proof}
%According to Theorem~\ref{thm:trans_sharper}, applied
%with   $C(m,u,\ell_h)=(\ell_h+1) (m+u-\ell_h+1)$
%and $m=u$ (and recalling that
%$\lambda_h = \log\frac{1}{p(h)} + \log\frac{1}{\delta}$), we have
%\begin{equation}
%\label{eq:cor_start}
%R_h(X_{u})
%\leq
%\hR_h(S_m) +
%  2\sqrt{\frac{
%  C(m,m,\ell_h) \lambda_h +2(2m+2)}
%  {
%  2m^2(2m+2)
%  }}.
%\end{equation}
%Clearly, when $m=u$,
%\begin{align*}
%\ell_h &=(m+u)R_h(X_{m+u}) \\
%&=m\hR_h(S_m)+uR_h(X_u)\\
%&=m\left(\hR_h(S_m)+R_h(X_u)\right),
%\end{align*}
%and therefore,
%\begin{align*}
%C(m,m,\ell_h) &=(\ell_h+1)(2m-\ell_h+1)\\
%&= \left(m\left(\hR_h(S_m)+R_h(X_u)\right)+1\right)
% \left(2m-m\left(\hR_h(S_m)+R_h(X_u)\right)+1\right).
%\end{align*}
%Plugging in this expression of $C(m,m,\ell_h)$
%in (\ref{eq:cor_start}) we get
%
%\medskip
%\noindent
%$
%R_h(X_u)\leq \hR_h(S_m)+
%2\sqrt{\frac{\left(m(\hR_h(S_m)+R_h(X_u))+1\right)
%\left(2m-m(\hR_h(S_m)+R_h(X_u))+1\right)\lambda_h+2(2m+2)}{%
%2m^{2}(2m+2)}}.
%$
%\medskip
%
%\noindent
%Denoting $R_u=R_h(X_u)$,
%with straightforward but tedious algebraic manipulation
%we get
%\begin{align}
%f(R_u)&=
%R_u^{2}\frac{m+\lambda_h+1}{m+1}
%-R_u\frac{2(m\hR_h(S_m)+\hR_h(S_m)+\lambda_h-\lambda_h \hR_h(S_m))}{m+1}
%\nonumber \\
%&\ \ \ \ +\frac{\hR_h(S_m)(m\hR_h(S_m)+\hR_h(S_m)-2\lambda_h+\lambda_h \hR_h(S_m))}
%{m+1}- \frac{\lambda_h(1+2m)+4(m+1)}{m^{2}\left( m+1\right) }\leq 0.
%\label{eq:quadratic}
%\end{align}
%The parabola $f(R_u)$ is upright and has two roots $z_1 < z_2$.
%Clearly, if $f(R_u) \leq 0$ then $R_u \leq z_2$.
%It is not hard to see that
%\begin{align*}
%z_2 =
%\hR_h(S_m) &+\frac{\lambda_h(1-2\hR_h(S_m))}{m+\lambda_h+1}\\
%&+ \frac{\sqrt{(m+1)\left(
%4 \lambda_h m^{2}\hR_h(S_m)(1-\hR_h(S_m))+m(2\lambda_h+\lambda_h^{2}+4)
%+\lambda_h^{2}+5\lambda_h+4\right) }}{\left( m+\lambda_h + 1\right) m}.
%\end{align*}
%%A straightforward expression of the root is:
%%$\frac{1}{2\left( m+1+L\right) }\frac{2m^{2}S+2Lm+2mS-2mLS+2\sqrt{\left(
%%4+4m^{2}+8m+5L+2Lm^{2}-4Lm^{3}S^{2}+4m^{3}SL+7Lm+L^{2}m^{2}+L^{2}+2L^{2}m-4Lm^{2}S^{2}+4Lm^{2}S\right)
%%}}{m}$
%\end{proof}

%---------------------------------------------------------------------

%\section{Proof of Lemma~\ref{lem:hoeffding}}
%For convenience we state the lemma once more here.
%Let $\cC = \{c_1,\ldots,c_N\}$ be a finite set containing $N$ elements, and let
%$Z_1,\ldots,Z_m$ be a random sample \textbf{with replacement} from
%$\cC$ and $X_1,\ldots,X_m$ a random sample
%\textbf{without replacement} from $\cC$. Then, for any continuous and convex
%real-valued function $f(x)$, $ \rE f\left( \sum_{i=1}^m X_i \right)
%\leq \rE f\left( \sum_{i=1}^m Z_i \right).$
%
%The proof we provide below is an adaptation of the proof of Theorem~4
%in \citep{Hoe63}.
%
%\begin{proof}
%For any positive integer $m \leq N$,
%denote by $\sub_m(N)$ the set of all $m$-subsets of $\{1,\ldots,N\}$.
%We first observe that for an arbitrary function $g$ of
%$m$ variables we have,
%\begin{align}
%U = \rE g(X_1,\ldots,X_m) &=
%\frac{1}{N(N-1)\cdots(N-m+1)}
%\sum_{\{i_1,\ldots,i_m\} \in \sub_m(N)} g(c_{i_1},\ldots,c_{i_m});
%\label{eq:U}\\
%W = \rE g(Z_1,\ldots,Z_m) &=
%\frac{1}{N^m} \sum_{1\leq i_1,\ldots,i_m \leq N}
%g(c_{i_1},\ldots,c_{i_m}). \label{eq:W}
%\end{align}
%A central observation is that $W$ can be written as $U$ with $g$
%replaced by $g^*$ where $g^*$ is some weighted sum of values of
%$g$. That is,
%$$
%\rE g(Z_1,\ldots,Z_m) = \rE g^*(X_1,\ldots,X_m).
%$$
%For example, if $m=2$ then
%\begin{equation}
%\label{eq:g_star_2}
%g^*(x_1,x_2) = \frac{N-1}{N}g(x_1,x_2) +
%\frac{1}{N}g(x_1,x_1),
%\end{equation}
%and clearly
%\begin{align*}
%\rE g(Z_1,Z_2) &= \frac{1}{N^2}\sum_{1\leq i_1,i_2 \leq N}g(c_{i_1},c_{i_2}) \\
%&= \frac{1}{N^2}\sum_{\{i_1,i_2\} \in \sub_2(N)}
%\left(g(c_{i_1},c_{i_2}) + \frac{1}{N-1} g(c_{i_1},c_{i_1} \right) \\
%&=\frac{1}{N(N-1)} \sum_{\{i_1,i_2\} \in \sub_2(N)}
%\left\{\frac{N-1}{N}g(c_{i_1},c_{i_2}) + \frac{1}{N}g(c_{i_1},c_{i_1}) \right\}\\
%&= \rE g^*(X_1,X_2).
%\end{align*}
%As a second example, when $m=3$
%\begin{align*}
%g^*(x_1,x_2,x_3) &=
%\frac{(N-1)(N-2)}{N^2}g(x_1,x_2,x_3) +
%    \frac{N-1}{N^2} \left\{ g(x_1,x_1,x_2) + g(x_1,x_2,x_1) + g(x_2,x_1,x_1)
%                    \right\}\\
%                   & \ \ \ \ \  + \frac{1}{N^2}g(x_1,x_1,x_1).
%\end{align*}
%To describe the general structure of $g^*$, let
%$p(m,k)$ be the number of partitions of a number $m$ into $k$
%positive parts. Each such partition $(r_1,\ldots,r_k)$ satisfies
%$\sum_{i=1}^k r_i = m$ and $1 \leq r_i \leq m$. Note that each
%partition is a \emph{multiset} (e.g. the partitions $\{2,2,3\}$
%and $\{2,3,2\}$ of $7$ are identical).
%Denote by $P_{m,k}$ the set of all these partitions
%(i.e. $|P_{m,k}| = p(m,k)$).\footnote{Despite extensive
%research, no closed form for $p(m,k)$ is known.
%It can be shown that $p(m,k) = p(m-1, k-1) + p(m-k,k)$
%with $p(m,k)=0$ if $k > m$, $p(m,m)=p(m,1) = 1$ and $p(m,0)=0$.
%The ID of the sequence $p(m,k)$ is A008284
%in \emph{Sloane's Encyclopedia of Integer Sequences};
%see more details at
%\texttt{http://www.research.att.com/$\sim$njas/sequences/index.html}.}
%
%In general, the function $g^*$ is a summation which has the following terms.
%For each $k = 1,\ldots,m$, and for each
%$\{r_1,\ldots,r_k\} \in P_{m,k}$
%the summation has a term of the following form
%$$
%\frac{N(N-1)\cdots(N-k+1)}{N^m}
%\left(
%\overbrace{g(\underbrace{c_{i_1},\ldots,c_{i_1}}_{r_1},\ldots,\underbrace{c_{i_k},\ldots,c_{i_k}}_{r_k})
%+ \ldots +
%g(\underbrace{c_{i_k},\ldots,c_{i_k}}_{r_k},\ldots,\underbrace{c_{i_1},\ldots,c_{i_1}}_{r_1})
%}^{\mbox{$\binom{m}{r_1,\ldots,r_k}$ terms}}\right),
%$$
%where the summation in the parenthesis contains all
%$\binom{m}{r_1,\ldots,r_k} = \frac{m!}{r_1 ! \cdots r_k !}$
%distinct arrangements of $k$ ``types'' of indices with
%multiplicities $r_1, \ldots, r_k$.
%We emphasize that the coefficients and number of terms are
%independent of $g$.
%
%Let $I$ be minimal real closed interval
%containing the sum of any $m$ elements from $\cC$.
%Let $f$ be any continuous and convex function over $I$.
%We take $g(x_1,\ldots,x_m) = f(\sum_i x_i)$ and now consider
%the specialization of $g^*$ to this case.
%However,
%note that the above representation of $g^*$ is not unique.
%For example, we can write
%$g^*(x_1,x_2) = \frac{N-1}{N}g(x_1,x_2) +
%\frac{1}{N}\left(\frac{1}{2}g(x_1,x_1) + \frac{1}{2}g(x_2,x_2)\right)$
%instead of the version given by (\ref{eq:g_star_2}).
%To complete the proof we
%consider a version $\gbar$ of $g^*$, which is symmetric in
%$x_1,\ldots,x_m$. It is possible to show that
%$\gbar$ is unique can be written in the following form
%\begin{equation}
%\label{eq:g_bar}
%\gbar(x_1,\ldots,x_m) =
%\sum_{\begin{array}{c}
%  k=1,\ldots,m \\
%  r_1+\cdots+r_k =m \\
%  (i_1,\ldots,i_k) \in \sub_k(1,\ldots,m)
%\end{array}}
%p(k,r_1,\ldots,r_k,i_1,\ldots,i_k)f\left(\sum_{j=1}^k r_j x_{i_j}\right),
%\end{equation}
%where $r_i$ are positive integers and the coefficients $p$
%are positive and do not depend on $f$. Clearly, for all $f$ it holds
%that
%\begin{equation}
%\label{eq:f_gbar}
%\rE f(Z_1+\cdots+Z_m) = \rE \gbar(X_1,\ldots,X_m).
%\end{equation}
%By taking $f(x) = 1$ and considering (\ref{eq:g_bar}) and
%(\ref{eq:f_gbar}), we have
%\begin{equation}
%\label{eq:the_p}
%\sum p(k,r_1,\ldots,r_k,i_1,\ldots,i_k) = 1.
%\end{equation}
%On the other hand, if $f(x)=x$ then $\gbar$ is a linear
%function of $x_1,\ldots,x_m$ and since $\gbar$ is symmetric, it follows
%that $\gbar(x_1,\ldots,x_m) = K\cdot (x_1+\cdots+x_m)$ where
%$K$ is some constant. It is not hard to see that
%$\rE(Z_1+\cdots + Z_m) = \rE(X_1 + \cdots + X_m)$.
%Therefore, using (\ref{eq:f_gbar})
%$\rE(X_1+\cdots + X_m) = \rE \gbar(X_1,\ldots,X_m)
%= K\cdot\rE (X_1+\cdots + X_m)$ and therefore $K=1$.
%It follows that
%\begin{equation}
%\label{eq:f_x}
%p(k,r_1,\ldots,r_k,i_1,\ldots,i_k)f\left(\sum_{j=1}^k r_j x_{i_j}\right)
%= x_1 + \cdots + x_m.
%\end{equation}
%If $f(x)$ is continuous and convex (in $I$), since the sum of the
%$p$ coefficients is 1, we can apply Jensen's inequality and get
%$\gbar(x_1,\ldots,x_m) \geq f(x_1+\cdots + x_m)$.
%Therefore, using (\ref{eq:f_gbar}) we have
%$$
%\rE f(Z_1+\cdots+Z_m) = \rE \gbar(X_1,\ldots,X_m) \geq \rE f(X_1+\cdots + X_m).
%$$
%\end{proof}
%
%



%where the sum $\sum'$ is taken over the positive integers
%$k=1,\ldots,m$, $r_1+\cdots+r_k =m$
%and $(i_1,\ldots,i_k) \in \sub_k(1,\ldots,m)$




%\section{A Lemma used to prove Theorem \ref{thm:McAllesterDKL}}
%
%\begin{lemma}\label{lem:dkl}
%For each $h \in \cH$ and training set $S_m$ let $\Delta_h(S_m) =
%|R_h(X_{m+u}) - \hR_h(S_m)|$. Let $\ppp$ be any distribution over
%$\cH$ and let $\delta \in (0,1)$ be given. Then, with probability at
%least $1 - \delta$ over the random choices of $S_m$ from the full
%sample
%\begin{equation}
%\rE_{h \sim P} \exp \left( {(2m-1)\Delta_h(S_m)^2} \right) \leq
%\frac{4m}{\delta} \label{eq:second McAllester lemma}
%\end{equation}
%\end{lemma}
%
%\begin{proof}
%We prove that
%\begin{equation}
%\rE_{\Sigma_m} \rE_{h \sim \ppp} \exp \left( {(2m-1)\Delta(h,
%S_m)^2} \right) \leq 4m, \label{eq:second McAllester lemma before
%Markov}
%\end{equation}
%where the outer expectation is taken with respect to all choices of
%$S_m$ from the full sample $X_{m+u}$ (i.e. $S_m = (X_m, Y_m)$ and
%$X_m$ is sampled from $X_{m+u}$ uniformly at random without
%replacements).
%%in the following way: (i)
%%choose uniformly $X_m$ from $X_{m+u}$; (ii) assign labels $Y_m$ to the $X_m$
%%using the $\phi(x)$ function (or a probability measure as in Section
%%\ref{sec:probabilistic_target}),
%Then by Markov inequality,
%\begin{equation}
%\Pr_{\Sigma_m} \{ Z \geq t \} \leq \frac{\rE_{\Sigma_m} X}{t},
%\label{eq:markov}
%\end{equation}
%the proof of the lemma is complete by taking $t = \frac{4m}{\delta}$
%and $Z = \rE_{h \sim \ppp} \exp{( {(2m-1)\Delta_h(S_m)^2} )}$.
%Specifically, assuming that (\ref{eq:second McAllester lemma before
%Markov}) is valid and using (\ref{eq:markov}),
%$$
%\Pr_{\Sigma_m}\lc Z \geq \frac{4m}{\delta}\rc \leq
%\frac{\rE(Z)\delta}{4m} \leq \frac{4m \delta}{4m} = \delta.
%$$
%It remains to prove (\ref{eq:second McAllester lemma before
%Markov}). This will be established if we prove that for $h \in \cH$
%\begin{equation}
%\rE_{\Sigma_m} \exp \left( {(2m-1)\Delta_h(S_m)^2} \right) \leq 4m,
%\label{eq:intermidiate_target}
%\end{equation}
%and then take expectation over random choices $h \sim \ppp$.
%
%It remains to prove (\ref{eq:intermidiate_target}). As shown in the
%proof of Theorem~\ref{thm:sqrt}, $\rE_{S_m} \hR_h(S_m) =
%R_h(X_{m+u})$. Applying Lemma~\ref{lem:hoeffding} we thus have
%\begin{equation}
%\Pr_{\Sigma_m} \left\{\Delta_h(S_m)  \geq t \right\} \leq 2 \exp
%\left(-2mt^2 \right). \label{eq:Delta Chernoff}
%\end{equation}
%Fix any $h$. If we show that
%inequality~(\ref{eq:intermidiate_target}) holds for the ``worst
%possible'' distribution (the one for which (\ref{eq:Delta Chernoff})
%holds with equality), then (\ref{eq:intermidiate_target}) is valid.
%Abbreviate $\Delta = \Delta_h(S_m)$ and consider a density function
%$f(\Delta)$ that maximizes the left-hand side of
%(\ref{eq:intermidiate_target}) subject to the constraint
%(\ref{eq:Delta Chernoff}). This distribution satisies
%$$
%\int_x^\infty f(\Delta) d\Delta = 2 \exp (-2mx^2),
%$$
%which gives $f(\Delta) = 8m\Delta \exp(-2m\Delta^2)$. Using this
%distribution we can now explicitly calculate the left-hand side of
%(\ref{eq:intermidiate_target}),
%\begin{align*}
%\rE_{\Sigma_m} \exp \left( {(2m-1)\Delta_h(S_m)^2} \right) &\leq
%\int_0^\infty \exp\left((2m-1)\Delta^2 \right) f(\Delta) d\Delta\\
%& = \int_0^\infty \exp \left( (2m-1)\Delta^2 \right) 8m\Delta
%\exp(-2m\Delta^2) d\Delta\\
%&=
%8m \int_0^\infty \Delta \exp( - \Delta^2 ) d\Delta\\
%&= 4m.
%\end{align*}
%\end{proof}

\end{appendix}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

%\section{Probabilistic Targets}
%\label{sec:probabilistic_target}
%Here we consider the more daunting case where the labels are the probabilistic function of the
%sample. An important distinction to make is that for the traning error
%definition remains a deterministic one, as the true labels for $S_m$ are chosen.
%Define:
%\begin{equation}
%L_h(S_m, X_u) = \frac{\left( m\widehat{R}_h(S_m) + uR_h(X_u) \right)}{m+u},
%\label{eq:L definition}
%\end{equation}
%notice, however, that the equation (\ref{full_risk}) still holds in the
%probabilistic case.
%\begin{lemma}
%Suppose that for an $h \in \cal{H}$ the following bound holds with probability
%at least $1-\delta - \exp{(-2m\epsilon^2)}$ for any $\delta \in (0,1)$
%over the random choices of the training set from the full sample and
%for any $\epsilon > 0$ over the choices of the $Y_m$ given $X_m$:
%\begin{equation}
%R_h(X_{m+u}) < \widehat{R}_h (S_m) + C(h, S_m, \delta),
%\label{eq:probabilistic_assumption}
%\end{equation}
%for some complexity term $C(h, S_m, \delta)$. Then
%\begin{equation}
%R_h(X_u) <
%\widehat{R}_h (S_m) + \alpha C(h, S_m, \delta) + {m\over{u}} \exp{(-2m\epsilon^2)}
%\label{eq:probabilistic_lemma}
%\end{equation}
%\label{lem:probabilistic_lemma}
%\end{lemma}
%
%\begin{proof}
%Here is why.
%Using (\ref{full_risk}) and (\ref{eq:probabilistic_assumption})
%we have
%\[
%\frac{m R_h(X_{m}) + uR_h(X_u)}{m+u} < \widehat{R}_h (S_m) + C(h, S_m, \delta),
%\]
%isolating $R_h (X_u)$ at the left side we have:
%\begin{equation}
%R_h (X_u) < {{m+u}\over{u}} \widehat{R}_h (S_m) + {{m+u}\over{u}} C(h, S_m,
%\delta) - {m\over{u}} R_h(X_m)
%\label{eq:probabilistic_lemma_middle}
%\end{equation}
%\[
%R_h (X_u) <
%{m\over{u}} (\widehat{R}_h (S_m) - R_h(X_m)) + \widehat{R}_h(S_m)
%+ {{m+u}\over{u}} C(h, S_m, \delta).
%\]
%
%Now we show that $E_{Y_m| X_m} \hR_h (S_m) = R_h (X_m)$. From the definitions
%of both:
%\[
%E_{Y_m| X_m} \hR_h (S_m) = E_{Y_m| X_m} \frac{1}{m} \sum_{i=1}^{m} \ell(h(x_i),y_i) =
%\frac{1}{m} \sum_{i=1}^{m} E_{y| x_i} \ell(h(x_i),y_i) = R_h(X_m).
%\]
%Therefore, we can use the Chernoff bound to limit the value of
%$\widehat{R}_h (S_m) - R_h(X_m)$:
%the probability of $\widehat{R}_h (S_m) - R_h(X_m) > \epsilon$ is smaller than
%$\exp{(-2m\epsilon^2)}$. Notice that we are interested in one direction only
%(when $\widehat{R}_h (S_m)$ is larger than $R_h(X_m)$, thus there is no absolute
%value and no factor of $2$ in the Chernoff bound) and we get the lemma
%(\ref{eq:probabilistic_lemma}).
%
%\end{proof}
%
%
%
%


%\begin{small}
%\bibliographystyle{unsrt}
%\bibliography{transduction}
%\bibliography{C:/Technion/Papers/biblio}

%\end{small}


\bibliography{biblio}
\bibliographystyle{theapa}

\end{document}
