引用本文

付维明, 秦家虎, 朱英达. 基于扩散方法的分布式随机变分推断算法. 自动化学报, 2021, 47(1): 92−99 doi:  10.16383/j.aas.c200445

Fu Wei-Ming, Qin Jia-Hu, Zhu Ying-Da. Distributed stochastic variational inference based on diffusion method. Acta Automatica Sinica, 2021, 47(1): 92−99 doi: 10.16383/j.aas.c200445

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200445

关键词

分布式算法，随机变分推断，扩散方法，异步网络，主题模型 

摘要

分布式网络上的聚类、估计或推断具有广泛的应用, 因此引起了许多关注. 针对已有的分布式变分贝叶斯(Variational Bayesian, VB)算法效率低, 可扩展性差的问题, 本文借用扩散方法提出了一种新的分布式随机变分推断(Stochastic variational inference, SVI)算法, 其中我们选择自然梯度法进行参数本地更新并选择对称双随机矩阵作为节点间参数融合的系数矩阵. 此外, 我们还为所提出的分布式SVI算法提出了一种对异步网络的适应机制. 最后, 我们在伯努利混合模型(Bernoulli mixture model, BMM)和隐含狄利克雷分布(Latent Dirichlet allocation, LDA)模型上测试所提出的分布式SVI算法的可行性, 实验结果显示其在许多方面的性能优于集中式SVI算法.

文章导读

在大数据时代, 数据通常会被分布式地存储在多个节点上, 例如传感器网络[1-3]和分布式数据库[4]中等, 其中每个节点只拥有部分数据. 考虑到单个节点的存储容量有限以及保护数据隐私或安全的需求[5-6], 通常无法将所有数据都发送给一个中心节点, 然后利用集中式的方法处理这些数据, 因此开发高效的算法对分布式存储的数据进行挖掘已成为当前一个重要的研究方向[7-12].

变分贝叶斯(Variational Bayesian, VB)推断[13]是一种功能强大的数据挖掘技术, 被广泛用于解决实际问题, 如识别文档主题[14-15], 对数据进行聚类和密度估计[16]以及预测未知数据[17]等. 近年来, 研究者们已提出很多分布式的VB算法[3, 18-20], 然而在大多数这些算法的每步迭代中, 都需要基于整个数据集更新全局参数, 这不仅会导致算法计算代价大、效率低, 还会导致算法可扩展性差, 难以扩展到在线学习或者流数据处理的情况.

随机变分推断(Stochastic variational inference, SVI)[15]的提出使得贝叶斯推断方法在处理海量数据时具有更高的效率和可扩展性. 它借用了随机优化的方法, 根据基于子样本的噪声自然梯度来优化目标函数, 大大减小了每步迭代时所需的存储量和计算量. 目前已有一些研究者将其扩展为分布式版本, 以提高分布式数据的处理效率以及将其应用于分布式数据流的处理[21]. 具体地, 文献[22]提出了一种有中心的异步分布式SVI算法, 该算法中的中心节点负责收发全局参数, 其余节点并行地更新全局参数. 值得一提的是, 这类有中心的算法往往会存在鲁棒性差, 链路负载不平衡, 数据安全性差等缺点. 在文献[11]中, 交替方向乘子方法(Alternating direction method of multipliers, ADMM)[23]被用来构造两种无中心的分布式SVI算法, 克服了有中心的算法的缺点, 但它们存在每步迭代中全局参数本地更新所需的计算代价大以及不适用于异步网络的缺点.

本文以SVI为核心, 借用多智能体一致优化问题中的扩散方法[24], 发展了一种新的无中心的分布式SVI算法, 并针对异步网络提出了一种适应机制. 在所提出的算法中, 我们利用自然梯度法进行全局参数的本地更新, 并选择对称双随机矩阵作为节点间参数融合的系数矩阵, 减小了本地更新的计算代价. 最后, 我们在伯努利混合模型(Bernoulli mixture model, BMM)和隐含狄利克雷分布(Latent Dirichlet allocation, LDA)上验证了所提出的算法的可行性, 实验结果显示所提出的算法在发现聚类模式, 对初始参数依耐性以及跳出局部最优等方面甚至优于集中式SVI算法, 这是以往分布式VB算法所没有表现出来的.

本文其余部分安排如下: 第1节介绍集中式SVI算法; 第2节介绍本文所提出的分布式SVI算法并给出了一种针对异步网络的适应机制; 第3节展示在BMM和LDA模型上的实验结果; 第4节对本文工作进行总结.

图1 本文考虑的模型的概率图表示

图2 通信网络拓扑图

图3 异步分布式SVI算法和集中式SVI算法得到的聚类中心

本文针对无中心的分布式网络, 基于扩散方法提出了一种新颖的分布式SVI算法, 其中采用自然梯度法进行本地更新以及采用对称双随机矩阵作为信息融合系数, 并且为其设计了一种针对异步网络的适应机制. 然后将其应用于BMM和LDA主题模型. 在不同数据集上的实验均表明所提出的算法确实适用于异步分布式网络, 而且其在发现聚类模式和对抗浅的局部最优方面的表现优于集中式SVI算法.

作者简介

付维明

中国科学技术大学自动化系博士后. 主要研究方向为多智能体系统一致与物理信息系统安全. E-mail: fwm1993@ustc.edu.cn

秦家虎

中国科学技术大学自动化系教授. 主要研究方向为多智能体系统, 复杂动态网络以及物理信息系统. 本文通信作者. E-mail: jhqin@ustc.edu.cn

朱英达

中国科学技术大学自动化系硕士. 主要研究方向为数据挖掘和分布式算法. E-mail: xy131237@mail.ustc.edu.cn