Capítulo 1 :

Introducción

Nos encontramos en la denominada "sociedad de la información", porque se destinan gran cantidad de recursos a la adquisición, almacenamiento, procesado, análisis, etc. de la información. El conocimiento más valioso suele aparecer oculto entre los datos recogidos, en forma de patrones o reglas que relacionan entre sí otras partes más superficiales de la información. Este conocimiento se ha venido obteniendo, tradicionalmente, mediante análisis manual, aplicando la inferencia inductiva sobre el conjunto de datos de partida.

Sin embargo, la adquisición y almacenamiento de los datos se realiza a un ritmo cada vez mayor. Por ejemplo, los satélites de observación de la Tierra generarán, previsiblemente, del orden de un petabyte de datos (1015 bytes) diariamente a finales de siglo; otros sistemas menos sofisticados, como las transacciones realizadas en un supermercado, cabinas de información de turismo, operaciones de tarjetas de crédito, etc. también son susceptibles de generar un volumen de datos imposible de analizar de forma manual. La explosión en el número de fuentes de información disponibles en Internet ofrece una nueva oportunidad de búsqueda y extracción de información útil a partir de esta "base de datos" dinámica y creciente. Se estima que cada 20 meses se duplica la cantidad de información en el mundo. Parece claro que el clásico método hipotético-deductivo de la ciencia positiva resulta inoperante ante tal avalancha de datos, al menos, aplicado de la forma tradicional, esto es, analizando manualmente los datos disponibles. Cada vez se necesita más la ayuda de ordenadores potentes para automatizar el proceso inductivo, para analizar de forma inteligente las montañas de datos existentes, y extraer de ellas ese conocimiento oculto y valioso. Sin duda, el término "minería de datos", con que se conocen las nuevas técnicas de análisis automático, refleja bastante bien esta idea.

Por otro lado, el esfuerzo inicial por adquirir conocimiento del mundo real está dejando paso a un mayor esfuerzo por conocer aspectos del propio conocimiento. Hoy en día nos encontramos este último punto, quizá como consecuencia de los fallos en el conocimiento adquirido mediante ese esfuerzo inicial. La preocupación principal ya no es la mera adquisición de conocimiento, sino la delimitación de su alcance y validez; necesitamos asignar un grado de certeza al conocimiento, saber en qué medida conocemos algo.

La incertidumbre está asociada, de forma inseparable, con la información. Aunque existen diferentes formas de incertidumbre, cabe destacar la que se produce como consecuencia de la imprecisión y subjetividad propias de la actividad humana. En muchas ocasiones sacrificamos parte de la información precisa disponible por otra más vaga pero más robusta, lo que permite manejar de forma eficiente la complejidad asociada al mundo real. Muchos de los conceptos manejados habitualmente son, en sí mismos, vagos o borrosos, es decir, sus límites no están perfectamente determinados, y no por ello carecen de significación. La lógica borrosa y la teoría de conjuntos borrosos ofrecen un método natural para representar esa imprecisión y subjetividad humanas.

La combinación de técnicas de minería de datos con la incertidumbre asociada a los conceptos del mundo real, desde el punto de vista humano, nos conducen a la inducción automática de conocimiento con incertidumbre, tema sobre el que se desarrollará esta tesis

1.1 Justificación de esta tesis

Esta tesis se enmarca dentro del vasto campo de la inducción automática de conocimiento a partir de bases de datos. En particular, dentro del aprendizaje empírico de primer orden y la programación lógica inductiva, en gran auge desde hace unos 10 años.

Aunque muchos sistemas de aprendizaje basados en la lógica de proposiciones ya han demostrado su validez al aplicarlos sobre conjuntos de datos reales, en general, no ocurre lo mismo con los sistemas de programación lógica inductiva. La expresividad de la lógica de predicados permite construir descripciones sencillas, aunque dificulta enormemente la construcción de las mismas, al producirse una explosión combinatoria en el espacio de búsqueda. Esto hace que la búsqueda de la mejor descripción se convierta en una difícil y costosa tarea, sólo posible mediante la aplicación de métodos heurísticos, ya usados por la mayoría de estos sistemas.

La aplicación de sistemas de "laboratorio" para inducción de conocimiento a partir de bases de datos reales presenta dificultades adicionales, asociadas al ruido e incertidumbre de la realidad, al gran volumen de datos existente en una base de datos real, así como a la dinamicidad e incompletitud de algunos datos.

El trabajo central de esta tesis se orienta, precisamente, hacia la aplicación de un sistema de programación lógica inductiva bien conocido, FOIL ( [Quinlan, 90] ), sobre bases de datos reales.

Para ello, se analizará, en primer lugar, la parte heurística que utiliza, en concreto la función Ganancia de evaluación de literales, que presenta algunas deficiencias en situaciones concretas que pueden presentarse no sólo en la realidad sino también en pequeños ejemplos de entrenamiento. Este punto guarda una estrecha relación con un problema bien conocido en muchos sistemas de optimización: los máximos locales. Una sustitución de esta función de evaluación por otra basada en medidas del interés de los literales, según ciertos criterios, así como algunas modificaciones en la construcción de los conjuntos de entrenamiento intermedios, mejoran sustancialmente el comportamiento global del algoritmo, solventando los problemas detectados.

