The perceptron invented by Frank Rosenblatt in 1957 is probably the simplest artificial neural network.^[1] It has N inputs and one output, with each input neuron i affecting the output neuron through a synapse of weight T_i.^[2–3] Given an N-dimensional input vector ξ ≡ (ξ₁, ξ₂,…, ξ_N), the binary output state σ is determined according to a (highly nonlinear) sign function
where T ≡ (T₁, T₂,…,T_N) denotes the synaptic weight vector. The output σ = 1 if the overlap between ξ and T, defined as ∑_i T_is_i, is positive and σ = −1 if this overlap is negative. We consider the binary (or Ising) perceptron problem, so all the synaptic weights and neural states are restricted to be Ising-valued (i.e., T_i, ξ_i ∈ ±1 for every input neuron i of the system). These constraints make the binary perceptron much more challenging to study than the continuous counterpart.^[2–3]

The perceptron can serve as a linear classifier. In this scenario, given P patterns with indices μ = 1, 2,…,P and their binary labels σ^μ, the task is to find a vector T such that these P patterns are correctly classified, that is, σ^μ = sign(ξ^μ; T) holds for each and every one of these P patterns.^[2–3] The whole set of all such compatible weight vectors form the version space (or solution space) of the perceptron. If the input binary patterns ξ^μ are random and independent, it was predicted using the replica method of statistical physics that there exist binary solutions T to this classification problem as long as P < 0.83N.^[4] Several message-passing algorithms^[5–6] inspired by the cavity method of statistical physics have been implemented to solve single instances of the perceptral classification problem. More recently it was revealed that, as the density α ≡ P/N of random input binary patterns increases, the typical (equilibrium) solutions of this classification problem become widely separated from each other and are extremely hard to reach,^[7–8] while there are also sub-dominant dense regions in the version space, which could be reached through entropy-weighted sampling strategies.^[9–10]

The perceptron can also be studied from the teacher–student perspective, with T understood as the teacher’s weight vector which is hidden to the student. For each query ξ to the teacher, the correct label σ(ξ) as computed through Eq. (1) is revealed to the student, and the task for the student is to infer the hidden vector T by learning from the (ξ, σ) associations.^[2–3] This inference task may be carried out in an offline manner, meaning that the training samples are repeatedly examined by the student during the learning process. It may also be carried out in an online manner, meaning that each training sample is used only once by the student to update his/her belief on T. We study online learning in the present work.

The learning performance of the teacher–student perceptron system has been investigated by many authors. In the passive learning mode for which the training patterns are independent and random, it was predicted that perfect (error-free) inference of a binary vector T is theoretically possible with P ≈ 1.25N binary samples.^[11–12] But this theoretical limit has never been achieved by actual heuristic algorithms. Theoretical and numerical studies on various algorithms have found that the generalization error ε of the passive learning process decreases with the pattern density α algebraically, e.g., ε ∝ α⁻¹. This means that in the thermodynamic limit of N → ∞, perfect inference is unlikely to achieve at any finite value of pattern density α.^[13–19]

In this work we address the issue of active learning, which aims at accelerating online inference by carefully designing the training patterns. After the student has encountered P samples and has already gained some knowledge about the truth vector T, how should she/he design the (P + 1)-th query so that the answer from this new query will be most informative for inference? This interesting question was explored by many authors in the early 1990s (see, e.g., Refs. [20–27]), but the focus was on minimization of the generalization error rather than on error-free inference. In Sec. 2 of the present paper we prove that error-free learning of T can be achieved using at most N +log₂N designed training patterns through deductive reasoning, which is only slightly beyond the theoretical lower bound, N. If the optimal Bayesian inference strategy is used instead of deductive logic, we find that error-free inference using exactly N designed samples is indeed possible, but it is computationally feasible only for small systems (Sec. 3). We then implement two heuristic designing algorithms in Secs. 4 and 5 for large systems based on this optimal Bayesian principle. Our simulation results demonstrate that these two heuristic algorithms need 2.3N and 1.9N training samples, respectively, to achieve error-free inference.

Although the deductive-logic algorithm certainly outperforms the data-driven Bayesian algorithms, the observation that the Bayesian statistical approach achieves perfect inference of N bits with less than 2N one-bit measurements is still quite encouraging. We expect that the performance of the Bayesian active inference algorithms will be further improved after taking into account the possibility of ergodicity breaking in the version space of the perceptron. If the version space divides into a large number of well-separated clusters, the assumption of Gaussian distribution of the mean field theory will no longer be valid (Sec. 6), and more advanced mean field theories such as the fist-step replica-symmetry-breaking cavity method will be needed to better describe the complicated statistical correlations of the version space.

