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

1. Construcci´on de redes bayesianas        81

Resumen        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        81

Contexto        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        81

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        81

Requisitos previos        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        81

Contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        82

1. Construcci´on de redes causales con conocimiento experto . . . . . . . . . . . .        82

1. Necesidad de la construcci´on manual (en algunos casos) . . . . . . . .        82
2. Fase cualitativa: estructura de la red . . . . . . . . . . . . . . . . . . .        83
3. Fase cuantitativa: obtenci´on de las probabilidades condicionales . . . .        85
4. Resumen        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        88

1. Modelos can´onicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        89

1. Modelos deterministas . . . . . . . . . . . . . . . . . . . . . . . . . . .        90
2. Modelos IIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        92
3. Modelos OR/MAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        93
4. Uso de los modelos can´onicos en la construcci´on de redes bayesianas .        97

1. Aprendizaje autom´atico a partir de bases de datos . . . . . . . . . . . . . . .        99

1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . .        99
2. Cuestiones generales sobre aprendizaje . . . . . . . . . . . . . . . . . .        100
3. Aprendizaje param´etrico . . . . . . . . . . . . . . . . . . . . . . . . . .        104
4. Aprendizaje estructural a partir de relaciones de independencia . . . .        106
5. Aprendizaje estructural mediante bu´squeda heur´ıstica . . . . . . . . .        108
6. Otras cuestiones        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        110

ii

        Bibliograf´ıa recomendada        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        111

        Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        111

1. An´alisis de decisiones        113

        Resumen        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        113

        Contexto        . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        113

        Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        114

...