Machine Learning Anomaly Detection and Recommender Systems

This post covers two important applications: anomaly detection for identifying unusual patterns and recommender systems for personalized predictions.

Anomaly Detection

Problem Motivation

Goal: Identify data points that deviate significantly from "normal" patterns

Example: Aircraft Engine QA

• Features x: Heat, vibration, etc.
• Training set: {x⁽¹⁾, ..., x⁽ᵐ⁾} from normal engines
• New engine x_test: Is it anomalous?

Approach: Build probability model p(x)

• If p(x_test) < ε: Flag as anomalous
• If p(x_test) ≥ ε: Consider normal

Applications:

• Fraud detection: Unusual user behavior
• Manufacturing: Defective products
• Data center monitoring: Failing computers

Gaussian Distribution

If x ~ N(μ, σ²):
$p(x; \mu, \sigma^2) = \frac{1}{\sqrt{2\pi}\sigma}\exp\left(-\frac{(x-\mu)^2}{2\sigma^2}\right)$

Parameter Estimation:
$\mu = \frac{1}{m}\sum_{i=1}^{m}x^{(i)}$
$\sigma^2 = \frac{1}{m}\sum_{i=1}^{m}(x^{(i)} - \mu)^2$

Note: In ML, using m instead of m-1 in variance is standard (makes little difference for large m)

Anomaly Detection Algorithm

Assumptions: Features are independent and Gaussian

Model:
$p(x) = \prod{j=1}^{n}p(xj; \muj, \sigmaj^2)$

Steps:

1. Choose features xⱼ that might indicate anomalies

1. Fit parameters μⱼ, σⱼ² for each feature j
2. For new example x:

• Compute p(x) = ∏ⱼ p(xⱼ; μⱼ, σⱼ²)
• If p(x) < ε: anomaly

Evaluation and Development

Challenge: Evaluating unsupervised learning

Solution: Use small labeled dataset

Data Split Example:

• Training: 6,000 normal engines (unlabeled)
• CV: 2,000 normal + 10 anomalous (labeled)
• Test: 2,000 normal + 10 anomalous (labeled)

Evaluation Metrics:

• True positive, False positive, True negative, False negative
• Precision/Recall/F₁ score (better for skewed datasets than accuracy)

Parameter Selection:
Try different ε values on CV set, choose one maximizing F₁ score

Anomaly Detection vs. Supervised Learning

Anomaly Detection	Supervised Learning
Very few positive (anomalous) examples	Many positive and negative examples
Many types of anomalies, future ones may differ	Enough positive examples to learn pattern
Hard to learn from positive examples	Future positives similar to training set
Use for: Fraud, failures, defects	Use for: Spam, weather, tumors

Feature Engineering for Anomaly Detection

Key Success Factor: Good features!

1. Non-Gaussian Features

Transform to more Gaussian:

• log(x)
• log(x + c)
• √x
• x^(1/k) for k=2,3,...

2. Error Analysis

If algorithm misses anomalies:

• Examine what makes them anomalous
• Create new features capturing that pattern

Example - Data Center:

• CPU load alone: May not detect stuck process
• Network traffic alone: May not detect stuck process
• New feature: CPU load / network traffic
• High ratio → anomalous (CPU busy but no traffic)

Guideline: Features should have:

• Normal: Intermediate values
• Anomalous: Very large or small values

Multivariate Gaussian Distribution

Motivation: Capture feature correlations

Standard model limitation: Features assumed independent

Multivariate Gaussian:
$p(x; \mu, \Sigma) = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}\exp\left(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\right)$

Parameters:

• μ ∈ ℝⁿ: Mean vector
• Σ ∈ ℝⁿˣⁿ: Covariance matrix

Covariance Matrix Effects:

• Diagonal elements: Control variance of each feature
• Off-diagonal elements: Control correlations
• Can model elliptical contours at any angle

When to Use:

Standard Model	Multivariate
Manually create features for correlations	Automatically captures correlations
Computationally cheap, scales to large n	Computationally expensive
Works with small m	Requires m > n (typically m ≥ 10n)
Use this most often!	Use when correlations complex

