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

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:

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

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:

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:

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:

• Parsing in Prolog (otra ubicación).
• Definite Clause Grammars (otra ubicación).
• Perl Style Regular Expressions in Prolog (otra ubicación).
• Introduction to Definite Clause Grammars.

CFGs y BNF:

• Lenguajes de Programación: Notación BNF y otras gramáticas.
• What is BNF notation?
• Backus-Naur Form (en FOLDOC).
• Context-free grammar (en Wikipedia).

Forman parte del mismo conjunto de lecturas de clase:

• Four Concepts in Programming Language Description: Syntax, Semantics, Pragmatics and Metalanguage.
• Grammatical Description of Syntax: The BNF Metalanguage.
• Derivations, Ambiguity and Semantics.
• Nonrecursive Syntax: The Regular Expression Metalanguage.
• Between Lexics and Syntax: Whitespace, Layout, Comment Conventions.

[7] comentarios | # | lista |

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:

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.

[1] comentarios | # | lista |

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).

[0] comentarios | # | lista |

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]

[0] comentarios | # | lista |

Nota: la primera parte de esta extensa anotación, la más directamente relacionada con el enunciado del título, ya fue publicada en mi bitácora hermana, Visto y Leído, el 16/01/2004, bajo el mismo título. Al apuntar posteriormente algún enlace en el que se trata de la aplicación de la programación lógica en general, y Prolog en particular, a los acertijos de ingenio y los juegos lógicos, he ido añadiendo otras cuestiones estrictamente relacionadas con dicho lenguaje de programación, particularmente relativas a su origen, evolución y algunas de sus versiones desarrolladas a lo largo del tiempo con más o menos fortuna y permanencia posterior.

En el libro "Ayudando a la memoria. Técnicas y trucos para recordar" (Plaza & Janes, 2001; ISBN: 84-8450-527-8) su autor, Josep Mª Albaigès, incluye, como complemento imprescindible a la excelente descripción que se aborda en el libro respecto de los procesos de retención, memoria, y técnicas de recuperación o recuerdo de lo memorizado, un curioso "Diccionario de Mnemotecnias", en el que se recogen, ordenados alfabéticamente en relación con la cuestión a la que hacen referencia, toda clase de recursos mnemotécnicos (de mnemo + tecnia, aquellos que sirven para auxiliar a la memoria), algunos de cierta complejidad y otros más asequibles, referidos a aspectos muy variados. En este mismo diccionario se encuentra la siguiente definición:

"Llamamos mnemotecnia a cualquier truco o procedimiento abreviado que permite recordar, de forma más o menos provisional, una cosa concreta y en general breve."

En "Ayudando a la memoria...", página 95

Me quedo para esta ocasión con dos curiosidades referidas al universo de las clasificaciones, entendidas éstas en sentido amplio (cito textualmente):

Clasificación decimal en bibliotecas
Las temáticas de la clasificación decimal suelen ser: 0. Obras Generales - 1. Filosofía - 2. Religión - 3. Ciencias Sociales - 4. Lengua - 5. Ciencias Puras - 6. Tecnología - 7. Arte - 8. Literatura - 9. Historia. Que se recuerdan con la frase: "Generales: ¡filosofad religiosamente! Socios: ¡hablad puramente! Técnicos y artistas: ¡escribid históricamente!".

Taxonomía
La clasificación de las especies naturales comprende los siguientes escalones: Reino - Tipo - Clase - Orden - Familia - Género - Especie. Se recuerda esta secuencia, en orden inverso, con la frase: "Una especie general de familias ordenadas clasifican los tipos del reino".

Es también muy curiosa la descripción menotécnica de los silogismos (y la forma de recordar las figuras en que los escolásticos los clasificaron), del número pi, y de varios principios o teoremas fundamentales de la física y la estadística, entre otros, pero dada la relativamente amplia extensión de los textos en cuestión, me remito a la consulta y lectura del libro referenciado, caso de interesar este tema.

La lógica silogística o aristotélica trata de determinar la verdad o falsedad de determinado argumento filosófico, mediante el contraste de proposiciones o premisas, y en cierto sentido puede ser considerada como una formalización, basada en expresiones del lenguaje natural, del sentido común. La utilización del silogismo por parte de los escolásticos se entiende dada la integración de la filosofía de Aristóteles en la dogmática cristiana, característica de la tarea de reflexión desarrollada por este grupo de pensadores de la Filosofía occidental entre mediados del siglo XI y mediados del siglo XV, aproximadamente.

Josep Mª Albaigès es también editor de la revista Carrollia,

"[...] órgano de comunicación [...] de Mensa España, que se dedica a las Matemáticas recreativas, la Lingüística, la Literatura Experimental, la Lógica, la Ciencia y todo aquello que hubiera gustado a Lewis Carroll."

Fuente

Los boletines de los últimos años están disponibles en formato PDF. También es muy recomendable, si se está interesado por estos temas, la "Colección de juegos de ingenio" (resueltos) del Club Mensa, gran parte de ellos editados originalmente en las páginas de Carrollia. En otro orden de "utilidad" práctica, el "Boletín Oficial de la Facultad de Ciencias Inútiles" (BOFCI) es otra publicación del Club Mensa cuya lectura conviene no perderse...

Y ya que hablamos, al menos tangencialmente, de juegos lógicos y de ingenio, mencionar dos bitácoras en lengua castellana dedicadas de forma monográfica a estos asuntos: Juegos de Ingenio & Acertijos y Pequeños Enigmas. En este último sitio se localizan un buen número de enlaces que llevan a otras páginas de temática afín (ver el apartado "Buenas páginas de ingenio").

Enlazando la cuestión planteada inicialmente con la utilización de la programación lógica en general, y el lenguaje Prolog en particular, en la resolución de acertijos y juegos lógicos, podemos mencionar a modo de ejemplo el excelente trabajo "Resolviendo acertijos con Prolog" (J. Peri, Universidad Nacional de Luján, Argentina; en formato PostScript), en el que podemos leer:

"[...] Prolog puede ser imaginado como un laboratorio de lógica. Su capacidad para manejar expresiones simbólicas le permite codificar fácilmente cierto tipo de información que en los lenguajes procedurales es muy difícil de manejar. La programación lógica permite traducir en líneas de código descripciones de hechos e implicaciones, lo que en principio permite codificar líneas de razonamiento completas."

En "Resolviendo acertijos con Prolog"

Los ejemplos están escritos en notación Micro-Prolog, que difiere sustancialmente de la difundida posteriormente como estándar de facto por el denominado "Prolog de Edimburgo", tal y como se explica en un apéndice al final del documento (Apéndice II - Diferencias entre Micro-Prolog y la notación de Edimburgo), si bien la semántica de ejecución es idéntica en ambos casos. La lógica subyacente en los ejemplos expuestos es en cualquier caso plenamente válida, independientemente de la notación con la que se representen.

El autor de este trabajo es coordinador del "Grupo de Programación Funcional y Lógica" (UNL, UNP, Argentina), cuyos miembros han publicado también otros interesantes documentos y trabajos sobre diversos aspectos de la programación lógica, localizables en la página web de dicho grupo (tengan paciencia con las descargas, el servidor es bastante lento, y se demoran un cierto tiempo). La utilización de la notación de Micro-Prolog en los trabajos de este grupo, se explica en razón de que sus miembros han desarrollado un intérprete para Prolog, Edulog, orientado hacia fines educativos y la utilización en sus cursos y seminarios, que precisamente hace uso de la notación que venimos comentando. El proyecto parece estar paralizado, al menos en su forma de comunicación pública, ya que las páginas llevan bastante tiempo sin ser actualizadas. El prototipo Edulog es accesible desde un enlace ubicado en la página de la asignatura "Programación Funcional y Lógica", si bien el archivo de descarga está protegido por contraseña. Supongo que poniéndose en contacto con los responsables del proyecto, y exponiéndoles las razones por las que se quiere acceder a su uso, no habrá ningún problema en conseguir la clave correspondiente.

La notación implementada por Micro-Prolog es más limitada y menos flexible que la propia del estándar de Edimburgo: así por ejemplo, los posibles nombres de variables están muy restringidos, y el intérprete se conformará con la primera solución que satisfaga el objetivo planteado, en contraposición a lo habitual en los intérpretes actuales basados en el Prolog estándar, que es tratar de proporcionar todas las posibles soluciones hasta agotar la base de conocimientos del programa y las posibilidades de unificación de las variables en juego. Otras diferencias se refieren a la utilización, por parte de Micro-Prolog, de predicados predefinidos de carácter particular.

Las diferencias básicas entre ambos tipos de notaciones están perfectamente explicadas, con ejemplos, en el documento "Diferencias entre la notación de Micro Prolog y la de Edimburgo" que encontramos en la página de la asignatura mencionada, si bien el archivo comprimido que sirve como medio de descarga al original en formato Word, está también protegido por contraseña, por lo que de nuevo se hace necesario ponerse en contacto con sus autores con el fin de obtener la pertinente autorización.

Micro-Prolog fue un dialecto del lenguaje Prolog creado alrededor de 1980 para ser ejecutado originalmente en los primeros ordenadores personales, equipos de poca capacidad de procesamiento y memoria en comparación con los parámetros actuales, basados en el procesador Z-80 de Zilog Corp., sucesor del 8085 de Intel, y el S.O. CP/M, antecesor del PC/MS-DOS (ZX Spectrum, Commodore 64, etc.). El compilador e intérprete LPA Prolog Professional soporta la notación Micro-Prolog, aunque hay que advertir que se trata de un "dialecto" completamente en desuso, dadas sus evidentes limitaciones, siendo la notación del estándar de Edimburgo (también conocida como sintaxis DECsystem-10) la más extendida, y por tanto la empleada en la práctica totalidad de las implementaciones actuales de intérpretes para el lenguaje Prolog. Desde este otro enlace se puede descargar el intérprete original para Micro-Prolog.

W.F. Clocksin y C.S. Mellish, en su libro "Programación en Prolog" (Gustavo Gili, 1993; ISBN: 84-252-1339-8), dedican un apartado completo, "Apéndice E - Micro-Prolog", a la explicación de la sintaxis implementada por Micro-Prolog:

"La sintaxis de Micro-Prolog es bastante diferente [...] La idea básica es que sólo existe un tipo de término: la lista. Si queremos construir el «término» con funtor f y cuatro argumentos, usamos de hecho una lista de cinco elementos, con f como la cabeza, y los cuatro argumentos apareciendo sucesivamente como los elementos restantes. Así, lo que en la sintaxis de nuestro «núcleo» se escribiría: f(a,g(2,3),c) se escribiría en Micro-Prolog: (f (g 2 3) c). Aquí también vemos la sintaxis diferente para listas, en donde las listas van entre paréntesis, con sus elementos separados por espacios.

Las cláusulas se representan como listas de términos, en los que el primero es la cabeza de la cláusula, y el resto son objetivos, que tomados como una conjunción, forman el cuerpo. He aquí una cláusula más complicada [...]:

((alterar (z1|z2) (x|y))
     (cambiar z1 x)
     (altera z2 y)
)

Esto es la segunda cláusula de [el predicado] alterar de la sección 3.4. [...]

alterar([H|T],[X|Y]):- cambiar(H,X), alterar(T,Y).

[...] Los nombres y propósitos de los predicados predefinidos varían considerablemente de los que se han visto a lo largo de este libro [...]"

En Programación en Prolog, Apéndice E - Micro-Prolog

Por otra parte, en Turbo Prolog los programas se dividen en secciones diferenciadas: dominios, cláusulas, predicados, base de datos y objetivos. La explicación, tanto sobre la sintaxis de Micro-Prolog, como sobre otros aspectos generales de este dialecto (predicados predefinidos particulares, facilidades para la depuración del código, etc.), tiene cierta extensión, por lo que me remito a la obra referenciada para obtener más información al respecto, y en particular, además de al referido Apéndice E, a los apéndices "C - Diferentes versiones de Prolog" (ofrece una breve visión general sobre este particular), y "D - Prolog del DECsystem-10".

Peter Van Roy (Universidad Católica de Lovaina, Bélgica, Dpto. de Ingeniería Informática), una de las figuras más destacadas en el mundo de la programación lógica, es autor de un artículo, de lectura más que recomendable, referido a la evolución del lenguaje Prolog en la década que transcurre a partir de la aparición de la arquitectura WAM: "1983-1993: The Wonder Years of Sequential Prolog Implementation" (en formato PS):

"This report surveys the major developments in sequential Prolog implementation during the period 1983-1993. In this decade, implementation technology has matured to such a degree that Prolog has left the university and become useful in industry. The survey is divided into four parts. The first part gives an overview of the important technical developments starting with the Warren Abstract Machine (WAM). The second part presents the history and the contributions of the major software and hardware systems. The third part charts the evolution of Prolog performance since Warren?s DEC-10 compiler. The fourth part extrapolates current trends regarding the evolution of sequential logic languages, their implementation, and their role in the marketplace."

"By 1983 Warren had developed the WAM, a structure-copying execution model for Prolog that has become the de facto standard implementation technique [...]. The WAM defines a high-level instruction set that maps closely to Prolog source code. [...]"

En "1983-1993: The Wonder Years of Sequential Prolog Implementation"

La tesis doctoral de Peter Van Roy versaba precisamente sobre la implementación de la WAM: "Can Logic Programming Execute as Fast as Imperative Pro-gramming?" (PhD Thesis, Department of Computer Science, U.C. Berkeley, Report UCB/CSD 90/600, 1990).

La aparición de la Máquina Abstracta de Warren o WAM (David H.D. Warren, 1983) supuso un punto de inflexión en la evolución del lenguaje Prolog, por cuanto comportaba la definición de un conjunto de instrucciones de alto nivel y un modelo de ejecución para este lenguaje, y la materialización de la programación lógica con restricciones (Constraint Logic Programming, CLP). Supone la base, adoptada como estándar de facto, para la implementación de intérpretes portables para el lenguaje Prolog, convirtiéndolo en un lenguaje multipropósito con características similares a las de los lenguajes compilados de carácter procedimental, en lo que alos tiempos de ejecución se refiere. Así, en el sitio web del intérprete SWI-Prolog leemos:

"SWI-Prolog is a Prolog implementation based on a subset of the WAM (Warren Abstract Machine)."

"[...] is based on a very restricted form of the WAM [...] described in Bowen & Byrd, 1983 which defines only 7 instructions. Prolog can easily be compiled into this language and the abstract machine code is easily decompiled back into Prolog. As it is also possible to wire a standard 4-port debugger in the WAM interpreter there is no need for a distinction between compiled and interpreted code. Besides simplifying the design of the Prolog system itself this approach has advantages for program development: the compiler is simple and fast, the user does not have to decide in advance whether debugging is required and the system only runs slightly slower when in debug mode. The price we have to pay is some performance degradation (taking out the debugger from the WAM interpreter improves performance by about 20%) and somewhat additional memory usage to help the decompiler and debugger."

"SWI-Prolog extends the minimal set of instructions described in Bowen & Byrd, 1983 to improve performance. While extending this set care has been taken to maintain the advantages of decompilation and tracing of compiled code. The extensions include specialised instructions for unification, predicate invocation, some frequently used built-in predicates, arithmetic, and control (;/2, |/2), if-then (->/2) and negation-by-failure (\+/1)."

En SWI-Prolog Reference Manual - 1.1 SWI-Prolog

La función de esta máquina virtual, dentro del núcleo del intérprete, es compilar las instrucciones escritas en lenguaje de alto nivel a instrucciones en lenguaje máquina, de forma similar a como lo hace la máquina virtual Java (JVM). La arquitectura WAM ha permitido en consecuencia desarrollar versiones de Prolog "compilado" a nivel de ejecución, aun cuando los programas se sigan guardando y ejecutando desde archivos que contienen código escrito en lenguaje de alto nivel. De manera general, una máquina virtual es por tanto un procedimiento abstracto para ejecutar conjuntos de instrucciones escritas en un lenguaje formal, como puede ser en este caso Prolog.

"[...] si utilizamos un entorno de programación interpretado de Prolog [...] la eficiencia, en cuanto a velocidad de ejecución se refiere, disminuye, al igual que en cualquier lenguaje interpretado, frente a un lenguaje compilado.

El conjunto de instrucciones de las computadoras actuales resulta muy pobre en relación con la semántica de Prolog, por lo que la mayoría de los compiladores de Prolog [...] realizan una compilación a un lenguaje intermedio en vez de hacerlo directamente a lenguaje máquina. El lenguaje más popular es el Warren Abstract Machine (WAM) [...] conjunto de instrucciones abstractas utilizable en Prolog y que se puede interpretar o traducir a lenguaje máquina. Existen otros compiladores que traducen Prolog a un lenguaje de alto nivel como Lisp o C, y utilizan dicho compilador para traducir a lenguaje máquina.

