Label Propagation for Learning with Label Proportions

ABSTRACT Learning with Label Proportions (LLP) is the problem of recovering the underlying true labels given a dataset when the data is presented in the form of bags. This paradigm is particularly suitable in contexts where providing individual labels is expensive and label aggregates are more easily obtained. In the healthcare domain, it is a burden for a patient to keep a detailed diary of their daily routines, but often they will be amenable to provide higher level summaries of daily behavior. We present a novel and efficient graph-based algorithm that encourages local smoothness and exploits the global structure of the data, while preserving the'mass' of each bag. 1. INTRODUCTION The whole spectrum of learning paradigms ranging from supervised to unsupervised learning is densely packed with different settings that have limited (or no) access to the true labels. For instance, in semi-supervised learning we have access to labels only for a subset of the dataset (usually small). Additionally, we can characterize the uncertainty in the labeling process when learning from noisy and partial labels [1, 2], using noise as a proxy in the former and a subset of labels per example in the later. Differently, in this paper we focus on learning from aggregated labels, also commonly referred to as Learning with Label Proportions (LLP) [3, 4]. In this setting, we assume the data comes in the form of bags of examples and for each of which we are given proportion of labels corresponding to each class.