Link to original article
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Towards Measures of Optimisation, published by mattmacdermott on May 12, 2023 on LessWrong.
We would like a mathematical theory which characterises the intuitive notion of ‘optimisation’.
Before Shannon introduced his mathematical theory of communication, the concept of ‘information’ was vague and informal. Then Shannon devised several standardised measures of it, with useful properties and clear operational interpretations. It turned out the concept of information is universal, in that it can be quantified on a consistent scale (bits) across various contexts.
Could something similar be true for ‘optimisation’?
In this post we review a few proposed ways to measure optimisation power and play around with them a bit.
Our general setup will be that we’re choosing actions from a set A to achieve an outcome in a set X. We have some beliefs about how our actions will affect outcomes in the form of a probability distribution pa∈ΔX for each a∈A. We also have some preferences, either in the form of a preference ordering over outcomes, or a utility function over outcomes. We will also assume there is some default distribution p∈ΔX, which we can interpret either as our beliefs about X if we don’t act, or if we take some default action[1].
Yudkowsky
Yudkowsky’s proposed definition just makes use of a preference ordering ⪰ over X. To measure the optimisation power of some outcome x, we count up all the outcomes which are at least as good as x, and divide that number by the total number of possible outcomes. It’s nice to take a negative log to turn this fraction into a number of bits: OP(x)=−log|{x′∈X∣x′⪰x}X|. If I achieve the second best outcome out of eight, that's −log28=2 bits of optimisation power.
If the outcome space is infinite, then we can't count the number of outcomes at least as good as the one we got, so we need a measure to integrate over. If we make use of our default probability distribution here, the resulting quantity has a nice interpretation. ∫x′⪰xp(x′)dx′∫p(x′)dx′ is just ∫x′⪰xp(x′)dx′: the default probability of doing as well as we did. Since we're always assuming we've got a default distribution, we might as well define OP like this even in the finite-domain case. Again we’ll take a log to get OP(x)=−log∫x′⪰xp(x′)dx′. Now 2 bits of optimisation power means the default probability of doing this well was 14.
So far we’ve just been thinking about the optimisation power of achieving a specific outcome. We can define the optimisation power of an action as the expected optimisation power under the distribution it induces over outcomes: OP(a)=∫pa(x)OP(x)dx. The above definitions just make use of a preference ordering. If we do have a utility function u:XR then we’d like our definitions to make use of that too. Intuitively, achieving the second best outcome out of three should constitute more optimisation power in a case where it’s almost as good as the first and much better than the third, compared to a case where it’s only slightly better than the third and much less good than the first[2].
Analogously to how we previously asked ‘what fraction of the default probability mass is on outcomes at least as good as this one?’ we could try to ask ‘what fraction of the default expected utility comes from outcomes at least as good as this one?’.
But making use of utility functions in the above definition is tricky. Recall that utility functions originate from the Von Neumann-Morgenstern theorem, which says that if an agent choosing between probabilistic mixtures of options satisfies some weak rationality criteria then it acts as if it maximises expected utility according to a utility function u:XR. The utility function produced by the VNM-theorem is only defined up to positive affine transformations, meaning that the utility function u′=au+b, for any a∈R>0 and b∈R, equally...
view more