# Hard and Soft EM in Bayesian Network Learning from Incomplete Data  
[PERSON]  
1 Department of Informatics, Systems and Communication, Universita degli Studi di Milano-Bicocca, 20126 Milano, Italy; [EMAIL_ADDRESS] (A.R. ); [EMAIL_ADDRESS] (F.S. ); [EMAIL_ADDRESS] (F.S.) [PERSON]  
1 Department of Informatics, Systems and Communication, Universita degli Studi di Milano-Bicocca, 20126 Milano, Italy; [EMAIL_ADDRESS] (A.R. ); [EMAIL_ADDRESS] (F.S. ); [EMAIL_ADDRESS] (F.S.) [PERSON]  
1 Department of Informatics, Systems and Communication, Universita degli Studi di Milano-Bicocca, 20126 Milano, Italy; [EMAIL_ADDRESS] (A.R. ); [EMAIL_ADDRESS] (F.S. ); [EMAIL_ADDRESS] (F.S.) [PERSON]  
2 Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), 6962 Vignanello, Switzerland 2*  
that is, the binary pattern of values being observed or not for that specific experimental variable. These auxiliary variables are then integrated out in order to compute the expected values of the parameters of the model. The most common approach to learn machine learning models that build on this idea is the _Expectation-Maximisation_ (EM) algorithm [5]; other approaches such as variational inference [6] have seen substantial applications but are beyond the scope of this paper and we will not discuss them further. The EM algorithm comprises two steps that are performed iteratively until convergence: the \"expectation\" (E) step computes the expected values of the sufficient statistics given the current model, and the \"Maximisation\" (M) step updates the model with new parameter estimates. (A statistic is called _sufficient_ for a parameter in a given model if no other statistic computed from the data, including the data themselves, provides any additional information to the parameter's estimation.) A natural way of representing experimental variables, auxiliary variables and their relationships is through graphical models, and in particular Bayesian networks (BNs) [7]. BNs represent variables as nodes in a directed acyclic graph in which arcs encode probabilistic dependencies. The graphical component of BNs allows for automated probabilistic manipulations via belief propagation, which in turn makes it possible to compute the marginal and conditional distributions of experimental variables in the presence of incomplete data. However, learning a BN from data, that is, learning its graphical structure and parameters, is a challenging problem; we refer the reader to [8] for a recent review on the topic. The EM algorithm can be used in its original form to learn the parameters of a BN. The Structural EM algorithm [9; 10] builds on the EM algorithm to implement structure learning: it computes the sufficient statistics required to score candidate BNs in the E-step. However, the Structural EM is computationally demanding due to the large number of candidate models that are evaluated in the search for the optimal BN. Using EM for parameter learning can be computationally demanding as well for medium and large BNs. Hence, practical implementations, e.g., [11; 12], of both often replace belief propagation with single imputation: each missing value is replaced with its expected value conditional on the values observed for the other variables in the same observation. This is a form of _hard EM_ because we are making hard assignments of values; whereas using belief propagation would be a form of _soft EM_. This change has the effect of voiding the theoretical guarantees for the Structural EM in [9; 10], such as the consistency of the algorithm. Hard EM, being a form of single imputation, is also known to be problematic for learning the parameters of statistical models [13]. In this paper, we investigate the impact of learning the parameters and the structure of a BN using hard EM instead of soft EM with a comprehensive simulation study covering incomplete data with a wide array of different characteristics.