Online matrix factorization for Markovian data and applications to Network Dictionary Learning
Online matrix factorization for Markovian data and applications to Network Dictionary Learning
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Hanbaek Lyu;D. Needell;L. Balzano
中科院分区：
文献类型：
--
作者：
Hanbaek Lyu;D. Needell;L. Balzano
在线矩阵分解（OMF）是字典学习问题的基本工具，它根据提取的特征的减少数量给出了复杂数据集的近似表示。文献中大多数OMF算法的收敛保证假定数据矩阵之间是独立的，而依赖数据流的情况在很大程度上仍未被探索。在本文中，我们证明了在\cite{mairal2010online}中提出的著名的用于i.i.d数据流的OMF算法实际上几乎肯定地收敛于期望损失函数的临界点集，即使当数据矩阵形成满足温和混合条件的马尔可夫链时也是如此。进一步，我们将收敛结果推广到算法中每一步优化问题都只能近似求解的情况。对于应用，我们演示了从马尔可夫链蒙特卡罗（MCMC）采样器生成的图像序列中进行字典学习。最后，通过结合在线非负矩阵分解和最近的MCMC算法从网络中采样motif，我们提出了一个新的网络字典学习框架，该框架以在线方式从给定网络中提取“网络字典补丁”，编码网络的主要特征。我们在真实的文本数据上演示了这种技术。
Online Matrix Factorization (OMF) is a fundamental tool for dictionary learning problems, giving an approximate representation of complex data sets in terms of a reduced number of extracted features. Convergence guarantees for most of the OMF algorithms in the literature assume independence between data matrices, and the case of a dependent data stream remains largely unexplored. In this paper, we show that the well-known OMF algorithm for i.i.d. stream of data proposed in \cite{mairal2010online}, in fact converges almost surely to the set of critical points of the expected loss function, even when the data matrices form a Markov chain satisfying a mild mixing condition. Furthermore, we extend the convergence result to the case when we can only approximately solve each step of the optimization problems in the algorithm. For applications, we demonstrate dictionary learning from a sequence of images generated by a Markov Chain Monte Carlo (MCMC) sampler. Lastly, by combining online non-negative matrix factorization and a recent MCMC algorithm for sampling motifs from networks, we propose a novel framework of Network Dictionary Learning, which extracts `network dictionary patches' from a given network in an online manner that encodes main features of the network. We demonstrate this technique on real-world text data.