Improving Generalization with Active Learning.
Active learning differs from learning from examples in that the learning algorithm assumes at least some control over what part of the input domain it receives information about. In some situations, active learning is provably more powerful than learning from examples alone, giving better generalization for a fixed number of training examples.In this article, we consider the problem of learning a binary concept in the absence of noise. We describe a formalism for active concept learning called selective sampling and show how it may be approximately implemented by a neural network. In selective sampling, a learner receives distribution information from the environment and queries an oracle on parts of the domain it considers useful. We test our implementation, called an SG-network, on three domains and observe significant improvement in generalization.
Introduction
vs. Active Learning
Most neural network generalization problems are studied only with respect to random sampling: the training
examples are chosen at random, and the network is simply a passive learner. This approach is generally
referred to as "learning from examples." Baum and Haussler (1989), examine the problem analytically for
neural networks; Cohn and Tesauro (1992) provide an empirical study of neural network generalization when
learning from examples. There have also been a number of empirical efforts, such as Le Cun et al. (1990),
aimed at improving neural network generalization when learning from examples.
Learning from examples is not, however, a universally applicable paradigm. Many natural learning
systems are not simply passive, but instead make use of at least some form of active learning to examine the
problem domain. By active learning, we mean any form of learning in which the learning program has some
control over the inputs it trains on. In natural systems (such as humans), this phenomenon is exhibited at
both high levels (e.g. active examination of objects) and low, subconscious levels (e.g. Fernald and Kuhl's
(1987) work on infant reactions to "Motherese" speech).
Within the broad definition of active learning, we will restrict our attention to the simple and intuitive
form of concept learning via membership queries. In a membership query, the learner queries a point in the
input domain and an oracle returns the classification of that point. Much work in formal learning theory
has been directed to the study of queries (see e.g.: Angluin 1986, Valiant 1984), but only very recently have
queries been examined with respect to their role in improving generalization behavior.
In many formal problems, active learning is provably more powerful than passively learning from randomly
given examples. A simple example is that of locating a boundary on the unit line interval. In order to achieve
an expected position error of less than ffl, one would need to draw O( 1
training examples. If
As published in Machine Learning 15(2):201-221, 1994. A preliminary version of this paper appears as (Cohn et al., 1990).
one is allowed to sequentially make membership queries, then binary search is possible and, assuming a
uniform distribution, a position error of ffl may be reached with O(ln( 1
queries.
One can imagine any number of algorithms for employing membership queries to do active learning. We
have been studying the problem of learning binary concepts in an error-free environment. For such problems,
a learner may proceed by examining the information already given and determining a region of uncertainty,
an area in the domain where it believes misclassification is still possible. The learner then asks for examples
exclusively from that region. This paper discusses a formalization of this simple approach, which we call
selective sampling.
In Section 2, we describe the concept learning problem in detail and give a formal definition of selective
sampling, describing the conditions necessary for the approach to be useful. In Section 3 we describe the
SG-network, a neural network implementation of this technique inspired by version-space search (Mitchell,
1982). Section 4 contains the results of testing this implementation on several different problem domains,
and Section 5 discusses some of the limitations of the selective sampling approach. Sections 6 and 7 contain
reference to related work in the field and a concluding discussion of the paper.
Concept Learning and Selective Sampling
Given an arbitrary domain X, we define a concept c to be some subset of points in the domain. For example,
X might be a two-dimensional space, and c might be the set of all points lying inside a fixed rectangle in the
plane. We classify a point x 2 X by its membership in concept c: we write
otherwise. A popular use of artificial neural networks is as concept classifiers: x is presented as the input
to an appropriately trained network, which then activates a designated output node above some threshold
if and only if x 2 c, that is, if x is an instance of concept c. Formally, a concept class C is a set of concepts,
usually described by some description language. In the above example, our class C may be the set of all
two-dimensional, axis-parallel rectangles (see Figure 1). In the case of neural networks, the concept class is
usually the set of all concepts that the network may be trained to classify.10000011
Figure

1: A concept class defined as the set of all axis-parallel rectangles in two dimensions. Several positive
and negative examples are depicted, as are several consistent concepts in the class.
2.1 Generalization
For target concept t, a training example is a pair (x; t(x)) consisting of a point x (usually drawn from some
distribution P), and the point's classification t(x). If x 2 t, then and we say that (x; t(x)) is a
positive example. Otherwise, is a negative example. A concept c is consistent with
an example (x; t(x)) if c(x) = t(x), that is, if the concept produces the same classification of point x as the
target. The error of c, with respect to t and distribution P, is the probability that c and t will disagree on
a random example drawn from P. We write this as
randomly according to P.
The generalization problem is posed as follows: for a given concept class C, an unknown target t, an
arbitrary error rate ffl and confidence ffi , how many examples do we have to draw and classify from an arbitrary
distribution P in order to find a concept c 2 C consistent with the examples such that ffl(c; t; P) - ffl with
confidence at least This problem was formalized by Valiant (1984) and has been studied for neural
networks in (Baum and Haussler, 1989) and (Haussler, 1989).1100000011

Figure

2: The region of uncertainty, R(S m ), is the set of all points x in the domain such that there are two
concepts that are consistent with all training examples in S m and yet disagree on the classification of x.
2.2 The region of uncertainty
If we consider a concept class C and a set S m of m examples, the classification of some regions of the domain
may be implicitly determined (Figure 2); all concepts in C that are consistent with all of the instances
may agree in these parts. What we are interested in here is the areas that are not determined by available
information - what we define to be the region of uncertainty:
are consistent with all s
For an arbitrary distribution P, we can define the size of this region as
in an incremental learning procedure, as we classify and train on more examples, ff will be monotonically
non-increasing. A point that falls outside R(S m ) will leave it unchanged; a point inside will further restrict
the region. Thus, ff is the probability that a new, random point from P will reduce our uncertainty.
As such, R(S m ) serves as an envelope for consistent concepts; any disagreement between those concepts
must lie within R(S m ). Because of this, R(S m ) also bounds the potential error of any consistent hypothesis
we choose. If the error of our current hypothesis is ffl, then ffl - ff. Since we have no basis for changing our
current hypothesis without a contradicting point, ff is also a bound on the probability of an additional point
reducing our error.
2.3 Selective sampling is active learning
Let us consider learning as a sequential process, drawing examples one after another, and determine how
much information each successive example gives us. If we draw at random over the whole domain, then
the probability that an individual sample will reduce our error is ff, as defined above, which decreases to
zero as the we draw more and more examples. This means that the efficiency of the learning process also
approaches zero; eventually, most examples we draw will provide us with no information about the concept
we are trying to learn.
Now consider what happens if we recalculate R(S m ), the region of uncertainty after each new example,
and draw examples only from within R(S m ). Then each example will reduce R(S m ), and will reduce our
uncertainty, with no decrease in efficiency as we draw more and more examples. We call this process selective
sampling.
If the distribution P is known (e.g. P is uniform), then we perform selective sampling directly by
randomly querying points (according to P) that lie strictly inside R(S m ). Frequently however, the sample
distribution, as well as the target concept is unknown. In this case, we cannot choose points from our domain
with impugnity or we risk assuming a distribution that differs greatly from the actual underlying P. In many
problems, though, we can still make use of distribution information without having to pay the full cost of
drawing and classifying an example. Rather than assuming that the drawing of a classified example is an
atomic operation (as in Valiant, 1984 and Blumer et al., 1988), we may divide the operation into two steps:
first, that of drawing an unclassified example from the distribution, and second, querying the classification
of that point. If the cost of drawing a point from our distribution is small compared to the cost of finding
the point's proper classification, we can ``filter'' points drawn from our distribution, drawing at random, but
only selecting, classifying and training on those that fall in R(S m ). This approach is well suited to problems
such as speech recognition, where unlabeled speech data is plentiful, but the classifying (labeling) of speech
segments is a laborious process.
Training set size
50 100 150 200
random sampling
pass sampling
3 pass sampling
4 pass sampling
pass sampling
pass sampling

Figure

3: As the batch size in selective sampling approaches one, the process yields diminishing improvements
for the added computational costs. This figure plots error vs. training set size for selective sampling using
different batch sizes for learning an axis-parallel rectangle in two dimensions.
Since calculating R(S m ) may be computationally expensive, we may want to perform selective sampling
in batches. On the first pass, we draw an initial batch of training examples S m
0 from P train on it, and
determine the the initial R(S m ). We then define a new distribution P 0 to sample from that is zero outside
maintains the relative distribution of P inside R(S m
We can then make a second pass, drawing
a second batch of training examples S m
adding it to the first, and determining a new, smaller R(S m
The smaller the batch size is, and the more passes are made, the more efficiently the algorithm will draw
training examples (see Figure 3). However, since R(S m ) is recalculated on each pass, this advantage must
be weighed against the added computational cost incurred in this calculation.
2.4 Approximations to selective sampling
Even for simple concept classes, such as the set of all axis-parallel rectangles in two dimensions, it may
be difficult or computationally expensive to exactly represent the region of uncertainty. For the class of
rectangles, negative examples that lie along the corners of the region can add complexity by causing "nicks"
in the outer corners of R(S m ) (as in Figure 2). With more realistic, complicated classes, representing
exactly can easily become a difficult, if not impossible, task. Using a good approximation of R(S m )
may, however, be sufficient to allow selective sampling. Practical implementations of selective sampling are
possible with a number of approximations to the process, including maintaining a close superset or subset
of R(S m ).
Assume we are able to maintain a superset R any point in R(S m ) will also be in
the superset, we can selectively sample inside R be assured that we will not exclude any part of
the domain that is of interest. The penalty we pay is that of efficiency: we may also train on some points
that are not of interest. The efficiency of this approach, as compared with pure selective sampling, can be
measured as the ratio P r[x
If we are only able to maintain a subset R our sampling and training algorithm must
take additional precautions. On any given iteration, some part of R(S m ) will be excluded from sampling.
Because of this, we will need to ensure that on successive iterations we will choose subsets that cover the
entire region of uncertainty (an example of this technique will be discussed in the next section). We will
also need to keep the number of examples on each iteration small to prevent oversampling of one part of the
domain.
For the remainder of this paper, we will denote an arbitrary algorithm's approximation to the true region
of uncertainty as R   (S m ).
3 Neural Networks for Selective Sampling
The selective sampling approach holds promise for improved generalization in many trainable classifiers. The
remainder of this paper is concerned with demonstrating how an approximation of selective sampling may
be implemented using a feedforward neural network trained with error backpropagation.
The backpropagation algorithm (Rumelhart et al., 1986) is a supervised neural network learning technique,
in that the network is presented with a training set of input/output pairs (x; t(x)) and learns to output t(x)
when given input x. To train a neural network using standard backpropagation, we take training example
(x; t(x)) and copy x into the input nodes of the network (as in Figure 4). 1 We then calculate the individual
neuron outputs layer by layer, beginning at the first "hidden" layer and proceeding through the output layer.
The output of neuron j is computed as
where w j;i is the connection weight to neuron j from neuron i, and
"squashing" function that produces neuron outputs in the range [0; 1]. We define the error of the output
node n as This error value is propagated back through the network (see Rumelhart
et al., 1986 for details), so that each neuron j has an error term (x). The connection weights w j;i are then
adjusted by adding
\Deltaw ji
where j is a constant "learning rate."
This adjustment incrementally decreases the error of the network on example (x; t(x)). By presenting
each training example in turn, a sufficiently large network will generally converge to a set of weights where
We assume that all inputs have been normalized to the range [0; 1].
first
hidden
layer
second
hidden
layer
output
layer
input
layer
network output
network
input
connection weights

Figure

4: A simple feedforward neural network. Each node computes the weighted sum of its inputs, passes
that sum through a sigmoidal "squashing" function, and passes the result on as its output.
the network has acceptably small error on each training example. In the concept learning model, the target
values of training examples are 1 or 0, depending on whether or not the input is an instance of the concept
being learned. Patterns are trained on until their error is less than some threshold.
At this point, we need to draw attention to the distinction between a neural network's architecture and
its configuration. 2 The architecture of a neural network refers to those parameters of the network that do
not change during training; in our case, this will be the network's topology and transfer functions. The
configuration of a network refers to the network parameters that do change during training: in this case,
the weights given to each of the connections between the neurons. Although there are network training
algorithms that involve changing a network's topology during training (e.g. Ash, 1989), we consider here
only those with fixed topologies that train by weight adjustment. The theory and methods described here
should, with some modification, be equally applicable to other trainable classifiers.
For a neural network architecture with a single output node, the concept class C is specified by the set
of all configurations that the network can take on. Each of these configurations implements a mapping from
an input x to an output in [0; 1], and many configurations may implement the same mapping. If we set a
threshold (such as 0.5) on the output, then we may say that a particular configuration ~ c represents a concept
c such that x 2 c if and only if ~ c(x) ? 0:5 (see Figure 5). Having trained on training set S m then, we can
say that the network configuration ~ c implements a concept c that is consistent with training set S m . Below,
we will use c to denote both the concept c and the network ~ c that implements it.
Below, we consider a na-ive algorithm for selective sampling with neural networks and examine its short-
comings. We then describe the SG-net, based on the version-space paradigm (Mitchell, 1982), that overcomes
these difficulties.
3.1 A na-ive neural network querying algorithm
The observation that a neural network implementation of a concept learner may produce a real-valued
output that is thresholded suggests a na-ive algorithm for defining a region of uncertainty. When a network
is trained with these tolerances, we can divide all points in the domain into one of three classifications:
"1" (0.9 or greater), "0" (0.1 or less), and "uncertain" (between 0.1 and 0.9). We may say that this last
category corresponds to a region where the network is uncertain, and may thus define it to be R   (S m ), our
approximation to the region of uncertainty (Figure 6).
The problem with applying this approach is that it measures only the uncertainty of that particular
configuration, not the uncertainty among configurations possible given the architecture. While it is in fact
2 The terminology is that of Judd (1988).

Figure

5: The thresholded output of the trained neural network ~ c serves as a classifier representing a concept
c that is (hopefully) similar to the unknown target concept.
a part of R(S m ), the full region is comprised of the differences between all possible consistent network
configurations.
This limitation is exacerbated by the inductive bias of some learning algorithms, including backpropa-
gation. The backpropagation algorithm, when attempting to classify a set of points, tends to draw sharp
distinctions and become "overly confident" in regions that are still unknown. As a result, the R   (S m ) chosen
by this method will in general be a very small subset of the true region of uncertainty.
A pathological example of this behavior is exhibited in Figures 7a and 7b. In Figure 7a, the initial random
sampling has failed to yield any positive examples in the triangle on the right. Training by backpropagation
on the examples yields a region of uncertainty (between the two contours) that concentrates on the left half
of the domain, completely to the exclusion of the right. The final result of 10 iterations of querying and
learning is shown in Figure 7b. This strategy (and related ones) is prone to failure of this form whenever
there are regions of detail in the target concept that are not discovered in the initial random sampling stage.
3.2 Version space
Mitchell (1982) describes a learning procedure based on the partial ordering in generality of the concepts
being learned. Some concept c 1 is "more general" than another concept c 2 if and only if c 2 ae c 1 . If c 1 6ae c 2
and c 2 6ae c 1 , then the two concepts are incomparable. For a concept class C and a set of examples S m ,
the version space is the subset is consistent with all s g. To bound the
concepts in the version space, we can maintain two subsets, is the set of all "most specific"
consistent concepts, that is,
cg. Similarly,
is the set of "most general" concepts. For any consistent concept c, it must be the case that s ' c ' g for
some s 2 S and g 2 G.
One may do active learning with a version space by examining instances that fall in the "difference" of
S and G, that is, the region S
(where \Delta is the symmetric difference operator).
If an instance in this region proves positive, then some s in S will have to generalize to accommodate the
new information; if it proves negative, some g in G will have to be modified to exclude it. In either case, the
version space, the space of plausible hypotheses, is reduced with every query.
3.3 Implementing an active version-space search
Since an entire neural network configuration represents a single concept, a complete version space cannot be
directly represented by any single neural network. In fact, Haussler (1987) pointed out that the size of the

Figure

na-ive approach to representing the region of uncertainty: we can use the network's transition
area between 0 and 1 to represent the part of the domain where the network is "uncertain."
S and G sets could grow exponentially in the size of the training set. Representing these sets completely
would require keeping track of and manipulating an exponential number of network configurations.
We can, however, modify the version-space search to make the problem tractable. This can be done if
we impose, according to the distribution P, a strict index of ordering on all concepts in the class. We will
define a concept c 1 to be "more general" than concept c 2 if and only if for a random point x drawn from
this definition, the generality of all concepts in the class is comparable,
and it makes sense to speak of an ordering in which we can represent a single "most general" concept g and
a single "most specific" concept s. There may still be many concepts with the same generality, but this is
no impediment. We need only know that there are no concepts, in the "most general" case, with a greater
generality than the concept g we have chosen.
By maintaining these two concepts, we have a window into our version space: R   (S m s\Deltag will be a
subset of S \DeltaG. Thus, a point x guaranteed to reduce the size of our version space. If positive,
it will invalidate s and leave us with another s, either a more general one, or an equally specific one that
includes the new point. Similarly, if the new point is classified as negative, it will invalidate g. By proceeding
in this fashion, we can approximate a step-by-step traversal of the S and G sets using a fixed representation
size.
3.4 The SG-net: a neural network version-space search algorithm
Since we are interested in selecting examples that improve the generalization behavior of some given neural
network architecture N , we define the concept class in question to be the the set of concepts learnable by N
with its learning algorithm. If we can manage to obtain network configurations that represent the s and g
concepts described above, then it is a simple matter to implement the modified version-space search. In the
following two subsections, we first describe how one may learn a "most specific" or "most general" concept
associated with a network, and then describe how these two networks may be used to selectively sample the
R   (S m ) defined by regions where they disagree.
3.4.1 Implementing a "most specific/general" network
Below, we describe how one may learn s, a "most specific" concept consistent with some given data. The
case for learning g, a "most general" concept, is analogous.
A most specific network for a set of examples S m (according to distribution P), is one that classifies as
positive those example points that are in fact positive and classifies as negative as much as possible of the
rest of the domain. This requirement amounts to choosing a c consistent with S m that minimizes P r[x 2 c].

Figure

7: A pathological example of na-ive network querying. In (a) on left, an initial random sample has
failed to detect the second, disjoint region of the target concept. In (b) on right, after 10 successive iterations
then, the na-ive querying algorithm has ignored that region and concentrated on the region where is has seen
examples. The dotted line denotes the true boundary of the unknown target concept.
Such a network may be arrived at by employing an inductive bias. An inductive bias is a predisposition of
a learning algorithm for some solutions over others. Most learning algorithms inherently have at least some
form of an inductive bias, whether it is a preference for simple solutions over complex ones, or a tendency
to choose solutions where the absolute values of the parameters remain small. 3
What we will do is explicitly add a new inductive bias to the backpropagation algorithm: by penalizing
the network for any part of the domain that it classifies as positive, we add a bias that prefers specific
concepts over general ones. The weight of this penalty must be carefully adjusted: if it is large enough to
outweigh the training examples, the network will not converge on the training data. It must, however, be
large enough to outweigh any other inductive bias in the learning algorithm, and force it to find a most
specific configuration consistent with S m .
This "negative" bias may be implemented by drawing unclassified points from P (or creating them in the
case where P is known), and arbitrarily labeling them as negative examples. We then add these "background"
examples to the training set (Figure 8). This creates a background bias over the domain that is weighted by
the input distribution P: the networks that have the least error on these background patterns will be the
ones that are the most specific according to P.
In order to allow the network to converge on the actual training examples in spite of the background
examples, we must balance the influence of background examples against that of the training data. As the
network learns training example x, the error term Equation 1 will approach zero, while the error term
of an arbitrary background example y may remain constant. Unless the "push" that the random background
example exerts on the network weights (\Deltaw ji (y)) is decreased to match that of the normal training examples
(\Deltaw ji (x)), the background examples will dominate and network will not converge on a solution.
We achieve balance by using different learning rates for training examples and background examples. We
dynamically decrease the background learning rate as a function of the network's error on the training set.
Each time we present a training example x, we calculate a new background learning rate
is the error of the network on x, and is a constant. We then train on a single background
3 The inductive biases inherent in backpropagation have not been well studied, but there appears to be a tendency to fit the
data using the smallest number of units possible.

Figure

8: Training on a large number of "background" points in addition to the regular training data forces
the network into a "most specific" configuration.
example using this value of j 0 and repeat. Formally, the algorithm is as follows:
1. Initialize network to random configuration c.
2. If for all actual training examples (x;
3. Otherwise, select next actual training example (x; t(x)).
4. Calculate the output error of network c on input x, backpropagate through the
network, adjusting weights according to
\Deltaw ji
5. Calculate new background learning rate
6. Draw a point y from P and create background example (y; 0).
7. Calculate the output error backpropagate through the network, adjusting weights
according to the modified equation
\Deltaw ji
7. Go to Step 2.
Optimally, fl should be set such that the weight update on the background patterns is always infinitesimally
smaller than the weight update on the actual training patterns, allowing the network to "anneal" to
a most specific configuration. This however, requires a prohibitive amount of training time. Empirically,
we have found that setting provides an adequate bias and still allows convergence in a reasonable
number of iterations.
A similar procedure can be used to produce a "most general" network, adding a positive inductive bias
by classifying all background points drawn from P as positive.
3.4.2 Implementing active learning with an SG-net
Once we can represent concepts s and g, it is a simple matter to test a point x for membership in R   (S m )
by determining if s(x) 6= g(x). Selective sampling may then be implemented as follows: if a point drawn
from the distribution is not in s\Deltag (if the two networks agree on their classification of it), then the point
is discarded. If point is in s\Deltag, then its true classification is queried and it is added to the training set. In
practice, we can merge the inputs of the s and g networks, as illustrated in Figure 9, and train both together.
It is important to note that this technique is somewhat robust, in that its failure modes degrade the
efficiency of a single sampling iteration rather than causing overall failure of the learning process. If either
typical network
architecture
split into separate
s and g networks
inputs merged to
G
G

Figure

9: Construction of an SG-network equivalent to the original.
the s or g networks fail to converge on the training data, the points that failed to converge will be contained
in s\Deltag, and that region will be eligible for additional sampling on the next iteration. In most cases, we have
found that these additional examples will suffice to "push" the network out of its local minimum.
If the network does converge on the training set, but settles on solutions that are not near the most
specific/general networks consistent with the data, the examples gleaned in the next iteration are still useful.
Since they were chosen by virtue of lying in areas where the two networks disagreed, the points will settle
discrepancies between the two. This may lead to some oversampling of the region, but will not, in and of
itself, cause the technique to fail.
The effects of these two failure modes can be minimized by keeping the number of examples taken on
each iteration small. This increases the efficiency of the learning process in terms of the number of examples
classified, but as we have observed, there is a tradeoff in the computational resources required. Each time
new data is added to the training set, the network may have to completely readjust itself to incorporate
the new information. We have found that in practice, with large training set sizes, it is often most efficient
to simply retrain the entire network from scratch when new examples are added. Recent work by Pratt
offers hope that this retraining may be made more efficient by use of "information transfer" strategies
between iterations.
4 Experimental Results
Experiments using selective sampling were run on three types of problems: solving a simple boundary-
recognition problem in two dimensions, learning a 25-input real-valued threshold function, and recognizing
the secure region of a small power system.
4.1 The triangle learner
A two-input network with two hidden layers of 8 and 3 units and a single output was trained on a uniform
distribution of examples that were positive inside a pair of triangles and negative elsewhere. This task was
chosen because of its intuitive visual appeal and because it requires learning a non-connected concept - a
task that demands more from the training algorithm (and sample selection scheme) than a simple convex
shape.
The baseline case consisted of 12 networks trained on randomly drawn examples with training set sizes
from 10 to 150 points in increments of 10 examples. Eight test cases were run on the same architecture
with data selected by four runs of an SG-network using 15 selective sampling iterations of 10 examples each

Figures

10a and 10b). Additionally, 12 runs of the na-ive querying algorithm described in Section 3.1 were
run for comparison.
The networks trained on the selectively sampled data showed marked, consistent improvement over both
the randomly sampled networks and the ones trained with na-ive querying (Figure 11). The na-ive querying
algorithm displayed much more erratic performance than the other two algorithms, possibly due to the
pathological nature of its failure modes.

Figure

10: The triangle learner problem. When learned by 150 random examples in (a) on left, and when
learned by 150 examples drawn in 15 passes of selective sampling in (b) on right. The dotted line denotes
the true boundary of the unknown target concept.
4.2 Real-valued threshold function
We used the 25-bit real-valued threshold problem as a quantitative measure of network performance on a
simple but higher-dimensional problem. Six runs of selective sampling, using iterations of 10 examples per
iteration, were trained on the problem and compared to 12 identical networks trained with randomly sampled
data. The results (Figure 12) indicate a much steeper learning curve for selective sampling.
Plotting the generalization error against the number of training examples m, networks trained on the
randomly sampled data exhibited a roughly polynomial curve, as would be expected following Blumer et
al. (1988). Using simple linear regression on 1
ffl , the error data fit
with a coefficient of determination (r 2 ) of 0:987. Networks trained on the selectively sampled
data, by comparison, fit indicating that its fit to the polynomial was not
as good.
Visually, the selectively sampled networks exhibited a steeper drop in the generalization error, as would be
expected from an active learning method. Using linear regression on the natural logarithm of the errors, the
selectively sampled networks exhibited a decrease in generalization error matching
until the error drops below 1.5%), indicating a good fit to the exponential
curve. By comparison, the randomly sampled networks' fit to
In this domain, the SG-network appears to provide and almost exponential improvement in generalization
with increasing training set size, much as one would expect from a good active learning algorithm. This
suggests that the SG-network represents a good approximation to the region of uncertainty (in this domain)
and thus implements a good approximation of selective sampling.
Additional experiments, run using 2, 3, 4, and 20 iterations indicate than the error decreases as the
sampling process is broken up into smaller, more frequent iterations. This observation is consistent with an
increased efficiency of sampling as new information was incorporated earlier into the sampling process.
4.3 Power system security analysis
If various load parameters of an electrical power system are within a certain range, the system is secure.
Otherwise it risks thermal overload and brown-out. Previous research (Aggoune et al., 1989) determined that
this problem was amenable to neural network learning, but that random sampling of the problem domain
was inefficient in terms of examples needed. The range of parameters over which the system will be run
is known, so distribution information is readily available. For each set of parameters (each point in the
domain), one can analytically determine whether the system is secure, but this must be done by solving a
Training set size
50 100 150
0.3 random sampling
naive querying
selective sampling

Figure

Generalization error vs. training set size for random sampling, na-ive querying, and selective
sampling. The irregularity of the na-ive querying algorithm's error may be due to its intermittent failure to
find both triangles in the intial random sample.
time-consuming system of equations. Thus, since the classification of a point is much more expensive than
the determination of an input distribution, the problem is amenable to solution by selective sampling.
The baseline case of random sampling in four dimensions studied by Hwang et al. (1990), was used for
comparison. In our experiments, we ran six sets of networks on the initial, random training sets (with 500
data points) and added a single iteration of selective sampling. Networks were trained on a small second
iteration of 300 points (for a total of 800) as well as a large second iteration of 2000 (for a total of 2500
points). These results were compared to the baseline cases of 800 and 2500 points of randomly sampled data.
We estimated the network errors by testing on 14,979 randomly drawn test points. The improvement
that the single extra iteration of selective sampling yielded for the small set was over 10.7% of the total
error (5.17% instead of 5.47%), while on the large set it resulted in an improvement of 12.6% of total (4.21%
instead of 4.82%). This difference is significant with greater than 90% confidence.
5 Limitations of the Selective Sampling Approach
There are a number of limitations to the selective sampling approach; some are practical, as mentioned in
the previous section discussing implementations of the technique, while others are more theoretical.
5.1 Practical limitations
As discussed earlier in this paper, an exact implementation of selective sampling is practical only for relatively
simple concept classes. As the class becomes more complex, it becomes difficult to compute and maintain
an accurate approximation of R(S m ).
In the case of maintaining a superset, increased concept complexity seems to lead to cases where R
effectively contains the entire domain, reducing the efficiency of selective sampling to that of random sam-
pling. The example in Section 2.4 illustrates this nicely: while a bounding box suffices as an approximation
Training set size
sampling
selective sampling
polynomial
exponential

Figure

12: Generalization error vs. training set size for random sampling, and selective sampling. Standard
deviation of error averages 0.00265 for the random case and 0.00116 for the selectively sampled case.
for rectangles in two dimensions, the "nicks" in such a box bounding a 20-dimensional figure could conceivably
require the approximation to contain most of the domain space.
In the case of maintaining a subset, increased concept complexity leads to an extreme where R
contains only a very small subset of R(S m ). In these cases, oversampling of regions becomes a critical
problem, and due to the inductive bias of the training algorithm, even a training set size of only one may
omit large regions of the domain.
5.2 Theoretical limitations
Selective sampling draws its power from the ability to differentiate a region of uncertainty from the bulk of
the domain. In cases where the representational complexity of the concept is large (as in a neural network
with many hidden units), however, R(S m ) can extend over the whole domain until the concept is already
well-learned. That is, even though the maximum error may be small, due to the number of places that this
error may arise, the total uncertainty may remain large. Thus, depending on the desired final error rate,
selective sampling may not come into effect until it is no longer needed. Similarly, if the input dimension is
very large, the bulk of the domain may be uncertain, even for simple concepts. One method for avoiding this
problem is the use of Bayesian probabilities to measure the degree of utility in querying various parts of the
region of uncertainty. This approach has recently been studied by David MacKay (1991), and is discussed
briefly in the following section.
6 Related Work
The work described in this paper is an extension of results published by Cohn et al. (1990). Prior to that
work, and since then, there have been many related results in active learning. There is a large body of work
studying the effects of queries from the strict learning theory viewpoint, primarily with respect to learning
formal concepts such as Boolean expressions and finite state automata.
Angluin (1986) showed that while minimal finite state automata were not polynomially learnable (in the
Valiant sense) from examples alone, they could be learned using a polynomial number of queries to an oracle
that provides counter-examples. Valiant (1984) considers various classes that are learnable using a variety
of forms of active learning.
Work by Eisenberg and Rivest (1990) puts bounds on the degree to which membership queries examples
can help generalization when the underlying distribution is unknown. Additionally, given certain smoothness
constraints on the distribution, they describe how queries may be used to learn the class of initial segments
on the unit line.
Actual implementations of querying systems for learning have only recently been explored. Work done
by Hwang et al. (1990) implements querying for neural networks by means of inverting the activation of a
trained network to determine where it is uncertain. This approach shows promise for concept learning in
cases with relatively compact, connected concepts, and has already produced impressive results on the power
system static security problem. It is, however, susceptible to the pathology discussed in Section 3.1. An
algorithm due to Baum and Lang (1991), uses queries to reduce the computational costs of training a single
hidden-layer neural network. Their algorithm makes queries that allow the network to efficiently determine
the connection weights from the input layer to the hidden layer.
Seung et al. (1992) independently proposed a similar scheme for selecting queries, basing it on a lack
of consensus in a "committee" of learners. Freund et al. (1993) showed that as the size of the committee
increases beyond the two learners used in selective sampling, the accuracy of one's ``utility'' estimate increases
sharply.
Work by David MacKay (1992) pursues a related approach to data selection using Bayesian analysis. By
assigning prior probabilities to each concept (or each network configuration) one can determine the utility of
querying various parts of R(S m ). The fact that a point lies within R(S m ) means that there are consistent
configurations that disagree on the classification of that point. If that point is on the edge of R(S m ) though,
it may be that only a very few configurations disagree, and querying the point will only decrease the size
of R(S m ) by an infinitesimally small amount. Using Bayesian analysis, one may, in effect, determine the
"number" of configurations that disagree on a given point, and thus determine what parts of R(S m ) are
most uncertain.
7 Conclusion
In this paper we have presented a theory of selective sampling, described a neural network implementation
of the theory, and examined the performance of the resulting system in several domains.
Selective sampling is a very rudimentary form of active learning, but it has the benefit of a formal
grounding in learning theory. In the neural network implementation tested, it demonstrates significant
improvement over passive random sampling techniques on a number of simple problems.
The paradigm is suited for concept learning problems where the relevant input distribution is known, or
where the cost of obtaining an unlabeled example from the input distribution is small compared with the
cost of labeling that example. While the limitations of selective sampling become apparent on more complex
problem domains, the approach opens the door to the study of more sophisticated techniques for querying
and learning by the natural and intuitive means of active learning.

Acknowledgements

This work was supported by National Science Foundation grant number CCR-9108314, the Washington
Technology Center, and the IBM Corporation. The majority of this work was done while David Cohn was
with the Dept. of Computer Science and Engineering, University of Washington. The remainder was done
while David Cohn was at IBM T. J. Watson Research Center, Yorktown Heights, NY 10598. We would like
to thank Jai Choi and Siri Weerasooriya for their work in running simulation data for the power system
problem. We would also like to thank two anonymous referees for their suggestions on an earlier version of
this paper.



--R

Artificial neural networks for power system static security assessment.
Learning regular sets from queries and counter-examples
Dynamic node creation in backpropagation networks.
What size net gives valid generalization?
Constructing hidden units using examples and queries.
Learnability and the Vapnik-Chervonenkis dimension
Training a 3-node neural network is NP-complete
Training connectionist networks with queries and selective sampling.

How tight are the Vapnik-Chervonenkis bounds? Neural Computation <Volume>4</Volume><Issue>(2)</Issue>:<Pages>249-269</Pages>
On the sample complexity of pac-learning using random and chosen examples
Acoustic Determinants of Infant Preference for Motherese Speech.


Learning conjunctive concepts in structural domains.
Generalizing the pac model for neural nets and other learning applications.
Query learning based on boundary search and gradient computation of trained multilayer perceptrons.
On the complexity of loading shallow neural networks.
Optimal brain damage.

Generalization as search.

Learning internal representations by error propagation.


A theory of the learnable.
--TR

--CTR
Gary M. Weiss , Ye Tian, Maximizing classifier utility when training data is costly, ACM SIGKDD Explorations Newsletter, v.8 n.2, p.31-38, December 2006
Patricia G. Foschi , Huan Liu, Active learning for detecting a spectrally variable subject in color infrared imagery, Pattern Recognition Letters, v.25 n.13, p.1509-1517, 1 October 2004
Tracy Hammond , Randall Davis, Interactive learning of structural shape descriptions from automatically generated near-miss examples, Proceedings of the 11th international conference on Intelligent user interfaces, January 29-February 01, 2006, Sydney, Australia
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
A. P. Engelbrecht , R. Brits, Supervised Training Using an Unsupervised Approach to Active Learning, Neural Processing Letters, v.15 n.3, p.247-260, June 2002
Prem Melville , Foster Provost , Maytal Saar-Tsechansky , Raymond Mooney, Economical active feature-value acquisition through Expected Utility estimation, Proceedings of the 1st international workshop on Utility-based data mining, p.10-16, August 21-21, 2005, Chicago, Illinois
Rebecca Hwa, On minimizing training corpus for parser acquisition, Proceedings of the 2001 workshop on Computational Natural Language Learning, p.1-6, July 06-07, 2001, Toulouse, France
Brigham Anderson , Andrew Moore, Active learning for Hidden Markov Models: objective functions and algorithms, Proceedings of the 22nd international conference on Machine learning, p.9-16, August 07-11, 2005, Bonn, Germany
Rebecca Hwa, Sample selection for statistical grammar induction, Proceedings of the 2000 Joint SIGDAT conference on Empirical methods in natural language processing and very large corpora: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics, p.45-52, October 07-08, 2000, Hong Kong
Sean P. Engelson , Ido Dagan, Minimizing manual annotation cost in supervised training from corpora, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.319-326, June 24-27, 1996, Santa Cruz, California
Kiyonori Ohtake, Analysis of selective strategies to build a dependency-analyzed corpus, Proceedings of the COLING/ACL on Main conference poster sessions, p.635-642, July 17-18, 2006, Sydney, Australia
George K. Baah , Alexander Gray , Mary Jean Harrold, On-line anomaly detection of deployed software: a statistical machine learning approach, Proceedings of the 3rd international workshop on Software quality assurance, November 06-06, 2006, Portland, Oregon
Jason Baldridge , Miles Osborne, Active learning for HPSG parse selection, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.17-24, May 31, 2003, Edmonton, Canada
Prem Melville , Raymond J. Mooney, Diverse ensembles for active learning, Proceedings of the twenty-first international conference on Machine learning, p.74, July 04-08, 2004, Banff, Alberta, Canada
Mark Steedman , Rebecca Hwa , Stephen Clark , Miles Osborne , Anoop Sarkar , Julia Hockenmaier , Paul Ruhlen , Steven Baker , Jeremiah Crim, Example selection for bootstrapping statistical parsers, Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.157-164, May 27-June 01, 2003, Edmonton, Canada
Hinrich Schtze , Emre Velipasaoglu , Jan O. Pedersen, Performance thresholding in practical text classification, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Rebecca Hwa, Sample Selection for Statistical Parsing, Computational Linguistics, v.30 n.3, p.253-276, September 2004
James F. Bowring , James M. Rehg , Mary Jean Harrold, Active learning for automatic classification of software behavior, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
A. P. Engelbrecht, Sensitivity Analysis for Decision Boundaries, Neural Processing Letters, v.10 n.3, p.253-266, Dec. 1999
Stephen Soderland, Learning Information Extraction Rules for Semi-Structured and Free Text, Machine Learning, v.34 n.1-3, p.233-272, Feb. 1999
Michael Lindenbaum , Shaul Markovitch , Dmitry Rusakov, Selective Sampling for Nearest Neighbor Classifiers, Machine Learning, v.54 n.2, p.125-152, February 2004
Steven A. Wolfman , Tessa Lau , Pedro Domingos , Daniel S. Weld, Mixed initiative interfaces for learning tasks: SMARTedit talks back, Proceedings of the 6th international conference on Intelligent user interfaces, p.167-174, January 14-17, 2001, Santa Fe, New Mexico, United States
Gaurav Pandey , Himanshu Gupta , Pabitra Mitra, Stochastic scheduling of active support vector learning algorithms, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Qi Su , Dmitry Pavlov , Jyh-Herng Chow , Wendell C. Baker, Internet-scale collection of human-reviewed data, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Atsushi Fujii , Takenobu Tokunaga , Kentaro Inui , Hozumi Tanaka, Selective sampling for example-based word sense disambiguation, Computational Linguistics, v.24 n.4, p.573-597, December 1998
Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Leonardo Franco , Sergio A. Cannas, Generalization and Selection of Examples in Feedforward Neural Networks, Neural Computation, v.12 n.10, p.2405-2426, October 2000
Aleksander Kocz , Joshua Alspector, Asymmetric Missing-data Problems: Overcoming the Lack of Negative Data in Preference Ranking, Information Retrieval, v.5 n.1, p.5-40, January 2002
Jianqiang Shen , Thomas G. Dietterich, Active EM to reduce noise in activity recognition, Proceedings of the 12th international conference on Intelligent user interfaces, January 28-31, 2007, Honolulu, Hawaii, USA
Francois Barbanon , Daniel P. Miranker, SPHINX: Schema integration by example, Journal of Intelligent Information Systems, v.29 n.2, p.145-184, October   2007
Yevgeniy Vorobeychik , Michael P. Wellman , Satinder Singh, Learning payoff functions in infinite games, Machine Learning, v.67 n.1-2, p.145-168, May       2007
Kinh Tieu , Paul Viola, Boosting Image Retrieval, International Journal of Computer Vision, v.56 n.1-2, p.17-36, January-February 2004
Dilek Hakkani-Tr , Giuseppe Riccardi , Gokhan Tur, An active approach to spoken language processing, ACM Transactions on Speech and Language Processing (TSLP), v.3 n.3, p.1-31, October 2006
Zhi-Hua Zhou , Ming Li, Tri-Training: Exploiting Unlabeled Data Using Three Classifiers, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1529-1541, November 2005
Pabitra Mitra , B. Uma Shankar , Sankar K. Pal, Segmentation of multispectral remote sensing images using active support vector machines, Pattern Recognition Letters, v.25 n.9, p.1067-1074, 2 July 2004
Joel Ratsaby, On learning multicategory classification with sample queries, Information and Computation, v.185 n.2, p.298-327, September 15,
Yoram Baram , Ran El-Yaniv , Kobi Luz, Online Choice of Active Learning Algorithms, The Journal of Machine Learning Research, 5, p.255-291, 12/1/2004
Maria-Florina Balcan , Alina Beygelzimer , John Langford, Agnostic active learning, Proceedings of the 23rd international conference on Machine learning, p.65-72, June 25-29, 2006, Pittsburgh, Pennsylvania
Maytal Saar-Tsechansky , Foster Provost, Active Sampling for Class Probability Estimation and Ranking, Machine Learning, v.54 n.2, p.153-178, February 2004
David D. Lewis , William A. Gale, A sequential algorithm for training text classifiers, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.3-12, July 03-06, 1994, Dublin, Ireland
Huan Liu , Hiroshi Motoda , Lei Yu, A selective sampling approach to active feature selection, Artificial Intelligence, v.159 n.1-2, p.49-74, November 2004
Vijay S. Iyengar , Chidanand Apte , Tong Zhang, Active learning using adaptive resampling, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.91-98, August 20-23, 2000, Boston, Massachusetts, United States
Hema Raghavan , Omid Madani , Rosie Jones, Active Learning with Feedback on Features and Instances, The Journal of Machine Learning Research, 7, p.1655-1686, 12/1/2006
Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002
Raymond J. Mooney , Loriene Roy, Content-based book recommending using learning for text categorization, Proceedings of the fifth ACM conference on Digital libraries, p.195-204, June 02-07, 2000, San Antonio, Texas, United States
Henrik Jacobsson, The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx, Neural Computation, v.18 n.9, p.2211-2255, September 2006
Huan Liu , Hiroshi Motoda, On Issues of Instance Selection, Data Mining and Knowledge Discovery, v.6 n.2, p.115-130, April 2002
Xingquan Zhu , Xindong Wu, Cost-Constrained Data Acquisition for Intelligent Data Preparation, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1542-1556, November 2005
Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005
A. P. Engelbrecht, Sensitivity Analysis for Selective Learning by Feedforward Neural Networks, Fundamenta Informaticae, v.46 n.3, p.219-252, August 2001
Andries P. Engelbrecht, Sensitivity Analysis for Selective Learning by Feedforward Neural Networks, Fundamenta Informaticae, v.45 n.4, p.295-328, December 2001
M. Hasenjger , H. Ritter, Active learning in neural networks, New learning paradigms in soft computing, Physica-Verlag GmbH, Heidelberg, Germany, 2002
active learning;version space;neural networks;queries;generalization