Evolution of Emergent Behavior using Genetic Programming

[Stephen Guerin]

> OK, I'm being dumb as a rock. Can other search techniques be considered
> self-organizing? If not, what is that makes a GA self-organizing but (say)
> gradient descent not?

It's not you, Robert -- It's gradient descent that is as dumb as a rock ;-)

We've been punting the criteria for self-organizing algorithms around for a
few years now and I can't say that I've seen necessary and sufficient
conditions defined out there yet.

Intuitively, I would say greedy gradient descent by a single computational
entity/agent is not self-organizing. I think its interesting, though, that I
would classify learning by back propagation in a neural network as an
instance of self-organization when Greg Stone's chapter in the early UCSD
PDP books (Stone, 1986) showed back propagation (delta rule) to be a form of
gradient descent. So what's the difference here?

Firstly, I think you need a *collection* of algorithms to constitute a
system that is capable of self-organization. I'll call the things in the
collections agents but you can call them PDEs :-)

Secondly, I suspect it has to do with the transfer of information of the
asymmetries of the environment (the function to be optimized) into the
structure of the agent system. I don't see this happening in simple gradient
descent.

In self-organizing systems, agents are constrained (informed) from their
natural degrees of freedom (loss of symmetry) as the system evolves.
Constraints can manifest themselves in environment-agent interactions,
agent-agent interactions, or internal rules to the agents themselves.

In the neural network example, information about the structure of the
pattern to be classified is imported to weights on the edges of the neural
network. This is a change on the agent-agent interaction. In the example of
a single agent falling down hill, I don't see the importing of information
into an agent's system structure - only work being done on the agent as it
moves to a lower energy state. I wonder if we could move further on a
continuum of self-organizing systems if we introduced history to the
gradient-decent agent like what happens in simulated annealing...

So to your question "are GAs self-organizing"? In the past, I've said no.
But I could flip-flop as the definitions get clearer and we think of the
structure of the environment being tranferred to lower the entropy of the
genomes. Chris Adami has looked at mutal entropy measures like this for his
Avida system and proposes it as a measure of complexity. So, in this
context, maybe GAs are self-organizing.

Eventually, perhaps concepts from nonequilibrium statistical mechanics will
apply that center on generalized definitions of heat and work and make all
this more rigorous. (Maybe, we'll have to goad Eric S. into doing the
appropriate maths and sums.) For now, it probably is just a bunch of jargon
babble :-) It's certainly murky in my head. It reminds me of asking "are
viruses alive?" when we don't have a good definition of life yet...

-Steve

Stone, G. O. (1986). An analysis of the delta rule and the learning of
statistical associations. In Rumelhart, D. E. & McClelland, J. L.(Eds.),
Parallel Distributed Processing, Vol. I (pp.444-459). Cambridge,
Massachusetts: MIT Press.

[Robert Holmes]

Dan, Steve - thanks for your posts. Good to know that there are good reason
for me not understanding this stuff. You should write a paper someday ;-)

Steve - I like your intuitive "collection of algorithms". I wonder though -
just because we have a collection of computing entities (ants or replicating
genes) does that mean we have a collection of algorithms? In the examples
I've seen, the entities are all running essentially the same algorithm, it's
just that the parameters of each agent's instance of the algorithm is
different. Now if they were *genuinely* different algorithms (one ant is
using gradient descent, one gradient descent with memory, one talking with
its neighbours to create some form of local collaborative simplex algorithm
etc.) things could get kinda fun. Anyone done any work on this?

Robert

> -----Original Message-----
> From: Stephen Guerin [mailto:[hidden email]]
> Sent: Monday, March 14, 2005 9:10 PM
> To: Friam
> Subject: RE: [FRIAM] Evolution of Emergent Behavior using
> Genetic Programming
>
> > OK, I'm being dumb as a rock. Can other search techniques be
> > considered self-organizing? If not, what is that makes a GA
> > self-organizing but (say) gradient descent not?
>
> It's not you, Robert -- It's gradient descent that is as dumb
> as a rock ;-)
>
> We've been punting the criteria for self-organizing
> algorithms around for a few years now and I can't say that
> I've seen necessary and sufficient conditions defined out there yet.
>
> Intuitively, I would say greedy gradient descent by a single
> computational entity/agent is not self-organizing. I think
> its interesting, though, that I would classify learning by
> back propagation in a neural network as an instance of
> self-organization when Greg Stone's chapter in the early UCSD
> PDP books (Stone, 1986) showed back propagation (delta rule)
> to be a form of gradient descent. So what's the difference here?
>
> Firstly, I think you need a *collection* of algorithms to
> constitute a system that is capable of self-organization.
> I'll call the things in the collections agents but you can
> call them PDEs :-)
>
> Secondly, I suspect it has to do with the transfer of
> information of the asymmetries of the environment (the
> function to be optimized) into the structure of the agent
> system. I don't see this happening in simple gradient descent.
>
> In self-organizing systems, agents are constrained (informed)
> from their natural degrees of freedom (loss of symmetry) as
> the system evolves.
> Constraints can manifest themselves in environment-agent
> interactions, agent-agent interactions, or internal rules to
> the agents themselves.
>
> In the neural network example, information about the
> structure of the pattern to be classified is imported to
> weights on the edges of the neural network. This is a change
> on the agent-agent interaction. In the example of a single
> agent falling down hill, I don't see the importing of
> information into an agent's system structure - only work
> being done on the agent as it moves to a lower energy state.
> I wonder if we could move further on a continuum of
> self-organizing systems if we introduced history to the
> gradient-decent agent like what happens in simulated annealing...
>
> So to your question "are GAs self-organizing"? In the past,
> I've said no.
> But I could flip-flop as the definitions get clearer and we
> think of the structure of the environment being tranferred to
> lower the entropy of the genomes. Chris Adami has looked at
> mutal entropy measures like this for his Avida system and
> proposes it as a measure of complexity. So, in this context,
> maybe GAs are self-organizing.
>
> Eventually, perhaps concepts from nonequilibrium statistical
> mechanics will apply that center on generalized definitions
> of heat and work and make all this more rigorous. (Maybe,
> we'll have to goad Eric S. into doing the appropriate maths
> and sums.) For now, it probably is just a bunch of jargon
> babble :-) It's certainly murky in my head. It reminds me of
> asking "are viruses alive?" when we don't have a good
> definition of life yet...
>
> -Steve
>
> Stone, G. O. (1986). An analysis of the delta rule and the
> learning of statistical associations. In Rumelhart, D. E. &
> McClelland, J. L.(Eds.), Parallel Distributed Processing,
> Vol. I (pp.444-459). Cambridge,
> Massachusetts: MIT Press.
>
>
>
>
>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org
>
>
>

[Robert Holmes]

Dan, Steve - thanks for your posts. Good to know that there are good reason
for me not understanding this stuff. You should write a paper someday ;-)

Steve - I like your intuitive "collection of algorithms". I wonder though -
just because we have a collection of computing entities (ants or replicating
genes) does that mean we have a collection of algorithms? In the examples
I've seen, the entities are all running essentially the same algorithm, it's
just that the parameters of each agent's instance of the algorithm is
different. Now if they were *genuinely* different algorithms (one ant is
using gradient descent, one gradient descent with memory, one talking with
its neighbours to create some form of local collaborative simplex algorithm
etc.) things could get kinda fun. Anyone done any work on this?

Robert

> -----Original Message-----
> From: Stephen Guerin [mailto:[hidden email]]
> Sent: Monday, March 14, 2005 9:10 PM
> To: Friam
> Subject: RE: [FRIAM] Evolution of Emergent Behavior using
> Genetic Programming
>
> > OK, I'm being dumb as a rock. Can other search techniques be
> > considered self-organizing? If not, what is that makes a GA
> > self-organizing but (say) gradient descent not?
>
> It's not you, Robert -- It's gradient descent that is as dumb
> as a rock ;-)
>
> We've been punting the criteria for self-organizing
> algorithms around for a few years now and I can't say that
> I've seen necessary and sufficient conditions defined out there yet.
>
> Intuitively, I would say greedy gradient descent by a single
> computational entity/agent is not self-organizing. I think
> its interesting, though, that I would classify learning by
> back propagation in a neural network as an instance of
> self-organization when Greg Stone's chapter in the early UCSD
> PDP books (Stone, 1986) showed back propagation (delta rule)
> to be a form of gradient descent. So what's the difference here?
>
> Firstly, I think you need a *collection* of algorithms to
> constitute a system that is capable of self-organization.
> I'll call the things in the collections agents but you can
> call them PDEs :-)
>
> Secondly, I suspect it has to do with the transfer of
> information of the asymmetries of the environment (the
> function to be optimized) into the structure of the agent
> system. I don't see this happening in simple gradient descent.
>
> In self-organizing systems, agents are constrained (informed)
> from their natural degrees of freedom (loss of symmetry) as
> the system evolves.
> Constraints can manifest themselves in environment-agent
> interactions, agent-agent interactions, or internal rules to
> the agents themselves.
>
> In the neural network example, information about the
> structure of the pattern to be classified is imported to
> weights on the edges of the neural network. This is a change
> on the agent-agent interaction. In the example of a single
> agent falling down hill, I don't see the importing of
> information into an agent's system structure - only work
> being done on the agent as it moves to a lower energy state.
> I wonder if we could move further on a continuum of
> self-organizing systems if we introduced history to the
> gradient-decent agent like what happens in simulated annealing...
>
> So to your question "are GAs self-organizing"? In the past,
> I've said no.
> But I could flip-flop as the definitions get clearer and we
> think of the structure of the environment being tranferred to
> lower the entropy of the genomes. Chris Adami has looked at
> mutal entropy measures like this for his Avida system and
> proposes it as a measure of complexity. So, in this context,
> maybe GAs are self-organizing.
>
> Eventually, perhaps concepts from nonequilibrium statistical
> mechanics will apply that center on generalized definitions
> of heat and work and make all this more rigorous. (Maybe,
> we'll have to goad Eric S. into doing the appropriate maths
> and sums.) For now, it probably is just a bunch of jargon
> babble :-) It's certainly murky in my head. It reminds me of
> asking "are viruses alive?" when we don't have a good
> definition of life yet...
>
> -Steve
>
> Stone, G. O. (1986). An analysis of the delta rule and the
> learning of statistical associations. In Rumelhart, D. E. &
> McClelland, J. L.(Eds.), Parallel Distributed Processing,
> Vol. I (pp.444-459). Cambridge,
> Massachusetts: MIT Press.
>
>
>
>
>
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9AM @ Jane's Cafe
> Lecture schedule, archives, unsubscribe, etc.:
> http://www.friam.org
>
>
>