Bayesian Decision Theory

Problem

optimal decisions in problems with uncertainty

Framework

• states:
  • prior: $P(Y)$ = probability of a state
• observer
  • that measures features from r.v. $X$
  • class conditional distribution — conditional on state (class)
    • one CCD for each states $P(X|Y)$
• Decision function: use observation to make a decision about the state
  • $g(x):X\to Y$
• Loss function - penalizes for deciding the wrong $Y$ (the state)
  • $L(g(X),Y)\ge 0$
  • 0-1 Loss: $\{\begin{array}{ll}0,& g(X)=Y\\ 1,& g(X)\ne Y\end{array}$

Bayesian Decision Rule

Risk - expected value of the loss function

$$\begin{array}{rl}{E}_{XY}[L(g(X),Y)]& =\sum _y{\int }_{x}p(x,y)L(g(x),y)dx\\ & ={\int }_x\sum _{y}p(x)p(y|x)L(g(x),y)dx\\ & ={\int }_{x}p(x)\sum _{y}p(y|x)L(g(x),y)dx\\ & =E_X[R(X)]\end{array}$$

Since $p(x)\ge 0$, $L(g(x),y)\ge 0$, then minimizing the risk can be achieved by minimizing the conditional risk for each $x$.

For a particular $X$, choose a class that minimize the risk:

$$\begin{array}{rl}{g}^{\ast }(x)& =g^{\ast }=\arg \underset{j\in Y}{\min }R(x)\\ & =\arg \underset{j\in Y}{\min }\sum _{y}p(y|x)L(j,y)\\ & =\arg \underset{j\in Y}{\min }{E}_{Y|X}[L(j,y)]\end{array}$$

This is the Bayesian Deciison Rule.

Classification and 0-1 loss

settings:

$$\begin{array}{rl}& Y\in \left\{1,\dots ,C\right\}\\ & L(g(x),y)=\{\begin{array}{ll}0,& g(x)=y\\ 1,& g(x)\ne y\end{array}\end{array}$$

conditional risk:

$$\begin{array}{rl}R(X)=E_{Y|X}[L(g(X),Y)]& =P[g(X)\ne Y|X]\\ & =1-P[g(X)=Y|X]\\ & =\end{array}$$

BDR:

$$\begin{array}{rlr}{y}^{\ast }=\arg \underset{j\in Y}{\min }R(X)& =\arg \underset{j\in Y}{\min }1-P[g(X)=Y|X]& \\ & =\arg \underset{j\in Y}{\max }P[g(X)=Y|X]& \text{same as MAP rule: selecting the largest posteriori}\end{array}$$

Equivalently:

$$y^{\ast }=\arg \underset{j\in Y}{\max }P(X|Y=j)P(Y=j)$$

Example - 2 class classification

given $x$: pick $0$ if $p(x|0)p(0)>p(x|1)p(1)$, evquivently:

$$\underset{\text{LRT}}{\underbrace{\frac{p(x|0)}{p(x|1)}}}>\underset{\text{threshold}}{\underbrace{\frac{p(1)}{p(0)}}}=T$$

Summary:

for 0-1 loss function

• BDR is the MAP rule (tells threshold for Likelihood Ratio Test)
• Risk = prob of error
• BDR minimizes prob of error (no other decision rule is better)
• caveats: assuming our models are corect! (the CCD and the prior)

This is called a generative model

1. Use data to learn the CCDs (modeling how features are generated)
2. use the CCD in decision rule

Example: Noisy Channel

decode $x$:

$$g(x)=\{\begin{array}{ll}0,& x<T\\ 1,& x\ge T\end{array}$$

Goal: given $X$, recover the bit $Y$ Model:

• prior: $P(y=0)=P(y=1)=\frac{1}{2}$
• CCD: assume gaussian additive noise: $X={\mu }_y+ϵ,ϵ\sim N(0,{\sigma }^2)$
  • $P(x|y=0)=N(0,{\mu }_0)$
  • $P(x|y=1)=N(1,{\mu }_1)$

BDR for 0-1 Loss:

$$\begin{array}{rl}{y}^{\ast }& =\arg \underset{j\in Y}{\max }\ln p(X|Y=j)+\ln p(Y=j)\\ & =\arg \underset{j\in Y}{\max }-(x-{\mu }_j{)}^2\\ & =\arg \underset{j\in Y}{\min }(x-{\mu }_j{)}^2\\ & =\arg \underset{j\in Y}{\min }-2{\mu }_{j}x+{\mu }_j^2\end{array}$$

Hence: pick $0$ when:

$$\begin{array}{rl}-2{\mu }_{0}x+{\mu }_0^2& <-2{\mu }_{1}x+{\mu }_1^2\\ 2x({\mu }_1-{\mu }_0)& <{\mu }_1^2-{\mu }_0^2\\ x& >\frac{{\mu }_1+{\mu }_0}{2}\end{array}$$

Gaussian Classifier

• CCD are Guassians
• No assumption on prior

Special case:

• Assume ${\Sigma }_j={\sigma }^{2}I$ (shared isotropic covariance)
• $g_j(x)=w^{T}x+b_j$ (discriminant function)

$$w^T(x-x_0)=0$$

define a hyper plane passes through $x_0$ that is normal to $w$

Goal: Find optimal $g^{\ast }(x)$ for the given assumptions (prior, CCD, Lossfunction)

Mode, Mean, Median

Loss function for every predict-true value pair

Conditional Risk

Given x, the risk of the system is:

$$R(x)={\int }_{Y}L(g(x),y))p(y|x)dy$$

Total Risk:

$${\int }_{x}R(x)p(x)dx$$

choose the action ${\alpha }_i$ that gives the smallest possible value for $R({\alpha }_i|x)$

likelihood, loss, prior

To minimize total risk, minimize conditional risk.

Two class decisioning: Likelihood Ratio Test (LRT)

LRT:

L(g(x), y) p(y|x)

Dimensionality

Weirdness of high dimensional

volume of sphere = $\frac{{\pi }^{d/2}{r}^d}{\Gamma \left(\frac{d}{2}+1\right)}$

Gamma Function

Volume of hyper cube: $(2r{)}^d$

$$f_d=\frac{\text{volume of sphere}}{\text{volume of cube}}=\frac{{\pi }^{d/2}}{2^d\Gamma \left(\frac{d}{2}+1\right)}$$ $$\underset{d\to \infty }{\lim }{f}_d=0$$

corner vector $c$, and axis vector $\rho$

$$\cos \theta =\frac{c^T\rho }{||c||||p||}=\frac{r^2}{r\sqrt{d}r}=\frac{1}{\sqrt{d}}$$ $$\underset{d\to \infty }{\lim }\cos \theta =0⟹\text{axis }\rho \perp \text{angle }c$$

hypersphere shell of thickness $ϵ$

outside sphere $s_2$, inside sphere $s_1$

$$\begin{array}{rl}{V}_{shell}& =V(S_2)-V(S_1)\\ & =\left(1-\frac{V(S_1)}{V(S_2)}\right)V(S_2)\\ \frac{V(S_1)}{V(S_2)}& ={\left(1-\frac{ϵ}{r}\right)}^d\end{array}$$ $$\underset{d\to \infty }{\lim }\frac{V_{S_1}}{V_{S_2}}=0$$

all the volume is inside the shell

High dimensional Gaussian

$X\sim N(0,{\sigma }^2{I}_d)$

$$E[||x|{|}^2]=E[x_1^2+x_2^2+\cdots +x_d^2]=$$

Central Limit Theorem the sum / average is concentrated around the mean s $d\to \infty$

$$\frac{1}{d}||X|{|}^2\sim N\left({\sigma }^2,\frac{1}{d}\right)$$

as $d$ increases, the $\frac{1}{d}||X|{|}^2$ converges to ${\sigma }^2$ Thus length of almost all samples vectors will be ${\sigma }^2$ Thus in high dim, a Gaussian is a shell of sphere $\sigma \sqrt{d}$ and most of the density is in this shell. The point of the max density is still the mean (0)

Curse of Dimensionality

In theory, adding new features will not increase $\rho (\mathrm{error})$ informative feature

informative features uninformative feature CCDs still overlap

quality of CCD estimates

• density estimates for high-dim need more data! e.g. high-dim histogram $[0,1{]}^d$
• on average suppose we want 1 sample / bin

In general, desired training set size = $O(e^p)$, $p$ is the number of parameters.

CCD

CCD = Class Conditional Desnity P(x | C_i)

• reduce number of parameters (complexity of model)
• reduce number of features (dimensionality reduction) reduce # parameters
• create more data
  • Bayesian formulation (virtual samples)
  • data augmentation

Linear Dimensionality Reduction

• summarize correlated features with fewer features
• How?

The data lives in a low-dimensional subspace

linear operation

Principal Component Analysis (PCA)

Idea: if the data lives in a subspace it will look flat in some directions.

if we fit a Gaussian, it will be highly skewed

eigen-decomposition: $\Sigma =V\Lambda V^T$

• each $v_i$ defines an axis of ellipse
• each ${\lambda }_i$ defines the width along axis.

keep the large eigenvalues

select $v_i$ with the largest eigenvalues (principle components) to find the subspace where data “lives”

Receipt of PCA:

1. calculate Gaussian: $\mu =\frac{1}{n}{\sum }_{i=1}^N{x}_i$, $\Sigma =\frac{1}{n}{\sum }_{i=}^N(x_i-\mu )(x_i-\mu {)}^T$
2. eigen decomp: $\Sigma =V\Lambda V^T$
3. sort eigenvalues for largest to smallest
4. select top-k eigenvectors: $\Phi =[v_1,\dots ,v_k]$
5. project $X$ onto $\Phi$: $z={\Phi }^T(x-\mu )\in {\mathbb{R}}^K$
6. $z$ as new feature vector, BDR as usual

Notes: This selection of $\Phi$

1. maximizes the variance of the projected training data ${\sum }_{i=1}^N||z_i|{|}^2$
2. minimizes the reconstruction error of training data

$$\widehat{x_i}=\Phi (z_i+\mu )$$

can be implemented efficiently using SVD pick a $k$ that works pick $k$ to preserve $p\%$ of variance of data

Assumption - “noise” variance is smaller than the signal variance

PCA is optimal for representation (but not necessarily for classification)

no way to fit it! (we don’t use class information)

Linear Discriminant Analysis (Fisher Linear Discriminant)

• Find a linear projection that best separate the classes

input space (x)

class mean: $u_j=\frac{1}{n_j}{\sum }_{x_i\in x_j}{x}_i$

1-d space (z)

$m_j=w^T{\mu }_j$

	input space	1-d space
class mean	$u_j=\frac{1}{n_j}{\sum }_{x_i\in x_j}{x}_i$	$m_j=w^T{\mu }_j$
class scatter	$S_j={\sum }_{x_i\in C_j}(x_i-{\mu }_j)(x_i-{\mu }_j{)}^T$	$s_j=w^T{S}_{j}w$
input	$x_i$	$w^T{x}_i$

Idea: maximize distance between proj.

problem: $w$ is unconstrained $⟹$ need normalization

Fisher’s Idea:

$$\begin{array}{rl}{w}^{\ast }& =\arg \underset{w}{\max }\frac{(m_1-m_2{)}^2}{S_1+S_2}\\ & =\arg \underset{w}{\max }\frac{(m_1-m_2{)}^T(m_1-m_2)}{S_1+S_2}\\ & =\arg \underset{w}{\max }\frac{({\mu }_1-{\mu }_2{)}^{T}w{w}^T({\mu }_1-{\mu }_2)}{w^T(S_1+S_2)w}\\ & =\end{array}$$

高内聚，低耦合