Adaptacja Gaussa - Gaussian adaptation

Adaptacja Gaussa (GA) , zwana także adaptacją normalną lub naturalną (NA), jest algorytmem ewolucyjnym zaprojektowanym w celu maksymalizacji wydajności produkcji w wyniku odchylenia statystycznego wartości składowych systemów przetwarzania sygnałów . Krótko mówiąc, GA jest stochastycznym procesem adaptacyjnym, w którym liczba próbek n- wymiarowego wektora x [ x ^T = ( x ₁ , x ₂ , ..., x _n )] jest pobieranych z wielowymiarowego rozkładu Gaussa , N ( m , m ) o średniej m i momentu macierzy m . Próbki są testowane pod kątem negatywnego lub pozytywnego wyniku. Momenty Gaussa pierwszego i drugiego rzędu ograniczone do próbek przebiegu to m * i M * .

Wynik x jako próbki pozytywnej jest określany przez funkcję s ( x ), 0 < s ( x ) < q ≤ 1, tak że s ( x ) jest prawdopodobieństwem, że x zostanie wybrane jako próbka pozytywna. Średnie prawdopodobieństwo znalezienia próbek pozytywnych (wydajność) wynosi

{\ Displaystyle P (m) = \ int s (x) N (xm) \, dx}

Wtedy twierdzenie GA stwierdza:

Dla dowolnego s ( x ) i dla dowolnej wartości P < q zawsze istnieje Gaussowski pdf [ funkcja gęstości prawdopodobieństwa ], która jest dostosowana do maksymalnego rozproszenia. Warunkiem koniecznym dla lokalnego optimum są m = m * i M proporcjonalne do M *. Problem podwójny również został rozwiązany: P jest maksymalizowane przy zachowaniu stałej dyspersji (Kjellström, 1991).

Dowody tego twierdzenia można znaleźć w pracach Kjellströma, 1970 i Kjellström & Taxén, 1981.

Ponieważ dyspersja jest zdefiniowana jako wykładniczy entropii / nieporządku / średniej informacji , natychmiast wynika, że twierdzenie to jest ważne również dla tych pojęć. W sumie oznacza to, że adaptacja Gaussa może przeprowadzać jednoczesną maksymalizację plonu i informacji o średniej (bez potrzeby definiowania plonu lub informacji średniej jako funkcji kryterialnych).

Twierdzenie jest ważne dla wszystkich obszarów dopuszczalności i wszystkich rozkładów Gaussa . Może być używany przez cykliczne powtarzanie losowych odchyleń i selekcji (podobnie jak naturalna ewolucja). W każdym cyklu dostatecznie duża liczba punktów rozproszonych Gaussa jest pobierana i testowana pod kątem przynależności do obszaru akceptowalności. Środek ciężkości Gaussa, m , jest następnie przesuwany do środka ciężkości zatwierdzonych (wybranych) punktów, m *. Zatem proces zbiega się do stanu równowagi spełniającego twierdzenie. Rozwiązanie jest zawsze przybliżone, ponieważ środek ciężkości jest zawsze określany dla ograniczonej liczby punktów.

Został użyty po raz pierwszy w 1969 roku jako czysty algorytm optymalizacyjny zmniejszający i zmniejszający obszary akceptowalności (analogicznie do symulowanego wyżarzania , Kirkpatrick 1983). Od 1970 roku jest używany zarówno do zwykłej optymalizacji, jak i maksymalizacji wydajności.

Ewolucja naturalna i adaptacja Gaussa

Porównano ją również z naturalną ewolucją populacji organizmów żywych. W tym przypadku s ( x ) jest prawdopodobieństwem, że osobnik mający szereg x fenotypów przeżyje, dając potomstwo następnemu pokoleniu; definicja przystosowania indywidualnego podana przez Hartla 1981. Plon, P , zostaje zastąpiony przez średnią przystosowanie określone jako średnia ze zbioru osobników w dużej populacji.

Fenotypy są często rozmieszczone w dużej populacji Gaussa, a warunkiem koniecznym, aby naturalna ewolucja była w stanie spełnić twierdzenie o adaptacji Gaussa, w odniesieniu do wszystkich cech ilościowych Gaussa, jest to, że może ona przesunąć środek ciężkości gaussa do punktu środek ciężkości wybranych osobników. Można tego dokonać na mocy prawa Hardy'ego-Weinberga . Jest to możliwe, ponieważ twierdzenie o adaptacji Gaussa obowiązuje dla każdego regionu akceptowalności niezależnego od struktury (Kjellström, 1996).

W tym przypadku zasady zmienności genetycznej, takie jak krzyżowanie, inwersja, transpozycja itp., Mogą być postrzegane jako generatory liczb losowych dla fenotypów. Zatem w tym sensie adaptację Gaussa można postrzegać jako algorytm genetyczny.

Jak wspiąć się na górę

Średnią przydatność można obliczyć pod warunkiem, że znany jest rozkład parametrów i struktura krajobrazu. Rzeczywisty krajobraz nie jest znany, ale poniższy rysunek przedstawia fikcyjny profil (niebieski) krajobrazu wzdłuż linii (x) w pomieszczeniu obejmującym takie parametry. Czerwona krzywa to średnia oparta na czerwonej krzywej dzwonowej u dołu rysunku. Uzyskuje się ją, przesuwając krzywą dzwonową wzdłuż osi x , obliczając średnią w każdym miejscu. Jak widać, wygładzane są małe szczyty i wgłębienia. Tak więc, jeśli ewolucja rozpocznie się w punkcie A ze stosunkowo niewielką wariancją (czerwona krzywa dzwonowa), wówczas wspinanie się będzie odbywać się na czerwonej krzywej. Proces może utknąć na miliony lat w B lub C, o ile pozostają wgłębienia po prawej stronie tych punktów, a współczynnik mutacji jest zbyt mały.

Jeśli wskaźnik mutacji jest wystarczająco wysoki, zaburzenie lub wariancja może wzrosnąć, a parametr (y) mogą zostać rozłożone jak krzywa zielonego dzwonka. Wtedy wspinaczka odbędzie się po zielonej krzywej, która jest jeszcze bardziej wygładzona. Ponieważ zagłębienia na prawo od B i C zniknęły, proces może trwać aż do szczytów w D. Ale oczywiście krajobraz ogranicza nieuporządkowanie lub zmienność. Poza tym - w zależności od krajobrazu - proces może stać się bardzo gwałtowny, a jeśli stosunek czasu spędzonego przez proces na lokalnym szczycie do czasu przejścia do następnego szczytu jest bardzo duży, równie dobrze może wyglądać jak przerywany równowaga sugerowana przez Goulda (patrz Ridley).

Symulacja komputerowa adaptacji Gaussa

Jak dotąd teoria bierze pod uwagę tylko średnie wartości ciągłych rozkładów odpowiadających nieskończonej liczbie osobników. W rzeczywistości jednak liczba osobników jest zawsze ograniczona, co powoduje niepewność przy szacowaniu m i M (macierz moment Gaussa). Może to również wpłynąć na efektywność procesu. Niestety, niewiele wiadomo na ten temat, przynajmniej teoretycznie.

Wdrożenie normalnej adaptacji na komputerze jest dość prostym zadaniem. Adaptacja m może być przeprowadzona na przykład przez jedną próbkę (indywidualną) na raz

m ( i + 1) = (1 - a ) m ( i ) + ax

gdzie x jest próbą pozytywną, a a <1 odpowiednią stałą, tak że odwrotność a reprezentuje liczbę osobników w populacji.

Zasadniczo M można aktualizować po każdym kroku y prowadzącym do wykonalnego punktu

x = m + y według:

M ( i + 1) = (1 - 2 b ) M ( i ) + 2 byy ^T ,

gdzie y ^T jest transpozycją y i b << 1 to kolejna odpowiednia stała. Aby zapewnić odpowiedni wzrost średniej informacji , y powinien mieć rozkład normalny z macierzą momentu μ ² M , gdzie skalar μ > 1 służy do zwiększania średniej informacji ( entropia informacyjna , nieporządek, różnorodność) w odpowiednim tempie. Ale M nigdy nie zostanie użyte w obliczeniach. Zamiast korzystania z osnową W określonej przez WW ^T = M .

Zatem mamy y = Wg , gdzie g ma rozkład normalny z macierzą momentu μU , a U to macierz jednostkowa. W i W ^T można zaktualizować za pomocą wzorów

W = (1 - b ) W + byg ^T i W ^T = (1 - b ) W ^T + bgy ^T

bo mnożenie daje

M = (1 - 2 b ) M + 2 byy ^T ,

gdzie terminy zawierające b ² zostały pominięte. Zatem M zostanie pośrednio zaadaptowane z dobrym przybliżeniem. W praktyce wystarczy zaktualizować tylko W.

W ( i + 1) = (1 - b ) W ( I ) + byg ^T .

To jest wzór zastosowany w prostym dwuwymiarowym modelu mózgu spełniającym hebbijską regułę uczenia się asocjacyjnego; patrz następny rozdział (Kjellström, 1996 i 1999).

