大型貝氏網路推論之時間與準度權衡演算法

在不同的領域中，貝氏網路是一種功能強大的分析工具。推論引擎則是貝氏網路中最重要的部分，負責處理接收到的訊息藉由機率的方式給出結論。推論引擎可以藉由不同的演算法來實現，並且加速推論的效率。由於傳統的精確推論演算法在大型貝氏網路中，會大幅降低演算效率導致無法運作。因此，我們提出了一種新的演算法，稱作KLA演算法，來解決在大型複雜的貝氏網路中推論的問題。KLA演算法可透過權衡時間和精準度來提升推論的效率，而且所需要的記憶體空間會是所有推論演算法中最小的。因此，此演算法能夠更容易的將貝氏網路實現在記憶體受限制的應用中。為了評估在不同結構下KLA演算法的表現，我們設計了一系列的實驗來觀察準度和計算時間的結果並且和傳統聯結樹演算法來做比較。我們也將KLA演算法運用在現實中的案例上來觀察模擬的成果。

關鍵字

貝氏網路；精準和近似推論；推論演算法；大型網路；時間準度權衡

並列摘要

Bayesian networks (BNs) are powerful tools in diverse fields. The most important part is the inference engine, which draws conclusions by updating probabilities on the basis of the given knowledge. The inference engine can be implemented by using different algorithms, which help BNs draw various conclusions efficiently. Since traditional exact methods collapse when applied to large-scale methods, we propose a new algorithm, called KLA-algorithm, to solve the problem of drawing an inference in a large and complex system. The KLA-algorithm always has tractable computational time and a trade-off with precision. The required memory in KLA-algorithm is the minimum as compared to the other inference algorithms. This advantage extends large-scale BNs to some limited resource applications. In order to verify the KLA-algorithm in a different graph structure, we design a series experiment to compare with the junction tree algorithm and discuss the performance of precision and computation time. We also apply the KLA-algorithm to real-world data in order to carry out some simulations.

並列關鍵字

Bayesian networks ； Exact and approximate inference ； Inference algorithms ； Large-scale networks ； Time-Precision Tradeoff

參考文獻

[1] Booker, L. B., and Hota, N. “Probabilistic Reasoning about Ship Images,” Uncertainty in Artificial Intelligence, vol. 2, pp. 371-379, 1988.

[5] Chow, C. K., and Liu, C.N. “Approximating Discrete Probability Distributions with Dependence Trees,” IEEE Transactions on Information Theory, vol. 14, no. 3, pp. 462-467, 1968.

[6] Cooper, G., and Hersovits, E. “A Bayesian Method for the Introduction of Probabilistic Networks from Data,” Machine Learning, vol. 9, pp. 309-347, 1992.

[9] Diez, F. J. “Local Conditioning in Bayesian Networks,” Artificial Intelligence, vol. 87, pp. 1-20, 1996.

[10] Fishelson, M. and Geiger, D. “Optimizing Exact Genetic Linkage Computations,” Proceedings of 7th Conference on Computational Molecular Biology (RECOMB), pp. 114-121, 2003.

國際替代計量

大型貝氏網路推論之時間與準度權衡演算法

全文下載

主題瀏覽