The concept of active (or adaptive) learning has been widely discussed in the fields of education science^[28] and optimal experimental design.^[29–30] Science itself may also be considered as an active learning process,^[29] for which data-inspired intuitive insights, controlled experiments, and deductive reasoning are all indispensable. Artificial deep neural networks are becoming powerful tools for extracting the most important features from huge amount of data,^[31–32] facilitating hypothesis formation and experimental design. Recently there has been great enthusiasm in this direction, and efficient active learning algorithms for deep neural networks are start to be explored.^[33–36] A lot of work remains to be done on this important issue. From the theoretical side, the binary perceptron may serve as a simple model system to push for the limit of active Bayesian learning. Another basic inference problem which is closely related to the perceptron model is the so-called one-bit compressed sensing problem.^[37–38] At the moment only the passive mode of one-bit compressed sensing has been considered in the literature. Beyond the single-layered perceptron and one-bit compressed sensing, the next and more challenging model is the multi-layered binary perceptron system.

We first show that if the student employs deductive reasoning, online perceptral learning can be made very efficient. At the start of the learning process, the student can simply choose an arbitrary pattern ξ = (ξ₁,ξ₂,…,ξ_N) ∈ {−1, +1}^N as the query. For convenience of discussion, let us define a particular overlap function q(n) on the integer domain n ∈ {0, 1,…,N} as
This function is simply the overlap (or the scalar product) of the teacher’s weight vector T and the modified pattern ξ(n) ≡ (−ξ₁,… −ξ_n, ξ_n+1, …,ξ_N) after flipping the first n entries of ξ. An example of function q(n) is illustrated in Fig. 1. Because N is odd, q(n) takes only odd values. And because q(N) = −q(0) and |q(n) − q(n + 1)| = 2 for any n < N (quasi-continuity), there must exist at least one n* ∈ {0, 1,…,N − 1} for which |q(n*)| = |q(n* + 1)| = 1 and q(n* + 1) = −q(n*).

Fig. 1

	Figure Option ViewDownloadNew Window
	Fig. 1 An example of the overlap function q(n) for a small perceptron of size N = 33. The random initial binary pattern ξ happens to have overlap q(0) = 7 with the teacher’s binary weight vector T, and q(n) is the new overlap with T after the first n entries of ξ are all flipped. In this example q(n) changes sign seven times.

The value of such an integer n* can be determined through at most log₂N queries. Starting from n_l = 0 and n_r = N, the query sequence goes as follows: (i) feed pattern ξ(n_l) to the perceptron to get the sign of q(n_l); (ii) set n_m ≡ ⌈(n_l+n_r)/2⌉ and feed pattern ξ(n_m) to the perceptron to get the sign of q(n_m); (iii) if q(n_m) and q(n_l) have the same sign, set n_l = n_m, otherwise set n_r = n_m; (iv) if n_r = n_l +1, set n* = n_l and quit, otherwise repeat steps (ii)–(iv).

The value of q(n*), i.e. the overlap between ξ(n*) and T, must be +1 or −1. Because of this fact, if one flips the i-th entry of ξ(n*) and feeds the resulting slightly modified pattern to the perceptron, the value of T_i can be deduced from the output. That is, if the output is the same as the sign of q(n*), then T_i must be equal to , otherwise T_i must be equal to .

By the above-mentioned deductive reasoning method, the binary weight vector T can be exactly determined after at most N + log₂N queries. But it is clear from the above discussions that the success of this logical approach requires a deep understanding of the perceptron system. We continue to explore other active learning strategies in the next three sections.

After P training samples ξ^μ, σ^μ) have been experienced, for a weight vector J = (J₁, J₂, …,J_N) ∈ {−1, +1}^N to be compatible with all these P samples, it must satisfy
for every one of these samples. We denote by Σ_P the set of all the Ising weight vectors J satisfying these P constraints, and refer to this set as the version space at stage P. Notice the teacher’s vector T is always a member of Σ_P, so the volume |Σ_P| of the version space must be positive-definite. To accelerate online learning, a simple idea would be to reduce the volume of the version space as much as possible with each new training pattern. When finally the version space shrinks to a single point, this surviving element must be T. Given the version space Σ_P at stage P, then how should the student construct the next, (P + 1)-th, Ising training pattern ξ^P+1?

