Artificial Intelligence & Data Mining

Week 12

WEN Bihan (Assoc Prof)

Homepage: [Link]

1
Recap: Bias and Variance

• Model Complexity Analysis:

Underfitting Overfitting
High bias and low variance Low bias and high variance

2
Recap: Overfitting and Underfitting

1. High complexity -> Large Gap -> Overfitting

2. Low complexity -> Small Gap -> Underfitting

3
Recap: Principal Component Analysis

• Project data onto the low-dimensional subspace, to achieve the

following objectives:

1. The mean square error (MSE) of the projected data is minimized.

2. The variance of the projected data is maximized.

• Example:

• 𝒙𝒊 ( black ): the original data.

• 𝒗 ( red ) : PCA subspace.

• 𝒗𝑻 𝒙𝒊 𝒗 ( blue ) : projected data.

• Green: 𝒙𝒊 - 𝒗𝑻 𝒙𝒊 𝒗 : projection error (MSE).

4
Recap: Principal Component Analysis

• Minimizing MSE <=> Maximizing Projected Variance

• Blue2 + green2 = black2

• Black is fixed (given data)

• Maximizing blue (variance)

is equivalent to
Minimizing green (MSE).

5
 Bayesian Inference

WEN Bihan (Assoc Prof)

Homepage: [Link]

6
Outline

• Probability and Conditional Probability

• Bayes’ Theorem

• Naïve Bayes

• Examples

7
Carry-on Questions

• What is Bayes’ Theorem?

• What is Naïve Bayes assumption?

8
From deterministic to probabilistic learning

• Training a deep neural network for classification:

• Deterministic model: always gives you the same output for the same input.

9
From deterministic to probabilistic learning

• Training a deep neural network for classification:

• Deterministic inference: gives you the same output for the same input.

• Bayesian Inference

• Tossing a coin twice, what outcomes will we get?

• There are 4 possible outcomes of this experiment

𝑆 = {𝐻𝐻, 𝐻𝑇, 𝑇𝐻, 𝑇𝑇}

• Probabilistic model: 𝑃𝑟𝑜𝑏 𝐻𝐻 = 0.25

10
Basic Concepts in Probability Theory

• Concepts and Notations:

• h = A hypothesis or an event. Tossing a coin

11
Basic Concepts in Probability Theory

• Concepts and Notations:

• h = A hypothesis or an event.

• D = A collection of data (e.g., training data).

We tossed the coin 8

times, and got 4 tails
and 4 heads
sequentially.
{H,H,H,H,T,T,T,T}
12
Basic Concepts in Probability Theory

• Concepts and Notations:

• h = A hypothesis or an event.

• D = A collection of data (e.g., training data).

• P(h) = Probability that Hypothesis h holds.

• P(D) = Probability of observing the training data D.

P(h) = probability of getting heads

13
Basic Concepts in Probability Theory

• Concepts and Notations:

• h = A hypothesis or an event.

• D = A collection of data (e.g., training data).

• P(h) = Probability that Hypothesis h holds.

• P(D) = Probability of observing the training data D.

• P(D|h) = Probability of observing D when h holds. (read

“probability of D given h”, “probability of D conditioned on h” ).

14
Basic Concepts in Probability Theory

• We are interested of P(h|D), because

• We always learn from history / knowledge.

• We normally have the access to the training data D.

• We need to know P(h|D), aims to find the most probable

hypothesis given that data.

15
Basic Concepts in Probability Theory

• Concepts and Notations:

• h = A hypothesis or an event.

• D = A collection of data (e.g., training data).

• P(h) = Probability that Hypothesis h holds.

• P(D) = Probability of observing the training data D.

• P(D|h) = Probability of observing D when h holds. (read

“probability of D given h).

• Can we calculate P(h|D)? 16

Joint and Conditional Probability

• Conditional Probability 𝑃 𝐴 | 𝐵 :

The probability that A happens given that B happened.

• Joint probability 𝑃 𝐴, 𝐵 :

The probability that A and B both happen.

• 𝑃 𝐴, 𝐵 = 𝑃 𝐴 𝐵 ∗ 𝑃(𝐵)

17
Bayes’ Theorem

• The simple form of Bayes’ Theorem:

𝑃 𝐵 𝐴 𝑃(𝐴)
𝑃 𝐴|𝐵 =
𝑃(𝐵)

• How to derive the theorem?

