Scalable Analytics: chapter 5

Introduction to Recommender Systems and the Data Analysis Landscape

Recommender systems are situated within the broader context of information retrieval and data mining. They belong to a diverse set of applications and methodologies used to manage various data types:

• High Dimensional Data: Includes techniques such as Locality Sensitive Hashing (LSH), clustering, and dimensionality reduction.

• Graph Data: Involves PageRank, SimRank, community detection, and spam detection.

• Infinite Data/Streaming: Focuses on filtering data streams, web advertising, and queries on continuous streams.

• Machine Learning Integration: Uses Support Vector Machines (SVM), decision trees, Perceptron, and k-nearest neighbors (kNN).

• Applications: Recommender systems coexist with association rules, duplicate document detection, and scalable analytics.

The Shift from Scarcity to Abundance

Traditional retail models were constrained by physical scarcity. Shelf space in stores, airtime on TV networks, and screens in movie theaters are finite resources. However, the web has enabled near-zero-cost dissemination of information, leading to a shift from scarcity to abundance.

• The Long Tail Phenomenon: Popular items (the "head") are available in both traditional and digital formats. For example, Wal-Mart and Rhapsody may share a selection of approximately $39,000$ songs. However, thousands of other titles (the "tail") are only available digitally via platforms like Rhapsody, which can offer over $500,000$ titles. Popularity typically follows a power-law distribution where common titles have thousands of monthly plays, while niche titles have fewer but collectively represent a significant market share.

• Choice and Filtering: As the number of available products increases, consumers require better filters to find relevant items. Recommender systems serve as these filters (e.g., how the book "Into Thin Air" helped turn "Touching the Void" into a bestseller).

Types of Recommendations

Recommendation engines typically fall into three categories:

1. Editorial and Hand-Curated: Lists created by experts or staff, such as "Essential Items" or specific lists of favorites.

2. Simple Aggregates: These use basic popularity metrics, such as "Top 10," "Most Popular," or "Recent Uploads."

3. Tailored to Individual Users: These leverage user-specific data to provide personalized suggestions, as seen on Amazon, Netflix, and Last.fm.

Formal Model of Recommender Systems

The formal mathematical structure of a recommender system involves the following components:

• $X$: A set of customers.

• $S$: A set of items.

• Utility Function ($u$): A function $u: X \times S \rightarrow R$ that maps a customer-item pair to a rating.

• $R$: A set of ratings, which is a totally ordered set (e.g., integers $1-5$ or a range $[0, 1]$).

The Utility Matrix

The utility matrix provides a tabular view of users and their ratings for specific items (e.g., movies like Avatar, LOTR, Matrix, and Pirates).

• Key Problems:

  1. Gathering Known Ratings: Collecting data for the matrix.

  2. Extrapolating Unknown Ratings: Predicting values for the empty cells in the matrix, focusing on identifying high unknown ratings to suggest.

  3. Evaluating Extrapolation: Measuring the success or performance of the prediction methods.

Rating Data Collection

• Explicit Ratings: Users are asked directly to rate an item (e.g., star ratings).

• Implicit Ratings: Ratings are inferred from user actions, such as purchase history, browsing behavior, or search queries.

Core Challenges in Utility Extrapolation

• Sparsity: The utility matrix $U$ is typically very sparse because most users only rate a tiny fraction of the total items available.

• Cold Start: New items lack ratings, and new users have no rating history to base recommendations on.

Content-Based Recommender Systems

Content-based systems recommend items to a user ($x$) that are similar to items user $x$ has previously rated highly.

• Item Profiles: For each item, a profile is created consisting of a set or vector of features. Finding appropriate features is often the most difficult task.

• User Profiles: Created based on the items a user has liked. This can be a weighted average of the profiles of rated items. A variation involves weighting features by the difference between the user's rating for an item and the average rating for that item.

• Prediction Heuristic: To estimate the utility of item $i$ for user $x$, the cosine similarity between the user profile vector ($x$) and the item profile vector ($i$) is calculated:     $u(x, i) = \cos(x, i) = \frac{x \cdot i}{\|x\| \times \|i\|}$

Pros and Cons of Content-Based Approaches

• Pros: No dependency on data from other users; handles users with unique tastes; able to recommend new or unpopular items; provides transparency/explanation for recommendations.

