Modelos Alternativos (2) M. Andrea Rodríguez Tastets DIIC - Universidad de Concepción andrea.

Modelos Alternativos (2)M. Andrea Rodríguez Tastets

DIIC - Universidad de Concepciónhttp://www.inf.udec.cl/~andrea

Modelos

Non-Overlapping ListsProximal Nodes

Structured Models

Retrieval: Adhoc Filtering

Browsing

U s e r

T a s k

Classic Models

boolean vector probabilistic

Set Theoretic

Fuzzy Extended Boolean

Probabilistic

Inference Network Belief Network

Algebraic

Generalized Vector Lat. Semantic Index Neural Networks

Browsing

Flat Structure Guided Hypertext

Modelo Vector Generalizado

Modelos clásicos asumen la independencia de los términos índices.

Para el modelo vector: • El conjunto de vectores de términos {k1, k2, ..., kt} are

linealmente independientes, los cuales forman la base para el subespacio de interes.

Esto se interpreta también como una ortogonalidad:• i,j ki kj = 0

En 1985, Wong, Ziarko, y Wong propusieron una interpretación en la cual los vectores de términos son linealmnete independientes, pero no ortogonales.

Idea Base:• En el modelo vector generalizado, dos vectores de

términos índices pueden ser no ortogonales y son representados en base a componentes más pequeños (minterms).

• Tal como antes, sea, wij el peso asociado con [ki,dj] {k1, k2, ..., kt} sea el conjunto de todos los términos

• Si estos pesos son todos binarios, todos los patrones de ocurrencia de los términos puden ser representados por:: m1 = (0,0, ..., 0) m5 = (0,0,1, ..., 0) m2 = (1,0, ..., 0) …. m3 = (0,1, ..., 0) m4 = (1,1, ..., 0) m2t =(1,1,1,

…..1) Aquí, m2 indica documentos en los cuales sólo el

término k1 occurre.

Idea Base:

• La base para el modelo vector generalizado está formado por un conjunto de vectores definidos sobre el conjunto de minterms (que son ortogonales), como sigue:

0 1 2 ... 2t

m1 = (1, 0, 0, ..., 0, 0) m2 = (0, 1, 0, ..., 0, 0) m3 = (0, 0, 1, ..., 0, 0)

• m2t = (0, 0, 0, ..., 0, 1)

• Note que,• i,j mi mj = 0 e.i., ortogonales

Idea Base:• Vectores minterm son ortogonales, pero no necesariamente

independientes:• El minterm m4 está dado por:

m4 = (1, 1, 0, ..., 0, 0)• Este minterm indica la ocurrencia de los términos k1 y

k2 en el mismo documento. Si tal documento existe en una colección, se dice que el mintem m4 está activo y que una dependencia entre estos términos está inducida.

• Se asume que la co-ocurrencia de términos en documentos induce dependencias entre ellos.

• El vector asociado con el término ki es computado:

El peso c con el par [ki,mr] suma los pesos de los términos ki en todos lo documentos en los cuales tiene un patrón de ocurrencia dado por mr.

Note que para una colección de tamaño N, sólo N minterms afectan el ranking.

Formando el Vector de Términos

t

rki =

ci,rrmr∀r,gi(mr )=1

∑ci,r2

∀r,gi(mr )=1∑

ci,r = wi, jdj |gl (

rdj )=gl (mr )∀l∑

• Un grado de correlación entre términos entre ki y kj puede ser determinado por:

• Este grado de correlación suma (en una forma ponderada) las dependencias entre ki y kj inducido por los documentos en la colección (representado por el mr minterms).

• Luego se aplica el modelo vectorial:

Dependencia entre Términos Índices

Ki ⋅K j = ci,r ×cj ,r∀r,gr (mr )=1∧gj (mr )=1∑

drj = wi, j k

ri

∀i∑ ,q

r= wi,qk

ri

∀i∑

Ejemplo

d1

d2

d3d4 d5

d6d7

k1k2

k3

k1 k2 k3

d1 2 0 1

d2 1 0 0

d3 0 1 3

d4 2 0 0

d5 1 2 4

d6 1 2 2

d7 0 5 0

q 1 2 3

Cálculo de C i,r

k1 k2 k3

d1 2 0 1

d2 1 0 0

d3 0 1 3

d4 2 0 0

d5 1 2 4

d6 1 2 2

d7 0 5 0

q 1 2 3

k1 k2 k3

