Sketching based Representations for Robust Image Classification with Provable Guarantees
Authors: Nishanth Dikkala
Sankeerth Rao Karingula
Raghu Meka
Jelani Nelson
Rina Panigrahy
Xin Wang
Venue: NeurIPS 2022 Accept (2022)

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

Sketching based Representations for Robust Image Classification with Provable Guarantees
Nishanth Dikkala" Google Research sishanthd@google..o com
Sankeerth Rao Karingula"
Raghu Meka" UC Los Angeles
Google Research saukeerch1728@mail.e
raghuvarchan@@gail.cc com
Jelani Nelson"
Rina Panigrahy Google Research
Xin Wang" Google Research
UC Berkeley minil Sanilek@gmaill com
rinapggoogle.com com
wanxin@google.cm com
Abstract
How do we provably represent images succinctly so that their essential latent attributes are correctly captured by the representation 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 interpretable ways. In this work we theoretically study synthetic images that are composed of union intersection of several mathematically specified shapes using thresholded polynomial functions (for e.g. ellipses, rectangles). We show how produce succinct sketch of such image that the sketch "smoothly" maps to the antent-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 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 parts of the same or different images that refer the same shape can point the same entry in this dictionary of common shape attributes.
high level of detail
1 Introduction
first step in many computer vision systems is to learn a succinct representation of an input image (or set of images) which retains all the useful information about the image. Today, there several deep networks that can take images and produce useful embedding representations [4, [ 2) Deep approaches extremely complex and hard to understand. Moreover, for the tasks they aim to solve, it is unclear if we need such non-interpretable (6. M approach which is also known to be very brittle (l77). Previously hand-crafied feature construction approaches such as SIFT [ used to dominate. These were also heuristic and not theoretically guaranteed to work. In addition, they focused heavily on local features which might not be good understanding important global information such as shape.
Ideally would like representations of images to be such that they capture the essential latent semantic attributes the image. If the images are produced by some generative process then the latent attributes correspond to parameters used in the generative process. Further, given large collection of images, can be desirable to create a dictionary or an index of commonly occurring latent attributes so that each image may be viewed To study this problem theoretically, we use a simple generative process for producing images using
of pointers into this global dictionary.
Alphahetical author order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

polynomial functions. By taking thresholded versions of polynomial functions one can generate simple shapes such as circles, ellipses. hyperbolas and by taking intersections of such functions one can generate polygons such as rectangle, triangles etc. By taking union of such intersections one can generate fairly complex images in fact, much of computer graphies is generated using such principles.
Since this process is fully formalized, it is now feasible to study questions such as: Do deep networks learn representations that are isomorphic to the parameters that generated the image? While today's deep networks do not provably have such properties about being able to recover the polynomial coefficients used in an image, we provide a method that can produce a sketch that is provably equivalent to the parameters that generated the image. While our sketch is not identical to the polynomial coefficients, we show that it is equivalent in smooth manner - that is there exist smooth functions mapping one to the other and vice versa. Further our sketches can be easily used to reconstruct the original image which means that our representations are robust across different types of shapes.
The main idea behind our sketching algorithm is fairly simple and uses a locality sensitive hash (LSH) table. We partition the pixels of the image into regions based on the LSH and train specific parameters within each hash bucket so that those parameters can be used to reconstruct that region of the image. By using few such LSH tables and training parameters in those buckets we obtain a succinct sketch that is able to provably reconstruct the image. This provides several advantages: 1) our sketches are invertible, that is one can reconstruct the original image: 2) they are semantically meaningful since they are isomorphic (using a smooth transform) to the latent parameters. This in turn means that any classification of shapes that can be done using the latent parameters can also be done using LSH sketches. If we think of each shape type (such as ellipse) as separate region in coefficient space that is well separated from other regions by a polynomial threshold function (PTF) over the coefficient vector, then by training such PTF classifier over the sketches of such images we obtain a robust classifier for such shapes. In fact in the coefficient space (which is homeomorphic to the set of produced sketches), we can view each shape type itself as an intersection of PTFss and thus the above tools for representing shapes in images could be used for representing shape-types in sketch space.
Our sketches also have the nice property that the sketch of a part of the image can be easily obtained as some of the dimensions in the full sketch. This means that one can create secondary LSH index of sketches for different parts and different shapes in the image over a large collection of images. This gives a global dictionary of shape attributes so that each image merely becomes a set of points into this global dictionary. If we think of each shape-type as a disjoint compact region in coefficient space, then each contiguous set of buckets in this secondary index forms shape-type and thus this secondary index can be viewed as a dictionary of shape-types.
We show the following results. An image can be viewed as map from pixel location to pixel values.
Proposition 1.1 (Informal, Image sketches and their properties).
1. Low degree polynomi- als: Given grayscale image where the map from pixel position to the pixel value is a degree polynomial, we construct sketch vector of size Oss) that is able to reconstruct the image (see Theorem H.4). Further the coefficient vector of the polynomial can be recovered by applying linear transform over the sketch vector (see Appendix).
2. Polynomial threshold functions: the image is PTF where the underlying polynomial is of degree s we can get a sketch vector of size (8)) that can reconstruct the image (TTheore 5.4)
3. Parametric isomorphism:
The sketch is "isomorphic" to the original parameters used in producing the image. Furthermore, the transform from the coefficient parameters to the sketch is "smooth" " (continuous and differentiable) (Lemma 5.5); whereas for PTFs the image itself (or a random projection of it) is not differentiable in the underlying coefficients.
4. Union/Intersections of PTFs: A union of intersection of ks PTFs each of degree at most can be converted into a sketch of size poly(ks) from which the image can be reconstructed. (claim 6.2
5. Local property: By projecting to specific dimensions, for any patch in the image one can obtain sub-sketch from the sketch corresponding to that patch. One can create an index of
2

---

patch sketches that can be used to retrieve patches from other images that are similar to given patch (claim 6.3
Theorem 1.2 (Learning Shape concepis, see claims 7.3 1.4) Assuming shapes (such ellipse) can be expressed as a region in coefficient space, and that each such region can be expressed as a PTF over the coefficient vector, and that these regions well separated, our sketching methods can be used build a robust high margin classifier for shapes that identifies these regions in sketch space and classifies an image sketch to its shape.
1.1 Related Work
There is tremendous amount of work on building features specifically for learning images similar to the ones we consider in the computer vision literature (for instance, SIFT features [.]. The literature is too vast to survey here see [[8] and references therein for instance. However, by and large while these methods are empirically well-understood they do not come with rigorous guarantees in terms of compressing images.
Learning good representations has also been posited key reason for the success of deep neural networks [2] Deep representations of complex inputs such as text and images are often used to compare the underlying objects and transfer to new classification problems 20 16. However there is little theoretical understanding of the neural representations computed by such networks.
Locality sensitive hashing originally introduced by X in the context of speeding up nearest- neighbor computations but has since found many applications in sketching in the streaming com- munity. The LSH framework has been applied to deep learning and vision settings well but approach tangential to these. In particular, it has mainly been used to speed up computations of various neural network architectures (see e.g.. M 3. We also study more general paradigm recursive LSH based sketching. We also refer the reader to [99 for a survey of LSH.
There is also extensive work on learning PTFs and intersections of PTF' (e.g., D12 10 III in the
high-dimensional setting under distributional assumptions. We also have distributional assumptions however the focus is on the very low-dimensional setting and dealing with an unsupervised learning problem with emphasis on computing compact representations.
2 Setup and Preliminaries
We focus on inputs which are 2D grayscale images which are square in shape for simplicity. All our algorithms and results easily extend non-grayseun grayscaae rectangular images as well. We view an image I as a real-valued function continuous 2-D domain I [0, 1J [0, I] mapping positions within a rectangular window to grayscale values.
Sampling Pixels of an Image: Given an image, we will assume the learner has n evaluations of points within [o, 1]2 sampled uniformly at random. That is we are given (ri,=));= U[0, 1 These points can be thought of as pixels in digital representation of the image. The vector of pixel values the sampled positions is denoted by v [0, 1]".. We denote these points as samples of 1.
Underlying Generative Process for Images: We will model images as being the outputs of a generative process. We will consider the following simple generative processes.
Definition 2.1 (Polynomial Images). The map I [0, 1]2 - [0,1] is a degree-s polynomial in variables (2)
Definition 2.2 (Thresholded Polynomial Images). Given a polynomial P(æ), a polynomial threshold function (PTF) fp : RR + {0, 1} is defined as fp(z) = [(P(x) 2 0}. A thresholded polynomial image is PTF on 1|2.
Rather than bounding the degree explicitly, we sometimes impose a 'smoothness' constraint on the polynomial generating image.
Definition 2.3 (y-Smoothnesss, We say a function f: [o, 1]2 + [o, ymmooth k (k2 () + 1) < 22 where Ck, are the coefficients of the Fourier series of ff restricted to [0, 2
3

---

We will also talk about classes of images which together can be thought of as constituting a concept. We assume that class of images forms a contiguous region in the underlying parameter space which generates our image.
Locality Sensitive Hashing We will construct our image sketches using form of hashing which is sensitive to distance called locality sensitive hashing which is a form of hashing defined on metric space where nearby points hash to same buckets and far away points hash to different buckets.
Originally introduced for solving the approximate of exact Nearest Neighbor Search problem, LSH has since found applications in many other problem areas. Next we define the specific LSH family we use.
Definition 2.4 (Hyperplane LSH Family for Euclidean Distance). The hyperplane LSH family Hillla (As, w)) for the metric space (R&4, [1-1[2) is one where each hash function is defined by set of hyperplane inequalities (we use axis-aligned hyperplanes in some settings). We sample random is independent normal variable. In addition we sample 6, ~ fnif E] independently for E [k]. Given a hash function h E HIllla (k, w) defined
directions 01,- Pi....;0. dg where each coordinate of each a;
by the hyperplane directions {as) and shifts (b.) h(x) = (L
a, 2+b;
D
i=1
3 Representation Learning using LSH
A natural assumption about images is that how quickly the pixel-values change with respect to distance in pixel locations conveys important information for most image-process paogee-pcssssing tasks. Convolutions erucially exploit this by using the same filter across various patches. We propose to exploit this by using LSH.
Definition 3.1. Simple LSH-Sketch of an Image I. Given n uniformly random samples of we define the Simple LSH-Sketch SI; k, w) of an image I as follows.
1. Using m random functions {f E Hillaa (ks, w), map the n pixel positions to correspond- ing hash buckets.
2. For each hash function fy. we allow each hash bucket to store a scalar value. We denote the vector of the resulting bucket values by 2 E RR where K is the number of hash buckets. The learnt value in each bucket will act as an approximation to the image in the region covered by that bucket.
Effectively, the Simple LSH sketch is a piecewise regression model where the pieces are determined by partitions induced by LSH. It can also be considered as form of smoothening of the image T (analogous to Gaussian smoothening).
Image from its Simple LSH-Sketch Given Simple LSH- Sketch S(I; m, k, w), we can reconstruct an approximation of as follows. For any position (2), the reconstructed pixel value is defined the average of the values stored in all the buckets that the point (I1, x22) hashes to under the m hash functions constituting the sketch. Let K denote the total number of buckets per each hash function. For the pixel values the train locations = [0, 1]", since the reconstruction is a linear operation can also be represented in matrix form
Procedure for Reconstructing
ATz, where z (21, ........ Zm E R is the vector of all bucket values concatenated and A E pgnkxn is matrix mapping pixels buckets such that
A(i if (2f 2 maps to bucket i, A(i,j) = 0 otherwise.
Computing the Optimal Bucket Values Given the above procedure to reconstruct the image, we now define the learning problem which we solve learn the bucket values z, for each hash function in the Simple LSH-Sketch. The values stored the buckets aim to minimize the reconstruction error between the predicted pixel values and the true pixel values Our goal is to minimize the reconstruction error on randomly drawn test pixel.
C(u, = E
x-010.11 [e(u(x)
(I)

---

where f(u, v) = (u - 2)2 for polynomial images and 8(u, v) = max(0, 1 - ww/e) (hinge loss) for PTF images. To achieve this goal, we minimize the fg-regularized training loss C,, R == llu,, 0/) + 2|
3.1 Multi-Level LSH Sketch (LSH-DAG Sketch)
The Simple LSH-Sketch works well for simple images defined using polynomials. For more complex images, it helps to build multi-level LSH-Sketch defined using underlying directed acyclic graph (DAG). We call this the LSH-DAG sketch.
Definition 3.2 (LSH--AA Sketch). A function class F (J [m]² - JR. a DAG where for every internal node the outgoing edges are labeled according to the indices of buckets of a function from LSH family, In addition, the nodes with no outgoing edges (i.c., leaves) are labeled with functions fe [0, 1 + [0, that are obtained the threshold of degree & polynomial on the input.
Recursive LSH sketching algorithm: Algorithm D describes how to compute good multi-level LSH-Tree sketch of an image. At high level, it computes LSH-Tree where regions that are hard to learn at certain resolution are recursively expanded into smaller regions to get a Tree of sketches.
Algorithm Recursive Sketching Subroutine. Image or the region in a bucket may optionally be centred before sketching
1: Given a function f [0. 1J2 + 1] pick a resolution and map the pixels to LSH buckets with constant bucket width parameter
2: Train a sketch in the buckets to best predict the pixel values in the image restricted to the region mapping to that bucket
3: Mark a bucket as invalid the prediction error for the pixels mapping to the bucket is not negligible
4: Recursively compute a finer LSH sketch the bucket marked invalid by dividing the region into smaller regions with resolution r/2 (do not expand buckets whose region is fully covered by other valid buckets).
Merging near duplicate sketches in the LSH-Tree to get an LSH-DAG: we can merge sub- sketches and even entire sub-trees that near duplicates get DAG strueture instead of recursive tree by using secondary LSH table of sketches. Inputs: bucket of a recursive LSH sketch, A global secondary LSH table of sketches H sketches
Algorithm 2 Recursive merging into LSH table of sketches
1: If the bucket B is marked valid (thus leaf level bucket that is not further expanded) then store the sketch the bucket into LSH table Hakotches- And replace the bucket contents by pointer to the index of the entry in Haketches
2: If a bucket B is not a leaf level bucket (so it is expanded into further buckets) then recursively merge the sketches in each of the component buckets. Look at the vector of merged sketches in the component buckets and hash to store this vector into Haketekes and store only the index in B
4 Warm-up: Sketching Low-Complexit Polynomials
Polynomial images are simpler sketch. For instance, random projection of the image of degree-s polynomial to O(s²) dimensions gives all desiderata, (i) reconstruction. (ii) small sketch, (iii) recoverability of parameters, (iv) smoothness
function of polynomial coefficients. However, will be beneficial to see how we can use LSH to sketch polynomial images as the analysis will help extend to more complex images in later sections. In fact, will show that LSH works not only for sketching degree- bounded polynomials but for polynomials of arbitrary degree as long as their Fourier spectra appropriately bounded described in Assumption 4.1
Assumption 4.1. We assume that the polynomial p(#1, 22) generating the image satisfies:
5

---

1. Suppose 2(21, = 2 C,. exp(2rikz1) exp(2vila))) is the Fourier series of p. We
assume that Lk 1, 1)(( + +) S n²2 for some constant ?.
2. In the region [0, 1]2, the Lipschitz constant of p(z1, is bounded by A.
Note that our assumption the Fourier spectrum of p is satisfied by bounded polynomials with bounded degrees in particular.
We start by first studying the limiting behavior of the axis-aligned LSH-Sketch as the number of hash functions m + DC.
Definition 4.2 (Infinite LSH-Sketch). Given an image I, sample m hash functions from HL1 (m, w1, W2) for W1, W2 ~ U[1/4,1/5 1/2] and we analyze the properties of the resulting sketch
In this scenario, the metric we focus on for reconstruction the mean squared error (MSE), Given the LSH Sketch (11; m, wi, W2), let K < [1/w1]
| x [1/wa] denote the total number of buckets per hash function. Let E Rmn xn denote the mapping from the n sampled pixel positions {(1), or3 to buckets. We minimize
A z - v 1 A ||
We can obtain a closed form expression for the à which minimizes the above objective. 2 A(A A + A1,))-vv
Next, we observe that lo A A is a shift-invariant smoothening operator (convolution matrix) which attenuates higher frequencies the image signal.
Lemma 4.3. lit0m=400 A A is shift- ihift-invariant (convolution) matrix which acts also smoothen- ing matrix. In the Fourier space, convolution of a signal with limm->x A A, corresponds to pointwise multiplication of the Fourier spectrum of I given by [(k,)) with sinc(wn k32² sinc(w?l²).
This realization from Lemma 4.3 suggests a Fourier style analysis of the solution 2. Due to Assump- tion B.I as well we can focus on the first few Fourier coefficients of the image and ignore the rest. This enables us to show the following.
Theorem 4.4 (Informal). With probability z 0.9, for
O(7A/ poly(c)) samples,
Ex-t/o.113 [(u(x) - [xx))²] < (ee).
In addition to Theorem 4.4 we also show that the resulting sketch has continuous and bounded derivatives with respect to the 9 (Lemma B.13 and that there exists linear transformation such that R2 = f with high probability (Lemma B.14).
Finally, we show how above properties.
obtain sketch with finite which approximately still satisfies the
Remark 4.5. [sketches are resilient to sampled pixel positions] The above methods let us produce sketches of smooth images from sampling few pixels in the image. The sketches only need random sampling and we can compare images even when different random pixel positions are sampled.
5 Sketching Thresholded Polynomial Images
Similar to the polynomials setting, assume that the Fourier spectrum of the underlying polynomial which we threshold is well-behaved. In addition the previous assumptions we had in Section F we also assume additional condition about the boundary of the PTF. First present definition.
Definition 5.1 (e-Boundary of a PTF). The region where the absolute value of the underlying polynomial is <.c. c.
The assumptions we make about our PTF image are given next. Assumption 5.2.
1. Satisfy Assumptions 4.
2. The total probability mass of the e-boundary of p is at most O(e). For example, this holds for an ellipse represented by ax?² by2 when Va² 12 for constant
We see how the sketch we construct can accurately reconstruct a PTF image. Due to the binary nature of the true pixel values, objective such as cross-entropy the hinge loss is found to

---

be more appropriate for computing the optimal bucket values. In particular, we use the following parametrization of hinge loss. For E {0, 1}, and for y E R, (e(0. v) - max 0.
9y
Similar to Section + we show that the sketch we get here has a low reconstruction error. In particular, we will only make errors near the boundary the PTF and we can control this error by increasing the number of buckets per each hash function. In addition, we show that the manifold containing the sketches is Lipschitz and has bounded derivatives with respect to the coefficients of p.
5.1 Properties of The Infinite Sketch
As in Section 1 begin by analyzing the sketch as cc. We first observe that + reconstruction procedure allows us the flexibility to express arbitrary smooth functions over a finite numbe of pixels.
Lemma 5.3. As m - co, any function f which is Lipschitz and has bounded derivatives can be expressed as A where z are the bucket values we learn.
Lemma 5.3 allows to argue that can get small reconstruction error for PTF images.
Theorem 5.4 (Informal). Constructing infinite sketch such that each hash function uses O(1/e) buckets with = ((xA/ poly(c)) samples will yield solution with expected 0/1 o/oorrccontrrucionn error at most Ö()).
A short overview of the proof of Theorem 5.4 is as follows. Recall that the hinge loss optimize is max(0, 1 uv/e) where U E {0, 1] is the true pixel value and u is the predicted reconstruction value. Note that this loss is O when reconstruction such that the reconstructed value at a pixel u is equal to the underlying polynomial value at This reconstruction will set |wv] > c for outside the c-boundary and hence incur 0 hinge loss there. With our assumption on the boundedness of c-boundary of we get that this solution incurs train reconstruction loss of (c) implying that the optimal solution also incurs loss of (e)). The last step is generalization bound to ensure that this behavior approximately holds for a randomly sampled test point as well.
Given infinitely many hash functions,
realize
5.2 Smoothness
We show that the sketch we compute an analytically smooth function in terms of the latent parameters used to generate the image. Note that this property is not true if just think of the mapping to the image itself. That is, say we have a degree d polynomial specified by coefficient parameters O. Let Va denote the image generated by the PTF represented by coefficients 0. The mapping 0 + Ve is non-differentiable whereas the mapping 0 + S(ve; m, H) is an analytic function with derivatives bounded independent of the number of pixels. This is a desirable property as implies that any nice space of images whose latent parameters form low-dimensional manifold will also be mapped to a -indesenniooaal manifold in the sketch space. Note that this not true for the image mapping as it preserves continuity but not differentiability.
Lemma 5.5
The infinite sketch produced is smooth in the PTF parameters and vice versa. If we use the image directly as the sketch then it is not smooth (first derivative not defined).
The main idea behind the proof is that as the sketch the arg min of convex optimization problem, we can compute derivatives of the arg min with respect to the parameters of the objective function using the implicit function theorem. See C.0.2 for the details of the proof.
As in Section we can again go from the infinite sketch to a finite sized sketch with both a small reconstruction and (approximate) smoothness. Details given in the supplementary material.
Intersection of PTFs
Learning rectangle We will now show how to construct recursive sketch of (constant-sized) rectangle image via our algorithm [ We will first focus only on reconstruction. Instead of keeping a scalar in each bucket, will keep sketch vector within each bucket that can be used to reconstruct
7

---

the region that maps to that bucket. For simplicity, let us say we use an LSH that does say square tiling with random offset (shift) where each bucket is a square of side length say 1/c. This would give about ea buckets. Within each bucket we run PTF learning algorithm giving ((d) sized sketch that can learn any edge that can be expressed as a PTF of degree d as long as the tile intersects purely with at most one side of the rectangle.
Any tile-sketch that does not predict its content with high accuracy is marked as invalid and we recurse further by dividing into smaller tiles and to compute sketches at higher resolution. We will only need to recurse to depth log n to go to the resolution of n pixels. Note that we can also amplify the coverage of valid tiles by using a constant number of random shifts of such LSH tilings and in this case we need recurse into a tile only if is not fully covered by tiles (from the different shifts) marked as valid. In expectation at least a constant fraction of each side will be covered by some tile that predicts correctly. The same idea works for an intersection of PTFs and also to a union of an intersection of PTFs. For the union of intersection of & PTFs if the boundary curve based on PTF appears multiple times along the boundary split by intersections we will count them separately for each appearance. This proves the following claim.
Claim 6.1. W.h.p. recursive LSH sketch of depth Ollogn) and size O(log n) will be able to reconstruct the rectangle. Wh..p. a recursive LSH sketch of depth (log n) and size Odk logn) will be able to reconstruct intersection (or union of intersection) of k PTTs of degree d each.
We will see how to further simplify these sketches by merging regions that have similar sketches.
Stable sketches: We will call sketching method stable if for smooth function, by sketching the function in a constant sized interval (or patch) we get the same sketch regardless of the interval (patch) position. By modifying the A matrix (for e.g. based on the polynomial kernel) we can get stable sketches (see Appendix).
Hashing sketches to merge duplicates: We can compress the LSH sketch by merging all near duplicate copies of the sketches from different parts of the same curve - this can be done by further hashing the sketches into another secondary LSH table of sketches and storing only one copy there and keeping only pointers to that table. This can also be done across different images; so the same curve being repeated across images gets replaced by a pointer. This merging can also be done recursively bottom up in a recursive fashion where each patch sketch at a leaf level is replaced by a pointer into the secondary LSH table and going up recursively an entire subtree may be replaced by a pointer so that all copics of a subtree point to the same entry in the global LSH table of sketches. Thus this global LSH table becomes a 'dictionary of sketches of shapes'. This gives us the following.
Claim 6.2 (Reconstruction). By using stable sketches and merging similar sketches, w.h.p. the above sketch can be compressed to size (dk: + k log n) for intersection/union of & PTFs of degree d each.
Claim 6.3 (Indexing). One can use an LSH table as an index of tile-sketches to find shifted copies of the same shape (specified by an intersection of PTFs). Further for PTF, only a patch containing part of the PTF is sufficient to index and lookup the shape.
7 Learning shapes as concepts
So far we have been viewing images as maps from pixel-locations to pixel-colors. However the same view can be applied to coefficient vectors or (sketch-vectors that can be viewed as smooth transforms of coefficient vectors) for given shape type (such as ellipses). For simplicity let us just think of shapes in terms of their coefficient vectors that are d-dimensional assuming each image corresponding to shape can be specified by PTF of degree d. Each shape-type can now be viewed as a region in the coefficient space. For example all ellipses can be casily shown to be representable as intersection of two PTFFs in coefficient space.
We proved that the transform from coefficient to sketch space is smooth and invertible; we will extend this to the following assumption. (Note that for PTFs there is linear map from the sketch vector to the coefficient vector it maps to.)
Assumption 7.1. We will assume that transform from the sketch space to the coefficient space is analytic and all derivatives are bounded by some constant. This immediately implies that any low degree polynomial in the coefficient space can be approximated by a low degree polynomial in the sketch space.
8

---

Assumption 7.2 (Model of Shapes in Real-Woridy, A shape is defined by region (open/closed body with volume) in the coefficient space. These regions are non-overlapping and have a constant margin separating regions corresponding to any distinct shapes. We will assume each region is an intersection of PTFF.
This means that constant margin PTF separating two shape-types remain separable by a constant margin PTF in the sketch-space. This gives the following theorem.
Claim 7.3. Given two shape-types assuming that there is (robust) high margin PTF that separates them in coefficient space, polynomial kernel can be used to separate the two regions with a high margin in sketch space.
Forming a dictionary of shapes: In fact, we will show how the recursive LSH algorithm described for classifying pixel-locations can actually be applied classify coefficient vectors. One difference here is that we only get +vely labeled sketches that correspond to some shape in an image; however this is not an issue as we can still study this set of sketches by treating them as "pixels" level and handle the absence of -vely labeled pixels by randomly sample points as -ve labels (see Appendix). Even for an unsupervised set of images, each contiguous region in coefficient space can now be treated as new latent shape label and its boundaries can be specified in a robust manner to precisely characterize the region spanned by the sketches corresponding to that shape. This gives the following claim.
meta
Claim 7.4. The recursive LSH sketch algorithm when applied to sketches of images can be used to decompose images of shapes into distinct concepts (regions) in sketch space by learning a union of intersection of PTFs. Even when images are not labelled, we can treat each contiguous region in sketch space distinct latent concept and characterize the region robustly as intersection of PTFs.
8 Experiments
We demonstrate the smoothness of sketch vectors in the latent parameters used to generate the image in this section. As shown in Lemma [.5] the infinite sketch is smooth as function of the PTF parameters. Here we further demonstrate that finite sketch vectors also exhibit similar smoothness as we vary the latent parameters.
In particular, we consider the following three functions that generate ellipses, hyperbolas and rectangles images, respectively: f1 = (x x²)² ( /22 (y y 12 /b² 1, f2 y) (x /a² (y- (y-ye) //22 1, fa(z,, y) = -Is--__ (2. y) I1- we (a, (z. y We sample (æ. y) uniformly in 00, 28] x [0, 28) and generate pixel values in {0, 1} with the above functions. The LSH network is trained to predict the correct pixel values and the trained LSH tables are the sketches for the corresponding images.
To examine the smoothness of the sketches, we apply projection of the sketches to random direction. We also obtain a "raw image" from the functions by computing the pixel values on a uniform 56 x 56 grid in [0, 28] x [o, 28). and compare with the random projection of the raw images. Examples of such random projections are shown Figure I In Table D we calculate the average absolute discrete derivatives of the projection with respect to the parameter, i.e. Σ, [Proj(Us+ Proj(::)) Σ, 1- where ii is the raw image vector (sketch vector) corresponding to parameter 0,- The sketch vectors have much smaller average absolute discrete derivatives (in Figure [ the sketch projections are almost flat, compared to large variations in the image projections), indicating a smooth dependency of the sketch vectors on the PTF parameters in the finite dimensional sketch case.
Table I: Average absolute discrete derivative for varying function parameters
Shape
Raw image
Sketch
cllipse
12.22
2.29
hyperbola 18.31
2.63
rectangle
10.25
1.32
We also performed an initial set of experiments on using sketches for image classification. In this experiment, we sampled 10% of the train/test split of the fashion MNIST dataset, and obtained LSH
2 LA is the indicator function of set A.

---

Barden inferiinn al
See pocktiee aude Foat
(a) Ellipses
(b) Hyperbolas
(c)
Rectangles
Figure 1: Examples of ID random projection of raw images versus sketches. Projections of sketches have smaller variations when change the parameters in its defining polynomials.
sketches of the images. We then train a layer neural network (with a hidden layer of size 128 and ReLU activation) to classify the sketches. We found 100% train accuray and 79.3% test accuracy for this task. This demonstrates that sketches have the potential to be used in practical applications.
10

---

References
[1] Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in Neural Information Processing Systems, 31, 2018.
[2] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions pattern analysis and machine intelligence, 35(8):1798- 1828, 2013.
[3] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. International Conference on Learning Representations, 2020.
[4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607. PMLR, 2020.
[5] Charles I. Epstein. How well does the finite fourier transform approximate the fourier transform? Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences,
2005.
[6] Feng-Lei Fan, Jinjun Xiong. Mengzhou Li, and Ge Wang. On interpretability of artificial neural networks: A survey. IEEE Transactions on Radiation and Plasma Medical Sciences, 2021.
[7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pages 770-778, 2016.
[8] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, pages 604-613. ACM, 1998.
[9] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR. OpenReview.net, 2020.
[10] Adam R. Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci., 68(4):808 -808, 2004.
[11] Adam Klivans, Ryan O'Donnell, and Rocco A. Servedio. Learning geometric concepts via gaussian surface area. In FOCS, pages 541-550. IEEE Computer Society, 2008.
[12] Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 20(n 1/3, J. Comput. Syst. Sci., 68(2):303-318, 2004.
[13] David G Lowe. Object recognition from local scale-invariant features. In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pages 1150-1157. Icee, 1999.
[14] Sheheryar Mehmood and Peter Ochs. Differentiating the value function by using convex duality. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 3871-3879 PMLR, 2021.
[15] Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[16] Flood Sung, Yongxin Yang. Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning compare: Relation network for few-shot learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1199-1208, 2018.
[17] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks, arXiv preprint arXiv: 112,,6999 2013.
11

---

[18] Richard Szeliski. Computer Vision Algorithms and Applications, Second Edition. Texts in Computer Science. Springer, 2022.
[19] Jingdong Wang, Heng Tao Shen, Jingkuan Song, and Jianqiu Ji. Hashing for similarity search: A survey, arXiv preprint IrX8iv1408.11 2927, 2014.
[20] Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):1-40, 2016.
12


Reviews:
[{"review_id": "WDFe_L5gN_", "reviewer": "Reviewer_JF41", "summary": "This work aims to describe the sketch of a simple image using polynomial functions and hash tables. This is a handcrafted feature technique that has interpretation compared to deep learning.", "questions": "I hope the authors will add a large number of experiments to prove its value as a feature.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I really like the idea of this paper, especially in this era of deep learning run amok.\nNot all applications have sufficient samples, and handcrafted features become especially important.\n\nStrengths\n\n[+]  The motivation sounds reasonable and the writing of the paper is good.\n\n[+]  The methodology is also reasonable, considering the trade-off between read efficiency (Hash) and accuracy (Polynomial).\n\nWeaknesses\n\n[-]  My only concern is the experimental part, which is difficult to persuade me that as a feature should be tested by the classification task.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DdBPnRJbH50", "reviewer": "Reviewer_Jdpa", "summary": "The scope of this work falls into image representation learning, and the authors aim to study synthetic images with thresholded polynomial functions (in a generative process). In particular, the authors proposed a sketching algorithm by using locality sensitive hash (LSH). As a result, a succinct sketch is produced from an image, such that the sketch can be used for image reconstruction. The major contribution is that the authors proposed to leverage LSH tables to split an image into regions, then train parameters within each hash bucket, and the resulting parameters can be used to reconstruct image regions. The authors claim potential usage on sketches for image classification and possible extension of using secondary LSH index of sketches for different parts/shapes in the image as well.", "questions": "I think the authors could provide some possible applications of using the proposed sketching method, where image classification could be one with a very broad impact on the computer vision community.\n\nIn addition, is that possible to some visual examples of handling simple and complex images by the proposed method, so that readers can more quickly get the point of what and how the algorithm can do.", "limitations": "The authors only study synthetic images with basic shapes, while there might be issues when dealing with more complex images or real images.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe overall idea makes sense to me, and the authors provide detailed descriptions of the method, including problem setup, preliminaries, and many additional explanations of the proposed definitions, lemma so on, making the read more smooth (although I have to repeatedly read several times). More details are also provided in the supplementary material.\n\nWeaknesses\n\nThe experiments part is somehow limited. The authors only demonstrate the smoothness of the sketch vectors on three functions that can generate simple shapes (ellipses, hyperbolas and rectangles). However, there is no support for the main claim about the usefulness of image classification in the paper title.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "9SDZY-J3LRn", "reviewer": "Reviewer_kMv5", "summary": "This paper studied the question \"Do deep networks learn representations that are isomorphic to the parameters to generate the image?\". It provided a sketching algorithm to produce an image sketch that is equivalent to the parameters. The main idea is to use a locality sensitive hash (LSH) table. The authors provided theoretical results on synthetic images that are composed of a union or intersection of several mathematically specified shapes using thresholded polynomial functions (for e.g. ellipses, rectangles).", "questions": "Do the theory proposed in this paper have potential applications on real classification tasks?", "limitations": "Addressed by the authors.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe methods seems to have theoretical supports. The results seems to be solid.\n\nWeaknesses:\nIt lacks intuitive explanations behind the theoretical results. Also, it does not tell the potential usage of the proposed method in real applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept