机器学习笔记之配分函数——对数似然梯度

• 引言
• • 回顾：过去介绍配分函数的相关结点
  • 配分函数介绍
  • • 配分函数在哪些情况下会“直面”到？
    • 场景构建
  • 包含配分函数的极大似然估计

引言

从本节开始，将介绍配分函数。[花书第三部分——第18章直面配分函数(Confronting Partition Function)]

回顾：过去介绍配分函数的相关结点

• 最早介绍配分函数(Partition Function)在指数族分布中。关于指数族分布的概率密度函数 表示如下：
  其中X\mathcal XX表示随机变量集合;η\etaη表示模型参数。
  P(X∣η)=h(X)exp⁡[ηTϕ(X)−A(η)]=h(X)exp⁡[A(η)]exp⁡[ηTϕ(X)]\begin{aligned} \mathcal P(\mathcal X \mid \eta) & = h(\mathcal X) \exp \left[\eta^T \phi(\mathcal X) - \mathcal A(\eta)\right] \\ & = \frac{h(\mathcal X)}{\exp[\mathcal A(\eta)]} \exp \left[\eta^T \phi(\mathcal X)\right] \end{aligned}P(X∣η)​=h(X)exp[ηTϕ(X)−A(η)]=exp[A(η)]h(X)​exp[ηTϕ(X)]​
  令Z=exp⁡[A(η)]\mathcal Z = \exp \left[\mathcal A(\eta)\right]Z=exp[A(η)]，称Z\mathcal ZZ为配分函数，称A(η)\mathcal A(\eta)A(η)为 对数配分函数 (Log Partition Function)。
• 在介绍马尔可夫随机场的表示(Representation)过程中，使用团(Clique)和势函数(Potential Functions)对随机变量集合X\mathcal XX的联合概率分布P(X)\mathcal P(\mathcal X)P(X)进行表示：
  K\mathcal KK表示极大团的数量/编号；ψi(xCi)\psi_i(x_{\mathcal C_i})ψi​(xCi​​)表示极大团xCix_{\mathcal C_i}xCi​​对应的势函数结果；X∈Rp\mathcal X \in \mathbb R^pX∈Rp.
  P(X)=1Z∏i=1Kψi(xCi)\mathcal P(\mathcal X) = \frac{1}{\mathcal Z}\prod_{i=1}^{\mathcal K} \psi_i(x_{\mathcal C_i})P(X)=Z1​i=1∏K​ψi​(xCi​​)
  而这里的Z\mathcal ZZ也是配分函数，对势函数结果起到一个归一化作用，并将其映射成概率分布：
  Z=∑X∏i=1Kψi(xCi)=∑x1,⋯,xp∏i=1Kψi(xCi)\begin{aligned} \mathcal Z & = \sum_{\mathcal X} \prod_{i=1}^{\mathcal K} \psi_i(x_{\mathcal C_i}) \\ & = \sum_{x_1,\cdots,x_p} \prod_{i=1}^{\mathcal K} \psi_i(x_{\mathcal C_i}) \end{aligned}Z​=X∑​i=1∏K​ψi​(xCi​​)=x1​,⋯,xp​∑​i=1∏K​ψi​(xCi​​)​

配分函数介绍

配分函数在哪些情况下会“直面”到？

• 求解配分函数的目的是针对Learning\text{Learning}Learning问题：给定样本集合X\mathcal XX(可观测的)，将概率模型P(X;θ)\mathcal P(\mathcal X;\theta)P(X;θ)中的模型参数θ\thetaθ求解出来：
  如极大似然估计，最大后验概率估计，EM算法~
  θ^=arg⁡max⁡θP(X;θ)\hat \theta = \mathop{\arg\max}\limits_{\theta} \mathcal P(\mathcal X;\theta)θ^=θargmax​P(X;θ)

  在参数θ\thetaθ的求解过程中，需要求解配分函数Z\mathcal ZZ对原式进行归一化处理(Normalization)；