d1=m6

1 0 1

d2=m2

1 0 0

d3=m7

0 1 1

d4=m2

1 0 0

d5=m8

1 1 1

d6=m7

0 1 1

d7=m3

0 1 0

q=m8 1 1 1

c1,r c2,r c3,r

m1 0 0 0

m2 3 0 0

m3 0 5 0

m4 0 0 0

m5 0 0 0

m6 2 0 1

m7 0 3 5

m8 1 2 4

Cálculo de vector de términos índices

c1,r c2,r c3,r

m1 0 0 0

m2 3 0 0

m3 0 5 0

m4 0 0 0

m5 0 0 0

m6 2 0 1

m7 0 3 5

m8 1 2 4

k1 =1

32 + 22 +12(3m2 + 2m6 +m8)

k2 =1

52 + 32 + 22(5m3+ 3m7 + 2m8)

k3 =1

12 + 52 + 42(1m6 + 5m7 + 4m8)

Cálculo de vector de documentos

k1 k2 k3

d1 2 0 1

d2 1 0 0

d3 0 1 3

d4 2 0 0

d5 1 2 4

d6 1 2 2

d7 0 5 0

q 1 2 3

d1 =2k1 + k3d2 =k1d3 =k2 + 3k3d4 =2k1d5 =k1 + 2k2 + 4k3d6 =2k2 + 2k3d7 =5k1q=k1 + 2k2 + 3k3

Calculo de Ranking

d1 =2k1 + k3d2 =k1d3 =k2 + 3k3d4 =2k1d5 =k1 + 2k2 + 4k3d6 =2k2 + 2k3d7 =5k1q=k1 + 2k2 + 3k3

k1 =1

32 + 22 +12(3m2 + 2m6 +m8)

k2 =1

52 + 32 + 22(5m3+ 3m7 + 2m8)

k3 =1

12 + 52 + 42(1m6 + 5m7 + 4m8)

Conclusiones

El modelo considera correlación entre términos índices.

No es claro cuánto mejor es con respecto al modelo vector clásico.

Costo computacional mayor Ideas nuevas e interesantes

Latent Semantic Indexing IR clásica puede llevar a una recuperación deficiente por:

• Documentos no relacionados pueden ser incluidos en la respuesta.

• Documentos relevantes que no contienen al menos un térmico índice no son considerados.

• Razonamiento: recuperación basada en términos índices es vaga y afectada

por “ruido”. El usuario está más relacionado a conceptos e ideas que a términos

índices. Un documento que comparte conceptos con otro documento conocido

de ser relevante puede ser de ínteres también.

Latent Semantic Indexing

La clave es mapear documentos y consultas a un espacio de dimensión menor (e.i. un espacio compuesto de conceptos de mayor nivel con un conjunto menor de términos índices).

Recuperar en este espacio reducido de conceptos puede ser mejor para recuperar que un espacio de términos índices.


Definiciones• Sea t el número total de términos índices• Sea N el número de documentos• Sea (Mij) una matriz de documento-término con t

filas y N columnas• Cada elemento de esta matriz está asociada con

un peso wij asociado con el par [ki,dj]• El peso wij puede basarse en el esquema tf-idf


La matriz (Mij) puede ser descompuesta en 3 matrices (decomposición de valor singular) como sigue:

• (Mij) = (K) (S) (D)t

• (K) es la matriz de vectores propios derivada de (M)(M)t

• (D)t es la matriz de vectores propios derivada de (M)t(M)

• (S) es una matriz diagonal r x r de valores singulares donde r = min(t,N) que es el rango de (Mij)

Ejemplo Sea (Mij) la matriz dada por

• determinar las matrices (K), (S), y (D)t

k1 k2 k3 q*dj

d1 2 0 1 5

d2 1 0 0 1

d3 0 1 3 11

d4 2 0 0 2

d5 1 2 4 17

d6 1 2 2 5

d7 0 5 0 10

q 1 2 3

Latent Semantic Indexing En la matriz (S), seleccionar sólo los s valores singulares

mayores mantenga las correspondientes columnas en (K) y (D)t

La matriz resultante es llamada (M)s y está dada por

• (M)s = (K)s (S)s (D)t

• donde s, s < r, es la dimensionalidad del espacio de conceptos

El parámetro s debe ser• suficientemente grande para permitir la caracterización de

los datos • suficientemente pequeño para filtrar datos no relevantes.

s

Latent Ranking

