Redes Bayesianas para Recuperação de Informação Estruturada
Preview:
DESCRIPTION
Redes Bayesianas para Recuperação de Informação Estruturada, Adolfo Neto e Carlos Estombelo
Citation preview
- 1. Redes Bayesianas para Recuperao de Informao Estruturada
Carlos Estombelo (estombelo @ gmail.com) Adolfo Neto (adolfo.usp @
gmail.com) Projeto Tidia-Ae (FAPESP) Laboratrio de Informtica em
Sade e ImagCom (LISI) Departamento de Fsica e Matemtica (DFM)
Faculdade de Filosofia, Cincias e Letras de Ribeiro Preto (FFCLRP)
USP Ribeiro Preto Ribeiro Preto, 21 de setembro de 2007
- 2. Roteiro
- Proposta dos Autores do Artigo
- Problemas Encontrados na Abordagem dos Autores do Artigo
- 3. Motivao
-
- Temos uma coleo de documentos estruturados e uma consulta
-
- Queremos encontrar as partes de documentos na coleo que
satisfazem a consulta
-
- Queremos uma lista ordenada (por relevncia em relao consulta)
de partes de documentos
-
- Categorizar documentos estruturados
-
- Estabelecer ligaes entre partes de documentos estruturados
- 4. Motivao: Busca
- Por exemplo, temos uma coleo de documentos estruturados sobre
doenas tropicais
- Fazemos a consulta mosquito da dengue
- Queremos que o sistema retorne algo como:
-
- Doc[345]/Sec[3]/P[1] 0,91
-
- Doc[345]/Sec[3]/P[3] 0,745
- 5. Objetivo
- Implementar um sistema de recuperao de informao em colees de
documentos estruturados utilizando redes bayesianas
- Por que Redes Bayesianas? So bastante utilizadas em
Aprendizagem de Mquina .
- 6. Atividade Inicial
- Estudar abordagens que utilizem redes bayesianas na implementao
de sistemas de consultas em colees de documentos estruturados
-
- Descobrir como representada a coleo de documentos
-
- Entender como construda a rede bayesiana
-
-
- Ler os artigos e olhar o cdigo-fonte das aplicaes
disponveis
- 7. Artigo Estudado
- A Bayesian Framework for XML Information Retrieval: Searching
and Learning with the INEX Collection
- Information Retrieval, Springer (Qualis A)
- Volume 8, Number 4 / December, 2005
- Benjamin Piwowarski e Patrick Gallinari
- http://www.springerlink.com/content/gn25xp4p35j88205
- 8. Proposta dos Autores do Artigo
- Framework genrico (adaptvel a diferentes tipos de documentos
estruturados e colees)
- Modelo que permita considerar diferentes tarefas de accesso a
informao em um nico formalismo
- Modelo que permita executar sofisticadas inferncias
- Parmetros do modelo aprendidos a partir dos dados.
- FOCO: treinamento da RB estruturada usando como critrio de
treinamento a entropia cruzada.
- Recuperao de Informao distribuda
- 9. Siglas
- BN = Bayesian Network = Rede Bayesiana
- INEX = Initiative for the Evaluation of XML Retrieval =
Iniciativa para a Avaliao da Recuperao em XML
- ML = Maximum Likelihood = Mxima Verossimilhana
- EM = Expectation/Estimation Maximization = Maximizao de
Expectativa/Esperana
- CE = Cross Entropy = Entropia Cruzada
- DOXEL = Document Element = Elemento de Documento
- 10. EPSIR
- Experimental Platform for Structured Information Retrieval
- Sistema implementado por Benjamin Piwowarski
- Define linguagem de scripts para obter maior flexibilidade
- Utiliza a base de documentos avaliados do INEX 2003
- 11. Fases do Desenvolvimento do EPSIR Algoritmo de Aprendizagem
Consultas Avaliadas do INEX 2003 Tabelas de Parmetros da Rede
Bayesiana do EPSIR Consulta Qualquer EPSIR RP hs e ERR TREINAMENTO:
EXECUO: Consultas Avaliadas do INEX 2003 EPSIR Lista pontuada de
doxels AVALIAO DE DESEMPENHO:
- 12. Escala bidimensional INEX
- Exaustividade (Ex): descreve o grau que o documento DISCUTE o
tpico requisitado
- Especificidade (Sp): descreve o grau que o documento FOCA sobre
o tpico requisitado.
- 13. Aprendizagem com Redes Bayesianas
- Treinar Redes Bayesianas para Recuperao de Informao Estruturada
(RIE/SIR) uma tarefa desafiadora de aprendizagem de mquina.
- 14. Aprendizagem com Redes Bayesianas
-
- Heterogeneidade no conjunto de dados:
-
-
- grande variabilidade no contedo e comprimento dos dxeis
-
-
- a quantidade de exemplos de treinamento na base de dados do
INEX relativamente pequena com relao a esta variabilidade (30
consultas)
- 15. Aprendizagem com Redes Bayesianas
-
- A fase de treinamento exige uma rotulao coerente do conjunto de
dados
-
-
- A avaliao de consultas para o INEX uma tarefa tediosa e no
trivial
-
-
- As avaliaes do INEX 2003 no so completas, coerentes e
homogneas
-
-
- Elas podem levar a julgamentos contraditrios
-
- Ranking uma tarefa mais difcil do que classificao uma vez que
os valores relativos dos scores so importantes
- 16. Aprendizagem com Redes Bayesianas
- Treinar a BN uma aplicao no-standard de aprendizagem de
mquina
- Tal situao geralmente exige experimentos extensivos com
diferentes modelos e bastante tuning com os parmetros de
aprendizagem antes de encontrar uma soluo apropriada
- 17. Aprendizagem com Redes Bayesianas Na figura vemos a
independncia na rede bayesiana: conhecendo a relevncia de um
peridico, a relevncia da coleo de peridicos no tem nenhuma
influncia na relevncia dos artigos deste peridico. Sejam X e Y
independentes dado Z ento: P(X|Y,Z) = P(X|Z). Isto quer dizer que
se o objetivo saber a probabilidade de X ento tanto faz o valor de
Y se voc ja sabe o valor de Z. No caso deste trabalho seria: P(Xi |
pai(Xi))
- 18. Aprendizagem com Redes Bayesianas Na figura vemos um pedao
de uma rede bayesiana utilizada para representar uma consulta sobre
uma base de documentos. Os ns Baseline model i for Nj (Mi)
representam a relevncia dos ns relativamente a uma consulta usando
um modelo como o Okapi.
- 19. Aprendizagem com Redes Bayesianas No modelo a probabilidade
que o elemento X esteja no estado {I, B, E} depende somente do
estado de seu pai e do resultados dos modelos baseline (R, -R)
Tabela de probabilidades condicionais associadas ao n X [Parmetros
a serem aprendidos] Para reduzir ou limitar o nmero de parmetros
livres, os doxel se agrupam em categorias e estes doxel utilizaram
a mesma tabela de probabilidades condicionais
- 20. Aprendizagem com Redes Bayesianas
- O treinamento de uma BN geralmente feito maximizando a
probabilidade do modelo em relao a um conjunto de treinamento.
- Diferentes algoritmos podem ser utilizados para isso.
- Um dos mais populares o algoritmo EM (Estimation-Maximisation)
- Dempster e outros, 1977
- Learning Probabilistic Networks, PJ Krause, 1998, faz uma
reviso dos algoritmos de treinamento para BNs
- 21. Aprendizagem com Redes Bayesianas
- Neste trabalho, para cada consulta, o conjunto de variveis com
evidncia consiste de todas as variveis associadas a ns com um
julgamento de relevncia.
- Todos os outros estados de variveis so desconhecidos ou
escondidos na terminologia de BNs.
- Mtodos iterativos como EM tm que ser usados para
treinamento.
- 22. Aprendizagem com Redes Bayesianas
- O algoritmo permite o aprendizado das probabilidades
condicionais: a probabilidade dos dados aumenta regularmente com as
iteraes do EM
- Porm, experimentos feitos com maximum likelihood EM no INEX
levaram a resultados desapontadores.
- 23. Aprendizagem com Redes Bayesianas
- Proposta dos Autores - usar outro critrio de treinamento: a
entropia cruzada (CE) entre uma distribuio alvo e a distribuio
aprendida pela BN
- Este critrio permitiu atingir uma performance mais satisfatria,
o que foi promissor
- Reflete mais aproximadamente o objetivo de aprendizagem para
SIR, e permite um treinamento mais rpido do que o algoritmo EM
- Para aprender as probabilidades condicionais dos ns com CE, um
mapeamento precisa ser definido entre uma avaliao e seu valor de
varivel associada ao n.
- 24. Mapeamento
- Mapeando a escala de relevncia do INEX para a distribuio de
probabilidade dos estados da BN:
1 0 0 Ex 0 Sp 0 0.5 0.5 0 Ex 1 Sp 1 0.5 0.25 0.25 Ex 1 Sp 2 0.5 0
0.5 Ex 1 Sp 3 0.25 0.75 0 Ex 2 Sp 1 0.25 0.375 0.375 Ex 2 Sp 2 0.25
0 0.75 Ex 2 Sp 3 0 1 0 Ex 3 Sp 1 0 0.5 0.5 Ex 3 Sp 2 0 0 1 Ex 3 Sp
3 I B E P(X=...)
- 25. O Algoritmo de Treinamento
- O critrio de treinamento a entropia cruzada entre os valores
das variveis alvo (como definidos pelo mapeamento anterior) e os
valores calculados pela BN:
- Q( )=- q peso(q) j vj V P T (X j =v j |q)logP (X j =v j
|q)
- Onde P a probabilidade a ser estimada
- 26. O Algoritmo de Treinamento
- Normalizamos a contribuio de cada consulta fazendo:
-
- Peso(q) = (quantidade de ns acessados) -1
- A somatria de q sobre o conjunto de todas as consultas de
treinamento
- A somatria de j sobre o conjunto de todas as variveis X j com
uma distribuio de probabilidade conhecida P T (X j =v j |q) para v
j V.
- 27. O Algoritmo de Treinamento
- O conjunto de variveis X j corresponde ao conjunto de doxels
com uma avaliao conhecida no conjunto de documentos de
treinamento.
- Comparado ML, este critrio fornece uma aproximao melhor da
distribuio desejada nos diferentes ns e neste sentido est mais
prximo do objetivo de aprendizagem para SIR.
- 28. O Algoritmo de Treinamento
- A minimizao de Q( ) pode ser efetuada via gradient descent
(descida em gradiente ou gradiente descendente)
- A derivada de erro com relao ao parmetro :
onde as somatrias so as mesmas da frmula de Q( ) .
- 29. O Algoritmo de Treinamento
- A frmula de atualizao para o parmetro :
- 30. O Algoritmo de Treinamento
-
- As primeiras somatrias sobre q, j e v so as mesmas
-
- Na segunda somatria ( l anc(j)), para cada valor v j de varivel
X j com avaliao conhecida, somamos todas as contribuies, com relao
a um dado parmetro , dos seus pares ancestrais (X l , pai X pa(l) )
onde X l um ancestral de X j .
- 31. O Algoritmo de Treinamento
-
- Esta contribuio modulada pelo termo de erro
-
- e pela probabilidade de que X j esteja no estado v j se seus
ancestrais X l e X pa(l) estiverem respectivamente nos estados v l
e v pa(l) .
- 32. O Algoritmo de Treinamento
- A implementao do algoritmo segue diretamente da frmula
anterior:
-
- Loop em cada n da BN para o qual temos uma avaliao para a
consulta
-
- Loop nos valores diferentes da varivel anterior
- Todos os parmetros so atualizados em paralelo
- 33. O Algoritmo de Treinamento
- Treinar um n apenas exige o conhecimento dos valores dos seus
ancestrais, o que leva a um algoritmo de treinamento muito mais
rpido do que o EM.
- A razo que o critrio de CE definido apenas para as variveis
para as quais existe uma avaliao.
- 34. Experimentos
- 30 consultas do INEX 2003 divididas em dois conjuntos (A e B)
de 15 consultas cada
- Cada conjunto foi usado alternadamente para treinamento e
teste: treinamento foi feito com A e teste com B, e
vice-versa.
- Em todos os experimentos a curva de erro para CE claramente
diminuiu tanto para treinamento como para teste, significando que o
algoritmo de fato otimiza de forma efetiva o critrio de CE.
- 35. Experimentos
- Isto significa que o erro rapidamente chega a um mnimo, depois
de aproximadamente 1000 iteraes.
- 36. Problemas Encontrados na Abordagem dos Autores do Artigo
- Depende de uma coleo de documentos estruturados avaliada
(INEX)
- Esta coleo no de livre acesso
- No existe uma medida padro de performance do SRI devido a que
no existe um objetivo bem definido na aprendizagem.
- A quantidade de exemplos de treinamento na base de dados do
INEX relativamente pequena com relao a esta variabilidade (30
consultas)
- 37. Problemas Encontrados na Abordagem dos Autores do Artigo
- A coleo INEX 2007 diferente da coleo INEX 2003, na INEX 2007 no
tem mais a exaustividade, somente existe a escala de especificidade
e aps o usurio avaliar o documento com o sistema de avaliao, este
calcula um valor entre 0 e 1 para esta especifidade com relao ao
documento.
- 38. Nossa Proposta
- Estudar com profundidade a abordagem EPSIR
- Implementar uma verso adaptada ao INEX 2007 do algoritmo
utilizado pelo EPSIR
- Testar com a base do INEX 2007
-
- como existe somente a especificidade entre 0 e 1, poderamos
discretizar essa faixa .
- Pesquisar formas de melhorar o algoritmo
-
- Aps a montagem bsica o sistema a proposta de utilizar uma
entropia diferente (Tsallis).
-
- Continuar focando em um treinamento robusto com a coleo INEX
2007.
- Implementar, testar e comparar
- Publicar os resultados obtidos
- 39. Outros artigos
-
- A Belief Networks-Based Generative Model for Structured
Documents. An Application to the XML Categorization. Ludovic
Denoyer and Patrick Gallinari. 2003.
-
- Calcula a probabilidade de que um documento faa parte de uma
categoria utilizando informaes estruturais
-
- Utiliza o algoritmo EM para aprender os parmetros da rede
bayesiana (algoritmo que foi descartado no trabalho sobre
busca)
- 40. Outros artigos
-
-
- Bayesian network model for semi-structured document
classification. Ludovic Denoyer and Patrick Gallinari. 2004.
- 41. Outros artigos
-
- Collaborative Knowledge Management: Evaluation of Automated
Link Discovery in the Wikipedia. Wei Che Huang, Andrew Trotman e
Shlomo Geva. 2007
-
- Descrio da Link-the-Wiki Track no INEX 2007
- 42.
- 43. FIM!
- 44. Slides Extras
- 45. Aprendizagem com Redes Bayesianas com EM
- Para o treinamento de ML com este modelo, cada varivel X deve
tomar um e apenas um valor entre I, B ou E.
- As avaliaes do INEX so numa escala bidimensional
(Exaustividade, Especificidade) com 4 valores possveis em cada
dimenso
- Desses 4x4 valores possveis, apenas 10 so vlidos
- Cada uma dessas 10 avaliaes deve ento ser mapeada no espao
tridimensional V={I, B, E}
- Dito de outra forma, para cada avaliao de doxel X, associamos
valores alvo 1 ou 0 para as probabilidades
- P(X=vx | variveis pai de X na BN, q) para vx V
- Perdemos uma grande parte da informao presente nas avaliaes uma
vez que o espao de avaliaes com 10 dimenses mapeado em um espao V
tridimensional
- 46. Aprendizagem com Redes Bayesianas com EM
- Porm, para estes experimentos diferentes, o desempenho medido
com highly specific inex_eval ou ERR foi menor do que a obtida com
Okapi D-P ou D-T sozinhos.
-
- Pequena quantidade de doxels avaliados na coleo
-
- A rotulao de variveis observadas na BN para o algoritmo ML
reduz a quantidade de informao
- 47. Aprendizagem com Redes Bayesianas com EM
- A distribuio de probabilidade alvo apenas uma aproximao
bastante crua do objetivo de aprendizagem que deveria refletir o
ranking desejado dos doxels.
- Aprender uma distribuio de probabilidade mais adequada iria
envolver um modelo de BN mais complexo, que incluiria variveis
randmicas reais.
- Isto seria proibitivo para SIR.
- 48. O Algoritmo de Treinamento
- Diferentes algoritmos de gradiente poderiam ter sido
utilizados.
- Para os experimentos foi usado um algoritmo de gradiente
descendente simples ( simple gradient descent algorithm ) onde a
taxa de aprendizagem foi configurada automaticamente por uma busca
em linha ( line search ).
- 49. O Algoritmo de Treinamento
- Foi usado o algoritmo de Armijo que encontra o maior epsilon
para o qual:
- Valor inicial de 0.1 para (0)
- Dividir este valor por 2 at que a desigualdade acima seja
verificada.
- Os parmetros foram ento atualizados para + (opt) Q().