Sunday, February 24, 2013

Google Code Jam 2013

Google Code Jam is right around the corner!  registration will open on March 12, 2013... this is always my favorite programming contest each year.  I'll be trying to get a group of coworkers to participate in the action.  Last year, I reached the second round, and actually had one of the better scores in round 1C, which was the best round of my life.  Hope to see you there!

Thursday, February 14, 2013


  Today, I was introduced to "Scalatron", a kind of virtual robot wars as a platform to teach programmers about Scala.  Its a fascinating concept, and appeals to my competitive nature in the programming arena.  Additionally, I think I can use this as a virtual world to validate some ideas I have about emergent intelligent behavior.

  Watching some of the competitions on youtube, there seem to be a number of ways you can set up the rules to the game.  I like this particular one, which introduces food, both animal and vegetable, poison, and predators as part of an environment where you try to prove your bot the best.

  If you are looking for an excuse to learn a new language, this may be as good a reason as any!

Saturday, February 9, 2013

Beginning a model for emergent intelligent behavior

A single neuron under an electron microscope
  One of the most fascinating mysteries of life is the nature of intelligence.  How is the brain able to make sense of the world around it?  How is able to use that information to make intelligent decisions?  How is a conglomeration of individual neurons, each largely functionally identical, able to link together into networks representing complex associations, abstract ideas, knowledge about the very patterns that make up the world around them?  I'd like to start a collection of posts describing my understanding of how these structures could be modeled to produce intelligent behavior.

Anatomy of a Neuron

  The arena of Artificial Intelligence actually has a lot to say about the mechanisms by which intelligence might work.  Early pioneers of the field examined the structures of neurons,  like the one pictured above.  Dendrites, which are short extensions emerging from the cell body, act as receptors of chemical-electrical inputs.  The axon acts as the emitter of electrical information, where its endings are significantly further away from the cell body.  When enough electrical activity builds up through simultaneous pulses to the dendrites, a signal will fire through the axon.  Neurons form electrical networks through overlapping regions of dendrites and axons.  But an arbitrary electrical network is not that interesting.  What is the guiding principal which gives neural networks that plasticity which allows the network to mimic patterns?  One of the long standing theories about how these adaptations occur was formed in 1949 by a man named Donald Hebb.

Hebbian Learning
  The basic idea of Hebbian Learning is captured in the expression, "cells that fire together, wire together".  When a synapse fires from an input neuron, and correlates to the firing of the output neuron, the dendrite connection to the input axon grows stronger.  Inactive dendrites over time grow weaker.  This provides the insight to describe a mathematical model for how connections on an artificial neural network can be updated such that any neuron naturally mimics the pattern of electrical activities at a neuron's outputs given only its inputs.  Suppose you have a neural network that looks as follows:

Model of a single neuron

  Here, the neuron's dendrites are represented as the X inputs on the left, which form a linear combination to produce the output Y on the right, representing the axon of a neuron.  The W weights represent the strength of the connection for any specific dendrite.  When some pattern of X inputs are fired, the weights are updated as follows:

  This equation says the weights get stronger when the input X and the output Y are the same, and gets weaker when they are different.  The N parameter is a learning rate.  From our diagram, we see that the linear combination comes together at f, which is a nonlinear function which acts to normalize the range of outputs.  To mimic the activity of a real neuron, usually some kind of step function is used, so that positive linear combinations produce a 1 at the output, and negative combinations produce a 0 at the output.  If you were to train such a neuron with example inputs and outputs, you would eventually get a neuron that given only the inputs would predict the output that most closely matches that in its training set.  This is called a Perceptron network.  Such a network would be capable of accurately predicting any set of data that is linearly separable in the input space, but would by itself not be good at identifying more complex patterns.

Multi-layer Perceptron

  Now suppose we take these neurons, and chain them together to form a more complicated network.  Here, the network takes input impulses and maps them to several neurons, which in turn map their axons to two more output neurons.  This feed forward multi-layer neural network is able to identify more complicated non-linear patterns.  The math to apply Hebbian updates to the weights in this network is also more complex, as the learning starts from the output layer and propagates backwards towards the input layers.... leading to the term "Backpropagation".  So with only a simple feed forward neural network, we are able to create a structure capable of identifying patterns.  But the brain does so much more... it is able to store and recall memories, and learn to make decisions to its own benefit.  How does this happen?

Hopfield Network

Hopfield Networks
  The next piece of the puzzle are a special type of neural network known as a Hopfield network.  A Hopfield network is different from a feed forward neural network because it allows for outputs from a neuron to have feedback loops to itself.  As inputs are fed into such a network, the outputs loop back to the inputs, providing a new training input for the network to adapt to.  This feedback repeats until the network converges on a stable solution.  One of the properties of such a network is that is acts as a type of memory.  If you give it an incomplete set of inputs, or if the inputs are partially garbled, it will naturally converge on the actual memory that most closely resembles the inputs it was fed.  For instance, if the inputs were pixels of an image, and we only provided the left half of the image as an input, it wold naturally reproduce the right half of the image (as seen below).

Hopfield network memory recovery from partial input
Again, there is a Hebbian learning learning rule for updating this type of network,  as follows:
which says that when you have P neurons that fully feed back into themselves, the weight between neuron i and j can be calculated as the sum of the inputs Xi, Xj for each of the training examples.

What Next?
  So we now have a basis of understanding for how neurons form networks, and how the networks can adapt their connections through Hebbian learning to allow the network to build pattern recognizers.  We have a mechanism for the network to store memories in an auto-associative fashion.  But we have a problem here... how does the brain learn good from bad behaviors?  Imagine you started walking towards a wall.  Eventually you reach this wall, but failing to stop, you bonk your head.  A pattern recognizer, trained to recognize the circumstance, may be capable of recognizing that when you reach the wall, your head will hurt.. but it wouldn't care one way or the other about the outcome it predicted.  Artificial intelligence typically prescribes that a teacher separates good behaviors from bad behaviors, and trains the neural network to avoid bad behaviors.  I believe this to be an incomplete explanation, as our brains do not have the luxury of a teacher to predefine all good and bad experiences for us.  This is an emergent property of the mind.  What I would like to explore is what mechanisms could exist to produce this emergent property, and come to a hypothesis of how intelligent behavior is formed.

Stay tuned for more to come...

Sunday, February 3, 2013

Facebook Hacker Cup 2013 Round 1 Problem 1

Wow, I have to say I was at first skeptical of a 24 hour round 1 in the Facebook Hacker Cup... but these problems were quite challenging. I'm going to break this up into three posts, one for each of the problems I attempted.

The first problem was as follows...

You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

The more intuitive explanation was from the problem statement... imagine that you have N cards in a deck, each representing a different value.  You randomly select K cards to make your hand, and the strength of your hand is equal to the card with the highest value... so for instance if you had the hand (2, 4, 6, 8)... your hand would score as 8.

Now given this, you want to consider all possible hands, and figure out the average score.  More specifically, you just want the sum of all hands mod 1000000007.  To solve this problem, you are given N, K, and the array A containing all the values in the deck.

My approach was to solve the problem looking at each element of A, asking how many possible hands exist given that this card is the highest in the hand.  So imagine we have A sorted as follows, with K = 3 and N = 10....

(2, 5, 6, 8, 9, 12, 15, 17, 19, 20)

if we consider how many K=3 card hands could have 15 as the highest card, we recognize that we need to select two cards from the set to the left of 15.  So in this case, we want 2 Choose 6 to fill out the remainder of the hand ( remember that K Choose N = N!/(K!*(N-K)!) ).. so in this case there are 15 possible 3 card hands from this set where 15 is the highest card.

Generalizing this to sum all possible hands together, and taking into account we get the main part of the program looking something like this...

public String Solve(int n, int k, List a)
    int mod = 1000000007;
    var answer = a.OrderBy(i => i).ToList().Select((strength, i) => (combinations(i, k - 1, mod) * (strength % mod)) % mod).Sum() % mod;
    return answer.ToString();

The next thing to note is the nature of big numbers... factorials combined with the sizes of the data sets means that you must be capable of taking care of the modulo requirement mid calculation.  First, we recognize the large prime number provided in the problem means we can structure the answer in terms of congruent answers...  I found this cheat sheet from U.C. San Diego to brush up on rules of modular arithmetic... and the section one rules tell us that if our binomial coefficient operator produces a congruent value mod the given modulo, we can just keep modding at each step of the operation to get an equivalent answer.  I had to look up an example of fast binomial coefficient generation, since my attempts overflowed with big numbers or were inaccurate... I found my baseline on stackoverflow here.

So that was my answer to the first problem... more to come with my approaches to the other two problems.