WICC 2012

832

Caracterizaci´on Formal y An´alisis Emp´ırico de Mecanismos Incrementales de B´usqueda basados en Contexto Carlos M. Lorenzetti* Director: Codirector:

Guillermo R. Simari Ana G. Maguitman

Universidad Nacional del Sur 18 de marzo de 2011

Resumen La Web se ha vuelto un recurso potencialmente infinito de informaci´on, transform´andose adem´as en una herramienta imprescindible para muchas tareas de la vida diaria. Esto provoc´o un aumento en la cantidad de informaci´on existente en el contexto de los usuarios, que no es tenida en cuenta por los sistemas de recuperaci´on de informaci´on actuales. En esta tesis se propone una t´ecnica semisupervisada de recuperaci´on de informaci´on que ayuda al usuario a recuperar informaci´on relevante para su contexto actual. El objetivo de la misma es contrarrestar la diferencia de vocabulario que pudiera existir entre el conocimiento que tiene el usuario sobre un tema y los documentos relevantes que se encuentran en la Web. Se presenta un m´etodo de aprendizaje de nuevos t´erminos asociados a un contexto tem´atico, a trav´es de la identificaci´on de t´erminos que sean buenos descriptores y t´erminos que sean buenos discriminadores del t´opico del contexto actual del usuario. Para la evaluaci´on del m´etodo propuesto se desarroll´o un marco te´orico de evaluaci´on de mecanismos de b´ usqueda y, a partir de este, se implement´o una plataforma de evaluaci´on, que adem´as permiti´o comparar las t´ecnicas desarrolladas en esta tesis con otras t´ecnicas existentes en la literatura. La evidencia experimental muestra que las mejoras alcanzadas son significativas respecto de otros trabajos publicados. Dentro de este marco se desarrollaron asimismo nuevas m´etricas de evaluaci´on que benefician al material novedoso y que incorporan una medida de relaci´on sem´antica entre documentos. Los algoritmos desarrollados a la largo de esta tesis evolucionan consultas de alta calidad, permitiendo recuperar recursos relevantes al contexto del usuario, e impactan positivamente en la forma en la que ´este interact´ ua con los recursos que tiene disponibles.

*

Laboratorio de Investigaci´ on y Desarrollo en Inteligencia Artificial, Departamento de Ciencias e Ingenier´ıa de la Computaci´on, Universidad Nacional del Sur, Av. Alem 1253, Bah´ıa Blanca, Argentina, [email protected] La tesis completa puede accederse en http://cs.uns.edu.ar/˜cml/tesisdoctoral.html.

2012

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

1.

833

Introducci´ on

La Recuperaci´on de Informaci´on (IR1 ) web es un a´rea de investigaci´on relativamente nueva, que se populariz´o desde la aparici´on de la Internet a principios de los ’90s y trata de afrontar los desaf´ıos de la IR en la Internet. La investigaci´on de la IR con la ayuda de computadoras data de los ’50s, cuando el esfuerzo estaba enfocado en la resoluci´on de problemas de IR en colecciones de documentos peque˜ nas, con consultas descriptivas, en un dominio acotado y con usuarios particulares. Las caracter´ısticas del nuevo entorno que result´o la World Wide Web (Web), hicieron que la tarea fuera algo diferente de la IR tradicional. La Web es un recurso pr´acticamente ilimitado, con informaci´on heterog´enea, con usuarios dotados de distintas habilidades y con gran variedad de requisitos, buscando informaci´on que satisfaga sus necesidades. Estos necesitan que la Web sea accesible a trav´es de sistemas de recuperaci´on de informaci´on efectivos y eficientes. El tama˜ no, la heterogeneidad, el dinamismo y la estructura de la Web, junto con la diversidad en los comportamientos de b´ usqueda de los usuarios, son las principales caracter´ısticas que hacen que la IR tradicional tenga grandes desaf´ıos en la Internet. Los motores de b´ usqueda comerciales, que son los sistemas de IR m´as populares, han resuelto parcialmente los desaf´ıos con los que se enfrenta la IR en la Web, ofreciendo una herramienta para la b´ usqueda de informaci´on relevante. En efecto, los usuarios actuales esperan ser capaces de encontrar la informaci´on que buscan en la Web, de forma r´apida y f´acil. La IR en la Web, sin embargo, contin´ ua siendo un a´rea con muchas cuestiones por resolver, probablemente con muchas aplicaciones por descubrir. En la actualidad sigue existiendo la necesidad de desarrollar m´etodos novedosos para facilitar el acceso eficiente a la informaci´on relevante en la Web. Algunos problemas de investigaci´on van desde comprender mejor las necesidades del usuario, al procesamiento de enormes cantidades de informaci´on para brindar mejores m´etodos de ordenamiento, que hagan uso de la estructura y las caracter´ısticas de la Web.

