Définition et évaluation de modèles d’agrégation pour l’estimation de la

pertinence multidimensionnelle en recherche d’information

Bilel MoulahiSous la direction de

Lynda Tamine & Sadok Ben Yahia

Équipe SIG – IRIT/ LIPAH - FST11 décembre 2015

2015

-20

16

Extrait des titres de papiers publiés, de l’introduction/conclusion avec http://www.wordle.net

Définition et évaluation de modèles d’agrégation pour l’estimation de pertinence multidimensionnelle en recherche d’information

3

ContexteLe temps comme facteur

principal dans l’estimation de pertinence

Attentat Paris Documents

Appariement

Documents pertinents (c1),

13/11(c2), sources de confiance (c3), …

Agrégation de scores

C3…

C2 C1

Attentat Paris Documents

Appariement

c1, c2, c3, …

Agrégation de scores

C3…

C2 C1

Temps

Période de temps spécifique

Estimation de pertinence

multidimensionnelle

4

Plan de la présentation

Approches multicritères pour l’estimation de pertinence de documents : contexte et problématique

Définition et évaluation d’un modèle d’agrégation de pertinence multidimensionnelle

Modèle d’agrégation sensible au temps

Conclusion et perspectives

Partie 1 Approches multicritères pour l’estimation de pertinence multidimensionnelle : contexte et problématique

Contexte

Recherche d’information classique : Faciliter l’accès à

l’information Besoin représenté par des

mots clés (Vickery, 1959; Cooper, 1971; Harter, 1992)

Approche généraliste : Résultats dépendant que de la requête

requête Documents

Appariement

besoin

6

7

Pertinence multidimensionnelle

Multiplicité des dimensions (Borlund, 2003, Saracevic, 2007, Taylor et al., 2007) Impact sur l’estimation de la

pertinence finale Dépendance (Carterette et al., 2011;

Eickhoff et al., 2013) Perception personnelle des

utilisateurs (Tamine et al., 2011, Sieg et al., 2007) Subjectivité entourant les

dimensions

Critère thématique

Fraîcheur

Autorité (influence, #tweets/mentions)

Critère thématique

Fraîcheur

Localisation géographique

Centres d’intérêts

8

Problème : énoncé

Modélisation de la pertinence multicritères : quel modèle ?

Comment modéliser

l’interdépendance et synergies

entre les critères ?

Comment quantifier

l’importance des critères ?

Comment personnaliser le

modèle de pertinence

multicritères ?

9

Problème : RI et approches multicritères

Analyse multicritère « Science vouée à

l’éclaircissement de la compréhension d’un

problème de décision et à sa résolution »

Fusion de données Choix social Prise de décision

multicritères Agrégation de préférences

• Doc 1• Doc 2• Doc 3

Critère 1

• Doc 2• Doc 1• Doc 3

Critère 2

• Doc 2• Doc 3• Doc 1

Critère 3

10

1

23

0

0.5

1

Series1 Series2 Series3 Series4

Problème : Illustration

Documents ayant le même score global mais pas les

mêmes scores partiels! Lequel retourner?

Degré d’importance des critères pour chaque

utilisateur

0,25 0,25

0,25 0,25

0,25

0,25 0,25

0 0,5

0,25

0,1 0,1

0,1 0,7

0,25

Diversité des préférencesAdditivité

11

Combinaison multicritères en RI : aperçu

Approches par valeurs

Approches classiques

Moyenne arithmétique

pondérée, Combinaison linéaire (Si et Callan, 2002;

Craswell et al., 2005; Damak et al., 2011; Wei et al., 2011), OWA (Yager, 1988),

Owmin (Boughanem et

al. 2006)

Agrégation prioritaires

Scoring, And (Celia et al., 2009, 2011)

Approches par listes

Agrégation d’ordonnancements

Comb* (Fox et Shaw, 1993),

Borda, RR, Condorcet

(Condorcet, 1785), distance

de Kendall (Fagin et al.,

2003), chaînes de Markov (CM) (Dwork et al.,

2001; Renda et Straccia, 2003)

Apprentissage d’ordonnancements

RankNet (Burges

et al., 2005), RankSVM (Joachims,

2006), ListNet (Cao et al.,

2007),Random Forest

(Breiman, 2001).

Approches de surclassement

Electre (Roy, 1991),

PROMETHE (Brans et

Vincke, 1985; Brans et al.,

1984), TACTIC (Vansnick, 1986)

• Score d1• Score d2• Score d3

Critère i

• Score d2• Score d1• Score d3

Critère j

• Score d2• Score d3• Score d1

Critère k

12

Combinaison multicritères en RI : positionnement

Approche Description Apprentissage Dépendance Personnalisatio

nInterprétati

onCombinaison linéaire

Somme pondérée des scores

Moyennes ordonnées

Somme ordonnée et pondérée des scores

Opérateurs prioritaires

Relation de priorité entre les critères

Apprentissage d’ordonnancement

Apprentissage automatique de modèle

Approche d’agrégation de pertinence multidimensionnelle

Définition d’une mesure floue sur les critères

Partie 2. Définition et évaluation d’un

modèle d’agrégation de pertinence multidimensionnelle

14

iAggregator: Modèle d’agrégation pour l’estimation de pertinence multidimensionnelle

Personnalisation des préférences

Modélisation des interactions entre l’ensemble des critères

Poids d’importance sur des combinaisons de critères : capacité

Mesure floue sur les critères

Comment modéliser

l’interdépendance et synergies entre

les critères ?

Comment hiérarchiser les

critères selon leur importance ?

Comment personnaliser le

modèle de pertinence

multicritères ?

15

iAggregator: Modèle d’agrégation pour l’estimation de pertinence multidimensionnelle

Mesure floue Définition des poids d’importance

Modélisation des interactions entre

les critèresModèle

Mesure floue (capacité) Fonction d’utilité , valeurs dans [0,1]

: Importance d’un critère ou un sous ensemble de critères

• μ{ci, cj} >= μ{ci} + μ{cj}• Impact de satisfaction d’un seul critère vs. la

satisfaction de deux critères

Interaction positive (complémentarité)• μ{ci, cj} <= μ{ci} + μ{cj} • biais introduit par les critères redondants

Interaction négative (redondance) 1

2

3

4

ci

cj

1

2

3

4

ci

cj

Pénaliser les documents surestimés selon un

seul critère de pertinence

atténuer le biais qui pourrait être introduit par l’implication

des critères de pertinence redondants

iAggregator: Modèle d’agrégation pour l’estimation de pertinence multidimensionnelle

Additivité Définition des poids d’importance

Modélisation des interactions entre

les critèresModèle

Mesure floue (capacité) Fonction d’utilité , valeurs dans [0,1]

: Importance d’un critère ou un sous ensemble de critères

• μ{ci, cj} >= μ{ci} + μ{cj}

Interaction positive (complémentarité)

• μ{ci, cj} <= μ{ci} + μ{cj}

Interaction négative (redondance)

RSV (𝑐1 ,𝑐2 ,… ,𝑐𝑛) (𝑞 ,𝑑 𝑗 )= h𝐶 𝜇 (RSV𝑐1 (𝑞 ,𝑑 𝑗 ) ,… ,RSV𝑐1 (𝑞 ,𝑑 𝑗 ) )

¿∑𝑖=1

𝑛

rsv𝑖( 𝑗 )(μ{𝑐 𝑖 ,… ,𝑐𝑛 }−μ{𝑐 𝑖+1 ,…,𝑐𝑛 })

Score (partiel) suivant

Score (partiel) ordonné suivant

Différence de l’importance de la coalition du reste des critères

Modèle basé sur l’intégrale de Choquet

16

17

Interprétation du modèle

Indice d’importance (Shapley):

(Grabisch et al., 2000)

Contribution moyenne qu’un critère apporte à

toutes les autres combinaisons de critères possibles

Indice d’interaction (Grabisch et al., 2000)

Degré d’interaction entre deux critères:

Nulle, positive, négative

18

Apprentissage des poids d’importance

Objectif• Identification des

valeurs de capacités

Données• Requêtes, Scores des

documents, jugements

Étapes• Paramétrage• Optimisation

Para

mét

rage 1. Génération

d’un ensemble de valeurs de capacités2. Agrégation3.Identification des meilleures valeurs initiales

Optim

isatio

n Interpolation des scores globauxMesure objective : P@X/ Méthode des moindre carrés

q1,d11:(RSVc1(q1,d11),...,RSVcN(q1,d11)):l11q1,d12:(RSVc1(q1,d12),...,RSVcN(q1,d12)):l12

q1,d1K:(RSVc1(q1,d1K),...,RSVcN(q1,d1K)):l1K

qm,dm1:(RSVc1(qm,d1m),...,RSVcN(qm,d1m)):lm1qm,dm2:(RSVc1(qm,d2m),...,RSVcN(qm,d2m)):lm2

qm,dmK:(RSVc1(qm,dmK),...,RSVcN(qm,dmK)):lmK

19

Modèle d’agrégation pour l’estimation de pertinence multidimensionnelle : approche personnalisée

Identification des préférences des utilisateurs

Personnalisation

RSV (𝑐1 ,𝑐2 ,… ,𝑐𝑛)𝑢 (𝑞 ,𝑑 𝑗 )= h𝐶 𝜇 (RSV𝑐1

𝑢 (𝑞 ,𝑑 𝑗 ) ,…,RSV𝑐𝑛

𝑢 (𝑞 ,𝑑 𝑗 ) )

¿∑𝑖=1

𝑛

𝑟𝑠𝑣 ( 𝑖 ) 𝑗𝑢 (μ{𝑐 𝑖 , …, 𝑐𝑛 }

𝑢 ,…,μ{𝑐 𝑖+1 , …,𝑐𝑛 }𝑢 )

Score (partiel) personnalisé suivant

Poids personnalisé d’un utilisateur u

Comment personnaliser le

modèle de pertinence

multicritères ?

20

Contexte de RI sociale

Recherche de tweets• 3 Critères : thématique, autorité,

fraîcheur• Collection de test fournie par la

tâche Microblog de TREC• 16 millions de tweets

Contexte de RI personnalisée

Recherche de lieux d’attraction• 2 critères : localisation, intérêts• Collection de test fournie par la tâche TREC Contextual Suggestion

Recherche dans les folksonomies• 2 critères : topicalité, intérêts• Base de test collectée de Delicious

Évaluation expérimentale : cadres d’applicationObjectifs : • O1. Estimer l’importance des critères en tenant compte de

leur propriétés• O2. Evaluer le modèle d’estimation de pertinence globale

21

Baselines

Moyenne arithmétique (MA)

Moyenne arithmétique pondérée

Mécanisme de combinaison linéaire

Opérateurs d ’agrégation prioritaires (And, Scoring) (Costa Pereira, 2012)

Opérateurs Min et Max

Opérateurs OWA et OWMin

L2R : RankSVM, LambdaMART,

Métrique d’évaluation

Mesures officielles des tâches Microblog de TREC 2011 et 2012• P@30• MAP

Protocole d’évaluation

Apprentissage : Requêtes TREC

Microblog 2011 (49) : Expérimentation de 19 combinaison de

capacités

Test : requêtes de la tâche Microblog

2012 (60)

Évaluation expérimentale : recherche de tweets

22

Apprentissage des capacités & Interaction des critères

• Valeurs de capacité différentes -> impact sur la précision

• Topicalité > Fraîcheur > autorité

Paramétrage

• Dimensions de pertinence dépendantes

• Interaction positive, négative suivant la collection

Dépendance

• Critère autorité : faible importance : 0,12

Importance

O1. Estimer l’importance des critères en tenant compte de leur propriétés

RésultatsComparaison avec les opérateurs

classiques Comparaison avec l’opérateur Scoring

Différence plus importante pour : AM, WAM, MAX

Min, And : même performances

15 % vs. Scoring / % Requêtes : 36% Iaggregator vs 22% Scoring 23

O2. Evaluer le modèle d’estimation de pertinence globale

Résultats (2)Comparaison avec méthode

d’apprentissage d’ordonnancement Comparaison avec RankSVM

Différence plus importante pour : RF, ListNetDifférence faibles % RankSVM, RankNet (5 % )67% Iaggregator vs 33% RankSVM (% Requêtes)

OpérateurPrécision

P@10 P@20 P@30 MAPRankSVM 0,2500 0,2250 0,2218 0,0871 5,17%RankNet 0,2448 0,2198 0,2201 0,0858 5,89%ListNet 0,0931 0,1009 0,1115 0,0485 52,33%RF 0,0810 0,0681 0,0687 0,0628 70,68%λ−MART 0,2276 0,2092 0,2043 0,1856 11,67%iAggregator

0,2345 0,2293 0,2339 0,1252-6.60% +1.87% +5.17% +30.43%

24

25

Évaluation expérimentale : cadre personnalisé

Utilisateurs Profils (exemples)

63550

Contextes (requête) 50Documents (suggestions) 3925 (157)

Base de test

Position géographique dans une ville

Google Place API (restaurants, pizzeria, musée, …)

Lieu, (URL, description)

Evaluer des techniques de recherche répondant à des besoins en information dépendant du contexte des utilisateurs : • chercher les places d’attractions pouvant

l’intéresser suivant deux critères de pertinence : • Centres d’intérêts• Localisation géographique

Mesure d’évaluation : P@5 (officielle)

Modèles de références : • Agrégation de pertinence

multidimensionnelle : moyenne arithmétique pondérée, Scoring, And

• Personnalisation des préférences : Intégrale de Choquet classique

26

Apprentissage & interaction

Diversité sur les préférences

O1. Estimer l’importance des critères en tenant compte de leur propriétés

27

Résultats

Différence relativement plus importante pour la méthode WAM et And

O2. Evaluer la personnalisation sur le modèle d’estimation de pertinence globale

28

Constats

•Plus les critères sont dépendants, plus la différence de performance est importante•Propriétés mathématiques intéressantes utiles en RI

Avantages

• Apprentissage :• Sensitivité aux

choix des paramètres initiaux

• Evaluation :• Vérité de terrain• Mesures

Défis

Partie 3.

Modèle d’agrégation sensible au temps

30

Problématique : temps comme critère de pertinence

Modélisation de la pertinence temporelle

Identification de la sensibilité de la requête au tempsCaractérisation des périodes pertinentes à la requête

Combinaison du critère temporel et thématique

Temps au niveau des requêtes

Temps au niveau des documents

Temps au niveau des modèles

d’ordonnancement

•Dimension temporelle exploitée de façon brute

• Temps de soumission des requêtes • Temps de publication des documents

•Collections de données statiques

31

Modèle sensible au temps : intuition

Termes des requêtes sont temporellement corrélés dans les documents pertinents

32

Modèle sensible au temps : Intuition - validation (2)

Modélisation statistique avec les séries chronologiques (Montgomery et al., 2008) dans les documents pertinents de la tâche TREC TS

Axe des abscisses : temps (heures) Axe des ordonnés : importance des

termes𝒕𝒇 (𝒘 𝒊 ,𝑫𝒕)

|𝑫𝒕|

Terme 1 : pakistan Terme 2: factory Terme 3 : fire Requête : pakistan factory fire

33

Analyse de corrélation temporelle : Intuition - validation (3) Objectif :

• Vérifier l’hypothèse de dépendance temporelle entre des requêtes• Tâche TREC TS 2013

Les termes appartenant à la

même requête sont plus corrélées que celles ne faisant pas partie de la même requête

Mots de requêtes de la collectionMot

s de

req

uête

s de

la c

olle

ctio

n

34

Modèle sensible au temps : hypothèse

Les documents qui sont susceptibles d’être pertinents

en réponse à une requête, sont ceux qui sont à la fois

pertinents pour tous les termes de la requête et qui sont

publiés dans des périodes de temps similaires

Terme 1

Terme 2

Terme 3 Terme i..

d1 d2 d2 d4

d2 d3 d4 d2

d3 d4 d3 d3

d4 d5 d5 d5

d5 d1 d1 d1

35

Modèle sensible au temps

Pertinence des documents suivant chaque terme de la requête

Fusion des listes d’ordonnancements selon les

termes des requêtes en une seule liste résultante.

booster les documents qui sont publiés dans les

mêmes périodes de temps qu’un nombre important de

documents pertinents retournés en réponse à tous

les termes de la requête

𝑃 (𝑑𝑡|𝑤𝑖 )=𝑃 (𝑑 ,𝑡|𝑤𝑖 )∝𝑃 (𝑑|𝑤𝑖 )𝑃 (𝑡|𝑤𝑖)

)

Pertinence thématique

𝑃 (𝑤𝑖|𝑑 )=𝑡𝑓 (𝑤 𝑖 ,𝑑)+𝜇

𝑡𝑓 (𝑤 𝑖 ,𝑑)¿𝐷∨¿|𝑑|+𝜇

¿

Pertinence temporelle

𝑃 (𝑡|𝑤 𝑖 )=𝑡𝑓 (𝑤 𝑖 ,𝐷 𝑡)

|𝐷 𝑡|

𝑇𝑇𝐷𝑀 (𝑑𝑡∈𝐷 )=∑𝑟 ∈𝑅

1𝜖+𝑟 (𝑑𝑡)

∗𝑘𝑒𝑟𝑛𝑒𝑙(𝑡 , 𝑡𝑎𝑣𝑔)

𝑘𝑒𝑟𝑛𝑒𝑙 (𝑡1 , 𝑡2 )= 1√2𝜋𝜎

∗𝑒𝑥𝑝[−(𝑡 1− 𝑡2)2

2𝜎2 ]

36

Baselines

Un modèle atemporel : le modèle de langue (ML) avec un

lissage Dirichlet (Zhai et Lafferty, 2004)

Le modèle de langue temporel Dakka et al. (2)

Le modèle Recency Prior (RP) Li et Croft (2003)

