《计算智能》笔记

最优化算法

广度优先搜索

总是在某一深度上先搜索所有节点,之后搜索下一个深度的节点,能保证一定可以得到最优解,但需要生成大量节点,并且有可能导致组合爆炸,搜索效率低。

深度优先搜索

总是扩展深度大的节点,直到找到目标节点。在存储空间上渐进最优,但是对于一棵无穷树,可能永远找不到最优解。搜索效率从一定程度上取决于运气,总体来说不高。

启发式搜索

通过合适的启发函数f(n)=g(n)+h(n),h(n)尽量取下界最大值,可以通过生成比较少的节点求得最佳路径,搜索效率高。

alpha​-beta剪枝

优点:节约了机器开销,减少搜索范围,提高了搜索效率。

缺点:严重依赖于算法的寻找顺序。

模拟退火算法

优点:

  • 具有摆脱局部最优解的能力,能够找到目标函数的全局最小点,已被证明有渐进收敛性;
  • 简单、通用、易实现;
  • 具有并行性。

缺点:

  • 对参数(如初始温度)的依赖性较强;
  • 优化过程长,效率不高。

流程图:

蚁群算法

优点:

  • 在求解性能上,具有很强的鲁棒性和搜索较优解的能力;
  • 蚁群算法是一种基于种群的进化算法,具有并行性
  • 搜索过程采用分布式计算方式,大大提高了算法的计算能力和运行效率。
  • 蚁群算法很容易与多种启发式算法结合,以解决陷入局部最优的问题。

缺点:

  • 蚁群算法中初始信息素匮乏
  • 收敛速度慢、易陷入局部最优
  • 蚁群算法复杂度高,需要的搜索时间较长。

流程图:

遗传算法

优点:

  • 算法独立于求解域,具有快速随机的搜索能力;
  • 群体搜索算法,具有潜在的并行性,鲁棒性高;
  • 搜索使用评价函数启发,过程简单;
  • 适合于求解复杂的优化问题。

缺点:

  • 编程实现较复杂,需要对问题进行编码和解码;
  • 算法参数多,会影响解的品质,而目前参数的选择基本是依靠经验;
  • 容易产生早熟收敛的问题,易于陷入局部最优解;
  • 算法对初始种群的选择有一定的依赖性,能够结合一些启发算法进行改进。

流程图:

粒子群算法

优点:

  • 具有相当快的逼近最优解的速度;
  • 个体充分利用自身经验和群体经验调整自身的最优解;
  • 无集中约束控制,具有很强的鲁棒性。

缺点:

  • 数学基础薄弱,不能严格证明它在全局最优点上的收敛性;
  • 容易产生早熟收敛,陷入局部最优,主要归咎于种群在搜索空间中多样性的丢失;
  • 由于缺乏精密搜索方法的配合 ,最优往往得不到最优解。

流程图:

时序逻辑推理

滤波

$$
P(X_t|Y_{1:t})
$$

即根据现在及以前的所有测量数据,估计当前的状态。在雨伞那个例子中,根据目前为止过去进屋的人携带雨伞的所有观察数据,计算今天下雨的概率,这就是滤波。

预测

$$
P(X_{t+k}|Y_{1:t}), k> 0
$$

即根据现在及现在以前的所有测量数据,估计未来某个时刻的状态。在雨伞的例子中,根据目前为止过去进屋的人携带雨伞的所有观察数据,计算从今天开始若干天后下雨的概率,这就是预测。

平滑

$$
P(X_k|Y_{1:t}), 0 < k < t
$$

即根据现在及现在以前的所有测量数据,估计过去某个时刻的状态。在雨伞的例子中,意味着给定目前为止过去进屋的人携带雨伞的所有观察数据,计算过去某一天的下雨概率。

最可能解释

$$
arg \max_{x_{1:t}}P(X_{1:t}|Y_{1:t}))
$$

即给出现在及现在以前的所有测量数据,找到最能最可能生成这些测量数据的状态序列。例如,如果前三天每天都出现雨伞,但第四天没有出现,最有可能的解释就是前三天下雨了,而第四天没下雨。最可能解释也被称为解码问题,在语音识别、机器翻译等方面比较有用,最典型的方法是隐马尔可夫模型。

评估

$$
P(Y_{1:t}|X_{1:t}, \lambda)
$$

这里面的$\lambda$是指模型。这个公式意味着在该模型下,给定到目前为止的状态序列,计算输出特定观测序列的可能性。这其实是个评估问题,可以评估模型的好坏,概率越高,意味着模型越能反映观测序列与状态序列之间的联系,模型就越好。

