CLOP for Noisy Black-Box Parameter Optimization

[ernest]

Hi Rémi,

Since I see you are active here now, would you care to give your opinion in the discussion I initiated on Elo rating in
http://www.talkchess.com/forum/viewtopi ... 196#422196

Merci,

Ernest

[Don]

Comments and questions are welcome.

Rémi

Larry and I are playing around with CLOP using clop-gui.

In the Max tab, there appears the columns Mean, Max-1, Max-2 and apparently as many columns as there are numbers of parameters to be tuned.

However nothing ever appears in those columns after a day of running. What do those columns mean (no pun.)

In the paper you mention that this is supposed to converge - so given enough games and time will this eventually stop running? I told Larry that even with a very efficient algorithm it is likely to take millions of games to see values that improve on already well selected values.

And which values are taken to be the final values to use? Are the Max-n columns supposed to represent superior parameters?

Addendum: We tried only tuning a couple of parameters and values start to appear in the Max-1 column after a few minutes. But we don't really know what they mean.

Thanks.

[Rémi Coulom]

Comments and questions are welcome.

Rémi

Larry and I are playing around with CLOP using clop-gui.

In the Max tab, there appears the columns Mean, Max-1, Max-2 and apparently as many columns as there are numbers of parameters to be tuned.

However nothing ever appears in those columns after a day of running. What do those columns mean (no pun.)

I explained earlier in this thread: it is a feature I did not implement. Only max-1 has a meaning: it is the maximum of the quadratic regression, if it exists. It sometimes does not exist. Mean is the weighted mean of all samples. I recommend using parameter values in the "Mean" column for your parameters. They usually perform better according to my artificial experiments.

In the paper you mention that this is supposed to converge - so given enough games and time will this eventually stop running? I told Larry that even with a very efficient algorithm it is likely to take millions of games to see values that improve on already well selected values.

It does not converge in a finite amount of games. It converges in the sense that expected simple regret decreases in time, and can be made arbitrarily small with a big enough number of games. Note that I do not have a mathematical proof of this convergence, but I am convinced it does converge if the function to be optimized is continuous.

