搜广推校招面经八十六

Y1n

1222人浏览 · 2025-07-06 00:15:00

Y1n · 2025-07-06 00:15:00 发布

京东搜索推荐算法一面

一、交叉熵损失的推导（贝叶斯）与理解

1.1. 交叉熵损失的定义

设：

真实标签为 one-hot 编码： $y=(y1,y2,...,yC)\boldsymbol{y} = (y_1, y_2, ..., y_C)$
模型预测输出为概率分布： $y^=(y^1,y^2,...,y^C)\hat{\boldsymbol{y}} = (\hat{y}_1, \hat{y}_2, ..., \hat{y}_C)$
则交叉熵损失函数定义为：
$LCE(y,y^)=−∑i=1Cyilog⁡y^i \mathcal{L}_{CE}(\boldsymbol{y}, \hat{\boldsymbol{y}}) = - \sum_{i=1}^C y_i \log \hat{y}_i$
由于 one-hot 中只有 $y_k = 1$ ，其余为 0，所以上式可简化为：
$LCE=−log⁡y^k \mathcal{L}_{CE} = -\log \hat{y}_k$
其中 $k$ 是真实标签对应的类别索引。

1.2. 从贝叶斯角度推导交叉熵

最大似然估计（MLE）

分类模型将类别预测为一个条件概率分布：
$P(y=k∣x;θ)=y^k P(y = k \mid \boldsymbol{x}; \theta) = \hat{y}_k$
最大似然目标：
$\mathcal{L}_{MLE}(\theta) = \prod_{n=1}^N P(y^{(n)} \mid \boldsymbol{x}^{(n)}; \theta)$
取负对数：
$log⁡LMLE(θ)=−∑n=1Nlog⁡P(y(n)∣x(n);θ)\log \mathcal{L}_{MLE}(\theta) = - \sum_{n=1}^N \log P(y^{(n)} \mid \boldsymbol{x}^{(n)}; \theta)$
若用 softmax 输出预测概率，上式等价于：
$LCE=−∑n=1Nlog⁡y^y(n)(n) \mathcal{L}_{CE} = - \sum_{n=1}^N \log \hat{y}^{(n)}_{y^{(n)}}$
即为交叉熵损失。

贝叶斯决策理论视角

真实标签 $y$ 服从真实分布 $P$
模型预测的是 $Q$ ，希望 $Q$ 趋近于 $P$
信息论中的交叉熵：
$-\sum_i P(i) \log Q(i)$
若 $P$ 为 one-hot，则交叉熵就是：
$\log Q(k)$
最小化交叉熵，即最大化正确类别的后验概率 $\mid x)$ ，这与贝叶斯分类器的目标一致。

1.3. 交叉熵与 KL 散度关系

KL 散度定义为：
$\text{KL}(P \| Q) = \sum_i P(i) \log \frac{P(i)}{Q(i)} = H(P, Q) - H(P)$

其中 $H (P)$ 为常数
所以 最小化交叉熵 $H (P, Q)$ 等价于最小化 KL 散度

二、L1 与 L2 范数的假设分布是什么？

2.1 结论

范数类型	损失项形式	对应的先验分布	特性说明
L1 范数	$λ∣w∣1\lambda \|\boldsymbol{w}\|_1$	拉普拉斯分布（Laplace）	促进稀疏性（特征选择），零点密集
L2 范数	$λ∣w∣22\lambda \|\boldsymbol{w}\|_2^2$	高斯分布（Gaussian）	促进平滑解，特征保留但值趋小

2.2. L1 范数对应拉普拉斯分布（Laplace Prior）

损失函数形式

L1 正则化（Lasso Regression）形式为：
$\mathcal{L}_{\text{Lasso}} = \sum_{i=1}^N (y_i - f(x_i))^2 + \lambda \sum_j |w_j|$

2.3. L2 范数对应高斯分布（Gaussian Prior）

损失函数形式

