Bayesian Networks

Let us revisit the example of genetic inheritance of coat color in guinea pigs.The fur color pattern $O$ of guinea pigs is determined by genetic material $H$ of the specimen, as well as by environment factors $D$, the post-conception pre-birth developmental factors, and $E$, the post-birth developmental factors. The genetic material $H$ is probabilistically determined by the genetic materials $H_F$ and $H_M$ of the female and male parents, respectively. These genetic factors in turn determine the color patterns $F$ and $M$ of the female and male parents.

To obtain a directed graphical description of that knowledge, we identify the parents of each node $X$ as the minimum set of random variables we need to specify its probability. This way, the parents of $X$ are the random variables whose influence is not mediated by any other variable, thus giving a meaning to a direct relationship. For example, the probability of $H$ can be specified given knowledge of $H_F$ and $H_M$, and the influence of other factors is mediated by those variables. Similarly, $O$ depends on $H$, $E$ and $D$, and the influence of other quantities, say $H_F$ and $H_M$, are mediated by these variables. Also, the probability of $E$ can be specified without any further knowledge, and there does not seem to exists a quantity that mediates influence on $E$; we thus specify the parents set of $E$ as empty. Following this reasoning for all the random variables, we obtain the following digraph.

The chances of developing dyspnea ($D$) are higher on patients that had tuberculosis ($T$), lung cancer ($L$) or bronchitis ($B$). A recent visit to Asia ($A$) increases the chances of tuberculosis, while smoking ($S$) is a risk factor for both lung cancer and bronchitis. An X-ray ($X$) does not distinguish between lung cancer and tuberculosis, and neither the presence or absence of dyspnea. Let $E$ denote the disjunction of $T$ and $L$. Following the same procedure as before (define as parents the nodes which are necessary and sufficient to specify its conditional probability), we reach the acyclic digraph below.

These are the Markov properties represented by the digraph of the coat color problem.

$$ \begin{gather*} O \ind F, H_F, H_M, M \mid E, H, D \\ E \ind H,D,F,H_F,M,H_M \\ D \ind H,E,F,H_F,M,H_M \\ H \ind E, D, F, M \mid H_F, H_M \\ F \ind H_M, M, H, E, D, O \mid H_F \\ M \ind H_F, F, H, E, D, O \mid H_M \\ H_F \ind H_M, M, E, D \\ H_M \ind H_F, F, E, D
\end{gather*} $$

A joint probability distribution satisfying the Markov property with respect to the graph of guinea pig coat color problem factorizes as $$ \begin{multline*} P(O,D,E,H,H_F,H_M,F,M) = \\ P(H_F) P(H_M) P(F|H_F) P(M|H_M) P(E) P(D) P(H|H_F,H_M) P(O|D,E,H) \, . \end{multline*} $$ Considering that all variables are binary, this specification requires $1 + 1 + 1\cdot 2 + 1 \cdot 2 + 1 + 1 + 1 \cdot 2 \cdot 2 + 1 \cdot 2 \cdot 2 \cdot 2 = 20$ probability values, against the $2^8-1=255$ values required by the naive specification of the joint distribution.

A joint probability distribution satisfying the Markov property with respect to the graph of the visit to Asia problem factorizes as $$ \begin{multline*} P(A,S,T,L,E,B,X,D) = \\ P(A)P(S)P(T|A)P(L|S)P(E|T,L)P(B|S)P(X|E)P(D|E,B) \, . \end{multline*} $$ Assuming that all variables are binary, this specification requires $1 + 1 + 1\cdot 2 + 1\cdot 2 + 1\cdot 2 \cdot 2 + 1 \cdot 2 + 1 \cdot 2 + 1 \cdot 2 \cdot 2=18$ probability values, against the $2^8-1=255$ values required by the naive specification of the joint distribution.

We can build a Bayesian network of the survivability of the Titanic sinking assuming that Gender and Class are independent random variables that direct influence Status, as shown in the digraph below.

We can estimate the conditional probabilities as the relative counts:

$P(G=\text{male}) = 0.56$ and $P(C=\text{1st})= 0.53$. These conditional distributions and digraph specify a Bayesian network whose joint probability distribution is given by $P(G,C,S)=P(S)P(G)P(S|G,C)$.

This example was taken from Norman Fenton’s note. Several recent studies suggest that smoking may reduce the severity of COVID-19 symptoms. These studies however are plagued by selection bias in their data, that originates from collecting information from a non-representative sample of the population. In particular, Myiara et al. collected data from 479 patients that tested positive ($T$) for COVID-19 at a large French hospital. According to the data, 64% of the smokers ($S$) developed more severe symptoms ($D$), compared with 73% of the non-smokers. Selection bias in the data was observed by noticing that the sample contained 6% of smokers, against the much higher rate of smokers in the French population, estimated to be nearly 26%, and that health workers ($O$) were over-represented. The digraph below provides an alternative explanation where the lower incidence of severe symptoms in smokers is obtained indirectly by the influence of the occupation sector on the severity of the disease and the probability of testing positive.

