# On Learning Latent Models with Multi-Instance Weak Supervision

arXiv: https://arxiv.org/abs/2306.13796 · HTML: https://mlsanity.com/paper/2306.13796/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 69 references that are in the map.
- First posted on arXiv 23 Jun 2023.

## Builds on (most cited first, 30 of 31)

- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [A Semantic Loss Function for Deep Learning with Symbolic Knowledge](https://mlsanity.com/paper/1711.11157/) (2017)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Harnessing Deep Neural Networks with Logic Rules](https://mlsanity.com/paper/1603.06318/) (2016)
- [Progressive Identification of True Labels for Partial-Label Learning](https://mlsanity.com/paper/2002.08053/) (2020)
- [MIPaaL: Mixed Integer Program as a Layer](https://mlsanity.com/paper/1907.05912/) (2019)
- [Leveraged Weighted Loss for Partial Label Learning](https://mlsanity.com/paper/2106.05731/) (2021)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [Instance-Dependent Partial Label Learning](https://mlsanity.com/paper/2110.12911/) (2021)
- [Neural-Symbolic Integration: A Compositional Perspective](https://mlsanity.com/paper/2010.11926/) (2020)
- [Abductive Knowledge Induction From Raw Data](https://mlsanity.com/paper/2010.03514/) (2020)
- [Neuro-Symbolic Inductive Logic Programming with Logical Neural Networks](https://mlsanity.com/paper/2112.03324/) (2021)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [Learning from Aggregate Observations](https://mlsanity.com/paper/2004.06316/) (2020)
- [Structured Prediction Theory Based on Factor Graph Complexity](https://mlsanity.com/paper/1605.06443/) (2016)
- [Learning from Multiple Noisy Partial Labelers](https://mlsanity.com/paper/2106.04530/) (2021)
- [Backpropagating through Structured Argmax using a SPIGOT](https://mlsanity.com/paper/1805.04658/) (2018)
- [Learnability with Indirect Supervision Signals](https://mlsanity.com/paper/2006.08791/) (2020)
- [Estimation from Indirect Supervision with Linear Moments](https://mlsanity.com/paper/1608.03100/) (2016)
- [Understanding the Mechanics of SPIGOT: Surrogate Gradients for Latent Structure Learning](https://mlsanity.com/paper/2010.02357/) (2020)
- [Paired Examples as Indirect Supervision in Latent Decision Models](https://mlsanity.com/paper/2104.01759/) (2021)
- [On the Power of Deep but Naive Partial Label Learning](https://mlsanity.com/paper/2010.11600/) (2020)
- [Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models](https://mlsanity.com/paper/2302.04599/) (2023)
- [Learning with Latent Structures in Natural Language Processing: A Survey](https://mlsanity.com/paper/2201.00490/) (2022)

## Built on by (most cited first, 13 of 13)

- [BEARS Make Neuro-Symbolic Models Aware of their Reasoning Shortcuts](https://mlsanity.com/paper/2402.12240/) (2024)
- [A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts](https://mlsanity.com/paper/2406.10368/) (2024)
- [On the Independence Assumption in Neurosymbolic Learning](https://mlsanity.com/paper/2404.08458/) (2024)
- [Shortcuts and Identifiability in Concept-based Models from a Neuro-Symbolic Lens](https://mlsanity.com/paper/2502.11245/) (2025)
- [Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees](https://mlsanity.com/paper/2308.10487/) (2023)
- [Multi-Instance Partial-Label Learning with Margin Adjustment](https://mlsanity.com/paper/2501.12597/) (2025)
- [A Learnability Analysis on Neuro-Symbolic Learning](https://mlsanity.com/paper/2503.16797/) (2025)
- [Imbalances in Neurosymbolic Learning: Characterization and Mitigating Strategies](https://mlsanity.com/paper/2407.10000/) (2024)
- [Calibratable Disambiguation Loss for Multi-Instance Partial-Label Learning](https://mlsanity.com/paper/2512.17788/) (2025)
- [On Improving Neurosymbolic Learning by Exploiting the Representation Space](https://mlsanity.com/paper/2602.07973/) (2026)
- [Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning](https://mlsanity.com/paper/2604.23377/) (2026)
- [Neuro-symbolic Weak Supervision: Theory and Semantics](https://mlsanity.com/paper/2503.18509/) (2025)
- [Differentiable Logic Programming to Mitigate Reasoning Shortcuts in Neurosymbolic Systems](https://mlsanity.com/paper/2607.21185/) (2026)

## Abstract (arXiv)

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 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.