Personalización y Aprendizaje

Aprendizaje en Servicios y Agentes

ECSDI

Curso 2019/2020

CS-FIB-UPC cbea

Adaptacion y perfilado

Adaptación al entorno

• Dos características interesantes de los agentes son laadaptación y la proactividad• Adaptación es la capacidad de cambiar su comportamiento

según sus experiencias y las percepciones del entorno

• Proactividad es la capacidad de adelantarse a las necesidades apartir de las consecuencias de su modelo del mundo

ECSDI - Curso 2019/2020 - FIB 1/79

Adaptación al entorno

• Estas dos capacidades pasan por que el agente genere unmodelo de su entorno

• Este modelo se basará en la integración de sus experiencias enuna representación

• En inteligencia artificial estos modelos se construyen mediantetécnicas de aprendizaje automático

ECSDI - Curso 2019/2020 - FIB 2/79

Aprendizaje en agentes

• Existen múltiples escenarios en los que se puede aplicaraprendizaje automático en agentes:• Perfilado de usuarios, recomendación: Aprender las

características y necesidades de un usuario asociadas a unatarea/dominio

• Automatización de tareas: Aprender los pasos para realizaruna tarea a través de la interacción con un usuario o el entorno

• Se pueden aplicar diferentes técnicas de aprendizaje

ECSDI - Curso 2019/2020 - FIB 3/79

Recomendación/Perfilado

Perfilado y Recomendación

• Un ámbito interesante del uso de aprendizaje enagentes/servicios es el perfilado de usuarios y la recomendación

• Se aprenden las preferencias del usuario para poder personalizarel funcionamiento del agente/servicio

• Las aplicaciones más comunes son en agentes que sirven para elacceso a algún tipo de contenido (productos, información)

• Puede realizarse a partir de la información que se obtiene demanera individual por usuario o de manera colectiva

ECSDI - Curso 2019/2020 - FIB 4/79

Tipos de perfiles

• Perfil individual estático: Se recolecta una vez la informaciónde un usuario y se utiliza como modelo para sus preferencias

• Perfil individual dinámico: Se observa o se obtiene feedbackdel usuario y se adapta el perfil inicial a las observaciones

• Perfil colaborativo: Se organizan a los usuarios en perfiles deacuerdo con sus características y se utiliza el modelo obtenidodel colectivo para determinar sus preferencias

ECSDI - Curso 2019/2020 - FIB 5/79

Perfil individual dinámico - Ejemplo

• Filtrado del correo no deseado

• El contenido son los mensajes de correo que recibe un usuario

• El comportamiento observable es el marcado como correo nodeseado de mensajes

• El perfil individual son las características que diferencian loscorreos no deseados para el usuario

• El perfil se aplica para etiquetar nuevos correos

ECSDI - Curso 2019/2020 - FIB 6/79

Perfil colaborativo - Ejemplo

• Recomendación de productos en una tienda

• El contenido son los productos de la tienda

• El comportamiento observable es el historial de compra ynavegación de los usuarios

• El perfil colectivo se puede obtener explícita (eg: partición deusuarios) o implicítamente (eg: usuarios con compras similares)

• El perfil se aplica para recomendar al usuario comprasrealizadas por usuarios con un comportamiento similar

ECSDI - Curso 2019/2020 - FIB 7/79

Representación de Perfiles

• Las características en un perfil dependen del dominio deaplicación

• Pueden incluir:• Información propia del usuario (eg: info. demográfica)

• Información que representa el contenido que se va arecomendar (eg: descripción de productos, texto, ...)

• La representación depende de la estructura del contenido• No estructurada (vector de atributos)

• Estructurada (grafos de relaciones, secuencias, ...)

ECSDI - Curso 2019/2020 - FIB 8/79

Tipos de sistemas de recomendación

• Recomendación basada en contenido• Se elabora un perfil explícito (modelo) de los usuarios a partir

de sus características y las del contenido

• Los nuevos elementos se recomiendan o no dependiendo de larespuesta del modelo

• Filtrado colaborativo• No se elabora un perfil explícito del usuario

• Se determina la adecuación de nuevo contenido a partir de lasimilaridad del usuario con otros usuarios o contenidos y susevaluaciones de estos

ECSDI - Curso 2019/2020 - FIB 9/79

Recomendación basada en contenido

• Basada en el análisis de las descripciones de contenido valoradopor el usuario

• El perfil sera una representación de las preferencias del usuarioa partir de esas descripciones

• Este perfil permite obtener la predicción de la valoración delusuario para nuevo contenido

• Esta valoración permite tomar la decisión sobre surecomendación

ECSDI - Curso 2019/2020 - FIB 10/79

Recomendación basada en contenido

Contenido

ExtracciónCaracterísticas

Items

Perfiles

Aprendizaje Perfil

Valoracionesusuario

Nuevositems

Filtrado

Recomendaciones

FeedbackUsuario

Nuevasvaloraciones

ECSDI - Curso 2019/2020 - FIB 11/79

Recomendación basada en contenido - Pros y Cons

• Ventajas:• Las recomendaciones de un usuario son independientes del resto

• Se puede obtener una explicación de la recomendación a partirdel perfil

• Se pueden recomendar contenidos nuevos que no han sidovalorados por nadie

ECSDI - Curso 2019/2020 - FIB 12/79

Recomendación basada en contenido - Pros y Cons

• Inconvenientes:• La calidad del perfil depende de las características usadas

• Sobreespecialización en las recomendaciones, no podemosrecomendar contenidos muy diferentes de los que ya conocemos

• Hacen falta un numero inicial de valoraciones por parte delusuario para poder recomendar eficazmente (cold start)

ECSDI - Curso 2019/2020 - FIB 13/79

Extracción de características

• El contenido puede tener una representación explícita(estructurada)• Una ontología define la descripción del contenido

• eg: Productos en una tienda (libros, discos, ...)

• El contenido puede tener una representación no estructurada• Se han de utilizar técnicas especializadas de extracción de

características

• ej.: Texto de noticias → técnicas de recuperación de lainformación (Information Retrieval)

ECSDI - Curso 2019/2020 - FIB 14/79

Feedback del usuario

• El feedback puede ser explícito:

• A partir de una valoración cualitativa (eg: gusta, no gusta)

• A partir de una valoración cuantitativa (eg: una puntuación)

• A partir de una valoración no estructurada (eg: el texto de unaopinión)

• El feedback puede ser implícito:

• Acciones del usuario que podemos transformar en unavaloración (eg: tiempo de lectura de una noticia)

ECSDI - Curso 2019/2020 - FIB 15/79

Aprendizaje y recomendación

Métodos de aprendizaje

• Los métodos más utilizados para la recomendación basada encontenidos provienen del aprendizaje inductivo supervisado

• Inducción: Pasamos de lo específico a lo general

• Supervisión: Conocemos el concepto al que pertenece cadaejemplo

ECSDI - Curso 2019/2020 - FIB 16/79

Métodos de aprendizaje

• A partir de ejemplos etiquetados obtenemos un modelo

• El modelo generaliza los ejemplos, representando los conceptosque definen las etiquetas

• Obtenemos lo que es común entre los ejemplos de un conceptoque les diferencia de los otros conceptos

ECSDI - Curso 2019/2020 - FIB 17/79

Aprendizaje Inductivo en recomendación

• Métodos usados en recomendación basada en contenido• 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 definir el problema como:• Clasificación: predecir un conjunto finito de conceptos

• Regresión: predecir una función continua

ECSDI - Curso 2019/2020 - FIB 18/79

Árboles de decisión

Árboles de decisión

• Aprender un concepto como la búsqueda del conjunto depreguntas que lo distingue de otros

• Estas preguntas se pueden organizar de manera jerárquica(árbol)

• El árbol de preguntas nos sirve de lenguaje de representación,cada nodo es un test sobre un atributo

• Representacion es equivalente a una FND (22n conceptosposibles)

• Búsqueda en el espacio de árboles de preguntas

ECSDI - Curso 2019/2020 - FIB 19/79

Árboles de decisión

Plant,�animal�or�mineral?

AnimalPlant

Mineral

Big�or�small?

Big Small

Acuatic�or�terrestrial?�

Árboles de decisión

• Buscar en el espacio de todas las FND es muy costoso

• Para reducir el coste computacional imponemos un sesgo

• Restricción: Queremos el árbol que represente la mínimadescripción del concepto objetivo dados los ejemplos

• Justificacion: Este árbol será el mejor clasificando nuevosejemplos (la probabilidad de tener preguntas innecesarias sereduce)

• Navaja de Occam: “En igualdad de condiciones, laexplicación más sencilla suele ser la correcta”

ECSDI - Curso 2019/2020 - FIB 21/79

Algoritmos de árboles de decisión - Algoritmo ID3

• El algoritmo ID3 realiza una búsqueda por ascenso en elespacio de árboles• Para cada nuevo nodo de decisión se elige un atributo y los

ejemplos son distribuidos según sus valores

• Este procedimiento es repetido recursivamente hasta que todoslos ejemplos son del mismo concepto

• La selección de cada atributo es decidida mediante una funciónheurística

ECSDI - Curso 2019/2020 - FIB 22/79

Algoritmos de árboles de decisión

1a 1b

2b2a

3a3b

4a4b

Heurísticas para árboles de decisión

• Una heurística es un método aproximado para la solución de unproblema

• Las heurísticas para árboles de decisión miden lo adecuado quees 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

• ...

ECSDI - Curso 2019/2020 - FIB 24/79

Teoría de la Información

• La teoría de la información estudia los mecanismos decodificación de mensajes y el coste de su transmisión

• Dados un conjunto de mensajes M = {m1,m2, ...,mn}, conuna probabilidad P (mi), podemos definir la cantidad deinformación (I) contenida en un mensaje de M como:

I(M) =n∑i=1

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

• Este valor se interpreta como la información necesaria paradistinguir entre los mensajes de M (Cuantos bits deinformación son necesarios para codificarlos)

ECSDI - Curso 2019/2020 - FIB 25/79

Cantidad de Información como Heurística

• Podemos hacer la analogía con codificación de mensajes:• las clases son los mensajes

• la proporción de ejemplos de cada clase su probabilidad

• Árbol de decisión = codificación que distingue las 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 evalúa para decidir si se le incluye

ECSDI - Curso 2019/2020 - FIB 26/79

Cantidad de Información como Heurística

• La elección se realiza en cada punto de decisión

• Elegir un atributo si hace que la cantidad de información quequede por cubrir sea la menor (bits restantes por codificar)

• La elección resulta en una decisión donde los ejemplos paracada posibilidad están sesgados hacia una clase

• Una heurística calcula la cantidad de información que no cubreun atributo (Entropia, E)

ECSDI - Curso 2019/2020 - FIB 27/79

Cantidad de información/Entropia

• Bits necesarios para codificar los ejemplos X y siendo C suclasificación, sin ninguna información adicional

I(X , C) =∑∀ci∈C

− ]ci]X

log(]ci]X

)

• Bits necesarios para codificar los ejemplos dado un atributo A ysiendo [A(x) = vi] los ejemplos con valor vi

E(X , A, C) =∑∀vi∈A

][A(x) = vi]

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

(Suma ponderada de la cantidad de I para cada partición)

ECSDI - Curso 2019/2020 - FIB 28/79

Ganancia de información

• Bits que aún han de ser codificados

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

C1 C2

C3 C1C1C1 C2C2C2

C3

C3C3

A=v1A=v2

A=v3

ECSDI - Curso 2019/2020 - FIB 29/79

ID3 algoritmo

Algorithm: ID3 (X : Ejemplos, C: Clasificación, A: Atributos)if todos los ejemplos son de la misma clasethen

return una hoja con el nombre de la claseelse

Calcular la cantidad de información de los ejemplos (I)foreach atribute en A do

Calcular la entropia (E) y la ganancia de información (G)

Escoger el atributo que maximiza G (a)Borrar a de la lista de atributos (A)Generar el nodo raíz para el atributo aforeach partición generada por los valores del atributo a do

Árboli=ID3(X [a] = vi, C ,A− a)generar una nueva rama con a=vi y Árboli

return El nodo raíz para a

ID3 - Ejemplo (1)

Tomemos el siguiente conjunto de ejemplos de películas

Ej. Década País Género Gusta1 70 USA Drama +

2 70 no USA Comedia +

3 80 no USA Drama −4 90 no USA Drama −5 90 no USA Comedia +

6 80 no USA Acción −7 90 USA Acción −8 70 no USA Drama +

ECSDI - Curso 2019/2020 - FIB 31/79

ID3 - Ejemplo (2)

Década N ejemplos Gusta no Gusta70 3/8 3/3 0/380 2/8 0/2 2/290 3/8 1/3 2/3 G(X,década)= 1 - 0.34= 0.65

País N ejemplos Gusta no GustaUSA 2/8 1/2 1/2

no USA 6/8 3/6 3/6 G(X,país)= 1 - 1 = 0

Género N ejemplos Gusta no Gustacomedia 2/8 2/2 0/2drama 4/8 2/4 2/4acción 2/8 0/2 2/2 G(X,genero)= 1 - 0.5 = 0.5

ECSDI - Curso 2019/2020 - FIB 32/79

ID3 - Ejemplo (3)

Este atributo nos genera una partición que forma el primer nivel delárbol.

DECADA

8090

70

1,2,8

+

3,6

-

4,7

-

5

+

ECSDI - Curso 2019/2020 - FIB 33/79

ID3 - Ejemplo (4)

Ahora solo en el nodo correspondiente al valor 90s tenemosmezclados objetos de las dos clases, por lo que repetimos el procesocon esos objetos.

Ej. País Género Gusta4 no USA drama −5 no USA comedia +

7 USA acción −

Ahora el atributo que maximiza la función es género.

G(X, pais) = 0,918− 0,666 = 0,252

G(X, genero) = 0,918− 0 = 0,918∗

ECSDI - Curso 2019/2020 - FIB 34/79

ID3 - Ejemplo (5)

El árbol resultante es ya totalmente discriminante y podemos usarlocomo descripción del perfil

4

-

7

-

5

+

DECADA

80 9070

1,2,8

+

3,6

-

GENERO

COMEDIA DRAMA ACCION

ECSDI - Curso 2019/2020 - FIB 35/79

Aprendizaje bayesiano

Aprendizaje bayesiano

• Los modelos basados en árboles de decisión o reglas asumenuna división perfecta entre conceptos

• Para algunos problemas es más interesante tener decisionesdifusas (soft)

• Esto se puede modelar usando distribuciones de probabilidadpara representar los conceptos

• Asume que con una muestra de datos problema podemosobtener un modelo para evaluar nuestras hipótesis (laclasificación de nuestros datos) estimando probabilidades

ECSDI - Curso 2019/2020 - FIB 36/79

Inferencia Bayesiana

• El mecanismo de razonamiento del aprendizaje bayesiano es elteorema de Bayes

• Este teorema liga hipótesis con observaciones

P (h|E) = P (h) · P (E|h)P (E)

• Obtiene de un modelo probabilístico de un problema unaestimación de la probabilidad de una decisión

ECSDI - Curso 2019/2020 - FIB 37/79

Inferencia Bayesiana - Ejemplo

• Supongamos que queremos recomendar una novela a un amigo

• Podemos basar esta decisión en:

• Nuestra opinión sobre la novela (evidencia)

• Probabilidad a priori de los gustos de nuestro amigo

• Como se parecen nuestros gustos a los de nuestro amigomodelado como la probabilidad conjunta de los gustos deambos (asumimos que correlación es causalidad)

ECSDI - Curso 2019/2020 - FIB 38/79

Inferencia Bayesiana - Ejemplo

• Sabemos que la probabilidad de que a nuestro amigo le gusteuna novela es del 60% (p(h), probabilidad a priori)

• Sabemos que nuestro amigo tiene un gusto similar al nuestro(P (E|h), probabilidad condicionada)

• Suponemos que parámetros estimados del P (E|h) son:• Probabilidad de tener nosotros una opinión positiva si nuestro

amigo tiene una opinión positiva es del 90%

• La probabilidad de tener nosotros una opinión negativa sinuestro amigo tiene una opinión negativa es del 95%

ECSDI - Curso 2019/2020 - FIB 39/79

Inferencia Bayesiana - Ejemplo

• A nosotros nos ha gustado la novela ¿deberíamosrecomendársela a nuestro amigo? (¿cual sería su predicción?)(P (h|E))

Si enumeramos todas las probabilidades relevantes:

• P(Amigo) = 〈0,60; 0,40〉 (pos/neg)

• P(Nuestra | Amigo=pos) = 〈0,9; 0,1〉 (pos/neg)

• P(Nuestra | Amigo=neg) = 〈0,05; 0,95〉 (pos/neg)

ECSDI - Curso 2019/2020 - FIB 40/79

Inferencia Bayesiana - Ejemplo

El teorema de bayes nos dice:

P (Amigo|Nuestra) = P (Amigo) · P (Nuestra|Amigo)P (Nuestra)

Dado que nuestra opinión es positiva (los datos) y dado que elresultado ha de sumar 1 para ser una probabilidad:

P (Amigo|Nuestra = pos) = 〈P (A = pos) · P (N = pos|A = pos),

P (A = neg) · P (N = pos|A = neg)〉= 〈0,6× 0,9; 0,4× 0,05〉= 〈0,94; 0,06〉 (normalizada)

Es muy probable que a nuestro amigo le vaya a gustar la novelaECSDI - Curso 2019/2020 - FIB 41/79

Aprendizaje Bayesiano

• El objetivo de aprendizaje es estimar la función de densidad deprobabilidad (FDP) de los datos

• Estimar una FDP necesita ciertas suposiciones sobre:

• El modelo de distribución que describe los atributos (continuos,discretos)

• El modelo de distribución que describe las hipótesis

• La dependencia entre las variables (todas independientes,algunas independientes, ...)

ECSDI - Curso 2019/2020 - FIB 42/79

Aprendizaje Bayesiano - Naive Bayes

• La aproximación más simple es asumir que todos los atributosson independientes (no es cierto en general)

• La FDP de los atributos se puede expresar como:

P (E|h) =∏∀i∈attr

P (Ei|h)

• La estimación del modelo para cada atributo se puede hacer porseparado P (Ei|h) a partir de los datos

• La probabilidad de un conjunto de hipótesis se expresa:

P (h|E) = argmaxh∈H

[P (h)×

∏∀i∈attr

P (Ei|h)

]ECSDI - Curso 2019/2020 - FIB 43/79

Naive Bayes - Algoritmo

Algorithm: Naive Bayes

Entrada: E ejemplos, A atributos, H hipótesis/clasesSalida : P (H),P (EA|H)foreach h ∈ H do

P (h)← Estimar la probabilidad a priori de la clase (E ,h)foreach a ∈ A do

P (Ea|h)← Estimar la FDP del atributo de la clase (E , h, a)

• Predecir nuevos ejemplos implica calcular la probabilidad de lashipótesis (aplicar el teorema de Bayes)

ECSDI - Curso 2019/2020 - FIB 44/79

Aprendizaje Bayesiano - Estimación en Naive Bayes

• Atributos discretos: P (Ei|h) se estima a partir de la frecuenciade los valores del atributo en los de datos para cada clase(distribución multinomial)

• Atributos continuos: P (Ei|h) se estima asumiendo unadistribución modelo continua (eg. gausiana) y estimando susparámetros con los datos

ECSDI - Curso 2019/2020 - FIB 45/79

Aprendizaje Bayesiano - Estimación en Naive Bayes

Ej. Década País Género Gusta1 70 USA Drama +

2 70 no USA Comedia +

3 80 no USA Drama −4 90 no USA Drama −5 90 no USA Comedia +

6 80 no USA Acción −7 90 USA Acción −8 70 no USA Drama +

ECSDI - Curso 2019/2020 - FIB 46/79

Aprendizaje Bayesiano - Estimación en Naive Bayes - Ejemplo

Década País Género P (H)70 80 90 USA noUSA Comedia Drama Acción Gusta1 0 .33 .5 .5 1 .5 0 + (.5)0 1 .66 .5 .5 0 .5 1 - (.5)

Ej: (90, USA, Drama)

argmaxh∈{+,−}

〈0,5× 0,33× 0,5× 0,5; 0,5× 0,66× 0,5× 0,5〉 =

argmaxh∈{+,−}

〈0,33; 0,66〉 = 0,66⇒ −

ECSDI - Curso 2019/2020 - FIB 47/79

Aplicación: Filtrado de correo no deseado

• El modelo bayesiano es utilizado frecuentemente en laclasificación de texto

• El filtrado de correo no deseado se puede ver como un procesode recomendación:

• Contenido: Correos electrónicos

• Recomendación: Leerlo o no

• En el caso del texto/documentos el contenido se representa porla frecuencia de sus palabras (Bag of words)

ECSDI - Curso 2019/2020 - FIB 48/79

Filtrado colaborativo

Filtrado colaborativo

• Se basa no solo en la información del usuario, sino también enla de los usuarios que más se le parecen

• Este método permite superar el problema de no tener unabuena descripción a partir del contenido

• Asumimos que a personas similares les gustan contenidossimilares

• Esto permite recomendar contenidos que no se parezcan a losque el usuario ya ha calificado (serendipia)

• Si ha sido calificado por personas similares a él, seguramente sele puede recomendar

ECSDI - Curso 2019/2020 - FIB 49/79

Filtrado colaborativo basado en vecindad

• Basado en las valoraciones de los items del contenido

• La recomendación utiliza una combinación de las valoracionesde los k usuarios/items más parecidos

• La recomendación se puede interpretar a partir de lascalificaciones de los vecinos

• La valoración de un nuevo item se puede obtener

• Usuario con usuario: Buscamos usuarios que hayan calificadoel item y que tengan un conjunto de items calificados similares,con valoraciones similares

• Item con item: Buscamos los items del usuario que son mássimilares al que queremos recomendar

Filtrado colaborativo basado en vecindad - Usuario a usuario

ECSDI - Curso 2019/2020 - FIB 51/79

Filtrado colaborativo basado en vecindad - Item a item

Others:

Me:

Others:

Me:

Others:

Me:

Others:

Me:

?

ECSDI - Curso 2019/2020 - FIB 52/79

Filtrado colaborativo basado en vecindad

• Si las valoraciones son un valor continuo podemos calcular lavaloración como una suma ponderada de las valoraciones de losvecinos

• Si las valoraciones son valores discretos se puede aplicar unaestrategia de voto ponderado

• La ponderación se obtiene de la similaridad/distancia entre loselementos que estamos combinando (usuarios/items)

ECSDI - Curso 2019/2020 - FIB 53/79

Aprendizaje por refuerzo

Automatización de tareas

• La autonomía de los agentes hace que deban:

• aprender a adaptarse a situaciones nuevas

• deban optimizar la forma en que realizan sus tareas

• Se usan técnicas de aprendizaje específicas para resolución deproblemas

• Estas asocian acciones o secuencias de acciones a estadosespecíficos del problema

• Los métodos de aprendizaje más utilizados se basan enAprendizaje por refuerzo

ECSDI - Curso 2019/2020 - FIB 54/79

¿Qué es el aprendizaje por refuerzo?

• Un agente debe resolver una tarea (objetivo) y tiene unconjunto de acciones disponible (operadores)

• El agente elige la acción o acciones que cree que resolverán latarea

• El agente recibe información del entorno sobre la calidad de susolución

• El agente usa esta información para modificar sucomportamiento

ECSDI - Curso 2019/2020 - FIB 55/79

Agente con aprendizaje por refuerzo

Agent

Environment

Actionat

Rewardrt

State st

st+1

rt+1

ECSDI - Curso 2019/2020 - FIB 56/79

¿Donde se aplica el aprendizaje por refuerso?

• Se usa cuando el agente interacciona con el entorno

• El entorno es capaz de cuantificar el éxito o fracaso de lasacciones del agente

• El espacio de estados puede ser discreto o continuo

• Con diferentes objetivos: medir la calidad de un conjunto deacciones, en contrar el conjunto óptimo de acciones

• Con diferente complejidad: los estados o efectos de las accionesson desconocidos, efectos no deterministas en las acciones, ...

ECSDI - Curso 2019/2020 - FIB 57/79

¿Cuándo se usa el aprendizaje por refuerzo?

• Problemas demasiado complejos para ser programados

• Problemas en los que generar un conjunto de ejemplos paraaprender la tarea por métodos inductivos clásicos es demasiadocostoso

• Problemas en los que es más sencillo permitir al agenteaprender la tarea por prueba y error

• Aplicaciones: Robótica, juegos, secuenciación de procesos,coordinación distribuida, ...

ECSDI - Curso 2019/2020 - FIB 58/79

Elementos del aprendizaje por refuerzo

• Un conjunto de estados que describan el entorno(discreto/continuo)

• Un conjunto de acciones que el agente puede realizar paramodificar su entorno

• Una función de refuerzo que indica al agente el resultadoobtenido al realizar una acción sobre el estado

• Objetivo: Encontrar una política de actuación que vinculeestados con acciones y maximice la ganancia obtenida a travésde los refuerzos

ECSDI - Curso 2019/2020 - FIB 59/79

Aprendizaje por refuerzo - Ejemplo

• Queremos decidir como presentar una lista de posibles comprasa un usuario para maximizar sus clicks

• El orden en el que se presentan y el tipo de los productosinfluye en su visibilidad por parte del usuario• Estado: Combinaciones de productos

• Acciones: Reposicionar producto, cambiar su tipo

• Refuerzo: Clicks/no Clicks del usuario

• Política: Cambios en la lista que maximizan los clicks

Un escenario simple

• El aprendizaje por refuerzo puede verse como un problema dedecisión

• Comenzaremos por un escenario de aprendizaje simple

• N-armed bandit problem:

• Tenemos una maquina tragaperras con npalancas

• Cada palanca es una acción (unadecisión)

• Nuestra recompensa es el dinero queobtenemos

• El objetivo es maximizar nuestrasganancias

N-armed bandit problem

• Este escenario hay que aprender la ganancia esperada con cadadecisión

• Esta se puede aproximar aprendiendo la función acción-valor(Q(a))

• A partir de esta función:

• Se puede seguir una política avariciosa (siempre la acción quedé la mayor recompensa), con esto estamos explotando nuestroconocimiento

• Podemos salirnos de la política explorando acciones fuera de lapolítica avariciosa (buscando mejores políticas)

ECSDI - Curso 2019/2020 - FIB 62/79

Aprendizaje en el N-armed bandit problem

• Consideraremos Q∗(a) la verdadera función acción-valor (larecompensa inmediata de la acción)

• Podemos estimar Qt(a) (función acción-valor estimada)considerando la media de las recompensas inmediatascalculando Qt(a) como:

Qt(a) =r1 + r2 + · · ·+ rka

ka

siendo ka el número de veces que a ha sido seleccionadadurante las t decisiones

• Con ka →∞ Qt(a) convergerá a Q∗(a)

ECSDI - Curso 2019/2020 - FIB 63/79

Problemas de aprendizaje por refuerzo

• El n-armed bandit problem no asocia acciones con diferentescircunstancias

• Se puede extender el problema:

• Múltiples n-armed bandits

• Nos movemos de uno a otro dependiendo de las acciones quetomemos

• Este es el modelo de aprendizaje por refuerzo

• El objetivo es aprender una política (π) que indique quéacciones hacer para moverse de un estado a otro

ECSDI - Curso 2019/2020 - FIB 64/79

Problemas de aprendizaje por refuerzo

• El objetivo de un agente se formaliza usando la respuesta delentorno, es una señal que denominaremos recompensa

• El agente debe maximizar no solo la recompensa inmediata sinola recompensa acumulativa a futuro

• La recompensa a futuro permite aproximar políticas globalesmediante información local mejor que la recompensa inmediata

• Esta recompensa permite optimizar decisiones que solo sepueden optimizar a largo plazo (eg. ¿porqué reciclamos?)

ECSDI - Curso 2019/2020 - FIB 65/79

Problemas de aprendizaje por refuerzo

• El modelo para calcular el refuerzo obtenido a futuro se basa enla la recompensa atenuada (con 0 ≤ γ ≤ 1):

Rt = rt+1 + γrt+2 + γ2rt+3 + · · · =T∑k=0

γkrt+k+1

• El valor de γ representa la influencia del futuro en la decisiónactual

ECSDI - Curso 2019/2020 - FIB 66/79

Procesos de Decisión de Markov

• Hay múltiples escenarios para el aprendizaje por refuerzo

• Procesos de Decisión de Markov

• El estado puede ser observado (por sensores en el agente)

• El entorno provee una función de recompensa

• Tenemos un conjunto de acciones que cambian el estado

• La tarea cumple la propiedad de Markov (futuras decisiones nodependen del pasado)

• Estos problemas se pueden definir por sus estados, acciones yuna dinámica de un paso

ECSDI - Curso 2019/2020 - FIB 67/79

Procesos de decisión de Markov - Elementos

• Un agente puede percibir un conjunto de S estados posibles

• Existe un conjunto A de acciones que se pueden realizar

• En cada intervalo (discreto) de tiempo, el agente observa elestado (st) y elige una acción a realizar (at)

• El entorno responde con una recompensa acorde con el estadoy la acción (rt = r(st, at)), produciendo el estado sucesor(st+1 = δ(st, at))

• r y δ son funciones del entorno y no tienen por que seconocidas por el agente

ECSDI - Curso 2019/2020 - FIB 68/79

Procesos de decisión de Markov - Políticas

• Una política es un conjunto de acciones que se han de realizarpara resolver el problema

• Por ejemplo: La secuencia de movimientos en un juego, lasacciones para controlar un proceso, las interacciones para llegara un acuerdo, . . .

• Para un problema aprenderemos la mejor política (π)

• π(s, a) representará la probabilidad de hacer una acción a desdeel estado s

ECSDI - Curso 2019/2020 - FIB 69/79

Procesos de decisión de Markov - Funciones valor

