Nguyen Hoang Tran
1
Review of probability
Distributed System
(COMP 3221)
Probability Theory
2
3
• When we make predictions we should assign “probabilities”
with the prediction.
• Examples:
– 20% chance it will rain tomorrow.
– 50% chance that the tumour is malignant.
– 60% chance that the stock market will fall by the end of the week.
– 30% that the next president of the United States will be a
Democrat.
– 0.1% chance that the user will click on a banner-ad.
• How do we assign probabilities to complex events… using
smart data algorithms… and counting.
Predictions and Probabilities
Probability Theory
4
Apples and Oranges
P(apples) = 2/8 = 0.25 P(apples) = 3/4 = 0.75
5
• Probability is a deep topic…..but for most cases the
rules are straightforward to apply.
• Terminology
– Experiment
– Sample Space
– Events
– Probability
– Rules of probability
– Conditional probability – Bayes’ Rule
Probability Basics
Experiments and Sample Space
6
• Consider an experiment and let S be the space of possible
outcomes.
• Example:
– Experiment is tossing a coin; S={h,t}
– Experiment is rolling a pair of dice:
S={(1,1),(1,2),…,(6,6)}
– Experiment is a race consisting of three cars: 1,2 and 3.
The sample space is
{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}
Probability
7
• Let Sample Space S = {1,2,…m}
• Consider numbers
• pi is the probability that the outcome of the experiment is
i.
• Suppose we toss a fair coin. Sample space is S={h,t}. Then
ph = 0.5 and pt = 0.5.
Assigning probabilities
8
• Experiment: Will it rain or not in Sydney:
S = {rain, no-rain}
– Prain = 138/365 = 0.38; Pno-rain = 227/365 = 0.62
• Assigning (or rather how to obtain) probabilities is a deep
philosophical problem.
– What is the probability that the “green object standing
outside my house is a burglar dressed in green?”
9
• An Event A is a set of possible outcomes of the
experiment. Thus A is a subset of S.
• Let A be the event of getting a seven when we roll a pair
of dice.
– A = {(1,6),(6,1),(2,5),(5,2),(4,3),(3,4) }
– P(A) = 6/36 = 1/6
• In general
Events
10
• The sample space S and events are “sets”.
• P(S) = 1; probability of everything
• P(Φ) = 0; probability of “null”
• Addition:
– Often
• Complement:
Events and Sample Space
Axioms of probability
11
12
• Suppose the probability of raining today is 0.4 and
tomorrow is also 0.4 and on both days is 0.1. What is the
probability it does not rain on both day?
Example
13
• Suppose the probability of raining today is 0.4 and
tomorrow is also 0.4 and on both days is 0.1. What is the
probability it does not rain on both day?
• S={(R,N), (R,R), (N,N), (N,R)}
• Let A be the event that it will rain today and B it will rain
tomorrow. Then
A ={(R,N), (R,R)} ; B={(N,R),(R,R)}
• Rain at least today or tomorrow:
• Will not rain on either day: 1 – 0.7 = 0.3
Example
14
• Events like “ASX is up” are binary events.
• We can extend this: by defining a discrete random
variable.
• Two properties need to be satisfied
P(X=x) <=1 only for discrete variables Discrete Random Variables P(X = x) the probability that event X = x 15 • Random variables can also be continuous: Height, rainfall, salary, chemical concentration… • We can talk about the average (mean) and standard deviation or variance. e.g., the average height of students in COMP5318 is 175 cm with a standard deviation of 15 cm. Continuous Random Variables 16 • Random variables (both continuous and discrete) are associated with distributions. • Common examples of discrete distributions are: Bernoulli, binomial, multinomial, Poisson. • Common examples of continuous distributions are: Gaussian (Normal), Laplacian, Exponential, Gamma. • Associated with distributions are parameters... • One of the key problems in Statistics is to learn the parameters of a distribution from data. Probability Densities This is like summarising data. 17 Conditional Expectation (discrete) Approximate Expectation (discrete and continuous) Expectations 18 Most entropic distribution given a mean and variance The Gaussian Distribution 19 Gaussian Mean and Variance Coin flipping: heads=1, tails=0 Bernoulli Distribution 20 Binary Variables 21 • One of the most important concepts in all of Machine Learning • P(A | B) = P(A, B)/P(B) …assuming P(B) not equal 0. – Conditional probability of A given B has occurred. • Probability it will rain tomorrow given it has rained today. – P(A | B) = P(A, B)/P(B) = 0.1/0.4 = 1⁄4 = 0.25 – In general P(A | B) is not equal to P(B | A) Conditional Probabilities • Sum Rule • Product Rule 22 Rules of Probability 23 • P(A | B) = P(A, B) / P(B); P(B | A) = P(B, A) | P(A) • Now P(A, B) = P(B, A) • Thus P(A | B) P(B) = P(B | A) P(A) • Thus P(A | B) = [P(B | A)P(A)] / [P(B)] – This is called Bayes’ Rule – Basis of almost all prediction – Latest theories hypothesise that human memory and action is Bayes' rule in action. Bayes’ Rule 24 Posterior Prior Bayes’ Rule Likelihood Normaliser 25 The ASX market goes up 60% of the days of a year. 40% of the time it stays the same or goes down. The day the ASX is up, there is a 50% chance that the Shanghai Index is up. On other days there is 30% chance that Shanghai goes up. Suppose the Shanghai market is up. What is the probability that ASX was up? • Define A1 as “ASX is up”; A2 is “ASX is not up” Define S1 as “Shanghai is up”; S2 is “Shanghai is not up” • We want to calculate P(A1 | S1) ? • P(A1) = 0.6; P(A2) = 0.4; P(S1 | A1) = 0.5; P(S1|A2) = 0.3 • P(S2 | A1) = 1 – P(S1 | A1) = 0.5; P(S2 | A2) = 1 – P(S1 | A2) = 0.7; Example 26 • We want to calculate P(A1 | S1) ? • P(A1) = 0.6; P(A2) = 0.4; P(S1 | A1) = 0.5; P(S1 | A2) = 0.3 P(S2 | A1) = 1 – P(S1 | A1) = 0.5; P(S2 | A2) = 1 – P(S1 | A2) = 0.7; • P(A1 | S1) = P(S1 | A1)P(A1) / (P(S1)) • How do we calculate P(S1) ? Example cont. The ASX market goes up 60% of the days of a year. 40% of the time it stays the same or goes down. The day the ASX is up, there is a 50% chance that the Shanghai Index is up. On other days there is 30% chance that Shanghai goes up. Suppose the Shanghai market is up. What is the probability that ASX was up? 27 • P(S1) = P(S1,A1) + P(S1,A2) [Key Step] = P(S1 | A1)P(A1) + P(S1 | A2)P(A2) = 0.5 x 0.6 + 0.3 x 0.4 = 0.42 • Finally, P(A1 | S1) = P(S1 | A1)P(A1) / P(S1) = (0.5 x 0.6)/0.42 = 0.71 Example cont. 28 • Two events A and B are independent if • Example: Toss a coin twice. Then what is the probability of two heads? • The outcome of the two tosses are not dependent on each other • If A and B are independent then Independence P(H,H) = P(H)P(H) = 0.5 x 0.5 = 0.25 P(A | B) = P(A,B) / P(B) = P(A)P(B) / P(B) = P(A) ! P(A,B) = P(A)P(B)