[tr352]

Author of this work here (and a bit surprised to find this on hacker news).

I don't disagree with your point about probability. However, there are various alternatives to probability which can be more appropriate for certain applications. For instance, with degrees of surprise (or ranks as they are called) you do not need to know exact probabilities, although the price you pay is that the scale is more coarse grained. If you reason about events that are either very probable or very improbable, then degrees of surprise are easier to work with than probabilities.

There's also a computational benefit. Execution of a ranked program is done much like a non-deterministic program where choice points execute "least surprising first". Compare that with the sampling techniques necessary in probabilistic programming that do not even provide exact results.

[wnoise]

What I don't understand is _what_ these applications are. What does this surprise value tell me, and how can it be calibrated to anything quantitative? What's the equivalent of statistics that I can use to alter my original model's rankings to conform to what I observe?

I can understand ranking as coarse-graining of probability if there's some way to approximately map it back to the standard notion of probability.

On the other hand, using rank to direct collections of traces in a well-defined order is admittedly a neat trick; I can see using it to find something like the "most reasonable" or "easiest to explain" solution to a given logic problem. (I have actually seen a hand-coded version for Sudoku that attempts to minimize the backtracking depth to make it as easy to explain as possible.) But when would I want to do that to a program where the ranks represent instead how common a given event is? Verifying the no-exception case first? Is that useful?

[tr352]

Ranks represent subjective degrees of belief but they do not, like subjective probabilities, nicely map to relative frequencies. So compared to probabilities, ranks are indeed limited in this regard. For instance, you can learn probabilities from data but there's no obvious way to learn ranks from data.

But for subjective belief they're still useful. Consider the problem of diagnosing a system with components that fail in rare cases. However we have no idea about failure probabilities. We can then use ranks. A diagnosis for some observed behaviour would then be the least surprising (i.e., lowest ranked) failure state that explains the observed behaviour. This is also the reason for least-surprising-first execution: the most important prediction or hypothesis is the most likely one and thus the least surprising one. There are some concrete examples in the paper which demonstrate this.

I am currently thinking about combining probabilities with ranks so that you can reason about both kinds of uncertainty in the same model. This could be implemented using a programming language that supports both ranked choice statements and probabilistic choice statements.