Self-Delimiting Neural Networks
Juergen Schmidhuber
cs.NE
2012-09-29
SLIM nets add a halt neuron so each episode traces only used connections; unused weights stay out of search. The 2012 report contains no experimental numbers.
An RNN weight matrix is a program. A sparse enough net whose units implement nonlinear AND and NAND gates can simulate a conventional microprocessor, so in principle an RNN is a general computer.
Asymptotically optimal program search (AOPS) had still never been applied to RNNs. Classic AOPS searches sequential self-delimiting programs: when the instruction pointer hits an unused address, a new instruction is requested online and appended; a halt instruction ends the run. Halting programs form a prefix code. In 2012, RNN training meant gradient descent or evolution. Matrix-multiply implementations still touched every weight, including connections that never fired. Overfitting was handled by pre-wired regularizer terms whose relative weights were a guess. Schmidhuber also wanted these nets as solvers for PowerPlay, a framework that invents the easiest still-unsolvable task from scratch. Ordinary RNNs do not carve the task space into weakly coupled modules.
A SLIM NN adds a dedicated halt neuron and switches to threshold activations, or winner-take-all inside ordered groups. Most units stay silent most of the time, which is how a program gets to choose its own length at runtime.
An episode spreads activation from the input neurons. Outputs may change the environment, which may return new inputs. The episode ends when the halt neuron lights up, or when a search-imposed time cap $t{lim}$ is hit. The weights on connections used at least once are the program.
Procedure Spread keeps three lists (old, new, trace) for neurons used in the last two steps and connections used at least once. Untouched outgoing edges are never read. Resetting the net costs no more than the episode that just ran. The thought experiment is a sparse net with a trillion connections, a billion neurons, and a thousand outgoing edges each: a single computation may light up a tiny fraction, and a dense matrix multiply is multiplying air.
Any learning algorithm must skip unused weights. Prefixes constrain suffixes, so a weight change early in an episode decides which later weights are even considered. Tentative changes therefore happen online during spreading. Growth uses the same hook: the first time a never-defined connection is touched, the learner may assign a nonzero weight and the effective topology grows by that edge.
Each connection stores the list of tasks that used it. After a candidate weight change, only the union of those lists needs to be re-evaluated; performance on every other task is guaranteed unchanged.
Universal SLIM NN Search is Levin search on these traces. Each candidate gets a share of search time proportional to its probability. If some unknown program solves a size-$k$ problem and verifies the answer in at most $f(k)$ steps, the whole search is $O(f(k))$. The practical search is depth-first in prefix space with stack backtracking, the same pattern as the 2004 Optimal Ordered Problem Solver (OOPS).
After a success the bias can shift. For each used connection, count how often source and target were both 1 on successive steps (yes) versus source 1 and target 0 (no). $\Delta=(\mathrm{yes}-\mathrm{no})/n$ lies in $[-1,1]$. A learning rate $\eta$ raises or lowers the probability of the current weight according to the sign of $\Delta$. Negative $\Delta$ shrinks that probability; positive $\Delta$ grows it. It is a Hebb rule written on a distribution.
The negative log of a trace's probability is the Huffman length of that program. Short, fast, and high-probability are the same quantity, so Occam's razor sits inside the time budget rather than as an extra term on the objective.
On the 3-D multiprocessor hardware imagined at the time, each connection carries a constant cost, readable as wire length. Adding $\sum$ length $\times$ uses to the objective pushes subtasks onto physically nearby subsets of neurons. Universal Search already accounts for those costs in the time bound, so the penalty does not need a separate hyperparameter.
This is a technical report, not an experimental paper. Section 4 says the first experiments were underway inside PowerPlay and would appear separately. There are no SLIM NN numbers on any public benchmark.
Error rates quoted in the text belong to other IDSIA nets from 2009–2012. They show that RNNs already worked on real tasks; they are not SLIM results:
| Source | Metric | Number | SLIM? |
| MNIST 2012 multi-column deep net | error | 0.23% | no |
| IJCNN 2011 traffic signs | error | 0.56% (humans 1.16%) | no |
| ICDAR 2009 handwriting | rank | LSTM RNNs won French, Arabic, and Farsi tracks | no |
Two theoretical claims are stated cleanly. Universal SLIM NN Search is near-bias-optimal and asymptotically optimal. The prefix-code property holds in a resettable deterministic environment; if the environment cannot be reset, environmental inputs have to be counted as part of the program.
For people still running hill-climbing or neuro-evolution in 2012, the constraint is concrete: the search space shrinks from the full weight matrix to the connections actually used. For anyone now working on sparse activation, conditional compute, or mixture-of-experts, Spread's "only touch lit edges" is familiar. There was no GPU kernel for it then.
Do not treat this as a drop-in trainer. Threshold units kill backpropagation, and Levin search still explodes in weight space. The contribution is a shared notation for Kolmogorov complexity, algorithmic probability, and neural nets, plus a principled alternative to regularizers: let the net pick its own number of free parameters per task.
The PowerPlay section is closer to later curriculum and modularity work. Preferring new tasks whose validity check is cheap is an implicit reward for not touching many old weights, so the task space splits into weakly coupled regions on its own.
The author deferred experiments. As of this report there are no public classification or control numbers, so there is no evidence that self-selected size actually controls overfitting.
Threshold and winner-take-all activations make self-delimiting easy and gradients impossible. That is a different training path from the LSTM and convolutional nets that were already winning contests.
The prefix-code argument needs a resettable deterministic environment. Physical robots and streaming data do not satisfy it.
The trillion-connection speedup is a thought experiment: never implemented, never timed. 3-D hardware and wire-length penalties were a forecast. There was no such chip in 2012.
The $O(f(k))$ bound hides a large constant from enumerating prefixes. OOPS reduced that constant with depth-first search and stack backtracking. This paper does not report a measured search time for the SLIM version.