Índice de contenidos - upv/ehuadimen.si.ehu.es/~rigau/teaching/ehu/pfcs/gorkablanco2010... ·...

Índice de contenidos1.- Introducción....................................................................................................................................1

1.1.- Presentación.............................................................................................................................11.2.- Motivación...............................................................................................................................1

1.2.1.- Empezando por el final: un ejemplo................................................................................11.2.2.- El problema de la desambiguación de palabras...............................................................2

2.- Antecedentes...................................................................................................................................32.1-Kyoto.........................................................................................................................................32.2- Redes semánticas......................................................................................................................5

2.2.1- Wordnet.............................................................................................................................62.2.2- EuroWordNet....................................................................................................................8

2.2.2.1- El Indice InterLingüa................................................................................................82.3- Proyecto Meaning...................................................................................................................11

2.3.1- Multilingual Central Repository (MCR)........................................................................122.4- SSI-Dijkstra............................................................................................................................132.5- SSI-Dijkstra+..........................................................................................................................152.6- UKB........................................................................................................................................172.7.- FrameNet...............................................................................................................................18

3.- Elección tecnológica.....................................................................................................................193.1.- Pre-requisitos.........................................................................................................................193.2.- Desarrollo: la máquina personal del alumno.........................................................................19

3.2.1.- Sistema operativo...........................................................................................................193.2.2.- Entorno de desarrollo.....................................................................................................20

3.3.- Documentación......................................................................................................................203.3.1.- OpenOffice Writer. Memoria.........................................................................................203.3.2.- OpenOffice Impress. Transparencias.............................................................................20 3.3.3.- Gantt Project. Diagrama de Gantt.................................................................................21

4.- DOP: Documento de Objetivos del Proyecto................................................................................224.1.- Objetivos................................................................................................................................224.2.- Método de trabajo..................................................................................................................224.3.- Alcance..................................................................................................................................23

4.3.1.- Recursos humanos.........................................................................................................234.3.2.- Recursos materiales.......................................................................................................234.3.3.- Recurso económico........................................................................................................234.3.4.- Diagrama EDT (Estructura de descomposición del trabajo).........................................244.3.5.- Proyecto de Final de Carrera (PFC)...............................................................................26

4.4.- Planificación temporal: Diagrama de Gantt..........................................................................294.5.- Plan de contingencia..............................................................................................................324.6.- Análisis de factibilidad..........................................................................................................34

5.- Captura de requisitos.....................................................................................................................355.1.- Motivación.............................................................................................................................355.2.- Requisitos específicos...........................................................................................................355.3.- Resumen................................................................................................................................36

6.- Análisis..........................................................................................................................................376.1.- Sobre UKB............................................................................................................................376.2.- Sobre SSI-Dijkstra.................................................................................................................37

7.- Diseño...........................................................................................................................................397.1.- Pseudocódigos.......................................................................................................................39

7.1.1.- Obtener_distancia..........................................................................................................397.1.2.- Obtener_distancia_mas_rapido......................................................................................39

I

7.1.3.- Mostrar_camino.............................................................................................................407.1.4.- SSI_Dijsktra...................................................................................................................417.1.5.- SSI_Dijkstra+................................................................................................................437.1.6.- Ordenar_por_polisemia.................................................................................................467.1.7.- Ordenar_de_forma_explicita.........................................................................................467.1.8.- Ordenar_por_id..............................................................................................................467.1.9.- Ordenar_palabras...........................................................................................................477.1.10.- Ordenación_por_id......................................................................................................477.1.11.- Programa principal (main)...........................................................................................48

8.- Implementación.............................................................................................................................498.1.- Sobre UKB: lo que no teníamos............................................................................................49

8.1.1.- Contextos como estructuras de datos: CSentence..........................................................498.1.2.- Limitaciones: creación de nuevos métodos...................................................................50

8.2.- Optimizaciones......................................................................................................................518.3.- Sobre SSI-Dijkstra................................................................................................................528.4.- UKB: Lectura de datos aleatoria...........................................................................................54

9.- Pruebas..........................................................................................................................................569.1.- Pruebas simples.....................................................................................................................56

9.1.1.- SSI-Dijkstra, ineficiente y sin pesos..............................................................................579.1.2.- SSI-Dijkstra, eficiente y sin pesos.................................................................................579.1.3.- SSI-Dijkstra+, eficiente y sin pesos...............................................................................579.1.4.- SSI-Dijkstra+, eficiente y con pesos..............................................................................58

9.2.- Pruebas completas (¡Egoitz!)................................................................................................5810.- Gestión........................................................................................................................................59

10.1.- Esfuerzo total planificado vs real .......................................................................................5910.1.1.- En procesos tácticos.....................................................................................................5910.1.2.- En procesos operativos................................................................................................60

10.1.2.1.- Primera iteración..................................................................................................6010.1.2.2.- Segunda iteración.................................................................................................6110.1.2.3.- Tercera iteración...................................................................................................62

10.1.3.- En procesos formativos................................................................................................6310.1.4.- Un punto de vista general............................................................................................65

10.2.- Justificación de las desviaciones.........................................................................................6510.3.- Incidencias principales........................................................................................................66

11.- Conclusiones...............................................................................................................................6711.1.- Objetivos cumplidos............................................................................................................6711.2.- Valoración personal.............................................................................................................6711.3.- Trabajos futuros...................................................................................................................67

11.3.1.- Integrar dentro del branch principal de desarrollo de UKB.........................................6711.3.2.- Implementar otros algoritmos que usan Dijkstra.........................................................6811.3.3.- Usar otras funcionalidades de BoostGraph que no sean Dijkstra................................6811.3.4.- Comparativa con una solución Perl pura (sin BoostGraph).........................................6811.3.5.- Creación de un daemon en Linux para mejorar eficiencia..........................................68

II

PFC: SSI-Dijkstra+: Desarrollo de un sistema de resolución de la ambigüedad semántica basada en grafos

1.- Introducción

1.1.- Presentación

Este documento es la memoria de un Proyecto de Final de Carrera realizado por Gorka

Blanco Gutierrez (estudiante de Ingeniería Técnica en Informática de Sistemas en la Facultad de

Informática de San Sebastián, Universidad Pública Vasca (UPV/EHU)) y dirigido por Germán

Rigau Claramunt (profesor asociado en la Facultad de Informática de San Sebastián, Universidad

Pública Vasca (UPV/EHU)).

Se encuadra en el campo de la Inteligencia Artificial, más concretamente en el campo de la

semántica, la desambiguación de palabras y el procesamiento del lenguaje natural.

1.2.- Motivación

No es objetivo de este apartado tratar que el lector entienda todo lo relacionado con el

proyecto en él, sino simplemente dar una idea general sobre cuál es el problema a resolver y cómo

se ha resuelto. Se van a dar una serie de ideas generales y un ejemplo que quizás no queden del todo

claros pero que se irán entendiendo a medida que se vaya profundizando más en la lectura de la

memoria.

1.2.1.- Empezando por el final: un ejemplo

El núcleo de este proyecto gira alrededor de lo siguiente:

Tenemos una lista de palabras en inglés, (por ejemplo: fly, airport, plane, pilot, biplane,

autogiro) cuyo significado desconocemos. Como sabemos, las palabras pueden ser monosémicas

(tienen un único significado, por ejemplo: airport) o pueden ser polisémicas (tienen varios

significados, por ejemplo: fly). La única información adicional que tenemos de estas palabras es si

son nombres, verbos, adjetivos o adverbios. Por ejemplo, pilot puede actuar al mismo tiempo como

nombre (piloto) o como verbo (pilotar). El problema es hallar el significado más adecuado para

cada una de estas palabras. Al proceso que seguimos desde que con la lista de palabras obtenemos

la solución del problema se le llama desambiguación. La solución consta de un listado en el que a

cada palabra se le asocia un sentido de los posibles para esa palabra.

Con el ejemplo, anterior, una posible solución al problema podría ser la siguiente:

1.


(fly – verbo → 01840238)

(airport – nombre → 02692232)

(plane – nombre → 02691156)

(biplane – nombre → 02842573)

(autogiro – nombre → 02759387)

El número que acompaña a la solución está asociado con el significado de la palabra en ese

contexto. Se explicarán de forma más amplia todos estos conceptos más adelante.

1.2.2.- El problema de la desambiguación de palabras

La desambiguación de palabras se ha considerado desde siempre uno de los problemas más

difíciles del Procesamiento del Lenguaje Natural y por ende, de la Inteligencia Artificial. Para dar

solución a este problema se utilizan bastantes técnicas diferentes, aunque como no son objeto de

estudio de este proyecto no vamos a hablar de ellas. En concreto, vamos a centrarnos en el estudio

de técnicas sobre bases de conocimiento. De forma aún más concreta, nos basaremos en un método

de desambiguación basado en bases de conocimiento basadas en grafos llamado SSI-Dijkstra.

2.


2.- Antecedentes

Los siguientes apartados explican superficialmente el marco de trabajo del proyecto. Se han

incluido aquellos que se han marcado como de mayor interés o relación con el proyecto, así como

también se han incluido formas (links) de ampliar algunas cosas de las aquí comentadas. Muchas

cosas podrán haber quedado fuera de esta memoria, pero se procura explicar lo necesario para la

comprensión del lector, por lo que se ha decidido no alargar innecesariamente este apartado.

2.1-Kyoto

El proyecto KYOTO1 (Knowledge Yielding Ontologies for Transition-based Organization)

(ICT-211423) empezó en Marzo de 2008 y tiene previsto terminar en Marzo de 2011.

KYOTO tiene como objetivo construir un sistema de información independiente del

lenguaje para un dominio específico (medio ambiente, ecología y biodiversidad). Este sistema será

una ontología compartida independiente del lenguaje que estará vinculada a WordNets de 7

idiomas diferentes. Para cada idioma, la identificación y la extracción léxica de conceptos se llevará

acabo por los Kybots, que también serán los encargados de introducir nuevas entradas a la

ontología. A través de las entradas de la ontología será posible relacionar términos de diferentes

idiomas.

KYOTO está desarrollando una infraestructura wiki para a largo plazo permitir compartir

conocimiento (no necesariamente del dominio relacionado con el proyecto) entre diferentes

idiomas, culturas, ordenadores, ... El wiki de medio ambiente ayudará a los usuarios a ponerse de

acuerdo sobre los conceptos y términos de interés, y servirá para compartir conocimiento. Este

proceso se basa en la extracción automática de términos y significados sacados de documentos

facilitados por los usuarios. En la figura 2.1 podemos ver cómo funciona este proceso.

1 http://www.kyoto-project.eu

3.


En la Imagen 1 podemos ver el funcionamiento del sistema de información KYOTO, que

básicamente se basa en 6 pasos:

1. Personas de un dominio concreto especifican los lugares de diferentes y variadas

fuentes de información de múltiples idiomas.

2. El modulo de captura obtiene el texto procedente de las fuentes de información, por

ejemplo el texto “repentino aumento de las emisiones de CO2 en 2008 en Europa”. Los

procesadores lingüísticos analizan el texto y generan una representación de la estructura lingüística.

3. Los robots terminologicos (TyBots) extraen automaticamente todos los términos

importantes y las posibles realciones semanticas, por ejemplo “emisión de CO2”, y relacionaría este

término con un WordNet ya existente. Los TyBots pueden hacer este trabajo para cualquier idioma.

4. El wiki de medio ambiente (Wikyoto) permite a las personas del dominio a mantener

los términos y conceptos y a ponerse de acuerdo en su significado, sin depender del idioma. Los

significados son fromalizados en una ontología del dominio que puede ser usada por programas de

ordenador. Términos parecidos de diferentes idiomas pueden relacionarse con un mismo concepto

de la ontología. Por ejemplo, el término Alemán “CO2-uitstoot” puede relacionarse con el término

CO2Emission de la ontología.

5. Los llamados Kybots utilizan los términos y el conocimiento para detectar datos en los

4.

Imagen 1: Ciclo de KYOTO


textos escritos en varios idiomas. En el caso de un hecho, tenemos una instancia específica o un

caso de las emisiones de CO2 que tuvo lugar en un determinado momento y en una región

determinada. Dada la ontología y WordNets de diferentes idiomas, los Tybots pueden recolectar

estos hechos una y otra vez, para grandes volúmenes de datos de diferentes estados y de diferentes

idiomas.

6. Los datos son indexados y pueden ser accedidos por cualquiera a través de una

búsqueda semántica, otra vez más independiente mente del idioma. Por ejemplo, datos sobre las

emisiones de CO2 en Europa del 2000 al 2009.

2.2- Redes semánticas

Una red semántica es una forma de representación de conocimiento lingüístico en la que los

conceptos y sus interrelaciones se representan mediante un grafo. Los conceptos o unidades léxicas

se representan mediante los nodos del grafo, y las interrelaciones que existen entre conceptos serán

representadas por las aristas dirigidas del grafo. En el caso de que no existan ciclos entre conceptos,

los grafos también pueden ser dibujados en forma de árbol.

En las redes semánticas, un concepto importante es la distancia semántica que se expresa en

relación al número y tipo de enlaces que separan un nodo de otro.

Imagen 2: Ejemplo de red semántica

5.


En la Imagen 2 podemos ver representado cierto conocimiento acerca de los mamíferos. En

ella identificamos los elementos característicos de las redes semánticas como los nodos (mamífero,

animal, oso, pez,…), las relaciones (es un, tiene, vive en) y las distancias.

Existen diversos tipos de relaciones semánticas como la sinonimia/antonimia (relación entre

sinónimos y antónimos), hiponimia/hiperonimia (relación entre subordinados y superordinados), la

meronimia/holonimia (relación entre subconjuntos y conjuntos globales), entre otras.

Una de las redes semánticas más conocidas es WordNet.

2.2.1- Wordnet

Desarrollada en la universidad de Princeton, WordNet2 (Miller et al., 1990) es una base de

datos léxica de dominio general para el inglés que actualmente constituye uno de los recursos

léxicos mas utilizados en el área de PLN. WordNet (WN) fue creada para intentar organizar la

información léxica por significados, a diferencia de los diccionarios convencionales, donde esta

información está organizada por la forma de las unidades léxicas.

WN está estructurada como una red semántica cuyos nodos, denominados

synsets (synonym sets, o conjuntos de sinónimos) constituyen su unidad básica de significado. Cada

uno de ellos se compone de un conjunto de las lexicalizaciones que representan un sentido y se

identifica mediante un “offset” (byte) y su correspondiente PoS (Part of Speech); que puede ser (n)

para nombres, (v) para verbos, (a) para adjetivos y (r) para adverbios:

02152053#n fish#1

01926311#v run#1

02545023#a funny#4

00005567#r automatically#1

El número que aparece después de cada palabra indica el número de sentido que representa

el synset. Una palabra puede ser polisémica, esto es, tener varios significados, por ejemplo:

02152053#n fish#1; representa la palabra fish con el sentido de pez como

2 http://wordnet.princeton.edu

6.


animal vertebrado acuático.

07775375#n fish#2; representa la palabra fish con el sentido de pescado como alimento.

También puede ser que varias palabras tengan el mismo significado, esto es, que sean

sinónimas. En Wordnet están representados en el mismo synset:

02383458#n car#1, auto#1, automobile#1, machine#4, motorcar#1; representa el vehículo de

cuatro ruedas.

Todos los synsets incluyen una glosa a modo de definición similar a la del diccionario

tradicional, que describe el significado del concepto de forma explícita. Por ejemplo:

02383458#n car#1; 4-wheeled motor vehicle; usually propelled by an internal combustion

engine: he needs a car to get to work;

Como ya expuso anteriormente, WordNet está estructura como una red semántica. Además

de la información que pueden proporcionar los sinónimos (componentes del synset) y la glosa,

tenemos que tener en cuenta los arcos de la red semántica, estos establecen diferentes relaciones

entre los synsets, por ejemplo:

Hiperonimia: Es el término genérico usado para designar a una clase de instancias

específicas. Y es un hyperónimo de X, si X es una clase de Y.

tree#n#1 HYPERONYM oak#n#2

Hiponimia: Es el término específico usado para designar el miembro de una clase, X es un

hipónimo de Y, si X es una clase de Y. En el caso de los verbos se denomina

Troponimia.

oak#n#2 HYPONYM tree#n#1

Antonimia: Es la relación que enlaza dos sentidos con significados opuestos.

active#a#1 ANTONYM_OF inactive#a#2

7.


inactive#a#2 ANTONYM_OF active#a#2

Meronimia: Es la relación que se define como componente de, substancia de,

o miembro de algo, X es merónimo de Y si X es parte de Y.

car#n#1 HAS_PART window#n#2

milk#n#1 HAS_SUBSTANCE protein#n#1

family#n#1 HAS_MEMBER child#n#2

Holonimia: Es la relación contraria a la meronimia, Y es holónimo de X si X es una parte

de Y.

window#n#2 PART_OF car#n#1

protein#n#1 SUBSTANCE_OF milk#n#1

child#n#2 MEMBER_OF family#n#2

2.2.2- EuroWordNet

El éxito de Wordnet impulsó la creación de nuevos proyectos similares para

otros idiomas. De éstos el mas destacado ha sido EuroWordNet3 (Vossen, 1998).

EuroWordNet (EWN) consiste en una extensión multilingüe de WN, compuesta por bases de datos

léxicas para 8 idiomas (inglés, holandés, español, italiano, francés, alemán, checo y estonio).

Tras la finalización del proyecto EWN, empezaron a desarrollarse wordnets

para idiomas como el catalán, euskera, portugués, griego, búlgaro, ruso y sueco. Actualmente, la

creación de estos wordnets esta coordinada por “Global Wordnet Organization”4.

2.2.2.1- El Indice InterLingüa

InterLingual Index (ILI, del inglés Índice InterLingüa) es un indice general de conceptos que

permite conectar entre sí las unidades consideradas equivalentes en su significado en bases de datos

de lenguas diferentes, permitiendo así pasar de términos de un idioma a términos de otro.

3 http://www.illc.uva.nl/EuroWordNet4 http://www.globalwordnet.org

8.


Cada wordnet local de EWN fue construido de forma independiente con los

recursos disponibles en cada lengua, formando así un conjunto demódulos independientes. La

conexión entre todos estos sistemas autónomos se hizo a través del Índice Interlingüa.

Cada índice en el ILI es un synset con una etiqueta de categoría sintáctica, una glosa y la

referencia a su origen. Los synsets de cada wordnet particular están enlazados a algún índice del

ILI. De esta forma, EWN proporciona la posibilidad de ir de una lexicalización de un concepto en

una lengua determinada a otra lexicalización de ese mismo concepto en otra lengua diferente. Por

ejemplo, partiendo del verbo español convertirse a través de su equivalente en el ILI, to become, se

puede llegar a su correspondiente en italiano, diventare:

convertirse (esp) Eq_Near_Synonym to become(ILI) Eq_Near_Synonym (it) diventare

En la siguiente figura podemos ver cual es la arquitectura que usa EuroWordNet, y como se

conectan los WordNets locales de diferentes idiomas a través del Índice InterLingüa.

9.


En la Imagen 3 se emplea el sentido drive para mostrar como se utilizan los diferentes tipos

de enlaces de EWN. En este caso tenemos cuatro de los wordnets locales (ingles, holandés, italiano,

español), para cada uno de ellos existe su correspondiente synset para el sentido que se está

utilizando de ejemplo, en español sería conducir, en italiano guidare, en holandés rijden y en inglés

drive. Estos synsets se relacionan con otros dentro de sus wordnets mediante enlaces dependientes

del lenguaje (en la figura se identifican con el número romano III), por ejemplo, en el caso del

español, conducir estaría conectado mediante este tipo de enlaces con transitar, cabalgar, ... Por

otra parte cada uno de ellos tiene un enlace desde su lenguaje específico a su correspondiente

registro del Indice Interlingüa (número II). De este modo, al estar los cuatro synsets conectados al

mismo registro ILI, podemos saber que todos representan el mismo sentido. Además, existe otro

tipo de enlace independiente del lenguaje (número I) desde este registro ILI a la información

adicional que ofrecen las distintas ontologías sobre este sentido. Así, cada uno de los synsets de los

10.

Imagen 3: Arquitectura de EuroWordNet


cuatro wordnets del ejemplo, adquieren esas características representadas en Domain-Ontology y

Top-Ontology, sin la necesidad de tener un enlace a las mismas.

2.3- Proyecto Meaning

Meaning5 (Rigau et al., 2002) representa uno de los proyectos más ambiciosos relacionados

con EWN y WN. Su objetivo principal consiste en la adquisición automática del conocimiento

lingüístico (en especial, del conocimiento semántico o conceptual) a partir de la Web y construcción

de recursos léxicos multilingües que sirvan de soporte para una desambiguación semántica

automática más eficiente, ya que los recursos léxicos existentes no proporcionan toda la

información necesaria para poder desambiguar con éxito la semántica de los textos.

En concreto, el proyecto se centró en los wordnets para 5 idiomas europeos: inglés, italiano,

español, catalán y euskera. Se pretendía enriquecer su estructura con nueva información léxico-

semántica extraída automáticamente de la web. Como resultado de este trabajo se generaron varios

resultados:

• Conjunto de herramientas para la adquisición automática de conocimiento semántico a

partir de grandes colecciones de textos disponibles en la web.

• Herramientas para el enriquecimiento automático de EWN con el conocimiento que una

el nivel sintáctico con el semántico: aplicaciones para la adquisición de la terminología

perteneciente a un dominio específico, la identificación y la extracción de sentidos nuevos y de

agrupaciones de sentidos relacionados, la adquisición de etiquetas de dominio, de alternancias de

diátesis, marcos de subcategorización, restricciones selectivas y de algunas relaciones léxico-

semánticas específicas.

• Un sistema de desambiguación semántica automática para las lenguas incluidas en el

proyecto basado en algoritmos de aprendizaje automático capaces de modelar el comportamiento de

cada sentido a partir de textos semánticamente anotados y textos no anotados.

El Repositorio Central Multilingüe (MCR), fue desarrollado como parte de este

proyecto. Su principal objetivo fue el de mantener la compatibilidad entre los

5 http://www.lsi.upc.es/~nlp/meaning/meaning.html

11.


diferentes wordnets y poder exportar, de forma consistente, el conocimiento adquirido

para un idioma en particular al resto de idiomas. Actualmente constituye probablemente

la base de conocimiento léxico multilingüe más extensa y más rica jamás construida.

2.3.1- Multilingual Central Repository (MCR)

El MCR6 (Multilingual Central Repository) (Atserias et al., 2004) es el resultado de la fusión

de distintos recursos (diversas versiones de WordNet, ontologías y bases del

conocimiento) que se llevó a cabo dentro del proyecto MEANING. Además mantiene el modelo

utilizado en EWN, cuya arquitectura incluye InterLingual Index (ILI), WordNet Domains7 y Top

Concept Ontology8.

Su versión final esta integrada por wordnets para cinco idiomas diferentes

(inglés, italiano, español, catalán y euskera) y contiene 1642384 relaciones semánticas

únicas entre conceptos. También está enriquecido con 466972 propiedades semánticas

extraídas de otras fuentes, como WordNet Domains, Top Concept Ontology o SUMO9.

Para poder interactuar con el MCR se desarrolló WEI (Web Eurowordnet Interface) que es

una interfaz web que permite hacer consultas en el sistema. Se puede ver un ejemplo en la siguiente

imagen.

6 http://www.lsi.upc.es/~nlp/meaning/demo/demo.html7 http://wndomains.itc.it/wordnetdomains.html8 http://www.globalwordnet.org/gwa/ewn_to_bc/ewnTopOntology.htm9 http://suo.ieee.org/SUO/SUMO/index.html

12.


