Download Searching the Web in Context - Universidad Nacional del Sur

CO NICET
Searching the Web in Context: Genetic
Algorithms for Exploring Query Space
Rocío L. Cecchini – Carlos M. Lorenzetti
Ana G. Maguitman – N. Beatriz Brignole
Bahía Blanca
LIDeCC – LIDIA – Universidad Nacional del Sur
Planta Piloto de Ingeniería Química
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Introducción
Objetivo del trabajo
• Diseñar nuevas técnicas capaces de refinar consultas de
manera automática para acumular recursos relevantes respecto
a un contexto temático.
R1
t1 t2 t3 t4 t5 … …
R2
R3
JAIIO 2007 – Mar del Plata, Buenos Aires
2
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Introducción
Objetivo del trabajo
Contexto
Artículos
Diario
Good
t1 t2 t3 … queries
Otros
R1
R2
JAIIO 2007 – Mar del Plata, Buenos Aires
RN
3
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Utilidad de generar buenas consultas
• Búsqueda basada en la tarea del usuario
• Recolección de recursos web para portales temáticos
• Búsqueda en la web oculta
• Soporte para gestión de conocimiento.
JAIIO 2007 – Mar del Plata, Buenos Aires
4
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Técnica basada en AGs
Objetivo del trabajo
Contexto
Artículos
Diario
Good
AGs
t1 t2 t3 … queries
Otros
R1
R2
JAIIO 2007 – Mar del Plata, Buenos Aires
RN
5
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Algoritmos Genéticos – Revisión
Definición
• Los Algoritmos Genéticos son métodos estocásticos de
búsqueda de soluciones cuasi-óptimas. En ellos se
mantiene una población de potenciales soluciones, la cual
es sometida a ciertas transformaciones con las que se
trata de obtener nuevos candidatos. Además, esta
población es sometida a un proceso de selección sesgado
a favor de los mejores candidatos.
JAIIO 2007 – Mar del Plata, Buenos Aires
6
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Algoritmos Genéticos – Revisión
Algoritmo
Comienzo
E
ció
a
lu
va
n
Convergencia?
S
ec
l
e
ón
i
c
NO
SI
Fin
Crossover
Mutación
JAIIO 2007 – Mar del Plata, Buenos Aires
7
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
AGs para la Búsqueda web basada en contexto
Sistemas de información basados en contexto
• Los sistemas de información basados en contexto crean
un modelo del contexto del usuario, infieren necesidades
del usuario y buscan documentos relevantes en la web o
en otras librerías electrónicas.
Porque AGs?
• Búsqueda web basada en contexto como problema de
optimización.
„
„
Espacio de búsqueda?
Función objetivo?
JAIIO 2007 – Mar del Plata, Buenos Aires
8
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
AGs para la Búsqueda web basada en contexto
Porque AGs?
•
•
•
Espacio multidimensional
Soluciones subóptimas
Múltiples soluciones. Podemos tener:
„
„
Resultados satisfactorios en distintos individuos
Interés en encontrar más de una consulta.
• Exploración
„
„
Crossover
Mutación
• Explotación
„
Selección
JAIIO 2007 – Mar del Plata, Buenos Aires
9
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Esquema genético para obtener buenas consultas
Población
• Representación
q1
q3
q2
…qi…
qN
I1
IN
I3
Ij = t1,t2,t3, …, tk
Población
Espacio de búsqueda
Población
• Inicialización
N° de términos?
Contexto
JAIIO 2007 – Mar del Plata, Buenos Aires
10
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Esquema genético para obtener buenas consultas
Función de fitness
• Dado un espacio de búsqueda Q y un contexto temático
inicial c, definimos la función de fitness F de la siguiente
manera:
F ( q ) = m ax (σ ( c , d i ))
Donde
d i ∈ Aq
• Aq es el conjunto de resultados obtenidos para la consulta
q
• σ : D×D → [0…1] es la medida de similitud para un par de
documentos.
Obs:
• En σ puede usarse cualquier medida de similitud.
• En Aq no se usa el total de resultados obtenidos → 10 Snippets.
JAIIO 2007 – Mar del Plata, Buenos Aires
11
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Esquema genético para obtener buenas consultas
Operadores genéticos
• Método de Selección
q1
q2
S1
q3
SN
qN
Población
S3
F (q )
P (q )
Resultados
• Selección directa: un porcentaje de individuos de la
población seleccionada, pasa directamente a formar parte
de la nueva generación.
JAIIO 2007 – Mar del Plata, Buenos Aires
12
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Esquema genético para obtener buenas consultas
Operadores Genéticos
• Crossover
qa
q1
q2
q3
qN
qb
Población
• Mutación
Punto de mutació
mutación
qa
q1
q2
q3
qN
Población
JAIIO 2007 – Mar del Plata, Buenos Aires
Pool de mutación
13
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Arquitectura propuesta
Query
Population
WEB
Formulation of
Initial Queries
Thematic
Context Model
Mutation
Crossover
Search Engine
Calculation of
Query Fitness
Mutation
Pool
Context
Modeling
Selection
Term
Extraction
Search
Results
JAIIO 2007 – Mar del Plata, Buenos Aires
14
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Criterio de evaluación
Definición:
• Dado un contexto temático c, una consulta q y el conjunto
Aq={a1,…,an} de recursos recuperados para q. Una medida
de similitud entre c y un recurso ai puede ser computada
usando similitud por coseno definida como:
σ ( c , ai ) =
c ⋅ ai
c ⋅ ai
Donde:
• c es la representación vectorial del contexto temático c
• a i es la representación vectorial de ai
JAIIO 2007 – Mar del Plata, Buenos Aires
15
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Calidad de q basada en similitud máxima:
Quality _ Max ( q ) = max (σ (c , ai ))
ai ∈ Aq
Calidad de q basada en similitud promedio:
∑ (σ (c, a ))
Quality _ Mean ( q ) =
JAIIO 2007 – Mar del Plata, Buenos Aires
i
ai ∈ Aq
Aq
16
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Diseño de experimentos
2 Business
DMOZ
2 Recreation
6 tests
2 Society
Para cada uno de los testeos se realizaron 5 corridas con los
siguientes parámetros genéticos:
„
„
„
„
„
n = 60
g = 20
Probabilidad de cruzamiento = 0,7
Probabilidad de mutación = 0,03
Longitud máxima inicial de las consultas = 32 palabras
JAIIO 2007 – Mar del Plata, Buenos Aires
17
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Resultados
JAIIO 2007 – Mar del Plata, Buenos Aires
18
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Resultados
JAIIO 2007 – Mar del Plata, Buenos Aires
19
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Evaluación del funcionamiento
Resultados
JAIIO 2007 – Mar del Plata, Buenos Aires
20
Searching the Web in Context:
Genetic Algorithms for Exploring Query Space
Cecchini, Lorenzetti, Maguitman, Brignole
Conclusiones y trabajo futuro
Conclusiones
• Esta herramienta es aplicable a diferentes dominios en los
cuales sea posible construir un modelo de términos a
partir de un contexto.
• La adaptación de las consultas tiene un costo.
• Efectividad del AG en generación y refinamiento de
consultas.
Trabajo futuro
•
•
•
•
Experimentos con ≠ valores para los parámetros del AG.
Método de selección.
Aplicación de Programación Genética.
Función de fitness
JAIIO 2007 – Mar del Plata, Buenos Aires
21
CO NICET
Searching the Web in Context: Genetic
Algorithms for Exploring Query Space
Rocío L. Cecchini – Carlos M. Lorenzetti
Ana G. Maguitman – N. Beatriz Brignole
LIDeCC – LIDIA – Universidad Nacional del Sur
Planta Piloto de Ingeniería Química