<$BlogRSDUrl$>

Pro·Log·[IR]

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

«Algorithm = Logic + Control» Robert Kowalski (1979)

¡Importante! esta página hace uso de estilos recogidos en la especificación CSS2, no soportados por el navegador que está utilizando. Por favor, lea esta recomendación al respecto.

Archivo

Guardado por meses.

Enlaces

Los siguientes listados son una referencia a partir de la cual ampliar la búsqueda de sitios relacionados (i).

Bitácoras en castellano

Bitácoras en inglés

Directorios, metablogs

Programación lógica, Inteligencia Artificial, Recuperación de Información

Usabilidad, Arquitectura de la Información

Listas, foros, wikis

Matemáticas, ciencias

Miscelánea

Búsquedas

Búsqueda simple en varios de los motores más conocidos. Para mayor precisión, entrar en la página correspondiente e ir al apartado de búsqueda avanzada.

Búsqueda con Google
 

Búsqueda con Yahoo!
 

Búsqueda con AlltheWeb

Varios

Esta página traducida:

Traducción al catalán, internostrum; traducción al portugués, universia.

Reciba un aviso de nuevos comentarios (por Bloglet).


Agregue este sitio a su lector de "feeds" (sindicación mediante el sistema Atom).

Sobre este sitio

Espacio dedicado a la programación lógica y la recuperación de información, con una atención especial al lenguaje Prolog y otros lenguajes afines, pertenecientes al paradigma lógico y declarativo. También se tratará de hablar de estos temas desde la perspectiva de la Biblioteconomía y la Documentación.

En esta página

13.11.05

Algoritmo de aprendizaje ID3

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:

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

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:

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:

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:

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

[0] comentarios | # | lista |

11.11.05

Técnicas mnemotécnicas y acertijos de ingenio

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

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

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. [...]"

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

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

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:

[1] comentarios | # | lista |


Pro·Log·[IR],

Publicación: Blogger | Estadísticas: eXTReMe Tracking

Se recomienda ver este sitio con Mozilla 1+, Firefox 0.8+ ó Netscape 7+. Si no queda más remedio, con IE 6+. Si lo desea, comunique cualquier problema al respecto. También será bien recibida cualquier sugerencia sobre el contenido. La fuente de letra preferente es Georgia. Se prohibe la utilización del diseño de la página salvo autorización expresa del autor. Los contenidos escritos son de uso libre, siempre que se cite la fuente.