Minimalistic Unsupervised Representation Learning with the Sparse Manifold Transform
Authors: Yubei Chen
Zeyu Yun
Yi Ma
Bruno Olshausen
Yann LeCun
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Unsupervised Learning
Sparsity
Low-rank
Manifold learning
Spectral Embedding

Abstract: We describe a minimalistic and interpretable method for unsupervised representation learning that does not require data augmentation, hyperparameter tuning, or other engineering designs, but nonetheless achieves performance close to the state-of-the-art (SOTA) SSL methods. Our approach leverages the sparse manifold transform, which unifies sparse coding, manifold learning, and slow feature analysis. With a one-layer deterministic (one training epoch) sparse manifold transform, it is possible to achieve $99.3\%$ KNN top-1 accuracy on MNIST, $81.1\%$ KNN top-1 accuracy on CIFAR-10, and $53.2\%$ on CIFAR-100. With simple gray-scale augmentation, the model achieves $83.2\%$ KNN top-1 accuracy on CIFAR-10 and $57\%$ on CIFAR-100. These results significantly close the gap between simplistic ``white-box'' methods and SOTA methods. We also provide visualization to illustrate how an unsupervised representation transform is formed. The proposed method is closely connected to latent-embedding self-supervised methods and can be treated as the simplest form of VICReg. Though a small performance gap remains between our simple constructive model and SOTA methods, the evidence points to this as a promising direction for achieving a principled and white-box approach to unsupervised representation learning, which has potential to significantly improve learning efficiency.

Published as a conference paper at ICLR 2023
MINIMALISTIC UNSUPERVISED REPRESENTATION LEARNING WITH THE SPARSE MANIFOLD TRANS- FORM
Yubei 122 Zeyu Yun Yi Ma', Bruno Olshausen 4.56, Yann LeCun
Meta AI
2 Center for Data Science, 3 Courant Institute, New York University
EECS Dept., Redwood Center, 6 Helen Wills Neuroscience Inst., UC Berkeley
ABSTRACT
We describe a minimalistic and interpretable method for unsupervised represen- tation learning that does not require data augmentation, hyperparameter tuning. or other engineering designs, but nonetheless achieves performance close to the state-of-the-ee (SOTA) SSL methods. Our approach leverages the sparse mani- fold transform (21), which unifies sparse coding, manifold learning, and slow fea- ture analysis. With a one-layer deterministic (one training epoch) sparse manifold transform, it is possible to achieve 99.3% KNN top-1 accuracy MNIST, 81.1% KNN top-1 accuracy on CIFAR- 10, and 53 on CIFAR-100 With simple gray- scale augmentation, the model achieves 83.2% KNN top-1 accuracy CIFAR-10 and 57% on CIFAR-100. These results significantly close the gap between sim- plistic "white-box" methods and SOTA methods. We also provide visualization illustrate how an unsupervised representation transform is formed. The proposed method closely connected to latent-embedding self-supervised methods and be treated as the simplest form of VICReg. Though a small performance gap re- mains between our simple constructive model and SOTA methods, the evidence points to this as promising direction for achieving a principled and white- box approach to unsupervised representation learning, which has potential signifi- cantly improve learning efficiency.
INTRODUCTION
Unsupervised representation learning (aka self-supervised representation learning) aims to build models that automatically find patterns in data and reveal these patterns explicitly with representa- tion. There has been tremendous progress over the past few years in the unsupervised representation learning community, and this trend promises unparalleled scalability for future data-driven machine learning. However, questions remain about what exactly a representation is and how it is formed in an unsupervised fashion. Furthermore, it is unclear whether there exists of common principles underlying all these unsupervised representations.
Many investigators have appreciated the importance improving our understanding unsupervised representation learning and taken pioneering steps to simplify SOTA methods [8
19
22 to 39
114
establish connections to classical methods [69 4 to unify different approaches
55
to visualize the representation 15). and to analyze the methods from a theoretical perspective
B 45 107 4 The hope is that such understanding will lead to a theory that enables us build
simple, fully explainable "white-box"" models [14] 13 71 from data based on first principles. Such computational theory could guide us in achieving two intertwined fundamental goals: modeling natural signal statistics, and modeling biological sensory systems 83
31
32 65
Here, we take small step toward this goal by building a minimalistic white-box unsupervised learn- ing model without deep networks, projection heads, augmentation, or other similar engineering de- signs. By leveraging the classical unsupervised learning principles of sparsity 88 82 and low-rank spectral embedding [89 105). build two-layer model that achieves non- trivial benchmark sults on several standard datasets. In particular, we show that a two-layer model based on the sparse manifold transform 21). which shares the same objective as latent-embedding SSL methods (5).

---

Published as a conference paper at ICLR 2023
achieves 99.3% KNN top-1 accuracy on MNIST, 81.1% KNN top-1 accuracy CIFAR-10, and 53.2% on CIFAR-100 100 without data augmentation. With simple grayscale augmentation, it achieves 83.2% KNN top-1 accuracy on 10 and 57% KNN top-1 accuracy on CIFAR- 100. These
sults close the gap between a white-box model and the SOTA SSL models [8] 20 5. 117. Though the gap remains, narrowing it further potentially leads to a deeper understanding of unsupervised representation learning, and this is a promising path towards useful theory.
We begin the technical discussion by addressing three fundamental questions. In Section 2 we then revisit the formulation of SMT from a more general perspective and discuss how it can solve various unsupervised representation learning problems. In Section B] we present benchmark results on MNIST, CIFAR-10, 10, and CIFAR-1000 together with visualization and ablations. Additional re- lated literature addressed in Section 4 and we offer further discussion in Section 5 This paper makes four main contributions. 1) The original SMT paper explains SMT from only a manifold learning perspective. We provide novel and crucial interpretation of SMT from a probabilistic co- occurrence point of view. 2) The original SMT paper potentially creates the misleading impression that time is necessary to establish this transformation. However, this is not true. In this paper, we explain in detail how different kinds of localities (or similarities) can be leveraged to establish the transform. 3) We provide benchmark results that support the theoretical proposal in SMT. 4) We provide a connection between SMT and VICReg (and other SSL methods). Because SMT is built purely from neural and statistical principles, this leads to a better understanding of self-supervised learning models.
Three fundamental questions:
What is an unsupervised (self-supervised) representation? Any non-identity transformation of the original signal can be called representation. One general goal in unsupervised representation learning is to find function that transforms raw data into a new space such that "similar" things are placed closer to each other and the new space isn't simply a collapsed trivial space]] That is, the important geometric or stochastic structure of the data must be preserved. If this goal is achieved, then naturally "dissimilar" things would be placed far apart in the representation space.
Where does "similarity" come from? "Similarity"" comes from three classical ideas, which have been proposed multiple times in different contexts: 1) temporal co-occurrence [12) [19], 2) spatial co-occurrence 990 28, 34
103 84], and 3) local metric neighborhoods [89 105] in the raw signal
considerable extent when the underlying structure is geometric but they can also differ conceptually when the structure is stochastic. In Figure [ we illustrate the difference between manifold structure and a stochastic co-occurrence structure. Leveraging these similarities, two unsupervised representation learning methods emerge from these ideas: manifold learning and co-occurrence statistics modeling. Interestingly, many of these ideas reach a low-rank spectral decomposition formulation or a closely related matrix factorization formulation [12 89 105
space. These ideas overlap
The philosophy of manifold learning is that only local neighborhoods in the raw signal space can be trusted and that global geometry emerges by considering all local neighborhoods together that is. "think globally, fit (ocally[[2]1 In contrast, co-occurrence (25 statistics modeling offers probabilistic view, which complements the manifold view as many structures cannot be modeled by continuous manifolds. A prominent example comes from natural language. where the raw data does not come from a smooth geometry. In word embedding 777] 78, 86), "Seattle" and "Dallas" might reach a similar embedding though they do not co-occur the most frequently. The underlying reason is that they share similar context patterns [68] 118). The probabilistic and manifold points of view complement each other for understanding "similarity." With a definition of similarity, the next step is to construct a non-irivial transform such that similar things are placed closer to one another.
How do we establish the representation transform? Through the parsimonious principles of sparsity and low-rank spectral embedding. The general idea is that we can use sparsity to de- compose and tile the data space to build a support, see Figure b...). Then, we can construct our representation transform with low-frequency functions, which assign similar values to similar points on the support, see Figure c). This process is called the sparse manifold transform 21.
An obvious trivial solution is to collapse every data point to a single point the new space. II we consider that signals which temporally spatially co-occur are related by a smooth transformation, then these three ideas are equivalent.
2

---

Published as a conference paper at ICLR 2023
(a) A manifold point of view
(b) co-occurrence point of view
Figure I: Two different points of view. (a) Manifold: There are three patches in the dashed boxes. Let's assume there a path between them on a manifold of the image patch space; then, their rela- tionship can be found based on either the Euclidean neighborhoods, spatial co-occurrence, or tem- poral co-occurrence from smooth transformation. (b) Probabilistic: For the two red boxes ("leg"), it is unclear whether there is a path between them in the patch space. However, they can still be considered to be similar under spatial co-occurrence because they appear the same context. These two patches both co-oceur with the "grass land" (blue boxes) and "elbow body" (green boxes). Temporal co-occurrence has a similar effect.
UNSUPERVISED LEARNING WITH THE SPARSE MANIFOLD TRANSFORM
The sparse manifold transform. The sparse manifold transform (SMT) was proposed to unify several fundamental unsupervised learning methods: sparse coding, manifold learning, and slow feature analysis. The basic idea of SMT is: 1) first to lift the raw signal into high-dimensional space by non-linear sparse feature function f. i.c. ā = f(²). where locality and decomposition respected. 2) then to linearly embed the sparse feature á into a www-dmmensionll space, i.c., find 3 = Pā. such that the similarity "trajectory linearity" for each data point 24, we can choose to use either its local neighbors in the raw signal space, its spatial co-occurrence neighbors,
respected. As mentioned earlier,
its temporal co-occurrence neighbors to define similarity. Let's denote the neighbors of I; as En(s). and denote ā; as the sparse feature of H, The optimization objective of finding similarity pereriti-ppeeriingg linear projection the following:
min Σ
PP Pājlli, jEn(i)
Σ
PEEa,,G pT
Example sparse feature extraction function ă = f() could be sparse coding (82 and vector quanti- zation 42 which will be further explained Section 3
Similarity be considered as first-order derivative (see Appendix L for detailed explaination). more restrictive requirement linearity 89 which the second-order derivative. Then the objective is changed to similar one:
min Σ Pā P
Σ jEn(i)
Pā,li)
s.t. PE =
(2)
where Ejen(h) w(i,)) = 1. Several ways to acquire w(:,)) are: to use locally linear interpolation,
temporal linear interpolation, spatial neighbor linear interpolation. If we write the set {ā,} as a matrix A, where each column of corresponds to the sparse feature of a data point, then both Optimization andd Optimization 2
can be formulated the following general formulation 21
min |AAD s.t. PVPT =
where D is differential operator, V 1, AAT and N is the total number of data point. D corre- sponds to a first-order derivative operator in Optimization and a second-order derivative operator in Optimization 2 For Optimization [ D has M columns, where M denote the number of pair
3

---

Published as a conference paper at ICLR 2023
of neighbors. D [d1 d.....dyy.. dM and for kth pair of neighbors F, 2y we have dki 1 and dk = -. All other elements D are zero. For Optimization 2 Djs = -((i,) for j E n(1), DH and j 0 otherwise. The solution to this generalized degenddecompositonn problem is given [109] by P UV-2 where is matrix of L trailing eigenvectors (i.e. eigenvectors with the smallest cigenvalues) of the matrix Q = V -- ADDD" V Please note that if contains all of the cigenvectors of Q, then the solution of SMT reduces to the whitening matrix.
a)
e)
Data Distribction
Epectralnmoedddng with Sparso Features
Eudidcon Ne ghboroood
b)
d)
Each Cimension the Unsupervised esentation Transform
Embedding Negbbooood
Figure 2: Manifold disentanglement with SMT. (a) Data distribution along two entangled 1D spiral manifolds in the 2D ambient space. (b) Sparse feature (dictionary) learned with 1-sparse sparse coding shown dots. They serve points marked as red and green crosses, the I-sparse feature function maps them to the corresponding dictionary element, marked as red and green dots. (c) Spectral embedding assigns similar values to nearby dictionary elements. Each embedding dimension is low-frequency function defined on the sparse dictionary support. We show the first 4 embedding dimensions, i.e., the first 4 rows of P. Pi.., P2.., Pa.. and Pa... The color represents the projection values for each dictionary element. (d) The sparse manifold transform is vector function P)()), and plot the first four dimensions of SMT over the data distribution. The color represents the projection values for each data point. (c) We show the Euclidean neighborhood of the point marked by blue cross in the original data space. (f) After the sparse manifold transform, we show the cosine similarity neighborhood of the point marked by the same blue cross in the representation space.
of landmarks to tile the data manifolds. Given two
Manifold point of view: 2D nonlinear manifold disentanglement problem. Let's consider spiral manifold disentanglement problem in a 2D space shown in Figure[ja) As it is not a linearly- separable problem, construct representation function disentangle the two spiral manifolds, we need to leverage nonlincarity and give the transform function enough sparse sparse coding learn an overcomplete dictionary + 2 i.e. set of K landmarks 198] 27). to tile the space. This dictionary serves as the support of the representation function, as shown Figure 2(b). This dictionary turns a data point into I-sparse vector f(ā) = argmin | @all |.t.| a = 1, ||@||| = 1; ā e IR. is an 1-hot vector and denotes the closest dictionary element to Z. Next, we seek linear projection P to embed the sparse vector ă to lower dimensional space, 3 Pf( and 8 IRd, which completes the transform. Each column of P E IR corresponds to a d-dimensional vector assigned to the corresponding entry a. The 7th row, P... of P is embedding dimension, which should assign similar values the nearby landmarks the manifolds. As we mentioned earlier, there are three localities to serve as similarities, where they behave similarly in this case. With either of the three, one can define the Optimization I or Optimization 2 In this simple case, the different similarity definitions are almost identical, leading to spectral solution P. Let's choose simple construction 66) given a data point ã E IR², add Gaussian noise 61; 62 to generate two augmented samples 31 21 +1 and F2 = 32 + <2, which are marked as the red and green crosses Figure b)b and are considered as similar data points. (āī1 and fāā2) are marked red and green dots (landmarks). So the objective in Optimization is to find P such that Epwe((a))) (o. P +e1) Pf(12 + =2) is minimized. We show the solution in Figure [(c) with the first four embedding dimensions, {Pi... P2. Pa.., P4. plotted, see, each embedding
h flexibility. Let's first use 1-
where the color reflect their values at each dictionary element. As
21 "--sparse sparse coding is equivalent clustering. Sampling the data the dictionary also suffices here.
4

---

Published as a conference paper at ICLR 2023
dimension, e.g. P..., is essentially low- foe-ureue function. Pi.,, P2. are piecewise constant functions on the union of the manifolds. Essentially, either P1. or P2. will suffice to determine which manifold point belongs to. P2.., Ps. are non-constant linear functions along the manifolds. A linear combination of Ps. and Pa. will preserve the coordinate information of the manifolds. Now with both the sparse feature function f and the spectral embedding P, we have constructed sparse manifold transform, i.e. 3 (z)) In Figure d)), we show how each dimension of this transform assigns different values to each point in the original 2D space, and the points from the same manifold are placed much closer in the representation space as shown Figure ft).
Probabilistic point of view: co-occurrence modeling, Many related variations of spectral and matrix factorization methods have been widely used to build continuous word representations. SMT formulation bears probabilistic point of view, which complements the manifold perspective. A notable example is the word co-occurrence problem. Here we present an SMT-word embedding. Given a corpus and token dictionary, we can treat each token seek linear projection P such that tokens co-occur within a certain size context window are linearly projected closer. After we solve Optimization [ each column of P corresponds to continuous emhedding of an element from the token dictionary. We train SMT on WikiText- 103 (76) and provide the visualization result in Appendix A As we discussed earlier, "Seattle" and "Dallas" may reach a similar embedding though they do not co-occur the most frequently. The probabilistic view of SMT explains the phenomenon that two embedding vectors can be close in the representation space if they frequently appear in similar contexts, though they may not be close in the signal space.
1-hot vector ã. Then we can
Sparsity, locality, compositionality, and hierarchy. (a) Sparsity: In the sparse manifold transform, sparsity mainly captures the locality and compositionality. which builds support for the spectral embedding. Spectral embedding, on the other hand, would assign similar values to similar points on the support. (b) Locality: In a fow-dimensional space, e.g., the 2D manifold disentanglement case, with enough landmarks, using I-sparse feature fug to capture locality will suffice, and SMT can directly solve the problem as we showed earlier. Please note that, in this simple case, this process is not different from manifold learning 89 105] and spectral clustering [80]. One can also use a kernel, e.g. RBF kernel the heat kernel, to respect locality by lifting to higher or infinite dimensional space 195] 112:
6 102 R. (c) Compositionality: If the signal comes from a high- dimensional space, e.g. images, then we may need build the representation for image patches first since even local neighborhoods can become less reliable in high-dimensional space with finite samples. If the patch space is simple enough, e.g. MNIST, using 1-sparse vector quantization as the sparse feature foy would be sufficient to capture the locality in patch space. As we will show later in Section 3 the SMT with 1-sparse feature feg achieves over 99.3% top-1 KNN accuracy. For more complex natural images, e.g. CIFAR or ImageNet, compositionality exists even in the patch space. So I-sparse feature becomes less efficient and may compromise the fidelity of the representation. As we will show, the general sparse feature will achieve better performance than the 1-sparse feature in this case, (d) Hierarchy: For high-resolution images, we may need to stack several layers of transforms in order to handle the hierarchical representation [108] 35 52).
SMT representation for natural images. We use SMT to build representation for image patches and aggregate patch representation of an image as the image representation. For an S x S image, we extract every T x T image patches as shown in Figure 3 Each of the image patches is whitened and 122normalized, which resembles the early visual system processing
[110] 74. Given image, denote the pre-processed image patches as { where indicates the vertical index of the patch and j indicates the horizontal index. For each image patch (7.g), we define its neighbors to be other patches within a certain pixel range from it on the same image, i.e., n(ij) = { Im;; l - 1| S d and j ml S d). Given sparse feature function f. we would like to map these neighboring patches to be close in the representation space. If we choose d = S - T + 1, then all the patches from the same image are treated as neighbors to each other, Given f.d, and set of training images, we can calculate ADDT AT, V. and solve Optimization I for P. [ The representation of patch E.y is B,, = (ā with a L2 normalization. If we denote all of the patch representations from an image as tensor B, the image representation is 전 = 1.2 normalize pw (avg pool( BB ks, stride)). avg-pool(:; ks, stride) denotes the average pooling operator, where ks and stride are the kernel size and stride size of the pooling respectively. L2.normalize.pp denotes a point-wise L2 normalization. We use tensor Z as a vector for an image representation. The detailed settings, e.g. d, ks, stride, etc.,
"hiile SGD algorithm can be used 21 we use deterministic algorithm in this paper.
5

---

Published as a conference paper at ICLR 2023
are left to the experiments section. In this work, we primarily use the soft-KNN classifier to evaluate the quality of representation.
Connection to the deep latent-embedding methods. There are important connection between the SOTA embedddin SSL methods [8] 5]. In particular, Optimization || can be considered the simplest form of VICReg [3], whereas the VC regularization is replaced by a hard constraint, and sparse feature function replaces the deep neural encoder. See exact formulation in Appendix KJ This
connection even stronger given the evidence that VICReg is essentially building representation of image patches [22] In this sense, SMT can be considered the simplest form of VICReg.
S T-TI
10
T+1
d1
012
P11
812
B.
in
P
3.
PdB
Patch Extautioon
Linear Spoctsal Eimradding
Normalistion & Local Aug Pooling
Figure 3: SMT representation of an image and its patches. An S S image first decomposed into (S - T + 1) x (S- - + 1) overlapping image patches of size T x T. Each image patch is whitened and the sparse feature is calculated, āzy f(Ez)), where ij indicates the spatial index of the image patch and žej is the whitened patch. The representation of patch Fig is Bij = (T with L2 normalization. We then aggregate these patch representations B.g via spatial local average pooling and 122normmaiie at every spatial location to obtain the final image-level representation z.
EMPIRICAL RESULTS
In this section, we first provide the benchmark results on MNIST, CIFAR-10, and CIFAR-100. Qualitative visualization is also provided for better understanding. We also compare 1-sparse feature fug and a more general sparse feature fgg- = Seg T D) refers to the I-sparse vector quantization sparse feature, where ã; = 1 for We denote the SMT representation with feg sparse feature as SMT-VQ. ā = foy D.t) refers more general sparse function, where each column of dictionary D is an image patch and / is a given threshold. For ā = (T D,I), the ith entry of ā is if only if the cosine similarity between J and äth dictionary element pass the threshold, i.e., 04- a; = otherwise. We denote the SMT representation with fog feature as SMT-GQ. We find fge achieves similar performance experiments since it does not involve loopy inference. For both MNIST and CIFAR, we use 6x6 image patches, i.e., T 6. All the image patches are whitened, and the whitening transform described in Appendix C Once patch embeddings are computed, we use spatial average pooling layer with ks = 4 and stride = 2 to aggregate patch embeddings to compute the final image-level embeddings.
argmax; || D.lell and D is a dictionary.
if cos D..)) 2 I and
the sparse coding feature in benchmarks, and it's more efficient in
MNIST. For MNIST, I-sparse feature fog is sufficient to build good support of the patch space. The dictionary D E IR 36xK is learned through 1-sparse sparse coding, which is equivalent to clustering and be implemented with any clustering algorithm. The centroid of each cluster will serve as a dictionary element. The detailed learning procedure is left to Appendix [ The inference is equivalent to vector quantization. We chose the patch embedding dimension as 32 because further increasing the dimension does not improve the performance. In Table [ we compare different dictionary sizes and different spatial co-occurrence ranges. We also compare the SMT embedding with the GloVe embedding. Treating each image patch as a token and the entire image patch as sentence, we can train a GloVe word embedding model on MNIST patches. We provide GloVe embedding with optimized settings. As we can see in Table I GloVe embedding works slightly worse in this case, even with a large dictionary size. Further, we can find that a small context range works slightly better for MNIST. This is probably due to the fact that the patch space of MNIST closer to a manifold, and co-occurrence is less informative in this case. To further verify this hypothesis, we provide an ablation study on embedding dimensions in Table Even if we reduce

---

Published as a conference paper at ICLR 2023
the embedding dimension to 4 the top-1 KNN accuracy is still 98.8%. This implies that the MNIST patch space might be close to a manifold like high-contrast natural image patches 667 26 12
Table 1: Evaluation of SMT representation on MNIST. The table shows the evaluation result of SMT embedding and GloVe embedding using KNN classifier. We compare different dictionary
size: 16384 vs. 65536 and context range: 3-Pixel (d = 3) vs. Whole Image (d = 28 - 6 + 1). We
use 32 as the embedding dimension. As shown in the table, Vl embedding works slightly worse than SMT embedding.
Co-Oecurrence Context Range
SMT-VQ (16384)
SMT-VQ (65536)
SMT-VQ (GloVe, 100K)
Whole Image
99.0%
98.9%
98.8%
3 Pixels
99.2%
99.3%
99.0%
Table 2: Low dimensionality of MNIST patch space. The table shows the effect of the embedding dimension of SMT on the KNN evaluation accuracy. With only a 4-dimensional embedding for each patch, SMT can still achieve 98.8% KNN accuracy. The quick accuracy drop at 3-dimensional embedding space may imply that the MNIST patch space can be approximately viewed as a 3- manifold since the 4-dimensional patch embedding is L2-normalized and on a 3-sphere.
Emb Dim=2
Emb Dim=3
Emb Dim=4
Emb Dim=8
Emb Dim=16
Emb Dim=32
KNN Acc
97.1%
98.3%
98.8%
99.0%
99.1%
99.2%
CIFAR-10 and CIFAR-100. For the CIFAR benchmarks, we compare both fug(;; D) and ( t). The dictionary D used in fog is learned through I-sparse sparse coding, and the dictio- nary D used in Soo is just randomly sampled from all image patches for efficiency purposes. Since Jog with color patches underperforms that with grayscale patches, we choose to experiment mostly with for on CIFAR benchmarks. For fog. t is set to 0.3 with color patches and 0.45 with grayscale patches. We choose the patch embedding dimension as 384. Further, with color patches, dropping the first 16 embedding dimensions of P improves the accuracy by about 1%. We compare the per- formance of SMT with SOTA SSL models, specifically, SimCLR and VICReg with a ResNet 18 backbone. We train these SSL models using random resized crop and random horizontal flip as de- fault data augmentations. For fair comparison, SMT training uses both the original version and the horizontally flipped version of the training set. We also experiment with different color augmentation schemes. For "Grayscale Image Only", we train both SMT and SSL models using only grayscale images. For "Original + Grayscale", we train SMT on both color images and grayscale images, then concatenates the embedding of each color image with the embedding of its grayscale version. We train SSL models with additional "random grayscale" color augmentations. With a two-layer deterministic construction using only image patches, SMT significantly outperforms SimCLR and VICReg, with no color augmentation. With "Grayscale Image Only" color augmentation, SMT-GQ achieves similar performance as SimCLR and VICReg. With "Original Grayscale" augmenta- tion, SMT-GQ performs on par with SimCLR and VICReg without colorjitter and several additional color augmentations. With full data augmentation, SimCLR and VICReg outperform SMT-GQ. However, we did not find a straightforward way to add these color augmentations to SMT-GQ. We can observe the same trend on CIFAR-100. Interestingly, SMT--Q always significantly outperforms SimCLR and VICReg before we add color jittering and additional data augmentations. We provide further ablation studies in Appendix. Appendix G and Appendix H study how context range and the studies different evaluation schemes (KNN vs. linear probing). Appendix E shows that the performance of SMT will signifi- cantly degrade if we replace spectral embedding with other dimension reduction algorithms that do not respect locality.
number of training samples affect the model performance. Appendix ||
Visualization. For a better understanding, we provide visualization of the patch embedding space with the 1-sparse feature in Figure 4 Given a dictionary D, each dictionary element is an image patch in the whitened space. For dictionary element shown in the red box, can visualize its nearest neighbors, measured by cosine similarity, in the embedding space. All the image patches unwhitened before visualization, where the detail is left to the Appendix C In Figure A we can see that the nearest neighbors are all semantically similar. a) is a slightly curved stroke of a digit in MNIST. b) shows the patch of the center of digit "4" e) shows part of "wheel" of
As the emhedding is further 1.2 normalized, this a d-dimensional space.

