2025.3.7 面试记录

记录第一次面试

聊经历环节

Q：自我介绍一下
A：略

Q：讲讲你的围捕论文
A：略（大约20分钟？）

Q：在你的项目中是如何避免sim2real的gap的
A：我们会把环境尽可能抽象以避免与真实世界的差距。

Q：你这里策略空间是比较小的，有没有什么办法在策略空间比较复杂的情况下获得一个好的策略。
A：我可能会使用一些专家数据，进行模仿学习。或者用LLM进行引导，从而获得一个好的策略。我认为RL任务中或许也存在Scaling Law，更大的参数规模也许会让策略网络和价值网络有更好的分析能力，从而做出更长线的规划。

分析：总结了几种方法

• 分层强化学习：将复杂任务分解为层次化子任务，上层负责长期规划，下层执行具体动作。这在我们的围捕项目中也能应用，将策略分为战略布局和战术执行两个层次。
• 课程学习与模仿学习结合：首先通过专家数据进行模仿学习建立基础能力，然后设计难度递增的课程，逐步优化策略。我曾在实验中发现，这种方法比单纯的RL训练收敛更快，且更稳定。
• 自监督探索：在复杂环境中，加入内在激励机制促进有效探索，如好奇心驱动或新颖性搜索，帮助智能体发现隐藏的解决方案。
• 大模型指导与知识蒸馏：利用LLM生成探索方向或初始策略，但我会更进一步结合知识蒸馏，将大模型的决策能力浓缩到更轻量的策略网络中，保证实时性能。
• 进化算法与RL混合：对于特别复杂的策略空间，有时传统RL难以收敛，我发现结合进化策略可以更有效地探索全局最优解。

Q：如果想让一个bot的行为更好，但是又要拟人，你会怎么做呢？
A：我也许会收集大量的用户数据来进行模仿学习，从而既保证其性能，又保证其的拟人性。
Q：还有别的方法吗？
A：我也许还会用逆强化学习去估计专家的奖励函数，不过这也是模仿学习的范畴了。
Q：还有么？
A：也许我会使用LLM评估agent的拟人性。

Q：讲讲如果你在你的项目里用MARL，你会使用什么算法？
A：MAPPO
Q：Why？
A：额，可能只是因为PPO在单智能体场景下性能比较好。

分析：这里没答上来，还是得稍微了解一些多智能体强化学习的方法的。
MAPPO有一些特性：

• 稳定性与可靠性：PPO通过限制策略更新步长来保证训练稳定性，这一特性在多智能体环境中尤为重要，因为多智能体系统本身具有较高的不稳定性和非平稳性。在我们的围捕项目中，智能体间的互动会导致环境动态快速变化，MAPPO的稳定性能很好地应对这一挑战。
• 集中式训练，分布式执行架构：MAPPO支持集中式训练与分布式执行范式，这与我们的系统设计匹配 - 在训练阶段可以访问全局信息以提升学习效率，而在执行阶段每个智能体只依赖自身观察。
• 处理异质智能体的能力：在我们的项目中，不同智能体可能需要扮演不同角色（如包围、拦截等），MAPPO可以通过参数共享同时保持个体特性，很好地适应这种需求。

基础知识环节

Q：PPO和SAC都用到了策略熵，说说他们的不同。
A：额，我知道SAC使用策略熵和预设的目标熵进行对比，动态的调整策略的稳定性。但是PPO我似乎不太知道其熵的存在。我知道PPO通过KL散度限制策略的更新幅度，但是似乎对策略熵的应用没有印象

