Long-Tailed Learning Requires Feature Learning

Part of the motivation for deploying a neural network arises from the belief that algorithms that learn features/representations generalize better than algorithms that do not. We try to give some mathematical ballast to this notion by studying a data model where, at an intuitive level, a learner succeeds if and only if it manages to learn the correct features. The data model itself attempts to capture two key structures observed in natural data such as text or images. First, it is endowed with a latent structure at the patch or word level that is directly tied to a classification task. Second, the data distribution has a long-tail, in the sense that rare and uncommon instances collectively form a significant fraction of the data. We derive non-asymptotic generalization error bounds that quantify, within our framework, the penalty that one must pay for not learning features.

We first prove a two part result that quantifies precisely the necessity of learning features within the context of our data model. The first part shows that a trivial nearest neighbor classifier performs perfectly when given knowledge of the correct features. The second part shows it is impossible to a priori craft a feature map that generalizes well when using a nearest neighbor classification rule. In other words, success or failure depends only on the ability to identify the correct features and not on the underlying classification rule. Since this cannot be done a priori, the features must be learned.

Our theoretical results therefore support the idea that algorithms cannot generalize on long-tailed data if they do not learn features. Nevertheless, an algorithm that does learn features can generalize well. Specifically, the most direct neural network architecture for our data model generalizes almost perfectly when using either a linear classifier or a nearest neighbor classifier on the top of the learned features. Crucially, designing the architecture requires knowing only the meta structure of the problem, but no a priori knowledge of the correct features. This illustrates the built-in advantage of neural networks; their ability to learn features significantly eases the design burden placed on the practitioner.

Subcategories in commonly used visual recognition datasets tend to follow a long-tailed distribution [25, 28, 11]. Some common subcategories have a wealth of representatives in the training set, whereas many rare subcategories only have a few representatives. At an intuitive level, learning features seems especially important on a long-tailed dataset since features learned from the common subcategories help to properly classify test points from a rare subcategory. Our theoretical results help support this intuition.

We note that when considering complex visual recognition tasks, datasets are almost unavoidably long-tailed [19] — even if the dataset contains millions of images, it is to be expected that many subcategories will have few samples. In this setting, the classical approach of deriving asymptotic performance guarantees based on a large-sample limit is not a fruitful avenue. Generalization must be approached from a different point of view (c.f. [10] for very interesting work in this direction). In particular, the analysis must be non-asymptotic. One of our main contribution is to derive, within the context of our data model, generalization error bounds that are non-asymptotic and relatively tight — by this we mean that our results hold for small numbers of data samples and track reasonably well with empirically evaluated generalization error.

In Section 2 we introduce our data model and in Section 3 we discuss our theoretical results. For the simplicity of exposition, both sections focus on the case where each rare subcategory has a single representative in the training set. Section 4 is concerned with the general case in which each rare subcategory has few representatives. Section 5 provides an overview of our proof techniques. Finally, in Section 6, we investigate empirically a few questions that we couldn’t resolve analytically. In particular, our error bounds are restricted to the case in which a nearest neighbor classification rule is applied on the top of the features — we provide empirical evidence in this last section that replacing the nearest neighbor classifier by a linear classifier leads to very minimal improvement. This further support the notion that, on our data model, it is the ability to learn features that drives success, not the specific classification rule used on the top of the features.

Related work. By now, a rich literature has developed that studies the generalization abilities of neural networks. A major theme in this line of work is the use of the PAC learning framework to derive generalization bounds for neural networks (e.g. [6, 21, 14, 4, 22]), usually by proving a bound on the difference between the finite-sample empirical loss and true loss. While powerful in their generality, such approaches are usually task independent and asymptotic; that is, they are mostly agnostic to any idiosyncrasies in the data generating process and need a statistically meaningful number of samples in the training set. As such, the PAC learning framework is not well-tailored to our specific aim of studying generalization on long-tailed data distributions; indeed, in such setting, a rare subcategory might have only a handful of representatives in the training set.

