SpringerLink
Log in

Quantifying predictability of sequential recommendation via logical constraints

  • Research Article
  • Published:
Frontiers of Computer Science Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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

    Article  MathSciNet  MATH  Google Scholar 

  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: https://doi.org/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, **g 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

    Article  Google Scholar 

  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, **e 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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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

    Chapter  MATH  Google Scholar 

  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

    Article  MathSciNet  MATH  Google Scholar 

  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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  25. Ren W, Li Y, Chen S, ** 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, ** 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

    Article  Google Scholar 

  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

    Article  Google Scholar 

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

    Article  Google Scholar 

  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

    Article  Google Scholar 

  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): 331–390

    Article  Google Scholar 

  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

Download references

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).

Author information

Authors and Affiliations

  1. School of Computer Science, Northwestern Polytechnical University, **’an, 710129, China

    En Xu, Zhiwen Yu, Nuo Li, Helei Cui & Bin Guo

  2. School of Computer Science and Engineering, University of New South Wales, Sydney, NSW, 2052, Australia

    Lina Yao

Authors
  1. En Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhiwen Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nuo Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Helei Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Lina Yao
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Bin Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhiwen Yu.

Additional information

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.

Electronic supplementary material

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, E., Yu, Z., Li, N. et al. Quantifying predictability of sequential recommendation via logical constraints. Front. Comput. Sci. 17, 175612 (2023). https://doi.org/10.1007/s11704-022-2223-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11704-022-2223-1

Keywords

Search

Navigation