Bayesian Concept Learning

Probability basics, Bayesian learning, Naïve Bayes,

Bayesian Belief Network

Dr. Ananya Choudhury

Asst. Prof., Dept. of ETE, AEC
Probability basics
Probability
● Probability is the study of randomness and uncertainty.
● A random experiment is a process whose outcome is uncertain.
Examples:

○ Tossing a coin once or several times

○ Tossing a die

○ Tossing a coin until one gets Heads

Events and Sample Spaces

Sample Space
The sample space is the set of all possible outcomes.

Event
An event is any
Simple Events collection of one or
The individual outcomes more simple events
are called simple events. 4
Sample Space
● Sample space Ω : the set of all the possible outcomes of the experiment

○ If the experiment is a roll of a six-sided die, then the natural sample space is {1, 2, 3,
4, 5, 6}

○ Suppose the experiment consists of tossing a coin three times.

Ω = {(ℎℎℎ, ℎℎ𝑡, ℎ𝑡ℎ, ℎ𝑡𝑡, 𝑡ℎℎ, 𝑡ℎ𝑡, 𝑡𝑡ℎ, 𝑡𝑡𝑡}

○ The number of customers that arrive at a service desk during a fixed time period,
the sample space should be the set of nonnegative integers: Ω = 𝑍 + =
0, 1, 2, 3, …
Events
● Events are subsets of the sample space

o A= {the outcome that the die is even} ={2,4,6}

o B = {exactly two tosses come out tails}=(htt, tht, tth}

o C = {at least two heads} = {hhh, hht, hth, thh}

Probability
● A Probability is a number assigned to each event in the sample space.
● Axioms of Probability:

○ For any event A, 0  P(A)  1.

○ P() =1 and 𝑃 𝜙 = 0

○ If A1, A2, … An is a partition of A, then

P(A) = P(A1) + P(A2) + ...+ P(An)

Properties of Probability
● For any event A, P(Ac) = 1 - P(A).
● If A  B, then P(A)  P(B).
● For any two events A and B,
P(A  B) = P(A) + P(B) - P(A  B).
For three events, A, B, and C,
P(ABC) =

P(A) + P(B) + P(C) - P(AB) - P(AC) - P(BC) + P(AB C)

Intuitive Development
● Intuitively, the probability of an event a could be defined as:

Where N(a) is the number that event a happens in n trials

9
Random Variable
● A random variable is a function defined on the sample space Ω

○ maps the outcome of a random event into real scalar values


X()


Random variables (RVs) which may take on only a countable number of

distinct values
e.g., the sum of the value of two dies
Probability of Discrete RV
● Probability mass function (pmf): P ( X = xi )
● Simple facts about pmf

○  P (X = x ) = 1
i i

○ ( )
P X = xi  X = x j = 0 i j

○ P ( X = xi  X = x j ) = P ( X = xi ) + P ( X = x j ) i j

○ P ( X = x1  X = x2    X = xk ) = 1
Common Distributions
● Uniform 𝑋~ 𝑈[1, ⋯ , 𝑁]
○ X takes values 1, 2, …, N
P (X = i) = 1 N
○ E.g. picking balls of different colors from a box

● Binomial 𝑋~𝐵𝑖𝑛(𝑛, 𝑝)
○ X takes values 0, 1, …, n

n i n −i
P ( X = i ) =   p (1 − p )
○ i
○ E.g. number of heads in n coin tosses
Joint Distribution
● Given two discrete RVs X and Y, their joint distribution is the
distribution of X and Y together
○ e.g. you and your friend each toss a coin 10 times
P(You get 5 heads AND you friend get 7 heads)

●  x y
P (X = x  Y = y) = 1

 
50 100
P ( You get i heads AND your friend get j heads ) = 1
i =0 j =0

● model dependent variables

Conditional Probability
● P ( X = x Y = y ) is the probability of 𝑋 = 𝑥, given the
occurrence of 𝑌 = 𝑦
○ E.g. you get 0 heads, given that your friend gets 3 heads

P (X = x  Y = y)
● P (X = x Y = y) =
P (Y = y)
Law of Total Probability
● Given two discrete RVs X and Y, which take values in
 x1 , , xm  and  y1 , , yn  , We have

P ( X = xi ) = P (X = x  Y = y )
j i j

=  P ( X = x Y = y )P ( Y = y )
i j j
j
Marginalization

Marginal Probability

P ( X = xi ) =  P (X = x
j i )(
Y = yj P Y = yj )
Marginal Probability
Conditional Probability

▪ used to simplify joint distributions

Bayes Rule
● X and Y are discrete RVs…
P (X = x  Y = y)
P (X = x Y = y) =
P (Y = y)

( )
P Y = y j X = xi P ( X = xi )
(
P X = xi Y = y j = )
 P (Y = y
k j )
X = xk P ( X = xk )

▪ Used when P(Y|X) is known but we need P(X|Y).

Independent RVs

● X and Y are independent means that 𝑋 = 𝑥 does not

affect the probability of 𝑌 = 𝑦

● Definition: X and Y are independent if

○ P(X,Y) = P(X)P(Y)

○ P (X = x  Y = y) = P (X = x) P (Y = y)
Conditionally Independent RVs
● Intuition: X and Y are conditionally independent given Z means that once Z is
known, the value of X does not add any additional information about Y

● Definition: X and Y are conditionally independent given Z if

P (X = x  Y = y Z = z ) = P (X = x Z = z ) P (Y = y Z = z )
Continuous Random Variables
● take real numbers.
● Use Probability density function (pdf) instead of probability mass function (pmf)
● A pdf is any function 𝑓(𝑥) that describes the probability density in terms of the
input variable x.
PDF
● Properties of pdf

○ f ( x )  0, x
+
○
−
f ( x) = 1

● Actual probability can be obtained by taking the integral of pdf

○ E.g. the probability of X being between 0 and 1 is

1
P ( 0  X  1) = 
0
f ( x )dx
Cumulative Distribution Function
● FX ( v ) = P ( X  v )

● Discrete RVs

FX ( v ) =  vi
P ( X = vi )

● Continuous RVs
v
○ FX ( v ) = 
−
f ( x ) dx

d
○ FX ( x ) = f ( x )
dx
Common Distributions
● Normal 𝑋~𝑁(𝜇, 𝜎 2 )

1  ( x −  )2 
f ( x) = exp − 2 
○ 2   2 
○ E.g. the height of the entire population

0.4

0.35

0.3

0.25
f(x)

0.2

0.15

0.1

0.05

0
-5 -4 -3 -2 -1 0 1 2 3 4 5
x
Multivariate Normal
● Generalization to higher dimensions of the one-dimensional normal

Covariance Matrix

1
f X ( x1 , , xd ) =
( 2 ) d 2

12

 1  T −1 
 exp − ( x −  )  ( x −  ) 
 2 
Mean
Mean and Variance
● Mean (Expectation):  = E (X)

○ Discrete RVs:
E ( X) =  vP
vi i
( X = vi )
+
○ Continuous RVs: E (X) =  −
xf ( x ) dx

V (X) = E (X −  )
2
● Variance:

○ Discrete RVs:
V (X) =  ( vi −  ) P ( X = vi )
2
v
i

+
V (X) = − ( ) f ( x )dx
2
○ Continuous RVs: x − 
Mean Estimation from Samples
● Given a set of N samples from a distribution, we can estimate the mean of the
distribution by:

● More samples give better approximation of true mean.

26
Variance Estimation from Samples
● Given a set of N samples from a distribution, we can estimate the variance of
the distribution by:

27
Bayes’ Theorem & Concept Learning
Importance of Bayesian methods
● Idea - training data are utilized to calculate an observed probability of each class
based on feature values. When the same classifier is used later for unclassified data,
it uses the observed probabilities to predict the most likely class for the new
features.
● Intuition - applying our prior knowledge to the probability of an outcome, so that it
has higher probability of meeting the actual outcome → concept of Bayes’ rule
● Uses -
❖ Text-based classification such as spam or junk mail filtering, author identification, or topic
categorization
❖ Medical diagnosis such as given the presence of a set of observed symptoms during a
disease, identifying the probability of new patients having the disease
❖ Detecting illegal intrusion or anomaly in computer networks
Some features

● Prior knowledge of the candidate hypothesis is combined with the observed data for arriving at
the final probability of a hypothesis.
● The Bayesian approach to learning is more flexible than the other approaches because each
observed training pattern can influence the outcome of the hypothesis by increasing or
decreasing the estimated probability
● Through the easy approach of Bayesian methods, it is possible to classify new instances by
combining the predictions of multiple hypotheses, weighted by their respective probabilities.
Limitation:
● Largely depends on the availability of initial knowledge about the probabilities of the
hypothesis set. So, if these are not known, we have to use some background
knowledge/assumptions about the data set, and the related probability distribution functions.
● Moreover, it normally involves high computational cost to arrive at the optimal Bayes
hypothesis.
BAYES’ THEOREM
● Bayes’ probability rule is given as-

where A and B are conditionally related events and p(A|B) denotes the probability
of event A occurring when event B has already occurred.
D : training data set having some observed data. Our task is to determine the best
hypothesis from H by using the knowledge of D.
● Prior : Prior knowledge or belief about the probabilities of various hypotheses in H is
For example, if we have to determine whether a particular type of tumour is
malignant for a patient, the prior knowledge of such tumours becoming malignant is
a prior probability or simply Prior.
Contd..
● Posterior: The probability of a particular hypothesis for a data set based on the
Prior is called the posterior probability or simply Posterior. For example, the
probability of the hypothesis that the patient has a malignant tumour considering
the Prior of correctness of the malignancy test is a posterior probability.
According to Bayes’ theorem suppose

Here, P(h|T) is called the posterior probability, i.e. whether the hypothesis holds true
given the observed training data T.
Maximum a Posteriori (MAP) hypothesis

● Maximum a posteriori (MAP) hypothesis - finding the maximum probable

hypothesis h from a set of hypotheses H (h∈H) given the observed training data T.
● MAP hypothesis can be found from the posterior probability of each candidate
hypothesis:

as P(T) is a constant independent of h, we can write

Contd..
● Likelihood - if every hypothesis in H has equal priori i.e. P(hi) = P(hj), then, we can
determine P(h|T) from P(T|h) only. Thus, P(T|h) is called the likelihood of data T
given h, and any hypothesis that maximizes P(T|h) is called the maximum likelihood
(ML) hypothesis, hML .
Concept Learning
● Brute-force Bayesian learning algorithm - if we feed the machine with the training
data, then it can calculate the posterior probability of the hypotheses and outputs
the most probable hypothesis
Bayes optimal classifier
● Use of the MAP hypothesis → to determine what is the most probable classification of the new
instance x given the training data T
● Example – There are three hypotheses h1 , h2 , and h3 in the hypothesis space H. Let the
posterior probability of these hypotheses be 0.4, 0.3, and 0.3, respectively. There is a new
instance x, which is classified as true by h1 , but false by h2 and h3 .
● Principle of optimal Bayes- the most probable classification of the new instance (x) is obtained
by combining the predictions of all hypotheses weighed by their corresponding posterior
probabilities
● Let ci - possible classification of the new instance x (from the set C), then the probability
P(ci|T) (the correct classification for the new instance is ci) is….

● The optimal classification is the one for which P(ci|T) is maximum

Naïve Bayes
Naïve Bayes classifier
● A simple but powerful probabilistic classifier based on Bayes' Theorem that
assign class labels to problem instances.
● Used in text classification, spam detection, sentiment analysis.
● From Bayes rule,

→ ‘What is the probability that a particular object belongs to class i given its
observed feature values?’
● For eg: a person has height and weight of 182 cm and 68 kg, respectively. What is
the probability that this person belongs to the class ‘basketball player’?
Contd..
● Consider a learning task→ each instance x has some attributes
target function (f(x)) can take any value from set C.
set of training examples for target function, and
a set of attributes {a1 , a2 ,…, an } for the new instance.
Our task is to predict the class for the new instance x.
● According to Bayes’ theorem , classification→ assign the most probable class CMAP to the new
instance based on the attribute values of the new instance {a1, a2,..,an}. So we have

Rewriting using Bayes’ Theorem

● As combined probability of the attributes =1

● P(ci) - calculate the frequency of each target value ci in the training data set.
P(a1 , a2 ,.., an |ci ) - requires rigorous calculation (as number of these terms =
product of possible instances and possible target values)
● Assumption - the attribute values are conditionally independent of each other for the
target value.
● Based on this simplification we have
● The Naïve Bayes classifier is given as

Computation is less → as we have to compute P(ai |cj ) only for number of distinct
attributes values i.e. (ai ) times the number of distinct target values (c ), which isa
much smaller set
● Significant characteristic - doesnot need to search the whole hypothesis space,
rather we can arrive at the target classifier by simply counting the frequencies of
various data combinations within the training example
Strengths & limitations
Bayesian Belief Network
Bayesian Belief Network (BBN)

● Naïve Bayes → attribute values a1 , a2 ,…, an are conditionally independent

for a target value. This becomes a difficult constraint for application of this
algorithm in many practical scenarios.
● BBN approach → within a set of attributes, the probability distribution can
have conditional probability relationship as well as conditional independence
assumptions.
● BBN→ flexibility of declaring a subset of the attributes as conditionally
dependent while leaving rest of the attributes to have conditional
independence.
Contd..
● A BBN describes the joint probability distribution of a set
of attributes in their joint space
● It consists of nodes and arcs. The nodes represent the
discrete or continuous variables for which we are
interested to calculate the conditional probabilities. The
arc represents the causal relationship of the variables.
● Arcs → node variables are conditionally independent of
its non-descendants, given its immediate predecessors
● Conditional probability table for each variable →
probability distribution of that variable given the values of
its immediate predecessors
● Unconditional probability (Hard evidence) that Tim is late to class:

● From this unconditional probability, use of BBN is to find out the revised probability on the basis of the prior
knowledge.
● The revised probability that there was rain today

● The revised probability that Paul will be late to class today is –

Hard evidence and Soft evidence
● Hard evidence /instantiation of a node → is evidence that the state of the
variable definitely has as a particular value. Example: ‘Tim is late to class’.

● If a particular node is instantiated → further backpropagate to its child nodes.

● Soft evidence for a node → provides the prior probability values for the node.
The node ‘Paul is late to class’ is soft evidenced with the prior knowledge that
‘Tim is late to class’.