TISEAN.NET. Algorytm wyliczania entropii wzajemnej

 

 

TISEAN.NET wkracza wkracza coraz bardziej w fazę konkretnej implementacji. Dlatego też chciałbym aby mi towarzyszyło

 Motto

„Gdybym się pomylił, poprawcie mnie”.

Intuicja.

Aby dobrze zrozumieć algorytm stworzony przez kogoś nie wystarczy odtworzyć mechanizm go tworzący przenosząc go do nowego języka programowania. Trzeba nabyć intuicję, która pozwala go w pełni zrozumieć.

Algorytm estymacji informacji względnej szeregów czasowych.

Weźmy dowolny próbkowany szereg czasowy.

Zadajmy sobie pytanie: czy można zbudować zestaw wektorów składający się z wartości opóźnionych szeregu, który w możliwie najlepszy sposób przybliży charakter zachowań szeregu X(t).

Jest taka metoda i nazywana jest metodą opóźnień (method of delays). Wektory w nowej przestrzeni zwanej przestrzenią osadzoną (embedding space) są zbudowane z wartości skalarnych

 

 

 

 

 

 

Liczba m jest nazywana wymiarem osadzenia (embedding dimension), czas t jest nazywany opóźnieniem (delay)

 

I tu się nasuwa pytanie. Co to znaczy w możliwie najlepszy sposób? To oznacza, że powinniśmy znaleźć miarę, która będzie dobrym kryterium wyboru. Powołując się na dokumentację do projektu Tisean 3.0.1 będącego pierwowzorem mojego projektu można wybrać miarę którą jest opisana w odnośniku [1]. Opiera się ona na klasycznej definicji entropii Shannona jako mierze nieokreśloności informacji zawartej w sygnale. Zanim dojdziemy do wzoru opisującego tę miarę pokażmy sobie ideę algorytmu.

Niech nasz szereg czasowy wygląda następująco:

W następnym kroku powinniśmy znormalizować zakres zmienności szeregu X(t) do przedziału [0,1].

Teraz wykonamy sztuczkę i pomnożymy wartości funkcji przez – na przykład 5 (jest to parametr Nmber of boxes z poprzedniej niotki serii TISEAN.NET) – obetniemy z wyniku wartości po przecinku. Teraz nasz wykres wygląda tak:

Dodatkowo pomalowaliśmy różnymi kolorami wartości szeregu przyjmujące te same wartości. Te kolory to „pudełka”, do których wpadają nasze przekształcone wartości szeregu czasowego. Sumując ilości kolorowych punktów otrzymujemy ilość wpadających do określonych pudełek. Dlatego też ten algorytm zwany jest jako „box count”.

Z rysunku widać, że ilości wpadające do poszczególnych pudełek są następujące:

b[0] = 4

b[1] = 0

b[2] = 1

b[3] = 9

b[4] = 28

b[5] = 6

Suma wszystkich ilości w każdym z pudełek daje ogólną ilość wszystkich wartości naszego szeregu czasowego. Nasuwa to nam intuicję, że dzieląc ilości w poszczególnych pudełkach otrzymamy prawdopodobieństwa, że dana wartość wpadanie do określonego pudełka.

I teraz zasadnicza część algorytmu.

Wybierzmy sobie wartość opóźnienia. Opóźnienie w przypadku naszego szeregu może mieć wartość od 1 do 48 (nasz szereg ma 49 punktów).

Dla większej czytelności wybierzmy nasze opóźnienie Ƭ= 4.

Otrzymamy dwa szeregi czasowe. Jeden zaczynający się od czasu t = 5, drugi od czasu t=1. W następnym kroku będzie to czas t= 6 dla jednego szeregu czasowego a dla drugiego 2, następnie t = 7 dla jednego i t = 3 dla drugiego. I w ostateczności otrzymamy wartość dla t=49 dla jednego szeregu i wartość drugiego szeregu dl t = 45. W kolejnych krokach będzie to wyglądała jak na obrazkach (czerwona kreska oznacza bieżącą oś czasu szeregu zwykłego z zielona szeregu opóźnionego).

 

Nazwijmy oba szeregi następująco: X_n(t) dla szeregu normalnego i X_d(t) dla szeregu opóźnionego.

 

 Widzimy tutaj, że w tym kroku szereg X_n(t) zaliczył swoją wartość do pudełka b[2], podczas gdy szereg X_d(t) zaliczył swoja wartość do pudełka b[3]. Oba szeregi w tym kroku zaliczyły swoje wartości jednocześnie do pudełek b[2,3].

 

W tym kroku szereg X_n(t) zaliczył swoją wartość do pudełka b[0], podczas gdy szereg X_d(t) zaliczył swoja wartość do pudełka b[3]. Oba szeregi w tym kroku zaliczyły swoje wartości jednocześnie do pudełek b[0,3].

 

 W tym kroku szereg X_n(t) zaliczył swoją wartość do pudełka b[4], podczas gdy szereg X_d(t) zaliczył swoja wartość do pudełka b[3]. Oba szeregi w tym korku zaliczyły swoje wartości jednocześnie do pudełek b[4,3].

 

 

.

.

.

 

 

I w ostatnim kroku szereg X_n(t) zaliczył swoją wartość do pudełka b[4], podczas gdy szereg X_d(t) zaliczył swoja wartość do pudełka b[4]. Oba szeregi w tym korku zaliczyły swoje wartości jednocześnie do pudełek b[4,4].

 

Przechodząc przez wszystkie punkty po kolei otrzymamy dla obu szeregów ilości wartości w poszczególnych pudełkach oraz ilości wartości wpadających do obu pudełek jednocześnie w tym samym kroku. Dzieląc te ilości przez całkowitą ilość punktów odwiedzanych w tym układzie otrzymamy prawdopodobieństwa, że dla danego szeregu osiągnął on określoną wartość. Podobnie dla drugiego szeregu. Natomiast dzieląc ilość w pudełkach wzajemnych z ilościami wzajemnie występującymi otrzymamy prawdopodobieństwa warunkowe, że jeżeli szereg X_n(t) przyjął jedną z wartości to szereg X_d(t) przyjął inną wartość.

 

Mając teraz intuicję jak działa ten algorytm możemy podać miarę entropii wzajemnej obu szeregów czasowych:

 

 

Gdzie:

 

P_i – jest prawdopodobieństwem, że szereg szereguX_n(t) przyjmie wartość i

P_j – jest prawdopodobieństwem, że szereg szereguX_d(t) przyjmie wartość j

P_ij - jest prawdopodobieństwem, że jeżeli w szereguX_n(t) wystąpiła wartość i to w szeregu X_d(t) wystąpiła w tym samym czasie wartość j.

 

Stosując tak zdefiniowany algorytm i powyższą miarę możemy zobaczyć jakie są wyniki obliczeń programu TISEAN.NET dla Maximum time delay równe 128:

Widać z tego wykresu, że od pewnych wielkości opóźnień nie poprawia sie już wielkość miary. Można więc przyjąć, że wymiar m dla danych gładkich wynosi około 36 a dla danych poszarpanych około 29. I takich wymiarów będą ich wektory w przestrzeni osadzonej. Jak budować takie wektory jak zwykle w następnych odcinkach serii TISEAN.NET.

 

Krytyczne głosy wsparte dobrą wolą mile widziane.

 

Link do poprzedniej notki z tej serii: http://marekpow.salon24.pl/456998,tisean-net-organizacja-danych-wejsciowych

 

Literatura:

[1] A. M. Fraser and H. L. Swinney, Independent coordinates for strange attractors from mutual information, Phys. Rev. A 33, 1134 (1986).