Ranking and combining multiple predictors without labeled data

By Fabio Parisi, Francesco Strino, Boaz Nadler, Yuval Kluger. 2013

150 citations recorded by the source corpus.

Significance A key challenge in a broad range of decision-making and classification problems is how to rank and combine the possibly conflicting suggestions of several advisers of unknown reliability. We provide mathematical insights of striking conceptual simplicity that explain mutual relationships between independent advisers. These insights enable the design of efficient, robust, and reliable methods to rank the advisers’ performances and construct improved predictions in the absence of ground truth. Furthermore, these methods are robust to the presence of small subgroups of malicious advisers (cartels) attempting to veer the combined decisions to their interest. In a broad range of classification and decision-making problems, one is given the advice or predictions of several classifiers, of unknown reliability, over multiple questions or queries. This scenario is different from the standard supervised setting, where each classifier’s accuracy can be assessed using available labeled data, and raises two questions: Given only the predictions of several classifiers over a large set of unlabeled test data, is it possible to (i) reliably rank them and (ii) construct a metaclassifier more accurate than most classifiers in the ensemble? Here we present a spectral approach to address these questions. First, assuming conditional independence between classifiers, we show that the off-diagonal entries of their covariance matrix correspond to a rank-one matrix. Moreover, the classifiers can be ranked using the leading eigenvector of this covariance matrix, because its entries are proportional to their balanced accuracies. Second, via a linear approximation to the maximum likelihood estimator, we derive the Spectral Meta-Learner (SML), an unsupervised ensemble classifier whose weights are equal to these eigenvector entries. On both simulated and real data, SML typically achieves a higher accuracy than most classifiers in the ensemble and can provide a better starting point than majority voting for estimating the maximum likelihood solution. Furthermore, SML is robust to the presence of small malicious groups of classifiers designed to veer the ensemble prediction away from the (unknown) ground truth.

Subfields: Artificial Intelligence, Evaluation & Benchmarks

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Evaluation & Benchmarks

Citations in the corpus

Snorkel: Rapid Training Data Creation with Weak Supervision (2017, background): “Other techniques for estimating latent class labels given noisy observations include spectral methods [35].”
Data Programming: Creating Large Training Sets, Quickly (2016, background): “More recent results provide formal guarantees even in the absence of labeled data using various approaches [3,8,14,15,22,31].”
Triple collocation for binary and categorical variables: Application to validating landscape freeze/thaw retrievals (2016, methodology): “Building on a recent method (Parisi et al., 2014, hereafter P14), we propose a variant of TC (Categorical Triple Collocation, or CTC) that is valid for this model and, crucially, does not violate its assumptions when applied to categorical variables.”
Transfer Learning for EEG-Based Brain–Computer Interfaces: A Review of Progress Made Since 2016 (2020, unknown): “STIG uses a spectral metalearner [71] to combine predictions from an ensemble of MDRM classifiers on data from individual source subjects.”
Estimating the accuracies of multiple classifiers without labeled data (2014, methodology): “Lemma 1 appeared in Parisi et al. [2014], and implies that given the value of b one may compute the balanced accuracies of all classifiers.”
A SPECTRAL APPROACH INTEGRATING FUNCTIONAL GENOMIC ANNOTATIONS FOR CODING AND NONCODING VARIANTS (2016, background): “[47] which considered the problem of combining multiple binary classifiers of unknown reliability, and which are conditionally independent (given the true status).”
Spectral Methods Meet EM: A Provably Optimal Algorithm for Crowdsourcing (2014, background): “Related Work Many methods have been proposed to address the problem of estimating true labels in crowdsourcing (Whitehill et al., 2009; Raykar et al., 2010; Welinder et al., 2010; Ghosh et al., 2011; Liu et al., 2012; Zhou et al., 2012; Dalvi et al., 2013; Karger et al., 2014, 2013; Parisi et al., 2”
Estimating Accuracy from Unlabeled Data (2014, methodology): “Parisi et al. [2014] proposed a spectral method used to rank classiﬁers based on accuracy and combine their outputs to produce one ﬁnal label, also under an assumption of independence of the input features given the labeling.”
Learning the Structure of Generative Models without Labeled Data (2017, background): “Parisi et al. (2014) proposed a spectral approach to estimating the accuracy of members of classiﬁer ensembles.”
Assessment of network module identification across complex diseases (2019, unknown): “…to construct consensus matrices C n were tested: (1) normalization of the contribution of each module by the module size led to similar results as the basic approach described above, and (2) unsupervised estimation of module prediction accuracy using the Spectral Meta Learner ensemble method 56 .”