RE: [agi] A probabilistic/algorithmic puzzle...

[Ben Goertzel]

 

OK... I can see that I formulated the problem too formally for a lot of people

 

I will now rephrase it in the context of a specific "test problem." 

 

This test problem was invented by Shane Legg in 2000, when he worked at Webmind Inc.

 

It is of no intrinsic interest, but it presents the mathematical puzzle in a simple visual context.

 

I'll describe the test problem in a 2D context, but it could be recast in n dimensions just as well.

 

First I'll define the basic players in the test problem.

 

Consider the unit square in the plane, i.e. a square of area 1.

 

Consider n rectangles inside the unit square.  Call these rectangles X_1, X_2,..., X_n

 

Now, we may define some probabilities:

 

P(X_i) = the area of the rectangle X_i

 

P(X_i | X_j) = (the area of the intersection between the rectangle X_i and the rectangle X_j) / (the area of the rectangle X_j)

 

Of course, if one knows the rectangles (the coordinates of their corners, say) then one can compute all these probabilities.

 

Conceptually, if you like, you can think of the set of rectangles as a Venn diagram, so that the points in the unit square are things in the world, and each X_i represents some concept (defined extensionally as a set of things)

 

Now the test problem is as follows.

 

1) Choose a large number of points in the unit square

2) Based on these points, evaluate *some of* the probabilities P(X_i) and P(X_i|X_j)

3) Provide an AI system with no information other than the probabilities evaluated in step 2

4) Ask the AI system to evaluate the rest of the probabilities P(X_i) and P(X_i | X_j)

 

 

I don't know if this "test problem" will clarify things or confuse them ;-)

 

This is an actual test problem we've used to tweak parameters of Novamente's first-order inference module (which embodies one solution to the problem)...

 

 

-- Ben

 

 

 

 

-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Jonathan Standley
Sent: Thursday, February 20, 2003 4:25 AM
To: [EMAIL PROTECTED]
Subject: Re: [agi] A probabilistic/algorithmic puzzle...

a challenge! cool :)  but let me try to put it in less-math terms for myself and others who are not math-types

 

>Let X_i, i=1,...,n, denote a set of discrete random variables

 

X_i is the set of all integers between i and n, initial value for i is 1?

or is i any member of the set X?

or does i function only as a lower bound to set X?

 

 

> Let's say we have a set of N << n^2 conditional probability relationships of
> the form

set N consists of relationships numbering n^2, n is the upper boundary of the set X? 
> P(X_j|X_i)

what does this notation "|" mean ?

does P(X_j|X_i) mean the probability of subset occuring within the set X,   X is bounded by [i,n]?

 

 > where i, j are drawn from {1,...,n}.

does X_i represent the whole set and j is a subset or set X_i?

or is i the lower bound of set X and j is an arbitrary member of set X?

> Let's say we also have a set of M <= n probabilities
 

is this a different n than the upper bound of set x?

> P(X_i)

M = P(X_i)?

if so, it means that M is the chance of set X existing within a larger 'parent' set (ie the novamente system)?

 

> The problem is:
>
> * Infer the rest of the P(X_i|X_j) and P(X_i): the ones that aren't given
>
> * Specifically, infer cases where P(X_i|X_j) differs significantly from
> P(X_i)

 

Is the above asking?  given a set X bounded upper = n, lower = i, and given j, an arbitrary subset of set X in X's  initial state, use the available data to approximate the probability of a hypothetical integer set ( a new value for j) apperaing within X in a future state.  specifically, try to find initial conditions which will lead to a large difference between the chances of X existing and the chances of X that contains j existing at a future state. all of this is assuming that Set X is being acted upon by a specified algorithm or process?
>
> Clearly this is a massively "underdetermined" problem: the given data will
> generally not be enough to uniquely determine the results.  This is what
> makes it interesting!
>
> As I said, we have two solutions for this, one implemented the other just
> designed; so we know the problem is approximately and heuristically solvable
> in a plausible computational timeframe.  But I wonder if there aren't
> radically different solutions from the ones we've come up with...

would you mind trying to put the problem in 'word problem' form?  I do much better with concepts than equations ;)

 

If it;s not worth the effort dont bother :)

 

J Standley