Million Song Dataset Recommendation Project Report

IV. M ETHODS AND A LGORITHMSFor all of our methods, we created sets of training, validation,and test data. For training data, we used unmodified userhistories and song metadata. For validation and test data, wetook the user histories and split it into two halves. The firsthalf was used to test our algorithms, while the second halfwas used to evaluate our results. If a song recommendationfor a user, predicted based on the history for that user inthe first half, existed in the second set of data, then thatrecommendation was considered relevant. This is the samemethod used to create training, validation, and test data in[1].A. Baseline algorithmsFor this project, we devised a few baseline algorithms againstwhich to compare our results. These methods provided asolid basis for evaluating the effectiveness of our later work.The first and simplest baseline method we implementedwas a straightforward popularity-based algorithm that justrecommends the most popular songs, as outlined in [1].1) K-Nearest Neighbors (KNN): We also used the kNearest Neighbor algorithm on the user history data. For eachtest user, we found the set of users who were closest, usingeach song as a feature and weighted according to the playcount for that song. From these results, we recommendedsongs (that the test user had not listened to) from the listeninghistory of the closest users. Closeness between users iscalculated by the minimum cosine distances between userssong histories.2) Matrix factorization: Singular Value Decompositions(SVD) are among the most successful recommender systemalgorithms. In its simplest form, SVD decomposes theuser-song play count matrix M into a latent feature spacethat relates users to songs (and vice-versa). This is usuallyachieved by factoring M according toM UT VWhere U Rk m is a low-rank representation of the musers, and V Rk n represents the n items. Once therepresentations U and V have been constructed, personalizedrecommendations are calculated for a user u by ranking eachitem i in descending order of the predicted feedback:wi UuT ViThe interpretation is that the users and songs can each berepresented by k-dimensional vectors, where each dimensioncorresponds to one of k topics like (rock music, artist nameetc). Each row of U , represents user u’s degree of interestin each topic. Each row of V represnts the relevance of thesong v to each topic.The computation of SVD in our case is non-trivial dueto the large number of missing values in M . The abovedecomposition is possible only if M is complete. SimonFunk has described a method to estimate SVD using onlythe known weights (playcount)[2]. The idea is to viewthe decomposition as a regression problem of finding theparameters of the vectors u and v, so as to minimize the errorbetween the known actual song weights and the predictions.Err(w) argmin(m,nX(V (wu,s ) V ) R)u U,s Swhere V (wu,s ) is the predicted value.As only few songs per user are known, an L2 norm regularizeris added to prevent overfitting:R γ( u 2 s 2 )Now, we use adaptive stochastic gradient descent to minimizethe above objective. We train the user and song vectors onefeature at a time. Here are the update equations for user andsong vector feature i:ui ui λ(u0 v 0 u · v)vi γuivi vi λ(u0 v 0 u · v)ui γviWhere u0 and v 0 represent current feature values for useru and song v. γ is the regularization parameter and γ isthe learning rate. For our experiments, we varied the latentfactors from k 1 to 20, and varied γ {10 3 , 10 4 } withλinit 10 2 .B. Main Algorithms1) K-Means clustering: One of the approaches used wasK-Means clustering. For all the users in the training data, wefound clusters of users based on their song histories. Fromthe clusters, we predicted for each user which cluster wasthe best fit according to proximity to its centroid. The mosthighly weighted songs in each cluster were selected as thesongs to recommend for that particular user. Although thisalgorithm will approximate the accuracy of KNN, it is a lotfaster and easier to tweak.2) User Based Recommendations: Generally, given a newuser, for which we want to obtain predictions, the set ofitems (in this case songs) to suggest is computed by lookingat similar users. This strategy is typically referred to as userbased recommendations. In user-based recommendations, thescoring function, on the basis of which the recommendationsare made, is computed assim(u, v) u·v11 u 2 · v 2which is just a cosine similarity between two users u and v.One common way of finding the cosine similarity is finding the

