Byron's Blog

InnoCentive

2011-11-21T22:40:00.001-08:00

I found a cool website called InnoCentive. They currently host 116 active competitions - some of them with million dollar prizes. Most of the contests seem to be about solving open-ended problems in science/engineering. I have made a submission to the "Strategy to Assimilate Unstructured Information" contest (which ends in four days). There is a similar website that hosts competitions for machine learning problems called Kaggle.

Facebook Removes RSS Importing

2011-11-21T00:31:00.001-08:00

When I logged into Facebook today I was greeted with this message:

That's right, Facebook is removing the ability to import RSS feeds. I am not very active on Facebook, so people commenting on my automatically imported blog posts is one of the few ways I still use the service. Now that this functionality is removed, my usage of Facebook will drop significantly. I have the suspicion they are removing it for a bad reason. I have noticed that the amount of time it takes for RSS feed items to be imported to Facebook can sometimes take several days. Why would it be so slow? Google Reader updates my feeds in a matter of minutes. I think the only reason Facebook would be so slow at importing feeds is if it is an expensive process and they don't want to spend the resources to update more often. The feature is obviously good for users, so the only reason Facebook would have to remove it is to reduce costs.

e-sports

2011-11-20T18:09:00.001-08:00

I spent the day watching the MLG Starcraft 2 championship. This is by far the most entertaining sport I have watched. I bet it would be fun to watch even for people who have never heard of Starcraft. It is definitely attracting a growing audience in the US and should start showing up on TV networks soon. I started cheering for the South Korean player Leenock while he was in the losers bracket, several rounds before the finals. I was thrilled when he continued winning round after round, making his way out of the losers bracket to eventually win the competition and a $50,000 prize. Incredibly he is only 16 years old! Before this contest almost nobody had heard of Leenock, so it was exciting to watch him defeat world-famous sc2 players one after another.

Leenock's rise to fame reminds me of another young e-sport competitor: tourist. tourist is only 17 years old but has proven himself to be one of the world's best competitive programmers. I find it shocking that tourist/Leenock can become the best at their respective fields at such a young age. It shows how genetics and innate intelligence/talent plays a crucial role in these sports, since their age obviously limits the number of years they have spent practising. I think since competitive programming is a pretty good measurement of human intelligence, tourist may also be one of the smartest people in the world. It will be interesting to keep track of what he eventually accomplishes in his career.

rpscontest.com is down!

2011-11-07T20:33:00.000-08:00

A while ago I created the site rpscontest.com - a rock-paper-scissors programming competition hosted by Google App Engine. The site is currently down due to exceeding its quota. This is because today App Engine introduced a new pricing model. With the old pricing model my quota usage was $0 per day. With the new model it is about $13 per day, or about $4,750 per year. Seriously? That is a ridiculous increase in price. Of course this basically forces me to shut down the site or redesign how it works. For now I have disabled all automatic ranked matches which should bring it back into the free quota (at the same time making the site completely useless because the rankings will no longer update). I can only assume that the price increase has a larger impact on me than typical users (possibly due to the type of resources I use to run matches). The only reason I make this assumption is because if everyone is hit by the price increase as badly as me, nobody would continue using App Engine. I am not happy.

Google Reader

2011-10-31T22:50:00.000-07:00

Today Google Reader was updated with a new UI and Google+ integration. Although the reaction on Reddit seems to be quite negative, I like the new UI. One complaint people have is that there is much more whitespace and less space for content than the older version. While this is true, it doesn't bother me because of the way I use Google Reader. I focus on one feed item at a time, using a hotkey to cycle through items. Feed items usually are a short snippet of text so don't need much space anyway.

In case anyone doesn't know what RSS feeds are or what Google Reader does, I will give a short explanation here. Many websites update a .RSS file whenever they post new content. A feed reader simply listens to a set of RSS feeds and tells you when new content is posted. Instead of manually visiting a long list of your favorite websites to find content, you can find it all organized in one place with a feed reader. RSS feeds can have other uses as well: my blog posts automatically get imported into Facebook via RSS.

I get the majority of my news/entertainment through RSS feeds, so I encourage everyone to try it out. My favorite feeds come from Reddit (and various subreddits). Webcomics are perfect for RSS feeds - some of my favorites include: xkcd, The Perry Bible Fellowship, Nedroid, Hyperbole and a Half, The Oatmeal, Penny Arcade, Buttersafe, and Abstruse Goose.

Google Reader has some interesting statistics in the "Trends" view. The graph above shows the time of day that I usually read items. Since October 7, 2005 I have read a total of 102,284 items. I can also view the number of people in Google Reader subscribed to various feeds - my blog currently has 14. Here is my blog's feed.

DARPA Shredder Challenge

2011-10-30T20:50:00.001-07:00

This weekend I started working on the DARPA Shredder Challenge. This is a contest to reconstruct shredded documents. There are a total of five puzzles and a $50,000 prize. So far I have solved one puzzle using a combination of algorithms and manual assembly. The first puzzle was pretty tough, so I am worried that I won't be able to solve any of the remaining four.

Dark Souls Defeated

2011-10-29T16:33:00.000-07:00

I managed to beat dark souls in a total of 57 hours of play time. I made heavy use of the multiplayer components of the game - summoning other players to help me defeat powerful enemies. I suspect that without taking advantage of the online functionality this game would be significantly more difficult. Overall I enjoyed Dark Souls more than Demon's Souls. Throughout the game I was stunned by the creativity and beauty of the level design. The design team must be incredibly talented since the world they created is far more immersive than any other game I have played.

Dark Souls

2011-10-07T00:08:00.000-07:00

Demon's Souls was one of the greatest games I have played. The game was so difficult that I considered giving up several times - but I eventually beat it. On Tuesday a sequel to Demon's Souls was released called Dark Souls. I am only about 5 hours into the game but so far it is incredible - maybe even better than the original. I have been warned by online reviews that Dark Souls is even harder than Demon's Souls, so I am hoping that I won't get stuck and miss out on experiencing the full game. It is interesting that such a frustrating/agonizing game is enjoyable at the same time - the joy of beating a monster makes up for the pain of spending hours trying and failing to beat the monster in previous attempts.

Fast String Matching

2011-09-06T00:15:00.000-07:00

String matching is an important problem in several fields of computer science such as bioinformatics, data compression, and search engines. I find it amazing that search engines can find exact string matches in massive datasets in essentially constant time. Having the ability to do this would be very useful for when I create data compression algorithms!

Last night I downloaded the entire English Wikipedia, which turned out to be a 31.6GiB XML file. I spent the day trying to solve the following problem: how to quickly find strings in this massive file. The hardest constraint in solving this problem is the fact that my computer only has about 3GiB of memory. Somehow I needed to preprocess the 32GiB file into 3GiB of memory and then *only* use the 3GiB of memory to find the location of arbitrary strings in constant time. Solving this problem exactly is impossible, so the goal of the project is to maximize the likelihood that the match I find is correct.

I tried doing some research online and was surprised that I couldn't find many helpful resources. This is surprising since this seems like such an important problem. I will describe the algorithm I ended up implementing:

I stored all of the data in two arrays. The first array stored positions in the XML file, type = long, dimension = 20000000x4. The second array stored counts, type = int, dimension = 20000000. The first step was to go through the 32GiB XML file and extract every substring of length 25. These substrings are keys that I used to store in the arrays. I computed a hash for each key to use as an array index. The second array was used to keep track of the number of keys put in each array position, so it is simply incremented for each key. The first array is used to store the position of up to four substrings. I stored the position of a particular key with a probability that depends on the number of colliding keys (the count stored in the second array). More collisions = less likely to store the position.

OK, so the algorithm so far preprocessed the 32GiB file into about 700MiB of memory. Now comes the fun part of using the data to do string matching. Given a string to search for, I first extract every substring of length 25. I hash each substring and collect the locations that are stored at those positions in the first array. Only a small fraction of these matches are likely to actually correspond to the string we are searching for. The essential piece of information that helps find the true match is the fact that the offset of the substrings in our search query should match the corresponding offset of matches returned from the data. It is possible to find the best match in O(n) time (where n is the length of the search query).

To sum it up: I preprocess the data in O(m) time (where m is the length of the data). I can then do string matching in O(n) time (where n is the length of the search query).

So how well did this work on the dataset? It took something like 1 hour to preprocess the XML file (basically the amount of time required to read the entire file from disk). The search queries run remarkably fast - no noticeable delay even for queries that are hundreds of thousands of characters long. The longer the search query, the more likely the algorithm is to return the correct match location. For queries of length 50, it seems to match correctly about half of the time. For queries over length 100, it is almost always correct. Success!

Interesting fact: my algorithm is somewhat similar to how Shazam works. Shazam is a program that can look up the name of a song given a short recorded sample of it. The longer the recording, the more likely the correct match is returned.

Gold Promotion

2011-09-03T20:01:00.000-07:00

I recently got promoted to gold league:

Here is the army graph for a match I am proud of:

The enemy completely destroyed my army and my main base. I think they started taking it easy after my main base went down - I made a huge comeback and eventually won the game :)

RoboCup

2011-07-09T01:22:00.003-07:00

I have been in Istanbul, Turkey for the last week at the RoboCup robotics competition. We are competing in the small size league. Today we finished our last official match. Although the final rankings have not been released yet, we think our team placed 9th (out of 20). We ranked well in the technical challenges: 3rd place in the navigation challenge and 3rd place in the mixed team challenge.

Master's Thesis

2011-07-09T01:14:00.002-07:00

I finished my master's thesis! The final copy is posted here. Now that my thesis is done I can start work at Google. My start date is July 18.

Crater Detection

2011-07-08T22:37:00.001-07:00

The contest has finished and my final ranking was 6th place. One rank away from a prize! The approach I used was using template matching and the normalized cross-correlation distance metric.

Crater Detection

2011-06-28T02:28:00.004-07:00

NASA is hosting a TopCoder marathon match to detect craters in satellite images. The contest lasts about two weeks and there are $10,000 in prizes (for the top five competitors). The task is to return a list of crater positions and sizes for a set of satellite images. There is a little over a day remaining in the contest and I am currently ranked third. If I end up doing well in the final rankings I will make a blog post about the technique I used. Here are a few example images in the training set:

