大模型算法工程师面试经验

发布日期

July 13, 2024

从2024年三月以来，我著手做一些大模型方向的面试准备工作。本文简单记录了一些实际面试过程中被问到的问题以及一些自己认为比较重要的知识。

文章使用“🌙”符号表示自己认为比较重要的知识，用“⭐”表示面试中实际被问到过的知识。“🌙/⭐”符号的多少指示我对问题重要性的评估（五分制）。

本人水平有限，文章内容不一定正确。本文的内容也难称完整，会持续保持更新。

1 LLM相关问题

1.1 数据工程

例子 1 🌙你有哪些大模型数据工程方面的经验值得分享？

一些感性经验：

数据的配比：在训练模型的过程中，我们经常为不同来源的训练数据设置不同配比，例如为数量级比较少的数据设置一个比较大的采样比例，为辅助任务数据设置较小的采样比例。
多次重复采样同一个数据可能导致模型在推理时有概率重复输出训练数据中的这些文本，因此采样比例不宜设置过大。（采样比例过大可以类比为训练集中有大量重复数据，因此这一经验也说明了训练数据去重的重要性。）
Early stop：一般经过SFT，使得交叉熵损失降低到\(0.5\)~\(0.3\)可以认为模型的训练已经充分。一般不宜将损失训练到\(0.1\)以下，此时模型可能已经发生过拟合。基于同样的理由，一般不要训练太多epoch，一般取\(1\)~\(3\) epoch内的训练结果。（这里提到的一些具体数值可能要依据具体项目而定，不是一成不变的。）
数据质量：相关论文^[1]认为，少量高质量的SFT数据能胜过大规模SFT数据，即数据的质量对于模型最终效果有非常直接的影响。当预测数据中出现不符合预期的模式（例如错别字、乱码等），应该及时从SFT数据集中搜索相关文本，找到导致问题的原因，并向数据来源做出反馈。
在项目的初期，人们常常使用GPT4等业界领先的通用大模型生产数据。这样的“伪造”数据对快速启动项目，建立项目雏形是有帮助的。但是，在项目数据得到充分积累之后，应当尽量用真实的、面向项目需求的人工标注数据、线上回流数据代替伪造数据，这样才能取得最好的效果。
验证集建设：合理的验证集设置是正确引导项目前进的关键。验证集建设过程中首先要注意数据分布接近真实场景，其次要注意“去毒化（Detoxification）”，即确保验证集数据不要泄露到训练集中。

1.2 训练工程

大模型的训练工程是指通过建设训练基础设施、改进训练策略等方法保障大模型在大规模数据、调用大量计算设备上正常训练、提高训练效率的工作。大模型的不同并行训练方法是需要熟悉掌握的重点。

例子 2 🌙🌙🌙🌙请介绍一下常见的几种并行训练方法。

参考资料：

Huggingface Transformers文档

1.3 偏好对齐

例子 3 ⭐为什么要做偏好对齐？只做SFT不行吗？

只做SFT不做偏好对齐经常会导致一些问题。
首先是从训练目标来看：预训练、SFT任务本质上都是要求模型预测下一个token，而这与AI应用的目标——“以安全和有益的方式遵循人类指令”是不一致的^[2]。这种训练目标的不对齐导致模型容易产生不安全、不忠实或有害的信息。

其次是曝光偏差问题：在预训练、SFT阶段，模型只是在训练数据的分布上进行下一个token的预测。一些基于强化学习的偏好对齐任务提供了一种在模型自身预测分布上进行训练的方法^[3]，缓解了曝光偏差问题。

例子 4 ⭐基于PPO强化学习方法为什么需要使用成对的训练数据？

（目前KTO已经实现了基于不成对的偏好数据进行训练。这里不讨论KTO，只讨论经典的PPO。）

