Accumulation of Adaptations
I think this represents the results we should work towards for the Living Machines 2013 exhibit.
The closest literature that tries to accumulate adaptations in the way we do is the options framework I think (and MAXQ), but they have not demonstrated transfer learning. A review of transfer learning appears
here by Taylor and Stone (2009). I summarise some aspects of that article here.
Q1. What knowledge to transfer?
a. Low-level knowledge: i. <s, a,r, s'> instances, action-value function (Q), policy (pi), full task model (model), prior distributions (pri).
b. High-level knowledge: i. What subset of actions A to use in which situations. ii. partial policies or options (basically what we're doing with the archive I think), iii. rules or advice, iv. important features for learning (e.g. perceptual atoms), v. proto-value functions?, vi. shaping rewards (subgoal functions suitable for full goals, subtask definitions).
Examples of Hierarchical Transfer Learning (Including only tasks that can be done in a Jolly Jumper)
Primitive Tasks
1. Agent learns to bounce on a cushion using its knees and ankles.
2. Agent learns to swing forwards and backwards on a cushion using its knees and ankles.
3. Agent learns to rotate around the vertical axis using its knees and ankles.
Permitting variability operators a. and b. will allow new molecule types to come into existence that may be more suitable for recombination. If these operators are evolved along with a recombination operator, then molecule types that suit those operators will evolve.
Purely Sequentially Composite Tasks
1. Bounce (1) for 5 seconds then Swing (2) for 5 seconds.
2. Bounce (1) for 5 seconds then Rotate (3) for 5 seconds.
3. Swing (2) for 5 seconds then Bounce (1) for 5 seconds.
4. Swing (2) for 5 seconds then Rotate (3) for 5 seconds.
5. Rotate (3) for 5 seconds then Bounce (1) for 5 seconds.
6. Rotate (3) for 5 seconds then Swing (2) for 5 seconds.
Purely Parallel Composite Tasks
1. Bounce + Swing
2. Bounce + Rotate
3. Swing + Rotate
at the same time. Fitness is the sum of both primitive fitnesses.
Methods of Transfer
1.
FIXED CHAIN the timing of sub-actions. A -(delay = 3)--> B. with fixed delays.
2.
CONDITIONAL CHAIN the timing of sub-actions based on termination conditions A --(terminate)-->B.
3.
MERGE two compartments with equal priority, such that all motor atoms controlling the same motors now average their motor commands in the motor buffer.
Transfer method 1 would be expected to be able to satisfy the purely sequential composite tasks, if it was possible to execute compartment (x) followed by compartment (y). Currently, our archive retrieval system does not permit combining distinct whole compartments in this way. Neither does it permit the termination condition based method of sequencing whole compartments relative to each other. This is a failing of the current EROS algorithm.
Parallel task recombination would be expected to be helped by (3) the equal priority Merge operator.
Primitive Compartment Mechanisms and Variability Operators.
1. A large DMP molecule moves knees and ankles taking sensory input from joints and accelerometers.
2. Two small reflex molecules operate ankle and knee movements as a function of FSRs on that leg.
TO DO: Currently, by limiting the molecules to the two above types, we severely restrict the kinds of knowledge transfer that can occur by recombination.
a. Structural changes should be permitted, e.g. removal and formation of edges. Removal is first order, and addition is zeroth order. This will result in the formation of new molecule structures.
b. Mutation of sensor identities should be permitted. Motor identities should also be mutable, within the subset of permitted motors i.e. knees and ankles only.
c. Priorities should also be allowed to mutate.
d. Recombination between compartments in the population (and between compartments in the archive and population should allow molecules to be added (with/without replacement).
e. These operators should be tested with the primitive tasks above.
Notes:
NEAT Stanley and Miikkulainen (2002) Evolutionary Computation 10(2):99-127
Neuroevolution of Augmented Topologies attempts to answer these questions. These have been the same questions we've been asking so we should look to see if they have solved all our problems for us. Lets hope they have, otherwise we might need to do some more work. Their questions were...
(1) Is there a genetic representation that allows disparate topologies to cross over in a meaningful way?
(2) How can topological innovation that needs a few generations to be optimized be protected so that it does not disappear from the population prematurely?
(3) How can topologies be minimized throughout evolution without the need for a specially contrived fitness function that measures complexity?
Topology andWeight Evolving Artificial Neural Networks
(TWEANNs) are of two types. Direct and indirect encoding.
Direct
1. Binary connectivity matrix [crossover requires equal sized matrices, crossover has competing conventions problem], (Dasgupta and McGregor, 1992)
2. Nodes contain incoming and outgoing edge list (Pujol and Poli, 1997). [Subgraph swapping is possible] "
Subgraph swapping is representative of a prevailing philosophy
in TWEANNs that subgraphs are functional units and therefore swapping them
makes sense because it preserves the structure of functional components. However, we
cannot be sure whether the particular subgraphs being combined in PDGP are the right
ones to create a functional offspring."
Indirect
1. Gruau's cellular encoding (I programmed this fully in C during my MSc thesis I remember now!). [Biased search space, utility of bias not known.]
Q(1) Is there a genetic representation that allows disparate topologies to cross over in a meaningful way?
A1. Competing Conventions Problem (CROSSOVER OF DIFFERENT TOPOLOGY CONTROLLERS)
[EROS SUFFERS FROM THIS CURRENTLY]
The biological solution is homology (lining up of equivalent genes) prior to crossover, done by RecA. Neat uses the HISTORICAL lineage knowledge to provide direct evidence of common ancestry from which true homology can be determined, to constrain crossover
[Can this really work well, because there could have been functional divergence. Is this the best that can be done, is direct structural analysis really not possible? How does RecA work?]
" Tracking the historical origins requires very little computation. Whenever a new gene appears (through structural mutation), a global innovation number is incremented and assigned to that gene. The innovation numbers thus represent a chronology of the appearance of every gene in the system."
" When crossing over, the genes in both genomes with the same innovation numbers are lined up. These genes are called matching genes. Genes that do not match are either disjoint or excess , depending on whether they occur within or outside the range of the other parent’s innovation numbers. They represent structure that is not present in the other genome. In composing the offspring, genes are randomly chosen from either parent at matching genes, whereas all excess or disjoint genes are always included from the more fit parent."
Q(2) How can topological innovation that needs a few generations to be optimized be protected so that it does not disappear from the population prematurely?
A2. Protecting Innovation (NEW STRUCTURAL MUTANTS) with Speciation
[EROS SUFFERS FROM THIS CURRENTLY]
"
Frequently, adding new structure initially causes the fitness of a network to decrease" " By adding new genes to the population and sensibly mating genomes representing different structures, the system can form a population of diverse topologies. However, it turns out that such a population on its own cannot maintain topological innovations. Because smaller structures optimize faster than larger structures, and adding nodes and connections usually initially decreases the fitness of the network, recently augmented structures have little hope of surviving more than one generation even though the innovations they represent might be crucial towards solving the task in the long run. The solution is to protect innovation by speciating the population"
Adding new nodes and connections can reduce fitness suddenly before it's parameters have had a chance to optimise, so new topological additions must be protected/ This is achieved by fitness sharing based on genetic similarity [?]
Solution: Genomes are clustered on the basis of evolutionary similarity. Individuals in the same species must share fitness as in Goldberg and Richardson, 1987 (explicit fitness sharing).
NEAT ALGORITHM OVERVIEW
1. Initialise population with a set of non-random MINIMAL initial topologies to reduce the number of parameters that have to be searched at the same time.
[Instead of penalising larger networks like Zhang and Muhlenbein, 1993), they start with a minimal topology and grow it carefully.]
Some parmeters from an example run below...
2. Genetic Encoding [Designed to allow homologous crossover.] Linear representations of network connectivity.
"Genomes are linear representations of network connectivity (Figure 2). Each genome includes a list of connection genes , each of which refers to two node genes being connected. Node genes provide a list of inputs, hidden nodes, and outputs that can be connected. Each connection gene specifies the in-node, the out-node, the weight of the connection, whether or not the connection gene is expressed (an enable bit), and an innovation number , which allows finding corresponding genes (as will be explained below)."
[I do not like the fact that connectivity is not a self-organizing consequence of atom structures, which makes them fully PSS like.]
MUTATIONS:
"In the add connection mutation, a single new connection gene with a random weight is added connecting two previously unconnected nodes. In the add node mutation, an existing connection is split and the new node placed where the old connection used to be. The old connection is disabled and two new connections are added to the genome. The new connection leading into the new node receives a weight of 1, and the new connection leading out receives the same weight as the old connection. This method of adding nodes was chosen in order to minimize the initial effect of the mutation."
[Vera's idea as well, in our system. But I'm not sure this way of adding nodes is the best. What is the justification for it in our system? How to add new nodes in our system in order to make smooth operators?]
IMPLICATIONS FOR EROS FROM NEAT.
1.
Introduce historical markings to atoms. [We have an issue with edges which are currently encoded IN atoms, rather than as separate genes to which a separate historical marking could be assigned. Is this a problem? Consider the entities to which historical markings, and hence species definition, could be assigned, and perhaps how the definition of a species (and inter-individual distance) might itself be evolvable, because surely it is rather arbitrary how the 3 parameters that define distance is NEAT are chosen. COULD BETTER SPECIES EVOLVE OVER TIME IF THE DEFINITION OF SPECIES DISTANCE WAS ITSELF EVOLVABLE< OR NOT?
2. Initialize with a more minimal topology, e.g. only a sensor and motor atom with a linear transform.
3. [Protect innovation] Introduce speciation based on historical similarity and niching (based on markings).
4. Make the initial parameters of a new structural variant likely to be not too detrimental, e.g. [neutral addition of variation (e.g. insertion of an identity transform between sensor and motor atom). Atoms and their variation operators should be designed such that they have this property.]
5. Increase parameter mutation rate (allowed by speciation!, not otherwise, see paragraph above..
