{'fraction_non_alphanumeric': 0.03424818203143326, 'fraction_numerical': 0.009747960486876744, 'mean_word_length': 4.6539935160624815, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Target-Independent Active Learning via Distribution-Splitting

To reduce the label complexity in Agnostic Active Learning (A^2 algorithm), volume-splitting splits the hypothesis edges to reduce the Vapnik-Chervonenkis (VC) dimension in version space. However, the effectiveness of volume-splitting critically depends on the initial hypothesis and this problem is also known as target-dependent label complexity gap. This paper attempts to minimize this gap by introducing a novel notion of number density which provides a more natural and direct way to describe the hypothesis distribution than volume. By discovering the connections between hypothesis and input distribution, we map the volume of version space into the number density and propose a target-independent distribution-splitting strategy with the following advantages: 1) provide theoretical guarantees on reducing label complexity and error rate as volume-splitting; 2) break the curse of initial hypothesis; 3) provide model guidance for a target-independent AL algorithm in real AL tasks. With these guarantees, for AL application, we then split the input distribution into more near-optimal spheres and develop an application algorithm called Distribution-based A^2 (DA^2). Experiments further verify the effectiveness of the halving and querying abilities of DA^2. Contributions of this paper are as follows.


Introduction
Active learning (AL), leveraging abundant unlabeled data to improve model performance, has been widely adopted in various machine learning tasks, such as text processing (Li et al., 2012), image annotation (Li and Guo, 2013), multi-label classification (Huang et al., 2017) (Huang et al., 2015), and multi-task learning (Harpale and Yang, 2010) (Fang et al., 2017), etc. Through AL, the researchers (human) can strategically query the "highly informative" data (McCallumzy and Nigamy, 1998) to reduce the error rate of the current learning model in different classification tasks. However, a natural question that arises is the following: If we increase the size of active query set, whether the error rate would keep decreasing? Besides this, can we find an -optimal ( is the error rate of prediction) hypothesis that is nearly as we desire?
This question has been considered in the Agnostic Active Learning (w.r.t A 2 algorithms) community, which studies the hypothesis relationship in VC (Vapnik-Chervonenkis) class (Vapnik and Chervonenkis, 2015) of the version space by splitting the hypothesis edges. With a goal of minimizing the query number of unlabeled data, A 2 algorithms   (Balcan et al., 2006) tried to improve the learning models with labeled data sampled from various distributions and diverse noise conditions. Specially, halfspaces learning Gonen et al. (2013) is one of the agnostic active learning problem over a unit sphere to explore the theoretical guarantees on error rate and label complexity (the number of labels requested before achieving a desired error).
Under the assumption of uniform distribution over a unit enclosed sphere with bounded noise condition, an A 2 algorithm which actively learns a homogeneous halfspace, can help to decrease the label complexity. However, the halfspaces heavily depend on the initial hypothesis. For example, Figure 1.(a) describes a binary classification task in a two-dimensional sphere (circle) with uniform distribution and arbitrary halfspace can generate a perceptron  classifier. To reduce the error rate of the initial hypothesis, researchers always sample some target points from the colored candidate pool to shrink their "volumes" (areas) as fast as possible since the volume size decides the label complexity. However, there exists a challenging gap for those A 2 algorithms: the VC dimension of sampling heavily depends on the distance between the initial and target ( -optimal) hypothesis, and this problematic setting is called "target-dependent" label complexity (Gonen et al., 2013). That is, for a poor input hypothesis which is far away from the desired hypothesis, it would lead to a large volume of the candidate hypotheses pool. Then, the label complexity of querying increases dramatically. Therefore, the volume of the version space decides the dependence of the querying target to the initial hypothesis and a series AL approaches involved with shrinking volume of version space could be loosely defined as volume-splitting.
To decrease the dependence of the initial hypothesis, (Dasgupta, 2006) removed the hypotheses edges with large model distances to split the volume of version space. In their work, the version space which includes all the feasible hypothesis, is embedded as a graph in the high dimensional space. After splitting, the VC dimension decreases dramatically. Then, the upper bound of the label complexity is also reduced.  Figure 1.(a), the general AL approaches always halve the "volume" of the colored candidate area to reduce the VC dimension, but this process heavily depends on the initial hypothesis. In Figure 1.(b), we halve the number of the input distribution to obtain a halfspace with sparse density. Then, we split the halfspace to a number of spheres to represent its distribution structure.
However, volume-splitting of version space still can not tackle the target-dependent problem successfully since: 1) doing volume-splitting in the candidate data pool can reduce the effect of the initial hypothesis but cannot completely get rid of its dependence; 2) volume-splitting is hard to be implemented in active learning task of input distribution, although this theoretical description has attracted the attention of researchers. Thus, finding an alternative splitting strategy which can both reach the same theoretical goal as volume-splitting of version space and deal with application tasks of input distribution is necessary. Inspired by these observations, we begin to collect evidences to consider the relationship between version space and input distribution.
Based on the perspective of (Cao et al., 2018a), the VC dimension of version space decides the hypothesis number and plays an important role in its volume description. Therefore, we are motivated to map the notion of volume into the number density of input distribution. Especially for a bounded local distribution, the more data located in the input distribution space, the larger the volume of version space would be (See Figure 2). Another perspective which supports our assumption is the input distribution induces a natural topology on the version space and a local hypothesis would easily capture its relevant local distribution . From the above perspectives, here we would perform the splitting on input distribution with the following advantages: 1) provide theoretical guarantees on reducing label complexity and error rate as volume-splitting; 2) break the curse of initial hypothesis; 3) provide model guidance for a target-independent AL algorithm in real AL tasks.
In this paper, we firstly shrink the volume of version space to obtain the halfspaces to reduce its VC dimension via halving the number density of the input distribution. With the theoretical advantages of halfspaces on error difference and label  complexity, we continue to split the input distribution into more near-optimal spheres to represent its structure. Contributions of this paper are described as follows.
-We connect version space and input distribution by number density, which provides a more natural and direct way to describe the hypothesis distribution than volume. -We present theoretical improvement guarantees on error rate difference, fall-back analysis, and label complexities with noise conditions for the halfsapce which halves the number density of the input distribution. -We propose a distribution-splitting strategy for learning the structure of the input distribution. -We propose a "target-independent" AL algorithm called DA 2 which is independent of the initial labeled set and classifier.
The outline of the paper is as follows. Related studies are mentioned in Section 2. In Section 3, we describe the preliminaries of this paper. The theoretical motivation of hypothesis and distribution is presented in Section 4. The proposed distributionsplitting strategy and the advantages of halfspaces are reported in Section 5. Experimental results of halving and querying abilities of the proposed algorithm are presented in Section 6. Conclusions are drawn in Section 7.

Related Work
The AL algorithms with input distribution aims to find the data which have "highly informativeness or representativeness" for the unseen queries. However the sampling targets heavily depend on the labeled set and classifiers .
To find an efficient labeling-tolerant algorithm, the agnostic active learner studies the -optimal hypothesis from VC class (or hypothesis class). The goal is to improve the performance guarantee of the current hypothesis by minimizing the label complexity in version space over different distribution assumptions. In this section, Section 2.1 introduces the AL strategies with input distribution, Section 2.2 presents the theoretical AL with VC class, and Section 2.3 describes the halfspaces and volumesplitting.

Active Learning with Input Distribution
The AL algorithm samples those data which can significantly improve the performance of the current learning model. By performing AL sampling strategies, even the worst annotator would no longer annotate such a large amount of labeled data because of expensive human cost. To optimize the querying process, the membershipquery strategy (Freund et al., 1997) tried to find the most distinguished sample in a set by asking subset membership queries. In structural data space with margins, the AL algorithm optimized the queries close to the hyperplane under the support of SVM theory. These approaches can be loosely approximated as finding the "highly informative" samples (Tosh and Dasgupta, 2017) (Gal et al., 2017) (McCallumzy andNigamy, 1998) to improve the performance of the model it learned.
The another sampling criterion is to pick up the representative samples from the unlabeled data pool. With each query, the researchers want to minimize the distribution differences between the labeled and original input sets, such as the experimental design (Yu et al., 2006) (Zhang et al., 2011) which measures the regression between data and their labels. To strengthen the sampling performance, (Huang et al., 2014) developed the informativeness and representativeness as an uniform standard with a given evaluation function. Then a series of AL algorithms which exploited the data with both the two characteristics kept appearing (Du et al., 2017).
However, these strategies heavily depend on the categories of classifiers and labeled set. For example, the AL algorithms using maximum margin of classification hyperplane could not break the curse of SVM classifier. Moreover, the influence of the input labeled set size is underestimated. In our investigation over some AL work, the researchers always query at least 50% of the total data as the initial labeled set, such as (Cai and He, 2012) (Du et al., 2017) (Shi and Shen, 2016). However, the real world might only provide very few labeled data for researchers and the percentage of the labeled data may be less than 10% or 5% of the total number of the data set, even less.

