Tipos De Aprendizaje.pdf

Aprenentatge

` Enginyeria en Informatica

´ DE PROBLEMES COL.LECCIO ´ Javier Bejar Llu´ıs Belanche

` Departament de Llenguatges i Sistemes Informatics

CURS 2013/2014 1Q

cbea

Índice general

1. Aprendizaje Inductivo 1.1. Espacio de Versiones . . . . . . 1.2. Arboles de Inducción . . . . . . 1.3. Inductive Logic Programming . 1.4. Naïve Bayes . . . . . . . . . . . 1.5. K-nearest neighbor . . . . . . . 1.6. TLUs . . . . . . . . . . . . . . 1.7. Perceptrones . . . . . . . . . . 1.8. Maquinas de Soporte Vectorial

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1 1 4 8 9 10 10 12 15

2. Aprendizaje No Supervisado

17

3. Aprendizaje Basado en Explicaciones

19

4. Aprendizaje por refuerzo

31

1

Esta obra está bajo una licencia Reconocimiento-NoComercial-CompartirIgual de Creative Commons. Para ver una copia de esta licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una carta a

Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Cap´ıtulo

1

Aprendizaje Inductivo 1.1.

Espacio de Versiones

1. Supongamos que tenemos un lenguaje de descripción de conceptos que admite solo formulas conjuntivas puras y tenemos el dominio de los coches con los siguientes atributos: Precio: caro, medio, barato. Color: azul, verde, rojo. Tamaño: grande, mediano, pequeño.

Motor: diesel, gasolina. País: Japón, Francia, USA, Alemania.

Genera un conjunto de ejemplos para aprender el siguiente concepto {Coches japoneses caros} y muestra la evolución del método del espacio de versiones para aprenderlo 2. Supongamos que tenemos un lenguaje de descripción de conceptos que admite solo formulas conjuntivas puras y tenemos el dominio de las películas con los siguientes atributos: Sonoro: Color: Nacionalidad: Duración: Género:

si, no si, no USA, España, Francia, Italia cortometraje, mediometraje, largometraje comedia, drama, acción, negro, policiaca, aventuras

Genera el conjunto mínimo de ejemplos para aprender el siguiente concepto {largometrajes franceses en color} y muestra la evolución del método del espacio de versiones para aprenderlo 3. Tomando el dominio de los animales con los siguientes descriptores: Especie (jerárquico); valores: mamífero (bobino, felino, cánido, ...), reptil (ofidio, saurio, quelonio, ... ), ave (corredoras, rapaces, palmípedas, ... ). Origen (jerárquico); valores: África (Zaire, Tanzania, Kenia, ...), Asia (India, Thailandia, Siria, Nepal, ...), América (Brasil, Bolivia, Perú, Nicaragua, ...). Alimentación (cualitativo); valores: Carnívoro, Insectívoro, Omnívoro, Herbívoro. Habitat (cualitativo); valores: montaña, mar, sabana, tundra, desierto, selva. Defensa (cualitativo); valores: dientes, cuernos, veneno, garras, carrera, ... Tiempo de desarrollo (cualitativo); valores: semanas, meses, años. Generar un conjunto de ejemplos para aprender alguno de los siguientes conceptos y mostrar la evolución del espacio de versiones: a) Mamíferos asiáticos herbívoros. 1

2

ÍNDICE GENERAL b) Aves marinas carnívoras americanas. c) Felinos africanos de montaña. d) Carnivoros de sabana. e) Animales que corren y se desarrollan en meses. f ) Felinos asiáticos carnívoros. g) Aves Peruanas insectivoras con garras. h) Reptiles que corren y que se desarrollan en semanas. i) Mamíferos herbívoros del desierto. j) Animales selváticos de Asia. k) Reptiles americanos selváticos l) Mamíferos zaireños con garras que se desarrollan en meses m) Aves carnívoras n) Animales de montaña con garras ñ) Reptiles o) Animales mamiferos africanos con dientes p) Animales carnivoros americanos q) Animales marinos brasileños venenosos que se desarrollan en meses r) Animales reptiles asiaticos omnivoros s) Animales asiáticos 4. Supongamos que ampliamos nuestro lenguaje de descripción de manera que podemos describir conceptos y ejemplos con una sola disyunción en la que los disyuntados no están ordenados. Por ejemplo, si tomamos el dominio de los objetos geométricos podemos expresar el ejemplo ((bola rojo grande) o (cubo verde pequeño)) que es equivalente a ((cubo verde pequeño) o (bola rojo grande)), donde ahora un nuevo ejemplo puede generalizar un concepto de dos maneras posibles, por ejemplo, la instancia ((cubo rojo pequeño) o (cubo verde grande)) puede generalizar el ejemplo anterior como ((? rojo ?) o (cubo verde ?)) o como ((? ? grande) o (cubo ? pequeño)), igual pasa con la especialización. Teniendo en cuenta este nuevo lenguaje y como se comporta ante la generalización y la especialización, y tomando como dominio el de los coches, descrito con los siguientes atributos: Precio: caro, medio, barato. Motor: diesel, gasolina. Color: azul, verde, rojo. País: Japón, Francia, USA, Alemania. Tamaño: grande, mediano, pequeño. Generar un conjunto de ejemplos para aprender alguno de los siguientes conceptos y mostrar la evolución del espacio de versiones: a) coches diesel americanos grandes o coches diesel americanos caros. b) coches verdes japoneses pequeños o coches franceses diesel grandes. c) coches caros japoneses o coches caros americanos. d) coches grandes azules o coches japoneses diesel. e) coches americanos de gasolina rojos o coches alemanes medianos. f ) Coches diesel japoneses pequeños o coches de gasolina azules grandes. g) Coches americanos o coches franceses grandes

1.1. ESPACIO DE VERSIONES

3

h) Coches diesel japoneses caros o coches diesel americanos grandes. i) Coches caros o coches de gasolina baratos 5. Supongamos que tenemos un lenguaje de descripción de conceptos que admite una única disyunción (como en el problema anterior) y tenemos el dominio de los coches con los siguientes atributos: Precio: caro, medio, barato. Color: azul, verde, rojo. Tamaño: grande, mediano, pequeño.

Motor: diesel, gasolina. País: Japón, Francia, USA, Alemania.

Suponiendo que los disyuntandos no estan ordenados (igual que la otra vez), cual sería la modificación del espacio de versiones que aparece a continuación, con el siguiente contraejemplo: ((barato diesel verde Francia grande) (caro diesel verde USA grande)) G= {((? ? ? ? ?) (? ? ? ? ?))} S= {((? diesel ? USA grande) (caro diesel ? USA ?))} ¿Cual sería la modificación del mismo espacio de versiones si el contraejemplo fuera: ((caro diesel verde Japón pequeño)(caro diesel verde Francia pequeño))? 6. Supongamos que tenemos un lenguaje de descripción de conceptos que admite una única disyunción (como en el problema de espacio de versiones que resolvisteis) y tenemos el dominio de los coches con los siguientes atributos: Precio: caro, medio, barato. Color: azul, verde, rojo. Tamaño: grande, mediano, pequeño.

Motor: diesel, gasolina. País: Japón, Francia, USA, Alemania.

Suponiendo que los disyuntandos no estan ordenados (igual que la otra vez), cual sería la modificación del espacio de versiones que aparece a continuación, con el siguiente contraejemplo: ((caro gasolina verde USA mediano) (barato gasolina verde Francia mediano)) G= {((? ? ? ? ?) (? ? ? ? ?))} S= {((? gasolina ? Francia mediano) (barato gasolina ? Francia ?))} ¿Cual sería la modificación del mismo espacio de versiones si el contraejemplo fuera: ((barato gasolina verde Japón grande)(barato gasolina verde USA grande))? 7. Supongamos que ampliamos nuestro lenguaje de descripción de manera que podemos describir conceptos y ejemplos con una sola disyunción en la que los disyuntados no están ordenados. Por ejemplo, si tomamos el dominio de los objetos geométricos podemos expresar el ejemplo ((bola rojo grande) o (cubo verde pequeño)) que es equivalente a ((cubo verde pequeño) o (bola rojo grande)), donde ahora un nuevo ejemplo puede generalizar un concepto de dos maneras posibles, por ejemplo, la instancia ((cubo rojo pequeño) o (cubo verde grande)) puede generalizar el ejemplo anterior como ((? rojo ?) o (cubo verde ?)) o como ((? ? grande) o (cubo ? pequeño)), igual pasa con la especialización. Teniendo en cuenta este nuevo lenguaje y como se comporta ante la generalización y la especialización, y tomando como dominio el de las películas de cine, descrito con los siguientes atributos: Sonoro: si, no. Nacionalidad: USA, España, Francia, Italia. Color: si, no. Género: comedia drama, acción, negro, policiaca, aventuras. Duración: cortometraje, mediometraje, largometraje.

