Granada, 2003

Diagramas de influencia enElvira II

Granada, 2003

ÍNDICE1.- Diagramas de Influencia

2.- Métodos de evaluación

3.- Clases disponibles

4.- Asimetrías

5.- Aproximación

6.- Simulación

Granada, 2003

1.- Diagramas de influencia

Los diagramas de influencia permiten representar problemas de decisión, tal y como los percibe el decisor: incertidumbre, acciones a tomar y preferencias. Representación + evaluación.

Los diagramas de influencia son grafos dirigidos y acíclicos, con tres tipos de nodos:

•nodos de azar

•nodos de decisión

•nodos de valor

determinísticos

Granada, 2003

1. Diagramas de Influencia (II)

Nodos de azar: variables aleatorias o eventos aleatorios influyentes en el proceso de toma de decisión. Si el nodo es determinístico, su valor queda “fijado” al conocer los valores de sus predecesores

Nodos de decisión: 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 decisión. Informacióndisponible en el momento de decidir

•condicionales: inciden sobre nodos de azar y sobre el(los) nodo(s) de utilidad. Representan dependencia probabilística (o funcional)entre nodos (y no necesariamente causalidad)

Tratamiento

CBrb Ingreso

EdadPeso

CBrbCHmgb

Enf1 Enf2

Daño

EdadPeso

Granada, 2003

Coste

total

Coste1

Coste2

Coste3

Distribuciones: P(Coste 1|.....)P(Coste 2|.....)P(Coste 3|.....)

Función: Coste totalk1*(Coste 1) + k2*(Coste 2) + k3*(Coste 3)

V1 V2 V3

D1

D2

Utilidad V1 V2 V3 D1 D2------------------------------------------- 100 v11 v21 v31 d11 d21 39 v11 v21 v31 d11 d22..........................................................

45 v1n v2m v3p d1q d2r

1. Diagramas de Influencia (IV)

Granada, 2003

Métodos de evaluación

•evaluación directa (Shachter, Shachter y Peot, Zhang y Poole, Zhang et al, etc). Idea original: Olmsted (1983)

•evaluación indirecta : transforman previamente el DI en alguna otra estructura : árboles de decisión, grafos de decisión, redes bayesianas, ... (Howard y Matheson, Cooper, Qi y Poole, Qi, etc)

•métodos aproximados: mediante simulación (Shenoy, Bielza, Ortiz, ...), mediante aproximaciones sucesivas (Horsch & Poole), ...

1. Diagramas de Influencia (V)

Granada, 2003

2.- Métodos de evaluaciónA) Método de inversión de arcos

Mientras haya antecesores del nodo de valor

- Eliminar nodo de azar

(herencia sobre el nodo de valor)

xx

vv '

X

A B

U

A B

UU(X) U(A,B))

Granada, 2003

- Eliminar nodo de decisión: vxv max '

A BU

XC

A BU

C

U(X, A, B) U(A, B)

Sumidero

2. Métodos de evaluación (II)

Granada, 2003

- Invertir arco: (previo a eliminación de nodo de azar)

A B

D

C

F

EU

A B

D

C

F

EU

P(A|C, D)P(B|A, E, F)

P(A|B, C, D, E, F)P(B|C, D, E, F)

iixFEABPDCAPFEDCBP

FEDCBP

FEABPDCAPFEDCBAP

),,|(),|(),,,|(

),,,|(

),,|(),|(),,,,|(

2. Métodos de evaluación (III)

Granada, 2003

Resultados:

•tablas de decisión (política óptima)

•distribuciones a poteriori de todas las variables antes de eliminarlas (recogen la incertidumbre actualizada sobre las variables; interesante en tareas de diagnóstico)

Inconveniente:

•elevado coste computacional

2. Métodos de evaluación (IV)

Granada, 2003

B) Método de eliminación de variables

- Determinar orden temporal, en función de los arcos informativos

nn IDIDI ...110

In: los nodos que no son antecesores de ningún nodo de decisión

In-1: nodos antecesores de Dn

.......................................................

I0: nodos antecesores de D1

2. Métodos de evaluación (V)

Granada, 2003

Se van seleccionando variables a eliminar respetandoel orden parcial anteriormente determinado. Cuandose selecciona una variable X, los potenciales se actualizan de la siguiente forma:

} |{

} |{

domX

domX

X

X

Si X es una variable de azar:

)(

XX

XX

XXX

2. Métodos de evaluación (VI)

Granada, 2003

2. Métodos de evaluación (VII)

Si X es una variable de decisión:

)(

XXXX

XXX

max

max

El conjunto final de potenciales, tras la eliminación deX queda:

X

XX

XX

}\{

}{}\{

Granada, 2003

2. Métodos de evaluación (VIII)

Resultados:

•tablas de decisión (política óptima)

•no obtiene las distribuciones a posteriori de las variables a eliminar

Ventaja:

•mucho menor coste computacional

Granada, 2003

C) Métodos aproximados