Active Learning with VC Class
To reduce the dependence of labeled set, the Agnostic AL tries to find an -optimal hypothesis from the hypothesis class H in version space. In this theoretical learning task, we are given access to a stream of unlabeled data drawn i.i.d. from a fixed distribution. Since agnostic AL could help to achieve such dramatic reduction in label complexity, substantial agnostic AL frameworks under various of assumptions of classifiers and labeled set were proposed (Dasgupta, 2006) (Balcan et al., 2006). Among them, the most popular strategy is pool-based AL which assumes there exists a perfect classifier when giving a fixed sample number. With this prior promise, they want to minimize the query number to decrease the difference between the perfect and final hypotheses. However, most of these agnostic AL algorithms either make strong distribution assumptions such as separability, uniform input distribution or are generally computationally prohibitive, thus they cannot effectively be applied in AL application tasks .

Halfspaces and Volume-Splitting
A halfspace is either of the two convex sets into which a hyperplane divides the enclosed-bounded affine space. In halfspaces learning, researchers study the perceptron training in the uniform distribution to find the optimal halfspace over a unit sphere, such as Figure 1.(a). The sampling goal is to reduce the vector classifier angle θ as fast as possible, in which θ decides the volume of the candidate hypothesis pool. Under this training assumption, the researchers try to reduce the label complexity by two methods: (1) halving the volume of the candidate pool to a halfspace, (2) binary search for halving (Tong and Koller, 2001).
By halving, the learner can fast reduce the VC dimension of version space to decrease the label complexity of querying since a part of hypotheses would be removed. Therefore, volume-splitting strategy is an effective solution whether in AL theory or application tasks.

Preliminaries
In this section, we present the preliminaries for the learning rule of A 2 algorithms which use a disagreement coefficient to control the sampling inputs in Section 3.1. Specifically, we present one important volume-splitting strategy called (ρ, , τ )-splitting in Section 3.2. Then, we define the target-dependent and target-independent Agnostic AL by halfspaces learning in Section 3.3.

Learning Rule
The A 2 algorithm queries the label of one example based on the empirical rule of error rate difference after assigning positive and negative labels. To describe the basic The sphere with radius and center settings The distance between the two input objects model of A 2 algorithms, we present some preliminaries in this section. In addition, the mathematical notations of this paper are described in Table 1. Given a data set X with binary class labels, and D is the distribution over X × {±1}, we divide X into two groups: L and U, in which L contains the labeled set of X , and U contains the unlabeled set. Let err(·) denote the error rate of predicting D by training the input set, {x, −ŷ} and {x, +ŷ} denote the queried data with different label assumptions, t denote the tth query, L t represents the labeled set in the tth query, and k denote the total number of queries. Here we define the empirical rule for querying by the sampling margin ∆ t , where h −ŷ and h +ŷ represent the classification hypotheses after queryingx with different label assumptions. By using this model rule, ∆ t is used to fast shrink the number of the unlabeled data of the candidate pool by increasing the margin. Then, it can shrink the volume of the version space to reduce the VC dimension.
To estimate ∆ t , the A 2 algorithms use the disagreement coefficient (Hanneke, 2007) where H is the hypothesis class over X , h * is the hypothesis with the lowest error rate ν, B(h, r) = {h ∈ H : (h, h ) < r}, and (·, ·) denotes the metrical distance between the two inputs. Generally, θ bounds the querying amount by calculating the probability mass of hypotheses in the ball B(h * , r). It is a theoretical assumption in version space which highlights the learning model of AL.