分析：这里确实不知道PPO中还有策略熵，毕竟不是核心创新点。
SAC中的熵应用：
SAC将熵直接整合到优化目标中，形成’最大熵RL’框架。具体来说，SAC的目标函数是$\mathbb{E}[R+\alpha\mathcal{H}]$，其中$R$是奖励，$\mathcal{H}$是策略熵，$\alpha$是温度参数。SAC的创新之处在于$\alpha$是自动调节的 - 算法会比较当前策略熵与预设目标熵，动态调整$\alpha$以达到目标熵水平。这使SAC能在探索与利用之间取得更好的平衡，特别适合多模态奖励环境。
PPO中的熵应用：
PPO也使用熵正则化，但作为辅助机制而非核心组件。在PPO的目标函数中，通常会添加一项$\beta \mathcal{H}(\pi)$，其中$\beta$是固定的熵系数，$\mathcal{H}(\pi)$是策略熵。这个熵项鼓励策略保持一定的随机性，防止过早收敛到次优解。与此同时，PPO的主要稳定机制是通过裁剪概率比来限制策略更新，

Q：那说说TRPO是如何从PG推导过来的
A：PG的代表算法REINFORCE采用的是蒙特卡洛采样方法，这种方法需要把整条轨迹都采样完毕后才能进行一次更新，这样会导致较大的方差，从而影响策略的稳定收敛。于是TRPO通过对新旧策略的KL散度进行计算，把策略的更新设计成一个带有约束的优化问题，避免了参数的不稳定更新。

分析：
从策略梯度(PG)到TRPO的推导过程涉及几个关键步骤：

• 标准策略梯度：PG算法通过梯度上升最大化期望回报$J(\theta) = \mathbb{E}_\tau[R(\tau)]$，其梯度为$\nabla_{\theta}J(\theta) = \mathbb{E}_\tau[\nabla_\theta \log \pi_\theta(a|s) \cdot R(\tau)]$。
• 策略性能提升保证：Kakade和Langford证明了策略改进的下界定理，表明新旧策略性能差可以表示为：

$$J(π_{new}) - J(π_{old}) \ge \mathbb{E}_{(s,a)\simπ_{old}}\left[A_{π_{old}}(s,a) · \frac{π_{new}(a|s)}{π_{old}(a|s)}\right] - C · D_{KL}^{\max}(π_{old}, π_{new})$$

其中$A$是优势函数，$D_{KL}^{max}$是最大KL散度，$C$是常数。

• 从保守策略迭代到TRPO：基于上述不等式，TRPO将策略优化定义为一个约束优化问题：

$$\max_{\theta} \; \mathbb{E}_{s,a \sim \pi_{\theta_{old}}}[A_{\pi_{\theta_{old}}}(s,a) \cdot \frac{\pi_{\theta}(a|s)}{\pi_{\theta_{old}}(a|s)}]$$

$$\text{s.t.} \; \mathbb{E}_{s \sim \rho_{\pi_{\theta_{old}}}}[D_{KL}(\pi_{\theta_{old}}(\cdot|s) || \pi_{\theta}(\cdot|s))] \leq \delta$$

这里用平均KL散度替代了最大KL散度，使问题更易处理。

• 近似求解：
  • 使用样本估计优势函数
  • 对目标函数进行一阶近似：

$$L(\theta) \approx L(\theta_{old}) + \nabla_\theta L(\theta_{old})^T(\theta - \theta_{old})$$

对KL约束进行二阶近似：

$$D_{KL}(\pi_{\theta_{old}} || \pi_\theta) \approx \frac{1}{2}(\theta - \theta_{old})^T H (\theta - \theta_{old})$$

其中$H$是KL散度关于$\theta$的Hessian矩阵。最终通过共轭梯度和线搜索方法求解这个近似问题。
TRPO的核心创新在于，它不仅指出了策略梯度中可能的不稳定性来源，更提供了理论保证的解决方案 - 通过KL散度约束确保每次更新都能提升策略性能或至少不会显著降低性能。这解决了标准PG算法中可能出现的大步长更新导致性能崩溃的问题，为后来的PPO等算法奠定了理论基础。

Q：有接触过SL吗？
A：以前做过一些CV

Q：说一说标签不均时有什么办法
A：可以在采样时调整不同标签的比重使其尽可能均匀，也可以使用一些模型生成数据来做半监督学习。

分析：不记得有什么方法了，就说了两个。

