# Long-Tailed Learning Requires Feature Learning

Thomas Laurent Loyola Marymount University<EMAIL_ADDRESS>James H. von
Brecht  Xavier Bresson National University of Singapore<EMAIL_ADDRESS>
###### Abstract

We propose a simple data model inspired from natural data such as text or
images, and use it to study the importance of learning features in order to
achieve good generalization. Our data model follows a long-tailed distribution
in the sense that some rare subcategories have few representatives in the
training set. In this context we provide evidence that a learner succeeds if
and only if it identifies the correct features, and moreover derive non-
asymptotic generalization error bounds that precisely quantify the penalty
that one must pay for not learning features.

##  1 Introduction

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

Figure 1:  Data model with parameters set to $L=5$, $n_{w}=12$, $n_{c}=3$,
$R=3$, and $n_{\text{spl}}=5$.

##  2 The Data Model

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:

${\mathcal{V}}=\\{\text{potato, cheese, carrots,
chicken},\ldots\\}\qquad\text{and}\qquad\mathcal{C}=\\{\text{vegetable, dairy,
meat}\\}.$

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

$[\text{dairy},\text{dairy},\text{veggie},\text{meat},\text{veggie}]\;\;\overset{\text{generates}}{\longrightarrow}\;\;[\text{cheese},\text{butter},\text{lettuce},\text{chicken},\text{leek}]$

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:

${\bf
x}^{\text{test}}=[\text{butter},\text{yogurt},\text{carrot},\text{beef},\text{lettuce}]$
(1)

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

${\bf
x}_{1,1}=[\text{cheese},\text{butter},\text{lettuce},\text{chicken},\text{leek}]\;.$
(2)

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.

Figure 2: A simple neural net.

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

$|\varphi^{-1}(\\{c\\})|=|\\{w\in\mathcal{V}:\varphi(w)=c\\}|=n_{w}/n_{c}\qquad\text{for
all }c\in\mathcal{C},$ (3)

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

$\Phi=\\{\text{All functions $\varphi$ from $\mathcal{V}$ to $\mathcal{C}$
that satisfy (\ref{equipartition0}) }\\}$

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

${\mathcal{X}}=\mathcal{V}^{L}\qquad\text{ and
}\qquad\mathcal{Z}=\mathcal{C}^{L},$

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.

##  3 Statement and Discussion of Main Results

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

$\mathcal{T}=(\;\;\varphi\;\;;\;\;{\bf c}_{1},\ldots,{\bf c}_{R}\;\;;\;\;{\bf
c}^{\prime}_{1},\ldots,{\bf
c}^{\prime}_{R}\;\;)\;\in\;\Phi\times\mathcal{Z}^{2R}$ (4)

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:

$\text{err}(\mathcal{F},\psi,\mathcal{T})=\underset{S\sim\mathcal{D}_{\mathcal{T}}^{\text{train}}}{\mathbb{E}}\Bigg{[}\underset{{\bf
x}\sim\mathcal{D}_{\mathcal{T}}^{\text{test}}}{\mathbb{P}}\left[f_{\mathcal{T}}\left(\arg\max_{{\bf
y}\in S}\langle\psi({\bf x}),\psi({\bf y})\rangle_{\mathcal{F}}\right)\neq
f_{\mathcal{T}}({\bf x})\right]\Bigg{]}.$ (5)

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

$\text{err}(\mathcal{F},\psi,\mathcal{T})=\underset{S\sim\mathcal{D}_{\mathcal{T}}^{\text{train}}}{\mathbb{E}}\Bigg{[}\underset{{\bf
x}\sim\mathcal{D}_{\mathcal{T}}^{\text{test}}}{\mathbb{P}}\left[\exists{\bf
y}\in\arg\max_{{\bf y}\in S}\langle\psi({\bf x}),\psi({\bf
y})\rangle_{\mathcal{F}}\text{ such that }f_{\mathcal{T}}({\bf y})\neq
f_{\mathcal{T}}({\bf x})\right]\Bigg{]}$ (6)

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

$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})=\frac{1}{|\mathfrak{T}|}\sum_{\mathcal{T}\in\mathfrak{T}}\text{err}(\mathcal{F},\psi,\mathcal{T})$
(7)

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) —

######  Theorem 1.

Let $L=9$, $n_{w}=150$, $n_{c}=5$, $R=1000$ and $n_{\text{spl}}\geq 2$. Let
$\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$. Then

$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})>98.4\%$

for all feature spaces $\mathcal{F}$, and all feature maps
$\psi:{\mathcal{X}}\mapsto\mathcal{F}$.

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

$\psi([x_{1},\ldots,x_{L}])=[{\bf e}_{\varphi(x_{1})},\ldots,{\bf
e}_{\varphi(x_{L})}]$ (8)

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:

######  Theorem 2.

Given a task $\mathcal{T}\in\Phi\times\mathcal{Z}^{2R}$ satisfying ${\bf
c}^{\prime}_{r}\neq{\bf c}^{\prime}_{s}$ and ${\bf c}^{\prime}_{r}\neq{\bf
c}_{s}$ for all $r\neq s$, there exists a feature space $\mathcal{F}$ and a
feature map $\psi:{\mathcal{X}}\mapsto\mathcal{F}$ such that
${\text{err}}(\mathcal{F},\psi,\mathcal{T})=0$.

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

$\mathcal{S}_{\ell}:=\left\\{{\bf
k}\in\mathbb{N}^{L+1}:\;\;\;\hat{\gamma}({\bf k})=n_{w}\quad\text{ and
}\quad\ell\leq\gamma({\bf k})\leq L\right\\}.$

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

$\mathcal{A}_{{\bf k}}:=\Big{\\{}A\in\mathbb{N}^{(L+1)\times
n_{c}}:\;\;\sum_{i=1}^{L+1}iA_{ij}=n_{w}/n_{c}\;\;\text{for all
$j$}\;\;\;\text{ and }\;\;\;\sum_{j=1}^{n_{c}}A_{ij}=k_{i}\;\;\;\;\text{for
all $i$}\Big{\\}}$

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

$\displaystyle\mathfrak{f}({\bf
k}):={\Big{(}(n_{w}/n_{c})!\Big{)}^{n_{c}}}\frac{n_{c}^{L}}{n_{w}!}\sum_{A\in\mathcal{A}_{k}}\left(\prod_{i=1}^{L+1}\frac{k_{i}!}{A_{i,1}!\;A_{i,2}!\;\cdots\;A_{i,n_{c}}!}\right)\qquad\text{and}\qquad$
$\displaystyle\mathfrak{g}({\bf k}):=\frac{\gamma({\bf
k})!}{n_{w}^{2L}}\left(\frac{n_{w}!}{k_{1}!k_{2}!\cdots
k_{L+1}!}\prod_{i=2}^{L+1}\left(\frac{i^{(i-2)}}{i!}\right)^{k_{i}}\right)\left(\sum_{i=\gamma(\bf
k)}^{L}{L\choose i}\genfrac{\\{}{\\}}{0.0pt}{}{i}{\gamma({\bf
k})}\;2^{i}n_{w}^{L-i}\right),$

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

######  Theorem 3 (Main Theorem).

Let $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$. Then

$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})\geq\left(\sum_{{\bf
k}\in\mathcal{S}_{\ell}}\mathfrak{f}({\bf k})\mathfrak{g}({\bf
k})\right)-\frac{1}{R}\left(1+\frac{1}{2}\max_{{\bf
k}\in\mathcal{S}_{\ell}}\;\mathfrak{f}({\bf k})\right)$ (9)

for all feature spaces $\mathcal{F}$, all feature maps
$\psi:{\mathcal{X}}\mapsto\mathcal{F}$, and all $0\leq\ell\leq L$.

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.

##  4 Multiple Unfamiliar Sentences per Category

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

$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})\geq
1-0.015\,n^{*}-1/R\qquad\text{for all $\mathcal{F}$ and all $\psi$,}$ (10)

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

Figure 3: More general version of our data model with multiple unfamiliar
sentences per category. The model parameters in this example are $L=5$,
$n_{w}=12$, $n_{c}=3$, $R=3$, $n_{\text{spl}}=6$ and $n^{*}=2$.

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.

##  5 Proof Outline — Permuted Moment and Optimal Feature Map

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

${\mathcal{H}}_{t}({\bf p})\;\;:=\;\;\max_{\sigma\in
S_{N}}\;\;\sum_{i=0}^{N-1}\left(i/N\right)^{t}\,p_{\sigma(i)}$ (11)

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

$K^{\star}({\bf x},{\bf y})=\;\langle\psi^{\star}({\bf x}),\psi^{\star}({\bf
y})\rangle_{\mathcal{F}^{\star}}=\frac{n_{c}^{L}}{n_{w}^{L}}\;\;\frac{\big{|}\\{\varphi\in\Phi:\varphi(x_{\ell})=\varphi(y_{\ell})\text{
for all }1\leq\ell\leq L\\}\big{|}}{|\Phi|}.$ (12)

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

$\sup_{\mathcal{F},\psi}\left[1-\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})\right]\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R},$ (13)

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

##  6 Empirical Results

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

$\psi_{\rm one-hot}([x_{1},\ldots,x_{L}])=[{\bf e}_{x_{1}},\ldots,{\bf
e}_{x_{L}}]$

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

Table 1: Success rate on unfamiliar test sentences. | $n^{*}\\!=\\!1$ | $n^{*}\\!=\\!2$ | $n^{*}\\!=\\!3$ | $n^{*}\\!=\\!4$ | $n^{*}\\!=\\!5$
---|---|---|---|---|---
|  $n_{\rm spl}\\!=\\!6$ |  $n_{\rm spl}\\!=\\!7$ |  $n_{\rm spl}\\!=\\!8$ |  $n_{\rm spl}\\!=\\!9$ |  $n_{\rm spl}\\!=\\!10$
Neural network in Figure 2 | $99.8\%$ | $99.9\%$ | $99.9\%$ | $99.9\%$ | $100\%$
Nearest neighb. on features learned by neural net | $99.9\%$ | $99.9\%$ | $99.9\%$ | $99.9\%$ | $99.9\%$
Nearest neighb. on features extracted by $\psi^{\star}$ | $0.7\%$ | $1.1\%$ | $1.5\%$ | $1.8\%$ | $2.2\%$
Nearest neighb. on features extracted by $\psi_{\rm one-hot}$ | $0.6\%$ | $1.1\%$ | $1.4\%$ | $1.7\%$ | $2.1\%$
Theoretical upper bound ($0.015n^{*}+1/1000$) | $1.6\%$ | $3.1\%$ | $4.6\%$ | $6.1\%$ | $7.6\%$
SVM on features extracted by $\psi^{\star}$ | $0.6\%$ | $1.5\%$ | $2.2\%$ | $3.2\%$ | $4.2\%$
SVM on features extracted by $\psi_{\rm one-hot}$ | $0.5\%$ | $1.1\%$ | $1.9\%$ | $2.8\%$ | $3.8\%$
SVM with Gaussian kernel | $0.6\%$ | $1.1\%$ | $2.0\%$ | $2.8\%$ | $3.6\%$

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.

## References

  * [1] Zeyuan Allen-Zhu and Yuanzhi Li.  What can resnet learn efficiently, going beyond kernels?  Advances in Neural Information Processing Systems, 32, 2019.
  * [2] Zeyuan Allen-Zhu and Yuanzhi Li.  Backward feature correction: How deep learning performs deep learning.  arXiv preprint arXiv:2001.04413, 2020.
  * [3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In International Conference on Machine Learning, pages 242–252. PMLR, 2019.
  * [4] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang.  Stronger generalization bounds for deep nets via a compression approach.  In International Conference on Machine Learning, pages 254–263. PMLR, 2018.
  * [5] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton.  Layer normalization.  arXiv preprint arXiv:1607.06450, 2016.
  * [6] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky.  Spectrally-normalized margin bounds for neural networks.  Advances in neural information processing systems, 30, 2017.
  * [7] Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar.  When is memorization of irrelevant training data necessary for high-accuracy learning?  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 123–132, 2021.
  * [8] Chih-Chung Chang and Chih-Jen Lin.  Libsvm: a library for support vector machines.  ACM transactions on intelligent systems and technology (TIST), 2(3):1–27, 2011.
  * [9] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  arXiv preprint arXiv:1810.02054, 2018.
  * [10] Vitaly Feldman.  Does learning require memorization? a short tale about a long tail.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 954–959, 2020.
  * [11] Vitaly Feldman and Chiyuan Zhang.  What neural networks memorize and why: Discovering the long tail via influence estimation.  Advances in Neural Information Processing Systems, 33:2881–2891, 2020.
  * [12] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  Limitations of lazy training of two-layers neural network.  Advances in Neural Information Processing Systems, 32, 2019.
  * [13] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari.  When do neural networks outperform kernel methods?  Advances in Neural Information Processing Systems, 33:14820–14830, 2020.
  * [14] Noah Golowich, Alexander Rakhlin, and Ohad Shamir.  Size-independent sample complexity of neural networks.  In Conference On Learning Theory, pages 297–299. PMLR, 2018.
  * [15] Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  Advances in neural information processing systems, 31, 2018.
  * [16] Ziwei Ji and Matus Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  arXiv preprint arXiv:1909.12292, 2019.
  * [17] Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh.  Local signal adaptivity: Provable feature learning in neural networks beyond kernels.  Advances in Neural Information Processing Systems, 34, 2021.
  * [18] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang.  Learning over-parametrized two-layer neural networks beyond ntk.  In Conference on learning theory, pages 2613–2682. PMLR, 2020.
  * [19] Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu.  Large-scale long-tailed recognition in an open world.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2537–2546, 2019.
  * [20] Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro.  Quantifying the benefit of using differentiable learning over tangent kernels.  In International Conference on Machine Learning, pages 7379–7389. PMLR, 2021.
  * [21] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.  A Pac-Bayesian approach to spectrally-normalized margin bounds for neural networks.  arXiv preprint arXiv:1707.09564, 2017.
  * [22] Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro.  Towards understanding the role of over-parametrization in generalization of neural networks.  arXiv preprint arXiv:1805.12076, 2018.
  * [23] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [24] Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová.  Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed.  In International Conference on Machine Learning, pages 8936–8947. PMLR, 2021.
  * [25] Ruslan Salakhutdinov, Antonio Torralba, and Josh Tenenbaum.  Learning to share visual appearance for multiclass object detection.  In CVPR 2011, pages 1481–1488. IEEE, 2011.
  * [26] Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma.  Regularization matters: Generalization and optimization of neural nets vs their induced kernel.  Advances in Neural Information Processing Systems, 32, 2019.
  * [27] Gilad Yehudai and Ohad Shamir.  On the power and limitations of random features for understanding neural networks.  Advances in Neural Information Processing Systems, 32, 2019.
  * [28] Xiangxin Zhu, Dragomir Anguelov, and Deva Ramanan.  Capturing long-tail distributions of object subcategories.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 915–922, 2014.

Appendix

In Section A we prove a few elementary properties of the permuted moment (11).
Section B is devoted to the proof of inequality (13), which we restate here
for convenience:

$\sup_{\mathcal{F},\psi}\left[1-\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})\right]\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}$ (14)

