Saya menerapkan Ridge Regression dalam modul Python / C, dan saya telah menemukan masalah "kecil" ini. Idenya adalah bahwa saya ingin sampel derajat efektif kebebasan kurang lebih sama spasi (seperti plot pada halaman 65 pada "Elemen statistik Learning" ), yaitu, sampel:
mana adalah nilai eigen dari matriks, darihingga. Cara mudah untuk mengatur batas pertama adalah untuk membiarkan(dengan asumsi ), di mana adalah konstanta kecil dan mewakili kira-kira tingkat kebebasan minimum yang ingin Anda sampel (misalnya ). Batas kedua tentu saja .
Seperti judulnya, maka, saya harus sampel dari ke dalam beberapa skala sehingga adalah sampel (kurang-lebih), mengatakan, di interval dari ke ... apakah ada yang mudah cara untuk melakukan ini? Saya pikir menyelesaikan persamaan untuk setiap menggunakan metode Newton-Raphson, tetapi ini akan menambahkan iterasi yang terlalu banyak, khususnya ketika besar. Ada saran?
ridge-regression
Néstor
sumber
sumber
Jawaban:
Ini jawaban yang panjang . Jadi, mari berikan versi cerita pendeknya di sini.
R
kode mati otak tidak ada upaya optimasi dapat menghitung kisi ukuran 100 dengan dalam beberapa detik. Kode yangditulis dengan hati-hatiakan mengurangi ini setidaknya 2-3 urutan besarnya.C
Ada dua skema yang diberikan di bawah ini untuk menjamin konvergensi monoton. Satu menggunakan batas yang ditunjukkan di bawah ini, yang tampaknya membantu menyelamatkan satu atau dua langkah Newton pada kesempatan.
Contoh : dan kotak seragam untuk derajat kebebasan ukuran 100. Nilai-nilai eigennya didistribusikan Pareto, karenanya sangat condong. Di bawah ini adalah tabel jumlah langkah Newton untuk menemukan setiap root.p=100000
Tidak akan ada solusi bentuk tertutup untuk ini , secara umum, tetapi ada adalah banyak struktur sekarang yang dapat digunakan untuk menghasilkan solusi yang sangat efektif dan aman menggunakan metode akar-menemukan standar.
Sebelum menggali terlalu dalam ke hal-hal, mari kita mengumpulkan beberapa sifat dan konsekuensi dari fungsi
Properti 0 : adalah fungsi rasional λ . (Hal ini terlihat dari definisi.) Konsekuensi 0 : Tidak ada solusi aljabar umum akan ada untuk menemukan akar d f ( λ ) - y = 0 . Ini karena ada masalah penemuan akar polinomial setara dengan derajat p dan jadi jika p tidak terlalu kecil (yaitu kurang dari lima), tidak ada solusi umum yang akan ada. Jadi, kita membutuhkan metode numerik.df λ
df(λ)−y=0 p p
Properti 1 : Fungsi yaitu cembung dan menurun pada λ ≥ 0 . (Ambil turunannya.) Konsekuensi 1 (a) : Algoritma pencarian akar Newton akan berperilaku sangat baik dalam situasi ini. Biarkan y menjadi derajat kebebasan yang diinginkan dan λ 0 akar yang sesuai, yaitu, y = d f ( λ 0 ) . Secara khusus, jika kita memulai dengan setiap nilai awal λ 1 < λ 0 (jadi, d f ( λ 1df λ≥0
y λ0 y=df(λ0) λ1<λ0 ), maka urutan iterasi langkah-Newton λ 1 , λ 2 , ... akan konvergensecara monotonke solusi unik λ 0 .
Konsekuensi 1 (b): Selanjutnya, jika kita memulai dengan λ 1 > λ 0 , makalangkahpertamaakan menghasilkan λ 2 ≤ λ 0df(λ1)>y λ1,λ2,… λ0
λ1>λ0 λ2≤λ0 , dari mana itu akan meningkat secara monoton ke solusi dengan konsekuensi sebelumnya (lihat peringatan di bawah). Secara intuitif, fakta terakhir ini mengikuti karena jika kita mulai di sebelah kanan akar, derivatif adalah "terlalu" dangkal karena busung dari dan langkah Newton pertama akan membawa kita ke suatu tempat ke kiri dari akar. NB Sejak d f adalah tidak di cembung umum untuk negatif λ , ini memberikan alasan yang kuat untuk memilih mulai ke kiri dari akar yang diinginkan. Jika tidak, kita perlu periksa bahwa langkah Newton tidak menghasilkan nilai negatif untuk perkiraan akar, yang dapat menempatkan kita di suatu tempat di bagian nonconvex dari d f .
df df λ df y1 y2<y1 λ1 df(λ1)=y1
Konsekuensi 1 (c) : Setelah kami telah menemukan akar untuk beberapa dan kemudian mencari akar dari beberapa y 2 < y 1 , menggunakan λ 1 sehingga d f ( λ 1 ) = y 1 sebagai dugaan awal kami jaminan kami mulai di sebelah kiri dari root kedua. Jadi, konvergensi kami dijamin monoton dari sana.
Properti 2 : Ada batasan yang wajar untuk memberikan titik awal yang "aman". Menggunakan argumen konveksitas dan ketidaksetaraan Jensen, kita memiliki batasan berikut
This assumes thatdi>0 for all i . If this is not the case, then the same bound holds by considering only the positive di and replacing p by the number of positive di . NB: Since df(0)=p assuming all di>0 , then y∈(0,p] , whence the bounds are always nontrivial (e.g., the lower bound is always nonnegative).
Here is a plot of a "typical" example ofdf(λ) with p=400 . We've superimposed a grid of size 10 for the degrees of freedom. These are the horizontal lines in the plot. The vertical green lines correspond to the lower bound in (⋆) .
An algorithm and some example R code
A very efficient algorithm given a grid of desired degrees of freedomy1,…yn in (0,p] is to sort them in decreasing order and then sequentially find the root of each, using the previous root as the starting point for the following one. We can refine this further by checking if each root is greater than the lower bound for the next root, and, if not, we can start the next iteration at the lower bound instead.
Here is some example code in
R
, with no attempts made to optimize it. As seen below, it is still quite fast even thoughR
is—to put it politely—horrifingly, awfully, terribly slow at loops.Below is the final full algorithm which takes a grid of points, and a vector of thedi (not d2i !).
Sample function call
sumber
In addition, a couple of methods exist that will calculate the complete regularization path efficiently:
The above are all R packages, as you are using Python, scikit-learn contains implementations for ridge, lasso and elastic net.
sumber
ols
function in the Rrms
package can use numerical optimization to find the optimum penalty using effective AIC. But you have to provide the maximum penalty which is not always easy.A possible alternative according to the source below seems to be:
The closed form solution:df(λ)=tr(X(X⊤X+λIp)−1X⊤)
Should you be using the normal equation as the solver or computing the variance-covariance estimate, you should already have computed(X⊤X+λIp)−1 . This approach works best if you are estimating the coefficients at the various λ .
Source: https://onlinecourses.science.psu.edu/stat857/node/155
sumber