Year: 2021

Abstract:
Humans can generalize from only a few examples and from little pre-training on similar tasks. Yet, machine learning (ML) typically requires large data to learn or pre-learn to transfer. Inspired by nativism, we directly model basic human-innate priors in abstract visual tasks e.g., character/doodle recognition. This yields a whitebox model that learns transformation-based topological similarity by mimicking how humans naturally “distort” an object when first seeing it. Using the simple nearest-neighbor classifier in this similarity space, our model achieves human-level character recognition using only 1–10 examples per class and nothing else (no pretraining). This differs from few-shot learning (FSL) using significant pre-training. On standard benchmarks MNIST, EMNIST-letters, and the Omniglot challenge, our model outperforms both neural-network-based and classical ML in the “tiny-data” regime, including FSL pre-trained on large data. Further, mimicking k-means but in a non-Euclidean space, our model enables unsupervised learning and generates human-interpretable archetypes as cluster “centroids”.

heading: 1 INTRODUCTION
text: Modern machine learning (ML) has made remarkable progress, but this is accompanied by increasing model complexity, with hundreds of neural layers (e.g., ResNet-152) and millions of parameters (e.g., AlexNet: 62.3M, VGG16: 138M, BERT: 110M, GTP-3: 175B). This results in a huge appetite for data and increasing difficulty in model interpretability—both for users to understand and for developers to tune (e.g., hyperparameters, architecture). As such, AI researchers have pushed for ML models that are prior- and data-efficient (Chollet, 2019), that are human-like (Lake et al., 2015), and that exhibit human-interpretable behaviors (Adadi & Berrada, 2018).
This poses the fundamental scientific question: How can humans learn so much from so little (May, 2015), whereas ML models, e.g., those achieving near-perfection on MNIST using all 60k training images, deteriorate rapidly as (pre)training reduces? Being data-hungry can pose a real challenge in data-scarce domains, e.g., in a rapidly evolving pandemic or a low-resource environment. Focusing on its scientific contribution, this paper presents a theoretically sound, white-box model that learns like humans do, with initial success on a first set of benchmarks. This includes our state-of-the-art results of hitting 80% / 90% MNIST accuracy using the only first / first four training images per class and achieving 6.75% error (human performance is 4.5%) in the Omniglot one-shot learning challenge without pre-training—one and only one shot.
We follow the nativist principle: given an example, humans make abstractions: we envision an equivalence class of unseen examples, equivalent to the given, in several abstract senses. Many abstraction abilities are inborn in humans and occur unconsciously. When a baby sees a mug, (s)he can immediately recognize it regardless of whether it is translated, rotated, scaled, or deformed. Such abstraction abilities are considered innate as Core Knowledge priors (Spelke & Kinzler, 2007), rather than acquired later in life such as learning that a mug is topologically a doughnut.
We computationally realize the above intuition via our so-called distortable canvas—imagining every image smoothly painted on a rubber canvas that can be distorted in many ways, e.g., bent, stretched, squeezed (Figure 1A). Due to rubber’s viscosity, more distorted canvas transformations expend more energy. This induces a topological similarity, or distance, based on minimal energy: two images are similar if one can almost transform into the other with little distortion (energy). Distance is computed by minimizing color and canvas distortions. In general, visual similarity involves not only a canvas but also a color transformation. Here, we focus on canvas transformations and grayscale images only.
Besides a final desired transformation (and distance), we apply the minimal-energy principle to the entire transformation process, i.e., to keep canvas and color distortions small along the entire optimization process (Mesa et al., 2019). When perceiving a translation, our mind does not process it as a sudden displacement from one location to another, but auto-completes a translation path— continuous and preferably short. Gradient descent naturally fits this goal by always choosing the steepest descent. Yet, it suffers from the curse of local minima. Our solution is to lift gradient descent to multiple levels of abstraction via multiscale canvas lattices and color blurring, mimicking human abstraction ability that is extremely flexible in multiscale optimization. This yields visualizable and interpretable transformation flows (Figure 1B) that either match human intuition (e.g., what humans would naturally do to transform a “7” to a “1”) or provide human intuition to initially nonintuitive settings. The latter case suggests new, human-interpretable transformations: “ah, I did not realize this other way of transforming ‘7’ into ‘1’, but now I see it and it makes perfect sense!”
We show initial success on abstract visual tasks such as character and doodle recognition (future work generalizes to photorealistic images after a preprocessing technique to turn them into abstract doodles or “emojis”). Our model can be used with the simple nearest-neighbor method to classify images and also in a simple k-means style to cluster images. On benchmarks including MNIST (LeCun et al., 1998), EMNIST-letters (Cohen et al., 2017), and the more taxing Omniglot challenge (Lake et al., 2015), running nearest-neighbor on our learned similarity space outperforms both neural-networkbased and classical ML in the “tiny-data” or single-datum regime. This includes beating few-shot models pre-trained on extra background data (which our model does not require). On MNIST, we need one and only one training image per class to hit 80% accuracy and four to hit 90%. In an unsupervised setting, our model enables k-means-like clustering, but on our learned similarity space. We generate archetypes as cluster “centroids”, e.g., different ways of writing “7” or doodling giraffes.
Literature on data scarcity: few-shot learning (FSL). One-/few-shot learning (Lake et al., 2011; Wang et al., 2020) via transfer or meta learning (Pan & Yang, 2009; Finn et al., 2017; Hsu et al., 2019) has achieved impressive success in data-scarce scenarios. FSL’s success relies on the assumption that source and target tasks are similar enough for pre-training to be relevant (Storkey, 2009). However, knowing a priori how relevant the tasks are and understanding what has been pre-learned are often considered “black art”. It remains challenging for FSL practitioners to pick proper source data/models for pre-training so as to transfer most effectively and avoid negative transfer (Pan & Yang, 2009; Meiseles & Rokach, 2020). This is especially the case in new domains (e.g., discovering rising trends) over classical ones (e.g., vision, language). So, rather than “big transfer” (Kolesnikov et al., 2020), the Omniglot challenge urges “small transfer”—advocating reduced pre-training (Lake et al., 2019). This paper follows Omniglot’s pursuit and pushes such reduction to the limit: with absolutely zero pre-training, we still achieved near-human performance and human-interpretability.
Literature on data scarcity: transformation and data augmentation. Our distortable canvas is conceptually akin to other transformation-based models, e.g., optimal-transport maps (Villani, 2009), transformation-induced descriptors (Lowe, 1999) and equivariances (Bronstein et al., 2017). Like all these models, we build transformations into the model rather than into the data as through data augmentation (Krizhevsky et al., 2012). This has the native advantage of harnessing transformational properties directly rather than learning them from data. Models with built-in transformations may be viewed as those perfectly learned from infinitely augmented data. Unlike transformations commonly considered in existing models and data augmentation techniques, we do not encode domain knowledge about preferred transformations such as translation, rotation, or scaling. Instead, our model considers all transformations while still maintaining efficiency via our abstracted gradient descent.

