How to measure optimisation power
As every school child knows, an advanced AI can be seen as an optimisation process—something that hits a very narrow target in the space of possibilities. The Less Wrong wiki entry proposes some measure of optimisation power:
One way to think mathematically about optimization, like evidence, is in information-theoretic bits. We take the base-two logarithm of the reciprocal of the probability of the result. A one-in-a-million solution (a solution so good relative to your preference ordering that it would take a million random tries to find something that good or better) can be said to have log2(1,000,000) = 19.9 bits of optimization.
This doesn’t seem a fully rigorous definition—what exactly is meant by a million random tries? Also, it measures how hard it would be to come up with that solution, but not how good that solution is. An AI that comes up with a solution that is ten thousand bits more complicated to find, but that is only a tiny bit better than the human solution, is not one to fear.
Other potential measurements could be taking any of the metrics I suggested in the reduced impact post, but used in reverse: to measure large deviations from the status quo, not small ones.
Anyway, before I reinvent the coloured wheel, I just wanted to check whether there was a fully defined agreed upon measure of optimisation power.
Yudkowsky’s attempt seems to be of little practical use—as I explain in the comments there and here. It’s a combination of a not-very-useful concept and misleading terminology.
Legg’s AIQ seems to be a much more reasonable approach. Mahoney has previously done something similar.
I discussed a third group’s attempt: http://lesswrong.com/lw/42t/aixistyle_iq_tests/
Thanks for the links, but I don’t understand your objections—when measuring the optimisation power of a system or an AI, costs such as cycles, memory use, etc… are already implicitly included in Eliezer’s measure. If the AI spends all it’s time calculating without ever achieving anything, or if it has too little memory to complete any calculations, it will achieve an optimisation of zero.
Can you make sense of Shane Legg’s objection, then?
One of my criticisms was this:
I don’t see the point of calling something “optimisation power”—and then using it to award a brain-dead algorithm full marks.
I think your objection shows that you failed to read (or appreciate) this bit:
No “limited resources”, just “preference ordering”.
I would say that that the simple algorithm he describes has immense optimisation power. If there were a competitive situation, and other competent agents were trying to derail its goal, then its optimisation power drops close to zero. If your objection is that it’s wrong to define a single “optimisation power” floating platonically above the agent, then I agree.
His very next paragraph is:
“outcome achieved”. Hence the optimisation is measuring how effective the agent is at implementing its agenda. An agent that didn’t have the ressources to think well or fast enough would score low, because it wouldn’t implement anything.
The article talks about “preference ordering”. There’s no mention of how long the preference ordering takes to output. Resource constraints are missing from the whole article. It’s optimisation power without consideration of resource limitation. Exhaustive search wins that contest—with the highest possible score.
Even if you factor in resource constraints (for example by imposing time and resource limits) - this is still a per-problem metric—while the term “optimisation power” suggests some more general capabilities.
“outcome achieved”, “did you hit an outcome”, “optimization processes produce surprises”, “relative improbability of ‘equally good or better’ outcomes”—he’s talking about the outcome produced (and then using the preference orderings to measure optimisation power given that that outcome was produced).
The time taken is not explicitly modeled, but is indirectly: exhaustive search only wins if the agent really has all the time in the world to implement its plans. An AI due to get smashed in a year if it doesn’t produce anything will have an optimisation of zero if it uses exhaustive search.
“An optimisation of zero” ?!?
Are you objecting to the phrasing or to the point?
That was the terminology—though it isn’t just the terminology that is busted here.
Frankly, I find it hard to believe that you seem to be taking this idea seriously.
I haven’t decided whether the idea is good or bad yet—I haven’t yet evaluated it properly.
But as far as I can tell, your objection to it is incorrect. A naive search program would have very low optimisation power by Eliezer’s criteria—is there a flaw in my argument?
Essentially I agree that that particular objection is largely ineffectual. It is possible to build resource constraints into the environment if you like—though usually resource constraints are at least partly to do with the agent.
Resource constraints need to be specified somewhere. Otherwise exhaustive search (10 mins) gets one score and exhaustive search (10 years) gets another score—and the metric isn’t well defined.
If you see the optimisation score as being attached to a particular system (agent+code+hardware+power available), then there isn’t a problem. It’s only if you want to talk about the optimisation power of an algorithm in a platonic sense, that the definition fails.
Upvoted because admitting to error is rare and admirable, even on Less Wrong :-)
Related to Legg’s work: Ben Goertzel’s paper “Toward a Formal Characterization of Real-World General Intelligence ”
Abstract:
I would love to see a more rigorous way to measure optimization power. It’s a very important concept, and in fact we probably care more about optimization power than intelligence. On some days I’d rather talk about the possibility of an “optimization power explosion” than an “intelligence explosion.”
I don’t think a formalization has been made. I think Carl once suggested we might define optimization power in terms of capacity to achieve narrow goals across a canonical set of environments, but that’s a long way from a formalization.
Wouldn’t AI effectiveness be different from optimization power? I mean, if a solution is ten thousand times harder to find, and only a tiny bit better, that just means the universe doesn’t allow much optimization in that direction. I think noticing that is a feature of the “optimization power” criteria, not a bug.
That’s exactly it. Just specifying the problem to be solved specifies the relationship between the value of a solution, and its percentile ranking, although you may not know this relationship without fully solving the problem. If all solutions have value between 0 and 1 (e.g. you’re trying to maximize your chances of succeeding at something) and half of all solutions have value at least 0.99 (so that it takes 1 bit of optimization power to get one of these) then an extra 100 bits of optimization power won’t do much. It’s not that the AI you ask to solve the problem isn’t good enough. It’s that the problem is inherently easy to find approximately optimal solutions to.
Measuring based on bits doesn’t seem to capture what we care about.
Consider the following two functions: F(x,y) = x+y and G(x,y) = the value of boolean expression x with the variables given truth-assignment y. In each case, I am given some value x and z and want to pick a y so that F(x,y) =z or G(x,y) = z.
Doing this for F is trivial, and for G is not known to be tractable. An AI able to efficiently solve SAT is much more powerful than being able to do subtraction. But you can arrange to have the same chance of succeeding by random chance in each case.
A definition that says that gnu “bc” is as powerful as an oracle for all problems in NP is not a very useful definition.
Moral: Knowing the chance to succeed “by chance” doesn’t tell you much about how sophisticated an algorithm is.
I think this paper will be of interest. It’s a formal definition of universal intelligence/optimization power. Essentially you ask how well the agent does on average in an environment specified by a random program, where all rewards are specified by the environment program and observed by the agent. Unfortunately it’s uncomputable and requires a prior over environments.
My intuition about measuring optimisation power has been: put a bunch of optimisers in a room and see which one is left at the end. (Or if you prefer, which goal state the room is in at the end).
For this definition to make sense there has to be the hypothesis that the ranking system is robust—for agents with a similar rank it’s uncertain which will win, but if the ranks are vastly different then the larger number pretty much always wins.
I’m not certain whether this definition is useful if it’s single-agent environments that you’re interested in, however.
One problem is that with UFAI, we are not interested (I assume) in optimization power with respect to a goal other than UFAI’s own (UFAI doesn’t optimize human value very well). Since rigorous elicitation of agent’s own goal is one of the great unsolved problems in FAI theory, a definition of optimization power might be somewhat FAI-theory-complete...
I would suggest GAI-theory-complete rather than FAI-theory-complete. FAI requires several additional considerations that go beyond that required for analysis of or implementation of an optimization algorithm with a goal system.
Could you evaluate against all possible goals and see which scores the highest in terms of optimization power?
Immediate problems with my suggestion:
It’s not very practical. There are a lot of possible functions to consider.
It would tend to lead to the conclusion that everyone’s goal is to ensure the laws of physics are being followed, and that they’re succeeding perfectly.
That’s an interesting article. We could contrast “powerful optimizers” and “asteroid strikes” or other natural disasters this way: an asteroid strike is dangerous because it could greatly increase entropy on earth. A powerful optimizer is very dangerous because it could greatly decrease it.
An optimizer could be trying to maximize entropy on Earth.
No it can’t. Entropy is not an absolute property.
ETA: I’m not as sure as I was when I said this last week. I was thinking of entropy as a relationship. But now I’m finding it hard to figure out exactly what the relationship is between.
I think you could be very good at creating entropy without being very smart.
I thought how good the solution is is dependent on the utility function, not the optimisation process.
The objective function that measures the value of the solution should be a part of the problem: it’s part of figuring out what counts as a solution in the first place. Maybe in some cases the solution is binary: if you’re solving an equation, you either get a root or you don’t.
In some cases, the value of solution is complicated to assess: how do you trade off a cure for cancer that fails in 10% of all cases, versus a cure for cancer that gives the patient a permanent headache? But either way you need an objective function to tell the AI (or the human) what a “cure for cancer” is; possibly your intuitive understanding of this is incomplete, but that’s another problem.
Edit: Your objection does have some merit, though, because you could have two different utility functions that yield the same optimization problem. For instance, you could be playing the stock market to optimize $$ or log($$), and the ranking of solutions would be the same (although expected values would be thrown off, but that’s another issue); however, the concept of a solution that’s “a tiny bit better” is different.
Only pure solutions—they would rank lotteries differently.