1. Ciencia

2014-2015
´
Aprendizaje Automatico
´
6. Modelos graficos
Francisco Casacuberta Nolla
([email protected])
Enrique Vidal Ruiz
([email protected])
`
Departament de Sistemas Informatics
i Computacio´ (DSIC)
`
`
Universitat Politecnica
de Valencia
(UPV)
December 17, 2014
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.1
Index
◦ 1 Introduccion
´ a los modelos graficos
´
2 Redes bayesianas
4
3 Inferencia en redes bayesianas
4 Aprendizaje de redes bayesianas
´
5 Otros modelos graficos
December 17, 2014
1
21
31
33
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.2
´
Modelos graficos
(MG)
´ compacta de distribuciones de probabilidad
• Concepto: Representacion
conjunta mediante grados dirigidos (redes bayesianas) y no dirigidos (campos
aleatorios markovianos) (Teor´ıa de grafos + teor´ıa de la probabilidad). Los
MGs generalizan a las redes neuronales y a los modelos de Markov ocultos
entre otros.
• Aspectos:
´ de probabilidad
– Inferencia: para responder cuestiones sobre la distribucion
´
´
– Aprendizaje: para obtener los parametros
y la estructura del modelo grafico
• Aplicaciones
´
´
– Diagnostico
medico,
de fallos, ...
´ por computador: segmentacion
´ de imagenes,
´
´ 3D,
– Vision
reconstruccion
´
analisis
de escenas
´ de
– Procesado del lenguaje natural: reconocimiento del habla, extraccion
´ textual, traduccion
´ automatica,
´
informacion
...
´
´ localizacion,
´ ...
– Robotica:
planificacion,
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.3
Algunos conceptos sobre la teor´ıa de las probabilidades
Probabilidad
P (x) :
P (x) = 1
x
Probabilidad conjunta
P (x, y) :
P (x, y) = 1
x
Probabilidad condicional
Marginales
P (x) =
P (x | y) :
P (x, y),
y
Regla de la probabilidad conjunta
y
x
P (x | y) = 1 ∀y
P (y) =
P (x, y)
x
P (x, y) = P (x) P (y | x)
N
Regla de la cadena
P (x1, x2, . . . , xN ) = P (x1)
i=2
Regla de Bayes
December 17, 2014
P (xi | x1, . . . , xi−1)
P (y | x) P (x) = P (y) P (x | y)
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.4
Index
´ a los modelos graficos
´
1 Introduccion
◦ 2 Redes bayesianas
1
4
3 Inferencia en redes bayesianas
21
4 Aprendizaje de redes bayesianas
´
5 Otros modelos graficos
31
33
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.5
Redes bayesianas
(Bishop. Pattern Recognition and Machine Learning. 2006)
Un ejemplo simple:
´ conjunta para tres variables: P (a, b, c) = P (a) P (b | a) P (c | a, b) que
Distribucion
se representa como un grafo ac´ıclico y dirigido:
a
b
c
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.6
´ ejemplos
Mas
P (a, b, c) =
P (a) P (b) P (c | a, b)
P (a, b, c, d, e, f ) =
P (a) P (b) P (c) P (d | b, c) P (e | a, b, d) P (f | a, c)
a
a
c
b
d
b
f
c
e
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.7
Un ejemplo detallado
P (A | L)
Lluvia (L)
n
s
Aspersor
P (L)
Aspersor (A)
f
p
0.40 0.60
0.01 0.99
Lluvia
Lluvia (L)
n
s
0.8 0.2
Césped
Aspersor
´
Cesped
Lluvia
f:
p:
m:
d:
s:
n:
funciona
parado
mojado
desecado
s´ı llueve
no llueve
P (C | A, L)
Aspersor (A)
p
p
f
f
Lluvia (L)
n
s
n
s
´
Cesped
(C)
m
d
0.00 1.00
0.80 0.20
0.90 0.10
0.99 0.01
´ conjunta: P (L, A, C) = P (L) P (A | L)P (C | L, A)
Distribucion
Ejercicio: calcular P (L = l, A = a, C = c),
December 17, 2014
l ∈ {s, n}, a ∈ {p, f}, c ∈ {m, d}.
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.8
Un ejemplo
´ es la probabilidad de que llueva si el cesped
´
• ¿Cual
esta´ mojado?
P (L = s, C = m)
P (C = m)
P (L = s | C = m) =
a∈{f,p} P (L
=
= s, A = a, C = m)
a∈{f,p},l∈{s,n} P (L
= l, A = a, C = m)
0.00198 + 0.1584
0.00198 + 0.288 + 0.1584 + 0.0
=
= 0.3577
´
• El cesped
esta´ mojado, ¿llueve?
arg max P (L = l | C = m) = n
l∈{s,n}
Ejercicio: a) Calcular P (A = a | L = l, C = c), a ∈ {p, f}, l ∈ {s, n}, c ∈ {m, d}.
´
b) Llueve y el cesped esta´ mojado, ¿como
esta´ el aspersor?
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.9
Otro ejemplo
P (P )
´ (P)
Polucion
a
b
0.1
0.9
P (X | C)
Rayos X (X)
´
Cancer
(C)
p
n
p
0.90 0.10
n
0.20 0.80
´
Polucion
Fumador
Disnea
Rayos X
´
Cancer
December 17, 2014
a:
b:
s:
n:
s:
n:
p:
n:
p:
n:
alto
bajo
s´ı
no
s´ı
no
positivo
negativo
positivo
negativo
P (F )
Polución
Fumador
Cáncer de
pulmón
Rayos X
Disnea
P (C | P, F )
´ (P)
Polucion
a
a
b
b
Fumador (F)
s
n
s
n
Fumador (F)
n
s
0.7
0.3
P (D | C)
Disnea (D)
´
Cancer
(C)
s
n
p
0.65 0.35
n
0.30 0.70
´
Cancer
(C)
p
n
0.05
0.95
0.08
0.92
0.03
0.97
0.001 0.999
´ es la probabilidad de que un paciente
Ejercicio: ¿Cual
´
no fumador no tenga cancer
si la radiograf´ıa ha dado un
resultado negativo pero sufre de disnea?
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.10
Redes bayesianas
Una red bayesiana es un grafo dirigido y ac´ıclico (“directed acyclic graph”
-DAG-) donde:
• Los nodos representan:
– variables (discretas o cont´ınuas)
– distribuciones de probabilidad condicional para cada variable xi dados
los valores de las variables asociadas a los nodos padres a(xi)
• Los arcos representan dependencias entre las variables
´ de
Una red bayesiana con nodos x1, . . . , xD define una distribucion
probabilidad conjunta:
D
P (x1, . . . , xD ) =
i=1
P (xi | a(xi))
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.11
Ejemplos simples de redes bayesianas
• El clasificador de Bayes (x ∈ Rd y c ∈ {1, . . . , C}):
c
P (c)
P (x, c) = P (c) P (x | c)
x
P (c | x) =
P (x | c)
P (x, c)
c P (x, c)
• Modelos naive-Bayes (xi ∈ R con 1 ≤ i ≤ d y c ∈ {1, . . . , C}):
c
P (c)
d
P (x1, . . . , xd, c) = P (c)
x1
P (x1 | c)
December 17, 2014
xd
i=1
P (xi | c)
P (xd | c)
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.12
Otro ejemplo: modelo oculto de Markov
P(q |q )
1 1
P(S|q ) P(q |q )
1
2 1
q
1
S ε {a, b, c}
P(q |q )
2 2
P(X |Q ) P(X |Q )
1 1
2 2
X1
X2
P(X |Q )
3 3
X3
P(X |Q )
4 4
X4
P(S|q )
2
q2
Q
1
P(Q )
1
Q
2
P(Q |Q )
2 1
Q
Q
3
P(Q |Q )
3 2
4
P(Q |Q )
4 3
P (X1 X2 X3 X4, Q1 Q2 Q3 Q4) =
P (Q1) P (X1 | Q1) P (Q2 | Q1) P (X2 | Q2) P (Q3 | Q2) P (X3 | Q3) P (Q4 | Q3) P (X4 | Q4)
P (X1 = a, X2 = a, X3 = b, X4 = c) =
P (X1 = a, X2 = a, X3 = b, X4 = c, Q1 = r1, Q2 = r2, Q3 = r3, Q4 = r4)
r1 ,r2 ,r3 ,r4 ∈{q1 ,q2 }
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.13
Independencia condicional
Se dice que a es independiente condicionalmente de b dado
´ que a esta´ D-separado de b por c, y se denota
c (o tambien
como: a b | c) si:
P (a | b, c) = P (a | c) ⇔ P (a, b | c) = P (a | c)P (b | c)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.14
Independencia condicional: estructuras t´ıpicas de RBs
´ causal a
Direccion
b
c
a
P (a, b | c) =
c
a
a
P (a)P (c | a)P (b | c)
= P (a | c)P (b | c)
P (c)
Causa comun
´ a
P (a, b | c) =
b
b|c
P (c)P (a | c)P (b | c)
= P (a | c)P (b | c)
P (c)
Estructura en V a / b | c
b
En general P (a, b | c) =
c
b|c
P (a)P (b)P (c | a, b)
= P (a | c)P (b | c)
P (c)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.15
Independencia condicional (I)
´ es la relacion
´ entre a y b?
• Caso 1: ¿Cual
P (a, b, c) = P (a)P (c | a)P (b | c)
a
c
b
P (a, b) =
c P (a)P (c
| a)P (b | c)
En general P (a, b) = P (a)P (b) ⇒ a / b | ∅
a
c
b
P (a, b | c) =
P (a, b, c) P (a)P (c | a)P (b | c)
=
P (c)
P (c)
= P (a | c)P (b | c) ⇒ a
b|c
El nodo c es cabeza-con-cola con respecto al camino desde a a b via c: Dos
nodos a y b conectados via un nodo c cabeza-con-cola son independientes
condicionalmen si c esta´ dado (nodo c bloquea al camino desde a a b).
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.16
Independencia conditional (II)
´ es la relacion
´ entre a y b?
• Caso 2: ¿Cual
P (a, b, c) = P (a | c)P (b | c)P (c)
c
P (a, b) =
a
c P (a
| c)P (b | c)P (c)
En general P (a, b) = P (a)P (b) ⇒ a / b | ∅
b
c
P (a, b | c) =
a
P (a, b, c)
= P (a | c)P (b | c) ⇒ a
P (c)
b|c
b
El nodo c es cola-con-cola con respecto a el camino desde a a b via c:
Dos nodos a y b conectados via un nodo c cola-con-cola son independientes
condicionalmente si c esta´ dado, (nodo c bloquea al camino desde a a b).
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.17
Independencia conditional (III)
´ es la relacion
´ entre a y b?
• Caso 3: ¿Cual
a
b
P (a, b, c) = P (a)P (b)P (c | a, b)
P (a, b) =
= P (a)P (b) ⇒ a
c
a
b
P (a, b | c) =
c
c P (a)P (b)P (c
| a, b)
b|∅
P (a, b, c) P (a)P (b)P (c | a, b)
=
P (c)
P (c)
En general P (a, b | c) = P (a | c)P (b | c) ⇒ a / b | c
El nodo c es to cabeza-con cabeza con respecto al camino desde a a b via c: Dos
nodos a y b conectados via un nodo c cabeza-con-cabeza no son independientes
condicionalmete si c esta´ dado, pero en caso contrario son independientes
condicionalmente (nodo c bloquea al camino desde a a b cunado c esta´ dado).
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.18
Independencia condicional: Ejemplo
• B es el estado de la bater´ıa (cargada B = 1 o descargada B = 0)
´
• C es el estado del deposito
de combustible (lleno C = 1 o vac´ıo C = 0)
´
• I es el estado del indicador electrico
del combustible (lleno I = 1 o vac´ıo I = 0)
P (B = 1) = P (C = 1) = 0.9
B
C
P (I = 1 | B = 1, C = 1) = 0.8
P (I = 1 | B = 1, C = 0) = 0.2
I
P (I = 1 | B = 0, C = 1) = 0.2
P (I = 1 | B = 0, C = 0) = 0.1
P (B, I, C) = P (B) P (C) P (I | B, C)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.19
Independencia condicional
P (B
P (B
P (I =
P (I =
P (I =
P (I =
= 1) = P (C
= 0) = P (C
1 | B = 1, C
1 | B = 1, C
1 | B = 0, C
1 | B = 0, C
=
=
=
=
=
=
1)
0)
1)
0)
1)
0)
=
=
=
=
=
=
0.9
0.1
0.8
0.2
0.2
0.1
B
C
I
B
C
I
P (B, I, C) = P (B) P (C) P (I | B, C)
´ sobre I ¿cual
´ es la probabilidad conjunta de B y C ?:
Si no tenemos informacion
P (B = 0, C = 0) = P (B = 0, C = 0, I = 0)+P (B = 0, C = 0, I = 1) = 0.01 = P (B = 0) P (C = 0)
⇒ B C|∅
´ es la probabilidad P (B = 0, C = 0 | I = 0)?
Supongamos que vemos I = 0, ¿Cual
P (B = 0, C = 0 | I = 0) =
P (B = 0 | I = 0) =
P (C = 0 | I = 0) =
P (B = 0) P (C = 0) P (I = 0 | B = 0, C = 0)
= 0.02857
b,c∈{0,1} P (B = b) P (C = c) P (I = 0 | B = b, C = c)
P (B = 0) P (C = c) P (I = 0 | B = 0, C = c)
= 0.25714
P (B = b) P (C = 0) P (I = 0 | B/! = /!b, C = 0)
= 0.25714
c∈{0,1}
b,c∈{0,1}
b∈{0,1}
P (B = b) P (C = c) P (I = 0 | B = b, C = c))
b,c∈{0,1}
P (B = b) P (C = c) P (I = 0 | B = b, C = c))
P (B = 0, C = 0 | I = 0) = P (B = 0 | I = 0) P (C = 0 | I = 0) = 0.06612 ⇒ B / C | I
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.20
Independencia condicional
P (B
P (B
P (I =
P (I =
P (I =
P (I =
= 1) = P (C
= 0) = P (C
1 | B = 1, C
1 | B = 1, C
1 | B = 0, C
1 | B = 0, C
=
=
=
=
=
=
1)
0)
1)
0)
1)
0)
=
=
=
=
=
=
0.9
0.1
0.8
0.2
0.2
0.1
B
B
C
C
B
C
I
I
I
P (B, I, C) = P (B) P (C) P (I | B, C)
´ es la probabilidad P (C = 0 | I = 0)?
Supongamos que vemos I = 0, ¿Cual
P (C = 0 | I = 0)
=
=
P (I = 0, C = 0)
=
P (I = 0)
B∈{0,1}
B∈{0,1}
=
B∈{0,1}
B∈{0,1}
P (I = 0, C = 0, B)
C∈{0,1}
P (I = 0, C, B)
P (I = 0 | B, C = 0)P (B)P (C = 0)
C∈{0,1}
P (I = 0 | B, C)P (B)P (C)
0.9 · 0.1 · 0.1 + 0.8 · 0.9 · 0.1
≈ 0.257 > P (C = 0)
0.315
Supongamos que vemos B = 0, P (C = 0 | I = 0, B = 0) ≈ 0.111 < P (C = 0 | I = 0)
Por otra parte, si no conocemos I , P (C = 0 | B = 0) = 0.1 = P (C = 0)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.21
Index
´ a los modelos graficos
´
1 Introduccion
2 Redes bayesianas
4
◦ 3 Inferencia en redes bayesianas
4 Aprendizaje de redes bayesianas
´
5 Otros modelos graficos
December 17, 2014
1
21
31
33
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.22
Inferencia con redes bayesianas
• En general, el problema consiste en calcular la probabilidad a posteriori de alguna
variable x a partir de las distribuciones conjuntas asociadas a una RB, dada alguna
evidencia e (como valores dados de alguna otra variable) y sin importar los valores
de resto de las variable f :
P (x | e) =
P (x, e)
con P (e) =
P (e)
P (x, e, f ) y P (x, e) =
x,f
P (x, e, f )
f
• El objetivo es calcular eficientemente P (e)
´ conjunta dada por
• Por ejemplo: Sea P (x1, x2, x3, x4) una distribucion
P (x1, x2, x3, x4) = P (x2)P (x1 | x2)P (x3 | x2)P (x4 | x3)
y se pretende calcular P (x3). Si xi ∈ X para i = 1, 2, 3 verifica que |X| = n
– P (x3) =
x1 ,x2 ,x4
– P (x3) =
x2
=
x2
P (x2)P (x1 | x2)P (x3 | x2)P (x4 | x3) ⇒ O(n3) operaciones.
P (x2)P (x3 | x2)
x1
P (x1 | x2)
x4
P (x4 | x3)
P (x2)P (x3 | x2) ⇒ O(n) operaciones.
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.23
Inferencia con redes bayesianas
Situaciones donde es util
´ calcular las probabilidades a-posteriori:
´ ¿Cual
´ es la probabilidad de observar un s´ıntoma sabiendo que se
• Prediccion:
tiene una determinada enfermedad?
´
´ es la probabilidad de que una determinada enfermedad
• Diagnostico:
¿Cual
´
sea un diagnostico
correcto dados algunos s´ıntomas?
´ de los enlaces entre variables no restringe el tipo de preguntas
En RB, la direccion
que se pueden hacer.
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.24
Tipos de redes bayesianas
Cadena
Árbol
Grafo
Poli-árbol
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.25
Inferencia en una cadena.
´ de creencias (“Belief propagation”)
Propagacion
xi
x i+1
Ex+
n
x n-1
xn
x n+1
x f-1
xf
Exn
´ dados
Supongamos que el menor xi ∈ Ex+n y el mayor xf ∈ Ex−n estan
P (xn | xi, xf ) =
P (xi, xf | xn) P (xn)
P (xi, xf )
=
P (xi | xn) P (xf | xn) P (xn)
P (xi, xf )
=
P (xn | xi) P (xi) P (xf | xn) P (xn)
P (xn) P (xi, xf )
= α P (xn | xi) P (xf | xn)
(Indepencia condicional)
(Regla de Bayes)
(α = P (xi)/P (xi, xf ))
´ conocemos xi ∈ Ex+n con i < i?
• Ejercicio: ¿Que´ ocurre si tambien
´ conocemos xf ∈ Ex−n con f > f ?
• Ejercicio: ¿Que´ ocurre si tambien
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.26
Inferencia en una cadena
π (xn )
xi
x i+1
x n-1
Ex+
n
λ (x )
n
xn
x n+1
x f-1
xf
Exn
def
P (xn | xi, xf ) = α P (xn | xi) P (xf | xn) = α π(xn) λ(xn)
donde π(xn) y λ(xn) se calculan como:
π(xi) = 1
λ(xf ) = 1
π(xn) =
xn−1
P (xn | xn−1) π(xn−1)
λ(xn) =
xn+1
P (xn+1 | xn) λ(xn+1)
• Ejercicio: P (xn)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.27
´ I)
Inferencia en una cadena (derivacion
π (xn-1 )
xi
x i+1
Ex+
n
π(xn) = P (xn | xi) =
=
xn−1
=
xn−1
π (xn )
x n-1
xn−1
xn
x n+1
x f-1
xf
Exn
P (xn, xn−1 | xi)
P (xn−1 | xi) P (xn | xi, xn−1) =
xn−1
P (xn−1 | xi) P (xn | xn−1)
π(xn−1) P (xn | xn−1)
π(xi) = 1
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.28
´ II)
Inferencia en una cadena (derivacion
λ (xn+1 )
λ (x )
n
xi
x i+1
x n-1
Ex+
n
λ(xn) = P (xf | xn) =
=
xn+1
=
xn+1
xn+1
x n+1
xn
x f-1
xf
Exn
P (xf , xn+1 | xn)
P (xn+1 | xn) P (xf | xn, xn+1) =
xn+1
P (xn+1 | xn) P (xf | xn+1)
P (xn+1 | xn) λ(xn+1)
λ(xf ) = 1
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.29
´
Inferencia en un arbol
ui
π x (ui )
λ x(uj i )
λ y (xj)
E+xj
j
xj
k
π y (x j)
k
y
k
E-xj
Para calcular P (xj | Ex+j , Ex−j ) = α π(xj ) λ(xj )
m
λyk (xj ) con λyk (xj ) =
λ(xj ) =
k=1
π(xj ) =
ui
December 17, 2014
yk
λ(yk ) P (yk | xj )
P (xj | ui) πxj (ui) con πxj (ui) = α
λxj (ui) π(ui)
j =j
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.30
Inferencia en otros tipos de grafos
• Poli-arboles (“Polytrees”). Los nodo pueden tener multiples
´
padres, pero solo puede existir un camnino unico
entre cualquier
´
´ del algoritmo sobre un arbol.
´
par de nodos: una generalizacion
´
´ en
• Arboles
conjuntos (“Junction Trees”). Con bucles: conversion
´
un poli-arbol
• Grafos generales. Inferencia aproximada:
´
– Metodos
variacionales.
´
– Metodos
basados en el muestreo.
´ del algoritmo suma– “Loopy belief propagation”: aplicacion
producto en el grafo general.
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.31
Index
´ a los modelos graficos
´
1 Introduccion
2 Redes bayesianas
4
3 Inferencia en redes bayesianas
◦ 4 Aprendizaje de redes bayesianas
´
5 Otros modelos graficos
December 17, 2014
1
21
31
33
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.32
Aprendizaje de redes bayesianas
• Dada la estructura, aprender las distribuciones de probabilidad a partir de
un conjunto de entrenamiento.
´
´ de la verosimilitud.
– Metodos
basados en la maximizacion
– Aprendizaje bayesiano.
• Aprender la estructura a partir de un conjunto de entrenamiento.
´ de modelos: busqueda
– Un problema de seleccion
en el espacio de
´
grafos.
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.33
Index
´ a los modelos graficos
´
1 Introduccion
2 Redes bayesianas
4
3 Inferencia en redes bayesianas
4 Aprendizaje de redes bayesianas
◦ 5 Otros modelos graficos
´
December 17, 2014
1
21
31
33
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.34
Campos de Markov aleatorios
• Aspectos generales:
– Independencia conditional simplificada
´ compleja de distribuciones de probabilidad.
– Asignacion
´ de un campo de Markov aleatorio
• Definicion
– Dado un conjunto de variables V = {x1, . . . , xN }
– Un grafo no-dirigido R = (V, E)
– Para un clique C in R (Un subgrafo completamente conectado), VC es el
conjunto variables en el clique C:
P (x1, . . . , xN ) =
1
Z
ψC (VC )
∀C∈R
´ potential (estrictamente positiva) y Z es un factor de
ψC (VC ) is a funcion
´ (funcion
´ de particion).
´
normalizacion
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.35
Campos de Markov aleatorios
P (x1, . . . , xN ) =
1
Z
ψC (VC )
∀C∈R
• Las funciones de potencial son de la forma: ψC (VC ) = exp (−E(VC )),
´ de energ´ıa.
donde E(VC ) es una funcion
´ de energ´ıa interesante es el queda definido mediante
• Un tipo de funcion
funciones lineales generalizadas:
E(xC ) = −
θC,k fC,k (VC )
k
• A partir de una red bayesiana se puede construir un campo de Markov
aleatorio
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.36
Un ejemplo
(Bishop. Pattern Recognition and Machine Learning. 2006)
Una matriz x de p´ıxeles binarios
xi ∈ {−1, +1}, 1 ≤ i ≤ D
La imagen esta´ corrupta con probabilidad
10% en una matriz y de p´ıxeles binarios
yi ∈ {−1, +1}, 1 ≤ i ≤ D
El objetivo es recuperar la imagen original
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.37
Un ejemplo
(Bishop. Pattern Recognition and Machine Learning. 2006)
´ entre xi y yi
• Hay una fuerte correlacion
yi
´ entre xi y xj si los dos p´ıxeles
• Hay una correlacion
son vecinos.
xi
´ de energ´ıa (cliques maximos:
´
• La funcion
(xi, xj∈N (i)), (xi, yi)):
E(x1, . . . , xD , y1, . . . , yD ) = −β
i,j
xi xj − ν
xiyi
i
´ conjunta:
• La distribucion
P (x1, . . . , xD , y1, . . . , yD ) =
December 17, 2014
1
exp (−E(x1, . . . , xD , y1, . . . , yD ))
Z
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.38
Un ejemplo
(Bishop. Pattern Recognition and Machine Learning. 2006)
´ conjunta:
• A partir de la distribucion
P (x1, . . . , xD , y1, . . . , yD ) =

1
exp β
Z
xi xj + ν
i,j
i

xiyi
• el objetivo es: (ˆ
x1 , . . . , x
ˆD ) = arg max P (x1, . . . , xD | y1, . . . , yD )
x1 ,...,xD
Esto es:
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.39
Inferencia con campos de Markov aleatorios
´ (”Backward-Forward
• En cadenas: Algoritmo Adelante-Atras
algorithm”)
´
• En arboles:
Algoritmo Suma-Producto
´
´ (“Junction
• En grafos generales: Algoritmo de arbol
de union
tree algorithms”)
December 17, 2014
DSIC – UPV
´
Aprendizaje Automatico.
2014-2015
´
Modelos graficos:
6.40
Algunos toolkits
• GMTK
http://melodi.ee.washington.edu/˜bilmes/gmtk/
• GraphLab
http://graphlab.org/toolkits/graphical-models/
• PMTK3 probabilistic modeling toolkit for Matlab/Octave
https://github.com/probml/pmtk
• Software Packages for Graphical Models
http://www.cs.ubc.ca/˜murphyk/Software/bnsoft.html
December 17, 2014
DSIC – UPV