# Hard and Soft EM in Bayesian Network Learning from Incomplete Data
## 2 Methods
### Bayesian Networks  
A Bayesian network BN [7] is a probabilistic graphical model that consists of a directed acyclic graph (DAG) \(\mathcal{G}=(\mathbf{V},E)\) and a set of random variables over \(\mathbf{X}=\{X_{1},\ldots,X_{N}\}\) with parameters\(\Theta\). Each node in \(\mathbf{V}\) is associated with a random variable in \(\mathbf{X}\), and the two are usually referred to interchangeably. The directed arcs \(E\) in \(\mathcal{G}\) encode the conditional independence relationships between the random variables using graphical separation, which is called _d-separation_ in this context. As a result, \(\mathcal{G}\) leads to the decomposition  
\[\mathrm{P}(\mathbf{X}\,|\,\mathcal{G},\Theta)=\prod_{i=1}^{N}\mathrm{P}\left( X_{i}\,|\,Pa(X_{i}),\Theta_{X_{i}}\right), \tag{1}\]  
in which the global (joint) distribution of \(\mathbf{X}\) factorises in a local distribution for each \(X_{i}\) that is conditional on its parents \(Pa(X_{i})\) in \(\mathcal{G}\) and has parameters \(\Theta_{X_{i}}\). In this paper, we assume that all random variables are categorical: both \(\mathbf{X}\) and the \(X_{i}\) follow multinomial distributions, and the parameters \(\Theta_{X_{i}}\) are conditional probability tables (CPTs) containing the probability of each value of \(X_{i}\) given each configuration of the values of its parents \(Pa(X_{i})\). In other words,  
\[\Theta_{X_{i}}=\left\{\pi_{ik\,|\,j},k=1,\ldots,|X_{i}|,j=1,\ldots,|Pa(X_{i})|\right\}\]  
where \(\pi_{ik\,|\,j}=\mathrm{P}(X_{i}=k\,|\,Pa(X_{i})=j)\). This class of BNs is called _discrete BNs_[15]. Other classes commonly found in the literature include Gaussian BNs (GBNs) [16], in which \(\mathbf{X}\) is a multivariate normal random variable and the \(X_{i}\) are univariate normals linked by linear dependencies; and conditional Gaussian BNs (CLGBNs) [17], which combine categorical and normal random variables in a mixture model. The task of learning a BN from a data set \(\mathcal{D}\) containing \(n\) observations is performed in two steps:  
\[\underbrace{\mathrm{P}(\mathcal{G},\Theta\,|\,\mathcal{D})}_{\text{ learning}}=\underbrace{\mathrm{P}(\mathcal{G}\,|\,\mathcal{D})}_{\text{ structure learning}}\quad\cdot\underbrace{\mathrm{P}(\Theta\,|\,\mathcal{G},\mathcal{D})}_{\text{ parameter learning}}\quad.\]  
Structure learning consists of finding the DAG \(\mathcal{G}\) that encodes the dependence structure of the data, thus maximising \(\mathrm{P}(\mathcal{G}\,|\,\mathcal{D})\) or some alternative goodness-of-fit measure; _parameter learning_ consists in estimating the parameters \(\Theta\) given the \(\mathcal{G}\) obtained from structure learning. If we assume that different \(\Theta_{X_{i}}\) are independent and that data are complete [15], we can perform parameter learning independently for each node following (1) because  
\[\mathrm{P}(\Theta\,|\,\mathcal{G},\mathcal{D})=\prod_{i=1}^{N}\mathrm{P}\left( \Theta_{X_{i}}\,|\,Pa(X_{i}),\mathcal{D}\right). \tag{2}\]  
Furthermore, if \(\mathcal{G}\) is sufficiently sparse, each node will have a small number of parents; and \(X_{i}\,|\,Pa(X_{i})\) will have a low-dimensional parameter space, making parameter learning computationally efficient. Both structure and parameter learning involve \(\Theta_{X_{i}}\), which can be estimated as using maximum likelihood  
\[\widehat{\pi}_{ik\,|\,j}=\frac{n_{ijk}}{\sum_{k}n_{ijk}} \tag{3}\]  
or Bayesian posterior estimates  
\[\widehat{\pi}_{ik\,|\,j}=\frac{\alpha_{ijk}+n_{ijk}}{\sum_{k}\alpha_{ijk}+n_{ ijk}} \tag{4}\]  
where the \(\alpha_{ijk}>0\) are hyperparameters of the (conjugate) Dirichlet prior for \(X_{i}\,|\,Pa(X_{i})\) and the \(n_{ijk}\) are the corresponding counts computed from the data. Estimating the \(\Theta_{X_{i}}\) is the focus of parameter learning but they are also estimated in structure learning.