Modèles probabilistes

La recherche d’informations comme science

Dans ce cours, nous cherchons à présenter la recherche d’informations comme un domaine certainement multidisciplinaire, ayant des applications importantes en technologie de l’information, mais aussi comme étant une science avec ses modèles rigoureux et mathématiques. Les modèles probabilistes en recherche d’informations sont importants parce qu’ils représentent une des tentatives les plus significatives pour donner une base théorique solide à la recherche d’informations.

Les modèles probabilistes

Si un utilisateur fait une requête, dans un moteur de recherche, avec le mot chat, il peut avoir diverses intentions. En effet, peut-être cherche-t-il un document qui porte sur les chats (les mammifères) ou peut-être veut-il en apprendre davantage sur le terme anglais chat (discussion) ? On peut penser qu’il y a une certaine « probabilité » qu’un document sur les chats en tant que mammifères soit pertinent pour l’utilisateur faisant une requête avec chat : disons que cette probabilité est peut-être de 80 %. La probabilité que l’utilisateur veuille en savoir davantage sur le mot anglais chat est sans doute plus faible, disons 20 %. En répétant ce type d’analyse, on en arrive à un modèle selon lequel, étant donné une certaine requête, chaque document est associé à une certaine probabilité de pertinence. L’idéal serait de présenter, à l’utilisateur, les documents les plus « probables » d’être pertinents en premier, suivis des autres [1]. Cette approche porte le nom de Probability Ranking Principle (PRP).

Dans les modèles probabilistes, en recherche d’informations, on cherche donc à estimer la probabilité qu’un document $D_i$ soit pertinent (relevant en anglais) ; on note cette probabilité $P(rel|D_i)$ . La probabilité que le document ne soit pas pertinent est $P(nrel|D_i)$ . Par exemple, si la requête est faite avec le mot chat et que $D_i$ est un document sur les chats de gouttière, nous aurons peut-être $P(rel|D_i)=0.4$ et $P(nrel|D_i)=0.6$ .

Comment calculer $P(rel|D_i)$ ? Un modèle simple

Comment calculer $P(rel|D_i)$ ? La vérité, c’est qu’il s’agit d’un calcul impossible à faire, parce que personne ne connaît vraiment la réponse : comment, en effet, mesurer la pertinence d’un document pour un humain ? Par ailleurs, un modèle peut quand même être utilisé.

Le modèle le plus simple, pour une requête donnée, consiste à compter le nombre de mots dans le document trouvé. Par exemple, si je fais une recherche avec les mots « cacaouette pistounette maison » et que seul le mot maison est présent dans le document, je pourrais dire que $P(rel|D_i)= 1/3$ . Cette façon de faire ne fonctionne pas bien parce qu’un document ne contenant que le mot (plus rare) pistounette se verra aussi attribuer une probabilité de $P(rel|D_i)= 1/3$ , alors qu’on s’attendrait à une probabilité plus élevée. Le mot maison est un moins bon indicateur de pertinence que le mot pistounette (ce qui est indiqué, dans certains modèles vectoriels, par le coefficient idf) [2].

$P(rel|D_i)$ ou $P(D_i|rel)$ ?

Nous avons proposé un modèle simple permettant de calculer $P(rel|D_i)$ , mais il s’avère simpliste. Nous allons maintenant proposer un modèle permettant de calculer plutôt $P(D_i|rel)$ .

On peut se demander laquelle des deux quantités, $P(rel|D_i)$ ou $P(D_i|rel)$ , est pertinente. Le PRP fait référence à la probabilité $P(rel|D_i)$ (la probabilité de pertinence), mais les deux probabilités sont liées et on peut calculer l’une à partir de l’autre.

Rappel : $P(rel|D_i)$ est la probabilité de pertinence étant donné que le document $D_i$ est choisi. D’autre part, $P(D_i|rel)$ est la probabilité que $D_i$ a été choisi étant donné qu’un document pertinent a été choisi. Nous avons que $P(rel|D_i) + P(nrel|D_i)=1$ . En général, $P(D_i|rel) + P(D_i|nrel)\neq 1$ , mais $\sum_i P(D_i|rel)=1$ et la somme s’applique à tous les documents disponibles.

Théorème : Trouver les documents qui maximisent $P(rel|D_i)$ est équivalent à trouver les documents qui maximisent :
– $\frac{P(rel|D_i)}{P(nrel| D_i)}$
– $\frac{P(D_i|rel)}{P(D_i|nrel)}$

Preuve :

En résumé : On cherche les documents maximisant $P(rel|D_i)$ , qui sont les mêmes que ceux maximisant $\frac{P(rel|D_i)}{P(nrel| D_i)}$ , qui sont, finalement, les mêmes que ceux maximisant $\frac{P(D_i|rel)}{P(D_i|nrel)}$ . En somme, dans le contexte du PRP, il importe peu qu’on travaille avec $P(rel|D_i)$ , $\frac{P(rel|D_i)}{P(nrel| D_i)}$ ou $\frac{P(D_i|rel)}{P(D_i|nrel)}$ , ou encore sur les logarithmes de ces quantités.

Un modèle plus efficace

Un modèle plus sophistiqué passe par la définition de deux probabilités $p_j=P(t_j|rel)$ et $p_j=P(t_j|nrel)$ qui notent respectivement la probabilité que le terme $t_j$ fasse partie d’un document pertinent, et la probabilité que le terme $t_j$ fasse partie d’un document non pertinent. Si on suppose qu’on connaît ces probabilités, on peut estimer $P(D_i|rel)$ comme étant le produit des probabilités associé à chaque terme dans le document, multiplié par le produit des probabilités que les termes absents n’apparaissent pas dans un document pertinent.

Avec ce modèle simple, on peut calculer $P(D_i|rel)$ comme suit :

$P(D_i|rel)= \prod_{t_j\in D_j} P(t_j|rel) \prod_{t_j\notin D_j} (1-P(t_j|rel))$

où $1-P(t_j|rel)$ est la probabilité que le terme $t_j$ n’apparaisse pas dans un document pertinent. De la même manière, on peut calculer

$P(D_i|nrel)= \prod_{t_j\in D_j} P(t_j|nrel) \prod_{t_j\notin D_j} (1-P(t_j|nrel)).$

Par exemple, si le mot enfant a une probabilité de 50 % de faire partie d’un document pertinent, alors que le mot chien a une probabilité de 40 %, un document qui ne contient que les deux mots enfant et chien pourrait avoir une probabilité de pertinence de $0.5 \times 0.4 = 0.2$ (20 %) si on suppose que la présence d’un terme dans un texte est indépendant de la présence des autres termes et que la pertinence d’un document ne dépend que des termes qu’il contient. Ce type de supposition n’est pas sans rappeler le modèle vectoriel où l’on suppose que les différents termes forment des dimensions orthogonales [4].

Maintenant que nous avons des formules pour $P(D_i|rel)$ et $P(D_i|nrel)$ , on souhaite calculer $\log \frac{P(D_i|rel)}{P(D_i|nrel)}$ afin d’appliquer le PRP. On peut utiliser les faits que $\log \frac{a}{b} = \log a - \log b$ et $\log (ab) = \log a+ \log b$ pour faciliter les calculs :
$\begin{eqnarray*} \log \frac{P(D_i|rel)}{P(D_i|nrel)} & =& \log P(D_i|rel) - \log P(D_i|nrel) \\ & =& \log \prod_{t_j\in D_j} P(t_j|rel) \prod_{t_j\notin D_j} (1-P(t_j|rel)) \\ & & - \log \prod_{t_j\in D_j} P(t_j|nrel) \prod_{t_j\notin D_j} (1-P(t_j|nrel)) \\ & =& \sum_{t_j\in D_j} \log P(t_j|rel)+ \sum_{t_j\notin D_j} \log (1-P(t_j|rel)) \\ & & - \sum_{t_j\in D_j} \log P(t_j|nrel) - \sum_{t_j\notin D_j} \log (1-P(t_j|nrel)). \end{eqnarray*}$
Nie et Savoie simplifient l’expression encore davantage dans le livre de référence. La quantité $\log \frac{P(D_i|rel)}{P(D_i|nrel)}$ est appelée « valeur de statut de recherche » et on doit trouver les documents $D_i$ qui la maximisent.

Conclusion : Le problème d’estimation de $P(D_i|rel)$ et $P(D_i|nrel)$ est maintenant un problème d’estimation de $P(t_j|rel)$ et $P(t_j|nrel)$ . C’est-à-dire qu’au lieu de travailler à l’estimation de la pertinence d’un document, on travaille maintenant à l’estimation de la pertinence d’un des termes (mots) contenus dans les documents.

Estimation a priori de $P(t_j|rel)$ et $P(t_j|nrel)$

