Introduction

Active class selection (ACS) [11,9] allows machine learning practitioners to actively choose the label proportions of their training data. This freedom of choice is due to a class-conditional data generator, e.g. an experiment or a simulation, which acquires feature vectors for arbitrarily chosen classes. Data generators of this kind appear in various use cases, such as astro-particle physics [4,3], gas sensor arrays [11], and brain computer interaction [13].

Lomasky et al. [11] have put forward the idea that such a generator can be leveraged in a sequence of multiple acquisition steps, as sketched in Fig. 1. In each step, a classifier is trained and evaluated on all examples that have been acquired so far, starting from a small initial data set (i). Based on the classifier's performance, a data acquisition strategy is then allowed to choose the label proportions of the next acquisition step (ii). The class-conditional data generator realizes these proportions, i.e. it produces a batch of labeled data according to the choice of the strategy (iii). This batch adds to the training set from which the classifier will be trained in all subsequent iterations. The promise of such a sequential and informed data acquisition is that the classifier can benefit in terms of data acquisition cost and performance, as compared to being trained with some predetermined proportions of classes. Existing strategies [9,11] for ACS do not account for the class proportions that a trained model needs to handle during deployment; they solely focus on the perceived difficulty of classes. One notable exception is a strategy that acquires training data precisely with those label proportions that are faced in the deployment stage; by design, this strategy requires the practitioner to know the deployment class proportions precisely in advance. However, what if we know the deployment class proportions not precisely, but with some degree of uncertainty? For instance, astro-particle physicists can estimate the ratio between their signal and their background class only roughly, as being approximately 1 : 10 3 or even 1 : 10 4 [2]. We are not aware of any ACS strategy that supports uncertain deployment class proportions out of the box.

Motivated by such uncertainties, we have recently proposed a theoretically justified certificate for ACS-trained models [4]. This certificate declares a range of deployment class proportions for which a given model is accurate (i.e. has an ACS-induced error smaller than some ε > 0) with a high probability (i.e. with probability at least 1 − δ). This declaration can help practitioners in assessing the practical value of an ACS-trained model. However, it has no immediate implication on how to acquire data-in terms of an ACS strategy-when the deployment class proportions are uncertain.

In the following, we therefore evolve the theoretical basis of our certificate towards a data acquisition strategy for ACS. This strategy uniquely combines the following qualities:

-our ACS strategy naturally supports uncertainty about the deployment class proportions, e.g. as expressed by a Beta prior for binary classification. -our strategy is theoretically justified by PAC learning bounds.

Our experiments suggest that our strategy, even under high amounts of uncertainty, exhibits a performance that is comparable to the performance of an optimal strategy with privileged access to the class proportions of the test set. Other strategies, which are oblivious to the deployment class proportions, fall behind by a significant margin.

We summarize the theoretic foundations of ACS in Sec. 2 before we detail our strategy in Sec. 3. The experiments in Sec. 4 lead to our conclusion in Sec. 5.

Theoretical Background

The term "domain", as proposed by domain adaptation [14,12], describes a probability density function over the data space X × Y. In ACS, we assume that the source domain S-where a machine learning model is trained-differs from the target domain T -where the model is deployed-only in terms of the class proportions p S = p T . Such deviations occur due to the freedom of ACS strategies to choose any p S for the acquisition of training data. We are interested in the impact of such deviations on the deployment performance, i.e. on the classification performance with respect to T .

Recently, a PAC learning perspective on this setting has provided us with Theorem 1 [4]. This result quantifies the difference in loss values L(h) between an ACS-generated training set D and the target domain T . Only if this difference is small, we can expect to learn a classifier h from D that is accurate also with respect to T , similar to standard PAC learning theory. The key insight of this theorem is that the relevant loss difference between D and T is continuously approaching the inter-domain gap ∆p•∆ while the training set size m increases. In ACS, this increase happens naturally while more and more data is actively being acquired, so that the error of any ACS-trained classifier is increasingly dominated by this gap. Here, ∆p = |p T − p S | denotes the difference between class proportions and ∆ = | Y =2 (h) − Y =1 (h)| denotes the difference between class-wise losses. The latter of these terms is constant across domains S and T . In turn, ∆p • ∆ is constant with respect to the random draw of the training set D and is therefore independent of ε, δ, and m; it reflects the interplay between the classifier h, the data distribution, and the loss function.

Theorem 1 (Identical mechanism bound; binary classification [4]). For any ε > 0, any h ∈ H, with probability at least 1 − δ, where δ = 4e −2mε 2 :

∆p • ∆ − ε ≤ |L T (h) − L D (h)| ≤ ∆p • ∆ + ε

The true difference ∆ from Theorem 1 is unknown, but we can estimate an upper bound ∆ * of this quantity from ACS-generated data. The details on this estimation are already presented in the scope of ACS model certification [4] and do not need to be repeated here. All we need to know to establish our ACS strategy is that ∆ * is the smallest upper bound of ∆ that holds with probability at least 1 − δ. The probabilistic nature of this upper bound stems from the fact that ∆ * is estimated from finite amounts of data.

A Strategy for Uncertain Class Proportions

