PDF de programación - Tesis: Ricardo Vazquez - APRENDIZAJE MEDIANTE INFERENCIA INDUCTIVA

CENTRO DE INVESTIGACION Y BE

ESTUDIOS AVANZADOS DEL

I. P. N.

B I B L I O T E C A
INGENIERIA ELECTRICA

CENTRO DE INVESTIGACION Y ESTUDIOS AVANZADOS

DEL

INSTITUTO POLITECNICO NACIONAL

DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION

CENTRO DE INVESTIGACION Y t>l

ESTUDIOS AVANZADOS DEL

I. P. N.

B I B L I O T E C A
INGENIERIA ELECTRICA

"APRENDIZAJE MEDIANTE INFERENCIA INDUCTIVA"

Tesis que presenta el M. en C. M. Ricardo Vázquez Alvidrez
para obtener el grado de MAESTRO EN CIENCIAS en la especialidad
de INGENIERIA ELECTRICA. Trabajo dirigido por el Dr. Zdenek
Zdrahal' H. y por el Dr. Guillermo Morales Luna.

México, D. F. Julio de 1988.

C O N T E N I D O

PREFACIO ............................................. i i i
RESUMEN ............................................. iv
INTRODUCCION ......................................... 1
I NOCIONES GENERALES

Aprendizaje..... ................................. 4
Aprendizaje y Reconocimiento de Patrones ....... 6
Aprendizaje de
vs Constructor-
de Clasificación ...................... ...... .
7
Buscador de Definición Clasificadora ........... 8

Conceptos

II FUNDAMENTOS

Nociones de Lógica y Notación ................... 10
Formalización del Objetivo del Programa ........ 12
Fórmulas Tipo "H-de-N" .......................... 16
Funcionamiento Global del Programa ............. 17
Ufia Base de Conocimientos
Como Dato de Entrada............................ 21

III INPLEMENTACION

.

Búsqueda

Generalizaciones en la

Leyes de Unificación Asumidas..... ............. 23
Uso de
de una Definición de Subclase ................... 24
Leyes de Generalización.... ..................... 26
Inconveniencia de Buscar
las Definiciones M¿s Restrictivas .............. 27
Búsqueda en la Dirección de lo Menor
Gc-rieral izaci ón .........................
30
Generalización por Pr edicados "l.i gahl es" ....... 33
Predicados y Funciones Especiales ....... .
33
CONCl USíCUES ......................................... 36
BIBLIOGRAFIA ......................................... 3G

USO DLL FFvGCRtiflA, ILUSTRACIONES.................... 39
INDICE D£ ILUSTRACIONES DE “PR00F-EVER"............ 43
INDICE IX ILUSTRACIONES DE "F-OR-TODO".... ........ í,

RESUMEN

de

Se propone y analiza un programa de cómputo para el
aprendizaje automático de conceptos mediante la
presentación de ejemplos. El programa busca una
fórmula lógica de primer orden que defina al
conjunto
a
de
contra-ejemplos
de trabajos
similares CMichal ski 1980 D aquí: los ejemplos son
descritos con fórmulas convencionales de cálculo de
predicados de primer orden, se admite como dato una
base de conocimientos y se es capaz de tomar en
cuenta la frecuencia con que la fórmula se cumple
ejemplos.
en

respecto
diferencia

ejemplos
A

contra

uno

los

ejemplos

y

los

.

CENTRO DE INVESTIGACION Y B£
-VANZADOS DEL ’

ESTUDIOS

I. P. N.

b i b l i o t e c a
INGENIERIA ELECTRICA

PREFACIO

Agradezco a todos los integrantes de
de
computación del CIEA del IPN : profesores, compañeros y
empleados por las facilidades otorgadas durante los estudios
y durante la preparación de este trabajo.

sección

la

De manera particular deseo expresar mi agradecimiento a:
Dr. Zdenek Zdrahal H. por su valiosa dirección y a mi esposa
El i a B. de Vázquez, por sus apreciables comentarios y apoyo
en general.

Agradezco también a la UAM azc. por haberme brindado algunas
facilidades y al Dr. Guillermo Morales L. por sus valiosos
comentari os.

•México D.F., Julio de 19B3

CENTRO DE INVESTIGACION Y 0£

ESTUDIOS AVANZADOS DEL

I. P. N.

b i b l i o t e c a
INGENIERÍA ELECTRICA

I N T R O D U C C I O N

un
aprendizaje en -forma automática ha prevalecido desde la creación
de las primeras computadoras electrónicas.

El interés

realizan

por

programas

que

En la década de los 50 y 60's

estudió
intensamente a los perceptrones . Este tipo de programa debía
identificar correctamente a una imagen presentada como una matriz
de bits, eligiendo una de entre varias posibles respuestas. Pero
más aun, en sesiones de entrenamiento debía automáticamente
aprender a identificar a estas imágenes ante la presentación
repetida de ellas y de la respuesta correcta por parte dei
"entrenador".

se

frase "aprendizaje a partir de ejemplos".

Esta es la idea que se encuentra en el fondo de la

matriz de bits.

