這篇文章記錄我自畢業以來,為大模型算法崗位面試準備的一些知識。這篇筆記主要基於個人實際經歷,希望可供後來者參考。
本人水平有限,文章内容不一定正確。本文的内容也難稱完整,會持續保持更新。
算法基礎知識
交叉熵、熵和KL散度之間的關係是什麼?
設\(P\)代表實際數據的分佈,\(Q\)是模型預測的分佈,那麼,
熵的定義: \[ H (P) = -\sum_x P(x) \log P(x) \] 交叉熵: \[ H_\text{CE}(P, Q) = -\sum_x P(x) \log {Q(x)} \]
KL散度的定義: \[ D_\text{KL}(P, Q) = \sum_x P(x) \log {P(x) \over Q(x)} \]
\[ H_\text{CE}(P, Q) = D_\text{KL}(P, Q) + H(P) \]
什麼時候優化KL散度等於優化交叉熵?
如前所述,如果數據分佈\(H(P)\)為常數(即不隨優化過程改變),那麼優化KL散度等價於優化交叉熵。
反過來,如果\(P\)隨著優化過程變化,那麼兩個優化目標就不能等價了。
手寫K-Means
TODO
如果特徵維度很大而樣本又少,應該怎麽辦?
TODO
MSE和MAE分別作爲損失函數會帶來什麽區別?
特徵存在共綫性問題會有什麽影響?應當如何應對。
TODO
在訓練模型的過程中,我們經常遇到過擬合。有哪些常見的應對過擬合的方法?
- 數據層面:增加數據量、數據增強;
- 模型設計層面:Dropout、DropBlock、weight decay;
- 訓練策略:遷移學習、部分參數微調、early stop、輔助任務、不確定性估計;
- 推理策略:test-time augmentation;
LLM數據工程
数据去重为什么重要?有哪些数据去重的方法?
- 提升训练效率:重复数据让模型浪费算力做无用功,拖慢收敛速度。
- 防止过拟合与记忆:模型会“背下”重复样本,而不是学习泛化规律,导致测试效果差,甚至引发隐私泄露。
- 缓解长尾问题:高频数据重复会加剧数据不平衡,让模型忽视低频但重要的知识。
常用的去重方法:
- 精确去重:直接比对字符串或字节,移除完全相同的样本。常用哈希指纹(如MD5)来加速。
- 近似去重(模糊去重):用于发现内容高度相似但不完全相同的文本。经典算法是MinHash + LSH。對於小規模數據,可以使用編輯距離去重。
偏好對齊方法為什麼需要准备成對的訓練數據?能不能只給正面數據,不提供負面數據?
我們從以下幾點分析這個問題。
1. 數據集中能不能只包含正面數據或負面數據?如果只給正面數據,那麼偏好對齊任務便退化為SFT任務。Jiwoo Hong等人(Hong, Lee, and Thorne 2024)指出,隨著SFT過程的進行,雖然模型產生訓練文本的概率會上升,但被拒絕文本的概率也隨之上升。這表明只給出正面數據(只做SFT)是無法作偏好微調的。類似的,可以推測如果只降低負面數據的出現概率,那正面文本的出現概率也會下降。
2. 為什麼PPO使用的是成對的正負樣本,而不是為每一個回復給出一個準確的分值? - 標註噪聲:從標註規範制定的角度看,個例的打分結果會帶有噪聲,而同時進行成對的數據標註,有助於減少標註噪聲。 - 從reward model學習的角度看,reward model學習目標是正確地評估不同回復之間的相對優劣,而不是模型回復的絕對評分,因此標註過程中分數不是必要的。 - 評分的粒度問題:例如,有兩個模型回復都打了3分(5分制),那這兩個回復間就不能再分出優劣了嗎?即使兩個回復都打了同樣的分數,它們之間的差異也可能提供有價值的信息。 以上討論說明了為什麼PPO為什麼採用了成對正負樣本進行訓練。但是在項目實踐中,我也經歷過需要標註員標註具體分數的情況。在任務規範清晰、打分標準容易制定的前提下,規定具體的評分標準有好處:
- 詳細、嚴謹的規範有助於減少數據中的噪聲;
- 分值間的相對差異大小可以為訓練過程提供細化的指導。例如,可參考LLaMa 2(Touvron et al., n.d.)在reward model的損失中加入一個margin component,要求正負樣本相似時reward model的打分可以不用差距太大,反之則要求二者的打分要有顯著差異。
- 最後,即使是在標註員已經提供了具體分值的情況下,我們仍要求標註員對所有回復進行排序,即使有些模型回復的分值是相同的。不同標註員的排序一致性是評價數據質量的一個重要指標。
3. 訓練成本。 從訓練成本的角度來看,成對的偏好訓練數據更容易大規模收集(例如可以在用戶點踩的時候立即給出另一個備選回復),標註成本也更低。
预训练/後訓練/偏好對齊/强化学习
LoRA訓練的時候,如何選擇凍結的層?
LoRA本身只插入低秩適配器(Adapter)矩陣,原始權重是凍結的,因此問題的關鍵不在於「凍結哪些層」,而在於「對哪些層應用LoRA適配器」。常見的選擇策略如下:
- 只對Attention的Q和V矩陣應用LoRA:這是LoRA原始論文的做法,在參數量和效果之間取得平衡。Q和V的調整對模型行為影響較大,足以適應下游任務。
- 對所有Attention層(Q/K/V/O)應用LoRA:當下游任務與預訓練分佈差異較大時(如代碼生成、數學推理),對所有Attention投影矩陣都應用LoRA可以提升適配能力。
- 對FFN層也應用LoRA:FFN層存儲了大量知識,在需要注入新知識或改變模型行為模式時(如長CoT訓練),對FFN層也應用LoRA有幫助。
- 根據層深度選擇:底層(靠近輸入)捕獲通用語法/句法特徵,高層(靠近輸出)更偏向語義和任務相關特徵。因此:
- 若任務與原始領域差異不大,可只對高層應用LoRA;
- 若任務需要大幅改變模型行為,建議對所有層均應用LoRA。
- 根據參數重要性選擇:可計算各層權重的Fisher Information或梯度幅值,選擇重要性高的層應用LoRA,減少冗餘參數。
實踐中,最常見的配置是對所有Attention的Q和V矩陣應用LoRA(rank=8~64),再根據任務複雜度決定是否擴展到其他層。
PPO的critic model是做什麼的,為什麼需要critic model?
Critic model(也稱value model)在PPO中負責估計狀態價值函數 \(V(s)\),即給定當前狀態(已生成的token序列),預測從該狀態出發能獲得的期望累積獎勵。
為什麼需要critic model?
- 降低梯度方差(Variance Reduction):PPO使用advantage函數 \(A(s,a) = Q(s,a) - V(s)\) 來衡量某個動作相對於平均水平的優勢。直接使用reward作為信號,梯度方差極大,訓練不穩定。減去baseline \(V(s)\) 後,方差顯著降低。
- 提供逐位置的學習信號:reward model只在完整序列結束時給出一個獎勵(稀疏獎勵),而critic model可以在每個token位置估計未來回報,使得actor model在每個生成步驟都能獲得學習信號。
- GAE(Generalized Advantage Estimation)的依賴:PPO通常使用GAE來計算advantage,GAE需要在每個時間步都有value預測,以平衡bias和variance的trade-off。
為什麼不能直接用reward model代替critic model?
Reward model給出的是完整序列的獎勵評分,而critic model給出的是當前狀態的期望回報。二者角色不同:reward model是環境提供的評分信號,critic model是對該評分信號的擬合,用於降低方差。如果去掉critic model,PPO就退化為REINFORCE算法,方差會大幅增加,訓練難以收斂。
為什麼GRPO可以成功去除PPO的critic model?
核心改進在於用group內的相對優勢替代critic model的value估計。
具體來說:
Group-based advantage估計:GRPO對同一個prompt採樣多個回復(一個group),然後用group內各回復的reward相對於group均值的標準化分數作為advantage: \[A_i = \frac{r_i - \text{mean}(r_1,\dots,r_G)}{\text{std}(r_1,\dots,r_G)}\] 這本質上是用group內的其他樣本作為baseline,替代了critic model的value估計。
為什麼可以去掉critic model?
- Critic model的作用是提供baseline以降低方差。GRPO利用同一prompt下多個採樣結果的reward分佈來構造baseline,同樣能達到降低方差的效果。
- 省去critic model意味著減少了約一半的訓練參數(value model通常與policy model規模相當),顯著降低了顯存和計算開銷。
- 避免了critic model訓練不穩定或擬合不準確帶來的額外噪聲。
GRPO的侷限:GRPO依賴於group內樣本的多樣性。如果group內所有回復的reward相近(方差小),則advantage信號微弱,訓練效率降低。這也是後續DAPO提出Dynamic Sampling(丟棄reward方差為0的group)的原因。
GRPO方法在后续其它的工作中得到哪些改进?
DAPO:
- Clip higher:DAPO观察到训练过程中,actor model的entropy在不断降低,导致reward趋同且探索不足,故提出修改PPO-Clip策略,允許clip的下界和上界設置不同的值。通過提高上界,可以鼓勵探索。
- 移除KL散度。DAPO认为在长CoT训练的过程中,模型参数显著偏离原模型是寻常的,而且移除KL散度项不会严重影响效果;
- Dynamic Sampling:GRPO需要group內有reward差異,否則當前組內數據就不會產生梯度。如果一組rollout沒有reward variance,DAPO會直接將其丟棄。
- Token-Level Loss:原GRPO會進行sequence-level的loss平均,這會導致長回復的sample中,每個token的權重變小。DAPO採取token級別的平均,有利於長思維鏈學習。
- Overlong Reward Shaping:GRPO通常採用truncation和簡單的超長懲罰。DAPO提出length-aware penaly,在超長時給予線性的懲罰(從0線性降低到-1)。
GSPO:
- 序列級重要性採樣:GRPO逐token算重要性權重,長序列方差高,噪聲累積;GSPO用整個序列的聯合概率比(幾何平均),所有token等權重;
- 序列級裁剪與獎勵:裁剪和獎勵分配都改為全序列級別;
詳細介紹Clip higher這個技巧。
DAPO采用的目標函數具備這樣的形式: \[ \begin{aligned} \mathcal J(\mathbf \theta) &= \mathbb E \left[ \frac{1}{\sum_{i=1}^G|o_i|} \sum_{i=1}^G \sum_{t=1}^{|o_i|} \min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, clip( r_{i, t}(\mathbf \theta), 1 - \epsilon_\text{low}, 1 + \epsilon_\text{high} )\hat A_{i, t} ) \right]\\ \end{aligned} \] 我們分情況討論\(\min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, clip( r_{i, t}(\mathbf \theta), 1 - \epsilon_\text{low}, 1 + \epsilon_\text{high} )\hat A_{i, t} )\)這個核心算式:
- 如果\(r_{i, t}(\theta)\)處於上下截斷界限之間,公式簡化為\(r_{i, t}(\mathbf \theta)\hat A_{i, t}\)這樣的簡單情形,我們不做更多討論;
- 如果\(r_{i, t}(\theta)\)被截斷為\(1 - \epsilon_\text{low}\),代表此時policy model比reference model更排斥使用當前action,而且程度相差過大。公式變成\(\min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, (1 - \epsilon_\text{low})\hat A_{i, t})\),此時如果\(\hat A_{i, t}<0\),\(\theta\)的梯度就被截斷,阻止policy model進一步降低當前action的輸出概率;
- 如果\(r_{i, t}(\theta)\)被截斷為\(1 + \epsilon_\text{high}\),代表此時policy model比reference model更偏好使用當前action,且程度相差過大。公式變成\(\min(r_{i, t}(\mathbf \theta) \hat A_{i, t}, (1 + \epsilon_\text{high})\hat A_{i, t})\),此時如果\(\hat A_{i, t} > 0\),\(\theta\)的梯度就消失,阻止policy model進一步增大對當前action的偏好;
DAPO將\(\epsilon_\text{low}\)和\(\epsilon_\text{high}\)設置為不同的值,並適當提高\(\epsilon_\text{high}\),從而允許模型在\(\hat A_{i, t}\)為正的時候,減少對提高“exploitation token”概率的限制,從而鼓勵exploitation。
有時關閉DAPO的dynamic sampling,效果反而更好。為什麼?
因為DAPO的重新採樣改變了數據分佈。例如模型已經高概率答對了某個問題,但dynamic sampling會重新採樣,直到出現負例,導致模型過度訓練。
為什麼要做偏好對齊?只做SFT不行嗎?
只做SFT不做偏好對齊經常會導致一些問題。
1. 從訓練目標來看:預訓練、SFT任務本質上都是要求模型預測下一個token,而這與具体业务场景的目標——例如”以安全和有益的方式遵循人類指令”——是不一致的(Ouyang et al. 2022)。這種訓練目標的不對齊導致模型容易產生不安全、不忠實或有害的信息。 2. 曝光偏差問題:在預訓練、SFT階段,模型只是在訓練數據的分佈上進行下一個token的預測。一些基於強化學習的偏好對齊任務提供了一種在模型自身預測分佈上進行訓練的方法(Ranzato et al. 2015),緩解了曝光偏差問題。
為什麼SFT後的大模型會有幻覺?
模型的幻覺是指模型誤認為自己能感知到一些實際感知不到的東西,或者以非常肯定的態度給出錯誤信息。例如,問”現在是幾點鐘?“,模型在不接入外部插件的情況下回答”現在是下午三點”,這便屬於模型幻覺。
預訓練、SFT任務本質上都是要求模型預測下一個token,而這與AI應用的目標——“以安全和有益的方式遵循人類指令”是不一致的(Ouyang et al. 2022)。這種訓練目標的不對齊導致模型容易產生不安全、不忠實或有害的信息,例如導致模型幻覺。
什麼是對齊稅?如何減少對齊稅?
在經過偏好對齊後,模型的通用能力可能下降,比如可能出現更多地生成不適當的”拒絕回答”現象,這一問題被稱為”對齊稅”。 那麼,我們要如何減少”對齊稅”,讓經過RLHF的模型盡量保持RLHF之前的能力呢?
- 訓練時不要偏離reference太多:在PPO算法中,除了reward model、policy model,還有一個reference model(同樣由SFT後的模型初始化得到)。PPO算法會限制policy model不過分偏離reference model。這可以視為一種限制policy model能力偏移的機制。(儘管reference model的作用不止於此。)InstructGPT(Ouyang et al. 2022)指出通過在PPO更新步驟中混入增加預訓練分佈的對數似然可以大幅降低模型的能力衰退。
- 強化學習/偏好對齊不一定帶來對齊稅:儘管多數研究未能消除偏好對齊對模型性能的損害,但也存在證據表明負對齊稅是可能實現的。OpenAI對大模型數學答題能力的一項研究(Lightman et al. 2023)顯示以合適的reward model設計為前提,模型的數學回答正確率能夠提升。儘管這項工作是針對數學任務進行的,但這一結論有可能可以推廣到一般的文本生成任務。
SFT過程中會出現災難性遺忘嗎?如何應對災難性遺忘?
一般我們在項目中會通過SFT來獲得一個面向專門領域和特定任務的模型,例如心理診療模型、法律咨詢模型、醫療建議模型、論文修改模型。SFT的過程中大模型很容易忘記對象任務以外的知識,損失一部分通用能力。就目前的技術來看,災難性遺忘問題是不可避免的,但可以通過以下方法緩解:
- 限制偏離基模的程度:使用基模作為教師模型,引入KL散度約束,使模型的token分佈不要過於偏離預訓練模型。
- 數據重放:一種直接的做法是在SFT階段隨機地採樣一部分預訓練數據。(經驗上看,預訓練數據的採樣比例在SFT階段會起到比較大的影響。)
- 部分參數微調:與全量微調不同,可考慮採用LoRA、Soft Prompt等方法,通過調控參與訓練的參數量來控制SFT的擬合程度。(個人實踐中還是全量微調比較多。)
- 其它訓練參數的調整:可以嘗試調整學習率、epoch數等參數,使用early stop等技巧減少過擬合和遺忘現象。一般訓練1到3個epoch、損失降到0.5~0.3以下就好。訓練太多,訓練集擬合得太厲害也不是好事。
除了在訓練階段盡量緩解災難性遺忘問題,去彌補訓練後已經發生的遺忘也是一種可取思路。以下是一些工程上可以選擇的方法:
- 外部知識庫/知識圖譜/檢索增強:實際上指望大模型記住各種各樣瑣碎的知識是十分困難的。相比之下,賦予大模型隨時調用外部知識庫是一種彌補知識缺陷的有效方法。
- 一些相關的學術工作:LoRAMoE(Dou et al. 2024)通過凍結主幹網絡,迫使LoRA利用一部分世界知識來緩解災難性遺忘。
當前RLHF的流程有什麼值得優化的地方?
這是一個開放性問題。言之有理地回答即可。
個人認為可以討論的點:
- 更細粒度的reward:如Let’s Verify Step by Step(Lightman et al. 2023)一文指出的那樣,偏好對齊可有更細粒度的標註,給出更準確的reward反饋。現在普遍常見的偏好數據只針對完整的回答給出標註,而不是針對每一個句子給出標註。相比於標註整個回答的偏好,僅標註出第一個有問題的句子/步驟不會增加更多的標註代價,但能夠提升reward信號的精細程度。這樣的細粒度偏好數據是目前比較少見的,有待建設;
- BT模型的優化和精細化:大多數偏好對齊方法採用了BT模型。BT模型要求reward model拉開正負樣本的得分差距,但並沒有考慮到正負樣本間差異以及偏好程度差異的強弱問題。直覺上,對於回復相似,偏好差異不明顯的情況,應該給與比較低的權重;對於回復差異大,偏好對比明顯的情況,應該給與比較高的權重。一些工作(Touvron et al., n.d.; Meng, Xia, and Chen 2024)嘗試了人為設置規則或調整超參來調整BT model的margin,但也許還有自適應地調整BT model的margin且取得更好對齊效果的方法存在。
旋轉位置編碼相對於原本的絕對位置編碼有何改進?
TODO
爲什麽Transformer模型要使用LayerNorm而不是BatchNorm。
TODO
介紹RMSNorm。
觀察到LayerNorm的成功在於縮放的穩定性,而中心化操作是可有可無的。故RMSNorm選擇只進行縮放,去除了中心化操作,減少了計算開銷;
class RMSNorm(nn.Module):
def __init__(self, dim: int, eps: float = 1e-6):
super().__init__()
self.eps = eps
# 可學習的縮放參數 Gamma,初始化為全 1
self.weight = nn.Parameter(torch.ones(dim))
def forward(self, x: torch.Tensor) -> torch.Tensor:
# x 的形狀通常是 (batch_size, seq_len, hidden_size)
# 1. 計算平方後的平均值,保留最後一個維度 (keepdim=True)
variance = x.pow(2).mean(-1, keepdim=True)
# 2. 計算 1 / RMS(x)
# 使用 torch.rsqrt(t) 相當於 1 / torch.sqrt(t),計算速度更快
rsqrt = torch.rsqrt(variance + self.eps)
# 3. 歸一化並乘上可學習參數
return x * rsqrt * self.weight請介紹幾種你熟悉的tokenization方法。
TODO
Encoder-Decoder結構、Prefix LM和Causal LM有什麼不同?
T5論文的Figure 4很好地展示了三者的不同。 Encoder-Decoder結構下,Encoder的輸入token間是兩兩互相可見的,Decoder的attention mask則是單向可見的。
Prefix LM和Causal LM的結構相近,區別是Prefix LM中,前綴文本內的token是兩兩互相可見的,前綴文本後的token是單向可見的;而Causal LM中所有token都是單向可見的。
Prefix LM和Encoder-Decoder相比是類似的,都允許一部分token之間兩兩完全可見,但Prefix LM好比是實現了Encoder和Decoder的參數共享,減少了參數量。
當下Causal LM是被大模型廣泛採用的架構。雖然Encoder-Decoder和Prefix LM的雙向注意力理論上有優勢,但仍然被大模型領域所”淘汰”。這就引出了另一個問題,“為什麼大模型都採用Causal LM結構”
為什麼大模型都採用Causal LM結構?
- KV-Cache優化:Encoder-Decoder和Prefix LM都不易採用KV-Cache優化,而支持KV-Cache的Causal LM對推理加速更友好;
- 訓練效率:Encoder-Decoder架構模型的Pipeline Parallel難以優化。即使模型架構能帶來理論上的性能優勢,但是卻帶來昂貴的訓練代價的話,那麼這種模型結構就會輸給那些更能充分利用算力的模型;
- 軌跡依賴:OpenAI使用Causal LM成功實現了GPT系列大模型,這使得後來者都更傾向於採用相近的配置進行實驗。
Qwen 3.5有哪些重要的優化點?
- 混合注意力機制:Gated Delta Network + 標準注意力。其中75%的層採用了混合注意力;
- 極致稀疏的MoE架構,極低的激活比。397B激活17B,35B激活3B;
- 原生多模態+early fusion,使用視覺token,而不是文本模型+外掛視覺;
- 原生多token預測支持
講講MOE的原理,爲什麽MOE的參數量大但計算量不大?
核心思想是將FFN層替換爲N個專家網絡+門控路由器,每個token只路由到Top-k個專家(通常K=1或者2),這就實現了控制計算量,但增大參數量。
路由的計算: \[ g(x) = \text{softmax}(W_g \cdot x) \] 根據上式的結果選擇Top-K個專家,加權混合。
(DeepSeek-V3引入共享專家,共享專家一定會被激活,負責通用知識,路由專家由Top-K決定是否激活,負責領域知識。)
MOE的負載均衡怎麽做?
爲了避免訓練時路由器總是把token分給少數專家,引入Aux Loss: \[ L_\text{aux} = \alpha \cdot N \cdot \sum_{i=1}^N f_i \cdot p_i \] 其中\(f_i\)是專家\(i\)被選中的token比例,\(p_i\)是專家的門控概率。
專家被均匀分配時,上式取得最小值,最小值為\(1\)。
爲什麽不是\(p_i * p_i\),而是\(f_i * p_i\)呢? 因爲MOE使用Top-K選擇專家,因此存在\(p_i\)比較小(只是略大於沒有選中的專家),但是\(f_i\)很大的情況。因此需要結合實際頻率\(f_i\)和預測的權重\(p_i\).
至於\(f_i * f_i\)肯定是不行的,因爲\(f_i\)不可導。
爲什麽MOE使用Top-K而不是隨機采樣呢?
- 隨機采樣可能會導致專家“同質化”,因爲每個專家都有概率在不應該被路由的時候被路由,不得不學習一些通用知識;
- 隨機性會給并行化的訓練工程帶來一些麻煩。
MOE路由是batch維度的還是token維度的?
- Batch維度:同一batch内所有token走同一個專家,引入了batch内的互相干擾,不合理。
- Token維度:合理,但是實現複雜,需要All-to-All通信。例如,先將
(batch_size, seq_len, hidden_dim)的矩陣展平為(batch_size * seq_len, hidden_dim),即不考慮batch的概念,然後分別計算每個token的去向,將輸入送到對應的計算設備上。
OPD (On-Policy Distillation)中,KL散度如何設計?
正向KL: \[ D_\text{KL}(P_\text{base}\Vert P_\theta) = \sum_x P_\text{base}(x)\log \frac{P_\text{base}(x)}{P_\theta(x)} \]
- 特性:如果教師在某個token上的概率很高,那麼學生必須在這個token上分配概率,否則KL散度會爆炸,導致懲罰極大
- 導向:學生會試圖“包住”教師的行為
- 缺點:小模型很難“包住”或者模仿大模型,導致訓練質量差。
逆向KL: \[ D_\text{KL} (P_\theta \Vert P_\text{base}) = \sum_x P_\theta(x) \log\frac{ P_\theta(x) }{ P_\text{base}(x) } \] 這是OPD最常採用的預設。
- 特性:如果教師分佈在某處為0,那麼學生在這個點的概率也需要趨近。相反,如果教師有若干個候選行為,學生只需要學會其中的一個模式;
- 導向:學生模型會表現得保守但精準,只說自己有把握,教師認可的話;
- 缺點:多樣性崩塌,同質化,Pass@k下滑;
目前前沿方法會採用自適應散度,在高熵、高不確定的情況下切到正向KL,鼓勵探索;在教師確定性強的情況下使用逆向KL收斂精度。
SFT和RL對基座大模型的作用和影響有什麼區別?
- SFT:
- 作用:通過提供特定格式、特定任務的數據,使其適應下游任務
- 影響:SFT傾向於讓模型記憶訓練數據,模型難以泛化到分佈外的數據;但是SFT的訓練有助於穩定模型的輸出格式,使得後續的RL可以穩定進行
- RL:
- 作用:對齊特定的人類偏好,或者通過最大化設計的reward來解決某些類型的任務;
- 影響:展現出較強的泛化能力;在多模態任務中也能提升模型潛在的視覺識別能力;
類 Transformer 模型計算量(FLOPs)精準推導
在評估 Transformer 模型的計算複雜度時,通常以 FLOPs(Floating Point Operations,浮點運算次數) 作為衡量指標。將矩陣乘法中的一次「乘加操作(Multiply-Accumulate)」計為 2 個 FLOPs(1 次乘法 + 1 次加法)。
以下為單個 Transformer Block(層)在一次前向傳播(Forward Pass)中,處理長度為 \(n\) 的序列時的計算量推導。推導使用如下符號:
- \(n\):序列長度(Sequence Length / Token 數)
- \(d\):模型隱藏層維度(Hidden Size / \(d_{model}\))
- \(m\):FFN(前饋網路)的中間層維度(Intermediate Size)
- \(L\):模型的總層數(Layers)
一個標準的 Transformer 層主要由兩部分組成:自注意力機制(Self-Attention) 與 前饋網路(FFN)。
自注意力的計算可以拆解為以下四個主要矩陣運算步驟:
- Q, K, V 投影矩陣(Projection)
- 將輸入的張量 \([n, d]\) 分別乘以 \(W_Q, W_K, W_V\)(三個權重矩陣大小皆為 \([d, d]\))。
- 計算量:\(3 \times (2 \times n \times d \times d) = 6nd^2\)
- 注意力分數計算(\(QK^T\))
- 矩陣乘法:\([n, d] \times [d, n] \rightarrow [n, n]\)。
- 計算量:\(2 \times n \times d \times n = 2n^2d\)
- 權重與 V 相乘(Attention Value)
- 矩陣乘法:\([n, n] \times [n, d] \rightarrow [n, d]\)(此處忽略 Softmax 的少量計算)。
- 計算量:\(2 \times n \times n \times d = 2n^2d\)
- 輸出投影矩陣(Output Projection)
- 將結果乘以 \(W_O\) 矩陣(大小為 \([d, d]\))。
- 計算量:\(2 \times n \times d \times d = 2nd^2\)
Attention 小計:\((6nd^2 + 2nd^2) + (2n^2d + 2n^2d) = 8nd^2 + 4n^2d\)
根據架構不同,FFN 的計算量有所差異:
採用兩層線性映射,中間夾一個激活函數(如 ReLU 或 GELU): 1. 第一層升維:\([n, d] \times [d, m] \rightarrow [n, m]\),計算量為 \(2ndm\) 2. 第二層降維:\([n, m] \times [m, d] \rightarrow [n, d]\),計算量為 \(2ndm\)
傳統 FFN 小計:\(4ndm\)
現代 LLM(如 LLaMA、Mistral)採用 SwiGLU 激活函數,需要三個權重矩陣(Gate、Up、Down): 1. Gate 與 Up 矩陣(升維):\(2 \times ([n, d] \times [d, m]) \rightarrow 2 \times 2ndm = 4ndm\) 2. Down 矩陣(降維):\([n, m] \times [m, d] \rightarrow [n, d]\),計算量為 \(2ndm\)
現代 FFN 小計:\(6ndm\)
將上述各部分加總,並乘上總層數 \(L\):
標準 Transformer 總計算量 \[ \text{Total FLOPs (Standard)} = L \times (8nd^2 + 4n^2d + 4ndm) \]
現代 SwiGLU Transformer 總計算量 \[ \text{Total FLOPs (SwiGLU)} = L \times (8nd^2 + 4n^2d + 6ndm) \]
在現代大語言模型(LLM)中,通常隱藏層維度遠大於序列長度(\(d \gg n\)),此時 \(4n^2d\) 的佔比極小,可近似忽略。
若以傳統 FFN 常見的 \(m = 4d\) 代入,前向傳播每層的計算量約為: \[ 8nd^2 + 4nd(4d) = 24nd^2 \]
這與模型參數量(密集參數主要集中在這些矩陣中)形成了固定的比例關係。因此業界常使用以下簡化公式來快速估算單個 Token 的計算量:
- 前向傳播(Forward Pass):\(\approx 2N\) FLOPs / Token
- 反向傳播(Backward Pass):\(\approx 4N\) FLOPs / Token(計算梯度與權重更新,工作量為前向的 2 倍)
- 完整訓練(Training):\(\approx 6N\) FLOPs / Token
訓練總計算量估算公式: \[ \text{Training FLOPs} \approx 6 \times \text{模型參數量}(N) \times \text{訓練總 Token 數} \]
Infra
介紹幾種包括Megatron等框架的大模型的並行訓練的方式。
下表歸納羅列了幾種主要的並行方法的特性:
| 并行方式 | 切分对象 | 主要目标 | 是否改变单卡参数量 | 是否改变单卡Activation | 主要通信 | 通信量趋势 | 依赖关系 |
|---|---|---|---|---|---|---|---|
| Data Parallel | Batch | 提高吞吐 | ❌ | ❌ | AllReduce Gradient | O(P) | 无 |
| Distributed Data Parallel | Batch | DP的優化版本 | ❌ | ❌ | AllReduce Gradient | O(P) | 无 |
| Fully Sharded Data Parallel | Batch + Parameters | 降参数显存 | ✅ | ❌ | AllGather + ReduceScatter | O(P) | 无 |
| ZeRO-1 | Optimizer State | 降优化器显存 | ❌ | ❌ | Gradient Sync | O(P) | DP |
| ZeRO-2 | Optimizer + Gradient | 降训练显存 | ❌ | ❌ | ReduceScatter | O(P) | DP |
| ZeRO-3 | 全参数 | 最大化省显存 | ✅ | ❌ | AllGather参数 | O(P) | DP |
| Tensor Parallel | Hidden维 | 扩大模型规模 | ✅ | 部分减少 | AllReduce / AllGather | O(B·S·H) | 无 |
| Sequence Parallel (Megatron) | Activation(seq维) | 降Activation显存 | ❌ | ✅ | Gather/Scatter Activation | O(B·S·H) | TP |
| Expert Parallel | Experts | 扩大MoE模型 | ✅ | ❌ | AllToAll Token Routing | O(Token) | MoE |
| Pipeline Parallel | Layer | 超大模型训练 | ✅ | 部分减少 | Send/Recv Activation | O(B·S·H) | 无 |
| Virtual Pipeline | Layer Chunk | 降流水线气泡 | 同PP | 同PP | Send/Recv | 同PP | PP |
| Context Parallel | Sequence | 长上下文训练 | ❌ | ✅ | KV交换 | O(S·H) | 通常配TP |
| Ulysses SP(Ulysses) | Sequence | 长上下文训练 | ❌ | ✅ | AllToAll | O(S·H) | 无 |
| Ring Attention | Sequence | 超长上下文 | ❌ | ✅ | Ring KV Transfer | O(S·H) | 无 |
簡單介紹Context Parallel。
Context Parallel作用於模型的Attention步驟,對query進行切分,但是每個rank都需要看到完整的key和value的副本。
key和value可以在計算時,在rank間交換傳輸,使每個query可以看到完整的key和value。
簡單介紹Ulysses並行
Ulysses來自Deepspeed生態。Ulysses 的核心思路是:在不同的训练阶段,灵活切换数据的切分维度。
进入 Attention 前:将文本的序列长度(Sequence Dimension)均匀切分到各个 GPU 上。
计算 Attention 时:通过通信,把数据转换为按注意力头(Head Dimension)切分,让每个 GPU 拥有“局部完整的序列,但只负责一部分 Head”。
簡單介紹Ring Attention
Ring Attention 把傳統 Context Parallel 中“一次性 All-Gather 收集齐全部 KV”的方式,改成了在环状通信拓扑中边传输、边计算的流水线模式。Ring Attention是Context Parallel的一種實現。
Agent設計
Agent架構
現在主流有哪幾種agent/multi agent架構?
- 單Agent架構
- ReAct架構(最經典)= Reason + Act。核心思想是:
Thought -> Action -> Observation -> Thought,是所有Agent的基礎。 - 特點:簡單、泛化性強、易擴展、適合聊天Agent - 缺點:長任務、長對話容易漂移、上下文越來越長、規劃能力有限 - Plan-and-Execute:把規劃和執行拆開。結構是
Planner Agent -> Task List -> Executor Agent. - 特點:長任務更可靠,可控性增強 - 缺點:計劃容易過時,動態適應能力一般 - Workflow Agent:本質不是Agent,而是LLM充當結點的工作流。可以分為幾種:
- DAG Workflow
- State Machine Agent
- Multi Agent:
- Manager-Worker。Manager負責拆任務,Worker負責執行不同的子任務;
- Debate式:允許Agent之間扮演不同的角色,互相辯論。能夠提升推理質量,修正幻覺
- Society:模仿社會/群體行為。理論上擴展性強,但容易失控。
- Blackboard:多個Agent共享一個“黑板”,任何Agent可以讀取和寫入,接力完成任務。
當前有哪幾種管理Agent記憶的方法?
- Working Memory,即當前上下文窗口。幾種管理方法:
- Sliding Window:保留最近N輪
- Summarization:總結和壓縮歷史上下文
- Hierarchical Context:分為Hot Context、Warm Context、Cold Context,類似CPU Cache:
- Hot Context包括:當前對話,最新任務,核心關注的任務。直接在prompt中保留
- Warn Context:中間推理結果、舊代碼……等不太重要,但可能有用的東西。採用summary + retrieval的方式保留和檢索
- Cold Context:冷上下文,可負責長期記憶。可通過Vector DB、Knowledge Graph等方式實現
- Episodic Memory:情節記憶,不只記知識,而是記經驗,例如某次失敗是因為token錯誤,或者用戶喜歡簡潔回答等。可以通過embedding向量庫召回。
- Semantic Memory:語義記憶,記憶知識庫,而不是記憶經歷、經驗。即RAG。
- Procedural Memory:程序性記憶,即執行某些事情,需要經過哪些步驟。skill文檔就是一種程序性記憶。
RAG
讲一讲NDCG(Normalized Discounted Cumulative Gain)这个reward/metric。
在介绍NDCG之前,先需要了解DCG和IDCG。
DCG:设召回模型返回n条结果, \[ DCG = \sum_{i=1}^n \frac{ 2^{\text{rel}_i} - 1 }{ \log_2(i+1) } \]
- \(\text{rel}_i\)表示第\(i\)个位置的搜索结果的相关性;我们可以用标注数据来定义相关性,如果第\(i\)个结果在标注的ground truth中,就让它的相关性为1,否则为0.
- 分子:相关性越高,贡献越大
- 分母:位置越靠后,折扣越大,按\(\log\)衰减。这是因为我们假设用户更关心排序靠前的结果。
IDCG:把所有结果按最佳排序(相关性从高到低)时的 DCG。
NDCG:\(\text{NDCG} = {\text{DCG}\over \text{IDCG}}\). 可以看出\(0 \le \text{NDCG} \le 1\). \(0\le \text{NDCG}\)是显然的。而\(\text{NDCG} \le 1\)可以这样理解:
假设存在\(i < j, g_i > g_j\),其中\(g_i, g_j\)是DCG的分子。那么交换这两项带来DCG的差值为: \[ \begin{aligned} \Delta &= {g_i \over \log_2(j+1)} + {g_j \over {\log_2(i+1)}} -({{{g_i} \over {\log_2(i+1)}} +{ g_j \over {\log_2(j+1)}}})\\ &= {g_i - g_j\over\log_2(j+1) } + {g_j - g_i\over \log_2(i+1)}\\ &= (g_j - g_i)(\frac{1}{\log_2(i+1)} - \frac{1}{\log_2(j+1)})\\ & > 0 \end{aligned} \]
因此DCG这类问题的最佳排序方案就是为高权重的位置分配高价值的结果,因此\(\text{NDCG} \le 1\).
CoT
你是如何構造CoT的?
這個要結合實際項目作答。可供參考的簡單回答:
- 數據層面:
- 合成数据:利用商用模型搜集合成數據,生成符合特定規則的求解步驟;
- 规则与模板引导:對於垂直領域任務,可以在prompt中設計對應規則模板;
- 数据清洗与过滤:利用verifier或規則檢查,濾除錯誤數據;
- 訓練層面:
- SFT:基於prompt、CoT、answer三元組構造訓練數據;
- RL方法:可引入過程獎勵提升CoT的準確率;利用可驗證的任務設計和獎勵設計,獲得可靠的CoT;
- 推理層面:
- 採樣多條CoT,利用Self-Consistency方法選出最優解,或者利用Tree of Thoughts方法進行回溯搜索。
多模態大模型
你能列舉幾個常見的從視覺編碼器的圖像特征映射到大模型文本特征的方法嗎?
各種多模態融合模塊的優缺點? (注意)Q-Former容易破壞visual token之間的空間關係。
在 BLIP-2 或者 Qwen-VL 中,Learnable Query 的作用是什么,为什么在后续版本中,比如 BLIP-3 和 Qwen2-VL 中都不使用了
Learnable Query(可学习查询)在BLIP-2和Qwen-VL中扮演了一个高效的”信息筛选官”角色,将海量的图像特征压缩成大语言模型更容易处理的少量语义标记。而后续模型(如BLIP-3和Qwen2-VL)之所以不再使用它,主要是因为基础模型的能力大幅提升,能够处理更长的上下文,更多的token,使得更简单、更直接的设计成为了新主流。
如果讓你從頭開始訓練一個多模態大模型,你會如何設計模型結構、訓練流程和項目流程?
對於多模態大模型,提高圖像的分辨率是十分重要的。為什麼現在的大模型往往使用如256x256這類低分辨率的圖像,無法做到高分辨率呢?
你觀察到GPT4-V有哪些問題?為什麼會存在這些問題?
計算機視覺相關問題
爲什麽要對圖像做預處理?
- 預處理將數據變換到統一的格式,方便模型學習;
- 通過提前提取有用的特徵,裁剪出感興趣區域來加快計算;
ViT模型中是如何對位置信息進行編碼的?
TODO
請比較Transformer和CNN
TODO
Coding
接下来简单记录一些面试过程中实际遇到的或其它面試經驗推薦的題。
在面試過程中要求現場手寫的算法題常常不會很難,但作答過程中要思路清晰,能夠有效地與面試官溝通,盡量減少試錯次數,一次通過。
答題之前記得問清楚數據規模,時間複雜度和空間複雜度需求。
- ⭐最長回文子串
- ⭐二叉樹的最近公共祖先
- ⭐⭐兩數之和變體:設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可解。可考慮引入緩存等策略進行優化。
開放性問題
這一節記錄一些自己被問到的開放性問題。問題具體的答案還是需要結合自身經歷才行。
在個人技術成長方面,你有什麼規劃?
一般可以列出自己最近感興趣的論文和想做的方向,與團隊業務相結合就好。
如何平衡團隊的業務目標與個人的技術成長?
面試官問出這個問題的時候,基本意味著這個團隊是業務導向的,技術上不太強。
ε=(´ο`*)))
回答“優先完成團隊目標,業餘也會保持對技術的關注”即可。
為什麼想要離職/看新機會?
- 僅僅是解釋前東家的缺點是不夠的。每個公司有每個公司的缺點,不能保證下一家沒有相同的問題。一般可以將問題解釋為當前公司平臺無法提供更好的發展,而現在在看的機會能補充這方面的不足。最好不要表現出自己是當前工作上遇到困難而離職的,而應盡量表現出自己的事業當前處於上升期,但由於某些原因(工作地點、待遇、發展方向、職業規劃)而不得不離開。這時可以順帶説説自己有多麽適合這個新崗位。重要的是表現出自己與新公司是一個互相成就的關係。
- 說清楚想去哪裡,比說為什麼離開更重要。
請介紹一下過往最困難的一個項目。
你當前採用的項目方案的亮點是什麼?你對項目最重要的貢獻是?
是什麼使你在項目中具有不可替代性?或者是什麼使你具備比他人更高的價值?
拿到offer後的標準問題
拿到Offer後,記得問以下重點問題。可以不直接問,但也需要間接地通過各種渠道去瞭解。要瞭解的包括但不限於:
- 績效的考核方式,KPI的考核情況
- 有沒有末位淘汰
- 有沒有輪流背D績效
- 績效工資佔縂工資比例
- 績效有沒有強制分佈
- 績效如何影響年終獎
- 股票和期權的行權規則
- 競業協議
- 是否需要背競業協議
- 競業協議是否與期權等權利挂鈎
- 工作強度:可以開門見山地詢問新工作的工作強度如何
- 總包、總包構成和職級
- 總包構成:
- 總回報預計多少
- 其中多少是現金,多少由股票/期權構成?
- 公積金繳納比例
- 職級:公司的職級是如何劃分的,如何與互聯網的“標準職級”對應?
- 總包構成:
一些經驗和感想:
- (不是絕對的)獵頭告訴你某公司不加班、965……基本不太可信,還是需要額外信息佐證。
- 競業協議是不公平的。如果你簽了競業協議,公司就有權阻止你入職同行業内的任何公司,並在你離職後提供一些微小的補償。但相反的,假如你主動離職去读博、考公,主動希望公司啟動競業協議,公司卻可以選擇不啟動競業。主動權總是在公司手上。 某些公司,例如拼多多,有很大的概率啓動競業協議,并且在员工離職後派人調查其去向;所以這個問題一定要在入職之前了解清楚。
總結
筆記的重要性:只學習不總結就容易忘。不做筆記不行啊。最好每次面試過後,立即將記錄下來,時不時重新過一遍。
平時多練習,多刷題,保持手感。有的公司(例如Minimax)的算法测试会期望给出最优解,面試時 即使把題目做出來了,也可以問一下需不需要繼續改進,提一提能想到的改進點。
附錄
智力題
本節記錄我收集到的一些代碼題或者智力題。
兩個硬幣的後驗概率
有兩個硬幣,一個硬幣的兩面都是正面;另一個是正常硬幣:一面是正面,另一面是反面;
隨機選取其中一枚,拋擲五次,都是正面。問這枚硬幣是正常硬幣的概率是?
解:設\(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} \]
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)\)
參考資料:斐波那契數列通項公式求解