La consulta puede ser modelada como un seudo-documento en la matriz original (M)

Asuma que la consulta es numerada como un documento 0 in la matriz

La matriz cuantifica la

relación entre cualquier par de documentos en el espacio reducido

La primera fila de la matriz da el ranking de todos los documentos con respecto a la consulta del usuario.

M stM s

Conclusiones

Latent semantic indexing otorga una conceptualización interesante de recuperación de información

Permite reducir la complejidad de la representación, el cual puede ser explorado,por ejemplo, con el propósito de interacción con el usurario.

Modelo de Redes Neuronales

IR clásica: • Términos son usados parta indexar documentos y

consultas• Recuperación está basada en el matching de términos

índices.

Motivación: • Redes neuronales son conocidas por ser buenas para

realizar matching.


Redes Neuronales:• El cerebro humano está compuesto de billones de

neuronas • Cada neurona puede ser vista como una unidad de

procesamiento• Un neurona es estimulada por una señal de entrada y

emite una señal de salida como reacción• Una cadena de reacción de propagación de señales es

llamada spread activation process • Como resultado de este proceso, el cerebro puede

controlar el cuerpo para lograr reacciones físicas.

Una red neuronal es una simplificación de la interacción de neuronas en el cerebro humano. • Nodos son unidades de procesamiento • Arcos son conexiones sinápticas • La fuerza de propagación es modelada como un

peso asignado a cada arco• El estado de un nodo es definido por su nivel de

activación • Dependiendo de su nivel de activación, un nodo

puede generar una señal de salida.


Redes Neuronales para IR Basado en el trabajo de Wilkinson & Hingston,

SIGIR’91Document Terms

Query Terms Documents

ka

kb

kc

ka

kb

kc

k1

kt

d1

dj

dj+1

dN

Redes de tres niveles Las señales se propagan a través de la red Primer nivel de propagación:

• Los términos de la consulta inician la señal • Estas señales se propoagan a través de la red hasta alcanzar

los nodos documentos Segundo nivel de propagación:

• Los nodos documentos pueden ellos por sí mismos generar nuevas señales las cuales afectan los términos de los documentos

• Los nodos de términos de documentos pueden responder con nuevas señales

Redes Neuronales para IR

Cuantificación de la Señal Normalizar la fuerza de la señal (MAX = 1) Términos de consulta emiten una señal igual a 1 Pesos asociados a cada arco desde un nodo término

de consulta ki a un nodo término documento ki:• WiqWiq = wiq

sqrt ( i wiq ) Pesos asociados a cada arco desde un nodo término

de un document ki a un nodo documento dj:• WijWij = wij

sqrt ( i wij )

2

2

Después del primer nivel de propación, el nivel de activación de un nodo documento dj está dado por:

i WiqWiq WijWij = i wiq wij sqrt ( i wiq ) * sqrt ( i wij )

el cual es exactamente el ranking del modelo vectorial Nuevas señales pueden ser intercambiadas entre nodos

términos de documento y nodos documento en un proceso análago a un ciclo de feedback

Un threshold mínimo debe ser asegurado para evitar generación de señales perturbadoras.

2 2

Cuantificación de la Señal

Conclusiones El modelo da una formulación

interesante al problema de IR El modelo no ha sido evaluado

extensiblementeNo es claro las mejoras que otorga

Modelo Alternativos Probabilísticos

Teoría de Probabilidad• Semánticamente clara• Computacionalmente enrredada

Por qué Redes Bayesianas? • Es un formalismo claro que combina evidencias • Comparticiona el mundo (dependencias)• Redes Bayesianas para IR

Redes de Inferencia (Turtle & Croft, 1991) Redes de Creencia (Ribeiro-Neto & Muntz, 1996)

Inferencia Bayesiana

Escuelas de pensamiento en probabilidad• Frecuencia: noción estadística

relacionada con las leyes de cambios

• Epistemología: interpreta la probabilidad como grado de creencia


Axiomas básicos:

0 < P(A) < 1 ;

P(sure)=1;

P(A V B)=P(A)+P(B) Si A y B son mutuamente exclusivos

Inferencias Bayesianas

Otras formulaciones• P(A)=P(A B)+P(A ¬B)• P(A)= i P(A Bi) , donde Bi,i es un conjunto

exhaustivo y mutuamente exclusivo• P(A) + P(¬A) = 1• P(A|K) creencia en A dado el conocimiento de

