The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Dans cet article, le problème informatique lié au problème de l'apprentissage des réseaux de croyances bayésiens (BBN) basés sur le principe de longueur minimale de description (MDL) est abordé. Sur la base d'une formule asymptotique de longueur de description, nous appliquons la technique de branchement et de liaison pour trouver de véritables structures de réseau. L'algorithme de recherche résultant économise considérablement le calcul tout en recherchant avec succès la structure du réseau avec la valeur minimale de la formule. Jusqu'à présent, il n'y a pas eu d'algorithme de recherche qui trouve la solution optimale pour des exemples de taille pratique et un ensemble de structures de réseau dans le sens de la probabilité a posteriori maximale, et les recherches heuristiques telles que K2 et K3 piègent les optima locaux en raison de la glouton nature même lorsque la taille de l’échantillon est grande. L'algorithme proposé, puisqu'il minimise la longueur de la description, sélectionne finalement la véritable structure du réseau lorsque la taille de l'échantillon tend vers l'infini.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Joe SUZUKI, "Learning Bayesian Belief Networks Based on the MDL Principle: An Efficient Algorithm Using the Branch and Bound Technique" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 2, pp. 356-367, February 1999, doi: .
Abstract: In this paper, 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_2_356/_p
Copier
@ARTICLE{e82-d_2_356,
author={Joe SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Learning Bayesian Belief Networks Based on the MDL Principle: An Efficient Algorithm Using the Branch and Bound Technique},
year={1999},
volume={E82-D},
number={2},
pages={356-367},
abstract={In this paper, 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.},
keywords={},
doi={},
ISSN={},
month={February},}
Copier
TY - JOUR
TI - Learning Bayesian Belief Networks Based on the MDL Principle: An Efficient Algorithm Using the Branch and Bound Technique
T2 - IEICE TRANSACTIONS on Information
SP - 356
EP - 367
AU - Joe SUZUKI
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 1999
AB - In this paper, 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.
ER -