W5 - Recommendation Systems.pdf

IS4242 INTELLIGENT SYSTEMS & TECHNIQUES L5 – Recommendation Systems Aditya Karanam © Copyright National Univer...

IS4242 INTELLIGENT SYSTEMS & TECHNIQUES L5 – Recommendation Systems Aditya Karanam © Copyright National University of Singapore. All Rights Reserved.  Announcements ▸ Programming Assignment – 1: Due Tonight (September 10, 11:59 PM) ▸ Programming Assignment – 2 ‣ Will be released later in the evening ‣ Due: October 6, 11:59 PM IS4242 (Aditya Karanam) 2  In this Class … ▸ Relaying and Connecting ‣ Recommendation Systems and their hidden side effects ▸ Collaborative Filtering ‣ Singular Value Decomposition IS4242 (Aditya Karanam) 3  The Bottleneck is in Demand ▸ Firms face a monumental challenge due to the emergence of IT ‣ Products are pouring out faster than the market’s ability to absorb them ‣ The bottleneck is not in the value chain, resource scarcity, or manufacturing ‣ The bottleneck is in demand: the ability of consumers to understand make sense of and buy the products Supply > Demand ▸ Solutions lie in the petabytes of information spewing out from the billions of consumer interactions, transactions, and other events ▸ We look at one prominent way in which this information can be used to create value for consumers: Relaying and Connecting IS4242 (Aditya Karanam) 4  Relaying and Connecting ▸ Refers to the scenario where firms learn from one customer and use that learning to help another customer ‣ A satellite with a large footprint: relay information from one location to other parts of the world, creating value for the receiver and perhaps also for the sender ▸ Firms act as a connector between two parties (E.g., buyers and sellers) that can benefit from knowing each other ▸ Simple idea but requires considerable skill to build such information arbitrage systematically ‣ Large and dispersed organizations are the best placed groups to implement this idea ‣ Any business with more than one customer or supplier can create value through this strategy information arbitrage = utilizing data to create value for consumers IS4242 (Aditya Karanam) 5  Relaying and Connecting: Big Picture ▸ Relaying is possible due to the Big Picture advantage of the firm ‣ Firms have a view of the forest where customers can only see the trees ‣ With information across all customers, firms see ideas, products, or solutions that have been implemented or tried ‣ These solutions could be very valuable to customers in other locations, industries, or contexts ▸ Customers, however, have no means of accessing this knowledge or a view of the entire playing field ‣ They would have to reinvent the wheel to find a solution IS4242 (Aditya Karanam) 6  How Do You Relay Information? ▸ Face of it: Bringing information to a customer about what happened elsewhere seems simple enough ▸ But capturing value and building competitive advantage through relaying is difficult ‣ Requires more than a one-time transfer of information to build trust ‣ Customers value firms for their accurate and consistent relaying capabilities not just instances of relaying IS4242 (Aditya Karanam) 7  How Do You Relay Information? ▸ Requires firms to build systems to collect and collate information from a vast network, and turn that knowledge into viable customer solutions ▸ Relaying functions must be institutionalized, rather than left to the initiative of front-line (E.g., customer service) employees ▸ Such Information Systems are prominent in information-intensive online businesses with large numbers of customers ‣ Amazon, Netflix, TikTok, YouTube, Spotify, etc. IS4242 (Aditya Karanam) 8  Value through Relaying and Connecting: Amazon ▸ Amazon.com started as a bookstore ▸ Over time acquired several dedicated retailers in the online shopping space including Zappos (shoes), Diapers.com (baby products) ▸ In a decade and a half, Amazon.com has grown from zero to more than $65 billion in annual sales ‣ Revolutionized retailing challenging the world’s largest general merchandisers (Walmart) IS4242 (Aditya Karanam) 9  Value through Relaying and Connecting: Amazon ▸ How was an online store - Amazon.com, operating in an experience economy neutralize challenges from brick-and-mortar booksellers? ‣ Offline bookstores offer hot coffee, leather reading chairs, meet-the-author events, immediate product delivery, reading club meetings, etc. ▸ How did a bookstore grow big enough to buy the other category-focused retailers? ▸ Why didn’t online retailers come out of established offline general merchandise businesses? IS4242 (Aditya Karanam) 10  Value through Relaying and Connecting: Amazon ▸ Customers get much more than books at Amazon.com ‣ Additional value resides in relayed experience and connections with other readers and consumers who provide valuable information ‣ Amazon.com uses this information and builds individualized best-seller lists ▸ Readers can find out about other similar books and the books that are purchased together ‣ Books the customer might not otherwise have heard of or considered ▸ Readers don’t just learn what others are reading, they get an answer to a more personalized question: “What are others like me reading?” ‣ For repeat customers, based on their purchasing and browsing history, Amazon.com provides highly accurate and targeted recommendations IS4242 (Aditya Karanam) 11  Platforms for Relaying and Connecting ▸ Relaying makes the company occupy the central position in a network of customers and producers ‣ All information flows first to the firm and then from this central node to other nodes in the network ▸ The company acts as a platform connecting different parties that would not otherwise connect ‣ This makes the firm indispensable IS4242 (Aditya Karanam) 12  Platforms for Relaying and Connecting: Amazon ▸ Amazon.com not only connects readers but also connects thousands of store owners with consumers who visit Amazon ‣ Some of these store owners (especially, small stores) and consumers might never otherwise have connected ‣ Consumers are comfortable buying from unknown stores as they are on Amazon ▸ Amazon extracts rent from stores to gain access to its consumers, payment services, logistics, etc. ‣ Why isn’t Amazon charging consumers to have access to millions of stores? ▸ Similar strategies for other products, which made it buy other dedicated retailers ‣ Similar strategies are present in the iTunes store, App Store, etc. IS4242 (Aditya Karanam) 13  Competitive Advantage ▸ The relaying and connecting is not easy for competitors to replicate ▸ Once these functions attract a critical mass of users, they become almost insurmountable barriers to entry ▸ What do Amazon competitors need to deliver similar information to consumers with such accuracy and reliability? ‣ Hundreds of millions of customers and their experiences! ▸ Amazon’s competitive advantage resides literally with its customers! ‣ Amazon.com is customer-obsessed! IS4242 (Aditya Karanam) 14  Competitive Advantage: Amazon ▸ This is working rather well ‣ Amazon revenues were just over $10 billion in 2006 and have risen fourfold around the time of deepest recessions in the US ▸ Customers are happy too ‣ The company has consistently been one of the top two online retailers in Foresee’s annual retail satisfaction index since 2005 ‣ Another front-runner is Netflix! IS4242 (Aditya Karanam) 15  Relaying and Connecting: Summary ▸ Most valuable when customers are unable to learn from each other or from accessing other parts of the market ‣ Firms can help bridge the information gap ▸ Customers find this valuable ‣ Reduces customer’s cost of search, evaluation, comparison, and decision making ‣ Reduces customer’s risks of choosing the wrong product ▸ How do firms operationalize relaying and connecting strategies? ‣ Recommendation Systems IS4242 (Aditya Karanam) 16  Recommendation Systems: Amazon ▸ General merchandisers operated with the mindset of the offline world ‣ Sell more of the stuff they were already selling ▸ Amazon was building information channels (recommendation engines) to relay information ‣ Applicable to all products – shoes, baby products, furniture, etc. ▸ Recommendation systems bring a unique competitive advantage ‣ More customers in the platform, more informative the reviews, more accurate its recommendations, more value it adds to customers, and more business it does at a lower cost ‣ Barriers to entry escalate with a larger installed base of customers! ‣ Less likely that competitors can replicate these advantages IS4242 (Aditya Karanam) 17  Not Just Amazon ▸ Recommendation systems brought significance to the e-commerce industry! ▸ Netflix: 75% of the content watched by its subscribers was suggested by its recommendation system ‣ Netflix offered $ 1 Million to develop a collaborative filtering algorithm for its platform ‣ Popularized the idea of crowd-sourced idea generation (Kaggle cashed it) ▸ At Spotify, users listened to 2.3 billion hours of music from ‘discover weekly’ recommendations ▸ TikTok introduced personalized recommended feeds for users ‣ On average a user spends ~50 minutes on this feed ‣ YouTube, Instagram and others copied this feature IS4242 (Aditya Karanam) 18  Side Effects of Recommendation Systems ▸ Recommendations do more than just reflect consumer preferences – they shape them! ▸ Experiment with 169 consumers of music, where participants listened to songs and provided their willingness to pay for each song ‣ Each song was presented with manipulated recommendation system ratings (which participants did not know) ‣ Despite the manipulation, a 1-star increase in the rating created an average 12- 17% increase in the willingness to pay ▸ Regardless of the likelihood of actual fit, recommendation systems can decrease willingness to pay for some items and increase it for others ‣ Evokes unethical behavior of inflating recommendations artificially IS4242 (Aditya Karanam) 19  Side Effects of Recommendation Systems ▸ The advent of recommendation systems may leave us questioning our own taste ‣ Don’t need a system to tell how much we enjoyed a song we just heard ‣ We move from asking ourselves, Do I like this? ⇒ Should I like this? ▸ More important, these systems may create information bubbles in social media ‣ E.g., A republican voter may only get the positive news on Trump and only get the negative news on Biden IS4242 (Aditya Karanam) 20  Recommendation Systems © Copyright National University of Singapore. All Rights Reserved. 21  Recommendation Systems ▸ Content Based Recommendations ▸ Collaborative Filtering IS4242 (Aditya Karanam) 22  Content Based Recommendation System ▸ Users and items are associated with feature-based descriptions ‣ Textual description of items ‣ Ex: Summary of the book, title, etc. ‣ Explicit interests provided by users in a profile ‣ Ex: Book genres, etc. ▸ Obtain the similarity between users’ interests and items’ descriptions to make recommendations Cold start problem can be partially mitigated using Content based recommendation system IS4242 (Aditya Karanam) 23  Collaborative Filtering ▸ Leverages user preferences in the form of ratings or buying behaviour in a collaborative way, for the benefit of all users ‣ Ratings, purchases, browsing, etc. represent preference or utility ▸ Utility matrix is used for providing recommendations ‣ If a relevant item is determined based on similarity between items ‣ Item-based collaborative filtering ‣ If a relevant item is determined based on user similarity ‣ User-based collaborative filtering IS4242 (Aditya Karanam) 24  Collaborative Filtering IS4242 (Aditya Karanam) 25  Collaborative Filtering IS4242 (Aditya Karanam) 26  Application: Book Recommendation System ▸ Data on books and user ratings ▸ Objective: Build a recommendation system that provides the next book to be read by the consumer ▸ Collaborative Filtering Algorithm IS4242 (Aditya Karanam) 27  Collaborative Filtering ▸ Given historical user preferences, predict (unknown) preference of a user Item1 Item2 … ItemM User1 1 0 … 1 User2 0 2 … 0 … … … … … Usern 1 ? … ? ▸ Can we just consider this as a missing value problem and use K-Nearest Neighbors? ‣ At higher dimensions, pairwise distances are concentrated at a higher value IS4242 (Aditya Karanam) 28  Singular Value Decomposition (SVD) ▸ SVD is more general than PCA ‣ PCA: Obtain low-dimensional representation of rows of data matrix ‣ SVD: Generalizes this idea to both the dimensions ▸ Decomposition is a Factorisation of the Matrix ‣ Generalizes factorization of scalars (e.g., 15 = 5 x 3) ‣ Expresses a given matrix as a product of two (or more) factor matrices ‣ 𝐴 = 𝐵𝐶 Singular value decomposition (SVD) is the factorization of a matrix into three matrices: two orthogonal matrices, - which contain the left and right singular vectors - and a diagonal matrix, which contains the singular values (non-negative scalars) Vectors are orthogonal if the dot product between those 2 are equal to ZERO A matrix is orthogonal if its own transpose multiplied with itself is equal to an identity matrix? A(inverse) == A(Transpose) then it's an orthogonal matrix IS4242 (Aditya Karanam) 29  SVD ▸ Singular value decomposition factorizes any matrix, A ∈ ℝ𝑚×𝑛 as: A = 𝑈Σ𝑉 𝑇 ▸ 𝑈 ∈ ℝ𝑚×𝑚 and 𝑉 ∈ ℝ𝑛×𝑛 are orthonormal matrices ‣ Columns of U or rows of 𝑉 𝑇 are orthogonal, and they are unit vectors ‣ Vectors are orthogonal to each other if their dot product is zero ‣ A vector is a unit vector if its L2-norm is 1 ‣ Orthonormal matrix has the property that its transpose is its inverse. ‣ E.g., 𝑈𝑈 𝑇 = 𝑈 𝑇 𝑈 = 𝐼 Orthogonal matrices are matrices that although rotated, will still preserve its value and magnitude. It's great for computer graphics, computer vision and data science. This is because it can preserve values after transformation of data IS4242 (Aditya Karanam) 30  SVD ▸ Singular value decomposition factorizes any matrix, A ∈ ℝ𝑚×𝑛 as: A = 𝑈Σ𝑉 𝑇 ▸ Σ is a diagonal matrix with values 𝜎1 , 𝜎2, 𝜎3, … , 𝜎min 𝑚,𝑛 ≥ 0 in its diagonal ‣ These values are the square root of the eigenvalues of matrix 𝐴𝐴𝑇 ‣ These are called singular values of matrix A ▸ SVD of a data matrix A can give us the principal components ordered by the eigenvalues ‣ Singular values are presented in a decreasing order in the matrix Diagonal matrix - Diagonal matrix are also called as singular values of matrix A IS4242 (Aditya Karanam) 31 - Diagonal matrix values are square roots of eigenvalues of matrix A(A_T)  SVD: Geometric Interpretation ▸ U and V are new sets of axes in the m and n dimensional space ▸ Singular value 𝜎𝑖 amplifies the vectors in the 𝑣𝑖 axis in the n-dimensional space and maps them into the 𝑢𝑖 axis in the m-dimensional space SVD Is used in PCA - SVD is used to select the principal components ordered by their eigenvalues (decreasing order) - SVD gives the most important direction of which component has the highest variance IS4242 (Aditya Karanam) 32  SVD: Geometric Interpretation SVD identifies the most important directions (directions of the highest variance) in the n-dimensional and m-dimensional spaces and their relative importance IS4242 (Aditya Karanam) 33  SVD ▸ Efficient algorithms exist to compute SVD ▸ PCA is usually done by computing SVD ‣ In sci-kit learn as well ▸ SVD provides low-dimensional representations of both rows and columns ‣ a.k.a. Latent representations ‣ Varied Applications: Latent Semantic Analysis, Image Compression, etc. Complete SVD practice TONIGHT WED IS4242 (Aditya Karanam) 34  Truncated SVD ▸ Truncated SVD takes the first k columns of U and V and the main k-by-k sub matrix of Σ 𝐴𝑘 ≈ 𝑈𝑘 Σ𝑘 𝑉𝑘𝑇 ▸ Eliminating the lower variance components can also help in noise removal IS4242 (Aditya Karanam) 35  Factor Interpretations A = 𝑈Σ𝑉 𝑇 ▸ If two rows have similar values in a column of 𝑉 , corresponding columns (features) in A are similar ▸ If two rows have similar values a column of U, corresponding rows (observations) in A are similar IS4242 (Aditya Karanam) 36  Collaborative Filtering ▸ Large sparse ratings matrix R: ▸ SVD on R: 𝑅 ≈ 𝑈𝑘 Σ𝑘 𝑉𝑘𝑇 Latent factors refer to hidden preferences that can be ‣ 𝐹𝑢𝑠𝑒𝑟 = 𝑈𝑘 Σ𝑘 = 𝑃𝑘 uncovered through analysis in recommendation systems. ‣ 𝐹𝑖𝑡𝑒𝑚 = 𝑉𝑘𝑇 = 𝑄𝑘𝑇 ▸ 𝑅 ≈ 𝑃𝑘 𝑄𝑘𝑇 ‣ P: Latent representations of users ‣ Q: Latent representations of items IS4242 (Aditya Karanam) 37  Collaborative Filtering: Latent Factors ▸ 𝑅𝑖𝑗 = σ𝑘𝑠=1 𝑃𝑖𝑠 𝑄𝑠𝑗 = σ𝑘𝑠=1 𝐴𝑓𝑓𝑖𝑛𝑖𝑡𝑦 𝑜𝑓 𝑢𝑠𝑒𝑟 𝑖 𝑡𝑜 𝑐𝑜𝑛𝑐𝑒𝑝𝑡 𝑠 ∗ (𝐴𝑓𝑓𝑖𝑛𝑖𝑡𝑦 𝑜𝑓 𝑖𝑡𝑒𝑚 𝑗 𝑡𝑜 𝑐𝑜𝑛𝑐𝑒𝑝𝑡 𝑠) ▸ What do latent factors/concepts mean? ‣ They characterise both users and items ‣ Sometimes they have meaningful interpretations, but not always IS4242 (Aditya Karanam) 38  Collaborative Filtering: Latent Factors ▸ K-Nearest Neighbours algorithm can be used in lower dimensions to find ‘neighbors’ ‣ Similar users with respect to their item-ratings ‣ Similar items with respect to their user-ratings IS4242 (Aditya Karanam) 39  Matrix Completion ▸ Once P and Q are learnt, they can be multiplied to ‘complete’ the ratings 𝑇 matrix: 𝑅 ≈ 𝑃𝑚×𝑘 𝑄𝑘×𝑛 ‣ For a given user the completed row can be ordered, and the highest valued items can be recommended ▸ What we have not covered: how can P and Q be learnt when there are missing values in R? ‣ Essentially reconstruct P and Q using only known values ‣ This was among the top 3 finalists in Netflix Prize ‣ Details: http://nicolas-hug.com/blog/matrix_facto_3 IS4242 (Aditya Karanam) 40  References ▸ Adomavicius et al. 2018 Effects of Online Recommendations on Consumers’ Willingness to Pay, Information Systems Research ▸ Understanding Complex Datasets: Data Mining with Matrix Decompositions, by David Skillicorn ‣ Chapters 2.1-2.3, 3.1-3.3 ▸ Data Mining: The Textbook, by Charu Aggarwal ‣ Chapter 2.4.3 IS4242 (Aditya Karanam) 41  Thank You © Copyright National University of Singapore. All Rights Reserved.