Volume-Splitting
To find the data which could reduce the VC dimension of the unlabeled data pool after querying its label, the volume-splitting strategy tries to design a margin factor evaluation rule, in which (ρ, , τ )-splitting  is one important approach. In its splitting rule, the rule is to find the subset of hypotheses S which satisfies (ρ, , τ )-splitting  in all finite edge-sets Q ⊂ S × S, in which ρ is a fraction, is the error rate, and τ is the number needed of unlabeled data. Under this policy, the ρ-splitting rule is defined as to split the hypothesis edges by Following this, (ρ, , τ )-splitting is defined as To find the instance with the highest informativeness, the agnostic AL algorithms select the data which maximally split Q, and then return the remained hypotheses. Considering the effectiveness of the splitting algorithm, we study it in the agnostic AL learning task which is independent of the structural assumption of uniform distribution. Without the fixed assumption on distribution, the hypotheses distances would be the most important splitting factor. Let h t be the current hypothesis, x i and x j be two candidate sampling points, there exists a new disagreement coefficient for agnostic AL learning task,θ Let m be the number of the unlabeled data in the candidate pool, we obtain the following hypothesis relationship, Based on this relationship set, we will use it to remove some hypotheses to shrink the VC dimension.

Target-Dependent and Target-Independent Agnostic AL
Halfspaces learning provides clear visualization to describe the hypothesis relationship. Based on this advantage, we will define the target-independent active learning over a unit sphere in this section.
Target-dependent label complexity is a challenging problem in AL. It shows the performance of the unseen sampling process heavily dependents on the initial hypothesis since they always select those points which could maximize the hypothesis or distribution update. Here we present the related mathematic definitions for targetdependent Agnostic AL by halfspaces learning. Firstly, we define the halfspacs: Definition 1 Halfspaces. Learning a halfspace c * (Alabdulmohsin et al., 2015)   in a unite instance space is to estimate an unknown vector µ, Let v t be the perceptron vector on the tth query, θ t be the angle between v t and µ, we give the following definitions: Definition 2 Target-dependent Agnostic AL. With a probability of 1 − δ to select an arbitrary point on D over an unit sphere, the probability of a lower error rate is (1 − δ) θ t π ≤ 1 2 . Even using the halving algorithm, the label complexity is Ω(In θt π ).
Different from the target-dependent AL, the target-independent AL requires the unseen sampled targets is independent of the initial hypothesis.
Definition 3 Target-independent Agnostic AL. With a probability of 1 − δ to select an arbitrary point on D over an unit sphere, the probability of a lower error rate is Intuitively, learning the structure of distribution could help to address the targetdependent problem with a certain sampling selection. In real AL tasks, the targetindependent would mean the sampled target is dependent of the input training set.

Hypothesis and Distribution
In Section 4.1, we would firstly reveal the monotonic property of active query set to show the uncertain error rate change after querying. Then, we discuss the bottleneck of informative AL and describe our splitting rule by representation sampling in Section 4.2. Finally, we discuss the relationship between error rate and number density of input distribution in Section 4.3.
Based on these theoretical analysis, we are motivated us to do the splitting on input distribution to learn the structure of the input distribution to address the targetdependence challenging.

