Artificial Intelligence

Module-3
Planning and Its Importance

[Link] 5th Semester

Instructor:
Prof. Rabindra Kumar Shial
Planning and Its Importance

• Planning in artificial intelligence is about decision-

making actions performed by robots or computer
programs to achieve a specific goal.
• Execution of the plan is about choosing a sequence of
tasks with a high probability of accomplishing a specific
task.
Planning problem:
• Find a sequence of actions that lead to a goal
• This requires to model and reason about effects of agent’s
actions on the real-world.

Planning problem:
– is a special type of a search problem
• State space: states of the world.
• Initial state: A world state we start from.
• Operators. Application of actions that change the state.
• Goal condition. Desired state of the world
Specifics of a planning problem:
• Complex description of world states
• Large number of actions
• Every action effects only a “small” subset of relations in
the state
• Goals are defined over a “small” set of relations
This causes:
• a large branching factor of the search tree,
• long action sequences (solution length is large)
 Planning systems design.

Two planning systems designs:

• Situation calculus
– based on first-order logic,
– a situation variable models new states of the world
– use inference methods developed for FOL to do the reasoning
• STRIPS –planners
– STRIPS – Stanford research institute problem solver
– Restricted language as compared to the situation calculus
– Allows for more efficient planning algorithms
 Classical Planning
• Classical Planning is the planning where an
agent takes advantage of the problem
structure to construct complex plans of an
action.
• The agent performs three tasks in classical
planning:
• Planning: The agent plans after knowing
what is the problem.
• Acting: It decides what action it has to
take.
• Learning: The actions taken by the agent
make him learn new things.
• A language known as PDDL(Planning Domain Definition Language) which
is used to represent all actions into one action schema.
PDDL describes the four basic things needed in a search problem:
• Initial state: It is the representation of each state as the conjunction of the
ground and functionless atoms.
• Actions: It is defined by a set of action schemas which implicitly define the
ACTION() and RESULT() functions.
• Result: It is obtained by the set of actions used by the agent.
• Goal: It is same as a precondition, which is a conjunction of literals (whose
value is either positive or negative).
There are various examples which will make PDLL understandable:
• Air cargo transport
• The spare tire problem
• The blocks world and many more.
Let’s discuss one of them
1. Air cargo transport
• This problem can be illustrated with the help of the following actions:
• Load: This action is taken to load cargo.
• Unload: This action is taken to unload the cargo when it reaches its
destination.
• Fly: This action is taken to fly from one place to another.
• Therefore, the Air cargo transport problem is based on loading and
unloading the cargo and flying it from one place to another.
2. The spare tire problem
• The problem is that the agent needs to change the flat tire. The aim is to
place a good spare tire over the car’s axle.
• There are four actions used to define the spare tire problem:
• Remove the spare from the trunk.
• Remove the flat spare from the axle.
• Putting the spare on the axle.
• Leave the car unattended overnight. Assuming that the car is parked at an
unsafe neighborhood.
The PDLL description for the spare tire problem is:

• Init(Tire1(Flat ) ? Tire1(Spare) ? At(Flat , Axle) ? At(Spare, Trunk ))

• Goal (At(Spare, Axle))
• Action(Remove(obj , loc),
• PRECOND: At(obj , loc) EFFECT: ? At(obj , loc) ? At(obj , Ground))
• Action(PutOn(t , Axle),
• PRECOND: Tire1(t) ? At(t , Ground) ?¬At(Flat , Axle)
• EFFECT: ? At(t , Ground) ? At(t , Axle)) Action(LeaveOvernight)
• PRECOND:
• EFFECT: ? At(Spare, Ground) ?¬At(Spare, Axle) ?¬At(Spare, Trunk) ?¬At(Flat,
Ground) ?¬At(Flat , Axle) ?¬At(Flat, Trunk))

The solution to the problem is:

[Remove(Flat,Axle),Remove(Spare,Trunk), PutOn(Spare, Axle)].
Complexity of the classical planning

In classical planning, there occur following two decision problems:

• PlanSAT: It is the question asking if there exists any plan that solves a planning
problem.
• Bounded PlanSAT: It is the question asking if there is a solution of length k or less
than it.
We found that:
• PlanSAT and Bounded PlanSAT are decidable for classical planning.
• Both decision problems lie in the complexity class PSPACE, which is larger than NP.
Note: PSPACE is the class which refers to those problems that can be solved via
deterministic Turing machine under a polynomial time space.
From the above, it can be concluded that:
• PlanSAT is P whereas Bounded PlanSAT is NP-complete.
• Optimal planning is hard with respect to sub-optimal planning.
Advantages of Classical Planning

