1. Introducción: Aprendizaje inductivo de conceptos



Descargar 21,68 Kb.
Fecha de conversión07.02.2017
Tamaño21,68 Kb.

1. Introducción: Aprendizaje inductivo de conceptos

  • Inducción
    • Razonamiento desde propiedades de individuos a propiedades de conjuntos de individuos
  • Concepto
    • U- cjto universal de objetos
    • El concepto C es un subconjunto de objetos de U
  • Aprendizaje Inductivo de conceptos (reconocimiento de objetos en C)
    • Dadas instancias de C
    • Encontrar un procedimiento que nos diga cuando x  C, para cada x  U

1. Introducción: aprendiendo descripciones de atributos

  • Tarea de aprendizaje
    • Dado un cjto de ejemplos de prueba (training examples) -tuplas de valores de atributos etiquetados con un nombre de clase-
      • A1 A2 A3 Clase
      • ejemplo 1 v1,1 v1,2 v1,3 C1
      • ejemplo 2 v2,1 v2,2 v2,3 C2
    • Encontrar un cjto de reglas (una hipótesis) como una función de valores de atributo que es consistente y completo w.r.t. el conjunto de ejemplos de prueba
      • Clase = Cn if (Ai = vi,k) and (Aj = vj,l) and ...

1. Introducción: play tennis (ejemplos de prueba)

  • Outlook
  • Humidity
  • Wind
  • Yes
  • Yes
  • Yes
  • No
  • No
  • Sunny
  • Rainy
  • Overcast
  • High
  • Normal
  • Strong
  • Weak

1. Introducción: ILP

  • Motivación para ILP (visión ML)
    • Usar un formalismo de representación más expresivo que la lógica proposicional
    • Usar conocimiento de base en el aprendizaje (fundamental en AI)

1. Introducción: motivación

  • Motivación para ILP (visión KDD)
    • Datos almacenados en bases de datos relacionales
      • Relaciones simples  aprendizaje proposicional
        • ejemplo: tupla de valores de un nº fijo de atributos (uno es la clase)
        • cjto de ejemplos: tabla
      • Relaciones múltiples  ILP
        • ejemplo: cjto de hechos lógicos
        • cjto de ejemplos: cjto. de tablas
    • Complejidad de los problemas
      • Datos temporales (medicina, análisis tráfico, manejo de redes): representando secuencias de tiempo
      • Datos estructurados (bioquímica, ingeniería de protenias, diseño de drogas): representando moléculas químicas y sus propiedades

1. Introducción: motivación

  • Tabla1: Tabla básica de clientes
  • Tabla2: Tabla de clientes para análisis

1. Introducción: motivación

  • Tabla de clientes representada como hechos Prolog
  • La forma de los hechos Prolog:
  • customer(Id,Zip,Sex,SoSt,In,Age,Club,Re)
  • Representación de los hechos básicos de la Tabla 2:
  • customer(3478,34667,m,si,60-70,32,me,nr).
  • customer(3479,43666,f,ma,80-90,45,nm,re).
  • ¿Cómo expresamos una propiedad?
  • customer(_,_,f._,_,_,_,_).

1. Introducción: motivación

  • Tabla 3: Tabla de clientes con información sobre pedidos y almacenes
  • Tabla 4: Tabla de clientes con información varios pedidos
  • Tabla 5: Tabla de clientes con resumen de atributos

1. Introducción: motivación

  • Representación relacional
  • de clientes, pedidos y
  • almacenes
  • good_customer(C): customer(C,_,f,_,_,_,_,_),
  • order(C,_,_,_,credit).

1. Introdución: terminología

  • Bases de datos
    • nombre de relación p
    • atributo de una relación p
    • tupla - una fila en la tabla relacional
    • relación p - una tabla relacional (un cjto de tuplas)
    • hipótesis: una regla o un árbol de decisión
  • Programación Lógica
    • símbolo de predicado p
    • argumento de un predicao p
    • hecho básico p(a1,…,an)
    • definición de un predicado p - un cjto de hechos básicos
    • hipótesis: un cjto de cláusulas

1. Introducción:Programación Lógica Inductiva

  • ILP
  • =
  • Aprendizaje Inductivo de Conceptos (I)
  • Programación Lógica (LP)
  • Tareas ILP:
  • - Inducción programas lógicos
  •  Síntesis de programas
  • Inducción
  • Lógica
  • Programación

1. Introducción:Programación Lógica Inductiva

  • ILP
  • =
  • Aprendizaje Inductivo de Conceptos (I)
  • Programación Lógica (LP)
  • Tareas ILP:
  • - Inducción programas lógicos
  •  Síntesis de programas
  • - Generalización de observaciones
  • específicas en leyes generales
  •  Data Minig (DM)
  • Knowledge discovery (KDD)
  • Inducción
  • Lógica
  • Programación
  • DM, KDD