Antes del trabajo de Warren sobre la compilación de la inferencia en Prolog, la programación lógica resultaba excesivamente lenta para su uso generalizado. Los compiladores diseñados por Warren y otros permitieron a Prolog alcanzar velocidades adecuadas [...] En fechas más recientes, la aplicación de la moderna tecnología de compilación [...] ha permitido a Prolog alcanzar velocidades tan óptimas que lo hace competir con C en cuanto a diversos aspectos estándar [...]. [...] el hecho de poder escribir un planificador o un analizador de lenguaje natural en unas cuantas decenas de líneas de Prolog, hacen que éste sea más preferible que C en la realización de los prototipos de gran parte de los proyectos de investigación de IA a escala reducida."

Fuente (estructura general de marcos de la página citada)

Más información al respecto: "Warrens's Abstract Machine: A Tutorial Reconstruction" (en PDF; Hassan Aït-Kaci; The MIT Press, Cambridge, MA, 1991).

En el siguiente trabajo se describe el sistema y la notación DECsystem-10 Prolog, en la que se basa el estándar de Edimburgo, que recordemos es de facto el sistema Prolog estándar en la actualidad, recogido la norma ISO vigente referida a este lenguaje (ISO/IEC 13211-1:1995 Part 1: General core):

"DECsystem-10 Prolog User's Manual". D.L. Bowen (ed.), L. Byrd, F.C.N. Pereira, L.M. Pereira, and D.H.D. Warren, Department of Artificial Intelligence, University of Edinburgh, November 10, 1982.

Si bien el formato del anterior documento es ".doc", se trata realmente de un archivo de texto plano, por lo que se descoloca la disposición del mismo si se abre con MS Word. También: versión en HTML, y traducción al castellano de este manual, limitada a los tres primeros capítulos.

El DECsystem-10 Prolog fue una implementación creada y desarrollada (1977, 1980) por D. Warren y otros (F. Pereira, L. Byrd, L. Pereira) en el Departamento de Inteligencia Artificial de la Universidad de Edimburgo, para operar en sistemas informáticos DECsystem-10. Junto con el Prolog descrito en la obra referenciada de Clocksin y Mellish, las versiones del DEC-10 Prolog y sus posteriores desarrollos constituyen la base del estándar o sintaxis de Edimburgo.

Las iniciales DECsystem-10 hacen referencia al sistema informático sobre el que se basó la implementación Prolog de la Universidad de Edimburgo que venimos comentando, fabricado por Digital Equipment Corp. Los DECsystem-10/20 eran sistemas de arquitectura de 36-bit, cuyas primeras versiones datan del año 1971. Cuando hablamos de este tipo de sistemas no hay que pensar en los PCs, posteriores en el tiempo y orientados inicialmente hacia otro tipo de usuario final, sino que se trataba de equipos situados, por potencia de procesamiento y cálculo (y todo sea dicho, por dificultad de manejo y operación), en la escala de los grandes equipos informáticos conocidos como "mainframes". No es infrecuente encontrar, en guías y manuales antiguos del lenguaje Prolog (por ejemplo los referidos a C-Prolog [en HTML] [en PS], y en general a las implementaciones derivadas de la primera especificación DECsystem-10 Prolog), referencias a TOPS-20, evolución de los DECsystem-10/20, y a otros sistemas de DEC.

Sobre la base de este primer intérprete-compilador para Prolog se creó, en 1983, uno de los primeros intérpretes puros para dicho lenguaje, C-Prolog (F. Pereira, D. Bowen, L. Byrd), escrito en lenguaje C, que contribuyó a consolidar el estándar de Edimburgo, como referencia para posteriores implementaciones.

Para finalizar esta anotación, mencionar el ejemplo de aplicación práctica del lenguaje Prolog a la resolución de juegos y acertijos lógicos descrito en "Solving Rubik's Cube Using the Bestfast Algorithm and Profile tables - A Prolog program and demonstration of an efficient heuristic search method" (por D.L. Winston Miller). Como el propio título indica, en este texto se explica el fundamento teórico y el funcionamiento de un programa diseñado para efectuar la búsqueda de los mejores métodos posibles de resolución del problema planteado por el famoso Cubo de Rubik. Los archivos que conforman el programa (ver al final del documento) están escritos originalmente para ser ejecutados bajo el intérprete Arity Prolog (de uso libre) si bien, al soportar la notación y predicados del estándar de Edimburgo, el programa en principio debería también poder ejecutarse correctamente bajo SWI-Prolog.

