Few days ago at the office building where our company’s office is located was an exhibition of some guy who draws labyrinths and then sticks pieces of old hardware (like old CPUs or floppy disks) to his paintings. I think his creative work is quite weird, but maybe you’ll like it, who knows :)

Click to read more ...

Few days ago one friend of mine (let’s name him A) has mentioned some psychological test. Test consists of a single question, and, according to some statistics, 98 percent of serial killers answer that question right. When another friend of mine (B) gave correct answer to the question, A said that it’s highly probable that B is a serial killer. Was he right? Of course, he wasn’t. A’s problem is that he is not familiar with the Bayesian approach at all. And here is why.

Let R be the event of giving the right answer to the question and M be the event that guy who answers is a maniac. From gathered statistics we know that P(R | M) = 0.98. Next, from Bayes theorem whe know that P(M | R) = P(R | M)P(M)/P(R). P(R) can be represented as P(R | M)P(M) + P(R | not M)P(not M). Next, assume that about 5 percent of usual people also gave the right answer to the question, so P(R | not M) = 0.05. Then, what’s the prior probability of M? I think we all agree that it’s quite small, about 1e-5 or even less. Now we are ready to calculate posterior probability of M:

P(M | R) = (0.98 * 1e-5) / (0.98 * 1e-5 + 0.05 * (1 - 1e-5)) = 0.0000098 / (0.0000098 + 0.0499995) ~ 0.0002.

Probability is very small, but why is that? That’s because my friend A was talking about the likelihood, but he didn’t take prior probabilities into account. And in this case prior probabilities are of great importance.

Btw, what’s if serial killers always answer right and normal people always give wrong answers? Then P(R | not M) = 0 and P(M | R) = 1, so our model works in extreme cases too.

Today we will consider a more sophisticated inference example, with both closed-form solution and Infer.NET program. We are going to find answers to some very important questions closely connected to the Lorenzo von Matterhorn trick from Barney Stinson’s Playbook.

First of all, let’s figure out factors influencing the successful completion of the trick. It looks reasonable that girl should search for your imaginary name in Google. Without it, trick wouldn’t work. It means that girl should have some internet device and area should be covered with internet (WiFi, 3G etc). Also, if your ugliness outweigh your imaginary wealth and fame, girl may not come with you (nevertheless, it’s highly improbable). Such suggestions allows us to build the following probabilistic model with discrete variables: 

In fact our model is a Bayesian network. It means that we should specify parent-conditional probability distribution for each variable it consists of. Let’s get started.

P(I) = 0.8 because almost all the modern phones have at least GPRS support.
P(C) = 0.9 because internet is available practically everywhere nowadays.
P(G | I, C) = 0.95 (wouldn’t you google for this strange man?)
P(G | not I, C) = 0.3 cause she can ask someone who has internet to google.
P(G | I, not C) = P(G | not I, not C) = 0 cause nobody can google without internet.
P(H) = 0.2 because not much guys are handsome.
P(S | G, H) = 0.99
P(S | not G, H) = 0.5 (it’s nice to be attractive, huh)
P(S | G, not H) = 0.9 cause wealth is more important than handsome look.
P(S | not G, not H) = 1e-5 (the worst case).

Computing probability of success is quite straightforward, so we will concentrate on two little more sophisticated questions:

1. What’s the probability of you being handsome if you’ve succeeded in the trick? 
2. If you haven’t succeeded in the trick, what’s the probability she had looked for your imaginary name in Google?

To compute those probabilities, we’ll use Bayes theorem together with the law of alternatives. This blog is not really a comfortable place for a lot of formulas, so the whole inference is available in the separate PDF. As we can see there, it’s not very hard to show that P(H | S) = 0.2449 and P(G | not S) = 0.2042. We can also write a small inference program using Infer.NET library which will give us exactly the same results.

Calculated probabilities agree with our common sense very well. Value of P(H | S) shows that it’s not necessary to be some handsome guy to perform a trick. And value of P(G | not S) tells us that most of the failures happen when girl refuses to google for some reason.

That was another example of probabilistic logic in action. Next time we’ll consider some continuos case like linear regression.

Probably, some of you have heard that GCC and Visual Studio C++ Compiler are written in C++. I guess that most of the C++ compilers are (if not, my plan will fail). So, if all the compiler binaries will somehow disappear someday, all the C++ sources (including sources of the compiler itself) will become useless. But how can we achieve that?

The most simple (but also the most hard) way is to add some kind of time bomb to the sources of every C++ compiler. That time-bomb should be activated a few years later, when everyone will be using compromised version of the compiler. After the activation of the time-bomb all the compiler executables will be destroyed on the first compilation. Nice scenario, isn’t it? The problem is to add time-bomb in a way that nobody in the team of compiler developers will notice it. An interesting problem for a great hacker, I guess. Man, if you do it, you’ll become a legend!

