Dlaczego istnieją duże współczynniki dla wielomianu wyższego rzędu

W książce Bishopa o uczeniu maszynowym omawia problem dopasowania krzywej funkcji wielomianu do zestawu punktów danych.

Niech M będzie rzędem dopasowanego wielomianu. Tak to stwierdza

Widzimy, że wraz ze wzrostem M wielkość współczynników zwykle rośnie. W szczególności dla wielomianu M = 9 współczynniki zostały precyzyjnie dostrojone do danych poprzez opracowanie dużych wartości dodatnich i ujemnych, dzięki czemu odpowiednia funkcja wielomianu dokładnie pasuje do każdego z punktów danych, ale między punktami danych (szczególnie w pobliżu końców zakres) funkcja wykazuje duże oscylacje.

Nie rozumiem, dlaczego duże wartości implikują ściślejsze dopasowanie punktów danych. Wydaje mi się, że wartości stałyby się bardziej precyzyjne po przecinku zamiast tego dla lepszego dopasowania.

regression least-squares curve-fitting polynomial Abhishek Bhatia
źródło

książka uważa, że x w 10 równo rozmieszczonych punktach w gdzie jest gaussowski z zerową średnią i „małą” wariancją (rozważając dopasowanie 9-wymiarowego wielomianu do 10 punktów ...

y = s i n (2 * π * x) + ϵ

$y = sin(2*\pi * x) + \epsilon$

[0, 1]

$[0,1]$

ϵ

$\epsilon$

seanv507 9.09.16

Odpowiedzi:

Jest to dobrze znany problem z wielomianami wysokiego rzędu, znanymi jako zjawisko Runge . Numerycznie jest związana ze złym klimatyzacji o matrycy Vandermonde , co sprawia, że współczynniki bardzo czułe na niewielkie wahania w danych i / lub zaokrąglenia w obliczeniach (tj model nie jest trwale zidentyfikowania ). Zobacz także tę odpowiedź na SciComp SE.

Istnieje wiele rozwiązań tego problemu, na przykład aproksymacja Czebyszewa , wygładzanie splajnów i regularyzacja Tichonowa . Regularyzacja Tichonowa jest uogólnieniem regresji kalenicowej , karającej normęwektora współczynnika , gdzie do wygładzania macierzy masy jest operatorem pochodnym. Aby penalizować oscylacje, możesz użyć , gdzie jest wielomianem ocenianym na danych. $||\Lambda \theta]||$ $\theta$ $\Lambda$ $\Lambda \theta=p^{\prime\prime}[x]$ $p[x]$

EDYCJA: Odpowiedź użytkownika hxd1011 zauważa, że niektóre problemy numeryczne źle warunkowane można rozwiązać za pomocą wielomianów ortogonalnych, co jest dobrym punktem. Chciałbym jednak zauważyć, że nadal występują problemy związane z identyfikowalnością wielomianów wysokiego rzędu. Oznacza to, że złe warunkowanie numeryczne wiąże się z wrażliwością na „nieskończenie małe” zaburzenia (np. Zaokrąglanie), podczas gdy „statystyczne” złe warunkowanie dotyczy wrażliwości na „skończone” zaburzenia (np. Wartości odstające; odwrotny problem jest źle postawiony ).

Metody wspomniane w moim drugim akapicie dotyczą tej wrażliwości na wartości odstające . Można uznać tę wrażliwość za naruszenie standardowego modelu regresji liniowej, który przy użyciu niedopasowania domyślnie zakłada, że dane są gaussowskie. Spline i regularyzacja Tichonowa radzą sobie z tą wrażliwością odstającą, nakładając gładkość przed dopasowaniem. Przybliżenie Czebyszewa rozwiązuje ten problem za pomocą niedopasowania zastosowanego w domenie ciągłej , tj. Nie tylko w punktach danych. Chociaż wielomiany Czebyszewa są ortogonalne (wrt pewien ważony produkt wewnętrzny), uważam, że gdyby były użyte z stosunku do danych, nadal miałyby wrażliwość odstającą. $L_2$ $L_{\infty}$ $L_2$

GeoMatt22
źródło

L_{2}

$L_2$

p^{″}

$p''$

Gdzie mogę dowiedzieć się więcej o tym „złym uwarunkowaniu działalności matrycy wandermonde”?

Matthew Drury,

@MatthewDrury Zazwyczaj stosuję również podejście empiryczne sugerowane przez hxd1011. Jednak po zapytaniu szybkie Google ujawniło niedawny artykuł, który może również być interesujący: Jak złe są matryce Vandermonde? (VY Pan, 2015) . (Na przykład

zastanawia się,

Dzięki @ GeoMatt22. Przepraszam, że sprawiłem, że znalazłeś się w Google dla mnie, zapytałem, ponieważ myślałem, że możesz mieć jakieś ulubione ulubione źródła.

Matthew Drury,

Pierwszą rzeczą, którą chcesz sprawdzić, jest to, czy autor mówi o surowych wielomianach vs. wielomianach ortogonalnych .

Dla wielomianów ortogonalnych. współczynnik nie staje się „większy”.

Oto dwa przykłady ekspansji wielomianowej 2. i 15. rzędu. Najpierw pokazujemy współczynnik rozszerzenia 2 rzędu.

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

Następnie pokazujemy 15. zamówienie.

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

Zauważ, że używamy wielomianów ortogonalnych , więc współczynnik niższego rzędu jest dokładnie taki sam jak odpowiadające warunki w wynikach wyższego rzędu. Na przykład punkt przecięcia i współczynnik pierwszego rzędu to 20.09 i -29,11 dla obu modeli.

Z drugiej strony, jeśli użyjemy surowego rozszerzenia, coś takiego się nie wydarzy. I będziemy mieli duże i wrażliwe współczynniki! W poniższym przykładzie możemy zobaczyć, że współczynniki są na poziomie . $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

Haitao Du
źródło

Nie jestem pewien, czy składnia jest poprawna, ale dlaczego nie porównać wyników ortogonalnego v raw z czymś podobnym do

summary(lm(mpg~poly(wt,2),mtcars)); summary(lm(mpg~poly(wt,5),mtcars)); summary(lm(mpg~ wt + I(wt^2),mtcars)); summary(lm(mpg~ wt + I(wt^2) + I(wt^3) + I(wt^4) + I(wt^5),mtcars))

Antoni Parellada

@AntoniParellada dobra sugestia, zmienię. BTW, możemy łatwo zrobić surową ekspansję dopoly(x,2,raw=T)

Haitao Du

Fajna sztuczka ... Myślę, że możesz trzymać się 15 i zrobić summary(lm(mpg~poly(wt,15, raw=T),mtcars)). Ogromny efekt we współczynnikach!

Antoni Parellada,

Komentarz do mojej odpowiedzi @ seanv507 wzbudził we mnie zainteresowanie. Jeśli użyjesz ortogonalnych wielomianów i chcesz zmniejszyć wrażliwość na wartości odstające, czy standardowa regresja kalenicy byłaby wystarczająca? A może wielomianowe oscylatory wyższego rzędu, nadal wymagałyby wag ~ rzędu? (Myślę, że to drugie, ponieważ np. Macierz DFT jest ortogonalna, ale nadal potrzebne będą obniżenie wysokich częstotliwości. Miałem (nieprzyjemne) doświadczenie z tym konkretnym przypadkiem!)

GeoMatt22

Abhishek, masz rację, że poprawa precyzji współczynników poprawi dokładność.

Widzimy, że wraz ze wzrostem M wielkość współczynników zwykle rośnie. W szczególności dla wielomianu M = 9 współczynniki zostały precyzyjnie dostrojone do danych poprzez opracowanie dużych wartości dodatnich i ujemnych, dzięki czemu odpowiednia funkcja wielomianu dokładnie pasuje do każdego z punktów danych, ale między punktami danych (szczególnie w pobliżu końców zakres) funkcja wykazuje duże oscylacje.

Myślę, że kwestia wielkości jest raczej nieistotna dla ogólnego punktu widzenia Bishopa - że stosowanie skomplikowanego modelu z ograniczonymi danymi prowadzi do „nadmiernego dopasowania”. W jego przykładzie 10 punktów danych jest używanych do oszacowania 9-wymiarowego wielomianu (tj. 10 zmiennych i 10 niewiadomych).

Jeśli dopasujemy falę sinusoidalną (bez szumu), dopasowanie będzie działać idealnie, ponieważ fale sinusoidalne [w określonym przedziale] można aproksymować z dowolną dokładnością za pomocą wielomianów. Jednak w przykładzie Bishopa mamy pewien „hałas”, do którego nie powinniśmy się dopasowywać. Sposób, w jaki to robimy, polega na utrzymywaniu dużej liczby punktów danych na liczbie zmiennych modelu (współczynniki wielomianowe) lub na regularyzacji.

Normalizacja nakłada na model „miękkie” ograniczenia (np. W regresji grzbietu), funkcja kosztu, którą próbujesz zminimalizować, jest kombinacją „błędu dopasowania” i złożoności modelu: np. W regresji grzbietu złożoność jest mierzona przez sumę kwadratów współczynników - w efekt ten nakłada koszty na zmniejszenie błędu - zwiększenie współczynników będzie dozwolone tylko wtedy, gdy ma wystarczająco dużą redukcję błędu dopasowania [to, jak duże jest wystarczająco duże, określa mnożnik terminu złożoności modelu]. Dlatego mamy nadzieję, że wybierając odpowiedni mnożnik nie będziemy pasować do dodatkowego małego szumu, ponieważ poprawa dopasowania nie uzasadnia wzrostu współczynników.

Zapytałeś, dlaczego duże współczynniki poprawiają jakość dopasowania. Zasadniczo powodem jest to, że oszacowana funkcja (sin + hałas) nie jest wielomianem, a duże zmiany krzywizny wymagane do przybliżenia efektu szumu z wielomianami wymagają dużych współczynników.

Zauważ, że użycie ortogonalnych wielomianów nie daje żadnego efektu (dodałem przesunięcie 0,1 tylko po to, aby ortogonalne i surowe wielomiany nie były na sobie)

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'))

seanv507
źródło