WSTĘP

Podstawowym celem modelowania systemów jest ustanowienie reprezentatywnego odwzorowania wejścia-wyjścia, które może zadowalająco opisać zachowania systemu, wykorzystując dostępne dane wejścia-wyjścia oparte na fizycznej lub empirycznej wiedzy o strukturze nieznanego systemu.

WSTĘP

Konwencjonalne techniki modelowania systemów sugerują konstruowanie modelu opisanego za pomocą zestawu równań różniczkowych lub różnicowych. To podejście jest skuteczne tylko wtedy, gdy system bazowy jest dobrze zdefiniowany matematycznie i precyzyjnie wyrażalny. Często nie radzą sobie one z niepewnymi, niejasnymi lub źle zdefiniowanymi systemami fizycznymi, a mimo to większość rzeczywistych problemów nie podlega tak precyzyjnym, wyidealizowanym i subiektywnym regułom matematycznym. Zgodnie z zasadą niekompatybilności , wraz ze wzrostem złożoności systemu maleje zdolność człowieka do formułowania precyzyjnych i znaczących stwierdzeń na temat jego zachowań, aż do osiągnięcia progu, po przekroczeniu którego precyzja i znaczenie stają się niemożliwe. Zgodnie z tą zasadą Zadeh (1973) zaproponował metodę modelowania ludzkiego myślenia za pomocą liczb rozmytych, a nie liczb ścisłych, co ostatecznie doprowadziło do późniejszego rozwoju różnych technik modelowania rozmytego.

GŁÓWNY CEL

Identyfikacja struktury

W identyfikacji struktury modelu rozmytego pierwszym krokiem jest wybór odpowiednich zmiennych wejściowych ze zbioru możliwych zmiennych wejściowych systemu; drugim krokiem jest określenie liczby funkcji przynależności dla każdej zmiennej wejściowej. Proces ten jest ściśle związany z partycjonowaniem przestrzeni wejściowej. Metody partycjonowania przestrzeni wejściowej są przydatne do określania takich struktur.

Partycjonowanie siatki



Rysunek (a) przedstawia typowy podział siatki w dwuwymiarowej przestrzeni wejściowej. Siatki rozmyte można wykorzystać do generowania reguł rozmytych na podstawie danych treningowych wejścia-wyjścia systemu. Ponadto, procedura budowania w jednym przejściu pozwala uniknąć czasochłonnego procesu uczenia, ale jej wydajność w dużym stopniu zależy od definicji siatki. Zasadniczo, im drobniejsza siatka, tym lepsza wydajność. Adaptacyjna siatka rozmyta może zostać wykorzystana do udoskonalenia, a nawet optymalizacji tego procesu. W podejściu adaptacyjnym do inicjalizacji można użyć siatki równomiernie podzielonej. W miarę postępu procesu parametry w funkcjach przynależności poprzedników będą dostosowywane. W rezultacie siatka rozmyta ewoluuje. Następnie można zastosować metodę gradientu prostego do optymalizacji rozmiaru i położenia obszarów siatki rozmytej oraz stopnia ich nakładania się. Główną wadą tej metody podziału siatki jest to, że wydajność cierpi z powodu wykładniczego wzrostu liczby zmiennych wejściowych lub funkcji przynależności wraz ze wzrostem zmiennych wejściowych, znanego jako "klątwa wymiarowości", co jest częstym problemem większości metod podziału.

Podział drzewa

Rysunek (b) przedstawia wizualizację podziału drzewa. Podział drzewa jest wynikiem serii cięć gilotynowych. Każdy region jest generowany przez cięcie gilotynowe, które jest wykonywane w całej podprzestrzeni, która ma zostać podzielona. W (k - 1)-ej iteracji przestrzeń wejściowa jest dzielona na k regionów. Następnie do jednego z tych regionów stosuje się cięcie gilotynowe, aby dodatkowo podzielić całą przestrzeń na k + 1 regionów. Istnieje kilka strategii określania, który wymiar wyciąć, gdzie ciąć w każdym kroku i kiedy zakończyć. Ten elastyczny algorytm podziału drzewa rozwiązuje problem przekleństwa wymiarowości. Jednak dla każdej zmiennej wejściowej potrzeba więcej funkcji przynależności, które zazwyczaj nie mają jasnego znaczenia językowego; Co więcej, powstały w ten sposób model rozmyty jest mniej opisowy.

Podział rozproszony

Rysunek (c) ilustruje podział rozproszony. Ta metoda wyodrębnia reguły rozmyte bezpośrednio z danych liczbowych . Załóżmy, że dostępne są jednowymiarowe dane wyjściowe, y, i m-wymiarowy wektor wejściowy, x. Najpierw przestrzeń wyjściowa jest dzielona na n przedziałów, [y₀, y₁], (y₁, y₂], …, (y_n-1, y_n], gdzie i-ty przedział nazywany jest "przedziałem wyjściowym i". Następnie określane są hiperboki aktywacji, które definiują obszar wejściowy odpowiadający przedziałowi wyjściowemu i, poprzez obliczenie minimalnych i maksymalnych wartości danych wejściowych dla każdego przedziału wyjściowego. Jeśli hiperbok aktywacji dla przedziału wyjściowego i nakłada się na hiperbok aktywacji dla przedziału wyjściowego j, to nakładający się obszar jest definiowany jako hiperbok hamowania. Jeśli dane wejściowe dla przedziałów wyjściowych i i/lub j istnieją w hiperboku hamowania, to w tym hiperboku hamowania zostanie zdefiniowany jeden lub dwa dodatkowe hiperboki aktywacji. Ponadto, jeśli zdefiniowane są dwa hiperboki aktywacji i nakładają się one, to dodatkowo definiowany jest dodatkowy hiperbok hamowania. Ta procedura jest powtarzana, aż do rozwiązania problemu nakładania się.

Identyfikacja parametrów

Po określeniu struktury systemu, konieczna jest identyfikacja parametrów. W tym procesie, za pomocą technik optymalizacyjnych, poszukuje się optymalnych parametrów modelu rozmytego, które najlepiej opisują zachowanie wejścia-wyjścia systemu bazowego. Czasami struktura i parametry są identyfikowane w ramach tych samych ram, za pomocą modelowania rozmytego. Istnieje praktycznie wiele różnych podejść do modelowania systemu z wykorzystaniem teorii zbiorów rozmytych i teorii systemów rozmytych , ale najpopularniejsze są klasyczne techniki optymalizacji metodą najmniejszych kwadratów i ogólne techniki optymalizacji algorytmów genetycznych (GA). Są one dość uniwersalne, skuteczne i konkurencyjne w porównaniu z innymi skutecznymi metodami modelowania opartymi na optymalizacji, takimi jak sieci neuronowe i statystyczna metoda Monte Carlo.

Podejście wykorzystujące optymalizację metodą najmniejszych kwadratów

System rozmyty można opisać za pomocą następującej ogólnej postaci:



gdzie są stałymi współczynnikami a



są funkcjami bazowymi, w których μ_Xkj(⋅) są wybranymi funkcjami przynależności. Załóżmy, że rzeczywisty wynik systemu to



gdzie y(t) jest wyjściem systemu, a e(t) reprezentuje błąd modelowania, który w tej dyskusji zakłada się jako nieskorelowany z rozmytymi funkcjami bazowymi {g_k(⋅)^m_k=1. Załóżmy, że podano n par danych wejściowych i wyjściowych systemu: (x_d(t_i), y_d(t_i)), i = 1,…,n. Celem jest znalezienie najlepszych możliwych rozmytych funkcji bazowych, tak aby zminimalizować całkowity błąd najmniejszych kwadratów między zbiorem danych a wyjściami systemu w {y(t_i)ⁿ_i=1. Aby to zrobić, model liniowy (3) jest najpierw zapisany w postaci macierzowej w dziedzinie czasu t₁ < … < t_n, mianowicie:



gdzie , i



gdzie g_j = [g_j(t₁), …, g_j(t_n)]^T, j = 1, ˇ…, n.

Pierwszym krokiem jest przekształcenie zbioru liczb, g_i(t_j), i = 1, …, m, j = 1, …, n, w zbiór ortogonalnych wektorów bazowych, a do utworzenia ostatecznej optymalizacji metodą najmniejszych kwadratów używane są tylko istotne wektory bazowe. W tym przypadku funkcje przynależności Gaussa



służą jako przykład ilustrujący algorytm obliczeniowy. Jednym ze sposobów inicjalizacji rozmytych funkcji bazowych jest wybranie n początkowych funkcji bazowych, g_k(x), w postaci (2) z m = n w tej dyskusji i początkowo z c_kj = 1, i



gdzie m_l to liczba funkcji bazowych w wyrażeniu końcowym, którą projektant określa na podstawie doświadczenia (zwykle m_l < n). Po wybraniu początkowych rozmytych funkcji bazowych, kolejnym krokiem jest wybór spośród nich tych najbardziej znaczących. Proces ten opiera się na klasycznej ortogonalizacji Grama-Schmidta, a i σ_kj są stałe:

Krok 1. Dla j = 1, oblicz



są zbiorem danych wejściowych i wyjściowych. Następnie oblicz



a potem



Krok 2. Dla każdego j, 2 ? j ? ml, oblicz



gdzie ε⁽ⁱ⁾_j reprezentuje współczynnik redukcji błędów wynikający z . Wybierz



Krok 3. Rozwiąż równanie



dla rozwiązania gdzie i

Końcowy wynik uzyskuje się jako



Podejście wykorzystujące algorytmy genetyczne

Procedura identyfikacji parametrów jest zazwyczaj bardzo żmudna w przypadku złożonych systemów o dużej skali, w których podejście algorytmów genetycznych oferuje pewne atrakcyjne cechy, takie jak duża elastyczność i solidne możliwości optymalizacji . GA przypisuje się Hollandowi (1975), który zastosował ją do modelowania rozmytego i sterowania rozmytego w latach 80. XX wieku. GA może być używane do znajdowania optymalnego lub suboptymalnego modelu rozmytego opisującego dany system bez konieczności ręcznego projektowania . Ponadto metodę modelowania rozmytego algorytmów genetycznych można zintegrować z innymi komponentami systemu rozmytego, aby osiągnąć ogólnie lepszą wydajność w sterowaniu i automatyzacji.

Podstawy algorytmu genetycznego

GA zapewnia metodę optymalizacji z algorytmem przeszukiwania stochastycznego, opartą na kilku powszechnych biologicznych zasadach selekcji, krzyżowania i mutacji. Algorytm GA koduje każdy punkt w przestrzeni rozwiązań w ciąg składający się z wartości binarnych lub rzeczywistych, zwany chromosomem. Każdemu punktowi przypisuje się wartość dopasowania od zera do jednego, którą zazwyczaj przyjmuje się za taką samą jak funkcja celu, która ma być maksymalizowana. Schemat GA utrzymuje zbiór punktów jako populację, która jest wielokrotnie ewoluowana w kierunku lepszej i potencjalnie najlepszej wartości dopasowania. W każdym pokoleniu GA generuje nową populację za pomocą operatorów genetycznych, takich jak krzyżowanie i mutacja. Dzięki tym operacjom osobniki o wyższych wartościach dopasowania mają większe szanse na przeżycie i udział w kolejnych operacjach genetycznych. Po kilku pokoleniach osobniki o wyższych wartościach dopasowania pozostają w populacji, podczas gdy pozostałe są eliminowane. GA może zatem zapewnić stopniowe zwiększanie liczby ulepszonych rozwiązań, aż do uzyskania pożądanego rozwiązania optymalnego lub suboptymalnego.

Podstawowe elementy GA

Prosty algorytm genetyczny (SGA) został po raz pierwszy opisany przez Goldberga (1989) i jest tutaj użyty do ilustracji, z pseudokodem pokazanym poniżej, gdzie populacja w czasie t jest funkcją czasu, P = P(t), z losową populacją początkową P(0).

Procedura GA

Rozpocznij
t = 0
Inicjuj P(t)
Oceń P(t)
Dopóki nie zostanie zakończone, wykonaj
Rozpocznij
t = t + 1
Odtwórz P(t) z P(t - 1)
Pospolity osobnik w P(t)
Mutuj osobniki w P(t)
Oceń P(t)
Koniec
Koniec

Reprezentacja i inicjalizacja populacji

Osoby są kodowane jako ciągi znaków (tj. chromosomy) składające się z pewnych alfabetów, dzięki czemu genotypy (wartości chromosomów) są jednoznacznie mapowane na domenę zmiennych decyzyjnych (fenotyp). Najczęściej używaną reprezentacją w algorytmie genetycznym jest alfabet binarny, {0,1}; inne to alfabet trójkowy, całkowity, liczbowy itd. Proces wyszukiwania, opisany poniżej, będzie operował na tych kodujących zmiennych decyzyjnych, a nie na samych zmiennych decyzyjnych, z wyjątkiem sytuacji, gdy używane są geny o wartościach rzeczywistych. Po wybraniu metody reprezentacji, pierwszym krokiem w algorytmie genetycznym populacji (SGA) jest utworzenie populacji początkowej poprzez wygenerowanie wymaganej liczby osobników za pomocą generatora liczb losowych, który równomiernie rozprowadza liczby początkowe w pożądanym zakresie.

Funkcje celu i dopasowania

Funkcja celu służy do pomiaru wydajności osobników w domenie problemu. Funkcja dopasowania służy do przekształcenia wartości funkcji celu w miarę dopasowania względnego; matematycznie F(x) = g(f(x)), gdzie f to funkcja celu, g to transformacja, która odwzorowuje wartość f na liczbę nieujemną, a F to wynikowe dopasowanie względne. Ogólnie rzecz biorąc, wartość funkcji dopasowania odpowiada liczbie potomstwa, a osobnik może oczekiwać uzyskania tej wartości w następnym pokoleniu. Powszechnie stosowaną transformacją jest proporcjonalne przypisanie dopasowania, zdefiniowane wzorem



gdzie N to wielkość populacji, a xi to wartość fenotypowa osobnika i, i = 1,…, N. Chociaż powyższe przypisanie sprawności zapewnia, że każdy osobnik ma określone prawdopodobieństwo reprodukcji zgodnie z jego względnym dostosowaniem, nie uwzględnia ono ujemnych wartości funkcji celu. Przed przypisaniem sprawności często stosuje się transformację liniową, która kompensuje funkcję celu. Przyjmuje ona postać

F(x) = fa(x) + b gdzie a jest dodatnim współczynnikiem skalowania, jeśli optymalizacja ma na celu maksymalizację funkcji celu, ale jest ujemny, jeśli jest minimalizacją, a przesunięcie b służy do zapewnienia, że wszystkie wynikowe wartości dopasowania są ujemne. Następnie algorytm selekcji wybiera osobniki do reprodukcji na podstawie ich względnego dopasowania.

Reprodukcja

Po przypisaniu każdemu osobnikowi wartości dopasowania, można go wybrać z populacji z prawdopodobieństwem zgodnym z jego względnym dopasowaniem. Następnie można go rekombinować w celu uzyskania kolejnego pokolenia. Najczęściej używanymi operatorami genetycznymi w algorytmach genetycznych są operatory selekcji, krzyżowania i mutacji. Często są one uruchamiane jednocześnie w programie algorytmów genetycznych.

Selekcja

Selekcja to proces określania liczby prób, w których dany osobnik zostanie wybrany do reprodukcji. Zatem jest to liczba potomstwa, które osobnik będzie miał w puli partnerskiej, tymczasowej populacji, w której operacje krzyżowania i mutacji są stosowane do każdego osobnika. Selekcja osobników składa się z dwóch oddzielnych procesów:

a. określenia liczby prób, których osobnik może się spodziewać;
b. Konwersja oczekiwanej liczby prób na dyskretną liczbę potomstwa.

Krzyżowanie (rekombinacja)

Operator krzyżowania definiuje procedurę generowania dzieci z dwojga rodziców. Analogicznie do krzyżowania biologicznego, polega ono na wymianie genów w losowo wybranym punkcie krzyżowania od również losowo wybranych rodziców z puli par w celu generowania dzieci. Powszechnie stosowaną metodą jest: chromosomy rodziców są przecinane w losowo wybranych punktach, których może być więcej niż jeden, w celu wymiany ich genów w określonych punktach krzyżowania z prawdopodobieństwem krzyżowania określonym przez użytkownika. Ta metoda krzyżowania jest klasyfikowana jako krzyżowanie jednopunktowe i krzyżowanie wielopunktowe w zależności od liczby punktów krzyżowania. Krzyżowanie jednorodne często sprawdza się w przypadku małych populacji chromosomów i prostszych problemów .

Mutacja

Operacja mutacji jest losowo stosowana do osobników, aby zmienić wartość ich genu z prawdopodobieństwem mutacji Pm, które jest na ogół bardzo niskie.

Parametry GA

Wybór prawdopodobieństwa mutacji P_m i prawdopodobieństwa krzyżowania P_c jako dwóch parametrów kontrolnych może być złożonym problemem optymalizacji nieliniowej. Ich ustawienia są krytycznie zależne od charakteru funkcji celu. Ta kwestia selekcji nadal pozostaje otwarta na lepsze rozwiązania. Jedna z sugestii głosi, że dla dużej populacji (np. 100), współczynnik krzyżowania wynosi 0,6, a współczynnik mutacji 0,001, natomiast dla małej populacji (np. 30), współczynnik krzyżowania wynosi 0,9, a współczynnik mutacji 0,01 .

Modelowanie systemów rozmytych oparte na algorytmach genetycznych

W algorytmach genetycznych parametry danego problemu są reprezentowane przez chromosom. Chromosom ten może zawierać jeden lub więcej podciągów. Każdy chromosom zawiera możliwe rozwiązanie problemu. Funkcja dopasowania służy do oceny, jak dobrze chromosom rozwiązuje problem. W podejściu do modelowania rozmytego opartym na algorytmach genetycznych każdy chromosom reprezentuje określony model rozmyty, a ostatecznym celem jest staranne zaprojektowanie dobrego (idealnie optymalnego) chromosomu reprezentującego pożądany model rozmyty.

Struktura chromosomu

Na przykład rozważmy prosty model rozmyty z tylko jedną regułą wraz z partycją rozproszenia, która ma być zakodowana w chromosomie. Załóżmy, że zastosowano zarówno kodowanie liczb rzeczywistych, jak i kodowanie liczb całkowitych. Struktura i parametry modelu rozmytego są zakodowane w jednym lub kilku podciągach w chromosomie. Chromosom składa się z dwóch podciągów (podciągu kandydującego i podciągu decyzyjnego), które są podzielone na dwie części (część JEŻELI i część TO), jak pokazano na rysunku 2.



Podciąg kandydujący jest kodowany liczbami rzeczywistymi, jak pokazano na rysunku 3(a).



Zawiera on kandydatów na parametry funkcji przynależności w części JEŻELI oraz rozmytą singletonową funkcję przynależności w części TO. Rysunek 3 opisuje format kodowania podciągu kandydującego w chromosomie, gdzie n jest liczbą zmiennych wejściowych, r liczbą kandydatów na parametry w części JEŻELI, a s liczbą kandydatów na liczby rzeczywiste w części TO. Podciągi decyzyjne są kodowane liczbami całkowitymi, które określają strukturę i liczbę reguł poprzez wybór jednego z parametrów w podciągach kandydujących, jak pokazano na rysunek 3(b). Podciągi decyzyjne dla części JEŻELI określają strukturę przesłanki rozmytej bazy reguł. Składa się z n genów, które przyjmują wartości całkowite (allele) z zakresu od 0 do r. Zgodnie z tą wartością wybierany jest odpowiedni parametr w podciągu kandydującym. Wartość zerowa oznacza, że powiązane dane wejściowe nie są uwzględniane w regule. Podciąg decyzyjny dla części THEN składa się z c (maksymalnej liczby reguł) genów, które przyjmują wartości całkowite z zakresu od 0 do s, co powoduje wybór odpowiednich wartości z podciągu kandydującego dla części THEN. W tym podciągu gen przyjmujący wartość zerową usuwa powiązaną regułę. Zatem te podciągi określają strukturę części THEN i liczbę reguł. Rysunek 4 ilustruje przykład dekodowania chromosomu, a wynikowa reguła rozmyta pokazana jest na rysunku 5.





Funkcja sprawności

Aby zmierzyć wydajność rozmytego modelowania opartego na algorytmach genetycznych, definiowana jest funkcja celu optymalizacji, wybierana przez projektanta i zazwyczaj jest to miara dopasowania najmniejszych kwadratów w postaci



gdzie {y_i} i {y^d_i to odpowiednio wyniki modelu rozmytego i wyniki pożądane, a n to liczba wykorzystanych danych. Ponieważ algorytm genetyczny kieruje się wartościami dopasowania i nie wymaga dosłownie żadnego ograniczenia w formułowaniu miary wydajności, można uwzględnić więcej informacji o modelu rozmytym w funkcji dopasowania: f = g(J_struktura, J_{Dokładność}, …). Jednym z przykładów funkcji dopasowania jest

f(J) = λ/J + 1-λ/1+c

gdzie λ ∈ [0,1] jest współczynnikiem ważenia (duże λ daje bardzo dokładny model, ale wymaga dużej liczby reguł), a c jest maksymalną liczbą reguł. Gdy funkcja dopasowania jest obliczana na zbiorze pustym, jest ona niezdefiniowana; ale w tym przypadku można wprowadzić współczynnik kary, 0 < p < 1, i obliczyć p ⋅ f(J) zamiast f(J). Jeśli osobnik o bardzo wysokiej wartości dopasowania pojawi się na wcześniejszym etapie, ta funkcja dopasowania może spowodować wczesną zbieżność rozwiązania, zatrzymując tym samym algorytm przed osiągnięciem optymalności. Aby uniknąć tej sytuacji, osobniki można posortować według ich surowych wartości dopasowania, a nowe wartości dopasowania są określane rekurencyjnie przez



dla współczynnika skalowania dopasowania a ∈ (0,1).

Modelowanie rozmyte oparte na algorytmach sterowania z precyzyjnym dostrajaniem

AG generalnie nie gwarantuje zbieżności do globalnego optimum. Aby to poprawić, można zastosować metodę spadku gradientowego do precyzyjnego dostrojenia parametrów zidentyfikowanych przez algorytm sterowania. Ponieważ algorytm sterowania zazwyczaj znajduje bliskie globalnemu optimum, precyzyjne dostrojenie parametrów funkcji przynależności zarówno w części JEŻELI, jak i TO, np. za pomocą metody spadku gradientowego, może generalnie prowadzić do globalnej optymalizacji .

PRZYSZŁE TRENDY

Zostanie to omówione w innym miejscu w przyszłości.

WNIOSKI

Identyfikacja systemów rozmytych jest ważnym, a jednocześnie trudnym tematem badań, który wymaga większych wysiłków ze strony społeczności zajmujących się teorią sterowania i systemami inteligentnymi, aby osiągnąć kolejny wysoki poziom wydajności i sukcesu.

WSTĘP

Maszyny Wektorów Nośnych (SVM) to maszyny uczące się, pierwotnie zaprojektowane do problemów biklasyfikacji, implementujące znaną zasadę indukcyjną minimalizacji ryzyka strukturalnego (SRM) w celu uzyskania dobrej generalizacji na ograniczonej liczbie obiektów uczących się. Kryterium optymalizacji dla tych maszyn jest maksymalizacja marginesu między dwiema klasami, tj. odległości między dwiema równoległymi hiperpłaszczyznami, które dzielą wektory każdej z dwóch klas. Im większy margines oddziela klasy, tym mniejszy wymiar VC maszyny uczącej się, co teoretycznie zapewnia dobrą wydajność generalizacji , co zostało wykazane w wielu rzeczywistych zastosowaniach . W jej sformułowaniu stosuje się sztuczkę jądra, która poprawia wydajność tych algorytmów, ponieważ uczenie nie jest wykonywane bezpośrednio w oryginalnej przestrzeni danych, ale w nowej przestrzeni zwanej przestrzenią cech; Z tego powodu algorytm ten jest jednym z najbardziej reprezentatywnych dla tzw. maszyn jądra (KM). Główna teoria została pierwotnie opracowana w latach sześćdziesiątych i siedemdziesiątych przez V. Vapnika i A. Chervonenkisa na podstawie problemu separowalnej klasyfikacji binarnej. Jednak uogólnienie w stosowaniu tych algorytmów uczenia nastąpiło dopiero w latach dziewięćdziesiątych . Maszyny SVM były szeroko stosowane w różnego rodzaju problemach uczenia się, głównie w problemach klasyfikacji, choć również w innych problemach, takich jak regresja czy klasteryzacja . Dziedziny optycznego rozpoznawania znaków i kategoryzacji tekstu były najważniejszymi początkowymi zastosowaniami, w których wykorzystywano maszyny SVM. Wraz z rozszerzonym zastosowaniem nowych jąder, pojawiły się nowe zastosowania w dziedzinie bioinformatyki, konkretnie wiele prac związanych jest z klasyfikacją danych w ekspresji genetycznej (mikromacierzowej ekspresji genów) (Brown i in., 1997) oraz wykrywaniem struktur między białkami i ich związku z łańcuchami DNA . Inne zastosowania obejmują identyfikację obrazu, rozpoznawanie głosu, predykcję w szeregach czasowych itp.

TŁO

Sieci regularyzacyjne (RN), uzyskane z zasady indukcyjności penalizacji, to algorytmy oparte na głębokim zapleczu teoretycznym, ale ich czysto asymptotyczne właściwości aproksymacyjne i rozwinięcie funkcji rozwiązania na dużą liczbę wektorów sprawiają, że w ich pierwotnej definicji nie mają one praktycznego zastosowania. Poszukując bardziej zredukowanego rozwinięcia rozwiązania, niektórzy badacze obserwują dobre zachowanie SVM, który w swoim dyskursie teoretycznym może traktować skończony zbiór treningowy jako hipotezę, a także budować rozwiązanie końcowe, uwzględniając zagnieżdżone przestrzenie aproksymacyjne. Zarówno zasady indukcyjności regularyzacji, jak i minimalizacja ryzyka strukturalnego zakładają wstawianie informacji "a priori" o kształcie rozwiązania bez uwzględniania żadnego założenia dotyczącego nieznanej funkcji gęstości prawdopodobieństwa odnoszącej się do przestrzeni roboczych. Zasada regularyzacji zakłada regularyzator lub operator regularyzacji zapewniający znalezienie dobrego rozwiązania w postaci asymptotycznej na zagnieżdżonych przestrzeniach funkcyjnych, gdy liczba elementów w zbiorze treningowym dąży do nieskończoności. Poza tym, zasada SRM również opiera się na przestrzeniach zagnieżdżonych, ale rozwiązanie znajduje się poprzez zapewnienie górnej granicy dla funkcjonału ryzyka, biorąc pod uwagę jedynie skończony zbiór danych empirycznych. Oba procesy wnioskowania oczywiście nie są równoważne, ale ich podobieństwa zostały wywnioskowane z metod uczenia się, które mają swoje teoretyczne podstawy w tych zasadach, w takiej formie, że wielu badaczy podchodzących do problemu uczenia się z różnych perspektyw implikuje ustanowienie wspólnych ram pozwalających traktować SVM i RN jak szczególne przypadki bardziej ogólnej metodologii uczenia się, nazwijmy ją metodami jądra , gdy podkreśla się kluczową regułę odgrywaną przez funkcję jądra generującą przestrzeń cech, lub klasyfikatorami o dużej marży, gdy podkreśla się miarę, która ma być zoptymalizowana w celu zapewnienia maksymalnej generalizacji. Zarówno uzyskane wyniki, jak i ramy teoretyczne z SRM wydają się oferować lepsze gwarancje teoretyczne niż inne wcześniejsze podejścia w poszukiwaniu rozwiązań z dobrą generalizacją dla problemów opartych na skończonym zbiorze empirycznym. Stąd integracja metod uczenia maszynowego w modelach mieszanych stanowi najnowocześniejszą dziedzinę badań. Ponadto unika się stosowania wnioskowania bayesowskiego w tych modelach mieszanych, ponieważ użytkownik musi wcześniej zdefiniować funkcję gęstości prawdopodobieństwa.

MASZYNA WEKTORÓW PODPOROWYCH

Rozważmy problem biklasyfikacji (inne rodzaje problemów są analizowane w cytowanych publikacjach). Niech zatem Z = {z_i = (x_i, y_i), i = 1, 2,…, n} będzie zbiorem treningowym z x_i ∈ X ⊂ R^d jako przestrzenią wejściową i y_i∈ {θ₁, θ₂} (przestrzenią wyjściową) (θ₁≠ θ₂). Załóżmy początkowo, że klasy są liniowo separowalne (dwa zbiory są liniowo separowalne w przestrzeni n-wymiarowej, jeśli można je rozdzielić hiperpłaszczyzną d?1-wymiarową), wówczas poszukiwana jest hiperpłaszczyzna, oznaczona jako π : w x - b = 0 (gdzie b nazywane jest odchyleniem), która rozdziela te dwie klasy, to znaczy w x_i - b > 0, jeśli y_i = θ₁ i w x_i - b < 0, jeśli y_i = θ₂. Niemniej jednak istnieje wiele hiperpłaszczyzn z tym warunkiem , więc narzucany jest nowy warunek, że odległość między optymalną hiperpłaszczyzną a najbliższym wzorcem uczącym (marginesem) jest maksymalna. Przyjrzyjmy się szczegółowo temu warunkowi: Po pierwsze, bez utraty większości, załóżmy, że θ₁ = 1 i θ₂ = -1. Niech zatem β i α będą minimalnymi (klasa +1) i maksymalnymi (klasa -1) wartościami bezwzględnymi nieobciążonej hiperpłaszczyzny efektywnie osiągniętymi dla pewnych wzorców z₁∈ Z₁ i z₂∈ Z₂, tj.



gdzie Z₁ i Z₂ to wzorce należące do klas oznaczonych odpowiednio jako {+1,-1}. Przyjmuje się, że α ≤β, w przeciwnym razie wybiera się wektor -w. Zatem, biorąc pod uwagę wektor w, margines definiuje się jako odległość między równoległymi hiperpłaszczyznami π_α : w x - α = 0 i π_β : w x - β = 0, czyli



Naturalnym wyborem dla odchylenia, zapewniającym dodatnie i ujemne wyniki dla wzorców w poszczególnych klasach, jest

b = α +β / 2

.Maksymalizacja marginesu ma na celu wymuszenie generalizacji znalezionej maszyny uczącej się poprzez wprowadzenie przestrzeni wejściowej X ⊂ R^d do innej przestrzeni, zazwyczaj o wyższym wymiarze F, zwanej przestrzenią cech lub charakterystyk, która jest wyposażona w iloczyn skalarny, poprzez nieliniową iniekcję φ : X -> F (ta procedura nazywana jest sztuczką jądra), tak aby w przestrzeni cech F poszukiwana była optymalna hiperpłaszczyzna f (x, w) = ⟨φ(x), w⟩_F - b . Niemniej jednak, w celu jednoznacznego zdefiniowania poszukiwanej hiperpłaszczyzny (postaci kanonicznej), należy dodać kolejne ograniczenia:

y_i f(x_i) ≥ 1 - ξ_i, i = 1, 2,…, n

na zbiorze treningowym Z, gdzie wprowadza się zmienne luzu ξ_i1, jeśli h(x)=1, i θ₂ w przeciwnym przypadku. Zatem optymalna hiperpłaszczyzna realizuje następujący problem optymalizacji z ograniczeniami:



Wektor rozwiązania można zapisać jako



gdzie SV to liczba wektorów treningowych, które potwierdzają, że odpowiadający im mnożnik Lagrange′a ?i nie jest zerem (te wektory nazywane są wektorami nośnymi) .Istnieje wiele innych podejść do definiowania SVM , niemniej jednak to sformułowanie jest najbardziej powszechne. Z równania (1) optymalną hiperpłaszczyznę można zapisać jako:



gdzie k(x_i, x) = ⟨φ (x_i), φ(x)⟩_F jest jądrem (funkcją dwuwymiarową spełniającą twierdzenie Mercera), a b oblicza się, stosując warunki Karusha-Kuhna-Tuckera (KKT). W przypadku problemów z wieloma klasyfikacjami rozważany jest zbiór możliwych etykiet Y = {θ₁, …, θℓ}, gdzie ℓ ≥ 2. Istnieją dwa główne podejścia oparte na SVM do rozwiązania tych problemów. Pierwszym z nich jest podejście "wszystkie klasy naraz", które rozwiązuje te problemy, biorąc pod uwagę wszystkie wystąpienia ze wszystkich klas w unikalnej formule optymalizacji, podczas gdy drugie to podejście architektoniczne "dekompozycji-rekonstrukcji" (wielokrotna klasyfikacja w dwóch fazach) z wykorzystaniem binarnych SVM. W pierwszym przypadku istnieje kilka formulacji , jednak spośród wszystkich proponowanych podejść do problemu maksymalnego marginesu, to przedstawione przez Shashua jest jedynym, które bierze pod uwagę maksymalizację dokładnego wyrażenia marginesu między wystąpieniami o różnej etykiecie, więc problem wielokrotnej klasyfikacji jest interpretowany jak problem regresji porządkowej, w którym funkcją celu jest suma odwrotności marginesów między klasami. W przypadku wieloklasyfikacji w dwóch fazach, najczęściej stosowanymi podejściami SVM do wieloklasyfikacji są SVM 1-v-1 (jeden kontra jeden) i SVM 1-v-r (jeden kontra reszta). W obu podejściach pierwsza faza dekompozycji generuje kilka maszyn uczących się równolegle, a schemat rekonstrukcji pozwala uzyskać ogólny wynik poprzez scalenie wyników z fazy dekompozycji. W pierwszej fazie 1-v-r SVM każda maszyna bierze pod uwagę wszystkie klasy; ℓ klasyfikatory binarne są trenowane do generowania hiperpłaszczyzn f_k, (k = 1,2,…, 7ell;) oddzielających wektory treningowe z etykietą θ_k od pozostałych wektorów. W fazie rekonstrukcji (druga faza) rozkład etykiet generowany przez wytrenowane maszyny w równoległym rozkładzie jest rozpatrywany za pomocą schematu scalania. Rozważane są wszystkie informacje dostarczane przez wektory treningowe, główną wadą jest to, że nie jest on dobrze zaprojektowany do oddzielania określonych klas. W pierwszej fazie 1-v-1 SVM każda maszyna bierze pod uwagę tylko dwie klasy. W tym podejściu ℓ(ℓ-1)/2 ? ? ? klasyfikatory binarne są trenowane do generowania hiperpłaszczyzn f_kh ,k, h = 1,2,..., ℓ, k < h oddzielających wektory treningowe z etykietą θ_k od wektorów treningowych w klasie θ_h. Pozostałe wektory treningowe nie są uwzględniane w problemie optymalizacji. W fazie rekonstrukcji rozkład etykiet generowany przez maszyny wytrenowane w dekompozycji równoległej jest uwzględniany za pomocą schematu scalania. Główną wadą jest to, że w procedurze dekompozycji dla każdej maszyny uwzględniane są tylko dane z dwóch klas, co powoduje wysoką wariancję wyników i ignorowanie wszelkich informacji z pozostałych klas. Schemat 1-v-1 jest zazwyczaj preferowany, ponieważ wymaga mniej czasu uczenia , chociaż niektórzy badacze rozważają schemat 1-v-r, ponieważ ma on pewne zalety. Niemniej jednak, według , trudno byłoby powiedzieć, który z nich zapewnia lepszą dokładność.

PRZYSZŁE TRENDY I WNIOSKI

Problem rekurencyjny przy rozważaniu SVM polega na zmniejszeniu kosztów obliczeniowych podczas rozwiązywania problemu QP. SVM dla klasyfikacji jest najczęściej badanym podejściem; jednak inne problemy, takie jak regresja, nie są wystarczająco rozwinięte, aby być konkurencyjnymi w stosunku do innych znormalizowanych obszarów badań, takich jak sztuczne sieci neuronowe. Tak więc w tym obszarze wciąż pozostaje długa droga do przebycia. Szczególnym otwartym problemem badawczym w przypadku multiklasyfikacji jest implementacja schematu trójklasowego. W tym podejściu jedna klasa jest oznaczana jako +1, inna jako -1, a pozostałe klasy jako 0, co jest wymuszone do hermetyzacji w ?-tube, 0 < δ < 1, wzdłuż hiperpłaszczyzn separacji. Trójklasowy SVM ulepsza standardowe algorytmy rozwiązujące problemy klasyfikacji 2-klasowej w fazie dekompozycji ogólnego schematu wieloklasowego, koncentrując uczenie na dwóch klasach, ale wykorzystując wszystkie dostępne informacje o wzorcach , dlatego to podejście można postrzegać jako połączenie SVM 1-v-r i 1-v-1. Drugą teoretyczną zaletą "podejścia trzeciej klasy" jest solidność procedury rekonstrukcji , co może prowadzić do empirycznego oczekiwania wyższej wydajności nowego podejścia pod względem dokładności . Badania powinny obejmować nawet badanie teoretycznych granic uogólnienia dla tego rodzaju maszyny.

WSTĘP

W ciągu ostatnich kilku dekad perceptrony wielowarstwowe (MLP) zyskały rosnącą popularność wśród naukowców, inżynierów i innych specjalistów jako narzędzia do reprezentacji wiedzy. Niestety, nie ma uniwersalnej architektury, która sprawdziłaby się we wszystkich problemach. Nawet przy odpowiedniej architekturze, frustrujące problemy z uczeniem wag połączeń wciąż pozostają ze względu na nierówny charakter krajobrazu energetycznego MLP. Funkcja energii często odnosi się do sumy kwadratów funkcji błędu w przypadku konwencjonalnych MLP i ujemnej logarytmicznej funkcji gęstości a posteriori w przypadku bayesowskich MLP. W niniejszym artykule przedstawiono metodę Monte Carlo, którą można wykorzystać do uczenia się MLP. Główny nacisk położono na sposób zastosowania tej metody do trenowania wag połączeń dla MLP. Omówiono również, jak zastosować tę metodę do wyboru optymalnej architektury i prognozowania przyszłych wartości, ale w ramach podejścia bayesowskiego.

TŁO

Jak wiedzą liczni badacze, krajobraz energetyczny MLP jest często nierówny. Algorytmy szkoleniowe oparte na gradiencie, takie jak propagacja wsteczna , gradient sprzężony, metoda Newtona i algorytm BFGS , mają tendencję do zbieżności do lokalnego minimum w pobliżu punktu początkowego, co sprawia, że dane szkoleniowe są niewystarczająco nauczone. Aby zmniejszyć ryzyko zbieżności do lokalnych minimów, zaproponowano szereg wariantów tych algorytmów opartych na idei zaburzeń . W praktyce efekty tych zaburzeń są zazwyczaj ograniczone, co jedynie opóźnia proces uczenia się zbieżności do lokalnych minimów o rozsądną liczbę iteracji . Aby uniknąć problemu pułapki lokalnej, niektórzy autorzy stosowali symulowane wyżarzanie (SA) do trenowania sieci neuronowych. Amato oraz Owen i Abunawass (1993) pokazują, że w przypadku złożonych zadań uczenia się, SA ma większą szansę na zbieżność do globalnego minimum niż algorytmy oparte na gradiencie. Geman i Geman (1984) pokazują, że globalne minimum można osiągnąć za pomocą SA z prawdopodobieństwem 1, jeśli temperatura spada z logarytmiczną szybkością O(1/log t), gdzie t oznacza liczbę iteracji. W praktyce jednak nikt nie może sobie pozwolić na tak powolny harmonogram chłodzenia. Najczęściej stosuje się liniowo lub geometrycznie malejący harmonogram chłodzenia, który nie gwarantuje już osiągnięcia globalnego minimum energetycznego . Inne algorytmy stochastyczne stosowane w trenowaniu MLP obejmują algorytm genetyczny i łańcuch Markowa Monte Carlo (MCMC). Chociaż algorytm genetyczny sprawdza się w przypadku niektórych problemów, nie ma teorii potwierdzającej jego zbieżność do minimów globalnych. Algorytmy MCMC są wykorzystywane głównie w bayesowskich modelach MLP

GŁÓWNY TEMAT

Niniejszy artykuł przedstawia, jak algorytm aproksymacji stochastycznej Monte Carlo (SAMC) może być wykorzystany do uczenia się algorytmu MLP, w tym do trenowania, predykcji i wyboru architektury.

Krótki przegląd algorytmu SAMC

Załóżmy, że pracujemy z rozkładem Boltzmanna,



gdzie Z to stała normalizująca, U(x) to funkcja energii, τ to temperatura, a Ω to przestrzeń próby. Bez utraty ogólności zakładamy, że Ω jest zwarta. W przypadku MLP x oznacza wektor wag połączeń, a Ω można ograniczyć do hiperprostokąta [-B_Ω, B_Ω]^dim(Ω), gdzie B_Ω to duża liczba taka, że Ω zawiera co najmniej globalne minimum U(x). Ponadto zakładamy, że przestrzeń próby można podzielić zgodnie z funkcją energii na m rozłącznych podregionów: E₁ = {x:U(x) ≤ u₁}, E₂ = {x:u₁ < U(x) ≤ u₂},…, E_m-1 = {x:u_m-2 < U(x) ≤ u_m-1} i E_m = {x:U(x) > u_m-1}, gdzie u₁,…,u_m-1 to z góry określone liczby rzeczywiste. SAMC dąży do pobrania próbek z każdego podregionu z z góry określoną częstością. Jeśli ten cel zostanie osiągnięty, problem lokalnej pułapki zostanie skutecznie wyeliminowany. Niech x_t+1 oznacza próbkę symulowaną z rozkładu



za pomocą algorytmu Metropolisa-Hastingsa (MH), gdzie Ψ(x) = e^-U(x)/τ, a θ_t = (θ_t1,… ,θ_tm) jest wektorem m w przestrzeni Θ. Dla uproszczenia zakładamy, że Θ jest zwarta, np. Θ = [-B_Θ, B_Θ]^dim(0), gdzie B_Θ jest dużą liczbą. Ponieważ dodawanie lub odejmowanie od θ_t stałej nie zmieni p_θt(x), θ_t można zachować w zbiorze zwartym w symulacjach, dostosowując je za pomocą stałej addytywnej. Niech rozkład propozycji, q(x, y), ruchów MH spełnia warunek minoryzacji , tj.



Ponieważ Ω jest zwarty, wystarczającym projektem dla warunku minoryzacji jest wybranie q(x,γ) jako globalnego rozkładu propozycji. Rozkład propozycji jest nazywany globalnym, jeśli q(x, y) > 0 dla wszystkich x, y ∈Ω. W przypadku MLP, q(x, y)można wybrać jako propozycję Gaussa losowego spaceru, γ ∿ N(x, σ²I), gdzie I jest macierzą jednostkową, a σ² jest skalibrowane tak, aby ruchy MH miały pożądany współczynnik akceptacji. Jak omówiono później, ograniczenie rozkładu propozycji do globalnego zapewnia zbieżność algorytmu SAMC z wyżarzaniem do globalnych minimów energii. Niech {γ_t} będzie dodatnim niemalejącym ciągiem spełniającym warunki:



dla pewnego δ ∈ (1, 2). Na przykład, można ustawić



dla pewnych wartości t₀ > 1 i η ∈ (1/2,1) Duża wartość t₀ pozwoli próbnikowi bardzo szybko dotrzeć do wszystkich podregionów, nawet w obecności wielu minimów lokalnych. Niech μ = (μ₁,…, μ_m) będzie m-wektorem, gdzie 0 < μ_i < 1 i



który definiuje pożądany rozkład częstotliwości próbkowania w podregionach. Przy użyciu powyższych oznaczeń iterację SAMC można opisać następująco.

Algorytm SAMC

a.Wygeneruj x_t+1L ∿ K_θt (x_t,.) w jednym kroku MH: 1.Wygeneruj y zgodnie z rozkładem propozycji q(x_t, y).

2. Oblicz iloraz



gdzie J(x) oznacza indeks podregionu, do którego należy próbka x.

3. Zaakceptuj propozycję z prawdopodobieństwem min(1, r). Jeśli zostanie zaakceptowana, ustaw x_t+1 = y; w przeciwnym razie ustaw x_t+1 = x_t

b. Ustaw θ* = θ_t> + γ_t (e_t+1-μ), gdzie γ_t nazywane jest współczynnikiem wzmocnienia, e_t+1 = (e_t+1,1,…, e_t+1,m), a e_t+1.i = 1, jeśli x_t+1∈ E_i i 0 w przeciwnym razie.

c. Jeśli θ* ∈Θ, ustaw θ_t+1 = θ*; w przeciwnym razie ustaw θ_t+1 = θ* + c*, gdzie c* jest wektorem stałym i jest tak dobrany, że θ* + c* ∈Θ . Istnienie c* jest oczywiste, ponieważ B_Θ zostało ustawione na dużą liczbę i można rozsądnie założyć, że zachowuje się w każdej iteracji. Niezwykłą cechą SAMC jest jego mechanizm samoregulacji. Jeśli propozycja zostanie odrzucona, waga podregionu, do którego należy bieżąca próbka, zostanie dostosowana do większej wartości, a zatem propozycja wyjścia z bieżącego podregionu będzie mniej prawdopodobna do odrzucenia w następnej iteracji. Ten mechanizm skutecznie zapobiega uwięzieniu systemu w minimach lokalnych. Jest to bardzo ważne dla uczenia MLP, ponieważ jego krajobraz energetyczny jest często nierówny. SAMC należy do kategorii algorytmów aproksymacji stochastycznej . Konwergencję SAMC można rozszerzyć na podstawie twierdzenia przedstawionego przez Liang. W łagodnych warunkach i gdy t -> ∞



gdzie



a m₀ = #{i : E_i = Ø} to liczba pustych podregionów, a C to dowolna stała. Podregion E_i jest uważany za pusty, jeśli



W SAMC podział przestrzeni próbkowania można przeprowadzić "na ślepo", po prostu podając pewne wartości u₁,…, u_m-1. Może to skutkować powstaniem pustych podregionów. Stałą C można określić, nakładając ograniczenie na θ_t, na przykład, że



jest równa znanej liczbie. Ponadto Liang pokazuje, że θ_t może zbiegać się w formie L₂ z szybkością O(1/t). Niech ? będzie prawdopodobieństwem pobrania próbek z podregionu E_i w iteracji t. Z równania wynika, że gdy będzie zbieżne do μ_i + ζ jeśli E_i ≠ Ø i 0 w przeciwnym przypadku. Oznacza to również, że wraz ze wzrostem liczby iteracji do nieskończoności, SAMC może w przybliżeniu pobierać próbki z każdego z podregionów z określonym prawdopodobieństwem. Przy odpowiedniej specyfikacji μ, próbkowanie może być ukierunkowane na obszary o niskiejenergii, aby zwiększyć szansę na znalezienie globalnego minimum.

Wyżarzanie SAMC do nauki MLP

Teoretycznie SAMC jest w stanie znaleźć globalne minima energii, jeśli przebieg jest wystarczająco długi. Jednak ze względu na szerokość przestrzeni próbkowania, proces może być powolny, nawet gdy próbkowanie jest ukierunkowane na podregiony o niskiej energii. Aby przyspieszyć proces wyszukiwania, można iteracyjnie zmniejszać przestrzeń próbkowania w symulacjach. Jak argumentowano poniżej, ta modyfikacja zachowuje teoretyczną własność SAMC, gdy używany jest globalny rozkład propozycji. Załóżmy, że podregiony E₁,…,E_m zostały uporządkowane rosnąco według energii; to znaczy, jeśli i < j, to U(x) <<U(y) dla dowolnego x ∈ E_i i y ∈ E_j. Niech κ(u) oznacza indeks podregionu, do którego należy próbka x o energii u. Niech Ω_t oznacza przestrzeń próbkowania w iteracji t. Wyżarzanie SAMC, w dalszej części nazywane w skrócie ASAMC, rozpoczyna się od



a następnie iteracyjnie ustala



gdzie U^t_min to minimalna wartość energii uzyskana w iteracji t, Δ>0 to parametr określony przez użytkownika. Przestrzeń próby Ω_t kurczy się z iteracji na iterację. W tym sensie zmodyfikowany algorytm nazywa się ASAMC. Ponieważ rozkład propozycji jest globalny, własność zbieżności SAMC nadal obowiązuje dla ASAMC w przestrzeni granicznej Ω_∞ = lim_t->∞Ω_t, chociaż Ω_∞ może zawierać pewne oddzielone obszary. Istnienie Ω_∞ jest prawdziwe ze względu na monotoniczność ciągu Ω₁ ⊇ Ω₂ ⊇ …. Z twierdzenia Scheffe′a wynika, że gdy t -> ∞, x_t będzie zbieżne w rozkładzie do zmiennej losowej o gęstości



gdzie u_min oznacza globalne minimum funkcji energii U(x). Ponownie, podobnie jak w SAMC, zbieżność można osiągnąć w postaci L2 z szybkością O(1/t). Jeśli pozwolimy, aby Δ zniwelowało się do zera, wówczas próbki ASAMC będą zbieżne w rozkładzie do globalnych minimów U(x). Aby skutecznie wdrożyć ASAMC, należy rozważyć kilka kwestii.

Podział przestrzeni próbkowania. Ponieważ w tym samym podregionie ASAMC sprowadza się do próbkowania z nieznormalizowanej gęstości Ψ(x), sugerujemy, aby maksymalna różnica energii w każdym podregionie była ograniczona rozsądną liczbą, powiedzmy 2τ, aby zapewnić, że lokalne ruchy Metropolis-Hastings w tym samym podregionie mają rozsądną stopę akceptacji.

Wybór Δ. Wydajność ASAMC zależy w pewnym stopniu od wartości ?Δ. Jeśli Δ jest zbyt duże, ASAMC może potrzebować dużo czasu na znalezienie globalnego minimum ze względu na szerokość przestrzeni próbkowania. Jeśli Δ jest zbyt małe, ASAMC może również potrzebować dużo czasu na znalezienie globalnego minimum. W takim przypadku przestrzeń próbkowania może zawierać tylko kilka oddzielnych regionów, a większość proponowanych przejść zostanie odrzucona. Z naszego doświadczenia wynika, że wartość Δ pomiędzy 5 a 10 sprawdza się w przypadku większości problemów MLP

Pożądany rozkład próbkowania. Wybór μ nie ma kluczowego znaczenia dla wydajności ASAMC, ponieważ przestrzeń próbkowania została zmniejszona poprzez iteracje. Wręcz przeciwnie, w SAMC μ należy dobierać ostrożnie, aby odchylić próbkowanie w kierunku obszarów o niskiej energii i poprawić ergodyczność symulacji.

Współczynnik wzmocnienia. Aby dokładnie oszacować całki



dokładnie, γ_t powinno być bardzo bliskie 0 na końcu symulacji. W przeciwnym razie uzyskane oszacowania mogą charakteryzować się dużą zmiennością. Malejącą prędkość γ_t można kontrolować za pomocą t₀ i η. W praktyce często ustalamy η = 1 i zmieniamy wartość t0 w zależności od złożoności problemu. Im bardziej złożony jest problem, tym większą wartość t₀ należy wybrać. Diagnostyka konwergencji. Formalna diagnostyka konwergencji algorytmu ASAMC powinna opierać się na wielu przebiegach. Zgrubną diagnostykę pojedynczego przebiegu można przeprowadzić, porównując obserwowane częstotliwości próbkowania z pożądanymi częstotliwościami próbkowania różnych podregionów. Jeśli są one bardzo dobrze ze sobą zgodne, możemy uznać przebieg za zbieżny. W przeciwnym razie można ponownie uruchomić algorytm z większą liczbą iteracji lub wyższą wartością t₀. Algorytm ASAMC został porównany przez Lianga z symulowanym wyżarzaniem, algorytmem SAMC i algorytmem BFGS na wielu przykładach, w tym na słynnych problemach z parzystością n i dwuspiralami. Wyniki numeryczne dla problemu dwuspiralowego przedstawiono ponownie w Tabeli i na Rysunku .





Ustawienia poszczególnych algorytmów można znaleźć w Liangu (2007). Wyniki dla pozostałych przykładów są podobne. Podsumowując, ASAMC przewyższa inne algorytmy zarówno pod względem błędów uczenia, jak i testowania. Podobnie jak inne algorytmy stochastyczne, ASAMC wymaga dłuższego czasu uczenia niż algorytmy oparte na gradiencie. Zapewnia jednak efektywne podejście do trenowania MLP, dla których krajobraz energetyczny jest nierówny.

Bayesowskie uczenie MLP

SAMC może być również używane do trenowania bayesowskich MLP. Niech Ψ(x) oznacza gęstość a posteriori MLP (z dokładnością do stałej normalizującej), a ?. Zatem następująca gęstość



może służyć jako gęstość próbna do próbkowania z Ψ(x). Jako gęstość próbna posiada dwie korzystne właściwości. Po pierwsze, waga ważności jest ograniczona powyżej przez , zakładając, że zostało znormalizowane przez dodatkowe ograniczenie, np.



jest znaną stałą. Po drugie, próbkowanie z doprowadzi do losowego spaceru w przestrzeni niepustych podregionów, jeśli każdy podregion potraktujemy jako punkt. Zatem cała przestrzeń próbkowania może być dobrze zbadana. Załóżmy, że ważne próbki (x₁, w₁),…,(x_n, w_n) zostały pobrane za pomocą próbnika MCMC, gdzie w_i oznacza wagę ważności x_i. Niech f(z |x) oznacza wyjście MLP z wejściem z. Dla nowego wejścia z₀ prognoza punktowa Bayesa wynosi zatem:



Ocena dowodów dla bayesowskich modeli MLP

Oprócz uczenia się MLP, SAMC zapewnia również wygodny sposób oceny dowodów dla bayesowskich modeli MLP. Jak zauważył MacKay , dowody bayesowskie mogą być wykorzystane jako wskazówka przy wyborze architektury dla bayesowskich modeli MLP. Niech f(D|x) oznacza funkcję wiarygodności danego modelu MLP, a l(x) niech oznacza gęstość a priori narzuconą na x. Tak jak poprzednio, zakładamy, że Ω zostało ograniczone do zbioru zwartego. Zdefiniuj funkcję



na przestrzeni iloczynowej Ω×{0,1}, gdzie |Ω| Oznacza hiperobjętość przestrzeni Ω. Podziel przestrzeń iloczynową w następujący sposób: E₀ = {(x, k) : k = 0, x∈ Ω}, E₁ = {(x, k) : k = 1, U(x) ≤ u₁},…, E_m = {(x, k) : k = 1, U(x) > u_m-1}. Jeśli SAMC zostanie uruchomiony z tym partycjonowaniem, dowód MLP można oszacować za pomocą wzoru



gdzie



oraz 0 < μ ₀ < 1. Zauważmy, że Ψ(x,0) może być dowolną nieujemną funkcją, dla której g0 jest analitycznie dostępne.

PRZYSZŁE TRENDY

W przyszłości konieczne będzie przeprowadzenie szeregu porównań w celu oceny możliwości SAMC w różnych aspektach. Na przykład, konieczne będzie porównanie SAMC z zaawansowanymi próbnikami MCMC, takimi jak równoległe temperowanie i ewolucyjna metoda Monte Carlo , aby ocenić jego możliwości w zakresie predykcji bayesowskiej; oraz porównanie SAMC z metodą aproksymacji Gaussa (MacKay, 1992b), aby ocenić jego możliwości w zakresie oceny dowodów.

WNIOSKI

W niniejszym artykule zaproponowano innowacyjną metodę uczenia, predykcji i wyboru architektury MLP. Siła SAMC wynika z mechanizmu samoregulacji, który pozwala mu pokonać problemy pułapek lokalnych. Podobnie jak algorytmy wyżarzania symulowanego i genetycznego, SAMC unika wymogu informacji o gradiencie funkcji celu. Dlatego też można go używać jako ogólnego narzędzia optymalizacji, symulacji i integracji w wielu innych problemach, takich jak optymalizacja kombinacyjna, wybór modelu i symulacje statystyczne.

WSTĘP

Od czasu przełomowej pracy McCullocha i Pittsa (McCulloch i Pitts, 1943) zaproponowano kilka modeli dyskretnych sieci neuronowych, z których wiele prezentowało możliwość przypisania dyskretnej wartości (innej niż unipolarna lub bipolarna) do wyjścia pojedynczego neuronu. Modele te koncentrowały się na szerokim spektrum zastosowań. Jeden z najważniejszych modeli został opracowany przez J. Hopfielda , który z powodzeniem zastosowano w takich dziedzinach, jak rozpoznawanie i rekonstrukcja wzorców i obrazów, projektowanie układów analogowo-cyfrowych , a przede wszystkim w optymalizacji kombinatorycznej , między innymi. Celem niniejszej pracy jest przegląd niektórych zastosowań wielowartościowych modeli neuronowych w problemach optymalizacji kombinatorycznej, ze szczególnym uwzględnieniem modelu neuronowego MREM, ponieważ obejmuje on wiele modeli wielowartościowych opisanych w literaturze specjalistycznej.

TŁO

W pionierskiej pracy Hopfielda i Tanka (Hopfield i Tank, 1985) sieci neuronowe zostały po raz pierwszy zastosowane do rozwiązania problemów optymalizacji kombinatorycznej, a konkretnie znanego problemu komiwojażera. Opracowali oni dwa typy sieci: dyskretną i ciągłą, choć ta druga była najczęściej wybierana do rozwiązywania problemów optymalizacyjnych, argumentując, że ułatwia ona ucieczkę od lokalnych optimów. Od tego czasu celem badaczy w tej dziedzinie jest poszukiwanie lepszych algorytmów neuronowych, pozwalających na rozwiązywanie różnorodnych problemów optymalizacji kombinatorycznej (wiele z nich należy do klasy problemów NP-zupełnych). Ta metoda optymalizacji polega na minimalizacji funkcji energii, której parametry i ograniczenia uzyskuje się poprzez identyfikację z funkcją celu problemu optymalizacyjnego. W tym przypadku funkcja energii ma postać:



gdzie N to liczba neuronów sieci, w_i,j to waga synaptyczna między neuronami j i i, a θ_i to próg lub odchylenie neuronu i. W dyskretnej wersji modelu Hopfielda składowa s_i wektora stanu S = (s₁,…,s_N) może przyjmować wartości w zakresie M = {?1,1} (stanowiąc model bipolarny) lub w zakresie M = {0,1} (model unipolarny). W wersji ciągłej M = [?1,1] lub M=[0,1]. Ta ciągła wersja, mimo że tradycyjnie była najczęściej wykorzystywana w problemach optymalizacyjnych, wiąże się z pewnymi niedogodnościami:

o Należy wprowadzić pewne specjalne mechanizmy, być może w postaci ograniczeń, aby w końcowym stanie sieci wszystkie składowe wektora stanu S należały do {-1, 1} lub {0,1}.
o Tradycyjna dynamika stosowana w tym modelu, wdrożona w komputerze cyfrowym, nie gwarantuje zmniejszenia funkcji energii w każdej iteracji, zatem nie ma pewności, że stan końcowy będzie minimum funkcji energii .

Jednak największym problemem tego modelu (zarówno dyskretnego, jak i ciągłego) jest możliwość zbieżności do stanu niewykonalnego lub do lokalnego (a nie globalnego) minimum. Wilson i Pawley (1988) wykazali za pomocą masowych symulacji, że dla problemu komiwojażera 10 miast tylko 8% rozwiązań było wykonalnych, a większość z nich nie była dobra. Co więcej, odsetek ten pogarszał się wraz ze wzrostem rozmiaru problemu. Później wiele prac koncentrowało się na ulepszaniu sieci Hopfielda:

o Poprzez modyfikację funkcji energetycznej .
o Poprzez dostosowanie licznych parametrów obecnych w sieci, jak w (Lai i Coghill, 1988).
o Poprzez zastosowanie technik stochastycznych w dynamice sieci .

W szczególności badacze starali się poprawić efektywność sieci Hopfielda w przypadku problemu komiwojażera, osiągając akceptowalne rezultaty, ale gorsze od technik badań operacyjnych . Powodem tych rozczarowujących rezultatów jest to, że liniowe sformułowanie stosowane w tych technikach stanowi dużą zaletę w porównaniu z sieciami neuronowymi, które nieuchronnie wykorzystują kwadratową funkcję energii, utrudniając stosowanie technik usuwania podścieżek (Smith, 1996) i powodując pojawienie się większej liczby minimów lokalnych. Inny nurt badań poświęcony był udoskonaleniu sieci rekurencyjnych typu Hopfielda i ich zastosowaniu w różnorodnych problemach optymalizacji, w których niektóre wyniki okazały się lepsze niż uzyskane tradycyjnymi technikami badań operacyjnych . Należy podkreślić prace Takefujiego , z wieloma publikacjami w mediach międzynarodowych. Ich wyniki zostały przewyższone przez model OCHOM .

WIELOWARTOŚCIOWY DYSKRETNY MODEL REKURENCYJNY. ZASTOSOWANIE DO PROBLEMÓW OPTYMALIZACJI KOMBINATORYJNEJ

W pracach (MéridaCasermeiro, 2000) (MéridaCasermeiro i in., 2001) przedstawiono nowe uogólnienie modelu Hopfielda (MREM - Wielowartościowy Model REKURENCYJNY).

Neuronowy model MREM

Model ten charakteryzuje się dwiema istotnymi cechami, które czynią go bardzo wszechstronnym i zwiększają jego zastosowanie:

o Wyjście każdego neuronu, s_i, jest wartością zbioru M = {m₁,m₂,…m_L},który niekoniecznie jest wartością numeryczną.
o Wprowadzono koncepcję funkcji podobieństwa f między wyjściami neuronów. f(x,y) reprezentuje podobieństwo między stanami neuronów x i y. W ten sposób funkcja energetyczna tego modelu przedstawia się następująco:



gdzie θ_i: -> M ? ℝ jest uogólnieniem progów każdego neuronu. Wspomniane powyżej cechy sprawiają, że w tym modelu pewne problemy optymalizacyjne (jak problem komiwojażera) mają lepszą reprezentację niż w unipolarnych lub bipolarnych modelach Hopfielda i ich następcach. Jest oczywiste, że MREM obejmuje modele Hopfielda (z wyjściami w M = {-1,1} lub w M = {0,1} jeśli rozważymy funkcję podobieństwa daną przez iloczyn f(a,b) = ab. Inne modele wielowartościowe, takie jak MAREN lub SOAR , są również uogólnione przez MREM. Dynamika tej sieci jest dobierana w zależności od rozwiązywanego problemu.

Zastosowanie do kilku problemów optymalizacji kombinatorycznej

Ten wielowartościowy model został z powodzeniem zastosowany do różnych problemów optymalizacyjnych, przewyższając najlepsze, sprawdzone algorytmy. Problemy te są typowymi przedstawicielami klasy złożoności NP-zupełnej, co wskazuje na stopień trudności ich rozwiązania.

Problem komiwojażera

Problem komiwojażera (TSP) jest jednym z najbardziej znanych i zbadanych problemów optymalizacji kombinatorycznej ze względu na szeroki zakres zastosowań w praktyce i wewnętrzną złożoność. Zastosowania praktyczne obejmują takie aspekty, jak automatyczne trasowanie dla robotów i lokalizacja otworów w projektowaniu obwodów drukowanych , a także sprawdzanie turbin gazowych, harmonogramowanie zadań maszyn czy analiza krystalograficzna .Problem ten można przedstawić następująco: biorąc pod uwagę N miast X₁,…,X_N oraz odległości d_i,j między każdą parą miast X_i i X_j, celem jest znalezienie najkrótszej trasy zamkniętej, obejmującej jednokrotne odwiedzenie każdego miasta. Aby rozwiązać TSP za pomocą tego modelu neuronowego, należy wykonać dwie identyfikacje: o Stan sieci musi zostać zidentyfikowany w rozwiązaniu TSP: Ponieważ rozwiązanie dla N miast TSP można przedstawić jako permutację w zbiorze liczb {1,...,N}, sieć zostanie utworzona przez N neuronów, przyjmujących wartości ze zbioru M = {1,…,N} takie, że wektor stanu S = (s₁, …,s_N) reprezentuje permutację {1,…,N}. W tej reprezentacji s_i = k oznacza, że k-te miasto zostanie odwiedzone w i-tym miejscu.
o Funkcja energii musi zostać zidentyfikowana w całkowitym dystansie wycieczki: Jeśli przyjmiemy f(x,y) = -2d_x,y i



uzyskana funkcja energii to



Całkowita odległość trasy reprezentowana przez wektor stanu S. Dynamika obliczeniowa opiera się na rozpoczęciu od losowego, wykonalnego wektora stanu początkowego i aktualizacji wyjść neuronów w celu utrzymania bieżącego wektora stanu w zbiorze stanów wykonalnych. W tym celu, w każdej iteracji, 2opt aktualizacja bieżącego wektora stanu będzie przeprowadzana, to znaczy, każda para neuronów, p, q, gdzie p > q + 1, jest badana i równolegle sprawdzana, czy istnieje skrzyżowanie między segmentami (s_p, s_p+1) i (s_q, s_q+1). W tym przypadku zachodzi następująca relacja:



Następnie trajektoria między miastami s_p+1 i s_q jest odwrócona, tzn. jeśli S jest stanem bieżącym, to nowy wektor stanu S′ zostanie zdefiniowany przez:



Jako dodatkową technikę udoskonalenia rozważano również aktualizacje 3opt: trasa jest rozkładana na trzy kolejne łuki, A, B i C, które następnie są łączone na wszystkie możliwe sposoby: {ABC, AC B, AB′C, ABC′, AB′C′, AC′B, ACB′, AC′B′}, gdzie A′, B′, C′ to odwrócone łuki odpowiadające odpowiednio A, B i C. Należy zauważyć, że {ABC, AB′C, ABC′, AC′B′} to aktualizacje 2opt, więc nie ma potrzeby ich ponownego sprawdzania. Następnym stanem sieci będzie kombinacja, która najbardziej zmniejsza funkcję energii. W (MeridaCasermeiro i in., 2003) przedstawiono niektóre wyniki eksperymentalne dla problemów z repozytorium TSPLIB . Model ten porównano z modelem KNIES , modelem opartym na samoorganizującej się mapie Kohonena. Model MREM okazał się skuteczniejszy od modelu KNIES, uzyskując w wielu przypadkach rozwiązania niemal optymalne.

Problem podziału grafu

Niech G = (V,ε) będzie grafem nieskierowanym bez samo-połączeń. V={v_i} jest zbiorem wierzchołków, a ε jest zbiorem n_e krawędzi. Dla każdej krawędzi (v_i,v_j) ∈ε istnieją krawędzie z ε, których końce znajdują się w różnych elementach podziału, funkcja jest maksymalna. Zatem funkcja, którą należy zmaksymalizować, to



Aby rozwiązać problem MaxCut za pomocą MREM, potrzebujemy N neuronów, po jednym na węzeł w ?V. Wyjście neuronu i,s_i∈ M = {1,2,…K} , co oznacza, że i-ty węzeł jest przypisany do A_si. Ponieważ maksymalizacja kosztu krawędzi przeciętych przez podział i minimalizacja kosztu krawędzi z punktami końcowymi w tym samym zbiorze podziału są równoważne, funkcję celu można modelować jako funkcję energii, przyjmując w_i,j = -2c_i,j oraz f(x,y) = δ_x,y (tj. f(x,y) = 1 wtedy i tylko wtedy, gdy x = y, w przeciwnym razie wynosi 0), biorąc pod uwagę θ_i = 0. Dynamika użyta w (MéridaCasermeiro & López-Rodríguez, 2005) została nazwana best2.Metoda best2 polega na uzyskaniu największego spadku funkcji energii poprzez zmianę stanu tylko dwóch neuronów w danym momencie. Jeśli neurony p i q mają zostać zaktualizowane, oblicza się przyrosty energii ΔE(i, j), gdy s_p = i oraz s_q = j, dla i, j ∈ {1,…,K}. Następnie stan minimalnego wzrostu jest wybierany jako nowy stan sieci. Wykorzystując tę dynamikę, model MREM jest porównywany z niektórymi innymi sieciami, takimi jak OCHOM , uzyskując najlepsze wyniki w eksperymentach autorów .



Problem układu grafu 2-stronnicowego

W ostatnich latach w literaturze badano kilka problemów reprezentacji grafu. Większość z nich związana jest z liniowym problemem układu grafu, w którym wierzchołki grafu są rozmieszczone wzdłuż poziomej "linii węzłów" lub "grzbietu" (dzielącej płaszczyznę na dwie półpłaszczyzny lub "strony"), a następnie do tej reprezentacji dodawane są krawędzie określone przez macierz sąsiedztwa. Celem tego problemu jest minimalizacja liczby skrzyżowań generowanych przez taki układ. Niektóre przykłady problemów związanych z tym liniowym problemem układu grafu (lub problemem 2 stron przekraczających liczbę, 2PCNP) to problem przepustowości , problem grubości książki , problem numeru strony, problem układu granicznego VLSI i problem trasowania jednorzędowego , lub układ płytki drukowanej i automatyczne rysowanie grafu. Model neuronowy, wyprowadzony z MREM, został zaprojektowany do rozwiązania tego problemu. Jedną z różnic tego modelu z algorytmami opracowanymi w literaturze jest to, że nie ma potrzeby przypisywania dobrego uporządkowania wierzchołków na etapie wstępnego przetwarzania. Model, a także względne położenie łuków, oblicza optymalną kolejność węzłów. Aby rozwiązać problem 2PCNP, autorzy rozważyli dwa modele neuronowe MREM:

o Pierwsza sieć zostanie utworzona z N neuronów, gdzie N będzie liczbą węzłów w grafie. Wyjście neuronów (wektor stanu) wskazuje kolejność węzłów w linii. Zatem s_i = k będzie interpretowane jako umieszczeniek-tego węzła na i-tej pozycji w linii węzłów. Zatem wyjście każdego neuronu może przyjmować wartości ze zbioru M = {1,2,…N}
o Druga sieć zostanie utworzona z tylu neuronów, ile jest krawędzi w grafie, M. Wyjście każdego neuronu będzie należeć do zbioru M₂ = {-1,1}. Dla łuku (v_i, v_j), S_{(vi, vj)} = -1 będzie oznaczać, że krawędź zostanie narysowana w dolnej półpłaszczyźnie, a S_{(vi, vj)} = +1 w górnej.

Początkowo stan siatki wierzchołków jest losowo wybierany jako permutacja {1,2,…,N}. W dowolnym momencie sieć poszukuje lepszego rozwiązania niż obecne, pod względem minimalizacji funkcji energii. Osiąga się to poprzez permutację wyjścia dwóch neuronów (położeń węzłów) i zmianę położenia krawędzi (z górnej półpłaszczyzny na dolną i odwrotnie). W pracy ten nowy model jest porównywany z niektórymi heurystykami (Cimikowski, 2002) specjalnie zaprojektowanymi dla tego problemu. MREM uzyskał najlepsze rozwiązania w eksperymentach, ulepszając w niektórych przypadkach najlepsze znane rozwiązanie.



TRENDY NA PRZYSZŁOŚĆ

Rekurencyjne sieci neuronowe mogą być wykorzystywane do rozwiązywania wielu problemów optymalizacyjnych. Naukowcy i praktycy mogą skorzystać z zastosowania modelu neuronowego MREM w różnorodnych problemach optymalizacyjnych. Inne problemy, w których można zastosować te modele, obejmują takie aspekty, jak klasyfikacja danych, kompresja obrazu poprzez kwantyzację wektorową itp. Należy zauważyć, że wiele problemów opartych na grafach można łatwo sformułować w kategoriach minimalizacji funkcji energii tego modelu: minimalne drzewo rozpinające o ograniczonym stopniu, maksymalna klika itp.

WNIOSKI

Pierwsze prace nad optymalizacją za pomocą sieci neuronowych były inspirowane modelami Hopfielda. Modele te nie dawały dobrych rezultatów w porównaniu ze znanymi technikami badań operacyjnych. Wielu badaczy skupiło się na opracowaniu nowych modeli neuronowych w celu poprawy wydajności sieci typu Hopfielda w tego typu zadaniach. Problemem tych modeli binarnych jest to, że wszystkie informacje dostarczane przez problem muszą być określone za pomocą tylko dwóch wartości ({0,1} lub {-1,1}), co powoduje utratę niektórych informacji. Wielowartościowe modele neuronowe są zaprojektowane do reprezentowania informacji o problemie za pomocą więcej niż dwóch wartości, co pozwala na lepsze przedstawienie problemu. Dzięki temu ulepszeniu, dynamika obliczeniowa modeli wielowartościowych może być łatwo zaprojektowana w celu rozwiązania danego problemu optymalizacyjnego. Te zalety sprawiają, że tego rodzaju sieci są bardzo silnym sojusznikiem w rozwiązywaniu problemów kombinatorycznych. Model MREM jest modelem wielowartościowym, który uogólnia wiele innych modeli, dzięki czemu można go łatwo wykorzystać do rozwiązywania problemów optymalizacyjnych, jak pokazano w tekście. Niektóre zastosowania modelu to dobrze znane problemy optymalizacji NPzupełnej, takie jak problem komiwojażera, problem partycjonowania grafu i problem przecinania się liczb na 2 stronach. Jak pokazano w literaturze, model ten jest w stanie przewyższyć algorytm muptodate w każdym z wymienionych problemów.

WSTĘP

Modele i algorytmy zostały zaprojektowane tak, aby naśladować przetwarzanie informacji i pozyskiwanie wiedzy przez ludzki mózg, ogólnie nazywane sztucznymi lub formalnymi sieciami neuronowymi (ANN), równoległym przetwarzaniem rozproszonym (PDP), modelami neuromorficznymi lub koneksjonistycznymi. Termin "sieć" jest dziś powszechny: istnieją sieci komputerowe, komunikacja jest określana mianem sieciowania, korporacje i rynki są strukturyzowane w sieci. Koncepcja ANN została pierwotnie ukuta jako pełna nadziei wizja przewidywania syntezy sztucznej inteligencji (AI) poprzez emulację biologicznego mózgu. ANN stanowią alternatywę dla programowania symboli, mającą na celu implementację koncepcji inspirowanych neuronami w środowiskach AI (neural computing) , podczas gdy systemy poznawcze starają się naśladować rzeczywiste biologiczne układy nerwowe (neuronauka obliczeniowa). Wszystkie możliwe modele neuromorficzne plasują się pomiędzy nimi i mają być uproszczoną, ale znaczącą reprezentacją pewnej rzeczywistości. Aby ustanowić jednolitą teorię obliczeń neuronowych i neuronauki obliczeniowej, należy rozwijać teorie matematyczne wraz ze specyficznymi metodami analizy . Poniżej przedstawiono wstępnie zamknięte matematycznie ramy modelowania neuronowego.

TŁO

Sieci neuronowe można postrzegać jako systemy dynamiczne (dyskretne lub ciągłe), których stany stanowią wzorce aktywności, a elementy sterujące stanowią wagi synaptyczne, które kontrolują przepływ informacji między jednostkami przetwarzającymi (systemy adaptacyjne sterowane przez macierze synaptyczne). Sieci neuronowe są równoległe w tym sensie, że większość neuronów przetwarza dane jednocześnie. Proces ten może być synchroniczny, jeśli czas przetwarzania neuronu wejściowego jest taki sam dla wszystkich jednostek sieci, i asynchroniczny w przeciwnym razie. Modele synchroniczne można postrzegać jako modele dyskretne. Ponieważ neurony biologiczne są asynchroniczne, wymagają ciągłego traktowania czasu za pomocą równań różniczkowych. Alternatywnie, sieci neuronowe mogą rozpoznawać stan środowiska i oddziaływać na nie, aby dostosować się do danych ograniczeń żywotności (systemy poznawcze sterowane przez elementy sterujące). Wiedza jest przechowywana w elementach sterujących, a nie kodowana w macierzach synaptycznych, podczas gdy reguły uczenia się opisują dynamikę elementów sterujących w kategoriach ewolucji stanu w adaptacji do ograniczeń żywotności. Koncepcja paradygmatu odnosząca się do sieci neuronowych zazwyczaj obejmuje opis formy i funkcji jednostki przetwarzającej (neuronu, węzła), topologię sieci opisującą wzorzec ważonych połączeń między jednostkami oraz regułę uczenia się służącą do ustalania wartości wag . Chociaż paradygmaty różnią się szczegółami, nadal mają wspólny podzbiór wybranych atrybutów , takich jak proste jednostki przetwarzające, wysoka łączność, przetwarzanie równoległe, nieliniowa funkcja przejścia, ścieżki sprzężenia zwrotnego, niealgorytmiczne przetwarzanie danych, samoorganizacja, adaptacja (uczenie się) i odporność na błędy. Niektóre dodatkowe cechy mogą obejmować: generalizację, użyteczne dane wyjściowe z rozmytych danych wejściowych, oszczędność energii i potencjalną ogólną dużą szybkość działania. Dominujący w informatyce paradygmat cyfrowy zakłada, że informacje muszą być digitalizowane w celu uniknięcia zakłóceń i degradacji sygnału. W przeciwieństwie do tego neuron jest wysoce analogowy w tym sensie, że jego obliczenia opierają się na czasoprzestrzennych procesach integracyjnych płynnie zmieniających się prądów jonowych w strefie wyzwalania, a nie na bitach. Mimo to systemy neuronowe są wysoce wydajnymi i niezawodnymi procesorami informacji.

Pamięć i uczenie się

Specyfika procesów neuronalnych polega na ich dystrybutywnej i kolektywnej naturze. Zjawisko, w którym biologiczne sieci neuronowe (NN) zmieniają się w odpowiedzi na bodźce zewnętrzne, nazywa się samoorganizacją. Elastyczna natura ludzkiego mózgu, reprezentowana przez samoorganizację, wydaje się być odpowiedzialna za funkcję uczenia się, która jest specyficzna dla organizmów żywych. Zasadniczo uczenie się jest adaptacyjnym procesem samoorganizacji. Z punktu widzenia wspomagania uczenia istnieją nadzorowane i nienadzorowane klasyfikatory neuronowe. Klasyfikatory nadzorowane dążą do scharakteryzowania predefiniowanych klas poprzez zdefiniowanie miar, które maksymalizują podobieństwo wewnątrzklasowe i odmienność pozaklasową. Nadzór może być prowadzony albo poprzez bezpośrednie porównanie wyników z pożądanym celem i oszacowanie błędu, albo poprzez określenie, czy wyniki są poprawne, czy nie (uczenie przez wzmacnianie). Miarą sukcesu w obu przypadkach jest zdolność do odtworzenia klas oryginalnych dla podobnych, ale nie identycznych danych wejściowych. Klasyfikatory nienadzorowane poszukują miar podobieństwa bez żadnych predefiniowanych klas, wykonując analizę skupień lub kwantyzację wektorową. Klasyfikatory neuronowe organizują się według stanu początkowego, typów i częstotliwości prezentowanych wzorców oraz korelacji we wzorcach wejściowych, ustalając pewne kryteria klasyfikacji odzwierciedlające mechanizmy przyczynowe. Nie ma powszechnej zgody co do miary ich sukcesu, ponieważ optymalizacja prawdopodobieństwa zawsze faworyzuje klasy pojedynczych instancji. Klasyfikacja realizowana przez sieci neuronowe ma zasadniczo dwoistą interpretację, odzwierciedloną również w uczeniu maszynowym. Może ona oznaczać albo przypisanie wzorców wejściowych do predefiniowanych klas, albo konstrukcję nowych klas z wcześniej niezróżnicowanego zbioru instancji . Jednakże przypisanie instancji do predefiniowanych klas może dać w rezultacie klasę najlepiej reprezentującą wzorzec wejściowy, jak w klasycznej teorii decyzji, lub klasyfikator może być wykorzystany jako pamięć adresowalna treściowo lub asocjacyjna, gdzie pożądany jest reprezentant klasy, a wzorzec wejściowy służy do określenia, który egzemplarz ma zostać wygenerowany. Podczas gdy pierwsze zadanie zakłada, że dane wejściowe zostały zniekształcone przez pewne procesy, drugie zajmuje się niekompletnymi wzorcami wejściowymi, gdy celem jest uzyskanie pełnej informacji. Większość klasyfikatorów neuronowych nie wymaga jednoczesnej dostępności wszystkich danych treningowych i często generuje wskaźniki błędów porównywalne z metodami bayesowskimi bez konieczności wcześniejszej informacji. Wydajna pamięć może przechowywać i odzyskiwać wiele wzorców, dlatego jej dynamika musi uwzględniać jak najwięcej stanów aktywności, które są stabilne wobec niewielkich zaburzeń. Kilka podejść do radzenia sobie z niepewnością, takich jak logika rozmyta, klasyfikatory probabilistyczne, hiperpłaszczyznowe, jądrowe i oparte na przykładach, można włączyć do klasyfikatorów ANN w zastosowaniach, w których dostępnych jest niewiele danych . Zdolność analogowych systemów neuronowych do działania w nieprzewidywalnych środowiskach zależy od ich zdolności do reprezentowania informacji w kontekście. Kontekst sygnału może być złożonym zbiorem wzorców neuronowych, w tym tych, które stanowią proces uczenia się. Współdziałanie kontekstu i adaptacji jest fundamentalną zasadą paradygmatu neuronowego. Ponieważ tylko wariacje i różnice przekazują informacje, stała zmiana jest koniecznością dla systemów neuronowych, a nie źródłem trudności, jak w przypadku systemów cyfrowych.

MATEMATYCZNE RAMY MODELOWANIA NEURONÓW I SIECI

Podejściem do badania systemów neuronowych w ujęciu ogólnym jest teoria pola średniego z fizyki statystycznej, odpowiednia dla silnie powiązanych systemów, takich jak obszary korowe. Istnieje jednak duża luka między formalnym poziomem opisu modelu na poziomach pamięci asocjacyjnej a złożonością dynamiki neuronowej w sieciach biologicznych. Modelowanie neuronowe nie wymaga informacji dotyczących korelacji danych wejściowych, a raczej nieliniowych jednostek przetwarzania i wystarczająco dużej liczby zmiennych parametrów, które zapewniają elastyczność w dostosowywaniu się do dowolnej relacji między danymi wejściowymi i wyjściowymi. Modele można modyfikować zewnętrznie, przyjmując inną strukturę aksjomatyczną, oraz wewnętrznie, ujawniając nowe wewnętrzne zależności strukturalne lub funkcjonalne. Ranking kilku modeli neuromorficznych przeprowadza się ostatecznie na podstawie pewnej miary wydajności.

Modelowanie neuronów

Kluczowe problemy w każdym sztucznym systemie zaprojektowanym do naśladowania sieci neuronowych wynikają z (i) cech biologicznych, które należy zachować, (ii) macierzy łączności jednostek przetwarzających, której rozmiar rośnie wraz z kwadratem ich liczby, oraz (iii) czasu przetwarzania, który musi być niezależny od rozmiaru sieci. Biologicznie realistyczne modele neuronów mogłyby obejmować co najmniej:

o Funkcje przejścia o wartościach ciągłych (odpowiedź stopniowana), ponieważ wiele neuronów reaguje na sygnał wejściowy w sposób ciągły, chociaż nieliniowa relacja między sygnałem wejściowym a wyjściowym komórek jest cechą uniwersalną;

o Nieliniowe sumowanie sygnałów wejściowych i istotne przetwarzanie logiczne wykonywane wzdłuż drzewa dendrytycznego;

o Sekwencje impulsów jako sygnał wyjściowy, a nie prosty poziom wyjściowy. Pojedyncza zmienna stanu y_j reprezentująca częstotliwość wyładowań, nawet jeśli jest ciągła, ignoruje wiele informacji (np. fazę impulsów), które mogą być zakodowane w sekwencjach impulsów. Nie ma jednak istotnych dowodów na to, że faza odgrywa znaczącą rolę w większości obwodów neuronalnych;

o Asynchroniczna aktualizacja i zmienne opóźnienie przetwarzania danych, czyli jednostka czasu upływająca na krok przetwarzania, t ? t + 1, jest zmienna między neuronami;

o Zmienność siły synaptycznej spowodowana ilością substancji przekaźnikowej uwalnianej w synapsie chemicznej, która może zmieniać się w sposób nieprzewidywalny. Efekt ten jest częściowo modelowany przez stochastyczną generalizację dynamiki binarnych modeli neuronowych.

Większość modeli neuromimetycznych opiera się na neuronie McCullocha i Pittsa (1943) jako binarnej jednostce progowej:



gdzie y_j reprezentuje stan neuronu j (1 lub 0) w odpowiedzi na sygnały wejściowe {x_i}_i, θ_j oznacza pewien próg charakterystyczny dla każdego neuronu j, czas t jest uważany za dyskretny, z jedną jednostką czasu upływającą na każdy krok przetwarzania, a Θ jest jednostkową funkcją kroku (Heaviside′a):



Wagi w^j_i, 1 ≤ i ≤ N, reprezentują siłę synaps łączących neuron i z neuronem j i mogą być dodatnie (pobudzające) lub ujemne (hamujące). Suma ważona



sygnałów wejściowych prezentowanych w czasie t jednostce j muszą osiągnąć lub przekroczyć próg θ_j, aby neuron j został aktywowany. Choć jest to skrajnie uproszczone, synchroniczny zespół takich formalnych neuronów teoretycznie jest zdolny do uniwersalnych obliczeń dla odpowiednio dobranych wag {w^j_i}_ij , tj. może wykonywać obliczenia wykonywane przez konwencjonalne komputery, ale niekoniecznie tak szybko i wygodnie. Ogólne wyrażenie, które zawiera niektóre z powyższychcech wyprowadzonych z modelu cyfrowego (1), to:



gdzie y_j jest stanem (aktywacją) jednostki j o wartościach ciągłych, a f_j jest ogólną funkcją przejścia. Węzły progowe są wymagane do uniwersalnej aproksymacji, a funkcja aktywacji powinna być nieliniowa z ograniczonym wyjściem . Neurony są aktualizowane asynchronicznie w losowej kolejności i w losowych momentach.

Matematyczne metody modelowania sieci neuronowych

Zaproponowano kilka modeli neuronowych i równoległych systemów przetwarzania informacji inspirowanych mechanizmami mózgu. Niemal wszystkie praktyczne zastosowania uzyskano poprzez symulację na konwencjonalnych komputerach cyfrowych (von Neumann), co oznacza, że utracono rzeczywiste korzyści z przetwarzania równoległego i oczekiwane ogromne gęstości jednostkowe. Metody matematyczne ujednolicające podejście do różnych typów sieci neuronowych oraz wyniki z liniowych i nieliniowych układów sterowania wykorzystywane do uzyskiwania algorytmów uczenia się można podzielić na cztery kategorie:

1. Iloczyny tensorowe i pseudoodwrotności operatorów liniowych, które reprezentują specyficzny koneksjonizm strukturalny i dostarczają matematycznego wyjaśnienia hebbowskiej natury wielu algorytmów uczenia się . Wynika to z faktu, że pochodne szerokiej klasy odwzorowań nieliniowych zdefiniowanych na przestrzeniach macierzy synaptycznych są iloczynami tensorowymi, a pseudoodwrotność iloczynu tensorowego operatorów liniowych jest iloczynem tensorowym ich pseudoodwrotności;
2. Analiza wypukła i niegładka jest szczególnie przydatna dla sieci nieliniowych w dowodzeniu zbieżności dwóch głównych typów reguł uczenia. Pierwsza klasa składa się z algorytmów wyprowadzonych z metod gradientowych i obejmuje regułę aktualizacji propagacji wstecznej, natomiast druga klasa dotyczy algorytmów opartych na metodzie Newtona;
3. Teoria sterowania i wykonalności , która zajmuje się systemami neuronowymi uczącymi się wykonalnych rozwiązań jako systemami sterowania spełniającymi zadane ograniczenia wykonalności (stanu). Celem jest wyprowadzenie algorytmów systemów sterowania emulowanych przez sieci neuronowe z regulacją sprzężenia zwrotnego. Przewiduje się trzy klasy reguł uczenia: (i) zewnętrzne reguły uczenia oparte na metodach gradientowych problemów optymalizacyjnych obejmujących funkcje niegładkie, (ii) wewnętrzne reguły uczenia oparte na teorii wykonalności oraz (iii) algorytmy jednorodne;
4. Rachunek prawdopodobieństwa i statystyka bayesowska. Statystyka bayesowska i modelowanie neuronowe mogą wydawać się skrajnościami spektrum modelowania danych. Sieci neuronowe to nieliniowe, równoległe urządzenia obliczeniowe, a ich trenowanie na przykładach w celu rozwiązywania problemów predykcyjnych i klasyfikacyjnych jest procedurą specyficzną dla konkretnego celu. Z kolei statystyka bayesowska w dużej mierze opiera się na wnioskowaniu spójnym i jasno zdefiniowanych aksjomatach. Jednak oba podejścia mają na celu tworzenie modeli zgodnych z danymi. Sieci neuronowe można interpretować jako bardziej elastyczne wersje tradycyjnych technik regresji, w tym sensie, że wychwytują regularności w danych, których modele liniowe nie są w stanie obsłużyć. Jednak nadmiernie elastyczne sieci neuronowe mogą odkryć nieistniejące korelacje w danych. Wnioskowanie bayesowskie zapewnia sposób wnioskowania o tym, jak elastyczny jest model w świetle danych i tłumi tendencję do oceny pozornej struktury danych poprzez zastosowanie brzytwy Ockhama, która preferuje prostsze modele, jeśli konkurują one o uzyskanie tego samego wyniku. Uczenie się w sieciach neuronowych interpretuje się jako wnioskowanie na podstawie najbardziej prawdopodobnych parametrów modelu, biorąc pod uwagę dane treningowe. Przeszukiwanie przestrzeni modelu można również traktować jako problem wnioskowania prawdopodobieństwa względnego dla modeli alternatywnych, biorąc pod uwagę dane. Wnioskowanie bayesowskie dla sieci neuronowych można zaimplementować numerycznie metodami deterministycznymi wykorzystującymi aproksymacje Gaussa lub metodami Monte Carlo .

Niech N formalnych neuronów połączy, bezpośrednio dla sieci jednowarstwowych i pośrednio dla sieci wielowarstwowych, przestrzeń wejściową X sygnałów z przestrzenią wyjściową Y. Przestrzeń stanu systemu jest iloczynem X × Y par wejście-wyjście (x, y), które są generycznie nazywane wzorcami lub konfiguracjami w rozpoznawaniu wzorców (PR), analizie danych i problemach klasyfikacji. Gdy X = Y, a dane wejściowe wzorców pokrywają się z danymi wyjściowymi, (x, y), x = y, system nazywa się autoasocjacyjnym; jeśli wzorce wejściowe i wyjściowe są różne, (x, y) y ≠ x, to system jest heteroasocjacyjny. Spośród wszystkich możliwych wzorców wejście-wyjście, podzbiór K ⊂ X × Y jest wybierany jako zbiór treningowy. Najczęściej przestrzenie wejściowe i wyjściowe są skończenie wymiarowymi przestrzeniami liniowymi: X = ?ℝ N i Y = ℝ^M? , podczas gdy sygnały wejściowe mogą podlegać pewnym ograniczeniom stanu:

o Liczby rzeczywiste dla zastosowań rozmytych, najlepiej w przedziałach [0, 1] lub [-1, +1];
o Liczby binarne należące do {0, 1};
o Liczby bipolarne należące do {-1, +1}.

Jeśli neurony są oznaczone przez j = 1, 2,..., N, niech P(N) liczby kardynalnej 2N oznacza rodzinę podzbiorów neuronów zwanych koniunkcjami (lub koalicjami) neuronów. Każde połączenie łączy neuron postsynaptyczny j z koniunkcjami S ⊂ P(N) neuronów presynaptycznych. Każda koniunkcja S wstępnie przetwarza (lub bramkuje) sygnały aferentne {x_i)_i wytwarzane przez neurony presynaptyczne za pomocą funkcji:



Jeżeli połączenia zredukowane zostaną do pojedynczych neuronów S = {i}, to rolę kontrolną pełni macierz synaptyczna:



gdzie w_j^S w reprezentuje wejścia z S do neuronu j. Moduł wagi synaptycznej w_j^S reprezentuje siłę i określa charakter połączenia od koniunkcji S do formalnego neuronu j, liczonego dodatnio, jeśli synapsa jest pobudzająca, i ujemnie, jeśli jest hamująca. W związku z tym neuron j odbiera sygnał



(rysunek 2),



który określa jego stan aktywności. Zatem reguła propagacji charakteryzująca dynamikę sieci jest następująca:



dla neuronów synchronicznych (dyskretny układ dynamiczny) oraz:



dla neuronów asynchronicznych (ciągły układ dynamiczny), gdzie w większości przypadków:



Tutaj g_j integruje sygnały aferentne {w_j^Sφ_s(x)} wysłane do neuronu j przez neurony aferentne poprzez ich wyjścia {xi}i, wstępnie przetworzone przez koniunkcję S i dostarczone do neuronu j za pomocą wagi w_j^S. Zwykle wagi synaptyczne w_j^S = 0 w = gdy j ∈ S, podczas gdy w_j^S≠ 0 gdy j ∈? S jest związane z autowzbudzeniem. Jednakże, gdy S = {j}, S ≠ {i} i w_j^S= 0, wówczas człon stratyg_j(0,0,…,wⁱ_jφ_j(x),0…0) reprezentuje pewien rodzaj zapominania, jak zanikająca częstotliwość, podczas gdy dany neuron j nie jest pobudzany przez pozostałe. W ramach tego modelu można wyróżnić kilka układów neuronowych.

1. Pamięć asocjacyjna jest definiowana przez brak wstępnego przetwarzania, czyli:



wtedy



gdzie |S| oznacza liczbę elementów w koniunkcji S.

2. Pamięci asocjacyjne z bramkami są definiowane przez wstępne przetwarzanie i afiniczne g_j:



Pamięci asocjacyjne Boole′a odpowiadają
N,Y=ℝ,K={0,1}^N x {0,1}

i niewyraźne wspomnienia skojarzeniowe

X = ℝ^N,Y=ℝ,K=[0,1]^N x [0,1]

zatem



3. Automaty nieliniowe definiowane są za pomocą różnych form g_j:



W stosownych przypadkach progi θ∈ Y można zintegrować w funkcji przetwarzania g:

g(z) = h(z-θ) (13) Jeżeli próg stanowi część elementów sterujących, które mają zostać dostosowane podczas treningu, można go włączyć jako wpis do rozszerzonej macierzy synaptycznej:



Szczególnie prosty jest perceptron:





PRZYSZŁE TRENDY

Zaproponowano również kilka obiecujących, inspirowanych neuronami, podejść do ekstrakcji i klastrowania cech , które są adaptacyjne online i mogą wykazywać dodatkowe pożądane właściwości, takie jak odporność na obserwacje odstające, w porównaniu z bardziej tradycyjnymi metodami ekstrakcji cech. Połączenie wnioskowania bayesowskiego z modelami neuronowymi otwiera nowe perspektywy dla założeń i aproksymacji przyjmowanych w sieciach neuronowych (SN) i algorytmach wykorzystywanych jako pamięci asocjacyjne. Postęp w modelowaniu neuronowym i projektowaniu algorytmów uczenia rozwiązał problemy z zakresem dynamiki i czułością, z którymi borykają się duże systemy analogowe, a także szybka ewolucja technik implementacji VLSI, co może prowadzić do powstania praktycznych systemów czasu rzeczywistego opartych na topologii i równoległym przetwarzaniu rozproszonym wykonywanym przez biologiczne sieci neuronowe.

WNIOSKI

Chociaż sieci neuronowe są w stanie wykonywać szeroką gamę zadań, problemy, którymi się zajmują w praktyce, można z grubsza podzielić na cztery podstawowe typy : auto- lub heteroasocjacja, klasyfikacja, mapowanie oraz modelowanie. W klasyfikatorach neuronowych zbiór przykładów użytych do treningu powinien koniecznie pochodzić z tego samego (potencjalnie nieznanego) rozkładu, co zbiór użyty do testowania sieci, aby zapewnić wiarygodną generalizację w klasyfikacji nieznanych wzorców. Prawidłowe wyniki uzyskuje się tylko wtedy, gdy przykłady treningowe są odpowiednio dobrane, a ich liczba jest porównywalna z liczbą efektywnych parametrów w sieci. Wiele klas algorytmów uczących się ma zagwarantowaną konwergencję; co więcej, wymagają one znacznych zasobów obliczeniowych. Zazwyczaj sieci neuronowe są wykorzystywane jako elementy większych systemów wykorzystywanych jako podsystemy przetwarzania wstępnego lub etykietowania/interpretacji. W wielu przypadkach elastyczność i brak konieczności stosowania algorytmów w przypadku sieci neuronowych przeważają nad ich niedogodnościami i sprawiają, że nadają się one do modelowania dość złożonych systemów, które obejmują dużą ilość informacji.

WSTĘP Niniejsza sekcja rozpoczyna się od dokładnej analizy niezawodności multipleksowania von Neumanna na poziomie bramki, wykorzystując bramki większościowe o rosnących wartościach fan-in (Δ = 3, 5, 7, 9, 11) przy najmniejszych współczynnikach redundancji (R_F = 2Δ), a następnie szczegółowo omawia dokładną analizę na poziomie urządzenia. Analiza ta uzupełnia znane wyniki teoretyczne i symulacyjne. Analiza na poziomie bramki jest dokładna, ponieważ została uzyskana za pomocą zliczania wyczerpującego. Rozszerzenie (dokładnej analizy na poziomie bramki) na błędy na poziomie urządzenia pozwoli nam analizować multipleksowanie większościowe von Neumanna w odniesieniu do awarii urządzeń. Wyniki te wyjaśniają nieprawidłowe zachowania multipleksowania von Neumanna zgłoszone na podstawie symulacji Monte Carlo. Analizy te pokazują, że wyniki niezawodności na poziomie urządzenia znacznie różnią się od wyników na poziomie bramki i mogą mieć istotne implikacje dla przyszłych projektów (nano)obwodów. SIA (2005) przewiduje, że przemysł półprzewodników będzie kontynuował sukcesy w skalowaniu CMOS przez kilka kolejnych generacji. Skalowanie to powinno stać się bardzo trudne przy zbliżaniu się do 16 nm. Skalowanie może trwać dalej, ale alternatywne nanourządzenia mogą być zintegrowane z CMOS na tej samej platformie. Oprócz wyższej czułości przyszłych ultramałych urządzeń, jednoczesny wzrost ich liczby stworzy sprzyjające warunki do punktu zwrotnego w sposobie, w jaki traktujemy niezawodność. Wraz ze zmniejszaniem się geometrii dostępne marginesy niezawodności przyszłych nanourządzeń ulegają znacznemu zmniejszeniu . Z perspektywy projektantów układów scalonych niezawodność przejawia się obecnie w niepewnościach zależnych od czasu i wahaniach parametrów elektrycznych. W erze nano, te niepewności parametryczne na poziomie urządzeń stają się zbyt wysokie, aby można je było obsłużyć za pomocą dominujących technik projektowania uwzględniających najgorszy scenariusz - bez ponoszenia znaczących strat w zakresie powierzchni, opóźnień oraz mocy/energii. Globalny obraz pokazuje, że niezawodność wydaje się jednym z największych zagrożeń dla projektowania przyszłych układów scalonych. W przypadku nowych nanourządzeń i powiązanych z nimi połączeń, przewidywane prawdopodobieństwo awarii może sprawić, że przyszłe nanoukłady scalone będą skrajnie zawodne. Obecne podejście projektowe oparte na konwencjonalnym założeniu zerowej liczby defektów jest poważnie kwestionowane. Dlatego też techniki tolerancji defektów będą musiały być uwzględniane już na wczesnych etapach projektowania. Niezawodność technologii wykraczających poza CMOS prawdopodobnie ulegnie dalszemu pogorszeniu, ponieważ przewiduje się, że wskaźniki awaryjności urządzeń sięgną nawet 10% w przypadku technologii pojedynczego elektronu, czyli SET, a nawet 30% w przypadku samoskładającego się DNA . Ponadto, kompleksowa analiza nanorurek węglowych do przyszłych połączeń międzysystemowych oszacowała wahania opóźnienia na około 60% w stosunku do wartości nominalnej. Ostatnio odnotowano wskaźniki defektów na poziomie 60% dla molekularnej pamięci elektronicznej o pojemności 160 kbitów . Osiągnięcie 100% poprawności z 10¹² nanourządzeniami będzie nie tylko skandalicznie drogie, ale wręcz niemożliwe! Złagodzenie wymogu 100% poprawności powinno obniżyć koszty produkcji, weryfikacji i testowania, a jednocześnie prowadzić do większej liczby błędów przejściowych i trwałych. Wynika z tego, że większość (jeśli nie wszystkie) tych błędów będzie musiała zostać skompensowana za pomocą technik architektonicznych . Z perspektywy projektowania systemów błędy dzielą się na: trwałe (defekty), okresowe i przejściowe (awarie). Źródeł tych błędów można doszukiwać się w procesie produkcyjnym, zmianach fizycznych zachodzących podczas eksploatacji, a także w wrażliwości na zakłócenia i zmiany wewnętrzne i zewnętrzne. Nie jest jasne, czy rozwijające się nanotechnologie nie będą wymagały nowych modeli błędów, czy też konieczne będzie radzenie sobie z wieloma błędami. Kuo (2006) wspomniał nawet, że: "nie jesteśmy pewni, czy znaczna część wiedzy opartej na technologiach z przeszłości jest nadal aktualna dla analizy niezawodności". Znanym podejściem do walki z błędami jest włączenie redundancji: statycznej (w przestrzeni, czasie lub informacji) lub dynamicznej (wymagającej wykrywania, lokalizacji, ograniczania i odzyskiwania błędów). Redundancja przestrzenna (sprzętowa) opiera się na wyborcach (generycznych, niedokładnych, o średniej wartości, medianowych, ważonych średnich, analogowych, hybrydowych itp.) i obejmuje: redundancję modułową, kaskadową redundancję modułową oraz multipleksowanie, takie jak multipleksowanie von Neumanna vN-MUX (von Neumann, 1952), ulepszony vN-MUX oraz restytucję równoległą. Redundancja czasowa polega na zamianie przestrzeni na czas, podczas gdy redundancja informacyjna opiera się na detekcji i kodach korekcji błędów. W tym rozdziale omówiono wydajność vN-MUX przy użyciu bramek większościowych Δ (MAJ-Δ). Celem jest uzyskanie jasnego zrozumienia kompromisów między poprawą niezawodności uzyskaną przy użyciu MAJ-Δ vN-MUX przy najmniejszych współczynnikach redundancji R_F = 2Δ



z jednej strony, a zarówno fan-inami, jak i zawodnymi nanourządzeniami z drugiej strony. Rozpoczniemy od przeglądu niektórych wyników teoretycznych i symulacyjnych dla vN-MUX w sekcji "Wprowadzenie". Dokładne symulacje na poziomie bramek (oparte na wyczerpującym algorytmie zliczania) i dokładne oszacowania na poziomie urządzeń, w tym szczegóły dotyczące wpływu nanourządzeń na MAJ-Δ vN-MUX, przedstawiono w sekcji "Główny temat" rozdziału.

TŁO

Multipleksowanie zostało wprowadzone przez von Neumanna jako schemat niezawodnych obliczeń (von Neumann, 1952). vN-MUX opiera się na kolejnych etapach obliczeniowych naprzemiennie z losowymi etapami połączeń. Każdy etap obliczeniowy zawiera zestaw redundantnych bramek. Chociaż vN-MUX został pierwotnie zilustrowany dla NAND-2, można go zaimplementować przy użyciu dowolnego typu bramki i zastosować na dowolnym poziomie abstrakcji (podukłady, bramki lub urządzenia). "Multipleksowanie" każdego obliczenia ma na celu zmniejszenie prawdopodobieństwa dalszej propagacji błędów poprzez wybór bardziej prawdopodobnych wyników na każdym etapie. Redundancja jest kwantyfikowana za pomocą współczynnika redundancji RF, który wskazuje iloczynowy wzrost liczby bramek (podukładów lub urządzeń). W swoim oryginalnym badaniu von Neumann (1952) założył niezależne (nieskorelowane) awarie bramek pf_GATE i bardzo duży współczynnik R_F. Wydajność NAND-2 vN-MUX została porównana z innymi technikami odpornymi na błędy w pracy , a analizowano ją przy niższym RF (od 30 do 3000) w pracy (Han i Jonker, 2002), natomiast pierwszą dokładną analizę przy bardzo niskim R_F (od 3 do 100) dla MAJ-3 vN-MUX przeprowadzono w pracy . Kwestia, której bramki należy użyć, jest dyskusyjna . Udowodniono, że użycie MAJ-3 może prowadzić do poprawy obliczeń vN-MUX tylko dla pf_MAJ-3 < 0,0197 (von Neumann, 1952). Przewyższa to próg błędu NAND-2 pf_NAND-2 < 0,0107 (von Neumann, 1952) (Sadek i in., 2004). Kilka innych badań wykazało, że progi błędu MAJ są wyższe niż NAND w przypadku zastosowania w vN-MUX. Evans (1994) udowodnił, że:



podczas gdy próg błędu dla NAND-ΔΔ został określony w (Gao et al., 2005) poprzez rozwiązanie:



Podejście do lepszego zrozumienia vN-MUX przy bardzo małym RF polega na wykorzystaniu symulacji Monte Carlo . Pokazały one, że niezawodność NAND-2 vN-MUX jest w rzeczywistości lepsza niż MAJ-3 vN-MUX (przy R_F = 6) dla małych zmian geometrycznych ?. W przeciwieństwie do wyników teoretycznych - gdzie niezawodność MAJ-3 vN-MUX jest zawsze lepsza niż NAND-2 vN-MUX - symulacje Monte Carlo pokazały, że MAJ-3 vN-MUX jest lepszy niż NAND-2 vN-MUX, ale tylko dla ? > 3,4%. Takich wyników nie przewidziano (teorią) ani nie sugerowano (symulacjami na poziomie bramek). Należy tutaj podkreślić, że wszystkie publikacje teoretyczne omawiają zawodne organy, bramki, węzły, obwody lub wzory, ale bardzo niewiele z nich wspomina o urządzeniach. Aby uzyskać jasny obraz, zaczęliśmy od opracowania kompleksowego algorytmu zliczającego, który dokładnie oblicza niezawodność MAJ-Δ vN-MUX . Prawdopodobieństwo awarii MAJ-Δ vN-MUX wynosi:



Wyniki oparte na wyczerpującym liczeniu przy zmiennym pf_MAJ-Δ potwierdziły zarówno wyniki teoretyczne, jak i symulacyjne. MAJ-Δ vN-MUX przy minimalnym współczynniku redundancji R_F = 2Δ poprawia niezawodność w porównaniu z MAJ-Δ, gdy pfMAJ-Δ ? 10%, a zwiększenie Δ zwiększa niezawodność. Gdy pf_MAJ-Δ wynosi 10%, użycie vN-MUX zwiększa niezawodność w porównaniu z MAJ-Δ, o ile pf_MAJ-Δ jest niższe od określonego progu błędu. Jeśli pf_MAJ-Δ przekracza próg błędu, użycie vN-MUX jest szkodliwe, ponieważ niezawodność systemu jest niższa niż MAJ-Δ. Mimo to nie wyjaśnia to wyników symulacji Monte Carlo wspomnianych wcześniej.

GŁÓWNY CEL

Zarówno pierwotne badanie vN-MUX, jak i późniejsze badania teoretyczne uwzględniały bramki zawodne. Nie uwzględnili elementów elementarnych i założyli, że bramki mają stałą (ograniczającą) wartość pf_GATE. To założenie pomija fakt, że różne bramki są budowane z wykorzystaniem różnej (liczby) elementów, stylów logicznych lub (nowych) zasad technologicznych. Podczas gdy standardowy inwerter CMOS ma 2 tranzystory, NAND-2 i MAJ-3 mają odpowiednio 4 i 10 tranzystorów. Forshaw i inni zasugerowali, że wartość pfGATE można oszacować jako:

pf_GATE= 1-(1- ε)ⁿ

gdzie ε oznacza prawdopodobieństwo awarii nanourządzenia (np. tranzystora, złącza, kondensatora, cząsteczki, kropki kwantowej itp.), a n to liczba nanourządzeń w bramce. Używając równania 4 jako pf_MAJ-Δ = 1 - (1 -ε)2Δ, niezawodności oszacowano, modyfikując dokładne wyniki zliczania podane w (Beiu 2007). Oszacowania na poziomie urządzenia przedstawiono na rysunku 2.



Pokazują one, że zwiększenie Δ niekoniecznie zwiększy niezawodność MAJ-Δ vN-MUX (w porównaniu z MAJ-Δ). Dzieje się tak, ponieważ MAJ-Δ z większym Δ wymaga większej liczby nanourządzeń. W szczególności, chociaż MAJ-11 vN-MUX jest najlepszym rozwiązaniem dla ε ≤ 1‰ (rysunek 2(a)), staje się najgorszym rozwiązaniem dla ε > 2 % (rysunek. 2(b)). Zatem większe fan-iny są korzystne dla niższego ε (≤ 1‰), podczas gdy mniejsze fan-iny działają lepiej dla większego ε (> 1%). Oczywiście istnieje obszar "zamiany", w którym kolejność jest odwracana. Szczegółowo przedstawiamy rysunek 2(b) dla ε > > 1%) (rysunek 2(c)) oraz dla obszaru "zamiany" 1‰ < ε < 2% (rysunek 2(d), gdzie znaki "?" oznaczają obwiednię). Wyniki te sugerują, że zwiększenie Δ i/lub R_F niekoniecznie poprawia ogólną niezawodność systemu. Dzieje się tak, ponieważ zwiększenie Δ i/lub R_F prowadzido zwiększenia liczby nanourządzeń:



Należy uwzględnić tę kwadratową zależność od Δ. Zasadniczo, to ε i liczba urządzeń N, a nie (tylko) R_F i pf_GATE, powinny być używane przy próbie dokładnego przewidywania zalet vN-MUX - lub dowolnego innego schematu redundancji. Następnym krokiem było porównanie oszacowań na poziomie urządzenia dla MAJ-Δ vN-MUX (rysunek 3(a)) z oszacowaniami symulacji Monte Carlo (rysunek 3(b), zaadaptowanymi z (Beiu, 2005) (Beiu i Sulieman, 2006)). Dwa wykresy na rys. 3 mają tę samą skalę pionową i podobne kształty.



Mimo to bezpośrednie porównanie nie jest trywialne, ponieważ są one mapowane na różne zmienne (odpowiednio ε i v). To podobieństwo utwierdza nas w przekonaniu, że oszacowane wyniki są dokładne i potwierdzają twierdzenie, że proste oszacowanie dla pf_GATE prowadzi do dobrych przybliżeń na poziomie systemu.

PRZYSZŁE TRENDY

W pierwszej serii eksperymentów porównaliśmy niezawodność MAJ-Δ z niezawodnością MAJ-Δ vN-MUX przy RF = 2Δ. W przypadku analiz na poziomie urządzenia nie jest to już oczywiste, ponieważ MAJ-Δ nie leżą na linii 45°, co utrudnia zrozumienie, gdzie i o ile vN-MUX poprawia się w porównaniu z MAJ-Δ. Wyniki tych symulacji można zobaczyć na rysunk 4, gdzie zastosowaliśmy ten sam przedział ε∈ [0, 0,11] na osi poziomej. Tutaj ponownie wygląda na to, że najmniejszy wachlarz jest najlepszy.



W drugiej serii eksperymentów zbadano wpływ zmiany Δ na próg błędu MAJ-Δ vN-MUX.



Rysunek 5(a) przedstawia teoretyczne progi błędów na poziomie bramki (z wykorzystaniem równania (1)), a także osiągalne progi błędów na poziomie bramki, oszacowane na podstawie symulacji z wykorzystaniem algorytmu zliczania wyczerpującego. Rysunek 5(a) pokazuje, że dokładne progi błędów na poziomie bramki są wyższe niż teoretyczne wartości progowe błędów na poziomie bramki (o około 33%). Wydaje się, że zawsze można zwiększyć niezawodność, stosując większy zakres wejścia. Rozszerzenie na oszacowania na poziomie urządzenia można zobaczyć na rysunek 5(b), co ukazuje zupełnie inny obraz. Wyniki te sugerują, że:

o progi błędów na poziomie urządzenia są około 10 razy niższe niż progi błędów na poziomie bramki;
o progi błędów na poziomie urządzenia maleją wraz ze wzrostem zakresu wejścia (dokładnie odwrotnie niż progi błędów na poziomie bramki);
o dla vN-MUX najwyższy próg błędu na poziomie urządzenia, wynoszący około 4%, osiąga się przy użyciu MAJ-3.

WNIOSKI

W niniejszym rozdziale przedstawiono szczegółową analizę MAJ-Δ vN-MUX dla bardzo małych fan-inów: dokładną na poziomie bramek i szacowaną, ale dokładną na poziomie urządzeń. Główne wnioski są następujące:

o Dokładne progi błędów na poziomie bramek dla MAJ-Δ vN-MUX są o około 33% lepsze niż teoretyczne i rosną wraz ze wzrostem fan-inów.
o Oszacowane progi błędów na poziomie urządzeń są około 10 razy niższe niż progi błędów na poziomie bramek i maleją wraz ze wzrostem fan-inów - dzięki czemu mniejsze fan-iny są lepsze
o Nieprawidłowe (nieliniowe) zachowanie vN-MUX wynika z faktu, że bramki elementarne są zbudowane z zawodnych nanourządzeń (co jest pośrednio uwzględniane w symulacjach Monte Carlo, ale pomijane w podejściach teoretycznych i symulacjach na poziomie bramek).
o Rozszerzenie dokładnych symulacji na poziomie bramek na oszacowania na poziomie urządzeń z wykorzystaniem równania 1 - (1 - ε)ⁿ prowadzi do dość dokładnych przybliżeń (w porównaniu z symulacjami Monte Carlo).
o Oszacowania na poziomie urządzeń wykazują znacznie bardziej złożone zachowania niż te ujawnione przez analizy na poziomie bramek (nieliniowe dla dużych ε, prowadzące do wielokrotnych i skomplikowanych przejść).
o Oszacowania na poziomie urządzeń sugerują, że optymalizacje niezawodności dla dużych ? będą trudniejsze niż oczekiwano na podstawie analiz na poziomie bramek.
o Jednym ze sposobów maksymalizacji niezawodności, gdy ? jest duże i nieznane (np. zmienne w czasie ), jest poleganie na bramkach "adaptacyjnych", więc inspiracja neuronowa powinna odgrywać ważną rolę w przyszłych projektach nano-IC .

Wreszcie, precyzja jest bardzo ważna, ponieważ drobne błędy… mają ogromny wpływ na oszacowanie wymaganego poziomu redundancji dla osiągnięcia określonej/docelowej niezawodności. Wydaje się, że obecne modele na poziomie bramek mają tendencję do niedoszacowania niezawodności, podczas gdy my nie radzimy sobie dobrze na poziomie urządzenia, a symulacja Monte Carlo jest jedyną powszechnie stosowaną metodą. Dokładniejsze oszacowania niż te przedstawione w tym rozdziale są możliwe przy użyciu symulacji Monte Carlo w połączeniu z algorytmami niezawodności na poziomie bramek. Są one wyraźnie potrzebne i dopiero rozpoczęto ich badanie .

WSTĘP

Aktualizacje stanowią kluczowy problem w relacyjnych bazach danych i bazach wiedzy. W ostatnich latach zostały one gruntownie zbadane w paradygmacie wnioskowania niemonotonicznego. Zaproponowano kilka semantyk dla aktualizacji programów logicznych. Jednak ostatnio scharakteryzowano szereg propozycji, które proponują mechanizmy aktualizacji oparte na logice i programowaniu logicznym. Wszystkie te mechanizmy opierają się na semantyce opartej na właściwościach strukturalnych. Co więcej, wszystkie te semantyczne założenia pokrywają się w rozważaniu propozycji AGM jako modelu standardowego w teorii aktualizacji, ze względu na bogactwo jej właściwości. Podejście AGM, wprowadzone w (Alchourron, Gardenfors i Makinson, 1985), jest dominującym paradygmatem w tej dziedzinie, ale w kontekście logiki monotonicznej. Wszystkie te propozycje analizują i reinterpretują postulaty AGM w ramach programowania zbiorów odpowiedzi (ASP), takie jak (Eiter, Fink, Sabattini i Thompits, 2000). Jednak większość zaadaptowanych postulatów AGM i aktualizacji jest naruszana przez programy aktualizujące, jak pokazano w (De Schreye, Hermenegildo i Pereira, 1999).

AKTUALIZACJE

Teoria aktualizacji zajmuje się bazą wiedzy reprezentowaną przez teorię zdań. Ponadto zajmuje się włączaniem nowej wiedzy o dynamicznym świecie. Dynamika ta wynika z faktu, że wiedza pochodzi ze świata rzeczywistego, co oznacza, że wiedza ewoluuje w czasie. Ten kurs wymiany dotyczy głównie zmian w ekstensjonalnej części baz wiedzy. Jednak problem aktualizacji intencjonalnej części bazy wiedzy (reguł i opisów działań) pozostaje zasadniczo niezbadany. Problem aktualizacji przyciągnął jednak w ostatnich latach uwagę badaczy, którzy zajmują się takimi aktualizacjami w kontekście programów logicznych. Istnieją jednak pewne interesujące propozycje oparte na programowaniu zbiorów odpowiedzi (ASP).Programowanie zbiorów odpowiedzi to nowy paradygmat stosowany w rozwiązywaniu problemu aktualizacji. W szczególności paradygmat ten zyskał większą popularność w teorii aktualizacji. Wiele prac teoretycznych na temat aktualizacji w ramach ASP zostało opracowanych przez uznanych badaczy, takich jak: Pereira, Alferes, Eiter, Osorio, Leite, Zacarias i inni. W ostatnich latach wiele prac teoretycznych poświęcono badaniu relacji między logiką intuicjonistyczną a ASP. Wyniki te niedawno dostarczyły następującej charakterystyki ASP za pomocą logiki intuicjonistycznej: literał jest implikowany przez program w semantyce zbioru odpowiedzi wtedy i tylko wtedy, gdy należy do każdego intuicjonistycznie kompletnego i spójnego rozszerzenia programu utworzonego przez dodanie wyłącznie literałów zanegowanych . Pomysł tych uzupełnień z wykorzystaniem logiki pośredniej pochodzi od Pearce′a. To logiczne podejście stanowi podstawę do zdefiniowania pojęcia wnioskowania niemonotonicznego dowolnej teorii zdań (z wykorzystaniem standardowych spójników) w kategoriach logiki monotonicznej (mianowicie logiki intuicjonistycznej)

ROZPOCZĘCIE OD AGM

Rozpoczynamy od analizy postulatów AGM, a następnie badamy je w odniesieniu do sekwencji aktualizacji. Wszystkie te propozycje opierają się na zasadzie odrzucenia przyczynowego. Jak wiadomo, jeśli w jakiś sposób uzyskuje się nową wiedzę o świecie i nie jest ona sprzeczna z wiedzą poprzednią, to jedynie ją poszerza. Jeśli natomiast nowa wiedza jest sprzeczna z wiedzą poprzednią, a chcemy, aby wiedza była zawsze spójna w każdym momencie, powinniśmy w jakiś sposób rozwiązać ten problem. Zwracamy uwagę, że nowe informacje są włączane do bieżącej bazy wiedzy zgodnie z zasadą odrzucenia przyczynowego, która wymusza, aby w przypadku konfliktów między regułami preferowane były reguły nowsze, a starsze były pomijane. Teoria aktualizacji to baza wiedzy reprezentowana przez program logiczny. Następnie niech P będzie programem reprezentującym bieżącą bazę wiedzy, jeśli jest ona aktualizowana przez inny program U, wtedy P_U jest programem zaktualizowanym dla P, jeśli tylko modele P_U są wynikiem aktualizacji każdego z modeli P zgodnie z daną semantyką S; do każdego z tych modeli zastosuj żądanie aktualizacji U, aby uzyskać nowy zestaw modeli M; P_Ujest dowolnym programem logicznym, którego modele są dokładnie M. Podejście AGM proponuje trzy podstawowe operacje na zbiorze przekonań K: a) rozszerzenie K + Φ, które jest po prostu dodaniem nowej informacji Φ∈L_B do K. b) rewizja K * Φ,Φ która jest sensowną rewizją K w świetle Φ (w szczególności, gdy K przeczy Φ); i c) kontrakcja K - Φ, która polega na usunięciu Φ z K. Z drugiej strony, AGM proponuje zbiór postulatów, K*1 ?- K*8, które powinien spełniać dowolny operator rewizji * odwzorowujący zbiór przekonań K ⊆ L_B i zdanie Φ ∈ L_B na zrewidowany zbiór przekonań K * ?Φ Zakładamy, że K jest reprezentowane przez stan epistemiczny E, wówczas postulaty K*1 -? K*8 można przeformułować w następujący sposób:





Katsuno i Mendelzon (1991) zaproponowali zestaw postulatów, w których zmianą &Phi: na bazę przekonań B są zdania zdaniowe w języku skończonym. Niektóre z istotnych różnic między postulatami AGM a postulatami Katsuno i Mendelzona polegają na tym, że rewizja powinna dawać taki sam wynik jak rozwinięcie E + Φ, pod warunkiem, że Φ jest zgodne z E, co nie jest pożądane w przypadku aktualizacji w ogólności. Postulat 8 głosi, że jeśli E można rozłożyć na dysjunkcję stanów (np. modeli), to każdy przypadek można aktualizować oddzielnie, a wynik końcowy uzyskuje się poprzez uwzględnienie dysjunkcji stanów powstających. Darwiche i Pearl (1997) zaproponowali postulaty rewizji iteracyjnej. Ten zestaw postulatów jest bardzo prosty, a większość zaadaptowanych postulatów AGM i aktualizacji jest naruszana przez programy aktualizacyjne. Inny zestaw postulatów rewizji iteracyjnej, odpowiadający sekwencji E obserwacji, został sformułowany przez Lehmanna (1995). Należy zauważyć, że generalnie postulaty proponowane dla rewizji iteracyjnej zawodzą i, z wyjątkiem niektórych postulatów, każda zmiana jest dana przez pojedynczą regułę. Należy jednak pamiętać, że oba opisane powyżej poglądy są na poziomie technicznym tożsame. Wszystkie te podejścia do kwestii aktualizacji traktują ją jako proces rewizji przekonań. Jednakże, idąc za Gardenforsem i Makinsonem (1991; 1994), rewizję przekonań można powiązać z rozumowaniem niemonotonicznym, interpretując ją jako abstrakcyjną relację konsekwencji w zdaniach, gdzie stan epistemiczny jest ustalony. Podobnie jak Eiter, możemy interpretować programy aktualizacji jako abstrakcyjną relację konsekwencji w programach logicznych. Mimo to powinniśmy rozważyć te propozycje, ponieważ na przykład Makinson (1993) rozważał zbiór (pożądanych) właściwości dla rozumowania niemonotonicznego i analizował zachowanie niektórych formalizmów rozumowania w odniesieniu do tych właściwości. Kontynuując nasze badania, od razu skomentujemy w ogólny sposób propozycję Alferesa i innych (2000). Wprowadzili koncepcję dynamicznych programów logicznych jako uogólnienie zarówno idei aktualizacji interpretacji poprzez programy rewizyjne, jak i aktualizacji programów, zdefiniowanej przez Alferesa i Pereirę (1997) oraz Leite i Pereirę (1997). Składniowo dynamiczne programy logiczne oparte są na uogólnionych programach logicznych (GLP), które dopuszczają domyślną negację w nagłówku reguł, ale nie dopuszczają żadnej silnej negacji. Sposób, w jaki modele sekwencji aktualizacji są definiowane przez Alferesa, jest podobny do transformacji zastosowanej przez Eitera . Są one definiowane jako stabilne modele programu powstałe w wyniku przepisania składni. Nazywa się to aktualizacją dynamiczną. Elementy sekwencji są uogólnionymi programami logicznymi. Alferes i inni zdefiniowali jej semantykę za pomocą dynamicznego programowania logicznego generowanego przez sekwencję poleceń. Następnie, translacja tych poleceń (program LUPS) na uogólniony program logiczny, w którym stabilne modele dokładnie odpowiadają semantyce oryginalnego programu LUPS. W tej propozycji autorzy zakładają, że wiedza ewoluuje z jednego stanu wiedzy do drugiego. Zatem, biorąc pod uwagę bieżący stan wiedzy KS, jego następczy stan wiedzy KS[U] jest generowany w wyniku wystąpienia niepustego zbioru U jednoczesnych aktualizacji. Każdą z aktualizacji można postrzegać jako zbiór działań, a kolejne stany wiedzy uzyskuje się jako:

KS_n = KS₀[U₁][U₂] … [U_n]

gdzie U_i reprezentują kolejne zbiory aktualizacji. Ten stan jest oznaczany przez:

KS_n = U₁ ⊕ U₂ ⊕ … ⊕ U_n

Zatem w dynamicznym programowaniu logicznym modele sekwencji aktualizacji są definiowane jako stabilne modele programu powstałe w wyniku przepisania składni. W (Alferes i Pererira, 2002) wykazano, że programy rewizyjne i dynamiczne aktualizacje są równoważne, pod warunkiem, że pierwotna wiedza ma charakter ekstensjonalny, tj. początkowy program zawiera jedynie reguły w postaci A <- lub nie A<-. Jedną zasadniczą różnicę można od razu zidentyfikować między naszymi programami aktualizacji a dynamicznymi aktualizacjami: w dynamicznych aktualizacjach wartość każdego atomu jest określana od najniższego poziomu P1 w górę w kierunku Pn. Różna strategia oceny prowadzi w efekcie do różnej semantyki. Ponadto, Alferes i inni używają nieco niestandardowej koncepcji modeli stabilnych. Istnieje różnica semantyczna między aktualizacjami dynamicznymi a aktualizacjami według Eitera . Z drugiej strony, jedna z propozycji bardziej wdzięcznie odnoszących się do aktualizacji odpowiada (Eiter, Fink, Sabattini i Thompits, 2000). Autorzy w (Eiter, Fink, Sabattini i Thompits, 2000) redefiniują i wdrażają proces aktualizacji inspirowany propozycją zdefiniowaną przez Alferesa do której można się odwołać . Propozycja (Eiter, Fink, Sabattini i Thompits, 2000) zawiera wyczerpującą analizę najnowszych propozycji opartych na logice niemonotonicznej. Przedstawiono tam syntaktyczną redefinicję dynamicznych programów logicznych i zbadano ich właściwości semantyczne. W szczególności przeprowadzono badanie weryfikacji dynamicznych programów logicznych w oparciu o dobrze znane postulaty rewizji przekonań . Badano również strukturalne właściwości aktualizacji programów logicznych. Jednakże, jak to bywa we wszystkich dotychczas zaprezentowanych pracach, większość przedstawionych właściwości nie jest spełniona. Ten fakt zmotywował nasze badania do pracy nad teorią opartą na właściwościach. Jest to podejście do aktualizacji niemonotonicznych baz wiedzy reprezentowanych jako rozszerzone programy logiczne w ramach semantyki zbioru odpowiedzi. Rozważają one udoskonalenia semantyki w pojęciu minimalności zmiany. Niniejsza propozycja proponuje mechanizm aktualizacji oparty na sekwencji programów logicznych. Nieformalnie program ten wyraża warstwową wyprowadzalność literału L, zaczynając od górnej warstwy P_n i kontynuując w dół do dolnej warstwy P₁. Warstwa reguły r Pi ma zastosowanie tylko wtedy, gdy nie jest obalona przez literał wyprowadzony na wyższym poziomie, który jest zgodny z H(r). Reguły bezwładności propagują lokalnie wyprowadzoną wartość dla L w dół do pierwszego poziomu, gdzie wartość lokalna staje się globalna. Kontynuując ten kierunek, pracowaliśmy nad znalezieniem właściwości, które spełnia nasz operator aktualizacji . Naszym celem jest zbudowanie semantyki opartej na właściwościach strukturalnych. Jest to nasz główny cel w teorii aktualizacji.Autorzy przedstawiają zbiór właściwości, które spełnia operator aktualizacji. W niniejszym artykule kontynuujemy ten sam kierunek badań, prezentując nowatorską propozycję mającą na celu wzbogacenie teorii aktualizacji. Ta nowatorska propozycja przynosi dwie korzyści. Po pierwsze, zachowujemy wiele właściwości przedstawionych we wcześniejszych pracach, takich jak: Słaba nieistotność składni (Weak Irrelevance of Syntax - WIS). Ta właściwość jest podobna do jednego z postulatów zaproponowanych przez AGM, ale w tym przypadku dla logiki niemonotonicznej i w ramach programowania zbiorów odpowiedzi (ASP) wprowadzonego i zdefiniowanego przez (Gelfond i Lifschitz, 1988). Z drugiej strony, dochodzimy do wniosku, że wiele podejść do aktualizacji programów nie spełnia wielu właściwości zdefiniowanych w literaturze . Jest to częściowo wyjaśnione niemonotonicznością programów logicznych i zasadą odrzucenia przyczynowego zawartą w semantyce, która w dużym stopniu zależy od składni reguł. Ponadto uważamy, że dobra teoria aktualizacji opiera się zasadniczo na zestawie właściwości. W wyniku pierwszej analizy propozycji , wprowadziliśmy nowy operator aktualizacji. Propozycja ta spełnia kilka właściwości postulatów AGM, między innymi nową właściwość zwaną słabą nieistotnością składni. Właściwości te dają agentowi wartość dodaną w stosunku do innych propozycji, które ich nie spełniają. Należy podkreślić prostotę naszej propozycji, która pozwala agentowi reagować w poprawny i odpowiedni sposób. Kontynuując analizę aktualizacji, przedstawiamy nasze główne wyniki dotyczące aktualizacji programów logicznych: podejście oparte na właściwościach opublikowane w (Zacarias, 2005). W tej propozycji przedstawiliśmy kilka właściwości aktualizacji teorii. Rozważamy te właściwości z perspektywy rozumowania niemonotonicznego, naturalnie interpretując aktualizacje programu jako niemonotoniczne relacje konsekwencji. W tej propozycji rozważamy nasze właściwości w ramach logiki N. Dodatkowo, przedstawiliśmy kilka przykładów dotyczących aktualizacji w programowaniu zestawów odpowiedzi. Przedstawiliśmy nową propozycję dotyczącą wzbogacenia operatora aktualizacji "⊕". Tam przedstawiliśmy udoskonalenie stabilnej semantyki modelu dla operatora aktualizacji. Przedstawiliśmy również nową właściwość, która pozwala nam stawić czoła aktualizacjom, w których nowe informacje zawierają reguły definiujące konserwatywne rozszerzenie. Tak więc, podaliśmy rozszerzenie naszych właściwości udowodnionych w (Osorio & Zacarías, 2003), w logice N. To podejście opiera się na pracy wykonanej przez Eitera i innych i zainspirowane niedawnym podejściem zaprezentowanym przez Alferesa . Dzięki tej pracy ulepszamy i wzbogacamy operator aktualizacji zaproponowany przez Eitera, dając w rezultacie nowy operator aktualizacji.

PRZYSZŁE TRENDY

Podobnie jak w (Eiter, Fink, Sabattini i Thompits, 2000) zbiega się to z tym, że ze względu na pozorny brak minimalności zmiany, rozważaliśmy udoskonalenia semantyki w kategoriach minimalnych i ściśle minimalnych zbiorów odpowiedzi. Kilka kwestii pozostaje do dalszej pracy. Interesujący punkt dotyczy formułowania postulatów (zasad lub właściwości) dla operatora aktualizacji w programach logicznych i, bardziej ogólnie, w teoriach niemonotonicznych. Jak widać, kilka postulatów z obszaru zmiany teorii logicznej zawodzi w przypadku programów aktualizacji. Można to wyjaśnić dominującą rolą składni dla aktualizacji, ucieleśnionej przez przyczynowe odrzucenie reguł.

WNIOSKI

W niniejszym artykule rozważaliśmy nową propozycję zapewnienia naszym agentom procesu aktualizacji. Nasza propozycja to nowatorska i prosta metodologia, która pozwala agentowi na ciągłe aktualizowanie swojej bazy wiedzy. Dzięki temu agent zachowuje się w sposób racjonalny, podobny do zachowania człowieka. Co więcej, jest to odpowiednia propozycja dla aplikacji wymagających odpowiedzi w czasie rzeczywistym. Otwiera ona również możliwości budowania rzeczywistych aplikacji, takich jak inteligentni agenci, których komponent racjonalny jest modelowany przez bazę wiedzy, która z kolei jest utrzymywana za pomocą programów logiki aktualizacji.

WSTĘP

Systemy syntezy tekstu na mowę (US-TTS) z wyborem jednostek generują mowę syntetyczną w oparciu o wyszukiwanie wcześniej nagranych jednostek mowy z bazy danych mowy (korpusu) sterowanej ważoną funkcją kosztu . Aby uzyskać wysokiej jakości mowę syntetyczną, wagi te muszą być efektywnie optymalizowane. W tym celu, we wcześniejszych pracach, wprowadzono technikę dostrajania wag opartą na ewolucyjnych testach percepcyjnych za pomocą aktywnych interaktywnych algorytmów genetycznych (aiGA). aiGA wykorzystują modele, które odwzorowują subiektywne preferencje użytkowników za pomocą grafów częściowego uporządkowania, dopasowania syntetycznego i obliczeń ewolucyjnych (EC). Chociaż aiGA proponuje skuteczną metodę mapowania preferencji pojedynczych użytkowników, o ile nam wiadomo, metodologia wyodrębniania wspólnych rozwiązań spośród różnych indywidualnych preferencji (zwanych dalej wspólną wiedzą) nie została jeszcze opracowana. Co więcej, istnieje problem niejednoznaczności, który należy rozwiązać, gdy różni użytkownicy ewoluują do różnych konfiguracji wag. W niniejszym przeglądzie przedstawiono Generative Topographic Mapping (GTM) jako metodę wyodrębniania wspólnej wiedzy z modeli aiGA uzyskanych z preferencji użytkowników.

WSTĘP

Dostrajanie wag w syntezie mowy z wyborem jednostek. Celem US-TTS jest generowanie mowy syntetycznej poprzez łączenie sekwencji jednostek, które najlepiej spełniają wymagania wynikające z tekstu wejściowego. Jednostki mowy są pobierane z bazy danych (korpusu mowy), która przechowuje jednostki mowy nagrane wcześniej, zazwyczaj przez profesjonalnego lektora. Przepływ pracy w syntezie mowy jest zazwyczaj modelowany jako dwa niezależne bloki, które konwertują tekst pisany na sygnał mowy. Pierwszy blok nosi nazwę Przetwarzania Języka Naturalnego (NLP), po którym następuje blok Cyfrowego Przetwarzania Sygnałów (DSP). Na pierwszym etapie blok NLP przeprowadza wstępne przetwarzanie tekstu (np. konwersję cyfr lub akronimów na słowa), a następnie konwertuje grafemy na fonemy. Na ostatnim etapie blok NLP przypisuje każdemu fonemowi skwantyfikowane parametry prozodii, kontrolując sposób, w jaki każdy fonem jest konwertowany na sygnał. Zasadniczo te skwantyfikowane parametry prozodii obejmują czas trwania, wysokość dźwięku i energię. Następnie blok DSP pobiera z zarejestrowanej bazy danych (korpusu mowy) sekwencję jednostek mowy, która najlepiej odpowiada wymaganiom docelowym (fonemy i ich prozodia). Na koniec jednostki mowy są łączone w celu uzyskania wyjściowego sygnału mowy. Proces pobierania jest realizowany przez algorytm programowania dynamicznego sterowany funkcją kosztu. Funkcja kosztu oblicza obciążenie związane z wyborem jednostki w sekwencji jako sumę dwóch ważonych podkosztów (patrz równanie (1)): docelowego podkosztu (C^t) i podkosztu konkatenacji (C^c). W niniejszej pracy C^t jest rozpatrywany jako ważona kombinacja liniowa znormalizowanych odległości prozodycznych między wektorem prozodii przewidywanym przez docelowe-NLP a wektorem prozodii jednostki kandydującej (patrz równanie ). W przeciwnym razie C^c jest obliczany jako ważona kombinacja liniowa odległości między wektorami cech sygnału mowy wokół jego punktu konkatenacji (patrz równanie ).





gdzie tⁿ₁ reprezentuje sekwencję jednostek docelowych {t₁,t₂,…,t_n}, a uⁿ₁ reprezentuje sekwencję jednostek kandydackich {u₁, u₂,…, u_n}.



Prawidłowe zaprojektowanie funkcji kosztowej za pomocą treningu siłowego jest kluczowe dla uzyskania wysokiej jakości mowy syntetycznej . Niemniej jednak, problem ten skupił się na podejściach, które nie dają jednoznacznej odpowiedzi. Zaproponowano kilka technik dostrajania wagi, które można podzielić na trzy grupy: i) dostrajanie ręczne, ii) metody czysto obiektywne, oparte na obliczeniach, oraz iii) techniki optymalizowane percepcyjnie. Niniejszy przegląd opiera się na technikach opartych na ludzkiej informacji zwrotnej dotyczącej procesu szkolenia, zgodnie z wcześniejszymi pracami, które zostały omówione w następnej sekcji.

Podejście: Interaktywne ewolucyjne dostrajanie wag

Metody czysto obiektywne, oparte na obliczeniach, koncentrują się głównie na pomiarze akustycznym (uzyskanym z odległości cepstralnych) między sygnałami resyntetyzowanymi a naturalnymi. Hunt i Black przyjęli dwa podejścia . Pierwsze podejście opierało się na dostosowaniu wag poprzez wyczerpujące przeszukiwanie predyskretyzowanej przestrzeni wag (przeszukiwanie przestrzeni wag, WSS). Drugie podejście zaproponowane przez autorów wykorzystywało technikę regresji wieloliniowej (MLR) w całej bazie danych do obliczenia pożądanych wag. Później Meron i Hirose przedstawili metodologię, która poprawiła wydajność WSS i udoskonaliła metodę MLR. W poprzedniej pracy (Alías & Llorà, 2003) wprowadzili obliczenia ewolucyjne do przeprowadzenia tego dostrajania. Dokładniej,zastosowano algorytmy genetyczne (GA) w celu uzyskania najodpowiedniejszej wagi. Główną wartością dodaną wykorzystania algorytmu genetycznego do znalezienia optymalnej konfiguracji wag jest niezależność od liniowych modeli wyszukiwania (jak w algorytmie wielopoziomowym), a ponadto unikanie wyszukiwania wyczerpującego (jak w algorytmie WSS). Jednak wszystkie te metody nie są zależne od miary akustycznej w celu określenia rzeczywistej jakości syntezowanej mowy, która w dużej mierze jest względna do słuchu ludzkiego. Aby uzyskać lepszą jakość mowy, zasugerowano udział użytkownika w tym procesie. W pracy (Alías, Llorà, Iriondo, Sevillano, Formiga i Socoró, 2004) przeprowadzono testy preferencji, syntetyzując tekst treningowy według dwóch różnych wag i porównując uzyskaną subiektywną jakość mowy. Następnie, zaprezentowano Aktywne Interaktywne Algorytmy Genetyczne (Active Interactive Genetic Algorithms) jako interaktywną ewolucyjną metodę obliczeniową, w której informacje zwrotne od użytkownika ewoluują rozwiązania poprzez mechanizm przetrwania najlepiej przystosowanych. Dopasowanie rozwiązań wrodzone opiera się na częściowym porządku dostarczonym przez ewaluatora; efektywność Aktywnych Algorytmów Genetycznych (iGA) opiera się na ewoluowaniu różnych rozwiązań za pomocą dopasowania zastępczego, które uogólnia preferencje użytkownika. To dopasowanie zastępcze i proces ewolucyjny opierają się na następujących kluczowych elementach: i) częściowym uporządkowaniu, ii) indukowanym porządku całkowitym oraz iii) funkcji zastępczej za pośrednictwem maszyn wektorów nośnych ε (ε-SVM). Decyzje dotyczące preferencji podejmowane przez użytkownika są modelowane jako graf kierunkowy, który służy do generowania częściowego uporządkowania rozwiązań (np.:



Tabela 1 przedstawia podejście do globalnego rankingu oparte na mierze dominacji: dla danego wierzchołka v obliczana jest liczba wierzchołków zdominowanych δ(v) i wierzchołków dominujących.



Korzystając z tych miar, oszacowane dopasowanie można obliczyć jako



Szacowany ranking uzyskuje się poprzez sortowanie na podstawie . Procedura aiGA jest szczegółowo opisana w algorytmie 1. Jednak po uzyskaniu wag globalnych za pomocą aiGA nie było jednego dominującego rozwiązania wagowego , tj. każdy test przeprowadzony przez różnych użytkowników dawał podobne i różne rozwiązania. Fakt ten implikował, że druga grupa użytkowników musiała zweryfikować uzyskane wagi. Zatem problem klastrowania z różnych testów nadawał się do rozwiązania problemu dostrajania wag, którego celem było uzyskanie spójnych wyników z testów użytkowników.

GENERATYWNE MAPOWANIE TOPOGRAFICZNE JAKO PLUS

GTM w pigułce

Uczenie bez nadzoru pozwala grupować rzadkie dane w klastry pod względem podobieństwa próbek danych. Grupowanie to realizuje kilka metod : Maksymalizacja Oczekiwania (EM), metoda k-średnich, Gaussowskie Modele Mieszane (GMM), Mapy Samoorganizujące (SOM) i Generatywne Mapowanie Topograficzne. Techniki można podzielić, zgodnie z (Figuereido i Jain, 2002), na dwa typy formulacji: i) metody oparte na modelach (np. GMM, EM, GTM) oraz ii) metody heurystyczne (np. metoda k-średnich lub hierarchiczne metody aglomeracyjne). Liczba źródeł generujących dane jest różniczkowalna. Rzeczywiście, metody oparte na modelach zakładają, że obserwacje zostały ukształtowane przez jedno (arbitralnie wybrane i niezidentyfikowane) źródło spośród zestawu alternatywnych, dowolnych źródeł. Zatem wnioskowanie o tych dostrojonych źródłach i mapowanie źródła na każdą obserwację prowadzi do klasteryzacji zbioru obserwacji. W przeciwnym razie metody heurystyczne zakładają tylko jedno źródło danych obserwowanych, biorąc pod uwagę podobną heterogeniczność tych danych. Mapy samoorganizujące się (lub mapy Kohonena) to technika klasteryzacji oparta na sieciach neuronowych. Łatwość wizualizacji danych wielowymiarowych jest w dużej mierze odpowiednią wartością dodaną SOM. Ponadto, Generative Topographic Mapping to nieliniowy model zmiennych ukrytych wprowadzony w (Bishop, Svensen i Williams, 1998). Model GTM ma na celu udzielenie alternatywnej odpowiedzi na model SOM poprzez pokonanie jego ograniczeń wymienionych w pracy: i) brak funkcji kosztu, ii) brak podstaw teoretycznych do wyboru rozkładów parametrów szybkości uczenia się i parametrów sąsiedztwa w celu zapewnienia uporządkowania topograficznego, iii) brak jakichkolwiek ogólnych dowodów zbieżności oraz iv) fakt, że model nie definiuje gęstości prawdopodobieństwa. Model GTM opiera się na ograniczonej mieszaninie modeli GMM, których parametry można dostrajać za pomocą algorytmu EM. Wadą modeli heurystycznych jest brak a priori rozkładu centroidów dla każdego klastra. W modelu GTM zbiór punktów ukrytych jest modelowany jako siatka. Kołowy rozkład Gaussa to punkt w siatce z jego odpowiednikiem, poprzez ważone nieliniowe funkcje bazowe, w przestrzeni wielowymiarowej. Zatem siatka jest kształtowana tak, aby otaczać dane ze względu na jawny porządek rozkładów Gaussa.

Modelowanie preferencji użytkownika za pomocą GTM

GTM jest w stanie wyodrębnić rozwiązania z różnych ewoluowanych grafów aiGA dzięki spójności swoich podstaw teoretycznych. Kluczowym celem jest rozpoznanie ważnych klastrów w ewoluowanej przestrzeni danych, a tym samym określenie entropii dopasowania każdego klastra w kategoriach wariancji dopasowania, aby wybrać globalny zestaw konfiguracji wag. GTM może modelować najlepsze wagi aIGA z wielowymiarowej przestrzeni wag do przestrzeni dwuwymiarowej. Uwzględnienie klastra o wyższej uśrednionej sprawności i niższym odchyleniu standardowym pozwala na wybór najlepszej konfiguracji wag z różnych modeli użytkownika aiGA. Aby dostosować tę metodę, geometria rozkładów Gaussa i rozmiar przestrzeni ukrytej muszą zostać skonfigurowane ręcznie. EM waży centroidy GTM i funkcje bazowe. Następnie z każdego klastra wyodrębniana jest średnia sprawność oraz jego odchylenie standardowe. Obliczenie uśrednionej sprawności i odchylenia standardowego jest obliczane na podstawie zestawu, którego kombinacje wag bayesowskich a posteriori prawdopodobieństwa są najwyższe dla klastra. Należy zauważyć, że samo dopasowanie nie jest uwzględniane w optymalizacji EM, ponieważ jest względne dla każdego użytkownika i nie jest znane dla nieocenionych kombinacji wag dla jednego konkretnego użytkownika (chyba że ε-SVM to przewidział).

Eksperymenty i wyniki

W (Formiga i Alías, 2007) wiedza wspólna została wyodrębniona z wag ewolucyjnych użytkowników z poprzednich testów przeprowadzonych na korpusie mowy katalońskiej z 9863 zarejestrowanymi jednostkami (1207 difonów i trifonów) (uzyskanymi z 1520 zdań i słów) . W tym teście z korpusu wyodrębniono pięć zdań zbalansowanych fonetycznie w celu przeprowadzenia globalnego procesu dostrajania wag za pomocą interfejsu internetowego o nazwie SinEvo . Wyewoluowane wagi zostały znormalizowane poprzez normalizację Max-Min, aby wszystkie wagi mieściły się w zakresie od 0 do 1. Test ten został przeprowadzony przez trzech użytkowników, uzyskując piętnaście różnych konfiguracji wag. W pracy (Formiga i Alías, 2007) przeanalizowano różne konfiguracje GTM pod kątem mapowania znormalizowanych wag (siatka heksagonalna lub prostokątna i różne rozmiary siatki: (3 × 3, 4 × 4, 5 × 5)). Celem tej analizy było znalezienie optymalnej konfiguracji GTM, tj. takiej, która minimalizuje uśrednione odchylenie standardowe (std) na klaster i liczbę istotnych klastrów na populację (ze średnią sprawnością powyżej 75%), jednocześnie maksymalizując uśrednioną średnią sprawność na klaster. Jak można zauważyć na rysunku 2, wybrano konfigurację siatki 4 × 4 z heksagonalną siatką utajoną, ponieważ dawała najlepszy front Pareto (chociaż pozostałe siatki 4x4 osiągnęły podobną wydajność). Po skonfigurowaniu GTM, każda ewoluowana waga została wyodrębniona i zmapowana na GTM innych użytkowników w tym samym zdaniu, uzyskując odpowiednią sprawność na podstawie preferencji innych użytkowników. Równanie 6 umożliwiło (ustawienie globalnej sprawności (gF) na podstawie uśrednionej ogólnej sprawności F^GTM_Av) dla każdej ewoluowanej konfiguracji wagi.



gdzie U oznacza liczbę użytkowników, W oznacza liczbę konfiguracji wag, a N oznacza całkowitą liczbę wag (U + W). Ponadto, aby uniknąć percepcyjnego etapu ręcznej walidacji, dziesięciu różnych użytkowników - w żaden sposób niezaangażowanych w proces dostrajania - przeprowadziło porównanie z najlepszymi wagami aIGA, aby umożliwić porównanie klastrowania GTM z rzeczywistymi preferencjami użytkownika na etapie walidacji. Analizując wyniki na rysunku 3, konfiguracje wag najczęściej głosowane przez GTM pasują do ręcznych preferencji użytkownika dla trzech zdań (De la Seva Selva, Del Seu Territori i Grans Extensions).



Pozostałe zdania zachowują się jednak zupełnie inaczej. Najlepszą kombinacją wag wybraną spośród użytkowników była druga najlepsza konfiguracja wag GTM w I els han venut, podczas gdy najlepsza kombinacja wag GTM nigdy nie została wybrana. Korelacja cosinusowa jest brana pod uwagę w przypadku problematycznych konfiguracji wag, ponieważ ważniejsza jest dystrybucja wag, a nie analiza samych wartości. W tym przypadku korelacja między dwiema lepszymi wagami GTM a dwiema lepszymi wagami wynosi 0,7841, więc wyniki GTM można uznać za zadowalające, ponieważ wagi zbliżają się do równoważnych wzorców. Z drugiej strony, korelacja między dwiema najlepszymi konfiguracjami wag GTM wynosi 0,8323 w Fusta de Birm?nia i, podobnie jak w poprzednim przypadku, korelacja ta ponownie daje zadowalające wyniki.

TRENDY NA PRZYSZŁOŚĆ

Przyszłe prace będą koncentrować się na przeprowadzaniu nowych eksperymentów, np. poprzez klastrowanie podobnych jednostek zamiast zajmowania się globalnym dostrajaniem wag na podstawie wstępnie wybranych zdań lub poprzez włączenie większej liczby użytkowników do procesu uczenia. Ponadto rozszerzenie możliwości GTM o mapowanie preferencji użytkowników otwiera możliwość skupienia się na nieliniowych funkcjach kosztów, aby pokonać ograniczenia liniowości obecnej funkcji.

WNIOSKI

Niniejszy artykuł kontynuuje prace nad uwzględnieniem preferencji użytkowników w celu dostrajania wag funkcji kosztów w systemach TTS z wyborem jednostek. W poprzednich pracach przedstawiliśmy metodę znajdowania optymalnego dostrajania wag funkcji kosztów w oparciu o kryteria percepcyjne poszczególnych użytkowników. W kolejnym kroku niniejszy artykuł stosuje heurystyczną metodę wyboru najlepszego rozwiązania spośród wszystkich użytkowników, eliminując konieczność przeprowadzenia drugiego testu odsłuchowego w celu wybrania najlepszej konfiguracji wag spośród indywidualnych optymalnych rozwiązań. To badanie dowodzące słuszności koncepcji pokazuje, że GTM jest w stanie odwzorować wspólną wiedzę różnych użytkowników dzięki pracy nad przestrzenią wag zoptymalizowaną percepcyjnie, uzyskaną za pomocą AIGA, i uzyskać ostateczne rozwiązanie, które można wykorzystać do ostatecznej regulacji TTS.

WSTĘP
Model języka to opis języka. Chociaż gramatyka od dawna stanowi dominujące narzędzie modelowania języka, ostatnio zainteresowanie przesunęło się w stronę modelowania statystycznego. Niniejszy rozdział odnosi się do eksperymentów z rozpoznawaniem mowy, chociaż statystyczne modele języka znajdują zastosowanie w szerokim zakresie zastosowań: tłumaczeniu maszynowym, wyszukiwaniu informacji itp.Modelowanie statystyczne ma na celu oszacowanie częstości występowania sekwencji słów. Jeśli sekwencja słów to s = w₁w₂….w_k, prawdopodobieństwo można wyrazić jako:



Uzasadnione jest uproszczenie tego obliczenia poprzez aproksymację generowania sekwencji słów jako procesu Markowa rzędu (n-1) (Jelinek, 1998). Modele bigramów (n=2) i trigramów (n=3) to powszechne wybory. Chociaż ograniczyliśmy kontekst, takie modele mają ogromną liczbę prawdopodobieństw, które należy oszacować. Tekst dostępny do budowy modelu nazywa się "korpusem szkoleniowym" i zazwyczaj zawiera wiele milionów słów. Niestety, nawet w bardzo dużym korpusie szkoleniowym wiele z możliwych n-gramów nigdy nie jest spotykanych. Problem ten rozwiązują techniki wygładzania . Która jednostka modelowania jest najlepsza? Słowa są powszechnym wyborem, ale można również użyć jednostek mniejszych (lub większych) niż słowa. N-gram oparty na słowach najlepiej nadaje się do modelowania języka angielskiego . Języki fleksyjne mają kilka cech, które osłabiają moc predykcyjną modeli standardowych. Ogólnie rzecz biorąc, wszystkie języki indoeuropejskie są fleksyjne, ale poważny problem pojawia się w przypadku języków, które są fleksyjne w większym stopniu (np. rosyjski, czeski, słoweński). Języki aglutynacyjne (np. węgierski, fiński, estoński) mają jeszcze bardziej złożoną gramatykę fleksyjną, w której, oprócz fleksji, dużym problemem są wyrazy złożone. Języki fleksyjne dodają do wyrazów morfemy fleksyjne. Morfemy fleksyjne wskazują na informacje gramatyczne słowa (na przykład przypadek, liczbę, osobę itp.). Morfemy fleksyjne są powszechnie dodawane poprzez afiksowanie, co obejmuje prefiksowanie (dodawanie morfemu przed podstawą), sufiksowanie (dodawanie go po podstawie) i znacznie rzadsze infiksowanie (dodawanie go wewnątrz podstawy). Wysoki stopień afiksowania przyczynia się do gwałtownego wzrostu liczby różnych form wyrazowych, utrudniając, a nawet uniemożliwiając, rzetelne oszacowanie prawdopodobieństw modelu językowego. Bogata morfologia prowadzi do wysokiego wskaźnika OOV (poza słownikiem), a zatem głównym problemem jest rzadkość danych. Niniejsza sekcja koncentruje się na modelowaniu wyboru jednostek dla języków fleksyjnych w celu zmniejszenia rzadkości danych. W tym celu przeanalizowano podejścia lingwistyczne i oparte na danych.

TŁO

Modele językowe oparte na klasach

Niektóre słowa są podobne pod względem funkcji morfologicznych, składniowych lub semantycznych. W modelach językowych opartych na klasach podobne słowa grupuje się w klasy w celu zwiększenia odporności estymacji parametrów:



C oznacza deterministyczne mapowanie słów na klasy. Mapowanie niedeterministyczne można również wyprowadzić, gdy jedno słowo może należeć do wielu klas. Model można również zastosować, gdy słowo jest bezpośrednio uwarunkowane klasami poprzednich słów. Ideą modeli opartych na klasach jest redukcja zbiorów parametrów. W modelu opartym na klasach jest znacznie mniej wolnych parametrów do oszacowania niż w modelu opartym na słowach. Słowa w tej samej klasie są podobne w pewien sposób. To podobieństwo można zdefiniować na podstawie pewnej wiedzy zewnętrznej lub kryterium statystycznego. Najbardziej znanym przykładem klasteryzacji z wykorzystaniem wiedzy lingwistycznej jest klasteryzacja według części mowy (POS). W tradycyjnej gramatyce angielskiej zdefiniowano osiem POS: rzeczownik, czasownik, przymiotnik, przysłówek, zaimek, przyimek, spójnik i wykrzyknik. Ten zestaw klas jest jednak zbyt mały do modelowania języków fleksyjnych. Bardziej odpowiednie są klasy, które odzwierciedlają dodatkowe cechy gramatyczne (rodzaj, przypadek, liczbę, czas itp.). Klasy językowe zostały zbadane dla kilku języków, które są mniej lub bardziej fleksyjne. Model językowy dla języka francuskiego łączył klasy POS ze składnikiem opartym na lemmatach . W modelu językowym dla języka czeskiego słowa zostały pogrupowane w 410 klas morfo-syntaktycznych . 1300 klas zostało wykorzystanych w innym eksperymencie dla języka czeskiego . Modele oparte na klasach z klasami lingwistycznymi okazały się skuteczne również dla języka hiszpańskiego . Klasy sterowane danymi są automatycznie wyprowadzane za pomocą środków statystycznych. IBM był pionierem tego podejścia . W ich podejściu słowa są grupowane za pomocą algorytmu zachłannego, który stara się zminimalizować utratę informacji wzajemnej między klasami zachodzącą podczas scalania. Liczba klas musi być zdefiniowana z góry. Algorytm kontynuuje łączenie par klas, aż do uzyskania pożądanej liczby klas. Inne podejście zachłanne wykorzystuje algorytm wymiany . Każde słowo jest przenoszone z klasy do innej, jeśli maksymalizuje wzajemną informację między klasami. Modele językowe oparte na klasach, oparte na danych, zostały zbudowane dla wielu języków fleksyjnych. W przypadku języka francuskiego wykazują one lepszą wydajność zarówno w małych, jak i dużych korpusach . Wyniki zostały ulepszone dzięki zastosowaniu hierarchicznego modelu języka z sekwencjami klas o zmiennej długości, opartego na 233 klasach gramatycznych. W eksperymentach z językiem rosyjskim najlepsze wyniki uzyskano przy użyciu 500 klas. Wyniki uległy dalszej poprawie, gdy model oparty na klasach został połączony z modelem opartym na słowach. Aby automatycznie wyprowadzić klasy z danych, zamiast korzystać z zewnętrznych źródeł wiedzy, konieczne jest posiadanie dużej ilości danych.

Modele językowe oparte na jednostkach podwyrazowych

Biorąc pod uwagę trudności w modelowaniu języka w oparciu o pełne formy wyrazowe, pożądane byłoby znalezienie metody rozkładu form wyrazowych na ich komponenty morfologiczne i zbudowanie bardziej solidnego modelu językowego opartego na prawdopodobieństwach dotyczących poszczególnych komponentów morfologicznych. Dla niektórych języków istnieją leksykony zawierające informacje o komponentach morfologicznych słów. W eksperymentach z językiem czeskim, słowa rozkładano na tematy i końcówki za pomocą czeskiego analizatora morfologicznego, a następnie wykorzystywano je jako jednostki modelowania . Modele językowe oparte na morfemach badano również dla języka koreańskiego, w którym fraza wyrazowa jest aglomeratem morfemów . Jednostki podwyrazowe są również wykorzystywane w modelowaniu języków aglutynacyjnych, gdzie oprócz fleksji, bardzo często występują wyrazy złożone . Morfologiczne jednostki podwyrazowe zostały również udowodnione dla języka tureckiego . Ograniczenia modelu językowego zostały przedstawione za pomocą ważonej maszyny stanów skończonych. Wiele języków nie posiada rozwiniętych analizatorów morfologicznych. W takich przypadkach stosuje się badanie morfologii języka w oparciu o dane. Podejścia oparte na danych często przewyższają podejścia lingwistyczne. Sufiksy morfemiczne odkryto za pomocą analizy minimalnej długości opisu (MDL). Analiza MDL została wykorzystana do segmentacji morfologicznej dla różnych języków europejskich . Odkryto również algorytm uczenia morfologii z wykorzystaniem ukrytej analizy semantycznej . Algorytm ten wyodrębnia afiksy tylko wtedy, gdy rdzeń i afiks-rdzeń są wystarczająco podobne semantycznie. Model językowy dla języka rosyjskiego ulega również poprawie dzięki wykorzystaniu jednostek podwyrazowych opartych na danych. Zaprezentowano niezależne od języka algorytmy do odkrywania fragmentów słów w oparciu o MDL dla języka fińskiego. Autorzy donoszą, że fragmenty słów uzyskane za pomocą reguł gramatycznych dały gorsze wyniki niż fragmenty uzyskane za pomocą algorytmów opartych na danych. Poprawili oni wyniki rozpoznawania mowy poprzez klasteryzację historii n-gramów morficznych . Podobne porównania z podobnymi wnioskami przeprowadzono również dla języków tureckiego i estońskiego.

MODEL JĘZYKOWY JĘZYKA FLEKTYWNEGO

Nasza praca poświęcona jest głównie wysoce fleksyjnemu językowi słoweńskiemu. Jest to język południowosłowiański. W różnym stopniu dzieli on swoje cechy z wieloma innymi językami fleksyjnymi, zwłaszcza słowiańskimi. Podobnie jak w przypadku innych języków fleksyjnych, koncentrujemy się na zmniejszeniu postrzeganej rzadkości danych. Badane przez nas techniki są niezależne od języka i jako takie mają zastosowanie również do innych języków wysoce fleksyjnych.

Modele językowe języka słoweńskiego oparte na klasach

W naszym pierwszym badaniu zbadaliśmy zastosowanie klas opartych na danych. W pracy opisaliśmy ulepszony algorytm klasteryzacji słów. Głównym założeniem było zastąpienie systematycznej zamiany słów między klasami zamianą losową. Po drugie, zamiast zastępować jedno słowo po drugim, losowo wybrana grupa słów była zastępowana jednocześnie. Pseudokod algorytmu wygląda następująco:

1. Utwórz mapowanie początkowe
2. Oblicz początkową perpleksję zbioru treningowego PP
3. Dopóki (kryterium nie jest spełnione) do begin
4. Losowo wybierz zbiór słów
5. Dla każdego wybranego słowa losowo wybierz klasę docelową
6. Oblicz nową perpleksję zbioru treningowego PP1
7. Jeśli (PP1 < PP) zachowaj słowa w nowych klasach i PP:=PP1 w przeciwnym razie zachowaj słowa w starych klasach
8. Przejdź do kroku 3
end

Głównym wąskim gardłem algorytmu klasteryzacji jest złożoność czasowa. Opracowaliśmy zrównolegloną wersję algorytmu, aby go przyspieszyć. Stosując dobór losowy, osiągnęliśmy 3,7% poprawę w zakresie perpleksywności, porównując wyniki z podstawowym algorytmem klasteryzacji, który systematycznie zastępuje słowa. Mając V słów w słowniku i grupując je w C klas, złożoność przestrzenna modelu języka bigram opartego na klasach wynosi O(C² + V), w przeciwieństwie do złożoności przestrzennej O(V²) modelu języka opartego na słowach. Używając klas, możemy rozszerzyć słownik słów, utrzymując mały rozmiar modelu języka, ale nie rozwiązuje to problemu słów OOV. Z drugiej strony, większość systemów rozpoznawania mowy korzysta wyłącznie z modeli opartych na słowach. W takich przypadkach modele oparte na klasach muszą zostać przekształcone w modele oparte na słowach, co znacznie zwiększa ich rozmiar.

Modele języka słoweńskiego

Język oparty na jednostkach podsłownych sterowanych danymi

Słowa słoweńskie często mają wiele wspólnych jednostek morfologicznych. Analizując bardzo uproszczony model słowa, można określić dwie jego części składowe: rdzeń, który można uznać za odpowiedzialny za podstawowe znaczenie słowa, oraz końcówkę, która określa cechy gramatyczne. Nie wszystkie słowa można rozłożyć na rdzeń i końcówkę. W tym przypadku stosuje się końcówkę pustą. Pokazaliśmy, że sensowne jest oddzielne modelowanie cech semantycznych i gramatycznych słów:



w_i rozkłada się na rdzeń si i końcówkę e_i. h oznacza wcześniej zaobserwowane jednostki w przewidywaniu tematu i końcówki. Przewidywanie tematu zostało poddane adaptacji tematycznej. Zakładano, że język w środowisku docelowym (w którym miała zostać użyta ostateczna aplikacja) jest jednorodny tematycznie. Ogólny model językowy dostosowano do konkretnego tematu, wykorzystując dane na trzech poziomach semantycznych. Pierwszy poziom odpowiada językowi ogólnemu, charakteryzującemu cały korpus. Drugi poziom odpowiada językowi charakteryzującemu podzbiór podobnych dokumentów. Trzeci poziom reprezentuje drobniejszy poziom podobieństwa językowego tematycznego. Biorąc pod uwagę długość historii w przewidywaniach, zbadaliśmy następujący model trygramu:



Przewidywanie tematu opiera się na znajomości dwóch poprzednich tematów. Przewidywanie końcówki opiera się na znajomości dwóch poprzednich końcówek i bieżącego tematu. W naszych eksperymentach najlepsze wyniki uzyskano dla λ = 0,1, ponieważ do danego tematu można dołączyć stosunkowo mały zestaw końcówek. Niektóre informacje o końcówkach wyrazów są również zawarte w końcówkach sąsiednich słów. Model zakłada rozłożony korpus szkoleniowy. W (Sepesy Maučec, Rotovnik i Zemljak Jontes, 2003) zastosowaliśmy prosty schemat dekompozycji, oparty na wstępnie wybranym zestawie końcówek i zasadzie najdłuższego dopasowania. Zestaw końcówek został automatycznie wygenerowany w trzech krokach. Najpierw utworzono listę wszystkich słów zapisanych w odwróconej kolejności znaków. Słowa ułożono w kolejności alfabetycznej; w ten sposób słowa mające wspólną końcówkę pojawiają się razem na liście. Początkowe znaki sąsiednich słów na liście są porównywane w celu znalezienia dopasowania. Aby uniknąć nadmiernego tworzenia tematów, zastosowano dwa ograniczenia: pozostały temat powinien mieć z góry określoną minimalną długość, a pierwszym znakiem dopasowania musi być samogłoska. Słowa powinny być rozkładane na pary spółgłoska-samogłoska, ponieważ spółgłoski niosą ze sobą więcej informacji o znaczeniu słowa niż samogłoski. Udoskonaliliśmy dekompozycję słów w sposób iteracyjny. Szukaliśmy dekompozycji, która daje zmaksymalizowane logarytmiczne prawdopodobieństwo korpusu szkoleniowego, obliczone na podstawie trigramów podwyrazowych. Pseudokod algorytmu jest następujący:

1. Zbierz liczbę bigramów słów w zbiorze treningowym
2. Ustaw rozkład początkowy
3. Oblicz początkową logarytmiczną wiarygodność zbioru treningowego LL
4. Dopóki (kryterium zatrzymania nie jest spełnione) rozpocznij
5. Losowo wybierz zbiór słów
6. Dla każdego wybranego słowa losowo ustaw nową granicę zakończenia tematu
7. Oblicz nową logarytmiczną wiarygodność zbioru treningowego LL1
8. Jeśli (LL1 > LL) zaakceptuj nowe rozkłady i LL:=LL1, w przeciwnym razie zachowaj stare rozkłady
9. Przejdź do kroku 4
end

Wybór rozkładu początkowego jest bardzo ważny, ponieważ rozkłady końcowe gwarantują jedynie lokalną optymalizację. Rozkład początkowy został ustawiony na rozkład zaproponowany w (Sepesy Maučec i in., 2003). Kryterium zatrzymania stanowiła predefiniowana liczba iteracji. Eksperymenty przeprowadzono z wykorzystaniem korpusu gazet o nazwie "Večer". Rozmiar korpusu wyniósł 85 mln słów (734 tys. odrębnych słów). Z korpusu zebrano 14 mln bigramów. Po inicjalizacji uzyskano 267 tys. odrębnych podsłów (264 tys. tematów i 3 tys. końcówek), a początkowa perpleksja podsłów wyniosła 361. Po 10 000 iteracji liczba odrębnych podjednostek wzrosła do 497 tys. (417 tys. tematów i 80 tys. końcówek), ale perpleksja podsłów spadła do 291. Dekompozycje oparte na danych uzyskane za pomocą tego algorytmu zostały już przetestowane w eksperymentach z rozpoznawaniem mowy . Współczynnik błędów zmniejszył się o 6,3% w porównaniu z wynikami rozpoznawania mowy z wykorzystaniem modeli opartych na słowach.

PRZYSZŁE TRENDY

Włożono wiele pracy w modelowanie języków wysoce fleksyjnych, ale nadal brakuje wiedzy na temat tego, jak modelować je "najskuteczniej". Jako rozszerzenie konwencjonalnego modelu języka opartego na n-gramach, zaproponowano i przetestowano model języka iloczynowego na języku arabskim (Bilmes i Kirchhoff, 2003). Ta iloczynowa forma mogłaby być również przydatna w przypadku innych języków wysoce fleksyjnych, ponieważ łączy informacje różnego typu w jednym ogólnym modelu. Z naszej wiedzy wynika, że iloczynowe modele języka nie były dotychczas szeroko badane w przypadku innych języków wysoce fleksyjnych, z wyjątkiem języka arabskiego, a ostatnio także estońskiego .

WNIOSKI

Niniejsza sekcja zawiera przegląd metod stosowanych w modelowaniu języków wysoce fleksyjnych. Biorąc pod uwagę cechy języków wysoce fleksyjnych, wyróżniliśmy dwa typy modeli: oparte na klasach i oparte na podwyrazach. Motywacją obu z nich jest redukcja rzadkości danych. Główną ideą modeli opartych na klasach jest redukcja liczby wolnych parametrów poprzez grupowanie słów w klasy. Co ciekawe, klasy oparte na danych przewyższyły klasy lingwistyczne w wielu eksperymentach badawczych. Modele oparte na podsłowach redukują rozmiar słownictwa poprzez dzielenie słów na mniejsze jednostki i przechowywanie tych podsłow (zamiast słów) w słowniku. Metody oparte na danych, służące do dzielenia słów na podsłowa, przewyższyły dekompozycje gramatyczne w wielu językach. Zgłoszone eksperymenty dotyczące wykorzystania tego typu modeli (zwłaszcza w połączeniu ze standardowymi modelami opartymi na słowach) pokazują ogólną redukcję błędów w docelowych zastosowaniach. Wyciągamy te same wnioski z naszych eksperymentów dotyczących języka słoweńskiego. Obiecujący kierunek dalszych prac widać w modelu języka czynnikowego.

WSTĘP

Prognozowanie godzinowych danych dotyczących promieniowania słonecznego ma istotne konsekwencje w wielu zastosowaniach solarnych . Takie dane można traktować jako szereg czasowy, a ich prognozowanie zależy od dokładnego modelowania procesu stochastycznego. Obliczenie warunkowej wartości oczekiwanej, która jest na ogół nieliniowa, wymaga znajomości rozkładu wyższego rzędu próbek. Przy użyciu skończonych danych takie rozkłady można jedynie oszacować lub dopasować do predefiniowanego modelu stochastycznego. Metody takie jak predykcja autoregresyjna (AR), analiza Fouriera, łańcuchy Markowa oraz model ARMA do projektowania nieliniowych predyktorów sygnałów są przykładami tego podejścia. Podejście oparte na sieciach neuronowych (NN) również zapewnia dobre rozwiązanie problemu poprzez wykorzystanie ich wrodzonej adaptacyjnej natury . Ponieważ sieci neuronowe można trenować w celu przewidywania wyników na podstawie przykładów, są one w stanie radzić sobie z problemami nieliniowymi. Po zakończeniu treningu predyktor można ustawić na stałą wartość w celu dalszej predykcji z dużą prędkością. Wielu badaczy pracowało nad prognozowaniem danych dotyczących globalnego promieniowania słonecznego . W tych pracach dane są traktowane w surowej postaci jako jednowymiarowe szeregi czasowe, dlatego zależności międzydniowe nie są wykorzystywane. Niniejszy artykuł przedstawia nowe i proste podejście do godzinowego prognozowania promieniowania słonecznego. Najpierw dane są renderowane w macierzy, tworząc dwuwymiarowy model przypominający obraz. Jako pierwszą próbę przetestowania efektywności modelu dwuwymiarowego skonstruowano optymalne liniowe filtry predykcji obrazu. Aby uwzględnić adaptacyjny charakter złożonych i niestacjonarnych szeregów czasowych, do problemu prognozowania zastosowano również sieci neuronowe (NN), a wyniki omówiono.

TŁO

Niniejszy artykuł przedstawia dwuwymiarowe podejście modelowe do prognozowania godzinowego promieniowania słonecznego. Przed przejściem do omówienia wyników prognozy przedstawiono następujące informacje techniczne. Przy użyciu opisanych narzędzi podejście zostało przetestowane przy użyciu optymalnych filtrów liniowych i sztucznych sieci neuronowych (Hocaoglu, Gerek i Kurban, 2007).

Dwuwymiarowa reprezentacja danych promieniowania słonecznego

Zebrane godzinowe dane dotyczące promieniowania słonecznego są jednowymiarowym sygnałem dyskretnym w czasie. W niniejszej pracy przedstawiamy te dane w postaci dwuwymiarowej macierzy, jak podano w równaniu 1.



gdzie wiersze i kolumny godzinowej macierzy promieniowania słonecznego wskazują odpowiednio dni i godziny. Taka dwuwymiarowa reprezentacja zapewnia istotny wgląd w rozkład promieniowania w czasie. Najpierw uzyskuje się wykres powierzchniowy danych, a następnie obraz danych, który przedstawiono na rysunku 1.



Analizując dane w postaci obrazu na rysunku 1, łatwo zinterpretować dzienne i sezonowe zachowanie promieniowania słonecznego. Ciemne obszary obrazu wskazują na brak światła słonecznego na powierzchni poziomej. Przejście z czerni do bieli wskazuje na wzrost lub spadek padania promieniowania słonecznego na powierzchnię poziomą. Zimą okres od świtu do zmierzchu jest krótszy, co powoduje powstanie węższej, wystającej plamy. Natomiast biała plama jest szersza latem, co wskazuje na dłuższy dzień. Szerokość białej plamy wyraźnie wskazuje na sezonowe zmiany okresów nasłonecznienia. Korelacje poziome i pionowe w danych 2D są dość wyraźne. Oznacza to, że biorąc pod uwagę korelację pionową między tymi samymi godzinami kolejnych dni, korzystne jest wykorzystanie prognozy 2D do prognozowania godzinowego. Efektywność prognozy proponowanego modelu jest zilustrowana za pomocą optymalnych liniowych filtrów predykcyjnych 2D i sieci neuronowych.

Optymalny projekt 2-D liniowego filtra predykcyjnego

Z literatury poświęconej kodowaniu obrazów predykcyjnych wiadomo, że macierz 2-D można efektywnie modelować za pomocą liniowych filtrów predykcyjnych . Dziedzina predykcji to parametr swobodny określany w zależności od zastosowania. Rozważmy strukturę filtra predykcyjnego o trzech współczynnikach, jak podano w wyrażeniu 2:



Współczynniki filtra liniowego a₁, a₂ i a₃ są zoptymalizowane, a wynik predykcji jest szacowany jako



Błąd prognozy dla tego członu wynosi:



Całkowitą energię błędu odpowiadającą prognozie całego obrazu można obliczyć jako:



gdzie m i n odpowiadają szerokości i wysokości obrazu, które dla danych słonecznych wynoszą odpowiednio 365 i 24. Współczynniki filtru minimalizujące tę funkcję można znaleźć z rozwiązania równania pochodnej minimalizacji:



Rozwiązanie równania 6 daje następujące równanie macierzowo-wektorowe:



co można zapisać zwięźle jako R . a = r, więc optymalne współczynniki filtru można uzyskać jako

a = R^0-1 r (8)

Krótkie omówienie technik uczenia się sieci neuronowych

Istnieje kilka technik umożliwiających osiągnięcie szybkich algorytmów sieci neuronowych. Wśród nich techniki heurystyczne opracowano na podstawie analizy wydajności standardowego algorytmu najszybszego spadku . W kategorii szybkich algorytmów metody te wykorzystują standardowe techniki optymalizacji numerycznej, takie jak gradient sprzężony, quasi-Newton i Levenberg-Marquard. Podstawowy algorytm propagacji wstecznej dostosowuje wagi w kierunku najszybszego spadku. Okazuje się, że chociaż funkcja maleje najszybciej wzdłuż ujemnej wartości gradientu, niekoniecznie prowadzi to do najszybszej zbieżności. W algorytmach gradientu sprzężonego przeszukiwanie odbywa się wzdłuż kierunków sprzężonych, co generalnie prowadzi do szybszej zbieżności niż w kierunkach najszybszego spadku. Metoda Newtona stanowi alternatywę dla metod gradientu sprzężonego, które często zbiegają szybciej. Wadą tej metody jest jej złożoność i kosztowność, ponieważ w sieciach neuronowych z sprzężeniem do przodu obliczana jest macierz hesjańska. Prostsze obliczeniowo metody quasi-Newtona nie wymagają obliczania drugich pochodnych. Podobnie, algorytm Levenberga-Marquardta został również zaprojektowany tak, aby osiągnąć prędkość uczenia drugiego rzędu bez konieczności obliczania macierzy hesjańskiej. Istnieje wiele badań na różne tematy, które wskazują na porównanie algorytmów treningowych . Ponieważ algorytm Levenberga-Marquardta zapewnia szybszą konwergencję, został on przyjęty i wykorzystany w niniejszym artykule.

WYNIKI PROGNOZOWANIA DANYCH DOTYCZĄCYCH PROMIENIOWANIA SŁONECZNEGO

Aby zmniejszyć złożoność obliczeniową i skupić się na propozycji, w niniejszej pracy zastosowano stosunkowo krótkie filtry predykcyjne 1-D i 2-D. Szablony filtrów podano na rysunku 2.



Szablony te są również szeroko stosowane w predykcyjnym kodowaniu obrazów i sygnałów. W przypadku minimalnej liniowej predykcji RMSE optymalne współczynniki są wyznaczane analitycznie poprzez rozwiązanie równania 8. Dane obrazu 2-D są wprowadzane do systemu predykcyjnego, a dla każdej godziny uzyskiwane są wartości błędów. Wartość błędu dla optymalnego filtra 2-D z 3 odgałęzieniami podano na rysunku 3.



Jako drugi model predykcji krokowej do danych zastosowano dwie struktury NN. W pierwszej strukturze dane wejściowe są traktowane jako 1-D, a elementami sieci wejściowej są i-ty, i+1. i i+2. element danych, gdzie wyjściem jest i+3. element dla każdej próbki w danych. W drugiej strukturze zastosowano proponowaną formę macierzy obrazu 2-D. Dane wejściowe sieci to i,j-ty, i+1,j-ty oraz i,j+1-szy element dwuwymiarowej macierzy danych, a dane wyjściowe to i+1, j+1-szy element macierzy danych dla każdego i oraz j. Do testowania wykorzystano okres 2 miesięcy. Funkcja sigmoidalna i algorytm gradientu prostego z modyfikacją Levenberga-Marquarda są wykorzystywane w procesie uczenia z trzema neuronami w warstwie ukrytej. Aby przyspieszyć proces uczenia, używany jest człon momentum, który jest aktualizowany o ułamek poprzedniej aktualizacji wagi do bieżącego. Po fazie uczenia sieć jest symulowana przy użyciu pozostałych danych obrazowych i uzyskiwane są próbki błędów



Wartości średniego błędu kwadratowego (RMSE) uzyskane z proponowanych optymalnych liniowych filtrów predykcyjnych i sieci neuronowych przedstawiono w tabeli I.



Współczynniki korelacji między rzeczywistymi wartościami danych a wartościami przewidywanymi również zestawiono w tabeli.

TRENDY NA PRZYSZŁOŚĆ

Reprezentacja 2-D ma potencjalne zastosowanie dla różnych parametrów meteorologicznych i różnych modeli, takich jak dopasowanie powierzchni, klasyfikacja oparta na klasteryzacji itp. Można również analizować dynamiczne, zmieniające się w czasie zachowanie modelu. Taką analizę można uznaćza przyszłe prace w ramach niniejszego badania.

WNIOSKI

W niniejszej pracy zaproponowano nowatorskie podejście do godzinowego prognozowania promieniowania słonecznego. Godzinowe promieniowanie słoneczne jest interpretowane i renderowane jako obraz 2D, a jego właściwości są badane. Zauważono, że reprezentacje dwuwymiarowe dają lepszy wgląd w rozkład słoneczny niż standardowa interpretacja 1D. Dla przykładu, zaprojektowano i porównano optymalne liniowe filtry predykcyjne 1D i 2D z 3 współczynnikami pod względem RMSE i współczynników korelacji. Wartość RMS energii danych i sekwencji predykcyjnej wynosi około 198. Po zastosowaniu predykcji, wartość RMS błędu predykcji zmniejsza się do 44,33 przy zastosowaniu predykcji 1D. Wartość ta stanowi również odchylenie standardowe systemu statystycznego. Dzięki zastosowaniu predykcji 2D, wartość ta jest dalej redukowana do 41,09. Aby podkreślić efektywność proponowanej reprezentacji 2D, zbudowano i wytrenowano dwie struktury NN ze sprzężeniem zwrotnym, jedną do modelowania 1D, a drugą do modelowania 2D, na tych samych danych. Wartości RMSE wynoszą odpowiednio 42,012 i 38,66 dla przypadku 1-D i 2-D. Obserwacja ta uzasadnia również efektywność reprezentacji danych 2-D, która wykorzystuje międzydniowe zależności rozkładu promieniowania słonecznego. Co więcej, oczywiste jest, że 2-D struktura sieci neuronowej (NN) zapewnia lepszą predykcję niż optymalny filtr liniowy.

WSTĘP

Koncepcja modułowości jest głównym zagadnieniem w generowaniu systemów sztucznej inteligencji. Modułowość to wszechobecna zasada organizacji, występująca wszędzie w naturalnych i sztucznych systemach złożonych . Dowody z biologicznego i filozoficznego punktu widzenia wskazują, że modułowość jest warunkiem koniecznym dla złożonych, inteligentnych zachowań. Ponadto, z inżynieryjnego punktu widzenia, modułowość wydaje się być jedynym sposobem na budowę złożonych struktur. Zatem, niezależnie od tego, czy pożądane są złożone programy neuronowe dla złożonych agentów, modułowość jest wymagana. Niniejszy artykuł wprowadza koncepcje modułowości i modułu z obliczeniowego punktu widzenia oraz ich zastosowanie w generowaniu programów neuronowych opartych na modułach. Zidentyfikowano dwa poziomy, strategiczny i taktyczny, na których można wdrożyć modułowość. Przedstawiono sposób ich działania i możliwości ich łączenia w celu wygenerowania całkowicie modułowego kontrolera dla agenta opartego na sieci neuronowej.

TŁO

Projektując kontroler dla agenta, istnieją dwa główne podejścia: pojedynczy moduł zawiera wszystkie wymagane zachowania agenta (podejście monolityczne) lub zachowanie globalne jest rozkładane na zestaw prostszych podzachowań, z których każde jest implementowane przez jeden moduł (podejście modułowe). Kontrolery monolityczne implementują w jednym module wszystkie wymagane odwzorowania między wejściami i wyjściami agenta. Zaletą jest brak konieczności identyfikowania wymaganych podzachowań ani relacji między nimi. Wadą jest to, że niezależnie od złożoności kontrolera, w praktyce zaprojektowanie takiego kontrolera bez uzyskania dużych interferencji między różnymi jego częściami może być niemożliwe. Zamiast tego, w przypadku kontrolera modułowego, kontroler globalny jest projektowany przez grupę podkontrolerów, dlatego wymagane podkontrolery i ich interakcje w celu wygenerowania końcowego globalnego wyjścia muszą być zdefiniowane. Pomimo wad podejścia modułowego , złożonych zachowań nie można osiągnąć bez pewnego stopnia modułowości . Sterowniki modułowe umożliwiają nabywanie nowej wiedzy bez zapominania o wiedzy nabytej wcześniej, co stanowi duży problem dla sterowników monolitycznych, gdy liczba wymaganych reguł wiedzy do nauczenia jest duża . Minimalizują one również wpływ problemu przypisywania punktów, gdzie mechanizm uczenia się musi dostarczyć sygnał uczenia oparty na bieżącej wydajności sterownika. Ten sygnał uczenia się musi być użyty do modyfikacji parametrów sterownika, co poprawi jego zachowanie. W dużych sterownikach trudno jest znaleźć zmieniające się parametry sterownika na podstawie globalnego sygnału uczenia. Modularyzacja pomaga utrzymać mały rozmiar sterowników, minimalizując wpływ przypisywania punktów. Podejścia modułowe pozwalają na redukcję złożoności rozwiązywanego zadania . Podczas gdy w systemie monolitycznym optymalizacja zmiennych jest wykonywana jednocześnie, co skutkuje dużą przestrzenią optymalizacji, w systemach modułowych optymalizacja jest wykonywana niezależnie dla każdego modułu, co skutkuje zmniejszoną przestrzenią wyszukiwania. Systemy modułowe są skalowalne w tym sensie, że stare moduły można wykorzystać do generowania nowych, gdy problemy są bardziej złożone, lub po prostu dodać nowe moduły do już istniejących. Oznacza to również, że systemy modułowe są odporne, ponieważ uszkodzenie jednego modułu powoduje utratę możliwości tego modułu, ale cały system częściowo utrzymuje swoją funkcjonalność. Modułowość może być rozwiązaniem problemu interferencji neuronowej , który występuje w sieciach monolitycznych. Zjawisko to występuje, gdy już wyszkolona sieć traci część swojej wiedzy, gdy jest ponownie szkolona do wykonywania innego zadania, zwanego przesłuchem czasowym , lub gdy wykonuje dwa lub więcej różnych zadań jednocześnie, co nazywa się przesłuchem przestrzennym (Jacobs, 1990). Systemy modułowe umożliwiają ponowne wykorzystanie modułów w różnych działaniach, bez ponownej implementacji funkcji reprezentowanej w każdym innym zadaniu.

Modułowość

Z obliczeniowego punktu widzenia modułowość rozumie się jako właściwość polegającą na tym, że niektóre złożone zadania obliczeniowe muszą zostać podzielone na prostsze podzadania. Następnie każde z tych prostszych podzadań jest wykonywane przez wyspecjalizowany system obliczeniowy zwany modułem, generujący rozwiązanie złożonego zadania na podstawie rozwiązania prostszych modułów podzadań. Z matematycznego punktu widzenia modułowość opiera się na koncepcji podzbioru zmiennych systemowych, który można optymalizować niezależnie od pozostałych zmiennych systemowych . W każdym przypadku zastosowanie modułowości oznacza, że w rozwiązywanym problemie istnieje struktura. W systemach modułowych każdy z modułów systemowych działa przede wszystkim zgodnie z własnymi, wewnętrznie określonymi zasadami. Moduły w ramach całego systemu są ściśle zintegrowane, ale niezależne od innych modułów, zgodnie z własnymi implementacjami. Mają one albo odrębne, albo te same dane wejściowe, ale generują własną odpowiedź. Gdy interakcje między modułami są słabe, a moduły działają niezależnie od siebie, system modułowy nazywa się prawie rozkładalnym . Inni autorzy zidentyfikowali ten typ systemów modułowych jako problemy rozdzielne. Jest to zdecydowanie jeden z najlepiej zbadanych typów modułowości i można go znaleźć wszędzie, od systemów biznesowych po systemy biologiczne. W prawie rozkładalnych systemach modułowych ostateczne optymalne rozwiązanie globalnego zadania uzyskuje się jako kombinację optymalnych rozwiązań prostszych (modułów). Jednak istnienie dekompozycji dla problemu nie oznacza, że podproblemy są całkowicie niezależne od siebie. W rzeczywistości system może być modułowy i nadal mieć współzależności między modułami. Problem rozkładalny definiuje się jako problem, który można rozłożyć na inne podproblemy, ale optymalne rozwiązanie jednego z tych problemów zależy od optymalnego rozwiązania niektórych pozostałych . Rozwiązanie takich systemów modułowych jest trudniejsze niż w przypadku typowego, rozdzielnego systemu modułowego i w literaturze jest zazwyczaj traktowane jako monolityczne.

Moduł

Większość prac wykorzystujących modularność posługuje się definicją modułu podaną przez (Fodor, 1983), która jest bardzo podobna do koncepcji obiektu w programowaniu obiektowym: moduł to element przetwarzania specyficzny dla danej dziedziny, który jest autonomiczny i nie może wpływać na wewnętrzne działanie innych modułów. Moduł może wpływać na inny moduł jedynie poprzez swoje dane wyjściowe, czyli wynik swoich obliczeń. Moduły nie znają globalnego problemu do rozwiązania ani globalnych zadań do wykonania i są sterowane określonymi bodźcami. Ostateczna odpowiedź systemu modułowego na rozwiązanie globalnego zadania jest dana przez integrację odpowiedzi różnych modułów przez specjalną jednostkę. Globalna architektura systemu definiuje sposób realizacji tej integracji. Jednostka integracyjna musi zdecydować, jak połączyć dane wyjściowe modułów, aby wygenerować ostateczną odpowiedź systemu, i nie może przekazywać informacji z powrotem do modułów.

MODULARNE SIECI NEURONOWE

W przypadku zastosowania modularności do projektowania sterownika opartego na modularnej sieci neuronowej (MNN) zazwyczaj obserwuje się trzy ogólne kroki: dekompozycję zadania, trening i wielomodułowe podejmowanie decyzji . Dekompozycja zadania polega na podzieleniu wymaganego sterownika na kilka podsterowników i przypisaniu każdego podsterownika do jednego modułu neuronowego. Moduły powinny być trenowane równolegle lub w różnych procesach, zgodnie z sekwencją wskazaną przez konstrukcję modułową. Na koniec, po przygotowaniu modułów, wdrażana jest wielomodułowa strategia podejmowania decyzji, która wskazuje, jak wszystkie te moduły powinny ze sobą współdziałać, aby wygenerować globalną odpowiedź sterownika. To podejście modularności można rozpatrywać na poziomie zadania. Poprzednie ogólne kroki modularności mają zastosowanie jedynie do modularyzacji problemów niemal dekompozycyjnych lub rozdzielnych. Problemy dekompozycyjne, czyli te, w których występują silne współzależności między modułami, nie są uwzględniane w ramach tego mechanizmu dekompozycji i są traktowane jako monolityczne. Artykuł wprowadza rozróżnienie między dwoma poziomami modułowości: obecnym poziomem modułowości, który koncentruje się na podziale zadań, oraz nowym poziomem modułowości realizowanym na poziomie urządzeń lub elementów. Podejścia te nazywane są odpowiednio strategicznym i taktycznym.

Modułowość strategiczna i taktyczna

Zapożyczając koncepcje z teorii gier, strategia zajmuje się tym, co należy zrobić w danej sytuacji, aby wykonać zadanie, dzieląc globalne rozwiązanie docelowe na wszystkie podcele wymagane do osiągnięcia celu globalnego. Taktyka natomiast dotyczy sposobu wdrażania planów, czyli sposobu wykorzystania zasobów dostępnych w danym momencie do osiągnięcia każdego z tych podcelów. W kontrolerach neuronowych modułowość strategiczna jest definiowana jako podejście modułowe, które identyfikuje, które podcele są wymagane dla agenta w celu rozwiązania problemu globalnego. Każdy zidentyfikowany podcel jest realizowany przez monolityczną sieć neuronową. Natomiast modułowość taktyczna w kontrolerach neuronowych definiuje się jako taką, która identyfikuje, które dane wejściowe i wyjściowe są niezbędne do realizacji danego celu, i projektuje pojedynczy moduł dla każdego z nich. W przypadku modułowości taktycznej modularyzacja odbywa się na poziomie elementów (dowolnych znaczących danych wejściowych lub wyjściowych kontrolera neuronowego), które są faktycznie zaangażowane w realizację zadania. W naszym rozumieniu, wszystkie badania oparte na modułowości neuronowej i zasadzie "dziel i zwyciężaj" koncentrują swój podział na poziomie strategicznym, czyli na tym, jak podzielić problem globalny na jego podcele. Następnie każdy z tych podcelów jest realizowany za pomocą pojedynczego kontrolera neuronowego, a cel końcowy jest generowany poprzez połączenie w pewnym sensie wyników tych podcelów. W niniejszym artykule proponuje się, po pierwsze, zdefiniowanie dwóch różnych poziomów modularności, a po drugie, wykorzystanie modułowości taktycznej jako nowego poziomu modularyzacji, który przydziela przestrzeń dla modułowości dekompozycyjnej. Oczekuje się, że modularyzacja taktyczna będzie możliwa w generowaniu złożonych kontrolerów neuronowych, w których konieczne jest uwzględnienie wielu sygnałów wejściowych i wyjściowych. Zostanie to potwierdzone poniżej, gdzie porównane zostanie zastosowanie obu typów modularności z podejściami monolitycznymi.

Implementacja modułowości

Modułowość strategiczna może być implementowana za pomocą dowolnego podejścia modułowego, które już istnieje w literaturze. Pełny opis znajduje się w publikacji . Każda z opisanych tam metod modularyzacji jest strategiczna, chociaż nie nadano jej takiej nazwy, i generalnie można ją zintegrować z modułowością taktyczną. Termin "strategiczny" jest używany w odniesieniu do tych podejść modułowych, aby odróżnić je od nowo proponowanej modułowości. Modułowość taktyczna definiuje modułowość na poziomie elementów zaangażowanych w generowanie podcelu. Przez elementy rozumie się dane wejściowe wymagane do wygenerowania podcelu oraz dane wyjściowe, które definiują rozwiązanie podcelu. Każdy z tych elementów odpowiada modułowi taktycznemu, implementowanemu przez prostą sieć neuronową. Oznacza to, że modułowość taktyczna jest implementowana poprzez zaprojektowanie całkowicie rozproszonego kontrolera złożonego z małych modułów przetwarzających wokół każdego ze znaczących elementów problemu. Schemat modułu taktycznego przedstawiono na rysunku .



Moduły taktyczne są połączone z powiązanym z nimi elementem, sterując nim i przetwarzając informacje przychodzące (dla elementów wejściowych) lub wychodzące (dla elementów wyjściowych). Ten rodzaj łączności oznacza, że element przetwarzający decyduje, które polecenia mają być wysłane do elementu wyjściowego lub jak należy interpretować wartość otrzymaną z elementu wejściowego. Mówi się, że element przetwarzający jest odpowiedzialny za powiązany z nim element. Aby wygenerować kompletną odpowiedź dla podcelu, wszystkie moduły taktyczne są ze sobą połączone, a dane wyjściowe każdego modułu są przesyłane z powrotem do wszystkich pozostałych. Dzięki wprowadzeniu tej łączności każdy moduł jest świadomy działań pozostałych, co pozwala różnym modułom na koordynację w celu wygenerowania wspólnej odpowiedzi i uniknięcie centralnego koordynatora. Powstała architektura przedstawia całkowicie rozproszoną sieć neuronową (MNN), w której moduły neuronowe są niezależne, ale implementują silne interakcje z pozostałymi modułami. Rysunek 2 przedstawia przykład łączności w generowaniu taktycznego modułowego sterownika neuronowego dla prostego systemu składającego się z dwóch elementów wejściowych i dwóch wyjść.



Łącząc oba poziomy w jednym kontrolerze neuronowym, należy najpierw przeprowadzić modularyzację strategiczną, aby zidentyfikować różne podcele wymagane do wdrożenia. Następnie należy przeprowadzić modularyzację taktyczną, wdrażając każdy z tych podcelów za pomocą grupy modułów taktycznych. Liczba modułów taktycznych dla każdego modułu strategicznego będzie zależeć od elementów zaangażowanych w realizację danego podcelu.

Przykłady zastosowań

Do tej pory modularność strategiczna i taktyczna była stosowana głównie w sterowaniu robotami. Elementami wejściowymi są czujniki, a elementami wyjściowymi - siłowniki. W pierwszym eksperymencie modularność taktyczna została zastosowana do sterowania robotem Khepera uczącym się rozwiązywania problemu "śmieciarki" . Obejmowało to koordynację 11 elementów (siedmiu czujników i czterech siłowników), tworząc 11 modułów taktycznych. Zadanie porównano z różnymi poziomami modularyzacji, w tym monolitycznym, strategicznym, taktycznym i kombinacją obu. Wynik pokazały, że połączenie obu poziomów dało lepsze rezultaty (patrz rysunek 3).



W dodatkowych eksperymentach zaimplementowano modułowość taktyczną dla robota Aibo. W tym przypadku do wygenerowania kontrolera potrzebnych było 31 modułów taktycznych. Kontroler został wygenerowany do rozwiązywania różnych zadań, takich jak wstawanie, stanie na nogach i odpychanie się od podłoża . Kontroler był również w stanie wygenerować jeden z pierwszych kontrolerów MNN, który umożliwił Aibo chodzenie.

TRENDY PRZYSZŁOŚCI

W paradygmacie robotyki ewolucyjnej generowanie złożonych zachowań jest bardzo trudne, gdy używany robot jest dość złożony i posiada ogromną liczbę czujników i siłowników. Zastosowanie modułowości taktycznej w połączeniu z modułowością strategiczną jest przedstawiane jako możliwe rozwiązanie problemu generowania złożonych zachowań w złożonych robotach. Nawet jeśli przedstawiono kilka przykładów z dość złożonym robotem, konieczne jest sprawdzenie, czy system może skalować się do systemów składających się z setek elementów. Dodatkowe zastosowania obejmują jego wykorzystanie w bardziej klasycznych dziedzinach, takich jak rozpoznawanie wzorców, rozpoznawanie mowy.

