CS224n異聞錄（二）

01-24

Hi，大家好，這裡是糖葫蘆喵喵~！

新年快樂~！

あけましておめでとうございます～！ことしもよろしくお願いします～！

另外喵喵的在線課程也已經上線啦：CS231n 課後作業第一講 : Assignment 1，歡迎觀看！

北方的孩子們已經感受到了雪的氣息，然而吳恩達老師的第五節課又雙叒叕跳票啦！在我們靜靜地等待late january的時候，先讓我們來進行CS224n 2017 Spring的Assignment 2作業解析吧，還請大家多多指教~！

喵喵的代碼實現：Observerspy/CS224n，歡迎watch和star！

那麼，繼續我們的自然語言處理煉丹旅程吧~！

Part 1 Tensorflow Softmax

上來就是送分題，用TF實現Softmax。我們在CS231n Assignment 1 Part 3詳細講了Softmax和cross-entropy Loss的推導，在CS224n Assignment 1 Patt 1里又講了Softmax的offset不變性。忘記了的小夥伴請去認真複習！

(a) 首先按照Softmax公式，簡單的兩行實現Softmax：

exp = tf.exp(x)out = exp / tf.reduce_sum(exp, 1, keep_dims=True)

(b) 繼續按照cross-entropy公式，實現loss：注意y原本是tf.int32的，類型轉換。

out = - tf.reduce_sum(tf.to_float(y) * tf.log(yhat))

(d) prediction_op，就是線性Softmax，注意初始化參數為0。

pred = softmax(tf.matmul(self.input_placeholder, W) + b)

loss_op，就是剛才的寫好的cross-entropy函數，注意y是目標，yhat是預測值，不要搞混了。

(e) train_op，就是用optimizer去minimize你的loss，並反向傳播（再也不用手寫反向傳播了是不是很開心！）。

然後就是跑一跑代碼，沒什麼複雜的。不過這個代碼結構寫的還是很不錯的，建議仔細閱讀一遍！

Part 2 Neural Transition-Based Dependency Parsing

基於神經網路的依存句法模型，第6課視頻已經詳細講解過了依存句法分析，這裡我們需要理解並實現一個Transition-Based的依存句法分析器。

如果你在視頻中沒有理解這個方法，不要怕，接下來我們一步步看到底什麼是Transition-Based。

(a) 首先要明確，依存句法分析的目的是通過建立詞之間的修飾關係從而分析句法結構的一種方法。Transition-Based實際上指的是arc-standard方法，通過SHIFT、LEFT-ARC和RIGHT-ARC三種動作來決定單詞之間是否依賴以及依賴關係。每個單詞只能被修飾（指向）一次，但是可以多次修飾（指向）其他單詞。

SHIFT指兩個詞A與B之間沒有依存關係；

LEFT-ARC指兩個詞A與B之間是A<-B的左鏈接關係；

RIGHT-ARC指兩個詞A與B之間是A->B的右鏈接關係。

我們通過作業中的例子來詳細地看這個方法。我們要對下面這個句子進行分析：

I parsed this sentence correctly.

分析結果如圖：

arc-standard方法通過維護一個棧(stack)和隊列(buffer)來進行分析Transition動作：

初始時stack空，buffer里是整個句子前加一個ROOT：

initial : stack : [] buffer : [ROOT, I, parsed, this, sentence, correctly]

然後buffer出隊（從左邊）: [ROOT]，並壓入stack。

step 1 : stack : [ROOT] buffer : [I, parsed, this, sentence, correctly]

這時分析stack 里最新的詞和緊挨著它的那個詞，但是只有一個詞ROOT，所以必然是SHIFT動作。然後buffer出隊（從左邊）: [I]，並壓入stack。

step 2 : stack : [ROOT, I] buffer : [parsed, this, sentence, correctly]

這時分析stack 里最新的詞和緊挨著它的那個詞：ROOT, I，根據分析結果圖，這倆詞沒有依存關係，因此執行的動作是SHIFT。然後buffer繼續出隊: [parsed]，並壓入stack。

step 3 : stack : [ROOT, I, parsed] buffer : [this, sentence, correctly]

分析stack 里最新的詞和緊挨著它的那個詞： I, parsed，根據分析結果圖，這倆詞是I<-parsed關係，即LEFT-ARC。這時由於[I]已經存在被指向的依存關係了，因此出棧。

step 4 : stack : [ROOT, parsed] buffer : [this, sentence, correctly]

