On Projectivity in Markov Logic Networks
This work addresses a foundational issue in relational AI for researchers and practitioners, offering incremental improvements in projectivity for specific MLN fragments.
The paper tackles the problem of domain size dependence in Markov Logic Networks (MLNs), which hinders consistent marginal inference and generalization to new domains, by characterizing conditions for projectivity in two-variable MLNs and identifying the Relational Block Model (RBM) as the best projective MLN in this class for data likelihood maximization, also showing that RBMs allow consistent parameter learning from sub-sampled domains.
Markov Logic Networks (MLNs) define a probability distribution on relational structures over varying domain sizes. Many works have noticed that MLNs, like many other relational models, do not admit consistent marginal inference over varying domain sizes. Furthermore, MLNs learnt on a certain domain do not generalize to new domains of varied sizes. In recent works, connections have emerged between domain size dependence, lifted inference and learning from sub-sampled domains. The central idea to these works is the notion of projectivity. The probability distributions ascribed by projective models render the marginal probabilities of sub-structures independent of the domain cardinality. Hence, projective models admit efficient marginal inference, removing any dependence on the domain size. Furthermore, projective models potentially allow efficient and consistent parameter learning from sub-sampled domains. In this paper, we characterize the necessary and sufficient conditions for a two-variable MLN to be projective. We then isolate a special model in this class of MLNs, namely Relational Block Model (RBM). We show that, in terms of data likelihood maximization, RBM is the best possible projective MLN in the two-variable fragment. Finally, we show that RBMs also admit consistent parameter learning over sub-sampled domains.