1 Sesión 12: Redes de Decisión “un agente racional ideal es aquel que, para cada posible secuencia de percepciones, realiza la acción que maximiza su medida de rendimiento esperada, basado en la evidencia y su conocimiento.” [Russell 95]

2 Incertidumbre - RdeD, L.E. SucarRedes de Decisión Teoría de Decisiones Utilidad Axiomas de utilidad Utilidad del dinero Modelos para soporte de decisiones Árboles de decisión Redes de decisión Redes de decisión dinámicas Incertidumbre - RdeD, L.E. Sucar

3 Incertidumbre - RdeD, L.E. SucarTeoría de Decisiones Marco teórico para tomar decisiones en forma racional Agente Racional – toma sus decisiones de forma que maximize la utilidad de sus acciones en función de sus objetivos y su conocimiento acerca del mundo Incertidumbre - RdeD, L.E. Sucar

4 Incertidumbre - RdeD, L.E. SucarUtilidad La utilidad expresa que tan deseable es el resultado de cada posible acción Ya que normalmente se tiene incertidumbre, se estima la utilidad esperada: U(a) = Sr U(r) P(r|a,e) Donde: a = posibles acciones r = posibles resultados e = evidencia disponible Incertidumbre - RdeD, L.E. Sucar

5 Incertidumbre - RdeD, L.E. SucarLotería A cada posible resultado (escenario) se la asocia una probabilidad de ocurrencia, al conjunto de estos se le denomina una lotería Cada estado de la lotería tiene una utilidad, de forma que se pueden ordenar de acuerdo a la preferencia del agente: Prefiere A a B – A > B Indiferente – A ~ B Incertidumbre - RdeD, L.E. Sucar

6 Incertidumbre - RdeD, L.E. SucarAxiomas de Utilidad Orden – dados dos estados, se prefiere uno u otro, o se es indiferente Transitividad – si A > B y B > C, entonces A > C Continuidad – Si A>B>C, existe algún valor de probabilidad, p, de forma que es indiferente entre obtener B o la lotería A, p y C,1-p Incertidumbre - RdeD, L.E. Sucar

7 Incertidumbre - RdeD, L.E. SucarAxiomas de Utilidad Substitución – si el agente es indiferente entre dos loterías A y B, entonces es indiferente entre dos loterías más complejas que son iguales excepto en que A es substituida por B en una de ellas Monotonicidad – si hay dos loterías con los mismos resultados, A y B, y el agente prefiere A, entonces debe preferir la lotería en que A tiene mayor probabilidad Descomposición – loterías compuestas se pueden reducir a loterías más simples usando las leyes de probabilidad Incertidumbre - RdeD, L.E. Sucar

8 Principio de Utilidad Se prefiere la acción (decisión) que de la mayor utilidad esperada: U(A) > U(B)  A > B (A es mejor que B) Si la utilidad es la misma se es indiferente: U(A) = U(B)  A ~ B (indiferencia) Normalmente se mide la utilidad en términos monetarios, aunque la relación de utilidad y $ no es lineal! Incertidumbre - RdeD, L.E. Sucar

9 Incertidumbre - RdeD, L.E. SucarUtilidad del Dinero Ejemplo: “En un concurso ya tienes $1,000,000. Tienes la oportunidad de quedarte con esto o lanzar una moneda – si cae águila ganas $3,000,000, si no pierdes lo que tenías” ¿Qué escogerías? Valor monetario esperado: Quedarse – VME = $1,000,000 Apostar – VME = 0.5x x$3,000,000 = $1,500,000 Incertidumbre - RdeD, L.E. Sucar

10 Incertidumbre - RdeD, L.E. SucarUtilidad del Dinero Se ha encontrado empíricamente que existe una relación logarítmica entre VME y la utilidad. Incertidumbre - RdeD, L.E. Sucar

