Sketching based Representations for Robust Image Classification with Provable Guarantees
Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang
Abstract
How do we provably represent images succinctly so that their essential latent attributes are correctly captured by the representation to as high level of detail as possible? While today's deep networks (such as CNNs) produce image embeddings they do not have any provable properties and seem to work in mysterious noninterpretable ways. In this work we theoretically study synthetic images that are composed of a union or intersection of several mathematically specified shapes using thresholded polynomial functions (for e.g. ellipses, rectangles). We show how to produce a succinct sketch of such an image so that the sketch "smoothly" maps to the latent-coefficients producing the different shapes in the image. We prove several important properties such as: easy reconstruction of the image from the sketch, similarity preservation (similar shapes produce similar sketches), being able to index sketches so that other similar images and parts of other images can be retrieved, being able to store the sketches into a dictionary of concepts and shapes so parts of the same or different images that refer to the same shape can point to the same entry in this dictionary of common shape attributes.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on3
- A Simple Framework for Contrastive Learning of Visual RepresentationsTing Chen, Simon Kornblith, Mohammad Norouzi, Geoffrey E. HintonICML 2020 · 24,064 citations
- Reformer: The Efficient TransformerNikita Kitaev, Lukasz Kaiser, Anselm LevskayaICLR 2020 · 2,878 citations
- MONGOOSE: A Learnable LSH Framework for Efficient Neural Network TrainingBeidi Chen, Zichang Liu, Binghui Peng, Zhaozhuo Xu et al.ICLR 2021 · 7 citations
Related papers
- Learning Manifold Patch-Based Representations of Man-Made ShapesDmitriy Smirnov, Mikhail Bessmeltsev, Justin SolomonICLR 2021 · 5 citations
- DeepFaceDrawing: deep generation of face images from sketchesShu-Yu Chen, Wanchao Su, Lin Gao, Shihong Xia et al.SIGGRAPH 2020 · 145 citations
- Polyhedral Complex Extraction from ReLU Networks using Edge SubdivisionArturs BerzinsICML 2023 · 12 citations
- Neural Star Domain as Primitive RepresentationYuki Kawana, Yusuke Mukuta, Tatsuya HaradaNeurIPS 2020 · 27 citations
- Learning Physical Graph Representations from Visual ScenesDaniel Bear, Chaofei Fan, Damian Mrowca, Yunzhu Li et al.NeurIPS 2020 · 88 citations
