A Model for Combinatorial Dictionary Learning and Inference
<|reference_start|>A Model for Combinatorial Dictionary Learning and Inference: 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.<|reference_end|>
@article{blum2024a,
    title={A Model for Combinatorial Dictionary Learning and Inference},
    author={Avrim Blum, Kavya Ravichandran},
    journal={arXiv preprint arXiv:2407.18436},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.18436},
    primaryClass={cs.LG cs.DS}
}