Por otro lado, se introducirá una importante mejora en el sistema anterior, enfocada hacia la manipulación de la incertidumbre asociada a la realidad. Se propone la utilización de la lógica borrosa y de conjuntos borrosos para representar, de un modo más natural, conceptos borrosos dentro de la base de datos relacional de partida. La adaptación del algoritmo para manejar relaciones borrosas a la entrada y construir definiciones con incertidumbre a la salida amplía las posibilidades y la expresividad (más afín a la concepción humana de la realidad) del sistema original. Esto supone una interesante aportación dentro de la programación lógica inductiva, ya que los sistemas existentes hasta ahora no van más allá de la manipulación de relaciones ordinarias (booleanas) o, a lo sumo, de relaciones en las que algunos atributos tienen asociado un factor de incertidumbre (enfocados a la lógica de proposiciones extendida). El sistema que se propone, por el contrario, maneja relaciones borrosas en sí mismas (con incertidumbre asociada a sus tuplas) y las descripciones que construye se basan en la lógica borrosa y en la lógica de predicados. Es decir, este sistema podría decirse que utiliza la "lógica borrosa de primer orden" para representar el conocimiento inducido. Sobre este punto será necesario desarrollar algunos conceptos teóricos y definiciones nuevas.

1.2 Objetivos

El principal objetivo que se planteó al comenzar este trabajo fue la adaptación de un sistema de programación lógica inductiva para poder aplicarlo sobre datos reales y su extensión para poder manejar conocimiento con incertidumbre, tanto en los datos de entrada (en la base de datos relacional de partida) como en las definiciones lógicas que se induzcan.

Para conseguir este objetivo, se desglosó el mismo en diferentes subobjetivos:

  1. Revisión de diferentes sistemas de aprendizaje basados en la programación lógica inductiva, así como de diferentes tipos de incertidumbre y de las teorías matemáticas adecuadas para su representación. Como resultado de este punto se seleccionó un sistema de aprendizaje de primer orden (FOIL), por su flexibilidad para representar el conocimiento, frente a otros métodos de representación del mismo. Por otro lado, se eligió un modo de representar la incertidumbre en la información (lógica borrosa), adecuado para el tipo de conocimiento que se maneja habitualmente, desde un punto de vista humano. A partir de ambas selecciones se planteó la construcción de un único sistema que incorporase las mejores ventajas de ambos: potencia expresiva de la lógica de primer orden y utilidad de la representación de la incertidumbre.
  2. El algoritmo inicial, FOIL, se analizó y recodificó en C++ para facilitar su mantenimiento y la incorporación de mejoras en algunos aspectos en los que presenta deficiencias, principalmente en su parte heurística. Con estas modificaciones se pretendía corregir algunos problemas que pueden presentarse en bases de datos reales, y que conducen a la no construcción de definiciones o a la construcción de definiciones más complejas de lo necesario. Asimismo se realizaron otras pequeñas modificaciones para facilitar el acceso a grandes volúmenes de datos (muestreo en el conjunto de entrenamiento), introducción de conocimiento de base (relaciones intensionales), etc.
  3. Extensiones orientadas hacia la lógica borrosa de primer orden. En este punto, cabe adelantar la no existencia de un formalismo teórico que incorpore de forma simultánea la lógica de predicados y la lógica borrosa, por lo que ha sido necesario redefinir diferentes aspectos teóricos de la lógica de predicados, para asentar las bases de una lógica borrosa de primer orden. Por otro lado, se amplió el formato de la base de datos de entrada para permitir, además de las relaciones ordinarias, la definición de relaciones borrosas, en el sentido estricto de dicho término: relaciones en las que sus tuplas incorporan un factor de incertidumbre, en forma de grado de pertenencia a la relación. Y, finalmente, se modificaron el algoritmo de partida y sus heurísticos para que se pudiera manejar esta información y se permitiera construir definiciones borrosas (con literales borrosos), tanto para relaciones ordinarias como borrosas. Las definiciones que se inducen siguen incorporando un factor de incertidumbre, similar a una medida de probabilidad que, del mismo modo que en FOIL, da una idea de su precisión, para poder ser aplicadas en un sistema experto.

1.3 Estructura de la tesis

Cada uno de los objetivos expuestos en el apartado anterior será tratado en un capítulo diferente de la tesis:

Para la descripción de FZFOIL se utilizan diferentes conceptos de la lógica borrosa que, a modo de resumen, se recopilan en el apéndice A : operadores en conjuntos borrosos, relaciones borrosas y proposiciones borrosas.

 

A continuación (capítulo 5 ) se presentan y analizan algunos resultados obtenidos, tras la aplicación del algoritmo sobre una base de datos real, procedente del proyecto SEIC (PC-183, dentro de la línea de "Acciones Especiales PASO"). En este capítulo, además, se plantean otros puntos de interés, como el análisis de la complejidad del algoritmo (algunas expresiones matemáticas utilizadas en este punto se desarrollan en el apéndice B ). En el apéndice C se incluye un pequeño manual de usuario y de instalación de la versión de FZFOIL implementada, con la que se han obtenido los resultados; este manual describe el formato de los datos de entrada y las opciones y órdenes seleccionables por el usuario, así como instrucciones sobre dónde conseguir el programa y cómo instalarlo.

 

Finalmente, el capítulo 6 recopila diferentes conclusiones y propone posibles líneas de investigación futuras.