# Retrospective Higher-Order Markov Processes for User Trails

**Authors:** Tao Wu, David Gleich  
**arXiv:** [1704.05982](https://arxiv.org/abs/1704.05982)  
**Date:** 2017-04-20  
**Summary page:** https://www.summarizepaper.com/en/paper/1704.05982v1/

## Key points

- Authors Tao Wu and David Gleich introduce the retrospective higher-order Markov process (RHOMP) to predict user behavior based on information trails.
- RHOMP overcomes limitations of traditional methods like first-order and higher-order Markov chains.
- First-order Markov chains lack accuracy in historical context, while higher-order chains suffer from overfitting due to a large number of parameters.
- RHOMP reduces parameters linearly with the order of the chain and can be applied effectively to large state spaces.
- Structuring the higher-order chain in a specific way improves prediction accuracy by efficiently utilizing historical states without overfitting.
- The authors demonstrate how to estimate a RHOMP from data and showcase its effectiveness across various real-world datasets including geolocation data, review sequences, and business locations.
- In comparative experiments, RHOMP consistently outperforms traditional higher-order Markov chains, Kneser-Ney regularization techniques, and tensor factorizations in prediction accuracy.
- This research offers a promising approach for modeling user trails that balances complexity with predictive power, providing insights for guiding recommendations and prefetching actions based on user behavior patterns.

## Summary

In their paper titled "Retrospective Higher-Order Markov Processes for User Trails," authors Tao Wu and David Gleich address the challenge of predicting user behavior based on information trails formed while browsing the web, checking in with geolocation data, rating items, or consuming media. They introduce a novel approach called the retrospective higher-order Markov process (RHOMP) to overcome limitations of traditional methods such as first-order and higher-order Markov chains. First-order Markov chains are easy to estimate but often lack accuracy when considering historical context. On the other hand, higher-order Markov chains suffer from overfitting due to a large number of parameters. The RHOMP model is a specialized version of a higher-order Markov chain that reduces the number of parameters linearly with the order of the chain and can be effectively applied to large state spaces. By structuring the higher-order chain in a specific way, RHOMPs improve prediction accuracy by efficiently utilizing historical states without risking overfitting. The authors demonstrate how to estimate a RHOMP from data and showcase its effectiveness across various real-world datasets including geolocation data, review sequences, and business locations. In comparative experiments, the RHOMP model consistently outperforms traditional higher-order Markov chains, Kneser-Ney regularization techniques, and tensor factorizations in terms of prediction accuracy. This research introduces a promising approach for modeling user trails that balances complexity with predictive power, offering valuable insights for guiding recommendations and prefetching actions based on user behavior patterns.