Learning Baysian Networks based on the MDL principle

基于MDL原理学习贝叶斯网络

• 批准号: 09680367
• 负责人: SUZUKI Joe
• 金额: $ 2.11万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1997
• 资助国家: 日本
• 起止时间: 1997 至 1998
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09680367/
• 关键词: MDL principle; Baysian Networks; machine learning; a prior knowledge; lranch and bound lechuzue; 帰納推論; ネットワーク構造

In this study, the computational issue in the problem of learning Bayesian belief networks (BBNs) based on the minimum description length (MDL) principle is addressed.Based on an asymptotic formula of description length, we apply the branch and bound technique to finding true network structures.The resulting algorithm searches considerably saves the computation yet successfully searches the network structure with the minimum value of the formula.Thus far, there has been no search algorithm that finds the optimal solution for examples of practical size and a set of network structures in the sense of the maximum posterior probability, and heuristic searches such as K2 and K3 trap in local optima due to the greedy nature even when the sample size is large.The proposed algorithm, since it minimizes the description length, eventually selects the true network structure as the sample size goes to infinity.

本文研究了基于最小描述长度（MDL）原则的贝叶斯信念网络（bbn）学习问题中的计算问题。基于描述长度的渐近公式，我们将分支定界技术应用于寻找真实网络结构。所得到的搜索算法大大节省了计算量，并成功地以公式的最小值搜索到网络结构。到目前为止，还没有一种搜索算法能够在最大后验概率的意义上找到实际规模的例子和一组网络结构的最优解，K2和K3等启发式搜索即使在样本量很大的情况下也会因为贪心而陷入局部最优。由于该算法使描述长度最小化，当样本量趋于无穷大时，最终选择出真实的网络结构。

项目成果

Harasawa,Shikata,Suzuki,Imai: "Comparing the MOD and FR reductions in Elliptic Curve Cryptography" Lecture Note on Computer Science,Eurocrypt'99. (to appear). (1999)

Harasawa、Shikata、Suzuki、Imai：“比较椭圆曲线密码学中的 MOD 和 FR 缩减”计算机科学讲义，Eurocrypt99。

Joe Suzuki: ""Learning Baysian Belief Networks Based on the MDL Principle : An Efficient Algorithm Using the Branch and Bound Technique"" IEICE Trans.on Information and Systems. Vol.82-D,No.2. (1999)

Joe Suzuki：“基于 MDL 原理学习贝叶斯信念网络：使用分支定界技术的高效算法”IEICE Trans.on 信息和系统。

Joe Suzuki: ""A Further Result on the Markov Chain Model of GAs and Their Application to SA-like Strategy"" IEEE Trans.on System, Man, and Cybernetics Part B. Vol.28, No.1. 95-102 (1998)

Joe Suzuki：“关于 GA 马尔可夫链模型及其在类 SA 策略中的应用的进一步结果””IEEE Trans.on 系统、人类和控制论 B 部分。第 28 卷，第 1 期。

Joe Suzuki: "“Universal Prediction and Universal Coding"" IEEE Int. Symp. on Inform. Theory. (1998)

Joe Suzuki：“通用预测和通用编码”，IEEE Int。

鈴木 譲,横尾英俊: "情報理論とその応用学会 情報源符号化とデータ圧縮 一無なみ圧縮(分筆)" 培風館, 18 (1999)

Yuzuki Suzuki、Hidetoshi Yokoo：“信息论及其应用社会信息源编码和数据压缩 Ichinomi Compression（Bungu）” Baifukan，18（1999）