Factorización de Árboles de Probabilidad
Irene Martınez1, Serafın Moral2, Carmelo Rodrıguez3 y Antonio Salmeron4
1 Dept. Lenguajes y Computacion. Universidad de Almerıa
2 Dept. Ciencia de la Computacion e I.A. Universidad de Granada
3,4 Dept. Estadıstica y Matematica Aplicada Universidad de Almerıa
Almerıa, Mayo 2005
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 1/38
Factorización de Árboles de Probabilidad
Factorización de árboles de probabilidad
Factorización exacta
Factorización aproximada
Factorización en Elvira
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 2/38
Bayesian networks and probability trees
Lazy-Penniless: potenciales mediante probability trees
Bajo ciertas condiciones, es posible realizar factorización sobreprobability treesÜ disminuir size(T ) Ü incrementar eficiencia
Probability Propagation:
Supongamos que se va borrar la variable Xi :1 Multiplicar los potenciales que contienen Xi (probability trees)
2 Sumar en Xi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 3/38
Bayesian networks and probability trees
Lazy-Penniless: potenciales mediante probability trees
Bajo ciertas condiciones, es posible realizar factorización sobreprobability treesÜ disminuir size(T ) Ü incrementar eficiencia
Probability Propagation:
Supongamos que se va borrar la variable Xi :1 Multiplicar los potenciales que contienen Xi (probability trees)
2 Sumar en Xi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 3/38
Bayesian networks and probability trees
Lazy-Penniless: potenciales mediante probability trees
Bajo ciertas condiciones, es posible realizar factorización sobreprobability treesÜ disminuir size(T ) Ü incrementar eficiencia
Probability Propagation:
Supongamos que se va borrar la variable Xi :1 Multiplicar los potenciales que contienen Xi (probability trees)
2 Sumar en Xi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 3/38
Bayesian networks and probability trees
Lazy-Penniless: potenciales mediante probability trees
Bajo ciertas condiciones, es posible realizar factorización sobreprobability treesÜ disminuir size(T ) Ü incrementar eficiencia
Probability Propagation:
Supongamos que se va borrar la variable Xi :1 Multiplicar los potenciales que contienen Xi (probability trees)
1.a Factorizar cada árbol que contiene a Xi como el producto de dos árboles de menor
tamaño:
uno contiene Xi
el otro no la contiene
1.b El producto se realiza sobre potenciales con un dominio menor
2 Sumar en Xi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 3/38
Factorisation of Probability Trees
Condiciones para aplicar factorización a Probability Trees:
Producto de los factores debe ser igual al árbol original.Algoritmo de propagación trabaje con listas de potenciales:Lazy propagation y Lazy-penniless
Métodos para descomponer probability trees:(conservando la primera condición)
Tree Splitting:
Proportional sub-trees:
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 4/38
Factorisation of Probability Trees
Condiciones para aplicar factorización a Probability Trees:
Producto de los factores debe ser igual al árbol original.Algoritmo de propagación trabaje con listas de potenciales:Lazy propagation y Lazy-penniless
Métodos para descomponer probability trees:(conservando la primera condición)
Tree Splitting:
Proportional sub-trees:
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 4/38
Factorisation of Probability Trees
Condiciones para aplicar factorización a Probability Trees:
Producto de los factores debe ser igual al árbol original.Algoritmo de propagación trabaje con listas de potenciales:Lazy propagation y Lazy-penniless
Métodos para descomponer probability trees:(conservando la primera condición)
Tree Splitting: Obtiene un par de árboles:Ü sólo uno contiene la variable (marginalise out)
Proportional sub-trees: Bajo ciertas condiciones, podemos aplicarla descomposición considerando:
Exact FactorisationApproximate Factorisation
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 4/38
Factorisation of Probability Trees: Tree splitting
Tree Splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Probability propagation: Y es la siguiente variable a borrarÜ Descomponer T como el producto de dos árboles menores:
Tf : no contiene a Y Ü no interviene para borrar Y
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 5/38
Factorisation of Probability Trees: Tree splitting
Tree Splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Probability propagation: Y es la siguiente variable a borrar
Ü Descomponer T como el producto de dos árboles menores:
Tf : no contiene a Y Ü no interviene para borrar Y
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 5/38
Factorisation of Probability Trees: Tree splitting
Tree Splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Probability propagation: Y es la siguiente variable a borrarÜ Descomponer T como el producto de dos árboles menores:
Tf : no contiene a Y Ü no interviene para borrar Y
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 5/38
Factorisation of Probability Trees: Tree splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
1
1 ⊗ X
1
0
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 6/38
Factorisation of Probability Trees: Tree splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
1
1 ⊗ . . .
X
1
0
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 6/38
Factorisation of Probability Trees: Tree splitting
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
X
Y
0
W
0
Z
0
0.1
0
0.7
1Z
1
0.3
0
0.1
1
W
1
Z
0
0.2
0
0.9
1Z
1
0.9
0
0.5
1
1
1 ⊗ X
1
0
W
1
Z
0
0.3
0
0.1
1Z
1
0.7
0
0.6
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 6/38
Factorisation of Probability Trees: Proportional sub-trees
Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Probability propagation: X siguiente variable a borrar
Ü Para el contexto W = 0, los dos hijos de X son proporcionalesÜ Factorizar T como el producto de dos árboles menores:
Tf : no contiene a X Ü no interviene al borrar X
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 7/38
Factorisation of Probability Trees: Proportional sub-trees
Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Probability propagation: X siguiente variable a borrarÜ Para el contexto W = 0, los dos hijos de X son proporcionales
Ü Factorizar T como el producto de dos árboles menores:Tf : no contiene a X Ü no interviene al borrar X
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 7/38
Factorisation of Probability Trees: Proportional sub-trees
Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Probability propagation: X siguiente variable a borrarÜ Para el contexto W = 0, los dos hijos de X son proporcionalesÜ Factorizar T como el producto de dos árboles menores:
Tf : no contiene a X Ü no interviene al borrar X
Tc: más sencillo que T
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 7/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
Sea T un probability tree y una variable X
(XC = xC) configuración de variables desde raíz de T a X
T es proporcional bajo X en el contexto (XC = xC) si existexi ∈ ΩX t.q. para cada xj 6= xi ∈ ΩX , ∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
siendo:
T R(XC=xC ,X=x) sub-tree de T al que se llega con el camino de laconfiguración (XC = xC, X = x).
α = αj|j 6= i : factores de proporcionalidad.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 8/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
Sea T un probability tree y una variable X
(XC = xC) configuración de variables desde raíz de T a X
T es proporcional bajo X en el contexto (XC = xC) si existexi ∈ ΩX t.q. para cada xj 6= xi ∈ ΩX , ∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
siendo:
T R(XC=xC ,X=x) sub-tree de T al que se llega con el camino de laconfiguración (XC = xC, X = x).
α = αj|j 6= i : factores de proporcionalidad.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 8/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
Sea T un probability tree y una variable X
(XC = xC) configuración de variables desde raíz de T a X
T es proporcional bajo X en el contexto (XC = xC) si existexi ∈ ΩX t.q. para cada xj 6= xi ∈ ΩX , ∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
siendo:
T R(XC=xC ,X=x) sub-tree de T al que se llega con el camino de laconfiguración (XC = xC, X = x).
α = αj|j 6= i : factores de proporcionalidad.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 8/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
T es proporcional bajo X en el contexto (W = 0)
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Y
0.1
0
0.2
1
α = 2
T R(W=0,X=1) = 2 · T R(W=0,X=0)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 9/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
T es proporcional bajo X en el contexto (W = 0)
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Y
0.1
0
0.2
1
α = 2
T R(W=0,X=1) = 2 · T R(W=0,X=0)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 9/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Proporcionalidad
T es proporcional bajo X en el contexto (W = 0)
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1Y
0.1
0
0.2
1
α = 2
T R(W=0,X=1) = 2 · T R(W=0,X=0)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 9/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Descomposición del árbol
Sea T un probability tree proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α. Obtenemos:
Core Term de T , T (XC = xC, X = x, α) , reemplazando:sub-tree T R(XC=xC ,X=xi) por la constante 1resto de sub-trees T R(XC=xC ,X=xj) por αj.
Free Term de T , T (XC = xC, X = x) , reemplazando:sub-tree T R(XC=xC) por T R(XC=xC ,X=xi)
resto de sub-trees T R(XD=xD) por la constante 1para todo contexto (XD = xD) inconsistente con (XC = xC).
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 10/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Descomposición del árbol
Sea T un probability tree proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α. Obtenemos:
Core Term de T , T (XC = xC, X = x, α) , reemplazando:sub-tree T R(XC=xC ,X=xi) por la constante 1resto de sub-trees T R(XC=xC ,X=xj) por αj.
Free Term de T , T (XC = xC, X = x) , reemplazando:sub-tree T R(XC=xC) por T R(XC=xC ,X=xi)
resto de sub-trees T R(XD=xD) por la constante 1para todo contexto (XD = xD) inconsistente con (XC = xC).
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 10/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Descomposición del árbol
Sea T un probability tree proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α. Obtenemos:
Core Term de T , T (XC = xC, X = x, α) , reemplazando:sub-tree T R(XC=xC ,X=xi) por la constante 1resto de sub-trees T R(XC=xC ,X=xj) por αj.
Free Term de T , T (XC = xC, X = x) , reemplazando:sub-tree T R(XC=xC) por T R(XC=xC ,X=xi)
resto de sub-trees T R(XD=xD) por la constante 1para todo contexto (XD = xD) inconsistente con (XC = xC).
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 10/38
Exact Factorisation: Proportional sub-trees
Exact Factorisation: Descomposición del árbol
Sea T un probability tree proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α. Obtenemos:
Core Term de T , T (XC = xC, X = x, α) , reemplazando:sub-tree T R(XC=xC ,X=xi) por la constante 1resto de sub-trees T R(XC=xC ,X=xj) por αj.
Free Term de T , T (XC = xC, X = x) , reemplazando:sub-tree T R(XC=xC) por T R(XC=xC ,X=xi)
resto de sub-trees T R(XD=xD) por la constante 1para todo contexto (XD = xD) inconsistente con (XC = xC).
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 10/38
Exact Factorisation: Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Y
0.1
0
0.2
1
α = 1 α = 2
W
X
0
1
0
2
1X
1
Y
0
0.3
0
0.6
1Y
1
0.6
0
1.2
1
⊗ W
Y
0
0.1
0
0.2
11
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 11/38
Exact Factorisation: Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1
Y
0.1
0
0.2
1
α = 1 α = 2
W
X
0
1
0
2
1X
1
Y
0
0.3
0
0.6
1Y
1
0.6
0
1.2
1
⊗ W
Y
0
0.1
0
0.2
11
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 11/38
Exact Factorisation: Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1Y
0.1
0
0.2
1
α = 1 α = 2
W
X
0
1
0
2
1X
1
Y
0
0.3
0
0.6
1Y
1
0.6
0
1.2
1
⊗ W
Y
0
0.1
0
0.2
11
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 11/38
Exact Factorisation: Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1Y
0.1
0
0.2
1
α = 1 α = 2
W
X
0
1
0
2
1X
1
Y
0
0.3
0
0.6
1Y
1
0.6
0
1.2
1
⊗ W
Y
0
0.1
0
0.2
11
1
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 11/38
Exact Factorisation: Proportional sub-trees
W
X
0
Y
0
0.1
0
0.2
1Y
1
0.2
0
0.4
1
X
1
Y
0
0.3
0
0.6
1Y
1
0.2
0
1.2
1Y
0.1
0
0.2
1
α = 1 α = 2
W
X
0
1
0
2
1X
1
Y
0
0.3
0
0.6
1Y
1
0.6
0
1.2
1
⊗ W
Y
0
0.1
0
0.2
11
1Core Term Free Term
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 12/38
Exact Factorisation: Partially Proportional sub-trees
Exact Factorisation: NO todos los hijos son proporcionales
X
Y Y Y
01
2
Z Z Z Z Z Z Z Z Z
01
2 01
2 01
2
.1 .2 .01 .05 .3 .025.15 .1 .02 .2 .4 .02 .1 .6 .5 .3 .2 .04 .7 .4 .97 .85 .1 .25 .55 .7 .94
Sean T un probability tree, var X, (XC = xC) configuración hasta X
T es parcialmente proporcional bajo X en el contexto (XC = xC) siexiste xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cada xj ∈ L,∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 13/38
Exact Factorisation: Partially Proportional sub-trees
Exact Factorisation: NO todos los hijos son proporcionalesX
Y Y Y
01
2
Z Z Z Z Z Z Z Z Z
01
2 01
2 01
2
.1 .2 .01 .05 .3 .025.15 .1 .02 .2 .4 .02 .1 .6 .5 .3 .2 .04 .7 .4 .97 .85 .1 .25 .55 .7 .94
Sean T un probability tree, var X, (XC = xC) configuración hasta X
T es parcialmente proporcional bajo X en el contexto (XC = xC) siexiste xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cada xj ∈ L,∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 13/38
Exact Factorisation: Partially Proportional sub-trees
Exact Factorisation: NO todos los hijos son proporcionalesX
Y Y Y
01
2
Z Z Z Z Z Z Z Z Z
01
2 01
2 01
2
.1 .2 .01 .05 .3 .025.15 .1 .02 .2 .4 .02 .1 .6 .5 .3 .2 .04 .7 .4 .97 .85 .1 .25 .55 .7 .94
Sean T un probability tree, var X, (XC = xC) configuración hasta X
T es parcialmente proporcional bajo X en el contexto (XC = xC) siexiste xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cada xj ∈ L,∃αj > 0 :
T R(XC=xC ,X=xj) = αj · T R(XC=xC ,X=xi)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 13/38
Exact Factorisation: Partially Proportional sub-trees
Exact Factorisation: NO todos los hijos son proporcionales
Para que se cumpla:
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Sea T un probability tree parcialmente proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α, y xi, L definidos. Se obtiene:
Partial Core Term de T , T (XC = xC, X = xi, α, L),reemplazando:
sub-tree T R(XC=xC ,X=xi) por la constante 1cualquier sub-tree T R(XC=xC ,X=xj) por αj.
cualquier sub-tree T R(XC=xC ,X=xk), xi 6= xk /∈ L, por
T R(XC=xC ,X=xk)T (XC=xC ,X=xi)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 14/38
Exact Factorisation: Partially Proportional sub-trees
Exact Factorisation: NO todos los hijos son proporcionales
Para que se cumpla:
T = T (XC = xC, X = x, α) × T (XC = xC, X = x)
Sea T un probability tree parcialmente proporcional bajo X en el contexto(XC = xC) con factores de proporcionalidad α, y xi, L definidos. Se obtiene:
Partial Core Term de T , T (XC = xC, X = xi, α, L),reemplazando:
sub-tree T R(XC=xC ,X=xi) por la constante 1cualquier sub-tree T R(XC=xC ,X=xj) por αj.
cualquier sub-tree T R(XC=xC ,X=xk), xi 6= xk /∈ L, por
T R(XC=xC ,X=xk)T (XC=xC ,X=xi)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 14/38
Exact Factorisation: Partially Proportional sub-trees
X
Y Y Y
01
2
Z Z Z Z Z Z Z Z Z
01
2 01
2 01
2
.1 .2 .01 .05 .3 .025.15 .1 .02 .2 .4 .02 .1 .6 .5 .3 .2 .04 .7 .4 .97 .85 .1 .25 .55 .7 .94
Partial Core Term Free TermX
1 2 Y
01
2
Z Z Z
01
2
7. 2. 97. 17. .33 1. 3.66 7. 47.
⊗
Y
Z Z Z
01
2
.1 .2 .01 .05 .3 .25 .15 .1 .02
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 15/38
Exact Factorisation: Partially Proportional sub-trees
X
Y Y Y
01
2
Z Z Z Z Z Z Z Z Z
01
2 01
2 01
2
.1 .2 .01 .05 .3 .025.15 .1 .02 .2 .4 .02 .1 .6 .5 .3 .2 .04 .7 .4 .97 .85 .1 .25 .55 .7 .94
Partial Core Term Free TermX
1 2 Y
01
2
Z Z Z
01
2
7. 2. 97. 17. .33 1. 3.66 7. 47.
⊗
Y
Z Z Z
01
2
.1 .2 .01 .05 .3 .25 .15 .1 .02
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 15/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
”Almost” proportional trees:
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
factorización aproximada
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 16/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
”Almost” proportional trees:
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
factorización aproximada
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 16/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
”Almost” proportional trees:
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
factorización aproximada
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 16/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
Sean T1 y T2 dos sub-trees (hermanos) en T para un determinado contexto,ambos con el mismo tamaño y con valores positivos en sus nodos hoja.
Encontrar otro árbol T ∗2 con la misma estructura que T2,
y con un potencial muy cercano al de T2, tal que T ∗2 y T1
puedan ser α-proporcionales.
Sustituyendo T2 por T ∗2 Ü es posible factorizar el árbol que contiene T1 y T ∗
2
Dos cuestiones fundamentales:
Determinar el factor de proporcionalidad α
Medir la bondad de la aproximación
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 17/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
Sean T1 y T2 dos sub-trees (hermanos) en T para un determinado contexto,ambos con el mismo tamaño y con valores positivos en sus nodos hoja.
Encontrar otro árbol T ∗2 con la misma estructura que T2,
y con un potencial muy cercano al de T2, tal que T ∗2 y T1
puedan ser α-proporcionales.
Sustituyendo T2 por T ∗2 Ü es posible factorizar el árbol que contiene T1 y T ∗
2
Dos cuestiones fundamentales:
Determinar el factor de proporcionalidad α
Medir la bondad de la aproximación
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 17/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
Sean T1 y T2 dos sub-trees (hermanos) en T para un determinado contexto,ambos con el mismo tamaño y con valores positivos en sus nodos hoja.
Encontrar otro árbol T ∗2 con la misma estructura que T2,
y con un potencial muy cercano al de T2, tal que T ∗2 y T1
puedan ser α-proporcionales.
Sustituyendo T2 por T ∗2 Ü es posible factorizar el árbol que contiene T1 y T ∗
2
Dos cuestiones fundamentales:
Determinar el factor de proporcionalidad α
Medir la bondad de la aproximación
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 17/38
Approximate Factorisation of Probability Trees
Approximate Factorisation
¿Qué ocurre cuando NO es factible la factorización exacta?
Sean T1 y T2 dos sub-trees (hermanos) en T para un determinado contexto,ambos con el mismo tamaño y con valores positivos en sus nodos hoja.
Encontrar otro árbol T ∗2 con la misma estructura que T2,
y con un potencial muy cercano al de T2, tal que T ∗2 y T1
puedan ser α-proporcionales.
Sustituyendo T2 por T ∗2 Ü es posible factorizar el árbol que contiene T1 y T ∗
2
Dos cuestiones fundamentales:
Determinar el factor de proporcionalidad α
Medir la bondad de la aproximación
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 17/38
Approximate Factorisation of Probability Trees
Approximate Factorisation: Definición
Sea T un probability tree y (XC = xC) configuración devariables
T es δ-factorizable en el contexto (XC = xC) con factores deproporcionalidad α y respecto a una medida de divergencia D,si existe xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cadaxj ∈ L, ∃αj > 0 :
D(T R(XC=xC ,X=xj), αj · T R(XC=xC ,X=xi)) ≤ δ
δ > 0 es la tolerancia de la aproximación
Ü Árboles proporcionales y parcialmente proporcionales para elcontexto (XC = xC) son δ-factorizables, con δ = 0.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 18/38
Approximate Factorisation of Probability Trees
Approximate Factorisation: Definición
Sea T un probability tree y (XC = xC) configuración devariables
T es δ-factorizable en el contexto (XC = xC) con factores deproporcionalidad α y respecto a una medida de divergencia D,si existe xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cadaxj ∈ L, ∃αj > 0 :
D(T R(XC=xC ,X=xj), αj · T R(XC=xC ,X=xi)) ≤ δ
δ > 0 es la tolerancia de la aproximación
Ü Árboles proporcionales y parcialmente proporcionales para elcontexto (XC = xC) son δ-factorizables, con δ = 0.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 18/38
Approximate Factorisation of Probability Trees
Approximate Factorisation: Definición
Sea T un probability tree y (XC = xC) configuración devariables
T es δ-factorizable en el contexto (XC = xC) con factores deproporcionalidad α y respecto a una medida de divergencia D,si existe xi ∈ ΩX y un conjunto L ⊂ ΩX \ xi t.q. para cadaxj ∈ L, ∃αj > 0 :
D(T R(XC=xC ,X=xj), αj · T R(XC=xC ,X=xi)) ≤ δ
δ > 0 es la tolerancia de la aproximación
Ü Árboles proporcionales y parcialmente proporcionales para elcontexto (XC = xC) son δ-factorizables, con δ = 0.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 18/38
Approximate Factorisation of Probability Trees
Approximate Factorisation: árboles δ-factorizables
Para obtener árboles δ-factorizables es necesario:Analizar diferentes medidas de divergenciaCalcular el α óptimo
Todos los métodos de factorización aproximada deben cumplir lasiguiente propiedad de consistencia con la factorización exacta:
Un método de factorización aproximada es consistentesi produce una factorización exacta para cualquier árbol0-factorizable.
Ü El método se dice consistente si no introduce error cuando elárbol es proporcional, o parcialmente proporcional, bajo elcontexto.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 19/38
Approximate Factorisation of Probability Trees
Approximate Factorisation: árboles δ-factorizables
Para obtener árboles δ-factorizables es necesario:Analizar diferentes medidas de divergenciaCalcular el α óptimo
Todos los métodos de factorización aproximada deben cumplir lasiguiente propiedad de consistencia con la factorización exacta:
Un método de factorización aproximada es consistentesi produce una factorización exacta para cualquier árbol0-factorizable.
Ü El método se dice consistente si no introduce error cuando elárbol es proporcional, o parcialmente proporcional, bajo elcontexto.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 19/38
Approximate Factorisation: Proportionality factor
Cálculo del factor de proporcionalidad α
Sean T1 and T2 dos sub-trees de T para un contexto (XC = xc)
P = pi : i = 1, . . . , n; pi 6= 0 hojas de T1
Q = qi : i = 1, . . . , n; hojas de T2
La factorización aproximada se realiza reemplazando T2 por otroárbol T ∗
2 tal que T ∗2 es proporcional con T1. Entonces:
Las hojas de T ∗2 serán
Q∗ = αpi : i = 1, . . . , n; , siendo α el proportionalityfactor entre T1 y T2.
Notaremos πi = qi/pi, i = 1, . . . , n; los cocientes entrelas hojas de T2 y T1.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 20/38
Approximate Factorisation: Proportionality factor
Cálculo del factor de proporcionalidad α
Sean T1 and T2 dos sub-trees de T para un contexto (XC = xc)
P = pi : i = 1, . . . , n; pi 6= 0 hojas de T1
Q = qi : i = 1, . . . , n; hojas de T2
La factorización aproximada se realiza reemplazando T2 por otroárbol T ∗
2 tal que T ∗2 es proporcional con T1. Entonces:
Las hojas de T ∗2 serán
Q∗ = αpi : i = 1, . . . , n; , siendo α el proportionalityfactor entre T1 y T2.
Notaremos πi = qi/pi, i = 1, . . . , n; los cocientes entrelas hojas de T2 y T1.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 20/38
Approximate Factorisation: Proportionality factor
Cálculo del factor de proporcionalidad α
Dos grupos de métodos para calcular α:
Calculan α bajo la restricción de que se minimicen diferentesmedidas de divergencia
minimum χ2 divergence
minimum Mean Squared Error(MSE)
Weighted MSE (WMSE)
null Kullback-Leibler (KL)
Obtienen α independientemente de cualquier medida dedivergencia
Weight Preserving (WP)
Weighted Average (WA)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 21/38
Approximate Factorisation: Proportionality factor
Cálculo del factor de proporcionalidad α
Dos grupos de métodos para calcular α:
Calculan α bajo la restricción de que se minimicen diferentesmedidas de divergencia
minimum χ2 divergence
minimum Mean Squared Error(MSE)
Weighted MSE (WMSE)
null Kullback-Leibler (KL)
Obtienen α independientemente de cualquier medida dedivergencia
Weight Preserving (WP)
Weighted Average (WA)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 21/38
Approximate Factorisation: Proportionality factor
Cálculo del factor de proporcionalidad α
Dos grupos de métodos para calcular α:
Calculan α bajo la restricción de que se minimicen diferentesmedidas de divergencia
minimum χ2 divergence
minimum Mean Squared Error(MSE)
Weighted MSE (WMSE)
null Kullback-Leibler (KL)
Obtienen α independientemente de cualquier medida dedivergencia
Weight Preserving (WP)
Weighted Average (WA)Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 21/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Method of minimum χ2 divergence:
Dχ(T2, T ∗2 ) =
n∑
i=1
(qi − αpi)2
qi
α que minimiza Dχ es:
αχ =
∑n
i=1 pi∑n
i=1 pi/πi
La version normalizada:
Dχ∗(T2, T ∗2 ) =
√
Dχ
Dχ + n
minimizada por el mismo α que Dχ.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 22/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Method of minimum χ2 divergence:
Dχ(T2, T ∗2 ) =
n∑
i=1
(qi − αpi)2
qi
α que minimiza Dχ es:
αχ =
∑n
i=1 pi∑n
i=1 pi/πi
La version normalizada:
Dχ∗(T2, T ∗2 ) =
√
Dχ
Dχ + n
minimizada por el mismo α que Dχ.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 22/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Method of minimum Mean Squared Error (MSE):
Dmse(T2, T ∗2 ) =
1
n
n∑
i=1
(qi − αpi)2
α que minimiza Dmse es
αmse =
∑n
i=1 πip2i
∑n
i=1 p2i
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 23/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Weighted MSE (WMSE):
Dwmse(T2, T ∗2 ) =
n∑
i=1
hi(qi − αpi)2
con hi ≥ 0, i = 1, . . . , n; hi = 1
αwmse =
∑n
i=1 hiπip2i
∑n
i=1 hip2i
hi =qi
∑n
i=1 qi
,
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 24/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Weighted MSE (WMSE):
Dwmse(T2, T ∗2 ) =
n∑
i=1
hi(qi − αpi)2
con hi ≥ 0, i = 1, . . . , n; hi = 1
αwmse =
∑n
i=1 hiπip2i
∑n
i=1 hip2i
hi =qi
∑n
i=1 qi
,
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 24/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Method of null Kullback-Leibler divergence (KL):
Dkl(T2, T ∗2 ) =
n∑
i=1
qi log
(
qi
αpi
)
α que minimiza Dkl es
αkl = 2
ni=1 qi log(πi)
ni=1
qi
Problema con Dkl: requiere que la suma de los valores coincida.En otro caso, Dkl puede tomar valores negativos.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 25/38
Approximate Factorisation: Proportionality factorα minimising measures of divergence
Method of null Kullback-Leibler divergence (KL):
Dkl(T2, T ∗2 ) =
n∑
i=1
qi log
(
qi
αpi
)
α que minimiza Dkl es
αkl = 2
ni=1 qi log(πi)
ni=1
qi
Problema con Dkl: requiere que la suma de los valores coincida.En otro caso, Dkl puede tomar valores negativos.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 25/38
Approximate Factorisation: Proportionality factorα Independently of any divergence measure
Weight Preserving Method (WP):
Ü Asegura que el peso del árbol original y del aproximadocoinciden:
sum(T ∗2 ) =
n∑
i=1
αpi =n
∑
i=1
qi = sum(T2)
α que cumple esta restricción es:
αwp =
∑n
i=1 qi∑n
i=1 pi
=
∑n
i=1 πipi∑n
i=1 pi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 26/38
Approximate Factorisation: Proportionality factorα Independently of any divergence measure
Weight Preserving Method (WP):
Ü Asegura que el peso del árbol original y del aproximadocoinciden:
sum(T ∗2 ) =
n∑
i=1
αpi =n
∑
i=1
qi = sum(T2)
α que cumple esta restricción es:
αwp =
∑n
i=1 qi∑n
i=1 pi
=
∑n
i=1 πipi∑n
i=1 pi
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 26/38
Approximate Factorisation: Proportionality factorα Independently of any divergence measure
Weighted Average Method (WA):
Ü Calcula α como una media ponderada de los cocientes entre lashojas de T1 y T2.
El α que se obtiene es:
αwa =n
∑
i=1
hiπi ,
con hi ≥ 0, i = 1, . . . , n;∑
hi = 1.
αwp y αmse son casos particulares de αwa con
hi =pi
∑
i pi
y hi =p2
i∑
i p2i
resp.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 27/38
Approximate Factorisation: Proportionality factorα Independently of any divergence measure
Weighted Average Method (WA):
Ü Calcula α como una media ponderada de los cocientes entre lashojas de T1 y T2.
El α que se obtiene es:
αwa =n
∑
i=1
hiπi ,
con hi ≥ 0, i = 1, . . . , n;∑
hi = 1.
αwp y αmse son casos particulares de αwa con
hi =pi
∑
i pi
y hi =p2
i∑
i p2i
resp.Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 27/38
Approximate Factorisation: Proportionality factor
Medida de la bondad de la aproximación
Podemos aplicar dos medidas, de forma conjunta o alternativa.
La proximidad del potencial de cada nodo. Para δ1 > 0,
|qi − αpi| ≤ δ1 ∀i = 1, . . . , n.
Proximidad de los subárboles completos. Para δ2 > 0 y unamedida de divergencia,
dist(T2, T ∗2 ) ≤ δ2
Maximum Absolute Difference (MAD) entre la hojas de T2 y T ∗2 :
Dmad(T2, T ∗2 ) = max
1≤i≤n|qi − αpi|
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 28/38
Approximate Factorisation: Proportionality factor
Medida de la bondad de la aproximación
Podemos aplicar dos medidas, de forma conjunta o alternativa.
La proximidad del potencial de cada nodo. Para δ1 > 0,
|qi − αpi| ≤ δ1 ∀i = 1, . . . , n.
Proximidad de los subárboles completos. Para δ2 > 0 y unamedida de divergencia,
dist(T2, T ∗2 ) ≤ δ2
Maximum Absolute Difference (MAD) entre la hojas de T2 y T ∗2 :
Dmad(T2, T ∗2 ) = max
1≤i≤n|qi − αpi|
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 28/38
Approximate Factorisation: Proportionality factor
Medida de la bondad de la aproximación
Podemos aplicar dos medidas, de forma conjunta o alternativa.
La proximidad del potencial de cada nodo. Para δ1 > 0,
|qi − αpi| ≤ δ1 ∀i = 1, . . . , n.
Proximidad de los subárboles completos. Para δ2 > 0 y unamedida de divergencia,
dist(T2, T ∗2 ) ≤ δ2
Maximum Absolute Difference (MAD) entre la hojas de T2 y T ∗2 :
Dmad(T2, T ∗2 ) = max
1≤i≤n|qi − αpi|
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 28/38
Approximate Factorisation: Example
Supongamos que T1 y T2 son subárboles ”casi” proporcionales,hijos de un mismo nodo de un árbol T :
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
Para poder factorizar T , tenemos que buscar T ∗2 próximo a T2
que sea α-proporcional con T1
La siguiente tabla muestra las divergencias entre T2 y lasposibles aproximaciones T ∗
2 , que son proporcionales a T1:
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 29/38
Approximate Factorisation: Example
Supongamos que T1 y T2 son subárboles ”casi” proporcionales,hijos de un mismo nodo de un árbol T :
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
Para poder factorizar T , tenemos que buscar T ∗2 próximo a T2
que sea α-proporcional con T1
La siguiente tabla muestra las divergencias entre T2 y lasposibles aproximaciones T ∗
2 , que son proporcionales a T1:
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 29/38
Approximate Factorisation: Example
Supongamos que T1 y T2 son subárboles ”casi” proporcionales,hijos de un mismo nodo de un árbol T :
T1 :X
0.1
0
0.2
1
0.2
2
0.5
3
T2 :X
0.1999
0
0.4
1
0.4002
2
0.9999
3
Para poder factorizar T , tenemos que buscar T ∗2 próximo a T2
que sea α-proporcional con T1
La siguiente tabla muestra las divergencias entre T2 y lasposibles aproximaciones T ∗
2 , que son proporcionales a T1:
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 29/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Ü Eligiendo αχ, αmse y αwmse se minimiza la correspondientemedida de divergencia (respecto a la que se calcula)
Ü La divergencia absoluta máxima (Dmad) se minimiza, en esteejemplo, tomando αwa como proportionality factor.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 30/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Ü Eligiendo αχ, αmse y αwmse se minimiza la correspondientemedida de divergencia (respecto a la que se calcula)
Ü La divergencia absoluta máxima (Dmad) se minimiza, en esteejemplo, tomando αwa como proportionality factor.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 30/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Ü Eligiendo αχ, αmse y αwmse se minimiza la correspondientemedida de divergencia (respecto a la que se calcula)
Ü La divergencia absoluta máxima (Dmad) se minimiza, en esteejemplo, tomando αwa como proportionality factor.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 30/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Si T1 y T2 son hermanos bajo el contexto (XC = xC) de T :
Ü T es δ-factorizable en el contexto (XC = xC) para cualquierδ > 0.001, independientemente del α y de la medida D.
Ü Para δ ≤ 0.001, T no siempre es δ-factorizable:
→ para δ = 0.0002 y Dmad, T es δ-factorizable en el contexto (XC = xC)
sólo para αwp, αwa y αkl.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 31/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Si T1 y T2 son hermanos bajo el contexto (XC = xC) de T :
Ü T es δ-factorizable en el contexto (XC = xC) para cualquierδ > 0.001, independientemente del α y de la medida D.
Ü Para δ ≤ 0.001, T no siempre es δ-factorizable:
→ para δ = 0.0002 y Dmad, T es δ-factorizable en el contexto (XC = xC)
sólo para αwp, αwa y αkl.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 31/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Si T1 y T2 son hermanos bajo el contexto (XC = xC) de T :
Ü T es δ-factorizable en el contexto (XC = xC) para cualquierδ > 0.001, independientemente del α y de la medida D.
Ü Para δ ≤ 0.001, T no siempre es δ-factorizable:
→ para δ = 0.0002 y Dmad, T es δ-factorizable en el contexto (XC = xC)
sólo para αwp, αwa y αkl.
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 31/38
Approximate Factorisation: Example
αwp αχ αmse αwmse αkl αwa
2.0 1.9999998 1.9999412 1.9998733 2.0000001 2.0000002
Dmad 0.00020000 0.000200032 0.000211764 0.000225343 0.000199984 0.000199968
Dχ 0.00039997005 0.00039997003 0.000402115 0.000409859 0.00039997005 0.00039997009
Dχ∗ 0.00019998502 0.00019998501 0.000201057 0.000204929 0.00019998503 0.00019998504
Dmse 0.000122474 0.000122467 0.000121267 0.000122872 0.000122477 0.000122481
Dwmse 5.91671E-5 5.91549E-5 5.56270E-5 5.41362E-5 5.91732E-9 5.91793E-5
Si T1 y T2 son hermanos bajo el contexto (XC = xC) de T :
Ü T es δ-factorizable en el contexto (XC = xC) para cualquierδ > 0.001, independientemente del α y de la medida D.
Ü Para δ ≤ 0.001, T no siempre es δ-factorizable:
→ para δ = 0.0002 y Dmad, T es δ-factorizable en el contexto (XC = xC)
sólo para αwp, αwa y αkl.Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 31/38
Approximate Factorisation: Experiments
Lazy-Penniless Ü añadiendo la posibilidad de factorizar lospotenciales (probability trees) antes de borrar una variable
Se pueden seleccionar los siguientes parámetros:
Nivel máximo del árbol al que se puede ’bajar’buscando la variable a borrar.Proporción de hermanos proporcionales.Elegir entre 3 métodos de factorización:
sólo Splitsólo Factorizaciónambos a la vez
Podemos aplicar factorización de P.T.
sólo en fase de compilación (relaciones iniciales) Ü exactasólo en fase de propagaciónambas a la vez
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 32/38
Approximate Factorisation: Experiments
Lazy-Penniless Ü añadiendo la posibilidad de factorizar lospotenciales (probability trees) antes de borrar una variable
Se pueden seleccionar los siguientes parámetros:
Nivel máximo del árbol al que se puede ’bajar’buscando la variable a borrar.Proporción de hermanos proporcionales.Elegir entre 3 métodos de factorización:
sólo Splitsólo Factorizaciónambos a la vez
Podemos aplicar factorización de P.T.
sólo en fase de compilación (relaciones iniciales) Ü exactasólo en fase de propagaciónambas a la vez
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 32/38
Approximate Factorisation: Experiments
Lazy-Penniless Ü añadiendo la posibilidad de factorizar lospotenciales (probability trees) antes de borrar una variable
Se pueden seleccionar los siguientes parámetros:
Nivel máximo del árbol al que se puede ’bajar’buscando la variable a borrar.Proporción de hermanos proporcionales.Elegir entre 3 métodos de factorización:
sólo Splitsólo Factorizaciónambos a la vez
Podemos aplicar factorización de P.T.
sólo en fase de compilación (relaciones iniciales) Ü exactasólo en fase de propagaciónambas a la vez
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 32/38
Redes bayesianas. Árboles de probabilidad
Factorización de árboles de probabilidad
Factorización exacta
Factorización aproximada
Experimentos
Factorización en
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 33/38
Integración en Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.javaÜ elvira/tools/FactorisationTools.java
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ListPotential.javaÜ elvira/potential/PotentialTree.javaÜ elvira/potential/ProbabilityTree.java
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 34/38
Integración en Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.javaÜ elvira/tools/FactorisationTools.java
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ListPotential.javaÜ elvira/potential/PotentialTree.javaÜ elvira/potential/ProbabilityTree.java
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 34/38
Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.java
método main()
Inicializar relaciones Ü Fact. en fase de compilación: exactaFact. en fase de propagación: exacta o aproximada
Ü elvira/tools/FactorisationTools.java
Inicializar parámetrosMétodos para calcular α en factorización aproximadaMétodos de divergencia
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 35/38
Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.java
método main()
Inicializar relaciones Ü Fact. en fase de compilación: exactaFact. en fase de propagación: exacta o aproximada
Ü elvira/tools/FactorisationTools.java
Inicializar parámetrosMétodos para calcular α en factorización aproximadaMétodos de divergencia
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 35/38
Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.java
método main()
Inicializar relaciones Ü Fact. en fase de compilación: exactaFact. en fase de propagación: exacta o aproximada
Ü elvira/tools/FactorisationTools.java
Inicializar parámetrosMétodos para calcular α en factorización aproximadaMétodos de divergencia
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 35/38
Elvira. Clases relacionadasFactorización
Nuevas clases:
Ü elvira/inference/clustering/FactorisedSLP.java
método main()
Inicializar relaciones Ü Fact. en fase de compilación: exactaFact. en fase de propagación: exacta o aproximada
Ü elvira/tools/FactorisationTools.java
Inicializar parámetrosMétodos para calcular α en factorización aproximadaMétodos de divergencia
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 35/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ListPotential.java
Factorización en compilación
Ü factorisePotentialAllVbles()
Factorización en propagación
Ü factorMarginalizePotential()Ü factorAddVariable()
Métodos para comparar tamaños con S.L.P.
Ü marginalizePotential(..., Vector)Ü addVariable(..., Vector)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 36/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ListPotential.java
Factorización en compilación
Ü factorisePotentialAllVbles()
Factorización en propagación
Ü factorMarginalizePotential()Ü factorAddVariable()
Métodos para comparar tamaños con S.L.P.
Ü marginalizePotential(..., Vector)Ü addVariable(..., Vector)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 36/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ListPotential.java
Factorización en compilación
Ü factorisePotentialAllVbles()
Factorización en propagación
Ü factorMarginalizePotential()Ü factorAddVariable()
Métodos para comparar tamaños con S.L.P.
Ü marginalizePotential(..., Vector)Ü addVariable(..., Vector)
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 36/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/PotentialTree.java
Métodos para split: Ü splitOnlyPT() y split()
Método para factorizar: Ü factoriseOnlyPT()
Split y Factorización Ü splitAndFactorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 37/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/PotentialTree.java
Métodos para split: Ü splitOnlyPT() y split()
Método para factorizar: Ü factoriseOnlyPT()
Split y Factorización Ü splitAndFactorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 37/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ProbabilityTree.java
Métodos para buscar la variable y split
Ü findVarAndSplit(), findFreeTerm() y findCoreTerm()
Métodos para buscar la variable y factorizar
Ü findVarAndFactorise()
Comprobar proporcionalidad de los hijos de la variable:
Ü getUniqueFactor()
Ü isPropor(), isProporExact() y isProporApprox()
Extraer subárboles proporcionales Ü factorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 38/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ProbabilityTree.java
Métodos para buscar la variable y split
Ü findVarAndSplit(), findFreeTerm() y findCoreTerm()
Métodos para buscar la variable y factorizar
Ü findVarAndFactorise()
Comprobar proporcionalidad de los hijos de la variable:
Ü getUniqueFactor()
Ü isPropor(), isProporExact() y isProporApprox()
Extraer subárboles proporcionales Ü factorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 38/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ProbabilityTree.java
Métodos para buscar la variable y split
Ü findVarAndSplit(), findFreeTerm() y findCoreTerm()
Métodos para buscar la variable y factorizar
Ü findVarAndFactorise()
Comprobar proporcionalidad de los hijos de la variable:
Ü getUniqueFactor()
Ü isPropor(), isProporExact() y isProporApprox()
Extraer subárboles proporcionales Ü factorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 38/38
Elvira. Clases relacionadasFactorización
Otras clases relacionadas con árboles de probabilidad:
Ü elvira/potential/ProbabilityTree.java
Métodos para buscar la variable y split
Ü findVarAndSplit(), findFreeTerm() y findCoreTerm()
Métodos para buscar la variable y factorizar
Ü findVarAndFactorise()
Comprobar proporcionalidad de los hijos de la variable:
Ü getUniqueFactor()
Ü isPropor(), isProporExact() y isProporApprox()
Extraer subárboles proporcionales Ü factorisePT()
Almerıa 2005 . . . Factorizacion de Arboles de Probabilidad . . .– p. 38/38
Top Related