On 22 Lip, 18:41, "Borneq" <b...@a...hidden.pl> wrote:
> Użytkownik "Segmentation Fault" <c...@o...eu> napisał w
> wiadomościnews:4c4854cc$0$19182$65785112@news.neostr
ada.pl...
>
> >> A nie możesz policzyć dyskretnej pochodnej?
> > Numerycznej miało być
Pewnie kolega może policzyć, ale numeryczna pochodna zaprzepaszcza
szybkość i dokładność jaką dają algorytmy gradientowe.

> Szybko liczy metoda najszybszego spadku ale nie wiadomo jaki współczynnik
> alfa dobrać.
Współczynnik coraz mniejszy. Zaczynasz np. od 1 i co iteracje dajesz
np.
alpha = alpha * 0.999.

Możesz też w każdej iteracji dobierać adaptacyjnie długość kroku.

np tak:

error = eval( parametry[] );
g[] = gradient();
norm = norma( n );
if( norm < 0.000001 ) koniec;
step = 0.1;
sum_step = 0;
kopia[] = parametry[];
while( fabs(step) > 0.000001 && fabs(sum_step) < 1.0 ) {
parametry[1..n] = parametry[1..n] -gradient[1..n] / norm * step;
tmp = eval( parametry[] );
if( tmp < error ) {
error = tmp;
sum_step += step;
step = step * +2;
kopia[] = parametry[];
} else {
parametry[] = kopia;
step = step / -2;
}
}

Pozdrawiam

do góry

On 07/22/2010 10:53 PM, Mariusz Marszałkowski wrote:
> On 22 Lip, 18:41, "Borneq" <b...@a...hidden.pl> wrote:
>> Użytkownik "Segmentation Fault" <c...@o...eu> napisał w
>> wiadomościnews:4c4854cc$0$19182$65785112@news.neostr
ada.pl...
>>
>>>> A nie możesz policzyć dyskretnej pochodnej?
>>> Numerycznej miało być
> Pewnie kolega może policzyć, ale numeryczna pochodna zaprzepaszcza
> szybkość i dokładność jaką dają algorytmy gradientowe.
>

Dlaczego zaprzepaszcza ?

Powiedział bym, że dla wielu funkcji nie ma istotnego wpływu na szybkość
( w sensie ilości iteracji i czasu jednej iteracji).

do góry

On 22 Lip, 23:31, Segmentation Fault <c...@o...eu> wrote:
> On 07/22/2010 10:53 PM, Mariusz Marszałkowski wrote:
>
> > On 22 Lip, 18:41, "Borneq" <b...@a...hidden.pl> wrote:
> >> Użytkownik "Segmentation Fault" <c...@o...eu> napisał w
> >> wiadomościnews:4c4854cc$0$19182$65785112@news.neostr
ada.pl...
>
> >>>> A nie możesz policzyć dyskretnej pochodnej?
> >>> Numerycznej miało być
> > Pewnie kolega może policzyć, ale numeryczna pochodna zaprzepaszcza
> > szybkość i dokładność jaką dają algorytmy gradientowe.
>
> Dlaczego zaprzepaszcza ?
> Powiedział bym, że dla wielu funkcji nie ma istotnego wpływu na szybkość
> ( w sensie ilości iteracji i czasu jednej iteracji).
Ilość iteracji się zwiększa, bo pochodna bywa naliczana niedokładnie.
Czas
jednej iteracji się wydłuża, bo jak optymalizujesz 100 parametrów, to
musisz wywołać 100 razy optymalizowaną funkcję aby ustalić
pochodną dla każdego parametru.

Pozdrawiam

do góry

slawek pisze:
>
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w
> wiadomości grup
> dyskusyjnych:99ca78d6-5bcd-4a25-8c58-bc3efa80e922@e5
g2000yqn.googlegroups.com...
>
>> Już czytałem nie jedno, więcej nie dam się nabrać :) Podejrzewam że
>
> Szukamy ekstremum globalnego. Mamy do wyboru algorytmy: losowe,
> gradientowe, sympleks, studzenie, genetyczne. Czy coś pominąłem?
>
> Powtórzenie obliczeń algorytmem tej samej klasy da przypuszczalnie to
> samo minimum lokalne. A tego nie chcemy.
Dla dobrze napisanego algorytmu - rzadko, chyba, że to minimum lokalne
jest w gruncie rzeczy dość dobre.

> Różne mogą być funkcje i dla
> niektórych algorytm genetyczny może być lepszy. Ponadto genetyczny
> nieźle się paralelizuje chyba. Daje radę ze zmiennymi dyskretnymi.
Pominąłeś takie metaheurystyki jak "kontrolowane wyżarzanie" (chyba, że
to u Ciebie "studzenie") i tabu search.

Ztcp kontrolowane wyżarzanie daje często dobre efekty.


> Random jest zbyt drogi gdy zmienne idą do nieskończoności.
>
Algorytmy genetyczne to taki "random na sterydach". Stosowany wtedy gdy
nie da się lepszej metaheyrystyki dostosować.

--
Pozdrawiam
Michoo

do góry

On 23 Lip, 00:20, Michoo <m...@v...pl> wrote:
>
> Ztcp kontrolowane wyżarzanie daje często dobre efekty.
W ogólnym przypadku chyba daje lepsze efekty niż AG.

> > Random jest zbyt drogi gdy zmienne idą do nieskończoności.
>
> Algorytmy genetyczne to taki "random na sterydach". Stosowany wtedy gdy
> nie da się lepszej metaheyrystyki dostosować.
Niestety to jest prawda. Jeśli nie uda się znaleźć dobrego sposobu
kodowania i krzyżowania osobników to lepiej nie używać AG.

