Date post: | 24-Jan-2016 |
Category: |
Documents |
Upload: | hictor-padron |
View: | 215 times |
Download: | 0 times |
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.
Latent Semantic Indexing
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
Latent Semantic Indexing
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.
Modelo de Redes Neuronales
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.
Modelo de Redes Neuronales
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
Inferencia Bayesiana
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)
Inferencia Bayesiana
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)
Modelo de Redes de Inferencia
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)
Modelo de Redes de Inferencia
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)
Modelo de Redes de Inferencia
Como la instanciación de dj hace todos los nodos de términos índices mutuamente independientes P(k | dj ),entonces
P(q dj) = k [ P(q | k) x
(i|gi(k)=1 P(ki | dj ))x (i|gi(k)=0 P(¬ki | dj)) x
P( dj )]recuerde que: gi(k)= 1 si ki=1 en el vector k
0 en otro caso
Modelo de Redes de Inferencia
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|
Modelo de Redes de Inferencia
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
Modelo de Redes de Inferencia
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
Modelo de Redes de Inferencia
Para una estrategia tf-idf
P(dj)= 1 / |dj|
P(¬dj) = 1 - 1 / |dj|
probabilidad anterior refleja la importancia de normalización de documento
Modelo de Redes de Inferencia
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
Modelo de Redes de Inferencia
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
Modelo de Redes de Inferencia
Para la estrategia tf-idf
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
Modelo de Redes de Inferencia
Para la estrategia tf-idf
Como P(q|k)=0 k ki, se reescribe P(q dj) como
P(q dj) = ki [ P(q | ki) P(ki | dj )x
(l|li P(¬kl | dj)) x P( dj )] = (i P(¬kl | dj))x P( dj )x ki [P(ki | dj ) xP(q | ki) / P(¬ki| dj)]
Modelo de Redes de Inferencia
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
Modelo de Redes de Inferencia
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 Inferencia
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)
Modelo de Redes de Creencia
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
Modelo de Redes de Creencia
Topología de Red consultas
documentos
Modelo de Redes de Creencia
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.
Modelo de Redes de Creencia
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)
Modelo de Redes de Creencia
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
Modelo de Redes de Creencia
Para el modelo vectorialDefine
(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
Modelo de Redes de Creencia
Para el modelo vectorialDefine
(wi,j / |dj|) if k = ki gi(dj)=1
P(dj | k) =
0 if k ki v gi(dj)=0
P(¬ dj | k) = 1 - P(dj | k)
(wi,j / |dj|) es una versión normalizada del peso del término índice ki en el documento d,j
Modelo de Redes de Creencia
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.