{'fraction_non_alphanumeric': 0.04206333227875406, 'fraction_numerical': 0.018522246829071873, 'mean_word_length': 4.515903862933291, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing Text Quantifiers for Multivariate Loss Functions

We address the problem of \emph{quantification}, a supervised learning task whose goal is, given a class, to estimate the relative frequency (or \emph{prevalence}) of the class in a dataset of unlabelled 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 unlabelled items which have been assigned the class, and tuning the obtained counts according to some heuristics. In this paper we depart from the tradition of using general-purpose classifiers, and use instead a supervised learning model for \emph{structured prediction}, capable of generating classifiers directly optimized for the (multivariate and non-linear) function used for evaluating quantification accuracy. The experiments that we have run on 5500 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.


INTRODUCTION
In recent years it has been pointed out that, in a number of applications involving classification, the final goal is not determining which class (or classes) individual unlabelled data items belong to, but determining the prevalence (or "relative frequency") of each class in the unlabelled data. The latter task is known as quantification [Forman 2005;2006a;].
Although what we are going to discuss here applies to any type of data, we are mostly interested in text quantification, i.e., quantification when the data items are textual documents. To see the importance of text quantification, let us examine the task of classifying textual answers returned to open-ended questions in questionnaires [Esuli and Sebastiani 2010a;Gamon 2004;Giorgetti and Sebastiani 2003], and let us discuss two important such scenarios.
In the first scenario, a telecommunications company asks its current customers the question "How satisfied are you with our mobile phone services?", and wants to classify the resulting textual answers according to whether they belong to the class May-DefectToCompetition. The company is likely interested in accurately classifying each individual customer, since it may want to call each customer that is assigned the class and offer her improved conditions.
In the second scenario, a market research agency asks respondents the question "What do you think of the recent ad campaign for product X?", and wants to classify the resulting textual answers according to whether they belong to the class LovedThe-Campaign. Here, the agency is likely not interested in whether a specific individual belongs to the class LovedTheCampaign, but is likely interested in knowing how many respondents belong to it, i.e., in knowing the prevalence of the class.
In sum, while in the first scenario classification is the goal, in the second scenario the real goal is quantification, i.e., evaluating the results of classification at the aggregate level rather than at the individual level. Other scenarios in which quantification is the goal may be, e.g., predicting election results by estimating the prevalence of blog posts (or tweets) supporting a given candidate or party [Hopkins and King 2010], or planning the amount of human resources to allocate to different types of issues in a customer support center by estimating the prevalence of customer calls related to a given issue [Forman 2005], or supporting epidemiological research by estimating the prevalence of medical reports in which a specific pathology is diagnosed [Baccianella et al. 2013].
The obvious method for dealing with the latter type of scenarios is aggregative quantification, i.e., classifying each unlabelled document and estimating class prevalence by counting the documents that have been attributed the class. However, there are two reasons why this strategy is suboptimal. The first reason is that a good classifier may not be a good quantifier, and vice versa. To see this, one only needs to look at the definition of F 1 , the standard evaluation function for binary classification, defined as where T P , F P and F N indicate the numbers of true positives, false positives, and false negatives, respectively. According to F 1 , a binary classifierΦ 1 for which F P = 20 and F N = 20 is worse than a classifierΦ 2 for which, on the same test set, F P = 0 and F N = 10. However,Φ 1 is intuitively a better binary quantifier thanΦ 2 ; indeed,Φ 1 is a perfect quantifier, since F P and F N are equal and thus compensate each other, so that the distribution of the test items across the class and its complement is estimated perfectly.
A second reason is that standard supervised learning algorithms are based on the assumption that the training set is drawn from the same distribution as the unlabelled data the classifier is supposed to classify. But in real-world settings this assumption is often violated, a phenomenon usually referred to as concept drift [Sammut and Harries 2011]. For instance, in a backlog of newswire stories from year 2001, the prevalence of class Terrorism in August data will likely not be the same as in September data; training on August data and testing on September data might well yield low quantification accuracy. Violations of this assumption may occur "for reasons ranging from the bias introduced by experimental design, to the irreproducibility of the testing conditions at training time" [Quiñonero-Candela et al. 2009]. Concept drift usually comes in one of three forms [Kelly et al. 1999]: (a) the class priors p(c i ) may change, i.e., the one in the test set may significantly differ from the one in the training set; (b) the classconditional distributions p(x|c i ) may change; (c) the posterior distribution p(c i |x) may change. It is the first of these three cases that poses a problem for quantification.
The previous arguments indicate that text quantification should not be considered a mere byproduct of text classification, and should be studied as a task of its own. To date, proposed methods explicitly addressed to quantification (see e.g., [Bella et al. 2010;Forman 2005;2006a;Hopkins and King 2010;Xue and Weiss 2009]) employ general-purpose supervised learning methods, i.e., address quantification by elaborating on the results returned by a general-purpose standard classifier. In this paper we take a sharply different, structured prediction approach, based upon the use of classifiers explicitly optimized for the non-linear, multivariate evaluation function that we will use for assessing quantification accuracy. This idea was first proposed, but not implemented, in [Esuli and Sebastiani 2010b].
The rest of the paper is organized as follows. In Section 2, after setting the stage we describe the evaluation function we will adopt ( §2.1) and sketch a number of quantification methods previously proposed in the literature ( §2.2). In Section 3 we introduce our novel method based on explicitly minimizing, via a structured prediction model, the evaluation measure we have chosen. Section 4 presents experiments in which we test the method we propose on two large batches of binary, high-dimensional, publicly available datasets (the two batches consist of 5148 and 352 datasets, respectively), using all the methods introduced in §2.2 as baselines. Section 5 discusses related work, while Section 6 concludes.

PRELIMINARIES
In this paper we will focus on quantification at the binary level. That is, given a domain of documents D and a class c, we assume the existence of an unknown target function (or ground truth) Φ : D → {−1, +1} that specifies which members of D belong to c; as usual, +1 and −1 represent membership and non-membership in c, respectively. The approaches we will focus on are based on aggregative quantification, i.e., they rely on the generation of a classifierΦ : D → {−1, +1} via supervised learning from a training set T r. We will indicated with T e the test set on which quantification effectiveness is going to be tested.
We define the prevalence (or relative frequency) λ T e (c) of class c in a set of documents T e as the fraction of members of T e that belong to c, i.e., as Given a set T e of unlabelled documents and a class c, quantification is defined as the task of estimating λ T e (c), i.e., of computing an estimateλ T e (c) such that λ T e (c) andλ T e (c) are as close as possible 1 . What "as close as possible" exactly means will be formalized by an appropriate evaluation measure (see §2.1).
The reasons why we focus on binary quantification are two-fold: -Many quantification problems are binary in nature. For instance, estimating the prevalence of positive and negative reviews in a dataset of reviews of a given product is such a task. Another such task is estimating from blog posts the prevalence of support for either of two candidates in the second round of a two-round ("run-off ") election. -A multi-class multi-label problem (also known as an n-of-m problem, i.e., a problem where zero, one, or several among m classes can be attributed to the same document) can be reduced to m independent binary problems of type (c j vs. c j ), where C = {c 1 , ..., c j , ..., c m } is the set of classes and where c j denotes the complement of c j . Binary quantification methods can thus also be applied to solving quantification in multi-class multi-label contexts.
We instead leave the discussion of quantification in single-label multi-class (i.e., 1-ofm) contexts to future work.

Evaluation measures for quantification
Different measures have been used in the literature for measuring binary quantification accuracy.
The simplest such measure is bias (B), defined as B(λ T e ,λ T e ) =λ T e (c) − λ T e (c) and used in [Forman 2005;2006a;Tang et al. 2010]; positive bias indicates a tendency to overestimate the prevalence of c, while negative bias indicates a tendency to underestimate it.
Absolute Error (AE -also used in [Esuli and Sebastiani 2010b], where it is called percentage discrepancy, and in [Barranquero et al. 2013;Bella et al. 2010;Forman 2005;2006a;González-Castro et al. 2013;Sánchez et al. 2008;Tang et al. 2010]), defined as AE(λ T e ,λ T e ) = |λ T e (c) − λ T e (c)|, is an alternative, equally simplistic measure that accounts for the fact that positive and negative bias are (in the absence of specific application-dependent constraints) equally undesirable.
Relative absolute error (RAE), defined as is a refinement of AE meant to account for the fact that the same value of absolute error is a more serious mistake when the true class prevalence is small. For instance, predictingλ T e (c) = 0.10 when λ T e (c) = 0.01 and predictingλ T e (c) = 0.50 when λ T e (c) = 0.41 are equivalent errors according to B and AE, but the former is intuitively a more serious error than the latter. The most convincing among the evaluation measures proposed so far is certainly Forman's [2005], who uses normalized cross-entropy, better known as Kullback-Leibler Divergence (KLD -see e.g., [Cover and Thomas 1991]). KLD, defined as and also used in [Esuli and Sebastiani 2010b;Forman 2006a;Tang et al. 2010], is a measure of the error made in estimating a true distribution λ T e over a set C of classes by means of a distributionλ T e ; this means that KLD is in principle suitable for evaluating quantification, since quantifying exactly means predicting how the test items are distributed across the classes. KLD ranges between 0 (perfect coincidence of λ T e andλ T e ) and +∞ (total divergence of λ T e andλ T e ). In the binary case in which C = {c, c}, KLD becomes Continuity arguments indicate that we should consider 0 log 0 q = 0 and p log p 0 = +∞ (see [Cover and Thomas 1991, p. 18]). Note that, as from Equation 4, KLD is undefined when the predicted distributionλ T e is zero for at least one class (a problem that also affects RAE). As a result, we smooth the fractions λ T e (c)/λ T e (c) and λ T e (c)/λ T e (c) in Equation 4 by adding a small quantity to both the numerator and the denominator. The smoothed KLD function is always defined and still returns a value of zero when λ T e andλ T e coincide.
KLD offers several advantages with respect to RAE (and, a fortiori, to B and AE). One advantage is that, as evident from Equation 5, it is symmetric with respect to the complement of a class, i.e., switching the role of c and c does not change the result. This means that, e.g., predictingλ T e (c) = 0.10 when λ T e (c) = 0.11 and predictingλ T e (c) = 0.90 when λ T e (c) = 0.89, are equivalent errors (which seems intuitive), while RAE considers the former a much more serious error than the latter. This is especially useful in binary quantification tasks in which it is not clear which of the two classes should play the role of the positive class c, as in e.g., Employed vs. Unemployed. A second advantage is that KLD is not defined only on the binary (and multi-label multi-class) case, but is also defined on the single-label multi-class case; this allows evaluating different types of quantification tasks with the same measure. Last but not least, one benefit of using KLD is that it is a very well-known measure, having been the subject of intense study within information theory [Csiszár and Shields 2004] and, although from a more applicative angle, within the language modelling approach to information retrieval [Zhai 2008].

Existing quantification methods
A number of methods have been proposed in the (still brief) literature on quantification; below we list the main ones, which we will use as baselines in the experiments discussed in Section 4.
Classify and Count (CC). An obvious method for quantification consists of generating a classifier from T r, classifying the documents in T e, and estimating λ T e by simply counting the fraction of documents in T e that are predicted positive, i.e., Forman [2008] calls this the classify and count (CC) method.

Probabilistic Classify and Count (PCC).
A variant of the above consists in generating a classifier from T r, classifying the documents in T e, and computing λ T e as the expected fraction of documents predicted positive, i.e., where p(c|d j ) is the probability of membership in c of test document d j returned by the classifier. If the classifier only returns confidence scores that are not probabilities (as is the case, e.g., when AdaBoost.MH is the learner [Schapire and Singer 2000]), the confidence scores must be converted into probabilities, e.g., by applying a logistic function. The PCC method is dismissed as unsuitable in [Forman 2005;, but is shown to perform better than CC in [Bella et al. 2010] (where it is called "Probability Average") and in [Tang et al. 2010]. Adjusted Classify and Count (ACC). Forman [2005; uses a further method which he calls "Adjusted Count", and which we will call Adjusted Classify and Count (ACC) so as to make its relation with CC more explicit. The underlying idea is that CC would be optimal, were it not for the fact that the classifier may generate different numbers of false positives and false negatives, and that this difference would lead to imperfect quantification. If we knew the "true positive rate" (tpr = T P T P +F N , a.k.a. recall) and "false positive rate" (f pr = F P F P +T N , a.k.a. fallout) that the classifier has obtained on T e, it is easy to check that perfect quantification would be obtained by adjustingλ CC T e (c) as follows:λ Since we cannot know the true values of tpr T e (c) and f pr T e (c), the ACC method consists of estimating them on T r via k-fold cross-validation and using the resulting estimates in Equation 8. However, one problem with ACC is that it is not guaranteed to return a value in [0,1], due to the fact that the estimates of tpr T e (c) and f pr T e (c) may be imperfect. This lead Forman [2008] to "clip" the results of the estimation (i.e., equate to 1 every value higher than 1 and to 0 every value lower than 0) in order for the final results to be in [0,1].
Probabilistic Adjusted Classify and Count (PACC). The PACC method (proposed in [Bella et al. 2010], where it is called "Scaled Probability Average") is a probabilistic variant of ACC, i.e., it stands to ACC like PCC stands to CC. Its underlying idea is to replace, in Equation 8,λ CC T e (c), tpr T e (c) and f pr T e (c) with their expected values, with probability of membership in c replacing binary predictions. Equation 8 is thus transformed intoλ where E[tpr T e (c)] and E[f pr T e (c)] (expected tpr T e (c) and expected f pr T e (c), respectively) are defined as and T e c (resp., T e c ) indicates the set of documents in T e that belong (resp., do not belong) to class c. Again, since we cannot know the true E[tpr T e (c)] and E[f pr T e (c)] (given that we do not know T e c and T e c ), we estimate them on T r via k-fold crossvalidation and use the resulting estimates in Equation 9. Threshold@0.50 (T50), Method X (X), and Method Max (MAX). Forman [2008] points out that the ACC method is very sensitive to the decision threshold of the classifier, which may yield unreliable values of λ ACC T e (c) (or lead to λ ACC T e (c) being undefined when tpr T e = f pr T e ). In order to reduce this sensitivity, [Forman 2008] recommends to heuristically set the decision threshold in such a way that tpr T r (as obtained via k-fold cross-validation) is equal to .50 before computing Equation 8. This method is dubbed Threshold@0.50 (T50). Alternative heuristics that [Forman 2008] discusses are to set the decision threshold in such a way that f pr T r = 1 − tpr T r (this is dubbed Method X) or such that (tpr T r − f pr T r ) is maximized (this is dubbed Method Max).
Median Sweep (MS). Alternatively, [Forman 2008] recommends to compute λ ACC T e (c) for every decision threshold that gives rise (in k-fold cross-validation) to different tpr T r or f pr T r values, and take the median of all the resulting estimates of λ ACC T e (c). This method is dubbed Median Sweep (MS). Mixture Model (MM). The MM method (proposed in [Forman 2005]) consists of assuming that the distribution D T e of the scores that the classifier assigns to the test examples is a mixture where D T e c and D T e c are the distributions of the scores that the classifier assigns to the positive and the negative test examples, respectively, and where λ T e (c) and λ T e (c) are the parameters of this mixture. The MM method consists of estimating D T e c and D T e c via k-fold cross-validation, and picking as value of λ T e (c) the one that generates the best fit between the observed D T e and the mixture. Two variants of this method, called the Kolmogorov-Smirnov Mixture Model (MM(KS)) and the PP-Area Mixture Model (MM(PP)), are actually defined in [Forman 2005], which differ in terms of how the goodness of fit between the left-and the right-hand side of Equation 12 is estimated. See [Forman 2005] for more details.

OPTIMIZING QUANTIFICATION ACCURACY
A problem with the methods discussed in §2.2 is that most of them are fairly heuristic in nature. For instance, the fact that methods such as ACC (and all the others based on it, such as T50, MS, X, and MAX) require "clipping" is scarcely reassuring. More in general, methods such as T50 or MS have hardly any theoretical foundation, and choosing them over CC only rests on our knowledge that they have performed better in previously reported experiments.
A further problem is that some of these methods rest on assumptions that seem problematic. For instance, one problem with the MM method is that it seems to implicitly rely on the hypothesis that estimating D T e c and D T e c via k-fold cross-validation on T r can be done reliably. However, since the very motivation of doing quantification is that the training set and the test set may have quite different characteristics, this hypothesis seems adventurous. A similar argument casts some doubt on ACC: how reliable are the estimates of tpr T e and f pr T e that can be generated via k-fold crossvalidation on T r, given the different characteristics that training set and test set may have in the application contexts where quantification is required? 2 In sum, the very same arguments that are used to deem the CC method unsuitable for quantification seem to undermine the previously mentioned attempts at improving on CC.
In this paper we propose a new, theoretically well-founded quantification method that radically differs from the ones discussed in §2.2. Note that all of the methods discussed in §2.2 employ general-purpose supervised learning methods, i.e., address quantification by post-processing the results returned by a standard classifier (where the decision threshold has possibly been tuned according to some heuristics). In particular, all the supervised learning methods adopted in the literature on quantification optimize Hamming distance or variants thereof, and not a quantification-specific evaluation function. When the dataset is imbalanced (typically: when the positives are by far outnumbered by the negatives), as is frequently the case in text classification, this is suboptimal, since a supervised learning method that minimizes Hamming distance will generate classifiers with a tendency to make negative predictions. This means that F N will be much higher than F P , to the detriment of quantification accuracy 3 .
We take a sharply different approach, based upon the use of classifiers explicitly optimized for the evaluation function that we will use for assessing quantification accuracy. Given such a classifier, we will simply use a "classify and count" approach, with no heuristic threshold tuning (à la T50 / X / MAX) and no a posteriori adjustment (à la ACC).
The idea of using learning algorithms capable of directly optimizing the measure (a.k.a. "loss") used for evaluating effectiveness is well-established in supervised learning. However, in our case following this route is non-trivial, because the evaluation measure that we want to use (KLD) is non-linear, i.e., is such that the error on the test set may not be formulated as a linear combination of the error incurred by each test example. An evaluation measure for quantification is inherently non-linear, because how the error on an individual test item impacts on the overall quantification error depends on how the other test items have been classified. For instance, if in the other test items there are more false positives than false negatives, an additional false negative is actually beneficial to overall quantification error, because of the mutual compensation effect between F P and F N mentioned in Section 1. As a result, a measure of quantification accuracy is inherently non-linear, and should thus be multivariate, i.e., take in consideration all test items at once.
As discussed in [Joachims 2005], the assumption that the error on the test set may be formulated as a linear combination of the error incurred by each test example (as indeed happens for many common error measures -e.g., Hamming distance) underlies most existing discriminative learners, which are thus suboptimal for tackling quantification. In order to sidestep this problem, we adopt the SVM for Multivariate Performance Measures (SVM perf ) learning algorithm proposed by Joachims [2005] 4 . SVM perf is a learning algorithm of the Support Vector Machine family that can generate classifiers optimized for any non-linear, multivariate loss function that can be computed from a contingency table (as KLD is).
SVM perf is a specialization to the problem of binary classification of the structural SVM (SV M struct ) learning algorithm [Joachims et al. 2009a;Joachims et al. 2009b;Tsochantaridis et al. 2004] for "structured prediction", i.e., an algorithm designed for predicting multivariate, structured objects (e.g., trees, sequences, sets). SVM perf is fundamentally different from conventional algorithms for learning classifiers: while these latter learn univariate classifiers (i.e., functions of typeΦ : D → {−1, +1} that classify individual instances one at a time), SVM perf learns multivariate classifiers (i.e., functions of typeΦ : D |S| → {−1, +1} |S| that classify entire sets S of instances in one shot). By doing so, SVM perf can optimize properties of entire sets of instances, properties (such as KLD) that cannot be expressed as linear functions of the properties of the individual instances.
As discussed in [Joachims et al. 2009b], SV M struct can be adapted to a specific task by defining four components: (1) A joint feature map Ψ(x, y). This function computes a vector of features (describing the match between the input vectors in x and the relative outputs, true or predicted, in y) from all the input-output pairs at the same time. In this way the number of features, and thus the number of parameters of the model, can be kept constant regardless of the size of the sample set. The Ψ function allows to generalise not only on inputs (x) but also on outputs (y), thus allowing to produce predictions not seen in the training data.
In SVM perf Ψ is defined 5 as (2) A loss function ∆(y,ŷ). SVM perf works with loss functions ∆(T P, F P, F N, T N ) in which the four values are those from the contingency table resulting from comparing the true labels y with the predicted labelsŷ. In our work we take the loss 4 In [Joachims 2005] SVM perf is actually called SV M ∆ multi , but the author has released its implementation under the name SVM perf . We will use this latter name because it uniquely identifies the algorithm on the Web, while searching for "SVM multi" often returns the SV M multiclass package, which addresses a different problem. 5 For this formulation of Ψ, and when error rate is the chosen loss function, Joachims [2005] shows that SVM perf coincides with the traditional univariate SVM model (called SVMorg in [Joachims 2005]). function to be KLD, i.e., 6 where λ(c) = T P + F N T P + F P + F N + T N andλ T e (c) = T P + F P T P + F P + F N + T N (3) An algorithm for the efficient computation of a hypothesiŝ where w is a vector of parameters. In SVM perf this simply corresponds to comput-ingΦ (4) An algorithm for the efficient computation of the loss-augmented hypothesiŝ which in SVM perf is computed via an algorithm [Joachims 2005, Algorithm 2] with O(n 2 ) worst-case complexity.
We have used the implementation of SVM perf made available by Joachims 7 , which we have extended by implementing the module that takes care of the ∆ KLD loss function.
In the rest of the paper our method will be dubbed SVM(KLD).

EXPERIMENTS
We now present the results of experiments aimed at assessing whether the approach we have proposed in Section 3 delivers better quantification accuracy than state-ofthe-art quantification methods. In order to do this, we have run all our experiments by using as baselines for our SVM(KLD) method all the methods described in §2.2.
For the CC, ACC, T50, X, MAX, MS, MM(KS), MM(PP) methods we have used the original implementation that we have obtained from the author (this guarantees that the baselines perform at their full potential). We have instead implemented PCC and PACC ourselves. At the heart of the implementation of all the baselines is a standard linear SVM with the parameters set at their default values; where quantities (such as e.g., f pr T e and tpr T e -see Equation 8) had to be estimated from the training set, we have used 50-fold cross-validation, as done and recommended in [Forman 2008].
In order to guarantee a fair comparison with the baselines we have used the default values for the parameters also for SVM perf , which lies at the basis of our SVM(KLD) method 8 . 6 In Equation 14 KLD is written as a function of T P , F P , F N , T N for the simple fact that in [Joachims 2005] (where SVM perf was originally described) the loss function ∆ is specified as a function of the four cells of the contingency table. However, it should be clear that λ(c) does not depend on the predicted labels: even if in Equation 14 we have written it out as λ(c) = T P +F N T P +F P +F N +T N , this latter is equivalent to writing λ(c) = GP GP +GN , where GP (the "gold positives") is T P + F N and GN (the "gold negatives") is F P + T N . Seen under this light, there is no trace of predicted labels in λ(c) = GP GP +GN , and λ(c) is just a function of the gold standard and not of the prediction. Analogously, it should be clear thatλ(c) is just a function of the prediction and not of the gold standard. 7 SVM perf is available from http://www.cs.cornell.edu/People/tj/svm\%5Flight/svm perf.html. Our module that extends it to deal with KLD is available at http://hlt.isti.cnr.it/quantification/. 8 An additional reason why we have left the parameters at their default values is that, in a context in which the characteristics of T r and T e may substantially differ, it is not clear that the parameter values which are found optimal on T r via k-fold cross-validation will also prove optimal (or at least will perform reasonably) on T e.
In order to generate the vectorial representations for our documents, the classic "bag-of-words" approach has been adopted. In particular, punctuation has been removed, all letters have been converted to lowercase, numbers have been removed, stop words have been removed using the stop list provided in [Lewis 1992, pages 117-118], and stemming has been performed by means of the version of Porter's stemmer available from http://snowball.tartarus.org/. All the remaining stemmed words ("terms") that occur at least once in T r have thus been used as features of our vectorial representations of documents; no feature selection has been performed. Feature weights have been obtained via the "ltc" variant [Salton and Buckley 1988] of the well-known tf idf class of weighting functions, i.e., where d i is a document, # T r (t k ) denotes the number of documents in T r in which feature t k occurs at least once and where #(t k , d i ) denotes the number of times t k occurs in d i . Weights obtained by Equation 18 are normalized through cosine normalization, i.e., where T denotes the total number of features. Following [Forman 2008], we set the constant for smoothing KLD to the value = 1 2 |T e|.

Datasets
The datasets we use for our experiments have been extracted from two important text classification test collections, REUTERS CORPUS VOLUME 1 version 2 (RCV1-V2) and OHSUMED-S. RCV1-V2 is a standard, publicly available benchmark for text classification consisting of 804,414 news stories produced by Reuters from 20 Aug 1996 to 19 Aug 1997 9 . RCV1-V2 ranks as one of the largest corpora currently used in text classification research and, as pointed out in [Forman 2006b], suffers from extensive "drift", i.e., from substantial variability between the training set and the test set, which makes it a challenging dataset for quantification. In our experiments we have used the 12,807 news stories of the 1st week (20 to 26 Aug 1996) for training, and the 791,607 news stories of the other 52 weeks for testing 10 . We have further partitioned these latter into 52 test sets each consisting of one week's worth of data 11 . RCV1-V2 is multi-label, i.e., a document may belong to several classes at the same time. Of the 103 classes of which its "Topic" hierarchy consists, in our experiments we have restricted our attention to the 99 classes with at least one positive training example. Consistently with the evaluation presented in [Lewis et al. 2004], also classes placed at internal nodes in the hierarchically organized classification scheme are considered in the evaluation; as positive examples of these classes we use the union of the positive examples of their subordinate nodes, plus their "own" positive examples.
The OHSUMED-S dataset  is a subset of the wellknown OHSUMED test collection [Hersh et al. 1994]. OHSUMED-S consists of a set of 15,643 MEDLINE records spanning the years from 1987 to 1991, where each record is classified under one or more of the 97 MeSH index terms that belong to the Heart Disease (HD) subtree of the well-known MeSH tree of index terms 12 . Each entry consists of summary information relative to a paper published on one of 270 medical journals; the available fields are title, abstract, author, source, publication type, and MeSH index terms. As the training set we have used, consistently with , the 2,510 documents belonging to year 1987; 9 MeSH index terms out of the 97 in the HD subtree are never assigned to any training document, so the number of classes we actually use is 88. We partition the four remaining years' worth of data into four bins (1988,1989,1990,1991), each containing the documents generated within the corresponding calendar year. The reason why we do not use the entire OHSUMED dataset is that roughly 93% of OHSUMED entries have no class assigned from the HD subtree, which means that the classes in the HD subtree have very low prevalence (λ T r = 0.003 on average); we thus prefer to use OHSUMED-S, which presents a wider range of prevalence values.
This experimental setting thus generates 52 × 99 = 5148 binary quantification test sets for RCV1-V2 (containing an average of 15,223 documents each), and 4 × 88 = 352 test sets for OHSUMED-S (containing an average of 3,283 documents each). This large number of test sets will give us an opportunity to study quantification across different dimensions (e.g., across classes characterized by different prevalence, across classes characterized by different amounts of drift, across time) 13 . More detailed figures about our datasets are given in Table I. Note that both RCV1-V2 and OHSUMED-S classes are characterized by severe imbalance, as can be noticed by the two "Avg prevalence of the positive class" rows of Table I, where both values are very far away from the value of 0.5, which represents perfect balance. On a side note, it is well-known that the "bag-of-words" extraction process outlined a few paragraphs above gives rise to very high-dimensional (albeit sparse) vectors; our case is no exception, and the dimensionality of our vectors is 53,204 (RCV1-V2) and 11,286 (OHSUMED-S), respectively.
Note that the experimental protocol we adopt is different from the one adopted by Forman. In [Forman 2005;2006a; he proposes a protocol in which, given a training set T r and a test set T e, several controlled experiments are run by artificially altering class prevalences (i.e., by randomly removing predefined percentages of the positives or of the negatives) either on T r or on T e. This protocol is meant to test the robustness of the methods with respect to different "distribution drifts" (i.e., differences between λ T r (c) and λ T e (c) of different magnitude) and different class prevalence values. We prefer to opt for a different protocol, one in which "natural" training and test sets are used, without artificial alterations. The reason is that artificial alterations may generate class prevalence values and/or distribution drifts that are simply not realistic (e.g., a situation in which λ T r (c) = .40 and λ T e (c) = .01); conversely, focusing on naturally occurring datasets forces us to come to terms with realistic levels of class prevalence and/or distribution drift. We will thus adopt the latter protocol in all the 12 https://www.nlm.nih.gov/mesh/ 13 In order to guarantee perfect reproducibility of our results, we make available at http://hlt.isti.cnr.it/ quantification/ the feature vectors of the RCV1-V2 and OHSUMED-S documents as extracted from our preprocessing module, and already split respectively into the 53 and 5 sets described above.

Testing quantification accuracy
We have run our experiments by learning quantifiers for each class c on the respective training set and testing the quantifiers separately on each of the test sets, using KLD as the evaluation measure. We have done this for all the 99 classes × 52 weeks in RCV1-V2 and for all the 88 classes × 4 years in OHSUMED-S, and for all the 10 baseline methods discussed in §2.2 plus our SVM(KLD) method.
4.2.1. Analysing the results along the class dimension. We first discuss the results according to the class dimension, i.e., by averaging the results for each RCV1-V2 class across the 52 test weeks and for each OHSUMED-S class across the 4 years 14 . Since this would leave no less than 99 RCV1-V2 classes to discuss, we further average the results across all the RCV1-V2 classes characterized by a training class prevalence λ T r (c) that falls into a certain interval (same for OHSUMED-S and its 88 classes). This allows us to separately check the behaviour of our quantification methods on groups of classes that are homogeneous by level of imbalance. We have also run statistical significance tests in order to check whether the improvement obtained by the best performing method over the 2nd best performer on the group is statistically significant 15 . The results are reported in Table II, where four levels of imbalance have been singled out: very low prevalence (VLP, which accounts for all the classes c such that λ T r (c) < 0.01; there are 48 RCV1-V2 and 51 OHSUMED-S such classes), low prevalence (LP 14 Wherever in this paper we speak of averaging accuracy results across different test sets, what we mean is actually macroaveraging, i.e., taking the accuracy results on the individual test sets and computing their arithmetic mean. This is sharply different from microaveraging, i.e., merging the test sets and computing a single accuracy figure on the merged set. Quite obviously, in a quantification setting microaveraging does not make any sense at all, since false positives from one set and false negatives from another set would compensate each other, thus generating misleadingly high accuracy values. 15 All the statistical significance tests discussed in this paper are based on a two-tailed paired t-test and the use of a 0.001 significance level. Table II. Accuracy of SVM(KLD) and of 10 baseline methods as measured in terms of KLD on the 99 classes of RCV1-V2 (top) and on the 88 classes of OHSUMED-S (bottom) grouped by class prevalence in T r (Columns 2 to 5); lower values are better; Column 6 indicates average accuracy across all the classes. The best result in each column is indicated with boldface only when there is a statistically significant difference with respect to each of the other tested methods (p < 0.001, two-tailed paired t-test on KLD value across the test sets in the group). The methods are ranked in terms of the value indicated in the "All" column. -0.01 ≤ λ T r (c) < 0.05; 34 RCV1-V2 and 28 OHSUMED-S classes), high prevalence (HP -0.05 ≤ λ T r (c) < 0.10; 10 RCV1-V2 and 4 OHSUMED-S classes), and very high prevalence (VHP -0.10 ≤ λ T r (c); 7 RCV1-V2 and 5 OHSUMED-S classes). The first observation that can be made by looking at the RCV1-V2 results in this table is that, when evaluated across all our 5148 test sets (Column 6), SVM(KLD) outperforms all the other baseline methods in a statistically significant way, scoring a KLD value of 1.32E-03 against the 1.74E-03 value (a -24.2% error reduction) obtained by the best-performing baseline (the PACC method). This is largely a result of a much better balance between false positives and false negatives obtained by the base classifiers: while (as already observed in Footnote 3) the average F P/F N ratio across the 5148 test sets is 0.109 for CC, it is 0.684 for SVM(KLD) (and it is 1 for the perfect quantifier). The OHSUMED-S results essentially confirm the insights obtained from the RCV1-V2 results, with SVM(KLD) again the best of the 11 methods and PACC again the 2nd best; the difference between them is now even higher, with an error reduction of -56.8%.

VLP
A second observation that the RCV1-V2 results allow is to make is that SVM(KLD) scores well on all the four groups of classes identified; while it is not always the best method (e.g., it is outperformed by other methods in the HP and VHP groups), it consistently performs well on all four groups. In particular, SVM(KLD) seems to excel at classes characterized by drastic imbalance, as witnessed by the VLP group, where SVM(KLD) is the best performer, and by the LP group, where SVM(KLD) is the best performer in a statistically significant way. In fact, this group of classes seems largely responsible for the excellent overall performance (Column 6) displayed by SVM(KLD), since on the LP group the margin between it and the other methods is large (4.92E-04 against 1.98E-03 of the 2nd best method), and since the VLP and LP groups altogether account for no less than 82 out of the total 99 classes. This latter fact characterizes most naturally occurring datasets, whose class distribution usually exhibits a power law, with very few highly frequent classes and very many highly infrequent classes. The OHSUMED-S results essentially confirm the RCV1-V2 results, with SVM(KLD) again the best performer on the VLP and LP classes, and still performing well, although not being the best, on HP and VHP.
The stability of SVM(KLD) is also confirmed by Table III, which reports, for the same groups of test sets identified by Table II, the variance in KLD across the members of the group. For example, on RCV1-V2, Column 3 reports the variance in KLD across all the 34 classes such that .01 ≤ λ T r (c) ≤ 0.05 and across the 52 test weeks, for a total of 34 × 52 = 1, 768 test sets. What we can observe from this table is that, when averaged across all the 99 × 52 = 5148 test sets (Column 6), the variance of SVM(KLD) is lower than the variance of all other methods in a statistically significant way. The variance of SVM(KLD) is fairly low in all the four subsets of classes, and particularly so in the subsets of the most imbalanced classes (VLP and LP), in which SVM(KLD) is the best performer in a statistically significant way. The OHSUMED-S results essentially confirm the RCV1-V2 results, with SVM(KLD) the best performer on VLP and LP, and still behaving well on HP and VHP.
Concerning the baselines, our results seem to disconfirm the ones reported in [Forman 2008] according to which the MS method is the best of the lot, and according to which the ACC method "can estimate the class distribution well in many situations, but its performance degrades severely when the training class distribution is highly imbalanced". In our experiments, instead, MS is substantially outperformed by several baseline methods; ACC is instead a strong contender, and (contrary to the statement above) especially shines on the subsets of the most imbalanced classes. The results of both Tables II and III clearly show that, on both RCV1-V2 and OHSUMED-S, PACC is the best of the baseline methods presented in §2.2.

4.2.2.
Analysing the results along the temporal dimension. We now analyse the results along the temporal dimension. In order to do this for the RCV1-V2 dataset (resp., OHSUMED-S dataset), for each of the 52 test weeks (resp., 4 test years) we average the 99 (resp., 88) accuracy results corresponding to the individual classes, and check the temporal accuracy trend resulting from these averages. This trend is displayed in Figure 1, where the results of SVM(KLD) are plotted together with the results of the three best-performing baseline methods. The plots unequivocally show that SVM(KLD) is the best method across the entire temporal spectrum for both RCV1-V2 and OHSUMED-S.
Note that quantification accuracy remains fairly stable across time, i.e., we are not witnessing any substantial decrease in quantification accuracy with time. Intuition might instead suggest that quantification accuracy should decrease with time, due to the combined effects of true concept drift and distribution drift. This may indicate that (at least in the context of broadcast news that RCV1-V2 represents, and in the context of medical scientific articles that OHSUMED-S represents) the chosen timeframe (one year for RCV1-V2, four years for OHSUMED-S) is not sufficient enough a timeframe to observe a significant such drift. 4.2.3. Analysing the results along the distribution drift dimension. The last angle according to which we analyse the results is distribution "drift". That is, we conduct our analysis in terms of how much the prevalence λ T ei (c) in a given test set T e i "drifts away" from Table III. Variance of SVM(KLD) and of 10 baseline methods as measured in terms of KLD on the 99 classes of RCV1-V2 (top) and on the 88 classes of OHSUMED-S (bottom) grouped by class prevalence in T r (Columns 2 to 5); Column 6 indicates variance across all the classes. Boldface represents the best value. The methods are ranked in terms of the value indicated in the "All" column. We have also run statistical significance tests in order to check whether the improvement obtained by the best performing method over the 2nd best performer on the test sets belonging to a certain quartile is statistically significant. The results of this analysis are displayed in Table IV. The most important observation here is that SVM(KLD) is the best performer in a statistically significant way, both overall and on three out of four quartiles (on the "very high drift" quartile SVM(KLD) is outperformed by PACC). Additionally, it is worth observing that its performance is consistently high on each quartile. Table V reports variance figures, showing again the stability of SVM(KLD), which is the most stable method overall and on three out of four quartiles (on the VHD quartile the most stable method is PACC). 4.2.4. Evaluating the results according to RAE. It may be interesting to analyse the results of the previous experiments according to an evaluation measure different from KLD, such as the RAE measure introduced in §2.1. As discussed in §2.1, RAE is the most (and only) reasonable alternative to KLD proposed so far. Given the simplicity of its mathematical form, it is also a measure everyone can relate to. Similarly to Table IV, Table VI reports the results of our experiments broken down into quartiles of test sets homogeneous by distribution drift; the difference with Table  IV is that RAE is now used as the evaluation measure in place of KLD. The RCV1-V2 results of Table IV confirm the superiority of SVM(KLD) over the baselines, notwithstanding the discrepancy between evaluation measure (RAE) and loss function optimized (KLD). As an average across the 5148 test sets, SVM(KLD) obtains an average RAE value of 0.465, which improves in a statistically significant way over the 0.674 result obtained by the second best performer, ACC; the next best-performing methods, CC and PACC, obtain dramatically worse results (1.087 and 1.466, respectively). SVM(KLD) is also the best performer, in a statistically significant way, in each of the four quartiles.

VLP
In this case OHSUMED-S results are substantially different from the RCV1-V2 results, since here the best performer is MM(KS) (a weak contender in all the experiments that we have reported so far), while SVM(KLD) performs much less well. The overall performance of SVM(KLD) is penalized by a bad performance on the VHD quartile, since it is the best performer (and in a statistically significant way) on the other three quartiles. While there is some discrepancy between the outcomes of the RCV1-V2 experiments and those of the OHSUMED-S experiments, we observe that the former might be considered somehow more trustworthy than the latter ones, since RCV1-V2 is much bigger than OHSUMED-S (approximately 60 times more test documents). Additionally, and more importantly, let us recall that SVM(KLD) is optimized for KLD, and not for RAE. This means that, in keeping with our plan to use classifiers explicitly optimized for the evaluation function used for assessing quantification accuracy, should we really deem RAE to be the "right" such function we would implement and use SVM(RAE)!, and not SVM(KLD). In other words, in the RCV1-V2 results of Table VI SVM(KLD) turns out to be the best performer despite the fact that we here use RAE as an evaluation measure.

Testing classification accuracy
As discussed in Section 1, quantification accuracy is related to the classifier's ability to balance false positives and false negatives, but is not related to its ability to keep their total number low, which is instead a key requirement in standard classification. However, it is fairly natural to expect that a user will trust a quantification method only inasmuch as its good quantification performance results from reasonable classification performance. In other words, a user is unlikely to accept a classifier with good quantification accuracy but bad classification accuracy. For this reason we have compared, in terms of classification accuracy, SVM(KLD) against the traditional classification-oriented SVMs (i.e., SVM org -see Section 3), with the goal of ascertaining if the former has also a reasonable classification accuracy. Default parameters have been used for both, for the reasons already explained in the first paragraph of Section 4. We have compared the two systems by using the same training set as used in the quantification experiments, and as the test set the union of the 52 test sets used for quantification (i.e., a single test set of 791,607 documents across 99 classes). Evaluation is based on the F 1 measure, both in its micro-averaged (F µ 1 ) and macro-averaged (F M 1 ) versions. On the RCV1-V2 dataset, in terms of F µ 1 SVM(KLD) performs slightly worse than SVM org (.755 instead of .777, with a relative decrease of −2.83%), while in terms of F M 1 SVM(KLD) performs slightly better (.440 instead of .433, a relative increase of +1.61%), which indicates that, on highly imbalanced classes, SVM(KLD) is not only a better quantifier, but also a better classifier. To witness, on the 48 classes for which λ T r ≤ 0.01 (i.e., on the most imbalanced classes) we obtain F µ 1 = .294 for SVM org while SVM(KLD) obtains F µ 1 = .350 (an increase of +19.09%). The trends on the AA:20

Andrea Esuli and Fabrizio Sebastiani
OHSUMED-S dataset are similar, though with smaller margins. In terms of F µ 1 SVM(KLD) performs slightly worse than SVM org (F µ 1 = .713 instead of .722, with a relative decrease of −1.24%), while in terms of F M 1 SVM(KLD) performs slightly better (.405 instead of .398, a relative increase of +1.76%), confirming the insights obtained from RCV1-V2. On the 51 classes for which λ T r ≤ 0.01 (i.e., on the most imbalanced classes) we obtain F µ 1 = .443 for SVM org while SVM(KLD) obtains F µ 1 = .456 (an increase of +2.93%).
All in all, these results show that classifiers trained via SVM(KLD), aside from delivering top-notch quantification accuracy, are also characterized by very good classification accuracy. This makes the quantifiers generated via SVM(KLD) not only accurate, but also trustworthy.

Testing efficiency
SVM(KLD) has also good properties in terms of sheer efficiency.
Concerning training, Joachims [2005] proves that training a classifier with SVM perf is O(n 2 ), with n the number of training examples, for any loss function that can be computed from a contingency table (such as KLD indeed is). This is certainly more expensive than training a classifier by means of a standard, linear SVM (which is at the heart of Forman's implementation of all the quantification methods of §2.2), since this latter is well-known to be O(sn) (with s the average number of non-zero features in the training objects) [Joachims 2006].
However, note that, while SVM(KLD) only requires training a classifier by means of SVM perf , setting up a quantifier with any of the methods of §2.2 (with the only exception of the simple CC method) requires more than simply training a classifier. For instance, ACC (together with the methods derived from it, such as T50, X, MAX, MS, PACC) also requires estimating tpr T e and f pr T e on the training set via k-fold cross validation, which may be expensive; analogously, both MM(KS) and MM(PP) require estimating D T e c and D T e c via k-fold cross-validation, and the same considerations apply. In practice, using SVM perf turns out to be affordable. On RCV1-V2, training the 99 binary classifiers described in the previous sections via SVM perf required on average about 4.7 seconds each 16 . By contrast, training the analogous classifiers via a standard linear SVM required on average only 2.1 seconds each. However, this means that, if k-fold cross-validation is used for the estimation of parameters with a value of k ≥ 2 (meaning that, for each class, additional k classifiers need to be trained), the computational advantage of using a linear SVM instead of the more expensive SVM perf is completely lost. Forman [2008] recommends choosing k = 50 in order to obtain more accurate estimates of tpr T e and f pr T e for use in ACC and derived methods; this means making the training phase roughly (2.1 · 51)/4.7 ≈ 22 times slower than the training phase of SVM(KLD).
Concerning the computational costs involved at classification / quantification time, SVM(KLD) and all the baseline methods discussed in this paper are equivalent, since (a) they all generate linear classifiers of equal efficiency, and (b) in ACC and derived methods the cost of the post-processing involved in computing class prevalences from the classification decisions is negligible.

RELATED WORK
An early mention of quantification can be found in [Lewis 1995, Section 7], where this task is simply called counting; however, the author does not propose any specific solu-tion for this problem. Forman [2005;2006a; is to be credited for bringing the problem of quantification to the attention of the data mining and machine learning research communities, and for proposing several solutions for performing quantification and for evaluating it. Chan and Ng [2005; apply quantification (which they call "class prior estimation") to determining the prevalence of different senses of a word in a text corpus, with the goal of improving the accuracy of word sense disambiguation algorithms as applied on that corpus. Forman [2008] uses quantification in order to establish the prevalence of various support-related issues in incoming telephone calls received at customer support desks. Esuli and Sebastiani [2010a] apply quantification methods for estimating the prevalence of various response classes in open-ended answers obtained in the context of market research surveys (they do not use the term "quantification", and rather speak of "measuring classification accuracy at the aggregate level"). Hopkins and King [2010] classify blog posts with the aim of estimating the prevalence of different political candidates in bloggers' preferences. Gonzalez-Castro et al. [2013] and Sanchez et al. [2008] use quantification for establishing the prevalence of damaged sperm cells in a given sample for veterinary applications. Baccianella et al. [2013] classify radiology reports with the aim of estimating the prevalence of different pathologies. Tang et al. [2010] focus on network quantification problems, i.e., problems in which the goal is to estimate class prevalence among a population of nodes in a network. Alaiz-Rodriguez et al. [2011], Limsetto andWaiyamai [2011], Xue andWeiss [2009], and Zhang and Zhou [2010] use quantification in order to improve classification, i.e., attempt to estimate class prevalence in the test set in order to generate a classifier that better copes with differences in the class distributions of the training set and the test set.

Applications of quantification
Many other works use quantification "without knowingly doing so"; that is, unaware of the existence of methods specifically optimized for quantification, they use classification with the only goal of estimating class prevalences. In other words, these works use plain "classify and count". Among them, Mandel et al. [2012] use tweet quantification in order to estimate, from a quantitative point of view, the emotional responses of the population (segmented by location and gender) to a natural disaster; O'Connor et al. [2010] analyse the correlation between public opinion as measured via tweet sentiment quantification and via traditional opinion polls; Dodds et al. [2011] use tweet sentiment quantification in order to infer spatio-temporal happiness patterns; and Weiss et al. [2013] use quantification in order to measure the prevalence of different types of pets' activity as detected by wearable devices. Bella et al. [2010] compare many of the methods discussed in §2.2, and find that CC ≺ PCC ≺ ACC ≺ PACC (where ≺ means "underperforms"). Also Tang et al. [2010] experimentally compare several among the methods discussed in §2.2, and find that CC ≺ PCC ≺ ACC ≺ PACC ≺ MS. They also propose a method (specific to linked data) that does not require the classification of individual items, but they find that it underperforms a robust classification-based quantification method such as MS. However, the experimental comparisons of [Bella et al. 2010] and [Tang et al. 2010] are both framed in terms of absolute error, which seems a sub-standard evaluation measure for this task (see §2.1); additionally, the datasets they test on do not exhibit the severe imbalance typical of many binary text classification tasks, so it is not surprising that their results concerning MS are not confirmed by our experiments.

Quantification methods
The idea of using a learner that directly optimizes a loss function specific to quantification was first proposed, although not implemented, in [Esuli and Sebastiani 2010b], which indeed proposes using SVM perf to directly optimize KLD; the present paper is thus the direct realization of that proposal. The first published work that implements and tests the idea of directly optimizing a quantification-specific loss function is [Milli et al. 2013], whose authors propose variants of decision trees and decision forests that directly optimize a loss combining classification accuracy and quantification accuracy. At the time of going to print we have become aware of a related paper [Barranquero et al. 2015] whose authors, following [Esuli and Sebastiani 2010b], use SV M perf to perform quantification; differently from the present paper, and similarly to [Milli et al. 2013], they use an evaluation function that combines classification accuracy and quantification accuracy. Bella et al. [2014] address the problem of performing quantification for the case in which the output variable to be predicted for a given individual is a real value, instead of a class as in the case we analyse; that is, they analyse quantification as a counterpart of regression, rather than of classification as we do.

Other related work
Quantification as defined in this paper bears some relation with density estimation [Silverman 1986], which can be defined as the task of estimating, based on observed data, the unknown probability density function of a given random variable. If the random variable is discrete, this means estimating, based on observed data, the unknown distribution across the discrete set of events, i.e., across the classes. An example density estimation problem is estimating the percentage of white balls in a very large urn containing white balls and black balls. However, there are two essential differences between quantification and density estimation, i.e., that (a) in density estimation the class to which a data item belongs can be established with certainty (e.g., if a ball is picked, it can be decided with certainty if it is black or white), while in quantification this is not true; and (b) in density estimation the population of data items is usually so large as to make it infeasible to check the class to which each data item belongs (e.g., only a limited sample of balls is picked), while this is not true in quantification, where it is assumed that all the items can be checked for the purpose of estimating the class distribution.
A research area that might seem related to quantification is collective classification (CoC) [Sen et al. 2008]. Similarly to quantification, in CoC the classification of instances is not viewed in isolation. However, CoC is radically different from quantification in that its focus is on improving the accuracy of classification by exploiting relationships between the objects to classify (e.g., hypertextual documents that link to each other). Differently from quantification, CoC (a) assumes the existence of explicit relationships between the objects to classify, which quantification does not, and (b) is evaluated at the individual level, rather than at the aggregate level as quantification.
Quantification bears strong relations with prevalence estimation from screening tests, an important task in epidemiology (see [Levy and Kass 1970;Lew and Levy 1989;Küchenhoff et al. 2012;Rahme and Joseph 1998;Zhou et al. 2002]). A screening test is a test that a patient undergoes in order to check if s/he has a given pathology. Tests are often imperfect, i.e., they may give rise to false positives (the patient is incorrectly diagnosed with the pathology) and false negatives (the test wrongly diagnoses the patient to be free from the pathology). Therefore, testing a patient is akin to classifying a document, and using these tests for estimating the prevalence of the pathology in a given population is akin to performing aggregative quantification. The main difference between this task and quantification is that a screening test typically has known and fairly constant recall (that epidemiologists call "sensitivity") and fallout (whose complement epidemiologists call "specificity"), while the same usually does not happen for a classifier.

CONCLUSIONS
We have presented SVM(KLD), a new method for performing quantification, an important (if scarcely investigated) task in supervised learning, where estimating class prevalence, rather that classifying individual items, is the goal. The method is sharply different from most other methods presented in the literature. While most such methods adopt a general-purpose classifier (where the decision threshold has possibly been tuned according to some heuristics) and adjust the outcome of the "classify and count" phase, we adopt a straightforward "classify and count" approach (with no threshold tuning and/or a posteriori adjustment) but generate a classifier that is directly optimized for the evaluation measure used for estimating quantification accuracy. This is not straightforward, since an evaluation measure for quantification is inherently non-linear and multivariate, and thus does not lend itself to optimization via standard supervised learning algorithms. We circumvent this problem by adopting a supervised learning method for structured prediction that allows the optimization of non-linear, multivariate loss functions, and extend it to optimize KLD, the standard evaluation measure of the quantification literature.
Experimental results that we have obtained by comparing SVM(KLD) with ten different state-of-the-art baselines show that SVM(KLD) (i) is more accurate (in a statistically significant way) than the competition, (ii) is more stable than the tested baselines, since it systematically shows very good performance irrespectively of class prevalence (i.e., level of imbalance) and distribution drift (i.e., discrepancy between the class distributions in the training and in the test set), (iii) is also accurate at the classification (aside from the quantification) level, and (iv) is 20 times faster to train than the competition. These experiments have been run, against 10 state-of-the-art baseline methods, on a batch of 5,148 binary, high-dimensional datasets (averaging more than 15,200 documents each and characterized by more than 50,000 features) and on a further batch of 352 binary, high-dimensional datasets (averaging more than 3,200 documents each and characterized by more than 10,000 features), all characterized by varying levels of class imbalance and distribution drift. These figures qualify the present experimentation as a very large one.

A. APPENDIX: ON THE PRESUMED INVARIANCE OF T P R AND F P R ACROSS TEST SETS
Most methods described in §2.2 (specifically: ACC, PACC, T50, X, MAX, MS) rely, among other things, on the assumption that tpr T e and f pr T e can reliably be estimated via k-fold cross-validation on the training set; in other words, they rely on the assumption that tpr and f pr do not change when the classifier is applied to different test sets.
Indeed, Forman explicitly assumes that the application domains he confronts are of a type that [Fawcett and Flach 2005] call "y → x domains", in which tpr and f pr are in fact invariant with respect to the test set the classifier is applied to. The notation y → x means that the value of the y variable (the output label) probabilistically determines the values of the x variables (the input features), i.e., x causally depends on y; in other words, the class-conditional probabilities p(x|y) are invariant across different test sets. For instance, our classification problem may consist in predicting whether a patient suffers or not from a given pathology (a fact represented by a binary variable y) given a vector x of observed symptoms. This is indeed a "y → x domain", since the causality relation is from y to x, i.e., it is the presence of the pathology that determines the presence of the symptoms, and not vice versa. In other words, the class conditional probabilities p(x|y) do not change across test sets: if more people suffer from the pathology, more people will exhibit its symptoms. Important quantification problems within y → x domains do exist. One of them is when epidemiologists attempt to estimate the prevalence of various causes of death (y) from "verbal autopsies", i.e., binary vectors of symptoms (x) as extracted from oral accounts obtained from relatives of the deceased [King and Lu 2008].
However, many application domains are instead of the type that [Fawcett and Flach 2005] call "x → y domains", where it is y that causally depends on x, and not vice versa. For instance, our classification problem may consist in predicting whether the home football team is going to win tomorrow's match or not (y) given a number of stats (x) about its recent performance (e.g., number of goals scored in the last k matches, number of goals conceded, etc.). This is indeed a "x → y domain", since the (assumed) causality relation is from x to y, i.e., the recent performance of the team is an indicator of its state of form, which may probabilistically determine the outcome of the game; it is certainly not the case that the outcome of the game determines the past performance of the team! And in x → y domains the class-conditional probabilities p(x|y) are not guaranteed to be constant.
One may wonder whether text classification contexts are y → x or x → y domains. Given the wide array of uses text classification has been put to, we think it is difficult to make general statements about this. We prefer to follow the advice in [Fawcett and Flach 2005], who recommend "that researchers test their assumptions in practice". We have thus compared, for each of our 5,148 RCV1-V2 test sets and 352 OHSUMED-S test sets, (a) the tpr T e and f pr T e values that the standard linear SVM classifier (the one at the heart of all our baseline methods) has obtained, with (b) the corresponding tpr T r and f pr T r values that we have computed on the training set via k-fold cross validation. If tpr and f pr were invariant across different sets, then (a) and (b) should be approximately the same. The results, which are displayed in Table VII, show that in our domain tpr and f pr are far from being invariant across different sets. For instance, on RCV1-V2 the average tpr T r as computed via k-fold cross-validation is 0.443, while the analogous average on the 5,148 test sets is 0.357, a -19.29% decrease; interestingly enough, on OHSUMED-S we witness an analogous trend but with opposite sign, with Table VII. Average tpr and f pr values measured on the training and test sets of the RCV1-V2 and OHSUMED-S datasets. The values in the avg(tpr T r ) and avg(f pr T r ) are computed via k-fold crossvalidation, and are thus averages across 99 classes (RCV1-V2) and 88 classes (OHSUMED-S). The values in the avg(tpr T e ) and avg(f pr T e ) are averages across 5,148 test sets (RCV1-V2) and 352 test sets (OHSUMED-S). Column 4 and 7 show the relative variation in these values, measured as (tpr T e − tpr T r )/(tpr T r ) and (f pr T e − f pr T r )/(f pr T r ), respectively. avg(tpr T r ) avg(tpr T e ) rel % diff avg(f pr T r ) avg(f pr T e ) rel % diff RCV1 In conclusion, tpr and f pr turn out to be far from being invariant across different sets, at least in the application contexts from which our datasets are drawn. It is thus evident that, at the very least in text quantification contexts, assuming that tpr and f pr are indeed invariant, and adopting methods that rely on this assumption, is risky, and definitely suboptimal in some cases. This is yet another reason to prefer methods, such as SVM(KLD), which do not rely on any such assumption.