How to measure optimisation power

post by Stuart_Armstrong · 2012-05-25T11:07:47.275Z · score: 8 (11 votes) · LW · GW · Legacy · 30 comments

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.

30 comments

Comments sorted by top scores.

comment by timtyler · 2012-05-25T20:38:42.742Z · score: 4 (4 votes) · LW(p) · GW(p)

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.

comment by gwern · 2012-05-25T22:28:55.099Z · score: 2 (2 votes) · LW(p) · GW(p)

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

comment by Stuart_Armstrong · 2012-05-28T14:26:57.915Z · score: 1 (1 votes) · LW(p) · GW(p)

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.

comment by timtyler · 2012-05-28T16:39:53.229Z · score: 1 (1 votes) · LW(p) · GW(p)

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

comment by Stuart_Armstrong · 2012-05-28T20:54:47.192Z · score: 1 (1 votes) · LW(p) · GW(p)

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.

comment by timtyler · 2012-05-29T10:11:36.948Z · score: 1 (1 votes) · LW(p) · GW(p)

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.

comment by Stuart_Armstrong · 2012-05-29T10:23:25.930Z · score: 0 (0 votes) · LW(p) · GW(p)

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

comment by timtyler · 2012-05-29T23:42:10.212Z · score: 0 (0 votes) · LW(p) · GW(p)

"An optimisation of zero" ?!?

comment by Stuart_Armstrong · 2012-05-30T08:49:28.424Z · score: 0 (0 votes) · LW(p) · GW(p)

Are you objecting to the phrasing or to the point?

comment by timtyler · 2012-05-30T09:48:04.925Z · score: 0 (0 votes) · LW(p) · GW(p)

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.

comment by Stuart_Armstrong · 2012-05-30T17:00:51.588Z · score: 2 (2 votes) · LW(p) · GW(p)

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?

comment by timtyler · 2012-05-30T23:10:49.234Z · score: 2 (2 votes) · LW(p) · GW(p)

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.

comment by Stuart_Armstrong · 2012-05-31T08:31:42.569Z · score: 3 (3 votes) · LW(p) · GW(p)

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

comment by PECOS-9 · 2012-05-28T21:20:14.715Z · score: 0 (0 votes) · LW(p) · GW(p)

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

comment by lukeprog · 2012-05-25T18:02:22.913Z · score: 4 (4 votes) · LW(p) · GW(p)

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.

comment by khafra · 2012-05-25T12:47:24.231Z · score: 3 (3 votes) · LW(p) · GW(p)

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.

comment by Kindly · 2012-05-25T18:17:00.065Z · score: 2 (2 votes) · LW(p) · GW(p)

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.

comment by asr · 2012-05-28T20:15:33.751Z · score: 2 (2 votes) · LW(p) · GW(p)

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.

comment by jacobt · 2012-05-25T19:09:49.304Z · score: 2 (2 votes) · LW(p) · GW(p)

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.

comment by Giles · 2012-05-26T17:08:25.032Z · score: 1 (1 votes) · LW(p) · GW(p)

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.

comment by Vladimir_Nesov · 2012-05-25T18:28:05.656Z · score: 1 (3 votes) · LW(p) · GW(p)

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

comment by wedrifid · 2012-05-26T06:09:56.160Z · score: 1 (1 votes) · LW(p) · GW(p)

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.

comment by Giles · 2012-05-26T17:15:09.728Z · score: -1 (1 votes) · LW(p) · GW(p)

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.
comment by [deleted] · 2012-05-25T18:26:15.323Z · score: 0 (2 votes) · LW(p) · GW(p)

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.

comment by Giles · 2012-05-26T16:54:39.992Z · score: 0 (0 votes) · LW(p) · GW(p)

An optimizer could be trying to maximize entropy on Earth.

comment by amcknight · 2012-05-28T20:02:58.310Z · score: 0 (0 votes) · LW(p) · GW(p)

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.

comment by [deleted] · 2012-05-26T17:23:44.772Z · score: 0 (0 votes) · LW(p) · GW(p)

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

comment by bramflakes · 2012-05-25T14:25:04.212Z · score: 0 (0 votes) · LW(p) · GW(p)

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.

comment by Kindly · 2012-05-25T18:00:48.155Z · score: 2 (2 votes) · LW(p) · GW(p)

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.

comment by Stuart_Armstrong · 2012-05-28T14:10:54.912Z · score: 0 (0 votes) · LW(p) · GW(p)

the ranking of solutions would be the same

Only pure solutions - they would rank lotteries differently.