Consider two vectors J, J′ of Σ_P. Each of them has equal probability to be the truth vector T (the uniform Bayesian prior distribution is assumed). If J happens to be the truth, then the other vector J′ can be refuted by a test pattern ξ if sign(ξ; J′) = −sign(ξ; J). The probability of a randomly chosen vector J′ ∈ Σ_P being refuted by the test pattern ξ is then
On the other hand, every J ∈ Σ_P is equally likely to be the truth T, so we need to maximize the mean value of the above expression over all the different choices of J,
which leads to the following constraint
In other words, ξ^P+1 should be designed to divide the old version space Σ_P into two parts of (almost) equal size. This designed pattern ξ^P+1 must not be completely random, since the corresponding sum (6) for a completely random pattern will be of order . After ξ^P+1 has been examined, one half of the members of Σ_P will be discarded and the surviving vectors form the new version space Σ_P+1. Let us remark that this idea of version space bisection began to be discussed in the mathematics community in the early 1970s,^[39] and it is underlying the widely appreciated optimal (minimum-error) Bayesian classification algorithm for the passive perceptron problem.^[14,40–41]

We test the performance of this conceptually simple designing principle on small perceptrons of size N ≤ 25, for which the whole version space can be stored in the memory of a desktop computer. In Fig. 2, we show how the entropy density s and the generalization error ε change with the density α of training patterns. The entropy density measures the volume of the version space, s ≡ (1/N)log₂|Σ_P|. The generation error is computed as the probability that a randomly sampled binary test pattern will be mis-classified by a randomly chosen member J of the version space.^[2–3] If the training patterns are randomly and independently drawn from the configuration space {−1, +1}^N (i.e., the passive learning mode), the mean entropy density s and mean generalization error ε both decrease gradually with α and are positive when α exceeds unity. On the other hand if the training patterns are required to satisfy Eq. (6) we find that the mean entropy density s decreases linearly from s = 1 to s = 0 as α increases from 0 to 1, and at α = 1 the generalization error ε becomes exactly zero. In other words, perfect inference of the N-dimensional Ising vector T is achieved by the active strategy (6) with only N one-bit queries (which only return ±1 values). Compared with the deductive reasoning approach, log₂N training patterns are saved following the designing principle (6). No algorithms can do better than this Bayesian strategy, because at least N measurements are needed to exactly fix an N-dimensional vector.

Fig. 2

Figure Option ViewDownloadNew Window

Fig. 2 The active learning strategy (6) outperforms passive learning on small Ising perceptrons: (a) entropy density s (in units of bit), (b) generalization error ε. Training patterns are added one after another, α = P/N is the instantaneous density of patterns (N is the number of input neurons and P is the number of training patterns). Each data point is obtained by averaging over 1,000 independent runs of the passive (Random) or the active (Design) learning algorithm.

These simulation results indicate that, in principle, perfect learning using only N training patterns is possible. But directly employing Eq. (6) to construct new training patterns is practically feasible only for small systems. When the dimension N becomes large the version space Σ_P (for P small) will be too huge to enumerate. We must convert Eq. (6) into a form suitable for implementation in large systems. This issue is addressed in the remaining part of this section.

With respect to all the accumulated P training patterns at the end of the P-th learning stage, the volume of the version space Σ_P (the partition function) is expressed as
where σ^μ is the true label of pattern ξ^μ, and Θ(x) is the Heaviside step function such that Θ(x) = 1 for x > 0 and Θ(x) = 0 for x ≤ 0. The probability of weight vectors J in Σ_P is
Notice that this probability distribution depends on the details of the P training patterns. If J ∈ Σ_P we have , otherwise . Besides this joint distribution of all the N entries J_i of J, we are also interested in single-weight marginals. The mean value of weight J_i among all the vectors of Σ_P is
Similarly, the mean value of J_iJ_j (pair correlation) is
When i = j we have 〈J_iJ_i〉_P = 1 due to the Ising nature of the weights. The training patterns bring correlations among the different weight variables. A consequence of these complicated correlations is that 〈J_iJ_j〉_P ≠ 〈J_i〉_P〈J_j〉_P for i ≠ j.

