---
page-title: Minor thesis - Structural degeneracy in neural networks
title: Structural degeneracy in neural networks
---

::: {style="text-align: center"}
Minor Thesis `<br>`{=html} *submitted in partial fulfilment of*
`<br>`{=html} *the requirements for the degree of* `<br>`{=html} Master
of Computer Science `<br>`{=html} *at* `<br>`{=html} The University of
Melbourne

**Matthew Farrugia-Roberts**

Supervised by [**Daniel Murfet**](http://therisingsea.org/) and **Nic
Geard**

Submitted: October, 2022. Minor revision: December, 2022.
:::

## Thesis

![](mthesis.png)

Download: Full text [PDF](mthesis.pdf) (3.2MB).

## Abstract

Neural networks learn to implement input--output functions based on
data. Their ability to do so has driven applications in many task
domains. However, a solid theoretical understanding of deep learning
remains elusive. For example, classical theoretical frameworks fail to
account for the performance of large neural networks despite their
capacity to implement overly complex functions. There is a need for
basic theoretical research clarifying the relationship between
structure, function, and complexity in neural networks.

For almost all neural networks, the relationship between structure and
function is well understood: all parameters implementing a given
function are related by simple operations such as exchanging the weights
of units. However, for the remaining *degenerate* neural networks, there
are additional parameters implementing the same function. Since some of
these additional parameters correspond to smaller, less complex neural
networks, degenerate neural networks are positioned to play a crucial
role in understanding neural network learning. However, prior work
investigating neural network structures has largely emphasised the
generic non-degenerate case.

In light of this situation, I present a comprehensive theoretical
investigation of structural degeneracy in a simple family of neural
networks (single-hidden-layer biased hyperbolic tangent networks). I
develop an algorithmic framework for analysing degeneracy, including an
ideal measure of degeneracy called the *rank* of a neural network (the
minimum number of hidden units required to implement an identical
function). Using this framework, I characterise the class of
functionally equivalent parameters including in the degenerate case,
extending prior work that has only considered the non-degenerate case. I
show that in the degenerate case, the functional equivalence class is
piecewise linear path connected. Moreover, I study a measure of
approximate degeneracy, the *parametric approximate rank,* based on
proximity to low-rank parameters. Drawing on computational complexity
theory, I show that determining such proximity is an NP-complete
problem.

The insights into structural degeneracy developed in this thesis have
the potential to clarify topics of current interest in deep learning.
More broadly, this thesis lays a foundation for future work developing
efficient measures of degeneracy and empirically investigating the role
of degeneracy in deep learning.

## Citation

BibTeX database entry:

    @mastersthesis{Farrugia-Roberts2022,
        title={Structural Degeneracy in Neural Networks},
        author={Farrugia-Roberts, Matthew},
        month=dec,
        year=2022,
        school={School of Computing and Information Systems,
            The University of Melbourne},
        url={https://far.in.net/mthesis},
    }

## Recorded talks

A talk at the [Singular Learning Theory & Alignment Summit,
2023](https://singularlearningtheory.com/2023)

-   "Hidden unit acrobatics: An introduction to swaps, flips, and other
    symmetries of singular networks and their applications". An
    intuitive-level overview of reducibility and main thesis results,
    plus important directions for future work. 45 minutes.
    \[[youtube](https://www.youtube.com/watch?v=BZaMNAhMgX0)\]
    \[[interactive
    notebook](https://hidden-unit-acrobatics.far.in.net/)\]

A series of three \~90-120 minute improvised talks at
[metauni](https://metauni.org/)'s [singular learning theory
seminar](https://metauni.org/slt/), presenting some of the key results
in the thesis.

-   Part 1: Overview of thesis. Three perspectives on degeneracy.
    Reducibility and reduction algorithms.
    \[[youtube](https://youtu.be/KwI-O8VKVv4)\]
-   Part 2: Rank and algorithms. Parametric approximate rank. Statement
    of hardness theorem. \[[youtube](https://youtu.be/eBdm1pPGsco)\]
-   Part 3: Bounding parametric approximate rank (PAR). PAR is NP.
    Reduction from SAT to PAR (sketch half of proof).
    \[[youtube](https://youtu.be/FngNdKxCIuY)\]

An earlier talk in the same series.

-   Part 0: Preliminary results on piecewise linear path connectivity of
    the functional equivalence class of reducible parameters.
    \[[youtube](https://youtu.be/WBiFFIhGIZM)\]

TODO: Upload and link a couple of other related talks.

## Colophon

Typeset with LaTeX.

Fonts include Computer Modern, BOONDOX fraktur, and Ralph Smith Formal
Script (`\usepackage[frak=boondox,scr=rsfs]{mathalfa}`).

Most figures drawn with TikZ, and some with pgfplots.

## Errata

Please contact me if you find any errors.

Known errors:

-   Page 38 (pdf page 43). After the list, "so w is reducible" should
    read "so w is non-minimal". Oops!
-   Page 42 (pdf page 47). The final paragraph of the proof of theorem
    3.39 is incorrect. The subparameters to which I apply Sussmann's
    result are not necessarily irreducible, they may satisfy
    reducibility condition (i) (this happens when the outgoing weight
    vectors of some unit have some zero components). However, the proof
    can be recovered since no units can have an outgoing weight vector
    with *all* units zero, and the required transformation can be
    constructed by piecing together those from the different
    subnetworks. A corrected proof is provided in a forthcoming
    conference paper (preprint [on
    arXiv](https://arxiv.org/abs/2305.05089)).
-   Page 90 (pdf page 94). In step (3) of the list, "approximately zero
    incoming weight" should read "approximately zero outgoing weight".
    Oops!
-   Page 91 (pdf page 95). Algorithm 6.10, line 10. The
    less-than-or-equal comparison operation should be a greater-than
    operation. Oops!
-   Reference to Amari *et al.,* (2017). That should actually be 2018.
    There are probably some other typos in the reference list, as many
    reference details were completed by hand.