Regularisasi Tikhonov

Mengapa Kuadrat Terkecil Dapat Tidak Stabil

Untuk $A\in\mathbb{R}^{m\times n}$ dan $b\in\mathbb{R}^m$ , kuadrat terkecil biasa menyelesaikan

\min_x\|Ax-b\|_2^2

Solusi minimum selalu ada, bahkan ketika persamaan $Ax=b$ tidak konsisten. Jika $A$ tidak berperingkat penuh, solusinya mungkin tidak tunggal. Jika $A$ hampir tidak berperingkat penuh, perubahan kecil pada $b$ dapat menyebabkan perubahan besar pada parameter hasil pencocokan.

$Dekomposisi nilai singular$ menjelaskan penguatan galat. Pada solusi kuadrat terkecil bernorma minimum, setiap komponen data dibagi dengan $nilai singular positif$ yang sesuai. Nilai singular nol memberikan kontribusi nol melalui pseudoinvers. Nilai singular positif yang sangat kecil memperbesar galat pada arah data tersebut.

Masalah Tikhonov

Regularisasi Tikhonov menyeimbangkan $kecocokan terhadap data$ dengan penalti yang dipilih, misalnya jarak dari $x_0$ atau perubahan antarparameter.

Untuk $\alpha>0$ , minimalkan:

\min_x\left(\|Ax-b\|_2^2+\alpha^2\|L(x-x_0)\|_2^2\right)

Di sini $x_0$ adalah perkiraan acuan dan $L$ menentukan besaran yang diberi penalti. Nilai $\alpha$ menentukan perbandingan bobot antara kecocokan data dan penalti yang ditentukan oleh $L$ .

$L=I$ memberi penalti pada jarak dari $x_0$ .
Matriks selisih pertama memberi penalti pada perubahan cepat antara parameter yang bertetangga.
Matriks selisih kedua memberi penalti lebih besar pada profil yang banyak melengkung, sehingga solusi cenderung lebih mulus.

Penalti menambahkan asumsi model tentang bentuk solusi dan dapat memperbaiki kondisi numerik masalah optimisasi. Informasi di dalam data pengamatan tetap sama.

Bentuk Kuadrat Terkecil Teraugmentasi

Masalah regularisasi di atas dapat ditulis sebagai masalah kuadrat terkecil berikut:

\min_x\left\|\begin{pmatrix}A\\\alpha L\end{pmatrix}x-\begin{pmatrix}b\\\alpha Lx_0\end{pmatrix}\right\|_2^2

Jika fungsi objektif ini diturunkan terhadap $x$ , kita memperoleh persamaan normal berikut:

(A^TA+\alpha^2L^TL)x =A^Tb +\alpha^2L^TLx_0

Persamaan normal tersebut memiliki $solusi unik$ tepat ketika syarat berikut terpenuhi.

\operatorname{null}(A)\cap\operatorname{null}(L)=\{0\}

Untuk regularisasi ridge standar dengan $L=I$ , syarat ini terpenuhi bagi setiap $\alpha>0$ karena $A^TA+\alpha^2I$ definit positif.

Penyaringan Spektral

Untuk $L=I$ dan $x_0=0$ , tulis $A=U\Sigma V^T$ . Maka

x_\alpha=\sum_i\frac{\sigma_i}{\sigma_i^2+\alpha^2}(u_i^Tb)v_i

Jika $\sigma_i$ jauh lebih besar daripada $\alpha$ , faktor $\phi_i(\alpha)$ mendekati $1$ . Regularisasi hampir tidak mengubah $komponen solusi$ yang terkait dengan nilai singular tersebut. Jika $\sigma_i$ jauh lebih kecil daripada $\alpha$ , faktor $\phi_i(\alpha)$ mendekati $0$ , sehingga komponen solusinya diperkecil. Cara ini mencegah kesalahan kecil pada data pengukuran menghasilkan perubahan besar pada solusi.

Contoh Perhitungan Sensitivitas

Perhatikan

A=\begin{pmatrix}1&0\\0&0{,}1\end{pmatrix},\qquad b=\begin{pmatrix}1\\0{,}2\end{pmatrix}

Nilai singular kedua hanya $0{,}1$ . Perubahan $0{,}01$ pada pengamatan kedua mengubah parameter kedua tanpa regularisasi sebesar $0{,}1$ .

Dengan $L=I$ , $x_0=0$ , dan $\alpha=0{,}2$ ,