After breakthrough results (e.g. [15, 9, 3, 16]) showed that vastly over-parametrized neural networks become kernel methods (the so-called Neural Tangent Kernel or NTK) in an appropriate limit, much effort has gone toward analyzing the extent to which neural networks outperform kernel methods [27, 26, 24, 12, 13, 17, 1, 2, 18, 20]. Our interest lies not in proving such a gap for its own sake, but rather in using the comparison to gain some understanding on the importance of learning features in computer vision and NLP contexts.

Analyses that shed theoretical light onto learning with long-tailed distributions [10, 7] or onto specific learning mechanisms [17] are perhaps closest to our own. The former analyses [10, 7] investigate the necessity of memorizing rare training examples in order to obtain near-optimal generalization error when the data distribution is long-tailed. Our analysis differs to the extent that we focus on the necessity of learning features and sharing representations in order to properly classify rare instances. Like us, the latter analysis [17] also considers a computer vision inspired task and uses it to compare a neural network to a kernel method, with the ultimate aim of studying the learning mechanism involved. Their object of study (finding a sparse signal in the presence of noise), however, markedly differs from our own (learning with long-tailed distributions).

We begin with a simple example to explain our data model and to illustrate, at an intuitive level, the importance of learning features when faced with a long-tailed data distribution. For the sake of exposition we adopt NLP terminology such as ‘words’ and ‘sentences,’ but the image-based terminology of ‘patches’ and ‘images’ would do as well.

The starting point is a very standard mechanism for generating observed data from some underlying collection of latent variables. Consider the data model depicted in Figure 1. We have a vocabulary of $n_{w}=12$ words and a set of $n_{c}=3$ concepts:

The $12$ words are partitioned into the $3$ concepts as shown on the left of Figure 1. We also have $6$ sequences of concepts of length $L=5$. They are denoted by ${\bf c}_{1},{\bf c}_{2},{\bf c}_{3}$ and ${\bf c}^{\prime}_{1},{\bf c}^{\prime}_{2},{\bf c}^{\prime}_{3}$. Sequences of concepts are latent variables that generate sequences of words. For example

The sequence of words on the right was obtained by sampling each word uniformly at random from the corresponding concept. For example, the first word was randomly chosen out of the dairy concept (butter, cheese, cream, yogurt), and the last word was randomly chosen out of the vegetable concept (potato, carrot, leek, lettuce.) Sequences of words will be referred to as sentences.

The non-standard aspect of our model comes from how we use the ‘latent-variable $\to$ observed-datum’ process to form a training distribution. The training set in Figure 1 is made of $15$ sentences split into $R=3$ categories. The latent variables ${\bf c}^{\prime}_{1},{\bf c}^{\prime}_{2},{\bf c}^{\prime}_{3}$ each generate a single sentence, whereas the latent variables ${\bf c}_{1},{\bf c}_{2},{\bf c}_{3}$ each generate $4$ sentences. We will refer to ${\bf c}_{1},{\bf c}_{2},{\bf c}_{3}$ as the familiar sequences of concepts since they generate most of the sentences encountered in the training set. On the other hand ${\bf c}^{\prime}_{1},{\bf c}^{\prime}_{2},{\bf c}^{\prime}_{3}$ will be called unfamiliar. Similarly, a sentence generated by a familiar (resp. unfamiliar) sequence of concepts will be called a familiar (resp. unfamiliar) sentence. The former represents a datum sampled from the head of a distribution while the latter represents a datum sampled from its tail. We denote by ${\bf x}_{r,s}$ the $s^{th}$ sentence of the $r^{th}$ category, indexed so that the first sentence of each category is an unfamiliar sentence and the remaining ones are familiar.

Suppose now that we have trained a learning algorithm on the training set described above and that at inference time we are presented with a previously unseen sentence generated by the unfamiliar sequence of concept ${\bf c}^{\prime}_{1}=[\text{dairy},\text{dairy},\text{veggie},\text{meat},\text{veggie}]$. To fix ideas, let’s say that sentence is:

This sentence is hard to classify since there is a single sentence in the training set that has been generated by the same sequence of concepts, namely

Moreover these two sentences do not overlap at all (i.e. the $i^{th}$ word of ${\bf x}^{\text{test}}$ is different from the $i^{th}$ word of ${\bf x}_{1,1}$ for all $i$.) To properly classify ${\bf x}^{\text{test}}$, the algorithm must have learned the equivalences butter $\leftrightarrow$ cheese, yogurt $\leftrightarrow$ butter, carrot $\leftrightarrow$ lettuce, and so forth. In other words, the algorithm must have learned the underlying concepts.

Nevertheless, a neural network with a well-chosen architecture can easily succeed at such a classification task. Consider, for example, the network depicted on Figure 2. Each word of the input sentence, after being encoded into a one-hot-vector, goes through a multi-layer perceptron (MLP 1 on the figure) shared across words.

The output is then normalized using LayerNorm [5] to produce a representation of the word. The word representations are then concatenated into a single vector that goes through a second multi-layer perceptron (MLP 2 on the figure). This network, if properly trained, will learn to give similar representations to words that belong to the same concept. Therefore, if it correctly classifies the train point ${\bf x}_{1,1}$ given by (2), it will necessarily correctly classify the test point ${\bf x}^{\text{test}}$ given by (1). So the neural network is able to classify the previously unseen sentence ${\bf x}^{\text{test}}$ despite the fact that the training set contains a single example with the same underlying sequence of concepts. This comes from the fact that the neural network learns features and representations from the familiar part of the training set (generated by the head of the distribution), and uses these, at test time, to correctly classify the unfamiliar sentences (generated by the tail of the distribution). In other words, because it learns features, the neural network has no difficulty handling the long-tailed nature of the distribution.

To summarize, the variables $L,n_{w},n_{c},R$ and $n_{\text{spl}}$ parametrize instances of our data model. They denote, respectively, the length of the sentences, the number of words in the vocabulary, the number of concepts, the number of categories, and the number of samples per category. So in the example presented in Figure 1 we have $L=5$, $n_{w}=12$, $n_{c}=3$, $R=3$ and $n_{\text{spl}}=5$ (four familiar sentences and one unfamiliar sentence per category). The vocabulary $\mathcal{V}$ and set of concepts $\mathcal{C}$ are discrete sets with $|{\mathcal{V}}|=n_{w}$ and $|\mathcal{C}|=n_{c}$, rendered as $\mathcal{V}=\{1,\ldots,n_{w}\}$ and $\mathcal{C}=\{1,\ldots,n_{c}\}$ for concreteness. A partition of the vocabulary into concepts, like the one depicted at the top of Figure 1, is encoded by a function $\varphi:\mathcal{V}\to\mathcal{C}$ that assigns words to concepts. We require that each concept contains the same number of words, so that $\varphi$ satisfies

and we refer to such a function $\varphi:\mathcal{V}\to\mathcal{C}$ satisfying (3) as equipartition of the vocabulary. The set

denotes the collection of all such equipartitions, while the data space and latent space are denoted

respectively. Elements of $\mathcal{X}$ are sentences of $L$ words and they take the form ${\bf x}=[x_{1},x_{2},\ldots,x_{L}],$ while elements of $\mathcal{Z}$ take the form ${\bf c}=[c_{1},c_{2},\ldots,c_{L}]$ and correspond to sequences of concepts.

In the context of this work, a feature map refers to any function $\psi:{\mathcal{X}}\mapsto\mathcal{F}$ from data space to feature space. The feature space $\mathcal{F}$ can be any Hilbert space (possibly infinite dimensional) and we denote by $\langle\cdot,\cdot\rangle_{\mathcal{F}}$ the associated inner product. Our analysis applies to the case in which a nearest neighbor classification rule is applied on the top of the extracted features. Such rule works as follow: given a test point ${\bf x}$, the inner products $\langle\psi({\bf x}),\psi({\bf y})\rangle_{\mathcal{F}}$ are evaluated for all ${\bf y}$ in the training set; the test point ${\bf x}$ is then given the label of the training point ${\bf y}$ that led to the highest inner product.