我们从以下几点分析这个问题。
1. 能不能只给一个正面数据或负面数据？如果只给正面数据，那么偏好对齐任务便退化为SFT任务。Jiwoo Hong等人^[4]指出，随著SFT过程的进行，虽然模型产生训练文本的概率会上升，但被拒绝文本的概率也随之上升。这表明只给出正面数据（只做SFT）是无法作偏好微调的。类似的，可以推测如果只降低负面数据的出现概率，那正面文本的出现概率也会下降。
2. 为什么PPO使用的是成对的正负样本，而不是为每一个回复给出一个准确的分值？如果给每一个回复打分，那么很容易便可以通过分值数据构造正负样本对。但是从标注规范制定的角度看，制定一个统一且清晰的打分标准可能比较困难。不是所有事情都有统一的标准。相对的，判断哪个回复更容易被接受就相对容易一些。
从reward model学习的角度看，reward model学习目标是正确地评估不同回复之间的相对优劣，而不是模型回复的绝对评分。既然模型回复的绝对评分是不需要的，为什么还要在标注过程中打出具体的分数呢？此外，评分的粒度也是一个问题。例如，有两个模型回复都打了3分（5分制），那这两个回复间就不能再分出优劣了吗？即使两个回复都打了同样的分数，它们之间的差异也可能提供有价值的信息。以上讨论说明了为什么PPO为什么采用了成对正负样本进行训练。但是在项目实践中，我也经历过需要标注员标注具体分数的情况。在任务规范清晰、打分标准容易制定的前提下，规定具体的评分标准有好处：

详细、严谨的规范有助于减少数据中的噪声；
分值间的相对差异大小可以为训练过程提供细化的指导。例如，可参考LLaMa 2^[5]在reward model的损失中加入一个margin component，要求正负样本相似时reward model的打分可以不用差距太大，反之则要求二者的打分要有显著差异。
最后，即使是在标注员已经提供了具体分值的情况下，我们仍要求标注员对所有回复进行排序，即使有些模型回复的分值是相同的。不同标注员的排序一致性是评价数据质量的一个重要指标。

3. 训练成本。 从训练成本的角度来看，成对的偏好训练数据更容易大规模收集（例如可以在用户点踩的时候立即给出另一个备选回复），标注成本也更低。

例子 5 🌙什么是对齐税？如何减少对齐税？

在经过偏好对齐后，模型的通用能力可能下降，比如可能出现更多地生成不适当的“拒绝回答”现象，这一问题被称为“对齐税”。那么，我们要如何减少“对齐税”，让经过RLHF的模型尽量保持RLHF之前的能力呢？

在PPO算法中，除了reward model、policy model，还有一个reference model（同样由SFT后的模型初始化得到）。PPO算法会限制policy model不过分偏离reference model。这可以视为一种限制policy model能力偏移的机制。（尽管reference model的作用不止于此。）

InstructGPT^[2]指出通过在PPO更新步骤中混入增加预训练分布的对数似然可以大幅降低模型的能力衰退。尽管多数研究未能消除偏好对齐对模型性能的损害，但也存在证据表明负对齐税是可能实现的。OpenAI对大模型数学答题能力的一项研究^[6]显示以合适的reward model设计为前提，模型的数学回答正确率能够提升。尽管这项工作是针对数学任务进行的，但这一结论有可能可以推广到一般的文本生成任务。

例子 6 🌙当前RLHF的流程有什么值得优化的地方？

这是一个开放性问题。言之有理地回答即可。

个人认为可以讨论的点：

如Let’s Verify Step by Step^[6]一文指出的那样，偏好对齐可有更细粒度的标注，给出更准确的reward反馈。现在普遍常见的偏好数据只针对完整的回答给出标注，而不是针对每一个句子给出标注。相比于标注整个回答的偏好，仅标注出第一个有问题的句子/步骤不会增加更多的标注代价，但能够提升reward信号的精细程度。这样的细粒度偏好数据是目前比较少见的，有待建设；
大多数偏好对齐方法采用了BT模型。BT模型要求reward model拉开正负样本的得分差距，但并没有考虑到正负样本间差异以及偏好程度差异的强弱问题。直觉上，对于回复相似，偏好差异不明显的情况，应该给与比较低的权重；对于回复差异大，偏好对比明显的情况，应该给与比较高的权重。一些工作^[5,7]尝试了人为设置规则或调整超参来调整BT model的margin，但也许还有自适应地调整BT model的margin且取得更好对齐效果的方法存在。

