# Hard and Soft EM in Bayesian Network Learning from Incomplete Data
## 2 Methods
### The Expectation-Maximisation (EM) Algorithm  
The imputation methods described above focus on completing individual missing values with predictions from the observed data without considering what probabilistic models will be estimated from the completed data. The Expectation-Maximisation (EM) [5] algorithm takes the opposite view: starting from the model we would like to estimate, it identifies the sufficient statistics we need to estimate its parameters and it completes those sufficient statistics by averaging over the missing values. The general nature of this formulation makes EM applicable to a wide range of probabilistic models, as discussed in [25; 26] as well as [4].  
EM (Algorithm 1) is an iterative algorithm consisting of the following two steps:  
* the _Expectation_ step (E-step) consists in computing the expected values of the sufficient statistics \(s(\mathcal{D})\) for the parameters \(\Theta_{j}\) using the previous parameter estimates \(\widehat{\Theta}_{j-1}\);
* the _Maximisation_ step (M-step) takes the sufficient statistics \(\widehat{s}_{j}\) from the E-step and uses them to update the parameters estimates.  
Both maximum likelihood and Bayesian posterior parameter estimates are allowed in the M-Step. The E-step and the M-step are repeated until convergence. Each iteration increases marginal likelihood function for the observed data, so the EM algorithm is guaranteed to converge because the marginal likelihood of the (unobservable) complete data is finite and bounds above that of the current model.  
One key limitation of EM as described in Algorithm 1 is that the estimation of the expected sufficient statistics may be computationally unfeasible or very costly, thus making EM impractical for use in real-world applications. As an alternative, we can use what is called hard EM, which is shown in Algorithm 2. Unlike the standard EM, hard EM computes the expected sufficient statistics \(s(\mathcal{D})\) by imputing the missing data \(\mathcal{D}^{(M)}\) with their most likely completion \(c(\cdot)\), and then using the completed data \(\widehat{\mathcal{D}}\) to compute the sufficient statistics. Hence the name, we replace the missing data with hard assignments. In contrast, the standard EM in Algorithm 1 is sometimes called soft EM because it averages over the missing values, that is, it considers all its possible values weighted by their probability distribution.  
```
Choose an initial value \(\widehat{\Theta}_{0}\) for \(\Theta\). while\(\left|\widehat{\Theta}_{j-1}-\widehat{\Theta}_{j}\right|<\varepsilon\), iterating over \(j=1,2,\ldots\):do Expectation step: impute the missing data with their expectations to create the completed data set \[\widehat{D}_{j}=\left\{\mathcal{D}^{(O)},\;\widehat{D}^{(M)}=c\left(\mathcal{D }^{(M)}\,|\,\widehat{\Theta}_{j-1}\right)\right\}\] and then compute the sufficient statistics for \(\Theta\) as \[\widehat{s}_{j}=s\left(\mathcal{D}_{j}\right)\] Maximisation step: compute the new estimate \(\widehat{\Theta}_{j}\) from \(\widehat{s}_{j}\).  end while Estimate \(\Theta\) with the last \(\widehat{\Theta}_{j}\).
```  
**Algorithm 2**The Hard EM Algorithm.  
It is important to note that hard EM and soft EM, while being both formally correct, may display very different behaviour and convergence rates. Both algorithms behave similarly when the random variables that are not completely observed have a skewed distribution [7].