Esta imagen representa una consulta sobre el wordnet English_1.6 de la palabra church. Los

resultados corresponden a los sentidos de esa palabra en los wordnets English_1.6 (en azul) y

Spanish_1.6 (en verde). A la izquierda de los sentidos aparece el conocimiento ontológico (Wn-

Domains, TCO,...) asignado a cada sentido. En este caso, como se han seleccionado las opciones

Gloss y Rels, el sistema también ha devuelto una glosa (aparece a la derecha) y el número y tipo de

relaciones que tiene cada sentido.

2.4- SSI-Dijkstra

El software SSI-Dijkstra es una versión del algoritmo SSI (Structural Semantic

Interconnections), que basándose en el conocimiento iterativo está orientado a la desambiguación

de palabras (WSD: Word Sense Disambiguation). El algoritmo SSI es muy simple y consiste en un

paso de inicialización y en ciertos pasos iterativos (ver algoritmo debajo).

Dada W, una lista ordenada de palabras que deben ser desambiguadas, el algoritmo SSI

funciona de la siguiente manera: en el paso de inicialización, todas las palabras monosémicas son

incluidas en una lista I que contiene las palabras que ya están interpretadas, mientras que las

13.

Imagen 4: Ejemplo de una consulta en WEI


palabras polisémicas son incluidas en la lista P, donde estarán todas las palabras pendientes de

desambiguar. En cada paso, la lista I se usa para desambiguar una palabra de la lista P,

seleccionando el sentido de palabra que más se aproxima de de las palabras ya desambiguadas de la

lista I. Una vez seleccionado el sentido, esa palabra la quitamos de la lista P y la incluimos en la

lista I. El algoritmo termina cuando ya no quedan más palabras pendientes de desambiguar en la

lista P.