1.4 幻觉

例子 7 ⭐为什么SFT后的大模型会有幻觉？ 模型的幻觉是指模型误认为自己能感知到一些实际感知不到的东西，或者以非常肯定的态度给出错误信息。例如，问“现在是几点钟？”，模型在不接入外部插件的情况下回答“现在是下午三点”，这便属于模型幻觉。

预训练、SFT任务本质上都是要求模型预测下一个token，而这与AI应用的目标——“以安全和有益的方式遵循人类指令”是不一致的^[2]。这种训练目标的不对齐导致模型容易产生不安全、不忠实或有害的信息，例如导致模型幻觉。

1.5 灾难性遗忘

例子 8 ⭐SFT过程中会出现灾难性遗忘吗？如何应对灾难性遗忘？

一般我们在项目中会通过SFT来获得一个面向专门领域和特定任务的模型，例如心理诊疗模型、法律咨询模型、医疗建议模型、论文修改模型。SFT的过程中大模型很容易忘记对象任务以外的知识，损失一部分通用能力。就目前的技术来看，灾难性遗忘问题是不可避免的，但可以通过以下方法缓解：
蒸馏：使用预训练模型作为教师模型，引入KL散度约束，使模型的token分布不要过于偏离预训练模型。（实践上来看比较难起作用，调参困难。）
数据重放：一种直接的做法是在SFT阶段随机地采样一部分预训练数据。（经验上看，预训练数据的采样比例在SFT阶段会起到比较大的影响。）
部分参数微调：与全量微调不同，可考虑采用LoRA、Soft Prompt等方法，通过调控参与训练的参数量来控制SFT的拟合程度。（个人实践中还是全量微调比较多。）
一些相关的学术工作：LoRAMoE^[8]通过冻结主干网络，迫使LoRA利用一部分世界知识来缓解灾难性遗忘。
其它训练参数的调整：可以尝试调整学习率、epoch数等参数，使用early stop等技巧减少过拟合和遗忘现象。一般训练1~3个epoch、损失降到0.5~0.3以下就好。训练太多，训练集拟合得太厉害也不是好事。
除了在训练阶段尽量缓解灾难性遗忘问题，去弥补训练后已经发生的遗忘也是一种可取思路。以下是一些工程上可以选择的方法：
外部知识库/知识图谱/检索增强：实际上指望大模型记住各种各样琐碎的知识是十分困难的。相比之下，赋予大模型随时调用外部知识库是一种弥补知识缺陷的有效方法。
推理阶段的多专家模型：将不同主题的对话派发给不同的“专家”模型。尽管当前模型可能在SFT过程中丢失了相关信息，当使用对应的专家模型还是能很好地弥补这些能力的缺失。
拒绝识别模块：在用户进行指定范围外的对话时，拒绝识别模块将会触发，拒绝就此话题进行讨论，从而避免模型就不擅长的话题进行讨论。拒绝识别模块非常容易降低用户的使用体验，但是实际应用场景往往对对涉政、色情等敏感信息的拒绝识别有非常严格的要求。
拒绝识别模块可以设计为专门的小型分类器。另外，也可以在SFT数据中加入一些拒绝模板，使模型具备拒绝不安全对话的能力。

1.6 CoT

例子 9 ⭐你是如何构造CoT的？

1.7 多模态大模型

例子 10 ⭐你能列举几个常见的从视觉编码器的图像特征映射到大模型文本特征的方法吗？

例子 11 ⭐各种多模态融合模块的优缺点？ （注意）Q-Former容易破坏visual token之间的空间关系。

例子 12 ⭐如果让你从头开始训练一个多模态大模型，你会如何设计模型结构、训练流程和项目流程？

