Learning mixtures of markov chains from aggregate data with structural constraints (extended abstract)
Dixin Luo, Hongteng Xu, Yi Zhen, Bistra Dilkina, Hongyuan Zha, Xiaokang Yang, Wenjun Zhang · 2017
In this work, we explore the learning task of mixtures of Markov chains (MMCs) from aggregate data. Our work demonstrates that although this challenging task is generally intractable because of the identifiability problem, it can be solved approximately by imposing structural constraints on its transition matrices Specifically, the proposed structural constraints include specifying active state sets corresponding to the chains and adding a series of pairwise sparse regularizers on transition matrices. Based on these two structural constraints, we propose a constrained least-squares method to learn mixtures of Markov chains. We develop a novel iterative algorithm that decomposes the overall problem into a set of convex subproblems and solves each subproblem efficiently. Experimental results on synthetic data prove that our learning method converges well and is robust to the noise in data. Moreover, the comparison with state-of-art competitors on real-world data further validates the superiority of our method.