Latent Modeling of Unexpectedness for Recommendations

Abstract

Unexpectedness constitutes an important factor for recommender system to improve user satisfaction and avoid filter bubble issues. Previous methods model unexpectedness in the feature space, making them dificult to capture the latent, complex and heterogeneous interactions between users and items. In this paper, we propose to model unexpectedness in the latent space and utilize a latent convex hull structure to provide unexpected recommendations, as illustrated in Figure 1. Extensive experiments on two real-world datasets demonstrate efectiveness of latent unexpectedness over explicit unexpectedness and show that the proposed model significantly outperforms baseline models in terms of unexpectedness measures while achieving the same level of accuracy.

Evaluation Metrics

RMSE & MAE

Root Mean Square Error and Mean Absolute Error measures the diferences between estimated ratings and actual ratings.

Precision@N & Recall@N

Precision is the fraction of the recommended items that are of high utility to the user. Recall is the fraction of the high utility items that are recommended to the user.

Unexpectedness

Unexpectedness is calculated through equation (3) following our proposed definition.

Serendipity

Serendipity [ 8 ] is computed by Serendipity = RS&P MR&SU sef ul where RS stands for the recommended items using the target model, PM stands for the recommendation items using a primitive prediction algorithm and USEFUL stands for the items whose utility is above certain threshold.

Diversity

Diversity is computed as the average intra-list distance [ 17 ]: D(R) = Íi ∈R Íj,i ∈R d(i, j)

Coverage

Coverage is computed as the percentage of distinctive recommended items over all distinctive items in the dataset. in the case when purchase actions are sparse or noisy. Besides, it does not include specific user and item features, neither does it address the latent and complex relationships between users and items. Furthermore, the distance metric between discrete items is hard to define in the feature space, while in the latent space we have well-defined euclidean distances. Thus, we cannot model the unexpected relations eficiently in the feature space.

Therefore, though researchers have successfully developed algorithms to improve unexpectedness and other novelty metrics, they always come at a price of losing accuracy performance, as pointed out in [ 19 ]. This severely limits the practical use of the unexpected recommendation, especially in business applications where the goal is to increase commercial sales and enhance user satisfaction. Thus, it is important to design a novel unexpected recommender to increase novelty of recommendations while keeping the same level of accuracy performance.

In this paper, we propose to define unexpectedness as the distance metric in the latent space (latent feature and atribute embeddings) rather than feature space (explicit users and items) by utilizing Heterogeneous Information Network Embeddings (HINE) [ 15, 16 ] to capture the latent, complex and heterogeneous relations between them. We take the natural closure of convex hull in the latent space, and calculate unexpectedness as the euclidean distance from new item embedding to the latent convex hull of expected items of the user. The proposed unexpectedness measure is subsequently combined with estimated ratings for providing recommendations.

We make the following contributions in this paper. We propose to model unexpectedness in the latent space by defining the expected set for each user as a latent convex hull generated by item embeddings. We also conduct extensive experiments on two real-world datasets and show that our model significantly improves novelty measures without losing any accuracy metrics.

METHOD

In prior literature [ 4 ], unexpectedness is defined as the distance of recommended item from the closure set of expected items, the later including items that either previously consumed by the user or closely related to the consumptions. However, this definition does not include the feature information for users and items, neither does it consider the latent and heterogeneous interactions between them. Thus, it might not serve as a perfect definition, for we cannot manually codify all explicit associations and relations between users and items. Also, it is hard to mathematically formalize the expected set in the feature space, where the distribution of users and items is discrete and unstructured.

On the other hand, heterogeneous information network [ 16 ] (HIN) along with latent embedding method [ 7 ] provides us with an eficient tool to model users, items and their associated features simultaneously by linking the associated features with corresponding entities in the network and subsequently map them into the latent space. Thus in the paper, we propose to combine those two techniques for latent modeling of unexpectedness.

Baseline Models SPR [9]

Serendipitous Personalized Ranking extends traditional personalized ranking methods by considering item popularity in AUC optimization, which makes the ranking sensitive to the popularity of negative examples.

Auralist [18]

Auralist is a personalized recommendation system that balances between the desired goals of accuracy and novelty simultaneously.

HOM-LIN [ 4 ] HOM-LIN is the state-of-the-art unexpected algorithm that utilizes the combination of estimated ratings and unexpectedness for recommendation. DPP [ 6 ] The Determinantal Point Process utilizes a fast greedy MAP inference approach to generate relevant and diverse recommendations.

Random

Random is the baseline model where we randomly recommend items to users without considering any information about the ratings, unexpectedness and utility. where C(TVt , TVt+1 ) stands for the transition coeficient between the type of node Vt and the type of node Vt +1. |Nt +1(Vt )| stands for the number of nodes of type Vt +1 in the neighborhood of Vt . We apply heterogeneous random walk iteratively to each node and generate the collection of meta-path sequences for the skip-gram mechanism.

Note that in previous definition [ 4 ], the idea of ‘’closure set” plays an important role. As a natural closure in the latent space, latent convex hull of each user is the smallest convex set that contains all the item embeddings that the user has visited. Under this seting, we assume that the expected set maintains its convexity in the growing process. For example, if a person enjoy rap music and rock & roll, she/he shall also have certain expectations on rap-rock music, an innovation combination of those two genres. Subsequently, we define the unexpectedness as the distance between the embedding of new item and the latent convex hull generated from the embeddings of all visited items of the user:

U tilityu,i = (1 − α ) ∗ EstRatinдu,i + α ∗ U nexpu,i

U nexpu,i = d(i; LC(Ni )) where Ni = (i1, i2, · · · , in ) contains the embeddings of items that link to the user in the heterogeneous information network. Specifically, the distance function is well defined as the minimal distance from the given point to all the boundaries of the latent closure. We visualize this definition in Figure 1.

