[Rd] application to mentor syrfr package development for Google Summer of Code 2010

[James Salsman]

Michael,

Thanks for your reply:

On Mon, Mar 8, 2010 at 12:41 AM, Michael Schmidt <mds47 at cornell.edu> wrote:
>
> Thanks for contacting me. Eureqa takes into account the total size of an
> equation when comparing different candidate models. It attempts to find the
> set of possible equations that are non-dominated in both error and size. The
> final results is a short list consisting of the most accurate equation for
> increasing equation sizes.
>
> This is closely related to degrees of freedom, but not exactly the same

That's very good, but I wonder whether we can perform automatic
outlier exclusion that way.  We would need to keep the confidence
interval, or at least the information necessary to derive it, accurate
in every step of the genetic beam search.  Since the confidence
intervals of extrapolation depend so heavily on the number of degrees
of freedom of the fit (along with the residual standard error) it's a
good idea to use a degree-of-freedom-adjusted F statistic instead of a
post-hoc combination of equation size and residual standard error, I
would think.  You might want to try it and see how it improves things.
 Confidence intervals, by representing the goodness of fit in the
original units and domain of the dependent variable, are tremendously
useful and sometimes make many kinds of tests which would otherwise be
very laborious easy to eyeball.

Being able to fit curves to one-to-many relations instead of strict
one-to-one functions appeals to those working in the imaging domain,
but not to as many traditional non-image statisticians. Regressing
functions usually results in well-defined confidence intervals, but
regressing general relations with derivatives produces confidence
intervals which can also be relations.  Trying to figure out a
spiral-shaped confidence interval probably appeals to astronomers more
than most people.  So I am proposing that, for R's contemplated
'syrfr' symbolic regression package, we do functions in a general
genetic beam search framework, Chillu and John Nash can do derivatives
in the new 'adinr' package, and then we can try to put them together,
extend the syrfr package with a parameter indicating to fit relations
with derivatives instead of functions, to try to replicate your work
on Eureqa using d.o.f-adjusted F statistics as a heuristic beam search
evaluation function.

Have you quantified the extent to which using the crossover rule in
the equation tree search is an improvement over mutation alone in
symbolic regression?  I am glad that Chillu and Dirk have already
supported that; there is no denying its utility.

Would you like to co-mentor this project?
http://rwiki.sciviews.org/doku.php?id=developers:projects:gsoc2010:syrfr
I've already stepped forward, so you could do as much or as little as
you like if you wanted to co-mentor and Dirk agreed to that
arrangement.

Best regards,
James Salsman


> On Mon, Mar 8, 2010 at 2:49 AM, James Salsman <jsalsman at talknicer.com>
> wrote:
>>
>> I meant that development on both a syrfr R package capable of
>> using either F statistics or parametric derivatives should proceed in
>> parallel with your work on such a derivatives package. You are right
>> that genetic algorithm search (and general best-first search --
>> http://en.wikipedia.org/wiki/Best-first_search -- of which genetic
>> algorithms are various special cases) can be very effectively
>> parallelized, too.
>>
>> In any case, thank you for pointing out Eureqa --
>> http://ccsl.mae.cornell.edu/eureqa -- but I can see no evidence there
>> or in the user manual or user forums that Eureqa is considering
>> degrees of freedom in its goodness-of-fit estimation.  That is a
>> serious problem which will typically result in invalid symbolic
>> regression.  I am sending this message also to Michael Schmidt so that
>> he might be able to comment on the extent to which Eureqa adjusts for
>> degrees of freedom in his fit evaluations.
>>
>> Best regards,
>> James Salsman
>>
>> On Sun, Mar 7, 2010 at 10:39 PM, Chidambaram Annamalai
>> <quantumelixir at gmail.com> wrote:
>> >
>> >> If I understand your concern, you want to lay the foundation for
>> >> derivatives so that you can implement the search strategies described
>> >> in Schmidt and Lipson (2010) --
>> >> http://www.springerlink.com/content/l79v2183725413w0/ -- is that
>> >> right?
>> >
>> > Yes. Basically traditional "naive" error estimators or fitness functions
>> > fail miserably when used in SR with implicit equations because they
>> > immediately close in on "best" fits like f(x) = x - x and other trivial
>> > solutions. In such cases no amount of regularization and complexity
>> > penalizing methods will help since x - x is fairly simple by most
>> > measures
>> > of complexity and it does have zero error. So the paper outlines such
>> > problems associated with "direct" error estimators and thus they infer
>> > the
>> > "triviality" of the fit by probing its estimates around nearby points
>> > and
>> > seeing if it does follow the pattern dictated by the data points -- ergo
>> > derivatives.
>> >
>> > Also, somewhat like a side benefit, this method also enables us to
>> > perform
>> > regression on closed loops and other implicit equations since the
>> > fitness
>> > functions are based only on derivatives. The specific form of the error
>> > is
>> > equation 1.2 which is what, I believe, comprises of the internals of the
>> > evaluation procedure used in Eureqa.
>> >
>> > You are correct in pointing out that there is no reason to not work in
>> > parallel, since GAs generally have a more or less fixed form
>> > (evaluate-reproduce cycle) which is quite easily parallelized. I have
>> > used
>> > OpenMP in the past, in which it is fairly trivial to parallelize well
>> > formed
>> > for loops.
>> >
>> > Chillu
>> >
>> >> It is not clear to me how well this generalized approach will
>> >> work in practice, but there is no reason not to proceed in parallel to
>> >> establish a framework under which you could implement the metrics
>> >> proposed by Schmidt and Lipson in the contemplated syrfr package.
>> >>
>> >> I have expanded the test I proposed with two more questions -- at
>> >>
>> >> http://rwiki.sciviews.org/doku.php?id=developers:projects:gsoc2010:syrfr
>> >> -- specifically:
>> >>
>> >> 5. Critique http://sites.google.com/site/gptips4matlab/
>> >>
>> >> 6. Use anova to compare the goodness-of-fit of a SSfpl nls fit with a
>> >> linear model of your choice. How can your characterize the
>> >> degree-of-freedom-adjusted goodness of fit of nonlinear models?
>> >>
>> >> I believe pairwise anova.nls is the optimal comparison for nonlinear
>> >> models, but there are several good choices for approximations,
>> >> including the residual standard error, which I believe can be adjusted
>> >> for degrees of freedom, as can the F statistic which TableCurve uses;
>> >> see: http://en.wikipedia.org/wiki/F-test#Regression_problems
>> >>
>> >> Best regards,
>> >> James Salsman