搜广推校招面经九十五

发布于：2025-07-20 ⋅ 阅读:(18) ⋅ 点赞:(0)

抖音广告算法

一、看过LGBM的源码没？详细介绍一下LGBM

LightGBM的输入数据是一个二维表格，为了让训练速度变快，无非两个方向：1.减少样本数；2.减少特征数。基于此，原论文提出了两大技术：

  1. GOSS(Gradient-based One-Side Sampling)：减少样本数
  2. EFB (Exclusive Feature Bundling )：减少特征数

除此之外，还有：

  1. 直方图差加速
  2. 自动处理缺省值，包括是否将0视为缺省值。
  3. Leaf-wise

1.1. EFB (Exclusive Feature Bundling )

大部分高纬度的数据都是稀疏的，这就为我们捆绑特征带来了可能性。特征的稀疏就说明很多特征是相互排斥的（它们不总是同时取非0值），所以我们可以很放心的将多个特征捆绑为一个特征。复杂度就从（datafeature）降为（databundle）,其中bundle就是经过捆绑后的特征数，通常bundle远小于feature。

假设有 3 个互斥的稀疏特征：

样本 f1 f2 f3
A 1 0 0
B 0 2 0
C 0 0 3
  • 可见：每个样本中，最多只有一个特征不为 0。
  • 说明这三个特征是 互斥的，可以合并成一个特征 bundle。
捆绑后的特征（Bundle）

将 f1、f2、f3 合并为一个 bundle 特征：

样本 bundle_1
A 编码(f1 = 1)
B 编码(f2 = 2)
C 编码(f3 = 3)
  • 每个特征值会被重新编码到 bundle 特征的不同 bin 中，不会冲突。
  • 这样显著减少了特征数量，提高了训练效率。

1.1.1. 哪些特征应该绑在一起

将相互独立的特征进行绑定是一个 NP-Hard 问题，LightGBM的EFB算法将这个问题转化为图着色的问题来求解，将所有的特征视为图的各个顶点，将不是相互独立的特征用一条边连接起来，边的权重就是两个相连接的特征的总冲突值，这样需要绑定的特征就是在图着色问题中要涂上同一种颜色的那些点（特征）。此外，我们注意到通常有很多特征，尽管不是％100相互排斥，但也很少同时取非零值。我们的算法可以允许一小部分的冲突，我们可以得到更少的特征包，进一步提高计算效率。

1.2. GOSS(Gradient-based One-Side Sampling)

1.2.1. 样本“权值”的缺失问题

在 Adaboost 中：
  • 每个样本有一个“权重”。
  • 没训练好的样本会获得更高权重，以便下一个模型重点学习。
  • 样本的重要性不同。
在 GBDT 中：
  • 所有样本权重相同，每轮都用全部样本。
  • 没有机制区分哪些样本更重要。

1.2.2. LightGBM 提出 GOSS（Gradient-based One-Side Sampling）

  • 用一阶导数（gradient）代替“样本权值”：
    • 大梯度 → 样本当前模型预测得差 → 重要
    • 小梯度 → 样本当前模型预测较好 → 次要
抽样步骤

设：

  • a = 大梯度样本的采样比例
  • b = 小梯度样本的采样比例
    步骤：
  1. 计算每个样本的一阶导数
  2. 将样本按梯度大小排序，取前 a * N 组成 topSet
  3. 从剩下的样本中随机抽取 b * (N - a*N) 个样本组成 randSet
  4. 合并 topSet 和 randSet 作为 usedSet 进行训练
小梯度样本的补偿
  • 由于小梯度样本被减少了，所以需要补偿其重要性
  • 方法：将小梯度样本的梯度值和 Hessian 值乘上 (1 - a)/b

1.2.3. GOSS 的优点总结

  • 保留高梯度样本，提高模型关注重点
  • 大幅减少样本数，加速训练
  • 几乎不影响模型精度（因为补偿机制）

1.3. 直方图算法；直方图差加速

在训练树的时候，需要找到最佳划分节点，为此其中需要遍历特征下的每一个value，这里通常有两种做法：
pre-sorted algorithm(预排序算法)：

  • 预排序算法就是传统的要遍历当前特征下的每一个value，其通常是在开始对该特征下的每个value进行排序，后面就是遍历选取最佳划分点；

histogram-based algorithm（直方图算法）：

  • 直方图算法其实就是将value离散化了，生成一个个bin，常称为分桶，离散化后的bin数其实是小于原始的value数的，于是复杂度从（featuredata）降为了（featurebin）。
  • 同时，在直方图树构建过程中，我们希望找到一个最优的切分点 bin。对于每个候选切分点，我们需要计算左子树和右子树的梯度和、hessian 和、样本数等指标，从而算出每个划分的 gain。但是我们只需要计算出左子树，可以直接all-left=right。
    在这里插入图片描述

1.3.1. 连续特征

连续特征值先被离散化（分桶 binning），为每个 bin 构建直方图，统计梯度、Hessian、数量，使用经典的增益公式（基于梯度、Hessian）。

1.3.2. 离散特征

类别值编码为整数，并做频次统计与筛选，为每个类别（或组合）构建 bin。

1.4. 带深度限制的 Leaf-wise 算法