Now consider adding a new training pattern ξ to the perceptron. The distribution of the overlap q between ξ and the weight vectors J of Σ_P is defined as
where δ(x) is the Dirac symbol such that δ(x) = 1 for x = 0 and δ(x) = 0 for x ≠ 0. From this definition we see that the mean overlap is
The variance of the overlap q is defined as . By a simple derivation we find that
The overlap q is the sum of N random terms ξ_iJ_i (randomness coming from J_i). As the lowest-order approximation we assume that the central limit theorem is valid for q when N is large, even through the weights J_i are not independent. In other words, we approximate the probability distribution (11) by a Gaussian distribution:
(The possible breaking down of this Gaussian assumption will be discussed in Sec. 6)

According to the designing principle (6), the (P + 1)-th training pattern should refute half of the weight vectors in Σ_P. This means that the overlap between ξ^P+1 and the weight vectors of Σ_P should be positive for half of the elements J ∈ Σ_P and be negative for the remaining half. According to the Gaussian approximation (14), we see that the new pattern ξ^P+1 should have zero mean overlap value with the weight vectors of Σ_P, that is
In comparison with Eq. (6), the advantage of Eq. (15) is that the student does not need to memorize all the candidate truth vectors J but only need to evaluate the N mean synaptic weights 〈J_i〉_P. Equation (15) may be regarded as a linearized version of Eq. (6) with the highly nonlinear sign function replaced by a linear function. In the next section we discuss how to efficiently update the mean weights during the online learning process. We notice that the constraint (15) is very similar in form to the designing constraint discussed in some of the early papers.^[20,25] A significant difference is that our proposed constraint (15) involves the mean synaptic weights 〈J_i〉_P, instead of the synaptic weights J_i of a single weight vector stored in memory.

We employ simulated annealing^[42] to sample a maximally random pattern ξ^P+1 under constraint (15). An energy penalty is defined for each Ising pattern ξ as
and the corresponding probability distribution of ξ is
where the parameter β is the inverse temperature. The pattern ξ evolves by single spin flips at slowly increasing β values. At each elementary update step, (i) a randomly chosen entry ξ_i of ξ is flipped to the opposite value; (ii) if the energy difference ΔE ≡ E(ξ′) − E(ξ) between the modified pattern ξ′ and the old pattern ξ is non-positive, then this flip ξ_i → −ξ_i is surely accepted, otherwise it is accepted only with probability e^−βΔE. After N such elementary flip trials the value of β is then elevated by a constant factor r_β (β ← r_ββ). Finally, the spin configuration after a total number tN of spin flip trials (β has been recursively elevated t times) is picked as the new training pattern ξ^P+1. In this work we set r_β = 1.1 and t = 100, and set the initial value of β to be 0.01. We have checked that the numerical results of the next two sections are insensitive to the particular values of these parameters.

To exploit the designing principle (15) we must first compute 〈J_i〉_P for all the weight indices i. At P = 0 we know that 〈J_i〉₀ = 0 for all the synaptic weights J_i. But the task for P ≥ 1 is quite non-trivial and can not be made exact. In the online learning paradigm we compute 〈J_i〉_P approximately by iteration.

After the training pattern ξ^P+1 has been added to the system, the new distribution of the version space is related to the old through
where is the label of ξ^P+1. The mean value of J_i under is
Here, is the probability of J_i = +1 in the version space Σ_P, and is the complementary probability; and are, respectively, the conditional probabilities of ξ^P+1 being correctly classified by a weight vector J ∈ Σ_P given that J_i = +1 and J_i = −1. The defining expressions for and are 20a
20b
where (respectively, ) denotes the version sub-space of Σ_P which contains all the vectors J ∈ Σ_P with J_i = +1 (respectively, J_i = −1). Notice that and . Similar to the derivation of Eq. (14) we can approximate and by two slightly different Gaussian integrals (details in Appendix A). Then we get the following convenient iterative equation for the mean weights
Here R_P is a magnitude factor determined by
with the function f(x) being
The value of f(x) equals to unity at x = 0, and it then rapidly decays to zero as x increases. When x is negative f(x) rapidly approaches the asymptotic form −2x.

