Diameter-Based Active Learning
Christopher Tosh Sanjoy Dasgupta


Comb-like Turing patterns embedded in Hopf oscillations: Spatially localized states outside the 2:1 frequency locked region
    Arik Yochelis
    December 30, 2023
===========================================================================================================================



 
To date, the tightest upper and lower-bounds for the active learning of general concept classes have been in terms of a parameter of the learning problem called the splitting index. We provide, for the first time, an efficient algorithm that is able to realize this upper bound, and we empirically demonstrate its good performance.
 



§ INTRODUCTION



In many situations where a classifier is to be learned, it is easy to collect unlabeled data but costly to obtain labels. This has motivated the pool-based active learning model, in which a learner has access to a collection of unlabeled data points and is allowed to ask for individual labels in an adaptive manner. The hope is that choosing these queries intelligently will rapidly yield a low-error classifier, much more quickly than with random querying. A central focus of active learning is developing efficient querying strategies and understanding their label complexity.

Over the past decade or two, there has been substantial progress in developing such rigorously-justified active learning schemes for general concept classes. For the most part, these schemes can be described as mellow: rather than focusing upon maximally informative points, they query any point whose label cannot reasonably be inferred from the information received so far. It is of interest to develop more aggressive strategies with better label complexity.

An exception to this general trend is the aggressive strategy of <cit.>, whose label complexity is known to be optimal in its dependence on a key parameter called the splitting index. However, this strategy has been primarily of theoretical interest because it is difficult to implement algorithmically. In this paper, we introduce a variant of the methodology that yields efficient algorithms. We show that it admits roughly the same label complexity bounds as well as having promising experimental performance.

As with the original splitting index result, we operate in the realizable setting, where data can be perfectly classified by some function h^* in the hypothesis class . At any given time during the active learning process, the remaining candidates—that is, the elements of  consistent with the data so far—are called the version space. The goal of aggressive active learners is typically to pick queries that are likely to shrink this version space rapidly. But what is the right notion of size? Dasgupta <cit.> pointed out that the diameter of the version space is what matters, where the distance between two classifiers is taken to be the fraction of points on which they make different predictions. Unfortunately, the diameter is a difficult measure to work with because it cannot, in general, be decreased at a steady rate. Thus the earlier work used a procedure that has quantifiable label complexity but is not conducive to implementation.

We take a fresh perspective on this earlier result. We start by suggesting an alternative, but closely related, notion of the size of a version space: the average pairwise distance between hypotheses in the version space, with respect to some underlying probability distribution π on . This distribution π can be arbitrary—that is, there is no requirement that the target h^* is chosen from it—but should be chosen so that it is easy to sample from. When  consists of linear separators, for instance, a good choice would be a log-concave density, such as a Gaussian. 

At any given time, the next query x is chosen roughly as follows:


  * Sample a collection of classifiers h_1, h_2, …, h_m from π restricted to the current version space V. 

  * Compute the distances between them; this can be done using just the unlabeled points.

  * Any candidate query x partitions the classifiers {h_i} into two groups: those that assign it a + label (call these V_x^+) and those that assign it a - label (call these V_x^-). Estimate the average-diameter after labeling x by the sum of the distances between classifiers h_i within V_x^+, or those within V_x^-, whichever is larger.

  * Out of the pool of unlabeled data, pick the x for which this diameter-estimate is smallest.

This is repeated until the version space has small enough average diameter that a random sample from it is very likely to have error less than a user-specified threshold ϵ. We show how all these steps can be achieved efficiently, as long as there is a sampler for π.

Dasgupta <cit.> pointed out that the label complexity of active learning depends on the underlying distribution, the amount of unlabeled data (since more data means greater potential for highly-informative points), and also the target classifier h^*. That paper identifies a parameter called the splitting index ρ that captures the relevant geometry, and gives upper bounds on label complexity that are proportional to 1/ρ, as well as showing that this dependence is inevitable. For our modified notion of diameter, a different averaged splitting index is needed. However, we show that it can be bounded by the original splitting index, with an extra multiplicative factor of log (1/ϵ); thus all previously-obtained label complexity results translate immediately for our new algorithm.



§ RELATED WORK


The theory of active learning has developed along several fronts.

One of these is nonparametric active learning, where the learner starts with a pool of unlabeled points, adaptively queries a few of them, and then fills in the remaining labels. The goal is to do this with as few errors as possible. (In particular, the learner does not return a classifier from some predefined parametrized class.) One scheme begins by building a neighborhood graph on the unlabeled data, and propagating queried labels along the edges of this graph <cit.>. Another starts with a hierarchical clustering of the data and moves down the tree, sampling at random until it finds clusters that are relatively pure in their labels <cit.>. The label complexity of such methods have typically be given in terms of smoothness properties of the underlying data distribution <cit.>. 

Another line of work has focused on active learning of linear separators, by querying points close to the current guess at the decision boundary <cit.>. Such algorithms are close in spirit to those used in practice, but their analysis to date has required fairly strong assumptions to the effect that the underlying distribution on the unlabeled points is logconcave. Interestingly, regret guarantees for online algorithms of this sort can be shown under far weaker conditions <cit.>.

The third category of results, to which the present paper belongs, considers active learning strategies for general concept classes . Some of these schemes <cit.> are fairly mellow in the sense described earlier, using generalization bounds to gauge which labels can be inferred from those obtained so far. The label complexity of these methods can be bounded in terms of a quantity known as the disagreement coefficient <cit.>. In the realizable case, the canonical such algorithm is that of <cit.>, henceforth referred to as CAL. Other methods use a prior distribution π over the hypothesis class, sometimes assuming that the target classifier is a random draw from this prior. These methods typically aim to shrink the mass of the version space under π, either greedily and explicitly <cit.> or implicitly <cit.>. Perhaps the most widely-used of these methods is the latter, query-by-committee, henceforth QBC. As mentioned earlier, shrinking π-mass is not an optimal strategy if low misclassification error is the ultimate goal. In particular, what matters is not the prior mass of the remaining version space, but rather how different these candidate classifiers are from each other. This motivates using the diameter of the version space as a yardstick, which was first proposed in <cit.> and is taken up again here.



§ PRELIMINARIES


Consider a binary hypothesis class , a data space , and a distribution  over . For mathematical convenience, we will restrict ourselves to finite hypothesis classes. (We can do this without loss of generality when  has finite VC dimension, since we only use the predictions of hypotheses on a pool of unlabeled points; however, we do not spell out the details of this reduction here.) The hypothesis distance induced by  over  is the pseudometric 

    d(h, h')  :=  _x ∼(h(x) ≠ h'(x)).
 
Given a point x ∈ and a subset V ⊂, denote

    V_x^+  =  { h ∈ V   :   h(x) = 1 }

and V_x^- = V ∖ V_x^+. Given a sequence of data points x_1, …, x_n and a target hypothesis h^*, the induced version space is the set of hypotheses that are consistent with the target hypotheses on the sequence, i.e.

    { h ∈  :   h(x_i) = h^*(x_i)  for all  i=1,…, n }.




 §.§ Diameter and the Splitting Index

The diameter of a set of hypotheses V ⊂ is the maximal distance between any two hypotheses in V, i.e. 

    diam(V) := max_h, h' ∈ V d(h, h').

Without any prior information, any hypothesis in the version space could be the target. Thus the worst case error of any hypothesis in the version space is the diameter of the version space. The splitting index roughly characterizes the number of queries required for an active learning algorithm to reduce the diameter of the version space below ϵ.

While reducing the diameter of a version space V ⊂, we will sometimes identify pairs of hypotheses h,h' ∈ V that are far apart and therefore need to be separated. We will refer to {h,h'} as an edge. Given a set of edges E = {{h_1, h'_1}, … , {h_n, h'_n }}⊂ 2, we say a data point x ρ-splits E if querying x separates at least a ρ fraction of the pairs, that is, if

    max{| E_x^+|,|E_x^- |  } ≤ (1-ρ)|E|

where E_x^+ = E ∩_x^+  2 and similarly for E_x^-. 
When attempting to get accuracy ϵ > 0, we need to only eliminate edge of length greater than ϵ. Define

    E_ϵ =  {{ h, h' }∈ E   :   d(h, h') > ϵ} .

The splitting index of a set V ⊂ is a tuple (ρ, ϵ, τ) such that for all finite edge-sets E ⊂V  2,

    _x ∼(x  ρ-splits  E_ϵ)  ≥ τ.

The following theorem, due to Dasgupta <cit.>, bounds the sample complexity of active learning in terms of the splitting index. The Õ notation hides polylogarithmic factors in d, ρ, τ, log 1/ϵ, and the failure probability δ.

Suppose  is a hypothesis class with splitting index (ρ, ϵ, τ). Then to learn a hypothesis with error ϵ,

	
  (a) any active learning algorithm with ≤ 1/τ unlabeled samples must request at least 1/ρ labels, and 
	
  (b) if  has VC-dimension d, there is an active learning algorithm that draws Õ(d/(ρτ) log^2 (1/ϵ)) unlabeled data points and requests Õ((d/ρ) log^2 (1/ϵ)) labels.



Unfortunately, the only known algorithm satisfying (b) above is intractable for all but the simplest hypothesis classes: it constructs an ϵ-covering of the hypothesis space and queries points which whittle away at the diameter of this covering. To overcome this intractability, we consider a slightly more benign setting in which we have a samplable prior distribution π over our hypothesis space .



 §.§ An Average Notion of Diameter

With a prior distribution, it makes sense to shift away from the worst-case to the average-case. We define the average diameter of a subset V ⊂ as the expected distance between two hypotheses in V randomly drawn from π, i.e. 

    Φ(V) := _h, h' ∼π|_V[d(h, h')]

where π|_V is the conditional distribution induced by restricting π to V, that is, π|_V(h) = π(h)/π(V) for h ∈ V. 

Intuitively, a version space with very small average diameter ought to put high weight on hypotheses that are close to the true hypothesis. Indeed, given a version space V with h^* ∈ V, the following lemma shows that if Φ(V) is small enough, then a low error hypothesis can be found by two popular heuristics: random sampling and MAP estimation. 
lemmaSmallAverageDiameterImpliesGoodEstimateLemma

Suppose V ⊂ contains h^*. Pick ϵ > 0.


  (a) (Random sampling) If Φ(V) ≤ϵ π|_V(h^*) then _h ∼π|_V [d(h^*,h)] ≤ϵ.

  (b) (MAP estimation) Write p_map = max_h ∈ Vπ|_V(h). Pick 0 < α < p_map. If 

    Φ(V)  ≤ 2 ϵ( min{π|_V(h^*), p_map-α})^2,

 then d(h^*,h) ≤ϵ for any h with π|_V(h) ≥ p_map - α.



Part (a) follows from

    Φ(V)  =  _h,h' ∼π|_V[d(h,h')]  ≥ π|_V(h^*) _h ∼π|_V[d(h^*,h)] .

For (b), take δ =  min(π|_V(h^*), p_map - α) and define V_π, δ = { h ∈ V   :  π|_V(h) ≥δ}. Note that V_π,δ contains h^* as well as any h ∈ V with π|_V(h) ≥ p_map - α.

We claim diam(V_π, δ) is at most ϵ. Suppose not. Then there exist h_1, h_2 ∈ V_π, δ satisfying d(h_1, h_2) > ϵ, implying

    Φ(V)    = _h,h' ∼π|_V[d(h,h')] 
       ≥ 2 ·π|_V(h_1) ·π|_V(h_2) · d(h_1, h_2)  >  2 δ^2 ϵ.
 
But this contradicts our assumption on Φ(V). Since both h, h^* ∈ V_π, δ, we have (b).




 §.§ An Average Notion of Splitting

We now turn to defining an average notion of splitting. A data point x ρ-average splits V if

    max{π(V_x^+)^2/π(V)^2Φ(V_x^+),  π(V_x^-)^2/π(V)^2Φ(V_x^-) } ≤ (1-ρ) Φ(V).

And we say a set S ⊂ has average splitting index (ρ, ϵ, τ) if for any subset V ⊂ S such that Φ(V) > ϵ, 

    _x ∼( x  ρ-average splits  V )  ≥ τ.

