Adaptive Sampling Methods for Scaling Up Knowledge Discovery Algorithms.
Scalability is a key requirement for any KDD and data mining algorithm, and one of the biggest research challenges is to develop methods that allow to use large amounts of data. One possible approach for dealing with huge amounts of data is to take a random sample and do data mining on it, since for many data mining applications approximate answers are acceptable. However, as argued by several researchers, random sampling is difficult to use due to the difficulty of determining an appropriate sample size. In this paper, we take a sequential sampling approach for solving this difficulty, and propose an adaptive sampling method that solves a general problem covering many actual problems arising in applications of discovery science. An algorithm following this method obtains examples sequentially in an on-line fashion, and it determines from the obtained examples whether it has already seen a large enough number of examples. Thus, sample size is not fixed a priori&semi; instead, it i>adaptively depends on the situation. Due to this adaptiveness, if we are not in a worst case situation as fortunately happens in many practical applications, then we can solve the problem with a number of examples much smaller than required in the worst case. We prove the correctness of our method and estimates its efficiency theoretically. For illustrating its usefulness, we consider one concrete task requiring sampling, provide an algorithm based on our method, and show its efficiency experimentally.
Introduction
Scalability is a key requirement for any knowledge discovery and data mining algorithm.
It has been previously observed that many well known machine learning algorithms do
not scale well. Therefore, one of the biggest research challenges is to develop new methods
that allow to use machine learning techniques with large amount of data.
Once we are facing with the problem of having a huge input data set, there are
typically two possible ways to address it. One way could be to redesign known algorithms
so that, while almost maintaining its performance, can be run e-ciently with much larger
input data sets. The second possible approach is random sampling. For most of the
data mining applications, approximate answers are acceptable. Thus, we could take a
random sample of the instance space and do data mining on it. However, as argued by
some researchers (see, for instance, [17]) this approach is less recommendable due to the
di-culty of determining appropriate sample size needed. In this paper, we advocate for
this second approach of reducing the dimensionality of the data through random sampling.
For this, we propose a general problem that covers many data mining problems and a
general sampling algorithm for solving it.
A typical task of knowledge discovery and data mining is to nd out some \rule" or
\law" explaining a huge set of examples well. It is often the case that the size of possible
candidates for such rules is still manageable. Then the task is simply to select a rule
among all candidates that has certain \utility" on the dataset. This is the problem we
discuss in the paper, and we call it General Rule Selection. More specically, we are
given an input data set X of examples, a set H of rules, and a utility function U that
measures \usefulness" of each rule on X. The problem is to nd a nearly best rule h,
more precisely, an h satisfying U(h)  (1 )U(h ? ), where h ? is the best rule and  is a
given accuracy parameter. Though simple, this problem covers several crucial topics in
knowledge discovery and data mining as shown in Section 4.
We would like to solve the General Rule Selection problem by random sampling. From
a statistical point of view, this problem can be solved by taking rst a random sample S
from the domain X and then selecting h 2 H with the largest U(h) on S. If we choose
enough number of examples from X randomly, then we can guarantee that the selected
h is nearly best within a certain condence level. We will refer this simple method as a
batch sampling approach.
One of the most important issues when doing random sampling is choosing proper
sample size, i.e., the number of examples. Any sampling method must take into account
problem parameters, an accuracy parameter, and a condence parameter to determine
appropriate sample size needed to solve the desired problem.
Non theoretically sound sampling methods, like taking a xed fraction of the data set,
while widely used in empirical machine learning research, are not appropriate for data
mining where the amount of data available is huge. Moreover, these methods do not take
into account any accuracy or condence considerations and therefore we do not discuss
them here.
Widely used and theoretically sound tools to determine appropriate sample size for
given accuracy and condence parameters are the so called concentration bounds or large
deviation bounds like the Cherno or the Hoeding bounds. They are commonly used in
most of the theoretical learning research (see [7] for some examples) as well as in many
other branches of computer science [13]. For some examples of sample size calculated with
concentration bounds for data mining problems, see, e.g.,[8], [15] and [18]. While these
bounds usually allow us to calculate sample size needed in many situations, it is usually
the case that resulting sample size is immense to obtain a reasonable good accuracy and
condence. Moreover, in most of the situations, to apply these bounds, we need to assume
the knowledge of certain problem parameters that are unknown in practical applications.
It is important to notice that, in the batch sampling approach, the sample size is
calculated a priori and thus, it must be big enough so that it will work well in all the
situations we might encounter. In other words, the sample size provided by the above
theoretical bounds for the batch sampling approach should be the worst case sample size
and thus, it is overestimated for most of the situations. This is one of the main reasons
why researchers have found that, in practice, these bounds are overestimating necessary
sample size for many non worst-case situations; see, e.g., the discussion of Toivonen for
sampling for association rules discovery [15].
For overcoming this problem, we propose in this paper to do the sampling in an
on-line sequential fashion instead of batch. That is, an algorithm obtains the examples
sequentially one by one, and it determines from those obtained examples whether it has
already received enough examples for issuing the currently best rule as nearly the best
with high condence. Thus, we do not x sample size a priori. Instead sample size will
depend adaptively in the situation at hand. Due to this adaptiveness, if we are not in a
worst case situation as fortunately happens in most of the practical cases, we may be able
to use signicantly much less examples than in the worst case. Following this approach,
we propose a general algorithm | AdaSelect | for solving the General Rule Selection
problem, which provides us with e-cient tools for many knowledge discovery applications.
This general algorithm evolves from our preliminary works on on-line adaptive sampling
for more specic problems related to model selection and association rules done in [3, 4].
The idea of adaptive sampling is quite natural, and various methods for implementing
this idea have been proposed in the literature. In statistics, in particular, these methods
have been studied in depth under the name \sequential test" or \sequential analysis" [16].
However, their main goal has been to test statistical hypotheses. Thus, even though some
of their methods are applicable for some instances of the General Rule Selection problem,
as far as the authors know, there has been no method that is as reliable and e-cient as
AdaSelect for the General Rule Selection problem. By using a simple example, we explain
in the next section the dierences and advantages of AdaSelect over related algorithms
including the one following the batch sampling approach.
The paper is organized as follows. In the next section, we explain still at some intuitive
level the advantage of our algorithm over other random sampling methods. In Section 3,
we present our problem and algorithm, and prove theorems concerning its reliability and
complexity. In Section 4, we describe several applications of our algorithm to particular
data mining problems. Further improvements that might be useful to study particular
situations are described in Section 5. We conclude in Section 6 highlighting future work.
Related Work
The idea of determining the number of necessary examples adaptively and thereby reducing
the average number of examples is quite natural, and methods for implementing this
idea have been proposed in the literature. In statistics these methods are called \sequential
test" or \sequential analysis". Since A. Wald published a pioneer 1 textbook on sequential
analysis [16], many researchers have studied sequential analysis methods in depth. Their
main goal has been, however, to test statistical hypotheses. Thus, even though some of
their methods are applicable for our purpose, that is, for evaluating and/or comparing
the value of a given function on a given huge dataset, there has been no method, as far
as the authors know, that is as reliable, e-cient and general as our algorithm AdaSelect.
To illustrate the dierence between AdaSelect and other methods, let us consider the
following very simple problem, for which we only need a very simple utility function.
The problem is to test whether the probability p ? that a given condition C holds in a
1 According to the Wald's textbook, the idea of a sequential test procedure goes back to H.F. Dodge
and H.G. Romig [2].
database X is more than 1=2 or not. If C held exactly in 1=2 of the transactions in
X, then we would have to check all the database to notice it; thus, let us suppose that
Intuitively, if the condition holds in many or
very few transactions (for instance, 90% or 10% of the database) then just sampling a
small number of transactions should be enough to gure out that the answer is positive
or negative. On the other hand, the closer to 50% of the transactions that the condition
holds the more di-cult it should be to test through sampling what is the correct answer.
We can use AdaSelect to solve this problem as follows. We keep two functions, h 1 and
h 2 that map transactions into 0=1 values. Given one transaction x, h 1 (x) outputs 1 if the
transaction x satises the condition C; otherwise, h 1 (x) outputs 0. On the other hand,
h 2 is the negation of h 1 . For the utility function, we use U(h
that is, the dierence (positive or negative) from half of the proportion of transactions.
For our purpose, the algorithm needs to detect whether U(h 1 ) is positive (in which case
negative). Thus, we just need to x  to any number less than 1. If we run
our algorithm under this setting, we would be able to determine, with high condence,
whether the condition C occurs with more than 50% of the transactions in X.
Notice that the above application of AdaSelect always solves the problem, no matter
how small is
? as far as it is not 0. On the other hand, its sample complexity (the number
of necessary examples) depends on
? , and hence, the algorithm might require a lot of
transactions when
? is small. More specically, the number of transactions need to be
sampled from the database is O((1=? ) ln(1=
(ignoring the factor depending on the
condence parameter). Therefore, the closer the value of
? to 0 (and thus, p ? to 1=2),
the larger the number of examples needed will be.
A batch sampling approach is also applicable for this problem. For any
, by using an
appropriate large deviation bound, e.g., the Cherno bound, we can determine the number
of examples su-cient to detect, with high condence, whether the condition holds more
than
of X. Notice here that we have to choose appropriate
since the high
condence of this algorithm is guaranteed only if
. On the other hand, the number
of examples needed is O(1=
Therefore, we have to use
that is smaller than
? , but
if we underestimate
? , then the sample complexity becomes large. In other words, this
batch sampling approach has to be always big enough to cover all possible values of
bigger than
and thus, it depends on
since in the worst case
? might be equal to
. On
the other hand, AdaSelect depends on the case at hand and thus, its sample size depends
on
? . Moreover, for practical applications it might be unrealistic to assume that we can
assume the knowledge of a lower bound
on the quantity
? that we want to estimate.
So we can clearly see here the advantage of our algorithm over the simple batch sampling.
A more sophisticated way to solve the above problem could be the following. Instead
of using the Cherno bound (that provides an estimate that is within a multiplicative
error from the probability being estimated and thus adequate for our purposes, but which
cannot be used unless a lower bound on
? is known) we can use the Hoeding bound,
also usually referred as the additive version of the Cherno bound. The sample size
provided by this bound is independent of the probability being estimated and thus, we
do not need to assume the knowledge of any lower bound on
? . On the other hand, the
estimate is only guaranteed to be within an additive error from the value being estimated.
Therefore, in general, it is impossible to use just one single sample to guarantee that our
problem is solved. Instead, we can do the following. Suppose that we run a batch
sampling calculating the appropriate size with the Hoeding bound for
we obtain an estimate p 1 for p ? . Then with high probability, p 1 should satisfy that
1=4. Thus, if p 1 is greater than 3=4, then we can determine (with
high condence) that p ? is greater than 1=2; on the other hand, if p 1 is less than 1=4,
then we can again determine that p ? is less than 1=2. However, if p 1 is not in that range,
that is, 1=4  p 1  3=4, then we cannot conclude anything about whether p ? is above or
below 1=2. This last situation does not occur if we choose  small enough, but then the
sample complexity becomes large if we underestimate . One way to solve this problem
is to iterate an execution of the algorithm with a smaller accuracy parameter when the
obtained estimate is not in a safe range. In the above case, for example, we can run the
algorithm again with  . Continue this process until the obtained estimate
after the ith iteration is not in the range [1=2 2 (i+1) ; 1=2+2 (i+1) ]. Suppose that the
algorithm always gives an  i -close estimate of p ? . Then routine calculations show that the
algorithm terminates after log(1=
iterations. This approach uses O(1= 2 ) examples for
obtaining an -close estimate (ignoring the factor depending on the condence parameter)
at every step. Hence, altogether we need O((1=?
which gives the
same order as AdaSelect. In fact, very roughly speaking, this is the idea of AdaSelect.
On the other hand, in AdaSelect the iteration phase is naturally incorporated, and thus,
AdaSelect has better sample complexity. Furthermore, it is now easy to generalize the
technique for estimating and/or comparing more general function values.
This method of sampling just described is referred in classical statistics as multiple
sampling [1], and it was one of the earlier works of sequential sampling methods [16].
More recent work on adaptive sampling comes from the database community and it is
due to Lipton et.al. [9, 10]. There the following problem is discussed 2 . Given a database
and a query over the databases (for instance, a selection or a joint), we want to estimate the
query size, that is, the number of transactions associated with the query in the database,
up to a certain error and condence level. They designed algorithms for this task. Below
we refer their algorithms as Adaptive Estimator. More specically, for a given database
X, a condition C, an accuracy parameter , and a condence parameter -, Adaptive
Estimator estimates (through random sampling) the probability p ? that transactions in
up to a multiplicative error . That is, with probability at least 1 -, the
algorithm yields estimate p of p ? such that (1 )p ?  p  (1 . For achieving this
task, Adaptive Estimator collects examples from the database sequentially at random
while checking whether collected examples are su-cient for terminating the execution
with the current estimate. The number of examples used by the algorithm depends on
-. The correctness of the algorithm is proved by using large deviation tools,
in particular, using the central limit theorem. Thus, in other words, Adaptive Estimator
is a sequential version of the multiplicative Cherno bound. However, it is important to
notice that Adaptive Estimator only works for estimating the total probability. In our
example, it provides us with a multiplicative estimate for p ? but not for
? .
Our approach is quite similar to the Adaptive Estimator. The algorithm AdaSelect
we propose also collects examples from a given database sequentially at random while
checking whether collected examples are su-cient. Furthermore, we also use one of the
large deviation tools in order to guarantee the correctness, i.e., the reliability of the output
of the algorithm. Thus, one may think supercially that AdaSelect diers from Adaptive
Estimator only on the point that it enable us to estimate a more general value, i.e.,
the value of a user dened utility function. In fact, this is why we could estimate the
advantage
? instead of p ? in the above example. Note that this dierence is essential.
For our example problem, Adaptive Estimator has exactly the same problem as the batch
sampling method with the Hoeding bound and thus, it cannot be used only once in
general. It must be used iteratively as we described before. Also we remark that the
choice of the utility function U is important. If we use U(h
for the
above problem, then the execution of AdaSelect becomes essentially the same as Adaptive
Estimator. Technically, due to our generalization, the stopping condition of the sampling
algorithm is not monotone, which requires more careful probability analysis.
2 In order to keep the explanation at an intuitive level we explain with some typical algorithm and
omit the details and the dierences of their algorithms. See the papers cited above for more details.
The algorithm AdaSelect presented in this paper evolves from our previous work on
hypothesis selection [3] and sampling for association rules [4]. In fact, the two cases
treated there are very simple cases of the more general utility function introduced in this
paper. The algorithm in the present paper greatly generalizes the adaptive algorithms
provided there so that it can be use to attack several other problems.
3 The Adaptive Sampling Algorithm
In this section we will formally describe the problem we would like to solve; then we
present our algorithm and investigate its reliability and complexity.
We begin introducing some notation. Let be a (large) set of
examples and let be a (nite, not too large) set of n functions such
that can be thought as a function that can be evaluated
on an example x producing a real value y as a result. Intuitively, each h 2 H
corresponds to a \rule" or \law" explaining examples, which we will call below a rule,
and y measures the \goodness" of the rule on x. (In the following, we identify
h with its corresponding rule, and we usually call h a rule.) For example, if the task is to
predict a particular Boolean feature of example x in terms of its other features, then we
could set y the feature is predicted correctly by h, and y predicted
incorrectly. We also assume that there is some xed real-valued and nonnegative utility
function U(h), measuring some global \goodness" of the rule (corresponding to) h on the
set X. More specically, for any S  X, U(h; S) is dened as
where F is some function IR 7! IR and avg(  ) denotes taking the arithmetic average, i.e.,
i2I a i )=jIj. Then U(h) is simply dened as U(h; X). In Section 4 we
will describe several applications of our framework and how U is instantiated to specic
functions; then its meaning will become more clear. Now we are ready to state our
problem.
General Rule Selection
Given: X, H, and , 0 <  < 1.
Goal: Find h 2 H such that U(h)  (1
be the rule with maximum value of U(h ? ).
Remark 1: (Accuracy Parameter )
Intuitively, our task is to nd some h 2 H whose utility is reasonably high compared with
the maximum U(h ? ), where the accuracy of U(h) to U(h ? ) is specied by the parameter
. Certainly, the closer U(h) is to U(h ? ) the better. However, depending on the choice of
U , the accuracy is not essential in some cases, and we may be able to use a large . The
advantage of our algorithm becomes clear in such cases. (Recall the example discussed in
Section 2. See also the discussion at the end of this section.)
Remark 2: (Condence Parameter -)
We want to achieve the goal above by \random sampling", i.e., by using examples randomly
selected from X. Then there must be some chance of selecting bad examples that
make our algorithm to yield unsatisfactory h 2 H. Thus, we introduce one more parameter
specifying condence and require that the probability of such error is
bounded by -.
Remark 3: (Condition on H)
In order to simplify our discussion, we assume in the following that the value of y h;x
(= h(x)) is in [0; d] for some constant d > 0. (From now on, d will denote this constant.)
Remark 4: (Condition on U)
Our goal does not make sense if U(h ? ) is negative. Thus, we assume that U(h ? ) is positive.
Also in order for (any sort of) random sampling to work, it cannot happen that a single
example changes drastically the value of U ; otherwise, we would be forced to look at all
examples of X to even approximate the value of U(h). Thus, we require that the function
F that denes U is smooth. Formally, F need to be c-Lipschitz for some constant c  0,
as dened below. (From now on, c will denote the Lipschitz constant of F .)
Denition. 1 Function F : IR 7! IR is c-Lipschitz if for all x; y it holds jF (x) F (y)j
c  jx yj. The Lipschitz constant of F is the minimum c  0 such that F is c-Lipschitz
(if there is any).
Observe that all Lipschitz functions are continuous, and that all dierentiable functions
with a bounded derivative are Lipschitz. In fact, if F is dierentiable, then by Mean
Value Theorem, the Lipschitz constant of F is max x jF 0 (x)j. As we will see in Section 4
all natural functions used in the applications we describe satisfy this condition for some
c. Also note that from the above conditions, we have cd  U(h)  cd for any h 2 H.
Remark 5: (Minimization Problem)
In some situations, the primary goal might not be to maximize some utility function over
the data but to minimize some penalty function P . That is, we want to nd some h such
that P (h)  (1 can solve the General Hypothesis Selection Problem by an
algorithm and analysis very similar to the one we present here. (End Remarks.)
One trivial way to solve our problem is evaluating all functions h in H over all examples
x in X, hence computing U(h) for all h, and then nding the h that maximizes this value.
Obviously, if X is large, this method might be extremely ine-cient. We want to solve
this task much more e-ciently by random sampling. That is, we want to look only at a
fairly small, randomly drawn subset S  X, nd the h that maximizes U(h; S), and still
be sure with probability 1 - that this h we output satises U(h)  (1 )  U(h ? ).
One can easily think of the following simple batch sampling approach. Obtain a
random sample S from X of a priori xed size m and output the function from H that has
the highest utility in S. There are several statistical bounds to calculate an appropriate
number m of examples. In this paper, we choose the Hoeding bound, which has been
widely used in computer science (see, e.g., [7, 13]). One can use any reasonable bound
here, and choosing which one to use should be determined by considering reliability and
e-ciency. The reason that we choose the Hoeding bound is that basically no assumption
is necessary 3 for using this bound to estimate the error probability and calculate the
sample size. On the other hand, other bounds, for example, the central limit theorem
might be appropriate for some practical situations, since it behaves better although being
slighlty less reliable. It is easy to modify our algorithm for analyze it with these alternative
bounds. Roughly, for any sample size and error value , the Hoeding bound provides
us with an upper bound on the probability that an estimate calculated from a randomly
drawn sample is apart from its real value by . Thus, by using this bound, we can
determine sample size m that guarantees that the batch sampling yields a rule satisfying
the requirement of the problem with probability at least 1 -.
While the batch sampling solves the problem, its e-ciency is not satisfactory because
it has to choose sample size for the worst case. For overcoming this ine-ciency, we
take a sequential sampling approach. Instead of statically decide the sample size, our
new algorithm obtains examples sequentially one by one and it stops according to some
condition based on the number of examples seen and the values of the functions on the
examples seen so far. That is, the algorithm adapts to the situation at hand, and thus
if we are not in the worst case, the algorithm would be able to realize of that and stop
3 The only assumption is that we can obtain samples that are independently obtained from the same
distribution, a natural assumption that holds for all the problems considered here.
Algorithm
repeat
x randomly drawn example from X;
Where  < 1 is some constant close to 1 (see the proof of Theorem 3).
output h 2 H with the largest U(h; S t );

Figure

1: Pseudo-code of our on-line sampling AdaSelect.
Figure 1 shows a pseudo-code of the algorithm we propose, called AdaSelect, for
solving the General Rule Selection problem.
Now we provide two theorems discussing the reliability and the complexity of the
algorithm AdaSelect. In the proofs we will make use of the following lemma.
Lemma. 2 Let S  X be a set of size t obtained by independently drawing t elements
from X at random. For any h 2 H and   0,

Proof. Let G be the value avg(y hx : x 2 X), and g be the random variable avg(y
S). Observe that using the fact that
F is c-Lipschitz,
Prf jg E(g)j  =c g:
But g is the average of t independent random variables with range bounded by d. By the
Hoeding bound, this probability is less than 2 exp
, as claimed. (End Proof)
We rst prove the reliability of Algorithm AdaSelect.
Theorem. 3 With probability 1 -, AdaSelect(X; H; ; -) outputs a function h 2 H such
that U(h)  (1 )U(h ? ).
Proof. For a xed  > 0, dene H g. We show that
the function output by AdaSelect(X; H; ; -) is in H bad with probability less than -. That
is, we want to bound the following error probability P error by -.
Here we regard one repeat-loop iteration as a basic step of the algorithm and measure
the algorithm's running time in terms of the number of repeat-loop iterations. We use
t to denote the number of executed repeat-loop iterations. In particular, let t 0 be the
integer such that the following inequalities hold.
Note that  t is strictly decreasing as a function of t; hence, t 0 is uniquely determined.
As we will see below, the algorithm terminates at the t 0 th step (i.e., just after the t 0 th
repeat-loop iteration) with high probability.
For deriving the bound, we consider the following two cases: (Case 1) Some h 2 H bad
satises the stopping condition of the repeat-loop before the t 0 th step, and (Case
does not satisfy the stopping condition during the rst t 0 steps. Clearly, whenever the
algorithm makes an error, one of the above cases certainly occurs. Thus, by bounding the
probability that either (Case 1) or (Case 2) occurs, we can bound the error probability
P error of the algorithm.
First we bound that the probability of (Case 1). Let h bad be the rule in H bad with
the largest utility.
(Case 1) holds g
Prf h satises the stopping condition of AdaSelect at the tth step g
the stopping condition of AdaSelect at the tth step g
Here g.
For any t, 1  t  t 0 , this P 1 (t) is bounded as follows.
where we have used the fact that for any t  t 0 ,  t > U(h ? )(=2) and that U(h ? )(1
U(h bad ). Then by Lemma 2, we have

Thus, we estimate
(Case 1) holds g
2n exp

Next consider (Case 2). Clearly, (Case 2) implies U(h ?
(2= 1). Thus,
the probability of (Case 2) is bounded by the following
For bounding P 2 , we rst estimate  t 0
where we let b
. Here by using the assumption that  t 0 +1  U(h ? )(=2)
and the fact that U(h)  cd, we
Hence, we may consider that b
1. Therefore, if   b
, then P 2 is bounded as follows.

2nt
In summary, if   b
then the probability that either (Case 1) or (Case
holds is bounded by -. (End Proof)
Next we estimate the running time of the algorithm. As above we regard one repeat-
loop iteration as a basic step of the algorithm and measure the algorithm's running time
in terms of the number of repeat-loop iterations that is exactly the number of required
examples. In the above proof, we have already showed that the probability that the
algorithm does not terminate within t 0 steps, that is, (Case 2) occurs, is at most -. Thus,
the following theorem is immediate from the above proof.
Theorem. 4 With probability 1 -, AdaSelect(X; H; ; -) halts within t 0 steps (in other
words, AdaSelect(X; H; ; -) needs at most t 0 examples), where t 0 is the largest integer
such that  t 0
Let us express t 0 in a more convenient form. Recall that   1. Then, since approximately
if we approximate x  y ln x by x  y ln y., we have

cd

Let us discuss the meaning of this formula. Since both n and - are within the log func-
tion, their in
uence to the complexity is small. In other words, we can handle a relative
large number of rules and require a very high condence without increasing too much the
sample size needed. The main terms in the above formula are 1= and (cd)=U(h ? ). (Recall
that U(h)  cd for any h 2 H; hence, both 1= and (cd)=U(h ? ) are at least 1.) Depending
on the choice of U , in some cases we may assume that (cd)=U(h ? ) is not so large; or,
in some other cases, we may not need small , and thus, 1= is not so large. AdaSelect
performs well in the latter case. More specically, AdaSelect shows its advantage most
when U is chosen so that (1) relatively large  is su-cient, and (2) though (cd)=U(h ? ) is
not bounded in general, it is not so large in lucky cases, which happen more often than
the bad cases. As we will see in Section 4, a clever choice of U might allow us to choose
a large  so that the overall number of examples might not be very large.
4 Examples of Applications
In this section we will describe two domains where an instance of our algorithm can be used
to solve a particular problem. The two domains studied are model or hypothesis selection
and induction of decision trees. Due to space limitations we cannot further describe other
possible applications but for problems like association rules mining (which we have already
studied in [4]) or subgroup discovery, where batch sampling methods based on large
deviation methods have already been proposed to speed up the computational process
(see for instance, [15]and [18]) our algorithm can also be applied.
In order to instantiate our framework to a particular problem we need to specify what
is the meaning of the functions class H, what is the utility function U , and how conditions
the conditions on U are satised. We will do so for the following problems.
Model or hypothesis selection.- This is the most typical application of our framework.
The class of functions H can be seen as a xed set of hypotheses or models. This set
could be obtained, for instance, from dierent runs of rival learning algorithms, or the
same learning algorithm but with dierent input parameters or architecture, or it could
contain several dierent memory-based hypothesis or be just xed to a certain restricted
model space as a consequence of a design decision. Notice that this later the case is the case
of algorithms that try to select a hypothesis from a simple and small class of hypotheses
(for instance, decision stumps) and then amplify its precision using voting methods like
boosting [5]. Thus, in the rest of the discussion, we will assume that the class H is xed,
nite and of tractable size. The utility function should capture the criterion of \goodness"
of the hypothesis, the typical one being the prediction error. In order to keep the discussion
at simple level we will assume that the hypotheses are binary and that the \goodness"
criteria is the prediction error. For this case, one might naively set the utility function to
be just the identity function, that is, U(h;
Notice, however, that the worst possible prediction error is 1/2, which is the same as
answering by
ipping a random coin. Hence, more precisely speaking, for the \goodness"
of hypothesis h, we should measure its advantage from from random guessing. Thus, we
want our algorithm to output a hypothesis whose advantage from random guessing is
close to the best possible advantage in the class. In fact, this setting ts particularly
well with voting methods like AdaBoost [5] where typically one just needs to obtain a
hypothesis that is better than random guessing at every step. For this purpose, we should
set U(h; In particular, for selecting
a hypothesis for voting methods, the choice of  may not be so important; we can set it
to any constant smaller than 1.
A similar setting was previously studied by Maron and Moore in [11] where they
proposed an algorithm called Hoeding races to accelerate model selection. Their idea
was to discard hypotheses when there are clearly not going to be among the best ones.
They criteria for discarding them was based on inverting the Hoeding bound, we refer
the reader to their paper for details. We can clearly add this feature to our algorithm
without compromising its reliability and complexity and possibly accelerating the total
running time. Notice that combining Hoeding races with our algorithm does not reduce
much the number of examples needed since it depends logarithmically on the number of
models n while it might greatly reduce the computation time that depends linearly on n.
In a follow up research, Moore and Lee [12] developed a more e-cient version of
Hoeding races based on a Bayesian approach under the assumption that the the models
accuracies over the dataset are normally distributed. Furthermore, they also introduce a
modication for discarding models that are almost indistinguishable to others and thus,
allowing the race to output a model that is not the best in the class. Notice that this is
also what we are doing through our accuracy parameter .
Our framework allows one to use more complicated utility functions that could incorporate
size or smoothness considerations together with prediction error or for the case of
real-valued functions we could also consider for instance mean square error.
Decision tree induction.- Algorithms for decision tree induction typically work by
choosing a test for the root from certain node function class (and subsequently, for the
root of each subtree) by exploring the training data and choosing the one that is the best
according to certain splitting criteria like the entropy measure or the Gini index. In a
large dataset it could be possible to reduce the training time by choosing the split based
only on a subsample of the whole data. Musick, Catlett, and Russell [14] described an
algorithm that implements this idea and chooses the sample based on how di-cult is the
decision at each node. Typically, their algorithm uses a small sample at the root node
and it enlarges it progressively as the tree grows. Here, we propose an alternative way to
select the appropriate sample size needed at every node by using an instantiation of our
algorithm that we describe in the following. We will follow the notation from [6].
For simplicity, we assume that we want to construct a decision tree that approximates
and unknown function using a training data set S  X. Furthermore, we
assume that the class of node functions F is xed a priori and it is nite and small, for
instance just the input variables and its negations 4 . In fact, this is the class commonly
used by standard software packages as C4.5 or CART. Finally, we denote by G : [0;
[0; 1] the splitting criteria used by the top-down decision tree induction algorithm. A
typical example of this function is the binary entropy
Let T be any decision tree whose internal nodes are labeled by functions in F and its
nodes labeled by values f0; 1g and let l the leaf of T where we want to make a new internal
node substituting leaf l by a function h from F . Our goal is to choose a function h such
that the value of G in the original tree T (that is, the sum of the values of G in every
leaf weighted by the probability of reaching that leaf) decreases by substituting l by h in
4 This assumption makes sense if all the attributes are discrete or have been discretized a priori.
T and labeling the new labels l 0 and l 1 according to the majority class of the instances
reaching l 0 and l 1 respectively. More formally, let ^
S  S be the set of instances that reach
l. For any x in ^
S and any h in F , we denote by p 1; the probability that f(x) is 1, by
p ;1 the probability that h(x) is 1, by p 1;1 the probability that both h(x) and f(x) are 1,
and by p 0;1 the probability that h(x) is 0 but f(x) is 1. Notice that these probabilities
are taken from the distribution induced on ^
S from the initial distribution on the training
set S which is typically assumed to be the uniform distribution. Thus, for given T and
leaf l from T , and for a given S, our goal is to nd the function h that has the maximum
value (T; l; h), where (T; l; denoted by h ? this
function.
As we mentioned, if we have a large dataset, a more e-cient way to attack this
problem is the following. For a given tree T and leaf l, take a sample from X and output
the function h that has the highest value (T; l; h) in the sample. If the sample size
is chosen appropriately, the value of (T; l; h), where h is the function output by this
algorithm, is close to (T; l; h ? ). We can apply our algorithm to use the appropriate
amount of data as follows. We use F for H and (T; l; h) for U(h; X) 5 . It only remains
to determine the constant c for the Lipschitz condition on U . Notice that U is just the
addition of three G functions over dierent inputs. Thus, if G is Lipschitz for certain
constant c so it is U . Here we just state how to obtain the Lipschitz constant for G and
leave to the reader the calculation of the appropriate constant for the whole function U .
If G(q) is the Gini index, then its derivative is G 0
4. Thus, by the Mean Value Theorem, the Lipschitz constant is 4. If G(q) is
the binary entropy H(q) or the improved splitting criterion
presented
in [6], its derivatives are not bounded in the [0; 1] range and therefore it cannot be a
xed constant that works for all the possible values. However, suppose that we ignore
the input values very close to 0 or 1 and we consider, for instance, the interval [0:05; 0:95]
then both functions have Lipschitz constant 5 in that interval. Notice that the inputs for
the function G are estimated in the sample. Thus, the above assumption makes sense
since we have to admit certain error for those values. Thus, we can now run our algorithm
with inputs H, U , d as discussed above and the desired accuracy  and condence level
-; then the algorithm outputs, with probability larger than 1 -, a node function h such
that (T; l; h)  (1 )(T; that again, the crucial point is in the choice
5 Precisely speaking, (T ; l; h) does not t to our denition of U(h; X), but it is easy to see that our
algorithm also works for this situation.
of U . Moreover, according to the results in [6], any h such that (T; l; h)  (T;
should su-ce to reduce the overall error of the whole tree after adding the new internal
node; thus, we can x  to be just 1=2.
We now informally described another possible application of our algorithm to a problem
in decision tree induction, the problem of nding a good cutting point for a continuous
attribute in order to discretize it. In this case, every function in H should represent a
possible cutting point. Even though the total number of cutting points is innite, notice
that we only need to consider cutting points that appears in the dataset set considered;
thus, there are at most k of them, where k is the size of X. Although X might be very
big, notice that the bound given in Theorem 4 depends only logarithmically in the size of
H. Thus, for this particular application, the size of X gives us an upper bound on the size
of H. Furthermore, notice that for running our algorithm we do not need to have all the
functions in H a priori. So every time that a new example reveals a new possible cutting
point, we can just add that new function to the class and calculate its utility function on
the examples seen so far. The utility function in this case is the splitting criterion used
to compare splitting functions as described above. Thus, our algorithm for this problem
would choose an almost optimal, with respect to some splitting criterion, cutting point
for a particular continuous attribute. Once this is done we can use that attribute as a
discrete attribute to decide which attribute is used to label the node we are building.
5 Further Improvements
In this section we describe some improvements that can be incorporated into the main
algorithm AdaSelect. Some of these have a completely rigorous justication; others seem
intuitively clear but harder to capture in a form of theorem.
Use (multiplicative) Cherno bounds instead of (additive) Hoeding bounds.-
We have developed algorithm AdaSelect using the Hoeding bound, in which the deviation
from the average value appears additively. In some cases, it is also possible to use
Cherno's bound, in which the deviation appears multiplicatively. The proof is slightly
more involved, because applying Cherno seems to require previous knowledge of the expected
value of the utility function, which is precisely what we re trying to estimate, but
some careful, also adaptive, application lets us circumvent this problem for some utility
functions. In particular, this can be done for the case where F is the identity function
plus or minus a constant in [0; 1], as in the problem of model or hypothesis selection. In
this case, using Cherno has a clear advantage for the case of small probabilities. More
precisely, we can then bound the number of examples by O(1=
the dependence on 1=U(h ? ) to linear instead of quadratic). Although this seems asymptotically
better, the hidden constant is bigger (precisely, we had 1=2 and now we have
and thus, it happens to be better for U(h ? ) < 1=6.
Considering the variance.- In some cases, it may not be true that the values of y hx
always are in [0; d] for a moderate d, just so with large probability. There are versions of
Hoeding, the so called Berstein bounds, that, instead of this assumption, incorporate the
variance of the y hx into the bound. When estimates of these variances are known, plugging
them into AdaSelect may give quite an advantage over using a worst-case constant d.
Adapting to the local Lipschitz constant.- Our bound depends on the constant c,
which is the global Lipschitz constant of F . However, in many regions a much smaller
constant may be enough to bound the growth rate of F . Consider for example the entropy-
style functions discussed for decision-tree induction. We saw there that an appropriate
choice for c is around 4 or 5, for probabilities near 0 and 1. However, for probabilities
near 1=2, a quite common case, these functions are almost
at, i.e., a c much closer to 0
should su-ce. In practice, one should probably use at each step the worst-case Lipschitz
constant within the uncertainty interval of U(h), i.e., [U(h; S t It is
di-cult to give a rigorous analysis of this new version, but it is intuitively clear that this
may result in a signicant improvement while essentially not aecting reliability.
6 Concluding Remarks
We have presented a new methodology for sampling that, while keeping all the theoretical
guarantees of previous ones, it is applicable in a wider setting and moreover, it is very
likely that it is useful in practice. The key point was that, rather than deciding a priori
the sample size and obtain it in batch, our algorithm performs sampling sequentially and
maintains a stopping condition that depends on the problem at hand. In future work,
we should verify the advantage of our approach experimentally. Although the theorem
provided in this paper suggests that our algorithm might be e-ciently applicable in several
domains, there is still plenty of work to test whether this assertion is true or not. On one
hand, our algorithm will take prot of non being in a worst case situation, and therefore,
it is very likely that it will outperform the usual batch sampling approach. On the other
hand, asymptotics alone do not guarantee practicality since a huge constant might spoil all
the advantage of sampling over using all data, even if the most e-cient sampling algorithm
is used. We have tested this second point in our preliminary work [3, 4] using synthetic
data so we could test a wide range of values and the results are very promising. The
sample size used by our method greatly outperform the one used by the batch approach.
Moreover, the sample size was, in many cases, reasonable small so that it suggested that
reducing the data size through sampling with our algorithm might allows us to improve
the overall running time. The experimental results in [10], although in a dierent context,
are also very encouraging. In any case, it remains to do experiments using real world data
to test the real practicality of our algorithm.
Furthermore, we have pointed our several improvements that one might perform when
applying the algorithm for a particular situation. Due to the generality of our approach,
every application deserves an individual and deeper study to see the possible enhancements
that one can do for a particular setting.

Acknowledgments

We would like to thank Heikki Mannila for pointing us the work in sampling for database
query estimation and for encouraging us to follow up our previous research on adaptive
sampling. We would also like to thank Chris Watkins for telling us about Hoeding races
and Pedro Domingos for pointing us to several related machine learning papers.



--R

Multiple Sampling with Constant Probability.
A Method of Sampling Inspection.
Ricard Gavald
Ricard Gavald
A decision-theoretic generalization of on-line learning and an application to boosting
On the boosting ability of top-down decision tree learning algorithms
An Introduction to Computational Learning Theory.
The power of sampling in knowledge discovery.
and Je



Randomized Algorithms.
Decision Theoretic Subsampling for Induction on Large Databases.
Sampling large databases for association rules.
Sequential Analysis.
Bala Iyer and Je
An algorithm for multi-relational discovery of subgroups
--TR

--CTR
Geoff Hulten , Pedro Domingos, Mining complex models from arbitrarily large databases in constant time, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Szymon Jaroszewicz , Tobias Scheffer, Fast discovery of unexpected patterns in data, relative to a Bayesian network, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Osamu Watanabe, Sequential sampling techniques for algorithmic learning theory, Theoretical Computer Science, v.348 n.1, p.3-14, 2 December 2005
Huan Liu , Hiroshi Motoda, On Issues of Instance Selection, Data Mining and Knowledge Discovery, v.6 n.2, p.115-130, April 2002
Jaekyung Yang , Sigurdur Olafsson, Optimization-based feature selection with adaptive instance sampling, Computers and Operations Research, v.33 n.11, p.3088-3106, November 2006
Pierre-Alain Laur , Richard Nock , Jean-Emile Symphor , Pascal Poncelet, Mining evolving data streams for frequent patterns, Pattern Recognition, v.40 n.2, p.492-503, February, 2007
data mining;concentration bounds;scalability;adaptive sampling;knowledge discovery