Examen 2018, preguntas y respuestas PDF

Preview

Summary

Examen 18 de mayo de 2018 APELLIDOS: NOMBRE: Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen Ejercicio 1: [20 puntos: respuesta acertada = +1, respuesta incorrecta = –1]...

Description

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen

Ejercicio 1:

[20 puntos: respuesta acertada = +1, respuesta incorrecta = –1]

Complete las frases que se muestran a continuación con las alternativas especificadas. En la siguiente tabla, indique "V" o "F" para respuestas verdaderas y falsas respectivamente:

(a)

(b)

(c)

(d)

1.1

F

V

V

F

1.2

F

F

V

V

1.3

V

F

F

V

1.4

V

F

V

F

1.5

V

V

F

F

!

Pág. 1 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen

1.1. Sea S un conjunto de estados del mundo. ¿Cuáles de los siguientes elementos forman parte del conocimiento a priori de un agente de búsqueda? (a) Un conjunto potencialmente infinito de estados iniciales S0ÍS (b) Una función expandir: s ! {s1, ..., sn} que asigna un conjunto finito de sucesores siÎS a cada estado sÎS (c) Una función meta?: s ! verdad | falso que determina si un estado sÎS es un estado meta (d) Una función de coste c: s ! r que asigna a cada estado sÎS un número real rÎÂ

1.2. ¿Cuáles de las siguientes afirmaciones acerca de los algoritmos de búsqueda son verdaderas y cuáles son falsas? (a) La búsqueda en amplitud tiene una menor complejidad en tiempo que la búsqueda A* (b) Si h1* y h2* son funciones heurísticas consistentes, entonces h3*(n) = h1*(n) + h2*(n), para todo nodo n, es una función heurística optimista. (c) En el algoritmo A*, si h* es consistente, entonces el valor de f * crece de forma (débilmente) monótona en todos los caminos del árbol de búsqueda. (d) Si h* es optimista, entonces el algoritmo A* es óptimo (ó admisible).

1.3. Sea X = {A,B,C} un conjunto de variables y R = {RA,B, RA,C, RB,C,} un conjunto de restricciones tal que RA,B º (A = B * 2); RA,C º (A > C); y RB,C º (B ¹ C). ¿Con cual(es) de los siguientes conjuntos de dominios D = {DA,DB,DC} se formaría un Problema de Satisfacción de Restricciones (X,D,R) que es arco-consistente? (a) DA = {2,4}; DB = {1,2}; DC = {1,2} (b) DA = {2}; DB = {1}; DC = {3} (c) DA = {4,6}; DB = {2,3}; DC = {3} (d) DA = {2,4,6} DB = {1,2,3}; DC = {1,2,3}

Pág. 2 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen

1.4. ¿Cuáles de las siguientes afirmaciones son verdaderas y cuáles son falsas? (a) En lógica de descripciones ALC: 9r.C u "r.C ´ 9r.> u "r.C (b) En RDF Schema se puede representar: A v B u C (c) En OWL se puede representar: A v B u C (d) Para toda t-norma T se cumple que "x,y T(x,y) ³ Mínimo(x,y)

1.5. ¿Cuáles de las siguientes afirmaciones son verdaderas y cuáles son falsas? (a) Un clasificador binario con una “false positive rate”=0,5 clasifica la mitad de los casos negativos como positivos. (b) Se quiere clasificar imágenes en dos clases, los que presentan algún coche y los que no. Para realizar este problema es apropiado usar un método de aprendizaje SUPERVISADO. (c) Dado una neurona perceptrón con dos entradas binarias y una salida binaria (por activación umbral) como se presenta en la figura. Es posible definir una combinación de pesos (w0, w1,w2) con w0 > 0 y tal que la neurona computa la función booleana AND.

x1

w1

w0 y

w2 x2

(d) Aplicando un árbol de decisión como clasificador, es posible que un mismo ejemplo se clasifica en dos nodos hoja diferentes del mismo árbol.

Pág. 3 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen Ejercicio 2:

[ 25 puntos]

Contemple el siguiente árbol de juego, en cuyas hojas se indica el valor correspondiente de la función de evaluación. Es el turno del jugador Max.

a) En este apartado, asumimos que x1= 5, x2= 9, x3= 7 y x4= 5. Suponiendo que siempre se expanden los sucesores de un nodo de izquierda a derecha, aplique el algoritmo Minimax con poda a- b. Marque con una “X” en el árbol de arriba qué nodos o subárboles se podan (e.d., qué nodos no se visitan). Además, indique en la tabla de abajo cómo van cambiando los valores de a y b de los demás nodos interiores durante la ejecución del algoritmo, así como la mejor jugada para Max.

!

a

b

b

!

!

c

!

!

d

!

!

e

!

!

f

!

!

g

!

!

h

!

!

i

!

!

j

!

!

k

!

!

a

Mejor!jugada:!! Pág. 4 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen b) En este apartado suponemos que las variables x1 y x2 pueden tomar cualquier valor entero. Especifique en el cuadro de abajo las condiciones más débiles (e.d., menos restrictivas) que han de cumplir estas variables, para que no haya podas en el subárbol con raíz en b (p.e.: 1 < x1 < 8 y x2 > 5)

c) En este apartado suponemos que Max juega contra un jugador llamado J, y que J no es nada experto en el juego concreto. Es tal que cuando le toca jugar, siempre elige aleatoriamente entre sus opciones (e.d. cada una de las n jugadas entre las que ha de elegir le parece igual de buena o mala). Suponiendo que Max es consciente de esto, evalúe el árbol de juego de abajo, indicando en cada nodo interior el valor correspondiente (nótese que en este apartado no se pide realizar podas alfa-beta!). Indique también en el árbol de abajo la mejor jugada para Max

Pág. 5 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen

Pág. 6 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen

Ejercicio 3: [15 puntos] Dados los siguientes nombres de conceptos: Pájaro, Gallina, Ave, Ala, Pico, Pluma, Animado y Agua, y los nombres de rol tiene y bebe, representar el siguiente conocimiento en lógica de descripciones ALC (10 puntos) y en lógica de primer orden (5 puntos). 1) 2) 3) 4) 5)

Los pájaros y las gallinas son aves Los pájaros tienen alas y pico Los pájaros sin plumas son animados Los pájaros son aves que sólo beben agua Piolín es un pájaro animado

Solución: 1) Los pájaros y las gallinas son aves Pájaro v Ave Gallina v Ave (otra equivalente: Pájaro t Gallina v Ave) "x(Pájaro(x) ® Ave(x)) "x(Gallina(x) ® Ave(x)) (otra equivalente: "x(Pájaro(x) Ú Gallina(x) ® Ave(x)) 2) Los pájaros tienen alas y pico Pájaro v $tiene.Ala u $tiene.Pico "x(Pájaro(x) ® $y(tiene(x,y) Ù Ala(y)) Ù $z(tiene(x,z) Ù Pico(z)) ) 3) Los pájaros sin plumas son animados Pájaro u ¬$tiene.Pluma v Animado (otra: Pájaro u "tiene.¬Pluma v Animado ) "x(Pájaro(x) Ù ¬$y(tiene(x,y) Ù Pluma(y)) ® Animado(x)) 4) Los pájaros son aves que sólo beben agua Pájaro v Ave u "bebe.Agua "x(Pájaro(x) ® Ave(x) Ù "y(bebe(x,y) ® Agua(y))) 5) Piolín es un pájaro animado (Pájaro u Animado)(Piolín) (otra: {Pájaro(Piolín), Animado(Piolín)} ) Pájaro(Piolín) Ù Animado(Piolín)

Pág. 7 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen Ejercicio 4:

[13 puntos]

a) Dada la t-norma T(x,y) = Max(0, x + y – 1), calcular su t-conorma dual. Si es necesario, tomar como negación N(x) = 1 – x. b) La siguiente figura muestra el conjunto borroso que representa el valor poco de la variable tiempo de realización de un ejercicio. TIEMPO Poco 1

min 0 0

5

10

15

20

25

Suponiendo que Ana tarda 6 minutos y Pedro 17 minutos en hacer el ejercicio, obtener el grado de verdad de las siguientes expresiones: b1) Ana tarda muy poco pero Pedro tarda mucho b2) Si Ana tarda poco Pedro no tarda mucho En caso de que sea necesario utilizar las funciones de Lukasiewicz: • T-norma = W(x,y) = Max(0, x + y – 1) • T-conorma = W*(x,y) = Min(1, x + y) • Implicación = J(x,y) = Min(1,1 – x + y) Solución: a) Si T es una t-norma y N es una negación fuerte entonces T*(r,s) = N(T(N(x),N(x))) es una t-conorma que se denomina t-conorma dual de T. En el caso del ejercicio: T*(x,y) = N(T(N(x),N(y))) = 1 – T(1 – x, 1 – y) = 1 – Max(0, 1 – x + 1 – y – 1) = = Min(1 – 0, 1 – (1 – x + 1 – y – 1)) = Min(1, x + y) Obsérvese que 1 – Max(a, b) = Min(1 – a, 1 – b) b) b1) Ana tarda muy poco pero Pedro tarda mucho µPoco(6) = 0.8 µMuy Poco(6) = µPoco(6)2 = 0.82 = 0.64 µMucho(17) = µPoco(25 – 17) = µPoco(8) = 0.4 µMuy Poco Ù Mucho(6,17) = T(µMuy Poco(6), µMucho(17)) = T(0.64, 0.4) = = Máx(0, 0.64+0.4 – 1) = 0.04 b2) Si Ana tarda poco Pedro no tarda mucho µ¬Mucho(17) = 1 – µMucho(17) = 1 – 0.4 = 0.6 µPoco® ¬Mucho(6,17) = J(µPoco(6), µ¬Mucho(17)) = J(0.8,0.6) = Mín(1, 1 – 0.8 + 0.6) = 0.8 Pág. 8 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen Ejercicio 5:

[20 puntos]

Considera un agente que se encuentra en un entorno modelado por un proceso de decisión de Markov determinista como se presenta en la siguiente figura:

E

P 0

E

V 0

O S

S

N T -50

O

R 50

O

U 90

Los estados del problema son P, V, R, T y U, y las acciones que el agente puede realizar son movimientos al sur (S), oeste (O), norte (N) y este (E), según indicado en la figura. Cuando el agente llega a un nuevo estado recibe las recompensas que se indican en cada caso. Supón que el agente no conoce el entorno (aunque sí sabe que es determinista) y que quiere aprender la política óptima aplicando el algoritmo Q-learning con los siguientes parámetros: • El agente arranca en el estado V • Inicialización de los valores de la función Q en 0 • factor de descuento g=1 • El agente siempre elige la acción de mayor valor Q y en caso de empate elige según el siguiente orden: E, S, N, O. Sin embargo, la segunda vez que el agente esté en el estado V, elige la acción S para explorar (sea cual sea el valor Q de las diferentes acciones disponibles en este momento). a) Realiza 11 movimientos del agente, indicando la secuencia de los estados recorridos, así como la evolución de los valores de la función Q. b) Especifica la política que el agente haya aprendido después de los 11 movimientos.

Pág. 9 / 10

Examen 18 de mayo de 2018

APELLIDOS:

NOMBRE:

Duración: 1 hora 50 mins No se permiten móviles, libros, apuntes, ni calculadora Realice los ejercicios en hojas separadas No se levante del asiento salvo para entregar el examen Solución: a) El agente aplica el algoritmo Q-learning: de

Ac.

a

V

E

R

R

O

V

V

S

U

U

O

T

T

N

P

P

E

V

V

S

U

U

O

T

T

N

P

P

E

V

V

E

R

Q*(V,E)

Q*(V,S)

Q*(V,O) Q*(R,O)

0

0

0

50

0

Q*(U,O)

Q*(T,N)

Q*(P,E)

Q*(P,S)

0

0

0 50

90

0 -50

0 0

90 40 -50 90 50 100

b) La política aprendida es la siguiente

Ejercicio 6:

Estado

P

V

R

U

T

p

E

E

O

O

N

[7 puntos]

Especifica una neurona perceptrón (incluyendo sus pesos) con 3 entradas y salida binarias y función de activación umbral, que calcula la siguiente función lógica: La neurona se activa si y sólo si la entrada 1 y/o la entrada 2 tienen valor 1 y la entrada 3 tiene valor 0. Solución: -0,2 E1

0,3 Y

E2 E3

0,3 -1

Pág. 10 / 10...