1 Universidad de Chile Facultad de Ciencias Físicas y Matemáticas Departamento de Ciencias de la Computación Charla Tesis I Magíster en Ciencias mención computación "Estimación de Confiabilidad de Sucesos Futuros Extraídos desde Fuentes de Noticias y su Utilización en un Motor de Búsqueda” Iván M. Rivera Jofré Profesor Guía: Dr. Ricardo Baeza-Yates Marzo 2006

2 Contenido de la Charla Motivación y Objetivos Descripción del Proceso Trabajo Previo Desarrollo Prototipo

3 El futuro… El 9 de Junio del año 2006 comienza el XVIII Campeonato Mundial de Fútbol, en Alemania El año 2009 estará disponible una vacuna contra la Malaria En el año 2011 se cierra la línea de explotación de sulfuros en la mina de El Salvador 07/07/2007: Se publica la séptima y última entrega de la serie de libros Harry Potter 11 de Julio de 2010. Eclipse Total de Sol en la Isla de Pascua. Hora: 16:10:57. Duración 4 minutos 44 segundos En el primer trimestre de 2006, Sky Airlines iniciará 7 vuelos semanales a Madrid

4 Motivación Toda esta información fue extraída de la Web. Sin embargo, no es simple llegar a esta información, debo saber dónde buscar y prácticamente saber qué es lo que busco.

5 Motivación Conocer sucesos del futuro puede influir en: una decisión de inversión un programa político un viaje una planificación de un evento una postulación a un trabajo etc. Pero además se requiere saber qué tan confiable es la información

6 Oportunidad Recuperar desde fuentes confiables en la Web, información sobre eventos futuros y su contexto. Catalogarlos e indexarlos. Incorporar este índice de eventos futuros en un motor de búsqueda permitiendo la búsqueda por contenido o por fecha o lapso de tiempo

7 Ejemplo Query: materia: "cobre Chile", periodo: "hoy – 2015" - Cierre de planta de sulfuros de El Salvador para el año 2011 - El año 2013 se inicia el Proyecto Chuquicamata Subterránea - La producción de cobre chileno se expandirá 26% al año 2012 - Codelco comienza la explotación de la mina Gaby el próximo año - Codelco aumentará la inversión a 1.7 billones de US$ este año - En Octubre, el precio del cobre caerá a US$1.25 … más otros 50 eventos aproximadamente

8 Recuperación del Futuro En "Searching the future" (Baeza-Yates, 2005) se define el problema "Recuperación del Futuro". Recuperar información descriptiva de eventos que tienen asociada una ubicación temporal en el futuro, desde artículos de noticias, para luego utilizarlos en un sistema de Recuperación de Información que responda a consultas que combinen texto y tiempo. Se reformula el ordenamiento de los resultados recuperados definiendo un nivel de confiabilidad (estimación numérica) para cada uno de estos eventos R. Baeza-Yates. "Searching the future". ACM SIGIR Workshop MF/IR 2005.

9 Objetivo de la Tesis Obtener una implementación de un sistema de Recuperación del Futuro y un algoritmo de estimación de un coeficiente de confiabilidad de un documento basado en técnicas de Procesamiento de Lenguaje Natural, con el fin de que este coeficiente se incluya en un algoritmo de ordenamiento de resultados de un sistema de Recuperación de Información

10 News Downloading News Text Extraction Temporal Entities Detection & Annotation Inverted Index Time Segments Index SearchEngine Ranking Calculation Confidence Level Calculation Confidence Level: 45 % Future Events Extraction Future events Event Index

11 Antecedentes Extracción de Información (Information Extraction, IE) - Se enfoca en encontrar información específica en documentos relativamente no estructurados - Típicamente se reconocen ciertos patrones lingüísticos y se procesan. Además el análisis no se realiza sobre todo el documento, sino que en forma parcial.

12 Proceso: recuperación del texto El proceso se inicia con la recuperación de artículos de noticias (típicamente páginas HTML). Problemas: Texto del artículo no viene incluido en RSS Editores dificultan la extracción de texto Comentarios de lectores a veces más extensos que el artículo Límites del texto difícil de detectar Extracción de Fecha de Publicación

