通信系统中的变分推理技术--因子图和消息传递方法

第1章绪论 在现代工程应用中，往往要对复杂系统中的某些参量进行估计。例如在无线通信系统中，源数据经编码、调制后由发射天线发出，经过信道传输后到达接收机。接收机的功能是从接收信号中*佳地估计出源数据。信号在传播过程中会受到信道和各类干扰的影响。如图1.1所示，由于接收者所处地理环境的复杂性，接收到的信号不仅可能有直射波，还可能有从不同物体（建筑物、道路、树木等）反射、绕射及散射过来的多条不同路径的电磁波。这些沿不同路径到达接收端的电磁波的信号强度、到达时间、到达角及载波相位等均不相同，接收端所接收到的信号是上述各路径信号的矢量和。这些不同路径信号之间有些相互增强，有些相互抵消，形成小尺度衰落（或多径效应）[1]。在大量随机噪声和干扰的环境下，接收机的目的是从接收到的复杂信号中恢复原始发送数据，这需要对干扰、噪声和信道等对象进行概率建模，然后利用统计的方法对信号进行处理。 统计信号处理为解决在随机信号下的估计问题提供了理论依据，它一般使用信号的统计特征完成信号处理任务。统计信号处理主要包括估计理论和检测理论，其中估计理论主要解决的是从包含随机噪声的接收信号里提取感兴趣参数的问题。统计信号处理具有广泛的应用领域，如无线通信中的基带信号处理、雷达监测、声呐定位、语音信号处理以及图像处理等。图1.1所示问题就可以采用统计信号处理的方法解决。贝叶斯理论认为一个系统中所有未知的参数都是随机的信号，它们可以是随机变量，也可以是未知的确定性参数，在这种理念下发展起来的估计方法，称为贝叶斯估计[2]。本书主要讨论贝叶斯估计理论及其应用。 1.1贝叶斯估计 在一个复杂系统中，考虑两类随机变量：感兴趣的参数和观.它们的某次实现分别是。贝测和叶斯估计通过选择合适的损失函数，采用贝叶斯推理得到感兴趣参数的估计值。贝叶斯推理（Bayesian Inference）是在给定先验概率和似然函数的条件下，利用贝叶斯公式求解后验概率的技术。贝叶斯公式为实现贝叶斯推理与贝叶斯估计提供了理论依据： (1-1) 在贝叶斯估计中，根据损失函数的不同，可以得到两类主要的*优估计准则：使得二次型风险函数*小的称为*小均方误差（Minimum Mean Square Error，MMSE）估计，使得均匀风险函数*小的称为*大后验（MaximumA-Posteriori，MAP）估计，两者分别定义为[3，4]： （1-3） 由式（1-1）～式（1-3）可以看出，这两种准则的求解需要利用的先验信息和似然函数，且均需要求解边缘后验概率密度函数（Probability DensityFunction，PDF）。原理上，边缘后验PDF可以通过边缘化联合后验PDF得到： （1-4） 其中，表示N维随机变量的联合后验PDF，表示除以外的剩余元素（若随机变量的元素为离散型，上式积分号需改为求和号。本书第2章证明了可以把离散型随机变量的概率质量函数用等价的PDF表示，那么式（1-4）可适用于连续和离散型随机变量）。通常把按照式（1-4）求解边缘后验PDF的方法称为精确推理。如果可以得到真实的边缘后验，则式（1-2）和式（1-3）可以得到精确解。但是当x的维度比较大时，由于式（1-4）存在多重积分，求解感兴趣参数边缘后验PDF的计算复杂度很高，甚至是不可实现的。例如在现代通信系统中通常有成千上万个变量，包括信息比特、编码比特、调制符号和信道参数等，若，则的取值共有21000种可能。相应的联合后验PDF共有21000项，其中计算.或均需2999.1次求和。由此可以看出计算边缘后验PDF的复杂度与变量的维度呈指数增长[7]。当变量维度较高时，按照式（1-4）的方法计算边缘后验PDF是当前计算条件下难以实现的。此外按照式（1-4）积分，有时联合后验PDF积分可能无法得到闭式解。在这些情况下，工程人员通常采用一些近似推理的方法获得感兴趣参数的边缘后验PDF。 目前，求解边缘后验PDF的近似推理方法主要有两类：马尔可夫链蒙特卡洛（Marko Chain Monte Carlo，MCMC）方法[8-10]和变分推理（Variational Inference）方法[11]。MCMC方法用大量采样代替联合后验PDF，式（1-4）不再对联合后验PDF进行积分，只对采样计算积分。大量采样可保证能够高精度逼近各种类型的复杂函数，但是也造成过高的计算复杂度，难以工程实现[4]。变分推理是一种高性能低成本的近似技术，其基本思想是利用一个易于分解、形式简单的“实验”函数。MCMC方法是一种无偏估（称为置信，Belief）逼近真实的联合后验PDF[12]计，在采样足够多的情况下可以得到更为精确的估计值，但是计算复杂度高，难以应用于大系统中的估计问题，并且在算法执行过程中需要监控马尔可夫链的收敛；而变分推理是有偏估计，但它效率很高，且是一个确定性方法，通过少量迭代即可达到收敛，计算复杂度低，适合大系统中的估计问题[13]。 变分推理的关键问题是找到一个可分解的*优，使其与距离*近。通常度量之间近似程度的指标是KL散度，*优的置信可以通过*小化KL散度求解，即 （1-5） 在变分推理过程中，需要应用某些规则，通过*小化KL（Kullback-Leibler）散度（可以证明等价于*小化系统变分自由能）的方法得到迭代算法，当迭代收敛到固定点时，算法可输出一个*优置信。常用的规则包括置信传播[14]、平均场[15]和期望传播[16]等。为了更好地应用这些规则，我们往往需要借助于图的方法，把系统中全部变量以及变量之间的关系构成概率图模型。 图是一种可以用于描述问题的可视化语言，工程师们经常用图形来辅助表述问题，比如电路图、信号流向图、网格图以及各种各样的框图[17]。概率图模型是一种表达变量之间概率关系的图形，一般包括贝叶斯网（Bayesian Network）[18]、马尔可夫随机场（Markov Random Field，MRF）[5]和因子图（Factor Graph，FG）[19]三种类型。贝叶斯网是一种表达变量间因果关系的有向无环图（Directed Acyclic Graph，DAG）。其形式简单，但是图上仅体现变量之间的连接，无法体现连接关系的细节[17]。马尔可夫随机场是一组具有马尔可夫性质①的随机变量组成的无向图。其相比于贝叶斯网能够表示除因果关系外更多的变量间关系，但是应用马尔可夫随机场计算复杂度较高，常采用近似方法代替。因子图是一种表达系统变量联合PDF因子分解的二分图（或称二部图），图上包含变量和因子两类节点。与贝叶斯网、马尔可夫随机场相比，因子图中包含了表示变量间函数关系的因子节点。因子节点的存在使因子图能够表达更详细的变量间关系。此外，因子图还可以进行拉伸、聚合变换，其应用更加灵活[14，20]。 在这三种概率图模型上都可以分别应用不同的规则得到不同的迭代算法，这些算法称为消息传递算法。为了获得*优的置信通常需要依据系统中变量的分布形式，选择不同的规则。在同一张图上，因子图可以联合应用多种不同的规则，从而得到精度更高的置信。因此，因子图和消息传递算法的结合是贝叶斯估计中更好的选择。 1.2因子图研究现状 由于因子图更加灵活多变，更适合设计使KL散度更小的迭代估计算法。近年来，因子图广泛应用于统计物理、通信、机器学习和信号处理等多个领域[21]，国内外学者对其开展了深入的讨论和研究。 *早在图上解决通信中的工程应用问题起源于1963年，Gallager[22]在博士论文中首次应用图形方式描述了低密度奇偶校验码（Low Density Parity Code，LDPC），引入了在图形上表达编码算法的思路。当时计算机处理能力有限且相关理论不够完善，LDPC编码渐渐被人们遗忘，但是在图上表达工程问题的思想引起人们的关注。受其启发1973年Forney[23]提出“网格图”，将其作为一种描述有限状态机中状态转移概率关系的方法。随后，1981年Tanner[24，25]提出了“Tanner图”，图中包含“数字”和“子编码”两类节点，分别表示编码比特及编码比特间的约束关系。1996年Wiberg等人[26]通过引入状态变量将Tanner图与网格图建立联系，提出了一种图上的计算方法，并把和积算法（Sum Product Algorithm，SPA）描述为一种在图上操作的“消息传递算法”，这种算法可以用于Viterbi算法、LDPC解码算法和Turbo解码算法。Wiberg提出的图模型包含因子和变量两种节点，以及节点之间的无向连接线，当前主流的因子图均采用这种表达方法。1998年Frey[27]首次提出“因子图”的概念，它或许可以看作是在Wiberg的思想上进一步细化的结果。Frey证明了在同一个系统中，因子图可以替代贝叶斯网和马尔可夫随机场更好地描述系统模型。2000年Aji[28]提出一种基于“连接树”的图模型实现函数边缘化的一般框架，这个框架具有里程碑的意义。2001年Forney[19]提出了Forney形式的因子图（Forney-Style Factor Graph，FFG），该图由因子节点和边组成，变量表示在边上。FFG形式简单，易于理解，但是对于复杂系统其图变换不够灵活，计算复杂度高。2001年，Kschischang等人[14]使用与Wiberg类似的图模型，与Forney形式的因子图不同，这种图模型增加了变量节点，使得图变换更为灵活，在复杂系统中能利用图变换有效降低计算复杂度。接着Kschischang详细介绍了这种因子图中的“环”及其对计算性能的影响，同时提出了通过“拉伸”和“聚合”解决该类问题的方法，这标志着因子图模型已经发展成熟。2004年，Loeliger[17]总结了在Forney形式因子图上进行信号处理的一般方法，从而使得因子图以及消息传递算法成为重要的形式化设计工具。随后，因子图及消息传递算法在多个领域取得了一系列成果[29-32]。2017年袁正道等人[20]提出一种增加辅助变量的因子图拉伸方法，其与Kschischang所提图变换的目的不同：前者将原本表示复杂函数关系的一个节点变换为几个节点，每个节点选择更合适的消息更新规则，*终实现在降低复杂度的同时提高算法性能。后者目的在于消除因子图中存在的环，保证了算法的收敛，但是增加了算法的复杂度。 一方面，因子图似乎已经发展到成熟阶段，但是作为一种图模型，因子图本身是否能够继续发展将依赖于图论的支撑。另一方面，因子图是设计消息传递算法的有力工具，想要发挥其功能，还需在因子图上根据系统的特点应用不同的规则，设计高性能的消息传递算法，*终得到精度更高的置信。本书将重点研究消息传递算法在因子图上的应用。 1.3消息传递算法研究现状 消息传递算法是一种可以通过迭代方式实现变分推理的有效工具。该类算法根据系统物理特征将系统变量的联合后验PDF进行因子分解并构建因子图模型，然后在因子图上采用合适的消息更新规则，得到合理的消息传递算法，从而以迭代的方式逐步近似求解各变量的边缘后验PDF。 常用的消息更新规则包括：平均场（Mean Field，MF）也称为变分消息传递（Variational Message Passing，VMP）[15]、置信传播（Belief Propagation，BP）也称为和积算法[18]和期望传播（Expectation Propagation，EP）[16]。除了上述独立的消息更新规则，许多国内外团队也开展了联合消息更新规则的研究，提出了联合BP-MF、联合BP-EP和联合BP-EP-MF等规则，这些规则分别适合不同的应用场景。另外，针对一些特殊应用场景，对应用BP规则得到的部分消息进行近似产生了近似消息传递（Approximate Message Passing，AMP）类算法[33-3