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:Sunday, October 4, 2020 - 18:48

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


jeff101's picture
User offline. Last seen 8 hours 12 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 8 hours 12 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!
Joined: 09/24/2012
Groups: Go Science

Would it be usefull for selecting optimimzed combination of sub-scores and bonusses at each step of a puzzle game ? Presently, the binusses are equal alongs the 7 days. However, experience says it's better to give higher weight to bonusses at start game.
I can imagine that there is a kind of optimal bonus and score weights at each time of the game.

If I understoot well, NMSDS could help dynamically changing the score goal at each step of the game ?

Another consideration: several years ago, I made statistics and I calculated a typical (static) fonction of score over time for several puzzle types. I then used the results in order to forecast the possile decreasing gain for JET recipe. This gives some indication in the recipe prints, with a "target" and "distance to target". But appart from this, I didn't use this information for the recipe behaviour. With the time, bonusses and symmetrics made these "forecasts" sometimes completely wrong. I'm wondering if there could be some use of NMSDS, including this "possible score target" information, in order to change the behaviour of recipes considering the "distance to target" (on the fly disturbing or "precise" recipe behaviour, and different subscore weights depending on the stage of the puzzle).

jeff101's picture
User offline. Last seen 8 hours 12 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
Basically, if you can define a function f that depends on several 
variables like a,b,c, the Nelder-Mead method will vary a,b,c to 
find the smallest value of f that it can. The smallest value of f 
that it finds is not guaranteed to be the global minimum of f, 
but you can run it multiple times with different starting values 
of a,b,c to increase the likelihood that it finds the global 
minimum of f.

If you want the maximum value for f, run Nelder-Mead on -f 
instead. If you minimize -f, that is like maximizing +f.
jeff101's picture
User offline. Last seen 8 hours 12 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
Below is one implementation in LUA of the Nelder-Mead 
method: https://gist.github.com/mwgamera/5077246
I have not tried to use it in a Foldit recipe yet.

One application could be to have it vary the strengths
and target lengths for bands in Foldit. Such a recipe 
could have f be the Foldit score times negative 1 
(this would let the minimum of f give the maximum Foldit 
score). The recipe could do a series of cycles. Each 
cycle could set the latest values for the band strengths 
and target lengths and then do a series of steps like 
reset the clashing importance to 0.1, shake the protein, 
wiggle the sidechains, wiggle the backbones, and wiggle 
everything. It could then repeat the shake and wiggle 
steps with clashing importance set to 1 instead. After 
all these steps, it could use the latest Foldit score 
and the Nelder-Mead method to pick the next set of band 
strengths and target lengths. Then it would repeat the 
cycle.  

Such a method could be used in puzzles with proteins
suspected to have disulfide bonds, for example. The 
recipe could start with all possible disulfides banded 
with the same strength and fixed target lengths (length 
2 for bands between sulfur atoms and length 3 for bands 
between sulfur atoms and nearby carbon atoms. See the 
recipes bandsome (https://fold.it/portal/recipe/43861) 
and bandsomeSS (https://fold.it/portal/recipe/101275) 
for more details). If the protein contains 7 cysteines,
for example, there are 21 possible disulfide bonds. 
One could use 3 bands for each of these 21 disulfide 
bonds and have all 3 bands in a particular group have 
the same band strength. This would give 63 bands with 
21 different band strengths for the Nelder-Mead method 
to adjust. Perhaps such a recipe could determine which 
3 of the 21 possible disulfide bonds work best for the 
protein. It might even determine that having 0, 1, or 
2 disulfide bonds would give a better score than having
3 disulfide bonds.

Similar recipes could also be made for Contact Map 
Puzzles. In such puzzles, picking which atoms to band 
and what band strengths and target lengths to use were 
big issues.
jeff101's picture
User offline. Last seen 8 hours 12 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
Most of my experience with the Nelder-Mead method has 
been with functions f of up to about 20 variables. For
these functions, a particular set of values for the
variables always gave the same value for f. That is,
if f depended on x,y,z, using x,y,z=3,4,5 would always
give the same value, say 20, for f while using 
x,y,z=5,7,9 would always give its own value, say 23,
for f. I don't know how Nelder-Mead would behave if 
the same set of variables could give a different value 
for f each time it was used. How would it behave if
for one try x,y,z=3,4,5 gave f=20 while for later 
tries x,y,z=3,4,5 gave f=23 then 22 then 17 then 25?
Such results might occur within Foldit, depending on
what one chooses to vary.

Usually within the Nelder-Mead method, a simplex is
stored and then updated multiple times. The simplex
consists of several vertices, where each vertex has
certain values for x,y,z and f. Usually the range
for each variable, like x, gradually shrinks with
each update of the simplex, eventually converging
to one combination of values for x,y,z with one
value for f. I once read a book that focused on
industrial applications of the Nelder-Mead method,
and it seemed like it gave good results, even on
real-world problems where f had built-in noise,
meaning doing multiple tests with the same values
for x,y,z would give multiple values for f. It 
seems likely that Foldit recipes using the 
Nelder-Mead method would have noisy f.
jeff101's picture
User offline. Last seen 8 hours 12 min ago. Offline
Joined: 04/20/2012
Groups: Go Science
One issue for band-adjusting Foldit recipes would be what
structure to use at the start of each step. Should you always
start with the best-scoring solution so far and just change 
the strengths of its bands? Should you instead have a bunch
of old solutions stored in quicksaves or *.ir_solution files, 
one for each vertex of the simplex, so that each of these
solutions has the Foldit score corresponding to the value of
f obtained at that vertex of the simplex? It's something to
think about.
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