Introduccion a los Modelos Graficos Probabilistas

Introduccio´n a los

Modelos Gr´aficos Probabilistas

Francisco Javier D´ıez

Dpto. Inteligencia Artificial

UNED

Primera edici´on: octubre de 2007

Revisio´n: 24 de octubre de 2014

´Indice general

Prefacio        v

1. Fundamentos de redes bayesianas        1

        Resumen        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        1

        Contexto        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        1

        Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        1

        Requisitos previos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        2

        Contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        2

1. Repaso de la teor´ıa de la probabilidad . . . . . . . . . . . . . . . . . . . . . .        2

1. Definiciones b´asicas sobre probabilidad . . . . . . . . . . . . . . . . . .        2
2. Independencia y correlaci´on . . . . . . . . . . . . . . . . . . . . . . . .        7
3. Teorema de Bayes        . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        10

1. M´etodo bayesiano ingenuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        16

1. Forma racional del m´etodo bayesiano ingenuo . . . . . . . . . . . . . .        19
2. Discusi´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        20

1. Nociones sobre grafos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        21

1. Definiciones b´asicas        . . . . . . . . . . . . . . . . . . . . . . . . . . . .        21
2. Grafos dirigidos ac´ıclicos . . . . . . . . . . . . . . . . . . . . . . . . . .        24

1. Definici´on de red bayesiana . . . . . . . . . . . . . . . . . . . . . . . . . . . .        26

1. Construcci´on de una red bayesiana . . . . . . . . . . . . . . . . . . . .        26
2. Propiedad de Markov        . . . . . . . . . . . . . . . . . . . . . . . . . . .        29

1. Grafos de dependencias e independencias probabilistas . . . . . . . . . . . . .        31

1. Separaci´on en grafos dirigidos y no dirigidos . . . . . . . . . . . . . . .        31
2. Mapas de independencias . . . . . . . . . . . . . . . . . . . . . . . . .        32
3. Separaci´on direccional y redes bayesianas        . . . . . . . . . . . . . . . .        33

1. Causalidad y correlaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        34

1. Interpretaci´on probabilista e interpretaci´on causal de un grafo . . . . .        34
2. Diferencia entre causalidad y correlaci´on . . . . . . . . . . . . . . . . .        34

        Bibliograf´ıa recomendada        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        36

        Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        37

1. Inferencia en redes bayesianas        39

        Resumen        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39

        Contexto        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39

Requisitos previos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        39

Contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        40

1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . .        40

1. Diagn´ostico probabilista . . . . . . . . . . . . . . . . . . . . . . . . . .        40
2. M´etodo de fuerza bruta . . . . . . . . . . . . . . . . . . . . . . . . . .        40

1. M´etodos exactos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        42

1. Eliminaci´on de variables . . . . . . . . . . . . . . . . . . . . . . . . . .        42
2. Agrupamiento        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        46
3. Variantes del m´etodo de agrupamiento . . . . . . . . . . . . . . . . . .        59
4. Inversi´on de arcos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        67

1. M´etodos aproximados        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        77

1. Fundamento de los m´etodos estoc´asticos . . . . . . . . . . . . . . . . .        77
2. Muestreo l´ogico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        77
3. Ponderaci´on por verosimilitud . . . . . . . . . . . . . . . . . . . . . . .        78
4. Otros m´etodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        78
5. Complejidad computacional de los m´etodos estoc´asticos . . . . . . . .        78

Bibliograf´ıa recomendada        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        78

Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        78

...