2.

Motivaci´ on

La omnipresencia de las computadoras personales, unida a la conectividad de la Internet han cambiado para siempre el rol de la informaci´on en la computaci´on. Los recursos de informaci´on ya no est´an m´as relacionados con una u ´nica ubicaci´on ni son accedidos s´olo por profesionales. Los sistemas de IR est´an disponibles para los usuarios de Internet cada d´ıa, desde el confort de su propia computadora personal. Estos repositorios de informaci´on se acceden de la misma forma en la que se escriben art´ıculos, se leen diarios y se navegan sitios de la Web. Desafortunadamente, los sistemas de IR tradicionales resultaron dif´ıciles de usar para usuarios nuevos, lo que impuls´o el desarrollo de una gran cantidad de sistemas para buscar, filtrar y organizar la gran cantidad de informaci´on que se ten´ıa disponible. Se desarrollaron sistemas de IR para aplicaciones que van desde la clasificaci´on y organizaci´on de correo electr´onico [30, 18], el filtrado de noticias [24], sistemas para responder consultas basados en las FAQ2 de Usenet3 [21], y la b´ usqueda en la Web [32, 6]. Tambi´en se han desarrollado algunas aplicaciones para organizar la informaci´on del usuario, como pueden ser archivos de notas, diarios y calendarios [22, 23]. Sin embargo, la mayor´ıa de estos sistemas, que se han convertido en la piedra angular del acceso a la informaci´on, s´olo se han concentrado en la generaci´on de consultas para recuperar informaci´on por demanda, lo que significa que el usuario tiene que invocarlos expl´ıcitamente, interrumpiendo el proceso normal de navegaci´on y esperando ocioso por los resultados de la b´ usqueda. Tales sistemas no pueden ayudar a un usuario cuando ´este no est´a suficientemente 1

del ingl´es, Information Retrieval. del ingl´es, Frequently Asked Questions, Preguntas frecuentes. 3 del ingl´es, USErs NETwork. 2

2012

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

834

familiarizado con el tema en cuesti´on, o desconoce el vocabulario exacto con el que debe formular las consultas para acceder a los recursos de inter´es. Este escenario trae nuevos desaf´ıos y oportunidades a los dise˜ nadores de tales sistemas, tanto para crear sistemas accesibles como para aprovechar por completo este nuevo espacio de informaci´on oculta. El crecimiento explosivo que ha tenido la Web y otras fuentes de informaci´on on-line han hecho cr´ıtica la necesidad de alguna clase de asistencia inteligente para el usuario que est´a buscando informaci´on relevante. Al desarrollarse computadoras de escritorio cada vez m´as potentes, la mayor parte del tiempo de CPU de ´estas se desperdicia esperando que el usuario presione la siguiente tecla, lea la siguiente p´agina o se cargue el siguiente paquete de la red. No hay raz´on para que esos ciclos de CPU desperdiciados no puedan ser usados constructivamente para realizar b´ usquedas de informaci´on u ´til para el contexto actual del usuario. Por ejemplo, mientras un ingeniero lee un correo electr´onico sobre un proyecto, un agente puede recordarle la planificaci´on, los reportes de avance u otros recursos relacionados con ese proyecto. Cuando el ingeniero no lee m´as el correo y, por ejemplo, comienza a editar un archivo, el agente cambiar´ıa autom´aticamente sus recomendaciones para adecuarse a la nueva tarea. Para los dise˜ nadores de interfaces de exploraci´on de informaci´on tambi´en se presentan problemas interesantes, ya que la forma en la que un usuario genera una consulta depende de su conocimiento previo y de su entendimiento del tema. Algunas preguntas que surgen son: ¿c´omo les presentamos a los usuarios las posibles acciones que pueden tomar teniendo en cuenta su entendimiento actual?, ¿c´omo podemos ayudar a los usuarios a tener un mejor entendimiento de estas referencias?, y ¿c´omo podemos ayudar a los usuarios a volver a sitios visitados con anterioridad en la exploraci´on, una vez que se gan´o una nueva perspectiva? La motivaci´on para las investigaciones presentadas en esta tesis es desarrollar una herramienta que ayude y asista al usuario de un sistema de IR en la tarea que est´a realizando, brind´andole informaci´on relevante y basada en el contexto en el cual est´a trabajando.

3.

Contribuciones

