TL;DR
This paper introduces a novel, closed-form method (DN2MN) to convert Dependency Networks (DNs) into Markov Networks (MNs). This allows researchers to leverage the fast learning of DNs while benefiting from the well-established inference and representation capabilities of MNs, achieving significant speedups and comparable or improved accuracy.
What Problem Does This Paper Address?
Representing joint probability distributions is fundamental in many AI domains. Markov Networks (MNs) are powerful for this, but learning their structure from data is computationally expensive, often involving exhaustive searches and costly evaluations of candidate structures. Dependency Networks (DNs) offer a much faster alternative for learning, as they decompose the problem into learning individual conditional probability distributions (CPDs). However, DNs can be inconsistent (meaning no single joint distribution satisfies all CPDs), making them difficult to interpret and limiting the availability of inference algorithms. This paper bridges this gap by providing an efficient way to convert potentially inconsistent DNs into MNs, combining the best of both worlds.
Methods
The core of the paper is the DN2MN algorithm, which converts a DN into an MN in a closed form, without search or optimization. For a consistent DN, this conversion is exact. The method relies on expressing the ratio of probabilities between two configurations of variables that differ by only one variable. By chaining these ratios and using a specific ordering of variables, the algorithm derives factors for the equivalent MN.
When DNs are inconsistent, the conversion can depend on the choice of a base instance and variable ordering. To address this, the authors propose averaging methods:
- Averaging over base instances: Instead of picking a single base instance, they average the resulting MNs. This can be done by combining features and adjusting weights based on the probability of encountering that feature in different base instances.
- Averaging over orderings: Since the conversion depends on the variable order, they average over multiple orderings to get a more robust result.
The paper also details how to handle DNs represented as log-linear models with conjunctive features, which is more efficient than tabular representations.
Datasets
The authors evaluated their methods on 12 standard MN structure learning datasets, which were originally collected and prepared by Davis and Domingos [3]. These datasets consist of binary variables and vary in size and number of variables. The paper provides a table summarizing these datasets.
Key Insights and Ideas
- Bridging the DN-MN divide: The most significant insight is that a direct, closed-form conversion from DNs to MNs is possible, offering a practical way to combine fast DN learning with robust MN representation and inference.
- Inconsistency is manageable: The paper demonstrates that even for inconsistent DNs, averaging over base instances and orderings can yield accurate MN approximations, often outperforming direct weight learning on the resulting MNs.
- Log-linear models simplify conversion: Converting DNs represented as log-linear models with conjunctive features is more efficient and scalable than using tabular CPDs.
- DN2MN is orders of magnitude faster: The proposed method offers a dramatic speedup compared to traditional MN learning methods, making it practical for larger datasets.
Key Results
- Speed: The DN2MN method is 7 to 1200 times faster than weight learning for converting DNs to MNs, depending on the type of CPDs used.
- Accuracy: For decision tree CPDs, the converted MNs were often more accurate than the original DNs. For logistic regression CPDs, the converted MNs were significantly more accurate than MNs learned via weight learning.
- Averaging Benefits: Averaging over orderings and base instances significantly improved the accuracy of the converted MNs, especially for inconsistent DNs. Using 2n orderings and marginals for base instances yielded the best results.
Limitations and Future Work
- Inconsistent DNs: While averaging methods improve approximations for inconsistent DNs, the conversion is not exact. The paper notes that for inconsistent DNs, a uniform distribution over all possible states might not always be the best approach, and using marginal distributions from training data proved slightly better.
- Future Work: The paper suggests that DN2MN can exploit many types of conditional distributions (e.g., boosted trees, rule sets) and can benefit from algorithmic improvements in learning those CPDs. It also highlights the potential for using DN2MN when models are specified by experts, as conditional distributions can be easier to define than joint distributions.
Summary updated