1. Introducción:Programación Lógica Inductiva

  • ILP
  • =
  • Aprendizaje Inductivo de Conceptos (I)
  • Programación Lógica (LP)
  • Características:
  • los ejemplos y la teoría de base son cláusulas.
  • La teoría aprendida es un cjto de cláusulas.
  • Ventajas ILP:
  • la lógica de primer orden es un campo
  • matemático ampliamente desarrollado.
  • proporciona una representación uniforme
  • y expresiva.
  • Inducción
  • Lógica
  • Programación

1. Introducción: aprendizaje inductivo de conceptos

  • Inducción predictiva
  • +
  • +
  • +
  • +
  • +
  • -
  • -
  • -
  • -
  • -
  • -
  • -
  • H

1. Introducción: aprendizaje inductivo de conceptos

  • Inducción predictiva
  • +
  • +
  • +
  • +
  • +
  • -
  • -
  • -
  • -
  • H

1. Introducción: aprendizaje inductivo de conceptos

  • Inducción predictiva
  • aprender la definición de
  • un concepto
  • +
  • +
  • +
  • +
  • +
  • -
  • -
  • -
  • -
  • -
  • -
  • -
  • H
  • Inducción descriptiva
  • aprender las relaciones entre
  • conceptos
  • +
  • +
  • +
  • +
  • +
  • +
  • H

1. Introducción: aprendizaje inductivo de conceptos (predictivo)

  • Dado:
  • Encontrar:
    • Una hipótesis H LH tal que (dado B) H cubre todos los ejemplos positivos y negativos
  • En lógica:
    • e E+: BH  e (H es completo)
    • e E-: BH / e (H es consistente)
  • En ILP, E son hechos básicos, B y H cjtos de cláusulas definidas
  • +
  • +
  • +
  • +
  • +
  • +
  • H
  • -
  • -
  • -
  • -
  • -
  • -
  • -

1. Introducción: aprendizaje inductivo de conceptos (predictivo)

  • Dado:
    • Un cjto de observaciones
      • ejemplos positivos E+
      • ejemplos negativos E -
    • conocimiento de base B
    • lenguaje de hipótesis LH
    • relación de cobertura
    • criterio de calidad
  • Encontrar:
    • Una hipótesis H LH tal que (dado B) H es óptima w.r.t. Algún criterio de calidad (p.ej. maximizar la precisión predictiva)
  • +
  • +
  • +
  • +
  • +
  • +
  • H
  • -
  • -
  • -
  • -
  • -
  • -
  • -
  • -
  • -
  • +

1. Introducción: aprendizaje inductivo de conceptos (descriptivo)

  • Dado:
    • Un cjto de observaciones (ejemplos positivos E+)
    • conocimiento de base B
    • lenguaje de hipótesis LH
    • relación de cobertura
  • Encontrar:
    • Una hipótesis (la más específica) H LH tal que (dado B) H cubre todos los ejemplos positivos
  • En lógica, encontrar H tal que c H, c es cierto en algún modelo preferido de B E+ (p. ej. el modelo mínimo de Herbrand)
  • En ILP, E son hechos básicos, B y H cjtos de cláusulas generales
  • +
  • +
  • +
  • +
  • +
  • +
  • H

1. Introducción: ejemplo de programación lógica

  • E+ = {sort([2,1,3],[1,2,3])}
  • E - = {sort([2,1],[1]),sort([3,1,2],[2,1,3])}
  • B contiene las definiciones permutation/2 y sorted/1
  • ILP predictivo
  • sort(X,Y) permutation(X,Y), sorted(Y).
  • ILP descriptivo
  • sorted(Y)  sort(X,Y).
  • permutation(X,Y)  sort(X,Y).
  • sorted(X) sort(X,X).

1. Introducción: ejemplo de descubrimiento de conocimiento

  • E+ = {daughter(mary,ann),daughter(eve,tom)}
  • E - = {daughter(tom,ann),daughter(eve,ann)}
  • B = {mother(ann,mary),mother(ann,tom),father(tom,eve),
  • father(tom,ian),female(ann),female(mary),female(eve),
  • male(pat),male(tom),parent(X,Y)mother(X,Y), parent(X,Y)father(X,Y)}
  • ILP predictivo
  • daughter(X,Y) female(X),parent(Y,X).
  • o un cjto de cláusulas definidas
  • daughter(X,Y) female(X),mother(Y,X).
  • daughter(X,Y) female(X),father(Y,X).
  • ILP descriptivo
  •  daughter(X,Y),mother(X,Y).
  • female(X)  daughter(X,Y).
  • mother(X,Y);father(X,Y) parent(X,Y).

1. Introducción: definición empírica de ILP

  • Dado:
    • Un cjto de ejemplos E de un predicado objeto p
      • Hechos básicos verdaderos E+
      • Hechos básicos falsos E -
    • Un conocimiento de base B que define predicados qip
    • Un lenguaje de hipótesis L, un subcjto. de cláusulas definidas
  • Encontrar:
    • Una hipótesis H que defina el predicado p, expresado en L como un cjto. de cláusulas de la forma
    • p(X1,...,Xn) L1,...,Li,...,Lm
    • tal que
      • H es completo: e E+: BH  e (suficiencia a posteriori)
      • H es consistente: e E-: BH / e (satisfacibilidad a posteriori)
      • e E+: B / e (necesidad a priori)
      • e E-: B / e (satisfacibilidad a priori)