13 Una expresión temporal se define como trozos de texto que expresan alguna información temporal explícita o inferida. Ejemplos: Proceso: Extracción de Expresiones Temporales  In July  Next day after the meeting  In several weeks  Friday at noon  Next Winter  Before Christmas  During the World Cup  October 15th, 2006  13/03/2006 3 p.m.  On Sunday  This Week-end  Next year  2007-2008  Tomorrow

14 Las expresiones temporales pueden clasificarse en: Explícitas October 24th 2007 03-13-2006 Relativas Tomorrow next Monday next Year Vagas after Christmas in several weeks by the end of the day Tipos de Expresiones Temporales

15 Resolución de Expresiones Temporales Un aproximación es utilizando expresiones regulares. Por ejemplo, si se considera: CategoríaTérminos basetermday, week, weekday, month, monthname, quarter, season, year, decade indexicalyesterday, today, tomorrow internalbeginning, end, early, late, middle determinerthis, last, next, previous, the temporalin, on, by, during, after, until, since, before, after postmodifierof, to numeralone, two, … ordinalfirst, second, …

16 Reconocimiento de Expresiones Temporales Este autómata permite encontrar diversas expresiones que incluyen el mes, por ejemplo: "by August 14th, 2006"

17 Resolución de Expresiones Temporales Una vez detectada la expresión temporal se debe encontrar la fecha o período al que hace referencia si es que la expresión no fuese explícita. Reglas: "tomorrow"  "next week"  fecha actual + 1 día Periodo : [ primer día próxima semana; último día próxima semana], / fecha_actual = '17/03/2006'

18 Definiciones Sea t un instante, definido como un elemento dentro de un conjunto de instantes T, línea de tiempo global. Un intervalo  t i, t k   T, t i < t k es un conjunto de instantes {  t j, t j  | i ≤ j ≤ k }

19 Definiciones Sea G una granularidad, definida como una unidad básica de tiempo para un calendario dado. Por ejemplo, en el calendario gregoriano es posible definir las granularidades: G year, G month, G week, G day En un contexto financiero se puede definir una granularidad: G quarter En un contexto deportivo se puede definir una granularidad: G season

20 Definiciones Sea C un calendario, definido como una tripleta donde: T es la línea de tiempo global de C,  es el conjunto de granularidades de C,  es un conjunto de funciones de conversión entre las granularidades. Por ejemplo, en un calendario gregoriano, las funciones de  permiten definir cuántos días tiene un mes, o cuántos meses un año.

21 Definiciones Las funciones de conversión de son del tipo: f C G 1  G 2 (i 1, i 2, …)  N G 2 Por ejemplo: f C G month  G day (2006, 3)  31 f C G month  G day (2006, 2)  28 f C G year  G day (2006)  365 f C G year  Gmonth (2006)  12

22 Definiciones  : G  T  T Retorna el punto de inicio de un elemento de granularidad G  : G  T  T Retorna el punto de inicio del siguiente elemento de granularidad G  L : G  IN  T  T Retorna el instante desplazado hacia la izquierda en la línea del tiempo en n unidades de la granularidad G  R : G  IN  T  T Retorna el instante desplazado hacia la derecha en la línea del tiempo en n unidades de la granularidad G

23 Ejemplos Si t r es la fecha actual  (G week, t r ) = 03-13-2006  (G month, t r ) = 04-01-2006  (G tuesday, t r ) = 03-21-2006  (G quarter,  (G month, t r ) ) = 07-01-2006  R (G day, 1, t r ) = 03-18-2006 tomorrow

24 Resolución de expresiones temporales utilizando funciones matemáticas Expresión: "en tres meses más" Fecha de Referencia: 2006-03-17  R (G month, 3, t r ) = =  R (G day,  f C G month  G day (y( t r ), m( t r ) + k), t r ) =  R (G day, (31 + 30 + 31), t r ) = 2006-06-17 2 k=0

25 Tagging de expresiones temporales Terminada a la resolución de las expresiones temporales, se suele anotar cada una de estas fechas o duraciones en el texto, para su posterior análisis. Existen especificaciones de anotación de expresiones temporales (fechas, períodos y duraciones): TIMEX, TIMEX2, TIMEX3, TimeML

26 Ejemplo "The draw at the FIFA Congress in August will determine whether Australia plays the home or away leg first in its critical World Cup playoffs against the fifth-placed South American team. Australia has been given permission to quit the Oceania Football Confederation (OFC) and join the Asian Football Confederation (AFC) from January 1st next year.”

27 "The draw at the FIFA Congress in August will determine whether Australia plays the home or away leg first in its critical World Cup playoffs against the fifth-placed South American team. Australia has been given permission to quit the Oceania Football Confederation (OFC) and join the Asian Football Confederation (AFC) from January 1st next year.” Ejemplo

28 Extracción de Información del Evento: Procesamiento de Lenguaje Natural (NLP) El paso siguiente a la detección de la expresión temporal es la extracción del evento futuro en sí. La complejidad radica es que el evento es descrito en lenguaje natural. Ejemplos: "New Horizons was launched on Jan. 19, 2006, and will fly through the Pluto system in July 2015" "Troops on alert as protesters go on march"

29 NLP 2 enfoques Simbólico Consiste de un conjunto de reglas para la manipulación de símbolos e.g. reglas gramaticales Análisis estadístico del lenguaje: Empírico Implica obtener un modelo del lenguaje desde grandes recopilaciones de texto (corpora), tales como fuentes de noticias o páginas Web

30 NLP Para extraer la descripción del evento mismo, se requiere conocer las partes básicas de una oración. El sujeto y el predicado. Se requiere reconocer de qué clase léxica es cada una de las palabras de la oración. (En inglés: Part of Speech) "New Horizons will fly through the Pluto system in July 2015" PROP NOUNAUX + VERBDET + NOUN + NOUNPREP+NOUN+ #

31 Part-Of-Speech (POS) Tagging El objetivo de este proceso es etiquetar cada palabra. Sin embargo, el conjunto de posibles clases léxicas o Part-Of-Speech puede variar. Sustantivo, Verbo, Adverbio, Adjetivo Nombres Propios, Preposición, Artículo, Pronombre, Conjunciones, Verbos Auxiliares, Numerales Para este proceso se requiere escoger un conjunto estándar de tags para trabajar. El más común es "UPenn Treebank tagset", que define 45 tags

32 Ejemplo de POS-tagging Troops on alert as protesters go on march Troops/NN on/IN alert/NN as/IN protesters/NN go/VB on/IN march/NN

33 POS-Tagging Básicamente existen 2 enfoques para resolver este problema: Simbólico: Aplicando reglas Estocástico: Utilizando un modelo probabilístico del lenguaje (e.g.: Hidden Markov Model)

34 POS-tagging mediante reglas Cada palabra la etiqueto con todos los posibles tags que puede tener. Estas posibles etiquetas las obtengo de un diccionario (lexicon). Aplicando reglas (típicamente gramaticales), se decide cuál es la etiqueta correcta. IPRP promiseVB NN itPRP Regla: después de un PRP no puede haber un NN

35 POS-tagging mediante probabilidades Cada palabra la etiqueto según un criterio probabilístico, e.g. ¿cuál es el tag más probable? theDET raceVB NN beganVBN En un corpus dado, "race" es 90% de las veces un sustantivo, y 10% un verbo

36 POS-tagging Utilizando Hidden Markov Models, es posible revisar la probabilidad de ocurrencia de un posible tag conociendo el tag anterior.. Por ejemplo, dado un artículo (the) un modelo de markov predice que la siguiente palabra es un sustantivo con un 40% de probabilidad, un adjetivo con 40% y un número con 20%.

37 POS-tagging No sólo puede conocer la probabilidad del tag precedente, sino que 2 ó 3 ó más tags: bi-gram tri-grams N-grams Estas probabilidades se obtienen calculándolos desde un corpus existente.

38 Extracción del Evento Una vez identificado el Part-Of-Speech de cada palabra, se procede a recuperar la descripción del evento. Se requiere entre otras cosas el sujeto o los sujetos del evento, el verbo y otras posibles descripciones esenciales de cada evento: July 2015: "New Horizons flies through Pluto system"

39 Extracción del Evento La información puede ser extraída aplicando expresiones regulares para detectar expresiones sin mayor dificultad gramatical, por ejemplo: NOUN + VERB NOUN + VERB + NOUN DET + NOUN + VERB + ADVERB + NOUN Etc. Para ello es posible utilizar Autómatas Finitos, el cual ha alcanzado niveles de reconocimiento y precisión de alrededor 70%.

40 Ejemplo de Autómata Finito No determinístico "… the Pluto System …" DET + NOUN + NOUN "… the small planet …" DET + ADJ + NOUN s1s1 s2s2 s3s3 NOUN ADJ DETNOUN NG

41 Extracción del Evento "Codelco, which is owned by Chilean government, will increase his production in 23%" NG RELPRO VG* donde RELPRO calza con los pronombres relativos "who" y "which" Cada evento puedo describirlo en forma sencilla en base al sujeto (NG) y la acción en el evento (VG)

42 Extracción del Evento Lamentablemente algunas oraciones en inglés requieren un procesamiento más profundo y que ya no puede ser procesado por expresiones regulares. Un análisis con Gramáticas Libres de Contexto es más complejo pero permite procesar una mayor cantidad de expresiones. Por ejemplo, puedo definir un Noun Group (NG): NG = DET + NOUN NG = DET + ADJ + NOUN NG = NG + PREP + NG

43 Plantillas de Eventos Una manera de describir un evento es con uso de plantillas Evento 5758 Fecha Evento Fecha Extracción Duración Sujeto New Horizons Predicado flies through Pluto system Modificadores Fuente http://www.universetoday.com/am/publish/pluto_moons_born_together. html?1332006

44 Plantillas de Eventos Una ventaja del uso de plantillas es que un evento puede definirse aún sin llenar todos los posibles campos de la plantilla. Si un mismo evento es descrito en otra fuente, generará una plantilla distinta, pero con algunas coincidencias. Realizando un proceso de "merge" de plantillas se facilita el seguimiento de eventos, identificación de un mismo evento y complemento de información

45 Template Merge Fecha Evento Sujeto New Horizons Predicado flies through Pluto system Fuente http://www.universetoday.com/am/publi sh/pluto_moons_born_together.html?1 332006 Fecha Evento Duración Sujeto A spacecraft Predicado flies by Pluto Fuente http://www.spaceref.com/news/viewsr.ht ml?pid=19795 merge Fecha Evento Duración Sujeto New Horizons Predicado flies by Pluto Fuente http://www.spaceref.com/news/viewsr.ht ml?pid=19795 http://www.universetoday.com/am/publis h/pluto_moons_born_together.html?133 2006

46 Aprovechando conocimiento del dominio del evento El proceso completo hasta ahora puede mejorarse aprovechando cierta información del dominio de los eventos Part-of-Speech más refinados: gun, grenade, missile, bomb /WEAPON man, woman, child, kid, boy /PEOPLE dollar, peso, GBP, euro /CURRENCY

47 Aprovechando conocimiento del dominio del evento El reconocimiento de patrones lingüísticos puede reconocer reglas del dominio: COMPANY SET-UP JOINT-VENTURE with COMPANY (en vez de NOUN VERB NOUN ADV NOUN) NOUN attacked PEOPLE with DEVICE SPACECRAFT will be launched TEMPORAL from PLACE STOCKQUOTE price TREND to CURRENCY QUANTITY

48 Aprovechando conocimiento del dominio del evento Plantillas más apropiadas al dominio: Evento Deportivo 00263 Fecha Evento Fecha Extracción Deporte Fútbol Competidor Alemania Competidor Costa Rica Torneo Copa Mundial de Fútbol FIFA Lugar Berlin, Alemania

49 Topic Clustering Para lograr una extracción de eventos adaptada al dominio, se requiere conocer a priori el tópico del evento. Antes de realizar el proceso completo se puede clasificar cada documento según su tópico en clusters. deporte economía política

50 Confiabilidad de información sobre el futuro No es factible predecir con certeza que un evento ocurrirá en el futuro. Pero si se puede definir que un evento es más confiable que otros según algunos criterios estadísticos y heurísticas

51 Confiabilidad Cantidad de Referencias: Si un evento es descrito por muchas fuentes de información, es más confiable que otro que aparece en un sola fuente. Tópico del Evento: Eventos de ciertos tópicos tienen una mayor probabilidad de ocurrencia por naturaleza, e.g.: suceso astronómico v/s precio de una acción

52 Confiabilidad Historial del predictor: Eventos pronosticados por una fuente que en promedio predice eventos correctos es más confiable que otros. Morfología utilizada: Si la descripción del evento puede clasificarse como un anuncio formal o una afirmación, es más confiable que una opinión personal o una pregunta.

53 Confiabilidad Eventos en conflicto: Si un evento tiene conflicto con otro, o es la negación de otro evento, entonces ambos tienen baja confiabilidad. Eventos obsoletos: Si un evento baja drásticamente su frecuencia de aparición, entonces su confiabilidad también baja.

54 Confiabilidad Eventos dependientes: Si la ocurrencia de un evento depende de un evento previo, su confiabilidad debe ser similar a la de éste. Cercanía al Evento: Eventos lejanos en el tiempo son menos confiables que los más cercanos.

55 Nivel de Confiabilidad El nivel de confiabilidad de un evento es una estimación de la probabilidad de que el evento ocurra en el tiempo pronosticado. Este nivel puede ser en un dominio discreto y/o cualitativo (e.g. alta, media, baja) ó en una escala numérica (1.0 = certeza absoluta  0.0= indeterminado)

56 Persistencia de un evento Un evento será procesado y anexado al sistema, pero ¿por cuánto tiempo estará vigente? Hasta que llegue la fecha del evento Hasta que la confiabilidad de un evento sea menor a un umbral predeterminado Hasta que un evento nuevo implique su cancelación (confiabilidad  0)

57 Nivel de Confiabilidad Dado un evento e Sea T e el tópico del evento Sea N e la cantidad de artículos desde donde se menciona este mismo evento Sea De el conjunto de eventos de los cuales depende Sea Ae el conjunto de agentes que pronosticaron el evento

58 Nivel de Confiabilidad: 0 ≤ γ ( e ) ≤ 1 γ ( e ) ~ max ( γ ( Ae ) ) * min ( γ ( De ) ) * ( 1 - ) * γ ( Te ) * ( 1 – max γ ( Ee ) ) 1 NeNe i i confiabilidad de quien predice confiabilidad de eventos de los que depende cantidad de menciones confiabilidad del tópico confiabilidad del eventos contradictorios o en conflicto

59 Otros criterios de Confiabilidad Cercanía al evento γ ( Te )  γ ( Te, t e – t ref ) Morfología utilizada γ ( Verbos(e ) ) = ∏ γ ( Vi ) Vi  Verbos(e ) Obsolescencia γ ( e ) ~ (t today - max(t ref ) ) -1

60 Ordenamiento de Resultados Una vez determinada la confiabilidad de los eventos extraídos, en un algoritmo de ranking de resultados tras una query (de texto y tiempo): Aquellos eventos más confiables aparecerán sobre los menos confiables Si un documento incluye varios eventos de distinta confiabilidad, su relevancia puede estimarse según la confiabilidad de los eventos que coinciden con el segmento de tiempo requerido (periodo)

61 Prototipo http://www.dcc.uchile.cl/~irivera/prototipo

62 Fin de la Presentación ¿ Preguntas ?

63

64 volver

65