There are following advantages of Classical planning:

• It has provided the facility to develop accurate domain-independent heuristics.
• The systems are easy to understand and work efficiently.
 Partial order planning
• Partial-order planning (pop) is an approach to a problem it works on the
decomposition of problem into sub-problems,
• The solution of sub problems are sub goals, each sub goal have sub-plans to solve
them.
• Finally it combines all the sub goals to give solution for final goal state.
• A partial-order planner maintains a partial ordering between actions and only
commits to an ordering between actions when forced.
• This is sometimes also called a non-linear planner, which is a misnomer because
such planners often produce a linear plan.
• A partial ordering is a binary relation that is transitive and asymmetric.
• A partial-order plan is a set of action instances together with a partial ordering
between them, representing a “before” relation on action instances.
• Write act0<act1 if action instance act0 is before action instance act1 in the partial
order. This means that the action of act0 must occur before the action of act1.
• The aim of the planner is to produce a partial ordering of the action instances so
that any total ordering consistent with the partial ordering will solve the goal from
the initial state.
• There are two special action instances, start, that achieves the relations that are
true in the initial state, and finish, whose precondition is the goal to be solved.
• Every other action instance is after start and before finish in the partial ordering.
• The use of these as action instances means that the algorithm does not require
special cases for the initial situation and for the goals. When the preconditions of
finish are achieved, the goal is solved.
• Any action instance, other than start or finish, will be in a partial-order plan to
achieve a precondition of an action instance in the plan.
• Each precondition P of an action instance act1 in the plan is either true in the
initial state, and so achieved by start, or there will be an action instance act0 in the
plan that achieves P.
• The action instance act0 that achieves P must be before act1; that is, act0<act1.
• To be correct, the algorithm must also ensure that nothing makes P false in
between act0 and act1.
 Example :

• In partial ordered planning (POP), ordering of

