Wednesday, September 09, 2009

Challenge: Compute a high dimensional integral, Win a 1,000 Euros.

To give some context, the following is related to the approach developed in The information associated with a sample, by Bernard Beauzamy. At issue is the possibility of building probability distributions from data as opposed to matching probabilistic models to data. It is an important problem and for this reason a 1,000 euros prize is offered by the SCM company to compute a high dimensional integral in an efficient manner. As of today, this translates into a US$1,400 or 9,889 Yuans any other local currency. The text of the challenge is as follows:

September 1st, 2009

The document "Robust Mathematical Methods for Extremely Rare Events" dated August 2009, by Bernard Beauzamy, uses the computation of a multiple integral, over a complicated domain in a many-dimensional space, in order to estimate a probability. This approach is inherent to the method itself.
However, the computation of the integral is done in a way which might not be the best : the function to integrate is a polynomial in one variable (with degree higher than 100 in our case), with rational coefficients (all coefficients are of the form m/n, where m and n are very large integers). In the paper, all coefficients are computed exactly, using the symbolic capabilities of Maple.
Therefore, the integration is slow and requires considerable memory in the computer. Typically, at this point, our method requires 30 multiple integrations, each of which takes around 20 minutes on an ordinary computer.
We would be interested to know if other numerical approaches are possible in order to compute such multiple integrals, with sufficient accuracy.
We offer a prize of Euros 1,000 to the best solution : a solution that can handle the requirements of speed, accuracy, and adaptability (not just our example, but any such example).

Solutions may be provided by individuals or by teams. The solutions should be sent by email to :
scm.sa@orange.fr
no later than March 31st, 2010.

The best solution, besides the prize, will be posted on the "Robust Mathematical Modeling" web site and will be communicated to all participants to the RMM program, worldwide.

If you have any questions, let me know and I'll forward them to the SCM folks.

8 comments:

Kevembuangga said...

LOL
Some kind of poor man's Netflix prize?
I doubt it will draw much interest and anyway if someone happens to solve it it's likely worth much much more than 1000 euros.

Igor said...

Hi Jean-Luc,

What makes you think it is worth more ?

Cheers,

Igor.

Kevembuangga said...

This:

At issue is the possibility of building probability distributions from data as opposed to matching probabilistic models to data.

It is a first step toward having the computer create the "concepts" instead of having the researcher pulling them out of his arse^H^H^H^H^H intuition.

It is matter in which I am keen to see some advances:
The common trap in which all AI researchers seem to fall is that they are always working on already human-elaborated concepts and whatever "good tricks" they find for processing and "massaging" those concepts more efficiently they are oblivious to the fact that they made up the concepts at start not the computer.

Igor said...

Hello Jean-Luc,

The integral can already be computed (see the maple program in one of the document), what is sought is a way to do this more efficiently.

I was not referring to AI as an example of application but it could certainly eventually go there in the future. Currently, these types of methods are used to provide engineers a way to judge how new experimental data assist in the understanding of a specific processes, failure rates, ... It tries to provide some statistical outlook on a data driven process without the intervention of a simple or complex model.

P.S.: You are making a somewhat good point but please be considerate of my readership and not use an overly vulgar vocabulary. Thanks in advance.

Cheers,

Igor.

Kevembuangga said...

(see the maple program in one of the document)

May be in the document which link is broken?
http://pagesperso-orange.fr/scmsa/RMM/SCM_prize_2009_09_01.pdf
Because I didn't see any Maple program in the other two. :-)

Kevembuangga said...

It is in page 9 of this document

Huh?
Page 9?
This is a single HTML page with no reference to any other multipage document whatsoever (and seemingly unrelated to SCM except for the reference to linear operators).
Are you sure you didn't mix up some copy/paste with your latest post?

Kevembuangga said...

Ok, I found it on "page 9", it was so tiny that I missed it on cursory reading.
Thanks!

Igor said...

oopsie, you're right:

http://pagesperso-orange.fr/scmsa/BB_rare_events_2009_08.pdf

I'll remove the offending comment to not confuse the readers.

Cheers,

Igor.

Printfriendly