where the collection of tasks $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$
consists in _all possible tasks_ that one might encounter. Inequality (14)
plays a central role in our work as it establishes the connection between the
generalization error, the permuted moment, and the optimal kernel $K^{\star}$
defined by (12). The proof is non-technical and easily accessible. In Section
C we provide the following upper bound on the permuted moment of the optimal
kernel:

$\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}{\mathcal{H}}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)\leq\left(1-\sum_{{\bf
k}\in\mathcal{S}_{\ell}}\;\mathfrak{f}({\bf k})\mathfrak{g}({\bf
k})\right)+\frac{1}{2R}\left(\max_{{\bf
k}\in\mathcal{S}_{\ell}}\;\mathfrak{f}({\bf k})\right)$ (15)

for all $0\leq\ell\leq L.$ The proof is combinatorial in nature, and involves
the analysis of a graph-cut problem. Combining (14) and (15) establishes
Theorem 3. In Section D we consider the case in which each unfamiliar sequence
of concepts has $n^{*}$ representatives in the training set. A simple union
bound shows that, in this situation, inequality (14) becomes

$\sup_{\mathcal{F},\psi}\left[1-\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})\right]\leq\frac{n^{*}}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}$ (16)

Combining (16) and (15) then provides our most general error bound, see
Theorem 7. Inequality (10) in the main body of the paper is just a special
case of Theorem 7. Finally, in Section E, we provide the full details of the
experiments.

##  Appendix A Properties of the Permuted Moment

The permuted moment, in Section 5, was defined for probability vectors only.
It will prove convenient to consider the permuted moment of nonnegative
vectors as well. We denote by ${}_{+}=[0,+\infty)$ the nonnegative real
numbers, and by ${}_{+}^{N}$ the vectors with $N$ nonnegative real entries
indexed from $i=0$ to $i=N-1$. The permuted moment of ${\bf u}\in{}_{+}^{N}$
is then given by

${\mathcal{H}}_{t}({\bf u})\;\;:=\;\;\max_{\sigma\in
S_{N}}\sum_{i=0}^{N-1}\left(i/N\right)^{t}\,u_{\sigma(i)}.$ (17)

where $S_{N}$ denote the set of permutations of $\\{0,1,\ldots,N-1\\}$. The
concept of an _ordering permutation_ will prove useful in the next lemma.

######  Definition 1.

$\sigma\in S_{N}$ is said to be an ordering permutation of ${\bf u}\in{}^{N}$
if

$\displaystyle u_{\sigma(0)}\leq u_{\sigma(1)}\leq\ldots\leq u_{\sigma(N-1)}.$
(18)

The lemma below shows that the permutation maximizing (17) is the one that
sorts the entries $u_{i}$ from smallest to largest.

######  Lemma 1.

Let ${\bf u}\in{}_{+}^{N}$ and let $\sigma^{*}$ be an ordering permutation of
${\bf u}$. Then

$\displaystyle\sigma^{*}\;\;\in\;\;\arg\max_{\sigma\in
S_{N}}\;\;\sum_{i=0}^{N-1}\left(i/N\right)^{t}\,u_{\sigma(i)}.$ (19)

###### Proof.

The optimization problem (19) can be formulated as finding a pairing between
the $u_{i}$’s and the $(i/N)^{t}$’s that maximizes the sum of the product of
the pairs. An ordering permutation of ${\bf u}$ corresponds to pairing the
smallest entry of ${\bf u}$ to $(0/N)^{t}$, the second smallest entry to
$(1/N)^{t}$, the third smallest entry to $(2/N)^{t}$, and so forth. This
pairing is clearly optimal. ∎

In light of the previous lemma, we see that computing the permuted moment of a
vector ${\bf u}$ can be accomplished as follow: 1) sort the entries of ${\bf
u}$ from smallest to largest; 2) compute the dot product between this sorted
vector and the vector

$\begin{bmatrix}\left(\frac{0}{N}\right)^{t}&\left(\frac{1}{N}\right)^{t}&\left(\frac{2}{N}\right)^{t}&\ldots&\left(\frac{N-1}{N}\right)^{t}\end{bmatrix}.$
(20)

Let us now focus on the case where ${\bf u}$ is a probability distribution. If
${\bf u}$ is very peaked, it must have a large permuted moment since, after
sorting, most of the mass concentrates on the high values of (20) located on
the right. On the contrary, if ${\bf u}$ is very spread, it must have small
permuted moment since it ‘wastes’ its mass on small values of (20). 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.

We now show that the permuted moment is subaddiditive and one-homogeneous on
${}_{+}^{N}$ (as a consequence it is convex on the set of probability vectors)
and we derive some elementary $\ell_{1}$ and $\ell_{\infty}$ bounds. We denote
by $\|{\bf u}\|_{p}$ the $\ell_{p}$-norm of a vector ${\bf u}$. In particular,
if ${\bf u}\in{}^{N}_{+}$, we have

$\|{\bf u}\|_{1}:=\sum_{i=0}^{N-1}u_{i}\qquad\text{ and }\qquad\|{\bf
u}\|_{\infty}:=\max_{0\leq i\leq N-1}u_{i}.$

With this notation in hand, we can now state our lemma:

######  Lemma 2.

  1. (i)

${\mathcal{H}}_{t}({\bf u}+{\bf v})\leq{\mathcal{H}}_{t}({\bf
u})+{\mathcal{H}}_{t}({\bf v})$ for all ${\bf u},{\bf v}\in{}_{+}^{N}$.

  2. (ii)

${\mathcal{H}}_{t}(c\,{\bf u})=c\,{\mathcal{H}}_{t}({\bf u})$ for all ${\bf
u}\in{}_{+}^{N}$ and all $c\geq 0$.

  3. (iii)

${\mathcal{H}}_{t}({\bf u})\leq\|{\bf u}\|_{1}$ for all ${\bf
u}\in{}_{+}^{N}$.

  4. (iv)

${\mathcal{H}}_{t}({\bf u})\leq\frac{N}{t+1}\|{\bf u}\|_{\infty}$ for all
${\bf u}\in{}_{+}^{N}$.

###### Proof.

Properties (i) and (ii) are obvious. To prove (iii) and (iv), define
$w_{i}=(i/N)^{t}$ and note that

$\|{\bf w}\|_{\infty}\leq 1\qquad\text{and}\qquad\|{\bf
w}\|_{1}=N\left(\frac{1}{N}\sum_{i=0}^{N-1}\left(i/N\right)^{t}\right)\leq
N\int_{0}^{1}x^{t}dt=\frac{N}{t+1}$

Then (iii) comes from ${\mathcal{H}}_{t}({\bf u})\leq\|{\bf
w}\|_{\infty}\|{\bf u}\|_{1}$ whereas (iv) comes from ${\mathcal{H}}_{t}({\bf
u})\leq\|{\bf w}\|_{1}\|{\bf u}\|_{\infty}.$ ∎

We conclude this section with a slightly more sophisticated bound that holds
for probability vectors — this bound will play a central role in Section C.

######  Lemma 3.

Suppose ${\bf p}\in{}_{+}^{N}$, and suppose $\sum_{i=1}^{N}p_{i}=1.$ Then

${\mathcal{H}}_{t}({\bf
p})\leq\left(1-\sum_{i=0}^{N-1}\min\\{p_{i},\lambda\\}\right)+\frac{\lambda
N}{t+1}\qquad\text{ for all }\lambda\geq 0.$

###### Proof.

Fix a $\lambda\geq 0$ and define the vectors ${\bf u}$ and ${\bf v}$ as
follow:

$u_{i}=\min\\{p_{i},\lambda\\}\qquad\text{ and}\qquad
v_{i}=p_{i}-\min\\{p_{i},\lambda\\}\qquad\text{ for all }0\leq i\leq N-1$

Note that this two vectors are non-negative and sum to ${\bf p}$. We can
therefore use Lemma 2 to obtain

${\mathcal{H}}_{t}({\bf p})={\mathcal{H}}_{t}({\bf u}+{\bf
v})\leq{\mathcal{H}}_{t}({\bf u})+{\mathcal{H}}_{t}({\bf
v})\leq\frac{N}{t+1}\|{\bf u}\|_{\infty}+\|{\bf v}\|_{1}$

To conclude, we note that $\|{\bf u}\|_{\infty}\leq\lambda$, and $\|{\bf
v}\|_{1}=1-\sum_{i=0}^{N-1}\min\\{p_{i},\lambda\\}.$ ∎

##  Appendix B Permuted Moment of $K^{\star}$ and Generalization Error

This section is devoted to the proof of inequality (14). We start by recalling
a few definitions. The vocabulary, set of concepts, data space, and latent
space are

$\mathcal{V}=\\{1,\ldots,n_{w}\\},\qquad\mathcal{C}=\\{1,\ldots,n_{c}\\},\qquad{\mathcal{X}}=\mathcal{V}^{L}\qquad\text{
and }\qquad\mathcal{Z}=\mathcal{C}^{L}$

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. We also recall that the collection of all
equipartitions of the vocabulary is denoted by

$\Phi=\big{\\{}\text{All functions $\varphi$ from $\mathcal{V}$ to
$\mathcal{C}$ that satisfy $|\varphi^{-1}(\\{c\\})|=s_{c}$ for all $c$
}\big{\\}}$

where $s_{c}:=n_{w}/n_{c}$ denote the size of the concepts. Given
$\varphi\in\Phi$, we denote by
$\mathring{\varphi}:{\mathcal{X}}\to\mathcal{C}$ the function

$\mathring{\varphi}\big{(}[x_{1},\,x_{2},\,\ldots,\,x_{L}]\big{)}:=\big{[}\varphi(x_{1}),\,\varphi(x_{2}),\,\ldots,\,\varphi(x_{L})\big{]}$

that operates on sentences element-wise. The informal statement “the sentence
${\bf x}$ is randomly generated by the sequence of concepts ${\bf c}$” means
that ${\bf x}$ is sampled uniformly at random from the set

$\mathring{\varphi}^{-1}(\\{{\bf c}\\})=\\{{\bf
x}\in{\mathcal{X}}:\mathring{\varphi}({\bf x})={\bf c}\\}.$ (21)

We will often do the abuse of notation of writing
$\mathring{\varphi}^{-1}({\bf c})$ instead of $\mathring{\varphi}^{-1}(\\{{\bf
c}\\})$. We now formally define the sampling process associated with our main
data model.

Sampling Process DM:

(i) Sample $\mathcal{T}=(\;\varphi\;;\;{\bf c}_{1},\ldots,{\bf c}_{R}\;;\;{\bf
c}^{\prime}_{1},\ldots,{\bf c}^{\prime}_{R}\;)$ uniformly at random in
$\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$. (ii) For $r=1,\ldots,R$: • Sample
$({\bf x}_{r,1},\ldots,{\bf x}_{r,n_{\rm unf}})$ uniformly at random in
$\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\times\ldots\times\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})$. • Sample $({\bf x}_{r,n_{\rm unf}+1},\ldots,{\bf
x}_{r,n_{\rm spl}})$ uniformly at random in $\mathring{\varphi}^{-1}({\bf
c}_{r})\times\ldots\times\mathring{\varphi}^{-1}({\bf c}_{r})$.  (iii) Sample
${\bf x}^{\text{test}}$ uniformly at random in $\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})$.

Step (i) of the above sampling process consists in selecting at random a task
$\mathcal{T}$ among all possible tasks. Step (ii) consists in generating a
training set111We refer to $S$ as the ‘training set’. In our formalism however
it is not a set, but an element of ${\mathcal{X}}^{R\times n_{spl}}$.
$S\in{\mathcal{X}}^{R\times n_{spl}}$ exactly as depicted on Figure 1: each
unfamiliar sequence of concept ${\bf c}_{r}^{\prime}$ generates $n_{\rm unf}$
sentences, whereas each familiar sequence of concept ${\bf c}_{r}$ generates
$n_{\rm fam}$ sentences (recall that the number of samples per category is
$n_{\rm spl}=n_{\rm unf}+n_{\rm fam}$). Finally step (iii) consists in
randomly generating an unfamiliar test sentence ${\bf
x}^{\text{test}}\in{\mathcal{X}}$. Without loss of generality we assume that
this test sentence is generated by the unfamiliar sequence of concept ${\bf
c}_{1}^{\prime}$.

We denote by $\varrho_{{\rm DM}}$ the p.d.f. of the sampling process DM. This
function is defined on the sample space

$\Omega_{\rm
DM}:=\left(\Phi\times\mathcal{C}^{2R}\right)\times{\mathcal{X}}^{R\times
n_{spl}}\times{\mathcal{X}}\;.$

A sample from $\Omega_{\rm DM}$ takes the form

$\omega=\Big{(}\underbrace{\varphi\;;\;{\bf c}_{1},\ldots,{\bf c}_{R}\;;\;{\bf
c}^{\prime}_{1},\ldots,{\bf c}^{\prime}_{R}}_{\text{The
task}}\;;\;\underbrace{{\bf x}_{1,1},\ldots,{\bf
x}_{1,n_{\text{spl}}}\;;\;\ldots\;;\;{\bf x}_{R,1},\ldots,{\bf
x}_{R,n_{\text{spl}}}}_{\text{The training sentences}}\;;\;\underbrace{{\bf
x^{\text{test}}}}_{\text{The test sentence}}\Big{)}$

and we have the following formula for $\varrho_{{\rm DM}}$

$\varrho_{{\rm
DM}}(\omega):=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\prod^{R}_{r=1}\left(\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}$ (22)

