Please implement the Nelder-Mead Simplex Direct Search Method in Foldit

Case number:845813-2009377
Topic:Game: Tools
Opened by:jeff101
Status:Open
Type:Suggestion
Opened on:Sunday, April 5, 2020 - 21:14
Last modified:Monday, April 6, 2020 - 01:50

Would someone please implement in Foldit, as either a LUA Recipe or a built-in LUA command, 
an optimization algorithm like the Nelder-Mead Simplex Direct Search Method (implemented in 
Matlab as the fminsearch command and in "Numerical Recipes in C" as the amoeba recipe)? 
fminsearch can find the minimum of a function f of multiple variables even when the 
derivatives of f with respect to these variables are unknown. While fminsearch is not 
guaranteed to give the global minimum of f, I have seen fminsearch give good solutions when 
optimizing up to about 20 variables.

For more information, please see:
https://www.mathworks.com/help/matlab/ref/fminsearch.html
https://www.mathworks.com/help/matlab/math/optimizing-nonlinear-functions.html#bsgpq6p-11
https://www.grad.hr/nastava/gs/prg/NumericalRecipesinC.pdf sections 10.0 & 10.4.

The pdf above is "Numerical Recipes in C: The Art of Scientific Computing"
Second Edition by William H Press, Saul A Teukolsky, William T Vetterling, 
and Brian P Flannery, Cambridge University Press, ISBN=0-521-43108-5.
It seems to be the 1992 version but reprinted with corrections in 2002.
Sections 10.0 & 10.4 are pp.394-397 & 408-412 in the text
but pp.418-421 & 432-436 in the pdf.
(Sun, 04/05/2020 - 21:14  |  2 comments)


jeff101's picture
User offline. Last seen 13 hours 26 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
Below is one way we might use fminsearch in Foldit:

Many Recipes run the same set of steps repeatedly.
Let each repeat of these steps be called a loop.
Let t be the # of loops done so far, so t=0,1,2,3,etc.
Let y be the score at the end of loop t.

Suppose y(t) roughly equals z(t)=A-B*exp(-p*t) with p>0.
This gives y(0) ~ z(0)=A-B and y(infinity) ~ z(infinity)=A,
which means that the score starts near A-B and will 
eventually rise to A, giving a maximum gain of A-(A-B)
or B, where B is a positive value.

If one records all the scores y at each loop # t so far,
one can use fminsearch to find the A, B, and p values
that give z(t)=A-B*exp(-p*t) that agrees best with all
the y(t) values so far. Then, using z(t)=A-B*exp(-p*t),
one can estimate at which loop # t the score y will be 
a particular value. If one defines F to be the fraction
of maximum gain attained by the end of loop t, F would 
be a number from 0 to 1 equal to [z(t)-z(0)]/[z(infinity)-z(0)]
or [A-B*exp(-p*t)-(A-B)]/[A-(A-B)] = [-B*exp(-p*t)+B)]/[B]
or 1-exp(-p*t). This can be rearranged to find the loop # t
at which the Recipe should have gained a fraction F of 
the maximum gain B that it is expected to attain. That is, 
since F=1-exp(-p*t), one gets exp(-p*t)=1-F or -p*t=ln(1-F) 
or t = -ln(1-F)/p.

Basically, by fitting the score y vs loop # t to a simple 
function z using fminsearch, one can estimate the maximum 
gain B that a Recipe will give and how many loop #'s are
needed to gain F*B points, where F is a number from 0 to 1.
jeff101's picture
User offline. Last seen 13 hours 26 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
One way to find a set of A,B,p values that gives z(t) ~ y(t)
for a given list of scores y and loop #'s t is to define the 
function f = sum[(z-y)^2] = sum(z^2 - 2*z*y + y^2) and minimize 
f with respect to A, B, and p. In the above definition, sum 
means to sum over all values of z, y, and t. Also, because f 
is a sum of squares, f will always be >= 0, and the minimum 
of f will also be >= 0.

