Intention2Basket: A Neural Intention-driven Approach for Dynamic Next-basket Planning

1 Introduction

Human behaviors are usually complex, uncertain and dynamic [Cone, 2012], which brings great challenges to model and predict them. For instance, purchasing a basket of products is a common user behaviour in our daily life but is hard to precisely predict. Psychologists have been trying to deeply reveal the essential complexities in human behaviours and indicate that human behaviours are essentially driven by certain inner intentions and one intention is usually accomplished by a series of actions with certain utilities [Ajzen et al., 2009]. Inspired by this, in this paper, we take the next-basket prediction problem as a typical example to study the complex user behaviours from the Psychological perspective, where the choices on a variety of items across shopping baskets form the user action sequence.

∗Corresponding author.

The commonly recognized Psychological theories [Albarracin and Wyer Jr, 2000; Albarracin et al., 2001] have revealed the complex relations between user behaviour and intentions. On the one hand, a user's behaviours are driven by a variety of heterogeneous intentions to achieve a certain goal and different intentions may influence each other. Specifically, a user's future actions are decided by the current intention states (i.e., intention accomplishment status) and are taken to accomplish the corresponding intentions. On the other hand, the user's intentions are disclosed by the happened actions and the state of each intention depends on the actions that have been taken for it. Furthermore, the goal (e.g., a shopping basket) is achieved on the basis of the perfect accomplishment of each intention [Wang et al., 2020].

However, most of the existing next-basket prediction approaches make predictions by simply modelling a user's actions in a sequence of shopping baskets as homogeneous time series data points, e.g., the stock price. Markov chain based approaches and Recurrent Neural Networks (RNN) based approaches are the two most representative approaches for nextbasket prediction. Markov chain based ones [Rendle and et al., 2010] mechanically factorize the overall transition matrix over items from adjacent baskets without differentiating the possible heterogeneous intentions behind different transitions and thus fail to capture the complex and heterogeneous dependencies over items across baskets. RNN-based ones [Yu et al., 2016; Le et al., 2019] model the inter-basket sequential dependencies by treating all the baskets in a sequence as homogeneous data points with rigid order. Therefore, they are not able to capture the complex and heterogeneous transitions over items for various intentions across baskets. As a result, all these approaches fail to consider the humans' heterogeneous intentions behind their choice actions in baskets, let alone well accomplish a user's different intentions to achieve his/her goal with a good basket planning procedure.

In this paper, inspired by the aforementioned Psychological theories on human behaviour reasoning and formation, we propose Int2Ba to deeply model the complex and heterogeneous user behaviours in a sequence of shopping baskets for better planning the next-basket. First, we design Intention Recognizer as a component of Int2Ba to automatically recognize the user's possible intentions behind the observed choices on items in baskets and then build an intentionspecific action representation by integrating the embeddings of all the items associated with the same intention in each basket. All the actions for the same intention across baskets constitute a chain for accomplishing the corresponding intention. Second, we devise Coupled Intention Chain Nets (CICN) to model the state transitions of different intentions along with the actions taken in the corresponding chains. Each Intention Chain Net (ICN) in CICN models one intention. Since different intentions may influence each other, accordingly, we particularly design Coupled Intention Unit (CIU) as the basic cell of ICN to model the intra-intention state transitions while incorporating the inter-intention influence. Consequently, the current state of each intention is obtained as the intention representation to guide the subsequent basket generation. Finally, we specifically design a Dynamic Basket Planner (DBP) to generate the next basket with a maximumutility optimizer in an iterative way, which can more effectively model the real-world basket formation process where items are put into a basket step by step. Hence, the basket with the highest utility generated in the last iteration is selected as the next-basket to best accomplish all the intentions.

The main contributions of our work are summarized below:

• We propose intention modelling for in-depth understanding of complex and heterogeneous user behaviours from the Psychological perspective.
• We design Int2Ba to model the heterogeneous intentions behind the user's complex behaviours. Specially, Intention Recognizer, CICN and DBP are devised to recognize, model and accomplish intentions respectively.
• Int2Ba is demonstrated by being applied to next-basket prediction to model the heterogeneous intentions which drive the complex purchasing actions.

2 RelatedWork

The existing work on next-basket prediction can be generally categorized into pattern-mining based, Markov chain based and neural network based approaches [Wang et al., 2019b].

Pattern mining is an intuitive solution to next-basket prediction by utilizing the mined sequence patterns as guidance. For example, Temporal Annotated Recurring Sequence was proposed to capture different factors (e.g., co-occurrence and sequentuality) influencing user choices for next-basket predictions [Guidotti and et al., 2018]. Pattern-mining based approaches usually focus on the frequent items while ignoring less-frequent ones, and reducing prediction performance.

Markov chain models are an alternative solution to avoid this drawback. Particularly, the Factorized Personalized Markov Chains (FPMC) was proposed for next-basket prediction by factorizing the transition matrix built on underlying Markov chains over items from adjacent baskets [Rendle and et al., 2010]. However, FPMC only captures the firstorder dependencies while ignoring higher-order ones, leading to poor performance on next-basket prediction [Wang et al., 2017; Wang et al., 2018; Lian et al., 2020b].

In recent years, various neural networks were employed for next-basket prediction. [Wang et al., 2015] constructed a hybrid representation of the last basket using shallow neural networks to predict the next basket, but it still only captures firstorder dependencies. Different from shallow neural networks, deep neural networks like RNN are more powerful in modeling complex dependencies due to their complex architectures. For example, a Dynamic REcurrent bAsket Model (DREAM) was proposed in [Yu et al., 2016] to learn the dynamic representation of a user and global sequential features across baskets for next-basket recommendations. An RNN-based sequence encoder was developed to incorporate the intra-basket correlations for predicting more coherent next basket [Le et al., 2019]. Attention mechanism was incorporated into RNN by [Bai et al., 2018] to highlight those more relevant items for next-basket prediction. RNN-based approaches can capture higher-order dependencies across multiple baskets, but they may also generate false dependencies due to the employed rigid order assumption over the baskets and bias to the recent baskets due to the memory decay [Wang et al., 2019a].

In summary, all these aforementioned works mechanically model users' behaviours in shopping baskets as homogeneous sequence data without considering the human's intentions behind, impeding the deep understanding of user behaviours. Consequently, the next-basket prediction performance is reduced. Very limited works have been reported to consider intention in users' behaviour modelling from our observation. [Chen et al., 2019] employed attention mechanism to predict users' category-wise intention, which was defined as an arbitrary pair of action type and item category, totally different from the Psychology intention in our work. In practice, the Psychology theories [Albarracin et al., 2001] have indicated that users' actions are driven by certain intentions and one intention is accomplished by the corresponding choice actions with good utility. Inspired by these, we develop Int2Ba to model the users' complex and heterogeneous actions in next-basket prediction by recognizing, modelling and accomplishing the intentions behind actions successively.

3 Problem Statement

Given a transaction dataset, D = {s1, ..., s|D|} denotes a collection of sequences of shopping baskets (called baskets for short), where each sequence s = {b1, ..., b|s|}(s ∈ D) consists of a list of time-ordered baskets purchased by an anonymous user. |D| is the number of sequences in D. Each basket b = {v1, ..., v|b|}(b ∈ s) contains a collection of items purchased in one transaction without rigid order. All the items in the whole dataset constitute the universal item set V = {v1, ..., v|V |}. For a target basket bt(bt ∈ s) to be predicted, all the baskets occurring prior to bt in s together form its sequential context (called context for short), denoted as Cbt = {b1, ..., bt-1} where each basket b ∈ Cbt is a contextual basket and each item v ∈ b is a contextual item. Given a context C with preceding (t - 1) baskets, a next-basket planner is to plan the items for the tth basket bt to best accomplish the intentions embeded in the context.