Au départ, étant donné une recherche, on ne connaît ni $P(t_j|rel)$ ni $P(t_j|nrel)$ pour chacun des termes $t_j$ . On suggère de donner une valeur fixée à $P(t_j|rel)$ telle que 0,025. Quant à $P(t_j|nrel)$ , on peut utiliser la fraction des documents dans notre ensemble qui contient le terme $t_j$ ; ainsi, si le terme $t_j$ est très rare, la probabilité de non-pertinence sera basse et vice versa [5].

Estimation de $P(t_j|rel)$ et $P(t_j|nrel)$ par rétroaction

Une fois qu’une courte liste de documents est fournie à l’utilisateur, on peut lui demander quels documents sont pertinents afin de préciser notre estimation des probabilités $P(t_j|rel)$ et $P(t_j|nrel)$ et de lui fournir une meilleure solution. Supposons que l’utilisateur juge $r$ documents comme étant pertinents et que $r\prime$ de ces documents contiennent un terme donné $t_j$ . On a alors :

$P(t_j|rel) = \frac{r\prime}{r}$

ce qui est logique, car si tous les documents jugés pertinents contiennent un terme donné, il est probable qu’un document pertinent, choisi au hasard, contienne aussi le terme donné, et vice versa.
D’autre part, si $df_j$ est le nombre total de documents contenant le terme $t_j$ et $n$ est le nombre total de documents, on estime que

$P(t_j|nrel) = \frac{df_j-r\prime}{n-r}$

ce qui donnera, si la collection de documents est importante, une valeur qui ressemble à la valeur ( $P(t_j|nrel) = \frac{df_j}{n}$ ) suggérée a priori plus tôt.

Quels mots doit-on indexer ?

Dans un tout autre ordre d’idées, on peut utiliser un modèle probabiliste pour déterminer quels mots sont suffisamment significatifs pour qu’on les indexe. Par exemple, les mots le, la, et et ou sont trop communs pour permettre des recherches utiles.

Certains chercheurs ont constaté que la probabilité qu’un mot commun apparaisse $k$ fois, $P(k)$ , suivait une loi de Poisson, c’est-à-dire que $P(k)=\frac{e^{-k} (\lambda)^k}{k !}$ où $\lambda$ est le nombre moyen d’occurrences de ce mot dans un texte. Le tableau suivant représente $P(k)$ pour $\lambda=5$ .

$k$	$P(k)$
1	0.034
2	0.084
3	0.14
4	0.18
5	0.18
6	0.15
7	0.10
8	0.065
9	0.036
10	0.018
11	0.0082
12	0.0034
13	0.0013
14	0.00047

Pour distinguer les mots courants des mots inhabituels, il suffit donc de vérifier si les occurrences d’un mot se comportent comme une distribution de Poisson. Voici par exemple un mot dont les occurrences ne suivent pas une loi de Poisson et qui constituent donc un mot qu’on désire indexer (un mot comme constitution ou voiture pourrait suivre un tel modèle) :

$k$	$P(k)$
1	0.5
2	0.00
3	0.00
4	0.00
5	0.00
6	0.00
7	0.00
8	0.25
9	0.25

Pour être entièrement réaliste, on devrait sans doute tenir compte de la longueur des documents, mais on suppose ici que les documents ont tous une longueur comparable.

On peut aller plus loin et unifier la méthodologie PRP, présentée précédemment, avec l’idée voulant que certains termes sont plus ou moins utiles (comme le en comparaison avec constitutionnellement) ; c’est le sujet de travaux récents menant notamment à l’approche par intelligence artificielle comme dans le cas des réseaux de neurones ou des réseaux bayésiens.

Lecture optionnelle

Il existe de nombreux modèles probabilistes utilisés par les moteurs de recherche. Par exemple, la famille de modèles BM25 est souvent utilisée. Plusieurs chercheurs évaluent et comparent différents modèles, voici d’ailleurs une référence pertinente :

– Jones, K.S. and Walker, S. and Robertson, SE, A probabilistic model of information retrieval : development and comparative experiments, Information Processing and Management, 36, no 6, pages 779-808, 2000.

[1] Comparons ici les modèles probabilistes avec le modèle vectoriel qui mesure la similarité entre deux vecteurs afin de déterminer quels documents sont les plus pertinents.

[2] Tout ceci devrait vous sembler familier : en effet, encore une fois, c’est très proche du modèle vectoriel sauf que les vecteurs sont remplacés par des probabilités.

[3] Quand $x$ croît, $\frac{x}{1-x}$ croît et vice versa.

[4] Rappelons que le Latent Semantic Indexing est une des façons de s’assurer que les dimensions que l’on traite sont vraiment orthogonales.

[5] Ce qui est similaire au calcul fait pour le facteur idf.

Semaine 7