Abstract
dc:description.abstractAlgorithms are easy... as long as they are kept in a textbook. In their universe, the world is often oversimplified and things are always represented in a simple numerical form. Sadly, this universe also does not always conform to the observable reality, the one we live in. Here, different factors play different roles and collapsing our reality into a couple of scalars is hardly achievable in a principled manner. Neural algorithmic reasoning has been recently proposed as a solution to this issue. It escapes the so-called scalar bottleneck problem by using specialised neural network architectures to execute the algorithm in higher-dimensional space. Mapping reality into this vectorial space is then left to the gradient-based optimisation techniques rather than the human operator. There are often cases, however, where we do not need to escape the scalar bottleneck. Sometimes, we may know precisely what algorithm we need and what its inputs should be. In other, worse scenarios, the task may already be hard enough so lifting the algorithm in higher-dimensional space does not make it any easier. This dissertation offers a different perspective into the field of neural algorithmic reasoning. It shows we do not have to be uncertain about how to represent reality in order to benefit from giving AI the knowledge of how algorithms operate. Throughout four different research works, I explore the utility of teaching algorithms to neural networks in cases where we do not break scalar bottlenecks. The first work demonstrates the utility of algorithmic reasoning in trajectory inference, the task of understanding how cells evolve during their lifetime. A neural model optimised to be a probabilistic proxy of the algorithm that often underlies existing approaches is integrated into a trajectory inference pipeline. Doing so gives access to a larger solution space, resulting in a competitive performance against other baselines in both synthetic and real-world data. The next chapter shows that neural algorithmic reasoning helps with computationally hard problems. Initialising a neural network with algorithmic information can help when solving NP-hard problems. The third chapter focuses on constraining algorithmic reasoners with an additional concept bottleneck in order to build interpretable algorithmic reasoners. An explainable-by-design graph neural network model, the first to utilise a concept bottleneck layer, is presented. With it, we are able to extract interpretable first-order logic rules for algorithms and also interfere with any mispredictions. Having provided sufficient evidence that bottlenecked algorithmic reasoning is useful, the last chapter focuses on what we can do to improve the accuracy and performance in the bottleneck regime itself. Previous approaches have always used a recurrent architecture, where each iteration of the neural network matches an iteration of the algorithm, essentially enforcing sequential execution. However, past experience shows that neural networks align better with parallel algorithms. Hence, I propose learning algorithms from a different perspective: since an algorithm’s solution is often an equilibrium, it is possible to turn neural algorithm execution into solving an equilibrium equation. This alignment to the equilibrium property increases overall accuracy and also brings substantial performance improvements to the inference speed of the trained model.
Degree
thesis:*- Name dc:type.qualificationname
- Doctor of Philosophy (PhD)
- Level dc:type.qualificationlevel
- Doctoral
- Grantor dc:publisher.institution
- University of Cambridge
- Year dc:date.issued
- 2024
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Georgiev, Dobrik
- Advisor dc:contributor.advisor
-
- Lio, Pietro
Subjects
dc:subject × 5Rights
dc:rightsIdentifiers
dc:identifier.*- DOI dc:identifier.doi
- https://doi.org/10.17863/CAM.115714
- OAI identifier oai:identifier
- oai:www.repository.cam.ac.uk:1810/379745