* [26] H. Wang, Y. Yu, and Q. Yuan, “Application of dijkstra algorithm in robot path-planning,” _2011 Second International Conference on Mechanic Automation and Control Engineering_ , Hohhot, China, 2011.
  * [27] M. Noto and H. Sato, “A method for the shortest path search by extended dijkstra algorithm,” _2000 IEEE International Conference on Systems, Man and Cybernetics_ , Nashville, USA, 2000.
  * [28] J. Yao, C. Lin, X. B. Xie, A. J. Wang, and C. Hung, “Path planning for virtual human motion using improved a* star algorithm,” _2010 Seventh International Conference on Information Technology: New Generations_ , Las Vegas, USA, 2010.
  * [29] C. B. Wang and et al., “Path planning of automated guided vehicles based on improved a-star algorithm,” _2015 IEEE International Conference on Information and Automation_ , Lijiang, China, 2015.
  * [30] H. R. Li, Q. C. Zhang, and D. B. Zhao, “Deep reinforcement learning-based automatic exploration for navigation in unknown environment,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 31, no. 6, pp. 2064 – 2076, June 2020.
  * [31] A. V. Savkin and H. Li, “Collision free navigation of a non-holonomic ground robot for search and building maps of unknown areas with obstacles,” _2016 35th Chinese Control Conference (CCC)_ , Chengdu, China, 2016.
  * [32] H. Teimoori and A. V. Savkin, “Equiangular navigation and guidance of a wheeled mobile robot using range-only measurements,” _2008 47th IEEE Conference on Decision and Control_ , Cancun, Mexico, 2008.
  * [33] A. V. Savkin and H. Li, “A collision-free area search and 3d map building algorithm for a ground mobile robot in unknown indoor environments,” _2017 IEEE International Conference on Robotics and Biomimetics (ROBIO)_ , Macau, China, 2017.
  * [34] H. Teimoori and A. V. Savkin, “A biologically inspired method for robot navigation in a cluttered environment,” _Robotica_ , vol. 28, no. 5, pp. 637–648, August 2010.
  * [35] A. V. Savkin and C. Wang, “A simple biologically inspired algorithm for collision-free navigation of a unicycle-like robot in dynamic environments with moving obstacles,” _Robotica_ , vol. 31, no. 6, pp. 993–1001, May 2013\.
  * [36] A. S. Matveev, H. Teimoori, and A. V. Savkin, “A method for guidance and control of an autonomous vehicle in problems of border patrolling and obstacle avoidance,” _Automatica_ , vol. 47, no. 3, pp. 515–524, March 2011\.
  * [37] A. V. Savkin and C. Wang, “Seeking a path through the crowd: Robot navigation in unknown dynamic environments with moving obstacles based on an integrated environment representation,” _Robotics and Autonomous Systems_ , vol. 62, no. 10, pp. 1568–1580, October 2014.
  * [38] H. Huang, A. V. Savkin, and C. Huang, _Wireless Communication Networks Supported by Autonomous UAVs and Mobile Ground Robots_. Elsevier, 2022.
  * [39] Y. Zhu, T. Zhang, J. Song, and X. Q. Li, “A new hybrid navigation algorithm for mobile robots in environments with incomplete knowledge,” _Knowledge-Based Systems_ , vol. 27, no. 11, pp. 302–313, March 2011.
  * [40] J. L. Jones, P. E. Sandin, and B. P. Adams, “Robot development platform,” _United States Patent_ , US 8095238 B2, January 2012.
  * [41] T. Brogardh, “Present and future robot control development- an industrial perspective,” _Annual Reviews in Control_ , vol. 31, no. 1, pp. 69–79, January 2007.
  * [42] P. Angelo, C. D. Bocaniala, C. Xideas, C. Patchett, D. Ansell, M. Everett, and G. Leng, “A passive approach to autonomous collision detection and avoidance in uninhabited aerial system,” _the 10th EUROS/UKSim International Conference on Computer Modelling and Simulation_ , Cambridge, UK, 2008.
  * [43] A. S. Matveev, A. V. Savkin, M. Hoy, and C. Wang, _Safe Robot Navigation among Moving and Steady Obstacles_. Elsevier, 2015.
  * [44] C. Wang, A. V. Savkin, and M. Garratt, “A strategy for safe 3D navigation of non-holonomic robots among moving obstacles,” _Robotica_ , vol. 36, no. 2, pp. 275–297, November 2018.
  * [45] H. Li and A. V. Savkin, “Wireless sensor network based navigation of micro flying robots in the industrial internet of things,” _IEEE Transactions on Industrial Informatics_ , vol. 14, no. 8, pp. 3524–3533, August 2018.
  * [46] A. V. Savkin and H. Li, “A safe area search and map building algorithm for a wheeled mobile robot in complex unknown cluttered environments,” _Robotica_ , vol. 36, no. 1, pp. 96–118, April 2018.
  * [47] N. Kehtarnavaz and S. Li, “A collision-free navigation scheme in the presence of moving obstacles,” _The Computer Society Conference on Computer Vision and Pattern Recognition_ , Ann Arbor, USA, 1988.
  * [48] X. L. Y. ans L. M. Alvarez and T. Bruggeman, “A 3D collision avoidance strategy for UAVs in a non-cooperative environment,” _J Intell Robot Syst_ , vol. 70, no. 12, pp. 315–327, August 2013.
  * [49] M. S. Wiig, K. Y. Pettersen, and T. R. Krogstad, “A 3D reactive collision avoidance algorithm for nonholonomic vehicles,” _2018 IEEE Conf. on Control Technology and Applications_ , Copenhagen, Denmark, 2018.
  * [50] I. R. Petersen, V. A. Ugrinovskii, and A.V.Savkin, _Robust Control Design Using $H^{\infty}$ Methods_. Springer Science and Business Media, 2000.
  * [51] R. A. Nichols, R. T. Reichert, and W. Rugh, “Gain scheduling for H-infinity controllers: a flight control example,” _IEEE Transactions on Control Systems Technology_ , vol. 1, no. 2, pp. 69–79, June 1993.
  * [52] M. Chen and M. Huzmezan, “A combined MBPC/ 2 DOF $H^{\infty}$ controller for a quadrotor UAV,” _AIAA Guidance, Navigation, and Control Conference and Exhibit_ , Austin, USA, 2003.
  * [53] I. R. Petersen and A. V. Savkin, _Robust Kalman Filtering for Signals and Systems with Large Uncertainties_. Springer Science and Business Media, 1999.
  * [54] P. N. Pathirana, N. Bulusu, A. V. Savkin, and S. Jha, “Node localization using mobile robots in delay-tolerant sensor networks,” _IEEE Transactions on Mobile Computing_ , vol. 4, no. 3, pp. 285–296, April 2005.
  * [55] A.V.Savkin and I. R. Petersen, “Robust state estimation and model validation for discrete-time uncertain systems with a deterministic description of noise and uncertainty,” _Automatica_ , vol. 34, no. 2, pp. 271–274, February 1998\.
  * [56] P. N. Pathirana, A. V. Savkin, and S. Jha, “Location estimation and trajectory prediction for cellular networks with mobile base stations,” _IEEE Transactions on Vehicular Technology_ , vol. 53, no. 6, pp. 1903–1913, November 2004.
  * [57] X. Liu and J. Cao, “Robust state estimation for neural networks with discontinuous activations,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 40, no. 6, pp. 1425–1437, December 2010\.
  * [58] J. Luc, “Robust set-membership state estimation; application to underwater robotics,” _Automatica_ , vol. 45, no. 1, pp. 202–206, January 2009.
  * [59] A. V. Savkin and I. R. Petersen, “Robust filtering with missing data and a deterministic description of noise and uncertainty,” _International journal of systems science_ , vol. 28, no. 4, pp. 373–378, 1997.
  * [60] P. A. et al., “A passive approach to autonomous collision detection and avoidance in uninhabited aerial systems,” _the 10th EUROS/UKSim International Conference on Computer Modelling and Simulation_ , Cambridge, UK, 2008.
  * [61] F. S. H. et al., “Advanced perception, navigation and planning for autonomous in-water ship hull inspection,” _The International Journal of Robotics Research_ , vol. 31, no. 12, pp. 1445–1464, November 2012.
  * [62] P. Young-Sik, C. Won-Seok, H. Seong-Ik, and L. Jang-Myung, “Navigation system of uuv using multi-sensor fusion-based EKF,” _Journal of Institute of Control, Robotics and Systems_ , vol. 22, no. 7, pp. 562–569, July 2016.
  * [63] D. Li, Z. Pan, and H. Deng, “Two-dimensional obstacle avoidance control algorithm for snake-like robot in water based on immersed boundary- lattice boltzmann method and improved artificial potential field method,” _Transactions of the Institute of Measurement and Control_ , vol. 42, no. 10, pp. 1840–1857, January 2020.
  * [64] O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” in _Autonomous Robot Vehicles_ , 1986, pp. 396–404.
  * [65] Z. Pan, J. Q. Li, K. M. Hu, and H. Zhu, “Intelligent vehicle path planning based on improved artificial potential field method,” _Applied Mechanics and Materials_ , vol. 742, no. 1, pp. 396–404, March 2015.
  * [66] P. W. et al., “Autonomous obstacle avoidance of an unmanned surface vehicle based on cooperative manoeuvring,” _Industrial Robot_ , vol. 44, no. 1, pp. 64–74, January 2017.
  * [67] A. S. Matveev, C. Wang, and A. V. Savkin, “Real-time navigation of mobile robots in problems of border patrolling and avoiding collisions with moving and deforming obstacles,” _Robotics and Autonomous Systems_ , vol. 60, no. 6, pp. 769–788, June 2012.
  * [68] V. Utkin, J. Guldner, and J. Shi, _Sliding mode control in electro-mechanical systems_. CRC press, 2017.
  * [69] V. I. Utkin, _Sliding modes and their applications in variable structure systems_. Mir Publisher, 1978.
  * [70] A. V. Savkin and R. J. Evans, _Hybrid Dynamical Systems: Controller and Sensor Switching Problems_. Springer Science and Business Media, 2002.
  * [71] E. Skafidas, R. J. Evans, A. V. Savkin, and I. R. Petersen, “Stability results for switched controller systems,” _Automatica_ , vol. 35, no. 4, pp. 553–564, April 1999.
  * [72] Y. Khnsiawan and I. Nielsen, “A system of UAV application in indoor environment,” _Robotica_ , vol. 4, no. 1, pp. 2–22, June 2016.
  * [73] N. Buniyamin, W. A. J. W. Ngah, N. Sariff, and Z. Mohamad, “A simple local path planning algorithm for autonomous mobile robots,” _International Journal of System Applications, Engineering and Development_ , vol. 5, no. 2, pp. 151–159, 2011.
  * [74] E. M. P. Low, I. R. Manchester, and A. V. Savkin, “A biologically inspired method for vision based docking of mobile robots,” _Robotics and Autonomous Systems_ , vol. 55, no. 10, pp. 769–784, October 2007.
  * [75] H. Huang, A. V. Savkin, M.Ding, and C. Huang, “Mobile robots in wireless sensor networks: A survey on tasks,” _Computer Networks_ , vol. 148, no. 10, pp. 1–19, January 2018.
  * [76] J. C. Kinsey, R. M. Eustice, and L. L. Whitcomb, “A survey of underwater vehicle navigation: Recent advances and new challenges,” _IFAC Conference of Manoeuvering and Control of Marine Craft_ , Lisbon, Portugal, 2006\.
  * [77] F. Zeng, C. Wang, and S. S. Ge, “A survey on visual navigation for artificial agents with deep reinforcement learning,” _IEEE Access_ , vol. 8, no. 30, pp. 135 426–135 442, July 2020.
  * [78] W. Shi, K. Wang, and S. X. Yang, “A fuzzy-neural network approach to multisensor integration for obstacle avoidance of a mobile robot,” _Intelligent Automation and Soft Computing_ , vol. 15, no. 2, pp. 289–301, March 2013.
  * [79] J. Qiao, Z. Hou, and X. Ruan, “Application of reinforcement learning based on neural network to dynamic obstacle avoidance,” _2008 International Conference on Information and Automation_ , Changsha, China, 2008.
  * [80] H. Liu and Y. Guo, “Intelligent obstacle avoidance algorithms for autonomous underwater vehicle,” _The 2020 3rd International Conference on Computer Information Science and Artificial Intelligence (CISAI)_ , Inner Mongolia, China, 2020.
  * [81] J. Li, J. Shi, J. Shi, and F. Huang, “Brief introduction of back propagation (BP) neural network algorithm and its improvement,” in _Advances in Intelligent and Soft Computing_ , 2012, pp. 553–558.
  * [82] W. Budiharto, “Intelligent surveillance robot with obstacle avoidance capabilities using neural network,” _Computational Intelligence and Neuroscience_ , vol. 2015, no. 52, pp. 52–57, January 2015.
  * [83] L. Dong and H. Xu, “Research on auv obstacle avoidance based on bp neural network,” _2017 the 2nd International Conference on Robotics, Control and Automation (ICRCA)_ , New York, USA, 2017.
  * [84] C. Luo, J. Gao, X. Li, H. Mo, and Q. Jian, “Sensor-based autonomous robot navigation under unknown environments with grid map representation,” _2017 the 2nd International Conference on Robotics, Control and Automation (ICRCA)_ , Orlando, USA, 2014.
  * [85] Y. Zhang and J. Zhang, “A navigation algorithm for UUVs to avoid shape changeable obstacles,” _2022 the 14th international Conference on Computer and Automation Engineering (ICCAE)_ , Brisbane, Australia, 2022.
  * [86] A. B. ORCID, Y. González, and G. Oliver, “Sonar sensor models and their application to mobile robot localization,” _sensors_ , vol. 9, no. 12, pp. 10 217–10 243, November 2009.
  * [87] T. T. Q. Bui, A. Widyotriatmo, L. H. Nguyen, and K. Hong, “Sonar-based collision avoidance and probabilistic motion model for mobile robot navigation,” _2009 7th Asian Control Conference_ , Hong Kong, China, 2009\.
  * [88] M. Daily, S. Medasani, R. Behringer, and M. Trivedi, “Self-driving cars,” _Computer_ , vol. 50, no. 12, pp. 18–23, December 2017.
  * [89] C. Badue and et al., “Self-driving cars: A survey,” _Expert Systems with Applications_ , vol. 165, no. 1, March 2021.
  * [90] C. Huang, H. Huang, J. Zhang, P. Hang, Z. Hu, and C. Lv, “Human-machine cooperative trajectory planning and tracking for safe automated driving,” _IEEE Transactions on Intelligent Transportation Systems_ , pp. 1–14, September 2021.
  * [91] C. Huang, H. Huang, P. Hang, H. Gao, J. Wu, Z. Huang, and C. Lv, “Personalized trajectory planning and control of lane-change maneuvers for autonomous driving,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 6, pp. 5511–5523, April 2021.
  * [92] D. J. Natale, R. L. Tutwiler, M. S. Baran, and J. R. Durkin, “Using full motion 3D flash lidar video for target detection, segmentation, and tracking,” _2010 IEEE Southwest Symposium on Image Analysis and Interpretation (SSIAI)_ , Austin, USA, 2010.
  * [93] C. Blanc, R. Aufrere, L. Malaterre, J.Gallice, and J. Alizon, “Obstacle detection and tracking by millimeter wave radar,” _IFAC Proceedings Volumes_ , vol. 37, no. 8, pp. 322–327, July 2004.
  * [94] D. A. Pomerleau, “Alvinn: An autonomous land vehicle in a neural network,” in _Advances in Neural Information Processing Systems_ , 1988.
  * [95] M. Bojarski and et al., “End to end learning for self-driving cars,” _Computer Vision and Pattern Recognition_ , 2016.
  * [96] S. Mathur, T. Jin, N. Kasturirangan, J. Chandrasekaran, W. Xue, M. Gruteser, and W. Trappe, “Parknet: Drive-by sensing of road-side parking statistics,” _Proceedings of the 8th International Conference on Mobile Systems, Applications and Services_ , p. 123–136, June 2010.
  * [97] D. A. Clevert, T. Unterthiner, and S. Hochreiter, “Fast and accurate deep network learning by exponential linear units (elus),” _Machine Learning_ , 2015.
  * [98] “Udacity: An open source self-driving car simulator,” 2018.
  * [99] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _Machine Learning_ , 2014.
  * [100] T. Castelli, A. Sharghi, D. Harper, A. Tremeau, and M. Shah, “Autonomous navigation for low-altitude UAVs in urban areas,” _Robotics_ , February 2016.
  * [101] J. Zhang and H. Huang, “Occlusion-aware UAV path planning for reconnaissance and surveillance,” _Drones_ , vol. 5, no. 3, p. 98, September 2021.
  * [102] A. V. Savkin and H. Huang, “Proactive deployment of aerial drones for coverage over very uneven terrains: A version of the 3D art gallery problem,” _Sensors_ , vol. 19, no. 6, pp. 1438–1449, March 2019.
  * [103] H. Huang, A. V. Savkin, and C. Huang, “Reliable path planning for drone delivery using a stochastic time-dependent public transportation network,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 8, pp. 4941–4950, 2020.
  * [104] A. V. Savkin and H. Huang, “Asymptotically optimal deployment of drones for surveillance and monitoring,” _Sensors_ , vol. 19, no. 9, pp. 2068–2079, April 2019.
  * [105] J. Zhang, “Occlusion-aware UAV path planning for reconnaissance and surveillance in complex environments,” _2019 IEEE Interna- tional Conference on Robotics and Biomimetics (ROBIO)_ , Dali, China, 2019.
  * [106] H. Huang and A. V. Savkin, “An algorithm of reactive collision free 3D deployment of networked unmanned aerial vehicles for surveillance and monitoring,” _IEEE Transactions on Industrial Informatics_ , vol. 16, no. 1, pp. 132–140, January 2020.
  * [107] J. Zhang, “A collision-free 3D path planning strategy for mobile robots,” _2019 Australian and New Zealand Control Conference (ANZCC)_ , Auckland, New Zealand, 2019.
  * [108] A. V. Savkin and H. Huang, “Deployment of unmanned aerial vehicle base stations for optimal quality of coverage,” _IEEE Wireless Communications Letters_ , vol. 9, no. 1, pp. 321–324, 2018.
  * [109] H. Huang and A. V. Savkin, “Reactive 3D deployment of a flying robotic network for surveillance of mobile targets,” _Computer Networks_ , vol. 161, no. 6, pp. 172–182, October 2019.
  * [110] A. V. Savkin and H. Huang, “A method for optimized deployment of a network of surveillance aerial drones,” _IEEE Systems Journal_ , vol. 13, no. 4, pp. 4474–4477, December 2019.
  * [111] L. Geng, Y. F. Zhang, J. J. Wang, J. Y. Fuh, and S. H. Teo, “Mission planning of autonomous UAVs for urban surveillance with evolutionary algorithms,” _IEEE International Conference on Control and Automation (ICCA)_ , Nha Trang, Vietnam, 2019.
  * [112] E. Semsch, M. Jakob, D. Pavlicek, and M. Pechouce, “Autonomous UAV surveillance in complex urban environments,” _2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT)_ , Milan, Italy, 2009.
  * [113] J. Zhang and H. Huang, “A path planning method for video camera equipped UAVs monitoring a ground area,” _2021 Australian and New Zealand Control Conference (ANZCC)_ , Gold Coast, Australia, 2021.
  * [114] V. Govindaraju, G. Leng, and Z. Qian, “Multi-UAV surveillance over forested regions,” _Photogrammetric Engineering and Remote Sensing_ , vol. 80, no. 12, pp. 1129–1137, December 2014.
  * [115] J. Tisdale, Z. Kim, and J. K. Hedrick, “Autonomous UAV path planning and estimation,” _IEEE Robotics and Automation Magazine_ , vol. 16, no. 2, pp. 35–42, June 2000.
  * [116] S. Bortoff, “Path planning for UAVs,” _Proceedings of the 2000 American Control Conference_ , Chicago, USA, 2000.
  * [117] Y. Zhao, Z. Zheng, and Y. Liu, “Survey on computational-intelligence-based UAV path planning,” _Knowledge-Based Systems_ , vol. 158, no. 5, pp. 54–64, October 2018.
  * [118] ——, “Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning,” _IEEE Transactions on Industrial Informatics_ , vol. 9, no. 1, pp. 132–141, February 2013.
  * [119] X. Chen and J. Zhang, “The three-dimension path planning of UAV based on improved artificial potential field in dynamic environment,” _2013 5th International Conference on Intelligent Human-Machine Systems and Cybernetics_ , Hangzhou, China, 2013.
  * [120] H. Li, A. V. Savkin, and B. Vucetic, “Autonomous area exploration and mapping in underground mine environments by unmanned aerial vehicles,” _Robotica_ , vol. 38, no. 3, pp. 442–456, March 2020.
  * [121] T. Elmokadem and A. V. Savkin, “A method for autonomous collision-free navigation of a quadrotor UAV in unknown tunnel-like environments,” _Robotica_ , vol. 40, no. 4, pp. 835–861, April 2022.
  * [122] A. S. Matveev, V. V. Magerkin, and A. V. Savkin, “A method of reactive control for 3D navigation of a nonholonomic robot in tunnel-like environments,” _Automatica_ , vol. 114, p. 108831, April 2020.
  * [123] A. S. Matveev and A. V. Savkin, _Estimation and Control over Communication Networks_. Springer Science and Business Media, 2009.
  * [124] A. V. Savkin, “Analysis and synthesis of networked control systems: topological entropy, observability, robustness, and optimal control,” _Automatica_ , vol. 42, no. 1, pp. 51–62, January 2006.
  * [125] A. V. Savkin and I. R. Petersen, “Set-valued state estimation via a limited capacity communication channel,” _IEEE Transactions on Automatic Control_ , vol. 48, no. 4, pp. 676–680, April 2003.
  * [126] A. S. Matveev and A. V. Savkin, “The problem of state estimation via asynchronous communication channels with irregular transmission times,” _IEEE Transactions on Automatic Control_ , vol. 48, no. 4, pp. 6770–676, April 2003.
  * [127] R. A. Gupta and M. Chow, “Overview of networked control systems,” in _Networked Control Systems_ , 2008, pp. 1–23.
  * [128] H. Li, X. Li, J. Wang, and H. Ma, “Design of networked control system based on wireless sensor networks,” _2009 International Conference on Information and Automation_ , Zhuhai and Macau, China, 2009.
  * [129] E. P. Godoy and et al., “Networked control system for the guidance of a four-wheel steering agricultural robotic platform,” _Journal of Control Science and Engineering_ , vol. 2012, no. 4, pp. 4–14, January 2012.
  * [130] H. Asama and I. Endo, “Collision avoidance among multiple mobile robots based on rules and communication,” _1991 IEEE/RSJ International Workshop on Intelligent Robots and Systems (IROS)_ , Osaka, Japan, 1991.
  * [131] Y. Guo and L. E. Parker, “A distributed and optimal motion planning approach for multiple mobile robots,” _Proceedings 2002 IEEE International Conference on Robotics and Automation_ , Washington, USA, 2002.


