QianQing's Blog

这篇博文记录计算方法中牛顿插值法及其Python实现，并且记录差商的相关知识。

上一篇博客介绍了有关概率图模型表示的基本内容，本篇博客介绍有关推断的内容。

推断的主要目的是求各种概率分布，包括边缘概率，条件概率，以及使用 MAP 来求得参数。本篇博客介绍三种算法

这篇博文记录计算方法中拉格朗日插值法的Python和matlab实现

本篇博客是关于在hexo中添加配置mermaid的记录

先总结了随机变量分布的一些规则，接着介绍了有向图/贝叶斯网络和无向图/马尔可夫随机场。

其实，分块是一种思想，而不是一种数据结构。

从 NOIP 到 NOI 到 IOI，各种难度的分块思想都有出现。

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。

分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。

当然，分块的缺点是渐进意义的复杂度，相较于线段树和树状数组不够好。

不过在大多数问题上，分块仍然是解决这些问题的一个不错选择。

本篇博客是几个例子。

我们需要先补充一些概率论知识。

指数族是一类分布，包括高斯分布、伯努利分布、二项分布、泊松分布、Beta 分布、Dirichlet 分布、Gamma 分布等一系列分布。指数族分布可以写为统一的形式： 其中， 是参数向量， 是对数配分函数（log partition function）（归一化因子），。

在这个式子中， 叫做充分统计量，包含样本集合所有的信息，例如高斯分布中的均值和方差。充分统计量在在线学习中有应用，对于一个数据集，只需要记录样本的充分统计量即可。

左偏树 与 配对堆 一样，是一种 可并堆，具有堆的性质，并且可以快速合并。

对于完全不可分的问题，我们采用特征转换的方式，在 SVM 中，我们引入正定核函数来直接对内积进行变换。

使用核方法的主要动机有两条：非线性带来高维转换、对偶带来内积计算。

支撑向量机（SVM）算法在分类问题中有着重要地位，其主要思想是最大化两类之间的间隔。本篇博客从Lagrange乘子法谈起，并引入、求解SVM的数学模型，并且简单介绍了核方法。

按照数据集的特点：

1. 线性可分问题，如之前的感知机算法处理的问题
2. 线性可分，只有一点点错误点，如感知机算法发展出来的 Pocket 算法处理的问题
3. 非线性问题，完全不可分，如在感知机问题发展出来的多层感知机和深度学习

这三种情况对于 SVM 分别有下面三种处理手段：

1. hard-margin SVM
2. soft-margin SVM
3. kernel Method