sesión 13: técnicas alternativas a b c f dh. incertidumbre - t.a., l.e. sucar2 técnicas...

Sesión 13: Técnicas Alternativas

A

BC

F

D H

Incertidumbre - T.A., L.E. Sucar 2

Técnicas Alternativas• Se han desarrollado algunas técnicas

numéricas para manejo de incertidumbre que no siguen los axiomas de probabilidad. Entre éstas se encuentran:

• Métodos empíricos o ad-hoc

• Teoría de Dempster-Shafer

• Lógica difusa

• Métodos aproximados

Incertidumbre - T.A., L.E. Sucar 3

Técnicas Alternativas• Algunas técnicas se pueden ver como casos

especiales o extensiones de probabilidad• Técnicas que se reducen a casos especiales

de probabilidad– Método de factores de certeza (MYCIN)– Método de pseudo-probabilidades subjetivas

(Prospector)

• Técnicas que extienden a probabilidad:– Teoría de Dempster-Shafer

Incertidumbre - T.A., L.E. Sucar 4

Las primeras técnicas que surgen, cuando menos dentro del área de sistemas expertos, son técnicas empíricas o ad-hoc orientadas aresolver aplicaciones específicas y sin un fuerte fundamento teórico.

Las más conocidas son las que corresponden a dos de los primeros sistemas expertos:

Las primeras técnicas que surgen, cuando menos dentro del área de sistemas expertos, son técnicas empíricas o ad-hoc orientadas aresolver aplicaciones específicas y sin un fuerte fundamento teórico.

Las más conocidas son las que corresponden a dos de los primeros sistemas expertos:

Técnicas empíricasTécnicas empíricas

Incertidumbre - T.A., L.E. Sucar 5

• PROSPECTOR (exploración minera) • PROSPECTOR (exploración minera)

• MYCIN (diagnóstico de enfermedades infecciosas en la sangre)

• MYCIN (diagnóstico de enfermedades infecciosas en la sangre)

Incertidumbre - T.A., L.E. Sucar 6

Sistemas basados en reglas Sistemas basados en reglas

En sistemas basados en reglas se tiene en general una estructura similar a la siguiente:

En sistemas basados en reglas se tiene en general una estructura similar a la siguiente:

Incertidumbre - T.A., L.E. Sucar 7

Si: se observa cierta evidencia E Entonces: se concluye cierta hipótesis H con probabilidad (certeza, ...) P

Si: se observa cierta evidencia E Entonces: se concluye cierta hipótesis H con probabilidad (certeza, ...) P

• ¿Cómo obtener estas medidas? • ¿Cómo combinar estas medidas? • ¿Cómo interpretar estas medias?

• ¿Cómo obtener estas medidas? • ¿Cómo combinar estas medidas? • ¿Cómo interpretar estas medias?

De aquí surgen varias interrogantes:De aquí surgen varias interrogantes:

Incertidumbre - T.A., L.E. Sucar 8

Las técnicas desarrolladas en MYCIN y Prospector son similares, ambas consideran sistemas basados en reglas a los que se les adicionan Factores de Certeza o Probabilidades Subjetivas, respectivamente.

Veremos brevemente el método de MYCIN.

Las técnicas desarrolladas en MYCIN y Prospector son similares, ambas consideran sistemas basados en reglas a los que se les adicionan Factores de Certeza o Probabilidades Subjetivas, respectivamente.

Veremos brevemente el método de MYCIN.

MYCIN MYCIN

Incertidumbre - T.A., L.E. Sucar 9

Técnica de Factores de Certeza

• Los autores de MYCIN dicidieron no aplicar probabilidad porque:– “... requiere de grandes cantidades de datos o

numerosas aproximaciones y suposiciones”

• Desarrollaron una técnica alternativa basada en factores de certeza (medidas no probabilistas) y técnicas para combinarlas

Incertidumbre - T.A., L.E. Sucar 10

Medidas básicas

• MB[h,e] – incremento de la creencia en la hipótesis h dada la evidencia e

• MD[h,e] – incremento en la no-creencia en la hipótesis h dada la evidencia e

