Random coloured digraphs defined by a Markov logic network

A Markov Logic Network (MLN) is a probabilistic relational model used in Statistical Relational Artificial Intelligence for defining a probability distribution on the set of possible worlds with domain D for an arbitrary finite domain D. An MLN consists of soft constraints with associated weights which are nonnegative real numbers. In this study we consider a language speaking about a property P(x) and a relation R(x, y). We consider an MLN for which every Boolean combination of P(x) and R(x, y) is a soft constraint (with associated weight). Let n denote the size (cardinality) of the domain. We show that, for every choice of weights, if the weights are scaled by 1/n then, for every first-order sentence φ, the probability that φ holds tends to either 0 or 1 as n \to \infty; that is, a 0-1 law for first-order logic holds. Morover, the limit probability does {\em not} depend on the weights. If we instead use the standard semantics of MLNs, in the case of which the weights are {\em not} scaled, then the limit behaviour is more complicated and {\em depends} on the weights. With unscaled weights we get 7 qualitatively different cases which depend on the weights. In some cases we have a 0-1 law for first-order logic, in some cases not, but we may still have a convergence law. The influence of the weights on the asymptotic probability of a first-order sentence may be in the form of a sudden ``phase transition'' from one of the 7 cases to another. The presence of a convergence law has positive implications for inference on large domains.