• Evaluation\text{Evaluation}Evaluation问题：如果此时模型已经求解(模型参数θ\thetaθ，未归一化的概率密度函数P(X)\mathcal P(\mathcal X)P(X)均以求解)，但是关于X\mathcal XX的联合概率分布P(X;θ)\mathcal P(\mathcal X ; \theta)P(X;θ)由于没有归一化因子依然无法求解。
  这里所说的模型一般是指‘无向图模型’。有向图模型的求值问题，如之前介绍的隐马尔可夫模型——前向、后向算法就不会出现这种情况.
因为有向图模型可以通过‘因子分解’准确找出各随机变量之间的条件关系。当然，隐马尔可夫模型有‘齐次马尔可夫假设、观测独立性假设’的约束，可以更加简化迭代过程。

场景构建

从样本(Sample)的角度观察，样本集合X\mathcal XX中包含NNN个样本：
X={x(i)}i=1N\mathcal X = \{x^{(i)}\}_{i=1}^NX={x(i)}i=1N​
从随机变量(Random Variable)的角度观察，已知随机变量集合X∈Rp\mathcal X \in \mathcal R^pX∈Rp，并且ppp个随机变量xi(i=1,2,⋯,p)x_i(i=1,2,\cdots,p)xi​(i=1,2,⋯,p)均服从伯努利分布：
X∈{0,1}p\mathcal X \in \{0,1\}^pX∈{0,1}p
那么关于X\mathcal XX有效的概率分布/概率密度函数P(X;θ)\mathcal P(\mathcal X;\theta)P(X;θ)表示如下：
这里说的‘有效的’指的是归一化后的、可以直接使用的概率密度函数。
P(X;θ)=1Z(θ)P^(X;θ)Z(θ)=∑x1,⋯,xpP^(X;θ)\begin{aligned} \mathcal P(\mathcal X;\theta) & = \frac{1}{\mathcal Z(\theta)} \hat \mathcal P(\mathcal X;\theta) \\ \mathcal Z(\theta) & = \sum_{x_1,\cdots,x_p} \hat \mathcal P(\mathcal X;\theta) \end{aligned}P(X;θ)Z(θ)​=Z(θ)1​P^(X;θ)=x1​,⋯,xp​∑​P^(X;θ)​
其中P^(X;θ)\hat \mathcal P(\mathcal X;\theta)P^(X;θ)是未归一化的、从概率图模型中直接得到的概率密度函数；Z(θ)\mathcal Z(\theta)Z(θ)表示配分函数。
很明显，随机变量x1,⋯,xpx_1,\cdots,x_px1​,⋯,xp​全部被积分掉了。配分函数Z\mathcal ZZ仅和模型参数θ\thetaθ相关。

包含配分函数的极大似然估计

在学习任务中，常用的求解模型参数方式是极大似然估计(Maximum Likelihood Estimation,MLE)：
依然假设样本之间属于‘独立同分布’，引入log⁡\loglog函数，并不影响最值的取值结果。
θ^=arg⁡max⁡θP(X;θ)=arg⁡max⁡θlog⁡∏i=1NP(x(i);θ)=arg⁡max⁡θ∑i=1Nlog⁡P(x(i);θ)\begin{aligned} \hat \theta & = \mathop{\arg\max}\limits_{\theta} \mathcal P(\mathcal X;\theta) \\ & = \mathop{\arg\max}\limits_{\theta} \log \prod_{i=1}^N \mathcal P(x^{(i)} ;\theta) \\ & = \mathop{\arg\max}\limits_{\theta} \sum_{i=1}^N \log \mathcal P(x^{(i)} ;\theta) \end{aligned}θ^​=θargmax​P(X;θ)=θargmax​logi=1∏N​P(x(i);θ)=θargmax​i=1∑N​logP(x(i);θ)​
将P(X;θ)=1Z(θ)P^(X;θ)\mathcal P(\mathcal X;\theta) = \frac{1}{\mathcal Z(\theta)} \hat \mathcal P(\mathcal X;\theta)P(X;θ)=Z(θ)1​P^(X;θ)代入，有：
θ^=arg⁡max⁡θ∑i=1Nlog⁡[1Z(θ)P^(x(i);θ)]=arg⁡max⁡θ∑i=1N[log⁡P^(x(i);θ)−log⁡Z(θ)]\begin{aligned} \hat \theta & = \mathop{\arg\max}\limits_{\theta} \sum_{i=1}^N \log \left[\frac{1}{\mathcal Z(\theta)} \hat \mathcal P(x^{(i)};\theta)\right] \\ & = \mathop{\arg\max}\limits_{\theta} \sum_{i=1}^N \left[\log \hat \mathcal P(x^{(i)};\theta) - \log \mathcal Z(\theta)\right] \end{aligned}θ^​=θargmax​i=1∑N​log[Z(θ)1​P^(x(i);θ)]=θargmax​i=1∑N​[logP^(x(i);θ)−logZ(θ)]​
由于配分函数Z(θ)\mathcal Z(\theta)Z(θ)中不含iii，因而上式可继续简化：
直接在等式右侧除以NNN，系数并不影响最值的取值结果。
θ^=arg⁡max⁡θ∑i=1Nlog⁡P^(x(i);θ)−N⋅log⁡Z(θ)=arg⁡max⁡θ1N∑i=1Nlog⁡P^(x(i);θ)−log⁡Z(θ)\begin{aligned} \hat \theta & = \mathop{\arg\max}\limits_{\theta} \sum_{i=1}^N \log \hat \mathcal P(x^{(i)};\theta) - N \cdot \log \mathcal Z(\theta) \\ & = \mathop{\arg\max}\limits_{\theta} \frac{1}{N}\sum_{i=1}^N \log \hat \mathcal P(x^{(i)};\theta) - \log \mathcal Z(\theta) \end{aligned}θ^​=θargmax​i=1∑N​logP^(x(i);θ)−N⋅logZ(θ)=θargmax​N1​i=1∑N​logP^(x(i);θ)−logZ(θ)​

由于是求解最大值，因此将L(θ)=1N∑i=1Nlog⁡P^(X;θ)−log⁡Z(θ)\mathcal L(\theta) = \frac{1}{N}\sum_{i=1}^N \log \hat \mathcal P(\mathcal X;\theta) - \log \mathcal Z(\theta)L(θ)=N1​∑i=1N​logP^(X;θ)−logZ(θ)看做目标函数，使用梯度上升法(Gradient Ascent)对模型参数近似求解：

