劉長遠Liou, Cheng-Yuan臺灣大學:資訊工程學研究所彭智楹Peng, Jyh-YingJyh-YingPeng2010-06-022018-07-052010-06-022018-07-052008U0001-1706200810042200http://ntur.lib.ntu.edu.tw//handle/246246/184828本論文提出一個新的序列圖案架構，可以正確並快速的計算出在時間序列資料中圖案出現的機率。此架構利用自動機描述出現圖案的計量，並將這個自動機嵌入一個馬可夫鏈，而圖案計量的分佈即可由馬可夫鏈的分佈求得。這個架構可以用來分析連續或離散的序列資料，只要圖案是出現於資料模型中的一個馬可夫來源。透過這個新方法，可以簡單並有效率的取得圖案計量的共同分佈。這個新方法的應用範圍極廣，本論文中將示範如何將之應用於時間序列中變異點的估計。This thesis introduces a new pattern statistics framework, which enables exact and efficient calculation of probabilities of pattern occurrences in sequence data. Statistics of pattern occurrences in data are formulated in terms of finite automata state transitions embedded into a Markov chain. This enables the analysis of continuous or discrete sequence data where the underlying generation process is governed by a Markov source, and where occurrences of specific patterns in the Markov state sequence is of interest. Through this new methodology, the full joint distribution of pattern statistics can be obtained in a conceptually simple and computationally efficient way. This new methodology can be adopted for many applications, and is here applied to change point estimation problems as an example.1 Introduction 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Contributions and Recognition . . . . . . . . . . . . . . . . . . . . . 3 The History of Pattern Statistics 7.1 Early Works related to Runs . . . . . . . . . . . . . . . . . . . . . . 8.2 Runs Conditional on Composition . . . . . . . . . . . . . . . . . . . 17.3 Recurrent Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19.4 Distributions of Order k . . . . . . . . . . . . . . . . . . . . . . . . 27.5 Combinatorial Enumeration . . . . . . . . . . . . . . . . . . . . . . 38.6 Waiting Time for Finite Regular Languages . . . . . . . . . . . . . 41.7 System of Equations of Probability Generating Functions . . . . . . 50.8 Markov Chain Embedding . . . . . . . . . . . . . . . . . . . . . . . 58.9 The Final Word . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Pattern Statistics Through Markov Chain Embedding 62.1 Markov Chain Embedding of Deterministic Finite Automata . . . . 62.2 Patterns as Regular Languages . . . . . . . . . . . . . . . . . . . . 65.3 Recent Advances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69.4 Applications of Pattern Statistics . . . . . . . . . . . . . . . . . . . 70.4.1 Pattern Detection . . . . . . . . . . . . . . . . . . . . . . . . 70.4.2 Pattern Searching . . . . . . . . . . . . . . . . . . . . . . . . 71.4.3 Sequence Segmentation . . . . . . . . . . . . . . . . . . . . . 75.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Pattern Statistics Applied to Change Point Estimation 84.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86.2 Models and Methodology . . . . . . . . . . . . . . . . . . . . . . . . 87.2.1 Hidden Markov Models of Change Points . . . . . . . . . . . 87.2.2 Waiting Time Distributions of Change Points . . . . . . . . 88.2.3 Markov Chain Embedding of Change Points . . . . . . . . . 90.3 Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3.1 U.S. Gross National Product . . . . . . . . . . . . . . . . . . 94.3.2 U.S. Treasury Bill Data . . . . . . . . . . . . . . . . . . . . 98.3.3 fMRI Data from Anxiety-Inducing Experiment . . . . . . . . 104.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Conclusion 111ibliography 113application/pdf1542919 bytesapplication/pdfen-US連列與圖案圖案計量時間序列分析馬可夫鏈隱含馬可夫模型馬可夫鏈嵌入有限自動機形式語言變異點非平穩型時間序列Runs and patternspattern statisticstime series analysisMarkov chainshidden Markov modelsMarkov chain embeddingdeterministic finite automataregular languageschange pointsnon-stationarity time seriesthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184828/1/ntu-97-F91922063-1.pdf