En esta parte del curso de doctorado se introduce una aproximación reciente al aprendizaje automático inductivo que se basa en el uso de la lógica clausal como lenguaje formal y en la que los conceptos aprendidos son programas lógicos. Inducción y deducción son procesos subyacentes en los agentes inteligentes. La Inducción hace referencia al proceso intelectual que va desde lo particular a lo general, y juega un papel importante en la adquisición de conocimiento y en el aprendizaje. La deducción es, por el contrario, una forma de razonamiento con y sobre conocimiento adquirido, que establece relaciones de tipo causa-efecto entre hechos existentes sin generar nuevos hechos. A pesar de estas diferencias, la deducci ón y la inducci ón están fuertemente interrelacionadas. La capacidad de razonar sobre un dominio de conocimiento se basa en reglas sobre este dominio que pueden ser adquiridas de algún modo; y la capacidad de razonar puede a menudo guiar la adquisición de nuevo conocimiento.
En el curso analizaremos las distintas aproximaciones que permiten realizar el proceso de inducción mediante métodos que progresen desde la hipótesis más general refinándola por especialización (top-down), o bien siguiendo un método que inicie el proceso desde los ejemplos positivos (las hipótesis más específicas) generalizándolos en los siguientes pasos (bottom-up). Estos métodos han sido utilizados en diversos sistemas de Programación Lógica Inductiva (ILP) que serán revisados en el curso.
La ILP se ha aplicado con éxito en áreas muy diversas. Mostraremos algunos de los resultados obtenidos en algunas de estas áreas. En particular, centraremos nuestro interés en la ingeniería del software y en la obtención de conocimiento a partir de bases de datos (data mining).
A pesar de todas las ventajas de la ILP, ésta ha heredado las principales limitaciones de la Programación Lógica (LP) y los lenguajes lógicos como Prolog: la imposibilidad de definir funciones y tipos (de una forma natural), la ausencia de constructores de orden superior y la evaluación perezosa (lazy evaluation). Aunque todas estas características están bien soportadas por los lenguajes funcionales, éstos a su vez carecen de la potencia computacional que proporcionan las variables lógicas y la unificación. Por ello, en los últimos aņos ha crecido el interés por la integración de ambas familias de lenguajes. Los lenguajes integrados explotan completamente las facilidades de la programación lógica en un sentido general: funciones, predicados e igualdad. Una de las aproximaciones más relevantes es la programación lógico-funcional, en la que los programas son programas lógicos aumentados con teorías ecuacionales de Horn. Presentaremos un marco de inducción para esta clase de lenguajes.
El curso comienza con una panorámica general sobre programación lógica. Revisaremos las nociones básicas sobre las semánticas operacional (basada en el procedimiento de resolución SLD) y declarativa (que define el significado de los programas) e introduciremos un lenguaje lógico (Prolog).
En este primer tema se presentarán los conceptos fundamentales
del paradigma de programación lógica: resolución SLD,
noción de modelo y significado de un programa.
En este apartado daremos una definición informal de este
paradigma y analizaremos su conexión con la inducción
de conceptos y el descubrimiento de conocimento. Básicamente,
la ILP induce hipótesis (programas lógicos) desde un
conjunto de evidencias positivas y/o negativas (hechos) haciendo uso de un
cierto conocimiento de base (otro programa lógico).
Dado que la inducción es el proceso mediante el cual es posible
generar programas que sean una explicación de los hechos
observados, en este tema estudiaremos el espacio de hipótesis
posibles y las distintas formas de efectuar la búsqueda en el mismo
de la hipótesis deseada.
En este tema veremos las distintas reglas inductivas que permiten
generar las hipótesis progresando desde la más
específica mediante un proceso de generalización. Estas
reglas se obtienen invirtiendo las principales reglas deductivas.
Como ejemplo, presentaremos diversos sistemas ILP que usan estos
métodos.
En este tema presentamos los métodos que
generan las hipótesis progresando desde la más
general mediante un proceso de especialización y su uso
en algunos sistemas ILP.
A continuación analizaremos otras propiedades de los sistemas
ILP como son la incrementalidad o la interactividad. Veremos ejemplos de
ellos.
Resumiremos algunas de las aplicaciones más destacadas de la
ILP, centrándonos en la Ingeniería del Software y en la
adquisición de conocimientos en bases de datos. Para esta
última introduciremos un formalismo conocido como árboles de
decisión, muy utilizado en el aprendizaje de conceptos para
problemas de clasificación.
En este tema presentaremos un marco genérico para la inducción de programas lógico-funcionales. La regla inductiva utilizada se define a partir de la inversión de uno de los mecanismos operacionales más extendido para este tipo de programas. Presentaremos el sistema FLIP, una implementación de este marco así como algunas extensiones introducidas para mejorar su eficiencia así como para poder abordar problemas de data mining.