加權有限自動機最小化

Abstract

加權自動機是一種可以用來模塑許多系統, 非常廣泛的數學模型. 在不同的研究領 域裡它有不一樣的名字, 例如機率有限自動機 (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.