---

Published as a conference paper at ICLR 2023
Table 3: Evaluation of SMT and SSL pretrained model on CIFAR-10. The table shows the eval- uation result of SMT embedding and SSL pretrained models using KNN classifiers. We evaluated these models using various color augmentation schemes. The details of how we add color augmen- tation to each model explained in section 3 We tried two sparse features for SMT: fug and føg- For sgg. we tried two dictionary sizes: 8192 and 65536. Both SSL models use ResNet- 88 as a back- bone and are optimized for 1000 epochs through backpropagation; SMT uses 2-layer architecture
and is analytically solved, which can be considered as epoch.
Color Augmentation
SMT VQ (100K) SMT GQ (8192)
SMT-GQ (65536)
SimCLR (ResNet18)
VICReg (ResNet18)
Original Image
79.2%
81.1% %
68.3%
70.2%
Grayscale Image Only
78.4%
77.5%
78.9%
80.6%
81.3%
Original Grayscale Full (Colorlitter etc.)
81.4%
83.2%
85,7%
83.7%
90.1%
91.1%
Evaluation of SMT and SSL pretrained model CIFAR-100. The table shows the performance of SMT embedding and two other SSL pretraining methods on the CIFAR-100 dataset. The data augmentation and different SMT variations used in this experiment the same as those for evaluating CIFAR-10 dataset in Table 3 For CIFAR-100 dataset, without full color augmentation, SMT always outperforms the two SSL pretraining methods.
Table 4:
Color Augmentation SMT-VQ (100K) SMT-GQ (8192) SMT-GQ (65536)
SimCLR (ResNet18)
VICReg (ResNet18)
Original Image
50.8%
53.2%
32.4%
32.6%
Grayscule Imuge
46.6%
45.8%
48.9 %
43.0%
43.9%
Original + Grayscale
53.7%
57.0%
48.9%
46.0%%
Full (ColorJitter etc.)
63.7%
65.4%
in CIFAR. d) shows part of "animal face". These results are similar to the 2D results shown in Figure 2 Overall, the representation transform brings similar points in the data space closer in the representation space. Additional visualization for SMT on CIFAR-TO dataset in Appendix M
MORE RELATED WORKS
There are several intertwined quests closely related this work. Here, we touch them briefly.
is the engine behind the recent revolution of AI. Given the right craftsmanship. deep neural networks are powerful optimization tools to allow us express various engineering objectives conveniently. It has also revolutionized the
The state-of-the-an unsupervised methods. Deep learning 63 66
unsupervised visual representation learning in the past few years [13 47 18 5 Understanding the engineering advancements can help us gain deeper theoretical insights and many efforts have been towards this goal.
made 885 70 2 94]
To model the patterns of the signal spaces. A central challenge of modeling the signals is the formalization of a small set of ideas for constructing the representations of the patterns [43] 77). formulated to handle the sparsity in the natural signals. Steerable and shiftable filters 38) 101 99] were introduced to handle the discontinuity of wavelet filters with respect to the natural transformations. Basis pursuit [1 16 finds decomposition of signal by a predefined dictionary, sparse coding[81 82), and ICA 7 (56) were proposed to learn the filters or dictionary from data. Before the sparse manifold transform 211, many important works have paved the way and introduced topology and transformations between the dictionary elements 58 M. There are also several important works studying the natural image patch space with non- parametric methods and topological tools 67
Wavelet transform 72 24
26
12 48). Manifold learning 89 [05] 44] and
93 was proposed model the geometric structure in the signal space. The geometric signal processing is also an increasingly important topic[96]
spectral clustering B3 37
95|
75 80
104
Modeling of biological visual system. Exploring the geometric or statistical structure of natural signals are also strongly motivated by computational modeling of biological visual system. Many properties of the visual system reflect the structure of natural images [100] 59 An early success of this quest was that the dictionary elements learned in unsupervised fashion closely resemble the receptive fields of simple cells in the V1 cortex [1 82]. In order to further understand the visual cortex, we need to develop theories that can help to elucidate how the cortex performs the computationally challenging problems of vision (8) One important proposal is that the visual
cortex performs hierarchical manifold disentanglement 31
32
The sparse manifold transform
8

---

Published as a conference paper at ICLR 2023
b)
Figure 4: Visualization of dictionary elements' neighborhoods in the SMT embedding space. We plot 4 different dictionary element and their top nearest neighbors in four subfigures, respec- tively. For each subfigure, the dictionary element shown in the red box. Its neighboring patches in the representation space ordered by their cosine similarity to the dictionary element, where the image patches in the top left have highest cosine similarity, and image patches on the bottom right have lowest cosine similarity. This figure is qualitatively similar to Figure f except it is in high-dimensional space and the semantic meaning is more complex.
was formulated solve this problem, which supported by a recent perceptual and neuroscience evidence 49 50 There are also several related seminal works on video linearization 112
To build representation models from the first principles. The now classical models before deep 60
learning use to be relatively simpler [64] 108:
[15] 61]. where sparsity was a widely adopted principle. While the gap between the SOTA deep learning models and the simple models is
87
111
large, it might be smaller than many expect 23 88 10 106]. The quest to build "white-box" models from the first principles
14
for unsupervised representation remains an open problem.
5 DISCUSSION
In this paper, we utilize the classical unsupervised learning principles of sparsity and low-rank spec- tral embedding to build minimalistic unsupervised representation with the sparse manifold trans- form 21 The constructed "white-box" model achieves non-trivial performance on several bench- marks. Along the way, we address fundamental questions and provide two complementary points of view of the proposed model: manifold disentanglement and co-occurrence modeling. Further, the proposed method has close connections with VICReg (5) and several other SOTA latent-embedding SSL models [8] 117 (39]. However, there are several important limits to this work, which point to potential future directions. 1) We need to scale the method to larger datasets, such as ImageNet. 2) While a two-layer network achieves non-trivial performance, we need further construct white-box hierarchical models to understand how a hierarchical representation is formed [51 53 3) While spectral embedding is context- independent [86] 118], there is clear benefit in building contextu-
alized embedding 229 91: 52
36
116 73). Building minimalistic unsupervised representation
based on contextualized embedding is an attractive topic for additional research. 4) Although we only focus sparse feature in this paper, other features should also be explored. We can generalize feature extraction function f in SMT to an arbitrary function as long as it can capture the locality and structures in the signal space. For example, if choose ff quadratic expansion function, Optimization I would reduce to slow feature analysis [112].
The evidence shows that there considerable promise in building minimalistic white-box unsuper- vised representation learning models. Further reducing the gap with SOTA methods and under- standing the mechanism behind this reduction can lead us towards theory. Minimalistic engineer- ing models are easier to analyze and help us build a theory to identify optimality and efficiency, and a testable theory can also facilitate modeling biological learning systems. This work takes step towards these goals.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Zengyi Li, Jamie Simon, Sam Buchanan, Juexiao Zhang, Christian Shewmake, Jiachen Zhu, Domas Buracas, and Shengbang Tong for participating in several intriguing discussions during the preparation of this manuscript. We also thank Fritz Sommer and Eero Simoncelli for provid- ing valuable feedback. We also thank our anonymous reviewers for the helpful suggestions and insightful questions, which helped us improve the manuscript considerably.
REFERENCES
[]] Joakim Andén and Stéphane Mallat. Deep scattering spectrum. IEEE Transactions on Signal Processing, 62(16))411-4122 2014.
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
[3] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: (002:0/902.022220 2019.
[4] Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learn- ing recover global and local spectral embedding methods. arXiv preprint arXiv:2205.11500 2022.
[5] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variane-iivarinne--cwaiinee regu- larization for self-supervised learning. arXiv preprint arXiv:1005004900: 2021.
[6] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-1396 2003.
[7] Anthony J Bell and Terrence J Sejnowski. An information-maximizztiio approach to blind separation and blind deconvolution. Neural computation, 7(6): ((6::1129-119, 1995.
[8] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8): 1798-1828, 2013.
[9] Florian Bordes, Randall Balestriero, and Pascal Vincent. High fidelity visualization of what your self-supervised representation knows about. arXiv preprint drXiv:2112.09164, 2021.
[10] Wieland Brendel and Matthias Bethge. Approximating cnns with bag-of-local-feature mod- els works surprisingly well on imagenet. arXiv preprint arXiv:1904.00760, 2019.
[11] Charles F Cadieu and Bruno A Olshausen. Learning intermediaae--eevel representations of form and motion from natural movies. Neural computation, 24(4):827-866, 2012.
[12] Gunnar Carlsson, Tigran Ishkhanov, Vin De Silva, and Afra Zomorodian. On the local be- havior of spaces of natural images. International journal of computer vision, 76(1):1-12, 2008.
[13] Kwan Ho Ryan Chan, YD Yu, Chong You, Haozhi Qi, John Wright, and Yi Ma. Redunet: A white-box deep network from the principle of maximizing rate reduction. J Mach Learn Res, 23(1 14):1-103, 2022.
[14] Tsung-Han Chan, Kui Jia, Shenghua Gao, Jiwen Lu, Zinan Zeng, and Yi Ma. Pcanet: A sim- ple deep learning baseline for image classification? IEEE Iransactions on image processing, 24(1 24(12)501775003, 2015.
[15] Hila Chefer, Shir Gur, and Lior Wolf. Generie attention explainability for interpreting bi-modal and encoder-decoder transformers. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 397-4997666 2021.
10

---

Published as a conference paper at ICLR 2023
[16] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159, 2001.
[17] Shaobing Chen and David Donoho. Basis pursuit. In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers, volume pp. 41-44, IEEE, 1994.
[18] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple frame- work for contrastive learning of visual representations. In International conference on ma- chine learning, pp. 1597-1607. PMLR, 2020.
[19] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceed- ings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 15750- 15758, 2021.
[20] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momen- tm contrastive learning. arXiv preprint arXi::2003.04297 2020.
[21] Yubei Chen, Dylan M. Paiton, and Bruno A. Olshausen. The sparse manifold transform. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural In- formation Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, 10534-10545 2018
pp.
[22] Yubei Chen, Adrien Bardes, Zengyi Li, and Yann LeCun. Intra-instance vicreg: Bag of self- supervised image patch embedding. arXiv preprint arXiv:2206.08954, 2022.
[23] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in un- supervised feature learning. In Proceedings of the fourleenth international conference on artificial intelligence and statistics, pp. 223. JMLR Workshop and Conference Proceed- ings, 2011.
[24] Ingrid Daubechies. Orthonormal bases of compactly supported wavelets. Communications on pure and applied mathematics. 41(():909-99)) 1988.
[25] Virginia R de Sa. Learning classification with unlabeled data, Advances in neural information processing systems, pp. 112-112, 1994.
[26] Vin De Silva and Gunnar E Carlsson. Topological estimation using witness complexes. SPBG, 4:157-166, 2004.
[27] Vin De Silva and Joshua B Tenenbaum. Sparse multidimensional scaling using landmark points. Technical report, Technical report, Stanford University, 2004.
[28] Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. Indexing by latent semantic analysis. Journal of the American society for infor- mation science, 41(6):99-407, 1990.
[29] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810004805, 2018.
[30] Inderjit S. Dhillon and Dharmendra S. Modha. Concept decompositions for large sparse text data using clustering. Machine Learning, 42(1):143-175, 2001.
[31] James DiCarlo and David D Cox. Untangling invariant object recognition. Trends in cogni- tive sciences, 1 1188:3333-33 341, 2007.
[32] James J DiCarlo, Davide Zoccolan, and Nicole C Rust. How does the brain solve visual object recognition? Neuron, 13(3)4415-434, 2012.
[33] William E. Donath and Alan J Hoffman. Lower bounds for the partitioning of graphs. In
Selected Papers Of Alan Hoffman: With Commentary, pp. 437-442. World Scientific, 2003.
[34] Susan T Dumais. Latent semantic analysis. Annual Review of Information Science and Technology (ARIST), 38:1 1881189-2330 2004.

---

Published as a conference paper at ICLR 2023
[35] Boris Epshtein and Shimon Ullman. Semantic hierarchies for recognizing objects and parts. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2007.
[36] Kawin Ethayarajh. How contextual are contextualized word representations? comparing the geometry of bert, elmo, and gpt-2 embeddings. arXiv preprint arXiv: XXKi::999.005/11 2019.
[37] Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak mathematical journal, 23 (2):298-300 305, 1973.
[38] William Freeman, Edward H Adelson, et al. The design and use steerable filters. JEEE Transactions on Pattern analysis and machine intelligence, 13(9):891-906, 1991.
[39] Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann Lecun. On the duality between contrastive and non-contrastive self-supervised learning. arXiv preprint arXiv:2206.02574. 2022.
[40] Ross Goroshin, Joan Bruna, Jonathan Tompson, David Eigen, and Yann LeCun. Unsuper- vised learning of spatiotemporally coherent metrics. Proceedings of the IEEE international conference computer vision, pp. 4086 0093,4093,000 2015.
[41] Ross Goroshin, Michael Mathieu, and Yann LeCun. Learning to linearize under uncertainty. Advances in neural information processing systems, 28, 2015.
[42] Robert M. Gray. Vector quantization. IEEE ASSP Magazine, 1:4-29, 1984.
[43] Ulf Grenander and Michael Miller. Pattern theory: from representation to inference. OUP Oxford, 2006.
[44] Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference Computer Vision and Pattern Recognition (CVPR 06), volume 2, pp. 1735-1742. IEEE, 2006.
[45] Jeff 7. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. Advances in Neural Information Pro- cessing Systems, 34:5000-5011, 2021.
[46] Tatsunori Hashimoto, David Alvarez-Melis, and Tommi S Jaakkola. Word, graph and manifold embedding from markov processes. arXiv preprint arXiv:1509.05800 2015.
[47] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
[48] Olivier J. Hénaff, Johannes Ballé, Neil C. Rabinowitz, and Eero P. Simoncelli. The local low-dimensionality of natural images. In 3rd International Conference Learning Repre- sentations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[49] Olivier Hénaff, Robbe LT Goris, and Ecro Simoncelli. Perceptual straightening natural videos. Nature neuroscience, 22(6):984-99)) 2019.
[50] Olivier Hénaff, Yoon Bai, Julie A Charlton, Ian Nauhaus, Fero P Simoncelli, and Robbe LT Goris. Primary visual cortex straightens natural video trajectories. Nature communications, 12(1):1-12, 2021.
[51] Geoffrey Hinton. Some demonstrations of the effects of structural descriptions in mental imagery. Cognitive Science, 3(3):231-22 1979.
[52] Geoffrey Hinton. How to represent part-wholc hierarchies in a neural network. arXiv preprint 1rXiv:2102.12627, 2021.
[53] Geoffrey Hinton. Mapping whrt- hierarchies into connectionist networks. Artificial Intelligence, 46(1-2):47-75, 1990.
12

