Lune

NeurIPS2022Top-tier venue

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. A Simple Framework for Contrastive Learning of Visual RepresentationsTing Chen, Simon Kornblith, Mohammad Norouzi, Geoffrey E. HintonICML 2020 · 24,064 citations
  2. Reformer: The Efficient TransformerNikita Kitaev, Lukasz Kaiser, Anselm LevskayaICLR 2020 · 2,878 citations
  3. 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

  1. Learning Manifold Patch-Based Representations of Man-Made ShapesDmitriy Smirnov, Mikhail Bessmeltsev, Justin SolomonICLR 2021 · 5 citations
  2. DeepFaceDrawing: deep generation of face images from sketchesShu-Yu Chen, Wanchao Su, Lin Gao, Shihong Xia et al.SIGGRAPH 2020 · 145 citations
  3. Polyhedral Complex Extraction from ReLU Networks using Edge SubdivisionArturs BerzinsICML 2023 · 12 citations
  4. Neural Star Domain as Primitive RepresentationYuki Kawana, Yusuke Mukuta, Tatsuya HaradaNeurIPS 2020 · 27 citations
  5. Learning Physical Graph Representations from Visual ScenesDaniel Bear, Chaofei Fan, Damian Mrowca, Yunzhu Li et al.NeurIPS 2020 · 88 citations
Dusk over the sea between two cliffs drawn in fine vertical lines