• Author / Uploaded
• Danilo Savedra Savedra

• Categories
• Red Bayesiana
• Probabilidad
• Variable aleatoria
• Algoritmos
• Red neuronal artificial

Citation preview

Inteligencia Artificial II (Curso 2007-2008) Ejercicios propuestos Ejercicio 1: En la Delegaci´on de Alumnos de una Escuela de Ingenier´ıa Inform´atica se plantean encontrar un m´etodo para predecir si una asignatura va a tener un n´ umero de aprobados superior al 70%, de manera que sirva para ayudar a decidir a sus compa˜ neros a la hora de matricularse. Deciden que esencialmente son cuatro los factores que influyen en el mayor o menor n´ umero de suspensos: ˆ Existencia de evaluaci´ on alternativa. ˆ Porcentaje de repetidores superior al 20%.

´cticas obligatorias. ˆ Pra ˆ Contenido principalmente matem´ atico, de programaci´ on o de hardware.

Deciden para ello aplicar alg´ un algoritmo de aprendizaje sobre un conjunto de 12 ejemplos de asignaturas de a˜ nos anteriores. Estos ejemplos se muestran en la siguiente tabla: Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12

Alternativa si si no si si si si no no no no si

Repetidores no si si si si no no si no si si no

´cticas Pra si si no no si no si no no si no si

Contenido programaci´ on programaci´ on programaci´ on programaci´ on matem´ atico matem´ atico matem´ atico matem´ atico hardware hardware hardware hardware

Aprobados si no no no no si si no no no no si

ˆ ¿Qu´e conjunto de reglas aprender´ıan si aplicaran el algoritmo de cobertura? Detallar todos los pasos realizados para aprender reglas tanto para Aprobados=si como para Aprobados=no. ˆ ¿Qu´e concepto aprender´ıan si aplicaran el algoritmo FIND-S? (suponiendo las hip´ otesis representadas como conjunci´ on de restricciones de la forma Atributo=valor) ¿Es el mismo que el aprendido en el apartado anterior? ˆ ¿Cu´ al es el sesgo inductivo en los dos algoritmos anteriores? ˆ Supongamos que se aplica el algoritmo de cobertura sobre un conjunto de entrenamiento an´ alogo al anterior, pero en el que cada ejemplo est´ a clasificado justo al rev´es (por ejemplo, el ejemplo 11 ser´ıa positivo y el 12 negativo) ¿Qu´e conjunto de reglas se aprender´ıa? ¿Representar´ıan el mismo concepto que el que aprender´ıa el algoritmo FIND-S (representando las hip´otesis como conjunci´ on de restricciones de la forma Atributo=valor)? Responder a estas dos preguntas de manera razonada, sin aplicar los correspondientes algoritmos.

Ejercicio 2: La siguiente tabla muestra las preferencias de una familia a la hora de decidir la compra de una segunda vivienda en el mercado de viviendas usadas, en funci´ on de determinadas caracter´ısticas: si est´ a en el campo o en la playa, la distancia a la primera vivienda, el color de la fachada, la d´ ecada en que fue construida y si se trata de un piso o una casa: Ejemplo E1 E2 E3 E4 E5

´n Situacio playa playa playa campo playa

Distancia cerca medio medio lejos cerca

Color blanco verde blanco rojo amarillo

1

D´ ecada ochenta setenta noventa ochenta ochenta

Tipo piso casa piso piso piso

Comprar si no si no si

Suponiendo que el espacio de hip´ otesis es el de aquellas expresables mediante conjunci´ on de restricciones de la forma Atributo=valor, aplicar (detallando cada uno de los pasos realizados) el algoritmo de eliminaci´ on de candidatos usando como entrada la tabla anterior. Seg´ un lo aprendido ¿qu´e tipo de vivienda se est´ a intentando comprar? Ejercicio 3: (Mitchell, ej. 2.3) Consideremos la tarea de aprendizaje consistente en decidir si ir a practicar nataci´ on a partir de los valores de ciertos atributos meteorol´ogicos, para lo que contamos con la siguiente tabla de datos: Ejemplo E1 E2 E3 E4

Cielo soleado soleado lluvia soleado

Temperatura templada templada fr´ ıa templada

Humedad normal alta alta alta

Viento fuerte fuerte fuerte fuerte

´n Previsio igual igual cambio cambio

Agua templada templada templada fr´ ıa

HacerDeporte s´ ı s´ ı no s´ ı

Sea H el espacio de hip´ otesis expresables mediante conjunci´ on de restricciones de la forma Atributo=valor, representadas de la siguiente forma: hsoleado, templada, ?, fuerte, ?, ?i. Esta hip´otesis acepta cualquier instancia en la que los atributos Cielo, Temperatura y Viento, tomen respectivamente los valores soleado, templada y fuerte. Consideremos un nuevo espacio de hip´ otesis H ′ formado por las disyunciones de pares de elementos de H, por ejemplo h?, templada, alta, ?, ?, ?i ∨ hsoleado, ?, alta, ?, ?, iguali Aplicar (detallando cada uno de los pasos realizados) el algoritmo de eliminaci´ on de candidatos con el espacio de hip´otesis H ′ , usando la secuencia de ejemplos de entrenamiento de la tabla anterior. Ejercicio 4: Consideremos el problema de caracterizar el perfil del comprador de un nuevo modelo de tienda de campa˜ na ´ n y Utilidad, que en funci´ on de 5 atributos: Altura, nivel de Estudios, Ingresos, grado de Ocupacio pueden tomar 3 valores cada uno: bajo, medio y alto. Consideremos las hip´ otesis expresadas de la forma hA, E, I, O, U i, donde A, E, I, O y U son, respectivamente, subconjuntos (pueden ser vac´ıos) del conjunto de valores que pueden tomar los atributos Altura, Estudios, ´ n y Utilidad. Cada una de estas hip´otesis representa un concepto en el que las instancias Ingresos, Ocupacio positivas son aquellas en las que los atributos toman, respectivamente, un valor de los incluidos en los conjuntos A, E, I, O y U . As´ı, una instancia positiva en el concepto representado por hA, E, I, O, U i es cualquier instancia ha, e, i, o, ui con a ∈ A, e ∈ E, i ∈ I, o ∈ O y u ∈ U . Se pide: ˆ Consideremos la hip´ otesis h = h{bajo, alto}, {bajo}, {medio}, {alto}, {bajo, medio}i. Enumera todas las instancias positivas en el concepto representado por h. Da un ejemplo de hip´otesis m´as espec´ıfica que h, un ejemplo de hip´ otesis m´as general que h y un ejemplo de hip´otesis que no sea comparable con h (ni m´as general, ni m´as espec´ıfica). ˆ ¿Cu´ antos conceptos hay?, ¿y cu´ antas hip´otesis? Si usamos este espacio de hip´otesis en el algoritmo de eliminaci´ on de candidatos, ¿existe sesgo en el lenguaje? ˆ Consideremos los siguientes ejemplos:

Ejemplo E1 E2 E3 E4

Altura medio alto alto medio

Estudios medio medio alto bajo

Ingresos alto bajo alto alto

´n Ocupacio medio alto alto bajo

Utilidad medio medio bajo alto

Comprador no si no si

Calcula la cota general y la cota espec´ıfica del espacio de versiones consistente con estos ejemplos. Para ello se ha de aplicar el algoritmo de eliminaci´ on de candidatos considerando las instancias en el orden en que se presentan en la tabla. Ejercicio 5: Consideremos el conjunto de instancias X = {1, 2, 3, 4, 5, 6, 7, 8, 9} y el siguiente espacio de hip´otesis: H = {h[x,y]|x, y ∈ X ∧ x ≤ y ∧ |x − y| < 4} 2