4

ÍNDICE GENERAL Generar un conjunto de ejemplos para aprender alguno de los siguientes conceptos y mostrar la evolución del espacio de versiones: a) Películas sonoras americanas o películas mudas de acción. b) Largometrajes españoles dramáticos o cortrometrajes cómicos italianos. c) Películas americanas de cine negro en color o comedias americanas en blanco y negro. d) Películas francesas mudas en blanco y negro o comedias mudas en blanco y negro. e) Cortometrajes en color o en blanco y negro f ) Películas mudas en blanco y negro o películas sonoras en color g) Largometrajes americanos de género negro o cortometrajes franceses cómicos h) Películas dramáticas americanas o cortrometrajes italianos i) Cortometrajes mudos o sonoros j) Comedias en color o largometrajes de acción americanos k) Peliculas policiacas en blanco y negro o en color l) Cortometrajes de acción americanos o peliculas comicas en blanco y negro m) Largometrajes de aventuras en color o cortometrajes dramaticos mudos n) Peliculas comicas sonoras o mediometrajes dramaticos en color ñ) Peliculas sonoras en color o peliculas mudas en blanco y negro 8. Supongamos que tenemos un lenguaje de descripción de conceptos que admite una única disyunción (como en el problema de espacio de versiones que resolvisteis) y tenemos el dominio de los coches con los siguientes atributos: Precio: caro, medio, barato. Color: azul, verde, rojo. Tamaño: grande, mediano, pequeño.

Motor: diesel, gasolina. País: Japón, Francia, USA, Alemania.

Suponiendo que los disyuntandos no estan ordenados (igual que la otra vez), genera un conjunto de ejemplos para aprender los siguientes conceptos: a) Coches diesel caros medianos o coches de gasolina japoneses verdes. b) Coches grandes o pequeños

1.2.

Arboles de Inducción

1. Rehaz los ejemplos de espacio de versiones utilizando el algoritmo de ID3 y compara el resultado para el conjunto de ejemplos positivos. 2. Dados los siguientes ejemplos: Ej. 1 2 3 4

Color Azul Rojo Azul Azul

Tamaño Grande Pequeño Pequeño Grande

Clase + + -

¿Que atributo tiene la mayor ganancia de información respecto a la clasificación? 3. Dados los siguientes ejemplos:

1.2. ARBOLES DE INDUCCIÓN

5 Ej. 1 2 3 4 5 6

Clase + + − + − −

A1 T T T F F F

A2 T T F F T T

¿Cual es la entropía de este conjunto de ejemplos? ¿Que atributo tiene la mayor ganancia de información respecto a la clasificación? 4. Un profesor poco escrupuloso pretende ahorrarse parte de la tarea de corrección de prácticas a base de construir un árbol de discriminación que le permita asociar ciertas características de las prácticas a un resultado. En concreto se utilizarán los atributos: Tamaño de la práctica (páginas), presentación (buena, regular, mala), documentación (existe o no), funcionamiento (funciona o no). Se podrán dar tres resultados posibles: aprueba, suspende, corregir. Generar el árbol de inducción que resulta del siguiente conjunto de ejemplos:

Pags. 100 100 80 50 50 30 20 20 20 10

Presen. Regular Buena Mala Regular Buena Mala Regular Buena Mala Regular

Docum. Si No Si No Si No Si No Si No

Funciona Si No Si Si Si No Si Si Si Si

Resultado Aprueba Suspende Aprueba Corregir Aprueba Suspende Corregir Corregir Suspende Suspende

¿Podrías averiguar los criterios de corrección del profesor? Propón unos criteros de selección de los atributos a cada nivel guiado por tu intuición sin tener el cuenta el resultado y compara los dos árboles. Razona sobre la necesidad de tener un conjunto representativo de ejemplos para obtener un resultado acorde con el criterio de un experto. 5. Construir un árbol de decisión para los siguientes conjuntos de ejemplos:

a)

Ejem. 1 2 3 4 5 6

Color Rojo Azul Rojo Verde Rojo Verde

Forma Cuadrado Cuadrado Redondo Cuadrado Redondo Redondo

Tamaño Grande Grande Pequeño Pequeño Grande Grande

Clase + + − − + −

6

ÍNDICE GENERAL

c)

b)

Ejem. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Clima Soleado Soleado Nublado Lluvioso Lluvioso Lluvioso Nublado Soleado Soleado Lluvioso Soleado Nublado Nublado Lluvioso

Ej. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Historial Malo Desconocido Desconocido Desconocido Desconocido Desconocido Malo Malo Bueno Bueno Bueno Bueno Bueno Malo

Temp. Calor Calor Calor Suave Frío Frío Frío Suave Frío Suave Suave Suave Calor Suave

Deudas Altas Altas Bajas Bajas Bajas Bajo Bajas Bajas Bajas Altas Altas Altas Altas Altas

Humedad Alta Alta Alta Alta Normal Normal Normal Alta Normal Normal Normal Alta Normal Alta

Informes Ninguno Ninguno Ninguno Ninguno Ninguno Buenos Ninguno Buenos Ninguno Buenos Ninguno Ninguno Ninguno Ninguno

Viento Débil Fuerte Débil Débil Débil Fuerte Fuerte Débil Débil Débil Fuerte Fuerte Débil Fuerte

Sueldo 0 a 2M 2M a 5M 2M a 5M 0 a 2M Mas de 5M Mas de 5M 0 a 2M Mas de 5M Mas de 5M Mas de 5M 0 a 2M 2M a 5M Mas de 5M 2M a 5M

Picnic No No Si Si Si No Si No Si Si Si Si Si No

Riesgo Alto Alto Moderado Alto Bajo Bajo Alto Moderado Bajo Bajo Alto Moderado Bajo Alto

6. Dada la siguiente tabla que representa ejemplos de clasificación de películas de cine según los cinco atributos que aparecen a continuación, construye el árbol de decisión resultante de aplicar el algoritmo de ID3.

Atributos nacionalidad: genero: actores: guión: director:

Valores USA, Europa, Asia comedia, drama, acción, policiaca, aventuras guaperas, actor_de_verdad, normal original, adaptado bueno, por_encargo, normal

1.2. ARBOLES DE INDUCCIÓN ID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Nacionalidad USA USA Europa USA Europa USA USA USA USA USA Asia Asia Europa Europa USA

7

Género accion drama drama aventuras aventuras drama drama policiaca comedia aventuras accion drama drama comedia drama

Actores guaperas actor_de_verdad actor_de_verdad actor_de_verdad actor_de_verdad guaperas normal actor_de_verdad normal guaperas normal normal normal guaperas guaperas

Guión original adaptado adaptado original adaptado original adaptado original original original original original original original original

Director bueno bueno bueno normal bueno por_encargo normal normal normal normal normal normal por_encargo por_encargo normal

Clase buena buena buena buena buena regular regular regular regular regular mala mala mala mala mala

7. El algoritmo ID3 explicado en clase esencialmente busca el árbol de decisión mínimo escogiendo en cada nivel la condición que de máxima información sobre la pertenencia de cada instancia a una clase. a) ¿Como se comportaría el algoritmo si cada instancia tiene un atributo que es identificador único (p.e.: el DNI)? b) ¿Como predeciría un árbol con datos con esas características? 8. En muchos dominios no todos los atributos son igualmente costosos de comprobar (p.e.: En un dominio médico posiblemente sea más barato hacer una análisis de sangre que una resonancia magnética). Suponiendo que el coste de conocer el valor del atributo X es CX , proponer una modificación del algoritmo de ID3 para construir árboles que minimizen el coste de la comprobación de los valores de los atributos. 9. En algunos dominios existen atributos en los que en algunas instancias se puede haber perdido su valor. Como modificarias el criterio de selección de los atributos para que se tenga en cuenta esto. 10. Dados los siguientes ejemplos, determina cual seria el atributo raíz que escogería el algoritmo de ID3 con la función de ganancia de información1 . ¿Tiene alguna influencia el número de valores por cada atributo en la decisión?, calcula cual sería el atributo elegido utilizando el split info. Obj 1 2 3 4 5 6 7