number of common items the users share between them. Thus,sim(u, v) #common items(u, v)11#items(u) 2 · #items(v) 2The strategy relies on the fact that each user belongs to a largergroup of similarly-behaving individuals. Consequently, itemsfrequently purchased (listened) by the various members of thegroup can be used to form the basis of the recommended items.The overall procedure is as follows: We try to find the weightof each item Ii in the system for the new user u by findingthe set of users V in the training set who have listened tothe item Ii and then summing the user similarity using thesimilarity function. Thus, weight for song Ii , wIi is,Xwli sim(u, v)v VFinally, all the items are sorted by their weights and top-Nare recommended to the user.The cosine similarity weighs each of the users equally whichis usually not the case. In fact, a user should be weightedless if he has shown interests to many variety of itemsbasing it on the knowledge that he does not discern betweensongs based on their quality of the item, or he just likesto explore items. Likewise, user is weighted more if helistens to very limited set of songs. Thus, we re-modeled thesimilarity measure by parametrizing it with this weighing rule.sim(u, v) #common items(u, v), α [0, 1)#items(u)α · #items(v)1 αWe also, added another parameterto sharpen thisnormalization. The effect of this exponentiation is this:when γ is high, smaller weights drop to zero while largerweights are (relatively) emphasized. Thus our item weightequation is now,Xwli (sim(u, v))γ , γ [0, 1)v V3) ItemBasedRecommendations:User-basedrecommendations identify a neighborhood of users that,in the past, have exhibited similar behaviors. An alternativeapproach is to build recommendation models that are basedon items. The key motivation behind this scheme is that auser will more likely purchase (or listen to) items that aresimilar to items he already purchased; thus, in this approach,the historical information is analyzed to identify relationshipsbetween the items so that the purchase of an item oftenleads to the purchase of another item. The algorithm firstdetermines the similarities between the various items, thenuses them to identify the items to be recommended. The keysteps in this approach are (i) the method used to compute thesimilarity between items and (ii) the method used to combinethe similarities and provide recommendations.During the model building phase, for each item i, the k mostsimilar items {i1 , i2 , ., ik } are computed and their corresponding similarities are stored. Now, for each user, that has listenedto a set U of items, we first identify the set V of candidateitems for recommendation by taking the union of the k mostsimilar items that are already in U . Then, for each item c C,we compute its similarity to the set U as the sum of similaritiesbetween all items u U and c, using only the k most similaritems of u. Finally, as in user-based recommendation, thecandidate items for recommendation are sorted and the top-Nitems are recommended.Xwc sim(u, c)u U,c CItem similarity: We used two approaches to calculate ItemItem similarity used in the Item based recommendations.(i) Without metadata: We used the similar method as in useruser similarity by finding the common users that are sharedby items i and j. Thus, similarity function is,sim(i, j) #common users(i, j)11#items(i) 2 · #items(j) 2(ii) With Metadata: the second approach involves using thesong metadata to compute a cosine similarity score betweentwo songs. The features used for each song in this calculationare artist name, tempo, loudness, energy, year the song wascomposed, the five most common lyrics in the song, and thefive most heavily weighted user tags for the song. All thefeatures, except tempo, loudness, and energy, were treated asbinary features.Lyrics were included as features in an attempt to takeadvantage of any possible semantic similarity between songs.For example, if a user enjoys love songs, then this approachcould exploit the fact that love songs may often sharelove-themed lyrics.4) Multi-faceted Prediction Algorithm: The multi-facetedprediction algorithm uses multiple algorithms to moreprecisely recommend songs for the user. We do this becausewe have observed that different methods work better underdifferent circumstances. By combining the different methodsand weighing a specific methods prediction more based onthe size of the test users listening history, we can maximizeour song recommendation systems precision.The multi-faceted prediction algorithm uses the trendsobserved in Figure 7 and Figure 8. For different sizes of thetest users song history, different methods of prediction giveoptimal recommendations. Specifically, when the test userssong history is small, predictions based on song similaritymetrics tend to perform better; when the test users songhistory is large, predictions based on similar user metrics tendto perform better. This has a direct application to the coldstart or near cold start situation, in which predictions based

on a test users song history tend to be noisy and inaccurate,since the similar users do not accurately represent the testuser. In these situations, making recommendations based onsong similarity is better. Thus, the multi-faceted predictionalgorithm aims to use this phenomenon to make the bestpredictions. Using our validation sets, we tuned the weightsto produce the optimal set of predictions.V. R ESULTSA. Precision MetricThe metric we used to determine the qual

Project Report Yi Li Cornell University yl2326@cornell.edu Rudhir Gupta Cornell University rg495@cornell.edu Yoshiyuki Nagasaki Cornell University yn253@cornell.edu Tianhe Zhang Cornell University tz249@cornell.edu Abstract—For our project, we decided to experiment, desig