Our main result states that, in the context of our data model, features must be tailored (i.e. learned) to each specific task. Specifically, it is not possible to find a universal feature map $\psi:{\mathcal{X}}\to\mathcal{F}$ that performs well on a collection of tasks like the one depicted on Figure 1. In the context of this work, a task refers to a tuple

that prescribes a partition of the vocabulary into concepts, $R$ familiar sequences of concepts, and $R$ unfamiliar sequences of concepts. Given such a task $\mathcal{T}$ we generate a training set $S$ as described in the previous section. This training set contains $R\times n_{spl}$ sentences split over $R$ categories, and each category contains a single unfamiliar sentence. Randomly generating the training set $S$ from the task $\mathcal{T}$ corresponds to sampling $S\sim\mathcal{D}_{\mathcal{T}}^{\text{train}}$ from a distribution $\mathcal{D}_{\mathcal{T}}^{\text{train}}$ defined on the space $\mathcal{X}^{R\times n_{spl}}$ and parametrized by the variables in (4) (the appendix provides an explicit formula for this distribution). We measure performance of an algorithm by its ability to generalize on previously unseen unfamiliar sentences. Generating an unfamiliar sentence amounts to drawing a sample ${\bf x}\sim\mathcal{D}_{\mathcal{T}}^{\text{test}}$ from a distribution $\mathcal{D}_{\mathcal{T}}^{\text{test}}$ on the space $\mathcal{X}$ parametrized by the variables $\varphi,{\bf c}^{\prime}_{1},\ldots,{\bf c}^{\prime}_{R}$ in (4) that determine unfamiliar sequences of concepts. Finally, associated with every task $\mathcal{T}$ we have a labelling function $f_{\mathcal{T}}:{\mathcal{X}}\to\{1,\ldots,R\}$ that assigns the label $r$ to sentences generated by either ${\bf c}_{r}$ or ${\bf c}_{r}^{\prime}$ (this function is ill-defined if two sequences of concepts from different categories are identical, but this issue is easily resolved by formal statements in the appendix). Summarizing our notations, for every task $\mathcal{T}\in\Phi\times\mathcal{Z}^{2R}$ we have a distribution $\mathcal{D}_{\mathcal{T}}^{\text{train}}$ on the space $\mathcal{X}^{R\times n_{spl}}$, a distribution $\mathcal{D}_{\mathcal{T}}^{\text{test}}$ on the space $\mathcal{X}$, and a labelling function $f_{\mathcal{T}}.$

Given a feature space $\mathcal{F}$, a feature map $\psi:{\mathcal{X}}\to\mathcal{F}$, and a task $\mathcal{T}\in\Phi\times\mathcal{Z}^{2R}$, the expected generalization error of the nearest neighbor classification rule on unfamiliar sentences is given by:

For simplicity, if the test point has multiple nearest neighbors with inconsistent labels in the training set (and so the $\arg\max$ returns multiple training points ${\bf y}$), we will count the classification as a failure for the nearest neighbor classification rule. We therefore replace (5) by the more formal (but more cumbersome) formula

to make this explicit. Our main theoretical results concern performance of a learner not on a single task $\mathcal{T}$ but on a collection of tasks $\mathfrak{T}=\{\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{N_{\text{tasks}}}\},$ and so we define

as the expected generalization error on such a collection $\mathfrak{T}$ of tasks. As a task refers to an element of the discrete set $\Phi\times\mathcal{Z}^{2R}$, any subset $\mathfrak{T}\subset\Phi\times\mathcal{Z}^{2R}$ defines a collection of tasks. Our main result concerns the case where the collection of tasks $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$ consists in all possible tasks that one might encounter. For concreteness, we choose specific values for the model parameters and state the following special case of our main theorem (Theorem 3 at the end of this section) —

