Mengapa ada koefisien besar untuk polinomial tingkat tinggi

Dalam buku Bishop tentang pembelajaran mesin, ia membahas masalah penyesuaian kurva fungsi polinomial ke sejumlah titik data.

Biarkan M menjadi urutan polinomial yang dipasang. Ini menyatakan seperti itu

Kita melihat bahwa, ketika M meningkat, besarnya koefisien biasanya menjadi lebih besar. Khususnya untuk polinomial M = 9, koefisien-koefisiennya telah disesuaikan dengan data dengan mengembangkan nilai-nilai positif dan negatif yang besar sehingga fungsi polinomial yang sesuai sesuai dengan masing-masing titik data secara tepat, tetapi di antara titik-titik data (khususnya di dekat ujung-ujungnya). range) fungsi menunjukkan osilasi besar.

Saya tidak mengerti mengapa nilai besar menyiratkan lebih dekat dengan titik data. Saya akan berpikir nilai-nilai akan menjadi lebih tepat setelah desimal, bukan untuk pemasangan yang lebih baik.

Ini adalah masalah yang terkenal dengan polinomial tingkat tinggi, yang dikenal sebagai fenomena Runge . Numerik hal ini terkait dengan sakit-conditioning dari matriks Vandermonde , yang membuat koefisien sangat sensitif terhadap variasi kecil dalam data dan / atau roundoff dalam perhitungan (yaitu model tidak stabil diidentifikasi ). Lihat juga jawaban ini di SciComp SE.

Ada banyak solusi untuk masalah ini, misalnya perkiraan Chebyshev , smoothing splines , dan regularisasi Tikhonov . Regularisasi Tikhonov adalah generalisasi dari regresi ridge , menghukum norma dari koefisien vektor θ , di mana untuk menghaluskan matriks bobot Λ adalah beberapa operator turunan. Untuk menghukum osilasi, Anda dapat menggunakan Λ θ = p ′ ′ [ x ] , di mana p [ x $||\Lambda \theta]||$$\theta$$\Lambda$$\Lambda \theta=p^{\prime\prime}[x]$$p[x]$ adalah polinomial yang dievaluasi pada data.

EDIT: Jawaban oleh pengguna hxd1011 mencatat bahwa beberapa masalah pengondisian numerik dapat diatasi menggunakan polinomial ortogonal, yang merupakan poin yang baik. Namun saya ingin mencatat bahwa masalah pengidentifikasian dengan polinomial tingkat tinggi masih ada. Artinya, pengondisian numerik dikaitkan dengan sensitivitas terhadap gangguan "sangat kecil" (misalnya pembulatan), sementara pengkondisian "statistik" menyangkut sensitivitas terhadap gangguan "terbatas" (misalnya pencilan; masalah terbalik adalah kesalahan penempatan ).

Metode yang disebutkan dalam paragraf kedua saya berkaitan dengan sensitivitas pencilan ini . Anda dapat menganggap sensitivitas ini sebagai pelanggaran model regresi linier standar, yang dengan menggunakan ketidakcocokan secara implisit mengasumsikan bahwa data tersebut adalah Gaussian. Regulasi Splines dan Tikhonov berurusan dengan sensitivitas pencilan ini dengan memaksakan kelancaran sebelum fit. Chebyshev penawaran pendekatan dengan ini dengan menggunakan L ∞ ketidakcocokan diterapkan atas domain terus menerus , yaitu tidak hanya pada titik-titik data. Meskipun polinomial Chebyshev adalah orthogonal (produk dalam tertimbang tertentu), saya percaya bahwa jika digunakan dengan ketidakcocokan L 2 atas data, mereka akan tetap$L_2$$L_{\infty}$$L_2$ memiliki sensitivitas pencilan.

Hal pertama yang ingin Anda periksa, adalah jika penulis berbicara tentang polinomial mentah vs. polinomial ortogonal .

Untuk polinomial ortogonal. koefisiennya tidak menjadi "lebih besar".

Berikut adalah dua contoh ekspansi polinomial orde 2 dan 15. Pertama, kami menunjukkan koefisien untuk ekspansi urutan kedua.

summary(lm(mpg~poly(wt,2),mtcars))

Call:
lm(formula = mpg ~ poly(wt, 2), data = mtcars)

Residuals:
   Min     1Q Median     3Q    Max 
