In this paper we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics. The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This work deviates from the standard formulation of graphical model learning in the literature, where one assumes access to i.i.d. samples from the distribution. Much of the research on graphical model learning has been directed towards finding algorithms with low computational cost. As the main result of this work, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on @math nodes with maximum degree @math can be learned in time @math , for a function @math , using nearly the information-theoretic minimum number of samples.
More broadly, a number of papers in the learning theory community have considered learning functions (or concepts) from examples generated by Markov chains, including @cite_41 @cite_15 @cite_20 @cite_22 . The present paper is similar in spirit to that of @cite_20 showing that it is relatively easy to learn DNF formulas from examples generated according to a random walk as compared to i.i.d. samples.
@cite_41 @cite_15 @cite_22 @cite_20
2033493462 2004036579 2119243017
An "Occam algorithm" learning model maintains a tentative hypothesis consistent with past observations and, when a new observation is inconsistent with the current hypothesis, updates to the next-simplest hypothesis consistent with all observations. In previous work, observations were assumed to be stochastically independent. This paper initiates study of such models under weaker Markovian assumptions on the observations, In the special case where the sequence of hypotheses satisfies a monotonicity condition, it is shown that the number of mistakes in classifying the first t observations is O(?t log 1 ?i), where ?i is the stationary probability of the initial state, i, of the Markov chain. In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show that this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions, 2-term RSE, and 2-term-DNF, when the examples are generated by a random walk on 0,1 n . We consider a model of learning Boolean functions from examples generated by a uniform random walk on 0, 1 sup n . We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.