In other words, for the model parameters specified above, it is not possible to design a ‘task-agnostic’ feature map $\psi$ that works well if we are uniformly uncertain about which specific task we will face. Indeed, the best possible feature map will fail at least $98.4\%$ of the time at classifying unfamiliar sentences (with a nearest-neighbor classification rule), where the probability is with respect to the random choices of the task, of the training set, and of the unfamiliar test sentence.

Interpretation: Our desire to understand learning demands that we consider a collection of tasks rather than a single one, for if we consider only a single task then the problem, in our setting, becomes trivial. Indeed, assume $\mathfrak{T}=\{\mathcal{T}_{1}\}$ with $\mathcal{T}_{1}=(\varphi;{\bf c}_{1},\ldots,{\bf c}_{R};{\bf c}^{\prime}_{1},\ldots,{\bf c}^{\prime}_{R})$ consists only of a single task. With knowledge of this task we can easily construct a feature map $\psi:{\mathcal{X}}\to{}^{Ln_{c}}$ that performs perfectly. Indeed, the map

that simply ‘replaces’ each word $x_{\ell}$ of the input sentence by the one-hot-encoding ${\bf e}_{\varphi(x_{\ell})}$ of its corresponding concept will do. A bit of thinking reveals that the nearest neighbor classification rule associated with feature map (8) perfectly solves the task $\mathcal{T}_{1}$. This is due to the fact that sentences generated by the same sequence of concepts are mapped by $\psi$ to the exact same location in feature space. As a consequence, the nearest neighbor classification rule will match the unfamiliar test sentence ${\bf x}$ to the unique training sentence ${\bf y}$ that occupies the same location in feature space, and this training sentence has the correct label by construction (assuming that sequences of concepts from different categories are distinct). To put it formally:

Consider now the case where $\mathfrak{T}=\{\mathcal{T}_{1},\mathcal{T}_{2}\}$ consists of two tasks. According to Theorem 2 there exists a $\psi$ that perfectly solves $\mathcal{T}_{1}$, but this $\psi$ might perform poorly on $\mathcal{T}_{2}$, and vice versa. So, it might not be possible to design good features if we do not know a priori which of these tasks we will face. Theorem 1 states that, in the extreme case where $\mathfrak{T}$ contains all possible tasks, this is indeed the case — the best possible ‘task-agnostic’ features $\psi$ will perform catastrophically on average. In other words, features must be task-dependent in order to succeed.

To draw a very approximate analogy, imagine once again that $\mathfrak{T}=\{\mathcal{T}_{1}\}$ and that $\mathcal{T}_{1}$ represents, say, a hand-written digit classification task. A practitioner, after years of experience, could hand-craft a very good feature map $\psi$ that performs almost perfectly for this task. If we then imagine the case $\mathfrak{T}=\{\mathcal{T}_{1},\mathcal{T}_{2}\}$ where $\mathcal{T}_{1}$ represents a hand-written digit classification task and $\mathcal{T}_{2}$ represents, say, an animal classification task, then it becomes more difficult for a practitioner to handcraft a feature map $\psi$ that works well for both tasks. In this analogy, the size of the set $\mathfrak{T}$ encodes the amount of knowledge the practitioner has about the specific tasks she will face. The extreme choice $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$ corresponds to the practitioner knowing nothing beyond the fact that natural images are made of patches. Theorem 1 quantifies, in this extreme case, the impossibility of hand-crafting a feature map $\psi$ knowing only the range of possible tasks and not the specific task itself. In a realistic setting the collection of tasks $\mathfrak{T}$ is smaller, of course, and the data generative process itself is more coherent than in our simplified setup. Nonetheless, we hope our analysis sheds some light on some of the essential limitations of algorithms that do not learn features.