例子 13 ⭐对于多模态大模型，提高图像的分辨率是十分重要的。为什么现在的大模型往往使用如256x256这类低分辨率的图像，无法做到高分辨率呢？

例子 14 ⭐你观察到GPT4-V有哪些问题？为什么会存在这些问题？

2 自然语言处理

例子 15 ⭐⭐⭐⭐旋转位置编码相对于原本的绝对位置编码有何改进？

TODO

例子 16 🌙🌙手写Multi-Head Attention。

本题答案可参考：《手写Multi-Head Attention：从公式到代码实现》

例子 17 🌙🌙你知道PreNorm和PostNorm的区别吗？

3 计算机视觉相关问题

例子 23 为什么要对图像做预处理？

预处理将数据变换到统一的格式，方便模型学习；
通过提前提取有用的特征，裁剪出感兴趣区域来加快计算；

例子 24 ⭐ViT模型中是如何对位置信息进行编码的？

TODO

例子 25 ⭐请比较Transformer和CNN

TODO

4 深度学习相关问题

例子 26 ⭐在训练模型的过程中，我们经常遇到过拟合。有哪些常见的应对过拟合的方法？

数据层面：增加数据量、数据增强；
模型设计层面：Dropout、DropBlock、weight decay；
训练策略：迁移学习、部分参数微调、early stop、辅助任务、不确定性估计；
推理策略：test-time augmentation；

5 机器学习问题

例子 27 ⭐手写K-Means

被问到过一次。按照自己的理解实现出来，但是只通过了35%的测试用例。

⭐你知道softmax函数的上溢和下溢问题吗？如何解决这个问题。

TODO :::

例子 28 🌙特征存在共线性问题会有什么影响？应当如何应对。

TODO

例子 29 🌙如果特征维度很大而样本又少，应该怎么办？

TODO

例子 30 🌙🌙MSE和MAE分别作为损失函数会带来什么区别？

例子 31 🌙特征存在共线性问题会有什么影响？应当如何应对。

TODO

6 算法题

接下来简单记录一些面试过程中实际遇到的或其它面试经验推荐的题。

在面试过程中要求现场手写的算法题常常不会很难，但作答过程中要思路清晰，能够有效地与面试官沟通，尽量减少试错次数，一次通过。

答题之前记得问清楚数据规模，时间复杂度和空间复杂度需求。

⭐最长回文子串
⭐二叉树的最近公共祖先
⭐⭐两数之和变体：设A、B是两个有序数组，找出所有\(i, j\)满足A[i] + B[j] = k，要求常数空间复杂度，线性时间复杂度。
此题需要注意数组不是严格单调的，即可能连续出现若干个相同的数。编写双指针法时需要注意边界条件，避免漏掉一些解。
⭐⭐三数之和：由两数之和扩展而来的一道题。
⭐滑动窗口求最大值：要求\(O(n)\)时间复杂度。
⭐top k算法：写出\(O(n\log k)\)的基于堆的方法并不困难，但最好能进一步掌握基于快排的\(O(n)\)时间复杂度的解法。
🌙岛屿数量：实际上属于求连通域数量的算法，可用DFS/BFS/并查集方法解。
🌙反转每对括号间的子串：考察栈的用法。也可以不用栈来解。容易想到\(O(n^2)\)复杂度的算法，但实际也存在\(O(n)\)的解法。
🌙搜索选择排序数组：考察二分法。需要做题者注意到选择排序数组的特性。
🌙寻找两个正序数组的中位数（困难）：更一般的，可以推广为寻找两个正序数组的第k小的数。考察二分法。需要思考应该对哪个量做二分查找。
🌙NER的BIO形式标注转start，end形式（例子 38）：以命名实体识别（NER）任务为背景的简单算法题。
🌙马在棋盘上的概率：可以用动态规划的方法求解，时间复杂度为\(O(n^2k)\)，这里\(n\)为棋盘大小，\(k\)为步数。还可以想到本题所执行的动态规划步骤实际上是一种卷积，且每一步的卷积核都是相同的，因此本题可以用快速幂的方式进行优化。
🌙整数拆分：将整数\(n\geq 2\)拆分为任意个正整数的和，使其乘积最大。容易想到基于动态规划的解法，但不容易给出\(O(1)\)时间复杂度的，基于数学分析的解法。
- 问题延伸：如果题目改为将整数\(n\geq 2\)拆分为任意个正数的和，使其乘积最大。该如何分析？参考例子 39
⭐给定一个字符串和一个词典，问字符串能否由词典中的单词拼接而成。用DFS可解。可考虑引入缓存等策略进行优化。