siendo h[x,y] = {n ∈ X|x ≤ n ≤ y}. Por ejemplo, h[2,5] = {2, 3, 4, 5} ∈ H. Dadas dos hip´otesis, h1 y h2 , h1 es m´as general que h2 si y s´ olo si h2 ⊆ h1 . Se pide aplicar, detallando cada paso, el algoritmo de eliminaci´ on de candidatos para encontrar, a partir del conjunto de entrenamiento D = {1− , 3+ , 7− , 4+ }, el conjunto de hip´otesis consistentes con dicho conjunto de entrenamiento. Indicar en cada momento el valor de la cota general y la cota espec´ıfica. Enumerar todos los elementos del espacio de versiones correspondiente al conjunto de entrenamiento D. Con lo aprendido por el algoritmo ¿c´ omo se clasificar´ıan las instancias 5, 2 y 9? Justificar las respuestas. Ejercicio 6: Consideremos el conjunto de instancias formado por los n´ umeros naturales y el siguiente espacio de hip´otesis: H = {Mk : 1 ≤ k ≤ 10}

donde Mk es el conjunto de los n´ umeros naturales m´ ultiplos de k. Se pide:

ˆ ¿Cu´ ales son las cotas general y espec´ıfica del espacio de hip´otesis? ˆ ¿Cu´ ales son todas las relaciones entre los elementos del espacio de hip´otesis con respecto al orden de generalidad? ˆ Aplicar, detallando cada paso, el algoritmo de eliminaci´ on de candidatos para encontrar, a partir del conjunto de entrenamiento D = {24+ , 84+ , 5− , 2− , 8− }, el conjunto de hip´otesis consistentes con dicho conjunto de entrenamiento. Indicar en cada momento el valor de la cota general y la cota espec´ıfica.

Ejercicio 7: Unos bi´ologos que exploraban la selva del Amazonas han descubierto una nueva especie de insectos, que bautizaron con el nombre de lepistos. Desgraciadamente, han desaparecido y la u ´ nica informaci´on que disponemos del nuevo insecto viene dada por el siguiente conjunto de ejemplos encontrados en un cuaderno de notas, en los que se clasifican una serie de muestras de individuos en funci´ on de ciertos par´ ametros como su color, el tener ˜o y su velocidad: alas, su taman Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10

Color negro amarillo amarillo blanco negro rojo rojo negro negro amarillo

Alas si no no si no si si no si si

˜o Taman peque~ no grande grande medio medio peque~ no peque~ no medio peque~ no grande

Velocidad alta media baja alta alta alta baja media media media

Lepisto si no no si no si no no no no

Contestar a las siguientes cuestiones: ˆ ¿Cu´ al es la entrop´ıa del conjunto de ejemplos, respecto a la clasificaci´ on de los mismos que realiza el atributo Lepisto? ˆ ¿Qu´e atributo proporciona mayor ganancia de informaci´ on? ˆ Aplicar (detallando cada uno de los pasos realizados) el algoritmo ID3 para encontrar, a partir de este conjunto de entrenamiento, un ´ arbol que nos permita decidir si un determinado individuo es un lepisto o no. ˆ Obtener un conjunto de reglas a partir del ´ arbol obtenido en el apartado anterior. ˆ Seg´ un el concepto aprendido, ¿hay alg´ un atributo que sea irrelevante para decidir si un individuo es un lepisto?

Ejercicio 8: Una entidad bancaria concede un pr´estamo a un cliente en funci´ on de una serie de par´ ametros: su edad (puede ser joven, mediano o mayor), sus ingresos (altos, medios o bajos), un informe sobre su actividad financiera (que puede ser positivo o negativo) y, finalmente, si tiene otro pr´ estamo a su cargo o no. La siguiente tabla presenta una serie de ejemplos en los que se especifica la concesi´on o no del pr´estamo en funci´ on de estos par´ ametros: 3

Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14

Edad joven joven mediano mayor mayor mayor mediano joven joven mayor joven mediano mediano mayor

Ingresos altos altos altos medios bajos bajos bajos medios bajos medios medios medios altos medios

Informe negativo negativo negativo negativo positivo positivo positivo negativo positivo positivo positivo negativo positivo negativo

´stamo Otro pre no si no no no si si no si no si si no si

Conceder no no si si si no si no si si si si si no

Supongamos que modificamos el algoritmo ID3 de manera que el criterio para obtener el “mejor” atributo que clasifica un conjunto de ejemplos es el de menor ganancia de informaci´on. En esta situaci´ on se pide: ˆ En caso de ausencia de ruido, ¿obtendr´ıa el algoritmo modificado un ´ arbol de decisi´on consistente con los ejemplos del conjunto de entrenamiento?, justifica la respuesta. ˆ ¿Qu´e sesgo tendr´ıa el algoritmo modificado y de qu´e tipo ser´ıa?, justifica la respuesta. ˆ Aplicar (detallando cada uno de los pasos realizados) el algoritmo modificado para encontrar, a partir de este conjunto de entrenamiento, un ´ arbol que nos permita decidir sobre la concesi´on de pr´estamos.

Ejercicio 9: Aplicar el algoritmo ID3 para construir un ´arbol de decisi´on consistente con los siguientes ejemplos, que nos ayude a decidir si comprar o no un CD nuevo. Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10

Cantante Queen Mozart Anastacia Queen Anastacia Queen Wagner Anastacia Queen Mozart

´fica Discogra Emi Emi Coraz´ on Sony Coraz´ on Sony Sony Coraz´ on Emi Sony

G´ enero rock cl´ asico soul rock soul rock cl´ asico soul rock cl´ asico

Precio 30 40 20 20 30 30 30 30 40 40

Tienda Mixup Virgin Virgin Virgin Mixup Virgin Mixup Virgin Virgin Mixup

Comprar si no si si si si no no no si

Considerar los siguientes ejemplos como conjunto de prueba y obtener la medida de rendimiento del ´arbol obtenido. Ejemplo E11 E12 E13 E14 E15 E16

Cantante Queen Anastacia Queen Anastacia Queen Mozart

´fica Discogra Emi Coraz´ on Sony Coraz´ on Sony Sony

G´ enero rock soul rock soul rock cl´ asico

Precio 30 20 20 30 40 40

Tienda Virgin Virgin Virgin Virgin Virgin Mixup

Comprar si no no no no si

Ejercicio 10: En una empresa se ha decidido usar el algoritmo ID3 para decidir si se lanza al mercado un determinado producto, en funci´ on de los siguientes factores: la utilidad del producto, el coste de la producci´on, el beneficio previsto y la fiabilidad del mismo. Los ejemplos que usan para construir el ´arbol de decisi´on se muestran en la siguiente tabla:

4

Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14 E15 E16 E17

Utilidad si no no si si si no no si si no si si si si si no

Fiabilidad si si no no si no no si no si no si no si si no si

Beneficio baja alta baja baja alta baja alta alta baja baja alta baja alta alta alta alta alta

Coste alto bajo bajo alto alto bajo bajo bajo alto bajo alto bajo alto bajo alto bajo bajo

Mercado no si no no si no no si no no no no si si si si si

Se pide: ˆ Construir el ´ arbol de decisi´on usando el algoritmo ID3 y expresar las condiciones que ha de cumplir un producto para ser lanzado al mercado ¿Hay atributos irrelevantes? ¿por qu´e? ˆ Expresar el resultado obtenido en el apartado anterior en forma de reglas. ˆ ¿Se pueden deducir las siguientes afirmaciones del ´ arbol aprendido?:

– Si el coste de un producto de utilidad es alto y el beneficio previsto es alto entonces se lanza al mercado. – No se lanza al mercado ning´ un producto cuyo beneficio previsto sea bajo. – Si el coste de un producto es bajo entonces s´ olo se lanza al mercado si es de utilidad y el beneficio previsto es alto. Ejercicio 11: Una empresa de material deportivo quiere hacer un estudio de mercado para encontrar las caracter´ısticas principales de sus potenciales clientes. En una primera fase, las caracter´ısticas a estudiar son las siguientes: la edad (joven o adulto), ser deportista profesional, el nivel de ingresos (altos, medios o bajos) y el sexo. Para ello, se realiza un cuestionario a 21 personas, obteniendo los resultados que se reflejan en la siguiente tabla: Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14 E15 E16 E17 E18 E19 E20 E21

Edad joven joven joven joven joven adulto adulto adulto adulto adulto adulto adulto adulto joven joven adulto adulto joven joven adulto joven

Profesional si si no si no si no si no si no si no si si no no no no si si

Ingresos bajos altos altos bajos medios altos altos altos medios bajos medios medios altos altos medios medios bajos medios bajos medios medios 5

Sexo hombre hombre mujer mujer mujer hombre mujer mujer mujer mujer mujer hombre hombre mujer hombre hombre hombre hombre mujer mujer mujer

Interesado si si no si no no no no no no no no si si si no no no no no si

Se pide: ˆ Aplicar el algoritmo ID3 (desarroll´ andolo paso a paso) para obtener un ´arbol de decision que sirva para decidir si un cliente potencial est´ a interesado o no en el producto que ofrece la empresa. Tomar como conjunto de entrenamiento los primeros 15 ejemplos de la tabla. ˆ Tomando ahora como conjunto de prueba los ejemplos del 16 al 21 de la tabla, calcular el rendimiento del ´arbol de decisi´on obtenido en el apartado anterior. Usando ese conjunto de prueba, aplicar un proceso de podado a posteriori sobre el ´ arbol de decisi´on. Expresar mediante reglas el ´arbol obtenido tras la poda ¿Qu´e rendimiento tiene este ´ arbol sobre el conjunto de prueba? ¿Y sobre el conjunto de entrenamiento?

Ejercicio 12: Una empresa de contactos en Internet tiene la costumbre de ayudarse de un ´arbol de decisi´on espec´ıfico para cada persona que acude a ellos en busca de pareja, con idea de usar este ´arbol de decisi´on para proponer al cliente determinadas personas con las que podr´ıa congeniar. Para ello, a cada nuevo cliente le ense˜ nan una muestra aleatoria de candidatos de su base de datos y para cada uno de ellos el cliente se˜ nala si en principio es de su agrado o no. Por simplificar supondremos que las caracter´ısticas que definen a un posible candidato son: Color del pelo (rubio o moreno), edad (joven, media o madura), nivel de estudios (primarios, medios o ´ n causada por su carta de presentaci´on (buena o mala), si es fumador y si vive en la superiores), impresio misma ciudad. En un caso concreto, las respuestas de un cliente ante una muestra de 18 candidatos se resumen en la siguiente tabla: Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14 E15 E16 E17 E18

Pelo moreno moreno moreno moreno moreno moreno moreno moreno rubio rubio rubio rubio rubio rubio rubio rubio rubio rubio

Edad joven joven joven madura madura media media media joven joven joven joven madura madura madura madura media media

Estudios medios medios primarios medios primarios medios primarios superiores medios medios medios superiores primarios superiores superiores superiores superiores superiores

´n Impresio buena mala buena buena mala mala buena buena buena mala mala buena buena mala mala mala mala mala

Fumador no si no no no no no no si no no no no no si si no no

Misma ciudad si si si si si no si no si no si si si no no si no si

Agrada si no no si si no si si no no si no si no no no no no

Aplicar el algoritmo ID3 (detall´ andolo paso a paso) para obtener un ´arbol de decisi´on que sirva para decidir si un candidato potencial debe ser presentado a ´este cliente. Ejercicio 13: La siguiente tabla muestra una serie de datos acerca de ejemplos de personas que han sufrido quemaduras ´ n o no. solares, junto con los datos acerca de su color de pelo, su altura, su peso y si usaban proteccio Ejemplo E1 E2 E3 E4 E5 E6 E7 E8

Pelo rubio rubio moreno rubio rojo moreno moreno rubio

Altura medio alto bajo bajo medio alto medio bajo

Peso bajo medio medio medio alto alto alto bajo

´n Proteccio no si si no no no no si

Quemadura si no no si si no no no

Aplicar (detallando cada uno de los pasos realizados) el algoritmo de cobertura para encontrar, a partir de este conjunto de entrenamiento, un conjunto de reglas que nos permita decidir situaciones en las que se 6

producir´a quemadura solar. Seg´ un lo aprendido ¿hay alg´ un atributo irrelevante para decidir si se producir´a quemadura solar? Ejercicio 14: La siguiente tabla muestra ejemplos de situaciones en las que comprar o no un ordenador, en funci´ on de su precio (alto, medio o bajo), su procesador (AMD o Intel), si tiene tarjeta ethernet y si el monitor es TFT (se supone que el resto de caracter´ısticas es com´ un). Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14 E15 E16

Precio alto alto alto alto alto alto medio medio medio medio medio bajo bajo bajo bajo bajo

Ethernet si si si si no no si si no no no si si no no no

Procesador AMD AMD Intel Intel AMD Intel AMD AMD AMD Intel Intel AMD Intel AMD AMD Intel

TFT si no si no no no si no si si no si no si no si

Comprar no no no no no no si si si no no no si no si no

Aplicar (detallando cada uno de los pasos realizados) el algoritmo de cobertura para encontrar, a partir de este conjunto de entrenamiento, un conjunto de reglas permita decidir sobre la compra de un ordenador, tanto afirmativa como negativamente. Seg´ un las reglas aprendidas ¿deber´ıamos comprar un ordenador con monitor TFT si el precio es bajo? ¿hay alg´ un atributo irrelevante? Ejercicio 15: La siguiente tabla muestra informaci´ on sobre si un alumno aprueba o no la asignatura de IA2, en funci´ on de su nota en la asignatura de L´ ogica Inform´atica (LI), si tiene internet en casa, si usa la bibliograf´ıa ´ n preferida: recomendada y de su aficio Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13 E14

LI sobresaliente aprobado aprobado sobresaliente notable aprobado notable sobresaliente sobresaliente notable notable aprobado notable aprobado

Internet si si si no si si no no si si no no si no

Bibliograf´ıa no no si si si si si no si no no si no no

´n Aficio cine m´ usica deporte deporte deporte m´ usica m´ usica m´ usica cine cine cine deporte m´ usica m´ usica

IA2 si si si si si si si si si no no no no no

Aplicar (detallando cada uno de los pasos realizados) el algoritmo de cobertura para encontrar, a partir de este conjunto de entrenamiento, un conjunto de reglas que nos permita decidir si un determinado alumno va a aprobar la asignatura IA2 o no. Ejercicio 16: Consid´erese el siguiente conjunto de entrenamiento, que describe bajo qu´e situaciones tomar la decisi´on de comprar un billete de avi´ on o no, dependiendo de su precio, la clase en la que se viaje y si la compa˜ n´ıa opera por internet.

7

Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12

Precio alto alto alto alto medio medio medio medio bajo bajo bajo bajo

Clase preferente preferente turista turista preferente preferente turista turista preferente preferente turista turista

Internet no si no si no si no si no si no si

Comprar no no no no si no si no si no si no

Se pide: ˆ Aplicar el algoritmo de cobertura para obtener un conjunto de reglas que ayuden a decidir en la compra del billete de avi´ on. ˆ A la vista de los resultados, ¿existe alg´ un atributo que sea irrelevante a la hora de tomar la decisi´on?

Ejercicio 17: Una asociaci´ on juvenil de geolog´ıa propone a sus miembros una excursi´ on a Sierra M´ agina (Ja´en) para buscar restos de meteoritos. Para distinguirlos de las dem´ as piedras se tienen en cuenta diferentes factores entre los que se encuentran los siguientes: la presencia de corteza de fusi´ on (el color de su superficie), la densidad, el magnetismo y la apariencia interior (met´ alica, cristalina o p´ etrea). Una vez recogidas las muestras, el Museo de Geolog´ıa de Sevilla determina cu´ ales son restos de meteoritos y cu´ ales no. Los datos se recogen en la siguiente tabla: Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10

Color negro blanco blanco gris negro marr´ on marr´ on negro negro blanco

Densidad alta baja baja alta baja alta alta baja alta alta

Magnetismo alto bajo bajo medio medio alto alto medio alto bajo

Interior met´ alico p´ etreo cristal met´ alico met´ alico met´ alico cristal p´ etreo p´ etreo p´ etreo

Meteorito si no no si no si no no no no

Se pide: ˆ Aplicar el algoritmo de cobertura para obtener un conjunto de reglas que ayuden a decidir si una muestra es un resto de meteorito o no. ˆ Aplicar el algoritmo ID3 para obtener un ´ arbol de decisi´on que igualmente nos ayude a decidir si una muestra es un resto de meteorito o no. ˆ A la vista de los resultados, ¿existe alg´ un atributo que sea irrelevante a la hora de tomar la decisi´on? ˆ Extraer un conjunto de reglas a partir del ´ arbol construido por el algoritmo ID3 ¿es el mismo conjunto de reglas que el obtenido en el primer apartado?

Ejercicio 18: La siguiente tabla muestra informaci´ on sobre setas, indicando si son comestibles o no en funci´ on de algunas ˜o del pie, la forma del sombrero, el entorno en el que se presenta y la caracter´ısticas: el color, el taman forma en que se agrupa con otras setas:

8

Ejemplo E1 E2 E3 E4 E5 E6 E7 E8 E9 E10

Color rojo blanco rojo blanco marr´ on rojo marr´ on marr´ on blanco rojo

˜o Taman mediano grande peque~ no peque~ no grande grande mediano mediano mediano peque~ no

Forma plana plana plana c´ oncava convexa c´ oncava convexa plana convexa convexa

Entorno pinar pinar pradera cueva pinar cueva pradera pinar pinar cueva

´n Agrupacio aislada racimo racimo grupo grupo grupo aislada racimo aislada grupo

Comestible si si si si si no no no no no

Se pide: ˆ Aplicar (detallando cada uno de los pasos realizados) el algoritmo de cobertura para encontrar, a partir de este conjunto de entrenamiento, un conjunto de reglas que nos permita clasificar nuevas instancias. Obtener las reglas para clasificar tanto instancias positivas como negativas. Seg´ un lo aprendido ¿hay alg´ un atributo irrelevante para realizar esta clasificaci´ on? ˆ Clasificar las siguientes instancias utilizando el conjunto de reglas aprendido:

I1 I2 I3 I4

Color blanco rojo marr´ on rojo

˜o Taman peque~ no mediano mediano mediano

Forma c´ oncava plana plana c´ oncava

Entorno pradera cueva pinar pinar

´n Agrupacio racimo aislada racimo grupo

Ejercicio 19: Consid´erese el siguiente problema de programaci´on l´ ogica inductiva: Ejemplos positivos: p(a,1) p(b,2) p(3,c) Ejemplos negativos: p(1,1) p(a,b) Conocimiento base: q(a) q(b) q(c) r(1) r(2) r(3) Se pide: ˆ Aplicar el algoritmo FOIL para aprender una definici´ on del predicado p. Nota: Usar la frecuencia relativa como criterio para decidir en cada caso el mejor literal. ˆ ¿Es posible que el algoritmo FOIL, aplicado a este problema, devuelva como resultado la siguiente (y u ´ nica) regla: p(X,Y) :- q(X),r(Y)? ¿Y si en el problema quitamos p(3,c) como ejemplo positivo y a˜ nadimos p(c,3) como ejemplo negativo? Justificar las respuestas.

Ejercicio 20: Consid´erese el siguiente problema de programaci´on l´ ogica inductiva: Ejemplos positivos: q(a,d) q(a,c) q(c,b) q(b,d) q(d,b) Ejemplos negativos: q(a,b) q(c,d) q(d,d) Conocimiento base: h(a) h(b) m(c) m(d) r(a,b) r(c,d) Supongamos que el algoritmo FOIL aplicado a este problema se encuentra en el bucle interno, con la regla q(X,Y) :- h(X)., parcialmente construida. ¿Incluir´ a esta regla en el conjunto de reglas a devolver o continuar´ a a˜ nadiendo condiciones? Si es as´ı: ¿cu´ ales son los posibles literales candidatos a ser a˜ nadidos y cu´ al se elegir´a? Una vez completada esta regla ¿ser´ a la u ´ nica regla que devuelva el algoritmo como salida? Justificar todas las respuestas. Ejercicio 21: Supongamos que queremos aprender el concepto de casilla amenazada por una reina en el ajedrez. Para ello queremos encontrar mediante el algoritmo FOIL un conjunto de reglas, de la forma: amenazada(X, Y ) : −??? que lo definan. En particular, queremos aprender este concepto a partir de los ejemplos que nos suministra el tablero de la figura y disponemos de dos predicados en el conocimiento base: 9

ˆ Reina(X, Y ), es decir Hay una reina en la casilla (X, Y ) (en este caso, sabemos que Reina(1, 2)). ˆ Dif Ab(X, Y, Z), es decir |X − Y | = Z (en este caso, sabemos restar y calcular valor absoluto).

# #

R # # #

# #

# #

Se pide: ˆ Los conjuntos E+ y E− de ejemplos positivos y negativos del concepto. ˆ El conjunto de reglas generados por el algoritmo FOIL si s´ olo tuvi´eramos Reina(1, 2) en el conocimiento base. Indicando los ejemplos positivos que quedar´ıan por cubrir. ˆ Considerando ahora todo el conocimiento base, decir los casos positivos, de entre los anteriores, que cubrir´ıa la regla: amenazada(X, Y ) : −Dif Ab(X, U, Z), Reina(U, V ) ˆ Completar la regla anterior, con el mejor de los tres literales que siguen: Dif Ab(Y, U, Z), Dif Ab(Y, V, Z), Dif Ab(X, X, X)

