依存句法分析器的簡單實現

生成式句法分析指的是，生成一系列依存句法樹，從它們中用特定演算法挑出概率最大那一棵。句法分析中，生成模型的構建主要使用三類信息：詞性信息、辭彙信息和結構信息。前二類很好理解，而結構信息需要特殊語法標記，不做考慮。

本文主要利用了辭彙+詞性生成聯合概率模型，使用最大生成樹Prim演算法搜索最終結果，得到了一個簡單的漢語依存句法分析器。

開源項目

本文代碼已集成到HanLP中開源：http://hanlp.dksou.com/

基本思路

統計詞語WordA與詞語WordB構成依存關係DrC的頻次，詞語WordA與詞性TagB構成依存關係DrD的頻次，詞性TagA與詞語WordB構成依存關係DrE的頻次，詞性TagA與詞詞性TagB構成依存關係DrF的頻次。為句子中詞語i與詞語j生成多條依存句法邊，其權值為上述四種頻次的綜合（主要利用詞-詞頻次，其餘的作平滑處理用）。取邊的權值最大的作為唯一的邊，加入有向圖中。

在有向圖上使用Prim最大生成樹演算法，計算出最大生成樹，格式化輸出。

模型訓練

簡單地統計一下清華大學語義依存網路語料，得到如下結果：

@符號連接起兩個辭彙或詞性，用<>括起來的表示詞性，否則是辭彙。如果@後面沒有內容，則表示頻次，否則表示一些依存關係與其出現的頻次。

依存句法分析

分詞標註

以「我吃米飯」為例，先進行分詞與詞性標註，結果：

生成有向圖

由於依存句法樹中有虛根的存在，所以為其加入一個虛節點，這樣一共有四個節點：

每個節點都與另外三個構成一條有向邊，一共4 * 3 = 12 條：

1. ##核心##/root 到 我/rr : 未知 10000.0
2. ##核心##/root 到 吃/v : 未知 10000.0
3. ##核心##/root 到 米飯/n : 未知 10000.0
4. 我/rr 到 ##核心##/root : 核心成分 6.410175
5. 我/rr 到 吃/v : 施事 21.061098 經驗者 28.54827 目標 33.656525 受事 37.021248 限定 43.307335 相伴體 48.00737 關係主體 53.115623 內容 53.115623 來源 64.101746
6. 我/rr 到 米飯/n : 限定 22.2052 施事 48.00737 受事 57.170277 目標 57.170277 經驗者 64.101746 連接依存 64.101746
7. 吃/v 到 ##核心##/root : 核心成分 1.7917595
8. 吃/v 到 我/rr : 連接依存 96.688614 介詞依存 107.67474 施事 107.67474
9. 吃/v 到 米飯/n : 限定 24.849068
10. 米飯/n 到 ##核心##/root : 核心成分 37.077995
11. 米飯/n 到 我/rr : 連接依存 113.2556
12. 米飯/n 到 吃/v : 受事 0.6931472

其中「未知」表示邊不存在，「受事」「施事」表示依存關係，後面的小數表示權值。我對概率取了負對數，所以接下來用加法求最小生成樹即可。

最小生成樹

關於最小生成樹的Prim演算法請參考《最小生成樹演算法初步》，這裡必須有所改動，由於虛根有且只能有一個孩子，所以虛根必須單獨計算：

然後就是中規中矩的Prim演算法：

得出最小生成樹：

格式化輸出

將其轉為CoNLL格式輸出：

可視化

使用可視化工具展現出來：

結果評測

我沒有進行嚴格的測試，這只是一個玩具級別的漢語依存句法分析器。先來看幾個good case與bad case——

效果比較馬虎，為何這麼說，這是因為分詞的訓練語料和句法分析語料不同，且我自知此方法嚴重依賴辭彙共現，主要是這種二元辭彙生成模型無法充分利用上下文。

短一點的搜索語句可能還是有微量的利用價值。

TODO

應當採用判別式模型，導入SVM或最大熵作為權值的計算工具，然後使用最大生成樹演算法獲取全局最優解。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！