Monotonic Property of Active Query Set
To observe the error rate change after increasing the size of active query set, we follow the perceptron training (see Figure 1(a))  to analyze the hypothesis relationship. In our perspective, training the updated hypothesis will result in two uncertain situations: (1) the error rate declines after querying, and (2) the error rate shows negative (or slow) improvement when querying a lot of unlabeled data. Therefore, the monotonic property of active query set size and error rate is unknown. The following theorem shows a mathematic description for this discovery.
Theorem 1 The monotonic property of active query set and error rate is unsatisfactory or negative. Suppose t and t+1 respectively be the error rates of training the active query sets D t and D t+1 . There must hold a uncertain probability δ which satisfies Proof. Suppose the vector µ be the optimal diameter which classifies the unit circle correctly, v t be the current classification perceptron at the tth querying, and θ t be angle between vectors, we then have v t+1 = v t + yx (w.r.t y is the label of sample x), in which v t is trained by D t , and v t+1 is trained by D t+1 . We divide the the circle into two parts: θ-sector and θ -sector, where θ-sector denotes the areas between v t and v, and θ -sector denotes the area out of it. Considering the two cases: (1) When the query is in θ -sector, i.e., θ t+1 > θ t , we will have t < t+1 . (2) When the query is in the θ-sector, i.e., θ t+1 < θ t , we have the conclusion of t > t+1 . Finally, Theorem 1 holds.
Theorem 1 describes our first perspective of this paper about the relationship between the performance of hypothesis and active query set size. It shows that the error rate probability reduces with the increase of the active query set size.

Bottleneck of Querying Informative Sample
The researchers want to obtain the optimal hypothesis path in the version space by querying informative points (See Figure 3.(a)). However, the hypothesis distances are very hard to calculate. Especially when the initial hypothesis is very far from (c) Fig. 3: Illustration of volume-splitting over version space. The graph structure denotes the version space, each node denotes one hypothesis, and the red lines denotes the hypothesis distances. In Figure 3.(a), researchers try to find the optimal path to h from h 0 , where h represent the hypothesis with error rate , and h 0 represents the initial hypothesis. In Figure 3.(b), researchers split the version space into a number of near-optimal spheres to reduce the VC dimension. In Figure 3.(c), researchers respectively use one hypothesis to represent each sphere to learn the structure of the version space.
the optimal hypothesis, the path finding process might be more difficult. Thus, there exists a bottleneck for the AL sampling by querying informative samples.
Since the VC dimension affects the path finding process largely, we use the volume-splitting to split the version space into a number of near-optimal spheres (Figure 3.(b)). Then, we remain the structure of the version space for AL sampling (Figure 3.(c)). This way aims to shrink the number of the candidate paths to reduce the uncertain performance of sampling in the path finding process. However, this strategy is adopted in the version space, we need to study a new splitting strategy which not only can achieve same representation results as volume-splitting but also can be applied in AL with input distribution. Therefore, we perform the splitting idea on input distribution by finding k local balls with the following rules.
Given B D is the ball which tightly enclose D, and {B 1 , B 2 , ..., B k } are the k local balls with the condition of ∀i, B i ⊂ D. Let V ol(·), r(·) respectively define the volume (Cao et al., 2018a) and radii of the input hypothesis class, the splitting must satisfy (1) , and (4) (c i , c * ) < 2r(B D ), where c i denotes the center of the ith splitted ball, and c * denotes the center of B D .

Error Rate with Number Density
Following the perceptron training in the unit circle with uniform distribution, we find the error rate grows with the number density of input distribution.
Proof. Let B denotes a unit circle with n samples, we have err(D t ) = θt π . After querying more samples, we obtain err(D t+1 ) = θt+1 π . In the unit circle, the volume of it is V ol(B) = π = n Den(B) . Then, the theorem is as stated.
Error rate difference represents the distance between two arbitrary hypotheses. By observing the above theorem, we can find number density affects the hypothesis distances. Besides this, we know the number density largely decides the VC dimension since V cdim(B) = n k=1 n k = 2 n = 2 πDen(B) . Based on the two reasons, number density is a more direct way to describe the hypothesis distribution than volume in version space. Therefore, we are motivated to map the volume of version space into the number density of the input distribution to both reduce the VC dimension and find a lower label complexity. In addition, we will define Den(B) for the real AL tasks in Section 5.3.2.