The goal of our strategy is to decrease the inter-domain gap ∆p • ∆ from Theorem 1 as much as possible, as according to a prior distribution P of the deployment class proportions p T . This goal will allow any binary classification algorithm to learn accurate predictions for the target domain, as according to the prior beliefs of a domain expert.

Formally, we assume a prior P : [0, 1] → [0, 1] of the positive class prevalence p T ∈ [0, 1] to be given. We incorporate P by marginalizing the inter-domain gap over this prior, as according to Eq. 1. Since we do not know the true ∆ , we are using the estimated upper bound ∆ * instead. Consequently, the marginalization according to ∆ * is an upper bound, with probability 1−δ, of the marginalization according to the true ∆ .

ε * = 1 0 P(p T = p) • |p S − p| = ∆p • ∆ * d p(1)

In each ACS iteration, we are free to alter the class proportions p S of the ACS-generated training set to some degree, depending on how much data we acquire in each batch and on how much data we already have acquired. In fact, we can understand p S = m2 (m1+m2) as a function of the class-wise numbers of samples m 1 and m 2 . The upper bound ∆ * also lends itself for being interpreted as a function of sample sizes: the more data is acquired in both classes, the tighter will our estimation of this quantity be. Ultimately, we consider ε * to be a function of m 1 and m 2 , so that we can minimize ε * via an optimal choice of m 1 and m 2 in each data acquisition batch.

Minimizing the Marginalized Error

Our strategy decreases ε * in the direction of its steepest descent, i.e. it takes a simple gradient step with respect to the acquisition vector m = (m 1 , m 2 ). The gradient which defines the steepest descent is computed via the product rule:

∇ m ε * = ∇ m f • ∆ * + f • ∇ m ∆ * where f (m) = 1 0 P(p T = p) • |p S (m) − p| d p(2)

We will come back to the function f shortly. For now, we plug ∆ * and ∇ m ∆ * into the equation above. These functions are defined by

∆ * (m) = ˆ Y =2 (h) + ln δ 2 −2m 2 − ˆ Y =1 (h) + ln δ 1 −2m 1 , [∇ m ∆ * ] y = − ln δ y m y 3 2 • (2 √ 2 ln δ y ) −1 ,(3)

where the δ y are probabilities of violations of ∆ * that occur from either one of the class-wise losses Y =y (h) in ∆ . In fact, finding a suitable assignment of δ y values within a given probability budget δ = δ 1 + δ 2 − δ 1 δ 2 is the central difficulty in model certification; there, the sample size m is fixed, so that ∆ * can be optimized over this assignment [4]. Here, we keep the δ y fixed instead, to values that are obtained with a certificate from previous ACS acquisitions. This change allows us to optimize ∆ * over m to acquire new data and it guarantees that ∆ * remains an upper bound of the true ∆ also in the next batch, at least with probability 1 − δ. The class-wise estimates ˆ Y =y (h) in Eq. 3 are the average values of losses in the training data; they are also part of our certificate.

A Beta Prior for Binary Class Proportions

Now we turn to the function value and the gradient of the function f in Eq. 2.

Plugging a parametric prior P into this function can allow us to compute these terms efficiently, in closed forms. To this end, a Beta(α, β) prior is suitable for binary classification because the Beta distribution is a conjugate prior of the Bernoulli distribution, which in turn is a suitable model for the prevalence of binary class labels. As a matter of convenience, the parameters α > 0 and β > 0 can be chosen such that the resulting distribution has some predetermined mean and standard deviation; we believe that domain experts can often express their prior beliefs in terms of these properties. Plugging a Beta prior into the f function from Eq. 2 yields the following components, where I is the regularized incomplete Beta function:

f α,β (m) = 2p S (m) α (1 − p S (m)) β (α + β)B(α, β) + p S (m) − α α + β 2I pS (m) (α, β) − 1 ∇ m f α,β = 2I pS (m) (α, β) − 1 (m 1 + m 2 ) 2 • m 2 −m 1(4)

Plugging Eq. 3 and 4 into Eq. 2 provides us with a gradient that we can compute analytically from a certificate with a δ y assignment, from sample sizes m 1 and m 2 and from the prior parameters α and β. The negative gradient −∇ m ε * of the marginalized error ε * defines the class-wise numbers of samples that our strategy acquires in the next data acquisition batch.

With small data volumes or with highly imbalanced classes, our strategy is dominated by the ∆ * component; small classes need additional data until this upper bound holds with some desired probability 1−δ. Constrastingly, when the total data volume is large, our strategy is dominated by the f component; to this end, a Beta prior favors class proportions that are close to its mean α α+β . The turning point between these two behaviors is well-founded in the PAC learning theory that underlies the estimation of ∆ * .

Experiments

The first introduction of the ACS problem is already accompanied by the proposal of five heuristic ACS strategies [11]. In the following, we compare our own strategy from Sec. 3 to these five heuristics:

proportional: always sample according to p T , provided that these true proportions are already known at training time.

