## CPPNs. Recursive vs Feedforward

Expand Messages
• Quick question. What s the prevailing opinion on whether CPPNs should be recursive or feedforward-only? Also there were discussions some years back about
Message 1 of 10 , Nov 2, 2009
• 0 Attachment
Quick question. What's the prevailing opinion on whether CPPNs should
be recursive or feedforward-only?

Also there were discussions some years back about algorithms for
efficiently implementing feedforward networks - e.g. calculating the
longest path from input to output. I think Derek and Phillip worked on
these ideas in ANJI so I'll be looking in the ANJI code (and NEAT
group archive) but if anyone's got any more recent ideas/pointers on
the subject then I'd be interested to hear them. Thanks.
• Hi Colin ... I ve recently implemented an algorithm that find this longuest path. It is written using boost::graph for my own framework (sferes2) but you could
Message 2 of 10 , Nov 3, 2009
• 0 Attachment
Hi Colin

Colin Green <colin.green1@...> wrote :

| Also there were discussions some years back about algorithms for
| efficiently implementing feedforward networks - e.g. calculating the
| longest path from input to output. I think Derek and Phillip worked on
| these ideas in ANJI so I'll be looking in the ANJI code (and NEAT
| group archive) but if anyone's got any more recent ideas/pointers on
| the subject then I'd be interested to hear them. Thanks.

I've recently implemented an algorithm that find this longuest
path. It is written using boost::graph for my own framework (sferes2)
but you could probably translate it to use it in NEAT. Here is the
code (check boost.org for the documentation of boost::graph),
where this->_g is the graph (feed-forward). I've not heavily
tested this code so I don't garantee it's bug-free but it should

void _compute_depth()
{
using namespace boost;
typedef std::map<vertex_desc_t, size_t> int_map_t;
typedef std::map<vertex_desc_t, vertex_desc_t> vertex_map_t;
typedef std::map<vertex_desc_t, default_color_type> color_map_t;
typedef std::map<edge_desc_t, int> edge_map_t;

typedef associative_property_map<int_map_t> a_map_t;
typedef associative_property_map<color_map_t> c_map_t;
typedef associative_property_map<vertex_map_t> v_map_t;
typedef associative_property_map<edge_map_t> e_map_t;

color_map_t cm; c_map_t cmap(cm);
vertex_map_t vm; v_map_t pmap(vm);
edge_map_t em;
BGL_FORALL_EDGES_T(e, this->_g, graph_t)
em[e] = 1;
e_map_t wmap(em);
_depth = 0;
// we compute the longest path between inputs and outputs
BOOST_FOREACH(vertex_desc_t s, this->_inputs)
{
int_map_t im; a_map_t dmap(im);
dag_shortest_paths
(this->_g, s, dmap, wmap, cmap, pmap,
dijkstra_visitor<null_visitor>(),
std::greater<int>(),
closed_plus<int>(),
std::numeric_limits<int>::min(), 0);

BGL_FORALL_VERTICES_T(v, this->_g, graph_t)
{
size_t d = get(dmap, v);
if (this->_g[v].get_out() != -1 && d <= num_vertices(this->_g))
_depth = std::max(_depth, d);
}
}
// add one "to be sure"
_depth ++;
}

--
Jean-Baptiste Mouret / Mandor
tel : (+33) 6 28 35 10 49
3 ((4&({*.(=+/))++/=3:)@([:,/0&,^:(i.3)@|:"2^:2))&.>@]^:(i.@[) <#:3 6 2
• Colin, it is probably not a critical decision whether CPPNs are recurrent or not (at least for the purposes of HyperNEAT), but it does have implications. In
Message 3 of 10 , Nov 3, 2009
• 0 Attachment
Colin, it is probably not a critical decision whether CPPNs are recurrent or not (at least for the purposes of HyperNEAT), but it does have implications. In the context of patterns, recurrence has the effect of potentially creating fractals, that is, self-similarity at different levels of scale. If you think about it, recurrence is like recreating a coordinate frame situated within its own self, which means you will get it repeating at different scales. Note that because of the complexity of the overall network, such repetitions may not be exact (and likely won't be), so you'd get repetition with variation at different scales.

So it introduces a new kind of regularity that the other activation functions don't really genuinely offer. However, my feeling from looking at 2-D patterns created by recurrent CPPNs is that they are brittle and can be difficult to optimize such patterns. While they may produce fractals in principle, in practice, they can produce messy noise-like patterns because of their brittleness and interaction with the other parts of the networks (which may include even more recurrence). I have a hunch that a more elegant kind of recurrence could be introduced to artificially enforce certain types of activation paths (while freezing others) to produce much more elegant fractal-like patterns consistently, but barring that, the CPPN with recurrent connections will not necessarily produce patterns that are easy to characterize. (Note that it is also an open and interesting question whether a neural networks should have fractal-like characteristics or not.)

Nevertheless, it is not clear ultimately that such connections cause a problem or not. While they may not look like very pretty fractals, for the purposes of HyperNEAT, it is not clear that they need to look pretty, and maybe they aren't hurting anything, or even helping a bit by giving extra degrees of freedom through the search space of patterns. I believe HyperSharpNEAT actually does allow such connections and it doesn't seem to have any serious performance implication, though it's hard to be certain without extensive testing.

But if you really want to kind of understand what types of things CPPNs will output, it's best left feedforward, because then it can be understood as sums and compositions of functions, which is conceptually pure and follows the theory in the papers. For example. Picbreeder is strictly feedforward, and that helps us to understand the function of internal nodes in Picbreeder networks (we hope to soon make public the structure of CPPNs within Picbreeder, which is very educational).

I hope this provides some insight.

ken

--- In neat@yahoogroups.com, Colin Green <colin.green1@...> wrote:
>
> Quick question. What's the prevailing opinion on whether CPPNs should
> be recursive or feedforward-only?
>
> Also there were discussions some years back about algorithms for
> efficiently implementing feedforward networks - e.g. calculating the
> longest path from input to output. I think Derek and Phillip worked on
> these ideas in ANJI so I'll be looking in the ANJI code (and NEAT
> group archive) but if anyone's got any more recent ideas/pointers on
> the subject then I'd be interested to hear them. Thanks.
>
• Colin, there is indeed a fast way to compute feedforward activation, but it does not actually involve computing the longest path. Rather, it entails recursing
Message 4 of 10 , Nov 3, 2009
• 0 Attachment
Colin, there is indeed a fast way to compute feedforward activation, but it does not actually involve computing the longest path. Rather, it entails recursing back from the outputs to the inputs, each time summing the incoming activation from the recursive calls. If a node has already been computed that is then called again, it simply returns the result of that prior computation. This approach is efficient because every activation function is guaranteed to be only run once. In contrast, in the more common arbitrary-topology approach to activation, at time t each node's activation is computed from incoming nodes' activations at tine t-1, which can take several ticks (and therefore re-activations) for activation to travel through the whole network.

Note that the two different ways of activating do not always yield equivalent results because of some subtle implications. However, these differences generally only come up in continual control scenarios (i.e. scenarios in which a networks is activated over and over again continually). If you just want a single "final answer" (i.e. like a pattern that the CPPN outputs) they should be equivalent, as long as the network really is feedforward.

ken

--- In neat@yahoogroups.com, Colin Green <colin.green1@...> wrote:
>
> Quick question. What's the prevailing opinion on whether CPPNs should
> be recursive or feedforward-only?
>
> Also there were discussions some years back about algorithms for
> efficiently implementing feedforward networks - e.g. calculating the
> longest path from input to output. I think Derek and Phillip worked on
> these ideas in ANJI so I'll be looking in the ANJI code (and NEAT
> group archive) but if anyone's got any more recent ideas/pointers on
> the subject then I'd be interested to hear them. Thanks.
>
• 2009/11/3 Ken ... [...] ... Yes I see. It s like evaluating an expression tree but with an extra rule for handling the fact it s not a
Message 5 of 10 , Nov 3, 2009
• 0 Attachment
2009/11/3 Ken <kstanley@...>
>
> Colin, there is indeed a fast way to compute feedforward activation,
[...]
> it entails recursing back from the outputs to the inputs, each time summing the incoming activation from the recursive calls. If a
> node has already been computed that is then called again, it simply returns the result of that prior computation.

Yes I see. It's like evaluating an expression tree but with an extra
rule for handling the fact it's not a tree (it's a directed acyclic
graph). With the timestep approach nodes are being activated even when
the signal 'wave' hasn't reached them yet, hence there is some
inefficiency.

> Note that the two different ways of activating do not always yield equivalent results because of some subtle implications.

Noted. Thanks.
• 2009/11/3 Jean-Baptiste Mouret / Mandor ... Thanks. I wonder if this is the same approach for DAGs listed here:
Message 6 of 10 , Nov 3, 2009
• 0 Attachment
2009/11/3 Jean-Baptiste Mouret / Mandor <mandor@...>
>
> I've recently implemented an algorithm that find this longuest
> path. It is written using boost::graph for my own framework (sferes2)
> but you could probably translate it to use it in NEAT. Here is the
> code (check boost.org for the documentation of boost::graph),
> where this->_g is the graph (feed-forward). I've not heavily
> tested this code so I don't garantee it's bug-free but it should

Thanks. I wonder if this is the same approach for DAGs listed here:

http://en.wikipedia.org/wiki/Longest_path_problem

Colin.
• 2009/11/3 Ken ... [...] Thanks. From reading your response my instinct is to use feedforward as the default/baseline for CPPNs and to
Message 7 of 10 , Nov 3, 2009
• 0 Attachment
2009/11/3 Ken <kstanley@...>
>
> Colin, it is probably not a critical decision whether CPPNs are recurrent or not (at least for the purposes of HyperNEAT), but it
> does have implications.
[...]

as the default/baseline for CPPNs and to look toward recursive CPPNs
as a research path from there. The function composition aspect of
feedforward networks is simple to understand (again, it's like an
expression tree with a little extra complexity - but not as much as a
recursive network).

> But if you really want to kind of understand what types of things CPPNs will output, it's best left feedforward, because then it can
> be understood as sums and compositions of functions, which is conceptually pure and follows the theory in the papers.

Totally agree.

> For example. Picbreeder is strictly feedforward, and that helps us to understand the function of internal nodes in Picbreeder
> networks (we hope to soon make public the structure of CPPNs within Picbreeder, which is very educational).

Will look forward to it. I appreciate the amount of work it takes to
get this kind of thing up and running.

Colin.
• Hi Colin, ... Yes, this is exactly the second approach listed in the DAG part (i.e. Using shortest-path algorithms ) since a feed-forward NN is obviously a
Message 8 of 10 , Nov 3, 2009
• 0 Attachment
Hi Colin,

Colin Green <colin.green1@...> wrote :
| 2009/11/3 Jean-Baptiste Mouret / Mandor <mandor@...>
| >
| > I've recently implemented an algorithm that find this longuest
| > path. It is written using boost::graph for my own framework (sferes2)
| > but you could probably translate it to use it in NEAT. Here is the
| > code (check boost.org for the documentation of boost::graph),
| > where this->_g is the graph (feed-forward). I've not heavily
| > tested this code so I don't garantee it's bug-free but it should

| Thanks. I wonder if this is the same approach for DAGs listed here:
| http://en.wikipedia.org/wiki/Longest_path_problem

Yes, this is exactly the second approach listed in the DAG part
(i.e. "Using shortest-path algorithms") since a feed-forward NN is
obviously a DAG.

I used a shortest path algorithm specially optimized for DAG (this one
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/dag_shortest_paths.html)
in which I "reversed" the distance.

Best regards,
--
Jean-Baptiste Mouret / Mandor
tel : (+33) 6 28 35 10 49
3 ((4&({*.(=+/))++/=3:)@([:,/0&,^:(i.3)@|:"2^:2))&.>@]^:(i.@[) <#:3 6 2
• Hey Colin, CPPNs, being an indirect encoding, allow for small changes in the genotype to have profound effects on the resulting substrate. While this is what
Message 9 of 10 , Nov 3, 2009
• 0 Attachment
Hey Colin,

CPPNs, being an indirect encoding, allow for small changes in the genotype to have profound effects on the resulting substrate. While this is what makes indirect encodings so powerful, the drawback is that it is hard to make a population drift in a particular gradient along the fitness landscape. In practice, I've noticed that adding recurrence magnifies this problem without providing much benefit in terms of overall fitness.

Jason G.

--- In neat@yahoogroups.com, Colin Green <colin.green1@...> wrote:
>
> 2009/11/3 Ken <kstanley@...>
> >
> > Colin, it is probably not a critical decision whether CPPNs are recurrent or not (at least for the purposes of HyperNEAT), but it
> > does have implications.
> [...]
>
> Thanks. From reading your response my instinct is to use feedforward
> as the default/baseline for CPPNs and to look toward recursive CPPNs
> as a research path from there. The function composition aspect of
> feedforward networks is simple to understand (again, it's like an
> expression tree with a little extra complexity - but not as much as a
> recursive network).
>
>
> > But if you really want to kind of understand what types of things CPPNs will output, it's best left feedforward, because then it can
> > be understood as sums and compositions of functions, which is conceptually pure and follows the theory in the papers.
>
> Totally agree.
>
> > For example. Picbreeder is strictly feedforward, and that helps us to understand the function of internal nodes in Picbreeder
> > networks (we hope to soon make public the structure of CPPNs within Picbreeder, which is very educational).
>
>
> Will look forward to it. I appreciate the amount of work it takes to
> get this kind of thing up and running.
>
> Colin.
>
• 2009/11/4 jgmath2000 ... Noted. Thanks.
Message 10 of 10 , Nov 4, 2009
• 0 Attachment
2009/11/4 jgmath2000 <jgmath2000@...>

>
> CPPNs, being an indirect encoding, allow for small changes in the genotype to have profound effects on the resulting substrate.
> While this is what makes indirect encodings so powerful, the drawback is that it is hard to make a population drift in a particular
> gradient along the fitness landscape. In practice, I've noticed that adding recurrence magnifies this problem without providing
> much benefit in terms of overall fitness.

Noted. Thanks.
Your message has been successfully submitted and would be delivered to recipients shortly.