Probabilistic Metric Learning with Adaptive Margin for Top-K Recommendation

Previous works (Hsieh et al., 2017; Tay et al., 2018) use the user and item embeddings in a deterministic manner and do not measure or learn the uncertainties of user preferences and item properties. Motivated by probabilistic matrix factorization (PMF) (Salakhutdinov and Mnih, 2007), we represent each user or item as a single Gaussian distribution. In contrast to PMF, which applies Gaussian priors on user and item embeddings, users and items in our model are parameterized by Gaussian distributions, where the means $\mu$ and covariances $\Sigma$ are directly learned. Specifically, the latent factors of user $i$ and item $j$ are represented as:

Here $\mathbf{\mu}^{(U)}_{i}$ and $\mathbf{\Sigma}^{(U)}_{i}$ are the learned mean vector and covariance matrix of user $i$, respectively; $\mathbf{\mu}^{(I)}_{j}$ and $\mathbf{\Sigma}^{(I)}_{j}$ are the learned mean vector and covariance matrix of item $j$. To limit the complexity of the model and reduce the computational overhead, we assume that the embedding dimensions are uncorrelated. Thus, $\mathbf{\Sigma}$ is a diagonal covariance matrix that can be represented as a vector. Specifically, $\mathbf{\mu}\in\mathbb{R}^{h}$ and $\mathbf{\Sigma}\in\mathbb{R}^{h}$, where $h$ is the dimension of the latent space.

Widely used distance metrics for deterministic embeddings, like the Euclidean distance, do not properly measure the distance between distributions. Since users and items are represented by probabilistic distributions, we need a distance measure between distributions. Among the commonly used distance metric between distributions, we adopt the Wasserstein distance to measure the user preference for an item. The reasons are twofold: i) the Wasserstein distance satisfies all the properties a distance should have; and ii) the Wasserstein distance has a simple form when calculating the distance between Gaussian distributions (Mallasto and Feragen, 2017). Formally, the $p$-th Wasserstein distance between two probability measures $\mu$ and $\nu$ on a Polish metric space (Srivastava, 2008) $(\mathcal{X},d)$ is defined (Givens and Shortt, 1984):

where $d(\cdot,\cdot)^{p}$ is an arbitrary distance with $p^{th}$ moment (Casella and Berger, 2002) for a deterministic variable, $p\in[1,+\infty)$; and $\mathcal{J}(\mu,\nu)$ denotes the set of all measures $J$ on $\mathcal{X}\times\mathcal{X}$ which admit $\mu$ and $\nu$ as marginals. When $p\geq 1$, the $p$-th Wasserstein distance preserves all properties of a metric, including both symmetry and the triangle inequality.

The calculation of the general Wasserstein distance is computation-intensive (Xie et al., 2019). To reduce the computational cost, we use Gaussian distributions for the latent representations of users and items. Then when $p=2$, the $2$-nd Wasserstein distance (abbreviated as $\mathcal{W}_{2}$) has a closed form solution, thus making the calculation process much faster. Specifically, we have the following formula to calculate the $\mathcal{W}_{2}$ distance between user $i$ and item $j$ (Givens and Shortt, 1984):

In our setting, we focus on diagonal covariance matrices, thus $\mathbf{\Sigma}^{(U)}_{i}\mathbf{\Sigma}^{(I)}_{j}=\mathbf{\Sigma}^{(I)}_{j}\mathbf{\Sigma}^{(U)}_{i}$. For simplicity, we use $\mathcal{W}_{2}(i,j)^{2}$ to denote the left hand side of Eq. 2. Then Eq. 2 can be simplified as:

According to the above equation, the time complexity of calculating $\mathcal{W}_{2}$ distance between the latent representations of users and items is linear with the embedding dimension.

To learn the distance-based model, most of the existing works (Hsieh et al., 2017; Tay et al., 2018) apply the margin ranking loss to measure the user preference difference between positive items and negative items. Specifically, the margin ranking loss makes sure the distance between a user and a positive item is less than the distance between the user and a negative item by a fixed margin $m>0$. The loss function is:

where $j\in\mathcal{S}_{i}$ is an item that user $i$ has accessed, and $k\not\in\mathcal{S}_{i}$ is a randomly sampled item treated as the negative example, and $[z]_{+}=\max(z,0)$. Thus, $(i,j,k)$ represents a training triplet.

The safe margin $m$ in the margin ranking loss is a crucial hyper-parameter that has a major impact on the model performance. A fixed margin value may not achieve satisfactory performance. First, using a fixed value does not allow for adaptation to distinguish the properties of the training triplets. For example, some users have broad interests, so the margins for these users should not be so large as to make potential preferred items too far from the user. Other users have very focused interests, and it is desirable to have a larger margin to avoid recommending items that are not directly within the focus. Second, in different training phases, the model may need different magnitudes of margins. For instance, in the early stage of training, the model is not reliable enough to make strong predictions on user preferences, and thus imposing a large margin risk pushing potentially positive items too far from a user. Third, to achieve satisfactory performance, the selection of a fixed margin involves tedious hyper-parameter tuning. Based on these considerations, we conclude that setting a fixed margin value for all training triplets may limit the model expressiveness.

To address the problems outlined above, we propose an adaptive margin generation scheme which generates margins according to the training triplets. Formally, we formulate the margin ranking loss with an adaptive margin as:

Here $f(i,j,k;\Phi)$ is a function that generates the specific margin based on the corresponding user and item embeddings and $\Phi$ is the learnable set of parameters associated with $f(\cdot)$. Then we could consider optimizing $\Theta$ and $\Phi$ simultaneously:

Unfortunately, directly minimizing the objective function as in Eq. 6 does not achieve the desired purpose of generating suitable adaptive margins. Since the margin-related term explicitly appears in the loss function, constantly decreasing the value of the generated margin is the straightforward way to reduce the loss. As a result all generated margins have very small values or are set to zero, leading to unsatisfactory results. In other words, the direct optimization of $\mathcal{L}_{Ada}$ with respect to $\Phi$ harms the optimization of $\Theta$.

It is important to model the relationships between pairs of users or pairs of items when developing recommender systems and strategies for doing so effectively have been studied for many years (Sarwar et al., 2001; Kabbur et al., 2013; Ning et al., 2015). For example, item-based collaborative filtering methods use item rating vectors to calculate the similarities between the items. Closely-related users or items may share the same interests or have similar attributes. For a certain user, items similar to the user’s preferred items are potential recommendation candidates.

Despite this intuition, previous distance-based recommendation methods (Hsieh et al., 2017; Tay et al., 2018) do not explicitly take the user-user or item-item relationships into consideration. As a result of relying primarily on user-item information, the systems may fail to generate appropriate user-user or item-item distances. To model the relationships between similar users or items, we employ two ranking margin losses with adaptive margins to encourage similar users or items to be mapped closer together in the latent space. Formally, the similarities between users or items are calculated from the user implicit feedback, which can be represented by a binary user-item interaction matrix. We set a threshold on the calculated similarities to identify the similar users and items for a specific user $i$ and item $j$, respectively, denoted as $\mathcal{N}^{U}_{i}$ and $\mathcal{N}^{I}_{j}$. We adopt the following losses for user pairs and item pairs, respectively:

where $q$ is a randomly sampled user in Eq. 15 and a randomly sampled item in Eq. 18. $U-U$ denotes the user-user relation and $I-I$ denotes the item-item relation. We use $\Phi^{t}_{U-U}$ and $\Phi^{t}_{I-I}$ to update $\Theta^{t+1}_{U-U}$ and $\Theta^{t+1}_{I-I}$, respectively, which are the same as in Alg. 1. We denote the indicator in Eq. 11 as $\mathbf{s}_{ijk}^{U-I}$, then we generate $\mathbf{s}_{ijq}^{U-U}$ and $\mathbf{s}_{ijq}^{I-I}$ following the procedure described by Eq. 11.

Let us denote the losses $\mathcal{J}_{inner}^{U-I}$ and $\mathcal{J}_{outer}^{U-I}$ to capture the interactions between users and items. Then we combine the loss functions presented in Section 4.3 to optimize the proposed model:

where $\lambda$ is a regularization parameter. We follow the same training scheme of Section 4.2 to train Eq. 19. To mitigate the curse of dimensionality issue (Bordes et al., 2013) and prevent overfitting, we bound all the user/item embeddings within a unit sphere after each mini-batch training: $||\mathbf{\mu}||\leqslant 1$ and $||\mathbf{\Sigma}||\leqslant 1$. When minimizing the objective function, the partial derivatives with respect to all the parameters can be computed by gradient descent with back-propagation.

Recommendation Phase. In the testing phase, for a certain user $i$, we compute the distance $\mathcal{W}_{2}(i,j)^{2}$ between user $i$ and each item $j$ in the dataset. Then the items that are not in the training set and have the shortest distances are recommended to user $i$.

The proposed model is evaluated on five real-world datasets from various domains with different sparsities: Books, Electronics and CDs (He and McAuley, 2016), Comics (Wan and McAuley, 2018) and Gowalla (Cho et al., 2011). The Books, Electronics and CDs datasets are adopted from the Amazon review dataset with different categories, i.e., books, electronics and CDs. These datasets include a significant amount of user-item interaction data, e.g., user ratings and reviews. The Comics dataset was collected in late 2017 from the GoodReads website with different genres, and we use the genres of comics. The Gowalla dataset was collected worldwide from the Gowalla website (a location-based social networking website) over the period from February 2009 to October 2010. In order to be consistent with the implicit feedback setting, we retain any ratings no less than four (out of five) as positive feedback and treat all other ratings as missing entries for all datasets. To filter noisy data, we only include users with at least ten ratings and items with at least five ratings. Table 1 shows the data statistics.

We employ five-fold cross-validation to evaluate the proposed model. For each user, the items she accessed are randomly split into five folds. We pick one fold each time as the ground truth for testing, and the remaining four folds constitute the training set. The average results over the five folds are reported.

We evaluate all models in terms of Recall@k and NDCG@k. For each user, Recall@k (R@k) indicates the percentage of her rated items that appear in the top $k$ recommended items. NDCG@k (N@k) is the normalized discounted cumulative gain at $k$, which takes the position of correctly recommended items into account.

To demonstrate the effectiveness of our model, we compare to the following recommendation methods.
Classical methods for implicit feedback:

• •

  BPRMF, Bayesian Personalized Ranking-based Matrix Factorization (Rendle et al., 2009), which is a classic method for learning pairwise personalized rankings from user implicit feedback.

Classical neural-based recommendation methods:

• •

  NCF, Neural Collaborative Filtering (He et al., 2017b), which combines the matrix factorization (MF) model with a multi-layer perceptron (MLP) to learn the user-item interaction function.

• •

  DeepAE, the deep autoencoder (Ma et al., 2018), which utilizes a three-hidden-layer autoencoder with a weighted loss function.

State-of-the-art distance-based recommendation methods:

• •

  CML, Collaborative Metric Learning (Hsieh et al., 2017), which learns a metric space to encode the user-item interactions and to implicitly capture the user-user and item-item similarities.

• •

  LRML, Latent Relational Metric Learning (Tay et al., 2018), which exploits an attention-based memory-augmented neural architecture to model the relationships between users and items.

• •

  TransCF, Collaborative Translational Metric Learning (Park et al., 2018), which employs the neighborhood of users and items to construct translation vectors capturing the intensity of user–item relations.

• •

  SML, Symmetric Metric Learning with adaptive margin (Li et al., 2020), which measures the trilateral relationship from both the user- and item-centric perspectives and learns adaptive margins.

The proposed method:

• •

  PMLAM, the proposed model, which represents each user and item as Gaussian distributions to capture the uncertainties in user preferences and item properties, and incorporates an adaptive margin generation mechanism to generate the margins based on the sampled user-item triplets.

In the experiments, the latent dimension of all the models is set to $50$ for a fair comparison. All the models adopt the same negative sampling strategy with the proposed model, unless otherwise specified. For BPRMF, the learning rate is set to $0.001$ and the regularization parameter is set to $0.001$. With these parameters, the model can achieve good results. For NCF, we follow the same model structure as in the original paper (He et al., 2017b). The learning rate is set to $0.001$ and the batch size is set to $1024$. For DeepAE, we adopt the same model structure employed in the author-provided code and set the batch size to $512$. The weight of the positive items is selected from $\{5,10,15,20\}$ by a grid search and the weights of all other items are set to $1$ as recommended in (Hu et al., 2008). For CML, we use the authors’ implementation to set the margin to $m=1$ and the regularization parameter to $\lambda_{c}=1$. For LRML, the learning rate is set to $0.001$, and the number of memories is selected from $\{5,10,20,25,50,100\}$ by a grid search. For TransCF, we follow the settings in the original paper to select $\lambda,\,\lambda_{nbr},\,\lambda_{dist}\in\{0,\,0.001,\,0.01,\,0.1\}$ and set the margin to $1$ and batch size to $1000$, respectively. For SML, we follow the author’s code to set the user and item margin bound $l$ to $1.0$, $\lambda$ to $0.01$ and $\gamma$ to $10$, respectively.

For our model, both the learning rate and $\lambda$ are set to $0.001$. For the $Electronics$ and $CDs$ datasets, we randomly sample $10$ unobserved users or items as negative samples for each user and positive item. This number is reduced to $2$ for the other datasets to speed up the training process. The batch size is set to $5000$ for all datasets. The dimension $h$ is set to $50$. The user and item embeddings are initialized by drawing each vector element independently from a zero-mean Gaussian distribution with a standard deviation of $0.01$. Our experiments are conducted with PyTorch running on GPU machines (Nvidia Tesla P100).

To speed up the training process, we implement a two-phase sampling strategy. We sample a number of candidates, e.g., 500, of negative samples for each user every 20 epochs to form a candidate set. During the next 20 epochs, the negative samples of each user are sampled from her candidate set. This strategy can be implemented using multiple processes to further reduce the training time.

Since none of the processed datasets has inherent user-user/item-item information, we treat the user-item interaction as a user-item matrix and compute the cosine similarity for the user and item pairs, respectively (Sarwar et al., 2001). We set a threshold, e.g., $0.2$ on Amazon and Gowalla datasets and $0.4$ on the Comics dataset, to select the neighbors. These thresholds are chosen to ensure a reasonable degree of connectivity in the constructed graphs.

The performance comparison is shown in Figure 3 and Table 2. Based on these results, we have several observations.

Observations about our model. First, the proposed model, PMLAM, achieves the best performance on all five datasets with both evaluation metrics, which illustrates the superiority of our model.
Second, PMLAM outperforms SML. Although SML has an adaptive margin mechanism, it is achieved by having a learnable scalar margin for each user and item and adding a regularization term to prevent the learned margins from being too small. It can be challenging to identify an appropriate regularization weight via hyperparameter tuning. By contrast, PMLAM formulates the adaptive margin generation as a bilevel optimization, avoiding the additional regularization. PMLAM employs a neural network to generate the adaptive margin, so the number of parameters related to margin generation does not increase with the number of users or items.
Third, PMLAM achieves better performance than TransCF. One major reason is that TransCF only considers the items rated by a user and the users who rated an item as the neighbors of the user and item, respectively, which neglects the user-user/item-item relations. PMLAM models the user-user/item-item relations by two margin ranking losses with adaptive margins.
Fourth, PMLAM makes better recommendations than CML and LRML. These methods apply a fixed margin for all user-item triplets and do not measure or model the uncertainty of learned user/item embeddings. PMLAM represents each user and item as a Gaussian distribution, where the uncertainties of learned user preferences and item properties are captured by the covariance matrices.
Fifth, PMLAM outperforms NCF and DeepAE. These are MLP-based recommendation methods with the ability to capture non-linear user-item relationships, but they violate the triangle inequality when modeling user-item interaction. As a result, they can struggle to capture the fine-grained user preference for particular items (Hsieh et al., 2017).

Other observations. First, all of the results reported for the Comics dataset are considerably better than those for the other datasets. The other four datasets are sparser and data sparsity negatively impacts recommendation performance.
Second, CML, LRML and TransCF perform better than SML on most of the datasets. The adaptive margin regularization term in SML struggles to adequately counterbalance SML’s tendency to reduce the loss by imposing small margins. Although it is reported that SML outperforms CML, LRML and TransCF in (Li et al., 2020), the experiments are conducted on three relatively small-scale datasets with only several thousands of users and items. We experiment with much larger datasets; identifying a successful regularization setting appears to be more difficult as the number of users increases.
Third, TransCF outperforms LRML on most of the datasets. One possible reason is that TransCF has a more effective translation embedding learning mechanism, which incorporates the neighborhood information of users and items. TransCF also has a regularization term to further pull positive items closer to the anchor user.
Fourth, CML achieves better performance than LRML on most of the datasets. CML integrates the weighted approximate-rank pairwise (WARP) weighting scheme (Weston et al., 2010) in the loss function to penalize lower-ranked positive items. The comparison between CML and LRML in (Tay et al., 2018) removes this component of CML. The WARP scheme appears to play an important role in improving CML’s performance.
Fifth, DeepAE outperforms NCF. The heuristic weighting function of DeepAE can impose useful penalties to errors that occur during training when positive items are assigned lower prediction scores.

To verify and assess the relative effectiveness of the proposed user-item interaction module, the adaptive margin generation module, and the user-user/item-item relation module, we conduct an ablation study. Table 3 reports the performance improvement achieved by each module of the proposed model. Note that we compute Euclidean distances between deterministic embeddings. In (1), which serves as a baseline, we use the hinge loss with a fixed margin (Eq. 4) on deterministic embeddings of users and items to capture the user-item interaction ($m$ is set to $1$ which is commonly used in (Hsieh et al., 2017; Tay et al., 2018; Park et al., 2018)). In (2), as an alternative baseline, we apply the same hinge loss as in (1), but replace the deterministic embeddings with parameterized Gaussian distributions (Section 4.1). In (3), we use the adaptive margin generation module (Section 4.2) to generate the margins for deterministic embeddings. In (4), we concatenate the deterministic embeddings of $(i,j,k)$ to generate $\mathbf{s}_{ijk}$ instead of using Eq. 11. In (5), we sum the deterministic embeddings of $(i,j,k)$ to generate $\mathbf{s}_{ijk}$ instead of using Eq. 11. In (6), we combine (2) and (3) to generate the adaptive margins for Gaussian embeddings. In (7), we augment (6) with user-user/item-item modeling but with a fixed margin, where the margin is also set to $1$. In (8), we add the user-user/item-item modeling with adaptive margins (Section 4.3) to replace the fixed margins in the configuration of (7).

From the results in Table 3, we have several observations. First, from (1) and (2), we observe that by representing the user and item as Gaussian distributions and computing the distance between Gaussian distributions, the performance improves. This suggests that measuring the uncertainties of learned embeddings is significant. Second, from (1) and (3) along with (2) and (6), we observe that incorporating the adaptive margin generation module improves performance, irrespective of whether deterministic or Gaussian embeddings are used. These results demonstrate the effectiveness of the proposed margin generation module. Third, from (3), (4) and (5), we observe that our designed inputs (Eq. 11) for margin generation facilitate the production of appropriate margins compared to commonly used embedding concatenation or summation operations. Fourth, from (2), (3) and (6), we observe that (6) achieves better results than either (2) or (3), demonstrating that Gaussian embedddings and adaptive margin generation are compatible and can be combined to improve the model performance. Fifth, compared to (6), we observe that the inclusion of the user-user and item-item terms in the objective function (7) leads to a large improvement in recommendation performance. This demonstrates that explicit user-user/item-item modeling is essential and can be an effective supplement to infer user preferences. Sixth, from (7) and (8), we observe that adaptive margins also improve the modelling of the user-user/item-item relations.

In this section, we conduct case studies to confirm whether the adaptive margin generation can produce appropriate margins. To achieve this purpose, we train our model on the MovieLens-100K dataset. This dataset provides richer side information about movies (e.g., movie genres), making it easier for us to illustrate the results. Since we only focus on the adaptive margin generation, we use deterministic embeddings of users and items to avoid the interference of other modules. We randomly sample users from the dataset. For each user, we sample one item that the user has accessed as the positive item and two items the user did not access as negative items, where one item has a similar genre with the positive item and the other does not. The case study results are shown in Table 4.

As shown in Table 4, our adaptive margin generation module tends to generate a smaller margin value when the negative movie has a similar genre with the positive movie, while generating larger margins when they are distinct. The generated margins thus encourage the model to embed items with a higher probability of being preferred closer to the user’s embedding.