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

En Xu received the bachelor’s degree from Northwestern Polytechnical University, China. He is currently a PhD student with the School of Computer Science, Northwestern Polytechnical University, China. His research interests include recommender system and predictability

Zhiwen Yu is currently a professor of the School of Computer Science, Northwestern Polytechnical University, China. He is the associate editor or editorial board of IEEE Transactions on Human-Machine Systems, IEEE Communications Magazine, ACM/Springer Personal and Ubiquitous Computing (PUC). His research interests include ubiquitous computing and mobile crowd sensing

Nuo Li received the bachelor’s degree from Northwestern Polytechnical University, China. At the moment, she is a PhD student with the School of Computer Science, Northwestern Polytechnical University, China. Her research interests include social and community intelligence and crowd knowledge transfer

Helei Cui is a professor from Northwestern Polytechnical University, China. He received his PhD degree in Computer Science from City University of Hong Kong (CityU), China in October 2018, under the supervision of Prof. Cong Wang (IEEE Fellow). Before that, he obtained MSc degree in Information Engineering from The Chinese University of Hong Kong (CUHK), China in November 2013 and BEng degree in Software Engineering from Northwestern Polytechnical University, China in July 2010. His research interests include industrial internet, secure crowdsensing, and distributed storage networks

Lina Yao is currently a scientia associate professor at School of Computer Science and Engineering, the University of New South Wales (UNSW), Australia. She received her PhD degree and Master degree both from The University of Adelaide ( UoA ), Australia in 2014 and 2010, respectively, and her Bachelor degree from Shandong University (SDU), China. Her research interest lies in data mining and machine learning applications with the focuses on internet of things analytics, recommender systems, human activity recognition, and brain computer interface

Bin Guo is a professor from Northwestern Polytechnical University, China. He received his PhD degree in computer science from Keio University, Japan in 2009 and then was a post-doc researcher at Institut TELECOM SudParis in France. His research interests include ubiquitous computing and mobile crowd sensing

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, doi: 10.1109/JIOT.2022.3185010

[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

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 61960206008, 62002294), and the National Science Fund for Distinguished Young Scholars (61725205).

RIGHTS & PERMISSIONS

2023 Higher Education Press