# Sampling Is All You Need on Modeling Long-Term User Behaviors
for CTR Prediction

Yue Cao, XiaoJiang Zhou, Jiaqi Feng
Peihao Huang, Yao Xiao, Dayao Chen, Sheng Chen  Meituan Inc.BeijingP.R. China
<EMAIL_ADDRESS>zhouxiaojiang, fengjiaqi03, huangpeihao, xiaoyao06,
chendayao<EMAIL_ADDRESS>
(2022)

###### Abstract.

Rich user behavior data has been proven to be of great value for Click-Through
Rate (CTR) prediction applications, especially in industrial recommender,
search, or advertising systems. However, it’s non-trivial for real-world
systems to make full use of long-term user behaviors due to the strict
requirements of online serving time. Most previous works adopt the retrieval-
based strategy, where a small number of user behaviors are retrieved first for
subsequent attention. However, the retrieval-based methods are sub-optimal and
would cause more or less information losses, and it’s difficult to balance the
effectiveness and efficiency of the retrieval algorithm.

In this paper, we propose SDIM (Sampling-based Deep Interest Modeling), a
simple yet effective sampling-based end-to-end approach for modeling long-term
user behaviors. We sample from multiple hash functions to generate hash
signatures of the candidate item and each item in the user behavior sequence,
and obtain the user interest by directly gathering behavior items associated
with the candidate item with the same hash signature. We show theoretically
and experimentally that the proposed method performs on par with standard
attention-based models on modeling long-term user behaviors, while being
sizable times faster. We also introduce the deployment of SDIM in our system.
Specifically, we decouple the behavior sequence hashing, which is the most
time-consuming part, from the CTR model by designing a separate module named
BSE (behavior Sequence Encoding). BSE is latency-free for the CTR server,
enabling us to model extremely long user behaviors. Both offline and online
experiments are conducted to demonstrate the effectiveness of SDIM. SDIM now
has been deployed online in the search system of Meituan APP.