where ${\bf 1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}$ and ${\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r}^{\prime})}$ denote the indicator
functions of the set $\mathring{\varphi}^{-1}({\bf c}_{r})$ and
$\mathring{\varphi}^{-1}({\bf c}_{r})$ respectively. Let us compute a few
marginals of $\varrho_{{\rm DM}}$ in order to verify that it is indeed the
p.d.f. of the sampling process DM. Writing $\omega=(\mathcal{T},S,{\bf
x^{\text{test}}})$, summing over the variables $S$ and ${\bf
x^{\text{test}}}$, and using the fact that $\sum_{{\bf x}\in{\mathcal{X}}}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c})}({\bf x})=|\mathring{\varphi}^{-1}({\bf
c})|,$ we obtain

$\sum_{S\in\mathcal{C}^{2R}}\sum_{{\bf
x^{\text{test}}}\in{\mathcal{X}}}\varrho_{{\rm DM}}(\mathcal{T},S,{\bf
x}^{\text{test}})=\frac{1}{|\Phi||\mathcal{C}|^{2R}}.$

This shows that each task $\mathcal{T}$ is equiprobable. Summing over the
variable $S$ gives

$\sum_{S\in\mathcal{C}^{2R}}\varrho_{{\rm DM}}(\mathcal{T},S,{\bf
x}^{\text{test}})=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{1})}({\bf
x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}$

This shows that, given a task $\mathcal{T}$, the test sentence ${\bf
x^{\text{test}}}$ is obtained by sampling uniformly at random from
$\mathring{\varphi}^{-1}({\bf c}^{\prime}_{1})$. A similar calculation shows
that, given a task $\mathcal{T}$, the train sentence ${\bf x}_{r,s}$ is
obtained by sampling uniformly at random from $\mathring{\varphi}^{-1}({\bf
c}_{r})$ if $s\geq 1$, and from $\mathring{\varphi}^{-1}({\bf
c}_{r}^{\prime})$ if $s=1$.

Given a feature space $\mathcal{F}$ and a feature map
$\psi:{\mathcal{X}}\to\mathcal{F}$, we define the events
$E_{\mathcal{F},\psi}\subset\Omega_{\rm DM}$ as follow:

$E_{\mathcal{F},\psi}=\Big{\\{}\omega\in\Omega_{\rm DM}:\;\;\text{There exists
}1\leq s^{*}\leq n_{\text{spl}}\text{ such that }\\\ \left\langle\psi({\bf
x}^{\text{test}}),\psi({\bf
x}_{1,s^{*}})\right\rangle_{\mathcal{F}}>\left\langle\psi({\bf
x}^{\text{test}}),\psi({\bf x}_{r,s})\right\rangle_{\mathcal{F}}\text{ for all
}2\leq r\leq R\text{ and all }1\leq s\leq n_{\text{spl}}\Big{\\}}.$ (23)

Note that this event consists in all the outcomes $\omega=(\mathcal{T},S,{\bf
x^{\text{test}}})$ for which the feature map $\psi$ associates the test
sentence ${\bf x^{\text{test}}}$ to a train point ${\bf x}_{r,s}$ from the
first category. Since by construction, ${\bf x^{\text{test}}}$ belongs to the
first category, $E_{\mathcal{F},\psi}$ consists in all the outcomes for which
the nearest neighbor classification rule is ‘successful’. As a consequence,
when $\mathfrak{T}=\Phi\times\mathcal{Z}^{2R}$, the generalization error can
be expressed as

$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})=1-\mathbb{P}_{{\rm
DM}}\Big{[}E_{\mathcal{F},\psi}\Big{]}$ (24)

where $\mathbb{P}_{\rm DM}$ denote the probability measure on $\Omega_{\rm
DM}$ induced by $\varrho_{\rm DM}$. Equation (24) should be viewed as our
‘fully formal’ definition of the quantity
$\overline{\text{err}}(\mathcal{F},\psi,\mathfrak{T})$, as opposed to the more
informal definition given earlier by equations (6) and (7).

The goal of this section is to prove inequality (14), which, in light of (24)
is equivalent to

$\sup_{\mathcal{F},\psi}\;\mathbb{P}_{{\rm
DM}}\Big{[}E_{\mathcal{F},\psi}\Big{]}\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}.$ (25)

which in turn equivalent to

$\sup_{\begin{subarray}{c}K:{\mathcal{X}}\times{\mathcal{X}}\to\real\\\
K\text{ pos. semi-def.}\end{subarray}}\mathbb{P}_{{\rm
DM}}\Big{[}E_{K}\Big{]}\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}$ (26)

where the event $E_{K}$ is defined by

$E_{K}=\Big{\\{}\omega\in\Omega_{\rm DM}:\;\;\text{There exists }1\leq
s^{*}\leq n_{\text{spl}}\text{ such that }\\\ K({\bf x}^{\text{test}},{\bf
x}_{1,s^{*}})>K({\bf x}^{\text{test}},{\bf x}_{r,s})\text{ for all }2\leq
r\leq R\text{ and all }1\leq s\leq n_{\text{spl}}\Big{\\}}$ (27)

and where the supremum is taken over all kernels
$K:{\mathcal{X}}\times{\mathcal{X}}\to\real$ which are symmetric positive
semidefinite. We will actually prove a slightly stronger result, namely

$\sup_{\begin{subarray}{c}K:{\mathcal{X}}\times{\mathcal{X}}\to\real\\\
K\text{is symmetric}\end{subarray}}\mathbb{P}_{{\rm
DM}}\Big{[}E_{K}\Big{]}\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}$ (28)

where the supremum is taken over all functions
$K:{\mathcal{X}}\times{\mathcal{X}}\to\real$ that satisfy $K({\bf x},{\bf
y})=K({\bf y},{\bf x})$ for all $({\bf x},{\bf
y})\in{\mathcal{X}}\times{\mathcal{X}}.$ The rest of the section is devoted to
proving (28).

In Subsection B.1 we start by considering a simpler data model — for this
simpler data model we are able to show that the function $\psi^{\star}$
implicitly defined by (12) is the best possible feature map (we actually only
work with the associated kernel $K^{\star}$, and never need $\psi^{\star}$
itself). We also show that the success rate is _exactly equal_ to the permuted
moment of $K^{\star}$ — see Theorem 4, which is is the central result of this
section. In the remaining subsections, namely Subsection B.2 and Subsection
B.3, we leverage the bound obtained for the simpler data model in order to
obtain bound (28) for the main data model. These two subsections are mostly
notational. The core of the analysis takes place in Subsection B.1.

###  B.1 A Simpler Data Model

We start by presenting the sampling process associated with our simpler
datamodel.

Sampling Process SDM:

(i) Sample $\varphi$ uniformly at random in $\Phi$. Sample ${\bf c}_{1},{\bf
c}_{2},\ldots,{\bf c}_{t+1}$ uniformly at random in $\mathcal{Z}$. (ii) For
$1\leq r\leq t+1$: Sample ${\bf x}_{r}$ uniformly at random in
$\mathring{\varphi}^{-1}({\bf c}_{r})$. (iii) Sample ${\bf x^{\text{test}}}$
uniformly at random in $\mathring{\varphi}^{-1}({\bf c}_{1})$.

The function

$\varrho_{\rm SDM}(\varphi;{\bf c}_{1},\ldots,{\bf c}_{t+1};{\bf
x}_{1},\ldots,{\bf x}_{t+1};{\bf
x}^{\text{test}}):=\frac{1}{|\Phi||\mathcal{C}|^{t+1}}\left(\prod^{t+1}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf
x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf c}_{1})\right|}$ (29)

on $\Omega_{\rm SDM}:=\Phi\times\mathcal{C}^{t+1}\times{\mathcal{X}}^{t+2}$ is
the p.d.f. of the above sampling process. We use $\mathbb{P}_{\rm SDM}$ to
denote the probability measure on $\Omega_{\rm SDM}$ induced by this function.
The identity in the next theorem is the central result of this section.

######  Theorem 4.

Let $\mathcal{K}$ denote the set of all symmetric functions from
${\mathcal{X}}\times{\mathcal{X}}$ to . Then

$\sup_{K\in\mathcal{K}}\;\;\mathbb{P}_{\rm SDM}\Big{[}K({\bf
x^{\text{test}}},{\bf x}_{1})>K({\bf x^{\text{test}}},{\bf x}_{r})\text{ for
all }2\leq r\leq t+1\Big{]}=\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{t}(K^{\star}_{\bf x})$ (30)

In (30), $K_{\bf x}^{\star}$ stands for the function $K({\bf x},\cdot)$.
Theorem 4 establishes an intimate connection between the permuted moment and
the ability of any fixed feature map (or equivalently, any fixed kernel) to
generalize well in our framework. The sampling process considered in this
theorem involves two points, ${\bf x}^{\text{test}}$ and ${\bf x}_{1}$,
generated by the same sequence of concepts ${\bf c}_{1}$, and $t$ ‘distractor’
points ${\bf x}_{2},\,\ldots,{\bf x}_{t+1}$ generated by different sequences
of concepts. Success for the kernel $K$ means correctly recognizing that ${\bf
x}^{\text{test}}$ is more ‘similar’ to ${\bf x}_{1}$ than any of the
distractors, and the success rate in (30) precisely quantifies its ability to
do so as a function of the number $t$ of distractors. The theorem shows that
the probability of success for the _best possible kernel_ at this task is
_exactly equal_ to the averaged $t^{th}$-permuted moment of $K^{\star}_{\bf
x}$, so it elegantly quantifies the generalization ability of the best
possible fixed feature map in term of the permuted moment. We also provide an
explicit construction for a kernel $K({\bf x},{\bf y})$ that achieves the
supremum in (30) — First, choose a kernel $\varepsilon({\bf x},{\bf y})$ that
satisfies

  1. (i)

$\varepsilon({\bf x},{\bf y})\neq\varepsilon({\bf x},{\bf z})$ for all ${\bf
x},{\bf y},{\bf z}\in{\mathcal{X}}$ with ${\bf y}\neq{\bf z}$.

  2. (ii)

$0\leq\varepsilon({\bf x},{\bf y})\leq 1$ for all ${\bf x},{\bf
y}\in{\mathcal{X}}$.

and then define the following perturbation

$K({\bf x},{\bf y})=K^{\star}({\bf x},{\bf y})+\varepsilon({\bf x},{\bf
y})/(2s_{c}^{L}|\Phi|)$ (31)

of $K^{\star}$. Any such kernel is a maximizer of the optimization problem in
(30), so we may think of perturbations of $K^{\star}$ as bona-fide optimal.

The rest of this subsection is devoted to the proof of Theorem 4, and we also
show, in the course of the proof, that (31) is a maximizer of the optimization
problem in (30). We use $\mathcal{K}$ to denote the set of all symmetric
functions from ${\mathcal{X}}\times{\mathcal{X}}$ to . We will refers to such
functions as ‘kernel’ despite the fact that these functions are not
necessarily positive semi-definite.

Proving Theorem 4 requires that we study the following optimization problem:

$\displaystyle\text{Maximize
}\;\;\mathfrak{E}(K):=\mathbb{P}_{SDM}\Big{[}K({\bf x}^{\text{test}},{\bf
x}_{1})>K({\bf x}^{\text{test}},{\bf x}_{r})\text{ for all }2\leq r\leq
t+1\Big{]}$ (32) over all kernels $K\in\mathcal{K}$. (33)

We recall the definition of the optimal kernel,

$K^{\star}({\bf x},{\bf
y})=\;\frac{1}{s_{c}^{L}}\;\;\frac{\big{|}\\{\varphi\in\Phi:\varphi(x_{\ell})=\varphi(y_{\ell})\text{
for all }1\leq\ell\leq L\\}\big{|}}{|\Phi|}$ (34)

where $s_{c}=n_{w}/s_{c}$ denotes the size of a concept. We start with the
following simple lemma:

######  Lemma 4.

The function $K^{\star}_{\bf x}(\cdot)=K^{\star}({\bf x},\cdot)$ is a
probability distribution on ${\mathcal{X}}$.

###### Proof.

First note that $K^{\star}$ can be written as

$K^{\star}({\bf x},{\bf
y})=\frac{1}{s_{c}^{L}}\frac{|\\{\varphi\in\Phi:\mathring{\varphi}({\bf
x})=\mathring{\varphi}({\bf
y})\\}|}{|\Phi|}=\frac{1}{s_{c}^{L}|\Phi|}\sum_{\varphi\in\Phi}{\bf
1}_{\\{\mathring{\varphi}({\bf x})=\mathring{\varphi}({\bf y})\\}}$ (35)

Since $\varphi$ maps exactly $s_{c}$ words to each concept
$c\in\\{1,\ldots,n_{c}\\}$, we have that

$|\\{{\bf x}\in\mathcal{X}:\mathring{\varphi}({\bf x})={\bf
c}\\}|=s_{c}^{L}\qquad\text{ for all ${\bf c}\in\mathcal{C}$.}$ (36)

Therefore

$\sum_{{\bf y}\in{\mathcal{X}}}K^{\star}({\bf x},{\bf
y})=\frac{1}{s_{c}^{L}|\Phi|}\sum_{\varphi\in\Phi}\sum_{{\bf
y}\in{\mathcal{X}}}{\bf 1}_{\\{\mathring{\varphi}({\bf
x})=\mathring{\varphi}({\bf
y})\\}}=\frac{1}{s_{c}^{L}|\Phi|}\sum_{\varphi\in\Phi}|\\{{\bf
y}\in\mathcal{X}:\mathring{\varphi}({\bf y})=\mathring{\varphi}({\bf
x})\\}|=1$

∎

We now show that the marginal of the p.d.f. $\varrho_{\rm SDM}$ is related to
$K^{\star}$.

######  Lemma 5.

For all ${\bf x}_{1},\ldots,{\bf x}_{t+1}$ and ${\bf x^{\text{test}}}$ in
${\mathcal{X}}$ we have

$\sum_{\varphi\in\Phi}\;\sum_{{\bf c}_{1}\in\mathcal{C}}\cdots\sum_{{\bf
c}_{t+1}\in\mathcal{C}}\varrho_{\rm SDM}(\varphi;{\bf c}_{1},\ldots,{\bf
c}_{t+1};{\bf x}_{1},\ldots,{\bf x}_{t+1};{\bf
x}^{\text{test}})=\frac{1}{|{\mathcal{X}}|^{t+1}}K^{\star}({\bf x}_{1},{\bf
x^{\text{test}}}).$

