Timezone: »

Sketching based Representations for Robust Image Classification with Provable Guarantees
Nishanth Dikkala · Sankeerth Rao Karingula · Raghu Meka · Jelani Nelson · Rina Panigrahy · Xin Wang

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #942

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 non-interpretable 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.

Author Information

Nishanth Dikkala (Google)
Sankeerth Rao Karingula (University of California San Diego)

I graduated with a PhD majoring in Machine Learning and Data Science at University of California San Diego. I am currently looking for opportunities to work as a Machine Learning Researcher.

Raghu Meka (UCLA)
Jelani Nelson (UC Berkeley)

Jelani Nelson is Professor in the Department of Electrical Engineering and Computer Science at UC Berkeley. His research interests include sketching and streaming algorithms, dimensionality reduction, compressing sensing, and randomized linear algebra. In the past he has been a recipient of the PECASE award, a Sloan Research Fellowship, and an NSF CAREER award. He is also the Founder and President of a 501(c)(3) nonprofit, “AddisCoder Inc.”, which organizes annual summer camps that have provided algorithms training to over 500 high school students in Ethiopia (see addiscoder.com).

Rina Panigrahy (Google)
Xin Wang (Google)

More from the Same Authors