SML Cheat sheet
Terminology
- The trace of a square matrix Tr(A) is the sum of elements on the main diagonal.
- is a linear operation
- Tr(A)=Tr(A.T)
Tricks
Writing a multiplication into an exponential: $c x e^a = e^{a} x e^{ln(c)} = e^{a + ln(c)}$
I got stuck at this one before:
$$(y-x)^T L y = y^T L y - x^T L y$$
Similar principle works when instead the right hand side is the difference.
Also:
$$y^T L x = x^T L y$$
Matrix properties
For square and invertable matrices:
$$(AB)^{-1} = B^{-1} A^{-1}$$
$$A^T B = B^T A$$
See appendix of Bishop.
Also there: positive semidefinite, p. 107.
Determinant of diagonal matrix is product of its diagonal terms.
Rules for expectations (and bit of variance)
- When i.i.d., expectation of product is product of expectations $E[xy]=E[x]E[y]$
- $E[cx]=cE[x]$
- $E[x+y]=E[x]+E[y]$
- $E[f^2]= Var[f] + (E[f])^2$
- Follows from definition $Var[f] = E[f^2] - (E[f])^2$
- Expectation over constant is that constant, so e.g. $E[ E[x] ] = E[x]$
Gaussians:
- For Gaussians, $E[x_i^2]=\mu^2 + \sigma^2$.
- See the rule above derived from the definition of variance
- $E[\mu_{ML}]=\mu$ (unbiased)
- $E[\sigma_{ML}^2] = \frac{N-1}{N}\sigma^2$ (biased estimator)
Dirac delta
Every time I want to instinctively use a "if statement", I should use a direct delta function.
Lagrange multiplier
- If you add the multiplier $\lambda(constraint)$, you get the constraint back by differentiating w.r.t. $\lambda$.
- Compute the gradient of the other variable
- In case of multiple variables, first find a solution to the one and then fill into the constraint
- Plug solution into the constraint
Jacobian
$$p(x) = p(u)|\frac{du}{dx}|$$
Picking from the same box
Pick uniformly from two boxes. What's the change of an outcome A for pick 2, assuming we pick from the same box as pick 1 (with replacement), but we don't know which box was picked. Because we don't know which box was picked, we marginalize out the box.
$$P(X2=A | X1=A) = P(X2=A|X1=A, B=1)P(B=1|X1=A)$$ $$+ P(X2=A|X1=A, B=2)P(B=2|X1=A)$$
Because $X1$ is independent of $X2$, we have
$$P(X2=A | X1=A) = P(X2=A|B=1)P(B=1|X1=A)$$ $$+ P(X2=A|B=2)P(B=2|X1=A)$$
Note that if we multiply with $P(B=1|X1=A)$ and not with $P(B=1, X1=A)$ because the latter scenario would remove the conditioning on $X1=A$.
Because we pick from the same box, we have $P(X2=A|B)=P(X1=A|B)$ greatly simplifying the calculation.
Covariance Matrices
- Determinant of a diagonal covariance matrix is just the product of the diagonal entries.
- Diagonal covariance matrix can be written as $\Sigma_{ij} = \sigma_i^2 I_{ij}$
- Inverse diagonal covariance matrix can be written as $\Sigma_{ij} = \frac{1}{\sigma_i^2} I_{ij}$
Gaussian Bayesian inference schema
If you have the full joint probability table, you can instead decompose into sub-Gaussians analytically.
See p. 93 Bishop.
Approach: write down explicit mapping between formula's and the variables used in the problem at hand.
If $\Lambda^{-1}$ is for example $\sigma_0^2$, then $\Lambda = \frac{1}{s_0^2}$
If you are transforming N samples from a univariate Gaussian into a single N-dimensional multivariate Gaussian, then the mean for each dimension will be the same. This means that $A=(1,1,...,1)^T$. This greatly simplifies solutions.
Some tricks are handy.
With that A, $A^T L A = N * \frac{1}{\sigma^2}$.
$A^T L y$, with $L^{-1}=\sigma^2 I$ and thus $L=\sigma^{-2}I$, instead can be written as
$$\frac{1}{\sigma^2}(x_1, ..., x_n) = \frac{N \bar{x}}{\sigma^2}$$
That's a clever trick leading to the usual notation of the Gaussian posterior. Of course the sum of all data points is N times the mean.
Also something that's often used: when you for example have the shape $A^T L A$ with $L=\beta I$, then you can take the $\beta$ in front.
$$\Phi^T \beta I \Phi = \beta \Phi^T \Phi$$.
When matching formulas on page 93, for multivariate recall that also A and b will be multi-dimensional.
KL-divergence
Be aware that KL divergence is not symmetric, and that you can also define KL-divergence "backwards". You may need the "reverse" KL-divergence when instead of KL(q||p) (where q is the posterior you are approximating) a formula uses KL(p||q).
See Kullback-Leibler divergence
The reverse KL-divergence is used in expectation propagation (see Bishop 468).
Design Matrix
$\Phi_{nj} = \phi_j(x_n)$
For example, in polynomial regression, the first column could correspond to all outcomes of basis function $\phi(x)=x^0$, the second to $\phi(x)=x^1$, third to $\phi(x)=x^2$ etc. So columns indicate basis functions, rows for the different inputs $x_n$.
Moore-Penrose pseudo-inverse: $(\Phi^T \Phi)^{-1} \Phi^T$. This is generalization of the notion of a matrix inverse, but then extended to nonsquare matrices.
Discrete distributions
$\Gamma(n) = (n-1)!$. Which means that when we encounter any factorial, we can conveniently write $n! = \Gamma(n+1)$.
$\int_{a}^{b} \mu^{a-1}(1-\mu)^{b-1} d\mu = \frac{\Gamma{a}\Gamma{b}}{\Gamma{a+b}}$
TODO: This follows, apparently, from the fact that the beta distribution is normalized.
Bayesian linear regression
Using least squares, we use additive Gaussian noise. This means that the likelihood will be an exponential function:
$$p(t | X, w, \beta) = \prod_{n=1}^N \mathbb{N}(t_n|w^T \phi(x_n), \beta^{-1})$$
(Where usually the training data X is left out to avoid clutter; note that t is a column vector of targets; w is a vector as well).
As a conjugate prior for linear Bayesian regression we thus use a Gaussian prior.
To simplify computations (by hand), we work in this course with zero-mean isotropic Gaussians with a single precision parameter $\beta$.
Note that the MAP solution is equal to the mean value $m_N$ of the posterior, since the mode of the Gaussian is equal to its mean.
Predictive distribution
See p. 156
General approach:
- Compute posterior of target variable
- Integrate out the weights
The formulas on p. 93 do this in one step.
With posterior mean vector $m_N$ the prediction, will be the basis functions applied to the means, i.e. $m_N^T \phi(x) = \phi(x)^T m_N$.
So the difference with the posterior is that the predictive distribution is a function of x!
You should therefore be careful to distinguish the training data and the input to the predictive distribution. Since we end up with a function of x, you should keep x explicit as a variable in the definition of the predictive distribution.
Properties
For N -> inf and simple linear regression, the posterior becomes independent of the initial hyperparameters $\alpha$ and $\beta$. You can show based on the components of $S_N$ that $S_N^{-1}$ goes to infinity, so $S_N$ goes to zero, independent of $\alpha$ and $\beta$. $\beta$ cancels out in the computation for the posterior mean (does this always hold for polynomial regression, or just the simplest linear regression?)
Unknown precision parameter
In most exercises we assume precision $\beta$ is known for an isotropic Gaussian prior. If both the regression weights and the precision is unknown, the conjugate prior $p(w, \beta)$ is the Gaussian-gamma distribution. The predictive distribution then is Student's t-distribution.
Vs. Gaussian processes.
If we use localized basis functions such as Gaussians, then in regions away from the basis function centres, the contribution from the second term in the predictive variance (3.59) will go to zero, leaving only the noise contribution $\beta^{-1}$. Thus, the model becomes very confident in its predictions when extrapolating outside the region occupied by the basis functions, which is generally an undesirable behaviour. This problem can be avoided by adopting an alternative Bayesian approach to regression known as a Gaussian process. (158)
Decision boundaries
If the expected loss over some test $x$ is asked, you 1) construct the loss matrix and 2) weigh all joint probabilities, i.e. with a loss matrix $L_{kj}$ with true class $k$ and predicted class $j$, you end up with two summations, over j and k. (If you do not also sum of j, your probabilities won't add up to 1)
When you care about determining a decision boundary, you instead want to condition on a particular classification, i.e. you want the posterior for the true classes, given test results.
Set e.g. $p(C=1 | x ) = p(C=2 | x)$.
With loss matrix you can add losses for different types of misclassifications. You then want to minimize the conditional expected classification loss.
- If you classify j=1, what's then the expected loss?
$$\mathbb{E}[L_j|x] = \sum_k p(C=k|x)L_{kj}$$
Read: for a given possible decision, look at each possible true class what the associated loss is, and weigh this with the (posterior) probability of that class being correct.
- Now recompute the decision boundary with the expected losses factored in
$$\mathbb{E}[L_1|x] = \mathbb{E}[L_2|x]$$
Generative vs. discriminative models vs. discriminant function
Generative models model both the input and output distribution. I.e. they aim to learn the density of the data which then, with prior, can be used to generate samples.
Discriminative models only model the conditional distribution of output (e.g. class label) given input.
You can also use a discriminant function which directly maps input to class labels. You then lose info on expected classification error.
Advantages of knowing the conditional class probabilities (so vs. discriminant function):
- Minimize risk by minimizing expected loss; it's ok if the loss matrix changes over time; the class distribution may remain the same so it's handy to have it modelled
- Reject uncertain class assignments
- Compensate for unbalanced data
Exercise could be to show something can be written as a discriminant function, e.g. $w_1^T x + w_0$. Approach: write out, find all linear terms in x, and take all remaining constant terms as $w_0$.
Matrix and vector derivatives
Derivative w.r.t. x over $x^T a$ is actually $a$. I encountered this in wk.6 ex 4c.
When doing a derivation over operations on a vector, try to write it out as a sum operation.
Then you can take a derivate with respect to one particular variable, e.g. $w_j$, so you can ignore the rest of the sum.
Fisher Linear Discriminant
- Project onto lower dimension $w^T x$ where $x$ is a D-dimensional vector.
- Typical decision boundary: $w^T x + w_0 = 0$, so can use $w^T x = -w_0$
- $m_k$ is mean of projected data
- Problem is that the classes may not be well separated in lower dimensionality
- Maximize between-class variance by separating the means
- This will still give overlap if the intra-class variance is large, so also make sure to minimize this at the same time
- Fisher criterion is ratio between between-class variance to within-class variance (sum of the within-class variance of each class)
For formulas, see p. 188-9. See result 4.30.
Note you still need to find a classification threshold.
When maximizing separation of means $w^T (m_1 - m_2)$, with the constraint that $\sum_i w_i^2 =c$, you'll find a weight vector proportional to $m_1 - m_2 $.
Sigmoid
See p. 197
Symmetry property!
$$\sigma(-a) = 1 - \sigma(a)$$
See week 5 ex 4.2: You can rewrite a posterior probability $p(C1|x)$ as a sigmoid over the log odds or logit function (divide both sides by the enumerator).
The log odds is the inverse of the sigmoid function.
See p.198 for softmax.
When doing a derivation on the log odds, make sure to look up the logaritmic derivative which follows from the chain rule:
$$\frac{ d ln f(x)}{ dx} = \frac{1}{f(x)} \frac{ df(x)}{dx}$$
Perceptron
Target encoding: {-1, 1}
We want $t_n w^T \phi(x_n) > 0$, so minimize the negative of this:
$$E_p(w) = - \sum_{n \in M} t_n w^T \phi(x_n)$$
Associate zero error for correct classifications, and for misclassifications update:
$$w^{t+1} = w^t + \eta \phi(x_n) t_n$$
The perceptron learning rule does not guarantee that the total error is reduced, because doing an update based on one misclassified input pattern may fix that one, but now cause others to be misclassified instead.
See perceptron.md .
Newton's Method and Iterative Reweighted Least Squares
See p. 207.
Uses Hessian Matrix, which contains the second derivative gradients w.r.t. weights w.
This does an exact form of gradient updating when the error is quadratic, which leads to a closed form solution for a linear regression problem with least squares.
For non-linear problems (e.g. when using a sigmoid), the Hessian matrix will have a dependency on the current weights. This means that it must be recomputed after weights are updated.
In this case it can be used in Iterative Reweighted Least Squares.
Gradient Descent
Look into convergence properties.
E.g. in a quadratic well (singe global minimum) we have convergence for $|1 - \eta \lambda_i| < 1$ and oscillations when $1 - \eta \lambda_i < 0$.
Bayesian Linear Regression
- Posterior: See 3.53 and 3.54 for main results.
- Predictive distribution: 3.58 and 3.59
- beta represents noise on the data
Gaussian Process
- GP cheaper then Bayesian linear regression when there are more input features than data points
- Predictive distribution GP: 6.66, 6.67
- For this type of assignment, they give you datapoints (x, t)
- Probably a prior mean of 0, because this is a common assumption
- Give you observational noise
- "as a function of x": also indication they are asking for the predictive distribution, since this depends on an input vector x
Clustering and Expectation Maximization (EM)
Responsibility $r_{nk}$ indicates to which cluster/mixture component $x_n$ is assigned to. It is 1 iff it is assigned to cluster k, 0 otherwise.
This is called the 1-of-K coding scheme.
When computing responsibilities by hand, it may be handy to instead use matrix computation on the whole dataset X.
$$\mu_{new} = \frac{1}{N_k} \gamma_{nk}^T X$$
Sampling
Gibbs:
- For Gibbs, you need conditional densitities.
- If you have a joint probability density of Gaussians, use the closed form solution to condition one subset on the other.
- Proposals are always accepted
Metropolis Hastings:
$p^{*}$ is the candidate, drawn from a proposal function.
$$A(z^{}, z^{(t)}) = min(1, \frac{ \tilde{p}(z^) } { \tilde{p}(z^{(t)}) })$$
The acceptance function evaluates the whether a candidate sample will be accepted or not. The candidate sample is accepted if $A(z^*, z^{(t)}) > u$, where $u$ is a uniform distribution over the unit interval (0,1).
If accepted, set the state to the accepted sample. Otherwise, keep the old state (in other sampling methods, you throw it away.)
If you use the log probability, also use the "log" acceptance criterion:
$$min(1, exp(p(z^*)-p(z^{(t)})))$$
Metropolis-Hastings satisfies detailed balance condition.
- Write out this condition (which contains transition probabilities)
- These transition probabilities can be written as product of proposal distribution and acceptance ratio:
$$p(\theta_j|\theta_i) = q( \theta_j | \theta_i) * A_{\theta_i \rightarrow \theta_j}$$
- Work out the acceptance criterior in both directions using a symmetric proposal distribution
- Fill in LHS and RHS of detailed balance, and verify they are equal.
Monte Carlo Markov Chains
- homogeneous if transition probabilities are the same for all timesteps
- invariant or stationary: each step leaves distribution for a candidate z the same
$$p^{}(z) = \sum_{z'}T(z', z)p^{}(z')$$
- detailed balance of transition probabilities: this is a sufficient but not necessary condition for an invariant distribution
- the chain is "reversible"
$$p^{}(z)T(z,z') = p^{}(z)T(z', z)$$
If we have detailed balance, the proposal distribution will be invariant:
$$\sum_{z'} p^{}(z')T(z',z) = \sum_{z'} p^{}(z)T(z,z') = p^{}(z') \sum_{z'} p(z'|z) = p^{}(z)$$
Where by definition $T(z,z') = p(z'|z)$ (probability of transition from z to z', is the probability of z' given z).
- ergodicity: with enough timesteps the distribution $p(z^{(t)})$ converges to invariant proposal distribution $p^*(z)$.
- ergodic Markov chain only has one equilibrium distribution
- A homogeneous Markov chain is ergodic.
Basic sampling
Using CDF F:
- Sample u from uniform X, transform with inverse of cdf $F^{-1}$
- Show $F^{-1}(u)$ follows X.
- For CDF we have $F(x) = P(X \leq x)$, i.e. probability that X is smaller than x
- Then it follows
$$P(F^{-1}(U) \leq x) = P(F (F^{-1}(U)) \leq F(x)) = P(U \leq F(x)) = F(x)$$
This uses that F is by definition increasing, so when $x \leq y$ we also have $F(x) \leq F(y)$.
Using PDF:
$$p(x) = p(u)| \frac{du}{dx} | = p(u) | \frac{dF(x)}{dx} = p(u)|F'(x)| = F'(x)$$
- Where we use $p(u)=1$ because... F is increasing so derivative is positive.
- PDF is the derivative of CDF, so p(x) on the left is equal to the pdf of X on the right.