加權有限自動機最小化

On Minimizing Weighted Finite Automata

黃亭遠(Ting-Yuan Huang)

指導教授 ： 顏嗣鈞

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

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

摘要

加權自動機是一種可以用來模塑許多系統, 非常廣泛的數學模型. 在不同的研究領
域裡它有不一樣的名字, 例如機率有限自動機 (probabilistic finite automata, PFA) 和隱藏式馬可夫模型 (hidden Markov model, HMM) 等等. 這些模型在很多研究領域裡皆具極為重要的地位, 例如機器學習 (machine learning), 語音處理 (speech processing), 圖像辨認 (pattern recognition), 語言塑模 (language modeling), 生物資訊 (bioinformatics), 電路測試 (circuit testing), 影像處理 (image processing) 及時間序列分析 (time series analysis). 因為加權自動機有著非常多的應用領域, 故只要有些微的理論突破或改進, 影響便非常深遠. 在本篇論文中, 藉由探討加權自動機中權重的代數性質及其拓撲結構, 我們引進了重新分佈權重的概念. 我們並將最短路徑問題 (shortest-path problem) 加以推廣, 使其定義於各路徑之最大下界(infimum) 之上, 同時給出一有效之演算法解決之. 我們提出之演算法不僅是本篇論文中縮小自動機的方法核心, 也能應用於辨別整數自動機 (Z-automata) 的等價性. 我們的方法能有效的縮小自動機, 對於之前文獻中的方法有十分顯著的改進.

關鍵字

加權有限自動機 ； 最小化 ； 機率有限自動機 ； 隱藏式馬可夫模型

並列摘要

Weighted Finite Automata represent a very general model which has many different names such as probabilistic finite automata (PFA), hidden Markov models (HMM), stochastic regular grammars, Markov chains and n-grams. These models play central roles in many domains such as machine learning, speech processing, computational linguistics, pattern recognition, language modeling, bioinformatics, music modeling, circuit testing, image processing, path query and time series analysis. The huge number of applications makes weighted finite automata a very valuable research topic: Even a very small breakthrough or improvement would benefit lots of domains. In this thesis, we introduce the notion of “weight redistribution” by investigating the algebraic properties along with the graphical structure inside weighted finite automata. We also generalize the concept of shortest-path problem to finding infimum along every paths and give an effcient algorithm to solve it. Our algorithm to compute “weight redistribution” not only plays the central role in our minimization algorithm, but also is applicable on determining the equivalence Z-automata. We also give two new algorithms to shrink the state space. These algorithms outperform pervious results.

並列關鍵字

weighted finite automata ； Minimization ； probabilistic finite automata ； hidden Markov model

參考文獻

[1] E. Vidal, F. Thollard, C. de la Higuera, F. Casacuberta, R.C. Carrasco, Probabilistic Finite-State Machines–Part I, IEEE Trans. Pattern Analysis and Machine Intelligence, special issue on syntactic and structural pattern recognition, vol 27, no. 7, pp. 1013-1025, 2005.

[2] A. Paz. Introduction to Probabilistic Automata. Academic Press. New York, NY, 1971.

[3] F. Jelinek. Statistical Methods for Speech Recognition. Cambridge, Massachusetts: The MIT Press, 1998.

[4] R. Carrasco and J. Oncina. Learning stochastic regular grammars by means of a state merging method, ser. Lecture Notes in Computer Science, R. C. Carrasco and J. Oncina, Eds., no. 862. Berlin, Heidelberg: Springer Verlag, 1994, pp. 139-150.

[7] J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.