The iterative expression (21) agrees with the belief-propagation equation reported in Ref. [6] (see also Refs. [5,43]). Notice that if has the same (respectively, opposite) sign of σ^P+1, the value of 〈J_i〉_P+1 increases (respectively, decreases) from 〈J_i〉_P by an amount . Equation (21) therefore implements a specific Hebbian rule of experience accumulation. Notice also that 〈J_i〉_P = ±1 are two fixed points of Eq. (21), so if 〈J_i〉_P is wrongly estimated to be (say) −1 while the truth value is T_i = +1, there is no chance to correct this mistake by further learning. To ensure that the iteration process is able to escape from a wrong fixed point, we therefore slightly modify Eq. (21) as follows:
where the weighting function W(〈J_i〉_P) by default is equal to , but W(〈J_i〉_P) = W₀ if the sign of is opposite to that of 〈J_i〉_P and at the same time . The precise value of the cutoff parameter has a weak effect on the learning performance. After some preliminary experiments we finally set W₀ = 8 × 10⁻³.

To determine the numerical value of the magnitude factor R_P, we need to compute the numerical value of the overlap variance Δ(ξ^P+1). The first summation of Eq. (13) is of order N and is easy to compute. On the other hand, it is quite complicated to compute the second summation of Eq. (13). In this work we make the simplest approximation of independence among different weight variables, that is, 〈J_iJ_j〉_P ≈ 〈J_i〉_P〈J_j〉_P. Under this additional approximation then
and it is completely independent of ξ^P+1. This independence approximate expression is commonly adopted in the literature (see, e.g., Refs. [6,44]), it amounts to approximate the probability distribution by a factorized form. To improve the numerical accuracy of computing the mean weight values, the next step is to include at least partially the correlations between the weight elements (see, e.g., discussions in Refs. [6,44] concerning the continuous Perceptron). We leave this demanding issue for future work. (More discussion is made in Sec. 6 on weight correlations.)

We now test the performance of the simple designing principle (15). The following straightforward inference rule is adopted in the computer simulations: At the end of the P-th learning stage, the inferred truth vector is simply the sign vector of the mean weights 〈J_i〉_P, with
The relative inference error is defined as the relative Hamming distance between the inferred weight vector and the teacher’s weight vector T, that is

Before testing the active learning mode, we first consider the random passive learning mode, in which every newly introduced training pattern is drawn independently and uniformly at random from the set of 2^N Ising patterns. The mean value of the relative inference error of this passive mode, averaged over simulated independent online learning trajectories, is shown in Fig. 3(a) as a function of pattern density α. We find that when α < 5, the curves of mean inference error for different system sizes N are well superimposed onto each other, while for α ≥ 5 the mean inference error saturates to a small positive level whose height slightly increases with system size N (see inset of Fig. 3(a)).

Fig. 3

Figure Option ViewDownloadNew Window

Fig. 3 The performance of passive online learning. The P training patterns are fed to the student sequentially and they are independent random N-dimensional Ising vectors. The pattern density is α = P/N. The total number of simulated independent online learning trajectories is . (a) The mean inference error, i.e., the mean fraction of incorrectly inferred teacher weights. The inset shows the tail part of the numerical data in semi-logarithmic scale. (b) The success fraction, i.e., the fraction of simulation trajectories in which the inferred weight vector is identical to the teacher’s weight vector.

As another measure of performance we consider the success fraction, which is defined as the probability that the inferred weight vector is identical to the truth vector T in repeated independent run of the whole online learning process. For example, if in 4000 out of 10,000 independent runs then the success fraction is 0.4 at this particular pattern density α = P/N. Notice that the success fraction is not necessarily a monotonic function of α because it is possible that but . The success fraction of passive online learning is shown in Fig. 3(b) as a function of pattern density α. We find this fraction is first identical to zero for small α values, it then increases quickly when α exceeds 4 and finally fluctuates around a plateau level. Since the height of the plateau level decreases considerably with system size N, error-free inference will be impossible in the thermodynamic limit of N → ∞.

When constraint (15) is imposed in designing each new training pattern, we find that the learning performance is greatly enhanced. As shown in Fig. 4(a), the mean inference error reaches below 10⁻³ as the pattern density α is increased up to 2.2 and it then quickly drops to zero as α further increases slightly. The dramatic effect of active learning is most clearly demonstrated by the difference between Fig. 4(b) and Fig. 3(b). We see from Fig. 4(b) that the curve of success fraction becomes more and more sharper as the system size N increases, and all these different curves intersect at approximately the same value of α. Similar system size-dependent behaviors are commonly observed in finite-size scaling studies of continuous phase transitions.^[45] We conjecture that a well-defined dynamical phase-transition to perfect inference will occur at the value of α ≈ 2.23 in the thermodynamic limit of N → ∞. More thorough theoretical investigation on the large N limit of this learning dynamics will be carried in a follow-up paper.

