\documentclass[12pt]{article} %\usepackage[T1]{fontenc} %\usepackage{colt99e,times} \usepackage{fullpage} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \newtheorem{thm}{Theorem}[section] \newtheorem{defn}[thm]{Definition} \makeatother \newcommand{\comment}[1]{} \newcommand{\numex}{m} \newcommand{\numfeat}{n} \newcommand{\meas}{\mu} \newcommand{\sfrac}[2]{{\textstyle \frac{#1}{#2}}} \begin{document} \title{Microchoice Bounds and Self Bounding Learning Algorithms} \author{ {\bf John Langford} and {\bf Avrim Blum} \\ Computer Science Department \\ Carnegie Mellon University\\ Pittsburgh, PA 15213 \\ \{jcl+,avrim+\}@cs.cmu.edu \\ } \maketitle \begin{abstract} A major topic in machine learning is to determine good upper bounds on the true error rates of learned hypotheses based upon their empirical performance on training data. In this paper, we demonstrate new adaptive bounds designed for learning algorithms that operate by making a sequence of choices. These bounds, which we call Microchoice bounds, are similar to Occam-style bounds and can be used to make learning algorithms self-bounding in the style of Freund \cite{F98}. We then show how to combine these bounds with Freund's query-tree approach producing a version of Freund's query-tree structure that can be implemented with much more algorithmic efficiency. \end{abstract} \section{Introduction} Sample complexity bounds tend to be too loose for application to real world learning problems using common learning algorithms. They require more examples than experimentally necessary to guarantee a reasonable accuracy with a reasonable probability. Chief amongst the reasons for this failure is that typical sample complexity bounds are worst-case in nature and do not take into account what may turn out to be a fortunate target function and/or data distribution. A tighter bound can perhaps be derived by taking properties of the observed data into account. Many learning algorithms work by an iterative process in which they take a sequence of steps each from a small set of choices (small in comparison to the overall hypothesis set size). Local optimization algorithms such as hill-climbing or simulated annealing, for example, work in this manner. Each step in a local optimization algorithm can be viewed as making a choice from a small set of possible steps to take. If we take into account the number of choices made and the size of each choice set, can we produce a tighter bound? We develop a bound we call the Microchoice bound, which is a natural approach to analyzing algorithms of this form and lends itself to the construction of Self bounding Learning algorithms in the style of Freund \cite{F98} in a straightforward way. The goal is to allow algorithms to bound the difference between the true and empirical errors of the output hypothesis based on the choices actually taken and the choice sets actually explored without needing to consider sets that ``might have been'' visited for different learning problems. By keeping track of the sizes of the choice sets visited, the bound can be calculated and output along with the answer. The simpler version of the Microchoice bound, which we describe first, can be thought of as a direct application of the Occam's razor connection developed by \cite{BEHW87}. In particular, the idea is to use the learning algorithm itself to define a description language for hypotheses, so that the description length of the hypothesis actually produced gives a bound on the estimation error. In the second half of this paper, we show how the Microchoice bound can be combined with the query-tree approach of Freund to produce a variant of the query tree that can be used much more efficiently. The idea here is to use empirical properties of the sample to prune away unlikely choices. For example, in decision tree learning, if the sample is such that one choice of root node test is highly preferred to all the rest, we may be able to formally act almost as if those other choices never existed (see Section \ref{sec:adaptive} for a fuller description of this example). Our procedures work without altering the final hypothesis produced by the learning algorithm. It is also possible to modify the learning algorithm to use a current bound in order to implement early stopping in a manner similar to that of dynamic Structural Risk Minimization \cite{SBWA96}. The structure of this paper is as follows. We begin in Section 2 with some background on standard bounds, and use this to provide motivation for our approach. Section 3 contains a simpler version of the Microchoice bound, which can be viewed as a warmup to our main result in Section 4 that combines this idea with Freund's Query-tree approach. We then discuss the relationship between some of these methods in Sections 5 and 6. Self bounding Learning algorithms were first suggested by Freund \cite{F98}. Work developing approximately Self Bounding Learning algorithms was also done by Domingos \cite{D98}. \section{Discrete PAC Bound Review} %%The initial framework will follow the setup of the standard PAC model %%with notation revised for easy extension into the Microchoice learning %%model. The basic PAC model is characterized by a hypothesis set, \( H \), composed of hypotheses, \( h:X\rightarrow Y \). We will be considering only discrete sets $H$. The learning algorithm is given \( \numex \) labeled examples $(x_1,y_1), \ldots, (x_\numex, y_\numex)$ generated according to an unknown distribution $P$ over the instance-label product space $X \times Y$. We will call the set of labeled examples $z^\numex = \{z_1, \ldots, z_\numex\}$, where $z_i = (x_i, y_i)$. Let $E_P(h) \equiv \Pr_{(x,y)\sim P}(h(x)\neq y)$ denote the true error of some hypothesis $h$ with respect to $P$, and let $E(h,z^\numex) \equiv \Pr_{(x,y)\sim z^\numex}(h(x)\neq y) $ denote $h$'s empirical error on the sample.\footnote{We are using $\Pr_{x\sim D}(\phi(x))$ to denote the probability $\phi$ holds for a random $x$ chosen from $D$.} In the realizable setting, we assume there exists some $h\in H$ with $E_P(h) = 0$. In this setting we typically wish to state that with high probability no hypothesis of high true error will have zero empirical error. %%Let $\Pr_{z^\numex \sim P^\numex} \left[ \phi(z^\numex) \right]$ be the %%probability that $\phi$ holds over the sample set. The standard result, using the union bound, is that for any $P$, for any $\delta>0$, \begin{equation} \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H: E(h,z^\numex) = 0 \mbox{ and } E_{P}(h) > \epsilon \right] < \delta, \mbox{ \ \ for } \epsilon = \frac{1}{\numex}\left(\ln \frac{|H|}{\delta }\right). \label{eqn:simple} \end{equation} A folk result, stated explicitly as Preliminary Theorem~1 in \cite{M98}, is that one can weight the hypotheses in H according to any probability measure $\meas$, resulting in different error bounds for different hypotheses. In particular, one way to think of the standard bound above is that we take our ``supply'' of confidence, $\delta$, and split it evenly among the hypotheses, giving $\delta/|H|$ to each. Then we define $\epsilon$ so that the probability a fixed hypothesis of true error $\epsilon$ has empirical error 0 on $\numex$ examples is at most $\delta/|H|$. The generalization is simply that we can allocate our supply of $\delta$ according to any distribution $\meas$ if we wish, giving $\delta(h) = \delta \cdot \meas(h)$ to each. We then define $\epsilon(h)$ so that the probability a hypothesis of true error $\epsilon(h)$ has empirical error 0 on $\numex$ examples is at most $\delta(h)$, and apply the union bound. Specifically, \begin{thm} (Realizable Folk Theorem \cite{M98}) For any $\delta > 0$, any $P$, and any measure $\meas$ over $H$, \begin{equation} \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H: E(h,z^\numex) = 0 \mbox{ and } E_{P}(h)>\epsilon(h)\right] < \delta, \mbox{ \ for \ } \epsilon(h) = \frac{1}{\numex}\left(\ln \frac{1}{\delta }+\ln \frac{1}{\meas(h)}\right) \label{eqn:realizable} \end{equation} \end{thm} For example, the Occam's razor connection observed by \cite{BEHW87} can be viewed in this framework by giving every hypothesis of description length $l$ a weight of $\meas(h)=2^{-2l}$. In the agnostic case, where the empirical error can be any value rather than only zero, we wish to bound the deviation between the true and empirical errors of any hypothesis. The same trick of unevenly spreading the confidence $\delta$ over the hypotheses, combined with Hoeffding bounds, produces the following result stated explicitly as Preliminary Theorem 2 in \cite{M98}. \begin{thm} (Agnostic Folk Theorem \cite{M98}) For any $\delta > 0$, any $P$, and any measure $\meas$ over $H$, $$ \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H :E_{P}(h)> E(h,z^{\numex}) + \epsilon(h)\right] < \delta, $$ $$\mbox{\ for \ } \epsilon(h) = \sqrt{\frac{1}{2\numex}\left(\ln \frac{1}{\delta }+\ln \frac{1}{\meas(h)}\right)} $$ \end{thm} \subsection{A Motivating Observation}\label{sec:motivating} For a given learning algorithm $A$, a distribution $P$ on labeled examples induces a distribution $p(h)$ over the possible hypotheses $h \in H$ produced by algorithm $A$ after $\numex$ examples\footnote{$p(h)$ is the probability over draws of examples and any internal randomization of the algorithm.}. If we knew $P$, then we could apply the Realizable Folk Theorem with the measure $\meas(h) = p(h)$. This choice of \( \meas(h) \) is optimal for minimizing the expected value of our true error bound, \( \epsilon (h) \). In particular, notice that \[ \inf_m \sum _{h\in H}p(h)\frac{1}{\numex}\left(\ln \frac{1}{\delta }+\ln \frac{1}{\meas(h)}\right) \] \[ = \frac{1}{\numex}\left(\ln \frac{1}{\delta }+\inf_m \sum _{h\in H}p(h)\ln \frac{1}{\meas(h)}\right)\] This corresponds to minimizing the Kullback-Liebler divergence which provides a solution of \( \meas(h)=p(h) \). Interestingly, for the agnostic bound this choice of measure, \( \meas(h)=p(h) \), does not minimize the expected value of \( \epsilon (h) \), as can be seen from a quick analysis of the two hypothesis case. Instead, this choice of measure minimizes the expected value of \( \epsilon (h)^{2} \). \[ \inf _m \sum _{h\in H}p(h)\epsilon (h)^{2} = \inf _m \sum _{h\in H}p(h)\frac{1}{2\numex}(\ln \frac{1}{\delta }+\ln \frac{1}{\meas(h)})\] From here, the analysis is the same as for the realizable case. The point of these observations is to notice that if we can use the structure of the learning algorithm to produce a choice of \( \meas(h) \) that approximates \( p(h) \), this should result in better estimation bounds. \section{The Basic Microchoice Bound} \label{sec:mc} \comment{Informally, the Microchoice bound is an \emph{a~posteriori} bound based upon the following reasoning. ``I have an \emph{a~priori} bound on the true error in mind, but I do not have the means to compute it explicitly. What I can do is run the learning algorithm on the data available, and based upon the trace of the algorithm, compute a bound on the \emph{a~priori} quantity.''} The Microchoice bound is essentially a natural measure \( \meas(h) \) for learning algorithms that operate by making a series of small choices. In particular, consider a learning algorithm that works by making a sequence of choices, \( c_{1},...,c_{d} \), from a sequence of choice sets, \( C_{1},...,C_{d} \), finally producing a hypothesis, \( h\in H\). Specifically, the algorithm first looks at the choice set $C_1$ and the data $z^\numex$ to produce choice $c_1 \in C_1$. The choice $c_1$ then determines the next choice set $C_2$ (different initial choices produce different choice sets for the second level). The algorithm again looks at the data to make some choice $c_2 \in C_2$. This choice then determines the next choice set $C_3$, and so on. These choice sets can be thought of as nodes in a {\em choice tree}, where each node in the tree corresponds to some internal state of the learning algorithm, and a node containing some choice set $C$ has branching factor $|C|$. Depending on the learning algorithm, subtrees of the overall tree may be identical. We address optimization of the bound for this case later. Eventually there is a final choice leading to a leaf, and a single hypothesis is output. For example, the decision list algorithm of Rivest \cite{Rivest87} applied to examples over $n$ features uses the data to choose one of $4n+2$ rules (e.g., ``if $\bar{x}_3$ then $-$'') to put at the top. Based on the choice made, it moves to a choice set of $4n-2$ possible rules to put at the next level (e.g., ``if $x_1$ then $+$''), then a choice set of size $4n-6$, and so on, until eventually it chooses a rule such as ``else $+$'' leading to a leaf. The way we determine $\meas(h)$ (equivalently, $\delta(h)$) for the basic Microchoice bound is as follows. We take our ``supply'' of $\delta$ and give it to the root of the choice tree. The root takes its supply and splits it equally among all its children. Recursively, each child then does the same: it takes the supply it is given and splits it evenly among its children, until all of the supplied confidence parameter is allocated among the leaves. If we examine some leaf containing a hypothesis $h$, we see that this method gives it $\delta(h) = \delta \prod _{i=1}^{d(h)}\frac{1}{|C_{i}(h)|}$, where $d(h)$ is the depth of $h$ in the choice tree and $ C_1(h), C_2(h), \ldots, C_{d(h)}(h)$ is the sequence of choice sets traversed on the path to $h$. Equivalently, we allocate $\meas(h) = \prod _{i=1}^{d(h)}\frac{1}{|C_{i}(h)|}$ measure to each $h$. Note it is possible that several leaves will contain the same hypothesis $h$, and in that case one should really add the allocated measures together. However, we will neglect this issue, implying that the Microchoice bound will be loose for learning algorithms that can arrive at the same hypothesis in multiple ways. The reason for neglecting this is that we want $\meas(h)$ to be something the learning algorithm itself can calculate by simply keeping track of the sizes of the choice sets it has encountered so far. It is important to notice that this construction is defined before observing any data. Consequently, every hypothesis has some bound associated with it before the data is used to pick a particular hypothesis and its corresponding bound. Another way to view this process is that we cannot know in advance which choice sequence the algorithm will make. However, a distribution $P$ on labeled examples induces a probability distribution over choice sequences, inducing a probability distribution $p(h)$ over hypotheses. Ideally we would like to use $\meas(h) = p(h)$ in our bounds as noted above. However, we cannot calculate \( p(h) \), so instead, our choice of \( \meas(h) \) will be just an estimate. In particular, our estimate $\meas(h)$ is the probability distribution resulting from picking each choice uniformly at random from the current choice set at each level (note: this is different from picking a final hypothesis uniformly at random). I.e., it can be viewed as the measure associated with the assumption that at each step, all choices are equally likely. We immediately find the following theorems. \comment{ We will neglect the possibility that multiple sequences of choices can lead to the same hypothesis, implying that the Microchoice bound will be unnecessarily loose for learning algorithms which can arrive at the same hypothesis in multiple ways. In fact, for ease of notation we will associate each hypothesis $h$ with the sequence of choice sets $C_1 = C_1(h), C_2(h), \ldots, C_{M(h)}(h)$ used in reaching i. Then we will choose \(\meas(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \). %% If there are multiple sequences which arrive at \( h \), use the %% sequence which minimizes \( \prod _{m=1}^{M}\frac{1}{|C_{m}|} \). } \begin{thm}\label{thm:rmt} (Realizable Microchoice Theorem) For any \( \delta \in (0,1) \), %% and the measure \( \meas(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \) %%over hypothesis set, \( H \), \[ \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H: E(h,z^\numex) = 0 \mbox{ and } E_{P}(h)> \epsilon(h) \right]<\delta \] \[ \mbox{ \ for \ } \epsilon(h) = \frac{1}{\numex}\left(\ln \frac{1}{\delta }+\sum _{i=1}^{d(h)}\ln |C_{i}(h)|\right) \] \end{thm} \noindent {\bf Proof.} Specialization of the Realizable Folk Theorem. \begin{thm}\label{thm:amt} (Agnostic Microchoice Theorem) For any \( \delta \in (0,1) \), %% and the measure \( \meas(h)=\prod _{m=1}^{M(h)}\frac{1}{|C_{m}(h)|} \) %% over the hypothesis set, \( H \), \[ \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H:E_{P}(h)>E(h,z^{\numex})+ \epsilon(h)\right] < \delta \] \[ \mbox{ \ for \ } \epsilon(h) = \sqrt{\frac{1}{2\numex}\left(\ln \frac{1}{\delta} + \sum_{i=1}^{d(h)}\ln |C_{i}(h)|\right)} \] \end{thm} \noindent {\bf Proof.} Specialization of the Agnostic Folk Theorem. The point of these Microchoice bounds is that the quantity $\epsilon(h)$ is something the algorithm can calculate as it goes along, based on the sizes of the choice sets encountered. Furthermore, in many natural cases, a ``fortuitous distribution and target concept'' corresponds to a shallow leaf or a part of the tree with low branching, resulting in a better bound. For instance, in the Decision List case, $\sum_{i=1}^{d(h)}\ln |C_{i}(h)|$ is roughly $d \log \numfeat$ where $d$ is the length of the list produced and $\numfeat$ is the number of features. Notice that $d \log \numfeat$ is also the description length of the final hypothesis produced in the natural encoding, thus in this case these theorems yield similar bounds to Occam's razor or SRM. \comment{ \subsection{decision list} Consider the process of learning a decision list. At step \( i \) in the algorithm, the possible choices for the next variable come from the set of features which have not yet been used, giving a choice set of size \( \numfeat-i \). If the decision list stops at some preset length, \( M \), the error output in the agnostic case will be: \emph{ \[ E(h^{l},z^{\numex})+\sqrt{\frac{1}{2\numex}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln (\numfeat-m))})\] } If instead, we allow the decision list stops at some unknown (in advance) M, the size of each choice set will increase by $1$, giving the bound: \[ E(h^{l},z^{\numex})+\sqrt{\frac{1}{2\numex}(\ln \frac{1}{\delta }+\sum _{m=1}^{M(h)}\ln (\numfeat-m+1))}) \] {\tt [Maybe generalize declist so that also have choice of expanding the width of each term. E.g., if no single variable works then go to conjunction of two...]} } More generally, the Microchoice bound is similar to Occam's razor or SRM bounds when each $k$-ary choice in the tree corresponds to $\log k$ bits in the natural encoding of the final hypothesis $h$. However, sometimes this may not be the case. Consider, for instance, a local optimization algorithm in which there are $n$ parameters and each step adds or subtracts 1 from one of the parameters. Suppose in addition the algorithm knows certain constraints that these parameters must satisfy (perhaps a set of linear inequalities) and the algorithm restricts itself to choices in the legal region. In this case, the branching factor, at most $2n$, might become much smaller if we are ``lucky'' and head towards a highly constrained portion of the solution space. One could always reverse-engineer an encoding of hypotheses based on the choice tree, but the Microchoice approach is much more natural. There is also an opportunity to use \emph{a~priori} knowledge in the choice of $\meas(h)$. In particular, instead of splitting our confidence equally at each node of the tree, we could split it unevenly, according to some heuristic function $g$. %% producing some measure, $g: c \times C \rightarrow %%m_i$, with $\sum_i m_i = 1$, we can divide our confidence across the %%choices according to the weighting, $m_i$. If $g$ is ``good'' it may produce error bounds similar to the bounds when $\meas(h)=p(h)$. In fact, the method of section \ref{sec:query} where we combine these results with Freund's query-tree approach can be thought of along these lines. \subsection{Examples} The Microchoice Bound is not always better than the standard sample complexity bound (\ref{eqn:simple}). To develop some understanding of how they compare we consider several cases. \comment{ \subsubsection{Simple sample complexity beats Microchoice} As discussed previously the description language for the Microchoice bound is not always the most efficient way of specifying a hypothesis. This can result in over-counting the number of hypotheses and a weaker bound. Consider a problem where the number of boolean features, $\numfeat$, is relatively small and the number of examples $\numex=O(2^\numfeat)$ is relatively large. Assume that a correct hypothesis requires a full decision tree with $2^\numfeat - 1$ internal nodes and $2^\numfeat$ leaves. The size of the hypothesis set will be $|H| = 2^{2^\numfeat}$ while the size of the choice sets will be: $\prod_i |C_i| = \prod_{i=0}^\numfeat (\numfeat-i+2)^{2^i} = 2^{2^\numfeat} 3^{2^{\numfeat-1}} 4^{2^{\numfeat-2}} ... \leq 2^{2^\numfeat 2\ln \numfeat}$. The complexity of the output hypothesis will be somewhat larger when using the Microchoice bound instead of the simple sample complexity bound. There are other learning algorithms where the underestimation of confidence placed on the final hypothesis will be more extreme. \subsubsection{Microchoice beats simple sample complexity} The Microchoice bound can improve on the simple sample complexity bound by arbitrary amounts. Assume that we have a problem with a large number $\numfeat$ of boolean features and a small number of examples $\numex = O(\numfeat)$. Also assume that this is a very simple problem - namely that each feature is the label. Consequently, the output decision tree will have one internal node and a choice set size of $(\numfeat+2)(\numfeat+1)^2$ and a complexity size of $\ln (\numfeat+2) + 2 \ln (\numfeat+1)$. Since $\numex$ is much larger than the complexity the Microchoice bound will be quite tight while the simple sample complexity bound will be loose to the point of uselessness.} \subsubsection{Greedy Set Cover} Consider a greedy set cover algorithm for learning an OR function over $\numfeat$ boolean features. The algorithms begins with a choice space of size $\numfeat+1$ (one per feature or halt) and chooses the feature that covers the most positive examples while covering no negative ones. It then moves to a choice space of size $\numfeat$ (one per feature remaining or halt) and chooses the best remaining feature and so on until it halts. If the number of features chosen is $k$ then the Microchoice bound is: $$\epsilon(h) = \frac{1}{\numex}\left(\ln \frac{1}{\delta }+\sum _{i=1}^{k}\ln (\numfeat-i+2)\right) \leq \frac{1}{\numex} \left( \ln \frac{1}{\delta} + k \ln (\numfeat+1) \right) $$ In contrast, the bound of (\ref{eqn:simple}) is: $$\epsilon = \frac{1}{\numex}\left( \ln \frac{1}{\delta} + \numfeat \ln 2 \right).$$ If $k$ is small, then the Microchoice bound is much better, but if $k=O(\numfeat)$ then the Microchoice bound is slightly worse. Notice that in this case the Microchoice bound is essentially the same as the standard Occam's razor analysis when one uses \( O( \ln \numfeat) \) bits per feature to describe the hypothesis. \subsubsection{Decision Trees}\label{sec:dt1} Decision trees over discrete sets (say, $\{0,1\}^\numfeat$) are another natural setting for application of the Microchoice bound. To apply this bound in a reasonable way, let us assume the learning algorithm operates in a recursive fashion: after placing a test at the root, it recursively constructs the left and right subtrees. (So, the only decision of the algorithm at each point in time is what, if any, test to apply at the current node --- not which node to expand next.) %% %%A decision tree differs from a decision list in that the size of the %%available choice set is larger due to the fact that there are %%multiple nodes where a new test may be applied. In particular, for a %%decision tree with \( K \) leaves at an average depth of $d$, the %%choice set size is $K(\numfeat-d)$, giving a bound noticeably worse than %%the bound for the decision list. This motivates a slightly different %%decision algorithm which considers only one leaf node at a time. The %%algorithm adds a new test or decides to never add a new test at this %%node. In this case, there are $(\numfeat-d(v)+1)$ choices for a node \( v \) at depth \( d(v) \), implying the bound: \begin{equation} E_P(h) \leq E(h,z^{\numex}) +\sqrt{\frac{1}{2\numex}(\ln \frac{1}{\delta }+\sum_{v}\ln (\numfeat-d(v)+1)}) \label{eqn:dectreemc} \end{equation} where $v$ ranges over the nodes of the decision tree. \subsubsection{Pruning} Decision tree algorithms for real-world learning problems often have some form of ``pruning'' as in \cite{Quinlan86} and \cite{Mingers89}. The tree is first grown to full size producing a hypothesis with minimum empirical error. Then the tree is ``pruned'' starting at the leaves and progressing up through the tree towards the root node using some type of significance test. %% for the significance of an internal node. An internal node %% is not significant if the reduction in total error is small in %% comparison to the complexity of its children. Insignificant internal %% nodes are replaced with a leaf resulting in a smaller tree. Microchoice bounds have the property that %% they incidentally prove a %% bound for every decision tree which can be found by pruning internal %% nodes. In particular, one of the choices available when constructing %% a node is to make the node a leaf. Therefore, if we begin with the tree $T$ and then prune to the smaller tree $T'$, we can apply the bound (\ref{eqn:dectreemc}) to $T'$ \emph{as if} the algorithm had constructed $T'$ directly rather than having gone first through the tree $T$. %%%% Include this? %% That is because all we care about is the description length of the %% final tree in the Microchoice ``language''. This suggests another possible pruning criterion: prune a node if the pruning would result in an improved Microchoice bound. That is, prune if the increase in empirical error is less than the decrease in $\epsilon (h)$. The similarities to SRM are discussed below. \subsection{Relationship with Structural Risk Minimization} Structural Risk Minimization works with a sequence of nested hypothesis sets, $H_1 \subset H_2 \subset .... \subset H_l$. For each hypothesis set, one can apply the standard sample complexity bound: $\Pr_{z^\numex \sim P^\numex}\left[\exists h\in H_i:E_{P}(h)>E(h,z^{\numex})+ \epsilon_i\right] < \delta$, where $\epsilon_i = \sqrt{({1}/{2\numex})\left(\ln {1}/{\delta} + \ln |H_i| \right)}$. %% %% \begin{thm} (Standard Sample Complexity Bound) %% \[ %% \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H_i:E_{P}(h)>E(h,z^{\numex})+ \epsilon(h)\right] %% < \delta \] \[ \mbox{ \ for \ } %% \epsilon(h) = \sqrt{\frac{1}{2\numex}\left(\ln \frac{1}{\delta} + %% \ln |H_i| \right)} \] %% %% \end{thm} SRM combines these into a single inequality that includes all hypothesis sets, as follows. \begin{thm} (Structural Risk Minimization) Let $\meas_i$ be some measure across the $l$ hypothesis sets with $\sum_{i=1}^l \meas_i = 1$. Then: \[ \Pr_{z^\numex \sim P^\numex}\left[\exists h\in H_i \in {H_1,...,H_l}:E_{P}(h)>E(h,z^{\numex})+ \epsilon_i\right] < \delta \] \[ \mbox{ \ for \ } \epsilon_i = \sqrt{\frac{1}{2\numex}\left(\ln \frac{1}{\delta} + \ln \frac{|H_i|}{\meas_i} \right)} \] \end{thm} The proof is simple --- just apply the union bound. The SRM bound is slightly inefficient in the sense that the bound for all hypotheses in $H_2$ includes a bound for every hypothesis in $H_1$. This effect is typically small because the size of the hypothesis sets usually grows exponentially, implying that the extra confidence given to a hypothesis $h$ in $H_1$ by the bounds used on hypothesis set $H_2, H_3, ...$ is small relative to the confidence given by the bound for $H_1$. One can remove this slack in Structural Risk Minimization bound by ``cutting out'' the nested portion of each hypothesis set in the formulation of $H_1, ..., H_l$. Let's call this Disjoint Structural Risk Minimization. The above Microchoice bound can be viewed as a form of Disjoint SRM bound where the description language for a hypothesis is the sequence of data-dependent choices that the algorithm makes in the process of deciding upon the hypothesis. The hypothesis set $H_i$ is all hypotheses with the same description length in this language. \comment{ [[This is confusing --- I suggest deleting this paragraph: As an example, consider a binary decision tree with $\numfeat$ boolean features and a boolean label. The first hypothesis set, $H_1$ will consist of $2$ hypotheses; always false and always true. In general, we will have one hypothesis set for every legal configuration of internal nodes. The size of a hypothesis set where every tree contains $k$ internal nodes will be $2^{k+1}$ because there are $k+1$ leaves each of which can take $2$ values. The weighting $m(i)$ across the different hypothesis sets is defined by the Microchoice allocation of confidence.]]} The principle disadvantage of the Microchoice bound is that the sequence of data-dependent choices may contain redundancy. A different SRM bound with a different set of disjoint hypothesis sets might be able to better avoid redundancy. As an example, assume that we are working with a decision tree on $\numfeat$ binary features. There are $\numfeat+2$ choices (any of $\numfeat$ features or $2$ labels) at the top node. At the next node down there will be $\numfeat+1$ choices in both the left and right children. Repeat until a maximal decision tree is constructed. There will be $\prod_{i=0}^{\numfeat} (\numfeat-i+2)^{2^i}$ possible trees. This number is somewhat larger than the number of boolean functions on $\numfeat$ features: $2^{2^\numfeat}$. %%The point here is that a different SRM bound may %%work even with an inefficiently expressed hypothesis. \section{Combining Microchoice with Freund's Query Tree approach}\label{sec:query} The remainder of the paper is devoted to an improvement of the Microchoice bound that we call Adaptive Microchoice which arises from synthesizing Freund's query trees with the Microchoice bound. This improvement is not easily expressed as a simplification of Structural Risk Minimization. First we require some background material in order to state and understand Freund's bound. \subsection{Preliminaries and Definitions} The statistical query framework introduced by Kearns \cite{MK93} is the same as the PAC framework, except that the learning algorithm can only access its data using statistical queries. A statistical query takes as input a binary predicate, $\chi$, mapping examples\footnote{In the real SQ model there is no set of examples. The algorithm asks a query $\chi$ and is given a response $\hat{P}_\chi$ that is guaranteed to be near to the true value $P_\chi$. That is, the true SQ model is an abstraction of the scenario described here where $\hat{P}_\chi$ is computed from an observed sample.} to a binary output: $(X,Y) \rightarrow \{0,1\}$. The output of the statistical query is the average of $\chi$ over the examples seen, \[ \hat{P}_\chi =\frac{1}{\numex}\sum_{i=1}^\numex \chi(z_i) \] The output is an empirical estimate of the true value $P_\chi = {\bf E}_P[\chi(z)]$ of the query under the distribution $P$. It is convenient to define $$\alpha(\delta) = \sqrt{\frac{1}{2\numex}\ln \frac{2}{\delta}}.$$ Then, by Hoeffding's inequality, \[ \Pr\left[|\hat{P}_\chi - P_\chi| > \alpha(\delta)\right] < \delta. \] \subsection{Background and Summary} Freund \cite{F98} considers choice algorithms that at each step perform a Statistical Query on the sample, using the result to determine which choice to take. %%The distribution $P$ determines the true correct answer $P_\chi$ to %%any statistical query $\chi$. For an algorithm $A$, tolerance $\alpha$, and distribution $P$, Freund defines the query tree $T_A(P,\alpha)$ as the choice tree created by considering only those choices resulting from answers $\hat{P}_\chi$ to queries $\chi$ such that $|\hat{P}_\chi - P_\chi| \leq \alpha$. The idea is that if a particular predicate, $\chi$, is true with probability $.9$ on a random example, then it is very unlikely that the empirical result of the query will be $.1$. More generally, the chance the answer to a given query is off by more than $\alpha$ is at most $2e^{-2\numex\alpha^2}$ by Hoeffding's inequality. So, if the entire tree contains a total of $|Q(T_A(P,\alpha))|$ queries in it, the probability {\em any} of these queries is off by more than $\alpha$ is at most $2 \cdot |Q(T_A(P,\alpha))| \cdot e^{-2\numex\alpha^2}$. In other words, this is an upper bound on the probability the algorithm ever ``falls off the tree'' and makes a low probability choice. The point of this is that we can allocate half (say) of the confidence parameter $\delta$ to the event that the algorithm ever falls off the tree, and then spread the remaining half evenly on the hypotheses in the tree (which hopefully is a much smaller set than the entire hypothesis set). Unfortunately, the query tree suffers from the same problem as the $p(h)$ distribution considered in Section \ref{sec:motivating}, namely that to compute it, one needs to know $P$. So, Freund proposes an algorithmic method to find a superset approximation of the tree. The idea is that by analyzing the results of queries, it is possible to determine which outcomes were unlikely given that the query is close to the desired outcome. In particular, each time a query $\chi$ is asked and a response $\hat{P}_\chi$ is received, if it is true that $|\hat{P}_\chi - P_\chi| \leq \alpha$, then the range $[\hat{P}_\chi - 2\alpha, \hat{P}_\chi + 2\alpha]$ contains the range $[{P}_\chi - \alpha, {P}_\chi + \alpha]$. Thus, under the assumption that no query in the \emph{correct} tree is answered badly, a superset of the correct tree can be produced by exploring all choices resulting from responses within $2\alpha$ of the response actually received. By applying this method to every node in the query tree we can generate an empirically observable superset of the query tree: that is, the original query tree is a pruning of the empirically constructed tree. A drawback of this method is that it can easily take exponential time to produce the approximate tree, because even the smaller correct tree can have a size exponential in the running time of the learning algorithm. Instead, we would much rather simply keep track of the choices actually made and the sizes of the nodes actually followed, which is what the Microchoice approach allows us to do. As a secondary point, given $\delta$, computing a good value of $\alpha$ for Freund's approach is not trivial, see \cite{F98}; we will be able to finesse that issue. In order to apply the Microchoice approach, we modify Freund's query tree so that different nodes in the tree receive different values of $\alpha$, much in the same way that different hypotheses $h$ in our choice tree receive different values of $\epsilon(h)$. \subsection{Microchoice Bounds for Query Trees} \comment{ If we knew exactly what the distribution, $P$, and the learning algorithm, we know the choice tree induced by the distribution on the learning algorithm. Not all branches in this tree are equally likely. For example, if a particular predicate, $\chi$ is true with probability $.9$ it is very unlikely that the empirical result of the query will be $.1$. If there are many such low likelihood possibilities, applying a uniform measure across all choices will result in a bound which is loose. Instead, we can place some confidence upon the output of the statistical query being within some error, $\alpha$, of the true answer, then remove all confidence from choices which would only have been made if the query was more than $\alpha$ from the true answer. } The manipulations of the choice tree are now reasonably straightforward. We begin by describing the {\em true} microchoice query tree and then give the algorithmic approximation. As with the choice tree in Section \ref{sec:mc}, one should think of each node in the tree as representing the current internal state of the algorithm. We incorporate Freund's approach into the choice tree construction by having each internal node allocate a portion $\delta'$ of its ``supply'' $\tilde{\delta}$ of confidence parameter to the event that the output of the statistical query being asked is within $\alpha(\delta')$ of the correct answer. The node then splits the remainder of its supply, $\tilde{\delta} - \delta'$, evenly among the children corresponding to choices that result from answers $\hat{P}_\chi$ with $|\hat{P}_\chi - P_\chi| \leq \alpha(\delta')$. Choices that would result from ``bad'' answers to the query are \emph{pruned away} from the tree and get nothing. This continues down the tree to the leaves. How should $\delta'$ be chosen? Smaller values of $\delta'$ result in larger values of $\alpha(\delta')$ leading to more children in the pruned tree and less confidence given to each. Larger values of $\delta'$ result in less left over to divide among the children. Unfortunately, our algorithmic approximation (which only sees the empirical answers $\hat{P}_\chi$ and needs to be efficient) will not be able to make this optimization. Therefore, we define $\delta'$ in the \emph{true} Microchoice query tree to be $\frac{\tilde{\delta}}{d+1}$ where $d$ is the depth of the current node. The algorithmic approximation uses the idea of \cite{F98} of including all choices within $2\alpha$ of the observed value $\hat{P}_\chi$. Unlike \cite{F98}, however, we do not actually create the tree; instead we just follow the path taken by the learning algorithm, and argue that the ``supply'' $\delta(h)$ of confidence remaining at the leaf is no greater than the amount that would have been there in the original tree. Finally, the algorithm outputs $\epsilon(h)$ corresponding to $\delta(h)$. Specifically, the algorithm is as follows. Suppose we are at a node of the tree containing statistical query $\chi$ at depth $d(\chi)$ and we have a $\tilde{\delta}$ supply of confidence parameter. (If the current node is the root, then $\tilde{\delta} = \delta$ and $d(\chi) = 1$). We choose $\delta' = \tilde{\delta}/(d+1)$, ask the query $\chi$, and receive $\hat{P}_\chi$. We now let $k$ be the number of children of our node corresponding to answers in the range $[\hat{P}_\chi - 2\alpha(\delta'), \hat{P}_\chi + 2\alpha(\delta')]$. We then go to the child corresponding to the answer $\hat{P}_\chi$ that we received, giving this child a confidence parameter supply of $(\tilde{\delta} - \delta')/k$. This is the same as we would have given it had we allocated $\tilde{\delta} - \delta'$ to the children equally. We then continue from that child. Finally, when we reach a leaf, we output the current hypothesis $h$ along with the error estimate $E(h,z^\numex) + \epsilon(\tilde{\delta})$, where $\epsilon(\tilde{\delta})$ is the error term corresponding to the remaining confidence supply $\tilde{\delta}$. \comment{ %% TRY TO GET THIS TO WORK FOR THE FINAL VERSION Specifically, the algorithm is as follows. Suppose we are at a node of the tree containing statistical query $\chi$ and we have a $\tilde{\delta}$ supply of confidence parameter. (If the current node is the root, the $\tilde{\delta} = \delta$. We ask the query $\chi$ and receive $\hat{P}_\chi$. We now need to choose $\delta'$. In particular, define $k(\delta')$ to be the number of children of our node corresponding to answers in the range $[\hat{P}_\chi - 2\alpha(\delta'), \hat{P}_\chi + 2\alpha(\delta')]$. We want to pick $\delta'$ to maximize the amount of our confidence parameter given to each child, namely $(\tilde{\delta} - \delta')/k(\delta')$. However, because we are concerned with algorithmic efficiency, we propose to just do the following. We first see if $k(\tilde{delta}/2) > 1$. If so, then we just let $\delta' = \tilde{\delta}/2$; the point is that in this case, the optimal value of $\delta'$ cannot be too much better. On the other hand if $k(\tilde{delta}/2) = 1$ (there is only one child) then we check $k(\tilde{delta}/4)$ and perform binary search to find the smallest value of $\delta'$ that yields just one child, and use that value. The point here is that the case of $k=1$ (i.e., an especially nice world) is one in which one can travel deeply in the tree with very little penalty, thus we do not wish to lose factors of 2 at each level unnecessarily. } We now prove that with probability $1 - \delta$, our error estimate $E(h,z^\numex) + \epsilon(h)$ is correct. By design, with probability $1-\delta$ all queries in the true Microchoice query tree receive good answers, {\em and} all hypotheses in that tree have their true errors within their estimates. We argue that in this case, the confidence assigned to the final hypothesis in the algorithmic construction is no greater than the confidence assigned in the true query tree. In particular, assume inductively that at the current node of our empirical path the supply $\tilde{\delta}_{\mathrm{emp}}$ is no greater than the supply $\tilde{\delta}_{\mathrm{true}}$ given to that node in the true tree. Now, under the assumption that the response $\hat{P}_\chi$ is ``good'', it must be the case that the interval $[\hat{P}_\chi - 2\alpha(\tilde{\delta}_{\mathrm{emp}}/(d+1)), \hat{P}_\chi + 2\alpha(\tilde{\delta}_{\mathrm{emp}}/(d+1))]$ contains the interval $[P_\chi - \alpha(\tilde{\delta}_{\mathrm{true}}/(d+1)), P_\chi + \alpha(\tilde{\delta}_{\mathrm{true}}/(d+1))]$. Therefore, the supply given to our child in the empirical path is no greater than the supply given in the true tree. Let $d(h)$ be the depth of some hypothesis $h$ in the empirical path and $\hat{C}_1(h)$, $\hat{C}_2(h)$, $\ldots$, $\hat{C}_d(h)$ be the sequence of choice sets resulting in $h$ in the algorithmic construction; i.e., $\hat{C}_i(h)$ is the number of unpruned children of the $i$-th node. Then, the confidence placed on $h$ will be: \begin{equation} \delta'(h) = \delta \prod_{i=1}^{d(h)}\left(\frac{i}{i+1}\frac{1}{|\hat{C}_i(h)|}\right) = \delta \frac{1}{d(h)+1} \prod_{i=1}^{d(h)}\frac{1}{|\hat{C}_i(h)|} \label{eqn:adaptiveMC} \end{equation} Let $A(z^\numex)$ denote the hypothesis produced by the learning algorithm on the given sample. We now have the following two theorems for the realizable and agnostic cases: \begin{thm}\label{thm:ramt} (Realizable Adaptive Microchoice Theorem) For any \( 0<\delta <1 \), under the assumption that $A$ produces only hypotheses with zero empirical error, \[ \Pr_{z^\numex \sim P^\numex}\left[A(z^\numex)=h:E_{P}(h)> \epsilon (h) \right] < \delta \] \[ \mbox { for } \epsilon (h) = \frac{1}{\numex}\left(\ln \frac{1}{\delta }+\ln(d(h)+1)+\sum _{i=1}^{d(h)} \ln (|\hat{C}_{i}(h)|)\right). \] \end{thm} \comment{ \noindent {\bf Proof.} As discussed above. Essentially, the same as the Realizable Microchoice theorem, except the choice sets, $C_i$ are pruned to include only the likely outcomes $\hat{C}_{i}$. } \begin{thm}\label{thm:aamt} (Agnostic Adaptive Microchoice Theorem) For any \( 0<\delta <1 \), \[ \Pr_{z^\numex \sim P^\numex}\left[A(z^\numex)=h:E_{P}(h)>E(h,z^{\numex})+ \epsilon (h) \right]<\delta \] \[ \mbox{ for } \epsilon (h) = \sqrt{\frac{1}{2\numex}(\ln \frac{1}{\delta }+\ln(d(h)+1)+\sum_{i=1}^{d(h)}\ln (|\hat{C}_{i}(h)|))}. \] \end{thm} The bounds in Theorems \ref{thm:ramt} and \ref{thm:aamt} are very similar to \ref{thm:rmt} and \ref{thm:amt} except that the choice complexity is slightly worsened with the \( \ln (d(h)+1) \) term but improved by replacing \( C_i(h) \) with the smaller \( \hat{C}_i(h) \). The hope is that the reduction in number of choices from $C_i(h)$ to $\hat{C}_i(h)$ resulting from pruning the tree will more than make up for the single $\ln(d(h)+1)$ term. \comment{ \noindent {\bf Proof.} The same proof as for the Realizable Adaptive Microchoice theorem starting with the Agnostic Microchoice theorem instead of the Realizable Microchoice theorem. } \subsection{Allowing batch queries} Most natural Statistical Query algorithms make each choice based on responses to a {\em set} of queries, not just one. For instance, to decide what variable to put at the top of a decision tree, we ask $\numfeat$ queries, one for each feature; we then choose the feature whose answer was most ``interesting''. This suggests generalizing the query tree model to allow each tree node to contain a set of queries, executed in batch. Requiring each node in the query tree to contain just a single query as in the above construction would result in an unnecessarily high branching factor just for the purpose of ``remembering'' the answers received so far.\footnote{Consider a decision tree algorithm attempting to find the right feature for a node. If the first query returns a value of $\hat{P}_\chi$ with a confidence of $\delta$ then the branching factor would be approximately $m \cdot\left[ \hat{P}_\chi - 2 \alpha(\delta) - (\hat{P}_\chi - 2 \alpha(\delta)) \right] = 4m \cdot \alpha(\delta)$. This branching factor would be approximately the same for further queries required by the algorithm to make a decision about what feature to use. This results in a total multiplied choice space size of approximately $\left[ 4m\cdot \alpha(\delta) \right] ^\numfeat$. This can be reduced to $\numfeat$ or less using a batch query.} Extending the algorithmic construction to allow for batch queries is easily done. If a node has $q$ queries $\chi_1, \ldots, \chi_q$, we choose the query confidence $\delta' = \tilde{\delta}/(d+1)$ as before, but we now split the $\delta'$ evenly among all $q$ queries. %%ask the queries receiving responses $\hat{P}_{\chi_1}, \ldots, %%\hat{P}_{\chi_b}$. We then We then let $k$ be the number of children corresponding to answers to the queries $\chi_1, \ldots, \chi_q$ in the ranges $[\hat{P}_{\chi_1} - 2\alpha(\delta'/q), \hat{P}_{\chi_1} + 2\alpha(\delta'/q)], \ldots, [\hat{P}_{\chi_q} - 2\alpha(\delta'/q), \hat{P}_{\chi_q} + 2\alpha(\delta'/q)]$ respectively. We then go to the child corresponding to the answers we actually received, and as before give the child a confidence supply of $(\tilde{\delta} - \delta')/k$. Theorems \ref{thm:ramt} and \ref{thm:aamt} hold exactly as before; the only change is that $|\hat{C}_i(h)|$ now denotes the size of the $i$-th choice set in the batch tree rather than the size in the single-query-per-node tree. \subsubsection{Example: Batch Queries for Decision trees} When growing a decision tree, it is natural to make a batch of queries and then use the results to make a decision about which feature to place in a node. The process is then repeated to grow the full tree structure. As in the decision tree example described in Section \ref{sec:dt1}, if we have $\numfeat$ features and are considering adding a node at depth $d(v)$, there are $\numfeat - d(v) + 1$ possible features that could be chosen for placement in a particular node. The decision of which feature to use is made by comparing the results of $\numfeat - d(v) + 1$ queries to pick the best feature according to some criteria, such as information gain. We can choose $\delta' = \tilde{\delta }/ (d + 1)$, then further divide $\delta'$ into confidences of size $\delta'/(\numfeat - d(v) + 1)$, placing each of these on one of the $\numfeat - d(v) + 1$ statistical queries. Based on the results of these queries, we now may be able to eliminate some of the $\numfeat - d(v) + 1$ choices from consideration, allowing the remaining confidence, $\tilde{\delta } - \delta $ to be apportioned evenly amongst the remaining choices. Depending on the underlying distribution this could substantially reduce the size of the choice set. The best case occurs when one feature partitions all examples reaching the node perfectly and all other features are independent of the target. In this case the choice set will have size $1$ if there are enough examples. %%A bound can be made for any a priori schedule of apportionment to $\delta'$. \subsection{Adaptive Microchoice vs.~ Basic Microchoice} \label{sec:adaptive} The Adaptive Microchoice bound is a significant improvement over the simple Microchoice bound when the distribution is such that each choice is clear. For example, consider $\numfeat$ boolean features and $\numex = O(\numfeat)$ examples. Suppose that one feature is identical to the label and all the rest of the features are determined with a coin flip independent of the label. When we apply a decision tree to a dataset generated with this distribution, what will be the resulting bound? Given enough examples, with high probability there will only be one significant choice for the first batch query: the feature identical to the label. The second and third batch queries, corresponding to the children of the root feature, will also have a choice space of size $1$ with very high probability: the ``right'' choice will be to make the node into a leaf containing the label value. Each choice set has size $1$ resulting in a complexity of $\ln 4$ due to allocation of confidence to the statistical queries necessary for learning the decision tree. $\ln 4$ is considerably better than $\ln (\numfeat+2) + 2 \ln (\numfeat+1)$ which the simple version of the Microchoice bound provides. Note that the complexity reduction only occurs with a large enough number of examples $\numex$ implying that the value of \( \epsilon (h) \) calculated can improve faster than (inverse) linearly in the number of examples. The Adaptive Microchoice bound is never much worse than the simple Microchoice bound under the assumption that choice sets are of size at least $2$, because in this case the penalty for using the adaptive version, $\ln d$, is always small compared to the complexity term $\sum_{i=1}^{d(h)} \ln |C_i(h)|$. \subsection{Alternative Adaptive Microchoice} The Adaptive Microchoice bound provides a simple scheme for dividing confidence between choices and queries. There are other choices which may be useful in some settings. Any scheme which \emph{a priori} divides the confidence between queries and choices at every node will generally work. Here are two schemes which may be useful: \begin{itemize} \item Assign a constant proportion of confidence to the query. This scheme is more aggressive than the one used in the Adaptive Microchoice bounds and may result in a lower complexity when many choices are eliminatable. The drawback is we no longer get the telescoping in equation (\ref{eqn:adaptiveMC}) and so the term logarithmic in $d(h)$ in theorems \ref{thm:ramt} and \ref{thm:aamt} becomes linear in $d(h)$. \item For a decision tree, assign a portion dependent on the depth of the node in the decision tree that the choice set is over. It is unlikely that choices are eliminatable from nodes not near the root because the number of examples available at a node typically decays exponentially with the (decision tree) depth. A progressive scheme which allocates less confidence to queries for deep nodes will probably behave better in practice. \end{itemize} \section{Comparison with Freund's Work} Freund's approach for self-bounding learning algorithms can require exponentially more computation then the Microchoice approach. In its basic form, it requires explicit construction of every path in the state space of the algorithm not pruned in the tree. There exist some learning algorithms where this process can be done implicitly making the computation feasible. However, in general this does not appear to be possible. The Adaptive Microchoice bound only requires explicit construction of the size of each subset from which a choice is made. Because many common learning algorithms work by a process of making choices from small subsets, this is often computationally easy. The Adaptive Microchoice bound does poorly, however, when Freund's query tree has a high degree of sharing; for example, when many nodes of the tree correspond to the same query, or many leaves of the tree have the same final hypothesis. Allowing batch queries alleviates the most egregious examples of this. It is also possible to interpolate between the Adaptive Microchoice bound and Freund's bound by a process of conglomerating the subsets of the Microchoice bound. \subsection{ Choice Set Conglomeration } The mechanism of choice set conglomeration is similar to the batch query technique. The idea is to collapse adjacent levels of the query tree in order to trade increased computation for a tighter bound. When starting with the simple Microchoice bound, this technique can smoothly interpolate with the simple sample complexity bound (\ref{eqn:simple}). When starting with the Adaptive Microchoice bound, we can interpolate with Freund's bound. Consider a particular choice set, \( \hat{C}_i \), with elements \( c_i \). Each \( c_i \) indexes another choice set, \( \hat{C}_{i+1}(c_{i}) \). If the computational resources exist to calculate the union \( \hat{C}_{i,i+1}=\bigcup _{c_i\in \hat{C}_i} \hat{C}_{i+1}(c_i) \), then \( |\hat{C}_{i,i+1}| \) can be used in place of \( |\hat{C}_{i}| \cdot |\hat{C}_{i+1}| \) in the adaptive Microchoice bound. The conglomeration can be done repeatedly to build large choice sets and also applies to the simple Microchoice bound \ref{thm:rmt} and \ref{thm:amt}. Conglomeration can be useful for tightening the bound when there are multiple choice sequences leading to the same hypothesis. However, choice set conglomeration is not always helpful because it trades away the fine granularity of the Microchoice bound. The extreme case where all choice sets are conglomerated into one choice set and every hypothesis and query have the same weight is equivalent to Freund's bound. \comment{For a proof, we need to show that the confidence placed on some final hypothesis is smaller than is placed on the hypothesis by the true query tree. The proof is very simple: first conglomerate the choice set in the true query tree then conglomerate the set of nodes in the approximate query tree. Now the previous proof that the number of choices in the approximate query tree will be at least as large as the number in the true query tree still holds. This implies theorems \ref{thm:ramt} and \ref{thm:aamt} where the choice sets cited in the theorem are conglomerated in some \emph{a~priori} defined manner.} When the choices of the attached choice sets are all different, conglomeration will have little use because the size of the union of the choice sets is the sum of the sizes of each choice set \( |\hat{C}_{i,i+1}| = \sum_{c_i\in \hat{C}_i} |\hat{C}_{i+1}(c_i)| \). If the child sets each have the same size $|\hat{C}_{i+1}| $ then this simplifies to \( |\hat{C}_{i,i+1}| = |\hat{C}_i| \cdot |\hat{C}_{i+1}|\) which results in the same confidence applied to each choice whether conglomerating or not. The best case for conglomeration is equivalent to the batch query case: every subchoice set contains the same elements. Then we have \( |\hat{C}_{i,i+1}| = |\hat{C}_{i+1}| \) and can pay no cost for the choice set \( |\hat{C}_{i}| \). \comment{ can make the bound significantly tighter. For instance, many natural algorithms can be thought of as sending out a ``batch'' of statistical queries, then based on the responses, sending out another batch. If the computational resources are available (or if the analysis is simple enough), then each batch could be viewed as a single node in the tree. %%%%is this strictly true?? %% By repeating this process for the duration of %% the algorithm we achieve Freund's bound. %% No, because our construction is slightly different By repeating this process for the duration of the algorithm we can achieve a result which is very similar to Freund's bound. } \section{Conclusion} The goal of this work is to produce tighter bounds on the future error rates of a learned hypothesis. We have presented the Microchoice bound which is a kind of Occam's razor bound using the structure of the learning algorithm itself. We then synthesized the Microchoice bound with Freund's query tree approach for Self-Bounding learning algorithms, to produce what we call the Adaptive Microchoice bound. We have also presented some simple techniques for improving these bounds. In particular, by allowing batch queries in nodes, we can produce much more natural bounds for algorithms such as decision trees that are best viewed as basing each decision on the results of a {\em set} of queries. %% One technique is a method for interpolating between the Microchoice %% bound and Freund's query tree approach using conglomeration of %% choice sets. Another technique is the batch query which is %% especially useful for decision trees. We have also presented some examples of the application of these bounds to decision trees. %% along with a new pruning technique suggested by the Microchoice bounds. The Microchoice bound can be applied to many common learning algorithms unintrusively --- the path through state space that the algorithm takes need not be affected. Some extra computation may be necessary to assess the size of the choice set from which the algorithm makes its choices. In return, the algorithm can state a bound along with its hypothesis. The Microchoice approach also shows a very natural way of performing SRM. For example, the bound can be used as a decision tree pruning criterion. In a given situation, the Microchoice bound may or may not be better than another PAC bound. In practice, it may be worthwhile to output a bound which is the minimum of that given by the Microchoice bound and a more general PAC bound. This can be done in a theoretically sound manner by giving half of the confidence parameter $\delta$ to each bound, for instance. %% first mapping \( \delta \rightarrow \frac{\delta }{2} \) in each %% bound which slightly worsens the result. The resulting $\epsilon = \min(PAC(\delta/2),Microchoice(\delta/2))$ bound will then hold with probability \( 1-\delta \). There are several remaining open questions. Is there a satisfying, natural bound for the continuous case? Can this approach be useful for commonly used learning algorithms? \subsection*{Acknowledgements} We would like to thank the referees for a number of helpful comments. This work was supported in part by NSF grants CCR-9732705 and CCR-0085982. \bibliographystyle{alpha} \bibliography{mc} \end{document}