Global-Local Item Embedding for Temporal Set Prediction

Let $\mathcal {U} = \lbrace u_1, u_2, \dots, u_N \rbrace$ be set of users and $\mathcal {E} = \lbrace e_1, e_2, \dots, e_M \rbrace$ be set of items. Given a user u_i’s sequence of sets , our goal is to predict next set $S_i^{T_i + 1}$. Each set $S_i^k$ can also be represented as a binary vector form $\mathbf {v}_i^k$, where each element . is a indicator function which returns 1 if x is true and 0 otherwise. We will use the set notation $S_i^k$ and $\mathbf {v}_i^k$ interchangeably to denote user u_i’s k-th set.

Variational Autoencoders (VAEs) [10, 13] are a class of deep generative models. VAEs provide latent structures that can nicely explain the observed data (e.g., customer's purchase history). Formally speaking, VAEs find the latent variables (z) that maximize the evidence lower bound (ELBO), a surrogate objective function for the maximum likelihood estimation of the given observation x:

(1)

Encoders are commonly structured by multilayer perceptrons (MLPs) that produce Gaussian distributions over the latent variable z. On the other hand, decoders are designed to have different probability distributions of output layer depending on the characteristics of datasets. For example, Gaussian distribution and multinomial distribution are often used to represent the real-valued continuous and binary data, respectively.

We are interested in modeling other users’ history as well as the given user's history. We proceed with this under the VAE framework. However, a difficulty arises: every user has a different length of the sequence of sets. To resolve this, we sum time decayed sequence of sets.

(3)

As most people interact with a few items, v_i contains many 0s and so does x_i. However, the reconstructed vector $\hat{\mathbf {x}}_i$ generated from the following process:

Note that Hu et al. [5]’s Personalized Item Frequency (PIF) is similar to our sum of time decayed vectors. However, since their work is based on K-Nearest Neighbor, two shortcomings arise: 1) the inference time grows cubic with the number of users and 2) they cannot use features unlike traditional deep learning approaches.

When training VAE, using gaussian output on p(x∣z) is a straightforward option. However, the distributions of the data generated from temporal set prediction problems are zero-inflated and long-tailed as shown in Figure 2.

Tweedie distribution is a special case of exponential dispersion model (EDM) with a power parameter p and the variance function V(μ) = μ^p [6]. Tweedie distribution with 1 < p < 2 corresponds to a class of compound Poisson distributions [7]. Consider two step sampling process N ∼ Poisson(λ) and X_i ∼ Gamma(α, β) for λ, α, β > 0 and i = 1, …, N. Now we define a random variable Z as follows:

It is straightforward that the distribution defined by Equation (5) is zero-inflated for small enough λ and long-tailed as Z is addition of X_i ∼ Gamma(α, β) for N > 0. Hence using Tweedie output on VAE's decoder for temporal set prediction is beneficial as Tweedie distribution easily captures the properties of distributions that are shown in Figure 2.

Learning the mean parameter μ and the power parameter p of Tweedie distribution via maximum likelihood is easy. Minimizing

A line of works chose distributions other than Gaussian or Bernoulli on matrix factorization and VAE [3, 12, 18]. Poisson distribution or multinomial distribution are usual choices. This paper is the first attempt to apply Tweedie distribution for VAE's decoder output to the best of our knowledge.

Though VAE with Tweedie output is already competent, it tends to underestimate a user's preference for the frequently interacted items. This tendency owes to the learning objective of VAE as the model has to maximize the likelihood of 0 for never interacted items. This sometimes sacrifices the ability to maximize the likelihood of values of interacted items. Hence, we integrate item embeddings of frequently interacted items which are learned by state-of-the-art models to our VAE. We use DNNTSP [21] as it is the state-of-the-art method. DNNTSP makes user-dependent embeddings of items that are interacted at least once via dynamic graph neural networks. We denote z_ij as the embedding of user u_i for item e_j.

When it comes to combining VAE with embeddings z_ij, a problem arises: the reconstructed value $\hat{\mathbf {x}}_{ij}$ of Equation (4) is a scalar while learned embedding z_ij is a vector. Hence, to match the size between $\hat{\mathbf {x}}_{ij}$ and z_ij, we simply multiply a vector w^*, which is of same size as z_ij, to $\hat{\mathbf {x}}_{ij}$. We defer the discussion on the selection of w^* to latter part of this section.

