Reconstructia atractorului sursei

de semnal

Procesarea Semnalelor – Curs 8

de semnal

De ce reconstructia atractorului?

• Primul pas pentru predictia neliniara a

semnalelor.

• Folosit in algoritmi de predictie de ultima

generatie (McNames (2002), Hanias & Karrasgeneratie (McNames (2002), Hanias & Karras

(2007))

• Utilizat si de alte metode: retele neuronale,

metode kernel, metode nonparametrice, etc.

Predictie in haos – model general

1) Determinam m - dimensiunea spatiului fazelor in

care se gaseste atractorul unui sistem haotic

determinist (sursa de semnal), plecand doar de la

esantioane ale unui semnal y[n].

Predictie in haos – model general

2) O data gasit acest spatiu (minimum embedding

phase space), se reconstruieste traiectoria sursei de

semnal pentru toate momentele de timp pentru care

avem esantioane y[n] (slide 7)

Predictie in haos – model general

3) Utilizand traiectoria reconstruita in acest spatiu,

pentru orice observatie noua facem extrapolari ale

urmatorului segment de traiectorie din phase space,

revenim in R si obtinem predictia semnalului cu un pas

inainte.

Predictie in haos – algoritm general

y[0]…, y[N]

esantioane in R

False Nearest

Neighbours

m = minimum embedding

dimension

Minimum Delay

Embedding Phase esantioane in R

Embedding Phase

Space = R^m

Predictie in R^m

Delay embedding in R^m

(= reconstructia

traiectoriei sursei de

semnal)

y [N+1]estimat

revenire

in R

Elemente introductive

• Delay embedding de dimensiune m:

Pentru un esantion finit de semnal y[n],n=0…N:

Y[i] = (y[i], y[i-1], …., y[i-(m-1)]) pentru orice

i=m-1…Ni=m-1…N

Operatia de mai sus se numeste m-dimensional

delay embedding.

Y[m-1], Y[m],..,Y[N-1]: traiectoria sursei de semnal

in delay embedding phase space de dimensiune m.

False Nearest Neighbours

• Idee: plecand de la un esantion finit de semnaly[n], n=0…N:– De gasit cea mai mica dimensiune m astfel incat delay

embedding-ul de dimensiune m sa contina topologiaatractorului sursei de semnal.

Se bazeaza pe teorema lui Takens:Se bazeaza pe teorema lui Takens:

- m este cel mai mic numar intreg astfel incat m > 2dA , unde dA este dimensiunea fractala a atractorului.

– Orice delay embedding de dimensiune mai mare sauegala cu m incorporeaza intreaga topologie aatractorului.

– Dorim m pentru a avea un spatiu de dimensiuneminima.

False Nearest NeighboursParametri: Rtol (default 10), Atol (default 2), f_limit (default 0.1%)

m=2

REPETA

1. Calculeaza Y[i], i=m-1…N-1 cf. slide-ului 7 pentru m curent.

2. Calculeaza Y’[i], i=m…,N-1 cf. slide-ului 7 pentru m+1

3. Calculeaza fractia f a perechilor de puncte Y[i], Y[i_nearest] cele

mai apropiate care satisfac relatia:

unde Rm(i) = dist(Y[i], Y[i_nearest])

(distanta euclideana)

Rm+1(i) = dist(Y’[i], Y’[i_nearest])

4. m=m+1

PANA CAND f<f_limit;

return (m-1);

//de ce m-1 ? Daca f=0 si seria de timp are zgomot, MED = ultimul m unde

f>f_limit, chiar daca alegem si f_limit=0. Zgomotul afecteaza minimum

embedding dimension in sensul ca pentru criteriul f=0 zgomotul creste artificial

masuratoarea lui MED. De aceea se utilizeaza f_limit.

Care este ideea ?

• 2 vecini apropiati intr-o proiectie nu mai sunt

apropiati daca se mareste cu 1 numarul de

dimensiuni.

Exemplu

Daca ii gasim

Nearest Neighbours

In acest embedding

2D…..si marim m la 3,

