LESSWRONG
LW

Comment Permalink

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.

See in context

13 How to measure optimisation power

by Stuart_Armstrong

25th May 2012

1 min read

13

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 log₂(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.

Personal Blog

13

New Comment

30 comments, sorted by

top scoring

Click to highlight new comments since: Today at 7:39 PM

[-]timtyler13y50

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.

[-]gwern13y20

I discussed a third group's attempt: http://lesswrong.com/lw/42t/aixistyle_iq_tests/

[-]Stuart_Armstrong13y10

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.

[-]timtyler13y10

Can you make sense of Shane Legg's objection, then?

One of my criticisms was this:

If you attempt to quantify the "power" of an optimisation process - without any attempt to factor in the number of evaluations required, the time taken, or the resources used - the "best" algorithm is usually an exhaustive search.

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:

You can quantify this, at least in theory, supposing you have (A) the agent or optimization process's preference ordering, and (B) a measure of the space of outcomes - which, for discrete outcomes in a finite space of possibilities, could just consist of counting them - then you can quantify how small a target is being hit, within how large a greater region.

No "limited resources", just "preference ordering".

[-]Stuart_Armstrong13y10

Can you make sense of Shane Legg's objection, then?

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.

I think your objection shows that you failed to read (or appreciate) this bit:

You can quantify this, at least in theory, supposing you have (A) the agent or optimization process's preference ordering, and (B) a measure of the space of outcomes - which, for discrete outcomes in a finite space of possibilities, could just consist of counting them - then you can quantify how small a target is being hit, within how large a greater region.

His very next paragraph is:

Then we count the total number of states with equal or greater rank in the preference ordering to the outcome achieved, or integrate over the measure of states with equal or greater rank. Dividing this by the total size of the space gives you the relative smallness of the target - did you hit an outcome that was one in a million? One in a trillion?

"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.

[-]timtyler13y10

Then we count the total number of states with equal or greater rank in the preference ordering to the outcome achieved, or integrate over the measure of states with equal or greater rank. Dividing this by the total size of the space gives you the relative smallness of the target - did you hit an outcome that was one in a million? One in a trillion?

"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.

[-]Stuart_Armstrong13y00

"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.

[-]timtyler13y00

"An optimisation of zero" ?!?

[-]Stuart_Armstrong13y00

Are you objecting to the phrasing or to the point?

[-]timtyler13y00

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.

[-]Stuart_Armstrong13y30

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?

[-]timtyler13y30

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.

[-]Stuart_Armstrong13y50

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.

Essentially I agree that that particular objection is largely ineffectual.

Upvoted because admitting to error is rare and admirable, even on Less Wrong :-)

[-]PECOS-913y00

Related to Legg's work: Ben Goertzel's paper "Toward a Formal Characterization of Real-World General Intelligence "

Abstract:

Two new formal definitions of intelligence are presented, the ”pragmatic general intelligence” and ”efficient pragmatic general intelligence.” Largely inspired by Legg and Hutter’s formal definition of ”universal intelligence,” the goal of these definitions is to capture a notion of general intelligence that more closely models that possessed by humans and practical AI systems, which combine an element of universality with a certain degree of specialization to particular environments and goals. Pragmatic general intelligence measures the capability of an agent to achieve goals in environments, relative to prior distributions over goal and environment space. Efficient pragmatic general intelligences measures this same capability, but normalized by the amount of computational resources utilized in the course of the goal-achievement. A methodology is described for estimating these theoretical quantities based on observations of a real biological or artificial system operating in a real environment. Finally, a measure of the ”degree of generality” of an intelligent system is presented, allowing a rigorous distinction between ”general AI” and ”narrow AI.”

[-]lukeprog13y50

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.

[-]khafra13y40

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.

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.

[-]Kindly13y40

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.

[-]asr13y30

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.

[-]jacobt13y20

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.

[-]Giles13y10

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).

I'm not certain whether this definition is useful if it's single-agent environments that you're interested in, however.

[-]Vladimir_Nesov13y10

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...

[-]wedrifid13y10

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.

[-]Giles13y-20

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.

[-][anonymous]13y00

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.

[-]Giles13y00

An optimizer could be trying to maximize entropy on Earth.

[-]amcknight13y00

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.

[-][anonymous]13y00

I think you could be very good at creating entropy without being very smart.

[-]bramflakes13y00

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.

I thought how good the solution is is dependent on the utility function, not the optimisation process.

[-]Kindly13y30

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.

[-]Stuart_Armstrong13y00

the ranking of solutions would be the same

Only pure solutions - they would rank lotteries differently.

Moderation Log