Recommender Systems

Problem Formulation

Movie Rating Example:

• nu users, nm movies
• r(i,j) = 1 if user j rated movie i
• y⁽ⁱ'ʲ⁾ = rating given by user j to movie i

Goal: Predict ratings for unseen movies, recommend highest predicted

Content-Based Recommendations

Assumption: Have features for each movie

Example Features:

• x₁: Romance level (0-1)
• x₂: Action level (0-1)

Model: For each user j, learn parameters θ⁽ʲ⁾

Prediction: (θ⁽ʲ⁾)ᵀx⁽ⁱ⁾ for user j, movie i

Cost Function (for user j):
$\min{\theta^{(j)}} \frac{1}{2}\sum{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum{k=1}^{n}(\thetak^{(j)})^2$

For all users:
$\min{\theta^{(1)},...,\theta^{(nu)}} \frac{1}{2}\sum{j=1}^{nu}\sum{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum{j=1}^{nu}\sum{k=1}^{n}(\theta_k^{(j)})^2$

Gradient Descent: Same form as regularized linear regression

Collaborative Filtering

Key Insight: Can learn both features x AND parameters θ!

Reverse Problem: Given θ, can we learn x?
$\min{x^{(i)}} \frac{1}{2}\sum{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum{k=1}^{n}(xk^{(i)})^2$

Collaborative Filtering Algorithm:
Simultaneously optimize x AND θ:

$\min{x,\theta} J(x,\theta) = \frac{1}{2}\sum{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)} - y^{(i,j)})^2 + \frac{\lambda}{2}\sum{i=1}^{nm}\sum{k=1}^{n}(xk^{(i)})^2 + \frac{\lambda}{2}\sum{j=1}^{nu}\sum{k=1}^{n}(\thetak^{(j)})^2$

Steps:

1. Initialize x and θ to small random values (break symmetry!)
2. Minimize J using gradient descent (or advanced optimizer)
3. For user j, movie i: predict (θ⁽ʲ⁾)ᵀx⁽ⁱ⁾

Why "Collaborative"?
Users collaborate to help system learn better features!

Vectorization: Low Rank Matrix Factorization

Rating Matrix Y: nm × nu matrix

Prediction Matrix:
$\text{Predictions} = X\Theta^T$

Where:

• X: n_m × n matrix (each row is x⁽ⁱ⁾ᵀ)
• Θ: n_u × n matrix (each row is θ⁽ʲ⁾ᵀ)

Finding Similar Movies:
Movie i similar to movie k if ||x⁽ⁱ⁾ - x⁽ᵏ⁾|| is small

Applications:

• Show "users who liked this also liked..."
• Features learned automatically (may not be interpretable)

Mean Normalization

Problem: New user Eve with no ratings

• All r(i, Eve) = 0
• Learned θ⁽ᴱᵛᵉ⁾ = [0,0,...,0] (from regularization)
• Predicts 0 for all movies!

Solution: Normalize ratings by subtracting mean

Steps:

1. Compute μᵢ = average rating for movie i
2. Create Y' = Y - μ (subtract μᵢ from each row)
3. Learn x and θ on Y'
4. Predict: (θ⁽ʲ⁾)ᵀx⁽ⁱ⁾ + μᵢ

For new user: Predict μᵢ (movie's average rating)

---

Key Takeaways

Anomaly Detection:

1. Model normal behavior with Gaussian distribution
2. Use small labeled set for evaluation (F₁ score)
3. Feature engineering is critical
4. Transform non-Gaussian features
5. Create features that capture anomalous patterns
6. Standard model usually better than multivariate

Recommender Systems:

1. Content-based: Requires pre-defined features
2. Collaborative filtering: Learns features automatically
3. Low-rank matrix factorization for efficient computation
4. Mean normalization handles new users (cold start)
5. Can find similar items using learned features
6. Random initialization breaks symmetry

Both techniques handle sparse data and are widely used in industry applications!