條件隨機(jī)場是一種無向圖模型，且相對于深度網(wǎng)絡(luò)有非常多的優(yōu)勢，因此現(xiàn)在很多研究者結(jié)合條件隨機(jī)場(CRF)與深度網(wǎng)絡(luò)獲得更魯棒和可解釋的模型。本文結(jié)合 PyTorch 從基本的概率定義到模型實現(xiàn)直觀地介紹了 CRF 的基本概念，有助于讀者進(jìn)一步理解完整理論。

假設(shè)我們有兩個相同的骰子，但是其中的一個是公平的，每個點數(shù)出現(xiàn)的概率相同;另一個骰子則被做了手腳，數(shù)字 6 出現(xiàn)的概率為 80%，而數(shù)字 1-5 出現(xiàn)的概率都為 4%。如果我給你一個 15 次投擲骰子的序列，你能預(yù)測出我每次投擲用的是哪一枚骰子嗎?

[[229606]]

為了得到較高的準(zhǔn)確率，一個簡單的模型是，每當(dāng)「6」出現(xiàn)的時候，我們那就預(yù)測使用了有偏的骰子，而出現(xiàn)其他數(shù)字時則預(yù)測使用了公平的骰子。實際上，如果我們在每次投擲時等可能地使用任意一個骰子，那么這個簡單的規(guī)則就是你可以做到的***預(yù)測。

但是，設(shè)想一種情況：如果在使用了公平的骰子后，我們下一次投擲時使用有偏的骰子的概率為 90%，結(jié)果會怎樣呢?如果下一次投擲出現(xiàn)了一個「3」，上述模型會預(yù)測我們使用了公平的骰子，但是實際上我們使用有偏的骰子是一個可能性更大的選項。我們可以通過貝葉斯定理來進(jìn)行驗證這個說法：

其中隨機(jī)變量 y_i 是第 i 次投擲所用的骰子類型，x_i 是第 i 次投擲得到的點數(shù)。

我們的結(jié)論是，在每一步中作出可能性***的選擇只是可行策略之一，因為我們同時可能選擇其它的骰子。更有可能的情況是，以前對骰子的選擇情況影響了我未來會做出怎樣的選擇。為了成功地進(jìn)行預(yù)測，你將不得不考慮到每次投擲之間的相互依賴關(guān)系。

條件隨機(jī)場(CRF)是一個用于預(yù)測與輸入序列相對應(yīng)標(biāo)注序列的標(biāo)準(zhǔn)模型。目前有許多關(guān)于條件隨機(jī)場的教程，但是我所看到的教程都會陷入以下兩種情況其中之一：1)全都是理論，但沒有展示如何實現(xiàn)它們 2)為復(fù)雜的機(jī)器學(xué)習(xí)問題編寫的代碼缺少解釋，不能令讀者對代碼有直觀的理解。

之所以這些作者選擇寫出全是理論或者包含可讀性很差的代碼教程，是因為條件隨機(jī)場從屬于一個更廣更深的課題「概率圖模型」。所以要想深入涵蓋其理論和實現(xiàn)可能需要寫一本書，而不是一篇博文，這種情況也使得學(xué)習(xí)條件隨機(jī)場的知識比它原本所需要的更困難。

本教程的目標(biāo)是涵蓋恰到好處的理論知識，以便你能對 CRF 有一個基本的印象。此外我們還會通過一個簡單的問題向你展示如何實現(xiàn)條件隨機(jī)場，你可以在自己的筆記本電腦上復(fù)現(xiàn)它。這很可能讓你具有將這個簡單的條件隨機(jī)場示例加以改造，用于更復(fù)雜問題所需要的直觀理解。

一、理論

我們對于理論的討論將分為三個部分：1)指定模型參數(shù) 2)如何估計這些參數(shù) 3)利用這些參數(shù)進(jìn)行預(yù)測，這三大類適用于任何統(tǒng)計機(jī)器學(xué)習(xí)模型。因此從這個意義上說，條件隨機(jī)場并沒有什么特別的，但這并不意味著條件隨機(jī)場就和 logistic 回歸模型一樣簡單。我們會發(fā)現(xiàn)，一旦我們要面對一連串的預(yù)測而不是單一的預(yù)測，事情就會變得更加復(fù)雜。

1. 指定模型參數(shù)

在這個簡單的問題中，我們需要擔(dān)心的唯一的參數(shù)就是與從一次投擲轉(zhuǎn)換到下一次投擲狀態(tài)的分布。我們有六種狀態(tài)需要考慮，因此我們將它們存儲在一個 2*3 的「轉(zhuǎn)移矩陣」中。

