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.

Vehicles in Rajasthan

I was perusing https://data.gov.in once more and my thoughts turned back to my home state of Rajasthan. A quick search revealed that the site does indeed host data on Rajasthan (see this).

We take up the motor vehicle registration data provided on the site and immediately discover that like all the data on the site, this dataset is not prepared for consumption. We shall have to perform some data cleaning.

A few Excel copy pastes later we have a single file which I've put up on my Google Drive here.

With that I loaded this stuff into a Jupyter notebook and got this neat plot as the end product of some nifty manipulations.  The entire notebook is available here (I'll upload this soon).

First let's take a look at the New Registrations in every vehicle Type over the years.

Everyone seems to be buying two wheelers in Rajasthan! Cars and Tractors are the next big wigs but they stand no where close to where two wheelers are.

 Irrespective of vehicle class, there is growth in motor vehicles in Rajasthan as can be seen in this Point plot. We can see that what has caused the explosion in vehicle numbers is within the non-transport class of vehicles.

We can see that it's just one outlier which has caused this boost! What is that? We know that it has always been high in registrations. It's probably the motorcycles. It's curious that the total shoots up so quickly in 2012 but the growth is generally increasing. Let's see if the data has mistakes in it. We plot the total counts reported over the years and then we plot the cumulative sum of the new registrations.

That's strange.

New registrations for a year should contribute to the next year's total. Since we don't have data before 2005, we should expect the difference between reported numbers and expected numbers to be constant.

That difference changes. It changes abruptly in 2012 going from massively underreported to over reported. An effect of the Aadhaar card wherein people suddenly started reporting unregistered vehicles? Perhaps vehicles came in from other states. I don't know if that is counted as a new registration or not. It's either that or our government is bad at reporting / collecting statistics.

Attendance in St. Stephen's College

I've been hunting around for datasets I can relate to for some time now. This fine evening I arrived on the conclusion that I could simply use attendance data from the website of St Stephen's College.

The complete analysis notebook is available as a gist (here's the gist).

Collecting the data was a matter of inspecting how the website was obtaining it's data. A company has been handling our attendance since the beginning it seems. (GreenClouds site link). As far as I'm concerned they've made a mess of the data transfer as I can see. Perhaps it originated in the college itself, perhaps it's due to some mistakes on the company level. Whatever the cause the data format is a mess.

I open up my console and spin up a Python script to get the data from the college website. Takes about two minutes on my Internet connection to collect all the information.

We then proceed to put it in a nice tabular form with columns being Name, percent LA, percent TA, percent PA, admission_year, course.

Things are now ready for graphing.

Graphs

We go on to make Box plots. If you were to line up people in order of their attendance you would get a box plot. The person in the middle of the line is the line cutting the box in the middle. It shows that there are an equal number of people on either side of the line.

You cut each part of the line in half again and you get the bounds of the box.

This one is a gem. What is up with Chem! The attendance of their Lectures is absolutely ridiculous. While everyone more or less has the same attendance in a course Chem people are all over the attendance spectrum! Then again, their Tutorials box plot is neat too!

Yes. I see it too. Math people are consistently in class with a few people as outliers. Nobody else has this kind of spread. 

Perhaps a better way of seeing this would be violin plots where you get to see the density of the people instead of simple boxes. The thickness of the violin denotes how many people people are at that point.

For example we can see that a lot of the math  people are high attendance junkies and a substantial amount of CHE, PHY, PCH and, PCS are low attendance lovers.

There! The average PHI student absolutely does not give a hoot about attendance! The PCH and PCS programs do every class together as is apparent from their spreads. ENG and HST do compete with PHI but PHI does take the cake.

Let's move on to the simplest of all graphs. The Histogram. No explanation needed here.

Looking at the histograms we can see that almost everyone attends class with the exception of a few people who absolutely don't come to class. Perhaps people who left the course and the administration just did not remove them from roll calls? What about experience?

We do a regular point plot to see change in attendance over months. The vertical lines along the points denote a 95% confidence interval.

The third years have found that perfect balance of leisurely attendance during most of the semester and then picking it up during the last months. First years exhibit that trait of a "नया नया मौलवी" perfectly. Second years have figured out that attendance does not really matter, but are still to find out how badly those marks can affect their marks. With time comes wisdom,

That's it for now. I'd love to do some more if someone can come up with data at a lower granularity.

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.