Objetivo: evaluar problemas muy complejos, las tablas de decisión incluyen muchas variables (explosión combinatoria)

Simulación:

- instanciar variables, reducción de la complejidad del problema (casos)

- aproximación anytime. Obtener solución inicial y mejorar sucesivamente

2. Métodos de evaluación (IX)

Granada, 2003

3.- Clases disponibles en Elvira

A) Clase IDiagram

Bnet

IDiagram

- Comprobación de características y acceso a nodos:a) hasCyclesb) directedLinksc) pathBetweenDecisionsd) onlyOneValueNode

e) numberOfDecisionsMétodos f) decisionReadyToRemove

g) firstDecisionh) getDecisionListi) getBarrenNodej) getValueNodek) getNodel) getProblemSize

Granada, 2003

- Manipulación sobre el DI:

m) addNonForgettingArcsn) eliminateRedundancyñ) removeBarrenNodeso) addLinks

Métodosp) copyq) qualitativeCopyr) evaluate (mediante ArcReversal)s) savet) print

3. Clases disponibles en Elvira (II)

Granada, 2003

B) Clase ArcReversal

3. Clases disponibles en Elvira (III)

Propagation

ArcReversal

- Constructores:

a) ArcReversal()b) ArcReversal(IDiagram)

- Comprobación de características y acceso

c) getInitialRelationsMétodos d) initialConditions

- Evaluación y manipulación del DI

e) evaluateDiagramf) removeChanceNodeg) removeDecisionNodeh) reverseArci) modifyUtilityRelationj) modifyUtilityLinks

IDiagram

RelationList

Granada, 2003

3. Clases disponibles en Elvira (IV)

- Evaluación y manipulación del DI

k) modifyRelations l) modifyLinks m) getExpectedUtility n) maximizeUtility ñ) getPosteriorDistributions o) storeDecisionTable p) giveInstantiationOrder q) getMarginalsNames r) checkInstantiationOrder s) variablesInDecisionTables

Granada, 2003

C) Clase QualitativeArcReversl

3. Clases disponibles en Elvira (V)

Propagation

ArcReversal

QualitativeArcReversal

- Constructores:

a) QualitativeArcReversal(IDiagram)

- Acceso a datos miembro

b) getOrderOfEliminationMétodos c) getOrderOfInstantiation

- Evaluación y manipulación del DI

d) produceOrderOfInstantiatione) evaluateDiagram

f) removeChanceNodeg) removeDecisionNodeh) reverseArc

Granada, 2003

D) Clase ARWithPotentialTree

3. Clases disponibles en Elvira (VI)

Propagation

ArcReversal

ARWithPotentialTree

- Constructores:

a) ARWithPotentialTree(IDiagram)

- Transformación de relacionesMétodos

b) transformInitialRelations: Este método convierte los valores de utilidades y de PotentialTable a PotentialTree (con la posibilidad de aplicar los métodos de árboles que permiten aproximar)

Granada, 2003

E) Clase VariableElimination Funcionalidad compartida para redes Bayesianas y diagramas de influencia

3. Clases disponibles en Elvira (VII)

- Métodos relacionados con DI

a) getPosteriorDistributionsIDb) combinePotentialsOfNodec) propagate

Incorporación de método nextToRemoveId en la clase PairTable, que determina la próxima variable a eliminar.

Este método de evaluación no altera la estructura del diagrama: trabaja con sus potenciales, sobre una copia de las relaciones.

Propagation

VariableElimination

Granada, 2003

F) Clase VEWithPotentialTree

3. Clases disponibles en Elvira (VIII)

Propagation

VariableElimination

VEWithPotentialTree

- Constructores:

a) VEWithPotentialTree(Bnet,Evidence)a) VEWithPotentialTree(Bnet)

- Transformación de relacionesMétodos

b) transformInitialRelations: Este método convierte los valores de utilidades y de PotentialTable a PotentialTree (con la posibilidad de aplicar los métodos de árboles que permiten aproximar)

Granada, 2003

4.- AsimetríasPara ciertos valores de algunas variables, los posibles valores de otra variable están restringidos. Esta información cualitativa se puede representar como una matriz de restricciones (definida sobre las variables afectadas).

Y1 Y2 ....... Yn

------------------------------------------- X1 1 0 ....... 0 X2 1 1 ....... 0..........................................................

Xm 0 1 ....... 1

El tratamiento de las restricciones simplifica la evaluación (sólo evalúa configuraciones válidas)

X

Y Y

1 0 0 1

x1 x2

y1 y2 y1 y2

Granada, 2003

Objetivos de la representación de asimetrías:

a) forma general, de forma que se pueda expresar cualquier tipo de relación. Expresiones lógicasb) las restricciones, asimetrías, se convierten en potenciales que se utilizan en la evaluación del DIc) si como soporte de la información cualitativa se

usan árboles, es posible realizar podasd) la aplicación de restricciones, en determinados

casos, puede hacer posible la aplicación de nuevas podas

4. Asimetrías (II)

Granada, 2003

Consideraciones sobre las asimetrías:

a) parte de la información cualitativa estará recogida en las distribuciones (probabilidad – utilidad) iniciales. Esto ocurre en el caso en que las variables afectadas por la restricción formen parte del dominio de las distribuciones. Por ejemplo:

4. Asimetrías (III)

Test1 Test2 Compra

Valor

RTest1 RTest2

Condiciones

Granada, 2003

Resultados del primer test:

P(RTest1 | Test1, Condiciones)

NoTestbien

NoTestmal

Frenosbien

Frenosmal

Electric.bien

Electric.mal

Sin resul. 1 1 0 0 0 0

0 defectos 0 0 0.9 0.4 0.8 0.13

1 defecto 0 0 0.1 0.6 0.2 0.53

2 defectos 0 0 0 0 0 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}

4. Asimetrías (IV)

Granada, 2003

Procedimiento:

1) extraer del experto la información cualitativa2) reducir con ella el número de parámetros a

obtener3) al usar árboles, aplicar poda para reducir el

número de valores a almacenar. En el ejemplo anterior, se podría hacer que las ramas asociadas a Test1 = no Test (correspondientes a los dos posibles valores de Condiciones), se podrían unir en 1 (son idénticas)

4) mantener estas dos informaciones supone cierta redundancia

4. Asimetrías (V)

Granada, 2003

b) ¿Qué ocurre si estas informaciones no son consistentes? Por ejemplo, en la primera columna se han especificado valores de probabilidad. ¿Debería prevalecer la información cualitativa? Convendría comprobar la consistencia de ambos tipos de informaciones

c) Puede que alguna información cualitativa haya que usarla durante el proceso de evaluación, por no estar reflejada en los potenciales originales. Por ejemplo, si los valores de Test1 y Test2 están afectados por alguna restricción, esta información está contenida en las distribuciones asociadas al nodo de utilidad, pero no es suficiente

4. Asimetrías (VI)

Granada, 2003

Test1 Test2 Compra

Valor

RTest1 RTest2

Condiciones

Al eliminar Condiciones, he de combinar los potencialess en que aparece esta variable (método de eliminación de variables, aunqye ocurriría lo mismo con inversión de arcos):

P(RTest1 | Condiciones, Test1)P(RTest2 | Condiciones, RTest1, Test2)P(Condiciones)

para obtener Ф(RTest1, RTest2, Condiciones, Test1, Test2)

4. Asimetrías (VII)

Granada, 2003

Sobre este potencial sí que habría que aplicar la restricción. En este caso no hay redundancia alguna.

d) En este caso, es necesaria una fase de normalización. Se considera el siguiente ejemplo.

A B C

a1 a2

b1 0.3 0.9

b2 0.7 0.1

b1 b2

c1 0.4 0.55

c2 0.6 0.45

Información cualitativa: A={a1} → C={c2}

4. Asimetrías (VIII)

Granada, 2003

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 restricción

B

A A

C C C C

b1 b2

a1 a2 a1 a2

0.12 0.18 0.36 0.54 0.39 0.31 0.055 0.045

c1 c2 c1 c2 c1 c2 c1 c2

0.3 0.7

4. Asimetrías (IX)

Granada, 2003

La normalización sólo 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)

B

A A

C C C C

b1 b2

a1 a2 a1 a2

0 ? 0.36 0.54 0 ? 0.055 0.045

c1 c2 c1 c2 c1 c2 c1 c2

¿ 0.18 / (0.18 + 0.31)=0.367 ?¿ 0.3 ?

¿ 0.31 / (0.18 + 0.31)=0.633 ?¿ 0.7 ?

4. Asimetrías (X)

Granada, 2003

ValuesSet

Node

Permite definir un conjunto de valores para un nodo (debenestar incluidos en su dominio, aunque también pudiera servacío). El tipo de operación a realizar se reduce a ver si unvalor para la variable está incluido en este conjunto.

Es decir, dado un valor xi para la variable X, esta clasepermite determinar si

Se puede establecer un flag de negación, de forma que lacomprobación a realizar sería:

Clases para tratar las asimetrías

A) ValuesSet

Vector},...,{ 1 ki xxx

}),...,{( 1 ki xxx

4. Asimetrías (XI)

Granada, 2003

Datos miembro:

a) Node nodeb) Vector valuesc) boolean negated

Métodos:

a) Constructor (Node, Vector, boolean)b) checkValue (String)

