條件隨機場之CRF++源碼詳解-預測

這篇文章主要講解CRF++實現預測的過程，預測的演算法以及代碼實現相對來說比較簡單，所以這篇文章理解起來也會比上一篇條件隨機場訓練的內容要容易。

預測

上一篇條件隨機場訓練的源碼詳解中，有一個地方並沒有介紹。 就是訓練結束後，會把待優化權重alpha等變數保存到文件中，也就是輸出到指定的模型文件。在執行預測的時候會從模型文件讀出相關的變數，這個過程其實就是數據序列化與反序列化，該過程跟條件隨機場演算法關係不大，因此為了突出重點源碼解析里就沒有介紹這部分，有興趣的朋友可以自己研究一下。

CRF++預測的入口代碼在crf_test.cpp的main函數中，最終會調用tragger.cpp的int crfpp_test(const Param &param)函數，期間會做一些輸入參數的處理、異常處理、讀取模型文件等操作。一切準備就緒就會打開待預測的文件，進行預測。正式探討預測代碼之前，我們先看下預測的理論基礎。條件隨機場的預測用到了維特比演算法，公式如下：

y

?

=argmax

y

P

w

(y|x)

=argmax

y

exp{∑

K

k=1

w

k

f

k

(y,x)}

Z

w

(x)

=argmax

y

exp{∑

k=1

K

w

k

f

k

(y,x)}

=argmax

y

∑

k=1

K

w

k

f

k

(y,x)

y?=arg?maxyPw(y|x)=arg?maxyexp?{∑k=1Kwkfk(y,x)}Zw(x)=arg?maxyexp?{∑k=1Kwkfk(y,x)}=arg?maxy ∑k=1Kwkfk(y,x)

從公式我們可以看出，我們求的概率最大值就是要求代價最大。接下來就看下CRF++的源碼，代碼在tragger.cpp的crfpp_test函數中：

while (*is) {//is是打開的測試文件，可以輸入多個測試文件做預測
tagger.parse_stream(is.get(), os.get());
}
bool TaggerImpl::parse_stream(std::istream *is,
std::ostream *os) {
if (!read(is) || !parse()) {//read函數在特徵篇講過，不再贅述，調用parse函數進行預測
return false;
}
if (x_.empty()) {
return true;
}
toString(); //格式化輸出，-v 會輸出每個詞預測為某個label的概率，-n會輸出預測序列概率最大的前n個，如果理解上一篇訓練過程，再看這個函數就比較容易理解，無非就是概率計算，這裡不再贅述
os->write(os_.data(), os_.size()); //輸出到輸出文件
return true;
}
bool TaggerImpl::parse() {
CHECK_FALSE(feature_index_->buildFeatures(this)) //構建特徵，同特徵篇代碼，不再贅述
<< feature_index_->what();
if (x_.empty()) {
return true;
}
buildLattice(); //構建無向圖，因為要計算代價最大的序列，訓練篇講過，不再贅述
if (nbest_ || vlevel_ >= 1) {
forwardbackward(); //前向後向演算法，為了計算單詞節點的概率，訓練篇講過，不再贅述
}
viterbi(); //維特比演算法， 做預測的代碼
if (nbest_) {
initNbest();
}
return true;
}
void TaggerImpl::viterbi() {
for (size_t i = 0; i < x_.size(); ++i) { //遍歷每個詞
for (size_t j = 0; j < ysize_; ++j) { //遍歷每個詞的每個label
double bestc = -1e37;
Node *best = 0;
const std::vector<Path *> &lpath = node_[i][j]->lpath;
for (const_Path_iterator it = lpath.begin(); it != lpath.end(); ++it) { //從前一個詞到當前詞的代價之和 = max(前一個節點的代價 + 前一個節點的邊代價 + 當前節點代價）
double cost = (*it)->lnode->bestCost +(*it)->cost +
node_[i][j]->cost;
if (cost > bestc) { //記錄截止當前節點最大的代價， 以及對應的前一個節點
bestc = cost;
best = (*it)->lnode;
}
}
node_[i][j]->prev = best; //記錄前一個幾點
node_[i][j]->bestCost = best ? bestc : node_[i][j]->cost; //記錄最大的代價值， 如果best = 0代表第一個詞，沒有左邊，最大代價就是節點的代價node_[i][j]->cost
}
}
double bestc = -1e37;
Node *best = 0;
size_t s = x_.size()-1;
for (size_t j = 0; j < ysize_; ++j) { //遍歷最後一個詞的節點，截止到最後一個詞的代價最大值就是整個句子的最大代價
if (bestc < node_[s][j]->bestCost) {
best = node_[s][j];
bestc = node_[s][j]->bestCost;
}
}
for (Node *n = best; n; n = n->prev) {//記錄代價最大的預測序列
result_[n->x] = n->y;
}
cost_ = -node_[x_.size()-1][result_[x_.size()-1]]->bestCost;
}

預測的核心代碼就看完了，大部分復用了訓練過程的邏輯。可以看到預測的過程跟公式是一致的，無非就是求能夠讓代價最大的label序列（標記序列），這就是維特比演算法。

總結

至此，我們的條件隨機場之CRF++源碼詳解系列就結束了，主要涵蓋了特徵處理、訓練以及預測三個核心過程。結合CRF++源碼我們可以更形象的、更通俗的去理解條件隨機場模型。以後想起條件隨機場模型，我們腦海浮現的不再是一堆公式，而是一個無向圖，在圖上進行代價計算、前向後向計算、期望值的計算以及梯度的計算等一系列的過程。希望這個系列對於正在學習條件隨機場的朋友能有幫助，如果本文闡述的有歧義、不通俗、不容易理解的地方，歡迎留言區交流，我將及時更正、回復，希望我們一起提高。

作者：渡碼

原文：https://www.cnblogs.com/duma/p/10344232.html

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