Ranking and combining multiple predictors without labeled data

Fabio Parisi; Francesco Strino; Boaz Nadler; Yuval Kluger

Source-linked AI summary

Ranking and combining multiple predictors without labeled data

Fabio Parisi, Francesco Strino, Boaz Nadler, Yuval Kluger

arXiv:1303.3257v3Mar 13, 2013stat.MLcs.LG

TL;DR

The paper studies how to rank and combine classifiers with unknown reliability using only predictions on unlabeled data. It develops a spectral covariance-based method and the Spectral Meta-Learner, which typically outperforms most ensemble members and majority voting while remaining robust to small malicious groups.

Problem
The central problem is ranking and combining classifiers when their accuracies cannot be assessed from labeled data.
Method
The method uses conditional-independence spectral analysis: covariance off-diagonals form a rank-one matrix, whose leading eigenvector supplies ranking information and SML weights.
Results
SML typically achieves higher accuracy than most classifiers and majority voting on simulated and real data, with results comparable to maximum likelihood estimation.
Takeaways & Limitations
SML offers an unsupervised ensemble and a better initialization for maximum likelihood, while spectral approaches remain robust to small unknown malicious cartels.
Takeaways & Limitations
The analysis is mainly asymptotic and assumes perfect conditional independence; SML may be suboptimal with finite samples, especially when one classifier is much better than the others.

Abstract

from arXiv · show

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 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 a) reliably rank them; and b) construct a meta-classifier more accurate than most classifiers in the ensemble? Here we present a novel 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, as 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), a novel ensemble classifier whose weights are equal to this 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.

Introduction

The paper addresses unsupervised ranking and combination of predictions from classifiers or advisers whose reliability is unknown. It develops a spectral approach that ranks classifiers and constructs SML, which typically outperforms most ensemble members and majority voting while remaining robust to small malicious groups.

Motivation: The paper asks whether classifiers can be ranked and combined accurately using only predictions on unlabeled test data.The setting includes advisers or algorithms with unknown reliability and no available labels for assessing performance.
Spectral insights: Under conditional independence, classifier covariance off-diagonals form a rank-one matrix whose leading eigenvector identifies relative balanced accuracies.This spectral structure provides a computationally efficient route to ranking classifiers without labels.
Spectral Meta-Learner: A linear approximation to maximum likelihood yields SML, an unsupervised ensemble learner weighted by the covariance eigenvector entries.The method is designed to combine predictions without labeled data.
Robustness: Unlike majority voting, SML is robust to a small enough unknown cartel of classifiers that attempts to move predictions away from the ground truth.The cartel produces a rank-two covariance matrix, while SML remains robust in this setting.
Empirical results: SML is typically more accurate than most classifiers and their majority vote on simulated and real-world data, with performance comparable to maximum likelihood estimation.It also provides a better initialization for computing the maximum likelihood solution.

Problem setup

The problem consists of ranking and combining binary classifiers that predict labels for unlabeled instances, with each classifier treated as a black box of unknown accuracy. The analysis assumes independently sampled instances and conditional independence of classifier errors.

Problem formulation: Each classifier independently maps feature vectors to one of two labels, +1 or −1, after undisclosed training on unavailable labeled data.The classifiers are therefore treated as black-box functions with unknown classification accuracy.
Problem formulation: Using only predictions on an unlabeled dataset, the task is to rank classifiers and estimate the unknown true labels with an improved combined predictor.No labeled data or external reliability information is available.
Performance measure: Classifier performance is measured by balanced accuracy, defined through sensitivity and specificity for positive and negative classes.Sensitivity measures correct positive predictions, while specificity measures correct negative predictions.
Assumptions: The unlabeled instances are assumed to be i.i.d. samples from pX, and classifier errors are conditionally independent given the true class.The conditional-independence condition factorizes paired prediction probabilities given either class label.
Assumptions: Approximate conditional independence can arise when advisers do not communicate or algorithms use different design principles or independent information sources.The paper notes that these assumptions also appear in related crowdsourcing and ensemble-learning settings.