WNIOSKI

Poziom modułowości w kontrolerach neuronowych można znacznie zwiększyć, uwzględniając modułowość taktyczną. Ten typ modułowości uzupełnia typowe podejścia modularyzacji oparte na modularyzacji strategicznej, poprzez podział modułów strategicznych na ich minimalne komponenty i przypisanie każdemu z nich jednego modułu neuronowego. Taka modularyzacja umożliwia implementację problemów dekompozycyjnych w ramach struktury modularnej. Oba typy modularyzacji można połączyć w celu uzyskania wysoce modularnego kontrolera neuronowego, który zapewnia lepsze rezultaty w złożonym sterowaniu robotem.

WSTĘP

Kluczowym czynnikiem umożliwiającym interoperacyjność w sieci semantycznej jest to, że ontologie są opracowywane przez różne organizacje na dużą skalę, również w obszarach, które się pokrywają. Dlatego też mapowanie ontologii pojawiło się w celu umożliwienia dzielenia się wiedzą i integracji semantycznej w środowisku, w którym wiedza i informacje są reprezentowane przez różne ontologie bazowe. Problem mapowania ontologii można zdefiniować jako ustalenie relacji między encjami dwóch ontologii. Wyniki mapowania mogą być wykorzystywane do różnych celów, takich jak integracja schematów/ontologii, wyszukiwanie informacji, mediacja zapytań czy mapowanie usług sieciowych. W niniejszym artykule przedstawiono metodę mapowania pojęć i właściwości między ontologiami. Najpierw stosowana jest analiza składniowa oparta na ciągach tokenów, a następnie przeprowadzana jest analiza semantyczna zgodnie z WordNet i grafami drzewiastymi reprezentującymi struktury ontologii. Wyniki eksperymentów dowodzą, że nasz algorytm znajduje odwzorowania z wysoką precyzją.

TŁO

Zapożyczona z filozofii ontologia odnosi się do systematycznego opisu tego, co może istnieć lub "być" w świecie. W dziedzinie sztucznej inteligencji i reprezentacji wiedzy ontologia odnosi się do konstruowania modeli wiedzy, które określają zbiór pojęć, ich atrybutów i relacji między nimi. Ontologie definiuje się jako "jawne konceptualizacje dziedziny" i postrzega jako klucz do urzeczywistnienia wizji Sieci Semantycznej. Ontologia, jako ważna technika reprezentacji wiedzy i informacji, pozwala na włączenie semantyki do danych, aby radykalnie usprawnić wymianę informacji. Sieć Semantyczna jest uniwersalnym medium wymiany danych, informacji i wiedzy. Sugeruje ona adnotację zasobów sieciowych za pomocą metadanych przetwarzalnych maszynowo. Wraz z szybkim rozwojem Sieci Semantycznej, prawdopodobne jest, że liczba wykorzystywanych ontologii znacznie wzrośnie w ciągu najbliższych kilku lat. Same w sobie ontologie nie rozwiązują jednak żadnego problemu interoperacyjności. Mapowanie ontologii jest zatem kluczem do wykorzystania semantycznej interoperacyjności informacji i dlatego w ostatnich latach przyciąga dużą uwagę społeczności badawczej. Niniejsza sekcja wprowadza podstawowe koncepcje integracji informacji, ontologii i mapowania ontologii. Niedopasowania między ontologiami są spowodowane głównie niezależnym rozwojem ontologii w różnych organizacjach. Stają się one oczywiste podczas próby łączenia ontologii opisujących częściowo nakładające się dziedziny. Niedopasowania między ontologiami można ogólnie podzielić na heterogeniczność składniową, semantyczną i strukturalną. Heterogeniczność składniowa oznacza różnice w prymitywach językowych używanych do określania ontologii, heterogeniczność semantyczna oznacza różnice w sposobie konceptualizacji i modelowania dziedzin, podczas gdy heterogeniczność strukturalna oznacza różnice w strukturyzacji informacji. Dotychczas zaproponowano szereg prac dotyczących mapowania ontologii. W pracy (Madhavan, 2001) przedstawiono hybrydowy algorytm mapowania podobieństwa. Proponowany sposób integruje techniki dopasowywania schematów językowych i strukturalnych. Dopasowanie opiera się głównie na nazwach elementów schematu, nie uwzględniając ich właściwości. LOM to półautomatyczne narzędzie do mapowania ontologii oparte na leksykonie, które wspiera inżyniera mapowania w wstępnym porównaniu terminów ontologicznych między mapowanymi ontologiami. Rozkłada terminy wielowyrazowe na ich składniki, z tym że nie wykonuje bezpośredniego mapowania między słowami. Procedura kojarzy numery indeksów synsetów WordNet słów składowych z terminem ontologicznym. Dwa terminy, które mają największą liczbę wspólnych synsetów, są rejestrowane i prezentowane użytkownikowi.

GŁÓWNY CEL

Nasza obecna praca ma na celu pokonanie wspomnianych powyżej ograniczeń i poprawę precyzji mapowania ontologii. Celem badawczym jest opracowanie metody i ocena wyników mapowania ontologii. W niniejszym artykule przedstawiamy metodę mapowania ontologii syntetyzowanych z analizy składniowej opartej na tokenach oraz analizy semantycznej z wykorzystaniem tezaurusa WordNet i grafów o strukturze drzewa. Algorytm jest opisany i zapisany w pseudokodzie, jak pokazano na rysunku 1.



Obiecujące wyniki uzyskane z eksperymentów wskazują, że nasz algorytm znajduje mapowania z wysoką precyzją.

Mapowanie na poziomie składni oparte na tokenizacji

Przed zastosowaniem mapowania składniowego nieuniknione jest wstępne przetwarzanie, zwane tokenizacją. W tym przypadku ontologie są reprezentowane w języku OWL-DL1. Dlatego wszystkie terminy ontologii są reprezentowane za pomocą identyfikatora URI OWL. Na przykład, w ontologii "beer", klasa OWL "Ingredient" jest opisana jako "[OWLClassImpl] http://www.purl.org/net/ontology/beer#Ingredient", gdzie "[OWLClassImpl]" implikuje klasę OWL, adres URL "http://www.purl.org/net/ontology/beer" wskazuje pochodzenie ontologii, a "Ingredient" to nazwa klasy. Tokenizacja powinna najpierw wyodrębnić prawidłowe encje ontologii z opisów OWL, którymi w tym przykładzie są "Ingredient". Co więcej, etykiety encji ontologii (klas i właściwości) są często definiowane za pomocą różnych reprezentacji przez różne organizacje. Na przykład reprezentacje mogą być z symbolami łączników lub bez nich, pisane wielkimi lub małymi literami itd., co znacznie komplikuje i utrudnia identyfikację terminów. Tokenizacja oznacza parsowanie nazw na tokeny w oparciu o określone reguły lub symbole przez konfigurowalne tokenizatory wykorzystujące interpunkcję, wielkie litery, symbole specjalne, cyfry itd. W ten sposób nazwa klasy lub właściwości może zostać tokenizowana w jeden lub kilka ciągów tokenów. Na przykład termin"Social_%26_Science" można tokenizować jako "Social", "26" i "Science". Należy zauważyć, że terminy mogą czasami zawierać cyfry, takie jak data, czego nie można pominąć. Dla uproszczenia zakładamy, że wszystkie terminy pojęć ontologii (klasy, właściwości) są opisane bez skrótów. Proces mapowania między różnymi nazwami klas i właściwości jest następnie przekształcany w mapowanie między tokenami. Najpierw sprawdzamy, czy oryginalne węzły potomne są równe, ignorując wielkość liter. W przeciwnym razie, do sprawdzenia, czy są równe, używane są tokeny. Jeśli nie, do obliczenia podobieństwa stosowana jest miara podobieństwa oparta na odległości edycyjnej. Jeśli obliczona wartość podobieństwa przekracza próg ? (na przykład 0,95), porównywane węzły są uznawane za podobne. Proces jest kontynuowany z kolejną parą węzłów w ten sam sposób. Do obliczenia podobieństwa tokenów wykorzystano tutaj odległość edycyjną sformułowaną przez Levenshteina oraz metodę mapowania ciągów znaków zaproponowaną przez Maedche i Staab . Odległość edycyjna to dobrze znana metoda ważenia różnic między dwoma ciągami znaków. Mierzy ona minimalną liczbę wstawień, usunięć i podstawień tokenów wymaganych do przekształcenia jednego ciągu znaków w drugi za pomocą algorytmu programowania dynamicznego. Metoda dopasowania ciągów znaków służy do obliczenia podobieństwa tokenów na podstawie odległości edycyjnej Levenshteina.



gdzie X, Y to ciągi tokenów, "|X|" to długość X, "min( )" i "max()" oznaczają odpowiednio minimalną/maksymalną wartość dwóch argumentów, a "ed( )" to odległość edycyjna. Ponieważ oryginalne terminy ontologii mogły zostać podzielone na wiele podterminów, tj. tokenów, konieczne jest oddzielne obliczenie podobieństwa między każdą parą ciągów tokenów. Załóżmy, że liczba tokenów pierwszego wyrazu wynosi m, n dla drugiego wyrazu i załóżmy, że m ≥ n, całkowita miara podobieństwa zgodnie z równaniem (1) wynosi:



gdzie Sim_orig to podobieństwo między oryginalnymi ciągami znaków, Sim_ij to podobieństwo między tokenami i-tym i j-tym z dwóch terminów źródłowych, a ?1, ?_ij to wagi dla Sim_orig i Sim_ij. Suma ?_ij i ?₁ powinna wynosić 1. Biorąc pod uwagę predefiniowany próg podobieństwa, jeśli uzyskana wartość podobieństwa jest większa lub równa progowi, dwa tokeny są uznawane za podobne i odwrotnie.

Mapowanie na poziomie semantycznym w oparciu o strukturę ontologii

Heterogeniczność semantyczna występuje, gdy występują rozbieżności co do znaczenia, interpretacji lub zamierzonego wykorzystania tych samych lub powiązanych danych. Relacje semantyczne to:

o różne nazewnictwo tej samej treści, tj. synonimy,
o różne poziomy abstrakcji: terminy ogólne a bardziej szczegółowe (imię a imię i nazwisko), hiperonimy lub hiponimy, oraz
o różne struktury dotyczące tej samej treści (oddzielny typ a część typu), tj. meronimy.

W mapowaniu ontologii WordNet jest jednym z najczęściej wykorzystywanych źródeł wiedzy kontekstowej. W rzeczywistości pełni rolę "pośrednika", pomagając w znajdowaniu heterogeniczności semantycznej. Do biblioteki WordNet można uzyskać dostęp za pomocą interfejsu API Java JWNL2. Grupuje ona angielskie słowa w zestawy synonimów zwane synsetami, które zawierają krótkie, ogólne definicje, i rejestruje różne relacje semantyczne między tymi zestawami synonimów. Celem jest stworzenie bardziej intuicyjnej w użyciu kombinacji słownika i tezaurusa oraz wsparcie dla automatycznej analizy tekstu i aplikacji sztucznej inteligencji. Zakłada się, że każdy sens w synsecie WordNet opisuje pojęcie. Sensy WordNet są powiązane ze sobą poprzez relacje synonimów, hiponimów i hiperonimów. Terminy leksykalizujące to samo pojęcie (sens) są uważane za równoważne poprzez relację synonimów, podczas gdy hiperonimy, hiponimy i meronimy są uważane za podobne. Zgodnie z tą zasadą, oryginalne terminy ontologiczne i ich względne ciągi tokenów są najpierw sprawdzane, czy mają tę samą część mowy, tj. rzeczownik, czasownik, przymiotnik, przysłówek. Następnym krokiem jest ocena, czy są one synonimami, hiperonimami, hiponimami czy meronimami. Analogicznie do równania (2), dla pary węzłów wartość podobieństwa jest obliczana na podstawie wag różnych części podobieństwa. Jeśli przekroczy ona określony próg, para jest uważana za podobną. Jeśli wyżej wymienione metody mapowania składniowego i semantycznego WordNet nadal nie mogą znaleźć odwzorowania między dwoma terminami, stosowana jest inna metoda na poziomie semantycznym oparta na grafach o strukturze drzewa. Zgodnie z renderowaniem w SWOOP3 (inspirowanym hipermediami edytorze i przeglądarce ontologii opartym na ontologiach OWL, który wspiera renderery w uzyskiwaniu drzew hierarchii klas/właściwości, a także definicji i wnioskowanych faktów dotyczących klas i właściwości OWL), encje ontologii są reprezentowane przez drzewa hierarchii klas/właściwości. Na podstawie drzew hierarchii klas konstruowane są grafy o strukturze drzewa. W oparciu o pojęcie grafów struktur (Lian, 2004), graf o strukturze drzewa (graf ts) definiuje się jako:

Definicja 1. Mając dane drzewo zbiorów T, gdzie N jest sumą wszystkich zbiorów w T, a E jest zbiorem krawędzi w T, wówczas ts-g (T) = (N, E) nazywa się grafem drzewiastym zbioru T, jeżeli zachodzi (a, b) ∈ E wtedy i tylko wtedy, gdy a jest elementem nadrzędnym zbioru b; a nazywa się węzłem nadrzędnym, a b węzłem podrzędnym.

Podczas budowania grafu ts, do przechodzenia hierarchii drzewa stosuje się metodę przechodzenia wszerz. Aby skonstruować graf ts, zaczynamy od pierwszego węzła potomnego węzła głównego. Wszystkie jego węzły potomne i ich względne węzły nadrzędne tworzą krawędzie jako (węzeł nadrzędny, węzeł podrzędny) dla grafu ts. Proces jest powtarzany aż do całkowitego przejścia drzewa. Po zbudowaniu grafów ts dwóch ontologii, które mają zostać dopasowane, zestawy krawędzi obu grafów są wykorzystywane w procesie mapowania. Względne pozycje węzłów pary (z dwóch ontologii) w ich grafach o strukturze drzewa określają mapowanie na poziomie semantycznym między nimi. W Tabeli 1 podsumowujemy trzy typy relacji między krawędziami charakteryzującymi właściwości, klasy potomne oraz klasy nadrzędne i potomne. Rozumiejąc te właściwości, możemy wywnioskować, że byty posiadające te same właściwości są podobne. Nie jest to reguła zawsze obowiązująca, ale jest silnym wskaźnikiem podobieństwa.

Wyniki eksperymentalne

Implementacja naszego algorytmu została napisana w Javie. Wykorzystuje on SWOOP do parsowania plików OWL. Wszystkie testy przeprowadzono na standardowym komputerze PC (z systemem Windows XP). Nasze przypadki testowe obejmują ontologie "Drużyna baseballowa" i "Rosja" dostarczone przez instytut AIFB4. Aby uzyskać wyobrażenie o wydajności matchmakera, należy wziąć pod uwagę różne wskaźniki. Istnieją różne sposoby pomiaru zgodności wyszukanych informacji z informacjami docelowymi. Aby ocenić jakość wyników mapowania, wykorzystujemy standardowe metryki wyszukiwania informacji: Recall (r), Precision (p) i F-Measure, gdzie Recall to stosunek liczby wyszukanych encji relewantnych do całkowitej liczby wyszukanych encji relewantnych, Precision to stosunek liczby wyszukanych rekordów relewantnych do całkowitej liczby wyszukanych rekordów relewantnych i nierelewantnych, a



PRZYSZŁE TRENDY

Obecnie wyniki obliczeń podobieństwa są udostępniane w formie dokumentów tekstowych. Aby przedstawić wyniki mapowania w sposób bardziej racjonalny i zrozumiały, celem naszych przyszłych prac jest traktowanie wyników obliczeń podobieństwa jako ontologii. Kolejnym celem naszych przyszłych prac jest rozwiązanie problemów bezpieczeństwa związanych z mapowaniem ontologii, takich jak zarządzanie zaufaniem w aplikacjach usług sieciowych.

WNIOSKI

Ogólnym celem badawczym przedstawionym w niniejszym artykule jest opracowanie metody mapowania ontologii, która łączy analizę składniową mierzącą różnicę między tokenami na podstawie odległości edycyjnej z analizą semantyczną opartą na WordNet jako relacji semantycznej i podobieństwie grafów strukturalnych reprezentujących porównywane ontologie. Empirycznie wykazaliśmy, że nasza metoda mapowania syntezowanego działa ze stosunkowo wysoką precyzją.

WSTĘP

Systemy informatyczne opracowano na początku lat 60. XX wieku w celu przetwarzania zamówień, fakturowania, kontroli zapasów, list płac i należności. Wkrótce rozpoczęły się badania nad systemami informatycznymi. Harry Stern rozpoczął publikację rubryki "Systemy informacyjne w nauce o zarządzaniu" w czasopiśmie "Management Science", aby stworzyć forum do dyskusji wykraczającej poza same artykuły naukowe . Ackoff (1967) prowadził najwcześniejsze badania nad systemami informatycznymi w zakresie podejmowania decyzji i opublikował je w "Management Science". Gorry i Scott Morton (1971) po raz pierwszy użyli terminu "systemy wspomagania decyzji" (DSS) w artykule i opracowali ramy doskonalenia systemów informatycznych w zarządzaniu. Tematyka badań nad systemami informatycznymi i DSS jest zróżnicowana. Jednym z głównych tematów jest prawidłowe projektowanie systemów. Hurtownie danych, jako aktywny element DSS, który jest częścią dzisiejszych systemów Business Intelligence, stały się jednym z najważniejszych osiągnięć w dziedzinie systemów informatycznych w połowie i pod koniec lat 90. XX wieku. Ponieważ środowisko biznesowe stało się bardziej globalne, konkurencyjne, złożone i zmienne, inicjatywy w zakresie zarządzania relacjami z klientami (CRM) i e-commerce stwarzają zapotrzebowanie na duże, zintegrowane repozytoria danych i zaawansowane możliwości analityczne. Korzystając z hurtowni danych, firmy mogą podejmować decyzje dotyczące strategii specyficznych dla klienta, takich jak profilowanie klientów, segmentacja klientów i analiza cross-sellingu . W związku z tym projektowanie i rozwój hurtowni danych stały się ważnymi zagadnieniami dla projektantów i programistów systemów informatycznych. Niniejszy artykuł przedstawia niektóre z obecnie omawianych metodologii rozwoju i projektowania w hurtowniach danych, takie jak model wielowymiarowy kontra relacyjny model ER, CIF kontra metodologie wielowymiarowe, podejścia oparte na danych kontra podejścia oparte na metrykach, podejścia projektowe odgórne kontra oddolne, partycjonowanie danych i przetwarzanie równoległe.

TŁO

Projektowanie hurtowni danych to długotrwały, czasochłonny i kosztowny proces. Każdy błędnie obliczony krok może prowadzić do niepowodzenia. Dlatego naukowcy włożyli wiele wysiłku w badanie zagadnień i metodologii związanych z projektowaniem i rozwojem. Modelowanie danych dla hurtowni danych różni się od modelowania danych w operacyjnej bazie danych. System operacyjny, np. przetwarzanie transakcji online (OLTP), to system służący do prowadzenia działalności w czasie rzeczywistym, w oparciu o bieżące dane. System OLTP zazwyczaj wykorzystuje modelowanie związków encji (ER) i projektowanie bazy danych zorientowane na aplikacje . System informatyczny, podobnie jak hurtownia danych, jest zaprojektowany w celu wspierania podejmowania decyzji w oparciu o dane historyczne i predykcyjne dla złożonych zapytań lub aplikacji eksploracji danych . Schemat magazynu danych jest postrzegany jako model wymiarowy . Zazwyczaj przyjmuje schemat gwiazdy lub płatka śniegu oraz projekt bazy danych zorientowany na podmiot . Projekt schematu jest najważniejszy dla projektu magazynu danych. Zaproponowano wiele podejść i metodologii w projektowaniu i rozwoju magazynów danych. Dwóm głównym metodologiom projektowania magazynów danych poświęcono najwięcej uwagi. Inmon i inni zaproponowali architekturę Corporate Information Factory (CIF). Architektura ta, w projektowaniu hurtowni danych na poziomie atomowym, wykorzystuje schemat zdenormalizowanego diagramu związków encji (ERD). Kimball (1996, 1997) zaproponował architekturę wielowymiarową (MD). Architektura ta wykorzystuje schemat gwiazdy w hurtowniach danych na poziomie atomowym. Którą architekturę powinno wybrać przedsiębiorstwo? Czy jedna jest lepsza od drugiej? Obecnie najpopularniejszym modelem danych do projektowania hurtowni danych jest model wymiarowy . Niektórzy badacze nazywają go modelem projektowania opartego na danych. Artz (2006) opowiada się jednak za modelem opartym na metrykach, który, jako inny pogląd na projektowanie hurtowni danych, zaczyna się od identyfikacji kluczowych procesów biznesowych, które należy mierzyć i śledzić w czasie, aby organizacja mogła funkcjonować wydajniej. Zawsze istniał problem podejścia odgórnego i oddolnego w projektowaniu systemów informatycznych. To samo dotyczy projektowania hurtowni danych. Były to zagadkowe pytania dla architektów inteligentnych rozwiązań biznesowych oraz projektantów i deweloperów hurtowni danych. W kolejnej sekcji poszerzona zostanie dyskusja na temat zagadnień związanych z metodologiami projektowania i rozwoju hurtowni danych.

METODOLOGIE PROJEKTOWANIA I ROZWOJU

Modelowanie danych w hurtowniach danych

Projektowanie bazy danych zazwyczaj dzieli się na czteroetapowy proces . Po zebraniu wymagań następuje projektowanie koncepcyjne, logiczne i fizyczne. Spośród tych czterech etapów, projektowanie logiczne jest kluczowym punktem procesu projektowania bazy danych i ma największe znaczenie dla samego procesu projektowania bazy danych. W projektowaniu systemu OLTP zazwyczaj stosuje się model danych ER i projekt bazy danych zorientowany na aplikacje. Większość nowoczesnych systemów informatycznych przedsiębiorstw jest budowana z wykorzystaniem modelu ER . Model danych ER jest powszechnie stosowany w projektowaniu relacyjnych baz danych, gdzie schemat bazy danych składa się z zestawu encji i relacji między nimi. Model ER służy do zademonstrowania szczegółowych relacji między elementami danych. Koncentruje się on na usuwaniu redundancji elementów danych w bazie danych. Schemat to projekt bazy danych zawierający logikę i pokazujący relacje między danymi zorganizowanymi w różnych relacjach . Z kolei magazyn danych wymaga zwięzłego schematu zorientowanego na podmiot, który ułatwia analizę danych online. Schemat magazynu danych jest postrzegany jako model wymiarowy, który składa się z centralnej tabeli faktów i zestawu otaczających ją tabel wymiarów, z których każda odpowiada jednemu ze składników lub wymiarów tabeli faktów . Modele wymiarowe są zorientowane na konkretny proces biznesowy lub podmiot. To podejście utrzymuje elementy danych powiązane z procesem biznesowym w odległości tylko jednego łączenia. Najpopularniejszym modelem danych dla magazynu danych jest model wielowymiarowy. Taki model może istnieć w postaci schematu gwiazdy, schematu płatka śniegu lub schematu płatka gwiazdy. Schemat gwiazdy to najprostsza struktura bazy danych zawierająca tabelę faktów w centrum, bez redundancji, otoczoną zestawem mniejszych tabel wymiarów . Tabela faktów jest połączona z tabelami wymiarów za pomocą relacji wiele do jednego, aby zapewnić ich hierarchię. Schemat gwiazdy może zapewnić szybki czas reakcji, umożliwiając optymalizatorom baz danych pracę z prostymi strukturami baz danych w celu uzyskania lepszych planów wykonania. Schemat płatka śniegu jest odmianą modelu schematu gwiazdy, w którym wszystkie informacje wymiarowe są przechowywane w trzeciej postaci normalnej, co dodatkowo dzieli dane na dodatkowe tabele, przy zachowaniu tej samej struktury tabeli faktów. Aby zadbać o hierarchię, tabele wymiarów są połączone z tabelami podwymiarów za pomocą relacji wiele do jednego. Powstały graf schematu tworzy kształt podobny do płatka śniegu . Schemat płatka śniegu może zmniejszyć redundancję i zaoszczędzić miejsce w pamięci. Może to jednak również zmniejszyć efektywność przeglądania, a wydajność systemu może ulec pogorszeniu. W związku z tym schemat płatka śniegu nie jest tak popularny jak schemat gwiazdy w projektowaniu hurtowni danych . Ogólnie rzecz biorąc, schemat gwiazdy wymaga większej pamięci, ale jest szybszy w przetwarzaniu niż schemat płatka śniegu . Schemat płatka gwiazdy , zwany również schematem galaktyki lub schematem konstelacji faktów , jest połączeniem zdenormalizowanego schematu gwiazdy i znormalizowanego schematu płatka śniegu . Schemat płatka gwiazdy jest używany w sytuacjach, gdy trudno jest przekształcić wszystkie jednostki w zestaw odrębnych wymiarów. Umożliwia on pewien stopień przenikania się między wymiarami w celu udzielenia odpowiedzi na odrębne zapytania . Należy zauważyć, że te trzy schematy są zazwyczaj przyjmowane w zależności od różnic w wymaganiach projektowych. Hurtownia danych gromadzi informacje o podmiotach obejmujących całą organizację, takich jak klienci, produkty, sprzedaż itp. Jej zakres obejmuje całe przedsiębiorstwo . Schemat Starflake może modelować wiele powiązanych ze sobą podmiotów. Dlatego jest zazwyczaj używany do modelowania hurtowni danych obejmującej całe przedsiębiorstwo. Z kolei hurtownia danych jest podobna do hurtowni danych, ale ogranicza się do działu, którego dotyczy. Jej zakres obejmuje cały dział. Schemat gwiazdy i schemat płatka śniegu są ukierunkowane na modelowanie pojedynczych podmiotów. W związku z tym schemat gwiazdy lub schemat płatka śniegu jest powszechnie używany do modelowania hurtowni danych, chociaż schemat gwiazdy jest bardziej popularny i wydajny.

CIF a wielowymiarowość

Dwóm głównym metodologiom projektowania poświęcono więcej uwagi w projektowaniu i rozwoju hurtowni danych. Kimball (1996, 1997) zaproponował architekturę wielowymiarową (MD). Inmon, Galemmco i Geiger (2000) zaproponowali architekturę Corporate Information Factory (CIF). Imhoff i in. (2004) porównali obie metody, stosując ważne kryteria, takie jak zakres, perspektywa, przepływ danych itp. Jedną z najważniejszych różnic między architekturami CIF i MD jest definicja hurtowni danych. W przypadku architektury MD projekt hurtowni danych na poziomie atomowym znacząco różni się od projektu hurtowni danych CIF, podczas gdy jej zagregowany schemat hurtowni danych jest w przybliżeniu taki sam, jak w architekturze CIF. Architektura MD wykorzystuje schematy gwiazdy, podczas gdy architektura CIF wykorzystuje zdenormalizowany schemat ERD. Ta różnica w modelowaniu danych stanowi główną różnicę projektową w obu architekturach . Hurtownia danych może wymagać obu typów hurtowni danych w architekturze magistrali hurtowni danych, w zależności od wymagań biznesowych. W przeciwieństwie do architektury CIF, w architekturze MD nie ma fizycznego repozytorium równoważnego hurtowni danych. Projekt obu hurtowni danych jest w przeważającej mierze wielowymiarowy w obu architekturach, ale architektura CIF nie ogranicza się tylko do tego projektu i może obsługiwać znacznie szerszy zestaw technik projektowania hurtowni danych. Pod względem zakresu, obie architektury uwzględniają zakres przedsiębiorstwa i zakres jednostki biznesowej, przy czym architektura CIF kładzie większy nacisk na zakres przedsiębiorstwa, a architektura MD na zakres jednostki biznesowej. Imhoff i inni (2004) zachęcają do stosowania kombinacji technik modelowania danych w obu podejściach architektonicznych, a mianowicie ERD lub technik normalizacji dla hurtowni danych oraz modelu danych schematu gwiazdy dla wielowymiarowych hurtowni danych. Architektura CIF składająca się wyłącznie z magazynu danych bez wielowymiarowych hurtowni danych jest praktycznie bezużyteczna, a środowisko obejmujące wyłącznie wielowymiarowy magazyn danych niesie ze sobą ryzyko braku integracji przedsiębiorstwa i obsługi innych form analiz Business Intelligence.

Model oparty na danych a model oparty na metrykach

Obecnie najpopularniejszym modelem danych do projektowania hurtowni danych jest model wymiarowy . W tym modelu dane z systemów OLTP są gromadzone w modelu wymiarowym. Naukowcy określają projekt hurtowni danych oparty na tym modelu jako model oparty na danych, ponieważ procesy pozyskiwania informacji w hurtowni danych są sterowane danymi udostępnianymi w bazowych systemach informatycznych. Innym podejściem do projektowania hurtowni danych jest podejście oparte na metrykach , które rozpoczyna się od identyfikacji kluczowych procesów biznesowych, które należy mierzyć i śledzić w czasie, aby organizacja mogła funkcjonować bardziej efektywnie. Zalety modelu opartego na danych obejmują jego bardziej konkretną, ewolucyjną naturę i wykorzystanie pochodnych danych podsumowujących. Jednak informacje generowane z hurtowni danych mogą być bezużyteczne dla użytkownika ze względu na fakt, że charakter pochodnych danych podsumowujących z systemów OLTP może nie być jasny. Z drugiej strony, podejście projektowe oparte na metrykach zaczyna się od zdefiniowania kluczowych procesów biznesowych, które należy mierzyć i śledzić w czasie. Po zidentyfikowaniu tych kluczowych procesów biznesowych, są one modelowane w wielowymiarowym modelu danych. Następnie przeprowadzana jest dalsza analiza w celu określenia sposobu wypełniania modelu wielowymiarowego . Według Artza (2006), model oparty na danych w projektowaniu hurtowni danych ma niewielką przyszłość, ponieważ informacje pochodzące z modelu opartego na danych to informacje o zbiorze danych. Model oparty na metrykach, z kolei, prawdopodobnie będzie miał pewne kluczowe skutki i implikacje, ponieważ informacje pochodzące z modelu opartego na metrykach to informacje o organizacji. Podejście oparte na danych dominuje obecnie w projektowaniu hurtowni danych w organizacjach. Z drugiej strony, podejście oparte na metrykach jest na etapie badań i wymaga praktycznego potwierdzenia jego spekulowanych potencjalnie dramatycznych implikacji. Odgórne a oddolne Istnieją dwa podejścia do budowy hurtowni danych przed rozpoczęciem jej budowy, w tym hurtowni danych: podejście odgórne i podejście oddolne . Podejście odgórne zaczyna się od ogólnego obrazu całościowego projektu obejmującego całe przedsiębiorstwo. Budowana hurtownia danych jest duża i zintegrowana, a nacisk kładzie się na integrację danych przedsiębiorstwa do wykorzystania w dowolnej hurtowni danych już od pierwszego projektu. Implikuje to strategiczną, a nie operacyjną perspektywę danych. Służy ona właściwemu dopasowaniu systemów informatycznych organizacji do jej celów biznesowych (Marakas, 2003). Jednak podejście to jest ryzykowne . Z kolei podejście oddolne polega na projektowaniu hurtowni danych z uwzględnieniem potrzeb jednostek biznesowych w zakresie systemów operacyjnych. Zaczyna się od eksperymentów i prototypów . W podejściu oddolnym, działowe hurtownie danych są budowane najpierw jeden po drugim. Oferuje to szybszą i łatwiejszą implementację, korzystny zwrot z inwestycji i mniejsze ryzyko awarii, ale z wadą fragmentacji i redundancji danych. Celem podejścia oddolnego jest zaspokojenie potrzeb specyficznych dla danej jednostki, przy minimalnym uwzględnieniu ogólnych wymagań dotyczących danych w całym przedsiębiorstwie . Alternatywą dla dwóch omówionych powyżej podejść jest zastosowanie podejścia łączonego , dzięki któremu "organizacja może wykorzystać planowy i strategiczny charakter podejścia odgórnego, zachowując jednocześnie szybką implementację i oportunistyczne zastosowanie podejścia oddolnego" , gdy takie podejście jest konieczne w bieżących scenariuszach organizacyjnych i biznesowych.

Partycjonowanie danych i przetwarzanie równoległe

Partycjonowanie danych to proces rozkładania dużych tabel (tabel faktów, widoków zmaterializowanych, indeksów) na wiele mniejszych tabel poprzez zastosowanie operatorów selekcji . Dobry schemat partycjonowania jest niezbędnym elementem projektowania bazy danych, która skorzysta z paralelizmu . Dzięki dobrze przeprowadzonemu partycjonowaniu można osiągnąć znaczną poprawę dostępności, administracji i wydajności skanowania tabel. Przetwarzanie równoległe opiera się na równoległej bazie danych, w której stosowane są wieloprocesory. Równoległe bazy danych łączą wiele mniejszych maszyn, aby osiągnąć taką samą przepustowość jak pojedyncza, większa maszyna, często z większą skalowalnością i niezawodnością niż bazy danych z jednym procesorem . W kontekście relacyjnego przetwarzania analitycznego online (ROLAP), poprzez partycjonowanie danych w schemacie ROLAP (schemat gwiazdy lub schemat płatka śniegu) pomiędzy zestaw procesorów, zapytania OLAP mogą być wykonywane równolegle, potencjalnie osiągając liniowe przyspieszenie i tym samym znacząco skracając czas odpowiedzi na zapytanie . Biorąc pod uwagę rozmiar współczesnych repozytoriów hurtowni danych, rozwiązania wieloprocesorowe mają kluczowe znaczenie dla ogromnych wymagań obliczeniowych obecnych i przyszłych systemów OLAP . Założeniem większości szybkich algorytmów obliczeniowych jest to, że ich algorytmy można zastosować w systemie przetwarzania równoległego . W rezultacie, czasami konieczne jest wykorzystanie przetwarzania równoległego do eksploracji danych, ponieważ eksploracja danych wiąże się z dużymi ilościami danych i intensywnym nakładem pracy na wyszukiwanie . Dlatego partycjonowanie danych i przetwarzanie równoległe to dwie uzupełniające się techniki pozwalające na redukcję kosztów przetwarzania zapytań podczas projektowania i rozwoju magazynów danych .

PRZYSZŁE TRENDY

Obecnie hurtownie danych są szeroko stosowane w zarządzaniu relacjami z klientami (CRM). Jednak obecnie nie ma uzgodnionych, ustandaryzowanych zasad projektowania hurtowni danych obsługujących CRM i konieczne jest opracowanie taksonomii analiz CRM w celu określenia czynników wpływających na decyzje projektowe dotyczące hurtowni danych CRM . W obszarze modelowania danych, aby opracować bardziej ogólne rozwiązanie do modelowania hurtowni danych, obecny model ER i model wymiarowy muszą zostać rozszerzone na wyższy poziom, aby połączyć prostotę modelu wymiarowego i wydajność modelu ER ze wsparciem koncepcji obiektowych.

WNIOSKI

Przeanalizowano i omówiono kilka metodologii rozwoju i projektowania hurtowni danych. Model hurtowni danych różni się od modelu ER orientacją na konkretne cele biznesowe. Przedsiębiorstwo odniesie większe korzyści, jeśli uwzględni zarówno architekturę CIF, jak i MD w projekcie hurtowni danych. Niektóre z metodologii zostały już wdrożone w praktyce i zaakceptowane przez dzisiejsze firmy. Jednak nowe, wymagające metodologie, szczególnie w modelowaniu danych i modelach projektowania fizycznych magazynów danych, takie jak metodologia oparta na metrykach, wymagają dalszych badań i rozwoju.

WSTĘP

W analizie procesu temporalnego mapy Kohonena mogą być wykorzystywane łącznie z algorytmami szeregów czasowych (TS). Wcześniejsze badania miały na celu połączenie algorytmów Kohonena i modeli przełączania Markowa w celu zasugerowania periodyzacji międzynarodowego bimetalizmu w XIX wieku . Niniejsze badania opierały się na analizie ekonomicznej międzynarodowego systemu monetarnego panującego w tym czasie w Europie, który łączył trzy strefy monetarne: system oparty na standardzie złota, z centrum w Londynie, system bimetaliczny, z centrum w Paryżu, oraz system oparty na standardzie srebra, z centrum w Hamburgu . Trzy główne centra finansowe tego systemu (Londyn, Paryż i Hamburg, stąd używana dalej nazwa LPH) były połączone poprzez operacje arbitrażowe między rynkami złota i srebra a rynkami walutowymi zlokalizowanymi w tych centrach. Ponieważ dwa metale, złoto i srebro, pełniły w tym systemie funkcję standardów monetarnych, system ten funkcjonował jako międzynarodowy bimetalizm. Jego rosnąca integracja w ciągu półwiecza (od 1821 do 1873 roku) znalazła odzwierciedlenie w konwergencji obserwowanych poziomów względnej ceny złota do srebra w Londynie, Paryżu i Hamburgu. Jednak ten proces integracji podlegał różnym zmianom, które można interpretować jako szoki egzogeniczne zakłócające ten proces. Jeden z takich szoków jest szeroko udokumentowany w literaturze: odkrycie nowych kopalni złota w Stanach Zjednoczonych i Australii, które doprowadziło do nagłego spadku ceny złota i srebra na wszystkich rynkach światowych w 1850 roku. Spadek ten nie był wszędzie tej samej wielkości, dlatego też spread między cenami złota i srebra w Londynie, Paryżu i Hamburgu wzrósł, zatrzymując na pewien czas proces integracji systemu. To właśnie nazwiemy załamaniem w tym procesie. Niniejszy artykuł ma na celu zlokalizowanie głównych załamań, które miały miejsce w okresie międzynarodowego bimetalizmu; badanie historyczne mogłoby powiązać je ze szczególnymi wydarzeniami, które działały jako szoki egzogeniczne na ten system. Zastosowanym wskaźnikiem integracji jest spread między najwyższą a najniższą ceną złota i srebra w Londynie, Paryżu i Hamburgu. Do badania tej integracji połączono trzy algorytmy: periodyzacja uzyskana za pomocą algorytmu SOM jest konfrontowana z estymacją dwureżimowego modelu przełączania Markowa, aby uzyskać interpretację zmian reżimu; jednocześnie w całym okresie identyfikowane są punkty zmian, co zapewnia dokładniejszą interpretację tych różnych typów regulacji. W rozdziale 2 podsumowano wyniki uzyskane za pomocą algorytmu SOM w celu rozróżnienia podokresów uzyskanych z wykorzystaniem wszystkich dostępnych danych. Rozdział 3 przedstawia rodzaj zastosowanego modelu oraz wyniki jego estymacji z wykorzystaniem nowego wskaźnika - spreadu obliczonego dla każdego okresu notowań między trzema względnymi cenami złota w srebrze. Podokresy są konfrontowane z dwoma uzyskanymi reżimami i przedstawiane są pewne dowody na związek między reżimem a zmiennością spreadu. Rozdział 4 przedstawia technikę zastosowaną do identyfikacji punktów zmian w procesie temporalnym i uzyskuje się pewne silne rezultaty w zakresie przełamań średniej i wariancji spreadu. Są one interpretowane w kategoriach historii monetarnej, ponieważ niektóre z nich są zupełnie nowe w literaturze z tej dziedziny. W podsumowaniu wskazano dalsze kierunki badań.

PODOKRESY UZYSKANE ZA POMOCĄ ALGORYTMU SOM

