{ "metadata": { "name": "06_Graphical_Models" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

# Graphical Models

\n", "Probabilistic graph models provide an intuitive way to express joint probability relationships. The nodes in a graph represent random variables and the edges between nodes represent a probabilistic relationship between variables. \n", "\n", "

## Bayesian Networks

\n", "Here we consider **acyclic directed** graphical models that express the joint probability relationship between some set of variables, known as *Bayesian Networks* because of the prominant use of Bayes' Theorem. To begin, consider the joint probability distribution $p\\left( x_1, \\ldots, x_K \\right)$ over $K$ variables. Using repeated application of the product rule, this can be expressed as \n", "\n", "$$p \\left(x_1, \\ldots, x_K \\right) = p \\left(x_K \\mid x_1, \\ldots, x_{K-1} \\right) \\ldots p\\left(x_2 \\mid x_1 \\right) p\\left(x_1\\right)$$\n", "\n", "This can be represented graphically as a **fully connected** directed graph having $K$ nodes, with each node having **incoming** links from all **lower** numbered nodes. \n", "\n", "Now consider the general case where the graph is **not necessarily** fully connected. Let the a given node $x_k$ have **incoming** links from the set of nodes $pa_k$ known as the *parent nodes* of $x_k$. Then the joint distribution defined by the directed acyclic graph over all nodes is given by the product of a conditional distribution for *each node conditioned on its parent nodes*. A graph with $K$ nodes has the joint distribution defined as\n", "\n", "$$p\\left(\\mathbf{x}\\right) = \\prod_{k=1}^K p\\left(x_k \\mid pa_k \\right)$$\n", "\n", "

## Graphical Notation

\n", "There are several conventions used to convey information in graphical models. They are briefly summarized here - see Bishop 363-365 for more detail.\n", "\n", "+ Represent multiple nodes of the form $t_1, \\ldots, t_N$ as a single node with a box, known as a *plate*, drawn around it and annotated with $N$, the number of repeated nodes.\n", "\n", "+ Deterministic model parameters, e.g. the mean of a distribution, are drawn as solid circles, and random variables as open circles\n", "\n", "+ Observed variables are drawn as shaded open circles\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

## Conditional Independence

\n", "Consider three random variables $a,b,c$, we use the following notation to indicate that $a$ is *conditionally idependent* of $b$ given $c$\n", "\n", "$$a \\perp\\\\!\\\\!\\\\!\\perp b \\mid c$$\n", "\n", "When this condition holds, using the product rule, we may write the joint distribution of $a$ conditioned on $b$ and $c$ as\n", "\n", "$$p\\left(a, b \\mid c \\right) = p\\left(a\\mid b,c\\right)p\\left(b\\mid c\\right) = p\\left(a\\mid c\\right) p\\left(b \\mid c\\right)$$\n", "\n", "

### D-separation

\n", "Given the description of conditional independence above, we now consider a general directed acyclic graph. Let $A$, $B$, and $C$ be arbitrary sets of *nonintersecting* nodes. We wish to determine if the graph structure implies the conditional independence $A \\perp\\\\!\\\\!\\\\!\\perp B \\mid C$. It turns out this conidition is satisfied if **all** possible paths from **any** node in $A$ to **any** node in $B$ are *blocked*, in which case $A$ is said to be *d-separated* from $B$. A path is considered blocked if either of the following hold:\n", "\n", "**(a)** There is a node, $n \\in C$, in the path such that the arrows on the path meet head-to-tail or tail-to-tail at n\n", "\n", "**(b)** There is a node, $n \\notin C$ with none of its descendants in $C$, in the path such that the arrows meet head-to-head at the node. A node $d$ is considered to a descendant of a node $p$ if there is a path from $p$ to $d$ in which each path step is in the direction of the arrows connecting the nodes on th path.\n", "\n", "Note that model parameters (e.g. the mean of a distribution) will always be tail-to-tail and therefore play no role in determining d-separation. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "-------------------------------------------\n", "\n", "

## Training a Bayes Net

\n", "MLE for training a Bayes Net, estimating the theta parameters for the nodes, is the equivalent to maximizing the likelihood of the data. So for each node, probability of the node being equal to $s$ be conditioned on say $f$ and $a$, then we have - TODO - generalize this to N conditional quantities\n", "\n", "$$\\theta_{s|ij} = \\frac{\\sum_{k=1}^K \\delta \\left(f_k = i, a_k =j, s_k =1 \\right)}{\\sum_{k=1}^K \\delta \\left(f_k=i, a_k=j \\right)}$$\n", "\n", "where\n", "$\\delta(x) = 1$ \n", "\n", "if $x$ is true, 0 otherwise" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

### Partially Observed Data

\n", "Can't use the MLE approach above due to lack of data\n", "Let $X$ be all *observed* variables values\n", "Let $Z$ be all *unobserved* variables\n", "Assume we always observe/unobserve the same variables - it is possible to generalize this\n", "\n", "Approach:\n", "\n", "$argmax_{\\theta} E_{P(Z|X,\\theta)}\\left[log P(x,z|\\theta) \\right]$\n", "\n", "using some probability distribution on $Z$, namely, $P(Z|X,\\theta)$ - do we need a model for this distribution?\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

### Expectation Maximization (EM) Algorithim

\n", "guaranteed to find local maximum of expected log likelihood above\n", "\n", "$argmax_{\\theta} E_{P(Z|X,\\theta)}\\left[log P(x,z|\\theta) \\right]$\n", "\n", "see slide at 29:59\n", "\n", "EM - general procedure for learning from partly observed data. Given observed varialbes, $X$, and unobserved variables, $Z$, define\n", "\n", "$Q\\left(\\theta' | \\theta \\right) = E_{E_{P(Z|X,\\theta)}} \\left[\\log P(X,Z | \\theta') \\right]$\n", "\n", "Iterate until convergence:\n", "\n", "* E Step: Use $X$ and current $\\theta$ to calculate $P(Z|X,\\theta)$ - done for every variable in $Z$ for each training example, \n", "\n", "* M Step: Replace current $\\theta$ by \n", "\n", "$\\theta \\leftarrow arg max_{\\theta'} Q$\n", "\n", "using step 1, plug into into last equation on slide 29:59 and pick max theta\n", "\n", "Example: see slide 38:59, 50:59\n", "\n", "More generally: Given observed variables $X$ and unobserved variables $Z$ all of which are boolean:\n", "\n", "* E Step: Calculate for each training example, $k$, the expected value of each unobserved variable in $Z$\n", "\n", "* M Step: Calculate estimates similar to MLE, but replacing each count (i.e. observed data proportions) by its expected count\n", "\n", "$\\delta(Y=1) \\rightarrow E_{Z|X,\\theta}[Y]$\n", "\n", "$\\delta(Y=0) \\rightarrow 1 - \\delta(Y=1)$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

## Example: Linear Gaussian Model

\n", "*TODO* A useful example may be a Linear-Gaussian model - see Bishop pages 370-372 - " ] } ], "metadata": {} } ] }