Ranking of classifiers

The paper ranks classifiers from the covariance matrix computed on unlabeled predictions. Under the stated assumptions, its rank-one off-diagonal structure makes the leading eigenvector proportional to classifier balanced accuracies.

Spectral ranking: The covariance matrix of classifier predictions provides the basis for ranking classifiers without labeled data.Its sample estimate converges to the population covariance as the unlabeled dataset grows.
Spectral structure: The covariance off-diagonals match a rank-one matrix, whose leading eigenvector has entries proportional to classifier balanced accuracies up to sign.This links the covariance structure directly to classifier performance.
Ranking rule: Sorting the leading eigenvector entries ranks the classifiers by balanced accuracy.The sign ambiguity can be resolved under an assumption such as most classifiers being better than random.
Finite-sample estimation: A finite-sample estimate reconstructs the rank-one matrix from sample covariance entries before eigendecomposition.The method estimates diagonal entries through a transformed linear system and then computes the leading eigenvector.
Asymptotic behavior: As the unlabeled sample size grows, the estimated rank-one matrix and leading eigenvector converge to their population counterparts, yielding asymptotically correct rankings.The stated perturbation behavior is ˆR − R = O(1/√S) and ˆv − v = O(1/√S).

The Spectral Meta Learner (SML)

The Spectral Meta-Learner (SML) approximates the maximum-likelihood ensemble by weighting classifier predictions with entries of an estimated leading covariance eigenvector. This provides an unsupervised alternative to majority voting and a stronger initialization for iterative maximum-likelihood estimation.

The Spectral Meta Learner (SML): The method addresses unsupervised meta-learning by estimating unknown labels from predictions of multiple classifiers without labeled test data.
The Spectral Meta Learner (SML): The exact maximum-likelihood classifier has weights depending on unknown sensitivities and specificities, motivating SML’s approximation.
The Spectral Meta Learner (SML): Expectation-maximization can converge to a local rather than global maximum, making initialization important for obtaining a good solution.
The Spectral Meta Learner (SML): SML combines classifier predictions using weights proportional to the leading eigenvector entries estimated from their covariance matrix.The eigenvector entries replace unknown balanced-accuracy terms in a linearized maximum-likelihood classifier.
The Spectral Meta Learner (SML): SML is intended to outperform majority voting by assigning greater weight to more accurate classifiers.
The Spectral Meta Learner (SML): Initializing iterative maximum-likelihood estimation with SML typically provides a better starting point than majority voting.

Learning in the Presence of a Malicious Cartel

A malicious cartel adds a second structured component to the classifiers’ covariance matrix, changing the spectral problem from rank one to rank two. Under stated conditions, SML can reduce the cartel’s influence more effectively than majority voting.

Learning in the Presence of a Malicious Cartel: The cartel model separates honest classifiers from malicious classifiers that predict a distinct target labeling under conditional-independence assumptions.
Learning in the Presence of a Malicious Cartel: The covariance formulation incorporates classifier accuracies, cartel-target accuracy relative to truth, and cartel members’ accuracies relative to their target.
Learning in the Presence of a Malicious Cartel: With one cartel, the off-diagonal covariance matrix becomes rank two rather than rank one.The two eigenvalues are determined by contributions from honest classifiers and cartel classifiers.
Learning in the Presence of a Malicious Cartel: SML can asymptotically ignore a cartel targeting labels unrelated to the truth when the honest-classifier eigenvalue dominates.Majority voting remains affected in proportion to the cartel fraction under the same setting.

Application to simulated and real-world datasets

Simulations and real-world experiments evaluate spectral ranking, SML, and iterative maximum-likelihood estimation under independent classifiers, poor predictors, correlated errors, and cartel contamination. Across these settings, SML generally improves on majority voting and provides a consistently strong initialization for iterative estimation.

