Weight Agnostic Neural Networks

In plain words

Most neural networks have a fixed wiring diagram whose numbers, the weights, are trained, usually by gradient descent. This paper asks how much of a task the wiring alone can do. The search works on wirings and gives every connection the same single number, so what a network does depends on its structure and on that one value.

The search starts from very small, sparse networks. Each generation it adds a node, adds a connection or changes a node's activation function. It then tests each network with several values of the shared number. Networks that do well across those values, and have few connections, survive into the next generation. Nothing is trained.

The result is small networks that balance a pole, walk on two legs, drive a car from learned image features, and classify handwritten digits, all without learning their weights. Tuning the one shared value, or fine-tuning the individual weights, improves them further. Because the networks are small, their structure can be read.

TL;DR

• Evolves minimal network topologies without training any weight: every connection shares one value, and each topology is scored over six such values §3.
• Three topology operators (insert node, add connection, change activation), tournament selection, and Pareto ranking by mean reward and connection count §3.
• Author-reported, with one tuned shared weight: swing-up 723 ± 16 against 8 ± 1 for a fixed network; car racing 608 ± 161 against -37 ± 36; biped 261 ± 58 against -35 ± 23 tab. 1.
• MNIST: about 92% test accuracy, given in the introduction §1. The accuracy curves themselves are only in a figure this card does not transcribe fig. 6.
• The official release is Apache-2.0. It differs from the paper in the mutation probabilities, adds culling and elitism that the paper does not describe, and scales crowding distance in an unusual way [Paper vs code].

Problem

Neural architecture search usually judges a candidate architecture after training its weights, which makes each evaluation costly §2. The authors want architectures that already do the task with weights that are not trained at all §3. Sampling random values for every weight is impractical for all but the simplest networks, because the weight space is high-dimensional §3. Sharing one weight across all connections reduces the number of weight values to one. Testing a network over a handful of such values then gives a usable estimate of its performance §3.

The paper treats the architecture as carrying the bias toward a solution, in contrast with NAS, whose found architectures are only a better substrate for trained weights §3.

Method

The search follows four steps §3:

1. Create an initial population of minimal topologies.
2. Evaluate each network over several rollouts, using a different shared weight value at each rollout.
3. Rank the networks by performance and complexity.
4. Build a new population by varying the top-ranked topologies, chosen by tournament selection. Then repeat from step 2.

Initial population. Networks have input and bias nodes wired directly to output nodes, with no hidden nodes wann.py. Each connection starts enabled with probability prob_initEnable, which is set per task §3 app. A.4 wann.py.

Node activations. Inputs pass their value through unchanged. The bias node is fixed at 1 ind.py. Hidden nodes take one of the activation functions in the allowed set. Output activations are fixed per task: linear for biped, car racing and MNIST, tanh for the swing-up force, and a softmax over the ten outputs for MNIST config.py config.py config.py. The paper does not state the output activations.

Shared-weight evaluation. Every existing connection receives the same value w, and absent connections stay absent §3 task.py. The six values are -2, -1, -0.5, 0.5, 1 and 2 §3 task.py. The paper reports that values in [-2, 2] vary most, that values above 3 perform similarly, and that values near 0 are omitted because little signal reaches the output §3, footnote.

Scores. For each network, average the rollouts at each shared value. The fitness is the mean over the six values, and the second objective is the best single value §3 task.py wann.py. Enabled connections count as complexity, and a network with no connections is set to one for the objective ind.py wann.py.

Ranking. The paper ranks networks on mean reward and connection count in 80% of cases, and on mean reward and maximum reward in the other 20% §3. The ranking is Pareto dominance with crowding distance §3 nsga_sort.py.

Variation. Each child comes from one parent, chosen by tournament selection, and receives exactly one topology change §3 _variation.py _variation.py.

• Insert node. Split a random enabled connection through a new hidden node. The connection into the node gets weight 1, the connection out keeps the old weight, and the new node's activation is drawn at random §3 _variation.py.
• Add connection. Connect two unconnected nodes so that the link goes from a lower to a higher layer, which keeps the network feed-forward §3 _variation.py.
• Change activation. Give one random hidden node a different activation from the allowed set §3 _variation.py.
• Enable connection (code only). Re-enable one random disabled connection. The paper does not describe this operator _variation.py.

Allowed hidden activations are ids 1 to 10 for every task except MNIST, which excludes the step function config.py. The paper's Figure 3 names the same ten functions fig. 3. The code defines them as follows ind.py:

The paper names the functions and shows their shapes, but it does not give the π scaling of sin and cos fig. 3.

Swing-up environment (code). The observation is (x, x_dot, cos θ, sin θ, θ_dot) and the output is a force, clipped to [-1, 1] and multiplied by 10 config.py cartpole_swingup.py cartpole_swingup.py. Each step pays ((cos θ + 1) / 2) times cos(π x / (2 · 2.4)). The episode ends when |x| exceeds 2.4 or after 1000 steps cartpole_swingup.py cartpole_swingup.py. The paper describes the reward only in words §4.

Biped, car racing and MNIST (code). The biped has 24 inputs, 4 outputs and episodes of up to 1600 steps config.py config.py. Car racing takes 16 latent features from a pre-trained VAE, outputs 3 commands and runs up to 1000 steps §4 app. A.4 config.py config.py. MNIST uses 16×16 images (256 inputs) and 10 outputs. Each rollout scores 1000 random training samples by the negative cross-entropy app. A.3 config.py classify_gym.py classify_gym.py classify_gym.py.

Pseudocode, search loop. This follows the paper's steps. The code's objective and selection details are in "Paper vs code".

# WANN search loop  [§3] [code: WANNRelease/WANN/wann_train.py#L27-L33]
# Input:  pop_size, generations, weight_values (six shared weights)
# Output: final population of topologies

def wann_search(pop_size, generations, weight_values, reps, tourn_size):
    # Start from minimal nets: no hidden nodes, sparse input-output links  [§3]
    population = initial_population(pop_size)
    for gen in range(generations):
        for net in population:
            per_weight = []
            for w in weight_values:
                # Average the rollouts at this shared weight  [§3]
                rewards = [rollout(net, w, rep) for rep in range(reps)]
                per_weight.append(mean(rewards))
            # Fitness: mean over weights; second objective: best weight  [§3]
            net.mean_reward = mean(per_weight)
            net.max_reward = max(per_weight)
        # One draw per generation: 80% (mean, connections),
        # otherwise (mean, max)  [§3]
        objectives = draw_objectives(population, prob=0.80)
        # Rank by Pareto dominance, ties broken by crowding distance  [§3]
        ranked = nondominated_sort(population, objectives)
        # Remove the worst 20% from the breeding pool
        # [code: WANNRelease/WANN/wann_src/_variation.py#L55-L58]
        pool = ranked[: int(0.8 * len(ranked))]
        # Keep the top 20% of the pool unchanged
        # [code: WANNRelease/WANN/wann_src/_variation.py#L60-L64]
        children = pool[: int(0.2 * len(pool))]
        while len(children) < pop_size:
            # Tournament: the best-ranked of tourn_size random picks  [§3]
            parent = tournament(pool, tourn_size)
            # Exactly one topology change per child  [§3]
            # [code: WANNRelease/WANN/wann_src/_variation.py#L299-L305]
            children.append(mutate_topology(parent))
        population = children
    return population

# One topology change per child  [§3]
# [code: WANNRelease/WANN/wann_src/_variation.py#L337-L349]
# Input:  net with its connections and nodes
# Output: a new net with exactly one change

def mutate_topology(net):
    # Draw one operator with the code's default probabilities
    # [code: WANNRelease/WANN/p/default_wan.json#L10-L13]
    # Paper table: add connection 0.25, no enable operator  [app. A.4]
    op = draw_operator(probs=[0.20, 0.25, 0.05, 0.50])
    if op == "add_connection":
        # Feed-forward link between two unconnected nodes  [§3]
        net = add_feedforward_connection(net)
    elif op == "add_node":
        # Split a random enabled connection through a new hidden node  [§3]
        net = insert_node(net)
    elif op == "enable":
        # Re-enable one random disabled connection  [code only]
        net = enable_random_connection(net)
    else:
        # Give one random hidden node a different allowed activation  [§3]
        net = change_activation(net)
    return net

Hyperparameters

Paper values from the appendix table, with the code's values beside them. Population sizes are multiples of 96 (or 64 for car racing) to fill the cores of the machines used app. A.4.

Settings that appear only in the code. Each row is swing-up, biped, car racing, MNIST, in that order.

Fine-tuning (tuned weights). For the "tuned weights" rows of Table 1, the champion's individual weights are trained with population-based REINFORCE. Swing-up and biped use a population of 384 with 16 rollouts per agent; car racing uses 64 agents with 4 rollouts each. Training runs for 3000 generations, and the rest uses the defaults of the external estool package app. A.6. The MNIST reward is the negative cross-entropy on the training set app. A.6. No REINFORCE code is in the WANN release [grep of code/WANN and code/WANNTool, no match].

Results

Author-reported. Each row is the cumulative reward averaged over 100 random trials of the champion network tab. 1. Each WANN task had nine independent search runs app. A.5. Fixed-topology baselines are hand-designed networks. The biped baseline is the estool model, whose state-of-the-art score is taken from the work keyed ha2018designrl app. A.7 §4. Car racing uses the controller from the work keyed ha2018worldmodels, with 867 trainable parameters app. A.7. Swing-up uses a single hidden layer of 10 units, 71 weights app. A.7.

Source: tab. 1. The caption does not define the ±. Shared weights are drawn from U(-2, 2), and the tuned shared weight is the best value in (-2, 2) §4 tab. 1.

The authors' reading is that the WANNs perform with random shared weights, where the fixed networks need tuning, and that WANN weights are not independent of their values: they fail when individual weights are random §4. With trained weights, WANNs reach similar state-of-the-art performance §4.

The authors say the networks are small enough to interpret, and they read the swing-up network's development across generations as a sequence of structures §4 fig. 4.

Champion networks: 52 connections for swing-up, 210 for biped and 245 for car racing fig. 5. The biped SOTA baseline uses 2804 connections §4. The MNIST champion has 1849 connections fig. 7.

MNIST. The introduction reports about 92% test accuracy with random weights §1. Section 4 says WANNs classify MNIST about as well as a single-layer network with thousands of weights trained by gradient descent, without giving a number §4. Per-digit accuracy varies across weight values fig. 6. A vote over the networks at several weight values beats a randomly chosen single weight and comes close to the best single weight §4 fig. 6.

Search runs. Figures 8 to 10 show per-run performance over weight values for swing-up, biped and car racing app. A.5 fig. 8 fig. 9 fig. 10. Their numbers are not transcribed here.

Paper vs code

Paper: arXiv v2, 2019-09-05 [raw metadata]. The paper points to a project page for its code app. A.1. That page links the WANNRelease folder of google/brain-tokyo-workshop, at commit 67c73645121d599f855714788db8a5c44e329c29, licensed Apache-2.0 LICENSE. The folder's own README calls it a snapshot of the code used for the paper and disclaims being an official Google product README.md README.md.

Checked and matching: population sizes, generation counts, initial connection percentages, tournament sizes, the change-activation and add-node probabilities, the six shared weights, and the ten activation functions.

Differences:

• Add-connection probability. The paper's table gives 25% app. A.4. The code default is 0.20, and none of the four task files overrides it default_wan.json _variation.py. The code runs 0.20 for add-connection, 0.25 for add-node, 0.05 for enable and 0.50 for change-activation.
• Enable operator. The paper lists three operators §3 and has no enable row app. A.4. The code adds an enable operator at 5% default_wan.json _variation.py.
• Objective choice. The paper says "in 80% of cases" §3. The code draws once per generation for the whole population wann.py.
• Culling and elitism. The worst 20% are removed from the breeding pool, and the top 20% of the rest are copied unchanged default_wan.json _variation.py. The paper describes neither.
• Crossover. The paper describes a mutation-only search §3. The code has a crossover operator, but its default probability is 0.0 default_wan.json. Crossover keeps parent A's topology and swaps in some of parent B's stored weights _variation.py. Evaluation overwrites those weights, so the swap has no effect on scores.
• Rollouts. The paper says "multiple rollouts" §3 and gives no count. The code uses 3, 4, 2 and 1 for swing-up, biped, car racing and MNIST swingup.json biped.json vaeRacer.json mnist256.json.
• Table 1 protocol. The paper's shared-weight rows use uniform draws from (-2, 2) tab. 1. The shared-weight evaluation in WANN/ uses the six fixed values, or an evenly spaced grid over [-2, 2] when alg_wDist is not "standard" task.py. The 100-trial protocol of Table 1 is not in WANN/. WANNTool/model.py has a uniform parameter sampler with default standard deviation 2.0 model.py, but I did not trace it to Table 1.
• MNIST activations. The MNIST section does not mention the step function, but the code removes it for MNIST config.py app. A.3.
• alg_nMean. Set to 8 for MNIST and 6 for car racing mnist256.json vaeRacer.json. No .py file in WANN/ reads it. The paper does not state it.

