Explainability and generalisation properties of artificial deep neural networks

Thesis

This thesis investigates two foundational questions about modern deep neural networks: (i) how to make their predictions explainable, and (ii) how to predict and understand their generalisation performance. We develop new theory and algorithms on formal methods for interpretability using computational complexity theory and logic; and new kernel, Bayesian and learning-theoretic perspectives on generalisation.

On explainability, we first study two canonical decision problems — Minimum Change Required and Minimum Sufficient Reason — used to compute cardinality-minimal contrastive and abductive explanations for neural network predictions. We prove that these problems remain intractable even for monotonic networks, but we show tractability is recovered under practical regularity assumptions (continuity everywhere and almost-everywhere differentiability of activations), yielding efficient greedy algorithms. Our analysis also uncovers new links to attribution methods via Aumann–Shapley values. We further introduce a logic-based framework that uses the fibring of modal logics to characterize the non-uniform expressiveness of certain classes of graph neural networks and transformer encoders, establishing along the way the exact correspondence between fibring of modal logics and fibring of neural networks. The goal of our fibring formalism is to lay the foundations for the development of a methodology with formal guarantees to extract interpretable logical rules from trained neural networks.

Ongeneralisation, we characterise properties of the Mercer spectrum of the empirical kernel associated with neural networks and leverage this viewpoint to analyse their Bayesian training, deriving an extension to the renormalisation theory of deep neural networks, and providing a new interpretation of the double-descent phenomenon. Using this perspective, we also show that adversarial examples can be, in interpolating regression settings, described as inputs that shift the empirical kernel’s spectrum toward near-zero eigenvalues; helping reconcile strong test performance with adversarial vulnerability. Finally, from the learning-theoretic viewpoint, we give sufficient conditions for algorithmic stability of minimum-norm interpolating deep ReLU networks: the existence of a stable prefix sub-network followed by at least one low-rank layer guarantees stability, linking generalisation to training-induced structures such as low rank and neural collapse.

Together, these contributions make several steps towards understanding how overparameterised networks can generalise on unseen data and how their decisions can be rendered intelligible.

Authors: El Harzli, O

• DOI: 10.5287/ora-z6we9kqk1
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: neural network explainability; neural network generalisation; machine learning theory; mathematics of deep learning; deep learning theory
• Subjects: Neural networks (Computer science); Deep learning (Machine learning)