---

Published as a conference paper at ICLR 2023
[54] Geoffrey E Hinton and Sam Roweis. Stochastic neighbor embedding. Advances in neural information processing systems, 15, 2002.
[55] Junqiang Huang, Xiangwen Kong, and Xiangyu Zhang. Revisiting the critical factors of mugmentation-invarian representation learning. arXiv preprint arXiv:2208. 00275, 2022.
[56] Aapo Hyvärinen and Erkki Oja. A fast fixed-point algorithm for independent component analysis. Neural computation, 977::1433-442, 1997.
[57] Aapo Hyvärinen, Patrik Hoyer, and Mika Inki. Topographic independent component anal- ysis. Neural computation, 13(7):1527-1558) 2001.
[58] Aapo Hyvärinen, Jarmo Hurri, and Jaakko Väyrynen. Bubbles: unifying framework for low-level statistical properties of natural image sequences. JOSA A, 20(7):1237-1222, 2003,
[59] Aapo Hyvärinen, Jarmo Hurri, and Patrick Hoyer. Natural image statistics: A probabilistic approach early computational vision., volume 39. Springer Science & Business Media, 2009.
[60] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neigh- bor search. IEEE transactions pattern analysis and machine intelligence, 33(1):117-128, 2010.
[61] Hervé Jégou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez. Aggregating local de- scriptors into compact image representation. In 2010 JEEE computer society conference computer vision and pattern recognition. pp. 3304-3311, IEEE, 2010.
[62] Jing, Jiachen Zhu, and Yann LeCun. arXiv:2206.07700, 2022.
Masked siamese convnets. arXiv preprint
[63] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-90) 90, 2017.
[64] Svetlana Lazebnik, Cordelia Schmid, and Jean Ponce. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. In 2006 IEEE computer society conference on computer vision and pattern recognition (CVPR '66), volume 2. pp. 2169-2178. IEEE, 2006.
[65] Y LeCun. A path towards autonomous machine intelligence. preprint posted openreview, 2022.
[66] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436- 444, 2015.
[67] Ann B Lee, Kim S Pedersen, and David Mumford. The nonlinear statistics of high-contrast patches in natural images. International Journal of Computer Vision, 54(1):83-103, 2003.
[68] Omer Levy and Yoav Goldberg. Linguistic regularities in sparse and explicit word repre- sentations. In Proceedings of the eighteenth conference on computational natural language learning, pp. 171-180, 2014.
[69] Zengyi Li, Yubei Chen, Yann LeCun, and Friedrich T Sommer. Neural manifold clustering and embedding. arXiv preprint arXiv:2201.10000. 2022.
[70] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and San- jeev Arora. Enhanced convolutional neural tangent kernels. arXiv preprint 2019.
[71] Yi Ma. Doris Tsao, and Heung- Yeung Shum. On the principles of parsimony and self- consistency for the emergence of intelligence. Frontiers of Information Technology & Elec- tronic Engineering, 23(9): 1399):298-111
2022.
[72] Stephane G Mallat. A theory for multiresolution signal decomposition: the wavelet repre- sentation. IEEE transactions on pattern analysis and machine intelligence, 11(7):674-66) 693, 1989.
13

---

Published as a conference paper at ICLR 2023
[73] Christopher D. Manning. Human Language Understanding & Reasoning. Daedalus, 151(2): 127-138, 05 2022.
[74] Valerio Mante, Vincent Bonin, and Matteo Carandini. Functional mechanisms shaping lateral geniculate responses to artificial and natural stimuli. Neuron, 58(4):625 638, 2008
[75] Marina Meilä and Jianbo Shi. A random walks view of spectral segmentation. In International Workshop on Artificial Intelligence and Statistics, pp. 203-208. PMLR, 2001.
[76] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Sth International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.neh, 2017.
[77] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint
2013.
[78] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
[79] David Mumford and Agnès Desolneux. Pattern theory: the stochastic analysis of real-world signals. CRC Press, 2010.
[80] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algo- rithm. Advances in neural information processing systems, 14, 2001.
[81] Bruno A Olshausen and David J Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature, 381 (6583):007, 1996.
[82] Bruno A Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision research, 37(23)33311-3325 1997.
[83] Bruno A Olshausen and David J Field. How close are we to understanding v1? Neural computation, 17(8): 166--19999999 2005.
[84] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1xXiv18077003744 2018.
[85] Edouard Oyallon and Stéphane Mallat, Deep roto-translation scattering for object classifica- tion. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2865-2873, 2015.
[86] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLPP), pp. 1532-1543, 2014.
[87] Florent Perronnin, Jorge Sánchez, and Thomas Mensink. Improving the fisher kernel for large-scale image classification. In European conference on computer vision, pp. 143-156.
Springer, 2010.
[88] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pp- 5389-5400. PMLR, 2019.
[89] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2333-2222 2000.
[90] David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back mhok-propggating errors. nature, 323(6088):533-536 1986.
[91] Justyna Sarzynska- Wawer, Aleksander Wawer, Aleksandra Pawlak, Julia Szymanowska, Iz- abela Stefaniak, Michal Jarkiewicz, and Lukasz Okruszek. Detecting formal thought disorder by deep contextualized word representations. Psychiatry Research, 144355, 2021.
14

---

Published as a conference paper at ICLR 2023
[92] Lawrence K Saul and Sam T Roweis. Think globally, fit locally: unsupervised learning of low dimensional manifolds. Journal of machine learning research, (0uu))::1-115:: 2003.
[93] Geoffrey Schiebinger, Martin J Wainwright, and Bin Yu. The geometry of kernelized spectral clustering. The Annals of Statistics, 43(2):819-844 846, 2015.
[94] Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Jonathan Ragan-Kelley, Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference on Machine Learning, pp. 8614-8623. PMLR, 2020.
[95] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905, 2000.
[96] David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Van- dergheynst. The emerging field of signal processing on graphs: Extending high- nigh-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30 09,83-98,44 2013.
[97] Ravid Shwartz-Ziv, Randall Balestriero, and Yann LeCun. What do we maximize in self- supervised learning? arXiv preprint arXiv:2207.1008/ 2022.
[98] Jorge Silva, Jorge Marques, and João Lemos. Selecting landmark points for sparse manifold learning. In Advances neural information processing systems, pp. 1241-1248 2006.
[99] Eero P Simoncelli and William T Freeman. The steerable pyramid: flexible architecture for multi-scale derivative computation. In Proceedings., International Conference on Image Processing, volume 3, pp. 444-447. IEEE, 1995.
[100] Ecro P Simoncelli and Bruno A Olshausen. Natural image statistics and neural representation. Annual review of neuroscience, 24(1):1193-1216, 2001.
[101] Eero P Simoncelli, William T Freeman, Edward H Adelson, and David J Heeger. Shiftable multiscale transforms. IEEE transactions on Information Theory, 38(2):587-607, 1992.
[102] Alex Smola and Bernhard Schölkopf. A tutorial on support vector regression. Statistics and computing, 14(3):19-222,, 2004.
[103] Kihyuk Sohn and Honglak Lee. Learning invariant representations with local transformations. arXiv preprint 1206.62000.644 2012.
[104] X Yu Stella and Jianbo Shi. Multiclass spectral clustering. In Computer Vision, IEEE Inter- national Conference on, volume 2, pp. 313-313. IEEE Computer Society, 2003.
[105] Joshua B Tenenbaum, Vin De Silva, and John Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319 2323, 2000.
[106] Louis Thiry, Michael Arbel, Eugene Belilovsky, and Edouard Oyallon. The unreason- able effectiveness of patches in deep convolutional kemnels methods. arXiv:2101.0752.1 2021.
arXiv preprint
[107] Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning dynamics without contrastive pairs In International Conference on Machine Learning, pp- 10268-10278. PMLR, 2021.
[108] Shimon Ullman. Object recognition and segmentation by fragment- based hierarchy. Trends in cognitive sciences, 11(2):88666 64, 2007.
[109] Max Vladymyrov and Miguel Á Carreira-Perpinán. manifold learning. In Joint European Conference on Machine Learning and Knowledge Dis- covery Databases, pp. 256-271. Springer, 2013.
Perpinán. Locally linear landmarks for large-scale
[110] Martin J. Wainwright, Odelia Schwartz, and Eero P. Simoncelli. Natural image statistics and divisive normalization: Modeling nonlinearity and adaptation in cortical neurons. 2002.
15

---

Published as a conference paper at ICLR 2023
[111] Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas Huang, and Yihong Gong. linear coding for image classification. In 2010 IEEE computer society conference computer vision and pattern recognition, pp- 5360-3361 IEEE, 2010.
[112] Laurenz Wiskott and Terrence Sejnowski. Slow feature analysis: Unsupervised learning of invariances. Neural computation, 14(4):715-770, 2002.
[113] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non-parann pon-mamaetriic instance discrimination. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3733-3742, 2018.
[114] Chun-Hsiao Yeh, Cheng- Yao
Yao Hong, Yen-Chi Hsu, Tyng-Luh Liu, Yubei Chen, and Yann LeCun. Decoupled contrastive learning. arXiv preprint 0rXiv:21 2021.
[115] Kai Yu, Tong Zhang, and Yihong Gong. Nonlinear learning using local coordinate coding. Advances neural information processing systems, 22, 2009.
[116] Zeyu Yun, Yubei Chen, Bruno Olshausen, and Yann LeCun. Transformer visualization via dictionary learning: contextualized embedding as a linear superposition of transformer factors. arXiv preprint arXiv:2 15949, 2021.
[117] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In International Conference Machine Learning, pp. 12310-12320. PMLR, 2021.
[118] Juexiao Zhang, Yubei Chen, Brian Cheung, and Bruno A Olshausen. Word embedding visu- alization via dictionary learning. arXiv preprint arXiv:1910.03833, 2019.
[119] Will Zou, Shenghuo Zhu, Kai Yu, and Andrew Ng. Deep learning of invariant features via simulated fixations in video. Advances in neural information processing systems, 25, 2012.
16

---

Published as a conference paper at ICLR 2023
Appendix
A PROBABILISTIC POINT OF VIEW EXAMPLE: SMT WORD EMBEDDING
(b)
Co-occurence and cosine similarity to word "raccoon"
Co-occurence and cosine similaitty to word "february'
,00g
3530
2011
Jas
polke
1030
10
2026
2012
2000
Co-accunence
her
rort) 1to
Inputation
mill
Co-trcumence
march jonarr
december
bobcats
1230
pebbat
dt
sectember
roverber
october
530
lire
0.4 similarity
0.2 Cosine similarity
36
(c)
Co-occ_rence and casine fimllarity to ward "saatlle'
Ca-ocrurence and casine similarity to word "aspirin"
jinscs
70
Juyer
530
"steer
STACK
marinars
sea 1awks
Co-orcunerce sp-
puch
igurnaa
Srugs
Josprtal
Jacome
Iicloationa
peracetamol
dayton, pittbburgh
denver dalla
beraodiaepiness
Ampheramine
02
02
02
64
85
05
0.7
0.0 04
62
24 Cosine similerity
B3
05
66
63
Cosine similarity
Figure 5: Visualization of SMT word embedding. For each word "raccoon", "February", "Seattle" and "aspirin",, we plot the top 10 words that are closest to it in the embedding space, and we show the top 10 words that co-occur with it the most. Two words are close if the cosine similarity between their SMT embedding is high. The co-occurrence is calculated based on the entire corpus. We count two words that co-occurred once if they appear in the same context window. The co-occurrence is plotted against the cosine similarity.
We use SMT to build word embedding for the vocabulary in WikiText-103 to illustrate the proba- bilistic view of SMT. Unlike in Figure 2 where the neighbor of each data point x can be interpreted as its Euclidean neighborhood, there is no such distance function in the natural language. Never- theless, we could still define neighborhood for each word. We define the neighbor of each word as other words that co-occur with it in given context.
Like the manifold learning view, where the global geometry emerges despite only local neighbor- hoods being used during training, such phenomenon is also observed from the probabilistic point of view. To visualize this phenomenon from a probabilistic point of view, we measure the co- occurrence of each pair of words and the cosine similarity between them in their SMT embedding space. In figure 5 (a), we show the top 10 words that are closest to "raccoon" and the top 10 words that co-occur the most with "raccoon". We can see words like "American," and "population" co- occur with "raccoon" a lot, but neither "American" nor "population" " are close to "raccoon" " in the embedding space. Instead, words that semantically related to "raccoon" are close to "raccoon"
17

---

Published as a conference paper at ICLR 2023
in the embedding space, like "squirrels", "rabbits" and "wolves". even though they rarely co-occur with "raccoon." The underlying reason is that these words share the same context patterns as "rac- co-occur with "raccoon" in phrases
coon". Although words like "American" and "population" like "American raccoon" and "raccoon's 's population," " these words also co-occur with other words in very different contexts. Thus, they could not be embedded be close "raccoon."
We also illustrate three more examples in figure 5 In (b), we see words that occur with "February" other months like "July," "June," and "September." In (c), words co-occur with "Seattle" the most are other large cities like "Dallas", "Denver" and "Pittsburgh", even though they rarely occur with "Seattle." " Finally, in (d), the words co-occur with "aspirin" the most are names of other medicines.
B DETAILS FOR TRAINING WORD EMBEDDING USING SMT
Dataset. We use WikiText-103 corpus 76 to train SMT word embedding, which contains around 103 million tokens. We use "Basic English Tokenizer" from torchtext, which uses minimal text normalization for the tokenizer. We tokenize and lowercase the WikiText- 103 corpus, building vocabulary using the top 33,474 words with the highest frequency. Notice that this dataset is signif- icantly smaller than the Wikipedia dump used to train GLoVe in the original paper (86). Wikipedia also highly biased toward technical subjects, which is reflected in our word embedding.
SMT training. First, we choose the one-hot encoding as the sparse extraction function f. Each token in the text corpus is considered data point e it is first transformed into a one-hot vector by f. then encoded to be close to its neighbor via spectral embedding. In order to perform spectral embedding, we need to define the neighbor(context) for each word in Optimization [ In this case, each word's neighbor(conteex) is its previous four words and the next four words. We "DD""""
then calculate ADD AT, V. and solve Optimization | for P. The representation of each word in the vocabulary is simply each column of P. This is because f is one-hot encoding, for each word oy have 33 (Z)) Pe: = P..
C WHITENING OF THE IMAGE PATCHES
We consider all the square image patches with size T T'xTX where T is patch size, and e is channel size, flattened vectors of dimension 2 We first remove the mean from each patch. Instead of calculating the global mean like in the normal whiteming procedure, we calculate the contextual mean. Let 2, denote image patch and let N₂ {ay j E n(i)} denote the neighboring patch for Jy We can calculate the contextual mean of z; as μ4 [NT ΣjEN, Zy. Let oe denote the mean removed image patch, then o; = I; Mu. We could also simply calculate the global mean μ and use it to center all the image patches. However, we found using contextual mean improve performance.
We apply the whitening operator to the mean mean-removed image patches. Let { denote the pre- processed image patches. Then we have
Al + t
To "unwhiten" the patch for visualization, multiply the whitened patch with the inverse of whiten operator: (XI + )
D 1-SPARSE DICTIONARY LEARNING
Given oi E d to be a data vector, and dictionary (codebook) & E RddK where d is the dimension of the data and K the number of dictionary elements, 1-Sparse Dictionary Learning, also known as Vector Quantization (VQ problem [2)). can be formulated as:
min G,,
| 46
(4)
s.t. |1 = || 1, 2
This is an NP-hard problem, but there efficient heuristic algorithms to approximate the solu- tion. The most well-known one is K-mean clustering, which can be interpreted as an expectation- maximization (EM) algorithm for mixtures of Gaussian distributions. This is the algorithm we used
18

---

Published as a conference paper at ICLR 2023
to solve 1-sparse dictionary learning when we use the 1-sparse feature fug in SMT. The exact algo- rithm we used to solve the 1-sparse dictionary learning problem is in Algorithm|] [ Notice that when data is uniformly distributed on the domain, even a dictionary consisting of uniformly sampled data point serve as a good enough approximation. This is the case for the toy example in Figure 2 In this case, the dictionary & can be predefined instead of learned. For MNIST and CIFAR-10 data, they are both assumed to be low dimensional data manifolds in high dimensional space. Thus, we cannot apply k-mean directly to the raw signal due to the high dimensionality and sparsity of the data. One way to alleviate this problem is to map the data to a unit sphere before applying k-mean. This method called spherical k-mean. More detailed motivations and advantages of this approach are explained in the original paper (30] The exact algorithm is also described in Algorithm
Algorithm 1:
Online 1-sparse dictionary learning heuristic (K-mean clustering)
Data: Data matrix [ ... n. 17 is learning rate.
Result: Dictionary (centroid) Φ = [01, "K]), where each column is dictionary element Sparse code (label)
[0 (0 , a for each data point.
initialization: + 0, A +- 0:
spherical then for i E 1, 1,... do #
Σ |
end end
while not & has not converge do
Find the sparse code for every data point; do
for i 1,...,,.. ,
ai E Eg- = arg max, |1 Fell2
=
11
end
12
Dictionary update;
1 + # E, - s.t. =E=((,a)))
13
14
spherical then
15
for
j 1.... K do 8,
6 1lo,
end
18
end
end
E ABLATION STUDY: FEATURE DIMENSION AND EMBEDDING DIMENSION
analyze how each component of SMT contributes to unsupervised learning. Specifically, we break down SMT into two components: dimensionality expansion using sparse features and dimensionality reduction through spectral embedding. We first show that a sparse feature by itself is important in building a good representation. As shown in Figure 6 we're re able achieve 71 % evaluation accuracy using only general sparse features fog on the CIFAR-10 dataset. Please refer to Section 3 for the definition of general sparse features fog- Combining sparse features with whitening will further boost the performance to 75 %. However, the performance does not increase as the number of features increases if we'r re using only sparse features and whitening. In contrast, if we combine sparse features and spectral embedding, the performance increases the number of features increases. This result implies that spectral embedding is also crucial element in obtaining a good representation.
Since SMT is white box model,
To further show the necessity of spectral embedding, we did an experiment to replace spectral em- bedding with PCA. PCA is a dimension reduction algorithm but does not enforce locality. In Fig- ure/o(b), see that if we're re using PCA dimension reduction, the performance decreases mono- tonically as we reduce the sparse feature to a lower dimension, which implies it is throwing away useful information. On the other hand, for SMT, the performance first increases and then decreases,
19

---

Published as a conference paper at ICLR 2023
80
500. 75.42)
(8192 75.22)
KNN Eval Acc (9)
7B-
KNN Eval Acc (%)
70
500, 59.92)
76-
74-
Sparse feature only
whitening
embedding
Sparse fecture Spectral embedding (SMT)
Sparse feature PCA
10a
30
10:
104
Size of Dictionary
Reduction Dimension (logscale)
Figure 6: Ablation Studies. (a) Evaluation accuracy as a function of dictionary sizes on CIFAR-10 10 dataset. We tried three representations for ablation study purpose. (b) Evaluation accuracy func- tion of reduction dimension on CIFAR-I0 dataset. Reduction dimension corresponds to number of principle components in PCA and embedding dimension in SMT. We general sparse feature foq with threshold set to be 0.3, dictionary of size 8192 and no color augmentation in this experiment.
increase the reduction dimension. The performance of SMT peaks when 500 as the reduction dimension, which is much higher than PCA (79.4% vs 59.9%) with 500 components and even higher than PCA with all principle components (79.4% 75.2%)
F HYPERPARAMETER FOR PRETRAINING DEEP SSL MODEL
For all the benchmark results on the deep SSL model, we follow the pretraining procedure used in solo-learn] Each method is pretrained for 1000 epochs. We list the hyperparameter we used to pretrain each model. For both methods, LARS optimizer, with 10 epochs of warmup follows by a cosine decay. For the SimCLR model, we set the learning rate be 0.4 and weight decay of le-5. We also set the temperature to 0.2, the dimension for the projection output layer to 256, and the dimension of the projection hidden layer to 2048. For VICReg, temperature to 0.2, and set the dimension for the projection output and hidden layer to 2048. We set the weight for similarity loss and variance loss 25, and the weight for covariance loss
resnet-18 the backbone, and a batch size of 256,
set the learning rate 0.3 and weight decay of 1e-4. We also the
We use the transform module in pytorchvision to implement data augmentations. By default, we use "RandomResszeeCroop" with min-scale equal 0.08 and max max-scale equal to 1.0. We also use "RandommHorizontalliii"" and use 0.5 as the flip probability. For "Grayscale Image Only", we apply the "RandomGraysccae"" transform with the grayscale probability to 1. For "Original + Grayscale," we set the grayscale probability to 0.5. For "Full" color data augmentation, we add "ColorJitter." For SimCLR, we use brightness= = 0.8, contrast= 0.8, saturation=O.8, and huc=0.2 as its "ColorJitter" parameter. For VICReg, we use brightness = 0.4, contrast= 0.4, saturation=0.2. hue=0,1 as its "ColorJitter" parameter. We also add additional "Solarization" transform with probability 0.1 for training VICReg.
G ABLATION STUDY: CONTEXT RANGE
Given an image patch [Te} we define its neighbors to be other patches within a specific pixel range from the same image, i.e., n(ij) Im; l - S and jj- j-m] S d). We use to denote the "context range". We showed the impact of context range on MNIST in table The performance of SMT decreases as we increase the context length. We also studied the effect context length on the CIFAR-10
CIFAR-10 10 dataset and showed the result in table Unlike MNIST, the performance dataset increases as the context window increases. This once again confirms that both the manifold view and the probabilistic co-occurrence view are necessary understand SMT. For CIFAR- 10, the images have lots of high-level structures. The key to building a good representation is the ability to model the co-occurrence between different image patches. For example, in an image of animal,
20