7 开放性问题

例子 32 ⭐在个人技术成长方面，你有什么规划？

例子 33 ⭐为什么想要离职？

仅仅是解释前东家的缺点是不够的。每个公司有每个公司的缺点，不能保证下一家没有相同的问题。一般可以将问题解释为当前公司平台无法提供更好的发展，而现在在看的机会能补充这方面的不足。最好不要表现出自己是当前工作上遇到困难而离职的，而应尽量表现出自己的事业当前处于上升期，但由于某些原因（工作地点、待遇、发展方向、职业规划）而不得不离开。这时可以顺带说说自己有多么适合这个新岗位。重要的是表现出自己与新公司是一个互相成就的关系。

例子 34 ⭐请介绍一下过往最困难的一个项目。

例子 35 ⭐你当前采用的项目方案的亮点是什么？你对项目最重要的贡献是？

例子 36 ⭐是什么使你在项目中具有不可替代性？或者是什么使你具备比他人更高的价值？

8 总结

笔记的重要性：只学习不总结就容易忘。不做笔记不行啊。最好每次面试过后，立即将记录下来，时不时重新过一遍。

平时多练习，多刷题，保持手感。有的公司（例如Minimax）的算法测试会期望给出最优解，面试时即使把题目做出来了，也可以问一下需不需要继续改进，提一提能想到的改进点。

拿到Offer后，记得问以下重点问题。可以不直接问，但也需要间接地通过各种渠道去了解。要了解的包括但不限于：

绩效的考核方式，KPI的考核情况

有没有末位淘汰
有没有轮流背D绩效
绩效工资占縂工资比例

竞业协议

是否需要背竞业协议
竞业协议是否与期权等权利挂钩

一些经验和感想：

（不是绝对的）不论是体制内还是体制外，国企还是私企，只要在国内，就不要相信955的存在。一位HR可以毫无心里负担地告诉你它是955，但它也可以随时转变为996而不受到任何约束。同理，一家企业声称它是996，那么你可以大胆推测它实际上已经是9106了。在这一点上面，猎头可能比HR更不可信。有一个猎头给我推荐了一家香港的初创公司，告诉我这是一家WLB（Work-Life Balance）的公司，但是我和创始人聊天的时候，他却笑着告诉我“初创公司不加班，还有谁敢来呀”。另一个猎头给我推荐宁德时代，告诉我那个组加班不严重。我觉得都不可相信；
竞业协议是不公平的。如果你签下了竞业协议，公司就有权阻止你入职同行业内的任何公司，并在你离职后提供一些微小的补偿。但相反的，假如你主动离职去读博、考公，主动希望公司启动竞业协议，公司却可以选择不启动竞业。主动权总是掌握在公司手上。
一般来说，即使签订了协议，公司也不会舍得为一个初入职场的大头兵启动竞业。因此初入职场的同学不必过于担心这个问题。但不论如何，在签订新公司时还是要对竞业协议保持谨慎。某些公司，例如拼多多，有很大的概率启动竞业协议，并且在员工离职后派人调查其去向；

9 附录

9.1 例题

例子 37 ⭐两个硬币的后验概率

有两个硬币，一个硬币的两面都是正面；另一个是正常硬币：一面是正面，另一面是反面；

随机选取其中一枚，抛掷五次，都是正面。问这枚硬币是正常硬币的概率是？

解：设\(A=\text{抛掷五次硬币都是正面}\)，\(B={这是一枚正常硬币}\)

