多樣性自動機之學習演算法與其量化分析

Quantitative Analysis using Multiplicity Automata Learning

洪文起(Wen-Chi, Hung)

指導教授 ： 王凡

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

https://doi.org/10.6342/NTU201701657

摘要

此篇論文應用機率近似模型學習演算法學習多樣性自動機。該演算法會產生目標軟體之多樣性自動機模型，並將其應用於量化分析。使用產生之多樣性自動機模型，我們設計了一系列演算法可以預測軟體量化分析目標軟體的最大值與平均值等特性。此外，我們修改該演算法，使其在輸入字母數量並非固定時也可以通用。在此片論文中我們實際測試了五種不同類型的軟體，實驗證明我們預測的結果與暴力法算得之結果相當接近，足以證明此演算法可以產生一些傳統難以預測的數據，並具有相當高的可信度。

關鍵字

軟體測試 ； 機率近似正確 ； 機器學習 ； 多樣性自動機 ； 量化分析

並列摘要

In this paper, we apply a probably approximately correct (PAC) learning algorithm for multiplicity automata which can generate a quantitative model of target system behaviors with a statistical guarantee. By using the generated multiplicity automata model, we apply two analysis algorithms to estimate the minimum, maximum and average values of system behaviors. Also, we demonstrate how to apply the learning algorithm when the alphabet symbol size is not fixed. The result of the experiment is encouraging; Our approach made the estimation which is as precise as the exact reference answer obtains by a brute force enumeration.

並列關鍵字

software testing ； probably approximately correct ； machine learning ； quantitative analysis ； multiplicity automata

參考文獻

2. Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation 75(2) (1987) 87–106

3. Angluin, D.: Queries and concept learning. Machine Learning 2(4) (1988) 319–342

4. Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. JACM 47(3) (2000) 506–530

5. Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput. 25(6) (1996) 1268–1280

7. Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numerica 4 (1995) 1–51