学习

学习$\lambda $,也即状态转移概率和观测概率
$$
P(X_{t+1}|X_{t}), P(Y_t|X_t)
$$
学习的目的是根据历史数据得到合理的模型,一般是根据一个目标函数,对模型进行迭代更新,例如使(5)中要计算的值最大便可以作为一个目标。

前向递归算法

应用于滤波问题。

前向-后向算法

屏幕快照 2018-11-18 下午2.18.58

应用于平滑问题。

维特比算法

$$
m_{t+1} = P(e_{t+1}|X_{t+1})\max_{X_t}(P(X_{t+1}|X_t) m_{1:t})
$$

应用于最大可能解释问题。

精确推理

Noisy-OR模型

对于其中一个变量依赖于 k 个父节点的噪声逻辑关系,可以用 O(k)而不是 O(2k)个参数来描述其完全条件概率表。

变量消元算法

变量消元算法保存了中间计算的结果,避免了重复计算,大大提高了计算效率。

动态贝叶斯网络

近似推理(离散型)

离散型的近似推理,即在贝叶斯网络下的近似推理。

各种采样算法的一致性估计

直接采样

直接采样可用于计算联合概率分布。

算法流程为:

拒绝采样

拒绝采样可用于计算条件概率。先通过直接采样生成一定量的样本,然后拒绝掉与证据变量不一致的样本,再计算剩余样本中查询变量所占的比例。

算法流程为:

似然加权

Likelihood Weighting

回顾拒绝采样的算法过程,一个疑问就是为什么不在采样过程中就指定证据变量的值呢?这便是似然加权(重要性采样)所解决的问题。在似然加权采样过程中,如果变量位于证据变量的子节点,那么就在指定证据变量的值的概率下进行采样;如果变量是证据变量的父节点,由于在采样过程中无法实现知道证据变量的值,但是证据变量的值对父节点的概率分布是有影响的,因此我们在计算到证据节点时,需要将父节点采样的值对应的概率分布加入权重中。如果证据节点的条件概率高,说明父节点的取值是大概率的,反之则是小概率的。

算法流程为:

粒子滤波

动态贝叶斯网络和马尔可夫模型可以相互转移。当给定证据变量想要计算隐含变量的概率时,我们可以通过“无限”复制时间片到动态贝叶斯网络中,然后再采用维特比算法等精确推理的方法去计算条件概率。但是,当网络的状态变量非常多的时候,即使维特比算法等精确推理的方法可以达到“常数级”的计算效率,但计算效率依旧不尽人意。

在复杂的动态贝叶斯网络下,可以采用似然加权的方法来近似得到条件概率。在传统的似然加权采样中,每次只产生一个样本,最后通过统计符合证据的样本频率来近似得到概率。替代地,我们可以一次性处理N个样本,并将其前向传播处理。但是似然加权采样存在的明显问题就是如果证据变量处在下游,那么算法的精度就会受损,前面的状态变量的采样无法从后面的证据变量得到指导。因此随着N个样本向后传播,就会有不少样本逐渐与证据变量的相似性变低。一个明显的做法就是去除掉与证据变量相似性低的样本,使得保留下来的样本大部分都是与证据变量相似性高的样本。

以上的整个过程,就是所谓的粒子滤波算法在动态贝叶斯网络中的应用。完整算法流程为:

粒子滤波和维特比算法的计算复杂度对比

近似推理(连续型)

直接采样

直接采样的思想是,通过对均匀分布采样,实现对任意分布的采样。因为均匀分布采样好猜,我们想要的分布采样不好采,那就采取一定的策略通过简单采取求复杂采样。
假设y服从某项分布p(y),其累积分布函数CDF为h(y),有样本z~Uniform(0,1),我们令 z = h(y),即 y = h(z)^(-1),结果y即为对分布p(y)的采样。

314331-a158633099c6fd5c-2

直接采样的核心思想在与CDF以及逆变换的应用。在原分布p(y)中,如果某个区域[a, b]的分布较多,然后对应在CDF曲线中,[h(a), h(b)]的曲线斜率便较大。那么,经过逆变换之后,对y轴(z)进行均匀分布采样时,分布多的部分(占据y轴部分多)对应抽样得到的概率便更大,

局限性

实际中,所有采样的分布都较为复杂,CDF的求解和反函数的求解都不太可行。

拒绝采样

