We consider a weakly supervised learning scenario where the supervision
signal is generated by a transition function $\sigma$ 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 $\sigma$. 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.

本文针对监督信号由多输入实例上的标签的转移函数 σ 生成的弱监督学习方案，提出了多实例偏标签学习（multi-instance PLL）问题，并给出了对于可能的未知转移 σ 的第一理论分析。通过使用一种在神经符号学中广泛使用的顶部 - k 替代损失，我们推导了基于 Rademacher 的错误界限，并进行了实证实验。