TE1 Flashcards
(76 cards)
1
Q
Qu’est-ce que la Recherche d’Information ?
A
L’ensemble des méthodes et techniques pour
- l’acquisition,
- l’organisation,
- le stockage,
- la recherche
- la sélection
d’information pertinente pour un utilisateur.
2
Q
Quels sont les domaines d’application de la recherche d’information ?
A
– Recherche locales sur les forums, blogs, sites de news
– Recherche sur les réseaux sociaux (facebook, twitter, telegram, etc.)
– Recherche sur les sites internes des entreprises
– Recherche sur les sites de bibliothèques numériques – Recherche sur les sites spécialisés (médecine, droit, littérature, chimie, mathématique, brevets, etc.)
– Recherche local sur ordinateurs et appareils mobiles personnel (Mac OS Spotlight, Desktop search)
– En combinaison avec les autres applications: système de recommandation (Netflix, Amazon, etc.), analyse big data, etc.
3
Q
Un document peut être … ?
A
– un texte complet (livre, article de news, blog)
– une partie de texte (chapitre, paragraphe, phrase)
– une page Web (html, php)
– une image
– une vidéo
– Etc.
4
Q
Que fait requête ?
A
Exprime le besoin d’informations de l’utilisateur
5
Q
Sous quelle forme se présente une requête ?
A
Peut être sous forme de description textuelle, mots clés, un exemple de document similaire, etc.
6
Q
Comment définir la notion de pertinence ?
A
Un document pertinent est un document qui doit contenir l’information que l’utilisateur recherche.
– notion qui peut être complexe et subjective selon le contexte et qui dépend de
• l’utilisateur
• la requête
– c’est sur cette notion que les systèmes de recherche d’information sont jugés.
7
Q
Qu’est-ce qu’une information structurée ?
A
Information structurée en champs => on se rapproche des systèmes de gestion de bases de données
– requête simple
– correspondance exact (SQL)
8
Q
A quelle type d’information (structurée ou non), la RI s’intéresse-t-elle?
A
RI s’intéresse surtout à l’accès à l’information non-structurée, même si, dans les documents textuels, il peut y avoir une partie structurée: champs (auteur, date, titre, etc.)
9
Q
Quel est le le problème central de la RI ?
A
Comment juger la pertinence est le problème central de la RI.
10
Q
Quels types de besoin en information existe-t-il ?
A
– Ponctuel (adhoc)
– Récurrent (filtrage, alertes, flux RSS)
Ils utilisent les mêmes technologies.
11
Q
Comment s’exprime un besoin ?
A
Langage de requêtes
– Texte libre, Liste de mots clés
– Avec ou sans opérateurs (AND, OR, NOT, etc.)
– Images
– Aucun : navigation dans une liste de concepts
12
Q
Quel est le paradoxe de la RI (ASK) ?
A
- Une “requête idéale” doit comporter toutes les informations que l’utilisateur recherche –> la similarité serait maximale (doit avoir toutes les infos que l’utilisateur recherche)
- Or, l’utilisateur recherche une information qu’il ne connaît pas à priori, il ne peut donc pas l’exprimer (décrire) de manière précise (idéale)
Ce phénomène est qualifié par Belkin comme ASK : “Anomalous State of Knowledge”.
13
Q
Comment évaluer un outil de recherche?
A
- Précision: fraction de documents récupérés correspondant au besoin d’informations de l’utilisateur
- Rappel: fraction de documents pertinents dans la collection qui sont récupérés
14
Q
Quel est le modèle le plus simple pour fonder un système de recherche d’information ?
A
Le modèle booléen
15
Q
Google utilise-t-il le modèle booléen?
A
Pas tout-à-fait mais il se base dessus.
– Oui, car on peut spécifier les opérateurs de recherche booléenne.
– Oui, car il essaie au mieux de respecter l’expression booléenne de la requête.
– Non, car il permet de faire un classement des résultats.
• Sur Google, l’interprétation par default d’une requête sous forme de w(1) w(2) …w(n) est :
– w(1) AND w(2) AND … AND w(n)
• Il y a pourtant des cas où on obtient des résultats qui ne contiennent pas un w(i) :
– le terme était présent sur le lien qui pointe la page (texte d’ancre)
– la page contient une variante de w(i) (morphologie, correction orthographique, synonyme)
– expression booléenne génère très peu de résultats
16
Q
Quelle est la différence principale entre le modèle booléen et le modèle utilisé par Google ?
A
- La recherche booléenne simple renvoie les documents correspondants sans ordre particulier.
- Google (et le moteurs de recherche les mieux conçus) classe l’ensemble de résultats. Il utilise certains estimateurs pour classer les bons résultats plus haut que les mauvais résultats: ranking.
17
Q
Qu’est-ce qu’une matrice d’incidence terme-document ?
A
La solution pour éviter de parcourir linéairement les textes à chaque nouvelle requête –> elle consiste à indexer les documents à l’avance.
18
Q
Prenons les vecteurs d’incidence suivant: Antony 110001, Cleopatra 100000 et Calpurnia 010000.
Quel est le vecteur d’incidence correspondant à la requête “(Antony or Cleopatra) and not Calpurnia”?
A
100001
19
Q
Quelle est la structure clé de la RI ?
A
Index inversé
20
Q
Qu’est-ce que l’index inversé ?
A
Pour chaque terme t, on stocke la liste de tous les documents qui contiennent t. Chaque document est identifié par un docID, un numéro de série de document.
Brutus –> 1, 2, 4, 11, 31, 45, 173, 174
Caesar –> 1, 2, 4, 5, 6, 16, 57, 132
Calpurnia –> 2, 31, 54, 101
21
Q
Quelles sont les premières étapes du traitement de texte ?
A
- Tokenisation
- Normalisation
- Stemming (racinisation)
- Stop words (mots-vides)
22
Q
En quoi consiste la tokenisation ?
A
Couper la séquence de caractères en tokens de mots. S’occuper des cas tels que John’s, a state-of-the-art solution.
23
Q
En quoi consiste la normalisation ?
A
Mapper le texte et les termes de requêtes à la même forme. Vous voulez que U.S.A. et USA correspondent.
24
Q
En quoi consiste le stemming (racination) ?
A
Nous pouvons souhaiter que différentes formes d’une racine correspondent
• kill, killed
25
En quoi consistent les stop words (mots-vides) ?
Nous pouvons omettre des mots très courants (ou non)
| • the, a, to, of
26
Prenons un corpus de 1 million de documents, chacun d’une longueur de 1000 mots, et un vocabulaire total de 500’000. Quelle est la taille maximale approximative des listes des occurrences et la taille de la matrice de cooccurrence?
10^9 et 5 * 10^11
27
Si les longueurs des deux listes des occurrences sont x et y, quelle est la complexité algorithmique dans le pire des cas pour fusionner les listes d’occurrences dans une requête OR?
O(x+y)
28
Considérons une requête qui est un AND de n termes. Pour chacun des n termes, obtenir ces listes des occurrences, puis les combiner avec AND.
Quel est le meilleur ordre pour le traitement de cette requête?
De la plus petite à la plus grande.
29
Quel est le problèmes avec des index biword ?
• Faux positifs
• Explosion d’index due à un dictionnaire plus grand
– Infaisable pour plus que deux mots, même très grand pour les biword.
• Les index biword ne sont pas la solution standard (pour tous les mots-clés) mais peuvent faire partie d'une stratégie composée.
30
En quoi consistent les index biword ?
Il s'agit d'une manière de séparer une query (requête) en groupe de deux mots utilisés pour effectuer des recherches booléennes sur les fichiers.
Par exemple the texte "Applied Science University" génèrerait les biwords
– applied science
– science university
31
En quoi consiste les index positionnels ?
Dans la listes des occurrences, stocker pour chaque terme la ou les position(s) dans lesquelles les tokens apparaissent:
32
Etant donné la liste des occurrences pour le mot “be”
Quels documents 1, 2, 4 et 5 pourraient contenir ‘to be or not to be’?
A. Documents 1, 4 , et5
B. Documents 4 et5
C. N’importe lequel entre eux, nous ne pouvons pas dire D. Seulement document 4
33
Comment peut-on classer les documents de la collection par rapport à une requête ?
* Attribuer une note (un score) - disons [0, 1] - à chaque document
* Ce score mesure la qualité de la "correspondance" entre le document et la requête.
34
Qu'est-ce qu'est le coefficient Jaccard ?
• Une mesure couramment utilisée pour calculer le chevauchement de deux ensembles
• Si A et B sont deux ensembles, le coefficient de Jaccard est calculé comme suit :
JACCARD(A,B) = |A ∩ B| / |A ∪ B|
35
Quels sont les problèmes avec Jaccard ?
* Il ne tient pas compte de la fréquence des termes (combien de fois un terme apparaît dans un document).
* Il ne tient pas compte de l’impact des termes rares dans une collection. Les termes rares sont en effet plus informatifs que les termes fréquents.
* Nous avons besoin d'un moyen plus sophistiqué de normaliser la longueur de document.
36
En quoi consiste le modèle de sac de mots ?
* Nous ne considérons pas l’ordre des mots dans un document.
| * John is quicker than Mary et Mary is quicker than John auront les mêmes vecteurs.
37
Qu'est-ce que la fréquence de terme : tf ?
• La fréquence tf(t,d) du terme t dans le document d, est défini comme le nombre de fois où t apparaît dans d.
• Nous voulons utiliser tf lors du calcul des scores de correspondance requête-document. Mais comment faire?
• La fréquence brute des termes n'est pas ce qu’on veut.
– Un document avec 10 occurrences du terme est plus pertinent qu'un document avec 1 occurrence du terme.
– Mais pas 10 fois plus pertinent.
– La pertinence n'augmente pas proportionnellement à la fréquence des termes.
38
Pondération par Log-frequency fréquence logarithmique, c'est quoi ?
• La pondération d’un terme t dans un document d selon le schéma Log-frequency est :
w(t,d) = [1 + log(tf(t,d)) | si tf(t,d) > 0], [0 | sinon]
0 -> 0 , 1 -> 1, 2 -> 1.3, 10 -> 2, 1000 -> 4, etc
• Le score pour un paire de document-requête: la somme des fréquences logarithmiques de tous les termes qui appartiennent à la fois à q et d:
Somme(t appartenant à q et d) de w(t,d)
– Le score est 0 si aucun des termes de la requête est présent dans le document.
39
Qu'est-ce que la fréquence documentaire : df ?
dft est la fréquence documentaire du terme t: le nombre de documents qui contiennent t.
40
Quel(s) est(sont) le(s) problème(s) ave la fréquence documentaire ?
• La fréquence brute des termes, telle qu'elle est suggérée, souffre d'un problème critique:
– Tous les termes sont considérés comme également importants lorsqu'il s'agit d'évaluer la pertinence d'une requête.
• En fait, certains termes ont peu ou pas de pouvoir discriminant pour déterminer la pertinence.
– Par exemple, une collection de documents sur les voitures contiendra probablement le terme Voiture dans presque tous les documents. Un terme plus spécifique comme Audi est cependant moins fréquent.
– Si nous recherchons une voiture Audi, le terme Audi est plus important : Audi est plus spécifique que Voiture.
41
Comment est définit le poids idf ?
On définit le poids idf, l’inverse de la fréquence documentaire du terme t comme :
idf(t) = log10 (N/df(t))
De nouveau, on utilise log (N/df(t)) au lieu de N/df(t) pour "atténuer" l’idf.
42
Quel est l'effet de l'IDF sur le classement ?
L’idf affecte le classement des documents uniquement si la requête comporte au moins deux termes.
Par exemple, dans la requête «Audi Car», la pondération idfdoit augmenter le poids relatif d'Audi et diminuer le poids relatif de Car.
idf n'a aucun effet sur le classement des requêtes à un terme.
43
Qu'est-ce que la pondération tf-idf ?
Le poids tf-idf d’un terme est le produit de son poids tf et son poids idf.
w(t,f) = (1 + log(tf(t,d))) * log10(N/df(t))
44
Quels sont les principaux avantages du modèle vectoriel ?
* Approche simple et mathématique.
* Prend en compte les fréquences d'occurrences des mots locaux (tf) et globaux (idf).
* Fournit une correspondance partielle et des résultats classés.
* A tendance à bien fonctionner dans la pratique.
* Permet une mise en œuvre efficace pour les grandes collections de documents.
45
Quels sont les principaux désavantages du modèle vectoriel ?
• Manque les informations sémantiques. Ex: sens des mots
• Manque les informations syntaxiques. Ex: structure de la phrase, ordre des mots, informations de proximité.
• Hypothèse d'indépendance du terme. Ex: ignore la synonomie
• Manque le contrôle d'un modèle booléen. Ex: exiger qu'un terme apparaisse dans un document.
Étant donné une requête à deux termes «A B», peut préférer un document contenant A fréquemment mais pas B, plutôt qu'un document contenant à la fois A et B, mais les deux moins fréquemment.
46
Comment se fait le calcul des scores cosinus ?
```
CosineScore(q)
1 float Scores[N] = 0
2 float Length[N]
3 for each query term t
4 do calculate w(t,q) and fetch postings list for t
5 for each pair (d, tf(t,d)) in postings list
6 do Scores[d] += w(t,d) * w(t,q)
7 Read the array Length
8 for each d
9 do Scores[d] = Scores[d]/Length[d]
10 return Top K components of Scores[]
-------------
=> term-at-a-term scoring
```
47
Dans le dernier algorithme de calcul des scores cosinus,
1– le score prend-il en compte la longueur de la requête?
2– pourquoi?
1- Non
2- La taille de la requête est une constante => aucun impact s/ le classement des résultats => aucune différence si l'on ignore la taille.
Il n'a une importance QUE si on le fait s/ plusieurs documents (il faut utiliser la taille de chacun d'entre eux)
48
A quoi ressemble la pipeline d'indexation ?
```
1- Documents à indexer
-> Tokeniseur ->
2- Flus de tokens
-> Modules linguistiques ->
3- Tokens modifiés
-> Indexeur ->
4- Index inversé
```
49
Devons-nous supprimer les mots vides ?
Utile à supprimer lors de la comparaison de paires de documents (ex: lors du clustering ou de la classification de documents)
Dans les applications de recherche, la tendance est de garder les mots vides
50
Qu'est-ce que l'algorithme de Porter ?
Un des algorithmes les plus courant de stemming:
- phrases appliquées séquentiellement
- chaque phrase se compose d'un ensemble de commandes
- exemple de convention _ parmi les règles d'une commande composée, sélectionnez celle qui s'applique au suffixe le plus long.
Exemples de règles typiques :
- sses -> ss (caresses -> caress)
- ies -> i (ponies -> poni)
- ss -> ss (caress -> caress)
- s -> _ (cats -> cat)
51
Pourquoi évaluer un système RI ?
Il existe de nombreuses alternatives dans la conception d'un système RI. Le choix d'une technique spécifique dépend de l'application et des données que vous traitez.
Comment savoir quelles techniques sont efficaces dans quelles applications / pour quelles données?
52
Quelles sont les questions à poser pour évaluer un système RI ?
• À quelle vitesse est-il indexé?
– Nombre de documents / heure
– Indexation incrémentale, par ex. s'il ajoute 10K produits / jour
• À quelle vitesse recherche-t-il?
– Besoins en latence et CPU
• À quel point est-ce évolutif?
– Si on passe de 5 millions à 20 millions de produits
53
Comment mesurer la qualité d’un nouvel algorithme de recherche ?
Pour mesurer l'efficacité de la recherche d'informations de manière standard, nous avons besoin d'une collection de tests composée de trois éléments:
1. Une collection de documents de référence (vos produits)
2. Une suite de requêtes de référence
3. Jugements de Pertinent ou Non Pertinent pour chaque requête et chaque document de la collection de tests
• Binaire (Pertinent vs Non Pertinent ) est le cas le plus simple
54
Quelles sont les mesures d’évaluations qu’on peut utiliser ?
```
– Précision
– Rappel
– Mesure F
– Graphe interpolé de Rappel-Précision
– MAP
– R-Précision
```
55
Un système RI renvoie 8 documents pertinents et 10 documents non pertinents. Il y a un total de 20 documents pertinents dans la collection. Quelle est la précision (P) et le rappel (R) du système sur cette recherche ?
P = 8/18 R= 8/20
56
Qu'est-ce que le Big Data
Big Data (données massives, ou mégadonnées) désigne un ensemble de données trop volumineuses, complexes et dynamiques pour pouvoir être géré par les outils conventionnels de gestion de base de données et d’analyse de données.
57
Quelles sont les caractérisation du Big-Data ?
Volume, Vitesse, Variété (V3)
58
Qu'entend-on par Volume dans le domaine du Big-Data?
* Un volume énorme de données est collecté sous forme de données sur le Web (p.ex.: données de capteurs, données météorologiques, données de vidéosurveillance, données de trafic routier, etc.)
* Le volume de Big Data fait référence à la taille des ensembles de données qui doivent être analysés et traités, qui sont souvent plus grands que les téraoctets et les pétaoctets.
* Le volume massif de données nécessite des technologies de traitement distinctes et différentes des capacités de traitement et de stockage traditionnelles.
59
Quelle est la taille du Big Data?
* Il n’existe pas de de seuil unique de taille pour qualifier les données de Big Data.
* Il est possible de séparer les tailles en trois niveaux approximatifs : Small (< 10 GB - excel, R), Medium (10 GB -> 1 TB - fichiers indexés, base de données monolithique), Big ( > 1 TB - Hadoop, base de données distribuées)
* Une indication utile: Les données Big Data sont si volumineuses qu’elles doivent être distribuées sur plusieurs machines.
60
Qu'entend-on par Vitesse dans le domaine du Big-Data?
• La vitesse fait référence à la vitesse à laquelle les données sont générées.
• Un exemple de données générées à grande vitesse serait les messages Twitter ou les publications Facebook.
• Il existe différents types de techniques et d'outils utilisés en fonction des analyses requises:
– Batch processing (Traitement par lots): lorsque le traitement se produit sur des blocs de données qui ont déjà été stockés sur une période de temps.
– Stream processing (Traitement de flux): permet de traiter les données en temps réel à mesure qu'elles arrivent et de détecter rapidement les conditions dans un court laps de temps à partir du point de réception des données.
61
Qu'entend-on par Variété dans le domaine du Big-Data?
* Le Big Data provient d'une grande variété de sources et est généralement l'un des trois types: les données structurées, semi-structurées et non structurées.
* La diversité des types de données nécessite souvent des capacités de traitement distinctes et des algorithmes spécialisés.
62
Un autre V: Véracité -> Qu'est-ce que c'est ?
• La véracité fait référence à la qualité des données analysées.
• Les données collectées sont souvent incertaines
– Données incohérentes
– Données incomplètes
– Données ambiguës
• Exemple: véracité des actualités communiquées sur twitter (incohérence due à la subjectivité humaine / manipulation), véracité des données des capteurs (incomplétude en raison d'un réseau peu fiable), etc.
• La qualité des données est primordiale pour l'analyse => L'analyse du Big Data nécessite souvent des techniques élaborées de prétraitement des données.
63
Pourquoi Big-Data?
• Les principales raisons de la croissance du Big Data sont:
1. Diminution du coût des capacités de stockage
2. Augmentation de la puissance de traitement
3. Augmentation de la disponibilité du réseau
4. Disponibilité des données
64
Quels sont les objectifs de Big Data ?
• Pour les entreprises, les données sont précieuses. Elle permettent:
– Une meilleure prise de décision
– Une meilleure compréhension des clients
– L’amélioration du processus opérationnel
– La réduction des coûts
• Problème principal
– Comment traiter/analyser efficacement des quantités massives de données?
65
Comment traiter le Big Data?
Diviser pour mieux régner ! :)
66
Qu'est-ce qu'est le MapReduce ?
• Modèle de programmation de haut niveau et implémentation pour le traitement parallèle de données à grande échelle.
– Conçu pour simplifier la tâche d'écriture de programmes parallèles
– Inventé par Google [Dean 2004]
– Implémentation open source: Hadoop
• Sa puissance est due à sa capacité à évoluer jusqu'à des centaines ou des milliers de machines pouvant avoir plusieurs cœurs.
* MapReduce permet de manipuler de grandes quantités de données en les distribuant dans un cluster de machines pour être traitées.
* De nombreux frameworks ont vu le jour afin d'implémenter le MapReduce. Le plus connu est Apache Hadoop.
* Un cluster MapReduce utilise une architecture de type maître-esclave où un nœud maître dirige tous les nœuds esclaves.
67
En quoi consiste l'approche MapReduce ?
Déplacer le traitement vers les données
--> ceci permet de diminuer la charge d'un seul processeur. Chaque processeur de données s'occupe de traîter ses propres données et envoie ensuite le résultat au processeur central.
68
Quels sont les avantages de l'approche MapReduce?
– Moins de mouvement de données sur le réseau.
– Le traitement a lieu en parallèle sur plusieurs machines.
– Traiter une copie du Web sur 1'000 machines: < 3 heures
69
Hadoop, c'est quoi?
– un projet Apache Open Source
– un cadre de calcul distribué
– un framework qui permet aux développeurs d'écrire des applications qui traitent de gros volumes de données
– conception basée sur Google File System (GFS)
70
Une installation Hadoop comporte principalement quoi?
– un cluster de machines (physiques ou virtuelles)
– le système de fichiers distribué HDFS (Hadoop Distributed File System)
– la base de données NoSQL HBase
– le cadre de calcul distribué MapReduce
– les applications informatiques écrites par le développeur
71
Quelles sont les étapes de la pipeline MapReduce ?
1 • Lire les données partitionnées (HDFS, GFS)
2 • Map: extraire une partie de l’enregistrement
3 • Mélanger (shuffle) et trier (fait par le système)
4 • Reduce: agréger, résumer, filtrer, transformer
5 • Écrire les résultats
72
Que faut-il donner à l'environnement d'exécution de MapReduce?
– Une fonction de Map
– Une fonction Reduce
– Les données
73
Que peut-on configurer dans MapReduce?
– La politique de shuffle et de tri
– Le nombre de tâches par reducer
– Formats d'entrée et de sortie
– Etc.
74
Qu'est-ce que le Framework Spark ?
Apache Spark est un framework open source qui combine
– un moteur de distribution de programmes sur des clusters de machines, avec
– un modèle élégant pour écrire des programmes dessus.
75
Resilient Distributed Datasets (RDDs) c'est quoi ?
• Spark est construit autour du concept d'un ensemble de données distribué résilient (RDD).
• RDD est une collection résiliente d'éléments répartis sur de nombreuses partitions qui peuvent être exploitées en parallèle.
• Trois éléments de la définition:
– Resilient: tolérante aux pannes et donc capable de recalculer les partitions manquantes ou endommagées en raison de pannes de nœuds.
– Distributed: les données résidant sur plusieurs nœuds dans un cluster.
– Dataset: une collection de données partitionnées avec des valeurs primitives ou des valeurs de valeurs, par ex. tuples ou autres objets (qui représentent des enregistrements des données avec lesquelles on travaille).
• De plus, un RDD présente les traits supplémentaires suivants:
– En mémoire: les données à l'intérieur de RDD sont stockées en mémoire autant (taille) et plus longtemps (temps) que possible.
– Immuable ou Read-Only: il ne change pas une fois créé et ne peut être transformé qu'en utilisant des transformations vers de nouveaux RDD.
– Typé: Les enregistrements RDD ont des types, par exemple Long dans RDD [Long] ou (Int, String) dans RDD [(Int, String)].
– Partitionné: les enregistrements sont partitionnés (divisés en partitions logiques) et distribués sur les nœuds d'un cluster.
76
Qu'est-ce que Spark apporte de plus que MapReduce ?
Spark maintient l'évolutivité linéaire et la tolérance aux pannes de MapReduce.
Mais il l'étend de trois manières importantes:
1. Le moteur Spark peut exécuter un graphe acyclique dirigé plus général (DAG) d'opérateurs. Pas seulement un format de map rigide puis de reduce!
2. Spark fournit un ensemble riche de transformations qui permet aux utilisateurs d'exprimer le calcul plus naturellement.
3. Spark fournit un traitement en mémoire. Les données d'un ensemble de données distribuées résilient (RDD) peuvent être matérialisées dans la mémoire du cluster, de sorte que les étapes futures qui souhaitent traiter le même ensemble de données n'ont pas besoin de le recalculer ou de le recharger à partir du disque.