CTR prediction, Hash-based sampling, Long-term user behavior modeling

††copyright: acmcopyright††journalyear: 2022††doi:
10.1145/1122445.1122456††conference: -; May 20, 2022; -††booktitle:
Unpublished Work††price: 15.00††isbn: XXXXXX††ccs: Information systems
Personalization††ccs: Information systems Recommender systems

##  1\. Introduction

Click-Through Rate (CTR) prediction is an essential task in industrial
applications, such as online search, recommendation, and advertising systems.
User interest modeling, which aims at learning user’s implicit interest from
historical behavior data, has been widely introduced for real-world systems
and contributes remarkable improvement (Zhou et al., 2018; Tang and Wang,
2018; Feng et al., 2019).

Various models are proposed for modeling users’ interests (Tang and Wang,
2018; Kang and McAuley, 2018; Zhou et al., 2018). Among them, DIN (Zhou et
al., 2018) adaptively calculates user interests by taking the relevance of
historical behaviors given a target item into consideration. DIN introduces a
new attention module named target attention, where the target item acts as the
query $\mathbf{Q}$ and historical user behaviors act as the key $\mathbf{K}$
and the value $\mathbf{V}$. Due to its superior performance, DIN-based methods
have become the mainstream solution for modeling user interests in recent
years.

With the rapid development of the internet, user accumulates more and more
behavior data on E-commerce platforms. Take Taobao, the largest online
shopping platform in China, for example, they report that 23% of users have
more than 1,000 behaviors in Taobao APP in six months (Ren et al., 2019). In
Meituan APP, there are more than 60% of users have at least 1,000 behaviors,
and more than 10% of users have at least 5,000 behaviors in one year. However,
the strict requirements of online serving time limit the length of user
behavior sequences that can be used. As a result, most of the industrial
systems truncate the user behavior sequences and just feed recent 50 behaviors
(Zhou et al., 2018, 2019) for user interest modeling, which leads to
information losses.

Recently, some methods are proposed to model users’ long-term interests from
long behavior sequences (Pi et al., 2019; Pi et al., 2020; Qin et al., 2020;
Chen et al., 2021). Among them, MIMN (Pi et al., 2019) decouples the user
interest modeling from the entire model by designing a separate User Interest
Center (UIC) module. While saving lots of online serving time, MIMN can’t
utilize the information from the target item, which has been proved to be
crucial for modeling users’ interests (Chen et al., 2021). Therefore, MIMN can
only model shallow user interests. SIM (Pi et al., 2020) and UBR4CTR (Qin et
al., 2020) adopt two-stage frameworks for handling long-term user behaviors.
They retrieves top-$k$ similar items, and feed top-$k$ items to the subsequent
target attention module (Zhou et al., 2018). As pointed by (Chen et al.,
2021), the retrieve objectives of these approaches are divergent with the goal
of the CTR model, and the pre-trained embedding in offline inverted index is
not suiting for online learning systems. ETA (Chen et al., 2021) proposes an
LSH-based method to retrieve top-$k$ similar items from long-term user
behaviors in an end-to-end fashion. They use locality-sensitive hash (LSH) to
convert items into hash signatures, and then retrieve top-$k$ similar items
based on their hamming distance to the candidate item. The use of LSH greatly
reduces the cost to calculate the similarity between items, and ETA achieves
better results than SIM (Pi et al., 2020) and UBR4CTR (Qin et al., 2020).

The above retried-based methods suffer from following drawbacks: The retrieve
of top-$k$ items from the whole sequence is sub-optimal and would produce
biased estimation of user’s long-term interests. If a user has lots of
behaviors, the retrieved top-$k$ items may all similar to the candidate item
and the estimated user interest representation would be inaccurate. Besides,
it’s difficult to balance to effectiveness and efficiency of the retrieval
algorithm. SIM (hard) uses a simple retrieve algorithm, so its performance is
inferior compared with other methods. On the other hand, UBR4CTR achieves
significant improvement with the aid of a complex retrieval module, but its
inference speed becomes $4\times$ slower (Qin et al., 2020), which prevents
UBR4CTR from being deployed online, especially for long-term user behaviors
modeling.

In this paper, we propose a simple hash sampling-based approach for modeling
long-term user behaviors. First, we sample from multiple hash functions to
generate hash signatures of the target item and each item in user behavior
sequence. Instead of retrieving top-$k$ similar items using a certain metric,
we directly gather behavior items that share the same hash signature with the
target item to form the user interest. The intrinsic idea behind our method is
to approximate the softmax distribution of user interest with LSH collision
probability. We show theoretically that this simple sampling-based method
produces very similar attention patterns as softmax-based target attention and
achieves consistent model performance, while being much more time-efficient.
Therefore, our method behaviors like computing attention directly on the
original long sequence, without information loss. We named the proposed method
as SDIM (means Sampling-based Deep Interest Modeling).