拒绝采样是由一个易于采样的分布出发,为一个难以直接采样的分布产生采样样本的通用算法。既然 p(x) 太复杂在程序中没法直接采样,那么便一个可抽样的分布 q(x) 比如高斯分布,然后按照一定的方法拒绝某些样本,达到接近 p(x) 分布的目的。

25225434-fd6db018b45d4152a09ea1de2b5304ad

计算步骤

设定一个方便抽样的函数 q(x),以及一个常量 k,使得 p(x) 总在 k*q(x) 的下方。(参考上图)

  • x 轴方向:从 q(x) 分布抽样得到 a;
  • y 轴方向:从均匀分布(0, k*q(a)) 中抽样得到 u;
  • 如果刚好落到灰色区域: u > p(a), 拒绝, 否则接受这次抽样;
  • 重复以上过程。

局限性

  • 拒绝了太多的样本!随着证据变量个数的增多,与证据e相一致的样本在所有样本中所占的比例呈指数级下降,所以对于复杂问题这种方法是完全不可用的。
  • 难以找到合适的k*q(a),接受概率可能会很低。

重要性采样

重要性采样(似然加权)主要是用于求一个复杂分布p(x)的均值,最后并没有得到样本。

重要性采样的思想是借助一个易于采样的简单分布q(x),对这个简单分布q(x)所得到的样本全部接受。但是以此得到的样本肯定不满足分布p(x),因此需要对每一个样本附加相应的重要性权重。在重要性采样中,以p(x0)/q(x0)的值作为每个样本的权重。这样,当样本和分布p(x)相近时,对应的权重大;与分布p(x)相差过多时,对应的权重小。这个方法采样得到的是带有重要性权重的服从q(z)分布的样本,这个权重乘以样本之后的结果其实就是服从p(z)分布的。

314331-0096a433b005eb92-2

通过上述公式,我们可以知道重要性采样可以用于近似复杂分布的均值。

吉布斯采样

假设有一个例子:E:吃饭、学习、打球;时间T:上午、下午、晚上;天气W:晴朗、刮风、下雨。样本(E,T,W)满足一定的概率分布。现要对其进行采样,如:打球+下午+晴朗。

问题是我们不知道p(E,T,W),或者说,不知道三件事的联合分布。当然,如果知道的话,就没有必要用吉布斯采样了。但是,我们知道三件事的条件分布。也就是说,p(E|T,W), p(T|E,W), p(W|E,T)。现在要做的就是通过这三个已知的条件分布,再用Gibbs sampling的方法,得到联合分布。
具体方法:首先随便初始化一个组合,i.e. 学习+晚上+刮风,然后依条件概率改变其中的一个变量。具体说,假设我们知道晚上+刮风,我们给E生成一个变量,比如,学习→吃饭。我们再依条件概率改下一个变量,根据学习+刮风,把晚上变成上午。类似地,把刮风变成刮风(当然可以变成相同的变量)。这样学习+晚上+刮风→吃饭+上午+刮风。同样的方法,得到一个序列,每个单元包含三个变量,也就是一个马尔可夫链。然后跳过初始的一定数量的单元(比如100个),然后隔一定的数量取一个单元(比如隔20个取1个)。这样sample到的单元,是逼近联合分布的。

25225719-116e5550e9fd448f894cddc6b6ab02b4

蓄水池采样

蓄水池抽样(Reservoir Sampling ),即能够在o(n)时间内对n个数据进行等概率随机抽取,例如:从1000个数据中等概率随机抽取出100个。另外,如果数据集合的量特别大或者还在增长(相当于未知数据集合总量),该算法依然可以等概率抽样。

算法步骤:

  • 先选取数据流中的前k个元素,保存在集合A中;
  • 从第j(k + 1 <= j <= n)个元素开始,每次先以概率p = k/j选择是否让第j个元素留下。若j被选中,则从A中随机选择一个元素并用该元素j替换它;否则直接淘汰该元素;
  • 重复步骤2直到结束,最后集合A中剩下的就是保证随机抽取的k个元素。

MCMC算法

随机采样和随机模拟:吉布斯采样Gibbs Sampling

MCMC算法学习总结

【重点】采样方法(二)MCMC相关算法介绍及代码实现

马氏链收敛定理

马氏链定理:如果一个非周期马氏链具有转移概率矩阵P,且它的任何两个状态是连通的,那么$\lim_{p\to\infty}P_{ij}^n$存在且与i无关,记$\lim_{p\to\infty}P_{ij}^n = \pi(j)$,我们有:

20180604161544272