• Se pueden combinar en una sola medida, el factor de certeza: CF = MB – MD

0 MB,MD 1 CF : [-1, +1]

Incertidumbre - T.A., L.E. Sucar 11

MYCIN define un Factor de Certeza que se asocia a cada regla y cada evidencia, y se definen un conjunto de reglas para combinar estos factores.

MYCIN define un Factor de Certeza que se asocia a cada regla y cada evidencia, y se definen un conjunto de reglas para combinar estos factores.

Incertidumbre - T.A., L.E. Sucar 12

Redes de Inferencia• Un conjunto de reglas se pueden ver como una

“red de inferencia”• Por ejemplo:

– R1: si A y B entonces C– R2: si C entonces D– R3: si F entonces D– R4: si D entonces H

A

BC

F

D H

Incertidumbre - T.A., L.E. Sucar 13

Redes de Inferencia• Tipos de combinaciones:

– Conjunción/disjunción

– Serie

– ParaleloF

D H

A

BC

C

C

Incertidumbre - T.A., L.E. Sucar 14

Reglas de combinaciónReglas de combinación

1. Propagación (fprop) o reglas en serie:1. Propagación (fprop) o reglas en serie:

2. AND (conjunción), OR (disjunción) de evidencias:2. AND (conjunción), OR (disjunción) de evidencias:

Incertidumbre - T.A., L.E. Sucar 15

3. Co-Conclusión (fco) o reglas en paralelo:

Incertidumbre - T.A., L.E. Sucar 16

R1: IF A and (B or C) Then H cf 0.8 R2: If D and F Then B cf 0.6 R3: If F or G Then H cf 0.4 R4: If A Then D cf 0.75 R5: If I Then G cf 0.3

R1: IF A and (B or C) Then H cf 0.8 R2: If D and F Then B cf 0.6 R3: If F or G Then H cf 0.4 R4: If A Then D cf 0.75 R5: If I Then G cf 0.3

EjemploEjemplo

Se conoce: CF(A,Ev) = 1, CF(C,Ev) = 0.5, CF(F,Ev) = 0.7, CF(I,Ev) = -0.4

Se conoce: CF(A,Ev) = 1, CF(C,Ev) = 0.5, CF(F,Ev) = 0.7, CF(I,Ev) = -0.4

Incertidumbre - T.A., L.E. Sucar 17

Ejemplo CF

B

C

F

DH-1

A

GH-2

I

0.80.6

H

0.4

0.75

0.3

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

Incertidumbre - T.A., L.E. Sucar 18

Ejemplo CF

B

C

F

DH-1

A

GH-2

I

0.80.6

H

0.4

0.75

0.3x0=0

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

Incertidumbre - T.A., L.E. Sucar 19

Ejemplo CF

B

C

F

DH-1

A

GH-2

0.80.6

H

0.4

0.75

0

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

0.7

Max[0.7,0]x0.4=0.28

Incertidumbre - T.A., L.E. Sucar 20

Ejemplo CF

B

C

F

DH-1

A

H-2

0.80.6

H

0.75

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

0.7

0.28

0.75x1=0.75

Incertidumbre - T.A., L.E. Sucar 21

Ejemplo CF

B

C

F

DH-1

A

H-2

0.80.6

H

0.75

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

0.7

0.28Min[0.75,0.7]x0.6=0.42

Incertidumbre - T.A., L.E. Sucar 22

Ejemplo CF

B

C H-1A

H-2

0.8

H

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

0.28

0.42

min[1,max[0.5,0.42]]x0.8=0.4

Incertidumbre - T.A., L.E. Sucar 23

Ejemplo CFH-1

H-2H

CF(A,Ev) = 1,

CF(C,Ev) = 0.5,

CF(F,Ev) = 0.7,

CF(I,Ev) = -0.4

0.28

0.4

0.4+0.28-(0.4)(0.28)=0.568

Incertidumbre - T.A., L.E. Sucar 24

Aplicación - MYCIN• Ejemplo de regla de MYCIN:

SI la clase de organismo es gram positivo & la morfología del organismo es coco & la forma de crecimiento es cadenas

