SquareSpace

I don't like Blogger. It kind of sucks. This blog will be available on SquareSpace starting from now!

Take a look - http://sexdrugsandappliedscience.com

Paper from the WIT talk

Preprint of the paper associated with my WIT talk I've recently posted about is available at arxiv.org now.

PhD summer school, WIT

Yesterday I've participated in pattern recognition section of PhD summer school on Scentific Computing. It's a web conference event. Several universities participate in it, including Waterford University of Technology and our Moscow State University. There I have a talk about my last research work: accelerating boosting with genetic algorithms. That was my first experience of web conferencing, but everything went ok as I think.

If someone is interested, slides from my talk are available there. AFAIK conference site will appear soon. It will contain both the presentations and theses of the presented works. There should be some interesting stuff there. For example, I'd like the talk about feature set compactness of the training set and its relation to k-NN classifiers by Dmitry Potepalov.

Physicist Day

Last saturday Physics Department of the Moscow State University was celebrating it's traditional holiday: Physicist Day. Every year something funny, strange or scaring happens to me on that day, but the last time was special. Here is a list of things I remember:

19:00 - Me and two my friends go to the local bar. It has nothing to deal with Physicist Day.

23:30 - Being quite drunk we try to return home. But near the campus we meet a bunch of our friends (being quite drunk too because of celebrating Physicist Day). They suggest to go to the night club where physicist's party is just starting. We take some beer.

23:50 - Something strange happens in the street railway. Somehow we get a big black hat.

00:00 - We are near the club where we meet some other guys from both CMC and Physics departments. Suddenly a fight between a guy being with us and some other guy starts.

00:05 - Some other guys trying to prevent previous fight begin to fight because of a little misunderstanding.

00:10 - Now guys who was trying to prevent the second fight are fighting because of the same reason.

00:15 - Guy from the very first fight call the cops.

00:20 - Cops are there. One of my friends is trying to prevent "the situation".

00:25 - Cops go away. We're in the club.

00:30 - Tequila, sambuca, Long Island, more tequila, more Long Island, ...

DO NOT REMEMBER

01:10 - Somehow we get into VIP zone. I have no idea about it.

DO NOT REMEMBER

01:30 - Suddenly I found myself on the dancefloor kissing some unknown chick.

DO NOT REMEMBER

02:30 - Suddenly I found myself in the car going to the nearest ATM to get some money. When we get to the ATM, I can't open the door. Too drunk to insert my credit card into an electronic lock. Driver helps me. I take the money and we return to the club. I gave about 40$ to driver for the 100-meter trip in the car (bad idea).

03:00 - I drink some shit again. I rock with some unknown girl. One of my friends get knocked out  from the club for the immoral conduct. 

DO NOT REMEMBER

05:00 - Staying at the street with some unknown chicks. Feeling bad.

DO NOT REMEMBER

07:00 - Found myself at home

SLEEPING

16:00 - Feeling like a shit

Result: about $500 spent in a chip dirty club in one night, headache for a day, a lot of impressions. God Damnit, I like physics ;)

RoboZZle solver update

I've just updated my RoboZZle solver. There are two major changes:

• I've fixed bug with program execution loop detection using approach proposed by Igor Ostrovsky there. So it can solve "Count the tiles"-like puzzles now.
  
• I've added the whole new solving approach based onto evolutionary algorithm (implemented using AForge.NET library). It is not very useful just for now, but still can solve some complicated puzzles. I've used eaten star count as a fitness function for program. So, if there is only one or two stars on the field, this approach works just like random search. But if you know correct path for your robot (it is obvious in many puzzles), you can mark it all with stars using field editor integrated in the solver, giving your guess to the evolutionary algorithm. The main problem with this approach is that in many puzzles correct program is very different from the program that can collect almost all the stars on the field. I need better fitness function, and probably, some other crossover and mutation ops. Currently chromosome is just a concatenation of all the program functions' code. Mutation operator changes color or operation at random position of the chromosome. 2-point crossover exchange operations between two chromosomes.

Btw, I will be really happy if you add a comment to this post describing what puzzles can (and can not) be solved using brute-force or evolutionary approach. That information will help me to improve my solver a lot.

RankBoost and DCG