uniform: always sample all classes in the same amount. inverse: sample according to the inverse accuracy of a classifier that is trained on earlier batches; the underlying assumption is that weak class-wise performances can be counteracted with over-sampling. improvement: sample according to the class-wise improvement in accuracy that has occurred between the current iteration and the iteration before; this strategy assumes that stable performances, i.e. performances that did not change recently, will remain stable during future acquisitions. redistriction: sample according to the class-wise number of training examples for which the prediction has changed between the current iteration and the iteration before; the assumption here is that stability can be promoted by over-sampling classes with volatile decision boundaries.

Our theoretical analysis of the ACS problem [5,4] reveals that the proportional strategy is actually more than a heuristic; this strategy is indeed optimal in the limit of data acquisition. However, it requires precise knowledge of p T , which practitioners might not be able to provide. Contrastingly, all other strategies are entirely oblivious to the deployment proportions; they solely focus on different notions of class-wise difficulties.

This shortcoming is also shared by an ACS strategy that aggregates utility scores of pseudo-instances [9]. For now, we have excluded this approach from our comparison, due to this property. For future work, however, we expect that the method can overcome this limitation with a recent update of its utility function [8]. This update supports a prior of p T , which is in line with our idea of incorporating prior beliefs in ACS. Embedding the update in the original pseudo-instance strategy, however, might not be trivial.

Methodology

We have parameterized the Beta prior of our strategy with a predetermined mean and standard deviation, both set to the true value of p T . Accordingly, the mean of the prior is well aligned with the true class proportions of the deployment data; the uncertainty, however, is as large as possible.

In accordance to a reliable evaluation methodology [7], we present pairwise differences between ACS strategies in terms of their statistical significance. A comprehensive way of plotting such differences is through critical difference diagrams [6,1], which compare multiple strategies over multiple data sets in a statistically sound way. We employ accuracy as the underlying performance metric and we conduct multiple trials to obtain an average performance value for each combination of strategy and data set. These average performances are then summarized through critical difference diagrams.

We define the trials via five repetitions of a three-fold cross validation. From the imbalanced-learn1 package [10], we retrieve 13 data sets that have at least 150 minority class samples (to facilitate sampling) and at most 100 features (to facilitate learning). We ensure comparability between all strategies by employing the same classifier in all experiments, a logistic regression with default metaparameters. The data acquisition happens in up to 8 batches, each of which acquires 50 new training examples. However, not all strategies reach the last batch on all data sets; we stop each trial as soon as the strategy exhausts one of the classes. We opted for this early stopping criterion to focus on "realistic" acquisitions that happen due to free choices and not due to the fact that our experiment only simulates class-dependent data acquisition with finite pools of data. For the same reason, and due to weak performances on imbalanced data, we did not evaluate the uniform strategy here. Due to the early stopping, it becomes increasingly harder to detect significant differences; while the batches three and four can be evaluated on all data sets, only 9 data sets remain for batch eight. The implementation of our configurable experiments is available online2 .

Results and Discussion

Fig. 2 presents the critical difference diagrams, as according to our evaluation methodology. We see that our method, with access to an uncertain prior of p T , performs as well as the privileged strategy that knows p T precisely. Moreover, our method outperforms all existing strategies which are oblivious to p T . Fig. 3 traces this success back to the acquisition behavior that each strategy exhibits. Our own strategy quickly approaches the true proportions p T of classes, due to the perfect alignment between the mean of the prior and p T . For the particular case of a Beta prior, this behavior is a reason for concern: if the mean of this prior was not well aligned with p T , we might have acquired data in mistaken class proportions; only if the mean of the Beta prior is sufficiently accurate, we can expect the competitive behavior that Fig. 2 suggests. Future research down this lane, e.g. with other types of prior distributions, is needed. Fig. 3 further reveals two explanations for the poor performances of the existing strategies: first, all of these strategies exhibit a central tendency of staying close to the class proportions of the initial training set; second, each of these strategies prefers class proportions of an increasingly large variability. Both of these behaviors are due to the sole focus of these strategies on the perceived difficulties of classes, which can differ considerably between the data sets.

Conclusion and Outlook

In contrast to existing ACS strategies, which either assume precise knowledge about the deployment class proportions or no knowledge at all, we have advocated the incorporation of a prior distribution that expresses beliefs about the class proportions with any degree of (un)certainty. Our ACS strategy is wellfounded on PAC learning bounds which we have recently proposed for ACS [4]. Experiments suggest that our strategy performs as well as the fully certain case, which, however, is harder to specify than an uncertain prior.

ACS batch

Fig. 2. Critical difference diagrams evaluate our ACS strategy ( ) against existing ACS strategies [11], one of which has privileged access to the true class proportions pT ( ). The two plots present different values of pT . Each position on the vertical axes corresponds to one critical difference diagram for one batch in the ACS data acquisition loop. Horizontal positions correspond to the average ranks of strategies across multiple data sets, as according to the average accuracy in multiple trials; lower ranks are better. Horizontal connections between two or more strategies indicate that a Wilcoxon signed-rank test is not able to detect significant differences between these methods from the performances they exhibit. Future work on ACS should focus on strategies that support multi-class classification and regression. We identify the PAL-ACS framework [9] with a recent update of its utility function [8] as a promising candidate in this direction.