comparison
AbramDemski
Recently Eric Baum's work caught my attention (as he announced that he
had project funding on the AGI list). Among other things, Eric has
worked on program evolution:
http://whatisthought.com/ptech.pdf
It occurs to me that this algorithm could be tested directly against
Moses, and I've been thinking of tackling such as project.
The idea would be to code his algorithm in Lisp, working with the same
representation language that Plop currently supports. Is there any
more documentation on this than that available in syntax.lisp? (I have
not yet examined the whole codebase.)
Also, any ideas on how fair the comparison could be? Is the current
implementation of Plop complete enough for a good comparison? What
steps could be taken to minimize the differences between the Plop
implementation and my implementation of Eric Baum's algorithm? (Beyond
using the same program representation and implementation language, are
there other factors to consider?) What code can/should be shared
between the two algorithms' implementations?
Thanks for any thoughts,
--Abram
Ben Goertzel
I believe Moshe implemented some variant of Eric's Hayek system, some
time ago... as I recall he got it to work, but it was slow and
difficult to tune...
What makes this sort of comparison hard is that, when you dig into the
details, both MOSES/Plop and Hayek turn out to be moderately broad
"families of algorithms", so that choosing only one alg from each
family for comparisons is very hard and winds up being a research
project in improving/fleshing-out each approach...
It's sorta like the problem of figuring out what string theory
predicts about some physical phenomenon -- "string theory", when you
dig deeper, is a multi-dimensionally-parametrized family of
uncountably infinitely many theories and to get a concrete prediction
out of it you need to make some hard specific decisions ... and
figuring out what decisions to make is much of what string theory
research is aboud...
-- Ben G
Ben Goertzel, PhD
CEO, Novamente LLC and Biomind LLC
Director of Research, SIAI
b...@goertzel.org
"It caused me to see all the moments of the creature's life arranged
in parallel, as if time were another kind of space."
Moshe Looks
> I believe Moshe implemented some variant of Eric's Hayek system, some
> time ago... as I recall he got it to work, but it was slow and
> difficult to tune...
>
I was inspired by
Market-Based Reinforcement Learning in Partially Observable Worlds
Kwee, Hutter, and Schmidhuber
http://arxiv.org/PS_cache/cs/pdf/0105/0105025v1.pdf
which could not reproduce Baum & Durdanovic's results, but changed
some details. I tried to get all the details right, and managed a 2/5
success rate on the blocksworld problem (whereas Baum's own
implementation got 100% success, and Kwee et al.'s was 0%).
> What makes this sort of comparison hard is that, when you dig into the
> details, both MOSES/Plop and Hayek turn out to be moderately broad
> "families of algorithms", so that choosing only one alg from each
> family for comparisons is very hard and winds up being a research
> project in improving/fleshing-out each approach...
>
Right, and additionally also choosing which problems to test on would
be tricky.
One major difference between Hayek and MOSES approaches is that in
Hayek one explicitly learns a collection of rules, whereas in MOSES
one learns individual program trees. So there is a nontrivial language
gap to be overcome. Did you have particular test problems in mind,
Abram? One possibility would be to simply see if MOSES could learn to
solve the Hayek Blocksworld task: I wrote up some notes on how to
present the problem a long time ago at:
http://code.google.com/p/moses/wiki/BlocksWorldProblem
Plop does not have action/perception capabilities, yet, so you would
need to add these. Also, recent plop improvements that I have made
have been done to an internal Google fork of plop for a proprietary
project, so if you do end up undertaking this project, drop me a line
and I will backport these improvements to the open source version... I
plan on doing this at some point anyway, but it is not a priority
unless there is someone outside Google (like you) who wants to do
serious work on the codebase.
> Is there any
> more documentation on this than that available in syntax.lisp? (I have
> not yet examined the whole codebase.)
>
Semantics.lisp and some other files might have more comments, but
these are not up-to-date or complete overall, sorry! On a
non-implementation level, the paper that Ben & I wrote for AGI-09
(http://www.agi-09.org/papers/paper_69.pdf) has some relevant bits..
Cheers,
Moshe
AbramDemski
Hmm, OK. I'll reconsider my easiness estimate for such a project. :)
> Right, and additionally also choosing which problems to test on would
> be tricky.
> One major difference between Hayek and MOSES approaches is that in
> Hayek one explicitly learns a collection of rules, whereas in MOSES
> one learns individual program trees. So there is a nontrivial language
> gap to be overcome.
difference" between the two approaches, ie, not something that needs
to be made the same in order to make a fair comparison... On the other
hand, one could take a more exhaustive approach and test Hayek against
straight Plop (learning a single program tree) but also against a
modified Plop that learns collections.
> Plop does not have action/perception capabilities, yet, so you would
> need to add these.
> Also, recent plop improvements that I have made
> have been done to an internal Google fork of plop for a proprietary
> project, so if you do end up undertaking this project, drop me a line
> and I will backport these improvements to the open source version...
On May 18, 1:33 pm, Moshe Looks <madscie...@google.com> wrote:
> I agree with everything Ben says (well,in this message ;->)
>
> > I believe Moshe implemented some variant of Eric's Hayek system, some
> > time ago... as I recall he got it to work, but it was slow and
> > difficult to tune...
>
> I was inspired by
>
> Market-Based Reinforcement Learning in Partially Observable Worlds
Lukasz Stafiniak
>
> On the other
> hand, one could take a more exhaustive approach and test Hayek against
> straight Plop (learning a single program tree) but also against a
> modified Plop that learns collections.
Abram, I would think you know that a collection of programs is another
program ;-)
Abram Demski
Well, a collection of programs *acting together in a specific way* is
another program... and, Plop could in principle come up with a program
that used the same interaction method... but the question is a bout
bias. Because Hayek *always* learns
collections-combined-in-a-specific-way, it has a different weighting
on the search space. The "more exhaustive" experiment would tell us
whether the success or failure of Hayek was due to this specific bias,
or due to other factors.
--Abram
Abram Demski
http://dragonlogic-ai.blogspot.com/
Moshe Looks
>
various combinations (i.e. symbolic regression). The problem with
applying Hayek to these sorts of problems is that there is no obvious
"world" for the agent's to bid on a accumulate partial credit. So one
could have a collection of bidding agents that solved symbolic
regression (by partitioning in input space based on which rules fire),
but it would not be cooperative in the way that Hayek on blocksworld
is. BTW, there is a huge learning classifier systems (LCS) literature
on stuff like this...
>> Plop does not have action/perception capabilities, yet, so you would
>> need to add these.
>
> How difficult do you think this would be?
>
Not especially difficult to do poorly, difficult to do well. The
problem is that representation-building and distance estimation
between programs would need to be worked out carefully and tuned in
order to obtain decent performance...
- Moshe
P.S. Regarding collections of programs vs. individual programs there
is of course no difference for a language where the individual
programs are turing complete but when they are not (as in Hayek) a
collection can be more expressive (i.e. correspond to a broader
computational class).