Introduction
A critical challenge in machine learning is "distribution shift," where the data used for model development fails to represent the complexities of real-world application environments. Missing scenarios—such as specific weather conditions or lighting—can lead to silent failures in production. While standard techniques like anomaly detection or active learning exist, they often fail to identify missing patterns or clusters of data.
Researchers from Toyota Central R&D Labs, in a paper presented at AAAI-22, introduced Partial Wasserstein Covering (PWC). This framework systematically identifies "blind spots" by comparing a development dataset to a real-world application dataset, selecting a subset of data that best "fills the gaps."
Methodology
The core of the PWC approach is the optimization of a partial Wasserstein divergence. Unlike standard Wasserstein distance, which requires equal total "mass" between distributions, the partial version allows for comparing datasets of different sizes. This asymmetry is crucial: PWC ignores regions where the development set is already dense and focuses on sparse regions relative to the application data.
The authors proved that the PWC objective function is submodular. This property ensures that a greedy selection algorithm—picking the most beneficial data point iteratively—is guaranteed to achieve at least 63% of the optimal solution's performance. To handle the computational cost of solving Linear Programs (LP) for large datasets, the authors introduced "quasi-greedy" heuristics such as sensitivity analysis and C-transforms.
Key Insights and Comparison
PWC differs fundamentally from traditional data selection methods. While anomaly detection (e.g., Local Outlier Factor) identifies individual "weird" points, and active learning (e.g., coreset) focuses on points that maximize model accuracy, PWC targets representative samples of missing high-density regions. As shown in the comparison figure above, PWC identifies missing clusters (indicated by red triangles) that align with the gaps in the original distribution, whereas anomaly detection picks outliers and active learning selects points based on different criteria.
Experimental Results
The framework was evaluated across synthetic and real-world datasets:
- MNIST: In a scenario where the digit '0' was underrepresented (0.5% vs. 10%), PWC selected the missing digit with 71% frequency, significantly outperforming baselines.
- Driving Scenes: Comparing the daytime-heavy KITTI dataset against the diverse BDD100K dataset, PWC successfully flagged nighttime scenes as the primary missing component.
- Efficiency: The
PW-sensitivity-Ctransalgorithm achieved an 8.7x speedup over standard MILP approaches, demonstrating scalability for larger datasets.
Conclusion and Future Work
Partial Wasserstein Covering provides a robust mathematical foundation for dataset auditing. By focusing on distributional gaps rather than individual outliers, it offers a more systematic way to ensure model reliability. Future work aims to address scalability for million-scale datasets and integrate fairness constraints to ensure that even rare "long-tail" cases are adequately covered.
Summary updated