An alternative to the previous models that learn embedding of entities and relations is to learn the interdependencies of relations, building models that predict some relations in terms of others, similar to how graphical models of Chapter 9 represented the interdependencies of random variables.

The belief networks of Chapter 9 were defined in terms of random variables. Many domains are best modeled in terms of entities and relations. Agents must often build models before they know what entities are in the domain and, therefore, before they know what random variables exist. When the probabilities are being learned, the probabilities often do not depend on the identity of the entities. Probability models with entities and relations are studied in the area of statistical relational AI, and the models are referred to as relational probabilistic models, probabilistic relational models, or probabilistic logic models.

A relational probabilistic model (RPM) is a model in which the probabilities are specified on the relations, independently of the actual entities. The entities share the probability parameters. The sharing of the parameters is known as parameter sharing or weight tying, as in convolutional neural networks.

A parameterized random variable is of the form $R(t_1,\mathrm{\dots },t_k)$, where each $t_i$ is a term (a logical variable or a constant). The parameterized random variable is said to be parameterized by the logical variables that appear in it. A ground instance of a parameterized random variable is obtained by substituting constants for the logical variables in the parameterized random variable. The ground instances of a parameterized random variable correspond to random variables, as in Section 17.1. The domain of the random variable is the range of $R$. A Boolean parameterized random variable $R$ corresponds to a predicate symbol. For example, $Grade(S,C)$ is a parameterized random variable, and $Grade(s_3,c_4)$ is a random variable with domain the set of all possible grades.

We use the Datalog convention that logical variables start with an upper-case letter and constants start with a lower-case letter. Parameterized random variables are written starting with an upper-case letter, with the corresponding proposition in lower case (e.g., $Diff(c_1)=true$ is written as $diff(c_1)$, and $Diff(c_1)=false$ is written as $\neg diff(c_1)$), similar to the convention for random variables.

A plate model consists of

• •

  a directed graph in which the nodes are parameterized random variables

• •

  a population of entities for each logical variable, and

• •

  a conditional probability of each node given its parents.

A rectangle – a plate – is drawn around the parameterized random variables that share a logical variable. There is a plate for each logical variable. This notation is redundant, as the logical variables are specified in both the plates and the arguments. Sometimes one of these is omitted; often the arguments are omitted when they can be inferred from the plates.

A model that contains parametrized random variables is called a lifted model. A plate model means its grounding – the belief network in which nodes are all ground instances of the parameterized random variables (each logical variable replaced by an entity in its population) and the arcs are preserved. That is, the parametrized random variables in each plate are replicated for each entity. The conditional probabilities of the grounded belief network are the same as the corresponding instances of the plate model.

Figure 17.6 shows the three cases of how a directed arc interacts with a plate. The population of logical variable $X$ is $\{x_1,\mathrm{\dots },x_n\}$. The random variable $A(x_i)$ is written as $A_i$, and similarly for $B$. The parametrization can be inferred from the plates.

In Figure 17.6(a), $A$ and $B$ are both within the plate, and so represent the parametrized random variables $A(X)$ and $B(X)$. In the grounding, the arc is replicated for every value of $X$. The conditional probability $P(B_i\mid A_i)$ is the same for every $i$, and is the one modeled by $P(B\mid A)$ in the lifted model. $A_i$ and $B_i$ are independent of $A_j$ and $B_j$ for $i\ne j$, unless there is another arc to make them dependent.

In Figure 17.6(b), the parent is outside of the plate, and so it is not replicated for each element of the population. $P(B_i\mid A)$ is the same for all $i$. This makes the $B_i$ dependent on each other when $A$ is not observed. The number of parameters in the lifted models of Figure 17.6(a) and (b) is the same as the network without the plates, and so is independent of the population size $n$.

In Figure 17.6(c), the child is outside of the plate, with a variable number of parents. In this case $B$ has $n$ parents and so cannot use the conditional probability $P(B\mid A)$. It needs an aggregator to compute the probability from arbitrary many parents. The aggregator is symmetric, as the index is of no significance; exchanging the names has no effect. This symmetry is called exchangeability. Some aggregators are the following:

• •

  If the model is specified as a probabilistic logic program with Boolean logical variables, the existential quantification of the logical variables in the body of a clause results in a noisy-or aggregation. In the aggregator of Figure 17.6(c), the noisy-or is equivalent to $b\leftarrow (\exists Xa(X)\wedge n(X))\vee n_0$, where $n_0$ and $n(x)$ are independent random variables for all instances $x$ of $X$.

• •

  The model can be specified using weighted logical formulas, extended to first-order logic. A first-order weighted logical formula is a pair of a first-order logic formula and a weight. The conditional probability is proportional to the exponential of the sum of weights of the groundings of formulas that are true. In this case, the aggregation becomes a case of logistic regression, called relational logistic regression.

  For example, the first-order weighted formulas $(b:w_0)$, $(b\wedge a(X),w_1)$ and $(b\wedge \neg a(X),w_2)$ result in $P(b\mid as)=sigmoid(w_0+c_1\ast w_1+c_2\ast w_2)$, where $as$ is an assignment of values to the parents consisting of $c_1$ entities with $A(e)=true$ and $c_2$ entities with $A(e)=false$.

• •

  Standard database aggregators such as average, sum, or max of some values of the parents can be used.

• •

  A more sophisticated aggregation, latent Dirichlet allocation (LDA), is when the population of the plate corresponds to the domain of the child. The value of $A(v)$ can be used to compute $P(B=v)$. For example, using a softmax

  $$P(B=v)=\frac{\exp (A(v))}{{\sum }_{v^{\prime }}exp(A(v^{\prime }))}$$

  (or perhaps without the exponentiation, if $A(v)\ge 0$). The aggregation is thus implementing an attention mechanism, similar to that used in transformers.

For overlapping plates, the values are duplicated for each plate separately, as in the following example.

Suppose there are many true/false questions that you would like the answer to. One way to find the answer might be to ask many people using crowd sourcing, where the users might be paid for reliable answers. Each person answers some subset of the questions; the aim is to determine which questions are true, and who to pay. Some people and bots may give random answers, in the hope of being paid for very little work. The problem of determining truth from crowd sourcing is called truth discovery.

One application for truth discovery is to evaluate predictions of an AI algorithm on a knowledge graph. You cannot just use a held-out test set for evaluation as there are only positive examples in a knowledge graph. Negative examples are required to evaluate probabilistic predictions, for example, using log loss. Negative examples can be acquired by crowd sourcing.

One way to represent this problem is the plate model of Figure 17.8, where $Answer(U,Q)$, the provided answer by user $U$ to question $Q$, depends on the reliability of $U$ and the truth of $Q$.

The conditional probabilities can specify that the answer provided by reliable users is highly likely to be the truth, and the answer provided by an unreliable person is likely to be random. When conditioned on the answers provided, the users are classified as reliable or not and the questions are classified as true or false. It may not take many reliable users answering a particular question to make us quite sure of the truth of the question, but users who answer randomly provide no information about the answer. Simultaneously classifying multiple entities, as in this case, is called collective classification.

Exact inference in this model is intractable because the treewidth of the grounding containing the $Reliable$, $True$, and observed $Answer$ random variables grows quickly; see Exercise 17.6. One way to carry out inference is to use Markov-chain Monte Carlo (MCMC), alternating between the truth random variables and reliability random variables.

Once there is a rough division into reliable and unreliable users and the truth of questions, expectation maximization (EM) can be used to learn the probability that a reliable user will give the correct answer and the prior probability that a user is reliable.

Such methods, however, can be manipulated by collusion among the users to give misinformation, which for this case means wrong answers. When some users are colluding to give misinformation, other methods can be used to help determine which users are reliable. You could start with some questions for which you know the truth; probabilistic inference can be used to determine reliability. Alternatively, some users can be deemed to be reliable; users that agree with them will be more likely to be reliable. It is also possible to have more than two classes as the domain of $Reliable$; how many classes to use is beyond the scope of the book, but the Chinese restaurant process provides one answer to that question. It is very difficult to counter the case where a group of people collude to give correct answers to all of the questions except for one; you can just hope that non-colluding reliable users will out number the colluding ones. Sometimes the best one can do is to check answers and find that collusion probably has occurred. Be warned, however, that just because people agree that something is true does not mean that it is true.