A a b b a a b c

B x y z z z y x

C 1 1 3 2 3 2 1

Clase C1 C1 C1 C1 C1 C1 C1

Obj 8 9 10 11 12 13 14

A c b c b c b c

B y x y x z z x

C 3 3 4 2 3 2 4

Clase C2 C2 C2 C2 C2 C2 C2

Atributo A={a,b,c} Atributo B={x,y,z} Atributo C={1,2,3,4} 11. Dados los siguientes árboles de decisión que han sido obtenidos usando el método de bagging a partir de un conjunto de ejemplos: ¿Cual sería la clasificación que obtendríamos para los siguientes ejemplos? 1

Recordad que loga (x) =

logb (x) logb (a)

y que es un factor común.

8

ÍNDICE GENERAL A

B

1

2

B

B

1 C

2 +

A

2

1 +

C

1

2

1

2

1

2

1

2

+

−

+

−

+

−

+

−

Ejemplo X1 X2 X3

A 1 2 1

B 2 1 1

C 1 2 2

Clase

12. Dados los siguientes árboles de decisión que han sido obtenidos usando el método de bagging a partir de un conjunto de ejemplos: B

A

C

1

2

A

1 C

2 +

A

2

1 +

B

1

2

1

2

1

2

1

2

+

−

+

−

+

−

+

−

¿Cual sería la clasificación que obtendríamos para los siguientes ejemplos? Ejemplo X1 X2 X3

1.3.

A 2 2 1

B 2 1 1

C 2 1 2

Clase

Inductive Logic Programming

1. Tenemos el siguiente conjunto de ejemplos: p(a, b),p(a, c),p(b, d),p(c, e),p(e, i),p(g, h),p(h, e) a(a, d),a(a, e),a(a, i),a(g, e),a(g, i),a(c, i),a(h, i) ¬a(i, a),¬a(b, a),¬a(c, h),¬a(h, c),¬a(c, d),¬a(h, d),¬a(g, c) a) Considerando como criterio de preferencia la diferencia entre ejemplos positivos y negativos cubiertos, realiza la primera iteración del algoritmo FOIL par aprender el concepto a(x, y) b) Enumera el conjunto de cláusulas candidatas para continuar la regla aprendida en la primera iteración 2. Tenemos el siguiente conjunto de ejemplos: P (1, 4),P (2, 4),P (2, 5),P (3, 5),P (1, 6),P (2, 6),P (6, 7),P (8, 3) B(4, 5),B(5, 4),B(4, 6),B(6, 4),B(5, 6),B(6, 5) ¬B(1, 2),¬B(2, 1),¬B(2, 3),¬B(3, 2),¬B(3, 7),¬B(6, 8) Suponiendo que el concepto objetivo que queremos aprender es B(x, y) y vamos a usar FOIL como algoritmo de aprendizaje:

1.4. NAÏVE BAYES

9

a) ¿Qué ejemplos positivos y negativos cubre la regla B(x, y) → P (z, x)? b) ¿Qué ejemplos positivos y negativos cubre la regla B(x, y) → P (z, x) ∧ P (z, y)? c) Suponiendo que en la primera iteración hemos escogido la regla B(x, y) → P (z, x) y restringiéndonos a átomos positivos y que no sean el objetivo de la regla (B) ¿Cual sería el conjunto de átomos candidatos que deberíamos probar en la siguiente iteración del algoritmo?

1.4.

Naïve Bayes

1. En la siguiente tabla esta representada la distribución de probabilidad aprendida mediante naïve bayes a partir de un conjunto de ejemplos pertenecientes a tres clases. El conjunto de datos consta de tres atributos A1, A2, A3, con los siquientes valores A1={a,b}, A2={a,b,c}, A3={1,2,3}.

Clase 1 Clase 2 Clase 3

A1 a b 0.3 0.7 0.9 0.2 0.4 0.6

a 0.1 0.2 0.3

A2 b 0.2 0.4 0.3

c 0.7 0.4 0.4

1 0.6 0.2 0.1

A3 2 0.2 0.5 0.6

3 0.2 0.3 0.3

Dado el siguiente ejemplo ej1= (A1=b,A2=b,A3=3), calcula a que clase lo asignaría el clasificador aprendido. 2. En la siguiente tabla esta representada la distribución de probabilidad aprendida mediante naïve bayes a partir de un conjunto de ejemplos pertenecientes a tres clases. El número de ejemplos de cada clase utilizados para general la tabla son (clase 1 = 100 ejemplos, clase 2 = 200 ejemplos, clase 3= 100 ejemplos). El conjunto de datos consta de tres atributos A1, A2, A3, con los siquientes valores A1={a,b}, A2={R,G,B}, A3={x,y,z}.

Clase 1 Clase 2 Clase 3

A1 a b 0.2 0.8 0.5 0.5 0.7 0.3

R 0.2 0.3 0.5

A2 G 0.2 0.6 0.4

B 0.6 0.1 0.1

x 0.1 0.3 0.7

A3 y 0.6 0.2 0.1

z 0.3 0.5 0.2

Dado el siguiente ejemplo ej1= (A1=b,A2=R,A3=z), ¿que probabilidad de pertenencia a cada clase le asignaría el clasificador aprendido? 3. En la siguiente tabla está representada las distribuciones de probabilidad aprendidas mediante naïve bayes a partir de un conjunto de ejemplos pertenecientes a tres clases. El número de ejemplos de cada clase utilizados para general la tabla son: clase 1 = 300 ejemplos, clase 2 = 200 ejemplos, clase 3= 100 ejemplos. El conjunto de datos consta de tres atributos A1, A2, A3, con los siquientes valores A1={a,b}, A2={R,G,B}, A3={x,y,z}.

Clase 1 Clase 2 Clase 3

A1 a b 0.3 0.7 0.9 0.1 0.6 0.4

R 0.1 0.4 0.7

A2 G 0.3 0.5 0.1

B 0.6 0.1 0.2

x 0.1 0.3 0.4

A3 y 0.6 0.3 0.4

z 0.3 0.4 0.2

Dado el siguiente ejemplo ej1= (A1=a,A2=G,A3=y), ¿que probabilidad de pertenencia a cada clase le asignaría el clasificador aprendido?

10

ÍNDICE GENERAL

1.5.

K-nearest neighbor

1. Dados los siguientes ejemplos que tienen un solo atributo real y están clasificados en dos clases (+,−). Vamos a usar K-nearest neighbour usando la distancia euclídea sin ponderar. +

+

−

−

+

−

+

+

−

−

-3.5

-2.7

-2.1

-1.3

-0.8

-0.4

0.3

1.4

2.3

3.1

x y

-3.5 +

-2.7 +

-2.1 −

-1.3 −

-0.8 +

-0.4 −

0.3 +

1.4 +

2.3 −

3.1 −

a) Calcula el error leave-one-out para un clasificador 1-Knn y expresa ese error como el número de ejemplos mal clasificados b) Calcula el error leave-one-out para un clasificador 3-Knn y expresa ese error como el número de ejemplos mal clasificados 2. Dados los siguientes ejemplos que representan una función unidimensional:

x 1 2 2.5 3 3.75 4.5 5

y 1 1.5 2 3 3.5 2.5 1.5

Calcular para los valores 1.5 y 3.5 el resultado que daría la regresión local calculada por k-nn en los siguientes casos: a) Media de los 2, 3 y 4 vecinos más cercanos (rompiendo empates prefiriendo vecinos a la izquierda) b) Ponderación por 1/distancia de los 2, 3 y 4 vecinos más cercanos c) Regresión lineal con los 3, 4 vecinos más cercanos d) Representa gráficamente los resultados y coméntalos. Nota: Un modelo de regresión lineal ajusta la recta y = α + β · x para un vector de puntos x y sus valores y, en el caso unidimensional β se puede calcular como: β=

x·y−x·y x2 − x2

siendo α = y − β · x (siendo z la media de un vector)

1.6.

TLUs

1. La siguientes redes utilizan neuronas TLU (Threshold Logical Units), donde la arista representa el peso y el nodo el límite. Dar la función lógica que evalúan.

1.6. TLUS

11 1 1

1

-1

1

1

a) -1 1 1

2

b) 1 1 1

2

c) 2. Encontrar las redes de neuronas TLU que calculen las funciones siguientes (proponer soluciones con 1 y 2 neuronas): a) y(x1 , x2 , x3 ) = x1 ∧ x2 ∧ ¬x3 b) y(x1 , x2 , x3 ) = ¬x1 ∧ x2 ∧ ¬x3 c) y(x1 , x2 ) = x1 ∧ x2 d) y(x1 , x2 , x3 ) = ¬(x1 ∨ x2 ) ∧ ¬(x2 ∨ x3 ) ∧ ¬(x3 ∨ x2 ) 3. ¿Qué función lógica calcula la red de la figura? ¿Se podría hacer con solo una neurona? 1 1

0

-1

1

4. Dada la siguiente red TLU 1

1

-1

1 1

-1 1

La función binaria que calcula esta red es: a) (x1 ∧ ¬x2 ) ∨ (¬x1 ∧ x2 ) b) (x1 ∨ ¬x2 ) ∧ (¬x1 ∨ x2 ) c) (x1 ∧ ¬x2 ) d) (¬x1 ∧ ¬x2 ) ∨ (x1 ∧ x2 )

1

1

12

ÍNDICE GENERAL

1.7.

Perceptrones

1. La red de la figura utiliza neuronas con la función de activación heaviside binaria de la forma: (

H(x) =

+1 si x ≥ 0 −1 si x < 0

realiza una correspondencia de R2 −→ {+1, −1}. Mostrarla gráficamente. -1 -3

2 1

1

1 -1

-3

2.5

1 -1

-1

2. Considerando la red de la figura que usa neuronas con función de activación heaviside (como en el problema anterior). Representar gráficamente la región para la que la red da una salida de 1. Tomar x0 = −1. -1 -3

2 1

1

1 -1 3.5

1

-3

-1 1 -6

2

3. Considerad la red multicapa de la figura donde cada unidad calcula:

yi = H(

ni X

wij xj )

j=0

Siendo x el vector de entrada con x0 = 1 fijo, ni el número de entradas de la neurona i (n1 = 2, n2 = 3) y H la función heaviside.

1.7. PERCEPTRONES

13

1

1

-1.5

-2

Neurona 1

Neurona 2

1 -0.5 1 1

La entradas son binarias, es decir x = (x1 , x2 ) ∈ {0, 1} × {0, 1}, con lo que la red calcula una función lógica f . Se pide: a) ¿Qué función lógica f1 calcula la neurona 1? b) ¿Qué función lógica f2 calcula la neurona 2? c) ¿Qué función f calcula la red? Expresarla en función de f1 y f2 . 4. Dar un ejemplo de una función booleana que sea linealmente separable y de una que no lo sea. 5. Decir si las siguientes funciones lógicas son linealmente separables a) y(x1 , x2 , x3 ) = x1 ∧ (x2 ∨ x3 ) b) y(x1 , x2 , x3 ) = (x1 ∧ x2 ) ∨ x3 ) c) y(x1 , x2 , x3 ) = x1 d) y(x1 , x2 , x3 ) = (x3 ) ∧ x1 ) ∨ (¬x3 ∧ ¬x2 ) 6. Tenemos un perceptrón con dos entradas x1 y x2 con pesos w0 = −0.35, w1 = 0.5 y w2 = 0.2, queremos que la entrada x = (−1, 1) de como resultado +1 (el valor de la entrada de sesgo es 1). a) ¿Es salida del perceptrón es correcta para esta entrada? b) Si no es correcta, aplica la regla del perceptrón las veces que sean necesarias hasta que la salida sea correcta utilizando α = 0.25. Haz lo mismo con α = 0.1. c) Aplica cuatro iteraciones de la regla δ con α = 0.25 7. Queremos entrenar un perceptrón para el conjunto de datos x1 = (1, −2), x2 = (0, 23 ), x3 = (−1, 1), x4 = (− 21 , 2), las salidas son respectivamente 0, 0, 1 y 1. Se pide: a) Ejecutar a mano la regla del perceptrón. Tomar α = 1 y vector inciial de pesos w = ( 12 , 1, −1) b) Representar gráficamente el resultado. 8. Queremos entrenar un perceptrón de una sola neurona para la siguiente tarea: Tenemos un display indicador del tráfico en el que se pueden encender de manera independiente las señales a (el signo “<”), b (el segmento recto y c (el signo “>” como se muestra en la figura. El perceptrón ha de dar respuesta afirmativa cuando se encienda la flecha izquierda (“<-”), la flecha derecha (“->”) o las dos a la vez (“<->”) y negativa para el resto (mal funcionamiento). Podemos suponer que el display tiene tres variables binarias (xa , xb y xc que expresan el estado del indicador (por ejemplo, xa = 1 quiere decir que la señal a está encendida)

a

b

c

14

ÍNDICE GENERAL 9. Considerar dos perceptrones de una neurona con dos dimensiones que calculal y = H(w0 +w1 x1 +w2 x2 ), siendo H la función heaviside. El perceptrón A tiene valores w0 = 2, w1 = −2 y w2 = 1, mientras que el perceptrón B tiene valores w0 = −2, w1 = −2 y w2 = 1. Decimos que un perceptrón P es más general que otro Q si P da una salida 1 siempre que lo hace Q. ¿Es cierto que A es más general que B?

10. Sea el conjunto de puntos x1 = (1, 1), x2 = (0, 0), x3 = (2, 2), x4 = (1, 0), x5 = (2, 0), x6 = (0, 1). Estos puntos se han de poder separar en dos clases: la clase +1 i la clase −1, de manera que x1, x3 y x5 son de la clase +1 y el resto de la −1. a) Dibujar los puntos en unos ejes coordenados y razonad si se puede hacer con un perceptrón. b) Entrenad un perceptrón con la regla vista en teoría, partiendo de un vector de pesos inicial w = (0, 0, 0) y α = 21 , presentando los puntos en el orden dado. c) Dibujar la recta solución superpuesta con los puntos de entrenamiento. ¿Qué tiene de particular esta recta respecto a los puntos? 11. Tenemos un perceptrón con dos entradas x1 y x2 donde el valor de la entrada de sesgo es 1 y los pesos asignados a cada entrada son (w0 = 2, w1 = 1, w2 = −1). La función de activación de la neurona es la función signo, de manera que los ejemplos se clasifican como positivos si el valor en el hiperplano es positivo o cero y como negativo en otro caso. a) Escribe la ecuación del hiperplano separador e indica cual es la clasificación que daría para los puntos (0, 0) y (−1, 2). b) Supongamos que el punto (−1, 0) es de la clase negativa. Dados los pesos anteriores aplica la regla del perceptrón para que se clasifique correctamente y da la ecuación del hiperplano resultante usando una tasa de aprendizaje de 0.5. c) Da la ecuación del hiperplano si usamos la regla delta con una tasa de aprendizaje de 0.5. 12. Dado el perceptrón multicapa de la figura, siendo la función de activación de las neuronas de la capa oculta la combinación lineal de sus entradas y la función de activación de la neurona de salida la función signo de la combinación lineal de sus entradas, calcula el hiperplano separador que corresponde a cada una de las neuronas de la capa oculta y da la clasificación que da la red para los siguientes puntos (1, 1), (−1, 1) y (0, 3).

1

1

1

-1

1 -1

-2

0

1

1

2 -1

1

3

1

1

S

13. Dado el perceptrón multicapa de la figura, siendo la función de activación de las neuronas de la capa oculta la combinación lineal de sus entradas y la función de activación de la neurona de salida la función signo de la combinación lineal de sus entradas, calcula el hiperplano separador que corresponde a cada

1.8. MAQUINAS DE SOPORTE VECTORIAL

15

una de las neuronas de la capa oculta y da la clasificación que da la red para los siguientes puntos (1, 1), (−1, 1) y (0, 3).

0

-1

1

-3

1 -1

1

3

1

1

2 1

2

3

-2

-1

S

