大师兄的贝叶斯网络学习笔记（四十七）：贝叶斯网络（二十一）
大师兄的贝叶斯网络学习笔记（四十九）：贝叶斯网络（二十三）
八、结构学习
5. 模型优化
5.3 爬山法
- 爬山法的目的是要找出评分最高的模型。
- 它从一个初始模型出发开始搜索，初始模型一般设为无边模型，在搜索的每一步。
- 在搜索的每一步，它首先用搜索算子(search operator)对当前模型(current model)进行局部修改，得到一系列候选模型(candidate model)；
- 然后计算每个候选模型的评分，并将最有候选模型与当前模型比较；
- 若最优候选模型的评分大，则以它为下一个当前模型，继续搜索；
- 否则，就停止搜索，并返回当前模型。
- 搜索算子有3个：加边(edge addition)、减边(edge deletion)和转边(edge reversal)。
- 加边即是在网络结构中添加一条边
- 减边是减去一条边
- 转边是把一条边的方向翻转。
- 加边和转边算子的使用有一个前提，即不能再网络中形成有向环。
- 爬山算法可以使用任何评分函数。
- 不同的评分函数有不同的要求：
- CH评分要求关于先验参数分布的超参数，
- 而HVL及CVL评分则要求吧数据分成训练数据和验证数据。
- 因此，需要处理的算法细节也有所不同。
- 下图是使用罚项似然度的爬山法:
- 计算罚项似然度需要计算参数的最大似然估计。
- 所以在图中把它视为模型G、模型参数θ以及数据D的函数。
- 爬山算法最费时的一步是计算候选模型G'的参数的最大似然估计θ'及其评分
。
- 由于G'与当前模型的差别不大，向量θ'与当前模型参数的最大似然估计θ相比，也只有几个维度需要更新。
- 实际上，我们可以从θ出发，利用搜索算子影响的维度重新计算，就可以得到θ'。
- 另外，一些常见的罚项似然度，比如BIC和AIC，都是可分解的，因此G'的评分可以从G的评分出发，通过简单计算获得。
- 爬山算法有一个众所周知的缺点，即它可能因为陷入局部最优(local optimal)或是与不过坪区(plateau)而找不到全局最优(global maximum)。
- 克服此缺点的一个方法是多次运行爬山法，每次都从一个随机产生的新结构开始，最后取各次运行中最优的哪个作为最后结果，这叫做随机重复爬山法(random restart hill-climbing)。
- 除此之外，也可以组合优化领域中的其它启发式搜索法，比如禁忌搜索(tabu search)、模拟退火(simulated annealing)、以及遗传算法(genetic algorithm)等。
