The presence of uncertainty drastically changes the way an agent makes decision. At particular time an agent can have various available decisions, from which it has to make a choice. To make such choices an agent must have a preferences between the different possible outcomes, of the various plans.
A particular outcome is completely specified state, along with the expected factors related with the outcome.
For example: Consider a car driving agent who wants to reach at airport by a specific time say at 7.30 pm.
Here factors like, whether agent arrived at airport on time, what is the length of waiting duration at the airport are attached with the outcome.
Utility Theory
Utility theory is used to represent and reason with preferences. The term utility in current context is used as "quality of being useful".
Utility theory says that every state has a degree of usefulness called as utility. The agent will prefer the states with higher utility.
The utility of the state is relative to the agent for which utility function is calculated on the basis of agent's preferences.
For example: The pay-off functions for games are utility functions. The utility of a state in which black has won a game of chess is obviously high for the agent playing black and low for the agent playing white.
There is no measure that can count test or preferences. Someone loves deep chocolate icecream and someone loves chocochip icecream. A utility function can account for altruistic behavior, simply by including the welfare of other as one of the factors contributing to the agent's own utility.
Decision theory
Preferences as expressed by utilities are combined with probabilities for making rational decisions. This theory, of rational decision making is called as decision theory.
Decision theory can be summarized as, Decision theory = Probability theory + Utility theory.
The principle of Maximum Expected Utility (MEU) Decision theory says that the agent is rational if and only if it chooses the action that yields highest expected utility, averaged over all the possible outcomes of the action.
Design for a decision theoretic agent Following algorithm sketches the structure of an agent that uses decision theory to select actions.
The algorithm
Function: DT-AGENT (percept) returns an action. Static: belief-state, probabilistic beliefs about the current state of the world. Action, the agent's action.
Update belief-state based on action and percept Calculate outcome probabilities for actions, given actions descriptions and current belief-state Select action with highest expected utility given probabilities of outcomes and utility information Return action. A decision therotic agent that selects rational actions.
The decision theoretic agent is identical, at an abstract level, to the logical agent. The primary difference is that the decision theoretic agent's knowledge of the current state is uncertain; the agent's belief state is a representation of the probabilities of all possible actual states of the world.
As time passes, the agent accumulates more evidence and its belief state changes. Given the belief state, the agent can make probabilistic predictions of action outcomes and hence select the action with highest expected utility.
The Basic Probability Notation
The probability theory uses propositional logic language with additional expressiveness.
The probability theory uses represent prior probability statements, which apply before any evidence is obtained. The probability theory uses conditional probability statements which include the evidence explicitly.
Propositions
The propositions (assertions) are attached with the degree of belief. v Complex proposition can be formed using standard logical connectives. For example: [(Cavity = True) ∧ (Toothache = False)] and [(Cavity ∧ ¬ Toothache )] both are same assertions.
The random variable
The basic element of language is random variable. v It refers to a "part" of the world whose "status" is initially unknown. For example: In toothache problem 'cavity' is a random variable which can refer to my left wisdom tooth or right wisdom tooth.
Random variables are like symbols in propositional logic.
Random variables are represented using capital letters. Whereas unknown random variable can be represented with lowercase letter. For example: P (a) = 1 - P ( ¬a)
Each random variable has a domain of values that it can take on. That is domain is, set of allowable values for random variable. For example: The domain of cavity can be < true, false >
A random variable's proposition will assert that what value is drawn for the random variable from its domain. For example: Cavity = True is proposition. Saying that "there is cavity in my lower left wisdom tooth".
Random variables are divided into three kinds, depending on their domain. The types are as follows.
Boolean random variables: These are random variables that can take up only boolean values. For example: Cavity, it takes value either true or false.
Discrete random variables: They take values from countable domain. They also include boolean domain. The values in the domain must be mutually exclusive and exhaustive (finite). For example: Weather, it has domain < sunny, rainy, cloudy, cold >
Continuous random variables: They take values from real numbers. The domain can be either entire real line or subset of it like intervals [2, 3]. For example : 𝑋 = 4.14 asserts that 𝑋 has exact value 4.14 Propositions having continuous random variable can have inequalities like 𝑋 ≤
4.14.
Atomic Events
An atomic event is a complete specification of the state of the world about which agent is uncertain. v They are represented as variables. These variables are assigned values from the real world. For example: If the world is consists of cavity and Toothache then there are four distinct atomic events,
a) Cavity = False ∧ Toothache = True b) Cavity = False ∧ Toothache = False c) Cavity = True ∧ Toothache = False d) Cavity = True ∧ Toothache = True e) Properties of atomic events v They are mutually exclusive-That is at most one can actually be the case. For example: (Cavity ∧ Toothache) and (Cavity ∧ ¬ Toothache) can not both be the case. v The set of all possible atomic events is exhaustive out of which at least one must be the case. That is, the disjunction of all atomic events is logically equivalent to true. v Any particular atomic event entails the truth or falsehood of every proposition, whether simple or complex. For example-The atomic event (Cavity ∧ ¬ Toothache) entails the truth of cavity and the Falsehood of (cavity →
toothache).
Any proposition is logically equivalent to the disjunction of all atomic events that entail the truth of the proposition.
For example: The proposition cavity is equivalent to disjunction of the atomic events (cavity ∧ toothache) and (cavity ∧ ¬ toothache).
Prior Probability (Unconditional Probability)
The prior (unconditional) probability is associated with a proposition ' 𝑎 '. v It is the degree of belief accorded to a proposition in the absence of any other information. v It is written as P(a). For example: The probability that, Ram has cavity = 0.1, then prior probability is written as, P( Cavity = true ) = 0.1 or P( Cavity ) = 0.1
-
It should be noted that as soon as new information is received, one should reason with the conditional probability of 'a' depending upon new information.
-
When it is required to express probabilities of all the possible values of a random variable, then a vector of values is used. It is represented using 𝐏(𝐚). This represents values for the probabilities of each individual state of the 'a'. For example: 𝐏( Weather ) =< 0.7,0.2,0.08,0.02 > is representing four equations
𝑃( Weather = Sunny ) = 0.7 𝑃( Weather = Rain ) = 0.2 𝑃( Weather = Cloudy) = 0.08 𝑃( Weather = Cold ) = 0.02
The expression P(a) is said to be defining prior probability distribution for the random variable 'a'. v To denote probabilities of all random variables combinations, the expression P(a₁, a₂) can be used. This is called as joint probability distribution for random variables a₁, a₂. Any number of random variables can be mentioned in the expression. v A simple example of joint probability distribution is, →𝐏< Weather, Cavity > can be represented as, 4 × 2 table of probabilities. (Weather's probability) (Cavity probability) v A joint probability distribution that covers the complete set of random variables is called as full joint probability distribution.
A simple example of full joint probability distribution is, If problem world consists of 3 random variables, whether, cavity, toothache then full joint probability distribution would be, 𝐏 < Weather, Cavity, Toothache> It will be represented as, 4 × 2 × 2, table of probabilities.
Prior probability for continuous random variable
i) For continuous random variable it is not feasible to represent vector of all possible values because the values are infinite. For continuous random variable the probability is defined as a function with parameter x, which indicates that random variable takes some value x. For example: Let random variable 𝑥 denotes the tomorrow's temperature in Chennai. It would be represented as, P(X = x) = U25 − 37.
This sentence express the belief that 𝑋 is distributed uniformly between 25 and 37 degrees celcius.
ii) The probability distribution for continuous random variable has probability density function.
3.7 Probabilistic Reasoning
Probability based reasoning is the same as inferring directly from knowledge that can be given a probability rating based on the amount of uncertainty present. The uncertainties can arise from an inability to predict outcomes due to unreliable, vague incomplete or inconsistent knowledge. The probability of an uncertain event is a measure of the degree of likelihood of occurrence of that event.
When one takes it for granted that certain parameters exist or known with certainty, solutions can be found out. Belief revision takes place whenever one encounters a piece of information that decreases the belief of the fact.
The source for all uncertainties is the real world. The following sources constitute the major causes of uncertainties,
Most information is not obtained personally but got from sources on which one has a lot of belief. Uncertainty prevails when the source does not send information in time or the information provided is not understood.
In laboratory, experiments one takes it for granted that the equipment is properly
calibrated and error free. If the equipment is faulty, the picture one gets about the situation is not correct which leads to uncertainty.
Experimental errors like parallax errors are also sources of uncertainty.
Imprecision in natural language is also a source of uncertainty.
A random event occurring is a major source of uncertainty.
In judicial courts one may have seen or heard delivering judgements acquitting the accused for,
Ø Lack of evidence
Lack of certainty in evidence thereby giving the benefit of doubt to the accused.
To handle these uncertain data, probability is the oldest technique available. Probabilistic reasoning is sometimes used when outcomes are unpredictable. For example, when a physician examines a patient, the patient's history, symptoms and test results provide some, but not conclusive evidence of possible ailments. This knowledge, together with the physician's experience with previous patients, improves the likelihood of predicting the unknown event, but there is still much uncertainty in most diagnoses.
One way to express confidence about such event is through probability. It is a mere number that expresses the chance of something happening or not happening.
Representing knowledge in uncertain domain
Independence and conditional independence relationships among variables can greatly reduce the number of probabilities that need to be specified in order to define the full joint distribution. There is technique called as Bayesian Network which can be used to represent the dependencies among variables and to give a concise specification of any full joint probability distribution.
Bayesian Network
Definition
It is a data structure which is a graph, in which each node is annotated with quantitative probability information.
The nodes and edges in the graph are specified as follows,
A set of random variables makes up the nodes of the network. Variables may be discrete or continuous.
A set of directed links or arrows connects pairs of nodes. If there is an arrow from node 𝑋 to node 𝑌, then 𝑋 is said to be a parent of 𝑌. v Each node 𝑋𝑖, has a conditional probability distribution 𝑃(𝑋𝑖 ∣ Parents (𝑋𝑖)) that quantifies the effect of the parents on the node. v The graph has no directed cycles (and hence is a directed, acyclic graph, or DAG). The set of nodes and links is called as topology of the network. The topology of the network specifies the conditional independence relationships that hold in the domain.
The intuitive meaning of an arrow between two nodes X and Y, in a properly constructed network, is that "X has direct influence on Y". The domain expert is a person who can identify such influence associations.
Once Bayesian network topology is specified then conditional probability distribution for each variable is specified. For specifying continuous probability distribution for a variable, its parent information is required.
The combination of topology and the conditional distributions is sufficient to specify the full joint distribution for all the variables.
Consider our example of simple world consisting of variables toothache, cavity, catch and weather. Weather is surly independent of other variables. Toothache and Catch are conditionally independent if given the information of cavity.
This relationships are represented by Bayesian network as shown below,
Fig. 3.25 A simple Bayesian network in which Weather is independent of other three
variables and Toothache and Catch are conditionally independent, given the cavity.
Note
The conditional independence of toothache and catch given the cavity is indicated by the absence of a link between toothache and catch. v The network represents the fact that cavity is a direct cause of toothache and catch. v No direct causal relationship exists between toothache and catch. Consider another example of burglar alarm installed at A's home. This alarm notifies in case of burglary and can occasionally respond to minor earthquakes. There are two neighbours to A, M and J. M and J promised to call A in office when they hear alarm. J always calls A when
he hears alarm, but many times he is confused between telephone ring and burglar alarm. M many a times misses alarm because he keeps on listening to loud music. Given the evidence of who has or has not called, we are to estimate the probability of burglary.
The Bayesian network for above problem along with the associated probabilities is shown below,
Fig. 3.26 A Typical Bayesian network, showing both the topology and the conditional probability tables (CPTs).
Note: In the figure, in the CPTs, the letters B, E, A, J and M stand for Burglary, Earthquake,
Alarm, Johncalls, Marycalls respectively.
In the figure, each distribution is shown as conditional probability table. Each row in the table contains the conditional probability of each node value for a conditioning case. A conditioning case is just a possible combination of values for the parent nodes. Each row must sum upto 1 because the entries represent an exhaustive set of cases for the variable. v For boolean variable if it is true and its probability is know to be ' P ' then when it is false its probability is 1 − P and it is ommited from the table (because it can be deduced from ' P '). v A table for a boolean variable with 𝑘 boolean parents contains 2𝑘 independently specifiable probabilities. A node with no parents has only one row, representing the prior probabilities of each possible value of the variable. The Semantics of Bayesian Networks
There are two ways through which semantic (meaning) of Bayesian network can be understood.
One way is to view network as a representation of the joint probability distribution. This view helps to constructs networks. Second way is to view a network as an encoding of a collection
of conditional independence statements. This view helps in designing inference procedure semantically both views are equivalent.
Understanding semantic of Bayesian network method,
Representing the full joint distribution
Every entry in the full joint probability distribution (hereafter abbreviated as "joint") can be calculated from the information in the network. v A generic entry in the joint distribution is the probability of a conjunction of particular assignments to each variable, such as P(X₁ = x₁ ∧….…Xn = xn) v The notation 𝑃(𝑥₁, …., 𝑥𝑛) is used as an abbrevation for this. v The value of this entry is given by the formula.
P(x₁, …., xn)=∏𝑛i=1P (xi ∣ parents (Xi)) (1)
Where, parents (𝑥𝑖) denotes the specific values of the variables in parents (𝑥𝑖).
Thus, each entry in the joint distribution is represented by the product of the appropriate elements of the Conditional Probability Tables (CPTs) in the Bayesian network. The CPTs therefore, provide a decomposed representation of the joint distribution. We can calculate the probability that the alarm has sounded, but neither a burglary nor an earthquake has occurred and both J and M call. We use single letter names for the variables:
P(j ∧ m ∧ a ∧ ¬ b ∧ ¬e) = P(j ∣ a)P( m ∣ a)P(a ∣ ¬b ∧ ¬e)P(¬ b)P(¬e) = 0.90 × 0.70 × 0.001 × 0.999 × 0.998 = 0.00062
Remember that the full joint distribution can be used to answer any query about the domain. If a Bayesian network is a representation of the joint distribution, then it too can be used to answer any query, by summing all the relevant joint entries.
A method for constructing Bayesian network
We rewrite the joint distribution in terms of a conditional probability, using the product rule. P(x₁, …., xn) = P(xn ∣ xn−1, …, x₁)P(xn−1, …, x₁).
Then the process is represented, reducing each conjunctive probability to a conditional probability and a smaller conjunction. We end up with one big product. P(x₁, …., xn) = P(xn ∣ xn−1, …., x₁)P(xn−1 ∣ xn−2, …., x₁) …. P(x₂ ∣ x₁)P(x₁) v = ∏n) i=1P(xi ∣ xi−1, … x₁
Above identity holds true for any set of random variables and is called the Chain rule. Comparing it with equation (1). We see that the specification of the joint distribution is equivalent to the general assertion that, for every variable 𝑋𝑖 in the network, 𝐏(𝑋𝑖 ∣ 𝑋𝑖−1,….𝑋₁) = 𝐏(𝑋𝑖 ∣ Parents(𝑋𝑖))
provided that parents (𝑋𝑖) ⊆ {𝑋𝑖−1,….𝑋₁}. This last condition is satisfied by labeling the nodes in any order that is consistent with the partial order implicit in the graph structure.
- Bayesian network is correct representation of the domain only if each node is conditionally independent of its predecessors in the node ordering, given its parents.
- In order to construct a Bayesian network with the correct structure for the domain, we need to choose parents for each node such that this property holds. Intuitively, the parents of node 𝑋𝑖 should contain all those nodes in 𝑋𝑖,….𝑋𝑖−1 that directly influence 𝑋𝑖. For example : Suppose we have completed the network in Fig. 3.26 except for the choice of parents for M calls, M calls is certainly influenced by whether there is a burglary or an earthquake, but not directly influenced. Institutively, our knowledge of the domain tells us that these events influence M's calling behaviour only through their effect on the alarm. Also given the state of the alarm, whether J calls has no influence on M's calling. Formally speaking, we believe that the following conditional independence statement holds, 𝐏(M Calls |J Calls, Alarm, Earthquake, Burglary) = P(M calls | Alarm).
Compactness and node ordering
Bayesian network are compact and they possess a property of being locally structured (also called as sparse systems). In a locally structured system, each sub component interacts directly with only a bounded number of other components, regardless of the total number of components.
Local structure is usually associated with linear rather than exponential growth in complexity.
We assume ' 𝑛 ' boolean variables for simplicity, then the amount of information needed to specify each conditional probability table will be at most 2𝑘 numbers. Where each random variable is influenced by ' k ' other variables.
The complete network can be specified by n2k numbers.
With some values of ' 𝑛 ' the joint distribution contains 2n numbers.
To make this concrete, suppose we have n = 30 nodes, each with five parents (k = 5 ). Then the Bayesian network requires 960 numbers, but the full joint distribution requires over a billion.
Ordering of nodes in Bayesian network
The correct order in which to add nodes is to add the "root causes" first, then the variables they influence, and so on, until we reach the "leaves", which have no direct causal influence on the other variables. v If wrong order is chosen we get more complicated network. For example: Consider network shown in following diagram.
The network construction process goes as follows,
v Adding M calls: No parent.
Adding J calls: If M calls, that probably means the alarm has gone off, which of course would make it more likely that J calls. Therefore J calls needs M calls as a parent.
Adding alarm: Clearly, if both call, it is more likely that the alarm has gone off than if just one or neither call, so we need both M calls and J calls as parent.
Adding burglary: If we know the alarm state, then the call from J or M might give us information about phone ringing or M's music, but not about burglary : 𝐏 (Burglary |Alarm, J calls, M calls) = P(Burglary |Alarm).
Hence we need just alarm as parent.
Fig. 3.27 and Fig. 3.28 Network structure depends on order of introduction. In each
network nodes are added from top to bottom.
Adding earthquake: If the alarm is on, it is more likely that there has been an earthquake. (The alarm is an earthquake detector of sorts). But if we know that there has been a burglary, then that explains the alarm, and the probability of an earthquake would be only slightly above normal. Hence, we need both Alarm and Burglary as parents. The network is shown below.
Consider example of a very bad node ordering as shown in the Fig. 3.28 M calls, J calls, Earthquake, Burglary, Alarm are nodes. This network requires 31 distinct probabilities to be specified exactly the same as the full joint distribution. It is important to realize, however, that any of the three networks can represent exactly the same joint distribution. The last two versions simply fail to represent all conditional independence relationships and hence end up specifying a lot of unnecessary numbers instead.
Conditional Independence Relations in Bayesian Networks
One can start from a "topological" semantics that specifies the conditional independence relationships encoded by the graph structure, and from these we can derive the "numerical" semantics. The topological semantics is given by either of the following specifications, which are equivalent.
- A node is conditionally independent of its non-descendants, given its parents. For example, in Fig. 3.26 J calls is independent of Burglary and Earthquake, given the value of Alarm.
- A node is conditionally independent of all other nodes in the network, given its parents, children, and children's parents-that is, given its Markov blanket. For example: Burglary is independent of J calls and M calls given Alarm and Earthquake. Fig. 3.29 (a) A node 𝒙 is conditionally independent of its non-descendants. (e.g., the
𝐙𝐢𝐣𝐬**) given its parents (the** 𝐔𝐢𝐬 shown in the gray area).
This specifications are illustrated in following figures. From these conditional independence assertions and the CPTs, the full joint distribution can be reconstructed; thus the "numerical" semantics and the "topological" semantics are equivalent.
A node 𝑋 is conditionally independent of its non-descendants (example-The 𝑍1𝑗𝑠) given its parents ( the 𝑈𝑖 is shown in the gray area).
Fig. 3.29 (b) A node 𝒙 is conditionally independent of all other nodes in the network
given its markov blanket (the gray area).
A node 𝑋 is conditionally independent of all other nodes in the network given its Markove blanket ( the gray area).
Efficient representation of conditional representation
If the maximum number of parents k is smallish, filling in the CPT for a node, would require up to O(2k) numbers.
To avoid this big relationship number canonical distribution is used. In this a complete table is specified by naming the patterns supplied with parameters, which can describe relationship which are necessary. A deterministic node represents canonical distribution. A deterministic node is a node whose value is exactly specified by the value of its parents with no uncertainity.
The uncertain relationships are often represented by noisy-OR relationships. [Noisy-OR is generalization of logical OR]. The noisy-OR model allows uncertainity about the parent to cause the child to be true i.e. the causal relationship between parent and child would be inhibited.
For example: A patient could have cold (parent) but not exhibit a fever (child). For noisy-OR model it is required that all the possible effects of parent must be listed. It should be clear that inhibition of one parent is independent of other parent.
The Hybrid Bayesian Network
A network with both discrete and continuous variables is called as hybrid Bayesian network. For representing continuous variable its discretization is done in terms of intervals (because it can have infinite values).
To specify a hybrid network, we have to specify two new kinds of distributions. The conditional distribution for a continuous variable given discrete or continuous parents; and the conditional distribution for a discrete variable given continuous parents.
Consider the simple example in following diagram, in which a customer buys some fruit depending on its cost, which depends in turn on the size of the harvest and whether the government's subsidy scheme is operating. The variable Cost is continuous and has continuous and discrete parents; the variable Buys is discrete and has a continuous parent.
For the cost variable, we need to specify 𝐏( Cost ∣ Harvest, Subsidy). The discrete parent is handled by explicit enumeration that is, specifying both P( Cost ∣ Harvest, Subsidy) and 𝐏 (Cost|Harvest, ¬ Subsidy). To handle Harvest, we specify how the distribution over the cost 'c' depends on the continuous value ' ℎ ', of Harvest. In other words, we specify the parameter of the cost distribution as a function of ' ℎ '.
Fig. 3.30 A simple network with discrete variables (Subsidy and Buys) and continuous variables (Harvest and Cost).
Inferencing in Bayesian Networks
Exact Inference in Bayesian Networks
For inferencing in probabilistic system, it is required to calculate posterior probability distribution for a set of query variables, where some observed events are given. [That is we have some values attached to evidence variables].
Notation Revisited
The notation used in inferencing is same as the one used in probability theory. 𝑋: Query variable.
E: The set of evidence variables E₁,….,E𝑚 and 'e' is the particular observed event.
Y: The set of non-evidence variables Y₁, Y₂,….Yk [Non-evidence variables are also called as hidden variables].
𝑋: It the complete set of all the types of variables, where 𝑋 = {𝑋} ∪ 𝐸 ∪ 𝑌.
Generally the query requires the posterior probability distribution 𝐏(𝑋 ∣ 𝑒) [assuming that query variable is not among the evidence variables, if it is, then posterior distribution for X simply gives probability 1 to the observed value]. [Note that query can contain more than one variable. For study purpose we are assuming single variable]. Example: In the burglary case, if the observed event is Jcalls = true and Mcalls = true. The query is 'Has burglary occurred?' The probability distribution for this situation would be,
P( Burglary ∣ J calls = true, M calls = true) =< 0.284,0.716 >
Inference by Enumeration
A Bayesian network gives a complete representation of the full joint distribution. These full joint distributions can be written as product of conditional probabilities from the Bayesian network.
A query can be answered using Bayesian network by computing sums of products of conditional probabilities from the network.
The algorithm
The algorithm ENUMERATE-JOINT-ASK gives inference by enumerating on full joint distribution.
Characteristics of algorithm
It takes input a full joint distribution 𝑃 and looks up values in it. [The same algorithm can be modified to take input as Bayesian network and looking up in joint entries by multiplying the corresponding conditional probability table entries from Bayesian network. v The ENUMERATION-JOINT-ASK uses ENUMERATION-ASK (EA) algorithm which evaluate expression using depth-first recursions. Therefore, the space complexity of EA is only linear in the number of variables. The algorithm sums over the full joint distribution without ever constructing it explicitly. The time complexity for network with ' 𝑛 ' boolean variables is always 𝑂(2𝑛) which is better than the O(n2n) required in simple inferencing approach (using posterior probability). v The drawback of the algorithm is, it keeps on evaluating repeated sub expression which results in wastage of computation time. The enumeration algorithm for answering queries on Bayesian network.
The algorithm
Function ENUMERATION-ASK ( X, e, bn) returns a distribution over X.
Inputs: 𝑋, the query variable e, observed values for variables E. bn, a Bayes net with variables {X} ∪ E ∪ Y/ ∗y = Hidden variable */
𝑄(𝑥) ← A distribution over 𝑋, initially empty for each value 𝑥𝑖 of 𝑋 do extend 𝑒 with value 𝑥𝑖 for 𝑋.
Q(xi) ← ENUMERATE-ALL (VARS[bn] e) return NORMALIZE ( Q(x) ).
Function ENUMERATE-ALL (vars, e) returns a real number.
if EMPTY ? (vars) then return 1.0
Y ← FIRST (vars)
If Y has value y in e.
Then return P(y ∣ parents (Y))X ENUMERATE-ALL (REST(vars), e)
else return ∑yP(y ∣ parents( Y))X ENUMERATE-ALL (REST(vars), ey)
where, 𝑒𝑦 is e extended with 𝐘 = 𝐲.
Example
Consider query, 𝐏 (Burglary ∣ J calls = true, M calls = true) Hidden variables in the queries are → Earthquake and Alarm. using the query equation. 𝐏( Burglary ∣ 𝑗, 𝑚) = 𝛼𝐏( Burglary, 𝐽, 𝑀) = 𝛼∑𝑒 ∑𝑎𝐏( Burglary, 𝑒, 𝑎, 𝑗, 𝑚)
The semantics of Bayesian networks (equation 8.2.1) then gives us an expression in terms of CPT entries. For simplicity, we will do this just for Burglary = true.
𝑃(𝑏 ∣ 𝑗, 𝑚) = 𝛼 ∑ ∑ 𝑃(𝑏)𝑃(𝑒)𝑃(𝑎 ∣ 𝑏, 𝑒)𝑃(𝑗 ∣ 𝑎)𝑃(𝑚 ∣ 𝑎) 𝑒 𝑎
To compute this expression, we have to add four terms, each computed by multiplying five numbers. v Worst case, where we have to sum out almost all the variables, the complexity of the algorithm for a network with n boolean variables is O(n2n). v An improvement can be obtained from the following simple observations. The P(b) term is a constant and can be moved outside the summations over a and e, and the P(e) term can be moved outside the summation over a. Hence, we have 𝑃(𝑏 ∣ 𝑗, 𝑚) = 𝛼𝑃(𝑏) ∑𝑒 𝑃(𝑒) ∑𝑎 𝑃(𝑎 ∣ 𝑏, 𝑒)𝑃(𝑗 ∣ 𝑎)𝑃(𝑚, 𝑎) (2)
This expression can be evaluated by looping through the variables in order, multiplying CPT entries as we go. For each summation, we also need to loop over the variable's possible values. The structure of this computation is shown in following diagram. Using the numbers from
Fig. 3.26, we obtain P(b ∣ j, m) = 𝛼 × 0.00059224. The corresponding computation for ¬b
yields 𝛼 × 0.0014919;
Hence,
P( B ∣ j, m) = 𝛼 < 0.00059224,0.0014919 > ≈< 0.284,0.716 >
That is, the chance of burglary, given calls from both neighbours is about 28%.
Fig. 3.31 The structure of the expression shown in equation (2).
Note: In the Fig. 3.31, the evaluation proceeds top to down, multiplying values along each
path and summing at the "t" nodes. Observe that there is repetition of paths for 𝑗 and 𝑚.
The Variable Elimination Algorithm
The enumeration algorithm can be improved substantially by eliminating calculations of repeated sub expression in tree. Calculation can be done once and save the results for later use. This is a form of dynamic programming.
Working of variable elimination algorithm
-
It works by evaluating expressions such as [P(b ∣ j, m) = 𝛼P(b)∑eP(e) ∑P(a ∣ b, e)P(j ∣ a)P(m ∣ a)] in right-to-left order. ∑𝑎𝑃(𝑎 ∣ 𝑏, 𝑒)𝑃(𝑗 ∣ 𝑎)𝑃(𝑚 ∣ 𝑎)] in right-to-left order.
-
Intermediate results are stored and summations over each variable are done only for those portions of the expression that depends on the variable. For example: Consider the Burglary network. We evaluate the expression : 𝑃(𝐵 ∣ 𝑗, 𝑚) = 𝛼𝑃 ⏟ (𝐵) ∑ 𝑃𝐸𝑃(𝑒) ∑ 𝑃⏟(𝑎 ∣ 𝐵, 𝑒) 𝑃⏟(𝑗 ∣ 𝑎) 𝑃⏟(𝑚 ∣ 𝑎) 𝐵 𝑒 𝐴 E 𝑀
-
Factors: Each part of the expression is annotated with the name of the associated variable, these parts are called factors.
Steps in algorithm
i) The factor for M, P(m ∣ a), does not require summing over M. Probability is stored, given each value of a, in a two-element factor, P( m ∣ a) fM( A) = [] P( m ∣ ¬a)
Note: fM means that M was used to produce f.
ii) Store the factor for 𝐽 as the two-element vector 𝑓𝐽(𝐴).
ii) The factor for A is P(a ∣ B, e) which will be a 2 × 2 × 2 matrix fA(A, B, E).
iv) Summing out A from the product of these tree factors. This will give 2 × 2 matrix whose indices range over just B and E. We put bar over A in the name of the matrix to indicate that A has been summed out.
fAM( B, E) = ∑ fA(a, B, E) × fJ(a) × fM(a) a = fA(a, B, E) × fJ(a) × fM(a) + fA(¬a, B, E) × fJ(¬a) × fM(¬a)
The multiplication process used is called a pointwise product.
v) Processing E in the same way (i.e.) sum out E from the product of fE(E) and fAJM(B, E) : fA𝐽M( B) = fE(e) × fA𝐽M( B, e) + fE(¬e) × fA/M( B, ¬e).
vi) Compute the answer simply by multiplying the factor for B. (i.e.) (𝑓𝐵 ∣ 𝐵) = 𝑃(𝐵), by the accumulated matrix (B) :
𝑃(𝐵 ∣ 𝑗, 𝑚) = 𝛼𝑓𝐵(𝐵) × 𝑓𝐸‾ 𝐴‾𝐽𝑀(𝐵).
From the above sequence of steps it can be noticed that two computational operations are required.
a) Pointwise product of a pair of factors. b) Summing out a variable from a product of factors. a) Pointwise product of a pair of factors: The pointwise product of two factors 𝑓₁ and 𝑓₂ yields a new factor 𝑓, those variables are the union of the variables in 𝑓₁ and 𝑓₂. Suppose the two factors have variables 𝑌₁,….,𝑌𝑘. Then we have 𝑓(𝑋₁,…,𝑋𝑗, 𝑌₁,….𝑌𝑘, 𝑍₁,…..𝑍𝑙) = 𝑓₁(𝑋₁,….𝑋𝑗, 𝑌₁ … 𝑌𝑘)𝑓₂(𝑌₁,…..𝑌𝑘, 𝑍₁,….𝑍𝑙). If all the variables are binary, then 𝑓₁ and 𝑓₂ have 2𝑗+𝑘 and 2𝑘+𝑙 entries and the pointwise product has 2j+k+𝑙 entries. For example : Given two factors 𝑓₁(𝐴, 𝐵) and 𝑓₂(𝐵, 𝐶) with probability distributions shown below, the pointwise product 𝑓₁ × 𝑓₂ is given as 𝑓₁(𝐴, 𝐵, 𝐶).
| 𝐀 | B | 𝐟₁ (𝐀, 𝐁) | B | C | 𝐟₂ (𝐁, C) | A | B | C | f₃ (A, B, C) |
|---|---|---|---|---|---|---|---|---|---|
| T | T | .3 | T | T | .2 | T | T | T | . 3 × .2 |
| T | F | .7 | T | F | .8 | T | T | F | . 3 × .8 |
| F | T | .9 | F | T | .6 | T | F | T | . 7 × .6 |
| F | F | .1 | F | F | .4 | T F F F F | F T T F F | F T F T F | . 7 × .4. 9 × .2. 9 × .8. 1 × .6. 1 × .4 |
b) Summing out a variable from a product of factors: It is a straight forward computation. Any factor that does not depend on the variable to be summed out can be moved outside the summation process. For example: ∑ 𝑓𝐸(𝑒) × 𝑓𝐴(𝐴, 𝐵, 𝑒) × 𝑓𝐽(𝐴) × 𝑓𝑀(𝐴) = 𝑓𝐽(𝐴) × 𝑓𝑀(𝐴) × ∑ 𝑓𝐸(𝑒) × 𝑓𝐴(𝐴, 𝐵, 𝑒). 𝑒 𝑒 Now, the pointwise product inside the summation is computed and the variable is summed out of the resulting matrix. 𝑓𝐽(𝐴) × 𝑓𝑀(𝐴) × ∑ 𝑓𝐸(𝑒) × 𝑓𝐴(𝐴, 𝐵, 𝑒) = 𝑓𝐽(𝐴) × 𝑓𝑀(𝐴) × 𝑓𝐸𝐴(𝐴, 𝐵). 𝑒
Matrices are not multiplied until we need to sum but a variable from the accumulated product. At that point, multiply those matrices that include the variable to be summed out.
The procedure for pointwise product and summing is as follows, the variable elimination algorithm is as follows:
Function ELIMINATION-ASK ( X, e, bn ) returns a distribution over X Inputs: X, the query variable
e, evidence specified as an event bn, a Bayesian network specifying joint distribution 𝑃(𝑋₁,…,𝑋𝑛). Factors ← [] : vars ← REVERSE (VARS [bn]) for each var in vars do Factors ← [MAKE-FACTOR (var, e) factors] if var is a hidden variable then Factors ← SUM-OUT (var, factors) returns NORMALIZE (POINTWISE-PRODUCT (factors)).
P(J calls, Burglary = True) The first step is to write out the nested summation.
P( J ∣ b) = 𝛼P( b) ∑ P(e) ∑ P(a ∣ b, e)P( J ∣ a) ∑ P(M ∣ a). e a m
Evaluating this expression from right to left, ∑mP(M ∣ a) is equal to 1.
Note: The variable M is irrelevant to this query. Result of the query P(J calls/Burglary = True
) is unchanged if we remove M calls from the network. We can remove any leaf node which is not a query variable or an evidence variable. After its removal, there may be more leaf nodes and they may be irrelevant. Eventually we find that every variable that is not an ancestor of a query variable or evidence variable is, irrelevant to the query. A variable elimination algorithm can remove all these variables before evaluating the query.
The Complexity Involved in Exact Inferencing
The variable elimination algorithm is more efficient than enumeration algorithm because it avoids repeated computations as well as drops irrelevant variables.
The variable elimination algorithm constructs the factor, deriving its operation. The space and time complexity of variable elimination is directly dependant on size of the largest factor constructed during the operation. Basically the factor construction is determined by the order of elimination of variables and by the structure of the network; which affects both space and time complexity.
For developing more efficient process we can construct singly connected networks which are also called as polytrees. In singly connected network, there is at most one undirected path between any two nodes in the networks. The singly connected networks have property that, the time and space complexity of exact inference in polytrees is linear in the size of the network. Here the size is defined as the number of CPT entries. If the number of parents of each node is bounded by a constant, then the complexity will also be linear in the number of nodes.
For example: The Burglary network shown in the Fig. 3.26 is a polytrees. [Note that every problem may not be represented as polytrees].
In multiply networks [In this, their can be multiple undirected paths between any two nodes and more than one directed path between some pair of nodes], variable elimination takes exponential time and space complexity in the worst case, even when the number of parents per node is bounded. It should be noted that variable elimination includes inference in propositional logic as a special case and inference in Bayesian network is NP-hard. In fact it is strictly harder than NP-complete problem.
Clustering algorithm
- Clustering algorithm (known as joint tree algorithms) in which inferencing time can be reduced to O(n). In clustering individual nodes of the network are joint to form cluster nodes to such a way that the resulting network is a polytree.
- The variable elimination algorithm is efficient algorithm for answering individual queries. Posterior probabilities are computed for all the variables in the network. It can be less efficient, in polytree network because it needs to issue 𝑂(𝑛) queries costing 𝑂(𝑛) each, for a total of 𝑂(𝑛²) time, clustering algorithm, improves over it. Fig. 3.32 (a) A multiply connected network with conditional probability tables.
For example: The multiply connected network shown in Fig. 3.32 (a) can be converted into a polytree by combining the Sprinkler and Rain node into a cluster node called Sprinkler + Rain, as shown in Fig. 3.32 (b). The two Boolean nodes are replaced by a mega node that takes on four possible values: TT, TF, FT, FF. The mega node has only one parent, the Boolean variable. Cloudy, so there are two conditioning cases.
Fig. 3.32 (b) A clustered equivalent of the multiply connected network.
Peculiarities of algorithm
Once the network is in polytree form, a special-purpose inference algorithm is applied. Essentially, the algorithm is a form of constraint propagation where the constraints ensure that neighbouring clusters agree on the posterior probability of any variables that they have in common. v With careful book keeping, this algorithm is able to compute posterior probabilities for all the non-evidence nodes in the network in time 𝑂(𝑛), where 𝑛 is now the size of the modified network. v However, the NP-hardness of the problem continues: if a network requires exponential time and space with variable elimination, then the CPTs in the clustered network will require exponential time and space to construct.