Distribution-Splitting for Agnostic Active Learning
By using a heuristic greedy selection, we halve the number density of input distribution to obtain the halfspaces in Section 5.1. Then, we discuss its theoretical advantages in Section 5.2. With these guarantees, Section 5.3 splits the halfspaces of input distribution into a certain number of local balls to find a near-optimal representation structure.

Halving Number Density for Halfspaces
By sorting the hypothesis distance of each pair, we could use a halving threshold α to cut the number density of the input distribution to a half. The cutting rule is: if (h t,xi , h t,xj ) ≥ α, we will remove x j from X . After the cutting, H will be reduced in to one halfspace H * .
In hypothesis class H, the VC dimension of H and H * could be written as Proof. The proof could be adapted from (Balcan et al., 2007)  .
Based on the above discussion, we could easily observe that the values of the two properties of halfspaces are lower than that of the original hypothesis class since the VC dimension is reduced.

Advantages of Halfspaces
To observe the advantages of halfspaces, Section 5.2.1 analyzes the bounds of error differences between the hypotheses with positive or negative labeling assumptions, Section 5.2.2 discusses the upper bound of error rate by fall-back analysis, and Section 5.2.3 then describes the label complexities in η-bounded and v-adversarial noise conditions.

Bounds of Error Difference in Halfspaces
In this learning process, we still use the greedy strategy of halving to split the local unit ball B(h * , r). Before splitting, here we present the halving guarantees of error rate difference on the distribution of halfspaces.
Theorem 3 Let D be the distribution over H * , F be a family of functions f : Proof. Following With the similar inequality in halfspace, let α t = (8/n)In(8S(H * , 2t) 2 )/δ, Let us rewrite the above equation as ∆ ≤ γ 1 + γ 2 + γ 3 + γ 4 for the four parts, in which each part is within a pair of brackets. Considering the number density of D is smaller than that of D, there exists err By this lemma, the error rate of halfspcaes guarantees the decrease. However, it has relationships with the size of D. To obtain the structure of the version space, we continue use the halving approach to split H to k local balls with a fall-back and bounded noises-tolerant guarantees.

Fall-Back Analysis in Halfspaces
Fall-back analysis helps us to observe the upper bound of error rate in the halfspace. Before analyzing the fall-back of querying, we need some technical lemmas.
Theorem 4 Assume there exists a hypothesis h f which satisfies err D (h f ) ≤ err D (h * ).
If the A 2 algorithm is given by k queries with probability of 1 − δ, let ν = err D (h * ), the error rate of halfspace is at most ( √ ν + β k ) 2 .
Proof. Using Lemma 4, we obtain err With this upper bound performance, the halfspaces can have a convergent error rate guarantee and this bound is lower than that of the input distribution without halving. Next, let us analyze the bounds of the label complexity in the noise settings.

Bounded Noise Analysis of Halfspace
Under the uniform assumption, noises affect the unseen queries. Here we discuss the label complexities of the halfspace in η-bounded and v-adversarial noise settings (Yan and Zhang, 2017).
Theorem 5 For some η ∈ [0, 1/2] with respect to µ (w.r.t. definition of halfspaces), if for any x i ∈ D , P[Y = sign(µ · x i )|X = x i ] ≤ η, we say the distribution of D is η-bounded (Massart et al., 2006). Under this assumption, (1) there are at most O( d (1−2η) 3 ) unlabeled data, and (2) the number of queries is at most Theorem 6 For some v ∈ [0, 1] with respect to µ, if for any x i ∈ D , P[Y = sign(µ· x i )|X = x i ] ≤ v, we say the distribution of D is v-adversarial noise condition (Awasthi et al., 2014). Under this assumption, (1)there are at most O( d 2 ) unlabeled data, and (2) the number of queries is at most O(d In 1 2 ).
Compared with the original input distribution, the label complexity of our proposed halfspace is lower since the VC dimension of the halfspaces is reduced.

