Apakah tingkat Kesalahan fungsi Cembung parameter lambda Regularisasi?

Dalam memilih parameter regularisasi lambda di Ridge atau Lasso, metode yang disarankan adalah mencoba nilai-nilai lambda yang berbeda, mengukur kesalahan dalam Set Validasi dan akhirnya memilih nilai lambda yang mengembalikan kesalahan terendah.

Ini tidak jelas bagi saya jika fungsi f (lambda) = error adalah Convex. Mungkinkah seperti ini? Yaitu dapat kurva ini memiliki lebih dari satu minimum lokal (yang akan menyiratkan bahwa menemukan minimum Kesalahan di beberapa wilayah lambda tidak menghalangi kemungkinan bahwa di beberapa daerah lain ada lambda mengembalikan Kesalahan yang lebih kecil)

Nasihat Anda akan dihargai.

cross-validation error regularization validation optimization rf7
sumber

Jawaban:

Pertanyaan awal bertanya apakah fungsi kesalahan harus cembung. Tidak. Analisis yang disajikan di bawah ini dimaksudkan untuk memberikan beberapa wawasan dan intuisi tentang ini dan pertanyaan yang dimodifikasi, yang menanyakan apakah fungsi kesalahan dapat memiliki beberapa minimum lokal.

Secara intuitif, tidak perlu ada hubungan matematis yang diperlukan antara data dan set pelatihan. Kita harus dapat menemukan data pelatihan yang model awalnya buruk, menjadi lebih baik dengan beberapa regularisasi, dan kemudian menjadi lebih buruk lagi. Kurva kesalahan tidak dapat cembung dalam kasus itu - setidaknya tidak jika kita membuat parameter regularisasi bervariasi dari hingga . $0$ $\infty$

Perhatikan bahwa cembung tidak sama dengan memiliki minimum yang unik! Namun, gagasan serupa menyarankan beberapa minimum lokal dimungkinkan: selama regularisasi, pertama model yang cocok mungkin akan lebih baik untuk beberapa data pelatihan sementara tidak berubah secara signifikan untuk data pelatihan lainnya, dan kemudian nanti akan menjadi lebih baik untuk data pelatihan lainnya, dll. Yang sesuai campuran dari data pelatihan tersebut harus menghasilkan beberapa minimum lokal. Agar analisisnya sederhana, saya tidak akan berusaha menunjukkannya.

Edit (untuk menanggapi pertanyaan yang diubah)

Saya sangat yakin dengan analisis yang disajikan di bawah ini dan intuisi di baliknya sehingga saya mulai mencari contoh dengan cara yang paling kasar: Saya menghasilkan set data acak kecil, menjalankan Lasso pada mereka, menghitung total kuadrat kesalahan untuk satu set pelatihan kecil, dan merencanakan kurva kesalahannya. Beberapa upaya menghasilkan satu dengan dua minimum, yang akan saya jelaskan. Vektor berada dalam formulir untuk fitur dan dan respons . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Data pelatihan

(1, 1, - 0.1), (2, 1, 0.8), (1, 2, 1.2), (2, 2, 0.9)

$(1,1,-0.1),\ (2,1,0.8),\ (1,2,1.2),\ (2,2,0.9)$

Uji data

(1, 1, 0.2), (1, 2, 0.4)

$(1,1,0.2),\ (1,2,0.4)$

Lasso dijalankan menggunakan glmnet::glmmetdi R, dengan semua argumen yang tersisa di default. Nilai pada sumbu x adalah kebalikan dari nilai-nilai yang dilaporkan oleh perangkat lunak tersebut (karena parameter parameter hukumannya dengan ). $\lambda$ $1/\lambda$

Kurva kesalahan dengan beberapa minimum lokal

Analisis

Mari kita pertimbangkan setiap metode pengaturan parameter pemasangan untuk data dan respons terkait yang memiliki sifat-sifat ini umum untuk Ridge Regression dan Lasso: $\beta=(\beta_1, \ldots, \beta_p)$ $x_i$ $y_i$

(Parameterisasi) Metode ini diparameterisasi oleh bilangan real , dengan model yang tidak diregulasi sesuai dengan . $\lambda \in [0, \infty)$ $\lambda=0$
(Kontinuitas) Estimasi parameter tergantung terus-menerus pada dan nilai prediksi untuk semua fitur bervariasi secara terus menerus dengan . $\hat\beta$ $\lambda$ $\hat\beta$
(Penyusutan) Sebagai , . $\lambda\to\infty$ $\hat\beta\to 0$
(Finiteness) Untuk vektor fitur , seperti , prediksi . $x$ $\hat\beta\to 0$ $\hat y(x) = f(x, \hat\beta) \to 0$
(Monoton error) Fungsi error membandingkan setiap nilai untuk nilai prediksi , , meningkat dengan perbedaansehingga, dengan beberapa penyalahgunaan notasi, kami dapat menyatakannya sebagai . $y$ $\hat y$ $\mathcal{L}(y, \hat y)$ $|\hat y - y|$ $\mathcal{L}(|\hat y - y|)$

(Nol dalam dapat digantikan oleh konstanta apa pun.) $(4)$

Misalkan datanya sedemikian sehingga estimasi parameter awal (tidak diregulasi) tidak nol. Mari kita membangun satu set data pelatihan yang terdiri dari satu pengamatan untuk yang . (Jika tidak mungkin menemukan seperti itu , maka model awal tidak akan terlalu menarik!) Set . $\hat\beta(0)$ $(x_0, y_0)$ $f(x_0, \hat\beta(0))\ne 0$ $x_0$ $y_0=f(x_0, \hat\beta(0))/2$

