EbTech

There's a link to the repo with our own rating system package. Maybe I should have shown that directly? The intention was to specifically draw attention to this finding.

The reference by Rathmanner & Hutter presents a useful analogy. It argues that Kolmogorov complexity (and Solomonoff induction) are best viewed as a conceptual gold standard, like a perfect chess computer that does an exhaustive tree search. Practical methods are approximations.

There are a few results where researchers were able to automatically infer evolutionary trees and such, by using a standard compression algorithm in place of K(x).

Thanks for the detailed critique! I'll take some time to think about how to better make the points that I wanted to convey with those sections.

Thanks! I hope to better address your concerns in Part 2.

Hm I admit it's hard to talk convincingly about election prediction, since we don't have practical algorithms to do this; a lot of it comes down to human judgment.

The philosophical point (which might be approximated algorithmically someday, or by intelligent minds today) is that your election probabilities should come out of an overall highly compressed model of the world. In theory, a Bayesian who uses the prior 2^-K(x) over all strings x should, with sufficient life experience, come up with good estimates, in a certain sense.

I'll have to think about this example more carefully when fulfilling my promise of writing about how this theory relates to everyday decision-making. Thanks for pointing out a potential weakness :)

1) I rather like the subjective view! Bayesians used to struggle to justify a choice of prior, but it turns out that 2^-K(x) is universal in the sense that it never falls below a constant factor of any given (semi-)computable finite (semi)-measure.

2) Sorry, I should have clarified that the programs are deterministic. So if you want to use an RNG, you also have to supply a string of random bits that cause the RNG to output forty digits of pi.

Thanks. I should clarify that the computer is deterministic, so as to avoid building randomness into the definition of randomness!

I skimmed over an example too quickly, but your intuition is about right. For that sequence, two possible programs are:

- Compute and print the first 40 digits of pi.

- Decompress the following string according to a Shannon code with probabilities (1/36,1/18,1/12,[etc]): [insert code]

Thanks! :)

I wasn't planning to go there! While I enjoy the idea, for now I'm trying to focus on what's needed to make sense of the problem of induction. Is there a nice connection that I missed?

I don't think frequentism is "bad"; just insufficient as a gold standard interpretation of probabilistic claims. I liked an analogy from the reference by Rathmanner & Hutter: the most "correct" chess-playing program involves a complete search along the tree of possible games. In practice, we try to approximate this ideal.

In the case of Kolmogorov complexity, a reasonable takeaway might be to use the shortest program that we're able to find, even if it's not the shortest overall.

The compression code can be specified first. If you have a lot of data, the specification will be negligible in length, compared to the code itself. Together, the specification and the Shannon code give an upper bound on the Kolmogorov compmlexity. If this is the shortest known program, we may consider the Shannon code probabilities as our "best explanation" of the data.

You can also get posterior probabilities using a universal prior such as 2^-K(x), but of course, this can only be approximated in the limit of infinite runtime.

Fair enough! I'd like to point out that the Kolmogorov complexity approach can make sense of subjective probability too. Since you lack precise enough information to predict the dice roll, the most compressed way to write down your observations will involve a Shannon-style code with your subjective probabilities. If you have enough information but not enough computational power, the resource-bounded variants of Kolmogorov complexity may be more applicable.

Since this topic isn't so well-known, I wrote the case arguing that frequentist interpretations don't work, but algorithmic information theory (Kolmogorov complexity) does. I want to make this accessible and persuasive, so thoughts, questions, and arguments would be appreciated!

Suggestions are welcome; I'm still learning Rust.

To put context around my provocative comment earlier: I write C++ professionally. C++ is the right choice for my organization, though for purely historical reasons. In the long run, I think we'd all be better off if Rust or similar languages replaced their predecessors. So my comment came from a place of personal frustration, the same that led me to find Rust in the first place.

The old wording was too negative; I'm just excited to show that contest programming, which one might imagine to be hard to translate, is not only practical but indeed arguably nicer in Rust.

I made this cookbook specifically to show it doesn't have to be so hard. While designing an industrial-strength data structure library is an advanced skill, there are easier ways to implement the core ideas that should suffice for contest and coursework purposes. Very few people have to build actual libraries.

What's their philosophy? I think Petr was using C# at some point.

Fair point, it's fixed now.