###### Proof.

Identity (36) can be expressed as $\left|\mathring{\varphi}^{-1}({\bf
c})\right|=s_{c}^{L}$ for all ${\bf c}\in\mathcal{C}$. As a consequence,
definition (29) of $\varrho_{\rm SDM}(\omega)$ simplifies to

$\varrho_{\rm SDM}(\omega)=\alpha\left(\prod^{t+1}_{r=1}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf x}_{r})\right){\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf x}^{\text{test}})$ (37)

where the constant $\alpha$ is given by

$\alpha=\frac{1}{|\Phi||\mathcal{C}|^{t+1}s_{c}^{L(t+2)}}=\frac{1}{|\Phi|n_{c}^{L(t+1)}s_{c}^{L(t+2)}}=\frac{1}{|\Phi||{\mathcal{X}}|^{t+1}s_{c}^{L}}$

In the above we have used the fact that $|\mathcal{C}|=n_{c}^{L}$ and
$|{\mathcal{X}}|=n_{w}^{L}$. We then note that the identity ${\bf
1}_{\mathring{\varphi}^{-1}({\bf c})}({\bf x})={\bf
1}_{\\{\mathring{\varphi}({\bf x})={\bf c}\\}}$ implies

$\displaystyle\sum_{{\bf c}\in\mathcal{C}}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c})}({\bf x})=\sum_{{\bf
c}\in\mathcal{C}}{\bf 1}_{\\{\mathring{\varphi}({\bf x})={\bf c}\\}}=1$ (38)
$\displaystyle\sum_{{\bf c}\in\mathcal{C}}\Big{(}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c})}({\bf x})\;{\bf
1}_{\mathring{\varphi}^{-1}({\bf c})}({\bf y})\Big{)}\;\;=\;\;\sum_{{\bf
c}\in\mathcal{C}}\Big{(}{\bf 1}_{\\{\mathring{\varphi}({\bf x})={\bf
c}\\}}\;{\bf 1}_{\\{\mathring{\varphi}({\bf y})={\bf
c}\\}}\Big{)}\;\;=\;\;{\bf 1}_{\\{\mathring{\varphi}({\bf
x})=\mathring{\varphi}({\bf y})\\}}$ (39)

for all ${\bf x},{\bf y}\in{\mathcal{X}}$. Summing (37) over the variables
${\bf c}_{1},\ldots,{\bf c}_{t+1}$ we obtain

$\displaystyle\sum_{{\bf c}_{1}\in\mathcal{C}}\cdots$ $\displaystyle\sum_{{\bf
c}_{t+1}\in\mathcal{C}}\varrho_{\rm SDM}(\omega)=\alpha\sum_{{\bf
c}_{1}\in\mathcal{C}}\cdots\sum_{{\bf c}_{t+1}\in\mathcal{C}}\left({\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf x}_{1})\;\;{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf
x}^{\text{test}})\;\;\prod^{t+1}_{r=2}{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{r})}({\bf x}_{r})\right)$ $\displaystyle\quad\quad=\alpha\sum_{{\bf
c}_{1}\in\mathcal{C}}\Bigg{(}{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{1})}({\bf x}_{1})\;{\bf 1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf
x}^{\text{test}})\Bigg{)}\;\;\;\;\sum_{{\bf
c}_{2}\in\mathcal{C}}\cdots\sum_{{\bf
c}_{t+1}\in\mathcal{C}}\left(\prod^{t+1}_{r=2}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf x}_{r})\right)$
$\displaystyle\quad\quad=\alpha\;{\bf 1}_{\\{\mathring{\varphi}({\bf
x}_{1})=\mathring{\varphi}({\bf x^{\text{test}}})\\}}$

where we have used (38) and (39) to obtain the last equality. Summing the
above over the variable $\varphi$ gives $K^{\star}({\bf x}_{1},{\bf
x^{\text{test}}})/|{\mathcal{X}}|^{t+1}$. ∎

The next lemma provides a purely algebraic (as opposed to probabilistic)
formulation for the functional $\mathfrak{E}(K)$ defined in (32).

######  Lemma 6.

The functional $\mathfrak{E}:\mathcal{K}\to\real$ can be expressed as

$\mathfrak{E}(K)=\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\sum_{{\bf y}\in{\mathcal{X}}}K^{\star}({\bf x},{\bf
y})\left(\frac{|\\{{\bf z}\in{\mathcal{X}}:K({\bf x},{\bf z})<K({\bf x},{\bf
y})\\}|}{|{\mathcal{X}}|}\right)^{t}.$ (40)

###### Proof.

Let $g:\mathcal{{\mathcal{X}}}^{t+2}\times\mathcal{K}\to\\{0,1\\}$ be the
indicator function defined by

$g({\bf x}_{1},\ldots,{\bf x}_{t+1},{\bf
x}^{\text{test}},K)=\begin{cases}1&\text{ if }K({\bf x^{\text{test}}},{\bf
x}_{1})>K({\bf x^{\text{test}}},{\bf x}_{r})\;\text{ for all }2\leq r\leq
t+1\\\ 0&\text{otherwise}\end{cases}$

Let $\omega$ denote the sample $(\varphi;{\bf c}_{1},\ldots,{\bf c}_{t+1};{\bf
x}_{1},\ldots,{\bf x}_{t+1};{\bf x}^{\text{test}})$. Since $g$ only depends on
the last $t+2$ variables of $\omega$, we have

$\displaystyle\mathfrak{E}(K)=\mathbb{P}_{SDM}\Big{[}K({\bf
x}^{\text{test}},{\bf x}_{1})>K({\bf x}^{\text{test}},{\bf x}_{r})\text{ for
all }2\leq r\leq t+1\Big{]}$ (41)
$\displaystyle=\sum_{\varphi\in\Phi}\;\sum_{{\bf
c}_{1}\in\mathcal{C}}\cdots\sum_{{\bf c}_{t+1}\in\mathcal{C}}\;\sum_{{\bf
x}_{1}\in{\mathcal{X}}}\cdots\sum_{{\bf x}_{t+1}\in{\mathcal{X}}}\;\sum_{{\bf
x^{\text{test}}}\in{\mathcal{X}}}g({\bf x}_{1},\ldots,{\bf x}_{t+1},{\bf
x}^{\text{test}},K)\;\varrho_{\rm SDM}(\omega)$ (42) $\displaystyle=\sum_{{\bf
x}_{1}\in{\mathcal{X}}}\cdots\sum_{{\bf x}_{t+1}\in{\mathcal{X}}}\;\sum_{{\bf
x^{\text{test}}}\in{\mathcal{X}}}g({\bf x}_{1},\ldots,{\bf x}_{t+1},{\bf
x}^{\text{test}},K)\left(\sum_{\varphi\in\Phi}\;\sum_{{\bf
c}_{1}\in\mathcal{C}}\cdots\sum_{{\bf c}_{t+1}\in\mathcal{C}}\varrho_{\rm
SDM}(\omega)\right)$ (43) $\displaystyle=\sum_{{\bf
x}_{1}\in{\mathcal{X}}}\cdots\sum_{{\bf x}_{t+1}\in{\mathcal{X}}}\;\sum_{{\bf
x^{\text{test}}}\in{\mathcal{X}}}g({\bf x}_{1},\ldots,{\bf x}_{t+1},{\bf
x}^{\text{test}},K)\;\;\frac{1}{|{\mathcal{X}}|^{t+1}}\;\;K^{\star}({\bf
x}_{1},{\bf x^{\text{test}}})$ (44)
$\displaystyle=\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}_{1}\in{\mathcal{X}}}\sum_{{\bf
x^{\text{test}}}\in{\mathcal{X}}}K^{\star}({\bf x}_{1},{\bf
x^{\text{test}}})\left(\frac{1}{|{\mathcal{X}}|^{t}}\sum_{{\bf
x}_{2}\in{\mathcal{X}}}\cdots\sum_{{\bf x}_{t+1}\in{\mathcal{X}}}g({\bf
x}_{1},\ldots,{\bf x}_{t+1},{\bf x}^{\text{test}},K)\right)$ (45)

where we have used Lemma 5 to go from (43) to (44). Writing the indicator
function $g$ as a product of indicator functions,

$\displaystyle g({\bf x}_{1},\ldots,{\bf x}_{t+1},{\bf x}^{\text{test}},K)$
$\displaystyle=\prod_{r=2}^{t+1}{\bf 1}_{\\{K({\bf x^{\text{test}}},{\bf
x}_{1})>K({\bf x^{\text{test}}},{\bf x}_{r})\\}}$

we obtain the following expression for the term appearing between parentheses
in (45):

$\displaystyle\frac{1}{|{\mathcal{X}}|^{t}}\sum_{{\bf
x}_{2}\in{\mathcal{X}}}\cdots\sum_{{\bf x}_{t+1}\in{\mathcal{X}}}g({\bf
x}_{1},\ldots,{\bf x}_{t+1},{\bf x}^{\text{test}},K)$
$\displaystyle=\frac{1}{|{\mathcal{X}}|^{t}}\prod_{r=2}^{t+1}\left(\sum_{{\bf
x}_{r}\in{\mathcal{X}}}{\bf 1}_{\\{K({\bf x^{\text{test}}},{\bf x}_{1})>K({\bf
x^{\text{test}}},{\bf x}_{r})\\}}\right)$
$\displaystyle=\frac{1}{|{\mathcal{X}}|^{t}}\left(\sum_{{\bf
z}\in{\mathcal{X}}}{\bf 1}_{\\{K({\bf x^{\text{test}}},{\bf x}_{1})>K({\bf
x^{\text{test}}},{\bf z})\\}}\right)^{t}$ $\displaystyle=\left(\frac{|\\{{\bf
z}\in{\mathcal{X}}:K({\bf x^{\text{test}}},{\bf x}_{1})>K({\bf
x^{\text{test}}},{\bf z})\\}|}{|{\mathcal{X}}|}\right)^{t}$

Changing the name of variables ${\bf x^{\text{test}}},{\bf x}_{1}$ to ${\bf
x},{\bf y}$ gives (40). ∎

We now use expression (40) for $\mathfrak{E}(K)$ and reformulate optimization
problem (32)-(33) into an equivalent optimization problem over symmetric
matrices. Putting an arbitrary ordering on the set $\mathcal{X}$ (starting
with $i=0$) and denoting by $K^{\star}_{ij}$ the value of the kernel
$K^{\star}$ on the pair that consists of the $i^{th}$ and $j^{th}$ element of
${\mathcal{X}}$, we see that optimization problem (32)-(33) can be written as

$\displaystyle\text{Maximize
}\quad\mathfrak{E}(K):=\frac{1}{N}\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}K^{\star}_{ij}\left(\frac{|\\{j^{\prime}\in[N]:K_{ij^{\prime}}<K_{ij}\\}|}{N}\right)^{t}$
(46) $\displaystyle\text{over all symmetric matrices }K\in{}^{N\times N}$ (47)

In the above we have used the letter $N$ to denote the cardinality of
${\mathcal{X}}$, that is $N=n_{w}^{L}$, and we have used the notation
$[N]=\\{0,1,\ldots,N-1\\}.$ Before solving the matrix optimization problem
(46)-(47), we start with a simpler vector optimization problem. Let ${\bf
p}^{\star}$ be a probability vector, that is ${\bf p}^{\star}\in{}_{+}^{N}$
with $\sum_{i=1}^{N}p_{i}=1$, and consider the optimization problem:

$\displaystyle\text{Maximize }\quad\mathfrak{e}({\bf
v}):=\sum_{j=0}^{N-1}p^{\star}_{j}\;\left(\frac{|\\{j^{\prime}\in[N]:v_{j^{\prime}}<v_{j}\\}|}{N}\right)^{t}$
(48) $\displaystyle\text{over all vector }{\bf v}\in{}^{N}.$ (49)

Recall from Definition 1 that an ordering permutation of a vector ${\bf v}$ is
a permutation that sorts its entries from smallest to largest. We will say
that two vectors ${\bf v},{\bf w}\in{}^{N}$ have _the same ordering_ if there
exist $\sigma\in S_{N}$ which is ordering for both ${\bf v}$ and ${\bf w}$.
The following lemma is key — it shows that the optimization problem (48)–(49)
has a simple solution.

######  Lemma 7.

The following identity

$\sup_{{\bf v}\in{}^{N}}\mathfrak{e}({\bf v})={\mathcal{H}}_{t}({\bf
p}^{\star})$

holds. Moreover, the supremum is achieved by any vector ${\bf v}\in{}^{N}$
that has mutually distinct entries222That is, $v_{i}\neq v_{j}$ for all $i\neq
j$. and that has the same ordering than ${\bf p}^{\star}$.

###### Proof.

Let $\text{Distinct}({}^{N})$ denote the vectors of N that have mutually
distinct entries. We will first show that

$\sup_{{\bf v}\in{}^{N}}\mathfrak{e}({\bf v})=\sup_{{\bf
v}\in\text{Distinct}({}^{N})}\mathfrak{e}({\bf v}).$ (50)

To do this we show that for any ${\bf v}\in{}^{N}$, there exists ${\bf
w}\in\text{Distinct}({}^{N})$ such that

$|\\{j^{\prime}\in[N]:v_{j^{\prime}}<v_{j}\\}|\leq|\\{j^{\prime}\in[N]:w_{j^{\prime}}<w_{j}\\}|\qquad\text{for
all }0\leq j\leq N-1.$ (51)

There are many ways to construct such a ${\bf w}$. One way is to simply set
$w_{j}=\sigma^{-1}(j)$ for some permutation $\sigma$ that orders $v$. Indeed,
note that $\sigma^{-1}(j)$ provides the position of $v_{j}$ in the sequence of
inequality (18). Therefore if $v_{j^{\prime}}<v_{j}$ we must have that
$\sigma^{-1}(j^{\prime})<\sigma^{-1}(j)$. This implies

$\\{j^{\prime}\in[N]:v_{j^{\prime}}<v_{j}\\}\subset\\{j^{\prime}\in[N]:\sigma^{-1}(j^{\prime})<\sigma^{-1}(j)\\}\qquad\text{for
all }j\in[N]$

which in turn implies (51).

Because of (50) we can now restrict our attention to ${\bf
v}\in\text{Distinct}({}^{N})$. Note that if ${\bf
v}\in\text{Distinct}({}^{N})$, then it has a unique ordering permutation
$\sigma$,

