research-article

Linear Additive Markov Processes

Authors:

Tamás Sarlós,

Andrew TomkinsAuthors Info & Claims

WWW '17: Proceedings of the 26th International Conference on World Wide Web

Pages 411 - 419

https://doi.org/10.1145/3038912.3052644

Published: 03 April 2017 Publication History

Abstract

We introduce LAMP: the Linear Additive Markov Process. Transitions in LAMP may be influenced by states visited in the distant history of the process, but unlike higher-order Markov processes, LAMP retains an efficient parameterization. LAMP also allows the specific dependence on history to be learned efficiently from data.

We characterize some theoretical properties of LAMP, including its steady-state and mixing time. We then give an algorithm based on alternating minimization to learn LAMP models from data.

Finally, we perform a series of real-world experiments to show that LAMP is more powerful than first-order Markov processes, and even holds its own against deep sequential models (LSTMs) with a negligible increase in parameter complexity.

References

[1]

P. Boldi, F. Bonchi, C. Castillo, D. Donato, A. Gionis, and S. Vigna. The query-flow graph: model and applications. In CIKM, pages 609--618, 2008.

Digital Library

[2]

J. Borges and M. Levene. Evaluating variable-length Markov chain models for analysis of user Web navigation sessions. TKDE, 19(4):441--452, 2007.

Digital Library

[3]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[4]

P. Buhlmann and A. Wyner. Variable length Markov chains. Annals of Statistics, pages 480--513, 1999.

[5]

H. Cao, D. Jiang, J. Pei, E. Chen, and H. Li. Towards context-aware search by learning a very large variable length hidden Markov model from search logs. In WWW, pages 191--200, 2009.

Digital Library

[6]

F. Chierichetti, R. Kumar, P. Raghavan, and T. Sarlós. Are Web users really Markovian? In WWW, pages 609--618, 2012.

Digital Library

[7]

N. Craswell and M. Szummer. Random walks on the click graph. In SIGIR, pages 239--246, 2007.

Digital Library

[8]

D. Dubashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2012.

Digital Library

[9]

J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the l<sub>1</sub>-ball for learning in high dimensions. In ICML, pages 272--279, 2008.

Digital Library

[10]

R. Fagin, A. R. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, M. Sudan, and A. Tomkins. Random walks with "back buttons". In STOC, pages 484--493, 2000.

Digital Library

[11]

C. Herrada. Music Recommendation and Discovery in the Long Tail. PhD thesis, Universitat Pompeu Fabra, 2009.

[12]

S. Hochreiter and J. Schmidhuber. Long short-term memory. In Neural Computation, pages 1735--1780, 1997.

Digital Library

[13]

S. Karlin and H. M. Taylor. A First Course in Stochastic Processes. Academic Press, 1975.

[14]

R. Kneser and H. Ney. Improved backing-off for $m$-gram language modeling. In ICASSP, pages 181--184, 1995.

[15]

R. Kumar, A. Tomkins, S. Vassilvitskii, and E. Vee. Inverting a steady-state. In WSDM, pages 359--368, 2015.

Digital Library

[16]

A. A. Markov. Extension of the limit theorems of probability theory to a sum of variables connected in a chain. Appendix B, Dynamic Probabilistic Systems: Markov Chains, 1, 1971.

[17]

S. Melnyk, O. Usatenko, and V. Yampol'skii. Memory functions of the additive Markov chains: applications to complex dynamic systems. Physica A: Statistical Mechanics and its Applications, 361(2):405--415, 2006.

[18]

J. Nocedal and S. Wright. Numerical Optimization. Springer Science & Business Media, 2006.

[19]

L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Technical report, InfoLab, Stanford University, 1999.

[20]

R. Pemantle. Vertex-reinforced random walk. Probability Theory and Related Fields, 92(1):117--136, 1992.

[21]

P. L. T. Pirolli and J. E. Pitkow. Distributions of surfers' paths through the World Wide Web: Empirical characterizations. World Wide Web, 2(1--2):29--45, 1999.

