Saya telah membaca buku-buku paling populer dalam pembelajaran statistik
1- Unsur-unsur pembelajaran statistik.
2- Pengantar pembelajaran statistik .
Keduanya menyebutkan bahwa regresi ridge memiliki dua formula yang setara. Apakah ada bukti matematis yang dapat dimengerti dari hasil ini?
Saya juga melewati Cross Validated , tetapi saya tidak dapat menemukan bukti yang pasti di sana.
Lebih lanjut, akankah LASSO menikmati jenis bukti yang sama?
Jawaban:
Regresi Ridge klasik ( Regulasi Tikhonov ) diberikan oleh:
Klaim di atas adalah bahwa masalah berikut ini setara:
Mari kita mendefinisikan x sebagai solusi optimal dari masalah pertama dan ~ x sebagai solusi optimal dari masalah kedua.x^ x~
Klaim berarti kesetaraan yang∀t,∃λ≥0:x^=x~ . t danλ≥0 sehingga solusi dari masalahnya adalah sama.
Yaitu Anda selalu dapat memiliki sepasang
Bagaimana kita bisa menemukan pasangan?
Nah, dengan menyelesaikan masalah dan melihat sifat-sifat solusinya.
Kedua masalah tersebut cembung dan halus sehingga harus membuat semuanya lebih sederhana.
Solusi untuk masalah pertama diberikan pada titik gradien hilang yang berarti:
The KKT Kondisi negara-negara Masalah kedua:
dan
Persamaan terakhir menunjukkan bahwaμ=0 atau ∥x~∥22=t .
Perhatikan bahwa 2 persamaan dasar adalah setara.x^=x~ danμ=λ kedua persamaan terus.
yaitu
Jadi itu berarti bahwa dalam kasus∥y∥22≤t seseorang harus menetapkan μ=0 yang berarti bahwa untuk t cukup besar agar keduanya setara, harus ditetapkan λ=0 .
Pada kasus lain, seseorang harus menemukanμ mana:
Ini pada dasarnya ketika∥x~∥22=t
Setelah Anda menemukan bahwaμ solusi akan bertabrakan.
Mengenai kasusL1 (LASSO), yah, ia bekerja dengan ide yang sama.
Satu-satunya perbedaan adalah kita tidak memiliki solusi yang tertutup sehingga memperoleh koneksi lebih sulit.
Lihat jawaban saya di StackExchange Cross Validated Q291962 dan StackExchange Signal Processing Q21730 - Signifikansiλ dalam Basis Pursuit .
Berkomentarx mencoba sedekat mungkin dengan y . x=y akan menghapus istilah pertama (The L2 ) dan dalam kasus kedua itu akan membuat fungsi objektif menghilang. L2 dari x . Sebagai λ semakin tinggi keseimbangan berarti Anda harus membuat x lebih kecil. x lebih dekat dan lebih dekat ke y sampai Anda menabrak dinding yang merupakan kendala pada Norm (By t ) -nya . t ) dan cukup tergantung pada norma y maka saya tidak memiliki makna, sama seperti λ relevan hanya nilainya dikalikan dengan norma y mulai bermakna.
Apa yang sebenarnya terjadi?
Dalam kedua masalah,
Dalam kasus pertama,
Perbedaannya adalah bahwa dalam kasus pertama kita harus menyeimbangkan Norma
Dalam kasus kedua ada dinding, Anda membawa
Jika temboknya cukup jauh (Nilai
Koneksi yang tepat adalah oleh Lagrangian yang disebutkan di atas.
Sumber daya
Saya menemukan makalah ini hari ini (03/04/2019):
sumber
Pendekatan yang kurang tepat secara matematis, tetapi mungkin lebih intuitif, untuk memahami apa yang sedang terjadi adalah memulai dengan versi kendala (persamaan 3.42 dalam pertanyaan) dan menyelesaikannya menggunakan metode "Pengali Lagrange" ( https: //en.wikipedia .org / wiki / Lagrange_multiplier atau teks kalkulus multivarian favorit Anda). Ingatlah bahwa dalam kalkulus adalah vektor variabel, tetapi dalam kasus kami xx x adalah konstan dan adalah vektor variabel. Setelah Anda menerapkan teknik pengali Lagrange Anda berakhir dengan persamaan pertama (3,41) (setelah membuang ekstraβ yang konstan relatif terhadap minimisasi dan dapat diabaikan).−λt
Ini juga menunjukkan bahwa ini berfungsi untuk laso dan kendala lainnya.
sumber
Mungkin perlu membaca tentang dualitas Lagrangian dan hubungan yang lebih luas (kadang-kadang setara) antara:
Pengenalan cepat ke dualitas yang lemah dan dualitas yang kuat
Asumsikan kita memiliki beberapa fungsi dari dua variabel. Untuk setiap x dan y , kita memiliki:f(x,y) x^ y^
Sejak itu berlaku untuk setiap x dan y juga menyatakan bahwa:x^ y^
Ini dikenal sebagai dualitas yang lemah . Dalam keadaan tertentu, Anda juga memiliki dualitas yang kuat (juga dikenal sebagai properti saddle point ):
Ketika dualitas kuat bertahan, menyelesaikan masalah ganda juga memecahkan masalah primal. Mereka dalam arti masalah yang sama!
Lagrangian untuk Regresi Ridge terbatas
The min-max interpretation of the Lagrangian
The Ridge regression problem subject to hard constraints is:
You pickb to minimize the objective, cognizant that after b is picked, your opponent will set λ to infinity if you chose b such that ∑pj=1b2j>t .
If strong duality holds (which it does here because Slater's condition is satisfied fort>0 ), you then achieve the same result by reversing the order:
Here, your opponent choosesλ first! You then choose b to minimize the objective, already knowing their choice of λ . The minbL(b,λ) part (taken λ as given) is equivalent to the 2nd form of your Ridge Regression problem.
As you can see, this isn't a result particular to Ridge regression. It is a broader concept.
References
(I started this post following an exposition I read from Rockafellar.)
Rockafellar, R.T., Convex Analysis
You might also examine lectures 7 and lecture 8 from Prof. Stephen Boyd's course on convex optimization.
sumber
They are not equivalent.
For a constrained minimization problem
we solve by minimize overb the corresponding Lagrangean
Here,t is a bound given exogenously, λ≥0 is a Karush-Kuhn-Tucker non-negative multiplier, and both the beta vector and λ are to be determined optimally through the minimization procedure given t .
Comparing(2) and eq (3.41) in the OP's post, it appears that the Ridge estimator can be obtained as the solution to
Since in(3) the function to be minimized appears to be the Lagrangean of the constrained minimization problem plus a term that does not involve b , it would appear that indeed the two approaches are equivalent...
But this is not correct because in the Ridge regression we minimize overb given λ>0 . But, in the lens of the constrained minimization problem, assuming λ>0 imposes the condition that the constraint is binding, i.e that
The general constrained minimization problem allows forλ=0 also, and essentially it is a formulation that includes as special cases the basic least-squares estimator (λ∗=0 ) and the Ridge estimator (λ∗>0 ).
So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.
sumber