CSCI5521 Homework 1 Solution

Questions
1. (30 points) Consider the class of K-interval classifier IK in R which is specified by K intervals [a1,b1], [a2,b2],...,[aK,bK] and labels any example positive iff it lies inside any of the K intervals.
(a) What is the VC dimension of I1 denoted by VC(I1)? Prove your answer. You need to show why the classifiers can shatter VC(I1) data points but not VC(I1)+1 data points.
(b) What is the VC dimension of I2 denoted by VC(I2)? Prove your answer. You need to show why the classifiers can shatter VC(I2) data points but not VC(I2)+1 data points.
(c) What is the VC dimension of IK denoted by VC(IK)? Prove your answer. You need to show why the classifiers can shatter VC(IK) data points but not VC(IK)+1 data points.
2. (30 points) Find the Maximum Likelihood Estimation (MLE) for the following pdf. In each case, consider a random sample of size n. Show your calculation:

(Hint: You can draw the likelihood function and pick a
θ based on all the data points.)
3. (30 points) Let P(x|C) denote a Bernoulli density function for a class C ∈ {C1,C2} and P(C) denote the prior,
(a) Given the priors P(C1) and P(C2), and the Bernoulli densities specified by p1 ≡ p(x = 0|C1) and p2 ≡ p(x = 0|C2), derive the classification rules for classifying a sample x into C1 and C2 based on the posteriors P(C1|x) and P(C2|x). (Hint: give rules for classifying x = 0 and x = 1.)
(b) Consider D-dimensional independent Bernoulli densities specified by pij ≡ p(xj = 0|Ci) for i = 1,2 and j = 1,2,...,D. Derive the classification rules for classifying a sample x into C1 and C2. It is sufficient to give your rule as a function of x.
(c) Follow the definition in 3(b) and assume D = 2, p11 = 0.6, p12 = 0.1, p21 = 0.6, and p22 = 0.9. For three different priors (P(C1) = 0.2,0.6,0.8 and P(C2) = 1 − P(C1)), calculate the posterior probabilities P(C1|x) and P(C2|x). (Hint: Calculate the probabilities for all possible samples (x1,x2) ∈ {(0,0),(0,1),(1,0),(1,1)}).
4. (30 points) Using your answers from Question 3 and the provided training, validation, and test datasets, write a Python program to calculate the maximum likelihood estimation on the training set. Consider the prior defined as
(1)
and P(C2) = 1−P(C1). Using the learned Bernoulli distributions and the given prior function, classify the samples in the validation set using your classification rules for σ = −5,−4,−3,−2,−1,0,1,2,3,4,5. Finally, choose the best prior (the one that gives the lowest error rate on the validation set) and use it to classify the samples in the test set. Print to the Python console (either in terminal or PyCharm) a table of error rate of each prior on the validation set and the error rate using the best prior on the test set.
Instructions
• Programming Questions: All programming questions must be written in Python, no other programming languages will be accepted. Only Numpy can be used in this assignment. The code must be able to be executed from the terminal command prompt on the cselabs machines. Each function must take the inputs in the order specified and display the textual output via the Python console (either in terminal or PyCharm). For each part, you can submit additional files/functions (as needed) which will be used by the main functions specified below. Put comments in your code so that one can follow the key parts and steps. Please follow the rules strictly. If we cannot run your code, you will receive no credit.
– Question 3:
∗ Training function in Bayes learning.py: Bayes Learning(training data , validation data). The function returns the outputs (p1: learned Bernoulli parameters of the first class, p2: learned Bernoulli parameters of the second class, pc1: best prior of the first class, pc2: best prior of the second class). It must also print to the terminal (sprintf) a table of error rates of all priors.
∗ Testing function in Bayes testing.py: Bayes Testing(test data, p1: the learned Bernoulli paramter of the first class, p2: the learned Bernoulli paramter of the second class, pc1: the learned prior of the first class, pc2: the learned prior of the second class). The function must print to the Python console (either in terminal or PyCharm) the error rate on the test dataset.
– Error rate: Error rate is the percentage of wrongly classified data points divided by the total number of classified data points.
• Report: Solutions to Questions 1, 2 and 3 must be included in a report. The table of error rates on the validation set and the error rate on the test set for Question 4 must also be included in the report.
• Things to submit:
1. hw1 sol.pdf: A document which contains the report with solutions to all questions. Scanned answer sheets need to be clean and 100% legible.
2. Bayes Learning.py and Bayes Testing.py: Code for Question 4.
3. Any other files, except the data, which are necessary for your code.
• Submit: All material must be submitted electronically via Canvas.