Fenton’s estimated the following conditional distributions using publicly available data and commonsense.

The joint probability distribution is given by $$ P(O,S,D,T) = P(O)P(S|O)P(D|O,S)P(T|O,D) \, . $$ One can use the network to verify that $$ P(D=\text{severe} | S = \text{no}, T = \text{yes}) = 0.1739 $$ and $$ P(D=\text{severe} | S = \text{yes}, T = \text{yes}) = 0.1548 \, . $$ Thus a higher incidence of severe symptoms for non-smokers is obtained despite the fact that the model assumes no direct relation between smoking and the disease (and no directed path between these two quantities).

Jochems et al. built a Bayesian network to predict dyspnea ($D$) in patients that received radiotherapy treatment for lung cancer. ² The network used information from tumor location ($T$), lung function tests ($L$), pre-treatment dyspnea ($B$), cardiac comorbidity ($H$) and timing of chemo ($C$). Numerical variables have been discretized. The graphical structure was elicited from medical experts and is shown below.

The conditional probability distributions were independently estimated from clinical data of 287 patients of 5 different medical facilities, and then combined to produce the tables below.

The joint probability distribution is given by $$ P(H,T,L,B,C,D) = P(H)P(T)P(L|H,T)P(B|T)P(D|B,C) \, . $$

A main advantage of the use of Bayesian networks in this domain is the ability to estimate, share and fuse the local models among different hospitals without releasing sensitive patient data, with little overhead.

Jayasurya et al. developed a Bayesian Network to predict two-year survival ($S$) in lung cancer patients treated with radiotherapy (considered a continuous variable with observations 0 and 1).³ The model relied on clinical factors such as performance status ($W$), number of positive lymph nodes on a PET scan ($L$), clinical $T$-stage and $N$-stage, and size of gross tumor volume ($G$). All variables are continuous. Data about 322 patients from a single hospital was available, and contained a significant amount of missing values. For example, $W$ was missing in 11% of the cases. More importantly the model was validate on data of patients from different hospitals with higher rates of missing values. For instance, one of the hospital did not run PET scans (so $L$ was missing for all cases), and $G$ was missing in 15% of cases for another hospital. The structure of the network was estimated from data, with an initial solution encoding knowledge available in the medical literature. The resulting digraph is shown below.

The conditional distributions are specified as Gaussian distributions whose mean is a linear function of the values of the parents. The numbers on the arcs in the figure above denote the weights of the linear combination. This type of model is known as a Gaussian Bayesian Network. The mean and variances were learned from the data using the EM algorithm, which we will study later in the course. The authors reported higher prediction accuracy (using AUC) than an SVM classifier when missing values are replaced by their mean value.

Consider an artificial model of overall student performance connecting the number of registered students $R$ in a course, the ability of the teacher $T$ and the number of students $A$ that pass that course. The number of registered students depend on the teacher’s ability. The number of students who pass the course depends on both the number of registered students and the course’s difficulty. The structure of the Bayesian network is given below.

To obtain the conditional distributions, suppose that on average 50% of registered students are approved when the teacher’s ability is low, and that 70% are approved when the teacher’s ability is high. We can mode the conditional distribution of $A$ given $T$ and $S$ as a binomial distribution with the number of trials equals to $R$, and success probability $p=0.7$ if $A$ is high and $p=0.5$ if $A$ low. We can model $R$ as a Gaussian distribution with, say mean 40 and standard deviation 10, if the teacher ability is high, and mean 20 and standard deviation 20, if the teacher ability is low. And we can mode the teacher’s ability as a uniform random variable. Alternatively, we can assume $A$ is continuous and approximate its distribution as a Gaussian distribution with mean $\mu_\text{low} = 0.5R$ and variance $\sigma_\text{low}^2 = 0.25R$ if $T=\text{low}$ and $\mu_\text{high} = 0.7R$ and variance $\sigma_\text{high}^2 = 0.21R$ if $T=\text{high}$. This latter type of model is known as a conditional Gaussian Bayesian network. We can then use the model to answer questions such as what is the expected number of registered students in a course where $20$ students are approved?

A Naive Bayes Classifier (NBC) is a simple class of Bayesian networks formed by a single root variable and leaf nodes as children. Even though the assumptions made by the mode may seem unrealistic, they often lead to a competitive classifier for high dimensional domains with few data. The reason is that NBC can deliver fairly accurate classifications despite being a poor probability estimator due to its low variance (over data sets).⁴ To illustrate the use of the model, we build an NBC for spam detection of mobile messages, using a publicly available dataset. The root variable $C$ represents the message type (spam or ham) and the leaves $X_1,\dotsc,X_n$ indicate the presence or absence of selected keywords. NBC is based around the assumption that the attribute variables are conditionally independent given a class value: $$ P(X_1,\dotsc,X_n|C) = \prod_{i=1}^n P(X_i|C) \, . $$ The structure of NBC is shown below.

