Learning Weighted Model Integration Distributions

Weighted model integration (WMI) is a framework for prob- abilistic inference over distributions with discrete and continuous variables and structured supports. Despite the grow- ing popularity of WMI, existing density estimators ignore the problem of learning a structured support, and thus fail to han- dle unfeasible conﬁgurations and piecewise-linear relations between continuous variables. We propose LARIAT , a novel method to tackle this challenging problem. In a ﬁrst step, our approach induces an SMT( LRA ) formula representing the support of the structured distribution. Next, it combines the latter with a density learned using a state-of-the-art estimation method. The overall model automatically accounts for the discontinuous nature of the underlying structured distribution. Our experimental results with synthetic and real-world data highlight the promise of the approach.


Introduction
Weighted model integration (WMI) is a recent framework for probabilistic inference in hybrid domains, that is, domains with both discrete and continuous variables. A key feature of WMI is that it enables reasoning with highly structured distributions that include arbitrary combinations of logical and linear constraints. As previously recognized in work on discrete structured distributions (e.g. (Liang, Bekker, and Van den Broeck 2017)), these arise in important real-world applications because of, e.g., physical and mechanical limitations (Afshar, Sanner, and Webers 2016) or safety requirements (Amodei et al. 2016).
Despite their relevance, learning these WMI distributions (formally defined in the Background) from data has not been considered so far. Indeed, density estimators for hybrid domains entirely ignore the problem of identifying and learning the support of the distribution. Stateof-the-art approaches like Mixed Sum-Product Networks (MSPNs) (Molina et al. 2018) and Density Estimation Trees (DETs) (Ram and Gray 2011) can only model boundingbox constraints over individual variables, and do not admit oblique supports, which are necessary to capture linear interactions between continuous quantities. Failing to account for the support can lead to substantial inaccuracies in density estimation, especially for high-density regions lying at the border of the support. Most importantly, acquiring a faithful support estimate is necessary to guarantee that invalid or harmful configurations cannot be generated, a crucial feature in safety-critical applications, e.g., reliable machine learning and safe AI (Amodei et al. 2016).
Inspired by work on learning discrete structured distributions (Liang, Bekker, and Van den Broeck 2017), we contribute LARIAT (LeARning to IntegrATe), a novel approach for learning WMI distributions from data. Our approach breaks the learning problem into two steps. In a first step, a (non-trivial) support is learned from the data. This is accomplished by a novel extension of the approach of (Kolb et al. 2018b) for learning satisfiability modulo linear real arithmetic formulas (Barrett et al. 2009). Our generalization extends the original approach to learning from positive-only data, and inherits the ability to natively acquire oblique and non-convex constraints. In a second step, a candidate density is obtained by employing a state-of-the-art non-parametric estimator, e.g., a DET or an MSPN. Finally, INCAL automatically adjusts (normalizes) the learned density to be consistent with the learned support, thus allocating zero mass to infeasible configurations while guaranteeing that the resulting model is a valid WMI distribution.
Summarizing, our main contributions are: (1) INCAL+, an extension of the SMT(LRA) learning algorithm of (Kolb et al. 2018b) to support learning; (2) LARIAT, a method to estimate WMI distributions that combines structured supports (either learned by INCAL+ or provided by a domain expert) and state-of-the-art density estimators, e.g., DETs and MSPNs; (3) Extensive experiments showing the advantages of LARIAT over standard density estimators in cases where the underlying distribution has a non-trivial support.