• Use joint probability: 𝑃 𝐴, 𝐵 = 𝑃 𝐴 𝐵) 𝑃 𝐵 = 𝑃 𝐵 𝐴) 𝑃(𝐴).

• Therefore:
𝑃(𝐴, 𝐵) 𝑃 𝐵 𝐴 𝑃(𝐴)
𝑃 𝐴|𝐵 = =
𝑃(𝐵) 𝑃(𝐵)

18
Bayes’ Theorem

• Given P(B) which is a constant, the proportional form:

• Sometimes P(B) can be also calculated as

• This is based on Law of total probability:

19
Bayes’ Theorem

• Now, we can predict 𝑃(ℎ|𝐷):

𝑃 𝐷 ℎ) 𝑃(ℎ)
𝑃 ℎ𝐷 =
𝑃(𝐷)
• Some terminologies we are going to use:

• Prior probability 𝑃(ℎ): prior knowledge of ℎ before observing 𝐷.

• Posterior 𝑃 ℎ 𝐷 : the probability of ℎ after we have observed 𝐷.

• Likelihood 𝑃 𝐷 ℎ : Likelihood of observing 𝐷 given ℎ.

20
Bayes’ Theorem

• Maximum A Posteriori (MAP) hypothesis:

𝐡𝐌𝐀𝐏 = 𝐚𝐫𝐠𝐦𝐚𝐱 𝐏(𝐡|𝐃)

𝑃 𝐷 ℎ) 𝑃(ℎ)
• We just learned that 𝑃 ℎ 𝐷 = . Given D, we have
𝑃(𝐷)

𝐡𝐌𝐀𝐏 = 𝐚𝐫𝐠𝐦𝐚𝐱 𝐏 𝐃 𝐡 𝐏(𝐡)

• If P(h) is constant, MAP is equivalent to Maximum Likelihood (ML):

𝐡𝐌𝐀𝐏 = 𝐚𝐫𝐠𝐦𝐚𝐱 𝐏 𝐃 𝐡

21
Example Questions

Quiz 1: Flipping a coin

• Suppose we are flipping a fair coin twice.

What is the probability that both flips are heads?

22
Example Questions

Quiz 1: Flipping a coin

• Suppose we are flipping a fair coin twice.

What is the probability that both flips are heads?

• Answer: 0.25
• There are 4 possible outcomes: HH, HT, TH, TT, with equal prob.
• Thus, Prob (HH ) = ¼ = 0.25

23
Example Questions

• Quiz 2: Flipping a coin

• Suppose we are flipping a fair coin twice.

Given that the outcome of first flip is heads, what is the
probability that both flips are heads?

24
Example Questions

• Quiz 2: Flipping a coin

• Suppose we are flipping a fair coin twice.

Given that the outcome of first flip is heads, what is the probability that
both flips are heads?

• Answer: 0.5
• Bayesian Theorem: 𝑃 𝐻𝐻 = 𝑃 (𝐻𝐻) 𝐻 ∗ 𝑃(𝐻)
• P(H) is given with probability 1, 𝑃 𝐻𝐻 = 𝑃 (𝐻𝐻) 𝐻 = 0.5

25
Example Questions

• Quiz 3: Our IE4483 is attended by students from both EEE and IEM.
Only 50% of the IEM students and 30% of the EEE students pass the
exam. Given that 60% of the entire class are EEE students, what is the
percentage of IEM students amongst those who pass the exam?

26
Example Questions
• Quiz 3: Our IE4483 is attended by students from both EEE and IEM.
Only 50% of the IEM students and 30% of the EEE students pass the
exam. Given that 60% of the entire class are EEE students, what is the
percentage of IEM students amongst those who pass the exam?

Step1: S – pass exam, M – from IEM, E – from EEE

Step2: What has been given?
P(M) = 0.4, P(E) = 0.6, P(S|M) = 0.5, P(S|E) = 0.3
What is asked by the question: P(M|S) = ?
Step3: Bayes Theorem: P(M|S) = P(S|M) * P(M) / P(S)
P(S|M) and P(M) are known. P(S) = ?
Step4: P(S) = P(S|M)*P(M) + (S|E)*P(E) - Law of Total Prob
= 0.5*0.4 + 0.3*0.6 = 0.38
P(M|S) = 0.5*0.4 / 0.38 = 0.526 27
Example Questions

• Quiz 4: Monty Hall Problem

• Movie 21, the Game Show Problem:

[Link]

[Link] 28
Example Questions

