×

Recovering Markov models from closed-loop data. (English) Zbl 1415.93243

Summary: Situations in which recommender systems are used to augment decision making are becoming prevalent in many application domains. Almost always, these prediction tools (recommenders) are created with a view to affecting behavioural change. Clearly, successful applications actuating behavioural change, affect the original model underpinning the predictor, leading to an inconsistency. This feedback loop is often not considered in standard machine learning techniques which rely upon machine learning/statistical learning machinery. The objective of this paper is to develop tools that recover unbiased user models in the presence of recommenders. More specifically, we assume that we observe a time series which is a trajectory of a Markov chain \(\boldsymbol{R}\) modulated by another Markov chain \(\boldsymbol{S}\), i.e. the transition matrix of \(\boldsymbol{R}\) is unknown and depends on the current state of \(\boldsymbol{S}\). The transition matrix of the latter is also unknown. In other words, at each time instant, \(\boldsymbol{S}\) selects a transition matrix for \(\boldsymbol{R}\) within a given set which consists of known and unknown matrices. The state of \(\boldsymbol{S}\), in turn, depends on the current state of \(\boldsymbol{R}\) thus introducing a feedback loop. We propose an expectation-maximisation (EM) type algorithm, which estimates the transition matrices of \(\boldsymbol{S}\) and \(\boldsymbol{R}\). Experimental results are given to demonstrate the efficacy of the approach.

MSC:

93E03 Stochastic systems in control theory (general)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
93B52 Feedback control
68T05 Learning and adaptive systems in artificial intelligence

References:

[1] Angrist, J.; Pischke, J., Mostly harmless econometrics: An empiricist’s companion (2008), Princeton University Press · Zbl 1159.62090
[2] Baum, Y.; Petri, T.; Soules, G.; Weiss, N., A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains, The Annals of Mathematical Statistics, 41, 164-171 (1970) · Zbl 0188.49603
[3] Bertsekas, D. P., Nonlinear programming (1999), Athena Scientific Belmont · Zbl 1015.90077
[4] Blackwell, D.; Koopmans, L., On the identifiability problem for functions of finite Markov chains, The Annals of Mathematical Statistics, 1011-1015 (1957) · Zbl 0080.34901
[5] Bottou, L.; Peters, J.; Quiñonero Candela, J.; Charles, D. X.; Chickering, D. M.; Portugaly, E., Counterfactual reasoning and learning systems: The example of computational advertising, Journal of Machine Learning Research, 14, 3207-3260 (2013), URL http://dl.acm.org/citation.cfm?id=25677092567766 · Zbl 1318.62206
[6] Cosley, D.; Lam, S. K.; Albert, I.; Konstan, J. A.; Riedl, J., Is seeing believing? How recommender system interfaces affect users’ opinions, (Proceedings of the SIGCHI conference on Human factors in computing systems (2003), ACM), 585-592
[7] Costa, O. L.V.; Fragoso, M. D.; Marques, R. P., Discrete-time Markov jump linear systems (2006), Springer Science & Business Media · Zbl 1081.93001
[8] Crisostomi, E.; Shorten, R.; Wirth, F., Smart cities: A golden age for control theory? [industry perspective], IEEE Technology and Society Magazine, 35, 23-24 (2016)
[9] Ephraim, Y.; Roberts, W. J.J., An EM algorithm for Markov modulated Markov processes, IEEE Transactions on Signal Processing, 57, 463-470 (2009) · Zbl 1391.62155
[10] Epperlein, J. P.; Monteil, J.; Liu, M.; Gu, Y.; Zhuk, S.; Shorten, R., Bayesian classifier for route prediction with Markov chains, IEEE International Conference on Intelligent Transportation Systems (2018), Preprint availablee arXiv:1808.10705
[11] Epperlein, J., Shorten, R., & Zhuk, S. (2017). Learning Markov models from closed loop data-sets. ArXiv e-prints arXiv:1706.06359v2; Epperlein, J., Shorten, R., & Zhuk, S. (2017). Learning Markov models from closed loop data-sets. ArXiv e-prints arXiv:1706.06359v2
[12] Forssell, U.; Ljung, L., Closed-loop identification revisited, Automatica, 35, 1215-1241 (1999), URL http://www.sciencedirect.com/science/article/pii/S0005109899000229 · Zbl 0934.93019
[13] Gilbert, E., On the identifiability problem for functions of finite Markov chains, The Annals of Mathematical Statistics, 30, 688-697 (1959) · Zbl 0089.34503
[14] Jacobs, R. A.; Jordan, M. I.; Nowlan, S. J.; Hinton, G. E., Adaptive mixtures of local experts, Neural Computation, 3, 79-87 (1991)
[15] Krumm, J. (2008). A Markov model for driver turn prediction. Technical Report. SAE Technical Paper.; Krumm, J. (2008). A Markov model for driver turn prediction. Technical Report. SAE Technical Paper.
[16] Lange, T.; Rahbek, A., An introduction to regime switching time series models, (Handbook of financial time series (2009), Springer) · Zbl 1178.91161
[17] Lassoued, Y.; Monteil, J.; Gu, Y.; Russo, G.; Shorten, R.; Mevissen, M., Hidden Markov model for route and destination prediction, (IEEE international conference on intelligent transportation systems (2017))
[18] Lazer, D.; Kennedy, R.; King, G.; Vespignani, A., The parable of Google Flu: Traps in big data analysis, Science, 343, 1203-1205 (2014)
[19] Levin, D. A.; Peres, Y.; Wilmer, E. L., Markov chains and mixing times (2009), American Mathematical Soc. · Zbl 1160.60001
[20] Loram, I. D.; Gollee, H.; Lakie, M.; Gawthrop, P. J., Human control of an inverted pendulum: Is continuous control necessary? Is intermittent control effective? Is intermittent control physiological?, The Journal of Physiology, 589, 307-324 (2011)
[21] Meila, M.; Jordan, M. I., Markov mixtures of experts, (Murray-Smith, R.; Johanssen, T. A., Multiple model approaches to nonlinear modelling and control (1996), Taylor and Francis)
[22] Norton, J., (An introduction to identification. An introduction to identification, Dover books on electrical engineering series (2009), Dover Publications), URL https://books.google.ie/books?id=eyHC7751n_cC
[23] Pearl, J., Causality: Models, reasoning, and inference (2000), New York: Cambridge University Press · Zbl 0959.68116
[24] Petrie, T., Probabilistic functions of finite state Markov chains, The Annals of Mathematical Statistics, 40, 97-115 (1969) · Zbl 0181.21201
[25] Rabiner, L. R., A tutorial on hidden Markov models and selected applications in speech recognition, Proceedings of the IEEE, 77, 257-286 (1989)
[26] Schlote, A.; Chen, B.; Shorten, R., On closed loop bicycle availability prediction, IEEE Transactions on Intelligent Transportation Systems, 16, 1449-1555 (2015)
[27] Schlote, A.; King, C.; Crisostomi, E.; Shorten, R., Delay-tolerant stochastic algorithms for parking space assignment, IEEE Transactions on Intelligent Transportation Systems, 15, 1922-1935 (2014)
[28] Simmons, R.; Browning, B.; Zhang, Y.; Sadekar, V., Learning to predict driver route and destination intent, (2006 IEEE intelligent transportation systems conference (2006)), 127-132
[29] Sinha, A.; Gleich, D.; Ramani, K., Deconvolving feedback loops in recommender systems, (Proceedings of NIPS (2016)), ArXiv:1703.01049
[30] Söderström, T.; Stoica, P., (System identification. System identification, Prentice hall international series in systems and control engineering (1989), Prentice Hall), URL https://books.google.ie/books?id=X_xQAAAAMAAJ · Zbl 0695.93108
[31] Stock, James H.; Trebbi, F., Retrospectives: Who invented instrumental variable regression?, Journal of Economic Perspectives, 17, 177-194 (2003)
[32] Van Den Hof, P. M.; Schrama, R. J., Identification and control - closed-loop issues, Automatica, 31, 1751-1770 (1995) · Zbl 0846.93020
[33] Varian, H. R., Causal inference in economics and marketing, Proceedings of the National Academy of Sciences of the United States of America, 7310-7315 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.