Please use this identifier to cite or link to this item: http://localhost/handle/Hannan/617648
Title: Learning Mixtures of Markov Chains from Aggregate Data with Structural Constraints
Authors: Dixin Luo;Hongteng Xu;Yi Zhen;Bistra Dilkina;Hongyuan Zha;Xiaokang Yang;Wenjun Zhang
subject: aggregate data|prediction|simulation|structural constraints|pairwise sparsity|Mixtures of Markov chains
Year: 2016
Publisher: IEEE
Abstract: Statistical models based on Markov chains, especially mixtures of Markov chains, have recently been studied and demonstrated to be effective in various data mining applications such as tourist flow analysis, animal migration modeling, and transportation administration. Nevertheless, the research so far has mainly focused on analyzing data at individual levels. Due to security and privacy reasons, however, the observations in practice usually consist of coarse-grained statistics of individual data, a.k.a.</italic> aggregate data, rendering learning mixtures of Markov chains an even more challenging problem. In this work, we show that this challenging problem, although intractable in its original form, can be solved approximately by posing structural constraints on the transition matrices. The proposed structural constraints include specifying active state sets corresponding to the chains and adding a pairwise sparse regularization term on transition matrices. Based on these two structural constraints, we propose a constrained least-squares method to learn mixtures of Markov chains. We further develop a novel iterative algorithm that decomposes the overall problem into a set of convex subproblems and solves each subproblem efficiently, making it possible to effectively learn mixtures of Markov chains from aggregate data. We propose a framework for generating synthetic data and analyze the complexity of our algorithm. Additionally, the empirical results of the convergence and the robustness of our algorithm are also presented. These results demonstrate the effectiveness and efficiency of the proposed algorithm, comparing with traditional methods. Experimental results on real-world data sets further validate that our algorithm can be used to solve practical problems.
Description: 
URI: http://localhost/handle/Hannan/148233
http://localhost/handle/Hannan/617648
ISSN: 1041-4347
volume: 28
issue: 6
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7393856.pdf1.31 MBAdobe PDFThumbnail
Preview File
Title: Learning Mixtures of Markov Chains from Aggregate Data with Structural Constraints
Authors: Dixin Luo;Hongteng Xu;Yi Zhen;Bistra Dilkina;Hongyuan Zha;Xiaokang Yang;Wenjun Zhang
subject: aggregate data|prediction|simulation|structural constraints|pairwise sparsity|Mixtures of Markov chains
Year: 2016
Publisher: IEEE
Abstract: Statistical models based on Markov chains, especially mixtures of Markov chains, have recently been studied and demonstrated to be effective in various data mining applications such as tourist flow analysis, animal migration modeling, and transportation administration. Nevertheless, the research so far has mainly focused on analyzing data at individual levels. Due to security and privacy reasons, however, the observations in practice usually consist of coarse-grained statistics of individual data, a.k.a.</italic> aggregate data, rendering learning mixtures of Markov chains an even more challenging problem. In this work, we show that this challenging problem, although intractable in its original form, can be solved approximately by posing structural constraints on the transition matrices. The proposed structural constraints include specifying active state sets corresponding to the chains and adding a pairwise sparse regularization term on transition matrices. Based on these two structural constraints, we propose a constrained least-squares method to learn mixtures of Markov chains. We further develop a novel iterative algorithm that decomposes the overall problem into a set of convex subproblems and solves each subproblem efficiently, making it possible to effectively learn mixtures of Markov chains from aggregate data. We propose a framework for generating synthetic data and analyze the complexity of our algorithm. Additionally, the empirical results of the convergence and the robustness of our algorithm are also presented. These results demonstrate the effectiveness and efficiency of the proposed algorithm, comparing with traditional methods. Experimental results on real-world data sets further validate that our algorithm can be used to solve practical problems.
Description: 
URI: http://localhost/handle/Hannan/148233
http://localhost/handle/Hannan/617648
ISSN: 1041-4347
volume: 28
issue: 6
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7393856.pdf1.31 MBAdobe PDFThumbnail
Preview File
Title: Learning Mixtures of Markov Chains from Aggregate Data with Structural Constraints
Authors: Dixin Luo;Hongteng Xu;Yi Zhen;Bistra Dilkina;Hongyuan Zha;Xiaokang Yang;Wenjun Zhang
subject: aggregate data|prediction|simulation|structural constraints|pairwise sparsity|Mixtures of Markov chains
Year: 2016
Publisher: IEEE
Abstract: Statistical models based on Markov chains, especially mixtures of Markov chains, have recently been studied and demonstrated to be effective in various data mining applications such as tourist flow analysis, animal migration modeling, and transportation administration. Nevertheless, the research so far has mainly focused on analyzing data at individual levels. Due to security and privacy reasons, however, the observations in practice usually consist of coarse-grained statistics of individual data, a.k.a.</italic> aggregate data, rendering learning mixtures of Markov chains an even more challenging problem. In this work, we show that this challenging problem, although intractable in its original form, can be solved approximately by posing structural constraints on the transition matrices. The proposed structural constraints include specifying active state sets corresponding to the chains and adding a pairwise sparse regularization term on transition matrices. Based on these two structural constraints, we propose a constrained least-squares method to learn mixtures of Markov chains. We further develop a novel iterative algorithm that decomposes the overall problem into a set of convex subproblems and solves each subproblem efficiently, making it possible to effectively learn mixtures of Markov chains from aggregate data. We propose a framework for generating synthetic data and analyze the complexity of our algorithm. Additionally, the empirical results of the convergence and the robustness of our algorithm are also presented. These results demonstrate the effectiveness and efficiency of the proposed algorithm, comparing with traditional methods. Experimental results on real-world data sets further validate that our algorithm can be used to solve practical problems.
Description: 
URI: http://localhost/handle/Hannan/148233
http://localhost/handle/Hannan/617648
ISSN: 1041-4347
volume: 28
issue: 6
Appears in Collections:2016

Files in This Item:
File Description SizeFormat 
7393856.pdf1.31 MBAdobe PDFThumbnail
Preview File