Bisakah ada beberapa solusi optimal lokal ketika kita menyelesaikan regresi linier?

Saya membaca pernyataan ini pada satu ujian benar / salah lama:

Kita bisa mendapatkan beberapa solusi optimal lokal jika kita memecahkan masalah regresi linier dengan meminimalkan jumlah kesalahan kuadrat menggunakan gradient descent.

Solusi: Salah

Pertanyaan saya adalah, bagian mana dari pertanyaan ini yang salah? Mengapa pernyataan ini salah?

Pertanyaan ini menarik sejauh memaparkan beberapa koneksi antara teori optimasi, metode optimasi, dan metode statistik yang perlu dipahami oleh setiap pengguna statistik yang mampu. Meskipun koneksi ini sederhana dan mudah dipelajari, mereka halus dan sering diabaikan.

Untuk meringkas beberapa ide dari komentar ke balasan lain, saya ingin menunjukkan setidaknya ada dua cara yang "regresi linier" dapat menghasilkan solusi non-unik - bukan hanya secara teoritis, tetapi dalam prakteknya.

Kurangnya pengidentifikasian

Yang pertama adalah ketika model tidak dapat diidentifikasi. Ini menciptakan fungsi objektif cembung tetapi tidak sepenuhnya cembung yang memiliki beberapa solusi.

Perhatikan, misalnya, regresi terhadap x dan y (dengan intercept) untuk ( x , y , z ) Data ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ) . Salah satu solusinya adalah z = 1 + y . Lain adalah $z$$x$$y$$(x,y,z)$$(1,-1,0),(2,-2,-1),(3,-3,-2)$$\hat z = 1 + y$ . Untuk melihat bahwa harus ada beberapa solusi, parameterkan model dengan tiga parameter nyata ( λ , μ , ν ) dan istilah kesalahan ε dalam bentuk$\hat z = 1-x$$(\lambda,\mu,\nu)$$\varepsilon$

Jumlah kuadrat residu disederhanakan

(Ini adalah kasus terbatas fungsi obyektif yang muncul dalam praktik, seperti yang dibahas di Dapatkah goni empiris dari penaksir-M menjadi tidak terbatas?) , Di mana Anda dapat membaca analisis terperinci dan melihat plot fungsi.)

Karena koefisien dari kuadrat ( dan 56 ) adalah positif dan penentu 3 × 56 - ( 24 / 2 ) 2 = 24 adalah positif, ini adalah bentuk kuadrat positif-semidefinite di ( μ , ν , λ ) . Ini diminimalkan ketika μ = ν = 0 , tetapi λ dapat memiliki nilai apa pun. Karena fungsi objektif SSR tidak bergantung pada $3$$56$$3\times 56 - (24/2)^2 = 24$$(\mu,\nu,\lambda)$$\mu=\nu=0$$\lambda$$\operatorname{SSR}$$\lambda$, juga tidak gradiennya (atau turunan lainnya). Oleh karena itu, setiap algoritma gradient descent - jika tidak melakukan perubahan arah yang sewenang-wenang - akan menetapkan nilai solusi menjadi apa pun nilai awalnya.$\lambda$

Bahkan ketika gradient descent tidak digunakan, solusinya dapat bervariasi. Dalam R, misalnya, ada dua mudah, cara setara untuk menentukan model ini: sebagai z ~ x + yatau z ~ y + x. Pertama hasil z = 1 - x tapi yang kedua memberikan z = 1 + y . $\hat z = 1 - x$$\hat z = 1 + y$

> x <- 1:3
> y <- -x
> z <- y+1

> lm(z ~ x + y)
Coefficients:
(Intercept)            x            y  
          1           -1           NA  


> lm(z ~ y + x)
Coefficients:
(Intercept)            y            x  
          1            1           NA 

( NANilai - nilai harus ditafsirkan sebagai nol, tetapi dengan peringatan bahwa ada beberapa solusi. Peringatan itu mungkin karena analisis awal yang dilakukan dalam Ryang independen dari metode solusinya. Metode penurunan gradien kemungkinan tidak akan mendeteksi kemungkinan beberapa solusi, meskipun yang baik akan memperingatkan Anda tentang beberapa ketidakpastian bahwa itu telah sampai pada optimal.)

Batasan parameter

