Problem Formulation

Every second, millions of users across the globe interact with systems that predict what they want before they know it themselves. When you open Netflix, scroll through Spotify, browse Amazon, or swipe through content, sophisticated algorithms are working behind the scenes to surface the most relevant items from catalogs containing millions of possibilities.

This isn't magic—it's the culmination of decades of research in recommendation systems (RecSys), a specialized branch of machine learning that addresses one of the most commercially significant prediction problems in the digital age: given a user's history and context, which items should we show them next?

At its core, a recommendation system is a specialized information filtering system that predicts preferences or relevance scores for items that users have not yet interacted with. The goal is to reduce information overload by surfacing the most relevant subset of items from a potentially massive catalog.

Formal Definition:

A recommendation system is a function that maps a (user, item) pair to a predicted utility or relevance score:

$$f: U \times I \rightarrow \mathbb{R}$$

Where:

• U is the set of all users in the system
• I is the set of all items that can be recommended
• The output is a real-valued score indicating predicted relevance or preference

This seemingly simple formulation conceals enormous complexity. The challenge lies in estimating this function accurately when we typically have observed outcomes for only a tiny fraction of all possible (user, item) pairs.

The Information Retrieval Perspective:

Recommendation systems can be viewed as a specialized form of information retrieval where the query is implicit—derived from user behavior and context rather than explicit user input. Unlike traditional search where users articulate what they want, recommenders must infer intent from patterns in historical behavior.

Key Distinctions:

The foundational data structure of recommendation systems is the user-item interaction matrix (also called the rating matrix or feedback matrix). This matrix provides a unified representation of all known user-item relationships.

Matrix Structure:

Let R be an $m \times n$ matrix where:

• $m$ = number of users
• $n$ = number of items
• $R_{ui}$ = the interaction value (rating, click, purchase) between user $u$ and item $i$

$$R = \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \ r_{21} & r_{22} & \cdots & r_{2n} \ \vdots & \vdots & \ddots & \vdots \ r_{m1} & r_{m2} & \cdots & r_{mn} \end{bmatrix}$$

Most entries in this matrix are missing (unobserved). The core task of recommendation is to predict the unobserved entries—to fill in the blanks with estimated preference scores.

Properties of the Interaction Matrix:

1. Extreme Sparsity: In real systems, typically 95-99.9% of entries are missing
2. Non-Random Missingness: Missing data is not random—users choose what to interact with (selection bias)
3. Heterogeneous Scales: Different users may use rating scales differently
4. Temporal Dynamics: Preferences evolve over time; older interactions may be less relevant
5. Implicit vs Explicit Entries: The values may represent explicit ratings or implicit signals (discussed in next page)

Matrix Completion Perspective:

From a mathematical standpoint, recommendation can be framed as a matrix completion problem: given a partially observed matrix, recover the complete matrix. This becomes tractable under assumptions like low-rank structure—that user preferences and item characteristics can be described by a small number of latent factors.

Recommendation problems can be formulated in several distinct ways, each leading to different algorithmic approaches and evaluation metrics. Understanding these paradigms is essential for choosing the right approach for your application.

1. Rating Prediction

The classic formulation: predict the numerical rating a user would assign to an item.

$$\hat{r}_{ui} = f(u, i; \Theta)$$

Objective: Minimize prediction error (e.g., RMSE) on observed ratings

Use Case: Systems where explicit ratings are the primary signal (e.g., IMDb, academic paper reviews)

Limitation: Optimizing for rating prediction doesn't necessarily produce good rankings—a model could achieve low RMSE while poorly ordering items by preference.

2. Top-N Ranking

Predict which N items a user is most likely to interact with or prefer.

$$\text{Recommend}(u) = \text{TopN}_{i \in I} ; s(u, i)$$

Objective: Maximize ranking quality (e.g., NDCG, MAP, Recall@K)

Use Case: Most real-world applications where we show a list of recommendations

Key Insight: Users don't see predicted ratings—they see ordered lists. Ranking quality matters more than rating accuracy.

Let's formalize the recommendation problem with proper mathematical notation. This precision is essential for understanding algorithms and their theoretical properties.

Notation:

• $U = {u_1, u_2, ..., u_m}$: Set of users
• $I = {i_1, i_2, ..., i_n}$: Set of items
• $R \in \mathbb{R}^{m \times n}$: Interaction matrix
• $\Omega \subseteq U \times I$: Set of observed (user, item) pairs
• $r_{ui}$: True value for $(u, i) \in \Omega$
• $\hat{r}_{ui}$: Predicted value for any $(u, i)$

Rating Prediction Optimization:

$$\min_{\Theta} \sum_{(u,i) \in \Omega} \mathcal{L}(r_{ui}, \hat{r}_{ui}; \Theta) + \lambda \cdot \text{Reg}(\Theta)$$

Where:

• $\mathcal{L}$ is a loss function (squared error, cross-entropy, etc.)
• $\Theta$ represents model parameters
• $\text{Reg}(\Theta)$ is a regularization term to prevent overfitting
• $\lambda$ controls regularization strength

Ranking Formulation via Pointwise/Pairwise/Listwise:

For ranking tasks, there are three major approaches to learning:

Pointwise: Treat each item independently $$\mathcal{L}{\text{pointwise}} = \sum{(u,i) \in \Omega} (y_{ui} - \hat{y}_{ui})^2$$

Pairwise: Learn to correctly order pairs of items $$\mathcal{L}{\text{pairwise}} = \sum{(u,i,j) \in D_s} -\log \sigma(\hat{r}{ui} - \hat{r}{uj})$$

Where $D_s$ contains tuples (user, positive item, negative item)

Listwise: Optimize the entire ranking directly $$\mathcal{L}{\text{listwise}} = -\sum{u} \text{NDCG}(\hat{\pi}_u, \pi^*_u)$$

Where $\pi$ represents the ranking permutation.

All recommendation systems—regardless of their sophistication—operate by leveraging information from three fundamental sources. Understanding these pillars helps you analyze any system and identify opportunities for improvement.

Pillar 1: Collaborative Information

Exploits patterns across users and items. "Users who liked X also liked Y" or "Similar users have similar preferences."

• Requires no domain knowledge or content features
• Discovers latent patterns humans might miss
• Fails for new users/items with no interaction history
• Suffers from popularity bias (popular items get more data)

Pillar 2: Content Information

Leverages item attributes and user profiles. "This movie is an action thriller directed by Christopher Nolan" → users who like similar attributes may like this.

• Works for new items with known features
• Provides explainable recommendations
• Limited by feature engineering quality
• Cannot discover serendipitous recommendations beyond content similarity

Pillar 3: Contextual Information

Incorporates situational factors: time, location, device, session behavior, etc.

• Same user may want different things at different times
• Captures temporal dynamics (weekday vs weekend preferences)
• Enables real-time personalization
• Increases model complexity and data requirements

Problem formulation isn't purely theoretical—it must account for the operational realities of production systems. Recommendations must be generated at massive scale with strict latency requirements.

The Two-Stage Architecture:

Most production recommender systems employ a two-stage architecture:

Stage 1: Candidate Generation (Retrieval)

• Goal: Narrow down millions of items to hundreds of candidates
• Latency budget: milliseconds
• Approach: Approximate nearest neighbor (ANN), inverted indices, embedding similarity
• Priority: High recall (don't miss good items)

Stage 2: Ranking

• Goal: Precisely order the candidates
• Latency budget: tens of milliseconds
• Approach: Complex ML models (deep networks, gradient boosting)
• Priority: High precision (put best items first)

This separation allows using simpler, faster models for retrieval while reserving computational budget for sophisticated ranking of the narrowed candidate set.

The mathematical formulation must ultimately serve business objectives. This is where recommendation science meets business reality—and they don't always align neatly.

Common Business Objectives:

1. Engagement Maximization

   • Objective: Maximize clicks, watch time, session length
   • Risk: May promote addictive, sensational, or low-quality content
   • Metric: CTR, time spent, sessions per user

2. Conversion Optimization

   • Objective: Maximize purchases, subscriptions, conversions
   • Risk: May over-promote items users would buy anyway
   • Metric: Conversion rate, GMV, ARPU

3. User Satisfaction

   • Objective: Maximize long-term user satisfaction and retention
   • Challenge: Harder to measure than clicks
   • Metric: Net Promoter Score, churn rate, explicit satisfaction surveys

4. Diversity and Discovery

   • Objective: Help users discover new interests
   • Trade-off: Short-term engagement may drop
   • Metric: Category diversity, novel item interaction rate

5. Supplier/Content Creator Health

   • Objective: Fair distribution of recommendations across sellers/creators
   • Risk: Winner-take-all dynamics harm ecosystem
   • Metric: Gini coefficient of recommendation distribution

Multi-Objective Formulation:

Real systems optimize for multiple objectives simultaneously:

$$\max_{\pi} \left[ \alpha \cdot \text{Relevance}(\pi) + \beta \cdot \text{Diversity}(\pi) + \gamma \cdot \text{Freshness}(\pi) - \delta \cdot \text{BiasViolation}(\pi) \right]$$

Where $\pi$ is the recommendation policy and $\alpha, \beta, \gamma, \delta$ are weights reflecting business priorities.

Pareto Optimization: Often there's no single solution that maximizes all objectives. We seek Pareto-optimal solutions where improving one objective requires sacrificing another.