11 Incertidumbre - RdeD, L.E. SucarÁrboles de Decisión Un árbol de decisión es una representación gráfica de las alternativas disponibles para el agente y los aspectos que son inciertos Un árbol de decisión tiene dos tipos de nodos: Nodos de decisión (cuadrados) Nodos aleatorios (círculos) Incertidumbre - RdeD, L.E. Sucar

12 Incertidumbre - RdeD, L.E. SucarÁrboles de Decisión El árbol de decisión se puede ver como una “guía” para el tomador de decisiones: Al encontrar un nodo de decisión debe seleccionar una de las alternativas Al encontrar un nodo aleatorio no tiene control, la trayectoria esta determinada por las probabilidades Cada alternativa en un nodo aleatorio tiene asociada una probabilidad Los nodos terminales (hojas) del árbol tienen un costo o utilidad (normalmente en unidades monetarias) Incertidumbre - RdeD, L.E. Sucar

13 Ejemplo de Árbol de DecisiónGanar (0.1) 100 pronósticos - 15 Perder (0.9) Decisión Ganar (0.2) melate 50 Perder (0.8) -10 Incertidumbre - RdeD, L.E. Sucar

14 Incertidumbre - RdeD, L.E. SucarEvaluación A partir de los nodos terminales (de las hojas hacia la raíz): Para los nodos aleatorios, se calcula la utilidad (costo) esperado en función de los costos de cada alternativa y sus probabilidades asociadas Para los nodos de decisión, se selecciona la alternativa de mayor utilidad (menor costo) esperado Incertidumbre - RdeD, L.E. Sucar

15 Incertidumbre - RdeD, L.E. SucarEjemplo de Evaluación Ganar (0.1) 100 -3.5 pronósticos - 15 Perder (0.9) Decisión Ganar (0.2) 50 melate 2 Perder (0.8) -10 Incertidumbre - RdeD, L.E. Sucar

16 Incertidumbre - RdeD, L.E. SucarRedes de Decisión Modelos para el apoyo a la toma de decisiones en forma racional, combinando el manejo probabilístico de incertidumbre con teoría de decisiones La redes de decisión extienden a las redes bayesianas incorporando nodos de decisión y nodos de utilidad Incertidumbre - RdeD, L.E. Sucar

17 Incertidumbre - RdeD, L.E. SucarTipos de Nodos Nodos Aleatorios – (óvalos) Nodos de Decisión – (rectángulos) Nodos de Utilidad – (rombos) Incertidumbre - RdeD, L.E. Sucar

18 Incertidumbre - RdeD, L.E. SucarEjemplo A Decisión B C Utilidad D Incertidumbre - RdeD, L.E. Sucar

19 Incertidumbre - RdeD, L.E. SucarNodos Aleatorios Representan variables aleatorias como en redes bayesianas Pueden ser observadas o estimadas Costo Incertidumbre - RdeD, L.E. Sucar

20 Incertidumbre - RdeD, L.E. SucarNodo de Decisión Representan los puntos de decisión del agente Tiene un conjunto de valores que corresponden a las opciones en ese punto Los arcos hacia nodos de decisión son de información, indican precedencia en el tiempo Pueden tener arcos (influenciar) a los nodos aleatorios o a los nodos de utilidad Puede haber varios nodos de decisión en una red de decisión Ubicación Incertidumbre - RdeD, L.E. Sucar

21 Incertidumbre - RdeD, L.E. SucarNodo de Utilidad Representan la función de utilidad del agente Tienen como padres los nodos aleatorios y de decisión que afectan directamente la utilidad La utilidad se puede definir como: Una matriz con un valor por cada combinación de los padres Una función matemática Normalmente se tiene un solo nodo de utilidad Utilidad Incertidumbre - RdeD, L.E. Sucar

22 Ejemplo – modelo para decidir la ubicación de un Aeropuertoaccidentes Utilidad tráfico ruido demanda costo Constr. Incertidumbre - RdeD, L.E. Sucar

23 Evaluación (un nodo de decisión)Asignar valores a todos los nodos aleatorios conocidos (evidencia) Para cada posible decisión: Asignar dicho valor al nodo de decisión Propagar las probabilidades Calcular la utilidad Seleccionar la alternativa de mayor utilidad Incertidumbre - RdeD, L.E. Sucar

24 Evaluación (más de un nodo de decisión)Si hay varios nodos de decisión se van evaluando uno por uno en “orden” Para ello se requiere hacer un ordenamiento mediante una transformación de la red El algoritmo de evaluación se basa en una serie de transformaciones del grafo – remover nodos e invertir arcos, tal que no modifican la política óptima Incertidumbre - RdeD, L.E. Sucar

25 Red de decisión regularUna red de decisión es regular si: Es un grafo acíclico dirigido El nodo de utilidad no tiene sucesores Hay una trayectoria dirigida que contiene a todos los nodos de decisión La tercera condición implica un ordenamiento total de todas las decisiones Incertidumbre - RdeD, L.E. Sucar

26 Incertidumbre - RdeD, L.E. SucarTransformaciones Eliminar nodos aleatorios o de decisión que sean nodos hoja (barren nodes)- no afectan las decisiones Eliminar nodos aleatorios que son padres del nodo de utilidad y no tienen otros hijos – se recalcula el nodo de utilidad en base a los padres del nodo eliminado Eliminar nodos de decisión que sean padres del nodo de utilidad y que sus padres también sean padres del nodo de utilidad – tomar la decisión de mayor utilidad y guardarla en el nodo de utilidad Incertidumbre - RdeD, L.E. Sucar

27 Incertidumbre - RdeD, L.E. SucarTransformaciones Inversión de arcos: se puede invertir el arco del nodo aleatorio i  j si no hay otra trayectoria entre i – j se invierte el arco j  i y cada nodo hereda los padres del otro Incertidumbre - RdeD, L.E. Sucar

28 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

29 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

30 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

31 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

32 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

33 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

34 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

35 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

36 Ejemplo de transformaciónIncertidumbre - RdeD, L.E. Sucar

37 Ejemplo en Hugin: ¿Llevar paraguas?Nodos aleatorios: predicción del clima clima Nodos de decisión: escuchar el pronóstico llevar paraguas Nodo de ultilidad: considera el compromiso entre el costo de llevar el paraguas vs. el costo de mojarse Incertidumbre - RdeD, L.E. Sucar

38 Redes de decisión dinámicasEste concepto se puede extender a la toma de decisiones en el tiempo – redes de decisión dinámicas Incorporan nodos de decisión y de utilidad a las redes bayesianas dinámicas Normalmente se tienen una serie de decisiones en el tiempo y una cierta utilidad en el futuro Incertidumbre - RdeD, L.E. Sucar

39 Redes de Decisión DinámicasDt-1 Dt Dt+1 Dt+2 Utilidad St St+1 St+2 St+3 E E E E Incertidumbre - RdeD, L.E. Sucar

40 Procesos de Decisión de MarkovLos procesos de decisión en el tiempo, conocidos también como procesos de decisión secuenciales, se modelan y resuelven como modelos de decisión de Markov (MDP) – que veremos en la siguiente sesión Incertidumbre - RdeD, L.E. Sucar

41 Incertidumbre - RdeD, L.E. SucarReferencias [Russell & Norvig] – Cap. 16 Hiller & Lieberman, Introduction to Operations Research, Holden-Day – Cap. 15 Warner, A tutorial introduction to decision theory, en Readings on Uncertain Reasoning, Morgan-Kaufmann Shachter, Evaluating influence diagrams, en Readings on Uncertain Reasoning, Morgan-Kaufmann Incertidumbre - RdeD, L.E. Sucar

42 Incertidumbre - RdeD, L.E. SucarActividades Continuar desarrollando el proyecto final Presentación último día de clases: de mayo Incertidumbre - RdeD, L.E. Sucar