{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们回顾一下朴素贝叶斯分类器，它的表达式如下：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "y = f(x) &= \\mathop{\\arg\\max}_{c_k} P(Y=c_k|X=x) \\\\\n",
    "&= \\mathop{\\arg\\max}_{c_k} P(Y=c_k)P(X=x|Y=c_k) \\\\\n",
    "&= \\mathop{\\arg\\max}_{c_k} P(Y=c_k) \\prod_i P(X=x^{(i)}|Y=c_k)\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "可以看出在使用贝叶斯公式计算后验概率 $P(Y=c_k|X=x)$ 时，类条件概率 $P(X=x|Y=c_k)$ 很难计算，它是所有属性上的联合概率，难以从有限的训练样本直接估计出来。所以，朴素贝叶斯分类器采用了一个很简单的假设：属性条件独立性假设，也就是说所有的属性相互独立，这样类条件概率可以写成每个属性的条件概率的乘积。\n",
    "\n",
    "不过在现实任务中，这个独立性假设往往很难成立，于是便有了 **半朴素贝叶斯分类器**（semi-naive Bayes classifiers），它的基本思想是适当的考虑一部分属性间的相互依赖信息，既不需要计算完全联合概率，又不至于彻底忽略了比较强的属性依赖关系。\n",
    "\n",
    "**独依赖估计**（One-Dependent Estimator，简称 ODE）是半朴素贝叶斯分类器最常用的一种策略，它假设每个属性在类别之外最多仅依赖于一个其他属性：\n",
    "\n",
    "$$\n",
    "y = f(x) = \\mathop{\\arg\\max}_{c_k} P(Y=c_k) \\prod_i P(X=x^{(i)}|Y=c_k, X=pa^{(i)})\n",
    "$$\n",
    "\n",
    "其中 $pa^{(i)}$ 为属性 $x^{(i)}$ 所依赖的属性，称为 $x^{(i)}$ 的父属性，若父属性 $pa^{(i)}$ 已知，概率 $P(X=x^{(i)}|Y=c_k, X=pa^{(i)})$ 也就很容易计算，所以问题也就转化为如何确定每个属性的父属性。常见的方法有：\n",
    "\n",
    "* SPODE（Super-Parent ODE），它假设所有属性都依赖于同一个属性，称为超父（super-parent），然后通过交叉验证等模型选择方法来确定超父属性\n",
    "* AODE（Averaged ODE），它尝试将每个属性作为超父来构建 SPODE，然后将那些具有足够训练数据支撑的 SPODE 通过集成学习汇聚起来得到结果\n",
    "* TAN（Tree Augmented naive Bayes）通过计算任意两个属性之间的 **条件互信息**（conditional mutual information） 构建完全图，再根据 **最大带权生成树**（maximum weighted spanning tree） 算法保留强相关属性之间的依赖性\n",
    "\n",
    "将 **属性条件独立性假设** 放松为 **独依赖假设** 可能获得泛化性能的提升，那么将 **独依赖假设**（ODE）再放松到 **k依赖假设**（kDE），是否能进一步提升泛化性能呢？要注意的是，随着 k 的增加，准确估计概率 $P(X=x^{(i)}|Y=c_k, X=pa^{(i)})$ 所需的训练样本数量将以指数级增加，因此，如果训练数据非常充分，泛化性能有可能提升，但是在有限样本条件下，效果不一定好。"
   ]
  }
 ],
 "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
}