ENTONCESla identidad del organismo es

estreptococo (CF=0.7)

Incertidumbre - T.A., L.E. Sucar 25

Ventajas

• Modularidad

• Simplicidad computacional

• Resultados comparables con expertos en aplicación médica (MYCIN)

• Poco sensitivo a los valores de los CF´s (variación de +/- 0.2)

Incertidumbre - T.A., L.E. Sucar 26

Aunque pretendía apartarse de probabilidad, se ha demostrado [Heckerman 86] que la técnica de MYCIN corresponde a un subconjunto de probabilidad con una serie de suposiciones implícitas:

Aunque pretendía apartarse de probabilidad, se ha demostrado [Heckerman 86] que la técnica de MYCIN corresponde a un subconjunto de probabilidad con una serie de suposiciones implícitas:

Desventajas: Desventajas:

Incertidumbre - T.A., L.E. Sucar 27

• La evidencia es condicionalmente independiente de la hipótesis y su negación. • La red de inferencia debe corresponder a un árbol para que los resultados sean coherentes. • Las fórmulas para conjunción y disjunción (min y max ) sólo son válidas si uno de los términos es subconjunto del otro.

• La evidencia es condicionalmente independiente de la hipótesis y su negación. • La red de inferencia debe corresponder a un árbol para que los resultados sean coherentes. • Las fórmulas para conjunción y disjunción (min y max ) sólo son válidas si uno de los términos es subconjunto del otro.

Incertidumbre - T.A., L.E. Sucar 28

Estas suposiciones no son válidas en muchas aplicaciones por lo que el método de MYCIN no se puede generalizar.

Estas suposiciones no son válidas en muchas aplicaciones por lo que el método de MYCIN no se puede generalizar.

Teoría de Dempster-Shafer

Incertidumbre - T.A., L.E. Sucar 30

AntecedentesTeoría para representar y combinar “grados de creencia”.  

Esta teoría se desarrollo básicamente como una alternativa (extensión) a teoría de probabilidad ya que los autores consideraban que ciertas situaciones no eran representadas adecuadamente con dicha teoría. En especial dos aspectos:

• Representación de ''ignorancia"• Representación de creencia NO asignada

Incertidumbre - T.A., L.E. Sucar 31

Ejemplo• Se tiene una moneda y dos situaciones distintas:

1. La moneda es “normal” por lo que tiene la misma probabilidad de cada lado

2. Se sabe que la moneda esta cargada con una mayor probabilidad de uno de los lados, pero no se sabe cual ni cuanto

• Con probabilidades ambas situaciones se representan igual – P=0.5, no hay forma de distinguir ignorancia de igual probabilidad

Incertidumbre - T.A., L.E. Sucar 32

La teoría de DS difiere en dos aspectos básicos de la teoría clásica de probabilidad:

• Los grados de creencia se asignan a subconjuntos en lugar de a elementos individuales del dominio de referencia.

• El axioma de aditividad no se forza, sino se substituye por una desigualdad.

Diferencias con Probabilidad

Incertidumbre - T.A., L.E. Sucar 33

Diferencias con ProbabilidadEstas diferencias tiene dos importantes implicaciones:

 1.- La creencia en una proposición y su complemento NO necesariamente suman “1”.

 2.- Se diferencia ignorancia de probabilidades iguales, dando la creencia no asignada al conjunto de todas las hipótesis.

Incertidumbre - T.A., L.E. Sucar 34

Fundamentos TeóricosLa teoría de DS requiere de un conjunto de hipótesis exclusivas y exhaustivas:

Θ - marco de dicernimiento

2Θ - conjunto de todos los subconjuntos de Θ

En base a esto se definen dos medidas:

– asignación básica de probabilidad (bpa)

– función de creencia (Bel)

Incertidumbre - T.A., L.E. Sucar 35

Asignación básica de probabilidad (bpa)• Representa la porción de creencia asignada

exactamente a un elemento A (subconjunto de Θ), sin incluir la creencia asignada sus subconjuntos.

bpa=m(A): 2Θ ->[0,1]

• Debe satisfacer las siguientes propiedades:

1 >= m(A) >= 0 (1)m(ø) = 0 (2)

Σm(A)=1 (3)

Incertidumbre - T.A., L.E. Sucar 36

Ejemplo• Para el ejemplo de la moneda

Θ = {águila, sol}

2Θ = [ {águila,sol}, {águila}, {sol}, ]

• Caso 1: igual probabilidadm({águila}) = 0.5, m({sol}) = 0.5

• Caso 2: completa ignoranicam({águila,sol}) = 1

Incertidumbre - T.A., L.E. Sucar 37

Función de creencia (Bel)

• Es la creencia total en el conjunto A, incluyendo la creencia asignada propiamente a A, así como la de todos sus subconjuntos:

Bel(A)=Σm(B), B A

• Se puede demostrar que Bel satisface las siguientes propiedades:

Bel(ø) = 0Bel(Θ) = 1Bel(A1A2) >= Bel(A1) + Bel(A2) -

Bel(A1A2)

Incertidumbre - T.A., L.E. Sucar 38

Función de creencia (Bel)

• Para una hipótesis sencilla (un solo elemento) se tiene que:

Bel(A)=m(A)

• Para el ejemplo de la moneda:

– Caso 1:

• Bel({águila,sol}) = 0.5 + 0.5 = 1

• Bel({águila}) = m({águila}) = 0.5

Incertidumbre - T.A., L.E. Sucar 39

Regla de Dempster• Para combinar distintas evidencias se calcula su suma

ortogonal, aplicando lo que se conoce como la regla de Dempster, y obteniendo un nuevo grado de creencia (m) basado en la evidencia combinada:

• Esta formula la podemos interpretar de la siguiente forma:– La evidencia E1 asigna la creencia ml al subconjunto Al

– La evidencia E2 asigna la creencia m2 al subconjunto B1

– Entonces el producto de ambas (ml * m2) nos da la creencia en su intersección - A

ABjAi

ji BmAmAmm 2121

Incertidumbre - T.A., L.E. Sucar 40

Regla de Dempster• La creencia total en A es simplemente la suma de las

creencia asignadas de esta forma, es decir, la suma de la creencia de todas la intersecciones entre los conjunto Ai y Bj que den como resultado A.

• Surge un problema si alguna de las intersecciones de el conjunto vacío, ya que no se puede asignar creencia a dicho conjunto (implicaría que la suma de bpa no sea l). Para resolver este caso hay que normalizar los bpa, es decir, inflar las creencias de los demás subconjuntos en forma proporcional a la creencia asignada al conjunto vacío.

Incertidumbre - T.A., L.E. Sucar 41

Regla de Dempster• Entonces la regla de Dempster en su forma general

es:

• Los nuevos valores de Bel para cada hipótesis son calculados de la misma forma, sumando los bpa's.

BjAiji

ABjAi

ji

BmAmK

donde

Ak

BmAmAmm

21

2121

:

,1

Incertidumbre - T.A., L.E. Sucar 42

Ejemplo• Si hubiera dos evidencias (expertos lanza

monedas) respecto a la moneda cargada:– m1(A) = 0.7, m1(Θ) = 0.3– m2(S) = 0.6, m2 (Θ) = 04

• Entonces:m2 \ m1 {A} 0.7 {Θ} 0.3

{S} 0.6 {} 0.42 {S} 0.18{Θ} 0.4 {A} 0.28 {Θ} 0.12

Incertidumbre - T.A., L.E. Sucar 43

Ejemplo

• Normalizando:– k = 0.42 1-k = 0.58

• Entonces:– m1 m2({S}) = 0.18 / 0.58 = 0.31– m1 m2({A}) 0.28 / 0.58 = 0.483– m1 m2({Θ}) 0.12 / 0.58 = 0.207

Incertidumbre - T.A., L.E. Sucar 44

Posibilidad

• Mientras que Bel nos da la cantidad de creencia en cierta hipótesis, otra medida denominada la posibilidad (plausibility – Pl) indica la máxima creencia que pudiera asignarse a la hipótesis. La posibilidad se define como:

P1(A) = 1-Bel(~A)

