On Learning Latent Models with Multi-Instance Weak Supervision
This work addresses a weakly supervised learning problem relevant to fields like latent structural learning and neuro-symbolic integration, offering theoretical insights but is incremental as it builds on existing partial label learning frameworks.
The paper tackles the problem of learning latent models with multi-instance weak supervision, extending partial label learning to handle deterministic transitions, and provides the first theoretical analysis with necessary and sufficient conditions for learnability and error bounds, supported by empirical results that reveal scalability issues.
We consider a weakly supervised learning scenario where the supervision signal is generated by a transition function $σ$ of labels associated with multiple input instances. We formulate this problem as \emph{multi-instance Partial Label Learning (multi-instance PLL)}, which is an extension to the standard PLL problem. Our problem is met in different fields, including latent structural learning and neuro-symbolic integration. Despite the existence of many learning techniques, limited theoretical analysis has been dedicated to this problem. In this paper, we provide the first theoretical study of multi-instance PLL with possibly an unknown transition $σ$. Our main contributions are as follows. Firstly, we propose a necessary and sufficient condition for the learnability of the problem. This condition non-trivially generalizes and relaxes the existing small ambiguity degree in the PLL literature, since we allow the transition to be deterministic. Secondly, we derive Rademacher-style error bounds based on a top-$k$ surrogate loss that is widely used in the neuro-symbolic literature. Furthermore, we conclude with empirical experiments for learning under unknown transitions. The empirical results align with our theoretical findings; however, they also expose the issue of scalability in the weak supervision literature.