14. Tenemos un perceptrón con dos entradas x1 y x2 donde el valor de la entrada de sesgo es 1 y los pesos asignados a cada entrada son (w0 = 3, w1 = 3, w2 = 1). La función de activación de la neurona es la función signo, de manera que los ejemplos se clasifican como positivos si el valor en el hiperplano es positivo o cero y como negativo en otro caso. a) Escribe la ecuación del hiperplano separador e indica cual es la clasificación que daría para los puntos (1, 1), (−2, 1), (−2, −2) y (1, −3). b) Supongamos que los dos primeros puntos son de la clase positiva y los dos últimos. Dados los pesos iniciales aplica una iteración de la regla delta y muestra como se halla la ecuación del hiperplano resultante usando una tasa de aprendizaje de 0.1. 15. Tenemos un perceptrón con dos entradas x1 y x2 donde el valor de la entrada de sesgo es 1 y los pesos asignados a cada entrada son (w0 = 3, w1 = 1, w2 = 3). La función de activación de la neurona es la función signo, de manera que los ejemplos se clasifican como positivos si el valor en el hiperplano es positivo o cero y como negativo en otro caso. a) Escribe la ecuación del hiperplano separador e indica cual es la clasificación que daría para los puntos (1, 1), (1, −3), (−2, −2) y (−2, 1). b) Supongamos que los dos primeros puntos son de la clase positiva y los dos últimos. Dados los pesos iniciales aplica una iteración de la regla delta y muestra como se halla la ecuación del hiperplano resultante usando una tasa de aprendizaje de 0.1.

1.8.

Maquinas de Soporte Vectorial

1. Tenemos el punto (2, 2) clasificado como positivo y el (1, 1) como negativo. Resuelve analíticamente el problema de optimización cuadrática de la SVM lineal para este caso y calcula los pesos de los vectores de soporte y el hiperplano separador. (Nota: al ser solo dos puntos el problema se simplifica en hallar el máximo de una función cuadrática) 2. Dado el siguiente conjunto de puntos:

16

ÍNDICE GENERAL x1 1 2 2 0 1 0

Categoría C1 C1 C1 C2 C2 C2

x2 1 2 0 0 0 1

Representa los seis puntos y a partir del gráfico calcula el hiperplano separador que maximiza el margen y el tamaño del margen. ¿Cuales serían los vectores de soporte? 3. Dada la siguiente tabla de ejemplos y pesos que corresponden a vectores de soporte obtenidos mediante el algoritmo de máquinas de soporte vectorial. Calcula el hiperplano separador a partir de estos vectores de soporte (primero el vector de pesos w y despues el interceptor b) y calcula la clasificación de los ejemplos (2, 0) y (1.4) usando los vectores de soporte, no el hiperplano. x1 2 4 1

x2 4 2 1

y + + -

α 0.125 0.125 0.25

4. Dada la siguiente tabla de ejemplos y pesos que corresponden a vectores de soporte obtenidos mediante el algoritmo de máquinas de soporte vectorial. Calcula el hiperplano separador a partir de estos vectores de soporte (primero el vector de pesos w y despues el interceptor b) y calcula la clasificación de los ejemplos (−1, 0) y (3, 1) usando los vectores de soporte, no el hiperplano. x1 1 3 4

x2 2 4 1

y + + -

α 0.125 0.125 0.25

Cap´ıtulo

2

Aprendizaje No Supervisado 1. Dada la siguiente jerarquía construida mediante el algoritmo de COBWEB.

F C T

P(C)= 2/5 Ci 1 Cu 0 R 1 V 0 A 0 P 0 M 1/2 G 1/2

F C T

F C T

P(C)= 1/2 Ci 1 Cu 0 R 1 V 0 A P0 M1 G

0 0

F C T

P(C)= 1/2 Ci 1 Cu 0 R 1 V 0 A0 P 0 M0 G 1

P(C)= 1 Ci 2/5 Cu 3/5 R 2/5 V 1/5 A 2/5 P 1/5 M 2/5 G 2/5

F C T

F C T

P(C)= 2/5 Ci 0 Cu 1 R 0 V 0 A1 P 0 M1/2 G 1/2

P(C)= 1/2 Ci 0 Cu 1 R 0 V 0 A 1 P 0 M1 G 0

F C T

F C T

P(C)= 1/5 Ci 0 Cu 1 R0 V 1 A 0 P1 M 0 G 0

P(C)= 1/2 Ci 0 Cu 1 R 0 V 0 A 1 P 0 M0 G 1

El dominio consta de 3 atributos: Forma: circulo, cuadrado. Color: rojo, verde, amarillo Tamaño: pequeño, mediano, grande ¿Como se modificaría al introducir el ejemplo: (cuadrado verde grande)?

17

18

ÍNDICE GENERAL

Cap´ıtulo

3

Aprendizaje Basado en Explicaciones 1. Considera la siguiente teoría de dominio para el concepto aprueba: aprueba(x) ← conoce_la_asignatura(x) ∧ esta_despierto(x) conoce_la_asignatura(x) ← ha_estudiado(x) esta_despierto(x) ← durmio_anoche(x) ha_estudiado ← f ue_a_clase(x) ∧ leyo_los_apuntes(x) Supón que los predicados operacionizables son {durmio_anoche, estudio, desayuno, aprobo_el_parcial, f ue_a_clase, leyo_los_apuntes}. Genera la explicación para la siguiente instancia positiva del concepto: durmio_anoche(juan) ∧ estudio(juan) ∧ ¬desayuno(juan) ∧ ¬aprobo_el_parcial(juan) ∧ leyo_los_apuntes(juan) 2. Aprende el concepto dias en los que navegar utilizando EBG. Tenemos la siguiente teoría del dominio: Dia_para_navegar(x) ← lloviendo(x, no) ∧ laborable(x, no) Dia_para_navegar(x) ← lloviendo(x, no) ∧ viento(x) laborable(x, no) ← f in_de_semana(x) f in_de_semana(x) ← domingo(x) f in_de_semana(x) ← sabado(x) lloviendo(x, no) ← soleado(x, si) Tenemos como instancia positiva del concepto: Dia_para_navegar(Julio_5), aniversario_juan(Julio_5), sabado(Julio_5), soleado(Julio_5, si), dia_siguiente(Julio_5, Julio_6) El concepto sólo puede estar expresado con los predicados de la instancia. 3. Aprende el concepto apilable utilizando EBG. Tenemos la siguiente teoría del dominio: apilable(x, y) ← ¬f ragil(y) apilable(x, y) ← mas_ligero(x, y) peso(x, w) ← volumen(x, v) ∧ densidad(x, d) ∧ multip(v, d, w) mas_ligero(x, y) ← peso(x, w) ∧ peso(y, z) ∧ menor(w, z) peso(x, 5) ← es_un(x, mesa) Tenemos como instancia positiva del concepto: 19

20

ÍNDICE GENERAL sobre(obj1, obj2), es_un(obj1, caja), es_un(obj2, mesa), color(obj1, rojo), color(obj2, azul), volumen(obj1, 1), densidad(obj1, .1), multip(1, x, x), menor(.1, 5) El concepto sólo puede estar expresado con los predicados de la instancia. 4. Aprende el concepto mata(juan,juan) utilizando EBG. Tenemos la siguiente teoría del dominio: mata(x, y) ← odia(x, y) ∧ posee(x, w) ∧ es_un(w, arma)) odia(x, x) ← deprimido(x) posee(x, y) ← compra(x, y) es_un(x, arma) ← es_un(x, pistola) Tenemos como instancia positiva del concepto: deprimido(juan), compra(juan, p1), es_un(p1, pistola) El concepto sólo puede estar expresado con los predicados de la instancia. 5. Aprende el concepto taza utilizando EBG. Tenemos la siguiente teoría del dominio: taza(x) ← estable(x) ∧ alzable(x) ∧ vaso_abierto(x) estable(x) ← f ondo(y) ∧ parte_de(y, x) ∧ plano(y) alzable(x) ← asible(x) ∧ ligero(x) asible(x) ← asa(y) ∧ parte_de(y, x) vaso_abierto(x) ← concavidad(y) ∧ parte_de(y, x) ∧ hacia_arriba(y) Tenemos como instancia positiva del concepto: ligero(obj1), color(obj1, rojo), parte_de(asa1, obj1), asa(asa1), f ondo(f 1), parte_de(f 1, obj1), plano(f 1), concavidad(c1), parte_de(c1, obj1), hacia_arriba(c1) El concepto sólo puede estar expresado con los predicados de la instancia. 6. La siguiente teoría de dominio describe las relaciones de parentesco de una familia. Genera la representación de una familia cualquiera y genera utilizando EBL las explicaciones correspondientes a algunos de los predicados de la teoría planteando algunos ejemplos utilizando la representacion de la familia. Supón que solo son operacionizables los predicados progenitor, casado, var´ on y mujer.

padre(x, y) ← progenitor(x, y) ∧ varon(x) casado(x, y) ← casado(y, x) madre(x, y) ← progenitor(x, y) ∧ mujer(x) marido(x, y) ← casado(x, y) ∧ varon(x) esposa(x, y) ← casado(x, y) ∧ mujer(x) hijo(x, y) ← progenitor(y, x) ∧ varon(x) hija(x, y) ← progenitor(y, x) ∧ mujer(x) hermanos(x, y) ← padre(f, x) ∧ padre(f, y) ∧madre(m, x) ∧ madre(m, y) hermano(x, y) ← hermanos(x, y) ∧ varon(x) hermana(x, y) ← hermanos(x, y) ∧ mujer(x) cu˜ nada(x, y) ← hermano(b, y) ∧ casado(x, b) cu˜ nado(x, y) ← hermana(s, y) ∧ casado(x, s) suegra(x, y) ← madre(x, s) ∧ casado(s, y) suegro(x, y) ← padre(x, s) ∧ casado(s, y)

3 Aprendizaje Basado en Explicaciones

21

tio(x, y) ← progenitor(p, y) ∧ hermano(x, p) tio(x, y) ← progenitor(p, y) ∧ hermana(s, p) ∧ marido(x, s) tia(x, y) ← progenitor(p, y ∧ hermana(xp) tia(x, y) ← progenitor(p, y) ∧ hermano(b, p) ∧ esposa(x, b) primo(x, y) ← progenitor(p, x) ∧ progenitor(o, y) ∧ hermanos(p, o) abuela(x, y) ← progenitor(p, y) ∧ madre(x, p) abuelo(x, y) ← progenitor(p, y) ∧ padre(x, p) ancestro(x, y) ← progenitor(x, y) ancestro(x, y) ← progenitor(p, y) ∧ ancestro(x, p) descendiente(x, y) ← ancestro(y, x)

7. Suponiendo un sistema de aprendizaje que utiliza EBL y el dominio de la familia en el que los predicado progenitor, casado, var´ on y mujer son predicados operacionalizables y con la siguiente teoría del dominio:

padre(x, y) ← progenitor(x, y) ∧ varon(x) madre(x, y) ← progenitor(x, y) ∧ mujer(x) casado(x, y) ← casado(y, x) marido(x, y) ← casado(x, y) ∧ varon(x) esposa(x, y) ← casado(x, y) ∧ mujer(x) ¿Se pueden operacionalizar los siguientes predicados? ¿Es única su operacionalización? ¿Es recomendable operacionalizar los dos? ¿Porque? suegro(x, y) ← padre(x, s) ∧ esposa(s, y) ancestro(x, y) ← progenitor(p, y) ∧ ancestro(x, p) ancestro(x, y) ← progenitor(x, y) ¿Cual sería el resultado de la operacionalización? (genera un ejemplo que la permita) 8. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: coger(x) Pre y Suprimir: en_mesa(x), libre(x), manovacía Añadir: cogido(x) dejar(x) Pre y Suprimir: cogido(x) Añadir: en_mesa(x), libre(x), manovacía apilar(x) Pre y Suprimir: cogido(x), libre(x) Añadir: manovacía, sobre(x,y), libre(x) desapilar(x) Pre y Suprimir: manovacía, libre(x), sobre(x,y) Añadir: cogido(x), libre(y)

22

ÍNDICE GENERAL Genera una escena del mundo de los bloques y escoge un objetivo. Crea una tabla triangular con el plan necesario para cumplir el objetivo y generalízala. 9. Supón que añadimos a las escenas anteriores la existencia de habitaciones que pueden estar conectadas entre si por pasadizos. La mano de robot se convierte en un robot entero con una mano. Los bloques y el robot pueden estar en una habitación. El conjunto de operadores disponibles se incrementa de la siguiente manera: ir(robot, p, hab1, hab2) Precondición: conectadas(p, hab1, hab2), en(hab1, robot) Suprimir: en (hab1, robot) Añadir: en(hab2, robot) empujar(robot, caja, p, hab1, hab2) Precondición: conectadas(p, hab1, hab2), en(hab1, robot), en(hab1, caja) Suprimir: en (hab1, robot), en(hab1, caja) Añadir: en(hab2, robot), en(hab, caja) Genera una escena del mundo de los bloques y escoge un objetivo. Crea una tabla triangular con el plan necesario para cumplir el objetivo y generalízala.

10. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: coger(x):

Precondición: en_mesa(x), libre(x), manovacía Suprimir: en_mesa(x), libre(x), manovacía Añadir: cogido(x)

dejar(x):

Precondición: cogido(x) Suprimir: cogido(x) Añadir: en_mesa(x), libre(x), manovacía

apilar(x,y):

Precondición: cogido(x), libre(y) Suprimir: cogido(x), libre(y) Añadir: manovacía, sobre(x,y), libre(x)

desapilar(x,y):

Precondición: manovacía, libre(x), sobre(x,y) Suprimir: manovacía, libre(x), sobre(x,y) Añadir: cogido(x), libre(y)

Supón que quieres planificar para pasar del estado inicial al estado final que aparecen en la figura. ¿Que ejemplos resolverías primero para hacer este problema más eficientemente? Genera la tabla triangular generalizada para estos problemas e incluye el resultado como otros operadores más. Intenta resolver el problema incial con estos nuevos operadores y generaliza también esta resolución. Los predicados con los que se puede describir una escena son: manovacía: La mano del robot esta libre sobre(x,y): El objeto x está sobre el objeto y libre(x): El objeto x no tiene nada encima cogido(x): El objeto x esta cogido por la mano del robot en_mesa(x): El objeto x esta sobre la mesa C C

D

B

A

B D

A

3 Aprendizaje Basado en Explicaciones

23

11. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: Operador Prec. Supr. Añadir Operador Prec. Supr. Añadir

coger(x) en_mesa(x), libre(x), manovacía en_mesa(x), libre(x), manovacía cogido(x) apilar(x,y) cogido(x), libre(y) cogido(x), libre(y) manovacía, sobre(x,y), libre(x)

dejar(x) cogido(x) cogido(x) en_mesa(x), libre(x), manovacía desapilar(x,y) manovacía, libre(x), sobre(x,y) manovacía, libre(x), sobre(x,y) cogido(x), libre(y)

Los predicados con los que se puede describir una escena son: manovacía: La mano del robot esta libre sobre(x,y): El objeto x está sobre el objeto y libre(x): El objeto x no tiene nada encima

cogido(x): El objeto x esta cogido por la mano del robot en_mesa(x): El objeto x esta sobre la mesa

a) Resuelve el problema de la figura y generaliza la resolución usando aprendizaje EBL. C

B

B

A

C

A

b) Supón que quieres planificar para pasar del estado inicial al estado final que aparecen en la figura. ¿Que ejemplos resolverías primero para hacer este problema más eficientemente? Genera la tabla triangular generalizada para estos problemas e incluye el resultado como otros operadores más. Intenta resolver el problema inicial con estos nuevos operadores y generaliza también esta resolución. C

D

D

C

B

A

B

A

12. Queremos trabajar en un mundo parecido al de los bloques en el que tenemos vasos, posavasos y la mano de un robot. Para manipular en este mundo disponemos de dos operadores coger(x,y) y dejar(x,y) Operador Prec. Supr. Añadir Operador Prec. Supr. Añadir

coger(x,y) vaso(x), posavasos(y), sobre(x,y), manovacía sobre(x,y), manovacía cogido(x), libre(y) dejar(x,y) vaso(x), posavasos(y), libre(y), cogido(x) cogido(x), libre(y) sobre(x,y), manovacía

Supón que queremos resolver el problema que aparece a continuación:

C

A

B

1

2

3

4

A

B

C

1

2

3

4

24

ÍNDICE GENERAL Para resolverlo más sencillamente vamos a plantearnos primero resolver mover un vaso de un posavasos a otro. Resuelve el problema de la figura siguiente y aprende a partir de él el operador mover(x,y,z) que mueve el vaso x del posavasos y al posavasos z. Resuelve el problema inicial usando este nuevo operador.

A

A

1

1

2

2

Supongamos que queremos un operador mas potente que intercambie los vasos entre dos posavasos usando un tercero como soporte temporal. Resuelve el problema de la figura siguiente usando el operador mover(x,y,z) para aprender en operador intercambiar(a,b,x,y,z) que intercambia el vaso a que esta sobre el posavasos x con el vaso b que esta sobre el posavasos y. Usa este nuevo operador para resolver otra vez el problema inicial.

A

B

1

2

3

B

A

1

2

3

Comenta las diferencias entre las dos soluciones. ¿Tiene ventajas el operador más complejo respecto al más simple? ¿Porque? 13. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: Operador Prec. Supr. Añadir Operador Prec. Supr. Añadir

coger(x) en_mesa(x), libre(x), manovacía en_mesa(x), libre(x), manovacía cogido(x) apilar(x,y) cogido(x), libre(y) cogido(x), libre(y) manovacía, sobre(x,y), libre(x)

dejar(x) cogido(x) cogido(x) en_mesa(x), libre(x), manovacía desapilar(x,y) manovacía, libre(x), sobre(x,y) manovacía, libre(x), sobre(x,y) cogido(x), libre(y)

Los predicados con los que se puede describir una escena son: manovacía: La mano del robot esta libre sobre(x,y): El objeto x está sobre el objeto y libre(x): El objeto x no tiene nada encima

cogido(x): El objeto x esta cogido por la mano del robot en_mesa(x): El objeto x esta sobre la mesa

a) Queremos resolver el problema de la figura, pero para ello primero queremos aprender dos operadores, uno llamado despejar(x,y), que quita un bloque de encima de otro y lo deja en la mesa y otro llamado colocar(x,y) que hace la operación inversa, pone un bloque que hay en la mesa encima de otro. Indica las unificaciones de variables que hagas durante el aprendizaje y por que las haces. No simplifiques los operadores despues del aprendizaje.

C

A Estado Inicial

C

A

B

B Estado Final

3 Aprendizaje Basado en Explicaciones

25

b) Una vez aprendidos estos dos operadores aplícalos para resolver el problema de la figura y aprende con el plan un operador que se llame sandwich(x,y,z). ¿Es mas general este operador que el plan original? c) Dados los planes de la tabla, que resuelven el problema de la siguiente figura, ¿Es mas ventajoso uno que el otro? Compáralos respecto al número de pasos primitivos y el número de precondiciones que hay que comprobar, y comenta los resultados. Plan 1 despejar(C,A) despejar(A,B) sandwich(E,A,D) colocar(C,B)

Plan 2 despejar(C,A) despejar(E,D) desapilar(A,B) apilar(A,D) colocar(E,A) colocar(C,B)

C

E

A

E

C

A

B

D

B

D

Estado Inicial

Estado Final

14. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: Operador Prec. Supr. Añadir

apilar(x,y) cogido(x), libre(y) cogido(x), libre(y) manovacía, sobre(x,y), libre(x)

desapilar(x,y) manovacía, libre(x), sobre(x,y) manovacía, libre(x), sobre(x,y) cogido(x), libre(y)

Los predicados con los que se puede describir una escena son: manovacía: La mano del robot está libre sobre(x,y): El objeto x está sobre el objeto y libre(x): El objeto x no tiene nada encima

cogido(x): El objeto x está cogido por la mano del robot en_mesa(x): El objeto x está sobre la mesa

a) Queremos aprender el operador mover(x,y,z) que pasa un bloque de una pila a otra como aparece en la figura:

A

A B

C

Estado Inicial

B

C Estado Final

No hace falta que useis el algoritmo de planificación para hallar el plan, lo podeis hacer a ojo. ¿Es este plan más general que el original? b) Tenemos tambien los operadores despejar(x,y) y colocar(x,y) con la siguiente definición: Operador Prec. Supr. Añadir

despejar(x,y) sobre(x,y), manovacía, libre(x) sobre(x,y), manovacía, libre(x) manovacía, en_mesa(x), libre(x), libre(y)

colocar(x,y) manovacía, en_mesa(x), libre(x), libre(y) manovacía, en_mesa(x), libre(x), libre(y) sobre(x,y), manovacía, libre(x)

26

ÍNDICE GENERAL Ahora queremos aprender el operador intercambiar(x,y,z,w) usando los operadores mover, despejar y colocar. Al generalizar el plan os encontrareis que aparecen múltiples posibilidades a la hora de unificar variables, indicad que posibilidades aparecen, pero escoged las que os parezcan las correctas para el plan que se quiere obtener.

A

D

D

A

B

C

B

C

Estado Inicial

Estado Final

c) ¿Encontrais alguna relación entre las múltiples posibilidades que aparece a la hora de generalizar el plan y el haber usado sólo operadores no primitivos? ¿Que creeis que se ha perdido al utilizar los operadores no primitivos que de alguna manera dificulta la generalización? 15. Tenemos un dominio en el que un camión traslada paquetes de una ciudad a otra, y disponemos de los siguientes predicados y operadores:

camion(c) paquete(p) ciudad(l) en(o,l) carga(c,p) conexion(l1,l2)

op: prec: add: del: op: prec: add: del:

c es un camión p es un paquete l es una ciudad el objeto o esta en el lugar l el camion c carga el paquete p la ciudad l1 conecta con la ciudad l2

cargar(c,p,l) camion(c),paquete(p), ciudad(l),en(c,l),en(p,l) carga(c,p) en(p,l) viajar(c,l1,l2) camion(c),ciudad(l1), ciudad(l2),en(c,l1),conexion(l1,l2) en(c,l2) en(c,l1)

op: prec: add: del:

descargar(c,p,l) camion(c),paquete(p),carga(c,p), ciudad(l),en(c,l) en(p,l) carga(c,p)

a) Dados los problemas de las figuras, generar un plan que los resuelva y crear un nuevo operador con la generalización de los planes:

Pa1

Pa1

Ca1 Ci1

Ca1 Ci2

ciudad(ci1),ciudad(c2),camion(ca1) paquete(pa1),en(ca1,ci1),en(pa1,c2) conecta(ci1,ci2),conecta(ci2,ci1)

Ci1 en(ca1,ci2),carga(ca1,pa1)

Ci2

3 Aprendizaje Basado en Explicaciones

27

Ca1 Pa1 Pa1 Ca1 Ci1

Ci2

Ci1

ciudad(ci1),ciudad(c2),camion(ca1) paquete(pa1),en(ca1,ci1),carga(ca1,pa1) conecta(ci1,ci2),conecta(ci2,ci1)

Ci2

en(ca1,ci2),en(pa1,ci2)

b) Dado este nuevo problema, generar un plan que lo resuelva y crear un nuevo operador con la generalización del plan. ¿Observas alguna particularidad en el plan generalizado?

Ca1

Ca1

Pa1

Pa1

Ci1

Ci2

Ci1

ciudad(ci1),ciudad(c2),camion(ca1) paquete(pa1),en(ca1,ci1),en(pa1,c1) conecta(ci1,ci2),conecta(ci2,ci1)

Ci2

en(ca1,ci2),en(pa1,ci2)

c) Resuelve este nuevo plan con los operadores originales, con los operadores aprendidos en el primer apartado y con el operador aprendido en el segundo apartado. Compara los tres planes obtenidos. Comenta la generalidad y utilidad de los operadores aprendidos. Ca1 Ca1 Ci1

Pa1

Pa1 Ci2

Ci3

ciudad(ci1),ciudad(c2),ciudad(c3) camion(ca1),paquete(pa1) en(ca1,ci1),en(pa1,c1) conecta(ci1,ci2),conecta(ci2,ci1) conecta(ci2,ci3),conecta(ci3,ci2)

Ci1

Ci2

Ci3

en(ca1,ci3),en(pa1,ci3)

16. Tenemos un vector con n posiciones donde en cada una de ellas tenemos una letra, disponemos de un operador que nos permite intercambiar dos posiciones consecutivas del vector definido de la siguiente manera: Operador Prec. Supr. Añadir

swap(x,y,vx,vy) next(x,y), val(x,xv), val(y,vy) val(x,vx), val(y,vy) val(x,vy), val(y,vx)

Los predicados con los que se puede describir una escena son: next(x,y): La posicion y es la siguiente a la x val(x,vx): la posicion x tiene el valor vx

28

ÍNDICE GENERAL a) Genera el plan que lleva del vector de la izquierda al de la derecha utilizando el operador swap (basta con indicar que pasos hacen falta). A B

C

C A

B

Aprende el operador back generalizando el plan generado usando la técnica de EBL utilizada por STRIPS. Indica la tabla triangular inicial justificando que predicados son los relevantes, la tabla generalizada y la tabla restringida con las unificaciones de variables que haces y por que. b) Genera el plan que lleva del vector de la izquierda al de la derecha utilizando el operador swap (basta con indicar que pasos hacen falta). A B

C

C

B A

