CSE 150 Lecture Notes - Lecture 8: Product Rule, Bayes Estimator, Asteroid Family
27 Apr 2018
School
Department
Course
Professor
Discrete BNs w/ complete data
- complete as in “each entry in the table has some number”
- given “fixed” DAG over nodes {X1,...,Xn}
- how to choose CPTs P(Xi = x| pa(Xi) = π) to maximize prob of observed data?
- data set: T complete “instantiations” of BN, {(X1
(t),...,Xn
(t)}t = 1
T, where each n-tuple is an
“example”
IID Assumption
- Independently, Identically Distributed
- examples are drawn “IID” from joint distribution
- Prob of data set
P(Data) = Πt = 1 to T P(X1 = x1
(t),...,Xn = xn
(t)) //joint prob of “tth” example
- work out t’th term in product
P(X1 = x1
(t),...,Xn= xn
(t)) = P(X1 = x1
(t)) P(X2 = x2
(t)|X1 = x1
(t)) … P(Xn = xn
(t)|X1 = x1
(t),...,Xn-1 = xn-1
(t))
Product rule
= Πi = 1 to n P(Xi = xi
(t)|X1 = x1
(t),...,Xi-1 = xi-1
(t))
= Πi = 1 to n P(Xi = xi
(t) | pa(Xi) = pai
(t)) [Conditional Independence in BN]
Log-likelihood
L = log P(data)
= log Πt = 1 to T P(X1
(t),...,Xn
(t))
= log Πt = 1 to T Πi = 1 to n P(xi
(t) | pai
(t)) //lower-case “x”
= Σt = 1 to T Σi = 1 to n log P(xi
(t) | pai
(t)) [Sum over rows & columns]
= Σi = 1 to n Σt = 1 to T log P(xi
(t) | pai
(t)) [Swap sums]
Let count(Xi = x, pai = π) denote the # examples in table for which Xi = x and pai = π
Log-likelihood:
L= Σi = 1 to n Σx Σπ count(Xi = x, pai = π) log P(Xi = x|pai = π)
Where:
x = possible values of Xi
π = possible “settings” of parents of Xi
Note:
count(Xi = x,pai = π) - purely properties of data
log P(Xi = x|pai = π) - numbers that we can optimize
ML estimation: how to choose P(Xi = x|pai = π) to maximize L ?
Empirical frequency of Xi = x and pai = π from data
PML(Xi = x|pai = π) = count(Xi = x,pai = π) / Σx’ count(Xi = x’, pai = π)
= count(Xi = x,pai= π) / count(pai = π) when Xi has parents
= count(Xi = x) / Twhen Xi is a root node
# of examples in our dataset (i.e. rows)
Properties of ML estimation
Document Summary
Complete as in each entry in the table has some number . Data set: t complete instantiations of bn, {(x 1 . Examples are drawn iid from joint distribution. Prob of data set (t) ) (t) ,,x n (t) } t = 1 . P(data) = t = 1 to t p(x 1 = x 1 (t) ,,x n = x n (t) ) = p(x 1 = x 1 . //joint prob of t th example (t) ) p(x n = x n (t) |x 1 = x 1 (t) |x 1 = x 1 . T , where each n-tuple is an (t) ,,x n-1 = x n-1 (t) ) = i = 1 to n p(x i = x i (t) ,,x i-1 = x i-1 (t) |x 1 = x 1 (t) | pa(x i ) = pa i (t) ) (t) ) = log t = 1 to t p(x 1 (t) ,,x n .
