免费表白网站制作,杭州网站程序开发公司,免费网络推广工具,中国网新重庆前言
译自:《Training Restricted Boltzmann Machines: An Introduction 》
马尔科夫链在RBM的训练中占据重要地位#xff0c;因为它提供了从复杂的概率分布(比如马尔科夫随机场MRF的吉布斯分布)中提取样本。这一部分主要就是对马尔科夫链做个基本的理论介绍#xff0c;将…前言
译自:《Training Restricted Boltzmann Machines: An Introduction 》
马尔科夫链在RBM的训练中占据重要地位因为它提供了从复杂的概率分布(比如马尔科夫随机场MRF的吉布斯分布)中提取样本。这一部分主要就是对马尔科夫链做个基本的理论介绍将要着重强调的是将吉布斯采样作为一种马尔科夫链蒙特卡洛方法去训练马尔科夫随机场以及训练RBM。
马尔科夫链
一个马尔科夫链是离散时间的随机过程系统的下一个状态仅仅依赖当前的所处状态与在它之前发生的事情无关。形式上一个马尔科夫链是一组随机变量X{X(k)|k∈N0}X=\{X^{(k)}|k\in N_0\}取值是一个有限集Ω\Omega而且对于∀k≥0\forall k\geq0以及∀j,i,i0,⋯,ik−1∈Ω\forall j,i,i_0,\cdots,i_{k-1}\in \Omega都有
p(k)ijPr(X(k1)j|X(k)i,X(k−1)ik−1,⋯,X(0)i0)Pr(X(k1)j|X(k)i)\begin{aligned}
p_{ij}^{(k)}如果对于所有k≥0k\geq 0的时间点p(k)ijp_{ij}^{(k)}都有相同的pijp_{ij}(转移概率不会随着时间而改变)这个链达到了稳态(homogeneous)矩阵P(pij)i,j∈ΩP=(p_{ij})_{i,j\in \Omega}称为稳态马尔科夫链的转移矩阵。如果初始分布μ(0)\mu^{(0)}(即X(0)X^{(0)}的概率分布)是由概率向量μ(0)(μ(0)(i))i∈Ω\mu^{(0)}=(\mu^{(0)}(i))_{i\in\Omega}给出的其中μ(0)(i)Pr(X(0)i)\mu^{(0)}(i)=Pr(X^{(0)}=i)那么X(k)X^{(k)}的分布μ(k)\mu^{(k)}是由μ(k)Tμ(0)TPk\mu^{(k)T}=\mu^{(0)T}P^k给出的。
对于πTπTP\pi^T=\pi^TP中的π\pi则称为稳态分布如果马尔科夫链在k时刻达到稳态分布μ(k)π\mu^{(k)}=\pi那么所有的后续状态都是相同分布也就是说对于所有的n∈Nn\in N都有μ(kn)π\mu^{(k+n)}=\pi。关于马尔科夫链的分布π\pi为稳态分布的一个充分不必要条件是对于转移概率pij,i,j∈Ωp_{ij},i,j\in\Omega中∀i,j∈Ω\forall i,j\in\Omega都有
π(i)pijπ(j)pji\pi(i)p_{ij}=\pi(j)p_{ji}这就称为细致平稳条件(detailed balanced condition)对于马尔科夫链存在唯一的一个稳态分布。这就是在有限状态空间Ω\Omega中马尔科夫链不可约的案例。不可约的意思就是任何一个状态都能通过其它状态的有限次转移得到公式表示就是∀i,j∈Ω∃k0\forall i,j\in\Omega\quad\exists k >0都有Pr(X(k)j|X(0)i)0Pr(X^{(k)}=j|X^{(0)}=i)>0
如果链上所有的状态都是无规律发生的就称为非周期性。公式表示就是对于∀i∈Ω\forall i\in \Omega集合k∈N0|Pr(X(k)i|X(0)i)0k\in N_0|Pr(X^{(k)}=i|X^{(0)}=i)>0的所有元素的最大公约数是1。在有限状态空间中的不可约非周期性的马尔科夫链能够保证收敛到一个稳态分布。假设有限状态空间中有两个分布α\alpha和β\beta变量距离可以被定义为
dV(α,β)12|α−β|12∑x∈Ω|α(x)−β(x)|d_V(\alpha,\beta)=\frac{1}{2}|\alpha-\beta|=\frac{1}{2}\sum_{x\in\Omega}|\alpha(x)-\beta(x)|为了方便标记我们让行和列的概率向量作为上式的函数自变量这样我们就有如下定理假设π\pi是有限状态空间中的不可约非周期的马尔科夫链的稳态分布转移概率矩阵为P\mathbf{P},对于任意的初始分布μ\mu都有 limk→∞dV(μTPk,πT)0
> \lim_{k\to\infty}d_V(\mu^TP^k,\pi^T)=0
> 马尔科夫链蒙特卡洛方法利用收敛定律通过建立一个收敛到期望分布的马尔科夫链然后从概率分布中生成样本。假设你想从具有有限状态空间的分布q中进行采样随后就应该建立一个不可约、非周期的马尔科夫链而且它的稳态分布πq\pi=q。这是一个非平凡问题(non-trivial task)。如果k足够大那么从马尔科夫链中重构X(k)X^{(k)}的状态x(k)x^{(k)},就会逼近与π\pi中的一个样本,也是qq中的。吉布斯采样就是这样一种马尔科夫链蒙特卡洛MCMC方法。吉布斯采样吉布斯采样是一种简单的MCMC方法，从多元随机变量的联合概率分布中产生样本。最基本的想法就是，依据条件分布更新每一个变量，而条件分布的条件就是给定除此变量以外的其它变量的状态，如此构造一个马尔科夫链。随后我们将描述，如何从一个马尔科夫随机场MRF的吉布斯分布中，利用吉布斯采样生成(近似)样本。我们假设一个马尔科夫随机场为X=(X1,⋯,XN)X=(X_1,\cdots,X_N)即一个无向图模型G(V,E)G=(V,E)其中V{1,⋯,N}V=\{1,\cdots,N\}是为了做更清楚的标记。随机变量Xi,i∈VX_i,i\in V在有限集Λ\Lambda中取值并且π(x)1Ze−ε(x)\pi(x)=\frac{1}{Z}e^{-\varepsilon (x)}是XX的联合概率分布。此外，如果我们假设马尔科夫随机场随着时间改变状态，就可以将X={X(k)|k∈N0}X=\{X^{(k)}|k\in N_0\}当做从ΩΛN\Omega=\Lambda^N中取值的马尔科夫链。那么X(k)(X(k)1,⋯,X(k)N)X^{(k)}=(X_1^{(k)},\cdots,X_N^{(k)})就描述了一个马尔科夫随机场在时刻k≥0k\geq0的状态。在接下来的两个后继时间节点中链上新状态的产生都需要经过以下步骤
从概率q(i)q(i)中随机挑选一个变量Xi,i∈VX_i,i\in V这里的概率q(i)q(i)是由V中的严格为正的概率分布qq给出的。
X(i)X^{(i)}的新状态就是给定其它所有变量(Xv)v∈V∖i(X_v)_{v\in V\backslash i}的状态(xv)v∖i(x_v)_{v\backslash i}然后基于其条件概率分布采样得到的。依据条件随机场的局部马尔卡夫特性有π(xi|(xv)v∈V∖i)π(xi|(xw)w∈ℵi)\pi(x_i|(x_v)_v\in V\backslash i)=\pi(x_i|(x_w)_{w\in\aleph_i} )。马尔科夫随机场的两个状态x,y,x≠yx,y,x\neq y的转移概率pxyp_{xy}是 pxy{q(i)π(yi|(xv)v∈V∖i),0,if ∃i∈Vso that ∀v∈Vwith v≠i:xvyv)elsep_{xy}=\begin{cases}\begin{aligned}q(i)\pi(y_i|(x_v)_{v\in V\backslash i}),\quad为了证明由这些转移概率定义的马尔科夫链(因而被称作吉布斯连)收敛到马尔科夫随机场的联合分布π\pi我们需要证明π\pi是吉布斯链的稳态分布而且这个链是不可约非周期的。
从细致平稳条件中很容易发现π\pi是稳态分布如果xx和yy在多个随机变量数值上有差异就遵循一个事实pxyPyx0p_{xy}=P_{yx}=0。假设xx和yy仅仅在一个确定的变量XiX_i上的状态不同比如当j≠ij\neq i的时候yjxjy_j=x_j且yi≠xiy_i\neq x_i ,那么
π(x)pxyπ(x)q(i)π(yi|(xv)v∈V∖i)π(xi,(xv)v∈V∖i)q(i)π(yi,(xv)v∈V∖i)π((xv)v∈V∖i)π(yi,(xv)v∈V∖i)q(i)π(xi,(xv)v∈V∖i)π((xv)v∈V∖i)π(y)q(i)π(xi|(xv)v∈V∖i)π(y)pyx\begin{aligned}
\pi(x)p_{xy}而且π\pi就是平稳分布。因为π\pi是严格为正的因而是单一变量的条件概率分布。这就意味着每个单一变量XiX_i在一个单一的转移步骤中可以取每一个状态xi∈Λx_i\in \Lambda而且整个马尔科夫随机场中的每个状态都能经过有限步骤转移到ΛN\Lambda^N的任何其它状态。因此马尔科夫链就是不可约的。此外对于所有的x∈ΛNx\in \Lambda^N因为它还服从正的条件分布pxx0p_{xx}>0所以这个马尔科夫链也是非周期的。不可约和非周期性就保证了链能够收敛到稳态分布π\pi
实际中单个随机变量不是基于分布qq随机选择更新的，而是有一个固定的预定义顺序。对应的算法经常依赖于周期吉布斯采样器periodic Gibbs sampler。如果P\mathbf{P}是吉布斯链的转移矩阵周期吉布斯采样器到马尔科夫随机场的稳态分布的收敛率其界限可以使用下列不等式定义
|μPk−π|≤12|μ−π|(1−e−NΔ)k|\mu P^k-\pi|\leq\frac{1}{2}|\mu-\pi|(1-e^{-N\Delta})^k其中Δsupl∈Vδl\Delta=\sup_{l\in V}\delta_l而且δlsup{|ε(x)−ε(y)|;xiyi ∀i∈V with i≠l}\delta_l=\sup\{|\varepsilon(x)-\varepsilon(y)|;x_i=y_i\ \forall i\in V \ with\ i\neq l\},其中μ\mu是任意的起始分布12|μ−π|\frac{1}{2}|\mu-\pi|是变量距离。这里有一个符号叫做sup\sup表示数理统计中的
格里文科(Gelivenko)定理吉布斯采样和梅特罗波利斯哈斯廷斯算法 吉布斯采样属于梅特罗波利斯哈斯廷斯采样算法的一个更广泛的类别。这一类中所有的MCMC算法都利用两个步骤生成马尔科夫链的转移
随机挑选一个候选状态称为提议分布proposal distribution候选状态根据一个接受概率acceptance probability转移到马尔科夫链上的一个新状态保证细致平稳条件
吉布斯采样的提议分布经常是翻转单个随机变量的当前状态建议状态的接受概率就是一个条件概率其条件就是给定的其它随机变量状态。
从易辛模型Ising Model中采样时采样的提议分布(翻转状态)结合了接受概率 min(1,π(x′)π(x))\min(1,\frac{\pi(x')}{\pi(x)})其中xx代表当前状态，x′x'代表马尔科夫链上的新状态。
