應用截斷牛頓法於條件隨機場

Abstract

條件隨機場是一個適合用來標記序列性資料的模組。由於考慮序列中所有可能的標籤組合，條件隨機場在學習及預測階段都非常耗時。牛頓法在最佳化的最後階段具有較快的收斂性質，因此我們採用牛頓法來解條件隨機場。海森矩陣向量乘積是整個計算過程中最耗時的部份。本篇論文提出一個新的動態規劃技巧，可以在多項式時間複雜度內完成海森矩陣向量乘積。

Conditional Random Fields (CRFs) is a useful technique to label sequential data. Due to considering all label combinations of a sequence, CRFs' training and testing are time consuming. In this work, we consider a Newton method for training CRFs because of its possible fast final convergence. The computational bottleneck is on the Hessian-vector product. We propose a novel dynamic programming technique to calculate it in polynomial time.