Almost Uniform Sampling From Neural Networks
This addresses a theoretical sampling problem for neural network researchers, offering incremental algorithmic improvements for specific network types.
The paper tackles the problem of uniformly sampling labelings from neural networks with fixed architectures, providing an algorithm that runs in polynomial time and guarantees each labeling appears with a probability at least (W/(2ekn))^W for W<n, and an exact uniform sampling method for single neurons.
Given a length $n$ sample from $\mathbb{R}^d$ and a neural network with a fixed architecture with $W$ weights, $k$ neurons, linear threshold activation functions, and binary outputs on each neuron, we study the problem of uniformly sampling from all possible labelings on the sample corresponding to different choices of weights. We provide an algorithm that runs in time polynomial both in $n$ and $W$ such that any labeling appears with probability at least $\left(\frac{W}{2ekn}\right)^W$ for $W<n$. For a single neuron, we also provide a random walk based algorithm that samples exactly uniformly.