Recommending User-Generated ItemListsbyYidan LiuB.Eng., Computer Science, Beijing Institute of Technology, 2013A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)April 2016c© Yidan Liu 2016AbstractNowadays, more and more websites are providing users with the functional-ity to create item lists. For example, in Yelp, users can create restaurant listshe/she likes. In Goodreads, users can create booklists consisting of booksthey like. These user-generated item lists complement the main functionalityof the corresponding application and intuitively become an alternative wayfor users to browse and discover interesting items. Existing recommendersystems are not designed for recommending user-generated item lists di-rectly. In this work, we study properties of these user-generated item listsand propose two different models for recommending user-generated lists.We first model the problem as a recommendation problem and propose aBayesian ranking model, called Lire . The proposed model takes into con-sideration users’ previous interactions with both item lists and with indi-vidual items. Furthermore, we propose in Lire a novel way of weightingitems within item lists based on both positions of items, and personalizedlist consumption pattern. Through extensive experiments on a real item listdataset from Goodreads, we demonstrate the effectiveness of our proposedLire model.We then summarize the lessons learned from the recommendation modeland model the problem as an optimization problem. We show that thelist recommendation optimization can be reduced to Maximum k-CoverageProblem, which is an NP-hard problem. We derive three different problemvariants and proposed algorithms for each of them. We then conduct exper-iments to compare their results. Lessons learned and possible applicationscenarios are also discussed in the hope of helping us and more people im-prove the work. Furthermore, we propose several potential directions forfuture work.iiPrefaceThis thesis is a collaborative research work with my colleague Min Xie andmy supervisor Laks V.S. Lakshamanan. The three of us together publishedthe below listed paper [21], which subsumes the first chapter of this thesis.1. Liu, Yidan, Min Xie, and Laks VS Lakshmanan. ”Recommendinguser generated item lists.” Proceedings of the 8th ACM Conference onRecommender systems. ACM, 2014.Below lists the contribution of each co-author in detail.Dr. Laks V.S. Lakshmanan, my supervisor, motivated the initial brain-storming of the problem studied in this thesis. He later involved in formu-lating the research problem, designing algorithms as well as experiments,and revising the paper before submission.Min Xie, a PhD colleague of mine, has been very generous in helping meformulating the problem, designing algorithms to solve the problem, andconducting experiments to evaluate the solutions. Min provided me withideas of how to model an optimization problem. He also involved in writingand revising the aforementioned paper.I was in charge of summarizing all the discussions and formulating theideas at the early stage of the project. Later I was involved in formulatingthe optimization problem and designing algorithms to solve the problem. Iproposed three problems variants and designed algorithms to solve each ofthem. Also, I implemented the experiments conducted in the aforementionedpaper and this thesis, including collecting data from websites, preprocess-ing, adapting the algorithms, and evaluation. In addition, I was involved inwriting, reviewing and revising the published paper and this thesis.iiiPrefaceLemma 3.2.3 is derived from the chapter 2 of the below listed paper [11].1. Cohen, Reuven, and Liran Katzir. ”The generalized maximum cover-age problem.” Information Processing Letters 108.1 (2008): 15-22.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Recommendation Model . . . . . . . . . . . . . . . . . . . . . 42.1 Lists Properties . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Problem Studied . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Baseline Algorithms . . . . . . . . . . . . . . . . . . . . . . . 52.3.1 Popularity-based Approach . . . . . . . . . . . . . . . 52.3.2 Collaborative Filtering for Implicit Data . . . . . . . 62.3.3 Markov-based Recommendation . . . . . . . . . . . . 82.4 Recommendation Model . . . . . . . . . . . . . . . . . . . . . 92.4.1 User Preference over Individual Item List . . . . . . . 92.4.2 Modeling Observed Data . . . . . . . . . . . . . . . . 112.4.3 Model Learning . . . . . . . . . . . . . . . . . . . . . 122.5 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . 152.5.1 Goodreads Data Setup . . . . . . . . . . . . . . . . . 15vTable of Contents2.5.2 Granularity of Browsing . . . . . . . . . . . . . . . . 182.5.3 Convergence of Lire . . . . . . . . . . . . . . . . . . 192.5.4 Quality Comparison . . . . . . . . . . . . . . . . . . . 193 Optimization Model . . . . . . . . . . . . . . . . . . . . . . . . 213.1 Lessons Learned . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Problem Studied and Application Scenarios . . . . . . . . . . 223.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . 223.2.2 Problem Definition . . . . . . . . . . . . . . . . . . . 233.2.3 Problem Variants . . . . . . . . . . . . . . . . . . . . 233.2.4 Application Scenarios . . . . . . . . . . . . . . . . . . 273.3 Modelling Relevance . . . . . . . . . . . . . . . . . . . . . . . 283.3.1 User Item Relevance . . . . . . . . . . . . . . . . . . . 283.3.2 User List Relevance . . . . . . . . . . . . . . . . . . . 293.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.5 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . 323.5.1 Data Setup . . . . . . . . . . . . . . . . . . . . . . . . 323.5.2 Topic Modeling . . . . . . . . . . . . . . . . . . . . . 333.5.3 Ground Information . . . . . . . . . . . . . . . . . . . 333.5.4 Similarity Measures . . . . . . . . . . . . . . . . . . . 343.5.5 Evaluation Results . . . . . . . . . . . . . . . . . . . 353.5.6 Results Analysis . . . . . . . . . . . . . . . . . . . . . 414 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.1 Playlist Recommendation . . . . . . . . . . . . . . . . . . . . 434.2 Travel Package Recommendation . . . . . . . . . . . . . . . . 434.3 Implicit Feedback Recommendation . . . . . . . . . . . . . . 444.4 Hybrid-model Recommendation . . . . . . . . . . . . . . . . 455 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48viList of Tables2.1 How β value affect the AUC. . . . . . . . . . . . . . . . . . . 193.1 Datasets statistics . . . . . . . . . . . . . . . . . . . . . . . . 333.2 Topic modeling statistics . . . . . . . . . . . . . . . . . . . . . 33viiList of Figures1.1 Examples of user-generated lists from different websites. . . . 22.1 Statistics of Goodreads data w.r.t. lists and users, users andbooks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Statistics of Goodreads data w.r.t. lists and books . . . . . . 172.3 Convergence of Lire when varying dimensionality of the la-tent factors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4 Quality comparison for various algorithms. . . . . . . . . . . . 203.1 List recommendation scenario. . . . . . . . . . . . . . . . . . 223.2 Evaluation results on Goodreads data . . . . . . . . . . . . . 373.3 Evaluation results on Askubuntu data . . . . . . . . . . . . . 383.4 Evaluation results on Programmer data . . . . . . . . . . . . 393.5 Evaluation results on Unix data . . . . . . . . . . . . . . . . . 403.6 Compare the results of with and without content information 41viiiAcknowledgementsI wish to express my sincere thanks to Prof. Laks V.S. Lakshmanan for hisguidance during my Master’s study. His passion to research, attention todetail and hard work have been inspiring me during my exploration to theworld of recommender systems.I must also acknowledge my PhD colleague Min Xie for his assistance andsupport all along. Min has extensive knowledge in databases and recom-mender systems. He has given me a lot of suggestions on formalizing theproblem as well as writing the thesis.I would also like to thank my second reader, Prof. Giuseppe Carenini for hisinsightful comments and valuable suggestions. His comments on comparingthe two models has given me a new perspective on my thesis work.I would like to thank my fellow lab mates in Data Mining and ManagementLab. They have given me a lot of valuable suggestions and encouragementduring my Master’s study. Thanks also goes out to my friends ShanshanChen and Yan Peng, who have been encouraging me along the way.Most importantly, I would like to thank my family for the support and lovethey have given to me through my entire life. I must also acknowledge myfianc Yu Yan for his generosity and understanding.ixChapter 1IntroductionWith the development of web applications and services, people are providedwith more opportunities as well as assistance to discover the items of theirinterest. These days, a lot of websites provide users with the service ofcreating item lists. More specifically, users can create lists on the site,adding items to the lists for future use. The types of items in the listsoften depend on the web service. For example, in Youtube, users can createa list consist of music videos from the same genre. In Yelp, a user can createa restaurant list that he/she often visits. In Foursquare, users can create alist of places he/she would like to visit. These item lists are usually createdwith a certain theme and are often made public by default, which enablesthem to be shared with other users on the website.While conventional item recommendations have been well-studied, thereare few works directly focusing on recommending item lists. In this work, westudied the properties of user-generated lists and proposed multiple modelsfor picking the most relevant lists for each user.The primary motivations for studying item lists are three-folded. Firstly,these user-generated item lists have become a trend these days. As more andmore websites are providing users with such functionality, the popularity ofitem lists is self-evident.Second, the user-generated item lists can be indeed helpful for users todiscover items of their interests. For websites like Amazon [2] or Yelp [3],the quantity of the items on the website can be considerably large. Whileusers may be able to find more relevant items from a large number of items,it also becomes more challenging for them to search and identify their itemsof interest. The user-generated item lists provide an efficient way to managesimilar items. Moreover, since these lists can be shared with other users, it1Chapter 1. Introductionrepresents the wisdom of the crowds. With the help of item lists, users cannarrow down their search and find items of their interest more efficiently.Imagine that a user has found an item she likes and would like to dis-cover more items similar to this one. Instead of exhaustively searching withkeywords, she can just browse through the lists containing the current itemand look for more relevant items. This way the search range can be quicklynarrowed down. Below are some examples from different websites.(a) Yelp list example(b) Goodreads list exampleFigure 1.1: Examples of user-generated lists from different websites.Last but not the least, while conventional item recommendations havebeen well-studied, there are few works directly targeting at recommendinguser-generated item lists. We note that in the domain of music, playlistshave a similar structure as the user-generated item lists studied in this work,and several existing works have been devoted to developing recommendation2Chapter 1. Introductionalgorithms for playlists [6, 8, 9]. However, a huge difference between playlistsand the item lists studied in this work is that there usually exists a strongcorrelation between neighboring songs in a playlist: in most cases songs in aplaylist have to be consumed sequentially. This property has been exploredextensively by existing works such as [6, 9]. However, for the item lists inour case, such as book lists, twitter user lists, and shopping lists, items donot necessarily have to be consumed sequentially. In fact, a user might wellbe interested in only one or a few items in a list and may consume them inno particular order. Therefore, the lack of research works on user-generatedlist recommendation further motivates us to investigate the user-generateditem lists and make full use of them.To model the list recommendation problem, we analyze the properties ofthe user-generated item lists and proposed two different frameworks: mod-elling as a recommendation problem and an optimization problem. We firstpropose a new List Recommendation Model called Lire in this work. InLire , we take a user’s item preference into consideration when modelingthe user’s item list preference. One challenge in modeling a user’s interestin lists is that on websites such as Goodreads, because of the way user in-terface is presented and the huge number items contained in each list, usersusually just see the top items in a list, and may stop browsing the list whenenough items have been explored. Therefore, we weight items based on theirpositions in the list, and also learn users’ browsing patterns by fitting a pa-rameter that indicates roughly how many items need to be consumed beforea user stops browsing an item list.Then we summarize the lessons learned from Lire and propose an op-timization model. In this model, based on different ways of crediting re-peated items, we propose three problem variants and design algorithms foreach problem. We also take content information into consideration. Finallythree algorithms’ performances are compared on real-world datasets.In the rest of the thesis, we first model the problem as a recommendationproblem in Chapter 2. In Chapter 3, we model the problem as an optimiza-tion problem. Related works are discussed and compared in Chapter 4.3Chapter 2Recommendation ModelIn this chapter, we will first give a brief overview of the list properties. Next,we will give a detailed definition of the problem and present our recommen-dation model.2.1 Lists PropertiesIn this section, we will discuss in detail the properties of user-generated itemlists, in the hope of helping readers to understand the type of lists discussedin our work.First, the item lists we studied are generated by website users and areopen to other users on the website. Users can view lists created by otherusers, as well as comment or edit the lists. Similarly, the recommendationoutput will also be the user-generated item lists.Second, the item lists are composed by a set of consumable items. Userson the website can interact with both items and item lists. Items withina list are ranked in a particular order, either decided by the user or bymetadata such as popularity or modified date.Third, these lists usually have a specific them, and items within the listsare relevant to this theme. Therefore, a list is more than a random set ofitems. Internal relationships exist between these items, as well as betweenthe set of items and the list itself.Finally, user feedback on item lists is implicit. Many existing works onrecommender system focus on explicit rating datasets in which ratings cantake values from a small domain such as 1 to 5 [19]. However, for manyrecommendation scenarios, feedbacks from users take an implicit form, suchas whether a user purchased a product, liked a feed, clicked on an item, etc42.2. Problem Studied[14, 25]. For the item lists in our case, we can only get boolean observationsof whether a user has shown interest to a list or not, as compared to explicitratings which can be found on movie recommendation websites.2.2 Problem StudiedTo formulate the item list recommendation problem, consider a set of usersU = {u1, . . . , um}, a set of items T = {t1, . . . , tn}, and a set of item listsL = {l1, . . . , lq}, where each list li ∈ L is composed of a subset of items fromT .Let the set of item lists which user u has shown interest in be denotedas Lu, Lu ⊆ L, where a list l ∈ Lu can be a list which u has liked, voted, orcommented on. As is mentioned in 2.1, we only focus on implicit feedback.On most websites such as Goodreads which provide the functionality forcreating and sharing item lists, each user u is also associated with a set ofitems Tu, namely the items which u has previously consumed/rated.Problem 1 Item List Recommendation: Given T , U , L, for each useru ∈ U , based on u’s previously consumed items Tu, and u’s previously con-sumed item lists Lu, recommend to u the top-N item lists from L\Lu whichu will be most interested in.2.3 Baseline Algorithms2.3.1 Popularity-based ApproachFor many a recommendation application be it item recommendations oritem list recommendations, there is typically a long tail distribution w.r.t.the number of user ratings/interactions of each item. E.g., most of the itemscan observe only a few ratings, whereas only a few enjoy much attention fromusers. Thus this popularity bias becomes an important factor for explainingand understanding the underlying data, as was also observed in the Netflixcompetition [18].52.3. Baseline AlgorithmsOne simple item list recommendation algorithm thus is to directly lever-age the popularity bias and recommend item lists based on the popularityof each list. That is, we sort item lists w.r.t. the number of votes received,and recommend to every user the same set of top item lists which have re-ceived the highest number of votes. We note that this is very similar to howGoodreads website recommends item lists on every book detail page, i.e.,every popular book is likely included in many book lists, and according toour observation, only two of the hottest book lists are shown on the detailpage of every book.We call above algorithm GLB (GLoBal), as the recommendation gener-ated using the above approach is based on global statistics and is not person-alized. We also consider the following two different personalized variants,among the baselines; these methods are in part motivated by the heuris-tic popularity-based approaches for generating playlists which have beendemonstrated to have good performance [8].The first alternative PPOP (Personalized POPularity) is based on theintuition that a user u may only be interested in item lists which containitems that u is familiar with. Thus instead of recommending the mostpopular item lists across all users, we recommend the most popular itemlists which contain at least one item the user has interacted with before.The second alternative PIF (Personalized Item Frequency) is based onthe same intuition as PPOP that a user u is only interested in item listswhich contain items that u is familiar with. But instead of ranking thesecandidate item lists by popularity, we rank these candidate item lists byhow many items the list contains that the user has interacted before. Therationale for this heuristic is that the more books a list contains that theuser is familiar with, the more interesting that list to the user. Ties in PIFare broken using popularity of the corresponding item list.2.3.2 Collaborative Filtering for Implicit DataConsider a matrix ML of users’ interest in each list, where each entry yulis 1 if u has voted list l before, and 0 otherwise. We could simply apply62.3. Baseline Algorithmspreviously proposed collaborative filtering algorithms to this matrix ML.Typical collaborative filtering algorithms are based on latent factor mod-els, which were made popular because of their success in the Netflix compe-tition [19]. The nature of the datasets we consider is that user feedback isimplicit, i.e., it tends to be in the form of votes. Thus, we adapt the recentlyproposed BPR method [25], demonstrated to be very effective on implicitfeedback data, to item list recommendation.In BPR [25], each user u is associated with a latent factor wu, each itemti is associated with a latent factor hi, then similarly to other latent factormodels, the rating xˆui of user u on item ti can be predicted based on thedot product wu · hi.Because of the nature of the implicit dataset, similar to [25], we assumethat items which have been voted by a user are preferred over other items.Thus, we let ti u tj denote that user u prefers item ti to item tj . Followingthe notation introduced in [25], let DS denote set of triples (u, ti, tj) suchthat ti u tj holds. Then BPR formalizes a learning problem by maximizingthe following log-posterior.lnP (Θ | DS) ∝ lnP (DS | Θ)P (Θ)= ln∏(u,ti,tj)∈DSσ(xˆui − xˆuj)p(Θ)=∑(u,ti,tj)∈DSlnσ(xˆui − xˆuj) + ln p(Θ)=∑(u,ti,tj)∈DSlnσ(xˆui − xˆuj)− λΘ‖Θ‖2 (2.1)Here, ∝ refers to direct proportionality. σ = 11+e−x is the logistic sigmoidfunction. Θ denotes all the parameters (latent factors of users and items),and each latent factor is assumed to be following a zero mean Gaussianprior. Finally, λΘ is a model specific regularization parameter.As discussed in [25], the optimization criteria of BPR is closely relatedto Area Under the ROC Curve (AUC) [12]. And above posterior in Equa-tion 2.1 can be optimized through Stochastic Gradient Descent (SGD) which72.3. Baseline Algorithmshas been demonstrated to be useful for learning various latent factor-basedmodels [17].2.3.3 Markov-based RecommendationAs we will discuss in Chapter 4, the item list recommendation problemresembles the playlist recommendation problem studied before [8, 9]. Oneimportant difference is that with playlists, there is an inherent assumptionthat items in the list are meant to be consumed sequentially, which may notbe relevant for user-generated item lists such as book lists or product lists.We adapt algorithms proposed for playlist recommendation for the sake ofcomparison with the algorithms we develop.In the literature, one very recent and representative model-based ap-proach for playlist recommendation is LME or Latent Markov Embedding[9, 10]. In LME, similar to other latent factor models, each item ti is associ-ated with a latent vector hi. Given a playlist l, let each item in l at positiona be denoted as l[a]. In order to model the sequential property of a playlistl, we consider the probability of each list being “generated” as a series ofMarkov transitions between consecutive songs.P (l) =|l|∏a=1P (l[a] | l[a− 1]) (2.2)where the transition probability P (l[a] | l[a− 1]) can be modeled as a func-tion of the Euclidean distance ∆(hl[a], hl[a−1]) between the two songs underconsideration. Let A denote the set of all songs which can follow one specificsong l[a− 1], we denote by Z(l[a− 1]) =∑t∈A e−∆(ht,hl[a−1]) the summationover transition probabilities w.r.t. all possible next song given l[a − 1]. Wecan then use the following logistic model to estimate P (l[a] | l[a− 1]).P (l[a] | l[a− 1]) = e−∆(hl[a],hl[a−1])Z(l[a− 1]) (2.3)Similar to BPR, an SGD-like algorithm can be leveraged to learn thelatent factor model in LME by maximizing the likelihood of generating the82.4. Recommendation Modeltraining playlists. We note that the original model in [9, 10] is not person-alized.2.4 Recommendation ModelIn this section, we propose a List Recommendation Model called Lire for theitem list recommendation problem. Similar to previous latent factor-basedmodels, we map users and lists into the same latent space. Since we alsotake items into consideration, we map users and items into the same latentspace. So users, items, and lists are mapped into a joint latent factor spaceof dimensionality k. Accordingly, each user u is associated with a vectorwu ∈ Rk, each item ti with a vector hi ∈ Rk, and each list lj with a vectorgj ∈ Rk.2.4.1 User Preference over Individual Item ListIntuitively, given a user u and an item list lj , u’s interest in lj can be capturedusing two major factors: (i) the overall intrinsic quality of the list l itself,and (ii) the user’s aggregate interest in the items in lj . The first factor canbe modeled simply as an inner product between wu and gj , while the secondfactor involves aggregating user’s preferences over multiple items within lj .A simple idea to model the relationship between u and items in lj is toassume that each item in lj has an equal influence on user u. Thus we couldmodel the preference of u on lj using the following equation.xˆLuj = wugj +1|lj |∑ti∈lj(wuhi) (2.4)where |l| denotes the length of list l. In Equation (2.4), the first compo-nent wugj models user’s intrinsic interest in the list as a whole, and thesecond component models the relationship between u and items in lj . Wecall above model UNIFORM. Note that omitting the second component inEquation (2.4) amounts to directly factorizing the user list interaction ma-trix ML into user latent vectors and item list latent vectors and using that92.4. Recommendation Modelsolely as the model for recommendation.As discussed in Section 2.5.1, usually different items in the list havedifferent influence on a user. E.g., items which are shown at the top of alist, or items which are shown on the first page of the list if pagings areenabled, obviously have more significant influence on the user. This effectis usually due to the way different items of a ranking list are shown on theuser interface, and how users consume items in a list. Similar effect canalso be observed in information retrieval [15]. To capture this property, weadopt a function inspired by DCG (Discounted Cumulative Gain) [16], inorder to weight down items which are ranked low in a displayed item list orare shown in later pages in case of a paging enabled interface. Without anyambiguity, let ti = lj [i] denote the ith item in list lj , 1 ≤ i ≤ |lj |, and let hibe the corresponding latent factor associated with ti.xˆLuj = wugj + C(wuh1 +|lj |∑i=2wuhilog2 i) (2.5)where C = 1/(1 +∑|lj |i=21log2 i) serves as a normalization constant. We callabove model DCG.Although DCG is able to weight down items with lower position in thedisplayed list, given the huge number of items which may exist in an itemlist, items which are ranked low down in a list usually will not be examinedby the user. E.g., one list named “Best Book Cover Art” has 4,775 booksand it’s unlikely a user will dig deep down such lists. Thus, incorporatingthese lower ranked items in predicting a user’s preference over an item listmay introduce lots of noise. In this work, to address this issue, we makethe reasonable assumption that users browse an item list top down, andstop browsing when enough items have been seen. Note that this thresholdnumber of items which indicates the number of items users consume beforestopping, may vary among different users, thus needs to be personalized.Even for a specific user, this number may change from list to list, whichmay motivate us to associate one random variable per user and per list.However, given the sparsity of the dataset, such fine granularity threshold102.4. Recommendation Modelmodeling might easily lead to overfitting. Thus we consider in this worka trade-off approach by introducing a personalized granularity controllingbrowsing threshold τu.We set τu = β × ηu. Here, ηu ∈ Z+ is a personalized discrete randomvariable with a positive integer as its value, β is a constant which is used tocapture a coarse list browsing granularity. E.g., β can either be the numberof items contained in a single page on the website, or can just be a constantsuch as 10 items, which captures a finer granularity. The value of β can betuned according to the underlying data. In this work, using our Goodreadsdataset, we set β to be 5 which leads to the best performance on our dataset.Let I(i ≤ τu) be an indicator function which equals 1 if i ≤ τu is true,and 0 otherwise. We could adapt DCG to the following model DCG-T.xˆLuj = wugj + C(wuh1 +|lj |∑i=2I(i ≤ τu)wuhilog2 i) (2.6)where C = 1/(1 +∑|lj |i=2 I(i ≤ τu) 1log2 i) serves as a normalization constant.This model captures the idea that user u stops browsing beyond depth τu.2.4.2 Modeling Observed DataIn general users’ feedback data on item lists tends to be even more sparsethan the feedback on items. This makes learning users’ preference over itemlists more challenging. Fortunately, for most applications in which userscan create and share item lists, users also can and tend to interact withindividual items. E.g., on Goodreads, users can vote for book lists which aregenerated by other users, and can also add books to their shelves, meaningthey either have already read the books, or are interested in reading thosebooks in the future. Thus in addition to the matrix ML which capturesinteractions between users and lists, we also have the matrix MT whichcaptures interactions between users and items.Motivated by recent effort on Collective Matrix Factorization [28], weconsider that users share their preferences over items and lists. Thus wecould potentially leverage information learnt from users’ item preferences112.4. Recommendation Modelto help mitigate the sparsity issue when modeling users’ list preferences.Considering the fact that the interactions between users and items or be-tween users and item lists are often implicit, e.g., vote on Goodreads andsubscription on Twitter, we adapt the framework of BPR [25] for derivingthe optimization criteria for our item list recommendation problem. LetΘ = {W,G,H, τ} be the set of parameters associated with the Lire model.We assume Θ is associated with a zero-mean Gaussian prior. By assumingLu and Tu are conditional independent given Θ, the log of the posterior ofΘ given the observed user/item interactions and user/item list interactionscan be calculated as follows.P(Θ) = ln p(Θ |Lu ,Tu ) = ln p(Lu ,Tu | Θ)p(Θ)= ln p(Lu | Θ)p(Tu | Θ)p(Θ)= ln p(Lu | Θ) + ln p(Tu | Θ)− λΘ‖Θ‖2=∑(u,li,lj)∈DLslnσ(xˆLuij(Θ)) +∑(u,ti,tj)∈DTSlnσ(xˆTuij(Θ))− λΘ‖Θ‖2 (2.7)where DLS denotes the set of triples (u, li, lj) for which li u lj holds,DTS denotes the set of triples (u, ti, tj) for which ti u tj holds, And λΘ arethe model specific regularization parameters. The relationship between useru, list li, and list lj is captured by xˆLuij(Θ). Following the BPR model, wedecompose the estimator and define xˆuij as:xˆLuij(Θ) := xˆLui(Θ)− xˆLuj(Θ) (2.8)Similarly, the relationship between user u, item ti, and item tj is capturedby xˆTuij(Θ), which can be modeled as xˆTui − xˆTuj .2.4.3 Model LearningGiven P(Θ), we use Maximum-a-Posteriori (MAP) to perform a point es-timation of the parameters of the Lire model. Considering the fact thatP(Θ) is differentiable w.r.t. most parameters, one popular way to optimize122.4. Recommendation ModelP(Θ) is through gradient-based algorithms. A naive approach to doing sowould be to directly sample quadruples (li, lj , ti, tj), where li, lj are positiveand negative item list instances for a user u, and ti, tj are positive and neg-ative item instances. More precisely, user u prefers li to lj and similarly tito tj . However, this introduces a huge sampling space. Hence, we proposean alternating learning framework, where we first sample (u, ti, tj) from DTS ,until convergence of P(Θ)T = ln p(Θ |Tu ); then we sample (u, li, lj) fromDLS , until convergence of P(Θ)L = ln p(Θ |Lu ). We iterate above processuntil the overall posterior converges. We note that the gradient of P(Θ)Tw.r.t. Θ can be derived in a similar way as in [25], thus in the following, wefocus on how a gradient-based algorithm can be applied to P(Θ)L.Recall from Section 2.4.1 that during the learning process to maximizeP(Θ)L, the threshold parameter τu for every user takes on positive integersas values, thus P(Θ)L is non-continous w.r.t. Θ. To solve this issue, wefurther decompose the maximization of P(Θ)L into the following two steps:first, fix τu then optimize the remaining model parameters; then fix theremaining model parameters and optimize τu.Given a fixed τu, the following is the gradient of P(Θ)L w.r.t. the modelparameter Θ for DCG-T. Since UNIFORM and DCG only differ from DCG-T with respect to the calculation of xˆuj , the similar gradients can be derivedfor them. To simplify the notation, we omit mentioning Θ for xˆTuij(Θ) andxˆLuij(Θ) if there is no ambiguity.∂P(Θ)L∂Θ=∑(u,li,lj)∈DLs∂ lnσ(xˆLuij)∂Θ− λΘ∂‖Θ‖2∂Θ=∑(u,li,lj)∈DLs∂ ln 11+e−xˆLuij∂Θ− λΘΘ=∑(u,li,lj)∈DLse−xˆLuij1 + e−xˆLuij∂xˆLuij∂Θ− λΘΘ (2.9)Since ∂xˆLuij/∂Θ = ∂xˆLui/∂Θ−∂xˆLuj/∂Θ, we list in the following equationshow ∂xˆLuj/∂Θ can be derived for w, and g in DCG-T, where f indicates an132.4. Recommendation Modelindex into the corresponding latent factor.∂xˆLuj∂Θ={gjf + C(h1f +∑|lj |i=2 I(i ≤ τu) hiflog2 i) Θ = wufwuf Θ = gjfGiven τu = β × ηu, ηu may have a small domain given the size |lj | of alist lj . E.g., on Goodreads, when β is set to the number of items on a singleweb page, most lists have size less than 40 web pages. A simple idea thus isto enumerate all possible ηu and then find the optimal η∗u which maximizesP(Θ)L.η∗u = arg max1≤ηu≤d|lj |/βeP(Θ)L (2.10)However, when β is tuned to be at a finer granularity, the cost of aboveexhaustive search becomes prohibitive. Given the fact that P(Θ)L may notbe monotone w.r.t. τu based on different possible values of the latent factors,we consider a local search algorithm LocalOpt (Algorithm 1) which finds alocal maximum of τu.Algorithm 1: LocalOpt(β,Θ,|l|)1 η∗ ← A random integer between 1 and d|l|/βe;2 Q ← An empty candidate queue;3 Q.add((max(ηu − 1, 1), left));4 Q.add((min(ηu + 1, d|l|/βe), right));5 while Q is not empty do6 (η, direction) ← Q.pop();7 if Pη∗(Θ)L < Pη(Θ)L then8 η∗ ← η;9 if direction = left and η > 1 then10 Q.add((η − 1, left));11 if direction = right and η < d|l|/βe) then12 Q.add((η + 1, right));13 return η∗The overall algorithm for learning Lire is listed in Algorithm 2. In eachiteration of the main loop, we first sample (u, ti, tj) from DTS and updatemodel parameters W , H through Stochastic Gradient Ascent until conver-142.5. Experiment Resultsgence. Then we sample (u, li, lj) from DLS , and update model parametersW , G through Stochastic Gradient Ascent until convergence. Finally, wefind the optimal τ through Algorithm LocalOpt for every user. We repeatabove three steps until the overall model has converged or the maximumnumber of iterations has been reached.Algorithm 2: Lire -Learn(Θ, DLS , DTS , β)1 Random initialize Θ;2 repeat3 repeat4 Draw (u, ti, tj) from DTS ;5 Update W , H w.r.t. P(Θ)T ;6 until convergence;7 repeat8 Draw (u, li, lj) from DLS ;9 Update W . G w.r.t. P(Θ)L;10 until covergence;11 foreach User u do12 |l| ← Longest list size considered by u;13 τu ← β× LocalOpt(β,Θ, |l|);14 until convergence or max-iter has been reached ;2.5 Experiment Results2.5.1 Goodreads Data SetupTo evaluate our proposed model Lire and compare it with existing modelsfor item and playlist recommendation, we collected data from Goodreads.Due to the time constraint, we obtained during one month a 10% sample ofall user-generated book lists. As can be found from the Goodreads website,there exist in total around 34,750 user-generated book lists, and our obtainedsample includes 3,000 randomly selected book lists from the entire collection.To prevent the user-list interaction data from being too sparse, we filterbook lists which have fewer than 5 voters, and the resulting dataset contains1,998 book lists. For the set of voters obtained from these 1,998 book lists,we again filter out those who have voted less than 5 times within the 1,998152.5. Experiment Resultsbook lists. The total number of unique users left at the end of this processis 3,425. To fit users’ preference over individual items, we also obtained theset of books which have been added to these 3,425 users’ book shelves. Thetotal number of unique books is 105,030.In Figure 2.2 (a), we group lists into different buckets based on how manybooks they contain, and plot the number of lists which belong to each bucket.It can be seen that the majority of the obtained book lists contain only asmall number of books, but there does exist book list which contains 4,775books. The average number of books per list is 109. Similarly, in Figure 2.2(b), we group books into different buckets based on how many book liststhey belong to, and plot the number of books belong to each bucket. Again,there is an obvious power law distribution between the number of lists abook belongs to and the number of books that belong to the same numberof lists.Similar statistics of the Goodreads dataset can be observed between usersand lists, and also between users and books, as shown in Figure 2.1. In anutshell, the majority of users interact only with a few lists or books, whilea few power users interact with a large number of lists or books.From the obtained Goodreads dataset, we randomly sample 10% user/listinteraction data as the test set, and the remaining data is treated as train-ing set. To simplify the training process, we assume each parameter of themodel is associated with the same regularization parameter λ. Learning rateγ in the Stochastic gradient descent step, and regularization parameter λare selected based on grid search. In our experiments, we found that usuallysetting γ = 0.1 and λ = 0.01 leads to the best performance.Algorithms ComparedWe compare our proposed Lire with the following 5 baseline algorithmsas discussed in Section 2.3: 1. GLB; 2. PPOP; 3. PIF; 4. BPR; 5. LME.For BPR and LME, we also used grid search on the whole dataset to findthe best learning parameter settings. Finally, we consider two variations ofLire – Lire -UNIFORM with uniform item weighting, and Lire -DCG-T162.5. Experiment ResultsFigure 2.1: Statistics of Goodreads data w.r.t. lists and users, users andbooks 1 10 100 1 10 100 1000 10000Number of listsNumber of contained books(a) Number of contained books/frequency 1 10 100 1000 10000 100000 1 10 100 1000Number of booksNumber of containing lists(b) Number of containing lists/frequencyFigure 2.2: Statistics of Goodreads data w.r.t. lists and bookswith item position-based weighting and personalized browsing threshold.172.5. Experiment ResultsPerformance MeasureAUC is a commonly used metric for testing the quality of rank orderings.Following [25], we use the AUC metric described below to compare the pro-posed Lire model with the baseline algorithms as it has been demonstratedto be a good metric for evaluating Top-N recommendation tasks [5]. Sup-pose the set of users, positive book list instance (book lists voted by the userin the test dataset), negative book list instance (book lists which have notbeen voted either in the training set or testing dataset) in the test datasetare denoted as DtestS . Then, the formula to compute AUC is given by:1|DtestS |∑(u,li,lj)∈DtestSI(xˆui > xˆuj)where I(xˆui > xˆuj) is an indicator function which returns 1 if xˆui > xˆuj istrue, and 0 otherwise.2.5.2 Granularity of BrowsingWe first test how the granularity parameter β of the browsing threshold τcan affect the performance of the Lire model. As discussed in Section 2.4,on one hand, when setting β to a small value, the predicted browsing thresh-old may lack flexibility in predicting user’s browsing pattern across differentlists. Whereas on the other hand, setting β to be a large value, we may in-corporate unnecessary items into the prediction of user’s interest in a specificlist.The above trade-off is confirmed by our results on Goodreads datasetas shown in Table 2.1. By fixing the dimensionality of D to be 10, theoverall AUC on the test set increases when β is varied from 1 to 5, and AUCdecreases when we further increase the value of β. We observed similarresults for other D settings and suppress them since they are very similar.This result indicates that β in practice can be tuned based on the actualdataset.182.5. Experiment Resultsβ value1 3 5 7 9AUC 0.9778 0.9787 0.9830 0.9819 0.9800Table 2.1: How β value affect the AUC.2.5.3 Convergence of LireIn Figure 2.3, we demonstrate the convergence behavior of the Lire model.As can be found in Figure 2.3, our model converges fairly quickly (around5 iterations). We note that this convergence result also holds for otherdimensionality setting of the latent factors. 0.5 0.6 0.7 0.8 0.9 1 1.1 1.21 2 3 4 5 6 7 8 9 10AUCNumber of iterationD = 10D = 20D = 30Figure 2.3: Convergence of Lire when varying dimensionality of the latentfactors.2.5.4 Quality ComparisonFinally, we compare the performance of Lire with other algorithms as pre-sented in Section 2.3. From Figure 2.4, we can readily observe that thethree baseline algorithms GLB, PPOP, PIF do not perform nearly as wellas BPR and Lire . We note that this is in contrast with the result onplaylist dataset, where popularity-based methods, and especially personal-ized popularity-based methods excel [8]. Also the Markov-based approachLME does not perform as well as BPR and Lire . We claim that the rea-son for this is that user-generated lists such as book lists on Goodreads donot have the sequential consumption property normally assumed by playlistmodeling works.192.5. Experiment ResultsFor the two variations of Lire , we can see from Figure 2.4, both of themperform better than the other algorithms. Lire -DCG-T performs slightlybetter than Lire -UNIFORM. We consider that there are two reasons forthis: (i) Lire -UNIFORM may aggregate more than the necessary numberof items’ preference when modeling a user’s interest in an item list, and(ii) it ignores the fact that preference over items positioned higher up inthe list may have a larger impact on the user’s preference for the list. Inaddition, because Lire -UNIFORM needs to visit all items in an item listduring training, training of Lire -UNIFORM is much slower compared withLire -DCG-T.Figure 2.4: Quality comparison for various algorithms.20Chapter 3Optimization ModelIn this chapter, we modeled the list recommendation problem as an opti-mization problem. We will give a detailed explanation of the model andshow how we achieved efficient list recommendation with only user-iteminteraction and content information.3.1 Lessons LearnedBefore going into the model detail, we first summarized the lessons welearned from recommendation model.First, in the previous recommendation model, we only utilized the pastinteraction data, which is all implicit feedback. In fact, based on our ob-servation, there is usually rich content associated with the items as well asitem lists. This information has not been used in our studies.Second, from our previous observation, user-list interactions are usuallymuch sparser than user-item interactions. The reasons are 3-folded: 1) thenumber of items is much larger than the number of lists; 2) the activitiesthat user can perform on an item are more diverse than the activities onecan perform on a list. For example, in Goodreads, users can rate, commenton a book. They can also add books into their bookshelves. While for booklists, they can only comment a list or vote on a book list. 3) although manywebsites are providing the list functionality, not all users are aware of thefunctionality or have tried the functionality. Therefore, user-list interactionscan be very sparse as compared to user-item interactions. In our previousrecommendation model, we need both user-list interaction and user-iteminteraction to perform efficient recommendation, which might not performwell for those users who do not have sufficient user-list interactions yet.213.2. Problem Studied and Application ScenariosIf we can achieve effective list recommendation based only on user-iteminteractions, our model can also benefit more users, i.e., users who do nothave sufficient past interactions with lists.3.2 Problem Studied and Application Scenarios3.2.1 PreliminariesConsider the scenario where user u has interacted with several items in thepast. Some of these items appear in one or more lists. We want to recom-mend to u the top-k most relevant lists based on his/her past interactionwith items. Figure 3.1 shows the relationship between list, item and user.Figure 3.1: List recommendation scenario.From Figure 3.1, we can see that users only have direct interactionswith items. The relevance of a list to a user can be derived from the itemscontained in the list. For example, for u2 in Figure 3.1, l0 and l1 will likelyto be more close to u2’s interest than lm, since both of l0 and l1 contain u2’srelevant item tn. Moreover, note that tn has a higher rank in l1 comparedwith l0. Intuitively, an item which ranks high in a list is more representativeof the list, as compared to items which have lower ranks. Therefore, l1 ismore relevance to u2 than l0.223.2. Problem Studied and Application Scenarios3.2.2 Problem DefinitionIn this section, we introduce our notation and problem formulation. Given aset of users U , a set of items T , a set of lists L, and each user’s relevant(pastinteracted) items Pu, the goal is to find a subset of lists Ru, Ru ⊆ L, whichmaximizes the weighted coverage of u’s relevant items. In our problem, therelevant items associated with each user are provided as implicit feedbacks.Problem 2 Coverage problem: Given a set of items T , a set of listsL, a set of users U , an undirected bipartite graph G = (L,U,E), whereE(U,L)→ R+ is a weighted-coverage function, and a capacity constraint k.Each user is associated with a set of consumed items Pu ⊆ T , the goal is tofind a set of lists Ru from L in G which satisfies the capacity constraint andmaximizes the total value of weighted-coverage.3.2.3 Problem VariantsTo solve the problem, we first need to define the coverage function. We nowdiscuss the problem of finding a set of lists for an individual user. For a sin-gle user, the problem of finding a set of potential lists is very similar to theMaximum k-Coverage problem [13]. One difference between our problemand the weighted maximum coverage problem is that we generalize the itemweights. In conventional weighted maximum coverage problem, the weightof an item will remain the same regardless of the list covering it. In ourproblem, since the rank of the item may change in different lists, the weightof the item will also change accordingly.Moreover, in our case, lists may have overlapped items. We further derivethree problem variants based on different ways of crediting the items whichappear in multiple lists in the final selection. In the classical maximumk-coverage problem, each item would only be credited once. It makes nodifference in which set the item receives credit since the weight of each itemis the same for all the sets. However, in our problem, the weight of an itemalso depends on its rank within the list. Even if an item can receive credit233.2. Problem Studied and Application Scenariosfor only once, we need to determine in which list should the item be credited.We propose 3 problem variants with different crediting strategy.Problem 3 IndCredit Given a set of items T , a set of item lists L, auser u and his/her relevant items Pu, find k list from L, denoted as Ru,such that Cov(Ru) =∑l∈Ru∑t∈l weight(u, t, l) is maximized.In the first problem variant, the weighted-coverage of a candidate set Ru iscomputed by summing up the relevance values of all the lists in Ru. Here,we will give full credit to an item for every appearance in Ru. In this case,the lists can be regarded as independent of each other.Problem 4 MaxCredit Given a set of items T , a set of item lists L, auser u and his/her relevant items Pu, find k list from L, denoted as Ru,such that Cov(Ru) =∑t∈Pumaxl∈Ru{weight(u, t, l)} is maximized.In the second problem variant, given a candidate set Ru, for each relevantitem t, we only give credit to it within the list l where t receive the highestweight among all the lists in Ru, i.e., l = argmax{l ∈ Ru}weight(u, t, l).Problem 5 DecayCredit Given a set of items T , a set of item lists L,a user u and his/her relevant items Pu, find k list from L, denoted as Ru,such that Cov(Ru) =∑l∈Ru∑t∈l d(n, t)weight(u, t, l) is maximized, wheren denotes the number of times t already been covered in Ru and d(n, t) is adecay function.In the third problem variant, we allow an item to be credited for more thanonce, but with a decay credit. Consider a simple scenario where user uhas 2 relevant items, t1 and t2. In the candidate set of lists, t1 appears ink lists, while t2 only appears once. Apparently t1 is more important andpopular than t2. Therefore, we would lose this popularity information ifwe only credit t1 once. In order to keep this popularity information, andalso prevent t1 from dominating other relevant items, we have proposed theDecayCredit variant. This problem variant aims to find a balance between243.2. Problem Studied and Application ScenariosIndCredit and MaxCredit.We now introduce the Maximum k-coverage problem, which will helpderive the complexity of our problems.Maximum k-coverage problemThe maximum k-coverage problem can be described as follows[13]:INSTANCE: A universal set of elements U , an integer k, and a class R ofsubsets of U . Each element u ∈ U has an associated weight w(u).OPTIMIZATION PROBLEM: Select k subsets, A1, A2, . . . , Ak of U , whereeach subset selected is a member of R, such that the weight of the elementsin Ukl=1Al is maximized.Maximum k-coverage problem is known to be NP-hard[13]. The itemlist recommendation scenario is very similar to maximum k-coverage prob-lem. Consider the item set T in our problem as the universal element setU in maximum k-coverage problem, and the list set L as the subsets U . Inmaximum k-coverage problem, the goal is to find k subsets that maximizesthe total weight of items covered by k subsets. In our problem, the goalis to find k lists which also maximizes the total weight of items, w.r.t. thecoverage function defined in each specific problem variant.Lemma 3.2.1 MaxCredit is NP-hard.From the definition of MaxCredit problem, it is easy to see that theMaximum k-coverage problem is a special case of MaxCredit: consider thecase where the ranks of the same item among all the lists that cover it arethe same, which indicates that the weights of the same item among all thelists covering it are also the same. In this case, the Maximum k-coverageproblem has a solution if and only if the MaxCredit problem has a solution.Lemma 3.2.2 DecayCredit is NP-hard.253.2. Problem Studied and Application ScenariosThe Maximum k-coverage problem can also be reduced to DecayCreditproblem: still consider the case where the ranks of the same item among allthe lists covering it are the same. Also, define the decay function d(n, t) as:d(n, t) =1, n = 00, n ≥ 1 (3.1)In this case, the weights of the same item among different lists are the same,and each item would only be credited for once. The Maximum k-coverageproblem has a solution if and only if the DecayCredit problem has a solution.Lemma 3.2.3 MaxCredit problem has (2e−1e−1 )-approximation ratio.We now prove that by reducing the MaxCredit problem to GeneralizedMaximized Cover Problem[11], we can get a (2e−1e−1 )-approximation bound.The formal definition of GMCP is as follows: Given a set of items E, aset of bins B, and a cost constraint L, each item has a pair of profit/costassociated with it, which will differ depending on the set covering it, eachset is also associated with a cost. The problem is to find a selection ofbins and items under the cost constraint, and the profit is maximized. Forthe GMCP, let the weights of items be 0, and let the weights of lists beunit. Let budget L equals to k. Since the assignment function in GMCPassigns each item t to only one list, it must be the list where t receivesthe highest weight. Otherwise there must exist another assignment whichachieves higher coverage than the current assignment. So the MaxCreditproblem has a solution if and only if GMCP has a solution. In GMCP, theyproposed a greedy algorithm which selects a subset of elements with themaximum residual density in each step. The selection for each greedy step isa α−approximation and the approximation bound for GMCP is 1+α−α·e−1α1−e− 1αusing the greedy algorithm[11]. In the MaxCredit problem, each greedystep is optimal since the sets of items are the lists, and we can get anoptimal solution by traversing all the lists. Therefore, we can get a 2e−1e−1approximation bound for MaxCredit problem.263.2. Problem Studied and Application Scenarios3.2.4 Application ScenariosIn this section, we briefly discuss the application scenarios of our problem.Capacity constraint The capacity constraint in our problem determineshow many list recommendations each user receive. This conforms to theTop-k recommendation, where only k lists with the highest relevance willbe recommended.Novelty of recommendation We can further add Novelty into considera-tion by differentiating between ”old” and ”new” items and incorporate thisinto the utility function. Old items refer to items that the user has alreadyinteracted with and new items refer to the opposite. This is similar to theexplore/exploit tradeoff and should also be personalized. For example, auser may have his/her own preference of how many new items/old items tobe covered in the final recommendation lists Ru. This can be measured bya function g(u, t), where u is the current user and t is the specific item wewant to measure. The utility function can be represented as:Cov(Ru) =∑t∈Pu{maxl∈Ru{weight(u, t, l)}+ g(u, t)}. (3.2)One issue about equation 3.2 is that the model may get into the extreme ofrecommending too many new items or old items. To prevent this, we canreplace the utility function with:Cov(Ru) = F{Gu(O,N),∑t∈Pumaxl∈Ru{weight(u, t, l)}}. (3.3)Here, O is the set of old items relevant to user u covered by lists in Ru,and N is the set of new items relevant to u. Gu(O,N) measures the overallnovelty of the recommendation. F is an aggregation function which takesboth novelty and coverage into consideration.Diversity of recommendation Another commonly-used measurement forrecommendation is Diversity. Considering two book lists l1 and l2. l1 iscomposed of all sci-fi books while l2 is composed of books from variousgenres or topics. In this case, l2 is more diverse than l1. Similar to novelty,273.3. Modelling Relevanceusers’ preference to diversity should also be personalized. Diversity can betaken into consideration using:Cov(Ru) = F{Du(Ru),∑t∈Pumaxl∈Ru{weight(u, t, l)}}. (3.4)In 3.4, Ru is also the set of recommended lists to user u, and Du(Ru) mea-sures the personalized diversity rewards of the recommendation set. F is anaggregation function which takes both diversity and coverage into consider-ation.3.3 Modelling Relevance3.3.1 User Item RelevanceTo determine the relevance of each user and each item, we incorporatedusers’ past interactions and items’ content information.We consider that user’s past interacted items can directly reflect the user’staste and interest. The past interactions between users and items can bemodeled as a 0-1 matrix, P . Each entry P (u, t) in the matrix indicateswhether or not user u has consumed item t in the past.Apart from direct interaction information, items’ content information can beused to represent the item features, and further help find relevant items .Thecontent information refers to text information associated with each item, andis usually depend on the particular web service. For example, in Goodreads,every book has text information including title, author, abstract, publisherand so on. For other shopping websites, content information may includeitem type, brand and so on. Using classical topic modelling strategy, we areable to get the topic distribution of each item. For each user u, based onthe user’s past item interactions, we can derive the user’s preference overdifference topics.Therefore, for user u, the relevance between u and each item t can be283.3. Modelling Relevancerepresented as follows.rel(u, t) = 1Rut+ Ct(t) · Cu(u) (3.5)In 3.5, 1Rut is an indicator function which equals to 1 if u has interactedwith t and 0 otherwise. Ct(t) denotes the content feature of t and Cu(u)denotes the content feature of u. By performing a dot product between usercontent feature and item content feature, we can get the content relevancebetween the user and the item.3.3.2 User List RelevanceFor a specific user u, the relevance of a list l is computed over all the itemsin l. There are two factors to consider. First, the appearance of u’s relevantitems within the list. If l contains an item t which is relevant to u, then therelevance between l and u will increase. Also, the more relevant t is to u,the relevance gain between l and u will be larger. Second, the rank of therelevant item within l. Ranking is a good measure to indicate how close theitem is to the theme of the list. Consider two lists l1 and l2, both containingan item t which the user u likes. Since l1 and l2 may have different theme,the importance/value of t within these two lists can also be different. If tis ranked higher in l1 than l2, it is likely that t is closer to the theme of l1,which indicates l1 will better fit the user’s taste than l2 . Thus, we also needto take the rank into consideration. By combining these two parts togetherusing multiplication, we can get the weight of t to u within the context of l.weight(u, t, l) = rel(u, t) ∗ rank(t, l). (3.6)One simple way to aggregate the relevance of items into the relevance of thelist is summation. Given each user, we first get the weight each item withincandidate lists, then sum up the weights and get the relevance of l.rel(u, l) =∑t∈lweight(u, t, l) (3.7)293.4. Algorithms3.4 AlgorithmsBased on the three problem variants proposed in the previous section, wenow discuss the algorithms for these problems.IndCredit Each relevant item can be covered repeatedly with full creditin Ru. In this case, each list l ∈ Ru will be measured independently. Theweighted-coverage of Ru can be represented as:Cov(Ru) =∑l∈Ru∑t∈lweight(u, t, l) (3.8)Properties• Additivity. Cov(R) = Cov(R1) + Cov(R2), where R1 ∪R2 = R.MaxCredit Each relevant item t can only be credited once in Ru, andthe list covering it should be the list where t receives the highest weightamong all the lists in Ru. This problem resembles Generalized MaximumCoverage Problem. (GMCP) [11]. The corresponding weighted-coverage ofRu can be represented as:Cov(Ru) =∑t∈Pumaxl∈Ru{weight(u, t, l)} (3.9)Properties• Subadditivity. Cov(R) ≤ Cov(R1) + Cov(R2), where R1 ∪R2 = R.We now present the greedy algorithm for MaxCredit. At each stage,select the list with the maximum coverage. When computing the coveragevalue for each list, residual item weight is used instead of the original itemweight. This ensures that each item only receive credit in the list where theitem has the highest rank.weight(u, t, l) =0, weight(u, t, l) < maxl′∈Ru{weight(u, t, l′)weight(u, t, l)−maxl′∈Ru{weight(u, t, l′)}, otherwise (3.10)303.4. AlgorithmsUsing the above subroutine, the greedy algorithm for MaxCredit is asfollows.Algorithm 3: Greedy for MaxCredit1 L ← list set, T ← item set, P ← user’s relevant items ;2 R ← empty candidate set, k ← the number of lists in the final candidate set;3 Compute the weighted coverage of items in P for all the list in L ;4 for stage = 1, 2, . . . , k do5 l ← the list with the highest weighted coverage in L;6 Q ← the set of relevant items in l ;7 R.add(l);8 L.remove(l);9 for t ∈ Q do10 Recompute the residual weight of t in all lists in L which contain t ;11 return R.DecayCredit The weight of each item will decay when covered multipletimes by Ru. In this case, the lists in Ru are not longer independent to eachother and Ru should be measured as a whole. We can use a decay functiond(n, t) to represent the decay, where n is the number of appearances of itemt in Ru. For each item covered in the set, The corresponding weighted-coverage of Ru can be represented as:Cov(Ru) =∑l∈Ru∑t∈ld(n, t)weight(u, t, l) (3.11)Properties• Subadditivity. Cov(R) ≤ Cov(R1) + Cov(R2), where R1 ∪R2 = R.Here is the greedy heuristic for picking Ru. Each time the algorithm picksthe list with highest weighted-coverage of relevant items. A recomputationis needed at the end of each iteration in order to reflect the reduction ofweights of the covered items.313.5. Experiment ResultsAlgorithm 4: Greedy for DecayCredit1 L ← list set, T ← item set, P ← user’s relevant items ;2 R ← empty candidate set, k ← the number of lists in the final candidate set;3 Compute the weighted coverage of items in P for all the list in L ;4 for stage = 1, 2, . . . , k do5 l ← the highest weighted coverage in L;6 Q ← the set of relevant items in l ;7 R.add(l);8 L.remove(l);9 for t ∈ Q do10 Recompute the weight of t in all lists in L which contain t ;11 return R.3.5 Experiment Results3.5.1 Data SetupFor experiments, we used datasets from Goodreads and Stack Overflow.The Goodreads dataset was collected and used in our previous work. InGoodreads data, user can interact with a list by voting on the book list.Here, we also need the content information. So we did extra work to collectand process the title as well as the abstract of each book. We also removeditems which we can not get the content information due to language reason.Apart from Goodreads data, we also used Stack Overflow datasets. StackOverflow is an online Question&Answer website. In Stack Overflow, userscan post questions, answer questions, and vote for questions or answers.Each post contains one question and multiple answers. Each post also hasone or more tags, which are edited by users and help to categorize thepost. For Stack Overflow data, we regard each tag as a list and each post(including both the question and the answers) as a single item. A user caninteract with an item/post by adding the question or the answers. The StackOverflow datasets are downloaded from Stack Exchange Data Dump [1].The data dump contains 315 small datasets of different areas. We selectedthree datasets: Programmer, Askubuntu, and Unix. Table 3.1 shows thestatistical information of the datasets we use.323.5. Experiment ResultsDataset # of Users # of Items # of ListsGoodreads 3,425 70,413 1,998Askubuntu 18,061 167,765 2,409Programmer 8,007 35,560 1,598Unix 5,975 48,430 1,620Table 3.1: Datasets statistics3.5.2 Topic ModelingWe used Latent Dirichlet Allocation for getting content features. LDAis a three-level hierarchical Bayesian model which has been commonly usedin topic modeling applications. In LDA, each document can be viewed as amixture of multiple topics, and each word in the document is attributableto one of the topics. For Goodreads, we regard each book as a document.The title and abstract parts of the book compose the document. For StackOverflow, each post is regarded as a document. The content of the question,as well as the answers, composes the document. For each dataset, we deter-mine the number of topics using grid search on the whole dataset. Figure 3.2shows the dataset information and parameters we used in experiments.Dataset # of Documents # of Terms # of TopicsGoodreads 70,413 399,002 200Askubuntu 167,765 1,029,247 80Programmer 35,560 561,257 80Unix 48,430 674,316 80Table 3.2: Topic modeling statistics3.5.3 Ground InformationFor Goodreads dataset, we used the known user-list interaction data asground truth for evaluation. For each user, we compared the similaritiesbetween the set of lists that the user has interacted with and the set of liststhat are recommended by the algorithm. The similarity is used for repre-senting algorithm accuracy. In other words, the more similar the recommend333.5. Experiment Resultslists to the ground lists, we consider the corresponding algorithm to be moreaccurate.For Stack Overflow datasets, there is no direct user-list interaction dataavailable for evaluation. We consider that the ground information can beregarded as personalized global information. Therefore, if we can derive suchpersonalized global information from the data, we can use it as the groundtruth. Since we have the user-post interaction and the post-tag relation, wecan derive a user-tag relation that for each user u. In this user-tag relation,for each user u, tags are ordered by the number of times u has interactedwith the tag through directly interacting with posts. In the experiments,we will use this user-tag relation as the ground information to evaluate therecommendation.3.5.4 Similarity MeasuresOne crucial subroutine of the evaluation process is to compare the similaritybetween the recommended lists and the ground lists. We applied multiplemeasures for calculating the similarity.Jaccard The Jaccard similarity measure is a commonly-used metric forcomparing the similarity of different sets. It is defined as the size of theintersection divided by the size of the union of the two sets. The value ofJaccard varies from 0.0 to 1.0, with 1.0 representing two same sets of items.J(A,B) =A ∩BA ∪B (3.12)In our experiments, intersection is computed as the set of lists which ap-pear in both the recommendation result as well as the ground information.Nested Jaccard Because each recommendation is actually a list, whichconsists of multiple items, it might not be enough just comparing their IDs.For example, it is possible that there are two lists which contain the same setof items, but with different list IDs. In this case, merely comparing the listIDs will not give the accurate result. Therefore, we proposed a Nested Jac-card measurement for evaluating the similarity between the recommendedlist and the ground list. In Nested Jaccard, two lists are determined as the343.5. Experiment Resultssame lists if they both contain a certain number of items.Topic We also proposed topic measure for comparing recommended list andground list. For each list, we can calculate its topic feature by summing uptopic features of the items in the list. Then we can calculate the cosinesimilarity of recommended list and ground list. The cosine similarity iscalculated as:similarity = cos(θ) =A ·B‖A‖‖B‖ (3.13)A and B are the feature vectors to be compared. The similarity value isbounded in 0.0 to 1.0, and higher value indicates higher similarity.NDCG In both Jaccard and nested Jaccard, the order of recommended listsis not considered. In our experiments, the order is crucial for Stack Overflowdata, since the ground information is personalized tag ranking. Therefore,we further choose Normalized Discounted Cumulative Gain for eval-uating the recommendation accuracy. NDCG measures the performance ofa recommendation based on the graded relevance of the recommended ele-ments. It varies from 0.0 to 1.0, with 1.0 representing the ideal ranking ofthe elements. The discounted cumulative gain can be calculated as:DCGk =k∑i=12reli − 1log2(i+ 1)(3.14)where k represents the number of recommended elements. The normal-ized DCG is calculated as:nDCGk =DCGkIDCGk(3.15)where IDCGk is the idea DCG for a given set of elements.3.5.5 Evaluation ResultsWe first show the evaluation results for Goodreads dataset, where Jaccard,Nested Jaccard, and Topic metrics are applied. For each user u, we comparethe similarity between the ground lists Pu and the recommended lists Ru.For the results shown below, x-axis represents the similarity value between353.5. Experiment Resultsrecommendation lists and ground lists, and y-axis represents the number ofusers that falls into each similarity range. For example, for user u, if thesimilarity value between u’s ground lists and u’s recommended lists is 0.45,then the number of users for similarity 0.4 will increment by 1.Figure 3.2 shows the evaluation results on Goodreads dataset, usingJaccard, Nested Jaccard, and Topic measures. From Figure 3.2, we can seethat the recommendation results from MaxCredit and DecayCredit are moresimilar to the ground truth as compared to the recommendation result fromIndCredit.Then we show the evaluation results for Stack Overflow datasets. Forthese datasets, we applied NDCG and Topic to measure the list similarity.Figure 3.3, Figure 3.4 and Figure 3.5 shows the evaluation result onthree datasets from Stack Overflow. From the figures we can see that theperformances of three algorithms are very close. DecayCredit has higheraccuracy in terms of list similarity.Next we compare the evaluation results for both with content informa-tion and without content information. Figure 3.6 shows the comparisonresults of with/without topic feature on Goodreads data. It is easy to seethat the algorithms with content information perform better than algorithmswithout content information.363.5. Experiment Results(a) Recommendation similarity using Jaccard(b) Recommendation similarity using Nested Jaccard(c) Recommendation similarity using TopicFigure 3.2: Evaluation results on Goodreads data373.5. Experiment Results(a) Recommendation similarity using Jaccard(b) Recommendation similarity using Nested Jaccard(c) Recommendation similarity using NDCG(d) Recommendation similarity using TopicFigure 3.3: Evaluation results on Askubuntu data383.5. Experiment Results(a) Recommendation similarity using Jaccard(b) Recommendation similarity using Nested Jaccard(c) Recommendation similarity using NDCG(d) Recommendation similarity using TopicFigure 3.4: Evaluation results on Programmer data393.5. Experiment Results(a) Recommendation similarity using Jaccard(b) Recommendation similarity using Nested Jaccard(c) Recommendation similarity using NDCG(d) Recommendation similarity using TopicFigure 3.5: Evaluation results on Unix data403.5. Experiment ResultsFigure 3.6: Compare the results of with and without content information3.5.6 Results AnalysisFrom the evaluation results shown above, we have the following observations.1. MaxCredit and DecayCredit achieve higher recommendation accura-cies than IndCredit. From the evaluation results, we can see thatthe lists recommended by MaxCredit and DecayCredit adopt highersimilarity to the ground lists. This conclusion holds when differentsimilarity measure are applied. The reason for this could be the dom-inance of popular items. Recall that in IndCredit, items can receivefull credits for multiple times. There are a small set of items whichappear frequently in lists and have been interacted by many users. Ifwe give the item full credit in every list it appears, these popular itemswill be likely to dominating other items that the user has interacted.Imagine a simple case where user u has interacted with t0, t1 and t2.Both t0 and t1 appear in list l0 and l1, while t2 only appears in l2. Ifwe can only recommend two lists to u, l0 and l1 are more likely to berecommended by IndCredit than l2 since the former two both containtwo relevant items. In this recommendation, t2 will be left out andthe u’s preference is not accurately represented. If we use MaxCreditor DecayCredit, in the first step, we would still pick one of l0 and l1.413.5. Experiment ResultsSuppose we pick l1, then l0’s marginal coverage will decrease and wehave more possibility to select l2.2. Recommended lists and ground lists are similar in topics. From theevaluation result, recommended lists and ground lists are very similarwhen using Topic as similarity measure. This indicates that althoughthe recommended lists generated by the algorithms are not exactly thesame as ground lists, they fall into similar topics and the recommen-dation can be potential fits for future consumption.3. The difference between three algorithms’ performances is smaller inStack Overflow datasets then in Goodreads dataset. From the eval-uation results of Stack Overflow dataset, the performances of threealgorithms are very close. Although DecayCredit usually has the bestperformance, the difference is very small. We consider the reason ofthe small difference is that in Stack Overflow, the number of lists con-taining a certain item is small. In our model, each post is an itemand the associated tags are the lists containing the item. Usually thenumber of tags for one post is around three. Therefore, for a itemappearing in multiple lists, the credit it receives would not change toomuch between different algorithms.42Chapter 4Related WorksWe referred to related research works from several categories.4.1 Playlist RecommendationUser-generated item lists are similar to playlists as explored in previousworks such as [9] and [6]. An important observation made by these works isthat neighbouring items in a playlist are usually correlated with each otherand items in a playlist usually have to be consumed sequentially. E.g., inLME [9], the proposed model assumes that transitions between neighbouringitems in a playlist satisfy the Markovian property, i.e., next song in a playlistdepend only on the current song which is playing. Similarly, in [6], theauthors consider that each song in a playlist is closely related to other songswhich are played within the same short time window. An interesting surveyof algorithms for modelling playlists is presented in [8]. This sequentialassumption differs our work from the playlist recommendation works.4.2 Travel Package RecommendationThe proposed item list recommendation problem is also related to recenteffort on package recommendation [24, 26, 29]. Although a travel packageis presented in a list structure, travel package recommendation is differentfrom our work in several aspects. The first one is the heterogeneity of items.Although both travel package and list consist of multiple items, the itemsin a travel package are much more heterogeneous than the items in the listin our problem. For example, in a travel package, the items can be flight,hotel, tours and so on. However, in the list, the items are of the same434.3. Implicit Feedback Recommendationtype, such as books, pins, or places, which depends on the services providedby the website. The second major difference is that most of these worksfocus on handling hard constraints specified by users as opposed to learninguser’s preferences over item lists from previous feedback. In [20], the authorspropose a Probability Matrix Factorization-based approach to model user’spreferences over travel packages, where each package is composed of a setof places of interest. The focus of their work is on modelling the cost of apackage. In our work, we focus on how item preferences can be aggregatedto model user’s preferences over item lists.4.3 Implicit Feedback RecommendationImplicit data settings create a huge challenge for existing latent factor mod-els. In particular, there is little information on what users dislike [14].Researchers have recently proposed various models for modelling implicitdatasets. One notable work in this direction is BPR [25], in which the au-thors proposed to solve the implicit data problem through a general Bayesianranking model, which can learn users’ preferences over items by samplingpositive and negative/missing entries from the user rating matrix. Anotherwork which proposes to model implicit dataset through ranking is CLiMF[27], which instead of optimizing AUC as in BPR, considers Mean ReciprocalRank as the optimization criterion. In [22], the authors argue that reasoningabout preferences between individual items might be too fine-grained, andpropose to lift item preferences to preferences over sets of items. The focusof this work is still on item recommendation, and when aggregating itempreferences, the proposed model does not consider the position of an item,and the defined item sets are hidden from users thus there is no need tomodel how users might view items within a set. Other works on implicitdatasets include [14], in which the authors propose a different way of mod-elling implicit datasets by weighting the importance of each observed ratingthrough heuristic functions. In [23], the authors propose a more complexmodel which models the relationship between the original implicit dataset(which can be considered as a bipartite graph between users and items) and444.4. Hybrid-model Recommendationrandom bipartite graphs which capture potential items which users haveconsidered before actually consuming items in the original dataset.4.4 Hybrid-model RecommendationContent-based and collaborative filtering models are both very popular inrecommender systems. The collaborative filtering methods usually sufferfrom cold-start issue and popularity bias. The content-based methods re-quire the content to be encoded as meaningful features and are usually easyto overfit [7]. This brings in a third type of method, which is the hybrid ap-proaches. There are some recommendation works about combining matrixfactorization with regression, i.e., using both implicit features and explicitfeatures [4, 30]. In [30], the authors applied a simple addition to combine thetwo parts. In [4], the model learns a transition matrix to transform explicitfeatures to latent factors. In our work, we used implicit features when mod-eling list recommendation as a recommendation problem, and used explicitfeatures when modeling it as an optimization problem. A potential futurework direction would be to combine implicit features with explicit features.45Chapter 5ConclusionIn this work, we motivate the problem of recommending user-generated itemlists and proposed two different models to solve the problem. Existing worksin recommender system usually focus on item recommendation. Thus, theydo not consider how user’s preference over item lists can be decomposed intopreferences over individual items within the list.In this work, we propose two models to capture users’ preference overitem lists. Based on our observations of user-generate item lists, we firstpropose a novel model Lire which models users’ preferences over item listsby aggregating users’ preferences over individual items within a list. Wecapture how users perceive an item list by weighting items within a listbased on position. We also take into consideration the number of items auser might consume before deciding whether to like this list or not. Throughextensive experiments, we demonstrate that our proposed model has a betterperformance compared with many existing recommendation algorithms.Next, we summarize the lessons we have learned from the Lire and pro-pose an optimization model for solving the problem. Based on different waysof rewarding repeatedly-appeared items, we specify three problem variants,presenting hardness proof and algorithms for each problem variant. We fur-ther conduct experiments on four datasets collected from two websites andshow the effectiveness of our optimization model.46Chapter 6Future WorksIn this chapter, we propose potential future works for list recommendationwork.First, we can study how temporal information from the dataset an beleveraged to help better model a user’s preference over item lists. E.g., wecan check whether liking a list will result in subsequent interactions withthe items in a list.Second, many applications that provide list functionality also involvesocial network. Friendship between users often indicates similar preferences.This further raises the question that how social influence can be incorporatedinto our current models to facilitate list recommendation.Third, it’s interesting to think about whether we can generate expla-nation for our recommendation. Explanation can be useful for users tounderstand why certain recommendations are generated. Specifically in ourproblem, explanation is particularly important for lists with larger size. Forexample, when a long list is recommended to the user, it would be impossiblefor the user to browse over the entire list trying to find interesting items. Ifwe can give the user an explanation, such as ”this list is recommended to youbecause we think you might be interested in these items in the list” alongwith the relevant items, the recommendation would be more effective.47Bibliography[1] https://archive.org/details/stackexchange, April 2016.[2] http://www.amazon.ca/gp/help/customer/display.html?nodeId=1197914, April 2016.[3] http://www.yelp.com/list_search, March 2016.[4] D. Agarwal and B.-C. Chen. Regression-based latent factor models. In Pro-ceedings of the 15th ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining, KDD ’09, pages 19–28, New York, NY, USA,2009. ACM.[5] A. Ahmed, B. Kanagal, S. Pandey, V. Josifovski, L. G. Pueyo, and J. Yuan. La-tent factor models with additive and hierarchically-smoothed user preferences.In WSDM, pages 385–394, 2013.[6] N. Aizenberg, Y. Koren, and O. Somekh. Build your own music recommenderby modeling internet radio streams. In Proceedings of the 21st InternationalConference on World Wide Web, WWW ’12, pages 1–10, New York, NY, USA,2012. ACM.[7] X. Amatriain. The recommender problem revisited. In Proceedings of the 8thACM Conference on Recommender Systems, RecSys ’14, pages 397–398, NewYork, NY, USA, 2014. ACM.[8] G. Bonnin and D. Jannach. Evaluating the quality of generated playlists basedon hand-crafted samples. In ISMIR, pages 263–268, 2013.[9] S. Chen, J. L. Moore, D. Turnbull, and T. Joachims. Playlist prediction viametric embedding. In Proceedings of the 18th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining, KDD ’12, pages 714–722, New York, NY, USA, 2012. ACM.48Bibliography[10] S. Chen, J. Xu, and T. Joachims. Multi-space probabilistic sequence modeling.In KDD, pages 865–873, 2013.[11] R. Cohen and L. Katzir. The generalized maximum coverage problem. Infor-mation Processing Letters, 108(1):15–22, 2008.[12] A. Herschtal and B. Raskutti. Optimising area under the roc curve usinggradient descent. In ICML, 2004.[13] D. S. Hochbaum and A. Pathria. Analysis of the greedy approach in problemsof maximum k-coverage. Naval Research Logistics, 45(6):615–627, 1998.[14] Y. Hu, Y. Koren, and C. Volinsky. Collaborative filtering for implicit feedbackdatasets. In Proceedings of the 2008 Eighth IEEE International Conference onData Mining, ICDM ’08, pages 263–272, Washington, DC, USA, 2008. IEEEComputer Society.[15] S. B. Huffman and M. Hochster. How well does result relevance predict sessionsatisfaction? In Proceedings of the 30th annual international ACM SIGIRconference on Research and development in information retrieval, pages 567–574. ACM, 2007.[16] K. Ja¨rvelin and J. Keka¨la¨inen. Cumulated gain-based evaluation of ir tech-niques. ACM Trans. Inf. Syst., 20(4):422–446, 2002.[17] Y. Koren. Factorization meets the neighborhood: A multifaceted collaborativefiltering model. In KDD, pages 426–434, 2008.[18] Y. Koren. The bellkor solution to the netflix grand prize. Netflix prize docu-mentation, 81, 2009.[19] Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for rec-ommender systems. Computer, 42(8):30–37, 2009.[20] Q. Liu, Y. Ge, Z. Li, E. Chen, and H. Xiong. Personalized travel packagerecommendation. In Proceedings of the 2011 IEEE 11th International Confer-ence on Data Mining, ICDM ’11, pages 407–416, Washington, DC, USA, 2011.IEEE Computer Society.[21] Y. Liu, M. Xie, and L. V. Lakshmanan. Recommending user generated itemlists. In Proceedings of the 8th ACM Conference on Recommender systems,pages 185–192. ACM, 2014.49Bibliography[22] W. Pan and L. Chen. Cofiset: Collaborative filtering via learning pairwisepreferences over item-sets. In SDM, pages 180–188, 2013.[23] U. Paquet and N. Koenigstein. One-class collaborative filtering with randomgraphs. In WWW, pages 999–1008, 2013.[24] A. G. Parameswaran and H. Garcia-Molina. Recommendations with prereq-uisites. In RecSys, pages 353–356, 2009.[25] S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme. Bpr:Bayesian personalized ranking from implicit feedback. In Proceedings of theTwenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI ’09,pages 452–461, Arlington, Virginia, United States, 2009. AUAI Press.[26] S. B. Roy, S. Amer-Yahia, A. Chawla, G. Das, and C. Yu. Constructing andexploring composite items. In SIGMOD, pages 843–854, 2010.[27] Y. Shi, A. Karatzoglou, L. Baltrunas, M. Larson, N. Oliver, and A. Hanjalic.Climf: learning to maximize reciprocal rank with collaborative less-is-morefiltering. In RecSys, pages 139–146, 2012.[28] A. P. Singh and G. J. Gordon. Relational learning via collective matrix fac-torization. In KDD, pages 650–658, 2008.[29] M. Xie, L. V. Lakshmanan, and P. T. Wood. Breaking out of the box ofrecommendations: From items to packages. In RecSys, pages 151–158. ACM,2010.[30] W. Zhang, J. Wang, and W. Feng. Combining latent factor model with lo-cation features for event-based group recommendation. In Proceedings of the19th ACM SIGKDD international conference on Knowledge discovery and datamining, pages 910–918. ACM, 2013.50
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Recommending user-generated item lists
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Recommending user-generated item lists Liu, Yidan 2016
pdf
Page Metadata
Item Metadata
Title | Recommending user-generated item lists |
Creator |
Liu, Yidan |
Publisher | University of British Columbia |
Date Issued | 2016 |
Description | Nowadays, more and more websites are providing users with the functionality to create item lists. For example, in Yelp, users can create restaurant lists he/she likes. In Goodreads, users can create booklists consisting of books they like. These user-generated item lists complement the main functionality of the corresponding application and intuitively become an alternative way for users to browse and discover interesting items. Existing recommender systems are not designed for recommending user-generated item lists directly. In this work, we study properties of these user-generated item lists and propose two different models for recommending user-generated lists. We first model the problem as a recommendation problem and propose a Bayesian ranking model, called Lire. The proposed model takes into consideration users' previous interactions with both item lists and with individual items. Furthermore, we propose in Lire a novel way of weighting items within item lists based on both positions of items, and personalized list consumption pattern. Through extensive experiments on a real item list dataset from Goodreads, we demonstrate the effectiveness of our proposed Lire model. We then summarize the lessons learned from the recommendation model and modelled the problem as an optimization problem. We show that the list recommendation optimization can be reduced to Maximum k-Coverage Problem, which is an NP-hard problem. We derive three different problem variants and propose algorithms for each of them. We then conduct experiments to compare their results. Lessons learned and possible application scenarios are also discussed in the hope of helping us and more people improve the work. Furthermore, we propose several potential directions for future work. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2016-04-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0300050 |
URI | http://hdl.handle.net/2429/57720 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2016-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2016_may_yidan_liu.pdf [ 2.28MB ]
- Metadata
- JSON: 24-1.0300050.json
- JSON-LD: 24-1.0300050-ld.json
- RDF/XML (Pretty): 24-1.0300050-rdf.xml
- RDF/JSON: 24-1.0300050-rdf.json
- Turtle: 24-1.0300050-turtle.txt
- N-Triples: 24-1.0300050-rdf-ntriples.txt
- Original Record: 24-1.0300050-source.json
- Full Text
- 24-1.0300050-fulltext.txt
- Citation
- 24-1.0300050.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0300050/manifest