Where can I find a machine learning library that implements loss functions measuring the Algorithmic Information Theoretic-friendly quantity "bits of information"?

To illustrate the difference between entropy, in the Shannon information sense of "bits" and the algorithmic information sense of "bits", consider the way these two measures treat a 1 million character string representing $\pi$:

Shannon entropy "bits" ($6$ for the '.'): $\lceil 1e6*\log_2(10) \rceil+6$

Algorithmic "bits": The length, in bits, of the shortest program that outputs 1e6 digits of $\pi$ .

All statistical measures of information, such as KL divergence, are based on Shannon information. By contrast, algorithmic information permits representations that are fully dynamical as in Chomsky type 0, Turing Complete, etc. languages. Since the world in which we live is dynamical, algorithmic models are at least plausibly more valid in many situations than are statistical models. (I recognize that recursive neural nets can be dynamical and that they can be trained with statistical loss functions.)

For a more authoritative and formal description of these distinctions see the Hutter Prize FAQ questions Why aren't cross-validation or train/test-set used for evaluation? and Why is Compressor Length superior to other Regularizations? For a paper-length exposition on the same see "A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions".

From what I can see, machine learning makes it difficult to relate loss to algorithmic information. Such an AIT-friendly loss function must, by definition, measure the number of bits required to reconstruct, without loss, the original training dataset.

Let me explain with examples of what I mean by AIT-friendly loss functions, starting with the baby-step of classification loss (usually measured as cross-entropy):

Let's say your training set consists of $P$ patterns belonging to $C$ classes. You can then construct a partial AIT loss function providing the length of the corrections to the model's classifications with a $P$-length vector, each element containing a $0$ if the model was correct for that pattern, or the class if not. These elements would each have a bit-length of $\lceil \log_2(C+1) \rceil$, and be prefixed by a variable length integer storing $P$. The more $0$ elements, the more compressible this correction vector until, in the limit, a single run-length code for $P$ $0$'s is stored as the correction, prefixed by $P$ and the length of the binary for the RLE algorithm itself. The bit-length of these, taken together, would comprise this partial loss function.

This is a reasonable first cut at an AIT-friendly loss function for classification error.

So now let's go one step further to outputs that are numeric, the typical approach is a summation of a function of individual error measures, such as squaring or taking their absolute value or whatever -- perhaps taking their mean. None of these are in units of bits of information. To provide the correction on the outputs to reproduce the actual training values requires, again, a vector of corrections. This time it would be deltas, the precision of which must be adequate to the original data being losslessly represented, hence requiring some sort of adaptive variable length quantity representation(s). These deltas would likely have a non-uniform distribution so they can be arithmetically encoded. That seems like a reasonable approach to another AIT-friendly loss function.

But now we get to the "model parameters" and find ourselves in the apparently well-defined but ill-founded notions like "L2 regularization", which are defined in terms of ill-defined "parameters", e.g. "parameter counts" aren't given in bits.

I'll grant that L2 regularization sounds like it is heading in the right direction by squaring the weights and summing them up, but when one looks at what is actually being done, it is:

  • applying additional functions to the sum such as mean
  • asking for a scaling factor to apply
  • applying the regularization on a per-layer basis rather than the entire model

I'm sure I missed some of the many ways L2 regularization fails to be AIT-friendly.

Finally, there is the model's pseudo-invariance, measured, not simply in terms of its hyperparameters but in terms of the length of the (compressed archive of the) actual executable binary running on the hardware. I say 'pseudo' because there is nothing that says one cannot vary, say, the number of neurons in a neural network during learning -- nor even change to another learning paradigm than neural networks during learning (in the most general case).

So that's pretty much the complete loss function down to the Universal Turing Machine iron, but I'd be happy to see just a reference to an existing TensorFlow or another library that tries to do even a partial loss function for AIT-theoretic learning.

  • $\begingroup$ Ok, I understand that you are interested in a measure that returns the number of bits of the shortest program that outputs something. But how do you want to use this as a loss function? Meanwhile, if you haven't found it yet, have a look at pypi.org/project/pybdm. $\endgroup$
    – nbro
    Commented Jul 13, 2020 at 18:38
  • $\begingroup$ Yes, that's in the right direction. What I'm more interested in is something that works with existing ML frameworks like Keras, etc. Of course it is always possible to write custom loss functions, but there is enough going on in the ML field and AIT has been understood by the theorists for 50 years, that I was hoping to avoid doing that. $\endgroup$ Commented Jul 14, 2020 at 3:06


You must log in to answer this question.

Browse other questions tagged .