其中$\pi = [\pi(1), \pi(2), … , \pi(j), …], \sum_{i=0}^{\infty}\pi_i = 1, \pi$称为马氏链的平稳分布。

所有的 MCMC(Markov Chain Monte Carlo) 方法都是以这个定理作为理论基础的。

说明:

  1. 该定理中马氏链的状态不要求有限,可以是有无穷多个的;
  2. 定理中的“非周期“这个概念不解释,因为我们遇到的绝大多数马氏链都是非周期的;

20180604161729263

细致平稳条件

012132441751392

012132476599223

针对一个新的分布,如何构造对应的转移矩阵?

对于一个分布$\pi(x)$,根据细致平稳条件,如果构造的转移矩阵P满足$\pi(i)P_{ij} = \pi(j)P_{ji}$,那么$\pi(x)$即为该马氏链的平稳分布,因此可以根据这个条件去构造转移矩阵。

通常情况下,初始的转移矩阵$P$一般不满足细致平稳条件,因此我们通过引入接受率构造出新的转移矩阵$P’$,使其和$\pi(x)$满足细致平稳条件。由此,我们便可以用任何转移概率矩阵(均匀分布、高斯分布)作为状态间的转移概率。

如果我们假设状态之间的转移概率是相同的,那么在算法实现时,接收率可以简单得用$\pi(j)/\pi(i)$表示。

Metropolis-Hastings采样

对于给定的概率分布p(x),我们希望能有便捷的方式生成它对应的样本。由于马氏链能收敛到平稳分布, 于是一个很的漂亮想法是:如果我们能构造一个转移矩阵为P的马氏链,使得该马氏链的平稳分布恰好是p(x), 那么我们从任何一个初始状态x0出发沿着马氏链转移, 得到一个转移序列 x0,x1,x2,⋯xn,xn+1⋯,, 如果马氏链在第n步已经收敛了,于是我们就得到了 π(x) 的样本xn,xn+1⋯。

在马尔科夫状态链中,每一个状态代表一个样本$x_n$,即所有变量的赋值情况。

通过分析MCMC源码,可以知道:假设状态间的转移概率相同,那么下一个样本的采样会依赖于上一个样本。假设上一个样本所对应的原始分布概率$\pi(x)$很小,那么下一个样本的接受率很大概率为1;反之如果上一个样本的原始分布概率$\pi(x)$很大,那么下一个样本会有挺大概率被拒绝。这样的机制保证了生成的样本服从分布$\pi(x)$。

从上述分析可以看出,假如初始状态的样本对应的分布概率很小,那么在算法刚开始运行时所产生的样本(即使是分布概率很小的样本)很大可能都会被接收,从而使得算法刚开始运行时采样的样本不满足原始分布$\pi(x)$。只要算法采样到分布概率大的样本(此时即为收敛!),那么之后所采样得到的样本就会基本服从原始分布。当然,从初始状态遍历到分布概率大的状态时需要运行一段时间,这段过程即为收敛的过程。MCMC算法在收敛之后,保证了在分布概率$\pi(x)$大的地方产生更多的样本,在分布概率$\pi(x)$小的地方产生较少的样本。

一个马尔可夫链需要经过多次的状态转移过程采用达到一个稳定状态,这时候采样才比较接近真实的分布。此过程称为burn in。一般可通过丢弃前面的N个采样结果来达到burn in。

疑问

  • MCMC的收敛是什么意思?这个过程中是什么参数会更新导致收敛?如何确定何时收敛?

    收敛过程没有参数会更新,收敛的思想类似于大数定理。应用MCMC算法采样时,初始的样本量少,服从的分布可能和复杂分布$\pi(x)$相差挺远,但随着状态转移数的增加(转移矩阵P的应用),根据上述定理的证明,最终的样本分布会逐渐服从复杂分布$\pi(x)$。

  • $\pi$是每个状态所对应的概率分布吗?如果是的话,初始选定一个状态后,这个$\pi$如何设定?或则在MCMC证明过程中,初始$\pi$的概率分布如何设置?

    在MCMC的证明过程中,$\pi$是每个状态所对应的概率分布。证明中所给定的初始$\pi$应该只是为了证明无论初始样本符合什么分布,在经过一定数量的转移之后,得到的样本会服从复杂分布$\pi (x)$,在实际代码实现中,不用对这个$\pi$进行设定。

神经网络

反向传播算法

1. 网络初始化:

初始化权重为(0,1)内的随机数,并给定α和$\eta$,α取(0.1,0.4),$\eta$取0.9左右。误差精度值$\varepsilon$。

