Bayes Theorem

Bayes' Theorem

Bayes’ Theorem states that $$ p(F | E) = \frac{p(E|F)p(F)}{p(E|F)p(F) + p(E|\bar F)p(\bar F)} $$

Short form: $P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$

Link to original

Bayesian learning

no clue what's going on here

Maximum a posteriori (MAP) hypothesis: $\begin{array}{rl}{h}_{\text{MAP}}& =\arg \underset{h\in H}{\max }p(h|\mathcal{D})\\ & =\arg \underset{h\in H}{\max }\frac{p(\mathcal{D}|h)p(h)}{p(\mathcal{D})}\\ & =\arg \underset{h\in H}{\max }p(\mathcal{D}|h)p(h)\end{array}$

In some cases we assume that every hypothesis $h\in H$ is equally likely a priori. Then we only need to consider the likelihood $p(\mathcal{D}|h)$.

In this case, we want the maximum likelihood hypothesis $h_{\text{ML}}$: $h_{\text{ML}}=\arg {\max }_{h\in H}p(\mathcal{D}|h)$

Naive Bayes classifier

Practical approach to Bayesian learning, it is simple but effective and particularly resistant to overfitting because of its simplicity.

As a classifier, it fits the mould of: $p(y_i|{\text{x}}_i,\mathcal{D})$ where we learn an approximation of the mapping $\mathbf{x}$ to $y$: $y=f(\mathbf{x})$

$f(\mathbf{x})$ takes on values from a finite set $V$ (target value) ${\mathbf{x}}_i$ is a tuple / vector of feature values: ${\mathbf{x}}_i=⟨a_1,a_2,\dots ,a_n⟩$

In this setting, a new instance is classified by looking for: $V_{\text{MAP}}=\arg {\max }_{v_i\in V}p(v_i|a_1,a_2,\dots a_n)$ which Bayes’ theorem allows us to re-write as: $\begin{array}{rl}{V}_{\text{MAP}}& =\arg \underset{v_i\in V}{\max }\frac{p(a_1,a_2,\dots ,a_n|v_i)p(v_i)}{p(a_1,a_2,\dots ,a_n)}\\ & =\arg \underset{v_i\in V}{\max }p(a_1,a_2,\dots ,a_n|v_i)p(v_i)\end{array}$ We can estimate these values based on training data.

• $p(v_i)$ is based on number of times $v_i$ appears in training data
• $p(a_1,a_2,\dots ,a_n|v_i)$ is the proportion of case that have $v_i$ which also have $a_1,a_2,\dots ,a_n$

Number of possible combinations is large, you need to see them many times to get good estimates, so we need a lot of data to train.

So we need to simplify (Naive Bayes Assumption):

1. assume position does not matter (if applicable)
2. assume that features are conditionally independent given the target $v$ (strong independence assumption)

$p(a_1,a_2,\dots ,a_n|v_i)={\prod }_{j}p(a_j,v_i)$

• $p(a_j,v_i)$: look for all cases in which $v_i$ occurs and then compute the proportion which have $a_j$
• need much less data to be accurate

After calculating $p(v_i)$ and the $p(a_j,v_i)$, we can make predictions about the $v_i$ for a given ${\mathbf{x}}_k=⟨a_1,a_2,\dots ,a_n⟩$. $V_{\text{NB}}=\arg {\max }_{v_i\in V}p(v_i){\prod }_{j}p(a_j|v_i)$

When the assumption about conditional independence is satisfied, $V_{\text{NB}}=V_{\text{MAP}}$.

We can prove this. However, when it is not satisfied, $V_{\text{NB}}$ is often a good solution which we can establish by experimentation.

Small probabilities $⟨0.0053,0.0206⟩$

With more features we can easily get underflow errors, we avoid this by taking logs: $\begin{array}{rl}{V}_{\text{NB}}& =\arg \underset{v_i\in V}{\max }p(v_i)\prod _{j}p(a_j,v_i)\\ & =\arg \underset{v_i\in V}{\max }\log P(v_i)+\sum _j\log P(a_j|v_i)\end{array}$

Estimating probabilities

So far we’ve computed probabilities by counting, e.g. estimate $p(A=a|B=b)$ by: $\frac{n_c\text{ – total number of cases where }B=b}{n\text{ – total number of cases where }A=a}$

Good estimate most of the time but can be poor when $n_c$ is close to zero, which can happen if we only have a few samples. This can lead to overfitting.

We can instead find the $m$-estimate: $\frac{n_c+m\cdot p}{n+m}$

• $p$ is a prior estimate (before taking any data into account) Typical value of $p$ is $\frac{1}{k}$ if the feature has $k$ values
• $m$ is a constant, equivalent sample size (weight given to prior)

Slide 59-61 useless or gay porn?

Gaussian mixture models

$p({\mathbf{x}}^{\prime }|\mathcal{D})\text{ – probability of example }{\mathbf{x}}^{\prime }\text{ given data }\mathcal{D}$ Given a dataset $D$ of non-anomalous instances, is a new ${\mathbf{x}}^{\prime }$ anomalous? We model $p(\mathbf{x})$ to detect anomalous cases: $p({\mathbf{x}}^{\prime })<\text{threshold}$.

Might model each feature $x$ as a Gaussian distribution with mean $\mu$ and variance ${\sigma }^2$. Often, the data we are trying to model is much more complex.

A mixture model is a combination of probability models:

Univariate Gaussian mixture	Multivariate Gaussian mixture

In the general case, we mix $K$ base distributions (of any type) so that:

where ${\pi }_k$ are the mixing weights.

In other words, probability of an element ${\mathbf{x}}_i$ is the sum of probabilities assigned to ${\mathbf{x}}_i$ by each of the probability models in the mixture.

Most widely used mixture model is probably the mixture of Gaussians. Each model is a multivariate Gaussian with mean ${\mu }_k$ and covariance ${\Sigma }_k$ (matrix $n\times n$). The mixture is: $p({\mathbf{x}}_i)={\sum }_{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_i|{\mu }_k,{\Sigma }_k)$ which just assigns $x_i$ the sum of the probabilities given to it by each of the components.

When all Gaussians are univariate, we have: $p(x_i)={\sum }_{k=1}^K{\pi }_k\mathcal{N}(x_i|{\mu }_k,{\sigma }_k^2)$ Where ${\sigma }_k^2$ is the variance.

Example: modelling human height

We can’t just fit a single Gaussian as it doesn’t properly represent the data

Why is this useful?

• Lots of processes are Gaussian: lots of stuff in the world generates normally distributed data.
• Combinations of these things will be mixture models.

EM algorithm

Estimating means of k Gaussians

Assume $\mathcal{D}$ is generated by a mixture model. Pick a distribution with equal probability $\frac{1}{K}$ then pick a value according to the distribution. Then repeat.

slides 71-86

K-means clustering

k-Means Clustering

Say we have $n$ points $x_1,x_2,\dots ,x_n$. We want to partition them into $k$ sets $S_1,S_2,\dots ,S_k$ such that the cost of the partition is minimised, $c(S_1,S_2,\dots ,S_k)$:

$$c(S_1,S_2,\dots ,S_k)=\sum _{i=1}^n\underset{j\in [k]}{\min }\left[\begin{array}{c}||x_i-{\mu }_j|{|}_2^2\end{array}\right]$$

Where ${\mu }_i$ is the mid-point of each cluster, i.e. ${\mu }_i=\frac{1}{|S_i|}{\sum }_{j\in S_i}{x}_j$.

Where $||\cdot |{|}_2^2$ is the squared L2 norm (squared Euclidian distance).

Link to original

There are two types of K-means clustering:

• hard clustering: reports which cluster $x_i$ is part of
• soft clustering: probability that $x_i$ is in the cluster