the actions is partial. Also partial ordered
planning don’t specify which action will come
first out of the two actions which are placed.
• With partial ordered planning, problem can be
decomposed, so it can work well in case the
environment is non-cooperative.
• It combines two action sequence:
i. First branch covers left sock and left shoe.
ii. In case, to wear a left shoe, wearing left sock is
precondition, similarly.
iii. Second branch covers right shock and right
shoe.
iv. Here, wearing a right shock is precondition for
wearing the right shoe.
• Once these actions are taken we achieve our
goal and reach the finish state.
• E.g. Partial order planning of Wearing Shoe
Pop as search problem:
Set of actions:
These are the steps of plan.
For e.g.: Set of Actions = {Start, Rightsock,
Rightshoe ,Leftsock, Leftshoe, Finish}
Set of ordering constraints/preconditions:
i. Preconditions are considered as ordering
constraints.(i.e. without performing action “x”
we cannot perform action “y”)
ii. For e.g.: Set of ordering = {Right-sock <right-
shoe; left-sock<left-shoe}
Set of causal links:
• Action A achieves effect “E” for action B
i. You can understand that if you buy an apple its effect can be eating an apple and the
precondition of eating an apple is cutting apple.
ii. For e.g. Set of Causal Links = {Right-sock-> Right-sock-on
• Set of open preconditions:
i. Preconditions are called open if it cannot be achieved by some actions in the plan.
ii. Consistent Plan is a Solution for POP Problem
iii. A consistent Plan doesn’t have cycle of constraints; it doesn’t have conflicts in the
causal links and doesn’t have open preconditions so it can provide a solution for POP
problem.
 Conditional Planning
• Conditional planning has to work regardless of the outcome of an action.
• It takes place in Fully Observable Environment where the current state of the
agent is known environment is fully observable. The outcome of actions cannot be
determined so the environment is said to be nondeterministic.
• Here we can check what is happening in environment at pre-determined points of
the plan to deal with ambiguous actions.
• It needs to take some actions at every state and must be able to handle every
outcome for the action it takes. A state node is represented with a square and
chance node is represented with a circles.
• For a state node we have an option of choosing some actions. For a chance node
agent has to handle every outcome.
• Conditional Planning can also take place in the Partially Observable Environments
where, we cannot keep a track on every state.
• In vacuum cleaner e.g. if the dirt is at Right and agent knows about Right, but not
about Left. Then, in such cases Dirt might be left behind when the agent, leaves a
clean square. Initial state is also called as a state set or a belief state.
• Sensors play important role in Conditional planning for partially observable
environments. Automatic sensing can be useful; with automatic sensing an agent
gets all the available percepts at every step.
Uncertainty
• Till now, we have learned knowledge representation using first-order logic and
propositional logic with certainty, which means we were sure about the
predicates. 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.
• 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.
• Information occurred from unreliable sources.
• Experimental Errors
• Equipment fault
• Temperature variation
• Climate change.
 Types of Uncertainty

• There are two sources of uncertainty that affect machine learning algorithms,
epistemic and aleatoric.
• Predictive uncertainty is also a useful notion that allows us to quantify the true
level of uncertainty in a model.
1. Epistemic Uncertainty
- Epistemic uncertainty refers to the model’s uncertainty due to the lack of training
data.
- It is reducible, which means it can be lowered by providing additional data.
- Its dependent on how appropriate the data is, which entails relevant, annotated
and high-quality data points.
- High epistemic uncertainty occurs when the input data is far away from the
training data, and low epistemic uncertainty for data points near the training data.
- Using a narrow dataset as a baseline, the model would only perform well for
inputs within that range.
- Epistemic uncertainty is a high-agenda problem for real-world applications, which
may have datasets which are rich in quantity and poor in quality.
2. Aleatoric Uncertainty
- Compared to epistemic uncertainty, which refers to the lack of data, aleatoric
uncertainty refers to the inherent stochasticity of the observations.
- When data is captured, it is not a perfect representation of reality, but it is
contaminated by noise and randomness.
- Every observation has inherent noise that cannot be controlled, and accumulated, all
the noise across observations add up to the model’s aleatoric uncertainty.
- While epistemic uncertainty can be reduced with additional observations, aleatoric
cannot.
- Additional data will also include noise captured at the moment of the observation.
- This type of uncertainty is not a property of the model, but rather is an inherent
property of the data distribution, and as such, irreducible.
- That’s why aleatoric uncertainty is also known as data uncertainty. It can be captured
by probabilistic classification and regression models.
- One way to estimate aleatoric uncertainty is by using data augmentation during the
testing phase.
Probabilistic reasoning:
• Probabilistic reasoning is a way of knowledge representation where we apply the
concept of probability to indicate the uncertainty in knowledge. In probabilistic
reasoning, we combine probability theory with logic to handle the uncertainty.
• We use probability in probabilistic reasoning because it provides a way to handle
the uncertainty that is the result of someone's laziness and ignorance.
• In the real world, there are lots of scenarios, where the certainty of something is
not confirmed, such as "It will rain today," "behavior of someone for some
situations," "A match between two teams or two players." These are probable
sentences for which we can assume that it will happen but not sure about it, so
here we use probabilistic reasoning.
Need of probabilistic reasoning in AI:
• When there are unpredictable outcomes.
• When specifications or possibilities of predicates become too large to handle.
• When an unknown error occurs during an experiment.
• In probabilistic reasoning, there are two ways to solve problems with uncertain
knowledge: Bayes' rule
Bayesian Statistics
• As probabilistic reasoning uses probability and related terms, so before understanding
probabilistic reasoning, let's understand some common terms:
• Probability: Probability can be defined as a chance that an uncertain event will occur. It
is the numerical measure of the likelihood that an event will occur. The value of
probability always remains between 0 and 1 that represent ideal uncertainties.
• 0 ≤ P(A) ≤ 1, where P(A) is the probability of an event A.
• P(A) = 0, indicates total uncertainty in an event A.
• P(A) =1, indicates total certainty in an event A.
• We can find the probability of an uncertain event by using the below formula.

• P(¬A) = probability of a not happening event.

• P(¬A) + P(A) = 1.
• Event: Each possible outcome of a variable is called an event.
• Sample space: The collection of all possible events is called sample space.
• Random variables: Random variables are used to represent the events and objects in
the real world.
• Prior probability: The prior probability of an event is probability computed before
observing new information.
• Posterior Probability: The probability that is calculated after all evidence or information
has taken into account. It is a combination of prior probability and new information.
Conditional probability:
• Conditional probability is a probability of occurring an event when another event
has already happened.
• Let's suppose, we want to calculate the event A when event B has already
occurred, "the probability of A under the conditions of B", it can be written as:

• Where P(A⋀B)= Joint probability of a and B

• If the probability of A is given and we need to find the probability of B, then it will
be given as:

• It can be explained by using the below Venn diagram, where B is occurred event,
so sample space will be reduced to set B, and now we can only calculate event A
when event B is already occurred by dividing the probability of P(A⋀B) by P( B ).
• Example:
• In a class, there are 70% of the students
who like English and 40% of the students
who likes English and mathematics, and
then what is the percent of students
those who like English also like
mathematics?
• Solution:
• Let, A is an event that a student likes
Mathematics
• B is an event that a student likes English.

• Hence, 57% are the students who like

English also like Mathematics.
 Joint Probability Distribution reasoning
• A Joint Probability Distribution is the distribution of Joint Probabilities.
• A Joint Probability is the probability of specific values of variables jointly occurring
in a domain.
Example
• We observe the variables Hair Color and Eye Color in a population of college
students.
• Joint Probability refers to the probability of specific values for Hair Color and Eye
Color jointly occurring in this population.
• For instance,
– P(Eye Color=Blue, Hair Color=Brown)=15.86% means that the probability of a
student having blue eyes and Brown hair in the given population is 15.86%.
– P(Eye Color=Green, Hair Color=Black)=0.85% means that the probability of
having green eyes and black hair in that population is only 0.85%.
• We can now look across all possible combinations of Hair Color and Eye Color,
compute all Joint Probabilities and list them in a Joint Probability Table, with one
row for each combination of the states of the variables.
• In this example, the size of the Joint Probability Table is manageable: Number of
States (Hair Color) × Number of States (Eye Color) = 3 × 3 = 9
• This Joint Probability Table is a direct and complete representation of the Joint
Probability Distribution for the variables Hair Color and Eye Color:

Hair Color Eye Color Joint Probability

Black Brown 11.49%
Brown Brown 20.10%
Red Brown 4.39%
Black Blue 3.38%
Brown Blue 14.19%
Red Blue 2.87%
• As the Joint Probability Distribution covers all possible combinations, it represents
all regularities and patterns (or the lack thereof) within a domain.
• Knowing the Joint Probability Distribution is required for performing two key
operations for data analysis and inference:
– Marginalization, which is calculating the marginal probability of a variable,
e.g., P(Hair Color=Black)=18.25%.
– Conditioning, which refers to inferring the values of a variable, given a specific
value of another variable, e.g. P(Hair Color=Blond | Eye Color=Blue)=43.7%.
Challenges
• In high-dimensional domains, however, calculating and listing the Joint
Probabilities in a Joint Probability Table can become intractable.
• The size of a Joint Probability Table grows exponentially with the number of
variables. For example, if we had 20 variables with 3 states each, the size of the
corresponding Joint Probability Table would exceed 1 trillion rows.
• While the arithmetic is straightforward, the sheer number of calculations can
easily exceed the available computational power, both for generating the Joint
Probability Table as well as for performing Marginalization and Conditioning.
 Bayesian Networks
• A Bayesian network is a probabilistic graphical model which represents a set of
variables and their conditional dependencies using a directed acyclic graph."
• It is also called a Bayes network, belief network, decision network, or Bayesian
model.
• Bayesian networks are probabilistic, because these networks are built from a
probability distribution, and also use probability theory for prediction and
anomaly detection.
• Real world applications are probabilistic in nature, and to represent the
relationship between multiple events, we need a Bayesian network. It can also be
used in various tasks including prediction, anomaly detection, diagnostics,
automated insight, reasoning, time series prediction, and decision making under
uncertainty.
• Bayesian Network can be used for building models from data and experts opinions,
and it consists of two parts:
– Directed Acyclic Graph
– Table of conditional probabilities.
• The generalized form of Bayesian network that represents and solve decision
problems under uncertain knowledge is known as an Influence diagram.
• A Bayesian network graph is made up of nodes and Arcs (directed links), where:

•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.
•Each node corresponds to the random variables,
and a variable can be continuous or discrete.

• 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
• In the above diagram, A, B, C, and D are random variables represented by the nodes
of the network graph.
• 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.
• Node C is independent of node A.
The Bayesian network has mainly two components:
– Causal Component
– Actual numbers

• Each node in the Bayesian network has condition probability distribution P(Xi
|Parent(Xi) ), which determines the effect of the parent on that node.
• Bayesian network is based on Joint probability distribution and conditional
probability. So let's first understand the joint probability distribution:
Joint probability distribution:
• If we have variables x1, x2, x3,....., xn, then the probabilities of a different
combination of x1, x2, x3.. xn, are known as Joint probability distribution.
• P[x1, x2, x3,....., xn], it can be written as the following way in terms of the joint
probability distribution.
= P[x1| x2, x3,....., xn]P[x2, x3,....., xn]
= P[x1| x2, x3,....., xn]P[x2|x3,....., xn]....P[xn-1|xn]P[xn].
• In general for each variable Xi, we can write the equation as:
P(Xi|Xi-1,........., X1) = P(Xi |Parents(Xi ))
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.
 Learning

• Learning is one of the fundamental building blocks of artificial intelligence

(AI) solutions. From a conceptual standpoint.
• Learning is a process that improves the knowledge of an AI program by
making observations about its environment.
• Machine learning is a subfield of artificial intelligence, which is broadly
defined as the capability of a machine to imitate intelligent human
behavior.
• Artificial intelligence systems are used to perform complex tasks in a way
that is similar to how humans solve problems.
 Explanation-Based learning (EBL)
• In simple terms, it is the ability to gain basic problem-solving techniques by
observing and analyzing solutions to specific problems.
• In terms of Machine Learning, it is an algorithm that aims to understand why an
example is a part of a particular concept to make generalizations or form concepts
from training examples.
• For example, EBL uses a domain theory and creates a program that learns to play
chess.
Intuition:
• The objective of EBL is to understand the essential properties of a particular
concept.
• So, we need to find out what makes an example, part of a particular concept.
Unlike FOIL algorithm, here we focus on the one example instead of collecting
multiple examples.
• The ability to explain single examples is known as “Domain Theory”.
• An EBL accepts 4 kinds of input:
i) A training example: what the learning model sees in the world.
ii) A goal concept: a high level description of what the model is supposed to learn.
iii) A operational criterion: states which other terms can appear in the generalized
result.
iv) A domain theory: set of rules that describe relationships between objects and
actions in a domain.
EBL involves 2 steps:
• Explanation — The domain theory is used to eliminate all the unimportant training
example while retaining the important ones that best describe the goal concept.
• Generalization — The explanation of the goal concept is made as general and
widely applicable as possible. This ensures that all possible cases are covered, not
just certain specific ones.
EBL Architecture:
• EBL model during training
– During training, the model generalizes the training example in such a way that
all scenarios lead to the Goal Concept, not just in specific cases. (As shown in
Fig)
EBL model after training
– Post training, EBL model tends to directly reach the hypothesis space involving
the goal concept. (As shown in Fig )
 Induction / Inductive Learning Algorithm

