Machine Learning

Probabilistic Perspective

Tien-Lam Pham
[Link]@[Link]
 Intelligent Machine
INPUT
Information
(X)

Give machine set of rules

Knowledge
Learning from data Intelligence
(Machine learning)

OUTPUT
Prediction (y)
Action (0, 1)
Machine Learning

3
Bayes Rule
Xad suit doing not hieri
P(A, B)
P(A | B) = Joint proba
P(B)
XadTtootk Marginal probability
conditionalproba

ÉI I Prior

[Link] Likelihood
tier
ughiem
[Link]

P h Data P Data h P h
chon thugé't PCh D loin what
 ng ge they

Bayes Rule

P(A, B)
P(A | B) =
P(B)

A woman decides to have a medical test for breast cancer. If

the test is positive, what is the probability you have cancer?

- Sensitivity: 0.8

- False positive: 0.1

- Positive rate: 0.004

ll from Section 2.5.2 that the pdf for an MVN in D dimensions is defined b
Gaussian Model Multivariate Gauss
! "
1 1
N (x|µ, Σ) !
(2π)D/2 |Σ|1/2 0
exp − (x − µ)T Σ−1 (x − µ)
2
Covariance
matrix
1 − 12 (x−μ)TΣ−1(y−ν)
p(x, y) = e
2π | Σ |

σx = 0.2 σxy
Σ= ,
σyx σy = 0.3

μx = 0.0
μ=
I
μy = 0.0
,
 Gaussian Model
1 − 12 (x−μ)TΣ−1(y−ν)
p(x, y) = e
2π | Σ |

σx = 0.2 σxy
Σ= ,
σyx σy = 0.3

μx = 0.0
μ= ,
μy = 0.0
D R R 2m

a
L
GS D train theo phain phoi Gauss
D ru't ra draw hoo's tag mai
ti phai phoni Gauss

D N x MO
n L I I
µ x̅

I X M x MT
Covariance matrix
 Guy
ya

kid
provide a measure of confidence in our estimates.
Theorem 4.1.1 (MLE for a Gaussian).
Maximum LikelihoodIf wefor
have N iid samples xi ∼ N (µ, Σ
MVN
the parameters is given by
!N
1
µ̂mle = xi ! x
N i=1
!N N
!
1 T 1
Σ̂mle = (xi − x)(xi − x) = ( xi xTi ) − x xT
N i=1 N i=1

That is, the MLE is just the empirical mean and empirical covariance. In the
get the following familiar results:
1 !
µ̂ = xi = x
N i
" #
1 ! 1 !
σ̂ 2 = (xi − x)2 = x2i − (x)2
N i N i
 Bayesian Inference

Regression Timi joint distribution of input

P(y, x) and output
ŷ = arg max P(y | x) = arg max
y y P(x
karst
 Bayesian Inference −2

−2 0 2 P 0.1 PG1 2 −
Classification
(a) Pe 0.9 P y ofr
ŷ = arg max P(y = c | x) x there's class1
Figure 4.3 Quadratic decision
c boundaries in JCR
2D for the
0 2
P(x | y = c)P(y = c)
discrimAnalysisDboundariesDemo.
P(y = c | x) =
P(x)
T=100 T=1 T
0.4 1 1

0.3

0.2 0.5 0.5

0.1

0 0 0
1 2 3 1 2 3 1
 Bayesian Learning

Prior: probability a hypothesis is True P h

Likelihood: probability that a data is observed given a
hypothesis i PCD h
Posterior: probability a hypothesis is True given a data
PLAID D 2.4
ĥ = arg max P(h | D) h In
h
D 52 K

P(D | h)P(h)
P(h | D) = P D h PK
P(D)
 Bayesian Learning

Prior: probability a hypothesis is True

Likelihood: probability that a data is observed given a
hypothesis
Posterior: probability a hypothesis is True given a data

θ̂ = arg max P(θ | D)

θ

P(D | θ)P(θ)
P(θ | D) =
P(D)
P D 0 PH
f Model parameters
D Ri ter K An Pfm ol D

D NC 4M 6
[Link]
Data
0 4 6
6

N 14ms é
P AID P Dlt
PIL
I argmax
PLD o Maximumlikelihood
Q
iii d independent identical distribution
assumption

997ft in
Plait
identical distribution
P Cai t
kind
Ig e
PCD A I

P Dlt
argmax

I log PID 0
argmax

ISH
4
arguin
0

Is
1
1
1 1
gr few

4
of É É

m2
52 Rin
85 71 1214 4

IT
o

6 Im IK suit
B ahineregren
Baitoan D K Y K Y km km
Tim T fu tot alot
Gaithied Ply x N Y Mcr Gm
4 1
e

Gatthiet 6 a 6 const
b
MCN I a at

brief
Inference a no'd long
y

I argmax P ly la Meng a Rtb

y
 One of the most widely Weused
often assume
models that ! has
for regression a Gaussia
is known as line
that the response is a linear2function of the inputs. This can be2 wri
N (µ,
Bayesian Linear σ where µ is the mean and σ is
), regression
this !distribution,
D we get the well-known be
y(x) = wT x + ! =To make
wj xjthe
+ !connection between linear r
the model
j=1 in the following form:
where wT x represents p(y|x, the inner or scalar product between
2
θ) = N (y|µ(x), σ (x)) the inp
. Some basic concepts in 7
machine learning 1
weight vector w , and ! is the residual error between our linea
response. This makes it clear that the model is a co
PDF
0.4

7. 0.35In statistics, it is moreassume is a the

µdenote
common to linear function
regression so µ of β.x,
weights by
2
0.3

0.25
this case, θ = (w, σ ) are the parameters
0.2 For example, suppose the input is 1 dim
0.15

0.1 follows:
0.05

T
0
−3 −2 −1 0 1
µ(x) = w0 + w1 x = w x
2 3

(a) (b)
 tablet
at D P aib D
arg max
a b
Posterior
Pla
argmax P D a b b
a b

Bayesian Rate
graithiett did
independence
PCD a b
II P Risi a b

PC x y PLY N PCH Ply n

const

P D a b N
II P Yi ai a b

identical distribution
PCs a ab e did
tiff
blast
IIIa e

logPCD aib
I
log
p flying
log likelihood L
 !(θ) ! log p(D|θ) Figure = 7.1 Linearlog p(y i |xi , θ)
regression applied to 2d data. Vertical axis i
One of the mostwithin widely
We aoften used models
i=1 assume
room. Data wasfor that regression
! hasby asome
collected is known
remote as
Gaussian linea
8sensing
or no
that the response Bayesian
N is(µ,a σlinear
courtesy ofLinear
2
), function
Romain
where ofthe
Thibaux).
regression
µ is themean
(a)inputs.
Theand This
fittedσ can
2plane
is the be writt
hasvarian
the
Instead of maximizing the log-likelihood, we can equivalently minimize
Temperature data is fitted with a quadratic of the form fˆ(x)
hood or NLL: Produced this distribution,
! D we get the well-known bell curve
by surfaceFitDemo.
y(x) = w x + T
N
To!= make the wj xconnection
j +! between linear regression
!
NLL(θ) ! −the model j=1in
log p(y |x
i i
the
, θ) following form:
T Iti=1
is common to assume the training 2 examples are ind
where w x represents p(y|x,
commonly
theabbreviated
θ)inner
= Nor(y|µ(x),
scalar
to iid.
product
σ (x))
This means
between
we can
the inputh
write
The NLL vector
weight formulation w7 , is and sometimes
! is the more residual convenient,
error betweensince many ouroptimiz
linear
are designed
response. to This
find themakes
minima it clear
of that
functions,! Nthe rathermodelthan is a maxima.
conditional
Now let us apply !(θ)
assume !µlog
the method is p(D|θ)
a oflinear
MLE =function
to the loglinearofi |x
p(y i ,so
θ) µ = w
x,regression T
x, a
setting.
of
7. the Gaussian it is into 2 that
In statistics, this the
more case, above,
common θ to we
(w,find
=denote σthe i=1 the log
are the parameters
) regression likelihood
weights by β. of is the
givenmo b
N
Instead
For "# of maximizing
example, $ 1supposethe
# log-likelihood,
the input is we
1 can$% equivale
dimensional.
! hood or NLL:1 2
1
!(θ) = follows:
log exp − (y i − w T
x i ) 2
2πσ ! 2 2σ 2
N
i=1 T
−1 NLL(θ) ! 0−N log
µ(x) = w + w 1 p(yi |xix
x = w
2
, θ)
= 2
RSS(w) − log(2πσ
i=1 )
2σwhere w is the 2 intercept or bias term, w is the s
0 1
The NLL formulation is sometimes more convenient, since
RSS stands for residual x = (1,sum of squares and
x). (Prepending is defined
a constant by to an inpu
1 term
 Bayesian Linear regression:
Regularization

Likelihood Prior Name Se

Gaussian Uniform Least squares L SSE7.3
Gaussian Gaussian Ridge L SSE α Norm 7.5
Gaussian Laplace Lasso LISSE α Norm 13.
Laplace Uniform Robust regression 7.4
Student Uniform Robust regression Ex

mary of various likelihoods and priors used for linear reg

2
l form of p(y|x, w, σ ), and the prior refers to the dis
 totomake
make the the
curvecurve “wiggle”
“wiggle” in just theinright
just the
way so right
that it way
almostso tha
perfec
has size
Figure Note: Models are ordered from complex (small regularizer) on the
But this7.8 (a) Training error
if we(dotted
changedblue) anda test
little,error (solid
N = 21).
situation is unstable: the data the coeffici
But
regularizer)
ridge We
this
on the situation
regression,
can encourage
isparameters
right. The stars
plotted
the
unstable:
correspond
vs log(λ). to
ifbe
to the we
Data changed
values
was
small,
used to plot
generated
thus
the
resulting
thedata
from
in a
a
function
no
sm
Estimate ofRidgeperformanceRegression
using training set. Dotted blue: 5-fold cross-validation estim
has We
size
zero-mean Ncan encourage
Gaussian
= 21). Note:
prior: the
Models parameters
are ordered to
frombe small,
complex
Solid black: negative log marginal likelihood, − log p(D|λ). Both curves have been
thus
(smalve
[0,1] to zero-mean
regularizer)
make
Prior p(w) =
!
on Gaussian
the
them comparable. right.
Figure
N (wj |0, τ )
prior:
2 The stars by
generated correspond to the values used
linregPolyVsRegDemo.
!
Estimate of performance using training set. Dotted blue: 5-fold
j 2
Solid p(w) =
black:2 negative Nlog j |0, τ )likelihood, − log p(D|λ). Both
(wmarginal
It is awhere
simple1/τ controls
exercise thethat
toj show strength
this is of the prior.
equivalent The corresponding
to minimizing M
the followi
[0,1] to make them comparable. Figure generated by linregPolyV
becomes
!N 2 N
1
(yi −controls the 2 strength
where 1/τ
" Dof the prior. The
2"
J(w) = (w0 + wT x ))
i T + λ||w||
N i=1 log N (yi |w0 + w xi , σ 2 ) +2
argmax log N (wj |0, τ 2 )
becomes
w
It is a simple
i=1 exercise to
" show that this is equivalent to min
j=1
where λ ! σ /τ and"
2 2 2
||w|| 2 T
N 2 = j wj = w w is the squared two-norm. " D Her
the MSE/ NLL as usual, and
argmax ! the second
N log N (y term, +
|w λ≥w0,T isxa,complexity
σ 2
) + penalty.
log T
N
solution J(w)
is given by 1 i 0 T i
w= (y − (w + w x )) + λ||w||2
i 0
2
i 2
Ni=1 i=1
j=1

"
where λ ! σ /τ T2
and 2
T2
||w||
−1
ŵridge = (λID + X X) X y = j wj2 = wT w is the squa
2
the MSE/ NLL as usual, and the second term, λ ≥ 0, is a co
solution is given by
This technique is known as ridge regression, or penalized least squares. I
Bayesian Linear regression: LASSO
 Classification: Bayesian Learning

Likelihood
P(D | θ) = ΠcP(x, y = c | θ) ∼ P(x | y = c, θ)P(y = c | θ)

Posterior

P(D | θ) = ΠcP(x, y = c | θ) ∼ P(x | y = c, θ)P(y = c | θ)P(θ)

 260 260
220 220
240 240
One important application of MVNs is to define the the class
200
220
200
220

weight

weight
Gaussian
classifier, i.e., Discriminant
180
200
160
180

160
200

weight

weight
180 180
140 140
Chapter 4. Gaussian
160
120

140
p(x|y = c, θ) = N (x|µc , Σc ) 120
160

100 100140

120
80 80120

280
The resulting technique is called (Gaussian) discriminant an
100
55 60
red = female, blue=male
65
height
70 75 80

280
55
100
red = female, blue=male
60 65
height
70

260 generative, not discriminative,

80
55(a) classifier — see Section 8.6(b)fo
60 65 70 75 260
80
80
55 60 65
height height

diagonal, this is equivalent to naive Bayes.

240 240

220 220
(a) (b
Figure 4.2 (a) Height/weight data. (b) Visualization of 2d Gaussians fit to each
200 200
weight

weight
180 180

mass is inside the ellipse. Figure generated by gaussHeightWeight.

160 160

Figure 4.2 (a) Height/weight data. (b) Visualization of 2d Gaussians fit to eac
140 140

mass is inside the ellipse. Figure generated by gaussHeightWeight.

120

100
120

100

80 80
55 60 65 70 75 80 55 60 65 70 75 80
We can classify a feature vector using the following decision rule, de
height height

(a) (b)
We can
ŷ(x) = classify
argmaxa[log
feature
p(y =vector
c|π) using
+ log the following
p(x|θ c )] decision rule, d
c
ure 4.2 (a) Height/weight data. (b) Visualization of 2d Gaussians fit to each class. 95% of the pro
ŷ(x)the=ellipse.
ss is inside argmax Figure[log p(y =
generated c|π) + log p(x|θ c )]
by gaussHeightWeight.
When we computec the probability of x under each class conditional d
the distance from x to the center of each class, µ , using Mahalanob
.1 Quadratic discriminant analysis (QDA)
Quadratic Discriminant Analysis (QDA)
The posterior over class labels is given by Equation 2.13. We can gain further insight into
model by plugging in the definition of the Gaussian density, as follows:
− 21
! 1 T −1
"
πc |2πΣc | exp − 2 (x − µc ) Σc (x − µc )
p(y = c|x, θ) = # − 1 ! 1 −1
" (4
T
c! πc |2πΣc |
4.2. Gaussian discriminant analysis exp − 2 (x − µc! ) Σc! (x − µc! ) 103
! ! 2

Thresholding this results in a quadratic function of x. The result is known as quadr

discriminant analysis (QDA). Figure 4.3 gives8 some examples
Parabolic Boundary ofSome
Some Linear, what the decision bounda
Quadratic

look
2 like in 2D.
6

4
0

−2 0

−2

−2 0 2 −2 0 2 4 6

(a) (b)

Figure 4.3 Quadratic decision boundaries in 2D for the 2 and 3 class case. Figure generated by
discrimAnalysisDboundariesDemo.
 We now consider
distribution a special
is “spiky”, with case
all its mass in largest
on the which the covariance
element. Figure generatedmatrices are
by softmaxDemo
ear discriminant
classes, Σc = Σ. In this case, analysis
we can simplify(LDA) Equation 4.33 as follows:
Linear Discriminant ! Analysis (LDA) "
Linear discriminant analysis (LDA)T −1 1 T −1 1 T −1
nowp(yconsider= c|x, θ) a∝ special πc exp µcase cΣ in− which
x x Σ x the− covarianc
µc Σ µc
2 matrices are2 tied or shared
We now consider a special case!in which the covariance "
es,classes,
Σc Σ= c = Σ.
Σ. In In
this this
case, wecase,
can we
simplify
T −1
can
Equation
1 T −1simplify
4.33 as Equation
follows: 1
= exp! µc Σ x − µ104 cΣ µc + log" πc exp[−
!1 2
p(y = c|x, θ) ∝ πc exp µTc Σ−1 x − xT Σ−1 x − µTc Σ−1 µc
1 2
2 T −1 2 1 T −1
(ySince
= thec|x, θ) ∝
quadratic term xπ! T
Σexp
−1
T c −1
x is1 µ Σ xof−c, it x
independent
T c−1
" will Σ−1 x
1 Tcancel out−
denominator. If we exp µc Σ x − µc Σ µcthen
= define
2
+ logwe πc can 2 write
exp[−
2
x Σ x]

104
! e
Chapter
βT
c
Since 1
γc the=quadratic
− µterm T −1
Σ
T
x Σµ
−1
x is
+ logindependent
π T −1 will 1
of c, it p(y = c|x,
cancel
T θ)in−1
out =the!
numera
denominator. If we
2 c=
define exp
c µ c
c Σ x − µ c Σ µ cc! +
e β

β = Σ 1 −1
µ 2 T
thenγ we=can− write
cc
T −1
c
µ Σ µ + log π
c c c where η = [β x + γ1 , . . . ,
1
2
βT
c x+γc e ηc
−1 e −1 T
e thep(yquadratic
= c|x, θ) = term
β c = Σ µc
! βTx x+γ
Σ x
= S(η)is
c independent
S(η)c = !C of c, i
η
c! e
c ! c !
e c!
ominator. If Twe define T c! =1
where η = [β 1 x + γ1 , . . . , β C x + γC ], and SThe softmax
is the function
softmax is so
function, de
1 ηc
eT divide each ηc by a constan
−1 "
γ = c− µ
S(η) = ! C Σ µ + log π
in Section 8.2. The difference between the two approaches is explained in Section 8.6.

Two-Class
Two-class LDA LDA
To gain further insight into the meaning of these equations, let us consider the binary case. I
this case, the posterior is given by
βT
1 x+γ1
e
p(y = 1|x, θ) = T T (4.44
eβ1 x+γ1 + eβ0 x+γ0
1 # T
$
= = sigm (β 1 − β 0 ) x + (γ1 − γ0 ) (4.45
1+ e(β0 −β1 )T x+(γ0 −γ1 )
1. The abbreviation “LDA”, could either stand for “linear discriminant analysis” or “latent Dirichlet allocation” (Se
tion 27.3). We hope the meaning is clear from text.
2. In the language modeling community, this model is called a maximum entropy model, for reasons explained
Section 9.2.6.
 We now 1 discuss how to fit a discriminant
!
0 analysis model. The simplest way is to
deviation of the noise. If d is large, the signal will be easier to discriminate from the noise.
likelihood. The log-likelihood function is as follows:
 
4.2.4 Maximum
MLE for discriminant ! NLikelihood
analysis
" "C for QDA
#
" C "
log p(D|θ)
We now discuss how= I(yianalysis
to fit a discriminant = c) log πc The
model.
 way islog
+ simplest to N
use(x|µ c , Σc )
maximum

likelihood. The log-likelihoodi=1
function
c=1 is as follows: c=1 i:yi =c
!N C #  
We see that this factorizes
"" into a term for C
" π, "and C terms for each µc and
log p(D|θ) = I(yi = c) log πc +  log N (x|µc , Σc ) (4.52)Nc
can estimate thesei=1 parameters
c=1
separately. For the
c=1 i:yi =c
class prior, we have π̂c = N
Bayes. For the class-conditional densities, we just partition the data based on its
We see that this factorizes into a term for π, and C terms for each µc and Σc . Hence we
compute the MLE for each Gaussian:
can estimate these parameters separately. For the class prior, we have π̂c = NNc , as with naive
"
Bayes. For the1 class-conditional densities,1we "
just partition the data based on its class label, and
T
µ̂c =the MLE for each
compute xi ,Gaussian:
Σ̂c = (xi − µ̂c )(xi − µ̂c )
Nc i:y =c Nc i:y =c
1 " i 1 " i
µ̂c = xi , Σ̂c = (xi − µ̂c )(xi − µ̂c )T (4.53)
See discrimAnalysisFit
Nc i:y =c
i
Ncfor a Matlab implementation.
i:y =c i
Once the model has b
make
See predictions usingfor
discrimAnalysisFit a Matlab implementation. Once thewhich
discrimAnalysisPredict, model uses a plug-in
has been appro
fit, you can
make predictions using discrimAnalysisPredict, which uses a plug-in approximation.
2.5 Strategies for preventing overfitting
4.2.5 Strategies for preventing overfitting
The speed and simplicity of the MLE method is one of its greatest appeals. Ho
The speed and simplicity of the MLE method is one of its greatest appeals. However, the MLE
can badly
can badlyoverfit
overfit in high
in high dimensions.
dimensions. In particular,
In particular, the MLE forthe MLE
a full for a full
covariance covar
matrix is
singularif ifNcN<c D.
singular < And And when
D. even even Nwhen
c > D,Nthe
c > MLE D,canthebeMLE can be ill-conditioned
ill-conditioned, meaning it is
closetotosingular.
close singular. There
There are several
are several possiblepossible
solutions tosolutions to this problem:
this problem:
 The
or thesimplest approach
MAP estimate for the isparameters.
to assume the features
However, we will are
alsoconditiona
discuss how
The fitting
probability
.5.1 posterior,
Model forterms
a singlecontaining the
data case is given θ
by jc ’s. Henc
label. This allows
p(θ|D).
Naive us toClassifiers
Bayes write the class conditional density a
We now discuss how to “train” a naive"
densities: , yi |θ)for=thep(y
From Equation 3.48, the MLE
" means computing
Bayes classifier. This usually
I(yi =c)
"" th
.1 or the p(x
MLE MAP iestimate
for NBC i |π) However,
parameters. p(xijwe |θwill
j) = πc how to compute t
also discuss
posterior, p(θ|D). "D c c
The p(x|y
probability for a
= c, θ) = single data
p(x
j
case
|y is
= given
c, θN by)c
j

5.1.1 MLE for NBC

Hence the log-likelihood" π̂cis given
j =" jc
by I(yi =c) " "
p(x , yi |θ) = p(y i
j=1
|π) p(x ij |θ j )
The probability for a single data case is given by
i = N
π c p(x ij |θ jc ) I(yi

The resulting model " isj # called a"naive c $ Bayes classifierI(y =c)(NBC).
C "# D
" # C j # c

Hence
p(xi , yi |θ) = p(yi |π)
log
Thethemodelp(D|θ) is called
log-likelihood =j
where
p(xij |θ j ) =
is N
“naive”
given byN
c log
c
πc
!
I(y =c)
i
π
since
c c + we
j icdoI(y not
i =
p(xij |θ jc )
i
c)
expect log isp(x
thethefe
ij
conditional on the# given The
isCclass [Link] However, for the
even if likelihood
the naive Bayes d
c=1 j=1 c=1 i:y i =c
Hence the log-likelihood D
## # C
results
log p(D|θ)
We seein that
classifiers
=this
#C that
feature.
N work
log
expression
c π#Dc +
# well
C
For (Domingos
decomposes
# simplicity,log and
p(x
into a
ij Pazzani
|θ let
jc )
series us 1997
ofsute
model is
log p(D|θ) quite
terms containing
= simple Nc log(it
c=1
the
πc only
θ
+
’s. has
Hencej=1O(CD)
c=1logi:y
we
p(x ijparameters,
i =c
can
|θ jc )
optimize forthese
all C cla
it issee
We relatively
Fromthat this
Equation
c=1
immune
expression
case,
3.48, to the
the
jc j=1 c=1 i:y =c
overfitting.
decomposes
MLE
i
MLE into
for thea
becomes
series
class of terms,
prior is one conc
given b
We see that this expression decomposes into a series of terms, one concerning π, an
termsThe form of
containing the
thethe
θ jcθ class-conditional
’[Link] ’s. Hence
we canwe density
can optimize alldepends on the typ
these parameters sep
terms
From
containing
Equation
possibilities
From Equation N
3.48,
below:
3.48, cthe the
Hence
MLEMLE for thefor
Nisjcgiven
optimize
theprior
class class
all these parameters
prior by is given by
separately.
π̂c = θ̂jc =
• Inπ̂
π̂ c the N
=
=
NNc c
case
N
of real-valued features,
N c we can use the Gaussia
#
c
N $
where D N$
Nc$!(x |µi I(y , σi2 = ), c)
where is the µ number
is the mean of examples
of feature in clas
j in