Why I prefer Sinusoids to Sigmoids in RNNs

Recently I've been reading about Bayesian inference, and thinking about how it relates to Minimum Description Length and other similar concepts.

A key idea is that the ability to do inference over a small set of examples is, in general, a very difficult problem, and strongly dependent upon the prior probabilities of the hypothesized models matching up with the "true" model to some degree.

In the absence of any knowledge about the "true" model, things get more complicated. Some theories suggest that there should always be a bias towards simpler models, while others contradict this idea. In any case, the prior distribution over the space of hypotheses turns out to be critical to the process of inference.

Therefore, any way of gaining better intuitions about the underlying distribution of a given class of hypotheses/models is of particular interest to me.

In this post, I briefly explore some simple behavioral distributions of my own personal favorite class of models - discrete time recurrent neural networks (RNNs).

---

First, I randomly created a large number of extremely simple RNNs, each having the following architecture:


The link weights were chosen randomly from a normal distribution with zero mean and a variance of 4.

Each randomly generated RNN was given an "impulse" input of 1.0 at the first time step, and 0.0 thereafter, and run for 10 time steps. The output of the RNN was collected and discretized to binary strings of length 10. Thus, there were exactly 1024 (2¹⁰) possible unique "behaviors" that could be displayed by an RNN.

Most behaviors turned out to be very simple - all zeroes or all ones, but there were a range of other behaviors as well. I decided to plot the behaviors as a histogram. Here are the results:


The original image (before scaling) is precisely 1024 by 500 pixels. Each pixel of the x-axis represents a different RNN "behavior", starting with 0000000000 at the left, and ending with 1111111111 at the right. (I considered ordering them by Gray code, but haven't implemented that just yet.) The height of the intervals in the y-axis are proportional to the natural log of the frequency of that particular behavior.

The two most immediately apparent aspects of the histogram are its symmetry and sparsity.

The edges of the histogram represent the most frequent (and simplest) behaviors - constant output of zeroes (left), and constant output of ones (right).

The two peaks nearer the center of the image occur at locations #341 and #682 along the x-axis, which, when converted to binary strings, produce the sequences 0101010101 and 1010101010, respectively. With a little thought, it is not difficult to see why these particular behaviors are so common - they can be represented by the following, extremely simple finite state machine:


So it appears that these very simple RNNs are able emulate some correspondingly simple finite state machines. But, as can be seen by all of the gaps in the histogram, there are a lot of behaviors that simply never occur. As an example, sequence #589 (1001001101) never happens.

---

The really interesting thing I found is that these gaps in behavior are not an inherent limitation of simple RNNs, but rather, they are a limitation simple RNNs that use sigmoidal activation functions:


If instead, a sinusoidal activation function is used, we get very different results!



Here is another histogram of the exact same experimental setup, but this time using sinusoids as the hidden nodes of the RNNs:


The difference is stunning. All 1024 binary sequences are produced!

Empirically, I have previously noticed that sinusoidal RNNs used for neuroevolution massively outperform sigmoidal ones on a wide range of tasks. I believe that now this can be at least partially explained by the fact that RNNs with sinusoidal neurons appear to have a much broader and more evenly distributed coverage of possible behaviors.

In summary: RNNs using sinusoidal hidden neurons appear to produce a more uniform prior over the space of possible dynamical models, which in turn enhances their learning capabilities over a wide range of problems.

Animated evolution of RNN state-space

The above animation depicts the state space of a discrete-time recurrent neural network (RNN) undergoing neuroevolution. Each new frame represents the discovery of an improvement over the previous best RNN.

The goal is to be able to classify the parity of a binary string, in this case, of length 10. The string is fed sequentially to the RNN, one bit per time step.

A few training examples:

0100110101 -> 1
1110001011 -> 0
0010000010 -> 0

The RNN I used for this particular experiment has a hidden layer of two neurons. This was done so that I could easily plot the state space in two dimensions. The x-axis represents the activation of the first neuron, the y-axis is the activation of the second. Each point within a given frame represents the 'state' of the RNN at the very end of processing a string. The number of points per frame corresponds to the number of training examples. The first few frames appear to have fewer points; this is just overlap. The points have been colored red and blue to denote whether the target output should have been even or odd parity; they are not representative of the actual output of the RNN.

As can be seen, over the course of evolution, the state space of the RNN rearranges itself so that the red and blue points become progressively more linearly separable. On the last frame, it has nearly achieved that goal (as shown below), and classification accuracy on unseen examples is roughly 99%.



For those who are interested, I created these visualizations using a combination of Processing and GIMP

n-grams as finite state machines

I'm going through Foundations of Statistical Natural Language Processing and decided to create some visualizations of n-grams as finite state machines to improve my intuitive understanding of them.

For alphabet {0,1} and n = 3:



For alphabet {0,1} and n = 4:



For alphabet {0,1,2} and n = 3:



I find it fascinating that such a simple concept (the n-gram) can produce such intricate structures.

RNN evolution

I evolved a recurrent neural network (Elman network with 5 hidden sine nodes) on the 89-state maze task (described here) using CMA-ES (thanks to Nikolaus Hansen for making his source code publicly available!), and was able to get good results (approx. 52 time-steps to solve, averaged over 1000 trials.) Each time an improved solution was found, the parameters were written to a text file. The above graphic visualizes the progression of the parameters through time.

Visualization done with Processing 1.0.

77neurons: Cart-pole

This is the first video of my project with Jad Nohra; our project is called 77neurons.

This is the non-Markov version of the cart-pole problem (no velocity information given.) The controller is a recurrent neural network using 2 sinusoidal nodes in the hidden layer (as opposed to more standard sigmoids.) It is currently being trained with a simplistic stochastic local search procedure, but we intend to implement various forms of reinforcement learning in the future.

Delayed N-Armed Bandit

I have been trying to more thoroughly understand concepts related to reinforcement learning; specifically temporal difference learning. I reread portions of the book by Barto and Sutton. One of the examples given in the book as a toy problem is that of the n-armed bandit. An interesting variant of this problem occurred to me – What if the rewards are not dispensed immediately, but rather after some fixed (or perhaps random) delay?



Imagine walking into a casino and being given one hour to play a large group of slot machines. However, unlike regular slot machines, these ones will produce a fixed amount of coins per pull. The trick is to figure out which slot machine gives you the most reward, and then exploit it. Sounds simple, right? There are two caveats: First, the machines will only give you the coins after some unknown delay. Second, when you receive the coins, you will not know the identity of the machine that produced the reward.

I wrote a fairly simple program in java to do this experiment by making use of eligibility traces, and found that it worked far better than I had expected was possible. Given a large number of possible actions (say n = 30), the system was able to properly assign credit to actions such that for all actions in A, if the real reward R(A_n) < R(A_m) then the expectation of reward E(A_n) < E(A_m) as well - so the actions would be ranked correctly in terms of value. This ranking could be learned perfectly, even when the delay between action and reward was 100 time-steps or more. Granted, a large number of observations are required (in the millions), but it is still impresses me that such a thing can be done at all.

In order to understand how and why this worked, I attempted to characterize the result mathematically, and was able to do so in a way that very closely matched the empirical results:


Where:

r := eligibility trace decay rate (such that 0 < r < 1)
d := (fixed) delay between causal action and reward
E[V_all] := Expectation of reward averaged over all actions
E[V_cause] := Expectation of reward due to causal action

This rather simple equation appears to nearly perfectly describe the observed results in the limit of a great number of observations.

The main technique used is treating the “volume” of eligibility as the sum of an infinite geometric series, which is where the 1 / (1 – r) terms come from. Basically, we are assuming a randomized action policy, and therefore, an average over all possible rewards weighted by their relative likelihoods. These rewards will be (incorrectly) applied to our “causal” action, weighted by the eligibility. The one difference is the time-step at which the “actual” reward is emitted; this will be weighted by the eligibility at that delay, which is represented by the r^d terms.


Additionally, I tried some variations on the basic experiment.

Successful circumstances:

• Various delays, uniform across bandits (up to about 500 time-steps)


• Online randomized delays (varies from observation to observation)


• Heterogeneous delays across bandits


• Skewed action frequencies (some actions taken far more frequently than others)


• Online Gaussian noise added to rewards (up to variance of 10)


• Various numbers of bandits (up to about 30)


• Non-random sequences of action (e.g. 1, 2, …, n–1, n, 1, 2, …)

Unsuccessful circumstances:

• Replacing traces

Visualizing high-dimensional fitness landscapes

I've recently been exploring various ways of improving my intuitive understanding of fitness landscapes. This is a difficult problem, because the parameter spaces I want to be able to think about are often composed of dozens or even hundreds of dimensions. I have found that most authors describing fitness landscapes do so using overly simplified diagrams that somewhat resemble hills or mountain ranges.

In some recent experiments, I've found some nice ways of visualizing the geometry of actual fitness landscapes. I produced the images below by evolving recurrent neural networks to optimize performance on various tasks (e.g. wandering through a virtual maze), and then examining the resulting fitness values of a large number of very nearby points to those evolved solutions. Of course it is impossible to visualize the entire space, because of the high dimensionality; so instead what we are looking at are randomly selected 2D slices through that space. The shading is representative of numeric fitness (dark = low-fitness, light = high-fitness).

Here are a few examples of the results: