Characterizing Learning in Deep Neural Networks using a Tractable Algorithmic Complexity Estimator

Algorithmic complexity measures the intrinsic structure (or randomness) of strings. Kolmogorov-Chaitin-Solomonoff (KCS) complexity is the length of the shortest program that can output a string and halt over all possible programs; due to this reason it is uncomputable. Estimating the algorithmic probability of strings using simulations of finite Turing machines is one way of obtaining tight estimations of KCS complexity of strings. For two dimensional objects, this is currently doable only for binary strings using the block decomposition method (BDM). In this work, we present the quantized block decomposition (QuBD) method to extend the estimation of algorithmic complexity to any $k$-ary objects such as the weights of deep neural networks. We show theoretically that the proposed QuBD method yields better KCS complexity estimations than BDM that relies on binarization. We further study how algorithmic complexity interacts with learning in deep neural networks by tracking the evolution of weights during training. Using a variety of experiments we show that algorithmic complexity decreases as models learn, it correlates with generalization performance and can be used as a diagnostic measure to perform model compression.