Métrique d’évaluation

Précision

Rappel

F-mesure

Protocole d’évaluation

Apprentissage : Requêtes TREC

Temporal Summarization 2013

Test : requêtes de la tâche TS

2014

Évaluation expérimentale

37

Résultats expérimentaux

Amélioration de + 32.74% en terme de F-mesure

Précision Rappel F-

Mesure %↗

ML 0,0830 0,2019 0,1177 +32,47%MLT 0,1307 0,1772 0,1504 +13,71%RP 0,0866 0,2019 0,1212 +30,46%TTD-M 0,1692 0,1797 0,1743 -

38

Résultats expérimentaux (2)TTD-M fournit des meilleurs résultats que RP pour 60% des requêtes (9 / 15).

ID Termes de requête F-Mesure %↗RP TTD-M11 costa concordia 0,2055 0,0904 55,98%12 european cold wave 0,0763 0,0347 54,49%13 queensland floods 0,2262 0,0787 65,21%

14 boston marathon bombing 0,0802 0,1171-45,99%

15 egyptian riots 0,1525 0,1028 32,56%16 quran burning protests 0,3646 0,2352 35,47%

17 in amenas hostage crisis 0,1252 0,2361-88,59%

18 russian protests 0,2107 0,0971 53,89%19 romanian protests 0,347 0,0794 77,10%20 egyptian protests 0,0831 0,0727 12,48%21 russia meteor 0,0707 0,143 -100%22 bulgarian protests 0,1967 0,0606 69,15%

23 shahbag protests 0,0281 0,0489-73,92%

24 nor’easter 0 0 025 Southern California shooting 0,0057 0,051 -100%

Nom

bre

des d

ocs p

ertin

ents

Temps (heures)

Conclusion

1. Modèle de combinaison de pertinence multicritères pour l’estimation de pertinence multidimensionnelle Opérateur d’agrégation flexible Algorithme pour l’apprentissage des poids d’importance Evaluation approfondie du modèle (3 tâches)

2. Approche d’agrégation personnalisée 3. Intégration de la dimension de pertinence

temporelle Analyse temporelle de la dépendance des terme de requêtes Modèle sensible au temps

Perspectives

Court terme • Réduire la complexité

de l’algorithme d’apprentissage des capacités

• Traiter le problème d’agrégation en l’absence de scores

Moyen terme• Evaluer la sensitivité

des paramètres du modèle d’ordonnancement sensible au temps

• Tester l’efficacité du modèle dans d’autres collection de données

Merci de votre attention !