We also introduce our hands-on practice on deploying SDIM online.
Specifically, we decouple our framework into two parts: (1) Behavior Sequence
Hashing (BSE) server, and (2) CTR server, where the two parts are deployed
separately. The behavior sequence hashing is the most time-consuming part of
the whole algorithm, and the decoupling of this part greatly reduces the
serving time. More details will be introduced in Section 4.4.

We conduct experiments on both public and industrial datasets. Experimental
results show that SDIM achieves results consistent with standard attention-
based methods, and outperforms all competitive baselines on modeling long-term
user behaviors, and with sizable speed ups. SDIM has been deployed in the
search system in Meituan111https://meituan.com/, the largest e-commerce
platform for lifestyle services in China, and bringing 2.98% CTR and 2.69% VBR
lift, which is very significant to our business.

In sum, the main contributions of this paper are summarized as follows:

  * •

We propose SDIM, a hash sampling-based framework for modeling long-term user
behaviors for CTR prediction. In SDIM, the distribution of user interest is
approximated with LSH collision probabilities. We prove that this simple
sampling-based strategy produces very similar attention patterns as target
attention.

  * •

We introduce our hands-on practice on deploying SDIM online in detail. We
believe this work would help to advance the community, especially in modeling
long-term user behaviors.

  * •

Extensive experiments are conducted on both public and industrial datasets,
and the results demonstrate the superiority of SDIM in terms of efficiency and
effectiveness. SDIM has been deployed in the search system in Meituan,
contributing significant improvement to the business.

##  2\. Related Work

###  2.1. Click-Through Rate (CTR) Prediction

With the rapid development of deep learning, deep neural-based methods have
achieved remarkable performance in CTR prediction.

Some work (Cheng et al., 2016; Guo et al., 2017; Qu et al., 2016; Wang et al.,
2017) focus on exploring feature interaction to improve performance. For
example, wide & deep (Cheng et al., 2016) jointly train a wide linear model
and a deep neural network, which explicitly models memorization and
generalization simultaneously in one model. DeepFM (Guo et al., 2017) replace
wide model with factorization machines (FM) (Rendle, 2010) to increase the
ability to model low-order feature interaction. PNN (Qu et al., 2016) designs
a product layer to capture high-order feature interactive patterns. DCN (Wang
et al., 2017) introduces a novel cross net to learn automatic bounded degree
feature interaction.

Besides feature interaction, many work (Zhou et al., 2018, 2019; Feng et al.,
2019; Li et al., 2019) focus on learning better representation from user
historical behaviors in recent years. DIN (Zhou et al., 2018) introduces
target attention which learns different user interests with regard to
different target items. In (Zhou et al., 2019), considering interest evolving
process in user behaviors, DIEN proposes an interest evolving layer to capture
dynamic interest about target item. In DSIN (Feng et al., 2019), based on a
prior knowledge that user behaviors are highly homogeneous in each session and
heterogeneous in different sessions, the session-based model is proposed. It
is worth noting that the target attention mechanism in DIN (Zhou et al., 2018)
has been widely used in CTR models nowadays.

###  2.2. Long-Term Sequential User Behavior Modeling

User behavior modeling has shown great performance in industrial applications.
Exploring richer user behavior in CTR models has attracted much attention.
However, long-term user behavior modeling is faced with several challenges,
such as complex model deployment and system latency.

In MIMN (Pi et al., 2019), the user interest center (UIC) block with a memory-
based architecture design is proposed to tackle the challenge. The block is
updated by user behavior event and only need to store limited user interest
memory. MIMN is hard to model the interaction between user behavior sequence
and target item which has proved to be important in CTR modeling. In SIM (Pi
et al., 2020), a two-stage method is proposed to model long-term user behavior
sequences. Firstly, a general search unit (GSU) is utilized to extract
relevant behaviors with regard to the target item. Secondly, an exact search
unit is proposed to model relevant behaviors in an end-to-end manner. UBR4CTR
(Qin et al., 2020) uses a similar search-based method as SIM (Pi et al., 2020)
to face challenges. Recently, ETA (Chen et al., 2021) proposes an end-to-end
target attention method to model long-term user behavior sequence. They apply
locality-sensitive hashing (LSH) to reduce the training and inference time
cost.

Besides the above related works in the field of CTR prediction, there are also
plenty of works in Natural Language Processing (NLP) that aim to improve the
efficiency of self-attention (Kitaev et al., 2020; Zhou et al., 2021; Zeng et
al., 2021; Wang et al., 2020). These approaches can reduce the time complexity
of self-attention from $O(L^{2})$ to $O(L\log(L))$, where $L$ is the sequence
length, but can not be applied to reduce the $O(L)$ time complexity of the
target attention.

##  3\. PRELIMINARIES

###  3.1. Task Formulation

CTR prediction is a core task in the industrial recommendation, search, and
advertising systems. The goal of the CTR task is to estimate the probability
of a user clicking on the item, which is defined as follows:

(1) $\text{prob}_{i}=P(y_{i}=1|x_{i};\theta)$

In above equation, $\theta$ represents trainable parameters in CTR model.
Given input features $x_{i}$, CTR model is trained to predict the click
probability $\text{prob}_{i}$ by minimizing the cross-entropy loss:

(2)
$L=-\frac{1}{N}\sum_{i=1}^{N}(y_{i}\log(\text{prob}_{i})+(1-y_{i})\log(1-\text{prob}_{i}))$

###  3.2. Target Attention

The concept of target attention is first proposed by DIN (Zhou et al., 2018)
and is widely applied for modeling user interests on CTR tasks (Zhou et al.,
2019; Feng et al., 2019; Chen et al., 2021; Pi et al., 2020; Pi et al., 2019).
Target attention takes the target item as query and each item in the user
behavior sequence as key and value, and uses an attention operator to soft-
search relevant parts from the user behavior sequence. The user interests are
then obtained by taking a weighted sum over user behavior sequence.

Specifically, designate the target item as $\mathbf{Q}\in\mathbb{R}^{B\times
d}$ and user sequence representations as $\mathbf{S}\in\mathbb{R}^{B\times
L\times d}$, where $B$ is the number of candidate items to be scored by the
CTR model for each request, $L$ is the length of user behavior sequence, and
$d$ is the model’s hidden size. Let $\mathbf{q}_{i}$ be the $i$-th target
item, target attention calculates the dot product similarity between
$\mathbf{q}_{i}$ and each item in behavior sequence $\mathbf{S}$, and then use
the normalized similarities as the weights to obtain user’s interest
representation.

(3)
$\text{TA}(\mathbf{q}_{i},\mathbf{S})=\frac{\exp{(\mathbf{q}_{i}^{\top}\mathbf{s}_{j}/\sqrt{d})}}{\sum_{j=1}^{L}\exp{(\mathbf{q}_{i}^{\top}\mathbf{s}_{j}/\sqrt{d})}}\cdot\mathbf{s}_{j}$

The matrix form of Eq. 3 can be written as:

(4)
$\text{TA}(\mathbf{Q},\mathbf{S})=softmax(\frac{\mathbf{Q}^{\top}\mathbf{S}}{\sqrt{d}})\mathbf{S}$

The scaling factor $\sqrt{d}$ is used to avoid large value of the inner
product (Chen et al., 2021).

The complexity of calculating $\text{TA}(\mathbf{Q},\mathbf{S})$ is $O(BLd)$
where $B$ is the number of candidate items for each request, $L$ is the length
of user behavior sequence, and $d$ is the model’s hidden size. In large-scale
industrial systems, $B$ is about $10^{3}$ and $d$ is about $10^{2}$, and it’s
infeasible to deploy target attention on long-term user behaviors modeling for
online systems (Chen et al., 2021; Pi et al., 2019).

###  3.3. Locality-Sensitive Hash (LSH) and SimHash

Locality-sensitive hash (LSH) (Andoni et al., 2015) is an algorithmic
technique for finding nearest neighbors efficiently in high-dimensional
spaces. LSH satisfies the locality-preserving property: nearby vectors get the
same hash with high probability while distant ones do not. Benefiting from
this property, LSH-based signatures has been widely used in many applications
such as web search system (Manku et al., 2007). The random projection scheme
(SimHash) (Charikar, 2002; Leskovec et al., 2014) is an efficient
implementation of LSH. The basic idea of SimHash is to sample a random
projection (defined by a normal unit vector $\mathbf{r}$) as hash function to
hash input vectors into two axes (+1 or -1). Specifically, given an input
$\mathbf{x}$ and a hash function $\mathbf{r}$, the corresponding hash is
calculated as:

(5) $h(\mathbf{x},\mathbf{r})=\text{sign}(\mathbf{r}^{\top}\mathbf{x})$

where $\mathbf{r}\in\mathbb{R}^{d}$, $r_{i}\sim\mathcal{N}(0,1)$.
$h(\mathbf{x},\mathbf{r})=\pm 1$ depends on which side of the hashed output
lies. For two vectors $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$, we say
$\mathbf{x}_{1}$ collides with $\mathbf{x}_{2}$ only when they have the same
value of the hash code:

(6)
$p^{(\mathbf{r})}=\mathbbm{1}_{h(\mathbf{x}_{1},\mathbf{r})=h(\mathbf{x}_{2},\mathbf{r})}$

While a single hash would work in estimating similarities, the outputs can be
the average of multiple hashes to lower the estimation error. In practice, the
$(m,\tau)$-parameterized SimHash (multi-round hash) algorithm (Leskovec et
al., 2014) is usually adopted, where $m$ is the number of hash functions and
$\tau$ is the width parameter. In the first step, SimHash randomly samples $m$
hash functions and generates $m$ hash codes for each input:

(7) $h(\mathbf{x},\mathbf{R})=\text{sign}(\mathbf{R}\mathbf{x})$

where $\mathbf{R}\in\mathbb{R}^{m\times d}$,
$h(\mathbf{x},\mathbf{R})\in\mathbb{R}^{m}$. To reduce the probability of
dissimilar items having the same hash codes, the algorithm merge the results
of every $\tau$ codes to form a new hash signature. For more details, please
refer to (Leskovec et al., 2014). In simHash, $\mathbf{x}_{1}$ collides with
$\mathbf{x}_{2}$ only when they have the same value of the hash signature,
i.e., their hash codes in a batch of $\tau$ codes are all the same:

(8) $\displaystyle\tilde{p}^{(\mathbf{R})}$
$\displaystyle=p^{(\mathbf{r}_{1})}\ \&\ p^{(\mathbf{r}_{2})}\ \&\ \cdots\&\
p^{(\mathbf{r}_{\tau})}$ $\displaystyle=\&_{k=1}^{\tau}p^{(\mathbf{r}_{k})}$

where ”$\&$” represents the logical ”AND”, and $\mathbf{r}_{k}$ is the $k$-th
hash function. The bottom of Figure 1 shows an example of
$(4,2)$-parameterized SimHash algorithm, where we use 4 hash functions and
aggregate every 2 hash codes into 2 hash signatures (yellow and green).

##  4\. Methodology

Figure 1. High-level overview of our framework. It consists of two separate
servers: Behavior Sequence Encoding (BSE) server and CTR server. The BSE
server calculates the hashing of user behavior sequence, and the CTR server
calculates the hashing of candidate items and gathers behavior items that
share the same hash signature with the candidate item to form user interests.
The CTR server contains a real-time CTR model, which takes user interest
features, item features, and context features as inputs to predict the click
probability corresponding to each candidate item.

In this section, we introduce our framework for implementing SDIM in our
system. A high-level overview can be seen in Figure 1. The framework is
consist of two separate servers: Behavior Sequence Encoding (BSE) server and
CTR Server, which will be introduced in detail later.

###  4.1. User Behavior Modeling via Hash-Based Sampling

####  4.1.1. Hash Sampling-Based Attention

At the first step, we sample multiple hash functions and generate the hash
codes of user behaviors and candidate items. Then we model user interest based
on the hash codes rather than original inputs, which is similar to ETA (Chen
et al., 2021). After hashing, ETA calculates the Hamming distance between
items as an approximation of user interest distribution to select top-$k$
similar items. Here we argue that there is a more efficient and more effective
way to approximate the user interest.

With the locality-preserving property, similar vectors fall in the same hash
bucket with high probability, therefore the similarity between user behavior
items and candidate item can be approximated by their frequency of having the
same hash codes (signatures), or the collision probability. This leads us to
hypothesize that the probability of hash collision may be an effective
estimator that approximates user interests.

Based on this observation, we propose a new method to obtain the user interest
given a candidate item. After hashing, we directly form the user interest by
summing together behavior items $\mathbf{s}_{j}$ associated with the candidate
item $\mathbf{q}$ with the same signature. In a single hash $\mathbf{r}$, the
proposed method for estimating user interest can be formulated as:

(9)
$\ell_{2}\left(\mathbf{P}^{(\mathbf{r})}\mathbf{S}\right)=\ell_{2}\left(\sum_{j=1}^{L}p^{(\mathbf{r})}_{j}\mathbf{s}_{j}\right)$

where $\mathbf{S}$ is the user behavior sequence and $\mathbf{s}_{j}$ is the
$j$-th item in this sequence, $p^{(\mathbf{r})}_{j}=\\{0,1\\}$ specifies
whether $\mathbf{s}_{j}$ contributes to the user interests. Concretely, if
$\mathbf{s}_{j}$ shares the same hash signature with the candidate item
$\mathbf{q}$ under hash function $\mathbf{r}$, then $p^{(\mathbf{r})}_{j}=1$,
else $p^{(\mathbf{r})}_{j}=0$:

(10)
$p^{(\mathbf{r})}_{j}=\mathbbm{1}_{h(\mathbf{q},\mathbf{r})=h(\mathbf{s}_{j},\mathbf{r})}$

where $h(\cdot,\cdot)$ is defined in Eq. 5. $\ell_{2}(\cdot)$ in Eq. 9 refers
to the $\ell_{2}$ normalization, which is used to normalize the interest
distribution such that the dependencies sum up to 1.222We also tried to
normalize the distribution using the sum of $P^{(\mathbf{r})}_{j}$, and the
resulting model performs on par with $\ell_{2}$ normalized model. However, the
implementation of $\ell_{2}$ normalization will be more efficient, therefore
we use the $\ell_{2}$ normalization.

####  4.1.2. Multi-Round Hashing

There is always a small probability that dissimilar items share the same hash
codes with the candidate item, thus bringing noise to the model. To reduce
this probability, we use the multi-round hash algorithm described in Section
3.3.

Specifically, we use the $(m,\tau)$-parameterized SimHash algorithm. We sample
and perform $m$ times hashes in parallel, and merge the results of every
$\tau$ hash codes to form a new hash signature. We regard $\mathbf{s}_{j}$
collides with $\mathbf{q}$ only when they have the same value of aggregated
hash signature, i.e., the codes of $\mathbf{s}_{j}$ within a batch of
signature should be all the same with $\mathbf{q}$’s.

(11)
$\tilde{p}^{(\mathbf{R}_{i})}_{j}=\&_{k=1}^{\tau}p^{(\mathbf{r}_{i,k})}_{j},\quad\text{where}\
p^{(\mathbf{r}_{i,k})}_{j}=\mathbbm{1}_{h(\mathbf{q},\mathbf{r}_{i,k})=h(\mathbf{s}_{j},\mathbf{r}_{i,k})}$

The outputs of $m/\tau$ hash signatures are averaged for a low-variance
estimation of user interest. It can be formulated as:

(12) $\displaystyle\text{Attn}(\mathbf{q},\mathbf{S})$
$\displaystyle=\frac{1}{m/\tau}\sum_{i=1}^{m/\tau}\ell_{2}(\tilde{\mathbf{P}}^{(\mathbf{R}_{i})}\mathbf{S})$
$\displaystyle=\frac{1}{m/\tau}\sum_{i=1}^{m/\tau}\ell_{2}(\sum_{j=1}^{L}\tilde{p}^{(\mathbf{R}_{i})}_{j}\mathbf{s}_{j})$

The bottom of Figure 1 shows an example of $(4,2)$-parameterized SimHash
algorithm, where we use 4 hash functions and aggregate the results into 2 hash
signatures (yellow and green).

###  4.2. Analysis of Attention Patterns

####  4.2.1. Expectation of Hash Sampling-Based Attention

In our method, as $\mathbf{s}_{j}$ becomes more similar to $\mathbf{q}$, their
collision probability becomes higher and the expectation of the coefficient
$\tilde{p}_{j}$ is higher. It can prove that the expectation of
$\tilde{p}_{j}$ is (Charikar, 2002):

(13)
$\mathbb{E}\left[\tilde{p}_{j}\right]=\left(1-\frac{\arccos\left(\mathbf{q}^{\top}\mathbf{s}_{j}\right)}{\pi}\right)^{\tau}$

Therefore, the expectation of user interest representation produced by SDIM
is:

(14) $\displaystyle\mathbb{E}\left[\text{Attn}(\mathbf{q},\mathbf{S})\right]$
$\displaystyle=\mathbb{E}\left[\ell_{2}(\sum_{j=1}^{L}\tilde{p}^{(\mathbf{R}_{k})}_{j}\mathbf{s}_{j})\right]$
$\displaystyle=\frac{(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}{\sum_{j=1}^{L}(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}\cdot\mathbf{s}_{j}$

As the number of hash signatures $m/\tau$ increases, $\tilde{p}_{j}$ converges
to $\mathbb{E}\left[\tilde{p}_{j}\right]$, and
$\text{Attn}(\mathbf{q},\mathbf{S})$ converges to
$\mathbb{E}\left[\text{Attn}(\mathbf{q},\mathbf{S})\right]$. The empirical
results show that when $m/\tau\geq 16$, the estimation error will be very
small. In practice, we use $m=48$ and $\tau=3$ for our online model.

We plot the attention weights
$\left((1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{3}\right)$
produced by SDIM in Figure 2. For comparison, we also plot the attention
weights $\left(\exp(\mathbf{q}^{\top}\mathbf{s}_{j}/0.5)\right)$ produced by
target attention in the same figure. From Figure 2, we can see that the
attention weights of the proposed model align well with the exponential
function in softmax in target attention. Therefore, theoretically, our method
can obtain outputs that are very close to the target attention. We name the
proposed method as SDIM, which means Sampling-based Deep Interest Modeling.

Figure 2. Visualization of attention weights produced by target attention and
our model. We left shift the curve of target attention by one unit
($\exp((x-1)/\sqrt{d})$) such that the input is in $[-1,1]$ (Since the weights
will be normalize, this will not change the attention weights). It can be seen
that the proposed model produces very similar attention patterns as the target
attention.

####  4.2.2. The Property of $\tau$ and Relation to Other Methods

In this subsection, we describe that the width parameter $\tau$ in SDIM plays
a role in controlling the strength of the model on paying more attention to
more similar items.

Denote $w_{j}$ as the attention weight of target item $\mathbf{q}$ to item
$\mathbf{s}_{j}$, i.e.,

(15)
$w_{j}=\frac{(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}{\sum_{j=1}^{L}(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}$

As $\tau$ increases, the entropy of the attention distribution $H(w_{j})$
decreases strictly (the proof is in Appendix), and the distribution of
$\mathbf{w}$ becomes sharper on large similarity region, which encourages the
model to pay more attention to more similar items.

Let us consider two extreme cases:

  * •

When $\tau\rightarrow+\infty$ (can be approximated by assigning a large
value), the algorithm only attends to items that are exactly the same as the
candidate item. If we use the category attributes for hashing, then the
algorithm behaviors like SIM (hard) (Pi et al., 2020). Therefore, our
algorithm can be seen as an extension of SIM (hard), where it will also
considers very similar behavior items but with different category ids.

  * •

When $\tau=0$, or $m=1$, the algorithm degenerates into Mean Pooling as the
target item and user behavior items will always have the same hash signature.

Therefore, SDIM is very flexible that can model different attention patterns
by assigning different value of $\tau$.

Method | Training | Online-Serving
---|---|---
DIN | $O(BLd)$ | $O(BLd)$
SIM | $O(B\log(M)+Bkd)$ | $O(B\log(M)+Bkd)$
ETA | $O(Lm\log(d)+BLm+Bkd)$ | $O(BLm+Bkd)$
SDIM | $O(Lm\log(d)+Bm\log(d))$ | $O(Bm\log(d))$
Table 1.  Time complexity of different methods at training and online-serving
stage. $B$ is the number of candidate items for each request, $m$ is the
number of hashes, $L$ and $k$ are the length of original and retrieved user
behavior sequence respectively, $M$ is the size of attribute inverted index in
SIM, and $d$ is the model’s hidden size. In our system, $B$ is about $10^{3}$,
$L=1024$, $m=48$, and $d=128$. Figure 3. Illustration of our online CTR model.
The model takes user interest features, item features and context features as
inputs to predict the click probability corresponds to each candidate item.

###  4.3. Implementation and Complexity Analysis

In this subsection, we elaborate that SDIM is sizable times faster than
standard attention-based methods.

Let’s review the formulation for calculating user interest in target attention
(Eq. 4). This algorithm first gets the attention weights by multiplying the
target vector with the behavior sequence, followed by a weighted sum of the
behavior sequence using the attention weights, as shown in the upper part in
Figure 4. Therefore, two matrix multiplications are needed for the
representation of user interest in target attention, and the time complexity
of this algorithm is $O(BLd)$.

SDIM decouples the calculation of user interest into two parts: (1) behavior
sequence hashing, and (2) target vector hashing. Note that user behavior
sequence are users’ inherent features and is independent of the candidate
item, which means that the results of users’ behavior sequence hashing are
fixed no matter what the candidate item is. Therefore for each user, we only
need to compute the hash transform of user behavior sequence once in each
request, as shown in the right part in Figure 4. As a result, SDIM reduces $B$
to 1 in the time complexity, thus is sizable times faster than the standard
target attention. After hashing, sequence items that share the same hash
signature with the target item are selected and summed together to form the
user interest. In Tensorflow, this step can be implemented via a
$\mathbf{tf.batch\\_gather}$ operator, which is an atomic operator of
Tensorflow and the time cost is negligible.

The most time-consuming part of SDIM is the multi-round hashing of the
behavior sequence, i.e., transform a $d$-dimensional matrix into
$m$-dimensional hash codes. The time complexity of this operation is $O(Lmd)$
and can be reduced to $O(Lm\log(d))$ using the Approximating Random Projection
algorithm (Andoni et al., 2015). Since $m\ll B$ and $\log(d)\ll d$, SDIM is
much faster than standard attention-based methods. In our scenario, SDIM
achieves 10x-20x speedups in training the user behavior modeling part.

Figure 4. Overview of the user interest modeling of target attention and SDIM.

###  4.4. Deployment of the Whole System

We introduce how we successfully deploy SDIM online in this subsection. As
described above, the whole algorithm is decoupled into two parts: (1) behavior
sequence hashing, and (2) target vector hashing. The behavior sequence hashing
is independent of the candidate item, which motivates us to build a
specialized server to maintain user-wise behavioral sequence hashes.

We divide our system into two parts: behavior Sequence Encoding (BSE) server
and CTR Server, as shown in Figure 1. The BSE server is responsible for
maintaining user-wise behavior sequence hashes. When received real-time user
behaviors, BSE server samples from multiple hash functions and generates hash
signatures for each item in behavior sequence. The items are then assigned to
different buckets according to their signatures, where each bucket corresponds
to a hash signature, as shown in Figure 1. The hash buckets are passed to the
CTR Server to model item-aware user interests.

The CTR Server is responsible for predicting the click probability of
candidate items. When received a batch of $B$ candidate items, the CTR Server
hashes each item into signatures, and gathers item representations from the
corresponding buckets. The user interest features concatenated with other
features are fed to a complex CTR model to get the predicted probabilities of
each item. The overall structure of our CTR model is shown in Figure 3. The
model takes item features, context features, short-term user interest
features, and long-term user interest features as inputs, and uses a multi-
layer perceptron to predict the click probability of candidate items. The
proposed framework is end-to-end at the training stage: the user interest
modeling part is jointly trained with the rest of the CTR model, and we deploy
them separately only at the online serving stage. Please note that SDIM is
architecture-free and can be applied to any structure of CTR models.

After decoupling BSE and CTR Server, the computation of the BSE is latency-
free for the CTR Server. In practice, We put the BSE Server before the CTR
Server and compute it in parallel with the retrieval module.

After deploying separately, the time cost of calculating user’s long-term
interest only lies in the hashing of candidate items, which has a
$O(Bm\log(d))$ time complexity and is independent of the sequence length $L$,
which means that our framework can handle the user interest modeling with
extremely long behaviors theoretically. From the perspective of CTR Server,
this time complexity is just feel like adding a common feature. In Table 1, we
compare the time complexity of different methods333Since UBR4CTR uses a
complex neural network to select features, its time complexity cannot be
accurately estimated..

Our serving system is somewhat similar to MIMN (Pi et al., 2019). The biggest
difference is that our system can model users’ deep interests, while MIMN can
only model shallow interests.

####  4.4.1. Remark on Transmission Cost of Servers

For each request, we need to transmit bucket representations from the BSE
server to the CTR server. Notice that we use a fixed number of hash functions,
therefore no matter how long the user’s behavior is, we only need to transmit
fixed-length vectors of bucket representations to the CTR server. In our
online system, the size of this vector is 8KB and the transmission cost is
about 1ms.

##  5\. Experiments

###  5.1. Dadaset and Evaluation Metrics

To verify the effectiveness of SDIM, we conduct experiments on both public and
real-world industrial datasets. For public dataset, we follow previous work
(Pi et al., 2019; Pi et al., 2020; Chen et al., 2021) to choose Taobao
dataset444https://tianchi.aliyun.com/dataset/dataDetail?dataId=649. For
industrial dataset, we use real-world data collected from the Meituan search
system for experiments.

Taobao Dataset: Taobao dataset is released by (Zhu et al., 2018) and is widely
used for offline experiments in previous work (Qin et al., 2020; Pi et al.,
2020). Each instance in this dataset is consist of five fields of features:
user ID, item ID, category ID, behavior type, and timestamp. Following (Qin et
al., 2020), we additionally introduce the feature of ”is_weekend” according to
the timestamp to enrich context features. We pre-process the data in the same
way with MIMN (Pi et al., 2019) and ETA (Chen et al., 2021). Concretely, we
use the $1$st to $(L-1)$-th behaviors as inputs to predict the $L$-th
behavior. We split the samples into training set (80%), validation set (10%),
and test set (10%) according to the timestep. The recent 16 behaviors are
selected as short-term sequence, and the recent 256 behaviors are selected as
long-term sequence.

Industrial Dataset: This dataset is collected from the platform searching
system of Mobile Meituan APP, which is the largest e-commerce platform for
lifestyle services in China. We select consecutive 14-day samples for training
and the next two days for evaluation and testing, the number of training
examples is about 10 billion. The recent 50 behaviors are selected as short-
term sequence, and the recent 1,024 behaviors are selected as long-term
sequence. If the number of user behaviors doesn’t reach this length, then we
pad the sequence to the maximum length with the default value. Besides the
user behavior features, we additionally introduce about 20 important id
features to enrich the inputs.

Evaluation Metrics: For offline experiments, we follow previous work to adopt
the widely used Area Under Curve (AUC) for evaluation. We also use the
Training & Inference Speed (T&I Speed) as a supplement metric to show the
efficiency of each model. For online experiments, we use CTR (Click-Through
Rate) and VBR (Visited-Buy Rate) as online metrics.

###  5.2. Competitive Models

Following previous work (Chen et al., 2021; Pi et al., 2020), we compare SDIM
with the following mainstream industrial models for modeling long-term user
behaviors:

  * •

DIN (Zhou et al., 2018). DIN is one of the most popular models for modeling
user interest in industrial systems. However, DIN is infeasible to be deployed
on modeling long-term user behaviors due to its high time complexity. In this
baseline, we only use the short-term user behavior features but not long-term
features.

  * •

DIN (Long Seq.). For offline experiments, to measure the information gain of
long-term user behavior sequences, we equip DIN with long behavior sequences.
We set $L=256$ for Taobao dataset and $L=1024$ for industrial dataset.

  * •

DIN (Avg-Pooling Long Seq.). This baseline is introduced by (Chen et al.,
2021) and (Pi et al., 2020), where DIN is applied to modeling short-term user
interest, and the long-term user interest is obtained by a mean pooling
operation on long-term behaviors. We denote this baseline as DIN(Avg-Pooling).

  * •

SIM (Pi et al., 2020). SIM first retrieves top-$k$ similar items from the
whole sequence via category id, and then applies target attention on top-$k$
items to get user interest. We follow previous work to compare SIM(hard) as
the performance are almost the same they deploy SIM(hard) online.

  * •

UBR4CTR (Qin et al., 2020). UBR4CTR is a two-stage method. At the first stage,
they design a feature selection module to select features to form the query,
and store the user behaviors in an inverted index manner. At the second stage,
the retrieved behaviors are fed to a target attention-based module to get user
interest.

  * •

ETA (Chen et al., 2021). ETA applies LSH to encode the target item and user
behavior sequence into binary codes, and then computes the item-wise hamming
distance to select top-$k$ similar items for subsequent target attention.

MIMN (Pi et al., 2019) is proposed by the same team with SIM. As the authors
claim that SIM defeats MIMN and they deploy SIM online, we only compare with
SIM and omit the baseline of MIMN for the space limitation.

For all the baselines and SDIM, we use the same features (include timeinfo
features) as input and adopt the same model structure except for the long-term
user behavior modeling module. All models use the same length of long-term
user behaviors (T=256 for Taobao and T=1024 for industrial dataset).

##  6\. Results and Analysis

###  6.1. Results on Taobao Dataset

Method | AUC $\uparrow$ | T&I Speed $\uparrow$
---|---|---
DIN(Long Seq.) (Zhou et al., 2018) | 0.8848 | -
DIN (Zhou et al., 2018) | 0.8627* | 7.4x
DIN(Avg-Pooling) (Chen et al., 2021; Pi et al., 2020) | 0.8669* | 2.6x
SIM (Pi et al., 2020) | 0.8692* | 2.4x
UBR4CTR (Qin et al., 2020) | 0.8752* | 0.8x
ETA (Chen et al., 2021) | 0.8753* | 1.8x
SDIM | 0.8854 | 5.0x
Table 2.  Performance comparison of different model on Taobao dataset. The Training-Speed improvements are calculated on the basis of DIN(Long Seq.). ”*” indicates that the improvement of SDIM over this baseline is statistically significant at p-value ¡ 0.05 over paired Wilcoxon-test. Method | AUC | T&I Speed
---|---|---
DIN(Long Seq.) (Zhou et al., 2018) | 0.7049 | -
DIN (Zhou et al., 2018) | 0.6652* | 13.5x
DIN(Avg-Pooling) (Chen et al., 2021; Pi et al., 2020) | 0.6749* | 11.0x
SIM (Pi et al., 2020) | 0.6852* | 10.8x
UBR4CTR (Qin et al., 2020) | 0.6836* | 1.2x
ETA (Chen et al., 2021) | 0.6906* | 3.7x
SDIM | 0.7044 | 11.4x
Table 3.  Performance comparison of different model on Industrial dataset. The
Training-Speed improvements are calculated on the basis of DIN(Long Seq.). ”*”
indicates that the improvement of SDIM over this baseline is statiscally
significant at p-value ¡ 0.05 over paired Wilcoxon-test.

The overall results of different models on Taobao dataset are shown in Table
2. We can draw the following conclusions: (1) SDIM performs on par with
DIN(Long Seq.) on modeling long-term user behaviors, while being 5x times
faster. As described above, SDIM can simulate an attention pattern that very
similar as the target attention, therefore SDIM can match or even surpass the
performance of DIN(Long Seq.).

(2) SDIM performs better than all baseline models that are proposed for
modeling long-term user behaviors. Concretely, SDIM outperforms SIM by 1.62%,
outperforms UBR4CTR by 1.02%, and outperforms ETA by 1.01%. We also notice
that DIN(Long Seq.) brings 2.21% improvement on AUC compared to DIN, which
indicates the importance of modeling the long-term user behaviors for CTR
prediction. SIM, UBR4CTR and ETA performs worse than DIN(Long Seq.), which is
due to the loss of information caused by the retrieval of user behaviors.
These retrieval operations may be helpful in removing noise away from the
sequence, but is harmful when there is not enough informative behavior for
top-$k$ retrieval.

(3) SDIM is much more efficient than DIN(Long Seq.), SIM and UBR4CTR. The
efficiency improvement can be ascribed to reducing the time complexity of the
algorithm to $O(Lm\log(d))$. SDIM is also much more efficient than ETA (Chen
et al., 2021). ETA also use LSH to hash the target item and behavior sequence,
the time complexity of the hash operation is the same as SDIM. After hashing,
ETA calculates the hamming distance and selects top-$k$ items for target
attention, the time complexity is $O(BL+Bkd)$. While SDIM only introduces a
gather operator followed by a mean pooling of $m/\tau$ hashes, thus is much
more efficient than ETA.

###  6.2. Results on Industrial Dataset

Figure 5. AUC results of SDIM on industrial dataset when altering the number
of hashes $m$.

The overall results of different models on industrial dataset are shown in
Table 3. Similar to the results from Taobao dataset, SDIM outperforms all
competitive baselines, and performs on par with DIN(Long Seq.). Our SDIM
achieves 1.92%, 2.08%, 1.38% improvements compared with SIM, UBR4CTR, and ETA
respectively, while being much faster than these methods.

Since the user sequence length in industrial Dataset is large enough which is
friendly to retrieve-based methods, it seems that they should perform on par
with DIN(Long Seq.). However, the results in Table 3 show that their
performance has some gaps with DIN(Long Seq.). We argue that this is because
user’s interest are typically diverse and people often want to buy new
categories of goods, especially in our food search cases. When faced with a
candidate item in a new category, it’s difficult for these retrieve algorithms
to accurately pick out the most valuable items from users’ historical
behaviors.

Compared with the Taobao dataset, the industrial dataset contains more
candidate items per request, so SDIM can achieve more speedups on this
dataset. The industrial dataset also has longer user behavior sequences
(T=1024), so retrieve-based methods also achieve more speedups. The
experimental results demonstrate the superiority of SDIM.

###  6.3. Hyper-Parameter Analysis

There are two important hyper-parameters in SDIM: (1) the number of hashes
$m$, and (2) the width of hash signatures $\tau$.

####  6.3.1. Analysis on $m$

Hyper-Parameter |  AUC
---|---
$\tau=1$ |  0.6911
$\tau=2$ |  0.7032
$\tau=3$ |  0.7044
$\tau=5$ |  0.7034
$\tau=10$ |  0.6923
Table 4.  AUC results of SDIM on industrial dataset when altering the width
parameter $\tau$.

The number of hashes $m$ affects the estimation error of the proposed hashing-
based attention. As the number of sampled hash function increases, the
estimated user interest will be more close to
$\mathbb{E}\left[\text{Attn}(\mathbf{q},\mathbf{S})\right]$ in Eq. 14.

To assess the estimation error, we test the performance of SDIM using $m$
hashes, where $m\in\\{24,36,48,60,72,90,120\\}$. We also implement a variation
of SDIM that directly compute attention weights using the expected collision
probability $\mathbb{E}\left[\tilde{p}_{j}\right]$ in Eq. 13. This baseline
simulates the behavior of SDIM when the number of hash signatures tends to be
infinite. The results are shown in Figure 5. It can be seen that when $m>48$
the models perform almost the same. For the sake of efficiency, we use $m=48$
in our model.

####  6.3.2. Analysis on $\tau$

As we described in subsection 4.2.2, $\tau$ controls the strength of the model
on paying more attention to more similar items. We investigate different
attention patterns of SDIM by varying $\tau$ in {1,2,3,5,10}. The results are
shown in Table 4.

From Table 4, we can see that SDIM performs well when $2\leq\tau\leq 5$. For
the balance of effectiveness and efficiency, we use $\tau=3$ in our online
model. The model performs poorly when $\tau=1$ because it encodes too many
noise behaviors. On the contrary, the model performs poorly when $\tau=10$ as
only very similar items have the chance to contribute to user interest, which
is unfriendly to users with few behaviors.

###  6.4. Online A/B Test

Method | CTR | VBR | Inf. Time
---|---|---|---
Base(w/o long seq.) | - | - |  $\approx$ 60ms
DIN(T=2000) | can not deploy
SDIM(T=2000) | +2.98% | +2.69% | +1ms
Table 5.  Online A/B testing results.

A strict online A/B testing is also conducted to verify the effectiveness of
SDIM. For online A/B testing, the baseline model is the previous online CTR
model in Meituan search system, where only short-term user behavior sequences
are used. The test model adopts the same structure and features as the base
model, but incorporates a long-term user interests modeling module with users
recent 2,000 behaviors on this basis. We use the proposed SDIM to model long-
term user interests, and denote this test model as SDIM(T=2000). The testing
lasts for 14 days, with 10% of Meituan search traffic are distributed for each
model respectively. The results of A/B testing are shown in Table 5.

SDIM(T=2000) achieves 2.98% improvements ($p\text{-value}<0.001$) on CTR and
2.69% improvements ($p\text{-value}<0.005$) on VBR compared with the base
model, which can greatly increase online profit considering the large traffic
of Meituan APP. The inference time of SDIM(T=2000) increased by 1ms compared
with the Base(w/o long seq.). The increase in inference time is mostly caused
by the transmission time between BSE Server and CTR Server.

We also tried to deploy the model that directly uses the target attention to
model long-term user behavior sequences with $T=2000$. However, its inference
time is greatly increased by about 50% (25ms-30ms), which is unacceptable for
our system. Therefore we can’t leave this model online for 14 days for A/B
Testing. SDIM performs on par with this model, but saves 95% online inference
time. SDIM has now been deployed online and serve the main traffic of
Meituan’s home search system.

##  7\. Conclusions

In this paper, we propose a hash sampling-based method named SDIM for modeling
long-term user behaviors. Instead of designing complicated modules to retrieve
from long-term user behaviors, we directly gather behavior items associated
with the candidate item with the same hash signature to form the user
interest. We also propose a new online serving framework that decouples the
hashing of user behavior sequence from the entire model, which makes it
latency-free for the CTR server. We show that the proposed method performs on
par with DIN(Long Seq.), while being sizable times faster. SDIM has been
deployed online in Meituan APP.

Future work includes reducing the transmission cost, exploring more complex
structures such as multi-head hashing, and so on.

## References

  * (1)
  * Andoni et al. (2015) Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. 2015\.  Practical and Optimal LSH for Angular Distance. In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_. 1225–1233.  https://proceedings.neurips.cc/paper/2015/hash/2823f4797102ce1a1aec05359cc16dd9-Abstract.html
  * Charikar (2002) Moses Charikar. 2002\.  Similarity estimation techniques from rounding algorithms. In _Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada_ , John H. Reif (Ed.). ACM, 380–388.  https://doi.org/10.1145/509907.509965
  * Chen et al. (2021) Qiwei Chen, Changhua Pei, Shanshan Lv, Chao Li, Junfeng Ge, and Wenwu Ou. 2021\.  End-to-End User Behavior Retrieval in Click-Through RatePrediction Model.  _CoRR_ abs/2108.04468 (2021).  arXiv:2108.04468 https://arxiv.org/abs/2108.04468
  * Cheng et al. (2016) Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, Rohan Anil, Zakaria Haque, Lichan Hong, Vihan Jain, Xiaobing Liu, and Hemal Shah. 2016\.  Wide & Deep Learning for Recommender Systems. In _Proceedings of the 1st Workshop on Deep Learning for Recommender Systems, DLRS@RecSys 2016, Boston, MA, USA, September 15, 2016_. ACM, 7–10.  https://doi.org/10.1145/2988450.2988454
  * Feng et al. (2019) Yufei Feng, Fuyu Lv, Weichen Shen, Menghan Wang, Fei Sun, Yu Zhu, and Keping Yang. 2019.  Deep Session Interest Network for Click-Through Rate Prediction. In _IJCAI 2019, Macao, China, August 10-16, 2019_. ijcai.org, 2301–2307.  https://doi.org/10.24963/ijcai.2019/319
  * Guo et al. (2017) Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017.  DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. In _IJCAI 2017, Melbourne, Australia, August 19-25, 2017_. ijcai.org, 1725–1731.  https://doi.org/10.24963/ijcai.2017/239
  * Kang and McAuley (2018) Wang-Cheng Kang and Julian J. McAuley. 2018.  Self-Attentive Sequential Recommendation. In _IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17-20, 2018_. IEEE Computer Society, 197–206.  https://doi.org/10.1109/ICDM.2018.00035
  * Kitaev et al. (2020) Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. 2020\.  Reformer: The Efficient Transformer. In _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net.  https://openreview.net/forum?id=rkgNKkHtvB
  * Leskovec et al. (2014) Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. 2014\.  _Mining of Massive Datasets, 2nd Ed_.  Cambridge University Press.  http://www.mmds.org/
  * Li et al. (2019) Chao Li, Zhiyuan Liu, Mengmeng Wu, Yuchi Xu, Huan Zhao, Pipei Huang, Guoliang Kang, Qiwei Chen, Wei Li, and Dik Lun Lee. 2019\.  Multi-Interest Network with Dynamic Routing for Recommendation at Tmall. In _Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019_. ACM, 2615–2623.  https://doi.org/10.1145/3357384.3357814
  * Manku et al. (2007) Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma. 2007\.  Detecting near-duplicates for web crawling. In _WWW 2007, Banff, Alberta, Canada, May 8-12, 2007_. ACM, 141–150.  https://doi.org/10.1145/1242572.1242592
  * Pi et al. (2019) Qi Pi, Weijie Bian, Guorui Zhou, Xiaoqiang Zhu, and Kun Gai. 2019.  Practice on Long Sequential User Behavior Modeling for Click-Through Rate Prediction. In _KDD 2019, Anchorage, AK, USA, August 4-8, 2019_. ACM, 2671–2679.  https://doi.org/10.1145/3292500.3330666
  * Pi et al. (2020) Qi Pi, Guorui Zhou, Yujing Zhang, Zhe Wang, Lejian Ren, Ying Fan, Xiaoqiang Zhu, and Kun Gai. 2020\.  Search-based User Interest Modeling with Lifelong Sequential Behavior Data for Click-Through Rate Prediction. In _CIKM ’20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020_. ACM, 2685–2692.  https://doi.org/10.1145/3340531.3412744
  * Qin et al. (2020) Jiarui Qin, Weinan Zhang, Xin Wu, Jiarui Jin, Yuchen Fang, and Yong Yu. 2020\.  User Behavior Retrieval for Click-Through Rate Prediction. In _SIGIR 2020, Virtual Event, China, July 25-30, 2020_. ACM, 2347–2356.  https://doi.org/10.1145/3397271.3401440
  * Qu et al. (2016) Yanru Qu, Han Cai, Kan Ren, Weinan Zhang, Yong Yu, Ying Wen, and Jun Wang. 2016.  Product-Based Neural Networks for User Response Prediction. In _IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain_. IEEE Computer Society, 1149–1154.  https://doi.org/10.1109/ICDM.2016.0151
  * Ren et al. (2019) Kan Ren, Jiarui Qin, Yuchen Fang, Weinan Zhang, Lei Zheng, Weijie Bian, Guorui Zhou, Jian Xu, Yong Yu, Xiaoqiang Zhu, and Kun Gai. 2019.  Lifelong Sequential Modeling with Personalized Memorization for User Response Prediction. In _SIGIR 2019, Paris, France, July 21-25, 2019_. ACM, 565–574.  https://doi.org/10.1145/3331184.3331230
  * Rendle (2010) Steffen Rendle. 2010\.  Factorization Machines. In _ICDM 2010, The 10th IEEE International Conference on Data Mining, Sydney, Australia, 14-17 December 2010_. IEEE Computer Society, 995–1000.  https://doi.org/10.1109/ICDM.2010.127
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang. 2018.  Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding. In _WSDM 2018, Marina Del Rey, CA, USA, February 5-9, 2018_. ACM, 565–573.  https://doi.org/10.1145/3159652.3159656
  * Wang et al. (2017) Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. 2017\.  Deep & Cross Network for Ad Click Predictions. In _Proceedings of the ADKDD’17, Halifax, NS, Canada, August 13 - 17, 2017_. ACM, 12:1–12:7.  https://doi.org/10.1145/3124749.3124754
  * Wang et al. (2020) Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. 2020.  Linformer: Self-Attention with Linear Complexity.  _CoRR_ abs/2006.04768 (2020).  arXiv:2006.04768 https://arxiv.org/abs/2006.04768
  * Zeng et al. (2021) Zhanpeng Zeng, Yunyang Xiong, Sathya N. Ravi, Shailesh Acharya, Glenn Moo Fung, and Vikas Singh. 2021\.  You Only Sample (Almost) Once: Linear Cost Self-Attention Via Bernoulli Sampling. In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ _(Proceedings of Machine Learning Research, Vol. 139)_ , Marina Meila and Tong Zhang (Eds.). PMLR, 12321–12332.  http://proceedings.mlr.press/v139/zeng21a.html
  * Zhou et al. (2019) Guorui Zhou, Na Mou, Ying Fan, Qi Pi, Weijie Bian, Chang Zhou, Xiaoqiang Zhu, and Kun Gai. 2019.  Deep Interest Evolution Network for Click-Through Rate Prediction. In _AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019_. AAAI Press, 5941–5948.  https://doi.org/10.1609/aaai.v33i01.33015941
  * Zhou et al. (2018) Guorui Zhou, Xiaoqiang Zhu, Chengru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. 2018\.  Deep Interest Network for Click-Through Rate Prediction. In _KDD 2018, London, UK, August 19-23, 2018_. ACM, 1059–1068.  https://doi.org/10.1145/3219819.3219823
  * Zhou et al. (2021) Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. 2021.  Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting. In _AAAI 2021, Virtual Event, February 2-9, 2021_. AAAI Press, 11106–11115.  https://ojs.aaai.org/index.php/AAAI/article/view/17325
  * Zhu et al. (2018) Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. 2018.  Learning Tree-based Deep Model for Recommender Systems. In _KDD 2018, London, UK, August 19-23, 2018_. ACM, 1079–1088.  https://doi.org/10.1145/3219819.3219826

##  Appendix A Proof of the Monotone Decreasing of Entropy in Eq. 15

Given a distribution as:

(16)
$W(j)=\frac{(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}{\sum_{j=1}^{L}(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}}$

we prove that the entropy $H(W(j))$ decreases strictly as the temperature
$\tau$ increases.

Denote $P(j)=(1-\frac{\arccos(\mathbf{q}^{\top}\mathbf{s}_{j})}{\pi})^{\tau}$,
the entropy $H(W(j))$ can be written as follows:

(17) $\begin{split}H(W(j))&=-\sum_{j=1}^{L}W(j)\cdot\log(W(j))\\\
&=\log\left(\sum_{j=1}^{L}P(j)\right)-\frac{\sum_{j=1}^{L}P(j)\cdot\log(P(j))}{\sum_{j=1}^{L}P(j)}\end{split}$

According to the chain rule, the gradient of $H(W(j))$ with respect to $\tau$
is: $\frac{\partial H}{\partial\tau}=\sum_{j}\frac{\partial H}{\partial
P(j)}\cdot\frac{\partial P(j)}{\partial\tau}$. The first term $\frac{\partial
H}{\partial P(j)}$ can be calculated as:

(18) $\frac{\partial H}{\partial P(j)}=\frac{\sum_{j=1}^{L}P(j)\log
P(j)}{(\sum_{j=1}^{L}P(j))^{2}}-\frac{\log P(j)}{\sum_{j=1}^{L}P(j)}$

and the second term $\frac{\partial P(j)}{\partial\tau}$ can be calculated as:

(19) $\frac{\partial P(j)}{\partial\tau}=\frac{1}{\tau}P(j)\log P(j)$

Therefore, we have:

(20) $\displaystyle\frac{\partial H}{\partial\tau}$
$\displaystyle=\sum_{j=1}^{L}\frac{\partial H}{\partial
P(j)}\cdot\frac{\partial P(j)}{\partial\tau}$
$\displaystyle=\frac{\left(\sum_{j=1}^{L}P(j)\cdot\log(P(j))\right)^{2}-\sum_{j=1}^{L}P(j)\sum_{j=1}^{L}P(j)(\log
P(j))^{2}}{\tau\cdot\left(\sum_{j=1}^{L}P(j)\right)^{2}}$

Since $P(j)>0$, we can apply the Cauchy inequality to the numerator part of
Eq. 20:

(21) $\begin{split}&\sum_{j=1}^{L}P(j)\sum_{j=1}^{L}P(j)(\log P(j))^{2}\\\
=&\sum_{j=1}^{L}\sqrt{P(j)}^{2}\sum_{j=1}^{L}(\sqrt{P(j)}\cdot\log(P(j)))^{2}\\\
\geq&\left(\sum_{j=1}^{L}P(j)\cdot\log(P(j))\right)^{2}\end{split}$

Combining Eq. 20 and Eq. 21, we have $\frac{\partial H}{\partial\tau}\leq 0$.
Therefore, the entropy is monotonically decreasing as the $\tau$ increases.