K• if P(A|B)=P(A), A y B son independientes• if P(A|B C)= P(A|C), A y B son

condicionalmente independientes, dado C• P(A B)=P(A|B)P(B)• P(A)= i P(A | Bi)P(Bi)


Regla de Bayes: El corazón de la técnica Bayesiana

P(H|e) = P(e|H)P(H)/ P(e)donde, H : una hipótesis y e es una evidencia

P(H) : Probabilidad anterior P(H|e) : Probabilidad posterior P(e|H) : Probabilidad de e si H es

verdadero P(e) : una constante normalizadora, entonces escribimos:

P(H|e) ~ P(e|H)P(H)

Redes Bayesianas

Definición:Son grafos dirigidos acíclicos en los cuales nodos representan variables aleatorias, los arcos representan relaciones de causalidad entre estas variables, y la fuerza de estas causalidades son expresadas por probabilidaddes condicionales.

Redes Bayesianas

yi : Nodos padres (en este caso, nodos de raíz)x : nodo hijoyi causa xY el conjunto de padres de xLa enfuencia de Y en x puede ser cuantificada por cualquier funciónF(x,Y) tal que x F(x,Y) = 1 0 < F(x,Y) < 1Por ejemplo, F(x,Y)=P(x|Y)

y1 y2 y3

x1

Redes Bayesianas

Dada la dependencia declarada en una red Bayesiana, la expresión para la probabilidad conjunto puede ser calculada como un producto de probabilidad condicional local, por ejemplo, P(x1, x2, x3, x4, x5)=

P(x1 ) P(x2| x1 ) P(x3| x1 ) P(x4| x2, x3 ) P(x5| x3 ).

P(x1 ) : probabilidad anterior del nodo raíz

x1

x2 x3

x4x5

Redes Bayesianas

En una red Bayesiana cada variable es condicionalmente dependiente de todos los no descendientes, sus padres Por ejemplo,

P(x4, x5| x2 , x3)= P(x4| x2 , x3) P( x5| x4)

x1

x2 x3

x4x5

Modelo de Redes de Inferencia

Vista Epistemológica del problema de IR Variables aleatorias asociadas con

documentos, términos índices y consultas Una variable aleatoria asociada con un

documento dj representa el evento de observar tal documento

Modelo de Redes de InferenciaNodos

documentos (dj)

términos índices (ki)

consultas (q, q1, y q2)necesidad de información del usuario (I)

Arcos desde dj, su nodo de término índice ki indica que la observación de dj aumenta la creencia en la variable ki

dj

k1 k2

q

q2

q1

I

ki kt

or

and

dj tiene términos k2, ki, y kt

q tiene términos k1, k2, y ki

q1 y q2 es una formulación Boolean

q1=((k1 k2) v ki);

I = (q v q1)


dj

k1 k2

q

q2

q1

I

ki kt

or

and

Definiciones:k1, dj,, son q variables aleatorias

k=(k1, k2, ...,kt) un vector t-dimensional

ki,i{0, 1}, entonces k tiene 2t posibles estados

dj,j{0, 1}; q{0, 1}

El ranking de un documento dj es calculado como P(q dj)

q y dj,son representación cortas para q=1 y dj =1

(dj representa un estado donde dj = 1 and lj dl =0, porque se observa un documento en cada momento)


P(q dj) = k P(q dj| k) P(k)

= k P(q dj k)

= k P(q | dj k) P(dj k)

= k P(q | k) P(k | dj ) P( dj )

P(¬(q dj)) = 1 - P(q dj)


Probabilidad anterior P(dj) refleja la probabilidad asociado a un evento de observación a un documento dj

• Uniforme para N documentos

P(dj) = 1/N

P(¬dj) = 1 - 1/N• Basada en la norma del vector dj

P(dj)= 1/|dj|

P(¬dj) = 1 - 1/|dj|


Para el modelo BooleanP(dj) = 1/N

1 if gi(dj)=1

P(ki | dj) = 0 otro caso

P(¬ki | dj) = 1 - P(ki | dj)

solo los nodos asociados con los términos índices del documento dj son activados