• Bel da la creencia mínima y P1 la creencia máxima. Ambas definen un intervalo de creencia:

[Bel(A), P1(A)]

Incertidumbre - T.A., L.E. Sucar 45

Posibilidad

• El rango dentro del cual estaría la creencia en A de acuerdo a la evidencia conocida. La diferencia entre Bel y Pl nos indica la ignorancia, es decir, la creencia que NO ha sido asignada ni a la hipótesis ni a su complemento (o demás hipótesis).

Incertidumbre - T.A., L.E. Sucar 46

Ejemplo• Para el caso anterior:

– Pl({A}) = 1 – 0.310 = 0.690– Pl({S}) = 1 – 0.483 = 0.517

• Entonces:– A: [0.483 0.690]– S: [0.310 0.517]

Incertidumbre - T.A., L.E. Sucar 47

Otro Ejemplo• Consideremos una aplicación médica en la

que hay cuatro posibles enfermedades (hipótesis):– Hepatitis (h/hep)– Cirrosis (c/cirr)– Cálculos en la vesícula (v/gall)– Pancreatitis (p/pan)

Incertidumbre - T.A., L.E. Sucar 48

Ejemplo Médico• Marco de dicernimiento (hipótesis) - jerarquía:

Incertidumbre - T.A., L.E. Sucar 49

Ejemplo Médico - subconjuntos

Incertidumbre - T.A., L.E. Sucar 50

Ejemplo Médico• Evidencia 1:

intrahepática – 0.6

• Evidencia 2:

no hepatitis – 0.7

Incertidumbre - T.A., L.E. Sucar 51

Ejemplo Médico• A partir de las bpa se puede calcular el

grado de creencia – Bel, por ejemplo:

Bel(intrahepática) = Bel({hep,cerr}) =

m(hep,cerr) + m(hep) + m(cerr) =

0.18 + 0 + 0.42 = 0.60

Incertidumbre - T.A., L.E. Sucar 52

Ejemplo Médico• Evidencia 3:

hepatitis – 0.8

- pizarrón -

Incertidumbre - T.A., L.E. Sucar 53

Ejemplo Médico• Cálculo de bpa:

k = 0.336+0.224 = 0.56, 1-k = 0.44

m(hep) = (0.144+0.096)/0.44 = 0.545m(cirr) = 0.084/0.44 = 0.191m(hep,cirr) = 0.036/0.44 = 0.082m(cirr,gall,pan) = 0.056/0.44 = 0.127m(Θ) = 0.024/0.44 = 0.055

Incertidumbre - T.A., L.E. Sucar 54

Aplicaciones• En sistemas basado en reglas, cada una se

considera como una fuente de evidencia, y asigna un bpa a una o un conjunto de hipótesis.

• Los grados de creencia (m) de cada regla son asignados por el experto.

• Los grados de creencia de cada regla son combinados aplicando la regla de Dempster. Luego se calcula Bel y Pl para cada hipótesis, obteniendo así su intervalo de creencia.

Incertidumbre - T.A., L.E. Sucar 55

Ventajas

• Intervalo de creencia

• Representación de ignorancia

• Representa “la forma en que los expertos usan la evidencia”

• Modular

Incertidumbre - T.A., L.E. Sucar 56

Desventajas

• Asume fuentes de evidencia independientes

• Interpretación de los valores finales (Bel)

• Bel no se puede interpretar como frecuencias

• Complejidad computacional (hipótesis sencillas, redes)

Incertidumbre - T.A., L.E. Sucar 57

Referencias• Lucas & Van Der Gaag, Principles of Expert Systems,

Addison-Wesley, 1991 – Cap. 5

• Buchanan & Shortliffe, Ruled-Based Expert Systems, Addison-Weslev, 1984 - Cap 10-13.

• D. Heckerman, Probabilistic interpretations for MYCIN´s certainty factors, UAI, 1986

• Shafer, A Mathematical Theory of Evidence, Princeton Univ. Press. 1976.

Incertidumbre - T.A., L.E. Sucar 58

Actividades

• Hacer ejercicios de técnicas alternativas