SSI (T: list of terms)for each {t ∈ T} do I[t] = ∅ if t is monosemous then I[t] := the only sense of t else P := P ⋃ {t} end ifend forrepeat P' := P for each {t ∈ P} do BestSense := ∅ MaxValue := 0 for each {sense s of t} do W[s] := 0 N[s] := 0 for each {sense s' ∈ I} do w := DijkstraShortestPath(s,s') if w > 0 then W[s] := W[s] + (1/w)

N[s] := N[s] + 1 end if end for if N[s] > 0 then NewValue := W[s]/N[s] if NewValue > MaxValue then MaxValue := NewValue BestSense := s end if end if end for if MaxValue > 0 then I[t] := BestSense P := P \ {t} end if end foruntil P ≠ P'

14.


return (I,P);

Inicialmente, la lista de palabras interpretadas I debería incluir los sentidos de las palabras

monosémicas de W10.

En relación a la proximidad de un synset con el resto de synsets de I, se usa el conocimiento

que ya tenemos disponible para construir un grafo que contiene 99,635 nodos (synset) y 636,077

arcos. Este grafo incluye una serie de relaciones directas sacadas WordNet y eXtended WordNet.

Dijkstra es un algoritmo muy eficiente para calcular cual es la distancia más corta entre dos nodos

cualquiera del grafo.

SSI-Dijkstra tiene unas propiedades muy interesantes, por ejemplo, es capaz de calcular de

forma eficiente cual es la distancia más corta entre dos nodos del grafo. Esto es, el algoritmo nos

proporciona una respuesta sobre si la distancia mínima entre dos nodos es corta o larga. De hecho,

el algoritmo compara las distancias entre los synsets de una palabra con los synsets de las palabras

ya interpretadas en I.

Además, esta aproximación es independiente del lenguaje. El mismo grafo se puede usar

para diferentes idiomas si existen palabras conectadas a WordNet para ese lenguaje.

2.5- SSI-Dijkstra+

SSI-Dijkstra+ es una versión extendida de SSI-Dijkstra. Se puede comprobar que, en

ausencia de monosémicos, SSI-Dijkstra desconoce completamente como actuar, ya que depende

directamente del conjunto I de palabras interpretadas para dar una solución. En estos casos, el

algoritmo no tiene solución y pueden ocurrir dos cosas: que el algoritmo se quede infinitamente

buscando una solución (inexistente) o que el algoritmo detecte que no hay solución y tome las

medidas adecuadas para notificárselo al usuario. SSI-Dijkstra+ es una versión mejorada del

algoritmo SSI-Dijkstra en dos aspectos.

En primer lugar, SSI-Dijkstra+ obtiene solución cuando los conjuntos de palabras por

procesar no tienen monosémicos. Para ello, obtiene la palabra menos ambigua (por norma general,

10 El algoritmo SSI-Dijkstra general no sabría que hacer en ausencia de monosémicos. Para este caso particular, véase SSI-Dijkstra+, más adelante.

15.


esta palabra es la que menor grado de polisemia posee, dicho de otro modo, la que menos sentidos

asociados tiene a sí misma) y realiza una hipótesis acerca de su significado más correcto. La

hipótesis se obtiene a partir del resultado de dos algoritmos diferentes: ASI y FSI.

ASI: Se basa en hallar la distancia mínima acumulada desde un sentido de la palabra hasta el

resto de sentidos de las palabras de P. El sentido más probable de la palabra a tratar será aquel que

tenga menor dicha distancia.

FSI: Se basa en hallar la distancia mínima acumulada desde un sentido de la palabra hasta

sólo el primer sentido de cada palabra de P. El sentido más probable de la palabra a tratar será aquel

que tenga menor dicha distancia.

Estos dos algoritmos siempre obtienen solución aún cuando no hay monosémicos ya que

aseguran que el conjunto de palabras interpretadas I no esté vacío antes del paso iterativo.

En segundo lugar, SSI-Dijkstra+ pretende mejorar la precisión de los resultados obtenidos a

partir de la aplicación del algoritmo incluyendo para ello dos nuevos algoritmos durante el paso

iterativo: ASP y FSP. Nótese que los dos algoritmos tienen en cuenta el conjunto de palabras

interpretadas I para obtener su resultado. La diferencia entre ellos, se explica a continuación:

ASP: Se basa en hallar la distancia mínima acumulada desde un sentido de la palabra por

interpretar hasta cada uno de los sentidos presentes en I y el resto de sentidos de las palabras de P.

El sentido más probable de la palabra a tratar será aquel que tenga menor dicha distancia.

FSP: Se basa en hallar la distancia mínima acumulada desde un sentido de la palabra por

interpretar hasta cada uno de los sentidos presentes en I y sólo el primer sentido de cada palabra de

P. El sentido más probable de la palabra a tratar será aquel que tenga menor dicha distancia.

Podría ser también que por razones de precisión nos interesara no utilizar el conjunto P de

palabras no interpretadas (podrían introducir error en algunos resultados aún no desambiguados), de

la misma forma que incluir P podría dar resultados más precisos. La inserción de P o no a la hora de

desambiguar palabras es una cuestión difícil (es un claro arma de doble filo) que fue estudiada de

forma empírica (Laparra et al., 2009). Los resultados de dicho estudio fueron que al parecer los

verbos, se desambiguaban bastante mejor utilizando el FSP; mientras que el resto de palabras se

16.


desambiguaban con un resultado de precisión mejor sin tener en cuenta el conjunto de palabras sin

desambiguar P.

En lo que respecta a este proyecto, se ha decidido utilizar FSI para la parte de inicialización

(sólo si el conjunto I está vacío después de la inicialización inicial) y para la parte iterativa, se ha

decidido usar FSP (sólo para verbos) o el propio algoritmo SSI-Dijkstra (nombres, adjetivos y

adverbios). Esto no es más que un convenio entre profesor y alumno intentando optimizar tiempo y

esfuerzo, pero cada uno es libre de utilizar el algoritmo SSI-Dijkstra+ de forma que mejor se

amolde a sus necesidades.

2.6- UKB11

UKB es un software desarrollado por el grupo IXA12 de la universidad del País Vasco para

trabajar en el campo de la desambiguación de palabras. Codificado en C++, se compone de clases

para creación, lectura y procesamiento de grafos a partir de ficheros los cuales contienen la

información necesaria para la desambiguación de palabras.

Teniendo en cuenta lo anterior, UKB ha sido uno de los pilares sobre los que se ha

sustentado este proyecto debido a sus facilidades para trabajar con bases de conocimiento basadas

en grafos. Por ejemplo, es necesario crear un fichero con la estructura del grafo sobre el que se va a

trabajar. UKB proporciona facilidades para ello, así como para procesar el fichero (lectura,

búsqueda, inserción, etc.). Entre otras razones, esta ha sido una de las más importantes para elegir

este software en este proyecto. Se debe tener en cuenta también que el propio UKB trae diferentes

ficheros con diferentes versiones del grafo de WordNet para trabajar con él. Así mismo, tiene

también un diccionario para poder enlazar cada palabra a sus sentidos asociados (y las utilidades de

uso de dicho diccionario).

Es importante también señalar que UKB proporcionaba casi todas las herramientas

necesarias para este proyecto, pero no todas. Como uno de los objetivos del proyecto era intentar

reutilizar al máximo el código propio de UKB, se han tenido que introducir utilidades y métodos

que antes no tenía. Esto es algo importante a tener en cuenta, ya que este proyecto sin UKB no

funciona pero tampoco lo hace con una versión errónea del mismo (actualmente, 0.1.5r1 aunque

faltaría actualizar la versión).

11 http://ixa2.si.ehu.es/ukb/12 http://ixa.si.ehu.es/Ixa

17.


2.7.- FrameNet13

FrameNet (Baker et al., 1988) es un recurso semántico bastante rico que contiene

descripciones y anotaciones del corpus de palabras del inglés siguiendo el paradigma de los Frames

Semánticos (Fillmore, 1976). En frames semánticos, un Frame corresponde a un escenario que

involucra la interacción de un conjunto de participantes típicos, jugando un rol específico en el

escenario. FrameNet agrupa las palabras, o las unidades léxicas (LUs de ahora en adelante) en

clases semánticas coherentes o frames, y cada frame está bastante bien caracterizado por una lista

de participantes o elementos léxicos (LEs de ahora en adelante). Los diferentes sentidos de una

palabra se representan en FrameNet asignándole diferentes frames.

Actualmente, FrameNet representa más de 10.000 LUs y 825 frames. Más de 6.100 de esos

LUs también proveen ejemplos de corpus lingüísticamente anotados. Partiendo de eso, sólo 9.360

de los LUs son reconocidos por WordNet (aproximadamente el 92 %), correspondientes a 708

frames.

Los LUs de un frame pueden ser nombres, verbos, adjetivos y adverbios que representen un

conjunto de significados coherente y cercanamente relacionado y que puede ser visto como un

pequeño campo semántico. Por ejemplo, el frame EDUCATION_TEACHING contiene LUs

referidos a la actividad de la enseñanza y de sus participantes. Está evocado por LUs como

student.n, teacher.n, learn.v, instruct.v, study.v, etc. El frame también define roles del núcleo

semántico (o FEs) como por ejemplo: STUDENT, SUBJECT o TEACHER que son participantes

semánticos del frame y sus correspondientes LUs (ver ejemplo debajo).

[Bernard Lansky]STUDENT studied [the piano]SUBJECT [with Peter Wallfisch]TEACHER

13 http://framenet.icsi.berkeley.edu/

18.


3.- Elección tecnológica

No hay gran cosa a comentar en cuanto a elección tecnológica, ya que dadas las

especificaciones del proyecto, era necesario trabajar con unas herramientas y tecnologías

determinadas. Sin embargo, se han podido hacer algunas elecciones que son importante señalar.

3.1.- Pre-requisitos

Antes de pasar a comentar las decisiones acerca de la tecnología utilizada para el proyecto,

es necesario comentar alguno de los pre-requisitos para poder utilizar y/o desarrollar con este

software.

En primer lugar, es importante que la máquina sea capaz de compilar C++. Ya que el

proyecto completo está hecho en C++, este es un pre-requisito bastante claro a tener en cuenta.

También es importante saber que el proyecto no tiene sentido sin estar junto con UKB, ya

que no sólo utiliza las clases proporcionadas por este software, sino que está bastante integrado y es

imposible trabajar con él de forma autónoma.

Por último, es necesario tener en cuenta también que tanto UKB como el proyecto

necesitarán librerías BoostGraph de C++.

Una vez instalado todo esto, uno debería ser capaz de poder trabajar con este proyecto. Por

lo que, los requisitos inamovibles respecto a elección tecnológica es el uso de C++, UKB y

BoostGraph para este proyecto.

3.2.- Desarrollo: la máquina personal del alumno

3.2.1.- Sistema operativo

El sistema operativo elegido para el desarrollo del proyecto ha sido Linux Ubuntu 10.04. Se

ha elegido un SO Linux frente a cualquier otra opción debido a las facilidades que el propio sistema

ofrece para desarrollar en C++. De igual forma, se ha elegido Ubuntu debido a que el alumno ya

estaba familiarizado de algún modo con sistemas operativos de familia Debian y claramente, era

más fácil trabajar en él (sin tener que aprender los entresijos de un sistema operativo diferente).

19.


3.2.2.- Entorno de desarrollo

No se ha utilizado un entorno de desarrollo en sí, ya que una vez hecho un esqueleto general

no era necesario cargar todo un entorno de desarrollo completo (como por ejemplo Eclipse o

NetBeans), y simplemente se ha utilizado un editor de textos para ir haciendo cambios sobre dicho

esqueleto.

El esqueleto general se ha hecho en NetBeans 6.8, ya que el alumno lo conocía y parece más

cómodo que otros entornos para trabajar con C++. Respecto al editor de textos, se ha usado el gedit

de Linux, que es un editor de textos simple pero potente.

3.3.- Documentación

Como no todo es desarrollo en un proyecto de final de carrera, se deja también una relación

del software utilizado para tareas no relacionadas directamente con la implementación, pero sí con

el proyecto.

Cabe destacar entre otras cosas que se ha hecho especial hincapié en intentar utilizar el

mayor número de herramientas libres posible (recordemos que el sistema operativo sobre el que

trabaja el alumno es un Linux), por lo que se ha preferido el paquete ofimático OpenOffice frente al

Office, entre otros.

3.3.1.- OpenOffice Writer. Memoria

OpenOffice.org Writer es un procesador de texto multiplataforma que forma parte del

conjunto de aplicaciones de la suite ofimática OpenOffice.org. Además de otros formatos

estándares y ampliamente utilizados de documentos, puede abrir y grabar el formato propietario

.doc de Microsoft Word casi en su totalidad. El formato nativo para exportar documentos es XML.

También puede exportar a ficheros PDF nativamente sin usar programas intermedios.

3.3.2.- OpenOffice Impress. Transparencias

OpenOffice.org Impress es un programa de presentación similar a Microsoft PowerPoint. Es

parte de la suite de oficina de OpenOffice.org desarrollada por Sun Microsystems. Puede exportar

presentaciones como archivos SWF de Adobe Flash permitiendo que sean ejecutados en cualquier

20.


computadora con Adobe Flash Player instalado. También incluye la capacidad de crear archivos

PDF. Impress sufre de la carencia de diseños de presentación listos para usarse. Sin embargo, se

pueden obtener fácilmente en Internet plantillas de terceros.

3.3.3.- Gantt Project. Diagrama de Gantt

Gantt Project es una herramienta de escritorio multiplataforma para la planificación y

gestión de proyectos. Funciona en Windows, Linux y MacOSX y es gratis y de código abierto.

Fundamentalmente, se utiliza para hacer diagramas de Gantt aunque permite hace también

diagramas PERT y tablas de asignación de recursos, además de otras cosas útiles. Permite además

exportar sus diagramas en formato de imagen, lo cual será bastante interesante a la hora de

integrarlos en esta memoria.

21.


4.- DOP: Documento de Objetivos del Proyecto

4.1.- Objetivos

Este proyecto surge de la necesidad de disponer del algoritmo SSI-Dijkstra en C++. Como se

ha explicado antes, SSI-Dijksta es un algoritmo de desambiguación de palabras, pero este algoritmo

está inicialmente escrito en Perl. El problema es que el script Perl que contiene este algoritmo

utiliza una interfaz Perl/C++ para acceder a las librerías BoostGraph y poder utilizar el algoritmo de

Dijkstra14. Se pensó en traducir este algoritmo de Perl a C++ para intentar obtener una ganancia en

la eficiencia del programa (evitando así acceder a la interfaz para las librerías BoostGraph y

pudiendo acceder directamente a éstas).

En paralelo, se trabaja con un software de desambiguación de palabras basadas en grafos

explicado anteriormente (UKB) y el cual tiene codificados varios métodos de desambiguación, pero

no SSI-Dijkstra en concreto.

Por lo que, el objetivo del proyecto es doble: por un parte, se intenta traducir el algoritmo

SSI-Dijkstra de Perl a C++ y por otra parte se intenta añadir dicho algoritmo al software de UKB

para poder usarlo en tareas de desambiguación de palabras.

4.2.- Método de trabajo

Durante el proyecto, el método de trabajo será el siguiente.

El profesor irá marcando objetivos que el alumno debe solventar en un lapso de tiempo

acordado entre ambos. El alumno dispone de medios (E-mail del profesor, documentación

específica, Internet, etc.) para solventar sus dudas y en caso de no poder llevar la tarea a tiempo se

pospondrá hasta que el alumno lo tenga dispuesto o en su defecto, se avisará al profesor y se

acordará un día para realizar una reunión y poder así solventar dudas y avanzar en el estado el

proyecto.

Las reuniones serán un punto para declarar nuevos objetivos y observar la evolución de los

realizados (o no) hasta el momento, por lo que es importante que el alumno lleve todo el material

14 http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

22.


posible en relación a su proyecto. Si alguno de los objetivos planteados no está correctamente

realizado, el alumno tiene la responsabilidad de intentar completarlo de forma adecuada para una

próxima ocasión, así como el profesor intentará guiar al alumno en este hecho. Según se vaya

progresando en la realización del proyecto, los objetivos irán acercándose cada vez más a la

finalización del mismo, y así hasta el final.

En caso de estancamiento o problemas relacionados con el proyecto, se seguirá el plan de

contingencia abajo descrito y en la mayoría de los casos se avisará al profesor, para solventar dudas

o realizar reuniones; profesor y alumno deberán acordar lo más adecuado.

4.3.- Alcance

4.3.1.- Recursos humanos

Los recursos humanos con los que cuenta este proyecto son el alumno y el profesor asignado

como director de proyecto. Es responsabilidad del alumno seguir las indicaciones del profesor

respecto a objetivos, tareas y plazos. Es responsabilidad del profesor orientar al alumno en la

ejecución de los objetivos para alcanzar el éxito lo antes posible.

4.3.2.- Recursos materiales

El alumno dispone de un ordenador personal portátil con un sistema operativo Linux

instalado (en concreto, una distribución Ubuntu) para el desarrollo del proyecto. El alumno dispone

también de material de oficina (véase como: papel, bolígrafos, impresora, etc) para obtener e

imprimir documentación, realizar esquemas, croquis, etc. Se dispone también de una unidad de

disco extraíble USB para realizar copias de seguridad, así como un disco duro externo en el que se

puede realizar una segunda copia de seguridad en caso de necesitarlo.

El profesor dispone de un ordenador de sobremesa con acceso a Internet, y del mencionado

anteriormente material de oficina, por lo que se podrán hacer esquemas, dibujos, etc. en caso de ser

necesario.

4.3.3.- Recurso económico

23.


Al ser un proyecto de final de carrera, y no haber recurso económico de por medio, el coste

total del proyecto será nulo, presuponiendo que los partícipes del proyecto tenían ya todo el material

independientemente y anteriormente a este proyecto. De todas formas, todo el software utilizado

para desarrollar el proyecto, así como para escribir la documentación y la memoria es código

abierto, y, más importante para este apartado, gratis. Por lo que en cualquier caso, el alumno no ha

tenido que gastar dinero en licencias de ningún tipo ya que el software utilizado no es ni privativo ni

cuesta dinero.

4.3.4.- Diagrama EDT (Estructura de descomposición del trabajo)

En la siguiente hoja se adjunta el diagrama correspondiente a la Estructura de

Descomposición del Trabajo planificada para este proyecto. En la siguiente, hay un desglose de las

tareas, así como una pequeña descripción de cada una de ellas y una referencia temporal que indica

cuánto tiempo estimado transcurrirá en cada una de las tareas.

24.

Procesos formativosProcesos tácticos Procesos operativos

PFC

Pruebas

Diseño

Instalación de herramientas

Implementación

Captura derequisitos

Implementación

Análisis

UKB

Análisis

2ª Iteración

Gestión

1ª Iteración


Diseño

Pruebas

3ª Iteración

Reuniones

Planificación

Lenguaje deprogramación C++

Memoria

Presentación

BoostGraph

Lenguaje de programación Perl

Pruebas

Diseño

Implementación


Análisis


4.3.5.- Proyecto de Final de Carrera (PFC)

Procesos formativos

1. Lenguaje de programación: Perl

Descripción: Aprendizaje básico por parte del alumno del lenguaje de programación

Perl para lograr entender el programa inicial propuesto para la traducción a C++.

Tiempo estimado: 10 horas

2. Lenguaje de programación: C++

Descripción: Aprendizaje básico por parte del alumno del lenguaje de programación

C++ para poder llevar a cabo el proyecto. Esto es estrictamente necesario ya que el alumno lo

desconoce.


3. BoostGraph

Descripción: Aprendizaje básico del uso de la librería BoostGraph en C++ y de sus

aplicaciones para este proyecto (Algoritmo de Dijkstra, etc)


4. UKB

Descripción: Revisión del código y la documentación disponible de UKB para

conseguir entender cómo y por qué utilizar este software.


5. Memoria

Descripción: Realización de la memoria como colofón al proyecto de final de carrera

desarrollado por el alumno.


6. Presentación

Descripción: Realización de las transparencias y preparación de la presentación de

finalización del proyecto.

26.


Tiempo estimado: 5 horas.

Procesos tácticos

1. Planificación

Descripción: Realización de las tareas de planificación (y replanificación en su caso)

del proyecto, entre otras, el propio DOP.


2. Gestión

Descripción: Realización de las tareas de gestión del proyecto.


3. Instalación de las herramientas

Descripción: Instalación de las herramientas (tácticas, por ejemplo: Gantt Project; u

operativas, por ejemplo: UKB)


4. Reuniones

Descripción: Reuniones con el director de proyecto, sea para tratar sobre temas

tácticos (planificación y gestión, memoria, etc) u operativos (el propio código del proyecto)


Procesos operativos

1. Primera iteración

Descripción: Esta primera iteración cubre todos los aspectos operativos desde el

inicio del proyecto hasta la obtención de una función que obtenga la distancia mínima en un grafo

de dos de sus nodos.

(a) Captura de requisitos

Descripción: Captura de requisitos de la primera iteración.


(b) Análisis

27.


Descripción: Análisis de la primera iteración


(c) Diseño

Descripción: Diseño de la primera iteración.


(d) Implementación

Descripción: Implementación de la primer iteración.


(e) Pruebas

Descripción: Pruebas de la primera iteración.


2. Segunda iteración

Descripción: Esta segunda iteración cubre todos los aspectos operativos desde la

finalización de la primera iteración hasta la obtención de una función que realice el algoritmo

SSI_Dijkstra sobre un contexto.


Descripción: Captura de requisitos de la segunda iteración.


(b) Análisis

Descripción: Análisis de la segunda iteración.


(c) Diseño

Descripción: Diseño de la segunda iteración.


(d) Implementación

Descripción: Implementación de la segunda iteración.

28.



(e) Pruebas

Descripción: Pruebas de la segunda iteración.


3. Tercera iteración

Descripción: Esta tercera iteración cubre todos los aspectos operativos desde la

finalización de la segunda iteración hasta la finalización del proyecto (obtención de funciones que

realicen el SSI-Dijkstra o el SSI-Dijkstra+ según petición del usuario).


Descripción: Captura de requisitos de la tercera iteración.

Tiempo estimado: 1 hora.

(b) Análisis

Descripción: Análisis de la tercera iteración.

Tiempo estimado: 1 hora.

(c) Diseño

Descripción: Diseño de la tercera iteración.


(d) Implementación

Descripción: Implementación de la tercera iteración.


(e) Pruebas

Descripción: Pruebas de la tercera iteración


4.4.- Planificación temporal: Diagrama de Gantt

29.


En la siguiente hoja, se adjunta el diagrama de Gantt de tareas planificadas para este

proyecto. Junto a cada una de las barras de las tareas, a la derecha, puede verse el día de inicio y el

día final estimado de cada una de las tareas; así como la duración total de cada una de ellas, lo cual

puede verse debajo.

30.


4.5.- Plan de contingencia

En la siguiente tabla se presenta la relación de riesgos posibles durante la ejecución de las

tareas del proyecto. El plan de contingencia a seguir en cada uno de los casos, viene descrito debajo.

Riesgo Probabilidad Consecuencia

Dificultad en entender Medio Bajo

Pérdida de la documentación Muy bajo Bajo

Indisponibilidad para reunir Bajo Bajo

Retraso en la tarea Medio Medio

Ordenador estropeado Medio Bajo

Pérdida de datos Bajo Medio

Problemas en manejar software Bajo Medio

Tabla 1: Tabla de riesgos

Dificultad en entender

Riesgo: Dificultad del alumno para entender algo relacionado con el proyecto que le haga

perder excesivo tiempo, con lo que le llevaría al riesgo de no poder realizar la tarea a tiempo.

Solución: El alumno le informará al profesor encargado del proyecto del problema, y

acordarán realizar alguna reunión para aclarar las dudas o le informara dónde puede encontrar

información añadida para solucionarlo o ampliaran el plazo de la tarea para que tenga más tiempo

para hacerlo.

Pérdida de la documentación

Riesgo: El alumno pierde documentación o acceso a la documentación que dispone para la

formación que dispone.

Solución: La mayoría de la documentación del alumno es física (papel escrito). En

cualquier caso, hay un “backup” de sitios de donde se ha obtenido dicha información en el correo

del alumno, ya que el profesor le envía un correo electrónico por reunión con los aspectos más

relevantes de la reunión, incluyendo enlaces a documentación interesante.

32.


Indisponibilidad para reunir

Riesgo: El alumno o el profesor encargado no pueden acudir a una reunión concertada por

causas tales como enfermedad, causas personales, trabajo...

Solución: Se notificará dicha indisponibilidad a la otra parte, y en su caso, se acordará otro

horario (fecha y hora) para la reunión.

Retraso en la tarea

Riesgo: El alumno no ha conseguido realizar la tarea a tiempo.

Solución: Entre el alumno y el profesor acuerdan un nuevo plazo para la ejecución de la

tarea, así como posponen nuevos objetivos.

Ordenador estropeado

Riesgo: El ordenador del alumno sufre daños parciales o totales

Solución: El profesor y el alumno llegarán a un acuerdo. El profesor puede prestarle un

ordenador de forma temporal, así como el alumno, puede usar los ordenadores de uso público de la

facultad de Informática.

Pérdida de datos

Riesgo: Se pierden los datos guardados en el ordenador.

Solución: Se recupera el último “backup” de la memoria extraíble USB del alumno y se

intenta devolver el proyecto al estado avanzado anterior.

Problemas en manejar software

Riesgo: Problemas en manejar software que está utilizando el alumno, debido a

desconocimiento del mismo.

Solución: Intentar buscar toda la documentación posible por Internet, por los libros de la

biblioteca, manuales... El profesor encargado le podrá orientar al alumno sobre que material le

convendría.

33.


4.6.- Análisis de factibilidad

Una vez conocidas las tareas a realizar para la finalización del proyecto y el tiempo

estimado en cada una de ellas, también conocido la posibilidad y descripción de los riesgos de las

tareas y sus posibles soluciones; creemos que el proyecto parece factible en el intervalo de tiempo

dado.

34.


5.- Captura de requisitos

5.1.- Motivación

Este proyecto surge de la necesidad de disponer del algoritmo en C++ del SSI-Dijkstra y del

SSI-Dijkstra+. Esta necesidad, viene establecida por lo comentado ya anteriormente: el algoritmo

original, escrito en Perl, no es capaz de utilizar de forma nativa las librerías BoostGraph; sino que

requiere de una interfaz entre el programa y las librerías (interfaz para convertir Perl en C++) para

poder utilizarlas. Se pretende mejorar la eficiencia del algoritmo eliminando este paso intermedio,

para lo cual es requisito claro escribir el algortimo (tanto SSI-Dijkstra como SSI-Dijkstra+) en C++.

En paralelo, se trabaja con la herramienta ya mencionada UKB, la cual está escrita en C++ y

utiliza también las librerías BoostGraph. UKB es una herramienta usada en la desambiguación de

palabras por métodos basados en grafos (como SSI-Dijkstra), pero que no implementa el SSI-

Dijkstra.

Se pensó en aprovechar ambas cosas para generar un algoritmo en C++ que trabajara con

UKB para, dar un mejor servicio en cuanto al tiempo y calidad de respuesta desambiguando

palabras y de paso conseguir que UKB trabajara con SSI-Dijkstra también. Por lo que, era también

requisito importante del proyecto que SSI-Dijkstra fuera capaz de entender, procesar y trabajar con

la misma entrada que UKB y que SSI-Dijkstra diera una salida de formato idéntica a la de UKB

(por las aplicaciones que puedan trabajar con la salida de UKB para obtención de otros datos...).

5.2.- Requisitos específicos

Además de todo eso, se vio una serie de necesidades de la aplicación en sí, no relacionadas

con el objetivo inicial del proyecto, pero que podrían ayudar a la eficiencia (mejora temporal) y

eficacia (mejora de resultados) del programa.

En primer lugar, era necesario algo que fuera capaz de ordenar las palabras del conjunto de

forma que al utilizar SSI-Dijkstra+ las primeras palabras fueran “las menos polisémicas”15; de

hecho el objetivo es intentar maximizar la eficacia del programa desambiguando primero las menos

ambiguas, haciendo que el conjunto de palabras quede ordenado de forma creciente en cuanto al

15 Se define como palabra “menos polisémica” aquella que tiene un menor número de sentidos asociados. A este método de ordenación se le refiere también como ordenación por grado de polisemia.

35.


grado de polisemia. Además, aprovechando las propiedades del formato de la entrada de UKB, se

quiso dar la posibilidad a que el usuario pudiera definir el orden en el que las palabras eran

procesadas y surgió la idea de crear una ordenación explícita.

En segundo lugar, era requisito que el programa pudiera trabajar con SSI-Dijkstra o SSI-

Dijkstra+ indistintamente según decisión propia del usuario. De esa forma, podemos obtener

resultados de fiabilidad para ambos algoritmos y analizar en qué casos es mejor uno que otro, o

también podemos obtener respuestas de SSI-Dijkstra+ en casos en los que SSI-Dijkstra no nos las

daría. También, se observó un método para obtener respuestas de forma más rápida en los sucesivos

cálculos de las distancias entre nodos del grafo. Este método lo denominaremos método con

“optimización”, mientras que la forma normal de hacerlo la denominaremos método sin

“optimización” (los detalles técnicos vienen descritos en el apartado de implementación).

En tercer lugar, es interesante que el usuario pudiera utilizar grafos definidos por él mismo,

de manera que pudiera utilizar las herramientas de UKB para crear el grafo siguiendo un patrón

definido por el propio usuario (con o sin pesos en los arcos). Por lo que también era requisito del

proyecto que el usuario pudiera decidir fácilmente el grafo que quería utilizar.

5.3.- Resumen

En resumen, los requisitos explícitos del proyecto son:

1. Codificar los algoritmos SSI-Dijkstra y SSI-Dijkstra+ en C++ utilizando las librerías

BoostGraph y el software UKB para ello.

2. Conseguir que SSI-Dijkstra y SSI-Dijkstra+ sean capaces de entender el formato de la

entrada de UKB, así como también sean capaces de generar una salida de formato idéntica a la de

UKB, que otros posibles programas sean capaces de comprender.

3. Poder elegir el método de ordenación, (no ordenado, por grado de polisemia o

explícito), el algoritmo a aplicar (SSI-Dijkstra o SSI-Dijkstra+) y la forma específica de cálculo de

las distancias entre nodos del grafo (con “optimización” o sin “optimización”).

4. Dar la posibilidad al usuario de utilizar en la desambiguación sus grafos generados

mediante UKB, tengan o no tengan pesos en los arcos del mismo.

36.


6.- Análisis

Se puede observar que este proyecto tiene bastante poco peso en cuanto a análisis (no es un

proyecto que vaya a suponer muchísima carga de desarrollo y por tanto no tenemos la necesidad de

seccionar y dividir bien el trabajo), pero sí hay algunas cosas que podrían comentarse antes de

seguir a otras cuestiones.

6.1.- Sobre UKB

Como se ha comentado anteriormente, UKB ha sido un software fundamental para el

proyecto, pero que a pesar de todo no cumplía del todo con las necesidades demandadas por la

aplicación desarrollada. Podría haberse intentado utilizar estructuras propias para algunas cosas,

pero ya que existía la obligación de acabar tocando el código del propio UKB (ante la imposibilidad

de desarrollar el proyecto sin algunas cuestiones que UKB no proporcionaba en su versión actual),

al final se pensó que era bastante mejor intentar re-aprovechar al máximo el propio UKB y definir

allí mismo los métodos que nos proporcionaban la información que necesitábamos. Por tanto, hay

bastantes semejanzas entre el código actual y el que podríamos encontrar si esta aplicación hubiera

estado integrada directamente en UKB, pero, también hay diferencias y ahí es obviamente donde

debemos hacer hincapié; ya que aquellos que hayan trabajado con UKB no tienen por qué conocer

la forma concreta de utilizar estas herramientas en el propio SSI-Dijkstra.

De forma algo más concreta, y teniendo en cuenta los requisitos que debía de cumplir la

aplicación a desarrollar, se tomaron las siguientes decisiones:

• Usar las mismas funciones, tanto de lectura de datos (del fichero de contexto) como de

escritura de datos (a la salida estándar); ya que uno de los requisitos era trabajar con un programa

cuya entrada fuera la misma que es capaz de procesar UKB y cuya salida fuera la misma que es

capaz de imprimir UKB.

• Usar para compilar los grafos el propio programa compile_kb proporcionado por UKB.

Esto facilita también el tratamiento del grafo, ya que todas las funciones de búsqueda, lectura y

tratamiento del grafo están ya implementadas para UKB.

6.2.- Sobre SSI-Dijkstra

Hay cosas a comentar que claramente recaen sobre el propio SSI-Dijkstra en sí ya que son

37.


cosas que tendremos en cuenta en la implementación final del algoritmo:

• Para capturar las diferentes posibilidades en la llamada al programa que se generará,

se usará el paquete de librerías program_options, que ya vienen integrados en BoostGraph y que

facilitan bastante utilizar diferentes opciones.

• Los métodos de ordenación se implementarán usando las opciones proporcionadas

por el propio lenguaje (el método sort de C++), en lugar de definir una función propia para ello.

Además de ser más cómodo para el programador, seguramente sea más eficiente.

38.


7.- Diseño

7.1.- Pseudocódigos

7.1.1.- Obtener_distancia

Descripción: Es un algoritmo que dados dos Kb_vertex_t (nodos del grafo en UKB) obtiene

la distancia mínima entre ellos en el KbGraph (grafo en UKB).

Pseudocódigo:

obtener_distancia(vertice1, vertice2, grafo) {

dijkstra_shortest_paths(grafo, vertice1,

predecessor_map(padres).distance_map(distancias));

N = nodos(grafo);

mi_iterador = apuntador(distancias[0]);

mientras mi_iterador != apuntador(distancias[N]) repetir

si mi_iterador = apuntador(vertice2) entonces

distancia = distancias[mi_iterador];

salir;

finsi

mi_iterador++;

finmientras

devolver distancia;

}

7.1.2.- Obtener_distancia_mas_rapido

Descripción: Es un algoritmo que dados dos Kb_vertex_t (nodos del grafo en UKB) obtiene

la distancia mínima entre ellos en el KbGraph (grafo en UKB). El cuarto parámetro es un

Kb_vertex_t para controlar que se calcule el dijkstra_shortest_paths sólo si este último parámetro

es diferente del primero.16

16 Los detalles relacionados con esto, pueden encontrarse en el apartado de Implementación

39.


Pseudocódigo:

obtener_distancia_mas_rapido(vertice1, vertice2, grafo,

vertice_anterior) {

si vertice1 != vertice_anterior entonces

dijkstra_shortest_paths(grafo, vertice1,

predecessor_map(padres).distance_map(distancias));

finsi

N = nodos(grafo);


mientras mi_iterador != apuntador(distancias[N]) repetir


distancia = distancias[mi_iterador];

salir;

finsi

mi_iterador++;

finmientras

devolver distancia;

}

7.1.3.- Mostrar_camino

Descripción: Es un algoritmo que dados dos Kb_vertex_t (nodos del grafo de UKB),

obtiene el camino mínimo entre ellos en el KbGraph (grafo en UKB) y lo muestra por pantalla.17

Pseudocódigo:

mostrar_camino(vertice1, vertice2, grafo) {

N = nodos(grafo);


mientras mi_iterador != apuntador(distancias[N]) {


vector.añadir(vertice2);

17 No es una parte del proyecto en sí, pero es una función fantástica para comprobar la validez de algunos resultados.

40.


aux_pointer = padres[aux_pointer]

mientras iterador_auxiliar != vertice1 repetir

si aux_pointer == iterador_auxiliar

entonces

vector.añadir(aux_pointer)

finsi;

finmientras;

salir;

finsi;

mi_iterador++;

finmientras;

imprimir(vector);

}

7.1.4.- SSI_Dijsktra

Descripción: Es una función que recibiendo un contexto de entrada genera una nueva

estructura de datos de contexto con las palabras del contexto de entrada desambiguadas.

Pseudocódigo:

SSI_Dijkstra (contexto, grafo) {

// Inicialización

para cada palabra ∈ contexto

caso(palabra.significados())

caso 0: // Algo extraño ha pasado

romper;

caso 1: // Palabra monosémica

I.añadir(palabra.significados()[0])

solucion.añadir(palabra)

romper;

defecto: // Palabra polisémica

P.añadir(palabra)

romper;

41.


fin-caso

fin-repetir

// Paso iterativo

si I ≠ ∅ entonces

mientras P ≠ ∅

vector_P = P[0].significados()

total = 0

synsets = 0

para cada significadoP ∈ P

para cada significado'I ∈ I

w = obtener_distancia(significadoP,

significado'I, grafo);

si w > 0

total = total + (1/w)

synsets++

fin-si

fin-para

si synsets > 0

v = total/synsets

si v > max

max = v

best = significado'I

fin-si

fin-si

fin-para

si max > 0

I.añadir(best)

solucion.añadir(new Palabra(best))

P.borrar(P[0])

fin-si

fin-mientras

fin-si

42.


devolver solucion

7.1.5.- SSI_Dijkstra+

Descripción: Es una función que recibiendo un contexto de entrada genera una nueva

estructura de datos de contexto con las palabras del contexto de entrada desambiguadas.

Pseudocódigo:

SSI_Dijkstra+ (contexto, grafo) {

// Inicialización: parte 1

para cada palabra ∈ contexto

caso(palabra.significados())

caso 0: // Algo extraño ha pasado

romper;

caso 1: // Palabra monosémica

I.añadir(palabra.significados()[0])

solucion.añadir(palabra)

romper;

defecto: // Palabra polisémica

P.añadir(palabra)

romper;

fin-caso

fin-repetir

// Inicialización: parte 2 (FSI)


palabraPtoI = P[0].significados()

i = 1

mientras i ≠ P.tamaño()

total = 0

synsets = 0

palabraP = P[i]

significadoPtoI =

43.


palabraPtoI.significados()[0]

para cada significadoP ∈ palabraP

w =

obtener_distancia(significadoP,

significadoPtoI, grafo)

si w > 0


synsets++

fin-si

fin-para

si synsets > 0

v = total/synsets

si v > max

max = v

best = significadoPtoI

fin-si

fin-si

fin-mientras

si max > 0

I.añadir(best)


P.borrar(P[0])

fin-si

fin-si

// Paso iterativo


mientras P ≠ ∅

vector_P = P[0].significados()

total = 0

synsets = 0

para cada significadoP ∈ P

para cada significado'I ∈ I

44.


w = obtener_distancia(significadoP,

significado'I, grafo)

si w > 0


synsets++

fin-si

fin-para

si P[0].pos() = 'v' // FSP

i = 1

mientras i ≠ P.tamaño()

palabra = P[i]

significadoP =

palabra.significados()[0]

w =

obtener_distancia(significadoP,

significado'I, grafo)

si w > 0


synsets++

fin-si

fin-mientras

fin-si // Fin FSP

si synsets > 0

v = total/synsets

si v > max

max = v

best = significado'I

fin-si

fin-si

fin-para

si max > 0

I.añadir(best)


45.


P.borrar(P[0])

fin-si

fin-mientras

fin-si

devolver solucion

7.1.6.- Ordenar_por_polisemia

Descripción: Es una función que compara el número de significados asociados de diferentes

palabras de un contexto y devuelve si la primera palabra tiene menos significados asociados que la

segunda.

Pseudocódigo:

ordenar_polisemia (palabra1, palabra2) {

vector1 = palabra1.significados()

vector2 = palabra2.significados()

devolver vector1.longitud() < vector2.longitud()

}

7.1.7.- Ordenar_de_forma_explicita

Descripción: Es una función que compara los pesos de diferentes palabras de un contexto y

devuelve si el primer peso es menor que el segundo

Pseudocódigo:

ordenar_explícito (palabra1, palabra2) {

peso1 = palabra1.peso()

peso2 = palabra2.peso()

devolver peso1 < peso2

}

7.1.8.- Ordenar_por_id

46.


Descripción: Es una función que compara los ids de diferentes palabras de un contexto y

devuelve si el primer id es “menor” (alfabéticamente hablando, es decir, si va antes) que el segundo

Pseudocódigo:

ordenar_ids (palabra1, palabra2) {

id1 = palabra1.id()

id2 = palabra2.id()

devolver id1 < id2

}

7.1.9.- Ordenar_palabras

Descripción: Es una función que ordena un contexto en función de una opción especificada.

La opción es un parámetro de la función.

Pseudocódigo:

ordenar_palabras(contexto, opcion) {

caso(opcion)

caso 0: // Sin ordenar

romper;

caso 1: // Ordenar por polisemia

sort(contexto.principio, contexto.final,

ordenar_polisemia)

romper;

caso 2: // Orden explícitos

sort(contexto.principio, contexto.final,

ordenar_explícito)

defecto: // Imposible

romper;

fin-caso

}

7.1.10.- Ordenación_por_id

47.


Descripción: Es una función que ordena un contexto en función de su id utilizando el sort

de C++ (la función auxiliar es la que queda más arriba). Por ejemplo, si los ids fueran w1, w2 y w10

devolvería un contexto ordenado de esta forma: w1, w10, w2.

Pseudocódigo:

ordenar_id (contexto) {

sort(contexto.principio, contexto.final, ordenar_ids)

}

7.1.11.- Programa principal (main)

Descripción: Es el programa principal del proyecto. Básicamente, lo que hace es comprobar

la corrección del proyecto, ya que lo que hace es recoger datos (leer contextos), procesarlos

(llamando a la función de desambiguación correspondiente) e imprimir datos (resultados de la

desambiguación).

Pseudocódigo:

main (...) {

// Configuración de las opciones del program_options

// Leer grafo + diccionario...

// Leer del fichero de contextos correspondiente

mientras existan contextos por leer repetir

estructura_UKB = leer_contexto();

estructura_UKB = calcular_SSID(estructura_UKB);

imprimir(estructura_UKB);

fin-repetir

}

48.


8.- Implementación

8.1.- Sobre UKB: lo que no teníamos

Como ya comentamos en el apartado de Análisis, había cosas de UKB que necesitábamos

crear ya que el propio software no nos las proporcionaba. En este apartado, se va a intentar explicar

de una forma un poco más concreta qué se ha añadido a UKB, cómo se ha hecho y por qué se ha

tenido que hacer. No es objetivo de este apartado el explicar las estructuras de datos que usa UKB,

pero es necesario explicarlas un poco por encima para comprensión del lector que puede no

conocerlas.

8.1.1.- Contextos como estructuras de datos: CSentence

El CSentence es la estructura propia de UKB para guardar los datos asociados a un contexto.

En sí, un CSentence no contiene más que un string (en el que guardamos el id del contexto) y un

vector de CWord. De forma gráfica, podría verse como algo así:

Un CWord, a su vez es una estructura de datos en la que guardamos toda la información

asociada a una palabra. Esta información va algo más allá de lo que necesita el SSI-Dijkstra en

realidad, por lo que (como veremos más adelante) parte de esta información se despreciará; pero, sí

que posee toda la información que necesita nuestro algoritmo, por lo que es idónea para este trabajo.

Además, se le suma la ventaja de que tenemos funciones tanto de lectura como de escritura

sobre algunos de sus parámetros, pero como estaba originalmente pensada para UKB, también hubo

que hacer algunos cambios a este nivel (véase sección 8.4).

Un CWord contiene (además de otras cosas) un string (donde guardaremos la palabra a

desambiguar), un carácter (donde guardaremos el PoS de la palabra) y una lista de strings asociados

49.

Imagen 5: Estructura de un CSentence

Vector<CWord>

id

CSentence


a los sentidos propios palabra (o lo que es lo mismo, una lista que representa algunos nodos en el

grafo). Como se trata de ver cuál es el mejor sentido de la palabra (o lo que es igual, de decidir qué

nodo de la lista de nodos se amolda mejor al contexto que estamos tratando), en principio con esto

debería valernos.

Por tema de especificación del problema y también por cuestiones de UKB, es digno de

mención también que el CWord cuenta además con un atributo booleano (que indica si la palabra

está desambiguada o no), con un peso propio de la palabra (que venía ya con UKB y que permite la

ordenación explícita) y también con un identificador propio de la palabra (lo cual permite identificar

la palabra dentro del contexto con un identificador cualquiera).

Una vez planteadas las bases sobre lo que se va a trabajar, es posible empezar a describir sus

características y sus limitaciones a la hora de desarrollar este proyecto concreto.

8.1.2.- Limitaciones: creación de nuevos métodos

Se estudiaron tanto la estructura de datos como los métodos del propio UKB. Respecto a las

estructuras de datos utilizadas (como se ha comentado antes), eran completas y realmente más que

suficientes para este proyecto. En ese sentido no se ha tenido que crear nada nuevo, ya que el propio

UKB proporcionaba incluso más de lo necesario.

Pero en cuanto a métodos se ha visto necesario hacer algunas cosas nuevas:

a) Un constructor nuevo para CWord. El que había hasta ahora no permitía crear

directamente palabras desambiguadas, sino simplemente decidía si estaban desambiguadas o no

según el número de sentidos. El nuevo constructor permite crear una nueva palabra ya

desambiguada. La razón de ello es que el algoritmo SSI-Dijkstra trabaja con vectores de Cwords,

tanto en las palabras por desambiguar como en la solución general del problema (véase apartado c).

b) Un setter para el atributo booleano de un CWord (en otras palabras, un método que

permite cambiar el valor de este atributo, ya que es privado). La idea inicial era no hacer copias de

variables y por eso se creó este método (permitiría cambiar el valor de false a true cuando se decida

que una palabra ya está desambiguada. Con la creación del constructor anterior tiene poco sentido,

pero se mantiene porque podría ser útil para posibles futuras expansiones de la aplicación.

50.


c) Un constructor nuevo para CSentence. Dado que el programa trabaja directamente con

estructuras CSentence (lectura y escritura de UKB), era necesario generar una estructura de datos de

este tipo con todas las palabras desambiguadas. Por eso, se creó un nuevo constructor que admite un

id y un vector de CWord como parámetros de entrada (ya que el método de SSI-Dijkstra nos genera

un vector de CWord con todas sus palabras desambiguadas y el id podemos cogerlo del CSentence

de entrada).

8.2.- Optimizaciones

Básicamente, puede comentarse una optimización en este proyecto. Pero antes de pasar a

hablar de la optimización en sí, estaría bien conocer el funcionamiento de dijkstra_shortest_paths,

una función de la librería BoostGraph. En esencia, lo que hace esta función es permitir calcular la

distancia total mínima (y el antecesor del nodo en ese camino mínimo) de un nodo al resto del

grafo. Esto es, si un nodo A tiene N caminos con un nodo B en el grafo, obtendremos la distancia

del camino más corto, y en caso de empates, obtendremos uno cualquiera.

Al contrario de lo que pensábamos al comenzar el proyecto, nos dimos cuenta de que la

función dijkstra_shortest_paths de la librería BoostGraph no era “inteligente” (es decir, no tenía en

cuenta si lo que estaba procesando ahora lo había hecho ya antes). Esto es, cuando calculábamos el

tiempo de ejecución de un programa que realizaba bastantes llamadas a esa función, nos

encontrábamos con tiempos sorprendentemente más altos de lo que esperábamos. Esto era debido a

que nosotros habíamos supuesto que el propio algoritmo detectaba si lo que estaba calculando ya lo

había calculado, y en ese caso no volvía a realizar el cálculo. Pero esta suposición inicial, que se vio

completamente falsa después de las primeras pruebas, dio lugar a una sencilla pero curiosa

optimización que da tiempos de ejecución bastante mejores.

Como de lo que se trataba es de saber si el algoritmo ya había operado con un nodo

determinado como origen, simplemente se fue guardando el valor del último nodo origen calculado

después de realizar la llamada a dijsktra_shortest_paths. Antes de esa llamada, se comparaba si a la

función ya se la había llamado en la iteración anterior con esos parámetros. En cuanto a código, se

sintetiza en:

si (por_calcular /= ya_calculado) entonces

51.


dijkstra_shortest_paths(...);

finsi;

ya_calculado := por_calcular;

La implementación de la solución de este problema, no podría haber sido más trivial y al

mismo tiempo, no podría haber sido mejor. Se pensó en utilizar tablas hash, pero no eran necesarias,

ya que incluían complejidad al problema, y, teniendo en cuenta que se iba a realizar el cálculo sólo

una vez por nodo del grafo (el algoritmo SSI-Dijkstra sólo realiza una pasada, no vuelve a

comprobar la corrección de sus resultados), el resultado en cuanto a tiempo de ejecución es aún

mejor (es una simple comparación y una asignación frente a un cálculo de una función hash,

búsqueda, asignación, etc).

8.3.- Sobre SSI-Dijkstra

Y SSI-Dijkstra+ también, ya que lo que se va a comentar aquí vale para ambos.

Obviamente, UKB no implementa de forma nativa ninguno de estos dos algoritmos; las

estructuras de datos de UKB están adaptadas y hechas para las aplicaciones (diferentes formas de

desambiguación de palabras) del propio UKB. Por lo que, ha sido necesario pensar cómo íbamos a

operar con las estructuras de datos de UKB (recordemos que el proyecto utiliza la función de lectura

y la función de escritura propias de UKB).

Al principio, se pensó en una solución del tipo:

estructura_UKB = leer_contextos();

estructura_SSID = convertir_a_SSID(estructura_UKB);

datos_SSID = calcular_SSID(estructura_SSID);

estructura_UKB = convertir_a_UKB(datos_SSID);

escribir(estructura_UKB);

Pero lo que realmente está implementado es:

estructura_UKB = leer_contextos();

estructura_UKB = calcular_SSID(estructura_UKB);

52.


imprimir(estructura_UKB);

Las razones de por qué se ha hecho así son sencillas. En primer lugar, es más reutizable bajo

el punto de vista de UKB una función que trabaja directamente con las estructuras de datos de UKB

y no una que trabaje con estructuras de datos propias (aunque esto no es del todo cierto: la

traducción se hace en el propio algoritmo para el cálculo del SSID). En segundo lugar, ya que era

necesario definir funciones propias en UKB (tal y como se ha visto en el apartado 8.1, lo que no

teníamos en UKB), se decidió que cambiar algunas cosas en UKB podía hacer más cómodo el

trabajo para el algoritmo del SSID, por lo que no era necesario hacer una traducción total, sino

simplemente guardar una parte de los datos y despreciar el resto. En realidad, en cada iteración se

guarda una copia completa del CWord que estamos tratando, por lo que no se pierden datos, sino

que simplemente usamos los que necesitemos (y los que no, los dejamos sin tratar).

Teniendo en cuenta todo esto, en esta versión de SSI-Dijkstra (y SSI-Dijkstra+), se ha

trabajado siguiendo lo expuesto a continuación:

a) A los algoritmos de desambiguación de palabras, se les pasa el CSentence del contexto

completo para que lo traduzcan a una estructura propia con la que trabajar.

b) Los algoritmos de desambiguación de palabras deben generar un nuevo CSentence

completamente desambiguado para poder utilizar correctamente la función de escritura de UKB

(que requiere que cada uno de los CWord de un contexto determinado esté desambiguado para

imprimir sus resultados).

En cuanto a la traducción implícita, que (como ya se ha explicado) se realiza de forma

implícita en el propio algoritmo del SSI-Dijkstra se ha realizado de la manera siguiente:

a) Las estructuras I (interpretadas) y P (pendientes de interpretar) serán propias del

algoritmo en cuestión (es decir, se usarán estructuras propias, la estructura que genera UKB sólo

servirá para obtener los datos que debemos filtrar para obtener los datos que nos importen, dejando

los demás fuera). La razón de esto es la búsqueda de la minimización de operaciones por parte del

algoritmo. Por ello, se creó un nuevo conjunto para las palabras solucionadas (solution_vector), así

se evita tener que arrastrar todos los datos de salida para el conjunto de interpretadas.

b) La estructura I se representa como un vector de Kb_vertex_t (nodos del grafo), mientras

53.


que las estructuras P y solution_vector se representan como vectores de CWords (debemos arrastrar

todos los datos de ambos conjuntos, en un caso porque falta de desambiguar y en otro porque como

solución del problema debemos escribir esos datos en la pantalla cuando finalice el programa).

c) El inicio de la traducción se realiza en el paso de inicialización, donde se separan

