Probabilités

Présentation et motivation

On peut ne pas voir immédiatement le lien entre les probabilités et la recherche d’information, mais ce lien deviendra rapidement très clair au fur et à mesure que le cours progressera. Les probabilités sont utilisées tant dans les modèles de la langue, que dans les algorithmes de Google (PageRank) ou dans les moteurs de recherche. En somme, elles sont incontournables.

Si vous n’avez pas étudié les probabilités auparavant, ce texte peut vous paraître difficile ou déroutant. N’ayez crainte. Vous aurez la possibilité de revenir sur ces notions en tout temps dans le cours et vous pourrez vérifier le degré de votre compréhension dans l’activité d’autoévaluation.

La moyenne

La moyenne d’un vecteur $V$ est la somme de ses composantes divisée par le nombre de composantes ; elle est notée $\overline{V}$ . La formule est $\sum_{i=1}^n V_i/n$ .

La variance

La variance d’un vecteur $V$ est la somme du carré de l’écart à la moyenne des composantes divisée par le nombre de composantes. La formule est la suivante : $\sum_{i=1}^n \frac{(V_i - \bar V)^2}{n}.$

Voici un script JavaScript qui calcule la moyenne et la variance d’un vecteur :

Vecteur:

(Le script ne fonctionne pas dans tous les navigateurs.)

La corrélation

Étant donné deux vecteurs de même taille, on peut calculer la corrélation de Pearson entre les deux vecteurs comme étant :

$\mathrm{Pearson}(V,W)= \frac{ (V-\overline{V})\cdot(W-\overline{W}) }{ \Vert V-\overline{V} \Vert \Vert W-\overline{W} \Vert }.$

La corrélation de Pearson est une valeur entre -1 et 1. Le carré de la corrélation de Pearson donne le pourcentage de corrélation.

Par exemple, ces deux vecteurs sont fortement corrélés (corrélation proche de 1) :

$V= \left [ \begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right ], W= \left [ \begin{array}{c} 1.1 \\ 2 \\ 3.2 \end{array}\right ]$

alors que ces deux vecteurs sont aussi fortement corrélés, mais négativement (corrélation de -1) :

$V= \left [ \begin{array}{c} 1 \\ 2 \\ -3 \end{array}\right ], W= \left [ \begin{array}{c} -1 \\ -2 \\ 3 \end{array}\right ].$

Finalement, il n’y a aucune corrélation entre ces deux vecteurs (corrélation de 0) :

$V= \left [ \begin{array}{c} 1 \\ 2 \\ -3 \end{array}\right ] , W= \left [ \begin{array}{c} -2 \\ 1 \\ 0 \end{array}\right ].$

La fréquence

La fréquence est le nombre de fois qu’une instance ou qu’un objet se manifeste. Par exemple, la fréquence du mot rue dans le journal est le nombre de fois que le mot rue est utilisé dans les textes du journal.

La distribution

Dans le cadre de ce cours, une distribution est une fonction qui, pour chaque instance possible, nous donne la probabilité correspondante. La somme de toutes les probabilités doit être 1.

La distribution des probabilités du lancer d’une pièce de monnaie est 50% pour l’instance pile et 50% pour l’instance face.

Si on choisit un mot au hasard dans un texte, quelle est la probabilité que le mot soit rue ou voiture ? Dans ce cas, on peut calculer la distribution avec exactitude si on connaît d’avance le texte : il suffit de calculer la fréquence de chaque mot et de la diviser par le nombre total de mots.

La moyenne et la variance d’une distribution

Notons $P(k)$ la probabilité que la valeur d’une certaine variable soit $k$ . Par exemple, si on attribue la valeur 1 au résultat pile et la valeur 0 au résultat face, alors la distribution d’un lancer d’une pièce de monnaie est $P(0)=0.5$ et $P(1)=0.5$ . Notez que $\sum_k P(k)= 1$ .

La moyenne ou l’espérance d’une distribution est :

$\bar X = \sum_k k P(k)$

alors que sa variance est :

$\sum_k (k-\bar X)^2 P(k).$

Voici un script JavaScript qui calcule la moyenne et la variance d’un vecteur :

P(k=1) =
P(k=2) =
P(k=3) =

La distribution de Poisson

Dans une distribution de Poisson, la probabilité pour qu’une valeur donnée soit $k=0,1,\ldots$ , est

$P(k)=\frac{e^{-\lambda} (\lambda )^k}{k !}$

où $\lambda$ est un paramètre et $e \approx 2.71828$ . La variance et la moyenne d’une distribution de Poisson est $\lambda$ .

Le rang

Étant donné une distribution, l’instance la plus probable occupe le premier rang, la deuxième instance la plus probable occupe le second rang et ainsi de suite.

Par exemple, dans le problème qui consiste à choisir au hasard un mot dans un texte, le mot le plus fréquent aura le premier rang et le mot le moins fréquent, le dernier rang.

La probabilité

La probabilité est toujours une valeur entre 0 (un événement impossible) et 1 (un événement certain). En général, on note la probabilité que l’événement $A$ se produise $P(A)$ et la probabilité qu’il ne se produise pas $P(\bar A)$ . Nous savons que $P(A)+P(\bar A)=1$ .

