A Review on Quantification Learning <s> Optimization Algorithms for Quantification <s> This paper presents a Support Vector Method for optimizing multivariate nonlinear performance measures like the F 1 -score. Taking a multivariate prediction approach, we give an algorithm with which such multivariate SVMs can be trained in polynomial time for large classes of potentially non-linear performance measures, in particular ROCArea and all measures that can be computed from the contingency table. The conventional classification SVM arises as a special case of our method. <s> BIB001 </s> A Review on Quantification Learning <s> Optimization Algorithms for Quantification <s> We address the problem of quantification, a supervised learning task whose goal is, given a class, to estimate the relative frequency (or prevalence) of the class in a dataset of unlabeled items. Quantification has several applications in data and text mining, such as estimating the prevalence of positive reviews in a set of reviews of a given product or estimating the prevalence of a given support issue in a dataset of transcripts of phone calls to tech support. So far, quantification has been addressed by learning a general-purpose classifier, counting the unlabeled items that have been assigned the class, and tuning the obtained counts according to some heuristics. In this article, we depart from the tradition of using general-purpose classifiers and use instead a supervised learning model for structured prediction, capable of generating classifiers directly optimized for the (multivariate and nonlinear) function used for evaluating quantification accuracy. The experiments that we have run on 5,500 binary high-dimensional datasets (averaging more than 14,000 documents each) show that this method is more accurate, more stable, and more efficient than existing state-of-the-art quantification methods. <s> BIB002 </s> A Review on Quantification Learning <s> Optimization Algorithms for Quantification <s> The estimation of class prevalence, i.e., the fraction of the population that belongs to a certain class, is a very useful tool in data analytics and learning, and finds applications in many domains, such as sentiment analysis, epidemiology, etc. For example, in sentiment analysis, the objective is often not to estimate whether a specific text conveys positive or negative sentiment, but rather estimate the overall distribution of positive and negative sentiment during an event window. A popular way of performing the above task, often dubbed quantification, is to use supervised learning to train a prevalence estimator from labelled data. In this paper we propose the first online stochastic algorithms for directly optimizing (i) performance measures for quantification, and (ii) hybrid performance measures that seek to balance quantification and classification performance. We prove rigorous bounds for our algorithms which demonstrate that they exhibit optimal convergence. Our algorithms present a significant advancement in the theory of multivariate optimization. We also report extensive experiments on benchmark and real data sets which demonstrate that our methods significantly outperform existing optimization techniques used for the quantification problem. <s> BIB003 </s> A Review on Quantification Learning <s> Optimization Algorithms for Quantification <s> Classification is the task of predicting the class labels of objects based on the observation of their features. In contrast, quantification has been defined as the task of determining the prevalence of the positive class labels in a target dataset. The simplest approach to quantification is Classify&Count where a classifier is optimised for classification on a training set and applied to the target dataset for the prediction of positive class labels. The number of predicted positive labels is then used as an estimate of the positive class prevalence in the target dataset. Since the performance of Classify&Count for quantification is known to be inferior its results typically are subject to adjustments. However, some researchers recently have suggested that Classify&Count might actually work without adjustments if it is based on a classifier that was specifically trained for quantification. We discuss the theoretical foundation for this claim and explore its potential and limitations with a numerical example based on the binormal model with equal variances. <s> BIB004 </s> A Review on Quantification Learning <s> Optimization Algorithms for Quantification <s> Our hypothesis: ensembles are well suited for problems with distribution changes.If those changes are characterizable, ensembles can be designed to tackle them.Idea: to generate different samples based on the expected distribution changes.Case study: we present ensembles versions of two binary quantification algorithms.Ensembles outperform original counterpart algorithms using trivial aggregation rules. Display Omitted Ensemble methods are widely applied to supervised learning tasks. Based on a simple strategy they often achieve good performance, especially when the single models comprising the ensemble are diverse. Diversity can be introduced into the ensemble by creating different training samples for each model. In that case, each model is trained with a data distribution that may be different from the original training set distribution. Following that idea, this paper analyzes the hypothesis that ensembles can be especially appropriate in problems that: (i) suffer from distribution changes, (ii) it is possible to characterize those changes beforehand. The idea consists in generating different training samples based on the expected distribution changes, and to train one model with each of them. As a case study, we shall focus on binary quantification problems, introducing ensembles versions for two well-known quantification algorithms. Experimental results show that these ensemble adaptations outperform the original counterpart algorithms, even when trivial aggregation rules are used. <s> BIB005
The methods belonging to this group are based on optimization and were designed for binary quantification. However, they can be easily extended to multi-class quantification. Following one of the most formal approach for learning, the idea initially proposed by  is to select a target quantification performance measure and to train an optimization algorithm to build the optimal model according to the training data available and the selected performance measure. Three different methods have been proposed following this approach. The differences between them are due to (i) the performance measure selected and (ii) the optimization algorithm used for training. All of them use advanced learning machines, because it is not straightforward to design an algorithm able to optimize a quantification measure. The difficulty arises because a quantification error cannot be decomposed as a combination of individual errors. BIB002 propose to optimize the well-known KL Divergence (Equation (10)), using SV M per f BIB001 as the learning algorithm. SV M per f is able to optimize any nonlinear measure computed using the contingency table, like KL Divergence.  also use SV M per f but with a different target measure. The authors argue that KL divergence, or any other pure quantification measure, does not take into account the accuracy of the underlying classifier, and thus the resulting quantifier could be built over a poor classifier. The key issue is that quantification measures produce several optimum points within the hypothesis search space (any that fulfills FP = F N ). However, some of these hypotheses correspond to better (or more reliable) classifiers. To select a model that is at the same time a good quantifier and a good classifier, the authors introduce a family of measures, called the Q-measure, because it is inspired by the Fmeasure family. Q-measure combines a quantification metric (Q per f ) with a classification metric (C per f ): To be appropriately combined, C per f and Q per f must be bounded, for instance, between 0 and 1. The β parameter allows to tradeoff between them. The selection of the two metrics mainly depends on the problem at hand. For instance, the authors select NAS (17) as Q per f and recall as C per f in their experiments. Notice that combining quantification and classification measure is also employed in quantification trees, see Section 7.1. SV M per f suffers from two drawbacks: (i) the structural SVM surrogate is not necessarily a tight surrogate for all performance measures, which can lead to a suboptimal model, and (ii) it scales poorly when the amount of training data increases. To alleviate these issues, BIB003 devised two online stochastic optimization algorithms that are able to optimize quantification performance measures. Regarding this, two families of multivariate performance measures are considered: nested concave and pseudo-concave measures. For the first group, the authors analyze three nested concave functions: (1) −KLD, (2) BAKLD = C · BA + (1 − C) · −KLD, in which C is a constant and BA stands for Balanced Accuracy, BA = 1 2 (tpr + tnr ), being tnr the true negative rate, and (3) Q-measure (44), using BA as C per f and NSS (18) as Q per f . In the group of pseudoconcave performance measures, two metrics are considered: (1) CQReward = BA/(2 − NSS) and (2) BKReward = BA/(1 + KLD). Their methods offer much faster and accurate quantification performance on a group of datasets. Recently, BIB004 investigates whether these approaches actually work without applying the AC correction. After an interesting theoretical discussion, the study concludes that quantification without adjustments a priori may work if proper calibration on the training dataset is ensured and the drift in class distribution is small. BIB005 introduce the first ensemble algorithm designed for binary quantification. The main idea of this method is that we can learn an ensemble with a proper diversity that takes into account the characteristics of our quantification task. This kind of ensemble will be better adapted to deal with the changes in data distribution of the quantification problem because its design depends on the expected variation of P (y). The algorithm has three main processes: