Optimized Ranking-Based Techniques for Improving Aggregate Recommendation Diversity

ABSTRACT:

This paper investigates how demand-side factors contribute to the Internet’s “Long Tail” phenomenon. It first models how a reduction in search costs will affect the concentration in product sales. Then, by analyzing data collected from a multi-channel retailing company, it provides empirical evidence that the Internet channel exhibits a significantly less concentrated sales distribution, when compared with traditional channels. The difference in the sales distribution is highly significant, even after controlling for consumer differences. Furthermore, the effect is particularly strong for individuals with more prior experience using the Internet channel. We find evidence that Internet purchases made by consumers with prior Internet experience are more skewed toward obscure products, compared with consumers who have no such experience. We observe the opposite outcome when comparing purchases by the same consumers through the catalog channel. If the relationships we uncover persist, the underlying trends in technology and search costs portend an ongoing shift in the distribution of product sales.Singular Value Decomposition (SVD), together with the Expectation-Maximization (EM) procedure, can be used to find a low-dimension model that maximizes the loglikelihood of observed ratings in recommendation systems. However, the computational cost of this approach is a major concern, since each iteration of the EM algorithm requires a new SVD computation. We present a novel algorithm that incorporates SVD approximation into the EM procedure to reduce the overall computational cost while maintaining accurate predictions. Furthermore, we propose a new framework for collaborating filtering in distributed recommendation systems that allows users to maintain their own rating profiles for privacy. We conduct o_ine and online tests of our ranking algorithm. For o_ine testing, we use Yahoo! Search queries that resulted in a click on a Yahoo! Movies or Internet Movie Database (IMDB) movie URL. Our online test involved 44 Yahoo! Employees providing subjective assessments of results quality. In both tests, our ranking methods show signi_cantly better recall and quality than IMDB search and Yahoo! Movies current search. Reduced rank approximation of matrices has hitherto been possible only by unweighted least squares. This paper presents iterative techniques for obtaining such approximations when weights are introduced. The techniques involve criss-cross regressions with careful initialization. Possible applications of the approximation are in modeling, biplotting, contingency table analysis, fitting of missing values, checking outliers, etc.

1. Introduction

Collaborative Filtering analyzes a user preferences database to predict additional products or services in which a user might be interested. The goal is to predict the preferences of a user based on the preferences of others with similar tastes. There are two general classes of collaborative filtering algorithms. Low-dimension linear models are a popular means to describe

user preferences. The following are representative state-of-the-art collaborative filtering algorithms.Directly assume that the user preferences database is generated from a linear model, matrix factorization based collaborative filtering methods obtain an explicitlinear model to approximate the original user preferences matrix, and use the Pearson correlation coefficient,

which is equivalent to a linear fit. If we assume that users’ ratings are generated from a low-dimension linear model together with Gaussiandistributed noise, the Singular Value Decomposition (SVD) technique can be used to find the linear model that maximizes the log-likelihood of the rating matrix, assuming it is complete. If the rating matrix is incomplete, as is the case in real-world systems, SVD cannot be applied directly. The Expectation-Maximization (EM) procedure can be used to find the model that maximizes the log-likelihood of the available ratings, but this requires a SVD computation of the whole matrix for each EM iteration. As the size of the rating matrix is usually huge (due to large numbers of users and items in typical recommendation systems), the computational cost of SVD becomes an important concern. Deterministic SVD methods for computing all singular vectors on anm-by-n matrix take O(mn2+m2n) time, and the Lanczos method requires roughly O(kmn log(mn)) time to approximate the top k singular vectors [10]. In this work, we present a novel algorithm based on using an SVD approximation. There are several challenges for adapting item authority in these information retrieval systems due to the di_erent characteristics of documents like item or product informa-tion documents in commercial sites, as compared to web documents. The power of PageRank and HITS stems from the feature of links between web documents. PageRank and

HITS assume that a link from document i to j represents a recommendation or endorsement of document j by the owner of document i. However, in item information pages in commercial sites, links often represent di_erent kinds of relationships other than recommendation. For example, two items may be linked because both items are produced by the same company. Also, since these item information pages are generally created by providers rather than users or cus-tomers, the documents may contain the providers' perspec-tive on the items rather than those of users or customers. On the other hand, recommender systems are widely used in ecommerce sites to overcome information overload. Note that information retrieval systems work somewhat passively while recommender systems look for the need of a user more actively.

2. RELATEDWORK

Recommender systems can be built in three ways:

content-based _ltering, collaborative _ltering, and hybrid systems.Content-based recommender systems, sometimes called in-formation _ltering systems, use behavioral user data for a single user in order to try to infer the types of item attributes that the user is interested in. Collaborative _ltering compares one user's behavior against a database of other users' behaviors in order to identify items that like-minded users are interested in. Even though content-based recommender systems are e_cient in _ltering out unwanted information and generating recommendations for a user from massive information, they _nd few if any coincidental discoveries. On the other hand, collaborative _ltering systems enables serendipitous discoveries by using historical user data.

Collaborative _ltering algorithms range from simple nearest neighbor methods to more complex machine learning based methods such as graph based methods linear algebra based methods and probabilistic methods. A few variations of lterbot based algorithms and hybrid methods that combine content and a collaborative ltering have also been proposed to attack the so-called cold start problem.Tapestry is one of the earliest recommender systems.In this system, each user records their opinions (annota-tions) of documents they read, and these annotations are accessed by others' _lters. GroupLens4, Ringo and Video Recommender are the earliest fully automatic recommender systems, which provide recommendations of news, music, and movies. PHOAKS (People Helping One Another Know Stu_) crawls web messages and extracts recommendations from them rather than using users' explicit ratings. GroupLens has also developed a movie recommender system called MovieLens5. Fab is the _rst hybrid recommender system, which use a combination of content-based and collaborative _ltering techniques for web recommendations. Tango provides online news recommendations and Jester provides recommendations of jokes. A new concept of document relevance, often called document authority, and developed the PageRank and HITS algorithms, respectively, for better precision in web search. Both algorithms analyze the link structure of the Web to calculate document authorities. Haveliwala proposed topic sensitive PageRank, which generates multiple document authorities biased to each speci_c topic for better document ranking.Note that our approach is di_erent from general web search engines since we use user ratings rather than link structure for generating item authorities. Also, our approach is di_erent from topic-sensitive PageRank since we provide personalized item authorities for each user rather than topic-biased item authorities. Also, our approach is di_erent from recommender systems since it uses predictions of items as a ranking function for information search rather than generating recommendation.

3. SVD Approximation in Centralized Recommendation Systems

In this section, we discuss how to use SVD approximation to reduce the computational cost of the SVD based collaborative filtering in traditional centralized recommendation systems where the server keeps all users’ rating profiles. If the server uses the EM procedure shown in Section

2, the computational cost will be l · O(mn2 + m2n), in which l is the number of iterations of the EM procedure and O(mn2+m2n) is the computational cost of performing deterministicSVD on an m(users)-by-n(items) matrix. This cost is expensive because m and n can be very large in a recommendation system, from thousands to millions. The SVD Approximation technique of Drineas et al. shows that for any matrix A (m-by-n), if c rows are sampled and scaled appropriately, the top right singular vectors of the new matrix C (c-by-n) approximate the top right singular vectors of A. More formally, assume that in picking a certain row for C, the probability that the ith row in A is picked (denoted as pi) is such that pi ≥ β_A(i)_2/_A_2F , where β is a constant and _ · _, denoting a vector’s length, is equal to the squared root of the sum of the squares of all its elements, and suppose that if A(i) is picked, A(i)/√cpi will be included as a row in C. Denote H (n-by-k) as the matrix formed by the top k right singular vectors of C and Ak (Ak = UkSkV T k ) as the best rank k approximation to A. It follows that for any c ≤ n and δ > 0,_A−AHHT _2F≤ _A−Ak_2F +2(1+_8 ln(2/δ))_kβc_A_2F .(2)In addition, if pi = _A(i)_2/_A_2F , which implies that β isequal to one,_A−AHHT _2F≤ _A−Ak_2F +2(1+_8 n(2/δ))_kc_A_2F .(3) The proof of both inequalities can be found in [5].As discussed in Section 2, the objective of the maximization step in the tth iteration of the EM procedure is to compute