Description
-
Gaussian Classi cation
Let f (x j Ci) N( i; 2) for a two-class, one-dimensional classification problem with classes C1 and C2, P(C1) = P(C2) = 1=2, and 2 > 1.
-
Find the Bayes optimal decision boundary and the corresponding Bayes decision rule.
-
The Bayes error is the probability of misclassification,
Pe = P((misclassified as C1) j C2) P(C2) + P((misclassified as C2) j C1) P(C1):
Show that the Bayes error associated with this decision rule is
-
1
Za
1
2
Pe =
p
e z
=2dz
2
-
2
1
where a =
.
2
-
Isocontours of Normal Distributions
Let f ( ; ) be the probability density function of a normally distributed random variable in R2. Write code to plot the isocontours of the following functions, each on its own separate figure. You’re free to use any plotting libraries available in your programming language; for instance, in Python you can use Matplotlib.
-
1. f ( ; ), where =
2
1
3
and =
2
0
2
3
.
6
1
7
6
1
0
7
6
7
6
7
6
7
6
7
6
7
6
7
4
5
4
5
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 2
-
f ( ; ), where =
2
21
3
and =
2
1
4
3
.
6
7
6
2
1
7
6
7
6
7
6
7
6
7
6
7
6
7
3.
f ( 1; 1)
4
5
4
0
3
5
2
2
3
and 1
= 2 =
2
2
1
3
.
f ( 2; 2), where 1 =
2
2
, 2 =
0
1
1
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
4.
f ( 1; 1)
f ( 2; 2), where 1 =
4
0
5
, 2 =
4
2
5
, 1 =
2
2
1
4
5
2
2
1
3
.
2
2
3
2
0
3
1
1
3 and 2 =
1
4
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
5.
f ( 1; 1)
f ( 2; 2), where 1 =
4
1
5
, 2 =
4
51
3
, 1
4
2
2
50
3
4
2
2
51
3
.
2
1
3
2
1
=
0
1
and 2 =
1
2
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
4
5
4
5
4
5
4
5
-
Eigenvectors of the Gaussian Covariance Matrix
Consider two one-dimensional random variables X1 N(3; 9) and X2 12 X1 + N(4; 4), where N( ; 2) is a Gaussian distribution with mean and variance 2. Write a program that draws
-
= 100 random two-dimensional sample points from (X1; X2) such that the ith value sampled from X2 is calculated based on the ith value sampled from X1. In your code, make sure to choose and set a fixed random number seed for whatever random number generator you use, so your simulation is reproducible, and document your choice of random number seed and random number generator in your write-up. For each of the following parts, include the corresponding output of your program.
-
-
Compute the mean (in R2) of the sample.
-
-
-
Compute the 2 2 covariance matrix of the sample.
-
-
-
Compute the eigenvectors and eigenvalues of this covariance matrix.
-
-
-
On a two-dimensional grid with a horizonal axis for X1 with range [ 15; 15] and a vertical axis for X2 with range [ 15; 15], plot
-
-
-
-
all n = 100 data points, and
-
-
-
-
-
arrows representing both covariance eigenvectors. The eigenvector arrows should orig-inate at the mean and have magnitudes equal to their corresponding eigenvalues.
-
-
(e) Let U = [v1 v2] be a 2 2 matrix whose columns are the eigenvectors of the covariance matrix, where v1 is the eigenvector with the larger eigenvalue. We use U> as a rotation matrix to rotate each sample point from the (X1; X2) coordinate system to a coordinate system aligned with the eigenvectors. (As U> = U 1, the matrix U reverses this rotation, moving back from the eigenvector coordinate system to the original coordinate system). Center your sample points by subtracting the mean from each point; then rotate each point by U>, giving xrotated = U>(x ). Plot these rotated points on a new two dimensional-grid, again with both axes having range [ 15; 15].
In your plots, clearly label the axes and include a title. Moreover, make sure the horizontal and vertical axis have the same scale! The aspect ratio should be one.
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 3
Suppose we have a classification problem with classes labeled 1; : : : ; c and an additional “doubt”
category labeled c + 1. Let r : Rd ! f1; : : : ; c + 1g be a decision rule. Define the loss function
8
>0
>
>
>
>
>
L(r(x) = i; y = j) = < r
>
>
>
>
>
>
: s
if i = j i; j 2 f1; : : : ; cg;
if i = c + 1;
otherwise;
where r 0 is the loss incurred for choosing doubt and s 0 is the loss incurred for making a misclassification. Hence the risk of classifying a new data point x as class i 2 f1; 2; : : : ; c + 1g is
c
X
R(r(x) = ijx) = L(r(x) = i; y = j) P(Y = jjx):
j=1
1. Show that the following policy obtains the minimum risk when r s.
(a) Choose class i if P(Y = ijx) P(Y = jjx) for all j and P(Y = ijx) 1 r= s;
-
-
Choose doubt otherwise.
-
-
What happens if r = 0? What happens if r > s? Explain why this is consistent with what one would expect intuitively.
-
Maximum Likelihood Estimation
Let X1; : : : ; Xn 2 Rd be n sample points drawn independently from a multivariate normal distribu-tion N( ; ).
(a) Suppose the normal distribution has an unknown diagonal covariance matrix
-
2
22
3
6
2
7
2
=
6
1
7
3
6
7
6
7
6
7
6
:
:
7
6
:
7
6
7
6
7
6
7
6
2
7
6
7
6
7
6
d
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
4
5
and an unknown mean . Derive the maximum likelihood estimates, denoted ˆ and ˆ i, for and i. Show all your work.
-
Suppose the normal distribution has a known covariance matrix and an unknown mean A , where and A are known d d matrices, is positive definite, and A is invertible. Derive the maximum likelihood estimate, denoted ˆ, for .
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 4
As described in lecture, the covariance matrix Var(R) 2 Rd d for a random variable R 2 Rd with mean is
-
2
Cov(R2
;1R1)
Var(R2)
Cov(R2
; Rd)
3
Var(R) = Cov(R; R) = E[(R ) (R
)>] =
6
Var(R )
Cov(R1
;
R2)
: : :
Cov(R1
; Rd)
7
;
::
: :
::
6
:
:
:
7
6
7
6
7
6
7
6
7
6
7
6
Cov(Rd
;
R1)
Cov(Rd
;
R2)
: : :
Var(Rd)
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
6
7
where Cov(Ri; Rj) = E[(Ri i) (Rj
j)] and Var(4
Ri) = Cov(Ri; Ri).
5
If the random variable R is sampled from the multivariate normal distribution N( ; ) with the PDF
f (x) = p 1 e ((x )> 1(x ))=2;
(2 )dj j
then Var(R) = .
Given n points X1; X2; : : : ; Xn sampled from N( ; ), we can estimate with the maximum likeli-hood estimator
-
ˆ
1
n
>;
Xi1
) (Xi
=
n
(Xi
)
=
which is also known as the covariance matrix of the sample.
ˆ ˆ
(a) The estimate makes sense as an approximation of only if is invertible. Under what
circumstances is ˆ not invertible? Make sure your answer is complete; i.e., it includes all
cases in which the covariance matrix of the sample is singular. Express your answer in terms of the geometric arrangement of the sample points Xi.
(b) Suggest a way to fix a singular covariance matrix estimator ˆ by replacing it with a similar but
invertible matrix. Your suggestion may be a kludge, but it should not change the covariance matrix too much. Note that infinitesimal numbers do not exist; if your solution uses a very small number, explain how to calculate a number that is su ciently small for your purposes.
(c) Consider the normal distribution N(0; ) with mean = 0. Consider all vectors of length 1; i.e., any vector x for which kxk = 1. Which vector(s) x of length 1 maximizes the PDF f (x)? Which vector(s) x of length 1 minimizes f (x)? Your answers should depend on the properties of . Explain your answer.
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 5
In this problem, you will build classifiers based on Gaussian discriminant analysis. Unlike Home-work 1, you are NOT allowed to use any libraries for out-of-the-box classification (e.g. sklearn). You may use anything in numpy and scipy.
The training and test data can be found with this homework. Don’t use the training/test data from Homework 1, as they have changed for this homework. Submit your predicted class labels for the test data on the Kaggle competition website and be sure to include your Kaggle display name and scores in your writeup. Also be sure to include an appendix of your code at the end of your writeup.
-
Taking pixel values as features (no new features yet, please), fit a Gaussian distribution to each digit class using maximum likelihood estimation. This involves computing a mean and a covariance matrix for each digit class, as discussed in lecture.
Hint: You may, and probably should, contrast-normalize the images before using their pixel values. One way to normalize is to divide the pixel values of an image by the l2-norm of its pixel values.
-
(Written answer.) Visualize the covariance matrix for a particular class (digit). How do the diagonal terms compare with the o -diagonal terms? What do you conclude from this?
-
Classify the digits in the test set on the basis of posterior probabilities with two di erent approaches.
-
-
Linear discriminant analysis (LDA). Model the class conditional probabilities as Gaus-sians N( C; ) with di erent means C (for class C) and the same covariance matrix , which you compute by averaging the 10 covariance matrices from the 10 classes.
-
To implement LDA, you will sometimes need to compute a matrix-vector product of the form 1 x for some vector x. You should not try to compute the inverse of (nor the determinant of ). Instead, you should find a way to solve the implied linear system without computing the inverse.
Hold out 10,000 randomly chosen training points for a validation set. Classify each image in the validation set into one of the 10 classes (with a 0-1 loss function). Compute the error rate and plot it over the following numbers of randomly chosen training points: 100, 200, 500, 1,000, 2,000, 5,000, 10,000, 30,000, 50,000. (Expect some variation in your error rate when few training points are used.)
-
-
Quadratic discriminant analysis (QDA). Model the class conditional probabilities as Gaussians N( C; C), where C is the estimated covariance matrix for class C. (If any of these covariance matrices turn out singular, implement the trick you described in Q7(b). You are welcome to use k-fold cross validation to choose the right constant(s) for that trick.) Repeat the same tests and error rate calculations you did for LDA.
-
-
-
(Written answer.) Which of LDA and QDA performed better? Why?
-
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 6
-
Using the mnist data.mat, train your best classifier for the training data and clas-sify the images in the test data. Submit your labels to the online Kaggle competition. Record your optimum prediction rate in your submission. You are welcome to compute extra features for the Kaggle competition. If you do so, please describe your implemen-tation in your assignment. Please use extra features only for the Kaggle portion of the assignment.
In your submission, include plots of error rate versus number of training examples for both LDA and QDA. Similarly, include a plot of validation error versus the number of training points for each digit. Plot all the 10 curves on the same graph as shown in Figure 1. Which digit is easiest to classify? Include written answers where indicated.
Figure 1: Sample graph with 10 plots
-
Next, apply LDA or QDA (your choice) to spam. Submit your test results to the online Kaggle competition. Record your optimum prediction rate in your submission. If you use additional features (or omit features), please describe them.
Optional: If you use the defaults, expect relatively low classification rates. The TAs suggest using a bag-of-words model. You may use third-party packages to implement that if you wish. Also, normalizing your vectors might help.
HW3, ‘UCB CS 189, Spring 2020. All Rights Reserved. This may not be publicly shared without explicit permission. 7
