Decision Theory Continued

  • Discriminant functions: the perceptron
  • Probabilistic generative models P(x|Ck)
  • Probabilistic discriminative models: logistic regression
  • Laplace approximation and BIC
  • Bayesian logistic regression

The Perceptron

Linear discriminant model relevant in history of pattern recognition and neural networks.

  • Perceptron learning rule + convergence, Rosenblatt (1962)
  • Perceptron critique (Minsky and Papert, 1969) -> the "Dark ages of neural networks"
    • Too restrictive and not widely applicable.
  • Revival in the 80s with backpropagation.

$y(x) = sign(w^T\phi(x))$ with $\phi(x)$ being a feature vector

$sign(a) = +1 if a \leq 0, else -1.

The perceptron algorithm: seek w such that $w^T\phi(x)>0$ for C1 and <0 for C2; with target coding t=+1 and t=-1.

If we define it as such, we always want $t_n w^T\phi(x)>0$; this means you are correct, either for positive or negative class. Incorrect predictions will always be negative.

Error is defined only on falsely predicted classes.

$E_p(w)=-\sum_{n \in M} t_n w^T\phi(x)>0$

This error criterion is always positive or equal to zero (if optimal solution).

Converges in finite number of steps if the data is linearly separable (and I guess if your learning rate isn't too big).

Learning rule can be derived from $w^(t+1)=w^t - \eta \nablaE(w)$; cf. to gradient descent.

Perceptron critique

  • There is no unique solution
    • We find a weight vector that linearly separates the classes, but depending on the order of points visited and the initial we can get multiple boundaries that perfectly separate the classes
    • But generally we want to know which one would be optimal
  • No probabilistic output; so no estimate of how good your boundary is.
  • Only works for linearly separable problems. Most functions are not; and even for lin. separable problems noise can make them not separable.

Probabilistic generative models

If we have a generative model $P(x|Ck)$, we can use Bayes' rule to find $P(Ck|x)$

If I divide all terms by $p(x|Ck)p(Ck)$, we end up with a function that takes the form of a sigmoid over a, where a is the log-odds of C1 and C2 (assuming binary).

We are now talking about binary classification.

Cf. 202010131120-logit.md

Very cool! If we know the densities and prior, we can always come up with a model that looks like a sigmoid!

Sigmoid

Nice properties

$\sigma(-a)=1-\sigma(a)$

$a = ln \frac{\sigma}{1-\sigma}$

Decision boundary at x=0, y=0.5 for max uncertainty.

Extension to softmax

Sigmoid is only for binary classification. If we extend to k classes, we get the softmax.

Slide 47. We still apply Bayes' rule, but now we take the sum of the exponents in the denominator.

Review/derive.

Gaussian Mixture Model

  • Suppose each class k can be modeled as a Guassian
    • $p(x|k) = N(x|\mu_k, \Sigma_k)$
  • The combined distribution is a Gaussian mixture model.
    • With mixing coefficients $\pi_k$; i.e. we have a weighted combination of Gaussians.
  • Constraints on mixing components to ensure the mixture model is itself a valid probability distribution
    • Mixing components should be non-zero
    • Sum of mixing components should be 1

This is not just a classification model; we can approximate any continuous function (if we assign each data point its own class)! (Cf. Ch. 6)

Easy to learn when K is known (cf. slide 51)

Continuous inputs

If we apply the formula $a_k$ to a Gaussian, we get the formula on slide 51. We have a log that cancels the exponent term.

We often the covariance matrix is the same for all terms; mainly the means of the distributions vary. This assumption simplifies calculation of the decision boundaries because then these covariances drop out. We only keep factors that vary for individual classes; if something is the same for each class, we do not care about it for determining the relative contribution of each term.

As a result, the discriminant function is linear; or a hyper-plane in multiple dimensions.

When we drop the assumption of equal covariance matrices, we get a quadratic decision boundary. This is still fine, but then the computation becomes quite complex and it's not that easy as now to find a clean analytic formula.

Maximum Likelihood Solution

See slide 53.

REVIEW

Discriminative vs generative models

Slide 55.

  • No extra effort with joint probabilities; we directly use conditional probabilities instead.
  • Usually fewer parameters
  • ...
  • ... some more; didn't pay attention.

Fixed basis functions

For basis function $\phi(x)$, we can make non-linearly separable problems linearly separable in a higher order.

Logistic regression

We established we can frame classification problems in the form of a sigmoid. So now we can define our problem as such

$p(C1|\phi)=\sigma(w^T\phi)$

This is a discriminative model, if I'm not mistaken.

We now have M-dimensional feature space; less that for Gaussians (cf. 57)

N.B. when we write out our error function now by taking the log over the likelihood, we get the entropic error function!

We can use ML to estimate parameters w. Do we?

Unlike squared error, our $\nablaE(w)$ does not have a closed form solution, even though the form is very simple.

When weights are linearly separable we risk overfitting with w -> $\inf$.

Intermezzo: Tayler Expansion and Newton's method

...

If you have a certain expression for an error function, you can make an approximation around the error function in terms of a quadratic function.... this is handy because we know a quadratic function has a unique minimum.

We can use the Hessian (its inverse) to directly minimize and solve $\nabla E(w)=0$. Now the main problem instead is to compute the inverse of the Hessian, which is costly in higher dimensions. So you can also approximate the Hessian.

If you can apply this trick, this is very efficient.

Iterative least squares

We can solve logistic regression by using the Newton-Raphson method, that uses the Hessian.

We can again take an iterative approach to basically have a very efficient form of gradient descent, specifically geared towards logistic regression.

Choose a w reasonably close to solution; is this assumed? This will double the amount of significant digits. However, we can find a closed form for the Hessian. See 62 and 4.3.3

Why do we take an iterative approach? Because we immediately just to the optimal solution assuming our quadratic approximation is correct. Because it isn't, we have to iterate a few times. After a step we have a new w and need to recompute R.