Chapter 17 - Undirected Graphical Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 17 - Undirected Graphical Models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.1 - Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A graph consists of a set of vertices (nodes), along with a set of edges joining some pairs of the vertices. \n",
    "* In graphical models, each vertex represents a random variable, and the graph gives a visual way of understanding the joint distribution of the entire set of random variables.\n",
    "* Undirected graphical models are also known as Markov random fields or Markov networks.\n",
    "* The absence of an edge between two vertices has a special meaning: the corresponding random variables are conditionally independent, given the other variables.\n",
    "* The edges in a graph are parametrized by values or *potentials* that encode the strength of the conditional dependence between the random variables at the corresponding vertices. \n",
    "* The main challenges in working with graphical models are choosing the structure of the graph, estimation of the edge parameters from data, and computation of marginal vertex probabilities and expectations from their joint distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.2 - Markov Graphs and Their Properties"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* A graph G consists of a pair (V, E), where V is a set of vertices and E the set of edges. \n",
    "* Two vertices X and Y are called adjacent if there is a edge joining them; this is denoted by X ∼ Y.\n",
    "* A path $X_1, X_2,\\dots, X_n$ is a set of vertices that are joined.\n",
    "* A complete graph is a graph with every pair of vertices joined by an edge. \n",
    "* A subgraph U ∈ V is a subset of vertices together with their edges.\n",
    "* If A, B and C are subgraphs, then C is said to separate A and B if every path between A and B intersects a node in C.\n",
    "* Separators have the nice property that they break the graph into conditionally independent pieces. \n",
    "* A clique is a complete subgraph — a set of vertices that are all adjacent to one another.\n",
    "* A subgraph is called maximal if it is a clique and no other vertices can be added to it and still yield a clique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.3 - Undirected Graphical Models for Continuous Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Gaussian distributions are almost always used for graphical models where all variables are continuous, because of its convenient analytical properties.\n",
    "* We assume that the observations have a multivariate Gaussian distribution with mean μ and covariance matrix Σ. Since the Gaussian distribution represents at most second-order relationships, it automatically encodes a pairwise Markov graph. \n",
    "* The Gaussian distribution has the property that all conditional distributions are also Gaussian. \n",
    "* The inverse covariance matrix captures all the second-order information (both structural and quantitative) needed to describe the conditional distribution of each node given the rest, and is the so-called \"natural\" parameter for the Gaussian graphical model.\n",
    "\n",
    "**Estimation of the Parameters when the Graph Structure is Known**\n",
    "* Given some realizations of X, we would like to estimate the parameters of an undirected graph that approximates their joint distribution.\n",
    "* If the graph is fully connected and we assume a multi-variate Gaussian distribution for $X$ with mean $\\mu$ and covariance $\\sigma$, then it can be shown that the maximum likelihood estimate for $\\sigma$ is just the empirical covariance estimate.\n",
    "* If we decide that some edges are missing (not fully connected), then the optimization problem becomes one that is constrained since some of the covariance entries will be 0.\n",
    "\n",
    "**Estimation of the Graph Structure**\n",
    "* In most cases, we do not know which edges to omit from our graph, and so would like to try to discover this from the data itself. \n",
    "* In recent years, a number of authors have proposed the use of lasso regularization for this purpose.\n",
    "* To determine if an entry in the covariance matrix should be 0 (and therefore no edge), we can fit a lasso regression using each variable as the response and the others as predictors. Then, we can use the coefficients of the predictors to determine if that variable is correlated with the response variable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.4 - Undirected Graphical Models for Discrete Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Undirected Markov networks with all discrete variables are popular, and in particular pairwise Markov networks with binary variables being the most common. \n",
    "* They are sometimes called Ising models in the statistical mechanics literature, and Boltzmann machines in the machine learning literature, where the vertices are referred to as “nodes” or “units” and are binary-valued.\n",
    "* Boltzmann machines are useful both for unsupervised and supervised learning, especially for structured input data such as images.\n",
    "* The Ising model is used more generally to model the joint effects of pairwise interactions of binary variables.\n",
    "\n",
    "**Estimation of the Parameters when the Graph Structure is Known**\n",
    "* The gradient of the likelihood functions is defined so we can use Newton or other methods to maximize it.\n",
    "* However, this not generally feasible for large $p$.\n",
    "* For small $p$ some approaches are:\n",
    "    * Poisson log-linear modeling where we treat the problem as a large regression problem. This is manageable for p < 20.\n",
    "    * Gradient descent can handle problems with p $\\leq$ 30.\n",
    "    * Iterative proportional fitting (IPF) performs cyclical coordinate descent on the gradient equations.\n",
    "* For larger $p$, some approaches are:\n",
    "    * The mean field approximation.\n",
    "    * Gibbs sampling.\n",
    "    * Using decomposable models, for which the maximum likelihood estimates can be found in closed form without any iteration whatsoever. \n",
    "    \n",
    "**Hidden Nodes**\n",
    "* We can increase the complexity of a discrete Markov network by including latent or hidden nodes.\n",
    "\n",
    "**Estimation of the Graph Structure**\n",
    "* Again, we can estimate these using the lasso penalty technique discussed above.\n",
    "* Alternatively, fit an $L_1$-penalized logistic regression model to each node as a function of the other nodes, and then symmetrize the edge parameter estimates in some fashion.\n",
    "\n",
    "**Restricted Boltzmann Machines**\n",
    "* A restricted Boltzmann machine (RBM) consists of one layer of visible units and one layer of hidden units with no connections within each layer.\n",
    "* This is inspired by neural networks.\n",
    "* The restricted form of this model simplifies the Gibbs sampling for estimating the expectations, since the variables in each layer are independent of one another, given the variables in the other layers. \n",
    "* The resulting model is less general than a Boltzmann machine, but is still useful; for example it can learn to extract interesting features from images.\n",
    "* As noted the restricted Boltzmann machine has the same generic form as a single hidden layer neural network.\n",
    "* The RBM can extract information from the input features that is useful for predicting the labels, but, unlike supervised learning methods, it may also use some of its hidden units to model structure in the feature vectors that is not immediately relevant for predicting the labels."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}