The probabilistic language models of Section 9.6.6, including the topic models of Figure 9.38, are simpler when viewed as relational models. Inferring the topic(s) of a document can help disambiguate the words in a document, as well as classify the documents.

Figure 17.9 shows a plate representation of a model where a document, represented as a set of words, has a single topic. In this model:

• •

  $D$ is the set of all documents

• •

  $W$ is the set of all words

• •

  $A(W,D)$ is a parametrized random variable such that Boolean $A(w,d)$ is true if word $w$ appears in document $d$

• •

  $T(D)$ is a parametrized random variable such that $T(d)$, with domain the set of all topics, is the topic of document $d$.

In this model, the topic for a document is connected to all words. There is no aggregation, as there are no arcs out of a plate. The documents are independent of each other.

Figure 17.10 shows a plate representation of a model where a document, represented as a set of words, can have multiple topics. Instead of having a random variable with domain the set of all topics – implying a document can only have a single topic – there is a Boolean random variable for each topic and document:

• •

  $D$ is the set of all documents

• •

  $W$ is the set of all words

• •

  $T$ is the set of all topics (with a slight abuse of notation from the previous model)

• •

  Boolean $A(w,d)$ is true if word $w$ appears in document $d$

• •

  Boolean $S(t,d)$ is true if topic $t$ is a subject of document $d$.

In this model, all topics for a document are connected to all words. The documents are independent of each other. The grounding for a single document is show in Figure 9.29. Because there is an arc out of a plate, this model requires a form of aggregation. Noisy-or was used in Google’s Rephil; see Example 9.38.

Figure 17.11 is like the previous case, but with a bag-of-words (unigram) model of each document. In this model

• •

  $D$ is the set of all documents

• •

  $I$ is the set of indexes of words in the document; $I$ ranges from $1$ to the number of words in the document

• •

  $T$ is the set of all topics

• •

  $W(d,i)$ is the $i$’th word in document $d$; the domain of $W$ is the set of all words.

• •

  $S(t,d)$ is true if topic $t$ is a subject of document $d$; $S$ is Boolean.

Figure 17.12 shows a model called latent Dirichlet allocation (LDA), with the following meaning:

• •

  $D$ is the document and $I$ is the index of a word in the document.

• •

  $T$ is the topic.

• •

  $w(d,i)$ is the $i$th word in document $d$. The domain of $w$ is the set of all words; thus, this is a bag-of-words model.

• •

  $to(d,i)$ is the topic of the $i$th word of document $d$. The domain of $to$ is the set of all topics. $P(w(d,i)\mid to(d,i)$ gives the word distribution over each topic.

• •

  $pr(d,t)$ represents the proportion of document $d$ that is about topic $t$. The domain of $pr$ is the reals. If $pr(d,t)$ is positive (pseudo)counts, this is a Dirichlet distribution, with

  $$P(to(D,I)=t\mid pr(D,T))=\frac{pr(D,T=t)}{{\sum }_{t^{\prime }}pr(D,T=t)}.$$

  Alternatively, $pr(d,t)$ could be represented as a softmax, with

  $$P(to(D,I)=t\mid pr(D,T))=\frac{\exp (pr(D,T=t))}{{\sum }_{t^{\prime }}\exp (pr(D,T=t^{\prime }))}$$

  which is similar to an attention mechanism, where each word pays attention to the topics.

To go beyond set-of-words and bag-of-words, for example, to model the sequence of words an $n$-gram, more structure is needed than is specified by a plate model. In particular, these require the ability to refer to the sequence previous words, which can be represented using structure in the logical variables (plates), such as can be provided by function symbols in logic.

Any of the representations of belief networks can be used for representing relational probabilistic models. However, because plates correspond to logical variables, representations defined in terms of first-order logic most naturally represent these models. The models can also provide structure in the logical variables. In the neural network literature, plate models are referred to as convolutional models, due to the parameter sharing, which also corresponds to universal quantification in logic.

The representations mainly differ in the way they handle aggregation, and whether latent features are random variables or tunable weighted formulas (as in neural networks).

Some notable representations include the following.