J1Hard★ Core Essential · Industrial BedrockPart J · RecSys & Search Metrics

Factorization Machine (FM) O(kd) Implementation

⚡Flashcard Drill➔

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?
Next: AUC-ROC Calculation with Rank Ties Handling →
💡

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

∑i=1d∑j=i+1d⟨vi,vj⟩xixj=12∑f=1k[(∑i=1dvi,fxi)2−∑i=1dvi,f2xi2]\sum_{i=1}^d \sum_{j=i+1}^d \langle v_i, v_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^k \left[ \left(\sum_{i=1}^d v_{i, f} x_i\right)^2 - \sum_{i=1}^d v_{i, f}^2 x_i^2 \right]
### O(kd)O(kd) Factorization of Pairwise Interactions
Pairwise polynomial regression costs O(d2)O(d^2) parameters and struggles on sparse inputs. Factorization Machines (Rendle, 2010) factorize interaction weights wij=⟨vi,vj⟩w_{ij} = \langle v_i, v_j \rangle with latent factors vi∈Rkv_i \in \mathbb{R}^k:
∑i=1d∑j=i+1d⟨vi,vj⟩xixj=12∑f=1k[(∑i=1dvi,fxi)2−∑i=1dvi,f2xi2]\sum_{i=1}^d \sum_{j=i+1}^d \langle v_i, v_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^k \left[ \left(\sum_{i=1}^d v_{i,f} x_i\right)^2 - \sum_{i=1}^d v_{i,f}^2 x_i^2 \right]
This collapses pairwise computation from O(kd2)O(k d^2) down to linear O(kd)O(k d).

🔄 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.
🎯 Drill This Card Now➔
← Prev: AWQ Activation-Aware Group-Wise INT4 QuantizationBack to Part J & All 105Next: AUC-ROC Calculation with Rank Ties Handling →