Source-linked AI summary
Identifying Unknown Unknowns in the Open World: Representations and Policies for Guided Exploration
Himabindu Lakkaraju, Ece Kamar, Rich Caruana, Eric Horvitz
TL;DR
The paper addresses how to discover high-confidence prediction errors that models cannot identify themselves, especially when systematic training-data biases create unknown unknowns. It introduces a black-box, oracle-guided framework that partitions instances by features and confidence, then explores those partitions; experiments report effective discovery across varied tasks and conditions.
Problem
The paper addresses the gap in algorithmically discovering high-confidence model errors caused by systematic training-data biases when the model is treated as a black box.
Method
The framework combines Descriptive Space Partitioning, which groups instances by feature values and confidence scores, with oracle-guided explore-exploit search across partitions.
Results
The framework demonstrates effective unknown-unknown discovery across sentiment, subjectivity, and image-classification tasks and varied experimental conditions.
Takeaways & Limitations
Interpretable partitions can help designers understand discovered blind spots, prevent errors or silence risky predictions, and retrain models using discovered failures.
Takeaways & Limitations
The approach assumes available evidential features are informative enough to characterize subsets of unknown unknowns and operates without access to model internals or training data.
Abstract
from arXiv · showhide
Predictive models deployed in the real world may assign incorrect labels to instances with high confidence. Such errors or unknown unknowns are rooted in model incompleteness, and typically arise because of the mismatch between training data and the cases encountered at test time. As the models are blind to such errors, input from an oracle is needed to identify these failures. In this paper, we formulate and address the problem of informed discovery of unknown unknowns of any given predictive model where unknown unknowns occur due to systematic biases in the training data. We propose a model-agnostic methodology which uses feedback from an oracle to both identify unknown unknowns and to intelligently guide the discovery. We employ a two-phase approach which first organizes the data into multiple partitions based on the feature similarity of instances and the confidence scores assigned by the predictive model, and then utilizes an explore-exploit strategy for discovering unknown unknowns across these partitions. We demonstrate the efficacy of our framework by varying the underlying causes of unknown unknowns across various applications. To the best of our knowledge, this paper presents the first algorithmic approach to the problem of discovering unknown unknowns of predictive models.
Introduction
The paper frames unknown unknowns as high-confidence prediction errors caused by mismatch or systematic bias between training and deployment data. It proposes a black-box, oracle-guided method that partitions the search space and uses explore-exploit discovery.
- Motivation: Unknown unknowns are high-confidence model errors, unlike known unknowns, which are low-confidence errors.The model lacks awareness of unknown unknowns, making oracle feedback necessary for discovery.
- Motivation: Training-data biases or train-test differences can create concentrated failure patterns, such as white dogs classified as cats after the model learns color as a proxy.The example uses black dogs and white or brown cats in training, producing high-confidence errors on white dogs.
- Problem: The problem is to discover systematic unknown unknowns by querying an oracle for true labels under a fixed query budget.The predictive model is treated as a black box that returns labels and confidence scores without exposing its form or training data.
- Approach: The proposed method first groups test instances by feature similarity and model confidence, then uses oracle feedback in an explore-exploit strategy across partitions.The partitioning objective also provides compact, interpretable descriptions of discovered groups.
- Evaluation: Experiments across sentiment classification, subjectivity detection, and image classification support the framework’s effectiveness across biased-data and domain-adaptation settings.The evaluation varies base models from decision trees to neural networks.
Problem Formulation
The formulation seeks a budgeted sequence of oracle queries that maximizes the utility of discovering unknown unknowns while accounting for labeling cost. It operates on confidently predicted instances of a selected critical class.
- Objective: The objective is to find B instances whose oracle feedback maximizes cumulative utility for discovering unknown unknowns.The search is conducted over a test set using a limited oracle-query budget.
- Inputs: The black-box model receives feature vector x and returns a class label c′ and confidence score s, while the oracle supplies true labels and query costs.The formulation does not require access to the model’s functional form or training data.
- Search Space: The search space contains instances assigned to a designer-selected critical class c above a confidence threshold τ, where false positives are costly.The method is generic across classes but formulates the problem around a critical class requiring targeted discovery.
- Utility: The utility of querying x(t) rewards identifying an unknown unknown and subtracts γ times the oracle cost.The unknown indicator and cost are initially unavailable and are observed through oracle feedback; γ controls the trade-off.
Methodology
The framework assumes unknown unknowns cluster in feature space and uses descriptive partitions followed by an oracle-guided explore-exploit policy to discover them under limited queries.
- Assumptions: The method assumes bias-induced unknown unknowns occur in specific feature-space regions and that available features characterize different unknown-unknown types.Without informative features, learning from previously discovered unknown unknowns cannot outperform blind search.
- Descriptive Space Partitioning: Descriptive Space Partitioning groups instances with similar features and model confidence scores into interpretable partitions.Candidate conjunctions of feature, operator, and value tuples define covered instances, centroids, and mean confidence scores.
- Descriptive Space Partitioning: DSP selects partitions by combining within-partition similarity, across-partition separation, confidence-score distances, and description conciseness.Its objective uses weighted metrics over candidate patterns and associates concise descriptions with partitions.
- Descriptive Space Partitioning: The partitioning problem is a weighted set cover, so greedy maximum coverage-to-weight selection provides a ln N approximation guarantee.The algorithm continues until all instances are covered and resolves overlapping assignments using the closest centroid.
- Explore-Exploit Search: UUB treats DSP partitions as bandit arms, samples oracle-labeled points without replacement, and allocates queries using empirical utility and uncertainty.Because querying changes each partition’s remaining unknown-unknown concentration, the expected utility is non-stationary and motivates discounted UCB rather than stationary UCB.
Experimental Evaluation
The evaluation tests partition quality, bandit search, and the complete DSP+UUB pipeline across multiple datasets and baselines. DSP concentrates unknown unknowns more effectively than partitioning alternatives, while UUB generally achieves the lowest cumulative regret.
- Partitioning quality: DSP produced consistently lower entropy than k-means using features, confidence scores, or both, across all datasets.Lower entropy indicates that unknown unknowns are concentrated in fewer partitions.
- Partitioning quality: DSP entropy was 32-37% lower than its corresponding random-partitioning baseline across all datasets.Random counterparts preserved each algorithm’s number and size of partitions while reassigning instances.
- Bandit evaluation: UUB achieved the smallest cumulative regret on image data, sentiment snippets, and subjectivity snippets, while discounted UCB was slightly better on Amazon reviews.Discounted UCB was sensitive to its discounting factor, whereas UUB was parameter free.
- Overall methodology: The complete DSP+UUB pipeline achieved the least cumulative regret among all tested end-to-end strategies on the image dataset.This included random sampling, similarity-based methods, and uncertainty-based selection; the similarity baselines additionally used training data.
- Overall methodology: In the image qualitative analysis, UUB explored partitions associated with white and brown dogs more often because those patterns were absent from training data.The white-cat partition was selected less often because white-cat images were represented in training data and contained fewer unknown unknowns.
Related Work
Prior work frames unknown unknowns alongside dataset shift, active learning, and outlier detection. The paper distinguishes its setting by algorithmically guiding discovery without access to the predictive model’s training data.
- Unknown Unknowns: Earlier unknown-unknowns research used human input for identification but left exploration and discovery entirely to humans.The paper contrasts this with its assisted exploration approach.
- Dataset Shift: Dataset shift explains unknown unknowns as a mismatch between training and test distributions, motivating approaches such as importance weighting and online learning.The paper treats dataset shift as a common cause rather than as the full discovery solution.
- Active Learning: Active learning queries an oracle for selected labels to improve predictive models, whereas this paper uses oracle feedback to discover model failures.The distinction is the objective of querying rather than merely model retraining.
- Outlier Detection: Although unknown unknowns can resemble collective outliers, standard outlier methods are unsuitable because the proposed setting assumes no access to training data.This separates the paper’s problem from detecting deviations relative to an available training distribution.
Discussion & Conclusions
The paper presents a model-agnostic algorithm for discovering unknown unknowns without access to a predictive model’s functional form or training data. Its partitioning and bandit-based discovery can help designers understand and respond to model blind spots.
- The framework treats the predictive model as a black box and uses partitions plus bandit algorithms to find regions containing more unknown unknowns.It proposes algorithms for both partitioning the search space and sifting through the resulting partitions.
- Alternative query budgets could account for the total cost of oracle labeling rather than merely the number of queries.The paper also proposes handling settings where the utility of discovering a type of unknown unknown decreases as examples accumulate.
- Interpretable partition descriptions can help system designers understand discovered failures and devise responses such as silencing the model in risky partitions.Discovered unknown unknowns can also be used to retrain the predictive model so it can recognize and correct mistakes.
- Formal methods for exposing model and system limitations are important for deploying AI in open-world, high-stakes, and safety-critical settings.
Appendix
The appendix reports evaluations of the bandit framework and complete pipeline across sentiment, subjectivity, Amazon reviews, and image datasets. The figures vary the predictive model, including decision trees, logistic regression, SVMs, random forests, and neural networks.
- Figure 5 evaluates the bandit framework and complete pipeline on Sentiment Snippets using decision trees.
- Figure 6 evaluates the bandit framework and complete pipeline on the Subjectivity Dataset using decision trees.
- Figure 7 evaluates the bandit framework and complete pipeline on the Amazon Reviews Dataset using decision trees.
- Figure 8 evaluates the complete pipeline on an image dataset using logistic regression.
- Figure 9 evaluates the complete pipeline on the Subjectivity Dataset using random forests.
- Figure 10 evaluates the complete pipeline on Sentiment Snippets using an SVM predictive model.
- Figure 11 evaluates the complete pipeline on Amazon reviews using a neural network with five hidden layers.
- Figure 12 evaluates retraining with discovered unknown unknowns on Amazon reviews using a decision tree.