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.
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!
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).
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.
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.
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.
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.