palabras monosémicas y polisémicas, y se hace lo siguiente:

1.- Si la palabra es monosémica, se introduce en I el sentido asociado a esa palabra y se

introduce el CWord de la palabra en solution_vector.

2.- Sino (la palabra es polisémica), se introduce en P.

8.4.- UKB: Lectura de datos aleatoria

En un momento determinado, realizando pruebas, nos dimos cuenta de que el programa no

daba los mismos resultados para el procesamiento de los mismos contextos, es decir, estaba siendo

no determinista. Dado que el SSI-Dijkstra trabaja con los datos de forma secuencial, la hipótesis

más probable desde el principio fue algún factor aleatorio en la función de lectura de UKB o algún

problema relacionado con la función dijkstra_shortest_paths de la librería BoostGraph. El problema

en cuestión fue el siguiente: se obtuvo un resultado diferente para un adjetivo de un contexto

determinado en las primeras pruebas.

El problema que se había observado en concreto era que en ejecuciones sucesivas del mismo

programa (usando las mismas opciones, etc) daba resultados diferentes para la misma palabra. Se

observó en un conjunto bastante reducido de palabras (3 de 187), por lo que se supuso un problema

relacionado con esas palabras en concreto: las palabras tenían empates. Definimos empates como

aquella situación que se da en la que una palabra tiene más de un posible sentido con la suma de sus

