僅用500行Python代碼實(shí)現(xiàn)一個(gè)英文解析器的教程

正確的解析是連接“with”和“pizza”，而錯(cuò)誤的解析將“with”和“eat”聯(lián)系在了一起：

過(guò)去的一些年，自然語(yǔ)言處理（NLP）社區(qū)在語(yǔ)法分析方面取得了很大的進(jìn)展。現(xiàn)在，小小的 Python 實(shí)現(xiàn)可能比廣泛應(yīng)用的 Stanford 解析器表現(xiàn)得更出色。

文章剩下的部分首先設(shè)置了問(wèn)題，接著帶你了解為此準(zhǔn)備的簡(jiǎn)潔實(shí)現(xiàn)。parser.py 代碼中的前 200 行描述了詞性的標(biāo)注者和學(xué)習(xí)者（這里）。除非你非常熟悉 NLP 方向的研究，否則在研究這篇文章之前至少應(yīng)該略讀。

Cython 系統(tǒng)和 Redshift 是為我目前的研究而寫(xiě)的。和麥考瑞大學(xué)的合同到期后，我計(jì)劃六月份對(duì)它進(jìn)行改進(jìn)，用于一般用途。目前的版本托管在 GitHub 上。
問(wèn)題描述

在你的手機(jī)中輸入這樣一條指令是非常友善的：

Set volume to zero when I'm in a meeting, unless John's school calls.

接著進(jìn)行適當(dāng)?shù)牟呗耘渲谩Ｔ?Android 系統(tǒng)上，你可以應(yīng)用 Tasker 做這樣的事情，而 NL 接口會(huì)更好一些。接收可以編輯的語(yǔ)義表示，你就能了解到它認(rèn)為你表達(dá)的意思，并且可以修正他的想法，這樣是特別友善的。

這項(xiàng)工作有很多問(wèn)題需要解決，但一些種類(lèi)的句法形態(tài)絕對(duì)是必要的。我們需要知道：

Unless John's school calls, when I'm in a meeting, set volume to zero

是解析指令的又一種方式，而

Unless John's school, call when I'm in a meeting

表達(dá)了完全不同的意思。

依賴(lài)解析器返回一個(gè)單詞與單詞間的關(guān)系圖，使推理變得更容易。關(guān)系圖是樹(shù)形結(jié)構(gòu)，有向邊，每個(gè)節(jié)點(diǎn)（單詞）有且僅有一個(gè)入弧（頭部依賴(lài)）。

用法示例：

>>> parser = parser.Parser()
>>> tokens = "Set the volume to zero when I 'm in a meeting unless John 's school calls".split()
>>> tags, heads = parser.parse(tokens)
>>> heads
[-1, 2, 0, 0, 3, 0, 7, 5, 7, 10, 8, 0, 13, 15, 15, 11]
>>> for i, h in enumerate(heads):
... head = tokens[heads[h]] if h >= 1 else 'None'
... print(tokens[i] + ' <-- ' + head])
Set <-- None
the <-- volume
volume <-- Set
to <-- Set
zero <-- to
when <-- Set
I <-- 'm
'm <-- when
in <-- 'm
a <-- meeting
meeting <-- in
unless <-- Set
John <-- 's
's <-- calls
school <-- calls
calls <-- unless

一種觀點(diǎn)是通過(guò)語(yǔ)法分析進(jìn)行推導(dǎo)比字符串應(yīng)該稍稍容易一些。語(yǔ)義分析映射有望比字面意義映射更簡(jiǎn)單。

這個(gè)問(wèn)題最讓人困惑的是正確性是由慣例，即注釋指南決定的。如果你沒(méi)有閱讀指南并且不是一個(gè)語(yǔ)言學(xué)家，就不能判斷解析是否正確，這使整個(gè)任務(wù)顯得奇怪和虛假。

例如，在上面的解析中存在一個(gè)錯(cuò)誤：根據(jù) Stanford 的注釋指南規(guī)定，“John's school calls” 存在結(jié)構(gòu)錯(cuò)誤。而句子這部分的結(jié)構(gòu)是指導(dǎo)注釋器如何解析一個(gè)類(lèi)似于“John's school clothes”的例子。

這一點(diǎn)值得深入考慮。理論上講，我們已經(jīng)制定了準(zhǔn)則，所以“正確”的解析應(yīng)該相反。如果我們違反約定，有充分的理由相信解析任務(wù)會(huì)變得更加困難，因?yàn)槿蝿?wù)和其他語(yǔ)>法的一致性會(huì)降低。【2】但是我們可以測(cè)試經(jīng)驗(yàn)，并且我們很高興通過(guò)反轉(zhuǎn)策略獲得優(yōu)勢(shì)。

我們確實(shí)需要慣例中的差異——我們不希望接收相同的結(jié)構(gòu)，否則結(jié)果不會(huì)很有用。注釋指南在哪些區(qū)別使下游應(yīng)用有效和哪些解析器可以輕松預(yù)測(cè)之間取得平衡。
映射樹(shù)

在決定構(gòu)建什么樣子的關(guān)系圖時(shí)，我們可以進(jìn)行一項(xiàng)特別有效的簡(jiǎn)化：對(duì)將要處理的關(guān)系圖結(jié)構(gòu)進(jìn)行限制。它不僅在易學(xué)性方面有優(yōu)勢(shì)，在加深算法理解方面也有作用。大部分的>英文解析工作中，我們遵循約束的依賴(lài)關(guān)系圖就是映射樹(shù)：

樹(shù)。除了根外，每個(gè)單詞都有一個(gè)弧頭。
映射關(guān)系。針對(duì)每對(duì)依賴(lài)關(guān)系 （a1, a2）和 （b1, b2），如果 a1 < b2, 那么 a2 >= b2。換句話(huà)說(shuō)，依賴(lài)關(guān)系不能交叉。不可能存在一對(duì) a1 b1 a2 b2 或者 b1 a1 b2 a2 形式的依賴(lài)關(guān)系。

在解析非映射樹(shù)方面有豐富的文獻(xiàn)，解析無(wú)環(huán)有向圖方面的文獻(xiàn)相對(duì)而言少一些。我將要闡述的解析算法用于映射樹(shù)領(lǐng)域。
貪婪的基于轉(zhuǎn)換的解析

我們的語(yǔ)法分析器以字符串符號(hào)列表作為輸入，輸出代表關(guān)系圖中邊的弧頭索引列表。如果第 i 個(gè)弧頭元素是 j, 依賴(lài)關(guān)系包括一條邊 （j, i）。基于轉(zhuǎn)換的語(yǔ)法分析器>是有限狀態(tài)轉(zhuǎn)換器；它將 N 個(gè)單詞的數(shù)組映射到 N 個(gè)弧頭索引的輸出數(shù)組。

弧頭數(shù)組表示了 MSNBC 的弧頭：MSNBC 的單詞索引是1，reported 的單詞索引是2， head[1] == 2。你應(yīng)該已經(jīng)發(fā)現(xiàn)為什么樹(shù)形結(jié)構(gòu)如此方便——如果我們輸出一個(gè) DAG 結(jié)構(gòu)，這種結(jié)構(gòu)中的單詞可能包含多個(gè)弧頭，樹(shù)形結(jié)構(gòu)將不再工作。

雖然 heads 可以表示為一個(gè)數(shù)組，我們確實(shí)喜歡保持一定的替代方式來(lái)訪(fǎng)問(wèn)解析，以方便高效的提取特征。Parse 類(lèi)就是這樣：

class Parse(object):
 def __init__(self, n):
 self.n = n
 self.heads = [None] * (n-1)
 self.lefts = []
 self.rights = []
 for i in range(n+1):
 self.lefts.append(DefaultList(0))
 self.rights.append(DefaultList(0))
 
 def add_arc(self, head, child):
 self.heads[child] = head
 if child < head:
 self.lefts[head].append(child)
 else:
 self.rights[head].append(child)

和語(yǔ)法解析一樣，我們也需要跟蹤句子中的位置。我們通過(guò)在 words 數(shù)組中置入一個(gè)索引和引入棧機(jī)制實(shí)現(xiàn)，棧中可以壓入單詞，設(shè)置單詞的弧頭時(shí)，彈出單詞。所以我們的狀態(tài)數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)。

解析過(guò)程的每一步都應(yīng)用了三種操作之一：

SHIFT = 0; RIGHT = 1; LEFT = 2
MOVES = [SHIFT, RIGHT, LEFT]
 
def transition(move, i, stack, parse):
 global SHIFT, RIGHT, LEFT
 if move == SHIFT:
 stack.append(i)
 return i + 1
 elif move == RIGHT:
 parse.add_arc(stack[-2], stack.pop())
 return i
 elif move == LEFT:
 parse.add_arc(i, stack.pop())
 return i
 raise GrammarError("Unknown move: %d" % move)

