výpočtů A. Křenek PA081: Programování numerických výpočtů 10. Modelování experimentálních dat, metoda nejmenších čtverců Metoda nejmenších čtverců Lineární regrese Aleš Křenek Lineární modely jaro 2012 Metoda nejmenších absolutních odchylek Regularizace Modelování experimentálních dat v experimentu naměříme v bodech xt hodnoty y t *■ x může být libovolná veličina: čas, napětí, poloha, ... chování systému popisujeme modelem y = M(x) model závisí na sadě parametrů au tj. y = M(x,ai,...,aM) hledáme takové hodnoty au pro něž model odpovídá nejlépe experimentu Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Modelování experimentálních dat Příklad t\n2 ► radioaktivní rozpad N = Noe t ► N je počet atomů ve vzorku (JV0 v čase ř = 0), T poločas rozpadu " príklady/exp. dat" 20*exp(-x/20*log(2)) - 0 10 20 30 40 50 60 70 80 90 100 Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších čtverců Odvození „Jaká je pravděpodobnost, že konkrétni sada parametru at je správná?" ► špatně položená otázka ► neexistuje „náhodná veličina modelů" ► naopak, náhodnou veličinou jsou měřená data zatížená chybou tedy „Při daných parametrech au jaká je pravděpodobnost měření (xuyt)?" Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► 4 ■= * < -š ► Metoda nejmenších čtverců Odvození „Jaká je pravděpodobnost, že konkrétní sada parametrů cii je správná?" ► špatně položená otázka ► neexistuje „náhodná veličina modelů" ► naopak, náhodnou veličinou jsou měřená data zatížená chybou tedy „Při daných parametrech ai, jaká je pravděpodobnost měření (xuyt)?" ► nulová, je-li y spojitá veličina ► musíme přidat „plus/minus odchylka měření Ay" model považujeme za správný, maximalizuje-li tuto pravděpodobnost ► i tak je to velmi intuitivní konstrukce Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ s 4 : ■oq.o Metoda nejmenších čtverců Odvození ► předpokládáme normální rozložení chyby měření ► pravděpodobnost výskytu dané sady měření Y\e H - ) Ay ► maximalizace odpovídá minimalizaci logaritmu, tj. ► N, (J, Ay jsou konstanty Metoda nejmenších čtverců Poznámky ► rozložení chyby všech měření nemusí být stejné ► používá se modifikovaná funkce ■M(xr))2 X = 1 2 af Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších čtverců Poznámky ► rozložení chyby všech měření nemusí být stejné ► používá se modifikovaná funkce ■M(xr))2 X = 1 (yi 2a rozložení chyby nemusí být normální ► počet měření v jednom bodě bývá příliš malý ► zatížení chybou typu „někdo kopl do váhy" ► metoda je na takové chyby nepřiměřeně citlivá ► tzv. robustní statistiky Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších čtverců Poznámky ► rozložení chyby všech měření nemusí být stejné ► používá se modifikovaná funkce ■M(xr))2 X = 1 (yi 2a rozložení chyby nemusí být normální ► počet měření v jednom bodě bývá příliš malý ► zatížení chybou typu „někdo kopl do váhy" ► metoda je na takové chyby nepřiměřeně citlivá ► tzv. robustní statistiky systematická chyba ► např. špatně kalibrovaný přístroj, závislost na související veličině Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších čtverců Zhodnocení vypočtených parametrů ► minimalizací x2 se téměř vždy hodnot ai dopočítáme ► nevypovídá to ještě nic o kvalitě modelu ► např. lineární model radioaktivního rozpadu 0 10 20 30 40 50 60 70 80 90 100 Metoda nejmenších čtverců Zhodnocení vypočtených parametrů ► „chi by eye" nebo seriozní statistické zhodnocení ► hodnotíme pomocí regularizované gamma funkce ► funkce konkrétního x2 a počtu stupňů volnosti (N - M) N ■ ■M x! : ' 2 ► viz např. http://en.wikipedia.org/wiki/Incomplete_ gamma_function ► pravděpodobnost, že zcela náhodně vybraný vzorek (x;, yi) dá větší hodnotu x2 čím větší tím lepší ► Q > 0.1 je v pořádku ► Q G [0.001,0.1] je podezřelé, ale stále přijatelné, není-li distribuce chyb měření zcela normální, resp. je mírně podceněná ► Q < 0.001 znamená špatný model nebo zcela nesmyslné měření Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ s 4 : Lineární regrese ► data prokládáme přímkou a + bx = 0 ► obecnější než se zdá na první pohled ► data (x,y) lze předem libovolně (nelineárně) transformovat na (x',y') *■ minimalizovaná funkce X2(a,b) = X {ji- a- bxj) 2af minimum v bodě nulových prvních derivací o = &- = -2Yyt-a7bXt da ^ uf db ^ a? Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Lineární regrese vhodným vyjádřením faktorů 5, Sx, Sy, Sxx, Sxy ► součty zlomků konstruovaných zxj,Jí,(7í ► vše jsou to tady konstanty řešíme systém lineárních rovnic Sa + Sxb = Sy Sxa + Sxxb = S, xy získáme řešení, ale nevíme nic o jeho kvalitě ► odhad podle grafu nebo výpočet Q ► uvedená lineární regrese na radioaktivní rozpad začíná být přijatelná až když připustíme 07 > 1.6 Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► 4 ■= * < ► Obecný model M(x, a\,au) je nelineární funkce v ai ► nelinearita v x by nevadila, viz dále výpočet minimálního x standardními optimalizačními metodami existují speciální varianty právě pro tvar funkce \2 X2(a1,...,aM) = X (yi -M(Xi,fli,...,flM) 2(7,2 včetně verzí s dostupnými prvními i druhými derivacemi díky speciálnímu použití další triky konkrétní metody ► Levenberg-Marquardt ► Moré např. NAG library Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ (5 4 : Lineární modely ► model M(x, a\,..., cim) je lineární kombinace M(x, ai,...,aM) = YJajxjM ► linearita ve smyslu parametrů modelu a j *■ základní funkce Xj mohou být jakékoli ► pro vyhodnocení modelu se použijí jen jejich konkrétní hodnoty v bodech x; ► opět minimalizujeme x2 *■ definujeme matici A a vektor b Aj XjiXi (Ji bi (Ti Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► 4 š ► < -E ► Lineární modely derivováním dostáváme M rovnic pro k = 1,..., M o = XJ^(yi-X cLjXjixi)) xk(Xi) po úpravách v maticovém vyjádření (ArA)a = Arb řešení bývá citlivé na zaokrouhlovací chyby preferovaná technika je QR rozklad Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Lineární modely Rozklad na singulární hodnoty model nemusí být dokonalý, mohou se objevit téměř lineární závislosti ► některé základní funkce nebo jejich kombinace jsou pro danou datovou sadu irelevantní vede na téměř singulární matici ► standardní metody inklinují k velkým hodnotám irelevantních parametrů SVD dokáže tyto problémy identifikovat algoritmus přímo hledá nejbližší řešení, tj. minimalizuje |Aa-b|2 zároveň detekuje problematické funkce Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Lineární modely Rozklad na singulární hodnoty ► stejná data, kvadratické a kubická funkce "exp.dal" 18.100248-0.426257"x+0.002662*x*x 19.418850-0.593832*x+0.007043-x*x-0.000031 *x*x*x _1_I_I_I-1-1-1-1-1- 10 20 30 40 50 60 70 80 90 100 15/23 Lineární modely tabulka singulárních hodnot pro různé řády polynomu PA081: Programování numerických výpočtů A. Křenek I Modelování experimentálních dat Metoda nejmenších čtverců řád 07 Lineární 1 5.18 537 24 regrese 2 39654.25 3 51 134.10 Obecný model 3 31922200.00 66338 90 564.94 25.73 Lineární modely 4 2685350000.00 4133810 00 19913.70 272.78 99.50 Vícerozměrná koeficienty u xn pro n > 4 jsou téměř nulové data Metoda nejmenších absolutních odchylek Regularizace Vícerozměrná data místo dvojic (xuyt) máme (xuyt) ► x je fc-rozměrný vektor model M je funkce Rk — R jinak se nic nemění ► minimalizujeme vůči parametrům ► základní funkce se pouze vyhodnocují v X/ ► není třeba derivovat podle složek X/ Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších absolutních odchylek metoda nejmenších čtverců minimalizovala ^ {yi - U{Xi,ai,...,aM))2 tj. normu řádu 2 metoda nejmenších absolutních odchylek minimalizuje normu řádu 1 Yj\yi-M(xi,a1,...,aM)\ Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších absolutních odchylek Výhody a nevýhody větší robustnost ► méně citlivá na odlehlé případy ► nemají kvadratickou váhu, snáz se „přebijí" menší stabilita ► malý posun v x může mít velký vliv na výsledné řešení nejednoznačné řešení ► lineární členy se vzájemně kompenzují proti posunu v ose y interaktivní srovnání na lineární regresi: ► http://www.math.wpi.edu/Course_Materi als/SAS/ lablets/7.3/73_choices.html Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace Metoda nejmenších absolutních odchylek Výpočet nejmenší čtverce ► derivace kvadratické funkce ► vede na systém lineárních rovnic absolutní odchylky ► úloha lineárního programování ► např. Barrodale-Robertsův algoritmus Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► 4 ■= * < -š ► Regularizace základní regresní metody fungují dobře pro ideální případy mohou selhávat na reálných datech snaží se modelovat šum více než vlastní chování systému Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► < _: ► < -_ ► Regularizace místo minimalizace výrazu ||Aa - b||2 minimalizujeme ||Aa-b||2 + IITall2 s vhodně volenou maticí ľ (Tikhonovova regularizace) podobně jako u nejmenších čtverců je řešením (ÁrA-TTT)-1Árb volbou ľ zvýhodňujeme nějaké řešení ► např. r = al preferuje menší normu Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► < _: ► < -_ ► Regularizace Vztah k SVD rozklad A na signgulární hodnoty A = UIVT potom řešení regularizovaného problému s ľ = al je (Ti Vl!UTb kde prvky Z jsou tj. a významněji ovlivní právě „skoro nulové" singulární hodnoty Metoda nejmenších čtverců Lineární regrese Lineární modely Metoda nejmenších absolutních odchylek Regularizace □ 4 ► 4 ■= * < ►