Evolving Neural Network Weights

Neural networks offer quiet a large repertoire of tasks that they can accomplish well. With the increasingly smart solutions people come up with to squeeze out performance with smaller networks(squeezeNet ,ReLu to name a few) it's likely that neural networks will dominate the Machine learning scenario for some time to come.

There is one limitation however. Current implementations of learning mechanisms ([1], [2]) are mostly gradient based. This limits the loss function to being at least differentiable, if not double differentiable in some cases. There are alternatives like reinforcement learning and genetic search but those have not been as heavily invested into by the community as the gradient based methods.

This post explores genetic search as a method for finding the appropriate weights for neural network architectures. We illustrate the basic principles and follow along with some basic code.

Let's look at the XOR problem. One of the classic problems that Minsky famously pointed to in the Perceptron book[3]. The problem is simply to compute the XOR function given two binary inputs. While a single perceptron is unable to do this, a multi layer perceptron is able to perform this computation.

We use a simple 3 layer neural network and sigmoid activation as done in the classic days of neural networks. Instead of using the wonderful powers of Theano, tensorflow or torch to perform automatic differentiation in order to use gradient based methods, we are able to drop those architectures from our program entirely.

We use numpy to make the matrix operations a little easier to read. The first part of the code imports the relevant libraries and defines the sigmoid function to be used later on.

We then define a roulette function which selects elements from a given array with a probability proportional to the magnitude of elements in the array. This is present in this part of the code.

The next bit defines the forward calculation of the network given it's weights and input data. Besides that it also defines a function which calculates the "score" of a given output from the network and the output expected. Here we ask the genetic search to maximize the ROC AUC score.

The get fitness function is another building block which makes use of the functions we have already defined. It takes in a network configuration and returns the "fitness" associated with this configuration. In genetic search terms this network configuration / network weight list is known as the "gene".

To employ genetic search in it's classic form we write two function which emulate gene crossover and mutation. This is the bread and butter of the genetic search algorithm which allows is to move around in the search space.

The last of our function definitions defines the "main" function which evolves network weights to fit on a certain data set that we provide. This data set is the XOR data set that we manufacture using numpy in the later sections of the code.

All that is left is to set the various configuration variables for the genetic search and to call the evolution function with these variables. We see that genetic search very quickly finds the "correct" weights for this neural network. It does get lost sometimes for very long periods of time but that is simply because we have implemented a vanilla version of genetic search.

The entire code is available at https://github.com/theSage21/evonet.

Taking a Look at Competitive Programming

Introduction

Competitive programming is a lucrative business if you have the chops for it. It has however been subject to little analysis AFAIK. This has partially been because of the unavailability of consolidated data set to facilitate this. To resolve that I scraped together data from the Codechef website amounting to a little over 1 million programs submitted to the site. You can get the dataset on Kaggle (link to data).

The purpose of this work is to get started with the OpenAI special project which states

Build an agent to win online programming competitions. A program that can write other programs would be, for obvious reasons, very powerful.

To solve a problem, the first step is always to understand the problem and know it's quirks. This blog post is possibly the first of many exploring this dataset with the ultimate aim of being able to generate a solution program given the statement of the problem.

An Exploratory Data Analysis has been done by Swaraj Khadanga. You can see it at Simple EDA.

A brief description of the data

The dataset presents a table with columns as variables and rows as observations, making it tidy in the process. The columns we are interested in are:

• QCode : The Question Code, denoting a unique question
• Solution : The program written by the user
• Status : Was it a correct attempt or not?
• Language : The language that the code was written in.

Program Visualization

This visualization makes some assumptions, namely:

• We consider only those programs which were written in C
• We reduce each program to another string, keeping only keywords and special characters. The idea is to try and get an approximate representation of the Abstract Syntax Tree by obtaining an infix representation of the code.
• With these program representations as representations of the programs, we calculate the Levenshtein distance between each pair of representations.
• Using the above data we have a complete graph with each vertex representing a program and each edge being the Levenshtein distance between two programs.
• Now, we place each vertex in a 2D plane at coordinates such that the difference between the distances between points on the plane and the Levenshtein distance between two points is minimal. This is similar to what has been done by Ben in his post on numerical optimization in the Last cities example.

We plot the points at the calculated coordinates and color them by the problem they were trying to solve. By doing this we arrive on a graph which is shown below.

All I can say at this point is that it's interesting. The X and Y represent nothing of significance. What is significant is the relative distances between the points. Most programs are of a similar structure with very few actually differing a lot from each other.

There will be more on this in later posts. The plot was created using this gist.

Why High Dimensional data is hard to work with.

High Dimensional Data is hard to work with. This statement is seen all over the place in reference to data analysis and machine learning. But why exactly does that happen? I'll try to explain two of my favorite reasons here in this post.

Sampling

Random Sampling gives out in high dimensional spaces. It's not random any more. This problem becomes apparent in algorithms like KNN. Take, for example 100 points in an n dimensional "cube".

If I use the inbuilt np.random.random() function from numpy I can easily obtain 100 random points from any n dimensional space. Or can I? If I measure the distances (L2 norm to be exact) between all pairs of these points, I get histograms as seen below.

As we see, higher dimensions lead to increasingly the same distance between points. The sampling loses it's randomness, rather higher dimensions are a little harder to sample from.

Spiky Nature

Higher dimensions are spiky! This is bad for methods which depend on the smooth nature of the cost surface for a loss function. It is wonderfully explained in this post here (http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres#HN2). I'd  simply like to add a graph to it.

This goes to show that the spike like nature of the surface of an n-sphere continuously increases as the number of dimensions increases. After 9 dimensions, the sphere actually "sticks" out of the cube that encloses it.