# Soft learning probabilistic circuits

Soroush Ghandi, Benjamin Quost, Cassio de Campos

► To cite this version:

Soroush Ghandi, Benjamin Quost, Cassio de Campos. Soft learning probabilistic circuits. International Journal of Approximate Reasoning, 2025, 185, pp.109467. 10.1016/j.ijar.2025.109467. hal-05432188

HAL Id: hal-05432188

https://hal.science/hal-05432188v1

Submitted on 8 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

ELSEVIER

Contents lists available at ScienceDirect

International Journal of Approximate Reasoning

journal homepage: www.elsevier.com/locate/ijar

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

# Soft learning probabilistic circuits

Soroush Ghandi<sup>a,*</sup>, Benjamin Quost<sup>b</sup>, Cassio P. de Campos<sup>a</sup>

## ARTICLE INFO

**Keywords:**

Probabilistic circuits

Probabilistic inference

Probabilistic graphical models

Missing data

## ABSTRACT

Probabilistic Circuits (PCs) are prominent tractable probabilistic models, allowing for a wide range of exact inferences. This paper focuses on a main algorithm for training PCs, LearnSPN, arguably a gold standard due to its efficiency, performance, and ease of use, in particular for tabular data. We show that LearnSPN is a greedy likelihood maximizer under mild assumptions. While inferences in PCs may use the entire circuit structure for processing queries, LearnSPN applies a *hard* method for learning PCs, propagating at each sum node a data point through one and only one of the children/edges as in a hard clustering process. We propose a new learning procedure named SoftLearn, that induces a PC using a *soft* clustering process. We investigate the effect of this learning-inference compatibility in PCs. Our experiments show that SoftLearn outperforms LearnSPN in many situations, yielding better likelihoods and arguably better samples. We also analyze comparable tractable models to highlight the differences between soft/hard learning and model querying.

## 1. Introduction

Generative probabilistic models typically aim to learn the joint probability distribution of data, to perform probabilistic inference and answer queries of interest. However, not all the probabilistic models are the same in that regard. Models like variational autoencoders (VAEs) [1] and generative adversarial networks (GANs) [2] possess exceptional modeling prowess; nevertheless, their ability to perform probabilistic inference such as marginalization and conditioning is rather limited, mainly due to computational (tractability) reasons.

In contrast, *tractable* probabilistic models, such as probabilistic circuits (PCs), which include sum-product networks (SPNs) [3, 4], allow for a wider range of exact inferences, arguably at the expense of some fitness power. PCs are a type of Probabilistic Graphical Models (PGMs), a class of models using a graph-based representation to encode high-dimensional distributions [5]. Unlike Bayesian networks, which have a notoriously high complexity for general queries [6,7], PCs can produce several types of inferences in polynomial time under arguably mild assumptions [8].

While intractable models such as VAE and GANs rely on deep neural networks as their structure, their PGM counterparts find graph structures that fit the data well. Moreover, PCs need to reach structures that facilitate exact inferences: this constrained structure learning problem has become an active line of research for many years. Many algorithms have been devised to learn PCs from data, among which LearnSPN [9] is considered a gold standard for its efficiency, performance, and ease of use. This approach to learning

<footnote><sup>a</sup> Eindhoven University of Technology, Department of Mathematics and Computer Science, Eindhoven, 5600 MB, the Netherlands</footnote>

<footnote><sup>b</sup> Université de technologie de Compiègne, CNRS, UMR 7253 Heudiasyc, Compiègne, 60200, France</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: s.ghandi@tue.nl (S. Ghandi), benjamin.quost@utc.fr (B. Quost), c.decampos@tue.nl (C.P. de Campos).</footnote>
the structure of the network follows a greedy search approach: it consists in recursively partitioning the data matrix over the instances (forming sum nodes) and variables (forming product nodes) in a top-down fashion [9,10]. Instead of alternating between instance and variable clustering, [11] proposed to cluster the joint space of instances and variables. Conversely, another category of approaches consists in learning the structure in a bottom-up fashion, by incrementally aggregating correlated variables [12,13].

LearnSPN is also the building block of many subsequent algorithms [14,10,15]. In another line of work, several attempts have been made to learn the structure of PCs in a more principled way, based on non-parametric formulations [16] and/or via Bayesian structure learning [17,18]. The Merged-L-SPN [19] algorithm proposes to merge subtrees in a post-processing approach to reduce computation complexity and improve the generalization of LearnSPN. There have also been a variety of approaches aimed at learning other structures of tractable probabilistic models, such as probabilistic sentential decision diagrams (PSDDs) [20] and Cutset networks [21,22].

In this paper, we focus on the LearnSPN procedure, due to its prominence in the field of PC learning strategies, and its overall very good performances—if not superior to those of its contenders. We claim that this greedy learning approach may result in inappropriate clusters and lead to partitioning marginals rigidly at sub-optimal locations, which can potentially lead to overfitting and poor generalization. We therefore propose the SoftLearn procedure as a counterpart to LearnSPN, with the aim to mitigate such potential drawbacks. SoftLearn is a soft learning scheme akin to LearnSPN which may provide smoother marginals between data clusters so as to reduce the errors induced by misgrouped instances, and therefore lead to better likelihoods and arguably better samples. We compare SoftLearn with LearnSPN over a range of datasets and configurations, and show that SoftLearn manages to outperform LearnSPN in most cases, which empirically validates our claims regarding the potential improvements made by our soft learning scheme. We also draw comparisons with Cutset Networks [21], another prominent tractable probabilistic model with similar goals. We would like to mention that this work builds upon, and extends previous work [23], by providing a more detailed analysis of the investigated methods, and by the addition of the experiments on datasets with missing values.

Our paper is organized as follows. Section 2 recalls the basics of probabilistic circuits, and presents the LearnSPN procedure in details. Section 3 presents our proposal to mitigate the hard partitioning strategy used in LearnSPN. Section 4 reports the results obtained in a variety of settings, which show that our soft learning scheme makes it possible to obtain networks with arguably better fitting power. Section 5 concludes the paper.

## 2. Probabilistic circuits

In this paper, we use the terms “SPNs” and “PCs” interchangeably. The development of these models is rooted at earlier ideas for the compilation of Bayesian networks [24]. SPNs use circuits with three types of nodes: sum nodes can be interpreted as latent variables; product nodes encode context-specific independence (independencies that hold only in certain contexts, i.e., given a specific assignment of values to certain variables [25]); and leaves encode (tractable) univariate probability distributions [26].

### 2.1. Structure of a PC

Structurally, an SPN takes the form of a rooted directed acyclic graph (RDAG). A directed graph is defined by a finite set $N$ of nodes and a set $\mathcal{E} \subseteq N \times N$ of ordered node pairs, called edges—for example, if $N, C \in N$ and $(N, C) \in \mathcal{E}$, then we have a directed edge between $N$ and $C$, written as $N \to C$. A directed acyclic graph does not contain any directed cycle (i.e., a path of directed edges from any node to itself); non-directed cycles are allowed. We denote the root of the graph (i.e., a node without incoming edge) by $R$. We assume nodes can only belong to a single graph; thus, $N$ and $\mathcal{E}$ can be left implicit in the notation.

Any node $N$ can be associated with important subsets:

* its *children* $\text{ch}(N) := \{C \in N : N \to C\}$ are those nodes to which there is a directed edge from $N$,

* its *descendants* $\text{de}(N) := \text{ch}(N) \cup \bigcup_{C \in \text{ch}(N)} \text{de}(C)$ can be accessed by a sequence of directed edges from $N$,

* the *leaves* $\text{lv}(N) := \{D \in \text{de}(N) : \text{ch}(D) = \emptyset\}$ are the descendants of $N$ that do not have children themselves.

Each node $N$ of an RDAG determines a sub-RDAG, written $N \downarrow$, rooted in $N$, and with nodes $\{N\} \cup \text{de}(N)$ (the whole RDAG could be written as $R \downarrow$). Given a non-leaf node $N$ of an RDAG, two of its children $C_1, C_2 \in \text{ch}(N)$ are said to be either *overlapping* if and only if $\text{lv}(C_1) \cap \text{lv}(C_2) \neq \emptyset$, or *disjoint* otherwise, i.e., if and only if $\text{lv}(C_1) \cap \text{lv}(C_2) = \emptyset$.

### 2.2. Probabilistic interpretation

Let $\mathbf{X}$ be a finite collection of random variables; $X \in \mathbf{X}$ denotes that a random variable $X$ belongs to $\mathbf{X}$.<fnref n="1" /> We will refer to the set of possible realizations $\mathbf{x}$ of $X$ as val $\mathbf{X}$, with val $\mathbf{X}$ being the set of possible realizations $\mathbf{x}$ for the variables in $\mathbf{X}$, i.e., val $\mathbf{X} = \bigcap_{\mathbf{X} \in \mathbf{X}}$ val $\mathbf{X}$. We will denote by $\mathbf{Y} \subseteq \mathbf{X}$ a subcollection of the variables in $\mathbf{X}$. Joint realizations $\mathbf{x} \in \text{val} \mathbf{X}$ or $\mathbf{y} \in \text{val} \mathbf{Y}$ can be projected onto a subspace. For example, if $\mathbf{Y} \subseteq \mathbf{X}$, then $\mathbf{x}|_{\mathbf{Y}} \in \text{val} \mathbf{Y}$; we use the same notation $\mathbf{y}|_{\mathbf{X}} \in \text{val} \mathbf{X}$ to project $\mathbf{y}$ onto a variable $\mathbf{X} \in \mathbf{Y}$.

**Probabilistic model.** A SPN encodes a probabilistic model over a collection of variables $\mathbf{X}$ [27,3,4]. It consists of a rooted directed acyclic graph (RDAG) with structural constraints. The graph is composed of three distinct types of nodes: sum nodes, associated with

<footnote n="1">¹ Collections of random variables and their realizations are in boldface, as opposed to single random variables and their realizations.</footnote>
(numerical) parameters **w**; product nodes, and distribution nodes. In a nutshell, distribution nodes (which correspond to the leaves of the SPN) describe simple distributions which can be recursively combined using sums and products so that the root encodes a complex distribution.

**Scope.** Every node $N$ in the SPN is in fact associated with a random variable or a subset thereof, called its *scope*, over which the node defines a probability distribution: e.g., $\mathbf{X}_N$ stands for the scope of $N$. While the scope of a leaf (terminal) node is user-defined or inferred from data, the scope of a non-leaf node $N$ is the union of its child scopes:

$$ \mathbf{X}_N = \bigcup_{C \in \text{ch}(N)} \mathbf{X}_C. $$

The root scope is $\mathbf{X}_R = \mathbf{X}$ (we assume every random variable to be in the scope of at least one leaf). We will write the *projection of a node scope* using the node symbol: $\mathbf{x}|_{N} := \mathbf{x}|_{\mathbf{X}_N}$.

**Combination of distributions.** A sum node $S$ computes a mixture of the distributions associated with its children. For this purpose, it is associated with a function $\mathbf{w}_S$ on $\text{ch}(S)$ that returns edge weights $w_{S \to C} := \mathbf{w}_S(C)$ for any $C \in \text{ch}(S)$: thus, $\mathbf{w}_S$ is the *weight vector* associated with $S$. Weights are assumed to be normalized and non-negative: for all $C \in \text{ch}(S)$,

$$ \sum_{C \in \text{ch}(S)} w_{S \to C} = 1, \quad w_{S \to C} \ge 0. $$

The numerical parameters **w** of the entire SPN can simply be seen as the map $\mathbf{w} : S \mapsto \mathbf{w}_S$ that identifies this vector for any sum node in the SPN. The value $S(f)$ of any sum node $S$ is recursively obtained from the values of its children:

$$ S(f) := \sum_{C \in \text{ch}(S)} w_{S \to C} C(f). $$

A product node $P$ computes a multivariate distribution by multiplying the distributions associated with its children. It is therefore associated with a value $P(f)$, also recursively computed using the values of its children:

$$ P(f) := \prod_{C \in \text{ch}(P)} C(f). $$

Finally, any leaf in the RDAG is a *distribution node* $D$ in the SPN. Distribution nodes define a probability distribution over their scope $\mathbf{X}_D$. We assume the scope $\mathbf{X}_D$ of any leaf node $D$ to consist of a single random variable, and thus leaf nodes to encode univariate distributions.

## 2.3. Queries

**Recursive computation.** SPNs allow for efficient computation of a wide range of probabilistic queries, including conditionals, expectations, or marginals. Assume we wish to calculate the expectation $R(f) := \mathbb{E}_{R|\mathbf{w}}(f)$ of a function $f$ according to the distribution encoded by the SPN with root $R$ and weights $\mathbf{w}$. Let $f$ be a product of indicators over variables in $\mathbf{X}$. Let $\mathbb{E}_D$ denote the expectation operator with respect to the distribution in any leaf node $D$.

The expectation $R(f)$ can be computed by propagating the expected values $D(f) := \mathbb{E}_D(f_D)$ in the leaves to the root node, thereby associating each node $N$ with an expected value $N(f)$. Distribution nodes, being always the leaves in the RDAG, are the terminal points of the recursive definition of the node values.

We assume in the sequel that we can *efficiently evaluate* the expectations in the leaves, which opens the way to efficiently computing the expectation $R(f)$.

**Validity of a SPN.** This efficiency relies on additional assumptions typically used in SPNs to ensure the probabilistic model is proper [27]. For any sum ($S$) and any product ($P$) node in the SPN, it holds that

$$ \text{A1: } \mathbf{X}_{C_1} = \mathbf{X}_{C_2} \text{ for all } C_1, C_2 \in \text{ch}(S); \qquad \text{(smoothness)} $$

$$ \text{A2: } \mathbf{X}_{C_1} \cap \mathbf{X}_{C_2} = \emptyset \text{ for all } C_1, C_2 \in \text{ch}(P). \qquad \text{(decomposability)} $$

Any SPN that meets both requirements is said to be *valid*. Validity is a sufficient condition for ensuring that queries can be computed efficiently.

## 2.4. LearnSPN: greedy variable and instance partitioning procedure

**Overview.** LearnSPN employs a greedy search in the space of SPNs, and augments the network in a top-down fashion accordingly. It initializes the network with a single node $R$ representing the entire dataset (with scope $\mathbf{X}$), and then proceeds by recursively partitioning the dataset into smaller chunks based on instance/variable-wise groupings found in the data.

Independence tests can be used to identify groups of variables that are supposedly conditionally independent. Should the outcome of such a test be positive, i.e., groups of independent variables can indeed be identified, a product node $P$ is added to the network, and each of its children is associated with one of the groups found. A product node operates a product of the distributions represented by its successors. Pairwise tests are typically used in the LearnSPN procedure
**Algorithm 1 LearnSPN(D|N, X_N).**

1: **Input:** set of instances $D|_N \subseteq \text{val } X_N$ for a scope $X_N$

2: **Output:** an SPN $N \downarrow$ representing a distribution over $X_N$ learned from $D|_N$

3: **if** $|X_N| = 1$ **then**

4: &nbsp;&nbsp;&nbsp;&nbsp; $N \leftarrow \text{leaf univariate distribution node } D$ estimated from the variable's values in $D|_N$

5: **else**

6: &nbsp;&nbsp;&nbsp;&nbsp; partition $X_N$ into approximately independent subsets $X_{C_j}$, that is, $(X_{C_j})_{j=1,...,J}$ is a partition of $X_N$

7: &nbsp;&nbsp;&nbsp;&nbsp; **if** $J > 1$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $N \leftarrow \bigotimes_{j=1}^J \text{LearnSPN}(D|_{C_j}, X_{C_j})$

9: **else**

10: &nbsp;&nbsp;&nbsp;&nbsp; partition $D|_N$ into subsets of similar instances $D_i|_{C_i}$, where $C_i = N$, with $i = 1, ..., I$

11: &nbsp;&nbsp;&nbsp;&nbsp; **if** $I > 1$ **then**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $N \leftarrow \bigoplus_{i=1}^I \frac{|D_i|_{C_i}|}{|D|_N}$ LearnSPN($D_i|_{C_i}, X_{C_i}$)

13: **else**

14: &nbsp;&nbsp;&nbsp;&nbsp; $N \leftarrow \bigotimes_{j=1}^{|X_N|} \text{LearnSPN}(D|_{X_j}, \{X_j\})$

15: **return** $N$

Should the independence tests result in a single connected component of dependences among the variables, the procedure proceeds with a clustering step, so as to identify groups of “similar” instances. Based on this partition of the data, a sum node $S$ is added to the network: this node operates a mixture of the distributions represented by its successors. In LearnSPN, sum nodes $S$ are created by performing hard clustering on the instances with the induced children having same scope as $S$.

The whole variable and instance partitioning process is recursively applied until a stopping criterion is met, at which point each group of data corresponds to a univariate distribution that can be modeled reliably in the corresponding leaf of the network.

**Limitations.** Here, we discuss a feature of the LearnSPN learning procedure, which does not process instances in the same way during training and test phases.

Indeed, as mentioned above, LearnSPN creates a sum node by partitioning a group of training instances into clusters. These clusters are then propagated down the network in a *hard way*: each is then exclusively associated with a sub-PC rooted in one of the sum node descendants, for which it serves as a training set (and thus the recursion continues). However, during inference, a PC may use the *entire network structure* to process a particular query, even though the relevant information to that query was only used to train *some parts* of the network structure.

Inherently, the response to a query will be mostly affected by the network parts trained on the relevant information; thus, this incompatibility does not lead to an erroneous response as long as the clustering in LearnSPN can well classify the queried datapoint. However, for datapoints that lie near the cluster borders, the response can become considerably erroneous in case of misgrouping by the clustering approach used in Line 10 of Algorithm 1. We will further clarify our point with a two-dimensional example in Section 3.1.

## 3. Soft learning of probabilistic circuits

In this section, we present our proposal to mitigate the hard clustering philosophy employed in the LearnSPN algorithm. We start by exposing the principle, before explaining how the features of the original procedure can be adapted to take cluster memberships into account. We then bring the analysis to a more formal level, comparing LearnSPN and SoftLearn in terms of likelihood maximization.

### 3.1. Principle

Our proposal, SoftLearn, induces a PC using a soft clustering process, so as to mitigate the consequences of the misgroupings mentioned above. In order to do so, during clustering, for a set of $K$ clusters $\{C_1, C_2, ..., C_K\}$, a set of $K$ datapoint weights are associated to each datapoint, $\{v_1, v_2, ..., v_K\}$ such that $\sum_i v_i = 1$. Each instance in the dataset starts with a datapoint weight equal to 1 (i.e., the very first call of Algorithm 2 has $V|_N = [1, ..., 1]$ as its weight input), which is divided among the children of sum nodes as the algorithm recursively performs clustering.

Thus, after clustering, each datapoint is shared among the children of the sum node proportionally to its cluster memberships; this way, each datapoint will be propagated through the entire network, but with different weights indicating its importance to a particular part of the network. Fig. 1 clarifies the difference between clustering in SoftLearn and LearnSPN with a simple example.

Other than the clustering method, for the most part, a high-level visual representation of SoftLearn is similar to that of LearnSPN (Fig. 1 in [9]); nonetheless, since SoftLearn works with soft clustering (while a hard clustering method is the default choice in LearnSPN), each process in SoftLearn is modified to work with weighted data.

Before detailing further how LearnSPN can be adapted to take into account such weighted instances, we present an (extreme-case) illustrative example of the potential benefits of SoftLearn.

**Example 1.** Assume that data $(X, Y) \in \mathbb{R}^2$ is generated from a PC as per Equation (1) (we use a flat notation for the PC):

$$ (X, Y) \sim 0.5 \cdot \mathcal{N}_X(-0.5, 1) \otimes \mathcal{N}_Y(-2, 0.2) \oplus 0.5 \cdot \mathcal{N}_X(0.5, 1) \otimes \mathcal{N}_Y(2, 0.2). \quad (1) $$
<figure><img src="image_5.png" /><figcaption>Fig. 1. Example of clustering process in LearnSPN vs. SoftLearn in a scenario with 3 clusters. (a) clustering in LearnSPN, which dedicates each instance to one and only one of the resulting clusters. (b) clustering in SoftLearn, which divides each instance among the resulting clusters based on membership/relevance score, specified by $v_i^k$. Note that the intensity of colors, for each instance i in each cluster k, is proportional to its membership score $v_i^k$. In this setting, the weights $w_k$ of the resulting sum node is calculated as $w_k = \frac{\sum_{i} v_i^k}{\sum_{i,k} v_i^k}$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 2. (a) PC structure equivalent to Expression (1), with a root sum node (in blue) with balanced weights to its children, which are two product nodes (in green), and four leaf distribution nodes (in salmon). (b) Green points $(X, Y)$ (respectively horizontal and vertical axes as usual) generated from the PC in Expression (1). The gray line represents a hypothetical bad partition obtained for the root node. SoftLearn yields the mean parameters of the Gaussian leafs represented by the black diamonds, which still captures the whole Gaussians on both sides of the gray cut of the first step; standard LearnSPN yields the red triangles as means, as both clusters are necessarily treated separately. (For interpretation of the colors in the figure(s), the reader is referred to the web version of this article.)</figcaption></figure>

Fig. 2(a) shows the equivalent graphical representation, which respects both the smoothness and decomposability Assumptions, and hence induces a valid joint distribution for $X, Y$. Fig. 2(b) shows a sample with 1000 datapoints (green points) for each of the two mixture components, which are independent bivariate Gaussians. Sampling is performed top-down, choosing the direction to take in a sum node based on its weights, while following all paths from product nodes, yielding a full sample when the corresponding leaf nodes are reached and sampled. This generating distribution is obviously unknown to the learning algorithms.

We start running both LearnSPN and SoftLearn on this dataset. Initially, the conditions in Line 7 of Algorithms 1 and 2 both fail, since $X$ and $Y$ are not independent ($X$ is shifted based on $Y$), and the algorithms proceed with creating a sum node. Assume now that the clustering fails and partitions the points as per the gray line in Fig. 2(b) (that is, at $X = 0$). Hence, in the continuation, LearnSPN will have to recursively deal with the groups of points in the left- and right-sides of the gray line separately, while SoftLearn will weight the pertinence of each data point to each of the two groups. After that first sum node, a product node will not appear again ($X$ and $Y$ being still considerably dependent). Assume now that the next clustering step works perfectly well (otherwise, the difference in favor of SoftLearn could be even stronger, as we will see), and hence split points perfectly (positive $Y$ go to one side and negative $Y$ to the other). Finally, $X$ and $Y$ will be found independent (enough) and the four bivariate Gaussians will appear as in the following expressions. LearnSPN gives the model in Expression (2):

$$ (X, Y) \sim .49(0.7 \cdot \mathcal{N}_X(-1, .69) \otimes \mathcal{N}_Y(-2, .2) \oplus .3 \cdot \mathcal{N}_X(-.69, .54) \otimes \mathcal{N}_Y(2.01, .2)) \\ \oplus .51(.31 \cdot \mathcal{N}_X(.64, .53) \otimes \mathcal{N}_Y(-1.98, .2) \oplus .69 \cdot \mathcal{N}_X(.98, .68) \otimes \mathcal{N}_Y(2, .19)); \quad (2) $$

and SoftLearn the model in Expression (3):

$$ (X, Y) \sim .5(5 \cdot \mathcal{N}_X(-.51, 1.01) \otimes \mathcal{N}_Y(-1.99, .2) \oplus .5 \cdot \mathcal{N}_X(.48, .99) \otimes \mathcal{N}_Y(2, .2)) $$
$$ \oplus .5(.51 \cdot \mathcal{N}_X(-.47, .99) \otimes \mathcal{N}_Y(-1.99, .2) \oplus .49 \cdot \mathcal{N}_X(.52, 1) \otimes \mathcal{N}_Y(2, .2)). \quad (3) $$

In this hypothetical example, both approaches learn reasonable parameter estimates for the distribution leafs over $Y$ (the true generating distribution is in Expression (1)), but LearnSPN struggles to yield good estimates for $X$ due to the bad clustering at the first sum node (the actual distributions being Gaussians $\mathcal{N}(0.5, 1)$ and $\mathcal{N}(-0.5, 1)$). On the other hand, SoftLearn has less difficulty to achieve good estimates for $X$. The Gaussian means of the distribution leaf nodes obtained by LearnSPN are shown in Fig. 2(b) as red triangles, while computed by SoftLearn are displayed in black diamonds. The figure clearly shows the difference between the hard LearnSPN approach and SoftLearn, suggesting that the latter might better cope with bad clustering results. It is not hard to imagine node pruning/merging techniques that would make the outcome of SoftLearn more compact in this situation, as some terms in Expression (3) represent somewhat similar Gaussians (and by that potentially we could recover even the simpler true structure of Expression (1)).

Although we provide an extreme low-dimensional example here, in more practical scenarios, we argue that the impact of a soft approach is still significant, yet more implicit. Arguably in most occasions, we do not see the extreme situation of this example, and even if we do, there is hardly a case where a clustering algorithm performs this poorly in low dimensions. Nonetheless, in practical scenarios, the data itself can be inherently hard to cluster (this also depends on the clustering algorithm as well). In high dimensions, it is hard to define a suitable distance metric between the instances, and as a result, methods that rely on distance metrics are prone to error in high-dimensional problems. Additionally, for the sake of efficiency, most of the time the number of output clusters is fixed (for methods that take the number of clusters as an input, like K-means and EM; this means that each time the clustering method is called, it outputs a fixed number of clusters), which essentially establishes a trade-off between optimizing the clustering (by fine-tuning the number of clusters for each call of the clustering method, which leads to better clusters) and being more computationally efficient. In both of these cases, a soft learning scheme can provide noticeable gains in mitigating the errors induced by the shortcomings of clustering methods.

On the other side, let us assume that at the first iteration, the clustering method works well, and divides the instances based on $Y=0$. At the second iteration, both methods can easily establish the independence of $X$ and $Y$ in the resulting clusters, and hence, can conclude the structure with leaf nodes corresponding to each variable during the following iteration. In this scenario, LearnSPN can model the underlying distribution with very high precision, and gives the model in Expression (4):

$$ (X, Y) \sim 0.5 \cdot \mathcal{N}_X(-0.5, 1) \otimes \mathcal{N}_Y(-2, 0.2) \oplus 0.5 \cdot \mathcal{N}_X(0.5, 1) \otimes \mathcal{N}_Y(2, 0.2). \quad (4) $$

which is (practically) the same as the true distribution; SoftLearn will lead to the model in Expression (5):

$$ (X, Y) \sim 0.5 \cdot \mathcal{N}_X(-0.49, 1.01) \otimes \mathcal{N}_Y(-1.98, 0.2) \oplus 0.5 \cdot \mathcal{N}_X(0.49, 1) \otimes \mathcal{N}_Y(1.98, 0.2). \quad (5) $$

In this case, we see that SoftLearn is slightly less precise; in general, when the clustering method consistently performs well and with high confidence, employing a soft method can negatively affect the results, since each part of the process has to deal with residual weights of instances that are not necessarily relevant, while benefiting less from the relevant samples. This essentially induces a slight bias in the distributions modeled by SoftLearn, and therefore, the results could be worse compared to LearnSPN in these scenarios. Yet, assuming that clustering can always be done well in a hard way is unrealistic, to say the least.

Based on the results of this example, we argue that the benefit of applying a soft method in the case of bad clustering is more significant than the impact of applying a hard approach when the clustering is good. As a result, in order for LearnSPN to be better than SoftLearn, we need good clustering, with high confidence and consistency, which is hard to ensure in practical, high-dimensional problems, especially over several steps of clustering. LearnSPN may be superior whenever there is a clear class structure in the data that can be captured with the clustering algorithm employed. Should this class structure be too complex to capture (e.g., classes differ in their covariance matrices, but we use K-means which assumes spherical clusters with the same volume), we expect that taking clustering uncertainty into account will lead to better results. Therefore, while it is possible for LearnSPN to outperform SoftLearn, we expect SoftLearn to generally perform better than LearnSPN in practical cases.

## 3.2. Adaptation

Propagating the weights associated with data points throughout the network and using them to learn a PC requires extensive adjustments to other parts of LearnSPN as well, beyond simply re-engineering the procedures, since clustering methods used to induce sum nodes, independence tests to induce product nodes, and distribution nodes at leafs do not naturally handle weighted datapoints.

A number of implementations of LearnSPN have been proposed. We build our method upon the version described in [28] (see Algorithm 1), since it achieved state-of-the-art results. Our experimental study in Section 4 nevertheless reports the results of the original implementation [9].

**Univariate density estimation.** Following [28], we model the distribution over discrete or continuous variables using a multinomial or Gaussian distribution, respectively. These choices are not limiting, since PCs under this formulation can fit any distribution so long as structure learning is able to split the space properly and data are enough.

In our case, each datapoint propagated in the learning algorithm has an associated weight. We employ the weights in our calculations as a measure of frequency. Take a univariate dataset $D|_D = \{d_1, d_2, ..., d_m\}$ and a set of corresponding weights $V = \{v_1, v_2, ..., v_m\}$ at a particular leaf $D$, with $v_i > 0$ for all $i$ (datapoints with zero weight are discarded). For discrete variables, we will have:
$$ \hat{P}(\mathbf{X}_D = k) = \frac{V_k}{\sum_{j=1}^{m} V_j}, \quad \text{where} \quad V_j = \sum_{i: d_i = j} v_i. \qquad (6) $$

For continuous variables, we use a Gaussian $N(\hat{\mu}, \hat{\sigma})$ obtained with the proper derivations to achieve the reweighted estimation with Bessel's correction (derivations are omitted for ease of exposure):

$$ \hat{\mu} = \frac{\sum_i v_i d_i}{\sum_i v_i}, \qquad (7) $$

$$ \hat{\sigma} = \sqrt{\frac{\sum_{i=1}^{m} v_i}{(\sum_{i=1}^{m} v_i)^2 - \sum_{i=1}^{m} v_i^2} \sum_{i=1}^{m} v_i(d_i - \hat{\mu})^2}. \qquad (8) $$

**Independence tests.** For discrete variables, [28] proposed to use the chi-square test of independence, and to add a product node if the variables can be split into independent subsets. In brief, the chi-square test uses the difference between expected (under null hypothesis of independence) and observed “frequencies”, using contingency tables. To account for weighted instances, we form weighted contingency tables and then proceed with the chi-square test based on the weighted tables. The calculations are similar to what is done in Equation (6) (we leave for the reader to fill in the simple gaps to perform this computation).

In the case of two continuous variables or of mixed variables, we first discretize the continuous variables, and then apply the weighted chi-square test, while [28] use the Kruskal and Kendall's tau tests. Adapting Kruskal and Kendall's tau to deal with weighted data and meaningful commensurable interpretation among tests seems to be a challenge in itself. Our choice is motivated by the clear interpretation of partial frequencies that now all tests have in common, regardless of the data type, so all tests are commensurable. Their efficacy is not largely affected so long as enough data points are available (which is the case, as we would want to stop expanding the model otherwise).

**Clustering.** In addition to handling soft membership degrees so as to quantify the relevance of an instance to a group, the clustering methods in our approach should also be able to admit weighted datapoints as inputs. We investigate two options.

The first one is an adjusted version of the K-means clustering algorithm. In order to work with weighted data, we only change the update rule of centroids to account for datapoint weights. Originally, assuming a centroid $O$ is associated with $m$ datapoints $\{d_1, d_2, ..., d_m\}$, it would be updated as: $O_{\text{upd}} = (\sum_i d_i)/m$. In our adjusted version, where datapoints are associated with weights $\{v_1, ..., v_m\}$, the update rule is simply $O_{\text{new}} = \sum_i v_i d_i / \sum_i v_i$.

Additionally, we utilize a weight function $v(d, \{O_i\}, i)$, that computes the weight $v_i$ of each datapoint $d$ in each group $i$ based on the group centroid $O_i$. We define an arguably natural reweighted function as:

$$ v_i := v(d, \{O_i\}, i) = \frac{\exp\left\{\beta(1 - \frac{\|d - O_i\|_F}{\sum_k \|d - O_k\|_F})\right\}}{\sum_j \exp\left\{\beta(1 - \frac{\|d - O_j\|_F}{\sum_{\ell} \|d - O_{\ell}\|_F})\right\}} $$

Where $\|\cdot\|$ denotes a distance measure. In other words, this reweighted function (i) computes the (Euclidian) distances of the datapoint $d$ to group centroids $\{O_i\}_{i=1}^c$ and normalizes them; (ii) computes an intermediate relevancy degree $1 - \|d - O_i\|_F / \sum_k \|d - O_k\|_F$ to each group, which trivially gives more (resp. less) value to groups that are closer to (resp. further away from) the datapoint; and (iii) applies a softmax function to the relevancy degrees.

The second clustering method we investigate is based on estimating mixtures of distributions using the Expectation-Maximization (EM) algorithm, under a conditional independence assumption. Let the dataset be $D|_S$ over variables $\mathbf{X}|_S$. In order to perform EM clustering, we assume the underlying distribution to be a mixture of $c$ fully factorized distributions ($c$ is the targeted number of children for $S$): $P(\mathbf{X}) = \sum_{i=1}^c P(i) \prod_{X \in \mathcal{X}} P(X|i)$. In a nutshell, EM estimates the model parameters by iteratively alternating between an expectation and a maximization step, until a stopping criterion is met. The expectation step amounts to updating the (soft) memberships of the instances to the clusters, based on the current distribution estimates; and the maximization step, to update the univariate distributions $P(X|i)$ and the group priors $P(i)$ based on the new memberships. In order to make EM work with weighted data, we only need to make two changes to the algorithm: we modify the univariate distribution updates in the maximization step to include the weights, as for univariate distribution estimation in Section 3.2, and we make the updates for the group priors $P(i)$ proportional to the sum of weights (instead of whole counts). Both steps are repeated iteratively until convergence to a stationary point (as usual in EM). The adjustments result in a soft learning scheme SoftLearn, whose pseudocode is given in Algorithm 2, which is not only more compatible with the soft inference scheme of PCs, but also uses each datapoint to learn every part of the network.

### 3.3. Theoretical analysis

We provide here theoretical insights into how methods like LearnSPN and SoftLearn optimize the global likelihood. Before going into the details, we first reiterate the learning process of LearnSPN and SoftLearn, and establish necessary assumptions. In both algorithms, each learning iteration does one of the three following tasks: i) adding a (factorized) leaf node at the end of a path; ii) adding an internal sum node; iii) adding an internal product node.

We assume that we have the option to terminate LearnSPN/SoftLearn at any arbitrary iteration of learning. Doing so means that we stop clustering over instances/variables and finalize the PC by adding factorized distributions to each path that does not already
<caption>**Algorithm 2 SoftLearn(D|N, X_N, V|N).**</caption>

1: **Input:** set of instances $D|_N \subseteq \text{val } X_N$ for a scope $X_N$, set of weights $V|_N$ corresponding to datapoint instances
2: **Output:** an SPN $N \downarrow$ representing a distribution over $X_N$ learned from $D|_N$
3: **if** $|X_N| = 1$ **then**
4: &nbsp;&nbsp;&nbsp;&nbsp;N $\leftarrow$ leaf univariate distribution node D estimated from the variable's values in $D|_N$ with weights in $V|_N$
5: **else**
6: &nbsp;&nbsp;&nbsp;&nbsp;partition $X_N$ into approximately independent subsets $X_{C_j}$ using weighted independence tests with weights $V|_N$, that is, $(X_{C_j})_{j=1,...,r}$ is a partition of $X_N$, using $D|_N$ and $V|_N$
7: **if** $J > 1$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;N $\leftarrow \bigotimes_{j=1}^J \text{SoftLearn}(D|_{C_j}, X_{C_j}, V|_{C_j})$
9: **else**
10: &nbsp;&nbsp;&nbsp;&nbsp;partition $D|_N$ using a weighted soft clustering with datapoint weights $V|_N$, yielding new weights ${V_j}_{j=1,...,I}$, with $i = 1, ..., I$ ($I$ is the number of groups)
11: &nbsp;&nbsp;&nbsp;&nbsp;update $V_j \leftarrow V_j \cdot V|_N$ and let $s_j = \sum V_j$
12: **if** $I > 1$ **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;N $\leftarrow \bigoplus_{i=1}^I \frac{s_i}{\sum_{j=1}^I s_j} \text{SoftLearn}(D|_{C_j}, X_{C_j}, V_j)$
14: **else**
15: &nbsp;&nbsp;&nbsp;&nbsp;N $\leftarrow \bigotimes_{j=1}^{|X_N|} \text{SoftLearn}(D|_{X_j}, \{X_j\}, V|_{X_j})$
16: **return** N

<figure><img src="image_7.png" /><figcaption>**Fig. 3.** Example of termination process. (a) termination at the root of the graph. (b) termination after adding a sum node with two children.</figcaption></figure>

end in a leaf node. The resulting PC produced by this process, called the *alternative PC* at iteration *t*, is written $p^t$. If we terminate the algorithm at the root of the PC, then we obtain as alternative PC $p^0$ a fully factorized distribution as in Fig. 3(a). Similarly, if we first add a sum node (with two children) to the root of the PC, and then proceed to terminate the learning, the alternative PC $p^1$ would have a structure similar to Fig. 3(b). We discuss here the differences between any two consecutive alternative PCs $p^t$ and $p^{t+1}$, and their consequences in terms of model fitting—quantified by the associated likelihood.

Should the learning algorithm add a leaf node or a product node, the additional iteration has no impact on the likelihood of the alternative PC obtained. Indeed, adding a leaf node to $p^t$ is inconsequential, since the termination process already includes adding a leaf node to any path without leaves. Adding a product node to $p^t$ is inconsequential as well: as can be seen in Algorithms 1 and 2, any leaf node associated with a subset of variables is naturally replaced by a product node over univariate distributions. Therefore, in both cases, there is no structural difference between $p^t$ and $p^{t+1}$, and their likelihood is therefore the same.

This leaves us only with the case where a sum node is added to $p^t$ to get $p^{t+1}$. The PCs represented in Figs. 3(a) and 3(b), referred to hereafter as $p^0$ and $p^1$, can be taken as examples; the same logic can be generalized to any arbitrary structures $p^t$ and $p^{t+1}$ (with the exception that the difference in the likelihood will be weighted by a positive multiplier). In this case, the difference in the likelihood stems from the difference between the factorized distribution $p^0(X_1, \dots, X_m)$ and the mixture $p^1(X_1, \dots, X_m)$ of C factorized distributions obtained after a clustering step, both learned from the same data D.

Whether or not $p^1$ is an increase over $p^0$ in terms of likelihood depends on the clustering algorithm. Yet, we can prove that there is always a solution that obtain the same likelihood as (or better than) the alternative option. Without losing generality, assume that we are adding a sum node with two children as in Fig. 3(b). In the case of soft clustering, one can equally divide each sample between the two clusters (weighing half to each side), which will lead to the same likelihood as the alternative fully factorized model. Hence, any soft clustering algorithm that outperforms this arguably trivial solution improves the likelihood after the sum node has been added. When using hard clustering, the argument is slightly different (as we cannot “split” the data points in half to use in each side). In this case, assume the sum node child $p_1^1$ in Fig. 3(b) is associated with an arbitrary data point with weight $w$, and the other child $p_2^1$ is associated with all other data points with summed weight $1-w$. The likelihood of both $p_1^1$ and $p_2^1$ is obviously higher than that of the alternative model $p^0$ for the part of the data points they represent, and the likelihood of $p^1$ is thus higher than that of $p^0$ with the appropriate weighting. Again, this clustering solution is only a crude solution, and the solutions obtained with any nontrivial clustering algorithm are expected to increase the likelihood even further.

In addition to the intuitive perspectives developed above, we would also like to mention that some algorithms such as hard/soft EM, if properly initialized, can theoretically guarantee that the resulting mixture will have a better likelihood compared to the alternative factorized model. Furthermore, the higher flexibility of soft clustering schemes, allowed by handling soft cluster memberships, suggests that the fitting power of soft-clustering based learning strategies (such as SoftLearn) might result in a higher fitting ability.
<table><caption>**Table 1**
Performance results of SoftLearn vs. LearnSPN [9], LearnSPN [28], and CNET [31] over 20 binary datasets.</caption><thead><tr><th rowspan="2">Data</th><th colspan="2">LearnSPN</th><th>CNET</th><th>Soft</th><th rowspan="2">Data</th><th colspan="2">LearnSPN</th><th>CNET</th><th>Soft</th></tr><tr><th>Gens</th><th>Correia</th><th></th><th>Learn</th><th>Gens</th><th>Correia</th><th></th><th>Learn</th></tr></thead><tbody><tr><td>NLTCS</td><td>-6.11</td><td>-5.99</td><td>-6.10</td><td><strong>-5.97</strong></td><td>DNA</td><td>-82.52</td><td>-83.67</td><td>-109.79</td><td><strong>-82.06</strong></td></tr><tr><td>MSNBC</td><td>-6.11</td><td><strong>-6.04</strong></td><td>-6.06</td><td>-6.04</td><td>Kosarek</td><td>-10.98</td><td>-11.04</td><td>-11.53</td><td><strong>-10.89</strong></td></tr><tr><td>KDD-2k</td><td><strong>-2.18</strong></td><td>-2.35</td><td>-2.21</td><td>-2.34</td><td>MSWeb</td><td>-10.25</td><td>-9.85</td><td>-10.20</td><td><strong>-9.68</strong></td></tr><tr><td>Plants</td><td>-12.97</td><td>-12.87</td><td>-13.37</td><td><strong>-12.57</strong></td><td>Book</td><td>-35.88</td><td>-34.33</td><td>-40.19</td><td><strong>-33.03</strong></td></tr><tr><td>Audio</td><td>-40.50</td><td>-39.84</td><td>-46.84</td><td><strong>-39.65</strong></td><td>E Movie</td><td><strong>-52.48</strong></td><td>-56.84</td><td>-60.22</td><td>-55.22</td></tr><tr><td>Jester</td><td>-75.98</td><td>-53.23</td><td>-64.50</td><td><strong>-53.00</strong></td><td>WebKB</td><td><strong>-158.20</strong></td><td>-159.53</td><td>-171.95</td><td>-158.70</td></tr><tr><td>Netflix</td><td>-57.32</td><td>-56.82</td><td>-69.74</td><td><strong>-56.49</strong></td><td>Reut.52</td><td><strong>-85.06</strong></td><td>-87.93</td><td>-91.35</td><td>-88.33</td></tr><tr><td>Accid.</td><td>-30.03</td><td><strong>-28.89</strong></td><td>-31.59</td><td>-29.54</td><td>20ng</td><td>-155.92</td><td>-122.16</td><td>-176.56</td><td><strong>-121.09</strong></td></tr><tr><td>Retail</td><td>-11.04</td><td>-11.09</td><td>-11.12</td><td><strong>-10.88</strong></td><td>BBC</td><td>-250.68</td><td><strong>-247.81</strong></td><td>-300.33</td><td>-249.38</td></tr><tr><td>Pumsb.</td><td>-24.78</td><td><strong>-24.10</strong></td><td>-25.06</td><td>-24.81</td><td>Ad</td><td>-19.73</td><td>-18.53</td><td><strong>-16.31</strong></td><td>-20.30</td></tr></tbody></table>

# 4. Experiments

We report here the results obtained in three series of experiments to evaluate our hypothesis about learning-inference compatibility and potential drawbacks of LearnSPN, by comparing its performance against SoftLearn.

## 4.1. Procedure

First, we compare the test log-likelihood of SoftLearn against LearnSPN on discrete and mixed datasets. In a second step, we focus on the generative ability of the LearnSPN and SoftLearn algorithms: first, we visually compare the quality of samples generated by SoftLearn and LearnSPN on an image dataset, and then we numerically compare the quality of samples generated by SoftLearn and LearnSPN on discrete datasets. In a last experiment, we compare the test log-likelihood of SoftLearn against LearnSPN when the datasets contain missing values. Additionally, we report an analysis of the execution times of the methods compared in Appendix D.

On discrete (binary) datasets, SoftLearn is compared against both implementations of LearnSPN [28,9]. For the rest of the experiments, since we have no access to the original implementation of LearnSPN [9], the comparison is held between SoftLearn and LearnSPN [28]. Both algorithms are optimized over two sets of hyperparameters, namely the chi-square test significance $p \in \{0.01, 0.001, 0.0001\}$ and the Laplace smoothing parameter of multinomial density estimation $\alpha \in \{0.1, 0.01, 10^{-6}\}$ (as usual on discrete data counts).

## 4.2. Test log-likelihood

**Binary datasets.** We compare the test log-likelihood of our method against LearnSPN [28,9] on 20 real-world datasets [29,30]. The number of instances varies from 2K to 388K, and the number of variables from 16 to 1556. More details about the datasets considered can be found in Appendix A.

In addition to the LearnSPN and SoftLearn approaches, we include the results of CNET [31], as this method combines a hard learning scheme with a hard inference scheme, representing the other side of the learning-inference spectrum. Note that [31] report 3 sets of results for 3 different versions of CNET, among which MCNET (which consists of an ensemble of CNETs) shows strong results and outperforms our method on several datasets; however, since our method does not include an ensemble of models and/or pruning, we only report the results for the vanilla CNET, as it is the most comparable version to SoftLearn. All in all, we do not seek to claim whether SoftLearn is the best over all methods to learn SPNs.

The results for LearnSPN [9] and CNET are reported from their corresponding paper. The results for LearnSPN [28] and SoftLearn are the average of 9 repetitions, and are summarized in Table 1.

**Mixed datasets.** We compare the test log-likelihood of the methods over a selection of datasets from the OpenML-CC18 benchmark [32]. Table 2 presents the results averaged over 9 repetitions.

As the results in Table 1 suggest, SoftLearn manages to outperform both implementations of LearnSPN on 14 out of 20 discrete datasets, and to outperform CNET on 18 out of 20 datasets. It also performs better than LearnSPN [28] on all mixed datasets. This indicates that a soft learning scheme can have a positive impact on the performance of LearnSPN over discrete and mixed datasets. We attribute this to the learning-inference compatibility preserved by our soft learning scheme. SoftLearn results in softer margins between groups when clustering: as a result, if a datapoint is misgrouped, the induced error will not be as costly as with the original LearnSPN. We would also like to note that for mixed datasets, in SoftLearn, continuous variables are discretized for each independence test, which adds another layer of estimation to the algorithm; however, SoftLearn still manages to outperform its contenders.

We also study the possibility of early stopping clustering algorithms to try to demonstrate the greater robustness of SoftLearn to potentially worse clustering results (with the benefit of speeding up the learning, as one can have fewer iterations). We limited clustering to only 2 iterations (which generally does not make it possible to reach convergence). The results (last column in Table 2) suggest that the speed up comes with little harm to the accuracy of the model, which still outperforms LearnSPN run without early stopping (broader experiments are needed for a more conclusive claim in this regard; current experiments suggest the potential).
<caption>**Table 2**</caption>

Performance results of LearnSPN vs. SoftLearn on mixed datasets; the last column displays results obtained using SoftLearn with at most 2 clustering iterations in the clustering steps, thus enforcing early stopping (often before convergence).

<table><caption>**Table 3**</caption><thead><tr><th>Dataset</th><th>L-SPN</th><th>SoftLearn</th><th>Early SoftLearn</th></tr></thead><tbody><tr><td>bank</td><td>-20.139</td><td><b>-19.993</b></td><td><b>-19.997</b></td></tr><tr><td>electricity</td><td>-11.229</td><td><b>-11.217</b></td><td>-11.226</td></tr><tr><td>segment</td><td>-17.517</td><td><b>-17.480</b></td><td>-17.493</td></tr><tr><td>german</td><td>-22.720</td><td><b>-22.395</b></td><td>-22.470</td></tr><tr><td>vowel</td><td>-16.957</td><td><b>-16.584</b></td><td>-16.634</td></tr><tr><td>cmc</td><td>-9.850</td><td><b>-9.811</b></td><td>-9.838</td></tr></tbody></table>

Performance drop for PCs trained on synthetically generated samples, averaged over 3 repetitions.

<table><thead><tr><th rowspan="3">Dataset</th><th colspan="4">Test Log Likelihood</th></tr><tr><th colspan="2">LearnSPN</th><th colspan="2">SoftLearn</th></tr><tr><th>Orig.</th><th>Synth.</th><th>Orig.</th><th>Synth.</th></tr></thead><tbody><tr><td>NLTCS</td><td>-5.997</td><td>-6.051</td><td>-5.976</td><td>-6.022</td></tr><tr><td>Audio</td><td>-39.823</td><td>-40.307</td><td>-39.649</td><td>-40.143</td></tr><tr><td>Retail</td><td>-11.074</td><td>-11.196</td><td>-10.880</td><td>-10.974</td></tr><tr><td>MSWeb</td><td>-9.833</td><td>-10.058</td><td>-9.696</td><td>-9.982</td></tr><tr><td>Reuters-52</td><td>-87.838</td><td>-90.741</td><td>-88.609</td><td>-97.002</td></tr></tbody></table>

<figure><img src="image_8.png" /><figcaption>**Fig. 4.** Samples of digits generated using LearnSPN (left) and SoftLearn (right).</figcaption></figure>

## 4.3. Quality of generated samples

**Visual assessment on image data.** We employ LearnSPN [28] and SoftLearn to learn PCs over the binary-MNIST [33] dataset, so that we can qualitatively evaluate the samples generated by both of the PCs. We decide to learn each PC on a single class of the dataset at a time in order to better visualize the samples. Fig. 4 shows the generated samples from PCs learned on classes 9 and 5 of the dataset, respectively.

As the results would suggest, the samples generated from the PC learned by SoftLearn appear to be less cluttered. We believe the soft clustering to be responsible for some better samples when compared to those generated from the PC trained with LearnSPN. Samples drawn from SoftLearn are mostly clear to interpret, even if they can also be noisy or erroneous.

**Numerical assessment via test log-likelihood.** Here, we aim to confirm the observations above by numerically comparing the quality of samples generated from PCs learned via LearnSPN and SoftLearn. We follow the experiment setup proposed by [34]. For each algorithm and dataset, i.e., we (i) learn a PC over the training dataset (using the best-performing set of hyperparameters); (ii) generate a synthetic dataset using the learned PC; (iii) learn another PC over the generated synthetic dataset; and (iv) interpret the test log-likelihood of learned PCs as an indicator for the quality of generated samples.

The results of this experiment over 5 datasets are summarized in Table 3. While SoftLearn still outperforms LearnSPN on 4 out of 5 datasets, it shows a greater performance drop in 3 out of 5 experiments. This shows that while SoftLearn seems to generate better samples, whether or not its performance is more affected by the synthetic data remains inconclusive.

## 4.4. Missing values

We compare the performance of LearnSPN vs. SoftLearn (in terms of test log-likelihood) when they are trained on datasets which include missing values. For this particular experiment, we assume that data is missing completely at random (MCAR). We consider
<figure><img src="image_9.png" /><figcaption>Fig. 5. Performance of SoftLearn vs. LearnSPN on binary datasets with missing values.</figcaption></figure>

the same binary datasets as in Section 4.2, nevertheless, we see no reason to expect different results when the experiment is done on a different collection of datasets. We take complete data and randomly (uniformly) remove a certain percentage of values in the training set. Note that training with missing values is another special characteristic of these PC algorithms, as they can be easily adapted to deal with incomplete training data by simple modifications of the independence tests and the clustering algorithms. The numerical results are summarized in Tables 4, 5, 6, and Figs. 5, 6. For more details on the results (separated EM/KM results, standard deviation of the reported log-likelihoods, the set of optimal hyperparameters resulting the best performance for each scenario), please refer to Tables E.15 to E.24 in Appendix E.
<figure><img src="image_10.png" /><figcaption>Fig. 6. Performance of SoftLearn vs. LearnSPN on binary datasets with missing values.</figcaption></figure>

Based on the reported results over a total of 100 different configurations, SoftLearn manages to outperform LearnSPN in 97 scenarios, while performing on par with it in one of the experiments. This clearly suggest that SoftLearn has a noticeable advantage when learning from datasets with missing data. Please also note that in the experiments on datasets with missing values, the gap between the best-performing SoftLearn and LearnSPN variants are usually much larger when compared to the case where the models are trained on complete data, which arguably makes SoftLearn a clear option (vs. LearnSPN) in these scenarios.
<table><caption>**Table 4**
Performance results of SoftLearn vs. LearnSPN [28] on binary datasets with missing values.</caption><thead><tr><th colspan="3">10% missing data</th><th colspan="3">20% missing data</th></tr><tr><th>Dataset</th><th colspan="2">Method</th><th>Dataset</th><th colspan="2">Method</th></tr><tr><th></th><th>SoftLearn</th><th>L-SPN</th><th></th><th>SoftLearn</th><th>L-SPN</th></tr></thead><tbody><tr><td>NLPCS</td><td>-5.993</td><td>-6.019</td><td>NLPCS</td><td>-6.008</td><td>-6.0737</td></tr><tr><td>MSNBC</td><td>-6.107</td><td>-6.107</td><td>MSNBC</td><td>-6.156</td><td>-6.213</td></tr><tr><td>KDDCup2k</td><td>-2.345</td><td>-2.357</td><td>KDDCup2k</td><td>-2.352</td><td>-2.375</td></tr><tr><td>Plants</td><td>-12.773</td><td>-13.147</td><td>Plants</td><td>-12.914</td><td>-13.427</td></tr><tr><td>Audio</td><td>-39.787</td><td>-40.017</td><td>Audio</td><td>-39.938</td><td>-40.353</td></tr><tr><td>Jester</td><td>-53.163</td><td>-53.437</td><td>Jester</td><td>-53.305</td><td>-53.751</td></tr><tr><td>Netflix</td><td>-56.651</td><td>-57.055</td><td>Netflix</td><td>-56.859</td><td>-57.365</td></tr><tr><td>Accidents</td><td>-30.746</td><td>-31.241</td><td>Accidents</td><td>-31.565</td><td>-34.529</td></tr><tr><td>Retail</td><td>-11.172</td><td>-11.239</td><td>Retail</td><td>-11.141</td><td>-11.318</td></tr><tr><td>Pumsb-star</td><td>-26.221</td><td>-26.968</td><td>Pumsb-star</td><td>-27.399</td><td>-29.628</td></tr><tr><td>DNA</td><td>-83.345</td><td>-84.129</td><td>DNA</td><td>-84.232</td><td>-85.591</td></tr><tr><td>Kosarek</td><td>-11.110</td><td>-11.373</td><td>Kosarek</td><td>-11.212</td><td>-11.598</td></tr><tr><td>MSWeb</td><td>-9.911</td><td>-10.250</td><td>MSWeb</td><td>-10.042</td><td>-10.483</td></tr><tr><td>Book</td><td>-34.290</td><td>-36.015</td><td>Book</td><td>-34.884</td><td>-36.898</td></tr><tr><td>EachMovie</td><td>-57.492</td><td>-60.857</td><td>EachMovie</td><td>-58.556</td><td>-62.478</td></tr><tr><td>WebKB</td><td>-163.518</td><td>-175.991</td><td>WebKB</td><td>-166.428</td><td>-180.047</td></tr><tr><td>Reuters-52</td><td>-90.830</td><td>-96.615</td><td>Reuters-52</td><td>-91.189</td><td>-98.308</td></tr><tr><td>20 Newsgrp.</td><td>-121.236</td><td>-132.352</td><td>20 Newsgrp.</td><td>-122.590</td><td>-134.831</td></tr><tr><td>BBC</td><td>-251.233</td><td>-270.534</td><td>BBC</td><td>-255.223</td><td>-277.052</td></tr><tr><td>Ad</td><td>-21.184</td><td>-20.556</td><td>Ad</td><td>-20.660</td><td>-21.900</td></tr></tbody></table>

<table><caption>**Table 5**
Performance results of SoftLearn vs. LearnSPN [28] on binary datasets with missing values.</caption><thead><tr><th colspan="3">30% missing data</th><th colspan="3">40% missing data</th></tr><tr><th>Dataset</th><th colspan="2">Method</th><th>Dataset</th><th colspan="2">Method</th></tr><tr><th></th><th>SoftLearn</th><th>L-SPN</th><th></th><th>SoftLearn</th><th>L-SPN</th></tr></thead><tbody><tr><td>NLPCS</td><td>-6.038</td><td>-6.167</td><td>NLPCS</td><td>-6.101</td><td>-6.289</td></tr><tr><td>MSNBC</td><td>-6.216</td><td>-6.359</td><td>MSNBC</td><td>-6.312</td><td>-6.546</td></tr><tr><td>KDDCup2k</td><td>-2.368</td><td>-2.399</td><td>KDDCup2k</td><td>-2.393</td><td>-2.442</td></tr><tr><td>Plants</td><td>-13.052</td><td>-13.789</td><td>Plants</td><td>-13.244</td><td>-14.238</td></tr><tr><td>Audio</td><td>-40.135</td><td>-40.661</td><td>Audio</td><td>-40.415</td><td>-41.089</td></tr><tr><td>Jester</td><td>-53.520</td><td>-54.172</td><td>Jester</td><td>-53.851</td><td>-54.722</td></tr><tr><td>Netflix</td><td>-57.094</td><td>-57.791</td><td>Netflix</td><td>-57.443</td><td>-58.399</td></tr><tr><td>Accidents</td><td>-32.677</td><td>-36.656</td><td>Accidents</td><td>-34.699</td><td>-38.803</td></tr><tr><td>Retail</td><td>-11.160</td><td>-11.531</td><td>Retail</td><td>-11.230</td><td>-11.718</td></tr><tr><td>Pumsb-star</td><td>-28.638</td><td>-31.636</td><td>Pumsb-star</td><td>-29.636</td><td>-33.095</td></tr><tr><td>DNA</td><td>-85.755</td><td>-88.336</td><td>DNA</td><td>-87.417</td><td>-91.936</td></tr><tr><td>Kosarek</td><td>-11.329</td><td>-11.797</td><td>Kosarek</td><td>-11.426</td><td>-12.171</td></tr><tr><td>MSWeb</td><td>-10.133</td><td>-10.733</td><td>MSWeb</td><td>-10.331</td><td>-11.180</td></tr><tr><td>Book</td><td>-35.240</td><td>-37.595</td><td>Book</td><td>-35.710</td><td>-38.046</td></tr><tr><td>EachMovie</td><td>-59.491</td><td>-63.108</td><td>EachMovie</td><td>-60.256</td><td>-64.071</td></tr><tr><td>WebKB</td><td>-169.176</td><td>-182.498</td><td>WebKB</td><td>-173.026</td><td>-184.290</td></tr><tr><td>Reuters-52</td><td>-93.643</td><td>-99.872</td><td>Reuters-52</td><td>-95.484</td><td>-101.655</td></tr><tr><td>20 Newsgrp.</td><td>-124.028</td><td>-136.353</td><td>20 Newsgrp.</td><td>-126.105</td><td>-137.917</td></tr><tr><td>BBC</td><td>-259.028</td><td>-279.090</td><td>BBC</td><td>-262.663</td><td>-283.070</td></tr><tr><td>Ad</td><td>-22.672</td><td>-23.418</td><td>Ad</td><td>-24.718</td><td>-25.799</td></tr></tbody></table>

## 5. Conclusion

In this paper, we addressed the problem of learning a probabilistic circuit from data. Many algorithms have been proposed for this purpose; we focused on a very prominent one, LearnSPN, which yields a certain incompatibility in the way that instances are treated during training and testing times. We shed some light on the importance of learning-inference consistency, and showed how repeating greedily hard clustering steps during learning can lead to rigid partitions and poor generalization.

Based on these considerations, we proposed SoftLearn, a soft structure-learning scheme which aims at mitigating the costs of such greedy behaviors by taking soft cluster memberships into account rather than hard ones. This seemingly reasonably simple idea nevertheless requires intricate changes in the clustering and independence test methods, including modifications for dealing with
<table><caption>**Table 6**
Performance results of SoftLearn vs. LearnSPN [28] on binary datasets with missing values.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="2">50% missing data</th></tr><tr><th>Method</th><th></th></tr><tr><th></th><th>SoftLearn</th><th>L-SPN</th></tr></thead><tbody><tr><td>NLTCS</td><td><strong>-6.221</strong></td><td>-6.555</td></tr><tr><td>MSNBC</td><td><strong>-6.440</strong></td><td>-6.872</td></tr><tr><td>KDDCup2k</td><td><strong>-2.469</strong></td><td>-2.575</td></tr><tr><td>Plants</td><td><strong>-13.566</strong></td><td>-14.939</td></tr><tr><td>Audio</td><td><strong>-40.766</strong></td><td>-41.820</td></tr><tr><td>Jester</td><td><strong>-54.306</strong></td><td>-55.337</td></tr><tr><td>Netflix</td><td><strong>-57.908</strong></td><td>-59.230</td></tr><tr><td>Accidents</td><td><strong>-35.409</strong></td><td>-40.079</td></tr><tr><td>Retail</td><td><strong>-11.524</strong></td><td>-12.292</td></tr><tr><td>Pumsb-star</td><td><strong>-31.208</strong></td><td>-34.129</td></tr><tr><td>DNA</td><td><strong>-89.504</strong></td><td>-96.694</td></tr><tr><td>Kosarek</td><td><strong>-11.788</strong></td><td>-12.840</td></tr><tr><td>MSWeb</td><td><strong>-10.626</strong></td><td>-11.822</td></tr><tr><td>Book</td><td><strong>-36.233</strong></td><td>-39.377</td></tr><tr><td>EachMovie</td><td><strong>-61.385</strong></td><td>-64.911</td></tr><tr><td>WebKB</td><td><strong>-176.820</strong></td><td>-186.922</td></tr><tr><td>Reuters-52</td><td><strong>-97.986</strong></td><td>-103.517</td></tr><tr><td>20 Newsgrp.</td><td><strong>-127.668</strong></td><td>-139.141</td></tr><tr><td>BBC</td><td><strong>-268.141</strong></td><td>-287.311</td></tr><tr><td>Ad</td><td><strong>-30.106</strong></td><td><strong>-29.772</strong></td></tr></tbody></table>

cases of incomplete training data. We discussed how both LearnSPN and the SoftLearn proposal aim at improving the likelihood of the model, hinting that soft-clustering-based approaches may be superior in that regard due to a finer modeling of the cluster memberships. In fact, this is not such a surprise, as soft Expectation-Maximization (also known simply by EM) is known to be superior to hard EM in many scenarios. This insight was confirmed by our experiments, which showed that SoftLearn outperforms LearnSPN on various configurations on test likelihoods, and arguably generates better samples likely due to its smoother partition margins, with special attention to training data with missing values.

We believe structure learning to be a major point of concern for PCs to reach greater accuracy in real-world applications, in particular for structured/tabular data. SoftLearn can be seen as a step in that direction by trying to mitigate greediness. Multiple avenues remain to be explored in learning the structure of PCs, which may constitute important future work. We intend to continue the study with pruning/merging techniques and to move away from excessively greedy structure-learning approaches. We also believe that the increased generative power of SoftLearn, as demonstrated in our experiments, could be leveraged in advanced strategies such as adversarial training.

## CRediT authorship contribution statement

**Soroush Ghandi:** Writing – review & editing, Writing – original draft, Visualization, Validation, Software, Methodology, Investigation, Data curation, Conceptualization. **Benjamin Quost:** Writing – review & editing, Writing – original draft, Validation, Supervision, Resources, Methodology, Investigation, Formal analysis, Conceptualization. **Cassio P. de Campos:** Writing – review & editing, Writing – original draft, Validation, Supervision, Project administration, Methodology, Investigation, Funding acquisition, Formal analysis, Conceptualization.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

## Appendix A. Dataset details

As mentioned in Section 4.2, we use a set of twenty real-world binary datasets [29,30] and 6 real-world mixed datasets [32] for the log-likelihood experiments. Over the binary datasets, the number of instances varies from 2K to 388K, and the number of variables from 16 to 1556; over the mixed datasets, the number of variables varies from 9 to 21, and the number of instances from 990 to 45312. The details regarding these datasets are outlined in Tables A.7 and A.8. Note that the binary datasets are already divided into train, validation, and test sets, and hence, the details regarding the size of each set are also reported in the table.
<table><caption>**Table A.7**
Discrete datasets statistics.</caption><thead><tr><th>Dataset</th><th>Vars.</th><th>Train</th><th>Valid.</th><th>Test</th><th>Density</th></tr></thead><tbody><tr><td>NLTCS</td><td>16</td><td>16181</td><td>2157</td><td>3236</td><td>0.332</td></tr><tr><td>MSNBC</td><td>17</td><td>291326</td><td>38843</td><td>58265</td><td>0.166</td></tr><tr><td>KDDCup2k</td><td>65</td><td>180092</td><td>19907</td><td>34955</td><td>0.008</td></tr><tr><td>Plants</td><td>69</td><td>17412</td><td>2321</td><td>3482</td><td>0.180</td></tr><tr><td>Audio</td><td>100</td><td>15000</td><td>2000</td><td>3000</td><td>0.199</td></tr><tr><td>Jester</td><td>100</td><td>9000</td><td>1000</td><td>4116</td><td>0.608</td></tr><tr><td>Netflix</td><td>100</td><td>15000</td><td>2000</td><td>3000</td><td>0.541</td></tr><tr><td>Accidents</td><td>111</td><td>12758</td><td>1700</td><td>2551</td><td>0.291</td></tr><tr><td>Retail</td><td>135</td><td>22041</td><td>2938</td><td>4408</td><td>0.024</td></tr><tr><td>Pumsb-star</td><td>163</td><td>12262</td><td>1635</td><td>2452</td><td>0.270</td></tr><tr><td>DNA</td><td>180</td><td>1600</td><td>400</td><td>1186</td><td>0.253</td></tr><tr><td>Kosarak</td><td>190</td><td>33375</td><td>4450</td><td>6675</td><td>0.020</td></tr><tr><td>MSWeb</td><td>294</td><td>29441</td><td>3270</td><td>5000</td><td>0.010</td></tr><tr><td>Book</td><td>500</td><td>8700</td><td>1159</td><td>1739</td><td>0.016</td></tr><tr><td>EachMovie</td><td>500</td><td>4524</td><td>1002</td><td>591</td><td>0.059</td></tr><tr><td>WebKB</td><td>839</td><td>2803</td><td>558</td><td>838</td><td>0.064</td></tr><tr><td>Reuters-52</td><td>889</td><td>6532</td><td>1028</td><td>1540</td><td>0.036</td></tr><tr><td>20 Newsgrp.</td><td>910</td><td>11293</td><td>3764</td><td>3764</td><td>0.049</td></tr><tr><td>BBC</td><td>1058</td><td>1670</td><td>225</td><td>330</td><td>0.078</td></tr><tr><td>Ad</td><td>1556</td><td>2461</td><td>327</td><td>491</td><td>0.008</td></tr></tbody></table>

<table><caption>**Table A.8**
Mixed datasets statistics.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="2">Vars.</th><th rowspan="2">Size</th></tr><tr><th>Categorical</th><th>Numeric</th></tr></thead><tbody><tr><td>bank</td><td>10</td><td>7</td><td>45211</td></tr><tr><td>electricity</td><td>2</td><td>7</td><td>45312</td></tr><tr><td>segment</td><td>1</td><td>19</td><td>2310</td></tr><tr><td>german</td><td>14</td><td>7</td><td>1000</td></tr><tr><td>vowel</td><td>3</td><td>10</td><td>990</td></tr><tr><td>cmc</td><td>8</td><td>2</td><td>1473</td></tr></tbody></table>

## Appendix B. Experiment details

In this section, we present supplementary results and details of our experiments, in addition to the results reported in Section 4. For each method (LearnSPN and SoftLearn), and for each dataset category (binary and mixed), we present a table outlining more details regarding the experiments. Each table provides a more detailed version of the results, which decomposes the results over the clustering method and provides the standard deviation of the results over the 9 repetitions of the experiments. In addition to that, each table also provides the hyperparameter configurations to reproduce the reported results. Tables B.9 and B.11 are dedicated to the experiments of LearnSPN and SoftLearn on binary datasets. Similarly, Tables B.10 and B.12 are dedicated to respective experiments of LearnSPN and SoftLearn on mixed datasets.

<table><caption>**Table B.9**
Performance of LearnSPN [28] on binary datasets.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td>-5.997 ± 0.008</td><td>0.01</td><td>0.01</td><td>-5.995 ± 0.007</td><td>0.01</td><td>0.1</td></tr><tr><td>MSNBC</td><td>-6.042 ± 0.003</td><td>0.01</td><td>0.1</td><td><b>-6.041</b> ± 0.001</td><td>0.01</td><td>0.1</td></tr><tr><td>KDDCup2k</td><td>-2.350 ± 0.001</td><td>0.001</td><td>0.1</td><td>-2.360 ± 0.003</td><td>0.0001</td><td>0.1</td></tr><tr><td>Plants</td><td>-12.878 ± 0.026</td><td>0.01</td><td>0.1</td><td>-12.908 ± 0.020</td><td>0.01</td><td>0.1</td></tr><tr><td>Audio</td><td>-39.841 ± 0.018</td><td>0.001</td><td>10<sup>-6</sup></td><td>-39.938 ± 0.038</td><td>0.001</td><td>0.1</td></tr><tr><td>Jester</td><td>-53.235 ± 0.031</td><td>0.001</td><td>0.1</td><td>-53.234 ± 0.026</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td>-56.818 ± 0.027</td><td>0.001</td><td>10<sup>-6</sup></td><td>-56.844 ± 0.028</td><td>0.001</td><td>0.1</td></tr><tr><td>Accidents</td><td><b>-28.895</b> ± 0.122</td><td>0.0001</td><td>0.1</td><td>-29.114 ± 0.070</td><td>0.0001</td><td>0.01</td></tr><tr><td>Retail</td><td>-11.092 ± 0.047</td><td>0.0001</td><td>0.1</td><td>-11.142 ± 0.017</td><td>0.0001</td><td>0.1</td></tr><tr><td>Pumsb-star</td><td><b>-24.101</b> ± 0.088</td><td>0.0001</td><td>0.1</td><td>-24.206 ± 0.085</td><td>0.0001</td><td>0.1</td></tr><tr><td>DNA</td><td>-83.674 ± 0.233</td><td>0.0001</td><td>0.1</td><td>-83.798 ± 0.182</td><td>0.0001</td><td>0.1</td></tr><tr><td>Kosarak</td><td>-11.043 ± 0.035</td><td>0.0001</td><td>0.1</td><td>-11.188 ± 0.037</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td>-9.847 ± 0.025</td><td>0.0001</td><td>0.1</td><td>-10.015 ± 0.018</td><td>0.0001</td><td>0.1</td></tr></tbody></table>

(continued on next page)
<table><caption>Table B.9 (continued)</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>Book</td><td>-34.334 ± 0.093</td><td>0.0001</td><td>0.1</td><td>-34.428 ± 0.080</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td>-56.842 ± 0.078</td><td>0.0001</td><td>0.1</td><td>-57.129 ± 0.069</td><td>0.0001</td><td>0.1</td></tr><tr><td>WebKB</td><td>-159.533 ± 0.227</td><td>0.0001</td><td>0.1</td><td>-160.601 ± 0.331</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td>-87.932 ± 0.144</td><td>0.0001</td><td>0.1</td><td>-88.400 ± 0.161</td><td>0.0001</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td>-122.162 ± 0.138</td><td>0.0001</td><td>0.1</td><td>-122.827 ± 0.121</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td>-248.293 ± 0.464</td><td>0.0001</td><td>0.1</td><td><strong>-247.815 ± 0.248</strong></td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td>-18.539 ± 0.152</td><td>0.001</td><td>0.1</td><td>-18.738 ± 0.403</td><td>0.01</td><td>0.01</td></tr></tbody></table>

<caption>Table B.10</caption>

Performance of LearnSPN [28] on mixed datasets.

<table><caption>Table B.11</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>bank</td><td>-20.139 ± 0.030</td><td>0.01</td><td>0.1</td><td>-20.277 ± 0.045</td><td>0.01</td><td>0.01</td></tr><tr><td>electricity</td><td>-11.229 ± 0.011</td><td>0.001</td><td>0.01</td><td>-11.488 ± 0.010</td><td>0.0001</td><td>0.1</td></tr><tr><td>segment</td><td>-17.517 ± 0.081</td><td>0.01</td><td>0.1</td><td>-17.663 ± 0.090</td><td>0.01</td><td>0.01</td></tr><tr><td>german</td><td>-22.720 ± 0.158</td><td>0.001</td><td>0.1</td><td>-22.857 ± 0.174</td><td>0.001</td><td>0.1</td></tr><tr><td>vowel</td><td>-16.957 ± 0.079</td><td>0.01</td><td>10<sup>-6</sup></td><td>-17.086 ± 0.076</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>cmc</td><td>-9.850 ± 0.087</td><td>0.01</td><td>0.1</td><td>-9.902 ± 0.128</td><td>0.01</td><td>0.1</td></tr></tbody></table>

Performance of SoftLearn on binary datasets.

<table><caption>Table B.12</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td>-5.979 ± 0.006</td><td>0.01</td><td>10<sup>-6</sup></td><td><strong>-5.974 ± 0.002</strong></td><td>0.01</td><td>0.01</td></tr><tr><td>MSNBC</td><td>-6.056 ± 0.003</td><td>0.01</td><td>0.01</td><td>-6.048 ± 0.001</td><td>0.01</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td>-2.372 ± 0.006</td><td>0.0001</td><td>10<sup>-6</sup></td><td>-2.345 ± 0.005</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Plants</td><td>-12.643 ± 0.015</td><td>0.01</td><td>0.1</td><td><strong>-12.572 ± 0.013</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><strong>-39.659 ± 0.023</strong></td><td>0.01</td><td>0.1</td><td>-40.346 ± 0.014</td><td>0.01</td><td>0.01</td></tr><tr><td>Jester</td><td><strong>-53.005 ± 0.041</strong></td><td>0.01</td><td>0.1</td><td>-53.545 ± 0.019</td><td>0.01</td><td>0.1</td></tr><tr><td>Netflix</td><td><strong>-56.491 ± 0.016</strong></td><td>0.01</td><td>0.1</td><td>-57.698 ± 0.015</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td>-30.092 ± 0.133</td><td>0.0001</td><td>0.1</td><td>-29.544 ± 0.049</td><td>0.0001</td><td>0.01</td></tr><tr><td>Retail</td><td>-11.040 ± 0.021</td><td>0.0001</td><td>0.1</td><td><strong>-10.888 ± 0.010</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Pumsb-star</td><td>-24.818 ± 0.244</td><td>0.0001</td><td>0.1</td><td>-28.397 ± 0.212</td><td>0.0001</td><td>0.01</td></tr><tr><td>DNA</td><td>-83.026 ± 0.240</td><td>0.0001</td><td>0.01</td><td><strong>-82.062 ± 0.078</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td>-11.108 ± 0.009</td><td>0.0001</td><td>0.1</td><td><strong>-10.890 ± 0.020</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>MSWeb</td><td>-9.881 ± 0.049</td><td>0.001</td><td>0.1</td><td><strong>-9.688 ± 0.007</strong></td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Book</td><td>-34.173 ± 0.080</td><td>0.0001</td><td>0.1</td><td><strong>-33.031 ± 0.022</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td>-57.401 ± 0.166</td><td>0.0001</td><td>0.1</td><td>-55.225 ± 0.058</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>WebKB</td><td>-162.361 ± 1.400</td><td>0.0001</td><td>0.1</td><td>-158.703 ± 1.015</td><td>0.01</td><td>0.01</td></tr><tr><td>Reuters-52</td><td>-90.240 ± 0.525</td><td>0.001</td><td>0.1</td><td>-88.338 ± 0.239</td><td>0.01</td><td>0.01</td></tr><tr><td>20 Newsgrp.</td><td>-121.218 ± 0.138</td><td>0.0001</td><td>0.1</td><td><strong>-121.091 ± 0.127</strong></td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>BBC</td><td>-249.381 ± 0.937</td><td>0.0001</td><td>0.1</td><td>-250.080 ± 0.533</td><td>0.01</td><td>0.01</td></tr><tr><td>Ad</td><td>-20.309 ± 0.794</td><td>0.01</td><td>0.01</td><td>-40.129 ± 1.791</td><td>0.01</td><td>0.01</td></tr></tbody></table>

Performance of SoftLearn on mixed datasets.

<table><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>bank</td><td><strong>-19.993 ± 0.044</strong></td><td>0.0001</td><td>0.1</td><td>-20.132 ± 0.033</td><td>0.01</td><td>0.01</td></tr><tr><td>electricity</td><td><strong>-11.217 ± 0.021</strong></td><td>0.01</td><td>10<sup>-6</sup></td><td>-11.422 ± 0.012</td><td>0.0001</td><td>0.1</td></tr><tr><td>segment</td><td><strong>-17.480 ± 0.071</strong></td><td>0.001</td><td>10<sup>-6</sup></td><td>-17.625 ± 0.100</td><td>0.001</td><td>0.01</td></tr><tr><td>german</td><td>-22.423 ± 0.186</td><td>0.01</td><td>0.1</td><td><strong>-22.395 ± 0.187</strong></td><td>0.01</td><td>0.1</td></tr><tr><td>vowel</td><td><strong>-16.584 ± 0.156</strong></td><td>0.01</td><td>10<sup>-6</sup></td><td>-17.347 ± 0.169</td><td>0.01</td><td>0.01</td></tr><tr><td>cmc</td><td>-9.820 ± 0.098</td><td>0.01</td><td>0.01</td><td><strong>-9.811 ± 0.060</strong></td><td>0.001</td><td>0.01</td></tr></tbody></table>

## Appendix C. Comparison with state-of-the-art

Once again, we would like to note that our motivation for proposing SoftLearn is not to compete with the state of the art methods, but to introduce a better *base model* compared to LearnSPN. LearnSPN is utilized as a base model (or a building block) for many
<table><caption>**Table C.13**
Performance results of SoftLearn vs. LearnSPN [9], LearnSPN [28], CNET [31], LearnPSDD [20], Hidden Chow Liu Trees [35], Einsum Networks [36], and RAT-SPN [37] over binary datasets.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="2">LearnSPN</th><th rowspan="2">CNET</th><th rowspan="2">Learn</th><th rowspan="2">HCLT</th><th rowspan="2">EiNet</th><th rowspan="2">RAT</th><th rowspan="2">Soft</th></tr><tr><th>Gens</th><th>Correia</th></tr></thead><tbody><tr><td>NLTCS</td><td>-6.110</td><td>-5.995</td><td>-6.10</td><td>-6.03</td><td>-5.99</td><td>-6.015</td><td>-6.01</td><td><strong>-5.974</strong></td></tr><tr><td>MSNBC</td><td>-6.113</td><td><strong>-6.041</strong></td><td>-6.06</td><td>-6.04</td><td>-6.05</td><td>-6.119</td><td>-6.04</td><td>-6.048</td></tr><tr><td>KDDCup2k</td><td><strong>-2.182</strong></td><td>-2.350</td><td>-2.21</td><td>-2.12</td><td>-2.18</td><td>-2.183</td><td>-2.13</td><td>-2.345</td></tr><tr><td>Plants</td><td>-12.977</td><td>-12.878</td><td>-13.37</td><td>-13.79</td><td>-14.26</td><td>-13.676</td><td>-13.44</td><td><strong>-12.572</strong></td></tr><tr><td>Audio</td><td>-40.503</td><td>-39.841</td><td>-46.84</td><td>-41.98</td><td>-39.77</td><td>-39.879</td><td>-39.96</td><td><strong>-39.659</strong></td></tr><tr><td>Jester</td><td>-75.989</td><td>-53.234</td><td>-64.50</td><td>-53.47</td><td><strong>-52.46</strong></td><td>-52.563</td><td>-52.97</td><td>-53.005</td></tr><tr><td>Netflix</td><td>-57.328</td><td>-56.818</td><td>-69.74</td><td>-58.41</td><td><strong>-56.27</strong></td><td>-56.544</td><td>-56.85</td><td>-56.491</td></tr><tr><td>Accidents</td><td>-30.038</td><td>-28.895</td><td>-31.59</td><td>-33.64</td><td><strong>-26.74</strong></td><td>-35.594</td><td>-35.49</td><td>-29.544</td></tr><tr><td>Retail</td><td>-11.043</td><td>-11.092</td><td>-11.12</td><td><strong>-10.81</strong></td><td>-10.84</td><td>-10.916</td><td>-10.91</td><td>-10.887</td></tr><tr><td>Pumsb-star</td><td>-24.781</td><td><strong>-24.101</strong></td><td>-25.06</td><td>-33.67</td><td>-23.64</td><td>-31.954</td><td>-32.53</td><td>-24.818</td></tr><tr><td>DNA</td><td>-82.523</td><td>-83.674</td><td>-109.79</td><td>-92.67</td><td><strong>-79.05</strong></td><td>-96.086</td><td>-97.23</td><td>-82.062</td></tr><tr><td>Kosarek</td><td>-10.989</td><td>-11.043</td><td>-11.53</td><td>-10.81</td><td><strong>-10.66</strong></td><td>-11.029</td><td>-10.89</td><td>-10.890</td></tr><tr><td>MSWeb</td><td>-10.252</td><td>-9.847</td><td>-10.20</td><td>-9.97</td><td>-9.98</td><td>-10.026</td><td>-10.12</td><td><strong>-9.688</strong></td></tr><tr><td>Book</td><td>-35.886</td><td>-34.334</td><td>-40.19</td><td>-34.97</td><td>-33.83</td><td>-34.739</td><td>-34.68</td><td><strong>-33.031</strong></td></tr><tr><td>EachMovie</td><td>-52.485</td><td>-56.842</td><td>-60.22</td><td>-58.01</td><td><strong>-50.81</strong></td><td>-51.705</td><td>-53.63</td><td>-55.225</td></tr><tr><td>WebKB</td><td>-158.204</td><td>-159.533</td><td>-171.95</td><td>-161.09</td><td><strong>-152.77</strong></td><td>-157.282</td><td>-157.53</td><td>-158.703</td></tr><tr><td>Reuters-52</td><td><strong>-85.067</strong></td><td>-87.932</td><td>-91.35</td><td>-89.61</td><td>-86.26</td><td>-87.368</td><td>-87.37</td><td>-88.338</td></tr><tr><td>20 Newsgrp.</td><td>-155.925</td><td>-122.162</td><td>-176.56</td><td>-161.09</td><td>-153.40</td><td>-153.938</td><td>-152.06</td><td><strong>-121.091</strong></td></tr><tr><td>BBC</td><td>-250.687</td><td><strong>-247.815</strong></td><td>-300.33</td><td>-253.19</td><td>-251.04</td><td>-248.332</td><td>-252.14</td><td>-249.381</td></tr><tr><td>Ad</td><td>-19.733</td><td>-18.539</td><td>-16.31</td><td>-31.78</td><td><strong>-16.07</strong></td><td>-26.273</td><td>-48.47</td><td>-20.309</td></tr></tbody></table>

subsequent algorithms that managed to achieve impressive competitive results, outperforming LearnSPN itself. Such algorithms can utilize SoftLearn interchangeably, and based on the results reported in this paper, we believe that utilizing SoftLearn instead of LearnSPN will lead to noticeable performance gains, helping other algorithms achieve or surpass state of the art. Hence, our experiments were mainly designed to compare SoftLearn with its main competitor, LearnSPN, on a variety of test configurations. Nevertheless, we include a comparison between SoftLearn and some of the state of the art methods (namely LearnPSDD [20], Hidden Chow Liu Trees [35], Einsum Networks [36], and RAT-SPN [37]) on binary datasets in Table C.13.

SoftLearn manages to outperform LearnPSDD on 16 out of 20 datasets, EiNet on 14 out of 20 datasets, and RAT-SPN on 15 out of 20 datasets. The only method that performs better on average than SoftLearn is HCLT (SoftLearn still outperforms HCLT on 8 out of 20 datasets), which has a larger set of hyperparameters and is fine-tuned over a larger (and more precise) set of hyperparameter configurations. In addition, SoftLearn manages to achieve the best results (among all the aforementioned methods) over 6 out of 20 datasets (On a separate not, we would like to mention that ID-SPN [38] also manages to statistically outperform SoftLearn on average, however, we do not consider ID-SPN a reasonable competitor since its resulting structures are orders of magnitude larger than the structures learned by SoftLearn and LearnSPN. This means that ID-SPN potentially achieves better performance at the cost of over-parametrization and larger amount of computations, which does not lead to an unbiased comparison). These results show that despite its simple design as a base model (like LearnSPN), SoftLearn is competitive to state of the art models, while having a very large room to grow when used as a building block of more elaborate methods.

## Appendix D. Execution times

Although SoftLearn statistically outperforms LearnSPN on a variety of experiments, this advantage comes at the cost of higher execution (learning) times. From a theoretical point of view, this is expected since SoftLearn theoretically propagates all data points

<table><caption>**Table D.14**
Average execution time (in seconds) of SoftLearn vs. LearnSPN [28] over binary datasets. Best-performing hyperparameters are used for both methods.</caption><thead><tr><th>Data</th><th>LearnSPN</th><th>SoftLearn</th><th>Data</th><th>LearnSPN</th><th>SoftLearn</th></tr></thead><tbody><tr><td>NLTCS</td><td>84.42</td><td>80.43</td><td>DNA</td><td>117.27</td><td>125.49</td></tr><tr><td>MSNBC</td><td>97.61</td><td>346.73</td><td>Kosarek</td><td>214.54</td><td>690.04</td></tr><tr><td>KDD-2k</td><td>282.22</td><td>908.71</td><td>MSWeb</td><td>254.99</td><td>1267.11</td></tr><tr><td>Plants</td><td>122.15</td><td>174.28</td><td>Book</td><td>1542.46</td><td>1067.42</td></tr><tr><td>Audio</td><td>134.04</td><td>168.94</td><td>E MOVIE</td><td>163.16</td><td>774.38</td></tr><tr><td>Jester</td><td>100.08</td><td>134.35</td><td>WebKB</td><td>361.85</td><td>1480.80</td></tr><tr><td>Netflix</td><td>130.03</td><td>179.28</td><td>Reut.52</td><td>524.73</td><td>4769.28</td></tr><tr><td>Accid.</td><td>125.29</td><td>412.04</td><td>20ng</td><td>1724.41</td><td>11770.24</td></tr><tr><td>Retail</td><td>176.19</td><td>268.14</td><td>BBC</td><td>419.26</td><td>513.10</td></tr><tr><td>Pumsb.</td><td>129.73</td><td>124.89</td><td>Ad</td><td>364.82</td><td>333.84</td></tr></tbody></table>
throughout the structure, and forces every module to process all the data points, albeit with varying weights (i.e. SoftLearn is not optimized around being faster). Practically, this can be alleviated by discarding the instances that have low membership, which is why we chose a threshold of 0.01 (membership score) to cut off practically irrelevant instances and speed up the learning process. However, even this practical trick cannot make SoftLearn comparable to LearnSPN. Table D.14 outlines the average execution times of SoftLearn compared to LearnSPN on binary datasets. SoftLearn only manages to achieve better execution time on 4 out of 20 datasets (2 of which with less than a 5% margin, and one with less than a 10% margin), which clearly indicates the superior performance of LearnSPN in execution time.

## Appendix E. Missing values

Tables in this section provide more details on the results of the evaluation of the approaches under scenarios with missing data, as explained in the main body of this paper.

<table><caption>**Table E.15**
Performance of SoftLearn on binary datasets with 10% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-5.993</b> ± 0.007</td><td>0.01</td><td>10<sup>-6</sup></td><td>-6.029 ± 0.003</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.107</b> ± 0.007</td><td>0.01</td><td>0.01</td><td>-6.165 ± 0.003</td><td>0.01</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.345</b> ± 0.004</td><td>0.001</td><td>0.1</td><td>-2.441 ± 0.005</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Plants</td><td><b>-12.773</b> ± 0.019</td><td>0.01</td><td>0.1</td><td>-13.094 ± 0.012</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><b>-39.787</b> ± 0.014</td><td>0.01</td><td>0.1</td><td>-40.973 ± 0.008</td><td>0.01</td><td>0.01</td></tr><tr><td>Jester</td><td><b>-53.163</b> ± 0.024</td><td>0.01</td><td>0.01</td><td>-53.945 ± 0.042</td><td>0.01</td><td>0.01</td></tr><tr><td>Netflix</td><td><b>-56.651</b> ± 0.022</td><td>0.01</td><td>0.01</td><td>-58.259 ± 0.057</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td>-31.866 ± 0.458</td><td>0.0001</td><td>0.1</td><td><b>-30.746</b> ± 0.033</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Retail</td><td><b>-11.172</b> ± 0.075</td><td>0.0001</td><td>0.1</td><td>-11.305 ± 0.012</td><td>0.01</td><td>0.01</td></tr><tr><td>Pumsb-star</td><td><b>-26.221</b> ± 0.409</td><td>0.0001</td><td>0.1</td><td>-29.425 ± 0.410</td><td>0.0001</td><td>0.01</td></tr><tr><td>DNA</td><td>-84.054 ± 0.280</td><td>0.0001</td><td>10<sup>-6</sup></td><td><b>-83.345</b> ± 0.052</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.110</b> ± 0.031</td><td>0.0001</td><td>0.1</td><td>-11.181 ± 0.021</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>MSWeb</td><td><b>-9.911</b> ± 0.023</td><td>0.0001</td><td>0.1</td><td>-10.082 ± 0.026</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Book</td><td>-34.384 ± 0.070</td><td>0.0001</td><td>0.1</td><td><b>-34.290</b> ± 0.052</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td>-57.977 ± 0.213</td><td>0.0001</td><td>0.1</td><td><b>-57.492</b> ± 0.085</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>WebKB</td><td>-164.829 ± 0.877</td><td>0.001</td><td>0.1</td><td><b>-163.518</b> ± 0.518</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Reuters-52</td><td><b>-90.830</b> ± 0.603</td><td>0.001</td><td>0.1</td><td>-94.491 ± 0.494</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>20 Newsgrp.</td><td><b>-121.236</b> ± 0.228</td><td>0.001</td><td>0.1</td><td>-124.775 ± 0.043</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>BBC</td><td><b>-251.233</b> ± 1.195</td><td>0.0001</td><td>0.1</td><td>-257.752 ± 0.196</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Ad</td><td><b>-21.184</b> ± 0.417</td><td>0.01</td><td>0.01</td><td>-52.249 ± 1.010</td><td>0.01</td><td>10<sup>-6</sup></td></tr></tbody></table>

<table><caption>**Table E.16**
Performance of LearnSPN on binary datasets with 10% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.019</b> ± 0.004</td><td>0.01</td><td>0.1</td><td>-6.053 ± 0.024</td><td>0.001</td><td>0.01</td></tr><tr><td>MSNBC</td><td><b>-6.107</b> ± 0.004</td><td>0.001</td><td>0.01</td><td>-6.134 ± 0.007</td><td>0.0001</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.357</b> ± 0.003</td><td>0.0001</td><td>0.1</td><td>-2.558 ± 0.082</td><td>0.01</td><td>0.1</td></tr><tr><td>Plants</td><td><b>-13.147</b> ± 0.027</td><td>0.01</td><td>0.1</td><td>-13.196 ± 0.031</td><td>0.01</td><td>0.1</td></tr><tr><td>Audio</td><td><b>-40.017</b> ± 0.049</td><td>0.001</td><td>0.1</td><td>-40.131 ± 0.071</td><td>0.001</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-53.437</b> ± 0.034</td><td>0.001</td><td>0.01</td><td>-53.460 ± 0.041</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td>-57.063 ± 0.038</td><td>0.001</td><td>0.1</td><td><b>-57.055</b> ± 0.013</td><td>0.001</td><td>0.1</td></tr><tr><td>Accidents</td><td><b>-31.241</b> ± 0.253</td><td>0.0001</td><td>0.1</td><td>-32.352 ± 0.224</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.239</b> ± 0.047</td><td>0.0001</td><td>0.1</td><td>-11.379 ± 0.019</td><td>0.0001</td><td>0.1</td></tr><tr><td>Pumsb-star</td><td><b>-26.968</b> ± 0.307</td><td>0.0001</td><td>0.1</td><td>-27.231 ± 0.347</td><td>0.0001</td><td>0.1</td></tr><tr><td>DNA</td><td>-84.496 ± 0.256</td><td>0.0001</td><td>0.1</td><td><b>-84.129</b> ± 0.419</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.373</b> ± 0.039</td><td>0.0001</td><td>0.1</td><td>-11.630 ± 0.032</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td><b>-10.250</b> ± 0.010</td><td>0.01</td><td>0.1</td><td>-10.457 ± 0.018</td><td>0.01</td><td>0.1</td></tr><tr><td>Book</td><td><b>-36.015</b> ± 0.208</td><td>0.0001</td><td>0.1</td><td>-36.213 ± 0.135</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td><b>-60.857</b> ± 0.110</td><td>0.0001</td><td>0.1</td><td>-61.326 ± 0.135</td><td>0.0001</td><td>0.1</td></tr><tr><td>WebKB</td><td>-176.398 ± 0.365</td><td>0.0001</td><td>0.1</td><td><b>-175.991</b> ± 0.819</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-96.615</b> ± 0.317</td><td>0.0001</td><td>0.1</td><td>-96.826 ± 0.276</td><td>0.0001</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td>-133.617 ± 0.364</td><td>0.0001</td><td>0.1</td><td><b>-132.352</b> ± 0.339</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td>-272.439 ± 1.380</td><td>0.0001</td><td>0.1</td><td><b>-270.534</b> ± 1.260</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-20.556</b> ± 0.215</td><td>0.01</td><td>0.1</td><td>-21.209 ± 0.153</td><td>0.01</td><td>0.1</td></tr></tbody></table>
<table><caption>**Table E.17**
Performance of SoftLearn on binary datasets with 20% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.008</b> ± 0.003</td><td>0.01</td><td>10<sup>-6</sup></td><td>-6.087 ± 0.005</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.156</b> ± 0.007</td><td>0.01</td><td>10<sup>-6</sup></td><td>-6.244 ± 0.001</td><td>0.01</td><td>0.1</td></tr><tr><td>KDDCup2k</td><td><b>-2.352</b> ± 0.001</td><td>0.001</td><td>0.1</td><td>-2.581 ± 0.012</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Plants</td><td><b>-12.914</b> ± 0.026</td><td>0.001</td><td>0.1</td><td>-13.625 ± 0.025</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><b>-39.938</b> ± 0.040</td><td>0.01</td><td>0.1</td><td>-41.447 ± 0.032</td><td>0.01</td><td>0.01</td></tr><tr><td>Jester</td><td><b>-53.305</b> ± 0.039</td><td>0.01</td><td>0.1</td><td>-54.174 ± 0.079</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td><b>-56.859</b> ± 0.019</td><td>0.01</td><td>0.1</td><td>-58.525 ± 0.026</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td>-33.075 ± 0.675</td><td>0.0001</td><td>0.1</td><td><b>-31.565</b> ± 0.431</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Retail</td><td><b>-11.141</b> ± 0.106</td><td>0.0001</td><td>0.1</td><td>-11.777 ± 0.133</td><td>0.0001</td><td>0.01</td></tr><tr><td>Pumsb-star</td><td><b>-27.399</b> ± 0.722</td><td>0.0001</td><td>0.1</td><td>-30.611 ± 0.138</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>DNA</td><td>-85.019 ± 0.177</td><td>0.0001</td><td>0.01</td><td><b>-84.232</b> ± 0.091</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.212</b> ± 0.064</td><td>0.0001</td><td>0.1</td><td>-11.567 ± 0.029</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>MSWeb</td><td><b>-10.042</b> ± 0.021</td><td>0.001</td><td>0.1</td><td>-10.623 ± 0.033</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Book</td><td><b>-34.884</b> ± 0.109</td><td>0.0001</td><td>0.1</td><td>-35.353 ± 0.125</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td><b>-58.556</b> ± 0.147</td><td>0.0001</td><td>0.1</td><td>-58.763 ± 0.051</td><td>0.0001</td><td>0.01</td></tr><tr><td>WebKB</td><td><b>-166.428</b> ± 0.900</td><td>0.0001</td><td>0.1</td><td>-168.751 ± 0.916</td><td>0.01</td><td>0.01</td></tr><tr><td>Reuters-52</td><td><b>-91.189</b> ± 0.206</td><td>0.0001</td><td>0.1</td><td>-98.750 ± 0.746</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>20 Newsgrp.</td><td><b>-122.590</b> ± 0.345</td><td>0.0001</td><td>0.1</td><td>-127.585 ± 0.108</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>BBC</td><td>-255.223 ± 1.273</td><td>0.0001</td><td>0.1</td><td>-260.844 ± 0.571</td><td>0.01</td><td>0.01</td></tr><tr><td>Ad</td><td><b>-20.660</b> ± 0.338</td><td>0.01</td><td>0.1</td><td>-58.263 ± 2.451</td><td>0.001</td><td>10<sup>-6</sup></td></tr></tbody></table>

<table><caption>**Table E.18**
Performance of LearnSPN on binary datasets with 20% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.0737</b> ± 0.004</td><td>0.01</td><td>0.1</td><td>-6.159 ± 0.017</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.213</b> ± 0.016</td><td>0.01</td><td>0.1</td><td>-6.312 ± 0.014</td><td>0.0001</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.375</b> ± 0.004</td><td>0.0001</td><td>0.1</td><td>-2.758 ± 0.146</td><td>0.001</td><td>0.1</td></tr><tr><td>Plants</td><td><b>-13.427</b> ± 0.036</td><td>0.01</td><td>0.1</td><td>-13.582 ± 0.030</td><td>0.01</td><td>0.1</td></tr><tr><td>Audio</td><td><b>-40.353</b> ± 0.022</td><td>0.001</td><td>0.1</td><td>-40.528 ± 0.045</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Jester</td><td>-53.763 ± 0.014</td><td>0.001</td><td>0.1</td><td><b>-53.751</b> ± 0.037</td><td>0.001</td><td>0.01</td></tr><tr><td>Netflix</td><td><b>-57.365</b> ± 0.014</td><td>0.001</td><td>0.01</td><td>-57.409 ± 0.043</td><td>0.001</td><td>0.01</td></tr><tr><td>Accidents</td><td><b>-34.529</b> ± 0.234</td><td>0.0001</td><td>0.1</td><td>-35.402 ± 0.205</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.318</b> ± 0.161</td><td>0.0001</td><td>0.1</td><td>-12.020 ± 0.119</td><td>0.0001</td><td>0.1</td></tr><tr><td>Pumsb-star</td><td><b>-29.628</b> ± 0.322</td><td>0.0001</td><td>0.1</td><td>-30.669 ± 0.209</td><td>0.0001</td><td>0.1</td></tr><tr><td>DNA</td><td>-85.956 ± 0.454</td><td>0.0001</td><td>0.1</td><td><b>-85.591</b> ± 0.573</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.598</b> ± 0.031</td><td>0.0001</td><td>0.1</td><td>-12.028 ± 0.152</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td><b>-10.483</b> ± 0.053</td><td>0.0001</td><td>0.1</td><td>-10.800 ± 0.038</td><td>0.01</td><td>0.1</td></tr><tr><td>Book</td><td><b>-36.898</b> ± 0.233</td><td>0.0001</td><td>0.1</td><td>-37.178 ± 0.275</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td><b>-62.478</b> ± 0.144</td><td>0.0001</td><td>0.1</td><td>-63.022 ± 0.102</td><td>0.001</td><td>0.1</td></tr><tr><td>WebKB</td><td><b>-180.047</b> ± 0.772</td><td>0.0001</td><td>0.1</td><td>-180.365 ± 0.634</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-98.308</b> ± 0.347</td><td>0.0001</td><td>0.1</td><td>-98.664 ± 0.239</td><td>0.0001</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td>-135.456 ± 0.275</td><td>0.0001</td><td>0.1</td><td><b>-134.831</b> ± 0.331</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td>-277.749 ± 0.957</td><td>0.0001</td><td>0.1</td><td><b>-277.052</b> ± 1.020</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-21.900</b> ± 0.195</td><td>0.01</td><td>0.1</td><td>-22.569 ± 0.063</td><td>0.01</td><td>0.1</td></tr></tbody></table>

<table><caption>**Table E.19**
Performance of SoftLearn on binary datasets with 30% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.038</b> ± 0.010</td><td>0.01</td><td>0.1</td><td>-6.146 ± 0.007</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSNBC</td><td><b>-6.216</b> ± 0.013</td><td>0.01</td><td>0.01</td><td>-6.309 ± 0.005</td><td>0.01</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.368</b> ± 0.001</td><td>0.001</td><td>0.1</td><td>-2.533 ± 0.014</td><td>0.0001</td><td>0.01</td></tr><tr><td>Plants</td><td><b>-13.052</b> ± 0.026</td><td>0.01</td><td>0.1</td><td>-14.151 ± 0.016</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><b>-40.135</b> ± 0.043</td><td>0.01</td><td>0.1</td><td>-41.934 ± 0.029</td><td>0.01</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-53.520</b> ± 0.034</td><td>0.01</td><td>0.1</td><td>-54.432 ± 0.051</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td><b>-57.094</b> ± 0.029</td><td>0.01</td><td>10<sup>-6</sup></td><td>-59.208 ± 0.027</td><td>0.01</td><td>0.01</td></tr><tr><td>Accidents</td><td>-34.219 ± 0.0419</td><td>0.0001</td><td>0.1</td><td><b>-32.677</b> ± 0.216</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Retail</td><td><b>-11.160</b> ± 0.044</td><td>0.0001</td><td>0.1</td><td>-12.137 ± 0.0254</td><td>0.0001</td><td>0.01</td></tr></tbody></table>

(continued on next page)
<table><caption>Table E.19 (continued)</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>Pumsb-star</td><td><b>-28.638</b> ± 0.446</td><td>0.0001</td><td>0.1</td><td>-31.322 ± 0.596</td><td>0.0001</td><td>0.01</td></tr><tr><td>DNA</td><td>-86.184 ± 0.422</td><td>0.0001</td><td>0.1</td><td><b>-85.755</b> ± 0.131</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.329</b> ± 0.016</td><td>0.0001</td><td>0.1</td><td>-11.839 ± 0.021</td><td>0.01</td><td>0.01</td></tr><tr><td>MSWeb</td><td><b>-10.133</b> ± 0.032</td><td>0.01</td><td>0.1</td><td>-11.017 ± 0.020</td><td>0.01</td><td>0.01</td></tr><tr><td>Book</td><td><b>-35.240</b> ± 0.097</td><td>0.0001</td><td>0.1</td><td>-35.711 ± 0.121</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td><b>-59.491</b> ± 0.214</td><td>0.0001</td><td>0.1</td><td>-59.775 ± 0.071</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>WebKB</td><td><b>-169.176</b> ± 1.324</td><td>0.0001</td><td>0.1</td><td>-173.036 ± 0.967</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Reuters-52</td><td><b>-93.643</b> ± 0.512</td><td>0.0001</td><td>0.1</td><td>-101.432 ± 1.286</td><td>0.01</td><td>0.01</td></tr><tr><td>20 Newsgrp.</td><td><b>-124.028</b> ± 0.387</td><td>0.0001</td><td>0.1</td><td>-131.665 ± 0.081</td><td>0.01</td><td>0.1</td></tr><tr><td>BBC</td><td><b>-259.028</b> ± 2.481</td><td>0.0001</td><td>0.1</td><td>-263.506 ± 0.255</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-22.672</b> ± 0.224</td><td>0.01</td><td>0.1</td><td>-67.785 ± 1.586</td><td>0.001</td><td>10<sup>-6</sup></td></tr></tbody></table>

<table><caption>Table E.20
Performance of LearnSPN on binary datasets with 30% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.167</b> ± 0.006</td><td>0.001</td><td>0.1</td><td>-6.333 ± 0.061</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.359</b> ± 0.013</td><td>0.0001</td><td>0.1</td><td>-6.609 ± 0.024</td><td>0.0001</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.399</b> ± 0.004</td><td>0.0001</td><td>0.1</td><td>-2.819 ± 0.139</td><td>0.0001</td><td>0.1</td></tr><tr><td>Plants</td><td><b>-13.789</b> ± 0.048</td><td>0.001</td><td>0.1</td><td>-13.995 ± 0.040</td><td>0.001</td><td>0.1</td></tr><tr><td>Audio</td><td><b>-40.661</b> ± 0.019</td><td>0.0001</td><td>0.01</td><td>-40.987 ± 0.046</td><td>0.0001</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-54.172</b> ± 0.059</td><td>0.001</td><td>0.1</td><td>-54.291 ± 0.040</td><td>0.0001</td><td>0.1</td></tr><tr><td>Netflix</td><td><b>-57.791</b> ± 0.055</td><td>0.001</td><td>0.1</td><td>-57.918 ± 0.067</td><td>0.001</td><td>0.01</td></tr><tr><td>Accidents</td><td><b>-36.656</b> ± 0.487</td><td>0.0001</td><td>0.1</td><td>-37.259 ± 0.302</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.531</b> ± 0.209</td><td>0.0001</td><td>0.1</td><td>-12.577 ± 0.104</td><td>0.001</td><td>0.1</td></tr><tr><td>Pumsb-star</td><td><b>-31.636</b> ± 0.249</td><td>0.0001</td><td>0.1</td><td>-32.261 ± 0.252</td><td>0.0001</td><td>0.1</td></tr><tr><td>DNA</td><td><b>-88.336</b> ± 0.996</td><td>0.0001</td><td>10<sup>-6</sup></td><td>-88.546 ± 0.485</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Kosarek</td><td><b>-11.797</b> ± 0.085</td><td>0.0001</td><td>0.1</td><td>-12.462 ± 0.048</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td><b>-10.733</b> ± 0.045</td><td>0.001</td><td>0.1</td><td>-11.221 ± 0.090</td><td>0.001</td><td>0.1</td></tr><tr><td>Book</td><td><b>-37.595</b> ± 0.250</td><td>0.0001</td><td>0.1</td><td>-38.046 ± 0.301</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td><b>-63.108</b> ± 0.149</td><td>0.01</td><td>0.1</td><td>-64.005 ± 0.118</td><td>0.001</td><td>0.1</td></tr><tr><td>WebKB</td><td><b>-182.516</b> ± 0.318</td><td>0.0001</td><td>0.1</td><td><b>-182.498</b> ± 0.660</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-99.872</b> ± 0.206</td><td>0.0001</td><td>0.1</td><td>-100.586 ± 0.371</td><td>0.0001</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td><b>-137.185</b> ± 0.175</td><td>0.0001</td><td>0.1</td><td><b>-136.353</b> ± 0.200</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td><b>-281.255</b> ± 0.751</td><td>0.0001</td><td>0.1</td><td><b>-279.090</b> ± 1.772</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-23.418</b> ± 0.211</td><td>0.001</td><td>0.1</td><td>-24.615 ± 0.444</td><td>0.01</td><td>0.1</td></tr></tbody></table>

<table><caption>Table E.21
Performance of SoftLearn on binary datasets with 40% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.101</b> ± 0.007</td><td>0.01</td><td>0.1</td><td>-6.202 ± 0.023</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSNBC</td><td><b>-6.312</b> ± 0.014</td><td>0.01</td><td>10<sup>-6</sup></td><td>-6.375 ± 0.003</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>KDDCup2k</td><td><b>-2.393</b> ± 0.003</td><td>0.001</td><td>0.1</td><td>-2.529 ± 0.018</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Plants</td><td><b>-13.244</b> ± 0.035</td><td>0.01</td><td>0.1</td><td>-14.868 ± 0.028</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><b>-40.415</b> ± 0.031</td><td>0.01</td><td>0.1</td><td>-42.531 ± 0.102</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Jester</td><td><b>-53.851</b> ± 0.052</td><td>0.01</td><td>0.1</td><td>-55.072 ± 0.031</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td><b>-57.443</b> ± 0.021</td><td>0.01</td><td>0.1</td><td>-60.430 ± 0.034</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td><b>-34.880</b> ± 0.475</td><td>0.0001</td><td>0.1</td><td><b>-34.699</b> ± 0.111</td><td>0.001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.230</b> ± 0.068</td><td>0.0001</td><td>0.1</td><td>-12.434 ± 0.144</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Pumsb-star</td><td><b>-29.636</b> ± 0.130</td><td>0.0001</td><td>0.1</td><td>-32.378 ± 0.158</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>DNA</td><td><b>-88.109</b> ± 0.401</td><td>0.0001</td><td>0.01</td><td><b>-87.417</b> ± 0.227</td><td>0.001</td><td>0.01</td></tr><tr><td>Kosarek</td><td><b>-11.426</b> ± 0.042</td><td>0.0001</td><td>0.1</td><td>-12.187 ± 0.053</td><td>0.01</td><td>0.01</td></tr><tr><td>MSWeb</td><td><b>-10.331</b> ± 0.011</td><td>0.01</td><td>0.1</td><td>-11.124 ± 0.008</td><td>0.001</td><td>0.01</td></tr><tr><td>Book</td><td><b>-35.846</b> ± 0.147</td><td>0.0001</td><td>0.1</td><td><b>-35.710</b> ± 0.224</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td><b>-60.256</b> ± 0.277</td><td>0.0001</td><td>0.1</td><td>-60.845 ± 0.155</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>WebKB</td><td><b>-173.026</b> ± 1.331</td><td>0.0001</td><td>0.1</td><td>-175.958 ± 1.261</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Reuters-52</td><td><b>-95.484</b> ± 0.377</td><td>0.0001</td><td>0.1</td><td>-106.005 ± 3.311</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>20 Newsgrp.</td><td><b>-126.105</b> ± 0.274</td><td>0.0001</td><td>0.1</td><td>-135.041 ± 0.216</td><td>0.01</td><td>0.1</td></tr><tr><td>BBC</td><td><b>-262.663</b> ± 1.429</td><td>0.0001</td><td>0.1</td><td>-265.926 ± 0.238</td><td>0.0001</td><td>0.01</td></tr><tr><td>Ad</td><td><b>-24.718</b> ± 0.569</td><td>0.01</td><td>0.1</td><td>-68.749 ± 0.050</td><td>0.0001</td><td>0.01</td></tr></tbody></table>
<table><caption>**Table E.22**
Performance of LearnSPN on binary datasets with 40% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.289</b> ± 0.020</td><td>0.0001</td><td>0.1</td><td>-6.584 ± 0.062</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.546</b> ± 0.0165</td><td>0.001</td><td>0.1</td><td>-7.004 ± 0.111</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>KDDCup2k</td><td><b>-2.442</b> ± 0.004</td><td>0.0001</td><td>0.1</td><td>-3.325 ± 0.192</td><td>0.01</td><td>0.01</td></tr><tr><td>Plants</td><td><b>-14.238</b> ± 0.040</td><td>0.001</td><td>0.1</td><td>-14.507 ± 0.045</td><td>0.0001</td><td>0.1</td></tr><tr><td>Audio</td><td><b>-41.089</b> ± 0.019</td><td>0.0001</td><td>10<sup>-6</sup></td><td>-41.576 ± 0.104</td><td>0.0001</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-54.722</b> ± 0.114</td><td>0.0001</td><td>0.1</td><td>-54.846 ± 0.131</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td><b>-58.399</b> ± 0.052</td><td>0.001</td><td>0.1</td><td>-58.579 ± 0.078</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td><b>-38.803</b> ± 0.166</td><td>0.0001</td><td>0.1</td><td><b>-38.806</b> ± 0.168</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.718</b> ± 0.090</td><td>0.0001</td><td>0.1</td><td>-13.309 ± 0.070</td><td>0.01</td><td>0.1</td></tr><tr><td>Pumsb-star</td><td><b>-33.095</b> ± 0.209</td><td>0.0001</td><td>0.1</td><td>-33.566 ± 0.117</td><td>0.001</td><td>0.1</td></tr><tr><td>DNA</td><td><b>-91.936</b> ± 1.256</td><td>0.0001</td><td>10<sup>-6</sup></td><td>-92.862 ± 1.016</td><td>0.0001</td><td>0.1</td></tr><tr><td>Kosarek</td><td><b>-12.171</b> ± 0.145</td><td>0.0001</td><td>0.1</td><td>-13.018 ± 0.248</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td><b>-11.180</b> ± 0.085</td><td>0.001</td><td>0.1</td><td>-11.808 ± 0.050</td><td>0.0001</td><td>0.1</td></tr><tr><td>Book</td><td><b>-38.046</b> ± 0.253</td><td>0.0001</td><td>0.1</td><td>-39.039 ± 0.166</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td><b>-64.071</b> ± 0.089</td><td>0.001</td><td>0.1</td><td>-64.728 ± 0.217</td><td>0.01</td><td>0.1</td></tr><tr><td>WebKB</td><td><b>-184.290</b> ± 0.484</td><td>0.0001</td><td>0.1</td><td>-185.262 ± 0.293</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-101.655</b> ± 0.185</td><td>0.0001</td><td>0.1</td><td>-102.456 ± 0.151</td><td>0.001</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td>-138.226 ± 0.114</td><td>0.0001</td><td>0.1</td><td><b>-137.917</b> ± 0.161</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td>-284.280 ± 1.458</td><td>0.0001</td><td>0.1</td><td><b>-283.070</b> ± 0.635</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-25.799</b> ± 0.340</td><td>0.01</td><td>0.1</td><td>-27.818 ± 0.883</td><td>0.0001</td><td>0.1</td></tr></tbody></table>

<table><caption>**Table E.23**
Performance of SoftLearn on binary datasets with 50% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">SoftLearn/EM</th><th colspan="3">SoftLearn/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.221</b> ± 0.025</td><td>0.001</td><td>10<sup>-6</sup></td><td>-6.313 ± 0.008</td><td>0.0001</td><td>0.01</td></tr><tr><td>MSNBC</td><td>-6.446 ± 0.032</td><td>0.001</td><td>0.01</td><td><b>-6.440</b> ± 0.009</td><td>0.01</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.469</b> ± 0.011</td><td>0.0001</td><td>0.1</td><td>-2.536 ± 0.004</td><td>0.0001</td><td>0.01</td></tr><tr><td>Plants</td><td><b>-13.566</b> ± 0.038</td><td>0.01</td><td>0.1</td><td>-15.735 ± 0.020</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Audio</td><td><b>-40.766</b> ± 0.058</td><td>0.01</td><td>0.1</td><td>-43.302 ± 0.158</td><td>0.01</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-54.306</b> ± 0.078</td><td>0.01</td><td>0.1</td><td>-55.903 ± 0.051</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Netflix</td><td><b>-57.908</b> ± 0.034</td><td>0.01</td><td>0.1</td><td>-60.964 ± 0.083</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td><b>-35.409</b> ± 0.264</td><td>0.0001</td><td>0.1</td><td>-36.551 ± 0.126</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-11.524</b> ± 0.127</td><td>0.0001</td><td>0.1</td><td>-12.337 ± 0.211</td><td>0.0001</td><td>0.01</td></tr><tr><td>Pumsb-star</td><td><b>-31.208</b> ± 0.170</td><td>0.0001</td><td>0.1</td><td>-33.642 ± 0.153</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>DNA</td><td>-91.582 ± 0.720</td><td>0.001</td><td>0.1</td><td><b>-89.504</b> ± 0.256</td><td>0.01</td><td>0.1</td></tr><tr><td>Kosarek</td><td><b>-11.788</b> ± 0.145</td><td>0.0001</td><td>0.1</td><td>-12.424 ± 0.060</td><td>0.001</td><td>0.01</td></tr><tr><td>MSWeb</td><td><b>-10.626</b> ± 0.056</td><td>0.0001</td><td>0.1</td><td>-11.128 ± 0.001</td><td>0.0001</td><td>0.01</td></tr><tr><td>Book</td><td>-36.613 ± 0.186</td><td>0.0001</td><td>0.1</td><td><b>-36.233</b> ± 0.192</td><td>0.01</td><td>10<sup>-6</sup></td></tr><tr><td>EachMovie</td><td><b>-61.385</b> ± 0.222</td><td>0.0001</td><td>0.1</td><td>-64.134 ± 0.105</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>WebKB</td><td><b>-176.820</b> ± 0.530</td><td>0.0001</td><td>0.1</td><td>-179.766 ± 1.532</td><td>0.01</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-97.986</b> ± 0.511</td><td>0.0001</td><td>0.1</td><td>-111.747 ± 0.550</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>20 Newsgrp.</td><td><b>-127.668</b> ± 0.275</td><td>0.0001</td><td>0.1</td><td>-138.089 ± 0.265</td><td>0.0001</td><td>0.01</td></tr><tr><td>BBC</td><td>-272.154 ± 3.820</td><td>0.0001</td><td>0.1</td><td><b>-268.141</b> ± 0.426</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-30.106</b> ± 1.484</td><td>0.01</td><td>0.1</td><td>-68.991 ± 0.037</td><td>0.001</td><td>0.01</td></tr></tbody></table>

<table><caption>**Table E.24**
Performance of LearnSPN on binary datasets with 50% missing value.</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>NLTCS</td><td><b>-6.555</b> ± 0.106</td><td>0.0001</td><td>0.1</td><td>-6.821 ± 0.140</td><td>0.0001</td><td>10<sup>-6</sup></td></tr><tr><td>MSNBC</td><td><b>-6.872</b> ± 0.035</td><td>0.001</td><td>0.1</td><td>-7.599 ± 0.087</td><td>0.0001</td><td>0.01</td></tr><tr><td>KDDCup2k</td><td><b>-2.575</b> ± 0.022</td><td>0.001</td><td>0.1</td><td>-4.142 ± 0.242</td><td>0.0001</td><td>0.01</td></tr><tr><td>Plants</td><td><b>-14.939</b> ± 0.034</td><td>0.001</td><td>0.1</td><td>-15.264 ± 0.091</td><td>0.01</td><td>0.1</td></tr><tr><td>Audio</td><td><b>-41.820</b> ± 0.178</td><td>0.0001</td><td>0.1</td><td>-42.250 ± 0.110</td><td>0.0001</td><td>0.1</td></tr><tr><td>Jester</td><td><b>-55.337</b> ± 0.172</td><td>0.001</td><td>0.01</td><td>-55.523 ± 0.078</td><td>0.001</td><td>0.1</td></tr><tr><td>Netflix</td><td><b>-59.230</b> ± 0.071</td><td>0.001</td><td>0.01</td><td>-59.441 ± 0.112</td><td>0.001</td><td>10<sup>-6</sup></td></tr><tr><td>Accidents</td><td>-40.120 ± 0.179</td><td>0.0001</td><td>0.1</td><td><b>-40.079</b> ± 0.124</td><td>0.0001</td><td>0.1</td></tr><tr><td>Retail</td><td><b>-12.292</b> ± 0.276</td><td>0.0001</td><td>0.1</td><td>-14.024 ± 0.126</td><td>0.01</td><td>0.1</td></tr></tbody></table>

(continued on next page)
<table><caption>Table E.24 (continued)</caption><thead><tr><th rowspan="2">Dataset</th><th colspan="3">LearnSPN/EM</th><th colspan="3">LearnSPN/K-means</th></tr><tr><th>Test LL</th><th>p</th><th>α</th><th>Test LL</th><th>p</th><th>α</th></tr></thead><tbody><tr><td>Pumsb-star</td><td><b>-34.129</b> ± 0.348</td><td>0.0001</td><td>0.1</td><td>-34.908 ± 0.142</td><td>0.0001</td><td>0.1</td></tr><tr><td>DNA</td><td><b>-96.694</b> ± 0.664</td><td>0.0001</td><td>0.1</td><td>-98.864 ± 0.833</td><td>0.001</td><td>0.1</td></tr><tr><td>Kosarek</td><td><b>-12.840</b> ± 0.145</td><td>0.0001</td><td>0.1</td><td>-13.982 ± 0.124</td><td>0.0001</td><td>0.1</td></tr><tr><td>MSWeb</td><td><b>-11.822</b> ± 0.023</td><td>0.01</td><td>0.1</td><td>-12.701 ± 0.091</td><td>0.0001</td><td>0.1</td></tr><tr><td>Book</td><td><b>-39.377</b> ± 0.122</td><td>0.0001</td><td>0.1</td><td>-40.405 ± 0.144</td><td>0.0001</td><td>0.1</td></tr><tr><td>EachMovie</td><td><b>-64.911</b> ± 0.208</td><td>0.01</td><td>0.1</td><td>-65.913 ± 0.254</td><td>0.01</td><td>0.1</td></tr><tr><td>WebKB</td><td><b>-186.922</b> ± 0.575</td><td>0.0001</td><td>0.1</td><td>-187.182 ± 0.368</td><td>0.0001</td><td>0.1</td></tr><tr><td>Reuters-52</td><td><b>-103.517</b> ± 0.354</td><td>0.001</td><td>0.1</td><td>-104.623 ± 0.303</td><td>0.01</td><td>0.1</td></tr><tr><td>20 Newsgrp.</td><td><b>-139.141</b> ± 0.137</td><td>0.0001</td><td>0.1</td><td>-140.361 ± 0.709</td><td>0.0001</td><td>0.1</td></tr><tr><td>BBC</td><td><b>-287.311</b> ± 1.277</td><td>0.0001</td><td>0.1</td><td>-288.070 ± 0.741</td><td>0.0001</td><td>0.1</td></tr><tr><td>Ad</td><td><b>-29.772</b> ± 0.858</td><td>0.01</td><td>0.1</td><td>-31.232 ± 0.870</td><td>0.01</td><td>0.1</td></tr></tbody></table>

## Data availability

Public data from public repositories.

## References

[1] D.P. Kingma, M. Welling, Auto-encoding variational Bayes, arXiv preprint, arXiv:1312.6114, 2013.

[2] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio, Generative adversarial networks, Commun. ACM 63 (11) (2020) 139–144.

[3] H. Poon, P. Domingos, Sum-product networks: a new deep architecture, in: 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), IEEE, 2011, pp. 689–690.

[4] R. Sánchez-Cauce, I. París, F. J. Díez, Sum-product networks: a survey, IEEE Trans. Pattern Anal. Mach. Intell. 44 (7) (2021) 3821–3839.

[5] D. Koller, N. Friedman, Probabilistic Graphical Models: Principles and Techniques, MIT Press, 2009.

[6] C.P. De Campos, New complexity results for map in Bayesian networks, in: IJCAI, vol. 11, Citeseer, 2011, pp. 2100–2106.

[7] C.P. De Campos, F.G. Cozman, The inferential complexity of Bayesian and credal networks, in: IJCAI, vol. 5, 2005, pp. 1313–1318.

[8] A. Vergari, Y. Choi, A. Liu, S. Teso, G. Van den Broeck, A compositional atlas of tractable circuit operations for probabilistic inference, in: Advances in Neural Information Processing Systems, vol. 34, 2021, pp. 13189–13201.

[9] R. Gens, P. Domingos, Learning the structure of sum-product networks, in: Proceedings of the 30th International Conference on Machine Learning, vol. 28, PMLR, 2013, pp. 873–880.

[10] A. Molina, A. Vergari, N. Di Mauro, S. Natarajan, F. Esposito, K. Kersting, Mixed sum-product networks: a deep architecture for hybrid domains, in: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32(1), 2018.

[11] T. Adel, D. Baluzzi, A. Ghodsi, Learning the structure of sum-product networks via an svd-based algorithm, in: Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, 2015, pp. 32–41.

[12] W. Hsu, A. Kalra, P. Poupart, Online structure learning for sum-product networks with Gaussian leaves, arXiv preprint, arXiv:1701.05265, 2017.

[13] A. Kalra, A. Rashwan, W.-S. Hsu, P. Poupart, P. Doshi, G. Trimonias, Online structure learning for feed-forward and recurrent sum-product networks, in: Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 6944–6954.

[14] S.-W. Lee, M.-O. Heo, B.-T. Zhang, Online incremental structure learning of sum-product networks, in: Neural Information Processing: 20th International Conference, Proceedings, Part II, ICONIP 2013, Daegu, Korea, November 3–7, 2013, vol. 20, Springer, 2013, pp. 220–227.

[15] A. Vergari, N. Di Mauro, F. Esposito, Simplifying, regularizing and strengthening sum-product network structure learning, in: Machine Learning and Knowledge Discovery in Databases: European Conference, Proceedings, Part II, ECML PKDD 2015, Porto, Portugal, September 7–11, 2015, vol. 15, Springer, 2015, pp. 343–358.

[16] M. Trapp, R. Peharz, M. Skowron, T. Madl, F. Pernkopf, R. Trappl, Structure inference in sum-product networks using infinite sum-product trees, in: NIPS Workshop on Practical Bayesian Nonparametrics, 2016.

[17] M. Trapp, R. Peharz, H. Ge, F. Pernkopf, Z. Ghahramani, Bayesian learning of sum-product networks, in: Advances in Neural Information Processing Systems, vol. 32, 2019, pp. 6347–6358.

[18] A. Vergari, A. Molina, R. Peharz, Z. Ghahramani, K. Kersting, I. Valera, Automatic Bayesian density analysis, in: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33(1), 2019, pp. 5207–5215.

[19] T. Rahman, V. Gogate, Merging strategies for sum-product networks: from trees to graphs, in: Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, 2016, pp. 617–626.

[20] Y. Liang, J. Bekker, G. Van den Broeck, Learning the structure of probabilistic sentential decision diagrams, in: Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, 2017.

[21] N. Di Mauro, A. Vergari, T.M. Basile, F. Esposito, Fast and accurate density estimation with extremely randomized cutset networks, in: Machine Learning and Knowledge Discovery in Databases: European Conference, Proceedings, Part I, ECML PKDD 2017, Skopje, Macedonia, September 18–22, 2017, vol. 10, Springer, 2017, pp. 203–219.

[22] T. Rahman, S. Jin, V. Gogate, Look ma, no latent variables: accurate cutset networks via compilation, in: Proceedings of the 36th International Conference on Machine Learning, vol. 97, PMLR, 2019, pp. 5311–5320.

[23] S. Ghandi, B. Quost, C. de Campos, Soft learning probabilistic circuits, in: Proceedings of the 12th International Conference on Probabilistic Graphical Models, PMLR, 2024, pp. 273–294.

[24] A. Darwiche, A differential approach to inference in Bayesian networks, in: C. Boutilier, M. Goldszmidt (Eds.), Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2000, pp. 123–132.

[25] C. Boutilier, N. Friedman, M. Goldszmidt, D. Koller, Context-specific independence in Bayesian networks, arXiv preprint, arXiv:1302.3562, 2013.

[26] R. Peharz, R. Gens, F. Pernkopf, P. Domingos, On the latent variable interpretation in sum-product networks, IEEE Trans. Pattern Anal. Mach. Intell. 39 (10) (2017) 2030–2044, https://doi.org/10.1109/TPAMI.2016.2618381.

[27] R. Peharz, S. Tschiatschek, F. Pernkopf, P. Domingos, On theoretical properties of sum-product networks, in: Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, vol. 38, PMLR, 2015, pp. 744–752.
[28] A. Correia, R. Peharz, C.P. de Campos, Joints in random forests, in: Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 11404–11415.

[29] D. Lowd, J. Davis, Learning Markov network structure with decision trees, in: 2010 IEEE International Conference on Data Mining, IEEE, 2010, pp. 334–343.

[30] J. Van Haaren, J. Davis, Markov network structure learning: a randomized feature generation approach, in: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 26, 2012, pp. 1148–1154.

[31] T. Rahman, P. Kothalkar, V. Gogate, Cutset networks: a simple, tractable, and scalable approach for improving the accuracy of Chow-Liu trees, in: Machine Learning and Knowledge Discovery in Databases: European Conference, Proceedings, Part II, ECML PKDD 2014, Nancy, France, September 15–19, 2014, vol. 14, Springer, 2014, pp. 630–645.

[32] J. Vanschoren, J.N. Van Rijn, B. Bischl, L. Torgo, Openml: networked science in machine learning, ACM SIGKDD Explor. Newsl. 15 (2) (2014) 49–60.

[33] H. Larochelle, I. Murray, The neural autoregressive distribution estimator, in: Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, vol. 15, PMLR, 2011, pp. 29–37.

[34] R. Fakoor, P. Chaudhari, J. Mueller, A.J. Smola, Trade: transformers for density estimation, arXiv preprint, arXiv:2004.02441, 2020.

[35] A. Liu, G. Van den Broeck, Tractable regularization of probabilistic circuits, in: Advances in Neural Information Processing Systems, vol. 34, Curran Associates, Inc., 2021, pp. 3558–3570.

[36] R. Peharz, S. Lang, A. Vergari, K. Stelzner, A. Molina, M. Trapp, G. Van Den Broeck, K. Kersting, Z. Ghahramani, Einsum networks: fast and scalable learning of tractable probabilistic circuits, in: Proceedings of the 37th International Conference on Machine Learning, vol. 119, PMLR, 2020, pp. 7563–7574.

[37] R. Peharz, A. Vergari, K. Stelzner, A. Molina, X. Shao, M. Trapp, K. Kersting, Z. Ghahramani, Random sum-product networks: a simple and effective approach to probabilistic deep learning, in: Proceedings of the 35th Uncertainty in Artificial Intelligence Conference, vol. 115, PMLR, 2020, pp. 334–344.

[38] A. Rooshenas, D. Lowd, Learning sum-product networks with direct and indirect variable interactions, in: Proceedings of the 31st International Conference on Machine Learning, vol. 32, PMLR, 2014, pp. 710–718.