Bitcoin

2011-06-21T01:18:00.006-07:00

I recently started bitcoin mining using my GeForce GTX 260. Some of my friends have invested thousands of dollars into bitcoin mining hardware and have already earned back more than they invested. Bitcoin mining seems to be the latest fad among CS students. Unfortunately my mining rate is pitifully slow, so I gave up after a few days. I earned 0.5 bitcoins in slush's pool. I held an auction for my 0.5 BTC on IRC and got payed $5 CAD for it.

Promotion

2011-05-28T03:19:00.004-07:00

I finally got promoted! I went directly from rank one in the bronze league to rank one in silver.

Website Exploit

2011-05-21T12:21:00.004-07:00

Within a few hours of launching my Rock Paper Scissors website somebody found an exploit. The exploit caused all users to be forwarded to another site. I have now fixed and prevented this particular exploit. An exciting website debut!

Rock Paper Scissors

2011-05-21T02:33:00.006-07:00

Over the last two days I implemented a new website: Rock Paper Scissors Programming Contest. It is amazing how fast a relatively complex website can be created using Google App Engine. It has probably been one of the funnest programming projects I have worked on!

I think the website could potentially lead to some innovative research. All of the submissions are open-source, so if the website becomes popular I will be very interested to see how the best AIs work. It should be possible to directly convert any RPS algorithm into a compression algorithm - there should even be a correlation between RPS performance and compression performance.

I encourage anyone who is reading this to try submitting an entry. Programming a RPS AI should be pretty fun. Python is also very easy to learn, so even people who have no programming experience should give it a try!

Promote Me!

2011-05-16T01:29:00.004-07:00

In Starcraft 2 I am currently rank 2 of bronze league. However, from what I understand the rank within a league is not very meaningful - the important number is called MMR. MMR determines league promotions and demotions. Blizzard keeps the MMR statistic hidden from players. I actually think this is a poor design decision since the benefits of releasing MMR seem to far outweigh the benefits of hiding it.

I have been practicing and optimizing a single strategy which seems to be doing pretty well. I won 17 of my last 18 matches - against bronze, silver, and gold players. The fact that I am winning against gold players should indicate that I need to be promoted from the bronze league. However, Blizzard's algorithm seems to think otherwise and wants me to stay in bronze :(

Starcraft II

2011-05-10T02:55:00.002-07:00

Last week I bought Starcraft II. The game has already been out for a year, so I am late to the party. I also never played the original Starcraft (which has been out for 13 years), so you can imagine that I am terrible at the game.

I have spent a lot of time over the last week studying and practicing. I found the beginner guide at /r/starcraft to be quite helpful. I have also been watching Husky and day[9] videos. This is my favorite match so far. I find watching Starcraft matches quite entertaining, so I anticipate that I will continue watching matches even if I stop playing the game.

I play as Terran (username: omninox). I have started focusing on a single build order that seems to be doing quite well. I have been slowly rising in the bronze league - hopefully I will be promoted to silver soon. Most of my friends are way better than me, so I have been doing 1v1s with strangers. One player I know (a friend of a friend) is ranked at the top of the master league!

I made it to the last level of the campaign on hard difficulty. After a number of retries on the last level, I gave up and beat it on normal. I have also started playing two custom Starcraft games: starjeweled and desert strike. I have been using starjeweled as a way to relax between 1v1 rounds - I find 1v1 to be quite mentally exhausting. Desert strike is a great way to practice unit counter strategies. If you play Starcraft, send me a friend request and maybe we can play sometime.

Image Compression Results

2011-04-28T02:43:00.015-07:00

Here are some more results comparing JPEG at the maximum compression level to my image compression algorithm:

Original image:

JPEG (15.7KiB):

My algorithm (3.2KiB):

Original image:

JPEG (6.3KiB):

My algorithm (2.0KiB):

Original image:

JPEG (6.2KiB):

My algorithm (3.9KiB):

Original image:

JPEG (11.2KiB):

My algorithm (2.8KiB):

Original image:

JPEG (7.1KiB):

My algorithm (3.0KiB):

Original image:

JPEG (5.9KiB):

My algorithm (1.5KiB):

Original image:

JPEG (16.4KiB):

My algorithm (4.0KiB):

All of the above images are around 1MiB when uncompressed. In every case my algorithm resulted in a smaller file size and a (arguably) better looking image.

Lossy Image Compression

2011-04-27T14:48:00.006-07:00

Last night I wrote a lossy image compression algorithm. It is based on an idea from this paper. First I trained a set of 256 6x6 color filters on the CIFAR-10 image dataset. To train the filters, I used the k-means algorithm on 400,000 randomly selected image patches. Here are the resulting filters:

I then used the filters to compress the following image:

Using the maximum compression level, JPEG compresses the image to 7.1KiB:

My compression algorithm compresses the image to 5.6KiB:

Try clicking on the above images to see the high resolution versions. My compressed version of the image is smaller and looks better than JPEG.

I did the compression by doing a raster scan of the image and for each image patch I select the best filter. I then losslessly compress the filter selections using paq8l. The obvious improvement to this algorithm would be to use a combination of several filters for each image patch instead of selecting the best filter. Using several filters would take more space to encode but would result in a much better image approximation. Another idea I plan to try is to use this same algorithm for lossy video compression.