En el caso de los perceptrones cada ejemplo era una

Una

aportación significativa a esta línea de
experimentación e investigación es la de P.H. Winston CBarr
,1982 3 .E l representa a cada ejemplo ya no como una matriz de
bits, sino como una gráfica (en el sentido de un conjunto de
nodos y de ligas entre ellos).

Además introduce la importante idea de obtener la
definición buscada ( en su caso una cierta gráfica ) mediante
operaciones de generalización y especialización desencadenados y
dirigidos por la comparación entre la definición previa y la
presentación de un nuevo ejemplo.

siguiente:

Por su parte Michalski C19803, contribuye con lo

% Propone un lenguaje al estilo de lógica de
predicados (..aunque algo confuso CBarr 19823).
% Propone un conjunto de leyes de generalización
que abarcan algunos conceptos sencillos de números
y de conjuntos (..p.ej, las afirmaciones "a<30" y
"b<20" se pueden generalizar a: "existe x tal que:
K < 30 ">.
La aceptación de la primer proposición nos da la
ventaja de representar a los ejemplos de una manera
más
aproximada a una descripción en lenguaje común* (.."lenguaje
natural"..).

Es más sencillo para una persona sin conocimientos

1

de Teoría de Gráficas describir a cada ejemplo mediante un
lenguaje de predicados que mediante una "gráfica".

La notación de Michal ski no es sin embargo una
notación estandard de lenguajes de predicados de primer orden.
De hecho, él menciona C Mi chal ski , 19803 que su lenguaje no se
puede reducir a uno de éstos. Esta opinión,por otro lado, no
ha
sido aceptada en la literatura del tema í Barr , 1982 3. Hay
algunos otros puntos oscuros en su trabajo, lo cual por supuesto
no le resta interés a sus contribuciones.

línea de los
trabajos que se han comentado, se propone incluir las siguientes
ideas:

En este documento, siguiendo

la

# El uso de bases de conocimiento de fondo.
t El uso de criterios estadísticos
* El uso de expresiones del tipo: " se cumplen m de
las n siguientes propiedades:...”.
Por otro lado, se usa además una notación

más
apegada a la común del cálculo de predicados de primer orden.
Esto contribuye a clarificar a la discución sobre el tema.

Se ha desarrollado un programa de cómputo que lleva
a la práctica éstas ideas, capaz de correr en una computadora
tipo "PC". Dicho programa realiza un aprendizaje automático ante
la presentación de ejemplos.

En el primer capítulo discutimos la noción de "
aprendizaje " , su asociación con el reconocimiento de patrones y
además algunas cuestiones generales sobre un programa buscador de
formas clasificadoras.

En el segundo introducimos algunos conceptos y

notación de la teoría matemática de la Lógica y damos una
descripción precisa de la función que realiza el programa que se
ha desarrollado. Es decir , aclaramos en que sentido se ha
realizado el objetivo de : " encontrar una definición de una
clase

objetos ".

de

En el tercero se discuten algunos de los problemas
específicos que se tuvieron que resolver para desarrollar el
programa. Algunas de las soluciones consistieron en buscar una
heurística adecuada.

C£NTB0 B£ INVEST|G1C|0|( y
ESTUDIOS AVANZADOS DEL

I. P. N.

b i b l i o t e c a
INGENIERIA ELECTRICA

Se incluye un apéndice: "Ilustraciones de Uso
del Programa". En él se revisan los conceptos discutidos en el
capítulo de implementación mediante varias i 1 ustraciones del uso
de las dos funciones principales del programa , "proof-ever" y
"■f-or-todo".

bibliográficas.

Se

incluye

una

sección

de

referencias

En la sección de "Conclusiones" se comenta sobre
los logros obtenidos , las limitaciones observadas y se sugieren
aplicaciones, líneas de investigación y mejoras a futuro .

CAPITULO I

N O C I O N E S G E N E R A L E S

QUE ES

APRENDIZAJE

No siempre resulta necesario o conveniente dar una supuesta
definición rigurosa de los conceptos manejados en una rama
técnica, de tal forma que esa definición abarque todas las
maneras de uso en el ámbito general.

A veces simplemente damos por sentado que el concepto se
"entiende" intuitiva o empíricamente hablando. Como ejemplo
podemos citar el caso del concepto de "tiempo" ,en Física.

Otras veces damos una definición más bien restringida, pero
que técnicamente es suficicentemente precisa como para sernos de
uti1idad.

Este es el caso de la noción de "aprendisaje".
Nuestro concepto restringido es el siguiente:
Supongamos que

definido

un

hemos

meta
experimentalmente comprobable para un programa de cómputo. Es
decir, contamos con una manera experimental y objetiva de decidir
si una respuesta del programa de cómputo , dada como consecuencia
de la llegada de ciertos "datos" o "estímulos", sabisface o no un
cierto requerimiento-meta.

objetivo

o

Además, supongamos que podemos definir bien a la máquina
al

generadora
programa.Llamemos temporalmente a esta máquina "habitat".

estímulos

entran

datos

que

los

de

o

Cap X

"Ta