Introduction
In probabilistic machine learning, a persistent tension exists between model expressivity and computational tractability. While graphical models like Bayesian Networks (BNs) provide an intuitive framework for representing complex dependencies, they often hit a "complexity wall": exact inference in BNs is generally #P-complete. Consequently, practitioners frequently rely on approximate inference methods, such as Gibbs sampling or loopy belief propagation, which may lack accuracy guarantees or suffer from slow convergence.
This paper proposes a paradigm shift: instead of treating Multi-linear Representations (MLR) as a mathematical derivative of graphical models (often called "Network Polynomials"), we should learn them directly from data. By representing probability distributions as multi-linear polynomials, we can achieve exact inference in time that scales linearly with the model size, often while maintaining a more compact representation than traditional Bayesian Networks.
The Multi-linear Representation (MLR)
An MLR represents a probability distribution as a large polynomial where each term is a product of indicator variables. For a set of variables $X$, an indicator variable $[X_i = s_i]$ evaluates to 1 if the variable takes a specific value and 0 otherwise. The probability of a specific state is the sum of these weighted terms:
$$P(x) = \sum_{i} c_i \prod_{j \in T_i} [X_j = s_j]$$
In this framework, marginalization and conditioning—the core operations of probabilistic inference—become trivial. One simply substitutes the known values and sums the remaining terms, resulting in an inference complexity of $O(\text{terms} \times \text{variables})$.
Methodology
1. Structure Learning
To avoid the exponential explosion of terms in a full polynomial, the authors employ a heuristic from data mining: Frequent Closed Itemsets. By treating training instances as transactions, the model identifies patterns (monomials) that appear frequently together in the data. These patterns form the structural "terms" of the MLR.
2. Parameter Learning
Once the terms are defined, the coefficients ($c_i$) must be optimized to ensure the polynomial represents a valid probability distribution:
- Exact-MLR: This approach uses constrained convex optimization to maximize the log-likelihood of the training data.
- Approx-MLR: To address the computational cost of convex optimization, the authors derived a closed-form approximation that maximizes a lower bound of the likelihood. This provides a high-speed alternative that can also serve as an initialization for the exact solver.
Theoretical Insights
The Compactness Paradox
The authors demonstrate (Theorem 1) that MLRs can be exponentially more compact than Bayesian Networks for certain distributions. BNs often require the introduction of numerous "dummy" dependencies or edges to represent specific distributions, whereas an MLR can capture the same information with a handful of polynomial terms.
The Positivity Challenge
A valid probability distribution must always yield non-negative values. However, verifying the positivity of a general multi-linear polynomial is NP-hard. To circumvent this, the authors restrict all coefficients ($c_i$) to be non-negative. While this guarantee of validity might require a larger number of terms than a version allowing negative coefficients, it ensures the model remains computationally feasible.
Experimental Results
The framework was evaluated against WinMine, a standard toolkit for learning Bayesian Networks, across three UCI datasets: Primary Tumor, House Votes, and Letter Recognition.
- Accuracy: MLR-based models achieved higher joint log-likelihoods than WinMine on the Primary Tumor and Letter Recognition datasets, while performing comparably on the House Votes dataset.
- Inference Speed: The MLR approach demonstrated significant computational advantages. On the Letter Recognition dataset, MLR inference was over 100 times faster than the approximate Gibbs sampling used by the Bayesian Network.
- Generalization: The authors observed that MLRs with smaller terms (fewer variables per monomial) tend to generalize better, as they avoid the overfitting associated with highly specific, high-order dependencies.
Conclusion
By elevating Multi-linear Representations from a theoretical byproduct to a primary learning target, this research offers a viable path toward efficient, exact probabilistic inference. While the current reliance on frequent itemset mining is a heuristic, the results suggest that direct polynomial learning can outperform traditional graphical models in both speed and accuracy. Future work will focus on more principled methods for growing polynomial structures and refining the positivity constraints to further enhance model compactness.
Summary updated