-3.483 -1.998 -0.773  1.462  6.238 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)   20.0906     0.4686  42.877  < 2e-16 ***
poly(wt, 2)1 -29.1157     2.6506 -10.985 7.52e-12 ***
poly(wt, 2)2   8.6358     2.6506   3.258  0.00286 ** 
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.651 on 29 degrees of freedom
Multiple R-squared:  0.8191,    Adjusted R-squared:  0.8066 
F-statistic: 65.64 on 2 and 29 DF,  p-value: 1.715e-11

Kemudian kami menampilkan urutan ke-15.

summary(lm(mpg~poly(wt,15),mtcars))

Call:
lm(formula = mpg ~ poly(wt, 15), data = mtcars)

Residuals:
    Min      1Q  Median      3Q     Max 
-5.3233 -0.4641  0.0072  0.6401  4.0394 

Coefficients:
               Estimate Std. Error t value Pr(>|t|)    
(Intercept)     20.0906     0.4551  44.147  < 2e-16 ***
poly(wt, 15)1  -29.1157     2.5743 -11.310 4.83e-09 ***
poly(wt, 15)2    8.6358     2.5743   3.355  0.00403 ** 
poly(wt, 15)3    0.2749     2.5743   0.107  0.91629    
poly(wt, 15)4   -1.7891     2.5743  -0.695  0.49705    
poly(wt, 15)5    1.8797     2.5743   0.730  0.47584    
poly(wt, 15)6   -2.8354     2.5743  -1.101  0.28702    
poly(wt, 15)7    2.5613     2.5743   0.995  0.33459    
poly(wt, 15)8    1.5772     2.5743   0.613  0.54872    
poly(wt, 15)9   -5.2412     2.5743  -2.036  0.05866 .  
poly(wt, 15)10  -2.4959     2.5743  -0.970  0.34672    
poly(wt, 15)11   2.5007     2.5743   0.971  0.34580    
poly(wt, 15)12   2.4263     2.5743   0.942  0.35996    
poly(wt, 15)13  -2.0134     2.5743  -0.782  0.44559    
poly(wt, 15)14   3.3994     2.5743   1.320  0.20525    
poly(wt, 15)15  -3.5161     2.5743  -1.366  0.19089    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 2.574 on 16 degrees of freedom
Multiple R-squared:  0.9058,    Adjusted R-squared:  0.8176 
F-statistic: 10.26 on 15 and 16 DF,  p-value: 1.558e-05

Perhatikan bahwa, kami menggunakan polinomial ortogonal , sehingga koefisien urutan rendah persis sama dengan istilah yang sesuai dalam hasil urutan yang lebih tinggi. Misalnya, intersep dan koefisien untuk urutan pertama adalah 20,09 dan -29,11 untuk kedua model.

$10^6$

> summary(lm(mpg~poly(wt,15, raw=T),mtcars))

Call:
lm(formula = mpg ~ poly(wt, 15, raw = T), data = mtcars)

Residuals:
    Min      1Q  Median      3Q     Max 
-5.6217 -0.7544  0.0306  1.1678  5.4308 

Coefficients: (3 not defined because of singularities)
                          Estimate Std. Error t value Pr(>|t|)
(Intercept)              6.287e+05  9.991e+05   0.629    0.537
poly(wt, 15, raw = T)1  -2.713e+06  4.195e+06  -0.647    0.526
poly(wt, 15, raw = T)2   5.246e+06  7.893e+06   0.665    0.514
poly(wt, 15, raw = T)3  -6.001e+06  8.784e+06  -0.683    0.503
poly(wt, 15, raw = T)4   4.512e+06  6.427e+06   0.702    0.491
poly(wt, 15, raw = T)5  -2.340e+06  3.246e+06  -0.721    0.480
poly(wt, 15, raw = T)6   8.537e+05  1.154e+06   0.740    0.468
poly(wt, 15, raw = T)7  -2.184e+05  2.880e+05  -0.758    0.458
poly(wt, 15, raw = T)8   3.809e+04  4.910e+04   0.776    0.447
poly(wt, 15, raw = T)9  -4.212e+03  5.314e+03  -0.793    0.438
poly(wt, 15, raw = T)10  2.382e+02  2.947e+02   0.809    0.429
poly(wt, 15, raw = T)11         NA         NA      NA       NA
poly(wt, 15, raw = T)12 -5.642e-01  6.742e-01  -0.837    0.413
poly(wt, 15, raw = T)13         NA         NA      NA       NA
poly(wt, 15, raw = T)14         NA         NA      NA       NA
poly(wt, 15, raw = T)15  1.259e-04  1.447e-04   0.870    0.395

Residual standard error: 2.659 on 19 degrees of freedom
Multiple R-squared:  0.8807,    Adjusted R-squared:  0.8053 
F-statistic: 11.68 on 12 and 19 DF,  p-value: 2.362e-06

Abhishek, Anda benar bahwa meningkatkan ketepatan koefisien akan meningkatkan akurasi.

Kita melihat bahwa, ketika M meningkat, besarnya koefisien biasanya menjadi lebih besar. Khususnya untuk polinomial M = 9, koefisien-koefisiennya telah disesuaikan dengan data dengan mengembangkan nilai-nilai positif dan negatif yang besar sehingga fungsi polinomial yang sesuai sesuai dengan masing-masing titik data secara tepat, tetapi di antara titik-titik data (khususnya di dekat ujung-ujungnya). range) fungsi menunjukkan osilasi besar.

Saya pikir masalah besarnya agak tidak relevan dengan poin keseluruhan Bishop - bahwa menggunakan model rumit pada data terbatas mengarah ke 'overfitting'. Dalam contohnya 10 titik data digunakan untuk memperkirakan polinomial 9 dimensi (yaitu 10 variabel dan 10 tidak diketahui).

Jika kita pas dengan gelombang sinus (tanpa noise), maka pas bekerja dengan sempurna, karena gelombang sinus [lebih dari interval tetap] dapat diperkirakan dengan akurasi sewenang-wenang menggunakan polinomial. Namun, dalam contoh Bishop, kita memiliki sejumlah 'kebisingan' yang tidak boleh kita muat. Cara kita melakukan ini adalah dengan menjaga jumlah titik data ke jumlah variabel model (koefisien polinom) besar atau dengan menggunakan regularisasi.

Regulasi memaksakan batasan 'lunak' pada model (misalnya dalam regresi ridge) fungsi biaya yang Anda coba untuk meminimalkan adalah kombinasi dari 'kesalahan pemasangan' dan kompleksitas model: misalnya dalam regresi ridge kompleksitas diukur dengan jumlah koefisien kuadrat- dalam efek ini membebankan biaya pada pengurangan kesalahan - meningkatkan koefisien hanya akan diizinkan jika memiliki pengurangan yang cukup besar dalam kesalahan pemasangan [seberapa besar cukup besar ditentukan oleh pengali pada istilah kompleksitas model]. Oleh karena itu harapannya adalah bahwa dengan memilih pengganda yang sesuai kita tidak akan cocok dengan istilah kebisingan kecil tambahan, karena peningkatan kecocokan tidak membenarkan peningkatan koefisien.

Anda bertanya mengapa koefisien besar meningkatkan kualitas kecocokan. Pada dasarnya, alasannya adalah bahwa fungsi yang diperkirakan (sin + noise) bukan polinomial, dan perubahan besar dalam kelengkungan diperlukan untuk memperkirakan efek noise dengan polinomial membutuhkan koefisien yang besar.

Perhatikan bahwa menggunakan polinomial ortogonal tidak memiliki efek (saya telah menambahkan offset 0,1 hanya agar polinomial ortogonal dan mentah tidak berada di atas satu sama lain)

require (penalized)
poly_order<-9
x_long<-seq(0,1, length.out = 100)
nx<-10
x<-seq(0,1, length.out = nx)
noise<- rnorm(nx, 0, 1)
noise_scale<-0.2
y<-sin(2*pi*x)+noise_scale*noise

training_data<-data.frame(x=x,y=y)
y_long<-sin(2*pi*x_long)

plot(x,y, col ='blue',ylim=c(-1.5,1.5))
lines(x_long,y_long,col='green')

polyfit_raw<-lm(y~poly(x,poly_order,raw=TRUE),data=training_data)
summary(polyfit_raw)

polyfit_raw_ridge1<-penalized(y,~poly(x,poly_order,raw=TRUE), model='linear', data=training_data, lambda2=0.0001, maxiter=10000, standardize=TRUE)

polyfit_orthog<-lm(y~poly(x,poly_order),data=training_data)
summary(polyfit_orthog)

pred_raw<-predict(polyfit_raw,data.frame(x=x_long))
pred_ortho<-predict(polyfit_orthog,data.frame(x=x_long))
pred_raw_ridge<-predict(polyfit_raw_ridge1,data=data.frame(x=x_long))[,'mu']
lines(x_long,pred_raw,col='red')
# add 0.1 offset to make visible
lines(x_long,pred_ortho+0.1,col='black')
lines(x_long,pred_raw_ridge,col='purple')
legend("bottomleft",legend=c('data sin(2 pi x) + noise','sin(2 pi x)', 
                             'raw poly','orthog poly +0.1 offset','raw poly + ridge regression'),
       fill=c('blue','green','red','black','purple'))