1. Introducción: un problema ILP simple

  • El problema
    • Dados:
      • ejemplos de la relación daughter(X,Y)
      • conocimiento de base –definiciones (extensionales) de las relaciones parent(X,Y) y female(X)
    • Encontrar: la definición de la relación daughter
  • daughter(X,Y) female(X),parent(Y,X).
  • Training examples
  • daughter(mary,ann). 
  • parent(ann,mary).
  • female(ann).
  • daughter(eve,tom). 
  • parent(ann,tom).
  • female(mary).
  • daughter(tom,ann). 
  • parent(tom,eve).
  • female(eve).
  • daughter(eve,ann). 
  • parent(tom,ian).
  • ann
  • mary
  • tom
  • eve
  • ian
  • f
  • f
  • f

1. Introducción: un problema ILP simple

    • Representación ILP estándar
      • ejemplos: hechos básicos de la relación daughter
      • conocimiento de base: hechos básicos que definen las relaciones parent(X,Y) y female(X)
  • Training examples
  • Background Knowledge
  • daughter(mary,ann).
  • parent(ann,mary).
  • female(ann).
  • daughter(eve,tom). 
  • parent(ann,tom).
  • female(mary).
  • daughter(tom,ann). 
  • parent(tom,eve).
  • female(eve).
  • daughter(eve,ann). 
  • parent(tom,ian).

1. Introducción: un problema ILP simple

  • daughter(mary,ann) female(mary),female(ann),
  • parent(ann,mary),parent(ann,tom).
    • Hipótesis inducida:
  • daughter(X,Y) female(X),parent(Y,X).
  • daughter
  • D
  • P
  • mary
  • ann
  • eve
  • tom

1. Introducción: ejemplo Bongard

  • Casificación de ejemplos basada en su estructura
  • pos
  • neg

1. Introducción: ejemplo Bongard (cont.)

  • Representación en lógica de primer orden
  • contains(1, o1).
  • contains(1, o2).
  • triangle(o1).
  • points(o1, down).
  • circle(o2).
  • pos(1).
  • pos(X) :- contains(X,Y), triangle(Y), points(Y, down).
  • el uso de variables proporciona un adecuado nivel de abstracción para la hipótesis
  • permitido cualquier
  • número de objetos
  • Dibujo 1

1. Introducción: un ejemplo del mundo real

  • Identificar subestructuras en las moléculas que hacen que
  • se adhieran a otras moléculas
  • La descripción de las moléculas es la lista de sus átomos, relaciones,…
  • El conocimiento de base define el cómputo de la distancia euclidea, …

1. Introducción: un ejemplo del mundo real

  • active(A) :- zincsite(A,B), hacc(A,C), hacc(A,D), hacc(A,E),
  • dist(A,C,B,4.891,0.750), dist(A,C,D,3.753,0.750), dist(A,
  • C,E,3.114,0.750), dist(A,D,B,8.475,0.750), dist(A,D,E,
  • 2.133,0.750), dist(A,E,B,7.899,0.750).
  • ...
  • hacc(M,A):- atm(M,A,o,2,_,_,_).
  • hacc(M,A):- atm(M,A,o,3,_,_,_).
  • hacc(M,A):- atm(M,A,s,2,_,_,_).
  • hacc(M,A):- atm(M,A,n,ar,_,_,_).
  • zincsite(M,A):-
  • atm(M,A,du,_,_,_,_).
  • hdonor(M,A) :-
  • atm(M,A,h,_,_,_,_),
  • not(carbon_bond(M,A)), !.
  • ...
  • atm(m1,a1,o,2,3.430400,-3.116000,0.048900).
  • atm(m1,a2,c,2,6.033400,-1.776000,0.679500).
  • atm(m1,a3,o,2,7.026500,-2.042500,0.023200).
  • ...
  • bond(m1,a2,a3,2).
  • bond(m1,a5,a6,1).
  • bond(m1,a2,a4,1).
  • bond(m1,a6,a7,du).
  • ...
  • Descripción de las moléculas:
  • Conocimiento de Base:
  • -> Hipótesis:

1. Introducción: un ejemplo del mundo real

  • Algunos ejemplos de moléculas:

1. Introducción: conclusión

  • Para ciertos tipos de aprendizaje...
    • algunas veces llamado aprendizaje estructural: ejemplos que tienen una estructura compleja (no simplemente un vector de valores) o aprendizaje relacional
  • ... es necesario un formalismo de representación para hipótesis y datos más expresivo
  • la lógica de primer orden proporciona esta expresividad
  • -> estudiar la inducción en lógica de primer orden.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal