Lecture 6: Classification and decision theory

Decision theory is often part of the exam.

So thoroughly review that.

  • Optimal classifiers and expected loss
  • Curse of dimensionality
  • Discriminant functions $C_k = f(x)$
    • Function that immediately returns class

For next week:

  • Conditional probability distribution model
  • Probabilistic generative models
  • Probabilistic discriminative models; logistic regression
  • Laplace estimation
  • Bayesian ...

Decision theory

Inference: given (x,t), learn p(x,t) and estimate p(x,t) for new values of x (and possibly all t)

Decision: for any new value of x estimate the 'best' t.

In practical applications, having a probability distribution is not enough: we need to decide on a course of action.

For example, we can use Bayes' theorem on classes. How do we use this model to decide on the best action?

We can build a classifier on the resulting probability distribution.

A classifiers distributes in regions such that in each region a single class is assigned.

We want to maximize the number of correct classifications. You want the curve of the true class to be above the curve of the false class.

$k= argmax_xp(x, C_k) = argmax_xp(C_k|x)$

Because we can divide by x because it's independent, does not change the argmax:

$$P(C,X)=P(C_k|X)P(X)$$

$$P(C,X)/P(X)=P(C_k|X)$$

Slide 4: note that $\hat{x}$ is a decision boundary; and $x_0$ is optimal boundary.

Colors are misclassifications; but confusing since

Medical example

If P(Cancer|X)=0.3, the chance is higher that the patient does not have cancer.

But simply deciding 'no' is not enough, because it takes a lot of risk.

So instead we take into account the expected loss for decisions, which we factor in by multiplying the probabilities for both classes with it.

Using a loss matrix. See slide 7.

If we now revisit the example, we see that we are rather "safe than sorry".

Reject option

We can also refrain from deciding if we set a threshold for the minimum amount of certainty needed for a decision. Answer "don't know" otherwise.

We need to have access to the probabilities for this.

Discriminant functions

We can also directly learn a decision rule/classifier without the intermediate step of defining a probability model.

The advantage of knowing the probabilities is that we can reject unlikely inputs x.

Approaches:

  • Generative: Keep the conditional probability in your model only; the prior changes over time.
  • Discriminative model: Learn the inference $p(C_k|x)$ directly; simpler model.
  • Discriminative function: Learn f(x) discriminant function; maps x directly onto a class label. This is even simpler.

Review slide 12.

Advantages of probability models

Advantages of probabilistic models over discriminative models

  • Minimize risk: the loss matrix may change over time whereas the class probabilities may not
  • Reject option: one can reject uncertain class assignments
  • Unbalanced data: You can compensate for balanced data; simple decision boundaries are very sensitive to this (e.g. classifying 99% as healthy to minimize loss, since most people are healthy)

We can combine models for $p(x|C_k)$ and $p(y|C_k)$. If we already know the class $C_k$, we can apply naive Bayes assumption to create the model on the joint $p(x,y|C_k)=P(x|C_k)p(y|C_k)$

This way you can combine test results.

Loss function for regression

If we generalize to continuous functions, the loss matrix becomes a loss function L(t,y(x))

So we're back at computing the expected loss; that we then in turn minimize.

For the minimum with quadratic loss is the average on the conditional $E_t[t|x]$.; the mean of the conditional distribution p(t|x).

Nearest-neighbour classification

1-NN is < 2 times the optimal when N -> Inf.

K-NN is optimal when K, N -> Inf, and K/N -> 0.

Curse of dimensionality

We cannot rely on our geometrical intuitions shaped in a 3D world and have to be careful.

Space in a 100D world is almost empty compared to a 3D world.

Imagine we have a "binning" classifier. This approach scales exponentially with dimensions. For D dimensions, we need n^D hypercubes for grid with length n.

Same problem for polynomials in multiple dimensions, scaled as M^D (or D^M?)

Q: Have 10-dimensional hypersphere with radius=1; which volume is in shell between r=0.5 and r=1.

In 10 dimensions, almost all volume is already in that "outer" shell (>0.999).

Meaning: almost all data points are at more or less the same distance because almost all data lies on the boundary of the sphere.

In 2D we already see that the area of the outer shell is larger than the inner circle. This effect is stronger in higher dimensions.

Same for D-dimensional Gaussians.

In a 1D Gaussian, most of the data is in the center of the distribution. In a higher-dimensional Gaussian, the data is instead concentrated in a thin shell $r ~ \sigma \sqrt{D}$. Most data is far from origin, and has almost the same distance to the origin.

So... can we do machine learning in high dimensions?

Machine learning in higher dimensions

Usually the data is concentrated in a lower dimensional subspace. Not all dimensions are relevant for solving a problem.

Object located in 3D -> images of objects are N-D -> there should be 3D manifold (curved subspace).

If we assume some smoothness, we can do local interpolation (also needed in low dimensions). (I.e. the object does not change if we move it a centimeter in space)

Classification

Chapter 4.

Regression versus classification

Regression ...

Classification uses discrete sets of classes.

  • Two classes: targets t in {0,1}
  • 1-K-encoding

Linear models for regression and classification

Review slide 29; and lecture.

Something is still linear, but not linear in weights; generalized linear. Called activation function in machine learning.

w^T(x1-x2)=0; because this inner product is 0, we know that the weight vector is orthogonal to x.

Review generalization to multiple classes; slide 31.

Decision boundaries $y_k(x)=y_j(x)$.

Convex spaces; missed that point.

In any case, Tom Classen adds: "in machine learning ’convex’ often means ‘easy to find the optimal answer’ ... like in a convex optimization problem there is only one optimum which is then also the global optimum... so if you can show/know your problem is convex then this can be really helpful"

Proof on slide 32.

Least-squares for classification?

Example slide 33; 4.1.3 in the book.

Least-squares is too sensitive to outliers. Logistic regression more appropriate.

Fisher's linear discriminant

If we have high dimensional data, we can project it onto lower dimensions in order to find the decision boundary in lower-D space.

Projection: y=w^t x

We want to find a projection such that the classes will be separated well in that lower dimensional space.

See slide and exercise 4.4.

Fisher's linear discriminant tries to project into lower dimension such that:

  • Maximize difference between means of classes
  • But also minimize variance within the classes

project both ... and project data (?)

Review 4.1.4.

How do we do this combined optimization? Fisher defined a loss function that balances both aspects.

In Matrix notation (slide 37): see exercise 4.5

(m2-m1)^Tw -> these are scalars.