$e: \lambda \to \mathcal{L}(y_0, f(x_0, \hat\beta(\lambda))$

$e(0) = \mathcal{L}(y_0, f(x_0, \hat\beta(0)) = \mathcal{L}(y_0, 2y_0) = \mathcal{L}(|y_0|)$ $y_0$
$\lim_{\lambda\to\infty}e(\lambda) = \mathcal{L}(y_0, 0) = \mathcal{L}(|y_0|)$ $\lambda\to\infty$ $\hat\beta(\lambda)\to 0$ $\hat{y}(x_0)\to 0$

Dengan demikian, grafiknya terus-menerus menghubungkan dua titik akhir yang sama-sama tinggi (dan terbatas).

Secara kualitatif, ada tiga kemungkinan:

Prediksi untuk set pelatihan tidak pernah berubah. Ini tidak mungkin - hampir semua contoh yang Anda pilih tidak akan memiliki properti ini.
Beberapa prediksi menengah untuk lebih buruk daripada di awal atau dalam batas . Fungsi ini tidak boleh cembung. $0\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
Semua prediksi menengah berada di antara dan . Kontinuitas menyiratkan akan ada setidaknya satu minimum , di mana harus cembung. Tetapi karena mendekati konstanta terbatas asimptotik, ia tidak dapat cembung untuk cukup besar . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

Garis putus-putus vertikal pada gambar menunjukkan di mana plot berubah dari cembung (di sebelah kiri) ke non-cembung (ke kanan). (Ada juga wilayah non-konveksitas dekat pada gambar ini, tetapi ini tidak akan menjadi kasus pada umumnya.) $\lambda\approx 0$

whuber
sumber

Terima kasih atas jawaban terperinci Anda. Jika mungkin tinjau pertanyaan saat saya mengedit dan memperbarui respons Anda.

rf7

Jawaban bagus (+1). Dalam praktiknya, saya pikir seringkali tidak banyak pelatihan dan uji poin data. Apakah kesimpulan dari jawaban ini berubah ketika ada cukup data pelatihan dan tes yang diambil dari distribusi yang sama (tetap dan cukup reguler)? Secara khusus, dalam skenario ini, adakah minimum lokal yang unik dengan probabilitas tinggi?

user795305

@ Ben Bukan jumlah poin tes yang penting: hasil ini sepenuhnya tergantung pada distribusi poin tes relatif terhadap distribusi poin pelatihan. Oleh karena itu masalah "dengan probabilitas tinggi" tidak akan dapat dijawab tanpa membuat beberapa asumsi spesifik tentang distribusi multivariat dari variabel regressor. Juga, dengan banyak variabel yang berperan, fenomena multi minimum lokal ini akan jauh lebih mungkin. Saya menduga bahwa pemilihan acak dari set tes besar (dengan banyak kali pengamatan sebagai variabel) mungkin sering memiliki min global yang unik.

whuber

@whuber Terima kasih! Saya setuju: distribusi (benar) antara pelatihan dan poin tes harus sama, dan perlu ada cukup sampel sehingga distribusi empiris dari pelatihan dan set tes memiliki kesepakatan. (Sepertinya saya mengutarakannya dengan buruk dalam komentar saya sebelumnya.) Misalnya, jika memiliki distribusi normal bersama (dengan kovarians nondegenerate), saya menduga probabilitas kurva kesalahan memiliki min lokal yang unik yang konvergen ke 1 (jika, katakanlah, ada sampel dalam pelatihan dan set tes dengan dengan tetap (atau bahkan meningkat relatif lambat terhadap ))

(x, y)

$(\mathbf x, y)$

n

$n$

n \to \infty

$n \to \infty$

p

$p$

n

$n$

user795305

$\newcommand{\dbeta}{\frac{\partial}{\partial \lambda} \hat\beta_\lambda}$ $\newcommand{\ddbeta}{\frac{\partial^2}{{\partial \lambda}^2} \hat\beta_\lambda}$

Jawaban ini secara khusus menyangkut laso (dan tidak berlaku untuk regresi ridge.)

Mempersiapkan

Misalkan kita memiliki kovariat yang kita gunakan untuk memodelkan respons. Misalkan kita memiliki titik data pelatihan dan titik data validasi . $p$ $n$ $m$

Biarkan input pelatihan menjadi dan responsnya menjadi . Kami akan menggunakan laso pada data pelatihan ini. Yaitu, letakkan keluarga koefisien yang diperkirakan dari data pelatihan. Kami akan memilih untuk digunakan sebagai estimator kami berdasarkan kesalahannya pada set validasi, dengan input dan respons . Dengan $X_{(1)} \in \mathbb{R}^{n \times p}$ $y_{(1)} \in \mathbb{R}^n$

\begin{matrix} (1) & {\hat{β}}_{λ} = \arg min_{β \in R^{p}} ‖ y_{(1)} - X_{(1)} β ‖_{2}^{2} + λ ‖ β ‖_{1}, \end{matrix}

$\hat\beta_\lambda = \arg\min_{\beta \in \mathbb{R}^p} \|y_{(1)} - X_{(1)} \beta\|_2^2 + \lambda \|\beta\|_1, \tag{1}$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

X_{(2)} \in R^{m \times p}

$X_{(2)} \in \mathbb{R}^{m \times p}$

y_{(2)} \in R^{m}

$y_{(2)} \in \mathbb{R}^m$

\begin{matrix} (2) & \hat{λ} = \arg min_{λ \in R_{+}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}, \end{matrix}

$\hat\lambda = \arg\min_{\lambda \in \mathbb{R}_+} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2, \tag{2}$ kami tertarik mempelajari fungsi kesalahan yang meningkatkan penduga data-driven kami .

e (λ) = ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}

$e(\lambda) = \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2$

{\hat{β}}_{\hat{λ}}

$\hat\beta_{\hat\lambda}$

Perhitungan

Sekarang, kita akan menghitung turunan kedua dari tujuan dalam persamaan , tanpa membuat setiap asumsi distribusi pada 's atau ' s. Menggunakan diferensiasi dan beberapa reorganisasi, kami (secara formal) menghitung bahwa $(2)$ $X$ $y$

\begin{aligned} \frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} & = \frac{\partial}{\partial λ} {- 2 y_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} + 2 {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ}} \\ = - 2 y_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 {({\hat{β}}_{λ})}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 \frac{\partial}{\partial λ} {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)}^{T} \frac{\partial}{\partial λ} {\hat{β}}_{λ} \\ = - 2 {{(y_{(2)} - X_{(2)} {\hat{β}}_{λ})}^{T} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} - ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2}} . \end{aligned}

