# A Model for Combinatorial Dictionary Learning and Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 26 Jul 2024.

## Builds on (most cited first, 8 of 8)

- [Adversarial Examples for Semantic Segmentation and Object Detection](https://mlsanity.com/paper/1703.08603/) (2017)
- [Universal Adversarial Perturbations Against Semantic Image Segmentation](https://mlsanity.com/paper/1704.05712/) (2017)
- [Enhancing Robustness of Machine Learning Systems via Data Transformations](https://mlsanity.com/paper/1704.02654/) (2017)
- [Reducing Adversarially Robust Learning to Non-Robust PAC Learning](https://mlsanity.com/paper/2010.12039/) (2020)
- [Efficient Representations for Life-Long Learning and Autoencoding](https://mlsanity.com/paper/1411.1490/) (2014)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Certified Defences Against Adversarial Patch Attacks on Semantic Segmentation](https://mlsanity.com/paper/2209.05980/) (2022)
- [Lifelong Learning in Costly Feature Spaces](https://mlsanity.com/paper/1706.10271/) (2017)

## Abstract (arXiv)

We are often interested in decomposing complex, structured data into simple components that explain the data. The linear version of this problem is well-studied as dictionary learning and factor analysis. In this work, we propose a combinatorial model in which to study this question, motivated by the way objects occlude each other in a scene to form an image. First, we identify a property we call "well-structuredness" of a set of low-dimensional components which ensures that no two components in the set are too similar. We show how well-structuredness is sufficient for learning the set of latent components comprising a set of sample instances. We then consider the problem: given a set of components and an instance generated from some unknown subset of them, identify which parts of the instance arise from which components. We consider two variants: (1) determine the minimal number of components required to explain the instance; (2) determine the correct explanation for as many locations as possible. For the latter goal, we also devise a version that is robust to adversarial corruptions, with just a slightly stronger assumption on the components. Finally, we show that the learning problem is computationally infeasible in the absence of any assumptions.