Diagramas de influencia en Elvira II
Granada, 2003
NDICE1.- Diagramas de Influencia 2.- Mtodos de evaluacin 3.- Clases disponibles 4.- Asimetras 5.- Aproximacin 6.- SimulacinGranada, 2003
1.- Diagramas de influenciaLos diagramas de influencia permiten representar problemas de decisin, tal y como los percibe el decisor: incertidumbre, acciones a tomar y preferencias. Representacin + evaluacin. Los diagramas de influencia son grafos dirigidos y acclicos, con tres tipos de nodos:
nodos de azar nodos de decisin nodos de valor
determinsticos
Granada, 2003
1. Diagramas de Influencia (II)
Nodos de azar: variables aleatorias o eventos aleatorios influyentes en el proceso de toma de decisin. Si el nodo es determinstico, su valor queda fijado al conocer los valores de sus predecesores Nodos de decisin: variables bajo control del decisor Nodos de valor: cuantifican las preferencias de los expertos
Granada, 2003
1. Diagramas de Influencia (III) Los arcos entre nodos representan las relaciones entre sus variables asociadas, y pueden ser: informativos: inciden sobre nodos de decisin. Informacin disponible en el momento de decidir CB Ingreso rb Ed ad Tratamiento Pes
o condicionales: inciden sobre nodos de azar y sobre el(los) nodo(s) de utilidad. Representan dependencia probabilstica (o funcional) entre nodos (y no necesariamente causalidad) CB CH Da rb mgb o En f1 En f2 Pe so Ed adGranada, 2003
1. Diagramas de Influencia (IV) Distribuciones: P(Coste 1|.....) P(Coste 2|.....) P(Coste 3|.....) Funcin: Coste total k1*(Coste 1) + k2*(Coste 2) + k3*(Coste 3) Utilidad V1 V2 V3 D1 D2 ------------------------------------------100 v11 v21 v31 d11 d21 39 v11 v21 v31 d11 d22 ......................................................... . 45 v1n v2m v3p d1q d2rGranada, 2003
Cost e 1
Cost e 2
Cost e 3
Cost e total
V 1
V 2
V 3 D1 D2
1. Diagramas de Influencia (V)
Mtodos de evaluacinevaluacin directa (Shachter, Shachter y Peot, Zhang y Poole, Zhang et al, etc). Idea original: Olmsted (1983) evaluacin indirecta : transforman previamente el DI en alguna otra estructura : rboles de decisin, grafos de decisin, redes bayesianas, ... (Howard y Matheson, Cooper, Qi y Poole, Qi, etc) mtodos aproximados: mediante simulacin (Shenoy, Bielza, Ortiz, ...), mediante aproximaciones sucesivas (Horsch & Poole), ...
Granada, 2003
2.- Mtodos de evaluacinA) Mtodo de inversin de arcos Mientras haya antecesores del nodo de valor - Eliminar nodo de azar
v' = v xx
(herencia sobre el nodo de valor)A X U U U(A,B))Granada, 2003
B
A
B
U(X)
2. Mtodos de evaluacin (II)
- Eliminar nodo de decisin:
v' = max x v
X A B
C A U
C B U(A, B)
U U(X, A, B)
SumideroGranada, 2003
2. Mtodos de evaluacin (III)
- Invertir arco: (previo a eliminacin de nodo de azar)D A C U P(A|C, D) P(B|A, E, F) P ( A | B, C , D, E , F ) = P ( B | C , D, E , F ) = B E C F D A U B E F
P(A|B, C, D, E, F) P(B|C, D, E, F) P ( A | C , D ) P ( B | A, E , F ) P ( B | C , D, E , F )
P ( A | C , D ) P ( B | A, E , F ) xiiGranada, 2003
2. Mtodos de evaluacin (IV)
Resultados: tablas de decisin (poltica ptima) distribuciones a poteriori de todas las variables antes de eliminarlas (recogen la incertidumbre actualizada sobre las variables; interesante en tareas de diagnstico) Inconveniente: elevado coste computacional
Granada, 2003
2. Mtodos de evaluacin (V)
B) Mtodo de eliminacin de variables - Determinar orden temporal, en funcin de los arcos informativos
I 0 < D1 < I1 < ... < Dn < I nIn: los nodos que no son antecesores de ningn nodo de decisin In-1: nodos antecesores de Dn ....................................................... I0: nodos antecesores de D1Granada, 2003
2. Mtodos de evaluacin (VI)
Se van seleccionando variables a eliminar respetando el orden parcial anteriormente determinado. Cuando se selecciona una variable X, los potenciales se actualizan de la siguiente forma:
X = { | X dom } X = { | X dom }Si X es una variable de azar:
X = XX
X = X ( X )X
Granada, 2003
2. Mtodos de evaluacin (VII)
Si X es una variable de decisin:
X = max X X ( X )El conjunto final de potenciales, tras la eliminacin de X queda:
X = max X X
= { \ X } X } {
X = { \ X } X
Granada, 2003
2. Mtodos de evaluacin (VIII)
Resultados: tablas de decisin (poltica ptima) no obtiene las distribuciones a posteriori de las variables a eliminar Ventaja: mucho menor coste computacional
Granada, 2003
2. Mtodos de evaluacin (IX)
C) Mtodos aproximados Objetivo: evaluar problemas muy complejos, las tablas de decisin incluyen muchas variables (explosin combinatoria) Simulacin: instanciar variables, reduccin complejidad del problema (casos) de la
aproximacin anytime. Obtener solucin inicial y mejorar sucesivamenteGranada, 2003
3.- Clases disponibles en ElviraA) Clase IDiagram- Comprobacin de caractersticas y acceso a nodos: a) hasCycles b) directedLinks c) pathBetweenDecisions d) onlyOneValueNode Mtodos e) numberOfDecisions f) decisionReadyToRemove g) firstDecision h) getDecisionList i) getBarrenNode j) getValueNode k) getNode l) getProblemSizeGranada, 2003
Bnet
IDiagram
3. Clases disponibles en Elvira (II)
- Manipulacin sobre el DI: m) addNonForgettingArcs n) eliminateRedundancy ) removeBarrenNodes o) addLinks p) copy q) qualitativeCopy r) evaluate (mediante ArcReversal) s) save t) print
Mtodos
Granada, 2003
3. Clases disponibles en Elvira (III) B) Clase ArcReversal
- Constructores: a) ArcReversal() b) ArcReversal(IDiagram) - Comprobacin de caractersticas y acceso
Propagation
ArcReversal
Mtodos
c) getInitialRelations d) initialConditions - Evaluacin y manipulacin del DI
IDiagram RelationList
e) evaluateDiagram f) removeChanceNode g) removeDecisionNode h) reverseArc i) modifyUtilityRelation j) modifyUtilityLinksGranada, 2003
3. Clases disponibles en Elvira (IV)- Evaluacin y manipulacin del DI k) modifyRelations l) modifyLinks m) getExpectedUtility n) maximizeUtility ) getPosteriorDistributions o) storeDecisionTable p) giveInstantiationOrder q) getMarginalsNames r) checkInstantiationOrder s) variablesInDecisionTables
Granada, 2003
3. Clases disponibles en Elvira (V) C) Clase QualitativeArcReversl
Propagation
- Constructores: a) QualitativeArcReversal(IDiagram) - Acceso a datos miembro
ArcReversal
Mtodos
b) getOrderOfElimination c) getOrderOfInstantiation - Evaluacin y manipulacin del DI
QualitativeArcReversal
d) produceOrderOfInstantiation e) evaluateDiagram f) removeChanceNode g) removeDecisionNode h) reverseArc
Granada, 2003
3. Clases disponibles en Elvira (VI) D) Clase ARWithPotentialTree
Propagation
- Constructores: a) ARWithPotentialTree(IDiagram)
ArcReversal
Mtodos
- Transformacin de relaciones b) transformInitialRelations: Este mtodo convierte los valores de utilidades y de PotentialTable a PotentialTree (con la posibilidad de aplicar los mtodos de rboles que permiten aproximar)
ARWithPotentialTree
Granada, 2003
3. Clases disponibles en Elvira (VII) E) Clase VariableElimination Funcionalidad compartida para redes Bayesianas y diagramas de influencia- Mtodos relacionados con DI a) getPosteriorDistributionsID b) combinePotentialsOfNode c) propagate Incorporacin de mtodo nextToRemoveId en la clase PairTable, que determina la prxima variable a eliminar. Este mtodo de evaluacin no altera la estructura del diagrama: trabaja con sus potenciales, sobre una copia de las relaciones.
Propagation
VariableElimination
Granada, 2003
3. Clases disponibles en Elvira (VIII) F) Clase VEWithPotentialTree- Constructores: a) VEWithPotentialTree(Bnet,Evidence) a) VEWithPotentialTree(Bnet)
PropagationMtodos
- Transformacin de relaciones b) transformInitialRelations: Este mtodo convierte los valores de utilidades y de PotentialTable a PotentialTree (con la posibilidad de aplicar los mtodos de rboles que permiten aproximar)
VariableElimination
VEWithPotentialTreeGranada, 2003
4.- AsimetrasPara ciertos valores de algunas variables, los posibles valores de otra variable estn restringidos. Esta informacin cualitativa se puede representar como una matriz de restricciones (definida sobre las variables afectadas). x1 y1 1 Y X x2 y2 y1 0 0 Y y2 1
Y1 Y2 ....... Yn ------------------------------------------X1 1 0 ....... 0 X2 1 1 ....... 0 .......................................................... Xm 0 1 ....... 1
El tratamiento de las restricciones simplifica la evaluacin (slo evala configuraciones vlidas)Granada, 2003
4. Asimetras (II)
Objetivos de la representacin de asimetras: a) forma general, de forma que se pueda expresar cualquier tipo de relacin. Expresiones lgicas b) las restricciones, asimetras, se convierten en potenciales que se utilizan en la evaluacin del DI c) si como soporte de la informacin cualitativa se usan rboles, es posible realizar podas d) la aplicacin de restricciones, en determinados casos, puede hacer posible la aplicacin de nuevas podas
Granada, 2003
4. Asimetras (III)
Consideraciones sobre las asimetras: a) parte de la informacin cualitativa estar recogida en las distribuciones (probabilidad utilidad) iniciales. Esto ocurre en el caso en que las variables afectadas por la restriccin formen parte del dominio de las distribuciones. Por ejemplo:Condici ones RTe st1 Test1 RTe st2 Test2 Compra V a l o r
Granada, 2003
4. Asimetras (IV)
Resultados del primer test: P(RTest1 | Test1, Condiciones)NoTest bien Sin resul. 0 defectos 1 defecto 2 defectos 1 0 0 0 NoTest mal 1 0 0 0 Frenos bien 0 0.9 0.1 0 Frenos mal 0 0.4 0.6 0 Electric. bien 0 0.8 0.2 0 Electric. mal 0 0.13 0.53 0.33
Si Test1={No Test} RTest1={Sin resul.} Si Test1={Frenos} RTest1 != {Sin resul, 2 defectos} Si Test1={Electric.} Condiciones={bien} RTest1 != {Sin resul, 2 defectos}
Granada, 2003
4. Asimetras (V)
Procedimiento: 1) extraer del experto la informacin cualitativa 2) reducir con ella el nmero de parmetros a obtener 3) al usar rboles, aplicar poda para reducir el nmero de valores a almacenar. En el ejemplo anterior, se podra hacer que las ramas asociadas a Test1 = no Test (correspondientes a los dos posibles valores de Condiciones), se podran unir en 1 (son idnticas) 4) mantener estas dos informaciones supone cierta redundancia
Granada, 2003
4. Asimetras (VI)
b) Qu ocurre si estas informaciones no son consistentes? Por ejemplo, en la primera columna se han especificado valores de probabilidad. Debera prevalecer la informacin cualitativa? Convendra comprobar la consistencia de ambos tipos de informaciones c) Puede que alguna informacin cualitativa haya que usarla durante el proceso de evaluacin, por no estar reflejada en los potenciales originales. Por ejemplo, si los valores de Test1 y Test2 estn afectados por alguna restriccin, esta informacin est contenida en las distribuciones asociadas al nodo de utilidad, pero no es suficienteGranada, 2003
4. Asimetras (VII)Condici ones RTe st1 Test1 RTe st2 Test2 Compra
V a l o r Al eliminar Condiciones, he de combinar los potencialess en que aparece esta variable (mtodo de eliminacin de variables, aunqye ocurrira lo mismo con inversin de arcos): P(RTest1 | Condiciones, Test1) P(RTest2 | Condiciones, RTest1, Test2) P(Condiciones) para obtener (RTest1, RTest2, Condiciones, Test1, Test2)Granada, 2003
4. Asimetras (VIII)Sobre este potencial s que habra que aplicar la restriccin. En este caso no hay redundancia alguna.
d)
En este caso, es necesaria una fase de normalizacin. Se considera el siguiente ejemplo.A B C
a1 b1 b2 0.3 0.7
a2 0.9 0.1 c1 c2
b1 0.4 0.6
b2 0.55 0.45
Informacin cualitativa: A={a1} C={c2}
Granada, 2003
4. Asimetras (IX) Al eliminar la variable B, se han de combinar los potenciales en que esta variable participa: P(B | A) y P(C | B). Sobre este potencial resulta aplicable la restriccin
b1 a1 C c10. 1 2 0 . 3 0. 1 8
B b 2 a2 C a1 C c20. 3 9 0 . 7 0. 3 1
A
A
a2 C c10.055
c20. 3 6
c10. 5 4
c2 c1
c20.045
Granada, 2003
4. Asimetras (X)
b1 a1 C c10 ? 0.18 / (0.18 + 0.31)=0.367 ? 0.3 ?
B b 2 a2 C a1 C c20 ? 0.31 / (0.18 + 0.31)=0.633 ? 0.7 ?
A
A
a2 C c10.055
c20. 3 6
c10. 5 4
c2 c1
c20.045
La normalizacin slo es necesaria en caso de verse afectada un potencial de probabilidad. Para las utilidades, asignar un nuevo 0 significa marcar ese escenario como no recomendable (a la cola de las preferencias)
Granada, 2003
4. Asimetras (XI)
Clases para tratar las asimetras A) ValuesSet ValuesSetPermite definir un conjunto de valores para un nodo (deben estar incluidos en su dominio, aunque tambin pudiera ser vaco). El tipo de operacin a realizar se reduce a ver si un valor para la variable est incluido en este conjunto. Es decir, dado un valor xi para la variable X, esta clase permite determinar si
Node Vector
xi {x1 ,..., xk }Se puede establecer un flag de negacin, de forma que la comprobacin a realizar sera:
( xi {x1 ,..., xk })Granada, 2003
4. Asimetras (XII)Datos miembro: a) Node node b) Vector values c) boolean negated Mtodos: a) Constructor (Node, Vector, boolean) b) checkValue (String)
Este es el elemento bsico que permite componer expresiones lgicas, mediante las clases LogicalNode y LogicalExpression
Granada, 2003
4. Asimetras (XIII)
B) LogicalNode LogicalNodeDatos miembro: a) int kind (si el nodo es operador u operando) b) int operator (clase de operador: AND, OR, NOT, etc) c) boolean negated d) LogicalNode leftOperand e) LogicalNode rightOperand f) ValuesSet valuesSet g) Vector variables LogicalNode h) Vector index (operator) i) boolean result j) int observedValue
ValuesSet Vector
LogicalNode (operand)
LogicalNode (operand)
Granada, 2003
4. Asimetras (XIV)Mtodos: a) b) c) d) Constructor (int operator) Constructor (ValuesSet values) indexVariables evaluateConfiguration
La idea es que esta clase permita crear objetos que representen relaciones lgicas entre variables, para expresar las relaciones que se pueden establecer entre las variables del modelo. Por encima de esta clase est LogicalExpression, que vincula dos relaciones lgicas en el esquema clsico antecedente consecuente El antecedente y el consecuente son objetos de la clase LogicalNode
Granada, 2003
4. Asimetras (XV)
C) LogicalExpressionDatos miembro:
Potential
LogicalExpression
a) LogicalNode consecuent b) LogicalNode antecedent c) int operator d) Vector index e) PotentialTable result
LogicalExpression (operator) LogicalNode Vector PotentialTable LogicalNode (antecedent) LogicalNode (consecuent)
Granada, 2003
4. Asimetras (XVI)
Mtodos: a) b) c) d) Constructor (LogicalExpression, LogicalExpression) Constructor (LogicalNode, LogicalNode, int) evaluate buildIndex
El resultado es un PotentialTable que contiene todas las configuraciones vlidas segn esta restriccin. Del PotentialTable se puede pasar fcilmente a un PotentialTree, de forma que se pueda incorporar a la evaluacin de DI mediante rboles. Para mejorar el tratamiento de las restricciones se debera hacer una poda del PotentialTree, de forma que se redujera al mximo su tamao y la expresin de la restriccin fuera lo ms compacta posible.
Granada, 2003
4. Asimetras (XVII)
Expresin de restricciones en ElviraRelation var1 var2 var3 var4{ kind=constraint; values=logical-expression (var1 in {var11,var12} & !(var2 in {var21} | var3 not in {var33}) -> var4 in {var41}); }
Granada, 2003
4. Asimetras (XVIII) D) Clase ARWPTAndConstraints
Propagation
- Constructores: a) ARWPTAndConstraints(IDiagram)
ArcReversal
Mtodos
- Transformacin de relaciones b) transformInitialRelations: Este mtodo convierte los valores de utilidades y de PotentialTable a PotentialTree (se aplican las restricciones. Poda) b) transformAfterOperation: Ve si es necesario aplicar restricciones sobre un potencial sobre el que se operado (Poda)Granada, 2003
ARWPTAndConstraints
4. Asimetras (XIX) D) Clase VEWPTAndConstraints
Propagation
- Constructores: a) VEWPTAndConstraints(IDiagram)
VariableElimination
- Transformacin de relaciones b) transformInitialRelations: Este mtodo convierte los valores de utilidades y de PotentialTable a PotentialTree (se aplican las restricciones. Poda) b) transformAfterOperation: Ve si es necesario aplicar restricciones sobre un potencial sobre el que se operado (Poda)Granada, 2003
VEWPTAndConstraints
5.- AproximacinEn problemas complejos, pese a aprovechar todo el conocimiento del problema, los potenciales obtenidos pueden ser enormes. En esta situacin se puede aprovechar el uso de rboles reduciendo el nmero de hojas mediante aproximacin. La idea consiste en organizar el rbol, de forma que las variables ms significativas aparezcan cerca de la raz del rbol; la realizacin de una poda debe suponer la menor prdida posible de informacin
Granada, 2003
5. Aproximacin (II)
rboles de probabilidad: medida de significacin: distancia de Kullback-Leibler rboles de utilidad: medida de significacin?: mtrica L2 (raz cuadrada de las diferencias al cuadrado entre las utilidades de las configuraciones en los rboles podado y expandido) x1 1 0 0 y1 Y X x2 Y y2 X x2 5 3 Y y 2 6 6Granada, 2003
y2 y1 3 9 5
9 7
x1 67 5
y1 54 5
5. Aproximacin (III)
x1 1 0 0 y1 Y
X x2 Y y2
y2 y1 3 9 52
9 72
x1 67 5
X x2 5 3
( 67'5 100) + ( 67'5 35) + ( 53 9) + ( 53 97 ) = 77'352 2
y1 54 5
Y y2 6 62 2 2 2
( 54'5 100) + ( 54'5 9) + ( 66 35) + ( 66 97 ) = 77'86Granada, 2003
5. Aproximacin (IV)
Otra posible medida estara relacionada con la proximidad de los nodos hoja. Se permite la poda en el caso en que la distancia sea menor que un cierto valor umbral.
x1 1 0 0 y1 Y
X x2 Y y2
y2 y1 9 9 7
6 3
x1 X x2 98 5 y Y y 1 2 9
6 3Granada, 2003
5. Aproximacin (V)
Desligar los dos aspectos? a) Reordenacin de variables, de forma que las ms significativas aparezcan ms arriba (intento de reducir la distancia de utilidad entre los nodos hoja). Esta informacin podra usarse con fines de explicacin b) Podas sobre nodos hoja. Slo se poda si hay proximidad entre los valores (intento de modificar en la menor medida la funcin de utilidad original)
Granada, 2003
6.- SimulacinEn desarrollo. Idea: abordar problemas muy complejos. Se obtendr una poltica (no ptima), especialmente relacionada con las situaciones ms usuales.
Granada, 2003