The Sleeping Mind

2011-04-26T00:27:00.006-07:00

I occasionally wake up from a dream and immediately realize how flawed my logic was. Although I rarely remember any of my dreams, I have definitely woken up and thought to myself "haha, my sleeping mind must be really stupid to have come up with that conclusion." However, I have encountered a few counterexamples which indicate that my sleeping mind can be productive.

When I am falling asleep I usually spend my time thinking about some challenging problem. My theory is that if I fall asleep while thinking about a problem, my sleeping mind might churn away during the night and make progress on the problem. Although this usually isn't the case, there have been a few instances when I wake up and I have the answer.

A few years ago I was stuck on a programming problem on a cpsc313 assignment. It was late at night, I wasn't making any progress, so I went to sleep. I woke up in the middle of the night and immediately knew how to solve the question. I was so excited that I spent a few minutes implementing the solution, verified that it worked, and then went back to sleep.

Last night I went to sleep trying to think of an idea for a project to implement on Google App Engine. This morning I was surprised to find that I had a complete project idea in mind (including the algorithms needed to implement it!). I don't particularly like the idea and I don't think I will implement it, but I was shocked to find that I could come up with an original idea with non-trivial algorithmic details while I was asleep.

The idea was to develop a website for people looking for recommended places to travel. The website would first ask a series of 5-10 binary questions. The questions would provide a brief description of two travel destinations. The user would then click on the destination they would prefer travelling to. After they complete the questions a ranked list of travel recommendations would be given to the user (the list would contain many more destinations than were asked in the questions). Using some basic machine learning, the travel recommendations would become more accurate as more people use the website. The answers to the questions serve two purposes: 1) to assign the user to a cluster of like-minded individuals in order to generate a ranked destination list and 2) to rank travel destinations for all users in that cluster. Although I don't particularly like this project idea, I do like the algorithm it uses. I can imagine that this same algorithm could be used for other project ideas (although I haven't thought of any good ones yet).

Rex

2011-04-10T15:34:00.002-07:00

[link]

RoboCup Iran Open

2011-03-27T18:49:00.003-07:00

Next week I was planning to travel to Iran with the UBC RoboCup team to compete in the Iran Open. After the competition I was planning on doing some travelling in Thailand. Unfortunately, the trip got cancelled. Since UBC is one of the team sponsors, they have a policy which requires that we get permission to travel to DFAIT level 3 regions. The official response was that the faculty would not give approval for the trip (due to the current threat level and the fact that the trip is not academically essential). Since we had already purchased plane tickets, the cancellation cost the team quite a bit of money. In July our team will be travelling to Turkey to compete in RoboCup 2011.

html5cards.org

2011-03-21T21:26:00.002-07:00

Today I purchased a domain name for the HTML5 card game website Simon and I have been working on: html5cards.org

HTML5 Card Games

2011-03-15T02:49:00.002-07:00

Simon and I have been making steady progress on our multiplayer card game website. The project is currently hosted at http://html5cards.appspot.com. We have implemented one game so far (German Bridge) which should be mostly functional. Let us know if you see any bugs or have feedback.

Face Cards

2011-03-08T12:42:00.005-08:00

I have released a new version of my vector playing cards. It turns out the designs for the face cards are in the public domain. I compared several brands of cards and they use the exact same designs. I scanned the cards and vectorized them using potrace. After vectorizing them I did a lot of touch-up work using Inkscape.

Today I learned...

2011-03-06T02:08:00.005-08:00

...that I am currently travelling at the speed of light. In fact, all objects in the universe are travelling at exactly the same speed. Although I am travelling slowly in the three spatial dimensions, I am travelling quickly in the time dimension. The combined speed of any object through the four spacetime dimensions is exactly the same. Light travels completely in the three spatial dimensions and doesn't travel at all through time. Photons never age. This also explains why we can't travel faster than the speed of light.

I am quite surprised I didn't learn this fact earlier in life. I somehow managed to make it through physics and astronomy classes learning about Einstein's relativity without ever making this simple connection!

Vector Playing Cards

2011-03-04T01:46:00.005-08:00

I have started working with Simon on a project to create a multiplayer card game website hosted by Google App Engine. For the website we need high quality images of each poker card. Ideally the images would be in a vector format so that we can scale them to any resolution. We found that there are not many options that don't have restrictive licenses (here is one exception).

Instead I decided to create a deck of vector graphics cards from scratch using Inkscape. I created most of the artwork myself except for the ace of spades:

I based this design on artwork by Suzanne Tyson. Since the source image was rasterized, I used the potrace algorithm to vectorize it.

I am releasing the images into the public domain. This means that they can be used for any purpose without any attribution (although attribution would be appreciated). I have created a Google Code project to host the SVG source code and also posted pictures of the cards to my Picasa account.

Climate Change

2011-02-28T21:15:00.005-08:00

[found here]

The Greatest Unsolved Problems

2011-02-25T14:21:00.026-08:00