• Inductive Learning Algorithm (ILA) is an iterative and inductive machine learning

algorithm which is used for generating a set of a classification rule, which produces
rules of the form “IF-THEN”, for a set of examples, producing rules at each iteration
and appending to the set of rules.
• Basic Idea: There are basically two methods for knowledge extraction firstly from
domain experts and then with machine learning.
• For a very large amount of data, the domain experts are not very useful and
reliable. So we move towards the machine learning approach for this work.
• To use machine learning One method is to replicate the experts logic in the form of
algorithms but this work is very tedious, time taking and expensive.
• So we move towards the inductive algorithms which itself generate the strategy
for performing a task and need not instruct separately at each step.
 Induction Learning-Decision Tree

• Decision Tree is a supervised learning method used in data mining for classification
and regression methods.
• It is a tree that helps us in decision-making purposes. The decision tree creates
classification or regression models as a tree structure.
• It separates a data set into smaller subsets, and at the same time, the decision tree
is steadily developed.
• The final tree is a tree with the decision nodes and leaf nodes. A decision node has
at least two branches.
• The leaf nodes show a classification or decision. We can't accomplish more split on
leaf nodes-
• The uppermost decision node in a tree that relates to the best predictor called the
root node.
• Decision trees can deal with both categorical and numerical data.
Key factors:
• Entropy:
• Entropy refers to a common way to measure impurity. In the
decision tree, it measures the randomness or impurity in data
sets.

• Information Gain:
• Information Gain refers to the decline in entropy after the
dataset is split. It is also called Entropy Reduction. Building a
decision tree is all about discovering attributes that return the
highest data gain.

• In short, a decision tree is just like a flow chart diagram with

the terminal nodes showing decisions. Starting with the
dataset, we can measure the entropy to find a way to
segment the set until the data belongs to the same class.
Specification about Decision trees :
• Decision tree is a hierarchical tree structure that can be used to split an extensive
collection of records into smaller sets of the class by implementing a sequence of
simple decision rules.
• A decision tree model comprises a set of rules for portioning a huge
heterogeneous population into smaller, more homogeneous, or mutually exclusive
classes.
• The attributes of the classes can be any variables from nominal, ordinal, binary,
and quantitative values, in contrast, the classes must be a qualitative type, such as
categorical or ordinal or binary.
• A decision tree creates a set of rules that can be used to identify the class.
• One rule is implemented after another, resulting in a hierarchy of segments within
a segment.
• The hierarchy is known as the tree, and each segment is called a node.
• With each progressive division, the members from the subsequent sets become
more and more similar to each other.
• Hence, the algorithm used to build a decision tree is referred to as recursive
partitioning. The algorithm is known as CART (Classification and Regression Trees)
Decision tree Algorithm:
• The decision tree algorithm may appear long, but it is quite simply the basis
algorithm techniques is as follows:
• The algorithm is based on three parameters: D, attribute_list, and Attribute
_selection_method.
• Generally, we refer to D as a data partition.
• Initially, D is the entire set of training tuples and their related class levels (input
training data).
• The parameter attribute_list is a set of attributes defining the tuples.
• Attribute_selection_method specifies a heuristic process for choosing the
attribute that "best" discriminates the given tuples according to class.
• Attribute_selection_method process applies an attribute selection measure.
Advantages of using decision trees:
• A decision tree does not need scaling of information.
• Missing values in data also do not influence the process of building a choice tree to
any considerable extent.
• A decision tree model is automatic and simple to explain to the technical team as
well as stakeholders.
• Compared to other algorithms, decision trees need less exertion for data
preparation during pre-processing.
• A decision tree does not require a standardization of data.
Key differences between Artificial Intelligence (AI) and Machine learning (ML)

Artificial Intelligence Machine learning

Machine learning is a subset of AI which
Artificial intelligence is a technology which
allows a machine to automatically learn
enables a machine to simulate human
from past data without programming
behavior.
explicitly.
The goal of AI is to make a smart computer The goal of ML is to allow machines to
system like humans to solve complex learn from data so that they can give
problems. accurate output.
In ML, we teach machines with data to
In AI, we make intelligent systems to
perform a particular task and give an
perform any task like a human.
accurate result.
Machine learning and deep learning are the Deep learning is a main subset of
two main subsets of AI. machine learning.
AI has a very wide range of scope. Machine learning has a limited scope.
Machine learning is working to create
AI is working to create an intelligent system
machines that can perform only those
which can perform various complex tasks.
specific tasks for which they are trained.
Artificial Intelligence Machine learning

AI system is concerned about maximizing Machine learning is mainly concerned about

the chances of success. accuracy and patterns.

The main applications of AI are customer The main applications of machine learning
support using catboats, Expert System, are Online recommender system, Google
Online game playing, intelligent search algorithms, Facebook auto friend
humanoid robot, etc. tagging suggestions, etc.
Machine learning can also be divided into
On the basis of capabilities, AI can be
mainly three types that are Supervised
divided into three types, which are,
learning, Unsupervised learning, and
Weak AI, General AI, and Strong AI.
Reinforcement learning.
It includes learning, reasoning, and self- It includes learning and self-correction when
correction. introduced with new data.
AI completely deals with Structured, Machine learning deals with Structured and
semi-structured, and unstructured data. semi-structured data.
 Statistical Learning

• Statistical Learning is a set of tools for understanding data. These tools broadly
come under two classes: supervised learning & unsupervised learning.
• Generally, supervised learning refers to predicting or estimating an output based
on one or more inputs.
• Unsupervised learning, on the other hand, provides a relationship or finds a
pattern within the given data without a supervised output.
What is Statistical Learning?
• Let, suppose that we observe a response Y and p different predictors X = (X₁, X₂,….,
Xp). In general, we can say: Y =f(X) + ε
• Here f is an unknown function, and ε is the random error term.
• In essence, statistical learning refers to a set of approaches for estimating f.
• In cases where we have set of X readily available, but the output Y, not so much,
the error averages to zero, and we can say: ¥ = ƒ(X)
• where ƒ represents our estimate of f and ¥ represents the resulting prediction.
 Bayesian Learning
