Modelo vectorial generalizado

Introducción

La modelación del proceso de recuperación de información de manera vectorial surge por primera vez en 1968, por Gerard Salton y Lesk.^[1]

Este modelo tiene su base en el álgebra lineal multidimensional y ofrece características destacables en cuanto a diseño, implementación y resultados. Los términos indexados como los documentos se modelan como vectores, los cuales son llamados vectores-términos y vectores-documentos, respectivamente. El conjunto de vectores términos representa la base de dicho espacio vectorial. El peso de un término indexado en un documento representa la componente del documento asociada al correspondiente vector término de la base.

En el modelo adoptado por Salton asume que los vectores términos son ortonormales, pero no se especifica nada acerca de la correlación de estos.

Es un modelo que deriva del clásico propuesto por Salton, y en realidad podemos contemplarlo como una extensión del mismo, ya que los principios en que está basado son muy parecidos, se puede decir que el modelo vectorial es un caso particular del Modelo Vectorial Generalizado, el cual permite, mediante transformaciones del vectorial, tomar en cuenta las relaciones entre los términos, y cuyo propósito principal es el de integrarle naturalmente al modelo, el cómputo de la correlación entre términos. También es relativamente fácil de implementar sobre sistemas que tienen implementado el modelo vectorial.^[2]

Descripción del modelo vectorial

Ideas Básicas

La idea fundamental que plantea el modelo vectorial es que la colección de documentos y la consulta se representan como vectores multidimensionales. El espacio vectorial sobre el que se definen estos vectores está generado por el conjunto de vectores términos { ${\overrightarrow {t_{i}}}$ } ( = 1,.., n). De esta idea podemos definir formalmente las siguientes expresiones.

Documentos

${\overrightarrow {d_{j}}}=\textstyle \sum _{k=1}^{n}w_{i,j}{\overrightarrow {t_{i}}}\displaystyle$ (1)

Vectores de Peso (términos indexados i en el documento j)

$w_{i,j}$ - representa el peso asociado al término indexado i en el documento j

Consultas

${\overrightarrow {q}}=\textstyle \sum _{k=1}^{n}w_{i,q}{\overrightarrow {t_{i}}}\displaystyle$ (2)

Vectores de Peso (términos indexados i en la consulta j)

$w_{i,q}$ - representa el peso asociado al término indexado i en la consulta q

Ranking

$sim({\overrightarrow {d_{k}}},{\overrightarrow {q}})=cos({\overrightarrow {d_{k}}},{\overrightarrow {q}})={{\overrightarrow {d_{k}}}*{\overrightarrow {q}} \over \|{\overrightarrow {d_{k}}}\|\|{\overrightarrow {q}}\|}$ (3)

Determina cuan relevante es un documento a una consulta q se determina la magnitud del coseno del ángulo entre ellos.

Al plantear los vectores documentos en forma matricial tenemos:

$Wt=D$ (4)

Donde $D={\bigl (}{\overrightarrow {d_{1}}},...,{\overrightarrow {d_{m}}})^{T}$ y $t={\bigl (}{\overrightarrow {t_{1}}},...,{\overrightarrow {t_{n}}})^{T}$

$W={\begin{vmatrix}w_{11}&...&w_{1n}\\.&.&.\\.&.&.\\.&.&.\\w_{m1}&...&w_{mn}\end{vmatrix}}$

Si planteamos de igual manera la función de similitud en forma matricial nos queda:

$WG{\overrightarrow {q}}=S$ (5)

Donde:

$S={\bigl (}sim{\bigl (}{\overrightarrow {d_{1}}},{\overrightarrow {q}}{\bigr )}$

${\overrightarrow {q}}={\bigl (}w_{q1},...,w_{qn})^{T}$

$G={\begin{vmatrix}{\overrightarrow {t_{1}}}*{\overrightarrow {t_{2}}}&...&{\overrightarrow {t_{1}}}*{\overrightarrow {t_{n}}}\\.&.&.\\.&.&.\\.&.&.\\{\overrightarrow {t_{n}}}*{\overrightarrow {t_{1}}}&...&{\overrightarrow {tn}}*{\overrightarrow {tn}}\end{vmatrix}}$

Esta es una generalización del MRI Vectorial Clásico, pues este se puede obtener como caso particular haciendo G= I (Matriz Identidad), de lo cual podemos decir que en este caso t es ortonormal.

Modelo Vectorial Generalizado

El MRI Vectorial Generalizado tiene sus principios en el Álgebra Booleana y la integración teórica de esta en el modelo vectorial.

Sea $B_{2^{n}}$ el álgebra booleana generada por n literales $t_{1},...,t_{n}$ .

Un minterm sobre $B_{2^{n}}$ es una conjunción donde cada literal o su negación aparece exactamente una vez.

Si tenemos n-literales se pueden conformar $2^{n}$ minterm.

Si denotamos como { $m_{s}2^{n}$ } al conjunto de minterms sobre $B_{2^{n}}$ , implica que a cada minterm $m_{k}$ se le puede asociar una etiqueta $k=(\delta _{1}^{k},...,\delta _{n}^{k})$ donde $\delta _{i}^{k}\in \{0,1\}$ es decir:

$m_{k}=t_{1}^{\delta _{1}^{k}}\land ...\land t_{n}^{\delta _{n}^{k}}$ , donde $t_{i}^{\delta _{i}^{k}}={\begin{cases}t_{i},&{\text{si }}\delta _{i}^{k}{\text{ =1}}\\\urcorner t_{i},&{\text{si }}\delta _{i}^{k}{\text{ =0}}\end{cases}}$

Una expresión booleana se puede transformar de manera única en una disyunción de minterms. En especial un literal $t_{i}$ de $B_{2^{n}}$ se puede expresar de manera única como:

$t_{i}=m_{i1}\lor ...\lor m_{ir},$ para todo $t_{i}=m_{ij}\lor t_{i}$

Se puede generalizar el álgebra booleana de $B_{2^{n}}$ y representar el conjunto de minterms { $m_{s}2^{n}$ } como un conjunto de vectores ortonormales sobre $\Re ^{2^{n}}$ :

${\overrightarrow {m_{1}}}=(1,...,0)...{\overrightarrow {m_{2^{n}}}}=(0,...,1)$

Correlación y Representación de Términos

La correlación de dos términos indexados depende de la cantidad de documentos en los que ellos aparecen juntos. El MRI Vectorial Generalizado se basa en esta idea para determinar el grado de correlación de dos términos. Pretendemos mostrar como el producto escalar de los vectores de términos determina el grado de correlación entre estos, demostrando así que $WG{\overrightarrow {q}}=S$ es la representación correcta del modelo vectorial general, lo que refleja implícitamente la relevancia a la dependencia entre términos.

Supongamos que la colección de documentos está representada por un conjunto de vectores binarios.

Entonces el k-ésimo documento de la colección se representa como:^[3]

${\overrightarrow {d_{k}}}=({\boldsymbol {\alpha }}_{k1},...,{\boldsymbol {\alpha }}_{kn})$ , donde:

${\boldsymbol {\alpha _{k1}}}={\begin{cases}1,&{\text{si el k-ésimo documento contiene al término indexado i}}\\0,&{\text{si el k-ésimo documento no contiene al término indexado i }}\end{cases}}$

Para obtener la representación explícita del véctor término ${\overrightarrow {t_{l}}}$ sumemos los vectores que representan a los minterm, multipliquémoslos por su factor de correlación asociado al término indexado i y normalicemos el vector.

Por lo que podemos decir que:

${\overrightarrow {t_{l}}}=\textstyle \sum _{k=1}^{r}\displaystyle {c_{k}(t_{i}){\overrightarrow {m_{k}}} \over {\sqrt {\textstyle \sum _{j=1}^{r}\displaystyle c_{j}(t_{i})^{2}}}}$

donde,

$c_{k}(t_{i})=\textstyle \sum _{a\in I(t_{i},k)}\alpha _{ai}\displaystyle$

$I(t_{i},k)=\{a|d_{a}\in f(m_{k})\subseteq f(t_{i})\}$

El producto escalar entre dos vectores términos proporciona una medida “normalizada" de la cantidad de documentos en los que ellos aparecen. Representar los documentos como vectores de valores reales lo único que modifica es el factor de correlación asociado a un término indexado, dado por $c_{k}(t_{i})=\textstyle \sum _{a\in I(t_{i},k)}\alpha _{ai}\displaystyle$ .Tomando como base la definición la definición general de modelo vectorial tenemos que:

$c_{k}(t_{i})=\textstyle \sum _{a\in I(t_{i},k)}\alpha _{ai}\displaystyle$

Obteniéndose, de manera general, como grado de correlación entre dos términos indexados:

${\overrightarrow {t_{l}}}*{\overrightarrow {t_{j}}}=\textstyle \sum _{\forall k\in H_{i,j}}\displaystyle {c_{k}(t_{i}){c_{k}(t_{j})} \over {\sqrt {\textstyle \sum _{p=1}^{r_{i}}\displaystyle c_{p}(t_{i})^{2}}}{\sqrt {\textstyle \sum _{p=1}^{r_{j}}\displaystyle c_{p}(t_{j})^{2}}}}$

Los cuales quedan almacenados en la matriz G y son utilizados en el cómputo del ranking como se planificó inicialmente.

Definición Formal del Modelo Vectorial Generalizado

Se define como el cuádruplo: MVG = <D,Q,F,R>

Documentos (D): Vectores de peso dados por (1)

Consultas (Q): Vectores de peso dados por (2)

Framework (F): Álgebra Booleana y Lineal. Espacio vectorial n-dimensional con vectores de dimensión 2𝑛

Ranking (R): Ecuación (5)

Ventajas y Desventajas

Ventajas:

El aporte fundamental de este modelo es la definición formal y elegante de un framework que permita la representación de dependencia entre términos indexados y aproveche las bondades del modelo vectorial.
Establece una función de correlación entre los términos.
Posee todas las ventajas del MRI Vectorial Clásico.
Ofrece nuevas ideas desde un punto de vista teórico y enriquece el MRI Vectorial Clásico.

Desventajas:

No está claro que en situaciones prácticas sea superior al modelo clásico.
El costo computacional del cómputo del ranking puede ser enorme en colecciones de documentos suficientemente grandes.
Su implementación tiene mayor complejidad que los modelos clásicos.
Al construir los vectores términos a partir de los documentos, al modificar la colección de documentos habrá que recalcular nuevamente todos los valores almacenados en el sistema, tanto de los vectores términos como de los vectores documentos.

Referencias

↑ Generalized Vector Space Model In Information Retrieval, S.K.M. Wong, Wojciech Ziarko and Patrick C.N. Wong, Department of Computer Science, University of Regina, Regina, Sask., Canada S4S OA2.
↑ Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier: Modern Information Retrieval. New York: ACM; Harlow, Essex: Addison-Wesley Longman, 1999.
↑ A Generalized Vector Space Model for Text Retrieval Based on Semantic Relatedness, George Tsatsaronis and Vicky Panagiotopoulou, Department of Informatics, Athens University of Economics and Business, 76, Patision Str., Athens, Greece

Datos: Q5532523

[1] Generalized Vector Space Model In Information Retrieval, S.K.M. Wong, Wojciech Ziarko and Patrick C.N. Wong, Department of Computer Science, University of Regina, Regina, Sask., Canada S4S OA2.

[2] Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier: Modern Information Retrieval. New York: ACM; Harlow, Essex: Addison-Wesley Longman, 1999.

[3] A Generalized Vector Space Model for Text Retrieval Based on Semantic Relatedness, George Tsatsaronis and Vicky Panagiotopoulou, Department of Informatics, Athens University of Economics and Business, 76, Patision Str., Athens, Greece

[1]

[2]

[3]