uitandu-ne din alt unghi

in 3D phase space, nu

mai sunt apropiati !

Ideea False Nearest Neighbours

• La un moment dat numarul de perechi care se

‘desfac’ prin acest procedeu scade sub un

prag.

• Cand algoritmul se opreste, inseamna ca am‘desfacut’ suficient spatiul prin delayembedding incat cuprinde intreg atractorul.

• Efectul este ca traiectoriile nu se mai auto-intersecteaza (nu exista ‘noduri’ in haos).intersecteaza (nu exista ‘noduri’ in haos).

• f_tol = 0.1% sau mai jos pentru situatiile candin semnal exista zgomot si exista auto-intersectii artificiale ale orbitelor (false nearestneighbours).

Ce concluzii se desprind ?

• Gasind m cu False Nearest Neighbours, putem

rationa despre dimensiunea fractala a

atractorului dA.

• dA este in intervalul [(m-1)/2, m/2)• dA este in intervalul [(m-1)/2, m/2)

• Cu m determinat, calculam Y[i] cf. slide-ului 7

• Pentru i=m-1..N-2, fiecarei observatii

Y[i] = (y[i], y[i-1], …., y[i-(m-1)]) ii atasam

observatia (eticheta) yDesired = y[i+1]-y[i]

Algoritmul False Nearest Neighbours

• Utilizat de Pavdilis, Tasoulis (2003) ca prim pas in predictia

cursului valutar, utilizand template-ul din slide-ul 6.

� Pavdilis, Tasoulis - articol disponibil la:

http://neuron.ro/PS/Documentatie%20implementare%20proi

ecte/ReconstructiaAtractorului_MinimumEmbeddingDimensiecte/ReconstructiaAtractorului_MinimumEmbeddingDimensi

on.pdf

� Implementare pe platforma MetaTrader 4 la:

http://neuron.ro/PS/Documentatie%20implementare%20proi

ecte/FalseNearestNeighbours.mq4

Atentie: implementarea nu include si criteriul cu Atol

Abordarea experimentala

• m (minimum embedding dimension) se poatedetermina si experimental:– Crestem m de la 2 la M_MAX, astfel:

– La fiecare iteratie:• calculam toti Y[i] in m-dim delay embedding si atasam

fiecarui Y[i] label-ul y[i+1]-y[i]

• Generam seturi de date (Y[i], y[i+1]-y[i]) cu Y[i] intrari, y[i+1]-• Generam seturi de date (Y[i], y[i+1]-y[i]) cu Y[i] intrari, y[i+1]-y[i] iesiri dorite

• Folosim jumatate din ei sa antrenam o retea neuronala

• Masuram MSE (Mean Squared Error) – eroarea patraticamedie de predictie

- Alegem m pentru care eroarea este minima

- Abordarea este folosita in literatura de unii autori, insa nu esteriguroasa

- Tema de proiect propusa impune implementarea algoritmuluiFalse Nearest Neighbours

Predictie in haos – algoritm general

y[0]…, y[N]False Nearest

Neighbours

m = minimum embedding

dimension

Minimum Delay

Embedding Phase

Discutate in acest curs

Embedding Phase

Space = R^m

Predictie in R^m

Delay embedding in in

R^m (= reconstructia

traiectoriei sursei de

semnal)

y [N+1]estimat

revenire

in R

Mai multe despre delay embedding• Din Y[i] , i=m-1,..N-1 se obtin traiectoriile sistemului in

phase space (vederi 2D sau 3D ale atractorului):

• Oricare 2 sau 3 componente ale punctelor Y[i] folosite ca

axe produc sectiuni 2D sau 3D prin spatiul fazelor.

Sectiuni prin phase space

• Daca atractorul are dimensiunea fractala dA,

False Nearest Neighbours gaseste m astfel

incat m > 2dA

• Cu m determinat, avem:• Cu m determinat, avem:

in care stim ca observam un atractor cu

dimensiune fractala dA in intervalul

[ (m-1)/2, m/2)

In realitate…

• In realitate y[n] – semnalul analizat este alterat de