Simulations: In simulations, the highest-accuracy classifier was identified by the largest absolute eigenvector entry with at least 80% probability and ranked among the top five above 99% of the time.
Simulations: SML was significantly more accurate than majority voting, while maximum-likelihood estimation initialized with SML produced relatively small further improvements.
Simulations: With a cartel comprising 20% of classifiers, SML remained nearly perfect while majority voting and its initialized maximum-likelihood method were far from 1 balanced accuracy.All methods eventually deteriorated as cartel size increased, but SML-based approaches were substantially more robust in the simulations.
Application to simulated and real-world datasets: On approximately assumption-satisfying real datasets, SML and both initialization strategies showed similar performance, with sample covariance matrices nearly rank one.The reported covariance condition was λ1(Ŕ)/Trace(Ŕ) > 0.8.
Application to simulated and real-world datasets: When predictors were weak or covariance structure was far from rank one, SML initialization avoided poor outcomes observed with majority-voting initialization.
Application to simulated and real-world datasets: Even with highly clustered errors, iterative estimation initialized with SML had equal or higher median balanced accuracy than initialization with majority voting across all datasets.

Summary and Discussion

The paper develops a spectral framework for unsupervised ranking and combining of predictors, while identifying limitations and extensions involving sampling, classifier dependence, task type, instance difficulty, and malicious cartels.

Summary and Discussion: The spectral analysis provides an efficient, asymptotically consistent solution for unsupervised ranking and combining of multiple predictors under independence assumptions.The off-diagonal covariance structure is rank one, with eigenvector entries proportional to balanced accuracies.
Summary and Discussion: SML may be sub-optimal with finite samples, especially when one classifier is substantially better than the others, and the analysis assumes infinitely many unlabeled examples and perfect error independence.The authors identify finite-sample and approximate-independence analysis as important future work.
Summary and Discussion: Extending the approach to multi-class and regression settings is proposed because their classifier or regressor covariance matrices may remain approximately low-rank.The paper presents this as a natural extension rather than an established result.
Summary and Discussion: Incorporating instance difficulty could improve prediction quality because very easy and very difficult examples are uninformative for ranking classifiers.The paper leaves modifying the approach to account for instance difficulty as future research.
Summary and Discussion: The analysis also examines malicious classifier cartels and motivates spectral methods for identifying, targeting, or ignoring their contributions.The proposed applications include electoral committees and trading decisions.

Materials and methods

The experiments use 17 binary-classification datasets spanning science, engineering, data mining, and finance, with classifiers drawn from published implementations and Weka.

Materials and methods: The study evaluates methods on 17 binary-classification datasets from science, engineering, data mining, and finance.The datasets are listed in Table S1.
Materials and methods: The classifiers are described in a cited reference or implemented in the Weka software suite.Their descriptions are provided in Table S2.
Materials and methods: Statistical analysis and visualization were performed with MATLAB 2012a and R.Additional information is provided in the supplementary information.

Supplementary Information: Ranking and combining multiple

The supplementary analysis estimates the rank-one covariance structure and its leading eigenvector from sample covariances, compares estimation methods, and derives SML as a linearized likelihood estimator.

Ranking and combining multiple: The off-diagonal classifier covariances equal those of a rank-one matrix, whose leading eigenvector encodes classifier balanced accuracies.This rank-one structure motivates spectral ranking from unlabeled predictions.
Weighted linear system: Four eigenvector-estimation approaches have comparable rankings in simulation, while direct eigendecomposition is slightly less accurate and the linear-system method is computationally efficient.The compared approaches are linear system, weighted linear system, SDP, and direct eigendecomposition.
Linear system: A linear-system estimator reconstructs the rank-one matrix and yields an asymptotically correct classifier ranking as the unlabeled sample size grows.The method estimates diagonal entries through a transformed vector and solves a quadratic objective by linear equations.
SDP approach: The SDP approach relaxes a rank-one constraint to a trace constraint and is slower than the linear-system methods despite polynomial-time solvability.It is formulated as a convex semidefinite program.
Direct eigendecomposition: Direct eigendecomposition is generally inconsistent for a finite number of classifiers, but becomes close to the true eigenvector when the rank-one matrix has a large spectral gap.When all classifiers have balanced accuracy bounded away from one-half, the angle between the relevant eigenvectors becomes small for many classifiers.
The SML: A first-order approximation of the MLE estimator: SML is derived by linearizing the maximum-likelihood estimator around chance-level sensitivity and specificity, using the rank-one eigenvector as ensemble weights.The resulting ensemble classifier is named the Spectral Meta-Learner.