Convexity yang ketat menjamin global optimal yang unik, asalkan domain parameternya adalah cembung. Pembatasan parameter dapat membuat domain non-cembung, yang mengarah ke beberapa solusi global.

Contoh yang sangat sederhana diberikan oleh masalah memperkirakan "rata-rata" untuk data - 1 , 1 tunduk pada pembatasan | μ | ≥ 1 / 2 . Ini memodelkan situasi yang merupakan kebalikan dari metode regularisasi seperti Ridge Regression, Lasso, atau Elastic Net: bersikeras bahwa parameter model tidak menjadi terlalu kecil. (Berbagai pertanyaan muncul di situs ini menanyakan bagaimana menyelesaikan masalah regresi dengan batasan parameter seperti itu, menunjukkan bahwa mereka memang muncul dalam praktik.)$\mu$$-1, 1$$|\mu| \ge 1/2$

$(1-\mu)^2 + (-1-\mu)^2$$|\mu| \ge 1/2$$\mu=\pm 1/2$$\mu \in (-\infty, -1/2]\cup [1/2, \infty)$

$\mu$$\mu=\pm 1/2$$5/2$

$\mu=1/2$$\mu=-1/2$

Situasi yang sama dapat terjadi dengan kumpulan data yang lebih besar dan dalam dimensi yang lebih tinggi (yaitu, dengan lebih banyak parameter regresi yang sesuai).

Saya khawatir tidak ada jawaban biner untuk pertanyaan Anda. Jika regresi Linear benar-benar cembung (tidak ada kendala pada koefisien, tidak ada regulator dll,) maka gradient descent akan memiliki solusi yang unik dan akan menjadi global optimal. Gradient descent dapat dan akan mengembalikan beberapa solusi jika Anda memiliki masalah non-cembung.

Meskipun OP meminta regresi linier, contoh di bawah ini menunjukkan minimalisasi kuadrat walaupun nonlinier (vs regresi linier yang diinginkan OP) dapat memiliki beberapa solusi dan gradient descent dapat mengembalikan solusi yang berbeda.

Saya dapat menunjukkan secara empiris menggunakan contoh sederhana itu

1. Jumlah kesalahan kuadrat kadang-kadang bisa menjadi non-cembung, oleh karena itu ada beberapa solusi
2. Metode keturunan gradien dapat memberikan beberapa solusi.

Pertimbangkan contoh di mana Anda mencoba meminimalkan kuadrat terkecil untuk masalah berikut:

$w$$a$

$a_{12} =9,a_{13} = 1/9,a_{23}=9,a_{31}=1/9$

$minimize$ ${(9-\frac{w_1}{w_2})^2+(\frac{1}{9}-\frac{w_1}{w_3})^2+(\frac{1}{9}-\frac{w_2}{w_1})^2+(9-\frac{w_2}{w_3})^2+(9-\frac{w_3}{w_1})^2+(\frac{1}{9}-\frac{w_3}{w_2})^2}$

Masalah di atas memiliki 3 solusi berbeda dan mereka adalah sebagai berikut:

$w = (0.670,0.242,0.080),obj = 165.2$

$w = (0.080,0.242,0.670),obj = 165.2$

$w = (0.242,0.670,0.080),obj = 165.2$

Seperti yang ditunjukkan di atas masalah kuadrat terkecil bisa nonconvex dan dapat memiliki beberapa solusi. Kemudian masalah di atas dapat diselesaikan dengan menggunakan metode gradient descent seperti microsoft excel solver dan setiap kali kita menjalankan akhirnya kita mendapatkan solusi yang berbeda. karena gradient descent adalah pengoptimal lokal dan dapat terjebak dalam solusi lokal kita perlu menggunakan nilai awal yang berbeda untuk mendapatkan global optima yang sebenarnya. Masalah seperti ini tergantung pada nilai awal.

Ini karena fungsi objektif yang Anda minimalkan adalah cembung, hanya ada satu minimum / maksimal. Oleh karena itu, optimum lokal juga optimal global. Keturunan gradien akan menemukan solusi pada akhirnya.

Mengapa fungsi objektif ini cembung? Ini adalah keindahan menggunakan kesalahan kuadrat untuk meminimalkan. Derivasi dan kesetaraan ke nol akan menunjukkan dengan baik mengapa hal ini terjadi. Ini cukup masalah buku teks dan dibahas hampir di mana-mana.