Consistently Estimating Markov Chains with Noisy Aggregate Data

Garrett Bernstein, Daniel Sheldon
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:1142-1150, 2016.

Abstract

We address the problem of estimating the parameters of a time-homogeneous Markov chain given only noisy, aggregate data. This arises when a population of individuals behave independently according to a Markov chain, but individual sample paths cannot be observed due to limitations of the observation process or the need to protect privacy. Instead, only population-level counts of the number of individuals in each state at each time step are available. When these counts are exact, a conditional least squares (CLS) estimator is known to be consistent and asymptotically normal. We initiate the study of method of moments estimators for this problem to handle the more realistic case when observations are additionally corrupted by noise. We show that CLS can be interpreted as a simple “plug-in” method of moments estimator. However, when observations are noisy, it is not consistent because it fails to account for additional variance introduced by the noise. We develop a new, simpler method of moments estimator that bypasses this problem and is consistent under noisy observations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-bernstein16, title = {Consistently Estimating Markov Chains with Noisy Aggregate Data}, author = {Bernstein, Garrett and Sheldon, Daniel}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {1142--1150}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/bernstein16.pdf}, url = {https://proceedings.mlr.press/v51/bernstein16.html}, abstract = {We address the problem of estimating the parameters of a time-homogeneous Markov chain given only noisy, aggregate data. This arises when a population of individuals behave independently according to a Markov chain, but individual sample paths cannot be observed due to limitations of the observation process or the need to protect privacy. Instead, only population-level counts of the number of individuals in each state at each time step are available. When these counts are exact, a conditional least squares (CLS) estimator is known to be consistent and asymptotically normal. We initiate the study of method of moments estimators for this problem to handle the more realistic case when observations are additionally corrupted by noise. We show that CLS can be interpreted as a simple “plug-in” method of moments estimator. However, when observations are noisy, it is not consistent because it fails to account for additional variance introduced by the noise. We develop a new, simpler method of moments estimator that bypasses this problem and is consistent under noisy observations.} }
Endnote
%0 Conference Paper %T Consistently Estimating Markov Chains with Noisy Aggregate Data %A Garrett Bernstein %A Daniel Sheldon %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-bernstein16 %I PMLR %P 1142--1150 %U https://proceedings.mlr.press/v51/bernstein16.html %V 51 %X We address the problem of estimating the parameters of a time-homogeneous Markov chain given only noisy, aggregate data. This arises when a population of individuals behave independently according to a Markov chain, but individual sample paths cannot be observed due to limitations of the observation process or the need to protect privacy. Instead, only population-level counts of the number of individuals in each state at each time step are available. When these counts are exact, a conditional least squares (CLS) estimator is known to be consistent and asymptotically normal. We initiate the study of method of moments estimators for this problem to handle the more realistic case when observations are additionally corrupted by noise. We show that CLS can be interpreted as a simple “plug-in” method of moments estimator. However, when observations are noisy, it is not consistent because it fails to account for additional variance introduced by the noise. We develop a new, simpler method of moments estimator that bypasses this problem and is consistent under noisy observations.
RIS
TY - CPAPER TI - Consistently Estimating Markov Chains with Noisy Aggregate Data AU - Garrett Bernstein AU - Daniel Sheldon BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-bernstein16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 1142 EP - 1150 L1 - http://proceedings.mlr.press/v51/bernstein16.pdf UR - https://proceedings.mlr.press/v51/bernstein16.html AB - We address the problem of estimating the parameters of a time-homogeneous Markov chain given only noisy, aggregate data. This arises when a population of individuals behave independently according to a Markov chain, but individual sample paths cannot be observed due to limitations of the observation process or the need to protect privacy. Instead, only population-level counts of the number of individuals in each state at each time step are available. When these counts are exact, a conditional least squares (CLS) estimator is known to be consistent and asymptotically normal. We initiate the study of method of moments estimators for this problem to handle the more realistic case when observations are additionally corrupted by noise. We show that CLS can be interpreted as a simple “plug-in” method of moments estimator. However, when observations are noisy, it is not consistent because it fails to account for additional variance introduced by the noise. We develop a new, simpler method of moments estimator that bypasses this problem and is consistent under noisy observations. ER -
APA
Bernstein, G. & Sheldon, D.. (2016). Consistently Estimating Markov Chains with Noisy Aggregate Data. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:1142-1150 Available from https://proceedings.mlr.press/v51/bernstein16.html.

Related Material