Modèle d'espace vectoriel

Le modèle d'espace vectoriel ou modèle vectoriel de terme est un modèle algébrique permettant de représenter des documents texte (ou plus généralement des éléments) sous forme de vecteurs de telle sorte que la distance entre les vecteurs représente la pertinence entre les documents. Il est utilisé dans le filtrage d'informations , la recherche d'informations , l'indexation et les classements de pertinence. Sa première utilisation a été dans le système de recherche d'informations SMART .

Définitions

Dans cette section, nous considérons un modèle d'espace vectoriel particulier basé sur la représentation en sac de mots . Les documents et les requêtes sont représentés sous forme de vecteurs.

{\displaystyle d_{j}=(w_{1,j},w_{2,j},\dotsc ,w_{n,j}) <semantics> <mrow> <mstyle> <msub> <mi>d</mi> <mrow> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{ displaystyle d_ {j} = (w_ {1, j}, w_ {2, j}, dotsc, w_ {n, j})}</annotation> </semantics> </math></span><img src=

{\displaystyle q=(w_{1,q},w_{2,q},\dotsc ,w_{n,q}) <semantics> <mrow> <mstyle> <mi>q</mi> <mo>=</mo> <mo>(</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>q</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> <mo>,</mo> <mi>q</mi> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>q</mi> </mrow> </msub> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle q=(w_{1,q},w_{2,q},\dotsc ,w_{n,q})}</annotation> </semantics> </math></span><img src=

Chaque dimension correspond à un terme distinct. Si un terme apparaît dans le document, sa valeur dans le vecteur est différente de zéro. Plusieurs méthodes différentes de calcul de ces valeurs, également appelées pondérations (de terme), ont été développées. L'un des schémas les plus connus est la pondération tf-idf (voir l'exemple ci-dessous).

La définition du terme dépend de l'application. En général, les termes sont des mots simples, des mots-clés ou des phrases plus longues. Si des mots sont choisis comme termes, la dimensionnalité du vecteur est le nombre de mots dans le vocabulaire (le nombre de mots distincts présents dans le corpus ).

Les opérations vectorielles peuvent être utilisées pour comparer des documents avec des requêtes.

Applications

Les documents candidats du corpus peuvent être récupérés et classés à l'aide de diverses méthodes. Le classement par pertinence des documents dans une recherche par mot-clé peut être calculé, en utilisant les hypothèses de la théorie des similitudes de documents , en comparant l'écart des angles entre chaque vecteur de document et le vecteur de requête d'origine où la requête est représentée comme un vecteur de même dimension que les vecteurs qui représentent les autres documents.

En pratique, il est plus simple de calculer le cosinus de l'angle entre les vecteurs, plutôt que l'angle lui-même :

{\displaystyle \cos { heta }={\frac {\mathbf {d_{2}} \cdot \mathbf {q} }{\left\|\mathbf {d_{2}} ight\|\left\|\mathbf {q} ight\| <semantics> <mrow> <mstyle> <mi>parce que</mi> <mo>⁡</mo> <mrow> <mi>θ</mi> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <msub> <mi>d</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> <mo>⋅</mo> <mrow> <mi>q</mi> </mrow> </mrow> <mrow> <mrow> <mo>‖</mo> <mrow> <msub> <mi>d</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> <mo>‖</mo> </mrow> <mrow> <mo>‖</mo> <mrow> <mi>q</mi> </mrow> <mo>‖</mo> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \cos { heta }={\frac {\mathbf {d_{2}} \cdot \mathbf {q} }{\left\|\mathbf {d_{2}} ight\|\left\ |\mathbf {q} ight\|}}}</annotation> </semantics> </math></span><img src=

Où est l'intersection (c'est-à-dire le produit scalaire ) des vecteurs document (d ₂ dans la figure de droite) et requête (q dans la figure), est la norme du vecteur d ₂ et est la norme du vecteur q. La norme d'un vecteur est calculée comme suit : ${\displaystyle \mathbf {d_{2}} \cdot \mathbf {q} <semantics> <mrow> <mstyle> <mrow> <msub> <mi>d</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> <mo>⋅</mo> <mrow> <mi>q</mi> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathbf {d_{2}} \cdot \mathbf {q} }</annotation> </semantics> </math><img src=$ ${\displaystyle \left\|\mathbf {d_{2}} ight\| <semantics> <mrow> <mstyle> <mrow> <mo>‖</mo> <mrow> <msub> <mi>d</mi> <mrow> <mn>2</mn> </mrow> </msub> </mrow> <mo>‖</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \gauche\|\mathbf {d_{2}} \droit\|}</annotation> </semantics> </math><img src=$ ${\displaystyle \left\|\mathbf {q} ight\| <semantics> <mrow> <mstyle> <mrow> <mo>‖</mo> <mrow> <mi>q</mi> </mrow> <mo>‖</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \gauche\|\mathbf {q} \droite\|}</annotation> </semantics> </math><img src=$

{\displaystyle \left\|\mathbf {q} ight\|={\sqrt {\sum _{i=1}^{n}q_{i}^{2 <semantics> <mrow> <mstyle> <mrow> <mo>‖</mo> <mrow> <mi>q</mi> </mrow> <mo>‖</mo> </mrow> <mo>=</mo> <mrow> <msqrt> <munderover> <mo>∑</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <msubsup> <mi>q</mi> <mrow> <mi>je</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msubsup> </msqrt> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \gauche\|\mathbf {q} \droite\|={\sqrt {\sum _{i=1}^{n}q_{i}^{2}}}}</annotation> </semantics> </math></span><img src=

En utilisant le cosinus, la similarité entre le document d _j et la requête q peut être calculée comme :

{\displaystyle \mathrm {cos} (d_{j},q)={\frac {\mathbf {d_{j}} \cdot \mathbf {q} }{\left\|\mathbf {d_{j}} ight\|\left\|\mathbf {q} ight\|}}={\frac {\sum _{i=1}^{N}d_{i,j}q_{i}}{{\sqrt {\sum _{i=1}^{N}d_{i,j}^{2}}}{\sqrt {\sum _{i=1}^{N}q_{i}^{2 <semantics> <mrow> <mstyle> <mrow> <mi>c</mi> <mi>ou</mi> <mi>m</mi> </mrow> <mo>(</mo> <msub> <mi>d</mi> <mrow> <mi>j</mi> </mrow> </msub> <mo>,</mo> <mi>q</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mrow> <msub> <mi>d</mi> <mrow> <mi>j</mi> </mrow> </msub> </mrow> <mo>⋅</mo> <mrow> <mi>q</mi> </mrow> </mrow> <mrow> <mrow> <mo>‖</mo> <mrow> <msub> <mi>d</mi> <mrow> <mi>j</mi> </mrow> </msub> </mrow> <mo>‖</mo> </mrow> <mrow> <mo>‖</mo> <mrow> <mi>q</mi> </mrow> <mo>‖</mo> </mrow> </mrow> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mrow> <munderover> <mo>∑</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>N</mi> </mrow> </munderover> <msub> <mi>d</mi> <mrow> <mi>je</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> <msub> <mi>q</mi> <mrow> <mi>je</mi> </mrow> </msub> </mrow> <mrow> <mrow> <msqrt> <munderover> <mo>∑</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>N</mi> </mrow> </munderover> <msubsup> <mi>d</mi> <mrow> <mi>je</mi> <mo>,</mo> <mi>j</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msubsup> </msqrt> </mrow> <mrow> <msqrt> <munderover> <mo>∑</mo> <mrow> <mi>je</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>N</mi> </mrow> </munderover> <msubsup> <mi>q</mi> <mrow> <mi>je</mi> </mrow> <mrow> <mn>2</mn> </mrow> </msubsup> </msqrt> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {cos} (d_{j},q)={\frac {\mathbf {d_{j}} \cdot \mathbf {q} }{\left\|\mathbf {d_{j}} ight\|\left\|\mathbf {q} ight\|}}={\frac {\sum _{i=1}^{N}d_{i,j}q_{i}}{{\sqrt {\sum _{i=1}^{N}d_{i,j}^{2}}} {\ sqrt {\ sum _ {i = 1} ^ {N} q_ {i} ^ {2}}}}}}</annotation> </semantics> </math></span><img src=

Comme tous les vecteurs pris en compte par ce modèle sont non négatifs élément par élément, une valeur de cosinus de zéro signifie que le vecteur de requête et le vecteur de document sont orthogonaux et n'ont aucune correspondance (c'est-à-dire que le terme de requête n'existe pas dans le document considéré). Voir la similarité cosinus pour plus d'informations.

Pondérations inverses de fréquence des documents par fréquence des termes

Dans le modèle d'espace vectoriel classique proposé par Salton , Wong et Yang , les pondérations spécifiques aux termes dans les vecteurs de documents sont des produits de paramètres locaux et globaux. Le modèle est connu sous le nom de modèle de fréquence de terme-fréquence de document inverse . Le vecteur de pondération pour le document d est , où ${\displaystyle \mathbf {v} _{d}=[w_{1,d},w_{2,d},\ldots ,w_{N,d}]^{T <semantics> <mrow> <mstyle> <msub> <mrow> <mi>v</mi> </mrow> <mrow> <mi>d</mi> </mrow> </msub> <mo>=</mo> <mo>[</mo> <msub> <mi>m</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>d</mi> </mrow> </msub> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mn>2</mn> <mo>,</mo> <mi>d</mi> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>m</mi> <mrow> <mi>N</mi> <mo>,</mo> <mi>d</mi> </mrow> </msub> <msup> <mo>]</mo> <mrow> <mi>T</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle \mathbf {v} _{d}=[w_{1,d},w_{2,d},\ldots ,w_{N,d}]^{T}}</annotation> </semantics> </math><img src=$

{\displaystyle w_{t,d}=\mathrm {tf} _{t,d}\cdot \log {\frac {|D|}{|\{d'\in D\,|\,t\in d'\}| <semantics> <mrow> <mstyle> <msub> <mi>m</mi> <mrow> <mi>t</mi> <mo>,</mo> <mi>d</mi> </mrow> </msub> <mo>=</mo> <msub> <mrow> <mi>t</mi> <mi>f</mi> </mrow> <mrow> <mi>t</mi> <mo>,</mo> <mi>d</mi> </mrow> </msub> <mo>⋅</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mrow> <mfrac> <mrow> <mrow> <mo>|</mo> </mrow> <mi>D</mi> <mrow> <mo>|</mo> </mrow> </mrow> <mrow> <mrow> <mo>|</mo> </mrow> <mo>{</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>∈</mo> <mi>D</mi> <mspace></mspace> <mrow> <mo>|</mo> </mrow> <mspace></mspace> <mi>t</mi> <mo>∈</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>}</mo> <mrow> <mo>|</mo> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle w_{t,d}=\mathrm {tf} _{t,d}\cdot \log {\frac {|D|}{|\{d'\in D\,|\,t\in d'\}|}}}</annotation> </semantics> </math></span><img src=

${\displaystyle \mathrm {tf} _{t,d <semantics> <mrow> <mstyle> <msub> <mrow> <mi>t</mi> <mi>f</mi> </mrow> <mrow> <mi>t</mi> <mo>,</mo> <mi>d</mi> </mrow> </msub> </mstyle> </mrow> <annotation>{\displaystyle \mathrm {tf} _{t,d}}</annotation> </semantics> </math><img src=$ t dans le document d (un paramètre local)
${\displaystyle \log {\frac {|D|}{|\{d'\in D\,|\,t\in d'\}| <semantics> <mrow> <mstyle> <mi>enregistrer</mi> <mo>⁡</mo> <mrow> <mfrac> <mrow> <mrow> <mo>|</mo> </mrow> <mi>D</mi> <mrow> <mo>|</mo> </mrow> </mrow> <mrow> <mrow> <mo>|</mo> </mrow> <mo>{</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>∈</mo> <mi>D</mi> <mspace></mspace> <mrow> <mo>|</mo> </mrow> <mspace></mspace> <mi>t</mi> <mo>∈</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>}</mo> <mrow> <mo>|</mo> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \log {\frac {|D|}{|\{d'\dans D\,|\,t\dans d'\}|}}}</annotation> </semantics> </math><img src=$ t . ${\displaystyle |D| <semantics> <mrow> <mstyle> <mrow> <mo>|</mo> </mrow> <mi>D</mi> <mrow> <mo>|</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle |D|}</annotation> </semantics> </math><img src=$ ${\displaystyle |\{d'\in D\,|\,t\in d'\}| <semantics> <mrow> <mstyle> <mrow> <mo>|</mo> </mrow> <mo>{</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>∈</mo> <mi>D</mi> <mspace></mspace> <mrow> <mo>|</mo> </mrow> <mspace></mspace> <mi>t</mi> <mo>∈</mo> <msup> <mi>d</mi> <mo>′</mo> </msup> <mo>}</mo> <mrow> <mo>|</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle |\{d'\dans D\,|\,t\dans d'\}|}</annotation> </semantics> </math><img src=$

Avantages

Le modèle d'espace vectoriel présente les avantages suivants par rapport au modèle booléen standard :

Permet de classer les documents en fonction de leur éventuelle pertinence
Permet de récupérer des éléments avec un chevauchement de terme partiel

La plupart de ces avantages sont une conséquence de la différence de densité de la représentation de la collection de documents entre les approches booléennes et inverses de fréquence des termes. Lorsque l'on utilise des pondérations booléennes, tout document se trouve dans un sommet d'un hypercube à n dimensions . Par conséquent, les représentations de documents possibles sont et la distance euclidienne maximale entre les paires est . Au fur et à mesure que des documents sont ajoutés à la collection de documents, la région définie par les sommets de l'hypercube devient plus peuplée et donc plus dense. Contrairement aux approches booléennes, lorsqu'un document est ajouté en utilisant des pondérations inverses de fréquence des termes et de fréquence des documents, les fréquences inverses des termes du nouveau document diminuent tandis que celles des termes restants augmentent. En moyenne, au fur et à mesure que des documents sont ajoutés, la région où se trouvent les documents s'agrandit, régulant la densité de la représentation de la collection entière. Ce comportement modélise la motivation originale de Salton et de ses collègues selon laquelle une collection de documents représentée dans une région à faible densité pourrait donner de meilleurs résultats de recherche. ${\displaystyle 2^{n <semantics> <mrow> <mstyle> <msup> <mn>2</mn> <mrow> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle 2^{n}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\sqrt {n <semantics> <mrow> <mstyle> <mrow> <msqrt> <mi>n</mi> </msqrt> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\sqrt {n}}}</annotation> </semantics> </math><img src=$

Limites

Le modèle d'espace vectoriel présente les limitations suivantes :

Les termes de requête sont supposés être indépendants, de sorte que les expressions peuvent ne pas être bien représentées dans le classement
Sensibilité sémantique ; les documents ayant un contexte similaire mais un vocabulaire de termes différent ne seront pas associés

Beaucoup de ces difficultés peuvent cependant être surmontées par l'intégration de divers outils, notamment des techniques mathématiques telles que la décomposition en valeurs singulières et des bases de données lexicales telles que WordNet .

Modèles basés sur et étendant le modèle d'espace vectoriel

Les modèles basés sur et étendant le modèle d'espace vectoriel incluent :

Logiciel qui implémente le modèle d'espace vectoriel

Les progiciels suivants peuvent intéresser ceux qui souhaitent expérimenter des modèles vectoriels et mettre en œuvre des services de recherche basés sur eux.

Logiciels open source gratuits

Apache Lucene . Apache Lucene est une bibliothèque de moteur de recherche de texte open source, hautes performances et riche en fonctionnalités, entièrement écrite en Java.
OpenSearch (logiciel) et Solr : les deux moteurs de recherche les plus connus (il en existe de nombreux plus petits) basés sur Lucene.
Gensim est un framework Python+ NumPy pour la modélisation de l'espace vectoriel. Il contient des algorithmes incrémentaux (efficaces en termes de mémoire) pour la fréquence inverse des documents , l'indexation sémantique latente , les projections aléatoires et l'allocation Dirichlet latente .
Weka . Weka est un package d'exploration de données populaire pour Java incluant les modèles WordVectors et Bag Of Words .
Word2vec . Word2vec utilise des espaces vectoriels pour les plongements de mots.

Lectures complémentaires

G. Salton (1962), « Quelques expériences dans la génération d'associations de mots et de documents », Actes de la conférence AFIPS '62 (automne) , pages 234–250. (Premier article de Salton utilisant la formalisation de la matrice terme-document)
G. Salton , A. Wong et CS Yang (1975), « Un modèle d'espace vectoriel pour l'indexation automatique » Communications of the ACM , vol. 18, n° 11, pages 613–620. (Article dans lequel un modèle d'espace vectoriel a été présenté)
David Dubin (2004), The Most Influential Paper Gerard Salton Never Wrote (Explique l'histoire du modèle d'espace vectoriel et la non-existence d'une publication fréquemment citée)
Description du modèle d'espace vectoriel
Description du modèle d'espace vectoriel classique par le Dr E. Garcia
Relation entre la recherche dans l'espace vectoriel et la recherche du « k-plus proche voisin »