J1Hard★ Core Essential · Industrial BedrockPart J · RecSys & Search Metrics
Factorization Machine (FM) O(kd) Implementation
Factorize pairwise feature interactions cleanly from O(k*d^2) down to linear O(k*d) complexity.
⏱️ Time:
O(B * D * K) 严格线性时间复杂度💾 Space:
O(D * K) 隐向量存储🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
class FactorizationMachine:
def __init__(self, num_features: int, k_factors: int = 8):
self.w0 = 0.0 # 全局偏置
self.w1 = np.zeros(num_features) # 一阶线性权重 (D,)
self.V =
def forward(self, x: np.ndarray) -> np.ndarray:
"""
x: (B, D) 样本特征矩阵
返回: (B,) 预测打分
"""
# 1. 零阶与一阶线性部分: w0 + x @ w1
linear_part = self.w0 + x @ self.w1 # (B,)
# 2. 二阶交叉部分
# term1: (sum(V_if * x_i))^2 -> (x @ V)^2 -> (B, K)
sum_vx = x @ self.V # (B, K)
term1 = sum_vx ** 2 # (B, K)
# term2: sum(V_if^2 * x_i^2) -> (x^2 @ V^2) -> (B, K)
term2 = (x ** 2) @ (self.V ** 2) # (B, K)
# 沿 K 轴求和并乘 0.5
interaction_part = 0.5 * np.sum(term1 - term2, axis=-1) # (B,)
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How does DeepFM combine Factorization Machines with deep neural networks?
💡
Core Mental Anchor / Mnemonic
Compute 0.5 * ((sum vx)^2 - sum(v^2 x^2)) to evaluate all pairwise interactions in O(kd).
📐 Mathematical Derivation & Core Formula
### Factorization of Pairwise Interactions
Pairwise polynomial regression costs parameters and struggles on sparse inputs. Factorization Machines (Rendle, 2010) factorize interaction weights with latent factors :
This collapses pairwise computation from down to linear .
Pairwise polynomial regression costs parameters and struggles on sparse inputs. Factorization Machines (Rendle, 2010) factorize interaction weights with latent factors :
This collapses pairwise computation from down to linear .
🔄 Tensor Dimensions & Shape Flow
x: (B, D) -> linear (B,) + 0.5 * sum_k((x @ V)^2 - (x^2 @ V^2)) -> out (B,)
🛡️ Numerical Stability & Pitfalls Checklist
- Initialize latent factors V with small variance (e.g., 0.01) to prevent initial gradient blow-up.
- Pass raw FM logits through Sigmoid for binary CTR click prediction.
💻 Reference Code Implementation
import numpy as np
class FactorizationMachine:
def __init__(self, num_features: int, k_factors: int = 8):
self.w0 = 0.0 # 全局偏置
self.w1 = np.zeros(num_features) # 一阶线性权重 (D,)
self.V = np.random.randn(num_features, k_factors) * 0.01 # 二阶隐向量 (D, K)
def forward(self, x: np.ndarray) -> np.ndarray:
"""
x: (B, D) 样本特征矩阵
返回: (B,) 预测打分
"""
# 1. 零阶与一阶线性部分: w0 + x @ w1
linear_part = self.w0 + x @ self.w1 # (B,)
# 2. 二阶交叉部分
# term1: (sum(V_if * x_i))^2 -> (x @ V)^2 -> (B, K)
sum_vx = x @ self.V # (B, K)
term1 = sum_vx ** 2 # (B, K)
# term2: sum(V_if^2 * x_i^2) -> (x^2 @ V^2) -> (B, K)
term2 = (x ** 2) @ (self.V ** 2) # (B, K)
# 沿 K 轴求和并乘 0.5
interaction_part = 0.5 * np.sum(term1 - term2, axis=-1) # (B,)
return linear_part + interaction_part
🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
import numpy as np
fm = FactorizationMachine(num_features=5, k_factors=4)
x = np.random.randn(2, 5)
out = fm.forward(x)
assert out.shape == (2,)
assert not np.isnan(out).any()
print("✓ FM 因子分解机自测通过")🎯 Core Follow-up Inquiries & Reference Answers
Q1:How does DeepFM combine Factorization Machines with deep neural networks?
DeepFM shares a common embedding table across an explicit FM branch (linear + 2nd-order pairwise terms) and a parallel MLP branch (capturing higher-order non-linear interactions), jointly summing both outputs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.