林智仁Lin, Chih-Jen臺灣大學:資訊工程學研究所陳鵬仁Chen, Peng-JenPeng-JenChen2010-06-092018-07-052010-06-092018-07-052009U0001-1108200914273000http://ntur.lib.ntu.edu.tw//handle/246246/185436條件隨機場是一個適合用來標記序列性資料的模組。由於考慮序列中所有可能的標籤組合，條件隨機場在學習及預測階段都非常耗時。牛頓法在最佳化的最後階段具有較快的收斂性質，因此我們採用牛頓法來解條件隨機場。海森矩陣向量乘積是整個計算過程中最耗時的部份。本篇論文提出一個新的動態規劃技巧，可以在多項式時間複雜度內完成海森矩陣向量乘積。Conditional Random Fields (CRFs) is a useful technique toabel 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.TABLE OF CONTENTS試委員審定書 ii要 iiiBSTRACT iv.Introduction 1I.Conditional Random Fields 3.1 Named-Entity Recognition Problem 3.2 Conditional Random Fields 5.3 Applying CRFs on NER Problems 6II.Trust Region Newton Methods 8.1 A Trust Region Newton Method 8.2 Hessian-vector Product in Conjugate Gradient 10.3 Gradient Calculation 12V.Dynamic Programming Formula for Hessian-vector Product 16.1 Calculation of (4.3) 18.2 Calculation of (4.4) 23.3 Overall Procedure and Time/Memory Analysis 24.Conclusions 27IBLIOGRAPHY 281435835 bytesapplication/pdfen-US共軛梯度法信賴區間牛頓法最大熵值法條件隨機場conjugate gradient methodstrust region Newton methodsmaximum entropyconditional random fieldsthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185436/1/ntu-98-R96922049-1.pdf