ISSonDL2019 Neuroevolution

Transcript

1. International Summer School on Deep Learning Neuroevolution workshop Michał Karzyński Intel AI
2. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 2 Hello, my name is… Michał Karzyński Software Architect at Intel AI @postrational http://karzyn.com
3. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 3 Neuroevolution Neuroevolution uses evolutionary algorithms to generate artificial neural networks, parameters, topology and rules. Stated goals of neuroevolution research: • Evolve complex AI systems • Democratize AI AutoML Neural Architecture Search Hyperparameter tuning Neuroevolution
4. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 4 Biological inspirations
5. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 5 Biological inspiration - Evolution • Natural selection – survival of the fittest • Genes for best fitness will be passed onto the next generation • Mutation – random changes can introduce new versions of genes which increase fitness • Speciation – over time new specialized species will arise Image source: Pixabay
6. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 6 Biological inspiration – Sexual reproduction • Offspring produced by two individuals • Each parent provides half of the genes • During meiosis two chromosomes undergo crossover to exchange homologous genetic material • Crossover creates genetic diversity Image source: Wikipedia
7. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 7 Biological inspiration – Development • Genetic information is not expressed directly • Genes encode a program for the development of the organism • Transcription factors control which genes are expressed in which cells, allowing reuse of genes at different stages and different places • Similar sets of genes under a different developmental program can create different species Image source: Wikipedia
8. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 8 Biological inspiration – Neurons and brain structure • Inspiration for the entire field of Deep Learning • Geometric topological arrangement of neurons in the visual cortex lines up with the grid of photoreceptive cells in the retina • Somatosensory representation of the body in the brain exhibits a similar geometry to the body itself Image source: Wikipedia
9. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 9 NeuroEvolution of Augmenting Topologies (NEAT)
10. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 10 NeuroEvolution of Augmenting Topologies (NEAT) Research started in 2002, primarily led by Kenneth O. Stanley and Risto Miikkulainen at The University of Texas at Austin. NEAT algorithm features: • Allows crossover • Protects innovation through speciation • Starts with minimal genome (allow evolution to add only needed features) Stanley, K. O., & Miikkulainen, R. (2002). Evolving Neural Networks through Augmenting Topologies. Evolutionary Computation, 10(2), 99–127.
11. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 11 NEAT Genetic Encoding • Encode nodes and connections • Use historical markers
12. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 12 NEAT Mutations • Change weight • Add/remove connection • Add/remove node
13. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 13 NEAT Crossover • Uses historical markers to align genomes
14. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 14 NEAT Speciation • Protect innovation by performing selection within a “species” of similar individuals
15. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 15 NEAT Ablation study • Evaluated on double pole balancing task (commonly used for reinforcement learning) • Evaluations: average number of individuals needed to complete task • Failure: no result within 1000 generations
16. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 16 Hypercube-based NEAT (HyperNEAT)
17. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 17 Hypercube-based NEAT (HyperNEAT) Builds on work on NEAT, starting around 2009. HyperNEAT extends NEAT by adding: • Mechanism simulating biological development • Indirect evolution – the developmental program is evolving, not the ANN itself • Substrate – ability to take advantage of spatial geometry of the problem domain Stanley, K. O., D’Ambrosio, D. B., & Gauci, J. (2009). A Hypercube-Based Encoding for Evolving Large-Scale Neural Networks. Artificial Life, 15(2), 185–212. Gauci, J., & Stanley, K. O. (2010). Autonomous Evolution of Topographic Regularities in Artificial Neural Networks - Neural Computation, 22(7), 1860–1898.
18. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 18 HyperNEAT Indirect encoding • Compositional pattern producing network (CPPN) produces an ANN by defining connections in a geometric substrate • NEAT is applied to evolve the CPPN
19. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 19 HyperNEAT Evolved connectivity patterns
20. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 20 HyperNEAT Connectivity Concepts
21. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 21 HyperNEAT Checkers • A CPPN calculates the weight of connections between the board and a hidden layer (AB) or the hidden layer and the output layer (BC) • Output of ANN is the score of the move to this position
22. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 22 HyperNEAT Compression • A relatively small CPPN can encode a much larger ANN
23. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 23 Deep Neuroevolution
24. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 24 Deep Neuroevolution • Builds on the success of deep neural networks (AlexNet, VGG, GoogLeNet, ResNet, etc.) • Steps away from building a custom feed-forward neural network edge-by-edge • Genes now represent layers of a deep neural network and their attributes (e.g.: type: Convolution, attributes: strides, padding, output channels, etc.) • Mutations can add or remove layers, change their type or attribute values • Combines two search algorithms: genetic algorithms for architecture search and backpropagation for training
25. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 25 CoDeepNEAT Research on NEAT continues into the Deep Neuroevolution era at Cognizant, an AI startup. DeepNEAT - NEAT approach is used, but each node in a chromosome now represents a network layer. CoDeepNEAT – two populations of modules and blueprints are evolved separately using DeepNEAT. The blueprint chromosome is a graph where each node contains a pointer to a particular module species. For fitness evaluation, the modules and blueprints are combined to create an ANN. Miikkulainen, R. et al. (2017). Evolving Deep Neural Networks.
26. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 26 CoDeepNEAT Modules and blueprints
27. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 27 CoDeepNEAT CIFAR-10 • 92.7% accuracy on CIFAR-10 • Training time was limited, so evolutionary pressure created fast training networks (120 epoch to converge)
28. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 28 CoDeepNEAT Custom LSTM
29. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 29 Neuroevolution research at Google Teams at Google Brain and DeepMind are working on neural architecture search methods based on genetic algorithms. In 2017 they published an influential paper on evolving image classifiers and achieved 94.6% accuracy on CIFAR-10 with no human participation in neural network design. Real, E. et al. (2017). Large-Scale Evolution of Image Classifiers
30. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 30 Real, E. et al. 2017 Mutations
31. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 31 Real, E. et al. 2017 Evolution
32. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 32 Real, E. et al. 2017 Results
33. International Summer School on Deep Learning 33 Hierarchial representations Inspired by reusable modules in human-created networks such as Inception, ResNet, etc. Build up more complex structures from simpler ones. Results in much faster evolution than a non-hierarchial representation. Similar in concept to modules and blueprints of CoDeepNEAT. Liu, H., Simonyan, K., Vinyals, O., Fernando, C., & Kavukcuoglu, K. (2017). Hierarchical Representations for Efficient Architecture Search
34. International Summer School on Deep Learning 34 Hierarchial representations
35. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 35 Google AutoML using Reinforcement Learning (NAS) Zoph, B., & Le, Q. V. (2016). Neural Architecture Search with Reinforcement Learning.
36. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 36 Reinforcement Learning vs Neuroevolution Real, E. et al. (2019). Regularized Evolution for Image Classifier Architecture Search
37. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 37 Function-preserving mutations New research performed at IBM, based on work by Chen et al. (ICLR, 2016), who proposed function-preserving transformations for transfer learning. Chen, T., Goodfellow, I., & Shlens, J. (2016). Net2Net: Accelerating Learning via Knowledge Transfer
38. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 38 Function-preserving mutations Martin Wistuba at IBM described the following function-preserving transformations: • Layer Widening – increase the number of filters in a convolutional layer • Layer Deepening – deepen a network by inserting an additional convolutional or fully connected layer • Kernel Widening – increase the kernel size in a convolutional layer by padding with zeros • Insert Skip Connections – initialize connection weights to produce zeros • Branch Layers – insert branching into network Wistuba, M. (2019). Deep learning architecture search by neuro-cell-based evolution with function-preserving mutations.
39. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 39 Function-preserving mutations He used them to create a set of function-preserving mutations: • Insert Convolution • Branch and Insert Convolution • Insert Skip • Alter Number of Filters • Alter Number of Units • Alter Kernel Size • Branch Convolution
40. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 40 Function- preserving mutations Results • Duration in GPU days
41. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 41 Function- preserving mutations Results
42. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 42 Takeaways • AutoML is a powerful technique, starting to outperform human ability • Neuroevolution is a viable approach to AutoML • Research in the are is ongoing and likely to generate results in near future • Computational costs are very high and put a limit on research
43. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 43 Takeaways • Deep Neuroevolution combines evolutionary search with weight training by backpropagation • Lamarckian evolution – passing on learned weight to the next generation improves search performance • Function-preserving mutations make Lamarckian evolution possible • Efficient methods perform multi-level evolution: smaller modules and larger networks
44. International Summer School on Deep Learning Michał Karzyński - Neuroevolution 44 Interesting research questions • What is the best genome encoding for Neuroevolution? • What other mutations can be added to the search? • Can “substrate geometry” be used in Deep Neuroevolution (like in HyperNEAT)? • Will a training network (RL) approach be more efficient than evolutionary search? • We need good open-source frameworks for Deep Neuroevolution research