Bagaimana cara mendapatkan solusi regresi ridge?

40

Saya mengalami beberapa masalah dengan derivasi solusi untuk regresi ridge.

Saya tahu solusi regresi tanpa ketentuan regularisasi:

β=(XTX)1XTy.

Tetapi setelah menambahkan istilah L2 ke fungsi biaya, mengapa solusinya menjadiλβ22

β=(XTX+λI)1XTy.
pengguna34790
sumber

Jawaban:

23

Cukuplah untuk memodifikasi fungsi kerugian dengan menambahkan penalti. Dalam istilah matriks, fungsi kehilangan kuadratik awal menjadi

(YXβ)T(YXβ)+λβTβ.
Turun sehubungan dengan β mengarah ke persamaan normal
XTY=(XTX+λI)β
yang mengarah ke estimator Ridge.
johnny
sumber
1
Kenapa turunan dari λβTβ sama dengan λIβ
user34790
4
@ user34790 Bukan. Itu sama dengan 2λβ . Tetapi 2 dibatalkan dengan 2s yang sama pada persyaratan lainnya. Tentu saja, faktor I seperti faktor 1 dalam aljabar "biasa", Anda dapat melipatgandakannya di mana pun Anda suka tanpa mengubah apa pun.
Bill
4
@ bill: di sini Anda memerlukan untuk mendapatkan matriks dari dimensi yang benar sehingga penambahan bekerja dengan : hanyalah sebuah skalarIXTXλ
Henry
47

Mari kita membangun apa yang kita ketahui, yaitu setiap matriks model adalah , respons -vektor adalah , dan parameter -vector adalah , fungsi objektifn×pXnypβ

f(β)=(yXβ)(yXβ)

(yang merupakan jumlah kuadrat residu) diminimalkan ketika memecahkan persamaan Normalβ

(XX)β=Xy.

Regresi Ridge menambahkan istilah lain ke fungsi objektif (biasanya setelah menstandarisasi semua variabel untuk menempatkan mereka pada pijakan yang sama), meminta untuk meminimalkan

(yXβ)(yXβ)+λββ

untuk beberapa konstanta non-negatif . Ini adalah jumlah kuadrat dari residu ditambah kelipatan dari kuadrat dari koefisien itu sendiri (membuatnya jelas bahwa ia memiliki minimum global). Karena , ia memiliki akar kuadrat positif .λλ0ν2=λ

Pertimbangkan matriks ditambah dengan baris yang sesuai dengan kali matriks identitas :Xνp×pI

X=(XνI)

Ketika vektor diperluas sama dengan nol di akhir , produk matriks dalam fungsi objektif menambahkan syarat tambahan dari formulir ke tujuan semula. Karena ituypyp(0νβi)2=λβi2

(yXβ)(yXβ)=(yXβ)(yXβ)+λββ.

Dari bentuk ekspresi tangan kiri, langsung bahwa persamaan Normal adalah

(XX)β=Xy.

Karena kita menyatukan nol ke ujung , sisi kanan sama dengan . Di sisi kiri ditambahkan ke . Oleh karena itu persamaan Normal yang baru disederhanakan menjadiyXyν2I=λIXX

(XX+λI)β=Xy.

Selain ekonomis secara konseptual - tidak ada manipulasi baru yang diperlukan untuk memperoleh hasil ini - juga ekonomis secara komputasi: perangkat lunak Anda untuk melakukan kuadrat terkecil biasa juga akan melakukan regresi ridge tanpa perubahan apa pun. (Namun demikian dapat membantu dalam masalah besar untuk menggunakan perangkat lunak yang dirancang untuk tujuan ini, karena itu akan mengeksploitasi struktur khusus untuk memperoleh hasil secara efisien untuk interval spasi yang padat , memungkinkan Anda untuk mengeksplorasi bagaimana jawabannya bervariasi dengan .)Xλλ