***列對應(yīng)于「從前一次投擲使用公平骰子的狀態(tài)，轉(zhuǎn)換到當(dāng)前使用公平骰子狀態(tài)的概率或成本(***行的值)，或轉(zhuǎn)換到有偏骰子狀態(tài)的概率(第二行的值)」。因此，***列中的***個元素編碼了在給定我本次投擲使用了公平骰子的前提下，預(yù)測下一次投擲使用公平骰子的概率。如果數(shù)據(jù)顯示，我不太可能在連續(xù)使用公平骰子，模型會學(xué)習(xí)到這個概率應(yīng)該很低，反之亦然。同樣的邏輯也適用于第二列。

矩陣的***和第二列假設(shè)我們知道在前一次投擲中使用了哪個骰子，因此我們必須將***次投擲作為一個特例來對待。我們將把相應(yīng)的概率存儲在第三列中。

2. 參數(shù)估計

假設(shè)給定一個投擲的集合 X* *以及它們相應(yīng)的骰子標(biāo)簽 Y。我們將會找到使整個訓(xùn)練數(shù)據(jù)的負(fù)對數(shù)似然最小的轉(zhuǎn)移矩陣 T。我將會向你展示單個骰子投擲序列的似然和負(fù)對數(shù)似然是什么樣的。為了在整個數(shù)據(jù)集上得到它，你要對所有的序列取平均。

P(x_i | y_i) 是在給定當(dāng)前的骰子標(biāo)簽的前提條件下，觀測到一個給定骰子投擲點數(shù)的概率。舉例而言，如果 y_i 為公平骰子，則 P(x_i | y_i) = 1/6。另一項 T(y_i | y_{i-1}) 是從上一個骰子標(biāo)簽轉(zhuǎn)換到當(dāng)前投資標(biāo)簽的概率，我們可以直接從轉(zhuǎn)移矩陣中讀取出這個概率。

請注意在分母中，我們是怎樣在所有可能標(biāo)簽 y' 的序列上進(jìn)行求和的。在傳統(tǒng)的二分類問題 logistic 回歸中，我們在分母中會有兩個項。但是現(xiàn)在，我們要處理的是標(biāo)注序列，并且對于一個長度為 15 的序列來說，一共有 2^15 種可能的標(biāo)簽序列，所以分母項是十分巨大的。條件隨機(jī)場的「秘密武器」是，它假定當(dāng)前的骰子標(biāo)簽僅僅只取決于之前的骰子標(biāo)簽，來高效地計算這個大規(guī)模求和。

這個秘密武器被稱為「前向-后向算法」。對該算法的深入討論超出了這篇博文的范圍，因此這里不做詳細(xì)的解釋。

3. 序列預(yù)測

一旦我們估計出了我們的轉(zhuǎn)移矩陣，我們可以使用它去找到在給定一個投擲序列的條件下，最有可能的骰子標(biāo)注序列。要做到這一點，最簡單的方法就是計算出所有可能的序列的似然，但這即使對于中等長度的序列也是十分困難的。正如我們在參數(shù)估計中所做的那樣，我們將不得不用一種特殊的算法高效地搜索可能性***的序列。這個算法與「向前-向后算法」很相近，它被稱為「維特比算法」。

二、代碼

PyTorch 是一個在 Python 語言環(huán)境下為訓(xùn)練深度學(xué)習(xí)模型而編寫的深度學(xué)習(xí)庫。盡管我們在這里并不是要進(jìn)行深度學(xué)習(xí)，但 PyTorch 的自動微分庫將幫助我們通過梯度下降算法訓(xùn)練條件隨機(jī)場模型，而無需我們手動計算任何梯度。使用 PyTorch 會迫使我們實現(xiàn)「向前-向后算法」的前向部分以及「維特比算法」，這比我們直接使用專門的條件隨機(jī)場構(gòu)建的 Python 包更有指導(dǎo)意義。

首先，讓我們先設(shè)想一下結(jié)果應(yīng)該是什么樣的。我們需要一種方法去計算給定骰子標(biāo)簽時，對于任意投擲序列的對數(shù)似然度，下面我們給出一種可能的方法：

def neg_log_likelihood(self, rolls, states): 
 """Compute neg log-likelihood for a given sequence. 
 
 Input:  
 rolls: numpy array, dim [1, n_rolls]. Integer 0-5 showing value on dice. 
 states: numpy array, dim [1, n_rolls]. Integer 0, 1. 0 if dice is fair. 
 """ 
 loglikelihoods = self._data_to_likelihood(rolls) 
 states = torch.LongTensor(states) 
 
 sequence_loglik = self._compute_likelihood_numerator(loglikelihoods, states) 
 denominator = self._compute_likelihood_denominator(loglikelihoods) 
 return denominator - sequence_loglik 