题目要求\(P(B|A)\)

\[ \begin{aligned} P(B|A) &= P(A|B) P(B) / P(A)\\ &= 0.5^5 \times 0.5 / P(A) \end{aligned} \] 其中 \[ \begin{aligned} P(A) &= P(A|B)P(B) + P(A|\neg B)P(\neg B) \\ &= 0.5^5 \times 0.5 + 1 \times 0.5 \\ \end{aligned} \] 所以 \[ \begin{aligned} P(B|A) &= 0.5^5 \times 0.5/ P(A) \\ &= \frac{0.5^5 \times 0.5} {0.5^5\times 0.5 + 1\times 0.5}\\ &= \frac{1}{1 + 32}\\ &= \frac{1}{33} \end{aligned} \]

例子 38 🌙NER标注格式转换

描述: 在命名实体识别(NER)任务中,BIO标注方式是常用的标注格式之一。但在某些应用场景下,我们可能需要将BIO格式转换为start,end形式的标注。

请你实现一个Python函数,将BIO格式的NER标注转换为start,end形式。

函数输入:

tokens: 一个字符串列表,表示分词后的句子
bio_tags: 一个字符串列表,表示对应的BIO标注

函数输出: 一个字典列表,每个字典包含以下键:

‘entity’: 实体文本
‘start’: 实体开始位置
‘end’: 实体结束位置
‘type’: 实体类型

示例:
输入:

tokens = ['John', 'lives', 'in', 'New', 'York', '.']
bio_tags = ['B-PER', 'O', 'O', 'B-LOC', 'I-LOC', 'O']

输出:

[
    {'entity': 'John', 'start': 0, 'end': 1, 'type': 'PER'},
    {'entity': 'New York', 'start': 3, 'end': 5, 'type': 'LOC'}
]

请实现函数bio_to_span(tokens, bio_tags)来完成这个转换任务。

提示

实体的end索引应该是实体最后一个词的索引+1
对于单个词的实体,start和end的差值应该是1
需要正确处理连续的多个词组成的实体

def bio_to_span(tokens, bio_tags):
    tokens.append('<eos>')
    bio_tags.append('O')
    start = 0 
    end = 0
    entity = []
    typ = None 
    ret = []
    for i, (t, b) in enumerate(zip(tokens, bio_tags)):
        if b.startswith('B-'):
            start = i 
            entity = [t]
            typ = b[2:]
        elif b.startswith('I-'):
            assert typ == b[2:], '{} != {}'.format(typ, b[2:])
        elif b == 'O':
            if len(entity):
                end = i 
                ret.append({
                    'entity': ''.join(tokens[start:end]),
                    'start': start,
                    'end': end,
                    'type': typ 
                })
                entity.clear()
        else:
            raise Exception("Invalid BIO label: {}".format(b))
    return ret

接下来用一些测试用例检查给出的算法的正确性。在请求面试官检查之前，先自己编写一些测试用例是一个好习惯。

查看测试用例

