| PhD Seminar

Name of the Speaker: Ms. Bagewadi Smita Milind (EE19D002)
Guide: Dr. Arun Pachai Kannu
Venue: ESB-234 (Malaviya Hall)
Date/Time: 31st July 2024 (Wednesday), 3:30 PM
Title: Learning the Influence Graph of a High-Dimensional Markov Process with Memory

Abstract :

This work considers the problem of learning the underlying (directed) influence graph or causal graph of a high-dimensional multivariate discrete-time Markov process with memory. This problem is vital in many real-world applications, including social networks and nervous systems. At any discrete time instant, each observed variable of the multivariate process is a binary string of random length, which is parameterized by an unobservable or hidden [0,1]-valued scalar. The hidden scalars corresponding to the variables evolve according to discrete-time linear stochastic dynamics dictated by the underlying influence graph whose nodes are the variables. This work extends an algorithm for learning i.i.d. graphical models to the Markovian setting with memory by introducing directed conditional entropy as a metric for learning the neighborhood. The adapted algorithm can learn the influence graph based on the binary observations using logarithmic (in number of variables or nodes) samples when the degree of the influence graph is bounded. The crucial analytical contribution of this work is the derivation of the sample complexity result by upper and lower bounding the rate of convergence of the observed Markov process with memory to its stationary distribution in terms of the parameters of the influence graph. Simulations show that the adapted algorithm has a high probability of success even in cases where the analytical bound is not applicable.