贝叶斯决策论
贝叶斯决策论（bayesian decision theory）是在概率框架下实施决策的基本方法
- 在分类问题情况下，在所有相关概率都已知的理想情形下，贝叶斯决策考虑如何基于这些概率和误判损失来选择最优的类别标记
假设有N中可能的类别标记，即 $y={c_1,\dots,c_N}$ ， $\lambda_ij$ 是将一个真实标记为 $c_j$ 的样本误分类为 $c_i$ 所产生的损失。基于后验概率 $P(c_i\vert x)$ 可获得将样本 $x$ 分类为 $c_i$ 所产生的期望损失（expected loss），即在样本上的“条件风险”（conditional risk）
\[R(c_i\vert x)=\sum\limits_{i=1}^N\lambda_{ij}P(c_j\vert x)\]寻找一个判定准则 $h:X\mapsto Y$ 以最小化总体风险
\[R(h)=E_x[R(h(x)\vert X)]\]显然，对每个样本 $x$ ，若规则 $h$ 能够最小化条件风险 $R(h(x)\vert x)$ ，则总体风险 $R(h)$ 也将被最小化
于是，得到贝叶斯判定准则（bayes decision rule）：为最小化总体风险，只需在每个样本上选择那个能使条件风险 $R(c\vert x)$ 最小的类别标记，即
\[h^*(x)=\mathop{\arg\min}\limits_{c\in y}R(c\vert x)\]- 此时，被称为贝叶斯最优分类器（bayes optimal classification），与之对应的总体风险 $R(h^*)$ 称为贝叶斯风险（bayes risk）
- $1-R(h^*)$ 反映了分类器所能达到的最好性能，即通过机器学习所能产生的模型精度的理论上限
具体来说，如果目标是最小化分类错误率，则误判损失 $\lambda_{ij}$ 可以写为
\[\lambda_{ij}\left\{ \begin{aligned} & 0,\quad if\:i=j;\\ & 1,\quad otherwise; \end{aligned} \right.\]此时条件风险为
\[R(c\vert x)=1-P(c\vert x)\]于是，最小化分类错误率的贝叶最优分类器为
\[h^*(x)=\mathop{\arg\max}\limits_{c\in y}P(c\vert x)\]即对每个样本 $x$ ，选择能使得后验概率 $P(c\vert x)$ 最大的类别标记
不难看出，使用贝叶斯判定准则来最小化决策风险，首先要获得后验概率；但是在现实中难以直接获得后验概率，机器学习实现的是基于有限的训练样本尽可能准确地估计出后验概率。
主要的两种策略：
- 判别式模型（discriminaive models）
- 给定 $x$ ，通过直接建模 $P(c\vert x)$ ，来预测 $c$
- 决策树、BP神经网络、支持向量机
- 生成式模型（generative models）
- 先对联合概率分布 $P(x,c)$ 建模，由此得到 $P(c\vert x)$
- 生成式模型考虑
极大似然估计
估计类条件概率的常用策略：先假定其具有某种确定的概率分布形式，再基于训练样本对概率分布参数估计
记关于类别c的类条件概率为 $P(x\vert c)$
- 假设 $P(x\vert c)$ 具有服从某个概率分布，分布模型被参数 $\theta_c$ 唯一确定，我们的任务就是利用训练集D估计参数 $\theta_c$
概率模型的训练过程就是参数估计过程，统计学界的两个学派提供了不同的方案：
- 频率主义学派（frequentist）认为参数虽然位置，但存在客观值，因此可以通过优化似然函数等准则来确定参数值
- 贝叶斯学派（bayesian）认为参数是未观察到的随机变量，其本身也可以有分布，因此可假定参数服从一个先验分布，然后基于观测到的数据计算参数的后验分布
令 $D_c$ 表示训练集中第 $c$ 类样本的组合的集合，假设这些样本是独立的，则参数 $\theta_c$ 对于数据集 $D_c$ 的似然是
\[P(D_c\vert \theta_c)=\prod\limits_{x\in D_c}P(x\vert \theta_c)\]- 对 $\theta_c$ 进行极大似然估计，寻找能够最大化似然 $P(D_c\vert \theta_c)$ 的参数值 $\hat{\theta_c}$
为了减少连乘操作造成的下溢，使用对数似然（log-likelihood）
\[LL(\theta_c)=\log P(D_c\vert \theta_c)=\sum\limits_{x\in D_c} \log P(x\vert \theta_c)\]此时参数 $\theta_c$ 的极大似然估计 $\hat{\theta_c}$ 为 $\hat{\theta_c}=\mathop{\arg\max}\limits_{\theta_c}LL(\theta_c)$
这种参数化的方法使得类条件概率估计变得相对见到那，但是估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布
省流：极大似然估计用于求样本假设分布的模型参数，基于频率主义学派，但这个分布可能不是真正的分布
朴素贝叶斯分类器
估计后验概率 $P(c\vert x)$ 主要困难：类条件概率 $P(x\vert c)$ 是所有属性上的联合概率，难以从有限的训练样本估计获得。
朴素贝叶斯分类器（naive bayes classification）采用“属性条件独立性假设”（attribute conditional independence assumption）：每个属性独立地对分类结果发生影响
\[P(c\vert x)=\frac{P(c)P(x\vert c)}{P(x)} =\frac{P(c)}{P(x)}\prod\limits_{i=1}^d P(x_i\vert c)\]对所有类别来说 $P(x)$ 相同，所以贝叶斯判定准则为
\[h_{nb}(x)=\mathop{\arg\max}\limits_{c\in y}P(c)\prod\limits_{i=1}^d P(x_i\vert c)\]令 $D_c$ 表示训练集 $D$ 中第 $c$ 类样本组合的集合，若有充足的独立同分布，则可以估计出类先验概率
\[P(c)=\frac{\vert D_c\vert}{D}\]对离散属性而言，令 $D_{c,x_i}$ 表示 $D_c$ 在第 $i$ 个属性上取值为 $x_i$ 的样本组成的集合，则条件概率 $P(x_i\vert c)$ 可估计为
\[P(x_i\vert c)=\frac{\vert D_{c,x_i}\vert}{D_c}\]对连续属性而言可考虑概率密度函数，假定 $P(x_i\vert c)\sim N(\mu,\sigma_{c,i}^2)$ ，则有
\[P(x_i\vert c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}} exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2})\]省流：朴素贝叶斯公式用先验概率和似然估计计算后验概率
拉普拉斯修正
若某个属性值在训练集中没有与某个类同时出现过，则直接计算会出现问题；例如“敲声==清脆“测试样例，训练集中没有出现该样例，因此连乘式计算的概率值为零，不合理。
为了避免其他属性携带信息被训练集中未出现的属性值”抹去“，在估计概率值时通常进行”拉普拉斯修正“（laplacian correction）
- 令 $N$ 表示训练集D中可能的类别数， $N_i$ 表示第i个属性可能的取值数，则式子修正为
现实任务中，朴素贝叶斯分类器的使用技巧：
- 速度要求高，”查表“
- 任务数据更替频繁，”懒惰学习“（lazy learning）
- 数据不断增加，增量学习
半朴素贝叶斯分类器
为了降低贝叶斯公式估计后验概率的困难，朴素贝叶斯分类器采用的属性条件独立性假设；对属性条件独立假设一定程度的放松，产生了一类称为”半朴素贝叶斯分类器“（semi-naive bayes classification）
半朴素贝叶斯分类器最常用的一种策略：”独依赖估计“（one-dependent estimator），假设每个属性在类别之外中最多仅依赖一个其他属性，即
\[P(c\vert x)\propto P(c)\prod\limits_{i=1}^dP(x_i\vert c,pa_i)\]其中 $pa_i$ 为属性 $x_i$ 所依赖的属性，即它的父属性
SPODE
最直接的做法是假设所有属性都依赖于同一属性，称为”超父“（super parent），然后通过交叉验证模型来确定超父属性
TAN
TAN（tree augmented naive bayes）在最大权生成算法的基础上改进
计算任意两个属性之间的条件互信息（conditional mutual information）
\[I(x_i,x_j\vert y)=\sum\limits_{x_i,x_j;c\in y} P(x_i,y_j\vert c)\log\frac{P(x_i,y_j\vert c)}{P(x_i\vert c)P(y_j\vert c)}\]- 以属性为节点构建完全图，任意两个节点连边的权重设为条件互信息
- 构建此完全图的最大带权生成树，挑选根变量，将边设为有向
- 加入类别节点y，增加y到每个属性的有向边
AODE
AODE（averaged one-dependent estimator）是基于集成学习机制、更强大的分类器
- 尝试将每个属性作为超父构建SPODE
- 将具有足够训练数据支撑的SPODE集群起来作为最终结果
贝叶斯网
贝叶斯网（bayesian network）也称为”信念网“（brief network），它借助有向无环图（DAG）来刻画属性间的依赖关系，并使用条件概率表（conditional probability table）来表述属性的联合概率分布
贝叶斯网有效表达了属性间的条件独立性
$B=\langle G,\Theta\rangle$ 将属性的联合概率分布定义为
\[P_B(x_1,\dots,x_d)=\prod\limits_{i=1}^dP_B(x_i\vert \pi_i)=\prod\limits_{i=1}^d\theta_{x_i\vert \pi_i}\]
贝叶斯网：学习
贝叶斯网络的首要任务：根据训练集找出结构最恰当的贝叶斯网
使用评分函数评估贝叶斯网和训练数据的契合程度
- “最小描述长度”（minimal description length，MDL）综合编码长度（包括描述网路和编码数据）最短
给定训练集 $D={x_1,\dots,x_m}$ ，贝叶斯网 $B=\langle G,\Theta\rangle$ 在D上的评价函数写为
\[S(B\vert D)=f(\theta)\vert B\vert-LL(B\vert D)\]$\vert B\vert$ ：贝叶斯网的参数个数
$f(\theta)$ ：描述参数 $\theta$ 需要的字节数
$LL(B\vert D)=\sum\limits_{i=1}^m\log P_B(x_i)$ ：贝叶斯网的对数似然
贝叶斯网：推断
通过已知的变量观测值来推测查询变量的过程称为“推断”（inference），一直变量观测值称为“证据”（evidence）
最理想的是根据贝叶斯网络的联合概率分布精确计算后验概率；在实际应用中，贝叶斯网的近似推断通常使用吉布斯采样（Gibbs sampling）来实现。
吉布斯采样随机产生一个与证据 $E=e$ 一致的样本 $q_0$ 作为初始点，然后每步从当前样本触出发产生下一个样本，假定T次采样的得到与q一致的样本有 $n_q$ 个，可以近似估算后验概率
\[P(Q=q\vert E=e)\simeq \frac{n_q}{T}\]吉布斯采样可以看作，每一步依赖前一步的状态，是一个“马尔科夫链”（markov chain）
EM算法
未观测到的变量称为“隐变量”（latent variable），令X表示已观测变量集，Z表示隐变量集，若分类模型参数 $\Theta$ 做极大似然估计，则应该最大化对数似然函数
\[LL(\Theta\vert X,Z)=\ln P(X,Z\vert\Theta)\]由于Z是隐变量，无法直接求解，可以通过对Z计算期望，来最大化已观测数据的对数“边际似然”（marginal likelihood）
\[LL(\Theta\vert X,Z)=\ln \sum\limits_Z P(X,Z\vert\Theta)\]EM（expectation-maximization）算法常用来估计参数隐变量
- 当参数 $\Theta$ 已知：根据训练数据集推断出最优隐变量 $Z$ （E步）
- 当隐变量 $Z$ 已知：对 $\Theta$ 做极大似然估计（M步）
于是，以初始值 $\Theta_0$ 为起点，迭代执行下面步骤直至收敛
- 基于 $\Theta_t$ 推断隐变量 $Z$ 的期望，记为 $Z^t$
- 基于已观测到的变量 $X$ 和 $Z^t$ 对参数 $\Theta$ 极大似然估计，记为 $\Theta^{t+1}$
E步：核心公式
\[\begin{aligned} Q(\theta,\theta^{(i)}) &=E_{Z}[\log P(Y,Z\vert \theta)\vert Y,\theta^{(i)}]\\ &=\sum\limits_{Z}\log P(Y,Z\vert\theta)P(Z\vert Y,\theta^{(i)}) \end{aligned}\]完全数据的对数似然函数 $\log P(Y,Z\vert\theta)$ 在给定观测数据 Y 和当前模型参数 $\theta^{(i)}$ 下对未观测隐变量 Z 的条件概率分布 $P(Z\vert Y,\theta^{(i)})$ 的期望称为Q函数
E步求Q函数，Q函数是在为M步的极大似然估计做数学公式解析准备的。每轮迭代实际上是在求Q函数极大，即不断调整隐变量极大似然。可见当隐变量越接近真实值，模型的极大似然才越接近真实值。
M步：对Q函数极大化
\[\theta^{(i+1)}=\mathop{\arg\max}\limits_{\theta}Q(\theta,\theta^{(i)})\]收敛条件： $\Vert\theta^{(i+1)}-\theta^{(i)}\Vert <\varepsilon$ 或 $\Vert Q(\theta^{(i+1)})-Q(\theta^{(i)})\Vert <\varepsilon$
省流：EM算法每轮迭代，Expectation步通过 Y 和上一步的 $\theta^{(i)}$ 更新隐变量 Z ，Maximization步通过 Y 和 Z 极大似然函数更新 $\theta^{(i+1)}$
数学基础
- 独立同分布 independent and identically distributed
- 如何理解先验概率与后验概率
- 机器学习项目中不可忽视的一个密辛 - 大数定理、中心极限定理
- (基础系列)1：先验概率 & 后验概率
- 一文搞懂极大似然估计
- 贝叶斯网络，看完这篇我终于理解了(附代码)！
- 详解十大经典机器学习算法——EM算法
- EM算法(Expectation Maximization Algorithm)初探