4 Intention2Basket Model

The architecture of our proposed Intention2Basket (Int2Ba for short) is shown in Figure 1 (a). Int2Ba is mainly comprised of three components: (1) Intention Recognizer, (2) Coupled Intention Chain Nets (CICN), and (3) Dynamic Basket Planner (DBP). An intention recognizer first recognizes the intentions behind the items in each contextual basket and accordingly builds the intention-specific action representation as the input of CICN. CICN models the state transitions of different intentions and accordingly generates an intention representation for basket generation. DBP iteratively generates baskets to best accomplish all the recognized intentions.

4.1 Intention Recognizer

Given the items in each contextual basket, intention recognizer discovers the potential intentions behind them. Given item vi, its embedding vi ∈ We is input into the intention recognizer to compute the probability αi,k of the kth intention to drive the choice on vi. We ∈ RK×|V | is the embedding matrix and softmax is employed to fit the case that sometimes there may be several intentions behind one item.

where Wf ∈ RK×m is the intention filtering matrix, and m is the number of possible intentions which is tuned by cross validation. τ ∈ (0,+∞) is the temperature parameter [Jang et al., 2017] to tune, when τ → 0+, vi tends to be driven by a single intention. In this paper, τ is empirically set to 0.01.

Then, the intention-specific action representation aj,k for the kth intention in the j th basket bj is calculated by integrating the embedings of items according to their intentions:

4.2 Coupled Intention Chain Nets (CICN)

CICN consists of m ICNs that are coupled together, where each for one intention as shown in Figure 1 (a). Each ICN is composed of (t-1) sequentially connected CIUs to model the corresponding intention state transitions while incorporating the inter-intention influence.

Coupled Intention Unit (CIU)

As mentioned in Section 1, different intentions usually influence each other in the sequential purchase behaviours [Morwitz, 2014]. Traditional RNN cells including Long ShortTermMemory (LSTM) [Shi and et al., 2015] and Gated Recurrent Unit (GRU) [Chung et al., 2014] are not capable of modelling such inter-intention influence since they are originally deigned for one homogeneous sequence and thus can model the state transitions within sequences only. To this end, we design CIUs to serve as the basic cells of each ICN. To be specific, a CIU first introduces an attention model to weigh the different importance scales of other intentions w.r.t. the current one and then introduces an influence gate to selectively absorb their states into that of the current intention, as shown by the green part in Figure 1 (b). Next, we formalize the work mechanism of the CIU step by step.

First, the update gate vector rj and reset gate vector zj in preparation for the subsequent state updating at the j th step in the current kth ICN are calculated below:

where σs is the activation function and is specified as sigmoid in this work. Wr and Wz are the weight matrices while br and bz are the corresponding bias.

Then we calculate the importance weights of all other intentions w.r.t. the current kth intention by employing a softmax function [Peng et al., 2017] as most attention models do. The importance weight for intention sate is:

Wa and ba are the attention filtering matrix and bias respectively. h(j-1,l) is the state at the (j-1)th step of lth intention.

With the attention weights, the states of all other intentions are integrated into a compound intention state hc(j-1) :

The influence weight to measure the degree to which the compound intention state can influence the current kth intention is calculated via a particularly designed influence gate:

whereWc andWg are the weighting matrices to be learned while σs is the sigmoid function.

The candidate intention state is calculated by taking the last state h(j-1,k), the compound state hcj-1 from other intentions, and the current action representation aj,k as the inputs:

Wo and bo are the weighting matrix and bias respectively.

Finally, the intention state is obtained by combining the last state and the candidate intention state with the reset gate:

The unified intention representation ht-1 is obtained by putting all the m intention states at the last step together:

4.3 Dynamic Basket Planner (DBP)