Para el modelo Boolean 1 if qcc | (qcc qdnf) ( ki, gi(k)= gi(qcc)P(q | k) =

0 otherwise

P(¬q | k) = 1 - P(q | k)

uno de los componentes conjuntivos de la consulta debe ser igualado por los términos índices activos en k


Para una estrategia tf-idf

P(dj)= 1 / |dj|

P(¬dj) = 1 - 1 / |dj|

probabilidad anterior refleja la importancia de normalización de documento


Para la estrategia tf-idf

P(ki | dj) = fi,j

P(¬ki | dj)= 1- fi,j

La relevancia del término ki es determinada por su factor de frecuencia de término normalizada fi,j = freqi,j / max freql,j


Para estrategia tf-idfDefine un vector ki dado por

ki = k | ((gi(k)=1) (ji gj(k)=0))

en el estado ki sólo el nodo ki está activo y todos los otros inactivos



idfi if k = ki gi(q)=1P(q | k) =

0 if k ki v gi(q)=0

P(¬q | k) = 1 - P(q | k)

sumamos las contribuciones individuales de cada término por su normalizado idf


Para una estrategia tf-idfAplicando la probabilidad,se tiene que

P(q dj) = Cj (1/|dj|) i [fi,j idfi (1/(1- fi,j ))] Cj cambia de documento en documento

El ranking es distinto del cual dado por el modelo vectorial


Combinando evidenciaSea I = q v q1

P(I dj) = k P(I | k) P(k | dj ) P( dj)

= k [1 - P(¬q|k)P(¬q1| k)] P(k| dj ) P( dj)

Puede llevar a un rendimiento de recuperación el cual sobrepasa el rendimiento de los nodos de consulta individuales (Turtle & Croft)


Modelo de Redes de Creencia

Como el Modelo de Redes de Inferencia• Una vista epistemológica • Variables aleatorias para docuementos,índices y

consultas Contrario a Redes de Inferencia

• Espacio de muestreo bien definido• Vista de teoría de conjuntos• Diferente topología de red

El espacio de probabilidadDefine:

K={k1, k2, ...,kt} el espacio de muestreo (un espacio conceptual)

u K un subconjunto de K (un concepto)ki un término índice (un concepto elemental)

k=(k1, k2, ...,kt) un vector asociado a cada u tal que gi(k)=1 ki u

ki una variable binaria aleatoria asociada con el término índice ki , (ki = 1 gi(k)=1 ki u)


Un vista de teoría de conjuntoDefine:

un documento dj y una consulta q como conceptos en K

un concepto genérico c en Kuna probabilidad de distribución P sobre K, como

P(c)=uP(c|u) P(u)

P(u)=(1/2)t

P(c) es el grado de cobertura del espacio por c


Topología de Red consultas

documentos


q

k1 k2 ki kt

dndjd1

Asume

P(dj|q) es adoptado como un ranking del documento dj con respecto a la consulta q. Refleja el grado de cobertura que da el concepto dj para el concepto q.


El ranking de dj

P(dj|q) = P(dj q) / P(q)

~ P(dj q)

~ u P(dj q | u) P(u)

~ u P(dj | u) P(q | u) P(u)

~ k P(dj | k) P(q | k) P(k)


Para el modelo vectorialDefine

Define un vestor ki dado por

ki = k | ((gi(k)=1) (ji gj(k)=0))

en el estado ki sólo el nodo ki está activo



(wi,q / |q|) if k = ki gi(q)=1P(q | k) =

0 if k ki v gi(q)=0

P(¬q | k) = 1 - P(q | k) (wi,q / |q|) es una versión normalizada del peso del término índice ki en la consulta q


Modelode Redes Bayesianas

Comparación Modelo de redes de inferencia en el primero y bien

conocido Modelo de redes de creencia adopta una vista de teoría de

conjunto Modelo de redes de creencia adopta un claro espacio de

muestreo Modelo de redes de creencia separa claramente la

consulta de los documentos Modelo de redes de creencia es capaz de reproducir

el ranking derivado de una red de inferencia (pero no el inverso)

Modelo de Redes Bayesianas

Costo Computacional Modelo de Redes de Inferencias: es lineal en el

número de documentos. Redes de creencia: sólo los estados de los

términos de la consulta son considerados Las redes no tienen ciclos y no imponen costos

adicionales

Modelos de Redes Bayesianas

Impacto

La combinación de propiedades de distintos modelos es una idea que ayuda a la mejora en recuperación de información.

Modelos Alternativos (2) M. Andrea Rodríguez Tastets DIIC - Universidad de Concepción andrea.

Documents

Transcript of Modelos Alternativos (2) M. Andrea Rodríguez Tastets DIIC - Universidad de Concepción andrea.