在Histogram算法之上，LightGBM进一步的优化。它抛弃了大多数GBDT工具使用的按层生长 (level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。

1.4.1. Level-wise（按层生长的决策树）

XGBoost 采用 Level-wise 的增长策略，该策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，实际上很多叶子的分裂增益较低，没必要进行搜索和分裂，因此带来了很多没必要的计算开销。
在这里插入图片描述

1.4.2. Leaf-wise（按叶子生长的决策树）

LightGBM采用Leaf-wise的增长策略，该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。
Leaf-wise的优点是，在分裂次数相同的情况下，Leaf-wise可以降低更多的误差，得到更好的精度；
Leaf-wise的缺点是，可能会长出比较深的决策树，产生过拟合。因此LightGBM会在Leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。
在这里插入图片描述

二、xgb怎么并行运算

2.1. 默认的特征级别并行（Feature-level Parallelism）

在训练过程中，XGBoost 需要为每个节点找到最优的划分点。为了找到最优特征的分裂点，需要对每个特征进行遍历计算 gain。上面的Level-wise（按层生长的决策树）↑

并行策略：
  • 对 每个特征的分裂点寻找过程并行处理。
  • 即每个线程分别负责一部分特征，计算每个特征的候选分裂点和其对应的 gain。最后再 reduce（归并） 所有特征找到 gain 最大的那个。

假设有 100 个特征，4 核 CPU，可以将这 100 个特征均分到 4 个线程，每个线程处理 25 个特征。

2.2. 数据级别并行（Row-level Parallelism）

虽然不像特征并行那样是默认的核心方式，但 XGBoost 在某些实现（如 GPU 训练、特定分布式场景）中支持 按样本划分数据进行并行计算。

  • 把训练数据行（样本）按 block 拆成不同的 batch，交由多个线程或设备（如 GPU 核）分别计算梯度和直方图。
  • 在构造 histogram（直方图）时，数据被划分到不同线程中累加，称为 histogram aggregation。
  • 特别在启用 hist 或 gpu_hist booster 时，数据并行被广泛使用。

三、为什么逻辑回归（Logistic Regression, LR）更容易并行？

逻辑回归是一个 线性模型 + Sigmoid 函数 + 交叉熵损失，它的优化目标函数是：
J(θ)=−1/N∑[yi∗log(pi)+(1−yi)∗log(1−pi)] pi=sigmoid(θTxi) J(θ) = -1/N ∑ [y_i * log(p_i) + (1 - y_i) * log(1 - p_i)] \\\ p_i = sigmoid(θ^T x_i) J(θ)=−1/N∑[yi​∗log(pi​)+(1−yi​)∗log(1−pi​)] pi​=sigmoid(θTxi​)

  • LR 是线性模型，不涉及树的递归构建或分裂点比较；
  • 没有每一轮必须依赖上一轮结构的递推（不像 XGBoost 中每轮依赖残差）。所以可以在多个线程/机器中“分片式”处理。

3.1. 逻辑回归中的并行粒度

1. 样本维度并行（Data Parallelism）

  • 损失函数和梯度是对所有样本求平均/累加：
    ∇J(θ)=∑i∇Ji(θ)/N ∇J(θ) = ∑_i ∇J_i(θ) / N ∇J(θ)=i∑​∇Ji​(θ)/N
  • 所以每个线程或 worker 可以独立计算一部分样本的梯度，然后再 reduce 汇总。
    ✔️ 示例：100万个样本，4个线程，每个线程计算25万样本梯度，最后汇总。

2. 特征维度并行（Feature Parallelism）

  • 对于稀疏大维度特征（如 CTR 场景中 10^6 特征），每个线程可以负责一部分参数更新；
  • 特别适用于 L-BFGS、FTRL、SGD 等优化器中的参数更新过程。

3. 逻辑回归与分布式系统的适配性更好

  • 在分布式场景中，每台机器处理数据 shard，并独立计算局部梯度；
  • 再通过 AllReduce 或参数服务器机制聚合结果；
  • 模型参数 θ 可以通过同步或异步方式更新。

四、交叉熵的计算公式。什么时候需要使用 Softmax？

4.1. 二分类交叉熵（Binary Cross Entropy）

如果标签为 y ∈ {0, 1}，预测为 ŷ ∈ [0, 1]，则公式为：
BCE=−[y∗log(y^)+(1−y)∗log(1−y^)] BCE = -[y * log(ŷ) + (1 - y) * log(1 - ŷ)] BCE=−[y∗log(y^​)+(1−y)∗log(1−y^​)]

4.2. 多分类交叉熵（Multi-class Cross Entropy）

若共有 C 个类别，真实标签 y 是 one-hot 编码，预测为 softmax 输出 ŷ_i，则：
CrossEntropy=−∑(i=1toC)yi∗log(y^i) CrossEntropy = -∑(i=1 to C) y_i * log(ŷ_i) CrossEntropy=−∑(i=1toC)yi​∗log(y^​i​)
可以简化为（因为 one-hot 编码只有一个位置是 1）：
CrossEntropy=−log(y^trueclass) CrossEntropy = -log(ŷ_true_class) CrossEntropy=−log(y^​t​ruec​lass)

4.3. 什么时候需要使用 Softmax？

  • 在 多分类问题中，模型输出 logits（未归一化的实数）后，必须加 softmax 转换为概率分布。

五、131. 分割回文串

在这里插入图片描述

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        path = []
        n = len(s)
        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            for j in range(i,n):
                t=s[i:j+1]
                if t == t[::-1]:
                    path.append(t)
                    dfs(j+1)
                    path.pop()
        dfs(0)
        return ans

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布