Existing next-basket predictors [Yu et al., 2016; Bai et al., 2018] often simply select those Top-K items with the highest probabilities at once to form the next-basket. However, such manner not only ignores the correlations between these K candidate items but also overlooks the increasing preceding items in the forming basket along with a user's choice actions, reducing the accomplishment of a user's intentions. To form the next basket in a way more approaching to the real-world cases where the items are put into the basket in multi-steps, we propose DBP to plan the next-basket with a maximumutility optimizer in an iterative way to better accomplish the user's intentions. Specifically, given the learned intentions, we generate a size-K basket with the maximum utility w.r.t. all the intentions by K steps. Next, we present DBP in detail.

A utility function U(·) is defined in the optimizer to measure the utility of each item or basket w.r.t. the accomplishment of an intention. In this paper, U(·) is specified as the inner product between the embedding v of the item or basket and the intention representation h to measure the interactions between them since a stronger interaction indicates better accomplishment of the intention [Louviere et al., 2000].

Given the representation h(t-1,k) of the kth intention, we select those Top-L (K ≤ L ≤ N) items with the highest utilities w.r.t. such intention from the whole item population to build an intention-specific candidate item set. L is a parameter to be tuned over specific datasets and is empirically set to 1,000 in this paper. K and N are the size of next-basket and the total number of items respectively. Then we employ an iterative generation process to generate the next-basket of size-K in K steps. In the first step, we select top-K items with the highest utilities from the whole item population to build K size-1 candidate baskets by taking each of them as one basket. In each of the following steps, first, we select Top-H items from each intention-specific candidate item set to get mH items and then we add each of them into each of the K baskets generated in the last step to form mHK new candidate baskets. Finally, we chose the Top-K ones with highest utilities w.r.t. all the intentions as the optimal ones. H is a parameter to be tuned in the specific dataset and is empirically set to 100 in our experiments. Following Eq. (11), the utility of a candidate basket ˆbt w.r.t. all the intentions in the context is calculated below:

where ˆbt = [ˆat,1, ..., ˆat,m] is the intention-specific basket representation. Finally, we generate K size-K candidate baskets and select the one with the highest utility.

4.4 Optimization Objective and Training

Ranking Loss

Each basket sequence used for the next-basket prediction is usually regarded as a context-target basket pair < C, bt >. Such data is referred to as one-class data [Hu et al., 2016] and learning from it is often treated as a ranking problem [Rendle and et al., 2009; Wu et al., 2019; Lian et al., 2020a]. Specifically, given a context C, a contrastive pair is constructed to specify the utility order b(C,x) ⪰ b(C,y) over a basket b(C,x) ∈ BC that is observed to match the context C and an unobserved basket b(C,y) /∈ BC, where BC is the set of target baskets w.r.t. the context C. Then the following max-margin loss [Lecun et al., 2006] is employed to optimize the ranking order over pairs:

where the margin needs to be tuned according to the range of utility values and is empirically set to 3 in this work.

Training Procedure

Our model is implemented using Tensorflow 1.11 and its parameters are learned based on a mini-batch learning procedure. Adam [Kingma and Ba, 2015] is used for gradient learning. The initial learning rate is empirically set to 0.001 and the batch size is set to 50.

5 Experiments and Evaluation

5.1 Data Preparation

Two real-world transaction datasets commonly used to test the performance of next-basket prediction [Guidotti and et al., 2018; Le et al., 2019] are used for the experiments: (1) Tmall 1 released by IJCAI-15 competition. It records the shopping baskets purchased by each anonymous user on Tmall.com (The Chinese version of Amazon) in six months. The purchase date of each basket is given while no timestamp for those items inside it; and (2) Tafeng 2 released on Kaggle. It contains the transaction data of a Chinese grocery store produced in four months, whose format is similar to Tmall.

First, all the purchased baskets by each user are ordered according to the purchase time to form a basket sequence s.

1 https://tianchi.aliyun.com/dataset/dataDetail?dataId=42

2 https://www.kaggle.com/chiranjivdas09/ta-feng-grocerydataset

