Week 5: One-Class Collaborative Filtering

Title: One-class collaborative filtering, Rong Pan, Yunhong Zhou, Bin Cao, Nathan N. Liu, Rajan Lukose, ICDE 2008.

Background: In Amazon and Netflix, users are allowed to express their preference by explicitly providing ratings of different scales. However, in some other applications, we can only observe implicit user behaviors such as click or not click, purchase or not purchase and bookmark or not bookmark. However, it would cause ambiguity because we are not able to interpret the true meaning of negative examples. For example, not clicking does not necessarily correspond to no interest, it may represent no awareness of its existence. The collaborative filtering with positive examples (ambiguous negative examples) is One-Class Collaborative Filtering (OCCF). This paper aims to address this issue.

Methods: Intuitive methods are "all missing as negative (AMAN)" and "all missing as unknown (AMAU)". AMAN takes all missing data as negative examples, which will bias recommendation results because some missing data may be positive. AMAU takes all missing data as unknown examples. It will produce a trivial situation where all predictions for missing values are positive.

To balance the two extremes and improve recommendation performance, this paper proposes two frameworks - (1) weighted low rank approximation and (2) negative example sampling. The main idea of weighted low rank approximation is to approximate user-to-item matrix by a low-rank matrix with different scales of weights based on the confidence on positive and so-called "negative" examples. To do so, the paper presents a weighted alternating least squares (wALS) method. As shown in Figure 1, its object function is a weighted Frobenius loss function with regularization to avoid overfitting, where R is user-to-item matrix, U and V are decompositions of low-rank approximation, W represent weighting matrix. In wALS algorithm, U or V are iteratively fixed and optimized.

Figure 1. Object function of wALS.

Figure 2. Algorithm of wALS.

They provide three weighting schemes. The first scheme is uniform weighting which assumes that all missing data has equal chance of being negative in [0,1]; The second schemes is user-oriented which assumes that if a user has more positive ratings, it is more likely that missing data represent negative examples; The third scheme is item-oriented which posits that if an item is less positively rated, its missing values will represent negative with higher probability.

There are two disadvantages lying in wALS: high computational cost and imbalanced classes. Therefore, they further incorporate negative example sampling approach to decrease learning set. The framework can be illustrated by Figure 3. In phase I, a set of "negative" examples are sampled from missing data and generate a series of reduced matrices whose sizes are much smaller than that of original one. The sampling strategies consist of uniform random sampling, user-oriented sampling and item-oriented sampling. In phase II, wALS is used to approximate those reduced matrices, and finally combined to obtain the final approximation result. This strategy is referred as sampling ALS ensemble (sALS-ENS).

Figure 3. Ensemble of negative sampling based wALS for OCCF.

Experiments: Two datasets are used in experiments - Yahoo news dataset with clicks and social bookmarking dataset. Evaluation measures mean average precision (MAP) and half-life utility (HLU) are used. Baselines methods are AMAN and AMAU. For AMAN case, they use traditional CF approaches such as ALS-AMAN and SVD, user-user similarity and item-item similarity algorithms. For AMAU case, they rank items by popularity and one-class classification method. Results show that sALS-ENS and wALS-UserOriented approaches maintain better performance than other competing approaches.

Figure 4. Performance of different methods as a function of ratio between negative sampling and positive examples.

Week 4: Location-based and Preference-aware recommendation using sparse geo-spatial networking data

Title: Location-based and Preference-aware recommendation using sparse geo-spatial networking data, ACM SIGPATIAL GIS 2012.
Author: Jie Bao, Yu Zheng, Mohamed F. Mokbel

Background: Location-based social networking services (LBSNs), such as Foursquare, Yelp and GeoLife, allow users to leave their mobility and activity records. For example, an user can leave a comment for a restaurant, or check-in a museum. Actually, such location history encapsulates much knowledge about an user's interests and preferences, which can be further exploited to improve location recommendation systems.

System Overview: In this paper, they propose a location recommendation system which is location-based and preference aware. The location-based property take users' current location as an important aspect and only recommend points of interest that are near to him/her. Besides, the preference aware property takes care of target user's preferences as well as social knowledge mainly from local experts.

As shown in Figure 1, the overall system contains two major components - offline modeling and online recommendation. Offline modeling is a static module which precompute each user's preferences and local experts' knowledge. Online recommendation is a dynamic module requiring the realtime inputs of users' queries and current locations. Offline module provide precomputed results into online module to facilitate the efficiency of realtime recommendation.

Figure 1. System Overview.

In offline module, the system implements two tasks: (1) social knowledge modeling, and (2) personal preference modeling. Social knowledge modeling is to identify local experts by calculating people's expertise in each category of venue in each city. To achieve it, they build a user-location matrix and apply HITS (or Hypertext Induced Topic Search) to such matrix. HITS assumes that each user holds a score indicating its knowledge and each location is associated with an authority score to show its level of interest. Personal preference modeling aims to extract a user's preference from his/her visited location history. Here they use TF-IDF (Term Frequency - Inverted Document Frequency) method by taking location history as a document and categories as terms in the document. A weighted category hierarchy (WCH) is constructed to show an user's preference at various levels of granularity.

In online module, it first selects a set of candidate local expert and venues matching target user's preferences within a limited geographical range, and then infers a score of candidate locations based on the opinions of selected local experts. The realtime online recommendation is similar to collaborative filtering (CF), yet, much more efficient than CF, since the procedure of candidate selection stage avoids computing similarities with the full set of users in the city.

Results: They collect users' tips in New York City and Los Angeles from Foursquare. They take New Jersey users as target users to study the recommendation effectiveness and efficiency. The baseline approaches consist of (1) Most Preferred Category (MPC) recommendation [1], Location-based CF (LCF) [2] and Preference-based CF (PCF). As show in Figure 2, their proposed system outperforms competing baselines in precision and recall. Besides, their method maintains a relatively short processing time.

Figure 2. Performance in precision, recall and processing time.

References:

[1] Y. Zheng, L. Zhang, X. Xie, and W.Y. Ma. Mining interesting locations and travel sequences from gps trajectories. In WWW, pages 791–800. ACM, 2009.
[2]V.W. Zheng, Y. Zheng, X. Xie, and Q. Yang. Collaborative location and activity recommendations with gps history data. In WWW, pages 1029–1038. ACM, 2010.