Este trabajo de investigaci´on propone una t´ecnica de IR novedosa que incrementalmente aprende nuevos t´erminos que pueden ayudar a reducir la distancia existente entre el vocabulario empleado en las consultas formuladas por un usuario y el vocabulario utilizado para indexar los documentos relevantes para dicho usuario. Es decir, las principales contribuciones de esta tesis son: 1. Un Algoritmo semisupervisado que utiliza una estrategia de recuperaci´on incremental de documentos web para el ajuste de la importancia de los t´erminos utilizados en la generaci´on de consultas, de forma tal que ´estos reflejen mejor su valor como descriptores y discriminadores del t´opico del contexto del usuario. El vocabulario enriquecido de esta forma permite la generaci´on de consultas para una b´ usqueda m´as efectiva. 2. Una Plataforma de evaluaci´on de nuevos m´etodos y algoritmos desarrollados para la IR. Una plataforma de evaluaci´on es algo fundamental en el desarrollo de nuevos m´etodos en IR, permitiendo la comparaci´on con las t´ecnicas existentes. Tambi´en se proponen nuevos m´etodos de evaluaci´on sustentados en una m´etrica de similitud sem´ antica para la comparaci´on de documentos.

2012

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

3.1.

835

M´ etodo incremental de recuperaci´ on de informaci´ on basado en contexto

Este trabajo presenta t´ecnicas generales para aprender incrementalmente t´erminos relevantes asociados a un contexto tem´atico. Espec´ıficamente se estudian tres preguntas: 1. ¿Puede el contexto del usuario explotarse satisfactoriamente para acceder a material relevante en la Web? 2. ¿Puede un conjunto de t´erminos espec´ıficos de un contexto ser refinado incrementalmente bas´andose en el an´alisis de los resultados de una b´ usqueda? 3. ¿Los t´erminos espec´ıficos de un contexto aprendidos mediante m´etodos incrementales, son mejores para generar consultas comparados con aquellos encontrados por t´ecnicas cl´asicas de IR o m´etodos cl´asicos de reformulaci´on de consultas? La contribuci´on de este trabajo es un algoritmo semisupervisado que aprende incrementalmente nuevo vocabulario con el prop´osito de mejorar consultas. El objetivo es que las consultas reflejen la informaci´on contextual y as´ı puedan recuperar efectivamente material relacionado sem´anticamente. En este trabajo se utiliz´o una m´etrica est´andar de evaluaci´on del rendimiento y dos m´etricas ad hoc para descubrir si estas consultas son mejores que las generadas utilizando otros m´etodos. La pregunta principal que gui´o este trabajo es c´omo aprender t´erminos espec´ıficos a un contexto bas´andonos en la tarea del usuario y en una colecci´on abierta de documentos web recuperados incrementalmente. Se asume que la tarea del usuario est´a representada como un conjunto de t´erminos cohesivos que resumen el t´opico del contexto del usuario. Consideremos un ejemplo que involucra la M´aquina Virtual de Java, descripto por los siguientes t´erminos: java computers sun

virtual netbeans technology

machine applets source

programming ruby jvm

language code jdk

Los t´erminos espec´ıficos a un contexto juegan distintos roles. Por ejemplo, el t´ermino java es un buen descriptor del t´opico para el com´ un de las personas. Por otro lado, t´erminos como jvm y jdk (acr´onimos de “Java Virtual Machine” y “Java Development Kit” respectivamente) pueden no ser buenos descriptores del t´opico para esas mismas personas, pero son efectivos recuperando informaci´on similar al t´opico cuando se los utiliza en una consulta. Luego, jvm y jdk son buenos discriminadores del t´opico. Para distinguir entre descriptores y discriminadores de t´opicos se argumenta que buenos descriptores de t´ opicos pueden encontrarse buscando aquellos t´erminos que aparecen en la mayor´ıa de los documentos relacionados con el t´opico deseado. Por otro lado, buenos discriminadores de t´ opicos pueden hallarse buscando t´erminos que s´olo aparecen en documentos relacionados con el t´opico deseado. Ambos tipos de t´erminos son importantes a la hora de generar consultas. Utilizar t´erminos descriptores del t´opico mejora el problema de los resultados falso-negativos porque aparecen frecuentemente en p´aginas relevantes. De la misma manera, los buenos discriminadores de t´opicos ayudan a reducir el problema de los falsos-positivos, ya que aparecen principalmente en p´aginas relevantes. En [31] se propone estudiar el poder descriptivo y discriminante de un t´ermino bas´andose en su distribuci´on a trav´es de los t´opicos de las p´aginas recuperadas por un motor de b´ usqueda. All´ı, el espacio de b´ usqueda es la Web completa y el an´alisis del poder descriptivo o discriminante de un t´ermino est´a limitado a una peque˜ na colecci´on de documentos que se va construyendo incrementalmente y que var´ıa en el tiempo. A diferencia de los esquemas de IR tradicionales, 2012

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

836

