Evolving machine learning algorithms from scratch

Technology News | July 28, 2020

By Rich Pell

Designed to automate the design of machine learning (ML) algorithms, AutoML has until now focused on constructing solutions by combining sophisticated hand-designed components. However, an alternative approach to using such hand-designed components in AutoML, say Google researchers, is to search for entire algorithms from scratch.

“This is challenging because it requires the exploration of vast and sparse search spaces, yet it has great potential benefits — it is not biased toward what we already know and potentially allows for the discovery of new and better ML architectures,” says the researchers. “By analogy, if one were building a house from scratch, there is more potential for flexibility or improvement than if one was constructing a house using only prefabricated rooms. However, the discovery of such housing designs may be more difficult because there are many more possible ways to combine the bricks and mortar than there are of combining pre-made designs of entire rooms.”

As a result, say the researchers, early research into algorithm learning from scratch focused on one aspect of the algorithm – to reduce the search space and compute required, such as the learning rule – and has not been revisited much since the early 90s. However, in a new paper, Google researchers say they have demonstrated that it is possible to successfully evolve ML algorithms from scratch.

Their approach, called AutoML-Zero, starts from empty programs and, using only basic mathematical operations as building blocks, applies evolutionary methods to automatically find the code for complete ML algorithms. Given small image classification problems, say the researchers, the method rediscovered fundamental ML techniques such as two-layer neural networks with back-propagation, linear regression, and the like, which have been invented by researchers throughout the years – a result that demonstrates the plausibility of automatically discovering more novel ML algorithms to address harder problems in the future.

In their work, the researchers used a variant of classic evolutionary methods to search the space of algorithms. These methods have proved useful in discovering computer programs since the 80s. Their simplicity and scalability, say the researchers, makes them especially suitable for the discovery of learning algorithms.

In this case, a population is initialized with empty programs. It then evolves in repeating cycles to produce better and better learning algorithms. At each cycle, two (or more) random models compete and the most accurate model gets to be a parent. The parent clones itself to produce a child, which gets mutated – i.e., the child’s code is modified in a random way, which could mean, for example, arbitrarily inserting, removing or modifying a line in the code. The mutated algorithm is then evaluated on image classification tasks.

In contrast to much previous AutoML work, the AutoML-Zero setup makes the search space very sparse — an accurate algorithm might be as rare as one in 1012 candidates. This is due to the granularity of the building blocks provided to the algorithm, which include only basic operations such as variable assignment, addition, and matrix multiplication.

“In such an environment, a random search will not find a solution in a reasonable amount of time, yet evolution can be tens of thousands of times faster, according to our measurements,” say the researchers. “We distributed the search on multiple machines that occasionally exchange algorithms (analogous to migration in real life). We also constructed small proxy classification tasks on which to evaluate each child algorithm, and executed this evaluation with highly optimized code.”

Despite the sparsity, the evolutionary search discovers more complex and effective techniques as time passes. Initially, the simplest algorithms appear, which represent linear models with hard-coded weights. In time, stochastic gradient descent (SGD) is invented to learn the weights, in spite of the gradient itself not having been provided as a building block. Though flawed at first, SGD gets fixed relatively quickly, starting a series of improvements to the prediction and learning algorithm.

“Within our toy scenario,” say the researchers, “the process discovers several concepts known to have been useful to the research community. In the end, our approach manages to construct a model that outperforms hand-designs of comparable complexity.”

The best evolved algorithm produced by the method includes techniques such as noise injection as data augmentation, bilinear model, gradient normalization, and weight averaging, and the improvement over the baseline also transfers to datasets that are not used during search. Through more experiments, say the researchers, they show that it is possible to guide the evolutionary search by controlling “the habitat” — i.e., the tasks on which the evolutionary process evaluates the fitness of the algorithms.

So far, say the researchers, they consider their work to be preliminary.

“We have yet to evolve fundamentally new algorithms, but it is encouraging that the evolved algorithm can surpass simple neural networks that exist within the search space,” say the researchers. “Right now, the search process requires significant compute. As the coming years scale up available hardware and as the search methods become more efficient, it is likely that the search space will become more inclusive and the results will improve. We are excited at the prospects of discovering novel machine learning algorithms as we further our understanding of AutoML-Zero.”

For more, see “AutoML-Zero: Evolving Machine Learning Algorithms From Scratch.”

Google AI