Then, following the common practice for sequence data processing, given an s, we build training and test sequence instances of length t in the form of context-target basket pair < C, bt > (C = {b1, b2, ..., bt-1}) by using the sliding window technique [Tanbeer et al., 2009] when |s| ≥ t or padding and masking [Collins and et al., 2012] otherwise. To feed the data into the model well, t is fixed (i.e., 5 and 8 for Tmall and Tafeng respectively) according to the data characteristics. Finally, we randomly select 20%, 30% and 40% of the instances whose target basket happens in the last 30 days to form three test sets, while the reminder for the corresponding training set respectively. Our method consistently outperforms all the baselines on all the three splits, and only the results w.r.t. the 30% split are reported for saving space. The characteristics of experimental datasets are shown in Table 1.

5.2 Experimental Settings

Comparison Methods

Seven representative and state-of-the-art approaches built on various models are used as baselines. In addition, three simplified versions of our model are used for ablation analysis.

• TBP: a next-basket predictor using temporal annotated recurring sequences to capture different factors affecting users' choices [Guidotti and et al., 2018].
• FPMC: a Markov chain based next-basket predictor factorizing the transition matrix over items from adjacent baskets [Rendle and et al., 2010].
• HRM: a next-basket predictor building a hierarchical lastbasket representation for prediction [Wang et al., 2015].
• DERAM: a next-basket predictor using RNN to learn a dynamic representation of a user based on historical baskets for the prediction [Yu et al., 2016].
• NAM: a next-basket predictor incorporating attention mechanism into RNN for tracking users' evolving appetite for items for the prediction [Bai et al., 2018].
• Beacon: a state-of-the-art next-basket predictor using RNN to encode the basket sequences while considering intra-basket correlations [Le et al., 2019].
• MCPRN: a next-item predictor using mixed-channels to model different types of items [Wang et al., 2019a] and is modified to be applicable for next-basket prediction.
• Int2Ba-S: a simplified version of Int2Ba, which is composed of a single ICN based on the homogeneous intention assumption. It is built to verify the effectiveness of CICN of Int2Ba in handling heterogeneous intentions.
• Int2Ba-GRU: a simplified version of Int2Ba replacing the CIUs in Int2Ba with GRUs. It is to justify the efficacy of CIUs in modeling inter-intention influence.
• Int2Ba-Top-K: a simplified version of Int2Ba replacing the DBP in Int2Ba with commonly used Top-K next-basket predictor to demonstrate the effectiveness of DBP.

Evaluation Metrics

Four accuracy metrics, i.e., Recall, F-1 Score, Hit-Ratio (HR) and normalized Discounted Cumulative Gain (nDCG) that are commonly used to test the next-basket prediction performance [Bai et al., 2018; Liu et al., 2020] are employed to evaluate the performance of all comparison methods.

Parameter Settings

For a fair comparison, we first initialize each baseline model with the parameter settings in the original papers and then carefully tune them on our datasets for best performance. In our model, the dimensions of embeddings and intention states are empirically set to 100, while the number of channels m and the candidate number H in DBP is set to 3 and 100 respectively by tuning on the validation set.

5.3 Performance Evaluation and Analysis

Extensive experiments are conducted to evaluate our model in terms of accuracy by answering the following questions:

Q1: How does our Int2Ba perform compared with the baseline approaches in terms of prediction accuracy?

Q2: How does CICN modeling various heterogeneous intentions perform compared with a single ICN modeling only a homogeneous intention?

Q3: How does the CIU perform in modeling the interintention influence?

Q4: How does our DBP perform in accomplishing the various heterogeneous intentions?