Intuitively, average splitting refers to the ability to significantly decrease the potential function 

    π(V)^2 Φ(V)  =  _h,h' ∼π[(h,h' ∈ V)   d(h,h')]

with a single query.

While this potential function may seem strange at first glance, it is closely related to the original splitting index. The following lemma, whose proof is deferred to Section <ref>, shows the splitting index bounds the average splitting index for any hypothesis class.

lemmaSplittingImpliesAverageSplittingLemma

Let π be a probability measure over a hypothesis class . If  has splitting index (ρ, ϵ, τ), then it has average splitting index (ρ/4 ⌈log(1/ϵ) ⌉, 2ϵ, τ).


Dasgupta <cit.> derived the splitting indices for several hypothesis classes, including intervals and homogeneous linear separators. Lemma <ref> implies average splitting indices within a log(1/ϵ) factor in these settings.


Moreover, given access to samples from π|_V, we can easily estimate the quantities appearing in the definition of average splitting. For an edge sequence E = ({h_1, h'_1}, … , {h_n, h'_n }), define 

    ψ(E) := ∑_i=1^n d(h_i, h'_i).

When h_i, h'_i are i.i.d. draws from π|_V for all i=1, …, n, which we denote E ∼ (π|_V)^2 × n, the random variables ψ(E), ψ(E_x^-), and ψ(E_x^+) are unbiased estimators of the quantities appearing in the definition of average splitting.  


Given E ∼ (π|_V)^2 × n, we have

	
  * [1/nψ(E) ] = Φ(V) and
	
  * [ 1/nψ(E_x^+) ] = π(V_x^+)^2/π(V)^2Φ(V_x^+) for any x ∈. Similarly for E_x^- and V_x^-.




From definitions and linearity of expectations, it is easy to observe [ψ(E)] = n  Φ(V). By the independence of h_i, h'_i, we additionally have

    [ 1/nψ(E_x^+) ]    = 1/n[ ∑_{ h_i, h_i' }∈ E_x^+ d(h_i, h'_i) ] 
    [3]
       = 1/n[ ∑_{ h_i, h_i' }∈ E[h_i ∈ V_x^+]  [h'_i ∈ V_x^+]   d(h_i, h'_i) ] 
    [3]
       = 1/n∑_{ h_i, h_i' }∈ E(  π(V_x^+)/π(V))^2 [ d(h_i, h'_i)   |   h_i, h'_i ∈ V_x^+] 
    [3]
       = (  π(V_x^+)/π(V))^2 Φ(V_x^+).




  
Remark: It is tempting to define average splitting in terms of the average diameter as 
    max{Φ(V_x^+), Φ(V_x^-) } ≤ (1- ρ) Φ(V).
 However, this definition does not satisfy a nice relationship with the splitting index. Indeed, there exist hypothesis classes V for which there are many points which 1/4-split E for any E ⊂V  2 but for which every x ∈ satisfies 

    max{Φ(V_x^+), Φ(V_x^-) } ≈ Φ(V).
 
This observation is formally proven in the appendix.



§ AN AVERAGE SPLITTING INDEX ALGORITHM


Suppose we are given a version space V with average splitting index (ρ, ϵ, τ). If we draw Õ(1/τ) points from the data distribution then, with high probability, one of these will ρ-average split V. Querying that point will result in a version space V' with significantly smaller potential π(V')^2 Φ(V').  


If we knew the value ρ a priori, then Lemma <ref> combined with standard concentration bounds <cit.> would give us a relatively straightforward procedure to find a good query point: 

	
  * Draw E' ∼ (π|_V)^2× M and compute the empirical estimate Φ(V) = 1/Mψ(E').
	
  * Draw E ∼ (π|_V)^2× N for N depending on ρ and Φ.
    
  * For suitable M and N, it will be the case that with high probability, for some x, 

    1/Nmax{ψ(E_x^+), ψ(E_x^-)  } ≈ (1-ρ)Φ.

Querying that point will decrease the potential.  


However, we typically would not know the average splitting index ahead of time. Moreover, it is possible that the average splitting index may change from one version space to the next. In the next section, we describe a query selection procedure that adapts to the splittability of the current version space.



 §.§ Finding a Good Query Point

Algorithm <ref>, which we term select, is our query selection procedure. It takes as input a sequence of data points x_1, …, x_m, at least one of which ρ-average splits the current version space, and with high probability finds a data point that ρ/8-average splits the version space. 


select proceeds by positing an optimistic estimate of ρ, which we denote ρ_t, and successively halving it until we are confident that we have found a point that ρ_t-average splits the version space. In order for this algorithm to succeed, we need to choose n_t and m_t such that with high probability (1) Φ_t is an accurate estimate of Φ(V) and (2) our halting condition will be true if ρ_t is within a constant factor of ρ and false otherwise. The following lemma, whose proof is in the appendix, provides such choices for n_t and m_t.

lemmaSelectionProcedureLemma

Let ρ, ϵ, δ_0 >0 be given. Suppose that version space V satisfies Φ(V) > ϵ. In select, fix a round t and data point x ∈ that exactly ρ-average splits V (that is, max{π|_V(V_x^+)^2 Φ(V_x^+),  π|_V(V_x^-)^2 Φ(V_x^-) } = (1-ρ)Φ(V)). If m_t ≥48/ρ_t^2 ϵlog4/δ_0 and n_t ≥max{32/ρ_t^2 Φ_t, 40/Φ_t^2}log4/δ_0 then with probability 1-δ_0, 

	
  (a) Φ_t ≥ (1-ρ_t/4)Φ(V);
	
  (b) if ρ≤ρ_t/2, then 1/n_tmax{ψ(E_x^+), ψ(E_x^-)} > (1- ρ_t) Φ_t; and
	
  (c) if ρ≥ 2ρ_t, then 1/n_tmax{ψ(E_x^+), ψ(E_x^-)}≤ (1- ρ_t) Φ_t .



Given the above lemma, we can establish a bound on the number of rounds and the total number of hypotheses select needs to find a data point that ρ/8-average splits the version space.



Suppose that select is called with a version space V with Φ(V) ≥ϵ and a collection of points x_1, …, x_m such that at least one of x_i ρ-average splits V. If δ_0 ≤δ/(2m (2 + log(1/ρ))), then with probability at least 1- δ, select returns a point x_i that (ρ/8)-average splits V, finishing in less than ⌈log(1/ρ) ⌉ + 1 rounds and sampling O( ( 1/ϵρ^2 + log(1/ρ)/Φ(V)^2) log1/δ_0) hypotheses in total.
 







  
Remark 1: It is possible to modify select to find a point x_i that (c ρ)-average splits V for any constant c < 1 while only having to draw O(1) more hypotheses in total. First note that by halving ρ_t at each step, we immediately give up a factor of two in our approximation. This can be made smaller by taking narrower steps. Additionally, with a constant factor increase in m_t and n_t, the approximation ratios in Lemma <ref> can be set to any constant.



  
Remark 2: At first glance, it appears that select requires us to know ρ in order to calculate δ_0. However, a crude lower bound on ρ suffices. Such a bound can always be found in terms of ϵ. This is because any version space is (ϵ/2, ϵ, ϵ/2)-splittable <cit.>. By Lemma <ref>, so long as τ is less than ϵ/4, we can substitute ϵ/8⌈log(2/ϵ)⌉ for ρ in when we compute δ_0.




Let T := ⌈log(1/ρ) ⌉ + 1. By Lemma <ref>, we know that for rounds t=1,…, T, we don't return any point which does worse than ρ_t/2-average splits V with probability 1-δ/2. Moreover, in the T-th round, it will be the case that ρ/4 ≤ρ_T ≤ρ/2, and therefore, with probability 1-δ/2, we will select a point which does no worse than ρ_T/2-average split V, which in turn does no worse than ρ/8-average split V.

Note that we draw m_t + n_t hypotheses at each round. By Lemma <ref>, for each round Φ_t ≥ 3Φ(V)/4 ≥ 3ϵ/4. Thus

    # of hypotheses drawn  =  ∑_t=1^T (48/ρ_t^2 ϵ + 32/ρ_t^2 Φ_t + 40/Φ_t^2) log4/δ_0 ≤ ∑_t=1^T (96/ϵρ_t^2 + 72/Φ(V)^2) log4/δ_0

Given ρ_t = 1/2^t and T ≤ 2 + log 1/ρ, we have

    ∑_t=1^T 1/ρ_t^2 =  ∑_t=1^T 2^2t ≤ (∑_t=1^T 2^t)^2  ≤ (2^2 + log 1/ρ)^2  =  16/ρ^2.

Plugging in  δ_0 ≤δ/2m (2 + log(1/ρ)), we recover the theorem statement.




 §.§ Active Learning Strategy



Using the select procedure as a subroutine, Algorithm <ref>, henceforth DBAL for Diameter-based Active Learning, is our active learning strategy. Given a hypothesis class with average splitting index (ρ, ϵ/2, τ), DBAL queries data points provided by select until it is confident Φ(V) < ϵ. 

Denote by V_t the version space in the t-th round of DBAL. The following lemma, which is proven in the appendix, demonstrates that the halting condition (that is, ψ(E) < 3ϵ n/4, where E consists of n pairs sampled from (π|_V)^2) guarantees that with high probability DBAL stops when Φ(V_t) is small.

lemmaCorrectTerminationLemma

The following holds for DBAL:

	
  (a) Suppose that for all t = 1, 2, …, K that Φ(V_t) > ϵ. Then the probability that the termination
		condition is ever true for any of those rounds is bounded above by K exp( - ϵ n /32).
	
  (b) Suppose that for some t = 1, 2, …, K that Φ(V_t) ≤ϵ/2. Then the probability that the termination
		condition is not true in that round is bounded above by K exp( - ϵ n /48).



Given the guarantees on the select procedure in Theorem <ref> and on the termination condition provided by Lemma <ref>, we get the following theorem.



Suppose that  has average splitting index (ρ, ϵ/2, τ). Then DBAL returns a version space V satisfying Φ(V) ≤ϵ with probability at least 1 - δ while using the following resources:

	
  (a) K ≤8/ρ( log2/ϵ + 2 log1/π(h^*)) rounds, with one label per round,
	
  (b) m ≤1/τlog2K/δ unlabeled data points sampled per round, and
	
  (c) n ≤ O ( ( 1/ϵρ^2 + log(1/ρ)/ϵ^2) ( logmK/δ + loglog1/ϵ)) hypotheses sampled per round.



From definition of the average splitting index, if we draw m = 1/τlog2K/δ unlabeled points per round, then with probability 1-δ/2, each of the first K rounds will have at least one data point that ρ-average splits the current version space. In each such round, if the version space has average diameter at least ϵ/2, then with probability 1-δ/4 select will return a data point that ρ/8-average splits the current version space while sampling no more than n = O( (1/ϵρ^2 + 1/ϵ^2log1/ρ) logmK log1/ϵ/δ) hypotheses per round by Theorem <ref>.


By Lemma <ref>, if the termination check uses n'= O( 1/ϵlog1/δ) hypotheses per round, then with probability 1-δ/4 in the first K rounds the termination condition will never be true when the current version space has average diameter greater than ϵ and will certainly be true if the current version space has diameter less than ϵ/2.

Thus it suffices to bound the number of rounds in which we can ρ/8-average split the version space before encountering a version space with ϵ/2. 

Since the version space is always consistent with the true hypothesis h^*, we will always have π(V_t) ≥π(h^*). After K = 8/ρ( log2/ϵ + 2 log1/π(h^*)) rounds of ρ/8-average splitting, we have

    π(h^*)^2 Φ(V_K)  ≤ π(V_K)^2Φ(V_K)   ≤ (1- ρ/8)^K π(V_0)^2 Φ(V_0)  ≤ π(h^*)^2ϵ/2

Where we have used the fact that π(V)^2 Φ(V) ≤ 1 for any set V ⊂. Thus in the first K rounds, we must terminate with a version space with average diameter less than ϵ.




§ PROOF OF LEMMA <REF>


In this section, we give the proof of the following relationship between the original splitting index and our average splitting index.
*
The first step in proving Lemma <ref> is to relate the splitting index to our estimator ψ(·). Intuitively, splittability says that for any set of large edges there are many data points which remove a significant fraction of them. One may suspect this should imply that if a set of edges is large on average, then there should be many data points which remove a significant fraction of their weight. The following lemma confirms this suspicion.



Suppose that V ⊂ has splitting index (ρ, ϵ, τ), and say E = ({h_1, h_1' }, …, { h_n, h_n' }) is a sequence of hypothesis pairs from V satisfying 1/nψ(E) > 2 ϵ. Then if x ∼, we have with probability at least τ, 

    max{ψ(E_x^+), ψ(E_x^-) }≤(1 - ρ/4 ⌈log(1/ϵ) ⌉)ψ(E) .



Consider partitioning E as

    E_0    = {{ h, h' }∈ E   :   d(h,h') < ϵ} and 
    
    E_k    = {{ h, h' }∈ E   :   d(h,h') ∈ [2^k-1ϵ, 2^k ϵ)

for k=1,…, K with K =  ⌈log1/ϵ⌉. Then E_0, …, E_K are all disjoint and their union is E. Define E_1:K = ∪_k=1^K E_k. 

We first claim that ψ(E_1:K) > ψ(E_0). This follows from the observation that because ψ(E) ≥ 2 n  ϵ and each edge in E_0 has length less than ϵ, we must have

    ψ(E_1:K)  =  ψ(E) - ψ(E_0)  >  2 n ϵ - n ϵ >  ψ(E_0).

Next, observe that because each edge { h, h' }∈ E_k with k ≥ 1 satisfies d(h,h') ∈ [2^k-1ϵ, 2^k ϵ), we have

    ψ(E_1:K)   =  ∑_k=1^K ∑_{ h , h' }∈ E_k  d(h,h')  ≤ ∑_k=1^K  2^kϵ |E_k|.

Since there are only K summands on the right, at least one of these must be larger than ψ(E_1:K)/K. Let k denote that index and let x be a point which ρ-splits E_k. Then we have

    ψ((E_1:K)^+_x)     ≤ ψ(E_1:K) - ψ(E_k ∖ (E_k)_x^+) 
       ≤ ψ(E_1:K) - ρ 2^k-1ϵ |E_k| 
       ≤ ( 1 - ρ/2K) ψ(E_1:K).

Since ψ(E_1:K) ≥ψ(E_0), we have

    ψ(E^+_x)  ≤ ψ(E_0) + ( 1 - ρ/2K) ψ(E_1:K)  ≤ ( 1 - ρ/4K) ψ(E).

Symmetric arguments show the same holds for E^-_x. 

Finally, by the definition of splitting, the probability of drawing a point x which ρ-splits E_k is at least τ, giving us the lemma.


With Lemma <ref> in hand, we are now ready to prove Lemma <ref>.


Let V ⊂ such that Φ(V) > 2ϵ. Suppose that we draw n edges E i.i.d. from π|_V and draw a data point x ∼. Then Hoeffding's inequality <cit.>, combined with Lemma <ref>, tells us that there exist sequences ϵ_n, δ_n ↘ 0 such that with probability at least 1-3δ_n, the following hold simultaneously:

	
  * Φ(V) - ϵ_n  ≤ 1/nψ(E)  ≤ Φ(V) + ϵ_n,
	
  * 1/nψ(E_x^+)  ≥ π(V_x^+)^2/π(V)^2Φ(V_x^+) - ϵ_n, and
	
  * 1/nψ(E_x^-)  ≥ π(V_x^-)^2/π(V)^2Φ(V_x^-) - ϵ_n.

For ϵ_n small enough, we have that Φ(V) - ϵ_n > 2ϵ. Combining the above with Lemma <ref>, we have with probability at least τ - 3δ_n,

    max{π(V_x^+)^2/π(V)^2Φ(V_x^+), π(V_x^-)^2/π(V)^2Φ(V_x^-)  } - ϵ_n     ≤ 1/nmax{ψ(E_x^+), ψ(E_x^-)  }
       ≤ (1 - ρ/4 ⌈log(1/ϵ) ⌉) ψ(E)/n
       ≤ (1 - ρ/4 ⌈log(1/ϵ) ⌉)(Φ(V) + ϵ_n).

By taking n →∞, we have ϵ_n, δ_n ↘ 0, giving us the lemma.



§ SIMULATIONS
 

We compared DBAL against the baseline passive learner as well as two other generic active learning strategies: CAL and QBC. CAL proceeds by randomly sampling a data point and querying it if its label cannot be inferred from previously queried data points. QBC uses a prior distribution π and maintains a version space V. Given a randomly sampled data point x, QBC samples two hypotheses h, h' ∼π|_V and queries x if h(x) ≠ h'(x).


We tested on two hypothesis classes: homogeneous, or through-the-origin, linear separators and k-sparse monotone disjunctions. In each of our simulations, we drew our target h^* from the prior distribution. After each query, we estimated the average diameter of the version space. We repeated each simulation several times and plotted the average performance of each algorithm.



  
Homogeneous linear separators The class of d-dimensional homogeneous linear separators can be identified with elements of the d-dimensional unit sphere. That is, a hypothesis h ∈𝒮^d-1 acts on a data point x ∈^d via the sign of their inner product:

    h(x)  :=  sign(⟨ h, x ⟩).

In our simulations, both the prior distribution and the data distribution are uniform over the unit sphere. Although there is no known method to exactly sample uniformly from the version space, Gilad-Bachrach et al. <cit.> demonstrated that using samples generated by the hit-and-run Markov chain works well in practice. We adopted this approach for our sampling tasks.

Figure <ref> shows the results of our simulations on homogeneous linear separators. 





  
Sparse monotone disjunctions A k-sparse monotone disjunction is a disjunction of k positive literals. Given a Boolean vector x ∈{0, 1}^n, a monotone disjunction h classifies x as positive if and only if x_i = 1 for some positive literal i in h.


In our simulations, each data point is a vector whose coordinates are i.i.d. Bernoulli random variables with parameter p. The prior distribution is uniform over all k-sparse monotone disjunctions. When k is constant, it is possible to sample from the prior restricted to the version space in expected polynomial time using rejection sampling.


The results of our simulations on k-sparse monotone disjunctions are in Figure <ref>. 



§ ACKNOWLEDGMENTS
 

The authors are grateful to the NSF for support under grants IIS-1162581 and DGE-1144086. Part of this work was done at the Simons Institute for Theoretical Computer Science, Berkeley, as part of a program on the foundations of machine learning. CT additionally thanks Daniel Hsu and Stefanos Poulis for helpful discussions.


plain





§ APPENDIX: PROOF DETAILS




 §.§ Remark from Section <ref>


In Section <ref>, the remark after the definition of average splitting stated that there exist hypothesis classes V for which there are many points which 1/4-split E for any E ⊂V  2 but for which any x ∈ satisfies 

    max{Φ(V_x^+), Φ(V_x^-) }≈Φ(V).

Here we formally prove this statement.


Consider the hypothesis class of homogeneous linear separators and let V = {e_1, …, e_n}⊂ where e_k is the k-th unit coordinate vector. Let the data distribution be uniform over the n-sphere and the prior distribution π be uniform over V. As a subset of the homogeneous linear separators, V has splitting index (1/4, ϵ, Θ(ϵ)) <cit.>. 


On the other hand, for any i ≠ j, d(h_i, h_j) = 1/2. This implies that 

    Φ(V)  =  (h ≠ h') _h,h'[d(h,h')   |   h≠ h']  =  n-1/2n.

Moreover, any query x ∈ eliminates at most half the hypotheses in V in the worst case. Therefore, for all x ∈,

    max{Φ(V_x^+), Φ(V_x^-) } ≥ (n/2 - 1)/2 (n/2) =  (n-2/n-1) Φ(V).




 §.§ Proofs of Lemma <ref> and Lemma <ref>


The proofs in this section rely crucially on two concentration inequalities. The first is due to Hoeffding <cit.>.



Let X_1, …, X_n be i.i.d. random variables taking values in [0,1] and let X = ∑ X_i and μ = [X]. Then for t > 0,

    (X - μ≥ t) ≤exp( -2t^2/n)


Our other tool will be the following multiplicative Chernoff-Hoeffding bound due to Angluin and Valiant <cit.>.


Let X_1, …, X_n be i.i.d. random variables taking values in [0,1] and let X = ∑ X_i and μ = [X]. Then for 0 < β < 1,

	
  (i) (X ≤ (1 - β)μ) ≤exp(	- β^2 μ/2) and
	
  (ii) (X ≥ (1 + β)μ) ≤exp(	- β^2 μ/3).


We now turn to the proof of Lemma <ref>.
*

In round t, let ρ := ρ_t, Φ := Φ_t, m := m_t, and n := n_t. 



For (a), recall Φ = 1/mψ(E') for E' ∼ (π|_V)^2 × m. By Lemma <ref>, we have for β_0 >0 

    ((1-β_0)Φ(V) ≤Φ≤ (1+β_0)Φ(V) ) ≥ 1- 2exp( - m β_0^2 ϵ/3).

Taking m ≥3/β_0^2 ϵlog( 4/δ_0), we have the above probability is at least 1 - δ_0/2. Let us condition on this event occurring.


To see (b), say w.l.o.g. ( π(V_x^+)/π(V))^2 Φ(V_x^+) = (1-ρ)Φ(V). Then, we have

    (1/nψ(E_x^+) ≤ (1-ρ) Φ)    ≤(1/nψ(E_x^+) ≤ (1-ρ) (1+ β_0) Φ(V) ).

Taking β such that (1-β)(1-ρ) = (1-ρ)(1+β_0), we have by Lemma <ref> (i),

    (1/nψ(E_x^+) ≤ (1-ρ) Φ)    ≤(1/nψ(E_x^+) ≤ (1-β) (1-ρ) Φ(V) ) 
       ≤exp( - n β^2(1-ρ) Φ(V)/2)
       ≤exp( - n (1-ρ) Φ/2(1+β_0)·[ 1 - (1 - ρ)(1+ β_0)/1-ρ]^2  ) 
       ≤exp( - n (1-ρ/2) Φ/2(1+β_0)·[ 1 - (1 - ρ)(1+ β_0)/1-ρ/2]^2  ).

Taking β_0 ≤ρ/4, the above is less than exp( - n Φρ^2/32). With n as in the lemma statement and combined with our results on the concentration of Φ, we have that with probability 1-δ_0 
    1/nmax{ψ(E_x^+), ψ(E_x^-)} > (1-ρ) Φ.


To see (c),  suppose now that w.l.o.g. ( π(V_x^-)/π(V))^2 Φ(V_x^-)  ≤( π(V_x^+)/π(V))^2 Φ(V_x^+) = (1-ρ)Φ(V). We need to consider two cases.




  
Case 1: ρ≤ 1/2. 
Taking β such that (1+β)(1-ρ) = (1-ρ)(1 - β_0), we have by Lemma <ref> (ii),

    (1/nψ(E_x^+) > (1-ρ) Φ)    ≤(1/nψ(E_x^+) > (1-ρ) (1-β_0) Φ(V) ) 
       = (1/nψ(E_x^+) > (1+β) (1-ρ) Φ(V) ) 
       ≤exp( - n β^2 (1- ρ)Φ(V)/3) 
       ≤exp( - n (1- ρ)Φ/3(1+β_0)·[(1-ρ)(1-β_0)/1-ρ -1]^2 ) 
       ≤exp( - n Φ/6(1+β_0)·[(1-ρ)(1-β_0)/1- 2 ρ -1 ]^2 ).


Taking β_0 ≤ρ/4, the above is less than exp( - n Φρ^2/12). Because ( π(V_x^-)/π(V))^2 Φ(V_x^-)  ≤( π(V_x^+)/π(V))^2 Φ(V_x^+), we also can say 

    (1/nψ(E_x^-) > (1-ρ) Φ) ≤exp( - n Φρ^2/12).




  
Case 2:  ρ > 1/2. Taking β_0 ≤ 1/16, we have 

    (1/nψ(E_x^+) > (1- ρ)Φ) 
       ≤(1/nψ(E_x^+) > (1- ρ)(1-β_0)Φ(V) ) 
       = (1/nψ(E_x^+) > (1-ρ)Φ(V) +  ((1- ρ)(1-β_0) - (1-ρ)) Φ(V) ) 
       ≤(1/nψ(E_x^+) > (1-ρ)Φ(V) +  (ρ - ρ - β_0 ) Φ(V) ) 
       ≤(1/nψ(E_x^+) > (1-ρ)Φ(V) +  (ρ/2 - β_0 ) Φ(V) ) 
       ≤(1/nψ(E_x^+) > (1-ρ)Φ(V) +  ( 1/4 - β_0 ) Φ(V) ) 
       ≤(1/nψ(E_x^+) > (1-ρ)Φ(V) +  1/4 - β_0/1 + β_0Φ) 
       ≤(1/nψ(E_x^+) > (1-ρ)Φ(V) +  3/17Φ)

By Lemma <ref>, the above is less than exp(- n Φ^2/40). Because ( π(V_x^-)/π(V))^2 Φ(V_x^-)  ≤( π(V_x^+)/π(V))^2 Φ(V_x^+), we also can say 

    (1/nψ(E_x^-) > (1-ρ) Φ) ≤exp(- n Φ^2/40).


Regardless of which case we are in, we have for n as in the lemma statement, with probability 1- δ_0, 
    1/nmax{ψ(E_x^+), ψ(E_x^-)}≤ (1- ρ) Φ.



We next provide the proof of Lemma <ref>.
*

Recall that the termination condition from DBAL is 1/nψ(E) < 3ϵ/4 for E ∼ (π|_V)^2× n. 


Part (a) follows from plugging in β = 1/4 into Lemma <ref> (i) and taking a union bound over rounds 1, …, K.


Similarly, part (b) follows from plugging in β = 1/4 into Lemma <ref> (ii) and taking a union bound over rounds 1, …, K.