$\begin{align*} \frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 & = \frac{\partial}{\partial \lambda} \left\{ -2 y_{(2)}^T X_{(2)} \dbeta + 2 \hat\beta_\lambda^T X_{(2)}^T X_{(2)} \dbeta \right\} \\ & = -2 y_{(2)}^T X_{(2)} \ddbeta + 2 \left( \hat\beta_\lambda \right)^T X_{(2)}^T X_{(2)} \ddbeta + 2 \dbeta^T X_{(2)}^T X_{(2)}^T \dbeta \\ & = -2 \left\{ \left( y_{(2)} - X_{(2)} \hat\beta_\lambda \right)^T \ddbeta - \|X_{(2)} \dbeta\|_2^2 \right\}. \end{align*}$ Karena adalah piecewise linear untuk (karena adalah kumpulan simpul hingga di jalur solusi laso), turunan adalah piecewise konstan dan nol untuk semua . Karenanya, fungsi non-negatif dari .

{\hat{β}}_{λ}

$\hat\beta_\lambda$

λ \notin K

$\lambda \not\in K$

K

$K$

\frac{\partial}{\partial λ} {\hat{β}}_{λ}

$\dbeta$

\frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ}

$\ddbeta$

λ \notin K

$\lambda \not\in K$

\frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} = 2 ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2},

$\frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 = 2 \|X_{(2)} \dbeta\|_2^2,$

λ

$\lambda$

Kesimpulan

Jika kita mengasumsikan lebih lanjut bahwa diambil dari beberapa distribusi kontinu independen dari , vektor hampir pasti untuk . Oleh karena itu, fungsi kesalahan memiliki turunan kedua pada yang (hampir pasti) benar-benar positif. Namun, mengetahui bahwa kontinu, kita tahu bahwa kesalahan validasi kontinu. $X_{(2)}$ $\{X_{(1)}, y_{(1)} \}$ $X_{(2)} \dbeta \neq 0$ $\lambda < \lambda_\max$ $e(\lambda)$ $\mathbb{R} \setminus K$ $\hat\beta_\lambda$ $e(\lambda)$

Akhirnya, dari laso ganda, kita tahu bahwa berkurang secara monoton ketika meningkat. Jika kita dapat menetapkan bahwa juga monotonik, maka cembung kuat dari mengikuti. Namun, ini berlaku dengan beberapa kemungkinan mendekati satu jika . (Aku akan segera mengisi detailnya di sini.) $\|X_{(1)} \hat\beta_\lambda\|_2^2$ $\lambda$ $\|X_{(2)} \hat\beta_\lambda\|_2^2$ $e(\lambda)$ $\mathcal{L} \left( X_{(1)} \right) = \mathcal{L} \left( X_{(2)} \right)$

pengguna795305
sumber

Anda hanya mengandalkan sebagai fungsi linear berkesinambungan piecewise dari untuk menyimpulkan benar-benar cembung. Mari kita lihat apakah pengurangan itu secara umum valid. Salah satu fungsi tersebut adalah(di mana menunjukkan pembulatan ke bilangan bulat terdekat). Misalkan dan , sehingga . Fungsi kesalahan ini memiliki banyak minimum lokal. Itu bukan cembung - itu hanya cembung di mana-mana kecuali pada titik-titik terisolasi! Itu membuat saya percaya bahwa Anda membuat asumsi tambahan yang tidak disebutkan.

\hat{β}

$\hat\beta$

λ

$\lambda$

\hat{e}

$\hat e$

\hat{β} (λ) = | λ - [λ] |

$\hat\beta(\lambda)=|\lambda-[\lambda]|$

[]

$[]$

y_{(2)} = 0

$y_{(2)}=0$

X_{(2)} = 1

$X_{(2)}=1$

\hat{e} (λ) = \hat{β} (λ)^{2}

$\hat {e}(\lambda)=\hat\beta(\lambda)^2$

whuber

@whuber Poin bagus! Terima kasih! Saya akan segera mengedit posting ini.

user795305