(A^TA+0{,}2^2I)x=A^Tb

Perubahan data sebesar $0{,}01$ kini hanya mengubah parameter kedua sebesar $0{,}02$ . Nilai $0{,}4$ juga menunjukkan bahwa penalti membuat perkiraan parameter kedua mendekati $0$ . Jadi, regularisasi $mengurangi sensitivitas terhadap perubahan data$ sekaligus menggeser perkiraan parameter. Selisih dari perkiraan tanpa regularisasi saja belum menentukan perkiraan mana yang lebih dekat dengan parameter sebenarnya yang belum diketahui.

Bandingkan parameter kedua sebelum dan sesudah perubahan data yang sama. Perubahan ini tidak mengubah parameter pertama.

Metode	Sebelum	Sesudah	Perubahan
Tanpa regularisasi	$2$	$21/10$	$1/10$
$\alpha=1/5$	$2/5$	$21/50$	$1/50$

\Delta x_2=\frac{(1/10)(1/100)}{(1/10)^2+(1/5)^2}=\frac{1/1000}{1/20}=\frac1{50}

Memilih Parameter Regularisasi

$Tidak ada satu nilai$ $\alpha$ yang selalu terbaik. Pilihan $\alpha$ bergantung pada besarnya gangguan acak dalam data pengamatan, skala parameter, penalti, dan tujuan model.

Metode	Bukti yang sesuai	Keputusan
Validasi atau validasi silang	Pemodelan prediktif dengan sebagian data yang dipisahkan untuk validasi	Pilih nilai dengan kinerja terbaik pada data validasi
Prinsip diskrepansi	Perkiraan besarnya gangguan acak pada data pengamatan	Cocokkan norma residual dengan besar gangguan yang diperkirakan
Generalized cross-validation atau GCV	Masalah invers linear tanpa set validasi terpisah	Pilih nilai yang membuat skor prediksi GCV paling kecil
Kurva L	Analisis eksploratif masalah invers	Cari titik tekuk pada kurva yang membandingkan norma residual dan norma penalti

Nilai $\alpha$ yang kecil membuat solusi mengikuti data dengan lebih dekat, tetapi gangguan kecil pada data masih dapat menghasilkan perubahan besar pada solusi. Nilai $\alpha$ yang besar memberi pengaruh lebih kuat pada penalti, sehingga solusi dapat menjadi terlalu mulus atau komponennya menjadi terlalu kecil. Kolom parameter dan baris penalti juga harus memakai skala yang bermakna. Jika skala ini diabaikan, angka $\alpha$ saja belum menunjukkan seberapa kuat penalti bekerja.

Bobot dan Syarat pada Solusi

Matriks diagonal $L=\operatorname{diag}(\omega_1,\ldots,\omega_n)$ memberikan penalti khusus per parameter:

\|L(x-x_0)\|_2^2=\sum_{i=1}^n\omega_i^2(x_i-x_{0i})^2

Semakin besar $\omega_i$ , semakin dekat nilai $x_i$ yang dipilih model dengan nilai acuan $x_{0i}$ . Pilih bobot berdasarkan satuan dan informasi awal yang jelas, misalnya skala wajar setiap parameter atau perubahan yang diperkirakan mulus antarparameter. Tingkat kesulitan memperkirakan parameter belum cukup untuk menentukan bobot.

Jika persamaan seperti $x_i=c$ harus selalu terpenuhi, masukkan persamaan itu sebagai $syarat tersendiri$ dalam model. Batas seperti $l_i\le x_i\le u_i$ memerlukan metode kuadrat terkecil yang dapat membatasi nilai solusi. Penalti yang sangat besar dapat mendekatkan solusi ke persamaan tersebut, tetapi tidak menjamin persamaan terpenuhi tepat dan dapat memperburuk skala numerik.

Menyelesaikan Sistem yang Diperluas

Persamaan normal dapat digunakan untuk menurunkan estimator teregularisasi dan memeriksa pengaruh $\alpha$ serta $L$ . Untuk komputasi numerik, jangan membentuk $A^TA$ karena langkah itu menguadratkan bilangan kondisi. $Sistem kuadrat terkecil teraugmentasi$ dapat diselesaikan dengan $\mathrm{QR}$ atau $\mathrm{SVD}$ . Agar perhitungan mudah diperiksa dan diulang, cantumkan $\alpha$ , $L$ , skala parameter, norma residual, dan norma penalti yang digunakan.