Distribution-Splitting for AL Tasks
Halfspaces provide theoretical advantages without special distribution assumptions since number density is independent of arbitrary distribution situation. Therefore, in the application tasks, we firstly halve the number density of input distribution to learn halfspaces via an active scoring strategy in Section 5.3.1. After obtaining the halfspace, Section 5.3.2 splits the halfspace into k near-optimal balls via the distribution density. Then, Section 5.3.3 proposes the DA 2 algorithm for AL querying.

Active Scoring for Halving
Active scoring is used to measure the local representativeness of an arbitrary data, in which the score value monotonically grows with the representativeness. Here we use the sequential optimization Yu et al. (2006) to find k data with the highest scores to represent the input data distribution. Its definition is as follows.
Score(x i ) = ||K(κ, :)K(:, κ)|| 2 K(κ, κ) + u) , ∀i where K is the kernel matrix of X , κ represents the sequence position of x i in X , κ represents the sequence position of the data with current highest confidence score in X , and u is the penalty factor of the global optimization.

Splitting by Distribution Density
Considering our theory perspective of number density, performing splitting in the input distribution by it has already been proved effective. But, ind-dimensional space, calculating the number density of a high dimensional-bounded space is challenging. Therefore, we use the exponential value of the distribution density to fast split the input distribution. Here we define the number density as where u i , σ i respectively denote the mean value and variable of the local ball B i . Then, we propose the splitting rule: To solve the above minimum optimization problem, we would like use the (1+ε)approximation (Tsang et al., 2005) approach to increase the ball radius to make it converge, where ε is set by the empirical threshold.

Querying by DA 2
How to query the unlabeled data is the important step for AL tasks. In this section, we propose a Distribution-based A 2 algorithm (DA 2 ) to implement the proposed distribution-splitting strategy. The algorithm has two steps.
Step 1 is to find a halfspace which contains the optimal data sequences by active scoring of Eq. (16).
Step 2 is to solve the optimization of Eq. (18). Finally, the output of the algorithm is used as the AL queries.

end 5
Find the sequence j with the maximum value of Ω.
6 Add x j to X * .

Evaluation
In the algorithm description, we know the DA 2 algorithm performs the querying in the halfspace. Thus, the halving ability would play an important role in its AL querying.
In this section, we investigate the halving and querying performances of DA 2 algorithm on six structured clustering and seven unstructured symbolic data sets. Before the test, we use the RBF kernel to transfer the input space into a non-liner kernel space to run DA 2 algorithm, where the used kernel sigma parameter is 1.8. To compare their classification performance of different AL algorithms, the LIBSVM (Chang and Lin, 2011) and error rate are respectively set as the default classifier and evalu-ation standard. Furthermore, we present the probabilistic explanations and models differences analysis for the two groups of experimental results.

Effectiveness of Halving
To verify the halving ability of DA 2 algorithm, we do passive sampling in the input space and halfspace to compare their prediction abilities on the input space. The tested data sets are six UCI real data sets: sonar, german, iris, monk1, vote, ionosphere, and two sub sets of letter data set: DvsP and A-D, where A-D represents the instances of AvsBvsCvsD. In the experimental process, we do passive sampling 10 times to obtain the mean error rate under different querying number settings in the two different spaces. Figure 4 has drawn the tested results.
By observing the change of the two curves, we could find the querying ability of the halfspace is better than that of the original input space since the halfspace has removed some "redundant points" (Cao et al., 2018b) which have small influences on the performance of the training model. Let us assume there are p "effective points" (Cao et al., 2018b) which greatly decide the performance of the final learning model in the input space. Under the limited training input number k, if we do not consider the influences of the classifiers and parameter settings, the probabilities of obtaining an -optimal hypothesis in the two spaces respectively are P , where p is the number of the effective points of the halfspace.
Since the sequential optimization has obtained success in representation sampling, p would be very close to m. Therefore, P(D) < P(D ).