這時分析stack 里最新的詞和緊挨著它的那個詞：ROOT, parsed，根據分析結果圖，這倆詞沒有依存關係，因此執行的動作是SHIFT。然後buffer繼續出隊: [this]，並壓入stack。

step 5 : stack : [ROOT, parsed, this] buffer : [sentence, correctly]

分析stack 里最新的詞和緊挨著它的那個詞： parsed, this，根據分析結果圖，這倆詞沒有依存關係，因此執行的動作是SHIFT。然後buffer繼續出隊: [sentence]，並壓入stack。

step 6 : stack : [ROOT, parsed, this, sentence] buffer : [correctly]

分析stack 里最新的詞和緊挨著它的那個詞： this, sentence，根據分析結果圖，這倆詞是this<-sentence關係，即LEFT-ARC。這時由於[this]已經存在被指向的依存關係了，因此出棧。

step 7 : stack : [ROOT, parsed, sentence] buffer : [correctly]

分析stack 里最新的詞和緊挨著它的那個詞： parsed, sentence，根據分析結果圖，這倆詞是parsed->sentence關係，即RIGHT-ARC。這時由於[sentence]已經存在被指向的依存關係了，因此出棧。

step 8 : stack : [ROOT, parsed] buffer : [correctly]

分析stack 里最新的詞和緊挨著它的那個詞： ROOT, parsed，根據分析結果圖，這倆詞沒有依存關係，因此執行的動作是SHIFT。然後buffer繼續出隊: [correctly]，並壓入stack。

step 9 : stack : [ROOT, parsed, correctly] buffer : []

分析stack 里最新的詞和緊挨著它的那個詞： parsed, correctly，根據分析結果圖，這倆詞是parsed->correctly關係，即RIGHT-ARC。這時由於[correctly]已經存在被指向的依存關係了，因此出棧。

step 10 : stack : [ROOT, parsed] buffer : []

分析stack 里最新的詞和緊挨著它的那個詞： ROOT, parsed，根據分析結果圖，這倆詞是ROOT->parsed關係，即RIGHT-ARC。這時由於[parsed]已經存在被指向的依存關係了，因此出棧。

step 11 : stack : [ROOT] buffer : []

stack只剩ROOT，buffer空，結束分析。

這就是完整的一次分析過程！可以看到其實就是在每次有棧操作之後判斷棧里最新的兩個詞之間的三種依存關係：如果沒有關係，則執行[出隊入棧]；如果有關係，記錄關係並將被修飾（指向）詞執行[出棧]。直到所有詞都出隊並出棧完成。

(b) 我們剛才說了，終止條件是stack只剩ROOT，buffer空，也就是說所有詞都分別執行[出隊入棧]與[出棧]兩個操作。因此對於n個詞的句子一共操作2n次。

初始化：（我們直接從step 1開始就行了），stack里有一個[ROOT]，buffer為整個句子，dependencies 為空。

parse step：根據動作執行[出隊入棧]與[出棧]操作：如果沒有關係(SHIFT)，則執行[出隊入棧]；如果有關係(LEFT-ARC/RIGHT-ARC)，記錄關係並將被修飾（指向）詞執行[出棧]

if transition == "S": #SHIFT word = self.buffer.pop(0) #出隊 self.stack.append(word) #入棧 elif transition == "LA": #LEFT-ARC (A<-B) leftword = self.stack.pop(-2) #A出棧 self.dependencies.append((self.stack[-1], leftword)) #記錄A<-B elif transition == "RA": #RIGHT-ARC (A->B) rightword = self.stack.pop(-1) #B出棧 self.dependencies.append((self.stack[-1], rightword)) #記錄A->B

(d) TF可以進行強大的矩陣運算，所以，我們可以實現一次轉化一組minibatch的操作，演算法如圖：

minibatch_parse參數：

sentences：一組句子

model：用來預測三種動作的模型

batch_size：minibatch大小

這個函數也就是讓我們把sentences按照batch_size分成一個個minibatch，每個minibatch通過一次model.predict就可以得到minibatch的動作了。然後執行動作，記錄依賴關係，直至結束。

1. 首先用類PartialParse對每個句子初始化：

parse = [PartialParse(sentence) for sentence in sentences]

2. 然後按照batch_size分選擇一個minibatch：

parse_mini = parse[:batch_size]

3.每個minibatch通過一次model.predict就可以得到minibatch的動作了，返回的就是minibatch中每個sentence需要執行的動作列表，然後每個sentence執行動作：

transitions = model.predict(parse_mini) for i, act in enumerate(transitions): parse_mini[i].parse_step(act)

4.我們要判斷某個句子是否分析完畢（終止條件是stack只剩ROOT，buffer空）需要檢查len(parse.stack) == 1 && len(parse.buffer) == 0這個條件。那麼，不滿足條件的繼續放入parse_mini中執行下一輪動作判斷操作：

parse_mini = [parse for parse in parse_mini if len(parse.stack) > 1 or len(parse.buffer) > 0]

5.當len(parse_mini) == 0時整個minibatch就分析完了，記錄依存關係並更新minibatch：

dependencies.extend(parse.dependencies for parse in parse[:batch_size]) parse = parse[batch_size:]

最後運行檢測代碼正確性即可。

(e) 好了，現在關於依存句法分析的功能已經實現完畢了，剩下的就是模型如何去預測動作，也就是上面我們使用的model.predict是怎麼執行的。

這裡我們的model神經網路結構如下：

relu====>dropout====>Softmax

我們網路的參數w要用到Xavier initialization初始化技術，實際上TF里有這個功能，我們在這裡還是要實現一遍：

Xavier initialization實際上是在 $(-epsilon, +epsilon)$ 範圍內產生均勻分布的值作為w的初始化值。 $epsilon$ 定義如下：

$epsilon =sqrt frac{6}{sum(dimension)}$

實現很簡單：

epsilon = tf.cast(tf.sqrt(6 / np.sum(shape)), tf.float32)out = tf.random_uniform(shape, -epsilon, epsilon)

所以我們在初始化w時要這樣：

xavier_initializer = xavier_weight_init()W = tf.Variable(xavier_initializer(shape), name="W")

(f) (g) 關於dropout和adam的推導請看歡迎來到實力至上主義的CS231n教室（二），裡面講的很詳細了，這裡不再重複。

(h) 我們的數據集是Penn Treebank，在data文件夾下.conll的文件就是了。訓練數據包含了很多句子的分析，這裡我們的程序讀取數據集中的單詞(word)、詞性(pos)、指向的單詞(head)、關係(label)。然後對每個狀態根據棧和隊列的狀態抽取了18個單詞和其對應的詞性，並用唯一ID來表示，共計36個特徵。具體內容可以閱讀論文《A Fast and Accurate Dependency Parser using Neural Networks》。於是，數據轉化為（None, 36）大小。

那麼這36個用ID表示特徵需要變成詞向量，這裡作業提供好了embedding矩陣,(詞表，50)大小，直接用ID去對應查找就好了，轉化後每一個ID特徵變為50維，因此數據是（None, 36*50）大小。

embedding實現，其中tf.nn.embedding_lookup函數相當於用ID進行lookup，也就是用輸入作為embedding矩陣的索引，輸出embedding矩陣的一行。

#self.pretrained_embeddings 就是讀入的embedding矩陣embedding = tf.Variable(self.pretrained_embeddings, name="embedding")embeddings = tf.reshape(tf.nn.embedding_lookup(embedding, self.input_placeholder), [-1, Config.n_features * Config.embed_size])

最後就是我們的網路核心結構了，前面說了是一個relu====>dropout====>Softmax的形式。

model：

hidden = tf.nn.relu(tf.matmul(x, W) + b1)h_drop = tf.nn.dropout(hidden, self.dropout_placeholder)pred = tf.matmul(h_drop, U) + b2

於是可以愉快地跑代碼啦！

結果loss要求小於0.07，dev和test都大於88%。

Part 3 Recurrent Neural Networks: Language Modelingn

最後一部分主要是RNN理論推導，詳細的RNN推導我們在歡迎來到實力至上主義的CS231n教室（三）里也講了，不在重複講了，只不過是把幾個符號變了而已。

(a) 我們來看新的東西：困惑度perplexity，定義如下：

$egin{align} label{eq:perplexity} PP^{(t)} left( oldsymbol{y}^{(t)}, hat{oldsymbol{y}}^{(t)} ight) &= frac{ 1 }{ ar{P} left( oldsymbol{x}_{pred}^{(t+1)} = oldsymbol{x}^{(t+1)} vert oldsymbol{x}^{(t)}, dots, oldsymbol{x }^{(1)} ight)} = frac{ 1 }{ sum_{j=1}^{vert V vert} y_{j}^{(t)} cdot hat{y}_{j}^{(t)} } end{align}$