3 ms·
Very cool. My only niggle is that PCA doesn't 'feel like' Kolmogorov Complexity to me: it's much closer to Shannon information than Algorithmic information. Sh
by chriswarbo 6y ago
Very cool. My only niggle is that PCA doesn't 'feel like' Kolmogorov Complexity to me: it's much closer to Shannon information than Algorithmic information.
Shannon information depends on population statistics of messages, usually has a 'shallow' and domain-specific interpreter (to turn encodings back into messages, e.g. like a Huffman tree), and tries to minimise the average length of a set of encoded messages. In this case the NN is the interpreter, the length of the encoding is the number of deformation axes, and the population is the training data (which we hope is representative of the real data).
Algorithmic information is different. It depends on patterns within an individual message, rather than across a population. The interpreter is a Universal Turing Machine (or equivalent), which is general-purpose. Encodings are programs which output a message, and can be arbitrarily 'deep' by running for an arbitrary amount of time.
Another way to look at it is: using PCA to solve the problem of 'automatically decide which deformation axes to include' is slightly interesting; much more interesting is the problem of 'how can we automatically decide that this data should be modelled as a set of deformations along various axes?'. That's a much harder problem, and tends to require a lot of search through program-space (whether NNs or GOFAI).
- yters 6y agoShannon info and KC are asymptotically equivalent.
- chriswarbo 6y agoThat's why I used 'scare quotes'. It's very similar (perhaps provably equivalent, I'm not sure) to how Frequentist and Bayesian probabilities are asymptotically equivalent; yet offer their own perspective on few/one-shot cases. In my experience, general practice w.r.t. Shannon information is to manually pick a model with some numerical parameters (Huffman tree, deformation-axes-NN, etc.), then set those parameters to work well on an example population. General practice w.r.t. algorithmic information seems to involve searching program space for a good model. The adjustable part is the language, which can certainly be manually tailored to the application, but doesn't tend to be the bulk of the work (e.g. automatically searching for an efficient language tends to be redundant once we're doing program search; since those programs will contain their own abstractions in any case).