Quantifying predictability of sequential recommendation via logical constraints

Abstract

The sequential recommendation is a compelling technology for predicting users’ next interaction via their historical behaviors. Prior studies have proposed various methods to optimize the recommendation accuracy on different datasets but have not yet explored the intrinsic predictability of sequential recommendation. To this end, we consider applying the popular predictability theory of human movement behavior to this recommendation context. Still, it would incur serious bias in the next moment measurement of the candidate set size, resulting in inaccurate predictability. Therefore, determining the size of the candidate set is the key to quantifying the predictability of sequential recommendations. Here, different from the traditional approach that utilizes topological constraints, we first propose a method to learn inter-item associations from historical behaviors to restrict the size via logical constraints. Then, we extend it by 10 excellent recommendation algorithms to learn deeper associations between user behavior. Our two methods show significant improvement over existing methods in scenarios that deal with few repeated behaviors and large sets of behaviors. Finally, a prediction rate between 64% and 80% has been obtained by testing on five classical datasets in three domains of the recommender system. This provides a guideline to optimize the recommendation algorithm for a given dataset.

Graphical abstract

Keywords

sequential recommendation / information theory / predictability

References

[1] Wang S, Hu L, Wang Y, Cao L, Sheng Q Z, Orgun M. Sequential recommender systems: challenges, progress and prospects. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 6332–6338

[2] Hidasi B, Karatzoglou A, Baltrunas L, Tikk D. Session-based recommendations with recurrent neural networks. In: Proceedings of the 4th International Conference on Learning Representations. 2016

[3] Li Z, Zhao H, Liu Q, Huang Z, Mei T, Chen E. Learning from history and present: next-item recommendation via discriminatively exploiting user behaviors. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018, 1734–1743

[4] Song C, Qu Z, Blumm N, Barabási A L . Limits of predictability in human mobility. Science, 2010, 327( 5968): 1018–1021

[5] Smith G, Wieser R, Goulding J, Barrack D. A refined limit on the predictability of human mobility. In: Proceedings of 2014 IEEE International Conference on Pervasive Computing and Communications. 2014, 88–94

[6] Yap G E, Li X L, Yu P S. Effective next-items recommendation via personalized sequential pattern mining. In: Proceedings of the 17th International Conference on Database Systems for Advanced Applications. 2012, 48–64

[7] Ren S, Guo B, Li K, Wang Q, Yu Z, Cao L. CoupledMUTS: coupled multivariate utility time series representation and prediction. IEEE Internet of Things Journal, 2022,

[8] Garcin F, Dimitrakakis C, Faltings B. Personalized news recommendation with context trees. In: Proceedings of the 7th ACM Conference on Recommender Systems. 2013, 105–112

[9] Wu C Y, Ahmed A, Beutel A, Smola A J, Jing H. Recurrent recommender networks. In: Proceedings of the 10th ACM International Conference on Web Search and Data Mining. 2017, 495–503

[10] Xu E, Yu Z, Guo B, Cui H . Core interest network for click-through rate prediction. ACM Transactions on Knowledge Discovery from Data, 2021, 15( 2): 23

[11] Tang J, Wang K. Personalized Top-N sequential recommendation via convolutional sequence embedding. In: Proceedings of the 11th ACM International Conference on Web Search and Data Mining. 2018, 565–573

[12] Wu S, Tang Y, Zhu Y, Wang L, Xie X, Tan T. Session-based recommendation with graph neural networks. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 346–353

[13] Takaguchi T, Nakamura M, Sato N, Yano K, Masuda N . Predictability of conversation partners. Physical Review X, 2011, 1( 1): 011008

[14] Baumann P, Santini S. On the use of instantaneous entropy to measure the momentary predictability of human mobility. In: Proceedings of the 14th IEEE Workshop on Signal Processing Advances in Wireless Communications. 2013, 535–539

[15] McInerney J, Stein S, Rogers A, Jennings N R. Exploring periods of low predictability in daily life mobility. In: Proceedings of Mobile Data Challenge by Nokia. 2012

[16] Krumme C, Llorente A, Cebrian M, Pentland A, Moro E . The predictability of consumer visitation patterns. Scientific Reports, 2013, 3: 1645

[17] Nguyen T, Rokicki M. On the predictability of non-CGM diabetes data for personalized recommendation. In: Proceedings of 2018 CIKM Workshops Co-located with the 27th ACM International Conference on Information and Knowledge Management. 2018

[18] Zhang P, Xue L, Zeng A . Predictability of diffusion-based recommender systems. Knowledge-Based Systems, 2019, 185: 104921

[19] Järv P. Predictability limits in session-based next item recommendation. In: Proceedings of the 13th ACM Conference on Recommender Systems. 2019, 146–150

[20] Ben-Naim A. Elements of information theory. In: Ben-Naim A, ed. A Farewell To Entropy: Statistical Thermodynamics Based on Information. Singapore: World Scientific, 2008

[21] Kontoyiannis I, Algoet P H, Suhov Y M, Wyner A J . Nonparametric entropy estimation for stationary processes and random fields, with applications to English text. IEEE Transactions on Information Theory, 1998, 44( 3): 1319–1327

[22] Zhao Z D, Yang Z, Zhang Z, Zhou T, Huang Z G, Lai Y C . Emergence of scaling in human-interest dynamics. Scientific Reports, 2013, 3: 3472

[23] Zhang L, Liu Y, Wu Y, Xiao J . Analysis of the origin of predictability in human communications. Physica A: Statistical Mechanics and its Applications, 2014, 393: 513–518

[24] Wang J, Mao Y, Li J, Xiong Z, Wang W X . Predictability of road traffic and congestion in urban areas. PLoS One, 2015, 10( 4): e0121825

[25] Ren W, Li Y, Chen S, Jin D, Su L. Potential predictability of vehicles’ visiting duration in different areas for large scale urban environment. In: Proceedings of 2013 IEEE Wireless Communications and Networking Conference. 2013, 1674–1678

[26] Zhao K, Khryashchev D, Freire J, Silva C, Vo H. Predicting taxi demand at high spatial resolution: approaching the limit of predictability. In: Proceedings of 2016 IEEE International Conference on Big Data. 2016, 833–842

[27] Li Y, Jin D, Hui P, Wang Z, Chen S . Limits of predictability for large-scale urban vehicular mobility. IEEE Transactions on Intelligent Transportation Systems, 2014, 15( 6): 2671–2682

[28] Xu T, Xu X, Hu Y, Li X . An entropy-based approach for evaluating travel time predictability based on vehicle trajectory data. Entropy, 2017, 19( 4): 165

[29] Chen Y Z, Huang Z G, Xu S, Lai Y C . Spatiotemporal patterns and predictability of cyberattacks. PLoS One, 2015, 10( 5): e0124472

[30] Fiedor P. Frequency effects on predictability of stock returns. In: Proceedings of 2014 IEEE Conference on Computational Intelligence for Financial Engineering & Economics. 2014, 247–254

[31] Dahlem D, Maniloff D, Ratti C . Predictability bounds of electronic health records. Scientific Reports, 2015, 5: 11865

[32] Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. In: Proceedings of the 1st International Conference on Learning Representations. 2013

[33] Ludewig M, Jannach D. Evaluation of session-based recommendation algorithms. User Modeling and User-Adapted Interaction, 2018, 28(4–5): 4–5

[34] Dacrema M F, Cremonesi P, Jannach D. Are we really making much progress? A worrying analysis of recent neural recommendation approaches. In: Proceedings of the 13th ACM Conference on Recommender Systems. 2019, 101–109

RIGHTS & PERMISSIONS

Higher Education Press