WSTĘP

Ograniczenia pojawiają się w wielu dziedzinach ludzkiej działalności, począwszy od łamigłówek takich jak krzyżówki (słowa mogą się nakładać tylko na tę samą literę) i ostatnio popularnego Sudoku (żadna liczba nie pojawia się dwa razy z rzędu), poprzez codzienne problemy, takie jak planowanie spotkań (sala konferencyjna musi pomieścić wszystkich uczestników), aż po rozwiązywanie trudnych problemów optymalizacyjnych, na przykład w harmonogramowaniu produkcji (zadanie musi się zakończyć przed innym). Chociaż wszystkie te problemy wydają się pochodzić z zupełnie innych światów, wszystkie mają podobną podstawę - zadaniem jest znalezienie wartości zmiennych decyzyjnych, takich jak czas rozpoczęcia zadania lub pozycja liczby na tablicy, z uwzględnieniem danych ograniczeń. Problem ten nazywa się problemem spełnienia ograniczeń (Constraint Satisfaction Problem - CSP). Przetwarzanie z ograniczeniami pojawiło się w badaniach nad sztuczną inteligencją w latach 70. XX wieku , kiedy badano takie problemy, jak etykietowanie scen . Celem etykietowania scen było rozpoznanie typu linii (a następnie typu obiektu) na dwuwymiarowym obrazie sceny trójwymiarowej. Możliwe typy to linie wypukłe, wklęsłe i zasłaniające, a kombinacja typów była ograniczona na skrzyżowaniach linii, aby była fizycznie wykonalna. Ten problem etykietowania scen jest prawdopodobnie pierwszym problemem sformalizowanym jako CSP, a niektóre techniki opracowane do jego rozwiązania, a mianowicie spójność łukowa, nadal stanowią rdzeń przetwarzania ograniczeń. Systematyczne wykorzystanie ograniczeń w systemach programowania rozpoczęło się w latach 80. XX wieku, kiedy naukowcy zidentyfikowali podobieństwo między unifikacją w programowaniu logicznym a spełnianiem ograniczeń. Tak narodziło się programowanie logiki ograniczeń. Obecnie programowanie ograniczeń jest odrębną dziedziną, niezależną od języka programowania, choć programowanie logiki ograniczeń nadal odgrywa ważną rolę dzięki naturalnej integracji ograniczeń w ramach programowania logicznego. W niniejszym artykule przedstawiono główne techniki rozwiązywania problemów spełniania ograniczeń. Techniki te są bardziej zaawansowane niż obecnie stosowane rozwiązania ograniczeń, a ich zrozumienie jest ważne dla pełnego wykorzystania dostępnej technologii.

TŁO

Problem spełniania ograniczeń jest formalnie definiowany jako trójka: skończony zbiór zmiennych decyzyjnych, dziedzina możliwych wartości oraz skończony zbiór ograniczeń ograniczających możliwe kombinacje wartości, które można przypisać zmiennym. Chociaż dziedzina może być nieskończona, na przykład liczby rzeczywiste, często zakłada się dziedzinę skończoną. Bez utraty ogólności, dziedzinę skończoną można odwzorować na zbiór liczb całkowitych, co jest typowym przypadkiem w solverach ograniczeń. Niniejszy artykuł dotyczy wyłącznie dziedzin skończonych. W wielu problemach każda zmienna ma swoją własną dziedzinę, która jest podzbiorem dziedziny z definicji problemu. Taka dziedzina może być formalnie zdefiniowana za pomocą ograniczenia unarnego. Wspomnieliśmy już, że ograniczenia ograniczają możliwe kombinacje wartości, jakie mogą przyjmować zmienne decyzyjne. Zazwyczaj ograniczenie jest definiowane dla podzbioru zmiennych, jego zakresu, i jest określone albo ekstensywnie, jako zbiór krotek wartości spełniających ograniczenie, albo celowo, za pomocą formuły logicznej lub arytmetycznej. Ta formuła, na przykład A < B, opisuje, które krotki wartości spełniają ograniczenie. Małym przykładem CSP jest ({A, B, C}, {1, 2, 3}, {A < B, B < C}). Zadaniem przetwarzania ograniczeń jest utworzenie instancji każdej zmiennej decyzyjnej za pomocą wartości z dziedziny w taki sposób, aby wszystkie ograniczenia były spełnione. Taka instancjacja nazywa się wykonalnym przypisaniem. Oczywiste jest, że problem, czy istnieje wykonalne przypisanie dla CSP, jest NP-zupełny - problemy takie jak 3SAT lub problem plecakowy można bezpośrednio zakodować jako CSP. Czasami problemowi spełnienia ograniczeń towarzyszy tak zwana funkcja celu zdefiniowana na podstawie (niektórych) zmiennych decyzyjnych, co prowadzi do problemu optymalizacji z ograniczeniami. Następnie zadaniem jest wybranie spośród wykonalnych zadań zadania, które minimalizuje (lub maksymalizuje) wartość funkcji celu. Niniejszy artykuł koncentruje się na technikach znajdowania wykonalnego zadania, ale techniki te można naturalnie rozszerzyć na problemy optymalizacyjne za pomocą znanej techniki gałęzi i ograniczeń. Istnieje wiele obszernych źródeł informacji na temat spełniania ograniczeń, począwszy od przeglądów czasopism , poprzez samouczki online, aż po kilka książek. Książka Van Hentenrycka (1989) była pionierską pracą, pokazującą spełnianie ograniczeń w kontekście programowania logicznego. Późniejsza książka Tsanga (1993) koncentruje się na technikach spełniania ograniczeń niezależnie od ram programowania i zawiera pełne szczegóły techniczne większości algorytmów opisanych w dalszej części artykułu. Najnowsze książki obejmują zarówno aspekty teoretyczne , jak i praktyczne , dostarczają dobrych materiałów dydaktycznych lub dogłębnych opracowań poszczególnych tematów (Rossi i in., 2006). Nie należy zapominać o książkach pokazujących, jak technologia spełniania ograniczeń jest stosowana w poszczególnych obszarach; problemy harmonogramowania odgrywają tu istotną rolę , ponieważ przetwarzanie ograniczeń jest w tym obszarze wyjątkowo skuteczne.

TECHNIKI SPEŁNIANIA OGRANICZEŃ

Problemy spełniania ograniczeń w domenach skończonych są zasadniczo problemami kombinatorycznymi, więc można je rozwiązać, badając przestrzeń możliwych (częściowych lub całkowitych) instancji zmiennych decyzyjnych. W dalszej części tego rozdziału przedstawimy typowe algorytmy wyszukiwania wykorzystywane w przetwarzaniu ograniczeń. Należy jednak podkreślić, że przetwarzanie ograniczeń nie jest prostą enumeracją, a także pokażemy, jak tzw. techniki spójności przyczyniają się do rozwiązywania problemów CSP.

Wyszukiwanie systematyczne

Wyszukiwanie jest podstawową technologią sztucznej inteligencji, a wiele algorytmów wyszukiwania zostało opracowanych w celu rozwiązania różnych problemów. W przypadku przetwarzania ograniczeń poszukujemy wykonalnego przypisania wartości do zmiennych, gdzie wykonalność jest zdefiniowana przez ograniczenia. Można to zrobić metodą cofania, gdzie przypisujemy wartość wybranej zmiennej i sprawdzamy, czy ograniczenia, których zakres jest już utworzona, są spełnione. W przypadku pozytywnym przechodzimy do następnej zmiennej. W przypadku negatywnym próbujemy innej wartości dla bieżącej zmiennej lub, jeśli nie ma więcej wartości, cofamy się do ostatniej utworzonej zmiennej i próbujemy tam wartości alternatywnych. Poniższy kod przedstawia szkielet tej procedury, zwanej historycznym etykietowaniem (Waltz, 1975). Należy zauważyć, że sprawdzanie spójności może przycinać domeny poszczególnych zmiennych, co zostanie omówione w następnej sekcji.

procedure labelling(V,D,C)
if all variables from V are assigned then return V
select not-yet assigned variable x from V
for each value v from Dx do
(TestOK,D′) <- consistent(V,D,C?{x=v})
if TestOK=true then
R <- labelling(V,D′,C)
if R <- fail then return R
end for
return fail
end labelling

Powyższy mechanizm backtrackingu jest parametryzowany przez heurystyki wyboru zmiennych i wartości, które decydują o kolejności instancji zmiennych oraz o kolejności próbkowania wartości. Chociaż porządkowanie wartości jest zazwyczaj zależne od problemu, a heurystyki niezależne od problemu nie są często stosowane ze względu na ich złożoność obliczeniową, istnieją popularne heurystyki porządkowania zmiennych niezależne od problemu. Porządkowanie zmiennych opiera się na tzw. zasadzie pierwszego błędu sformułowanej przez Haralicka i Eliota (1980), która mówi, że zmienna, której instancja doprowadzi do awarii z największym prawdopodobieństwem, powinna być wypróbowana jako pierwsza. Typowym przykładem tej zasady jest heurystyka dom, która preferuje zmienne o najmniejszej domenie do instancjonowania. Istnieją inne popularne heurystyki porządkowania zmiennych, takie jak dom+deg lub dom/deg, ale ich szczegółowy opis wykracza poza zakres tego krótkiego artykułu. Chociaż heurystyki wpływają (pozytywnie) na wydajność wyszukiwania, nie są w stanie rozwiązać wszystkich wad backtrackingu. Prawdopodobnie główną wadą jest ignorowanie informacji o przyczynie niewykonalności ograniczenia. Jeśli algorytm odkryje, że zmiennej nie można przypisać wartości, bezmyślnie cofa się do ostatniej instancji zmiennej, mimo że przyczyna konfliktu może leżeć gdzie indziej. Istnieją techniki takie jak backjumping, które pozwalają wykryć zmienną, której instancjacja spowodowała problem, i cofnąć się do niej (backjump). Techniki te należą do szerszej klasy inteligentnych backtrackingów, które podzielają ideę inteligentnego odzyskiwania po niewykonalności. Chociaż techniki te są interesujące i wykraczają daleko poza proste enumeracje, wydaje się, że lepiej zapobiegać niewykonalności niż ją odzyskiwać (nawet w inteligentny sposób).

Filtrowanie domeny i utrzymanie spójności

Załóżmy zmienne A i B z dziedziną {1, 2, 3} i prostym ograniczeniem A < B. Oczywiste jest, że wartość 3 nigdy nie może zostać przypisana do zmiennej A, ponieważ nie ma sposobu na spełnienie ograniczenia A < B, jeśli ta wartość jest używana dla zmiennej A. W związku z tym wartość tę można bezpiecznie usunąć z dziedziny zmiennej A i nie trzeba jej przyjmować podczas wyszukiwania. Podobnie, wartość 1 można usunąć z dziedziny zmiennej B. Ten proces nazywa się filtrowaniem domeny i jest realizowany za pomocą specjalnej procedury przypisanej do każdego ograniczenia. Filtrowanie domeny jest ściśle związane ze spójnością ograniczenia. Mówimy, że ograniczenie C jest (łuk) spójne, jeśli dla dowolnej wartości x w dziedzinie dowolnej zmiennej w zakresie C istnieją wartości w dziedzinach innych zmiennych w zakresie C takie, że krotka wartości spełnia warunek C. Taka krotka wartości nazywana jest wsparciem dla x. Filtrowanie domeny ma na celu uczynienie ograniczenia spójnym poprzez usunięcie wartości, które nie mają wsparcia. Filtrowanie dziedzinowe można zastosować do wszystkich ograniczeń w problemie, aby usunąć nieobsługiwane wartości z dziedzin zmiennych i zapewnić spójność całego problemu. Ponieważ ograniczenia są ze sobą powiązane, może być konieczne powtórzenie filtrowania dziedzinowego ograniczenia C, jeśli inne ograniczenie przycięło dziedzinę zmiennej w zakresie C. Zasadniczo filtrowanie dziedzinowe jest powtarzane do momentu osiągnięcia ustalonego punktu, który usuwa największą liczbę nieobsługiwanych wartości. Istnieje kilka procedur realizujących tę ideę, a schemat AC-3 jest najpopularniejszy:



Nie omówiliśmy tutaj szczegółów procedury filtrowania. Najprościej rzecz ujmując, może ona eksplorować spójne krotki w ograniczeniu, aby znaleźć wsparcie dla każdej wartości. Istnieją bardziej zaawansowane techniki, które zachowują pewne informacje pomiędzy powtarzającymi się wywołaniami filtru, a tym samym osiągają lepszą wydajność czasową . Często procedura filtrowania wykorzystuje semantykę ograniczenia, aby zrealizować filtrowanie szybciej. Na przykład filtrowanie dla ograniczenia A < B można zrealizować usuwając z dziedziny A wszystkie wartości większe niż maksymalna wartość B (i podobnie dla B). Wróćmy do wyszukiwania. Nawet jeśli uczynimy wszystkie ograniczenia spójnymi, nie oznacza to, że uzyskaliśmy rozwiązanie. Na przykład problem ({A, B, C}, {1, 2, 3}, {A ≠ B, B ≠ C}) jest spójny w opisanym powyżej sensie, ale nie ma rozwiązania. Dlatego techniki spójności należy połączyć z wyszukiwaniem wstecznym, aby uzyskać kompletny solver ograniczeń. Najpierw zapewniamy spójność ograniczeń. Następnie rozpoczynamy wyszukiwanie wsteczne, jak opisano w poprzedniej sekcji, i po każdej instancji zmiennej ponownie zapewniamy spójność ograniczeń. Może się zdarzyć, że podczas procedury spójności jakaś dziedzina stanie się pusta. Wskazuje to na niespójność i możemy natychmiast cofnąć się. Ponieważ procedura spójności usuwa niespójności ze zmiennych, które nie zostały jeszcze utworzone, zapobiega to przyszłym konfliktom podczas wyszukiwania. Stąd ta zasada nazywana jest patrzeniem w przód, w przeciwieństwie do technik patrzenia wstecz, które koncentrują się na odzyskiwaniu po wykrytych konfliktach. Cały proces nazywany jest również utrzymywaniem spójności podczas wyszukiwania i można go zrealizować, zastępując procedurę spójności w etykietowaniu procedurą AC-3. Rysunek przedstawia różnicę między prostym wyszukiwaniem wstecznym (góra) a techniką patrzenia w przód (dół) podczas rozwiązywania znanego problemu z czterema hetmanami.



Zadanie polega na przydzieleniu hetmana do każdej kolumny szachownicy w taki sposób, aby żadne dwa hetmany nie atakowały się nawzajem. Zauważ, że metoda look-ahead rozwiązała metodę po czterech próbach, podczas gdy proste cofanie się nadal przydziela pierwsze dwie królowe. Oczywiście, im więcej niespójności uda się usunąć, tym mniejsze drzewo poszukiwań należy zbadać. Istnieją silniejsze techniki spójności, które zakładają kilka ograniczeń jednocześnie (zamiast filtrowania każdego ograniczenia osobno, jak opisaliśmy powyżej), ale są one zazwyczaj zbyt kosztowne obliczeniowo i dlatego nie są stosowane w każdym węźle drzewa poszukiwań. Niemniej jednak istnieje również kompromis między silniejszym a wydajnym filtrowaniem domeny, zwany ograniczeniem globalnym. Chodzi o to, aby zamknąć dobrze zdefiniowany podproblem w jednym ograniczeniu (zamiast w zestawie ograniczeń), a następnie zaprojektować szybki algorytm filtrowania dla tego ograniczenia. Typowym przykładem takiego globalnego ograniczenia jest ograniczenie "all-different", które obejmuje zbiór nierówności binarnych między wszystkimi parami zmiennych, a dzięki zastosowaniu filtrowania opartego na dopasowaniu w grafach dwudzielnych, osiąga silniejsze przycinanie (Régin, 1994). Rysunek 2 ilustruje, jak CSP z nierównościami binarnymi jest konwertowany na graf dwudzielny, gdzie dopasowanie oznacza spójną instancjację zmiennych.



Ograniczenia globalne stanowią potężny mechanizm integracji efektywnych algorytmów rozwiązywania w ogólne ramy spełniania ograniczeń. Istnieją dziesiątki ograniczeń globalnych zaprojektowanych dla konkretnych obszarów zastosowań , a także ogólne ograniczenia globalne.

PRZYSZŁE TRENDY

Przetwarzanie ograniczeń to dojrzała technologia, wykraczająca poza sztuczną inteligencję i współpracująca (i konkurująca) z technikami z takich dziedzin jak badania operacyjne i matematyka dyskretna. W ostatnich latach opracowano wiele technik spełniania ograniczeń, w tym dziesiątki specjalistycznych, jak i generycznych ograniczeń globalnych , a nowe techniki wciąż się rozwijają. Trendem technologicznym jest integracja technik z różnych dziedzin w celu kooperacyjnego i hybrydowego rozwiązywania problemów. Przetwarzanie ograniczeń może stanowić dobrą bazę dla takiej integracji (jak pokazały ograniczenia globalne), ale może również dostarczać technik rozwiązywania, które można zintegrować z innymi frameworkami, takimi jak SAT (spełnianie formuł logicznych w koniunktywnej postaci normalnej). Ten trend "hybrydyzacji i integracji" znajduje odzwierciedlenie w nowych konferencjach, na przykład CP-AI-OR (Międzynarodowa Konferencja Integracji Technik AI i OR w Programowaniu Ograniczeń dla Problemów Optymalizacji Kombinatorycznej). Paradoks szybkiego rozwoju technologii polega na tym, że jest ona trudniejsza w obsłudze dla użytkowników niebędących ekspertami. Zawsze istnieje kilka sposobów modelowania problemu za pomocą ograniczeń i chociaż modele te są równoważne pod względem poprawności, często nie są równoważne pod względem efektywności. Chociaż istnieje kilka zasad "dobrego modelowania ograniczeń" , nie istnieją powszechnie obowiązujące wytyczne dotyczące modelowania ograniczeń. W związku z tym czasami nie jest łatwo zaprojektować model, który będzie rozwiązywalny (w rozsądnym czasie) przez dostępne solvery ograniczeń. Dlatego jednym z najważniejszych wyzwań przetwarzania ograniczeń w nadchodzących latach jest przywrócenie tej technologii powszechnemu dostępowi poprzez zapewnienie zautomatyzowanych narzędzi do modelowania i reformułowania problemów, które utworzą oprogramowanie pośredniczące między solverami ograniczeń a użytkownikami niebędącymi ekspertami i sprawią, że święty Graal programowania - użytkownik zgłasza problem, a komputer go rozwiązuje - stanie się rzeczywistością.

WNIOSKI

W niniejszym artykule dokonano przeglądu popularnych technik spełniania ograniczeń, aby przedstawić zwięzłe podstawy technologii osobom, które chciałyby wykorzystać te techniki do rozwiązywania problemów optymalizacji kombinatorycznej. Uprościliśmy nieco techniki i terminologię, aby dopasować je do zakresu artykułu, zachowując jednocześnie podstawowe zasady. Należy pamiętać, że zaprezentowane techniki (i wiele innych) są już dostępne w istniejących systemach do rozwiązywania ograniczeń, takich jak biblioteka ILOG CP , SICStus Prolog , ECLiPSe , Mozart , Choco i inne systemy, dzięki czemu użytkownicy nie muszą ich programować od podstaw. Niemniej jednak zrozumienie podstawowych zasad jest ważne dla projektowania efektywnych modeli ograniczeń, które mogą być rozwiązywane przez te systemy. Przetwarzanie ograniczeń nie osiągnęło jeszcze szczytu programowania, ale szybko zmierza w tym kierunku.

WSTĘP

Symulowane wyżarzanie jest jednym z najważniejszych metaheurystyk lub algorytmów ogólnego przeznaczenia optymalizacji kombinatorycznej, którego właściwości zbieżności w kierunku rozwiązań wysokiej jakości są dobrze znane, choć charakteryzują się wysokim kosztem obliczeniowym. Z tego powodu powstało wiele prac badawczych dotyczących szybkości zbieżności algorytmu, a zwłaszcza sposobu traktowania parametru temperatury, znanego jako harmonogram lub strategia chłodzenia. W niniejszym artykule przeprowadzamy badanie porównawcze wydajności symulowanego wyżarzania z wykorzystaniem najważniejszych strategii chłodzenia. W praktycznej analizie algorytmu wykorzystywane są dwa klasyczne problemy optymalizacji kombinatorycznej: problem komiwojażera i problem przyporządkowania kwadratowego.

WSTĘP

Głównym celem optymalizacji kombinatorycznej jest analiza i algorytmiczne rozwiązywanie problemów optymalizacji z ograniczeniami i zmiennymi dyskretnymi. Najważniejsze są problemy wymagające algorytmów o niewielomianowej złożoności czasowej w stosunku do rozmiaru problemu, zwane problemami NP-zupełnymi. Ogólne techniki rozwiązywania tego typu problemów należą do trzech różnych, ale powiązanych ze sobą dziedzin badawczych. Po pierwsze, możemy wymienić heurystyczne algorytmy wyszukiwania, takie jak deterministyczne algorytmy wyszukiwania lokalnego , stochastyczny algorytm symulowanego wyżarzania oraz wyszukiwanie tabu. Drugim rodzajem technik rozwiązywania problemów są algorytmy inspirowane genetyką i teorią ewolucji, takie jak algorytmy genetyczne i ewolucyjne oraz algorytmy memetyczne. Wreszcie, ze względu na kolektywne właściwości obliczeniowe niektórych modeli neuronowych, obszar sztucznych sieci neuronowych wniósł trzecie podejście, choć prawdopodobnie nie tak istotne jak poprzednie, do rozwiązywania problemów optymalizacji kombinatorycznej za pomocą sieci Hopfielda, maszyny Boltzmanna oraz mapy samoorganizującej się .

Algorytm symulowanego wyżarzania

Symulowane wyżarzanie to stochastyczna odmiana przeszukiwania lokalnego, która zawiera stochastyczne kryterium akceptacji rozwiązań o gorszej jakości, aby zapobiec przedwczesnemu uwięzieniu algorytmu w lokalnych optimach. To kryterium akceptacji jest oparte na algorytmie Metropolisa do symulacji systemów fizycznych poddanych działaniu źródła ciepła.

Algorytm (symulowane wyżarzanie). Niech będzie kombinatorycznym problemem optymalizacji (X, S, f, R) z funkcją generatora losowych k-sąsiadujących dopuszczalnych rozwiązań g : S × [0, 1 [? S. Zakładając, bez utraty ogólności, że f musi być minimalizowane, algorytm symulowanego wyżarzania można opisać w następujący sposób:

1. Ustal początkowe losowe dopuszczalne rozwiązanie jako bieżące rozwiązanie, s_i = s₀.
2. Ustaw temperaturę początkową lub parametr sterujący T = T₀.
3. Uzyskaj nowe rozwiązanie, które różni się od obecnego wartością k zmiennych, korzystając z funkcji generatora losowych k-sąsiadujących dopuszczalnych rozwiązań, s_j = g(s_i, random[0,1[).
4. Jeśli nowe rozwiązanie sj jest lepsze od obecnego, f(s_j) < f(s_i), to s_j jest ustawiane jako obecne rozwiązanie, s_i = s_j. W przeciwnym razie, jeśli ef(si)-f(sj)/ T > random[0,1[ , s_j jest równie akceptowane jako obecne rozwiązanie, s_i = s_j.
5. Jeśli liczba wykonanych przejść między stanami (kroki 3 i 4) dla bieżącej wartości temperatury jest równa L, to temperatura T jest zmniejszana.
6. Jeśli istnieją pewne k-sąsiadujące dopuszczalne rozwiązania w pobliżu obecnego, które nie zostały jeszcze przetworzone, należy powtórzyć kroki od 3 do 5. Algorytm kończy się w przypadku, gdy zbiór rozwiązań k-sąsiedzkich bliskich bieżącemu zostanie całkowicie przetworzony z prawdopodobieństwem bliskim 1 bez uzyskania jakiejkolwiek poprawy jakości rozwiązań.

Najważniejszą cechą algorytmu symulowanego wyżarzania jest to, że oprócz akceptacji przejść, które implikują poprawę kosztu rozwiązania, pozwala on również zaakceptować malejącą liczbę przejść, które oznaczają utratę jakości rozwiązania. Algorytm symulowanego wyżarzania zbiega asymptotycznie do zbioru globalnie optymalnych rozwiązań problemu. E. Aarts i J. Korst przedstawiają pełny dowód w swojej książce "Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing" (1989). Zasadniczo warunek zbieżności w kierunku globalnego optimum określa, że temperatura T układu musi być zmniejszana logarytmicznie zgodnie z równaniem: T_k = T₀/1 +Log(1+k) gdzie k = 0,1,...,n oznacza cykl temperaturowy. Jednak ta funkcja chłodzenia układu wymaga zaporowego czasu obliczeniowego, dlatego konieczne jest rozważenie szybszych metod obniżania temperatury.

Harmonogramy chłodzenia

Praktyczna implementacja symulowanego wyżarzania wymaga wygenerowania skończonej sekwencji malejących wartości temperatury T oraz skończonej liczby L przejść między stanami dla każdej wartości temperatury. Aby osiągnąć ten cel, należy określić harmonogram chłodzenia. Poniższy harmonogram chłodzenia, często stosowany w literaturze, został zaproponowany przez Kirkpatricka, Gelatta i Vecchiego (1983) i składa się z trzech parametrów: •  Temperatura początkowa, T₀. Wartość początkowa temperatury musi być wystarczająco wysoka, aby każde nowe rozwiązanie wygenerowane w przejściu między stanami zostało zaakceptowane z pewnym prawdopodobieństwem bliskim 1.
•  Funkcja spadku temperatury. Zazwyczaj stosuje się wykładniczą funkcję spadku, taką jak T_k = T₀ ⋅ α^k, gdzie α jest stałą mniejszą od jednostki. Wartości typowe α wahają się między 0,8 a 0,99. •  Liczba przejść między stanami, L, dla każdej wartości temperatury. Intuicyjnie rzecz biorąc, liczba przejść dla każdej temperatury musi być wystarczająco wysoka, aby w przypadku braku akceptacji zmian w rozwiązaniu, cały zbiór k-sąsiadujących, dopuszczalnych rozwiązań w pobliżu aktualnego rozwiązania, mógł zostać przetworzony z prawdopodobieństwem bliskim 1. Temperaturę początkową, T₀, i liczbę przejść między stanami, L, można łatwo uzyskać. Z drugiej strony, funkcja spadku temperatury była badana w licznych pracach badawczych

GŁÓWNY TEMAT

W tej sekcji opisano dziewięć różnych harmonogramów chłodzenia wykorzystanych w porównaniu algorytmu symulowanego wyżarzania. Wszystkie składają się z co najmniej trzech parametrów: temperatury początkowej T₀, funkcji spadku temperatury oraz liczby przejść między stanami L dla każdej temperatury.

Multiplikatywne chłodzenie monotoniczne

W multiplikatywnym chłodzeniu monotonicznym, temperatura układu T w cyklu k jest obliczana poprzez pomnożenie temperatury początkowej T₀ przez współczynnik malejący w stosunku do cyklu k. Rozważane są cztery warianty:

•  Wykładnicze chłodzenie multiplikatywne ,





zaproponowane przez Kirkpatricka, Gelatta i Vecchiego (1983), użyte jako punkt odniesienia w porównaniu różnych kryteriów chłodzenia. Spadek temperatury wynika z pomnożenia temperatury początkowej T0 przez współczynnik malejący wykładniczo względem cyklu temperaturowego k: T_k = T₀ ⋅ α^k ( 0,8 ≤ a ≤ 0,9 )

•  Logarytmiczne chłodzenie multiplikatywne (rysunek 1-B),



(α > 1)

oparte na warunku asymptotycznej konwergencji symulowanego wyżarzania , ale uwzględniające współczynnik a przyspieszenia chłodzenia, który umożliwia jego zastosowanie w praktyce. Spadek temperatury uzyskuje się mnożąc temperaturę początkową T₀ przez współczynnik, który maleje odwrotnie proporcjonalnie do logarytmu naturalnego cyklu temperaturowego k:

T_k = T₀ / 1 + αLog(1+k)

(α > 1)

•  Liniowe chłodzenie multiplikatywne (rysunek 1-C).



Spadek temperatury uzyskuje się mnożąc temperaturę początkową T₀ przez współczynnik, który maleje odwrotnie proporcjonalnie do kwadratu cyklu temperaturowego k:

T_k = T₀/1 +αk

(α > 0)

•  Kwadratowe chłodzenie multiplikatywne (rysunek 1-D).



Spadek temperatury uzyskuje się mnożąc temperaturę początkową T₀ przez współczynnik, który maleje odwrotnie proporcjonalnie do kwadratu cyklu temperaturowego k:

T_k = T₀/1 +αk²

(α > 0)

Chłodzenie monotoniczne addytywne

W chłodzeniu monotonicznym addytywnym należy uwzględnić dwa dodatkowe parametry: liczbę n cykli chłodzenia oraz temperaturę końcową T_n układu. W tym typie chłodzenia temperaturę układu T w cyklu k oblicza się, dodając do temperatury końcowej T_n człon malejący w stosunku do cyklu k. Rozważane są cztery warianty oparte na wzorach zaproponowanych przez B. T. Luke′a (2005):

•  Liniowe chłodzenie addytywne (rysunek 2-A).



Spadek temperatury oblicza się, dodając do temperatury końcowej T_n człon malejący liniowo względem cyklu temperaturowego k:

T_k = T_n + (T₀ - T_n)(n-k/n) •  Kwadratowe chłodzenie addytywne (rysunek 2-B).



Spadek temperatury oblicza się, dodając do temperatury końcowej T_n człon malejący proporcjonalnie do kwadratu cyklu temperaturowego k:

T_k = T_n + (T₀ - T_n)(n-k/n)²

•  Wykładnicze chłodzenie addytywne (rysunek 2-C).



Spadek temperatury oblicza się, dodając do temperatury końcowej T_n człon, który maleje odwrotnie proporcjonalnie do liczby e podniesionej do potęgi cyklu temperaturowego k:



•  Chłodzenie addytywne trygonometryczne (rysunek 2-D).



Spadek temperatury oblicza się, dodając do temperatury końcowej T_n człon malejący proporcjonalnie do cosinusa cyklu temperaturowego k:

T_k = T_n+1/2(T₀-T_n)(1 + cos(kπ/n))

Chłodzenie adaptacyjne niemonotoniczne

W chłodzeniu adaptacyjnym niemonotonicznym temperatura układu T w każdej zmianie stanu jest obliczana poprzez pomnożenie wartości temperatury T_k, uzyskanej zgodnie z dowolnym z poprzednich kryteriów, przez współczynnik adaptacyjny μ oparty na różnicy między bieżącym celem rozwiązania, f(s_i), a najlepszym celem osiągniętym do tego momentu przez algorytm, oznaczony f*:

T = μT_k= (1 + f(s_i - f*/f(s_i))T_k

Należy zauważyć, że nierówność 1 ≤ μ < 2 została zweryfikowana. Współczynnik μ oznacza, że im większa odległość między bieżącym rozwiązaniem a najlepszym osiągniętym rozwiązaniem, tym wyższa temperatura, a w konsekwencji tym większe są dozwolone przeskoki energii. Kryterium to jest wariantem kryterium zaproponowanego przez M. Locatelliego (2000) i może być stosowane w połączeniu z dowolnym z poprzednich kryteriów do obliczenia T_k. W porównaniu, w tym celu zastosowano standardowe chłodzenie wykładnicze iloczynowe. Zatem krzywa chłodzenia charakteryzuje się fluktuacyjnym, losowym zachowaniem, mieszczącym się między krzywą wykładniczą zdefiniowaną przez T_k a jej podwójną wartością 2T_k .

Problemy optymalizacji kombinatorycznej

Wykorzystane w porównaniu

Problem komiwojażera. Problem komiwojażera, TSP, polega na znalezieniu najkrótszej cyklicznej ścieżki, która okrąża n miast, tak aby każde miasto zostało odwiedzone tylko raz. Funkcja celu f, którą należy zminimalizować, jest dana wyrażeniem:



gdzie każda zmienna xi oznacza miasto odwiedzane w i-tym punkcie trasy, a d(x_i,x_ji i x_j. Testy przeprowadzono z użyciem dwóch różnych instancji euklidesowego TSP. Pierwsza z nich pozwala na objazd 47 miast europejskich, a druga - 80 miast.

Problem zadania kwadratowego. Problem Przydziału Kwadratowego, QAP, polega na znalezieniu optymalnej lokalizacji n warsztatów w p dostępnych miejscach (p ≥ n ), biorąc pod uwagę, że między każdymi dwoma warsztatami należy przetransportować określoną ilość towarów, a koszt jednostkowy różni się w zależności od lokalizacji warsztatów. Celem jest minimalizacja całkowitego kosztu transportu towarów między warsztatami. Funkcja celu f, którą należy minimalizować, jest podana wzorem:



gdzie każda zmienna x_i oznacza miejsce, w którym znajduje się warsztat i, c(x_i,x_j) to koszt jednostkowy transportu towarów między miejscami, w których znajdują się sklepy i i j, a q(i,j) to ilość towarów, która musi zostać przetransportowana między tymi warsztatami. Testy zostały przeprowadzone z wykorzystaniem dwóch różnych instancji QAP: pierwszej z 47 warsztatami zlokalizowanymi w 47 miastach europejskich i drugiej z 80 warsztatami zlokalizowanymi w 80 miastach.

Wybór parametrów . Dla każdej instancji problemu wszystkie warianty algorytmu wykorzystują te same wartości temperatury początkowej T₀ i liczby L przejść między stanami dla każdej temperatury. Temperatura początkowa T₀ musi być wystarczająco wysoka, aby zaakceptować każde przejście między stanami do gorszego rozwiązania. Liczba L przejść między stanami musi gwarantować z prawdopodobieństwem η bliskim 1, że jeśli nie zostaną zaakceptowane żadne zmiany rozwiązania, można będzie przetworzyć dowolne rozwiązanie k-sąsiadujące, zbliżone do bieżącego.

Aby określić pozostałe parametry obniżania temperatury dla każdego schematu chłodzenia przy podobnych warunkach czasu realizacji, bierzemy pod uwagę średnią temperaturę końcową oraz błąd standardowy temperatury σ wykładniczego mnożnika chłodzenia Kirkpatricka, Gelatta i Vecchiego ze współczynnikiem malejącym α = 0,95. Celem jest takie określenie parametrów spadku temperatury, aby temperatura w przedziale została osiągnięta w takiej samej liczbie cykli, jak w przypadku wykładniczego mnożnikowego chłodzenia. Rozróżniamy trzy przypadki:

o Multiplikatywne chłodzenie monotoniczne. Współczynnik spadku a, który pojawia się w równaniach spadku temperatury, musi umożliwiać osiągnięcie temperatury , czyli najwyższej temperatury, od której koniec algorytmu jest bardzo prawdopodobny, w takiej samej liczbie n cykli, jak w przypadku wykładniczego chłodzenia multiplikatywnego. Wiedząc, że dla tego chłodzenia liczba n cykli wynosi:



dla chłodzenia mnożnikowego logarytmicznego otrzymujemy:



dla chłodzenia mnożnikowego liniowego:



a dla chłodzenia mnożnikowego kwadratowego:



•  Chłodzenie monotoniczne addytywne. Temperatura końcowa wynosi , a liczba n cykli temperaturowych jest równa odpowiadającej im liczbie cykli chłodzenia wykładniczego mnożnikowego dla tej temperatury końcowej, czyli:



•  Chłodzenie adaptacyjne niemonotoniczne. Ponieważ chłodzenie adaptacyjne jest w testach łączone z chłodzeniem wykładniczym mnożnikowym, współczynnik spadku a, który pojawia się w równaniu spadku temperatury, musi również wynosić α = 0,95.

PRZYSZŁE TRENDY

Zgodnie z poprzednimi wynikami proponujemy kontynuację badań nad harmonogramami chłodzenia z symulowanym wyżarzaniem:

•  Analiza wpływu temperatury początkowej na wydajność algorytmu. Interesującym pomysłem mogłoby być oszacowanie zachowania algorytmu, gdy temperatura jest inicjowana z procentem od 10% do 90% typowej szacowanej wartości dla T₀

•  Określenie optymalnej monotonicznej krzywej spadku temperatury, w oparciu o wykładnicze chłodzenie multiplikatywne. Możliwa byłaby dynamiczna zmiana parametru a w równaniu spadku temperatury, z niższymi wartościami początkowymi (α = 0,8) i wartościami końcowymi bliższymi 1 (α = 0,9), ale osiągnięciem średniej liczby cykli temperaturowych równej standardowemu przypadkowi ze stałym parametrem α = 0,95.

•  Zbadanie nowych niemonotonicznych metod obniżania temperatury w połączeniu z wykładniczym chłodzeniem multiplikatywnym. Metody te, podobnie jak metoda Locatelliego w porównaniu, mogłyby opierać się na modyfikacji temperatury w zależności od odległości od bieżącego celu do najlepszego celu odniesienia.

Chociaż te trzy kierunki pracy są niezależne, wydaje się jasne, że ostatecznym celem byłoby zintegrowanie wyników uzyskanych za pomocą tych kierunków, w celu zbudowania wysokiej jakości kombinatorycznej metaheurystyki optymalizacji opartej na symulowanym wyżarzaniu.

WNIOSKI

Główne wnioski, jakie można wyciągnąć z porównania harmonogramów chłodzenia algorytmu symulowanego wyżarzania, to:

•  Biorąc pod uwagę obiektywną jakość związaną z kształtem krzywej spadku temperatury, możemy stwierdzić, że symulowane wyżarzanie działa prawidłowo pod względem zdolności do ucieczki od lokalnych minimów, gdy krzywa ma umiarkowane nachylenie w początkowej i środkowej części przetwarzania, a łagodniejsze w końcowej części, tak jak ma to miejsce w standardowym wykładniczym chłodzeniu multiplikatywnym. Specyficzny kształt (wypukły, sigmoidalny) krzywej w początkowej i środkowej części nie wydaje się wyjątkowy.

•  Biorąc pod uwagę czas wykonania, błąd standardowy liczby iteracji wydaje się być powiązany z ogonem krzywej spadku temperatury w końcowej części algorytmu. Odwrotnie logarytmiczny ogon powoduje łagodniejszy końcowy spadek temperatury i wyższy błąd standardowy, podczas gdy odwrotnie kwadratowe i wykładnicze ogony znoszą się szybciej, zapewniając najlepsze wartości błędu standardowego algorytmu.

•  Biorąc pod uwagę zastosowanie niemonotonicznej metody spadku temperatury, możemy stwierdzić, że zastosowane kryterium nie tylko nie pogarsza ogólnej wydajności algorytmu, ale wydaje się mieć korzystny wpływ, który zasługuje na uwzględnienie i dokładniejsze zbadanie.

WSTĘP

Od czasu swojej przełomowej publikacji w 1988 r. paradygmat sieci neuronowej komórkowej (CNN) przyciągnął uwagę społeczności badawczej, głównie ze względu na jego zdolność do integrowania złożonych procesów obliczeniowych w kompaktowe, programowalne w czasie rzeczywistym analogowe układy scalone VLSI. W przeciwieństwie do automatów komórkowych, model CNN zawiera nieliniowe procesory, które z analogowych danych wejściowych tablicy generują w czasie ciągłym analogowe dane wyjściowe tablicy przy użyciu prostego, powtarzalnego schematu kontrolowanego tylko przez kilka parametrów o wartościach rzeczywistych. CNN jest rdzeniem rewolucyjnego Analogowego Komputera Komórkowego, programowalnego systemu, którego struktura jest tak zwaną Uniwersalną Maszyną CNN (CNN-UM). Analogowe komputery CNN naśladują anatomię i fizjologię wielu narządów sensorycznych i przetwarzających, z dodatkową możliwością przechowywania danych i programów . W tym artykule omówiono główne cechy tego modelu sztucznej sieci neuronowej (ANN) i skupiono się na jego wybitnym i bardziej eksploatowanym zastosowaniu inżynieryjnym: cyfrowym przetwarzaniu obrazu (DIP).

KONTEKST

W poniższych akapitach przeprowadzono definicję parametrów i struktury CNN w celu wyjaśnienia praktycznego wykorzystania modelu w DIP. Standardowa architektura CNN składa się z prostokątnej tablicy M × N komórek C(i,j) o współrzędnych kartezjańskich (i,j), i = 1, 2, …, M, j = 1, 2, …, N. Każda komórka lub neuron C(i,j) jest ograniczony do spójnego sąsiedztwa lub sfery wpływu Sr(i,j) o dodatnim promieniu całkowitym r, który jest zbiorem wszystkich sąsiadujących komórek spełniających następującą właściwość:



Ten zestaw jest czasami określany jako sąsiedztwo (2r +1) × (2r +1), np. dla sąsiedztwa 3 × 3 r powinno wynosić 1. Tak więc parametr r kontroluje łączność komórki, tj. liczbę aktywnych synaps, które łączą komórkę z jej bezpośrednimi sąsiadami. Gdy r > N /2 i M = N, uzyskuje się w pełni połączoną sieć neuronową, w której każdy neuron jest połączony z każdą inną komórką w sieci, a Sr(i,j) jest całą tablicą. Ten skrajny przypadek odpowiada klasycznemu modelowi sieci neuronowej Hopfielda. Równanie stanu dowolnej komórki C(i,j) w strukturze tablicy M × N standardowej sieci neuronowej można opisać matematycznie za pomocą:



gdzie C i R są wartościami kontrolującymi przejściową odpowiedź obwodu neuronowego (podobnie jak filtr RC, zwykle ustawiony na jedność dla uproszczenia), I jest ogólnie stałą wartością, która odchyla lub proguje macierz stanu Z = {z_ij}, a Sr jest lokalnym sąsiedztwem komórki C(i, j) zdefiniowanym w (1), które kontroluje wpływ danych wejściowych X = {x_ij} i wyjścia sieciowego Y = {y_ij} dla czasu t. Oznacza to, że zarówno płaszczyzna wejściowa, jak i wyjściowa oddziałują ze stanem komórki poprzez definicję zestawu wag o wartościach rzeczywistych, A(i, j; k, l) i B(i, j; k, l), których rozmiar jest określany przez promień sąsiedztwa r. Macierze lub szablony klonowania A i B nazywane są odpowiednio operatorami sprzężenia zwrotnego i sprzężenia zwrotnego do przodu (lub sterowania). Standardowa sieć CNN jest zwykle definiowana ze stałymi wartościami dla r, I, A i B, co oznacza, że dla ustalonego obrazu wejściowego X, neuron C(i, j) jest dostarczany dla każdego piksela (i, j), ze stałymi obwodami ważonymi zdefiniowanymi przez szablon sprzężenia zwrotnego A, który łączy komórkę z płaszczyzną wyjściową Y, i przez szablon sterowania B, który łączy neuron z sąsiednimi pikselami wejściowymi x_ij ∈ X. Wartość stanu neuronu z_ij jest następnie dostosowywana za pomocą parametru odchylenia I i przekazywana jako dane wejściowe do funkcji liniowej po kawałku w celu określenia wartości wyjściowej y_ij. Tę funkcję można wyrazić jako



W kontekście przetwarzania obrazu obraz wejściowy w skali szarości X można przedstawić piksel po pikselu, używając liniowej mapy między wartością piksela (np. 8-bitową macierzą jasności całkowitej z 256 poziomami skali szarości) a interwałem wejściowym CNN [-1, +1], gdzie dolny limit jest używany do implementacji pełnej jasności (tj. bieli), a górny do czarnych pikseli

PODSTAWOWE PRZETWARZANIE OBRAZU CNN

Głównym zastosowaniem modelu CNN, ze względu na jego schemat przypominający splot, jest modelowanie i projektowanie DIP. W kolejnych podsekcjach przedstawiono szereg podstawowych podejść DIP, podkreślając znaczenie parametrów sieci poprzez podanie ilustrujących przykładów zastosowania. Zaczynając od standardowego modelu opisanego w poprzedniej sekcji, następuje definicja standardowej izotropowej sieci CNN. Następnie wykonano przykład zastosowania w logicznym przetwarzaniu DIP w celu wprowadzenia efektów nieliniowych, które implikują użycie szablonu sprzężenia zwrotnego innego niż zero.

Izotropowy model CNN

W przypadku nieruchomego obrazu X będzie niezmienne w czasie, a w przypadku wideo X = X(t). W najbardziej ogólnym przypadku r, A, B i I mogą się zmieniać w zależności od położenia i czasu, a szablony klonowania są definiowane jako nieliniowe, z możliwością integrowania sygnałów hamujących dla macierzy stanu, a nawet nieliniowych szablonów, które oddziałują z mieszanymi danymi wejścia-wyjścia-stanu. Te możliwe rozszerzenia podnoszą definicję specjalnej (i prostszej) klasy CNN, zwanej izotropową lub niezmienną w przestrzeni, w której r, A, B i I są ustalone dla całej sieci i w której wykorzystywane są liniowe operatory synaptyczne. Innymi słowy,



Zdecydowana większość szablonów zdefiniowanych w kompendium szablonów dla CNN-UM opiera się na tym izotropowym schemacie, używając r = 1 i obrazów binarnych na płaszczyźnie wejściowej. Jeśli nie jest używane żadne sprzężenie zwrotne (tj. A = 0), wówczas CNN zachowuje się jak sieć splotowa, używając B jako filtru przestrzennego, I jako progu i liniowego wyjścia kawałkami (3) jako ogranicznika lub nasyconego filtra wyjściowego. W ten sposób praktycznie każdy filtr przestrzenny z teorii DIP może być zaimplementowany na takim sterowanym w przód CNN, co zapewnia stabilność jego wyjścia. Na przykład szablon EDGE zdefiniowany przez



jest zaprojektowany do poprawnej pracy dla wejść binarnych, dając czarne (+1) piksele wyjściowe w lokalizacjach wejściowych, w których istnieje czarny piksel krawędziowy (tj. jeśli czarny piksel ma 1 białego sąsiada), i białe (-1) piksele w innych miejscach. Jednak gdy obraz wejściowy w skali szarości jest podawany do tego CNN, wyjście może nie być obrazem binarnym. Aby rozwiązać ten potencjalny problem, następująca modyfikacja jest wykonywana w EDGE CNN:



Definicja wartości bezwzględnej sprzężenia zwrotnego środka większej niż 1 w (6) zapewnia wyjście binarne, a tym samym stabilność sieci wyjściowej. Szablon B używany w tych CNN jest typu Laplace′a, mający ważną właściwość, że wszystkie otaczające wejściowe wagi synaptyczne są hamujące (tj. ujemne) i identyczne, ale waga synaptyczna środka jest pobudzająca, a średnia wszystkich wejściowych wag synaptycznych wynosi zero. Oprócz krawędzi, wypukłe rogi (tj. czarne piksele z co najmniej pięcioma białymi sąsiadami) mogą być również wykrywane za pomocą następującej modyfikacji jego parametrów:



Przykład ten ilustruje ważną rolę odgrywaną przez parametr progowy I. Parametr ten można postrzegać jako indeks odchylenia, który realokuje początek z₀ funkcji wyjściowej (3)

Podstawowe operatory logiczne

Aby wykonać operacje logiczne na poziomie pikseli pomiędzy dwoma obrazami binarnymi X₁ i X₂, stan początkowy Z(0) sieci jest również wykorzystywany jako zmienna . W standardowej sieci CNN ze sprzężeniem zwrotnym ta zmienna Z(0) jest zwykle ustawiana na zero, ale może być również używana w celu uzyskania wyników ważnych dla innych zastosowań, takich jak wykrywanie ruchu i szacowanie. Na przykład dla unii zbiorów binarnych (logiczne LUB) zdefiniowano następujące szablony:



podczas gdy dla przecięcia zbiorów (logiczne AND) zmienne te są definiowane jako



Po raz kolejny wykorzystanie sprzężenia zwrotnego pobudzającego zapewnia stabilność wyjścia poprzez funkcję wyjściową nasycenia (3), a próg odpowiednio odchyla wynik końcowy.

Standardowa sieć CNN sterowana sprzężeniem zwrotnym

Szablony sprzężenia zwrotnego używane we wszystkich wcześniej opisanych sieciach CNN wykorzystują (jeśli w ogóle) tylko centralny element szablonu. Standardowa sieć CNN z niecentralnymi elementami sprzężenia zwrotnego niezerowymi to specjalna klasa, która wykazuje bardziej złożoną dynamikę niż te omówione do tej pory . Użycie elementu centralnego w A, a₀₀ > 1, oznacza, że wyjście będzie binarne, tj. wyjście sieciowe nigdy nie będzie stabilne w liniowym obszarze funkcji nasycenia (3). Przy tym ograniczeniu, jeśli w szablonie sprzężenia zwrotnego zostanie ustawiony inny element, mogą wystąpić dwie możliwe sytuacje: aktywacja komórek w przeciwnej części tylko jednego z obszarów nasycenia (częściowa inwersja) lub inwersje komórek propagujących fale w obu stanach binarnych. Pierwszy rodzaj tych sieci CNN sterowanych sprzężeniem zwrotnym ma właściwość monoaktywacji, jeśli komórki tylko w jednym obszarze nasyconym mogą wejść do obszaru liniowego. Tak więc, jeśli komórki mogą wejść do obszaru liniowego z obszaru nasycenia dodatniego, to te komórki nasycone w części ujemnej muszą spełniać warunek, że całkowity wkład A, B i I w jego sferze wpływu S_r musi być mniejszy niż -1. To znaczy,



Z drugiej strony, jeśli komórki wchodzą do regionu liniowego tylko z regionu ujemnego nasycenia, to wkład dla dodatnich stabilnych komórek musi być wij(t) > 1. Można wykazać, że w monoaktywowanej sieci CNN z dodatnimi współczynnikami A, z a₀₀ > 1 i nasyconymi wartościami początkowymi, wszystkie komórki, które wchodzą do regionu liniowego, zmieniają monotonicznie swój stan z (tylko) jednego obszaru nasyconego do drugiego, a zatem jest to stabilna sieć nieliniowa. Jeśli na przykład jeden element w A jest ujemny, stan przejściowy nie będzie monotoniczny, co niekoniecznie oznacza niestabilność sieci. Przykładem niemonotonicznej, ale stabilnej sieci CNN jest detektor połączonych komponentów (CCD) , którego szablony (dla przypadku poziomego) są następujące:



Do zaprojektowania jednokierunkowej, falowo-propagowanej, monoaktywowanej sieci CNN zdefiniowano binarny wzór aktywacji, który będzie wyzwalał stan przejściowy, dopóki nie zostanie osiągnięta stabilność wyjściowa . Przykładem tego typu stabilnej sieci CNN napędzanej sprzężeniem zwrotnym jest (poziomy) detektor cienia , którego parametry to:



TRENDY PRZYSZŁOŚCI

Inżynierowie i specjaliści nieustannie dążą do: konkurowania z naturą i naśladowania jej, zwłaszcza niektórych "inteligentnych" zwierząt. Jednym z obszarów, którym interesują się inżynierowie komputerowi, jest wzrok. W tym kontekście tzw. Bioniczne Oko osadzone w architekturze CNN-UM jest idealne do implementacji wielu przestrzenno-czasowych modeli neuromorficznych. Dzięki potężnemu zestawowi narzędzi do przetwarzania obrazu i kompaktowej implementacji VLSI CNN-UM można wykorzystać do programowania lub naśladowania różnych modeli siatkówek, a nawet ich kombinacji . Ponadto może łączyć modele oparte na biologii, modele inspirowane biologią i analogowe algorytmy przetwarzania obrazu sztucznego. Ta kombinacja z pewnością przyniesie szerszy rodzaj zastosowań i rozwoju.

WNIOSEK

W ciągu ostatniej dekady zbadano szereg innych postępów w zakresie definicji i charakterystyki CNN. Obejmuje to definicję metod projektowania i implementacji większych niż 3 × 3 sąsiedztw w CNN-UM , wydajną implementację technik półtonowania , implementację CNN niektórych technik kompresji obrazu lub projekt algorytmu szybkiej transformaty Fouriera opartego na CNN na sygnałach analogowych, między wieloma innymi. Niektóre z nich zostały również opisane w tej książce w artykule zatytułowanym Advanced Cellular Neural Networks Image Processing. W tym artykule omówiono ogólny przegląd głównych właściwości i cech modelu Cellular Neural Network, skupiając się na jego możliwościach DIP z podstawowego punktu widzenia. CNN jest obecnie podstawowym i potężnym zestawem narzędzi do zadań nieliniowego przetwarzania obrazu w czasie rzeczywistym, głównie ze względu na jego wszechstronną programowalność, która napędzała jego rozwój sprzętowy dla aplikacji do wykrywania obrazu.

WSTĘP

Uczenie maszynowe dostarczyło potężnych algorytmów, które automatycznie generują modele predykcyjne na podstawie doświadczenia. Jedną z konkretnych technik jest uczenie nadzorowane, w którym maszyna jest trenowana w celu przewidywania pożądanego wyniku dla każdego wzorca wejściowego x. Ten rozdział skupi się na klasyfikacji, czyli uczeniu nadzorowanym, gdy przewidywanym wynikiem jest etykieta klasy. Na przykład przewidywanie, czy u pacjenta w szpitalu rozwinie się rak, czy nie. W tym przykładzie etykieta klasy c jest zmienną o dwóch możliwych wartościach: "rak" lub "brak raka", a wzorzec wejściowy x jest wektorem zawierającym dane pacjenta (np. wiek, płeć, dietę, nawyki związane z paleniem itp.). Aby zbudować właściwy model predykcyjny, metody uczenia nadzorowanego wymagają zestawu przykładów xi wraz z odpowiadającymi im etykietami ci. Ten zestaw danych nazywany jest "zbiorem treningowym". Skonstruowany model jest następnie wykorzystywany do przewidywania etykiet zbioru nowych przypadków xj, zwanego "zbiorem testowym". W przykładzie przewidywania raka jest to faza, w której model jest wykorzystywany do przewidywania raka u nowych pacjentów. Jednym z powszechnych założeń w algorytmach uczenia nadzorowanego jest to, że struktura statystyczna zbiorów danych treningowych i testowych jest taka sama. Oznacza to, że zakłada się, że zbiór testowy ma taki sam rozkład atrybutów p(x) i taki sam rozkład klas p(c|x) jak zbiór treningowy. Jednakże, z różnych powodów, nie jest to zazwyczaj prawdą w rzeczywistych zastosowaniach. Na przykład, w wielu problemach zbiór danych treningowych jest uzyskiwany w określony sposób, który różni się od sposobu, w jaki zbiór danych testowych zostanie wygenerowany później. Ponadto, natura problemu może ewoluować w czasie. Zjawiska te powodują, że pTr(x, c) ? pTest(x, c), co może obniżyć wydajność modelu skonstruowanego w trakcie treningu. W niniejszym artykule przedstawiamy nowy algorytm, który pozwala na reestymację modelu skonstruowanego w trakcie treningu z wykorzystaniem nieoznakowanych wzorców testowych. Przedstawiamy właściwości konwergencji algorytmu i ilustrujemy jego wydajność na przykładzie problemu sztucznego. Na koniec pokazujemy jego mocne strony w kontekście diagnozy choroby serca, gdzie zbiór treningowy pochodzi z innego szpitala niż zbiór testowy.

WSTĘP

W praktycznych problemach struktura statystyczna zbiorów uczących i testowych może być różna, tj. pTr(x, c) ? pTest(x, c). Efekt ten może wynikać z różnych przyczyn. Na przykład z błędów w doborze próby zbioru uczącego. Inną możliwą przyczyną jest to, że zbiory uczące i testowe mogą być powiązane z różnymi kontekstami. Na przykład, model diagnostyki chorób serca stosowany w szpitalu, który różni się od szpitala, w którym zebrano zbiór danych uczących. Z kolei, jeśli szpitale znajdują się w miastach, w których ludzie mają różne nawyki, średni wiek itp., spowoduje to powstanie zbioru testowego o innej strukturze statystycznej niż zbiór uczący. Przypadek szczególny pTr(x) ? pTest(x) i pTr(c | x) = pTest(c | x) jest znany w literaturze jako "przesunięcie kowariancji". W kontekście uczenia maszynowego przesunięcie kowariancji może obniżyć wydajność standardowych algorytmów uczenia maszynowego. Zaproponowano różne techniki radzenia sobie z tym problemem, patrz na przykład . Sugerowano również uczenie transdukcyjne jako inny sposób poprawy wydajności, gdy struktura statystyczna zbioru testowego jest przesunięta względem zbioru uczącego . Statystyki wzorców x mogą również zmieniać się w czasie, na przykład w firmie o ciągłym napływie nowych i odchodzących klientów (rysunek 1). Jeśli jesteśmy zainteresowani zbudowaniem modelu predykcyjnego, statystyki klientów w momencie wykorzystania modelu będą różnić się od statystyk w trakcie uczenia. Wreszcie, często koncepcja, której należy się nauczyć, nie jest statyczna, lecz ewoluuje w czasie (na przykład, przewidując, które wiadomości e-mail są spamem, a które nie), co powoduje, że pTr(x, c) ? pTest(x, c). Problem ten znany jest jako "dryf koncepcji" i zaproponowano różne algorytmy, aby sobie z nim poradzić.

NOWY ALGORYTM KONSTRUKCJI KLASYFIKATORÓW, GDY ZBIORY TRENINGOWE I TESTOWE MAJĄ RÓŻNE ROZKŁADY

W niniejszym artykule przedstawiamy nową strategię uczenia się dla problemów, w których rozkłady statystyczne zbiorów treningowego i testowego są różne. Tę technikę można zastosować w problemach, w których występuje dryf koncepcji, błędy próbkowania lub inne zjawiska powodujące różnice w strukturze statystycznej zbiorów treningowego i testowego. Z drugiej strony, nasza strategia konstruuje jawne oszacowanie struktury statystycznej problemu w zbiorze danych testowych. Pozwala nam to skonstruować klasyfikator zoptymalizowany pod kątem nowych statystyk testowych i dostarczający użytkownikowi istotnych informacji o tym, które aspekty problemu uległy zmianie.

Algorytm

1. Skonstruuj model statystyczny { P~(x | c) , P~(c) } dla zbioru treningowego, stosując standardową procedurę (na przykład standardowy algorytm EM).
2. Przeprowadź ponowną estymację tego modelu statystycznego, wykorzystując nieoznaczone wzorce x ze zbioru testowego. W tym celu opracowaliśmy półnadzorowane rozszerzenie EM.
3. Użyj tego ponownie oszacowanego modelu statystycznego {P~ '(x | c) , P~ '(c) } do skonstruowania klasyfikatora zoptymalizowanego pod kątem zbioru testowego.

Reestymacja modelu: Półnadzorowane rozszerzenie metody EM

Standardowy algorytm EM (Dempster, Laird i Rubin, 1977) to iteracyjna procedura zaprojektowana w celu znalezienia optymalnych parametrów modelu statystycznego w ujęciu metody maksymalnego prawdopodobieństwa. W niniejszym artykule przedstawiamy rozszerzenie algorytmu EM, które reestymuje model statystyczny wyuczony w trakcie treningu, wykorzystując nieoznakowany zbiór testowy, przy założeniu, że powinien on przypominać model statystyczny wyuczony w trakcie treningu. Oznacza to, że algorytm znajduje minimalną wartość zmiany, jaką należy przyjąć dla modelu skonstruowanego w trakcie treningu (gdzie znane są klasy wzorców), aby wyjaśnić globalny rozkład atrybutów x w zbiorze testowym. Nazwijmy ? zbiorem różnych parametrów w modelu statystycznym naszego problemu. Na przykład, jeśli modelujemy P~(x c = 1) i P~(x c = 2) za pomocą mieszaniny odpowiednio dwóch i trzech rozkładów Gaussa, wówczas ? będzie składać się ze średnich, macierzy kowariancji i prawdopodobieństw 2+3 różnych rozkładów Gaussa w modelu. Oszacowanie ?Tr należy najpierw wykonać w zbiorze treningowym, stosując standardową technikę, taką jak zastosowanie EM dla każdej indywidualnej klasy. Następnie należy je przeliczyć na ?Te, używając nieoznaczonego zbioru testowego, optymalizując prawdopodobieństwo ~( ) P Te DTe, Tr, gdzie DTe to nieoznaczony zbiór testowy (wzorce testowe bez informacji o klasie). Maksymalizacja tej wielkości względem ?Te jest równoważna maksymalizacji wielkości L'? ln P~(DTe Te) + ln P~(Te Tr) którą nazwiemy "rozszerzonym logarytmem wiarygodności". Wyrażenie ~( ) P Te Tr implementuje błąd w reestymacji parametrów, który w naszym przypadku jest preferencją dla małych zmian. Wykorzystując ten rozszerzony logarytm wiarygodności, możliwe jest wyprowadzenie nowej wersji EM, która maksymalizuje L'. Aby to osiągnąć, rozważamy, podobnie jak w standardowych zastosowaniach EM, istnienie dodatkowych, ale ukrytych (lub "ukrytych") zmiennych h w problemie (Dempster, Laird i Rubin, 1977). Na przykład, jeśli modelujemy statystyki jako mieszaninę rozkładów Gaussa, zmienna ukryta wskazuje, który z rozkładów Gaussa faktycznie wygenerował wzór. Parametry naszego modelu statystycznego są zatem dwojakiego rodzaju: te a wpływające na rozkłady prawdopodobieństwa ukrytych zmiennych h i te b wpływające na pozostałe parametry modelu. Zatem ? = {a, b}. Na przykład, jeśli model statystyczny jest mieszaniną rozkładów Gaussa, a zawiera prawdopodobieństwa a priori różnych rozkładów Gaussa, a b składa się z macierzy średnich i macierzy kowariancji. Zakładamy, że człon penalizacji można zapisać jako:



Jesteśmy teraz w stanie opracować półnadzorowane rozszerzenie EM. Postępując zgodnie z tym samym schematem rozumowania, dochodzimy do następującego algorytmu.

1. Zainicjuj "Te ? Tr" i "Te ? Tr"
2. (Krok E): Oblicz dla wszystkich h i xi:



3. (Krok M):

Oblicz * Te, które maksymalizuje następującą wielkość (ustalając 'Te i 'Te):



Oblicz * Te, które maksymalizuje następującą ilość (ustalając 'Te i 'Te):



4. Zaktualizuj parametry: "Te ? *Te" i "Te ? *Te"

5. Przejdź do kroku 2, aż do osiągnięcia zbieżności L.

W tym wyprowadzeniu zagwarantowane jest również, że L' nie maleje na każdym kroku, więc nasz algorytm znajdzie co najmniej lokalne optimum L'. Z drugiej strony, człon penalizacji zapewni stabilność algorytmu (niewielkie zmiany w danych testowych prowadzą do niewielkich zmian w reestymacji) i pozwoli na powiązanie właściwej klasy z różnymi klastrami. Nasz algorytm zawiera jako przypadek szczególny standardowy algorytm EM, gdy rozkład ( ) C ~ P Te Tr nie jest brany pod uwagę lub jest zakładany jako jednorodny. W przykładach, które pokażemy w tym rozdziale, używamy prostego przypadku tego algorytmu, w którym model statystyczny składa się z jednego rozkładu Gaussa na klasę, a jedynie średnie rozkładów Gaussa są reestymowane. Wyraz penalizacji ln P ~ ( Te Tr) używany w tych przykładach jest proporcjonalny do odległości Mahalanobisa (Duda, Hart i Stork, 2001) między średnimi oszacowanymi w treningu i tymi reestymowanymi w teście (będziemy odnosić się do czynnika proporcjonalności jako g). Następnie dochodzimy do następującego uproszczonego algorytmu:

1. Zainicjuj '1, Te ? 1, Tr i '2, Te ? 2, Tr
2. (Krok E): Oblicz dla c=1,2 i wszystkich xi w zestawie danych testowych:



3. (Krok M):



i przejdź do kroku 2, aż do osiągnięcia zbieżności L′.

gdzie c?{1, 2} jest klasą wzorca; P~(c) jest prawdopodobieństwem a priori klasy c oszacowanym w zestawie treningowym; c, Tr i c, Te są średnimi wzorców klasy c odpowiednio w zestawach treningowym i testowym; Mc jest macierzą kowariancji klasy c oszacowaną w zestawie treningowym; ~p(x ,M) jest funkcją gęstości prawdopodobieństwa x, pod warunkiem, że została wygenerowana przez proces Gaussa średniej m i macierzy kowariancji M; d jest odjęciem średniej globalnej atrybutów w teście od średniej globalnej atrybutów w treningu; a NTe jest liczbą wzorców w teście.

Zastosowanie do problemu syntetycznego

Najpierw zilustrujemy nasz algorytm, wykorzystując prosty problem syntetyczny z dwiema klasami. W procesie uczenia klasę "szarą" wygenerowano z rozkładu Gaussa ze średnią [1,0; 1,0] i macierzą kowariancji [0,5; 0,0; 0,0; 0,5]; klasę "czarną" wygenerowano z rozkładu Gaussa ze średnią [1,0; 1,5] i macierzą kowariancji [0,5; 0,4; 0,4; 0,5]. Struktura statystyczna zbioru testowego różni się od struktury w procesie uczenia ze względu na przesunięcie klasy "czarnej" , która obecnie ma średnią [2,0; 1,0]. Minimalne błędy Bayesa zbioru uczącego i testowego wynoszą odpowiednio 27,7% i 18,8%. Najpierw konstruujemy model statystyczny zbioru treningowego składający się z jednego rozkładu Gaussa dla każdej klasy (rysunek 2c). Ten model statystyczny jest następnie wykorzystywany do konstruowania klasyfikatora w oparciu o liniową analizę dyskryminacyjną (LDA). Błąd tego klasyfikatora w trakcie treningu wynosi 34,1%. Po zastosowaniu do zbioru testowego, błąd tego klasyfikatora wzrasta do 66,0%. Nasz algorytm został następnie wykorzystany do ponownej estymacji modelu statystycznego zbudowanego w trakcie treningu z wykorzystaniem wzorców z nieoznakowanego zbioru testowego . Możemy zaobserwować, że nasz algorytm znajduje odpowiedni model statystyczny dla zbioru testowego. W rzeczywistości, po ponownym obliczeniu klasyfikatora LDA z wykorzystaniem ponownie oszacowanego modelu statystycznego, błąd w teście zmniejszył się do 20,5%.

Zastosowanie w diagnostyce chorób serca, gdy szpitale szkoleniowy i testowy różnią się

Przetestowaliśmy nasz algorytm, korzystając z bazy danych chorób serca z repozytorium uczenia maszynowego UCI . Celem jest przewidzenie, czy pacjent ma chorobę serca, czy nie, na podstawie danych osobowych (wiek, płeć, nałóg palenia tytoniu itp.) oraz wyników kilku badań medycznych, takich jak ciśnienie krwi i elektrokardiogramy. Baza danych chorób serca to w rzeczywistości połączenie czterech zestawów danych, z których każdy pochodzi z innego szpitala. Można by oczekiwać, że struktura statystyczna problemu będzie inna w różnych szpitalach, ponieważ pacjenci mieszkają w różnych miastach (a zatem czynniki środowiskowe mogą być różne), urządzenia pomiarowe nie są identyczne itp. Dlatego oczekujemy, że nasz algorytm poprawi wydajność klasyfikacji modelu zbudowanego w innym szpitalu. Sprawdziliśmy tę hipotezę, wykorzystując dane z Cleveland Clinic Foundation jako dane treningowe oraz dane z Węgierskiego Instytutu Kardiologii jako dane testowe. W obu przypadkach usunęliśmy atrybuty z kolumn 12 i 13, ponieważ często brakuje ich w węgierskim zestawie danych, i przeprowadziliśmy normalizację w każdym zestawie, tak aby atrybuty miały zerową średnią i wariancję jednostkową. Rezultatem jest 297 przykładów z Cleveland Clinic (149 z klasy 1, 148 z klasy 2) i 294 z Węgierskiego Instytutu Kardiologii (188 z klasy 1, 106 z klasy 2). Najpierw używamy PCA, aby zredukować wymiarowość problemu w zbiorze uczącym. Dlatego model statystyczny naszego problemu składa się teraz z macierzy średniej i kowariancji każdej klasy na osiach głównych. Następnie rozważany jest prosty klasyfikator, który przypisuje wzorcowi x klasę o najbliższym środku. Liczba głównych składowych jest automatycznie wybierana na podstawie wydajności klasyfikatora w losowym podzbiorze zbioru danych uczących, który został zarezerwowany dla tego zadania. Po skonstruowaniu modelu statystycznego zbioru uczącego, oceniliśmy wydajność klasyfikatora w zbiorze testowym, uzyskując wskaźnik błędu wynoszący 18,7%. W drugim kroku zastosowaliśmy nasz algorytm do reestymacji modelu statystycznego z wykorzystaniem ? = 0,01, a następnie sklasyfikowaliśmy wzorce testowe, stosując tę samą procedurę co poprzednio, czyli przypisując każdemu wzorcowi testowemu klasę z najbliższym środkiem. Błąd został w tym przypadku zredukowany do 15,3%. Jeśli powtórzymy tę samą strategię, używając bardziej rozbudowanego klasyfikatora, takiego jak oparty na liniowej analizie dyskryminacyjnej, zaobserwujemy zmniejszenie błędu z 17,0% do 13,9% po zastosowaniu naszego algorytmu.

PRZYSZŁE TRENDY

W przedstawionych tutaj przykładach zastosowaliśmy uproszczoną wersję naszego algorytmu, która zakłada model statystyczny składający się z jednego rozkładu Gaussa dla każdej klasy i wymaga jedynie ponownego oszacowania średnich za pomocą testu. Jednak nasze półnadzorowane rozszerzenie metody EM jest algorytmem ogólnym, który można stosować z dowolnymi parametrycznymi modelami statystycznymi (np. mieszaninami dowolnej liczby modeli niegaussowskich) i pozwala na ponowne oszacowanie dowolnego parametru modelu. Przyszłe prace będą obejmować badanie wydajności i odporności różnych typów modeli statystycznych w praktycznych problemach. Z drugiej strony, ponieważ nasze podejście opiera się na rozszerzeniu szeroko badanego standardowego algorytmu EM, oczekujemy, że możliwe będzie uzyskanie wyników analitycznych, takich jak granice błędu generalizacji, co uczyni algorytm atrakcyjnym również z perspektywy teoretycznej.

WNIOSKI

Zaprezentowaliśmy nową strategię uczenia się dla problemów klasyfikacyjnych, w których struktura statystyczna zbiorów uczących i testowych jest różna. W tego typu problemach wydajność tradycyjnych algorytmów uczenia maszynowego może ulec znacznemu pogorszeniu. Zaproponowano różne techniki radzenia sobie z różnymi aspektami problemu, takie jak strategie radzenia sobie z błędem doboru próby , strategie radzenia sobie z dryfem pojęć oraz uczenie transdukcyjne . Przedstawiona przez nas strategia uczenia się pozwala uwzględnić wszystkie te aspekty, dzięki czemu może być stosowana w problemach, w których występuje dryf pojęć, błędy próbkowania lub jakiekolwiek inne zjawiska powodujące różnice w strukturze statystycznej zbiorów uczących i testowych. Co więcej, nasz algorytm konstruuje jawny model statystyczny nowej struktury w zbiorze danych testowych, co jest niezwykle cenne dla zrozumienia dynamiki problemu i wykorzystania tej wiedzy w praktycznych zastosowaniach. Aby to osiągnąć, rozszerzyliśmy algorytm EM o wersję półnadzorowaną, która pozwala na reestymację modelu statystycznego zbudowanego w trakcie treningu z wykorzystaniem rozkładu atrybutów wzorców nieoznakowanego zbioru testowego.

WSTĘP

Automatyczna diagnostyka i prognozowanie nowotworów ośrodkowego układu nerwowego (OUN) stanowią ogromne wyzwanie ze względu na heterogeniczny fenotyp i genotyp komórek nowotworowych. Jednoznaczna charakterystyka tych guzów jest niezbędna dla dokładnego prognozowania i terapii. Chociaż obecne techniki obrazowania pomagają w badaniu cech anatomicznych guzów mózgu, nie zapewniają one skutecznego sposobu wczesnego wykrywania. Obecnie badanie histologiczne guzów mózgu jest powszechnie stosowane w celu postawienia trafnej diagnozy; jednak klasyfikacja i stopniowanie guza na podstawie wyglądu histologicznego nie zawsze gwarantują absolutną dokładność . W wielu przypadkach,wykrycie szczegółowych zmian na poziomie molekularnym za pomocą badania histologicznego może okazać się niewystarczające, ponieważ takie badanie może nie pozwolić na dokładne przewidywanie odpowiedzi terapeutycznej lub rokowania. Zbyt mała próbka biopsji dodatkowo pogłębia problemy. Aby osiągnąć bardziej wiarygodną diagnostykę i rokowanie guzów mózgu, pomiary ekspresji genów z mikromacierzy znajdują się w centrum uwagi wielu badaczy pracujących nad schematami predykcji guzów. Nasz proponowany schemat predykcji guzów omówiono w dwóch rozdziałach tego tomu. W części I (tym rozdziale) wykorzystujemy model analizy wariancji (ANOVA) do scharakteryzowania danych dotyczących ekspresji genów Affymetrix z próbek guzów ośrodkowego układu nerwowego , natomiast w części II omawiamy przewidywanie klas guzów na podstawie genów markerowych wybranych za pomocą technik opracowanych w tym rozdziale. W tym rozdziale szacujemy miary ekspresji genów specyficzne dla nowotworów w oparciu o model ANOVA i wykorzystujemy je do lokalizacji genów markerowych o istotnie zróżnicowanej ekspresji w różnych typach próbek guzów. Przedstawiamy również nowatorską metodę wizualizacji do walidacji procesu selekcji genów markerowych.

WSTĘP

Opracowano wiele metod statystycznych, które koncentrują się na problemie wyszukiwania genów markerowych o zróżnicowanej ekspresji w próbkach guzów . Na przykład Pomeroy i inni wykorzystują test t-Studenta do identyfikacji takich genów w próbkach guzów OUN u zarodków. Ze względu na nienormalność pomiarów ekspresji genów, wielu badaczy przyjęło stosowanie metod nieparametrycznych, takich jak test sumy rang Wilcoxona , jako solidną alternatywę dla procedur parametrycznych. W tym rozdziale badamy podejście typu Wilcoxona i dostosowujemy wynikające z niego procedury do lokalizacji genów markerowych. Zazwyczaj procedury statystyczne do analizy danych z mikromacierzy obejmują przeprowadzanie testów specyficznych dla genów. Ponieważ liczba rozważanych genów jest zazwyczaj duża, powszechną praktyką jest kontrolowanie potencjalnie dużej liczby fałszywie dodatnich wniosków i współczynników błędów rodzinnych (FWB) (prawdopodobieństwo wystąpienia co najmniej jednego fałszywie dodatniego stwierdzenia) poprzez zastosowanie korekt wartości p. Pollard oraz Van der Laan i zaproponowali metody kontroli współczynników błędów rodzinnych w oparciu o technikę resamplingu bootstrapowego Westfalla i Younga (1993). Benjamini i Hochberg (1995), Efron i inni (2001) oraz Storey i inni (2002, 2003a, 2003b, 2004) przedstawili różne techniki kontroli współczynnika fałszywych odkryć (FDR), który jest definiowany jako oczekiwany współczynnik fałszywego odrzucenia hipotezy zerowej o braku różnicowej ekspresji genów. Te techniki korekcji zyskały na znaczeniu w badaniach statystycznych dotyczących analizy danych z mikromacierzy. W niniejszym artykule stosujemy kontrolę FDR, ponieważ jest ona mniej konserwatywna niż wskaźniki błędów rodzinnych (FDM) w korygowaniu obserwowanych wartości p pod kątem fałszywych odkryć. Ponadto proponujemy nowatorską technikę wizualizacji genu markerowego, aby zbadać odpowiedni wybór punktu odcięcia w procesie selekcji genu markerowego. Przed przeprowadzeniem analizy formalnej należy zidentyfikować rzeczywiste poziomy ekspresji genów powiązane z różnymi grupami tkanek i odrzucić lub zminimalizować inne źródła zmienności. Takie podejście zaproponowali Townsend i Hartl (2002), którzy wykorzystują model bayesowski z małymi błędami zarówno mnożnikowymi, jak i addytywnymi, do wykrywania niewielkich, ale istotnych różnic w ekspresji genów. Alternatywnie, model ANOVA wydaje się naturalnym wyborem do szacowania rzeczywistej ekspresji genów . W kontekście danych z mikromacierzy cDNA, model ANOVA został po raz pierwszy zaproponowany przez Kerra.

TECHNIKI OCENY I WIZUALIZACJI EKSPRESJI GENÓW SPECYFICZNE DLA NOWOTWORÓW

Aby zilustrować naszą procedurę, wykorzystaliśmy dane z mikromacierzy zebrane przez Pomeroya dotyczące pacjentów z różnymi typami guzów zarodkowych. Wśród pacjentów znalazło się 60 dzieci z rdzeniakami zarodkowymi, 10 młodych dorosłych z glejakami złośliwymi, 5 dzieci z AT/RT, 5 z guzami rabdoidalnymi nerek/pozanerkowymi oraz 8 dzieci z nadnamiotowymi guzami neuroendokrynnymi (PNET). Najpierw wstępnie przetwarzamy dane, aby usunąć szum tła i efekty matrycowe. Przeskalowujemy surowe dane dotyczące ekspresji uzyskane z GeneChip firmy Affymetrix, aby uwzględnić różną intensywność chipów. Dane z mikromacierzy zazwyczaj charakteryzują się niepożądanymi źródłami zmienności, takimi jak fluktuacje intensywności w małej i dużej skali w obrębie plamek, nieaddytywne tło, artefakty produkcyjne, procedury sprzęgania i przetwarzania sond, przygotowanie celu i macierzy w procesie hybrydyzacji, tło i efekty nadmiernego świecenia oraz ustawienia skanera . W celu modelowania tych zmienności w literaturze opisano szereg metod. W naszej obecnej pracy zastosowano model ANOVA podobny do tego zastosowanego przez Kerra , który ułatwia uzyskanie miar ekspresji genów specyficznych dla guza na podstawie wstępnie przetworzonych danych z mikromacierzy. Nasz dwukierunkowy model ANOVA przedstawia się następująco:



gdzie, y_jgk oznacza logarytm miary ekspresji genu dla k-tej replikacji g-tego genu w j-tej grupie guzów (k = 1,…, K_j; g = 1,…, G; j = 1,…, J); μ α_g, β_j, γ_jg odnoszą się odpowiednio do ogólnego efektu, głównego efektu g-tego genu, głównego efektu j-tej grupy guzów i efektu interakcji g-tego genu z j-tą grupą guzów, a ε_jgk jest błędem losowym o zerowej średniej i stałej wariancji. Zakładamy, że te terminy są niezależne; jednak nie przyjmujemy żadnych założeń co do ich rozkładu. Ten model zakłada, że szum tła i efekty macierzy zostały wyeliminowane na poprzednich etapach wstępnego przetwarzania. To założenie dobrze pasuje do naszych wstępnie przetworzonych danych. Powodem wybrania tego modelu jest to, że dobrze pasuje on do naszego celu, jakim jest zbudowanie odpowiednich prototypów guzów do predykcji. Uważamy, że prototypy guzów powinny być budowane wyłącznie w oparciu o specyficzne dla guza miary ekspresji genów. W tym modelu termin interakcji γ_jg stanowi rzeczywistą ekspresję genu g przypisywaną typowi guza j. Zatem wartość wkładu k-tej replikacji pomiaru genu g w tkance j do wartości ekspresji genu specyficznej dla guza można zapisać zgodnie z :



a ekspresję specyficzną dla guza szacuje się za pomocą równania (3):



gdzie,

? są najmniejszymi kwadratowymi oszacowaniami głównych efektów g-tego genu i j-tej grupy nowotworów w oparciu o replikacje. W niniejszym opisie traktujemy te oszacowania jako oszacowania efektów stałych. W analizie bayesowskiej wszystkie parametry można traktować jako efekty losowe. Wartości są brane pod uwagę w kolejnych krokach analizy wpływu k replikacji na ekspresję genu g u pacjenta z j-tej grupy nowotworów. Stosując kilka różnych procedur, takich jak test Shapiro-Wilka i wykresy prawdopodobieństwa normalnego, obserwujemy, że poziomy ekspresji genu w naszym zbiorze danych nie mają rozkładu normalnego. Dlatego w naszym zbiorze danych wybraliśmy test nieparametryczny, taki jak Wilcoxon dla problemu dwóch kategorii i Kruskala-Wallisa dla problemu pięciu kategorii, aby zidentyfikować znacząco różnicowo ekspresjonowane geny wśród typów próbek tkanek. Dostosowujemy wielość zastosowanych testów, kontrolując współczynnik fałszywych odkryć (FDR) za pomocą wartości q, zgodnie z propozycją Storeya. Przy wyborze różnicowo ekspresjonowanych genów, ścisłe odcięcie może pominąć niektóre ważne geny markerowe, podczas gdy hojny próg zwiększa liczbę wyników fałszywie dodatnich. Aby rozwiązać ten problem, wykorzystaliśmy równoległy wykres współrzędnych średnich ekspresji genów dla poszczególnych grup. Na tym wykresie równoległe i równomiernie rozmieszczone osie reprezentują poszczególne geny. Dla każdej grupy próbek guzów narysowano oddzielne linie łamane. Im bardziej średnie poziomy ekspresji genów różnią się między grupami, tym więcej miejsca pojawia się między liniami łamanymi na wykresie. Aby skutecznie zwizualizować geny o zróżnicowanej ekspresji, najpierw obliczamy średnią wartości ekspresji genów specyficznych dla guza w dowolnym konkretnym typie próbki tkanki , zgodnie z równaniem (3). Następnie standaryzujemy średnie wartości ekspresji genów uzyskane w równaniu (3) w następujący sposób:

gdzie i Następnie dzielimy geny na dwie grupy. Pierwsza grupa składa się z genów, dla których , a pozostałe geny pozostają w drugiej grupie. Grupujemy je tak, aby linie reprezentujące typ guza na naszym wykresie się nie przecinały. Teraz, w obrębie każdej grupy genów, ponownie dzielimy geny na podgrupy, tak aby geny o podobnej ekspresji były grupowane razem. Do tego podziału wykorzystujemy podejście analizy wariancji oparte na samoorganizującej się mapie (SOM) Następnie, w obrębie każdej z podgrup, geny są porządkowane zgodnie z ?. Ta dalsza metoda podziału i porządkowania nadaje odpowiednie kształty liniom reprezentującym typ guza, dzięki czemu użytkownik może szybko zwizualizować zdolność rozróżniania typu guza przez wybrane geny. Przed wygenerowaniem ostatecznego wykresu normalizujemy standaryzowane średnie wartości ekspresji ? w następujący sposób:



Na koniec, znormalizowane wartości ekspresji są wykreślane za pomocą współrzędnych równoległych, gdzie każda oś równoległa odpowiada konkretnemu genowi, a każda linia łamana konkretnemu typowi guza. Podgrupy każdego genu są wykreślane na oddzielnych wykresach. Algorytm 1 określa nasze sformalizowane podejście do wizualizacji genów. Celem takich wykresów jest jakościowy pomiar wydajności procesu selekcji genów i znalezienie odpowiedniego punktu odcięcia, który zmniejsza liczbę wyników fałszywie dodatnich, jednocześnie utrzymując wysoką liczbę wyników prawdziwie dodatnich. Poniższe wyniki ilustrują użyteczność naszej metody wizualizacji przedstawionej w Algorytmie 1. Wzory ekspresji genów markerowych związanych z grupami przeżycia i niepowodzenia leczenia rdzeniaka zarodkowego przedstawiono na rysunkach 2 i 3.

Linie ciągłe i przerywane reprezentują odpowiednio grupę niepowodzenia (zgonu) i przeżycia (życia). Geny są wybierane za pomocą metody Wilcoxona, która została wcześniej opisana, w której w zależności od wartości q, wybierana jest różna liczba genów. Na obu rysunkach Na rysunkach 2 i 3, każdy indywidualny wykres przedstawia grupę genów o podobnej ekspresji, zgrupowanych razem, zgodnie z krokiem 5 Algorytmu 1. Rysunki 2 i 3 przedstawiają odpowiednio 280 i 54 wybrane geny markerowe. Obserwujemy, że spośród 280 wybranych genów na rys. 2, wiele z nich wykazuje podobne wzorce ekspresji zarówno w grupie próbek z niepowodzeniem, jak i z przeżyciem, co wskazuje, że dwie grupy próbek znajdują się blisko siebie na osiach równoległych. Ponieważ każda oś przedstawia inny gen, wnioskujemy, że wiele genów na rys. 2 jest błędnie zidentyfikowanych jako geny markerowe (fałszywie dodatnie). Dla porównania, linie ciągłe i przerywane są od siebie oddalone na większości osi równoległych na rys. 3. Oznacza to, że średnie wartości ekspresji genów dla wybranych 54 genów znacznie różnią się między dwiema grupami próbek tkanek. Zatem ta wizualizacja pomaga w wyborze prawidłowego progu w procesie selekcji genów markerowych.

PRZYSZŁE TRENDY

W tym rozdziale szacujemy miary ekspresji genów specyficzne dla guza, wykorzystując model ANOVA. Parametry modelu określamy jako efekty stałe; jednak taka specyfikacja może nie zawsze być odpowiednia. Zamiast tego, traktowanie parametrów modelu jako efektów losowych może być bardziej odpowiednie dla zbioru danych mikromacierzy (Kerr i in., 2000). Zatem jednym z możliwych ulepszeń może być traktowanie wszystkich efektów w naszym modelu ANOVA jako losowych. Ponadto, określenie parametrów efektów losowych w ramach analizy bayesowskiej zapewnia formalny sposób wykorzystania wszelkiej wcześniejszej wiedzy na temat rozkładu parametrów, jeśli jest ona dostępna. Obecnie jesteśmy w trakcie wdrażania hierarchicznego podejścia bayesowskiego w naszej pracy, zgodnie z kilkoma nowszymi, istotnymi pracami.

WNIOSKI

Podjęliśmy próbę oszacowania specyficznych dla guza miar ekspresji genów za pomocą modelu ANOVA. Oszacowania te są następnie wykorzystywane do identyfikacji genów markerowych o zróżnicowanej ekspresji. W celu oceny identyfikacji genów markerowych zaproponowaliśmy nowatorskie podejście do wizualizacji średnich wartości ekspresji genów dla określonego typu tkanki. Proponowany wykres wizualizacji jest przydatny do jakościowej oceny skuteczności metod selekcji genów markerowych, a także do określenia odpowiednich punktów odcięcia w procesie selekcji. Badania opisane w tym rozdziale zostały częściowo sfinansowane z grantów badawczych udzielonych przez Fundację Whitakera, a głównym badaczem był Khan M. Iftekharuddin.

WSTĘP

W tym rozdziale proponujemy nowatorski algorytm charakteryzowania różnych nowotworów ośrodkowego układu nerwowego. Proponowany algorytm zilustrowano analizą danych o ekspresji genów uzyskanych z próbek guzów ośrodkowego układu nerwowego za pomocą aplikacji Affymetrix. Jak omówiono w poprzednim rozdziale zatytułowanym: Prognozowanie nowotworów ośrodkowego układu nerwowego z wykorzystaniem danych o ekspresji genów, część I, wykorzystaliśmy model ANOVA do normalizacji pomiarów ekspresji genów na mikromacierzach. W tym rozdziale przedstawiamy systemowy sposób budowania prototypów guzów, aby ułatwić automatyczne prognozowanie nowotworów ośrodkowego układu nerwowego.

WSTĘP

Mikromacierze DNA, znane również jako genom lub chipy DNA, stały się ważnym narzędziem do przewidywania typów nowotworów ośrodkowego układu nerwowego. Kilku badaczy wykazało, że analiza klastrowa danych ekspresji genów uzyskanych z mikromacierzy DNA jest pomocna w znajdowaniu funkcjonalnie podobnych genów, a także w przewidywaniu różnych typów nowotworów. Eisen i inni (1998) zastosowali hierarchiczną klasteryzację sprzężeń średnich ze współczynnikiem korelacji jako miarę podobieństwa w porządkowaniu wartości ekspresji genów z danych z mikromacierzy. Wykazali, że funkcjonalnie podobne geny grupują się w ten sam klaster. Herwig i inni (1999) zaproponowali wariant algorytmu k-średnich do grupowania genów klonów cDNA. Tomayo i inni (1999) wykorzystali samoorganizujące się mapy cech (SOFM) do porządkowania genów w biologicznie istotne grupy. Stwierdzili, że modele SOFM ujawniają rzeczywistą strukturę klastrów w porównaniu ze sztywną strukturą hierarchicznego klasteryzacji i bezstrukturalnego podejścia K-średnich. Biorąc pod uwagę relacje wiele do wielu między genami a ich funkcjami, Dembele i inni (2003) zaproponowali rozmytą technikę klasteryzacji C-średnich. Głównym celem tych procedur klasteryzacji było grupowanie genów na podstawie ich funkcjonalności. Jednak żadna z tych prac nie oferuje systematycznego sposobu odkrywania lub przewidywania grup próbek tkanek, jak proponujemy w naszej obecnej pracy. Aby zidentyfikować grupy próbek tkanek, Alon i inni (1999) zaproponowali algorytm klasteryzacji, który wykorzystuje algorytm wyżarzania deterministycznego do organizacji danych w drzewie binarnym. Alizadeh i inni. (2000) zaprezentowali skuteczny schemat klasyfikacji molekularnej nowotworów na podstawie wzorców ekspresji genów, wykorzystując algorytm hierarchicznego klasteryzacji sprzężeń średnich z korelacją Pearsona jako miarą podobieństwa. Jednakże w pracach nie opisano formalnego sposobu przewidywania kategorii nowej próbki tkanki. Takie problemy z przewidywaniem klas zostały rozwiązane przez Goluba i innych (1999), którzy wykorzystali modele SOFM do skutecznego rozróżnienia dwóch typów ostrej białaczki u ludzi. Dettling i inni (2002) włączyli zmienne odpowiedzi do klasteryzacji genów i zlokalizowali grupy genów o zróżnicowanej ekspresji na podstawie wyników klasteryzacji. Te grupy genów zostały następnie wykorzystane do przewidywania kategorii nowych próbek. Jednakże żadna z wyżej wymienionych prac nie uwzględniała korelacji między genami w klasyfikacji i/lub przewidywaniu próbek tkanek. Co więcej, żadna z nich nie przedstawiła systematycznego sposobu postępowania z prawdopodobnymi podgrupami w obrębie znanych grup. W tym rozdziale rozważamy zarówno korelacje między genami, jak i prawdopodobne podgrupy w obrębie znanych grup, tworząc odpowiednie prototypy guzów. Co więcej, poważną wadą tych analiz jest niewystarczająca normalizacja. Chociaż większość tych metod normalizuje zbiór danych w celu usunięcia efektów macierzy, nie koncentrują się one na usuwaniu innych źródeł zmienności obecnych w danych z mikromacierzy. Naszym głównym celem w tym rozdziale jest opracowanie zautomatyzowanego schematu predykcji dla guzów ośrodkowego układu nerwowego, opartego na ekspresji genów z mikromacierzy DNA w próbkach tkanek. Proponujemy nowy algorytm do tworzenia prototypów dla różnych typów guzów ośrodkowego układu nerwowego, w oparciu o dane dotyczące ekspresji genów z mikromacierzy Affymetrix HuGeneFL pochodzące od Pomeroy i in. (2002). Klasyfikując próbki guzów OUN na podstawie ekspresji genów, bierzemy pod uwagę informacje molekularne, takie jak korelacje między ekspresją genów i prawdopodobnymi podgrupami w obrębie znanych typów histologicznych guzów. Pokazujemy, jak ten model można wykorzystać do przewidywania guzów OUN.

PROTOTYP GUZA OUN DO AUTOMATYCZNEGO WYKRYWANIA GUZÓW

Schemat budowy prototypów guzów przedstawiono na rysunku.



W pierwszym kroku uzyskujemy miary ekspresji genów specyficzne dla typu guza. Następnie identyfikujemy geny markerowe, których ekspresja jest istotnie zróżnicowana w zależności od typu tkanki. Następnie, za pomocą techniki wizualizacji, analizujemy trafność procesu selekcji genu markerowego. Organizujemy geny markerowe w grupy, tak aby geny silnie skorelowane były grupowane razem. W tym procesie klasteryzacji geny są grupowane na podstawie miar ekspresji genów specyficznych dla typu guza. Następnie uzyskujemy miary ekspresji genów własnych dla każdej indywidualnej grupy genów poprzez projekcję ekspresji genów na kilka pierwszych głównych składowych. Na koniec tego etapu zastępujemy pomiary ekspresji genów wartościami ekspresji genów własnych, które zachowują korelacje między silnie skorelowanymi genami. Następnie dzielimy próbki tkanek znanych typów guzów na podgrupy. Centroidy tych podgrup próbek tkanek z ekspresją genów własnych reprezentują prototyp odpowiadającego im typu guza. Ostatecznie, każda nowa próbka tkanki jest przewidywana jako typ guza najbliższego centroidu. Ten proponowany, nowatorski schemat predykcji uwzględnia zarówno korelację między silnie skorelowanymi genami, jak i prawdopodobną podgrupę fenotypową w obrębie znanych typów guzów. Kwestie te są często pomijane w literaturze w kontekście przewidywania kategorii guzów. Szczegółowe informacje na temat etapów poprzedzających identyfikację genów markerowych przedstawiono w poprzednim rozdziale zatytułowanym: "Przewidywanie guzów ośrodkowego układu nerwowego z wykorzystaniem danych o ekspresji genów, część I". W tej sekcji przedstawiamy szczegóły kolejnych etapów. Teraz omówimy tworzenie prototypów guzów, wykorzystując specyficzne dla guza wartości ekspresji naszych genów markerowych o znacząco zróżnicowanej ekspresji, zidentyfikowanych w poprzednim etapie. Wiele genów markerowych prawdopodobnie jest silnie skorelowanych. Takie korelacje genów wpływają na pomyślną klasyfikację guza. Jednak ta korelacja między genami może dostarczyć ważnych informacji biologicznych. W związku z tym uwzględnienie odpowiednich korelacji między genami w modelu guza może pomóc w uzyskaniu bardziej biologicznie znaczącej prognozy guza. Aby sprostać tej nietrywialnej potrzebie, najpierw grupujemy silnie skorelowane geny, stosując hierarchiczne podejście pełnego sprzężenia, w którym współczynnik korelacji jest traktowany jako miara podobieństwa par genów. Następnie, dla każdego z klastrów, obliczamy główne składowe (PC) i rzutujemy geny odpowiadającego klastra na pierwsze 3 PC, aby uzyskać ekspresje genów własnych. Należy zauważyć, że PC i ekspresje genów własnych są obliczane oddzielnie dla każdego klastra. Takie geny własne kodują informacje o korelacji między silnie skorelowanymi genami, które są zgrupowane razem. Ostatnio opisano molekularnie odrębne podgrupy w obrębie tego samego typu histologicznego guza (Taylor i in., 2005). Aby znaleźć podgrupowanie w obrębie tego samego typu histologicznego guza, ponownie wykorzystujemy mapy samoorganizujące (SOM) do grupowania próbek tkanek w obrębie każdej grupy guzów. To podgrupowanie w obrębie każdej grupy odzwierciedla możliwe zróżnicowanie genotypowe w obrębie tego samego typu histologicznego guza. Teraz prototyp dowolnego określonego typu histologicznego guza składa się z centroidu uzyskanego z odpowiedniej siatki SOM. Algorytm 1 przedstawia kroki budowy prototypu guza. Aby przewidzieć kategorię guza dowolnej nowej próbki, obliczamy odległości między nową próbką a każdą z prototypowych podgrup uzyskanych za pomocą Algorytmu 1. Kategoria próbki jest przewidywana jako kategoria najbliższej podgrupy. Odległość między nową próbką a x-tą podgrupą, dx, jest obliczana na podstawie odległości euklidesowej w następujący sposób:



gdzie jest wartością środkową k-tego genu własnego w x-tej podgrupie, g_k jest miarą ekspresji k-tego genu własnego nowej próbki, a N jest całkowitą liczbą genów własnych. Ta miara odległości celowo ignoruje niereprezentatywne korelacje między ekspresjami genów własnych, ponieważ nie są one naturalne i dlatego trudne do interpretacji. Tabela 1 przedstawia skuteczność naszego modelu w klasyfikowaniu pięciu kategorii tkanek jednocześnie. Obserwujemy, że nasz schemat predykcji przewyższa inną metodę predykcji we wszystkich trzech przypadkach. Najbardziej zauważalna różnica występuje w grupie danych C, gdzie uzyskujemy 100% dokładność predykcji w porównaniu z 78% dokładnością.

PRZYSZŁE TRENDY

W niniejszej pracy oszacowaliśmy miarę ekspresji genów specyficzną dla guza, wykorzystując model ANOVA z parametrami jako efektami stałymi. Jak omówiono w sekcji dotyczącej przyszłych trendów w rozdziale zatytułowanym: "Prognozowanie guzów ośrodkowego układu nerwowego z wykorzystaniem danych o ekspresji genów, część I", możemy traktować wszystkie efekty w naszym modelu ANOVA jako losowe i określić parametry efektów losowych w ujęciu bayesowskim. Po uzyskaniu rozkładów miar ekspresji genów specyficznych dla guza z zadowalającą pewnością, możliwe będzie uzyskanie bardziej reprezentatywnych prototypów guzów i sformalizowanie dokładniejszego schematu prognozowania guza. Reprezentacja prototypów guzów za pomocą mieszaniny modeli Gaussa może zapewnić lepszą reprezentację. W takim przypadku określenie liczby składników w mieszaninie jest kolejnym zagadnieniem badawczym pozostawionym do dalszych prac.

WNIOSKI

W celu automatycznej predykcji guza zaproponowaliśmy nowy algorytm do budowy prototypów guzów ośrodkowego układu nerwowego w oparciu o wartości ekspresji genów z mikromacierzy Affymetrix. Wygenerowaliśmy prototypy dla różnych typów histologicznych guzów, uwzględniając ich heterogeniczność genotypową w obrębie grup. Geny własne kodują korelacje między ekspresjami genów w prototypach. Ponadto, miary ekspresji genów własnych pochodzą z oszacowanych miar ekspresji genów specyficznych dla guza, które są wolne od innych niepożądanych źródeł zmienności. Zaproponowaliśmy nowatorską, płynną procedurę, która integruje normalizację i predykcję guza, uwzględniając zarówno prawdopodobne podgrupowania w obrębie znanych typów guzów, jak i prawdopodobne korelacje między genami. Silna zgodność naszych wyników z aktualną klasyfikacją molekularną dostępnych typów guzów sugeruje, że nasz proponowany model i jego unikalne rozwiązanie mają istotną wartość praktyczną w automatycznym wykrywaniu guzów ośrodkowego układu nerwowego. Badania w tym rozdziale zostały częściowo sfinansowane z grantów badawczych [RG-01-0125, TG-04-0026] udzielonych przez Fundację Whitakera, a głównym badaczem był Khan M. Iftekharuddin.