heading: 2 SMOOTH IMAGE ON DISTORTABLE CANVAS
text: We introduce a distortable canvas model: any image is thought of as smoothly painted on a rubber canvas that can be bent, stretched, etc. We further introduce canvas transformations that can flexibly “distort” an image as we naturally simulate in our mind. More specifically, we define a smooth image by a piecewise differentiableM : R2 → R+, where R2 denotes an infinite canvas and R+ denotes color (grayscale in this paper). We define a canvas transformation by α : R2 → R2, which “reshapes” the underlying canvas of a smooth image. Examples include translation, rotation, scaling, and more. We also define a color transformation by χ : R+ → R+, which “repaints” a color. In this paper, we simplify color transformation and only use it to adjust image contrast via affine χ(c) := ac+ b. Nevertheless, we do not restrict canvas transformation, but consider all 2D transformations. Given M, α, χ, the composition χ ◦M ◦ α denotes the transformed image ofM by transformations α, χ. To mimic innate human intuition about topological similarity, we introduce canvas distortion DV (α) for any canvas transformation α and color distortion DC(M,M′) between two smooth images M,M′. Our idea is to search for a transformation that mimics what humans naturally do to transform one image into another. That is, a low-distorted α which makes little difference in color betweenM and the transformedM′, or more precisely, an α that minimizes bothDV (α) andDC(M, χ◦M′◦α). Representating digital and smoothed images. Anm×n digital image is a discrete M : [m]×[n]→ [0, 1], where [k] := {0, 1, . . . , k − 1}. We call [m] × [n] the canvas grid and any z ∈ [m] × [n] a grid point. For any m× n digital image M, we smooth it toM via a sum of kernels:
M(x) := ∑
z∈[m]×[n]
M(z) · κ(ρ(z, x)) for any x ∈ R2, (1)
where a kernel κ : R+ → R+ is a decaying function (e.g., linear, polynomial, Gaussian decay) and ρ is a metric on R2 (e.g., `1, `2, `∞). In this paper, we use linear decay and `∞, i.e., κ(ρ(z, x)) = 1− 1ρc ‖z − x‖∞ if ‖z − x‖∞ < ρc (for some cutoff radius ρc > 0) and κ(ρ(z, x)) = 0 otherwise. Note:M is defined everywhere on R2. This differs from Gaussian blurring as we do not discretize kernels. It is key to use the smoothed image as input, which allows computing gradients analytically. As such, we always smooth any digital image at first and then only manipulate the smoothed image.
Representing arbitrary canvas transformations. We consider all 2D transformations (including those without a formula), but how do we represent them in a computer? With respect to the standard grid [m]× [n], we use the transformed grid α([m]× [n]) to represent α digitally. Thus, any canvas transformation α is digitally represented by ( d=) a matrix α ∈ R(mn)×2 whose ith row is the 2D coordinate of the transformed ith grid point. We use the lexicographical order of a 2D grid, e.g., with respect to [2]× [3], the identify transformation id d= id = [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]]. Any transformed imageM◦α d=M(α) := (M(α0), . . . , M(α(mn−1)) ) ∈ R(mn), i.e., a (vectorized) digital image sampled fromM at the transformed grid α. Representing color and canvas distortions. The color distortionDC measures the color discrepancy between M(id) and M′(α) up to an affine color transformation χ. The canvas distortion DV measures the distortion between the original grid id and the transformed grid α. Formally,
DC(M, χ ◦M′ ◦ α) d= DC(M(id), χ(M′(α)) ) := ‖aM′(α) + b−M(id)‖22 (2)
DV (α) d= DV (id,α) := max {{i,j},{i′,j′}}∈BE ∣∣∣∆α{i,j} −∆α{i′,j′}∣∣∣ , ∆α{i,j} := log ‖αi −αj‖2‖idi − idj‖2 (3)
Here, BE comprises all pairs of neighboring edges in a canvas lattice (introduced below). Eq. (3) is derived from the mathematical definition of distortion of a function by discretizing it across the canvas lattice. This formula measures how far an arbitrary transformation is from being conformal, which is flexible for local isometries and scaling. Given a canvas grid [m]×[n], its corresponding canvas lattice is an undirected graphL = (V,E), with the set of vertices V = [m]×[n] and the set of edges obtained by connecting neighboring vertices in the `∞ sense: E = {{i, j} | ‖vi − vj‖∞ = 1 for vi, vj ∈ V }. We say two edges are neighbors if they form a 45◦ angle (Figure 2).
Computing topological distance by minimizing distortions. To minimize color and canvas distortions (2) and (3), we consider two dual views: minimizingDC among low-distorted α’s or minimizing DV among best-matching α’s. We write the two views as the following two constrained optimization problems, together with their respective unconstrained equivalents: with → 0+ and µ→ 0+,
min. α,χ DC(M, χ ◦M′ ◦ α) s.t. DV (α) ≤ ⇐⇒ min. α,χ DV (α) + µDC(M, χ ◦M′ ◦ α) (4)
min. α,χ DV (α) s.t. DC(M, χ ◦M′ ◦ α) ≤ ⇐⇒ min. α,χ DC(M, χ ◦M′ ◦ α) + µDV (α) (5)
We let the optima D?C for (4) and D?V for (5) denote two versions of our desired topological distance that mimics innate human intuition. We call them DC-distance and DV -distance, respectively. Transformation flow. To obtain both transformations and transformation processes that are humanlike, we run (projected) gradient descent. The iterative gradient steps yield not only a transformation α? in the end but also a transformation flow id = α(0) → α(1) → · · · → α?. The resulting sequence of transformed imagesM′ = M′ ◦ α(0) → M′ ◦ α(1) → · · · → M′ ◦ α? ≈ M (we omit χ for simplicity) makes up an animation (Figure 1), which helps with human intuition on transformingM′ toM. However, directly running (projected) gradient descent on (4) or (5) does not work, because it suffers from the curse of local minima, which we discuss and solve in the next section.

heading: 3 GRADIENT DESCENT AT HIGHER LEVELS OF ABSTRACTION
text: The canvas distortion DV is invariant under a variety of transformations (e.g., DV (α) = 0 for any conformal α), which nicely mimics humans’ flexible transformation options. But this also implies lots of local/global minima and other critical points where the gradient is zero. How much the color distortionDC fluctuates as a function of α depends on the imagesM,M′. But in most cases,DC also has lots of local/global minima, the majority of which represent unwanted “short cuts”—unnatural transformations that make DC → 0 but would break the rubber canvas or create holes in it. The curse of vanishing gradients can freeze gradient descent. To unfreeze it, we lift gradient descent to higher levels, mimicking once again humans’ abstraction power, as our internal optimization system is quite flexible in pursuing “gradient-descent” moves at multiple levels of abstraction. We design two abstraction techniques: a chain of anchor lattices to make hierarchical abstractions of canvas transformations and a chain of color blurring to make hierarchical abstractions of image painting.
Anchor grids and lattices. An anchor grid and its corresponding anchor lattice offer a simpler parameterization (i.e., an abstraction) of canvas transformations. Without such an abstraction, any transformed [m] × [n] grid α ∈ R(mn)×2 consists of 2mn free parameters. So, the optimization problems (4) and (5) are 2mn+2 dimensional, which is not only computationally inefficient for large images but also has too much room for vanishing gradient. We use a simpler α-parameterization that regularizes transformation, lowers distortion, and agrees with our intuition on rubber transformations.
Formally, an anchor system (G, Ĝ) = (M×N, M̂×N̂) uses two layers of grids: an underlying gridG and an anchor grid Ĝ atop, satisfying M̂ ⊆M, N̂ ⊆ N , andG ⊆ ConvexHull(Ĝ). Figure 3A shows
one example, whereG = [5]× [6] = {0, . . . , 4}×{0, . . . , 5} and Ĝ = {0, 2, 4}×{0, 2, 5}. Under an anchor system, we can uniquely represent any grid point g ∈ G via four anchors Ag, Bg, Cg, Dg ∈ Ĝ via proportional interpolation, or more precisely, the following double convex combination
g = (1− λg)(1− νg)Ag + (1− λg)νgBg + λg(1− νg)Cg + λgνgDg. (6) Here, AgBgDgCg can be uniquely selected as the smallest rectangle in Ĝ’s lattice containing g; the two weight parameters λg, νg are computed based on relative position, e.g., as in Figure 3A. The relation between grid points and anchors can be summarized by a weight matrix W ∈ R|G|×|Ĝ|. Its ith row stores weights for the ith grid point (say g in (6)) and contains at most four non-zero entries (i.e., coefficients in (6)) located at the columns corresponding to Ag, Bg, Cg, Dg , respectively.
Given an anchor system (G, Ĝ), any canvas transformation α d= α ∈ R|G|×2 under G and d= α̂ ∈ R|Ĝ|×2 under Ĝ. α̂ is a submatrix of α, which induces an equivalence relation on the set of all canvas transformations: α,β are equivalent iff α̂ = β̂, and α̂ abstracts the equivalence class {β | β̂ = α̂}. Based on the maximum entropy principle (Jaynes, 1957), a reasonable selection of a representative of this equivalence class is W α̂, because W α̂ ∈ {β | β̂ = α̂} and evenly distributes the transformed grid points. Figure 3B illustrates this type of even distribution, which agrees with human intuition on how a rubber surface would naturally react when transforming forces are applied at anchors.
Using an anchor system in optimization problems (4) and (5) adds very little to computing distortions and gradients: we reuse the computation with α = W α̂ and perform only one additional chain-rule step ∂α/∂α̂ = W . By doing so, however, the number of optimization variables in (4) or (5) reduces from |G|+2 to |Ĝ|+2 (e.g., if G = [28]× [28] and Ĝ = {0, 27}×{0, 27}, the number reduces from 1570 to 10). It is important to note that using a simpler anchor grid is not the same as downsampling. If it were, one would plug in α← α̂, but we plug in α← W α̂. In our case, image colors are still sampled from the underlying grid rather than downsampled from the anchor grid. So, using our anchor system is not information lossy while still benefiting from reduced optimization size. Running gradient descent (w.r.t. anchors) in abstracted optimization spaces effectively bypasses critical points.
Blurring. Another view to lifting gradient descent to a high-level, abstracted optimization space, is to blur the image. Intuitively, blurring ignores low-level fluctuation, similar to how humans naturally abstract an image. Blurring helps remedy vanishing gradients and is done in our image smoothing process. The cutoff radius ρc in κ in (1) controls the blurring extent: larger ρc means more blurred.
Guided gradient descent. Mixing the two abstraction techniques yields our guided gradient descent proceeding from higher- to lower-level abstractions. Given an anchor grid Ĝ and a cutoff radius ρc, we denote the corresponding (4) and (5) by DC(Ĝ, ρc) and DV (Ĝ, ρc), respectively. For either, we solve for a (Ĝ, ρc)-solution path, from coarser Ĝ and larger ρc to finer Ĝ and smaller ρc. Let Ĝk be a k × k evenly distributed anchor grid and L̂k be its corresponding lattice. Figure 3C shows a chain of anchor lattices {L̂3i+1}i=0,1,2,... and cutoff radii {ηjρc0}j=0,1,2,.... It is easy initially to align two blurred blobs via small canvas adjustments, implying a small number of iterations to converge to DC ≈ DV ≈ 0. As we proceed along the solution path, the images restore more detail but the finer L̂k helps manage that detail. In a solution path, an earlier solution is used to warm start the subsequent solve step, which further alleviates the curse of vanishing gradients. Notably, even the starting L̂2 comprising only four corner anchors parameterizes a large family of transformations containing all affine transformations. Finer anchor grids/lattices express more flexible transformations (including local, global, piecewise affine, and more), approaching human-level flexibility.
11
12 18
71 83
200+ 200+
200+
Minimum number of training examples /class needed to reach 75%Number of training examples /class (N)
Te st
s et
a cc
ur ac
y
EMNIST-LETTERS EMNIST-LETTERSDc-Nearest-Neighbor
Dv-Nearest-
Neighbor TextCaps
SVM NeuralNetwork
NearestNeighbor RandomForest DecisionTree
Dc-NearestNeighbor Dv-NearestNeighbor TextCaps
SVM NeuralNetwork
NearestNeighbor RandomForest DecisionTree
4
6 28
65 109
183 200+
200+
Minimum number of training examples /class needed to reach 90%Number of training examples /class (N)
Te st
s et
a cc
ur ac
y
MNIST
MNIST +data augmen t
transfer learn ing
CNN+dro pout
Capsu le+Sia
mese
Figure 4: MNIST (10 classes) in the tiny-data regime: first 1–20 training images per class and full test set (examples shown on top). For each model listed in the legend, we plot its test accuracy versus the training size N (bottom left) and also the smallest N needed to reach a threshold of 90% accuracy (bottom right). Our model outperforms all other models for all N ∈ {1, . . . , 20}, requiring the fewest training examples (first four or six per class) to reach 90% accuracy.
11
12 18
71 83
200+ 200+
200+
Minimum number of training examples /class needed to reach 75%Number of training examples /class (N)
Te st
s et
a cc
ur ac
y
EMNIST-LETTERS EMNIST-LETTERSDc- r t-Neigh Dv-Nearest-
Neighbor TextCaps
SVM NeuralNetwork
NearestNeighbor RandomForest DecisionTree
Dc- r tNeigh Dv-NearestNeighbor TextCaps
SVM NeuralNetwork
NearestNeighbor
RandomForest
DecisionTree
4
6 28
65 109
183
200+
200+
Minimum number of training examples /class needed to reach 90%Number of training examples /class (N)
Te
st
s et
a cc
ur ac
y
MNIST
MNIST +data augmen t
transfer learn ing
CNN+dro pout
Capsu le+Sia
mese
Figure 5: EMNIST-letters (26 classes) in the tiny-data regime: first 1–20 training images per class and full test set (examples shown on top). Results are shown in the same way as in Figure 4. Our model outperforms all other models for all N ∈ {1, . . . , 20}, requiring the fewest training examples (first eleven or twelve per class) to reach 75% accuracy (due to increased difficulty in this dataset).

heading: 4 IMAGE CLASSIFICATION IN THE TINY DATA REGIME
text: We use our learned DC - / DV -distance in the simplest nearest-neighbor method to classify grayscale images, namedDC - /DV -nearest-neighbor. The whole process of metric learning and classification is human intuitive and interpretable. We show classification performances on three standard benchmarks: the MNIST and EMNIST datasets of handwritten digits and letters restricted to the tiny-data regime, as well as the Omniglot challenge.
MNIST in the tiny-data regime. The original benchmark has 60k images for training and 10k for testing, spanning 10 classes. To evaluate how a model performs in the tiny data regime, we train the model on the first N images per class from the original training set, test it on the full test set, and record test accuracy versusN = 1, 2, 3, . . .. We compare our model to both neural-network-based and classical ML models, including TextCaps (Jayasundara et al., 2019) with state-of-the-art performance in the small-data regime, SVM, nearest neighbor, etc. Classical ML is included to show that nailing the tiny-data regime does not mean just using simple models. For stochastic models, we record mean and standard deviation from 5 independent runs. TextCaps only runs when N ≥ 4 and sometimes returns a random guess (10%), so, we record trimmed mean and standard deviation from 11 runs (where we trim the best two and worst four). We also copy results from other references that ran MNIST in a similar tiny-data setting, including FSL that uses extra data for pre-training (whereas all our other selected models do not). These results are from the same training-testing sizes but not the same data sets, and hence, are considered indirect comparisons. We present all results in Figure 4.
EMNIST-letters in the tiny-data regime. The original benchmark has 4.8k training images per class and 0.8k test images per class, spanning 26 classes of case-insensitive English letters. We keep the same experimental setting as in MNIST (except for TextCaps being more stable now: we do 7 independent runs for each N and trim the best and the worst). Results are shown in Figure 5. EMNIST-letters is harder, not only with more classes but also more intrinsic ambiguities, e.g., an l and an I can look identical, so can an h and an n when written carelessly. Hence, all models perform significantly worse than in MNIST. The intrinsic ambiguity, as well as more labeling errors, narrows our superiority over other models as training size increases. This is especially true for the state-ofthe-art TextCaps model, catching up quickly in Figure 5. Being sensitive to ambiguities and outliers, however, is not a deficiency of our distortable canvas model, but a property of nearest-neighbor. To improve, we may integrate our model with more robust classifiers, e.g., k-nearest-neighbor (k-NN) with proper voting. However, k-NN is not applicable in the tiny-data regime, not only because the training size can be as small as k but also there is little room to hold out a validation set for selecting k. An adaptive k-NN may be desired, with k remaining 1 in the tiny-data regime and becoming tunable when training size increases to a level that affords a held-out validation set. A related issue due to lacking validation data is about picking a proper model configuration. One may expect better results from any selected model in Figures 4 and 5 by attempting new configurations. Yet, it is unclear what heuristics one may use. For TextCaps, we used its original implementation and configuration; for the rest, we used scikit-learn implementations with default configurations (except for small tweaks for the tiny-data regime e.g., neural-network size and stronger regularization). By contrast, our distortable canvas model requires little to tune, other than the (Ĝ, ρc)-solution path. Theoretically, the more gradual the path, the better. We picked (Ĝ, ρc) based on only image size (28 here) and runtime.
The Omniglot challenge for one-shot classification. The Omniglot dataset contains handwritten characters from 50 different alphabets, which include historical, present, and artificial scripts (e.g., Hebrew, Korean, “Futurama”) and thus, are far more complex than MNIST digits and EMNIST letters. The characters are stored as both images and stroke movements. Unlike MNIST/EMNIST coming with large training data, the Omniglot challenge was specially designed for human-level concept learning from small data. Its one-shot classification task was benchmarked to evaluate how humans and machines can learn from a single example. This benchmark contains 20 independent runs of 20-way within-alphabet classifications. The (2k − 1)th and (2k)th runs for k = 1, . . . , 10 use the same set of 20 characters from a single alphabet. Each run uses 40 images: one training and one test image per character. The unit task here is to predict for each test image, the character class to which it belongs (one of 20), based on the 20 training images. In total, there are 400 independent unit tasks across all 20 runs. Figure 6A shows a unit task (in red) and the first two runs in the benchmark, covering 1 alphabet, 20 characters, and 80 distinct images.
The Omniglot benchmark adopted the standard FSL setting, where it also provided a background set for pre-training. The original background set contains 964 character classes from 30 alphabets; a reduced background set was proposed later to make the classification task more challenging. We run our DC-nearest-neighbor without any background set or any stroke-movement information. In
other words, in each unit task, we predict the test image based on one and only that training image per character, and we read all images from their raw pixels. Shown in Figure 6B, our model (with a 6.75% error rate) approaches human performance (4.5%) and outperforms all models in the Omniglot leaderboard (Lake et al., 2019), except for BPL specially designed for the Omniglot challenge by making additional use of both the background set and the stroke-movement information.

heading: 5 UNSUPERVISED LEARNING: ARCHETYPE GENERATION
text: Beyond use with a classifier, our distortable canvas model can also perform k-means-style clustering, but within its human-intuitive topological similarity landscape. As in other metric learning and non-Euclidean settings (Cuturi & Doucet, 2014), a naive way of explicitly computing distances and then running k-means is not realistic. Learning distance in our model requires solving an optimization problem, which is not as cheap as computing Euclidean distance. Further, computing a “centroid” in non-Euclidean space requires solving another optimization problem (i.e., minimizing the sum of within-cluster distances)—so an optimization problem of optimization problems—which is not as simple as an arithmetic mean. Our idea of transformation flow between two images can be extended to multi-flows among multiple images. Under this multi-flow extension, we do not explicitly compute pairwise distances, i.e., we do not solve the inner optimizations first. Instead, we solve the inner and outer optimizations at the same time, flattening the nested optimizations into a single one. Formally, given N imagesM1, . . . ,MN , to cluster them into K clusters, we solve
minimize α1,...,αN α1,...,αK C1,...,CK
K∑ k=1 ∑ i∈Ck DC(Mk ◦ αk, Mi ◦ αi) subject to N∑ i=1 DV (αi) ≤ , (7)
where Ck denotes the kth cluster,Mk ◦ αk denotes the kth centroid, andMi ◦ αi denotes the ith transformed image flowing to its corresponding centroid together with all other N − 1 transformed images. One can check (7) is an extension of (4) where we omitted χ for simplicity. Solving (7) is similar to k-means via alternating refinement: the assignment step assigns each transformed image Mi ◦αi to Ck? according to k? = arg mink=1,...,K DC(Mk ◦αk, Mi ◦αi); the update step solves (7) for one gradient-descent step given the Cks. Upon convergence, we obtain C?1 , . . . , C ? K as clusters andM1 ◦ α1, . . . ,MK ◦ αK as centroids. We treat the learned centroids as archetypes of the N images given at the beginning, which may be further deployed for education purposes.
We run the above procedure to generate archetypes of a particular image class. Like common practices used in k-means, we try different k. For each k, we try multiple random starts and record the best within-cluster sum of distances (WCSD). We use the elbow method to pick good values for k. Figure 7 shows the WCSD-versus-k curve obtained by running our clustering method on a set of 16 images of “7”s from MNIST. The curve indicates k = 2 or 3 as a potential elbow point. The resulting two clusters of “7” agree with human intuition regarding two general ways of writing “7”, depending on whether there is an extra stroke. The resulting three clusters further divide the cluster of “simpler 7s” based on the angle of the transverse stroke. Moving away from more strict symbol systems towards
free-form art, we try our model on doodle data where people were tasked with freely drawing abstract sketches of real-world objects. Figure 7 also shows four ways of doodling a giraffe, learned from the first 16 giraffes in Google’s Quick Draw dataset (Jongejan et al., 2016). The four learned archetypes cleanly separate outline sketches, pose orientations, as well as focused views of the neck.

heading: 6 CONCLUSION, LIMITATION, AND FUTURE WORK
text: Focusing on its scientific contribution, this paper designs a human-intuitive model from first principles to learn from few and only those few shots—in particular one and only one shot—requiring no extra data for pre-training. Based on nativism, our introduced distortable canvas effectively models humans’ topological intuition and learns transformation-based visual similarity akin to how humans naturally “distort” objects for comparison. This notion of similarity is formalized in our proposed optimization problem, which minimizes canvas and color distortions so as to transform one object to another with minimal distortion. To remedy vanishing gradients and solve the optimization efficiently, we mimic human abstraction ability by chaining anchor lattices and image blurs into a solution path. This yields our gradient descent method capable of optimizing at multiple levels of abstraction. Our model outputs not only transformations but also transformation flows that mimic human thought processes. We demonstrate initial empirical success in a first set of benchmarks focused on abstract visual tasks such as character and doodle recognition. By simply using 1-NN, we achieved state-of-the-art results in the tiny-data and single-datum regime on MNIST/EMNIST and achieved near-human performance in the Omniglot challenge. Our model also enables k-means-style clustering to generate humaninterpretable archetypes. This paper is a first step towards a general theory of a comprehensive, human-like framework for human-level performance in diverse applications. The current paper focuses on an initial scope, but opens the pathway to future generalizations as detailed below.
Consider two general types of images: 1) images of abstract patterns, or abstract images, e.g., those of symbols and doodles; 2) photorealistic images of real-world objects, or real-world images, e.g., those in CIFAR10/100 (Krizhevsky & Hinton, 2009). This paper focuses on the first type, handling abstract images only, by modeling humans’ distortion-based intuition. For real-world images, it may be more efficient to first model cognitive simplification and then apply our current distortion model. It is a reasonable assumption that humans have evolved to classify real-world images by first converting them into abstract icons, or “e (picture)+moji (character)”s (e.g., the emoji of a face, the outline of a mountain, the shape of a lake) and then comparing these simplifications. Following this, an efficient way to apply our method to real-world images is to follow this pipeline—preprocessing them first into “emojis” and then comparing “emojis” using our distortion model. In fact, abstract images (e.g., doodles of giraffes, hieroglyphics) are those that can be treated as “emojis” already. There are baselines to attempt first, e.g., smart edge detectors (Xie & Tu, 2015), but the human visual system does more than edge detection. In the future, we will work on a complete theory of icon or “emoji” creation mimicking human capacity and deal with real-world images, 3D objects, and more.
Although our model has shown dominant classification performance in the tiny-data regime of the presented benchmarks, its dominance diminishes when training size increases. This is due to 1-NN being 100% biased towards the “nearest neighbor” and hence fragile against noisy, erroneous, and ambiguous training examples. This suggests another future direction: our distortable canvas model may be designed jointly with a new, human-like classifier that introduces a small amount of learning into classification. The goal is to achieve state-of-the-art results on all training sizes, which is not merely about swapping in and out existing classifiers. We will not be using black-box models, but maintain model interpretability by modeling “the direct human way”, where we learn (from a small training set) a particular function to be integrated into our distortion formulas. We will introduce such functions in future work and continue to improve them. Figure 8 summarizes the pipeline for generalizing our current distortable canvas model into the future directions sketched above.

Review summaries:
This paper proposes a method that models the visual difference between images as a topological transformation for images. Using this model and computing the topological distance by minimizing the distortions between imagers, one can find neighbors that are conceptually similar to the input image. Evaluation results show that this simple method can achieve strong performance when only very few samples are available and no pretraining is allowed.

**Summary**  The authors propose a white-box model that uses a similarity score in a space that is constructed based on topological transformation. In other words, two data points are close to each other if you can transform them into each other. To achieve this, they first compute the topological distance with training data points while minimizing the distortions (this part was a little bit unclear to me. I would appreciate it if the authors provide more context or examples of this). They use an interesting idea of using gradient descent to find a sequence of transformation which is the main reason that contributes to having a white-box model. I found this part of the paper very interesting and novel. Finally, it is not possible to apply this method at the pixel level. So they propose using a chain of lattices to be able to apply their technique in higher abstractions.    

The paper on hand tackles the problem of learning from very few samples, which is of high relevance for many machine learning problems. To this end, an approach to model transformation-based topological similarity is introduced, allowing for covering many kinds of invariants in image data. The approach is demonstrated for well-known benchmark datasets for different classification models, demonstrating that in this way just using a small number of samples competitive classification results can be obtained.

This paper proposes a novel white-box model for one or few-shot learning, which tries to simulate the human recognition ability for “distort” objects. The authors use transformation-based topological similarity to build the model and propose an anchor system with gradient descent to train their models. Extensive experiments on standard character recognition benchmarks demonstrate the proposed method outperforms the classical machine learning methods with very limited training data, such as less than 20.