Sunday, March 25, 2012
symbols
This is a follow-up on my last post. Here are some comparisons of two symbols generated from the same class and displayed at the same orientation. I can adjust parameters on how much variance there is between symbols within a class - the parameters I chose are fairly conservative so that most symbols should appear very similar:
A New Kind of CAPTCHA
My goal for today was to create my own CAPTCHA system. I find CAPTCHAs fascinating because of their goal of distinguishing human intelligence from machines. Surprisingly, most major CAPTCHA systems (currently used by companies such as Google, Microsoft, Facebook, etc.) are routinely solved by computers with over 15% success rates (at least according to the brief research I did on the topic today).
Most CAPTCHA systems provide an image of a sequence of characters and ask the user to type in the text. Software that attempts to solve these typically first segment the image into characters and then classify each character individually. Character classification is a solved problem - so the only security behind current CAPTCHAs relies on the fact that character segmentation is difficult. In my attempt at creating a CAPTCHA system I will try to make both the segmentation and classification tasks as difficult as possible.
One of the reasons English letter classification is so easy is because there is a massive amount of training data available for each letter. In my CAPTCHA system, I will create my own symbols and provide only *one* training example for each symbol class. My hypothesis is that humans are better than computers at extrapolating from tiny training sets. Another benefit of creating new symbols from scratch is that it makes the system internationalizable (i.e. not dependent on the character set of a particular language).
Here is an example output from my CAPTCHA program:
The answer in this case is "1428736". First, I create 10 symbol classes and present one example from each class to the user. I then generate 7 symbols from random classes (no repetition) and arrange them from left to right (allowing overlaps). The user has to enter the symbol classes in the right order. There is a 1 in 604,800 chance of guessing correct randomly, or a 1 in 10,000,000 chance if symbol repetition is allowed. The symbols are displayed in random orientation.
The symbol from a particular class will look different between the training example and the main CAPTCHA. Each class is defined by a small set random parameters. These parameters determine features such as branching factor, curviness, length, etc. Once I have generated the random class parameters, each symbol is also created via a stochastic process - but its general appearance will remain visually similar to the other symbols in its class due to the class parameters.
Well, I suspect that this CAPTCHA system will not work well in practice because it is too tedious for humans to solve. On first impression I think this task seems more difficult to solve with a computer than typical CAPTCHA systems. It would be easy to evaluate the time/precision of humans solving these CAPTCHAs with a user-study. However, evaluating the performance of software solvers is more difficult. One idea I had for evaluating software solvers is to host a contest (say on TopCoder or Kaggle) and offer a big cash prize as incentive to make competitive AIs (I won't actually do this :P).
Here are a few more random CAPTCHAs from the program. I have posted the answers at the end of this post - how many can you solve without looking at the answers?
The answers are: 0718936, 9467251, 0197283, and 7634290 respectively.
Most CAPTCHA systems provide an image of a sequence of characters and ask the user to type in the text. Software that attempts to solve these typically first segment the image into characters and then classify each character individually. Character classification is a solved problem - so the only security behind current CAPTCHAs relies on the fact that character segmentation is difficult. In my attempt at creating a CAPTCHA system I will try to make both the segmentation and classification tasks as difficult as possible.
One of the reasons English letter classification is so easy is because there is a massive amount of training data available for each letter. In my CAPTCHA system, I will create my own symbols and provide only *one* training example for each symbol class. My hypothesis is that humans are better than computers at extrapolating from tiny training sets. Another benefit of creating new symbols from scratch is that it makes the system internationalizable (i.e. not dependent on the character set of a particular language).
Here is an example output from my CAPTCHA program:
The symbol from a particular class will look different between the training example and the main CAPTCHA. Each class is defined by a small set random parameters. These parameters determine features such as branching factor, curviness, length, etc. Once I have generated the random class parameters, each symbol is also created via a stochastic process - but its general appearance will remain visually similar to the other symbols in its class due to the class parameters.
Well, I suspect that this CAPTCHA system will not work well in practice because it is too tedious for humans to solve. On first impression I think this task seems more difficult to solve with a computer than typical CAPTCHA systems. It would be easy to evaluate the time/precision of humans solving these CAPTCHAs with a user-study. However, evaluating the performance of software solvers is more difficult. One idea I had for evaluating software solvers is to host a contest (say on TopCoder or Kaggle) and offer a big cash prize as incentive to make competitive AIs (I won't actually do this :P).
Here are a few more random CAPTCHAs from the program. I have posted the answers at the end of this post - how many can you solve without looking at the answers?
Sunday, March 11, 2012
An API for Intelligence
Over the last few years I have made many attempts at creating artificial intelligence. By "artificial intelligence" I mean a general purpose system that can recognise and predict patterns in spatio-temporal data. I have written about this topic in some previous posts.
Spatio-temporal data is any data that has a temporal dimension and one or more spatial dimensions. Everything your brain perceives is a stream of spatial data over time. Any type of sensor (e.g. microphone, camera, thermometer) can create a stream of spatial data over time. The goal of artificial intelligence/machine learning/data compression is to look for patterns in this type of data and predict what the data will be in the future.
All of my AI projects have had essentially the same API. For those of you who speak Java: "double[][] perceive (double[][] inputs)". That is, a single function that takes a matrix of floating point numbers and returns another matrix of floating point numbers. The input represents spatial data at a particular moment in time and the return value from the function represents a prediction for the next input (the next time step).
A magic black box:
Let us imagine that I have a magic black box that does a great job at implementing this function. What could I do with it? Well the most obvious thing I can do is use it to predict the future. Let's use it to find out what the stock prices will be five years from now:
Of course, these estimates wouldn't be very accurate because in reality stock prices depend on a vast number of different types of data (which I didn't give to the black box as input). If I gave the black box additional data in the input matrix (such as local news stories, earning reports, weather sensors, etc.) it would do a better job at predicting stock prices.
What else could I do with the black box? If I want to have a conversation with it or make it control a robot, I would need to give it some mechanism to perform actions. Let's imagine I naively plug a light bulb into a random cell in the output matrix of the black box (and the light bulb turns on/off depending on the value of that prediction). This light bulb is now an actuator - it gives the black box a mechanism to interact with the environment. There is now a feedback loop where the black box can influence the value of future sensor readings by changing the light bulb prediction. How would the black box choose which action to take? Well, the only "goal" of the box is to minimise the difference between its predictions and what actually happens in the future. Maybe turning on the light bulb allows the black box to make more accurate predictions of future sensor values, so it "decides" to keep the light on. If I hook up a speaker and microphone to the black box, maybe it will decide that having a conversation with me will also allow it to make more accurate predictions about the future (which is probably true).
The Magic Number:
Hopefully in the previous section I convinced you that if this one function was implemented correctly, it would result in something most people would consider true AI. So, why did I choose a matrix of floating point numbers? Why not simplify the API by just making it a single array instead? Why not a higher dimensional matrix? The answer is because I think that two (as in a two-dimensional matrix) is the magic number that makes a reasonable trade-off between competing factors. Using a higher dimensional space would make implementing the function infeasible due to computational complexity. Using a lower dimensional space loses critical information about the spatial relationships between sensors. As evidence of this information loss, imagine converting a two-dimensional image into a one-dimensional array of pixels. The image would become meaningless to you because you have lost the information of how the pixels are spatially arranged.
Let us consider the most intelligent system we know of today: the human brain. I think that the human brain is complying to the same API I described above. In fact, we only need to look at a part of the brain known as the neocortex. The neocortex is a thin sheet of neurons on the outer surface of the brain. It is responsible for essentially all higher-level thought and what makes humans intelligent. Since the neocortex is fundamentally a two-dimensional surface, it uses topographic maps to project higher-dimensional signals onto a two-dimensional space. For example, the three-dimensional touch sensors on your body are mapped onto a two-dimensional homunculus on your neocortex, where regions that are neighbouring in 3D space are also neighbouring on the homunculus (and regions which are more important are mapped to larger regions on the homunculus).
So, how close are we to being able to implement AI? I think so far the most successful efforts come from the field of data compression. A compression algorithm called PAQ8 does an amazing job of implementing "boolean perceive (boolean input)". However, it doesn't scale well to continuous numbers or higher-dimensional spaces. Another promising attempt at creating AI is coming from Numenta in the form of hierarchical temporal memory. So far their attempts have been unsuccessful, but I think at a higher level their approach to the problem is the best I have seen.
Spatio-temporal data is any data that has a temporal dimension and one or more spatial dimensions. Everything your brain perceives is a stream of spatial data over time. Any type of sensor (e.g. microphone, camera, thermometer) can create a stream of spatial data over time. The goal of artificial intelligence/machine learning/data compression is to look for patterns in this type of data and predict what the data will be in the future.
All of my AI projects have had essentially the same API. For those of you who speak Java: "double[][] perceive (double[][] inputs)". That is, a single function that takes a matrix of floating point numbers and returns another matrix of floating point numbers. The input represents spatial data at a particular moment in time and the return value from the function represents a prediction for the next input (the next time step).
A magic black box:
Let us imagine that I have a magic black box that does a great job at implementing this function. What could I do with it? Well the most obvious thing I can do is use it to predict the future. Let's use it to find out what the stock prices will be five years from now:
// Training.
double[][] stockPrices;
for (Time t = TimeOfFirstData(); t < Now(); ++t) {
stockPrices = GetHistoricalStock(t);
stockPrices = blackBox.perceive(data);
}
// Predict the future.
for (Time t = Now(); t <= FiveYearsFromNow(); ++t) {
stockPrices = blackBox.perceive(stockPrices);
}
return stockPrices;
Of course, these estimates wouldn't be very accurate because in reality stock prices depend on a vast number of different types of data (which I didn't give to the black box as input). If I gave the black box additional data in the input matrix (such as local news stories, earning reports, weather sensors, etc.) it would do a better job at predicting stock prices.
What else could I do with the black box? If I want to have a conversation with it or make it control a robot, I would need to give it some mechanism to perform actions. Let's imagine I naively plug a light bulb into a random cell in the output matrix of the black box (and the light bulb turns on/off depending on the value of that prediction). This light bulb is now an actuator - it gives the black box a mechanism to interact with the environment. There is now a feedback loop where the black box can influence the value of future sensor readings by changing the light bulb prediction. How would the black box choose which action to take? Well, the only "goal" of the box is to minimise the difference between its predictions and what actually happens in the future. Maybe turning on the light bulb allows the black box to make more accurate predictions of future sensor values, so it "decides" to keep the light on. If I hook up a speaker and microphone to the black box, maybe it will decide that having a conversation with me will also allow it to make more accurate predictions about the future (which is probably true).
The Magic Number:
Hopefully in the previous section I convinced you that if this one function was implemented correctly, it would result in something most people would consider true AI. So, why did I choose a matrix of floating point numbers? Why not simplify the API by just making it a single array instead? Why not a higher dimensional matrix? The answer is because I think that two (as in a two-dimensional matrix) is the magic number that makes a reasonable trade-off between competing factors. Using a higher dimensional space would make implementing the function infeasible due to computational complexity. Using a lower dimensional space loses critical information about the spatial relationships between sensors. As evidence of this information loss, imagine converting a two-dimensional image into a one-dimensional array of pixels. The image would become meaningless to you because you have lost the information of how the pixels are spatially arranged.
Let us consider the most intelligent system we know of today: the human brain. I think that the human brain is complying to the same API I described above. In fact, we only need to look at a part of the brain known as the neocortex. The neocortex is a thin sheet of neurons on the outer surface of the brain. It is responsible for essentially all higher-level thought and what makes humans intelligent. Since the neocortex is fundamentally a two-dimensional surface, it uses topographic maps to project higher-dimensional signals onto a two-dimensional space. For example, the three-dimensional touch sensors on your body are mapped onto a two-dimensional homunculus on your neocortex, where regions that are neighbouring in 3D space are also neighbouring on the homunculus (and regions which are more important are mapped to larger regions on the homunculus).
So, how close are we to being able to implement AI? I think so far the most successful efforts come from the field of data compression. A compression algorithm called PAQ8 does an amazing job of implementing "boolean perceive (boolean input)". However, it doesn't scale well to continuous numbers or higher-dimensional spaces. Another promising attempt at creating AI is coming from Numenta in the form of hierarchical temporal memory. So far their attempts have been unsuccessful, but I think at a higher level their approach to the problem is the best I have seen.
Saturday, February 25, 2012
Project Euler
Over the last few months I have been solving programming problems on Project Euler. I currently have solved 140 out of 373 problems. Since I have been solving the problems in order of increasing difficulty, my progress will probably slow down now that I have finished solving all of the easy problems. There is a great range in the difficulty of the problems - there are probably some problems that I couldn't solve even if I spent weeks working on them. If you have a Project Euler account, feel free to add me as a friend: 13166529170291_2172f964a0c5e4a2e5a4d6e690c97cb8
Game Playtime
Today I beat The Legend of Zelda: Skyward Sword. It was an amazing game - better than The Legend of Zelda: Ocarina of Time in my opinion. I noticed at the end of the game that my total playtime was recorded as 41 hours. Out of curiosity, I have gone through some of my save files from other games and compiled a list of how long it took me to beat each game. Unfortunately the game that I probably spent the most time playing, Baldur's Gate II, doesn't record total playtime.
See this post for a list of my favorite games (four years ago).
| Title | Playtime (rounded to the nearest hour) |
|---|---|
| Dark Souls | 57 |
| The Legend of Zelda: Skyward Sword | 41 |
| Demon's Souls | 40 |
| Valkyria Chronicles | 24 |
| The Elder Scrolls V: Skyrim | 21 |
| Red Dead Redemption | 15 |
| Mass Effect 2 | 15 |
| Heavy Rain | 14 |
| Dead Space | 11 |
| Uncharted 2: Among Thieves | 11 |
| Super Smash Bros. Brawl | 10 |
| ICO | 7 |
| The Secret of Monkey Island: Special Edition | 5 |
See this post for a list of my favorite games (four years ago).
Monday, November 21, 2011
InnoCentive
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
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.
Sunday, November 20, 2011
e-sports
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.
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.
Monday, November 07, 2011
rpscontest.com is down!
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.
Monday, October 31, 2011
Google Reader
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.
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.
Sunday, October 30, 2011
DARPA Shredder Challenge
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.
Saturday, October 29, 2011
Dark Souls Defeated
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.
Friday, October 07, 2011
Dark Souls
Tuesday, September 06, 2011
Fast String Matching
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.
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.
Saturday, September 03, 2011
Gold Promotion
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 :)
Saturday, July 09, 2011
RoboCup
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
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.
Friday, July 08, 2011
Crater Detection
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.
Tuesday, June 28, 2011
Crater Detection
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:
Tuesday, June 21, 2011
Bitcoin
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.
Saturday, May 28, 2011
Saturday, May 21, 2011
Website Exploit
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
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!
Monday, May 16, 2011
Promote Me!
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 :(
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 :(
Tuesday, May 10, 2011
Starcraft II
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.
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.
Thursday, April 28, 2011
Image Compression Results
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.
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.
Wednesday, April 27, 2011
Lossy Image Compression
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.
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.
Tuesday, April 26, 2011
The Sleeping Mind
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).
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).
Sunday, April 10, 2011
Sunday, March 27, 2011
RoboCup Iran Open
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.
Monday, March 21, 2011
html5cards.org
Today I purchased a domain name for the HTML5 card game website Simon and I have been working on: html5cards.org
Tuesday, March 15, 2011
HTML5 Card Games
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.
Tuesday, March 08, 2011
Face Cards
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.
Sunday, March 06, 2011
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!
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!
Friday, March 04, 2011
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.
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.
Subscribe to:
Posts (Atom)