搜广推校招面经二十八

美团推荐算法

一、介绍FM提取值的公式

1.1. FM 的基本形式

FM 的预测值可以表示为：
$$\hat{y}(\mathbf{x})=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j$$

其中：

• $\hat{y}(\mathbf{x})$：模型的预测值；
• $w_0$：全局偏置项；
• $w_i$：第 $i$ 个特征的线性权重；
• $x_i$：第 $i$ 个特征的值；
• ${\mathbf{v}}_i$：第$i$ 个特征的隐向量（长度为 $k$ 的低维向量）：隐向量用于将高维稀疏特征，降为低维稠密的特征。
• $⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩$：隐向量 ${\mathbf{v}}_i$ 和 ${\mathbf{v}}_j$ 的内积，用于建模特征 $i$ 和 $j$ 的交互关系。

1.2. 特征交互项的优化公式

直接计算二重求和 ${\sum }_{i=1}^n{\sum }_{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j$ 的时间复杂度为 $O(n^{2}k)$，在高维稀疏数据中效率较低。因此，FM 提出了一个优化公式，将复杂度降低到 $O(kn)$。
优化后的公式为：
$$\sum _{i=1}^n\sum _{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j=\frac{1}{2}\sum _{f=1}^k\left({\left(\sum _{i=1}^n{v}_{i,f}{x}_i\right)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2\right)$$

公式推导：

1. 展开隐向量内积 $⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩$：
   $$⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩=\sum _{f=1}^k{v}_{i,f}{v}_{j,f}$$
   因此：
   $$\sum _{i=1}^n\sum _{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j=\sum _{f=1}^k\sum _{i=1}^n\sum _{j=i+1}^n{v}_{i,f}{v}_{j,f}{x}_i{x}_j$$

2. 利用平方展开公式 $(a+b{)}^2=a^2+b^2+2ab$，可以将两两交互项转化为单个求和项：
   $$\sum _{i=1}^n\sum _{j=i+1}^n{v}_{i,f}{v}_{j,f}{x}_i{x}_j=\frac{1}{2}\left({\left(\sum _{i=1}^n{v}_{i,f}{x}_i\right)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2\right)$$

3. 将所有维度 $f$ 的结果累加，得到最终公式。

1.3. 完整预测公式

将线性部分和优化后的交互部分结合起来，FM 的预测公式可以写为：
$$\hat{y}(\mathbf{x})=w_0+\sum _{i=1}^n{w}_i{x}_i+\frac{1}{2}\sum _{f=1}^k\left({\left(\sum _{i=1}^n{v}_{i,f}{x}_i\right)}^2-\sum _{i=1}^n{v}_{i,f}^2{x}_i^2\right)$$

二、pointwise、pairwise、listwise原理和区别

2.1. Pointwise 方法

（1）原理

• Pointwise 方法将排序问题视为一个回归或分类问题。每个样本被单独处理，模型的目标是为每个样本预测一个独立的分数。
• 如果目标是回归问题，则预测值表示文档的相关性得分；如果是分类问题，则预测值表示文档是否相关。

（2）优点

• 简单直观，容易实现。
• 可以直接使用标准的回归或分类算法（如线性回归、逻辑回归等）。

（3）缺点

• 忽略了样本之间的相对关系，无法直接优化排序质量指标（如 NDCG、MAP）。对于排序任务来说，可能不够精确。

（4）适用场景

• 当样本之间相对顺序不重要时，或者排序目标可以通过简单的回归/分类来近似时。

2.2. Pairwise 方法

（1）原理

• Pairwise 方法关注样本对之间的相对顺序。模型的目标是比较两个样本的相关性得分，并确保相关性更高的样本获得更高的分数。
• 训练数据由样本对组成，标签表示两个样本之间的相对顺序（例如，1 表示第一个样本更重要，0 表示第二个样本更重要）。

（2）优点

• 能够直接建模样本之间的相对关系。更适合优化排序质量指标（如 NDCG、MAP），因为这些指标本质上依赖于样本对的相对顺序。

（3）缺点

• 需要构造大量的样本对，计算复杂度较高。在高维稀疏数据中可能会面临效率问题。

（4）适用场景

• 当需要优化排序质量指标时，或者样本之间的相对顺序非常重要时。

2.3. Listwise 方法

（1）原理

• Listwise 方法直接针对整个列表进行建模。模型的目标是为整个列表生成一个合理的排序，使得相关性高的样本排在前面。
• 训练数据由整个列表组成，标签通常是一个分布（如 Softmax 分布），表示每个样本在列表中的相对重要性。

（2）优点

• 最接近实际排序任务的需求，能够直接优化排序质量指标。
• 能够考虑整个列表的整体结构，而不仅仅是样本对的关系。

（3）缺点

• 实现复杂度较高，需要设计专门的损失函数（如 ListNet、ListMLE）。
• 对于大规模数据集，计算成本可能较高。

（4）适用场景

• 当排序任务需要考虑整个列表的整体结构时，或者需要直接优化排序质量指标时。

2.4. 三者的区别

• Pointwise：简单易用，但忽略了样本之间的相对关系。
• Pairwise：关注样本对的相对顺序，适合优化排序质量指标。
• Listwise：直接针对整个列表建模，最适合真实的排序任务。

选择哪种方法取决于具体任务的需求和数据规模。如果需要快速实现，可以先尝试 Pointwise；如果排序质量指标很重要，可以选择 Pairwise 或 Listwise。

三、78. 子集（hot100_回溯_中等）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]  # 神来之笔
        return res