TRANSFORMACIÓN AUTOMÁTICA DE TEXTO A GRAFOS CONCEPTUALES Sonia Ordoñez Salinas Universidad Nacional de Colombia Facultad Ingenieria, Departamento de Sistemas e Industrial Doctorado en Ingeniería Sistemas y Computación Ciudad, Colombia 2011 TANSFORMACIÓN AUTOMÁTICA DE TEXTO A GRAFOS CONCEPTUALES Sonia Ordoñez Salinas Tesis o trabajo de investigación presentada como requisito parcial para optar al título de: Doctor en Ingnería de Sistemas y Computación Director: Ph.D., Alexander Gelbukh Línea de Investigación: Procesmiento de Lenguaje Natural y Lingüística Computacional Universidad Nacional de Colombia Facultad Ingeniería, Departamento Sistemas e Industrial Doctorado en Ingeniería de Sistemas y Computación Ciudad, Colombia 2011 A quienes me han apoyado incondicional- mente, mi compañero y amigo de vida Alvaro, mis adorados hijos Sebastian y Laura, a mi amada madre y hermanos. Agradecimientos VI Agradecimientos Agradezco la asesoría y colaboración del profesor Alexander Gelbukh, director del proyecto, ya que sin su ayuda no hubiera sido posible la realización de esta investigación. Quiero de manera especial resaltar su empeño y dedicación hacia la investigación y la transmisión del conocimiento. De manera muy especial quiero reconocer el gran apoyo brindado por el profesor Luis Fernando Niño, quien con su desinteresada colaboración a todos los estudiantes ha permitido la consolidación del doctorado y los procesos de investigación en la Universidad. De igual forma agradezco el cuerpo de Docentes entre los que me gustaria destacar al profesor Fabio Gonzalez. Quiero hacer extensivo estos agradecimientos al cuerpo administrativo de la facultad y de la Universidad en General. Por último quiero expresar mi sentido de gratitud a la Universidad Distrital F.J.C por la comisión de estudios que me fue otorgada y que me permitió dedicarme a desarrollar esta investigación y al Instituto Politécnico Nacional de México por permitirme realizar la pasantía. Resumen y Abstract VII Resumen Dentro de las estructuras computacionales utilizadas para el procesamiento del lenguaje natural, se encuentran los grafos conceptuales (GCs) que por sus ventajas se pueden convertir en un instrumento eficiente para la representación formal del significado del texto. Usualmente los GCs son creados utilizando una estructura sintáctica que es modificada hasta obtener los GCs, lo que involucra dos procesos costosos: el análisis sintáctico y la transformación al los GCs. Esta tesis propone dos soluciones más simples para la transformación directa de texto a grafos conceptuales, sin involucrar una estructura intermedia. Una solución es a través de la construcción de una gramática especializada. Dicha gramática se crea de forma automática a partir de un recurso léxico existente construido para otro fin. Otra solución propuesta, es a través del desarrollo de un analizador sintáctico basado en un método estadístico no supervisado y pobre en conocimiento. El método usa las estadísticas de coocurrencia de las palabras en un corpus grande (o en Internet) y permite obtener estructuras simplificadas de GCs. Cabe mencionar que para su entrenamiento no se requiere ningún trabajo manual previo ya que se basa en un corpus no preparado, más aún, sólo se requieren las estadísticas de coocurrencia y no se requiere el acceso al corpus mismo, lo que es importante en el caso del uso de los motores de búsqueda en Internet como la fuente de información estadística. Palabras clave: Procesamiento de lenguaje natural, Lingüística computacional, Grafos conceptuales, Análisis sintáctico no supervisado, Gramática especializada. VIII Transformación automática de texto a Grafos conceptuales Abstract One of the computational structures used in natural language processing is the Conceptual Graphs (CGs), which thanks to their advantages can become an efficient tool for formal representation of the meaning of the text. GCs are usually created using some syntactic structure that is modified to obtain the CGs. This involves two costly processes: parsing and transformation to the CGs. This thesis proposes two simpler solutions for converting text to conceptual graphs directly, without involving an intermediate structure. One solution is through the construction of a specialized grammar. This grammar is automatically created from an existing lexical resource that has been built for another purpose. The other proposed solution is through the development of a parser based on a knowledge-poor unsupervised statistical method. The method uses co-occurrence statistics of words in a large corpus (or Internet) and generates simplified CG-like structures. It should be mentioned that the training process does not require any previous manual work because it is based on a raw text corpus. Moreover, it only requires the co-occurrence statistics and does not require access to the corpus itself, which is important for the use of Internet search engines as the source of statistical information. Keywords: Natural language processing, Computational linguistics, Conceptual graphs, unsupervised parsing, Specialized grammar. Contenido IX Contenido 1.INTRODUCCIÓN 1 1.1 HIPÓTESIS _______________________________________________________________________________________ 2 1.2 ESTRUCTURA DEL DOCUMENTO ___________________________________________________________________ 3 2.ESTADO DEL ARTE Y MARCO TEÓRICO 4 2.1 ESTRUCTURAS COMPUTACIONALES EN EL PLN _____________________________________________________ 5 2.1.1 Estructuras básicas ........................................................................................................................... 5 2.1.2 Estructuras avanzadas ...................................................................................................................... 8 2.1.3 Estructuras conceptuales estandarizadas ........................................................................................ 11 2.2 GRAFOS CONCEPTUALES (GCs) ____________________________________________________________________ 16 2.2.1 Características de los GCs ............................................................................................................. 16 2.2.2 Herramientas para generar grafos conceptuales ............................................................................. 17 2.2.3 Recuperación automática de grafos conceptuales .......................................................................... 22 3.MÉTODO BASADO EN REGLAS SINTÁCTICAS Y SEMÁNTICAS 25 3.1 INTRODUCCIÓN __________________________________________________________________________________ 25 3.2 TRABAJO PREVIO ________________________________________________________________________________ 25 3.2.1 La tarea principal no corresponde a la Creación de los GC ........................................................... 26 3.2.2 La tarea es restringida a un vocabulario controlado ....................................................................... 26 3.2.3 Se crean reglas sobre estructuras sintácticas .................................................................................. 27 3.2.4 Uso de recursos .............................................................................................................................. 27 3.3 TRABAJO PROPUESTO ____________________________________________________________________________ 27 3.3.1 Los grafos conceptuales y las estructuras sintácticas ..................................................................... 28 3.3.2 Gramática para los grafos conceptuales (gramática-GC) ............................................................... 33 3.3.3 Parsing cic-ipn ............................................................................................................................... 38 3.3.4 Validación los grafos conceptuales ................................................................................................ 40 X Trasnformación automática de texto a grafos conceptuales 4.MÉTODO ESTADÍSTICO NO SUPERVISADO 47 4.1 “PARSING” PROBABILÍSTICOS ____________________________________________________________________ 47 4.1.1 Modelo de Caroll y Charniak ........................................................................................................ 48 4.1.2 Modelo de Paskin y Yuret ............................................................................................................. 49 4.1.3 Modelo de Klein y Mannning ........................................................................................................ 49 4.2 LAS ESTRUCTURAS DE DEPENDENCIA Y LOS GRAFOS CONCEPTUALES _______________________________ 49 4.3 ASOCIACIONES POR CO-OCURRENCIAS ____________________________________________________________ 51 4.4 ESTRUCTURA SIMPLIFICADA DE GRAFOS CONCEPTUALES __________________________________________ 52 4.5 PARSING PARA GENERAR UNA ESTRUCTURA SIMPLIFICADA DE GC __________________________________ 56 4.5.1 Método ........................................................................................................................................... 56 4.5.2 Algoritmo voraz ............................................................................................................................. 58 4.5.3 Resultados experimentales del parsing .......................................................................................... 58 5.RESULTADOS DE LA INVESTIGACIÓN 60 5.1 CONCLUSIONES Y TRABAJO FUTURO ______________________________________________________________ 60 5.2 APORTES _______________________________________________________________________________________ 60 5.3 PRODUCTOS ENTREGABLES ______________________________________________________________________ 61 5.4 PUBLICACIONES _________________________________________________________________________________ 62