2. 数据加载:

提供训练样本集${x_n, y_n}_{n-1}^{N}$。

3. 前向传播:

计算网络的实际输出以及各隐层单元的状态(即前向过程)。

上述的$I _ { \mathrm { p } ^ { i } } ^ { ( l ) }$即为本层的输入,$O _ { j } ^ { ( l - 1 ) }$为上一层的输出,L、S代表两层的神经元个数,其实L==S,f(x)为阈值函数。

4. 反向传播:

反向计算误差,由以下公式计算完成:

对于输出层,误差计算公式如下:

对于隐含层,误差计算公式如下:

即对于隐含层,其误差取决于上一层的误差值,K、M、J分别为第二层,第三层,第一层的神经元的个数,其实K=M=J.

5. 更新权重:

修改权重和阈值

6. 中止判断:

判断输出层误差是否满足$\varepsilon $的要求,若满足则则停止训练,否则转向(3),继续执行。

Hebb学习(无监督)

Hebb学习规则与“条件反射”机理一致,并且已经得到了神经细胞学说的证实。

巴甫洛夫的条件反射实验:每次给狗喂食前都先响铃,时间一长,狗就会将铃声和食物联系起来。以后如果响铃但是不给食物,狗也会流口水。
受该实验的启发,Hebb的理论认为在同一时间被激发的神经元间的联系会被强化。比如,铃声响时一个神经元被激发,在同一时间食物的出现会激发附近的另一个神经元,那么这两个神经元间的联系就会强化,从而记住这两个事物之间存在着联系。相反,如果两个神经元总是不能同步激发,那么它们间的联系将会越来越弱。
Hebb学习律可表示为:
$$
W_{ij}(t+1)=W_{ij}(t)+a⋅y_i⋅y_j
$$
其中$W_{ij}$表示神经元j到神经元i的连接权,$y_i$与$y_j$表示两个神经元的输出,a是表示学习速率的常数,如果$y_i$与$y_j$同时被激活,即$y_i$与$y_j$同时为正,那么$w_{ij}$将增大。如果$y_i$被激活,而$y_j$处于抑制状态,即$y_i$为正$y_j$为负,那么$w_{ij}$将变小。

Delta学习规则(有监督)

Delta学习规则是一种简单的有监督学习算法,该算法根据神经元的实际输出与期望输出差别来调整连接权,其数学表示如下:
$$
W_{ij}(t+1)=W_{ij}(t)+a⋅(d_i−y_i)x_j(t)
$$
其中$W_{ij}$表示神经元j到神经元i的连接权,$d_i$是神经元i的期望输出,$y_i$是神经元i的实际输出,$x_j$表示神经元j状态,若神经元j处于激活态则$x_j$为1,若处于抑制状态则$x_j$为0或-1(根据激活函数而定)。a是表示学习速度的常数。假设$x_i$为1,若$d_i$比$y_i$大,那么$W_{ij}$将增大,若$d_i$比$y_i$小,那么$W_{ij}$将变小。

Detla规则简单来讲就是:若神经元实际输出比期望输出大,则减少输入为正的连接的权重,增大所有输入为负的连接的权重。反之,则增大所有输入为正的连接权的权重,减少所有输入为负的连接权的权重。

支持向量机

基本问题:
$$
\begin{array} { c l } { \min _ { \gamma , w , b } } & { \frac { 1 } { 2 } | w | ^ { 2 } + C \sum _ { i = 1 } ^ { m } \xi _ { i } } \ { \text { s.t. } } & { y ^ { ( i ) } \left( w ^ { T } x ^ { ( i ) } + b \right) \geq 1 - \xi _ { i } , \quad i = 1 , \ldots , m } \ { } & { \xi _ { i } \geq 0 , \quad i = 1 , \ldots , m } \end{array}
$$
对偶问题:
$$
\begin{array} { c l } { \max _ { \alpha } } & { W ( \alpha ) = \sum _ { i = 1 } ^ { m } \alpha _ { i } - \frac { 1 } { 2 } \sum _ { i , j = 1 } ^ { m } y ^ { ( i ) } y ^ { ( j ) } \alpha _ { i } \alpha _ { j } \left\langle x ^ { ( i ) } , x ^ { ( j ) } \right\rangle } \ { \text { s.t. } } & { 0 \leq \alpha _ { i } \leq C , \quad i = 1 , \ldots , m } \ { } & { \sum _ { i = 1 } ^ { m } \alpha _ { i } y ^ { ( i ) } = 0 } \end{array}
$$

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×