贝叶斯/05. 贝叶斯网.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在半朴素贝叶斯分类器中，我们对每一个属性的依赖做了约束，使其只依赖于另一个（ODE）或另几个属性（kDE），这使得属性之间的依赖关系呈树状或网状，不过这里的约束比较刻意，每个属性依赖的属性个数是相等的，在现实生活中，属性之间的依赖是没有规律的，更像是一个普通的网状结构。比如下图描述了心血管疾病和成因之间的关系，这被称为 **贝叶斯网**（Bayesian network）。\n",
    "\n",
    "<img src=\"../images/bayesian-network.png\" width=\"600px\" />\n",
    "\n",
    "贝叶斯网也叫做 **信念网**（belief network），它由网络结构 $G$ 和参数 $\\Theta$ 两部分组成，网络结构 $G$ 是一个有向无环图（directed acyclic graph，简称 DAG），其每一个节点对应一个属性，若两个属性有直接依赖关系，则用一条边连接起来；参数 $\\Theta$ 用于定量描述这种依赖关系，它包含了每个属性的 **条件概率表**（conditional probability table，简称 CPT）。\n",
    "\n",
    "### 贝叶斯网络结构\n",
    "\n",
    "下图是西瓜问题的一种贝叶斯网结构以及属性“根蒂”的条件概率表：\n",
    "\n",
    "<img src=\"../images/bayesian-network.jpg\" width=\"600px\" />\n",
    "\n",
    "贝叶斯网假设每个属性与它的非后裔属性独立，对于上图的联合概率可以定义为：\n",
    "\n",
    "$$\n",
    "P(x_1,x_2,x_3,x_4,x_5) = P(x_1)P(x_2)P(x_3|x_1)P(x_4|x_1,x_2)P(x_5|x_2)\n",
    "$$\n",
    "\n",
    "很显然，在贝叶斯网络中，存在下面三种典型的依赖关系：\n",
    "\n",
    "<img src=\"../images/bayesian-network-dependency.png\" width=\"700px\" />\n",
    "\n",
    "为了分析有向图中变量的条件独立性，通常使用 **有向分离**（D-separation） 将有向图转化为一个无向图，这个无向图称为 **道德图**（moral graph）。\n",
    "\n",
    "在知道了贝叶斯网络结构之后，下一步就是如何根据训练数据集构造出这样的贝叶斯网络？条件概率表如何计算？怎么根据贝叶斯网络来预测新的测试数据？\n",
    "\n",
    "### 贝叶斯网络结构的学习\n",
    "\n",
    "首先定义一个评分函数，用于评估贝叶斯网和训练数据的契合程度，然后基于这个评分函数来寻找结构最优的贝叶斯网，这被称为 **评分搜索**。评分函数通常基于信息论准则来设计，譬如将学习问题看作一个数据压缩任务，试图找到一个能以最短编码长度描述训练数据的模型，编码长度包括了**描述模型自身**所需的字节长度和使用该模型**描述数据**所需的节点长度，这就是 **最小描述长度**（Minimal Description Lenght，简称 MDL）准则。\n",
    "\n",
    "对给定的训练集 $D$，贝叶斯网 $B$ 的评分函数可写为：\n",
    "\n",
    "$$\n",
    "s(B|D) = f(\\theta)|B| - LL(B|D)\n",
    "$$\n",
    "\n",
    "其中，$|B|$ 是贝叶斯网的参数个数，$f(\\theta)$ 是描述每个参数 $\\theta$ 的字节数，$LL(B|D)$ 是贝叶斯网 $B$ 的对数似然：\n",
    "\n",
    "$$\n",
    "LL(B|D) = \\sum_{i=1}^m \\log P_B(x_i)\n",
    "$$\n",
    "\n",
    "可以看出，上式中第一项是计算编码贝叶斯网 $B$ 所需的字节数，第二项是计算 $B$ 所对应的概率分布 $P_B$ 需多少字节来描述。于是，学习任务就转化为一个优化任务，寻找一个贝叶斯网 $B$ 使评分函数 $s(B|D)$ 最小。\n",
    "\n",
    "不过从所有可能的网络结构空间搜索最优贝叶斯网结构是一个 NP 难问题，通常有两种常用的策略在有限时间内近似求解：\n",
    "\n",
    "* 贪心法：从某个网络结构出发，每次调整一条边（增加、删除、调整方向），直到评分函数值不再降低为止\n",
    "* 约束法：给网络结构施加约束来削减搜索空间，譬如之前学习的半朴素贝叶斯分类器 TAN 将结构限定为树形（半朴素贝叶斯分类器也是一种特殊的贝叶斯网）\n",
    "\n",
    "### 贝叶斯网络参数的学习\n",
    "\n",
    "若网络结构已知，即属性间的依赖关系已知，只需要对训练样本进行计数就可以估计出每个属性节点的条件概率表。\n",
    "\n",
    "### 根据贝叶斯网络进行推断\n",
    "\n",
    "贝叶斯网络训练好之后（结构和参数都已训练好），就可以通过一些属性的观测值来推测其他属性的值，比如观测到西瓜色泽青绿、敲声浊响、根蒂蜷缩，要判断它是否成熟、甜度如何。\n",
    "\n",
    "最理想的方法是根据贝叶斯网定义的联合概率分布来精确计算后验概率，不过这样的计算方法是 NP 难的，当网络节点较多、连接稠密时，难以精确推断，这时通过使用某种近似推断的方法，降低精度要求，在有限时间内求取近似解，在现实应用中，通常使用 **吉布斯采样**（Gibbs sampling）来完成。"
   ]
  }
 ],
 "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}