Finally, our empirical results (see Section 6) show that a simple algorithm that learns features does not face this obstacle. We do not need knowledge of the specific task $\mathcal{T}$ in order to design a good neural network architecture, but only of the family of tasks $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$ that we will face. Indeed, the architecture in Figure 2 succeeds at classifying unfamiliar test sentences more than $99\%$ of the time. This probability, which we empirically evaluate, is with respect to the choice of the task, the choice of the training set, and the choice of the unfamiliar test sentence (we use the values of $L,n_{w},n_{c}$ and $R$ from Theorem 1, and $n_{\text{spl}}=6,$ for this experiment). Continuing with our approximate analogy, this means our hypothetical practitioner needs no domain specific knowledge beyond the patch structure of natural images when designing a successful architecture. In sum, successful feature design requires task-specific knowledge while successful architecture design requires only knowledge of the task family.

Main Theorem: Our main theoretical result extends Theorem 1 to arbitrary values of $L$, $n_{w}$, $n_{c}$, $n_{\rm spl}$ and $R$. The resulting formula involves various combinatorial quantities. We denote by ${n\choose k}$ the binomial coefficients and by $\genfrac{\{}{\}}{0.0pt}{}{n}{k}$ the Stirling numbers of the second kind. Let $\mathbb{N}=\{0,1,2,\ldots\}$ and let $\gamma,\hat{\gamma}:\mathbb{N}^{L+1}\to\mathbb{N}$ be the functions defined by $\gamma({\bf k}):=\sum_{i=1}^{L+1}(i-1)k_{i}$ and $\hat{\gamma}({\bf k}):=\sum_{i=1}^{L+1}ik_{i},$ respectively. We then define, for $0\leq\ell\leq L$, the sets

We let $\mathcal{S}=\mathcal{S}_{0}$, and we note that the inclusion $\mathcal{S}_{\ell}\subset\mathcal{S}$ always holds. Given ${\bf k}\in\mathbb{N}^{L+1}$ we denote by

the set of ${\bf k}$-admissible matrices. Finally, we let $\mathfrak{f},\mathfrak{g}:\mathcal{S}\to\real$ be the functions defined by

respectively. With these definitions at hand, we may now state our main theorem.

The combinatorial quantities involved appear a bit daunting at a first glance, but, within the context of the proof, they all take a quite intuitive meaning. The heart of the proof involves the analysis of a measure of concentration that we call the permuted moment, and of an associated graph-cut problem. The combinatorial quantities arise quite naturally in the course of analyzing the graph cut problem. We provide a quick overview of the proof in Section 5, and refer to the appendix for full details. For now, it suffices to note that we have a formula (i.e. the right hand side of (9)) that can be exactly evaluated with a few lines code. This formula provides a relatively tight lower bound for the generalization error. Theorem 1 is then a direct consequence — plugging $L=9$, $n_{w}=150$, $n_{c}=5$, $R=1000$ and $\ell=7$ in the right hand side of (9) gives the claimed $98.4\%$ lower bound.

The two previous sections were concerned with the case in which each unfamiliar sequence of concepts has a single representative in the training set. In this section we consider the more general case in which each unfamiliar sequence of concepts has $n^{*}$ representatives in the training set, see Figure 3. Using a simple union bound, inequality (9) easily extends to this situation — the resulting formula is a bit cumbersome so we present it in the appendix (see Theorem 7). In the concrete case where $L=9$, $n_{w}=150$, $n_{c}=5$, $R=1000$ this formula simplifies to

therefore exhibiting an affine relationship between the error rate and the number $n^{*}$ of unfamiliar sentences per category.

Note that choosing $n^{*}=1$ in (10) leads to a $98.4\%$ lower bound on the error rate, therefore recovering the result from Theorem 1. This lower bound then decreases by $1.5\%$ with each additional unfamiliar sentence per category in the training set.

We would like to emphasize one more time the importance of non-asymptotic analysis in the long-tailed learning setting. For example, in inequality (10), the difficulty lies in obtaining a value as small as possible for the coefficient in front of $n^{*}$. We accomplish this via a careful analysis of the graph cut problem associated with our data model.