• Quiz 4: Monty Hall Problem

• You’re a contestant on a game show. You see three closed doors, and
behind one of them is a prize. You choose one door, and the host opens
one of the other doors and reveals that there is no prize behind it. Then
he offers you a chance to switch to the remaining door. Should you take
it?

[Link] 29
Example Questions

• Quiz 4: Monty Hall Problem, Explained.

• 1st Trial:

• Case 1: With probability 1/3, you picked the correct door.

• Case 2: With probability 2/3, picked the wrong door.

• What’s the chance of winning, if your strategy is to switch:

• If case 1 and you switch, you lose – prob = 1/3

• If case 2 and you switch, you win – prob = 2/3.

30
Example Questions

• Quiz 4: Monty Hall Problem, Explained.

• 1st Trial:

• Case 1: With probability 1/3, you picked the correct door.

• Case 2: With probability 2/3, picked the wrong door.

• What’s the chance of winning, if your strategy is to NOT switch:

• If case 1, you win – prob = 1/3

• If case 2, you lose – prob = 2/3.

31
Example Questions

• Use Bayes Theorem to analyze it:

• Prior: P(c1)=P(c2)=P(c3) = 1/3

• Suppose the player choose Door 1 first – happened

• Event D2: the host opens Door 2 (D2).

1/2 ∗ 1/3
• P(c1 | D2) = P(D2| c1) * P(c1) / P(D2) = 1/2
= 1/3

• P(c2 | D2) = 0

• P(c3 | D2) = 1 – 1/3 = 2/3

1 ∗ 1/3
= P(D2| c3) * P(c3) / P(D2) =
1/2
= 2/3

32
Naïve Bayes

• The basic form of Bayes’ Theorem:

𝑃 𝐵 𝐴 𝑃(𝐴)
𝑃 𝐴|𝐵 =
𝑃(𝐵)

• It is straightforward if A and B are both single attributes.

• But what if we have multiple conditions or query events?

• How to represent their conditional probabilities?

33
Naïve Bayes

• Extend from simple example to large training datasets.

• Single attribute Multiple attributes

• How does 𝑃 𝑎1 , 𝑎2 𝑣𝑗 ) relate to 𝑃 𝑎1 𝑣𝑗 ) and 𝑃 𝑎2 𝑣𝑗 ) ?

• Naïve Bayes Assumption:

𝑃 𝑎1 , 𝑎2 𝑣𝑗 ) = 𝑃 𝑎1 𝑣𝑗 )𝑃 𝑎2 𝑣𝑗 )

34
Naïve Bayes

• Naïve Bayes assumption:

• The conditional independence assumption

• The values of some features are conditionally independent on the others.

• Mathematical Form:

𝑃 𝑎1 , … , 𝑎𝑑 𝑣𝑗 ) = 𝑃 𝑎1 𝑣𝑗 ) … 𝑃 𝑎𝑑 𝑣𝑗 )

𝑃 𝑎1 , … , 𝑎𝑑 𝑣𝑗 ) = ෑ 𝑃 𝑎𝑖 𝑣𝑗 )
𝑖=1

35
Naïve Bayes - Example

• Play Tennis:

• New Observation: <Sunny,Cool,High,Strong>, will you play tennis?

36
Naïve Bayes - Example

• Play Tennis:

• New Observation: <Sunny,Cool,High,Strong>, will you play tennis?

• What do you need to know, to answer the question?

• 𝑃 𝑝𝑙𝑎𝑦 = 𝑦𝑒𝑠 < 𝑆, 𝐶, 𝐻, 𝑆 >)

• 𝑃 𝑝𝑙𝑎𝑦 = 𝑛𝑜 < 𝑆, 𝐶, 𝐻, 𝑆 >)

37
Naïve Bayes - Example

• Play Tennis:

• Hard to compare 𝑃 𝑦𝑒𝑠 < 𝑆, 𝐶, 𝐻, 𝑆 >) and

𝑃 𝑛𝑜 < 𝑆, 𝐶, 𝐻, 𝑆 >) directly

• According to Bayes’ Theorem, it is to compare S = Sunny (outlook)

𝑃 𝑦𝑒𝑠 𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑦𝑒𝑠)
and 𝑃 𝑛𝑜 𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑛𝑜) C = Cool (Temp.)

H = High (Humidity)

S = Strong (Wind)

38
Bayes’ Theorem

• Bayes’ Theorem:

𝑃 𝐵 𝐴 𝑃(𝐴)
𝑃 𝐴|𝐵 =
𝑃(𝐵)
𝑃 𝑂𝑏𝑠𝑒𝑟. 𝑦𝑒𝑠 𝑃(𝑦𝑒𝑠)
𝑃 𝑦𝑒𝑠 | 𝑂𝑏𝑠𝑒𝑟. =
𝑃(𝑂𝑏𝑠𝑒𝑟. )

• Denote the < 𝑆, 𝐶, 𝐻, 𝑆 > as the 𝑂𝑏𝑠𝑒𝑟.

• 𝑷(𝑶𝒃𝒔𝒆𝒓. ) is a constant, i.e., same for both choices.

• If 𝑃 𝑦𝑒𝑠 | 𝑂𝑏𝑠𝑒𝑟. > 𝑃 𝑛𝑜 | 𝑂𝑏𝑠𝑒𝑟.

It is the equivalent to 𝑃 𝑂𝑏𝑠𝑒𝑟. 𝑦𝑒𝑠 𝑃(𝑦𝑒𝑠) > 𝑃 𝑂𝑏𝑠𝑒𝑟. 𝑛𝑜 𝑃(𝑛𝑜)

39
Naïve Bayes - Example

• Play Tennis:

• Compare 𝑃 𝑦𝑒𝑠 < 𝑆, 𝐶, 𝐻, 𝑆 >) and

𝑃 𝑛𝑜 < 𝑆, 𝐶, 𝐻, 𝑆 >)

• According to Bayes’ Theorem, it is to compare S = Sunny (outlook)

𝑃 𝑦𝑒𝑠 𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑦𝑒𝑠)
and 𝑃 𝑛𝑜 𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑛𝑜) C = Cool (Temp.)

• P(yes) = #yes / #days = 9/14 By counting H = High (Humidity)

• Based on Naïve Bayes assumption, we have S = Strong (Wind)

𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑦𝑒𝑠) =
𝑃 𝑆 𝑦𝑒𝑠 𝑃 𝐶 𝑦𝑒𝑠 𝑃 𝐻 𝑦𝑒𝑠 𝑃 𝑆 𝑦𝑒𝑠
2 3 3 3
= × × × = 0.00823
9 9 9 9
By counting

9
• Thus, 𝑃(𝑦𝑒𝑠, < 𝑆, 𝐶, 𝐻, 𝑆 >) = 14 × 0.00823 = 𝟎. 𝟎𝟎𝟓𝟏
40
Naïve Bayes - Example

• Play Tennis:

• 𝑃(𝑦𝑒𝑠, < 𝑆, 𝐶, 𝐻, 𝑆 >) = 𝟎. 𝟎𝟎𝟓𝟏

• Similarly, 𝑃 𝑛𝑜, < 𝑆, 𝐶, 𝐻, 𝑆 > = 𝑃 𝑛𝑜 𝑃 < 𝑆, 𝐶, 𝐻, 𝑆 > 𝑛𝑜)

= 𝑃 𝑛𝑜 𝑃 𝑆 𝑛𝑜 𝑃 𝐶 𝑛𝑜 𝑃 𝐻 𝑛𝑜 𝑃 𝑆 𝑛𝑜
= 0.36 × 0.6 × 0.2 × 0.8 × 0.6 = 𝟎. 𝟎𝟐𝟎𝟕

• Will you play tennis?

• 𝑃(𝑦𝑒𝑠, < 𝑆, 𝐶, 𝐻, 𝑆 >) < 𝑃 𝑛𝑜, < 𝑆, 𝐶, 𝐻, 𝑆 >

• Given the observation <Sunny,Cool,High,Strong>, more likely you

will NOT play tennis.

41
Carry-on Questions

• What is Bayes’ Theorem?

𝑃 𝐵 𝐴 𝑃(𝐴)
𝑃 𝐴|𝐵 =
𝑃(𝐵)

• What is Naïve Bayes assumption?

𝑃 𝑎1 , … , 𝑎𝑑 𝑣𝑗 ) = ෑ 𝑃 𝑎𝑖 𝑣𝑗 )
𝑖=1

42
What we have learned

• Probability and Conditional Probability

• Hypothesis, joint / conditional probability, etc.

• Bayes’ Theorem

• Various forms of Bayes’ Theorem, prior, likelihood, Posterior, etc.

• Naïve Bayes

• Multi-attributes, Naïve Bayes assumption, examples.

43