[SOLVED] CSE417: Introduction to Machine Learning Problem Set 1

Problems

1. LFD Problem 1.3 2. Out of textbook 3. LFD Problem 1.7 4. LFD Problem 1.8

CSE417: Introduction to Machine Learning

Problem Set 1

Q1: LFD Problem 1.3

(a)

Since w^∗ is the optimal set of weights, for all 1 ≤ n ≤ N, w^∗T x_n must have same sign as y_n since a linear separation is achieved.

Therefore, for all 1 ≤ n ≤ N, y_n(w^∗T x_n) > 0, which suggests min_1≤n≤Ny_n(w^∗T x_n) > 0, or ρ > 0

(b)

Given the update rule, w(t + 1) = w(t) + y(t)x(t), transpose both sides and multiply by w^∗:

w(t + 1)^T = w(t)^T + (y(t)x(t))^T

w(t + 1)^T w^∗ = w(t)^T w^∗ + (y(t)x(t))^T w^∗

w(t + 1)^T w^∗ = w(t)^T w^∗ + y(t)(x(t)^T w^∗) → given y(t) is 1 * 1

w(t + 1)^T w^∗ = w(t)^T w^∗ + y(t)(w^∗T x(t)) → given w^∗T x(t) is 1*1 so its symmetric

And by the definition of ρ = min_1≤n≤Ny_n(w^∗T x_n), for all 1 ≤ t ≤ N, we have rho ≤ y(t)(w^∗T x(t).

Then we could conclude that:

w(t + 1)^T w^∗ ≥ w(t)^T w^∗ + ρ

Base Case: t = 0, since we assumed w(0) = 0, we have:

w^T (0)w^∗ = 0 ≥ 0ρ = 0

Induction: for t = n, given that the inequality is valid:

w^T (n)w^∗ ≥ nρ

and incorporate the inequality we deduced above:

w^T (n + 1)w^∗ ≥ w(n)^T w^∗ + ρ w^T (n + 1)w^∗ ≥ nρ + ρ w^T (n + 1)w^∗ ≥ (n + 1)ρ

so the inequality must also be valid for t = n + 1. Thus proved.

(c)

Given the update rule, w(t+1) = w(t)+y(t)x(t), transpose both sides and multiply by the original equation:

w(t + 1) ∗ w(t + 1)^T = (w(t) + (y(t)x(t)))(w(t)^T + (y(t)x(t))^T )

||w(t + 1)||² = ||w(t)||² + 2y(t)x(t)w(t)^T + y(t)²||x(t)||²

Since for any y(t), we have y(t)² = 1, and 2y(t)x(t)w(t)^T < 0 given y(t) represents a misclassified point, we have:

||w(t + 1)||² ≤ ||w(t)||² + y(t)²||x(t)||² ||w(t + 1)||² ≤ ||w(t)||² + ||x(t)||²

(d)

Proof:

Base case: for t = 0, ||w(t)||² = 0 ≤ 0 ∗ R² = 0

Induction:

Given that ||w(t)||² ≤ tR², we have:

||w(t + 1)||² ≤ ||w(t)||² + ||x(t − 1)||²

||w(t + 1)||² ≤ ||w(t)||² + R² ||w(t + 1)||² ≤ ||w(t)||² + R²

||w(t + 1)||² ≤ ||w(t)||² + R²

||w(t + 1)||² ≤ tR² + R²

||w(t + 1)||² ≤ (t + 1)R²

2

(e)

Proof: Using the conclusion in part (b):

given the conclusion in (d)

Since  where θ represents the angle between w^T (t) and w^∗, we must have

1, then we could rewrite the inequality to be:

√

Given That      t ≥ 0

2

Q2

The first plot is the number of operation for each iteration and the second plot is a histogram of log difference. Plot attached below:

Q3: LFD Problem 1.7

(a)

For µ = 0.05

P[0|10,0.05] = 0.95¹⁰ = 0.5987

1 Coin: P = 0.5987

10 Coins: P = 1 − (1 − 0.95¹⁰)¹⁰ = 0.9998

1000 Coins: P = 1 − (1 − 0.95¹⁰)¹⁰⁰⁰ = 1

1000000 Coins: P = 1 − (1 − 0.95¹⁰)^1000000 = 1

For µ = 0.8

P[0,|10,0.8] = 0.2¹⁰ = 1.024e − 7

1 Coin: P = 1.024e-7

10 Coins: P = 1 − (1 − 0.2¹⁰)¹⁰ = 0.000001024

1000 Coins: P = 1 − (1 − 0.2¹⁰)¹⁰⁰⁰ = .0001024

1000000 Coins: P = 1 − (1 − 0.2¹⁰)^1000000 = 0.09733

(b)

The result should be equivalent to P = 1 ) for each , which produces a step function satisfy the following condition:

Using Hoeffding bound for 2 coins,

Plot attached below:

Q4: LFD Problem 1.8

(a)

By definition, we have that Then for each α > 0, we have:

Proved.

(b)

By definition, E[(u − µ)²] = σ², then using the conclusion in part (a), we have:

(c)

By definition, for N iid random variables (u₁,u₂,…u_n) each with E(u_i) = µ and variance V ar(u_i) = σ² for 0 < i ≤ n

Letwe have that:

And that:

Then similar to that in part (b):

proved.