• L(θ)\mathcal L(\theta)L(θ)对θ\thetaθ求解梯度：
  这个对应花书-直面配分函数公式(18.4)
  ∇θL(θ)=1N∑i=1N[∇θlog⁡P^(x(i);θ)]−∇θlog⁡Z(θ)\nabla_{\theta} \mathcal L(\theta) = \frac{1}{N} \sum_{i=1}^N \left[\nabla_{\theta}\log \hat \mathcal P(x^{(i)};\theta)\right] - \nabla_{\theta} \log \mathcal Z(\theta)∇θ​L(θ)=N1​i=1∑N​[∇θ​logP^(x(i);θ)]−∇θ​logZ(θ)
  通常称1N∑i=1N[∇θlog⁡P^(x(i);θ)]\frac{1}{N} \sum_{i=1}^N \left[\nabla_{\theta}\log \hat \mathcal P(x^{(i)};\theta)\right]N1​∑i=1N​[∇θ​logP^(x(i);θ)]部分为 正相(Positive Phase)；称∇θlog⁡Z(θ)\nabla_{\theta} \log \mathcal Z(\theta)∇θ​logZ(θ)为 负相(Negative)。在当前示例中，所有随机变量均是基于样本的观测变量，不包含隐变量。因此，正相的求解仅需要将样本带入即可：
  需要注意的是，每一次求解梯度都需要带入NNN个样本，这种方法就是传统的‘批量梯度上升法’。(Batch Gradient Ascent,BGA)(\text{Batch Gradient Ascent,BGA})(Batch Gradient Ascent,BGA)
  ‘批量梯度下降法’也是同理的。(Batch Gradient Descent,BGD)\text{(Batch Gradient Descent,BGD)}(Batch Gradient Descent,BGD)
  如果从已知NNN个样本中选出m(m个样本计算梯度，对应名称即(miniBatch Gradient Descent/Ascent)\text{(miniBatch Gradient Descent/Ascent)}(miniBatch Gradient Descent/Ascent).
  x(i)⇒1N∑i=1N∇θP^(x(i);θ)P^(x(i);θ)x^{(i)} \Rightarrow \frac{1}{N}\sum_{i=1}^N \frac{\nabla_{\theta} \hat \mathcal P(x^{(i)};\theta)}{\hat \mathcal P(x^{(i)};\theta)}x(i)⇒N1​i=1∑N​P^(x(i);θ)∇θ​P^(x(i);θ)​
  受限玻尔兹曼机(Restricted Boltzmann Machine, RBM)由于观测变量给定的条件下，隐变量之间相互独立。因此，受限玻尔兹曼机是一个典型的正相容易求解，负相难求解的模型。

• 而负相的求解是困难的。这里着重观察log⁡Z(θ)\log \mathcal Z(\theta)logZ(θ)梯度的求解过程。
  ∇θlog⁡Z(θ)=1Z(θ)∇θZ(θ)\nabla_{\theta} \log \mathcal Z(\theta) = \frac{1}{\mathcal Z(\theta)} \nabla_{\theta} \mathcal Z(\theta)∇θ​logZ(θ)=Z(θ)1​∇θ​Z(θ)
  将Z(θ)=∑x1,⋯,xpP^(X;θ)\mathcal Z(\theta) = \sum_{x_1,\cdots,x_p} \hat \mathcal P(\mathcal X;\theta)Z(θ)=∑x1​,⋯,xp​​P^(X;θ)带入上式，有：
  ∇θlog⁡Z(θ)=1Z(θ)⋅∇θ∑x1,⋯,xpP^(X;θ)\nabla_{\theta} \log \mathcal Z(\theta) = \frac{1}{\mathcal Z(\theta)}\cdot \nabla_{\theta} \sum_{x_1,\cdots,x_p} \hat \mathcal P(\mathcal X;\theta)∇θ​logZ(θ)=Z(θ)1​⋅∇θ​x1​,⋯,xp​∑​P^(X;θ)

• 根据牛顿-莱布尼兹公式，有：
  积分-梯度符号互换。
  ∇θlog⁡Z(θ)=1Z(θ)⋅∑x1,⋯,xp∇θP^(X;θ)\nabla_{\theta} \log \mathcal Z(\theta) = \frac{1}{\mathcal Z(\theta)} \cdot \sum_{x_1,\cdots,x_p} \nabla_{\theta} \hat \mathcal P(\mathcal X;\theta)∇θ​logZ(θ)=Z(θ)1​⋅x1​,⋯,xp​∑​∇θ​P^(X;θ)
  由于Z(θ)\mathcal Z(\theta)Z(θ)自身和X\mathcal XX没有任何关系(因为x1,⋯,xpx_1,\cdots,x_px1​,⋯,xp​均被积分掉了)，因此这里使用一些技巧：将1Z(θ)\frac{1}{\mathcal Z(\theta)}Z(θ)1​添加到积分号∑x1,⋯,xp\sum_{x_1,\cdots,x_p}∑x1​,⋯,xp​​中：
  根据P(X;θ)=1Z(θ)P^(X;θ)\mathcal P(\mathcal X;\theta) = \frac{1}{\mathcal Z(\theta)} \hat \mathcal P(\mathcal X;\theta)P(X;θ)=Z(θ)1​P^(X;θ)有1Z(θ)=P(X;θ)P^(X;θ)\frac{1}{\mathcal Z(\theta)} = \frac{\mathcal P(\mathcal X;\theta)}{\hat \mathcal P(\mathcal X;\theta)}Z(θ)1​=P^(X;θ)P(X;θ)​并带入到式子中。
  ∇θlog⁡Z(θ)=∑x1,⋯,xp1Z(θ)⋅∇θP^(X;θ)=∑x1,⋯,xp[P(X;θ)⋅1P^(X;θ)⋅∇θP^(X;θ)]\begin{aligned} \nabla_{\theta} \log \mathcal Z(\theta) & = \sum_{x_1,\cdots,x_p} \frac{1}{\mathcal Z(\theta)} \cdot \nabla_{\theta} \hat \mathcal P(\mathcal X;\theta) \\ & = \sum_{x_1,\cdots,x_p} \left[\mathcal P(\mathcal X;\theta) \cdot \frac{1}{\hat \mathcal P(\mathcal X;\theta)} \cdot \nabla_{\theta} \hat \mathcal P(\mathcal X;\theta)\right] \end{aligned}∇θ​logZ(θ)​=x1​,⋯,xp​∑​Z(θ)1​⋅∇θ​P^(X;θ)=x1​,⋯,xp​∑​[P(X;θ)⋅P^(X;θ)1​⋅∇θ​P^(X;θ)]​

• 观察1P^(X;θ)⋅∇θP^(X;θ)\frac{1}{\hat \mathcal P(\mathcal X;\theta)} \cdot \nabla_{\theta} \hat \mathcal P(\mathcal X;\theta)P^(X;θ)1​⋅∇θ​P^(X;θ)，它可以化简为：
  1P^(X;θ)⋅∇θP^(X;θ)=∇θlog⁡P^(X;θ)\frac{1}{\hat \mathcal P(\mathcal X;\theta)} \cdot \nabla_{\theta} \hat \mathcal P(\mathcal X;\theta) = \nabla_{\theta} \log \hat \mathcal P(\mathcal X;\theta)P^(X;θ)1​⋅∇θ​P^(X;θ)=∇θ​logP^(X;θ)
  最终关于梯度∇θlog⁡Z(θ)\nabla_{\theta} \log \mathcal Z(\theta)∇θ​logZ(θ)可表示为：
  ∇θlog⁡Z(θ)=∑x1,⋯,xp[P(X;θ)⋅∇θlog⁡P^(X;θ)]=EP(X;θ)[∇θlog⁡P^(X;θ)]\begin{aligned} \nabla_{\theta} \log \mathcal Z(\theta) & = \sum_{x_1,\cdots,x_p} \left[\mathcal P(\mathcal X;\theta) \cdot \nabla_{\theta} \log \hat \mathcal P(\mathcal X;\theta)\right] \\ & = \mathbb E_{\mathcal P(\mathcal X;\theta)} [\nabla_{\theta} \log \hat \mathcal P(\mathcal X;\theta)] \end{aligned}∇θ​logZ(θ)​=x1​,⋯,xp​∑​[P(X;θ)⋅∇θ​logP^(X;θ)]=EP(X;θ)​[∇θ​logP^(X;θ)]​

关于这个期望结果，由于没有办法求解它的精确解，因此常用蒙特卡洛方法(Monti Carlo Method)进行近似求解。

下一节将介绍随机最大似然(Stochastic Maximum Likelihood)与对比散度(Contrastive Divergence)。

相关参考：
直面配分函数-1-The log-likelihood gradient
深度学习(花书)——第18章 直面配分函数