CAP6938 Neuroevolution and Developmental Encoding Non-Neural NEAT and Closing RemarksOutlineComplexification is a General ConceptComplexification Does Not Mean Optimizing Random Dimensions From a SetThen What Does it Mean?ExampleExample 2Protecting Innovation is a General ConceptSpeciation Protects InnovationGeneral Concepts Means They Don’t Have to Apply to a Neural NetworkNovel Phenotype: Cellular Automata2D Cellular AutomataNeighborhood RulesCan It Do Anything Useful?Assessing PerformanceComplexifying Cellular AutomataSlide 17Even More Abstract Complexification SolutionConclusionNE & DE: What Have We LearnedWhat Is Its Significance?Where is the Field?Next Topics: Technical topics in implementing complexifying evolutionary systems and presenting results.CAP6938Neuroevolution and Developmental Encoding Non-Neural NEAT andClosing Remarks Dr. Kenneth StanleyOctober 30, 2006Outline•Complexification is a general concept•Protecting innovation is a general concept•Therefore, they can apply to anything without a defined dimensionality•Example: Cellular AutomataComplexification is a General Concept•Solving a smaller version of a problem and expanding the solution•Making a rough estimate and refining it•Building a structure piece by piece•Elaboration of a pre-existing conceptComplexification Does Not Mean Optimizing Random DimensionsFrom a Set•Example: 10-dimensional search space•Now hold d2 through d10 constant and search d1 •Once you get a good value for d1, start searching both d1 and d2 together, and so on•This is not complexification–It is a naïve search assuming independent variables–Subject to simple deception–Usually won’t work 10987654321,,,,,,,,, ddddddddddThen What Does it Mean?•Complexification means increasing information about the solution–(Optimizing d1 does not increase general information about the solution)•Initial dimensions are a complete solution on their own (nothing is held at zero)•Complexification means finding the dimensionality of the solution is part of the problem•A neural network can have any number of weight dimensions and solve the same problem•Most “dimensions” outside the current structure have no meaning on their ownExample•3 dimensions•Is dimension 2372 held at zero?•What exactly is dimension 2372?–It depends on how the other 2371 dimensions turn out to relate to each other–It is undefined; it doesn’t exist: •Not like d10 in prior example, which always exists•Complexification is searching infinite undefined dimensions, or rather, it is not performing search in the usual sense. It is increasing information.123Example 2•Problem: Find an expression of this function•Complexification says start with a very low dimensional approximation as accurate as possible in its space•Red line: 2-dimensional estimate y=mx+b–Now we could add new terms and refine the estimate–Analogous to bending the line like a rubber band for each new dimension added–New estimate does not necessarily need exactly the same term “mx+b”xyProtecting Innovation is a General Concept•New ideas need time to mature•Children need time to grow up•Ph.D. students need room to make mistakes•Bigger often means slower, but not stupider•Einstein was not the teacher’s pet–The long run is what matters–If we kicked him out early, we’d all loseSpeciation Protects Innovation•An “idea” is represented as a niche•The niche is a local, protected competition•One niche does not directly compete with another•Only the absolute worst are purged after sufficient opportunity is spentGeneral Concepts Means They Don’t Have to Apply to a Neural Network•Complexification and protection of innovation go hand in hand•In order to elaborate, one must protect potential elaborations•In order to grow one must have roomNovel Phenotype: Cellular Automata•Set of pixels that change over time according to neighborhood rules•The Game of Life is a familiar example of 2D cellular automataFrom: http://www.bitstorm.org/gameoflife/2D Cellular Automata•Pixels are in a line instead of a plane•Change over time can be represented as a vertical graph:timeFrom: Melanie Mitchell, James P. Crutchfield, and Rajarshi Das, "Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work", In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96), Russian Academy of Sciences (1996).Neighborhood Rules•Next state for pixel determined by pixels in its neighborhood within some radius:From: Melanie Mitchell, James P. Crutchfield, and Rajarshi Das, "Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work", In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96), Russian Academy of Sciences (1996).2(2r+1) bits per rule tableCan It Do Anything Useful?•Maybe it can compute functions•Popular task: Fill the line with whichever color is in the majority (Density Classification)•Successful attempts: (r=3; 128 bits/genome)Assessing Performance•Measure % correct over unbiased distribution of many initial conditions•Best performance is 86% on 149 pixels with r=3 (Juillé and Pollack 1998) using coevolution of rules and initial conditions•Could we do a lot better than 86%?•Maybe with complexificationComplexifying Cellular Automata•How?Complexifying Cellular Automata•How? Expand the neighborhood•Neighborhood doesn’t need to be symmetric or even contiguous•Is this really complexification?–Yes: Unexpressed dimensions are undefined without knowing all the dimensions–The initial rules give us only a little information, but good information–The dimensions of the search space are the bits of the rule, not the neighborhood positions–The rule includes the neighborhood positions, i.e. there is structure. Position is a historical marker in this case.0000011010101110Even More Abstract Complexification Solution•A very wide neighborhood could be input into a neural network that computes a function of those inputs and outputs the next value for the bit in the middle•The network that computes the function can complexify………Evolved TopologyConclusion•Complexification and protection of innovation may allow more complex and therefore powerful neighborhood functions to evolve (maybe beat 86% by using with coevolution?)•Complexification and protection of innovation may