Digital Library

[22]

S. I. Resnick. Adventures in Stochastic Processes. Birkhauser, 2002.

Digital Library

[23]

J. Rissanen. A universal data compression system. IEEE TOIT, 29(5):656--664, 1983.

Digital Library

[24]

R. R. Sarukkai. Link prediction and path analysis using Markov chains. Computer Networks, 33(1--6):377--386, 2000.

Digital Library

[25]

M. H. Schulz, D. Weese, T. Rausch, A. Döring, K. Reinert, and M. Vingron. Fast and adaptive variable order Markov chain construction. In Algorithms in Bioinformatics, pages 306--317. Springer, 2008.

Digital Library

[26]

R. Sen and M. Hansen. Predicting Web users' next access based on log data. Journal of Computational and Graphical Statistics, 12(1):143--155, 2003.

[27]

P. Singer, D. Helic, A. Hotho, and M. Strohmaier. HypTrails: A Bayesian approach for comparing hypotheses about human trails on the Web. In WWW, pages 1003--1013, 2015.

Digital Library

[28]

O. V. Usatenko. Random Finite-Valued Dynamical Systems: Additive Markov Chain Approach. Cambridge Scientific Publishers, 2009.

[29]

O. V. Usatenko, V. A. Yampol'skii, K. E. Kechedzhy, and S. S. Mel'nyk. Symbolic stochastic dynamical systems viewed as binary n-step Markov chains. Physical Review E, 68(6):061107, 2003.

[30]

A. Wald. On cumulative sums of random variables. Annals of Mathematical Statistics, 15(3):283--296, 1944.

[31]

R. West and J. Leskovec. Human wayfinding in information networks. In WWW, pages 619--628, 2012.

Digital Library

[32]

R. West, J. Pineau, and D. Precup. Wikispeedia: An online game for inferring semantic distances between concepts. In IJCAI, pages 1598--1603, 2009.

Digital Library

[33]

W. Zaremba, I. Sutskever, and O. Vinyals. Recurrent neural network regularization. CoRR, abs/1409.2329, 2014.

[34]

J.-D. Zhang and C.-Y. Chow. Spatiotemporal sequential influence modeling for location recommendations: A gravity-based approach. TIST, 7(1):11:1--11:25, 2015.

Digital Library

[35]

J.-D. Zhang, C.-Y. Chow, and Y. Li. Lore: Exploiting sequential influence for location recommendations. In SIGSPATIAL, pages 103--112, 2014.

Digital Library

[36]

I. Zukerman, D. W. Albrecht, and A. E. Nicholson. Predicting users' requests on the WWW. In UM, pages 275--284, 1999.

Digital Library

Cited By

Smart BRoughan MMitchell L(2024)The entropy rate of Linear Additive Markov ProcessesPLOS ONE10.1371/journal.pone.029507419:4(e0295074)Online publication date: 5-Apr-2024
https://doi.org/10.1371/journal.pone.0295074
Kohjima M(2022)Mixture of Linear Additive Markov Processes: A Probabilistic Model for Joint Clustering and History-Dependent Transition Estimation2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)10.1109/WI-IAT55865.2022.00027(127-134)Online publication date: Nov-2022
https://doi.org/10.1109/WI-IAT55865.2022.00027
Kohjima M(2022)Polya Decision Processes: A New History-Dependent Framework for Reinforcement Learning2022 IEEE 61st Conference on Decision and Control (CDC)10.1109/CDC51059.2022.9992504(4884-4891)Online publication date: 6-Dec-2022
https://doi.org/10.1109/CDC51059.2022.9992504
Show More Cited By

Index Terms

Linear Additive Markov Processes
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random walks and Markov chains

Recommendations

Genetic Algorithms as an Alternative Method of Parameter Estimation and Finding Most Likely Sequences of States of Hidden Markov Chains for HMMs and Hybrid HMM/ANN Models

