A Model for Combinatorial Dictionary Learning and Inference
This work addresses the challenge of interpreting complex data in fields like computer vision, though it appears incremental as it builds on existing dictionary learning frameworks with new combinatorial assumptions.
The paper tackles the problem of decomposing structured data into simple components by proposing a combinatorial model for dictionary learning, showing that a 'well-structuredness' property enables learning latent components and addressing inference tasks like minimal component identification and robust explanation under adversarial conditions.
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.