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^[1]​ 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,^[2]​ 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 ${\displaystyle U}$ es el conjunto ${\displaystyle K}$ de todos los términos indexados.

Todos los documentos ${\displaystyle d_{j}}$ de la colección son representados como el conjunto de términos indexados ${\displaystyle k_{i}}$ que pertenecen a él. El conjunto ${\displaystyle k}$ = {${\displaystyle 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 ${\displaystyle k_{i}}$, se le asocia una variable binaria aleatoria, también referenciada como ${\displaystyle k_{i}}$. La variable aleatoria ${\displaystyle k_{i}}$ tiene valor 1 si el índice ${\displaystyle k_{i}}$ pertenece al concepto/conjunto representado por 𝑘⃗.

Un documento ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle d_{j}}$. Esta variable toma valor 1 cuando ${\displaystyle 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 ${\displaystyle d_{j}}$ relativa a la consulta 𝑞 es interpretado como una relación de coincidencia y refleja el grado de cubrimiento del concepto 𝑞 al concepto ${\displaystyle d_{j}}$. En redes de creencia este valor está dado por la probabilidad condicional de que ocurra ${\displaystyle d_{j}}$ dado que ocurrió q:

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

Aplicando el teorema de Bayes:

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

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

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

Aplicando la fórmula (1):

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

Luego, dado la topología de la red, ${\displaystyle 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:

${\displaystyle 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}}}$

${\displaystyle 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.

Referencias

Esta página se editó por última vez el 18 jul 2019 a las 15:20.