Dane

Względne ceny złota w srebrze obliczane są na podstawie cen każdego metalu obserwowanych dwa razy w tygodniu w każdym z trzech ośrodków finansowych: Paryżu, Londynie i Hamburgu (odpowiednio: poa, lgs i hoa), od początku 1821 r. do końca 1860 r. Ten sam typ danych jest dostępny dla kursów walutowych (funt we frankach, funt w markach, marka we frankach: odpowiednio: lpv, hlv i phv). Obserwacja to zestaw dwunastu wartości, dwóch notowań (wtorek i piątek) dla każdej z sześciu zmiennych. Dodano zmienną obliczeniową, aby podkreślić związek między względną ceną metali w Hamburgu a średnim poziomem tej wartości (hpl) w Paryżu i Londynie. W większości przypadków notowania wykazują raczej niewielkie różnice w ciągu danego tygodnia, ale okresy z istotnymi problemami, na przykład Paryż pod koniec lat 40. XIX wieku, można wyraźnie oddzielić od okresów bardziej klasycznych. Po klasyfikacji Kohonena z wykorzystaniem siatki 25 węzłów, zastosowano hierarchiczną klasyfikację rosnącą, aby wygenerować niewielką liczbę makroklas, w tym przypadku 6 makroklas, odpowiadających głównym podokresom. Ta ostatnia klasyfikacja jest tworzona z wektorów kodowych uzyskanych w pierwszym procesie.

Charakterystyka makroklas

Duże ciągi kolejnych tygodni grupowane są w makroklasy, jednak kilka lat jest rozbitych na krótkie okresy, mieszczące się w różnych klasach.

o Klasa 1 składa się z 3 grup lat 1829-30, 1834-38, 1848-49 oraz wielu fragmentów innych lat.
o Klasę 2 można opisać łatwiej, z 3 przedziałami 1832-33, 1842-43 i 1846-47 oraz kilkoma nielicznymi tygodniami z lat 30. XIX wieku.Reprezentują one centralną pozycję, kontrastującą z dobrze zidentyfikowanymi innymi klasami:

o Klasa 3: 2 zestawy obejmujące lata 1824-25 i 1827-28, w których prawie nie brakuje tygodni, co wskazuje na bardzo jednorodny charakter tego podokresu
o Klasa 4: koniec roku 1853 i cały okres 1854-60; ponownie brakuje jedynie niewielkiej liczby tygodni w tym ciągłym podokresie trwającym ponad siedem lat
o Klasa 5: lata 1821-24 i 1826-początek 1827 oraz niewielkie fragmenty lat 1830 i 1832
o Klasa 6: dwa zestawy 1839-41 i 1851-53 Średnie zmiennych użytych do uzyskania klasyfikacji można przedstawić w celu zilustrowania dużych różnic występujących między podokresami. Zmieniające się hierarchie między cenami względnymi są cechą identyfikującą cztery ostatnie makroklasy.

Ponowne uporządkowanie poszczególnych klas według czasu kalendarzowego pozwala na rozróżnienie trzech podokresów: a) lata 20. XIX wieku (klasy 5 i 3, obejmujące lata 1821-1828); b) lata 30. i 40. XIX wieku (klasy 1 i 2, obejmujące lata 1829-1849); c) lata 50. XIX wieku (klasy 6 i 4, obejmujące lata 1851-1860). Jedynie lata 1839-1841 opierają się temu uporządkowaniu, ponieważ należą do klasy 6, podczas gdy powinny znaleźć się w klasach 1 i 2 w stosunku do lat 30. i 40. XIX wieku; pewne wyjaśnienia zostaną zasugerowane w ostatniej sekcji. Rys. 1 przedstawia dwie skontrastowane sytuacje, w których cena złota i srebra jest odpowiednio niska (klasa 4) i wysoka (klasa 5) we wszystkich trzech centrach finansowych. Rys. 2. potwierdza tę opozycję, ponieważ obie klasy są również ostro od siebie oddzielone poziomami kursów walutowych. Lata 1821-23 i 1826 (klasa 5) charakteryzują się niskim kursem marki do franka i wysokimi cenami złota i srebra, przy czym kurs hamburski jest wyższy niż paryski; lata 1854-60 (klasa 4) charakteryzują się wysokim kursem marki do franka i niskimi cenami złota i srebra, przy czym kurs hamburski jest niższy niż paryski. Uwagi te, które odnoszą się odpowiednio również do reszty lat dwudziestych XIX wieku (klasa 3) i reszty lat pięćdziesiątych XIX wieku (klasa 6), są zgodne z analizą historyczną: podczas gdy marka hamburska była zawsze zakotwiczona w srebrze, frank francuski w latach dwudziestych i pięćdziesiątych XIX wieku był zakotwiczony w złocie (w przeciwieństwie do lat trzydziestych i czterdziestych XIX wieku, kiedy był zakotwiczony w srebrze); w takim razie jest rzeczą normalną, że marka traci na wartości w stosunku do franka, gdy srebro traci na wartości w stosunku do złota, i bardziej w Hamburgu niż w Paryżu (jak w klasach 5 i 3), a marka zyskuje na wartości w stosunku do franka, gdy srebro zyskuje na wartości w stosunku do złota, i bardziej w Hamburgu niż w Paryżu (jak w klasach 4 i 6).

MODEL ROZPIĘTOŚCI MIĘDZY NAJWYŻSZĄ A NAJNIŻSZĄ CENĄ ZŁOTA I SREBRA

Autoregresyjny model przełączania Markowa

Kluczowym założeniem jest to, że modelowany szereg czasowy podąża za innym wzorcem lub innym modelem zgodnie z pewnym nieobserwowalnym procesem o skończonych wartościach. Zwykle nieobserwowany proces jest łańcuchem Markowa, którego stany nazywane są "reżimami", podczas gdy obserwowany szereg podąża za liniowym modelem autoregresyjnym, którego współczynniki zależą od bieżącego reżimu. Ujmijmy to w języku matematycznym. Załóżmy, że (yt)t?Z jest obserwowanym szeregiem czasowym, a nieobserwowany proces (xt)t?Z jest dwustanowym łańcuchem Markowa z macierzą przejść



Następnie, zakładając, że y_t zależy od pierwszych l opóźnień czasu, otrzymujemy następujące równanie modelu:



Następnie, zakładając, że yt zależy od pierwszych l opóźnień czasu, otrzymujemy następujące równanie modelu: gdzie dla każdego a ε_t jest standardowym szumem Gaussa. Następnie parametry modelu są

i są one zazwyczaj szacowane poprzez maksymalizację funkcji logarytmu wiarygodności za pomocą algorytmu EM (Expectation - Maximization). Naszą cechą będą obliczone "a posteriori" prawdopodobieństwa warunkowe przynależności do pierwszego lub drugiego reżimu. Rzeczywiście, ponieważ naszym celem jest wyprowadzenie periodyzacji międzynarodowego bimetalizmu, obliczone "a posteriori" stany nieobserwowanego łańcucha Markowa dostarczą naturalnego rozwiązania. Chociaż wyniki uzyskane za pomocą przełączającego modelu Markowa są zazwyczaj satysfakcjonujące pod względem przewidywań, a periodyzacje są interesujące i łatwe do interpretacji, pozostaje problem: jak wybrać liczbę reżimów? W przypadku braku pełnej teoretycznej odpowiedzi, kryteria wyboru "właściwej" liczby reżimów są dość subiektywne ze statystycznego punktu widzenia.

Wyniki

W niniejszym artykule wykorzystano model dwureżimowy do przedstawienia rozrzutu obliczonego na podstawie cen złota i srebra obserwowanych w każdym okresie w trzech miejscach. Macierz przejścia wskazuje na dobre właściwości stabilności:



i nie znaleziono żadnego modelu trójreżimowego o akceptowalnej stabilności. Pierwszy reżim to perceptron wielowarstwowy z jedną warstwą ukrytą, drugi to prosty model liniowy z jednym opóźnieniem. Wykorzystując prawdopodobieństwa obliczone dla każdego reżimu w każdym okresie, interesujące może być zbadanie sześciu uzyskanych podokresów i obserwacja przełączania się między reżimami w tych okresach. W większości przypadków reżim 1 wyjaśnia spread (około 70% całego okresu), ale między podokresami należy zauważyć istotne różnice: Klasy 3 i 4 wyraźnie kontrastują odpowiednio z najwyższą i najniższą zmiennością spreadu, ponieważ są one rządzone odpowiednio przez modele reżimu 2 i reżimu 1. Jak zostanie wyjaśnione później, dalsze badania muszą zostać przeprowadzone z wykorzystaniem bardziej złożonego modelu i bardziej dostosowanego wskaźnika arbitraży rządzących rynkami.

IDENTYFIKACJA PUNKTÓW ZMIANY: GLOBALNA WIZJA DIMETALISTICZNEGO SYSTEMU PŁATNOŚCI

Elementy techniki

Innym podejściem do modelowania zmian reżimu w szeregu czasowym jest wykrywanie punktów zmiany lub załamań. W tym przypadku głównym założeniem jest, że cały szereg jest obserwowany, a punkty zmiany są obliczane "a posteriori". Zatem to podejście nie ma celu predykcyjnego, lecz raczej ma na celu wyjaśnienie szeregu za pomocą procesu stacjonarnego, który wydaje się być dobrze dostosowany do naszego problemu. Matematycznie model można zapisać następująco: rozważmy obserwowany szereg m-wymiarowy y_t = {y_1,t,…,y_m,t)^T, t = 1,...,T i załóżmy, że ulega on nagłej zmianie. Zmiany, których liczba i konfiguracja są nieznane, zachodzą w rozkładzie brzegowym i mogą być w średniej, w wariancji lub zarówno w średniej, jak i w wariancji. Zakładamy, że istnieje liczba całkowita K* i ciąg punktów zmian τ* =τ₁^*,…τ_K^* gdzie τ₀^* < τ₁^* < … < τ_K-1^* < τ_K^* takie, że (μ_k, Σ_k) ≠ (μ_k+1, Σ_k+1) gdzie μ_k = E(Y_t) i Σ_k = Cov(Y_t) = E(Y_t - E(Y_t))(Y_t- E(Y_t))^T, τ^*_k-1+1 ≤ t ≤ τ^*_k Liczbę zmian oraz ich konfigurację oblicza się poprzez minimalizację funkcji kontrastu z karą.

Niektóre wyniki i interpretacja

Zastosowanie tej techniki do spreadu dało 7 punktów zmiany średniej i 4 punkty zmiany średniej i wariancji. Rysunek podsumowuje spread, cztery punkty zmiany (pierwsze 4 zielone linie w kolejności chronologicznej) uzyskanew średniej i wariancji oraz 2 ostatnie punkty zmiany średniej, które odpowiadają znaczącemu załamaniu poziomu ceny złota i srebra, obserwowanemu jednocześnie na trzech pozycjach i odpowiadającemu dużej zmianie w produkcji złota w Stanach Zjednoczonych. Bliższe przyjrzenie się spreadowi między najwyższą a najniższą ceną złota i srebra w Londynie, Hamburgu i Paryżu zwraca uwagę na trzy epizody, z których każdy rozpoczyna się załamaniem, które gwałtownie zwiększa spread, a kończy kolejnym załamaniem, które gwałtownie go zawęża (zielone pionowe linie na rysunku). Wspólną cechą tych epizodów jest powiązanie z szokami wpływającymi na proces integracji systemu LPH, chociaż szoki te mogły być asymetryczne (na początku dotknięte zostało tylko jedno lub dwa centra finansowe) lub symetryczne (wszystkie trzy dotknięte jednocześnie). Pierwszy epizod trwał od 21. tygodnia 1824 r. do 41. tygodnia 1825 r. Gwałtowny początkowy wzrost spreadu można wyjaśnić dwoma przeciwnymi ruchami w Londynie i Hamburgu: z jednej strony, intensywna spekulacja obligacjami południowoamerykańskimi i indyjską bawełną napędzała w Londynie popyt na płatności zagraniczne w srebrze, co skutkowało znacznym wzrostem ceny srebra i odpowiadającym mu spadkiem ceny złota i srebra; z drugiej strony, cena złota wzrosła w Hamburgu, podczas gdy cena srebra pozostała na stałym poziomie, co spotęgowało ogromną różnicę między najwyższą (Hamburg) a najniższą (Londyn) ceną złota i srebra. Ponad rok później nastąpiły ruchy przeciwne: cena złota gwałtownie spadła w Hamburgu, podczas gdy cena srebra w Londynie utrzymywała się na najwyższym poziomie pod wpływem ciągłej spekulacji (co doprowadziło do słynnego kryzysu bankowego w grudniu 1825 r.); w konsekwencji spread gwałtownie się zawęził, co znalazło odzwierciedlenie w załamaniu 41. tygodnia 1825 r. Drugi epizod trwał od 45. tygodnia 1839 r. do 13. tygodnia 1843 r. Rozpoczął się on od próby zjednoczenia przez Prusy licznych niemieckojęzycznych niepodległych państw we wspólnej strefie monetarnej, opartej na standardzie srebra. Ponieważ Bank Hamburski utrzymywał stałą cenę srebra, presja na srebro doprowadziła do spadku ceny złota w Hamburgu, a w konsekwencji jego ceny złota i srebra, w czasie, gdy w Paryżu była ona mniej więcej ustabilizowana. Różnica między najwyższą (Paryż) a najniższą (Hamburg) ceną złota i srebra nagle się powiększyła i przez ponad trzy lata utrzymywała się na poziomie znacznie wyższym niż w ciągu poprzednich 14 lat. Ten epizod zakończył się przełamaniem w 13. tygodniu 1843 roku, kiedy to, po zamortyzowaniu szoku, cena złota i srebra w Hamburgu powróciła do poziomu cen w dwóch pozostałych centrach finansowych. Trzeci epizod trwał od 46. tygodnia 1850 roku do 41. tygodnia 1854 roku. Szok był wówczas symetryczny: Londyn, Paryż i Hamburg zostały dotknięte napływem złota po odkryciu kopalni w Kalifornii i nagłą presją spadkową na światową cenę tego metalu. Zamortyzowanie tego ogromnego szoku zajęło cztery lata, o czym świadczy przełamanie w 41. tygodniu 1854 roku.

WNIOSKI

W tych trzech przypadkach proces integracji systemu LPH, widoczny w spadkowej tendencji spreadu na przestrzeni półwiecza, został zagrożony przez szok: spekulacyjny w 1824 r., instytucjonalny w 1839 r. i technologiczny w 1850 r. Skutki tych szoków zostały jednak zamortyzowane po pewnym czasie dzięki aktywnym operacjom arbitrażowym między trzema centrami finansowymi systemu. Zasadniczo arbitraż ten nie oznaczał wymiany złota na srebro, lecz sprzężenie operacji walutowej (na wekslach) z transportem tylko jednego metalu. W związku z tym w dalszych badaniach należałoby zlokalizować zakłócenia innego wskaźnika integracji: spreadu między reprezentatywną "krajową" ceną złota i srebra a arbitrażową międzynarodową ceną złota i srebra, uwzględniającą kursy walut. Jednocześnie interesujące byłoby pogłębienie modelu przełączania Markowa, próbując uzyskać bardziej kompletne specyfikacje.

WSTĘP

Zastosowanie koncepcji biologicznych do tworzenia nowych modeli w dziedzinie obliczeń nie jest rewolucyjnym pomysłem: nauka stała się już podstawą słynnych modeli sztucznych neuronów, algorytmów genetycznych itd. Komórki organizmu biologicznego są w stanie tworzyć bardzo złożone struktury z unikalnej komórki, zygoty, bez potrzeby scentralizowanego sterowania (Watson J.D. i Crick F.H. 1953). Komórki mogą realizować taki proces dzięki istnieniu ogólnego planu, zakodowanego w DNA, dotyczącego rozwoju i funkcjonowania systemu. Inną interesującą cechą komórek naturalnych jest to, że tworzą one systemy odporne na częściowe awarie: drobne błędy nie powodują globalnego załamania systemu. Wreszcie, tkanki zbudowane z komórek biologicznych charakteryzują się równoległym przetwarzaniem informacji, koordynującym funkcjonowanie tkanek w każdej komórce tworzącej tę tkankę. Wszystkie powyższe cechy są bardzo interesujące z obliczeniowego punktu widzenia. W niniejszym artykule przedstawionoopracowanie modelu, który próbuje naśladować komórki biologiczne i wykorzystać niektóre z ich cech, próbując zaadaptować je do komórek sztucznych. Model ten opiera się na zestawie technik znanych jako sztuczna embriologia lub obliczenia embriologiczne .

WSTĘP

Dziedzina obliczeń ewolucyjnych (EC) dała początek zestawowi modeli zgrupowanych pod nazwą sztucznej embriologii (AE), wprowadzonej po raz pierwszy przez Stanleya i Miikkulainnena. Grupa ta odnosi się do wszystkich modeli, które próbują zastosować pewne cechy biologicznych komórek embrionalnych do komputerowego rozwiązywania problemów, tj. samoorganizacji, odporności na awarie i równoległego przetwarzania informacji. Prace nad AE przedstawiają dwa punkty widzenia. Z jednej strony można znaleźć modele gramatyczne oparte na L-systemach, które stosują podejście odgórne do problemu. Z drugiej strony można znaleźć modele chemiczne oparte na ideach Turinga , które stosują podejście odgórne. W ostatnim przypadku punkt wyjścia tej dziedziny można znaleźć w modelowaniu sieci regulacji genów, przeprowadzonym przez Kauffmanna w 1969 roku . Następnie przeprowadzono szereg prac na tematy takie jak złożone zachowanie generowane przez fakt, że zróżnicowana ekspresja niektórych genów ma kaskadowy wpływ na ekspresję innych. Prace wykonywane przez społeczność naukową można podzielić na dwie główne gałęzie. Bardziej teoretyczna gałąź wykorzystuje emulację zdolności komórkowych, takich jak różnicowanie komórkowe i metabolizm, aby stworzyć model funkcjonujący jak naturalna komórka. Celem niniejszej pracy jest dogłębne zbadanie modelu biologicznego. Bardziej praktyczna gałąź koncentruje się głównie na opracowaniu modelu inspirowanego komórką, który mógłby znaleźć zastosowanie w innych problemach. Zgodnie z tym modelem każda komórka nie tylko posiadałaby informację genetyczną, która koduje ogólną wydajność systemu, ale także działałaby jako procesor komunikujący się z innymi komórkami. Model ten jest stosowany głównie do rozwiązywania prostych problemów przestrzennych 3D, sterowania robotami, kodowania generatywnego w celu tworzenia sztucznych organizmów w symulowanych środowiskach fizycznych i rzeczywistych robotach lub do opracowywania ewolucyjnego projektowania sprzętu i obwodów. Biorąc pod uwagę działanie sieci regulacji genów, najistotniejsze modele to: model Kumara i Bentleya , który wykorzystuje teorię białek fraktalnych Bentleya do obliczania stężenia białka; model Eggenbergera , który wykorzystuje koncepcje różnicowania i ruchu komórkowego do określania połączeń między komórkami; oraz praca Dellaerta i Beera, którzy proponują model wykorzystujący ideę operonów biologicznych do kontrolowania ekspresji modelu, gdzie funkcja przyjmuje matematyczne znaczenie funkcji Boole′a. Wszystkie te modele można uznać za specjalne automaty komórkowe. W automatach komórkowych początkowy zestaw komórek w określonym stanie przekształca się w inny zestaw komórek w różnych stanach, gdy ta sama funkcja przejścia zostanie zastosowana do wszystkich komórek w określonym odstępie czasu, w celu kontrolowania zgodności komunikatów między nimi. Najbardziej znanym przykładem automatów komórkowych jest "Gra w życie" Conwaya, gdzie to zachowanie można doskonale zaobserwować. Podczas gdy koncepcja klasyczna określa reguły zachowania, modele ewolucyjne ustanawiają je poprzez poszukiwanie określonego zachowania. Ta różnica wynika z matematycznego pochodzenia automatów komórkowych, podczas gdy prezentowane tutaj modele opierają się na biologii i embriologii. Modeli tych nie należy mylić z innymi koncepcjami, które mogą wydawać się podobne, takimi jak programowanie ekspresji genów (GEP) . Chociaż GEP koduje rozwiązanie w postaci ciągu, podobnie jak w niniejszej pracy, program rozwiązania jest rozwijany w kształcie drzewa, jak w klasycznym programowaniu genetycznym , które ma niewiele lub nic wspólnego z przedstawionymi modelami.

MODEL SZTUCZNEGO ZARODKA

Komórki systemu biologicznego są głównie determinowane przez nić DNA, geny i białka zawarte w cytoplazmie. DNA to struktura, która przechowuje zakodowaną w genach informację, niezbędną do rozwoju systemu. Geny są aktywowane lub transkrybowane dzięki informacji o kształcie białek, która znajduje się w cytoplazmie i składa się z dwóch głównych części: sekwencji, która identyfikuje białko, które zostanie wygenerowane w przypadku transkrypcji genu, oraz promotora, który identyfikuje białka potrzebne do transkrypcji genu. Innym niezwykłym aspektem genów biologicznych jest różnica między genami konstytutywnymi a genami regulującymi. Te ostatnie są transkrybowane tylko wtedy, gdy obecne są białka zidentyfikowane w części promotorowej. Geny konstytutywne są transkrybowane zawsze, chyba że są hamowane przez obecność białek zidentyfikowanych w części promotorowej, działając wówczas jako opresory genów. W niniejszej pracy podjęto próbę częściowego modelowania tej struktury w celu dopasowania niektórych jej możliwości do modelu obliczeniowego; w ten sposób system miałby strukturę zbliżoną do powyższej, co zostanie szczegółowo omówione w następnej sekcji.

Proponowany model

Opracowano różne warianty modelu w oparciu o koncepcje biologiczne. Proponowany sztuczny system komórkowy opiera się na interakcji sztucznych komórek za pomocą komunikatów zwanych białkami. Komórki te mogą się dzielić, umierać lub generować białka, które będą działać jako komunikaty zarówno dla nich samych, jak i dla sąsiednich komórek. System ma wyrażać globalne zachowanie w kierunku generowania struktur w 2D. Takie zachowanie wynikałoby z informacji zakodowanej w zestawie zmiennych komórki, które - analogicznie do komórek biologicznych - zostaną nazwane genami. Jednym z obiecujących zastosowań, nad którym pracujemy, mogłoby być kompaktowe kodowanie kształtów adaptacyjnych, podobne do działania wzrostu fraktalnego lub kompresji obrazu fraktalnego. Centralnym elementem naszego modelu jest sztuczna komórka. Każda komórka posiada zakodowaną w łańcuchu binarnym informację regulującą jej funkcjonowanie. Zgodnie z analogią biologiczną, łańcuch ten będzie nazywany DNA. Komórka posiada również strukturę do przechowywania i zarządzania białkami wytwarzanymi przez własną komórkę oraz tymi otrzymywanymi z sąsiednich komórek; zgodnie z modelem biologicznym, struktura ta nazywana jest cytoplazmą. DNA sztucznej komórki składa się z jednostek funkcjonalnych zwanych genami. Każdy gen koduje białko lub informację (wytwarzaną przez gen). Struktura genu składa się z czterech części :

•  Sekwencja: łańcuch binarny odpowiadający białku kodującemu gen
•  Promotory: to obszar genu, który wskazuje białka potrzebne do transkrypcji genu.
•  Składnik: ten bit określa, czy gen jest składnikiem, czy regulatorem
•  Procent aktywacji (wartość binarna): procent minimalnego stężenia białek promotorowych w komórce, który powoduje transkrypcję genu.

Innym fundamentalnym elementem odpowiedzialnym za przechowywanie i zarządzanie białkami otrzymywanymi lub produkowanymi przez sztuczną komórkę jest cytoplazma. Przechowywane białka mają określony czas życia, zanim zostaną usunięte. Cytoplazma sprawdza, które i ile białek jest potrzebnych komórce do aktywacji genów DNA i w ten sposób odpowiada na wszystkie wymagania komórkowe dotyczące stężenia danego rodzaju białka. Cytoplazma również wyodrębnia białka ze struktury na wypadek, gdyby były potrzebne do transkrypcji genu.

Funkcja modelu

Funkcjonowanie genów jest determinowane przez ich typ, który może być składowy lub regulujący. Transkrypcja kodowanego białka zachodzi, gdy promotory genów nieskładowych pojawiają się w cytoplazmie komórki z określoną częstotliwością. Z drugiej strony, geny składowe są ekspresjonowane przez wszystkie "cykle", aż do momentu zahamowania ekspresji przez aktualną częstotliwość genów promotorowych.

Procent stężenia białka>= (Odległość+1 * Procent aktywacji

Aktywacja genów regulujących lub hamowanie genów składowych jest osiągane, jeśli spełniony jest warunek wyrażony w równaniu , gdzie Procent stężenia białka reprezentuje stężenie rozpatrywanego białka w cytoplazmie; Odległość oznacza odległość Hamminga między jednym promotorem a rozpatrywanym białkiem; a Procent aktywacji to minimalny procent potrzebny do aktywacji genu zakodowanego w genie. To równanie jest testowane dla każdego promotora i każdego białka. Jeśli warunek jest spełniony dla wszystkich promotorów, dany gen jest transkrybowany. Zgodnie z tym, jeśli promotory genopodobne istnieją w stężeniu wyższym niż stężenie kodowane, mogą również indukować jego transkrypcję, podobnie jak dzieje się to w biologii, zapewniając tym samym modelowi większą elastyczność. Jeśli warunek jest spełniony dla każdego promotora, gen jest aktywowany, a zatem transkrybowany. Po aktywacji jednego z genów mogą nastąpić trzy rzeczy: wygenerowane białko może być przechowywane w cytoplazmie komórki, może być przekazywane sąsiednim komórkom lub może indukować podział komórkowy (mitozę) i/lub śmierć komórkową (apoptozę). Różne zdarzenia w tkance są zarządzane w modelu komórkowym za pomocą "cykli komórkowych". Takie "cykle" będą zawierać wszystkie działania, które mogą być wykonywane przez komórki, ograniczając czasami ich występowanie. "Cykle komórkowe" można opisać następująco:

•  Aktualizacja czasu życia białek w cytoplazmie
•  Weryfikacja statusu życiowego komórki (śmierć komórkowa)
•  Obliczenie genów, które reagują i wykonują specyficzne zachowania, które mogą być z nimi związane
•  Komunikacja między białkami

Wyszukiwanie rozwiązań

Klasyczne podejście EC proponuje wykorzystanie algorytmów genetycznych (GA) do optymalizacji, w tym przypadku, wartości genów DNA (nici binarnych). Każdy osobnik populacji GA będzie reprezentował potencjalną nić DNA do rozwiązania problemu. Aby obliczyć wartość dopasowania dla każdego osobnika w GA lub DNA, nić jest wprowadzana do komórki początkowej lub zygoty. Po symulacji przez określoną liczbę cykli, zawarta informacja jest wyrażana, a cechy powstałej tkanki są oceniane za pomocą różnych kryteriów, w zależności od zamierzonego celu. Kodowanie poszczególnych genów przebiega według struktury podobnej do opisanej na Rysunku 2, gdzie liczba promotorów każdego genu może się różnić, ale biała i niepodzielna sekcja "Procent Aktywacji - Składnik - Sekwencja" (PCS) musi być zawsze obecna. Sekcje PCS określają geny osobnika, a sekcje promotorowe są powiązane z sekcjami PCS, jak pokazano na Rysunku 2.



Poszukiwanie zestawu struktur podobnych do przedstawionych na Rysunku 2 wymagało dostosowania operacji krzyżowania i mutacji GA do tego konkretnego problemu. Ponieważ długość osobników jest zmienna, krzyżowanie musiało zostać przeprowadzone zgodnie z tymi długościami. Po wybraniu osobnika generowany jest losowy procent w celu określenia punktu krzyżowania dla tego osobnika. Po wybraniu sekcji w tej pozycji, punkt krzyżowania jest wybierany dla sekcji wybranej w drugim osobniku macierzystym. Po wykonaniu tej czynności proces wyboru punktu krzyżowania jest powtarzany w drugim wybranym osobniku macierzystym, w tej samej pozycji, co w poprzednim osobniku. Od tego etapu potomkowie są komponowani w tradycyjny sposób, ponieważ są to dwa ciągi bitów. Moglibyśmy wykonać standardową krzyżówkę ciągów bitów, ale wcześniej wspomniane kroki gwarantują, że potomkowie są poprawnymi rozwiązaniami dla transformacji nici DNA. Odnośnie mutacji należy wspomnieć, że typy promotorów lub sekcji PCS są identyfikowane na podstawie wartości pierwszego bitu ciągu. Mając to na uwadze, wraz ze zmienną długością osobników, operacja mutacji musiała zostać dostosowana tak, aby mogła modyfikować nie tylko liczbę tych sekcji, ale także wartość danej sekcji. Prawdopodobieństwo wykonania mutacji jest zazwyczaj niskie, ale tym razem musiało zostać podzielone na trzy możliwe operacje mutacji, które system rozważa. Różne testy dowiodły, że najbardziej odpowiednie wartości dla rozkładu różnych operacji mutacji, po wybraniu pozycji do mutacji, były następujące: dla 20% możliwości dodawany jest fragment (promotor lub PCS); dla kolejnych 20% istniejący fragment jest usuwany; i wreszcie, dla pozostałych 60% możliwości, wartość jednego z bitów sekcji jest losowo zmieniana. To ostatnie może powodować nie tylko zmianę jednej z wartości, ale także zmianę typu sekcji: jeśli bit identyfikujący typ sekcji zostanie zmieniony, informacje o tej sekcji ulegają zmianie. Na przykład, jeśli sekcja promotora zmienia się w sekcję PCS, sekwencja promotora zmienia się w sekwencję genu, a generowane są wartości konstytutywne i procentowe wartości aktywacji. Po osiągnięciu tego poziomu rozwoju i zaprezentowaniu zestawu testowego w, autorzy doszli do wniosku, że wąskim gardłem modelu okazał się rozwój funkcji ewaluacyjnych, ponieważ na każdym nowym rysunku rozwój funkcji był czasochłonny i niemożliwy do ponownego wykorzystania. Aby rozwiązać ten problem, opracowano funkcję oceny zgodnie z koncepcją szablonu korekcyjnego. Z tkanki, która powstaje w wyniku analizy DNA, obliczany jest centroid. Ten punkt stanowiłby środek szablonu rozwiązania, który jest jedynie macierzą wartości boolowskich reprezentującą figurę, do której się dąży. Szablon może być (i zazwyczaj jest) mniejszy niż środowisko programistyczne tkanki, co oznacza, że każda komórka, która nie jest objęta szablonem, będzie przyczyniać się do błędu tkanki o 1,0. Pozostała tkanka, objęta szablonem, wykona operację boolowską NEXOR w celu uzyskania liczby różnic między szablonem a tkanką. Każda różnica przyczynia się do błędu tkanki o 1,0. Rysunek 3 ilustruje zastosowanie tej metody.



Możemy zauważyć, że błąd tej tkanki w stosunku do szablonu wynosi 2, ponieważ wygenerowano komórkę, która nie jest uwzględniona w szablonie, podczas gdy inna komórka, obecna w szablonie, faktycznie brakuje.

PRZYSZŁE TRENDY

Model mógłby również obejmować nowe cechy, takie jak przemieszczanie komórek w ich otoczeniu lub operator specjalizacji, który blokuje fragmenty DNA podczas ekspresji jego komórek potomnych, tak jak dzieje się to w modelu naturalnym. Wreszcie, grupa ta pracuje obecnie nad jednym z możliwych zastosowań tego modelu: jego wykorzystaniem do kompresji obrazu, podobnie jak działa kompresja fraktalna. Kompresja fraktalna przeszukuje parametry formuły fraktalnej, która koduje obraz początkowy. Niniejszy model przeszukuje sekwencję genu, która może skutkować obrazem początkowym. W ten sposób metoda oparta na szablonie, przedstawiona w niniejszym artykule, może być wykorzystana do przeprowadzenia tego wyszukiwania, wykorzystując obraz początkowy jako szablon.

WNIOSKI

Biorąc pod uwagę opracowany tutaj model, możemy stwierdzić, że wykorzystanie pewnych właściwości biologicznych systemów komórkowych jest wykonalne do tworzenia sztucznych struktur, które mogłyby zostać wykorzystane do rozwiązania pewnych problemów obliczeniowych. Niektóre zachowania modelu biologicznego zaobserwowano również w modelu sztucznym: redundancję informacji w DNA, stabilność po osiągnięciu pożądanego kształtu lub zmienność zachowania genów.

WSTĘP

Obrazowanie biomedyczne stanowi praktyczną i koncepcyjną rewolucję w naukach stosowanych ostatnich trzydziestu lat. Dwa podstawowe czynniki umożliwiły ten przełom: rozwój technologiczny sprzętu do gromadzenia szczegółowych informacji o badanym narządzie w coraz mniej inwazyjny sposób; sformułowanie i zastosowanie zaawansowanych narzędzi matematycznych do przetwarzania sygnałów w ramach metodologii o prawdziwie interdyscyplinarnym charakterze. Typowa procedura akwizycji w obrazowaniu biomedycznym wymaga sondowania tkanki biologicznej za pomocą promieniowania emitowanego, odbitego lub transmitowanego. Następnie wprowadza się model matematyczny opisujący proces powstawania obrazu i formułuje metody obliczeniowe do numerycznego rozwiązywania równań modelu. Na koniec do zrekonstruowanych obrazów stosuje się metody oparte na lub inspirowane przez sztuczną inteligencję (AI), takie jak uczenie maszynowe, w celu wydobycia klinicznie przydatnych informacji. Ważnymi zagadnieniami w tej działalności badawczej są wewnętrzna niestabilność numeryczna problemu rekonstrukcji, właściwości konwergencji oraz złożoność obliczeniowa algorytmów przetwarzania obrazu. Zagadnienia te zostaną omówione poniżej na podstawie kilku przykładów o szczególnym znaczeniu w praktyce biomedycznej.

TŁO

Pierwszym przełomem w teorii i praktyce współczesnego obrazowania biomedycznego jest rentgenowska tomografia komputerowa (TK). 11 października 1979 roku Allan Cormack i Godfrey Hounsfield otrzymali Nagrodę Nobla w dziedzinie medycyny za rozwój tomografii wspomaganej komputerowo. W komunikacie prasowym uzasadniającym przyznanie nagrody, Zgromadzenie Noblowskie Instytutu Karolinska napisało, że w tym rewolucyjnym narzędziu diagnostycznym "sygnały […] są przechowywane i analizowane matematycznie w komputerze. Komputer jest zaprogramowany do rekonstrukcji obrazu badanego przekroju poprzecznego poprzez rozwiązanie dużej liczby równań zawierających odpowiadającą im liczbę niewiadomych". Począwszy od tego przełomowego momentu, obrazowanie biomedyczne stanowiło tętniący życiem tygiel praktyki klinicznej, fizyki eksperymentalnej, informatyki i matematyki stosowanej, dostarczając ludzkości licznych nieinwazyjnych i skutecznych narzędzi do wczesnego wykrywania chorób oraz naukowców tworzących płodny i ekscytujący obszar działalności badawczej. Główne metody obrazowania stosowane w biomedycynie można podzielić na dwie rodziny w zależności od rodzaju dostarczanych informacji.

•  Obrazowanie strukturalne: obraz dostarcza informacji o cechach anatomicznych tkanki bez badania metabolizmu organicznego. Modalności strukturalne charakteryzują się zazwyczaj znaczną rozdzielczością przestrzenną, ale są nieskuteczne w rekonstrukcji dynamicznej ewolucji parametrów obrazowania. Oprócz tomografii rentgenowskiej (RTG), innymi przykładami takiego podejścia są mikroskopia fluorescencyjna , tomografia ultradźwiękowa , strukturalne obrazowanie metodą rezonansu magnetycznego (MRI) oraz niektóre rodzaje prototypowych tomografii nieliniowych, takie jak tomografia mikrofalowa , tomografia dyfrakcyjna, tomografia impedancji elektrycznej oraz tomografia optyczna .

•  Obrazowanie funkcjonalne: podczas akwizycji rejestrowanych jest wiele różnych zestawów sygnałów zgodnie z precyzyjnie ustalonym paradygmatem czasowym. Uzyskane obrazy mogą dostarczyć informacji na temat niedoborów metabolicznych i chorób czynnościowych, ale zazwyczaj charakteryzują się niższą (czasem znacznie niższą) rozdzielczością przestrzenną niż obrazowanie anatomiczne. Tomografie emisyjne, takie jak tomografia komputerowa emisyjna pojedynczych fotonów (SPECT) lub pozytonowa tomografia emisyjna (PET) oraz obrazowanie metodą rezonansu magnetycznego w jego funkcjonalnym układzie (fMRI) są przykładami tych dynamicznych technik, wraz z elektroencefalografią i magnetoencefalografią (EEG i MEG) , które odtwarzają aktywność neuronalną w skali milisekundowej i w sposób całkowicie nieinwazyjny.

We wszystkich tych modalnościach obrazowania prawidłowe modelowanie matematyczne problemu obrazowania, sformułowanie algorytmów obliczeniowych do rozwiązania równań modelu oraz zastosowanie algorytmów przetwarzania obrazu do interpretacji danych to kluczowe kroki, które umożliwiają wykorzystanie informacji wizualnej z surowych danych pomiarowych.

GŁÓWNY CEL

Z matematycznego punktu widzenia problem odwrotny syntezy informacji biologicznej w formie wizualnej z zebranego promieniowania charakteryzuje się szczególną patologią. Pojęcie źle postawionego problemu zostało wprowadzone przez Julesa Hadamarda (Hadamard, 1923) w celu wskazania problemów matematycznych, których rozwiązanie nie istnieje dla wszystkich danych, nie jest jednoznaczne lub nie zależy jednoznacznie od danych. W obrazowaniu biomedycznym ta ostatnia cecha ma szczególnie szkodliwe konsekwencje: obecność szumu pomiarowego w surowych danych może powodować znaczne niestabilności numeryczne w rekonstrukcji, gdy stosowane są naiwne podejścia. Większość (jeśli nie wszystkie) problemów obrazowania biomedycznego to źle postawione problemy odwrotne , których rozwiązanie jest trudnym zadaniem matematycznym i często wymaga znacznego nakładu obliczeniowego. Pierwszym krokiem w kierunku rozwiązania jest dokładne modelowanie relacji matematycznej między obrazowanym narządem biologicznym a danymi dostarczonymi przez urządzenie obrazujące. Przy najogólniejszych założeniach równanie modelu jest nieliniowym równaniem całkowym, chociaż w przypadku kilku urządzeń nieliniowe równanie obrazowania można wiarygodnie aproksymować modelem liniowym, w którym jądro całkowe koduje odpowiedź impulsową instrumentu. Taka linearyzacja może być przeprowadzona albo poprzez precyzyjną realizację technologiczną, jak w MRI, gdzie akwizycja jest zaprojektowana w taki sposób, że dane są po prostu transformatą Fouriera obiektu, który ma być obrazowany, albo uzyskana matematycznie, poprzez zastosowanie do równania nieliniowego pewnego rodzaju teorii zaburzeń, jak w tomografii dyfrakcyjnej, której model pochodzi z linearyzacji równania rozpraszania. Drugim krokiem w kierunku rekonstrukcji obrazu jest sformułowanie metod obliczeniowych do redukcji równania modelu. W przypadku liniowych, źle postawionych problemów odwrotnych istnieje dobrze ugruntowana teoria regularyzacji, która osłabia niestabilność numeryczną związaną ze źle postawioną sytuacją, zachowując biologiczną wiarygodność zrekonstruowanego obrazu. Teoria regularyzacji leży u podstaw większości liniowych metod obrazowania, a metody regularyzacji można sformułować zarówno w ujęciu probabilistycznym, jak i deterministycznym. Niestety, w przypadku problemów z obrazowaniem nieliniowym nie istnieje analogiczna, dobrze ugruntowana teoria, która jest często rozwiązywana za pomocą technik "ad hoc". Po zrekonstruowaniu obrazu na podstawie danych należy rozważyć trzeci krok, tj. przetwarzanie zrekonstruowanych obrazów w celu ekstrakcji i interpretacji zawartych w nich informacji. Na tym etapie zazwyczaj rozwiązuje się trzy różne problemy:

•  Detekcja krawędzi . Techniki wizji komputerowej są stosowane w celu wzmocnienia obszarów obrazu, w których intensywność światła gwałtownie się zmienia.
•  Integracja obrazu . W procesie klinicznym wykonuje się kilka zdjęć pacjenta w różnych modalnościach i geometriach. Obrazy te można połączyć w zintegrowany model, odzyskując zmiany w ich geometrii.
•  Segmentacja obrazu . Efekty częściowej objętości powodują, że interfejsy między różnymi tkankami są niezwykle rozmyte, co komplikuje kliniczną interpretację odtworzonych obrazów. Automatyczna procedura podziału obrazu na jednorodne zestawy pikseli oraz klasyfikacji segmentowanych obszarów leży u podstaw każdego oprogramowania do komputerowego wspomagania diagnostyki i terapii (CAD).

Algorytmy sztucznej inteligencji, a przede wszystkim uczenie maszynowe, odgrywają kluczową rolę w rozwiązywaniu tych problemów z przetwarzaniem obrazu. W szczególności, jako dziedzina uczenia maszynowego, rozpoznawanie wzorców zapewnia zaawansowany opis danych, który w obrazowaniu medycznym pozwala na lokalizację guzów i innych patologii, pomiar wymiarów tkanek, wspomaganie chirurgii komputerowej i badanie struktur anatomicznych. Na przykład, nadzorowane metody, takie jak propagacja wsteczna lub wzmacnianie , realizują zadania klasyfikacyjne różnych tkanek na podstawie wiedzy z wcześniej zinterpretowanych obrazów; podczas gdy metody nienadzorowane, takie jak samoorganizujące się mapy (SOM) , klasteryzacja rozmyta i maksymalizacja oczekiwań (EM) , pozwalają na wyciągnięcie wniosków probabilistycznych lub identyfikację struktur klastrowych w zestawach nieoznakowanych obrazów. Z matematycznego punktu widzenia, kilka z tych metod odpowiada raczej heurystycznym przepisom niż rygorystycznie sformułowanym i umotywowanym procedurom. Jednak od ostatniej dekady teoria uczenia statystycznego jawi się jako najlepszy kandydat do ścisłego opisu uczenia maszynowego w ramach analizy funkcjonalnej.

TRENDY PRZYSZŁOŚCI

Wśród głównych celów współczesnego obrazowania biomedycznego wskazujemy na realizację:

•  technik mikroobrazowania, które umożliwiają badanie tkanek biologicznych o rozmiarach mikrometrycznych, zarówno w celach diagnostycznych, jak i badawczych;
•  systemów hybrydowych łączących informacje z różnych modalności, potencjalnie anatomicznych i funkcjonalnych;
•  wysoce nieinwazyjnych narzędzi diagnostycznych, w których unika się nawet niewielkiego dyskomfortu.

Cele te można osiągnąć jedynie poprzez efektywne współdziałanie rozwoju sprzętu i zastosowania innowacyjnych algorytmów przetwarzania obrazu. Na przykład, mikrotomografia próbek biologicznych wymaga wprowadzenia zarówno nowych lamp rentgenowskich do akwizycji danych, jak i metod obliczeniowych w celu redukcji efektów utwardzania wiązki; Informacje elektrofizjologiczne i strukturalne dotyczące mózgu można zebrać, wykonując zapis EEG w ramach skanowania MRI, ale także wykorzystując informacje strukturalne z MRI jako dane wstępne w analizie sygnału EEG przeprowadzanej w warunkach bayesowskich; wreszcie, nieinwazyjność w kolonoskopii można uzyskać, wykorzystując najnowszy projekt akwizycji w tomografii rentgenowskiej wraz z zaawansowanym oprogramowaniem, które umożliwia wirtualną nawigację w jelicie, elektroniczne oczyszczanie i automatyczną klasyfikację tkanek nowotworowych i zdrowych. Z czysto obliczeniowego punktu widzenia, dwa ważne cele uczenia maszynowego stosowanego w obrazowaniu medycznym to opracowanie algorytmów uczenia półnadzorowanego oraz automatyczna integracja danych genetycznych z informacjami pochodzącymi z uzyskanych obrazów.

WNIOSKI

Niektóre aspekty współczesnego obrazowania biomedycznego zostały opisane z perspektywy nauk obliczeniowych. Problem rekonstrukcji obrazu biomedycznego został omówiony jako źle postawiony problem odwrotny, w którym wewnętrzna niestabilność numeryczna powodująca artefakty obrazu może zostać zredukowana poprzez zastosowanie zaawansowanych metod regularyzacji. Opisano rolę przetwarzania obrazu z wykorzystaniem technik uczenia maszynowego oraz główne cele najnowszych zastosowań obrazowania biomedycznego.

WSTĘP

W ostatnich latach pojęcie systemów złożonych okazało się bardzo użyteczną koncepcją do definiowania, opisywania i badania różnorodnych zjawisk naturalnych obserwowanych w wielu dyscyplinach naukowych. Przykłady dyscyplin naukowych, które w dużym stopniu korzystają z tej koncepcji, obejmują fizykę, matematykę i informatykę, poprzez biologię i medycynę, a także ekonomię, po nauki społeczne i psychologię. Opracowano różne techniki opisu zjawisk naturalnych obserwowanych w tych systemach złożonych. Należą do nich sztuczne życie, obliczenia ewolucyjne, inteligencja roju, sieci neuronowe, obliczenia równoległe, automaty komórkowe i wiele innych. W tym tekście skupiamy się na jednej z nich, tj. "automatach komórkowych". Przedstawiamy prawdziwie dyskretny wszechświat modelowania, dyskretny w czasie, przestrzeni i stanie: automaty komórkowe (CA) . Warto podkreślić znaczenie automatów kombinowanych w rozwiązywaniu pewnych klas problemów, których nie da się rozwiązać innymi technikami. Automaty kombinowane, pomimo swojej prostoty, potrafią opisać i odtworzyć wiele złożonych zjawisk, ściśle związanych z procesami takimi jak samoorganizacja i emergencja, często obserwowanymi w wyżej wymienionych dyscyplinach naukowych.

WSTĘP

Krótko wyjaśniamy koncepcję systemów złożonych i automatów komórkowych oraz podajemy odnośniki do szeregu istotnych publikacji z tej dziedziny.

Systemy złożone

Koncepcja systemów złożonych (CS) pojawiła się jednocześnie, a często niezależnie, w różnych dyscyplinach naukowych . Można to interpretować jako dowód ich uniwersalności. Pomimo różnorodności tych dziedzin, wszystkie systemy złożone mają wiele wspólnych cech. Zazwyczaj system złożony składa się z ogromnej liczby prostych i lokalnie działających części, które wzajemnie na siebie oddziałują i generują globalną, złożoną reakcję. Samoorganizacja i wyłanianie się, często obserwowane w systemach złożonych, są napędzane przez rozpraszanie energii i/lub informacji. Samoorganizację można łatwo wyjaśnić za pomocą badań nad zachowaniem kolonii mrówek, gdzie ogromna liczba identycznych procesów, zwanych mrówkami, oddziałuje lokalnie poprzez kontakt fizyczny lub za pomocą śladów oznaczonych feromonami. Nie ma lidera, który dostarczałby każdej mrówce informacji lub instrukcji, co powinna zrobić. Pomimo braku takiego lidera lub hierarchii liderów, mrówki są w stanie budować złożone kolonie mrówek, karmić swoje larwy, chronić kolonię, walczyć z innymi koloniami itd. Wszystko to odbywa się automatycznie poprzez zestaw prostych, lokalnych interakcji między mrówkami. Powszechnie wiadomo, że mrówki reagują na każdy bodziec jedną z 20 do 40 (w zależności od gatunku mrówek) reakcji, co wystarcza do uzyskania obserwowanej złożoności. Emergencja jest definiowana jako występowanie nowych procesów działających na wyższym poziomie abstrakcji niż poziom, na którym działają lokalne reguły. Każdy poziom zazwyczaj ma swoje własne lokalne reguły, różniące się od reguł działających na innych poziomach. Emergencja, podobnie jak kolonia mrówek, jest produktem procesu emergencji. Może istnieć cała hierarchia emergentów, np. jak w ciele człowieka, składająca się z substancji chemicznych i DNA, przechodząca przez polipeptydy, białka, infrastruktury komórkowe i cykle, a dalej do komórek i tkanek, narządów i ciał. Widzimy, że samoorganizacja i emergencja są często ściśle ze sobą powiązane.

Automaty komórkowe

Wczesny rozwój automatów komórkowe sięga czasów A. Turinga, S. Ulama i J. von Neumanna. Automaty komórkowe można zdefiniować za pomocą czterech wzajemnie zależnych elementów: sieci i jej zmiennych, sąsiedztwa oraz reguł lokalnych . Poniżej pokrótce wyjaśniono to zagadnienie.

Kraty i sieci

Kratę tworzy siatka elementów, z przyczyn historycznych zwanych komórkami, które mogą być złożone w przestrzeni jedno-, dwu-, trój- lub wielowymiarowej. Sieć zazwyczaj składa się z jednorodnych komórek, takich jak na przykład kwadraty, sześciokąty lub trójkąty w dwóch wymiarach. Sieci CA działające na sieciach i grafach stanowią uogólnienie klasycznych sieci CA, które działają na regularnych sieciach. Sieci mogą być losowe lub regularne. Sieci mogą mieć różne topologie, które są klasyfikowane według stopnia regularności i losowości. Sieć komórek można interpretować jako regularną sieć wierzchołków połączonych krawędziami. Gdy porzucimy tę regularność i dopuścimy pewnych losowych sąsiadów, a dokładniej, jeśli większa część sieci jest regularna, a mniejsza jej część jest losowa, wówczas wkraczamy w domenę sieci małego świata. Idea sieci małego świata dostarcza unikalnego narzędzia, które pozwala nam uchwycić wiele istotnych właściwości zjawisk obserwowanych naturalnie, zwłaszcza tych związanych z sieciami społecznymi i, co zaskakujące, z sieciami (metabolicznymi i innymi) działającymi w żywych komórkach. Podczas gdy sieci małego świata są mieszanką sieci regularnych i losowych, sieci czysto losowe mają zupełnie inny zakres zastosowania. Warto wspomnieć o koncepcji sieci bezskalowych, których łączność nie jest już zależna od skali

Zmienne

Kreatywne struktury odniesienia (CA) zawierają dowolną liczbę zmiennych dyskretnych. Ich liczba i zakres zależą od badanego zjawiska. Najprostsze struktury odniesienia (CA) są budowane przy użyciu tylko jednej zmiennej boolowskiej w jednym wymiarze (1D), patrz np. (Wolfram, 2002). Niektóre z takich prostych jednowymiarowych struktur odniesienia (CA) charakteryzują się nawet wysoką złożonością i wykazują zdolność do uniwersalnych obliczeń.

Otoczenia

Otoczenie, które służy do oceny reguły lokalnej, jest definiowane przez zbiór sąsiednich komórek, w tym samą zaktualizowaną komórkę w przypadku sieci regularnych, rys. 1. Sąsiedzi o współrzędnych względnych [i, j+1], [i-1, j], [i, j-1], [i+1, j] zaktualizowanej komórki [i, j] i znajdujący się odpowiednio na północy, zachodzie, południu i wschodzie definiują tzw. otoczenie von Neumanna o promieniu r = 1. Sąsiedztwo Moore′a o promieniu r = 1 zawiera te same komórki co sąsiedztwo von Neumanna oraz komórki diagonalne zlokalizowane w pozycjach względnych [i-1, j+1], [i-1, j-1], [i+1, j-1], [i+1, j+1], [i+1, j+1], tj. odpowiednio północno-zachodnie, południowo-zachodnie, południowo-wschodnie i północno-wschodnie. Istnieje wiele innych możliwych typów sąsiedztw; sąsiedztwa mogą być nawet nierównomierne przestrzennie lub czasowo. Jednym z przykładów jest sąsiedztwo Margolusa, wykorzystywane w modelowaniu dyfuzji. Granice dla każdego CA mogą być stałe, odbijające lub okresowe. Okresowe warunki brzegowe reprezentują nieskończone sieci. Okresowość oznacza, że np. w jednym wymiarze, najbardziej prawa komórka sieci jest połączona z najbardziej lewą komórką sieci. Stałe komórki brzegowe są utrzymywane na predefiniowanych wartościach. Odbijające komórki brzegowe odbijają wartości z powrotem do głównej części sieci.

Reguły lokalne

Reguła lokalna definiuje ewolucję każdego CA. Zwykle: Realizuje się to poprzez pobranie wszystkich zmiennych ze wszystkich komórek w sąsiedztwie i obliczenie zestawu operacji logicznych i/lub arytmetycznych zapisanych w formie algorytmu. Wektor s tych zmiennych jest aktualizowany zgodnie z następującą regułą lokalną w przypadku sąsiedztwa von Neumanna: s[i,j] = f(s[i,j+1], s[i-1,j], s[i,j-1], s[i+1,j]), gdzie i reprezentuje współrzędną x, j reprezentuje współrzędną y komórki, a f regułę lokalną. Zaktualizowana komórka ma współrzędne [i,j]. Rysunek przedstawia dwuwymiarowy układ współrzędnych 5x5 z sąsiedztwami o różnych promieniach.



Modelowanie

Modelowanie obliczeniowe definiuje się jako matematyczny, numeryczny i/lub obliczeniowy opis zjawiska obserwowanego w naturze. Jest ono niezbędne w sytuacjach, gdy obserwowane zjawiska nie są możliwe do uchwycenia metodami analitycznymi. Wyniki są często weryfikowane w odniesieniu do rozwiązań analitycznych w szczególnych lub uproszczonych przypadkach. Jego znaczenie zostało udowodnione w fizyce i chemii i stale rośnie w nowych dziedzinach, takich jak biologia, medycyna, socjologia i psychologia.

MODELOWANIE SYSTEMÓW ZŁOŻONYCH ZA POMOCĄ AUTOMATÓW KOMÓRKOWYCH

Ciągle napływa wiele nowych pomysłów i podejść wzbogacających metodę CA. W ramach modelowania złożonych systemów CA istnieją odrębne nurty badań i ich zastosowania w różnych dyscyplinach, które zostaną pokrótce omówione w tej sekcji. Klasyczne automaty komórkowe, z regularną siecią komórek, są wykorzystywane do modelowania materiałów ferromagnetycznych i antyferromagnetycznych, krzepnięcia, rekrystalizacji statycznej i dynamicznej, dynamiki laserów, przepływu ruchu, ucieczek i zachowań pieszych, procesów głosowania, samoreplikacji, samoorganizacji, trzęsień ziemi, aktywności wulkanicznej, bezpiecznego kodowania informacji i kryptografii, układów odpornościowych, zachowania żywych komórek i tkanek, rozwoju morfologicznego, ekosystemów i wielu innych zjawisk naturalnych . Automaty CA zostały po raz pierwszy wykorzystane w modelowaniu ośrodków pobudliwych, takich jak tkanka serca. Metoda CA często przewyższa inne metody, takie jak np. metoda Monte Carlo, szczególnie w przypadku układów o wysokiej dyssypalności. Głównym powodem, dla którego metody CA stanowią najlepszy wybór w modelowaniu wielu naturalnie obserwowanych złożonych zjawisk, jest to, że są one definiowane powyżej światów w pełni dyskretyzowanych czasoprzestrzennie. Wrodzone właściwości CA wnoszą nowe jakości do modeli, które nie są zasadniczo osiągalne za pomocą innych technik obliczeniowych. Przykładem zaawansowanej metody CA jest metoda kratowa Boltzmanna, składająca się z trójkątnej sieci wierzchołków połączonych krawędziami, w których uogólnione "cząstki cieczy" poruszają się i zderzają zgodnie z tabelą zderzeń. Tworzony jest model gazu, w którym wymuszane jest zachowanie masy, pędu i energii podczas zderzeń, co daje w pełni dyskretną i uproszczoną, a jednocześnie fizycznie poprawną mikrodynamikę. Działając w odpowiednich granicach, metody te odtwarzają równania Naviera-Stokesa dla nieściśliwych układów i dlatego stanowią model dynamiki płynów. Uśrednione wielkości wynikające z takich symulacji odpowiadają rozwiązaniom równań Naviera-Stokesa. Klasyczne automaty komórkowe, wykorzystujące sieci, mają wiele zalet w porównaniu z innymi podejściami, ale należy wspomnieć o kilku znanych wadach. Jedną z wad automatów technologicznych może być użycie zmiennych dyskretnych. To ograniczenie jest przez niektórych autorów usuwane poprzez zastosowanie zmiennych ciągłych, co prowadzi do uogólnionych automatów technologicznych. Największą wadą klasycznych automatów technologicznych jest często ograniczona topologia sieci. Klasyczne regularne sieci nie odtwarzają właściwości wielu naturalnie obserwowanych zjawisk. To doprowadziło do następującego rozwoju automatów technologicznych. Uogólnione automaty komórkowe, jak opisali Darabos, Giacobini i Tomassini , są zbudowane na ogólnych sieciach, które są reprezentowane przez regularne, losowe, bezskalowe sieci lub sieci małego świata. Z klasycznego CA i jego kratownicy można utworzyć regularną sieć, w której każda komórka reprezentuje węzeł, a każdy sąsiad jest połączony krawędzią. Losowy graf powstaje z węzłów, które mają losowo wybrane węzły jako sąsiadów. W sieciach bezskalowych niektóre węzły są silnie połączone z innymi punktami, podczas gdy inne są mniej połączone. Ich właściwości są niezależne od ich rozmiaru. Rozkład stopnia połączeń w węźle podlega zależności potęgowej P(k) = k-γ, gdzie P(k) jest prawdopodobieństwem, że węzeł jest połączony z k innymi węzłami. Współczynnik γ w większości przypadków mieści się w przedziale od 2 do 3. Sieci te występują na przykład w Internecie, w sieciach społecznościowych oraz w sieciach wytwarzanych biologicznie, takich jak sieci regulacji genów w żywych komórkach lub łańcuchy pokarmowe w ekosystemach. Ogólnie rzecz biorąc, zachowanie danego CA jest nieprzewidywalne, co jest często wykorzystywane w kryptografii. Istnieje wiele technik statystycznych, pozwalających na badanie zachowania danego CA, ale żadna z nich nie jest dokładna. Najprostszym, a często jedynym, sposobem na sprawdzenie stanu CA jest jego wykonanie.

STUDIA PRZYPADKÓW

Zrozumienie wzrostu morfologicznego i rozgałęzień koralowców twardych za pomocą metody sieci Boltzmanna jest dobrym przykładem badania naturalnych systemów złożonych z udziałem alg. Głębokie zrozumienie tych procesów jest ważne dla oceny roli koralowców w ekosystemach morskich i np. ich związku z globalnymi zmianami klimatu. Symulacja wzrostu i rozgałęzień koralowca obejmuje procesy wielofizyczne, takie jak dyfuzja składników odżywczych, przepływ płynów, absorpcja światła przez zooksantele żyjące w symbiozie z polipami koralowca, a także stres mechaniczny. Wykazano, że gradienty składników odżywczych determinują morfogenezę rozgałęzień koralowców fototropowych. W tym konkretnym przypadku mamy do czynienia z procesami ograniczonymi dyfuzją, które w pełni determinują kształt morfologiczny rosnących koralowców. Z eksperymentów w zbiornikach i badań symulacyjnych wiadomo, że te obszary dominujące w dyfuzji działają przy stosunkowo dużych prędkościach przepływu. Wykazano, że symulowane morfologie koralowców są nieodróżnialne od rzeczywistych . Modelowanie dynamicznej rekrystalizacji stanowi kolejne praktyczne zastosowanie rekrystalizacji w dziedzinie fizyki ciała stałego . Metale o postaci polikrystalicznej, złożone z wielu monokryształów, ulegają odkształceniu w podwyższonych temperaturach. Zmagazynowana energia wzrasta z powodu odkształcenia, które z kolei jest uwalniane przez rekrystalizację, gdzie zarodki rosną i tworzą nowe ziarna. Wzrost jest napędzany uwalnianiem zmagazynowanej energii. Reakcja odkształconego materiału polikrystalicznego znajduje odzwierciedlenie w złożonych zmianach mikrostruktury i krzywej odkształcenia. Krzywe naprężenie-odkształcenie mierzone podczas odkształcania próbek metalicznych wykazują zachowanie pojedynczego lub wielu pików. Ta złożona reakcja odkształconego materiału jest bezpośrednim rezultatem współbieżnych procesów zachodzących w odkształconym materiale. Modelowanie CA stanowi jak dotąd jedyną technikę obliczeniową, która jest w stanie opisać tak złożone zachowanie materiału

PRZYSZŁE TRENDY

W badaniach nad modelowaniem CA istnieje wiele odrębnych ścieżek, charakteryzujących się ciągłym napływem nowych odkryć . Modele CA służą do modelowania zjawisk fizycznych, ale coraz częściej wykorzystuje się je do modelowania zjawisk biologicznych, medycznych i społecznych. Większość modeli CA jest projektowana ręcznie, ale przyszłość wymaga opracowania automatycznych i samoregulujących się technik optymalizacji w celu projektowania lokalnych reguł zgodnie z potrzebami opisywanych zjawisk naturalnych. Na koniec warto podkreślić, że CA reprezentują metodę generyczną, często wykorzystywaną w rozwoju prototypów zupełnie nowych metod numerycznych opisujących zjawiska obserwowane w naturze. Wierzymy, że CA mają ogromny potencjał dla przyszłego rozwoju modelowania obliczeniowego i zrozumienia dynamiki złożonych systemów.

WSTĘP

Systemy biologiczne można postrzegać jako systemy zarządzania informacją, z podstawowym zestawem instrukcji przechowywanym w DNA każdej komórki jako "geny". W przypadku większości genów ich informacje są włączane, gdy są one transkrybowane do RNA, które jest następnie tłumaczone na białka, które tworzą znaczną część maszynerii komórki. Chociaż szczegóły procesu dla poszczególnych genów są znane, bardziej złożone interakcje między elementami nie zostały jeszcze odkryte. Wiemy, że choroby mogą być wynikiem zmian w samych genach, w kodowanych przez nie białkach lub jeśli RNA lub białka są wytwarzane w niewłaściwym czasie lub w niewłaściwych ilościach. Ostatnie postępy w biotechnologii doprowadziły do opracowania mikromacierzy DNA, które ilościowo mierzą ekspresję tysięcy genów jednocześnie i dostarczają migawkę reakcji komórki na konkretny stan. Znalezienie wzorców ekspresji genów, które dostarczają wglądu w biologiczne punkty końcowe, oferuje ogromne możliwości zrewolucjonizowania diagnostyki i medycyny prognostycznej oraz zapewnienia mechanistycznego wglądu w badania oparte na danych w naukach o życiu, obszarze, w którym istnieje duże zapotrzebowanie na postęp, biorąc pod uwagę pilność związaną z chorobami. Jednak analiza danych z mikromacierzy stwarza szereg wyzwań, od zaszumionych danych po przekleństwo wymiarowości (duża liczba cech, mała liczba wystąpień) po problemy bez jasnych rozwiązań (np. mapowania genów w świecie rzeczywistym na cechy lub choroby, które nie są jeszcze znane). Znalezienie wzorców ekspresji genów w danych z mikromacierzy stwarza problemy związane z odkrywaniem klas, porównywaniem, przewidywaniem i analizą sieci, do których często podchodzi się za pomocą metod sztucznej inteligencji. Wiele z tych metod zostało pomyślnie zastosowanych do analizy danych z mikromacierzy w różnych zastosowaniach, od grupowania wzorców ekspresji genów drożdży po klasyfikację różnych typów białaczki. Metody uczenia się bez nadzoru (np. klasteryzacja hierarchiczna) eksplorują klastry w danych i były używane do odkrywania klas odrębnych form rozlanego chłoniaka z dużych komórek B. Metody uczenia się bez nadzoru (np. sztuczne sieci neuronowe) wykorzystują wcześniej określone mapowanie między próbkami biologicznymi i klasami (tj. etykietami) w celu generowania modeli do przewidywania klas. Podejście k-najbliższych sąsiadów (k-NN) zostało użyte do trenowania klasyfikatora ekspresji genów różnych form guzów mózgu, a jego przewidywania były w stanie odróżnić próbki biopsji o różnym rokowaniu, co sugeruje, że profile mikromacierzy mogą przewidywać wynik kliniczny i kierować leczeniem. Sieci bayesowskie zbudowane z danych mikromacierzy rokują nadzieję na wyjaśnienie podstawowych mechanizmów biologicznych choroby

KONTEKST

Komórki dynamicznie reagują na swoje środowisko, zmieniając zestaw i stężenia aktywnych genów poprzez zmianę powiązanej ekspresji RNA. Tak więc "ekspresja genu" jest jednym z głównych czynników determinujących stan komórki lub fenotyp. Na przykład możemy zbadać różnice między komórką normalną a komórką nowotworową, badając ich względne profile ekspresji genów. Mikromacierze określają ilościowo poziomy ekspresji genów w różnych warunkach (takich jak choroba vs. normalna) lub w różnych punktach czasowych. Dla n genów i m wystąpień (próbek biologicznych) pomiary mikromacierzy są przechowywane w macierzy n na m, gdzie każdy wiersz jest genem, każda kolumna jest próbką, a każdy element w macierzy jest poziomem ekspresji genu w próbce biologicznej, gdzie próbki są wystąpieniami, a geny są cechami opisującymi te wystąpienia. Dane z mikromacierzy są dostępne w wielu publicznych repozytoriach online. Ponadto repozytorium Kent-Ridge zawiera wstępnie sformatowane dane gotowe do użycia w znanym narzędziu do uczenia maszynowego Weka. Dane z mikromacierzy stwarzają pewne wyjątkowe wyzwania dla AI, takie jak poważny przypadek klątwy wymiarowości z powodu niedoboru próbek biologicznych (instancji). Badania z mikromacierzy zazwyczaj mierzą dziesiątki tysięcy genów w zaledwie dziesiątkach próbek. Ten niski stosunek przypadków do zmiennych zwiększa ryzyko wykrycia fałszywych relacji. Problem ten jest zaostrzony, ponieważ dane z mikromacierzy zawierają wiele źródeł zmienności wewnątrzklasowej, zarówno technicznych, jak i biologicznych. Wysoki poziom wariancji i mała wielkość próby utrudniają wybór cech. Testowanie tysięcy genów stwarza problem wielokrotnego testowania, co może skutkować niedoszacowaniem liczby fałszywie pozytywnych wyników. Biorąc pod uwagę dane z tymi ograniczeniami, konstruowanie modeli staje się niedookreślone i w związku z tym podatne na nadmierne dopasowanie. Z biologii jasno wynika również, że geny nie działają niezależnie. Geny oddziałują na siebie w formie ścieżek lub sieci regulacji genów. Z tego powodu potrzebujemy modeli, które można interpretować w kontekście ścieżek. Naukowcy z powodzeniem zastosowali metody AI do wstępnego przetwarzania danych z mikromacierzy, grupowania, wyboru cech, klasyfikacji i analizy sieci.

GÓRNICTWO DANYCH Z MIKROMACIERZY: AKTUALNE TECHNIKI, WYZWANIA I MOŻLIWOŚCI DLA PRZETWARZANIA WSTĘPNEGO DANYCH AI

Po uzyskaniu danych z mikromacierzy przeprowadzana jest normalizacja w celu uwzględnienia systematycznych błędów pomiaru i ułatwienia porównań między próbkami. Dane z mikromacierzy mogą zawierać brakujące wartości, które mogą zostać zastąpione przez zastąpienie średniej lub imputację k-NN.

Selekcja cech

Celem selekcji cech jest znalezienie genów (cech), które najlepiej odróżniają grupy instancji (np. choroba vs. normalność), aby zmniejszyć wymiarowość zbioru danych. Kilka metod statystycznych, w tym test t, analiza istotności mikromacierzy (SAM) i analiza wariancji (ANOVA) zostało zastosowanych do selekcji cech z danych z mikromacierzy. W eksperymentach klasyfikacyjnych metody selekcji cech mają na celu zazwyczaj identyfikację odpowiednich podzbiorów genów w celu skonstruowania klasyfikatora o dobrej wydajności. Cechy są uważane za istotne, gdy mogą wpłynąć na klasę; silnie istotne są niezbędne do przewidywania, a słabo istotne mogą tylko czasami przyczyniać się do przewidywania. Metody filtrowania oceniają podzbiory cech niezależnie od zastosowanego konkretnego algorytmu uczenia się. Omówione powyżej metody statystyczne do selekcji cech, a także rankery, takie jak rankery zysku informacji, są filtrami dla cech, które mają zostać uwzględnione. Metody te ignorują fakt, że mogą istnieć redundantne cechy (cechy, które są silnie skorelowane ze sobą i jako takie mogą być użyte do zastąpienia innych), a zatem nie starają się znaleźć zestawu cech, który mógłby działać podobnie przy mniejszej liczbie zmiennych, zachowując jednocześnie tę samą moc predykcyjną. Z tego powodu metody wielowymiarowe są bardziej odpowiednie. Alternatywnie, wrappery traktują algorytm uczenia się jako czarną skrzynkę i wykorzystują dokładność przewidywania do oceny podzbiorów cech. Wrappery są bardziej bezpośrednie niż metody filtrów, ale zależą od konkretnego użytego algorytmu uczenia się. Złożoność obliczeniowa związana z wrapperami jest zaporowa z powodu klątwy wymiarowości, więc zazwyczaj filtry są używane z selekcją do przodu (rozpoczynając od pustego zestawu i dodając cechy pojedynczo) zamiast eliminacji wstecznej (rozpoczynając od wszystkich cech i usuwając je pojedynczo). Podejścia redukcji wymiarów są również używane do wielowymiarowej selekcji cech

Podejścia do redukcji wymiarów

Analiza głównych składowych (PCA) jest szeroko stosowana do redukcji wymiarów w uczeniu maszynowym . Idea stojąca za PCA jest dość intuicyjna: skorelowane obiekty można łączyć w celu zmniejszenia "wymiarowości" danych. Relacje między profilami ekspresji genów w macierzy danych można wyrazić jako kombinację liniową, tak aby zmienne współliniowe były regresowane do nowego zestawu współrzędnych. PCA, jej podstawowa metoda Single Value Decomposition (SVD), powiązane podejścia, takie jak analiza korespondencji (COA) i skalowanie wielowymiarowe (MDS), zostały zastosowane do danych z mikromacierzy i zostały omówione przez Brazmę i Culhane′a . Badania wykazały, że COA lub inne podejścia do redukcji wymiarów z podwójnym skalowaniem, takie jak analiza mapy widmowej, mogą być bardziej odpowiednie niż PCA do dekompozycji danych z mikromacierzy. Podczas gdy PCA bierze pod uwagę wariancję całego zestawu danych, podejścia klastrowania badają odległość parami między instancjami lub cechami. Dlatego te metody są komplementarne i często obie są stosowane w eksploracyjnej analizie danych. Jednak trudności w interpretacji wyników w kategoriach dyskretnych genów ograniczają zastosowanie tych metod.

Klastrowanie

To, co postrzegamy jako jedną chorobę, jest często zbiorem podtypów chorób. Odkrywanie klas ma na celu odkrycie tych podtypów poprzez znalezienie grup przypadków o podobnych wzorcach ekspresji. Klastrowanie hierarchiczne jest metodą aglomeracyjną, która zaczyna się od pojedynczego przypadku i grupuje podobne punkty danych przy użyciu pewnej miary odległości, tak aby dwa najbardziej podobne punkty danych były grupowane razem w klaster, czyniąc je dziećmi węzła nadrzędnego w drzewie. Proces ten jest powtarzany w sposób oddolny, aż wszystkie punkty danych będą należały do jednego klastra (odpowiadającego korzeniowi drzewa). Hierarchiczne i inne podejścia do klasteryzacji, w tym K-means, zostały zastosowane do danych z mikromacierzy. Klastrowanie hierarchiczne zostało zastosowane do badania ekspresji genów w próbkach od pacjentów z rozlanym chłoniakiem z dużych komórek B (DLBCL), co doprowadziło do odkrycia dwóch podtypów choroby. Grupy te zostały znalezione poprzez analizę danych z mikromacierzy z próbek biopsji pacjentów, którzy nie byli wcześniej leczeni. Ci pacjenci byli nadal badani po chemioterapii, a naukowcy odkryli, że dwa nowo odkryte podtypy choroby miały różne wskaźniki przeżywalności, co potwierdza hipotezę, że podtypy miały znacząco różne patologie (Alizadeh i in., 2000). Podczas gdy klasteryzacja po prostu grupuje dane na podstawie odległości parami, gdy informacje są znane a priori na temat niektórych lub wszystkich danych, tj. etykiet, można zastosować podejście nadzorowane w celu uzyskania klasyfikatora, który może przewidzieć etykietę nowych przypadków.

Klasyfikacja (uczenie nadzorowane)

Duża wymiarowość danych z mikromacierzy oznacza, że wszystkie metody klasyfikacji są podatne na nadmierne dopasowanie. Do danych z mikromacierzy zastosowano kilka nadzorowanych podejść, w tym sztuczne sieci neuronowe (ANN), maszyny wektorów nośnych (SVM) i k-NN. Bardzo trudnym i klinicznie istotnym problemem jest dokładna diagnoza pierwotnego pochodzenia guzów przerzutowych. Bloom i inni zastosowali ANN do danych z mikromacierzy 21 typów guzów z dokładnością 88%, aby przewidzieć pierwotne miejsce pochodzenia nowotworów przerzutowych o nieznanym pochodzeniu. Klasyfikacja na poziomie 84% została uzyskana w niezależnym zestawie testowym, co ma ważne implikacje dla diagnozowania pochodzenia raka i kierowania terapią. W porównaniu różnych podejść SVM, wielokategorialne SVM okazały się skuteczniejsze od innych popularnych algorytmów uczenia maszynowego, takich jak k-NN i ANN , gdy zastosowano je do 11 publicznie dostępnych zestawów danych mikromacierzy związanych z rakiem. Warto zauważyć, że wybór cech może znacząco poprawić wydajność klasyfikacji.

Walidacja krzyżowa

Walidacja krzyżowa (CV) jest odpowiednia w badaniach mikromacierzowych, które są często ograniczone liczbą wystąpień (np. próbek pacjentów). W k-krotnym CV zbiór treningowy jest dzielony na k podzbiorów o równej wielkości. W każdej iteracji k-1 podzbiorów jest używanych do treningu, a jeden podzbiór jest używany do testowania. Ten proces jest powtarzany k razy, a średnia dokładność jest raportowana. Niestety, niektóre opublikowane badania stosowały CV tylko częściowo, stosując CV do tworzenia reguły predykcji, wykluczając jednocześnie wybór cech. Wprowadza to stronniczość w szacowanych współczynnikach błędów i przecenia dokładność klasyfikacji. W rezultacie wyniki wielu badań są kontrowersyjne ze względu na wady metodologiczne. Dlatego modele muszą być ostrożnie oceniane, aby zapobiec stronniczości wyboru. Zalecane jest zagnieżdżone CV, z wewnętrzną pętlą CV do wykonywania strojenia parametrów i zewnętrzną CV do obliczania szacunkowego błędu. Kilka badań, które badały podobne problemy biologiczne, wykazało słabe nakładanie się sygnatur ekspresji genów. Brenton i inni porównali dwie listy genów przewidujące rokowanie raka piersi i znaleźli tylko 3 wspólne geny. Mimo że przecięcie się określonych list genów jest słabe, wysoce skorelowana natura danych z mikromacierzy oznacza, że wiele list genów może mieć podobną dokładność przewidywania. Wykazano, że sygnatury genów zidentyfikowane w różnych badaniach nad rakiem piersi z niewielką liczbą wspólnych genów mają porównywalny sukces w przewidywaniu przeżycia pacjentów. Powszechnie stosowane algorytmy uczenia nadzorowanego dają modele czarnej skrzynki, co powoduje potrzebę interpretowalnych modeli, które dostarczają wglądu w podstawowy mechanizm biologiczny, który wytworzył dane.

Analiza sieci

Sieci bayesowskie (BN), wywodzące się z sojuszu teorii grafów i teorii prawdopodobieństwa, mogą uchwycić zależności między wieloma zmiennymi . Friedman i inni wprowadzili wielomianowy model ramowy dla BN w celu inżynierii wstecznej sieci i pokazali, że ta metoda różni się od klasteryzacji tym, że może odkryć interakcje genów inne niż korelacja, gdy jest stosowana do danych ekspresji genów drożdży. Spirtes i inni podkreślają niektóre trudności związane ze stosowaniem tego podejścia do danych z mikromacierzy. Niemniej jednak zbadano wiele rozszerzeń tego kierunku badań. Korelacja nie jest koniecznie dobrym predyktorem interakcji, a słabe interakcje są niezbędne do zrozumienia postępu choroby. Identyfikacja biologicznie znaczących interakcji od pozornych jest trudna, a BN są szczególnie dobrze przystosowane do modelowania stochastycznych procesów biologicznych. Wykładniczy wzrost danych generowanych przez technologię mikromacierzy, a także innych danych o wysokiej przepustowości (np. interakcji białko-białko), wymaga nowych podejść do sztucznej inteligencji, ponieważ paradygmat nauk o życiu zmienia się z redukcjonistycznego na mechanistyczny, skupiający się na systemach.

PRZYSZŁE TRENDY

Odkrycie podstawowych mechanizmów biologicznych, które generują te dane, jest trudniejsze niż przewidywanie i może mieć daleko idące implikacje dla zrozumienia etiologii chorób. Analiza szeregów czasowych (Bar-Joseph, 2004) jest pierwszym krokiem do zrozumienia dynamiki regulacji genów, ale ostatecznie musimy wykorzystać tę technologię nie tylko do obserwacji danych dotyczących ekspresji genów, ale także do kierowania eksperymentami interwencyjnymi i opracowania metod badania podstawowego problemu odróżniania korelacji od związku przyczynowo-skutkowego.

WNIOSEK

Przeanalizowaliśmy metody sztucznej inteligencji do wstępnego przetwarzania, klastrowania, wyboru cech, klasyfikacji i analizy mechanistycznej danych z mikromacierzy. Klastry, listy genów, odciski palców molekularnych i hipotezy sieciowe wytworzone przez te podejścia wykazały już wpływ; od odkrywania nowych podtypów chorób i markerów biologicznych, przewidywania wyników klinicznych w celu ukierunkowania leczenia, a także rozwikłania sieci genów. Z perspektywy sztucznej inteligencji dziedzina ta stwarza trudne problemy i może mieć ogromny wpływ na biologię i medycynę.