[SOLVED] Ece 50024 / stat 59800 homework 6 exercise 1. suppose that we have a learning scenario

Exercise 1.
Suppose that we have a learning scenario with 8 possible input vectors x1, . . . , x8, each being a 3-bit binary
vector. We are given a training dataset D that contains {(x1, y1), . . . ,(x5, y5)}. Each label yn is either ◦ or
•. The relationship between xn and yn is given by an unknown target function f : X → Y. Since there are
only three variables to be learned from data, there is a total of 2
3 possible f’s we can possibly have.They
are summarized in the figure below.
xn yn g f1 f2 f3 f4 f5 f6 f7 f8
0 0 0 ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
0 0 1 • • • • • • • • • •
0 1 0 • • • • • • • • • •
0 1 1 ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦
1 0 0 • • • • • • • • • •
1 0 1 ? ◦ ◦ ◦ ◦ • • • •
1 1 0 ? ◦ ◦ • • ◦ ◦ • •
1 1 1 ? ◦ • ◦ • ◦ • ◦ •The following exercises involve different choices of the hypothesis set H. You need to (i) Identify the
final hypothesis g by listing the 8 entries it has for the 8 input vectors x1, . . . , x8. For example, you can
write g = [◦, •, •, ◦, •, ◦, •, •]. (ii) Compute how many of the 8 possible target functions agree with g on
all the three out-sample points, on two of them, one one of them, and on none of them. For example, if
g = [◦, •, •, ◦, •, ◦, •, •], then it will match with three out-samples once (f4), match with two out-samples
three times (f2, f3, f8), etc.(a) H has only two hypotheses h1 and h2. The first hypothesis h1 always return •, and the second
hypothesis h2 always return ◦. The learning algorithm picks the hypothesis that matches the training
set D the most.(b) Same as (a), but the learning algorithm picks the hypothesis that matches the training set D the least.
(c) H = {h}, where h is the XOR operation. That is, h(x) = • if x contains an odd number of 1’s and
h(x) = ◦ if x contains an even number of 1’s.Exercise 2.
In this exercise, we shall illustrate, with a simple numerical example, that given a hypothesis set H = {h :
X → {+1, −1}} and samples {(xn, yn)}
N
n=1, if one does not let the hypothesis function h ∈ H be independent
of the samples when computing the in-sample error Ein, then the probability P(|Ein(h) − Eout(h)| > ϵ) does
not necessarily obey Hoeffding’s inequality.More specifically, for the final hypothesis g picked by the learning
algorithm based on the training samples, P(|Ein(g)−Eout(g)| > ϵ) does not necessarily satisfy the Hoeffding’s
inequality, and we indeed require the uniform bound.Consider the following random experiment. Suppose we have 1000 fair coins. We flip each coin independently
for N = 10 times.Let’s focus on 3 coins as follows:
• coin1 = the first coin flipped.
• coinrand = a coin you choose at random from the 1000 coins.
• coinmin = the coin that had the minimum frequency of heads. (You have 1000 coins and each is flipped
10 times. So one of the 1000 coins will have the minimum frequency of heads. In case of a tie, pick
the earlier one).Let V1, Vrand and Vmin be the fraction of heads we obtain for coin1, coinrand and coinmin respectively.
(a) What is the probability of getting a head for coin1, of getting a head for coinrand and of getting a head
for coinmin? Denote them by µ1, µrand and µmin, respectively.(b) In Python, repeat this entire experiment for 100, 000 runs to get 100,000 instances of V1, Vrand and
Vmin. Plot the histograms of the distributions of these three random variables.(c) Using (b), plot the estimated P(|V1 −µ1| > ϵ), P(|Vrand −µrand| > ϵ) and P(|Vmin −µmin| > ϵ), together
with the Hoeffding’s bound 2 exp(−2ϵ
2N), for ϵ = 0, 0.05, 0.1, …, 0.5.(d) Which coins obey the Hoeffding’s bound, and which ones do not? Explain why.
Hint: Note that µ1, µrand and µmin are not necessarily equal to E[V1], E[Vrand] and E[Vmin] respectively.
Pay particular attention to Vmin and its E[Vmin] and µmin!Exercise 3. Project Checkpoint #6
This is the final checkpoint for your project. As you can see, the amount of homework is reduced because I
understand that you need more time to focus on your project.The final project report is due on Apr 30, 2022, 4:59pm Eastern Time. Please submit through gradescope.
All reports must be typed using the ICML template (in LaTeX). The page limit is 10 pages. References do
not count towards the page limit.Also, please upload your code to a github repository and put the link to the repository in your report. If
you want to keep your repository private, you can upload to Purdue’s internal Github at https://github.
itap.purdue.edu/ as a private repository and add the teaching staff as collaborators.• Every report will be reviewed by 3 teaching staff. You can treat them as the conference reviewers.
• Each teaching staff will be asked to fill out a score sheet based on the following criteria listed on the
course website. Your score will be the average of the scores from three independent reviewers.– Does the paper clearly state the problem that the implemented machine learning model targets?
You will have to use your own language to describe the problem. Heavy penalty will be added for
copying (with moderate modification of) the original paper. Does the paper identify and clearly
descirbe similar works in the related work, and lists their advantages and disadvantages?– Does the paper explain the mathematical derivation well? You will have to use your own language
to form the mathematical derviation. Heavy penalty will be added for copying (with moderate
modification of) the original paper.– Does the paper clearly state the technical difficulties in the reimplementation and possible solutions?
– Does the paper identify, describe, and analyze the effect of different engineering practices, e.g.,
implementation tricks and parameter/hyperparameter choices, using scientific languages?
– Does the student train the implemented model using the dataset they select, and identify and
solve issues that prevent the model from convergence?– Does the paper analyze the experimental behaviors of their model on selected application and
compare with baselines?
– Are there sufficient experiments demonstrating the success of re-implementation?– Are the limitations/assumptions clearly stated in the paper? Are there overclaim? Heavy penalty
will be added for overclaim.
– The amount of work in the reimplementation.
– Is the paper easy to read? Are your ideas elaborated clearly?