Si on est certain qu’un (et un seul) des événements $A$ , $B$ ou $C$ doit se produire, nous avons $P(A)+P(B)+P(C)=1$ .

$P(A\textrm{ ET }B)=P(A \cap B)$ est la probabilité que $A$ et $B$ se produisent.

Les événements $A$ et $B$ sont indépendants si et seulement si $P(A\textrm{ ET }B)=P(A \cap B)=P(A)P(B)$ .

Les divers lancers d’une pièce de monnaie sont indépendants et donc, la probabilité d’obtenir deux fois pile est $0.5\times 0.5 = 0.25$ (25%).

Note. Certains auteurs utilisent le et et le ou logiques : $P(A\textrm{ ET }B)=P(A\land B)$ et $P(A\textrm{ OU }B)=P(A\lor B)$ . Personnellement, je trouve qu’il est difficile de se rappeler lequel de $\lor$ et de $\land$ signifie « et » et lequel signifie « ou ». Dans ce cours, nous n’utiliserons pas cette notation.

**Représentation graphique de la probabilité que A et B soient vraies.**

La probabilité conditionnelle et la vraisemblance

La probabilité qu’au lancer d’une pièce de monnaie, on obtienne pile peut être notée $P(\textrm{pile})$ . Nous avons, bien sûr, $P(\textrm{pile})= 1/2$ . La probabilité conditionnelle est la probabilité attribuée à un fait connu. Par exemple, si on sait que Jean triche, on pourra avoir une probabilité différente, disons de 60% pour la valeur pile. On note la probabilité conditionnelle avec la barre verticale, comme ceci : $P(\textrm{pile}|\textrm{Jean triche})=0.6$ .

Formellement, on définit la probabilité conditionnelle ( $P(A|B)$ ) comme
$P(A|B)=P(A\textrm{ ET }B) / P(B)$ . Ainsi, si la probabilité que Jean triche est de 5% et qu’il arrive dans 3% des cas que Jean ait triché et que le résultat soit pile, on dira que la probabilité conditionnelle d’avoir pile étant donné que Jean triche est de 60%. Nous avons $P(A|B)+P(\bar A|B)=1$ . En général, $P(A|B)\neq P(B|A)$ ; cependant, on peut calculer l’une des valeurs à partir de l’autre en utilisant le théorème de Bayes.

Le théorème de Bayes stipule que $P(A|B) = \frac{P(B | A) P(A)}{P(B)}$ où, dans le cas de notre exemple,

$P(\textrm{pile}|\textrm{Jean triche})=\frac{P(\textrm{Jean triche} | \textrm{pile}) P(\textrm{pile})}{P(\textrm{Jean triche})}.$

Il n’est pas nécessaire de mémoriser ce théorème dans ce cours, mais il faut savoir que c’est le principal théorème utilisé avec les probabilités conditionnelles. Il est facile de le démontrer à partir de la définition $P(A|B)=P(A ET B) / P(B)$ :

$P(A|B)=P(A\textrm{ ET }B) / P(B)= \frac{P(A\textrm{ ET }B) P(A)}{P(A)P(B)}=\frac{P(B | A) P(A)}{P(B)}.$

La vraisemblance est définie comme $L(B|A)=P(A|B)$ . Ainsi, la vraisemblance que Jean triche étant donné un résultat pile est 60% ( $L(\textrm{Jean triche}|\textrm{pile})=P(\textrm{pile}|\textrm{Jean triche})$ ), si on suppose que personne d’autre ne triche, et que pile et face sont équiprobables, alors la vraisemblance que Jean ne triche pas étant donné un résultat pile est de 50%. Contrairement à ce qui se passe avec les probabilités, les vraisemblances d’événements mutuellement exclusifs ne totalisent pas 100%.

Estimation des probabilités par vraisemblance maximale

Nous n’avons pas toujours accès à toutes les données lorsqu’il faut calculer les probabilités et nous sommes souvent forcés de les estimer. La façon la plus simple d’estimer les probabilités consiste à recourir à la méthode de vraisemblance maximale.

Supposons que vous preniez des échantillons de fleurs dans un parc. Sur 50 fleurs que vous avez ramassées, 12 fleurs sont des pissenlits et le reste, des trèfles blancs. Quelle est le probabilité que la prochaine fleur que vous ramassiez soit un pissenlit ? Une réponse fort naturelle est 12/50. C’est en effet la réponse la plus vraisemblable étant donné notre échantillonnage. Ainsi, si nous avons $n$ échantillons et que nous observons l’élément $i$ , $f_i$ fois, alors la probabilité associée à $i$ sera $f_i/n$ .

Dans le cours, nous verrons que ce n’est pas seule méthode utilisée pour estimer des probabilités. Le lissage de Laplace et la formule de Good-Turing sont d’autres méthodes souvent utilisées.

La probabilité : toute une discipline

Il y aurait encore beaucoup à écrire sur les probabilités. Il faudrait traiter des équations de Chernoff, de Chebyshev, etc. Cependant, dans le cadre de ce cours, bien comprendre les notions présentées ici sera suffisant.

Lectures complémentaires fortement suggérées

– Une introduction improbable aux probabilités (chaudement recommandé, à consulter absolument !)
– Article de Wikipédia sur les probabilités (excellent !)

Semaine 1

Probabilités