Poniższy rysunek ilustruje efekt zwiększonej średniej informacji w pliku PDF Gaussa używanym do wspinania się na szczyt góry (dwie linie reprezentują linię konturu). Zarówno klaster czerwony, jak i zielony mają taką samą średnią przydatność, około 65%, ale klaster zielony ma znacznie wyższe średnie informacje, dzięki czemu zielony proces jest znacznie bardziej wydajny. Efekt tej adaptacji nie jest zbyt wyraźny w przypadku dwuwymiarowym, ale w przypadku o dużym wymiarze wydajność procesu wyszukiwania może zostać zwiększona o wiele rzędów wielkości.

Ewolucja w mózgu

W mózgu ewolucja wiadomości DNA ma zostać zastąpiona ewolucją wzorców sygnałowych, a krajobraz fenotypowy zostaje zastąpiony krajobrazem mentalnym, którego złożoność nie ustępuje pierwszemu. Metafora z krajobrazem mentalnym opiera się na założeniu, że pewne wzorce sygnałów prowadzą do lepszego samopoczucia lub wydajności. Na przykład kontrola grupy mięśni prowadzi do lepszej wymowy słowa lub wykonania utworu muzycznego.

W tym prostym modelu zakłada się, że mózg składa się z połączonych ze sobą komponentów, które mogą dodawać, zwielokrotniać i opóźniać wartości sygnału.

Jądro komórki nerwowej może dodawać wartości sygnału,
synapsa może się rozmnażać ze stałą i
Akson może opóźniać wartości.

Stanowi to podstawę teorii filtrów cyfrowych i sieci neuronowych składających się z komponentów, które mogą dodawać, zwielokrotniać i opóźniać wartości sygnału, a także wielu modeli mózgu, Levine 1991.

Na poniższym rysunku pień mózgu ma dostarczać rozproszone wzorce sygnału Gaussa. Może to być możliwe, ponieważ niektóre neurony odpalają się losowo (Kandel et al.). Trzon stanowi również nieuporządkowaną strukturę otoczoną bardziej uporządkowanymi powłokami (Bergström, 1969), a zgodnie z centralnym twierdzeniem granicznym suma sygnałów z wielu neuronów może mieć rozkład Gaussa. Trójkątne prostokąty reprezentują synapsy, a pola ze znakiem + to jądra komórek.

W korze sygnały mają być testowane pod kątem wykonalności. Po przyjęciu sygnału obszary stykowe w synapsach są aktualizowane zgodnie z poniższymi wzorami, zgodnie z teorią Hebba. Rysunek przedstawia dwuwymiarową symulację komputerową adaptacji Gaussa według ostatniego wzoru z poprzedniej sekcji.

m i W są aktualizowane zgodnie z:

m ₁ = 0,9 m ₁ + 0,1 x 1; m ₂ = 0,9 m ₂ + 0,1 x ₂ ;

w ₁₁ = 0,9 w ₁₁ + 0,1 y ₁ g ₁ ; w ₁₂ = 0,9 w ₁₂ + 0,1 y ₁ g ₂ ;

w ₂₁ = 0,9 w ₂₁ + 0,1 y ₂ g ₁ ; w ₂₂ = 0,9 w ₂₂ + 0,1 y ₂ g ₂ ;

Jak widać, jest to bardzo podobne do małego mózgu rządzonego przez teorię uczenia się Hebbów (Kjellström, 1996, 1999 i 2002).

Adaptacja Gaussa i wolna wola

Adaptacja Gaussa jako ewolucyjny model mózgu zgodny z hebbijską teorią uczenia się asocjacyjnego oferuje alternatywne spojrzenie na wolną wolę ze względu na zdolność procesu do maksymalizacji średniej sprawności wzorców sygnałowych w mózgu poprzez wspinanie się po krajobrazie mentalnym analogicznie do fenotypowego. ewolucja.

Taki przypadkowy proces daje nam dużą swobodę wyboru, ale prawie żadnej woli. Złudzenie woli może jednak emanować ze zdolności procesu do maksymalizacji średniej sprawności, co sprawia, że proces dąży do celu. To znaczy, preferuje wyższe szczyty w krajobrazie przed niższymi lub lepszymi alternatywami przed gorszymi. W ten sposób może pojawić się iluzja. Podobny pogląd przedstawił Zohar 1990. Zobacz także Kjellström 1999.

Twierdzenie o efektywności wyszukiwania losowego

Skuteczność adaptacji Gaussa opiera się na teorii informacji należnej Claude E. Shannonowi (patrz treść informacji ). Gdy zdarzenie zachodzi z prawdopodobieństwem P , wówczas może zostać osiągnięty dziennik informacji ( P ). Na przykład, jeżeli średnia fitness jest P , informacje uzyskane za każdy poszczególny wybrany do przetrwania będzie -log ( P ) - na średni - a praca / czas potrzebny na uzyskanie informacji jest proporcjonalna do 1 / P . Tak więc, jeśli wydajność, E, jest zdefiniowana jako informacja podzielona przez pracę / czas potrzebny na jej uzyskanie, to mamy:

E = - P log ( P ).

Ta funkcja osiąga swoje maksimum, gdy P = 1 / e = 0,37. Ten sam wynik uzyskał Gaines inną metodą.

E = 0, jeśli P = 0, dla procesu z nieskończoną częstością mutacji, a jeśli P = 1, dla procesu z częstością mutacji = 0 (pod warunkiem, że proces jest aktywny). Ta miara wydajności jest ważna dla dużej klasy losowych procesów wyszukiwania , pod warunkiem spełnienia określonych warunków.

1 Poszukiwanie powinno być statystycznie niezależne i równie skuteczne w różnych kierunkach parametrów. Warunek ten może być w przybliżeniu spełniony, gdy macierz momentu Gaussa zostanie zaadaptowana dla maksymalnej średniej informacji do jakiegoś obszaru akceptowalności, ponieważ liniowe przekształcenia całego procesu nie wpływają na wydajność.

2 Wszystkie osoby mają jednakowy koszt, a pochodna przy P = 1 wynosi <0.

Wówczas można udowodnić następujące twierdzenie:

Wszystkie miary wydajności, które spełniają powyższe warunki, są asymptotycznie proporcjonalne do - P log ( P / q ), gdy liczba wymiarów wzrasta i są maksymalizowane przez P = q exp (-1) (Kjellström, 1996 i 1999).

Powyższy rysunek przedstawia możliwą funkcję wydajności dla losowego procesu wyszukiwania, takiego jak adaptacja Gaussa. Po lewej stronie proces jest najbardziej chaotyczny, gdy P = 0, podczas gdy po prawej stronie jest idealny porządek, gdzie P = 1.

W przykładzie z Rechenberg, 1971, 1973, losowy spacer jest przepychany przez korytarz, maksymalizując parametr x ₁ . W tym przypadku obszar akceptowalności jest zdefiniowany jako ( n - 1) -wymiarowy przedział w parametrach x ₂ , x ₃ , ..., x _n , ale wartość x ₁ poniżej ostatnio zaakceptowanej wartości nigdy nie zostanie zaakceptowana. Ponieważ P nigdy nie może przekroczyć 0,5 w tym przypadku, maksymalna prędkość w kierunku wyższych wartości x ₁ jest osiągana dla P = 0,5 / e = 0,18, zgodnie z ustaleniami Rechenberga.

Punkt widzenia, który również może być interesujący w tym kontekście, jest taki, że żadna definicja informacji (poza tym, że próbkowane punkty wewnątrz jakiegoś obszaru akceptowalności dają informacje o rozszerzeniu regionu) nie jest potrzebna do udowodnienia twierdzenia. Wówczas, ponieważ formuła może być zinterpretowana jako informacja podzielona przez pracę potrzebną do uzyskania informacji, jest to również wskazanie, że −log ( P ) jest dobrym kandydatem na miarę informacji.

Algorytm Stauffera i Grimsona

Adaptacja Gaussa została również wykorzystana do innych celów, na przykład do usuwania cieni przez „algorytm Stauffera-Grimsona”, który jest odpowiednikiem adaptacji Gaussa, jak użyto w sekcji „Komputerowa symulacja adaptacji Gaussa” powyżej. W obu przypadkach metoda największej wiarygodności jest używana do oszacowania średnich wartości poprzez adaptację na jednej próbie na raz.

Ale są różnice. W przypadku Stauffera-Grimsona informacja nie jest wykorzystywana do sterowania generatorem liczb losowych w celu wyśrodkowania, maksymalizacji średniej sprawności, średniej informacji lub wydajności produkcji. Adaptacja macierzy momentu również bardzo się różni w porównaniu z „ewolucją w mózgu” powyżej.

Zobacz też

Bibliografia

Bergström, RM Model entropii rozwijającego się mózgu. Developmental Psychobiology , 2 (3): 139–152, 1969.
Brooks, DR i Wiley, EO Evolution as Entropy, Towards a Unified Teoria of Biology . The University of Chicago Press, 1986.
Brooks, DR Evolution in the Information Age: Rediscovering the Nature of the Organism. Semiosis, Evolution, Energy, Development, tom 1, numer 1, marzec 2001
Gaines, Brian R. Zarządzanie wiedzą w społeczeństwach inteligentnych agentów adaptacyjnych. Journal of Intelligent Information Systems 9, 277–298 (1997).
Hartl, DL A Elementarz genetyki populacji . Sinauer, Sunderland, Massachusetts, 1981.
Hamilton, WD. 1963. Ewolucja zachowań altruistycznych. American Naturalist 97: 354–356
Kandel, ER, Schwartz, JH, Jessel, TM Essentials of Neural Science and Behavior . Prentice Hall International, Londyn, 1995.
S. Kirkpatrick i CD Gelatt i MP Vecchi, Optimization by Simulated Annealing, Science, tom 220, numer 4598, strony 671–680, 1983.
Kjellström, G. Optymalizacja sieci przez losową zmienność wartości składowych. Ericsson Technics , vol. 25, nie. 3, s. 133–151, 1969.
Kjellström, G. Optymalizacja sieci elektrycznych pod kątem kosztów tolerancji. Ericsson Technics , no. 3, s. 157–175, 1970.
Kjellström, G. & Taxén, L. Stochastic Optimization in System Design. IEEE Trans. na Circ. i Syst., tom. CAS-28, nr. 7 lipca 1981.
Kjellström, G., Taxén, L. i Lindberg, PO Discrete Optimization of Digital Filters Using Gaussian Adaptation and Quadratic Function Minimization. IEEE Trans. na Circ. i Syst., tom. CAS-34, nr 10, październik 1987.
Kjellström, G. On the Efficiency of Gaussian Adaptation. Journal of Optimization Theory and Applications , vol. 71, nie. 3 grudnia 1991.
Kjellström, G. & Taxén, L. Gaussian Adaptation, oparty na ewolucji wydajny globalny optymalizator; Computational and Applied Mathematics, In, C. Brezinski & U. Kulish (redaktorzy), Elsevier Science Publishers BV, str. 267–276, 1992.
Kjellström, G. Evolution jako algorytm optymalizacji statystycznej. Teoria ewolucji 11: 105–117 (styczeń 1996).
Kjellström, G. Ewolucja w mózgu. Applied Mathematics and Computation , 98 (2–3): 293–300, luty 1999.
Kjellström, G. Evolution w pigułce i niektóre konsekwencje dotyczące wycen. EVOLVE, ISBN 91-972936-1-X , Sztokholm, 2002.
Levine, DS Wprowadzenie do modelowania neuronowego i poznawczego. Laurence Erlbaum Associates, Inc., Publishers, 1991.
MacLean, PD Trójjedyna koncepcja mózgu i zachowania . Toronto, Univ. Toronto Press, 1973.
Maynard Smith, J. 1964. Group Selection and Kin Selection, Nature 201: 1145-1147.
Maynard Smith, J. Evolutionary Genetics . Oxford University Press, 1998.
Mayr, E. Czym jest ewolucja . Basic Books, Nowy Jork, 2001.
Müller, Christian L. i Sbalzarini Ivo F. Gaussian Adaptacja zrewidowana - entropijny pogląd na adaptację macierzy kowariancji. Instytut Informatyki Teoretycznej i Szwajcarski Instytut Bioinformatyki , ETH Zurich , CH-8092 Zurych, Szwajcaria.
Pinel, JF i Singhal, K. Statystyczne wyśrodkowanie i tolerancja projektowania przy użyciu próbkowania parametrycznego. Transakcje IEEE na obwodach i systemach, tom. Das-28, nr 7, lipiec 1981.
Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (praca doktorska). Przedrukowany przez Fromman-Holzboog (1973).
Ridley, M. Evolution . Blackwell Science, 1996.
Stauffer, C. & Grimson, WEL Learning Patterns of Activity Using Real-Time Tracking, IEEE Trans. na PAMI, 22 (8), 2000.
Stehr, G. On the Performance Space Exploration of Analog Integrated Circuits. Technischen Universität Munchen, Dissertation 2005.
Taxén, L. Ramy koordynacji rozwoju złożonych systemów. Institute of Technology, Linköping University, Dissertation, 2003.
Zohar, D. Jaźń kwantowa: rewolucyjny pogląd na ludzką naturę i świadomość zakorzenioną w nowej fizyce . Londyn, Bloomsbury, 1990.

Languages

In other projects