• A learning technique that determines model parameters (such as the network
weights) by maximizing the posterior probability of the parameters given the
training data. The idea is that some parameter values are more consistent with the
observed data than others.
• Bayesian ML is a paradigm for constructing statistical models based on Bayes'
Theorem. p(θ|x)=p(x|θ)p(θ)/p(x) Generally speaking, the goal of Bayesian ML is
to estimate the posterior distribution (𝑝(𝜃|𝑥)p(θ|x)) given the likelihood
(𝑝(𝑥|𝜃)p(x|θ)) and the prior distribution, 𝑝(𝜃)p(θ).
• An important concept of Bayes theorem named Bayesian method is used to
calculate conditional probability in Machine Learning application that includes
classification tasks.
• Further, a simplified version of Bayes theorem (Naïve Bayes classification) is also
used to reduce computation time and average cost of the projects.
• Bayes theorem is also known with some other name such as Bayes rule or Bayes
Law. Bayes theorem helps to determine the probability of an event with random
knowledge.
• It is a best method to relate the condition probability and marginal probability.
Bayesian Learning depends upon Bayes Theorem
What is Bayes Theorem?
• Bayes' theorem can be derived using product rule and conditional probability of
event X with known event Y:
• According to the product rule we can express as :
• The probability of event X with known event Y as follows;
P(X ? Y)= P(X|Y) P(Y) {equation 1}
• Further, the probability of event Y with known event X:
P(X ? Y)= P(Y|X) P(X) {equation 2}
• Mathematically, Bayes theorem can be expressed by combining both equations on
right hand side. We will get:
• Here, both events X and Y are independent events which means probability of
outcome of both events does not depends one another.
• The above equation is called as Bayes Rule or Bayes Theorem.
• P(X|Y) is called as posterior, which we need to calculate. It is defined as updated
probability after considering the evidence.
• P(Y|X) is called the likelihood. It is the probability of evidence when hypothesis is
true.
• P(X) is called the prior probability, probability of hypothesis before considering the
evidence
• P(Y) is called marginal probability. It is defined as the probability of evidence under
any consideration.
• Hence, Bayes Theorem can be written as:
• posterior = likelihood * prior / evidence
• Suppose Sample space is : S1 = {1, 2, 3, 4, 5, 6}
• Possible outcomes : S2 = {Head, Tail}
• Two event A and B such that;
• A = Event when an even number is obtained = {2, 4, 6}
• B = Event when a number is greater than 4 = {5, 6}
• Probability of the event A ''P(A)''= Number of favourable outcomes / Total
number of possible outcomes P(E) = 3/6 =1/2 =0.5
• Similarly, Probability of the event B ''P(B)''= Number of favourable outcomes /
Total number of possible outcomes
=2/6, =1/3, =0.333
• Union of event A and B: A∪B = {2, 4, 5, 6}
• Intersection of event A and B: A∩B= {6}
• Disjoint Event: If the intersection of the event A and B is an empty set or null then
such events are known as disjoint event or mutually exclusive events also.
• If two events A and B are said to be independent if: P(A ∩ B) = P(AB) = P(A)*P(B)
• Conditional probability is defined as the probability of an event A, given that
another event B has already occurred (i.e. A conditional B). This is represented by
P(A|B) and we can define it as: P(A|B) = P(A ∩ B) / P(B)
• Marginal probability is defined as the probability of an event A occurring
independent of any other event B. Further, it is considered as the probability of
evidence under any consideration. P(A) = P(A|B)*P(B) + P(A|~B)*P(~B)
 Naïve Bayes Classifier in Machine Learning
• Naïve Bayes theorem is also a supervised algorithm for quick predictions.
• Based on Bayes theorem and used to solve classification problems.
• It is a probabilistic classifier that means it predicts on the basis of probability of an
object.
• Some popular Naïve Bayes algorithms are spam filtration, Sentimental analysis,
and classifying articles.
Advantages of Naïve Bayes Classifier in Machine Learning:
• It is one of the simplest and effective methods for calculating the conditional
probability and text classification problems.
• A Naïve-Bayes classifier algorithm is better than all other models where
assumption of independent predictors holds true.
• It is easy to implement than other models.
• It requires small amount of training data to estimate the test data which minimize
the training time period.
• It can be used for Binary as well as Multi-class Classifications.
Disadvantages of Naïve Bayes Classifier in Machine Learning:
• The main disadvantage of using Naïve Bayes classifier algorithms is,
• it limits the assumption of independent predictors because it implicitly assumes
that all attributes are independent or unrelated but in real life it is not feasible to
get mutually independent attributes.
 Expectation Maximization
• The Expectation-Maximization (EM) algorithm is defined as the combination of
various unsupervised machine learning algorithms, which is used to determine the
local maximum likelihood estimates (MLE) or maximum a posteriori estimates
(MAP) for unobservable variables in statistical models.
• Further, it is a technique to find maximum likelihood estimation when the latent
variables are present. It is also referred to as the latent variable model.
• A latent variable model consists of both observable and unobservable variables
where observable can be predicted while unobserved are inferred from the
observed variable. These unobservable variables are known as latent variables.
Key Points:
• It is known as the latent variable model to determine MLE and MAP parameters
for latent variables.
• It is used to predict values of parameters in instances where data is missing or
unobservable for learning, and this is done until convergence of the values occurs.
• EM Algorithm
• Expectation step (E - step): It involves
the estimation (guess) of all missing
values in the dataset so that after
completing this step, there should not
be any missing value.
• Maximization step (M - step): This step
involves the use of estimated data in
the E-step and updating the
parameters.
• Repeat E-step and M-step until the
convergence of the values occurs.
- The EM algorithm is completed mainly
in 4 steps, which include
- Initialization Step, Expectation Step,
Maximization Step, and convergence
Step.

- These steps are explained as follows:

1st Step: The very first step is to initialize the
parameter values. Further, the system is
provided with incomplete observed data with
the assumption that data is obtained from a
specific model.
2nd Step: This step is known as Expectation or
E-Step, which is used to estimate or guess the
values of the missing or incomplete data using
the observed data. Further, E-step primarily
updates the variables.
3rd Step: This step is known as Maximization or
M-step, where we use complete data obtained
from the 2nd step to update the parameter
values. Further, M-step primarily updates the
hypothesis.
4th step: The last step is to check if the values
of latent variables are converging or not. If it
gets "yes", then stop the process; else, repeat
the process from step 2 until the convergence
occurs.
Applications of EM algorithm
• The EM algorithm is applicable in data clustering in machine learning.
• It is often used in computer vision and NLP (Natural language processing).
• It is used to estimate the value of the parameter in mixed models such as the
Gaussian Mixture Model and quantitative genetics.
• It is also used in psychometrics for estimating item parameters and latent abilities
of item response theory models.
• It is also applicable in the medical and healthcare industry, such as in image
reconstruction and structural engineering.
• It is used to determine the Gaussian density of a function.
Advantages of EM algorithm
• It is very easy to implement the first two basic steps of the EM algorithm in various
machine learning problems, which are E-step and M- step.
• It is mostly guaranteed that likelihood will enhance after each iteration.
• It often generates a solution for the M-step in the closed form.
Disadvantages of EM algorithm
• The convergence of the EM algorithm is very slow.
• It can make convergence for the local optima only.
• It takes both forward and backward probability into consideration. It is opposite to
that of numerical optimization, which takes only forward probabilities.
 Hidden Markov Model(HMM)

• Hidden Markov Model is an temporal probabilistic model for which a single

discontinuous random variable determines all the states of the system.
• It means that, possible values of variable = Possible states in the system.
• For example: Sunlight can be the variable and sun can be the only possible state.
• The structure of Hidden Markov model is restricted to the fact that basic
algorithms can be implemented using matrix representations.
Hidden Markov Model : The Concept
• In Hidden Markov Model, every individual states has limited number of
transitions and emissions.
• A Probability value is assigned for each transition between states.
• Hence, the past states are totally independent of future states.
• The fact that HMM is called hidden because of its ability of being a memory less
process i.e. its future and past states are not dependent on each other.
• Since, HMM is rich in mathematical structure it can be implemented for practical
applications.
• This can be achieved on two algorithms called as:
– Forward Algorithm.
– Backward Algorithm.
Applications : Hidden Markov Model
• Speech Recognition.
• Gesture Recognition.
• Language Recognition.
• Motion Sensing and Analysis.
• Protein Folding.
Markov Model
• Markov model is an un-precised model that is used in the systems that does not
have any fixed patterns of occurrence i.e. randomly changing systems.
• Markov model is based upon the fact of having a random probability distribution
or pattern that may be analysed statistically but cannot be predicted precisely.
• In Markov model, it is assumed that the future states only depends upon the
current states and not the previously occurred states.
• There are four common Markov models out of which the most commonly used is
the hidden Markov model.
 Closed-world Problems
• The closed-world assumption (CWA), in a formal system of logic used for
knowledge representation, is the presumption that a statement that is true is also
known to be true.
• Therefore, conversely, what is not currently known to be true, is false.
• The same name also refers to a logical formalization of this assumption by
Raymond Reiter.
• The opposite of the closed-world assumption is the open-world assumption
(OWA), stating that lack of knowledge does not imply falsity.
• Decisions on CWA vs. OWA determine the understanding of the actual semantics
of a conceptual expression with the same notations of concepts.
• A successful formalization of natural language semantics usually cannot avoid an
explicit revelation of whether the implicit logical backgrounds are based on CWA
or OWA.
• Negation as failure is related to the closed-world assumption, as it amounts to
believing false every predicate that cannot be proved to be true. (en)
• n the context of knowledge management, the closed-world assumption is used in
at least two situations:
• (1) when the knowledge base is known to be complete (e.g., a corporate database
containing records for every employee), and
• (2) when the knowledge base is known to be incomplete but a "best" definite
answer must be derived from incomplete information
Formalization in logic
• The first formalization of the closed-world assumption in formal logic consists in
adding to the knowledge base the negation of the literals that are not currently
entailed by it.
• The result of this addition is always consistent, if the knowledge base is in Horn
form, but is not guaranteed to be consistent otherwise.
For example, the knowledge base
• { E n g l i s h ( F r e d ) ∨ I r i s h ( F r e d ) } entails neither E n g l i s h ( F r e d ) nor I r
ish(Fred).
Adding the negation of these two literals to the knowledge base leads to
• {English(Fred)∨Irish(Fred),¬English(Fred),¬Irish(Fred)
}