這個方法做了三件主要的事情：1)將骰子的值映射到一個似然函數(shù)上 2)計算對數(shù)似然項的分子 3)計算對數(shù)似然項的分母。

讓我們首先來處理「_data_to_likelihood」方法，它幫助我們?nèi)?zhí)行上面提到的步驟 1。我們將要做的是，創(chuàng)建一個維度為 6*2 的矩陣，其中***列是用公平骰子擲到 1-6 的似然度，第二列是用有偏骰子擲到 1-6 的似然度。這個問題中的矩陣的形式如下所示：

array([[-1.79175947, -3.21887582], 
 [-1.79175947, -3.21887582], 
 [-1.79175947, -3.21887582], 
 [-1.79175947, -3.21887582], 
 [-1.79175947, -3.21887582], 
 [-1.79175947, -0.22314355]]) 

現(xiàn)在，如果我們看到一個投擲的點數(shù)為「4」，我們可以直接選擇矩陣中的第四行。這個向量中的***個元素是用公平骰子得到「4」的對數(shù)似然 log(1/6)，而第二個元素是用有偏骰子得到「4」的對數(shù)似然 log(0.04)。代碼如下：

def _data_to_likelihood(self, rolls): 
 """Converts a numpy array of rolls (integers) to log-likelihood. 
 self.loglikeligood is a matrix of 6 x 2 in our case.  
 Input is one [1, n_rolls] 
 """ 
 log_likelihoods = self.loglikelihood[rolls] 
 return Variable(torch.FloatTensor(log_likelihoods), requires_grad=False) 

接下來，我們將編寫計算對數(shù)似然分子和分母的方法。

def _compute_likelihood_numerator(self, loglikelihoods, states): 
 """Computes numerator of likelihood function for a given sequence. 
 
 We'll iterate over the sequence of states and compute the sum  
 of the relevant transition cost with the log likelihood of the observed 
 roll.  
 Input: 
 loglikelihoods: torch Variable. Matrix of n_obs x n_states.  
 i,j entry is loglikelihood of observing roll i given state j 
 states: sequence of labels 
 Output: 
 score: torch Variable. Score of assignment.  
 """ 
 prev_state = self.n_states 
 score = Variable(torch.Tensor([0])) 
 for index, state in enumerate(states): 
 score += self.transition[state, prev_state] + loglikelihoods[index, state] 
 prev_state = state 
 return score 
 
 def _compute_likelihood_denominator(self, loglikelihoods): 
 """Implements the forward pass of the forward-backward algorithm. 
 
 We loop over all possible states efficiently using the recursive 
 relationship: alpha_t(j) = \sum_i alpha_{t-1}(i) * L(x_t | y_t) * C(y_t | y{t-1} = i) 
 Input: 
 loglikelihoods: torch Variable. Same input as _compute_likelihood_numerator. 
 This algorithm efficiently loops over all possible state sequences 
 so no other imput is needed. 
 Output: 
 torch Variable.  
 """ 
 
 # Stores the current value of alpha at timestep t 
 prev_alpha = self.transition[:, self.n_states] + loglikelihoods[0].view(1, -1) 
 
 for roll in loglikelihoods[1:]: 
 alpha_t = [] 
 
 # Loop over all possible states 
 for next_state in range(self.n_states): 
 
 # Compute all possible costs of transitioning to next_state 
 feature_function = self.transition[next_state,:self.n_states].view(1, -1) +\ 
 roll[next_state].view(1, -1).expand(1, self.n_states) 
 
 alpha_t_next_state = prev_alpha + feature_function 
 alpha_t.append(self.log_sum_exp(alpha_t_next_state)) 
 prev_alpha = torch.cat(alpha_t).view(1, -1) 
 return self.log_sum_exp(prev_alpha) 

就是這樣!我們現(xiàn)在已經(jīng)擁有了學(xué)習(xí)轉(zhuǎn)移矩陣所需的全部代碼。但是，如果我們想要在訓(xùn)練完模型之后作出預(yù)測，我們就必須編寫維特比算法：