LEFT 和 RIGHT 操作添加依賴(lài)關(guān)系并彈棧，而 SHIFT 壓棧并增加緩存中 i 值。

因此，語(yǔ)法解析器以一個(gè)空棧開(kāi)始，緩存索引為0，沒(méi)有依賴(lài)關(guān)系記錄。選擇一個(gè)有效的操作，應(yīng)用到當(dāng)前狀態(tài)。繼續(xù)選擇操作并應(yīng)用直到棧為空且緩存索引到達(dá)輸入數(shù)組的終點(diǎn)。（沒(méi)有逐步跟蹤是很難理解這種算法的。嘗試準(zhǔn)備一個(gè)句子，畫(huà)出映射解析樹(shù)，接著通過(guò)選擇正確的轉(zhuǎn)換序列遍歷完解析樹(shù)。）

下面是代碼中的解析循環(huán)：

class Parser(object):
 ...
 def parse(self, words):
 tags = self.tagger(words)
 n = len(words)
 idx = 1
 stack = [0]
 deps = Parse(n)
 while stack or idx < n:
 features = extract_features(words, tags, idx, n, stack, deps)
 scores = self.model.score(features)
 valid_moves = get_valid_moves(i, n, len(stack))
 next_move = max(valid_moves, key=lambda move: scores[move])
 idx = transition(next_move, idx, stack, parse)
 return tags, parse
 
def get_valid_moves(i, n, stack_depth):
 moves = []
 if i < n:
 moves.append(SHIFT)
 if stack_depth >= 2:
 moves.append(RIGHT)
 if stack_depth >= 1:
 moves.append(LEFT)
 return moves

我們以標(biāo)記的句子開(kāi)始，進(jìn)行狀態(tài)初始化。然后將狀態(tài)映射到一個(gè)采用線(xiàn)性模型評(píng)分的特征集合。接著尋找得分最高的有效操作，應(yīng)用到狀態(tài)中。

這里的評(píng)分模型和詞性標(biāo)注中的一樣工作。如果對(duì)提取特征和使用線(xiàn)性模型評(píng)分的觀點(diǎn)感到困惑，你應(yīng)該復(fù)習(xí)這篇文章。下面是評(píng)分模型如何工作的提示：

class Perceptron(object)
 ...
 def score(self, features):
 all_weights = self.weights
 scores = dict((clas, 0) for clas in self.classes)
 for feat, value in features.items():
 if value == 0:
 continue
 if feat not in all_weights:
 continue
 weights = all_weights[feat]
 for clas, weight in weights.items():
 scores[clas] += value * weight
 return scores

這里僅僅對(duì)每個(gè)特征的類(lèi)權(quán)重求和。這通常被表示為一個(gè)點(diǎn)積，然而我發(fā)現(xiàn)處理很多類(lèi)時(shí)就不太適合了。

定向解析器（RedShift）遍歷多個(gè)候選元素，但最終只會(huì)選擇最好的一個(gè)。我們將關(guān)注效率和簡(jiǎn)便而忽略其準(zhǔn)確性。我們只進(jìn)行了單一的分析。我們的搜索策略將是完全貪婪的，就像詞性標(biāo)記一樣。我們將鎖定在選擇的每一步。

如果認(rèn)真閱讀了詞性標(biāo)記，你可能會(huì)發(fā)現(xiàn)下面的相似性。我們所做的是將解析問(wèn)題映射到一個(gè)使用“扁平化”解決的序列標(biāo)記問(wèn)題，或者非結(jié)構(gòu)化的學(xué)習(xí)算法（通過(guò)貪婪搜索）。
特征集

特征提取代碼總是很丑陋。語(yǔ)法分析器的特征指的是上下文中的一些標(biāo)識(shí)。

我們指出了上述12個(gè)標(biāo)識(shí)的單詞表，詞性標(biāo)注，和標(biāo)識(shí)關(guān)聯(lián)的左右孩子數(shù)目。

因?yàn)槭褂玫氖蔷€(xiàn)性模型，特征指的是原子屬性組成的三元組。