$v_{\sigma(0)}<v_{\sigma(1)}<v_{\sigma(2)}<v_{\sigma(3)}<\ldots<v_{\sigma(N-1)}$

and, recalling that $\sigma^{-1}(j)$ provide the position of $v_{j}$ in the
above ordering, we clearly have that

$|\\{j^{\prime}\in[N]:v_{j}^{\prime}<v_{j}\\}|=\sigma^{-1}(j).$

Therefore, if ${\bf v}\in\text{Distinct}({}^{N})$ and if $\sigma$ denotes its
unique ordering permutation, $\mathfrak{e}({\bf v})$ can be expressed as

$\displaystyle\mathfrak{e}({\bf
v})=\sum_{j=0}^{N-1}p^{\star}_{j}\;\left(\frac{|\\{j^{\prime}\in[N]:v_{j^{\prime}}<v_{j}\\}|}{N}\right)^{t}=\sum_{j=0}^{N-1}p^{\star}_{j}\;\left(\frac{\sigma^{-1}(j)}{N}\right)^{t}=\sum_{j=0}^{N-1}p^{\star}_{\sigma(j)}\;(j/N)^{t}$
(52)

Looking at definition (11) of the permuted moment, it is then clear that
$\mathfrak{e}({\bf v})\leq{\mathcal{H}}_{t}({\bf p}^{\star})$ for all ${\bf
v}\in\text{Distinct}({}^{N})$. We then note that if ${\bf
v}\in\text{Distinct}({}^{N})$ has the same ordering than ${\bf p}^{\star}$,
then its unique ordering permutation $\sigma$ must also be an ordering
permutation of ${\bf p}^{\star}$. Then (52) combined with Lemma 1 implies that
$\mathfrak{e}({\bf v})={\mathcal{H}}_{t}({\bf p}^{\star})$. This concludes the
proof. ∎

Relaxing the symmetric constraint in the optimization problem (46)-(47) gives
the following unconstrained problem over all $N$-by-$N$ matrices:

$\displaystyle\text{Maximize
}\quad\mathfrak{E}(K):=\frac{1}{N}\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}K^{\star}_{ij}\left(\frac{|\\{j^{\prime}\in[N]:K_{ij^{\prime}}<K_{ij}\\}|}{N}\right)^{t}$
(53) $\displaystyle\text{over all matrices }K\in{}^{N\times N}$ (54)

Let us denote by $K^{\star}_{i,:}$ the $i^{th}$ row of the matrix $K^{\star}$
and remark that $K^{\star}_{i,:}$ is a probability vector (because
$K^{\star}({\bf x},\cdot)$ is a probability distribution on ${\mathcal{X}}$,
see Lemma 4). We then note that the above unconstrained problem decouples into
$N$ separate optimization problems of the type (48)-(49) in which the
probability vector ${\bf p}^{\star}$ must be replaced by the probability
vector $K^{\star}_{i,:}$. Using Lemma 7 we therefore have that any
$K\in{}^{N\times N}$ that satisfies, for each $0\leq i\leq N-1$,

  1. (a)

The entries of $K_{i,:}$ are mutually distinct,

  2. (b)

$K_{i,:}$ and $K^{\star}_{i,:}$ have the same ordering,

must be a solution of (53)-(54). Lemma 7 also gives:

$\sup_{K\in{}^{N\times
N}}\mathfrak{E}(K)=\frac{1}{N}\sum_{i=0}^{N-1}{\mathcal{H}}_{t}(K^{\star}_{i,:}).$

Now let $\varepsilon\in{}^{N\times N}$ be a symmetric matrix that satisfies:

  * (i)

$\varepsilon_{ij}\neq\varepsilon_{ij^{\prime}}$ for all $i,j,j^{\prime}\in[N]$
with $j\neq j^{\prime}$,

  * (ii)

$0\leq\varepsilon_{ij}\leq 1$ for all $i,j\in[N]$,

and define the following perturbation of the matrix $K^{\star}$:

$K=K^{\star}+\frac{0.5}{s_{c}^{L}|\Phi|}\;\;\varepsilon$ (55)

Recalling definition (35) of the kernel $K^{\star}$, it is clear that for each
$i,j\in[N]$, we have

$K^{\star}_{ij}=\frac{\ell}{s_{c}^{L}|\Phi|}\qquad\text{ for some integer
}\ell.$ (56)

As a consequence perturbing $K^{\star}$ by adding to its entries quantities
smaller than $1/(s_{c}^{L}|\Phi|)$ can not change the ordering of its rows.
Therefore the kernel $K$ defined by (55) satisfies (b). It also satisfies (a).
Indeed, if $K^{\star}_{ij}=K^{\star}_{ij^{\prime}}$ and $j\neq j^{\prime}$,
then we clearly have that $K_{ij}\neq K_{ij^{\prime}}$ due to (i). On the
other hand if $K^{\star}_{ij}\neq K^{\star}_{ij^{\prime}}$, then $K_{ij}\neq
K_{ij^{\prime}}$ due to (ii) and (56).

We have therefore constructed a symmetric matrix that is a solution of the
optimization problem (53)-(54). As a consequence we have

$\sup_{K\in\mathcal{K}}\mathfrak{E}(K)=\sup_{K\in{}^{N\times
N}}\mathfrak{E}(K)=\frac{1}{N}\sum_{i=0}^{N-1}{\mathcal{H}}_{t}(K^{\star}_{i,:})$

where $\mathcal{K}$ should now be interpreted as the set of $N$-by-$N$
symmetric matrices. The above equality proves Theorem 4, and we have also
shown that the perturbed kernel (55) achieves the supremum.

###  B.2 Connection Between the Two Sampling Processes

In this subsection we show that the p.d.f. of Sampling Process SDM can be
obtained by marginalizing the p.d.f. of Sampling Process DM over a subset of
the variables. We also compute another marginal of $\varrho_{\rm DM}$ that
will prove useful in the next subsection. Recall that

$\varrho_{{\rm
DM}}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\prod^{R}_{r=1}\left(\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x^{\text{test}}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}$ (57)

on $\Omega_{\rm DM}:=\Phi\times\mathcal{C}^{2R}\times{\mathcal{X}}^{R\times
n_{\text{spl}}+1}$ is the p.d.f. of the sampling process for our main data
model. Samples from $\Omega_{\rm DM}$ take the form

$\omega=(\varphi\;\;\;;\;\;\;{\bf c}_{1},{\bf c}_{2},{\bf c}_{3},\ldots,{\bf
c}_{R}\;\;\;;\;\;\;{\bf c}^{\prime}_{1},{\bf c}_{2}^{\prime},{\bf
c}_{3}^{\prime},\ldots,{\bf c}^{\prime}_{R}\;\;;\\\ {\bf x}_{1,1},{\bf
x}_{1,2},{\bf x}_{1,3},\ldots,{\bf
x}_{1,n_{\text{spl}}}\;\;\;;\;\;\;\ldots\;\;\;;\;\;\;{\bf x}_{R,1},{\bf
x}_{R,2},{\bf x}_{R,3},\ldots,{\bf x}_{R,n_{\text{spl}}}\;\;\;;\;\;\;{\bf
x^{\text{test}}})$

We separate these variables into two groups, $\omega=(\omega_{a},\omega_{b})$,
where

$\displaystyle\omega_{a}$ $\displaystyle=(\varphi\;\;\;;\;\;\;{\bf c}_{1},{\bf
c}_{2},{\bf c}_{3},\ldots,{\bf c}_{R}\;\;\;;\;\;\;{\bf c}^{\prime}_{1},{\bf
c}_{2}^{\prime},{\bf c}_{3}^{\prime},\ldots,{\bf c}^{\prime}_{R}\;\;;\;\;{\bf
x}_{1,1},{\bf x}_{1,2}\;\;;\;\;\;\ldots\;\;;\;\;{\bf x}_{R,1},{\bf
x}_{R,2}\;\;\;;\;\;\;{\bf x^{\text{test}}})$ (58) $\displaystyle\omega_{b}$
$\displaystyle=({\bf x}_{1,3},{\bf x}_{1,4},\ldots,{\bf
x}_{1,n_{\text{spl}}}\;\;\;;\;\;\;\ldots\;\;;\;\;{\bf x}_{R,3},{\bf
x}_{R,4},\ldots,{\bf x}_{R,n_{\text{spl}}})$ (59)

The variable $\omega_{a}$ belongs to
$\Omega_{a}=\Phi\times\mathcal{C}^{2R}\times{\mathcal{X}}^{2R+1}$, and the
variable $\omega_{b}$ belongs to
$\Omega_{b}={\mathcal{X}}^{R(n_{\text{spl}}-2)}.$ Note that the variables in
$\omega_{a}$ contains, among other, $2R$ sequences of concepts and $2R$
training points (the first and second training points of each category). Each
of these $2R$ training points is generated by one of the $2R$ sequences of
concepts. So the variables involved in $\omega_{a}$ are generated by a process
similar to the one involved in the simpler data model. The following lemma
shows that $p.d.f.$ of $\omega_{a}$, after marginalizing $\omega_{b}$, is
indeed $\varrho_{SDM}$.

######  Lemma 8.

For all $\omega_{a}\in\Omega_{a}$ we have

$\sum_{\omega_{b}\in\Omega_{b}}\varrho_{\rm
DM}(\omega_{a},\omega_{b})=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{r})}({\bf x}_{r,\,2})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}$

Recalling the definition (29) of $\varrho_{\rm SDM}$, and letting $t+1=2R$, we
see that the above lemma states that

$\sum_{\omega_{b}\in\Omega_{b}}\varrho_{\rm
DM}(\omega_{a},\omega_{b})=\varrho_{\rm SDM}(\omega_{a})$ (60)

and $\Omega_{a}=\Omega_{\rm SDM}$.

###### Proof of Lemma 8.

We start by reorganizing the terms involved in the product defining
$\varrho_{\rm DM}$ so that the variables in $\omega_{a}$ and $\omega_{b}$ are
clearly separated:

$\varrho_{\rm DM}(\omega)=\\\
\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{r})}({\bf x}_{r,\,2})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=3}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)$

To demonstrate the process, let us start by summing the above formula over the
first variable of $\omega_{b}$, namely ${\bf x}_{1,3}$. Since this variable
only occurs in the last term of the above product, we have:

$\sum_{{\bf x}_{1,3}\in{\mathcal{X}}}\varrho_{\rm
DM}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{r})}({\bf x}_{r,\,2})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}\\\ \left(\prod_{\begin{subarray}{c}1\leq
r\leq R\\\ 3\leq s\leq n_{\text{spl}}\\\
(r,s)\neq(1,3)\end{subarray}}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{r})}({\bf x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\left(\sum_{{\bf x}_{1,3}\in{\mathcal{X}}}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf
x}_{1,3})}{\left|\mathring{\varphi}^{-1}({\bf c}_{1})\right|}\right)$

Since $\sum_{{\bf x}\in{\mathcal{X}}}{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}_{1})}({\bf x})=|\mathring{\varphi}^{-1}({\bf c}_{1})|$, the last term of
the above product is equal to $1$ and can therefore be omitted. Repeating this
process for all the ${\bf x}_{r,s}$ that constitute $\omega_{b}$ leads to the
desired result. ∎

In the next subsection we will need the marginal of $\varrho_{\rm DM}$ with
respect to another set of variables. To this aim we write
$\omega=(\omega_{c},\omega_{d})$ where

$\displaystyle\omega_{c}=(\varphi\;\;\;;\;\;\;{\bf x}_{1,2},{\bf
x}_{1,3},\ldots,{\bf x}_{1,n_{\text{spl}}}\;\;\;;\;\;\;\ldots\;\;\;;\;\;\;{\bf
x}_{R,2},{\bf x}_{R,3},,\ldots,{\bf x}_{R,n_{\text{spl}}}\;\;\;;\;\;\;{\bf
x^{\text{test}}})$ (61) $\displaystyle\omega_{d}=({\bf c}_{1},\ldots,{\bf
c}_{R}\;\;;\;\;{\bf c}^{\prime}_{1},\ldots,{\bf c}^{\prime}_{R}\;\;;\;\;{\bf
x}_{1,1}\;\;;\;\;\ldots\;\;;\;\;{\bf x}_{R,1})$ (62)

Note that all the unfamiliar training points are contained in $\omega_{d}$.
The test point and the familiar training points are in $\omega_{c}$. We also
let $\Omega_{c}=\Phi\times{\mathcal{X}}^{R(n_{\text{spl}}-1)+1}$ and
$\Omega_{d}=\mathcal{C}^{2R}\times{\mathcal{X}}^{R}$.

######  Lemma 9.

For all $\omega_{c}\in\Omega_{c}$ we have

$\sum_{\omega_{d}\in\Omega_{d}}\varrho_{\rm
DM}(\omega_{c},\omega_{d})=\frac{1}{|\Phi||{\mathcal{X}}|^{R+1}s_{c}^{LR(n_{\text{spl}}-2)}}\prod^{R}_{r=1}{\bf
1}_{\\{\mathring{\varphi}({\bf x}_{r,2})=\mathring{\varphi}({\bf
x}_{r,3})=\ldots=\mathring{\varphi}({\bf x}_{r,n_{\text{spl}}})\\}}$

###### Proof.

We reorganizing the terms involved in the product defining $\varrho_{\rm DM}$
so that the variables in $\omega_{c}$ and $\omega_{d}$ are separated:

$\displaystyle\varrho_{\rm DM}(\omega)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}\left(\prod^{R}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\right)$

Summing the above formula over the last variable involved in $\omega_{d}$,
namely ${\bf x}_{R,1}$, gives

$\sum_{{\bf x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm
DM}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}\\\ \left(\prod^{R-1}_{r=1}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{r})}({\bf
x}_{r,\,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{r})\right|}\right)\Bigg{(}\sum_{{\bf
x}_{R,1}\in{\mathcal{X}}}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{R})}({\bf x}_{R,1})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{R})\right|}\Bigg{)}$

The last term in the above product is equal to $1$ and can therefore be
omitted. Iterating this process gives

$\displaystyle\sum_{{\bf x}_{1,1}\in{\mathcal{X}}}\cdots\sum_{{\bf
x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm
DM}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{2R}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\Bigg{(}\frac{{\bf 1}_{\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})}({\bf x}^{\text{test}})}{\left|\mathring{\varphi}^{-1}({\bf
c}^{\prime}_{1})\right|}\Bigg{)}$

We then use the fact that $\sum_{c_{1}^{\prime}\in\mathcal{C}}{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}^{\prime}_{1})}({\bf x^{\text{test}}})=1,$
see (38), together with $\left|\mathring{\varphi}^{-1}({\bf
c}_{1}^{\prime})\right|=s_{c}^{L}$, see (36), to obtain

$\displaystyle\sum_{c_{1}^{\prime}\in\mathcal{C}}\sum_{{\bf
x}_{1,1}\in{\mathcal{X}}}\cdots\sum_{{\bf
x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm
DM}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{2R}s_{c}^{L}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)$

We then sum over ${\bf c}^{\prime}_{2},\ldots,{\bf c}^{\prime}_{R}$. Since
these variables are not involved in the above formula we get

$\displaystyle\sum_{c_{1}^{\prime}\in\mathcal{C}}\cdots\sum_{c_{R}^{\prime}\in\mathcal{C}}\sum_{{\bf
x}_{1,1}\in{\mathcal{X}}}\cdots\sum_{{\bf
x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm DM}(\omega)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{R+1}s_{c}^{L}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{R}|{\mathcal{X}}|}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)$

where we have used $|\mathcal{C}|s_{c}^{L}=n_{c}^{L}s_{c}^{L}=|{\mathcal{X}}|$
to obtain the last equality. Summing over ${\bf c}_{1}$ gives

$\displaystyle\sum_{{\bf
c}_{1}\in\mathcal{C}}\sum_{c_{1}^{\prime}\in\mathcal{C}}$
$\displaystyle\cdots\sum_{c_{R}^{\prime}\in\mathcal{C}}\sum_{{\bf
x}_{1,1}}\cdots\sum_{{\bf x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm
DM}(\omega)=\frac{1}{|\Phi||\mathcal{C}|^{R}|{\mathcal{X}}|}\sum_{{\bf
c}_{1}\in\mathcal{C}}\left(\prod^{R}_{r=1}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{r})\right|}\right)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{R}|{\mathcal{X}}|}\left(\prod^{R}_{r=2}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\left(\sum_{{\bf
c}_{1}\in\mathcal{C}}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{1})}({\bf
x}_{1,\,s})}{\left|\mathring{\varphi}^{-1}({\bf c}_{1})\right|}\right)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{R}|{\mathcal{X}}|}\left(\prod^{R}_{r=2}\prod^{n_{\text{spl}}}_{s=2}\frac{{\bf
1}_{\mathring{\varphi}^{-1}({\bf c}_{r})}({\bf
x}_{r,\,s})}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|}\right)\left(\frac{{\bf 1}_{\\{\mathring{\varphi}({\bf
x}_{1,2})=\mathring{\varphi}({\bf x}_{1,3})=\ldots=\mathring{\varphi}({\bf
x}_{1,n_{\text{spl}}})\\}}}{\left|\mathring{\varphi}^{-1}({\bf
c}_{1})\right|^{n_{\text{spl}}-1}}\right)$

To obtain the last equality we have used (39) but for a product of
$n_{\text{spl}}-1$ indicator functions instead of just two. Iterating this
process we obtain

$\displaystyle\sum_{{\bf c}_{1}\in\mathcal{C}}\cdots\sum_{{\bf
c}_{R}\in\mathcal{C}}\sum_{c_{1}^{\prime}\in\mathcal{C}}\cdots\sum_{c_{R}^{\prime}\in\mathcal{C}}\sum_{{\bf
x}_{1,1}\in{\mathcal{X}}}\cdots\sum_{{\bf
x}_{R,1}\in{\mathcal{X}}}\varrho_{\rm DM}(\omega)$
$\displaystyle=\frac{1}{|\Phi||\mathcal{C}|^{R}|{\mathcal{X}}|}\prod^{R}_{r=1}\frac{{\bf
1}_{\\{\mathring{\varphi}({\bf x}_{r,2})=\mathring{\varphi}({\bf
x}_{1,3})=\ldots=\mathring{\varphi}({\bf
x}_{r,n_{\text{spl}}})\\}}}{\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|^{n_{\text{spl}}-1}}$

Using one more time that $\left|\mathring{\varphi}^{-1}({\bf
c}_{r})\right|=s_{c}^{L}$ and $|\mathcal{C}|s_{c}^{L}=|{\mathcal{X}}|$ gives
to the desired result. ∎

###  B.3 Conclusion of Proof

We now establish the desired upper bound (28), which we restate below for
convenience:

$\sup_{K\in\mathcal{K}}\mathbb{P}_{{\rm
DM}}\Big{[}E_{K}\Big{]}\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}\left(K^{\star}({\bf
x},\,\cdot)\right)+\frac{1}{R}$ (63)

where

$E_{K}=\Big{\\{}\omega\in\Omega_{\rm DM}:\;\;\text{There exists }1\leq
s^{*}\leq n_{\text{spl}}\text{ such that }\\\ K\left({\bf
x}^{\text{test}},{\bf x}_{1,s^{*}}\right)>K\left({\bf x}^{\text{test}},{\bf
x}_{r,s}\right)\text{ for all }2\leq r\leq R\text{ and all }1\leq s\leq
n_{\text{spl}}\Big{\\}}$ (64)

Figure 4: The test point ${\bf x}^{\text{test}}$ and the train point ${\bf
x}_{1,1}$ are generated by the same sequence of concepts.

We recall that the test point ${\bf x}^{\text{test}}$ is generated by the
unfamiliar sequence of concepts ${\bf c}_{1}^{\prime}$ and that it belongs to
category 1, see Figure 4. The event $E_{K}$ describes all the outcomes in
which the training point most similar to ${\bf x}^{\text{test}}$ (where
similarity is measured with respect to the kernel $K$) belongs to the first
category. There are two very distinct cases within the event $E_{K}$: the
training point most similar to ${\bf x}^{\text{test}}$ can be ${\bf x}_{1,1}$
— this corresponds to a ‘meaningful success’ in which the learner recognizes
that ${\bf x}_{1,1}$ is generated by the same sequence of concepts than ${\bf
x}^{\text{test}}$, see Figure 4. Or the training point most similar to ${\bf
x}^{\text{test}}$ can be one of the points ${\bf x}_{1,2},\ldots,{\bf
x}_{1,n_{\text{spl}}}$ — this corresponds to a ‘lucky success’ because ${\bf
x}_{1,2},\ldots,{\bf x}_{1,n_{\text{spl}}}$ are not related to ${\bf
x}^{\text{test}}$ (they are generated by a different sequence of concept, see
Figure 4). To make this discussion formal, we fix a kernel $K\in\mathcal{K}$,
and we partition the event $E_{K}$ as follow

$E_{K}=E_{\text{meaningful}}\cup E_{\text{luck}}$ (65)

where

$\displaystyle
E_{\text{meaningful}}=E_{K}\;\cap\;\Big{\\{}\omega\in\Omega_{\rm
DM}:\;\;K\left({\bf x}^{\text{test}},{\bf x}_{1,1}\right)>K\left({\bf
x}^{\text{test}},{\bf x}_{1,s}\right)\text{ for all }2\leq s\leq
n_{\text{spl}}\Big{\\}}$ $\displaystyle
E_{\text{luck}}=E_{K}\;\cap\;\Big{\\{}\omega\in\Omega_{\rm DM}:\;\;K\left({\bf
x}^{\text{test}},{\bf x}_{1,1}\right)\leq K\left({\bf x}^{\text{test}},{\bf
x}_{1,s}\right)\text{ for some }2\leq s\leq n_{\text{spl}}\Big{\\}}$

The next two lemmas provide upper bounds for the probability of the events
$E_{\text{meaningful}}$ and $E_{\text{luck}}.$

######  Lemma 10.

$\displaystyle\mathbb{P}_{\rm
DM}[E_{\text{meaningful}}]\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}(K^{\star}_{\bf x}).$

###### Proof.

Define the event

$A:=\Big{\\{}\omega\in\Omega_{\rm DM}:\;\;K\left({\bf x}^{\text{test}},{\bf
x}_{1,1}\right)>K\left({\bf x}^{\text{test}},{\bf x}_{r,1}\right)\text{ for
all }2\leq r\leq R\Big{\\}}\\\ \cap\Big{\\{}\omega\in\Omega_{\rm
DM}:\;\;K\left({\bf x}^{\text{test}},{\bf x}_{1,1}\right)>K\left({\bf
x}^{\text{test}},{\bf x}_{r,2}\right)\text{ for all }1\leq r\leq R\Big{\\}}.$

This events involves only the first two training points of each category. On
the example depicted on Figure 4, that would be the points ${\bf x}_{1,1}$ and
${\bf x}_{1,2}$, the points ${\bf x}_{2,1}$ and ${\bf x}_{2,2}$, and finally
the points ${\bf x}_{3,1}$ and ${\bf x}_{3,2}$. The event $A$ consists in all
the outcomes in which, among these $2R$ training points, ${\bf x}_{1,1}$ is
most similar to ${\bf x}^{\text{test}}$. We then make two key remarks. First,
these $2R$ points are generated by $2R$ distinct sequences on concepts — so if
we restrict our attention to these $2R$ points, we are in a situation very
similar to the simpler data model $\varrho_{SDM}$ (i.e. we first generate $2R$
sequences of concepts, then from each sequence of concepts we generate a
single training point, and finally we generate a test point from the first
sequence of concepts.) We will make this intuition precise by appealing to the
fact that $\varrho_{SDM}$ is the marginal of $\varrho_{DM},$ and this will
allow us to obtain a bound for $\mathbb{P}_{\rm DM}[A]$ in term of the
permuted moment of $K^{\star}.$ The second remark is that
$E_{\text{meaningful}}$ is clearly contained in $A$, and therefore we have

$\mathbb{P}_{\rm DM}[E_{\text{meaningful}}]\leq\mathbb{P}_{\rm DM}[A]$ (66)

so an upper bound for $\mathbb{P}_{\rm DM}[A]$ is also an upper bound for
$\mathbb{P}_{\rm DM}[E_{\text{meaningful}}]$.

Let us rename some of the variables. We define ${\bf d}_{1},\ldots,{\bf
d}_{2R}$, and ${\bf y}_{1},\ldots,{\bf y}_{2R}$ as follow:

$\displaystyle{\bf d}_{2r-1}={\bf c}^{\prime}_{r}\quad\;\;\,\text{ and
}\quad{\bf d}_{2r}={\bf c}_{r}\qquad\;\;\text{ for }r=1,\ldots,R$
$\displaystyle{\bf y}_{2r-1}={\bf x}_{r,1}\quad\text{ and }\quad{\bf
y}_{2r}={\bf x}_{r,2}\qquad\text{ for }r=1,\ldots,R$

On the example depicted on Figure 4, that would be:

$\begin{matrix}{\bf y}_{1}={\bf x}_{1,1},&\;\;{\bf y}_{2}={\bf
x}_{1,2},&\;\;{\bf y}_{3}={\bf x}_{2,1},&\;\;{\bf y}_{4}={\bf
x}_{2,2},&\;\;{\bf y}_{5}={\bf x}_{3,1},&\;\;{\bf y}_{6}={\bf x}_{3,2}\\\ {\bf
d}_{1}={\bf c}_{1},&\;\;{\bf d}_{2}={\bf c}_{1}^{\prime},&\;\;{\bf d}_{3}={\bf
c}_{2},&\;\;{\bf d}_{4}={\bf c}_{2}^{\prime},&\;\;{\bf d}_{5}={\bf
c}_{3},&\;\;{\bf d}_{6}={\bf c}_{3}^{\prime}\end{matrix}$

In other words, the ${\bf y}_{r}$’s are the first two training points of each
category and the ${\bf d}_{r}$’s are their corresponding sequence of concepts.
With these notations it is clear that the training points ${\bf y}_{r}$ are
generated by distinct sequences of concepts, and that the test point ${\bf
x}^{\text{test}}$ is generated by the same sequence of concepts than ${\bf
y}_{1}$. Moreover the event $A$ can now be conveniently written as

$A=\\{\omega\in\Omega_{\rm DM}:\;\;K\left({\bf x}^{\text{test}},{\bf
y}_{1}\right)>K\left({\bf x}^{\text{test}},{\bf y}_{r}\right)\text{ for all
}2\leq r\leq 2R\\}.$

Let $h:{\mathcal{X}}^{2R+1}\to\real$ be the indicator function defined by

$h({\bf y}_{1},\ldots,{\bf y}_{2R},{\bf
x^{\text{test}}})=\begin{cases}1&\text{ if }K\left({\bf x}^{\text{test}},{\bf
y}_{1}\right)>K\left({\bf x}^{\text{test}},{\bf x}_{r}\right)\text{ for all
}2\leq r\leq 2R\\\ 0&\text{otherwise}\end{cases}$

We now recall the splitting $\omega=(\omega_{a},\omega_{b})$ described in
(58)-(59) and note that $\omega_{a}$ can be written as

$\omega_{a}=(\varphi\;\;;\;\;{\bf d}_{1},\ldots,{\bf d}_{2R}\;\;;\;\;{\bf
y}_{1},\ldots,{\bf y}_{2R}\;\;;\;\;{\bf x^{\text{test}}})$

Since $h$ only depends on the variables involved in $\omega_{a}$, and since,
according to Lemma 8, $\sum_{\omega_{b}}\varrho_{\rm
DM}(\omega_{a},\omega_{b})=\varrho_{\rm SDM}(\omega_{a})$, we obtain

$\displaystyle\mathbb{P}_{\rm DM}[A]$
$\displaystyle=\sum_{\omega_{a}\in\Omega_{a}}\sum_{\omega_{b}\in\Omega_{b}}h({\bf
y}_{1},\ldots,{\bf y}_{2R},{\bf x^{\text{test}}})\;\varrho_{\rm
DM}(\omega_{a},\omega_{b})$
$\displaystyle=\sum_{\omega_{a}\in\Omega_{a}}h({\bf y}_{1},\ldots,{\bf
y}_{2R},{\bf x^{\text{test}}})\;\varrho_{\rm SDM}(\omega_{a})$
$\displaystyle=\mathbb{P}_{\rm SDM}[\omega_{a}\in\Omega_{a}:\;\;K\left({\bf
x}^{\text{test}},{\bf y}_{1}\right)>K\left({\bf x}^{\text{test}},{\bf
y}_{r}\right)\text{ for all }2\leq r\leq 2R]$
$\displaystyle\leq\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}\mathcal{H}_{2R-1}(K^{\star}_{\bf x})$

