10-701: Introduction to Machine Learning Lecture 8 – Regularization

10-701: Introduction to Machine Learning Lecture 8 – Regularization Henry Chai 2/12/24Front Matter Announcements: HW2 released 2/7, due 2/19 (previously 2/16) at 11:59 PM HW3 released 2/19 (previously 2/16), due 2/28 (previously 2/26) at 11:59 PM Lecture schedule has been updated, see the course website for full details Lecture on 2/21 (Wednesday) and Recitation on 2/23 (Friday) have been [...] = 𝜔/ = 𝜔0 = 𝜔1 = 𝜔!, = 0 Henry Chai - 2/12/24 1 𝑁 Χ𝝎 − 𝒚 5 Χ𝝎 − 𝒚 27Hard Constraints ℋ!, = 10()-order polynomials 𝜙!,!, 𝑥 = 𝑥, 𝑥#, 𝑥%, 𝑥&, 𝑥-, 𝑥., 𝑥/, 𝑥0, 𝑥1, 𝑥!, Given Χ = 1 𝜙!,!, 𝑥 ! 1 𝜙!,!, 𝑥 # ⋮ ⋮ 1 𝜙!,!, 𝑥 4 and 𝒚 = 𝑦 ! 𝑦 # ⋮ 𝑦 4 find 𝝎 = 𝜔,, 𝜔!, 𝜔#, 𝜔%, 𝜔&, 𝜔-, 𝜔., 𝜔/, 𝜔0, 𝜔1, 𝜔!, that minimizes Subject to 𝜔% = 𝜔& = 𝜔- = 𝜔. [...] = 𝜔/ = 𝜔0 = 𝜔1 = 𝜔!, = 0 Henry Chai - 2/12/24 28 1 𝑁 ; 63! 4 ; 23, !, 𝑥2 6 𝜔2 − 𝑦 6 # ℋ!, = 10()-order polynomials 𝜙!,!, 𝑥 = 𝑥, 𝑥#, 𝑥%, 𝑥&, 𝑥-, 𝑥., 𝑥/, 𝑥0, 𝑥1, 𝑥!, Given Χ = 1 𝜙!,!, 𝑥 ! 1 𝜙!,!, 𝑥 # ⋮ ⋮ 1 𝜙!,!, 𝑥 4 and 𝒚 = 𝑦 ! 𝑦 # ⋮ 𝑦 4 find 𝝎 = 𝜔,, 𝜔!, 𝜔#, 𝜔%, 𝜔&, 𝜔-, 𝜔., 𝜔/, 𝜔0, 𝜔1, 𝜔!, that minimizes Subject to nothing! Hard Constraints Henry Chai - 2/12/24 29 1 𝑁 ; 63! [...] Given Χ = 1 𝜙! 𝒙 ! ⋯ 𝜙7 𝒙 ! ⋮ ⋮ ⋱ ⋮ 1 𝜙! 𝒙 4 ⋯ 𝜙7 𝒙 4 and 𝒚 = 𝑦 ! 𝑦 # ⋮ 𝑦 4 , find 𝝎 that minimizes Subject to: Soft Constraints 𝝎 # # = 𝝎5𝝎 = ; 23, " 𝜔2 # ≤ 𝐶 Henry Chai - 2/12/24 31 1 𝑁 Χ𝝎 − 𝒚 5 Χ𝝎 − 𝒚Henry Chai - 2/12/24 𝝎5𝝎 = 𝐶 0,0 subject to 𝝎5𝝎 ≤ 𝐶 minimize ℓ𝒟 𝝎 = Χ𝝎 − 𝒚 5 Χ𝝎 − 𝒚 U𝝎 ℓ𝒟 𝝎 Soft Constraints 320,0 Henry Chai - 2/12/24 Soft Constraints subject to 𝝎5𝝎 ≤ 𝐶 minimize ℓ𝒟 𝝎 = Χ𝝎 − [...] 𝝎 = ℓ𝒟 𝝎 + 𝜆=𝝎5𝝎 ⇕ Henry Chai - 2/12/24 Soft Constraints: Solving for #𝝎#$% subject to 𝝎5𝝎 ≤ 𝐶 minimize ℓ𝒟 𝝎 = Χ𝝎 − 𝒚 5 Χ𝝎 − 𝒚 35∇𝝎ℓ𝒟 :>? [...] 𝝎 = 2 𝛸5𝛸𝝎 − 𝛸5𝒚 + 𝜆=𝝎 2 𝛸5𝛸U𝝎9:; − 𝛸5𝒚 + 𝜆= U𝝎9:; = 0 𝛸5𝛸 + 𝜆=𝐼"@! U𝝎9:; = 𝛸5𝒚 U𝝎9:; = 𝛸5𝛸 + 𝜆=𝐼"@! A!𝛸5𝒚 Henry Chai - 2/12/24 Ridge Regression Adding this positive (𝜆= ≥ 0) diagonal matrix can help if 𝛸5𝛸 is not invertible! minimize ℓ𝒟 :>? [...] 𝝎 = ℓ𝒟 𝝎 + 𝜆=𝝎5𝝎 360 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Target Function 10th-Order Hypothesis Noisy Samples Ridge Regression 10-dimensional target function with additive Gaussian noise ℋ!, = 10()-order polynomial Henry Chai - 2/12/24 370 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Target Function 10th-Order Hypothesis [...] 𝐾F 𝒙, 𝒙′ = Φ 𝒙 5Φ 𝒙G ∀ 𝒙, 𝒙G ∈ 𝒳 𝐾F 𝒙, 𝒙′ should be cheaper to compute than Φ 𝒙 Example: Φ# G 𝒙 = 𝑥!, … , 𝑥", 𝑥!#, 2𝑥!𝑥#, … , 2𝑥"A!𝑥", 𝑥" # Φ# G 𝒙 5Φ# G 𝒙G = ; H3! " 𝑥H𝑥H G + ; H3! " 𝑥H #𝑥H G# + ; H3! " ; IJH 2𝑥H𝑥H G𝑥I𝑥I G Φ# G ⃗𝑥 5Φ# G ⃗𝑥G = ; H3! " 𝑥H𝑥H G + ; H3! " 𝑥H𝑥H G # = 𝒙5𝒙G + 𝒙5𝒙G # 𝐾F! " 𝒙, 𝒙′ = 𝒙5𝒙G + 𝒙5𝒙G # Computing Φ# G 𝒙 5Φ# G 𝒙G requires 𝑂 𝐷# time whereas computing 𝐾F! " [...] 𝐾 𝒙, 𝒙′ = Φ 𝒙 5Φ 𝒙G ∀ 𝒙, 𝒙′ ⇕ the Gram matrix Κ = 𝐾 𝒙 ! , 𝒙 ! 𝐾 𝒙 ! , 𝒙 # ⋯ 𝐾 𝒙 ! , 𝒙 4 𝐾 𝒙 # , 𝒙 ! 𝐾 𝒙 # , 𝒙 # ⋯ 𝐾 𝒙 # , 𝒙 4 ⋮ ⋮ ⋱ ⋮ 𝐾 𝒙 4 , 𝒙 ! 𝐾 𝒙 4 , 𝒙 # ⋯ 𝐾 𝒙 4 , 𝒙 4 is symmetric and positive semi-definite ∀ sets 𝒙 ! , 𝒙 # , … , 𝒙 4 57 Henry Chai - 2/12/24Key Takeaways Henry Chai - 2/12/24 Polynomial/non-linear feature transformations allow for learning non-linear functions/decision bo