Typically, NBC is used to classify an object $x_1,\dotsc,x_n$ by selecting the value $c$ which maximizes the class posterior probability $P(C=c|x_1,\dotsc,x_n)$. The conditional probabilities are generally estimated by the relative counts from data: $P(X_i=x_i|C=c)=N(X_i=x_i,C=c)/N(C=c)$, where $N(X=x,C=c)$ denotes the number of instances (say, messages) of class $c$ where $X$ takes on value $x$, and $N(C=c) = \sum_x N(X=x,C=x)$. By taking the logarithm, and dispensing with terms that are constant with respect to the choice of class label, the maximum a posteriori class label can be found as: $$ \arg\max_c (1-n)\ln N(C=c) + \sum_{i=1}^n \ln N(X_i=x_i,C=c) \, . $$ Hence, classification takes linear time in the number of attributes and classes, and requires only simple computations, which leads to an extremely lightweight classifier.

To simplify matters, we select as keywords all words with at least 30 occurrences for some class. We preprocess the messages to include three special tokens indicating whether the message has a number, whether it has an upper case word, and whether it has a monetary amount. Here are some of the 227 keywords selected:

just with NUMBER come need what time about text cash reply nokia free when this there only like call home guaranteed ALLCAPS stop want from service know love today contact tone have urgent good please mobile MONEY prize customer claim your going still send will that then week mins dont sorry

We then obtain the relative frequencies (counts) of keywords in ham and spam messages, as well as the proportion of spam/ham messages. For example, the counts of the top 5 most frequent words in ham messages are:

that have ALLCAPS your will just when with what this

The top 5 most frequent words in spam messages:

ALLCAPS NUMBER call your MONEY free have from mobile stop

According to the model the probability of observing the word “winner” in a ham/spam message is: $$ P(X_\text{winner}=1|C=\text{ham})=0 \qquad P(X_\text{winner}=1|C=\text{spam})=0.021 \, . $$ The probability of observing ALLCAPS is: $$ P(X_\text{ALLCAPS}=1|C=\text{ham})=0.09 \qquad P(X_\text{ALLCAPS}=1|C=\text{spam})=0.90 \, . $$

We use the classifier to predict the labels for the same dataset used to estimate the counts (a biased approach), and obtain an accuracy of 98%.

A One-Dependence Bayesian Network Classifier (ODC) extends the Naive Bayes Classifier by allowing each attribute variable to depend also on a distinguished attribute called the superparent (which only depends on the class variable).⁵ An example of the structure of the network is represented below.

The conditional joint distribution of the model given the class is $$ P(X_1,\dotsc,X_n|C) = P(X_i|C) \prod_{j \neq i} P(X_j|X_i,C) \, . $$

The classifier is usually learned by comparing all models obtained with each attribute as superparent and selecting the one with highest score ( loglikelihood, accuracy, etc). Alternatively, one can dispense with the model selection and consider all possible ODC classifiers. A classification is then made by averaging the inferences of all classifiers. The result is called Average One-Dependence Classifier (AODC). The conditional joint distribution of AODC given the class is $$ P(X_1,\dotsc,X_n|C) = \frac{1}{n} \sum_{i=1}^n P(X_i|C) \prod_{j\neq i} P(X_j|X_i,C) , . $$ Note that the above joint distribution has no immediate Bayesian network representation, as it subsumes a cycle between attributes.

In multilabel classification each object is assigned to one or more relevant class labels. For example, an image can be associated with the objects it contains, and a text document can be associated with topics. Let $C_1,\dotsc,C_m$ denote the presence or absence of each label. A simple approach consists is the prediction of presence of each label as a separate classification problem, that is, to build a classifier for the domain $X_1,\dotsc,X_n,C_j$ for each $j=1,\dotsc,m$. While this approach often performs reasonably well, an explicit modeling of class dimension correlations can often improve accuracy (and particularly so if the accuracy measure takes class correlations into account). The naive Bayes classifier can be extended to multilabel classification by combining all single label naive Bayes classifiers into a single network. The result is the bipartite digraph below.

Note that not all arcs are present; some of the class to attribute arcs have been pruned by a feature selection procedure. According to the model, the attributes are conditionally independent given all class labels: $$ P(C_1,\dotsc,C_m,X_1,\dotsc,X_n) = \prod_i P(X_i|\pa{X_i}) \prod_{j=1}^m P(C_j) \, . $$

A similar model was used in the QMR-DT Bayesian network, that was support medical diagnoses of about 600 diseases (labels) and 4000 symptoms (attributes). The performance of the network was comparable to medical experts.⁶ A more accurate model can be obtained by also allowing dependences among class labels, and among attributes. Antonucci et al. developed a more sophisticated ensemble model where the subgraph of the class labels is an ensemble of Naive Bayes structures.⁷ By doing so they obtained a very competitive multilabel classifier.