The Learning Problem

1. Which of the following problem is suited for machine learning if there is assumed to be enough associated data? Choose the correct answer; explain how you can possibly use machine learning to solve it.
   • predicting the winning number of the next invoice lottery
   • calculating the average score of 500 students
   • identifying the exact minimal spanning tree of a graph
   • ranking mango images by the quality of the mangoes
   • none of the other choices
2. Which of the following describes an machine learning approach to build a system for spam detection? Choose the correct answer; explain briefly why you think other choices are not machine learning.
   • flip 3 fair coins; classify the email as a spam iff at least 2 of them are heads
   • forward the email to 3 humans; classify the email as a spam iff at least 2 of them believe so
   • produce a list of words for spams by 3 humans; classify the email as a spam iff the email contains more than 10 words from the list
   • get a data set that contains spams and non-spams, for all words in the data set, let the machine calculate the ratio of spams per word; produce a list of words that appear more than 5 times and are of the highest 20% ratio; classify the email as a spam iff the email contains more than 10 words from the list
   • get a data set that contains spams and non-spams, for all words in the data set, let the machine decide its spam score; sum the score up for each email; let the machine optimize a threshold that achieves the best precision of spam detection; classify the email as a spam iff the email is of score more than the threshold

Perceptron Learning Algorithm

Next, we will play with multiple variations to the Perceptron Learning Algorithm (PLA).

3. Short scales down all x_n (including the x₀ within) linearly by a factor of 4 before running PLA. How does the worst-case speed of PLA (in terms of the bound on page 16 of lecture 2) change after scaling? Choose the correct answer; explain your answer.
   • 4 times smaller (i.e. faster)
   • 2 times smaller

• 2 times smaller
• unchanged

• 2 times larger (i.e. slower)

4. The scaling in the previous problem is equivalent to inserting a learning rate to the PLA update rule

wt+1 wt + yn(t)xn(t)

with. In fact, we do not need to use a fixed . Let _t denote the learning rate in the t-th iteration; that is, let PLA update w_t by

wt+1 wt + t yn(t)xn(t)

whenever (x_n(t),y_n(t)) is not correctly classified by w_t. Dr. Adaptive decides to set so

longer x_n(t) will not affect w_t too much. Let

,

which can be viewed as a normalized version of the on page 16 of lecture 2. The bound on the same page then becomes ^p after using this adaptive _t. What is p? Choose the correct answer; explain your answer.

• 0

[b] 1

[c] 2

[d] 4

[e] 8

5. Another possibility of setting _t is to consider how negative y_n(t)w_t^Tx_n(t) is, and try to make

0; that is, let w_t+1 correctly classify (x_n(t),y_n(t)). Which of the following update

rules make 0? Choose the correct answer; explain your answer.

[a] wt+1 wt + 2 yn(t)xn(t)

6. Separate decides to use one of the update rules in the previous problem for PLA. When the data set is linear separable, how many choices in the previous problem ensures halting with a perfect line? Choose the correct answer; explain the reason behind each halting case.

[a] 1

• 2
• 3
• 4
• 5

Types of Learning

7. One shared technique between the famous AlphaGo, AlphaGo Zero, and AlphaStar is called selfpracticing: learning to play the game by practicing with itself and getting the feedback from the judge environment. What best describes the learning problem behind self-practicing? Choose the correct answer; explain your answer.
   • human learning
   • unsupervised learning
   • semi-supervised learning
   • supervised learning
   • reinforcement learning
8. Consider formulating a learning problem for building a self-driving car. First, we gather a training data set that consists of 100 hours of video that contains the view in front of a car, and records about how the human behind the wheel acted with physically constrained choices like steering, braking, and signaling-before-turning. We also gather another 100 hours of videos from 1126 more cars without the human records. The learning algorithm is expected to learn from all the videos to obtain a hypothesis that imitates the human actions well. What learning problem best matches the description above? Choose the correct answer; explain your answer.
   • regression, unsupervised learning, active learning, concrete features
   • structured learning, semi-supervised learning, batch learning, raw features
   • structured learning, supervised learning, batch learning, concrete features
   • regression, reinforcement learning, batch learning, concrete features
   • structured learning, supervised learning, online learning, concrete features

(We are definitely not hinting that you should build a self-driving car this way. 😀 )

Off-Training-Set Error

As discussed on page 5 of lecture 4, what we really care about is whether g f outside D. For a set of universe examples U with D U, the error outside D is typically called the Off-Training-Set (OTS) error

1 X

E_ots(h) = h(x) 6= y .

|U D| (x,y)UD J K

9. Consider U with 6 examples

Run the process of choosing any three examples from U as D, and learn a perceptron hypothesis (say, with PLA, or any of your human learning algorithm) to achieve E_in(g) = 0 on D. Then, evaluate g outside D. What is the smallest and largest E_ots(g)? Choose the correct answer; explain your answer.

[e] (0,1)

Hoeffding Inequality

10. Suppose you are given a biased coin with one side coming up with probability . How many times do you need to toss the coin to find out the more probable side with probability at least 1 using the Hoeffdings Inequality mentioned in page 10 of lecture 4? Choose the correct answer; explain your answer. (Hint: There are multiple versions of Hoeffdings inequality. Please use the version in the lecture, albeit slightly loose, for answering this question. The log here is log_e.)

Bad Data