Este es el elemento básico que permite componer expresiones lógicas,mediante las clases LogicalNode y LogicalExpression

4. Asimetrías (XII)

Granada, 2003

LogicalNode

ValuesSet

Datos 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 h) Vector index i) boolean result j) int observedValue

B) LogicalNode

Vector LogicalNode(operator)

LogicalNode(operand)

LogicalNode(operand)

4. Asimetrías (XIII)

Granada, 2003

Métodos:

a) Constructor (int operator)b) Constructor (ValuesSet values)c) indexVariablesd) evaluateConfiguration

La idea es que esta clase permita crear objetos que representen relacioneslógicas entre variables, para expresar las relaciones que se pueden establecerentre las variables del modelo. Por encima de esta clase está LogicalExpression,que vincula dos relaciones lógicas en el esquema clásico

antecedente consecuente

El antecedente y el consecuente son objetos de la clase LogicalNode

4. Asimetrías (XIV)

Granada, 2003

LogicalExpression

LogicalNode

Datos miembro:

a) LogicalNode consecuent b) LogicalNode antecedent c) int operator d) Vector index e) PotentialTable result

C) LogicalExpression

Vector

LogicalExpression(operator)

LogicalNode(antecedent)

LogicalNode(consecuent)

4. Asimetrías (XV)

Potential

PotentialTable

Granada, 2003

Métodos:

a) Constructor (LogicalExpression, LogicalExpression)b) Constructor (LogicalNode, LogicalNode, int)c) evaluated) buildIndex

El resultado es un PotentialTable que contiene todas las configuraciones válidassegún esta restricción. Del PotentialTable se puede pasar fácilmente a unPotentialTree, de forma que se pueda incorporar a la evaluación de DI medianteárboles. Para mejorar el tratamiento de las restricciones se debería hacer unapoda del PotentialTree, de forma que se redujera al máximo su tamaño y laexpresión de la restricción fuera lo más compacta posible.

4. Asimetrías (XVI)

Granada, 2003

Expresión de restricciones en Elvira

Relation var1 var2 var3 var4{ kind=constraint; values=logical-expression (var1 in {var11,var12} & !(var2 in {var21} | var3 not in {var33}) -> var4 in {var41});}

4. Asimetrías (XVII)

Granada, 2003

4. Asimetrías (XVIII)

D) Clase ARWPTAndConstraints

Propagation

ArcReversal

ARWPTAndConstraints

- Constructores:

a) ARWPTAndConstraints(IDiagram)

- Transformación de relacionesMétodos

b) transformInitialRelations: Este método 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

4. Asimetrías (XIX)

D) Clase VEWPTAndConstraints

Propagation

VariableElimination

VEWPTAndConstraints

- Constructores:

a) VEWPTAndConstraints(IDiagram)

- Transformación de relaciones

b) transformInitialRelations: Este método 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

5.- Aproximación

En problemas complejos, pese a aprovechar todo el conocimiento del problema, los potenciales obtenidos pueden ser enormes. En esta situación se puede aprovechar el uso de árboles reduciendo el número de hojas mediante aproximación.

La idea consiste en organizar el árbol, de forma que las variables más significativas aparezcan cerca de la raíz del árbol; la realización de una poda debe suponer la menor pérdida posible de información

Granada, 2003

Árboles de probabilidad:

medida de significación: distancia de Kullback-Leibler

Árboles de utilidad:

¿medida de significación?: métrica L2 (raíz cuadrada de las diferencias al cuadrado entre las utilidades de las configuraciones en los árboles podado y expandido)

X

Y Y

100 35 9 97

x1 x2

y1 y2 y1 y2

X

67’5 53

x1 x2Y

54’5 66

y1 y2

5. Aproximación (II)

Granada, 2003

X

Y Y

100 35 9 97

x1 x2

y1 y2 y1 y2

X

67’5 53

x1 x2

35'779753953355'671005'67 2222

Y

54’5 66

y1 y2

86'779766356695'541005'54 2222

5. Aproximación (III)

Granada, 2003

5. Aproximación (IV)

Otra posible medida estaría 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.

X

Y Y

100 97 9 63

x1 x2

y1 y2 y1 y2

X

98’5

x1 x2

Y

9 63

y1 y2

Granada, 2003

5. Aproximación (V)

¿Desligar los dos aspectos?

a) Reordenación de variables, de forma que las más significativas aparezcan más arriba (intento de reducir la distancia de utilidad entre los nodos hoja). Esta información podría usarse con fines de explicación

b) Podas sobre nodos hoja. Sólo se poda si hay proximidad entre los valores (intento de modificar en la menor medida la función de utilidad original)

Granada, 2003

6.- Simulación

En desarrollo. Idea: abordar problemas muy complejos. Se obtendrá una política (no óptima), especialmente relacionada con las situaciones más usuales.