Probably Approximately Precision (Hallucination) and Recall (Mode Collapse) Learning

Precision and recall are fundamental metrics in machine learning tasks where both accuracy and coverage are essential, including multi-label learning, language generation, medical studies, and recommender systems. In language generation, for example, hallucination reflects a failure of precision, where models output strings outside the true language, while mode collapse reflects a failure of recall, where some valid outputs are never produced. A central challenge in these settings is the prevalence of one-sided feedback, where only positive examples are observed during training. To address learning under such partial feedback, we introduce a Probably Approximately Correct (PAC) framework in which hypotheses are set functions that map each input to a set of labels, extending beyond single-label predictions and generalizing classical binary, multi-class, and multi-label models. Our results reveal sharp statistical and algorithmic separations from standard settings: classical methods such as Empirical Risk Minimization provably fail, even for simple hypothesis classes. We develop new algorithms that learn from positive data alone, achieving optimal sample complexity in the realizable case, and establishing multiplicative—rather than additive—approximation guarantees in the agnostic case, where achieving additive regret is impossible.