因子分解机（Factorization Machines）算法的原理与计算过程 题目描述 因子分解机（Factorization Machines, FM）是一种结合支持向量机（SVM）和矩阵分解思想的监督学习算法，由Steffen Rendle于2010年提出。FM的核心目标是解决高维稀疏数据（如推荐系统、点击率预测中的特征）下的特征组合问题。传统线性模型（如逻辑回归）无法捕捉特征交互，而直接使用多项式模型（如二阶特征组合）会导致参数过多且稀疏性下难以有效训练。FM通过隐向量内积来建模特征交互，将二阶交互参数矩阵分解为低秩矩阵，从而以线性复杂度计算特征组合效应。本题目将详解FM的数学模型、计算步骤及训练方法。 1. 问题背景与模型动机 稀疏数据挑战 ：在推荐系统中，用户和物品的交互数据通常用one-hot编码生成高维稀疏特征（例如用户ID、物品ID的组合）。若直接使用二阶多项式模型，参数数量为O(n²)，且大多数组合在训练集中从未出现，导致过拟合。 FM的解决方案 ：为每个特征学习一个隐向量，通过隐向量的内积表示特征交互的强度。例如，用户A和电影B的交互强度不再用一个独立参数w_ AB表示，而是用向量V_ A和V_ B的内积⟨V_ A, V_ B⟩近似，使相似特征（如用户A和C喜欢同一类电影）共享隐向量，提升泛化性。 2. FM的数学模型 FM模型的预测公式为： ŷ(x) = w₀ + Σᵢ wᵢ xᵢ + Σᵢ Σ_ {j>i} ⟨vᵢ, vⱼ⟩ xᵢ xⱼ 其中： w₀：全局偏置。 wᵢ：一阶特征权重（对应线性部分）。 vᵢ ∈ Rᵏ：特征i的k维隐向量（k为隐向量维度，超参数）。 ⟨vᵢ, vⱼ⟩ = Σᵢᵏ vᵢ,ƒ vⱼ,ƒ 表示隐向量的点积，用于建模特征i和j的交互强度。 关键创新 ：二阶参数矩阵W（元素wᵢⱼ）被分解为VVᵀ（低秩近似），参数量从O(n²)降至O(nk)，且k通常远小于n。 3. 计算过程的优化 直接计算二阶项Σᵢ Σ_ {j>i} ⟨vᵢ, vⱼ⟩ xᵢ xⱼ的时间复杂度为O(kn²)，但FM通过数学变换将其降至O(kn)： 原式 = ½ Σƒ [ (Σᵢ vᵢ,ƒ xᵢ)² - Σᵢ (vᵢ,ƒ xᵢ)² ] 推导步骤 ： 展开所有交互对（包括i=j）：Σᵢ Σⱼ ⟨vᵢ, vⱼ⟩ xᵢ xⱼ = Σƒ (Σᵢ vᵢ,ƒ xᵢ)² 减去对角线项（i=j）：Σᵢ Σⱼ → 2Σᵢ Σ_ {j>i} + Σᵢ (i=j) 最终得：Σᵢ Σ_ {j>i} ⟨vᵢ, vⱼ⟩ xᵢ xⱼ = ½ [ Σƒ (Σᵢ vᵢ,ƒ xᵢ)² - Σᵢ Σƒ (vᵢ,ƒ xᵢ)² ] 计算步骤 ： 对每个隐维度ƒ，计算Sƒ = Σᵢ vᵢ,ƒ xᵢ（复杂度O(n)）。 二阶项 = ½ Σƒ (Sƒ² - Σᵢ vᵢ,ƒ² xᵢ²)（复杂度O(kn)）。 举例 ：设特征向量x=[ 1, 0, 2]（稀疏编码），隐向量k=2，则先对每个ƒ计算Sƒ（如S₁ = v₁,₁ 1 + v₃,₁ 2），再平方求和。 4. 模型训练与损失函数 任务适配 ： 回归：使用均方误差损失，ŷ为连续值。 分类（如CTR预测）：使用sigmoid函数输出概率，损失函数为对数损失。 参数学习 ：通过梯度下降（如SGD）优化所有参数{w₀, wᵢ, vᵢ}。 梯度计算：以回归损失L = (y - ŷ)²为例， ∂L/∂w₀ = -2(y - ŷ) ∂L/∂wᵢ = -2(y - ŷ) xᵢ ∂L/∂vᵢ,ƒ = -2(y - ŷ) xᵢ [ Σⱼ vⱼ,ƒ xⱼ - vᵢ,ƒ xᵢ ] （由二阶项优化公式推导） 正则化 ：常对wᵢ和vᵢ加L2正则化防止过拟合。 5. 扩展与优势 高阶FM ：可扩展至更高阶特征交互（但计算复杂度增加）。 对比其他模型 ： 优于SVM：SVM的核函数需手动设计，FM自动学习特征交互。 优于矩阵分解：FM融入一侧特征（如用户年龄、物品类别），突破仅用ID的局限。 应用场景 ：推荐系统、广告点击率预测、生物信息学等稀疏数据领域。 通过以上步骤，FM以高效的方式建模稀疏特征交互，成为推荐领域的基础算法之一。后续发展如FFM（Field-aware FM）进一步引入了特征域的概念，提升模型表达能力。