August 5, 2010 1:06 am by Markus.

Kaggle has a new and interesting competition on building a chess rating algorithm that performs better than the official Elo rating system currently in use. Entrants build their own rating systems based on the results of more than 65,000 historical chess games and then test their algorithms by predicting the results on a holdout set of 7,800 games.

Looks like an interesting problem. The only other thing that comes to my mind literature-wise is that Microsoft built and published their TrueSkill™ Ranking System for the XBox in order to match players with similar skills in online games. In the original paper at NIPS, the authors had shown that TrueSkill outperformed Elo.

Posted in Statistics, Machine Learning | Print | No Comments »

July 11, 2010 8:56 pm by Markus.

Interesting article:  GraphLab: A New Framework for Parallel Machine Learning

From the abstract:

Designing and implementing efficient, provably correct parallel machine learning (ML) algorithms is challenging. Existing high-level parallel abstractions like MapReduce are insufficiently expressive while low-level tools like MPI and Pthreads leave ML experts repeatedly solving the same design challenges. By targeting common patterns in ML, we developed GraphLab, which improves upon abstractions like MapReduce by compactly expressing asynchronous iterative algorithms with sparse computational dependencies while ensuring data consistency and achieving a high degree of parallel performance. We demonstrate the expressiveness of the GraphLab framework by designing and implementing parallel versions of belief propagation, Gibbs sampling, Co-EM, Lasso and Compressed Sensing. We show that using GraphLab we can achieve excellent parallel performance on large scale real-world problems.

Given all the talk about Map-Reduce, Hadoop etc. this seems like a logical next step to make scaling data mining to large data sets a lot easier.

Posted in Data Mining, Machine Learning | Print | 1 Comment »

June 15, 2010 8:21 pm by Markus.

I had some problems setting PHP values for shared hosting on 1and1 and the suggested way from their FAQ using php.ini didn’t work for me. Here are the settings in .htaccess that worked for me:

AddType x-mapp-php5 .php

# PHP 4, Apache 1
<IfModule mod_php4.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
</IfModule>

# PHP 4, Apache 2
<IfModule sapi_apache2.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
</IfModule>

# PHP 5, Apache 1 and 2
<IfModule mod_php5.c>
php_value magic_quotes_gpc 0
php_value register_globals 0
php_value session.auto_start 0
</IfModule>

This instructs the server to use PHP5 and the configuration below is turning off the magic quotes, register globals and session auto start features.

Posted in Fixing Stuff | Print | No Comments »

February 28, 2010 12:21 pm by Markus.

I was a bit amused to read about this new algorithm that IBM research developed and that was sold as “energy efficient” in their press-release. This is good marketing, because the average journalist and reader might not understand the impact of the improvement. It just sounds a lot better to be green and save energy than to improve computational complexity…

Posted in Data Mining | Print | No Comments »

February 16, 2010 11:56 pm by Markus.

How can one evaluate the performance of prognostic models in a meaningful way? This is a very basic and yet an interesting problem especially in the context of prediction of very rare events (base-rates <10%). How reliable is the model’s forecast? This is a good question and of particular importance when it matters - think criminal psychology where models forecast the likelihood of recidivism for criminally insane people (Quinsey 1980). There are a variety of ways to evaluate a model’s predictive performance on a hold out sample, and some are more meaningful than others. For example, when using error-rates one should keep in mind that they are only meaningful when you consider the base-rate of your classes and the trivial classifier as well. Often this gets confusing when you are dealing with very imbalanced data sets or rare events. In this blog post, I’ll summarize a few techniques and alternative evaluation methods for predictive models that are particularly useful when dealing with rare events or low base-rates in general.

The Receiver Operator Characteristic is a graphical measure that plots the true versus false positive rates such that the user can decide where to cut for making the final classification decision. In order to summarize the performance of the graph in a single, reportable number, the area under the curve (AUC) is generally used.

Read the rest of this entry »

Posted in Statistics, Classification, Data Mining, Machine Learning | Print | 2 Comments »

January 26, 2010 9:54 pm by Markus.

The New Scientist describes a new method for spam detection by learning patterns. This new method exploits the spammers most powerful weapon - the automatic generation of many, similar messages by automated means (i.e., some grammar in a formal language) - and turns it against them. The article reports that a pattern can reliably be learned from about 1000 examples captured from a bot, allowing the method to classify new messages accurately and with zero false positives. This sounds really exciting given my full spam-folder.

However, I’m a bit cautious. The article is a bit sparse on technical details, so I might make some wrong assumptions here. First, zero false positives reported is the discrimination of spam from that particular spam-grammar versus other messages. At least that’s how I understand it. Second, it seems from the article that they only learn from positive examples. Overall the technique sounds to me like they are learning a pattern language. Pattern languages are a class of grammars that overlap with linear and context-sensitive grammars (Chomsky hierarchy). Unfortunately they don’t have a real Wikipedia page so I’ll try to give a bit of background. The closest I can give for an example right now would be regular expressions with back-references. I’m not sure if this is an accurate description for all possible patterns, but it’s close enough for an example.

I don’t know how the specific technique mentioned in the article works in detail, but I’ve learned two things about learning grammars from text: (a) we can’t learn all linear or context-sensitive languages, only all pattern language grammars; (b) learning patterns without negative examples leads to over-generalization really really fast.

While I haven’t worked with learning grammars in a long while, the only algorithm of which I’m aware is the Lange-Wiehagen algorithm (Steffen Lange and Rolf Wiehagen; Polynomial-time inference of arbitrary pattern languages. New Generation Computing, 8(4):361-370, 1991). This algorithm is not a consistent learner, but can learn all pattern languages in polynomial time. There might be better ones available by now, but learning grammars is not that popular in the machine learning community right now. I’m sure there are some other interesting applications besides spam filtering. Maybe it’s time for a revival.

Overall, it sounds like a promising new anti-spam technique, but I’d like to see some more realistic testing done. There are some obvious ways for spammers to make learning these patterns harder, but either way I’m curious - maybe the inventors of this technique discovered a better way to learn patterns? Maybe by using some problem-specific domain knowledge?

Posted in spam, Machine Learning | Print | No Comments »

January 10, 2010 5:37 pm by Markus.

Just in time for the latest Christmas terror scare, I came across an interesting paper: “Strong profiling is not mathematically optimal for discovering rare malfeasors” (William H. Press; PNAS 106(6), p. 1716-1719 www.pnas.org/cgi/doi/10.1073/pnas.0813202106). In the paper, the author investigates whether profiling by nationality or ethnicity can be justified mathematically and tries to answer the question of how much screening must we do, on average, to catch the bad guys in the crowd. Rare events detection is hard as it is, and it’s interesting to see a look from the sampling perspective. It’s an interesting and short read. Long story short, it shows that using an indiscriminate feature like nationality or ethnicity is not optimal (as is any screening at least in proportion to a prior probability) and wastes resources.

Posted in Math, Society, Statistics | Print | 1 Comment »

November 13, 2009 12:27 am by Markus.

UCSC is holding a Starcraft AI competition. I wish I had the time to participate… Starcraft is one of my all time favorite games, and writing a better AI for a real-time strategy game is certainly interesting and challenging.

Posted in Artificial Intelligence (AI) | Print | No Comments »

July 25, 2009 8:34 pm by Markus.

Quick note: One of the strangest things I’ve seen in a while was during my desktop’s boot-up today. There were random lines across the manufacturer’s BIOS logo, then all sorts of weird and random characters during BIOS messages and boot-manager. The monitor was fine, the power-on self test didn’t indicate anything fishy and even Linux would boot fine (but only in 640 x 480 resolution). If it had been the RAM or something, chances would be that the OS would have crashed or complained. Obviously it wasn’t a driver or OS issue as the computer hadn’t even booted up yet. It turns out it was the graphics card (an old 7xxx nVidia) and replacing it with a newer one did the trick. I’m a bit puzzled how the graphics card could have caused all those weird characters to show up, but I’m guessing the graphics RAM might have died or something like that.

Posted in Fixing Stuff | Print | No Comments »

June 7, 2009 5:04 pm by Markus.

Ok, this post is more of a rant. I’m one of those people that are a bit impatient when starting a program on my desktop. When I start up my Windows machine I click on several buttons in the “quicklaunch” bar to fire up what I’ll need to use - Outlook, R / SPSS /SAS, Winamp etc. So why do all sorts of dialogs pop up in my face while I am typing? Why does winamp have to pop up while I’m typing my email password? And why do they have to switch the input focus so that whatever I’ve happen to type now ends up in the wrong window? This is so annoying. Stealing the input focus is a known problem that has been written about countless times. It’s even against the GUI programming guidelines. “Do not steal the input focus” - what’s so difficult about that?

As a first consequence Norton Internet Security is now gone from my machine forever after it kept reminding me constantly - specifically with an uncanny accuracy when I was busy playing computer games - that I need to renew my anti-virus subscription or bad things will happen to my computer. And bad things did happen to my video game. But not anymore…

On the upside, there’s a carefully hidden option in the Windows XP Powertoys (TweakUI) that is supposed to prevent programs from stealing the input focus. It made things better, but doesn’t seem to work all the time.

Posted in Coding / Programming, Ramblings | Print | No Comments »