從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 訓練工程
大模型的訓練工程是指通過建設訓練基礎設施、改進訓練策略等方法保障大模型在大規模數據、調用大量計算設備上正常訓練、提高訓練效率的工作。大模型的不同並行訓練方法是需要熟悉掌握的重點。
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。
例子 18 🌙🌙爲什麽Transformer模型要使用LayerNorm而不是BatchNorm。
TODO
例子 19 🌙🌙介紹RMSNorm。
TODO
例子 20 🌙🌙請介紹幾種你熟悉的tokenization方法。
TODO
例子 21 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結構”
例子 22 ⭐⭐⭐為什麼大模型都採用Causal LM結構？
- KV-Cache優化：Encoder-Decoder和Prefix LM都不易採用KV-Cache優化，而支持KV-Cache的Causal LM對推理加速更友好；
- 訓練效率：Encoder-Decoder架構模型的Pipeline Parallel難以優化。即使模型架構能帶來理論上的性能優勢，但是卻帶來昂貴的訓練代價的話，那麼這種模型結構就會輸給那些更能充分利用算力的模型；
- 軌跡依賴：OpenAI使用Causal LM成功實現了GPT系列大模型，這使得後來者都更傾向於採用相近的配置進行實驗。
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)\)
參考資料：斐波那契數列通項公式求解