11. Consider x = [x₁,x₂]^T R², a target function f(x) = sign(x₁), a hypothesis h₁(x) = sign(2x₁x₂), and another hypothesis h₂(x) = sign(x₂). When drawing 5 examples independently and uniformly within [1,+1] [1,+1] as D, what is the probability that we get 5 examples (x_n,f(x_n)) such that E_in(h₂) = 0? Choose the correct answer; explain your answer. (Note: This is one of the BAD-data cases for h₂ where E_in(h₂) is far from E_out(h₂).)

[a] 0

[b] [c]

[d]

[e] 1

12. Following the setting of the previous problem, what is the probability that we get 5 examples such that E_in(h₂) = E_in(h₁), including both the zero and non-zero E_in cases? Choose the correct answer; explain your answer. (Note: This is one of the BAD-data cases where we cannot distinguish the better-E_out hypothesis h₁ from the worse hypothesis h₂.)

[a]

[b] [c] [d]

[e]

13. According to page 22 of lecture 4, for a hypothesis set H,

BAD D for H h H s.t.

Let x = [x₁,x₂, ,x_d]^T R^d with d > 1. Consider a binary classification target with Y = {+1,1} and a hypothesis set H with 2d hypotheses h₁, ,h_2d.

• For i = 1, ,d, h_i(x) = sign(x_i).
• For i = d + 1, ,2d, h_i(x) = sign(x_id).

Extend the Hoeffdings Inequality mentioned in page 10 of lecture 4 with a proper union bound. Then, for any given N and , what is the smallest C that makes this inequality true?

P[BAD.

Choose the correct answer; explain your answer.

• C = 1 [b] C = d
• C = 2d
• C = 4d [e] C =

Multiple-Bin Sampling

14. We then illustrate what happens with multiple-bin sampling with an experiment that use a dice (instead of a marble) to bind the six faces together. Please note that the dice is not meant to be thrown for random experiments. The probability below only refers to drawing the dices from the bag. Try to view each number as a hypothesis, and each dice as an example in our multiple-bin scenario. You can see that no single number is always greenthat is, E_out of each hypothesis is always non-zero. In the next two problems, we are essentially asking you to calculate the probability of getting E_in(h₃) = 0, and the probability of the minimum E_in(h_i) = 0.

Consider four kinds of dice in a bag, with the same (super large) quantity for each kind.

• A: all even numbers are colored green, all odd numbers are colored orange
• B: (2,3,4) are colored green, others are colored orange
• C: the number 6 is colored green, all other numbers are colored orange
• D: all primes are colored green, others are colored orange

If we draw 5 dices independently from the bag, which combination is of the same probability as getting five green 3s? Choose the correct answer; explain your answer.

• five green 1s
• five orange 2s
• five green 2s
• five green 4s [e] five green 5s

15. Following the previous problem, if we draw 5 dices independently from the bag, what is the probability that we get some number that is purely green? Choose the correct answer; explain your answer.

[a]

[b] [c] [d]

[e]

Experiments with Perceptron Learning Algorithm

Next, we use an artificial data set to study PLA. The data set with N = 100 examples is in

http://www.csie.ntu.edu.tw/~htlin/course/ml20fall/hw1/hw1_train.dat

Each line of the data set contains one (x_n,y_n) with x_n R¹⁰. The first 10 numbers of the line contains the components of x_n orderly, the last number is y_n. Please initialize your algorithm with w = 0 and take sign(0) as 1.

16. (*) Please first follow page 4 of lecture 2, and add x₀ = 1 to every x_n. Implement a version of PLA that randomly picks an example (x_n,y_n) in every iteration, and updates w_t if and only if w_t is incorrect on the example. Note that the random picking can be simply implemented with replacementthat is, the same example can be picked multiple times, even consecutively. Stop updating and return w_t as w_PLA if w_t is correct consecutively after checking 5N randomly-picked examples.

Hint: (1) The update procedure described above is equivalent to the procedure of gathering all the incorrect examples first and then randomly picking an example among the incorrect ones. But the description above is usually much easier to implement. (2) The stopping criterion above is a randomized, more efficient implementation of checking whether w_t makes no mistakes on the data set.

Repeat your experiment for 1000 times, each with a different random seed. What is the median number of updates before the algorithm returns w_PLA? Choose the closest value.

• 8
• 11
• 14
• 17
• 20

17. (*) Among all the w₀ (the zero-th component of w_PLA) obtained from the 1000 experiments above, what is the median? Choose the closest value.
    • -10
    • -5 [c] 0
    • 5
    • 10
18. (*) Set x₀ = 10 to every x_n instead of x₀ = 1, and repeat the 1000 experiments above. What is the median number of updates before the algorithm returns w_PLA? Choose the closest value.
    • 8
    • 11
    • 14
    • 17
    • 20
19. (*) Set x₀ = 0 to every x_n instead of x₀ = 1. This equivalently means not adding any x₀, and you will get a separating hyperplane that passes the origin. Repeat the 1000 experiments above. What is the median number of updates before the algorithm returns w_PLA?
    • 8
    • 11
    • 14
    • 17
    • 20
20. (*) Now, in addition to setting x₀ = 0 to every x_n, scale down each x_n by 4. Repeat the 1000 experiments above. What is the median number of updates before the algorithm returns w_PLA? Choose the closest value.
    • 8
    • 11
    • 14
    • 17
    • 20