caminos mínimos igual. Es decir, si tenemos una palabra cuyos sentidos tienen una distancia

mínima total con el conjunto de palabras a comprobar de (por ejemplo): 9, 5, 5, 4 y 3; no hay

problema ya que el mínimo es 3 y por ello elegiremos ese sentido. Si en cambio fuera (por

ejemplo): 9, 9, 5, 3, 3; el programa elegía de forma aleatoria (a primera vista) el sentido que se iba a

elegir como correcto. Eso no interesa, ya que nos interesa mantener el orden que nos viene del

diccionario, porque vienen ordenados: el primer sentido en la entrada del diccionario es el sentido

más probable, mientras que según se va avanzando el sentido va siendo menos probable, hasta el

último.

54.


Se contactó con una de las personas que desarrolló UKB, quien nos dio la respuesta y una

posible solución al problema. Efectivamente, la función de lectura de contextos de UKB ordenaba

de forma aleatoria los sentidos de cada palabra por razones relacionadas con UKB. El problema era

que a nosotros sí que nos interesaba mantener el orden de los sentidos al leerlos del diccionario, por

lo que tras pensarlo decidimos aplicar la solución propuesta (que no era otra que declarar una nueva

variable global para controlar si se quiere o no ordenar de forma aleatoria y encapsular el código

que reordena estos resultados en una condición if). Tras aplicar esta solución, el problema dejó de