def _viterbi_algorithm(self, loglikelihoods): 
 """Implements Viterbi algorithm for finding most likely sequence of labels. 
 
 Very similar to _compute_likelihood_denominator but now we take the maximum 
 over the previous states as opposed to the sum.  
 Input: 
 loglikelihoods: torch Variable. Same input as _compute_likelihood_denominator. 
 Output: 
 tuple. First entry is the most likely sequence of labels. Second is 
 the loglikelihood of this sequence.  
 """ 
 
 argmaxes = [] 
 
 # prev_delta will store the current score of the sequence for each state 
 prev_delta = self.transition[:, self.n_states].view(1, -1) +\ 
 loglikelihoods[0].view(1, -1) 
 
 for roll in loglikelihoods[1:]: 
 local_argmaxes = [] 
 next_delta = [] 
 for next_state in range(self.n_states): 
 feature_function = self.transition[next_state,:self.n_states].view(1, -1) +\ 
 roll.view(1, -1) +\ 
 prev_delta 
 most_likely_state = self.argmax(feature_function) 
 score = feature_function[0][most_likely_state] 
 next_delta.append(score) 
 local_argmaxes.append(most_likely_state) 
 prev_delta = torch.cat(next_delta).view(1, -1) 
 argmaxes.append(local_argmaxes) 
 
 final_state = self.argmax(prev_delta) 
 final_score = prev_delta[0][final_state] 
 path_list = [final_state] 
 
 # Backtrack through the argmaxes to find most likely state 
 for states in reversed(argmaxes): 
 final_state = states[final_state] 
 path_list.append(final_state) 
 
 return np.array(path_list), final_score 

我們實現(xiàn)的代碼還有很多，但我在這里僅僅只包含了我們在理論部分討論過的核心功能。

三、利用數(shù)據(jù)進(jìn)行模型評價

我使用下面概率模擬得到的數(shù)據(jù)，并對模型進(jìn)行評價：

• P(序列中的***個骰子為公平骰子)=0.5
• P(當(dāng)前為公平骰子|上一次為公平骰子)=0.8
• P(當(dāng)前為有偏骰子|上一次為有偏骰子)=0.35

請查看我編寫的 Notebook 去看看我是如何生成條件隨機(jī)場模型并且訓(xùn)練它的。

Notebook 地址：

https://github.com/freddyalfonsoboulton/crf_tutorial/blob/master/crf_demo.ipynb

我們要做的***件事就是看看估計出的轉(zhuǎn)移矩陣是怎樣的。模型會學(xué)習(xí)如果在前一次使用了公平骰子，那么這一次更有可能使用公平骰子進(jìn)行投擲(-1.38 < -0.87)。模型還學(xué)到在使用了有偏骰子后，我們更有可能使用公平骰子，但這和使用有偏投擲的可能性差別并不是很大(-1.38 < -0.87)。該模型在***次投擲時給兩種骰子分配相同的代價(0.51 ~ -0.54)。

array([[-0.86563134, -0.40748784, -0.54984874], 
 [-1.3820231 , -0.59524935, -0.516026 ]], dtype=float32) 

接下來，我們來看看對于一個特定的投擲序列的預(yù)測結(jié)果如何：

# observed dice rolls 
array([2, 3, 4, 5, 5, 5, 1, 5, 3, 2, 5, 5, 5, 3, 5]) 
# corresponding labels. 0 means fair 
array([0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1]) 
# predictions 
array([0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0]) 

模型識別出「6」的長序列(在上面的代碼中實際顯示為「5」，因為我們是從「0」開始的)來自于有偏的骰子，這是有意義的。請注意，模型并沒有將所有的「6」都分配給有偏的骰子，就像對第八次投擲的預(yù)測那樣。這是因為在這個「6」之前，我們很確信使用了公平骰子(我們擲出了一個「2」)并且從公平骰子狀態(tài)轉(zhuǎn)換到有偏骰子狀態(tài)的可能性較小。我認(rèn)為這種錯誤是可以接受的，因此模型是很成功的。

結(jié)論

我向你展示了條件隨機(jī)場背后的一小部分理論知識，同時也展示了你如何才能實現(xiàn)一個用于簡單問題的條件隨機(jī)場。當(dāng)然，相關(guān)的知識遠(yuǎn)遠(yuǎn)比我在這里所能夠涵蓋到的要多。所以我建議各位讀者查看更多相關(guān)的資源。

原文鏈接：

https://towardsdatascience.com/conditional-random-field-tutorial-in-pytorch-ca0d04499463

【本文是51CTO專欄機(jī)構(gòu)“機(jī)器之心”的原創(chuàng)譯文，微信公眾號“機(jī)器之心( id: almosthuman2014)”】

戳這里，看該作者更多好文