So I've finally sucked (my best DCG on test set is 4.198 which is kind of not too good) in the Yandex contest I've already posted about. As I think, there were two major problems: lack of time and, unfortunately, lack of good ideas. But I want to share with you some things I've learned while participating in it.

One of the ranking algorithms I've tried was RankBoost with binary rankers originally proposed by Freund and Schapire. To have ability to separate not only documents with high value of some feature from documents with low value of the same feature, but also, for example, documents with feature value distributed somewhere around 0.5 from any other, I've performed additional experiments using ranking features that are functions of another features. For that purpose I've selected truncated gaussian with mean=0.5 and also [0,1]-multimodal sinus-based function:
There are plots representing experiment results in terms of RankBoost performance value and Yandex DCG:

As for me, I've drawn 3 conslusions:

1. Using only original features for creating weak ranker sucks.
2. Using weak rankers based on functions of features is slightly better.
3. The whole approach still sucks in terms of DCG.

I should have tried RankBoost with concave learners proposed there. Oh, forget to mention. Yandex DCG for query can be calculated like that:

Final DCG value is then acquired by calculating sum of DCGs of all the queries and then dividing it to the number of queries.

Dependency reconstruction using Infer.NET

Today we'll take a look at the sexual relationship problem from another point. Let's assume that there is some decision model describing how girls select their sexual partners. But, unfortunately, we don't know that model yet. One day some girl we know has betrayed a secret: decision model is linear and it depends on such a factors: your sexuality, your smartness and also girl's slutness. So we decided to find out the way that model actually looks like. The most simple way to do that is to gather some training data of the following format: (sexuality, smartness, slutness, was there any sex). Yeah, we assume that we can somehow estimate that values for some girls and boys and ask them about sex. Than we can use Bayes point machine implemented in Infer.NET to reconstruct that linear model. Factor graph for that implementation is really simple. It just assumes that we can get an answer by calculating inner product between weight vector (which describes our linear model) and observation vector (which contains first 3 values of the training data vector followed by 1 for representing bias) and checking if it is positive:

That model can be build using following code piece:

Range range = new Range(ItemsCount);
VariableArray<bool> observedSex = Variable.Observed(observedResults, range).Named("observed sex");
VariableArray<Vector> trainingData = Variable.Observed(observedData, range).Named("observations");
Variable<Vector> weights = Variable.Random(
new VectorGaussian(new Vector(ParamCount),
PositiveDefiniteMatrix.Identity(ParamCount))).Named("weights");
observedSex[range] = Variable.InnerProduct(weights, trainingData[range]) > 0;

So, let's generate some observed data using "unknown" linear model:

const int ParamCount = 4;
Vector[] observedData = new Vector[ItemsCount];
bool[] observedResults = new bool[ItemsCount];
for (int i = 0; i < ItemsCount; ++i)
{
double sexuality = Math.Max(0, Math.Min(Gaussian.Sample(0.5, 1), 1));
double smartness = Math.Max(0, Math.Min(Gaussian.Sample(0.1, 0.5), 1));
double slutness = Math.Max(0, Math.Min(Gaussian.Sample(0.3, 1), 1));
bool haveSex = sexuality + 0.1 * smartness - slutness > 0.25;
observedData[i] = new Vector(sexuality, smartness, slutness, 1);
observedResults[i] = haveSex;
}

We can now infer weight vector posterior distribution using Expectation Propagation algorithm. Gaussian distribution is symmetric and unimodal, so we'll take it's mean as a result.

InferenceEngine engine = new InferenceEngine { Algorithm = new ExpectationPropagation()};
VectorGaussian weightDistribution = engine.Infer<VectorGaussian>(weights);
Vector mean = weightDistribution.GetMean();
Console.WriteLine(
"Model: ({0:0.00})*sexuality + ({1:0.00})*smartness + ({2:0.00})*slutness + ({3:0.00}) > 0",
1, mean[1] / mean[0], mean[2] / mean[0], mean[3] / mean[0]);

After running that sample we'll get the following output which confirms that we have reconstructed unknown linear model quite precise:

Compiling model...done.
Initialising...done.
Iterating:
.........|.........|.........|.........|.........| 50
Model: (1.00)*sexuality + (0.10)*smartness + (-0.99)*slutness + (-0.26) > 0

