algo-rec-mf
把互動矩陣拆成潛在因子的矩陣分解推薦
中文翻譯
---
name: "algo-rec-mf"
description: "實作矩陣分解，把使用者與項目的互動矩陣拆解成潛在因子表示。當使用者需要可擴展的協同過濾、潛在特徵探索、或推薦用的降維時使用，即使他們說的是「SVD 推薦」、「潛在因子」或「分解評分矩陣」也一樣。"
metadata:
category: "WP-36 推薦系統"
tags: ["recommendation", "matrix-factorization", "svd", "latent-factors"]
---
# 矩陣分解（Matrix Factorization）
## 概述
矩陣分解把使用者與項目的互動矩陣 R (m×n) 拆成兩個低秩矩陣：U (m×k) 和 V (n×k)，其中 k << min(m,n)。預測評分：r̂ᵢⱼ = uᵢ · vⱼ。訓練複雜度是 O(k × nnz × iterations)，nnz = 非零項的數量。
## 何時使用
**觸發條件：**
- 要把 CF 擴展到超越兩兩相似度的規模（數百萬使用者／項目）
- 要找出能解釋使用者與項目互動的潛在因子
- 要預測沒被觀察到的使用者與項目配對的評分
**何時不要用：**
- 互動資料極度稀疏時（填充率 < 0.1%），不足以學習
- 需要即時更新時（重新訓練很昂貴）
## 演算法
```
鐵律：秩 k 控制偏差與變異數的取捨
- k 太「低」：欠擬合，抓不到細緻的偏好（高偏差）
- k 太「高」：對雜訊過擬合，泛化差（高變異數）
- 典型的 k：20-200。用留出評分做交叉驗證來選。
- 一定要加正則化（λ）來防止過擬合。
```
### 階段 1：輸入驗證
載入稀疏的互動矩陣。切分成 train/validation/test。檢查最低密度。
**關卡：** 訓練矩陣中，每位使用者和每個項目都有足夠的項數。
### 階段 2：核心演算法
**ALS（交替最小平方法）：**
1. 隨機初始化 U、V（或用 SVD 暖啟動）
2. 固定 V，解 U：最小化 ||R - UV^T||² + λ(||U||² + ||V||²)
3. 固定 U，用同一個目標函數解 V
4. 交替進行，直到收斂（RMSE 變化 < ε）
**SGD 替代做法：** 對每個觀察到的評分，用梯度下降逐步更新 u_i、v_j。
### 階段 3：驗證
在留出的驗證集上計算 RMSE。和基準線（全域平均、使用者平均）比較。
**關卡：** 驗證集 RMSE 明顯低於基準線。
### 階段 4：輸出
回傳每位使用者的前 N 名預測，附上預測分數。
## 輸出格式
```json
{
"recommendations": [{"user_id": "u1", "items": [{"item_id": "i5", "predicted_rating": 4.3}]}],
"metadata": {"rank_k": 50, "regularization": 0.01, "iterations": 20, "train_rmse": 0.82, "val_rmse": 0.91}
}
```
## 範例
### 輸入輸出範例
**輸入：** 3×3 評分矩陣 R（0 = 未觀察到），k=1
```
R = [[5, 3, 0],
[4, 0, 2],
[0, 1, 1]]
```
**預期：** 用 k=1（一個潛在因子、λ=0.01、50 次迭代）跑 ALS 之後，近似的分解結果：
```
U ≈ [[2.24], [1.84], [0.53]]
V ≈ [[2.23], [1.06], [0.98]]
R_hat ≈ [[4.99, 2.37, 2.20],
[4.10, 1.95, 1.80],
[1.18, 0.56, 0.52]]
```
驗證：在觀察到的項目上，R_hat ≈ R（RMSE 在 0.2 以內）。U[0] >> U[2]，正確抓到使用者 0 給分比較高。
### 邊界情況
| 輸入 | 預期 | 原因 |
|-------|----------|-----|
| 只有 1 筆評分的使用者 | 對該使用者的預測很差 | 資料不足，學不出使用者因子 |
| 非常熱門的項目 | 預測接近平均 | 主導的第一個潛在因子抓到的是熱門度 |
| 所有評分 = 5 | 平凡的分解 | 沒有變異可以學習 |
## 常見陷阱
- **隱性資料需要不同的損失函數**：點擊／瀏覽（沒有顯性評分）要用帶信心權重的加權矩陣分解（Hu et al. 2008），不能用 RMSE。
- **冷啟動依然存在**：新使用者／項目在 R 裡沒有項目。MF 無法分解不存在的東西。要用輔助特徵或混合式做法。
- **負採樣**：隱性回饋必須抽樣負樣本（沒被觀察到 ≠ 不喜歡）。隨機負採樣可行，但有偏的採樣更好。
- **初始化很重要**：隨機初始化可能收斂到差的局部最佳解。以 SVD 暖啟動通常有幫助。
- **偏差項**：加上使用者偏差 bᵢ 和項目偏差 bⱼ：r̂ᵢⱼ = μ + bᵢ + bⱼ + uᵢ·vⱼ。這能捕捉系統性的評分傾向。
## 參考資料
- ALS 與 SGD 的比較，見 `references/optimization-comparison.md`
- 隱性回饋的矩陣分解，見 `references/implicit-mf.md`英文原文
---
name: "algo-rec-mf"
description: "Implement matrix factorization to decompose user-item interaction matrices into latent factor representations. Use this skill when the user needs scalable collaborative filtering, latent feature discovery, or dimensionality reduction for recommendation — even if they say 'SVD recommendations', 'latent factors', or 'factorize the rating matrix'."
metadata:
category: "WP-36 推薦系統"
tags: ["recommendation", "matrix-factorization", "svd", "latent-factors"]
---
# Matrix Factorization
## Overview
Matrix factorization decomposes the user-item interaction matrix R (m×n) into two low-rank matrices: U (m×k) and V (n×k), where k << min(m,n). Predicted rating: r̂ᵢⱼ = uᵢ · vⱼ. Trains in O(k × nnz × iterations) where nnz = non-zero entries.
## When to Use
**Trigger conditions:**
- Scaling CF beyond pairwise similarity (millions of users/items)
- Discovering latent factors that explain user-item interactions
- Predicting ratings for unobserved user-item pairs
**When NOT to use:**
- When interaction data is extremely sparse (< 0.1% fill) — insufficient for learning
- When you need real-time updates (retraining is expensive)
## Algorithm
```
IRON LAW: Rank k Controls Bias-Variance Trade-Off
- Too LOW k: underfits, misses nuanced preferences (high bias)
- Too HIGH k: overfits to noise, poor generalization (high variance)
- Typical k: 20-200. Select via cross-validation on held-out ratings.
- Always add regularization (λ) to prevent overfitting.
```
### Phase 1: Input Validation
Load sparse interaction matrix. Split into train/validation/test. Check minimum density.
**Gate:** Train matrix has sufficient entries per user and item.
### Phase 2: Core Algorithm
**ALS (Alternating Least Squares):**
1. Initialize U, V randomly (or with SVD warm-start)
2. Fix V, solve for U: minimize ||R - UV^T||² + λ(||U||² + ||V||²)
3. Fix U, solve for V using same objective
4. Alternate until convergence (RMSE change < ε)
**SGD alternative:** Update u_i, v_j incrementally for each observed rating using gradient descent.
### Phase 3: Verification
Compute RMSE on held-out validation set. Compare against baseline (global mean, user mean).
**Gate:** Validation RMSE significantly below baseline.
### Phase 4: Output
Return top-N predictions per user with predicted scores.
## Output Format
```json
{
"recommendations": [{"user_id": "u1", "items": [{"item_id": "i5", "predicted_rating": 4.3}]}],
"metadata": {"rank_k": 50, "regularization": 0.01, "iterations": 20, "train_rmse": 0.82, "val_rmse": 0.91}
}
```
## Examples
### Sample I/O
**Input:** 3×3 rating matrix R (0 = unobserved), k=1
```
R = [[5, 3, 0],
[4, 0, 2],
[0, 1, 1]]
```
**Expected:** After ALS with k=1 (one latent factor, λ=0.01, 50 iterations), approximate factorization:
```
U ≈ [[2.24], [1.84], [0.53]]
V ≈ [[2.23], [1.06], [0.98]]
R_hat ≈ [[4.99, 2.37, 2.20],
[4.10, 1.95, 1.80],
[1.18, 0.56, 0.52]]
```
Verify: R_hat ≈ R on observed entries (within 0.2 RMSE). U[0] >> U[2] correctly captures user 0's higher ratings.
### Edge Cases
| Input | Expected | Why |
|-------|----------|-----|
| User with 1 rating | Poor predictions for that user | Insufficient data to learn user factors |
| Highly popular item | Predicted near average | Dominant first latent factor captures popularity |
| All ratings = 5 | Trivial factorization | No variance to learn from |
## Gotchas
- **Implicit data needs different loss**: For clicks/views (no explicit ratings), use weighted matrix factorization (Hu et al. 2008) with confidence weighting, not RMSE.
- **Cold start remains**: New users/items have no entries in R. MF can't factorize what doesn't exist. Use side features or hybrid approaches.
- **Negative sampling**: For implicit feedback, you must sample negative examples (unobserved ≠ disliked). Random negative sampling works but biased sampling is better.
- **Initialization matters**: Random initialization can converge to poor local optima. SVD-based warm-start often helps.
- **Bias terms**: Add user bias bᵢ and item bias bⱼ: r̂ᵢⱼ = μ + bᵢ + bⱼ + uᵢ·vⱼ. This captures systematic rating tendencies.
## References
- For ALS vs SGD comparison, see `references/optimization-comparison.md`
- For implicit feedback matrix factorization, see `references/implicit-mf.md`