Page cover image

#5-6: Bayesian Machine Learning

  • 5 min

#5-6: Bayesian Machine Learning content

Created
Topics

Validation

For any hypothesis hh
Eout(h)=Ein(h)+ Overfitting PenaltyE_{out}(h)=E_{in}(h)+\text{ Overfitting Penalty}
  • Eout(h)E_{out}(h): estimated by validation

Formula

Dataset D={(x1,y1),(x2,y2),…,(xN,yN)}D=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}
  • Training set Dtrain ∈D←N−KD_{\text {train }} \in D \leftarrow N-K samples
  • Validation set Dval∈D←KD_\text{val} \in D \leftarrow K samples
g−:g^{-}: the hypothesis selected after training on Dtrain D_{\text {train }}
Eval(g−)=1K∑xn∈Dvale(g−(xn),yn)E_\text{val}\left(g^{-}\right)=\frac{1}{K} \sum_{x_{n} \in D_{v a l}} e\left(g^{-}\left(x_{n}\right), y_{n}\right)
Expected value of validation error EDval\mathbb{E}_{D_\text{val}}
EDval[Eval(g−)]=EDval[1K∑xn∈Dval e(g−(xn),yn)]=1K∑xn∈DvalEDval[e(g−(xn),yn)]=1K∑xn∈DvalEout (g−)=Eout (g−)\begin{aligned} \mathbb{E}_{D_{v a l}}\left[E_{v a l}\left(g^{-}\right)\right] &=\mathbb{E}_{D_{v a l}}\left[\frac{1}{K} \sum_{x_{n} \in D_{\text {val }}} e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right] \\ &=\frac{1}{K} \sum_{x_{n} \in D_{v a l}} \mathbb{E}{D{v a l}}\left[e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right] \\ &=\frac{1}{K} \sum_{x_{n} \in D_{v a l}} E_{\text {out }}\left(g^{-}\right) \\ &=E_{\text {out }}\left(g^{-}\right) \end{aligned}
This is because
EDval[e(g−(xn),yn)]=Exn[e(g−(xn),yn)]=Eout (g−)\mathbb{E}_{D_{v a l}}\left[e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right]=E_{x_{n}}\left[e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right]=E_{\text {out }}\left(g^{-}\right)
Thus we have
E[Eval(g−)]=1K∑xn∈DvalE[e(g−(xn),yn)]=Eout (g−)V[Eval(g−)]=1K2∑xn∈DvalV[e(g−(xn),yn)]=σ2K\begin{align*} \mathbb{E}\left[E_{v a l}\left(g^{-}\right)\right]&=\frac{1}{K} \sum_{x_{n} \in D_{v a l}} \mathbb{E}\left[e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right]&&=E_{\text {out }}\left(g^{-}\right) \\ \mathbb{V}\left[E_{v a l}\left(g^{-}\right)\right]&=\frac{1}{K^{2}} \sum_{x_{n} \in D_{v a l}} \mathbb{V}\left[e\left(g^{-}\left(x_{n}\right), y_{n}\right)\right]&&=\frac{\sigma^{2}}{K} \end{align*}
Eout (g−)≤Eval(g−)+O(1K)E_{\text {out }}\left(g^{-}\right) \leq E_\text{val}\left(g^{-}\right)+O\left(\frac{1}{\sqrt{K}}\right)
  • Expected value of validation error closely matches EoutE_{out}

Choosing Validation Set Size KK

KK⬆️ ⇒ EoutE_{out}⬇️
notion image
KK too large ⇒ training set size N−KN-K too small
💡
Practical Rule: use 20% of DD as DvalD_{\text{val}}

Fold-Back-In Validation

notion image

Procedure: Make Most Use of Data

  1. Separate the training & validation set
  1. Tune model to find best hyper-parameters
  1. Put validation set back to train the last time

Model Selection

💡
Use the same validation set multiple times without loosing guarantees
Assume you have MM models (hypothesis sets):{H1,H2,…,HM}\left\{\mathscr{H}_{1}, \mathscr{H}_{2}, \ldots, \mathscr{H}_{M}\right\}
notion image

Cross Validation

Small K: Eout(g)≈Eout(g_)E_\text{out}(g)\approx E_\text{out}(g^\_)
Large K: Eout(g−)≈Eval(g−)E_\text{out}(g^-)\approx E_\text{val}(g^-)

Leave One Out Analysis

notion image
D=(x1,y1),…(xn−1,yn−1),(xnyn),(xn+1,yn+1),…,(xN,yN)D=\left(x_{1}, y_{1}\right), \ldots\left(x_{n-1}, y_{n-1}\right),\left(x_{n} y_{n}\right),\left(x_{n+1}, y_{n+1}\right), \ldots,\left(x_{N}, y_{N}\right)
  1. Leave 1 sample out, use the rest to train the modelD=(x1,y1),…(xn−1,yn−1),(xnyn),(xn+1,yn+1),…,(xN,yN)D=\left(x_{1}, y_{1}\right), \ldots\left(x_{n-1}, y_{n-1}\right),\xcancel{\left(x_{n} y_{n}\right)},\left(x_{n+1}, y_{n+1}\right), \ldots,\left(x_{N}, y_{N}\right)
  1. Compute model error with the 1 sampleEval(g−)=en=e(gn−(xn),yn) E_{v a l}\left(g^{-}\right)=e_{n}=e\left(g_{n}^{-}\left(x_{n}\right), y_{n}\right)
  1. Repeat step 1 & 2 for nn times
  1. Compute the Cross Validation ErrorEcv=1N∑n=1NenE_{c v}=\frac{1}{N} \sum_{n=1}^{N} e_{n}
notion image

Pros & Cons

Pro: Far more accurate
Con: Very expansive
  • The Model is trained nn times

Model Selection with Cross Validation

  1. Define MM models by choosing different values of λ\lambda: (H,λ1),(H,λ2)…,(H,λM)\left(\mathscr{H}, \lambda_{1}\right),\left(\mathscr{H}, \lambda_{2}\right) \ldots,\left(\mathscr{H}, \lambda_{M}\right)
  1. For each model m=1,2,...,Mm=1,2,...,M:
    1. Run the cross validation module to get an estimate of the cross validation error ECV(gm)E_\text{CV}(g^m)
    2. Pick the model (H,λ∗)(ℋ, \lambda^*) with the smallest error
  1. Train the model (H,λ∗)(ℋ, \lambda^*) on the entire training set DD to obtain the final hypothesis gm∗g^{m^*}

Bayesian Decision Theory

Bayes Rule

notion image

Given

  • State of nature ω\omega:
  • Prior probabilities P(ω1),P(ω2)P(\omega_1), P(\omega_2)
  • Class conditional probability: P(x∣ω1)P(x|ω_1), P(x∣ω2)P(x|ω_2)

To Find: Posterior Probability

P(ωj,x)=P(x∣ωj)P(ωj)=P(ωj∣x)P(x)P\left(\omega_{j}, x\right)=P\left(x \mid \omega_{j}\right) P\left(\omega_{j}\right)=P\left(\omega_{j} \mid x\right) P(x)

Error

P(error∣x)=P(ω1∣x)P(\text {error} \mid x) = P(ω_1 |x) if we decide on ω1\omega_1
P(error∣x)=P(ω2∣x)P(\text {error} \mid x) = P(ω_2 |x) if we decide on ω2\omega_2
⇒P(error∣x)=min⁡[P(ω1∣x),P(ω2,x)]\Rightarrow P(\text {error} \mid x)=\min \left[P\left(\omega_{1} \mid x\right), P\left(\omega_{2}, x\right)\right]
 
Evidence P(x)P(x) is a scaling factor ⇒ Pick ω1\omega_1 if P(x∣ω1)P(ω1)>P(x∣ω2)P(ω2)P\left(x \mid \omega_{1}\right) P\left(\omega_{1}\right)>P\left(x \mid \omega_{2}\right) P\left(\omega_{2}\right) otherwise ω2\omega_2
 

Conditional Risk

x:\mathbf{x}: multi-dimensional observations represented as a vector

Bayes Theorem

P(ωj∣x)=P(x∣ωj)P(ωj)P(x)P\left(\omega_{j} \mid \mathbf{x}\right)=\frac{P\left(\mathbf{x} \mid \omega_{j}\right) P\left(\omega_{j}\right)}{P(\mathbf{x})}

Evidence

P(x)=∑j=1cP(x∣ωj)P(ωj)P(\mathbf{x})=\sum_{j=1}^{c} P\left(\mathbf{x} \mid \omega_{j}\right) P\left(\omega_{j}\right)

Conditional Risk

Expected loss associated with taking an action αi\alpha_{i} when the true state of nature is ωj\omega_{j}
R(αi∣x)=∑j=1cλ(αi∣ωj)P(ωj∣x)R\left(\alpha_{i} \mid \mathbf{x}\right)=\sum_{j=1}^{c} \lambda\left(\alpha_{i} \mid \omega_{j}\right) P\left(\omega_{j} \mid \mathbf{x}\right)

