UNIT 5

UNCERTAIN KNOWLEDGE AND PROBABILISTIC REASONING

ACTING UNDER UNCERTAINTY

AI deals with uncertainty by using models and methods that assign probabilities to different outcomes.
Managing uncertainty is important for AI applications like self-driving cars and medical diagnosis, where
safety and accuracy are key.
Uncertainty:
o We have learned knowledge representation using first-order logic and propositional logic
with certainty, which means we were sure about the predicates.
o With this knowledge representation, we might write A→B, which means if A is true then B is
true, but consider a situation where we are not sure about whether A is true or not then we
cannot express this statement, this situation is called uncertainty.
o So, to represent uncertain knowledge, where we are not sure about the predicates, we need
uncertain reasoning or probabilistic reasoning.
Causes of uncertainty:
Following are some leading causes of uncertainty to occur in the real world.
1. Information occurred from unreliable sources.
2. Experimental Errors
3. Equipment fault
4. Temperature variation
5. Climate change.
“Uncertainty in artificial intelligence (AI) refers to the lack of complete information or the presence of
variability in data and models”.

Sources of Uncertainty in AI
Uncertainty
Data Model Human Ethical
in AI
Uncertainty Uncertainty Uncertainty Uncertainty
Reasoning

There are several sources of uncertainty in AI that can impact the reliability and effectiveness of AI
systems. Here are some common sources of uncertainty in AI:
1. Data Uncertainty: AI models are trained on data, and the quality and accuracy of the data can affect
the performance of the model. Noisy or incomplete data can lead to uncertain predictions or
decisions made by the AI system.
2. Model Uncertainty:
3. AI models are complex and can have various parameters and hyperparameters that need to be tuned.
The choice of model architecture, optimization algorithm, and hyperparameters can significantly
impact the performance of the model, leading to uncertainty in the results.
4. Human Uncertainty: AI systems often interact with humans, either as users or as part of the decision-
making process. Human behavior and preferences can be difficult to predict, leading to uncertainty in
the use and adoption of AI systems.
5. Ethical Uncertainty: AI systems often raise ethical concerns, such as privacy, bias, and transparency.
These concerns can lead to uncertainty in the development and deployment of AI systems,
 particularly in regulated industries.
6. Uncertainty in AI Reasoning: AI systems use reasoning techniques to make decisions or predictions.
However, these reasoning techniques can be uncertain due to the complexity of the problems they
address or the limitations of the data used to train the models.
To mitigate these sources of uncertainty, developers, and users of AI systems need to invest in better data
quality, model interpretability, and transparency, as well as engage in open dialogue about ethical and
legal considerations.

Types of Uncertainty in AI:

There are several types of uncertainty in AI, including:
1. Aleatoric Uncertainty: This type of uncertainty arises from the inherent randomness or variability
in data. It is often referred to as “data uncertainty.” For example, in a classification task, aleatoric
uncertainty may arise from variations in sensor measurements or noisy labels.
2. Parameter Uncertainty: This type of uncertainty is specific to probabilistic models, such as
Bayesian neural networks. It reflects uncertainty about the values of model parameters and is
characterized by probability distributions over those parameters.
3. Uncertainty in Decision-Making: Uncertainty in AI systems can affect the decision-making process.
For instance, in reinforcement learning, agents often need to make decisions in environments with
uncertain outcomes, leading to decision- making uncertainty.
4. Uncertainty in Natural Language Understanding: In natural language processing (NLP),
understanding and generating human language can be inherently uncertain due to language
ambiguity, polysemy (multiple meanings), and context-dependent interpretations.
5. Uncertainty in Probabilistic Inference: Bayesian methods and probabilistic graphical models are
commonly used in AI to model uncertainty. Uncertainty can arise from the process of probabilistic
inference itself, affecting the reliability of model predictions.
6. Uncertainty in Reinforcement Learning: In reinforcement learning, uncertainty may arise from the
stochasticity of the environment or the exploration-exploitation trade-off. Agents must make
decisions under uncertainty about the outcomes of their actions.
7. Uncertainty in Autonomous Systems: Autonomous systems, such as self-driving cars or drones,
must navigate uncertain and dynamic environments. This uncertainty can pertain to the movement
of other objects, sensor measurements, and control actions.
8. Uncertainty in Human-AI Interaction: When AI systems interact with humans, there can be
uncertainty in understanding and responding to human input, as well as uncertainty in predicting
human behavior and preferences.
Addressing and quantifying these various types of uncertainty is an ongoing research area in AI, and
techniques such as probabilistic modeling, Bayesian inference, and Monte Carlo methods are commonly
used to manage and mitigate uncertainty in AI systems.

BASIC PROBABILITY NOTATION