L2 正则化（Ridge Regression）形式为：
$\mathcal{L}_{\text{Ridge}} = \sum_{i=1}^N (y_i - f(x_i))^2 + \lambda \sum_j w_j^2$

2.4. 图像直观比较

高斯分布（L2）：
      ___
     /   \
    /     \
---         ---   → 尾部衰减快，整体光滑，产生稠密参数

拉普拉斯分布（L1）：
     /\
    /  \
---    ---    → 尖峰密集，激励参数为 0，产生稀疏性

三、GBDT中的梯度有何意义，与XGBoost的区别是什么

3.1. GBDT中的梯度意义

GBDT（Gradient Boosting Decision Tree，梯度提升决策树）是一种加法模型，通过不断地拟合残差来逼近目标函数。其“梯度”主要体现在以下几个方面：

在每一轮迭代中，GBDT以当前模型的预测结果与真实值之间的残差为新一轮的学习目标。
这个“残差”实际上是损失函数对当前模型输出的一阶导数（负梯度），即：

3.2. XGBoost与GBDT的区别

3.2.1. 二阶导数的使用

GBDT与XGBoost都是通过拟合这个负梯度（残差）来更新模型，即相当于用决策树去拟合损失函数的下降方向。

GBDT：只使用一阶导数（即负梯度）来拟合残差。
XGBoost：同时使用一阶导数和二阶导数，进行更精确的损失函数泰勒展开，提高收敛速度和精度。

3.2.2. 正则化的使用

GBDT：没有显式正则化项。
XGBoost：在目标函数中加入了正则化项（树的复杂度），控制过拟合。

四、Attention机制介绍与时间复杂度分析

4.1. 基本思想

对于一个输入序列，Attention机制将其映射为三个矩阵：

Q（Query）：查询向量
K（Key）：键向量
V（Value）：值向量
然后通过如下公式计算注意力权重和输出：
Attention(Q, K, V) = softmax( (QK^T) / √d_k ) V
其中：
Q ∈ ℝ^{n×d}
K ∈ ℝ^{n×d}
V ∈ ℝ^{n×d}
n 是序列长度，d 是特征维度
√d_k 是缩放因子，用于避免梯度爆炸

4.2. 多头注意力（Multi-head Attention）的时间复杂度分析

为了增强模型表达能力，Transformer 使用了多头注意力，将输入分别映射到多个子空间后独立计算 Attention，最后将各头的输出拼接起来。

4.2.1. Q、K、V 的线性变换

假设：

输入矩阵为 X ∈ ℝ^{n×d_model}
$W_q, W_k, W_v$ 分别是三个线性变换矩阵，维度为 d_ $m o d e l$ × $d_k$
那么计算：
$Q = XW_q$ ，时间复杂度：O(n·d_ $m o d e l$ · $d_k$ )
$K = XW_k$ ，时间复杂度：O(n·d_ $m o d e l$ · $d_k$ )
$V = XW_v$ ，时间复杂度：O(n·d_ $m o d e l$ · $d_v$ )

a. 计算 $QK^T$

Q ∈ ℝ^{n×d_k}，K ∈ ℝ^{n×d_k}
QK^T 的结果是 n×n 矩阵
时间复杂度：O(n²·d_k)

b. softmax 和乘以 V

softmax(QK^T)：O(n²)
softmax(QK^T) × V：O(n²·d_v)

c. 总体时间复杂度

O(n²·d_ $m o d e l$ )

五、介绍DQN（各种DQN变种的意义）