---

Published as a conference paper at ICLR 2023
Table Ablation study on the context range used in SMT on CIFAR-10 dataset. We use general sparse feature fay with threshold set to be 0.3, a dictionary of size 8192 and no color augmentation this experiment.
Context Range (d)
4
6
12
24
32
KNN Accuracy
78.0 %
78.5 %
78.5 %
79.0 %
79.4%
Table 6: Ablation study on the number of training examples used in SMT and SimCLR on CIFAR-10 dataset. We use general sparse feature fog with threshold be 0.3, a dictionary of size 8192 and no color augmentation in this experiment. We evaluate both method using soft KNN classifier.
number of training examples
1000
2000
4000
8000
16000
32000
50000
SMT-GQ (8192, no color aug)
58.7 %
63.7 %
67.2 %
70.7 %
74.0 %
77.4 %
79.4 %
SimCLR (ResNet18, color aug) 28.9 %
33.9 %
37.8
41.3
50.1 %
60.4 %
68.3
the animal's "leg" and "head" might lie in two image patches far apart. But it is very important to capture the fact that "leg" and "head" co-occur, because this is a unique trait for animals, which requires the context range be large. This also requires the probabilistic co-occurrence view. Many image patches can be neighbors (co-occur), but they cannot all be encoded to the same point. Instead, if we record the co-occurrence, patches that co-occur more often should be encoded closer than each other. On the other hand, MNIST is closer to a manifold, so co-occurrence is less informative in this case. Modeling co-occurrence between image patches might result in overfitting. In order to form good representation, we need to use small context range to capture slow features. This is a lot like the formulation in the original sparse manifold paper, where they use consecutive video frames to define context, which is essentially a context range of only 2 pixels.
H ABLATION STUDY: NUMBER OF TRAINING EXAMPLES
We experiment with the impact of number of training examples on performance. The experiment is done on the CIFARIO dataset. The result is shown in table The result shows SimCLR experienced a much more significant performance drop compared to SMT when training with a limited amount of data. The significant performance drop of the deep SSL method is likely due to the well-known overfitting problem of complicated models like neural networks. This shows the advantages of SMT as simple white-box model.
I ABLATION STUDY: LINEAR PROBING VS KNN FOR EVALUATION
We experiment with using linear probing for evaluation instead of the KNN classifier. We also exper- iment with the comparison between linear probing and KNN classifiers with a different number of embedding dimensions. As shown in the table 7 with optimal embedding dimension, linear probing accuracy is higher than KNN accuracy (81.0% vs 79.4% ). This implies that the linear layer learned in SMT not optimal for image classification, but it is still pretty good representation for image classification purposes. Most useful information for image classification captured during this un- supervised dimension reduction process. This explains why the optimal embedding dimension is much higher (3200) when using a linear classifier compared to when using a KNN classifier (500).
SOFT KNN EVALUATION
Classic K-nearest-neighhor classifier (hard KNN); for each data point x, which labeled with class, let Mo denote the label of 2, Zz. Then let x(x) = |a(c]] Exjenta) OneHHot(y;), which counts the average number of time x's neighbors belong each class. And soflmar(2(x)).
21

---