Keindahan lain dari cara memandang hal - hal ini adalah bagaimana hal itu dapat membantu kita memahami regresi ridge. Ketika kita ingin benar-benar memahami regresi, hampir selalu membantu untuk memikirkannya secara geometris: kolom membentuk vektor dalam ruang vektor nyata dari dimensi . Dengan menyatukan ke , dengan demikian memperpanjangnya dari vektor ke vektor, kami menyematkan ke dalam ruang yang lebih besar dengan memasukkan "imajiner", arah yang saling ortogonal. Kolom pertamaXpnνIXnn+pRnRn+ppXdiberi komponen imajiner kecil dengan ukuran , sehingga memanjangnya dan memindahkannya keluar dari ruang yang dihasilkan oleh kolom asli . Kolom kedua, ketiga, ..., sama-sama diperpanjang dan dipindahkan dari ruang asli dengan jumlah yang sama - tetapi semuanya dalam arah baru yang berbeda. Akibatnya, setiap collinearity yang ada di kolom asli akan segera diselesaikan. Selain itu, semakin besar , semakin banyak vektor baru ini mendekati individuνppthννparah imajiner: mereka menjadi lebih dan lebih normal. Akibatnya, solusi dari persamaan Normal akan segera menjadi mungkin dan itu akan cepat menjadi stabil secara numerik karena meningkat dari .ν0

Deskripsi proses ini menyarankan beberapa pendekatan baru dan kreatif untuk mengatasi masalah yang dirancang untuk ditangani oleh Ridge Regression. Misalnya, dengan menggunakan segala cara apa pun (seperti dekomposisi varian yang dijelaskan oleh Belsley, Kuh, dan Welsch dalam buku 1980 mereka tentang Regresi Diagnostik , Bab 3), Anda mungkin dapat mengidentifikasi subkelompok kolom hampir collinear , di mana setiap subkelompok hampir ortogonal dengan yang lain. Anda hanya perlu berdampingan dengan banyak baris ke (dan nol ke ) karena ada elemen dalam grup terbesar, yang mendedikasikan satu dimensi "imajiner" baru untuk memindahkan setiap elemen grup dari saudara-saudaranya: Anda tidak perlu imajiner dimensi untuk melakukan ini.XXyp

whuber
sumber
2
Penulis buku terakhir adalah Welsch, bukan Welsh.
Mark L. Stone
1
Wah, ini benar-benar membuat saya bingung. Apakah ada diskusi tentang apa yang terjadi ketika ini digeneralisasi di luar model linier, yaitu ke GLM? Hukuman seharusnya tidak sejajar dengan regresi ridge ... tetapi interpretasi ini menyiratkan bahwa itu masih akan menjadi penduga yang berguna!
Cliff AB
2
@ Tebing Itu saran yang sangat menarik. Namun, karena estimasi GLM bergantung pada cara yang lebih rumit pada dan estimator mereka biasanya tidak dapat difaktorkan dalam bentuk sebagaimana untuk OLS (di mana dan ), mungkin sulit untuk membangun hubungan yang bermanfaat antara memaksakan fungsi penalti dan memodifikasi kolom . Secara khusus, tidak jelas bagaimana nilai-nilai dalam perlu ditambah untuk membuat pekerjaan ini. X
β^=g(X)h(y)
g(X)=(XX)1Xh(y)=yXy
Whuber
1
Ya, perlu beberapa pemikiran untuk mencoba menentukan apakah penalti itu, tetapi saya tidak begitu khawatir tentang itu. Ide apa penggunaan umumnya tidak mudah baik ... kecuali mungkin dalam kasus regresi logistik, di mana kita bisa menambahkan dua 's; salah satu dari 0 dan satu dari 1. Augmentasi ini kemudian akan menjadi versi yang lebih umum dari "+2 penaksir binomial" (ada nama yang lebih tepat untuk penaksir ini yang saya kosongkan, yang pada dasarnya ketika Anda memperkirakan dari distribusi binomial menggunakan mean posterior sebagai estimasi dengan seragam sebelum ). y ypp
Cliff AB
@ Mark Terima kasih atas koreksinya. Anda bisa tahu saya pergi dari memori ... :-).
Whuber
20

Derivasi termasuk kalkulus matriks, yang bisa sangat membosankan. Kami ingin mengatasi masalah berikut:

minβ(YβTX)T(YβTX)+λβTβ

Sekarang perhatikan bahwa dan Bersama-sama kita mencapai kondisi urutan pertama Mengisolasi menghasilkan solusi:

(YβTX)T(YβTX)β=2XT(YβTX)
λβTββ=2λβ.
XTY=XTXβ+λβ.
β
β=(XTX+λI)1XTY.
pthesling
sumber
9

Saya baru-baru ini menemukan pertanyaan yang sama dalam konteks P-Splines dan karena konsepnya sama, saya ingin memberikan jawaban yang lebih terperinci tentang derivasi penaksir bubungan.

Kita mulai dengan fungsi kriteria hukuman yang berbeda dari fungsi kriteria OLS klasik dengan istilah hukumannya di ringkasan terakhir:

CriterionRidge=i=1n(yixiTβ)2+λj=1pβj2

dimana

  • p= jumlah kovariabel yang digunakan dalam model
  • xiTβ= prediktor linier standar Anda
  • summand pertama mewakili MSE (kuadrat divergensi dari prediksi dari nilai aktual) yang ingin kita perkecil seperti biasa
  • sumand kedua mewakili hukuman yang kita terapkan pada koefisien. Di sini kita berada dalam konteks Ridge yang menyiratkan Ukuran Jarak Euclidian dan karenanya derajat 2 dalam istilah hukuman. Dalam kasus Penetrasi Lasso kita akan menerapkan derajat 1 dan menghasilkan penaksir yang sama sekali berbeda.

Kita dapat menulis ulang kriteria ini dalam notasi matriks dan selanjutnya memecahnya:

CriterionRidge=(yXβ)T(yXβ)+λβTβ

=yTyβTXTyyTXβ+βTxTXβ+λβTβ

=yTyβTXTyβTXTy+βTXTXβ+βTλIβ dengan menjadi matriks identitasI

=yTy2βTXTy+βT(XTX+λI)β

Sekarang kami mencari yang meminimalkan kriteria kami. Di antara yang lainnya, kami menggunakan aturan diferensiasi matriks yang dapat kita gunakan berlaku di sini sebagai : βxTAxx=(A+AT)x=A symmetric2Ax(XTX+λI)Rn×n

CriterionRidgeβ=2XTy+2(XTX+λI)β=!0

(XTX+λI)β=XTy

et voilàβ^=(XTX+λI)1XTy

Jann Goschenhofer
sumber
@Jahn, bisa tolong jelaskan bagaimana menjadi ? Saya pikir Anda baru saja menerapkan transpos di atasnya, kan. Tapi, Anda tidak bisa hanya menerapkan transpos pada satu istilah tanpa menerapkannya pada semua persamaan. Apa yang kulewatkan di sini?
yTXβ
βTXTy
theateist
1
@theateist Skalar yang dialihkan adalah skalar yang sama.
Konstantin
2

Ada beberapa hal penting yang hilang dalam jawaban yang diberikan.

  1. Solusi untuk berasal dari kondisi urutan pertama yang diperlukan: yang menghasilkan . Tetapi apakah ini cukup? Artinya, solusinya adalah minimum global hanya jika benar-benar cembung. Ini bisa terbukti benar.βfridge(β,λ)β=0β=(XTX+λI)1XTYfridge(β,λ)

  2. Cara lain untuk melihat masalahnya adalah dengan melihat kesetaraan antara dan dibatasi menjadi . OLS adalah singkatan dari Ordinary Least Squares. Dari perspektif ini hanyalah fungsi Lagrangian yang digunakan untuk menemukan minimum global fungsi objektif cembung dibatasi dengan fungsi cembung .fridge(β,λ)fOLS(β)=(YβTX)T(YβTX)||β||22tfridge(β,λ)fOLS(β)||β||22

Penjelasan yang baik tentang poin-poin ini dan derivasi dapat ditemukan dalam catatan kuliah yang bagus ini: http://math.bu.edu/people/cgineste/classes/ma575/p/w14_1.pdfβ

Davor Josipovic
sumber