Liu Song, Quinn John A, Gutmann Michael U, Suzuki Taiji, Sugiyama Masashi
Tokyo Institute of Technology, Meguro, Tokyo 152-8552, Japan
Neural Comput. 2014 Jun;26(6):1169-97. doi: 10.1162/NECO_a_00589. Epub 2014 Mar 31.
We propose a new method for detecting changes in Markov network structure between two sets of samples. Instead of naively fitting two Markov network models separately to the two data sets and figuring out their difference, we directly learn the network structure change by estimating the ratio of Markov network models. This density-ratio formulation naturally allows us to introduce sparsity in the network structure change, which highly contributes to enhancing interpretability. Furthermore, computation of the normalization term, a critical bottleneck of the naive approach, can be remarkably mitigated. We also give the dual formulation of the optimization problem, which further reduces the computation cost for large-scale Markov networks. Through experiments, we demonstrate the usefulness of our method.
我们提出了一种检测两组样本之间马尔可夫网络结构变化的新方法。我们不是简单地分别对两个数据集拟合两个马尔可夫网络模型并找出它们的差异，而是通过估计马尔可夫网络模型的比率直接学习网络结构变化。这种密度比率公式自然地使我们能够在网络结构变化中引入稀疏性，这对增强可解释性有很大帮助。此外，朴素方法的一个关键瓶颈——归一化项的计算，可以显著减轻。我们还给出了优化问题的对偶公式，这进一步降低了大规模马尔可夫网络的计算成本。通过实验，我们证明了我们方法的有效性。
