Full-joint distributions are particularly attractive representations of (uncertain) knowledge, for they enable a wide variety of reasoning patterns: Causal, diagnostic and mixed inference patterns are all supported within a single framework. Given a full-joint distribution $P(X=x)$ over a set of variables $X$, we can, in particular, reason about conditional probabilities of the form $P(Q=q \mid E=e)$ for any subsets $Q \subseteq X$ and $E \subseteq X$ of the variables. Probabilistic models that represent such distributions have thus long been viewed as valuable resources for AI systems at large.

With joint probability trees (JPTs), Nyga et al. present a novel formalism for the representation of full-joint distributions with some attractive properties [Nyg23J]:

• support for hybrid domains (discrete and continuous random variables)
• tractable learning and inference
• model construction in the absence of domain knowledge (no prior specification of a dependency structure is necessary)

Representation

A joint probability tree represents a full-joint distribution over a set of random variables $X = \{ X_1, \dots, X_N \}$ as a mixture model, where

• the mixture components are obtained by recursively partitioning a training set using a greedy algorithm that seeks to minimise an impurity metric (analogous to the learning of decision trees).
• the representation of the full-joint distribution of each mixture component assumes mutual independence of the random variables, i.e. each component contains representations of $N$ univariate distributions.

Let $\Lambda$ be the set of partitions (leaves) we obtain via the learning algorithm. The full-joint distribution then decomposes as follows, \begin{align} P(X=x) &= \sum_{\lambda \in \Lambda} P(X=x \mid \lambda) P(\lambda) \\ &= \sum_{\lambda \in \Lambda} P(\lambda) \prod_{i=1}^N P(X_i=x_i \mid \lambda), \end{align} where $P(\lambda)$ is the fraction of the samples that ended up in leaf $\lambda$ during training, and $P(X_i=x_i \mid \lambda)$ is computed based on the distribution that is stored for random variable $X_i$ in leaf $\lambda$:

• For a discrete variable $X_i$, $P(X_i=x_i \mid \lambda)$ is simply the relative frequency of value $x_i$ in the training samples that ended up in leaf $\lambda$. We thus store the corresponding multinomial distribution in $\lambda$.
• For a continuous variable $X_i$, we store a cumulative distribution function (CDF), which we conveniently represent as a piecewise linear function, such that both density values of the form $P(X_i=x_i \mid \lambda)$ and range queries of the form $P(x_i^\bot \leq X_i \leq x_i^\top \mid \lambda)$ can straightforwardly be supported. To achieve compactness, the authors use a recursive optimisation scheme in order to induce the CDF representation from the training samples in $\lambda$.

Learning

JPTs use a recursive partitioning scheme that is inspired by the greedy algorithms typically used for the induction of decision trees, which we shall briefly review: When inducing a (binary) decision tree, the fundamental operation is to split the training dataset into two subsets, such that the average impurity in the two subsets is lower than the impurity of the set we started with. The split condition can be any condition that compares one of the variables against a constant (e.g. $X_i < c$ for a continuous variable $X_i$ and some real-valued constant $c$) and we greedily choose, among all candidate splits, the one that yields the greatest reduction in impurity. The two subsets are then recursively split in the same way until a termination criterion is met (e.g. until impurity is sufficiently low or until the sets have become too small).
The reduction in impurity means that after we have checked the condition, we are closer to a unique answer than we were previously. For classification, a common impurity metric is the entropy of the class variable’s distribution, and for regression, one often uses the variance of the regression target variable, which corresponds to the mean squared error (MSE) when using the mean as the predictor.
In JPTs, there is no target variable; the goal is to obtain subsets where the impurity of all variables is low, and the authors thus minimise the (weighted) sum of the impurity values pertaining to the individual variables. In order to reconcile the semantics of impurity values of discrete and continuous variables (at various scales), relative improvements in impurity for each variable are considered in order to determine the best splits. Figure 1 illustrates JPT learning and the resulting representation based on the example of a hybrid distribution involving three variables.

The authors’ evaluation indicates promising performance in practice, showing that generative JPTs can perform on par with discriminative models (that were specifically trained to solve a specific classification or regression problem) whilst retaining a much higher degree of flexibility.
Moreover, although the authors do not explicitly mention this, the JPT learning algorithm can also be viewed as a clustering method which falls into the category of divisive hierarchical clustering algorithms. When combined with appropriate, clustering-specific termination criteria, it could prove to be a highly effective automatic clustering method where no prior knowledge on the number of clusters is required.

Discussion

The independence assumption that is made in each leaf may seem strong, yet the impurity minimisation that is at the heart of the learning algorithm seeks to ensure that there are ultimately few interactions between the variables, reducing co-information and thus weakening the assumption. By varying the number/size of partitions, we can essentially control the degree to which the independence assumption constitutes an approximation.
However, with the current incarnation of JPTs as proposed by the authors, we cannot arbitrarily reduce leaf size, because doing so may result in a potentially problematic case of overfitting where the probability of the evidence becomes zero for an increasingly large number of out-of-sample predictions. Fortunately, we can conceive of straightforward solutions to this problem: We could, for instance, assume that the observed values of continuous variables are but noisy observations of the true values and apply the principles of kernel density estimators in order to induce the CDF representations. For discrete variables, we could, in a similar spirit, assume pseudo-counts.
The authors provide an open-source implementation, so little stands in the way of experimentation.