Published as a conference paper at ICLR 2023
Table Comparing the performance of using linear probing or KNN classifier for evaluation on CIFAR-10. We use general sparse feature fgr with threshold set to be 0.3, a dictionary of size 8192 and no color augmentation in this experiment.
Embedding dimension
110
210
350
500
800
1600
3200
6400
8192
KNN Accuracy
74.7 %
77.6
78.6 %
79.3 %
79.4 %
79.3 16
79.0
77.9
76.1
75.2
Linear Probing Accurccy
69.0%
74.5
77.0 %
78.6 %
79.7 %
80.2 %
80.8
81.0
80.5
80.4 %
Σ. EXP( 2 This quantity is the estimated conditional probability that the data point x belong to kth class, given temperature T, i.. P(y = k|rr). Finally, we simply assign the class with largest conditional probability as the predicted class label i.e. y(z)) = arg max g(x))x-
Lee ((x)x
expp
Soft K-nearest-neighhor classifier (soft KNN): for a given data point x; instead of using only a's neighbors' class label to estimate the conditional probability, we also we take into account of the co-
sine similarity between x to its neighbors. Instead of having =(xr) [n(z]] Σzjen(a) (ly)))
we have 2(x) = [n(2]] Ex, Em(a) OneHot ot (os The rest of the algorithm is exactly the
same as hard KNN. In all the experiment, we set K = 30 and T = 0.03 for evaluation.
K CONNECTION TO DEEP LATENT- SSL METHOD
The general formulation of SMT, as stated in Section is:
min P s.t. PVP"
(5)
where denotes the sparse representation of the data.
Feature extraction: As discussed in Section 2 sparse features used to capture locality and com- positionality. There's 's also other feature that might be used to serve the same purpose. We can abstract such feature extractor a function f X' A.
Projection: As discussed in Section 2 we assume the sparse feature of the data is a oow-dimessional manifold that lies in high-dimensional space. Thus, seek optimal map that projects the sparse representation to the low dimensional space, such that points that are close in feature space should also be close after the projection. In our setup, optimal projection function, but the projection function does not have to be linear in general. We can abstract this projection function function g A + Z.
linear function approximate this
Let Z = g((())), then SMT objective can be generalized to the following form: min 1.9
|DDI s.t.
zzn =1
Consider the objective for VICReg:
Loic = a max ((())
Σ Cool 2) 1=1,fk
2 E
+EΣ 1,,
Σ jEn(E)
-
2
k=1
where Z = (x(())), and both feature extractor f and projector g are parametrized by neural networks. Like discussed in [4), use friendlier variance loss: replacing the hinge loss at 1 as square loss. We also assume a = B = = for simplicity. Then we have:
d
Lyie E( V(Coo(Z)ur)) k=1
Σ 1
Cou(Z)i
+ 1 Σ Σ N
14--- 2/12
jEn(()
(6)
117
11
Σ
Σ
|| 2,113
jEn(s)
Thus,
min Trmic min 1.9
Σ
Σ
||2 - 22
s.t. 22 =1
5.8
jEn(i)
22

---

Published as a conference paper at ICLR 2023
This is the same objective Eq 1 We can construct D as the same first order derative operator as the one described in Section then we have:
min |I S.t. ZZ =1
fi
With generalized features and projects, can formulate VICReg sparse manifold transform problem. In VICReg, there is no close-form solution since both parameters f and are parametrized by neural networks. They are optimized with a stochastic gradient bescent-based algorithm. As discussed in [4] most SSL models can be reduced into the same form, which means they can all be formulated into SMT objectives.
L INTERPRETING SIMILARITY LOSS AS FIRST-ORDER DIRECTIONAL DERIVATIVE
Similarity can be considered as a first-order directional derivative of the representation transform w.r.t the similarity neighborhoods. A representation transform maps signal vector / into representation embedding B, i.e. g R Rd In SMT, g Pf()). where f is a sparse feature function.
The definition of directional derivative is: Pag(a) lim g(a+Aa)-g(a) ,where à the direction we want to take the derivative and h is the infinitesimal change. In discrete space, we represent the dataset as graph. Each data point a node that connects to its neighbors. As we discussed at the beginning of the paper, "similarity" neighborhoods can be defined by I) temporal co-occurrence, 2) spatial co-oceurrence, 3) local metric neighborhoods in the raw signal space. The direction between two neighboring raw signal points and z, is defined as their direction in the sparse feature space, ie., fzz, fx;). Unlike the real coordinate space, where we can take infinite direct directions each location, with the discrete setting, we can only take finite number of directions each data point (the same number as the number of its neighbors). Moreover, since everything is discrete, the infinitesimal change h
For example, we want to take the directional derivative at point x; and in the direction towards its neighbor Zj. Then we have f(x;) (xx), and
Dag(z,)= Dag(f(zi))
g(S(1, + hd) -(((()))))) h-0
lim
=g(f(x,) (f(x,) -(;;)) g(f(x;))
M VISUALIZATION FOR MISCLASSIFIED EXAMPLE FOR CIFAR-10
We provide the visualization for examples misclassified by our SMT KNN model. In Figure 7 the figure is divided into two panels, with 25 images on the left and 24 images on the right. In the left panel, we show an image being classified on the top left corner and its 24 nearest neighbors. In Figure the image being classified is an image of a "dog". Almost all of its 24 nearest neighbors are "horses." As a result, the "dog" image is misclassified as a "horse". The right panels show the patches with the highest cosine similarity to their corresponding patch in each of the 24 nearest neighbors. One insight we can learn from these visualizations is that these misclassifications are largely due local-part matching. For example, "deer" may look like "horse" except for the "deer horn" parts. However, "deer horn" parts may only contribute a small fraction in the similarity measurement. As result, the nearest neighbors of "deer" may be almost all "horses". To solve this issue, again, we need to have a better understanding of hierarchical representation learning and high-level concept formation.
23

---

Published as a conference paper at ICLR 2023
Figure 7: Misclassified example 1. "deer" image misclassified as horse.
Figure 8: Misclassified example 2. A "dog" image is misclassified horse.
Figure 9: Misclassified example 3. A "deer" image is misclassified as horse.
24


Reviews:
[{"review_id": "mZttRTf07V", "reviewer": "Reviewer_77VK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper provides a method to learn an embedding from sparse coding and dictionary learning through the sparse manifold transform. The authors show that this “white-box model” performs well compared to Deep Learning methods on classical image datasets like MNIST and CIFAR.", "summary_of_the_review": "Even though I think that the 1-sparse case is restrictive and that the paper lacks a bit of experimental grounding and details, the idea seems new and interesting in the context of SSL and dictionary learning, and is worth being highlighted.\n\n------------------------------------\n\nThe authors added relevant details and experiments to the paper, and responded to my requests for clarification.", "strength_and_weaknesses": "**Strengths**\n\nThe method proposed in the paper, which is an extension of SMT, allows to embed data from sparse coding and dictionary learning. The model is interesting because it is simple and seems to work well compared to SOTA Deep Learning methods on classical datasets. This might be of interest for people working on self-supervised learning and dictionary learning on various types of signals.\n\n**Weaknesses**\n\n- The contributions are not always clearly highlighted. I don’t understand whether Part 2 contains new ideas concerning SMT or not. In particular, the authors claim to “revisit the formulation of SMT” in the introduction. Could this be more specific ?\n\n- The authors use 1-sparse sparse coding to learn the dictionary D and the representation codes in the experiments.  As described in the paper, this corresponds to performing a k-means algorithm. Figure 6 in appendix highlights that the number of atoms has to be extremely large (at least 8000 atoms of dimension 32) to achieve optimal performance, and I wonder if this is due to the 1-sparse constraint. Why focusing only on this case? This seems very restrictive, especially for complex data. It would be interesting to increase the number of non zero coefficients (even to consider relaxations of the $\\ell_0$ constraint for efficiency purposes as it seems to be an issue for CIFAR datasets, see Mairal et al. 2009) to see whether this allows to reduce the dimension of the dictionary without impacting the performance in terms of knn accuracy and computation time (same kind of experiments as in Figure 6 in appendix). This might also help doing better than randomized dictionaries in CIFAR experiments. In my opinion, this study would improve the quality of the paper.\n\n- There is no discussion about the impact of the number of samples on performance. Would it be possible (and interesting from the authors point of view) to integrate figures providing the knn accuracy with respect to the number of images to see whether SMT performs well with small datasets compared to baseline methods?\n\nMinor remarks:\n- In Table 2, the authors claim that “the MNIST patch space can be viewed as a 3-manifold”. I don’t understand how this can be inferred from the results shown in the table. Could the authors elaborate on that point ?\n- There is not enough discussion about the impact of the context range, especially in the experiments on CIFAR, and it seems to be an important hyper-parameter of the model. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XhpsZlFhDTQ", "reviewer": "Reviewer_dX2g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the application of the Sparse Manifold Transform (SMT) to image classification problems. The SMT is a shallow transform that first sparsely represents the input data/image in a high-dimensional feature space (via a non-linear mapping) and then linearly embeds these sparse representations in a low-dimensional space. The authors work out the details of how to apply the SMT to image data and evaluate the method on MNIST and CIFAR-10/100, showing good results. In addition, some of the design choices are ablated.", "summary_of_the_review": "The paper makes an interesting attempt at applying the SMT to image classification and shows quite strong results. The overall direction of the paper seems relevant and interesting to me. \n\nThe clarity of the paper could be improved, scaling aspects should be discussed in more detail, and the method should be compared to more related work.", "strength_and_weaknesses": "I think the overall direction of the paper is interesting and exploring ways to construct simple, interpretable models performing competitively with highly-overparameterized, very large models is a worthwhile endeavor. In more detail, I see the following strengths and weaknesses.\n\n*Strengths:*\n- The method is quite simple and produces surprisingly good results given its simplicity.\n- The paper makes a good effort in describing the SMT and giving an intuitive understanding using the manifold disentanglement problem (Figure 2).\n- The paper presents a number of interesting ablations.\n\n*Weaknesses:*\n- As acknowledged by the authors KNN, the reliance of their method on KNN limits the scalability of the method. This could be discussed in more detail: What does this mean in terms of compute and memory requirements? Also, have the authors considered training a small model (linear classifier, MLP) on top of the SMT representation? This could lead to more interesting compute/memory vs accuracy tradeoffs. Also what would be the effect of increasing resolution? The datasets considered by the authors have tiny images.\n -The paper could make a better case for interpretability. Instead of just looking at patches with similar embeddings, what are the nearest neighbors for misclassified examples? Which patches led to misclassification? Is there anecdotal evidence of the SMT allowing us to understand incorrect classifications?\n- There are a number of prior works investigating engineered, principled transforms as a substitute for deep end-to-end learned black-box methods. These usually evaluate on MNIST and CIFAR-10/100, so comparing performance and methods would be possible. For example the scattering transform [a] and kernel methods [b].\n\n\n[a] Oyallon, Edouard, and Stéphane Mallat. \"Deep roto-translation scattering for object classification.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2015.\n\n[b] Shankar, Vaishaal, et al. \"Neural kernels without tangents.\" International Conference on Machine Learning. PMLR, 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "N1fM-arDWGN", "reviewer": "Reviewer_hKPC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper describes a barebones version of unsupervised representation learning framework based on the sparse manifold transform (SMT), which according to the authors, helps in understanding SOTA self-supervised representation learning (SSL) methods (such as VICReg). SMT has two steps: (1) sparse coding to map into a high-dimensional space and (2) manifold learning: a low-dimensional embedding that takes neighborhood/co-occurrence structure into account. Both sparsity (with respect to a dictionary) and local neighborhoods/co-occurrences serve as important features of natural signals like images, and even words (the sparsity is trivial).  While SMT is not a contribution of this paper, they show that SMT produces representations that capture the essence of unsupervised representation learning (SMT is a minimal model in this sense that it is a minimal model that takes both sparsity and neighborhood structure into account). The authors make connections with SOTA by pointing out that a deep neural encoder takes the place of sparse coding and the SMT optimization is very similar to that of VICReg. In principle, even SMT could be stacked in order to produce hierarchical representations that are necessary for larger natural images. Experiments on small-sized images in CIFAR illustrate that even SMT can produce representation that rival the SOTA. \n", "summary_of_the_review": "I think the paper uses SMT which is a simple and easy-to-understand model in a novel setting in order to gain understanding of SSL methods, which is an interesting and important research direction. Experimental results on the small image datasets are convincing and do show that SMT is indeed a strong model in spite of being simple, which is great. However, I have noted some weaknesses that I hope the authors can respond to. Overall, this is a nice paper with interesting ideas and results and I am happy to increase my score based on the authors' response. \n\nUPDATE AFTER AUTHOR RESPONSE:\n\nI greatly appreciate the authors taking the time to significantly edit and improve the paper. Appendix K in particular helps me understand the connection between SMT and VICReg a lot better, and the loss functions indeed are similar. The minimal model does help illustrate that the ideas of SMT are useful in learning good SSL features. How these ideas fully translate to deep models trained with SGD with data augmentations is not clear, but this seems to be a good step in that direction. Perhaps if it is possible to train shallow (a few layers (?)) VICReg and showing the learned features are similar to SMT features in some sense, the connection would be even stronger. Overall, I am increasing my rating and recommending acceptance of the paper. ", "strength_and_weaknesses": "Strengths:\n\n1. The paper studies an important problem which is to provide some understanding of SOTA SSL methods, and proposes to use SMT which is a simple model using a single-level dictionary learning (which is well understood) and a single linear spectral embedding (which is also well understood in manifold learning literature).\n\n2. The paper is written well with ample explanations, connections with plenty of related work and illustration on a toy dataset. \n\n3. Experiments on MNIST and CIFAR show results that to me are surprising. SMT performs comparably with SOTA SSL methods (when some data augmentations are turned off). \n\nWeaknesses:\n\n1. I don't quite understand why SMT cannot work with all data augmentations. Perhaps the authors can explain this point better.\n\n2. Beyond empirical analysis, I am not seeing how this minimal setup is helping explain SOTA SSL methods. If I look at SimCLR, for example, the features are derived at the image level using augmentations as positives and other images as negatives. I don't see that happening with SMT. So, I would appreciate a clearer explanation as to how having this minimal SMT model helps understand SimCLR or VICReg.\n\n3. I think related to (2), maybe a longer discussion on how to connect SMT and VICReg optimization and loss functions more concretely can help. I am not very familiar with VICReg, so I think this would definitely help me. \n\n4. Besides SimCLR and VICReg, there are several other SSL models such as Masked Autoencoders, does SMT also help in understanding these models?\n\n5. Also, are the authors saying that if there is a way to easily stack more layers of SMT in order to learn hierarchical representations, the gap between SMT and VICReg (for example) would not exist?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "BIUCheX9Tm", "reviewer": "Reviewer_iJSh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors leverage the sparse manifold transform (SMT) and provide an insight into its merits on unsupervised learning. The authors show how SMT can be applied to the manifold disentanglement problem. As is pointed out, SMT as a white-box method can be an alternative to black box and self-supervised models building on the principles of parsimony namely sparsity and low-rank.", "summary_of_the_review": "The authors leverage the sparse manifold transform showing its potential as a white-box unsupervised learning method. The main contribution of the paper the use of SMT in manifold disentanglement problem and its probabilistic point of view interpretation for co-occurence modeling. My main comments are the followings:\n\n1) The overall presentation of ideas could be improved making clear the contributions of the current paper (see above).\n2) The experimental results show promising performance of the methods on MNIST and CIFAR datasets. Do the authors believe that a similar performance could be obtained in more complicated and high-dimensional datasets such as IMAGEnet? Specifically, are there any ideas on how to efficiently learn the sparsifying transform in such cases? Also, how practical is the implementation of compositional models that the authors hint on the manuscript?\n3) An  advantage of SMT as compared to alternative SSL methods is its white-box nature. What is the trade-off between the \"simplicity\" of the method and  modifications needed for making it efficient  in more complicated datasets such as IMAGEnet? \n\n\n------------------------------\nPost-rebuttal Update:\nI want to thank the authors for their time and effort in responding to reviewers' comments and addressing their concerns. At this time, I will keep my scope the same.", "strength_and_weaknesses": "Sparse manifold transform is an approach proposed for signal representation in [20]. SMT is a white box method, meaning that it consists of interpretable steps i.e., sparse coding and low-dimensional spectral embedding. The authors build on SMT showing its efficiency in the manifold disentanglement problem. Moreover, they provide experimental results on MNIST, CIFAR10 and CIFAR100 showing promising performance of SMT as compared to SOTA SSL methods e.g. SimCLR and VICReg. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%