• Para obtener una política se definen funciones que estiman:

• función estado-valor, Q(s): Cómo de bueno es un estadoespecífico

• función acción-valor, Q(s,a): Cómo de bueno es hacer unaacción desde un estado específico

• Definidas a partir de las recompensas futuras esperadas

• Usadas para evaluar la calidad de una política

ECSDI - Curso 2019/2020 - FIB 70/79

Procesos de Decisión de Markov - Aprendizaje

• Resolver el problema de aprendizaje por refuerzo significaencontrar:

Q∗(s) = maxπQπ(s) o Q∗(s, a) = maxπQ

π(s, a)

• Hay tres aproximaciones para resolver este problema

• Programación dinámica

• Aproximación por métodos de Monte Carlo

• Aprendizaje por diferencias temporales (Temporal Differencelearning)

ECSDI - Curso 2019/2020 - FIB 71/79

Temporal Difference Learning

• Temporal Difference Learning utiliza la recompensa obtenida apartir de los estados inmediatos

• El más simple es TD(0) que usa la estimación:

Q(st, at) = Q(st, at) + α[rt+1 + γQ(st+1, at+1)−Q(st, at)]

equivalentemente para Q(st)

• No es siempre necesario tener un modelo de la tarea

• Puede implementarse on-line, no necesita llegar al estado finalpara calcular la recompensa

ECSDI - Curso 2019/2020 - FIB 72/79

Q-learning

• Q-learning es un tipo de Time Difference Learning que nonecesita un modelo de la tarea a aprender

• El objetivo es aproximar la función acción-valor (Q) observandolas recompensas obtenidas en episodios de resolución

• A cada paso la recompensa inmediata es usada para actualizarla función Q

Q(st, at) = Q(st, at) + α[rt+1 + γmaxaQ(st+1, a)−Q(st, at)]

• La política aprendida será aquella que siempre escoja la acciónque maximiza la recompensa desde un estado

ECSDI - Curso 2019/2020 - FIB 73/79

Q-learning: Aproximación de la función acción-valor

Procedure: Q-learning

Input: Q(s, a)← función arbitrariaforeach episodio do

s←primer estado del episodioforeach pasos en el episodio do

Escoger a de la política derivada de QHacer la acción aObservar la recompensa r y el estado siguiente s′

Q(st, at) = Q(st, at)+α[rt+1+γmaxaQ(st+1, a)−Q(st, at)]s← s′

ECSDI - Curso 2019/2020 - FIB 74/79

Ejemplo - Composición de servicios

• En un entorno abierto existen muchos posibles servicios quepueden combinarse para una tarea

• En una composición debemos realizar una tarea complejacombinando servicios simples (acciones)

• No es posible evaluar todas las posibles combinaciones

• Podemos utilizar Q-learning para aprender la combinaciónóptima

• Estamos aprendiendo a como asignar servicios a una tarea apartir de la experiencia obtenida

ECSDI - Curso 2019/2020 - FIB 75/79

Ejemplo - Composición de servicios

• Las acciones serían asignar o no un servicio a una tarea

• El espacio de estados serían todas las posibles asignaciones

• Al finalizar la tarea recibiríamos un refuerzo para lasasignaciones elegidas (¿QoS?)

• Cada nueva tarea sería una nueva secuencia de entrenamiento

• Al realizar el aprendizaje on-line las asignaciones iríanevolucionando con la calidad de los servicios

ECSDI - Curso 2019/2020 - FIB 76/79

Ejemplo - Composición de servicios

Tarea

ServiciosTipo 1

1 2 3 4

ServiciosTipo 2

ServiciosTipo 3

ServiciosTipo 4

Ejecución

1 2 3 4

Evaluación

QoS

Refuerzo

ECSDI - Curso 2019/2020 - FIB 77/79

Ejemplo - Coordinación distribuida

• En un sistema abierto con agentes que realizan las mismastareas/comparten recursos/comparten objetivos es necesaria lacoordinación

• La complejidad de algunas tareas no permite tener unacoordinación centralizada o una coordinación fija

• Los agentes aprenden la acciones que pueden realizar porinteracción con el resto observando el éxito de la tarea

• Por ejemplo:• Balanceado de carga

• Asignación de recursos

• Equipos

ECSDI - Curso 2019/2020 - FIB 78/79

Ejemplo - Coordinación distribuida - Balanceado de carga

Agente distribución

Modelo