aparecer.

55.


9.- Pruebas

9.1.- Pruebas simples

Durante el desarrollo del proyecto, se han ido haciendo pruebas de forma puntual para

ilustrar que cada parte (función) realizada funciona de forma correcta, independientemente al resto.

De igual forma, antes de hacer las pruebas con el fichero completo de contextos, se decidió

hacer unas cuantas pruebas simplemente para ilustrar la diferencia entre usar SSI-Dijkstra o SSI-

Dijkstra+ (número de resultados), un grafo con pesos o sin pesos (fiabilidad de los resultados) o la

versión “optimizada” o no de la función que obtiene la distancia entre dos nodos del grafo (tiempo

en el cálculo de la distancia). Estas pruebas utilizaron un fichero de contextos reducido, un

subconjunto de los contextos contenidos en el frame-lu.context proporcionado por el director del

proyecto y que contiene 9 contextos y 187 palabras. La descripción de los contextos del fichero

viene en la tabla adjunta debajo. Para obtener estadísticas referentes a tiempos se utilizó el comando

time de Linux y para obtener estadísticas referentes a diferencias entre ficheros se utilizó el diff de

Linux. La máquina utilizada para hacer las pruebas tiene un procesador Intel Centrino, 384 MB de

RAM y Linux Ubuntu 8.04.

Nombre Número de palabras Todas polisémicas

Abounding_with 64 NO

Absorb_heat 10 NO

Abundance 4 NO

Abusing 5 NO

Accomplishment 5 NO

Accoutrements 77 NO

Achieving_first 13 NO

Active_substance 6 NO

Activity_done_state 3 SI

Tabla 2: Relación de contextos utilizados y datos interesantes

Estudiadas las posibilidades, se vieron suficientes hacer las siguientes pruebas:

56.


9.1.1.- SSI-Dijkstra, ineficiente y sin pesos

Esta prueba es la base de todo el sistema. Con esta prueba, se pretenderá demostrar

empíricamente que cada una de las pruebas es mejor que la anterior, y se dirá por qué. Los

resultados de esta prueba han sido los siguientes:

Tiempo de ejecución total: 48m39.714s

Estadísticas respecto a palabras:

Se obtiene un resultado para todas los conjuntos de palabras (contextos) que contienen

palabras monosémicas, es decir, todos excepto el contexto activity_done_state.

9.1.2.- SSI-Dijkstra, eficiente y sin pesos

