How to set up a DL classification model so that it selects from an ever changing menu

Question

The question is edited for clarity after tchainzzz's comments about meta-learning.

Let's say we have 10,000 pet pictures and 10,000 kids. Each kid is presented with 10 randomly picked pet pictures at a time. Each time, they have to pick the one picture that they like best. Our goal, during inference, is to predict probabilities on which picture (from 0 to 9) the (same) kids will pick. My struggle is how to construct a NN to make this classification.

Paths I've been thinking about or tried:

• I have created embeddings for kids and pictures using a (Netflix competition winner style) factorization method. The embeddings are pretty good: Visualizing the picture embeddings in a projector, similar pets are grouped together.

• The first thing I tried was to concatenate the embeddings of the 10 pictures and feed this together with the embedding of the kid. The output layer a softmax and CE loss. But it doesn't work - I guess it's to difficult for the model to "understand" where one picture embedding starts and another stops, and to relate each of the embeddings to the 10 categories in the output layer.

• tchainzzz pointed me in the direction of meta-learning, including few-shot learning (before I had clarified my case). But these methods are mainly intended for classifying the entities (is the pet a dog or a cat?) and they are intended for limited training sets. In our case, we're not classifying the pictures (we already know which ones are cats and which ones are dogs) and we have ample training data.

• Why not use metric learning with siamese networks? I don't think it will work here, because this method assumes that there is one ideal pet that each kid would select, and we just need to figure out which picture is more like that ideal pet. But we don't have an ideal pet for each kid, only the previously performed selections.

• Why not use some kind of ranking solution? (We could probably create a system, like elo chess ranking. Every time a kid selects a picture, that picture would get a higher ranking, particularly for that kid, and more so if the competing picture already have a high ranking.) Because that's not a neural network classification architecture. I can add such a ranking as a feature, but the question is how to create an NN model so that it "understands" that the classification should happen from a menu of 10 available dishes.

• There is, however, elements from 'siamese networks' that I've been thinking about. Not the metric part of siamese architechture, but the 'shared weights' part: A possible solution to my problem could be that I insert the embedding for the kid next to the embedding of one picture (i from 0 to 9) into 10 siamese twin networks (i from 0 to 9) sharing the same weights. Each twin would have one output mapped to 10 classes in a softmax layer. (The softmax layer is on the outside of the siamese part of the network.) I have tried this quickly, without much luck. But so far, this is my best idea and i'm continuing to work in this direction.

Any further advice or ideas would be welcome!

Answer 1

For matching problems, there are mainly two approaches:

• Single network to embed object A and object B: In natural language processing, the input would be "[CLS] SentenceA [SEP] SentenceB [SEP]". Then the neural network would measure the difference between the two sentences. In computer vision, you would need to concatenate the two images (as you do not have a sequence).
• Siamese network: It is still a single network, but you would first run "object A" through the network and then "object B" through the same network. The result is two vectors of size batch_size x n.

The second approach is a bit more complicated because you have to turn the outputs "object A" and "object B" into a single number.

However, this approach is also more common in computer vision. As you have two vectors of size n, you can compute the scalar product between both objects to obtain a single value. The scalar product can be interpreted as cosine similarity. Normalizing the two vectors is maybe not necessary in deep learning. The next step is to define a loss function $L(a^Tb, y)$ between objects $a^Tb$ and the ground truth $y$.

Note that a batch should not only consist of positive examples. So you have to sample negative examples for each positive example (noise contrastive estimation). See this question.

I described the general approach, but what works best depends on the dataset. For example, instead of using the scalar product, you could also try the mean squared error. Besides the papers, I mentioned in the comments, you can also look at contrastive losses.

Answer 2

NOTE: I'm still editing this post, need a bit more time to finish

Here's a philosophical aside on the limits of few-shot learning. It is not exactly the answer to the question, but I guess it could help set the expectations straight.

Part 1: Naive estimate of number of samples needed for classifier convergence. Let's say we did some dimensionality reduction on the available images and extracted $N$ features. We could argue that these features are representative of the images as finer features are weak and likely imperceptible for the human eye. For simplicity, let us assume that all of the features are orthogonal. Further, for the sake of the argument, let's assume that exactly 1 of these features is used by the participant to classify the images as those they like vs those they don't. Our goal is to find which feature that is. We have to know this well, or we would not be able to make predictions. Let's assume that each feature has a standard normal distribution $\mathcal{N}(0,1)$ over the available images, and that the important feature will be greater than zero if the image is liked, otherwise below, meaning that the participant will like approximately half of all the images. The question now is: how many trials do we require to find the correctly-predicting feature. The expected number is $\log_2 N$ - there will be some features which will be predictive at random, and at every trial each of them will have 50% probability of still being predictive by chance, meaning that 50% of them will drop out. A related and a bit more realistic question is - how many trials do we require to guarantee that all non-informative features have dropped off (e.g. with 95% confidence). A little less intuitively, but this value also scales as $\log_2 N$. The proof is as follows: after $t$ trials, the probability that one non-informative feature still looks informative by chance is $p_1 = 2^{-t}$. We are looking for the probability that $N$ non-informative features have all been revealed, and we want this probability to be greater or equal to 95%. This can be written as $(1 - p_1)^N \geq 0.95$. If we solve this inequality for $t$ and use series expansion, we will get $t \geq C + \log_2 N + O(\frac{1}{N})$ for some small constant $C$.

Part 2: Effect of noise. But this is the absolute lowest unrealistic estimate. The difficulty starts when we consider that participants such as humans and mammals are known to have variance in their choice, meaning that they do not stay consistent to their general strategy at all trials. To model this, we must allow for a fraction of trials to be non-informative. Let's say that fraction of correct trials for informative features is $p_I = 90\%$. We need a condition to refute the feature if it is non-informative. Dropping some finer details of hypothesis testing, we will find the fraction $\phi=\frac{t_{good}}{t}$ of trials for which the feature is informative, and compare it with $p_I$. The more trials we measure, the closer we would expect the observed fraction to be to the true fraction. So, we would consider the channel as informative, if the observed fraction of trials $\phi$ is greater or equal to some threshold $\phi_0$, which can be written as

$$\phi_0 = p_I+\frac{\sigma_I}{\sqrt{t}}K$$

where $\sigma_I$ is the variance of the fraction (in our binomial case it is $\sigma_I = \sqrt{p_I(1-p_I)}$), and $K$ is some constant which depends on the desired confidence of the test (for normal approximation it is $K=\sqrt{2}erf^{-1}(2\alpha - 1)$ where $\alpha$ is the confidence level). Next, we need to find the probability that a non-informative feature fails the test $\phi \geq \phi_0$, namely, that the result will be $\phi < \phi_0$. For a non-informative trial, the fraction of correct trials will be $p_{NI}=50\%$. Using DeMoivre-Laplace approximation, the sample fraction for non-informative features will be normally distributed, namely $$\phi \sim \mathcal{N}(\frac{1}{2}, \frac{1}{4t})$$

Part 3: Effect of feature synergy. Finally, situation is further complicated if individual features are insufficient for good prediction, and synergistic predictors are required. For example, if we require a pair of features to be simultaneously high (e.g. a person likes red images that are also very sharp), then we effectively have $N^2$ features to consider.

TL;DR: Humans have to be cheating when performing few-shot learning. The only way to learn fast is to have prior information on what features are likely to be salient (predictive of outcome).