Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje

CI5438 - Inteligencia Artificial 2Clase 6Cap 18. Russel & Norvig: Inteligencia Artificial. Un enfoque estructurado

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje: MotivacinLa leccin del los Sistemas Expertos:

Adquisicin conocimiento: El proceso de extraer la experticia de un humano para codificarla el un programaProblemas:

Trabajo extremadamente intensivoEl desempeo de un sistema experto es incorrecto si la percepcin no se corresponde con alguna regla codificada.Nuevo conocimiento requiere re-codificacin.

Solucin: Disear sistemas que aprendan de su propia experiencia.

Grupo de Inteligencia Artificial

Universidad Simn BolvarRazonamiento Deductivo e Inductivo

Las conclusiones deductivas estn contenidas en las premisas:

x Hombre(x) Mortal(x) Mortal(Pedro)Luego, Mortal(Pedro)

Las conclusiones Inductivas van ms all de las premisas:

Hombre(Pedro) & Mortal(Pedro)Hombre(Luis) & Mortal(Luis)Hombre(Maria) & Mortal(Maria)Luego, x Hombre(x) Mortal(x) [nuevo conocimiento ha sido aprendido]

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

18.0 Qu es el aprendizaje?

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Qu es el aprendizaje?El aprendizaje denota cambios en un sistema que capacitan al sistema a realizar la misma tarea ms efcientemente la prxima vez. Herbert Simon Aprender es construir o modificar la representacin de lo que ha sido experienciado. Ryszard Michalski Aprender es hacer cambios tiles en nuestras mentes. Marvin Minsky

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Por qu aprender?Entender y mejorar la eficiencia del aprendizaje humano

Para mejorar los mtodos para ensear a la gente (e.j. mejores sistemas de instruccin asistida por computadora)

Descubrir nuevas cosas o estructras que eran desconocidas para los humanos

Ejemplos: data mining

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Por qu aprender?Rellenar el esqueleto o la especificacin incompleta de un dominio

En general, los sistemas de IA complejos con pueden ser derivados completamente a mano, y requieren de una actualizacin dinmica para incorporar nueva informacinAprender nuevas caractersticas expande el dominio o la experticia y disminuye la fragilidad del sistema

Construir agentes de software que puedan adaptarse a sus usuarios o a otros agentes de software

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

18.1 Tipos de Aprendizaje

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje por observacin

El aprendizaje en un agente involucra percibir, razonar y actuar en el ambiente que lo rodeaEl agente interacta con el mundo, y observa sus propios procesos de toma de decisiones

Grupo de Inteligencia Artificial

Universidad Simn BolvarModelo general de los agentes con aprendizaje

All agents described so far have only used their percepts to come up with an actionTrue intelligence requires using percepts to also improve future actions (learning)The agents described so far have been performers, not learnersA general model of learning contains a performance element as just one of several elements (fig. 18.1)

Grupo de Inteligencia Artificial

Universidad Simn BolvarModelo general de los agentes con aprendizaje

Grupo de Inteligencia Artificial

Universidad Simn BolvarModelo general de los agentes con aprendizaje

Los agentes que aprenden estn conformados por 4 componentes:

El elemento de aprendizaje (Learning Element)El elemento de desempeo (Performance Element)El crtico (Critic)El generador de problemas (Problem Generator)

Grupo de Inteligencia Artificial

Universidad Simn BolvarModelo general de los agentes con aprendizaje

Elemento de Desempeo (E.D.): Los agentes que hemos estudiado hasta el momentoElemento de Aprendizaje (E.A.): Toma el conocimiento del E.D y el feedback sobre las acciones del agente para modificar el E.D en el futuroCritico: provee el feedback para el E.A. mediante el monitoreo del resultado de las acciones tomadas por el E.D. (debe estar fuera del E.D.)Generador de problemas: Provee las acciones que conllevarn a experiencias de apredizaje (como experimentos cientficos)

Grupo de Inteligencia Artificial

Universidad Simn BolvarDiseo de un Agente que aprendeCuatro cuestiones principales afectan el

diseo del Elemento de Aprendizaje:Cules componentes del Elemento de Performance van a ser mejorados?Qu representacin se usar para esos componentes?Qu feedback est disponible?Qu informacin previa hay disponible?

Grupo de Inteligencia Artificial

