:)

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.

2009 Pacific Northwest Contest

Today was the ACM ICPC regional programming contest. Here is the final scoreboard:

UBC^ got first place.
Stanford got second and third place.
UVic got fourth place.
UBC+ got 10th place.
UBC* got 15th place.

There were 77 teams competing. I was on UBC*. In theory UBC* was supposed to do better than UBC+. They lucked out because one of their members knew a specific algorithm from a graph theory course which allowed them to solve a very difficult problem (which only two teams solved). Our team did really well on time, but we got completely stuck once we reached five problems. In fact, we were in first place when we got to five problems. There were two or three additional problems which were definitely solvable, but unfortunately we didn't finish them in time :(.

Nort

I have released another Java game called Nort. This is a two player game based on Tron.

Soku

Today I made a game called Soku using Java (you can play it here). It is a remake of a game I made in high school. I think it is the best of the three Java games I have made so far (the other two being Ping and Swarm). Ping is also a remake of a game I made in high school.

Photo Crasher

Circles

Two perfectly round circles:

Four perfectly round circles:

my brain hurts.

Time Stop Version 1.0

I just released version 1.0 of Time Stop. This version has eight levels. Enjoy!

w00t

My computer is finally working. After letting it dry for a couple days, I finished replacing the motherboard. Unfortunately this didn't fix any problems. I bought a nice new 1TB drive from NCIX which finally got my computer working. I guess the other symptoms I saw might have been due to a corrupt Ubuntu live CD.

Blargh

My computer has been broken for the last month. Today my new motherboard finally arrived. I decided to replace the motherboard on a picnic table outside because a) I wanted to clean my case without filling the room with dust and b) my room is too hot (it is currently 33°C outside and much warmer inside). I had a friend help me replace the components. Everything was going well until about half way through the process. Right when the computer was completely disassembled and parts were lying all over the picnic table, water starts flying at me from all directions simultaneously. Apparently the picnic table is positioned perfectly between at least three high-flow sprinklers. This was a terrifying experience since I know that water and computers do not mix well. It took several trips to get all the components out of range, so a few pieces got thoroughly soaked. I am going to leave the desktop disassembled and let it dry overnight. Hopefully the sprinklers did not destroy my computer :'(

Netflix Prize

The Netflix Prize contest is officially over. One month ago BellKor's Pragmatic Chaos made a submission with a 10.05% improvement over Cinematch. The contest ends 30 days after any submission over 10%. Yesterday a new team called The Ensemble made a submission at 10.09% accuracy (a 0.01% improvement over BellKor's Pragmatic Chaos). Today, 24 minutes before the contest finished BellKor's Pragmatic Chaos made a submission of 10.09%. Four minutes before the end The Ensemble made their final submission with a 10.10% improvement. Both of these teams were actually a combination of many smaller teams. In the end the key to victory was combining the results of a myriad of different algorithms/approaches.

Now that the Netflix Prize has finished I will start focusing on a new contest ☺. Eternity II is a puzzle with a two million dollar prize. I have written a solver using stochastic local search. My solution currently has a score of 437 out of 480. Last year the highest score was 467 (with a $10,000 prize).