los cuales analizan una colecci´on predefinida de documentos y buscan en ella, los m´etodos propuestos utilizan una cantidad limitada de informaci´on para medir la importancia de los t´erminos y documentos as´ı como tambi´en para la toma de decisiones acerca de cu´ales t´erminos conservar para an´alisis futuros, cu´ales descartar, y qu´e consultas adicionales generar. 1

Extracción del contexto

2

Formulación de consultas y proceso de recuperación

3

Procesamiento de los resultados

4

Proceso de actualización del contexto wm

Contexto

w1

1

2

4

Ruleta

w2

Términos

wm-2 wm-1 ...

w3

w4

w9

w5

w8 w7 w6

descriptores w1 0,5 w2 0,25 . . . wm 0,1

w1 0,4 w2 0,37 . . . wm 0,01

discriminadores

3

resultado 01

consulta 01

resultado 02

consulta 02

resultado 03

consulta 03

resultado n

consulta n

Figura 1: Una representaci´on esquem´atica del m´etodo incremental para el refinamiento de consultas tem´aticas. Como parte del trabajo de esta tesis se comenz´o formulando un marco te´orico [17] que realiza un an´alisis cualitativo y cuantitativo del contexto del usuario para el mejoramiento de los resultados de una b´ usqueda. En la Figura 1 puede verse un esquema del m´etodo incremental para el refinamiento de consultas basado en un contexto tem´atico. El sistema lleva a cabo una serie de fases con el objetivo de aprender mejores descripciones de un contexto tem´atico. En la figura esto est´a representado por el ciclo de pasos que van desde el paso 1 al paso 4. Al final de cada fase se actualiza la descripci´on del contexto con el nuevo material aprendido (paso 4). Continuando con las investigaciones se lleg´o a la conclusi´on de que el contexto puede utilizarse para encontrar material relevante, aunque en [29] se mostr´o que las palabras m´as frecuentes no siempre son las m´as u ´tiles. Es por esto que, bas´andose en los resultados obtenidos, se hizo hincapi´e en el uso de m´etodos incrementales para el refinamiento del contexto del usuario, desarrollando una nueva t´ecnica de enriquecimiento del vocabulario [27]. Una versi´on extendida de este trabajo fue publicada en [28], en donde puede encontrarse un desarrollo m´as profundo del m´etodo incremental y en donde tambi´en puede encontrarse su comparaci´on con otros m´etodos de IR. Paralelamente a estos trabajos se estudi´o el impacto de utilizar Algoritmos Gen´eticos (AG) como alternativa v´alida para el refinamiento del contexto, dada sus probadas cualidades en problemas de optimizaci´on [8]. Continuando con este trabajo, se incluy´o un algoritmo basado en AGs en la plataforma propuesta. Se analizaron las razones por las que los AGs son apropiados para la b´ usqueda Web y se describi´o el funcionamiento del algoritmo. Las evaluaciones realizadas en [13] mostraron la efectividad de los m´etodos propuestos y las ventajas que presentan respecto de otros trabajos publicados previamente. Siguiendo con estas investigaciones se decidi´o analizar el efecto de la variaci´on de distintos par´ametros propios de un AG, como son por ejemplo, las 2012

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

837

tasas de cruzamiento y mutaci´on [12]. A partir de estos trabajos se fueron publicando distintos resultados a medida que se avanzaba en la investigaci´on [14, 11, 9, 10]. Los resultados completos de estos estudios pueden encontrarse en [15].

3.2.

Plataforma de evaluaci´ on

Contexto

representación

Consultas

Algoritmo de IR

consulta 01 consulta 02

estadísticas

métricas

consulta 03

consulta n

pedidos

documentos

Interfaz Motores de Búsqueda

Las primeras evaluaciones realizadas a trav´es de esta plataforma se presentan en [25], comparando el m´etodo incremental propuesto, basado en la utilizaci´on de las nociones de descriptores y discriminadores de t´opicos, con un mecanismo simple tomado como referencia. Se introdujo tambi´en la noci´on de similitud novedosa, que es conceptualmente similar a la medida de similitud m´as conocida en IR, la similitud por coseno. Sin embargo esta medida es capaz de descubrir nuevas relaciones entre los documentos y el contexto del usuario, ya que favorece a aquellos que contienen informaci´on relevante y que a su vez contienen t´erminos que no se encontraban en documentos anteriores. La plataforma incluye actualmente una colecci´on local de documentos que fueron indexados con la plataforma de c´odigo abierto Terrier4 , desarrollada por la Universidad de Glasgow. El acceso a este ´ındice se realiza a trav´es de una interfaz que es capaz de aceptar otros tipos de ´ındices e incluso, motores de b´ usqueda web. En un comienzo, se implement´o una interfaz para el servicio web SOAP de Google5 , que luego fuera reemplazado por la empresa por una API AJAX. La utilizaci´on del servicio web permiti´o el desarrollo de las primeras versiones de los algoritmos presentados en esta tesis. Finalmente se opt´o por un ´ındice local de documentos web debido a las limitaciones que se encontraron en cuanto a los tiempos de ejecuci´on de los algoritmos y al l´ımite impuesto por Google a la cantidad de consultas que se pod´ıan realizar por d´ıa. Algunos resultados obtenidos mediante el uso de esta nueva plataforma se muestran en [26].

