Imagine Cup

Surprisingly, we advanced to round 2 of Imagine Cup. Here is the demo we submitted. 150 teams out of 700 advanced. Only 6 teams advance to the finals. We are debating whether finishing the game is worth the time investment given we have such a low probability of making it to the finals :D

lol

Googleplex

I just accepted the internship offer from Google. I will be headed to the Googleplex this summer. Numenta replied saying that they will not be giving me an offer. I will be doing a 14 week internship at Google. When I finish the internship in August I plan on visiting my parents in Sri Lanka for a few weeks before returning to UBC.

Summer Internship

Today I got internship offers from both Google and Facebook. I am just waiting to hear back from Numenta before I make a decision of which to accept. On Friday I visited Numenta for a full day of interviews. Jeff Hawkins and I were on the same flight to San Francisco. We shared a taxi from UBC to the airport and he even gave me a ride to my hotel after the flight! It was a great opportunity to talk with him about HTM.

o_o

Contests and Interviews

There is a new programming contest on Al Zimmermann's webpage: http://www.azspcs.net/Contest/MagicWater. I am currently ranked 8th out of 56. The contest lasts months, so there is no way I will maintain this high rank :D. On the son of darts contest I currently have a score of 90.00 and a rank of 59 out of 384.

Three friends and I are entering the Game Design category of Imagine Cup. Today we submitted a game demo. It is a simple text adventure game using Silverlight. The game also works in Linux using Moonlight. I wrote the text parser for the game. Our team was speculating that we probably put the fewest man-hours into making the game out of all the competitors (so I will be surprised if we advance to future rounds). If we make it to the finals we get a free trip to Poland.

I am currently in the interview process with Google, Facebook, IMO, and Numenta for a summer internship. Later this week I will be flying down to California for a full day interview at Numenta. Coincidentally, Numenta's founder Jeff Hawkins is giving a talk at UBC this week. I have scheduled a meeting with him when he gets here!

Son of Darts

I spent the entire day working on Son of Darts. I am now in 71st place out of 379. My current submissions use a variety of searches including stochastic local search, backtracking, greedy, and various heuristics. Out of the 19 Canadian competitors I have the highest score :D

Contests

UBC has a two week break due to the Vancouver Olympics. I have been using the time to work on various programming projects. I have become involved in a number of contests:

-RoboCup: A robot soccer contest. I am working on the AI for the robots. We recently sent in qualification materials. If we qualify, we get to compete at RoboCup 2010 in Singapore this summer. Last year we went to Austria for the contest.

-ImagineCup: Our team is planning to compete in the game design category. We haven't done much implementation yet, but we plan on creating a text adventure game (plus some simple graphics). If we make it to the finals we get to go to Poland this summer.

-Son of Darts: I just started this contest a couple of days ago. I am currently ranked 145th out of 368 competitors. I am using stochastic local search to optimize the solutions.

-BattleCode: A fun AI programming contest. Last year our team did pretty well.

This break I am also planning on submitting a paper about PPM to a NLP workshop. I also need to study for a big midterm happening in two weeks. It is going to be a busy break!

Harbin Trip

Over the last week I have been in China attending the ACM ICPC World Finals. The trip was really fun. I got invited to come even though I am not a competitor since I might be part of the UBC team next year. Six people from UBC came (one coach, three competitors and another guest). Harbin is in the northern part of China so was extremely cold. The temperature was usually between -10 to -30 Celsius. I have posted pictures of my trip here. There were a lot of activities organized by ACM so there wasn't much time to explore Harbin ourselves. Harbin is famous for ice and snow sculptures. There were sculptures lining the streets all over the city.

UBC did well at the finals. They got 18th place. I think UBC's record is 13th place. Here is the final scoreboard. There were three North American teams which did better: Stanford, Cornell, and Carnegie Mellon. These teams only did better on time and did not solve more problems than UBC. All three members of this year's team are not eligible to compete again next year. Based on the performance of the second and third UBC teams, it is extremely unlikely we will be nearly as good next year.

:)

Cutlery

I must get a complete set. Three to go!

Class Project