Ejercicio 22: En una m´aquina expendedora de “huevos sorpresa”, unos huevos est´ an pintados de rojo y otros de azul. El 40% de los huevos de la m´aquina contienen sorpresa y el resto no contiene nada. El 30% de los huevos que contienen sorpresa est´ a pintado de azul, y el 10% de los huevos que est´ an vac´ıos son azules. Si ha tocado un huevo azul ¿Cu´al es la probabilidad de que tenga sorpresa? Ejercicio 23: Consid´erese el siguiente test para saber si un ni˜ no peque˜ no ser´ a diestro o zurdo, se le tumba boca arriba y se mira hacia donde gira la cabeza. La predicci´ on que realiza el test es que ser´ a diestro si gira la cabeza a la derecha y zurdo si la gira hacia la izquierda. Suponiendo que el test acierta en el 90% de las veces y que el 90% de la poblaci´ on es diestra, calcular la probabilidad de que un ni˜ no que gira la cabeza hacia la izquierda sea diestro. Repetir el calculo suponiendo que el test acierta en el 80% de los casos. Ejercicio 24: Supongamos que un d´ıa vas por la calle y crees reconocer a una famosa actriz. Piensas que es bastante improbable que sea realmente ella; es m´as, calculas que existe s´ olo un 5% de posibilidades de que sea realmente ella. As´ı que decides preguntarle directamente, aunque piensas que existe la posibilidad (que calculas es del 50%) de que quiera pasar desapercibida y que a´ un siendo realmente ella, te conteste que no lo es. Incluso piensas que podr´ıa no ser realmente ella y que te respondiese que s´ı lo es (y cifras esa posibilidad en el 10% de los casos). Cuando le preguntas si es la famosa actriz, ella te responde que s´ı, que efectivamente lo es ¿Qu´e probabilidad existe de que efectivamente lo sea? Justificar los c´ alculos realizados. Ejercicio 25: (Russell & Norvig, ej. 13.11) Supongamos que tenemos una bolsa que contiene n monedas, de las cuales sabemos que hay n − 1 normales (con cara y cruz) y una falsa que tiene caras en ambos lados. ˆ Supongamos que extraemos una moneda de la bolsa aleatoriamente, y que la lanzamos, obteniendo cara ¿Cu´al es la probabilidad (condicional) de que la moneda escogida sea la moneda falsa? ˆ En general, supongamos que lanzamos la moneda k veces y que las k veces obtenemos cara ¿Cu´ al es la probabilidad (condicional) de que la moneda escogida sea la falsa. ˆ Supongamos el siguiente procedimiento para decidir si la moneda es falsa. Se lanza k veces, y s´ olo cuando las k veces sale cara, damos la moneda por falsa ¿Cu´al es la probabilidad de que este procedimiento devuelva una respuesta err´ onea?

Ejercicio 26: (Russell & Norvig, ej. 13.15) Supongamos que una persona es testigo de un accidente en el que un taxi de Atenas se ha visto involucrado, pero ha huido. Los taxis en Atenas son azules o verdes. La persona ha visto que el taxi es azul, pero es bien conocido que por la noche, la capacidad de discriminar entre azul y verde es fiable s´ olo en un 75% ¿Es posible calcular el color m´as probable para el taxi del accidente? ¿Y si un polic´ıa

10

local nos dice que en Atenas el 90% de los taxis son verdes? Nota: distinguir entre las variables aleatorias “ser azul” y “parecer azul” Ejercicio 27: (Russell & Norvig, ej. 14.1) Consid´erese la siguiente red para diagn´ostico de aver´ıas en coches (las variables son booleanas): Bateria

Radio

Encendido

Gasolina

Arranca

SeMueve

ˆ Extender la red con las variables T iempoHelado y M otorArranque ˆ Incluir unas tabla de probabilidad (con valores razonables) en cada nodo de la red. ˆ ¿Cuantos valores de probabilidad (independientes) necesitar´ıamos para la DCC, supuesto que no conoci´eramos las relaciones de dependencia? ¿Cu´antos se necesitan una vez que se saben las dependencias de la red? ˆ Con esos valores de probabilidad, calcular la probabilidad de que un coche que no se mueva tenga mal la bater´ıa.

Ejercicio 28: Supongamos que tenemos un modelo probabil´ıstico que expresa en qu´e manera influyen los fallos de electricidad y los de hardware en los fallos inform´ aticos. Tenemos por tanto tres variables aleatorias, E, H e I, con las siguientes probabilidades: P (e) = 0.1, P (h) = 0.2, P (i|¬e, ¬h) = 0, P (i|¬e, h) = 0.5, P (i|e, ¬h) = 1 y P (i|e, h) = 1. Dibujar la correspondiente red bayesiana y calcular P (¬e, h, i), P (h|e) y P (e|i). Ejercicio 29: Supongamos que tenemos cinco variables aleatorias A, B, C, D y E, tales que: ˆ B es independiente de A. ˆ C es independiente de A y de B. ˆ D es independiente de C. ˆ E es condicionalmente independiente de A y de D, dadas B y C.

Dibujar una red bayesiana que exprese las relaciones de dependencia e independencia anteriores. Consideremos que las probabilidades de la red son las siguientes: P (a) = 0.2, P (b) = 0.5, P (c) = 0.8, P (d|¬a, ¬b) = 0.9, P (d|¬a, b) = 0.6, P (d|a, ¬b) = 0.5, P (d|a, b) = 0.1, P (e|¬b, ¬c) = 0.2, P (e|¬b, c) = 0.4, P (e|b, ¬c) = 0.8 y P (e|b, c) = 0.3. Se pide calcular P (a, b, c, d, e), P (¬a|b, c, d, e) y P (e|a, ¬b). Ejercicio 30: Consideremos la siguiente red bayesiana que relaciona las variables aleatorias A, B, C, D, E y F :

11

A

B

C

D

E

F con las siguientes tablas de distribuci´ on:

P (a) 0.4

P (b) 0.3

B b b ¬b ¬b

C c ¬c c ¬c

A a a ¬a ¬a

P (c) 0.7

P (e|B, C) 0.2 0.3 0.5 0.8

D d d ¬d ¬d

E e ¬e e ¬e

B b ¬b b ¬b

P (d|A, B) 0.8 0.2 0.7 0.3

P (f |D, E) 0.1 0.8 0.2 0.7

Se pide: ˆ Calcular la distribuci´ on de la variable aleatoria B condicionada a que se ha observado que F es verdadera, utilizando para ello el algoritmo de inferencia por enumeraci´ on. ˆ Calcular la distribuci´ on de la variable aleatoria B condicionada a que se ha observado que F es falsa, utilizando para ello el algoritmo de eliminaci´ on de variables.

Ejercicio 31: Consid´erese las siguientes variables aleatorias que describen determinadas circunstancias sobre el examen para obtener el permiso de circulaci´ on: ˆ E: se ha dedicado poco tiempo de estudio al c´ odigo de circulaci´ on. ˆ T : se ha hecho mal el examen te´ orico. ˆ P : se ha hecho mal el examen pr´ actico. ˆ A: se han aprendido bien las se˜ nales de circulaci´ on. ˆ S: se ha suspendido.

Supongamos que todo el conocimiento (incierto) acerca de la situaci´ on modelada queda expresado mediante la siguiente red bayesiana:

E

A

P

T

S 12

con las siguientes tablas de distribuci´ on:

P (e) 0.7

E e ¬e

P (a|E) 0.2 0.8

E e ¬e

P (p|E) 0.3 0.8

E e ¬e

P (t|E) 0.8 0.4

P p p ¬p ¬p

T t ¬t t ¬t

P (s|P, T ) 0.9 0.6 0.5 0.1

Responder justificadamente a las siguientes preguntas, suponiendo que la red refleja adecuadamente el dominio de conocimiento. ˆ ¿Es posible calcular a partir de la red cualquier entrada de la DCC? ˆ ¿Es cierto que P y A son incondicionalmente independientes? ¿Es cierto que P(S|T ) = P(S|T, E)? ¿Qu´e relaci´on de independencia condicional existe entre P y T ? ˆ Calcular la probabilidad de que se dedique poco tiempo de estudio, se hagan mal ambos ex´ amenes (te´ orico y pr´actico), no se aprendan las se˜ nales y no se suspenda. ˆ Supongamos que se ha suspendido. ¿Cu´ al es la probabilidad de que se haya dedicado poco tiempo de estudio al c´ odigo de circulaci´ on?