def extract_features(words, tags, n0, n, stack, parse):
 def get_stack_context(depth, stack, data):
 if depth >;= 3:
 return data[stack[-1]], data[stack[-2]], data[stack[-3]]
 elif depth >= 2:
 return data[stack[-1]], data[stack[-2]], ''
 elif depth == 1:
 return data[stack[-1]], '', ''
 else:
 return '', '', ''
 
 def get_buffer_context(i, n, data):
 if i + 1 >= n:
 return data[i], '', ''
 elif i + 2 >= n:
 return data[i], data[i + 1], ''
 else:
 return data[i], data[i + 1], data[i + 2]
 
 def get_parse_context(word, deps, data):
 if word == -1:
 return 0, '', ''
 deps = deps[word]
 valency = len(deps)
 if not valency:
 return 0, '', ''
 elif valency == 1:
 return 1, data[deps[-1]], ''
 else:
 return valency, data[deps[-1]], data[deps[-2]]
 
 features = {}
 # Set up the context pieces --- the word, W, and tag, T, of:
 # S0-2: Top three words on the stack
 # N0-2: First three words of the buffer
 # n0b1, n0b2: Two leftmost children of the first word of the buffer
 # s0b1, s0b2: Two leftmost children of the top word of the stack
 # s0f1, s0f2: Two rightmost children of the top word of the stack
 
 depth = len(stack)
 s0 = stack[-1] if depth else -1
 
 Ws0, Ws1, Ws2 = get_stack_context(depth, stack, words)
 Ts0, Ts1, Ts2 = get_stack_context(depth, stack, tags)
 
 Wn0, Wn1, Wn2 = get_buffer_context(n0, n, words)
 Tn0, Tn1, Tn2 = get_buffer_context(n0, n, tags)
 
 Vn0b, Wn0b1, Wn0b2 = get_parse_context(n0, parse.lefts, words)
 Vn0b, Tn0b1, Tn0b2 = get_parse_context(n0, parse.lefts, tags)
 
 Vn0f, Wn0f1, Wn0f2 = get_parse_context(n0, parse.rights, words)
 _, Tn0f1, Tn0f2 = get_parse_context(n0, parse.rights, tags)
 
 Vs0b, Ws0b1, Ws0b2 = get_parse_context(s0, parse.lefts, words)
 _, Ts0b1, Ts0b2 = get_parse_context(s0, parse.lefts, tags)
 
 Vs0f, Ws0f1, Ws0f2 = get_parse_context(s0, parse.rights, words)
 _, Ts0f1, Ts0f2 = get_parse_context(s0, parse.rights, tags)
 
 # Cap numeric features at 5?
 # String-distance
 Ds0n0 = min((n0 - s0, 5)) if s0 != 0 else 0
 
 features['bias'] = 1
 # Add word and tag unigrams
 for w in (Wn0, Wn1, Wn2, Ws0, Ws1, Ws2, Wn0b1, Wn0b2, Ws0b1, Ws0b2, Ws0f1, Ws0f2):
 if w:
 features['w=%s' % w] = 1
 for t in (Tn0, Tn1, Tn2, Ts0, Ts1, Ts2, Tn0b1, Tn0b2, Ts0b1, Ts0b2, Ts0f1, Ts0f2):
 if t:
 features['t=%s' % t] = 1
 
 # Add word/tag pairs
 for i, (w, t) in enumerate(((Wn0, Tn0), (Wn1, Tn1), (Wn2, Tn2), (Ws0, Ts0))):
 if w or t:
 features['%d w=%s, t=%s' % (i, w, t)] = 1
 
 # Add some bigrams
 features['s0w=%s, n0w=%s' % (Ws0, Wn0)] = 1
 features['wn0tn0-ws0 %s/%s %s' % (Wn0, Tn0, Ws0)] = 1
 features['wn0tn0-ts0 %s/%s %s' % (Wn0, Tn0, Ts0)] = 1
 features['ws0ts0-wn0 %s/%s %s' % (Ws0, Ts0, Wn0)] = 1
 features['ws0-ts0 tn0 %s/%s %s' % (Ws0, Ts0, Tn0)] = 1
 features['wt-wt %s/%s %s/%s' % (Ws0, Ts0, Wn0, Tn0)] = 1
 features['tt s0=%s n0=%s' % (Ts0, Tn0)] = 1
 features['tt n0=%s n1=%s' % (Tn0, Tn1)] = 1
 
 # Add some tag trigrams
 trigrams = ((Tn0, Tn1, Tn2), (Ts0, Tn0, Tn1), (Ts0, Ts1, Tn0),
 (Ts0, Ts0f1, Tn0), (Ts0, Ts0f1, Tn0), (Ts0, Tn0, Tn0b1),
 (Ts0, Ts0b1, Ts0b2), (Ts0, Ts0f1, Ts0f2), (Tn0, Tn0b1, Tn0b2),
 (Ts0, Ts1, Ts1))
 for i, (t1, t2, t3) in enumerate(trigrams):
 if t1 or t2 or t3:
 features['ttt-%d %s %s %s' % (i, t1, t2, t3)] = 1
 
 # Add some valency and distance features
 vw = ((Ws0, Vs0f), (Ws0, Vs0b), (Wn0, Vn0b))
 vt = ((Ts0, Vs0f), (Ts0, Vs0b), (Tn0, Vn0b))
 d = ((Ws0, Ds0n0), (Wn0, Ds0n0), (Ts0, Ds0n0), (Tn0, Ds0n0),
 ('t' + Tn0+Ts0, Ds0n0), ('w' + Wn0+Ws0, Ds0n0))
 for i, (w_t, v_d) in enumerate(vw + vt + d):
 if w_t or v_d:
 features['val/d-%d %s %d' % (i, w_t, v_d)] = 1
 return features

