Dependency的Parsing

我們為什麼把Parsing特別拿出來講呢?

這頁投影片,我相信大家已經看過很多次了

我們說NLP的任務,就可以歸類成幾大類

但有一些任務看起來比較複雜

我們沒有辦法把它放到這八大類的NLP任務上

所以我們特別拿出來講,其中一個就是Parsing

那之前呢,我們已經講過Constituency Parsing

那Constituency Parsing在意的是說

某兩個相鄰的詞彙,它們能不能夠拼在一起變成一個Constituent

這些Constituent還可以再拼成更大的Constituent

然後組成一個樹狀的結構

那我們已經講過Constituency Parsing是怎麼運作的

那Dependency Parsing它關注的點跟Constituency Parsing不太一樣

Constituency Parsing在意的是兩個相鄰的Token能不能夠組成一個Constituent

那Dependency Parsing在意的是兩個詞彙之間的關係

而這兩個詞彙不一定要相鄰

所以Dependency Parsing相較於Constituency Parsing

它又有更大的Flexibility

Constituency Parsing只在意相鄰詞彙之間的關係

但Dependency Parsing它在意的是一個句子裡面

詞彙兩兩之間的關係

它們不需要是相鄰的

不是相鄰的詞彙,它們可能也會有非常緊密的關係

所以Dependency Parsing它考慮的是詞彙和詞彙之間的關係

而不局限於兩個詞彙是否是相鄰

舉例來說,在今天這個例子裡面

今天在這個例子裡面有說

We book her the flight to Taipei

那book是book什麼東西呢?

訂了一個什麼東西呢?

是訂了一個飛機票

那雖然book跟flight它們沒有直接相連

但是flight是book所訂的東西

所以flight跟book它們有非常緊密的關聯性

那這個就是Dependency Parsing想要找出來的東西

當我們說兩個詞彙間有關聯的時候

這種關聯有各式各樣的關聯

那我們會用一個箭頭來表示這種關係

在這個箭頭的起始我們叫做head

起始的詞彙叫做head

箭頭指向的那一個詞彙我們叫dependent

那詞彙和詞彙之間有什麼樣的關係呢?

有非常多種關係

那這邊我們就不細講

我這邊就直接剪了一個教科書裡面的圖

給大家看說

詞彙和詞彙之間有很多各式各樣的關係

那這個我們是想要憑藉著Machine Learning的力量

幫我們找出來的

那Dependency Parsing要做的事

就是找出詞彙和詞彙之間的關係

而講得更具體而言

Dependency Parsing要做的事

就是把一個句子變成一個graph

變成一個directed graph

directed graph的意思就是說

node和node之間是由箭頭連起來

而這些箭頭是有方向性的

這個叫directed graph

那這個graph裡面

每一個節點每一個node

就是一個詞彙

詞彙和詞彙節點和節點之間的edge

就代表了這兩個詞彙之間的關係

那舉一個具體的例子

假設一個句子是說

I want to study a PhD

我想念個博班

你會對你指導教授說的話

你想要念個博班

想要簽下去

那這句話的Dependency Parsing的結果

長什麼樣子呢

Dependency Parsing就是要把一個句子

變成一個圖

這個圖上每一個節點就是一個詞彙

然後接下來節點和節點間

詞彙和詞彙之間

有關係的詞彙會被連在一起

比如說

Want的主詞是什麼呢

誰想呢

我想

我想要做什麼呢

想要念一個東西

想要念什麼呢

想要念博班

那這些詞彙和詞彙間有關係的

就被箭頭把它連起來

而箭頭上面其實會有一個標記

每一個箭頭是有不同的型態的

這邊我們用一個英文的

用一串英文來代表這個型態

每一個箭頭都是有不同的型態

代表這兩個用箭頭連在一起的詞彙

它們之間有什麼樣的關係

那找出這個Graph

就是Dependency Parsing的任務

那你會發現說在這個圖上

一般每一個詞彙

它都只有一個Parent

比如說Study就是被Want指到

然後PhD就是被Study指到

然後會有某一個詞彙

它沒有被任何其他人指到

所以這個時候一般而言呢

在做Dependency Parsing的時候

你就會加上一個額外的Node

這個Root會去指向那個

沒有任何人指到的詞彙

這個詞彙指的是

這整個句子裡面最關鍵的那個詞彙

它指向所有人

沒有人被它指到

那這一個沒有被指到的詞彙

就用Root來指它

所以這整個Graph

其實它不是一個General的Graph

它是一個樹狀的結構

在這個樹狀的結構裡面

每一個Node也就是每一個詞彙

只會有一個箭頭指進來

唯一的例外是Root

沒有箭頭指進來

它只有指給別人

但是一個詞彙

它可以指給很多不同的詞彙

比如說Want

它可以指向I

也可以指向Study

那因為它是一個樹狀的結構

所以在這個樹狀結構裡面

的每一個Node

每一個詞彙

它都有唯一的一條路徑

可以回溯到它的Root

因為它是一個樹狀的結構

所以它不會有兩條不同路徑

回溯到Root

每一個詞彙

都只有一個唯一的路徑

可以回溯到Root

這個就是Dependency Parsing

就是我們要用Machine Learning

找出來的東西

那怎麼找出一個Dependency的Parsing Tree呢

其實這個方法可能比你想像的還要更簡單

還記不記得我們在講

Constituency Parsing的時候

我們說怎麼知道一串文字

一個Spam 是不是Constituent呢

你就Train一個Classifier

這個Classifier吃一串文字

接下來它會說

它是Constituent 還是不是Constituent

那它是哪一種Constituent呢

把它當作一個Multiclass Classification的Problem來看待

讓Classifier決定說這串文字

它是哪一個Constituent

它如果是Constituent的話

它是哪一個Constituent

其實Dependency Parsing也是一樣的

Dependency Parsing在意的是

兩個詞彙間他們有沒有關係

如果有的話是什麼樣的關係

所以真正要做的事情就是訓練一個Classifier

這Classifier吃兩個詞彙作為Input

然後它來判斷說

到底左邊這個詞彙

該不該有一個箭頭指向右邊這個詞彙

Classifier會吃兩個輸出

Classifier會吃兩個輸入

我們叫它左輸入跟右輸入

那Classifier要決定說

左側的這個輸入能不能

應不應該被指到右側這個輸入

那應不應該呢

這是一個Binary的Classification的問題

這只是一個簡單的二元分類的問題

左邊這個詞彙要指到右邊這個詞彙

或左邊這個詞彙不要指到右邊這個詞彙

這是一個二元分類的問題

如果我們確定說

左邊這個詞彙要指到右邊這個詞彙

那這兩個詞彙間的關係到底是什麼呢

把它當作一個Multiclass Classification的問題

然後就Train下去

就結束了

假設你真的Train出來了

一個這樣子的Classifier以後

你怎麼會透過這個Classifier

來得到一個Dependency的Parsing Tree呢

你要做的事情就是這個樣子

你有N個詞彙

那你其實除了這N個詞彙以外

你還多加一個多餘的詞彙叫做Root

接下來呢

把這些N個詞彙加上Root

兩兩丟到Classifier裡面

問Classifier說

左邊這個輸入應不應該接到右邊這個輸入

舉例來說

現在Classifier的輸入是Root跟Want

那你在訓練的時候

你有Ground Truth

你有標準答案

你有Label好的標準答案

所以你知道說Root要指到Want

所以Classifier就會說Yes

Root要指到Want

或者是你把另外兩個詞彙Q跟A

分別當作Classifier的左邊的輸入跟右邊的輸入

Q有指到A嗎

沒有

所以Classifier就要說No

那你只要訓練出這樣的Classifier

然後把這個Classifier跑N加1平方次

因為這邊有N個Word加Root嘛

所以總共有N加1個Token

然後這些Token兩兩間都要用Classifier來跑一下

它們應不應該被接在一起

那你就跑N加1平方次就好了

那事實上N加1平方次是高估啦

不應該是N加1平方次啦

因為自己跟自己不用算嘛

所以其實是N加1乘N

而且其實還應該要再更少一點

為什麼還應該要再更少一點呢

因為Root它只能夠指向別人

它不能夠被別人指向

所以你不需要去檢查說

愛會不會指向Root

Want會不會指向Root

因為這本來就是不合理不可能的

一開始你就不會去

不需要去檢查這件事

你只需要檢查說Root能不能指愛

Root能不能指Want

所以這邊N加1平方次是遠遠的

其實是高估啦

其實還有很多可能你是不需要考慮的

那總之呢

你只需要把這些Token兩兩丟到Classifier

讓Classifier告訴你說

要不要被接在一起

就結束了

Dependency Parsing

就做完了

就這樣子

在文獻上真的是這麼做的嗎

真的是這麼做

所以這邊就是引用了一個

iClear的論文跟ACL18的論文

告訴你說

真的就是這麼做

當然這邊我們可以來稍微看一下

18年的ACL這篇Paper的做法

它先用Bidirectional的LSTM

把每一個Token的Embedding抽出來

因為那個時候BERT呢

還沒有BERT

所以就不會用BERT

用這個Bidirectional的LSTM

今天你如果自己要做的話

你當然會選擇用BERT

然後把這個Embedding

我們現在就是要把這個Embedding

兩兩丟到Classifier裡面去

然後Classifier幫我們決定說

這兩個Embedding要不要被連在一起

如果它們被連在一起的話

那它們的Relation應該是什麼

那實際上在這篇Paper裡面

它的做法就是說

我們把這個Embedding乘上一個Transform

得到另外一個Embedding

我們把這個Embedding再乘上另外一個Transform

得到另外一個Embedding

然後呢

我們把這兩個Embedding

做類似Attention這樣子的機制

那實際上它做的事情是把

右邊這個Embedding乘上一個Transform

再乘上左邊這個Embedding

然後會得到一個數值

那個數值就代表說

這兩個Token應不應該被連在一起

它們應該被連在一起的Confident

這個數值就代表了一個

Binary Classifier的Output

然後就結束了

像Label的部分其實也是

就以此類推而已

好 但講到這邊

我們可能會發現一個問題

那你會發現說呢

在這個

在講這個Dependency Parsing

跟Constituency Parsing的時候

有很多類似的地方

其實在講這個Constituency Parsing的時候

我們也講過類似的問題

就是你如果單純把整個問題

看作是一個分類的問題

你可能會製造出矛盾的結果

你可能會製造出

不是Tree的東西

不符合規則的東西

舉例來說

你有可能說

有一個Binary Classifier告訴你說

W1要接到W

所以你就在W1跟W2之間

加一個Age

然後這個Binary Classifier又說

現在我們把W3當作左邊的輸入

W2當作右邊的輸入

它又說Yes

代表說W3應該要接到W2

但這樣就矛盾了

因為在Dependency Parsing Tree裡面

每一個Node只能夠有一個Incoming的Age

它只能夠有一個輸入的箭頭

它不可以有兩個輸入的箭頭

這樣你就製造出一個

不合法的Dependency Parsing Tree

那這個是我們不想要的

但是如果單純把Dependency Parsing

看作是一個Binary Classification Problem的話

你會遇到這樣子的問題

所以怎麼辦呢

你可以用類似Maximum Spanning Tree的Algorithm

來解釋這個問題

其實我們在講Constituency Parsing的時候

也說遇到這樣子的

有可能產生不符合文法

不符合規則的文法數的狀況

我們就用另外一個方法

我們說如果是Dependency Parsing的話

你就是用這個CKY的Parser

CKY的Chart Based Parsing來解決這個問題

那如果在Dependency Parsing裡面

你會用Maximum的Spanning Tree

那它的概念是這個樣子

根據我們的Classifier

我們會知道所有的Node

兩兩之間

它們應該被連在一起的分數

Classifier會Output一個分數給我們

Classifier可能會說

Root連到W2的信心分數給它0.2分

Root連到W1的信心分數給它0.9分

W1連到W2的信心分數給它0.7分

W2連到W1的信心分數給它0.3分

接下來你重啟所有合乎規則的

Dependency Parsing Tree

比如說Root

它只能夠指到W1跟W2的其中一個

指誰呢

它指W2

如果它指W2的話

W2就得去指W1

那另外一個可能的Parsing Tree呢

是Root去指W1

然後W1再去指W2

那再看說在這兩個Case

哪一個Case

它上面的這個Edge

上面的這個Edge

總合起來的分數比較高

比如說下面這個Case

總合起來的分數比較高

那下面這個Case

就是Dependency Parsing的結果

那因為今天這個例子非常簡單

只有兩個詞彙

所以我們可以用重啟的方法

找出所有符合規則的Parsing Tree

看誰的分數最高

那如果有非常多的Node呢

那你就會用類似Maximum Spanning Tree的演算法

來找出符合規則

且分數最高的那個數

就這樣

那其實在Dependency Parsing裡面

也可以做Transition Based Approach

我們在講Constituency Parsing的時候

也有講過這個Transition Based Approach

那時候我們有講說

有一個Stake 有一個Buffer

然後有三個Action是你可以採取的

那在Dependency Parsing裡面也是一樣

你也有一個Stake

你也有一個Buffer

你一樣也有三個Action可以採取

那你只要有這個Stake

一開始是空的

然後你有一個Buffer

Buffer一開始是把整個句子直接填進去

然後你只要採取一連串的Action

你只要不斷的決定說

有三個Action要採取哪一個

採取一連串的Action

最後就會得到一個Parsing Tree

那因為這個部分跟Constituency Parsing差不多

那這門課我們其實真正想要Focus

Focus的是Deep Learning的部分

所以我們就不會再重複跟你講說

在Dependency Parsing裡面

是怎麼做Transition Based Approach

要知道說跟Constituency Parsing很像

我們就是要看這個Stake的內容

看這個Buffer的內容

決定要採取哪一個Action

就結束了

所以在文獻上就有很多這樣子的做法

那你看這個圖也大概可以知道它是怎麼做的

用一個RNN

用一個LSTM

把Stake讀過去

然後用一個LSTM把Buffer讀過去

用一個LSTM把過去採行過的Action讀過去

然後決定說

現在要採取三個Action裡面的哪一個

那下面這個圖呢

意思也是差不多

就有一個Stake 有一個Buffer

然後有一個Network

把Stake跟Buffer的資訊讀進去

然後接下來決定要採取哪一個Action

那你發現說這些Paper呢

都是比較早期的Paper

舉例來說像這樣子的想法

其實在14年的時候就已經有了

那這種Transition Based

用Deep Learning做Transition Based的方法

其中最知名的就是SyntaxNet

那SyntaxNet呢

是Google在ACL16發表的Paper

為什麼SyntaxNet特別知名呢

我覺得其實有一個最關鍵的原因就是

它有一個好的Blog Post

它又是Google做的

又有一個好的Post

那個Post裡面有一個好的動畫

這個動畫呢

長這個樣子

我們來觀賞一下這個動畫

你看有一個Stake 有一個Buffer

然後不斷地採取不同的Action

不斷地採取不同的Action

每次要決定說要採取這三個Action裡面的哪一個

然後你就產生了一個Parsing Tree了

再看一次

我們要建一個Dependency的Parsing Tree

有Stake 有Buffer

然後每次要決定說要採取這三個Action裡面的哪一個

然後呢

你最後就可以產生一個Parsing Tree了

怎麼決定要採取哪一個Action呢

就是用RNN LSTM

把Stake跟Buffer讀過去

然後決定採取哪一個Action

然後就結束了

那當然從今天的角度看來

這個不就是用Deep Learning做Transition Based的Parsing嗎

不過當年,要看看這個Blog Post的時間

是16年啊

16年的春天

那是一個混亂的時代

那個時候剛有AlphaGo

所有人只要聽到一點點跟AI有關的東西

都會大驚小怪

當時很多人看到這個Post

馬上嚇得魂不附體

哇,這個是Google的

是Syntax內

它一定可以解決所有的問題

這個,這邊有Action

它一定是用Reinforcement Learning Learn的

它就跟AlphaGo一樣

所有NLP的問題都解決了

才不是,這個就是一個Parsing

為什麼要這麼大驚小怪呢

它就是一個Parsing

不過在2016年那個混亂的年代

那個時候有各式各樣的裝神弄鬼

那Syntax內

今天甚至不是一個最好的Parser

後面還有更多

更好的Transition Based Parsing的方法

但反正這個是

它出現在2016年的上半年

接在AlphaGo之後

所以造成了一個巨大的轟動

就是這麼回事

好

這個是Syntax內

那還有很多其他的啦

比如說有Stack Pointer啊

等等

那我們就不再細講

有關Dependency Parsing的部分

總之今天就是很快的帶過Dependency Parsing

告訴大家說

怎麼用Deep Learning的技術

來做Dependency Parsing這件事情

好

下次Reference