In the paper I ran experiments on artificial problems. It gives an idea of how close to optimal parameters you get with a given number of games. Around 50% winning rate, one Elo point is about 0.0014. For the Log problem in one dimension, it takes about 10k games to have 0.001 expected simple regret (so, less than one Elo point). For the 5-dimensional problem, it takes a few hundred thousand games to reach 1-Elo expected simple regret (that's 0.2 Elo per parameter).

The magic of CLOP is that it approaches optimal performance faster than it can be measured. Simple regret is smaller than the confidence interval around the estimated win rate.

Rémi

[Don]

Comments and questions are welcome.

Rémi

Larry and I are playing around with CLOP using clop-gui.

In the Max tab, there appears the columns Mean, Max-1, Max-2 and apparently as many columns as there are numbers of parameters to be tuned.

However nothing ever appears in those columns after a day of running. What do those columns mean (no pun.)

I explained earlier in this thread: it is a feature I did not implement. Only max-1 has a meaning: it is the maximum of the quadratic regression, if it exists. It sometimes does not exist. Mean is the weighted mean of all samples. I recommend using parameter values in the "Mean" column for your parameters. They usually perform better according to my artificial experiments.

In the paper you mention that this is supposed to converge - so given enough games and time will this eventually stop running? I told Larry that even with a very efficient algorithm it is likely to take millions of games to see values that improve on already well selected values.

It does not converge in a finite amount of games. It converges in the sense that expected simple regret decreases in time, and can be made arbitrarily small with a big enough number of games. Note that I do not have a mathematical proof of this convergence, but I am convinced it does converge if the function to be optimized is continuous.

In the paper I ran experiments on artificial problems. It gives an idea of how close to optimal parameters you get with a given number of games. Around 50% winning rate, one Elo point is about 0.0014. For the Log problem in one dimension, it takes about 10k games to have 0.001 expected simple regret (so, less than one Elo point). For the 5-dimensional problem, it takes a few hundred thousand games to reach 1-Elo expected simple regret (that's 0.2 Elo per parameter).

The magic of CLOP is that it approaches optimal performance faster than it can be measured. Simple regret is smaller than the confidence interval around the estimated win rate.

Rémi

Thanks for explaining that Rémi. I have a script for chess if anyone wants to use it for chess. The script does not have a legal move generator for simplicity and therefore draw and win detection is a bit of a kludge, but it works well.

[Rémi Coulom]

Thanks for explaining that Rémi. I have a script for chess if anyone wants to use it for chess. The script does not have a legal move generator for simplicity and therefore draw and win detection is a bit of a kludge, but it works well.

I can put a link on the CLOP web site, or host it there.

Rémi

[F. Bluemers]

Comments and questions are welcome.

Rémi

Larry and I are playing around with CLOP using clop-gui.

In the Max tab, there appears the columns Mean, Max-1, Max-2 and apparently as many columns as there are numbers of parameters to be tuned.

However nothing ever appears in those columns after a day of running. What do those columns mean (no pun.)

I explained earlier in this thread: it is a feature I did not implement. Only max-1 has a meaning: it is the maximum of the quadratic regression, if it exists. It sometimes does not exist. Mean is the weighted mean of all samples. I recommend using parameter values in the "Mean" column for your parameters. They usually perform better according to my artificial experiments.

In the paper you mention that this is supposed to converge - so given enough games and time will this eventually stop running? I told Larry that even with a very efficient algorithm it is likely to take millions of games to see values that improve on already well selected values.

It does not converge in a finite amount of games. It converges in the sense that expected simple regret decreases in time, and can be made arbitrarily small with a big enough number of games. Note that I do not have a mathematical proof of this convergence, but I am convinced it does converge if the function to be optimized is continuous.

In the paper I ran experiments on artificial problems. It gives an idea of how close to optimal parameters you get with a given number of games. Around 50% winning rate, one Elo point is about 0.0014. For the Log problem in one dimension, it takes about 10k games to have 0.001 expected simple regret (so, less than one Elo point). For the 5-dimensional problem, it takes a few hundred thousand games to reach 1-Elo expected simple regret (that's 0.2 Elo per parameter).

The magic of CLOP is that it approaches optimal performance faster than it can be measured. Simple regret is smaller than the confidence interval around the estimated win rate.

Rémi

Thanks for explaining that Rémi. I have a script for chess if anyone wants to use it for chess. The script does not have a legal move generator for simplicity and therefore draw and win detection is a bit of a kludge, but it works well.

I wrote one that calls xboard to run the game
I redirect the output to a file and parse it like this to get the outcome:

Code: Select all

for line in open("herr"):
    parts = line.split(' ')
    # print len(parts)
    x = 0
    while x+1<len&#40;parts&#41; &#58;
    	if parts&#91;x&#93; == 'score' &#58;
           parts&#91;x+1&#93;=parts&#91;x+1&#93;.strip&#40;)
           if parts&#91;x+1&#93; == '0-0-1' &#58;
               print 'D'
           if parts&#91;x+1&#93; == '0-1-0' &#58; 
               print 'L'
           if parts&#91;x+1&#93; == '1-0-0' &#58;
               print 'W'
        x=x+1

My first hack in python ,so I bet it can be done a lot better,I parse
all lines,if xboard is invoked with -debug it contains more lines (last one holding result,but i wanted to keep the code simple)

[Rémi Coulom]

I added the script of Don, as well as a data file demonstrating the application of CLOP to piece values in Chess, contributed by Gian-Carlo Pascutto:
http://remi.coulom.free.fr/CLOP/

Thanks to both.

Rémi

[Rémi Coulom]

Hi,

Don just wrote this to me:

Remi,

Sorry to bug you, but there is an error in the script. Also, I found that it does not run on most unix systems due to an outdated tclsh on most systems. I use 1 modern command not in older tcls.

I also included a README file with my email for help.

So if you can update this, it would probably be useful to people.

the web site of CLOP is now updated with the new version.

Rémi

[lkaufman]

I would like to ask for more comments about the "correlations" option. If you are dealing with the evaluation function of a chess program, there are a huge number of terms, and many of them (maybe all) do correlate to some degree with each other. Se clearly the "correct" setting is correlations all. However if you have much more than a dozen or so eval terms, it seems to converge too slowly to be practical. With correlations none, things seem to happen much more quickly with a lot of terms. I have a suspicion that the time it takes to converge with correlations none may only go up in proportion to the number of terms (or maybe the square of it), whereas with correlations all it may be exponential. Do you think this is correct or close to it?
So the other question is: if you have to use correlations none to get convergence in any practical amount of time, how valid are the results if there really are correlations? What exactly are the types of errors you would see?
If you had a hundred or so eval terms in a chess program to optimize, how would you use your own software to best do this?

[Rémi Coulom]

I would like to ask for more comments about the "correlations" option. If you are dealing with the evaluation function of a chess program, there are a huge number of terms, and many of them (maybe all) do correlate to some degree with each other. Se clearly the "correct" setting is correlations all. However if you have much more than a dozen or so eval terms, it seems to converge too slowly to be practical. With correlations none, things seem to happen much more quickly with a lot of terms. I have a suspicion that the time it takes to converge with correlations none may only go up in proportion to the number of terms (or maybe the square of it), whereas with correlations all it may be exponential. Do you think this is correct or close to it?
So the other question is: if you have to use correlations none to get convergence in any practical amount of time, how valid are the results if there really are correlations? What exactly are the types of errors you would see?
If you had a hundred or so eval terms in a chess program to optimize, how would you use your own software to best do this?

In theory, "Correlations all" should always be best in terms of getting a good optimal from the same number of games, but there are at least two problems: first, computing the regression becomes very slow. The number of parameters of the regression for n parameters (of the program) is (n+1)*(n+2)/2. I use Newton's method to do the regression, which has a cost cubic in the number of parameters of the regression, so O(n^6) cost. In practice, this will be too slow when n becomes much larger than a dozen. The second problem is that because the number of parameters increases, there are more risks of over-fitting when the number of games is low. This problem should always go away when the number of games becomes higher.

Both problems are solvable, with a better algorithm (for regression), or stronger regularization (for overfitting) (ie, a stronger prior).

In practice "Correlations none" may seem to converge faster, but what it converges to might not be very good. In my low-dimensional experiments, even when there are no correlations at all, "Correlations none" does not perform significantly better than "Correlations all" in terms of simple regret. So "Correlations all" should be always better whith a high enough number of games.

The problem is for a large number of parameters "high enough" might be extremely high. Right now, it does not seem realistic to use "Correlations all" with more than a dozen parameters, as you noticed. But I will try to improve this.

Rémi