# How to formalize learning in terms of information theory?

Consider the following game on a MNIST dataset:

1. There are 60000 images.
2. You can pick any 1000 images and train your Neural Network without access to the rest of images.
3. Your final result is prediction accuracy on all dataset.

How to formalize this process in terms of information theory? I know that information theory works with distributions, but maybe you can provide some hints how to think in terms of datasets instead of distributions.

1. What is the information size of all datasets. My first idea was that each image is iid from uniform distribution and information content = -log2(1/60000). But common sense and empirical results (training neural network) show that there are similar images and very different images holding a lot more information. For example if you train NN only on good looking images of 1 you will get bad results on unusual 1s.
2. How to formalize that the right strategy is to choose as much as possible different 1000 images. I was thinking to take image by image with the highest entropy relative to the images you already have. How to define distance function.
3. How to show that all dataset contains N bits of information, training dataset contain M bits of information and there is a way to choose K images < 60000 that hold >99.9% of information.

In short: It is easy to quantify information, but it is not easy to quantify its usefulness I'm not sure how exactly you are looking to formalise your experiment, but it might be helpful to consider these points:

1. There is no such thing as an absolute measure of information. The amount of information contained in some dataset is dependent on the underlying assumptions that are made when interpreting it, and therefore, the quantity of information conveyed is also dependent on the encoder/decoder (for example, a neural network). See the Wikipedia article on Kolmogorov Complexity.

2. Entropy is a useful measure of information content when you assume each sample is iid, but this would be a very bad assumption to make for natural images, since they are highly structured. For example, imagine an image with 50% black pixels and 50% white pixels that can be arranged in any configuration - not matter how you arrange them, wether it looks like random noise, a text paragraph, or a chequer board, the entropy value will be identical for each, even though our intuition tells us otherwise (see attached image). The discrepancy between our intuition and the entropy value arises because our intuition does not interpret the image through the "lens" of iid pixels, but rather, hierarchical receptive fields in the visual cortex (somewhat analogous to convolutional neural networks).

3. Calculating the entropy of pixel values in one image is somewhat useful, but calculating the "entropy" of a set of images would not be useful, because each image as a whole is treated as if it were a unique arbitrary symbol. I assume this is what you meant by "the information size of all datasets"

4. KL-divergence is a distance function that is often used to compare two distributions. Intuitively, it represents the redundant bits generated by a non-ideal compression program that assumes an incorrect data distribution. However, KL-divergence between two natural images will not give you a particularly meaningful result.

If I am not mistaken, you want to find some information metric that will enable you to pick the smallest number of the most optimal images for training and get a good test score with the network. Is that correct? It is an interesting idea. However, in order to define such a metric, we might have to know in advance what features of an image are the most significant for classification, which in some ways defeats the point of using machine learning in the first place, where non-obvious and "hidden" features are exploited.

• Correct. Behind each new image, there are some most significant features for classification and some features we already know. The task is to identify these interesting images and select them for our training dataset. What do you mean by "defeats the point of using machine learning"? – Oleg Dats Jan 7 '20 at 10:48
• What I mean is the following: the task of finding useful and interesting features in a dataset (and therefore picking optimal images) is not too different from the task of the neural network itself. In most cases, we use a neural network because understanding or even seeing such features is a problem that we cannot solve directly. – Barium Nitrate Jan 7 '20 at 11:42
• To illustrate the point, let's consider a dataset that is not so familiar. Let's say we want to build a classification network that characterises pictures of various types of grey rock. For someone who is not a geologist, they would have no idea as to what kinds of features to look for in the rock, let alone the rules by which to classify it. Let's now give this person a neural network and tell him to pick a small subset of training images. How is he going to do this when he has no prior knowledge or experience about rocks? – Barium Nitrate Jan 7 '20 at 11:47
• I would create a few coordinates: size, color and shape and choose extreme examples (min / max values). I was thinking to use variational autoencoder (channel) and choose the next images that perform poorly on trained VE. It means some images will give me more information / surprise than others. – Oleg Dats Jan 7 '20 at 12:15