訓(xùn)練

學(xué)習(xí)權(quán)重和詞性標(biāo)注使用了相同的算法，即平均感知器算法。它的主要優(yōu)勢(shì)是，它是一個(gè)在線(xiàn)學(xué)習(xí)算法：例子一個(gè)接一個(gè)流入，我們進(jìn)行預(yù)測(cè)，檢查真實(shí)答案，如果預(yù)測(cè)錯(cuò)誤則調(diào)整意見(jiàn)（權(quán)重）。

循環(huán)訓(xùn)練看起來(lái)是這樣的：

class Parser(object):
 ...
 def train_one(self, itn, words, gold_tags, gold_heads):
 n = len(words)
 i = 2; stack = [1]; parse = Parse(n)
 tags = self.tagger.tag(words)
 while stack or (i + 1) < n:
 features = extract_features(words, tags, i, n, stack, parse)
 scores = self.model.score(features)
 valid_moves = get_valid_moves(i, n, len(stack))
 guess = max(valid_moves, key=lambda move: scores[move])
 gold_moves = get_gold_moves(i, n, stack, parse.heads, gold_heads)
 best = max(gold_moves, key=lambda move: scores[move])
 self.model.update(best, guess, features)
 i = transition(guess, i, stack, parse)
 # Return number correct
 return len([i for i in range(n-1) if parse.heads[i] == gold_heads[i]])

訓(xùn)練過(guò)程中最有趣的部分是 get_gold_moves。 通過(guò)Goldbery 和 Nivre （2012），我們的語(yǔ)法解析器的性能可能會(huì)有所提升，他們?cè)赋鑫覀冨e(cuò)了很多年。

在詞性標(biāo)注文章中，我提醒大家，在訓(xùn)練期間，你要確保傳遞的是最后兩個(gè)預(yù)測(cè)標(biāo)記做為當(dāng)前標(biāo)記的特征，而不是最后兩個(gè)黃金標(biāo)記。測(cè)試期間只有預(yù)測(cè)標(biāo)記，如果特征是基于訓(xùn)練過(guò)程中黃金序列的，訓(xùn)練環(huán)境就不會(huì)和測(cè)試環(huán)境保持一致，因此將會(huì)得到錯(cuò)誤的權(quán)重。

在語(yǔ)法分析中我們面臨的問(wèn)題是不知道如何傳遞預(yù)測(cè)序列！通過(guò)采用黃金標(biāo)準(zhǔn)樹(shù)結(jié)構(gòu)，并發(fā)現(xiàn)可以轉(zhuǎn)換為樹(shù)的過(guò)渡序列，等等，使得訓(xùn)練得以工作，你獲得返回的動(dòng)作序列，保證執(zhí)行運(yùn)動(dòng)，將得到黃金標(biāo)準(zhǔn)的依賴(lài)關(guān)系。

問(wèn)題是，如果語(yǔ)法分析器處于任何沒(méi)有沿著黃金標(biāo)準(zhǔn)序列的狀態(tài)時(shí)，我們不知道如何教它做出的“正確”運(yùn)動(dòng)。一旦語(yǔ)法分析器發(fā)生了錯(cuò)誤，我們不知道如何從實(shí)例中訓(xùn)練。

這是一個(gè)大問(wèn)題，因?yàn)檫@意味著一旦語(yǔ)法分析器開(kāi)始發(fā)生錯(cuò)誤，它將停止在不屬于訓(xùn)練數(shù)據(jù)的任何一種狀態(tài)——導(dǎo)致出現(xiàn)更多的錯(cuò)誤。

對(duì)于貪婪解析器而言，問(wèn)題是具體的：一旦使用方向特性，有一種自然的方式做結(jié)構(gòu)化預(yù)測(cè)。

