Source-linked AI summary
Estimating Accuracy from Unlabeled Data: A Probabilistic Logic Approach
Emmanouil A. Platanios, Hoifung Poon, Tom M. Mitchell, Eric Horvitz
TL;DR
The paper addresses estimating classifier accuracy without labeled data when multiple classification problems are linked by logical constraints. It encodes those constraints in probabilistic logic to infer error rates and target outputs, and reports strong performance across constrained and unconstrained datasets. The approach also scales through heuristic grounding and stochastic consensus ADMM, although identifiability can require assumptions when constraints are absent or symmetric.
Problem
The paper addresses estimating accuracies and true outputs for multiple classifiers from unlabeled data when their target functions may be logically constrained.
Method
The method encodes logical constraints as probabilistic rules over classifier error rates and performs inference, using heuristic grounding and stochastic consensus ADMM for scalability.
Results
Across four datasets, the method outperforms existing methods in error-rate estimation and target-output combination, including settings without logical constraints.
Takeaways & Limitations
Logical constraints provide additional information for unlabeled accuracy estimation, while the inference system can scale to many functions and millions of observations.
Takeaways & Limitations
When logical constraints are absent or symmetric, error rates and target values may be unidentifiable unless assumptions such as better-than-chance approximations are imposed.
Abstract
from arXiv · showhide
We propose an efficient method to estimate the accuracy of classifiers using only unlabeled data. We consider a setting with multiple classification problems where the target classes may be tied together through logical constraints. For example, a set of classes may be mutually exclusive, meaning that a data instance can belong to at most one of them. The proposed method is based on the intuition that: (i) when classifiers agree, they are more likely to be correct, and (ii) when the classifiers make a prediction that violates the constraints, at least one classifier must be making an error. Experiments on four real-world data sets produce accuracy estimates within a few percent of the true accuracy, using solely unlabeled data. Our models also outperform existing state-of-the-art solutions in both estimating accuracies, and combining multiple classifier outputs. The results emphasize the utility of logical constraints in estimating accuracy, thus validating our intuition.
1. Introduction
The paper targets accuracy estimation without labeled data for multiple classifiers whose outputs may be linked by logical constraints. It models soft classifier responses and constrained categories, including mutually exclusive classes.
- Unlabeled accuracy estimation matters for autonomous systems and crowdsourcing, where correct outputs may be unavailable.
- Constraint violations imply that at least one participating classifier is erroneous, motivating the proposed unlabeled and semi-supervised accuracy estimation approach.
- The setting involves multiple approximations to Boolean classification functions, with unknown accuracies and unobserved true responses.
- Classifiers may return probabilities in [0, 1], allowing their certainty to be modeled rather than restricting outputs to binary responses.
- Logical constraints can be hard or probabilistic; for example, an object may be unlikely to belong to both the city and animal categories.
Grounding
The system estimates classifier error rates from probabilistic responses and can also operate without logical constraints. Its error-rate formulation supports probability-valued predictions and treats accuracy as one minus error rate.
- Classifier approximations may output probabilities for class membership instead of binary values, so their certainty enters the error model.
- For binary classifiers, the error rate is the probability that an approximation disagrees with the true function, and accuracy equals one minus error rate.
- The error definition can be relaxed for probabilistic outputs to represent an expected probability of error.
- The method is also evaluated when no logical constraints exist between domains, despite being motivated by constrained settings.
2. Related Work
Prior unlabeled accuracy methods commonly rely on assumptions such as conditional independence, but they do not incorporate logical constraints. The paper positions its approach as the first to use logic for this estimation problem.
- Earlier approaches often assume independence given outputs or knowledge of the true output distribution, while none incorporated logical constraints.
- Medical-test estimation methods address a related no-gold-standard problem but commonly assume constant accuracies across populations and conditional independence of test results.
- Agreement-based, graphical-model, nonparametric, and max-margin methods have been proposed for estimating or combining classifier outputs.
- The authors report that their method is the first to use logic for unlabeled accuracy estimation and that logical constraints provide additional information associated with improved performance.
3. Proposed Method
The proposed method encodes logical constraints as rules involving classifier error rates and performs probabilistic inference over unknown error rates and target outputs. Constraint violations provide evidence that at least one approximation is wrong.
- The method defines logic rules connecting underlying functions, approximations, error rates, and known logical constraints.
- Probabilistic inference uses these rules as priors to estimate error rates and infer the unobserved outputs of the underlying functions.
- When approximation outputs violate a logical constraint, at least one approximation must contain an error; mutually exclusive categories provide the motivating example.
3.1. Probabilistic Logic
The paper distinguishes classical logic, which infers unobserved predicate values from observed values and rules, from probabilistic logic, which infers their probabilities.
- Classical logic represents predicates and rules as boolean values, with a rule true when it holds.
- The inference goal is to determine the most likely values of unobserved ground predicates from observed predicate values and logic rules.
- Probabilistic logic assigns ground predicates and rules continuous truth values in [0, 1], representing their probabilities.
- Because truth values can be probabilistic, logical operators such as AND, OR, NOT, and IMPLIES must be redefined.
3.2. Model
The model combines classifier outputs and estimates their error rates while using mutual-exclusion and subsumption constraints to relate target functions across domains.
- 3.2. Model: The model combines function-approximation outputs into one value while accounting for approximation error rates and logical constraints between domains.
- 3.2.1. ENSEMBLE RULES: The ensemble rules encode agreement between each approximation and its target function when correct, and disagreement when the approximation errs.
- 3.2.1. ENSEMBLE RULES: Error rates are implicitly estimated from approximation agreement, yielding a weighted majority vote whose weights reflect those error rates.
- 3.2.1. ENSEMBLE RULES: Without logical constraints, jointly flipping all error rates and target responses leaves the ensemble rules unchanged, so the parameters are not identifiable.
- 3.2.2. CONSTRAINTS: The model uses mutual exclusion and subsumption constraints, covering many ontology constraints in NELL and a broad subset of constraints used in practice.
- 3.2.2. CONSTRAINTS: Mutual exclusion requires an approximation to output 0 for one domain when another mutually exclusive domain is true, while subsumption requires output 1 for the broader domain.
- 3.2.2. CONSTRAINTS: Inference determines the most likely truth values of unobserved predicates given observed predicates and the model’s rules.
3.3. Inference
The inference system uses probabilistic logic, specialized grounding, and scalable optimization to infer unobserved predicate values from observed outputs and logical rules.
- 3.3. Inference: The model can use multiple probabilistic logic frameworks, while PSL is chosen as a scalable convex relaxation of MLNs for large-scale inference.The primary model contribution is framework-independent; PSL is selected because discrete MLN inference can be inefficient at scale.
- 3.3.1. PROBABILISTIC SOFT LOGIC (PSL): PSL represents soft truth values with hinge-loss Markov random fields, where inference finds the most probable explanation by solving a convex optimization problem.Observed predicates are fixed in X, unobserved predicates are represented by Y ∈ [0, 1], and rule potentials penalize violations.
- 3.3.2. GROUNDING: Grounding constructs variables and objective terms from possible rule instances, but naive enumeration can create impractically large optimization problems.For large domains, the number of ground rules and predicates can grow combinatorially, as in the NELL setting.
- 3.3.2. GROUNDING: A heuristic grounding procedure keeps only potentially influential rules whose function-approximation predicates are observed, making grounding orders of magnitude faster than prior solutions.Rules that are always satisfied have zero distance to satisfiability and can be omitted without affecting the optimization solution.
- 3.3.3. SOLVING THE OPTIMIZATION PROBLEM: Consensus ADMM decomposes the objective into parallel subproblems linked by consensus variables, while stochastic sampling prioritizes subproblems with greater disagreement.The stochastic variant enabled inference on NELL within minutes instead of hours.
4. Experiments
The experiments evaluate unlabeled accuracy estimation and label inference across constrained and unconstrained data sets, using several baselines and three metrics. The proposed method is fastest and outperforms existing methods on constrained data while almost always outperforming them without constraints.
- Data Sets: The experiments use NELL-7 and NELL-11 with constraints, plus unconstrained uNELL and uBRAIN, to test performance across four real-world data sets.NELL-7 uses mutually exclusive categories, while NELL-11 uses the constraints illustrated in Figure 2; uNELL and uBRAIN have no logical constraints.
- Evaluation: Methods are compared using Error Rank MAD, Error MAD, and Target AUC, with lower MAD and higher AUC indicating better performance.The comparison includes Majority Vote, GIBBS-SVM/GD-SVM, DS, Agreement Rates, AR-2, and BEE-family methods.
- Results: The method’s maximum execution time was about 10 minutes, compared with about 100 minutes for HCBEE, highlighting its scalability.All results are reported in Table 1.
- Results: The proposed method outperforms all existing methods on NELL-7 and NELL-11, with significantly better error-estimation MADs and target-function AUCs.These data sets contain logical constraints and therefore directly test the paper’s central claim.
- Results: On uNELL and uBRAIN, the proposed method almost always outperforms competing methods and always does so for error-rate estimation MAD.These data sets contain no logical constraints, showing applicability beyond the constrained setting.
5. Conclusion and Future Work
The paper presents probabilistic logic for estimating multiple classifiers’ accuracies from unlabeled data while incorporating logical constraints and inferring likely true outputs. It reports state-of-the-art performance and identifies extending beyond Boolean error rates and toward self-reflection as future work.
- Conclusion: The probabilistic-logic approach estimates accuracies and infers likely outputs for multiple functions from unlabeled data while incorporating logical constraints.It scales through PSL, heuristic grounding, and stochastic consensus ADMM.
- Conclusion: Across four data sets, the proposed methods outperform the current state of the art in estimating error rates and inferring the most likely single label.
- Future Work: Future work includes modeling complete confusion matrices, handling discrete-valued rather than only Boolean functions, and applying error estimation to self-reflection.