DQN（Deep Q-Network）是将深度神经网络应用于强化学习Q-learning的一种方法，用于在高维状态空间中逼近Q函数。
核心思想：使用一个深度神经网络 Q(s, a; θ) 来逼近最优动作价值函数 Q*，并通过不断地采样 (s, a, r, s') 来更新网络参数。

输入：状态（如图像）
输出：每个动作对应的 Q 值
更新目标：
$y = r + γ * max_{a'} Q(s', a'; θ⁻)$

5.1. Double DQN（双重DQN）

背景问题：

DQN 中使用 max Q(s', a') 容易造成 过估计（Overestimation）。

改进方式：

将动作选择与动作评估解耦： $y = r + γ * Q(s', argmax_a Q(s', a; θ), θ⁻)$

使用主网络选择动作（argmax）
使用目标网络评估该动作的 Q 值

作用：

减少 Q 值过估计，提高学习稳定性和性能。

5.2. Dueling DQN（决斗DQN）

背景问题：

在某些状态下，动作选择并不重要（如等待状态）。

改进方式：

将 Q 值拆分为状态值 V(s) 与动作优势 A(s, a)： $Q(s, a) = V(s) + A(s, a) - mean_a A(s, a)$

V(s)：表示当前状态本身的价值
A(s, a)：表示某个动作相对于平均动作的优势

作用：

增强对状态的表达能力，加快收敛速度。

5.3. Prioritized Experience Replay（优先经验回放）

背景问题：

原始 DQN 使用 均匀采样，效率较低。

改进方式：

按 TD-error 大小进行采样： $p_i ∝ |δ_i| + ε$

TD-error δ 越大，代表该样本越有学习价值

作用：

更频繁采样有学习价值的样本，加快收敛，提升性能。

5.4. Multi-step DQN（多步 DQN）

背景问题：

一步 TD 更新传播奖励信号慢。

改进方式：

使用 n 步回报进行更新： $r_t + γr_{t+1} + γ²r_{t+2} + ... + γⁿ*Q(s_{t+n}, a_{t+n})$

作用：

加快奖励传播速度，提升训练效率。

5.5. Rainbow DQN（彩虹 DQN）

概述：

将多种 DQN 改进融合为一个综合模型。

包含：

Double DQN
Dueling DQN
Prioritized Replay
Multi-step Learning
Noisy Network
Distributional RL

作用：

在多个强化学习 benchmark（如 Atari）上取得 SOTA 表现。

5.6. 总结

变种名称	主要改进点	意义与优势
Double DQN	解耦动作选择与估值	减少过高估计，提高稳定性
Dueling DQN	分离状态值与动作优势	加强状态表示能力
Prioritized Replay	按 TD-error 采样	加快训练收敛速度
Multi-step DQN	多步奖励回报	奖励传播更高效
Noisy DQN	内建可学习噪声	更有效的探索策略
Distributional DQN	学习 Q 值分布	表达能力增强
Rainbow DQN	多项技术融合	综合最强性能

六、手撕快排（空间复杂度有要求）

class Solution:
    def partition(self, nums, left, right):
        """划分函数：以nums[right]为基准，返回基准值的正确位置索引"""
        pivot = nums[right]
        i = left - 1  # 指向小于基准的子数组末尾
        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]      # 将小元素交换到左侧
        nums[i+1], nums[right] = nums[right], nums[i+1]  # 基准归位
        return i + 1
        
    def topk_split(self, nums, k, left, right):
        """快速选择算法核心：找到第k小元素的位置后停止递归"""
        if left < right:
            # 注意必须添加 self. 调用类方法
            index = self.partition(nums, left, right)
            if index == k:
                return                                    # 找到目标位置，终止递归
            elif index < k:
                self.topk_split(nums, k, index+1, right)  # 处理右半部分
            else:
                self.topk_split(nums, k, left, index-1)   # 处理左半部分
                
    #获得前k小的数
    def topk_smalls(nums, k):
        topk_split(nums, k, 0, len(nums)-1)
        return nums[:k]
        
    #获得前k大的数 
    def topk_larges(nums, k):
        #parttion是按从小到大划分的，如果让index左边为前n-k个小的数，则index右边为前k个大的数
        topk_split(nums, len(nums)-k, 0, len(nums)-1) #把k换成len(nums)-k
        return nums[len(nums)-k:]