# Hard and Soft EM in Bayesian Network Learning from Incomplete Data
## 2 Methods
### The EM Algorithm and Bayesian Networks  
In the context of BNs, EM can be applied to both parameter learning and structure learning. For the parameter learning, the E-step and M-step become:  
* the _Expectation_ (E) step consists of computing the expected values of the sufficient statistics (the counts \(\{n_{ijk}\}\)) using exact inference along the lines described above to make use of incomplete as well as complete samples;* the _Maximisation_ (M) step takes the sufficient statistics from the E-step and estimates the parameters of the BN. As for structure learning, the Structural EM algorithm [9] implements EM as follows:
* in the E-step, we complete the data by computing the expected sufficient statistics using the current network structure;
* in the M-step, we find the structure that maximises the expected score function for the completed data.  
This approach is computationally feasible because it searches for the best structure inside of the EM, instead of embedding EM inside a structure learning algorithm; and it maintains the convergence guarantees of the original both in its maximum likelihood [9] and Bayesian [10] formulations. However, the Structural EM is still quite expensive because of the large number and the dimensionality of the sufficient statistics that are computed in each iteration. [9] notes: \"Most of the running time during the execution of our procedure is spent in the computations of expected statistics. This is where our procedure differs from parametric EM. In parametric EM, we know in advance which expected statistics are required. [...] In our procedure, we cannot determine in advance which statistics will be required. Thus, we have to handle each query separately. Moreover, when we consider different structures, we are bound to evaluate a larger number of queries than parametric EM.\" Even if we explore candidate DAGs using a local search algorithm such as hill-climbing, and even if we only score DAGs that differ from the current candidate by a single arc, this means computing \(O(N)\) sets of sufficient statistics. Furthermore, the size of each of these sufficient statistics increases combinatorially with the size of the \(Pa(X_{i})\) of the corresponding \(X_{i}\).  
As a result, practical software implementations of the Structural EM such as those found in [11; 12] often replace the soft EM approach described in Algorithm 1 with the hard EM from Algorithm 2. The same can be true for applications of EM to parameter learning, for similar reasons: the cost of using exact inference can become prohibitive if \(\mathbf{X}\) is large or if there is a large number of missing values. Furthermore, the decomposition in (2) no longer holds because the expected sufficient statistics depend on all \(X_{i}\). In practice this means that, instead of computing the expected values of the \(\{n_{ijk}\}\) as weighted average over all possible imputations of the missing values, we perform a single imputation of each missing value and use the completed observation to tally up \(\{n_{ijk}\}\).  
This leads us to the key question we address in this paper: what is the impact of replacing soft EM with hard EM on learning BNs?