D Comparison between SML and Majority Voting

Under the stated conditional-independence setting, SML is designed to outperform equal-weight majority voting by weighting classifiers according to spectral estimates of their reliability.

SML’s balanced accuracy is always at least that of majority voting in the analyzed special case.The result is established for conditionally independent classifiers where one classifier may differ from the others.
SML is also at least as accurate as the remaining classifiers and nearly matches the best classifier when those classifiers are better than random.The guarantee relative to the best classifier permits a small gap that decreases with ensemble size.
SML is typically more accurate than most ensemble classifiers, whereas majority voting can fall below random performance when one classifier is much worse than random.This illustrates why adapting weights to inferred reliability can help.
SML is conservative and can underperform the best classifier, because its finite nonzero weights differ from the maximum-likelihood solution’s potentially extreme weights.The performance gap is described as small and exponentially decreasing with the number of classifiers.

G.1 Simulated data: Ensembles of statistically independent predictions

The simulations construct conditionally independent classifier ensembles with controlled balanced accuracies, using randomized predictions derived from known ground-truth labels.

Simulated ensembles use conditionally independent RDFBA classifiers whose empirical balanced accuracies are fixed before prediction generation.RDFBA denotes the random detector with fixed balanced accuracy algorithm.
Each RDFBA classifier starts from the ground truth, then introduces randomly selected false positives and false negatives under a balanced-accuracy constraint.The construction preserves the target accuracy while randomizing error locations.
The simulations sample π uniformly from 0.3 to 0.8 and evaluate 600 test instances comprising 300 positives and 300 negatives.Finite sampling can make observed accuracy slightly exceed 0.8 or fall below 0.3.

G.2 Simulated data: Ensembles of independent predictors with one cartel present

Cartel simulations extend the independent-predictor construction by replacing a fraction of classifiers with predictors sharing a common cartel target vector.

Cartel ensembles combine independent honest predictions with a cartel whose members are independently generated around a shared target vector.The cartel target is assigned its own empirical balanced accuracy relative to the ground truth.
The real-data classifier ensembles are trained independently and evaluated on the same test data, using partially or non-overlapping training data.These constructions provide empirical settings with predictor dependence or cartel-like structure.

H Custom datasets

The custom-data evaluation spans diverse real-world tasks and compares spectral methods with individual classifiers, voting, and ensemble baselines across supplementary datasets and figures.

H Custom datasets: The custom benchmark adds nine datasets from economics, sociology, geography, semantics, ecology, and finance to eight standard UCI datasets.The supplementary material provides scripts for generating the custom feature and label matrices.
H Custom datasets: The benchmark includes tasks based on geography, stock-price movements, email keywords, satellite chlorophyll measurements, song tags, and place names.These tasks cover heterogeneous feature spaces and prediction targets.
I Supplementary Tables: The supplementary tables summarize datasets, Weka classifiers, and ensemble characteristics including deviations from conditional independence and the median rank of the best inferred predictor.Table S3 reports averages over runs except for the median true rank quantity.
J Supplementary Figures: In the illustrative nine-classifier example, majority-voting performance varies linearly with the first classifier’s accuracy, while SML varies piecewise linearly with threshold-induced jumps.The example fixes the other classifiers’ sensitivity at π = 0.6.
H Custom datasets: Figures compare several classifiers and spectral methods on real-world datasets, often against the ensemble’s median balanced accuracy.The figures include settings with nearly satisfied independence conditions, cartel-like predictor structure, sparse ENRON features, and ranking outcomes.