Little update

I've finally received "The Elements of Statistical Learning" book from Amazon. It's really great because it covers probably all the important machine learning topics including various regression and classification algorithms, model selection, graphical models, dimensionality reduction and many more. And this is also the first book covering boosting good (which is kind of important for me). Book authors, Trevor Hastie, Robert Tibshirani and Jerome Friedman are famous machine learning scientists from Stanford University. And the last one: book is published by Springer on an awesome paper with color plots. Holy crap, I like it!

Btw about Springer. Today I've found that one of the university shells I have access to is in the same university subnet where all the papers from SpringerLink are available for free. So I've written a little script that downloads requested article to my computer through that shell. Together with ACM account I've recently bought it gaves me acceess to almost every article I want.

Bunch of useful links

Blogs about machine learning:

• http://hunch.net/
• http://slycoder.wordpress.com/
• http://yaroslavvb.blogspot.com/

Some funny stuff about theorem proving: http://www.wolfbane.com/jazz/proof.htm

Genetic algorithm for producing beautiful artwork: http://oranchak.com/photosome/results/

Bayesian inference for boys

Learning something is good. Learning something using interesting examples is even better. Today I'm going to show you the power of bayesian inference by building model representing probability of you having some sex. If you want more formal introduction, please read this paper written by Christopher Bishop, famous researcher from Microsoft Research Cambridge.

Bayesian inference is a method for finding posterior distribution of dependent set of random variables, when some variables are observed and some are not interesting. That set of variables is often represented as so-called graphical model: a directed graph called Bayesian network or undirected graph called Markov network. In that kind of graph vertices represent random variables and edge connecting two vertices mean that variables associated with that vertices are dependent. That representation is not only clean and obvious, but it also allows using some fast and robust algorithms for performing inference.

Let's look at concrete example. We'll try to build simple model describing sexual relationships between boys and girls. Probability of you having sex with some girl mostly depends on the degree of she liking you (which depends on you sexuality) and her so-called slutness. I've also considered some gaussian noise in woman's head that sometimes dramaticaly imacts on her decisions. An assumption that slutness and sexuality are distributed normally around zero (which we consider as an average value for that variables) and value describing how much she likes you is also distributed normally around your sexuality allows us to build simple graphical model. Amazing tool for that is Infer.NET, .NET library for bayesian inference from Microsoft Research. Model code is quite short:

Variable<double> youAreSexy = Variable.GaussianFromMeanAndVariance(0, 1).Named("you're sexy");
Variable<double> howMuchSheLikesYou = Variable.GaussianFromMeanAndVariance(youAreSexy, 0.25).Named("how much she likes you");
Variable<double> slutness = Variable.GaussianFromMeanAndVariance(0, 1).Named("her slutness");
Variable<double> randomNoiseInHerHead = Variable.GaussianFromMeanAndVariance(0, 0.25).Named("noise in her head");
Variable<bool> willYouHaveSexToday = (howMuchSheLikesYou + randomNoiseInHerHead + slutness > 0).Named("will you have some sex?");

After compiling model in Infer.NET you'll get a graphical representation of your model which is called factor graph. It looks very similar to bayesian network but also contains special "factor" nodes representing different operations, constrains and distributions. Clickable picture below is an example of factor graph for our "sex" model:

Let's ask some questions to our model using ExpectationPropagation inference algorithm:

1. slutness = -5 (she's REALLY not a slut), willYouHaveSexToday = true (yeah, you did it). Then distribution of you being sexy is Gaussian(3.514, 0.3635) which means you are beauty as a devil (I guess).
   
2. slutness = -0.5 (she's just a girl), youAreSexy = -1 (you are not a good one). Then probability of you having sex today is 0.01695. It means that your chances are quite small.
   
3. youAreSexy = -5 (oh, you look really bad), willYouHaveSexToday = true (but still have some sex? strange, isn't it?). Then distribution of her slutness is Gaussian(3.514, 0.3635) (oh, she is a slut... that makes sence).
   

So, bayesian inference helps us with different questions about girls, sex and everything. Remember that provided model is very simple and inaccurate. For example, one can consider slutness as a variance of howMuchSheLikesYou variable or add some other random variables and factors into model. Have fun with it and don't forget that math is great.