Generate dataset from Bayesian network Given a Bayesian network consisting of n random variables. What is the algorithm to generate the dataset from the given structure and associated conditional probability table for each random variable xi.
 A: I will give a brief algorithm and some code that I used to generate data from a Bayesian network. Python code to generate one such datapoint using NumPy is provided at the end.

We have to generate a data point $X$ consisting of $p$ variables, indexed as $X_1, \dots, X_p$. We assume here that we have the functions to generate a variable given its parents. For ease, we assume a linear formulation, where a child node is linearly weighted combination fo its parents and some additive noise. We also have access to the causal Bayesian network underlying this distribution via its adjacency matrix. The adjacency matrix $A$ denotes the edges in the graph. $A_{ij}=1$ iff there is an edge from node $i$ to node $j$. The following is an algorithmic way to sample from this network.

*

*Identify the source nodes: If node $k$ is a source node, then it will not have any incoming edges. That is, $A_{i,k}=0$ for all $i$. Get all $k$ such that $A_{i,k}=0$ for all $i$.

*Sample the values for the source nodes: Since source nodes can be sampled independently, sample the values for those variables. Add the indices of these source nodes to a list SampledNodes.

*Repeat until $A_{ij}=0, \forall i,j$.

*

*Identify the next generation: Go through the rows of the indices in SampledNodes and find all nodes that can be sampled from the sampled nodes alone. To find those nodes, for each node $i$ in SampledNodes, find all $j$ where $A_{ij}=1$. For these indices $j$, check if $A_{kj}=0$ for all $k\notin$ SampledNodes. If not, then node $j$ is not in the next generation. It has other parents which need to be sampled first. But if the above condition is satisfied, add those nodes to a list NextGenNodes.

*Sample the next generation: The next generation can now be sampled. Form a sub-matrix from the adjacency matrix with its row indices belonging to SampledNodes and its column indices belonging NextGenNodes. Let's call this sub-matrix $A'$. As mentioned before, we are considering the linearly weighted combination of random variables. Let a weighted sub-matrix be formed from $A'$ and the weight matrix $W$, and we will denote it by $A'^T_w$. The next generation nodes is given by $X_{next} = A'^T_wX_{par}$, where $X_{par}$ are the values of the nodes from SampledNodes.

*Include the latest generation among the parents: The generation that we sampled just now can be included among the parents now. Set $A_{ij}=0$ for all $i\in$ SampledNodes and $j\in$ NextGenNodes. Add all indices from NextGenNodes to SampledNodes.




import numpy as np

def _generate_one_data_point(weight_matrix, dim):
    """
    Generate one data point from a Bayesian network with each variable
    being linearly weighted combination of its parents.
    """
    sampled_nodes = []
    next_gen_nodes = []

    # Initialize a placeholder
    X = np.zeros((weight_matrix.shape[0], dim))
    zeros = np.zeros(dim)
    I = np.eye(dim)

    # Get the source nodes
    sampled_nodes.extend([_ for _ in np.where(np.sum(weight_matrix, 0) == 0)[0]])
    # Generate data for those source nodes
    X[np.array(sampled_nodes)] = np.random.multivariate_normal(zeros, I, size=len(sampled_nodes))

    weight_matrix_copy = weight_matrix.copy()
    while np.sum(np.abs(weight_matrix_copy)) != 0:
        # Identify the next generation of nodes.
        with_only_parents = np.sum(weight_matrix_copy[np.array(sampled_nodes)], 0)
        with_all = np.sum(weight_matrix_copy, 0)
        next_gen_nodes.extend([_ for _ in np.where(with_only_parents == with_all)[0]])
        # Remove already sampled nodes
        for _ in sampled_nodes:
            if _ in next_gen_nodes:
                next_gen_nodes.remove(_)

        submatrix = weight_matrix_copy[np.ix_(sampled_nodes, next_gen_nodes)]
        # Generate data for the next generation nodes
        X[np.array(next_gen_nodes)] = np.matmul(submatrix.T, X[np.array(sampled_nodes)])

        sampled_nodes.extend(next_gen_nodes)
        next_gen_nodes = []

        weight_matrix_copy[:, np.array(sampled_nodes)] = 0
 
    return X

A: A Bayesian network is a directed acyclic graph with no cycle.
Hence, there is at least one node that has no parent. Let's first assume that there is only one such root node.
Begin at that node - as it has no parents, we can sample directly from its marginal probability distribution.
Then, use that sample to compute the distributions of its children - we can do this because we're able to condition on the value of the sample. Generate a sample from these distributions, and keep traversing in a breadth-first manner until all nodes have been sampled from once.
The vector of samples you have obtained from each node is a sample from the Bayesian network.
Now, consider the case where there are multiple root nodes - in this case all you need to do is follow the sampling process described above but taking care to sample from all root nodes, and only moving down to sample from their children when all parents have been sampled from.