El programa hace uso de un algoritmo de búsqueda A* (ejemplo), basado en el tipo conocido como "best-first search", derivado a su vez del método de búsqueda "breadth-first search" o "búsqueda primero en anchura" (ejemplo), que evalúa cada nodo del mismo nivel, dentro del árbol de búsqueda (entendiendo por tal la representación en forma de grafo dirigido -los nodos que lo forman están conectados mediante flechas que indican la dirección del movimiento- de un determinado problema de búsqueda), antes de continuar el proceso en el siguiente nivel de profundidad. En contraposición a este método se sitúa la búsqueda "depth-first" o "primero en profundidad" (ejemplo), en la que se explora cada "rama" del árbol hasta llegar al "nodo terminal", antes de proceder a la búsqueda por otro camino. Este es precisamente el tipo de búsqueda "interna" por defecto que lleva a cabo el lenguaje Prolog (búsqueda en profundidad y de izquierda a derecha en un árbol And-Or) dentro de la base de conocimientos compilada, al tratar de satisfacer los objetivos.

"The A* [...] is an efficient and widely used pathing algorithm. The A* keeps track of the cost of getting from point A to point B and the overall cost of getting from the beginning point to the end point. The algorithm follows the path of least cost to find a solution. The A* uses up a lot of memory and can be very slow on rough terrain - therefore it is not used for real-time robotics pathing too often."

Fuente

A los dos tipos básicos de algoritmos de búsqueda mencionados (existen otros muchos), se les pueden añadir eventualmente métodos heurísticos de evaluación, consistentes en reglas capaces de valorar si, en base a determinado tipo de información previa, la búsqueda está siguiendo el camino correcto, para de esta forma aumentar la probabilidad de dar con la solución correcta. Los métodos heurísticos tratan de aplicar dos criterios de búsqueda: a) elección de los caminos que es posible que fallen con mayor probabilidad, para de esta forma "podar" el espacio de búsqueda y así reducir su tamaño, o bien b) comprobación, en primer lugar, de los caminos con mayor probabilidad de éxito. Las búsquedas heurísticas son por tanto búsquedas basadas en la experiencia. La adición de capacidades heurísticas a los métodos de búsqueda "breadth-first", da lugar a los algoritmos "best-first search", como el A* utilizado en el programa aplicado a la resolución de los estados del Cubo de Rubik.

Estos tres tipos básicos de algoritmos de búsqueda, así como los conceptos y teoremas básicos de la Teoría de Grafos [1] [2] [3] necesarios para la comprensión y conocimiento de sus mecanismos de funcionamiento, se describen ampliamente en los capítulos 11. "Basic Problem-Solving Strategies", 12. "Best First: A Heuristic Search Principle", y 13. "Problem Reduction and AND/OR Graphs" de la obra de Ivan Bratko "Prolog programming for Artificial Intelligence" (Addison-Wesley, 1994; ISBN: 0-201-41606-9).

Por otra parte "Artificial Intelligence Through Search" (C.J. Thorton, B. du Boulay) es un libro que aborda de forma especifica la cuestión de los métodos y algoritmos utilizados en espacios de búsqueda (definidos éstos por el conjunto de todos los nodos de un grafo dirigido). Desafortunadamente, en la versión electrónica de este libro se pierden gran parte de las figuras y esquemas del original impreso, lo cual dificulta la comprensión de estas cuestiones, que de por si tienen cierta complejidad.

Más información:

• "Los Juegos como Herramienta Docente. Formalización de Juegos Lógicos en Prolog" (F. Llorens, Mª Jesús Castel, F. Mora y C. Villagrá; en PDF).
• Turbo Prolog.
• Early History of Prolog: The birth of Prolog / La naissance de Prolog (en PDF; P. Roussel).
• Notas de curso sobre Prolog: Chapter 7 Graphs (representación de grafos en Prolog).
• Código fuente de algunos algoritmos A*.
• Otro ejemplo de implementación del algoritmo de búsqueda A* en Prolog, y en dos versiones: a) en sintáxis Turbo Prolog, compatible con Visual Prolog + IDA* (Iterative Deepening A* search); y b) en sintáxis LPA Win-Prolog.
• The A* algorithm in Prolog (en Prolog Tutorial de J.R.Fisher).
• A* for the Masses (en generation5.org).

[1] comentarios | # | lista |