限制玻尔兹曼机学习笔记整理

return 0; } int MaxMatch() { int i,num; num=0; memset(link,0xff,sizeof(link)); for(i=1;i<=gn;i++) { memset(useif,0,sizeof(useif)); if(can(i)) num++; } return num; } 用尽量少的不相交简单路径覆盖有向无环图(DAG)的所有顶点，这就是 DAG 图的最 小路径覆盖问题。DAG 图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）
������������ = 其中
1 −������������ ������ ������ ������������
������������
1.2 贝叶斯定理
P(A|B,C)=P(B|A)*P(A)*P(C|A,B)/(P(B)*P(C|B)) P(A)是 A 的先验概率或边缘概率。之所以称为"先验"是因为它不考虑任何 B 方面的因素。 P(A|B)是已知 B 发生后 A 的条件概率，也由于得自 B 的取值而被称作 A 的后验概率。 P(B|A)是已知 A 发生后 B 的条件概率，也由于得自 A 的取值而被称作 B 的后验概率。 P(B)是 B 的先验概率或边缘概率，也作标准化常量（normalized constant）。
二分图的最小覆盖分为最小顶点覆盖和最小路径覆盖： ① 最小顶点覆盖是指最少的顶点数使得二分图 G 中的每条边都至少与其中一个点 相关联， ② 二分图的最小顶点覆盖数=二分图的最大匹配数； ②最小路径覆盖也称为最小边覆盖， 是指用尽量少的不相交简单路径覆盖二分图中 的所有顶点。 二分图的最小路径覆盖数=|V|-二分图的最大匹配数；
������������ ∑������ ������=1 ������������
≈ ������(������������ )，
������
那么我们可以通过这些样本来逼近这个均值 1 ∫ ℎ(������)������������ = ������������(������) [������(������)] ≈ ∑ ������(������������ ) ������ ������
������ ������
蒙特卡洛方法的核心是定义好分布之后如何从这个分布上采集样本？ 对于如何在任意分布下采集样本是马尔科夫链蒙特卡洛方法 （MCMC） 解决的问题， 其基本思想就是利用马尔科夫链来产生指定分布下的样本。
1.4.1 马尔科夫链
设������������ 表示随机变量 X 在离散时间 t 时刻的取值。若该变量随时间变化的转移概率仅 仅依赖于它的当前取值，即 P(������������+1 = ������������ |������0 = ������������0 , ������1 = ������������1 , … … , ������������ = ������������ ) = P(������������+1 = ������������ |������������ = ������������ ) 则称这个变量为马尔科夫变量，其中������������0 , ������������1 , … … , ������������ , ������������ ∈ ������ 为随机变量 X 可能的状态。这 个性质成为马尔可夫性质，具有马尔科夫性质的随机过程成为马尔可夫过程。 对于一个马尔科夫随机变量我们只需知道它的当前取值，就足以预测其未来的变化 趋势。而所谓的马尔科夫链就是指一段时间内随机变量 X 的取值序列(������0 , ������1, … … , ������������ )， 它们符合上式。 一般来说，一个马尔科夫链可通过其对应的转移概率来定义。所谓转移概率，是指 随机变量从一个时刻到下一个时刻，从状态������������ 转移到下一个状态������������ 的概率，即 P(������ → ������) ≔ ������������,������ = P(������������+1 = ������������ |������������ = ������������ ) 若记下������������ 表示随机变量 X 在时刻 t 取值������������ 的概率，则 X 在时刻 t+1 取值为������������ 的概率
������ ������
(������)
设状态的数目为 n，则根据上式有
如果存在某个取值， 从它出发转移回自身所需要的转移次数总是整数 d(>1)的倍数， 那么这个马尔可夫过程就是就有周期性。 如果两个取值之间总是能以非零的概率相互转 移， 那么该马尔科夫过程就成为不可约 （不可约指每一个状态都可来自任意的其他状态） 。 如果一个马尔可夫过程既没有周期性又不可约，则称它是各态遍历的。 对于各态遍历的马尔科夫过程，不论������ 0 取何值，随着转移次数的增多，随机变量的 取值分布最终都会收敛于唯一的平稳分布������ ∗ ，即
������
∫ ℎ(������)������������
������
如果我们无法通过数学推导直接求出解析解，那么为了避免对区间(a,b)上的所有 x 值进行枚举(多数情况下这也是不可能的)，我们可以将h(x)分解为某个函数������(������)和一个 定义在(a,b)上的概率密度函数������(������)的乘积。这样整个积分就可以写成
1.4.2 正则分布
假设一个物理系统具备一定的自由度，那么系统所处的状态就具有一定的随机性。 假设系统处于状态 i 的概率为������������ ，则显然有 ������������ ≥ 0, 且 ∑ ������������ = 1
������
根据系统的物理性质，不同的状态可能会使系统具备不同的能量。我们用������������ 表示系 统处于状态 i 时的能量。统计力学的一个基本结论是：当系统与外界达到热平衡时，系 统处于状态 i 的概率������������ 具有以下形式
1.3.5 最大独立集
最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来 说，最大独立集是一个 NP 完全问题，对于二分图来说 最大独立集=|V|-二分图的最大匹配数。
1.4 MCMC 方法
最早的蒙特卡洛方法旨在通过随机化的方法计算积分，假设给定函数h(x)，我们想 计算如下积分
限制玻尔兹曼机
1. 预备知识
受限玻尔兹曼机 （RBM） 是一种可用随机神经网络来解释的概率图模型。 所谓随机， 是指这种网络中的神经元是随机神经元，其输出只有两种状态（激活、未激活） ，一般 用二进制的 0 和 1 来表示，而状态的具体取值则根据概率统计法则来决定。
1.1 Sigmoid 函数
Sigmoid 函数是神经网络中常用的激活函数 1 S(x) = 1 + ������ −������ 其定义域为(-∞， + ∞),值域为(0,1)。
n→∞
lim ������ 0 ������������ = ������ ∗ ，
且这个平稳分布满足������ ∗ ������ ∗ ������ = ������ ∗ 这就意味着，无论������ 0 取何值，经过足够多转移后，随机变量个取值总会不断接近与该过 程的平稳分布。这就为 MCMC 建立了基础：如果我们想在某个分布下采样，只有模拟 以其为平稳分布的马尔可夫过程， 经过足够多次转移之后， 我们的样本分布就会充分接 近于该平稳分布。这意味着我们近似的采集到了目标分布下的样本。
1.3 二分图 1.3.1 定义
设 G=(V,E)是一个无向图。如顶点集 V 可分割为两个互不相交的子集，并且图中每 条边依附的两个顶点都分属两个不同的子集。则称图 G 为二分图。也就是说在二分图 中，顶点可以分为两个集合 X 和 Y，每一条边的两个顶点都分别位于 X 和 Y 集合中。
1.3.2 最大匹配
(������)
为 �����������
(������+1)
= P(������������+1 = ������������ ) = ∑ P(������������+1 = ������������ |������������ = ������������ ) ∗ P(������������ = ������������ ) = ∑ ������������,������ ∗ ������������
������ ������ ������ ������
∫ ℎ(������)������������ = ∫ ������(������)������(������)������������ = ������������(������) [������(������)] 这样一来原积分就等同于������(������)在������(������)这个分布上的均值。 这时如果我们从分布������(������) 上采集大量的样本点，这些样本点符合分布������(������)，即对∀i，有
在 G 的一个子图 M 中，M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为 最大匹配数.如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为
完全匹配，也称作完备匹配。如果在左右两边加上源汇点后，图 G 等价于一个网络流， 二分图最大匹配问题可以转为最大流的问题。 解决此问的匈牙利算法的本质就是寻找最 大流的增广路径。 基本模式如下： 初始时最大匹配为空 while 找得到增广路径 do 把增广路径加入到最大匹配中去 二分图中的增广路径的性质： (1)有奇数条边。 (2)起点在二分图的左半边，终点在右半边。 (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。 （其实二分图的性 质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。 ） (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。 (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。 (7)最后， 也是最重要的一条， 把增广路径上的所有第奇数条边加入到原匹配中去， 并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反） ， 则新的匹配数就比原匹配数增加了 1 个。 初始时最大匹配为空 for 二分图左半边的每个点 i do 从点 i 出发寻找增广路径。 如果找到， 则把它取反 （即增加了总了匹配数） 。 如果二分图的左半边一共有 n 个点， 那么最多找 n 条增广路径。 如果图中共有 m 条边， 那么每找一条增广路径（DFS 或 BFS）时最多把所有边遍历一遍，所花时间也就是 m。 所以总的时间大概就是 O（n * m） 。 #define N 202 int useif[N]; //记录 y 中节点是否使用 0 表示没有访问过，1 为访问过 int link[N]; //记录当前与 y 节点相连的 x 的节点 int mat[N][N]; //记录连接 x 和 y 的边，如果 i 和 j 之间有边则为 1，否则为 0 int gn,gm; //二分图中 x 和 y 中点的数目 int can(int t) { int i; for(i=1;i<=gm;i++) { if(useif[i]==0 && mat[t][i]) { useif[i]=1; if(link[i]==-1 || can(link[i])) { link[i]=t; return 1; } } }