Once we set up the definition of unexpectedness, we perform the unexpected recommendation using hybrid-utility based collaborative filtering methods that linearly combine estimated ratings (representing accuracy) with unexpectedness (representing novelty) (1) (2) (3) (4) To calculate P (ct |v; θ ), we propose to use heterogeneous random walk to generate meta-paths of multiple types of nodes in the form of V1 −−R→1 V2 −−R→2 V3 · · · Vn wherein R = R1 ◦ R2 ◦ · · · Rn defines the composite relations between the start and the end of the heterogeneous random walk. The transition probability within each random walk between two nodes is defined as follows: p(Vt +1 |Vt ) = ( C(TVt ,TVt+1 ) , (Vt , Vt +1) ∈ E

|Nt+1(Vt )| 0, (Vt , Vt +1) < E Dataset Yelp TA # Review 5,996,996 878,561 # Business 188,593 576,689 # User 1,518,169 3,945 # Sparsity 0.002% 0.039% Table 1: Descriptive Statistics for the two

Datasets.

The key idea lies in that, instead of recommending the similar items that the users are very familiar with as the classical recommenders do, we recommend unexpected and useful items to the users that they might have not thought about, but indeed fit well to their satisfactions. These two adversarial forces of accuracy and novelty work together to obtain the optimal solution, thus improving recommendation performance and user satisfaction. In real practice, the unexpected coeficient α is optimized through Bayesian optimization.

EXPERIMENTS AND RESULTS

We implement our model on two real-world datasets: the Yelp Challenge Dataset Round 12 [ 2 ] and the TripAdvisor Dataset [ 1 ]. The descriptive statistics of these two datasets are listed in Table 1. To address the cold-start issue, we filter out users and items that appear less than 5 times in the dataset. We measure the recommendation results using accuracy and novelty metrics listed in page 2.

We compare the recommendation performance with and without considering the proposed unexpectedness by 5-fold cross-validation experiments using five popular collaborative filtering algorithms including KNN, SVD, CoClustering, NMF and FM [ 13 ]. We also report results for baseline unexpected recommendation models. As shown in Table 2 and 3, when considering unexpectedness in the recommendation process, we obtain significant amount of improvements in terms of Unexpectedness, Serendipity and Diversity measures, without sacrificing any accuracy performance in RMSE, MAE, Precision and Recall. Therefore, the proposed definition of unexpectedness enables us to provide unexpected and useful recommendations at the same time. It is crucial for successful deployments of unexpected recommendation models in industrial applications. In addition, the proposed approach outperforms all previous unexpected recommendation models introduced in page 3, which validates the superiority of modeling unexpectedness in the latent space over feature space. Finally, we point out that the proposed model achieves greater improvements on Yelp dataset, which contains richer feature information compared to the TripAdvisor dataset. This observation is in line with our assumption that feature information maters in the definition of unexpectedness.

CONCLUSION

In this paper, we propose to model unexpectedness and user expectations in the latent space, which makes it possible to capture the latent, complex and heterogeneous relations between users and items, thus significantly improving the performance and practicability of unexpected recommendations. We empirically demonstrate that the proposed approach consistently and significantly outperforms baseline models in terms of unexpected measures without sacrificing the performance of accuracy.

As the future work, we plan to conduct live experiments with real business environment in order to further evaluate the efectiveness of unexpected recommendations and analyze both qualitative and quantitative aspects in an online retail seting, especially with the utilization of A/B test. Data TA

Model

FM FM+Unexp

CoCluster CoCluster+Unexp

SVD SVD+Unexp

NMF NMF+Unexp

KNN KNN+Unexp

SPR Auralist HOM-LIN

DPP Random

FM FM+Unexp

CoCluster CoCluster+Unexp

SVD SVD+Unexp

NMF NMF+Unexp

KNN KNN+Unexp

SPR Auralist HOM-LIN

DPP Random

References

[1] 2019 . TripAdvisor Dataset. htp://www.cs.cmu.edu/~jiweil/html/hotel-review. html.

[2] 2019 . Yelp Challenge Dataset . htps://www.yelp.com/dataset/challenge.

[3] Panagiotis Adamopoulos . 2014 . On discovering non-obvious recommendations: Using unexpectedness and neighborhood selection methods in collaborative filtering systems . In Proceedings of the 7th WSDM.

[4] Panagiotis Adamopoulos and Alexander Tuzhilin . 2015 . On unexpectedness in recommender systems: Or how to beter expect the unexpected . ACM Transactions on Intelligent Systems and Technology (TIST) ( 2015 ).

[5] Li Chen , Yonghua Yang , Ningxia Wang , Keping Yang , and Quan Yuan . 2019 . How Serendipity Improves User Satisfaction with Recommendations? A Large-Scale User Evaluation . In The World Wide Web Conference. ACM , 240 - 250 .

[6] Laming Chen , Guoxin Zhang, and Eric Zhou . 2018 . Fast greedy MAP inference for Determinantal Point Process to improve recommendation diversity . In Advances in Neural Information Processing Systems . 5622 - 5633 .

[7] Yuxiao Dong , Nitesh V Chawla, and Ananthram Swami . 2017 . metapath2vec: Scalable representation learning for heterogeneous networks . In Proceedings of the 23rd ACM SIGKDD. ACM.

[8] Mouzhi Ge , Carla Delgado-Batenfeld, and Dietmar Jannach . 2010 . Beyond accuracy: evaluating recommender systems by coverage and serendipity . In Proceedings of the fourth ACM conference on Recommender systems. ACM , 257 - 260 .

[9] Qiuxia Lu , Tianqi Chen, Weinan Zhang, Diyi Yang, and Yong Yu . 2012 . Serendipitous personalized ranking for top-n recommendation . In 2012 WI-IAT. IEEE.

[10] Tomoko Murakami , Koichiro Mori, and Ryohei Orihara . 2007 . Metrics for evaluating the serendipity of recommendation lists . In Annual conference of the Japanese society for artificial intelligence . Springer, 40 - 46 .

[11] Tien T Nguyen , Pik-Mai Hui , F Maxwell Harper , Loren Terveen, and Joseph A Konstan . 2014 . Exploring the filter bubble: the efect of using recommender systems on content diversity . In Proceedings of the 23rd WWW. ACM.

[12] Eli Pariser . 2011 . The filter bubble: How the new personalized web is changing what we read and how we think . Penguin.

[13] Francesco Ricci , Lior Rokach, and Bracha Shapira . 2015 . Recommender systems: introduction and challenges . In Recommender systems handbook. Springer , 1 - 34 .

[14] Guy Shani and Asela Gunawardana . 2011 . Evaluating recommendation systems . In Recommender systems handbook.

[15] Chuan Shi , Binbin Hu, Xin Zhao , and Philip Yu . 2018 . Heterogeneous Information Network Embedding for Recommendation . IEEE Transactions on Knowledge and Data Engineering ( 2018 ).

[16] Yizhou Sun and Jiawei Han. 2013 . Mining heterogeneous information networks: a structural analysis approach . Acm Sigkdd Explorations Newsleter 14 , 2 ( 2013 ), 20 - 28 .

[17] Mi Zhang and Neil Hurley . 2008 . Avoiding monotony: improving the diversity of recommendation lists . In Proceedings of the 2008 ACM conference on Recommender systems. ACM , 123 - 130 .

[18] Yuan Cao Zhang , Diarmuid Ó Séaghdha, Daniele Quercia, and Tamas Jambor . 2012 . Auralist: introducing serendipity into music recommendation . In Proceedings of the fifth ACM WSDM . ACM.

[19] Zainab Zolaktaf , Reza Babanezhad, and Rachel Potinger . 2018 . A Generic Top-N Recommendation Framework For Trading-of Accuracy, Novelty, and Coverage. In 2018 IEEE 34th ICDE . IEEE.