References：
【贝叶斯网络的学习】
在网络结构已知，即特征间的依赖关系已知的情况下，贝叶斯网络只需要对训练样本进行统计，估计出每个结点的条件概率表即可
但在实际应用中，往往不知道网络结构，因此贝叶斯网络学习的首要任务就是通过训练集来找出结构最为合适的贝叶斯网络
目前，最常用的方法是评分搜索（Score Search），该方法定义了一个评分函数（Score Function），通过该函数来寻找结构最优的贝叶斯网络
【最小描述长度准则】
目前常用的评分函数都是基于信息论准则的，其将学习问题视为一个数据压缩任务，试图找到一个可以用最短编码长度来描述训练数据的模型，此时，编码长度包括：模型自身所需的字节长度、使用该模型描述数据所需的字节长度
对于贝叶斯网络学习而言，每个贝叶斯网络即为一个模型，其描述了训练集在该模型上的概率分布，对于那些在训练集中经常出现的样本，存在一套编码机制，使得这些经常出现的样本有着更短的编码
由此，应该选择综合编码长度最短的模型，这就是最小描述长度（Minimal Description Length，MDL）准则
【评分函数最小化】
给定由 $P(X,Y)$ 独立同分布产生的训练数据集 $T=\{(\mathbf{x_1},y_1),(\mathbf{x_2},y_2),…,(\mathbf{x_N},y_N)\}$，对于每一样本对 $(\mathbf{x_i},y_i)$，输入 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathcal{X}$，输出 $y_i\in\mathcal{Y}$
那么，贝叶斯网络 $B= < G,\Theta >$ 在 $T$ 上的评分函数为：
其中，$|B|$ 为贝叶斯网络的参数个数，$f(\theta)$ 描述了每个参数 $\theta$ 所需的字节数，显然，$f(\theta)|B|$ 计算了编码整个贝叶斯网络 $B$ 所需要的字节数
而 $LL(B|T)$ 为贝叶斯网络的对数似然，其计算了贝叶斯网络 $B$ 对应的概率分布 $P_B$ 对训练集 $T$ 的描述程度，即：
可以发现，学习任务转为了优化任务，即寻找一个贝叶斯网络 $B$，使得评分函数 $s(B|T)$ 最小
若贝叶斯网络 $B = < G,\Theta >$ 的网络结构 $G$ 固定，那么评分函数 $s(B|T)$ 的第一项 $f(\theta)|B|$ 为常数，此时，最小化评分函数 $s(B|T)$ 等价于对参数 $\Theta$ 进行极大似然估计，即求：
而参数 $\Theta_{x^{(j)}|\pi^{(j)}}$ 可以直接在训练集 $T$ 上通过经验估计获得，即：
因此，为最小化评分函数 $s(B|T)$，只需要对所有可能的网络结构空间中进行搜索最优的贝叶斯网络结构，而网络的 $\Theta$ 参数可以直接在训练集上计算得到
但在所有可能的网络结构空间中搜索最优网络结构是一个 NP 难问题，难以快速求解，为此，常通过以下两种策略在有限时间内求得近似解：
- 贪心法：从某个网络结构出发，每次调整一条边，直到评分函数值不再降低
- 约束法：对网络结构施加约束条件来削减搜索空间（半朴素贝叶斯可视为贝叶斯网络的特例，其将网络结构限定为树形结构）
【AIC 与 BIC】
当每个参数用 $1$ 字节描述时，有 $f(\theta)=1$，此时得到的评分函数称为赤池信息准则（Akaike Information Criterion，AIC）评分函数，即：
当每个参数用 $\frac{1}{2}\log N$ 个字节描述时，有 $f(\theta)=\frac{1}{2}\log N$，此时得到的评分函数称为贝叶斯信息准则（Bayesian Informatica Criterion，BIC）评分函数，即：
当不对贝叶斯网络进行编码长度的计算时，有 $f(\theta)=0$，此时得到的评分函数退化为负对数似然函数，学习任务退化为极大似然估计，即：
