Chapitre 4 : Modèles

booléen, vectoriel

1
 Qu’est ce qu’un modèle de RI ?

• Un modèle est une abstraction d’un processus (ici

recherche d’info)
• Les modèles mathématiques sont souvent utilisés pour
– formaliser les propriétés d‘un processus,
– élaborer des conclusions, faire des prévisions, etc.
• Les conclusions dérivées d’un modèle dépendent de
la qualité du modèle
– Question : est ce que le modèle est une bonne
approximation du processus ?

2
 Qu’est ce qu’un modèle de RI ?
• Les modèles de RI peuvent décrire
– Le processus de mesure de pertinence : comment les documents
sont sélectionnés et triés
– L’utilisateur : besoin en information, interaction
– L’information

• Les modèles de RI manipulent plusieurs variables : les besoins,

les documents, les termes, les jugements de pertinence , les
utilisateurs, …

• Les modèles de RI se distinguent par le principe d’appariement

(matching) : appariement exact /approché (Exact /Best matching)

3
 Appariement exact /Appariement approché

• Appariement exact
– Requête spécifie de manière précise les critères recherchés
– L’ensemble des documents respectant exactement la requête
sont sélectionnés, mais pas ordonné

• Appariement approché
– Requête décrit les critères recherchés dans un document
– Les documents sont sélectionnés selon un degré de pertinence
(similarité/ probabilité ) vis-à-vis de la requête et sont
ordonnés

4
 Modèles de RI

• Panoplie de modèles
– Modèle booléen (±1950)
– Modèle vectoriel (±1970)
– Modèle LSI (± 1994)
– Modèle probabiliste (±1976)
– Modèle inférentiel (±1992)
– Modèle connexionniste (±1989)
– Modèle de langage (±1998)

5
 IR models
– Théorie des ensembles :
• Boolean model (±1950)
– Algèbre
• Vector space model (±1970)
• Spreading activation model (±1989)
• LSI (Latent semantic Indexing)(± 1994)
– Probabilité
• Probabilistic model (±1976)
• Inference network model (±1992)
• Language model (±1998)
• DFR (Divergence from Randomness model) (±2002)
– Learning to rank
6
Le Modèle booléen
Boolean Model

7
 Le Modèle Booléen

• Le premier modèle de RI
• Basé sur la théorie des ensembles
• Un document est représenté un ensemble de termes
– Ex : d1(t1,t2,t5); d2(t1,t3,t5,t6); d3(t1,t2,t3,t4,t5)
• Une requête est un ensemble de mots avec des
opérateurs booléens : AND (∧), OR(∨), NOT (¬)
– Ex: q = t1 ∧ (t2 ∨ ¬t3)
• Appariement Exact basé sur la présence ou l’absence
des termes de la requête dans les documents
– Appariement (q,d) = RSV(q,d)=1 ou 0
8
 Le Modèle Booléen

• q = t1 ∧ (t2 ∨ ¬t3)

• d1(t1,t2,t5); d2(t1,t3,t5,t6); d3(t1,t2,t3,t4,t5)

Rsv(q,d1)=
Rsv(q,d2)=
Rsv(q,d3)=

9
 Inconvénient du Modèle Booléen

• La sélection d’un document est basée sur une décision

binaire

• Pas d’ordre pour les documents sélectionnés

• Formulation de la requête difficile pas toujours

évidente pour beaucoup d’utilisateurs

• Problème de collections volumineuses : le nombre de

documents retournés peut être considérable
10
 Modèle Vectoriel
Vector Space Model (VSM)

11
 Modèle Vectoriel (Vector Space Model) (VSM)

• Proposé par Salton dans le système SMART (Salton,

G. 1970)
• Idée de base :
– Représenter les documents et les requêtes sous forme de
vecteurs dans l’espace vectoriel engendré par tous les
termes de la collection de documents :
T<t1,t2, …, tM> (un terme = une dimension)

– Document : dj= (w1j, w2j, …, wMj)

– Requête : q= (w1q, w2q, …, wMq)
wij: poids du terme ti dans le document djà tf*idf
12
 Modèle sac de mots

• La représentation vectorielle ne tient pas compte

de l’ordre des mots
– « Un garçon manque une pomme » est représenté
par le même vecteur que « une pomme mange un
garçon »
– à c’est ce que l’on appelle « Sac de mots » (Bag
of words)

13
 Modèle Vectoriel
• Une collection de n documents et M termes distincts peut
être représentée sous forme de matrice

T1 T2 …. TM
D1 w11 w21 … wM1
D2 w12 w22 … wM2
: : : :
: : : :
Dn w1n w2n … wMn

• La requête est également représentée par un vecteur.

14
 Mesure de la pertinence

• Pertinence est traduite comme une similarité de vecteurs

t1
d1
q
d2
θ Similarité ß Cos(θ)
t3

t2 d3

La pertinence est traduite en une similarité vectorielle :

un document est d1 est d’autant plus pertinent à une requête que le vecteur
associé est similaire à celui de la requête.
15
 Sec. 6.3

Similarité requête, document à Cosine(q,d)

Dot product

! ! ! ! V
! ! q•d q d ∑ qd
i =1 i i
cos( q, d ) = ! ! = ! • ! =
qd q d V 2
q
V
d 2
∑ i =1 i ∑ i =1 i

qi est le poids du terme ti dans la requête

di est le poids du terme ti dans le document
 Le Modèle Vectoriel
mesure de similarité

Inner product X ∩Y ∑x*y

i i

2* X ∩Y 2*∑ xi*yi
Coef. de Dice
X +Y ∑xi2+∑ y2j
Mesure du cosinus X ∩Y ∑x *y i i

X * Y ∑x *∑ y
2
i
2
j

