Machine Learning with Arbitrary Iterative Computation Graphs

Inspiration:

Ever since I learned about the existence of neural networks about 6 years ago I've had the idea of wanting to try to make an arbitrary graph learn. Now that I am at the end of my undergraduate studies I have decided to make this idea happen. I originally thought of this as an uninformed attempt to generalize neural networks, however in practice, I don't think this is what I have achieved. I still hope that the flexible nature of this system allows for some insights into general purpose problem solving.

What it is:

Breakdown:

• Arbitrary: any topology, any size 2d array with any value
• Iterative: outputs take n steps to generate
• Computation: nodes represent operations
• Graph: graph

Purpose

• Augment existing machine learning techniques with a flexible, general purpose method

Notable Classes and Files

In graph.py:

• OperationGraph: A container that holds operations
• Operation: Any operation that given an nd array return an nd array or scalar In generator.py:
• num_funcs: list of defined functions that operate on an nd array and return an nd array. More functions can be defined by the user.
• red_funcs: list of defined functions that operate on an nd array and reduce them into a scalar. More functions can be defined by the user.
• generate_genome(length): creates a random n x 5 numpy array that represents a graph.
• generate_graph(genome): creates a graph from a genome using a set of rules
• mutate(genome, gamma): mutates a genome by a factor of gamma

What it does

Attempts to learn a computation graph that solves a given problem in n steps.

Training Methodology

Graphs are represented by an n by 5 matrix of numbers between 0 and 1 and then optimized using the following genetic algorithm:

• Select the top 20% of agents and compute the mean and standard deviation of their genomes.
• For each agent in the top 10%, cross their genome with the best performing genome.
• For each agent below the top 10% and above the bottom 22.5%, set their genome to a mutation of the average genome computed above with a mutation factor of the standard deviation computed above.
• For each agent in the bottom 22.5%, randomize their genomes.

How I built it

• Efficient planning followed by minimal sleep and then inefficient debugging of unplanned issues.

Challenges we ran into

• Doing arbitrary operations on arrays of arbitrary length and dimensions required a bit of engineering to prevent jagged arrays and other cases where computation would be ambiguous. Solution: padding arrays before computations. bounding results of operations and replacing NaNs to prevent NaN propagation.
• Python int type is arbitrarily large. Larger than a C long which resulted in rare crashes. Solution (?) clip the results of numeric and reduction operations between 2^31 and 2^31 - 1.
• State space for graph genome in training is not only discontinuous, but also arbitrarily large based on genome size. This just means that the learning process is slow and more time is required to optimize it.
• Lost time on small typos that completely blocked development and learning.
• Inconsistency of environments between my desktop and laptop breaking things
• Other things I can't remember because it's all a blur

Accomplishments that we're proud of

• The system demonstrates the capability to learn tasks, and once trained is fairly computationally cheap.
• I managed to make and submit something in time!

What we learned

• I learned about many limitations of numpy I was unaware of
• I learned how to use vectorized openAI gym
• I learned some new techniques for genetic algorithms such as CrossEntropy
• I now have a better understanding of my own capabilities and limits when under a time constraint

What's next for Machine Learning with Arbitrary Iterative Computation Graphs

• Rewrite everything in C and add threading.
• Dive deeper into understanding its use cases including strengths and weaknesses.
• Experiment with this technique in other more complex tasks such as factorization.
• Add a way to train computation graphs by using a neural network to estimate a graph's genome for a given task instead of searching the genome space directly.

Built With

• gym
• numpy
• python
• pyvis