PDF de programación - Aprendizaje Automático

Aprendizaje Automático

c b e a

LSI - FIB

IA - Curso 2014/2015

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

1 / 46

Índice

1

Introducción

2 Aprendizaje inductivo

3 Árboles de decisión

4 Aprendizaje Bayesiano

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

2 / 46

Introducción

1

Introducción

2 Aprendizaje inductivo

3 Árboles de decisión

4 Aprendizaje Bayesiano

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

3 / 46

Aprendizaje Automático

Introducción

Las técnicas que hemos visto hasta ahora nos permiten crear sistemas
que resuelven tareas que necesitan inteligencia
La limitación de estos sistemas reside en que sólo resuelven los
problemas ya previstos
Sólo podemos considerar que un sistema es realmente inteligente si es
capaz de observar su entorno y aprender de él
La autentica inteligencia reside en adaptarse, tener capacidad de
integrar nuevo conocimiento, resolver nuevos problemas, aprender de
errores

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

4 / 46

Objetivos

Introducción

No se pretende modelar el aprendizaje humano
Busca aumentar las capacidades de los programas de IA (SBC,
planificación, TLN, búsqueda, ...):

Su límite está en el conocimiento que se les ha introducido
No resuelven problemas mas allá de esos límites

Es imposible prever todos los problemas desde el principio
Buscamos dar a programas la capacidad de adaptarse sin tener que
ser reprogramados

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

5 / 46

¿Funciona?

Introducción

Does Machine Learning Really Work? Tom Mitchell. AI Magazine 1997

¿Donde y para que se puede usar el aprendizaje automático?

Tareas difíciles de programar (adquisición de conocimiento,
reconocimiento de caras, voz, ...)
Aplicaciones auto adaptables (interfaces inteligentes, spam filters,
sistemas recomendadores, ...)
Minería de datos/Descubrimiento de conocimiento (análisis de datos
inteligente)

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

6 / 46

Tipos de aprendizaje

Introducción

Aprendizaje inductivo: Creamos modelos de conceptos a partir de
generalizar ejemplos simples. Buscamos patrones comunes que
expliquen los ejemplos.
Aprendizaje analítico o deductivo: Aplicamos la deducción para
obtener descripciones generales a partir de un ejemplo de concepto y
su explicación.
Aprendizaje genético: Aplica algoritmos inspirados en la teoría de la
evolución para encontrar descripciones generales a conjuntos de
ejemplos.
Aprendizaje conexionista: Busca descripciones generales mediante
el uso de la capacidad de adaptación de redes de neuronas artificiales

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

7 / 46

Aprendizaje inductivo

1

Introducción

2 Aprendizaje inductivo

3 Árboles de decisión

4 Aprendizaje Bayesiano

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

8 / 46

Aprendizaje inductivo

Aprendizaje Inductivo

Los métodos más utilizados en aplicaciones provienen del aprendizaje
inductivo supervisado
Inducción: Pasamos de lo específico a lo general
Supervisión: Conocemos el concepto al que pertenece cada ejemplo
A partir de un conjunto de ejemplos etiquetados obtenemos un
modelo
El modelo generaliza los ejemplos, representando los conceptos que
definen las etiquetas
Obtenemos lo que es común entre los ejemplos de un concepto que
les diferencia de los otros

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

9 / 46

Aprendizaje inductivo

Aprendizaje Inductivo

Desde el punto de vista formal lo que se obtiene mediante aprendizaje
inductivo no es válido
Asumimos que un número limitado de ejemplos representa las
características del concepto que queremos aprender
Solo hace falta un contraejemplo para invalidar el resultado
Pero, !una gran parte del aprendizaje humano es inductivo!

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

10 / 46

Aprendizaje inductivo

Aprendizaje Inductivo en recomendación

Tipos de métodos de aprendizaje inductivo supervisado
Modelos caja blanca (podemos inspeccionar el modelo)

Árboles de decisión/reglas de inducción
Modelos probabilísticos

Modelos caja negra

Redes de neuronas artificiales
Máquinas de soporte vectorial

Podemos plantear el problema como:

Clasificación: un conjunto finito de conceptos
Regresión: una función continua

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

11 / 46

Árboles de decisión

1

Introducción

2 Aprendizaje inductivo

3 Árboles de decisión

4 Aprendizaje Bayesiano

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

12 / 46

Árboles de decisión

Árboles de decisión

Podemos aprender un concepto
como la aplicación de un algoritmo
que busca el conjunto de preguntas
que lo distingue de otros
El árbol de preguntas nos sirve de
lenguaje de representación, cada
nodo es un test sobre un atributo
Esta representacion es equivalente
a una FND (22n conceptos)
Para aprender hemos de realizar
una búsqueda en el espacio de
árboles de preguntas

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

13 / 46

Plant,�animal�or�mineral?AnimalPlantMineralBig�or�small?BigSmallAcuatic�or�terrestrial?� Árboles de decisión

Árboles de decisión

Buscar en el espacio de todas las FND es demasiado costoso
Para reducir el coste computacional imponemos un sesgo (las
descripciones que se prefieren)
Restricción: Queremos el árbol que represente la mínima descripción
del concepto objetivo dados los ejemplos
Justificacion: Este árbol será el mejor clasificando nuevos ejemplos
(la probabilidad de tener preguntas innecesarias se reduce)
Navaja de Occam: “En igualdad de condiciones, la explicación más
sencilla suele ser la correcta”

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

14 / 46

Árboles de decisión

Algoritmos de árboles de decisión

Existen muchos algoritmos para aprender árboles de decisión
El más simple es el denominado ID3
Este algoritmo realiza una búsqueda por ascenso en el espacio de
árboles

Para cada nuevo nodo de decisión un atributo es elegido y los ejemplos
son distribuidos según sus valores
Este procedimiento es repetido recursivamente hasta que todos los
ejemplos son del mismo concepto

La selección de cada atributo es decidida mediante una función
heurística que tiene preferencia a formar árboles mínimos

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

15 / 46

Árboles de decisión

Algoritmos de árboles de decisión

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

16 / 46

1a1b2b2a3a3b4a4b Árboles de decisión

Heurísticas para árboles de decisión

Una heurística es un método aproximado para la solución de un
problema
Las heurísticas para árboles de decisión miden lo adecuado que es un
atributo para formar un árbol mínimo
Esta decisión se realiza de manera local (en cada nodo del árbol)
aproximando el problema global
Heurísticas utilizadas:

Entropía, entropía normalizada
GINI index
Rough sets
...

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

17 / 46

Árboles de decisión

Teoría de la Información

La teoría de la información estudia entre otras cosas los mecanismos
de codificación de mensajes y el coste de su transmisión
Si definimos un conjunto de mensajes M = {m1, m2, ..., mn}, cada
uno de ellos con una probabilidad P(mi), podemos definir la cantidad
de información (I) contenida en un mensaje de M como:

nX

i=1

I(M) =

−P(mi)log(P(mi))

Este valor se puede interpretar como la información necesaria para
distinguir entre los mensajes de M (Cuantos bits de información son
necesarios para codificarlos)

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

18 / 46

Árboles de decisión

Cantidad de Información como Heurística

Podemos hacer la analogía con la codificación de mensajes
suponiendo que las clases son los mensajes y la proporción de
ejemplos de cada clase su probabilidad
Podemos ver un árbol de decisión como la codificación que permite
distinguir entre las diferentes clases
(Aprender un árbol de decisión ⇐⇒ Aprender un código)
Buscamos el mínimo código que distingue entre las clases
Cada atributo se deberá evaluar para decidir si se le incluye en el
código

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

19 / 46

Árboles de decisión

Cantidad de Información como Heurística

En cada nivel del árbol debemos evaluar qué atributo permite
minimizar el código
Este atributo será el que haga que la cantidad de información que
quede por cubrir sea la menor (bits restantes por codificar)
La elección de un atributo debería resultar en una partición donde los
ejemplos en cada una de ellas estén sesgados hacia una clase
Necesitamos una medida de la cantidad de información que no cubre
un atributo (Entropia, E)

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

20 / 46

Árboles de decisión

Cantidad de información

Dado un conjunto de ejemplos X y siendo C su clasificación

]X log( ]ci
− ]ci
]X )

I(X ,C) = X

∀ci∈C

Bits necesarios para codificar los ejemplos sin ninguna información
adicional

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

21 / 46

Árboles de decisión

Entropia

Dado un atributo A y siendo [A(x) = vi] los ejemplos con valor vi en
el atributo

][A(x) = vi]

]X

I([A(x) = vi],C)

E(X , A,C) = X

∀vi∈A

Bits necesarios para codificar los ejemplos dado un atributo
(Simplemente la suma ponderada de la cantidad de información de
cada partición)

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

22 / 46

Árboles de decisión

Ganancia de información

Bits que aún han de ser codificados

G(X , A,C) = I(X ,C) − E(X , A,C)

c b e a (LSI - FIB)

Aprendizaje Automático

IA - Curso 2014/2015

23 / 46

C1C2C3C1C2C3C1C2C3C1C2C3A=v3A=v1A=v2I(X,C)E(X,A,C)G(X,A,C)= I(X,C) − E(X,A,C) Árboles de decisión

ID3 algoritmo
Algoritmo: ID3 (X : Ejemplos, C: Clasificación, A: Atributos)
si todos los ejemplos son