Here is the PPM project I have been working on. The paper may not be high quality since I had to rush to get it submitted on time. However, I am pretty excited about some of the topics it covers and the algorithm it introduces. I learned a surprising amount about information theory when researching the topic. I plan on continuing developing the algorithm and applying it to new domains.

:(

NIPS

Earlier this week I had a great time at the NIPS conference. I got to meet several famous AI researchers. The best part of the conference was the poster/demo sessions. My favourite posters were related to Hinton's Restricted Boltzmann Machines. I also got a chance to talk with some people from Numenta about HTM. Google and Microsoft Research both actively participated at the conference. Google had an interesting booth unveiling research they had done in using quantum computing for image search.

Disclaimer for the following paragraph: I know nothing about quantum computing and have a bad memory, so this information is not reliable. When I walked up to the booth I was very sceptical since as far as I know quantum computers are still theoretical. From what I understood they used adiabatic quantum computers to solve an optimization task. I think introducing the image search problem is misleading because any improvement in the image search is not necessarily due to the quantum computer. They should have introduced their image search algorithm and quantum optimization algorithm completely independently of each other. I would only be impressed if the quantum computer was solving an optimization problem faster than what can currently be done on a classical computer. I asked the Google guy the following question: "I remember seeing a proof that a certain type of adiabatic quantum computer could be simulated on a classical computer just as efficiently using simulated annealing. Any comments?" His response seemed to indicate that he thought that the quantum algorithm they were using could solve problems in polynomial time which could not be done on a classical computer. In addition, he gave a cool explanation of how the quantum computer did the optimization by simulating a particle in the search space and allowing the particle to travel through walls so that it doesn't get stuck in local minima. Also, the search space is slowly changed from an easy-to-solve "bowl" to the actual objective function so that the particle converges on the global minima. The algorithm supposedly needs to be run several times since it is stochastic and doesn't necessarily find the global minima every time.

Prediction by Partial Matching

I am currently working on a project for a natural language processing course. Given my interest in temporal pattern recognition, I decided to make the project about text prediction. For the last few weeks I have been really excited because I thought I discovered an innovative algorithm which was doing extremely well compared to existing methods. In particular, it completely outperforms my previous approaches using neural networks/HTM when it comes to almost any pattern recognition task. However, today I was disappointed to learn that almost exactly the same algorithm was discovered back in the 80s. It is a data compression algorithm called prediction by partial matching (PPM). PPM happens to be one of the best text compression algorithms, so at least its nice to know that I independently discovered it. However, I would have been much happier if I had been the first to do so.

Hockey Bears

I've done some online research on these bears, and as far as I can tell they appear to be genuine. [YouTube link]

Temporal Pattern Recognition

As an alternative to neural networks, I have found that a technique called linear predictive coding does a good job at temporal pattern recognition. I wrote a couple short scripts in MATLAB which do binary prediction and play rock paper scissors. The binary prediction seems to work better than the version I made using neural networks. I think that the RPS AI also works better than the version I made using hierarchical temporal memory, although I haven't interfaced the two programs together yet to test them.

CTV

A friend let me know that there was a clip of me on CTV. It was on a story about upgrading Vancouver's networking system for the Olympics. I was completely unaware that I had been filmed.

Genetics

Rock Paper Scissors

I have released a rock paper scissors (RPS) AI on my homepage. It was made using hierarchical temporal memory. RPS is a great domain to test temporal pattern recognition, so I am somewhat disappointed how poorly my AI does. Some people may be surprised that there is any strategy involved in RPS. After all, an AI which just outputs random moves will win 50% of the time. Humans are terrible at being random, so its not hard for an AI to win against people. When competing AI against AI, superior strategies can be determined based on their performance against a large number of opponents. This allows some AIs to get much better results than ones which just output random moves.

I have become really interested in hierarchical temporal memory since starting grad school. My supervisor Nando said that this might be a topic I can pursue for my thesis. I think there are some pretty major flaws with the implementation by Numenta. I implemented my own version using backpropagation neural networks. So far I have tested it in three applications (binary input prediction, handwritten digit recognition, and RPS). The results haven't been great. Next I plan on comparing it directly to NuPIC on their standard datasets. Hopefully my implementation does better! If so, this would be a great thesis topic.