New Advances and Theoretical Insights into EDML

Khaled S. Refaat, Arthur Choi, Adnan Darwiche
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:704-713, 2012.

Abstract

EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-refaat12a, title = {New Advances and Theoretical Insights into {EDML}}, author = {Refaat, Khaled S. and Choi, Arthur and Darwiche, Adnan}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {704--713}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/refaat12a/refaat12a.pdf}, url = {https://proceedings.mlr.press/r10/refaat12a.html}, abstract = {EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T New Advances and Theoretical Insights into EDML %A Khaled S. Refaat %A Arthur Choi %A Adnan Darwiche %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-refaat12a %I PMLR %P 704--713 %U https://proceedings.mlr.press/r10/refaat12a.html %V R10 %X EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM. %Z Reissued by PMLR on 04 October 2026.
APA
Refaat, K.S., Choi, A. & Darwiche, A.. (2012). New Advances and Theoretical Insights into EDML. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:704-713 Available from https://proceedings.mlr.press/r10/refaat12a.html. Reissued by PMLR on 04 October 2026.

Related Material