关键词:
图学习
图拉普拉斯矩阵
平滑图信号
图信号处理
吸引的DC-内禀的高斯马尔可夫随机场
精度矩阵
摘要:
随着信息技术的飞速发展,万物互联化、数据泛在化的趋势明显,数据呈现出海量、结构化和高维低秩等特点。如果能从数据中捕获数据之间的结构特征并加以利用,有助于人们更好地对数据进行采集、存储、传输和应用。图是抽象表示数据实体之间拓扑结构的重要工具,一旦在数据实体之间建立了具有可解释性的图,就可以结合谱图理论和信号处理方法对数据进行系统的分析和处理。然而,图并不都是先验已知的,由此出现了图学习研究,即从观测数据中推测数据实体之间可能存在的图结构信息。图拉普拉斯矩阵是图的一类矩阵表示,能够反映图的结构信息,且具有特殊的谱特性,是谱图理论研究的核心内容之一,在机器学习和图信号处理等领域得到广泛的应用。尤其在图信号处理领域,图傅里叶变换、图滤波等概念都建立在图拉普拉斯矩阵的基础之上。在高斯图模型中,吸引的DC-内禀的高斯马尔可夫随机场的精度矩阵是拉普拉斯矩阵,对应的随机变量服从退化的多元高斯分布且具有非负偏相关性,因此图拉普拉斯矩阵还具有统计意义。本文基于图信号处理和高斯图模型理论,研究从观测数据推断图拉普拉斯矩阵的方法,从而获得图的结构信息,揭示数据实体之间的关联性,为拉普拉斯理论框架下的信号分析和处理提供技术支撑。主要研究内容如下:1.针对具有时间和空间变化平滑性的信号,提出从时空平滑信号推断图拉普拉斯矩阵的方法。首先,利用笛卡尔乘积构造时空联合图,将观测信号表示为时空联合图频域上低频分量的线性组合,建模时空平滑图信号表示模型。其次,通过最大后验概率估计,构建以联合图拉普拉斯矩阵和重构的图信号为优化变量的图学习问题。最后,根据笛卡尔乘积图的性质分解图学习问题,用原始-对偶与共轭梯度下降算法交替迭代求解子问题,通过约束重构图信号的时空平滑性获得时间图和顶点图的拉普拉斯矩阵。所提图学习方法在图学习的同时利用图拉普拉斯矩阵在时域和空域对图信号进行重构,在噪声和缺失信号场景下,图信号重构的精度高,进而保证了图学习性能。实验结果表明,在信号采样率为0.5的场景下,所提图学习方法仍然能够达到较高的图学习精度,优于对比的图学习方法。2.物理系统的观测数据可能会受到潜在因素的影响,如果数据服从退化的多元高斯分布且存在非负偏相关性,可用拉普拉斯约束下的隐变量高斯图模型建模,以刻画潜在因素的影响。在给定隐变量的条件下,观测变量的条件精度矩阵是稀疏的。但由于隐变量未知,拉普拉斯约束下的一般图学习方法只能估计观测变量的边缘精度矩阵,该矩阵具有“稀疏+低秩”的非稀疏结构。图的稀疏性在统计和计算上至关重要,为此,本文提出的图学习方法在估计边缘精度矩阵的同时,分离“稀疏项”和“低秩项”,其中的“稀疏项”即观测变量的条件精度矩阵,其稀疏模式可揭示观测变量之间的成对条件独立性。首先,通过最大化观测变量的边缘似然函数,构建图学习优化问题,其优化变量包括观测变量的边缘精度矩阵、条件精度矩阵以及低秩矩阵。通过证明它们分别具有组合拉普拉斯、对角占优拉普拉斯以及非负性等特殊的矩阵性质,图学习问题被进一步约束为具有特定形式矩阵变量的凸优化问题。最后通过多块交替方向乘子法求解得到三个目标矩阵。实验结果表明,在隐变量存在的情况下,所提方法能够有效推断条件精度矩阵的稀疏模式,为后继信号分析和处理任务提供稀疏图。3.在大规模网络中,由于数据样本、通信带宽和计算资源的有限性,集中式图学习存在困难。针对这一挑战,本文提出了拉普拉斯和结构约束下的分布式图学习方法。首先通过定义每个顶点的局部邻域,并最大化局部变量的边缘似然函数,构建低维的带拉普拉斯和结构约束的局部优化问题,再利用块坐标下降算法求解。最后,从每个局部问题的优化解中提取参数,通过单一的信息传递、合并以及对称化,得到全局图拉普拉斯矩阵。所提分布式图学习方法计算复杂度低、可并行计算,在无采样误差的情况下,可以达到全局估计的统计精度。实验结果验证了以上理论结果。