where we have used Theorem 4 in order to get the last inequality (with the
understanding that $t+1=2R$.) Combining the above bound with (66) concludes
the proof. ∎

We now estimate the probability of the event $E_{\text{luck}}.$

######  Lemma 11.

$\displaystyle\mathbb{P}_{\rm DM}[E_{\text{luck}}]\leq\frac{1}{R}.$

###### Proof.

For $1\leq r\leq R$, we define the events

$\displaystyle B_{r}=\bigcap_{\begin{subarray}{c}1\leq r^{\prime}\leq R\\\
r^{\prime}\neq r\end{subarray}}\left\\{\omega\in\Omega_{\rm
DM}:\;\;\max_{2\leq s\leq n_{\text{spl}}}K({\bf x^{\text{test}}},{\bf
x}_{r,s})>\max_{2\leq s^{\prime}\leq n_{\text{spl}}}K({\bf
x^{\text{test}}},{\bf x}_{r^{\prime},s^{\prime}})\right\\}$

Note that the events $B_{r}$ involve only the training points with an index
$s\geq 2$: these are the familiar training points. On the example depicted on
Figure 4, these are the training points generated by ${\bf c}_{1},{\bf c}_{2}$
and ${\bf c}_{3}$. Let us pursue with this example. The event $B_{1}$ consists
in all the outcomes in which one of the points generated by ${\bf c}_{1}$ is
more similar to ${\bf x}^{\text{test}}$ than any of the points generated by
${\bf c}_{2}$ and ${\bf c}_{3}$. The event $B_{2}$ consists in all the
outcomes in which one of the points generated by ${\bf c}_{2}$ is more similar
to ${\bf x}^{\text{test}}$ than any of the points generated by ${\bf c}_{1}$
and ${\bf c}_{3}$. And finally the event $B_{3}$ consists in all the outcomes
in which one of the points generated by ${\bf c}_{3}$ is more similar to ${\bf
x}^{\text{test}}$ than any of the points generated by ${\bf c}_{1}$ and ${\bf
c}_{2}$. Importantly, the test point ${\bf x}^{\text{test}}$ is generated by
the unfamiliar sequence of concepts ${\bf c}_{1}^{\prime}$, and this sequence
of concept is unrelated to the sequence ${\bf c}_{1},{\bf c}_{2}$ and ${\bf
c}_{3}$. So one would expect that, from simple symmetry, that

$\mathbb{P}_{\rm DM}[B_{1}]=\mathbb{P}_{\rm DM}[B_{2}]=\mathbb{P}_{\rm
DM}[B_{3}].$ (67)

We will prove (67) rigorously, for general $R$, using Lemma 9 from the
previous subsection. But before to do so, let us show that (67) implies the
desired upperbound on the probability of $E_{\text{luck}}.$ First, note that
$E_{\text{luck}}\subset B_{1}$ and therefore

$\mathbb{P}_{\rm DM}[E_{\text{luck}}]\leq\mathbb{P}_{\rm DM}[B_{1}].$ (68)

Then, note that $B_{1}$, $B_{2}$ and $B_{3}$ are mutually disjoints, and
therefore, continuing with the same example,

$\mathbb{P}_{\rm DM}[B_{1}]+\mathbb{P}_{\rm DM}[B_{2}]+\mathbb{P}_{\rm
DM}[B_{3}]=\mathbb{P}_{\rm DM}[B_{1}\cup B_{2}\cup B_{3}]\leq 1$

which, combined with (67) and (68), gives $\mathbb{P}_{\rm
DM}[E_{\text{luck}}]\leq 1/3$ as desired.

We now provide a formal proof of (67). As in the proof of the previous lemma,
it is convenient to rename some of the variables. Let denote by ${\bf
fam}_{r}$ the variable that consists in the familiar training points from
category $r$:

${\bf fam}_{r}=({\bf x}_{r,2},\ldots,{\bf
x}_{r,n_{\text{spl}}})\in{\mathcal{X}}^{n_{\text{spl}}-1}$

With this notation we have ${\bf fam}_{r,s}={\bf x}_{r,s+1}.$ We now recall
the splitting $\omega=(\omega_{c},\omega_{d})$ described in (61)-(62), and
note that $\omega_{c}$ can be written as

$\omega_{c}=(\varphi;\;\;{\bf fam}_{1}\;\;;\;\;\ldots\;\;;\;\;{\bf
fam}_{R}\;\;;\;\;{\bf x^{\text{test}}}).$ (69)

Using Lemma 9 we have

$\displaystyle\sum_{\omega_{d}\in\Omega_{d}}\varrho_{\rm
DM}(\omega_{c},\omega_{d})$ $\displaystyle=\alpha\prod^{R}_{r=1}{\bf
1}_{\\{\mathring{\varphi}({\bf x}_{r,2})=\mathring{\varphi}({\bf
x}_{r,3})=\ldots=\mathring{\varphi}({\bf x}_{r,n_{\text{spl}}})\\}}$ (70)
$\displaystyle=\alpha\prod^{R}_{r=1}{\bf 1}_{\\{\mathring{\varphi}({\bf
fam}_{r,1})=\mathring{\varphi}({\bf fam}_{r,2})=\ldots=\mathring{\varphi}({\bf
fam}_{r,n_{\text{spl}}-1})\\}}$ (71)
$\displaystyle=\alpha\prod^{R}_{r=1}h(\varphi,{\bf fam}_{r})$ (72)

where $\alpha$ is the constant appearing in front of the product in Lemma 9 an
$h:\Phi\times\mathcal{{\mathcal{X}}}^{n_{\text{spl}}-1}\to\\{0,1\\}$ is the
indicator function implicitly defined in equality (71)-(72). With the slight
abuse of notation of viewing ${\bf fam}_{r}$ as a set instead of a tuple, let
us rewrite the event $B_{r}$ as

$\displaystyle B_{r}=\bigcap_{\begin{subarray}{c}1\leq r^{\prime}\leq R\\\
r^{\prime}\neq r\end{subarray}}\left\\{\omega\in\Omega_{\rm DM}:\;\;\max_{{\bf
x}\in{\bf fam}_{r}}K({\bf x^{\text{test}}},{\bf x})>\max_{{\bf x}\in{\bf
fam}_{r^{\prime}}}K({\bf x^{\text{test}}},{\bf x})\right\\}$

We also define the corresponding indicator function

$g({\bf fam}_{r},{\bf fam}_{r^{\prime}},{\bf
x^{\text{test}}})=\begin{cases}1&\text{ if }\displaystyle\max_{{\bf x}\in{\bf
fam}_{r}}K({\bf x^{\text{test}}},{\bf x})>\max_{{\bf x}\in{\bf
fam}_{r^{\prime}}}K({\bf x^{\text{test}}},{\bf x})\\\ \\\
0&\text{otherwise}\end{cases}$

We now compute $\mathbb{P}_{\rm DM}(B_{1})$ (the formula for the other
$\mathbb{P}_{\rm DM}(B_{r})$ are obtained in a similar manner.) Recall from
(69) that the variables involved in ${\bf fam}_{r}$ only appear in
$\omega_{c}$. Therefore

$\displaystyle\mathbb{P}_{\rm DM}[B_{1}]$
$\displaystyle=\sum_{\omega_{c}\in\Omega_{c}}\sum_{\omega_{d}\in\Omega_{d}}\left(\prod_{r=2}^{R}g({\bf
fam}_{1},{\bf fam}_{r},{\bf x^{\text{test}}})\right)\ \varrho_{\rm
DM}(\omega_{c},\omega_{d})$ (73)
$\displaystyle=\sum_{\omega_{c}\in\Omega_{c}}\left(\prod_{r=2}^{R}g({\bf
fam}_{1},{\bf fam}_{r},{\bf x^{\text{test}}})\right)\
\sum_{\omega_{d}\in\Omega_{d}}\varrho_{\rm DM}(\omega_{c},\omega_{d})$ (74)
$\displaystyle=\alpha\sum_{\omega_{c}\in\Omega_{c}}\left(\prod_{r=2}^{R}g({\bf
fam}_{1},{\bf fam}_{r},{\bf x^{\text{test}}})\right)\
\Bigg{(}\prod^{R}_{r^{\prime}=1}h(\varphi,{\bf fam}_{r^{\prime}})\bigg{)}$
(75)

where we have used (72) to obtain the last equality. Let us now compare
$\mathbb{P}_{\rm DM}(B_{1})$ and $\mathbb{P}_{\rm DM}(B_{2})$. Letting
$\mathcal{Z}:={\mathcal{X}}^{n_{\text{spl}}-1}$, and recalling that
$\omega_{c}=(\varphi;\;\;{\bf fam}_{1}\;\;,\;\;\ldots\;\;,\;\;{\bf
fam}_{R}\;\;;\;\;{\bf x^{\text{test}}})$, we obtain:

$\displaystyle\mathbb{P}_{\rm DM}[B_{1}]=\sum_{\varphi\in\Phi}\sum_{{\bf
fam}_{1}\in\mathcal{Z}}\cdots\sum_{{\bf fam}_{R}\in\mathcal{Z}}\sum_{{\bf
x^{\text{test}}}\in\mathcal{X}}\left(\prod_{\begin{subarray}{c}1\leq r\leq
R\\\ r\neq 1\end{subarray}}g({\bf fam}_{1},{\bf fam}_{r},{\bf
x^{\text{test}}})\right)\left(\prod_{r^{\prime}=1}^{R}h(\phi,{\bf
fam}_{r}^{\prime})\right)$ $\displaystyle\mathbb{P}_{\rm
DM}[B_{2}]=\sum_{\varphi\in\Phi}\sum_{{\bf
fam}_{1}\in\mathcal{Z}}\cdots\sum_{{\bf fam}_{R}\in\mathcal{Z}}\sum_{{\bf
x^{\text{test}}}\in\mathcal{X}}\left(\prod_{\begin{subarray}{c}1\leq r\leq
R\\\ r\neq 2\end{subarray}}g({\bf fam}_{2},{\bf fam}_{r},{\bf
x^{\text{test}}})\right)\left(\prod_{r^{\prime}=1}^{R}h(\phi,{\bf
fam}_{r}^{\prime})\right)$

From the above it is clear that $\mathbb{P}_{\rm DM}[B_{1}]=\mathbb{P}_{\rm
DM}[B_{2}]$ (as can be seen by exchanging the name of the variables ${\bf
fam}_{1}$ and ${\bf fam}_{2}$). Similar reasoning shows that the events
$B_{r}$ are all equiprobable, which concludes the proof. ∎

Combining Lemma 10 and 11, together with the fact that
$E_{K}=E_{\text{correct}}\cup E_{\text{luck}}$, concludes the proof of (63).
Inequality (63) implies inequality (26), which itself is equivalent to
inequality (14).

##  Appendix C Upper bound for the Permuted Moment of $K^{\star}$

This section is devoted to the proof of inequality (15), which we state below
as a theorem for convenience.

######  Theorem 5.

For all $0\leq\ell\leq L$, we have the upper bound

$\frac{1}{|{\mathcal{X}}|}\sum_{{\bf
x}\in{\mathcal{X}}}{\mathcal{H}}_{t}(K^{\star}_{\bf x})\leq\left(1-\sum_{{\bf
k}\in\mathcal{S}_{\ell}}\mathfrak{f}({\bf k})\mathfrak{g}({\bf
k})\right)+\frac{1}{t+1}\left(\max_{{\bf
k}\in\mathcal{S}_{\ell}}\;\mathfrak{f}({\bf k})\right).$ (76)

The rather intricate formula for the function $\mathfrak{f}$ and
$\mathfrak{g}$ can be found in the main body of the paper, but we will recall
them as we go through the proof.

We also recall that the optimal kernel is given by the formula:

$K^{\star}({\bf x},{\bf
y})=\;\frac{1}{s_{c}^{L}}\;\;\frac{\big{|}\\{\varphi\in\Phi:\varphi(x_{\ell})=\varphi(y_{\ell})\text{
for all }1\leq\ell\leq L\\}\big{|}}{|\Phi|}$ (77)

The key insight to derive the upper bound (76) is to note that each pair of
sentences $({\bf x},{\bf y})$ induces a graph on the vocabulary
$\\{1,2,\ldots,n_{w}\\}$, and that the quantity

$\big{|}\\{\varphi\in\Phi:\varphi(x_{\ell})=\varphi(y_{\ell})\text{ for all
}1\leq\ell\leq L\\}\big{|}$

can be interpreted as the number of equipartitions of the vocabulary that do
not sever any of the edges of the graph. This graph-cut interpretation of the
optimal kernel is presented in detail in Subsection C.1. In Subsection C.2 we
derive a formula for $K^{\star}$ which is more tractable than (77). To do this
we partition ${\mathcal{X}}\times{\mathcal{X}}$ into subsets on which
$K^{\star}$ is constant, then provide a formula for the value of $K^{\star}$
on each of these subsets (c.f. Lemma 16). With this formula at hand, we then
appeal to Lemma 3 to derive a first bound for the permuted moment of
$K^{\star}$ (c.f. Lemma 17). This first bound is not fully explicit because it
involves the size of the subsets on which $K^{\star}$ is constant. In section
C.3 we appeal to Cayley’s formula, a classical result from graph theory, to
estimate the size of these subsets (c.f. Lemma 18) and therefore conclude the
proof of Theorem 5.

We now introduce the combinatorial notations that will be used in this
section, and we recall a few basics combinatorial facts. We denote by
$\mathbb{N}=\\{0,1,2,\ldots\\}$ the nonnegative integers. We use the standard
notations

${n\choose k}:=\frac{n!}{k!(n-k)!}\qquad\text{ and }\qquad{n\choose
k_{1},k_{2},\dots,k_{m}}:=\frac{n!}{k_{1}!k_{2}!\cdots k_{n}!}$

for the binomial and multinomial coefficients, with the understanding that
$0!=1$. We recall that multinomial coefficients can be interpreted as the
number of ways of placing $n$ distinct objects into $m$ distinct bins, with
the constraint that $k_{1}$ objects must go in the first bin, $k_{2}$ objects
must go in the second bin, and so forth.