The proof involves two main ingredients. First, the key insight of our analysis is the realization that generalization in our data model is closely tied to the permuted moment of a probability distribution. To state this central concept, it will prove convenient to think of probability distributions on ${\mathcal{X}}$ as vectors ${\bf p}\in{}^{N}$ with $N=|{\mathcal{X}}|$, together with indices $0\leq i\leq N-1$ given by some arbitrary (but fixed) indexing of the elements of data space. Then $p_{i}$ denotes the probability of the $i^{{\rm th}}$ element of ${\mathcal{X}}$ in this indexing. We use $S_{N}$ to denote the set of permutations of $\{0,1,\ldots,N-1\}$ and $\sigma\in S_{N}$ to refer to a particular permutation. The $t^{{th}}$ permuted moment of the probability vector ${\bf p}\in{}^{N}$ is

Since (11) involves a maximum over all possible permutations, the definition clearly does not depend on the way the set ${\mathcal{X}}$ was indexed. In order to maximize the sum, the permutation $\sigma$ must match the largest values of $p_{i}$ with the largest values of $(i/N)^{t}$, so the maximizing permutation simply orders the entries $p_{i}$ from smallest to largest. A very peaked distribution that gives large probability to only a handful of elements of ${\mathcal{X}}$ will have large permuted moment. Because of this, the permuted moment is akin to the negative entropy; it has large values for delta-like distributions and small values for uniform ones. From definition (11) it is clear that $0\leq{\mathcal{H}}_{t}({\bf p})\leq 1$ for all probability vectors ${\bf p}$, and it is easily verified that the permuted moment is convex. These properties, as well as various useful bounds for the permuted moment, are presented and proven in the appendix.

Second, we identify a specific feature map, $\psi^{\star}:{\mathcal{X}}\to\mathcal{F}^{\star}$, which is optimal for a collection of tasks closely related to the ones considered in our data model. Leveraging the optimality of $\psi^{\star}$ on these related tasks allows us to derive an error bound that holds for the tasks of interest. The feature map $\psi^{\star}$ is better understood through its associated kernel, which is given by the formula

Up to normalization, $K^{\star}({\bf x},{\bf y})$ simply counts the number of equipartitions of the vocabulary for which sentences ${\bf x}$ and ${\bf y}$ have the same underlying sequence of concepts. Intuitively this makes sense, for the best possible kernel must leverage the only information we have at hand. We know the general structure of the problem (words are partitioned into concepts) but not the partition itself. So to try and determine if sentences $({\bf x},{\bf y})$ were generated by the same sequence of concepts, the best we can do is to simply try all possible equipartitions of the vocabulary and count how many of them wind up generating $({\bf x},{\bf y})$ from the same underlying sequence of concepts. A high count makes it more likely that $({\bf x},{\bf y})$ were generated by the same sequence of concepts. The optimal kernel $K^{\star}$ does exactly this, and provides a good (actually optimal, see the appendix) measure of similarity between pairs of sentences.

For fixed ${\bf x}\in{\mathcal{X}}$, the function ${\bf y}\mapsto K^{\star}({\bf x},{\bf y})$ defines a probability distribution on data space. The connection between generalization error, permuted moment, and optimal feature map, come from the fact that

and so, up to a small error $1/R$, it is the permuted moments of $K^{\star}$ that determine the success rate. We then obtain the lower bound (9) by studying these moments in great detail. A simple union bound is then used to obtain inequalities such as (10).

We conclude by presenting empirical results that complement our theoretical findings. The full details of these experiments (training procedure, hyperparameter choices, number of experiments ran to estimate the success rates, and standard deviations of these success rates), as well as additional experiments, can be found in Appendix E. Codes are available at https://anonymous.4open.science/r/Long_Tailed_Learning_Requires_Feature_Learning-17C4.

