臺灣博碩士論文加值系統

簡單神經網路(Simple Neural Network, NN)為機器學習中，監督式學習的一種，其在函數學習與分類上也都有不錯的效果；而隱藏馬可夫模型(Hidden Markov Model, HMM)為一種藉由觀測數據去訓練或者估計隱藏狀態的模型，其對於擁有時序資料或隱藏變量的系統均有非常好的應用，因此本論文主要以GPS時序資料作為基礎，並將其使用於簡單神經網路，使GPS資料能夠因為其位置、速度的不同分類成適合HMM使用的觀測數據，然後再將使用者的行程視為隱藏狀態，以期許HMM能夠對GPS資料估測出使用者的行程。其中GPS資料採用行動手機作為GPS接收機來收取資料。
在本論文中，首先驗證了HMM其學習問題(Baum–Welch演算法)與解碼問題(維特比算法, Viterbi algorithm)的精準度，然後再分析GPS資料於簡單神經網路中的分類結果，最後才將HMM與簡單神經網路做結合使GPS資料能夠有效估計出其行程，而從實驗結果可以看出我們所提出方法的準確度堪稱優良。

In the field of machine learning, Neural Network (NN) is a type of supervised training method, which has good results in function learning and classification. Hidden Markov Model (HMM) is a kind of model which training and estimate hidden state by observations data, and it is brilliant for systems with time series data or hidden variables. In this thesis, we mainly uses GPS time series data as the basis and the GPS data is fed into a Simple Neural Network to classify the user’s activities based on the position and speed readings obtained from the GPS receiver. After that, the user's activities which are served as hidden states, along with the GPS position and speed data, which is served as the observed state, are then input into the HMM to identify the user’s personal schedule.
In this thesis, we verify the accuracy of HMM’s learning problem (Baum–Welch algorithm) and decoding problem (Viterbi algorithm) first, and then we analyze the result of classification where GPS data is classified in a Simple Neural Network. Finally, we combine HMM with Simple Neural Network to make GPS data being able to effectively estimate user’s activities. From the experimental results, we can see that the accuracy of estimated activities is well.

摘要 i
Abstract ii
目錄 iii
圖次 v
表次 vii
第一章、緒論 1
1.1 前言 1
1.2 研究目的與動機 1
1.3 文獻回顧 2
第二章、隱藏馬可夫模型 3
2.1 HMM基本架構 3
2.1.1 馬可夫鏈 4
2.1.2 隱馬爾可夫模型 6
2.2 HMM的三個基本問題 8
2.2.1 計算問題：前向算法、後向算法 8
2.2.2 解碼問題：Viterbi 演算法 16
2.2.3 學習問題：Baum–Welch演算法 18
2.3 HMM實作問題 22
2.3.1 起始參數設定 22
2.3.2 訓練資料處理 23
2.3.3 Data Scaling 24
第三章、簡單神經網路 28
3.1 類神經網路 28
3.1.1 神經網路架構 29
3.1.2 激勵函數 30
3.2 學習法則 32
3.2.1 前向傳遞運算 33
3.2.2 梯度下降法 34
3.2.3 倒傳遞演算法 36
3.2.4 資料量化 39
第四章、實驗與結果分析 40
4.1 實驗環境與設備 40
4.2 HMM精準度測試 41
4.2.1 HMM-訓練 41
4.2.2 HMM-維特比算法 47
4.3 NN分類結果 48
4.4 行動資料估測結果 62
第五章、結論與未來展望 76
5.1 結論 76
5.2未來展望 76
參考文獻 77

[1] Liao, L., Patterson, D. J., Fox, D., & Kautz, H. (2006). Building personal maps from GPS data. Annals of the New York Academy of Sciences, 1093(1), 249-265.

[2] Stratonovich, R.L. (1960). Conditional Markov Processes. Theory of Probability and Its Applications. 5(2): 156–178. doi:10.1137/1105015

[3] Forney Jr, G. D. (2005). The viterbi algorithm: A personal history. arXiv preprint cs/0504020.

[4] Baum, L. E., Petrie, T. (1966). Statistical Inference for Probabilistic Functions of Finite State Markov Chains. The Annals of Mathematical Statistics. 37 (6): 1554–1563. doi:10.1214/aoms/1177699147.

[5] Baum, L. E., Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematical Society. 73 (3): 360. doi:10.1090/S0002-9904-1967-11751-8.

[6] Baum, L. E., Sell, G. R. (1968). Growth transformations for functions on manifolds. Pacific Journal of Mathematics. 27 (2): 211–227. doi:10.2140/pjm.1968.27.211.

[7] Baum, L. E., Petrie, T., Soules, G., Weiss, N. (1970). A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. The Annals of Mathematical Statistics. 41 (1): 164–171. doi:10.1214/aoms/1177697196.

[8] Baum, L.E. (1972). An Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov Process. Inequalities. 3: 1–8.

[9] Baker, J. (1975). The DRAGON system—An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing. 23: 24–29. doi:10.1109/TASSP.1975.1162650

[10] Bishop, M., Thompson, E. (1986). Maximum Likelihood Alignment of DNA Sequences. Journal of Molecular Biology. 190 (2): 159–165. doi:10.1016/0022-2836(86)90289-5.

[11] McCulloch, W., Walter, P. (1943). A Logical Calculus of Ideas Immanent in Nervous Activity. Bulletin of Mathematical Biophysics. 5 (4): 115–133. doi:10.1007/BF02478259.

[12] Rosenblatt, F. (1958). The Perceptron: A Probabilistic Model For Information Storage And Organization In The Brain. Psychological Review. 65 (6): 386–408. doi:10.1037/h0042519

[13] Werbos, P. J. (1994). The Roots of Backpropagation : From Ordered Derivatives to Neural Networks and Political Forecasting. New York: John Wiley & Sons.

[14] Rumelhart, D. E.; Hinton, G. E.; Williams, Ronald J. (1986). Learning representations by back-propagating errors. Nature. 323 (6088): 533–536. doi:10.1038/323533a0.

[15] Rabiner, L. R. (1989). A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257-286.

[16] Borman, S. (2004). The expectation maximization algorithm-a short tutorial. Submitted for publication, 41.

[17] Manning, C. D., Manning, C. D., & Schütze, H. (1999). Foundations of statistical natural language processing. MIT press. p338-339

[18] Davis, R. I., Lovell, B. C., & Caelli, T. (2002, August). Improved estimation of hidden markov model parameters from multiple observation sequences. In Object recognition supported by user interaction for service robots (Vol. 2, pp. 168-171). IEEE.

[19] Tu, S. (2015). Derivation of baum-welch algorithm for hidden markov models. URL: https://people. eecs. berkeley. edu/~ stephentu/writeups/hmm-baum-welch-derivation. pdf.


[20] 顧正偉（2005）。利用多觀察值型隱馬可夫模型進行人體動作辨識。國立交通大學資訊工程系所碩士論文，新竹市。 取自https://hdl.handle.net/11296/383tud

[21] Haykin, S. (2010). Neural Networks and Learning Machines, 3/E. Pearson Education India.

[22] Snyder, J. P. (1987). Map projections--A working manual (Vol. 1395). US Government Printing Office. P60-64