Ejercicio 32: Para la red del ejercicio anterior, y en el caso de la consulta sobre la probabilidad de que se haya dedicado poco tiempo de estudio si se ha suspendido, obtener una muestra ponderada, tal y como las obtiene el algoritmo de inferencia aproximada de ponderaci´ on por verosimilitud; es decir, la muestra y su peso asociado. Nota: Cuando se necesite realizar un sorteo con una probabilidad dada, suponer siempre que se obtiene el valor m´as probable. Ejercicio 33: El doctor House te contrata como nuevo colaborador inform´ atico, experto en redes bayesianas. House escribe en su pizarra lo siguiente: “La met´ astasis (M ) causa tumor cerebral (T ) e incremento en los niveles de calcio (I). El tumor cerebral y el incremento en el nivel de calcio causan coma (C). El tumor cerebral tambi´en causa fuertes jaquecas (J)”. Se pide: ˆ Representa dicha informaci´ on mediante una red bayesiana. ¿Qu´e independencias entre las variables implica la red? ˆ ¿Qu´e datos sobre probabilidades debes pedirle para tener almacenada en la red la informaci´ on necesaria para codificar la distribuci´ on de probabilidad conjunta? ˆ House le proporciona la siguiente informaci´ on:

– En el 20% de los casos hay met´ astasis. – Met´astasis provocan incremento en los niveles de calcio en un 80% de los casos y tumor cerebral en un 20%. – P (c|t, i) = 0.8, P (c|t, ¬i) = 0.7, P (c|¬t, i) = 0.9, P (c|¬t, ¬i) = 0.05

– En el caso de que no haya met´ astasis, se puede producir incremento en los niveles de calcio en un 20% de los casos, y tumor cerebral en un 5%. Con ella, calcula la probabilidad de que el paciente tenga met´ astasis, sabiendo que ha entrado en coma, usando el algoritmo de eliminaci´ on de variables, detallando el significado y el valor de cada factor. ˆ ¿Has necesitado alg´ un dato m´as?

Ejercicio 34: Consideremos la siguiente red bayesiana que relaciona las variables aleatorias A, B, C, D, E, F y G:

13

A

B

C

D

E

F

G

con las siguientes tablas de distribuci´ on:

P (a) 0.4

B b ¬b

A a ¬a

P (b) 0.3

P (e|B) 0.2 0.5

C c c ¬c ¬c

D d ¬d d ¬d

P (c|A) 0.7 0.2

P (f |C, D) 0.1 0.5 0.7 0.9

A a a ¬a ¬a

B b ¬b b ¬b

P (d|A, B) 0.8 0.2 0.7 0.3

D d d ¬d ¬d

E e ¬e e ¬e

P (g|D, E) 0.9 0.7 0.6 0.1

Se pide: ˆ Calcular la distribuci´ on de la variable aleatoria B condicionada a que se ha observado que F es verdadera, utilizando para ello el algoritmo de eliminaci´ on de variables. ˆ Calcular la distribuci´ on de la variable aleatoria B condicionada a que se ha observado que D es verdadera y F es falsa, utilizando para ello el algoritmo de ponderaci´ on por verosimilitud con 5 muestras, indicando las muestras generadas y el peso de las mismas ¿Es necesario generar valores en las muestras para todas las variables o se puede eliminar alguna de ellas?, justificar la respuesta.

Considerar la siguiente secuencia de n´ umeros aleatorios en el proceso de generaci´ on de las muestras: 0.13, 0.07, 0.57, 0.94, 0.13, 0.78, 0.48, 0.38, 0.75, 0.93, 0.55, 0.16, 0.91, 0.06, 0.74, 0.02, 0.71, 0.48, 0.10, 0.04, 0.86, 0.70, 0.49, 0.40, 0.77 Ejercicio 35: En sociedades endog´ amicas se dan con cierta frecuencia relaciones incestuosas entre hermanos. Esta es una situaci´ on propicia para la trasmisi´ on de enfermedades sangu´ıneas. El servicio de salud quiere desarrollar una aplicaci´ on inform´ atica para dar informaci´on a parejas de hermanos sobre la probabilidad de que sus hijos tengan enfermedades sangu´ıneas. Para ello se considera la siguiente red bayesiana que establece las relaciones de dependencia entre las variables asociadas a la presencia de enfermedades sangu´ıneas en un hombre (A), una mujer (B), dos de sus hijos (C hombre y D mujer) y dos hijos fruto de la relaci´on de estos u ´ ltimos (E hombre y F mujer):

14

A

B

C

D

E

F

con las siguientes tablas de distribuci´ on:

P (a) 0.3

P (b) 0.4

C c c ¬c ¬c

D d ¬d d ¬d

A a a ¬a ¬a

B b ¬b b ¬b

P (c|A, B) 0.8 0.7 0.4 0.3

P (e|C, D) 0.8 0.5 0.3 0.2

A a a ¬a ¬a C c c ¬c ¬c

D d ¬d d ¬d

B b ¬b b ¬b

P (d|A, B) 0.8 0.3 0.7 0.2

P (f |C, D) 0.7 0.5 0.2 0.1

Se pide: ˆ Calcular la probabilidad de que una hija fruto del incesto (F ) tenga una enfermedad sangu´ınea, dado que se sabe que un primer hijo (E) ya la tiene, utilizando para ello el algoritmo de inferencia por enumeraci´ on. ˆ Calcular la probabilidad de que una hija fruto del incesto (F ) tenga una enfermedad sangu´ınea, dado que se sabe que un primer hijo (E) no la tiene, utilizando para ello el algoritmo de eliminaci´ on de variables.

Ejercicio 36: Supongamos que acudes a un casino y que uno de los juegos consiste en apostar al n´ umero que saldr´ a en una tirada de un dado. Un amigo te ha dicho que algunos de los dados que usa el casino tienen un defecto de fabricaci´ on que hace que una de las caras del dado sea cinco veces m´as probable de aparecer que las otras caras, y esto siempre ocurre o con la cara del “1” o con la cara del “2”. Seg´ un tu amigo, la f´abrica de dados reconoce que un 3% de los dados que fabrica tienen sesgo hacia el “1” y otro 3% tienen el sesgo hacia el “2”. Antes de hacer tu apuesta, has observado tres jugadas previas y en las tres ha salido el “2”. Si te dejaras guiar por el aprendizaje bayesiano ¿A qu´e n´ umero apostar´ıas en la siguiente jugada? ¿Y si decidieras seg´ un el aprendizaje MAP? ¿Cu´ al de los dos criterios te llevar´ıa a apostar m´as dinero por el n´ umero decidido? Ejercicio 37: Supongamos que tenemos un test m´edico para detectar la hepatitis, cuya eficacia depende del tipo de hepatitis que se tenga. En el caso de que que se tenga hepatitis A, el test lo va a detectar en el 90% de los casos, si se tiene hepatitis B o C, la efectividad baja al 80%. Si no se tienen esas enfermedades, el test ser´ a negativo en el 95% de los casos. Seg´ un las estad´ısticas m´edicas, la probabilidad a priori de tener hepatitis A es de 3 entre 1000 y la de tener tanto hepatitis B como C es de 1 entre 1000 (supondremos, por simplificar, que s´ olo existen esos tres tipos de hepatitis y que no se pueden tener simult´ aneamente). ˆ Supongamos que hacemos dos tests (independientes) a un paciente y que ambos resultan positivos. Seg´ un el aprendizaje bayesiano ¿cu´ al es la probabilidad de tener hepatitis (de alg´ un tipo)? ¿Cu´al es la hip´otesis MAP en este caso? ¿Y si hubi´eramos ignorado las probabilidades a priori y hubi´eramos aprendido la hip´otesis ML? ¿Crees que es razonable usar MAP o ML? ¿Por qu´e? (Nota: considerar cuatro posibles hip´ otesis, considerando que el paciente pueda tener hepatitis A, B, C o ninguna)

15

ˆ Supongamos ahora que, ante la incertidumbre, realizamos un tercer test y que ´este sale tambi´en positivo. Responder a las mismas preguntas que en el apartado anterior. ˆ ¿Y si el tercer test hubiera salido negativo?

