Discussion:
Najlepsze dopasowanie dla potęg wyższych niż 2
(Wiadomość utworzona zbyt dawno temu. Odpowiedź niemożliwa.)
Borneq
2020-12-01 17:06:39 UTC
Permalink
Cytując Bartka:

Na dzień dobry, to, że funkcja y=a sqrt(x)+b jest nieliniowa nie ma
najmniejszego znaczenia. y (a nawet ściślej, wektor błędów - residuum)
ma być liniowe względem _parametrów_. a i b. To ona są istotne.

Powiedzmy, że mamy LZNK postaci
y = a* f(x1,x2,x3...) + b* g(x1,x2,x3...) + c*h(x1,x2,x3...) +e
I zestaw danych (y,x1,x2,x3...), k takich krotek.

Błąd pojedynczego pomiaru to

Zapiszmy to równanie tak:

Y = A v -E
gdzie Y - wektor y-ków
v - wektor [a,b,c..]
A - Macierz, w której w wierszu k znajduje się f(.),g(.),h(.) dla k-tego
zestawu danych.

Wektor błędów
E = Av -Y
To nic nowego, tylko oryginalne równania zapisane macierzowo. Chcemy aby
druga norma E była możliwie najmniejsza. Metod jest parę, dla
niewielkich danych wystarczy równane normalne - można udowodnić, że v
daje najmniejsze E, gdy v spełnia równania
A^tA v = A^tY

Jeśli mamy j różnych funkcji (2 w zadaniu, 3 w moim zapisie), to A^t A
(macierz transponowana * macierz) jest tylko j x j. A^tY to wektor
dlugości j., można rozwiązywać.

W zadaniu pierwszą funkcją jest sqrt(x), drugą 1(stała).
W wersji dla f liniowej y = at +1
Macierz A to kolumna wartośći t i kolumna jedynek.
Licząc A^t A i A^tY dostajemy szkolne wzorki.

Ale takie podejście daje wygodne narzędzie dla przypadków dowolnie wielu
funkcji od dowolnie wielu zmiennych. Byle współczynniki, którymi chcemy
manipulować, były liniowe. Więc nie y=a sin( x+b ), ale y=a sin(x) + b
cos(x).

Edit: wniosek, który należy wyciągnąć, to to, że w przypadku
y = a .... + b .... + c .....
te .... nie są dla nas istotne, nieważne, jakiej sa postaci, to tylko
numeryczne wielkości które ładuje się do liczbowej tabelki, mięsko jest
gdzie indziej, w wektorze [a,b,c].

===================
Zwłaszcza fragment
E = Av -Y
To nic nowego, tylko oryginalne równania zapisane macierzowo. Chcemy aby
druga norma E była możliwie najmniejsza. Metod jest parę, dla
niewielkich danych wystarczy równane normalne - można udowodnić, że v
daje najmniejsze E, gdy v spełnia równania
A^tA v = A^tY

Co gdy chcemy by zamiast drugiej normy E minimalizować trzecią , czwartą
i większą normę?
Jak obliczyć wektor v?
Jak się do tego zabrać? Gdyby było równanie, można by je obliczyć
wielowymiarowym Newtonem, być może jako punkt początkowy przyjmując
wynik dla minimalizacji drugiej normy.
Borneq
2020-12-01 17:46:10 UTC
Permalink
Post by Borneq
E = Av -Y
To nic nowego, tylko oryginalne równania zapisane macierzowo. Chcemy aby
druga norma E była możliwie najmniejsza. Metod jest parę, dla
niewielkich danych wystarczy równane normalne - można udowodnić, że v
daje najmniejsze E, gdy v spełnia równania
A^tA v = A^tY
w https://global.oup.com/booksites/content/0199268010/samplesec3
wyprowadzenie wzoru zaznaczonego tam jako (3.9)
nie bardzo wiem, dlaczego x_i=1 dla każdego i na początku wyprowadzenia.
Borneq
2020-12-01 18:24:58 UTC
Permalink
Post by Borneq
w https://global.oup.com/booksites/content/0199268010/samplesec3
wyprowadzenie wzoru zaznaczonego tam jako (3.9)
nie bardzo wiem, dlaczego x_i=1 dla każdego i na początku wyprowadzenia.
Tylko że dla sumy kwadratów zauważone jest we wzorze (3.6) że taka suma
to jest iloczyn skalarny przez siebie , czyli pomnożenie transponowanego
przez siebie. I wtedy mamy ładne przejście do form macierzowych.
Natomiast nic takiego nie zachodzi dla sumy wyższych potęg.
J.F.
2020-12-07 16:31:07 UTC
Permalink
Użytkownik "Borneq" napisał w wiadomości grup
Post by Borneq
Post by Borneq
E = Av -Y
To nic nowego, tylko oryginalne równania zapisane macierzowo.
Chcemy aby druga norma E była możliwie najmniejsza. Metod jest
parę, dla niewielkich danych wystarczy równane normalne - można
udowodnić, że v daje najmniejsze E, gdy v spełnia równania
A^tA v = A^tY
w https://global.oup.com/booksites/content/0199268010/samplesec3
wyprowadzenie wzoru zaznaczonego tam jako (3.9)
nie bardzo wiem, dlaczego x_i=1 dla każdego i na początku
wyprowadzenia.
Popatrz na wzor 3.1 - zakladaja, ze jest tam "wyraz wolny " beta1.

Aby odzwierciedlic to w rachunku macierzowym (3.2), musieli do
wektorow X dorzucic fikcyjna wartosc 1.


Tak jak na to patrze ... to sie zastanawiam, czy te macierze
upraszczaja, czy utrudniaja :-)

J.
bartekltg
2021-01-20 14:30:49 UTC
Permalink
Użytkownik "Borneq" napisał w wiadomości grup
Post by Borneq
w https://global.oup.com/booksites/content/0199268010/samplesec3
wyprowadzenie wzoru zaznaczonego tam jako (3.9)
nie bardzo wiem, dlaczego x_i=1 dla każdego i na początku
wyprowadzenia.
Popatrz na wzor 3.1 - zakladaja, ze jest tam "wyraz wolny " beta1.
Aby odzwierciedlic to w rachunku macierzowym (3.2), musieli do
wektorow X dorzucic fikcyjna wartosc 1.
Tak jak na to patrze ... to sie zastanawiam, czy te macierze
upraszczaja, czy utrudniaja :-)
Macierze w tamtym dowodzie troszkę uprazczają zapis.
Prawdziwa siłą siedzi w interpretacji geometrycznej.

Mamy punkt Y i chcemy go przybliżyć przez
Av
gdzie v to wektor naszych parametrów, a A to amceirz z danymi.

Czyli minimalizować normę E = Y-Av.

Ale co to jest Y? Punkt w jakimś R^m.
Co to jest Av.
Dla konkretnego v też punkt. Ale jeśli pomyślimy
o wszystkich możliwych v (v zyje sobie w jakiom s R^n)
to zbiór wszytkich Av, nzawijmy go H (Sciśle pisząc: H= {Av : v \in R^n })
będzie tworzył jakąś n wymiarową*) podprzestrzeń
(powierzchnię) w naszej R^m

Nasze zagadnienie sprowadza się wiec do znalezienia
takeigo punktu na H, który jest najblizęj Y.

Naj znaleść punkt na płaszczyźnie, który jest najbliżej jakeigoś
punkty Y (poza płaszczyzną). W przypadku gdy lioczymy
odległość euklidesowsko, wektor od Y do optymalnego punktu
musi być prostopadły do tej płaszczyzny.

Czyli (oznaczając v* jakoi optymalne v) v* musi spełniać
Av* - Y _|_ H

H jest rozpięte przez kolumny A. Oznaczmy je a_i
Czyli wektor w jest prostopadły do podprzestrzeni H gdy
w jest prostopadły do każdego a_i.
Czyli a_i^t * w = 0
Zamiast pisać to dla każego i to samo mozna zspisać masowo:
A^t * w = 0

Czyli naszym warunkiem jest A^t * (Av* - Y) = 0

I tak bez jednego wzorku, tylko geometrią liniową, dostaliśmy
rówananie normalne. W dodatku w miarę intuicyjnie.

pzdr
bartekltg
bartekltg
2021-01-20 14:54:03 UTC
Permalink
Post by Borneq
Zwłaszcza fragment
E = Av -Y
To nic nowego, tylko oryginalne równania zapisane macierzowo. Chcemy aby
druga norma E była możliwie najmniejsza. Metod jest parę, dla
niewielkich danych wystarczy równane normalne - można udowodnić, że v
daje najmniejsze E, gdy v spełnia równania
A^tA v = A^tY
Co gdy chcemy by zamiast drugiej normy E minimalizować trzecią , czwartą
i większą normę?
Jak obliczyć wektor v?
Jak się do tego zabrać? Gdyby było równanie, można by je obliczyć
wielowymiarowym Newtonem, być może jako punkt początkowy przyjmując
wynik dla minimalizacji drugiej normy.
Łatwość obliczenia elementu optymalnego dla drugeij normy wynika
jednak z tej postaci (i od razu daje ładną interpretację geometryczną).

Tej interpretacji nie widać dla innych p-norm.

Jeśli rozpiszemy sumę kwadratów dla Av-Y mamy
jakieś wyrażenie kwadratowe (wzglęm parametrów).
Różniczkujac (i przyrównując do zera, bo chcemy znaleść maksimum)
je po parametrach dostajemy zestaw równań liniowych.
Identyczny jak w geometrycznie wyprowadzonym równaniu normalnym.


Dla 3 stopnia nasza funkcja ktorą minimalizujemy to suma tego typu składników:
| -y_1+v_1 a_{1,1}+v_2 a_{1,2}+v_3 a_{1,3}| ^3
(zwróć uwagę na wymagana wartość bezwzględną! Dla parzystych poteg przynajmniej jej nie ma).

Teraz to różniczkując nie dość, że dostajesz równania w potędze p-1 względem
paremetrów, to jeszcze dna nieparzytych psiedzą tam funkcje znaku tego co
pod nawiasem. Rozwiązania analitycznego nie będzie.

Ale można minimalizować. Zagoadnienie jest wypukłe, wiec dość wdzięczne do tego.
Jeśli liczba parematrów niw jest za wielka, metoda Newtona (będzie trzeba Hesjan policzyć),
jeśli nie, są metody newtonopodobne które sobie przyblizony hesjan budują.

Można też siegnać po algorytmy z programowania wypukłego/stożkowego.
Albo nawet dedykowane do optymalizowania p-normy.
https://www.researchgate.net/publication/2784232_An_efficient_algorithm_for_minimizing_a_sum_of_pnorms_SIAM
(trzeba kliknać download)

Tak czy inaczej, zamiast rozwiązania wprost dostajemy algorytm iteracyjny,
jak ładnie zbiegajacy zależy od zagadnienia i oczywiście wymiaru.
I tak jest łatwiej niż przy próbie optymalizacji L1 czy nawet
dla pseudonorm Lp z 0<p<1.


pzdr
bartekltg

Loading...