Today I learned...

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

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

[found here]

The Greatest Unsolved Problems

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

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

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

Ambigram

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

[link]

Kaggle

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

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

Al Zimmermann's Programming Contests

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

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

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

[link]

Lasers

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

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

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!

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

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

[link]