Mesure du Jaccard X ∩Y ∑x *y i i

X + Y − X ∩Y ∑x +∑ y −∑x *y
2
i
2
j i i

17
 Sec. 6.4
Retour sur la pondéra/on
à 0*idf a plusieurs variantes

Une variante est identifiée par un nom d’attribut pour chaque colonne (un tf, un idf, une
normalisation)

Une pondération de type lnc à logarithme pour tf, pas d’idf , normalisation cosine
Une pondération de type ltcà logaritme pour tf, idf et cosine

Dans le modèle vectoriel on aura ce type de notation :

ddd.qqq (ddd pour le document, qqq pour la requête)

score(q, d) = ∑ w(t.q).w(t, d)
t∈q
 Sec. 6.4

Exemple lnc.ltc :

Document: car insurance auto insurance

Query: best car insurance

Terme Req (ltc) Document(lnc) Prod

freq tf nd idf w(t,q) Nor.li freq tf- w(t,d) n’lisa
sation tion
auto 0 0 5000 1 1

best 1 1 50000 0 0

car 1 1 10000 1 1

insurance 1 1 1000 2 1.3

N=10^6 documents

Score (q,d)= 0.8

 • ddd.qqq=lnc.ltc.

(1+ log(t, q))*idf (t)* (1+ log(t, d))

score(q, d) = ∑
t∈q
∑ ((1+ log(t, q))*idf (t)) 2
. ∑ (1+ log(t, d)) 2

t∈q t∈d

20
 Le Modèle Vectoriel

• Avantages:
– La pondération améliore les résultats de recherche
– La mesure de similarité permet d’ordonner les
documents selon leur pertinence vis à vis de la requête

• Inconvénients:
– La représentation vectorielle suppose l’indépendance
entre termes (?)

21
Extension du modèle Booléen

22
 Introduction

• Prendre en compte l’importante des termes dans les

documents et/ou dans la requête

• Possibilité d’ordonner les documents séléctionnés

• Comment étendre le modèle booléen ?

– Interpréter les conjonctions et les disjonction

• Deux modèles :
– Modèle flou- fuzzy based model (basé sur la logique floue)
– Modèle booléen étendu- extended boolean model

23
 Modèle booléen étendu
(extended Boolean Model)

24
 Modèle booléen étendu

• Combinaison des modèles booléen et vectoriel

– Document : liste de termes pondérés
– Requête booléenne
– Utilisation des distances algébriques pour mesurer la
pertinence d’un document vis-à-vis à d’une requête

25
 Modèle booléen étendu
appariement

• Considérons
– dj (w1j,w2j,… wtj)

– q : requête à deux termes

– qand = t1 et t2
– qor= t1 ou t3

26
 Intuition
• qand = t1 ∧ t2; w1j = x and w2j = y
t2 (1,1)

dj+1
AND/ET

y = w2j
dj

(0,0) x = w1j t1

((1 − w
1j ) 2
+ (1 − w2j ) 2
)
On veut se rapprocher du point (1,1) RSV (d j , t1 ∧ t2 ) = 1 −
2
 Intuition

• qor = t1 ∨ t2; wt1 = x and wt2 = y

(1,1)
t2

dj+1 OR/OU

dj
y = w2j

(0,0) x = w1j t1

On veut être le plus loin de (0,0) RSV (d j , t1 ∨ t2 ) =

(w
2
1j + w22 j )
2
 Modèle booléen étendu
appariement

• Considérons
– dj (w1j,w2j,… wtj)
– q : requête à deux termes

RSV (d j , t1 ∨ t2 ) =
(w
2
1j + w22 j )
2

RSV (d j , t1 ∧ t2 ) = 1 −
((1 − w 1j)
2
+ (1 − w2 j ) 2 )
2

29
 Modèle booléen (pnorm)étendu
appariement
• Généralisation
– Distance euclidienne à plusieurs dimensions
– Utilisation de la p-norm
• Considérons :
– un document dj (w1j,w2j,… wtj) et
q (t1, t2, ..tm) : une requête composée de m termes
1
p
w1pj +w2pj +...+wmj
p

RSV(dj,qor)=( m
)

p p p 1/ p
((1 − w1 j ) + (1 − w2 j ) + ... + (1 − wmj ) )
RSV (d j , qand ) = 1 −
m1/ p
RSV(dj,qnot)=1−RSV(dj,q)
30
 Modèle booléen(pnorm) étendu
appariement
• Si p = 1 alors (on retrouve le modèle vectoriel)
– RSV(dj,qor) = RSV(dj,qand)

• Si p = ∞ alors (modèle booléen)

– RSV(dj,qor) = max (wxj)
– RSV(dj,qand) = min (wxj)

• p=2 correpond à la distance euclidienne, semble être le

meilleur choix

31
 Modèle booléen (pnorm) étendu
appariement
• Généralisation :
– Si la requête et les documents sont pondérés
• q(q1, q2, .., qm)
• dj (w1j,w2j,… wtj)

1
p
qip*wijp
(∑ )
RSV(dj,qor)= ∑ qip

p p
∑ qi * (1 − wij )
RSV (dj, qand ) = 1 − ( )1 p
p
∑ qi

32
 Modèle booléen étendu

• Modèle puissant

• Calcul complexe

• Problème de distributivité
– q1=(t1 OU t2) ET t3
– q2=(t1 ET t3) OU (t2 ET t3)
– RSV(q1,d) <> RSV(q2,d)

33
 Exercice

• Exemple :
– T(document, web, information,
recherche,image,contenu) : ensemble des termes
d’indexation

– d1(document 0.3,web 0,5,image 0.2 )

– q1 (document OU web); q2(web ET document)

q3((web OU document) ET image)

34