Description
Questions
1. (10 points) What is the VC dimension, dI, of intervals in R? The target function
is specified by an interval [a,b], and labels any example positive iff it lies inside that
interval. Show how to shatter dI points with the function.
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:
(a) f(x|θ) = 1
θ−1
e
− x
θ−1 , x > 0, θ > 1
(b) f(x|θ) = (θ − 1)x
θ−2
, 0 ≤ x ≤ 1, 1 < θ < ∞
(c) f(x|θ) = 1
θ
, 0 ≤ x ≤ θ (Hint: You can draw the likelihood function)
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 the provided training, validation, and test datasets, write a Python
script to calculate the maximum likelihood estimation on the training set. Consider a
prior function defined with respect to sigma as
P(C1|σ) = 1 − e
−σ
, σ > 0 (1)
1
Instructor: Rui Kuang (kuang@umn.edu). TAs: Rachit Jas (jas00001@umn.edu) and Tianci Song
(song0309@umn.edu).
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
σ = 0.00001, 0.0001, 0.001, 0.01, 0.1, 1, 2, 3, 4, 5, 6. 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. (Hint: if some Bernoulli probabilities are 0, you can replace
them with a small probability such as 10−10 to avoid the numerical problem.)
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
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.
3
