Revisiting "Self-Structuring Machine Learning Models"
A rushed pandemic-era thesis finally gets its missing second act: we revisit "Self-Structuring Machine Learning Models" with corrections, modern commentary, and the missing experiment.
Introduction
A few years ago, I wrote a thesis titled "Self-Structuring Machine Learning Models" (inline here or search Harvard DASH). The thesis was reviewed by two reviewers who provided it with "High Honors" and "Honors" ratings, but my honest assessment is that it is embarrassingly incomplete. I unfortunately completed this work in a rush, over the course of a few weeks rather than the typical 6-12 months, at the height of the pandemic.
In light of some recent developments since then, I've decided to revisit this work in a focused retrospective and provide a missing experiment that runs in your browser. Mixtures of experts have been common in language models for years, and recent reporting indicates that recurrent architectures have made their way into the latest generation of LLMs (1, 2, 3) and are discussed in academic literature as well (Geiping, Jonas, et al.; Saunshi, Nikunj, et al.; Ekbote, Chanakya, et al.).
Below, I give a brief, high-level discussion, at times with different terminology and framing than the original paper, for clarity.
The Core Intuition
The intuition is best structured in two parts: (A) Use a Group of Small Models Instead of One Large One; (B) Make the Small Models Smaller by Reusing Parameters Between Them.
Use a Group of Small Models Instead of One Large One
Some model architectures have a comparative advantage for some data. The paper uses Definition 3.2.1: $\delta$-Passable With Probability $\epsilon$ to define this formally, with $\delta$ roughly corresponding to a measure of model fit, and $\epsilon$ as the probability that training an architecture $M$ results in a model $\hat M$ that meets that level of quality.
An extreme toy example is encoded multi-modal data – concatenated text embeddings or image data, though for a given input you are not told which, only given the vector of a fixed length that encodes one or the other. An architecture with transformer blocks will likely fare better with the former, and a convolutional neural network better for the latter.
Train multiple small models with different architectures suited to different parts of your sample space; use a router to choose which one at runtime.
This is a natural next step. The paper suggests you train the router according to a classification objective, where the inputs are the examples from the training dataset, and their labels are the "optimal path" for that particular input – i.e. the routing decision on which models (in the paper, "units") to use for prediction. The paper suggests the "optimal path" label is the path with the best $\epsilon$ for the given data point, though later suggests using test loss instead to reduce computational complexity.
In the toy example, one would imagine this results in a dataset where input vectors with text embedding data are labeled with the path corresponding to the transformer blocks, and vectors with image data are labeled with the path corresponding to the convolutional network.
Make the Small Models Smaller by Reusing Parameters Between Them
The paper argues this can be done by reusing parameters between the different models available to the router. It calls these reusable parameterized modules "units."
One can begin to stretch the toy example further, although it becomes a bit far-fetched: imagine some of the images in the dataset are of text. You might have a transformer unit and a convolutional network unit, and for images of text, you'd want to run the convolutional unit and then the transformer unit. For non-text images, just the convolutional unit might do; for just text embedding inputs, a sequence of one or more iterations of the transformer unit would suffice.
With this enhancement, the router no longer just chooses a single model for an input, but rather a sequence of model units (convolutional network, transformer, etc.). Now, the term "path" makes more sense (though in hindsight, "sequence" would have been better), as the router chooses an appropriate chain of such units based on the input.
The Main Algorithm
The spirit of the main training algorithms (Algorithm 4 and Algorithm 5) is essentially as follows:
- Find the best "path" for each example in your dataset. Algorithm 4 chooses "optimal path" for an example via an $argmax$ (typo in PDF says $argmin$) over estimations of the $\epsilon$ metric for the datapoint, while Algorithm 5 just asks you to train each possible path once on the full data set, and then label the "best path" for your example as the path/sequence that produced the lowest loss under your test for that example.
- Repeatedly train each path/sequence of units only on examples for which the path was chosen as the "optimal path" for the example.
- Train the decision model on the "optimal path" dataset.
I skip some nuance, because in honesty, it neither helps in explanation nor matters in practice.
Problems
We will not go over every issue, but we'll cover some of the big ones:
There are no experiments.
Well, that is embarrassing. I ran out of time. I have one for you today – just scroll further.
The proposed training procedure is computationally troubling.
Both Algorithm 4 and Algorithm 5 require training each possible path in full to determine the "optimal path" per-example. Later, further training must occur on every path again for input examples for which it was designated the "optimal path." For a non-trivial number of units or a large unit parameter count, this becomes very expensive.
The definitions are sloppy.
Definition 2.4.1 calls the following quantity "total variation distance":
\[ \operatorname{DC}(D_1, D_2, T_e) = \left| \mathbb{E}_{(x,y)\sim D_1}\!\left[T_e(x,y)\right] - \mathbb{E}_{(x,y)\sim D_2}\!\left[T_e(x,y)\right] \right|. \]which is wrong because that would require it to be the supremum over all measurable tests $T: X \times Y \to [0, 1]$. Nonetheless, it can still be useful, just perhaps named as "discrepancy under fixed test".
Definition 3.2.1 is also internally inconsistent about whether $\epsilon$ is a per-example or distribution-level probability. The intent is the former, but the displayed definition includes $(x,y)\sim\mathcal{D}$ inside the probability, which makes $\epsilon$ average over both the sampled datapoint and the randomness of training. est_eps and the later path-selection procedure hold $(x,y)$ fixed and repeatedly train $M$. The intended per-example form would be:
and the corresponding distribution-level probability would be: $\mathbb{E}_{(x,y)\sim\mathcal{D}}[\epsilon_M(x,y)]$.
Definition 3.2.2 and Definition 3.2.3 define $\alpha$ and $\gamma$, but are somewhat reckless in failing to emphasize the independence assumptions across training runs.
Let's take the first as an example, which makes a jump from:
\[ \alpha = \int_x f_{\mathcal{D}:x}(x) \Pr\!\left( \left( x \text{ is not } \delta\text{-passable under each } \hat{M}_i \right)^C \right) \,dx \]to
\[ \alpha = \int_x f_{\mathcal{D}:x}(x) \left( 1 - \prod_{i=1}^{n_M} \left( 1-\Pr\!\left[P_{M_i,\delta,x}\right] \right) \right) \,dx \]Recall that we have $P_{M, \delta, x}$, which earlier was stated to refer to the event that training on model architecture $M$ for $S_{train}$ drawn at random results in a $\delta$-passable model, and previously $r$ was declared as a random string for the purposes of random initialization. Technically, there is no clear transgression yet, but it would be helpful to re-emphasize that the training set and initialization randomness are independently redrawn for each training run of $M_i$, i.e. $r_i \stackrel{\mathrm{iid}}{\sim} R, \qquad i=1,\ldots,n_M$ and $S_i \stackrel{\mathrm{iid}}{\sim} \mathcal{D}^n$. When $S_{train}$ is held fixed, only the $r_i$ are independently redrawn.
Likewise, the estimation algorithms for $\alpha$ and $\gamma$ should similarly clarify that each retraining uses independent draws of both $S_i$ (unless $S_{train}$ is fixed) and $r_i$.
Below I've added clarified versions of these definitions:
Revised definition · Section 3.2 Definition 3.2.2. $\delta$-Covering to Degree $\alpha$
Let $\mathcal{M} = \{M_i\}_{i=1}^{n_M}$ be a set of model archetypes. For each $M_i$, independently draw a training set $S_i$ and a random string $r_i$:
\[ S_i \stackrel{\mathrm{iid}}{\sim} \mathcal{D}^n, \qquad r_i \stackrel{\mathrm{iid}}{\sim} R, \qquad i = 1,\ldots,n_M. \]All training-set and random-string draws are mutually independent across $i$, and are independent of the evaluated data point $(x,y)$. Let
\[ \hat{M}_i = \operatorname{train}(M_i,S_i,r_i). \]For a fixed data point $(x,y)$, define the event that the trained instantiation of $M_i$ is $\delta$-passable by
\[ A_i(x,y) = \left\{ \left| T_e(x,y) - T_e\!\left(x,\hat{M}_i(x)\right) \right| < \delta \right\}. \]Write
\[ q_i(x,y) = \Pr_{S_i,r_i}\!\left[A_i(x,y)\right]. \]The distribution $\mathcal{D}$ is said to be $\delta$-covered by $\mathcal{M}$ to degree $\alpha$, where $\alpha$ is the expected probability that a data point is $\delta$-passable under at least one independently trained model:
\[ \alpha = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Pr\!\left( \bigcup_{i=1}^{n_M} A_i(x,y) \right) \right]. \]Because the training procedures are independent across model archetypes, this is equivalently
\[ \alpha = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ 1 - \prod_{i=1}^{n_M} \left( 1-q_i(x,y) \right) \right]. \]If a common training set $S_{\mathrm{train}}$ is held fixed, each model is instead trained using an independently drawn random string:
\[ r_i \stackrel{\mathrm{iid}}{\sim} R, \qquad \hat{M}_{i,S_{\mathrm{train}}} = \operatorname{train} \left( M_i, S_{\mathrm{train}}, r_i \right). \]Define
\[ q_{i,S_{\mathrm{train}}}(x,y) = \Pr_{r_i} \left[ \left| T_e(x,y) - T_e\!\left( x, \hat{M}_{i,S_{\mathrm{train}}}(x) \right) \right| < \delta \right]. \]The fixed-training-set covering degree is then
\[ \alpha_{S_{\mathrm{train}}} = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ 1 - \prod_{i=1}^{n_M} \left( 1-q_{i,S_{\mathrm{train}}}(x,y) \right) \right]. \]
Revised definition · Section 3.2 Definition 3.2.3. Separated $\delta$-Covering to Degree $\gamma$
Use the same independently trained model instantiations $\{\hat{M}_i\}_{i=1}^{n_M}$, passability events $A_i(x,y)$, and probabilities $q_i(x,y)$ defined above.
The distribution $\mathcal{D}$ is said to have a separated $\delta$-covering by $\mathcal{M}$ to degree $\gamma$, where $\gamma$ is the expected probability that a data point is $\delta$-passable under exactly one independently trained model:
\[ \gamma = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \Pr\!\left( \text{exactly one of } A_1(x,y),\ldots,A_{n_M}(x,y) \text{ occurs} \right) \right]. \]Because the training procedures are independent across model archetypes, this is equivalently
\[ \gamma = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \sum_{i=1}^{n_M} q_i(x,y) \prod_{\substack{j=1 \\ j\neq i}}^{n_M} \left( 1-q_j(x,y) \right) \right]. \]If a common training set $S_{\mathrm{train}}$ is held fixed and the random strings $r_i$ are independently redrawn for each model, the fixed-training-set separated covering degree is
\[ \gamma_{S_{\mathrm{train}}} = \mathbb{E}_{(x,y)\sim\mathcal{D}} \left[ \sum_{i=1}^{n_M} q_{i,S_{\mathrm{train}}}(x,y) \prod_{\substack{j=1 \\ j\neq i}}^{n_M} \left( 1-q_{j,S_{\mathrm{train}}}(x,y) \right) \right]. \]
The length of the bibliography is best suited for a middle school essay; extremely important existing work was missed.
This is the big one – a better review of existing literature would genuinely have helped and forced some hard questions about the usefulness of this complicated procedure. MoE (Mixture of Experts) was already a long-discussed idea; given this thesis was submitted in March 2021, the minimum would likely include:
- Jacobs et al.'s Adaptive Mixtures of Local Experts from 1991
- Bengio et al.'s Conditional Computation in Neural Networks for Faster Models from 2015
- Graves's Adaptive Computation Time for Recurrent Neural Networks from 2016
- Shazeer et al.'s Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer from 2017
- McGill and Perona's Deciding How to Decide: Dynamic Routing in Artificial Neural Networks from 2017
- Rosenbaum et al.'s Routing Networks: Adaptive Selection of Non-Linear Functions for Multi-Task Learning, first posted in 2017 and published at ICLR 2018
- Wu et al.'s BlockDrop: Dynamic Inference Paths in Residual Networks, first posted in 2017 and published at CVPR 2018
- Wang et al.'s SkipNet: Learning Dynamic Routing in Convolutional Networks, first posted in 2017 and published at ECCV 2018
- Lepikhin et al.'s GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding, first posted in 2020 and published at ICLR 2021
- Fedus et al.'s Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity, first posted in January 2021 and published in JMLR in 2022
This is a major miss, especially because sparse MoE offers a more direct approach to one of the thesis's central problems: allowing the task loss to train the router alongside the units or “experts” it selects. That leads us to ...
The hard-index routing formulation discards a useful task-loss gradient.
The thesis represents each routing choice from the decision model as a discrete next-unit index; the decision models are trained separately against the optimal target paths. However, the final task prediction loss cannot update the decision-only parameters $W_d$ through the hard routing choices because no continuous routing score participates in the forward prediction.
A common top-1 sparse-MoE formulation avoids this disconnect by retaining the selected expert's gate value in the forward. A learned router produces logits $z$ and converts them into probabilities $p$, and then selects the highest-probability expert.
\[ p = \operatorname{softmax}(z), \qquad i^* = \operatorname*{arg\,max}_{i} p_i. \]Only the selected expert $E_{i^*}$ is evaluated, but its output is multiplied by the selected routing probability $p_{i^*} = \max_i p_i$:
\[ h_{\mathrm{out}} = p_{i^*} E_{i^*}(h). \]The $argmax$ remains non-differentiable, but $p_{i^*}$ remains in the computation graph, so the task loss can backpropagate through it into router logits and weights.
The thesis instead separates router training from the task loss: it (1) optimizes the forward parameters along each example’s fixed “optimal path,” and then (2) trains the decision parameters separately to reproduce those paths.
Chapter 5 introduces much complexity to compensate for the lack of task-loss gradients in routing training. It offers the following explanation:
5.1 The Issue With Optimizing Sets of Units
Finding $\hat{U}^*$ may be extremely difficult in a computational sense, as it requires joint optimization over both the parameters responsible for generating activations, and the parameters responsible for deciding the next units in the chain.
Recall that parameters for an instantiated unit are given as $W = (W_f, W_d)$. $W_d$ are "decision-only" parameters that are "unused" by $\hat{M}_f$. By unused, we mean that:
\[ \hat{M}_f = M_f((W_f, W_d)) = M_f((W_f, W_d')) \qquad \forall W_d, W_d' \in \mathcal{W}_d \]The above statement highlights that the model function that results from the instantiation of $M_f$ is independent of the decision only parameters $W_d$ – swapping $W_d$ with any $W_d'$ still results in the same instantiated activationn model.
One reason why the joint optimization required for finding $\hat{U}^*$ is so difficult is because of the discontinuous nature of the decision model function $M_d$, which outputs an exact index of the next unit to be in the chain. This causes the entire instantiated model $\mathbf{\hat{U}}$ to be discontinuous as well. For instance, with just 3 instantiated units $\hat{U}_1$, $\hat{U}_2$ and $\hat{U}_3$, where $\mathbf{U}_1$ is always the input and $\mathbf{downcomp}(U_1) = \{U_2, U_3\}$, and chains are constrained to 2 units maximum, we have:
\[ \mathbf{\hat{U}}(x) = \begin{cases} \hat{M}_{2,f}(\hat{M}_{1,f}(x)) & \hat{M}_{1,d}(x) = 2 \\ \hat{M}_{3,f}(\hat{M}_{1,f}(x)) & \hat{M}_{1,d}(x) = 3 \end{cases} \]With such discontinuity, optimizing the parameters of $\mathbf{\hat{U}}$ is not possible with plain gradient descent. In this chapter, we present a way to break up the optimization into multiple optimizations over differentiable "pieces."
One of the reviewers rightfully questioned this part of the paper, and asked if the discrete decision model function could be approximated with a continuous one (and if not, suggested stochastic techniques like Monte Carlo parameter assignment).
There is no reward for shorter unit paths/sequences.
When choosing optimal paths for each example, the optimality of a path for an example only considers its accuracy under the model and does not reward shorter chains. For the experiment below, we add a minor tweak to address this.
The paper needs a proofread; the flow and terminology could be refined.
The shift from "small models can cover parts of your sample space" to "now we'll break models up into variable chains of units" was abrupt and poorly explained. There's a typo in the abstract, and typos elsewhere. "Path" should almost certainly be termed "sequence"; a reviewer complained that the use of the term "activation" is "mysterious" and I agree (I just meant the non-decision outputs of each unit). In its first nested for loop, Algorithm 4 uses $p$ before it is bound; deleting that line and replacing $M_p$ on the following line with $\mathbf{assembleArch}(U, p)$ fixes the immediate error.
The Missing Experiment
For all its flaws, the method in the thesis deserves an experiment, even if it's five years late. Experimentation has become very cheap with agents, and I was able to find a small motivating example, which is available as a live demonstration below.
The in-browser experiment below follows the method described in the thesis in spirit with a few tweaks, including:
- Shorter-path tolerance. Algorithm 5 chooses the minimum-loss path. We prefer a shorter sequence of units when its loss is within
0.1NLL of the minimum (you may change this in the settings). This is an imperfect heuristic since fewer units does not always mean greater efficiency, depending on the size of the units. A better choice would be to incorporate path cost directly into the objective used to select the target path. - Warm-started "activation" (i.e. non-decision) training. The paper randomly initializes the shared units after finding paths. By default, we copy the selected long-path network’s trained weights, then train along the assigned paths.
- Adaptive stopping of training and learning rates. The algorithms in the paper operate with a fixed number of iterations in training loops, whereas the experiment has a min and max number of epochs, with early-stopping criteria being 30 epochs without meaningful validation improvements after two learning rate reductions. Learning rate is halved after 10 stagnant epochs.
- Minibatch optimization. The pseudocode updates on individual observations. We aggregate gradients in 128-observation minibatches using Adam, initially at learning rate
0.003. - Single decision router rather than per-unit. The simulation uses a single decision model to decide the path/sequence of units rather than embedding a decision model at each unit to choose the next one. This changes the router architecture, but not the essential routing objective used in the experiment – the per-unit decision weights can be treated as a single jointly optimized parameter block, so our modification changes the router’s parameterization rather than the basic decision-training objective.
Original Paper
Find it on Harvard DASH or see rendered below.