4
$\begingroup$

I'm working on my own implementation of NEAT algorithm based on the original 2002 paper called "Efficient Reinforcement Learning through Evolving Neural Network Topologies" (by Kenneth O. Stanley and Risto Miikkulainen). The way the algorithm is designed it may generate loops in connection of hidden layer. Which obviously will cause difficulties in calculating the output.

I have searched and came across two types of approaches. One set like this example claim that the value should be calculated like a time series usually seen in RNNs and the circular nodes should use "old" values as their "current" output. But, this seems wrong since the training data is not always ordered and the previous value has nothing to do with current one.

A second group like this example claim that the structure should be pruned with some method to avoid loops and cycles. This approach apart from being really expensive to do, is also against the core idea of the algorithm. Deleting connections like this may cause later structural changes.

I my self have so far tried setting the unknown forward values as 0 and this hides the connection (as whatever weight it has will have no effect on the result) but have failed also for two reasons. One is my networks get big quickly destroying the "smallest network required" idea and also not good results.

What is the correct approach?

$\endgroup$
2
$\begingroup$

NEAT does not employ a feed forward concept and also it does not take any special action to avoid loops.

Network is evaluated in non-recursive model. The only non-deterministic loop, the evaluation has is the loop for activating all the outputs. Pseudo code is something like this,

Until all the outputs are active
    for all non-sensor nodes
        activate node
        sum the input
    for all non-sensor and active nodes
        calculate the output

NOTE1: You can use a defensive mechanism (like a counter) to avoid a infinite loop

NOTE2: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero.

This is the note from the author of NEAT about identifying loops,

Note that checking networks for loops in general in not necessary and therefore I stopped writing this function

bool Network::integrity()

$\endgroup$
  • $\begingroup$ I don't think that we are on the same page. If node A has a connection to node B and node B has a connection to node A you can't get the input of node A because it depends on it self. You added a note to stop infinite loops but how would you calculate the initial iteration? $\endgroup$ – Emad Dec 16 '19 at 11:22
  • $\begingroup$ @Emad, I have added another note regarding how NEAT handles the dependent value issue. That is: When summing the input, outputs of nodes which were at least evaluated/calculated once are considered, otherwise their outputs are assumed to be zero. $\endgroup$ – Morpheus Dec 18 '19 at 3:41
  • $\begingroup$ For example, suppose both A and B has links from sensors (actual input layer), in the first iteration of outer loop, A's input summing disregards B's output since B is not evaluated yet. And B does the same since A's output is not evaluated yet. Then both A and B calculate their outputs in the second inner loop. Then in the second iteration of outer loop, both A and B consider each other's outputs from first iteration. So you see this continues without an issue. Let me know if you need more clarification $\endgroup$ – Morpheus Dec 18 '19 at 4:02
  • $\begingroup$ Ok great. Now I understand. Can you please cite any reference for this. This is same as the first approach that I mentioned in the OP. But I fail to verify this in literature. $\endgroup$ – Emad Dec 18 '19 at 4:55
  • 1
    $\begingroup$ Literature fails to express all these implementation details I guess. However next valid reference we can take is the original source code, which is nn.cs.utexas.edu/?neat-c $\endgroup$ – Morpheus Dec 18 '19 at 13:24
1
$\begingroup$

You can use a feed forward style network, so that every node outputs to a higher node except output nodes. This will eliminate connection loops.

$\endgroup$
  • $\begingroup$ "higher" in what sense? Innovation number? or something else? $\endgroup$ – Emad Aug 13 '19 at 6:24
  • $\begingroup$ Yes, identification number or innovation number. $\endgroup$ – Terry T. Aug 13 '19 at 13:06
  • $\begingroup$ Ok but innovation number is not actually a measure of being later in the feed network. i.e. a new connection can form before one of the existing ones yet take higher innovation number. $\endgroup$ – Emad Aug 14 '19 at 14:17
  • $\begingroup$ Whoops it is actually this: a new connection is formed only when the first node is is closer to the input then the second node, or the fewest number of connections to get to the input is greater in the second node. Another question simailar to this can be found here ai.stackexchange.com/questions/6231/… $\endgroup$ – Terry T. Aug 14 '19 at 20:43
  • $\begingroup$ I see. Yet in the literature it's a bit different. I appreciate your solution. $\endgroup$ – Emad Aug 15 '19 at 19:05

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.