Quantifying predictability of sequential recommendation via logical constraints

doi:10.1007/s11704-022-2223-1

Front. Comput. Sci.

2023, Vol. 17

Issue (5) : 175612 https://doi.org/10.1007/s11704-022-2223-1

RESEARCH ARTICLE

Quantifying predictability of sequential recommendation via logical constraints

En XU¹, Zhiwen YU¹(

), Nuo LI¹, Helei CUI¹, Lina YAO², Bin GUO¹

¹. School of Computer Science, Northwestern Polytechnical University, Xi’an 710129, China
². School of Computer Science and Engineering, University of New South Wales, Sydney NSW 2052, Australia

Download: PDF(3055 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords sequential recommendation information theory predictability

Corresponding Author(s): Zhiwen YU

Just Accepted Date: 21 July 2022 Issue Date: 15 December 2022

Cite this article:

En XU,Zhiwen YU,Nuo LI, et al. Quantifying predictability of sequential recommendation via logical constraints[J]. Front. Comput. Sci., 2023, 17(5): 175612.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2223-1
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I5/175612

Fig.1 Schematic representation of the predictability of sequential recommendation. As new algorithms continue to be proposed, the accuracy of sequential recommendations continues to improve. Predictability is the potential maximum accuracy

Symbol	Meaning
$N s$	N calculated by method $M s$
$N r$	N calculated by method $M r$
$N l c$	N calculated by method $M l c$
$N b p a a$	N calculated by method $M b p a a$
$Π$	Predictability
$Π u p$	The upper bound of predictability

Tab.1 Meanings of main symbols used

Dataset	NOWP	RETLR	RSC15	CLEF	TMALL
$H P l$	10	10	10	10	10
$H P r$	0.96	0.86	0.77	0.90	0.73
$H P s$	0.65	0.8	0.59	0.67	0.56

Tab.2 Hyperparameters under five datasets

Method	$M l c$	$M b p a a$
Corresponding parameters	$H P l$	Length of user behavior
	$H P r$	Accuracy
	$H P s$	Predicted probability
	$N$	Top-N

Tab.3 The relationship between

M l c

and

M b p a a

Method	Advantages	Characteristics of usage scenarios	Example scenarios
$M s$	Simple Fast	Stable set of user behaviors New behaviors rarely appear	Movement behavior Calling behavior
$M r$	Simple Fast	Stable set of user behaviors New behaviors rarely appear	Movement behavior Calling behavior
$M l c$	Balancing usability and accuracy	Huge set of user behaviors Massive new behaviors constantly appear	Shopping Watching movies
$M b p a a$	Accurate		Shopping Watching movies

Tab.4 The comparison of our proposed methods

M l c

and

M b p a a

with existing methods

M s

and

M r

. We illustrate the advantages of each method and introduce the characteristics of the usage scenarios and typical scenarios

Tab.5 The detailed statistical characteristics of the five datasets

Fig.2 The similarity between items varies with the distance

Fig.3 Similarity distribution between historical behaviors and similarity distribution between random behaviors

Dataset	NOWPLAYING	RetailRocket	RSC15	CLEF	TMall
$N s$	9	4	20	22	17
$N r$	1	2	1	2	1
$N l c$	139	64	74	48	45
$N b p a a$	100	97	80	53	70

Tab.6 N calculated under five datasets

Fig.4 Accuracy results of 10 algorithms on 5 datasets. The horizontal coordinate represents the candidate set size

N

. The vertical coordinate represents the accuracy corresponding to Top-N

Fig.5 The

T o p - N b p a a

accuracy of the optimal algorithm and the predictability calculated by the four methods

1	S, Wang L, Hu Y, Wang L, Cao Q Z, Sheng M Orgun . Sequential recommender systems: challenges, progress and prospects. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 6332–6338
2	B, Hidasi A, Karatzoglou L, Baltrunas D Tikk . Session-based recommendations with recurrent neural networks. In: Proceedings of the 4th International Conference on Learning Representations. 2016
3	Z, Li H, Zhao Q, Liu Z, Huang T, Mei E Chen . 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	C, Song Z, Qu N, Blumm A L Barabási . Limits of predictability in human mobility. Science, 2010, 327( 5968): 1018–1021
5	G, Smith R, Wieser J, Goulding D Barrack . 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	G E, Yap X L, Li P S Yu . 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	S, Ren B, Guo K, Li Q, Wang Z, Yu L Cao . CoupledMUTS: coupled multivariate utility time series representation and prediction. IEEE Internet of Things Journal, 2022, doi:
8	F, Garcin C, Dimitrakakis B Faltings . Personalized news recommendation with context trees. In: Proceedings of the 7th ACM Conference on Recommender Systems. 2013, 105–112
9	C Y, Wu A, Ahmed A, Beutel A J, Smola H Jing . Recurrent recommender networks. In: Proceedings of the 10th ACM International Conference on Web Search and Data Mining. 2017, 495–503
10	E, Xu Z, Yu B, Guo H Cui . Core interest network for click-through rate prediction. ACM Transactions on Knowledge Discovery from Data, 2021, 15( 2): 23
11	J, Tang K Wang . 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	S, Wu Y, Tang Y, Zhu L, Wang X, Xie T Tan . Session-based recommendation with graph neural networks. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence. 2019, 346–353
13	T, Takaguchi M, Nakamura N, Sato K, Yano N Masuda . Predictability of conversation partners. Physical Review X, 2011, 1( 1): 011008
14	P, Baumann S Santini . 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	J, McInerney S, Stein A, Rogers N R Jennings . Exploring periods of low predictability in daily life mobility. In: Proceedings of Mobile Data Challenge by Nokia. 2012
16	C, Krumme A, Llorente M, Cebrian A, Pentland E Moro . The predictability of consumer visitation patterns. Scientific Reports, 2013, 3: 1645
17	T, Nguyen M Rokicki . 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	P, Zhang L, Xue A Zeng . Predictability of diffusion-based recommender systems. Knowledge-Based Systems, 2019, 185: 104921
19	P Järv . Predictability limits in session-based next item recommendation. In: Proceedings of the 13th ACM Conference on Recommender Systems. 2019, 146–150
20	A Ben-Naim . Elements of information theory. In: Ben-Naim A, ed. A Farewell To Entropy: Statistical Thermodynamics Based on Information. Singapore: World Scientific, 2008
21	I, Kontoyiannis P H, Algoet Y M, Suhov A J Wyner . 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	Z D, Zhao Z, Yang Z, Zhang T, Zhou Z G, Huang Y C Lai . Emergence of scaling in human-interest dynamics. Scientific Reports, 2013, 3: 3472
23	L, Zhang Y, Liu Y, Wu J Xiao . Analysis of the origin of predictability in human communications. Physica A: Statistical Mechanics and its Applications, 2014, 393: 513–518
24	J, Wang Y, Mao J, Li Z, Xiong W X Wang . Predictability of road traffic and congestion in urban areas. PLoS One, 2015, 10( 4): e0121825
25	W, Ren Y, Li S, Chen D, Jin L Su . 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	K, Zhao D, Khryashchev J, Freire C, Silva H Vo . 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	Y, Li D, Jin P, Hui Z, Wang S Chen . Limits of predictability for large-scale urban vehicular mobility. IEEE Transactions on Intelligent Transportation Systems, 2014, 15( 6): 2671–2682
28	T, Xu X, Xu Y, Hu X Li . An entropy-based approach for evaluating travel time predictability based on vehicle trajectory data. Entropy, 2017, 19( 4): 165
29	Y Z, Chen Z G, Huang S, Xu Y C Lai . Spatiotemporal patterns and predictability of cyberattacks. PLoS One, 2015, 10( 5): e0124472
30	P Fiedor . Frequency effects on predictability of stock returns. In: Proceedings of 2014 IEEE Conference on Computational Intelligence for Financial Engineering & Economics. 2014, 247–254
31	D, Dahlem D, Maniloff C Ratti . Predictability bounds of electronic health records. Scientific Reports, 2015, 5: 11865
32	T, Mikolov K, Chen G, Corrado J Dean . Efficient estimation of word representations in vector space. In: Proceedings of the 1st International Conference on Learning Representations. 2013
33	M, Ludewig D Jannach . Evaluation of session-based recommendation algorithms. User Modeling and User-Adapted Interaction, 2018, 28(4–5): 4–5
34	M F, Dacrema P, Cremonesi D Jannach . 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

[1]

FCS-22223-OF-EX_suppl_1

Download

[1]	Mingyue CHENG, Qi LIU, Wenyu ZHANG, Zhiding LIU, Hongke ZHAO, Enhong CHEN. A general tail item representation enhancement framework for sequential recommendation[J]. Front. Comput. Sci., 2024, 18(6): 186333-.

Viewed

Full text

Abstract

Cited

Shared

Discussed