Disambiguation of weak supervision with exponential convergence rates
This work provides a theoretical foundation with strong convergence guarantees for disambiguating weak supervision, which is important for researchers and practitioners in machine learning seeking to reduce data annotation costs.
This paper addresses the problem of partial labeling in weakly supervised learning, where inputs are associated with a set of potential targets. The authors propose an empirical disambiguation algorithm and prove its exponential convergence rates under standard learnability assumptions.
Machine learning approached through supervised learning requires expensive annotation of data. This motivates weakly supervised learning, where data are annotated with incomplete yet discriminative information. In this paper, we focus on partial labelling, an instance of weak supervision where, from a given input, we are given a set of potential targets. We review a disambiguation principle to recover full supervision from weak supervision, and propose an empirical disambiguation algorithm. We prove exponential convergence rates of our algorithm under classical learnability assumptions, and we illustrate the usefulness of our method on practical examples.