Repositorio Institucional de Documentos

Universidad de Zaragoza Departamento de Informática e Ingeniería de Sistemas Aplicación de las 2-estructuras a las gramáticas del lenguaje humano y representación gráfica de ambas Proyecto Fin de Carrera Ingeniería en Informática Autor: Daniel Larraz Hurtado Directora: Elvira Mayodormo Cámara Centro Politécnico Superior Agosto de 2010 Curso 2009-2010 I Agradecimientos Este trabajo representa el fin de una etapa en mi vida. Durante ella he tenido la gran suerte de convivir con un grupo de compañeros excepcionales con los que he compartido miles de momentos innolvidables. Su compañía ha hecho del camino recorrido un auténtico placer. No voy a intentar nombrarles a todos, pues son muchos y existe el peligro de omitir a alguno. Confio en que ellos sepan quiénes son. Sin embargo, estoy seguro de que comprenderan el hecho de que haga una excepción y mencione de manera especial a mi gran amigo, y compañero de prácticas durante casi toda la carrera, Santiago. Durante todo este tiempo Santiago ha sido para mí un referente por su pasión y por su buen hacer tanto en el ámbito académico como en el personal. Le doy mil gracias por su fantástica compañía a largo de estos cinco años. Por motivos similares a los esgrimidos previamente tampoco voy a hacer una lista de profesores, de los que en gran parte guardo muy buen recuerdo y con los que he aprendido mucho. No obstante, debo agradecer la confianza, la libertad y el apoyo que he recibido por parte de Elvira Mayordomo para desarrollar este proyecto. Por último, y no por ello en menor grado de importancia sino todo lo contrario, no tengo palabras para expresar mi gratitud por todo lo que les debo a mis padres, Pedro y Asun, y mi novia, Natalia, que han estado a mi lado compartiendo todas mis alegrías y penas y haciendo de mí lo que soy. Sin ellos, el inminente ingeniero en informática que suscribe estas líneas no sería nada. A ellos les dedico este trabajo. II III Aplicación de las 2-estructuras a las gramáticas del lenguaje humano y representación gráfica de ambas Resumen La teoría de las 2-estructuras [5] proporciona una infraestructura matemática para la descomposición y la transformación de grafos. Se trata de un formalismo muy potente y robusto que permite representar múltiples grafos en una sola estructura algebraica, una 2-estructura, y derivar de ella una descomposición única en 2-estructuras más simples. En este proyecto se ha llevado a cabo su estudio con dos finalidades: −El diseño y la implementación de un paquete de software que sistematice el análisis, la transformación y la visualización de las principales estructuras involucradas en la teoría de las 2-estructuras. −La investigación y el desarrollo de posibles aplicaciones de las 2-estructuras a las gramáticas usadas en el procesamiento del lenguaje humano (lenguaje natural). El lenguaje natural es casi en cualquier aspecto más complejo de lo esperado [6]. La sintaxis de muchos idiomas incluye reglas gramaticales que son sensibles al contexto, fenónemos cuyo procesado está muy lejos de tener soluciones eficientes (recordemos que los compiladores de lenguajes de programación sólo procesan un subconjunto muy simple de las gramáticas completamente libres del contexto y que el procesado de gramáticas sensibles al contexto es en general inviable). Las gramáticas suavemente sensibles al contexto (Mildly Context Sensitive Grammars, MCSG) pretenden capturar la sintaxis del lenguaje natural y conseguir su procesado eficiente [7,9]. Entre los lenguajes que describen estas gramáticas encontramos una subclase de gran interés por los siguientes tres motivos. Los lenguajes que contiene capturan un amplio espectro de las dependencias del lenguaje natural, son reconocibles en tiempo polinómico y existen cuatro formalismos independientes entre sí que los generan [8]. Son los lenguajes descritos por las grámaticas de adjunción de árboles (Tree Adjoining Grammars, TAG), las gramáticas de núcleo (Head Grammars, HG), las gramáticas lineales de índices (Linear Indexed Grammars, LIG) y las gramáticas categoriales combinatorias (Combinatory Categorial Grammars, CCG). En este trabajo se presentan dos resultados producto de la investigación sobre la aplicación de las 2-estructuras a algunas de las gramáticas mencionadas: −Una extensión de las HG que asocia explícitamente un árbol derivado a las cadenas generadas apoyándose en las bases de las 2-estructuras. −Un algoritmo que genera una gramática TAG a partir de una frase con dependencias anidadas y cruzadas (las capturables por el formalismo). IV V Índice 1.Introducción .............................................. 1 1.1. Objetivos y alcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Trabajo previo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Métodos, técnicas y herramientas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5. Organización de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Desarrollo del paquete de software . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1. Análisis y diseño de las 2-estructuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2. Controles gráficos para la visualización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3. Arquitectura y diseño del programa interactivo . . . . . . . . . . . . . . . . . . . . 10 3. Asociación de un árbol derivado a las cadenas generadas porunagramáticaHG ..................................... 13 3.1. Extensión de las gramáticas de núcleo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Ejemplo ilustrativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4. Generación de una gramática TAG a partir de una frase condependencias ......................................... 21 4.1. Definición de un árbol de dependencias . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2. División del problema en dos casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3. Método para generar un árbol de dependencias simple . . . . . . . . . . . . . . 23 4.4. Método para generar un árbol de dependencias complejo . . . . . . . . . . . . 24 5.Conclusiones ............................................. 29 5.1. Resultados del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3. Valoración personal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 VI .Bibliografía ............................................... 31 1 1 Introducción En este capítulo se describen los elementos fundamentales en que se enmarca el proyecto como pueden ser los objetivos, el alcance, el trabajo previo en que se apoya, el contexto en que se desarrolla o las herramientas que se han utilizado para su realización. Además se indica de forma abreviada el contenido y distribución del resto de capítulos de la memoria. 1.1. Objetivos y alcance Los objetivos de este proyecto pueden agruparse y resumirse en la consecución de dos metas. La primera meta del proyecto consiste en el diseño e implementación de un paquete de software que cumpla los siguientes requisitos: −Permita la creación, la consulta de propiedades y la transformación de las principales estructuras definidas en tres de los papers [1,2,4] que cubren el estudio fundamental sobre la teoría de las 2-estructuras. −Dibuje gráficamente las representaciones propuestas en los mencionados papers. −Integre los anteriores componentes en un programa interactivo que permita la manipulación y el almacenamiento permanente de las estructuras. La segunda meta tiene como propósito la investigación y el desarrollo de posibles aplicaciones de las 2-estructuras a las gramáticas suavemente sensibles al contexto (Mildly Context Sensitive Grammars, MCSG) utilizadas en el procesamiento del lenguaje natural. Para ello se toma como punto de partida los siguientes dos subobjetivos: −Utilización de la herramienta construida para estudiar formas de representación conjunta del orden de escritura y el orden de generación de los terminales de cadenas derivadas de una MCSG, empleando en las pruebas un conjunto suficientemente representativo de ejemplos de gramáticas. El interés de esta tarea viene dado por el hecho de que, al contrario de lo que ocurre con las gramáticas independientes el contexto (Context Free Grammar, CFG), en algunas MCSG no se puede deducir de los árboles de derivación las reglas aplicadas en la derivación. −Establecimiento de conjeturas y/o resultados que permitan fortalecer la formalización de las MCSG mediante el uso de las 2-estructuras. Este último subobjetivo corresponde a un reto actual de investigación del procesamiento del lenguaje natural [6]. En este proyecto se pretende obtener resultados iniciales o al menos conjeturas prometedoras. 2. Desarrollo del paquete de software 8 Ilustración 2.1 Diagrama de clases con el modelado y el diseño de las 2-estructuras. Las 2-estructuras son básicamente conjuntos disjuntos de aristas y por ello se han implementado usando una conocida representación eficiente en árbol [16] que tiene un coste amortizado asíntoticamente óptimo. Las labeled tree families se han implementado trasladando de forma natural su definición a estructuras de datos típicas con las optimizaciones que su semántica permitía. 2.2. Controles gráficos para la visualización En la ilustración 2.2 se muestra el diseño del visualizador de las 2-estructuras y el de las labeled tree families. El primero tiene desacoplada toda la lógica del dibujado y la interacción, que se encuentra contenida en la clase TwoStructureCanvas, del control gráfico propiamente dicho (TwoStructureViewer). De esta forma, el visualizador de las labeled tree families (LabeledTreeFamilyViewer) puede reutilizar los métodos 2.2. Controles gráficos para la visualización 9 de dibujado para mostrar las 2-estructuras que etiquetan cada nodo interno del árbol. Además, los algoritmos de posicionamiento de los nodos para cada estructura se encuentran en clases separadas de las de los controles. En concreto en TwoStructureLayout y en GeneralTreeLayout. En el caso de las 2-estructuras el objetivo es dibujar un grafo completo. Por ello se opta por un posicionamiento de los nodos en forma de polígono regular. Se tratan como situaciones especiales las 2-estructuras, con pocos elementos, que etiquetan los nodos de las labeled tree families. En dichas situaciones los nodos se posicionan de forma que faciliten las conexiones con los hijos. Para las labeled tree families se implementa el algoritmo de Walker [14] que sirve para situar los nodos de un árbol con un número arbitrario de hijos en cada nivel. Ambos visualizadores se han implementado como controles gráficos (Swing) de Java con JPanel como superclase de partida. Debido a que el número de elementos de las 2-estructuras que etiquetan los nodos de las labeled tree families puede ser arbitrariamente grande, sólo se dibujan en el interior de los nodos las 2-estructuras con como máximo tres elementos. Para poder ver una labeled tree family junto a la 2-estructura con cuatro o más elementos que etiqueta un nodo, se ha diseñado un control gráfico de doble panel (LabeledTree- FamilySplitViewer) tal que el panel izquierdo muestra la labeled tree family y el derecho la 2-estructura del nodo que se seleccione. De nuevo este último componente es un control gráfico de Java que hereda esta vez de JSplitPanel. Ilustración 2.2 Controles gráficos de visualización de 2-estructuras y sus formas. 2. Desarrollo del paquete de software 10 2.3. Arquitectura y diseño del programa interactivo En la ilustración 2.3 se muestra la división en tres capas de la aplicación de escritorio que permite analizar, transformar y visualizar las distintas estructuras del dominio del problema. Ilustración 2.3 Arquitectura en tres capas del programa interactivo. En la capa lógica está la clase Application que se encarga de construir la interfaz y procesar las respuestas a los distintos eventos. También está la clase Workspace que mantiene un diccionario de nombres de variables asociados a instancias de las estructuras creadas en una sesión. La idea del espacio de trabajo es la misma que la que utiliza el conocido software matemático MATLAB. El espacio de trabajo de una sesión puede ser almacenado de manera permanente en un fichero XML utilizando la clase WorkspaceXML de la capa de datos. La ventana principal del programa se divide en tres áreas que se corresponden con las clases WorkspaceTable (la tabla en donde se lista las variables de la sesión), 2.3. Arquitectura y diseño del programa interactivo 11 ConsoleTextArea (un cuadro de texto donde se lista información sobre las estructuras seleccionadas) y ViewerPanel (el panel donde se muestra las representaciones gráficas de las estructuras). El ViewerPanel contiene una especialización de los visores descritos en la sección anterior a los que se les ha añadido opciones de edición y transformación. Por ejemplo, permite seleccionar varias aristas de una 2-estructura y hacerlas equivalentes o seleccionar varios elementos de una 2-estructura y generar la subestructura correspondiente. Para mantener una separación estanca entre las distintas capas de forma que sólo las capas superiores dependan de los servicios ofrecidos por las capas inferiores, se implementa el patrón Observador. De esta manera la interfaz, ante las peticiones del usuario, llama a los métodos de la capa lógica donde se realizan las modificaciones del modelo (como el espacio de trabajo) y los controles de la interfaz, suscritos a los eventos de las partes afectadas por los cambios, son notificados sincronizando su estado con el del modelo. El diseño se corresponde con lo que algunos autores llaman una arquitectura Modelo-Vista-Controlador. . 12 13 3Asociación de un árbol derivado a las cadenas generadas por una gramática HG Las gramáticas de núcleo4no proporcionan un árbol derivado a las cadenas del lenguaje [11,12]. En este capítulo se propone una extensión de las gramáticas de núcleo que asocia explícitamente un árbol derivado a las cadenas generadas usando las mismas operaciones de concatenación y de wrapping empleadas en el formalismo. Para ello se hace uso de los conceptos sobre textos alternantes de la teoría de las 2-estructuras5. Esto permite dotar de una estructura a las palabras generadas para poder compararlas con las dadas por otras gramáticas que generan la misma clase de lenguajes[8], como las gramáticas de adjunción de árboles. El interés de este trabajo, y su diferencia con el de otros trabajos previos como [12], radica en que se utiliza un formalismo robusto (las 2-estructuras) para expresar la estructura de una palabra de una forma ‘natural’ (basándose en las operaciones de concatenación y de wrapping originales). 3.1. Extensión de las gramáticas de núcleo En la nueva gramática propuesta vamos a realizar derivaciones de textos con núcleo, que definiremos como 3-tuplas pertenecientes a: HT =h(C→VT)×(C+×C+)×(C+×C+)i donde C+=∪k≥1Cky, CyVTson dos conjuntos arbitrarios. Notar que al trabajar con textos con núcleo trabajaremos con pares ordenados de secuencias y no con pares de ordenes lineales (revisar la definición de un texto en A.2), ya que desde el punto de vista gramatical nos interesará manipular secuencias. Como veremos adelante, del conjunto Csólo necesitaremos que se pueda generar un elemento distinto a los de una secuencia ya generada a partir de otro elemento cualquiera del conjunto, es decir, que tenga una función sucesor definida. Por comodidad consideramos que C es siempre el conjunto de los números naturales Nque cumple dicha condición. Adelantamos que durante la generación del árbol derivado, las operaciones de concatenación y wrapping concatenarán subárboles asociados a textos con distinta interpretación de la dirección. Para hacerlo de manera consistente se necesitará saber de dicha interpretación en las posiciones (nodos del árbol correspondiente) donde se apliquen y, por tanto, en vez de trabajar con textos con núcleo ‘puros’ se empleará una extensión de los mismos. Como ya se verá, sólo hay dos puntos posibles de concatenación, en la raíz o en un nodo ‘pie’, por lo que en vez de usar HT durante la derivación, en realidad se usará el conjunto HT +=HT ×V2 Adonde Ver anexo B.4 para la definición de las gramáticas de núcleo. 4 Ver anexo A para una introducción a las 2-estructuras y los textos alternantes. 5 3. Asociación de un árbol derivado a las cadenas ... 14 VA={→,←}. El elemento →indicará que la interpretación de la dirección es de izquierda a derecha mientras que el elemento ←indicará la otra dirección. Usaremos el operador ¬sobre VAcon su significado ‘habitual’ de opuesto. Es decir, ¬ →=← y¬ ←=→. Dado un texto con núcleo extendido τ=hλ, (u↑v),(p↑q),(r, f)i, diremos que el texto asociado a τes (λ, ρ1, ρ2)donde ρ1yρ2son los ordenes lineales inducidos por las secuencias uv ypq respectivamente. Por otra parte, diremos que el árbol asociado aτes el árbol ordenado inducido por su texto asociado y que la interpretación de la dirección en la raíz es r. Para hablar de una interpretación de la dirección de τen concreto, usaremos dir+(τ)para denotar a rydir−(τ)para denotar a f. Definiremos el reverso o inverso de τcomo hλ, ρ1,(rev(q), rev(p)),(¬r, ¬f)iy lo denotaremos con rev(τ). Diremos que la longitud de τ,len(τ), es |u|+|v|con el significado habitual de la operación al utilizar secuencias. Ejemplo 3.1. Sea τ=hλ, ρ1, ρ2, θi ∈ HT+con λ={(1, a),(2, a),(3, b),(4, b)}, ρ1= (1,2↑3,4),ρ2= (1,4↑2,3) yθ= (→,→). La longitud de τes len(τ) = |(1,2)|+|(3,4)|= 2 + 2 = 4. Y el reverso de τes µ=hλ, ρ1,(3,2↑1,4),(←,←)i. Respecto a una gramática de núcleo en su concepción original, la versión extendida modifica las operaciones de concatenación y de wrapping, y la relación de derivación ⇒. Por tanto, sólo se van a redefinir éstas enteniéndose que el resto de la definición de la gramática sigue siendo aplicable. Para que esto sea así, se empleará en la relación de derivación la siguiente función de conversión de una cadena con núcleo a un texto con núcleo extendido usando un natural scomo ‘semilla generadora’. ht : (V∗ T×V∗ T)×N→HT+: ht(u1. . . un↑v1. . . vm, s)=(λ, ρ1, ρ2, θ) donde: λ={(s, u1),...,(s+n−1, un),(s+n, v1),...,(s+n+m−1, vm)} ρ1=hs, . . . , s +n−1↑s+n, . . . , s +n+m−1i ρ2=hs+n+m−1, . . . , s +n↑s+n−1, . . . , si=rev(ρ1) θ= (←,←) Ci,n : (HT+)n→HT +es la nueva operación de concatenación: Ci,n(τ1, . . . , τi, . . . , τn) = h∪n t=1λt, u1v1. . . ui↑vi. . . unvn, p1q1. . . pi↑qi. . . pnqn,(→, fi)i donde τj=hλj, uj↑vj, pj↑qj,(rj, fj)icon (1 ≤j≤n). 3.1. Extensión de las gramáticas de núcleo 15 W: (HT+)2→(HT +)es la nueva operación de wrapping: W(τ1, τ2) = hλ1∪λ2, u1u2↑v2v1, p1p2↑q2q1,(r1, f2)i donde τj=hλj, uj↑vj, pj↑qj,(rj, fj)icon (1 ≤j≤2). Antes de poder redefinir la relación de derivación tenemos que definir dos funciones auxiliares, left ycomp. La primera es utilizada para asegurarse de que si un texto con núcleo extendido tiene →como dir+, éste sea invertido. La segunda función se emplea para asegurarse de que si un texto con núcleo extendido no tiene como dir+la opuesta a una dada, éste sea invertido. left :HT+→HT +: left(τ) = rev(τ),si dir+(τ) =→ τ, si dir+(τ) =← comp :HT+×VA→HT +: comp(τ, a) = rev(τ),si dir+(τ) = a τ, si dir+(τ)6=a La relación de derivación ⇒se define como sigue: •τ0 =⇒τpara todo τ∈HT+. •Si A→W(σ1, σ2)∈Pentonces (A, s)k =⇒W(τ1, comp(τ2, dir−(τ1))) donde: (σj, next(s, j)) kj =⇒τj, si σj∈VN,ht(σj, next(s, j)) kj =⇒τj, si σj∈V∗ T×V∗ T con (1 ≤j≤2),k= 1+P1≤j≤2kjynext(s, j) = s, si j=1 s+Pj−1 t=1 len(τt),si j>1 •Si A→Ci,n(σ1, . . . , σn)∈Pentonces (A, s)k =⇒Ci,n(left(τ1), . . . , left(τn))) donde: (σj, next(s, j)) kj =⇒τj, si σj∈VN,ht(σj, next(s, j)) kj =⇒τj, si σj∈V∗ T×V∗ T con (1 ≤j≤n),k= 1+P1≤j≤nkjynext(s, j) = s, si j=1 s+Pj−1 t=1 len(τt),si j>1 Destacar que de la manera en la que hemos definido la relación de derivación, ésta nos asegura que todo texto asociado a un texto con núcleo extendido resultado de una derivación sea alternante. 3. Asociación de un árbol derivado a las cadenas ... 16 El lenguaje generado por una gramática de núcleo extendida queda definido por todos los (λ(u1)·. . .·λ(un)) ∈V∗ Ttales que (S, 1) ∗ =⇒(λ, (u1, . . . , ui↑ui, . . . , un), ρ2, θ). Dada una palabra (λ(u1)·. . . ·λ(un)) ∈V∗ Ttal que (S, 1) ∗ =⇒τdonde τ= (λ, (u1, . . . , ui↑ui, . . . , un), ρ2, θ), su árbol derivado asociado viene determinado por el árbol asociado a τ. 3.2. Ejemplo ilustrativo La gramática de núcleo extendida6G= ({S, T},{a, b, c, d}, S, P )genera el lenguaje {anbncndn|n≥0}donde Pes como sigue. P={S→C1,1(↑), S →C2,3(a↑, T, d↑), T →W(S, b↑c)} La derivación de la cadena aabbccdd junto a la de su árbol derivado asociado se descompone en los siguientes dos grupos de pasos. Vamos a presentarlos en dos grupos separados para verlo más claramente. En el primer grupo detallamos la reglas de reescritura aplicadas. (S, 1) 5 =⇒ τ12 z}| { C2,3(left(ht(a↑, 1)) | {z } τ9 , left((T, 3)) | {z } τ10 , left(ht(d↑, 13)) | {z } τ11 ) que depende de (T, 3) 4 =⇒W((S, 3) |{z} τ7 , comp(ht(b↑c, 11), dir−(τ7)) | {z } τ8 ) que depende de (S, 3) 3 =⇒C2,3(left(ht(a↑, 3)) | {z } τ4 , left((T, 5)) | {z } τ5 , left(ht(d↑, 9)) | {z } τ6 ) que depende de (T, 5) 2 =⇒W((S, 5) |{z} τ2 , comp(ht(b↑c, 7), dir−(τ2)) | {z } τ3 ) que depende de (S, 5) 1 =⇒C1,1(left(ht(↑, 5)) | {z } τ1 ) En el segundo grupo listamos los resultados de aplicar las operaciones de conversión, de concatenación y de wrapping para obtener el texto con núcleo extendido final. En el anexo B.4 se encuentra el mismo ejemplo para gramáticas de núcleo. Su ‘aparencia’ es 6 idéntica puesto que lo que cambia son las definiciones de la relación de derivación y las operaciones de concatenación y de wrapping. 3.2. Ejemplo ilustrativo 17 τ1=h{(5, ),(6, )},(5↑6),(6↑5),(←,←)i τ2=C1,1(τ1) = hλ1,(5↑6),(6↑5),(←,←)i τ3=h{(7, b),(8, c)},(7↑8),(7↑8),(→,→)i τ4=h{(3, a),(4, )},(3↑4),(4↑3),(←,←)i τ5=left(W(τ2, τ3)) = hλ2∪λ3,(5,7↑8,6),(6,7↑8,5),(←,→)i τ6=h{(9, d),(10, )},(9↑10),(10↑9),(←,←)i τ7=C2,3(τ4, τ5, τ6) =hλ4∪λ5∪λ6,(3,4,5,7↑8,6,9,10),(4,3,6,7↑8,5,10,9),(→,→)i τ8=h{(11, b),(12, c)},(11↑12),(12↑11),(←,←)i τ9=h{(1, a),(2, )},(1↑2),(2↑1),(←,←)i τ10 =left(W(τ7, τ8)) =left(hλ7∪λ8,(3,4,5,7,11↑12,8,6,9,10),(4,3,6,7,12↑11,8,5,10,9),(→,←)i) =hλ7∪λ8,(3,4,5,7,11↑12,8,6,9,10),(9,10,5,8,11↑12,7,6,3,4),(←,→)i τ11 =h{(13, d),(14, )},(13↑14),(14↑13),(←,←)i τ12 =C2,3(τ9, τ10, τ11) =hλ9∪λ10 ∪λ11,(1,2,3,4,5,7,11↑12,8,6,9,10,13,14), (2,1,9,10,5,8,11↑12,7,6,3,4,14,13),(→,→)i A partir de τ12 = (λ, (u↑v), ρ, θ), se puede obtener la palabra derivada aplicando λa cada elemento de la secuencia uv,(λ(1)·. . .·λ(14)) = aabbccdd, y se puede obtener el texto (λ, (1,2,3,4,5,7,11,12,8,6,9,10,13,14),(2,1,9,10,5,8,11,12,7,6,3,4,14,13)) que representa el árbol derivado de la ilustración 3.17. Para entender mejor cómo va quedando definido el árbol derivado durante el proceso de derivación, vamos a analizar un paso de la derivación en la que aparezca una operación de wrapping, por ejemplo al calcular τ5a partir de τ2yτ3. En la ilustración 3.2 tenemos los árboles derivados asociados a τ2,τ3yτ5res- pectivamente. Podemos ver que el árbol de τ5es el resultado de concatenar el árbol de τ3al árbol de τ2por el punto donde la segunda secuencia de τ2está dividida. Notar que las interpretaciones de las direcciones de los nodos involucrados son complementarias porque τ3es el resultado de aplicar la función comp aht(b↑c, 7) Realmente es la representación del árbol derivado junto a la información del texto a partir de la 7 cual se genera. 4. Generación de una gramática TAG a partir de una ... 24 D1D1D0). Si la caracterizamos, tal como se detalló en la sección anterior, podemos deducir que la solución buscada tiene que ser un árbol de dependencias simple. Por otra parte, se puede observar que es posible dividir las dependencias en dos subsecuencias iguales (D0D1D1D0)que, trivialmente, cumplen la propiedad de ser una la inversa de la otra. Si nos fijamos en el árbol derivado de la palabra aabbccdd, mostrado en la parte izquierda de la ilustración 4.2, se puede ver que cada subsecuencia en la que se puede dividir las dependencias se corresponde con los terminales presentes en cada lateral del árbol. Por tanto, un algoritmo para hallar un árbol de dependencias simple consistiría en conseguir partir la secuencia de dependencias en dos subsecuencias tales que insertando, si es necesario, dependencias ficticias (asociadas a ) una sea la inversa de la otra. No obstante, hay que tener en cuenta que no todos las inserciones llevan a secuencias de dependencias compatibles con un árbol de dependencias válido. Una secuencia será compatible si y sólo si ninguna dependencia situada entre dos dependencias iguales está también antes o después de las dependencias que la rodean. Esto tiene que ser así porque la operación de adjunción o bien se comporta como una operación de concatenación por delante o detrás de un grupo de nodos de dependencias o bien divide en dos a un grupo de nodos con la misma dependencia quedando situado sobre las dos partes resultantes. También es necesario ver que puede haber más de una manera válida de insertar dependencias ficticias en la secuencia, lo que sugiere, unido al anterior hecho, que se debe realizar una búsqueda en el espacio de soluciones. Además en esta búsqueda interesará que el número de dependencias introducidas sea mínimo, aunque esta condición es prescindible. En el anexo D.1 se puede ver una implementación del algoritmo. 4.4. Método para generar un árbol de dependencias complejo La idea que se plantea para resolver estos árboles consiste en identificar cada rama independiente de tal manera que se agrupen todas las dependencias pertenencientes a dicha rama bajo una dependencia que hará de representante y será hijo en un lateral de una rama superior. Es decir, la rama independiente equivaldrá a un nodo hoja de una espina superior. Después se resolverá cada rama independiente, con el algoritmo ya visto, que dará lugar a un subárbol que será sustituido por su nodo representante. 4.4. Método para generar un árbol de dependencias complejo 25 Para ayudar a entender la explicación se va a presentar un ejemplo. Supongamos que se tiene la siguiente entrada: ((eabbbtptcddvpvdere),(D0D1D2D3D4D5 D6D5D1D2D3D7D6D7D4D0D8D0)). Su representación gráfica está disponible en la ilustración 4.4. e a b b b t p t c d d v p v d e r e Ilustración 4.4 Palabra con dependencias disjuntas. Claramente se aprecia que las dependencias D5,D7yD8, asociados a los terminales t,vyrrespectivamente, son disjuntas entre sí. Para eliminar dicho problema se propone agrupar las dependencias D5bajo una dependencia D6, las D7bajo otra dependencia D6y la D8bajo una dependencia D0. La ilustración 4.5 lo muestra gráficamente. Para el caso de D8yD0se puede apreciar una agrupación adicional. Ésta es debida a que, como se explicó para el algoritmo de la sección anterior, si hay varias dependencias iguales contiguas se consideran como si fuera una sola. S D0 e D1 a D2 b D3 b D4 b D6 D5 t D6 p D5 t D1 c D2 d D3 d D6 D7 v D6 p D7 v D4 d D0 D0 e D0 D8 r D0 e Ilustración 4.5 Subdivisión de una entrada en ramas independientes. Una vez realizadas las agrupaciones, cada nivel del árbol se puede procesar como una entrada del algoritmo para árboles de dependencias simples y combinar los árboles resultantes para construrir el árbol de dependencias final. La siguiente cuestión a plantear es cómo se puede llegar a identificar correctamente el grupo de dependencias que forma una rama independiente y averiguar 4. Generación de una gramática TAG a partir de una ... 26 cuál es la dependencia que la representa. Como solución a este problema se propone un método iterativo/recursivo que dada una secuencia de dependencias genera una nueva secuencia formada como resultado de sustituir algunas subsecuencias de dependencias contiguas por otra dependencia en la secuencia de entrada. El algoritmo termina cuando la secuencia de entrada está constituida por una sola dependencia. Además de todas las dependencias involucradas en la secuencia original, también puede ser necesario disponer de una superdependencia, que denotaremos por S, que será padre de todas aquellas ramas independientes que no tengan en común ninguna dependencia. A continuación se describen los pasos más importantes del algoritmo: −Se lee toda la secuencia de dependencias y se calcula el intervalo asociado a cada una de ellas. Este paso es necesario hacerlo la primera vez, pero en las sucesivas vueltas se puede precalcular mientras se genera la secuencia de salida. −Se recorre toda la secuencia buscando las posiciones en las que aparece por primera vez una dependencia (se abre su intervalo) después de que otra dependencia hubiese sido leída por última vez (su intervalo se cerrara). −En cada subsecuencia en la que los puntos encontrados en el paso previo divide la entrada, o en la secuencia entera si no existe ningún punto, se busca la mayor subsecuencia de dependencias tales que todas las dependencias iguales a ella están contenidas en la subsecuencia y ésta contiene como máximo una dependencia que no cumple la condición. A la subsecuencia máxima le llamaremos grupo, las dependencias que cumplen la condición diremos que son de tipo A y las que no de tipo B. Hacer notar que estos grupos pueden no existir. −A cada grupo encontrado se le asocia una nueva dependencia como representante que será igual a: −La dependencia de tipo B que está contenida en el grupo. −O en caso contrario, la última dependencia que abrió su intervalo antes del grupo. Si no existe dicha dependencia se usará la superdependencia S. −La secuencia de salida es el resultado de sustituir cada grupo por su representante en la secuencia de entrada dejando el resto de dependencias en sus posiciones originales. Ejemplo 4.1. En la ilustración 4.6 se muestra el árbol de dependencias resultante tras procesar la espina principal y el grupo que contiene a D8∗del ejemplo visto en la sección anterior. Para obtener el árbol final se debe sustituir los representantes D6∗por el resultado de aplicar el algoritmo para árboles simples a las secuencias correspondientes. Los subárboles que se obtienen figuran en la ilustración 4.7. 4.4. Método para generar un árbol de dependencias complejo 27 D0 0 (e) D1 1 (a) D2 2 (b) D3 3 (b) D4 4 (b) D6 D6*D3 D2 D1 8 (c) 9 (d) 10 (d) D6* 14 (d) 15 (e) D8* 16 (r) 17 (e) Ilustración 4.6 Árbol de dependencias de la espina principal de eabbbtptcddvpvdere. D5 5 (t) D6 6 (p) 7 (t) D7 11 (v) D6 12 (p) 13 (v) Ilustración 4.7 Subárbol de dependencias de tpt yvpv. En el anexo D.2 se detalla una implementación en pseudocódigo junto a las estructuras de datos utilizadas. Una implementación ‘real’ ha sido incluida e integrada en el entorno de análisis y visualización de las 2-estructuras, la cual permite generar y visualizar los árboles de dependencias complejos a partir de una cadena con dependencias. También se puede visualizar la composición jerárquica de las distintas espinas de manera similar a lo mostrado en la ilustración 4.5. . 28 29 5 Conclusiones En este capítulo se presenta un resumen del conjunto del trabajo realizado y se describen las posibilidades de continuación. También se ofrece una valoración personal sobre el desarrollo del proyecto. 5.1. Resultados del proyecto Este proyecto nació con la doble finalidad de proveer una herramienta para el estudio de las 2-estructuras y sus aplicaciones y de establecer resultados prometedores que relacionaran las 2-estructuras y las MCSG, objetivos que han sido cumplidos satisfactoriamente. El trabajo realizado por el autor puede ser resumido en los siguientes tres puntos: −El diseño y la implementación de un paquete de software que contiene tanto una biblioteca para futuros programas que requieran del análisis, la transformación y la visualización de las principales estructuras involucradas en la teoría de las 2-estructuras como un entorno de trabajo para usuarios finales que investiguen sobre el tema. −La formulación de una extensión de las grámaticas de núcleo que dota a las cadenas generadas de una estructura que sirve para realizar comparaciones con otras gramáticas debilmente equivalentes, que además preserva el uso de las operaciones originales y que se fundamenta en la teoría de las 2-estructuras. −El diseño de un algoritmo capaz de generar una gramática TAG a partir de una cadena (o frase del lenguaje natural) con dependencias anidadas y cruzadas. Como resultado adicional se prevee la elaboración de un artículo de investigación cuyo germen será el presente proyecto en colaboración con el grupo de investigación del profesor Balcázar en la Universidad de Cantabria. 5.2. Trabajo futuro Parte del objetivo con el que se ha construido el paquete de software es el de servir de herramienta base para futuras investigaciones en relación con las 2-estructuras. Sin embargo, es imposible adelantarse a todos los posibles usos que se le pueda dar. Es por ello que será necesario seguir complentando y adaptando el trabajo aquí realizado para ajustarse a las necesidades de trabajos venideros. En relación con la extensión de las gramáticas de núcleo presentada, se propone diseñar un algoritmo que, en vez de generar una gramática TAG, genere una gramática HG (en su versión extendida) a partir de una cadena con dependencias. Después 30 se podría comparar ambos algoritmos y estudiar sus semejanzas y diferencias en cuanto a los métodos usados y las estructuras generadas. Otro punto interesante a analizar en profundidad es ver cuanto se parece las gramáticas generadas a partir de una palabra a las que uno construiría con la intención de poder derivarla. La experiencia tenida durante el trabajo muestra que aunque muchas veces éstas coinciden, muchas otras no lo hacen. Por último, se propone como siguiente paso natural, una vez que se es capaz de generar una gramática a partir de una sola palabra, el buscar la mejor forma de unificar todas las gramáticas generadas a partir de palabras pertenecientes a un mismo lenguaje. 5.3. Valoración personal La realización de este proyecto fin de carrera como colofón a mis estudios ha sido una experiencia muy gratificante y enriquecedora. Por una parte por la doble naturaleza del proyecto, que se compone de una parte más teórica y una parte más práctica. En la parte práctica tenemos el desarrollo del paquete de software, donde he podido aplicar muchos de los conocimientos de ingeniería y programación adquiridos durante la carrera. En la parte teórica está el estudio de las 2-estructuras, del procesamiento del lenguaje natural y las MSCG, temas desconocidos o de los que tenía un conocimiento muy superficial y cuya exploración me ha resultado muy interesante. En particular la teoría de las 2-estructuras, que ha influido en mi forma de abordar nuevos problemas con su visión ‘puramente’ matemática. Y por otra parte por la libertad que he tenido y el apoyo que he recibido para desarrollar el proyecto. 31 Bibliografía [1] A. Ehrenfeucht and G. Rozenberg. “Theory of 2-structures. Part I: Clans, basic subclasses, and morphisms”. Theor. Comput. Sci., 70:277–303, 1990. [2] A. Ehrenfeucht and G. Rozenberg. “Theory of 2-structures. Part II: Representation through labeled tree families”. Theor. Comput. Sci., 70:305–342, 1990. [3] A. Ehrenfeucht and G. Rozenberg. “Angular 2-structures”. Theor. Comput. Sci., 92:227–248, 1992. [4] A. Ehrenfeucht and G. Rozenberg. “T-Structures, T-functions, and texts”. Comput. Sci., 116:227–290, 1993. [5] A. Ehrenfeucht, T. Harju and G. Rozenberg. “The theory of 2-estructures. A Framework for Decomposition and Transformation of Graphs”. World Scientific, 1999. [6] D. Jurafsky, J.H. Martin: “Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition”. Prentice Hall, 2009. [7] M. A. Alonso. “Interpretación tabular de autómatas para lenguajes de adjunción de árboles”, Tesis doctoral, Universidad de La Coruña, España, 2000. [8] K. Vijay-Shanker, D.J. Weir. “The Equivalence Of Four Extensions Of Context- Free Grammars”. Mathematical Systems Theory, 27:511–546, 1994. [9] J.M. Vergés. “La no-independencia del contexto de los lenguajes naturales”. Lenguajes naturales y lenguajes formales: actas del XII congreso de los lenguajes naturales y lenguajes formales, pp. 87—102, 1996. [10] C. Pollard. “Generalized Phrase Structure Grammars, Head Grammars and Natural Language”. PhD thesis, Stanford Ubiversity, 1984. [11] D.J. Weir. “Characterizing Mildly Context-Sensitive Grammar Formalisms”. PhD thesis, University of Pennsylvania, 1988. Available as Technical Report MSCIS-88-74 of the Department of Computer and Information Sciences, University of Pennsylvania. [12] D.J. Weir, K. Vijay-Shanker and A.K. Joshi. “The relantionship Between Tree Adjoining Grammars And Head Grammars”. Proceedings of the 24th annual meeting on Association for Computational Linguistics, 67–74, 1986. [13] J.Q. Walker II. “A node-positioning algorithm for general trees”. Softw. Pract. Exper., 20:685–705, 1990. 32 [14] C. Buchheim, M. Jünger and S. Leipert. “Improving Walker’s Algorithm to Run in Linear Time”, Graph Drawing. Lecture Notes in Computer Science, 2528:347–364, 2002. [15] A.K. Joshi. “Processing Crossed and Nested Dependencies: An automaton Perspective on the Psycholinguistic Results”. Language and Cognitive Processes, 1989. [16] Bernard A. Galler and Michael J. Fischer. “An improved equivalence algorithm”. Communications of the ACM, 7:301–303, 1964. [17] Plataforma Java SE. http://www.oracle.com/technetwork/java/javase/ (Último acceso: 24/08/2010). [18] JGraph. http://www.jgraph.com (Último acceso: 24/08/2010). [19] JUNG. http://jung.sourceforge.net/ (Último acceso: 24/08/2010). [20] Eclipse. http://www.eclipse.org/ (Último acceso: 24/08/2010). [21] Subversion. http://subversion.apache.org/ (Último acceso: 24/08/2010).