Successful machine learning methods require a trade-off between memorization and generalization. Too much memorization and the model cannot generalize to unobserved examples. Too much over-generalization and we risk under-fitting the data. While we commonly measure their performance through cross validation and accuracy metrics, how should these algorithms cope in domains that are extremely under-determined where accuracy is always unsatisfactory? We present a novel probabilistic graphical model structure learning approach that can learn, generalize and explain in these elusive domains by operating at the random variable instantiation level. Using Minimum Description Length (MDL) analysis, we propose a new decomposition of the learning problem over all training exemplars, fusing together minimal entropy inferences to construct a final knowledge base. By leveraging Bayesian Knowledge Bases (BKBs), a framework that operates at the instantiation level and inherently subsumes Bayesian Networks (BNs), we develop both a theoretical MDL score and associated structure learning algorithm that demonstrates significant improvements over learned BNs on 40 benchmark datasets. Further, our algorithm incorporates recent off-the-shelf DAG learning techniques enabling tractable results even on large problems. We then demonstrate the utility of our approach in a significantly under-determined domain by learning gene regulatory networks on breast cancer gene mutational data available from The Cancer Genome Atlas (TCGA).

In order to rigorously characterize the difference or similarity between two probabilistic knowledge bases, a distance/divergence metric must be established. This becomes increasingly important when conducting parameter learning or tuning of a knowledge base. When tuning a knowledge base, it is essential to characterize the global probabilistic belief change as the knowledge base is tuned to ensure the underlying probability distribution of the knowledge base is not drastically compromised. In this paper, we develop an entropy-based distance measure for a Bayesian Knowledge Base (BKB) derived from the Chan-Darwiche distance measure used in a variety of probabilistic belief network analyses. Through this distance measure it is possible to calculate the theoretical minimum distance required to correct a BKB when the system's answer contradicts that of an expert. Having a theoretical minimization limit on distance allows for a quick calculation to test the integrity of either the BKB or the expert's judgement, since a high minimum distance would suggest the necessary tuning is not consistent with the rest of the knowledge base. Further still, this distance measure can be used to prove that in some cases the standard single causal rule set BKB tuning procedure (discussed in our prior work) in fact minimizes the global BKB distance. The final portion of this paper presents a few practical examples which analyze the utility of the BKB distance measure along with evidence supporting the proposition that the Causal Rule Set tuning procedure minimizes the distance between the original and tuned knowledge base in many cases.