Universidad Simn BolvarComponentes del Elemento de Desempeo

No: Cmo voy a poder aprender esto?Qu clase de Elemento de Desempeo necesitar mi agente para hacer esto, una vez que halla aprendido como

Grupo de Inteligencia Artificial

Universidad Simn Bolvar6 Componentes del Elemento de Desempeo

1. Un mapeo directo de las condiciones del estado actual en acciones

2. Una medida para inferir las propiedades relevantes del mundo a partir de la secuencia de percepciones

3. Informacin sobre como el mundo evoluciona y sobre el resultado de las acciones posibles que el agente puede tomar

Grupo de Inteligencia Artificial

Universidad Simn Bolvar6 Componentes del Elemento de Desempeo

4. Informacin sobre la Utilidad, que indique lo deseable que son los estados del mundo

5. Informacin sobre el Valor de una Accin (Action-value), que indique lo deseable de una accin particular en un estado particular

6. Metas, que describan las clases de estados cuyo alcance maximice la utilidad del agente

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Feedback and Prior KnowledgeIf the Critic provides feedback in the form of the correct action, the learning is supervisedIf the correct action is not given, but the consequences of the chosen action are, this is reinforcement learningIf no information at all about the action is given, then any learning is unsupervisedPrior knowledge may or may not be available, but it is enormously helpful for learning (most M.L. research does not use prior knowledge)

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Feedback Disponible

Aprendizaje Supervisado el agente puede percibir tanto las entradas como las salidas de una componente. Generalmente las salidas son proporcionadas por un tutor amistoso. El problema del aprendizaje supervisado involucra aprender una funcin a partir de ejemplos de sus entradas y salidas

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Feedback Disponible

Aprendizaje No Supervisado el agente no tiene idea de las salidas correctas. Puede aprender a predecir sus percepciones futuras dadas las previas, pero no puede aprender que hacer a menos que ya posea una funcin de utilidad. El problema del aprendizaje no supervisado involucra aprender patrones en las entradas cuando los valores especficos de las salidas no son suministrados

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Feedback DisponibleAprendizaje por Reforzamiento cuando el agente recibe alguna evaluacin de sus acciones (como una multa por chocar un carro), pero no se le indica cul es la accin correcta (frenar antes). El agente en lugar de tener un tutor que le diga que hacer, el agente debe aprenderlo por un reforzamiento

Grupo de Inteligencia Artificial

Universidad Simn BolvarRepresentacin de los Componentes

Descripciones Determinsticas como funciones polinomiales para programas de juegos Logica Proposicional y de primer ordenpara todos los componentes de un agente logicoDescripciones Probabilsticas como redes de creencias, para el componente de inferencias de un agente de decisiones tericas

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Conocimiento PrevioLa mayor parte de la investigacin en ML se centra en agentes que no tienen conocimiento previo de que es lo que trata de aprenderLos agente slo tienen acceso a los ejemplos que les presentan sus experiwenciasHowever, Si el agente tiene conocimiento previo, puede ayudar en el aprendizaje

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

18.2 Aprendizaje Inductivo

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje SupervisadoTodo aprendizaje pretende aprender la representacin de una funcin:

estado estado: Como evoluciona el mundoestado (0,1): si el estado es una metaaccin real: funcin de utilidad, etc.

Aprendizaje InductivoDado: un conjunto de ejemplos (x, f(x))Tarea: encontrar una funcin h que aproxime f. Como varias funciones pueden satisfacer los ejemplos, cualquier preferencia por una es un bias. Todos los algoritmos de aprendizaje exhiben bias

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje InductivoUn ejemplo es un par (x, f(x)) donde x es la entrada y f(x) es la salida de la funcin aplicada a xInferencia inductiva pura (o induccin): dado un conjunto de ejemplos del f, retornar una funcin h que aproxime f. La funcin h se denomina hiptesisUna buena hiptesis generalizar bien. i.e., predecir ejemplos desconocidos correctamente

Grupo de Inteligencia Artificial

Universidad Simn BolvarAprendizaje Inductivo : Ejemplo

En (a) mostramos un ejemplo de pares (entrada, salida). En (b), (c), (d) tenemos tres hiptesis de funciones desde las cuales podran haberse obtenido estos ejemplos

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Aprendizaje Inductivo

Una hiptesis es consistente si concuerda con todos los datosCmo escogemos entre varias hiptesis consistentes?Ockham razor: Prefererir la hiptesis ms simple que sea consistente con los datosLa posibilidad de encontrar una hiptesis simple y consistente depende fuertemente del espcio de hiptesis escogido.

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

18.3 Aprendizaje en rboles de Decisin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

rboles de DecisinUn rbol de decisin es un rbol de bsqueda que retorena una decisin

Entrada: Un objeto o situacin descrito por un conjunto de atributosSalida: Una Decisin.

La entrada puede ser discreta o contnua.La salida tambien puede ser discreta o contnuaAprender una funcin con salida discreta se denomina aprendizaje de clasificacinAprender una funcin con salida contnua se denomina regresin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

rboles de DecisinCada nodo en el rbol corresponde con una prueba de uno de los atributosCada enlace entre los nodos representa uno de los valores que puede tomar el nodo padreCada hoja en el rbol es el valor booleano retornado si la bsqueda lleg a esa hojaLa meta es aprender la definicin del predicado meta, donde esta definicin se expresa como un rbol de decisin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

rboles de DecisinEl proceso de construir un rbol de decisin es como sigue:

Comenzar con el problemaDeterminar cul es el predicado meta para el problemaConstruir una lista de atributos que describen el dominioo del problemaEliminar los atributos irrelevantesConstruir el rbol usando la lista filtrada de atributos

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Ejemplo de rbol de DecisinEl problema es decidir si esperar o no por una mesa en un restaurant Un predicado meta para este ejemplo es Esperar. En otras palabras, si una persona esperar por una mesa para comer en el restaurant

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

The wait estimated by the host.(Values are 0-10 minutes, 10-30, 30-60 and >60)

WaitEstimate

The kind of restaurant.Type

Whether the person made a reservation.Reservation

Whether it is raining outside.Raining

The restaurants price range.(Values are $, $$, $$$)

Price

How many people are in the restaurant? (Values are None, Some, and Full)

Patrons

Whether the person is hungry.Hungry

True on Fridays and Saturdays.Fri/Sat

Whether the restaurant has a comfortable bar area to wait in.Bar

Whether there is a suitable alternative restaurant nearby.Alternate

DescriptionAttribute

Ejemplo de rbol de Decisin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Ejemplo de rbol de Decisin

Grupo de Inteligencia Artificial

Universidad Simn BolvarExpresividad de los rboles de decisin

Cualquier rbol de decisin particular para un predicado meta PM es una expresin de la forma:

s PM(s) (P1(s) P2(s) Pn(s)) Donde Pi(s) es la conjuncin de pruebas de

un camino entre la raz y una hoja con salida positivaProposicional: solo 1 variable y predicados unarios

Grupo de Inteligencia Artificial

Universidad Simn BolvarExpresividad de los rboles de decisin

Pregunta: Si los rboles de decisin se corresponden con un conjunto de conjunto de implicaciones, pueden representar cualquier conjunto?Respuesta: No!

Los rboles de decisin estn implcitamente limitados a hablar de solo un objeto o situacinEl lenguaje de los rboles de decisin es esencialmente proposicional, donde cada uno de los atributos que se prueban es un objeto simple

Los rboles de decisin son completamente expresivos en el lenguaje de la lgica proposicionalEn otras palabras, cualquier funcin booleana puede ser representada con un rbol de decisin

Grupo de Inteligencia Artificial

Universidad Simn BolvarInduciendo rboles de decisin a partir de ejemplos

Meta: Encontrar el rbol ms pequeo que sea consistente con los ejemplos de entrenamientoUn ejemplo consiste en un vector de atributos de entrada X, y un valor booleano de salida y

Grupo de Inteligencia Artificial

Universidad Simn BolvarInduciendo rboles de decisin a partir de ejemplos

Ejemplo Un ejemplo consiste en un vector de atributos de entrada X, y un valor booleano de salida yClasificacin Valor del predicado metaEjemplo Positivo El predicado meta es TrueEjemplo Negativo El predicado meta es FalseConjunto de Entrenamiento Un conjunto completo de ejemplos positivos y negativos

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Conjunto de EntrenamientoEjemplos descritos como valores de atributos (booleanos, discretos, contnuos, etc.)

ExampleAttributes Goal

Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait

X1 Yes No No Yes Some $$$ No Yes French 010 YesX2 Yes No No Yes Full $ No No Thai 3060 NoX3 No Yes No No Some $ No No Burger 010 YesX4 Yes No Yes Yes Full $ No No Thai 1030 YesX5 Yes No Yes No Full $$$ No Yes French >60 NoX6 No Yes No Yes Some $$ Yes Yes Italian 010 YesX7 No Yes No No None $ Yes No Burger 010 NoX8 No No No Yes Some $$ Yes Yes Thai 010 YesX9 No Yes Yes No Full $ Yes No Burger >60 NoX10 Yes Yes Yes Yes Full $$$ No Yes Italian 1030 NoX11 No No No No None $ No No Thai 010 NoX12 Yes Yes Yes Yes Full $ No No Burger 3060 Yes

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Ockhams razor

The most likely hypothesis is the simplest one that is consistent with all observationsThe razor states that the most likely hypothesis is the simplest one that is consistent with all observations.

Grupo de Inteligencia Artificial

Universidad Simn BolvarAlgorirtmo de Aprendizaje de un rbol de decisin

El algoritmo DECISION-TREE-LEARNING cumple con el objetivo de construir un rbol pequeo y consistente con el conjunto de entrenamientoLa ideal central del algoritmo es probar primero el atributo ms importanteEl trmino ms importante significa que sea el atributo que haga una mayor diferencia en la clasificacin de los ejemplosEl resultado de esta heurstica es que el rbol de decisin es ms pequeo

Grupo de Inteligencia Artificial

Universidad Simn BolvarAlgorirtmo de Aprendizaje de un rbol de decisin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Escogiendo un atributoIdea: Un buen atributo separa los ejemplos en subconjuntos que son (idealmente) todos positivoso todos negativos

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

InformacinLa informacin responde a la preguntaMientras menos idea tengo sobre la respuesta inicialmente, hay ms informacin contenida en la respuestaEscala: 1 bit = respuesta a una pregunta booleana con previo La informacin en una respuesta cuando el previo es es I() = -PiLog(Pi)

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Informacin (cont.)Supongamos que tenemos p ejemplos positivos y n negativos en la raz

Se necesitan I() bits para clasificar un nuevo ejemploEn el ejemplo del restaurant p=n=6, luego necesitamos 1 bit

Un atributo separa los ejemplos E en subconjuntos Ei, capa uno de los cuales (esperamos) necesite menos informacin para completar la clasificacin

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Informacin (cont.)Sea Ei con pi ejemplos positivos y ni negativos

Se necesitan I(< pi /(pi + ni),n/(pi + ni)>) bits para clasificar un nuevo ejemploEl nmero esperado de bits sobre todas las ramificaciones es (pi + ni)/(p + n) (I(< pi /(pi + ni),n/(pi + ni)>))

Para patrons? Es 0.459 bits y para type es 1Escoger el atributo que minimize el la informacin que ser requirida

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Ejemplo (cont)rbol de Decisin inducido por los ejemplos

Grupo de Inteligencia Artificial

Universidad Simn BolvarDesempeo del Algoritmo de Aprendizaje

Un algoritmo de aprendizaje es bueno si produce hiptesis que predicen adecuadamente la clasificacin de ejemplos desconocidos.Una metodologa para verificar la calidad de la prediccin:

1. Coleccionar un gran conjunto de ejemplos2. Separarlo en dos conjuntos disjuntos: el conjunto de

entrenamiento y el conjunto de prueba3. Usar en algoritmo en es conjunto de entrenamiento para

generar la hiptesis h4. Medir el porcentaje de los ejemplos del conjunto de

pruebas que son clasificados correctamente por h5. Repetir los pasos 1 al 4 variando el tamao del conjunto

de entrenamiento y seleccionando aleatoriamentel los elementos para cada tamao

Grupo de Inteligencia Artificial

Universidad Simn Bolvar

Medida de DesempeoCmo sabemos si hf?

Usar los teoremas de la teora de aprendizaje estadsticoProbar h es un nuevo conjunto de ejemplos de prueba

Curva de aprendizaje = % de aciertos en el conjunto de prueba como funcin del tamao del conjunto de entrenamiento

0.4

0.5

0.6

0.7

0.8

0.9

1

0 20 40 60 80 100

% co

rrect

on te

st se

t

Training set size