Motor de búsqueda Web Motor de búsqueda local

Resultados

Figura 2: Representaci´on esquem´atica de la plataforma de evaluaci´on.

Una representaci´on esquem´atica de la Plataforma de Evaluaci´on se muestra en la Figura 2. Como se puede observar existe una primera parte que se encarga de la representaci´on de las consultas. Estas pueden ingresarse como un conjunto o como un documento, a partir del cual el sistema generar´a las consultas necesarias. Por otro lado, la plataforma ofrece una interfaz de comunicaci´on con los distintos motores de b´ usqueda. Como se dijo m´as arriba, una de las posibilidades es contar con un motor de b´ usqueda web. Tambi´en existe un componente dedicado al c´alculo de las m´etricas que guiar´an los algoritmos de b´ usqueda y que tambi´en servir´an para 4 5

2012

http://www.terrier.org http://www.google.com

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

838

su evaluaci´on. En [16] se desarrollan estas m´etricas y se las compara con otras existentes en la literatura. Como parte de las contribuciones de esta tesis se desarrollaron dos m´etricas nuevas para la comparaci´on de documentos en algoritmos de IR. Una de ellas es la Similitud novedosa, una medida de comparaci´on entre documentos que descarta los t´erminos que pudieran introducir un sesgo en la medici´on, beneficiando a los documentos que incluyen t´erminos nuevos. La otra es la Precisi´on sem´antica, una m´etrica para la comparaci´on de los resultados de un sistema de recuperaci´on de informaci´on. Esta medida brinda una noci´on m´as rigurosa de la calidad de los documentos recuperados por un algoritmo de IR, al incorporar la noci´on de relevancia parcial entre t´opicos. Este nuevo concepto se basa en una m´etrica de similitud entre nodos de un grafo arbitrario. En particular se utiliz´o la ontolog´ıa creada por el Open Directory Project (ODP6 ), que es un gran directorio de la Web editado por personas, y utilizado por cientos de portales y sitios de b´ usqueda. El ODP clasifica millones de URLs en una ontolog´ıa tem´atica. Las ontolog´ıas ayudan a darle sentido a un conjunto de objetos y, con esta informaci´on, pueden derivarse relaciones sem´anticas entre esos objetos y, por lo tanto, son una fuente muy u ´til de donde se pueden obtener medidas de similitud sem´antica.

4.

Conclusiones

A lo largo de esta tesis se desarroll´o una herramienta de recuperaci´on de informaci´on que ayuda al usuario en la tarea que est´a realizando, brind´andole informaci´on relevante y basada en su contexto actual. Para ello se propuso una soluci´on al problema de la sensibilidad sem´antica, que es la limitaci´on que surge cuando no se puede hallar una relaci´on entre dos documentos similares sem´anticamente, porque contienen distintos t´erminos en su vocabulario, resultando en un falso-negativo al intentar recuperar material relevante. Adem´as, mediante la identificaci´on de buenos discriminadores de t´opicos, la propuesta presentada en esta tesis ayuda a mitigar el problema de falsos-positivos, que aparece cuando el mismo t´ermino (p. ej., java) aparece en dos t´opicos diferentes. El m´etodo enunciado trabaja aprendiendo incrementalmente mejores vocabularios de un gran conjunto de datos como la Web. A partir de este trabajo se concluye que la informaci´on contextual puede ser utilizada con ´exito para acceder a material relevante. Sin embargo, los t´erminos m´as frecuentes en ese contexto no son necesariamente los m´as u ´tiles. Es por ello que se propone un m´etodo incremental para el refinamiento del contexto, que se basa en el an´alisis de los resultados de las b´ usquedas y que mostr´o ser aplicable a cualquier dominio caracterizable por t´erminos. En este trabajo se demostr´o que al implementar un m´etodo incremental semisupervisado de refinamiento del contexto se puede mejorar el rendimiento alcanzado por un m´etodo base, el cual env´ıa consultas generadas directamente a partir del contexto inicial, y mejorar tambi´en el rendimiento del m´etodo de refinamiento Bo1-DFR [1], el cual no refina las consultas bas´andose en un contexto. Esto muestra la utilidad de aprovechar simult´aneamente los t´erminos existentes en el contexto tem´atico actual y los de un conjunto externo de datos a la hora de aprender mejores vocabularios y de refinar consultas autom´aticamente. En esta tesis se implement´o una plataforma de evaluaci´on de m´etodos y t´ecnicas para la recuperaci´on de informaci´on. La misma permiti´o el desarrollo de los algoritmos presentados en este trabajo, proporcionando el soporte necesario para un an´alisis detallado de los resultados obtenidos. Dentro de esta plataforma tambi´en se implementaron las nuevas m´etricas propuestas en esta tesis. En la literatura se han propuesto otros m´etodos basados en corpus para atacar el problema 6

