论文标题
消息通讯算法和同源性
Message-Passing Algorithms and Homology
论文作者
论文摘要
该博士学位论文列出了与概率图形模型研究相关的代数和拓扑结构。 边缘估计算法作为$ \ dot u =Δφ$的扩散方程式引入。他们概括了传统的信仰传播（BP）算法，并为对比度差异（CD）或马尔可夫链蒙特卡洛（MCMC）算法提供了替代方案，通常参与估计自由能函数及其梯度W.R.T.模型参数。 我们提出了一个新的同源图片，其中参数是A_0 $中的局部交互潜力$（U_α）\的集合，对于在给定区域图的因子节点上运行的$α$。 $Δ$映射热通量$（φ_{αβ}）\ in A_1 $ to subspace $ΔA_1\ subseteq A_0 $是分散的离散类似物。总能量$ h = \sum_αu_α$定义全局概率$ p = e^{ - h} / z $与同源类$ [u + +ΔA_1$的交互潜力的一对一对应，因此当$ $ u $ u $ u $ evolve to to y $ u $ evolve to tor Bounce Term term forouse term term term termence underce $Δφ$Δφ$。 固定的扩散状态显示出与局部边际估计值的非线性约束表面执行一致性的同源性类别的相交。这张图片使我们能够精确并完成证明BP的固定状态与局部自由能功能的临界点之间的对应关系（由Bethe-Kikuchi近似获得），并扩展了无循环图（即树）的唯一性结果，以使其成为较宽的超graphs类。通常，平衡的分叉与局部扩散算子的光谱奇异性有关，从而产生了脱落现象的新示例。 PR监督的工作。丹尼尔·本尼金（Daniel Bennequin）
This PhD thesis lays out algebraic and topological structures relevant for the study of probabilistic graphical models. Marginal estimation algorithms are introduced as diffusion equations of the form $\dot u = δφ$. They generalise the traditional belief propagation (BP) algorithm, and provide an alternative for contrastive divergence (CD) or Markov chain Monte Carlo (MCMC) algorithms, typically involved in estimating a free energy functional and its gradient w.r.t. model parameters. We propose a new homological picture where parameters are a collections of local interaction potentials $(u_α) \in A_0$, for $α$ running over the factor nodes of a given region graph. The boundary operator $δ$ mapping heat fluxes $(φ_{αβ}) \in A_1$ to a subspace $δA_1 \subseteq A_0$ is the discrete analog of a divergence. The total energy $H = \sum_αu_α$ defining the global probability $p = e^{-H} / Z$ is in one-to-one correspondence with a homology class $[u] = u + δA_1$ of interaction potentials, so that total energy remains constant when $u$ evolves up to a boundary term $δφ$. Stationary states of diffusion are shown to lie at the intersection of a homology class of potentials with a non-linear constraint surface enforcing consistency of the local marginals estimates. This picture allows us to precise and complete a proof on the correspondence between stationary states of BP and critical points of a local free energy functional (obtained by Bethe-Kikuchi approximations) and to extend the uniqueness result for acyclic graphs (i.e. trees) to a wider class of hypergraphs. In general, bifurcations of equilibria are related to the spectral singularities of a local diffusion operator, yielding new explicit examples of the degeneracy phenomenon. Work supervised by Pr. Daniel Bennequin
