Loading ...
Sorry, an error occurred while loading the content.

Re: GECCO Paper on HyperNEAT

Expand Messages
  • Ken
    Thanks to Jeff an JBM for alerting me to even more recent evidence that target-based fitness isn t healthy for indirect encodings. This article is a really
    Message 1 of 14 , Jul 1, 2013
    View Source
    • 0 Attachment
      Thanks to Jeff an JBM for alerting me to even more recent evidence that target-based fitness isn't healthy for indirect encodings. This article is a really nice find - it's in Nature and it's from people apparently not part of our community, yet comes to a very similar conclusion on the problem with target-based fitness for indirect encoding. The title is, "Adaptive dynamics under development-based genotype–phenotype maps." :

      http://www.nature.com/nature/journal/v497/n7449/full/nature12142.html

      Here is a quote from the abstract:
      "We show that the complexity of the genotype–phenotype map prevents substantial adaptation in some of the phenotype–fitness maps: sustained adaptation is only possible using `roughness' or `few-traits' phenotype–fitness maps."

      In other words, a direct target-based fitness prevents adaptation. This paper is a really nice companion to my paper with Brian Woolley.


      Best,

      ken

      --- In neat@yahoogroups.com, "Ken" <kstanley@...> wrote:
      >
      >
      >
      > Hi Shimon,
      >
      > I sense from your saying, "I am only saying that I am not aware of any result which gives good reason to abandon hope in developing methods..." that you are being very careful to remain as safely agnostic as possible. But I would guess that you (or at least most people) wouldn't be working on finding "...methods that work with indirect encodings and excel on 'regular' FFs" unless you actually believed they exist (which would indeed be a bold hypothesis). Or maybe you really do choose research directions with no confidence in them beyond total neutrality, but sometimes there's no harm in throwing your hat in the ring and seeing where your hopes (i.e. hypotheses) lead you. In any case, since you say you aren't aware of any, I'd like to offer a number of published results that do support (not prove, but certainly support) doubting the hypothesis that such methods exist.
      >
      > First, the most obvious is my paper with Brian Woolley (http://eplex.cs.ucf.edu/papers/woolley_gecco11.pdf) on re-evolving Picbreeder images as targets. That of course goes straight to the heart of the issue we are discussing, which is whether it will be possible to evolve to particular targets with regular FFs. In that paper, the answer is a resounding "no," although Picbreeder users routinely evolve such images (meaning images as complex and interesting as the Skull or Butterfly), yet not as targets. Of course that does not prove that some other indirect encoding does not exist that can evolve to such images as targets, but what should be worrisome is the extreme disparity in that work: Picbreeder images that are evolved in only a few dozen generations (with a population of 15) cannot be re-evolved effectively in 30,000 generations! I mean, you could logically say "there is no proof that a method better than NEAT+CPPNs at evolving to targets does not exist," but surely NEAT+CPPNs aren't *that* terrible of a combination - they'd have to be abjectly terrible for there to be hope that something can handily substitute in the face of such abysmal failure. So the seed of doubt is reasonably planted. At the same time, we see in the same Picbreeder system (with NEAT+CPPNs) routine discovery of such images as non-objectives in only a few generations. That's interesting.
      >
      > Second, the novelty search and behavioral diversity results (from our group and others; see http://eplex.cs.ucf.edu/noveltysearch/userspage/) deserve to be counted as evidence (not proof) supporting my hypothesis. We see there many examples of a non-objective search easily solving problems that are difficult or impossible for purely target-based searches with various algorithms. Certainly after some time all that accumulated evidence is enough to raise doubt as to whether there exists some kind of magical target-driven algorithm that always gives you what you want. But it's easy to misinterpret the lesson in novelty search's results. It's not its successes that are most important to the current discussion; rather it's the *failures* of the target-driven variants that are most suggestive: We are talking about a situation in which entirely reasonable target-based setups that follow well accepted practices from decades of research are being squashed by a ridiculous setup that doesn't even know what it's trying to do! Rather than celebrating the "success" of novelty search, we should be sweating with anxiety over this disconcerting failure of the very paradigm over which you are saying "there is no reason for despair." Perhaps not yet despair, but doubt - certainly.
      >
      > Third, sometimes just thinking a problem through is worth a few cents. Take the example of evolving the pattern of a face. If an indirect encoding is to evolve a face properly, then logic suggests that it simply must discover symmetry early on. It is true that it could theoretically discover a face by discovering both sides separately, but that is not what I am calling "healthy" because any mutation of such a perverse representation will destroy the face-ness of the face (which means it cannot lead to new faces). It also would be inefficient because it would require finding both sides independently when they are not independent. In fact, the more complex each side of the face is, the worse this misadventure becomes. At an extreme, if each side is as complex as a human brain, forget it, the need to make an astronomically unlikely sequence of discoveries twice is an absolute deal-breaker.
      >
      > Now the question is, how can there possibly be any magical target-based algorithm or encoding that "realizes" that symmetry needs to be rewarded early on when symmetry on its own does not even remotely resemble a face? Of course if there is special knowledge, like if we know that faces require symmetry, we could try to incorporate that knowledge into the FF, but that's not what you're suggesting - you're suggesting there may exist some method that doesn't need to know the stepping stones but magically rewards them anyway simply by virtue of rewarding only the target. Once again, the possibility remains, but the reason for doubt here is significant.
      >
      > Finally, the idea that the products of nature are indeed impressive is not mere conjecture. For example, see our publication on the topic of impressiveness (which also establishes a connection between novelty and impressiveness):
      > http://eplex.cs.ucf.edu/papers/lehman_alife12b.pdf
      >
      > Now I'm not taking an extreme position here. I'm not saying a target can't be anywhere in the mix whatsoever (so I leave plenty of room e.g. for the behavioral diversity combination that Stef and JBM have developed over the years). I'm just saying there is good reason to doubt the clarion call for pure target-based FFs leading us to the promised land. And as an extra bonus in the name of hope for the non-objective alternative, we have the fact that Einstein did evolve. That is, I didn't mean in my previous post to say that Einstein is a proof that non-objective evolution is the only way; rather my point is that it is a proof-of-concept that it *can* work. Your alternative on the other hand boasts no such proof of concept. We don't have any evidence it can or did work at finding human-level intelligence, ever, anthropic concern or not.
      >
      > So we've got publications, we've got results, we've got reasoning, we've got natural precedent, all consistent with my hypothesis, and it continues to accumulate. And for what I believe is your hypothesis (i.e. that powerful target-based methods exist) we have little support beyond that there is no proof that that it isn't true.
      >
      > Anyway, by all means, don't despair. But do embrace your position and consider what it implies. For example, try to imagine a way any conceivable indirect encoding with a target can commit to an ambiguous yet essential symmetry before it discovers its target. It's a really interesting question. Of course, like you say, just because you can't think of it doesn't mean it doesn't exist, but even so it sure would be reassuring if you could think of it.
      >
      > Best,
      >
      > ken
      >
      >
      > --- In neat@yahoogroups.com, "shimonw" <shimon@> wrote:
      > >
      > > Hi Ken,
      > >
      > > Yes, I agree that this conversation is exposing some of our fundamental assumptions, and it is always good to examine and question such assumptions.
      > >
      > > However, if you think that our hypotheses are equally bold, then I fear my main point has been misunderstood. I am not actually hypothesizing that an algorithm with any particular qualities exists. I am only saying that I am not aware of any result which gives good reason to abandon hope in developing methods that work with indirect encodings and excel on "regular" FFs. This is actually not a hypothesis at all; it is an incontrovertible fact. Of course, it doesn't prove that such a result doesn't exist and I certainly don't claim a comprehensive mastery of the literature. But if such a result does exist (though it's hard to imagine it would), anyone is free to simply point it out to me.
      > >
      > > By contrast, your hypothesis was that "an unhappy and unhealthy indirect encoding is one with only a strict target to which to aspire." I continue to maintain that this quite a bold claim. You suggested that the "success" of natural evolution provides a proof of concept to support your hypothesis, but I find this highly problematic. Firstly, it's unclear that evolution was "successful" in any meaningful way because there's an anthropic principle at work here: we are human and so we find humans impressive. The success of evolution is thus a self-fulfilling prophecy. Secondly, and more importantly, even if we accept that evolution is successful, this actually does not validate your hypothesis at all. Showing that there's a nice algorithm that works without a target is not the same as showing that there are *no* algorithms that work with a target, which is what your hypothesis claims.
      > >
      > > That's why I think it's not correct to describe our "hypotheses" as equally bold. In my case, there is nothing to prove: there's just a simple fact. In your case, validating the hypothesis requires proving a negative (and quite a sweeping one at that), which is notoriously difficult to do.
      > >
      > > Finally, I sense from your defense of PicBreeder that I may have been misunderstood in another way. I'm in no way trying to criticize PicBreeder or suggest that research into it is misguided. I think it's a very cool and intriguing result, possibly a highly significant one. You and I may disagree about *why* it's significant, but we definitely agree that it's useful to study further and has the potential to yield important insights.
      > >
      > > I'm just saying that, in the complementary search for optimization methods that use indirect encodings and can excel on hard FFs, there's really no reason for despair.
      > >
      > > Cheers,
      > > Shimon
      > >
      > > --- In neat@yahoogroups.com, "Ken" <kstanley@> wrote:
      > > >
      > > > Hi Shimon,
      > > >
      > > > The nice thing about this type of conversation is that it pushes us
      > > > towards realizing our fundamental assumptions. In that spirit, a few
      > > > other thoughts in response:
      > > >
      > > > Many top biologists and EC researchers would call the behavior of the
      > > > organism in the world (i.e. its interactions with the world) the
      > > > "phenotype." David Fogel once sent me a long and forceful defense of
      > > > such a position, quoting a number of famous biologists. In that
      > > > context, whether you map CPPN->pattern or CPPN->behavior, a target is
      > > > still a target and the neural network is not the phenotype.
      > > >
      > > > In any case, I guess we both hold bold hypotheses in some sense. Your
      > > > hypothesis that there exist methods that can solve hard FFs almost
      > > > deterministically as targets (up to and even beyond delivering us an
      > > > Einstein-level brain) seems boldly optimistic to me. But the big
      > > > difference between our hypotheses is that you have no proof of concept
      > > > for your approach while I do. In your approach, you will set a target
      > > > of Einstein and almost magically the algorithm will then deliver us
      > > > Einstein, which no method has yet shown even the faintest sign of
      > > > achieving. In my approach, Einstein is not the target of the search
      > > > process but instead appears as a byproduct of a search without any
      > > > explicit target, which is (amazingly) actually what happened in the real
      > > > world! It may be tempting to dismiss that distinction, but think about
      > > > it, the fact that any process actually *did* produce Einstein is beyond
      > > > incredible. We should learn from that as much as we can before
      > > > insisting "there's got to be a better way."
      > > >
      > > > Of course, it's great that you're searching for a better way (it sure
      > > > would be nice if we could just set Einstein's IQ as a fitness target),
      > > > but the things is, there will always be a ton of people trying to follow
      > > > that path because it's such a clean and intuitively appealing notion.
      > > > So it hardly needs a vigorous argument to convince someone that it's
      > > > important to try. The danger is instead that in such a rush of
      > > > enthusiasm for intuitively appealing approaches, we sweep aside the much
      > > > more delicate yet equally critical attempt to harness evolution on its
      > > > own terms, which leads to things like novelty search, indirect encoding,
      > > > and behavioral diversity. The power of this process may not be as clean
      > > > and simple as the optimization crowd is hoping; my argument here guards
      > > > against that danger.
      > > >
      > > > I think something similar is going on in our fracture argument: In
      > > > Picbreeder (and to some extent Endlessforms too, which also uses CPPNs)
      > > > we have perhaps the only massive proof-of-concept that exists of
      > > > fracture evolving through an artificial encoding. Picbreeder is a
      > > > treasure trove of almost 10,000 examples, each one with its own lesson
      > > > to teach us on fracture. And my argument is, since we are fortunate
      > > > enough to have this example right in front of us (like the example of
      > > > natural evolution evolving Einstein), let's learn everything we can from
      > > > it before looking away and saying hastily, "there must be something
      > > > better." Picbreeder is a fortuitous goldmine of data that is very hard
      > > > to reproduce; it took several years and the contributions of hundreds
      > > > of people to accumulate its results. Let's scrub every last bit of
      > > > wisdom from that windfall that we can. It's not a question of better
      > > > for me, it's a question of learning from the only evidence we have. How
      > > > do you expect to really develop a better encoding of fracture if you
      > > > ignore the thousands of examples of fracture that already exist? You
      > > > will just end up reinventing the wheel.
      > > >
      > > > The danger of that is evident in some of the assumptions you hold
      > > > already about how CPPNs encode fracture. For example, you are worried
      > > > that it may not do so efficiently, but you have only constructed a
      > > > single thought experiment (your figure 13) instead of taking a measured
      > > > look at the thousands of examples in front of us. In fact, while indeed
      > > > I don't think 6 nodes is particularly much, it's easy enough to find
      > > > fracture in Picbreeder represented in under 6 nodes. For example, the
      > > > pattern below has at least 3 distinct fractured regions (which I
      > > > numbered for clarity): a pinkish region, an ovular inner region, and a
      > > > conic lower region. However, the CPPN that encodes it (shown to its
      > > > left) only uses 4 nodes to encode these 3 fractured regions (notice that
      > > > two of the displayed hidden nodes have outgoing weights of zero, so they
      > > > are not contributing to the output pattern, leaving only the 4 nodes).
      > > > That's a respectable 1.3 nodes per fractured region:
      > > >
      > > > (this image is also available at
      > > > http://eplex.cs.ucf.edu/hyperNEATpage/content/four-node-fracture.jpg
      > > > <http://eplex.cs.ucf.edu/hyperNEATpage/content/four-node-fracture.jpg>
      > > > )
      > > >
      > > >
      > > >
      > > >
      > > > We could argue about the definition of fracture, and perhaps you'd want
      > > > to refine the definition to argue that the above example doesn't really
      > > > have three fractured regions. Or you could argue that the "d" input
      > > > should be counted as a 5th node (to encode the 3 regions, which is still
      > > > a respectable 1.7 nodes per region). But even those would be healthy
      > > > discussions that we could not begin to have without first referring to
      > > > the examples that we already have. Of course (intuitively) more complex
      > > > fracture will require more nodes (maybe at some point 6!), as it should.
      > > > All I'm saying is I think this kind of speculation about whether it's
      > > > efficient or not is jumping the gun: Let's understand it first before
      > > > we worry about fixing it.
      > > >
      > > > So I think there's a difference of philosophies ultimately at work here.
      > > > Because the road ahead to AI is so vast, I'm more motivated by
      > > > maximizing our information than doing "better." For example, that's the
      > > > motivation behind Picbreeder - obviously it is not quantifiably better
      > > > than anything in particular, but it increased our understanding of a
      > > > number of important phenomena, including fracture, representation, and
      > > > non-objective search, by providing useful information. So I say, let's
      > > > see where this takes us - there's still a ton left to learn. But you
      > > > are already itching to start anew and fix things that are not clearly
      > > > broken just when we have hit a goldmine of untapped information.
      > > >
      > > > Without question, neither of our perspectives is definitively superior;
      > > > we are both merely speculating about where time is best invested, and
      > > > obviously neither of us can predict the future. This argument is only
      > > > my own case for my perspective.
      > > >
      > > > Best,
      > > >
      > > > ken
      > > >
      > > >
      > > > --- In neat@yahoogroups.com, "shimonw" wrote:
      > > > >
      > > > > Hi Ken,
      > > > >
      > > > > If I may, I'd like to offer a couple reactions to your latest message.
      > > > This is indeed an interesting discussion that touches on many
      > > > potentially important issues. I hope I can offer a useful perspective
      > > > on these topics.
      > > > >
      > > > > You are right that in a target-based scenario there can be many CPPNs
      > > > that generate the same phenotype. But the CPPN is a genotype, not a
      > > > phenotype. In what I'm calling "regular" FFs, there are potentially many
      > > > *phenotypes* that solve the problem, and for each of them potentially
      > > > many genotypes. So in my mind, there is still a useful distinction
      > > > between target based FFs and regular FFs, though they are perhaps best
      > > > seen as different points on a spectrum.
      > > > >
      > > > > If I understand correctly, you are suggesting that the important
      > > > distinction is how the FF interacts with the search process. But to me,
      > > > this is a difficult criterion to use because the search process could be
      > > > anything. The space of possible black-box optimization methods is huge,
      > > > and what encourages piecewise incremental progress for one method may
      > > > not for another.
      > > > >
      > > > > I don't pretend to know what kind of algorithm would generate
      > > > Einstein-level intelligence (I don't even know if this is a useful
      > > > goal). But as a researcher I highly respect once told me, "your failure
      > > > to imagine it does not constitute a proof that it cannot be done."
      > > > >
      > > > > That's why I think your hypothesis is quite a bold one, because it
      > > > looks at the limitations of a specific class of black-box optimization
      > > > methods and generalizes them to all possible black-box optimization
      > > > methods.
      > > > >
      > > > > To give just one example of the possibilities here: algorithms for
      > > > continuous-armed bandits, such as X-armed bandits and Bayesian
      > > > optimization methods such as GP-UCB, can be applied to black-box
      > > > optimization. These methods avoid the problem of local optima in a
      > > > principled way, by maintaining a posterior distribution over the global
      > > > FF, and using optimism in the face of uncertainty to ensure sufficient
      > > > exploration of the solution space. As a result, these methods have very
      > > > nice theoretical properties, like guaranteed convergence to the global
      > > > optimum in the limit and logarithmic regret bounds along the way.
      > > > >
      > > > > As far as I know, no one has tried to develop versions of these
      > > > methods that can discover NN topologies, and which would thus be
      > > > suitable for optimizing CPPNs or other indirect encodings. But there's
      > > > no a priori reason to think it can't be done. I'm not saying this would
      > > > necessarily work or even that it's the most promising approach to
      > > > explore. I'm just saying it's one example of a principled approach that
      > > > could avoid all the difficulties you mention and which we currently have
      > > > no strong reason to eliminate from contention.
      > > > >
      > > > > So I think it's quite likely that these hard FFs are not unsolvable,
      > > > but just that current methods cannot solve them. Rather than giving up
      > > > on them, in my opinion we should be focusing on developing better
      > > > methods for them.
      > > > >
      > > > > Regarding whether 6 nodes is a lot to represent fracture, I think the
      > > > same point applies: just because we can't think of a better way to do
      > > > it, doesn't mean it doesn't exist. Our paper establishes 6 as an upper
      > > > bound, which can be easily done by example. If I understand correctly,
      > > > you are suggesting that 6 may be a lower bound, which is much more
      > > > difficult to demonstrate.
      > > > >
      > > > > I could definitely imagine that a different type of network, or one
      > > > with a different set of activation functions, might be able to make
      > > > better use of 6 nodes. Even if it's true that there's a trade-off, and
      > > > using fewer nodes means less flexibility, there may be many cases where
      > > > that's a favorable trade-off. We should at least be open to the
      > > > possibility that it some cases the sweet spot is not a representation
      > > > that requires 6 nodes for fracture.
      > > > >
      > > > > I'm looking forward to chatting more about this at GECCO.
      > > > >
      > > > > Cheers,
      > > > > Shimon
      > > > >
      > > > > --- In neat@yahoogroups.com, "Ken" kstanley@ wrote:
      > > > > >
      > > > > > Hi Shimon,
      > > > > >
      > > > > > These are some really interesting and deep issues we're getting
      > > > into. I
      > > > > > am sure they will be the foundation of great discussions at GECCO.
      > > > I'll
      > > > > > try to keep my response more brief than before.
      > > > > >
      > > > > > 1) Indeed recent quadruped results are not in the same setup as in
      > > > your
      > > > > > work; that is a legitimate qualification and they do not constitute
      > > > a
      > > > > > proof that in your particular setup HyperNEAT would succeed.
      > > > However,
      > > > > > they are arguably at least comparably complex. For example, the
      > > > CTRNN
      > > > > > in
      > > > > > http://eplex.cs.ucf.edu/papers/risi_gecco13b.pdf
      > > > > > is a complicated
      > > > > > structure and the CPPN that encodes it is required not only to
      > > > generate
      > > > > > a controller for a single quadruped morphology, but to generate
      > > > multiple
      > > > > > controllers for multiple morphologies, all from the same CPPN. A
      > > > video
      > > > > > of three controllers all from the same CPPN is here:
      > > > > > http://youtu.be/oLSSt5GyHNk
      > > > > >
      > > > > > 2) I think the question of what is "target-based" can actually be
      > > > > > interesting, but I completely agree that the semantic side of the
      > > > > > argument isn't really important. But what I do find interesting is
      > > > the
      > > > > > idea that these two scenarios differ substantively in your mind (as
      > > > you
      > > > > > put it):
      > > > > >
      > > > > > "there is an important difference between FFs that require a single
      > > > > > specific phenotype and FFs that require only that some goal be
      > > > achieved"
      > > > > >
      > > > > > I think by "single specific phenotype" you mean pattern-matching
      > > > (i.e.
      > > > > > image-matching). But I think this distinction doesn't really exist:
      > > > > > There are an unlimited number of networks (i.e. CPPNs) that can
      > > > encode a
      > > > > > particular two-dimensional image, just as there are an unlimited
      > > > number
      > > > > > of CPPNs that can encode a particular behavior or goal (such as
      > > > > > following a line).
      > > > > >
      > > > > > What makes both target-based and fundamentally the same is not the
      > > > > > number of ways they can be solved, but rather the way the fitness
      > > > > > function interacts with the search process. The problem is that
      > > > > > target-based fitness encourages piece-wise incremental progress,
      > > > which
      > > > > > tends to be highly deceptive. For example, with an image, matching
      > > > a
      > > > > > single pixel can raise fitness even if the function that causes that
      > > > > > pixel to be matched has no relationship whatsoever to the overall
      > > > > > regularities in the target pattern. The same is true in control
      > > > tasks:
      > > > > > A mutation that causes a quadruped to lunge forward clumsily is
      > > > rewarded
      > > > > > for the slight improvement in fitness, whereas an important
      > > > underlying
      > > > > > regularity (e.g. oscillation) necessary to get really good at the
      > > > task
      > > > > > is never established. Non-target-based fitness (or what I call
      > > > > > "non-objective") avoids these problems because it *does* reward
      > > > > > establishing regularities: it appreciates new regularities even if
      > > > they
      > > > > > don't immediately raise fitness.
      > > > > >
      > > > > > But what's most interesting to me is your intuition that there is
      > > > some
      > > > > > way to sidestep the tradeoff in combining indirect encodings with
      > > > > > target-based fitness functions. That is, you suspect there may
      > > > exist an
      > > > > > indirect encoding that can both elaborate regularities
      > > > compositionally
      > > > > > over very many generations and also almost deterministically satisfy
      > > > an
      > > > > > arbitrary target-based objective. I am convinced that is not the
      > > > case
      > > > > > (it would be too good to be true), but you rightly point out that my
      > > > > > position is a hypothesis. However, just as a thought experiment,
      > > > can
      > > > > > you really imagine any neural network encoding (including DNA) that
      > > > > > would give you Einstein-level intelligence if the target was simply
      > > > to
      > > > > > score maximally on an IQ test? It is plain to me that the stepping
      > > > > > stones to human level cannot be crossed in the presence of a
      > > > > > target-based objective (or any one conceivable). However,
      > > > > > interestingly, that does not mean that such a neural network does
      > > > not
      > > > > > exist in the search space. It just means a target won't get you
      > > > there.
      > > > > >
      > > > > > 3) We apparently disagree on whether 6 is a big number (for nodes
      > > > needed
      > > > > > to represent fracture). If you try to devise an encoding that
      > > > > > represents fracture with fewer than that, my intuition is that you
      > > > would
      > > > > > be sacrificing an enormous breadth of flexibility in the kinds of
      > > > > > fracture (and patterns in general) that you can represent. Think
      > > > about
      > > > > > the number of "degrees of freedom" in fracture: it's not really
      > > > > > well-defined, but a single line of fracture has a lot of dimensions:
      > > > > >
      > > > > > -position
      > > > > > -orientation
      > > > > > -curvature (which can be arbitrarily complex)
      > > > > > -fracture gradient (that is, one region can smoothly transition into
      > > > > > another in a kind of interpolated transitional zone)
      > > > > > -embedding (fracture can potentially be hierarchical or regular,
      > > > i.e.
      > > > > > dependent on higher-level containing regions)
      > > > > >
      > > > > > The idea that all of that can be encoded in anything less than about
      > > > 6
      > > > > > simple functions seems optimistic. Of course, if you are willing to
      > > > > > sacrifice some of those degrees of freedom, then you can get fewer
      > > > > > nodes, but the exquisite minutia of such patterns would be lost (and
      > > > > > you'd move more towards direct encoding, like the wavelets do).
      > > > > >
      > > > > > By the way, here are some cool examples of complicated kinds of
      > > > fracture
      > > > > > from Picbreeder (such as fractured periodic zones, but even more
      > > > complex
      > > > > > than even that):
      > > > > >
      > > > > > Nontrivial color patterns in each zone:
      > > > > > http://picbreeder.org/search/showgenome.php?sid=11328
      > > > > >
      > > > > >
      > > > > > Very complex brush-stroke pattern inside the apple vs. outside (the
      > > > DNA
      > > > > > for this one is fascinating):
      > > > > > http://picbreeder.org/search/showgenome.php?sid=7109
      > > > > >
      > > > > >
      > > > > >
      > > > > > Fractured regions covering a distorted surface, giving a remarkable
      > > > > > underlying curvature:
      > > > > > http://picbreeder.org/search/showgenome.php?sid=2684
      > > > > >
      > > > > >
      > > > > > A color variant:
      > > > http://picbreeder.org/search/showgenome.php?sid=6652
      > > > > >
      > > > > >
      > > > > > When I see so many remarkable examples like these on Picbreeder, the
      > > > > > message to me is that we have only scratched the surface of what
      > > > CPPN
      > > > > > encoding can teach us about representation. That's why I think it's
      > > > > > premature (in the face of such a treasure trove of evidence) to be
      > > > > > worrying about whether we can represent some subcomponent of such
      > > > > > patterns with less than 6 nodes. At present I'm amazed they can be
      > > > > > represented at all, let alone with under 6 nodes.
      > > > > >
      > > > > > Thanks very much for raising these issues in any case - it's a great
      > > > > > debate to have about representation and search and goes to the heart
      > > > of
      > > > > > the field of GDS/indirect encoding.
      > > > > >
      > > > > > Best,
      > > > > >
      > > > > > ken
      > > > > >
      > > > > > --- In neat@yahoogroups.com, "shimonw" wrote:
      > > > > > >
      > > > > > > Hi Ken,
      > > > > > >
      > > > > > > Thanks for your interesting and thought-provoking comments. I'll
      > > > give
      > > > > > some brief reactions here, and I hope we can have a productive
      > > > > > discussion about it at GECCO.
      > > > > > >
      > > > > > > 1) I won't comment for now on the new experiments you've been
      > > > running
      > > > > > because the details are not available yet. Instead, I will just
      > > > comment
      > > > > > on the various walking gait domains, because the details of the
      > > > > > additional results you mentioned are in that case already available,
      > > > in
      > > > > > newly published GECCO papers.
      > > > > > >
      > > > > > > FIrst of all, these are very cool results, and nice success
      > > > stories
      > > > > > for HyperNEAT. It's great to see that the GDS community is
      > > > continuing
      > > > > > the push the envelope in terms of robot locomotion, which seems to
      > > > be
      > > > > > emerging as a nice application for indirect encodings.
      > > > > > >
      > > > > > > However, I would simply caution against placing all these
      > > > variations
      > > > > > on the walking gait task on a one-dimensional spectrum of
      > > > difficulty.
      > > > > > In our paper, we took the orignal walking gait task and made only
      > > > one
      > > > > > change (increasing the mass of the torso) which clearly makes the
      > > > task
      > > > > > harder. In the papers Ken mentioned, there are other differences,
      > > > e.g.,
      > > > > > the use of an SUPG encoding, the use of CTRNNs, the use of a
      > > > different
      > > > > > substrate topology, and varying the length of the legs.
      > > > > > >
      > > > > > > It's completely legitimate to make these changes and they don't
      > > > > > detract from the results at all. But they are confounding factors
      > > > when
      > > > > > it comes to comparing HyperNEAT's performance on walking gait tasks
      > > > of
      > > > > > different difficulties. Some of these changes may make the task
      > > > harder
      > > > > > in some ways but other changes may make it easier in others ways,
      > > > and so
      > > > > > far we don't have experimental results that control for these
      > > > factors.
      > > > > > >
      > > > > > > 2) I hope to avoid a semantic debate about what is a
      > > > "target-based"
      > > > > > FF. If you want to include what I was calling a "regular" FF in the
      > > > > > scope of target-based FFs, I won't object. But my point is that,
      > > > > > regardless of what you call them, there is an important difference
      > > > > > between FFs that require a single specific phenotype and FFs that
      > > > > > require only that some goal be achieved. For the latter, there may
      > > > be
      > > > > > many ways to skin the cat, though in any interesting problem, good
      > > > > > solutions are still quite rare. The distinction is important
      > > > because,
      > > > > > while the former category is arguably only of theoretical interest,
      > > > the
      > > > > > second category corresponds to what I consider the most interesting
      > > > and
      > > > > > important class of FFs, because these are the FFs that naturally
      > > > arise
      > > > > > in a very large number of real-world optimization problems.
      > > > > > >
      > > > > > > So, using your terminology, I agree it is reasonable to say
      > > > > > HyperNEAT's difficulties with fracture are probably limited to
      > > > > > "target-based" FFs. But for me, this is a potentially serious
      > > > > > restriction, since target-based FFs include not just pathological
      > > > FFs
      > > > > > but a large class of real-world FFs.
      > > > > > >
      > > > > > > Regarding the wavelet method, I would still definitely call this
      > > > an
      > > > > > indirect encoding, but it is in some sense "less indirect" because
      > > > it
      > > > > > lacks the compositional functions of HyperNEAT. It's a perfectly
      > > > > > reasonable hypothesis that such compositionality is advantageous in
      > > > some
      > > > > > ways. However, if that's true, then we should be able to
      > > > demonstrate
      > > > > > that by finding tasks where HyperNEAT outperforms the wavelet method
      > > > > > (FYI, in the extended analysis Thomas is conducting for his master's
      > > > > > thesis, we have found one variation of the line-following task where
      > > > > > this is the case). So in that sense, the wavelet method is a useful
      > > > > > baseline, which is the whole reason we introduced it.
      > > > > > >
      > > > > > > 3) If it's true that it takes ~6 nodes to represent fracture, then
      > > > I
      > > > > > think this a potentially important point. On regular FFs, it could
      > > > > > contribute to the difficulty of discovering fracture, since
      > > > > > representations that have only some of the necessary components may
      > > > not
      > > > > > be rewarded (I think you would call this "deception"). In
      > > > > > Picbreeder-like tasks, we already see that fracture can evolve
      > > > anyway,
      > > > > > but this doesn't mean it wouldn't do it even better if fracture
      > > > required
      > > > > > fewer nodes to represent. If we think that the solutions to many
      > > > > > interesting problems require fracture, then I think it's at least
      > > > > > possible that one could devise a better representation for such
      > > > problems
      > > > > > than the CPPNs used in HyperNEAT.
      > > > > > >
      > > > > > > As I understand it, your approach to dealing with "regular" FFs is
      > > > to
      > > > > > reformulate them "in a way that respects the need for phenotypic
      > > > > > diversity and open-endedness." That's a very interesting approach
      > > > and I
      > > > > > think it has a lot of merit, but I don't think it will solve all our
      > > > > > problems because it presupposes that such a reformulation is
      > > > possible
      > > > > > (or that the prior knowledge it requires is available). In some
      > > > cases,
      > > > > > I think we are just stuck with hard FFs and we need to develop
      > > > better
      > > > > > methods to deal with them.
      > > > > > >
      > > > > > > Regarding the idea that "an unhappy and unhealthy indirect
      > > > encoding is
      > > > > > one with only a strict target to which to aspire": this is a very
      > > > > > intriguing hypothesis, but to me it is only a hypothesis. I think
      > > > it's
      > > > > > true of existing indirect encodings, but that for me does not in any
      > > > way
      > > > > > rule out the possibility of developing a different indirect encoding
      > > > for
      > > > > > which that is not true, and I think that's one thing we should be
      > > > > > working on. One of the reasons that I'm interested in indirect
      > > > > > encodings is that I strongly believe this can be done.
      > > > > > >
      > > > > > > Cheers,
      > > > > > > Shimon
      > > > > > >
      > > > > >
      > > > >
      > > >
      > >
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.