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

Newton Methods for Conditional Random Fields

陳鵬仁(Peng-Jen Chen)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00820

摘要

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

關鍵字

共軛梯度法 ； 信賴區間牛頓法 ； 最大熵值法 ； 條件隨機場

並列摘要

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.

並列關鍵字

conjugate gradient methods ； trust region Newton methods ； maximum entropy ； conditional random fields

參考文獻

J. Laff erty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th International Conference on Machine Learning (ICML), pages 282-289, 2001.

C.-J. Lin and J. J. More. Newton's method for large-scale bound constrained problems. SIAM Journal on Optimization, 9:1100-1127, 1999.

D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1):503-528, 1989.

A. Mccallum and W. Li. Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons. In Seventh Conference on Natural Language Learning (CoNLL), 2003.

F. Peng, F. Feng, and A. McCalum. Chinese segmentation and new word detection using conditional random fields. In Proceedings of The 20th International Conference on Computational Linguistics (COLING), pages 562-568, 2004.