Se puede observar una sustancial reducción en el tiempo de ejecución del banco de pruebas.

Esto es debido a la optimización de la función para obtener la distancia entre dos nodos del grafo

comentada ya en el apartado de Implementación. Respecto al resto, los resultados son similares a

los obtenidos en la primera prueba.



Se obtiene un resultado para todas los conjuntos de palabras (contextos) que contienen

palabras monosémicas, es decir, todos excepto el contexto activity_done_state.

Por tanto, la conclusión que sacamos de esto es que mejor utilizar la optimización, ya que

obtiene los mismos resultados que la no optimizada y en un tiempo sustancialmente menor.

9.1.3.- SSI-Dijkstra+, eficiente y sin pesos

Se observa que esta versión del algoritmo proporciona respuestas para el conjunto de

palabras (contexto) que el anterior no proporcionaba, por lo que ya es una mejora suficientemente

positiva. También hay que señalar que, al utilizar FSP para desambiguar verbos, se espera una

diferencia (sea mejora o empeora) de los resultados asociados a verbos. Se observa también mayor

tiempo de ejecución para esta prueba que para la anterior, debido a que hay un contexto más que

queda por desambiguar y para el que hay posibilidades.



57.


Se obtiene un resultado para todas los conjuntos de palabras (contextos). El tiempo no es

muy superior al anterior, obtiene resultados para los nuevos contextos en tiempos razonablemente

cortos.

Por tanto, la conclusión que sacamos de esto es que mejor utilizar el SSI-Dijkstra+ a SSI-

Dijkstra, ya que obtenemos solución a mayor número de contextos, incluidos aquellos sin

monosémicos en él.

9.1.4.- SSI-Dijkstra+, eficiente y con pesos

Se observa que en esta prueba, el algoritmo obtiene diferentes respuestas para toda clase de

palabras (no sólo verbos). Se tiene que agregando un peso determinado a un arco que une dos nodos

del grafo, cuanto mayor sea el peso, menor es la probabilidad de que el algoritmo obtenga como

camino mínimo aquel que contiene ese arco. Por lo que, pueden definirse caminos por los que “no

nos interese” ir, así como otros por los que “nos interese” ir. Esto puede empeorar, tanto mejorar los

resultados y hay que hacerlo sabiendo qué posibilidades hay. En nuestro caso concreto tenemos

que:



Se obtiene un resultado para todas los conjuntos de palabras (contextos). El tiempo no es

muy superior al anterior, aunque teniendo en cuenta que son el mismo número de contextos,

sorprende la diferencia palpable del resultado (10 segundos). Se observa también que los

significados que se obtienen para cada palabra son mejores en algunos casos, lo que demuestra de

alguna forma que escogiendo el peso adecuado para un arco o conjunto de arcos particular, se

obtiene un resultado más refinado y más concreto enfocado en el contexto que estamos tratando.

Por tanto, la conclusión que sacamos de esto es que mejor utilizar un grafo con pesos

adecuado al problema que estamos tratando.

9.2.- Pruebas completas (¡Egoitz!)

58.


10.- Gestión

10.1.- Esfuerzo total planificado vs real

Como en todo proyecto, la planificación inicial no tiene por qué ajustarse a la realidad de los

plazos y del tiempo que se invierte en cada cosa. En los siguientes apartados, así como los

siguientes tablas y gráficos ilustran la diferencia entre lo planificado y lo real:

10.1.1.- En procesos tácticos

Proceso Tiempo planificado Tiempo real

Planificación 10 horas 12 horas

Gestión 5 horas 6 horas

Instalación herramientas 5 horas 10 horas

Reuniones 20 horas 22 horas

TOTAL: 40 horas 50 horas

Tabla 3: Comparativa planificado vs real: procesos tácticos

59.

Imagen 6: Esfuerzo planificado en procesos tácticos

PlanificaciónGestiónInstalación herramientasReuniones


Puede observarse que, tal y como se había previsto, las reuniones son la tarea que más

tiempo ocupa en procesos tácticos.

10.1.2.- En procesos operativos

10.1.2.1.- Primera iteración


Captura requisitos 5 horas 8 horas

Análisis 5 horas 15 horas

Diseño 5 horas 2 horas

Implementación 10 horas 10 horas

Pruebas 8 horas 5 horas

TOTALES: 33 horas 40 horas

Tabla 4: Comparativa planificado vs real: procesos operativos - 1era iteración

60.

Imagen 7: Esfuerzo real en procesos tácticos

PlanificaciónGestiónInstalación herramientasReuniones


Puede observarse que, al contrario de lo que se había planificado, la tarea de Análisis de esta

iteración del proyecto es bastante costosa en cuanto a tiempo.

10.1.2.2.- Segunda iteración

61.

Imagen 8: Esfuerzo planificado en procesos operativos – 1ª iteración

Captura RequisitosAnálisisDiseñoImplementaciónPruebas

Imagen 9: Esfuerzo real en procesos operativos – 1ª iteración




Captura requisitos 2 horas 4 horas


Diseño 5 horas 4 horas




Tabla 5: Comparativa planificado vs real: procesos operativos - 2da iteración

62.




Puede observarse que, como en la iteración anterior, la tarea de implementación supone

menor carga de trabajo relativa que la planificada.

10.1.2.3.- Tercera iteración


Captura requisitos 1 horas 1 hora


Diseño 2 horas 1 hora




TOTALES (OPERATIVOS): 79 horas 92 horas

Tabla 6: Comparativa planificado vs real: procesos operativos - 3era iteración

63.




Puede observarse que, la tarea de implementación y la tarea de pruebas compiten en esta

iteración por ser la tarea que más tiempo requiere.

10.1.3.- En procesos formativos

64.







Lenguaje Perl 10 horas 8 horas

Lenguaje C++ 15 horas 20 horas

BoostGraph 5 horas 10 horas

UKB 25 horas 40 horas

Memoria 60 horas 72 horas

Presentación 5 horas


Tabla 7: Comparativa planificado vs real: procesos formativos

65.

Imagen 14: Esfuerzo planificado en procesos formativos

PerlC++BoostGraphUKBMemoriaPresentación


Puede observarse que, las tareas UKB y Memoria son las que más tiempo costaron, así como

tienen una diferencia reseñable con lo planificado. No se indica el tiempo real de la tarea

presentación porque, de momento se desconoce.

10.1.4.- Un punto de vista general

Puede observarse una diferencia notable entre lo real y lo planificado en las tareas de

“Análisis”, tanto en la primera como en la segunda iteración.

Es importante señalar que el número de horas totales reales para procesos formativos han

superado por bastante lo planificado inicialmente, así como de forma general se observa una

diferencia especialmente importante en la tareas de este grupo de tareas.

10.2.- Justificación de las desviaciones

Como puede verse, la mayoría de las desviaciones importantes se deben a una mala

planificación (se asigna poco tiempo planificado para hacer tareas bastante importantes, por

ejemplo, las fases de captura de requisitos y análisis en las primeras iteraciones del proyecto). No

fue necesaria una replanificación porque se calculó que el proyecto podía entregarse igualmente en

plazo, aunque seguramente lo correcto hubiera sido replanificar.

66.

Imagen 15: Esfuerzo real en procesos formativos

PerlC++BoostGraphUKBMemoriaDescripción


Puede notarse también desviaciones en la planificación del aprendizaje de UKB (en este

caso debido a la falta de familiaridad con el lenguaje C++ y a que se hacía complicado para el

alumno leer ciertas partes del código), así como en los procesos formativos en general (recordemos

que el alumno tuvo que aprender algunas cosas nuevas con las que no había trabajado hasta ahora).

Es destacable también la tercera iteración del proyecto, cuya duración real es menor que la

planificada. Esto es debido a que, una vez hecha la segunda iteración, la tercera era bastante más

sencilla, ya que no era más que ampliar la segunda con una pequeña funcionalidad.

10.3.- Incidencias principales

Es destacable señalar que el ordenador portátil del alumno dejó de funcionar durante la

realización del proyecto. Al margen del plan de contingencia (que recordemos: da algunas de las

posibles soluciones al proyecto, y no necesariamente todas), esta incidencia se resolvió de la

siguiente manera: el director de proyecto decidió prestar temporalmente un ordenador al alumno

para que continuara con el proyecto. Gracias al protocolo habitual de realizar con cierta frecuencia

copias de seguridad, el alumno no tuvo problemas en la continuación del proyecto y se pudo seguir

adelante sin contratiempos mayores.

67.


11.- Conclusiones

11.1.- Objetivos cumplidos

Considerando los objetivos propuestos en el Documento de Objetivos del Proyecto:

1.- Traducir el algoritmo de desambiguación de palabras SSI-Dijkstra de Perl a C++.

2.- Utilizar como base para el algoritmo el software UKB para poder integrar en un futuro el

algoritmo al propio UKB.

Creo que se han cumplido las metas marcadas. Si bien la aplicación desarrollada no puede

implantarse en el sitio en el que está actualmente la aplicación en Perl de SSI-Dijkstra, los objetivos

marcados inicialmente están cubiertos: no sólo tenemos una aplicación escrita en C++ que realiza el

mismo trabajo, sino que además congenia fantásticamente con el software de UKB.

11.2.- Valoración personal

Dado que el proyecto tiene como pivote un tema que no se trata en la Ingeniería Técnica en

Informática de Sistemas (Procesamiento del Lenguaje Natural, Inteligencia Artificial, etc), me

pareció algo complicado entender el proyecto desde el principio. De igual forma, el proyecto me

pareció bastante interesante desde el principio debido a sus múltiples posibilidades (como por

ejemplo, en mejora de los traductores on-line).

Respecto al proyecto, supongo que como todo es mejorable, pero estoy bastante satisfecho

con lo que se ha hecho. Al menos, se han cubierto los objetivos que se habían propuesto

inicialmente y personalmente, para mí se me ha abierto una posible vía de trabajo e investigación en

un futuro puede que no muy lejano.

11.3.- Trabajos futuros

Todo es mejorable en algún aspecto. En este apartado presentaremos algunas de las cosas

que podrían ser trabajos futuros relacionados con este proyecto, o bien, mejoras en algún aspecto

del proyecto en cuestión.

11.3.1.- Integrar dentro del branch principal de desarrollo de UKB

68.


Estaría bien que UKB (que fue utilizado como base en el proyecto) y SSI-Dijkstra siguieran

una misma línea de desarrollo (y no dos diferentes, ya que cambios en UKB podría hacer que SSI-

Dijkstra no funcione o viceversa). Queda pendiente de saber si esto es posible o no, pero es una

posibilidad como cualquier otra.

11.3.2.- Implementar otros algoritmos que usan Dijkstra

Podría ser interesante que, una vez tenemos la función que calcula las distancias mínimas en

C++, podamos usarla para implementar otros algoritmos que utilicen el algoritmo de Dijkstra como

base.

11.3.3.- Usar otras funcionalidades de BoostGraph que no sean Dijkstra

Como por ejemplo, el Bellman's-Ford Shortest Paths.

11.3.4.- Comparativa con una solución Perl pura (sin BoostGraph)

Ya que el algoritmo SSI-Dijkstra está implementado en Perl, sería interesante utilizar una

librería Perl de tratamiento de grafos (Graph.pl) para comparar el rendimiento de las diferentes

soluciones: la Perl pura, la Perl con llamadas a las librerías BoostGraph y la C++ pura.

11.3.5.- Creación de un daemon en Linux para mejorar eficiencia

Ya que la lectura del grafo de UKB y la lectura del diccionario tarda un tiempo determinado

(normalmente determinante para ficheros de contextos pequeños), estaría bien tener un daemon que

tenga cargados estos ficheros y que atienda las peticiones de los clientes (SSI-Dijkstra o SSI-

Dijkstra+) para intentar mejorar la eficiencia del programa.

69.

Índice de contenidos - upv/ehuadimen.si.ehu.es/~rigau/teaching/ehu/pfcs/gorkablanco2010... ·...

Documents