Optimal Accuracy of Querying
The experiments of halving have shown the halfspace could have a better passive sampling performance compared with the original input space. It provides guarantee for the distribution-splitting in the halfspace. However, the most of AL work are based on the labeled set. To verify the target-independence of the proposed algorithm, we set the size of the initial training set be the class category via randomly selecting one data from each class. Because the labeled set-based AL algorithms must show negative performances when the input set is small, we try to minimize the influences of the labeled set by training their parameters. Under different querying number settings, we collect the results of 100 times to obtain their optimal prediction results In this group of experiments, we compare the AL abilities of three mainstream algorithms including Hieral, TED, GEN. The description is as follows: -Hieral:  utilizes the prior knowledge of hierarchical clustering to actively annotate more unlabeled data by an established probability evaluation model, but it is sensitive to cluster structure. -TED: (Yu et al., 2006) is also called T-optimization, and prefers the data points that are on the one side hard to predict and on the other side representative for the rest of the unlabeled pool. -GEN: (Du et al., 2017) pays attention on the data which minimizes the difference between the distribution of labeled and unlabeled sets. Figure 5 presents the error rate curves of the five AL approaches on different tested data sets. Although we have maximized the model performances of the labeledbased AL algorithms, the performances of DA 2 algorithm are still better than them. To reveal the potential reasons behind their performances, we report the probabilistic and model explanations for this group of tests.
In the probabilistic analysis, if we assume all the learning algorithms could obtain the -optimal hypothesis in each test, we will have the following results: (1) for the uncertain AL algorithms, an arbitrary input set could lead to an -optimal hypothesis, and P( > | ) = 1; (2) in this group of test, an arbitrary input set has an approximate probability of P( = | ) = 1 100 to obtain the best classification result; (3) for the target-independent DA 2 algorithm, the trained hypothesis is unique and P( > | ) = 0; (4) in this group of test, an arbitrary input set has a certain probability of P( = | ) = 1 to obtain the best classification result.
To analyze the model differences of these algorithms, we present the following specific discussions. (1)The idea of Hieral is active annotating and it depends on the cluster assumption of version space. Its classification ability in the unstructured data sets such as letter data sets is unstable, and the recorded error rates are higher than that of other approaches, although we have increased the test number. (2)TED tends to select those points with large norms, which might be hard to predict, but not be able to best represent the whole data set. Also, the noises will be sampled in its querying set. So the reported classification results are good but not the best. (3) GEN always presents disappointed results at the beginning of training in all tested data sets and its error rate declines rapidly with the increase of queries. The reason is that the established objective function prefers the data located at the center area of classes, which can't reflect the complete class structure well. (4) Compared with the above algorithms, DA 2 algorithm halves the number density of the data distribution into a halfspace which removes most of the redundant points. The remained points, which represent the local data distributions, help the learner to obtain the structure of the original data distribution. In the reported error rate curves, this represented structure shows effective sampling guidance when the number of queries are not big.

Conclusion
The A 2 algorithm can provide strong theoretical guarantees on learning an agnostic AL task under fixed distribution and noises conditions. However, the label complexity of querying heavily depends on the initial hypothesis. This generates a challenging gap between theoretical guarantee and application performance of A 2 algorithms.
To bridge this gap, we use the distribution-splitting strategy to halve the number density of the input distribution to reduce the VC dimension of the version space. With the reduction of error rate and label complexity, we split the original data distribution into a halfspace which retains the most highly informative data for the unseen sampling. In the constructed halfspace, we then continue to use the distributionsplitting approach to find a number of near-optimal spheres to represent an arbitrary agnostic input distribution. The proposed DA 2 algorithm further demonstrates the effectiveness of the halving and querying abilities of the proposed distribution-splitting strategy.