In this paper genetic algorithms are used in estimation and decoding processes of a Hidden Markov Model (HMM) and a hybrid HMM/ANN model with conditional binomial distributions. The hybrid model combines a hidden Markov chain with a perceptron which is ...
Genetic Algorithms as an Alternative Method of Parameter Estimation and Finding Most Likely Sequences of States of Hidden Markov Chains for HMMs and Hybrid HMM/ANN Models

In this paper genetic algorithms are used in estimation and decoding processes of a Hidden Markov Model (HMM) and a hybrid HMM/ANN model with conditional binomial distributions. The hybrid model combines a hidden Markov chain with a perceptron which is ...
Upper Bound Kullback&#x2013;Leibler Divergence for Transient Hidden Markov Models

This paper reports an upper bound for the Kullback-Leibler divergence (KLD) for a general family of transient hidden Markov models (HMMs). An upper bound KLD (UBKLD) expression for Gaussian mixtures models (GMMs) is presented which is generalized for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '17: Proceedings of the 26th International Conference on World Wide Web

April 2017

1678 pages

ISBN:9781450349130

General Chairs:
Rick Barrett
W3Events
,
Rick Cummings
Murdoch University
,
Program Chairs:
Eugene Agichtein
Emory University
,
Evgeniy Gabrilovich
Google Research

Copyright © 2017 Copyright is held by the International World Wide Web Conference Committee (IW3C2).

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 03 April 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

WWW '17

Sponsor:

IW3C2

WWW '17: 26th International World Wide Web Conference

April 3 - 7, 2017

Perth, Australia

Acceptance Rates

WWW '17 Paper Acceptance Rate 164 of 966 submissions, 17%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
213
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Smart BRoughan MMitchell L(2024)The entropy rate of Linear Additive Markov ProcessesPLOS ONE10.1371/journal.pone.029507419:4(e0295074)Online publication date: 5-Apr-2024
https://doi.org/10.1371/journal.pone.0295074
Kohjima M(2022)Mixture of Linear Additive Markov Processes: A Probabilistic Model for Joint Clustering and History-Dependent Transition Estimation2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)10.1109/WI-IAT55865.2022.00027(127-134)Online publication date: Nov-2022
https://doi.org/10.1109/WI-IAT55865.2022.00027
Kohjima M(2022)Polya Decision Processes: A New History-Dependent Framework for Reinforcement Learning2022 IEEE 61st Conference on Decision and Control (CDC)10.1109/CDC51059.2022.9992504(4884-4891)Online publication date: 6-Dec-2022
https://doi.org/10.1109/CDC51059.2022.9992504
FASINO DTONETTO ATUDISCO F(2022)Hitting times for second-order random walksEuropean Journal of Applied Mathematics10.1017/S0956792522000213(1-25)Online publication date: 4-Jul-2022
https://doi.org/10.1017/S0956792522000213
Wang HLi YJin DHan Z(2021)Attentional Markov Model for Human Mobility PredictionIEEE Journal on Selected Areas in Communications10.1109/JSAC.2021.307849939:7(2213-2225)Online publication date: Jul-2021
https://doi.org/10.1109/JSAC.2021.3078499
Vekslerchik VMelnik SPritula GUsatenko O(2019)CORRELATION FUNCTIONS FOR LINEAR ADDITIVE MARKOV CHAINS OF HIGHER ORDERSRADIOFIZIKA I ELEKTRONIKA10.15407/rej2019.01.04724:1(47-57)Online publication date: 5-Apr-2019
https://doi.org/10.15407/rej2019.01.047
Duong QRamampiaro HNØrvåg K(2018)Applying temporal dependence to detect changes in streaming dataApplied Intelligence10.1007/s10489-018-1254-748:12(4805-4823)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10489-018-1254-7
Wu TGleich DMatwin SYu SFarooq F(2017)Retrospective Higher-Order Markov Processes for User TrailsProceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining10.1145/3097983.3098127(1185-1194)Online publication date: 13-Aug-2017
https://dl.acm.org/doi/10.1145/3097983.3098127

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents