Neural Algorithmic Reasoning

Algorithms and Deep Learning

Algorithms are pervasive in modern society—from elevators, microwave ovens and other household equipment to procedures for electing government officials. Algorithms allow us to automate and engineer systems that reason. Remarkably, algorithms applied in one domain—such as a microwave oven—may be slightly adjusted and deployed in a completely different domain—such as a heart pacemaker (e.g., a control algorithm such as PID). That is not to say that you would expect to be able to safely run a microwave oven using a pacemaker (or vice versa) without modification, but the same recipe underlies both constructions.

An undergraduate textbook on algorithms (Cormen et al., 2009) will cover fewer than 60 distinct algorithms. A subset of these will serve as the useful basis for someone’s life-long career in software engineering in almost any domain. Part of the skill of a software engineer lies in choosing which algorithm to use, when, and in combination with what else. Only rarely will an entirely novel algorithm be warranted.

This same algorithmic basis could also help us solve one of the hardest problems in deep learning: generalisation. Deep learning methods learn from data and are then deployed to make predictions or decisions. The core generalisation concern is: will it work in a new situation? In other words, from training data, will the deep learning method generalise to the new situation. Under certain assumptions, guarantees can be given but so far these are in simple cases.

Algorithms, on the other hand, typically come with strong general guarantees. The invariances of an algorithm can be stated as a precondition and a postcondition, combined with how the time and space complexity scales with input size. The precondition states what the algorithm will assume is true about its inputs, and the post-condition will state what the algorithm can then guarantee about its outputs after its execution. For example, the precondition of a sorting algorithm may specify what kind of input it expects (e.g., a finite list of integers allocated in memory it can modify) and then the postcondition might state that after execution, the input memory location contains the same integers but in ascending order.

Even with something as elementary as sorting, neural networks cannot provide guarantees of this kind: neural networks can be demonstrated to work on certain problem instances and to generalise to certain larger instances than were in the training data. There is no guarantee they will work for all problem sizes, unlike good sorting algorithms, nor even on all inputs of a certain size.

Algorithms and the predictions or decisions learnt by deep learning have very different properties—the former provide strong guarantees but are inflexible to the problem being tackled, whilst the latter provide few guarantees but can adapt to a wide range of problems. Understandably, work has considered how to get the best of both. Induction of algorithms from data will have significant implications in computer science: better approximations to intractable problems, previously intractable problems shown to be tractable in practice, and algorithms that can be optimised directly for the hardware that is executing them with little or no human intervention.

Already several approaches have been explored for combining deep learning and algorithms. Inspired by deep reinforcement learning, deep learning methods can be trained to use existing, known algorithms as fixed external tools (Reed and De Freitas, 2015; Li et al., 2020). This very promising approach works well—when the existing known algorithms fit the problem at hand. This is somewhat reminiscent of the software engineer wiring together a collection of known algorithms. An alternative approach is to teach deep neural networks to imitate the workings of an existing algorithm, by producing the same output, and in the strongest case by replicating the same intermediate steps (Graves et al., 2014; Kaiser and Sutskever, 2015; Kurach et al., 2015; Veličković et al., 2020). In this form, the algorithm itself is encoded directly into the neural network before it is executed. This more fluid representation of the algorithm allows learning to adapt the internal mechanisms of the algorithm itself via feedback from data. Furthermore, a single network may be taught multiple known algorithms and abstract commonalities among them (Veličković et al., 2019), allowing novel algorithms to be derived. Both of these approaches build atop known algorithms. In the former case, new combinations of existing algorithms can be learnt. Excitingly, in the latter case, new variants or adaptations of algorithms can be learnt, as the deep neural network is more malleable than the original algorithm.

At present, in computer science, a real world problem is solved by first fitting the problem to a known class of problems (such as sorting all numbers), and then an appropriate algorithm chosen for this known problem class. This known problem class may actually be larger than that exhibited by the real world problem, and so the chosen algorithm may be suboptimal in practice (for example, the known problem class may be NP-hard, but all real world examples are actually in P, so can be solved in polynomial time). Instead, by combining deep learning and algorithms together, an algorithm can be fit directly to the real world problem, without the need for the intermediate proxy problem.

Algorithms in the real world

To elaborate on how neural networks can more directly be fused with algorithmic computation, we will take a step back and consider the theoretical motivation for designing algorithms.

Algorithms can represent the purest form of problem-solving. The Church-Turing thesis states that a problem of any kind is computationally solvable if and only if there exists an algorithm that solves it when executed on the model of computation known as a Turing machine. Thus, solvability of problems necessitates existence of suitable algorithms for them.

Algorithms reason about problems in an abstract space, where the inputs conform to stringent pre-conditions. Under this lens, it becomes far easier to guarantee correctness (in the form of stringent post-conditions), provide performance guarantees, support elegant and interpretable pseudocode, and perhaps most importantly, draw clear connections between problems that may be otherwise hard to relate.

The theoretical utility of algorithms is unfortunately at timeless odds with the practical motivation for designing them: to apply them to real-world problems. Clear examples of both the appeal of algorithmic reasoning and the apparent dissonance it has with practical applications were known as early as 1955—within a write-up from Harris and Ross (Harris and Ross, 1955), which studied the bottleneck properties of railway networks.