Parameter Settings. We consider five parameter settings for the data model depicted in Figure 3. Each setting corresponds to a column in Table 1. In all five settings, we set the parameters $L=9$, $n_{w}=150$, $n_{c}=5$ and $R=1000$ to the values for which the error bound (10) holds. We choose values for the parameters $n_{\rm spl}$ and $n^{*}$ so that the $i^{th}$ column of the table corresponds to a setting in which the training set contains $5$ familiar and $i$ unfamiliar sentences per category. Recall that $n_{\rm spl}$ is the total number of samples per category in the training set. So the first column of the table corresponds to a setting in which each category contains $5$ familiar sentences and $1$ unfamiliar sentence, whereas the last column corresponds to a setting in which each category contains $5$ familiar sentences and $5$ unfamiliar sentences.

Algorithms. We evaluate empirically seven different algorithms. The first two rows of the table correspond to experiments in which the neural network in Figure 2 is trained with SGD and constant learning rate. At test time, we consider two different strategies to classify test sentences. The first row of the table considers the usual situation in which the trained neural network is used to classify test points. The second row considers the situation in which the trained neural network is only used to extract features (i.e. the concatenated words representation right before MLP2). The classification of test points is then accomplished by running a nearest neighbor classifier on these learned features. The third (resp. sixth) row of the table shows the results obtained when running a nearest neighbor algorithm (resp. SVM) on the features $\psi^{\star}$ of the optimal feature map. By the kernel trick, these algorithms only require the values of the optimal kernel $\langle\psi^{\star}({\bf x}),\psi^{\star}({\bf y})\rangle_{\mathcal{F}^{\star}}$, computed via (12), and not the features $\psi^{\star}$ themselves. The fourth (resp. seventh) row shows results obtained when running a nearest neighbor algorithm (resp. SVM) on features extracted by the simplest possible feature map, that is

where ${\bf e}_{x_{\ell}}$ denotes the one-hot-encoding of the $\ell^{th}$ word of the input sentence. Finally, the last row considers a SVM with Gaussian Kernel (also called RBF kernel).

Results. The first two rows of the table correspond to algorithms that learn features from the data; the remaining rows correspond to algorithms that use a pre-determined (not learned) feature map. Table 1 reports the success rate of each algorithm on unfamiliar test sentences. A crystal-clear pattern emerges. Algorithms that learn features generalize almost perfectly, while algorithms that do not learn features catastrophically fail. Moreover, the specific classification rule matters little. For example, replacing MLP2 by a nearest neighbor classifier on the top of features learned by the neural network leads to equally accurate results. Similarly, replacing the nearest neighbor classifier by a SVM on the top of features extracted by $\psi^{\star}$ or $\psi_{\rm one-hot}$ leads to almost equally poor results. The only thing that matters is whether or not the features are learned. Finally, inequality (10) gives an upper bound of $0.015n^{*}+1/1000$ on the success rate of the nearest neighbor classification rule applied on the top of any possible feature map (including $\psi^{\star}$ and $\psi_{\rm one-hot}$). The fifth row of Table 1 compares this bound against the empirical accuracy obtained with $\psi^{\star}$ and $\psi_{\rm one-hot}$, and the comparison shows that our theoretical upper bound is relatively tight.

When $n^{*}=1$ our main theorem states that no feature map can succeed more than $1.6\%$ of the time on unfamiliar test sentences (fifth row of the table). At first glance this appears to contradict the empirical performance of the feature map extracted by the neural network, which succeeds $99\%$ of the time (second row of the table). The resolution of this apparent contradiction lies in the order of operations. The point here is to separate hand crafted or fixed features from learned features via the order of operations. If we choose the feature map before the random selection of the task then the algorithm performs poorly since it uses unlearned, task-independent features. By contrast, the neural network learns a feature map from the training set, and since the training set is generated by the task, this process takes place after the random selection of the task. It therefore uses task-dependent features, and the network performs almost perfectly for the specific task that generated its training set. But by our main theorem, it too must fail if the task changes but the features do not.

Acknowledgements

Xavier Bresson is supported by NRF Fellowship NRFF2017-10 and NUS-R-252-000-B97-133.