Reply to Q1: Int2Ba vs. baselines. The prediction accuracy of our Int2Ba and those of the seven baselines are reported in Table 2. In TBP, the minimum item occurrence times in the whole dataset and the minimum number of baskets per user are empirically set to 5 and 10 respectively for the best performance. TBP is a frequent-pattern mining based approach with a user-centralized design, leading to its ignorance of infrequent items and poor performance on sparse data. The number of factors is set to 50 in FPMC for the best performance. Although it can cover more items and thus performs better than TBP, the strict assumption of first-order dependencies between any adjacent baskets prevents FPMC from being always in line with the real-world cases. The dimensions of both item embeddings and state vectors (if there is any) are empirically set to 100 in the other five baselines for best performance. Although HRM performs better by learning latent representations of baskets to relax the strict assumption in FPMC, it still only captures first-order dependencies. DERAM employs an RNN to model the higher-order dependencies over a sequence of baskets for more accurate prediction. NAM and Beacon incorporate the attention mechanism and intra-basket correlations into RNN respectively for better prediction. To avoid the noisy information from irrelevant items, MCPRN employs mixture-channel models built on RNN to model dependencies for different types of items independently. In summary, all these approaches not only ignore the heterogeneous intentions behind users' choice behaviours, but also form the next-basket by simply selecting the Top-K items with the highest probabilities, without considering the correlations between them, failing to better accomplish all the intentions by taking the basket as a whole. In contrast, by modeling the state transitions of different intentions over a sequence of baskets with different ICNs while considering the inter-intention influence, Int2Ba is able to comprehensively model the complex user behaviours driven by heterogeneous intentions. More importantly, the carefully designed DBP generates the next-basket in an iterative way driven by the intentions, and thus better accomplishes the user's intentions. As a result, Int2Ba achieves clear improvement ranging from 3.22% to 23.86% over the best performing baselines w.r.t. all the metrics on both datasets (cf. the bottom row of Table 2). The recall also shows Int2Ba leads the baselines with a clear margin (cf. Figure 2).

Reply to Q2: heterogeneous intention modeling by CICN vs. homogeneous intention modeling by ICN. We compare the performance of Int2Ba with that of Int2Ba-S to demonstrate the effectiveness of CICN to model multiple heterogeneous intentions. As shown in Table 2 and Figure 2, Int2Ba achieves clearly higher accuracy compared with Int2Ba-S with an improvement ranging from 10.07% (nDCG@5 on Tafeng) to 47.20% (nDCG@5 on Tmall). This verifies the rationality to model uers' actions across baskets by considering their heterogeneous intentions behind.

Reply to Q3: CIU vs. GRU in modeling the inter-intention influence. Similarly, the accuracy improvement ranging from 3.43% (HR@20 on Tmall) to 28.31% (nDCG@5 on Tmall) of Int2Ba over Int2Ba-GRU in Table 2 proves the existence of inter-intention influence and it can be better captured by our designed CIU.

Reply to Q4: DBP vs. Top-K predictor in accomplishing various heterogeneous intentions. For the verification of the efficacy of our devised DBP, we compare the performance of Int2Ba with that of Int2Ba-Top-K. As reported in Table 2, Int2Ba obviously outperforms Int2Ba-Top-K w.r.t. all the metrics on both datasets, specifically, Int2Ba brings an improvement ranging from 3.22% (nDCG@20 on Tmall) to 23.86% (HR@5 on Tmall) over Int2Ba-Top-K. Such improvement demonstrates the superiority of our devised DBP in basket formation over the Top-K predictor commonly used in existing works [Yu et al., 2016; Liu et al., 2018].

6 Conclusions

In this paper, we have proposed Intention2Basket (Int2Ba) to effectively model the complex and heterogeneous user behaviours for better planning next-basket, which cannot be well addressed by existing works. Int2Ba harnesses an intention recognizer to recognize the possible intentions behind each basket, coupled intention chain nets to model the state transitions of different intentions and a dynamic basket planner to iteratively generate optimal basket with the highest utility to best accomplish the recognized intentions. Empirical evaluations on real-world data show the superiority of Int2Ba over the state-of-the art methods.

Acknowledgements

This work was supported by Australian Research Council Discovery Project DP180102378.