1
$\begingroup$

I'm trying to write my own implementation of NEAT and I'm stuck on the network evaluate function, which calculates the output of the network.

NEAT as you may know contains a group of neural networks with continuously evolving topologies by the addition of new nodes and new connections. But with the addition of new connections between previously unconnected nodes, I see a problem that will occur when I go to evaluate, let me explain with an example: Network

INPUTS = 2 yellow nodes
HIDDEN = 3 blue nodes
OUTPUT = 1 red node

In the image a new connection has been added connecting node3 to node5, how can I calculate the output for node5 if I have not yet calculated the output for node3, which depends on the output from node5?

(not considering activation functions)

node5 output =  (1 * 0.5) + (1 * 0.2) + (node3 output * 0.8)
node3 output =  ((node5 output * 0.7) * 0.4)
$\endgroup$
1
$\begingroup$

Consider the execution order, 5 will have an invalid value because it hasn't been set form 3 yet. However the second time around it should have a value set. The invalid value should falloff after sufficient training.

0 -> 5
1 -> 5
5 -> 2
2 -> 3
3 -> 4
3 -> 5
RESTART
0 -> 5
1 -> 5
$\endgroup$
  • $\begingroup$ Thanks for the reply, okay, I'm not sure if that answers my question, node3 cannot be calculated and node5 cannot be calculated, because they both depend on each other, how can you evaluate either node? Am I missing something? $\endgroup$ – Chris May 1 '18 at 20:15
  • $\begingroup$ I don't see how it can't be calculated. The first unresolved value you get is when calculating 5 (3 -> 5). Considering 0 has a value of .5, 1 has a value of .8, and 3 is unresolved, you may consider the following v5 = .5 * w0 + .8 * w1 + (3?) * w3 Where the 3? is an unresolved value. I think the hack here is to initialize it to zero so your equation becomes v5 = .5 * w0 + .8 * w1 + 0 * w3 Reduces to v5 = .5 * w0 + .8 * w1 This can calculate a value for 5 that can be used to calculate 2. You can then calculate 3 from 2. Then the next time 5 is calculated the value wouldn't be zero $\endgroup$ – Zakk Diaz May 1 '18 at 21:11
  • $\begingroup$ That makes sense, ty. $\endgroup$ – Chris May 1 '18 at 21:17
  • 3
    $\begingroup$ @Chris: NEAT does not usually allow backwards connections and loops AFAIK, connections are normally feed-forward. So you are creating more work for yourself here. In principle it can be made to work, and for all I know there are some notes on implementing recurrent NNs in NEAT somewhere. But you may want to consider starting with feed-forward only. $\endgroup$ – Neil Slater May 2 '18 at 7:31
  • 1
    $\begingroup$ @Chris: Actually, from re-reading the documentation, recurrent connections can be quite common and are not necessarily defended against in original NEAT implementations. It seems that the algorithm relies on weeding them out if they are not useful. $\endgroup$ – Neil Slater May 10 '18 at 7:18
1
$\begingroup$

I can think of two possible ways of enforcing NEAT to create a feed forward network. One elegant one and one a little more cumbersome one;

  1. Only allow the "add connection" mutation to connect a node with another node that have a higher maximum distance from an input node. This should result in feed forward network, without much extra work. (Emergent properties are great!)
  2. Run as you did and create a fully connected network with NEAT and then prune it during a forward pass. After creating the network, run through it and remove connections that try to connect to a node already used in the forward pass (example 3->5). Alternatively just remove unused input connections to nodes during the forward pass. Given how NEAT mutates, it should not be possible that you remove a vital connection and cut the the network in two. This property of NEAT make sure your signal will always be able to reach the output, even if you remove those "backwards pointing" connections.

I believe these should work, however i have not tested them.

The original NEAT paper assumed a feed forward ANN, even though its implementation as described would result in a fully connected network. I think it was just an assumption of the paradigm they worked in. The confusion is fully understandable.

$\endgroup$
0
$\begingroup$

In my implementation, I used a recursion system to calculate the output nodes. It works as follows:

  1. Assume a feed-forward network

Only allow the "add connection" mutation to connect a node with another node >that have a higher maximum distance from an input node. This should result in >feed forward network, without much extra work. (Emergent properties are great!)

  1. Define function x, a recursive function that takes in a node number
  2. Define function y, a second function that takes in a node and returns all the connections with that node as an output

In the recursive function:

  1. Call function y

  2. Call function x on function y outputs

  3. If the parameter for x is any input node, return the node value.

This was the most elegant way of implementing I could think of, and its a lot simpler than explicitly tracking all of the connections.

$\endgroup$
0
$\begingroup$

Hello chris i am also implementing this algorithm from scratch and the way i go about activating my mlp net is as follows: I instantiate a list of nodes(actives), this is set to all input nodes initially, i then pass that to a function that initializes an empty list(next actives) and proceeds to loop through each set of conns for each node in the actives list, it adds each "to" node from those connections to the "next actives) list unless its an output node or has already been activated, once all the "actives" list is looped through, i call the function again this time passing "next actives" as the actives list unless "next actives" is still empty after then i know the net has been fully activated.

in this scenario the connection from node three to node five would be evaluated but it would not be added to the next actives list because it had already been activated, preventing an infinite loop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.