• Cons: Hard to find appropriate features; difficult for new users; overspecialization (never recommends things outside the user's existing profile); ignores quality judgments from other users.

Collaborative Filtering

Collaborative filtering makes recommendations for user $x$ by finding a set ($N$) of "similar" users and basing suggestions on their ratings.

Similarity Measures for Users

Let $r_x$ be the vector of ratings for user $x$ and $r_y$ for user $y$.

• Jaccard Similarity: Measures overlap but ignores rating values.

• Cosine Similarity: Considers the angle between rating vectors.     $\text{sim}(x, y) = \cos(r_x, r_y) = \frac{r_x \cdot r_y}{\|r_x\| \times \|r_y\|}$

• Pearson Correlation Coefficient: Evaluates the linear correlation between users, accounting for their average ratings ($\bar{r}_x$ and $\bar{r}_y$). Let $S_{xy}$ be the set of items rated by both:     $\text{sim}(x, y) = \frac{\sum_{s \in S_{xy}} (r_{xs} - \bar{r}_x)(r_{ys} - \bar{r}_y)}{\sqrt{\sum_{s \in S_{xy}} (r_{xs} - \bar{r}_x)^2} \sqrt{\sum_{s \in S_{xy}} (r_{ys} - \bar{r}_y)^2}}$

Rating Prediction for User-User CF

Let $N$ be the set of $k$ users most similar to $x$ who have rated item $i$. Predictions for rating $r_{xi}$ can be made via:

• Simple average: $r_{xi} = \frac{1}{k} \sum_{y \in N} r_{yi}$

• Weighted average using similarity $s_{xy}$: $r_{xi} = \frac{\sum_{y \in N} s_{xy} \cdot r_{yi}}{\sum_{y \in N} s_{xy}}$

Item-Item Collaborative Filtering

Instead of looking for similar users, this approach looks for items similar to item $i$ based on ratings across all users.

• Prediction Heuristic: The rating $r_{xi}$ for user $x$ and item $i$ is estimated by taking a weighted average of user $x$'s ratings for items $j$ that are similar to $i$:     $r_{xi} = \frac{\sum_{j \in N(i;x)} s_{ij} \cdot r_{xj}}{\sum_{j \in N(i;x)} s_{ij}}$     where $N(i;x)$ is the set of items similar to $i$ that user $x$ has rated and $s_{ij}$ is the similarity between items $i$ and $j$.

• Comparison: In practice, item-item collaborative filtering often performs better than user-user filtering.

Pros and Cons of Collaborative Filtering

• Pros: Works for any kind of item (no feature extraction needed).

• Cons: Cold start problem (new users/items); sparsity of the matrix; first rater problem; popularity bias (tends to recommend what is already popular).

Evaluation Metrics for Prediction

Systems are evaluated by comparing predicted ratings ($\hat{r}_{xi}$) against known test ratings ($r_{xi}^*$):

• Root Mean Square Error (RMSE):     $\text{RMSE} = \sqrt{\frac{1}{N} \sum_{xi} (r_{xi} - r_{xi}^*)^2}$

• Precision at Top 10: Measures how many of the top 10 recommended items were actually liked.

• Rank Correlation: Measures the correctness of the ordering of items.

• Coverage: Percentage of items the system is able to provide recommendations for.

• Metric Limitations: Error measures can have a narrow focus on accuracy while ignoring diversity, context, and the reality that systems often only need to predict high ratings accurately.

Latent Factor Models

Latent factor models, such as Matrix Factorization or Singular Value Decomposition (SVD), aim to approximate the utility matrix $R$ as the product of two thinner matrices, $Q$ and $P^T$.

• Approximation: $R \approx Q \cdot P^T$

  • $Q$: Item-factor matrix (items are represented by factors like genre, target demographic, or tone).

  • $P$: User-factor matrix (users are represented by their preference for those factors).

• Heuristic Prediction: The predicted rating is the dot product of the item vector and user vector:     $\hat{r}_{xi} = q_i \cdot p_x = \sum_f q_{if} \cdot p_{xf}$

Singular Value Decomposition (SVD)

SVD decomposes a matrix $A$ into $U \Sigma V^T$. In recommendation contexts, $A=R, Q=U, P^T = \Sigma V^T$. SVD provides minimum reconstruction error ($SSE$): $\min_{U,V,\Sigma} \sum_{ij \in A} (A_{ij} - [U \Sigma V^T]_{ij})^2$ However, SVD is not defined when entries are missing. Specialized methods are used to find $P$ and $Q$ by minimizing the squared error only over known entries.

Optimization and Regularization

To prevent overfitting (where the model performs well on training data but poorly on test data), regularization is added to the objective function.

• Objective Function with Regularization:     $\min_{P,Q} \sum_{i,x \in \text{training}} (r_{xi} - q_i \cdot p_x)^2 + \lambda_1 \sum_x \|p_x\|^2 + \lambda_2 \sum_i \|q_i\|^2$     The parameters $\lambda_1, \lambda_2$ control the amount of regularization; higher values shrink parameters where data is scarce.

• Stochastic Gradient Descent (SGD): An iterative optimization algorithm used to find $P$ and $Q$.

  • Update rule for $Q$: $Q \leftarrow Q - \eta \cdot \nabla Q$

  • $-2(r_{xi} - q_i p_x)p_{xf}$ represents the error term, and $2\lambda_2 q_{if}$ represents the regularization term.

  • SGD updates parameters for each individual rating, leading to faster convergence compared to Batch Gradient Descent (BGD), which updates after seeing all ratings.

Integrating Biases and Temporal Dynamics

Advanced models improve accuracy by accounting for systematic biases:

• Global Mean ($\mu$): The average rating across all users and items.

• User Bias ($b_x$): Some users are naturally more critical or lenient (e.g., Star Wars fan vs. critical reviewer).

• Item Bias ($b_i$): Some items are inherently better or worse than the average (e.g., Star Wars having a higher average rating).

• Combined Model:     $\hat{r}_{xi} = \mu + b_x + b_i + q_i \cdot p_x$

• Temporal Biases: Users' preferences and item ratings can change over time (e.g., movie age influencing ratings).

The Netflix Prize Case Study

Netflix held a competition from 2006 to 2009 for a $10\%$ improvement over their CineMatch algorithm.

• Dataset: $100$ million ratings from $480,000$ users on $17,770$ movies.

• Performance Comparison (RMSE):

  • Global Average: $1.1296$

  • User Average: $1.0651$

  • Netflix Baseline: $0.9514$

  • Basic Collaborative Filtering: $0.94$

  • Latent Factors + Biases: $0.89$

  • Latent Factors + Biases + Time (Temporal Dynamics): $0.876$

  • Grand Prize Winning Entry: $0.8563$ ($10.09\%$ improvement reached by BellKor's Pragmatic Chaos).

• The Big Picture: The final solution involved blending approximately $500$ predictors and hundreds of different models.