Related Work
Non-parametric multivariate density estimation is a venerable field of study. Textbook approaches include histograms (Fix and Hodges Jr 1951) and kernel density estimation (Gray and Moore 2003). Histograms partition the space into regularly sized bins, each associated to a constant density. Adaptive histograms fit a local regressor (e.g., a spline) at each bin to capture the finer details while allowing the bin size to grow adaptively (Jing, Koch, and Naito 2012). Kernel density estimation (KDE) fits a local density around each datapoint. The runtime of these methods grows quickly with the number of dimensions and/or datapoints. Multivariate adaptive regression splines (MARS) (Friedman 1991) is another classical, greedy space-partitioning model (with polynomial leaves) that tends to be more efficient than histograms and KDE.
Recently, more efficient tree-and grid-based approaches have been introduced. Tree-based methods (Li, Yang, and Wong 2016;Meyer 2018) such as Density Estimation Trees (DETs) (Ram and Gray 2011) achieve considerable scalability by recursively partitioning the space based on axisaligned splits. The splits are obtained in an adaptive manner by greedily optimizing the integrated square error. Notably, DETs support hybrid domains. Grid-based methods (Peherstorfer, Pflüge, and Bungartz 2014) recursively partition the space too, but they place the splits at fixed, progressively finer-grained locations.
In the discrete case, learning of structured distributions has been explored for probabilistic sentential decision diagrams (Kisa et al. 2014) from both examples and prespecified constraints (Liang, Bekker, and Van den Broeck 2017). These techniques, however, have not been extended to hybrid domains. On the other hand, MSPNs (Molina et al. 2018;) are state-of-the-art density estimators that extend Sum-Product Networks (Poon and Domingos 2011;Darwiche 2009;Vergari, Di Mauro, and Esposito 2019) by introducing continuous variables and polynomial densities at the leaves. Like DETs, MSPNs allow efficient inference so long as the query formula is axis-aligned, and are learned using a greedy scheme. DETs and MSPNs will be discussed in detail later on. Hybrid SPNs (Bueff, Speichert, and Belle 2018) is another very recent alternative and could be used in place of MPSNs. However, since an implementation is not yet available, we postpone an evaluation to future work.
None of the above models can learn or represent structured, oblique supports, which are crucial in many applications, including safety-critical ones. As our experimental evaluation highlights, taking the support into account can lead to dramatically improved performance in some applications.

Background
Satisfiability modulo theories WMI builds on satisfiability modulo linear real arithmetic (SMT(LRA)) ( Barrett et al. 2009), which we briefly overview here. SMT(LRA) extends propositional logic to a combination of Boolean and continuous variables, indicated as A = {A 1 , . . . , A M } and X = {X 1 , . . . , X N }, respectively. An LRA atom is a formula i c i X i c such that X i ∈ X, c i , c ∈ R are constants and ∈ {=, >, <, =, ≤, ≥}. We call an LRA atom axis-aligned if at most one coefficient c i is non-zero, and oblique otherwise. An LRA formula ϕ combines Boolean variables (aka Boolean atoms) and LRA atoms by means of standard logical connectives, e.g., ϕ = (A 1 ∧ (X 1 + X 2 ≤ −1)) ∨ (¬A 1 ∧ (X 1 + X 2 ≥ 1)). The if-thenelse expression ite(ϕ, ϕ , ϕ ) evaluates to ϕ if ϕ holds and to ϕ otherwise. The above formula can be written ite(A 1 , X 1 + X 2 ≤ −1, X 1 + X 2 ≥ 1). Given a set of LRA formulas Φ = {ϕ 1 , . . . , ϕ K }, a total truth assignment μ Φ is an assignment of truth values to all the formulas, e.g., μ Φ = {ϕ 1 → ⊥, . . . , ϕ K → }. Given a formula ϕ and a total truth assignment μ to all its atoms, we denote by μ A the assignment to the Boolean atoms of ϕ. Later on, we will often call SMT(LRA) formulas simply "SMT formulas" and, according to the context, we denote with "μ" either a set of truth assignments or their conjunction.
Weighted model integration Probabilistic inference over discrete variables is often solved with weighted model counting (WMC), i.e., by computing the weighted sum of all satisfying assignments of a propositional formula (Chavira and Darwiche 2008). Weighted model integration (WMI) extends WMC to mixed discrete-continuous domains. Here we follow (Belle, Passerini, and Van den Broeck 2015;Morettin, Passerini, and Sebastiani 2017).
A WMI distribution χ, w over X × A includes: • a (not necessarily minimal) support χ : X × A → B, which encodes the area outside of which w is zero. • a conditional weight function w : X × A → R ≥0 , which associates a weight to interpretations. Intuitively, w plays the role of a density function. We assume (w.l.o.g.) that w integrates to 1. Semantically, w is a piecewise-polynomial function over X × A. More formally, w is characterized by a set of LRA formulas Ψ = {ψ 1 , . . . , ψ K }, such that every assignment μ Ψ identifies a convex region X × A (namely μ Ψ ∧ χ) and defines a potential function w [μ Ψ ] : X × A → R ≥0 on it. The potential functions are usually taken to be (multivariate) polynomials 1 . Encodings for w include directed acyclic graphs (Morettin, Passerini, and Sebastiani 2017) (with sum, product, and branching nodes), MSPNs (Molina et al. 2018), and extended algebraic decision diagrams (XADDs) (Kolb et al. 2018a). In XADDs the internal nodes encode the LRA conditions Ψ and the leaves are labelled with the polynomials w [μ Ψ ] . From this perspective, an assignment μ Ψ merely specifies a path from the root to a leaf, as well as the region The support χ is a standard SMT(LRA) formula. It is used by SMT-based solvers for pruning zero-density areas from the computations using logical reasoning only. Example. Figure 1 illustrates the weight function: The polynomials at the leaves are unnormalized, for simplicity. Figure 1: Left: XADD of an example weight function w. Solid (dashed) arrows point to the true (false) child. Right: WMI can answer marginal and conditional queries in hybrid domains. Given a WMI distribution χ, w , computing the probability of an LRA formula ϕ involves integrating the weight of its (potentially uncountably many) models: Here the sum ranges over all total truth assignments on A and the integral is over all real variables X. Computing the conditional probability of a query ϕ given evidence ϕ e also reduces to weighted model integration: P (ϕ | ϕ e ) = P (ϕ ∧ ϕ e )/P (ϕ e ). Notice that WMI also subsumes volume computation, since vol(ϕ) = WMI(ϕ, 1 | X, A).
Although WMI is #P -hard in general, several solvers have been proposed, including exact approaches based on SMT solvers (Belle, Passerini, and

Learning WMI distributions
We are concerned with learning WMI distributions, that is, hybrid distributions with a structured support. Formally, our learning problem can be stated as follows: Definition (WMI learning). Given a dataset D of feasible samples drawn i.i.d. from an unknown hybrid structured distribution P * with true support χ * , find a WMI distribution ŵ,χ that well approximates P * .
Notice that P * is not required to be a WMI distribution, and that χ * is not required to be an SMT formula. In principle this is not an issue, because (complex enough) WMI distributions can approximate any hybrid structured distribution.
We are now ready to introduce our approach, LARIAT (for LeARning to IntegrATe). Let D = {(x s , a s )} S s=1 be the samples at our disposal, where x s and a s are the values assigned to X and A, respectively. LARIAT estimates a WMI distribution from D by breaking the learning problem into two tasks: 1) learning a supportχ; and 2) learning a weight functionŵ compatible withχ. The first step is handled by a novel generalization of INCAL (Kolb et al. 2018b), a stateof-the-art method for learning SMT formulas. The second step uses a hybrid density estimator to learn a weight function. Finally, LARIAT normalizes the latter to trim away the unfeasible areas. We discuss these steps in detail.