Pitfalls

• Stored weights are ignored in scoring. Evaluation maps every existing connection to the shared value task.py. The stored weights (1 for new connections, the parent's weight on a split) never reach a score _variation.py. Only which connections exist matters, plus the shared value.
• Disabled and absent connections. Disabled connections become NaN in the weight matrix and are then set to zero, so they behave as absent ind.py ind.py. Complexity counts enabled connections only.
• Crowding-distance scale. The guard tests the objective range, but the scale factor is abs(1/max - min), not a function of the range nsga_sort.py. The factor can be zero, which collapses every crowding distance in that front to zero and removes the tiebreak, or it can be large. The paper gives no normalisation.
• Culling and elitism change the dynamics. The 20% cull and 20% elite copy are not in the paper, so results that depend on population turnover may not transfer default_wan.json.
• Shared seeds. All individuals in a generation use the same rollout seeds, so differences between candidates are not sampling noise wann_train.py task.py. The paper does not state this.
• Activation constants. The code uses sin(πx) and cos(πx), a Gaussian with exp(-x²/2), and a sigmoid written as (tanh(x/2) + 1) / 2 ind.py ind.py. Other scalings give different functions, and the paper does not specify these. The Figure 3 caption writes the plotting range as [2,2]. It means [-2, 2] fig. 3.
• Tie-breaking on integer type. topoMutate compares integers with is, for example choice is 1 _variation.py. This works on CPython's small-integer cache but raises a warning on newer versions. Use == in a reimplementation. The code is pinned to Python 3.5.3 README.md.
• Cost. These counts are derived from the configuration files. Per generation, swing-up runs 192 × 6 × 3 = 3456 rollouts, biped runs 480 × 6 × 4 = 11,520 rollouts of up to 1600 steps, car racing runs 64 × 6 × 2 = 768 rollouts of up to 1000 steps, and MNIST evaluates 960 × 6 = 5760 networks on 1000 samples each. MNIST runs 4096 generations. Evaluation is parallel across cores app. A.4.
• Old pinned dependencies. The code was tested with Python 3.5.3, NumPy 1.15.2, mpi4py 3.0.1 and OpenAI Gym 0.9.6. The car-racing VAE needs TensorFlow 1.8 README.md.
• MNIST test accuracy. The best MNIST network is chosen by training accuracy app. A.3, and the search scores networks on training samples app. A.3. The paper does not say what test protocol produces the 92% in the introduction §1.
• Tuned shared weight. The best shared value in (-2, 2) is picked §4 tab. 1, but the paper does not say whether the 100 evaluation trials are separate from the trials used to pick it.
• Table 1 spread. The ± is not defined in the caption tab. 1.
• Biped input count. The paper says the biped uses 24 inputs and that the controller uses 17 of 25 possible inputs §4. The code has 24 inputs plus a bias node config.py wann.py. The 25th input is probably the bias, but the paper does not say so.
• Random weights hurt. The paper states that WANNs fail when individual weights are random §4. Do not read the "random weights" rows of Table 1 as WANN performance without training.
• Feed-forward only. The search only builds feed-forward networks, and recurrent connections are future work §4 §5.
• Shown networks are not the best-scoring ones. The networks on page 1 and in Figure 5 were chosen for performance and readability §4.
• Car racing VAE. The VAE follows the work keyed ha2018worldmodels, with 16 latent dimensions app. A.4. The WANN controller sees only the VAE latent, not the RNN §4 app. A.4 app. A.7. The VAE code and a pre-trained model are in the release vae.py vae_16.json.
• Figures are not transcribed. Figure 6 and the per-run plots in Figures 8 to 10 carry numbers the card does not repeat.

Lineage

• Builds on: NEAT-style topology operators and minimal initial networks §2 §3; the connection-cost idea, keyed clune2013evolutionary §3; Pareto ranking with crowding distance from NSGA-II §3; tournament selection §3; the minimum-description-length motivation §2 §3.
• Related: earlier weight-tolerant evolution by random trials, cited as hinton1996learning and smith1987learning §2; Bayesian neural networks with sampled weights §2; pruning and lottery-ticket work §2.
• Concurrent: a supermask method that finds sub-networks performing well with random weights §5 §2.
• Compared against: the hand-designed networks in Table 1 §4 app. A.7.
• Superseded: not stated.