Tagging Game Simulation

After several months of absence due to huge changes in my environment, I've finally spared some time and enthusiasm to invest into my blog! So please be glad dear reader.

Today, I'll take you out for a little and hopefully enjoyable trip into the concept of assigning names to things. This seemingly innocent task is at the center of several contemporary issues surrounding information in the human context. Of course, our long lasting friend Probability Theory comes along with us.

For the purpose of the argument, let's consider the non iterated following game:

Two players are given a common evidence. An evidence is anything the players can identify with good certainty, ranging from single words, to complete works, pictures, etc. The players must then independently come up with an unique word. If the words are the same, then they win the round.

We require the game to be one time because we don't want the players to figure out a cheating strategy, like always returning the same word (although non-matching words can be kept secret to diminish the feasibility of this strategy). Does this game reminds you of something? Actually it is a minimalist version of the ESP game by Luis Von Ahn, which seems to be a pretty efficient way to get good tags on pictures using human minds. His presentation of the work is a must see.

Anyway, we're going to focus on another aspect of the game, namely what is the probability of winning a round? And this should by design also be the probability of the description given by any two players of the evidence being the same, which is in essence the naming problem.

Heuristically, this probability must be pretty low on random evidences. Try something like "sick pigeons fall on people's heads". Candidate 1-word descriptions are for instance: umbrella, stroke, disgusting, absurd, crazy. Then we can try to guess what could be the most "popular" answer for this evidence, and return this one, as it would intuitively increase our chances of winning.

Let's now dive further into a bayesian probabilistic model of the naming game. Let $n$ be a positive integer representing the underlying vocabulary size, $e$ be the random variable representing the evidence (we're not interested in its density function though), and $x$ be the chosen candidate word. For commodity reasons, we'll represent $x$ as an $n$-dimensional vector having one 1 on the coordinate corresponding to the word and 0s everywhere else. The goal is to model the distribution $p(x|e)$, which is in our case a mass function of the form:

$$p(x|e) = \prod_{i=1}^n{\theta_i^{x_i}}$$

where the parameters of the model $\theta_i$ are positive and sum to 1. Notice that each evidence $e$ gets its own set of $\theta$ s. Now, what do the $\theta$ s look like?

A reasonable guess would suppose that they follow something called a Zipf's law. This particular kind of distribution is actually very common in the context of human language (and language in general as a communication protocol) and requires its own post for a decent coverage. In any case, there are both theoretical and practical evidence to support such a choice.

Under this assumption, and for the simplest possible form of a Zipf-like distribution (which is good enough for this back-of-the-envelop model), we can derive our parameters quite simply by:

$\theta_i \propto i^{-s}$

where our words "i" are ordered by decreasing popularity and $1 \leq s$.

We'll fix $n=100,000$ (reasonable for the English language, see AskOxford). $s$ can be seen as a measure of the difficulty of the problem. A low $s$ means a difficult problem where people don't come up with "hit words", and a high $s$ makes the distribution very sharp around the few first words, meaning that some consensus is emerging. As a reference level, $s \sim 1.1$ for the distribution of words in a standard English text.

The model is simple in its outset, but obtaining a nice closed form for $p(x^{(1)}=x^{(2)}|e)$ (namely the probability of 2 independent names being the same) is another challenge. Without loss of generality, given the various independence assumptions, it is straightforward to show that this probability is nothing else than:

$$p=\sum_{i=1}^n{\theta_i^2}$$

And there is no further simplification. In the improbable configuration $n \rightarrow \infty$ and $s>1$ (this condition is not $s>0.5$ because $p(x|e)$ would be otherwise not defined), we have $p \propto \zeta (2s)$, where $\zeta$ is the elusive Riemann's Zeta function.

A sensible range for the values of $s$ is $[1;1.5]$ . Usually, $s=1$ is accepted as a good choice for words frequencies in documents. However, the asymptotic properties of a Zipf distribution having $s=1$ are unpleasant. Because $\sum_{i=1}^n{\frac{1}{i}} \rightarrow \infty$ as $n \rightarrow \infty$, we would have $p \rightarrow 0$ as the vocabulary size grows...

We see how difficult it is to independently give the same name for the same evidence. The naming problem is in general tough stuff, and there are some nice empirical articles in the field of human computer interaction which study how to name the functionalities of a software so that people can easily find what they need.

Agressivité passive à 300km/h

Prendre le TGV, c’est un peu vivre une expérience sociale inattendue à chaque reprise. Non, je ne parle pas des retards et autres incidents qui bien que malvenus n’ont rien d’extraordinaires. Je parle des gens, de mes congénères voyageurs, dont la personnalité semble se réaliser pleinement dans cet espace fermé mais néanmoins public.

Mise en situation : quelqu’un a pris votre place. Que faites-vous?

• Solution 1 : Vous changez de place sans rien dire puisque peu importe, vous êtes seul et vous n’êtes pas un fétichiste des places numérotés.

• Solution 2 : Vous prenez vos précautions et faites remarquer à la personne son mauvais placement et qu’au moindre pépin vous regagnerez votre place.

• Solution 3 : Vous changez de place sans rien dire et vous n’arrêtez pas de répéter à votre fille à très haute voix que « le vilain monsieur a pris nos places ».

• Solution 4 : Horreur ! Vous faites dégager sans ménagement le fraudeur trop baba-cool à votre goût avant que le contrôleur n’ait eu le temps de valider son méfait.

1, 2 ou 4 : vous faites ce que vous voulez tant que vous restez en accord avec vous même, mais par pitié fuyez la 3. D’une part parce que l’on apprend ainsi à sa fille à éviter tout conflit direct sans pour autant se résoudre à accepter son sort et à attendre l’intervention de quelqu’un d’autre que soi-même. Et surtout parce que l’on emmerde tous les autres passagers mal placés (c'est-à-dire tous les non-fétichistes des places numérotées) qui se demandent si les ineptes gesticulations de la pauvre victime lui sont destinés. Si un jour vous êtes le spectateur de ce petit manège, deux choix s’offrent à vous, selon que vous vous sentez l’âme joyeuse ou plutôt sombre. Dans le dernier cas, mettez ostensiblement vos écouteurs et ouvrez un livre, ou mieux, votre ordinateur portable. N’y pensez pas, c’est son problème, pas le votre.

En revanche, dans le premier, il faudra franchement mettre les pieds dans le plat. Demandez-lui suffisamment fort pour que vos voisins l’entendent, qui est le gredin qui a osé le/la léser de ses places. Allez-y franchement, ne faites pas les choses à moitié, sinon vous allez vous retrouver à lui faire la conversation durant tout le trajet (alors que le but de la manœuvre est seulement de contribuer à la sérénité des non-fétichistes de la rame, c'est-à-dire de vous même). Affirmez-lui toute votre indignation face à ces attitudes si peu respectueuses des autres. Rajoutez en des couches tant que la personne ne se décidera pas à prendre une décision. Si elle décide de rester là ou elle est, elle arrêtera à coup sûr de râler, en tout cas elle le gardera pour elle. Sinon elle s’en ira d’elle-même récupérer les places si chères à son cœur, ce qui sera un spectacle des plus divertissants pour tous les voyageurs du wagon!

La prochaine fois je tente cette dernière stratégie, promis. En attendant, une bonne lecture sur ce qu'est le comportement passif agressif ici. A bientôt pour une nouvelle tranche de vie sur les rails!