Ejercicio 38: Supongamos que tenemos una urna con bolas blancas y negras. A priori sabemos que la composici´ on de la urna podr´ıa ser de dos tipos: mitad blancas y negras, o bien todas negras. La probabilidad a priori de que sea una urna del primer tipo es 0.75 y de que sea del segundo tipo el 0.25. Vamos extrayendo bolas, anotando su color y devolvi´endolas a la urna; de esa manera aprendemos progresivamente sobre la composici´ on real de la urna. Demostrar, para este ejemplo concreto, que a medida que crece el n´ umero de observaciones (extracciones), el aprendizaje bayesiano y el aprendizaje MAP tienden a identificarse ¿Es ´este un fen´ omeno general? Ejercicio 39: Supongamos una variable aleatoria X que puede tomar tres valores posibles (1, 2 ´o 3), con una distribuci´ on de probabilidad que desconocemos. Con el prop´ osito de estimar dicha distribuci´ on de probabilidad, realizamos N observaciones y de ellas obtenemos n1 , n2 y n3 con valor 1, 2 y 3, respectivamente. Planteado como un problema de aprendizaje estad´ıstico ¿Cu´ al es el espacio de hip´otesis? ¿Cu´al es la hip´otesis ML? ¿Por qu´e tiene sentido aprender la hip´ otesis ML y no la hip´ otesis MAP? Ejercicio 40: Una variable aleatoria se dice continua si toma valores en un conjunto no numerable de n´ umeros reales. La distribuci´ on de probabilidad normal (tambi´en llamada de Gauss) es la distribuci´ on m´as frecuente para una variable aleatoria continua. En una distribuci´ on normal, su funci´ on de densidad (en v.a. continuas, la funci´ on de densidad es el an´ alogo a la probabilidad asignada a un valor x) viene dada por la expresi´ on: (x−µ)2 1 f (x) = √ e− σ2 σ 2π

donde µ y σ son dos constantes llamadas media y desviaci´ on est´ andar. Supongamos que conocemos que una variable aleatoria sigue una distribuci´ on normal, pero desconocemos el valor de µ y de σ. Para averiguarlo, realizamos N observaciones y obtenemos una serie de valores xi , i = 1, . . . , N . Plantear el problema como un aprendizaje ML, especificando claramente el espacio de hip´otesis y de todas ellas, cu´ al es la hip´ otesis ML, justific´ andolo. Ejercicio 41: Supongamos que queremos aprender a clasificar un correo como SPAM a partir de tres caracter´ısticas X1 , X2 y X3 (cada una de ellas puede tomar un valor verdadero o falso). Para ello, disponemos de un conjunto de 1000 correos de los cuales 750 est´ an clasificados como “no SPAM” y 250 como “SPAM”. De los “no SPAM”, la mitad tienen la caracter´ıstica X1 , la cuarta parte la caracter´ıstica X2 y 225 tienen la caracter´ıstica X3 . Y de los “SPAM”, la cuarta parte tiene caracter´ıstica X1 , la mitad la caracter´ıstica X2 y 100 tienen la caracter´ıstica X3 . Se pide: ˆ Asumir un modelo Naive Bayes para este problema, y dibujar la red bayesiana correspondiente ¿Qu´e relaciones de independencia condicional se est´ an suponiendo? ˆ Estimar, seg´ un los datos tomados del conjunto de entrenamiento, las tablas de probabilidad de la red anterior ¿Cu´ al es la propiedad fundamental de esa estimaci´ on? ˆ Dado un nuevo correo que no tiene la caracter´ıstica X1 pero que s´ı tiene las otras dos ¿c´ omo se clasificar´ıa seg´ un este modelo Naive Bayes?

Ejercicio 42: Consid´erese el conjunto de entrenamiento en el problema de los “lepistos” (ejercicio 7) y plantearlo como un modelo probabil´ıstico Naive Bayes. Calcular las tablas de probabilidad del modelo a partir del conjunto de entrenamiento. Usando el modelo planteado, decidir si un animal amarillo, peque˜ no, sin alas y con velocidad alta es un lepisto. Comp´ arese el resultado con la clasificaci´ on que se obtendr´ıa con el ´arbol de decisi´on obtenido con ID3 o con el conjunto de reglas obtenido por el algoritmo de cobertura. En el algoritmo ID3 para este problema aparece un atributo irrelevante ¿qu´e ocurre con este atributo en el modelo probabil´ıstico? Ejercicio 43: Considerar el conjunto de entrenamiento del problema de concesi´on de prestamos (ejercicio 8). Plantearlo como un modelo probabil´ıstico Naive Bayes y decidir sobre la concesi´on de pr´estamo a una persona joven, con ingresos altos, informe positivo y con otro pr´estamo. Lo mismo para una persona mayor, con ingresos

16

bajos, informe negativo y con otro pr´estamo. Comparar los resultados con la clasificaci´ on que realiza el ´arbol de decisi´on obtenido mediante ID3. Ejercicio 44: Se sabe que la miop´ıa es un defecto visual que tiene cierta componente hereditaria, ya que tener un padre miope influye, de manera probabil´ıstica, en su aparici´ on. Para realizar un modelo probabil´ıstico de tal circunstancia, consideraremos dos variables aleatorias booleanas M iope y P adreM iope que representan, respectivamente, el tener miop´ıa y el tener un progenitor con miop´ıa. Se pide: ˆ Modelar la situaci´ on mediante una red bayesiana ˆ Supongamos que realizamos un cuestionario a 1000 personas, obteniendo la siguiente informaci´ on: 400 ten´ıan un progenitor miope, de los cuales 300 eran a su vez miopes; otros 100 eran miopes sin tener progenitor miope. Con estos datos, obtener una estimaci´ on de m´axima verosimilitud de los par´ ametros de la red bayesiana del apartado anterior ¿Qu´e significa exactamente que dichas estimaciones sean de m´axima verosimilitud? Demostrar (con el desarrollo matem´atico correspondiente) que lo son. ˆ Supongamos ahora que en la encuesta realizada no hubi´eramos preguntado por los progenitores, y simplemente tuvi´eramos la informaci´ on de que tenemos 400 miopes y 600 no miopes. ¿Por qu´e necesitamos recurrir a un algoritmo EM para encontrar una estimaci´ on ML de los par´ ametros de la red? ¿Hacia qu´e converge el algoritmo EM? Aplicar dos iteraciones del algoritmo, tomando inicialmente todos los par´ ametros igual a 0.5.