Now we combine updated embedding with $\hat{\mathbf {x}}_{ij} \cdot \mathbf {w}^*$s and z_ijs. The updated embedding $\tilde{\mathbf {z}}_{ij}$ is defined as

Lastly, we calculate the affinity of a user u_i to item e_j by

We now going back to the selection of w^* in Equation (7). We set w^* = w₀ in Equation (9) though we can set w^* as a learnable parameter. If we set w^* = w₀, Equation (9) becomes $ \hat{\mathbf {y}}_{ij} = \sigma \left(\hat{\mathbf {x}}_{ij} \cdot \mathbf {w}_0^T \mathbf {w}_0 + b_0 \right)$ for non-interacted item $e_j \notin \bigcup _k S_i^k$, hence it preserves the order of affinity that is learned by VAE. We also run experiments with learnable parameter w^* but the performance was on par with w^* = w₀.

We evaluate our method on three public benchmarks: Dunnhumby Carbo (DC), TaoBao, and Tags-Math-Sx (TMS). We partitioned each dataset into train, validation and test into 70%, 10% and 20% respectively following Yu et al. [21]. See Table 1 for statistics of benchmarks.

We compare four methods: Toppop, PersonalToppop, Sets2Sets and DNNTSP.

Toppop simply serves the items that are interacted the most across all users. PersonalToppop serves the items that the given user interacted with the most. Sets2Sets uses encoder-decoder framework to predict the next set [4]. Set embeddings are made by pooling operation and set-based attention is used to model temporal correlation relation. This method also models repeated elements. DNNTSP is composed of three components: Element Relationship Learning (ERL), Temporal Dependency Learning (TDL) and Gated Information Fusing. ERL is simply a dynamic weighted graph neural networks. TDL captures temporal dependency. By Gated Information Fusing each user shares the embeddings of uninteracted items. Hence DNNTSP can be seen as an ensemble of model which learns local information and Toppop model.

The results of our evaluation on three public benchmarks are shown in Table 2. We consider three metrics: Recall, Normalized Discounted Cumulative Gain (NDCG) and Personal Hit Ratio (PHR). PHR@K is calculated as where N′ is the number of test users, $\hat{S}_i$ is the predicted top-K elements, and S_i is the ground truth set.

We trained VAE for 30 epochs and then trained DNNTSP for 30 epochs. We used only one layer for the VAEs across all benchmarks. For the decay factor in Equation (2), we set τ = 0.6. As illustrated in Figure 3, τ = 0.6 shows the best performance on TaoBao dataset. We empirically observe that τ = 0.6 could provide decent results across all metrics on the other datasets as well. The dimension of latent space is 128 for DC and TaoBao, and 512 for TMS. We used Adam optimizer [9] with learning rate 0.001.

Across all benchmarks and metrics, GLOIE with Tweedie output outperforms or is on par with all compared methods. Especially, GLOIE with Tweedie output outperforms the other methods on all metrics on DC and TaoBao datasets. We can see that GLOIE with Tweedie outperforms DNNTSP on every metric when K = 10 which means that the embeddings learned by VAE are richly used as well as the embeddings learned by DNNTSP.

One thing to remark is that VAE with Tweedie output shows comparable performance to all compared methods on most metrics. Given that the number of items a user interacted with is 5.44, 4.96, and 18.05 respectively in DC, TaoBao, and TMS, this shows that VAE with Tweedie output captures the preference of users to non-interacted items.

To investigate the effectiveness of the attention-based integration method illustrated in Equation (8), we compared GLOIE with attention to the one with itemwise learnable weight similar to the method proposed in Yu et al. [21]. For overall datasets and metrics, we could observe performance gains: 3.09%, 0.45%, 0.92% improvement of NDCG@10 on DC, Taobao, and TMS, respectively.

Lastly, we note that the selection of output distribution of decoder on VAE largely affects the performance. We empirically show that both Gaussian and multinomial outputs do not fit temporal set prediction problems even though Gaussian is a popular choice for VAE and multinomial is a common choice in recommender system literature after the advent of VAECF [12].