Algorytm GP vs TE

Porównanie algorytmu Grassbegera-Proccacia i Takensa-Ellnera

Pierwszym popularnym algorytmem wyznaczającym złożoność wymiarową był algorytm Grassbergera-Proccacia. Algorytm ten jest stosunkowo prosty i intuicyjny i prawidłowo estymuje złożoność wymiarową dla sygnałów o niskiej i, do pewnego stopnia, średniej złożoności wymiarowej.

Najpierw wyznaczany jest histogram odległości pomiędzy punktami w przestrzeni fazowej. Nastepnie wyznaczana jest suma kumulacyjna histogramu. Suma ta jest następnie przedstawiana w skali logarytmicznej. Suma kumulatywna tworzy w początkowym odcinku linię prostą, której nachylenie (współczynnik kierunkowy, tangens a) oznacza złożoność wymiarową. (Analogicznie, jesli weźmiemy wielomian y=x4, to wykres tego wielomianu w skali logarytmicznej będzie prostą o współczynniku kierunkowym  a=4.)

Jeśli liczba par punktów, których wzajemna odległość jest mniejsza od r, przyrasta przykładowo z czwartą potęgą odległości r, to złożoność tego sygnału wynosi 4. Np. dla odległości r=0.2 znajdziemy 100 par punktów o odległości mniejszej niż r=0.2 a dla r=0.4 znajdziemy 1600 par punktów o odległości mniejszej niż r=0.4 to złożoność wynosi 4, gdyż liczba par punktów przyroszła 16x, podczas gdy odległość tylko 2x. 24=16, więc złożoność wynosi 4.

Gdy przygotowujemy histogram, duża liczba odległości tworzy jeden punkt wykresu histogramu odległości, a liczba odległości wrasta wykładniczo dla kolejnych punktów histogramu. Np. jesli badamy sygnał o złożoności d=8, liczba odległości dla kolejnych punktów histogramu jest proporcjonalna do :

18, 28, 38, 48, 58,,,,. i8. Można wyliczyć, że  aby uzyskać odcinek skalowania liniowego o długości tylko 10 punktów, liczba odległości tworzących odcinek skalowania liniowego musi wynosić minimum 108.

Ponadto, trzeba zauważyć, że odcinek skalowania liniowego dla sygnałów wysokowymiarowych jest widoczny dla bardzo krótkiego początkowego fragmentu całki korelacyjnej rzędu Pmax=10-3. Oznacza to że w celu wyznaczenia  złożoności równej 8, trzeba by wyliczyć 108/10-3 =1011 odległości. Jeśli byśmy natomiast chcieli uzyskać odcinek skalowania liniowego składający się z 20 punktów, liczba odległości musiałaby wynosić 208/10-3 = 2.56*1013. Ta prosta symulacja pokazuje, że estymacja złożoności wymiarowej przy użyciu tego algorytmu dla sygnałów wysokowymiarowych jest praktycznie niemożliwa.

Jesli chodzi o różnicę pomiędzy algorytmem GP i Takensa-Ellnera (TE) , TE  wykorzystuje każdą odległość do wyznaczenia złożoności wymiarowej, nie ma grupowania dużej liczby odległości w jeden punkt histogramu. 10 punktów histogramu odpowiada ~108 odległości.

Wykres wektora z odległościami w funkcji indeksu wektora dla wzorcowego sygnału o złożoności d=~8. Osie X i Y zostały zamienione miejscami. Skala logarytmiczna. Uzyskujemy klasyczną całkę korelacyjną z obszarem skalowania liniowego o współczynniku kieruynkowym d = ~8.

Pochodne wykresów powyżej. Obszar skalowania liniowego jest prostą poziomą  o wartości ok 8.

Wektor z odległościami budowany w algorytmie TE może być łatwo przetransformowany do całki korelacyjnej budowanej w algortmie GP. Wykres 1 pokazuje przykładowe wartości wektora d z odległościami w funkcji indeksu wektora I w skali logarytmicznej, z tą drobną zmianą, że osie X i Y zostały zamienione miejscami a indeksy zostały przetrasformowane do względnych indeksów P = I / length(d). Wartość idneksu I odpowiada sumie kumulatywnej odległości, które sa równe lub mniejsze niż dI. Tak więc wykres ten przedstawia typową całkę korelacyjną z algorytmu GP z tą różnicą, że wszystkie odległości między punktami tworzą tę relację. Można więc zastosować dalsze kroki algorytmu w celu wyliczenia złożoności sygnału, z tą różnicą, że liczba odległości które trzeba wyznaczyć jest o kilka rzędów wielkości mniejsza. Oba algorytmy korzystają z tego samego obszaru całki korelacyjnej, a kluczowym punktem jest właściwy dobór obszaru skalowania liniowego reprezentowany przez przedział Imin-Imax (indeksy bezwzględne posortowanego wektora z odległosciami) lub Pmin-Pmax (bardziej uniwersalne indeksy względne).

Pritchard  i Duke sugerowali, że  algorytmy GP i TE korzystają z innych obszarów całki korelacyjnej, co spowodowało dużo zamieszania i być może porzucenie zainteresowania tym obszarem teorii chaosu przez wielu badaczy, spowodowane niezrozumieniem problemu. Ta błędna konkluzja wynikała prawdopdobnie z informacji podanej przez autorów algorytmu TE, że powienien on korzystać z zakresu całki korelacyjnej Pmin-Pmax = 0.02-0.22. Ten wzięty empirycznie dla sygnałów niskowymiarowych przedział jest całkowicie nieodpowiedni dla sygnałów średnio- i wysokowymiarowych.

Algorytm TE wylicza złożoność przy pomocy nieintuicyjnego  zbioru równań:

      d (i) -  posortowany rosnąco wektor z odległościami między punktami w przestrzeni fazowej

       D = Imax - Imin  =   liczba analizowanych odległości

                for i=0 to D-1:       y(i) = ln( d(Imax) ) - ln( d(Imin+ i) )             

               Y = sum(y(i))

          d = D / [ Y +   Imin* y(0) ]

Dokładna analiza tych równań pokazuje, że algorytm TE jest po prostu innym sposobem estymacji pochyłości odcinka skalowania liniowego na wykresie całki korelacyjnej, bazującym na posortowanym wektorze z odległościami d (i) między punktami w przestrzeni fazowej.

Zastosowanie algorytmu Takensa Ellnera jako bazy dla wyznaczania złożoności wymiarowej jest więc oczywiste, ze względu na jego ZNACZNIE szybszy czas obliczeń. Konieczne było jedynie jego dopasowanie do potrzeb analizy wysokowymiarowej.