像所有的最佳突破一樣，一旦你理解了這些，解決方案似乎是顯而易見(jiàn)的。我們要做的就是定義一個(gè)函數(shù)，此函數(shù)提問(wèn)“有多少黃金標(biāo)準(zhǔn)依賴(lài)關(guān)系可以從這種狀態(tài)恢復(fù)”。如果能定義這個(gè)函數(shù)，你可以依次進(jìn)行每種運(yùn)動(dòng)，進(jìn)而提問(wèn)，“有多少黃金標(biāo)準(zhǔn)依賴(lài)關(guān)系可以從這種狀態(tài)恢復(fù)？”。如果采用的操作可以讓少一些的黃金標(biāo)準(zhǔn)依賴(lài)實(shí)現(xiàn)，那么它就是次優(yōu)的。

這里需要領(lǐng)會(huì)很多東西。

因此我們有函數(shù) Oracle（state）:

Oracle(state) = | gold_arcs ∩ reachable_arcs(state) |

我們有一個(gè)操作集合，每種操作返回一種新?tīng)顟B(tài)。我們需要知道：

 shift_cost = Oracle(state) – Oracle(shift(state))
 right_cost = Oracle(state) – Oracle(right(state))
 left_cost = Oracle(state) – Oracle(left(state))

現(xiàn)在，至少一種操作返回0。Oracle(state)提問(wèn)：“前進(jìn)的最佳路徑的成本是多少?”最佳路徑的第一步是轉(zhuǎn)移，向右，或者向左。

事實(shí)證明，我們可以得出 Oracle 簡(jiǎn)化了很多過(guò)渡系統(tǒng)。我們正在使用的過(guò)渡系統(tǒng)的衍生品 —— Arc Hybrid 是 Goldberg 和 Nivre （2013）提出的。

我們把oracle實(shí)現(xiàn)為一個(gè)返回0-成本的運(yùn)動(dòng)的方法，而不是實(shí)現(xiàn)一個(gè)功能的Oracle(state)。這可以防止我們做一堆昂貴的復(fù)制操作。希望代碼中的推理不是太難以理解，如果感到困惑并希望刨根問(wèn)底的花，你可以參考 Goldberg 和 Nivre 的論文。

def get_gold_moves(n0, n, stack, heads, gold):
 def deps_between(target, others, gold):
 for word in others:
 if gold[word] == target or gold[target] == word:
 return True
 return False
 
 valid = get_valid_moves(n0, n, len(stack))
 if not stack or (SHIFT in valid and gold[n0] == stack[-1]):
 return [SHIFT]
 if gold[stack[-1]] == n0:
 return [LEFT]
 costly = set([m for m in MOVES if m not in valid])
 # If the word behind s0 is its gold head, Left is incorrect
 if len(stack) >= 2 and gold[stack[-1]] == stack[-2]:
 costly.add(LEFT)
 # If there are any dependencies between n0 and the stack,
 # pushing n0 will lose them.
 if SHIFT not in costly and deps_between(n0, stack, gold):
 costly.add(SHIFT)
 # If there are any dependencies between s0 and the buffer, popping
 # s0 will lose them.
 if deps_between(stack[-1], range(n0+1, n-1), gold):
 costly.add(LEFT)
 costly.add(RIGHT)
 return [m for m in MOVES if m not in costly]

進(jìn)行“動(dòng)態(tài) oracle”訓(xùn)練過(guò)程會(huì)產(chǎn)生很大的精度差異——通常為1-2%，和運(yùn)行時(shí)的方式?jīng)]有區(qū)別。舊的“靜態(tài)oracle”貪婪訓(xùn)練過(guò)程已經(jīng)完全過(guò)時(shí)；沒(méi)有任何理由那樣做了。
總結(jié)

我感覺(jué)，語(yǔ)言技術(shù)，特別是那些相關(guān)語(yǔ)法，特別神秘。我不能想象什么樣的程序可以實(shí)現(xiàn)。

我認(rèn)為對(duì)于人們來(lái)說(shuō)，最好的解決方案可能相當(dāng)復(fù)雜是很自然的。200,000 行的Java包感覺(jué)為宜。

但是，僅僅實(shí)現(xiàn)一個(gè)單一算法時(shí)，算法代碼往往很短。當(dāng)你只實(shí)現(xiàn)一種算法時(shí)，在寫(xiě)之前你確實(shí)知道要寫(xiě)什么，你不需要關(guān)注任何不必要的具有很大性能影響的抽象概念。
注釋

[1] 我真的不確定如何計(jì)算Stanford解析器的代碼行數(shù)。它的jar文件裝載了200k大小內(nèi)容，包括大量不同的模型。這并不重要，但在50k左右似乎是安全的。

[2]例如，如何解析“John's school of music calls”?你需要確認(rèn)“John's school”短語(yǔ)和“John's school calls”、“John's school of music calls”有相同的結(jié)構(gòu)。對(duì)可以放入短語(yǔ)的不同的“插槽”進(jìn)行推理是我們推理句法分析的關(guān)鍵途徑。你能想到每個(gè)短語(yǔ)為具有不同形狀的連接器，你需要插入不同的插槽——每個(gè)短語(yǔ)也有一定數(shù)量不同形狀的插槽。我們正試圖弄清楚什么樣的連接器在什么地方，因此可以搞清句子是如何連接在一起的。

[3]這里有使用了“深度學(xué)習(xí)”技術(shù)的 Stanford 解析器更新版本，此版本準(zhǔn)確性更高。但是，最終模型的準(zhǔn)確度仍排在最好的移進(jìn)歸約分析器后面。這是一篇偉大的文章，該想法在一個(gè)語(yǔ)法分析器上實(shí)現(xiàn)，這個(gè)語(yǔ)法分析器是不是最先進(jìn)其實(shí)并不重要。

[4]一個(gè)細(xì)節(jié)：Stanford 依賴(lài)關(guān)系實(shí)際上是給定黃金標(biāo)準(zhǔn)短語(yǔ)結(jié)構(gòu)樹(shù)自動(dòng)生成的。參考這里的Stanford依賴(lài)轉(zhuǎn)換器頁(yè)面：http://nlp.stanford.edu/software/stanford-dependencies.shtml。
無(wú)根據(jù)猜測(cè)

長(zhǎng)期以來(lái)，增量語(yǔ)言處理算法是科學(xué)界的主要興趣。如果你想要編寫(xiě)一個(gè)語(yǔ)法分析器來(lái)測(cè)試人類(lèi)語(yǔ)句處理器如何工作的理論，那么，這個(gè)分析器需要建立部分解釋器。這里有充分的證據(jù)，包括常識(shí)性反思，它設(shè)立我們不緩存的輸入，說(shuō)話(huà)者完成表達(dá)立即分析。

但與整齊的科學(xué)特征相比，當(dāng)前算法勝出！盡我所能告訴大家，勝出的秘訣就是：

增量。早期的文字限制搜索。
錯(cuò)誤驅(qū)動(dòng)。訓(xùn)練包含一個(gè)發(fā)生錯(cuò)誤即更新的操作假設(shè)。

和人類(lèi)語(yǔ)句處理的聯(lián)系看起來(lái)誘人。我期待看到這些工程的突破是否帶來(lái)一些心理語(yǔ)言學(xué)方面的進(jìn)步。
參考書(shū)目

NLP 的文獻(xiàn)幾乎完全開(kāi)放。所有相關(guān)論文都可以在這里找到：http://aclweb.org/anthology/。

我所描述的解析器是動(dòng)態(tài)oracle arc-hybrid 系統(tǒng)的實(shí)現(xiàn)：

Goldberg, Yoav; Nivre, Joakim

Training Deterministic Parsers with Non-Deterministic Oracles

TACL 2013

然而，我編寫(xiě)了自己的特征。arc-hybrid 系統(tǒng)的最初描述在這里：

Kuhlmann, Marco; Gomez-Rodriguez, Carlos; Satta, Giorgio

Dynamic programming algorithms for transition-based dependency parsers

ACL 2011

這里最初描述了動(dòng)態(tài)oracle訓(xùn)練方法：

A Dynamic Oracle for Arc-Eager Dependency Parsing

Goldberg, Yoav; Nivre, Joakim

COLING 2012

當(dāng)Zhang 和 Clark 研究定向搜索時(shí)，這項(xiàng)工作依賴(lài)于以轉(zhuǎn)換為基礎(chǔ)的解析器在準(zhǔn)確性上的重大突破。他們發(fā)表了很多論文，但首選的引用是：

Zhang, Yue; Clark, Steven

Syntactic Processing Using the Generalized Perceptron and Beam Search

Computational Linguistics 2011 (1)

另外一篇重要的文章是這個(gè)短篇的特征工程文章，這篇文章進(jìn)一步提高了準(zhǔn)確性：

Zhang, Yue; Nivre, Joakim

Transition-based Dependency Parsing with Rich Non-local Features

ACL 2011

作為定向解析器的學(xué)習(xí)框架，廣義的感知器來(lái)自這篇文章

Collins, Michael

Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms

EMNLP 2002

實(shí)驗(yàn)細(xì)節(jié)

文章開(kāi)頭的結(jié)果引用了華爾街日?qǐng)?bào)語(yǔ)料庫(kù)第22條。Stanford 解析器執(zhí)行如下：

java -mx10000m -cp "$scriptdir/*:" edu.stanford.nlp.parser.lexparser.LexicalizedParser 
-outputFormat "penn" edu/stanford/nlp/models/lexparser/englishFactored.ser.gz $*

應(yīng)用了一個(gè)小的后處理，撤銷(xiāo)Stanford 解析器為數(shù)字添加的假設(shè)標(biāo)記，使數(shù)字符合 PTB 標(biāo)記：

"""Stanford parser retokenises numbers. Split them."""
import sys
import re
 
qp_re = re.compile('xc2xa0')
for line in sys.stdin:
 line = line.rstrip()
 if qp_re.search(line):
 line = line.replace('(CD', '(QP (CD', 1) + ')'
 line = line.replace('xc2xa0', ') (CD ')
 print line

由此產(chǎn)生的PTB格式的文件轉(zhuǎn)換成使用 Stanford 轉(zhuǎn)換器的依賴(lài)關(guān)系：

for f in $1/*.mrg; do
 echo $f
 grep -v CODE $f > "$f.2"
 out="$f.dep"
 java -mx800m -cp "$scriptdir/*:" edu.stanford.nlp.trees.EnglishGrammaticalStructure 
 -treeFile "$f.2" -basic -makeCopulaHead -conllx > $out
done

我不能輕易的讀取了，但它應(yīng)該只是使用相關(guān)文獻(xiàn)的一般設(shè)置，將一個(gè)目錄下的每個(gè).mrg文件轉(zhuǎn)換成一個(gè)CoNULL格式的 Stanford 基本依賴(lài)文件。

接著我從華爾街日?qǐng)?bào)語(yǔ)料庫(kù)第22條轉(zhuǎn)換了黃金標(biāo)準(zhǔn)樹(shù)進(jìn)行評(píng)估。準(zhǔn)確的分?jǐn)?shù)是指所有未標(biāo)記標(biāo)識(shí)中未標(biāo)記的附屬分?jǐn)?shù)（如弧頭索引）

為了訓(xùn)練 parser.py，我將華爾街日?qǐng)?bào)語(yǔ)料庫(kù) 02-21 的黃金標(biāo)準(zhǔn) PTB 樹(shù)結(jié)構(gòu)輸出到同一個(gè)轉(zhuǎn)換腳本中。

一言以蔽之，Stanford 模型和 parser.py 在同一組語(yǔ)句中進(jìn)行訓(xùn)練，在我們知道答案的持有測(cè)試集上進(jìn)行預(yù)測(cè)。準(zhǔn)確性是指我們答對(duì)多少正確的語(yǔ)句首詞。

在一個(gè) 2.4Ghz 的 Xeon 處理器上測(cè)試速度。我在服務(wù)器上進(jìn)行了實(shí)驗(yàn)，為 Stanford 解析器提供了更多內(nèi)存。parser.py 系統(tǒng)在我的MacBook Air上運(yùn)行良好。在parser.py 的實(shí)驗(yàn)中，我使用了PyPy；與早期的基準(zhǔn)相比，CPython大約快了一半。

parser.py 運(yùn)行如此之快的一個(gè)原因是它進(jìn)行未標(biāo)記解析。根據(jù)以往的實(shí)驗(yàn)，經(jīng)標(biāo)記的解析器可能慢400倍，準(zhǔn)確度提高大約1%。如果你能訪(fǎng)問(wèn)數(shù)據(jù)，使程序適應(yīng)已標(biāo)記的解析器對(duì)讀者來(lái)說(shuō)將是很好的鍛煉機(jī)會(huì)。

RedShift 解析器的結(jié)果是從版本 b6b624c9900f3bf 取出的，運(yùn)行如下：

./scripts/train.py -x zhang+stack -k 8 -p ~/data/stanford/train.conll ~/data/parsers/tmp
./scripts/parse.py ~/data/parsers/tmp ~/data/stanford/devi.txt /tmp/parse/
./scripts/evaluate.py /tmp/parse/parses ~/data/stanford/dev.conll

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com