2012

http://dmoz.org

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

839

de la sensibilidad sem´antica. Por ejemplo, el an´alisis de la sem´antica latente [20, 19], o la t´ecnica PMI-IR7 [34]. Este m´etodo de recuperaci´on de informaci´on est´a basado en la informaci´on de polaridad mutua, que mide la relaci´on entre dos elementos (p. ej., t´erminos) comparando sus frecuencias observadas con respecto a las esperadas. Estas t´ecnicas se diferencian de la que se propone en que no se basan en un proceso incremental de refinamiento de consultas, sino que utilizan una colecci´on predefinida de documentos para identificar relaciones sem´anticas. Adem´as, estas t´ecnicas no distinguen las nociones de descriptores y discriminadores de t´opicos. Las t´ecnicas para la elecci´on de los t´erminos de las consultas propuestas en este trabajo est´an inspiradas y motivadas sobre la misma base de otros m´etodos de expansi´on y refinamiento de consultas [33, 5]. Sin embargo, los sistemas que aplican estos m´etodos se diferencian de la plataforma propuesta en que el proceso se realiza a trav´es de consultar o navegar en interfaces que necesitan la intervenci´on expl´ıcita del usuario, en lugar de formular consultas autom´aticamente. En los sistemas de recuperaci´on proactivos, el uso del contexto juega un rol vital a la hora de seleccionar y filtrar informaci´on. Tales sistemas observan las interacciones del usuario e infieren necesidades adicionales de informaci´on, buscando documentos relevantes en la Web u otras librer´ıas electr´onicas. Aprender mejores vocabularios es una manera de aumentar la percepci´on y la accesibilidad del material u ´til. Se propuso un m´etodo prometedor para identificar la necesidad detr´as de la consulta, lo cual es uno de los principales objetivos para muchos servicios y herramientas web actuales y futuras.

5.

Trabajo a futuro

Dentro de las limitaciones encontradas durante el desarrollo de esta tesis, la m´as importante result´o ser el tiempo de ejecuci´on de los algoritmos presentados. La velocidad es un obst´aculo muy grande a la hora de realizar una evaluaci´on con usuarios y es un aspecto a tener en cuenta a futuro. Por otro lado, el tiempo l´ımite de ejecuci´on podr´ıa incluirse como un par´ametro a ser definido por el usuario, indicando qu´e tanto est´a dispuesto a esperar por resultados o si en cambio, desea un determinado n´ umero de documentos novedosos sin importar el tiempo de espera. Otro aspecto que no fue abordado dentro de los objetivos y contribuciones de estas tesis es la determinaci´on del contexto actual del usuario, que tambi´en es de especial inter´es al momento de realizar las evaluaciones con usuarios. En lugar de esto, en las evaluaciones presentadas, se utiliz´o un conjunto de t´erminos extra´ıdos de una p´agina de un t´opico dado o la descripci´on de un t´opico realizada por un editor de una ontolog´ıa tem´atica. En la literatura existen diversos trabajos que abordan el tema del reconocimiento autom´atico del contexto actual de un usuario [2, 4, 3, 7]. Se est´a trabajando actualmente para aplicar el m´etodo propuesto para el aprendizaje de mejores vocabularios en otras tareas de IR, como la clasificaci´on de texto. Tambi´en se est´an analizando las distintas estrategias que ayudan a mantener al sistema enfocado en el contexto inicial, luego de que se han llevado a cabo varios pasos incrementales. Por otro lado, se espera adaptar la plataforma propuesta para evaluar otras aplicaciones de recuperaci´on de informaci´on, tales como algoritmos de clasificaci´on y clustering. Se ampliar´a la plataforma de evaluaci´on presentada en esta tesis con el prop´osito de ponerla a disponibilidad de la comunidad de IR, lo que resultar´a de gran utilidad a la comunidad cient´ıfica del ´area, provey´endola de una herramienta que permitir´a analizar de manera objetiva la efectividad de nuevos m´etodos. Entonces, se dise˜ nar´a un instrumento de evaluaci´on para sistemas de IR basado en un gran n´ umero de t´opicos y documentos obtenidos a partir de ontolog´ıas de t´opicos, para luego integrarlo con m´etodos de evaluaci´on existentes y novedosos. 7

2012

del ingl´es, Pointwise Mutual Information – Information Retrieval

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

840

En tal sentido ser´a importante el uso de las nociones de similitud sem´antica y relevancia parcial incorporadas a partir de esta tesis. La construcci´on de colecciones de prueba ha merecido especial atenci´on del ´ambito de la IR experimental, ya que analizar grandes colecciones de documentos y juzgar su relevancia es una tarea sumamente costosa, especialmente cuando los documentos cubren t´opicos diversos. A la luz de estas necesidades y dificultades, y a partir de ontolog´ıas de t´opicos editadas por humanos, tales como ODP, hemos desarrollado, y esperamos seguir refinando, un marco de experimentaci´on para la evaluaci´on autom´atica y semi-autom´atica de sistemas de IR, aprovechando el n´ umero masivo de relaciones disponibles entre t´opicos y documentos.

Agradecimientos El desarrollo de esta tesis fue financiado en su totalidad por el CONICET, dentro del Laboratorio de Desarrollo y Investigaci´on en Inteligencia Artificial (LIDIA), perteneciente al Departamento de Ciencias y Ingenier´ıa de la Computaci´on (DCIC) de la Universidad Nacional del Sur (UNS). Adem´as parcialmente por los siguientes proyectos: PICT 2005 Nro. 32373, TICsSinergia 2008, PGI-UNS 24/ZN13, PGI-UNS 24/N029, PIP N◦ 11220090100863. Algunos de los trabajos publicados se realizaron en conjunto con integrantes del Laboratorio de Investigaci´on y Desarrollo en Computaci´on Cient´ıfica (LIDeCC8 ) de la UNS.

Referencias [1] G. Amati and C. J. van Rijsbergen. Probabilistic models of information retrieval based on measuring the divergence from randomness. ACM Transactions on Information Systems (TOIS), 20(4):357–389, 2002. [2] M. Balabanovi´c, Y. Shoham, and Y. Yun. An Adaptive Agent for Automated Web Browsing. Technical report, Stanford University, Palo Alto, 1995. [3] T. Bauer and D. B. Leake. Wordsieve: A Method for Real-Time Context Extraction. En V. Akman, et. al., eds., Modeling and Using Context, vol. 2116 de Lecture Notes in Computer Science, pp. 30–44. 2001. [4] K. Bharat. Searchpad: explicit capture of search context to support web search. Computer Networks, 33(1-6):493–501, 2000. [5] B. Billerbeck, F. Scholer, H. E. Williams, and J. Zobel. Query expansion using associated queries. En Proceedings of the twelfth international CIKM, pp. 2–9, New York, 2003. ACM. [6] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7):107–117, 1998. [7] J. Budzik, S. Sood, K. J. Hammond, and L. Birnbaum. Context transformations for just-in-time retrieval: Adapting the watson system to user needs. Technical Report NWU-EECS-06-21, 2006. [8] R. L. Cecchini, C. M. Lorenzetti, and A. G. Maguitman. Algoritmos Gen´eticos para la B´ usqueda Web basada en Contextos tem´ aticos. En IX WICC, ASI, pp. 6–10, Trelew, Argentina, 2007. [9] R. L. Cecchini, C. M. Lorenzetti, and A. G. Maguitman. Evolving Disjunctive and Conjunctive Topical Queries based on Multi-objective Optimization Criteria. Inteligencia Artificial, 13(44):14–26, 2009. [10] R. L. Cecchini, C. M. Lorenzetti, and A. G. Maguitman. Multi–objective Query Optimization Using Topic Ontologies. En T. Andreasen, et. al., eds., Flexible Query Answering Systems, 8th Internat. Conference, vol. 5822 de Lecture Notes in Computer Science, pp. 145–156, Roskilde, Denmark, 2009. Springer. [11] R. L. Cecchini, C. M. Lorenzetti, and A. G. Maguitman. A Multi-objective Evolutionary Algorithm Approach to Learn Disjunctive and Conjunctive Topical Queries. En 38◦ Jornadas Argentinas de Inform´ atica e Investigaci´ on Operativa (JAIIO), ASAI, pp. 25–36, Mar del Plata, 2009. [12] R. L. Cecchini, C. M. Lorenzetti, A. G. Maguitman, and N. B. Brignole. Genetic Algorithms for Topical Web Search: A Study of Different Mutation rates. En XIII CACIC, pp. 1585–1595, Corrientes, 2007. 8

2012

http://lidecc.cs.uns.edu.ar

XIV Workshop de Investigadores en Ciencias de la Computación

WICC 2012

841

[13] R. L. Cecchini, C. M. Lorenzetti, A. G. Maguitman, and N. B. Brignole. Searching the Web in Context: Genetic Algorithms for Exploring Query space. En 36◦ Jornadas Argentinas de Inform´ atica e Investigaci´ on Operativa, SSI, pp. 183–195, Mar del Plata, 2007. [14] R. L. Cecchini, C. M. Lorenzetti, A. G. Maguitman, and N. B. Brignole. Using genetic algorithms to evolve a population of topical queries. Information Processing and Management, 44(6):1863–1878, 2008. [15] R. L. Cecchini, C. M. Lorenzetti, A. G. Maguitman, and N. B. Brignole. Multi-objective Evolutionary Algorithms for Context-based Search. Journal of the American Society for Information Science and Technology, 61(6):1258–1274, 2010. [16] R. L. Cecchini, C. M. Lorenzetti, A. G. Maguitman, and F. Menczer. A semantic framework for evaluating topical search methods. CLEI Electronic Journal, 14(1):13–27, 2011. [17] C. I. Ches˜ nevar, C. M. Lorenzetti, A. G. Maguitman, F. M. Sagui, and G. R. Simari. Exploiting User Context and Preferences for Intelligent Web Search. En Proceedings of the WICC, Mor´on, 2006. [18] W. W. Cohen. Learning rules that classify e-mail. En M. A. Hearst and H. Hirsh, eds., AAAI Spring Symposium on Machine Learning in Information Access, pp. 18–25, 1996. [19] S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41(6):391–407, 1990. [20] G. W. Furnas, S. C. Deerwester, S. T. Dumais, T. K. Landauer, et. al.. Information retrieval using a singular value decomposition model of latent semantic structure. En Proceedings of the 11th annual int. ACM SIGIR conf. on Research and development in IR, pp. 465–480, New York, 1988. ACM. [21] A case-based approach to knowledge navigation. En U. M. Fayyad, et. al., eds., Proceedings of the Workshop on KDD, pp. 383–394. AAAI Press, 1994. [22] W. P. Jones. On the applied use of human memory models: the memory extender personal filing system. International Journal of Man-Machine Studies, 25:191–228, 1986. [23] M. Lamming and M. Flynn. Forget-me-not: intimate computing in support of human memory. En FRIEND21: Symposium on Next Generation Human Interfaces, pp. 125–128, Meguro Gajoen, Japan, 1994. [24] K. Lang. NewsWeeder: Learning to Filter Netnews. En A. Prieditis and S. J. Russell, eds., Proceedings of the Twelfth International Conference on Machine Learning, pp. 331–339. Morgan Kaufmann, 1995. [25] C. M. Lorenzetti, R. L. Cecchini, and A. G. Maguitman. Intelligent Methods for Information Access in Context: The Role of topic descriptors and discriminators. En XIII CACIC, pp. 1608–1619, 2007. [26] C. M. Lorenzetti and A. G. Maguitman. Learning Better Context Characterizations: An Intelligent Information retrieval approach. En XXXIV Conferencia Latinoamericana de Inform´ atica, pp. 200–209, 2008. [27] C. M. Lorenzetti and A. G. Maguitman. Tuning Topical Queries through Context Vocabulary Enrichment: A Corpus-based approach. En R. Meersman, et. al., eds., On the Move to Meaningful Internet Systems: OTM 2008 Workshops, vol. 5333 de Lecture Notes in Computer Science, pp. 646–655. Springer, 2008. [28] C. M. Lorenzetti and A. G. Maguitman. A semi-supervised incremental algorithm to automatically formulate topical queries. Information Sciences, 179(12):1881–1892, 2009. [29] C. M. Lorenzetti, F. M. Sagui, A. G. Maguitman, C. I. Ches˜ nevar, and G. R. Simari. Incremental Methods for Context-based Web Retrieval. En XII CACIC, pp. 1243–1254, San Luis, 2006. [30] P. Maes. Agents that reduce work and information overload. Communicat. of the ACM, 37(7):30–40, 1994. [31] A. G. Maguitman, D. B. Leake, T. Reichherzer, and F. Menczer. Dynamic Extraction of Topic Descriptors and Discriminators: Towards Automatic Context-Based Topic Search. En Proceedings of the Thirteenth CIKM, pp. 463–472, Washington, 2004. ACM Press. [32] O. A. McBryan. GENVL and WWWW: Tools for Taming the Web. En First International Conference on the World Wide Web, Geneva, Switzerland, 1994. CERN. [33] F. Scholer and H. E. Williams. Query Association for Effective Retrieval. En Proceedings of the eleventh international CIKM, pp. 324–331, New York, 2002. ACM. [34] P. D. Turney. Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL. En L. De Raedt, et. al., eds., Proceedings of the 12th European Conf. on M.L., pp. 491–502, London, UK, 2001. Springer-Verlag.

2012

XIV Workshop de Investigadores en Ciencias de la Computación