There is an alternative option. Not so powerful, but still possible. Every virus maker who cares should add search-for-compilers-and-delete-them-when-time-bomb-is-activated code to her (or his) brainchild. The problem here is that there are not much computer viruses for *nix systems, but most of the C++ compiler instances are concentrated there. Anyway, people, we should try!

I propose the following date for the time-bomb activation: December 12, 2012. Develop your viruses and keep it quiet.

Btw, it also can be a plot for a great action movie. Imagine some well-secured subterranean storage for the Last Compiler, a lot of men with big guns, and a bunch of heroes trying to fix the men’s biggest mistake: C++ language invention.

Update on Thursday, November 19, 2009 at 9:46PM by hr0nix

Here is a beautiful idea of how can trojan horse be insensibly added to the compiler which is written in the language it compiles, thank to Alexander Monakov.

And bad news, guys. Some C++ compilers are written in C, so we have to destroy all the C compilers also. Nothing personal, we just have to do it for the common good. List of enemies can be found here.

Those of you who watches The Big Bang Theory CBS sitcom should be familiar with the Rock-Paper-Scissors-Lizard-Spock game introduced in the Lizard-Spock expansion episode. One of my friends has recently got a t-shirt with the rules of the game printed on it. Then, we’ve got drunk and decided to play. The one question I’ve asked before we started was if the game is fair (I still have a strong feeling that Spock must act like an ultimate weapon). When t-shirt is in front of you, it’s rather easy to answer: each vertex of the digraph drawn on it (representing weapon) should have equal in and out degrees. If so, each weapon beats and is beaten by the same number of weapons. In the mentioned Lizard-Spock game each vertex has in and out degrees of 2.

But what if you haven’t such a beautiful picture? Remember how Sheldon Cooper introduces the game:

Scissors cuts Paper, Paper covers Rock, Rock crushes Lizard, Lizard poisons Spock, Spock smashes Scissors, Scissors decapitates Lizard, Lizard eats Paper, Paper disproves Spock, Spock vaporizes Rock, and as it always has, Rock crushes Scissors!

As you can see, his speech actually represents a path in the game graph. He starts and ends with the Scissors, walking through every relationship in the game. In fact, Sheldon gives us an Eulerian circuit in the digraph. Existence of such circuit implies that each vertex of the graph has equal in and out degrees, something we were trying to figure out.

Well, each vertex Vi can have the same in and out degree Ki, but Kj can be not equal to Ki for distinct j and i. What does that mean for the players? It means that there is no rule for some pair of weapons. So, if you began to play and then discovered that nobody knows what lizard does to Spock, then something is obviously wrong with your game and you don’t need neither graph theory nor other theories to figure it out.

People often understand complex things better when good examples are provided. But, unfortunately, many mathematicians prefer abstract explanations like “so, Slut(x) and Drunk(x) obviously implies Sex(me, x)” instead of just saying “I’m pretty sure I’ll have sex with that drunk chick tonight”. That’s why I want to create a list of math application examples to some real-world things that are familiar to most people. It, probably, can make math more interesting and, of course, more comprehensible. And, I’m going to start from the graph theory because it seems to be rather clear even for people far from math. So, here we go.

Click to read more ...

Some people do not believe that switching door in Monty Hall game can actually help you to win. Usually they say something like “yeah, your math is all right, but it’s just a probability theory trick, math does not help you when you are playing in real life”. Those people sometimes pretend to be clever and intellectual, but, unfortunately, they are all wrong. There is a gap between probability theory and real life of course, but not the gap they think.

For those who are too lazy to perform a simple experiment, I’ve written this short program in C#. It plays in Monty Hall game using switching strategy and actually wins in 2/3 of all the cases.

Q.E.D., bitches!

Update:
For an example of the probability theory paradox that has larger gap with the real life one can look, for example, through St. Petersburg paradox . And very good place to start finding another interesting paradoxes is there

You are given 2 pieces of code:

void func()
{
  variable = 666;
}

int variable;

void func()
{
  variable = 666;
}

Make them compile. You can add any C++ constructs after and before the whole code block, except for

1. Anything related with preprocessor.
2. Comment symbols.
3. Digraphs or trigraphs.
4. Any constructs with “variable” text inside.

In the first puzzle function must access variable “variable” declared below, not any other.

Click to read more ...

We have recently performed a simple experiment at work. The purpose of the experiment was to compare the performance of our SVM-based gender classifier with the human ability to distinguish faces of people of different age. As the result, I was the only man beaten by the machine.

All the faces were divided into 5 classes (age<20, 20<=age<30, 30<=age<40, 40<=age<50, age>=50). Each human participatin in the experiment labeled about 100 face pictures manually. Classifier performance was estimated using 10-fold cross validation on a bigger dataset.

Error value equals to P means that P x N of N samples were labeled right (correct label was selected by the decision rule from the set of 5 available labels, decision rule is either human brain or SVM classifier).

I think that rise of the machines will happen very soon (hope some robot from the future will save my ass).