Bayes Decision Rule

🎯
To minimize the overall risk, compute & take action to minimize conditional risk R(αi∣x)R(\alpha_i|\mathbf{x}) for i=1,2,…,ai = 1,2,…, a

Frequentist vs Bayesian Approach

Frequentist

Probability = relative frequency of events over the long run
Repeat & count # of event occurrence
Information incomplete; with uncertainty
  • Parameter θ\theta is fixed but unknown
Goal: Find params to best explain data
Implementation: MLE
θ∗=arg⁡max⁡θ[∏i=1NP(yi∣xi;θ)]\theta^{*}=\arg \max {\theta}\left[\prod{i=1}^{N} P\left(y^{i} \mid x^{i} ; \theta\right)\right]
 

Bayesian

Probability = measure of confidence of belief in the occurrence of event
Cannot repeat events
Information complete; no uncertainty
Goal: find dist over params to quantify uncertainty

Bayesian Parameter Estimation

  1. Start with prior distribution P(θ)P(\theta)
    = prior knowledge about parameters before looking at the data
  1. Given a data set D={(x1,y1),(x2,y2),…,(xN,yN)}\mathscr{D}=\left\{\left(x^{1}, y^{1}\right),\left(x^{2}, y^{2}\right), \ldots,\left(x^{N}, y^{N}\right)\right\}
  1. Use the Bayesian Theorem to find the posterior distribution of θ\theta given D(P(θ∣D))\mathscr{D}(P(\theta \mid \mathscr{D}))P(θ∣D)=P(D∣θ)P(θ)P(D)=[∏i=1NP(yi∣xi,θ)]P(θ)∫θP(D∣θ)P(θ)dθ=[∏i=1NP(yi∣xi,θ)]P(θ)∫θ[∏i=1NP(yi∣xi,θ)]P(θ)dθ\begin{aligned}P(\theta \mid \mathscr{D}) &=\frac{P(\mathscr{D} \mid \theta) P(\theta)}{P(\mathscr{D})} \\&=\frac{\left[\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}, \theta\right)\right] P(\theta)}{\int_{\theta} P(\mathscr{D} \mid \theta) P(\theta) d \theta} \\&=\frac{\left[\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}, \theta\right)\right] P(\theta)}{\int_{\theta}\left[\prod_{i=1}^{N} P\left(y^{i} \mid x^{i}, \theta\right)\right] P(\theta) d \theta}\end{aligned}
    • Denominator = dist of data

Example: Logistic Regression

hθ(x)=11+e−θTxP(yi∣xi,θ)=hθ(xi)yi⋅(1−hθ(xi))1−yi\begin{aligned}h_{\theta}(x) &=\frac{1}{1+e^{-\theta^{T} x}} \\P\left(y^{i} \mid x^{i}, \theta\right) &=h_{\theta}\left(x^{i}\right)^{y^{i}} \cdot\left(1-h_{\theta}\left(x^{i}\right)\right)^{1-y^{i}}\end{aligned}
⬆️ The product term
 
 
Maximum A Posteriori Estimation
Bayesian Linear Regression
Generative vs Discriminative Models

How to Choose a Prior

notion image
Objective
Subjective
Conjugate
 

?? Learning

Prior = posterior of the previous iteration
 

Naive Bayes Classifier

Assumes all features xix_i are conditionally independent of other features
⇒ xix_i only depends on y
⇒ P(x1,x2,x3)=P(x1∣y)P(x2∣y)P(x3∣y)P(x_1,x_2,x_3)=P(x_1|y)P(x_2|y)P(x_3|y)
 
P(x∣y)=∏i=1nP(xi∣y)P(\mathbf{x}|y)=\prod_{i=1}^nP(x_i|y)
 
Reduce 2n2^n params to nn
 
Generative Model

Discriminative vs Generative Model

notion image

Discriminative

Models P(y∣x)P(y\mid x)
  • Models the decision boundary itself
  • Simpler
  • Cannot derive the generative model by Bayes Theorem
    • Because P(x)P(x) required but impossible to find
    • Contains a lot less information

Generative

Models P(x∣y)P(x\mid y)
  • Harder to model the data itself, but more useful
Find P(y∣x)P(y\mid x) by Bayes Theorem
  • Since P(x)P(x) is the same for y=±1y=\pm1, P(x) is considered a constant normalizer and can be disregarded in computation