0% found this document useful (0 votes)
79 views49 pages

Probability Theory: Sargur N. Srihari Srihari@cedar - Buffalo.edu

1) Probability theory provides a framework for dealing with uncertainty in machine learning. 2) Key concepts include random variables, probability distributions, marginal, conditional, and joint probabilities. 3) The sum and product rules relate these probabilities, and Bayes' theorem updates probabilities based on new information.

Uploaded by

asdfasdffdsa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
79 views49 pages

Probability Theory: Sargur N. Srihari Srihari@cedar - Buffalo.edu

1) Probability theory provides a framework for dealing with uncertainty in machine learning. 2) Key concepts include random variables, probability distributions, marginal, conditional, and joint probabilities. 3) The sum and product rules relate these probabilities, and Bayes' theorem updates probabilities based on new information.

Uploaded by

asdfasdffdsa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 49

Machine Learning Srihari

Probability Theory

Sargur N. Srihari
[email protected]

1
Machine Learning Srihari

Probability Theory in Machine Learning

•  Probability is key concept is dealing with


uncertainty
–  Arises due to finite size of data sets and noise on
measurements
•  Probability Theory
–  Framework for quantification and manipulation of
uncertainty
–  One of the central foundations of machine learning

2
Machine Learning Srihari

Random Variable (R.V.)


•  Takes values subject to chance
–  E.g., X is the result of coin toss with values Head
and Tail which are non - numeric
•  X can be denoted by a r.v. x which has values of 1 and 0
–  Each value of x has an associated probability
•  Probability Distribution
–  Mathematical function that describes
1. possible values of a r.v.
2. and associated probabilities

3
Machine Learning Srihari

Probability with Two Variables


•  Key concepts:
–  conditional & joint probabilities of variables
•  Random Variables: B and F
–  Box B, Fruit F
•  F has two values orange (o) or apple (a)
•  B has values red (r) or blue (b)
2 apples 3 apples
6 oranges 1 orange P(F=o)=3/4 and P(F=a)=1/4
Let p(B=r)=4/10 and p(B=b)=6/10

Given the above data we are interested in


several probabilities of interest:
marginal, conditional and joint
Described next

4
Machine Learning Srihari

Probabilities of Interest
•  Marginal Probability
2 apples 3 apples
–  what is the probability of an 6 oranges 1 orange
apple? P(F=a)
•  Note that we have to consider P(B)
•  Conditional Probability
–  Given that we have an orange
what is the probability that we
chose the blue box? P(B=b|F=o)
•  Joint Probability
–  What is the probability of orange
AND blue box? P(B=b,F=o) 5
Machine Learning Srihari

Sum Rule of Probability Theory

•  Consider two random variables


•  X can take on values xi, i=1,, M
•  Y can take on values yi, i=1,..L
•  N trials sampling both X and Y
•  No of trials with X=xi and Y=yj is nij
nij
Joint Probability p(X = x i ,Y = y j ) =
N
ci
p(X = x i ) =
•  Marginal Probability N
L
Since ci = ∑ nij , p(X = x i ) = ∑ p(X = x i ,Y = y j )
j j =1 6
Machine Learning Srihari

Product Rule of Probability Theory


•  Consider only those instances for which X=xi
•  Then fraction of those instances for which Y=yj is
written as p(Y=yj|X=xi)
•  Called conditional probability
•  Relationship between joint and conditional probability:

nij
p(Y = y j | X = x i ) =
ci
nij nij ci
p(X = x i ,Y = y j ) = = •
N ci N
= p(Y = y j | X = x i )p(X = x i )

7
Machine Learning Srihari

Bayes Theorem
•  From the product rule together with the symmetry
property p(X,Y)=p(Y,X) we get
p(X |Y )p(Y )
p(Y | X ) =
p(X )
•  Which is called Bayes’ theorem
•  Using the sum rule the denominator is expressed as
Normalization constant to
ensure sum of conditional
p(X ) = ∑ p(X |Y )p(Y ) probability on LHS
Y sums to 1 over all values of Y

8
Machine Learning Srihari

Rules of Probability
•  Given random variables X and Y
•  Sum Rule gives Marginal Probability
L
ci
p(X = x i ) = ∑ p(X = x i ,Y = y j ) =
j =1 N

•  Product Rule: joint probability in terms of conditional and


marginal
nij nij ci
p(X,Y ) = = p(Y | X )p(X ) = ×
N ci N

•  Combining we get Bayes Rule


p(X |Y )p(Y ) where p(X ) = ∑ p(X |Y )p(Y )
p(Y | X ) = Y
p(X )
Viewed as
Posterior a likelihood x prior
9
Machine Learning Srihari

Ex: Joint Distribution over two Variables


X takes nine possible values, Y takes two values

N = 60 data points
Histogram
of Y
(Fraction of
data points
having each
value of Y)

Histogram Histogram
of X of X given Y=1

Fractions would equal the probability as N àoo


10
Machine Learning Srihari

Bayes rule applied to Fruit Problem


•  Probability that box is red given
that fruit picked is orange
p(F = o | B = r) p(B = r)
p(B = r | F = o) =
p(F = o)
3 4
×
= 4 10 = 2 = 0.66 The a posteriori probability of 0.66 is
9 3 different from the a priori probability of 0.4
20

•  Probability that fruit is orange



–  From sum and product rules
p(F = o) = p(F = o,B = r) + p(F = o,B = b)
= p(F = o | B = r) p(B = r) + p(F = o | B = b) p(B = b)
6 4 1 6 9 The marginal probability of 0.45 is lower
= × + × = = 0.45
8 10 4 10 20 than average probability of 7/12=0.58 11
Machine Learning Srihari

Independent Variables
•  If p(X,Y)=p(X)p(Y) then X and Y are said to be
independent
•  Why?
p(X,Y )
•  From product rule: p(Y | X ) =
p(X )
= p(Y )

•  In fruit example if each box contained same


fraction of apples and oranges then p(F|B)=p(F)

12
Machine Learning Srihari

Probability Density Function (pdf)


Cumulative
Distribution
Function
•  Continuous Variables
•  If probability that x falls in
interval (x,x+δx) is given
by p(x)dx for δx à0
then p(x) is a pdf of x
•  Probability x lies in Probability that x lies in
interval (a,b) is Interval (-∞,z) is
z
b

p(x ∈ (a,b)) = ∫ p(x)dx P(z) = ∫ p(x)dx


a −∞

13
Machine Learning Srihari

Several Variables
•  If there are several continuous variables x1,…,xD
denoted by vector x then we can define a joint
probability density p(x)=p(x1,..,xD)
•  Multivariate probability density must satisfy
p(x) ≥ 0

∫ p(x)d x = 1
−∞

14
Machine Learning Srihari

Sum, Product, Bayes for Continuous


•  Rules apply for continuous, or combinations of
discrete and continuous variables

p(x) = ∫ p(x,y)dy
p(x,y) = p(y | x)p(x)
p(x | y)p(y)
p(y | x) =
p(x)

•  Formal justification of sum, product rules for


continuous variables requires measure theory
15
Machine Learning Srihari

Expectation
•  Expectation is average value of some function f(x) under the
probability distribution p(x) denoted E[f]
•  For a discrete distribution
E[f] = Σx p(x) f(x) Examples of f(x)
•  For a continuous distribution of use in ML:
f(x)=x; E[f] is mean
f(x)=ln p(x); E[f] is entropy
E[f ] = ∫ p(x)f (x)dx f(x)=-ln[q(x)/p(x)]; K-L divergence
•  If there are N points drawn from a pdf, then expectation can be
approximated as This approximation is extremely important
when we use
E[f] = (1/N)ΣnN=1 f(xn) sampling to determine expected value
•  Conditional Expectation with respect to a conditional distribution
Ex[f] = Σx p(x|y) f(x)
16
Machine Learning Srihari

Variance
•  Measures how much variability there is in f(x)
around its mean value E[f(x)]
•  Variance of f(x) is denoted as
var[f] = E[(f(x) – E[f(x)])2]
•  Expanding the square
var[f] = E[(f(x)2] – E[f(x)]2
•  Variance of the variable x itself
var[x] = E[x2] – E[x]2
17
Machine Learning Srihari

Covariance
•  For two random variables x and y their covariance is
•  cov[x,y] = Ex,y [{x-E[x]} {y-E[y]}]
= Ex,y [xy] - E[x]E[y]

–  Expresses how x and y vary together


•  If x and y are independent then their covariance
vanishes
•  If x and y are two vectors of random variables
covariance is a matrix
•  If we consider covariance of components of vector x
with each other then we denote it as cov[x] =cov [x,x]

18
Machine Learning Srihari

Bayesian Probabilities
•  Classical or Frequentist view of Probabilities
–  Probability is frequency of random, repeatable event
–  Frequency of a tossed coin coming up heads is 1/2
•  Bayesian View
–  Probability is a quantification of uncertainty
–  Degree of belief in propositions that do not involve random
variables
–  Examples of uncertain events as probabilities:
•  Whether Arctic Sea ice cap will disappear
•  Whether moon was once in its own orbit around the sun
•  Whether Thomas Jefferson had a child by one of his slaves
•  Whether a signature on a check is genuine 19
Machine Learning Srihari

Whether Arctic Sea cap will disappear

•  We have some idea of how


quickly polar ice is melting

•  Revise it on the basis of


fresh evidence (satellite
observations)

NASA Video •  Assessment will affect


actions we take (to reduce
greenhouse gases)
An uncertain event
Answered by general Bayesian interpretation
20
Machine Learning Srihari

Bayesian Representation of Uncertainty


•  Use of probability to represent uncertainty is not an
ad-hoc choice
•  If numerical values are used to represent degrees of
belief, then simple set of axioms for manipulating
degrees of belief leads to sum and product rules of
probability (Cox’s theorem)
•  Probability theory can be regarded as an extension of
Boolean logic to situations involving uncertainty
(Jaynes)

21
Machine Learning Srihari

Bayesian Approach
•  Quantify uncertainty around choice of parameters w
–  E.g., w is vector of parameters in curve fitting
M
y(x, w) = w0 + w1x + w2x 2 + ..+ wM x M = ∑ w j x j
j =0

•  Uncertainty before observing data expressed by p(w)


•  Given observed data D ={ t1, . . tN }
–  Uncertainty in w after observing D, by Bayes rule:
p(D | w)p(w)
p(w | D) =
p(D)

–  Quantity p(D|w) is evaluated for observed data


•  It can be viewed as function of w
•  It represents how probable the data set is for different parameters w
•  It is called the Likelihood function
•  Not a probability distribution over w 22
Machine Learning Srihari

Bayes theorem in words


•  Uncertainty in w expressed as
p(D | w)p(w)
p(w | D) =
p(D)

•  Bayes theorem in words:


posterior α likelihood ✕ prior

•  Denominator is normalization factor


•  Involves marginalization over w

p(D) = ∫ p(D | w)p(w)d w by Sum Rule


Machine Learning Srihari

Role of Likelihood Function

•  Likelihood Function plays central role in both


Bayesian and frequentist paradigms
•  Frequentist:
•  w is a fixed parameter determined by an estimator;
•  Error bars on estimate are obtained from possible
data sets D
•  Bayesian:
•  There is a single data set D
•  Uncertainty in parameters expressed as probability
distribution over w
Machine Learning Srihari

Maximum Likelihood Approach


•  In frequentist setting w is a fixed parameter
–  w is set to value that maximizes likelihood function p(D|w)
–  In ML, negative log of likelihood function is called error
function since maximizing likelihood is equivalent to
minimizing error
•  Error Bars
–  Bootstrap approach to creating L data sets
•  From N data points new data sets are created by drawing N points at
random with replacement
•  Repeat L times to generate L data sets
•  Accuracy of parameter estimate can be evaluated by variability of
predictions between different bootstrap sets
25
Machine Learning Srihari

Bayesian: Prior and Posterior


•  Inclusion of prior knowledge arises naturally
•  Coin Toss Example
–  Fair looking coin is tossed three times and lands Head each time
–  Classical m.l.e of the probability of landing heads is 1 implying all
future tosses will land Heads
–  Bayesian approach with reasonable prior will lead to less
extreme conclusion

µ=p(H)

p(µ) p(µ|H)

26
Machine Learning Srihari

Practicality of Bayesian Approach


•  Marginalization over whole parameter space is
required to make predictions or compare
models
•  Factors making it practical:
•  Sampling Methods such as Markov Chain Monte Carlo
methods
•  Increased speed and memory of computers
•  Deterministic approximation schemes such as
Variational Bayes and Expectation propagation
are alternatives to sampling
27
Machine Learning Srihari

The Gaussian Distribution


•  For single real-valued variable x What is an Exponential:
1 ⎧⎪ 1 2⎪
⎫ y=ex, where e=2.718
N(x | µ, σ ) =2
exp ⎨− 2 (x − µ) ⎪⎬
⎪ Its value for argument 0 is 1
2 1/2
(2πσ ) ⎪⎪⎩ 2σ ⎪⎪⎭ It is its own derivative

•  It has two parameters: Maximum of a distribution is its mode

–  Mean µ, variance σ 2, For a Gaussian, mode coincides with mean

–  Standard deviation σ
•  Precision β =1/σ 2
•  Can find expectations of functions of
x under Gaussian

∫ N(x | µ, σ )
2
E[x ] =
−∞

E[x 2 ] = ∫ N(x | µ, σ )x dx = µ
2 2 2
+ σ2 µ= 0, σ =1
−∞

var[x ] = E[x 2 ]− E[x ]2 = σ 2


Machine Learning Srihari

Multivariate Gaussian Distribution


•  For single real-valued variable x
1 1 ⎧⎪ 1 ⎫⎪
N(x | µ,Σ) = exp ⎨− (x − µ) Σ (x − µ)⎪⎬
⎪ T −1
D/2
(2π) Σ 1/2 ⎪⎪⎩ 2 ⎪⎪⎭

•  It has parameters:
–  Mean µ, a D-dimensional vector
–  Covariance matrix Σ
•  Which is a D ×D matrix
Machine Learning Srihari

Likelihood Function for Gaussian


•  Given N scalar observations x=[x1,.. xn]T
–  Which are independent and identically
distributed
•  Probability of data set is given by
likelihood function
N
Data: black points
p(x | µ, σ ) = ∏ N(x n | µ, σ 2 )
2
Likelihood= product of blue values
n=1
Pick mean and variance to maximize
•  Log-likelihood function is this product

1 N N N
ln p(x | µ, σ ) = − 2 ∑ (x n − µ)2 − ln σ 2 − ln(2π)
2

2σ n=1 2 2
•  Maximum likelihood solutions are given by
1 N
µML =
N
∑x
n=1
n which is the sample mean
1 N
2
σML =
N
∑ (x
n=1
n
− µML )2 which is the sample variance
30
Machine Learning Srihari

Bias in Maximum Likelihood


•  Maximum likelihood
systematically
underestimates variance
–  E[µML]=µ
–  E[σ 2ML]=((N-1)/N)σ 2
Green curve is true distribution
Averaged across three data sets
–  Not an issue as N increases mean is correct
Variance is underestimated
•  Problem is related to over- because it is estimated relative
to sample mean and not true mean
fitting problem
31
Machine Learning Srihari

Curve Fitting Probabilistically


•  Goal is to predict for target
variable t given a new value
of the input variable x

–  Given N input values


x=(x1,..xN)T and corresponding
target values t=(t1,..,tN)T

–  Assume given value of x, value


of t has a Gaussian distribution
with mean equal to y(x,w) of
polynomial curve Gaussian conditional distribution
for t given x.
p(t|x,w,β)=N(t|y(x,w),β-1) Mean is given by
M polynomial function y(x,w)
y(x, w) = w0 + w1x + w2x 2 + ..+ wM x M = ∑ w j x j Precision given by β
j =0
32
Machine Learning Srihari

Curve Fitting with Maximum Likelihood


N
p(t | x, w, β) = ∏ N(tn | y(x n , w), β −1 )
•  Likelihood Function is n=1

•  Logarithm of the Likelihood function is


β N N N
ln p(t | x, w, β) = − ∑ {y(x n , w) −tn }2 + ln β − ln(2π)
2 n=1 2 2

•  To find maximum likelihood solution for


polynomial coefficients wML
–  Maximize w.r.t w
–  Can omit last two terms -- don’t depend on w
–  Can replace β/2 with ½ (since it is constant wrt w)
–  Minimize negative log-likelihood
–  Identical to sum-of-squares error function
33
Machine Learning Srihari

Precision parameter with MLE


•  Maximum likelihood can also be used to
determine β of Gaussian conditional distribution
•  Maximizing likelihood wrt β gives
2
1 1 N
=
βML N
∑ {y(x , w
n=1
n ML
)−tn }

•  First determine parameter vector wML governing


the mean and subsequently use this to find
precision βML

34
Machine Learning Srihari

Predictive Distribution
•  Knowing parameters w and β
•  Predictions for new values of x can be made
using
p(t|x,wML,βML)=N(t|y(x,wML),βML-1)
•  Instead of a point estimate we are now giving a
probability distribution over t

35
Machine Learning Srihari

A More Bayesian Treatment


•  Introducing a prior distribution over polynomial
coefficients w
(M +1)/2
⎛ α ⎞⎟ ⎧
⎪ α T ⎫

p(w | α) = N(w | 0, α I ) = ⎜⎜⎜ ⎟⎟
−1
exp ⎨− w w⎪
⎪ ⎬
⎝ 2π ⎟⎠ ⎪

⎩ 2 ⎪


–  where α is the precision of the distribution
–  M+1 is total no. of parameters for an Mth order polynomial
–  α are Model parameters also called hyperparameter
•  they control distribution of model parameters

36
Machine Learning Srihari

Posterior Distribution
•  Using Bayes theorem, posterior distribution for w is
proportional to product of prior distribution and
likelihood function
p(w|x,t,α,β) α p(t|x,w,β)p(w|α)
•  w can be determined by finding the most probable
value of w given the data, ie. maximizing posterior
distribution
•  This is equivalent (by taking logs) to minimizing
2
β N
α T

2 n=1
{y(x n , w )−tn } + w w
2
•  Same as sum of squared errors function with a
regularization parameter given by λ=α/β
37
Machine Learning Srihari

Bayesian Curve Fitting


•  Previous treatment still makes point estimate of w
–  In fully Bayesian approach consistently apply sum and
product rules and integrate over all values of w
•  Given training data x and t and new test point x , goal
is to predict value of t
–  i.e, wish to evaluate predictive distribution p(t|x,x,t)
•  Applying sum and product rules of probability
–  Predictive distribution can be written in the form
p(t | x, x,t) = ∫ p(t, w |x, x, t)dw by Sum Rule (marginalizing over w)

=∫ p(t|x,w,x,t) p(w | x, x,t) by Product Rule


=∫ p(t|x,w)p(w|x,t)dw by eliminating unnecessary variables

p(t | x, w) = N(t | y(x , w), β −1 ) Posterior distribution over parameters 38


Also a Gaussian
Machine Learning Srihari

Bayesian Curve Fitting


•  Predictive distribution is also Gaussian
p(t | x, x,t) = N(t | m(x),s 2(x))
–  Where the Mean and Variance are dependent on x
N
m(x) = βφ(x) S ∑ φ(x n )tn
T

n=1 First term is uncertainty in predicted value due to noise in target


2 −1 T Second term is uncertainty in parameters due to Bayesian treatment
s (x) = β + φ(x) Sφ(x)
N
S −1
= αI + β ∑ φ(x n )φ(x)T
n=1

φ(x) has elements φi (x) = x i for i = 0,..M

Predictive Distribution is a M=9 polynomial


α = 5 x 10-3
β =11.1
Red curve is mean
Red region is +1 std dev

39
Machine Learning Srihari

Model Selection

40
Machine Learning Srihari

Models in Curve Fitting


•  In polynomial curve fitting:
–  an optimal order of polynomial gives best
generalization
•  Order of the polynomial controls
–  the number of free parameters in the model and
thereby model complexity
•  With regularized least squares l also controls
model complexity

41
Machine Learning Srihari

Validation Set to Select Model


•  Performance on training set is not a good
indicator of predictive performance
•  If there is plenty of data,
–  use some of the data to train a range of models Or a
given model with a range of values for its parameters
–  Compare them on an independent set, called
validation set
–  Select one having best predictive performance
•  If data set is small then some over-fitting can
occur and it is necessary to keep aside a test set
42
Machine Learning Srihari

S-fold Cross Validation


•  Supply of data is limited S=4

•  All available data is


partitioned into S groups
•  S-1 groups are used to train
and evaluated on remaining
group
•  Repeat for all S choices of If S=N this is the
leave-one-out method
held-out group
•  Performance scores from S
runs are averaged

43
Machine Learning Srihari

Bayesian Information Criterion


•  Criterion for choosing model
•  Akaike Information criterion (AIC) chooses
model for which the quantity
ln p(D|wML) –M
•  Is highest
•  Where M is number of adjustable parameters
•  BIC is a variant of this quantity

44
Machine Learning Srihari

The Curse of Dimensionality

Need to deal with spaces with many


variables in machine learning

45
Machine Learning Srihari

Example Clasification Problem


•  Three classes

•  12 variables:
two shown
•  100 points
•  Learn to Which class
should x
classify from belong to?
data

46
Machine Learning Srihari

Cell-based Classification
•  Naïve approach of
cell based voting
will fail because of
exponential growth
of cells with
dimensionality
•  Hardly any points in
each cell

47
Machine Learning Srihari

Volume of Sphere in High Dimensions


•  Sphere is of radius r =1 in
D-dimensions
•  What fraction of volume
lies between radius
r = 1-ε and r =1?
•  VD(r)=KDrD
•  This fraction is given by 1-
(1-ε)D
•  As D increases high
proportion of volume lies Fraction of volume of sphere
near outer shell lying in range r =1- ε to r = 1
for various dimensions D

48
Machine Learning Srihari

Gaussian in High-dimensional Space


•  x-y space converted to r-
space using polar
coordinates
•  Most of the probability
mass is located in a thin
shell at a specific radius

49

You might also like