In 2000, the Clay Mathematics Institute published a list of seven unsolved problems in mathematics called the Millennium Prize Problems. There is a prize of US$1,000,000 for solving each problem. One of these problems has already been solved. In 1900, David Hilbert published a list of 23 unsolved problems in mathematics. Looking at the status of these problems on Wikipedia, only five of them remain unresolved.

Although there are many unsolved problems in science and mathematics, we have been making steady progress in solving open problems. Fermat's Last Theorem was conjectured in 1637 and was solved in 1995. The four color theorem was stated in 1852 and proven in 1976. Throughout human history we seem to be systematically progressing and accumulating scientific knowledge.

I have compiled a list of what I consider to be the five most important unsolved problems. Ranking the importance of problems is of course subjective. Biologists would probably be biased towards biology problems and physicists towards physics problems. I have tried to avoid being too biased towards computer science problems. Here is the list, ranked from most important to least:

1) Theory of Everything:

The Theory of Everything (TOE) is the most important unsolved problem in physics. As the name suggests, this theory would fully explain all known physical phenomena in the universe. The complexity of the universe does not necessarily mean that TOE needs to be complex. As observed in chaos theory and cellular automaton, a set of extremely simple rules can lead to incredible complexity. Albert Einstein spent the last few decades of his life searching for TOE (which he referred to as unified field theory). He failed.

Einstein's general theory of relativity explains the universe at large scales. So far, all experimental evidence confirms general relativity. Quantum mechanics explains the universe at the scale of subatomic particles. Once again, all experimental evidence confirms quantum mechanics. Unfortunately, these two theories can not both be right. In extreme conditions like black holes and the Big Bang, these theories seem to contradict each other. String theory seems to be a promising candidate for a TOE. It resolves the tension between general relativity and quantum mechanics. However, string theory has yet been unable to produce testable experimental predictions.

2) Intelligence:

There are several definitions of intelligence. When comparing the intelligence of animals, most people agree that humans are more intelligent than dogs and dogs are more intelligent than goldfish. How can we quantify intelligence? Several tests have been created that attempt to measure and compare human intelligence (such as the IQ test). Some of these tests are based directly on pattern matching and prediction skills.

Based on my research in the field of data compression, I have my own definition of intelligence which is easily quantifiable. Intelligence can be measured by the cross entropy rate of a predictive compression algorithm on multidimensional sequence data. This basically means that an algorithm which is better at predicting temporal patterns in data is more intelligent. The human brain is extremely good at recognising and predicting patterns in the massively parallel sensory data it processes.

Most data compression algorithms work on one-dimensional sequence data. For example, text is a one-dimensional sequence of characters. Studies have been performed to try to measure the cross entropy rate of humans trying to predict the next character in a natural language text sequence: 0.6 to 1.3 bits per character. The best text compression algorithms (such as PAQ8) are starting to approach the upper end of this range. Unfortunately, compressing one-dimensional data is easy compared to high-dimensional data. In my opinion, any compression algorithm which could approach the predictive capability of the human brain on billions of parallel inputs would be truly intelligent. The most promising framework I have seen for explaining the algorithm behind human intelligence is hierarchical temporal memory.

If humans are so intelligent, what is the point of making intelligent machines? Well, if we could design an algorithm which becomes more intelligent just by giving it more computational resources, we could make it arbitrarily intelligent. If it could surpass human intelligence, there could be a singularity in which the AI can design a new AI which is even more intelligent than itself (ad infinitum). Achieving this would allow AI to solve the other four open problems on this list (assuming they are solvable!).

3) Dark Energy and Dark Matter:

Experiments indicate that the universe is expanding at an accelerated rate. This is surprising because mass in the universe should cause gravity to slow its expansion. Dark energy is currently the most accepted theory to explain the expansion. Not much is known about dark energy besides the fact that based on its effect on expansion, about 74% of the universe is dark energy.

So if 74% of the universe is made up of dark energy, you might assume the rest of it is the visible universe. Wrong. The visible universe only accounts for about 4%. The other 22% is known as dark matter. Once again, not very much is known about dark matter. Advances in our understanding of dark energy and dark matter would provide insight into the nature of our universe and its eventual fate.

4) One-way Functions:

Any computer scientists reading this post might be surprised by the fact that the P = NP problem is not on my list. As Scott Aaronson points out, solving the P = NP problem could have a huge impact:

If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...

The problem is that most people assume that P ≠ NP. Although a proof of this would have some theoretical value, it would not have a large impact. This is why the problem got bumped off my list.

The existence of one-way functions is another famous problem in computer science. The existence (or non-existence) of one-way functions would have a bigger impact than proving that P ≠ NP. In fact, the existence of one-way functions would in itself prove that P ≠ NP. If one-way functions do not exist then secure public key cryptography is impossible. Either outcome results in a useful result.

5) Abiogenesis:

Abiogenesis is the study of the origin of life on Earth. Having little chemistry/biology background, I can't give a very good comparison between different abiogenesis theories. However, I can appreciate the importance of understanding how life arose. Not only would it enhance our knowledge of life on Earth, it would assist in the search for extra terrestrial life.

Machine Learning Contests

2011-01-12T23:15:00.004-08:00

I just found another machine learning contest site called TunedIT. TunedIT seems to be very similar to Kaggle. On first inspection one of the TunedIT contests seemed to be very interesting - categorizing the genre and instruments in music. My current area of research involves one dimensional time-series data, so I thought audio would be an interesting domain to work with. Unfortunately, instead of providing the raw audio data, the contest organizers decided to process the audio and provide feature vectors instead. No longer being a one-dimensional temporal problem, the contest has lost much of its appeal.

I have been treating the traffic prediction contest on Kaggle as a one-dimensional temporal prediction problem (considering every road segment as a completely independent problem). I am currently ranked 8th out of 214 teams. I am guessing that my ranking won't improve before the contest end because I don't have any new ideas on how to increase my score. Most of my submissions so far have been used for parameter tuning. However, my parameter tuning efforts seem to have reached a local optimum.

Ambigram Failure

2011-01-11T19:46:00.003-08:00

Two people who don't know my name tried to decrypt my ambigram. Their responses were "liynh knoll" and "liymr uwnq". :(

Ambigram

2011-01-11T04:49:00.004-08:00

Today I tried to make my first ambigram:
After staring at it for several hours and making minor adjustments, I still have no idea how legible it is. I guess a good test would be to show it to someone who doesn't know my name and see if they can decipher it.

Captcha

2011-01-05T20:06:00.002-08:00

[link]

Kaggle

2010-12-24T22:26:00.004-08:00

I recently found a great website which hosts competitions related to machine learning. I am currently competing in the freeway travel time contest and the grant proposal contest. I think Kaggle has potential to be very successful. The contest sponsors benefit by getting good solutions to tough problems at a relatively low cost. The contest participants benefit by getting access to interesting problems and the potential of winning cash prizes.

Christmas in Sri Lanka

2010-12-24T22:09:00.003-08:00

From left to right: Nathan (dad), Archie (dog), Martha (mom), George (tortoise), Skylor (brother), Aaron (brother), Byron (me).

Al Zimmermann's Programming Contests

2010-12-03T23:17:00.002-08:00

Over the last couple of days I have been working on a programming contest called Topswops. I am currently ranked 31 out of 312. This is the third Al Zimmermann programming contest I have competed in. The site has some very interesting optimization problems. In my first two contests I ranked 65 out of 414 and 49 out of 143.

Game Review

2010-12-03T23:09:00.002-08:00

I noticed that somebody wrote a review about the laser game I made. The game got quite a bit of traffic when I posted a link to it on Reddit. I am pleased.

Lasers

2010-11-22T03:01:00.002-08:00

Thanks to everyone for the useful feedback on my Laser game so far. I have added another three levels, making a total of ten. I am trying to order the levels in increasing difficulty. However, I am having trouble comparing the difficulty of levels (since I already know the solution to levels when I design them, it is hard to judge how hard it would be for someone else to solve them). It would be great if I could get some more feedback on if you encounter an earlier level which appears to be more difficult than a later level.

Batman

2010-11-18T22:58:00.001-08:00

[link]

Lasers

2010-11-18T22:28:00.003-08:00

My laser reflection game now has seven levels. I have found that it is much easier to create levels for this game than it was for the art gallery problem game. I think the last two levels are quite challenging, so let me know if you manage to beat them.

Lasers

2010-11-14T21:02:00.004-08:00

Today I started working on a new Java game. It will be a geometry-based puzzle game. The idea is to position mirrors so that they reflect lasers to a set of targets. I have posted a prototype version here.

State of the Art

2010-11-14T13:47:00.002-08:00

For my master's thesis I have been looking into compression-based techniques for classification, clustering, and anomaly detection. I have implemented a classification algorithm using PAQ and evaluated it on three datasets. So far the results look very promising and it seems to get state of the art results on all three datasets. The first dataset (called 20news) involves categorizing newsgroup articles into one of twenty categories. The other two datasets are spam-filtering (ling-spam and PU1). For the spam-filtering datasets a tradeoff can be made between spam/ham misclassification rates. I therefore evaluated my algorithm using ROC curves. Although my algorithm wasn't the best spam-classifier on all portions of the ROC curves, on both datasets there was still a significant portion in which it got state of the art results.

It's Alive!

2010-10-29T19:20:00.002-07:00

After the suitcase incident, my desktop has been broken for the last six months. Earlier this week I replaced its motherboard. When I tried booting, I was disappointed to hear that it was still just beeping error codes. However, the error codes this time indicated a memory problem (which is different from the beep codes I was hearing before). I identified the damaged stick of RAM and removed it. Finally my computer seemed to boot normally, except that it unexpectedly turned off about 30 seconds later. I identified this problem to be due to the heatsink not attaching properly to the CPU. I ordered a new heatsink from Ebay and it arrived today. I just put in the new heatsink and the computer seems to be functioning normally. yay. In total, transporting my desktop in a suitcase destroyed the motherboard, one stick of RAM, and the CPU heatsink.

Art Gallery Problem

2010-10-17T02:39:00.002-07:00

My art gallery game now has seven levels. Designing challenging levels is surprisingly difficult. Today I implemented mirrors which reflect the guard visibility polygons (seen in the screenshot above). Hopefully mirrors will allow me to create harder levels.

Logarithmic Scales