test_cases = [
    # case 1
    {
        "input": (["我", "爱", "北京", "天安门"], ["O", "O", "B-LOC", "I-LOC"]),
        "output": [{'entity': '北京天安门', 'type': 'LOC', 'start': 2, 'end': 4}]
    },
    # case 2
    {
        "input": (["他", "是", "一位", "来自", "中国", "的", "医生", "，", "名叫", "张伟"], 
                  ["O", "O", "O", "O", "B-LOC", "O", "B-PROF", "O", "O", "B-PER"]),
        "output": [{'entity': '中国', 'type': 'LOC', 'start': 4, 'end': 5}, 
                   {'entity': '医生', 'type': 'PROF', 'start': 6, 'end': 7}, 
                   {'entity': '张伟', 'type': 'PER', 'start': 9, 'end': 10}]
    },
    # case 3 (空实体)
    {
        "input": (["今天", "天气", "真好"], ["O", "O", "O"]),
        "output": []
    },
    # case 4 
    {
        'input': (
            ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'], 
            ['O', 'B-PER', 'I-PER', 'O', 'B-ORG', 'I-ORG', 'I-ORG', 'O', 'B-LOC', 'O']
        ),
        'output': [{'entity': 'bc', 'type': 'PER', 'start': 1, 'end': 3},
            {'entity': 'efg', 'type': 'ORG', 'start': 4, 'end': 7},
            {'entity': 'i', 'type': 'LOC', 'start': 8, 'end': 9}]
    },
    # case 5 (空序列)
    {
        'input': (
            [], []
        ),
        'output': []
    },
    # case 6 (只有O标签)
    {
        'input': (['a', 'b', 'c'], ['O', 'O', 'O']),
        'output': []
    },
    # case 7 
    {
        'input': (
            ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'],
            ['B-PER', 'I-PER', 'O', 'B-PER', 'O', 'B-PER', 'I-PER', 'I-PER']
        ),
        'output': [{'entity': 'ab', 'type': 'PER', 'start': 0, 'end': 2},
            {'entity': 'd', 'type': 'PER', 'start': 3, 'end': 4},
            {'entity': 'fgh', 'type': 'PER', 'start': 5, 'end': 8}]
    }
]

for test_case in test_cases: 
    out = bio_to_span(*test_case['input'])
    assert len(out) == len(test_case['output']), 'Length inqueal! {} != {}'.format(out, test_case['output'])
    for o1, o2 in zip(out, test_case['output']):
        for k in o2.keys():
            assert o1[k] == o2[k], '{} != {}'.format(o1, o2)

print('所有测试用例均通过。')

所有测试用例均通过。

例子 39 🌙如何将整数\(n\geq 2\)拆分为任意个正数的和，使其乘积最大？

设\(n\)被拆分为\(k\)个数，容易证明每个数都为\(n/k\)时乘积最大。（先证明\(k=2\)时，\(n\)应该被拆为\(\frac{n}{2} + \frac{n}{2}\)；然后通过构造条件满足数学归纳法来证明。）

加下来，设将\(n\)拆为\(k\)份，可知其乘积应为\(f(n, k) = \left(\frac{n}{k}\right)^k\). 先不考虑\(k\)应为正整数的问题，令\(k \in \mathbb R^+\). \(f(n, k)\)是一个连续函数。

\[ \begin{aligned} f(n, k) &= e^{\ln \left(\frac{n}{k}\right)^k} \\ &= e^{k\ln n - k \ln k } \end{aligned} \]

\[ \begin{aligned} \frac{\partial f}{\partial k} &= e^{k\ln n - k \ln k }\cdot (\ln n - \ln k - 1) \end{aligned} \]

\[ \begin{aligned} \frac{\partial f}{\partial k} = 0 & \Rightarrow \ln n - \ln k - 1 = 0\\ & \Rightarrow k = \frac{n}{e} \end{aligned} \]

容易看出\(\frac{\partial f}{\partial k}\)随著\(k\)的增加而单调上升。因此\(k=\frac{n}{e}\)是函数的极大值点。但是\(k\)需要是整数，因此我们可以考虑取\(k=\lceil \frac{n}{e} \rceil\)或\(k=\lfloor \frac{n}{e}\rfloor\)，取其中使乘积最大的\(k\)即可。

例子 40 求斐波那契数列1、1、2、3、5、8……的通项公式。

当\(n\geq 3\)时，有\(F_{n} = F_{n-1} + F_{n-2}\). 写成矩阵形式为 \[ \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1}\\ F_{n-2} \end{pmatrix} \]

于是可得 \[ \begin{aligned} \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} & = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1}\\ F_{n-2} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F_{n-2}\\ F_{n-3} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} 1\\ 1 \end{pmatrix} \\ &=\mathbf A^{n-2} \begin{pmatrix} 1\\ 1 \end{pmatrix} \end{aligned} \]

