Red de creencia

Las redes de creencia constituyen una extensión del modelo probabilístico clásico utilizado en problemas de recuperación de información. Se derivan de las redes bayesianas de creencia​ y son una generalización del modelo de redes de inferencia.

En recuperación de información, las redes bayesianas de creencia son útiles porque proveen una forma clara de combinar distintas fuentes de evidencia que respalden el ranking dado a un documento. Esta combinación de fuentes distintas de evidencia puede ser utilizada para mejorar la eficiencia del proceso de recuperación de información.

El modelo de redes de creencia,​ introducido en 1996 por Ribeiro-Neto y Muntz, está basado en una interpretación epistemológica de las probabilidades. Parte del modelo de redes de inferencia, pero adopta un espacio de muestras claramente definido. Como resultado, se obtiene una topología distinta, que provee una separación entre el documento y la consulta dentro de la red. Esta constituye la mayor diferencia entre ambos modelos.

Espacio de probabilidades

El espacio de probabilidades adoptado fue introducido por primera vez por Wong y Yao. Todos los documentos en la colección son incorporados como "términos indexados" y el universo de discurso $U$ es el conjunto $K$ de todos los términos indexados.

Todos los documentos $d_{j}$ de la colección son representados como el conjunto de términos indexados $k_{i}$ que pertenecen a él. El conjunto $k$ = {$k_{1},k_{2},...,k_{t}$} de todos los términos indexados define el espacio muestral para el modelo de redes de creencia. A cada subconjunto 𝑢 del espacio 𝐾 se asocia un vector 𝑘⃗.

De cada término indexado se dice que es un concepto elemental y 𝐾 el espacio de conceptos. De cada u subconjunto de 𝐾 se dice que es un concepto, y puede representar tanto un documento de la colección como una consulta del usuario.

El conjunto de relaciones de la red de creencia es especificado a partir de variables aleatorias como se muestra a continuación.

A cada término indexado $k_{i}$, se le asocia una variable binaria aleatoria, también referenciada como $k_{i}$. La variable aleatoria $k_{i}$ tiene valor 1 si el índice $k_{i}$ pertenece al concepto/conjunto representado por 𝑘⃗.

Un documento $d_{j}$ en la colección es representado como un concepto compuesto por los términos usados para indexarlo. Análogamente, una consulta 𝑞 es representada como un concepto compuesto por los términos usados para indexarla.

La distribución de probabilidad $P$ se define sobre 𝐾 dado un concepto 𝑐 genérico que representa a una consulta, se define como:

𝑃(𝑐) = ∑𝑢 𝑃(𝑐|𝑢) ∗ 𝑃(𝑢) (1)

𝑃(𝑢) = (½)^t (2)

La ecuación (1) define 𝑃(𝑐) como el grado de cobertura que ofrece 𝑐 del espacio 𝐾. Como al principio del sistema no hay conocimiento de la probabilidad con la que un concepto ocurre en el espacio 𝐾, podemos asumir que cada concepto 𝑢 es igualmente probable de modo que se cumple (2).

Modelación del sistema

En redes de creencia, una consulta 𝑞 es representada como un nodo de la red al cual se le asocia una variable binaria aleatoria a la que haremos también referencia como 𝑞. Esta variable toma valor 1 cuando 𝑞 cubre completamente el espacio de conceptos 𝐾.

Análogamente, un documento $d_{j}$ es modelado como un nodo de la red al cual se le asocia una variable binaria aleatoria a la que haremos también referencia como $d_{j}$. Esta variable toma valor 1 cuando $d_{j}$ cubre completamente el espacio de conceptos 𝐾.

La modelación de igual forma de los documentos y las consultas define la topología de la red de creencia.

En un modelo de red de creencia, el nodo consulta 𝑞 es apuntado por aristas a partir de los nodos que representan los términos indexados que componen el concepto de 𝑞. Los documentos, de igual manera que las consultas, son apuntados por los nodos de términos indexados que componen dichos documentos.

El ranking de un documento $d_{j}$ relativa a la consulta 𝑞 es interpretado como una relación de coincidencia y refleja el grado de cubrimiento del concepto 𝑞 al concepto $d_{j}$. En redes de creencia este valor está dado por la probabilidad condicional de que ocurra $d_{j}$ dado que ocurrió q:

$P(d_{j}|q)$ (3)

Aplicando el teorema de Bayes:

$P(d_{j}|q)=P(d_{j}\land q)/P(q)$ (4)

Como $P(q)$ es igual para todos los documentos se puede afirmar que son directamente proporcionales, es decir, se cumple que:

$P(d_{j}|q)~P(d_{j}\land q)$ (5)

Aplicando la fórmula (1):

𝑃(𝑑𝑗|𝑞) ~ ∑∀𝑢 𝑃(𝑑𝑗 ⋀ 𝑞|𝑢) ∗ 𝑃(𝑢) (6)

Luego, dado la topología de la red, $d_{j}$ y q son independientes, por tanto:

𝑃(𝑑𝑗|𝑞) ~ ∑∀𝑢 𝑃(𝑑𝑗|𝑢) ∗ 𝑃( 𝑞|𝑢) ∗ 𝑃(𝑢) (7)

Esta última puede ser reescrita como:

𝑃(𝑑𝑗|𝑞) ~ ∑∀𝑘 𝑃(𝑑𝑗 | 𝑘⃗ ) * 𝑃( 𝑞| 𝑘⃗) ∗ 𝑃(𝑘⃗ ) (8)

Como 𝑃(𝑘⃗) = (1⁄2)^t solo falta especificar como se definen las probabilidades condicionales 𝑃(𝑑𝑗 | 𝑘⃗ ) y 𝑃( 𝑞| 𝑘⃗ ), existen distintas especificaciones que permiten diferentes estrategias de ranking. Para el modelo vectorial estas probabilidades se calculan de la siguiente forma:

$P(d_{j},{\overrightarrow {k}})={\begin{cases}{\frac {w_{i,j}}{\sqrt {\sum _{i=1}^{t}w_{i,j}^{2}}}},&{\mbox{si }}{\overrightarrow {k}}={\overrightarrow {k_{i}}}\land g_{i}(q)=1;\\0,&{\mbox{en otro caso }};\end{cases}}$

$P(q,{\overrightarrow {k}})={\begin{cases}{\frac {w_{i,q}}{\sqrt {\sum _{i=1}^{t}w_{i,q}^{2}}}},&{\mbox{si }}{\overrightarrow {k}}={\overrightarrow {k_{i}}}\land g_{i}(q)=1;\\0,&{\mbox{en otro caso }};\end{cases}}$

Ventajas y desventajas del modelo de Redes de Creencia

Ventajas:

• Permite realizar ranking a los documentos.
• Puede ser aplicado para representar el modelo booleano y el vectorial.
• Permite correspondencia parcial.
• Debido a la separación entre el documento y la consulta, es capaz de reproducir cualquier estrategia de ranking generada por el modelo de recuperación de información basado en Redes de Inferencia o de otros modelos de recuperación de información.
• Permite realizar consultas a consultas realizadas con anterioridad, elevando la calidad del conjunto de documentos recuperados.

Desventajas:

• Asume independencia entre los términos.

Bibliografía

• Information Retrieval Data Structures & Algorithms; William B. Frakes, Ricardo Baeza-Yates.
• Modern Information Retrieval I; Ricardo Baeza-Yates, Berthier Ribeiro-Neto.
• An Introduction to Information Retrieval; Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze.