How to formalize learning in terms of information theory?

Question

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.

Answer 1

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.