2010-10-04T00:48:00.003-07:00

[link]

Genius

2010-10-04T00:42:00.003-07:00

[link]

Art Gallery Problem

2010-10-03T23:57:00.004-07:00

I was looking through Wikipedia's list of NP-complete problems to try to come up with an idea for a game. A few of the problems on the list have already been made into games. I thought the art gallery problem might make an interesting game. My research on Google suggests that it has never been adapted into a game before. I spent the day implementing the game and have posted it online here. So far I have only made four levels but I plan on adding more soon.

Google Offer

2010-09-30T12:29:00.003-07:00

I just accepted a job offer from Google! The position is Software Engineer. After I finish my master's degree, I will be moving to Mountain View, California.

ACM Eligibility

2010-09-27T21:10:00.002-07:00

During the last two weekends I competed in tryouts to be part of the UBC programming team. I did well enough to qualify for the first team. However, yesterday I noticed on the 2010 ACM eligibility chart that I am ineligible because I am slightly too old (by four months). We tried emailing the ICPC manager but she verified that I can not compete :(

Happy Petrov Day!

2010-09-26T21:08:00.001-07:00

Thank you Stanislav Petrov for saving the world on September 26, 1983.

Sri Lanka

2010-08-18T01:50:00.002-07:00

Last week I finished my internship at Google. I have been in Sri Lanka for about a day now. Cathay Pacific managed to lose both of my suitcases on the way here. So far I like Sri Lanka. It seems to be similar to India except better in a number of ways.

Homework

2010-08-12T23:08:00.003-07:00

Translation courtesy of reddit user thelifan:

My life here is terrible. Work environment is not great and benefits are little. But don't worry, everyday only about 10 people are seriously injured and I'm very careful. We opened a small shop, business isn't bad. Although I don't understand very much English, but I can still understand what white men say. Hopefully we can become successful, I will work hard and take care of myself.

Are you guys well? Miss you very much, hope to see you again.

Skydiving!

2010-08-07T22:32:00.003-07:00

This morning I went skydiving from 15,000 feet. It was an incredible experience. The free-fall lasted for about one minute and parachuting lasted five minutes. The "falling" sensation only lasted for a few seconds after leaving the plane. Once reaching terminal velocity, the free-fall was quite comfortable (and surreal). My instructor let me control the parachute for part of the descent. We also performed a fun maneuver spinning the parachute around in a tight spiral. A few years ago I went bungee jumping. I think making the jump was probably scarier for bungee jumping than skydiving. However, I enjoyed everything about skydiving a lot more than bungee jumping.

Skydiving!

2010-07-28T15:22:00.002-07:00

Next week I am planning to go skydiving with some Google interns. Should be fun!

YouTube Easter Egg

2010-07-25T00:46:00.003-07:00

For YouTube videos with the new layout style, performing the following steps will start up a game of Snake:

1) Click on the video to give it keyboard focus
2) Hold the left arrow key

Here is a YouTube video that it will work on. Discovered via Reddit.

Body Invaders

2010-07-18T14:12:00.011-07:00

[YouTube link]

[YouTube link]

[YouTube link]

National Geographic

2010-07-18T14:08:00.002-07:00

New Camera!

2010-07-18T01:16:00.003-07:00

I am now the proud owner of a Panasonic Lumix DMC-ZS7. Today I took some photos with it around the Google campus. One of my favorite features of the camera is that it tags pictures with GPS coordinates. Picasa Web Albums automatically creates a Google Map with the photo locations.

Demon's Souls

2010-07-11T22:31:00.003-07:00

Today I finally beat Demon's Souls. I am pretty proud of this accomplishment given how ridiculously hard the game is. It is the best PS3 game I have played.

RoboCup 2010

2010-06-22T18:10:00.002-07:00

I am currently in Singapore attending RoboCup 2010. UBC Thunderbots is competing in the small size league. We played four games and did not advance to the semi-finals. We lost three games and won one game. The Thunderbots website has lots of pictures, videos, and a blog. I will be in Singapore for one week.

TopCoder Open

2010-05-20T00:38:00.002-07:00

Today I discovered that TopCoder is hosting an interesting marathon match over the next month. The problem is pretty simple:

Input: list of edges
Output: vertex locations
Goal: minimize number of edge intersections

There is an online scoreboard which shows your ranking after each submission. I was in last place after my first submission. My second submission was quite an improvement and put me in second place =)

siarco

2010-05-17T23:35:00.003-07:00

I just released an open source version of the arithmetic coder I discussed in my previous post. The project is hosted at http://code.google.com/p/siarco/.

Nice Weather

2010-05-16T13:51:00.005-07:00

[link]

Arithmetic Coding

2010-05-16T12:47:00.002-07:00

This week I wrote a program to perform arithmetic coding. Arithmetic coding is useful for data compression. This summer I plan to release an open source lossless data compression algorithm which uses the coder.

The program to do the arithmetic coding is only around 150 lines of Java code. For a while I had a really annoying bug related to precision errors with floating point numbers. The vast majority of the time I spent developing the program was trying to fix this bug. Today I finally figured out a great solution to the precision problem which has almost no computational overhead and is theoretically guaranteed to always be correct.

Wikipedia claims "every programmatic implementation of arithmetic encoding has a different compression ratio and performance." I find this statement surprising because I think I can construct a proof showing that my program encodes the input with exactly the minimal number of bits. If the number of bits is not divisible by 8, my program uses a few extra bits in order to store the resulting bytes to disk. As far as I know it is impossible for another arithmetic coder to achieve a better compression ratio. I tried testing the program on several files and it achieved a compression ratio extremely close to the theoretical cross entropy limit.

In terms of performance my algorithm also has nice properties. The time and space complexity are both linear in terms of the number of input characters (which is optimal). The code only performs basic arithmetic operations on primitive data types, so it should also be very efficient. The code works with any input alphabet size. I plan to convert the program to optimized C code and compare its performance to other arithmetic coders. Since I am already confident that its compression ratio can not be beaten, if it turns out to be faster than other arithmetic coders as well, then my algorithm could be an important contribution =)

Googleplex

2010-05-09T21:05:00.004-07:00

I really enjoyed my first week at Google. So far I have mostly been doing training. The food at the Googleplex is amazing. I will be eating breakfast, lunch, and dinner there, so I will only have to cook for myself on weekends. I have been trying to go to a different café for every meal. My apartment is about a 30 minute bike ride from the campus, so that exercise might help counteract the abundance of free food. Google gave me a nice bike to use over the summer.

Yesterday I bought a new monitor so that I can play my PS3. I also bought a game called Demon's Souls. I tried getting Demon's Souls at three different places in Vancouver but they were all sold out. In Mountain View I tried checking Best Buy and Toys Я Us but they were also sold out. Finally, I found a copy at Game Stop (which turned out to be their last copy). The ridiculous thing is that this game was released over half a year ago. The gameplay is incredibly addicting (and incredibly difficult). It is the best PS3 game I have played.

Suitcase Computer

2010-05-09T20:40:00.003-07:00

I recently discovered that traveling with a desktop computer in a suitcase is a bad idea. When I was packing for my trip to Mountain View I spontaneously decided to bring my desktop computer since I had lots of extra room in my suitcases. I have traveled with a desktop computer before without any problems.

The first annoyance was that both my suitcases were way over the weight limit, so I was charged expensive overweight fees. I would have been under the weight limit without the computer. When I arrived in Mountain View and started unpacking the computer, I noticed a horrible rattling sound when I moved it. A rattling sound indicating loose components in the case.

The CPU heatsink had somehow become detached and was bouncing around inside the case the entire trip. Today I bought some thermal grease and reattached the heatsink. When I tried to boot the computer it started making beeping sounds and immediately shutdown. It is most likely the motherboard which was damaged. I wish I had just left the computer in Vancouver.

Imagine Cup

2010-04-10T05:17:00.004-07:00

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

2010-04-02T20:11:00.002-07:00

Googleplex

2010-03-30T09:42:00.002-07:00

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

2010-03-22T15:32:00.002-07:00

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

2010-03-15T14:51:00.002-07:00

Contests and Interviews

2010-03-14T23:29:00.003-07:00

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

2010-03-06T03:32:00.002-08:00

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

2010-02-17T21:05:00.004-08:00

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

2010-02-06T22:45:00.002-08:00

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.

:)

2009-12-22T19:53:00.002-08:00

Cutlery

2009-12-21T03:00:00.004-08:00

I must get a complete set. Three to go!

Class Project

2009-12-16T00:09:00.006-08:00

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.

:(

2009-12-14T22:49:00.002-08:00

NIPS

2009-12-13T22:40:00.003-08:00

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

2009-12-13T20:54:00.004-08:00

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

2009-12-01T00:17:00.003-08:00

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

2009-11-19T09:09:00.003-08:00

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

2009-11-10T01:45:00.004-08:00

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

2009-11-08T22:15:00.001-08:00

Rock Paper Scissors

2009-11-08T21:35:00.004-08:00

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

2009-11-07T22:03:00.006-08:00

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

2009-11-06T23:21:00.003-08:00

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

Soku

2009-11-01T01:28:00.004-07:00

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

2009-08-22T21:13:00.002-07:00

Circles

2009-08-10T18:46:00.004-07:00

Two perfectly round circles:

Four perfectly round circles:

my brain hurts.

Time Stop Version 1.0

2009-08-10T18:26:00.001-07:00

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

w00t

2009-08-05T19:44:00.004-07:00

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

2009-07-29T20:00:00.003-07:00

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

2009-07-26T21:53:00.003-07:00

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).

Rhythm Recognition

2009-07-19T19:46:00.002-07:00

I just posted a new applet on my website which can learn simple rhythms. The rhythms are input by clicking on a button. I plan on creating a few more applets which demonstrate some of the things temporal pattern recognition can be used for.

I actually think that temporal pattern recognition can be used for any task which requires intelligence. Intelligence is equivalent to the ability to recognize and predict patterns. The only reason that we haven't created intelligent AI is because pattern recognition is a difficult problem. Since the code I am using to recognize patterns is terrible compared to what most animals can accomplish, my demos will have to be constrained to relatively simple problems.

Low Ink

2009-07-16T10:24:00.000-07:00

[link]