Date post: | 23-Jan-2016 |
Category: |
Documents |
Upload: | bernardita-toro |
View: | 220 times |
Download: | 0 times |
Manejo de IncertidumbreManejo de Incertidumbre
Sesión 13Eduardo Morales / L. Enrique Sucar
Sesión 13Eduardo Morales / L. Enrique Sucar
Fundamentos de Inteligencia ArtificialFundamentos de Inteligencia Artificial
Los sistemas basados en conocimiento deben ser capaces de representar y razonar con incertidumbre.
Existen varias causas de incertidumbre que tienen que ver con la información, el conocimiento y la representación.
Los sistemas basados en conocimiento deben ser capaces de representar y razonar con incertidumbre.
Existen varias causas de incertidumbre que tienen que ver con la información, el conocimiento y la representación.
Introducción Introducción
• Incompleta • Poco confiable • Ruido, distorsión
• Incompleta • Poco confiable • Ruido, distorsión
Información Información
• Impreciso • Contradictorio • Impreciso • Contradictorio
Conocimiento Conocimiento
• No adecuada • Falta de poder descriptivo • No adecuada • Falta de poder descriptivo
RepresentaciónRepresentación
• Diagnóstico médico o industrial • Predicción financiera • Exploración minera / petrolera • Interpretación de imágenes (visión) • Reconocimiento de voz • Monitoreo / control de procesos industriales complejos • Robótica
• Diagnóstico médico o industrial • Predicción financiera • Exploración minera / petrolera • Interpretación de imágenes (visión) • Reconocimiento de voz • Monitoreo / control de procesos industriales complejos • Robótica
Ejemplos de dominios con incertidumbreEjemplos de dominios con incertidumbre
Ejemplo de Incertidumbre
• Un robot móvil tiene incertidumbre respecto a lo que obtiene de sus sensores y de su posición en el mundo
Si pierden varias propiedades de los sistemas que no tienen incertidumbre, basados en lógicas o reglas, lo cual hace el manejo deincertidumbre más complejo. Las principales dos características que, en general, ya no aplican son:
Si pierden varias propiedades de los sistemas que no tienen incertidumbre, basados en lógicas o reglas, lo cual hace el manejo deincertidumbre más complejo. Las principales dos características que, en general, ya no aplican son:
Efectos de Incertidumbre Efectos de Incertidumbre
1. Modularidad2. Monotonicidad1. Modularidad2. Monotonicidad
Un sistema de reglas es modular, ya que para saber la verdad de una regla sólo tiene que considerarla a ésta, sin importar el resto del conocimiento.
Pero si hay incertidumbre ya no puedo considerar la regla por si sola, debo tomar en cuenta otras reglas
Un sistema de reglas es modular, ya que para saber la verdad de una regla sólo tiene que considerarla a ésta, sin importar el resto del conocimiento.
Pero si hay incertidumbre ya no puedo considerar la regla por si sola, debo tomar en cuenta otras reglas
ModularidadModularidad
Un sistema es monotónico si al agregar nueva información a su base de datos, no se alteran las conclusiones que seguían de la base de datos original.
Un sistema es monotónico si al agregar nueva información a su base de datos, no se alteran las conclusiones que seguían de la base de datos original.
Monotonicidad Monotonicidad
Si hay incertidumbre ya no puedo considerar que la certeza en una hipótesis ya no puede cambiar, debo tomar en cuenta otras reglas que involucren a dicha hipótesis.
Si hay incertidumbre ya no puedo considerar que la certeza en una hipótesis ya no puede cambiar, debo tomar en cuenta otras reglas que involucren a dicha hipótesis.
• No-numéricas * Lógicas no-monotónicas * Sistemas de mantenimiento de verdad (TMS, ATMS) * Teoría de endosos
• No-numéricas * Lógicas no-monotónicas * Sistemas de mantenimiento de verdad (TMS, ATMS) * Teoría de endosos
Técnicas Técnicas
• Numéricas * Empíricas (MYCIN, Prospector) * Métodos aproximados * Lógica difusa * Teoría de Dempster-Shafer * Redes Bayesianas
• Numéricas * Empíricas (MYCIN, Prospector) * Métodos aproximados * Lógica difusa * Teoría de Dempster-Shafer * Redes Bayesianas
Técnicas Técnicas
Recordaremos algunos conceptos de probabilidad relevantes, en particular:Recordaremos algunos conceptos de probabilidad relevantes, en particular:
Conceptos de ProbabilidadConceptos de Probabilidad
• Probabilidad Condicional • Independencia • Teorema de Bayes
• Probabilidad Condicional • Independencia • Teorema de Bayes
Para cada h,e con P(e) 0, la probabilidadcondicional de h dado e o P(he) (probabilidad a posteriori) es:
Para cada h,e con P(e) 0, la probabilidadcondicional de h dado e o P(he) (probabilidad a posteriori) es:
Probabilidad Condicional Probabilidad Condicional
P(he) =P(he) =P(he)P(he)
P(e)P(e)
En la práctica P(he) no se obtiene fácilmente, sin embargo P(eh) sí.
Para obtenerla utilizamos el Teorema de Bayes:
En la práctica P(he) no se obtiene fácilmente, sin embargo P(eh) sí.
Para obtenerla utilizamos el Teorema de Bayes:
Teorema de Bayes Teorema de Bayes
P(he) =P(he) =P(eh) P ( h )P(eh) P ( h )
P(e)P(e)
Independencia marginal: P(h e)= P( h ). Independencia marginal: P(h e)= P( h ).
IndependenciaIndependencia
Los eventos e1,…,en son independientes si:Los eventos e1,…,en son independientes si:
Los eventos e1,…,en son condicionalmente independientes dado un evento h , si:Los eventos e1,…,en son condicionalmente independientes dado un evento h , si:
P(e1 ... en)= P(e1 ) … P(en )P(e1 ... en)= P(e1 ) … P(en )
P(e1 ... enh)= P(e1h) … P(en h )P(e1 ... enh)= P(e1h) … P(en h )
Independencia condicional: P(h ke)= P( h k). Independencia condicional: P(h ke)= P( h k).
Sean H ={ h1,…,hn} el conjunto de n posibles hipótesis y E ={e1,…,em }, m posibles evidencias. Si asuminos que la hipótesis y los eventos son V o F, lo que queremos encontrar es la h más probable dado e E.
Sean H ={ h1,…,hn} el conjunto de n posibles hipótesis y E ={e1,…,em }, m posibles evidencias. Si asuminos que la hipótesis y los eventos son V o F, lo que queremos encontrar es la h más probable dado e E.
Probabilidad en Sistemas Expertos Probabilidad en Sistemas Expertos
Se tiene que calcular P(he ) para cada subconjunto de h y seleccionar la de mayor probabilidad utilizando el teorema de Bayes.
Se tiene que calcular P(he ) para cada subconjunto de h y seleccionar la de mayor probabilidad utilizando el teorema de Bayes.
como
Opción 1: Exhaustivo
)()()|(
)|(ePhPheP
ehP
)()()|(
)|(eP
hPhePehP
1)|()|( ehPehP
)()|()()|()( hPhePhPhePeP
A esto se le llama normalización ya que
se toma como una constante que permite que los términos condicionales sumen 1.
A esto se le llama normalización ya que
se toma como una constante que permite que los términos condicionales sumen 1.
1P(e) 1P(e)
)()|()()|()()|(
)|(hPhePhPheP
hPhePehP
En general: En general:
Generalización Generalización
n
jjjjkj
iijkjjkji
hPheeP
hPheePeehP
11
11
)()|(
)()|()|(
Para aplicar Bayes, se requiere calcular las probabilidades condicionales P(ehi ) para cada combinación de evidencias (en generalno se pueden calcular de sus componentes individuales).
Esto implica que se tienen que conocer un número exponencial de probabilidades!!
Para aplicar Bayes, se requiere calcular las probabilidades condicionales P(ehi ) para cada combinación de evidencias (en generalno se pueden calcular de sus componentes individuales).
Esto implica que se tienen que conocer un número exponencial de probabilidades!!
Las evidencias son condicionalmente independientes.
Las evidencias son condicionalmente independientes.
Opción 2: independenciaOpción 2: independencia
Con ésto, solo se requieren m x n probabilidades condicionales y n - 1 probabilidades a priori.
Con ésto, solo se requieren m x n probabilidades condicionales y n - 1 probabilidades a priori.
n
llljklj
iijkijjkji
hPhePheP
hPhePhePeehP
11
11
)()|()|(
)()|()|()|(
En la opción 1 el sistema se vuelve demasiado complejo, mientras que la opción 2 puede no ser realista para muchas aplicaciones.
Una alternativa es buscar un compromiso entre ambos extremos, esto se logra mediante las redes Bayesianas.
En la opción 1 el sistema se vuelve demasiado complejo, mientras que la opción 2 puede no ser realista para muchas aplicaciones.
Una alternativa es buscar un compromiso entre ambos extremos, esto se logra mediante las redes Bayesianas.
Conclusión Conclusión
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 numéricasTécnicas numéricas
• 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)
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:
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 medidas?
• ¿Cómo obtener estas medidas?
• ¿Cómo combinar estas medidas?
• ¿Cómo interpretar estas medidas?
De aquí surgen varias interrogantes:De aquí surgen varias interrogantes:
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
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.
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 ( fand, for):2. AND (conjunción), OR (disjunción) de evidencias ( fand, for):
´),(,0max),(´),( eeCFehCFehCF
´),(´),,(max´),or (
´),(´),,(min´), and (
2121
2121
eeCFeeCFeeeCF
eeCFeeCFeeeCF
3. Co-Conclusión (fco) o reglas en paralelo:
2,1,0),( if
)),(1)(,(),(0),(),(1 if
|}),(||,),(min{|1),(),(
2,1,0),( if
)),(1)(,(),(
) co ,(
121
21
21
21
121
21
iehCF
ehCFehCFehCFehCFehCF
ehCFehCFehCFehCFiehCF
ehCFehCFehCF
eehCF
i
i
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
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:
• 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.
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.
Redes Bayesianas
Las redes bayesianas o probabilísticas son una representación gráfica de dependencias para razonamiento probabilístico, en la cual los nodos y arcos representan:
Las redes bayesianas o probabilísticas son una representación gráfica de dependencias para razonamiento probabilístico, en la cual los nodos y arcos representan:
IntroducciónIntroducción
• Nodo: Variable proposicional. • Arcos: Dependencia probabilística. • Nodo: Variable proposicional. • Arcos: Dependencia probabilística.
Una red probabilística (RP) es un grafo acíclico dirigido (DAG) en la cual cada nodo representa una variable y cada arco una dependencia probabilística, en la cual se especifica la probabilidad condicional de cada variable dados sus padres.
Una red probabilística (RP) es un grafo acíclico dirigido (DAG) en la cual cada nodo representa una variable y cada arco una dependencia probabilística, en la cual se especifica la probabilidad condicional de cada variable dados sus padres.
Definición:Definición:
La variable a la que apunta el arco es dependiente (causa-efecto) de la que está en el origen de éste.
La variable a la que apunta el arco es dependiente (causa-efecto) de la que está en el origen de éste.
1. Distribución de probabilidad: Representa la distribución de la probabilidad conjunta de las variables representadas en la red.
1. Distribución de probabilidad: Representa la distribución de la probabilidad conjunta de las variables representadas en la red.
Podemos interpretar a una RP de dos formas: Podemos interpretar a una RP de dos formas:
Por ejemplo: Por ejemplo:
)()()|(),|()|(
),,,,(
FBPFVPFBFAPFBFVFEPFENDP
NDFEFAFVFBP
2. Base de reglas: Cada arco representa un conjunto de reglas que asocian las variables involucradas, Por ejemplo:
Si FB,FV entonces FE
2. Base de reglas: Cada arco representa un conjunto de reglas que asocian las variables involucradas, Por ejemplo:
Si FB,FV entonces FE
Dichas reglas están cuantificadas por las probabilidades respectivas. Dichas reglas están cuantificadas por las probabilidades respectivas.
La topología o estructura de la red nos da información sobre las dependencias probabilísticas entre las variables.
La red también representa las independencias condicionales de una variable (o conjunto de variables) dada otra(s) variable(s).
La topología o estructura de la red nos da información sobre las dependencias probabilísticas entre las variables.
La red también representa las independencias condicionales de una variable (o conjunto de variables) dada otra(s) variable(s).
EstructuraEstructura
Ej.: {FA} es cond. indep. de {FV,FE,ND} dado {FB}
Esto es: P(FA | FV,FE,ND,FB)= P( FA | FB)
Ej.: {FA} es cond. indep. de {FV,FE,ND} dado {FB}
Esto es: P(FA | FV,FE,ND,FB)= P( FA | FB)
Esto se representa gráficamente por el nodo FB separando al nodo FA del resto de las variables.
Esto se representa gráficamente por el nodo FB separando al nodo FA del resto de las variables.
En general, el conjunto de variables A es independiente del conjunto B dado C si al remover C hace que A y B se desconecten.
Es decir, NO existe una trayectoria entre A y B en que las siguientes condiciones sean verdaderas.
En general, el conjunto de variables A es independiente del conjunto B dado C si al remover C hace que A y B se desconecten.
Es decir, NO existe una trayectoria entre A y B en que las siguientes condiciones sean verdaderas.
Verificación de IndependenciaVerificación de Independencia
1. Todos los nodos con flechas convergentes están o tiene descendientes en C.
2. Todos los demás nodos están fuera de C.
1. Todos los nodos con flechas convergentes están o tiene descendientes en C.
2. Todos los demás nodos están fuera de C.
Esto se conoce como Separación-D.Esto se conoce como Separación-D.
En una RP todas la relaciones de independencia condicional representadas en el grafo corresponden a relaciones de independencia en la distribución de probabilidad.
Dichas independencias simplifican la representación del conocimiento (menos parámetros) y el razonamiento (propagación de las probabilidades).
En una RP todas la relaciones de independencia condicional representadas en el grafo corresponden a relaciones de independencia en la distribución de probabilidad.
Dichas independencias simplifican la representación del conocimiento (menos parámetros) y el razonamiento (propagación de las probabilidades).
Complementa la definición de una red bayesiana las probabilidades condicionales de cada variable dados sus padres.
Nodos raíz: vector de probabilidades marginales
Otros nodos: matriz de probabilidades condicionales dados sus padres
Complementa la definición de una red bayesiana las probabilidades condicionales de cada variable dados sus padres.
Nodos raíz: vector de probabilidades marginales
Otros nodos: matriz de probabilidades condicionales dados sus padres
ParámetrosParámetros
P(FV)
P(FE|FV,FB)
P(FB)
P(FlV|FB)
P(ND|FE)
El razonamiento probabilístico o propagación de probabilidades consiste en propagar de los efectos de la evidencia a través de la red paraconocer la probabilidad a posteriori de las variables.
El razonamiento probabilístico o propagación de probabilidades consiste en propagar de los efectos de la evidencia a través de la red paraconocer la probabilidad a posteriori de las variables.
Propagación de ProbabilidadesPropagación de Probabilidades
La propagación consiste en darle valores a ciertas variables (evidencia), y obtener la probabilidad posterior de las demás variables dadas las variables conocidas (instanciadas).
La propagación consiste en darle valores a ciertas variables (evidencia), y obtener la probabilidad posterior de las demás variables dadas las variables conocidas (instanciadas).
Los algoritmos de propagación dependen de la estructura de la red:Los algoritmos de propagación dependen de la estructura de la red:
AlgoritmosAlgoritmos
• Árboles
• Poliárboles
• Redes multiconectadas
• Árboles
• Poliárboles
• Redes multiconectadas
Cada nodo corresponde a una variable discreta, A={A1,A2,…,An) con su respectiva matriz de probabilidad condicional, P(B|A)=P(Bj| Ai)
Cada nodo corresponde a una variable discreta, A={A1,A2,…,An) con su respectiva matriz de probabilidad condicional, P(B|A)=P(Bj| Ai)
Propagación en Árboles .Propagación en Árboles .
Dada cierta evidencia E --representada por la instanciación de ciertas variables-- la probabilidad posterior de cualquier variable B, por el teorema de Bayes:
Dada cierta evidencia E --representada por la instanciación de ciertas variables-- la probabilidad posterior de cualquier variable B, por el teorema de Bayes:
P( Bi | E)=P( Bi ) P(E | Bi) / P( E )P( Bi | E)=P( Bi ) P(E | Bi) / P( E )
Ya que la estructura de la red es un árbol, el Nodo B la separa en dos subárboles, por lo que podemos dividir la evidencia en dos grupos:
E-: Datos en el árbol que cuya raíz es B
E+: Datos en el resto del árbol
Ya que la estructura de la red es un árbol, el Nodo B la separa en dos subárboles, por lo que podemos dividir la evidencia en dos grupos:
E-: Datos en el árbol que cuya raíz es B
E+: Datos en el resto del árbol
EvidenciaEvidencia
Entonces: P( Bi | E ) = P ( Bi ) P ( E-,E+ | Bi ) / P(E)
Pero dado que ambos son independientes y aplicando nuevamente Bayes:
Entonces: P( Bi | E ) = P ( Bi ) P ( E-,E+ | Bi ) / P(E)
Pero dado que ambos son independientes y aplicando nuevamente Bayes:
P( Bi | E ) = P ( Bi | E+ ) P(E- | Bi ) P( Bi | E ) = P ( Bi | E+ ) P(E- | Bi )
Evidencia
A
D
C
F G
B
E
H
I
E+
E-
Donde es una constante de normalización.
Esto separa la evidencia para actualizar la probabilidad de B.
Además vemos que no requerimos de la probabilidad a priori, excepto en el caso de la raíz donde:
Donde es una constante de normalización.
Esto separa la evidencia para actualizar la probabilidad de B.
Además vemos que no requerimos de la probabilidad a priori, excepto en el caso de la raíz donde:
P (Ai | E+ )=P( Ai ) P (Ai | E+ )=P( Ai )
Si definimos los siguientes términos:Si definimos los siguientes términos:
Definiciones:Definiciones:
(Bi)= P ( E- | Bi) (Bi)= P ( E- | Bi)
Entonces:Entonces:
(Bi)= P (Bi | E+ )(Bi)= P (Bi | E+ )
P(Bi | E )= (B i) (B i) P(Bi | E )= (B i) (B i)
Dado que los hijos son condicionalmente independientes dado el padre:Dado que los hijos son condicionalmente independientes dado el padre:
Abajo hacia arriba (Lambda)Abajo hacia arriba (Lambda)
Donde Ek- corresponde a la evidencia que proviene del hijo k de B, denotado por Sk.Donde Ek- corresponde a la evidencia que proviene del hijo k de B, denotado por Sk.
)()|()( ikk
ikk
i BBEPB
Condicionando cada término en la ecuación anterior respecto a todos los posibles valores de cada nodo hijo, obtenemos:
Condicionando cada término en la ecuación anterior respecto a todos los posibles valores de cada nodo hijo, obtenemos:
ji
kj
kjik
ki BSPSBEPB )|(),|()(
Dado que B es condicionalmente de la evidencia bajo cada hijo dado éste y usando la definición de :
Dado que B es condicionalmente de la evidencia bajo cada hijo dado éste y usando la definición de :
j
kji
kj
ki SBSPB )()|()(
En forma análoga obtenemos una
ecuación para .
En forma análoga obtenemos una
ecuación para .
Arriba hacia abajo (PI)Arriba hacia abajo (PI)
Primero la condicionamos sobre todos los posibles valores del padre:Primero la condicionamos sobre todos los posibles valores del padre:
j
jjii EAPAEBPB )|(),|()(
Podemos eliminar E+ del primer termino dada independencia condicional. Podemos eliminar E+ del primer termino dada independencia condicional.
El segundo término representa la probabilidad posterior de A sin contar la evidencia de subárbol de B, por lo que podemos expresarla usando la ecuación para P(Bi|E) y la descomposición de .
El segundo término representa la probabilidad posterior de A sin contar la evidencia de subárbol de B, por lo que podemos expresarla usando la ecuación para P(Bi|E) y la descomposición de .
Donde k incluye a todos los hijos de A excepto B. Donde k incluye a todos los hijos de A excepto B.
jjk
kjjii AAABPB )()()|()(
Mediante estas ecuaciones se integra un algoritmo de propagación de probabilidades en árboles.
Cada nodo guarda los valores de los vectores
y , así como las matrices de probabilidad P.
Mediante estas ecuaciones se integra un algoritmo de propagación de probabilidades en árboles.
Cada nodo guarda los valores de los vectores
y , así como las matrices de probabilidad P.
AlgoritmoAlgoritmo
La propagación se hace por un mecanismo de paso de mensajes, en donde cada nodo envía los mensajes correspondientes a su padre e hijos:
La propagación se hace por un mecanismo de paso de mensajes, en donde cada nodo envía los mensajes correspondientes a su padre e hijos:
Mensaje al padre (hacia arriba) -- nodo B a su padre A:Mensaje al padre (hacia arriba) -- nodo B a su padre A:
j
jijiB BABPA )()|()(
Mensaje a los hijos (hacia abajo) -- nodo B a su hijo Sk :
Mensaje a los hijos (hacia abajo) -- nodo B a su hijo Sk :
)()()( jlkl
jik BBB
Al instanciarse ciertos nodos, éstos envían mensajes a sus padres e hijos, y se propagan hasta a llegar a la raíz u hojas, o hasta encontrar un nodo instanciado.
Así que la propagación se hace en un solo paso en un tiempo proporcional al diámetro de la red.
Al instanciarse ciertos nodos, éstos envían mensajes a sus padres e hijos, y se propagan hasta a llegar a la raíz u hojas, o hasta encontrar un nodo instanciado.
Así que la propagación se hace en un solo paso en un tiempo proporcional al diámetro de la red.
Esto se puede hacer en forma iterativa, instanciando ciertas variables y propagando su efecto; y luego instanciando otras y propagando la nueva información, combinando ambas evidencias.
Esto se puede hacer en forma iterativa, instanciando ciertas variables y propagando su efecto; y luego instanciando otras y propagando la nueva información, combinando ambas evidencias.
Propagación
A
D
C
F G
B
E
H
I
(H)
E(B)
G(D)F(D)
C(A)
D(B)
B(A)
A(H)
Propagación
A
D
C
F G
B
E
H
I
(I)
B(E)
D(G)D(F)
A(C)
B(D)
A(B)
H(A)
Condiciones Iniciales
• Nodos no conocidos:
(Bi) = [1,1, …]
(Bi) = [1,1, …]• Nodos asignados (conocidos): (Bi) = [0,0, ..1, 0, …, 0] (1 para valor asignado)
(Bi) = [0,0, ..1, 0, …, 0] (1 para valor asignado)• Nodo raíz:
(A) = P(A), (probabilidad marginal inicial)
Ejemplo
Enf.
Fiebre Dolor
Comida
P(F|E)0.9 0.50.1 0.5
P(D|E)0.7 0.40.3 0.6
P(E|C)0.9 0.70.1 0.3
P(C)0.8 0.2
Ejemplo
Enf.
Fiebre Dolor
Comida
F=si=[1,0] =[1,1]
Ejemplo
Enf.
Fiebre Dolor
ComidaF= [1,0] * [.9 .5 | .1 .5] = [.9 .5]
D= [1,1] * [.7 .4 | .3 .6] = [1 1]
P(D|E)0.7 0.40.3 0.6
P(F|E)0.9 0.50.1 0.5
Ejemplo
Enf.
Fiebre Dolor
Comida
(E) = [.9 .5] * [1 1] = [.9 .5]
P(D|E)0.7 0.40.3 0.6
P(F|E)0.9 0.50.1 0.5
(C) = [.9 .5] * [.9 .7| .1 .3] = [.86 .78]
P(E|C)0.9 0.70.1 0.3
Ejemplo
Enf.
Fiebre Dolor
Comida(E) = [.8 .2] * [.9 .7| .1 .3] = [.86 .14]
P(D|E)0.7 0.40.3 0.6
P(F|E)0.9 0.50.1 0.5
(C) = [.8 .2]
P(E|C)0.9 0.70.1 0.3
Ejemplo
Enf.
Fiebre Dolor
Comida
(E) = [.86 .14]
P(D|E)0.7 0.40.3 0.6
(C) = [.8 .2]
(D) = [.86 .14] * [.9 .5] [.7 .4| .3 .6] = [.5698 .2742]
Ejemplo
Enf.
Fiebre Dolor
Comida(E) = [.86 .14]
(C) = [.8 .2]
(D) = [.57 .27]
D=[1,1]
(E) = [.9 .5]
(C) = [.86 .78]P(C)=[.688 .156]P(C)= [.815 .185]
P(E)=[.774 .070]P(E)= [.917 .083]
P(D)=[.57 .27]P(D)= [.67 .33]
Un poliárbol es una red en la que un nodo puede tener varios padres, pero sin existir múltiples trayectorias entre nodos (red conectada en forma sencilla - SCG)
Un poliárbol es una red en la que un nodo puede tener varios padres, pero sin existir múltiples trayectorias entre nodos (red conectada en forma sencilla - SCG)
Propagación en poliárbolesPropagación en poliárboles
La principal diferencia es que se requiere de la probabilidad conjunta de cadanodo dado todos sus padres:
La principal diferencia es que se requiere de la probabilidad conjunta de cadanodo dado todos sus padres:
P ( Bi | A1,....An ) P ( Bi | A1,....An )
El algoritmo de propagación es muy similar al de árboles. El algoritmo de propagación es muy similar al de árboles.
Una red multiconectada es un grafo no conectado en forma sencilla, es decir, en el que hay múltiples trayectorias entre nodos (MCG).
En este tipo de RP los métodos anteriores ya no aplican, pero existen otras técnicas alternativas:
Una red multiconectada es un grafo no conectado en forma sencilla, es decir, en el que hay múltiples trayectorias entre nodos (MCG).
En este tipo de RP los métodos anteriores ya no aplican, pero existen otras técnicas alternativas:
Propagación en Redes MulticonectadasPropagación en Redes Multiconectadas
• Condicionamiento • Simulación estocástica • Agrupamiento
• Condicionamiento • Simulación estocástica • Agrupamiento
Si instanciamos una variable, ésta bloquea las trayectorias de propagación.
Entonces asumiendo valores para un grupo seleccionado de variables podemos descomponer la gráfica en un conjunto de SCG.
Propagamos para cada valor posible de dichas variables y luego promediamos las probabilidades ponderadas.
Si instanciamos una variable, ésta bloquea las trayectorias de propagación.
Entonces asumiendo valores para un grupo seleccionado de variables podemos descomponer la gráfica en un conjunto de SCG.
Propagamos para cada valor posible de dichas variables y luego promediamos las probabilidades ponderadas.
Condicionamiento: Condicionamiento:
Condicionamiento
1
32
4 5
1
32
4 5
1
1=V 1=V
Se asignan valores aleatorios a las variables no instanciadas, se calcula la distribución de probabilidad y se obtienen valores de cadavariable dando una muestra.
Se repite el procedimiento para obtener un número apreciable de muestras y en base al numero de ocurrencias de cada valor se determina la probabilidad de dicha variable.
Se asignan valores aleatorios a las variables no instanciadas, se calcula la distribución de probabilidad y se obtienen valores de cadavariable dando una muestra.
Se repite el procedimiento para obtener un número apreciable de muestras y en base al numero de ocurrencias de cada valor se determina la probabilidad de dicha variable.
Simulación Estocástica: Simulación Estocástica:
Simulación Estocástica: Simulación Estocástica:
1
32
4 5
v
f f
v
f
vfffv
El método de agrupamiento consiste en transformar la estructura de la red para obtener un árbol, mediante agrupación de nodos usando la teoría de grafos [Lauritzen 88].
El método de agrupamiento consiste en transformar la estructura de la red para obtener un árbol, mediante agrupación de nodos usando la teoría de grafos [Lauritzen 88].
Agrupamiento:Agrupamiento:
Ejemplo
1
32
4 5
1
32
4 5
Ordenamiento de Cliques
1
32
4 5
C1
C2
C3
Árbol de Cliques
C1
C2
C3
1,2,3
2,3,4
3,5
En general, la propagación en una red probabilística con una estructura compleja es un problema de complejidad NP-duro [Cooper 90]; sin embargo, en muchas aplicaciones prácticas la estructura de la red no es tan compleja y los tiempos de propagación son razonables.
En general, la propagación en una red probabilística con una estructura compleja es un problema de complejidad NP-duro [Cooper 90]; sin embargo, en muchas aplicaciones prácticas la estructura de la red no es tan compleja y los tiempos de propagación son razonables.
ComplejidadComplejidad
Ejemplo de Propagación en Redes Bayesianas
Demostración
Ejemplo de Propagación en Redes Bayesianas
Demostración
La redes bayesianas son un método adecuado para representar y razonar con incertidumbre. La redes bayesianas son un método adecuado para representar y razonar con incertidumbre.
ConclusionesConclusiones
Se han desarrollado diversas aplicacionesbasadas en redes bayesianas en áreas como diagnóstico médico e industrial, robótica, sistemas de soporte de decisiones, tutoresinteligentes, etc.; e incluso los “ayudantes” de Office están en parte basados en redes bayesianas.
Se han desarrollado diversas aplicacionesbasadas en redes bayesianas en áreas como diagnóstico médico e industrial, robótica, sistemas de soporte de decisiones, tutoresinteligentes, etc.; e incluso los “ayudantes” de Office están en parte basados en redes bayesianas.
Actualmente hay desarrollos en varios áreas, incluyendo la inclusión de aspectos temporales (redes dinámicas), manejo de variables continuas y aprendizaje.
Actualmente hay desarrollos en varios áreas, incluyendo la inclusión de aspectos temporales (redes dinámicas), manejo de variables continuas y aprendizaje.
Existen, básicamente, otras dos alternativas bien fundamentadas para el manejo de incertidumbre: teoría de Dempster-Shafer y Lógica Difusa.
La teoría de Dempster-Shafer permite diferenciar entre ignorancia e iguales probabilidades, aunque para problemas grandes se vuelve demasiado compleja.
Existen, básicamente, otras dos alternativas bien fundamentadas para el manejo de incertidumbre: teoría de Dempster-Shafer y Lógica Difusa.
La teoría de Dempster-Shafer permite diferenciar entre ignorancia e iguales probabilidades, aunque para problemas grandes se vuelve demasiado compleja.
ConclusionesConclusiones
La lógica difusa tiene la ventaja de que permite representar más facilmente ciertos conceptos no bien definidos y, en particular las reglas difusas se asemejan a los sistemas basados en reglas.
Sin embargo, tiene la dificultad de que falta de una semántica clara.
La lógica difusa tiene la ventaja de que permite representar más facilmente ciertos conceptos no bien definidos y, en particular las reglas difusas se asemejan a los sistemas basados en reglas.
Sin embargo, tiene la dificultad de que falta de una semántica clara.
IncertidumbreIncertidumbre
FINFIN