Learning the support
Given examples of positive (feasible) and negative (infeasible) variable assignments, INCAL learns an SMT formula ϕ that covers all positive and no negative examples. Support learning can be reduced to a similar problem, namely finding a formulaχ that generalizes from the feasible samples D to their underlying true support χ * . Here we briefly overview INCAL, and then introduce INCAL+, our generalization of the former to support learning.
Learning SMT formulas with INCAL Given a set D of positive and negative examples and a maximum number of clauses k and unique linear inequalities h, INCAL finds a CNF (or DNF) formula ϕ of the given complexity that correctly classifies all examples. The search is encoded as an SMT(LRA) satisfaction problem and solved with an SMT solver, e.g., MathSAT (Cimatti et al. 2013) or Z3 (De Moura and Bjørner 2008); the full SMT encoding can be found in (Kolb et al. 2018b). This non-greedy learning strategy can acquire SMT formulas with non-convex feasible sets and oblique LRA atoms, which lie at the core of WMI distributions and are beyond the reach of greedier approaches (see (Kolb et al. 2018b) for a discussion).
INCAL employs an incremental scheme whereby a candidate formula is gradually adapted to correctly classify progressively larger subsets of the data. At iteration i, a formula ϕ i that correctly classifies a subset D i of the data is computed. Next, some of the examples V i ⊆ D \ D i inconsistent with ϕ i are added to D i to obtain D i+1 and the process repeats. Empirically, this allows learning a formula by encoding a small fraction of the dataset, with noticeable runtime benefits.
If the target formula complexity (k, h) is not given, INCAL automatically searches for a formula of minimal complexity that covers all positive and no negative examples. This is achieved by gradually increasing k and h (initially set to 1 and 0, respectively) until an appropriate formula is found.
Learning supports with INCAL+ We cast support learning as the problem of finding an SMT formulaχ that covers all of the positive examples and does not cover regions too "far away" from them, as determined by some distance measure d over X × A and a user-provided threshold θ > 0 over it.
More specifically, let B θ be the union of S bounding boxes, each of size θ, centered around the samples in D: s , a s ), (x, a)) ≤ θ} Also, letB θ be its complement. Our assumption is that θ can be chosen so that B θ is a reasonably tight overapproximation of the true support χ * . In this case, ifχ approximates if the solver returns unsat then 6: return no support 7: returnχ i B θ and does not cover any ofB θ , then it will also be a good approximation of the true support. (The algorithm can be trivially adapted to allow for B θ to be an underapproximation instead.) Since too complex supports (in terms of k and h) can overfit, we wish to minimize complexity.
This leads to the INCAL+ support learning problem: where s = 1, . . . , S ranges over all samples in the dataset. As underlying distance we choose d ((x, a), (x , a )) = ite(a = a , max i (x i − x i ), ∞), which admits an SMT(LRA) representation. This formulation can not be solved directly, because of the universal quantifier in Eq. 2. For given (k, h), we solve it with INCAL, by exploiting its incremental learning scheme (see Algorithm 1). First, an initial subset D 1 is obtained (at line 2) by sampling examples from D. Then, at each iteration i, INCAL+ computes a formula ϕ i that correctly classifies D i ⊆ D (line 4), and a set misclassified variable assignments V i is obtained from D; if none are found, a new, misclassified negative is taken fromB θ ∧χ i (lines 7-11). Finding a negative example (x − , a − ) ∈B θ that is wrongly covered byχ i (line 11) is done via SMT by solving: where s iterates over the examples in D and BK is background knowledge that should not be relearned, such as mutual exclusivity of Boolean variables used as a one-hot encoding of discrete multi-valued attributes. The violating examples are then added to D i to obtain D i+1 and the loop repeats. INCAL+ stops when no violating examples can be found. To improve the runtime of the algorithm, initial negative examples sampled fromB θ (e.g., through rejection sampling) can be added to the initial dataset.
Like the original algorithm, INCAL+ allows to search for values of (k, h) by wrapping the above procedure into a loop that gradually increases k and h whenever an appropriate formula can not be found (line 6). This converges to a consistent formula if one exists (Kolb et al. 2018b).
To automatically select a viable threshold θ, we dynamically explore various thresholds θ i = m i · θ nn , where θ nn is the average closest distance between neighbors in D. Since smaller thresholds provide more detailed supports but increase the runtime, we use an exponential-search based procedure to quickly find the smallest multiple m i for which IN-CAL+ can learn a support within a given time budget t. Starting with an initial multiplier m 1 and given a maximal number of steps N , at each step we run INCAL+ with threshold θ i for at most t seconds, increasing the multiplier if a support was found, and decreasing it when INCAL+ timed out. The latter controls the trade-off between computational resources and complexity of the learned support. Notice however that a tighter support is not necessarily better, and that the support to be used in LARIAT should selected e.g. on a validation set.

Learning the weight function
Since the weight function w behaves like a structured density function, it can in principle be estimated by any hybrid density estimation technique. We focus on two state-ofthe-art models, Density Estimation Trees (DETs) and Mixed Sum-Product Networks (MSPNs), which we introduce next. A major limitation is that these estimators can not learn nor model oblique structured supports. Below we show how LARIAT lifts this limitation by normalizing the estimated densities with respect to a learned SMT(LRA) support.

Density Estimation Trees
DETs are a density estimation analogue of standard decision trees. The internal nodes recursively partition the space with univariate, axis-aligned LRA conditions (aka splits), while the leaves define uniform density functions. DETs are learned from data using an iterative procedure, whereby splits are introduced so as to greedily optimize (a surrogate of) the integrated square error (Ram and Gray 2011). The procedure terminates when a pre-specified minimal number of instances is covered by each leaf. In order to control overfitting, the resulting tree is then pruned. The whole learning procedure allows piecewise constant densities to be efficiently learned from data.
DETs have a number of useful features. First, under suitable conditions, DETs are provably consistent (Ram and Gray 2011). Just like decision trees can approximate any Boolean function, deep enough DETs can approximate any weight function to arbitrary precision. Second, given a DET, the weighted model integral of any axis-aligned query ϕ can be easily computed by partitioning ϕ according to the leaves and summing the resulting integrals.
DETs also have limitations. The shallow DETs that are used in practice can not approximate oblique LRA splits. Moreover, DET leaves have constant density and may fail to accurately represent non-constant densities. Finally, since leaves always contain at least one example, DETs can only model trivial supports (Ram and Gray 2011).
Mixed Sum-Product Networks Mixed Sum-Product Networks (MSPNs) (Molina et al. 2018) are state-of-the-art models for hybrid domains. MSPNs extend Sum-Product Networks (Poon and Domingos 2011;Darwiche 2009) by introducing continuous variables and densities. They encode a circuit where the leaves define piecewise polynomial distributions over the input variables, and the internal nodes are sums (i.e., mixtures) or products of their child nodes.
Like DETs, MSPNs are learned greedily from data. The learning algorithm recursively splits the dataset by either: i) partitioning the input variables into independent sets, which amounts to introducing a product node, or ii) clustering similar examples together, thus introducing a sum node. If no split can be found (e.g., if there's only one example/variable in the current dataset), a polynomial leaf node is fit on the data. In practice, MSPNs implementations support univariate constant or linear leaves only.
By exploiting context-specific independencies, MSPNs can be much more compact than DETs, while still allowing for tractable inference of marginal and conditional queries. Indeed, if the queried quantity decomposes over the circuit, then inference amounts to a couple of bottom-up evaluations.

Normalization
The third and final step of LARIAT is normalization. Given a supportχ and a learned piecewise-polynomial weight functionw, normalization aims at redistributing the density ofw away from the unfeasible region outside ofχ and inside the feasible one. After normalization, the resulting weight functionŵ has to satisfy the properties: p 1 ) WMI(¬χ,ŵ) = 0; and p 2 ) WMI(χ,ŵ) = 1. For general densities normalization is computationally hard, because computing the mass of infeasible regions is #P-hard. However, it must only be performed once and the guarantees it offers e.g. in safetycritical applications justify the additional processing cost.
Global normalization These two properties give rise to a simple, yet effective normalization scheme which defines: It is trivial to see that properties p 1 and p 2 are satisfied, however, to improve the likelihood of the resulting density, we can resort to a more elaborate normalization scheme.
Local Normalization Local density estimators, like DETs, partition the space into sub-regions defined by mutually exclusive SMT formulas χ i and fit a local densityw i for every sub-region i. The idea behind local normalization is to retain the space partitioning induced by the learner but to (locally) normalize the densities within every subregion such that: WMI(χ i ∧ ¬χ,ŵ i ) = 0 and WMI(χ i ∧χ,ŵ i ) = WMI(χ i ,w i ), whereŵ i is the normalized local density. It follows that, since the χ i exhaustively partition the entire space and WMI( ,w) = 1, the properties p 1 and p 2 are both satisfied. The local normalized densityŵ i can be computed as: Local normalization for DETs In the case of DETs, local densitiesw i are computed asw i = 1 S Si vol(χi) , and we obtain, using S = |D| for the total number of samples and S i = |D |= χ i | for the number of samples that satisfy χ i : There are three properties of DETs which makes local normalization especially attractive: 1) DETs explicitly describe the sub-regions; 2) norm * and norm + yield the same result sincew i is constant; and 3) since every DET subregion contains at least one sample, no subregion can become entirely infeasible. Local normalization is computationally more expensive than global normalization, however, for locally fit models (like DETs) it obtains more accurate models.
Example. Consider a learned weight function (DET) consisting of two non-zero subregions whose local densities have been fitted based on the number of samples in those sub-regions ( 1 4 th of the samples in the first, and 3 4 th of the samples in the second sub-region): and a supportχ = (y ≥ x). The support only cuts away feasible volume from the first sub-region, meaning that the samples falling into the first sub-region are now distributed over a smaller volume. Therefore, the local normalization procedure increases the density over the remaining feasible volume in the first sub-region, while leaving the second subregion untouched. We obtain the normalized weight function: Local normalization for generic densities First, to normalize generic weight functions encoded as ASTs (e.g., MSPNs) which only indirectly describe the sub-regions and their densities, we can compile the ASTs into equivalent XADDs (Kolb et al. 2018a) that support the enumeration of sub-regions and integration. Second, the choice between norm * and norm + is left up to the user. Third, the density of completely infeasible sub-regions is redistributed over the entire feasible space akin to global normalization. It is important to note that normalization of models like MSPNs that support tractable inference generally may render inference intractable.
Both normalization schemes are amenable to any support, be it learned with INCAL+ or provided by a domain expert (as can be the case in security applications). Since they can can deal with arbitrary WMI distributions, other density estimators such as MARS (see Related Work), can also be readily converted to WMI and normalized.

Empirical Analysis
In this section, we explore the following research questions 2 : Q1) Does INCAL+ learn reasonable supports? Q2) Does LARIAT improve over state-of-the-art density estimators when the true support is provided? Q3) Does LARIAT improve over state-of-the-art density estimators when the support is estimated by INCAL+? We address the first two questions on synthetic datasets of increasing complexity, and the last one on both synthetic and real-world datasets.
Each synthetic dataset was obtained by first generating a random WMI distribution χ * , w * with a given number of Boolean b and continuous variables r, and then sampling examples (i.e. feasible configurations) from it. More specifically: i) w * was a random XADD sampled by recursively adding internal and leaf nodes up to a fixed depth d = 2, where the internal nodes partition the space with a random SMT(LRA) formula, while the leaves host a randomly generated non-negative polynomial of maximum degree 2r. ii) χ * was obtained by sampling a CNF formula with h hyperplanes and l literals using the procedure of (Kolb et al. 2018b). Without loss of generality, we restricted the range of the continuous variables to [0, 1].
We evaluated how the complexity of the true distribution impacts the performance of INCAL+ and LARIAT by generating increasingly complex supports, either by fixing b = 3, l = 3 and varying h and r, or by fixing r = 3, h = 5 and increasing l and b, for a total of 30 configurations. For each configuration, we generated 20 different ground-truth models and relative dataset, each consisting of 500 training and 50 validation examples.
Learning the support In order to answer Q1, we implemented INCAL+ using the MathSAT solver, applied it to the synthetic datasets with a timeout of 300 seconds for each call, and measured the misclassification error between the true and the learned support. This amounts to the volume of the symmetric difference of the two supports, that is, vol((χ ∧ ¬χ * ) ∨ (¬χ ∧ χ * )).
In these experiments we ran INCAL+ on training data D T and used the validation data D V to select the learned support that minimizes: is the indicator function and B θ is the formula that encodes the union of bounding boxes of size θ around the points in D V , being θ the threshold used to learn χ. Contrary to the previous support learning experiment, IN-CAL+ was run on D T ∪ D V . Weight learning was performed on D T only, reserving the validation set D V to select the best support among those learned by INCAL+, as the one yielding the highest log-likelihood on D V . For DETs, the validation set was also used to prune the tree.
We measured the quality of the learned distributions χ,ŵ by measuring the integrated absolute error (IAE) with respect to the true distribution: Since computing the exact value of IAE is computationally prohibitive, we performed a Monte Carlo approximation with 1,000,000 samples. The average IAEs and their standard deviations are shown in Figure 2 (middle) and (right) when using DET and MSPN estimators respectively. The results affirmatively answer Q2, as LARIAT with ground truth support achieves substantial improvements over the density estimators alone, for both DET and MSPN. The same holds for Q3 when using a DET estimator, even if the improvements are clearly more limited. Conversely, the supports learned appear not as effective when applied to the global normalization.
Learning real-world distributions In order to check whether the improvements shown by LARIAT in the synthetic experiments hold in real world scenarios, we tested its performance on real-world datasets (question Q3). The categorical features were converted to Booleans with a one-hotencoding. The resulting mutual exclusivity constraints were used to initialize both INCAL+ and the sampling procedures. Support and weight learning were run using the same setting used for the synthetic distributions.
We evaluated LARIAT on the hybrid UCI benchmarks contained in the MLC++ library, which includes 18 hybrid datasets from different real-world domains. On some datasets, INCAL+ was not able to discover any non-trivial support on the full hybrid space before timing out. In those cases, the search was then performed on the numerical subspace, allowing INCAL+ to learn linear relationships among the continuous variables. Table 1 shows the average loglikelihood computed on the test set for each dataset. (Notice that the log-likelihood of test points falling outside the model support is −∞. In order to apply the metric in our structured and hybrid spaces, we follow the approach of (Molina et al. 2018) and substitute each log(0) in the average with a large negative constant.) For the most complex tasks, LARIAT-DET is sometimes unable to complete the local normalization within reasonable time. If the local normalization timeout (set to 1200s) is reached, LARIAT's fallback strategy is to apply the faster, global normalization.
Nevertheless, in every setting LARIAT improves the performance of the underlying model. We compared the loglikelihood of test set points using a Wilcoxon test, confirming that the improvement is significant for both DETs and MSPNs (p-value < 0.0001).
The tasks that benefited the most from LARIAT are characterized by a large amount of categorical and few continuous variables. A more extensive investigation of the factors contributing to the performance gains is left for future work.

Conclusion and Future Work
We presented LARIAT, a novel approach for learning WMI distributions from data. LARIAT first learns a non-trivial SMT(LRA) support from examples-using an extension of a recent SMT(LRA) constraint learner to positive-only data-and then combines said support with state-of-the-art hybrid density estimators. Our experiments with DETs and MSPNs show that combining support learning and density estimation allows to more accurately recover the underlying density. Our approach is modular, and each component can be replaced with alternative solutions whenever appropriate. For instance, solutions based on search-based program synthesis (Alur et al. 2018) could be explored as a replacement for INCAL+ in learning supports. Concerning the density estimator, we showed the advantages of integrating support learning and density estimation for both DET and MSPN, but other density estimators like the recently proposed HSPN (Bueff, Speichert, and Belle 2018) could be tried as soon as implementations will be made available.