1. 数据层面：

   • 重采样技术：可以对少数类过采样(Oversampling)或对多数类欠采样(Undersampling)。在实践中，我发现SMOTE(合成少数类过采样)和其变体如Borderline-SMOTE在保持数据分布的同时增加少数类样本效果较好。
   • 数据增强：针对少数类进行特定的数据增强，如在CV中对少数类图像进行旋转、缩放、翻转等变换；在NLP中使用回译或同义词替换等技术。

2. 算法层面：

   • 加权损失函数：根据类别频率反比设置权重，如在分类问题中使用class_weight='balanced'或手动设置权重，我经常将权重设为$w_i = \frac{N}{K \times n_i}$，其中$N$是总样本数，$K$是类别数，$n_i$是第$i$类的样本数。
   • 特殊损失函数：使用Focal Loss等对难分样本给予更高权重的损失函数，我在目标检测任务中发现它比交叉熵损失效果显著。

3. 评估层面：

   • 合适的评估指标：不仅关注准确率，还要考察精确率、召回率、F1分数、AUC-ROC等更适合不均衡数据的指标。
   • 分层交叉验证：确保每个折中类别分布与原始数据集一致。

Q：RNN和Transformer的区别
A：RNN由于把输入序列化，导致越往后越会忘记前文。而Transformer从全局计算注意力矩阵，很好的考虑到了上下文信息。为了解决位置的独特影响，Transformer加入了位置编码。

分析：

1. 序列处理方式：

   • RNN：采用循环结构，按时间步顺序处理输入，当前时刻状态依赖于前一时刻状态。基本公式：$h_t = f(W_h h_{t-1} + W_x x_t + b)$
   • Transformer：基于自注意力机制，同时处理整个序列，每个位置直接与所有位置交互。核心公式：$\text{Attention}(Q, K, V) = \text{softmax}(\frac{QK^T}{\sqrt{d_k}})V$

2. 长程依赖：

   • RNN：存在长期依赖问题 - 信息在序列传递过程中会逐渐衰减（梯度消失）或爆炸。LSTM/GRU等变体通过门控机制缓解但未完全解决此问题。
   • Transformer：通过自注意力机制建立任意距离位置间的直接连接，序列长度不影响信息传递距离，理论上能捕获无限长的依赖关系。

3. 计算并行性：

   • RNN：本质上是顺序计算，第t步必须等待第t-1步完成，无法并行。
   • Transformer：所有位置的计算可完全并行化，极大提高训练和推理速度，特别适合现代GPU/TPU加速。

4. 位置信息：

   • RNN：位置信息隐式编码在序列处理顺序中。
   • Transformer：需要显式添加位置编码（如正弦/余弦位置编码或可学习位置嵌入），否则模型无法区分不同位置的token。

Q：在一个POMDP中，如果需要使用局部观测观测进行全局信息的估计，你会使用LSTM还是Transformer？
A：其实我更倾向于LSTM，因为在RL问题中，往往越近的观测更具有可信度，那么遗忘就不是一件坏事了。这也就是为什么我们需要折扣因子的原因。

分析：

1. LSTM对序列数据有天然的处理能力，特别适合POMDP中需要从历史观测推断当前状态的场景
2. 计算效率方面，LSTM处理增量观测很高效，不需要每次都重新计算整个历史的注意力，这在实时决策环境中很重要
3. LSTM的门控机制能够学习什么信息该记住、什么该忘记，这对处理有噪声的观测很有用
4. 在RL环境中，LSTM产生的状态表示通常比较稳定，这对策略学习有好处

Transformer的优势：

1. 如果历史观测中有关键信息，但出现顺序不规则，Transformer的全局注意力机制可能表现更好
2. 对于超长序列依赖的环境，理论上Transformer不会像LSTM那样受到梯度消失的限制
3. 训练速度上，Transformer的并行计算有优势

Q：RNN的主要问题以及后续GRU和LSTM如何解决
A：RNN主要问题就是长程依赖性问题，GRU和LSTM通过加入门控机制来解决，但这一块原理我有些淡忘了。

分析：这里确实忘了，毕竟没有经常使用RNN，基本不记得了。
首先，RNN的核心问题有两个方面：