Ejercicio 45: Considerar el problema de aprendizaje con el algoritmo EM para la red bayesiana en la que aparecen las variables Bolsa, Sabor, Envoltorio y Agujero, vista en teor´ıa. Realizar con detalle los c´ alculos de la primera iteraci´ on del algoritmo EM. Calcular la “log-verosimilitud” tanto antes de la iteraci´ on como despu´es, y observar c´ omo mejora. Ejercicio 46: Dise˜ nar un perceptr´ on simple con n valores de entrada y funci´ on umbral de activaci´ on que sirva para calcular la funci´ on MAYORIA-SIMPLE; esta funci´ on recibe n entradas (cada una puede ser un 0 o un 1) y devuelve como salida un 1 si hay estrictamente m´as 1s que 0s, o 0 en caso contrario. Ejercicio 47: Demostrar geom´etricamente que un perceptr´on simple no puede calcular la funci´ on XOR. Construir una red neuronal (con funci´ on umbral como funci´ on de activaci´ on) que s´ı la calcule. Indicaci´ on: Tener en cuenta que XOR se puede obtener mediante AND y OR, y que estas dos funciones si pueden ser calculadas por perceptrones. Ejercicio 48: La funci´ on PARIDAD es aquella que recibiendo n bits, devuelve 1 si hay un n´ umero par de ellos igual a 1, y 0 en caso contrario ¿Se puede calcular la funci´ on PARIDAD mediante un perceptr´on simple? ¿Y mediante una red neuronal con una capa oculta y funci´ on umbral como funci´ on de activaci´ on? Indicaci´ on: incluir n neuronas en la capa intermedia, donde cada neurona i de la capa intermedia se debe activar con un 1 si hay m´as de i entradas iguales a 1. Ejercicio 49: Sea f una funci´ on de R × R en {−1, 1} tal que f (−1, 1) = f (0, 0) = 1 y f (−1, 0) = f (0, 1) = −1. Supongamos que con ese conjunto de ejemplos aplicamos el algoritmo de entrenamiento del perceptr´on simple bipolar ¿Ser´a el algoritmo capaz de encontrar los pesos adecuados para que la unidad bipolar correspondiente calcule correctamente los cuatro ejemplos anteriores? En el caso de usar el algoritmo de entrenamiento de la regla delta para encontrar un perceptr´ on simple con funci´ on activaci´ on diferenciable, ¿hacia qu´e converge el vector de pesos que va construyendo el algoritmo? Ejercicio 50: Sea el conjunto de puntos del plano x1 = (1, 1), x2 = (0, 0), x3 = (2, 2), x4 = (1, 0), x5 = (2, 0) y x6 = (0, 1). Estos puntos est´ an clasificados en dos grupos: los tres primeros de la clase 1 y los restantes de la clase -1 ¿Es posible que un perceptr´ on los clasifique correctamente? Aplicar el algoritmo de entrenamiento del perceptr´on simple bipolar para encontrar un vector de pesos que clasifique correctamente esos puntos. Tomar w0 = w1 = w2 = 0 como pesos iniciales y 0.5 como factor de aprendizaje. Ejercicio 51: Sea una red neuronal con la siguiente estructura en la que se usa el sigmoide como funci´ on de activaci´ on: 17

1

2

3

5

7

6

8

4 Supongamos dado un ejemplo (x1 , x2 , x3 , x4 ) con salida esperada (y7 , y8 ). Supongamos tambi´en que ya hemos calculado la salida ai en cada unidad i = 1, . . . , 8. Seg´ un el algoritmo de retropropagaci´on: ¿cu´ ales son las f´ormulas para calcular los errores ∆8 , ∆7 y ∆6 , respectivamente? ¿y las f´ormulas para actualizar los pesos w6,7 y w6,8 , respectivamente? Ejercicio 52: Consideremos la red neuronal de la siguiente figura formada por unidades bipolares (considerando x0 = 1 en todos los casos):

X

wAx

A wCA

wAy

wAx = 1 wBx = 1 wCA = 1

C wBx

Y

wBy

wAy = 1 wBy = −1 wCB = 1

wCB

wA0 = −1 wB0 = −1 wC0 = −1

B

En esta red neuronal las unidades de la capa oculta son, consideradas de forma aislada, perceptrones simples con dos entradas; cada uno de los cuales clasifica una regi´on del plano XY (ver figura). La unidad C implementa una conjunci´ on de las se˜ nales de las unidades A y B que, gr´aficamente, se corresponde con la intersecci´on de las regiones clasificadas por las unidades A y B (ver figura).

Y

11111111111111111 00000000000000000 00000000 11111111 00000000000000000 11111111111111111 A 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 C 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 X 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 B 00000000 11111111 00000000000000000 11111111111111111 00000000 11111111 00000000000000000 11111111111111111 00000000000000000 11111111111111111 00000000000000000 11111111111111111 Teniendo en cuenta esta interpretaci´ on geom´etrica de la red neuronal, se pide: 18

ˆ Determinar los valores de los pesos de la red neuronal para que clasifique como 1 la siguiente regi´ on geom´etrica: {(x, y) : y ≤ 1 + x o y ≤ 1 − x} ˆ Determinar los valores de los pesos de la red neuronal para que clasifique como 1 la siguiente regi´ on geom´etrica: {(x, y) : −1 ≤ x − y ≤ 1} ˆ Calcular la funci´ on XOR con una red neuronal como la de la figura, utilizando un razonamiento de tipo geom´etrico (intersecci´on o uni´ on de regiones del plano).

Ejercicio 53: Sea f una funci´ on de R × R en {−1, 1}. Consideremos el problema de aprender f mediante un perceptr´on simple bipolar, para ello se tiene el siguiente conjunto de entrenamiento: E1 E2 E3 E4 E5 E6

Entradas (2, 0) (0, 0) (2, 2) (0, 1) (1, 1) (1, 2)

Salida 1 −1 1 −1 1 −1

Aplicar el algoritmo de entrenamiento del perceptr´on simple bipolar con el conjunto de entrenamiento anterior, considerando los ejemplos en el mismo orden en que aparecen, hasta que se clasifiquen correctamente todos los ejemplos. Tomar 0 como valor inicial para los pesos y 0.1 como factor de aprendizaje. Con los pesos aprendidos, ¿qu´e salida se obtiene para las siguientes entradas: (0, 2), (1, 0) y (2, 1)? Ejercicio 54: ˆ Supongamos que queremos dise˜ nar un sistema automatizado para reconocer el estado de ´animo de la gente observando la expresi´ on de su cara. Por simplificar las cosas, supongamos que consideramos cuatro tipos distintos de estados de ´ animo: alegre, triste, enfadado y neutro. Suponiendo que nuestro sistema dispone de una c´ amara que es capaz de obtener im´ agenes digitalizadas de la cara de una persona ¿c´ omo dise˜ nar´ıas el sistema usando una red neuronal? ¿en qu´e consistir´ıa el aprendizaje de esa red? ˆ Consid´erese la red neuronal (cuya funci´ on de activaci´ on es el sigmoide) representada por el siguiente dibujo:

1

3 5

2

4

Como es usual, el peso asociado a la conexi´on entre una unidad i y una unidad j de la capa siguiente se representar´ a por wij . Adem´as, cada unidad i que no sea de entrada tiene un peso de umbral notado por w0i asociado a una entrada fija a0 = −1. Dado un ejemplo (x1 , x2 ) del conjunto de entrenamiento, con salida asociada y, se pide escribir las correspondientes f´ormulas de actualizaci´on de los pesos al ejecutar una iteraci´ on del algoritmo de retropropagaci´on con ese ejemplo. En concreto, se pide: – Dar las f´ ormulas de las salida ai asociada a cada unidad i. – Dar las f´ ormulas de actualizaci´on de los pesos (incluidos los pesos de umbral).

19

Tabla de Entrop´ıas Ent(X, Y )

X

0 1 2 3 4 5 6 7 8 9

Y 0 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

1 0.000 1.000 0.918 0.811 0.722 0.650 0.592 0.544 0.503 0.469

2 0.000 0.918 1.000 0.971 0.918 0.863 0.811 0.764 0.722 0.684

3 0.000 0.811 0.971 1.000 0.985 0.954 0.918 0.881 0.845 0.811

4 0.000 0.722 0.918 0.985 1.000 0.991 0.971 0.946 0.918 0.890

20

5 0.000 0.650 0.863 0.954 0.991 1.000 0.994 0.980 0.961 0.940

6 0.000 0.592 0.811 0.918 0.971 0.994 1.000 0.996 0.985 0.971

7 0.000 0.544 0.764 0.881 0.946 0.980 0.996 1.000 0.997 0.989

8 0.000 0.503 0.722 0.845 0.918 0.961 0.985 0.997 1.000 0.998

9 0.000 0.469 0.684 0.811 0.890 0.940 0.971 0.989 0.998 1.000