Programación Lógica y Recuperación de Información

DCG: notación de reglas gramaticales en Prolog

2006-03-06T18:37:00.000+01:00

La notación de reglas gramaticales DCG (Definite Clause Grammar, en castellano gramática de cláusulas definidas) es una variante o extensión sintáctica de la sintaxis ordinaria del lenguaje Prolog, cuyo objeto es implementar gramáticas formales de forma abreviada, y en consecuencia simplificar y hacer más legibles los analizadores sintácticos escritos en este lenguaje, ya que permite manejar información (entiéndase por ésta "variables") implícita. Su expresión es una notación abreviada de la sintaxis del lenguaje Prolog, recogida por la práctica totalidad de los parsers e intérpretes actuales para este lenguaje, que la transforman automáticamente y de forma interna en cláusulas normales. En la notación DCG el operador infijo ":-" es sustituido por el operador del mismo carácter "-->", y se puede establecer, a modo de ejemplo, la siguiente correspondencia entre notaciones, siendo la primera la cláusula Prolog en sintaxis ordinaria, y la segunda la notación DCG equivalente:

oracion(S0,S) :- sintagma_nominal(S0,S1), sintagma_verbal(S1,S).
oracion --> sintagma_nominal, sintagma_verbal.

La anterior cláusula Prolog se expresa en palabras como sigue:

"Existe una oración entre S0 y S si existe un sintagma nominal entre S0 y S1, y existe un sintagma verbal entre S1 y S"

La notación DCG se basa en la utilizada para las gramáticas libres de contexto (context-free grammars o CFGs, N. Chomsky), estructura jerárquica que indica las relaciones de las construcciones del lenguaje, descritas mediante notación BNF (Backus Normal Form ó Backus-Naur form), creada originalmente para definir la estructura sintáctica del lenguaje ALGOL60 (1960, John Backus), y muy utilizada tanto para definir la estructura sintáctica de los lenguajes de programación, como para definir estructuras sintácticas de los lenguajes en general. Por tanto, mediante notación DCG, es posible manejar directamente en lenguaje Prolog gramáticas libres de contexto. Las gramáticas libres de contexto vienen a ser una simplificación de la gramática ordinaria, que, por ejemplo, y referida al idioma castellano, podría adoptar la siguiente expresión en notación DCG:

oracion --> sintagma_nominal, sintagma_verbal.

sintagma_nominal --> determinante, nombre.

sintagma_verbal --> verbo, sintagma_nominal.
sintagma_verbal --> verbo.

determinante --> [el].
determinante --> [la].

nombre --> [hombre].
nombre --> [manzana].

verbo --> [come].
verbo --> [canta].

Que el sistema Prolog (en este caso SWI-Prolog) traduce automáticamente al siguiente conjunto de cláusulas:

oracion(A,B):- sintagma_nominal(A,C),
sintagma_verbal(C,B).

sintagma_nominal(A,B):- determinante(A,C),
nombre(C,B).

sintagma_verbal(A,B):- verbo(A,C),
sintagma_nominal(C,B).
sintagma_verbal(A,B):- verbo(A,B).

determinante([el|A],A).
determinante([la|A],A).

nombre([hombre|A],A).
nombre([manzana|A],A).

verbo([come|A],A).
verbo([canta|A],A).

Como es fácilmente deducible, el programa basado en esta pequeña y muy limitada gramática, solo aceptará como oraciones gramaticalmente correctas "el hombre come la manzana", "el hombre canta", y combinaciones similares, incluso por ejemplo frases a todas luces gramaticalmente incorrectas como "la manzana canta", "la hombre come", etc., devolviéndonos una lista vacía, pero no aceptará por ejemplo "el hombre baila" (el verbo "baila" no se halla dentro de la base de hechos o conocimiento del programa). Se entiende por tanto que una gramática completa, que abarque todas las posibles estructuras, relaciones y combinaciones de las partes constitutivas de una lengua, requiere un programa muy complejo y difícil de implementar. En el ejemplo expuesto, se pueden obtener todas las oraciones aceptadas como gramaticalmente correctas por la gramática del programa, lanzando en el intérprete el siguiente objetivo:

?- oracion(X,[]).

Por su parte, un ejemplo muy sencillo de gramática para el idioma inglés, escrita mediante notación DCG, adopta la siguiente expresión:

sentence --> noun_phrase, verb_phrase.

noun_phrase --> noun.
noun_phrase --> determiner, noun, rel_clause.

verb_phrase --> verb.
verb_phrase --> verb, noun_phrase.

rel_clause --> [].
rel_clause --> [that], verb_phrase.

determiner --> [the].
determiner --> [a].

noun --> [john].
noun --> [annie].
noun --> [man].
noun --> [men].
noun --> [woman].
noun --> [women].
...

verb --> [like].
verb --> [likes].
...

En la notación DCG se suprimen dos parámetros, una lista de entrada, y una lista de salida. La primera puede estar representada, por ejemplo, por la oración [el,perro,muerde] y la segunda por una lista vacía [] que es el resultado de comprobar la estructura sintáctica de dicha oración en función del parser utilizado. Adicionalmente, es posible agregar variables a las gramáticas representadas mediante notación DCG, por ejemplo para especificar el género y el número.

Como se ha dicho anteriormente, la notación DCG permite añadir argumentos adicionales, y también incorporar objetivos Prolog en el cuerpo de las reglas, estos últimos encerrados entre llaves {}. Los argumentos adicionales nos permitirían por ejemplo introducir las reglas gramaticales correctas en función de las convenciones adoptadas por la lengua objeto de representación, y así evitar incorrecciones en la concordancia género / número, etc. También, mediante notación DCG también es posible construir programas capaces de representar árboles de análisis de una oración (que representan las categorías gramaticales implicadas en la descomposición de sus partes), y árboles sintácticos (parse trees) que de una forma gráfica muestran la estructura en forma de árbol descendente de determinada construcción gramatical. Como explicamos en la anterior anotación, los analizadores sintácticos o parsers se encargan de la construcción de árboles de análisis de las oraciones de una lengua, capaces de representar la estructura sintagmática de las mismas. Siguiendo con el ejemplo de la sencilla gramática en castellano, expuesto más arriba, la representación gráfica del árbol de análisis de la oración "el hombre come la manzana" presenta el siguiente aspecto, haciendo uso para ello de este programa:

?- draw(o(sn(d(el),n(hombre)),sv(v(come),sn(d(la),n(manzana))))).

                       o
                       |
        +--------------------+
        sn                   sv
        |                    |
   +-------+        +------------+
   d       n        v            sn
   |       |        |            |
   |       |        |      +--------+
   |       |        |      d        n
   |       |        |      |        |
   |       |        |      |        |
   el    hombre    come    la    manzana

Donde "o" = oración, "sn" = Sintagma Nominal, "d" = Determinante, "n" = Nombre, "sv" = Sintagma Verbal, y "v" = Verbo. Hay que advertir que este programa no realiza el árbol de análisis propiamente dicho, que es:

o(sn(d(el),n(hombre)),sv(v(come),sn(d(la),n(manzana))))

Simplemente lleva a cabo su representación gráfica en forma de diagrama de caracteres ASCII. El código fuente del programa en cuestión, que originalmente se llama draw.swi, ha sido copiado a un editor de texto plano, y salvado con la extensión ".pl" para poder ser ejecutado por el intérprete SWI-Prolog, aunque otra opción es asociar los archivos con extensión ".swi" con el ejecutable de dicho intérprete. Su autor es Bertram Ludäscher, de la "University of California Davis".

Los ejemplos de notación DCG y Prolog en castellano se han tomado del capítulo 9, "Uso de reglas gramaticales en Prolog", apartado 9.1, "El problema del análisis sintáctico", de la obra de W.F. Clocksin y C.S. Mellish "Programación en Prolog" (2ª ed.; Barcelona: Gustavo Gili, 1993; ISBN: 84-252-1339-8), traducción del original en inglés "Programming in Prolog", a la que me remito para obtener una explicación detallada sobre reglas gramaticales, análisis sintáctico, y notación DCG en Prolog, habida cuenta de que los autores reseñados hacen una exposición clara y perfectamente comprensible sobre el particular, perfectamente asequible para las personas no excesivamente versadas en este lenguaje.

Por su parte el ejemplo de gramática en inglés se ha obtenido del capítulo 17, "Languague Processing with Grammar Rules", de la obra "Prolog - Programming for Artificial Intelligence" (Ivan Bratko, 2ª ed.; Addison-Wesley, 1990; ISBN: 0-201-41606-9). Se trata de un libro muy recomendable, de nivel más avanzado y completo que el de Clocksin y Mellish, claramente más introductorio, y como su propio nombre indica cubre por un lado las generalidades del lenguaje Prolog, y por otro lado su aplicación a las principales técnicas del campo de la IA (búsqueda y clasificación, sistemas expertos y representación del conocimiento, PLN, Machine Learning, etc.).

Por último, mencionar otro ejemplo de utilización práctica de la notación DCG y el lenguaje de programación lógica Prolog, la librería Html-write [1] [2] [3] del intérprete y entorno de desarrollo SWI-Prolog, que traslada términos Prolog en HTML, generando salidas en este último lenguaje, para lo cual hace uso precisamente de estructuras escritas en notación DCG.

Más información (PLN y DCGs en Prolog):

Adventure in Prolog - 15. Natural Language.
En Learn Prolog Now!: 7. Definite Clause Grammars, 8. More Definite Clause Grammars (P. Blackburn, J. Bos, K. Striegnitz).
Logic, Programming and Prolog - 10. Logic and Grammars (monografía, en formato PDF; U. Nilsson, J. Maluszynski).
Natural Language Processing in Prolog (G. Gazdar, C. Mellish; otra ubicación).
Parsing in Natural Language Processing (Julia Lavid).
Parsing Techniques - A Practical Guide (monografía, varios formatos; D. Grune, Ceriel J.H. Jacobs).
Parsing techniques in Prolog (monografía, formato ".doc"; Klaus von Bremen).
Prolog and Natural-Language Analysis (monografía, formato PDF; F.C.N. Pereira, S.M. Shieber).
Prolog Tutorial - 7. Introduction to Natural Language Processing (J.R. Fisher).
Prolog Tutorial - Definite Clause Grammars (A. Aaby; otra ubicación).
Natural Language Processing (A. Aaby).
A Natural Language Processor (A. Aaby).
Quick Prolog - Definite Clause Grammars (D.S. Robertson).
Extended DCG's: Declarative Programming with State (Peter Van Roy).
ProNTo - Prolog Natural Language Tools.

Específicamente sobre DCG:

CFGs y BNF:

Forman parte del mismo conjunto de lecturas de clase:

Analizadores sintácticos y tokenización

2006-02-27T01:55:00.000+01:00

Dentro del complejo y amplio ámbito de dominio del Procesamiento del Lenguaje Natural (PLN), una de las funciones esenciales de los analizadores sintácticos o parsers es el análisis de cadenas de tokens en busca de posibles errores sintácticos (recordemos que la sintaxis, entendida en sentido amplio, es aquella parte de la gramática que se ocupa de las normas que rigen la formalización de las palabras en estructuras mayores tales como las oraciones, así como de las relaciones que establecen entre si dichas palabras). Un token se puede definir como la unidad mínima de información con significado propio dentro de una secuencia de caracteres alfanuméricos. Estas cadenas de unidades mínimas de información o unidades léxicas, son generadas previamente por el módulo lexicográfico integrado en el parser, encargado de identificarlas dentro de un texto o secuencia ordenada de caracteres alfanuméricos. Por su parte, la tokenización es un proceso consistente en la descomposición, en forma de lista, de esas cadenas de tokens en sus unidades mínimas. Así, un programa de este tipo podría generar la siguiente lista de tokens a partir de la frase "¡Hola Mundo!":

[161, 72, 111, 108, 97, 32, 77, 117, 110, 100, 111, 33]

Donde cada uno de los números de la lista se corresponde con el carácter ASCII (American Standard Code for Information Interchange) correspondiente a cada una de las unidades mínimas de significación identificadas en la frase, en el mismo orden. Por supuesto es posible llevar a cabo el proceso inverso, y a partir de esa lista generar las cadenas de tokens que forman la frase en cuestión. La tokenización es por tanto el proceso básico que permite manejar el lenguaje natural escrito para su posterior procesamiento, en base a su descomposición en unidades mínimas de información con significado propio.

La mayor parte de los lenguaje de programación contemplan instrucciones específicas para llevar a cabo el proceso de tokenización de cadenas ordenadas de caracteres alfanuméricos, si bien es posible implementar alternativamente esta operación mediante otros procedimientos proporcionados por esos lenguajes.

Así, un programa que pretenda "leer" un texto, deberá en primer lugar "tokenizarlo", generando una lista de los tokens, o unidades léxicas mínimas con significado propio, identificados en ese texto. A continuación, procederá a identificar unidades mayores de significado propio (contemplando por ejemplo la presencia, como elemento separador, del carácter ASCII 36, que se corresponde con el espacio en blanco), lo que podríamos asimilar como "palabras", para, finalmente, acabar identificando otras unidades de significación de orden superior, frases u oraciones. Diferenciadas las oraciones del texto "leído", el parser procede a realizar el análisis sintáctico propiamente dicho, identificando para ello las partes constitutivas de dichas oraciones que, a tal fin, son comparadas con patrones previamente definidos de estructuras posibles, que dependerán de la lengua de escritura del texto, y del nivel de complejidad de análisis que se pretenda alcanzar, ya que contemplar todas las posibles estructuras de una lengua y sus numerosas variaciones, y representarlas mediante una serie de reglas, no es una tarea precisamente sencilla.

La detección de las variaciones de posición admitidas en cada lengua, en relación con el orden de las palabras, o análisis de las transformaciones, se realiza mediante procesos de análisis estructural que tratan de identificar la estructura profunda de una oración en relación con su estructura superficial. El análisis estructural, en base a la estructura superficial (2) de una oración y, cambiando el orden de determinadas palabras, trata de determinar su posible transformación a una estructura de tipo profundo (1):

(1) Estructura profunda: "Pedro come una manzana"
(2) Estructura superficial: "Come Pedro una manzana"

La implementación del proceso de tokenización, al margen de la utilización de instrucciones específicas que transforman directamente una cadena de caracteres alfanuméricos en una cadena de tokens, implica la utilización de otro tipo de instrucciones cuya función es la "lectura" individual, uno a uno, de los caracteres presentes en el canal o grupo activo de entrada de datos (input stream) que se halla especificado, que por lo general será bien el teclado del ordenador, que es el canal activo de entrada por defecto (al igual que el canal de salida de datos, output stream, por defecto es el monitor del ordenador), o bien un fichero de texto ubicado en la ruta que se indique.

Así, en el lenguaje Prolog existe el predicado predefinido name(?AtomOrInt, ?String). El argumento AtomOrInt es la variable que representa la cadena de caracteres alfanuméricos o "átomo" que se desea tokenizar, mientras que el argumento String es la variable que representa la lista resultante. El símbolo "?" indica que ambos argumentos son reversibles, es decir, que pueden funcionar tanto como variables de entrada de datos como variables de salida, si bien uno de ellos ha de estar necesariamente instanciado. Su modo de funcionamiento es el siguiente:

?- name('¡Hola Mundo!', X).

X = [161, 72, 111, 108, 97, 32, 77, 117, 110|...] [write]

X = [161, 72, 111, 108, 97, 32, 77, 117, 110, 100, 111, 33]

Yes

La indicación [write] simplemente expresa que, una vez que el intérprete proporciona la lista de tokens, incompleta como indica la barra vertical seguida de puntos suspensivos "|...", se ha tecleado el operador w para que ésta se muestre en toda su extensión, ya que, en este caso SWI-Prolog, muestra por defecto en pantalla una versión abreviada de las listas, cuando estas exceden determinada longitud (no obstante se pueden obtener listas completas utilizando el comando "w", tal y como se explica en esta página).

Por supuesto, existen más predicados para la manipulación de átomos, como se referencia en el apartado "Analysing and Constructing Atoms" del manual de SWI-Prolog.

Otra forma de tokenizar átomos en Prolog es utilizar el predicado get0/1 y get0/2 y algún tipo de algoritmo recursivo que vaya "recorriendo" todo el texto del canal activo de entrada de datos (un archivo externo, por ejemplo), y al tiempo introduzca los tokens resultantes, incluyendo los espacios en blanco (get/1 y get/2 no los leen), en una lista acumuladora, en tanto no se alcance determinado marcador de parada, definido previamente (para este fin suele aprovecharse el átomo end_of_file, que se corresponde con el final de texto). Este predicado realmente lee el byte correspondiente a cada carácter alfanumérico individual, asociándolo con su correspondiente código ASCII.

El analizador sintáctico, en base a los constituyentes de una oración (véanse los principios de la gramática generativa de Noam Chomsky), y mediante un número finito de reglas, trata de determinar la gramaticalidad o no de un número infinito de construcciones. Un analizador sintáctico trata de ver hasta que punto puede someterse un grupo de palabras a una estructura de reglas. Así por ejemplo, si tenemos la oración:

Pedro come una manzana

en primer lugar, y mediante un proceso de tokenización, se genera una lista de las palabras que contiene. De esta lista inicial de palabras, se puede diferenciar una sublista que se corresponda con el Sintagma Nominal (SN) de la oración, y si ésta puede concatenarse con otras sublistas que según determinadas reglas se verifica como Sintagma Verbal (SV), la oración se concluye que es gramatical. Lo que importa en los constituyentes es el orden de las palabras de la oración.

El analizador sintáctico realiza el análisis secuencialmente, palabra por palabra, partiendo de una lista inicial que, siguiendo con el ejemplo de la oración expuesta, sería:

[pedro,come,una,manzana]

El proceso de computación de las reglas del analizador sintáctico debe dar como resultado otra lista, que será una lista vacía [] si la oración inicial es gramatical (siempre en base a las reglas que tenga definidas el analizador). En definitiva, partiendo de la lista inicial de palabras, el analizador sintáctico comprueba si ésta se puede subdividir en dos sublistas, que se corresponden, respectivamente, con el SN y el SV de la oración.

Más información: El análisis sintáctico y el análisis semántico.

¿Ha llegado el fin de los tesauros documentales?

2006-02-19T12:08:00.000+01:00

Aunque no suele ser mi costumbre publicar integramente textos completos en este sitio (para esos menesteres mantengo abierto Visto y Leído), me permito hacerlo en esta ocasión dado el indudable interés que tiene el que reproduzco a continuación, en función de las ideas que plantea, las experiencias prácticas puestas de manifiesto y compartidas por el autor, y el debate que todo ello pretende suscitar. Se trata de un mensaje enviado por José Ramón Pérez Agüera (Departamento de Sistemas Informáticos y Programación, Facultad de Informática, Universidad Complutense de Madrid) a la lista de distribución IWETEL, el pasado 13/02/2006 (para acceder al texto original, en el apartado de archivos, hace falta estar suscrito a dicho foro de discusión para profesionales del ámbito de las bibliotecas y los centros de documentación).

[Comienza el texto de Pérez Agüera]

"Aunque no me toca publicar nota en Thinkepi, llevo unos meses (de hecho algún año que otro) dándole vueltas a este asunto y me gustaría contar con la opinión de la comunidad de documentalistas, más allá de mis propias observaciones, con lo cual este correo no pretende ser una nota sino dar pie a un debate en el que los documentalistas no están teniendo voz, al desarrollarse dentro del campo de la informática.

Trabajo en generación automática de tesauros, lo cual me ha llevado a realizar experimentos de indización automática y expansión de consultas a partir de tesauros realizados a mano. Concretamente he utilizado tres tesauros: ISOC-Economía, EUROVOC y SPINES, todos ellos conocidos de sobra. La colección sobre la que he realizado las pruebas ha sido el sub-conjunto de noticias de economía y política generadas por la Agencia EFE en 1994 (efe94 es una colección típica en experimentos de recuperación de información que consta de un total de 215.738 documentos. Yo he utilizado 23.390 en mis experimentos para centrarme en el área de política y economía, las cuales son cubiertas en buena medida por los tesauros anteriormente mencionados).

A parte también he contado con un conjunto 22 de consultas con sus respectivos juicios de relevancia para el dominio mencionado de cara a la realización de los experimentos. Estas consultas las he obtenido del congreso CLEF [Cross-Language Evaluation Forum] que se celebra todo los años y que se centra en temas de recuperación de información mono y multilingüe.

Como motor de búsqueda he usado Lucene, adaptado al español con stemming sobre los términos de indización, el cual está basado en el modelo tradicional de espacio vectorial de Salton (un clásico, vamos).

El objetivo de mis primeros experimentos ha sido el de comprobar de que forma afectaba a la recuperación de información automatizada el uso de tesauros documentales como los que se usan todos los días en centros de documentación de todo el mundo. Y cual no ha sido mi sorpresa al comprobar que tanto juntos como por separado, usando todos o parte de los tipos de relaciones que existen en los tesauros, realizando expansión global directa o ponderada (la forma en que he ponderado los tesauros es otra historia), en cada uno de los casos los tesauros mencionados, no han mejorado prácticamente nada la recuperación en la colección, ni en precisión, ni en recall (ni en otro cerro de medidas que he ido aplicando basadas en el modelo propuesto por TREC [Text REtrieval Conference], otro congreso de RI que tiene un programita bastante completillo llamado trec_eval para evaluar la recuperación), es más en algunos de los experimentos, dependiendo de la longitud de la consulta el uso de tesauros documentales hechos a mano empeoraba los resultados.

El siguiente paso en mi investigación ha sido trabajar con tesauros generados automáticamente a partir de tres metodologías básicas:

Procesamiento lingüístico de la colección (POS-Tagging, análisis sintáctico, análisis de árboles de dependencia entre términos).
Análisis de co-ocurrencias para la generación de las relaciones entre términos (Latent Semantic analysis, Qui y Frei (y su versión española implementada por Zazo, Berrocal y Cia de Salamanca), Jing y Croft, etc.).
Utilización de otros recursos lingüísticos (léase eurowordnet en su versión española, y diccio).

Los tesauros generados automáticamente a partir de estas metodologías sí han proporcionado mejoras significativas en la recuperación. No me quiero poner aquí más pesado de la cuenta sobre los detalles técnicos y las cifras pero para el que las quiera se las puedo pasar.

El caso es que comenté el hecho con Antonio García Jiménez, que de esto de tesauros documentales sabe un rato, y me comentó ciertas ideas muy valiosas que explicaban en parte los resultados, y que se podrían resumir (Antonio, si andas por ahí, corrígeme si me equivoco) en que los tesauros no se adaptaban perfectamente a la colección sobre la que yo los aplicaba y que por tanto se necesitaría un tesauro hecho a mano para la colección con la que yo trabajo para obtener una mejora basada en el uso de tesauros documentales.

Tras este comentario me quede rumiando y modifique la colección para adaptarla terminológicamente a los tesauros con los que yo contaba, para hacer confluir ambos conjuntos de datos en lo posible y así comprobar si mejoraba algo la capacidad de recuperación de los tesauros, pero por desgracia los datos han seguido siendo bastante descorazonadores.

Después de todas estas pruebas me surgió la siguiente pregunta ¿realmente tienen lugar los tesauros hechos a mano, y basados en la metodología y normativas tradicionales en el panorama de recuperación automatizada imperante hoy, ya sea dentro o fuera de Internet?

Mi respuesta por el momento, y a falta de vuestros comentarios, es que no tienen lugar y que es necesario plantearse con urgencia varios cambios en la metodología de elaboración de tesauros que existe actualmente y de la que las normas ISO, el libro de Gilchrist y Aitchison y el libro de Blanca Gil, suponen las principales referencias.

Los principales problemas del uso de tesauros documentales en Recuperación de Información Automatizada son:

Dispersión de datos: Es decir en la colección aparecen constantemente palabras que el tesauro no es capaz de normalizar (este problema no se soluciona con una actualización periódica hecha a mano en función del crecimiento de la colección).
Ambigüedad Semántica excesiva aún en tesauros de dominio específico como los mencionados.
Inconsistencias en la estructura de los tesauros.

Todos estos problemas son normales teniendo en cuenta que son tesauros hechos y gestionados a mano sin ningún mecanismo más o menos automático de control de consistencia (de hecho la mera importación de los tesauros a SQL a permitido la detección de estas inconsistencias estructurales) más allá de programas tipo multites y demás.

A esto se suma que tal y como se hacen los tesauros hoy en día, y en contra de lo que muchos opinan, tampoco sirve para la transición a las ontologías, debido a cuestiones básicas de diseño (fundamentalmente el paradigma orientado a objetos) con las que los tesauros documentales no cumplen ni de lejos y que provoca serios problemas de consistencia cuando intentamos convertir un tesauro documental en una ontología.

En vista a estos hechos y a que yo no doy más de mi por el momento en este asunto, me gustaría conocer vuestra opinión en este tema (pues a muchos les va el pan en ello, pienso yo). Por concretar, las preguntas iniciales, sin excluir otras posible que podéis ir haciendo serían:

¿Cual es el papel de los tesauros documentales en el contexto de la recuperación de información automatizada en centros de documentación?
¿Cual es el papel de los tesauros documentales en la recuperación de información en Internet?
¿Es necesario modificar el paradigma de elaboración de tesauros actualmente imperante? ¿en que sentido?

Yo, aunque no soy un experto tesaurista tengo mis opiniones que iré poniendo aquí si el debate tiene éxito, pero las que me interesan son las vuestras.

Espero haber sido claro, si tenéis cualquier duda sobre lo que he escrito o algo no se entiendo no dudéis en preguntar, espero que con suerte y entre todos le podamos dar un tiento a este problema tan puramente documental."

[Fin del texto de Pérez Agüera]

Pues ya saben, cualquier comentario, rectificación, aportación etc., en relación con las cuestiones planteadas en el texto anterior, pueden enviarlo a la referida lista IWETEL, y así enriquecer el debate que sin duda merece el conjunto de asuntos planteados por Pérez Agüera en relación con la recuperación de información, la indización automatizada, y el papel que los tesauros como instrumento de descripción normalizada juegan en todo ello...

De Pérez Agüera, y sobre los temas que aborda en su comunicación a la lista IWETEL, ver también: "Automatización de Tesauros y su utilización en la Web Semántica" (SWAD-Europe, taller Introducción al uso de la Web Semántica, 13 de junio 2004). Véanse también en general los SWAD-Europe Reports y SWAD-Europe Presentations. SWAD significa Semantic Web Activity: Advanced Development. También me parece pertinente reseñar, de la revista Anales de Documentación (nº 7, 2004, págs. 79-95), el artículo de Antonio García Jiménez "Instrumentos de Representación del Conocimiento: Tesauros versus Ontologías" (en PDF).

En otro orden de cosas, aprovecho la ocasión para relacionar a continuación una serie de enlaces, referencias y textos que han ido mereciendo mi atención en los últimos meses (los entrecomillados son citas textuales tomadas de los sitios referenciados):

Artículos, introducciones, anotaciones de "blogs":

Why Use Prolog? (Jocelyn Paine). Documento en el que se exponen diez (buenas) razones para (en opinión del autor) utilizar el lenguaje de programación lógica Prolog.
"I'm sorry Dave, I'm afraid I can't do that": Linguistics, Statistics, and Natural Language Processing circa 2001 (en PDF; Lillian Lee, Cornell University).
Programación utilizando Visual Prolog 6.0 (R. Fuentes Covarrubias, Universidad de Colima, Facultad de Ingeniería Mecánica y Eléctrica, México).
The legacy of the Reverend Bayes (en Devlin's Angle, febrero 2000).
Dos muy buenas introducciones básicas al lenguaje Prolog: First Steps in Prolog: an easy introduction to this AI language / Free Prologs: a guide to freely available Prolog systems (H. Collingbourne; en Bitwise Magazine).
Linear Logic - Naturally! (en That Logic Blog): "Linear logic has enjoyed enormous popularity over the last couple of decades or so. For those without some training in structural proof theory, understanding the system can be quite intimidating, especially because of the funny notation and weird jargon. In this post, I am going to show you that, in fact, you could have invented linear logic! [...]".
Lógica, Matemática, Deducción Automática (Manuel Ojeda Aciego, Dept. Matemática Aplicada, Universidad de Málaga; en PDF): "Presentamos una breve perspectiva histórica del desarrollo en paralelo y, a veces, entrelazado, de la Lógica y las Matemáticas, con el objetivo final de presentar la Lógica Computacional y, en particular, la Deducción Automática, como un área de investigación matemática de extraordinario potencial práctico, no en balde distintos autores de conocido prestigio afirman que la Lógica es a la Computación como el Cálculo Infinitesimal es a la Física.".

Páginas y sitios web:

Neural Java: Neural Networks Tutorial with Java Applets. "Neural Java is a series of exercises and demos. Each exercise consists of a short introduction, a small demonstration program written in Java (Java Applet), and a series of questions which are intended as an invitation to play with the programs and explore the possibilities of different algorithms. [...]".
My Artificial Intelligence project.
Wikibook on Prolog ("[...] This book can serve as a textbook or tutorial for anyone who wants to learn the prolog programming language. No prior programming experience is required. Some basic knowledge of logic can come in handy. [...]").
Yandes. Conjunto de módulos concebidos para ayudar a los estudiantes de Lógica, implementados en lenguaje Prolog. Actualmente son los siguientes: TT: construcción de tablas de verdad para Lógica proposicional. Incluye además dos predicados para determinar una fórmula como válida, satisfactible, o insatisfactible, y un razonamiento como correcto o incorrecto; ND: construcción de demostraciones de deducción natural; CNF: convierte fórmulas en forma conjuntiva normal, o en forma clausal.
TRIPLE ("[...] an RDF query, inference, and transformation language for the Semantic Web. [...]").
Glosario de Recuperación de Información Web (Adriana Colino Tomé; vía Recuperación de Información en la Web).

Conferencias, congresos:

Modeling Decisions for Artificial Intelligence (Tarragona, 3-5 abril 2006): "Decision making processes, and information fusion tools at large, are currently embedded in most Artificial Intelligence applications. As a consequence, systems based on decision making and fusion techniques are becoming pervasive. They are currently in use in all kind of environments, from entertainment gadgets to safety-critical or risk management software.".
22nd International Conference on Logic Programming (ICLP 2006, 17-20 agosto 2006).

Algoritmo de aprendizaje ID3

2005-11-13T00:43:00.000+01:00

Una de las aplicaciones prácticas de las Redes Neuronales Artificiales (RNA), es la clasificación de datos, entendida ésta como un proceso de búsqueda de propiedades comunes a una serie de objetos de un dominio del conocimiento, en función de los valores de determinados atributos. Dentro de la cuestión de la clasificación automática, en tanto que proceso subsidiario de procesos más generales englobados dentro de lo que se conoce como "machine learning", uno de los algoritmos de aprendizaje automático más conocidos, basado en "ejemplos", es el denominado ID3, o "Iterative Dichotomizer (version) 3" (J.R. Quinlan, 1979). Trabaja con datos simbólicos, en contraposición a los datos numéricos, y se basa en la obtención de un árbol de decisión (ver anexo), a partir del cual se obtienen una serie de reglas de producción, capaces de representar un dominio o universo determinado, generando conocimiento independiente de dicho dominio (el sistema de aprendizaje parte de un estado inicial del dominio escogido en el que no existe conocimiento de partida, extrayendo patrones comunes de entre los ejemplos utilizados, a partir de los cuales genera una base de conocimientos de aplicación a dicho dominio). El árbol de decisión permite por tanto clasificar los datos de entrada. Se pueden distinguir dos tipos de procesos de aprendizaje:

Supervisado: los ejemplos o "explicaciones" son proporcionados al sistema por un sujeto externo. Pertenecen a esta categoría las clasificaciones de datos basadas en árboles de decisión en base a ejemplos, como es el caso del algoritmo de aprendizaje ID3.
No supervisado: los ejemplos u "observaciones" son creados por el propio sistema. Pertenecen a esta categoría los procesos de agrupamiento de datos o data clustering (o simplemente clustering).

Atendiendo a un plano de abstracción conceptual superior, en el denominado "machine learning" o aprendizaje de máquina, es posible diferenciar dos tipos de aprendizaje: aprendizaje memorístico (o aprendizaje de memoria) y aprendizaje cognoscitivo. El primero hace referencia a procesos de memorización de a) hechos y b) secuencias o procedimientos de acciones, siendo el tipo de aprendizaje más fácil de implementar en un sistema computacional "inteligente". El segundo tipo de aprendizaje, el cognoscitivo, es el que hace uso de procedimientos de razonamiento a partir de un conocimiento básico, de forma que sea posible la obtención de "descripciones de clase", generalizaciones que se obtienen de la observación de ejemplos concretos. Es por tanto un tipo de aprendizaje basado en un razonamiento de carácter inductivo, aquel que permite la formulación de principios generales, a partir de casos específicos individuales, a diferencia del razonamiento deductivo, que a partir de generalizaciones, y por medio de la lógica (silogismos), infiere conclusiones de carácter particular y concreto. En el razonamiento inductivo, es la acumulación de observaciones lo que permite llegar a conclusiones de validez universal.

No obstante, no es infrecuente, en los sistemas de aprendizaje automático, encontrar ambos universos de razonamiento, ya que las generalizaciones que se obtienen mediante el razonamiento inductivo, a partir de un grupo relativamente reducido de "ejemplos" u observaciones (fase de entrenamiento previo), servirán posteriormente para la obtención de conclusiones particulares a través de un proceso de razonamiento deductivo.

Los árboles de decisión o clasificación consisten en una técnica de carácter inductivo muy utilizada en el ámbito del aprendizaje automático. Gráficamente, están formados por nodos y ramas. Los primeros representan el identificador de un atributo concreto. Los nodos terminales u hojas representan los valores asociados a dicho atributo, mientras que las ramas. A cada uno de estos valores, se accede a través de una rama que parte del nodo en cuestión. Los casos son dirigidos hacia una u otra rama en función de los valores de sus atributos. Los árboles de clasificación son un método de aprendizaje válido en aquellas situaciones en las cuales los ejemplos de partida se pueden representar mediante un conjunto finito de atributos y valores. Los árboles de clasificación también se pueden concebir, desde un punto de vista algorítmico, como un conjunto de reglas if-then.

El carácter de los árboles de decisión es jerárquico, por lo que solo son capaces de representar conocimiento jerárquico, la mayor parte del mismo. Por otro lado, su construcción tienen un carácter recursivo y descendente, de los conceptos generales a los particulares, razón por la cual el acrónimo TDIDT (Top-Down Induction on Decision Trees) es utilizado para referirse a los algoritmos de construcción de árboles de decisión, como es el caso del algoritmo ID3 de Quinlan.

La mayoría de las heurísticas utilizadas para la determinación de árboles de decisión mediante algoritmos de aprendizaje, se basan en la teoría matemática de la información (C. Shannon, W. Weaver; Bell Laboratories, 1948) [1] [2]. Las heurísticas son criterios, métodos o principios, que permiten decidir, de entre varias alternativas de acción, cuál será la más efectiva para cumplir determinada meta. Permiten restringir el número de evaluaciones, y en consecuencia repercuten en una mejora de los tiempos de búsqueda de soluciones. Entropía y cantidad de información son dos conceptos que se dan la mano en el campo de las heurísticas. Sobre Entropía y cantidad de información, ver en Tio Petros: [1] [2] [3] [4].

El algoritmo ID3 genera lo que se conoce como reglas "duras", es decir, aquellas que solo atienden a dos posibles estados (verdadero-falso, positivo-negativo, 0-1, etc.), y que tienen por tanto un carácter bivalente, a diferencia de las reglas "borrosas", que permiten representar un rango infinito de valores entre dos extremos de una escala, como las que se obtienen mediante algoritmos ID3 "extendidos" (ID4, ID5, ID5R, C4.5, C5, etc.).

Pseudocódigo del algoritmo ID3:

Si todos los ejemplos de E pertenecen a una misma clase C, entonces
   arbol1 <-- nodo etiquetado con C
SiNo
   Si a = f, entonces
      C <-- clase mayoritaria de los ejemplos de E
      arbol1 <-- nodo etiquetado con C
   SiNo
      A <-- mejor atributo de a
      arbol1 <-- nodo etiquetado con A
      Para cada v perteneciente a los valores de A, hacer
         EAv <-- los ejemplos de E que tienen el valor v para el atributo A
         Si EAv = f, entonces
            arbol2 <-- nodo etiquetado con la clase mayoritaria en E
         SiNo
            arbol2 <-- ID3(EAv , a-{A})
         arbol1 <-- añadir a arbol1 el arbol2, a través de una rama etiquetada con v
Devolver arbol1

Otra representación en pseudocódigo del algoritmo ID3:

Aprendizaje-Árbol-Decisión(Ejemplos, Atributos, Default)
   retorna un árbol de decisión

IF no hay Ejemplos, retornar Default
ELSE IF si todos los Ejemplos tienen la misma clasificación,
   retornar la clasificación,
ELSE IF Atributos = vacío, retornar Mayoría(Ejemplos)
ELSE
   mejor-atr <-- elegir-atributo(Atributos, Ejemplos)
   árbol <-- nuevo árbol de decisión con raíz en mejor-atr
   FOR EACH valor v[i] de mejor-atr DO
      Ejemplos[i] <-- {elementos de Ejemplos con mejor-atr = v[i]}
      subar <-- Aprendizaje-Árbol-Decisión(ejemplos[i], Atributos - mejor-atr, Mayoría(Ejemplos))
      agregar rama al árbol con etiqueta v[i] y subárbol subar
   OD
retornar árbol

Los procesos de aprendizaje, que hacen uso de la clasificación de datos, mediante el descubrimiento de patrones, se utilizan con profusión dentro de lo que se conoce como "Data Mining", en castellano minería de datos, explotación de datos, o descubrimiento de conocimiento en bases de datos, diversidad terminológica en torno a la cual existe una cierta polémica.

Maximiliano del Rio es autor de una versión escrita en lenguaje Prolog del algoritmo de aprendizaje ID3. Los archivos correspondientes a esta implementación (librería Clasif) se pueden localizar bien en la sección de código fuente de programacion.com (comprimidos en un "zip"), o en el espacio personal que el propio autor tiene en el "Wiki" de SWI-Prolog. En "guia.txt" se explica el manejo de esta implementación del algoritmo ID3 en Prolog, que hace uso de la interfaz ODBC para consultar las tablas de la base de datos seleccionada, de las que se obtienen los ejemplos necesarios para generar las reglas de producción. Se adjunta además el archivo "clasif.pl", programa de "Data Mining" que hace uso del algoritmo ID3, dotado de interfaz gráfica mediante la utilización de la librería nativa XPCE.

"[...] programa que utiliza la librería anterior [...] Ayuda a generar las reglas y muestra las reglas obtenidas textual y gráficamente; también muestra una traza de como trabaja el algoritmo."
Fuente

Esta interfaz gráfica se abre lanzando el objetivo "?- main." en la línea de órdenes de SWI-Prolog, una vez compilado el programa. Finalmente, la librería "compila.pl" contiene predicados que permiten generar un ejecutable para Windows de los resultados obtenidos, mediante SWI-Prolog.

Para obtener una visión bastante amplia sobre la implementación en lenguaje Prolog de procesos de aprendizaje automático en general, y aprendizaje inductivo mediante árboles de decisión en particular (clasificación de datos), es muy recomendable la lectura del capítulo 18, "Machine Learning", de la (ya clásica) obra de Ivan Bratko "Prolog: Programming for Artificial Intelligence" (2ª ed. Addison-Wesley, 1994; ISBN: 0-201-41606-9). Sobre árboles de decisión trata concretamente el punto 18.6, "Induction of decision trees".

Existe así mismo un repositorio de algoritmos de aprendizaje automático escritos en lenguaje Prolog, Prolog library of machine learning algorithms, un tanto desactualizado eso sí, ya que la última actualización parece datar del año 1994, mantenido por Thomas Hoppe (Fraunhofer-Gesellschaft, Universidad Técnica de Berlín). Los programas están escritos haciendo uso de la sintaxis y, en la mayor parte de las ocasiones, de los predicados predefinidos (built-in predicates) contemplados en el Prolog descrito por Clocksin y Mellish, conocido como "estándar de Edimburgo", basado a su vez en el DECsystem-10 (D. Warren, F. Pereira y L. Pereira), para de esta forma asegurar el mayor grado posible de compatibilidad entre versiones de este lenguaje. Las implementaciones del algoritmo ID3 se localizan en la carpeta "IDT" (ver en cualquier caso el archivo "Readme" para más información).

Más información:

Algoritmo ID3 de J.R. Quinlan (documento traducido por J.A. Fernández, en PDF, comprimido en un zip).
Aspectos Básicos del Aprendizaje Simbólico (J.G. Boticario).
Aprendizaje de clasificadores (F. Berzal Galiano; en PDF).
ART: Un método alternativo para la construcción de árboles de decisión (F. Berzal Galiano; en PDF).
ART: Un método alternativo para la construcción de árboles de decisión (F. Berzal Galiano, 2002; tesis doctoral, en PDF).
IDT: Torgos ID3-like system based on the gain-ratio measure (algoritmo ID3 escrito en sintaxis del Prolog de Edimburgo). Este código se localiza en el directorio sobre Machine Learning del CMU Artificial Intelligence Repository (ver descripción; en cada uno de los directorios existen tres archivos, "0.html", "0.doc" y "readme.txt", que contienen la descripción de su contenido). El directorio dedicado al lenguaje Prolog en general se localiza en este enlace.
Induction of Decision Trees.
Árboles, Grafos (en Estructuras de Datos, algoritmia.net).
Árboles de Clasificación (PDF; tema de los apuntes de la asignatura "Métodos Matemáticos en Ciencias de la Computación", UPV).
Sistemas de Inducción de árboles de decisión.
Decision Tree for Optimization Software.
En Artificial Intelligence Lecture Notes: a) Problem Solving in Prolog; b) Induction of Decision Trees.
Algoritmo ID3 escrito en Prolog.
"ID3" en "The Machine Learning Dictionary".
"IDT: Torgos ID3-like system based on the gain-ratio measure" en CMU Artificial Intelligence Repository. Forma parte del directorio de programas "Machine Learning Algorithms Implemented in Prolog".
Tesis doctoral: Inducción de Conocimiento con Incertidumbre en Bases de Datos Relacionales Borrosas (A. J. Gómez Flechoso, 1998). En relación con los temas tratados en este "post", ver el capítulo 2 en general, y en particular los apartados 2.1 (Introducción), 2.2 (Descubrimiento de conocimiento y minería de datos), 2.3 (Métodos aplicados de minería de datos), y 2.4 (Programación Lógica Inductiva).
MLnet (Machine Learning network) Online Information Service.

Anexo - Árboles de decisión

Los árboles de decisión son una representación de los procesos involucrados en las tareas de clasificación. Se componen de:

Nodos: nombres o identificadores de los atributos.
Ramas: posibles valores del atributo asociado al nodo.
Hojas: conjuntos ya clasificados de ejemplos y etiquetados con el nombre de una clase.

Los nodos reflejan propiedades de los objetos del dominio, los arcos o ramas son los distintos valores de dichos atributos y las hojas son las clasificaciones posibles.

[Los árboles de decisión] Se adaptan especialmente bien a aquellos casos en los que:

Los ejemplos pueden ser descritos como pares valor-atributo.
La función objetivo toma valores discretos.
Podemos tomar hipótesis con disyunciones.
Posible existencia de ruido en el conjunto de entrenamiento.
Los valores de algunos atributos en los ejemplos del conjunto de entrenamiento pueden ser desconocidos.

[Fuente: Inducción de Árboles de Decisión: extensiones del ID3] [Volver al texto]