Statistical Decision Theory

Question 1

What is the Expected Prediciton Error of a function?

Answer 1

EPE(f) = E[ (y - f(x))² ]

Question 2

Using MSE, what is the optimal prediction function?

Answer 2

f* = E_Y|X ( Y|X=x )

Question 3

How does k-NN approximate the optimal solution?

Answer 3

f_kNN(x) = Ave( yi|xi in Nk(x) )
1. The expectation is approximated by averaging over sample data.
2. Conditioning at a point is relaxed to conditionning on its neighbourhood.

Question 4

How does linear regression approximate the optimal solution?

Answer 4

f_LR(x) = x.T * w
LR replaces expectation by average over the training data.

Question 5

What is the inductive bias of an algorithm and what are those of k-NN and LR?

Answer 5

The inductive bias of an algorithm is the set of assumptions made by using it.
The inductive bias of k-NN is that it assumes the target function is well approximated by a locally constant funciton.
The inductive bias of LR is that it assumes the target function is well approximated by a globally linear funciton.

Question 6

What is the “curse of dimensionality”?

Answer 6

To cover a given percentage of an output space, the more dimensions it has, the wider the range you’ll need to cover.
For example, to cover 25% of a 2D square, you’ll need to consider a square which has 50% its width and 50% its height. To cover the same percentage of a 3D cube, you’ll need to cover ~63% of each of its dimension.

Question 7

What is the 0/1 loss function?

Answer 7

For a classification problem, it is the function which is 0 for correct classifications and 1 for misclassifications.

Question 8

What is the Bayes Classifier?

Answer 8

f_BC(x) = argmax[ P(g|X=x) ] for g in G (the set of all possible classes)
It is the optimal solution for a classification problem with 0/1 loss function.

Question 9

What is the Bayes Error Rate?

Answer 9

It is the error rate of the Bayes classifier. It is the lowest possible error rate a classifier can achieve.