Support consistency of direct sparse-change learning in Markov networks

DOI10.1214/16-AOS1470MaRDI QIDQ2012923zbMATH OpenFDO

Authors Song Liu, Taiji Suzuki, Raissa Relator, Jun Sese, Masashi Sugiyama, Kenji Fukumizu

Publication date 3 August 2017

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.0581, https://projecteuclid.org/euclid.aos/1497319685

zbMATH Keywords

change detectiondensity ratio estimationMarkov networkssparse-change learning

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Estimation in multivariate analysis (62H12) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We study the problem of learning sparse structure changes between two Markov networks $P$ and $Q$. Rather than fitting two Markov networks separately to two sets of data and figuring out their differences, a recent work proposed to learn changes emph{directly} via estimating the ratio between two Markov network models. In this paper, we give sufficient conditions for emph{successful change detection} with respect to the sample size $n_p,n_q$, the dimension of data $m$, and the number of changed edges $d$. When using an unbounded density ratio model we prove that the true sparse changes can be consistently identified for $n_p=Omega(d^{2}logfrac{m}^2+m2)$ and $n_q=Omega(n_p^2)$, with an exponentially decaying upper-bound on learning error. Such sample complexity can be improved to $min(n_p,n_q)=Omega(d^{2}logfrac{m}^2+m2)$ when the boundedness of the density ratio model is assumed. Our theoretical guarantee can be applied to a wide range of discrete/continuous Markov networks.

Recommendations

• Direct Learning of Sparse Changes in Markov Networks by Density Ratio Estimation
• scientific article; zbMATH DE number 1931919
• Sparse and low-rank matrix regularization for learning time-varying Markov networks
• Marginal pseudo-likelihood learning of discrete Markov network structures
• Change point estimation in high dimensional Markov random-field models

Cited in

(3)

• Consistent change-point detection with kernels
• Direct Learning of Sparse Changes in Markov Networks by Density Ratio Estimation
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes

This page was built for publication: Support consistency of direct sparse-change learning in Markov networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012923)