To minimize f, one could use fminsearch while varying A, B, 
and p. This should work, but a more efficient way is to find
the derivatives of f with respect to A, B, and p, and set 
them all to zero. That is, since z=A-B*exp(-p*t), one has
dz/dA=1, dz/dB= -exp(-p*t), dz/dp=B*t*exp(-p*t),
df/dA = sum[2*(z-y)*(dz/dA)] = sum[2*(z-y)*1],
df/dB = sum[2*(z-y)*(dz/dB)] = sum[2*(z-y)*(-exp(-p*t))], and
df/dp = sum[2*(z-y)*(dz/dp)] = sum[2*(z-y)*B*t*exp(-p*t)].

If one lets x(t)=exp(-p*t), one gets z=A-B*x and the following:
df/dA = sum[2*(z-y)*1] = 2*sum[z-y] = 2*sum[A-B*x-y]
        which equals 0 when A*sum(1)-B*sum(x)=sum(y).
df/dB = sum[2*(z-y)*(-exp(-p*t))] = -2*sum[(z-y)*x]
      = -2*sum[(A-B*x-y)*x] = -2*sum[A*x - B*x^2 - y*x]
        which equals 0 when A*sum(x)-B*sum(x^2)=sum(y*x).
df/dp = sum[2*(z-y)*B*t*exp(-p*t)] = 2*B*sum[(z-y)*t*x]
      = 2*B*sum[(A-B*x-y)*t*x] = 2*B*sum[A*t*x - B*t*x^2 - t*y*x]
        which equals 0 when A*sum(t*x)-B*sum(t*x^2)=sum(t*y*x)
        or more trivially when B=0.
Note that sum(1) above is the # of y values found by loop # t.

The above equations can be written in matrix form as:
|sum(1)   -sum(x)    |    |sum(y)    |
|sum(x)   -sum(x^2)  ||A|=|sum(y*x)  |
|sum(t*x) -sum(t*x^2)||B| |sum(t*y*x)|
which could be solved for A & B using linear algebra, 
but while sum(1) & sum(y) are fixed, sum(x), sum(x^2), 
sum(y*x), sum(t*x), sum(t*x^2), & sum(t*y*x) all depend 
on x(t)=exp(-p*t), which depends on p.

To make progress, one has fminsearch vary only p to find 
the minimum value of f. A and B for any p can be found 
using just the equations for df/dA=0 and df/dB=0:
A*sum(1)-B*sum(x)=sum(y)
A*sum(x)-B*sum(x^2)=sum(y*x)
which in matrix form give:
|sum(1)   -sum(x)    ||A|=|sum(y)    |
|sum(x)   -sum(x^2)  ||B| |sum(y*x)  |
and are solved by 
A=[sum(y*x)*sum(x)-sum(y)*sum(x^2)]/[sum(x)*sum(x)-sum(1)*sum(x^2)]
B=[sum(y*x)*sum(1)-sum(y)*sum(x)] / [sum(x)*sum(x)-sum(1)*sum(x^2)].

Finally, using z=A-B*x, f = sum[(z-y)^2] = sum[(A-B*x-y)^2] gives
f = sum(A^2 + B^2*x^2 + y^2 - 2*A*B*x - 2*A*y + 2*B*x*y)
  =   A^2*sum(1) + B^2*sum(x^2) +     sum(y^2)
  - 2*A*B*sum(x) - 2*A*sum(y)   + 2*B*sum(x*y).
This final equation for f can be evaluated using the sums 
needed to calculate A and B for a given value of p.

If anyone finds typos in the above, please e-mail me about them.

Thanks!
Sitemap

Developed by: UW Center for Game Science, UW Institute for Protein Design, Northeastern University, Vanderbilt University Meiler Lab, UC Davis
Supported by: DARPA, NSF, NIH, HHMI, Amazon, Microsoft, Adobe, RosettaCommons