1. 梯度消失问题：在反向传播时，梯度会沿着时间步骤连乘，由于权重通常小于1，连乘后梯度会接近于0，导致远距离的信息几乎无法影响当前输出。这就是为什么vanilla RNN很难学习长距离依赖关系。
2. 梯度爆炸问题：相反，如果权重大于1，梯度会随着时间步呈指数增长，导致训练不稳定。虽然梯度裁剪可以部分缓解这个问题，但并不能从根本上解决。
   针对这些问题，LSTM和GRU提出了不同的门控机制：
   LSTM引入了三个门：

• 遗忘门：决定丢弃多少上一状态的信息
• 输入门：决定更新多少新信息到细胞状态
• 输出门：决定输出多少细胞状态的信息

这种设计的核心创新是细胞状态（cell state）通道，它可以不受门控直接传递信息，避免了反向传播中的连乘效应，从而解决梯度消失问题。
GRU则是LSTM的简化版本，它只使用两个门：

• 更新门：相当于LSTM的输入门和遗忘门的组合
• 重置门：控制使用多少前一状态的信息

GRU计算更高效，参数更少，在很多任务上表现与LSTM相当，特别是在数据量较小时可能更不容易过拟合。
这些门控机制的本质是让网络学会选择性地记住有用信息、遗忘无关信息，从而能够捕获长距离依赖。以语言模型为例，如果序列开头出现"我来自中国"，即使在很多词之后，当需要用代词时，网络依然能"记得"说话者是"我"而非"他"。

现场编程环节

1. 编辑距离
   分析：经典的DP题，在这里再过一遍。
   给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。
   你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

重点就是dp如何设计，这里直接使用二维dp。dp的size为$(n+1)\times (m+1)$，dp[i][j]为word1的前$i$个单词与word2的前$j$个单词的最小编辑距离。这样就成功构造了规模更小的子问题。
考虑dp的状态转移方程：

• 如果word1[i] == word2[j]
  • 此时这两个词的末尾字母相同，无需修改。那么最小编辑距离就等于去掉这个末尾字母的最小编辑距离dp[i-1][j-1]
• 如果word1[i] != word2[j]，这时两个词的末尾不同：
  • 如果使用插入操作，即出现'ros'和'love'的情况，通过插入'e'来使'ros'变成'rose'以使末尾位相同，那么最小编辑距离就是dp[i][j-1]，即'ros'和'lov'的最小编辑距离加1。
  • 如果使用删除操作，即出现'love'和'dev'的情况，通过删除'e'来使'love'变成'lov'以使末尾位相同，那么最小编辑距离就是dp[i-1][j]，即'lov'和'dev'的最小编辑距离加1。
  • 如果使用替换操作，即出现'love'和'bash'的情况，通过替换'e'来使'love'变成'lovh'以使末尾位相同，那么最小编辑距离就是dp[i-1][j-1]，即'lov'和'bas'的最小编辑距离加1。
  • 即：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

n, m = len(word1), len(word2)
dp = [[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
   dp[i][0] = i

for i in range(m+1):
   dp[0][i] = i

for i in range(1, n+1):
   for j in range(1, m+1):
         if word1[i-1] == word2[j-1]:
            dp[i][j] = dp[i-1][j-1]
         else:
            dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

dp[-1][-1]

2. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

分析：我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。

m,n = len(grid), len(grid[0])
if m == 0:
   return 0
ans = 0
def dfs(i,j):
   grid[i][j] = '0'
   for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
         if 0<=x<m and 0<=y<n and grid[x][y] == '1':
            dfs(x,y)
for i in range(m):
   for j in range(n):
         if grid[i][j] == '1':
            ans += 1
            dfs(i,j)
ans

3. Transformer的self-attention计算怎么写

$$\text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$

$$\text{softmax}:\frac{e^{z_i}}{\sum^n_{j = 1}e^{z_j}}$$

尾声

Q：你有什么想问我的吗？
A：（没问什么，就问了工作内容）