The Stirling numbers of the second kind $\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}$
are close relatives of the binomial coefficients.
$\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}$ stands for the number of ways to partition
a set of $n$ objects into $k$ nonempty subsets. To give a simple example,
$\genfrac{\\{}{\\}}{0.0pt}{}{4}{2}=7$ because there are 7 ways to partition
the set $\\{1,2,3,4\\}$ into two non-empty subsets, namely:

$\displaystyle\\{1\\}\cup\\{2,3,4\\},\qquad\\{2\\}\cup\\{1,3,4\\},\qquad\\{3\\}\cup\\{1,2,4\\},\qquad\\{4\\}\cup\\{1,2,3\\},$
$\displaystyle\\{1,2\\}\cup\\{3,4\\},\qquad\\{1,3\\}\cup\\{2,4\\},\qquad\\{1,4\\}\cup\\{3,4\\}.$

Stirling numbers are easily computed via the following variant of Pascal’s
recurrence formula 333Alternatively, Stirling numbers can be defined through
the formula
$\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}=\frac{1}{k!}\sum_{i=0}^{k}(-1)^{i}{k\choose
k-i}(k-i)^{n}$:

$\displaystyle\genfrac{\\{}{\\}}{0.0pt}{}{n}{1}=1,\qquad\genfrac{\\{}{\\}}{0.0pt}{}{n}{n}=1\qquad\text{
for }n\geq 1,$
$\displaystyle\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}=\genfrac{\\{}{\\}}{0.0pt}{}{n-1}{k-1}+k\;\genfrac{\\{}{\\}}{0.0pt}{}{n-1}{k}\qquad\text{
for }2\leq k\leq n-1.$

The above formula is easily derived from the definition of the Stirling
numbers as providing the number of ways to partition a set of $n$ objects into
$k$ nonempty subsets (see for example chapter 6 of [graham1989concrete]).
Table 2 shows the first few Stirling numbers.

Table 2: First five rows of the Strirling triangle for the Stirling numbers $\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}$. $n\backslash k$ | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
1 | 1 |  |  |  |
2 | 1 | 1 |  |  |
3 | 1 | 3 | 1 |  |
4 | 1 | 7 | 6 | 1 |
5 | 1 | 15 | 25 | 10 | 1

We recall that an undirected graph is an ordered pair $\mathcal{G}=(V,E)$,
where $V$ is the vertex set and

$E\subset\\{\\{v,v^{\prime}\\}:v,v^{\prime}\in V\text{ and }v\neq
v^{\prime}\\}$

is the edge set. Edges are unordered pairs of distinct vertices (so loops are
not allowed.) A tree is a connected graph with no cycles. A tree on $n$
vertices has exactly $n-1$ edges. Cayley’s formula states that there are
$n^{n-2}$ ways to put $n-1$ edges on $n$ labeled vertices in order to make a
tree. We formally state this classical result below:

######  Lemma 12 (Cayley’s formula).

There are $n^{n-2}$ trees on $n$ labeled vertices.

###  C.1 Graph-Cut Formulation of the Optimal Kernel

In this section we consider undirected graphs on the vertex set

${\mathcal{V}}:=\\{1,2,\ldots,n_{w}\\}.$

Since the data space ${\mathcal{X}}$ consists of sentences of length $L$,
graphs that have at most $L$ edges will be of particular importance. We
therefore define:

$\mathfrak{G}:=\\{\text{All graphs on ${\mathcal{V}}$ that have at most $L$
edges}\\}.$

In other words, $\mathfrak{G}$ consists in all the graphs
$\mathcal{G}=({\mathcal{V}},E)$ whose edge set $E$ has cardinality less or
equal to $L$. Since these graphs all have the same vertex set, we will often
identify them with their edge set. We now introduce a mapping between pairs of
sentences containing $L$ words, and graphs containing at most $L$ edges.

######  Definition 2.

The function $\zeta:{\mathcal{X}}\times{\mathcal{X}}\to\mathfrak{G}$ is
defined by

$\zeta({\bf x},{\bf y}):=\bigcup_{\begin{subarray}{c}1\leq\ell\leq L\\\
x_{\ell}\neq y_{\ell}\end{subarray}}\\{\\{x_{\ell},y_{\ell}\\}\big{\\}}.$ (78)

The right hand side of (78) is a set of at most $L$ edges. Since graphs in
$\mathfrak{G}$ are identified with their edge set, $\zeta$ indeed define a
mapping from ${\mathcal{X}}\times{\mathcal{X}}$ to $\mathfrak{G}.$ Let us give
a few examples illustrating how the map $\zeta$ works. Suppose we have a
vocabulary of $n_{w}=10$ words and sentences of length $L=6$. Consider the
pair of sentences $({\bf x},{\bf y})\in{\mathcal{X}}\times{\mathcal{X}}$ where

$\begin{matrix}&{\bf x}=[&2,&2,&8,&5,&9,&7&]\\\ &{\bf
y}=[&2,&5,&8,&2,&2,&1&]\end{matrix}$ (79)

Then $\zeta({\bf x},{\bf y})$ is the set of 3 edges

$\zeta({\bf x},{\bf
y})=\Big{\\{}\quad\\{2,5\\},\quad\\{9,2\\},\quad\\{7,1\\}\quad\Big{\\}}.$

which indeed define a graph on ${\mathcal{V}}$. Note that position $\ell=2$
and $\ell=4$ of $({\bf x},{\bf y})$ ‘code’ for the same edge $\\{2,5\\}$,
position $5$ codes for the edge $\\{9,2\\}$, and position $6$ codes for the
edge $\\{7,1\\}$. On the other hand, position $1$ and $3$ do not code for any
edge: indeed, since $x_{1}=y_{1}$ and $x_{3}=y_{3}$, these two positions do
not contribute any edges to the edge set defined by (78). We will say that
positions $1$ and $3$ are _silent_. We make this terminology formal in the
definition below:

######  Definition 3.

Let $({\bf x},{\bf y})\in{\mathcal{X}}\times{\mathcal{X}}$. If
$x_{\ell}=y_{\ell}$ for some $1\leq\ell\leq L$, we say that position $\ell$ of
the pair $({\bf x},{\bf y})$ is silent. If $x_{\ell}\neq y_{\ell}$ for some
$1\leq\ell\leq L$, we say that position $\ell$ of the pair $({\bf x},{\bf y})$
codes for the edge $\\{x_{\ell},y_{\ell}\\}$.

Note that if $({\bf x},{\bf y})$ has some silent positions, or if multiple
positions codes for the same edge, then the graph $\zeta({\bf x},{\bf y})$
will have strictly less than $L$ edges. On the other hand, if none of these
take place, then $\zeta({\bf x},{\bf y})$ will have exactly $L$ edges. For
example the pair of sentences

$\begin{matrix}&{\bf x}=[&1,&1,&1,&5,&6,&7]\\\ &{\bf
y}=[&2,&3,&4,&6,&7,&1]\end{matrix}$ (80)

does not have silent positions, and all positions code for different edges.
The corresponding graph

$\zeta({\bf x},{\bf
y})=\Big{\\{}\quad\\{1,2\\},\quad\\{1,3\\},\quad\\{1,4\\},\quad\\{5,6\\},\quad\\{6,7\\},\quad\\{7,1\\}\quad\Big{\\}}$

has the maximal possible number of edges, namely $L=6$ edges. From the above
discussion, it is clear that any graph with $L$ or less edges can be expressed
as $\zeta({\bf x},{\bf y})$ for some pair of sentences $({\bf x},{\bf
y})\in{\mathcal{X}}\times{\mathcal{X}}.$ Therefore
$\zeta:{\mathcal{X}}\times{\mathcal{X}}\to\mathfrak{G}$ is surjective. On the
other hand, different pair of sentences can be mapped to the same graph.
Therefore $\zeta$ is not injective. We now introduce the following function.

######  Definition 4 (Number of cut-free equipartitions of a graph).

The function $\mathcal{I}:\mathfrak{G}\to\mathbb{N}$ is defined by :

$\mathcal{I}(\mathcal{G})=|\\{\varphi\in\Phi:\varphi(v)=\varphi(v^{\prime})\text{
for all edge $\\{v,v^{\prime}\\}$ of the graph }\mathcal{G}\\}|$ (81)

Recall that $\Phi$ is the set of maps
$\varphi:{\mathcal{V}}\to\\{1,\ldots,n_{c}\\}$ that satisfy
$|\varphi^{-1}(c)|=s_{c}$ for all $1\leq c\leq n_{c}.$ Given a graph
$\mathcal{G}$, the quantity $\mathcal{I}(\mathcal{G})$ can therefore be
interpreted as the number of ways to partition the vertices into $n_{c}$
labelled subsets of equal size so that no edges are severed (i.e. two
connected vertices must be in the same subset.) In other words,
$\mathcal{I}(\mathcal{G})$ is the number of “cut-free” equipartition of the
graph $\mathcal{G}$, see Figure 5 for an illustration. Note that if the graph
$\mathcal{G}$ is connected, then $\mathcal{I}(\mathcal{G})=0$ since any
equipartition of the graph will severe some edges. On the other hand, if the
graph $\mathcal{G}$ has no edges, then $\mathcal{I}(\mathcal{G})=|\Phi|$ since
there are no edges to be cut (and therefore any equipartition is acceptable.)

(a) Cut-free

(b) Not cut-free

Figure 5: Two equipartitions of the same graph (each subsets of the
equipartitions contain $7$ vertices). The equipartition on the left is cut-
free (no edges are severed). The equipartition on the right is not cut-free (4
edges are severed). The optimal kernel $K^{\star}({\bf x},{\bf y})$ can be
interpreted as the number of distinct cut-free equipartitions of the graph
$\zeta({\bf x},{\bf y})$ (modulo some scaling factor.)

The optimal kernel $K^{\star}$ can be expressed as a composition of the
function $\zeta$ and $\mathcal{I}$. Indeed:

$\displaystyle K^{\star}({\bf x},{\bf y})$
$\displaystyle=\frac{1}{|\Phi|s_{c}^{L}}\;\;|\\{\varphi\in\Phi:\varphi(x_{\ell})=\varphi(y_{\ell})\text{
for all }1\leq\ell\leq L\\}|$ (82)
$\displaystyle=\frac{1}{|\Phi|s_{c}^{L}}\;\;|\\{\;\varphi\in\Phi:\varphi(v)=\varphi(v^{\prime})\text{
for all $\\{v,v^{\prime}\\}\in\zeta({\bf x},{\bf y})$ }\\}|$ (83)
$\displaystyle=\frac{1}{|\Phi|s_{c}^{L}}\;\;\mathcal{I}(\zeta({\bf x},{\bf
y}))$ (84)

where we have simply used that $\zeta({\bf x},{\bf
y}):=\bigcup_{\begin{subarray}{c}1\leq\ell\leq L\\\ x_{\ell}\neq
y_{\ell}\end{subarray}}\\{\\{x_{\ell},y_{\ell}\\}\big{\\}}$ to go from (82) to
(83). We will refer to (84) as the _graph-cut formulation_ of the optimal
kernel.

We have discussed earlier that the function
$\zeta:{\mathcal{X}}\times{\mathcal{X}}\to\mathfrak{G}$ is surjective but not
injective. We conclude this subsection with a lemma that provides an exact
count of how many distinct $({\bf x},{\bf y})$ are mapped by $\zeta$ to a same
graph $\mathcal{G}.$

######  Lemma 13.

Suppose $\mathcal{G}\in\mathfrak{G}$ has $m$ edges. Then

$|\zeta^{-1}(\mathcal{G})|=|\\{({\bf x},{\bf
y})\in{\mathcal{X}}\times{\mathcal{X}}:\zeta({\bf x},{\bf
y})=\mathcal{G}\\}|=m!\sum_{\alpha=m}^{L}{L\choose\alpha}\genfrac{\\{}{\\}}{0.0pt}{}{\alpha}{m}2^{\alpha}n_{w}^{L-\alpha}.$

###### Proof.

Fix once and for all a graph $\mathcal{G}=({\mathcal{V}},E)$ with edge set
$E=\\{e_{1},\ldots,e_{m}\\}$ where $m\leq L$. Given $0\leq\alpha\leq L$,
define the set

$\mathcal{O}_{\alpha}=\\{({\bf x},{\bf
y})\in{\mathcal{X}}\times{\mathcal{X}}:\zeta({\bf x},{\bf
y})=\mathcal{G}\text{ and }({\bf x},{\bf y})\text{ has exactly $\alpha$ non-
silent positions}\\}.$

We start by noting that the set $\mathcal{O}_{\alpha}$ is empty for all
$\alpha<m$: indeed, since $\mathcal{G}$ has $m$ edges, at least $m$ positions
of a pair $({\bf x},{\bf y})$ must be coding for edges (i.e., must be non-
silent) in order to have $\zeta({\bf x},{\bf y})=\mathcal{G}$. We therefore
have the following partition:

$\zeta^{-1}(\mathcal{G})=\bigcup_{\alpha=m}^{L}\mathcal{O}_{\alpha}\qquad\text{
and
}\qquad\mathcal{O}_{\alpha}\cap\mathcal{O}_{\alpha^{\prime}}=\emptyset\;\;\text{
if }\alpha\neq\alpha^{\prime}.$

To conclude the proof, we need to show that

$\left|\mathcal{O}_{\alpha}\right|={L\choose\alpha}\;\genfrac{\\{}{\\}}{0.0pt}{}{\alpha}{m}\;m!\;2^{\alpha}\;n_{w}^{L-\alpha}\qquad\text{for
all }m\leq\alpha\leq L.$ (85)

Consider the following process to generate an ordered pair $({\bf x},{\bf y})$
that belong to $\mathcal{O}_{\alpha}$: we start by deciding which positions of
(x,y) are going to be silent, and which positions are going to code for which
edge of the graph $\mathcal{G}$. This is equivalent to choosing a map
$\rho:\\{1,\ldots,L\\}\to\\{e_{1},\ldots,e_{m},s\\}$ where $\\{1,\ldots,L\\}$
denotes the $L$ positions, $e_{1},\ldots,e_{m}$ denote the $m$ edges of the
graph $\mathcal{G}$, and $s$ is the silent symbol. Choosing a map $\rho$
correspond to assigning a “role" to each position: $\rho(\ell)=e_{i}$ means