Advances in automated knowledge base construction have led to successful systems, such as DeepDive [17], NELL [13], and Google's Knowledge Vault [7]. They extract structured knowledge from multiple sources, through a chain of statistical techniques, and produce probabilistic knowledge bases (PKBs). The basic data model underlying these systems is given by probabilistic databases (PDBs) [18]; see recent surveys focusing on PKBs [2, 4]. PKBs are inherently incomplete, which makes reasoning more challenging. A common way to deal with incompleteness is to add commonsense knowledge, in the form of logical theories, to allow for deductions that go beyond existing facts in the knowledge base. Statistical relational models are concise, and lifted representations of probabilistic graphical models [9]. Well-known examples include Markov logic networks (MLNs) [15], relational Bayesian networks [10], and approaches to probabilistic logic programming (PLP). All these models can encode commonsense knowledge, but they are based on the closed-domain assumption (CDA) that requires the set of relevant objects to be finite, and known at design-time, which is not always an easy condition to be met. And contrary to the intuition, the CDA does not necessarily imply efficiency in comparison to open-domain models. Example 1. In the closed domain C = {c1, . . . , cn}, the following are equivalent:
(1) (2) That is, all employee’s addresses must be one of the known objects in the database. If the address of a new employee is still unknown, in an interpretation they will be randomly assigned the address of another employee. A common remedy is to introduce a number of auxiliary objects into C that can serve as “unknown addresses”. However, it is unclear how many additional objects are needed.
Another problem is the large disjunction in (2), which introduces a huge
amount of nondeterminism. For MLNs, this is a known problem, and more
sophisticated techniques to eliminate existential quantification exist [
Stefan Borgwardt, İsmail İlkan Ceylan, and Thomas Lukasiewicz
in the worst case, these techniques also cannot avoid the nondeterminism over
the fixed domain. For this reason, almost all MLN implementations only support
universal quantification [
Probabilistic models that can encode commonsense knowledge while allowing
an open domain include PLP with function symbols [
Another problem that is inherent to knowledge-based probabilistic models is related to inconsistent worlds, which are usually removed, and the resulting probability distribution is renormalized.
Example 2. Consider the following tuple-independent PDB P and theory T : P ∶= {⟨A(a) ∶ 0.5⟩, ⟨B(a) ∶ 0.5⟩}
T ∶= {∀x A(x) → B(x)}.
The possible worlds are
W1 ∶= {A(a), B(a)}, W2 ∶= {A(a), ¬B(a)}, W3 ∶= {¬A(a), B(a)}, W4 ∶= . . . Without T , each of these worlds has the probability 0.25, by the independence assumptions of P. However, since W2 is inconsistent with T , its probability is reduced to 0, and the probability of the remaining worlds is renormalized to add up to 1, yielding a probability of 0.33 each. As an undesired side effect, the probabilities for A(a) and B(a) change to 0.33 and 0.66, respectively. ∎
We argue that the observed probabilities of 0.5 should be preserved, and try to find a log-linear distribution that deviates from these input values as little as possible. By assigning both W2 and W3 a probability of 0 and the remaining worlds 0.5 each, we obtain a model that satisfies the constraints of both T and P. This approach respects both the probabilistic and the logical input, and does not favor one over the other. In our new approach, we assume the database given as a set of facts with associated weights, which is then interpreted as a log-linear model. As in MLNs, we restrict the probability distribution to the known objects, but additionally use a first-order theory interpreted over arbitrary, possibly infinite domains, whereby we achieve open-world, open-domain reasoning.
We show that reasoning in our model can be reduced (via polynomial rewriting techniques) to inference in MLNs, or PDBs. These results are significant given the expressive nature of our formalism. As a consequence of the above reductions, many computational complexity results from previous models carry over. We also describe a new approach to learn the weights for our model, based on the principle of maximum entropy, to establish the connection with existing PKBs. This approach is independent of the other results, however—in principle, we could use any other weight learning method, e.g., using standard renormalization.
The full paper can be found at https://tu-dresden.de/inf/lat/papers.