Fig. 4

	Figure Option ViewDownloadNew Window
	Fig. 4 Same as Fig. 3, but for active online learning under the designing principle (15). Error-free inference is achieved at pattern density α ≈ 2.23.

When a new training pattern ξ^P+1, constrained by Eq. (15) but otherwise being maximally random, is sampled by simulated annealing (Eq. (17)), it is conditionally independent of all the earlier training patterns given the values of 〈J_j〉_P. But since the mean weights 〈J_j〉_P are determined through the accumulative mechanism (24), Eq. (15) indeed brings complicated correlations between ξ^P+1 and all its predecessors. If ξ^P+1 happens to be relatively similar to some of the old training patterns, its power in promoting active inference will be compromised.^[23,46] According to the geometric picture underlying the exact designing principle (6), it should be beneficial to explicitly require (at least approximate) orthogonality between ξ^P+1 and the training patterns introduced during the last M steps.

To implement these additional orthogonality constraints, we modify the energy function of the simulated annealing process as follows:
The second energy term is equal to the average squared overlap between ξ and an old pattern ξ^μ. The parameter λ controls the relative importance of the additional orthogonality constraints. In the present work we set λ = 1, and considering that there are N mutually orthogonal vectors in an N-dimensional space, we set M = N − 1. (We have not yet tried to optimize the values of λ and M.) Each new training pattern is then sampled by simulated annealing starting from an initial completely random pattern. The only difference is that the energy function in Eq. (17) now takes the form of Eq. (28).

The performance of the modified online learning algorithm is shown in Fig. 5. We find that error-free inference of the teacher’s weight vector can be achieved with high probability after encountering P ≈1.9N training patterns. Compared with the results of Fig. 4, the additional orthogonality considerations indeed lead to a remarkable boost to the learning efficiency.

Fig. 5

	Figure Option ViewDownloadNew Window
	Fig. 5 Same as Fig. 3 and Fig. 4, but for active online learning under the designing constraint (15) and the additional orthogonality constraints, see Eq. (28). The number of stored training patterns is set to be M = N−1.

It may be possible to further improve the learning performance by optimizing the parameters λ and M of Eq. (28). Furthermore, the energy function (28) may not necessarily be the best way to incorporate both the designing constraint (15) and the additional orthogonality constraints. For example, it may be even better to consider all the P old patterns (instead of only the last M ones) with non-uniform weighting factors.

In this work we considered the Bayesian active learning principle (6) to infer the teacher’s weight vector of an N-dimensional Ising perceptron. Each new Ising training pattern is not randomly drawn as in passive learning but is designed with the aim of splitting the current version space into two equal sub-spaces. This designing principle was exactly implemented for small systems to achieve error-free inference using only N training samples (Fig. 2). When exhaustive enumeration becomes unfeasible for large systems, we derived a simple constraint (15) based on this principle and demonstrated that error-free inference is achievable with P ≈ 2.3N training samples (Fig. 4). The number of training samples was further reduced to P ≈1.9N after imposing additional orthogonality constraints on the training patterns (Fig. 5). On the other hand, the deductive reasoning algorithm discussed in this paper is guaranteed to achieve error-free inference with at most N+log₂N queries and therefore is much superior to the Bayesian strategies discussed in Secs. 4 and 5.

In deriving the constraint Eq. (15) from the Bayesian principle (6), we have approximated the overlap probability profile (Eq. (11)) by a Gaussian distribution. Maybe this Gaussian assumption is only valid for sufficiently small values of the pattern density α. With the addition of training patterns, the volume of the version space becomes more or more small. At the same time the shape of the version space may become more and more irregular. One highly possible scenario is that, when α exceeds certain threshold value, the version space breaks up into many well-separated sub-spaces with each of them having a different set of mean weight values {〈J_i〉_P}. As a consequence, the overlap probability profile should be described as a weighted sum of many distinct Gaussian distribution functions (one for each version sub-space), and then Eq. (15) should be modified accordingly.

From the academic point of view, active learning in the presence of ergodicity breaking is a very interesting challenge. With an accurate approximation to the overlap probability profile , the efficiency of the active learning process may closely approach the theoretical limiting value of α = 1. We hope that significant theoretical and algorithmic progresses will be made in the near future on this important research issue.