\(\mathbf A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\)的特征值为\(\lambda_1 = \frac{1 - \sqrt 5}{2}\), \(\lambda_2 = \frac{1 + \sqrt 5}{2}\)，对应的特征向量为 \(\vec x_1 = (\frac{1 - \sqrt 5}{2}, 1)^T\)， \(\vec x_2 = (\frac{1 + \sqrt 5}{2}, 1)^T\)

特征值的求解方法

设\(\lambda\)是\(\mathbf A\)的特征值，\(\vec x\)是对应的特征向量，则有 \[ \mathbf A \vec x = \lambda \vec x \]

从而得到\(\lambda \mathbf E - \mathbf A\)的秩为0.

\[ \left| \begin{matrix} \lambda - 1 & -1 \\ -1 & \lambda \end{matrix} \right| = 0 \Rightarrow \lambda ^2 - \lambda - 1 = 0 \] 从而得到两个解：\(\lambda_1 = \frac{1 - \sqrt 5}{2}\), \(\lambda_2 = \frac{1 + \sqrt 5}{2}\)

将\(\lambda_1, \lambda_2\)的值代入到\((\lambda \mathbf E - \mathbf A)\vec x = \vec 0\)可解得两个特征向量 \[ \vec x_1 = (\frac{1 - \sqrt 5}{2}, 1)^T \] 和 \[ \vec x_2 = (\frac{1 + \sqrt 5}{2}, 1)^T \]

因此\(\mathbf A\)是可对角化的，即令 \[ \mathbf P = \begin{pmatrix} \vec x_1, \vec x_2 \end{pmatrix} ,\]

则有\(\mathbf P^{-1} \mathbf A \mathbf P = \mathbf\Lambda=\begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\) 因此\(\mathbf A^{n-2}=(\mathbf P^{-1} \mathbf\Lambda \mathbf P)^{n-2}=\mathbf P \mathbf\Lambda^{n-2} \mathbf P^{-1}\)

\[ \begin{aligned} \mathbf P \mathbf\Lambda^{n-2} \mathbf P^{-1} \begin{pmatrix} 1 \\ 1 \end{pmatrix} &= \frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}^{n-2} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^{n-2} & 0 \\ 0 & \lambda_2^{n-2} \end{pmatrix} \begin{pmatrix} \lambda_1 \\ \lambda_2 \end{pmatrix}\\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^{n-1} \\ \lambda_2^{n-1} \end{pmatrix}\\ &=\frac{1}{\lambda_1 - \lambda_2} \begin{pmatrix} \lambda_1^n + \lambda_2^n\\ \lambda_1^{n-1}+\lambda_2^{n-1} \end{pmatrix}\\ \end{aligned} \] 即通项公式为\(F_n=\frac{1}{\lambda_1 - \lambda_2}(\lambda_1^n + \lambda_2^n)\)，代入特征值得到\(F_n=\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1 - \sqrt 5}{2})^n)\)

参考资料：斐波那契数列通项公式求解

参考

[1]

ZHOU C, LIU P, XU P, 等. LIMA: Less Is More for Alignment[J]. 2023.

[2]

OUYANG L, WU J, JIANG X, 等. Training language models to follow instructions with human feedback[J]. ArXiv, 2022, abs/2203.02155.

[3]

RANZATO M, CHOPRA S, AULI M, 等. Sequence Level Training with Recurrent Neural Networks[J]. CoRR, 2015, abs/1511.06732.

[4]

HONG J, LEE N, THORNE J. ORPO: Monolithic Preference Optimization without Reference Model[J]. 2024.

[5]

TOUVRON H, MARTIN L, STONE K, 等. Llama 2: Open Foundation and Fine-Tuned Chat Models[J].

[6]

LIGHTMAN H, KOSARAJU V, BURDA Y, 等. Let’s Verify Step by Step[J]. 2023.

[7]

MENG Y, XIA M, CHEN D. SimPO: Simple Preference Optimization with a Reference-Free Reward[J]. 2024.

[8]

DOU S, ZHOU E, LIU Y, 等. LoRAMoE: Alleviate World Knowledge Forgetting in Large Language Models via MoE-Style Plugin[J]. 2024.