{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "****************\n", "Graphical Models\n", "****************\n", "\n", "Figure 10.13 is a nice illustration of :doc:`contrastive divergence `." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.1\n", "=============\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator{\\MarkovBlanket}{MB}\n", " (x_1)\\\\\n", " (x_3)\\\\\n", " (x_7)\\\\\n", " (x_1) \\rightarrow (x_2)\\\\\n", " (x_3) \\rightarrow (x_2)\\\\\n", " (x_7) \\rightarrow (x_5)\\\\\n", " (x_2) \\rightarrow (x_5)\\\\\n", " (x_2) \\rightarrow (x_4)\\\\\n", " (x_5) \\rightarrow (x_6)\\\\\n", " (x_4) \\rightarrow (x_6)\n", "\n", "The Markov blanket for :math:`x_2` is\n", ":math:`\\MarkovBlanket(x_2) = \\{ x_1, x_3, x_5, x_4, x_7 \\}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.2\n", "=============\n", "\n", ".. math::\n", "\n", " \\begin{multline}\n", " Pr(x_1, \\ldots, x_{15}) =\n", " Pr(x_1) Pr(x_2) Pr(x_3) Pr(x_4 \\mid x_1, x_2) Pr(x_5 \\mid x_2, x_3)\n", " Pr(x_6) Pr(x_7) Pr(x_8 \\mid x_4, x_5) Pr(x_9 \\mid x_3, x_5, x_6)\\\\\n", " Pr(x_{10} \\mid x_7) Pr(x_{11} \\mid x_8, x_{10}) Pr(x_{12} \\mid x_8, x_9)\n", " Pr(x_{13} \\mid x_9) Pr(x_{14} \\mid x_{11}) Pr(x_{15} \\mid x_{12})\n", " \\end{multline}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.3\n", "=============\n", "\n", ".. math::\n", "\n", " (x_1) \\leftrightarrow (x_2) \\leftrightarrow (x_5)\\\\\n", " (x_2) \\leftrightarrow (x_3) \\leftrightarrow (x_4)\\\\\n", " (x_1) \\leftrightarrow (x_5)\\\\\n", " (x_5) \\leftrightarrow (x_6)" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.4\n", "=============\n", "\n", ".. math::\n", "\n", " \\mathcal{S}_1 &= \\{ x_1, x_4 \\}\\\\\n", " \\mathcal{S}_2 &= \\{ x_2, x_4, x_8 \\}\\\\\n", " \\mathcal{S}_3 &= \\{ x_2, x_5, x_8 \\}\\\\\n", " \\mathcal{S}_4 &= \\{ x_3 \\}\\\\\n", " \\mathcal{S}_5 &= \\{ x_6, x_9 \\}\\\\\n", " \\mathcal{S}_6 &= \\{ x_7, x_{10} \\}\\\\\n", " \\mathcal{S}_7 &= \\{ x_7, x_{11} \\}\\\\\n", " \\mathcal{S}_8 &= \\{ x_8, x_{11} \\}\\\\\n", " \\mathcal{S}_9 &= \\{ x_8, x_{12} \\}\\\\\n", " \\mathcal{S}_{10} &= \\{ x_9, x_{12}, x_{13}, x_{15} \\}\\\\\n", " \\mathcal{S}_{11} &= \\{ x_{11}, x_{14} \\}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.5\n", "=============" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from itertools import product\n", "\n", "def phi(i, j):\n", " _ = {};\n", " _[(0, 0)] = 1.0\n", " _[(0, 1)] = 0.1\n", " _[(1, 0)] = 0.1\n", " _[(1, 1)] = 2.0\n", " return _[(i, j)]\n", "\n", "Z = 0.0\n", "P = {}\n", "for x_1, x_2, x_3, x_4 in product([0, 1], [0, 1], [0, 1], [0, 1]):\n", " PI = phi(x_1, x_2) * phi(x_2, x_3) * phi(x_3, x_4) * phi(x_4, x_1)\n", " P[(x_1, x_2, x_3, x_4)] = PI\n", " Z += PI\n", "\n", "_ = 'Pr(x_1 = {}, x_2 = {}, x_3 = {}, x_4 = {}) = {:.5f}'\n", "for k, v in P.items():\n", " print(_.format(*k, v / Z))" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.6\n", "=============\n", "\n", "Figure 10.7a\n", "------------\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(x_1) &= \\{ x_3 \\}\\\\\n", " \\MarkovBlanket(x_2) &= \\{ x_3 \\}\\\\\n", " \\MarkovBlanket(x_3) &= \\{ x_1, x_2 \\}\n", "\n", "Figure 10.7b\n", "------------\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(x_1) &= \\{ x_3 \\}\\\\\n", " \\MarkovBlanket(x_2) &= \\{ x_3 \\}\\\\\n", " \\MarkovBlanket(x_3) &= \\{ x_1, x_2 \\}\n", "\n", "Figure 10.7c\n", "------------\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(x_1) &= \\{ x_3, x_2 \\}\\\\\n", " \\MarkovBlanket(x_2) &= \\{ x_3, x_1 \\}\\\\\n", " \\MarkovBlanket(x_3) &= \\{ x_1, x_2 \\}\n", "\n", "Figure 10.8a\n", "------------\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(x_1) &= \\{ x_2, x_3 \\}\\\\\n", " \\MarkovBlanket(x_2) &= \\{ x_1, x_4 \\}\\\\\n", " \\MarkovBlanket(x_3) &= \\{ x_1, x_4 \\}\\\\\n", " \\MarkovBlanket(x_4) &= \\{ x_2, x_3 \\}\n", "\n", "Figure 10.8b\n", "------------\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(x_1) &= \\{ x_2, x_3 \\}\\\\\n", " \\MarkovBlanket(x_2) &= \\{ x_1, x_4, x_3 \\}\\\\\n", " \\MarkovBlanket(x_3) &= \\{ x_1, x_4, x_2 \\}\\\\\n", " \\MarkovBlanket(x_4) &= \\{ x_2, x_3 \\}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.7\n", "=============\n", "\n", "Figure 10.7a\n", "------------\n", "\n", ".. math::\n", "\n", " Pr(x_2 \\mid x_1, x_3)\n", " &= \\frac{Pr(x_1, x_2, x_3)}{\\int Pr(x_2, x_1, x_3) dx_2}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " Pr(x_1) Pr(x_3 \\mid x_1) Pr(x_2 \\mid x_3)\n", " }{\n", " \\int Pr(x_1) Pr(x_3 \\mid x_1) Pr(x_2 \\mid x_3) dx_2\n", " }\n", " & \\quad & \\text{factorization of graphical model}\\\\\n", " &= Pr(x_2 \\mid x_3)\n", "\n", "Figure 10.7b\n", "------------\n", "\n", ".. math::\n", "\n", " Pr(x_2 \\mid x_1, x_3)\n", " &= \\frac{Pr(x_1, x_2, x_3)}{\\int Pr(x_2, x_1, x_3) dx_2}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " Z^{-1} \\phi_1[x_1, x_3] \\phi_2[x_2, x_3]\n", " }{\n", " \\int Z^{-1} \\phi_1[x_1, x_3] \\phi_2[x_2, x_3] dx_2\n", " }\n", " & \\quad & \\text{factorization of graphical model}\\\\\n", " &= \\frac{\\phi_2[x_2, x_3]}{\\int \\phi_2[x_2, x_3] dx_2}\n", "\n", "Figure 10.7c\n", "------------\n", "\n", ".. math::\n", "\n", " Pr(x_2 \\mid x_1)\n", " &= \\frac{Pr(x_1, x_2)}{\\int Pr(x_2, x_1) dx_2}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " Pr(x_1) Pr(x_2)\n", " }{\n", " \\int Pr(x_1) Pr(x_2) dx_2\n", " }\n", " & \\quad & \\text{factorization of graphical model}\\\\\n", " &= Pr(x_2)\n", "\n", "Figure 10.8a\n", "------------\n", "\n", "The factorization of this undirected graphical model is\n", "\n", ".. math::\n", "\n", " Pr(x_1, x_2, x_3, x_4) =\n", " \\frac{1}{Z} \\phi_1[x_1, x_2] \\phi_2[x_1, x_3]\n", " \\phi_3[x_2, x_4] \\phi_4[x_3, x_4]\n", "\n", "where\n", "\n", ".. math::\n", "\n", " Pr(x_1 \\mid x_2, x_3, x_4)\n", " &= \\frac{Pr(x_1, x_2, x_3, x_4)}{\\int Pr(x_1, x_2, x_3, x_4) dx_1}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " \\phi_1[x_1, x_2] \\phi_2[x_1, x_3]\n", " }{\n", " \\int \\phi_1[x_1, x_2] \\phi_2[x_1, x_3] dx_1\n", " }\n", "\n", "and\n", "\n", ".. math::\n", "\n", " Pr(x_2 \\mid x_1, x_3, x_4)\n", " &= \\frac{Pr(x_1, x_2, x_3, x_4)}{\\int Pr(x_2, x_1, x_3, x_4) dx_2}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " \\phi_1[x_1, x_2] \\phi_3[x_2, x_4]\n", " }{\n", " \\int \\phi_1[x_1, x_2] \\phi_3[x_2, x_4] dx_2\n", " }.\n", "\n", "Figure 10.8b\n", "------------\n", "\n", "The factorization of this directed graphical model is\n", "\n", ".. math::\n", "\n", " Pr(x_1, x_2, x_3, x_4) =\n", " Pr(x_1) Pr(x_2 \\mid x_1) Pr(x_3 \\mid x_1) Pr(x_4 \\mid x_2, x_3)\n", "\n", "where\n", "\n", ".. math::\n", "\n", " Pr(x_1, x_2, x_3)\n", " &= \\int Pr(x_1, x_2, x_3, x_4) dx_4\\\\\n", " &= \\int Pr(x_1) Pr(x_2 \\mid x_1)\n", " Pr(x_3 \\mid x_1) Pr(x_4 \\mid x_2, x_3) dx_4\\\\\n", " &= Pr(x_1) Pr(x_2 \\mid x_1) Pr(x_3 \\mid x_1),\n", "\n", ".. math::\n", "\n", " Pr(x_1 \\mid x_2, x_3, x_4)\n", " &= \\frac{Pr(x_1, x_2, x_3, x_4)}{\\int Pr(x_1, x_2, x_3, x_4) dx_1}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{\n", " Pr(x_1) Pr(x_2 \\mid x_1) Pr(x_3 \\mid x_1)\n", " }{\n", " \\int Pr(x_1) Pr(x_2 \\mid x_1) Pr(x_3 \\mid x_1) dx_1\n", " }\\\\\n", " &= \\frac{\n", " Pr(x_1, x_2, x_3)\n", " }{\n", " Pr(x_2, x_3)\n", " }\\\\\n", " &= Pr(x_1 \\mid x_2, x_3),\n", "\n", "and\n", "\n", ".. math::\n", "\n", " Pr(x_2 \\mid x_1, x_3)\n", " &= \\frac{Pr(x_1, x_2, x_3)}{\\int Pr(x_2, x_1, x_3) dx_2}\n", " & \\quad & \\text{Bayes' rule}\\\\\n", " &= \\frac{Pr(x_2 \\mid x_1)}{\\int Pr(x_2 \\mid x_1) dx_2}\\\\\n", " &= Pr(x_2 \\mid x_1)." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.8\n", "=============\n", "\n", "Figure 10.7a\n", "------------\n", "\n", ".. math::\n", "\n", " (x_1) -[A]- (x_3)\\\\\n", " (x_2) -[B]- (x_3)\n", "\n", "Figure 10.7b\n", "------------\n", "\n", ".. math::\n", "\n", " (x_1) -[A]- (x_3)\\\\\n", " (x_2) -[B]- (x_3)\n", "\n", "Figure 10.7c\n", "------------\n", "\n", ".. math::\n", "\n", " (x_1) -[A]-\\\\\n", " (x_2) -[A]-\\\\\n", " (x_3) -[A]-\n", "\n", "Figure 10.8a\n", "------------\n", "\n", ".. math::\n", "\n", " (x_1) -[A]- (x_2)\\\\\n", " (x_1) -[B]- (x_3)\\\\\n", " (x_2) -[C]- (x_4)\\\\\n", " (x_3) -[D]- (x_4)\n", "\n", "Figure 10.8b\n", "------------\n", "\n", ".. math::\n", "\n", " (x_1) -[A]- (x_2)\\\\\n", " (x_1) -[B]- (x_3)\\\\\n", " (x_2) -[C]-\\\\\n", " (x_3) -[C]-\\\\\n", " (x_4) -[C]-" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.9\n", "=============\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(w_2) = \\{ w_1, w_5, w_4 \\}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 10.10\n", "==============\n", "\n", ".. math::\n", "\n", " \\MarkovBlanket(w_8) = \\{ w_5, w_7, w_9, w_{11} \\}" ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python [default]", "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.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }