sesión 14: redes de decisión - ciencias computacionalesesucar/clases-mgp/pgm14-rdec-2012.pdf ·...
TRANSCRIPT
![Page 1: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/1.jpg)
Sesión 14: Redes de Decisión
“un agente racional ideal es aquel que, para cadaposible secuencia de percepciones, realiza laacción que maximiza su medida de rendimientoesperada, basado en la evidencia y suconocimiento.” [Russell 95]
Modelos Gráficos ProbabilistasL. Enrique Sucar
INAOE
![Page 2: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/2.jpg)
© L.E. Sucar: MGP - redes decisión 2
Redes de Decisión• Teoría de Decisiones
– Utilidad– Axiomas de utilidad– Utilidad del dinero
• Modelos para soporte de decisiones– Árboles de decisión– Diagramas de influencia– Redes de decisión dinámicas
![Page 3: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/3.jpg)
© L.E. Sucar: MGP - redes decisión 3
Teoría de Decisiones• Marco teórico para tomar decisiones en
forma racional• Agente Racional – toma sus decisiones de
forma que maximize la utilidad de susacciones en función de sus objetivos y suconocimiento acerca del mundo
![Page 4: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/4.jpg)
© L.E. Sucar: MGP - redes decisión 4
Elementos
• Alternativas: decisiones del agente• Eventos: producto del ambiente u otros
agentes (no tiene control)• Resultados: combinación de las decisiones
y eventos, cada uno tiene asociada unapreferencia para el agente
• Preferencias: valor que establece el agentede acuerdo a sus metas
![Page 5: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/5.jpg)
© L.E. Sucar: MGP - redes decisión 5
Utilidad
• La utilidad expresa que tan deseable es elresultado de cada posible acción
• Ya que normalmente se tiene incertidumbre, seutiliza la utilidad esperada:
U(a) = Σr U(r) P(r|a,e)• Donde:
– a = posibles acciones– r = posibles resultados– e = evidencia disponible
![Page 6: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/6.jpg)
© L.E. Sucar: MGP - redes decisión 6
Lotería
• A cada posible resultado (escenario) se laasocia una probabilidad de ocurrencia, alconjunto de estos se le denomina una lotería
• Cada estado de la lotería tiene una utilidad,de forma que se pueden ordenar de acuerdoa la preferencia del agente:– Prefiere A a B – A > B– Indiferente – A ~ B
![Page 7: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/7.jpg)
© L.E. Sucar: MGP - redes decisión 7
Axiomas de Utilidad
1. Orden – dados dos estados, se prefiereuno u otro, o se es indiferente
2. Transitividad – si A > B y B > C,entonces A > C
3. Continuidad – Si A>B>C, existe algúnvalor de probabilidad, p, de forma que esindiferente entre obtener B o la loteríaA, p y C, 1-p
![Page 8: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/8.jpg)
© L.E. Sucar: MGP - redes decisión 8
Axiomas de Utilidad4. Substitución – si el agente es indiferente entre
dos loterías A y B, entonces es indiferenteentre dos loterías más complejas que soniguales excepto en que A es substituida por Ben una de ellas
5. Monotonicidad – si hay dos loterías con losmismos resultados, A y B, y el agente prefiereA, entonces debe preferir la lotería en que Atiene mayor probabilidad
6. Descomposición – loterías compuestas sepueden reducir a loterías más simples usandolas leyes de probabilidad
![Page 9: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/9.jpg)
© L.E. Sucar: MGP - redes decisión 9
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érminosmonetarios, aunque la relación de utilidad y $ noes lineal!
![Page 10: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/10.jpg)
© L.E. Sucar: MGP - redes decisión 10
Utilidad del Dinero• Ejemplo:
– “En un concurso ya tienes $1,000,000. Tienesla oportunidad de quedarte con esto o lanzaruna 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.5x0 + 0.5x$3,000,000 = $1,500,000
![Page 11: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/11.jpg)
© L.E. Sucar: MGP - redes decisión 11
Utilidad del Dinero• Se ha encontrado empíricamente para la mayor
parte de las personas hay existe una relaciónlogarítmica entre VME y la utilidad.
$
U
![Page 12: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/12.jpg)
© L.E. Sucar: MGP - redes decisión 12
Utilidad del Dinero• Sin embargo, para diferentes personas (empresas)
puede haber diferentes relaciones entre U y VMEdependiendo de la situación y el contexto
$
UNeutro
Evita elRiesgo
Busca elRiesgo
![Page 13: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/13.jpg)
© L.E. Sucar: MGP - redes decisión 13
Árboles de Decisión• Un árbol de decisión es una representación
gráfica de las alternativas disponibles parael agente y los aspectos que son inciertos
• Un árbol de decisión tiene dos tipos denodos:– Nodos de decisión (cuadrados) - alternativas
del agente– Nodos aleatorios (círculos) - posibles
resultados de un evento incierto
![Page 14: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/14.jpg)
© L.E. Sucar: MGP - redes decisión 14
Á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 tieneasociada una probabilidad
• Los nodos terminales (hojas) del árbol tienen uncosto o utilidad (normalmente en unidadesmonetarias)
![Page 15: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/15.jpg)
© L.E. Sucar: MGP - redes decisión 15
Ejemplo de Árbol de Decisión
Decisión
pronósticos
melate
Ganar (0.1)
Ganar (0.2)
Perder (0.9)
Perder (0.8)
100
- 15
50
-10
![Page 16: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/16.jpg)
© L.E. Sucar: MGP - redes decisión 16
Evaluación• A partir de los nodos terminales (de las
hojas hacia la raíz):– Para los nodos aleatorios, E, se calcula la
utilidad (costo) esperado en función de loscostos de cada alternativa y sus probabilidadesasociadas
V(E) = Σ P(resultado(E)) V(resultado(E))– Para los nodos de decisión, D, se selecciona la
alternativa de mayor utilidad (menor costo)esperado:
V(D) = max V(resultado(D))
![Page 17: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/17.jpg)
© L.E. Sucar: MGP - redes decisión 17
Ejemplo de Evaluación
Decisión
pronósticos
melate
Ganar (0.1)
Ganar (0.2)
Perder (0.9)
Perder (0.8)
100
- 15
50
-10
-3.5
2
![Page 18: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/18.jpg)
© L.E. Sucar: MGP - redes decisión 18
Diagramas de Influencia• Alternativa a los árboles de decisión que es
más expresiva y a la vez permite construirmodelos más compactos basados enmodelos gráficos
• Se pueden ver como una extensión a lasredes bayesianas, incorporando nodos dedecisión y nodos de utilidad
![Page 19: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/19.jpg)
© L.E. Sucar: MGP - redes decisión 19
Tipos de Nodos
• Nodos Aleatorios – (óvalos)• Nodos de Decisión – (rectángulos)• Nodos de Utilidad – (rombos)
![Page 20: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/20.jpg)
© L.E. Sucar: MGP - redes decisión 20
Ejemplo
A
B C
D
Decisión
Utilidad
![Page 21: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/21.jpg)
© L.E. Sucar: MGP - redes decisión 21
Nodos Aleatorios
• Representan variables aleatorias como enredes bayesianas
• Pueden ser observadas o estimadas
Variable
![Page 22: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/22.jpg)
© L.E. Sucar: MGP - redes decisión 22
Nodo 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ónDecisión
![Page 23: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/23.jpg)
© L.E. Sucar: MGP - redes decisión 23
Nodo 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
• En los modelos básicos hay un nodo de utilidad, peropuede haber más. Generalmente se asume que lautilidad es la suma (pesada) de los nodos de utilidad
Utilidad
![Page 24: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/24.jpg)
© L.E. Sucar: MGP - redes decisión 24
Ejemplo – modelo para decidirla ubicación de un Aeropuerto
tráfico
Ubicaciónaeropuerto
Utilidad
Constr.
demanda
costo
ruido
accidentes
![Page 25: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/25.jpg)
© L.E. Sucar: MGP - redes decisión 25
Evaluación (DI simple: un nodode decisión y de utilidad)
1. Asignar valores a todos los nodosaleatorios conocidos (evidencia)
2. Para cada posible decisión:• Asignar dicho valor al nodo de decisión• Propagar las probabilidades• Calcular la utilidad
3. Seleccionar la alternativa de mayorutilidad
![Page 26: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/26.jpg)
© L.E. Sucar: MGP - redes decisión 26
Técnica de Evaluación
• En general existen 3 tipos de técnicas pararesolver diagramas de influencia:– Conversión a un árbol de decisión– Eliminación de variables - aplicando una
serie de transformaciones a la red– Conversión a una red bayesiana
![Page 27: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/27.jpg)
© L.E. Sucar: MGP - redes decisión 27
Eliminación de Variables
• Si hay varios nodos de decisión se van evaluandouno por uno en “orden”
• Para ello se requiere hacer un ordenamientomediante una transformación de la red
• El algoritmo de evaluación se basa en una seriede transformaciones del grafo – remover nodos einvertir arcos, tal que no modifican la políticaóptima
![Page 28: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/28.jpg)
© L.E. Sucar: MGP - redes decisión 28
Red de decisión regular
• Una red de decisión es regular si:1. Es un grafo acíclico dirigido2. El nodo de utilidad no tiene sucesores3. 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• Una representación alternativa que no impone
estas restricciones son los LIMIDs (LImitedMemory Influence Diagramas)
![Page 29: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/29.jpg)
© L.E. Sucar: MGP - redes decisión 29
Transformaciones• Eliminar nodos aleatorios o de decisión que sean
nodos hoja (barren nodes)- no afectan lasdecisiones
• Eliminar nodos aleatorios que son padres delnodo de utilidad y no tienen otros hijos – serecalcula el nodo de utilidad en base a los padresdel nodo eliminado
• Eliminar nodos de decisión que sean padres delnodo de utilidad y que sus padres también seanpadres del nodo de utilidad – tomar la decisión demayor utilidad y guardarla en el nodo de utilidad
![Page 30: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/30.jpg)
© L.E. Sucar: MGP - redes decisión 30
Transformaciones
• Inversión de arcos: se puede invertir el arcoentre los nodos aleatorios i j si no hayotra trayectoria entre i – j– se invierte el arco j i y cada nodo hereda los
padres del otro
![Page 31: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/31.jpg)
© L.E. Sucar: MGP - redes decisión 31
Ejemplo de transformación
![Page 32: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/32.jpg)
© L.E. Sucar: MGP - redes decisión 32
Ejemplo de transformación
![Page 33: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/33.jpg)
© L.E. Sucar: MGP - redes decisión 33
Ejemplo de transformación
![Page 34: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/34.jpg)
© L.E. Sucar: MGP - redes decisión 34
Ejemplo de transformación
![Page 35: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/35.jpg)
© L.E. Sucar: MGP - redes decisión 35
Ejemplo de transformación
![Page 36: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/36.jpg)
© L.E. Sucar: MGP - redes decisión 36
Ejemplo de transformación
![Page 37: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/37.jpg)
© L.E. Sucar: MGP - redes decisión 37
Ejemplo de transformación
![Page 38: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/38.jpg)
© L.E. Sucar: MGP - redes decisión 38
Ejemplo de transformación
![Page 39: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/39.jpg)
© L.E. Sucar: MGP - redes decisión 39
Ejemplo de transformación
![Page 40: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/40.jpg)
© L.E. Sucar: MGP - redes decisión 40
Conversión a una red bayesiana• Otra forma de resolver una red de decisión es
transformarla a una red bayesiana:– Los nodos de decisión se convierten a nodos aleatorios
con una distribución uniforme– Los nodos de utilidad se convierten a nodos aleatorios
binarios, para los que su probabilidad es proporcional ala utilidad
• Entonces el problema se reduce a propagar en lared bayesiana para todas las combinaciones de losnodos de decisión, de forma que se maximice laprobabilidad del nodo(s) de utilidad
![Page 41: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/41.jpg)
© L.E. Sucar: MGP - redes decisión 41
Ejemplo de Transformación
tráfico
Ubicaciónaeropuerto
Utilidad
Constr.
demanda
costo
ruido
accidentes
![Page 42: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/42.jpg)
© L.E. Sucar: MGP - redes decisión 42
Ejemplo de Transformación
tráficoUtilidad
Constr.
demanda
costo
ruido
accidentes
Ubicaciónaeropuerto
![Page 43: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/43.jpg)
© L.E. Sucar: MGP - redes decisión 43
Ejemplo de Transformación
tráfico
Constr.
demanda
costo
ruido
accidentes
Ubicaciónaeropuerto
Utilidad
![Page 44: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/44.jpg)
© L.E. Sucar: MGP - redes decisión 44
Ejemplo en Hugin:¿Llevar paraguas?
• Nodos aleatorios:– predicción del clima– clima
• Nodos de decisión:– escuchar el pronóstico– llevar paraguas
• Nodo de utilidad:– considera el compromiso entre el costo de
llevar el paraguas vs. el costo de mojarse
![Page 45: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/45.jpg)
© L.E. Sucar: MGP - redes decisión 45
Redes de decisión dinámicas• Este concepto se puede extender a la toma
de decisiones en el tiempo – redes dedecisión dinámicas
• Incorporan nodos de decisión y de utilidada las redes bayesianas dinámicas
• Normalmente se tienen una serie dedecisiones en el tiempo y una cierta utilidaden el futuro
![Page 46: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/46.jpg)
© L.E. Sucar: MGP - redes decisión 46
St St+1 St+2 St+3
Dt-1
Ut
Redes de Decisión Dinámicas
E E E E
Dt Dt+1 Dt+2
Ut+1 Ut+2
![Page 47: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/47.jpg)
© L.E. Sucar: MGP - redes decisión 47
Procesos de Decisión de Markov
• Una red de decisión dinámica esequivalente a un MDP – proceso dedecisión de Markov o a un POMDP –proceso de decisión de Markovparcialmente observable
• Sin embargo, en un MDP puede haber unnúmero infinito de decisiones o etapastemporales
• Estos modelos son el tema de la siguientesesión
![Page 48: Sesión 14: Redes de Decisión - Ciencias Computacionalesesucar/Clases-mgp/pgm14-rdec-2012.pdf · •Agente Racional – toma sus decisiones de ... Generalmente se asume que la utilidad](https://reader034.vdocumento.com/reader034/viewer/2022051722/5a94750e7f8b9a30358c1057/html5/thumbnails/48.jpg)
© L.E. Sucar: MGP - redes decisión 48
Referencias• [Russell & Norvig] – Cap. 16• [Sucar, Morales, Hoey] - Caps. 1, 2• Borrás, Análisis de incertidumbre y riesgo para la
toma de decisiones, Comunidad Morelos, 2001.• 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, Operations
Research 34, 1986• Crawley, Evaluating infuence diagrams, 2004.