By studying the problem in an abstract space (railway junctions being nodes in a graph, and edges between them endowed with scalar capacities, specifying the limits of traffic flow along edges), the authors formalised the bottleneck finding task as a minimum-cut problem. Observing the problem in this abstract space made it easily relatable to the (otherwise seemingly unrelated) maximum-flow problem. In fact, studying the problem under this lens not only enabled a strong theoretical connection between these two problems, it also spearheaded decades of research into efficient algorithms in flow networks.

However, there is a fundamental limitation to this kind of abstraction. In order for all of the above to be applicable, we need to “compress” all of the complexity of the real-world railway network into single-scalar capacities for every edge. And, as the authors themselves remark:

“The evaluation of both railway system and individual track capacities is, to a considerable extent, an art. The authors know of no tested mathematical model or formula that includes all of the variations and imponderables that must be weighed.* Even when the individual has been closely associated with the particular territory he is evaluating, the final answer, however accurate, is largely one of judgment and experience.”

This remark may be of little importance to the theoretical computer scientist, but it has strong implications on applying classical algorithms on natural inputs, that hold to this day. If data is manually converted from raw to abstract form, this often implies drastic information loss, making our problem no longer accurately portray the dynamics of the real world. Hence the algorithm will give a perfect solution, but in a potentially useless setup. Even more fundamentally, the data we need to apply the algorithm may be only partially observable—in which case, the algorithm could even be rendered inapplicable.

In order to circumvent this issue, we may recall that the “deep learning revolution” occurred with neural networks replacing the use of manual feature extractors from raw data, causing significant gains in performance. Accordingly, as our issues stem from manually converting complex natural inputs to algorithmic inputs, we propose applying neural networks in this setting as well.

Algorithmic bottlenecks and neural algorithm execution

Directly predicting the algorithmic inputs from raw data often gives rise to a very peculiar kind of bottleneck. Namely, the richness of the real world (e.g. noisy real-time traffic data) still needs to be compressed into scalar values (e.g. edge weights in a path-finding problem). The algorithmic solver then commits to using these values and assumes they are free of error—hence, if we don’t have sufficient data to estimate these scalars properly, the resulting environment where the algorithm is executed does not accurately portray the real-world problem, and results may be suboptimal, especially for low data setups.

To break the algorithmic bottleneck, it would be preferential to have our neural network consistently producing high-dimensional representations. This means that the computations of our algorithm also must be made to operate over high-dimensional spaces. The most straightforward way to achieve this is replacing the algorithm itself with a neural network—one which mimics the algorithm’s operations in this latent space, such that the desirable outputs are decodable from those latents. The recently resurging area of algorithmic reasoning (Cappart et al., 2021, Section 3.3.) exactly studies the ways in which such algorithmically-inspired neural networks can be built, primarily through learning to execute the algorithm from abstractified inputs.

Algorithmic reasoning provides methods to train useful processor networks, such that within their parameters we find a combinatorial algorithm that is (a) aligned with the computations of the target algorithm; (b) operates by matrix multiplications, hence natively admits useful gradients; (c) operates over high-dimensional latent spaces, hence is not vulnerable to bottleneck phenomena and may be more data-efficient.

The blueprint of neural algorithmic reasoning

Having motivated the use of neural algorithmic executors, we can now demonstrate an elegant neural end-to-end pipeline which goes straight from raw inputs to general outputs, while emulating an algorithm internally. The general procedure for applying an algorithm $A$ (which admits abstract inputs $\bar{x}$) to raw inputs $x$ is as follows (following Figure 1):

Learn an algorithmic reasoner for $A$, by learning to execute it on synthetically generated inputs, $\bar{x}$. This yields functions $f,P,g$ such that $g(P(f(\bar{x})))\approx A(\bar{x})$. $f$ and $g$ are encoder/decoder functions, designed to carry data to and from the latent space of $P$ (the processor network).

One area where this blueprint had already proved useful is reinforcement learning (RL). A very popular algorithm in this space is Value Iteration (VI)—it is able to solve the RL problem perfectly, assuming access to environment-related inputs that are usually hidden. Hence it would be highly attractive to be able to apply VI over such environments, and also, given the partial observability of the inputs necessary to apply VI, it is a prime target for our reasoning blueprint.

Specifically, the XLVIN architecture (Deac et al., 2020) is an exact instance of our blueprint for the VI algorithm. Besides improved data efficiency over more traditional approaches to RL, it also compared favourably against ATreeC (Farquhar et al., 2017), which attempts to directly apply VI in a neural pipeline, thus encountering the algorithmic bottleneck problem in low-data regimes.

Conclusion

We demonstrated how neural algorithmic reasoning can form a rich basis and core for learning novel and old algorithms alike. At first, algorithmic reasoners can be bootstrapped from existing algorithms using supervision of their internal workings, and then subsequently embedded into the real world input/outputs via separately trained encoding/decoding networks. Such an approach has already proved fruitful across a range of domains, such as reinforcement learning and genome assembly. It is our belief that neural algorithmic reasoning will allow for applying classical algorithms on inputs that substantially generalise the preconditions specified by their designers, uniting the theoretical appeal of algorithms with their intended purpose.

References