Aprende el operador mirror generalizando el plan generado usando la técnica de EBL utilizada por STRIPS. Indica la tabla triangular inicial justificando que predicados son los relevantes, la tabla generalizada y la tabla restringida con las unificaciones de variables que haces y por que. c) Dados los planes de la tabla, que resuelven el problema de la figura, ¿Es alguno mas ventajoso uno que el otro? Compáralos respecto al número de pasos primitivos y el número de precondiciones que hay que comprobar, y comenta los resultados. A B

Plan 1 swap(3,4,C,D) swap(2,3,B,D) swap(1,2,A,D) swap(3,4,B,C) swap(2,3,A,C) swap(3,4,A,B)

C

D

Plan 2 back(2,3,4,B,C,D) swap(1,2,A,D) back(2,3,4,A,B,C) swap(3,4,A,B)

D C

B

A

Plan 3 mirror(1,2,3,A,B,C) swap(3,4,A,D) mirror(1,2,3,C,B,D) swap(2,3,B,C)

Plan 4 swap(3,4,C,D) back(1,2,3,A,B,D) mirror(2,3,4,A,B,C)

17. Tenemos un vector con n posiciones donde en cada una de ellas tenemos una letra, disponemos de dos operadores, el primero (swap) nos permite intercambiar dos posiciones consecutivas del vector, el segundo (mirror) nos permite intercambiar dos posiciones separadas una posicion. Estan definidos de la siguiente manera: Operador Prec. Supr. Añadir Operador Prec. Supr. Añadir

swap(x,y,vx,vy) next(x,y), val(x,xv), val(y,vy) val(x,vx), val(y,vy) val(x,vy), val(y,vx) mirror(x,y,z,vx,vz) next(x,y), next(y,z), val(x,xv), val(z,vz) val(x,vx), val(z,vz) val(x,vz), val(z,vx)

Los predicados con los que se puede describir una escena son: next(x,y): La posición y es la siguiente a la x val(x,vx): la posición x tiene el valor vx Aprende el plan [swap(1,2,A,B) → mirror(1,2,3,B,C) → swap(2,3,A,B)] que lleva del vector de la izquierda al de la derecha

3 Aprendizaje Basado en Explicaciones

29 A B C

C B A

Aprende el plan generando un operador con él, usando la técnica de EBL utilizada por STRIPS. Indica la tabla triangular inicial justificando que predicados son los relevantes, la tabla generalizada y la tabla restringida con las unificaciones de variables que haces y por que. 18. Supón que podemos describir escenas del mundo de los bloques que contienen una mano de robot, bloques y una mesa. Estos bloques pueden estar sobre la mesa o sobre otro bloque. Tomemos los siguientes operadores de planificación: Operador Prec. Supr. Añadir

despejar(x,y) sobre(x,y), manovacía, libre(x) sobre(x,y), manovacía, libre(x) manovacía, en_mesa(x), libre(x), libre(y)

colocar(x,y) manovacía, en_mesa(x), libre(x), libre(y) manovacía, en_mesa(x), libre(x), libre(y) sobre(x,y), manovacía, libre(x)

Los predicados con los que se puede describir una escena son: manovacía: La mano del robot esta libre sobre(x,y): El objeto x está sobre el objeto y libre(x): El objeto x no tiene nada encima

cogido(x): El objeto x esta cogido por la mano del robot en_mesa(x): El objeto x esta sobre la mesa

a) Queremos aprender el operador extrae(x,y,z) que quita un bloque de entre otros dos. Indica las unificaciones de variables que hagas durante el aprendizaje y por que las haces. No simplifiques los operadores después del aprendizaje, si el nuevo operador borra algo del estado original y luego lo vuelve a añadir dejalo así. A B

A

C

C

B

b) Una vez aprendido este operador aplícalo (junto con el resto de operadores del dominio) para resolver el problema de la figura y aprende con el plan un operador que se llame malabares(x,y,z,w). A B C

A

C

D

D

B

c) Compara el plan obtenido en el apartado anterior, el operador aprendido con ese plan y el plan [despejar(A,B), despejar(B,C), despejar(C,D), colocar(C,B), colocar(A,D)]. ¿Se obtiene un ahorro respecto al número de pasos primitivos aplicados? ¿Y respecto al número de precondiciones que se han de comprobar? Comenta los resultados.

30

ÍNDICE GENERAL

Cap´ıtulo

4

Aprendizaje por refuerzo 1. Queremos construir un sistema capaz de controlar un proceso con tres estados {Alto, Medio, Bajo} donde se pueden realizar las acciones Aumentar y Disminuir. El siguiente gráfico indica como es la función de cambio de estado (δ) y el refuerzo (r) obtenido por cada acción:

Disminuir, 0

Disminuir, 0 Alto

Bajo

M edio

Aumentar, 100

Aumentar, 0

Supondremos que para entrenar el sistema aprenderemos a partir de tres secuencias de entrenamiento: a) Estado Inicial=Alto, acciones={Disminuir,Aumentar,Disminuir} b) Estado Inicial=Bajo, acciones={Aumentar,Aumentar,Disminuir} c) Estado Inicial=Medio, acciones={Disminuir,Aumentar,Aumentar} ˆ que obtendríamos después de aprender estas tres secuencias mediante el algoritmo Calcula la función Q ˆ paso a paso. de Q-Learning. Muestra la evolución de la función Q 2. Queremos construir un sistema capaz de controlar un proceso con tres estados {A, B, C} donde se pueden realizar las acciones up y down. El siguiente gráfico indica como es la función de cambio de estado (δ) y el refuerzo (r) obtenido por cada acción:

A

up, 100

down, 0 up, 0

up, 25 down, 0

B

C

down, 50

Supondremos que para entrenar el sistema aprenderemos a partir de tres secuencias de entrenamiento: a) Estado Inicial=A, acciones={up,up,up} 31

32

ÍNDICE GENERAL b) Estado Inicial=B, acciones={down,up,down} c) Estado Inicial=C, acciones={down,down,up} ˆ que obtendríamos después de aprender estas tres secuencias mediante el algoritmo Calcula la función Q ˆ de Q-Learning considerando que el valor del parámetro γ es 0.9. Muestra la evolución de la función Q paso a paso. 3. Queremos hacer que un sistema de control aprenda a controlar una válvula que gobierna la presión y la temperatura de un sistema. Consideraremos que la presión y la temperatura pueden tomar los valores alta y baja. De esta manera tenemos cuatro estados definidos por las combinaciones de los valores de estas dos variables. El sistema de control puede hacer dos acciones: Abrir, Cerrar. La función δ de cambio de estado y la funcion r de refuerzo son las del siguiente grafo:

Cerrar, 0 (A, A)

(A, B)

Cerrar, 0

Cerrar,0

Abrir, 50

Abrir, 100

Cerrar, 50

Abrir, 100 (B, A)

(B, B)

Abrir, 0

Supondremos que para entrenar el sistema aprenderemos a partir de tres secuencias de entrenamiento: a) Estado Inicial=(A,A), acciones={cerrar, cerrar, abrir, abrir} b) Estado Inicial=(A,B), acciones={cerrar, cerrar, abrir} c) Estado Inicial=(B,B), acciones={cerrar, abrir} El valor del parámetro γ es de 0.9. 4. Queremos construir un sistema capaz de controlar un proceso que tiene cuatro estados {A, B, C, D} donde podemos realizar las acciones a y b. La siguiente figura muestra la función de transición (δ) y el refuerzo (r) obtenido por cada acción: b, 20

a, 10 A

a, 20 B

C

a, 60 b, 50

b, 50

a, 70

b, 30 D

4 Aprendizaje por refuerzo

33

Usando el algoritmo Q-Learning con γ = 0.9 y α = 1, Using the Q-Learning algorithm with γ = 0.9 and α = 1, Calcula la función acción-valor Q que se obtiene con la secuencia que empieza en el estado A y realiza las acciones {a,a,b,a,b,a}. 5. Queremos construir un sistema capaz de controlar un proceso que tiene cuatro estados {A, B, C, D} donde podemos realizar las acciones a y b. La siguiente figura muestra la función de transición (δ) y el refuerzo (r) obtenido por cada acción: b, 20 b, 50 a, 10 A

a, 20 B

C

a, 60 b, 30 b, 50 a, 70 D

Usando el algoritmo Q-Learning con γ = 0.9 y α = 1, a) Calcula la función acción-valor Q que se obtiene con la secuencia que empieza en el estado A y realiza las acciones {a,b,a,b,b,a} b) Calcula la función acción-valor Q que se obtiene con la secuencia que empieza en el estado A y realiza las acciones {b,b,a,b,a,a}