Probabilistic notation uses symbols and rules to talk about chances and predictions. It helps AI make
decisions when things are uncertain, like guessing weather or predicting stocks.
1. Basic Probability Notation:
o P(A): Probability of event A occurring.
o P(A') Probability of event A not occurring.
o P(A ∩ B): Probability of both A and B occurring simultaneously.
o P(A ∪ B): Probability of either A or B occurring.
o P(A ∩ B'): Probability of A occurring but not B.
o P(A' ∪ B): Probability of either A not occurring or B occurring.
Example: If the probability of rain tomorrow is P(Rain)= 0.4 , then the probability of no rain would be P(No
Rain) = 0.6 (since P(No Rain) = 1 - P(Rain)).
2. Conditional Probability:
o P( A |B): Probability of event A occurring given that event B has occurred.
o Bayes' Theorem: P(A|B)= P(B|A)* P(A) P(B) .
Example: Given that it's cloudy (B), what is the probability of rain (A)? P(Rain | Cloudy).
3. Joint Probability:
o P( A cap B); Probability of both A and B occurring.
Example: What is the probability of both flipping two coins and getting heads on both? P(Heads on coin 1 n
Heads on coin 2).
4. Expectation and Variance:
o E[X]: Expected value or mean of random variable X.
o Var(X): Variance of random variable X.
Example: For a fair six-sided die, E[X] = 3.5 (mean value), Var(X) = 2.92 (variance).
5. Bayesian Networks:
o Use graphs to represent probabilistic relationships.
o Nodes represent random variables, edges represent dependencies.
Example: In a medical diagnosis system, nodes could represent symptoms and diseases, and edges
represent conditional dependencies based on medical knowledge.

1. Bayes' Theorem Basics:

o Definition: Bayes theorem calculates the probability of an event based on prior knowledge.
o Formula: It relates the conditional probability P( A|B) to P( B |A), P(A) and P(B)
o Application: Useful in updating probabilities with new evidence.
2. Example in Medicine (Meningitis and Stiff Neck):
o Scenario: A doctor wants to determine the probability that a patient with a stiff neck has
meningitis.
o Given Data:
 Probability of a stiff neck given meningitis P( a |b)=0.8.
 Probability of meningitis in the population P(b) = 1/30000
 Probability of a stiff neck in the population P(a) = 0.02
3. Using Bayes' Theorem:
o Objective: Calculate P( b |a), which is the probability of meningitis given a stiff neck.
o Steps:
 Step 1: Prior Probability P(b) = 1/30000
 Step 2: Likelihood P( a |b)=0.8.
 Step 3: Marginal Probability P(a) = 0.02
4. Calculation:
o Apply Bayes' theorem formula:
 P(b|a)= P(a|b)* P(b)/P(a)
o Substitute the values:
 P(b|a)= (0.8 * 1/30000)/0.02
o Simplify to find P( b |a).

Applications in AI:
1. Bayesian Networks: Represent probabilistic relationships using DAGs.
2. Hidden Markov Models (HMMs): Model systems with hidden states influencing observable
events.
3. Markov Decision Processes (MDPs): Model decision-making under uncertainty.
4. Gaussian Processes (GPs): Used for regression and classification tasks, incorporating uncertainty
in predictions.
5. Probabilistic Graphical Models (PGMs): Encode conditional independence structures between
random variables.

Importance of Probabilistic Notation:

o Helps AI handle uncertainty in data, like predicting weather changes.
o Lets AI learn from data and update its knowledge, like predicting which movie you might like.
o Allows AI to make smart decisions based on what it knows, even if it doesn’t have all the
information.
Probabilistic notation is crucial in AI because it gives a clear way for AI to understand and work with
uncertain information.
Whether predicting outcomes, learning from data, or making decisions, mastering this language helps
AI become smarter and more reliable in various real-world applications.

INFERENCE USING FULL JOINT DISTRIBUTION

The full joint distribution is like a giant table that lists all possible combinations of events (rain, no rain,
sprinkler on, sprinkler off) and their probabilities. This table helps us answer any question about the
domain (like what’s the probability the grass is wet given that it’s raining and the sprinkler is off).
Chain Rule
The chain rule lets us calculate the probability of any combination of events by multiplying the conditional
probabilities together.
For example, to find the probability of it raining and the grass being wet, we multiply the probability of
it raining by the probability of the grass being wet given that it’s raining.
Why Bayesian Networks Are Useful
o No Redundancy: Bayesian Networks don’t repeat any probability values, so there’s no chance of
conflicting information.
o Accurate Representation: It’s impossible to create a Bayesian Network that doesn’t follow the
rules of probability, ensuring accuracy.
In Simple Terms
o Nodes: Think of them as questions (Is it raining? Is the sprinkler on? Is the grass wet?).
o Links: These are the connections showing how one question affects another (Rain affects Wet
Grass).
o CPTs: These are small tables that tell us the answer to one question based on the answers to
others.
o Chain Rule: This is like a recipe for calculating the probability of any combination of answers.
With a Bayesian Network, you can figure out the likelihood of any event based on the known relationships
and probabilities, and it’s always consistent with the rules of probability.
Compactness of Bayesian Networks Example: Burglar Alarm Network Imagine a network where:
o "Burglary" and "Earthquake" can cause an "Alarm."
o If the "Alarm" goes off, "John" and "Mary" might call the police.
Why Bayesian Networks are Compact:
1. Local Structure:
o Each variable (e.g., "Alarm") depends directly on only a few other variables (e.g., "Burglary" and
"Earthquake"), not all variables in the network.
o This local dependency keeps the network manageable.
2. Conditional Probabilities:
o We only need probabilities for direct influences (e.g., the probability that the alarm goes off given
a burglary and/or an earthquake), not for every possible combination of all variables.
Numbers Example:
o Suppose we have 30 variables (like "Alarm," "JohnCalls," etc.), each influenced by at most 5 others.
o For each variable, we need at most 252^525 (or 32) numbers to specify its probabilities.
o Total numbers needed: 30×32=96030 \times 32 = 96030×32=960.
o If we specified the full joint distribution, we'd need 2302^{30}230 (over a billion) numbers.
Practical Considerations:
1. Simplicity vs. Accuracy:
Adding more connections (like linking "Earthquake" directly to "JohnCalls" and "MaryCalls") might
improve accuracy but increases complexity.
Example Decision:
o Without the link: John and Mary call based on the alarm.
o With the link: They might not call during an earthquake because they assume it's the cause of the
alarm.
o Whether to add this link depends on if the small gain in accuracy is worth the added complexity.
By using Bayesian networks, we can efficiently manage and compute probabilities in large domains by
focusing on local structures and direct dependencies.
If we choose the wrong order when creating a Bayesian network, we can end up with a more complex
network that requires more probabilities to be specified and includes difficult and unnatural
relationships.
Example: Burglary Scenario
Consider a scenario involving an alarm system that detects both burglaries and earthquakes, and two
people (John and Mary) who call when they hear the alarm.
Correct Node Order: Burglary, Earthquake, Alarm, JohnCalls, MaryCalls
In this correct order:
1. Burglary and Earthquake are independent events.
2. Alarm depends on both Burglary and Earthquake.
3. JohnCalls and MaryCalls depend on the Alarm. This order results
in a simple and compact network.

Incorrect Node Order: MaryCalls, JohnCalls, Alarm, Burglary, Earthquake

In this incorrect order:
1. MaryCalls has no parents.
2. JohnCalls depends on MaryCalls.
3. Alarm depends on both MaryCalls and JohnCalls.
4. Burglary depends on the Alarm.
5. Earthquake depends on both Alarm and Burglary.
This creates a more complex network with unnecessary relationships, making it harder to specify and
 understand the probabilities. For example, you would need to assess the probability of an Earthquake
given both an Alarm and a Burglary, which is unnatural.

Very Bad Node Order: MaryCalls, JohnCalls, Earthquake, Burglary, Alarm

In this very bad order:
1. MaryCalls and JohnCalls have no parents.
2. Earthquake depends on both JohnCalls and MaryCalls.
3. Burglary depends on Earthquake.
4. Alarm depends on both Burglary and Earthquake.
This results in a network as complex as specifying the full joint distribution, requiring 31 distinct
probabilities.

Key Point
Using a causal model (causes to effects) is simpler and requires fewer and more natural probabilities than
using a diagnostic model (symptoms to causes). For example, in medicine, doctors prefer giving
probabilities for causes leading to symptoms rather than the other way around.

Conclusion:
o Correct order = simpler network, fewer probabilities.
o Incorrect order = more complex network, more probabilities, unnatural relationships.
o Very bad order = maximum complexity, as complex as the full joint distribution.

INDEPENDENCE
Independence between subsets of random variables allows the full joint distribution to be factored into
smaller joint distributions, greatly reducing its complexity. Conditional independence brought about by
direct causal relationships in the domain might allow the full joint distribution to be factored into smaller,
conditional distributions.
Conditional independence in Bayesian networks using simple examples:
1. Numerical Semantics: This means defining how variables interact through specific probabilities in
the network.
Example: In a Bayesian network about home security, if Alarm going off influences whether John Calls
and Mary Calls, we might say:
o P(John Calls | Alarm) = 0.8 (John is likely to call if the alarm goes off).
o P(Mary Calls | Alarm) = 0.6 (Mary is somewhat likely to call if the alarm goes off).
2. Topological Semantics: This focuses on the structure of the network to determine independence
relationships.
Example: In the same security network, if Alarm directly affects both John Calls and Mary Calls, they
would be independent of each other given Alarm.
If Alarm is on, whether John calls or not doesn’t change the probability of Mary calling, and vice
versa.
3. Equivalence of Semantics: Both numerical and topological views are equivalent—they
describe the same relationships.
Example: Knowing that in our network, Burglary is independent of John Calls and Mary Calls given
Alarm and Earthquake allows us to precisely calculate how these variables influence each other
numerically.
4. Markov Blanket:It includes a node's parents, children, and children's parents, making it a shield
against influences from other parts of the network.
Example: If Burglary’s Markov blanket includes Alarm and Earthquake, then Burglary is independent of
 other variables like John Calls and Mary Calls given these factors.
o Bayesian networks use both graphical (topological) and probability-based (numerical) approaches
to show how variables interact.
o Understanding these concepts helps in modeling dependencies effectively, ensuring that we can
make accurate predictions and decisions based on the network's structure and parameters.

(a) Conditional Independence Given Parents:

In a family tree, if X is a child and U are its parents, X is independent of its non-descendant relatives (Z)
given its parents (U). Knowing X's parents (like John and Mary) tells you everything about X that
knowing their cousins wouldn't.
(b) Conditional Independence Given Markov Blanket:
In a network, a node X is independent of all other nodes if you know everything about its Markov blanket.
This blanket includes X's parents, children, and their other parents. For example, knowing a student's
friends, their parents, and the student's own parents is enough to predict the student's behavior without
needing details about other students or their families.

BAYES’ RULE AND ITS USE

Bayes’ rule allows unknown probabilities to be computed from known conditional probabilities, usually
in the causal direction. Applying Bayes’ rule with many pieces of evidence runs into the same scaling
problems as does the full joint distribution.
Bayes' Rule, or Bayes' Theorem, is a mathematical formula used to update probabilities based on new
evidence. It describes the probability of an event given prior knowledge and new data, expressed as:
P(A∣B)=P(B∣A)⋅P(A)P(B)/P(A|B)
Where:
o P(A∣B) P(A|B) P(A∣B): Posterior probability (probability of A given B)
o P(B∣A) P(B|A) P(B∣A): Likelihood (probability of B given A)
o P(A) P(A) P(A): Prior probability of A
o P(B) P(B) P(B): Marginal probability of B (normalizing constant)
Use in AI
Bayes' Rule is foundational in AI, particularly in probabilistic reasoning, machine learning, and decision-
making. Key applications include:
1. Bayesian Inference:
o Used in models to update beliefs about unknown parameters as new data arrives.
o Example: In spam email filtering, the model updates the probability that an email is spam
based on word frequencies.
2. Machine Learning:
o Naive Bayes Classifiers: Assumes feature independence to classify data (e.g., text
 classification, sentiment analysis).
o Bayesian Neural Networks: Incorporate uncertainty in weights, improving robustness in
predictions.
3. Natural Language Processing (NLP):
o Used in language models to predict the next word or disambiguate meanings based on
context.
o Example: Spell checkers use Bayes' Rule to suggest corrections by combining prior word
probabilities with observed errors.
4. Robotics and Sensor Fusion:
o Combines noisy sensor data to estimate a robot’s position or environment (e.g., in Kalman
filters or particle filters).
5. Medical Diagnosis:
o AI systems use Bayes' Rule to update disease probabilities based on symptoms and test
results.
6. Reinforcement Learning:
o Helps agents update beliefs about the environment to make optimal decisions under
uncertainty.
Bayes' theorem in Artificial intelligence
o Bayes' theorem is also known as Bayes' rule, Bayes' law, or Bayesian reasoning, which
determines
o the probability of an event with uncertain knowledge.
o In probability theory, it relates the conditional probability and marginal probabilities of two
random events.
o Bayes' theorem was named after the British mathematician Thomas Bayes. The
Bayesian inference is an application of Bayes' theorem, which is fundamental to
Bayesian statistics.
o It is a way to calculate the value of P(B|A) with the knowledge of P(A|B).
o Bayes' theorem allows updating the probability prediction of an event by observing new
information of the real world.
Example:
o If cancer corresponds to one's age, then by using Bayes' theorem, we can determine the
probability of cancer more accurately with the help of age.
o Bayes' theorem can be derived using product rule and conditional probability of event A with
known event B:
o As from product rule we can write:

P(A ⋀ B)= P(A|B) P(B) or

Similarly, the probability of event B with known event A:

P(A ⋀ B)= P(B|A) P(A)

o Equating right hand side of both the equations, we will get:

 o The above equation (a) is called as Bayes' rule or Bayes' theorem. This equation is
basic of most modern AI systems for probabilistic inference.
o It shows the simple relationship between joint and conditional probabilities. Here,
P(A|B) is known as posterior, which we need to calculate, and it will be read as
Probability of hypothesis A when we have occurred an evidence B.
o P(B|A) is called the likelihood, in which we consider that hypothesis is true, then we
calculate the probability of evidence.
o P(A) is called the prior probability, probability of hypothesis before considering the
evidence
o P(B) is called marginal probability, pure probability of an evidence.
o In the equation (a), in general, we can write P (B) = P(A)*P(B|Ai), hence the Bayes'
rule can be written as:

Where A1, A2, A3,. ...... , An is a set of mutually exclusive and exhaustive events.

Applying Bayes' rule:

o Bayes' rule allows us to compute the single term P(B|A) in terms of P(A|B), P(B), and P(A).
o This is very useful in cases where we have a good probability of these three terms
and want to determine the fourth one.
o Suppose we want to perceive the effect of some unknown cause, and want to compute
that cause, then the Bayes' rule becomes:

Example-1:
Question: what is the probability that a patient has diseases meningitis with a stiff
neck? Given Data:
A doctor is aware that disease meningitis causes a patient to have a stiff neck, and it occurs 80% of
the time. He is also aware of some more facts, which are given as follows:
o The Known probability that a patient has meningitis disease is 1/30,000.
o The Known probability that a patient has a stiff neck is 2%.

Let a be the proposition that patient has stiff neck and b be the proposition that patient has
meningitis. , so we can calculate the following as:
P(a|b) = 0.8
P(b) =
1/30000
P(a)= .02

Hence, we can assume that 1 patient out of 750 patients has meningitis disease with a stiff neck.

Why It’s Powerful in AI

 Handles Uncertainty: AI often deals with incomplete or noisy data, and Bayes' Rule provides a
principled way to manage uncertainty.
 Incorporates Prior Knowledge: Allows models to start with existing knowledge and refine it
with new evidence.
 Scalable: Bayesian methods integrate with modern AI frameworks, like probabilistic
 programming (e.g., Pyro, Stan).
Challenges
 Computational Complexity: Calculating P(B) P(B) P(B) can be intensive, especially with high-
dimensional data.
 Prior Selection: Choosing an appropriate prior can be subjective and impact results.
 Approximations: In complex models, exact Bayesian inference is often intractable, requiring
approximations like Markov Chain Monte Carlo (MCMC) or variational inference.
In summary, Bayes' Rule is a cornerstone of probabilistic AI, enabling systems to reason under
uncertainty, learn from data, and make informed decisions across diverse applications.

PROBABILISTIC REASONING
Probabilistic reasoning is a method used in intelligent systems to handle uncertainty. It uses
probabilistic concepts to make decisions or draw conclusions based on available information.
Probabilistic reasoning in AI uses probability theory to manage uncertainty in decision- making.
It enables AI systems to function effectively in complex, real-world scenarios where information is
incomplete or noisy.
Problems of Full Joint Probability Distribution:
1. Complexity with Many Variables: When the number of variables increases, the full joint
probability distribution becomes extremely large and difficult to manage. Example: Imagine trying to
calculate the probabilities of all possible outcomes in a complex scenario involving many factors,
like predicting weather patterns based on numerous environmental variables.
2. Tedious Specification: Specifying probabilities for every possible scenario
sequentially can be laborious and prone to errors.
Example: Assigning probabilities for every combination of symptoms and diseases in a medical
diagnosis system without any structured framework.
Key Techniques:
o Bayesian Networks: Graphical models showing relationships between variables and their
probabilities, used in medical diagnosis and causal reasoning.
o Markov Models: Predict future states based on current and past states, widely used in weather
forecasting and speech recognition.
o Hidden Markov Models (HMMs): Extend Markov models to include hidden states, crucial in
applications like stock market prediction.
o Probabilistic Graphical Models: Framework encompassing Bayesian networks and HMMs,
suitable for complex relationships.
Advantages:
o Flexibility: Adaptable to various domains and types of uncertainty.
o Robustness: Handles noise and incomplete data well, making it reliable in practical
applications.
o Interpretable: Provides a clear framework for understanding uncertainty, aiding in
transparency and decision-making.

1. Definition of Probabilistic Reasoning: Probabilistic reasoning integrates probability theory with

logic to manage uncertainty in knowledge representation. It allows us to quantify the likelihood of
different outcomes or states of the world based on available evidence or assumptions.
2. Uncertainty in Knowledge Representation: Traditional approaches like propositional and first-
order logic assume certainty in predicates (statements about the world). In contrast, probabilistic
reasoning acknowledges uncertainty, where we are unsure about the truth value of predicates due to
various factors like unreliable sources, experimental errors, or environmental variations.
3. Causes of Uncertainty: Several factors contribute to uncertainty in real-world scenarios,
including unreliable information sources, experimental errors, equipment faults, temperature
variations, and broader phenomena like climate change. These factors challenge the certainty of
statements we might make about the world.
4. Application Scenarios: Probabilistic reasoning is essential in AI when dealing with:
a. Unpredictable Outcomes: Situations where outcomes cannot be determined with certainty,
 such as weather predictions or human behavior modeling.
b. Complex Specifications: When the number of possible states or outcomes becomes too vast to
handle with certainty using traditional logic.
c. Unknown Errors: Cases where unexpected errors or anomalies occur during experiments or
data collection, affecting the reliability of information.
5. Role of Probability: Probability provides a structured framework to express and manage
uncertainty in probabilistic reasoning. It allows AI systems to make informed decisions or
predictions by quantifying uncertainty and updating beliefs based on new evidence.
6. Practical Examples: Examples of probabilistic reasoning applications include predicting the
likelihood of rain, modeling the behavior of individuals in various contexts, or assessing the outcome
of competitive events like sports matches.
Probabilistic reasoning is crucial in AI for handling uncertainty effectively, which is pervasive in real-
world scenarios due to various factors and phenomena beyond our complete control or knowledge. It
enriches knowledge representation by allowing AI systems to reason about probabilities and make
decisions in the face of uncertainty.

REPRESENTING KNOWLEDGE IN AN UNCERTAIN DOMAIN

How Knowledge is Represented
Knowledge Representation is how we store information about the world so that a computer can
understand and use it to make decisions.
Example: Think of it like writing down a recipe for cooking. The recipe tells you the ingredients and
steps needed to make a dish. In the same way, knowledge representation tells a computer the
important facts and rules about a situation.
Knowledge Representation Techniques
There are several techniques for representing knowledge, especially in uncertain domains where
information may not be complete or certain:
1. Logic-Based Representation:
Propositional Logic: Simple statements those are either true or false.
Example: "It is raining" (true or false).
First-Order Logic: Uses objects, relations, and quantifiers.
Example: "All cats are mammals."
2. Probabilistic Representation:
Bayesian Networks: Graphical models that represent probabilistic
relationships among variables.
Example: Representing the likelihood of having a cold given symptoms like cough and fever.
3. Fuzzy Logic:
Deals with reasoning that is approximate rather than fixed and exact.
Example: "The room is warm" rather than a specific temperature.
4. Semantic Networks:
Graph structures for representing knowledge in patterns of interconnected nodes and edges.
Example: Representing relationships like "A dog is a pet" and "A pet can be a companion."
Role of Knowledge in Reasoning
Reasoning is the process of drawing conclusions from available knowledge.
Example: If you know that "All humans are mortal" and "Socrates is a human," you can reason that
"Socrates is mortal."
Knowledge helps in reasoning by providing the facts and rules needed to make logical deductions,
predictions, or decisions. In uncertain domains, probabilistic reasoning helps in making decisions
based on incomplete or uncertain information.
Example: Given symptoms like fever and cough, reasoning with a Bayesian network can help
diagnose the probability of having a flu.
Issues in Knowledge Representation
There are several challenges when it comes to representing knowledge, especially in uncertain
domains:
1. Complexity:
 Representing real-world situations can be very complex.
Example: Accurately modeling the weather involves many variables and relationships.
2. Uncertainty:
Not all information is certain; there can be unknowns or probabilities.
Example: Predicting if it will rain tomorrow based on current weather data.
3. Ambiguity:
The same information can be interpreted in different ways.
Example: The word "bank" can mean the side of a river or a financial institution.
4. Incompleteness:
Sometimes, not all information is available.
Example: Diagnosing a disease without knowing all symptoms.
5. Scalability:
Handling large amounts of knowledge efficiently.
Example: A search engine indexing billions of web pages.

Knowledge representation in uncertain domains involves storing information in ways that allow
computers to understand and use it for reasoning.
o Techniques like logic-based representation, probabilistic models, and fuzzy logic help manage
uncertainty. Knowledge plays a critical role in reasoning by providing the necessary facts and
rules.
o However, issues like complexity, uncertainty, ambiguity, incompleteness, and scalability pose
challenges to effective knowledge representation.

THE SEMANTIC OF BAYESIAN NETWORKS

Semantics: The meaning or interpretation of a concept or term within a specific context.
Example: In a Bayesian Network, the semantics refer to the specific joint probability distribution over
all the variables represented by the network.
The semantics of Bayesian Network:
There are two ways to understand the semantics of the Bayesian network, which is given below:
1. To understand the network as the representation of the Joint probability distribution.
It is helpful to understand how to construct the network.
2. To understand the network as an encoding of a collection of conditional independence
statements.
It is helpful in designing inference procedure.
What is a Bayesian Network?
A Bayesian Network is like a map showing how different factors are related to each other and how
likely certain things are to happen. A Bayesian network graph is made up of nodes and Arcs (directed
links), where:

o Each node corresponds to the random variables, and a variable can be continuous or
discrete.
o Arc or directed arrows represent the causal relationship or conditional probabilities
between random variables. These directed links or arrows connect the pair of nodes in the
graph. These links represent that one node directly influence the other node, and if there is
no directed link that means that nodes are independent with each other.
o In the above diagram, A, B, C, and D are random variables represented by the nodes of the
 network graph.
o If we are considering node B, which is connected with node A by a directed arrow, then node
A is called the parent of Node B.
o Node C is independent of node A.
Bayesian networks, also known as belief networks or causal networks, are a structured way to
represent and reason about probabilistic relationships. They address the limitations of full joint
probability distributions.
Properties of Bayesian Networks:
a. Node Representation: Each node in a Bayesian network represents a random variable, which
can be discrete (like true/false) or continuous (like temperature).
Example: In a medical diagnosis system, nodes could represent variables such as symptoms
(fever, cough) or diseases (flu, pneumonia).
b. Directed Graph Structure: Nodes are connected by directed arrows that show the influence
between variables. An arrow from node X to Y means X directly influences Y.
Example: An arrow from "Smoking" to "Lung Cancer" in a health-related Bayesian network
signifies that smoking affects the likelihood of developing lung cancer.
c. Directed Acyclic Graph (DAG): It's a graph without any cycles (loops), ensuring there are no
feedback loops where a variable indirectly affects itself.
Example: A DAG ensures that in a system predicting financial market trends, no variable (like
stock price) influences itself through a series of dependent variables.
d. Conditional Probability Distribution: Each node has associated probabilities that depend on its
parents in the network. This distribution captures how each variable is affected by its direct
influences.
Example: For "Rain" as a node, its conditional probability distribution might specify how likely
rain is given the previous day's weather and current atmospheric conditions.
Bayesian networks provide a structured approach to probabilistic reasoning by organizing variables,
their relationships, and their uncertainties, making complex systems more manageable and allowing
for efficient decision-making and inference.
How Does It Work?
1. Nodes and Conditional Probabilities: Each node has some numbers attached to it called
conditional probabilities. These numbers tell us how likely an event is, given some other events. For
example, if we have a node for "Rain" and a node for "Wet Grass", the conditional probability tells us
how likely the grass is wet if it’s raining.
2. Conditional Probability Tables (CPTs): Each node has a table (CPT) that shows the conditional
probabilities. For example, the "Wet Grass" node will have a table showing the probability of the grass
being wet if it’s raining and if it’s not raining.
Example
Imagine we have three nodes: Rain, Sprinkler, and Wet Grass.
o Rain: It can either rain or not rain.
o Sprinkler: It can either be on or off.
o Wet Grass: The grass can either be wet or dry.
Conditional Probabilities:
o If it rains, there’s an 80% chance the grass will be wet.
o If the sprinkler is on, there’s a 90% chance the grass will be wet.
o If it’s raining and the sprinkler is on, the grass is almost certainly wet.
Explanation of Bayesian network:
Let's understand the Bayesian network through an example by creating a directed acyclic graph:
Example: Harry installed a new burglar alarm at his home to detect burglary. The alarm reliably
responds at detecting a burglary but also responds for minor earthquakes. Harry has two neighbors
David and Sophia, who have taken a responsibility to inform Harry at work when they hear the
alarm. David always calls Harry when he hears the alarm, but sometimes he got confused with the
phone ringing and calls at that time too. On the other hand, Sophia likes to listen to high music, so
sometimes she misses to hear the alarm. Here we would like to compute the probability of Burglary
Alarm.
Problem:
Calculate the probability that alarm has sounded, but there is neither a burglary, nor an
earthquake occurred, and David and Sophia both called the Harry.
Solution:
o The Bayesian network for the above problem is given below. The network structure is
showing that burglary and earthquake is the parent node of the alarm and directly affecting
the probability of alarm's going off, but David and Sophia's calls depend on alarm
probability.
o The network is representing that our assumptions do not directly perceive the burglary
and also do not notice the minor earthquake, and they also not confer before calling.
o The conditional distributions for each node are given as conditional probabilities table or CPT.
o Each row in the CPT must be sum to 1 because all the entries in the table represent an
exhaustive set of cases for the variable.
o In CPT, a boolean variable with k boolean parents contains 2K probabilities. Hence, if there
are two parents, then CPT will contain 4 probability values
List of all events occurring in this network:
o Burglary (B)
o Earthquake(E)
o Alarm(A)
o DavidCalls(D)
o SophiaCalls(S)
We can write the events of problem statement in the form of probability: P[D, S, A, B, E], can rewrite
the above probability statement using joint probability distribution:
P[D, S, A, B, E]= P[D | S, A, B, E]. P[S, A, B, E]
=P[D | S, A, B, E]. P[S | A, B, E]. P[A, B, E]
= P [D| A]. P [ S| A, B, E]. P[ A, B, E]
= P[D | A]. P[ S | A]. P[A| B, E]. P[B, E]
= P[D | A ]. P[S | A]. P[A| B, E]. P[B |E]. P[E]

Let's take the observed probability for the Burglary and earthquake
component: P(B= True) = 0.002, which is the probability of burglary.
P(B= False)= 0.998, which is the probability of no burglary.
P(E= True)= 0.001, which is the probability of a minor earthquake
P(E= False)= 0.999, Which is the probability that an earthquake not occurred.
We can provide the conditional probabilities as per the below tables:
 Conditional probability table for Alarm A:
The Conditional probability of Alarm A depends on Burglar and earthquake:

B E P(A= True) P(A= False)

True True 0.94 0.06
True False 0.95 0.04
False True 0.31 0.69
False False 0.001 0.999
Conditional probability table for David Calls:
The Conditional probability of David that he will call depends on the probability of Alarm.

A P(D= True) P(D= False)

True 0.91 0.09
False 0.05 0.95
Conditional probability table for Sophia Calls:
The Conditional probability of Sophia that she calls is depending on its Parent Node "Alarm".

A P(S= True) P(S= False)

True 0.75 0.25
False 0.02 0.98
From the formula of joint distribution, we can write the problem statement in the form of probability
distribution:
P(S, D, A, ¬B, ¬E) = P (S|A) *P (D|A)*P (A|¬B ^ ¬E) *P (¬B) *P (¬E).
= 0.75* 0.91* 0.001* 0.998*0.999
= 0.00068045.
Hence, a Bayesian network can answer any query about the domain by using Joint distributions.

EFFICIENT REPRESENTATION OF CONDITIONAL DISTRIBUTIONS

Conditional Distribution:
Creating Conditional Probability Tables (CPTs) for Bayesian networks can be complex, especially with
fewer parent nodes (k). In the worst case, filling these tables could need O(2^k) entries. However,
many parent-child relationships follow standard patterns, described by simpler distributions. For
instance, in a network predicting rain (R) with Cloudy (C) and Windy
(W) as parents, instead of listing all combos (4), you might note rain is likelier when cloudy: P(R | C,
W) = High if C = True, else Low.
This simplifies the CPT by using patterns rather than every scenario, making it easier to manage.
Deterministic Nodes:
In a Bayesian network, a deterministic node's value is exact and depends solely on its parent nodes,
without uncertainty:
o Logical Example: A child node "North American" with parent nodes "Canadian," "US," and
"Mexican" simply reflects whether any parent is true.
o Numerical Example 1: If parent nodes are car prices at different dealers, the child node
"bargain hunter's price" would be the minimum price among the parents.
o Numerical Example 2: For a lake's parent nodes representing inflows and outflows, the child
node "change in water level" would be the difference between total inflows and outflows.
Noisy-OR
Noisy logical relationships, like noisy-OR, handle uncertainty in connections. For example, in
propositional logic, we might say having a Fever could be due to Cold, Flu, or Malaria. But unlike a
strict OR, where having any one of these conditions guarantees a Fever, noisy-OR allows for cases
where having Cold alone might not result in a Fever.
Noisy-OR Assumption
1. Assumption 1: Listing Possible Causes:
When identifying causes of a symptom (like fever), we assume we've listed all major causes. If some
causes are unknown or miscellaneous, we can add a "leak node" to cover these.
2. Assumption 2: Independent Inhibition:
Each cause's ability to prevent the symptom (fever) is independent of others. For instance, what stops
Malaria from causing a fever is separate from what stops Flu.
3. Probability Calculation:
We assign probabilities (inhibition probabilities) to each cause preventing the symptom:
o For Cold (qcold): 0.6
o For Flu (qflu): 0.2
o For Malaria (qmalaria): 0.1
4. Building Conditional Probability Table (CPT): Using the noisy-OR model:
o If a cause is present, it can contribute to the symptom (fever).
o If multiple causes are present, their combined effect is considered.
5. Example CPT Calculation for Fever

Cold Flu Malaria P(Fever) P(¬Fever)

F F F 0.0 1.0
F F T 0.9 0.1
F T F 0.8 0.2
F T T 0.98 0.02
T F F 0.4 0.6
T F T 0.94 0.06
T T F 0.88 0.12
T T T 0.988 0.012

o These values show the probability of fever (P(Fever)) or no fever (P(¬Fever)) given
combinations of causes (Cold, Flu, Malaria).
6. Advantages of Noisy-OR Model
o Simplifies complex probability assessments by focusing on how each cause independently
influences the symptom.
o Reduces the number of parameters needed compared to a full probability table, making it
easier to manage and learn from data.
o This approach, used in medical diagnosis and other fields, helps model probabilistic
relationships efficiently while accounting for uncertainty and independence among causes.

Bayesian nets with continuous variables

Discretization
o Handling continuous variables in Bayesian networks is tricky because they can take on
countless values. To handle this, we often use discretization. For instance, instead of
considering every possible temperature, we might group them into categories like "cold,"
"warm," and "hot."
o Discretization simplifies things by reducing the number of specific values we deal with.
However, it can make our estimates less precise and require larger tables of probabilities.
o Alternatively, we can use standard math functions like the Gaussian (normal) distribution,
which uses parameters like mean (μ) and variance (σ²). This approach helps us model values
more accurately without discretizing them explicitly.
o In more complex situations, we might use nonparametric methods. Here, distributions are
represented indirectly through specific examples with known values of related variables.
o These methods make Bayesian networks useful for real-world problems involving continuous
data, balancing accuracy with practicality in calculations.
Hybrid Bayesian Network
In a hybrid Bayesian network, which deals with both discrete and continuous variables, we specify
how variables depend on each other using conditional distributions:
1. Continuous Variable (Cost):
o Given Parents (Harvest and Subsidy): We need to define how the cost (a continuous variable)
depends on its parents (which can be both continuous and discrete).
o Handling Discrete Parents: For discrete parents like Subsidy, we specify different scenarios
(Subsidy is true or false) by providing separate distributions (P(Cost | Harvest, Subsidy) and
P(Cost | Harvest, ¬Subsidy)).
o Handling Continuous Parent (Harvest): We use a linear Gaussian distribution, where the cost's
distribution (like its mean and variability) changes linearly with the value of Harvest.
o Example: If Harvest affects Cost, we might say Cost follows a Gaussian distribution with mean μ
= ath + bt and standard deviation σ. Here, ath and bt are parameters that define how Harvest
influences Cost.
2. Discrete Variable (Buys):
o Given Continuous Parent (Cost): For Buys (a discrete variable), its distribution depends on the
continuous variable Cost.
o Example: Buys could be influenced by Cost such that the probability of buying fruit might
increase as Cost decreases. This relationship is specified in the Bayesian network to show how
Cost affects Buys.
o In a hybrid Bayesian network: Continuous variables like Cost are described using linear
Gaussian distributions, with parameters that show how they depend on continuous and
discrete parent variables.
o Discrete variables like Buys are described by how they depend on continuous parent variables,
showing the likelihood of different outcomes based on the value of the continuous parent.
This structure helps model complex relationships in systems where both types of variables interact.
For this example, then, the conditional distribution for Cost is specified by naming the linear Gaussian
distribution and providing the parameters at, bt, σt, af, bf,and σf.
Figures 14.6(a) and (b) show these two relationships. Notice that in each case the slope is negative,
because cost decreases as supply increases. (Of course, the assumption of linearity implies that the
cost becomes negative at some point; the linear model is reasonable only if the harvest size is limited
to a narrow range.)
Figure 14.6(c) shows the distribution P(c|h), averaging over the two possible values of Subsidy and
assuming that each has prior probability 0.5. This shows that even with very simple models, quite
interesting distributions can be represented.
Conditional Gaussian
In networks with linear Gaussian distributions:
o All continuous variables connected in a certain way form a joint distribution that looks like a
bell curve, known as a multivariate Gaussian.
o When discrete variables influence continuous ones, the conditional distribution of the
continuous variables given specific values of the discrete ones is called a conditional Gaussian
distribution.
For example, imagine predicting if a customer buys a product based on its cost. Let's say cost is
continuous, and the buying decision (Buys) is discrete (yes or no). If we think customers are more
likely to buy when the cost is low and less likely as it increases, we can model this with a soft
threshold.
To create soft thresholds, we use the cumulative standard normal distribution function, Φ(x).
For instance, the probability a customer buys given a cost (c) might be Φ((−c+μ)/σ), where:
P(buys |Cost =c)=Φ((−c+μ)/σ)
o μ is the cost where the probability of buying is 50%,
o σ controls how quickly the probability changes around μ.
As cost moves away from μ, the probability of buying decreases smoothly according to the standard
normal curve. This method helps us model complex decision-making in a clear, probabilistic way.
 o This probit distribution (pronounced “pro-bit” and short for “probability unit”) is illustrated in
Figure 14.7(a). The form can be justified by proposing that the underlying decision process has a
hard threshold, but that the precise location of the threshold is subject to random Gaussian noise.
o An alternative to the probit model is the logit distribution (pronounced “low-jit”). It uses the
logistic function 1/(1 + e−x) to produce a soft threshold: P(buys |Cost =c)= 1/ 1+exp (−2−c+μ/σ) .
o This is illustrated in Figure 14.7(b). The two distributions look similar, but the logit actually has
much longer “tails.” The probit is often a better fit to real situations, but the logit is sometimes
easier to deal with mathematically. It is used widely in neural networks. Both probit and logit can
be generalized to handle multiple continuous parents by taking a linear combination of the parent
values.

APPROXIMATE INFERENCE BAYESIAN NETWORKS

Montecarlo
o Big and complex networks make exact answers hard to find. So, we turn to approximate methods
like Monte Carlo algorithms, such as simulated annealing. These methods randomly sample
data to give results close to the right ones. They're widely used in science to estimate tricky
values.
o For example, imagine predicting an election outcome in a large country with many factors
affecting voters. Monte Carlo methods help us estimate different outcomes by randomly
sampling voter opinions and behaviors.
o When calculating posterior probabilities, we look at two main types of algorithms: direct
sampling and Markov chain sampling. Each tackles complex network data differently to give
useful estimates.
o Other methods like variational approaches and loopy propagation are also mentioned as ways to
handle similar problems at the end of the chapter.
Direct sampling methods
1. Direct Sampling Overview: Sampling methods generate random outcomes from known
probability distributions. For example, flipping an unbiased coin with a 50% chance for heads
and tails can be simulated by generating a random number between 0 and 1. If it's ≤ 0.5, it's
heads; otherwise, it's tails.
2. Simple Example: To simulate a coin flip, generate a random number between 0 and 1. ≤
3. 0.5 = heads, > 0.5 = tails.
4. Sampling in Bayesian Networks: Bayesian networks depict probabilistic relationships among
variables. Sampling follows a topological order, starting with variables without parents and
using their distributions to sample values. Proceed to variables with known parent values using
conditional distributions until all are sampled.
5. Conclusion In a Bayesian network where variables like Weather, Temperature, and Outfit Choice
are interconnected, sample in topological order: Weather first, then Temperature, and finally
Outfit Choice, respecting each variable's dependencies. This approach ensures that sampled
values reflect the network's probabilistic structure accurately.

Algorithm Explanation:
The function PRIOR-SAMPLE that generates events from a Bayesian network
PRIOR-SAMPLE constructs a sample by iteratively sampling each variable in the network according to
its conditional probability distribution, given the values already sampled for its parent variables.
1. Sampling Process: We use a method called PRIOR-SAMPLE to generate events from a network
(like a Bayesian network). Each event depends on its parent events.
2. Probability Calculation: The probability of generating a specific event using PRIOR- SAMPLE is
the product of the probabilities of its components given their parents.
3. Accuracy of Sampling: As we increase the number of samples (N), the fraction of times a
specific event occurs (NPS(x1,...,xn)/N) gets closer to its actual probability (SPS(x1,...,xn)).
4. Estimating Probabilities: If we generate a large number of samples, we can estimate the
probability of any event by counting how often it occurs among all samples. This estimated
probability becomes more accurate with more samples.
5. Consistency: When we say an estimate is "≈" to a probability, it means the estimate becomes
exact in the limit of infinitely many samples. This type of estimate is called consistent.
6. Example: For instance, if we sample 1000 times and find that 511 of those samples have Rain
= true, then we estimate the probability of rain as 0.511.
7. These points highlight how sampling from a Bayesian network helps us understand
probabilities of different events, even when the exact probabilities are not initially known.
Algorithm: Rejection sampling in Bayesian networks
Rejection sampling is a method used to estimate probabilities when dealing with uncertain situations,
like predicting if it will rain based on certain observations. Here’s a simplified explanation with
examples:
What is rejection sampling?
Rejection sampling helps us estimate probabilities when direct calculation is hard. Imagine you want to
know the chance of rain (R) given that the sprinkler is on (S = true), denoted as P(R | S = true).
How does rejection sampling work?
1. Generate Samples: First, generate many random scenarios (samples) of sprinkler and rain using
what we know about their typical occurrences (prior knowledge).
Example: Assume we know from past data:
o P(Rain) = 0.3 (30% chance of rain on any given day)
o P(Sprinkler) = 0.4 (40% chance the sprinkler is on on any given day)
2. Apply Evidence: Apply the evidence (observations) we have. In our example, we observe that the
sprinkler is on (S = true).
o Among the samples where S = true, count how many times it also rains (R = true).
3. Estimate Probability: Estimate P(R | S = true) based on the ratio of how often it rains when the
sprinkler is on compared to all times the sprinkler is on.
Example: Out of 100 days sampled where the sprinkler is on (S = true):
o 40 days might have the sprinkler on (based on our prior)
o Among those 40, we find it rains on 12 days. Therefore, P(R | S
= true) ≈ 12/40 = 0.3.
Why is rejection sampling limited?
Rejection sampling becomes less effective as more variables (like more evidence to consider) are
involved because it discards many samples that don’t match the evidence. For instance, if we had to
consider not just the sprinkler but also the color of the sky the previous night (another evidence), we
might end up with very few samples that fit all conditions.
Real-world comparison:
In everyday life, estimating probabilities can be similar to rejection sampling. For example, to guess if
it will rain (R) after seeing a red sky at night (RedSkyAtNight = true):
o We might observe how often it rains after seeing a red sky, ignoring days when the sky wasn’t
red.
If we observe 50 red sky nights and it rains 15 times the next day, then P(R | RedSkyAtNight =
true) ≈ 15/50 = 0.3.
Conclusion:
Rejection sampling provides a way to estimate probabilities in complex scenarios by generating and
filtering scenarios based on observed evidence. However, it becomes impractical for highly complex
problems due to the large number of samples it discards.

Algorithm Explanation: Rejection sampling for Bayesian networks:

Rejection sampling is a Monte Carlo method used in Bayesian networks for generating samples from
joint probability distributions:
1. Basic Idea: It randomly assigns values to variables based on priors and accepts or rejects
samples based on observed evidence.
2. Procedure:
a. Randomly assign values to variables according to priors.
b. Check if the sample satisfies observed evidence; keep or reject it accordingly.
c. Repeat until enough valid samples are collected.
3. Sampling Efficiency: Can be inefficient with low prior probabilities of satisfying evidence, leading
to many rejections.
4. Consistency: Provides consistent estimates of the posterior distribution with sufficient samples,
but can be computationally expensive for large networks or strict evidence.
5. Suitability: Easy to implement but may struggle with scalability in complex networks or
dependencies.
6. Comparison: Less efficient compared to methods like likelihood weighting due to higher rejection
rates, wasting computational [Link] sampling ensures correct posterior estimates with
enough samples, its inefficiency in managing evidence constraints and scalability issues restrict its
practical utility in many Bayesian network scenarios.
This method relies on generating samples and selecting only those consistent with the observed
evidence, making it suitable for querying Bayesian networks where direct computation of
probabilities may be impractical.

Algorithm: Likelihood Weighting:

o Likelihood weighting is a technique in artificial intelligence used for probabilistic inference.
o It works by sampling from the Bayesian network, focusing more on variables that are relevant to
the query being evaluated.
o This method improves efficiency compared to exhaustive enumeration of all possible outcomes.
o Likelihood weighting efficiently computes probabilities in Bayesian networks by focusing
sampling efforts on events consistent with observed evidence, and adjusting for the likelihood
of those events given the evidence.
o This avoids the high rejection rates seen in rejection sampling, making it a more effective method
for inference.

Likelihood Weighting Overview:

Likelihood weighting is a technique used in Bayesian networks to efficiently compute probabilities
of queries given evidence. It avoids the inefficiencies of rejection sampling by only generating
events that are consistent with the evidence provided.
Example Scenario:
Let's consider a simplified Bayesian network concerning weather conditions:
1. Variables and Probabilities:
o Cloudy (C): P(C=true) = 0.5, P(C=false) = 0.5
o Sprinkler (S): P(S=true | C=true) = 0.1, P(S=true | C=false) = 0.5
 o Rain (R): P(R=true | C=true) = 0.8, P(R=true | C=false) = 0.2
o WetGrass (W): P(W=true | S= true, R=true) = 0.9, P(W=true | S=true, R=false) = 0.8. P(W=true |
S=false, R=true) = 0.2, P(W=true | S=false, R=false) = 0.1
2. Evidence:
We have evidence that it is Cloudy = true and WetGrass = true.

3. Query:
We want to compute the probability of Rain = true given Cloudy = true and WetGrass = true, i.e.,
P(R=true | C=true, W=true).

Likelihood Weighting Process:

1. Initialization:
Start with a weight w = 1.0.
2. Sampling Process:
Since Cloudy is evidence and fixed to true:
Set weight w←wxP(C= true) = 0.5.
Sample Sprinkler given Cloudy = true:
Suppose it returns S=false (since we sample from P(S=false | C=true) = 0.9).
Sample Rain given Cloudy = true:
Suppose it returns R=true (since we sample from P(R=true | C=true) = 0.8).
Since WetGrass is evidence and fixed to true:
Set weight w→w × P(W='S = false, R = true) = 0.2.
3. Result of the Weighted Sample:
The sampled event is [true, false, true, true] (Cloudy=true, Sprinkler=false, Rain=true,
WetGrass=true) with a weight of 0.2.
4. Tallying the Results:
This event contributes to the count for Rain = true.

Why Likelihood Weighting Works:

o Consistency with Evidence: Likelihood weighting ensures that each sampled event is consistent
with the given evidence (in this case, Cloudy=true and WetGrass=true).
o Weighting by Likelihood: The weight of each event is adjusted based on how likely it is under
the evidence conditions. Events that match the evidence well receive higher weights, improving
the accuracy of the probability estimation.

1. Sampling with Likelihood Weighting: In Bayesian networks, the Sampling with Likelihood
Weighting (SWS) algorithm samples variables (including the query variable) given its parents'
values.
2. Influence of Evidence: SWS considers evidence but less than the true posterior distribution. For
instance, when sampling the Sprinkler variable, it takes into account evidence like "Cloudy = true"
but ignores evidence from variables like "WetGrass = true."
3. Weight Calculation: Each sample's weight compensates for the discrepancy between the actual and
desired sampling distributions. It's calculated based on the likelihoods of evidence variables given
their parents.
4. Weighted Probability: The weighted probability of a sample combines the sampling distribution and
the likelihood weights, ensuring that the overall probability estimate matches the joint probability
distribution.
5. Consistency: Likelihood weighting estimates are consistent, meaning they converge to the true
posterior probability with increasing sample size, as shown by the equation P(x|e) ≈ P(x|e) for large
N.
6. Efficiency and Limitations: Likelihood weighting is more efficient than rejection sampling because it
uses all generated samples. However, its performance degrades with more evidence variables, as
most samples end up with very low weights, skewing the weighted estimate.
7. Impact of Variable Ordering: If evidence variables appear late in the variable order, non evidence
 variables may lack guidance from evidence in their ancestors, resulting in samples that don't reflect
the real-world scenario indicated by the evidence.

1. Objective: Estimate P(X|e), which is the probability of variable X given evidence e.

2. Inputs:
X: Query variable for which we want to estimate the probability.
e: Observed values of evidence variables E.
bn: Bayesian network that defines the joint distribution P( X1,...,Xn).
N: Total number of samples to generate.
3. Local variables:
W: Vector of weighted counts for each value of X, initially set to zero.
4. Algorithm Execution:
Initialization: Start a loop that runs N times to generate samples.
Weighted Sample Generation (Function WEIGHTED-SAMPLE):
Initialize weight w to 1.
Initialize event z with n elements, using values from e.
For each variable X, in X1,...,X n;
If Xi is an evidence variable with a specified value in e.
Update by multiplying it with P(Xi =xi |parents (Xi) ).
Otherwise (if Xi is not evidence):
Sample a value for Xi from P(Xi |parents (Xi) )
Return the event and the weight w.
Weight Accumulation: After generating each sample in WEIGHTED-SAMPLE:
Update W[x] adding w, where x is the value of X in the current sample x.
Normalization: Once all N samples are generated and weights accumulated:
Normalize the vector W to get an estimate of P(X|e).
5. Output: Return the normalized vector W, ↓ich provides an estimate of P(X|e).
Summary: The algorithm generates samples from the Bayesian network conditioned on the evidence
e. For each sample, it calculates a weight based on how consistent the sample is with the observed
evidence. After generating V such samples, it estimates P(X|e) by normalizing the accumulated
weights of the samples where X takes each possible value.

Algorithm-4: Inference by Markov chain simulation

MARKOV CHAIN MONTECARLO Markov chain Monte Carlo (MCMC) algorithms
Markov chain Monte Carlo (MCMC) algorithms work differently than methods like rejection sampling
and likelihood weighting. Instead of creating each sample from scratch, MCMC generates samples by
tweaking the previous sample randomly.
Think of MCMC as being in a current state, where every variable has a value. It moves to a next state
by making random changes to the current state. This process is akin to how simulated annealing or
WALKSAT work, which are also types of MCMC methods.
One specific type of MCMC is Gibbs sampling, which is great for Bayesian networks. Here's how it
works:
Imagine you have variables X and Y, and you want to sample from their joint distribution. Gibbs
sampling does this by iteratively sampling each variable conditioned on the current values of the
others. For instance, if you know the value of Y, you can sample X based on the distribution of X given
Y. Then, you update Y based on the new value of X, and repeat.
This method helps in exploring complex distributions where directly sampling is hard, by gradually
moving through states that approximate the desired distribution.

Gibbs sampling in Bayesian networks

o In Gibbs sampling for Bayesian networks, we start with an initial guess where observed variables
like 'Sprinkler' and 'Wet Grass' are fixed. We then randomly set the values of other variables,
such as 'Cloudy' and 'Rain'. For example, let's say we start with 'Cloudy' as true and 'Rain' as false:
[true, true, false, true].
o The algorithm then updates one variable at a time based on its Markov blanket—its parents,
children, and children's parents. This process continues, flipping variables while keeping the
observed variables fixed.
o This random wandering through possible assignments helps us estimate probabilities like P(Rain
| Sprinkler = true, Wet Grass = true)
Now the nonevidence variables are sampled repeatedly in an arbitrary order. For example:
1. Sampling Cloudy:
o Imagine we're trying to determine if it's cloudy outside. We look at related factors, like if the
sprinkler is on and if it's raining.
o Suppose we know the sprinkler is on and it's not raining. Based on our model, if we find that the
probability of cloudy being false is higher, we update our current situation accordingly.
2. Sampling Rain:
o Next, let's determine if it's raining. This depends on factors like whether it's cloudy, if the
sprinkler is on, and if the grass is wet.
o For instance, if we know it's not cloudy, the sprinkler is on, and the grass is wet, we might find
that rain is likely to be true.
3. Counting States:
o As we go through these steps, each combination of conditions we consider forms a state.
Some states will have rain as true, others as false.
o Let's say we count 20 states where rain is true and 60 states where it's false.
4. Calculating the Probability:
o To answer how likely it is to rain, we normalize the counts we found. This means dividing
the number of true rain states by the total number of states considered.
o In our example, with 20 true rain states and 60 false ones, the normalized probability is
o 0.25 (or 25%) for rain being true and 0.75 (or 75%) for rain being false.
o In Bayesian networks help us compute probabilities by sampling different scenarios based on
known conditions, ultimately giving us a clearer picture of the likelihood of events like rain
occurring.
The complete algorithm is shown in Figure 14.16.
The Gibbs sampling algorithm for approximate inference in Bayesian networks:
The Gibbs sampling algorithm is used for estimating probabilities in Bayesian networks when some
evidence about variables is known.
Markov chains, stationary distributions, and detailed balance:

Gibbs sampling is a method used in Bayesian networks to generate samples from the
posterior distribution of variables given evidence:
1. Gibbs Sampling Overview:
o Gibbs sampling iterates through each variable in the network, updating it based on the current
values of all other variables (including evidence).
o It ensures detailed balance, meaning the sampling process reaches a stationary distribution
equal to the true posterior distribution P( x |e).
2. Transition Probability:
o Each variable X_{i} is updated based on its Markov blanket (MB), which includes its parents
and children in the Bayesian network.
 o For example, if X_{i} has parents Parents(X,) and children Children(X), the conditional
probability is proportional to:
P(xi|mb(Xi)) =α . P(xi|Parents(Xi)) x∏ YjℇChildren(Xi) P(y) Parents(Yj))
3. Detailed Balance:
o Gibbs sampling maintains detailed balance by ensuring:
∏ (x) qi(x→x) =P(x|e)qi (x→ x)
where ∏(x) is the true posterior and qi(x → x) is the transition probability for variable Xi
4. Ergodicity and Stationarity:
o If the conditional probability distributions q_{i} for each variable maintain the stationary
distribution P( x |e) and the network is connected (no probabilities of 0 or 1 causing
disconnects), Gibbs sampling is ergodic. This means it eventually samples from P( x |e)
5. Implementation:
o To perform Gibbs sampling:
o Start with initial values for all variables..
o Sequentially update each variable Xi using its Markov blanket until convergence.
o Repeat until enough samples are obtained from P( x |e).

RELATIONAL AND FIRST-ORDER PROBABILITY

Representational Advantages of First-Order Logic vs. Bayesian Networks
In Chapter 8, explored how first-order logic improves upon propositional logic by allowing more
concise expression of relationships among objects and properties. This is crucial in domains with
varying numbers of objects and complex interactions.
Limitations of Bayesian Networks
Bayesian networks are constrained by their propositional nature, limiting them to fixed sets of
variables and predefined value domains. This can restrict their applicability in scenarios with
nuanced interactions.
Example Scenario: Assessing Book Quality with Customer Recommendations
Consider an online book retailer analyzing book quality based on customer recommendations:
 Bayesian Networks Approach: A basic method might average recommendations, adjusting for
variance based on the number received. This overlooks factors like varying customer honesty and
kindness, which can bias recommendations.
 First-Order Logic Approach: Here, each customer's recommendation for a book (e.g., recommending
Book A to Customer X) can be represented with variables such as Honest(X), Kindness(X), and
Quality(Book A). Rather than manually specifying these relationships repeatedly, first-order logic
uses a structured approach where the recommendation (Recommendation(X, Book A)) depends on
these variables.
Example in First-Order Logic:
plaintext Copy code
Recommendation(X, Book A) ∼ RecCPT(Honest(X), Kindness(X), Quality(Book A))
This states that the recommendation of Book A by Customer X follows a Conditional Probability Table
(CPT), which considers the variables Honest(X), Kindness(X), and Quality (Book A).
Benefits of First-Order Logic:
 Flexibility: It allows for a more flexible representation of complex interactions among customers and
books.
 Scalability: Easily scales with increasing numbers of customers and books without the need for
repetitive manual adjustments to the network structure.
 Nuanced Analysis: Enables a nuanced analysis by capturing diverse customer behaviors and book
attributes that a fixed Bayesian network structure may struggle to accommodate.
 Bayesian networks are useful for certain structured problems, first-order logic provides a more
adaptable framework for modeling dynamic and intricate relationships in domains where such
variability is significant.
Possible worlds
1. Possible Worlds in Probability Models:
In probability theory, a set of possible worlds, denoted as Ω, represents all conceivable scenarios or
states of affairs.
Each world ω in Ω has an associated probability P(ω), which tells us how likely that particular world
is.
Example: Consider a coin toss where Ω = {Heads, Tails}. If we assume a fair coin, P(Heads) = P(Tails) =
0.5.
2. Possible Worlds in Bayesian Networks:
In Bayesian networks, possible worlds are specific assignments of values to variables that satisfy the
network's structure and conditional probabilities.
Example: Imagine a Bayesian network for diagnosing diseases, where variables could be {Symptoms,
Disease}. Possible worlds would be {Fever, Flu} or {No Fever, No Flu}, etc.
3. First-Order Probability Models:
For first-order logic, possible worlds involve a richer structure. They encompass sets of objects with
relations among them, akin to the semantics of first-order logic.
Example: Suppose we have a domain with objects {Alice, Bob} and a relation Likes(x, y) which denotes
x likes y. Possible worlds would include assignments such as
{Likes(Alice, Bob)} or {Likes(Bob, Alice)}.
4. Challenges with Infinite Sets of Worlds:
One issue with first-order models is that the set of possible worlds can be infinite. For instance, if we
have an infinite number of individuals (objects) and relations, the number of possible worlds
becomes uncountably large.
5. Dealing with Infinite Sets:
To manage this, one approach is to adopt database semantics, where we assume a finite set of
possible worlds by restricting the domain to named constants (unique names assumption) and
ensuring domain closure (no unnamed objects).
Example: In a domain of books and readers, if we only consider named readers {Alice, Bob} and books
{Book1, Book2}, possible worlds are constrained to combinations like {Alice likes Book1, Bob likes
Book2}.
The first-order logic allows for rich modeling of complex scenarios, managing infinite sets of possible
worlds poses challenges. Techniques like database semantics help in restricting these sets to
manageable sizes for probabilistic reasoning.
Relational Probability Model
In a Relational Probability Model (RPM), we deal with uncertainty about how symbols correspond to
real-world objects. Unlike traditional databases that assume everything not known is false, RPMs
acknowledge uncertainties like whether different symbols refer to the same object or how many
objects exist.
For example, imagine a book retailer using ISBNs to identify books. A single book like "Gone With the
Wind" might have multiple ISBNs, which complicates tracking recommendations or sales across
different identifiers. Similarly, customers using multiple login IDs can confuse systems meant to
track reputation, like in online reviews or security systems.
These uncertainties are critical because:
1. Existence Uncertainty: We're unsure about which objects truly exist behind the symbols we
observe. For instance, how many distinct copies of "Gone With the Wind" are there?
2. Identity Uncertainty: We may not be certain which symbols actually refer to the same underlying
object. For example, are two different ISBNs really identifying the same physical book?
RPMs help us model scenarios where what we observe (like ISBNs or customer IDs) might not perfectly
reflect the underlying reality (actual books or unique customers). This flexibility in handling
uncertainty makes RPMs useful in areas like online retail and security where clear identifications
can be tricky due to various factors.
Relational Probability Models
Relational Probability Models (RPMs) are similar to first-order logic but use symbols for constants,
functions, and predicates. Predicates act like functions that determine true or false statements.
In the context of recommending books to customers, here are the key elements simplified:
1. Symbols and Types:
Constants: Names of customers (like C1, C2) and books (like B1, B2).
Functions (returning values):
 Honest: Determines if a customer is honest (Honest(C1)).
 Kindness: Rates the kindness of a customer (Kindness(C1)).
 Quality: Rates the quality of a book (Quality(B1)).
 Recommendation: Rates how likely a customer recommends a specific book
(Recommendation(C1, B1)).
Each function has specific types for its arguments and return values:
o Honestand Kindnessare boolean (true/false).
o Qualityis rated on a scale of 1 to 5.
o Recommendationis rated on a scale of 1 to 5.
2. Random Variables:
RPM defines random variables by instantiating each function with specific combinations of
customers and books. For instance:
 Honest(C1), Honest(C2), etc.
  Quality(B1), Quality(B2), etc.
 Recommendation(C1, B1), Recommendation(C1, B2), etc.
3. Dependencies:
Each function has dependencies that govern its behavior. These are statements about the likelihood
of certain values based on other factors:
 Honest(c)might have probabilities like 0.99 for true and 0.01 for false.
 Kindness(c) might have probabilities like 0.1, 0.1, 0.2, 0.3, 0.3 for its ratings.
 Quality(b) might have probabilities like 0.05, 0.2, 0.4, 0.2, 0.15 for its ratings.
 Recommendation(c, b)'s probability might be derived from a conditional distribution table
(RecCPT) based on the honesty, kindness, and quality values associated with c and b.
4. Bayesian Network:
By instantiating these dependencies for all known customers and books, RPM forms a Bayesian
network.
This network defines a joint probability distribution over all the random variables, representing how
likely different states (like honesty, kindness, quality, recommendation) are given the relationships
between customers and books.
RPMs help model relationships and probabilities between entities like customers and books, enabling
systems to make informed predictions and recommendations based on data and logical dependencies
defined for each entity.
Context Specific Independence
Imagine a scenario where customers give recommendations for books. Some customers are honest,
while others might not be truthful in their reviews. Dishonest customers might ignore a book's
quality when recommending it, and their kindness doesn't affect their decisions.
Conditional Dependence Example
1. Basic Independence Example:
o If a customer c is dishonest (Honest(c) = false), their recommendation ( Recommendation(c,
b)) doesn't depend on how kind they are (Kindness(c)) or the book's quality (Quality(b)).
o For honest customers (Honest(c) true), their recommendation depends on both kindness and
quality.
2. Adding Fan of an Author:
An honest customer who is a fan of a specific author (Fan(c, Author(b))) always gives the author's
books a perfect rating of 5, regardless of the book's quality.
Otherwise, they use a more nuanced recommendation rule ( Honest RecCPT(Kindness(c), Quality(b))).
Handling Uncertainty
1. Unknown Author Example:
o If we don't know who the author of a book B2 is (Author(B2)), we might have to consider all
possible authors, say A1 and A2.
o Each potential author (like A1 or A2) could be favored by a customer (Fan(C1, A1), Fan(C1,
A2)), influencing their recommendation.
2. Relational Uncertainty:
o The uncertainty about Author(B2) affects how the recommendation system works. If three
customers are all fans of Al and have given B2 a perfect score, it strongly suggests that Al is
likely the author of B2.
 1. Emergence of Sophisticated Reasoning: RPM models demonstrate how probabilities spread
through connections among objects, leading to clearer and more reliable results as
connections and objects increase.
2. Inference in RPMs: "Unrolling" involves gathering evidence and queries about constant
symbols to construct an equivalent Bayes network for inference.
3. Drawbacks of Unrolling: The resulting Bayes network can become very large, especially
with many possible objects related to unknown functions or relations.
4. Improving Standard Inference Methods: Techniques like caching can speed up
computations by exploiting repeated structures in the unrolled Bayes network.
5. Adapting Methods for RPMs: Methods that exploit specific contexts and MCMC algorithms
are beneficial for handling relational uncertainty in RPMs.
6. MCMC Algorithm: Samples potential scenarios where relational structures are fully
understood, simplifying dependencies for each scenario and managing relational uncertainty
effectively.
7. Comparison with Logical Inference: RPMs require partial unrolling into Bayesian networks
similar to how logical propositions are handled in first-order logical inference.
8. Alternative Approaches: Systems like resolution theorem provers and logic programming
avoid exhaustive unrolling by instantiating logical variables as needed, akin to the lifting
approach in probabilistic inference.
Enhancing Book Rating Predictions: Managing Author Uncertainty and Customer Bias
Imagine a website where customers rate books. Some users are honest in their reviews, while others
might not be truthful. Dishonest reviewers ignore a book's quality and their kindness doesn't
influence their ratings.
For example:
o An honest customer might always give books by their favorite author a perfect rating of 5.
o If we don't know who wrote a certain book, we have to consider all possible authors and how
much customers like each author to predict their ratings accurately.
This system deals with uncertainty about book authors and customer preferences to make better
predictions about book ratings.

Open-universe probability models (Managing Ambiguity in Real-World Object Identification)

1. Unlike in databases with unique IDs, real-life systems like cameras, text processors, and
intelligence analysis deal with ambiguity.
2. Cameras may not recognize if the object around a corner is the same as seen earlier.
3. Text processors must determine if different mentions (e.g., "Mary," "Dr. Smith," "she") refer
to the same entity.
4. Intelligence analysts track spies without knowing how many there are or if various
identifiers belong to the same spy.
5. Human understanding involves learning what objects exist and linking observations
 without clear, unique identifiers.
6. Dealing with uncertainty is a crucial challenge in these contexts.
OPEN UNIVERSE
Open-Universe Probability Models (OUPMs) compared to Bayesian Networks and their application
in a book-recommendation context:
1. Purpose: OUPMs maintain a consistent probability distribution across all scenarios by allowing
creation of new objects.
2. Comparison with Bayesian Networks:
o OUPMs create and define distributions over new objects dynamically.
o Bayesian networks use predefined structures to assign values to variables.
3. Generating Objects:
o OUPMs model scenarios with variable numbers and types of objects.
o Example: Predicting customer count and their login IDs using probabilistic distributions.
4. Example in Book-Recommendation Domain:
o OUPMs predict customer numbers via distributions like log-normal.
o They differentiate between honest and dishonest customers with distinct distribution
patterns for login IDs.
5. Overall Benefit: OUPMs offer a robust framework for probabilistic modeling by ensuring
consistent distributions across all possible object configurations.

Customer Behavior Modeling with Log-Normal Distributions:

1. We expect between 100 and 10,000 customers, represented by a log-normal
distribution with parameters μ = 6.9 and σ = 2.32.
2. For honest customers, each customer has exactly one ID.
3. For dishonest customers, the number of IDs follows a log-normal distribution with the same
parameters μ = 6.9 and σ = 2.32.
Origin Function:
In BLOG, imagine a system where each customer has several unique login IDs. Each possible scenario
or "world" in this system shows exactly how these IDs were created. To ensure accuracy, the system
follows specific rules to calculate probabilities across all these scenarios. Algorithms in BLOG can
figure out answers to questions about these scenarios, getting closer to the true likelihoods over
time. It's tricky to design these algorithms, especially when dealing with endless possibilities. Despite
these challenges, using first-order logic for probabilistic reasoning significantly improves AI's ability
to handle uncertain information, like in computer vision or intelligence analysis.

OTHER APPROACHES TO UNCERTAIN REASONING: DEMPSTER–SHAFER THEORY

Dempster-Shafer Theory was given by Arthur P. Dempster in 1967 and was later developed by his
student Glenn Shafer in 1976. This theory was released because of the following reason:-
o Bayesian theory is only concerned about single evidence.
o Bayesian probability cannot describe ignorance.
Dempster Shafer Theory (DST) is an evidence theory, it combines all possible outcomes of the
problem. Hence it is used to solve problems where there may be a chance that a piece of different
evidence will lead to some different result.
The uncertainty in this model is given by:-
1. Consider all possible outcomes.
2. Belief will lead to belief in some possibility by bringing out some evidence. (What is this
supposed to mean?)
3. Plausibility will make evidence compatible with possible outcomes.
The Dempster–Shafer theory DEMPSTER–SHAFER is designed to deal with the distinction between
uncertainty and ignorance. Rather than computing the probability of a proposition, it computes the
probability that the evidence supports the proposition. This measure of belief is called a belief
function, written Bel(X).
The mathematical formulation of Dempster–Shafer theory is similar to those of probability theory;
the main difference is that, instead of assigning probabilities to possible worlds, the theory assigns
masses to sets of possible world, that is, to events.
The masses still must add to 1 over all possible events. Bel(A) is defined to be the sum of masses for
all events that are subsets of (i.e., that entail) A, including A itself. With this definition, Bel(A) and
Bel(¬A) sum to at most 1, and the gap—the interval between Bel(A)and 1 − Bel(¬A)—is often
interpreted as bounding the probability of A.

As with default reasoning, there is a problem in connecting beliefs to actions. Whenever there is a
gap in the beliefs, then a decision problem can be defined such that a Dempster–Shafer system is
unable to make a decision.
Bel(A) should be interpreted not as a degree of belief in A but as the probability assigned to all
the possible worlds (now interpreted as logical theories) in which A is provable.

Example:
Let us consider a room where four person are presented A, B, C, D(lets say) And suddenly lights out
and when the lights come back B has been died due to stabbing in his back with the help of a knife.
No one came into the room and no one has leaved the room and B has not committed suicide. Then
we have to find out who is the murderer?
o Either {A} or{C} or {D} has killed him.
o Either {A, C} or {C, D} or {A, C} have killed him.
o Or the three of them kill him i.e; {A, C, D}
o None of the kill him {o}(let us say).
These will be the possible evidences by which we can find the murderer by measure of
plausibility. Using the above example we can say:
Set of possible conclusion (P): {p1, p2..... pn} where P is set of possible conclusion and cannot be
exhaustive means at least one (p)i must be true.(p)i must be mutually exclusive. Power Set will contain
2n elements where n is number of elements in the possible set.
For example:
If P = { a, b, c}, then Power set is given as {o, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c}}= 23 elements.
Mass function m(K): It is an interpretation of m({K or B}) i.e; it means there is evidence for {K or B}
which cannot be divided among more specific beliefs for K and B.
Belief in K: The belief in element K of Power Set is the sum of masses of element which are subsets of
K. This can be explained through an example
Lets say K = {a, b, c}
Bel(K) = m(a) + m(b) + m(c) + m(a, b) + m(a, c) + m(b, c) + m(a, b, c)
Plausibility in K: It is the sum of masses of set that intersects with K. i.e; Pl(K) = m(a) + m(b) + m(c) +
m(a, b) + m(b, c) + m(a, c) + m(a, b, c)Characteristics of Dempster Shafer Theory:
It will ignorance part such that probability of all events aggregates to 1. Ignorance is reduced in this
theory by adding more and more evidences. Combination rule is used to combine various types of
possibilities.
Advantages:
o Uncertainty interval reduces.
o DST has much lower level of ignorance.
o Diagnose Hierarchies can be represented using this.
o Person dealing with such problems is free to think about evidences.
Disadvantages:
o In this computation effort is high, as we have to deal with 2n of sets.