Factorizaci´on de ´arboles de probabilidad y sus aplicaciones
Transcript of Factorizaci´on de ´arboles de probabilidad y sus aplicaciones
![Page 1: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/1.jpg)
Factorizacion de arboles de probabilidady sus aplicaciones
I. Martınez∗, S. Moral∗∗, C. Rodrıguez∗, A. Salmeron∗
∗Dept. Estadıstica y Mat. Aplicada ∗∗Dept. Ciencias de la Computacion e I.A.
Universidad de Almerıa Universidad de Granada
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.1/13
![Page 2: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/2.jpg)
Índice
1. Motivación
2. Niveles de factorización
3. Factorización de árboles de probabilidad
4. Aplicaciones
5. Conclusiones
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.2/13
![Page 3: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/3.jpg)
¿Para qué factorizar?
• En cálculo de probabilidades, FACTORIZAR⇒ MÁSEFICIENCIA
• Modelos multivariantes, gran número de variables,f.m.p. sin expresión analítica: MUY FRECUENTESEN LA PRÁCTICA
• Antes de factorizar: INTRATABLES
• Después de factorizar: TRATABLES
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.3/13
![Page 4: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/4.jpg)
¿Para qué factorizar?
• En cálculo de probabilidades, FACTORIZAR⇒ MÁSEFICIENCIA
• Modelos multivariantes, gran número de variables,f.m.p. sin expresión analítica: MUY FRECUENTESEN LA PRÁCTICA
• Antes de factorizar: INTRATABLES
• Después de factorizar: TRATABLES
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.3/13
![Page 5: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/5.jpg)
¿Para qué factorizar?
• En cálculo de probabilidades, FACTORIZAR⇒ MÁSEFICIENCIA
• Modelos multivariantes, gran número de variables,f.m.p. sin expresión analítica: MUY FRECUENTESEN LA PRÁCTICA
• Antes de factorizar: INTRATABLES
• Después de factorizar: TRATABLES
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.3/13
![Page 6: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/6.jpg)
¿Para qué factorizar?
• En cálculo de probabilidades, FACTORIZAR⇒ MÁSEFICIENCIA
• Modelos multivariantes, gran número de variables,f.m.p. sin expresión analítica: MUY FRECUENTESEN LA PRÁCTICA
• Antes de factorizar: INTRATABLES
• Después de factorizar: TRATABLES
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.3/13
![Page 7: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/7.jpg)
Niveles de factorización
• PRIMER NIVEL: Red bayesiana⇔ Join tree.
• Concepto subyacente: Independencia condicional
• SEGUNDO NIVEL: Potenciales asociados a losnodos del join tree.
Un potencial es una función
Ψ : Rn→ R+0
con soporte finito
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.4/13
![Page 8: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/8.jpg)
Niveles de factorización
• PRIMER NIVEL: Red bayesiana⇔ Join tree.
• Concepto subyacente: Independencia condicional
• SEGUNDO NIVEL: Potenciales asociados a losnodos del join tree.
Un potencial es una función
Ψ : Rn→ R+0
con soporte finito
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.4/13
![Page 9: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/9.jpg)
Niveles de factorización
• PRIMER NIVEL: Red bayesiana⇔ Join tree.
• Concepto subyacente: Independencia condicional
• SEGUNDO NIVEL: Potenciales asociados a losnodos del join tree.
Un potencial es una función
Ψ : Rn→ R+0
con soporte finito
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.4/13
![Page 10: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/10.jpg)
Niveles de factorización
• PRIMER NIVEL: Red bayesiana⇔ Join tree.
• Concepto subyacente: Independencia condicional
• SEGUNDO NIVEL: Potenciales asociados a losnodos del join tree.
Un potencial es una función
Ψ : Rn→ R+0
con soporte finito
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.4/13
![Page 11: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/11.jpg)
Árboles de probabilidad
Un potencial se puede representar como unárbol:
w x y ψ(w,x,y)
0 0 0 0.1
0 0 1 0.2
0 1 0 0.2
0 1 1 0.4
1 0 0 0.3
1 0 1 0.6
1 1 0 0.6
1 1 1 1.2
W
X X
Y Y YY
0.1 0.2 0.2 0.4 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.5/13
![Page 12: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/12.jpg)
Árboles de probabilidad
Un potencial se puede representar como unárbol:
w x y ψ(w,x,y)
0 0 0 0.1
0 0 1 0.2
0 1 0 0.2
0 1 1 0.4
1 0 0 0.3
1 0 1 0.6
1 1 0 0.6
1 1 1 1.2
W
X X
Y Y YY
0.1 0.2 0.2 0.4 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.5/13
![Page 13: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/13.jpg)
Factorización de árboles de prob.
¿Se puede factorizar un árbol?
bajo ciertas condiciones,SÍ
Definicion: Sea ψ un potencial sobre X = X1, . . . ,Xnrepresentado por un árbol T . Sea XC ⊆ X y (XC = xC) unaconfiguración de variables que llevan desde T hasta unavariable Xi. Decimos que T es factorizable en Xi para elcontexto (XC = xC), si para todo x,y ∈ΩXi, ∃ε> 0 t.q.
T R(XC=xC,Xi=x) = ε ·T R(XC=xC,Xi=y) .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.6/13
![Page 14: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/14.jpg)
Factorización de árboles de prob.
¿Se puede factorizar un árbol? bajo ciertas condiciones,SÍ
Definicion: Sea ψ un potencial sobre X = X1, . . . ,Xnrepresentado por un árbol T . Sea XC ⊆ X y (XC = xC) unaconfiguración de variables que llevan desde T hasta unavariable Xi. Decimos que T es factorizable en Xi para elcontexto (XC = xC), si para todo x,y ∈ΩXi, ∃ε> 0 t.q.
T R(XC=xC,Xi=x) = ε ·T R(XC=xC,Xi=y) .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.6/13
![Page 15: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/15.jpg)
Factorización de árboles de prob.
¿Se puede factorizar un árbol? bajo ciertas condiciones,SÍ
Definicion: Sea ψ un potencial sobre X = X1, . . . ,Xnrepresentado por un árbol T . Sea XC ⊆ X y (XC = xC) unaconfiguración de variables que llevan desde T hasta unavariable Xi. Decimos que T es factorizable en Xi para elcontexto (XC = xC), si para todo x,y ∈ΩXi, ∃ε> 0 t.q.
T R(XC=xC,Xi=x) = ε ·T R(XC=xC,Xi=y) .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.6/13
![Page 16: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/16.jpg)
Factorización de árboles de prob.
Definicion: Sea T un árbol de probabilidad. DefinimosT (XC = xC,Xi,x,y,ε) como el árbol que se obtienereemplazando, en T , T R(XC=xC,Xi=x) por la constante 1 yT R(XC=xC,Xi=y) por ε.
Definicion: Sea T un árbol de probabilidad. DefinimosT (XC = xC,Xi,x) como el árbol que se obtienereemplazando, en T , T R(XC=xC) por T R(XC=xC,Xi=x) yT R(XD=xD) por 1 para cualquier contexto (XD = xD)
incompatible con (XC = xC).
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.7/13
![Page 17: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/17.jpg)
Factorización de árboles de prob.
Definicion: Sea T un árbol de probabilidad. DefinimosT (XC = xC,Xi,x,y,ε) como el árbol que se obtienereemplazando, en T , T R(XC=xC,Xi=x) por la constante 1 yT R(XC=xC,Xi=y) por ε.
Definicion: Sea T un árbol de probabilidad. DefinimosT (XC = xC,Xi,x) como el árbol que se obtienereemplazando, en T , T R(XC=xC) por T R(XC=xC,Xi=x) yT R(XD=xD) por 1 para cualquier contexto (XD = xD)
incompatible con (XC = xC).
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.7/13
![Page 18: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/18.jpg)
Factorización de árboles de prob.
Proposicion: Sea T un árbol de probabilidadfactorizable en Xi con factor de proporcionalidadε para el contexto (XC = xC). Entonces,
T = T (XC = xC,Xi,x,y,ε)⊗T (XC = xC,Xi = x)
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.8/13
![Page 19: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/19.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.2 0.4 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.9/13
![Page 20: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/20.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.2 0.4 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.9/13
![Page 21: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/21.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.2 0.4 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.9/13
![Page 22: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/22.jpg)
Aplicaciones: propagación perezosa
La factorización es útil cuando:
• Se va a borrar una variable X que está en más de unárbol.
• Alguno de los árboles es factorizable en X para algúncontexto.
• Es tanto más efectiva cuanto más cerca de la raízesté X .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.10/13
![Page 23: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/23.jpg)
Aplicaciones: propagación perezosa
La factorización es útil cuando:
• Se va a borrar una variable X que está en más de unárbol.
• Alguno de los árboles es factorizable en X para algúncontexto.
• Es tanto más efectiva cuanto más cerca de la raízesté X .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.10/13
![Page 24: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/24.jpg)
Aplicaciones: propagación perezosa
La factorización es útil cuando:
• Se va a borrar una variable X que está en más de unárbol.
• Alguno de los árboles es factorizable en X para algúncontexto.
• Es tanto más efectiva cuanto más cerca de la raízesté X .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.10/13
![Page 25: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/25.jpg)
Justificación
Proposicion: Ninguna variable aparece más deuna vez en una misma rama de un árbol deprobabilidad.
Corolario: T (XC = xC,Xi) no contiene a Xi.
PROBLEMA: Puede ser difícil que se dé la pro-
porcionalidad en un árbol
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.11/13
![Page 26: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/26.jpg)
Justificación
Proposicion: Ninguna variable aparece más deuna vez en una misma rama de un árbol deprobabilidad.
Corolario: T (XC = xC,Xi) no contiene a Xi.
PROBLEMA: Puede ser difícil que se dé la pro-
porcionalidad en un árbol
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.11/13
![Page 27: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/27.jpg)
Justificación
Proposicion: Ninguna variable aparece más deuna vez en una misma rama de un árbol deprobabilidad.
Corolario: T (XC = xC,Xi) no contiene a Xi.
PROBLEMA: Puede ser difícil que se dé la pro-
porcionalidad en un árbol
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.11/13
![Page 28: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/28.jpg)
Solución: factorización aproximada
Definicion: Sea ψ un potencial sobreX = X1, . . . ,Xn representado por un árbol T .Sea XC ⊆ X y (XC = xC) una configuración devariables que llevan desde T hasta una variableXi. Decimos que T es δ-factorizable en Xi para elcontexto (XC = xC), con δ > 0, si para todox,y ∈ΩXi, ∃ε> 0 t.q.
∣∣∣T R(XC=xC,Xi=x)− ε ·T R(XC=xC,Xi=y)∣∣∣≤ δ .
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.12/13
![Page 29: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/29.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.21 0.39 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es 0.1-factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.13/13
![Page 30: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/30.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.21 0.39 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es 0.1-factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.13/13
![Page 31: Factorizaci´on de ´arboles de probabilidad y sus aplicaciones](https://reader031.fdocumento.com/reader031/viewer/2022030322/588c76991a28abaf218b9646/html5/thumbnails/31.jpg)
Ejemplo
W
X X
Y Y YY
0.1 0.2 0.21 0.39 0.3 0.6 0.2 1.2
0 1
0 1 0 1
0 1 0 1 0 1 0 1
T es 0.1-factorizable en X para el contexto (W = 0)
W
X X
1 2
0.3 0.6 0.6 1.2
× W
Y 1
0.1 0.2Y Y
Factorizaci on de arboles de probabilidad y sus aplicaciones – p.13/13