動態規劃 (Dynamic Programming)

動態規劃（Dynamic Programming，簡稱 DP）是一種通過將問題分解為較小子問題來優化計算效率的技術。它特別適用于優化最優解問題，比如序列標注（sequence tagging）這類任務。

序列標注 (Sequence Tagging)

序列標注是自然語言處理（NLP）中常見的任務之一。它的目標是為輸入的每個單詞（或者子序列）分配一個標簽。這個標簽集通常是固定且有限的。最常見的例子是：

• 命名實體識別（NER）：為句子中的每個單詞分配一個類別（例如，表示人名、地點、組織等）。
• 詞性標注（POS tagging）：為每個單詞標記它的詞性（例如，名詞、動詞、形容詞等）。

在序列標注中，標簽是來自一個固定的標簽集合，且序列長度已知且固定。

問題描述

獨立預測的局限性

在許多基礎的機器學習模型中，每個標簽都是獨立預測的。這種方法存在一個問題，就是 獨立預測可能會導致不一致的結果。例如，在詞性標注任務中，模型可能會錯誤地標記某個單詞的詞性，但這個錯誤可能會影響后續預測。

貪心預測的缺點

貪心算法（greedy approach）逐步做出局部最優的選擇，但由于缺乏全局視野，這種方法可能會導致全局的錯誤。例如，貪心算法可能錯誤地為某個詞分配了標簽，導致后續的標注結果不一致。

舉個例子，“the old man the boat”這個句子中，如果我們貪心地預測每個詞的標簽，可能會錯誤地預測"man"作為動詞（即“the old man [to] the boat”）。但由于模型只關注當前詞，錯誤直到后續預測時才會變得明顯。

動態規劃在序列標注中的應用

動態規劃（DP）是解決這類問題的有效工具。它的基本思想是通過將問題分解為子問題，并存儲子問題的解，避免重復計算，進而提高效率。在序列標注中，DP通過計算每個詞的標簽得分以及標簽之間的轉移得分，來有效地找到最高得分的標簽序列。

序列標注模型中的得分計算

序列標注任務的模型通常會涉及兩個主要部分：

1. 發射模型（Emission Model）：表示當前單詞與某個標簽的關聯。例如，對于命名實體識別任務，發射模型會計算每個單詞屬于某個實體類型（如人名、地點等）的概率。
2. 轉移模型（Transition Model）：表示從一個標簽轉移到另一個標簽的概率。例如，標簽 “動詞” 轉移到標簽 “名詞” 的概率。

計算得分的步驟：

1. 初始化步驟（Start State）：首先計算從開始狀態（start state）到每個標簽的概率，通常用發射模型來計算。

$$prob1=e/t$$

其中 e 是發射概率，t 是轉移概率。

2. 遞歸計算（Intermediate Scores）：對于每個單詞，基于其與當前標簽的發射概率，和從前一個標簽到當前標簽的轉移概率，計算所有可能路徑的得分。

$$\text{prob4}=e\times \max (t\times \text{prob?pre})$$

其中 prob pre 是前一個狀態的概率。

3. 最終得分（Final Score）：當所有單詞都標注完成時，計算最終的得分。

$$\text{prob10}=\max (t_{\text{pre}}\times \text{prob?pre})$$

其中 tpre 是前一個標簽到當前標簽的轉移概率，prob pre 是前一個標簽的得分。

時間復雜度

• O(|words| * |labels|2)：對于標準的序列標注任務，時間復雜度是 O(單詞數×標簽數^2)，因為對于每個單詞，我們需要計算標簽之間的轉移概率，而轉移的計算需要遍歷每對標簽。
• O(|words| * |labels|3)：如果我們在模型中加入了更多的標簽上下文（例如，考慮更長的標簽序列歷史），時間復雜度會增加到 O(單詞數×標簽數^3)，這意味著計算量會更大。

模型的應用

這種基于動態規劃的序列標注方法可以應用于不同類型的模型，包括：

• 線性模型（Linear Models）：比如條件隨機場（CRF）模型，能夠有效地處理序列標注問題。
• 前饋神經網絡（Feedforward Networks）：可以用于對每個單詞進行獨立標注，盡管沒有考慮標簽之間的轉移關系。
• 循環神經網絡（RNN）：能夠在處理序列數據時保持對上下文的記憶。
• 變換器（Transformer）：能夠捕捉全局依賴關系，用于序列標注任務。

擴展：提高標簽上下文

如果我們希望引入更多的上下文信息（例如，考慮每個詞的前后標簽），可以將模型擴展為聯合模型（Joint Model）。這種模型將多個標簽的上下文信息一起處理，提高了模型的復雜性，但也可能帶來更好的性能。

語法解析（Graph Parsing）

在自然語言處理中，語法解析（Syntactic Parsing）用于識別句子的語法結構，它能夠幫助我們解析一個句子的結構，解決歧義問題。一句話可能有多種解釋，語法解析的目標是通過建立詞語之間的關系樹來解決這種歧義。

1. 什么是圖解析（Graph Parsing）？

在圖解析中，我們通過構建依存關系樹（dependency tree）來表示句子的語法結構。這種結構通常由弧（arc）、邊（edge）和依賴關系（dependencies）組成，表示一個詞語與另一個詞語之間的語法關系。

• 頭部（head）詞語是句子的核心，它決定了其他詞語的語法角色。
• 從屬詞（dependent）是依賴于頭部詞語的詞，表示與頭部的語法關系。

2. 解析樹的要求

為了確保生成的語法樹是正確的，解析算法必須滿足以下幾個要求：

1. 生成一棵樹：結果必須是一個樹結構。
2. 沒有交叉弧：樹中不能有交叉的依賴關系。
3. 有且僅有一個根：樹中必須有一個唯一的根節點。
4. 樹有最高的得分：在所有可能的樹中，得分最高的樹是最終的解析結果。

3. 動態規劃方法

圖解析可以使用動態規劃（Dynamic Programming）來高效地推導出最優的解析樹。解析的過程通常基于項目（items）和規則（rules）。

• 項目：表示在解析過程中需要構建的中間結構。
• 規則：定義如何從已有的項目中組合出新的項目。

解析過程遵循以下步驟：

1. 為每個項目定義規則：逐步組合項目。
2. 保持每個項目的最佳得分：對于每個步驟，我們保存當前最優的解析樹。

4. 圖解析的過程

圖解析算法通常基于如下思路：

• 對每個項目進行分析，存儲最優的解析路徑。
• 最終從最頂層開始，逐步向下回溯，得到最優的解析樹。

這個過程類似于金字塔結構：從底部逐步構建解析樹的各個部分，最后得到完整的句子結構。

5. CKY算法（Cocke-Younger-Kasami Algorithm）

CKY算法是一種常用的動態規劃算法，它可以有效地進行語法分析。其時間復雜度為：

O(∣rules_comb∣?∣words∣^3 + ∣rules_arc∣?∣words∣^2)

其中，|rules_comb| 是組合規則的數量，|words| 是句子中單詞的數量，|rules_arc| 是依賴關系的數量。

6. 為什么圖解析在LLM時代依然重要？

雖然大規模語言模型（LLM）在許多自然語言處理任務中表現出色，但在某些領域，語法解析仍然是非常有用的，尤其是在一些特定的專業領域，如醫療和法律中。以下是一些原因：

1. 專業領域的需求：例如，醫療領域的文本通常包含復雜的術語和結構，這時準確的語法解析對于理解句子至關重要。
2. 作為系統的一部分：語法解析可以作為其他任務（如信息抽取、機器翻譯等）的組成部分。它能提供更好的句法結構，幫助后續任務提高準確性。
3. LLMs的局限性：盡管LLMs在處理自然語言時非常強大，但在某些任務（例如抽象意義表示 AMR）上仍然存在挑戰，而圖解析可以在這些任務中提供幫助。

7. 共同指代（Coreference）

共同指代指的是文本中多個提及相同實體的現象。例如，在句子中提到“John”和“he”，我們需要確定“he”是否指代“John”。

• 實體鏈接/維基化（Entity Linking/Wikification）：將文本中的每個實體鏈接到外部知識庫（如維基百科）。

共同指代的搜索空間非常龐大，可能存在多種方式來將不同的提及聚類在一起。為了解決這個問題，我們可以采用以下簡化方法：

1. 提及檢測和過濾：首先檢測文本中所有的提及，然后篩選出可能的共同指代。
2. 鏈接提及對：對每一對提及，找到最可能的前一個提及，并將它們標記為共同指代。
3. 尋找傳遞閉包：通過逐步傳遞的方式，建立完整的共同指代關系。

8. 簡單而有效的推理算法

有時候，簡單的推理算法就足夠解決問題。通過上述的簡化方法，我們可以有效地解決共同指代問題，盡管這些方法看起來很基礎，但在許多實際應用中仍然非常有效。