Pozdrawiam

do góry

Użytkownik "Borneq" <b...@a...hidden.pl> napisał w wiadomości
news:i29sbf$nnt$1@news.onet.pl...
> Szybko liczy metoda najszybszego spadku ale nie wiadomo jaki współczynnik
> alfa dobrać.

Można według
http://www.ikb.poznan.pl/zaklady/komp/dydaktyka/mate
rialy/metobl/w2.pdf
strona 37
Minimalizujemy h szukając minimum jednowymiarowego np. metodą Newtona dla
minimów:
xk+1 = xk-f'(xk)/f''(xk) dzieląc pierwszą pochodną przez drugą

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
grup
dyskusyjnych:c83c0c55-71ab-44d6-a1c6-f372ebb3f108@j8
g2000yqd.googlegroups.com...
> Ilość iteracji się zwiększa, bo pochodna bywa naliczana niedokładnie.

Numeryczna aproksymacja gradientu z wartości funkcji niekoniecznie jest
mniej wartościowa w porównaniu z gradientem wydzierganym analitycznie.

> Czas
> jednej iteracji się wydłuża, bo jak optymalizujesz 100 parametrów, to
> musisz wywołać 100 razy optymalizowaną funkcję aby ustalić
> pochodną dla każdego parametru.

Bynajmniej. Ulegasz błędnemu mitowi wyższości "ścisłych" rozwiązań.

Analitycznie liczysz 100 pochodnych cząstkowych, masz średnio dwa razy
dłuższy (liczba operacji) wzór na każdą w porównaniu z samą funkcją. I to
jak dobrze będzie, bo może być nawet znacznie bardziej złożony, policz np.
f'(x) = (d/dx) (sin(x)sin(a x)sin(b x)sin(c sin(p sin(q x)))

Numerycznie liczysz funkcję 1 raz i jeszcze 100 razy, razem 101 razy. Ale
masz z reguły dużo prostsze wzory niż na pochodne cząstkowe. Więc ten 1%
narzutu nie znaczy.

slawek

do góry

Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
grup
dyskusyjnych:a47db692-d3da-4fef-b019-aa9a75b6c3ed@w3
1g2000yqb.googlegroups.com...
> Zgoda że AG ma szanse wypaść najlepiej, ale dopiero gdy to będzie
> baaaardzo
> trudna funkcja. Dopiero gdy to będzie taka funkcja, że zmiana jednego
> bitu będzie
> powodowała bardzo duże wahanie wartości funkcji.

Wystarczy logarytmiczna funkcja wiarygodności. W aplikacji do konkretnych
problemów powstaje z funkcji występujących w danych zagadnieniach, a jak
wiadomo zagadnienia są różne.

> W przypadku gładkich funkcji jednomodalnych zawsze lepiej wypadnie

Acha... a jak uprosić aby funkcja wiarygodności była jednomodalna?

Ja wiem, najlepiej strzyże się łysych.

> Zastosowanie AG to ostateczność, gdy nic innego nie działa.

Nie.

slawek

do góry

Użytkownik "Michoo" <m...@v...pl> napisał w wiadomości grup
dyskusyjnych:i2ag5r$eu2$...@n...onet.pl...
> Dla dobrze napisanego algorytmu - rzadko, chyba, że to minimum lokalne
> jest w gruncie rzeczy dość dobre.

Zdefiniuj "dobrze napisany algorytm".

Zdefiniuj "dość dobre minimum".

> Algorytmy genetyczne to taki "random na sterydach". Stosowany wtedy gdy
> nie da się lepszej metaheyrystyki dostosować.

Niezupełnie.

slawek

do góry

On 26 Lip, 15:21, "slawek" <s...@h...pl> wrote:
> Użytkownik "Mariusz Marszałkowski" <m...@g...com> napisał w wiadomości
> grup
> dyskusyjnych:c83c0c55-71ab-44d6-a1c6-f372ebb3f...@j8
g2000yqd.googlegroups.com...
>
> > Ilość iteracji się zwiększa, bo pochodna bywa naliczana niedokładnie.
>
> Numeryczna aproksymacja gradientu z wartości funkcji niekoniecznie jest
> mniej wartościowa w porównaniu z gradientem wydzierganym analitycznie.
>
> > Czas
> > jednej iteracji się wydłuża, bo jak optymalizujesz 100 parametrów, to
> > musisz wywołać 100 razy optymalizowaną funkcję aby ustalić
> > pochodną dla każdego parametru.
>
> Bynajmniej. Ulegasz błędnemu mitowi wyższości "ścisłych" rozwiązań.
>
> Analitycznie liczysz 100 pochodnych cząstkowych, masz średnio dwa razy
> dłuższy (liczba operacji) wzór na każdą w porównaniu z samą funkcją. I to
> jak dobrze będzie, bo może być nawet znacznie bardziej złożony, policz np.
> f'(x) = (d/dx) (sin(x)sin(a x)sin(b x)sin(c sin(p sin(q x)))
Zależy jaka funkcja. W sieciach neuronowych liczę 1000 pochodnych
cząstkowych
tak samo szybko jak 1-2 razy funkcję celu.

> Numerycznie liczysz funkcję 1 raz i jeszcze 100 razy, razem 101 razy. Ale
> masz z reguły dużo prostsze wzory niż na pochodne cząstkowe. Więc ten 1%
> narzutu nie znaczy.
Nie wiem jak się zdarza częściej, chyba częściej dobrze
zoptymalizowany wzór
na pochodne jest prostszy.

Pozdrawiam

do góry