zgomot.

• De aceea in realitate sursa de semnal este un sistem

haotic determinist cu zgomot:

Y[n+1] = f(Y[n]) + zgomot (medie 0, dev.std. σ)

(Y[n] – notatia din slide-ul 7)(Y[n] – notatia din slide-ul 7)

• Doar nivelul de zgomot impiedica in viata reala

predictiile ideale.

• Zgomot = variatie neexplicabila doar cu teoria haosului

pe baza observatiilor uni-variate y[n].

• Limiteaza performanta ORICARUI predictor (retele

neuronale, metode non-parametrice, alg. bazati pe teoria

haosului, etc.).

Signal-to-noise ratio (SNR)

• Marime care determina in ce masura

componenta determinista f(Y[n]) a unui

semnal ‘mascheaza’ componenta de zgomot:

SNR in haos

• Cum masuram SNR in haos ?

• Ideal, SNR = 20log10(RMS(f(Y[n])) / σ) , valori mediimasurate intr-o vecinatate B(Y[n],r) (bila de centru Y[n]si raza r) din phase space.

• Experimental, SNR = 20log10(RMS(prediction(Y[n])) /RMS(eroare absoluta)), pentru orice predictor cu functiede predictie prediction cu m intrari reale.

⇒SNR in decibeli, dependent de pozitia in phase space!

⇒Nivelul de zgomot poate varia in phase space

⇒Subiect de cercetare

Principii generale legate de predictie

• Predictia seriilor de timp are sens doar in

portiuni din phase space unde SNR este peste

o valoare de prag dependenta de criteriile

minime de precizie dorita

• Valabil indiferent de metoda de predictie:

– Retele neuronale

– Metode kernel

– Algoritmii pe care ii vom studia

– Regresie liniara, etc.

Principii generale legate de predictie

• Daca functia predictor nu tine cont de pozitia

curenta in phase space, performanta

predictorului poate fi sever afectata.

• Daca functia predictor nu tine cont de SNR• Daca functia predictor nu tine cont de SNR

local in jurul pozitiei curente din phase space,

performanta predictorului poate fi sever

afectata.

• Geometria campului vectorial depinde de

pozitia in phase space (divergenta, rotor).

Principii generale legate de predictie

• Urmand aceste principii intr-o forma sau alta,

se poate detecta haos determinist chiar si in

nivele foarte mari de zgomot, unde alte

metode esueaza.metode esueaza.

• Literatura de specialitate sugereaza acest

lucru.

Preliminarii pentru predictia neliniara

– Preprocesarea semnalelor nestationare:

• Inainte de predictie, semnalele nestationare sediferentiaza:

– z[n] = y[n]-y[n-1], n=0…N

– Se aplica False Nearest Neighbours pe z[n]Se aplica False Nearest Neighbours pe z[n]

– Se prezice z[n+1]-z[n]

– Alinierea traiectoriilor:

• 2 segmente de traiectorie (Y[i],Y[i+1]) si (Y[j],Y[j+1]) suntaliniate daca unghiul dintre cei 2 vectori este mai micde X grade (X se alege cel mult 90 grade). Se folosesteprodusul scalar in R^m.

• Un fascicul de traiectorii este aliniat daca oricare 2 cate2 sunt aliniate.

Preliminarii pentru predictia neliniara

• Campul vectorial se poate schimba in timp !

�Atractorul isi poate schimba forma si locatia.

�In aceasta situatie se foloseste predictieadaptiva (L.J. Cao, R. Tay, 2002)adaptiva (L.J. Cao, R. Tay, 2002)

http://portal.acm.org/citation.cfm?id=607854

Nota: acest slide informativ nu intra in materia

de examen

Anexa: Dimensiunea Fractala

• Exista mai multe masuri

• Cea mai des utilizata in teorie: Box-CountingDimension (Minkovski – Bouligand):

• Utilizata in R^n : la limita, log(numarul decuburi de latura ε necesare pentru a acoperimultimea S) (presupusa atractor) impartit lalog(1/ ε)