La Predizione
In questo capitolo viene presentato brevemente il problema della predizione di un processo aleatorio e viene data la formula della metrica usata come parametro di bontà per i predittori nei capitoli successivi. In seguito, dopo una breve introduzione sui processi caotici e sulle loro caratteristiche, vengono discusse le proprietà di self-similarity e long-range dependence e la loro implicazione nella predicibilità di un processo. Quindi vengono illustrate le tecniche di predizione più utilizzate basate su modelli non lineari, con particolare attenzione ai processi costituiti dal traffico di rete. Infine viene data una panoramica sulle tecniche di predizione standard.
2.1 Problema
della
predizione
In molte applicazioni, tipicamente nelle operazioni di controllo, compressione dati e allocazione delle risorse, è di grande utilità poter predire, con un certo anticipo e con la massima accuratezza, il valore che assumerà un processo in un determinato istante futuro. Si parla di predizione ad r passi, per indicare l’intervallo temporale, rispetto all’ultimo dato disponibile, del campione che si vuole predire (Figura 2.1). Risulta intuitivo che quanto più lontano è l’istante di predizione, tanto maggiore risulterà l’errore commesso.
Figura 2.1 – Modello di predizione
Si consideri dunque il problema di stimare, conoscendo i campioni fino al passo n-r, il valore del segnale al passo n. Questo problema è noto come predizione ottima ad r passi e consiste nel determinare lo stimatore ottimo del processo, che utilizzando tutti i campioni disponibili da -∞ a n-r, fornisca una predizione che minimizzi il valore della metrica utilizzata come parametro di bontà del predittore stesso. Se come criterio di ottimalità viene scelta la minimizzazione dell’errore quadratico medio si parla di predizione ottima in media quadratica. La scelta della metrica da ottimizzare risulta dal compromesso tra accuratezza del predittore e facilità di trattazione matematica [1].
x(n) x n n rˆ( | − )
2.2 Metriche per la qualità delle predizioni
Per quantificare la bontà di un predittore P che, dato un insieme di N osservazioni x(n)=[x(n), x(n-1), … , x(n-N+1)], restituisca la predizione x(n+1)=P(x(n)), introduciamo la metrica chiamata predictor error σ2( )P definita come:
1 2 2( ) lim 1 1 N M ( 1) ˆ( 1) M n N P x n x n M V σ + + →∞ = =
∑
+ − + (2.1)dove V è il fattore di normalizzazione:
2 1 1 1 1 lim M ( ) lim M ( ) M M m m V x m x m M M →∞ = →∞ = = −
∑
∑
(2.2)Valori di σ2( )P vicini a 0 indicano buone prestazioni del
predittore mentre prestazioni sempre peggiori si hanno al tendere di σ2( )P ad 1. Un valore di σ2( )P molto vicino a
zero, implica che il valore predetto sia quasi identico a quello attuale; ovviamente una simile condizione è eccessivamente restrittiva. Quello che ricercheremo nei capitoli successivi sarà un valore di σ2( )P che sia ragionevolmente basso, tale
da assicurare la necessaria accuratezza delle predizioni effettuate [5].
Un’altra metrica usata come parametro delle prestazioni di un predittore è il rapporto rumore-segnale (NSR) [3] definito da:
[
]
2 2 ˆ ( ) ( ) ( ) x n x n NSR x n − =∑
∑
(2.3)che indica buone prestazioni per valori prossimi a zero.
2.3 Il Chaos
In questa sezione verrà data una breve introduzione sulle principali nozioni che regolano i sistemi caotici [4, 5].
Definiamo un generico sistema dinamico tempo-continuo descritto dalla seguente equazione differenziale:
0 ( ) ( ) F t = = 0 x x x x (2.4)
dove x( )t è lo stato del sistema al tempo t e :F Rn →R è il n
campo vettoriale. La soluzione ( )φt x alla (2.4) è chiamata 0
traiettoria e la mappa : n n t
φ R →R è chiamata flusso del
sistema.
I sistemi dinamici sono classificati sulla base del loro comportamento nello stato di riposo, detto comportamento asintotico se t tende all’infinito. Nonostante non ci siano definizioni generalmente accettate, il chaos può essere intuitivamente definito come un comportamento nello stato di riposo, limitato, ma che non può essere associato ad alcun punto di equilibrio, soluzione periodica o quasi periodica. I sistemi caotici hanno inoltre un’importante proprietà chiamata Sensitive dependance on Initial Condition (SIC) cioè, date due differenti condizioni iniziali arbitrariamente vicine l’una all’altra, le traiettorie che emanano da questi punti divergono in modo significativo, fino a diventare praticamente incorrelate. In accordo a questa proprietà, nei sistemi caotici l’inevitabile effetto dell’incertezza sulle
condizioni iniziali è accentuato e il comportamento del sistema diviene impredicibile.
2.3.1 Strange Attractors
A causa della loro evoluzione impredicibile, le traiettorie dei sistemi caotici sono limitate (per definizione), e convergono nello spazio degli stati ad un oggetto chiamato attractor. La nozione di attractor è basata sulla definizione di punti limite e insieme limite.
Un punto y è un punto limite di x se, per ogni intorno I(y), la traiettoria φt(x) entra ripetutamente in I(y) al tendere di
t→ ∞ . L’insieme di tutti i punti limite di x è chiamato insieme limite L(x) di x. Gli insiemi limite sono chiusi ed invarianti rispetto a φt, cioè:
( ( ))φt L x =L( )x (2.5)
Un insieme limite α si definisce attracting se esiste un intorno aperto U di α tale che ∀ ∈x U L, ( )x =L. L’unione di tali intorni B(α) è chiamata basin of attraction dell’insieme α. In altre parole, ogni traiettoria che parte da B(α) termina nell’attractor α.
Tipici attractors sono costituiti da punti (in caso di punti di equilibrio stabili), cicli (in caso di soluzioni periodiche) o tori (in caso di soluzioni quasi-periodiche). Attractors di sistemi caotici sono invece oggetti geometrici molto più complessi di quelli elencati e posseggono proprietà frattali. Per questa ragione sono tipicamente chiamati strange attractors.
Gli attractors possono essere caratterizzati tramite la loro dimensione. Un attractor ha dimensione n (è n-dimensionale) se nell’intorno di uno dei suoi punti assomiglia ad un insieme aperto di R . In questo senso abbiamo che un punto di n equilibrio ha dimensione 0, una circonferenza ha dimensione 1, un toro ha dimensione 2. Al contrario, la geometria di uno strange attractor non assomiglia ad alcuno spazio euclideo e quindi tali attarctor non hanno una dimensione intera. Ci sono molti modi per generalizzare il concetto di dimensione ad un numero razionale, che portano a differenti definizioni come: capacity dimension, information dimesnion, correlation dimension e Lyapunov dimension.
2.4 Predizione di serie caotiche
Il tipico problema che si incontra nell’analisi di un sistema dinamico caotico è, data una mappa non lineare :f Rm→R m con uno strange attractor α, determinare il comportamento asintotico delle iterazioni n( )0
n
x = f x , 1 ≤ n < ∞. Quello che si è invece interessati a risolvere, in caso di predizione, è il problema inverso. Cioè dato un numero finito di iterazioni, costruire una mappa non lineare che le ha generate. Questa mappa verrà poi usata in un modello predittivo. In altre parole, data una serie di osservazioni
[
, ( 1)]
( )= x n x n( ), ( −1), x n N− +
x n
[
]
( 1) ( )
x n+ =F x n
cerchiamo una mappa :f Rm→R tale che: m
[
]
( 1) ( )
x n+ = f x n
questo problema può essere risolto in generale, con varie tecniche di interpolazione. Andiamo ora a descrivere un metodo che ci consenta di effettuare predizioni su serie temporali caotiche [17].
2.4.1 Algoritmo di predizione
Il primo passo è considerare le serie temporali come ottenute dal campionamento di una variabile temporale scalare x(t), che rappresenta la dinamica del sistema giacente su di uno strange attractor D-dimensionale.
Assumiamo poi una sequenza di osservazioni xn =x n( )τ ; la sequenza prende il nome di serie temporale caotica ed il periodo di campionamento prende il nome di delay time. Il secondo passo è inserire la sequenza in uno spazio degli stati m-dimensionale. Il valore m è chiamato embedding dimension. Il teorema di Taken, assicura che:
2 1
D m≤ ≤ D+ (2.6)
( ) ( ) ( 2 ) ( ( 1) ) x n x n x n x n m τ τ τ τ τ τ τ − = − − − n x (2.7)
Il terzo passo sarà quello di scegliere una apposita funzione interpolatrice f tale che: N
1 ( )
n N
x+ = f x n
N
f prende il nome di predittore. E’ da notare che, con un vettore di stato della forma (2.7) il futuro vettore xn+1 ha solo
la prima componente incognita.
Una volta che la funzione di interpolazione è stata scelta ed un valore di prova è stato assegnato ad m, le prestazioni delle predizioni sono ricavabili calcolando il predictor error (2.1). Se i risultati saranno ragionevolmente accurati (errore di predizione vicino a 0), il problema della predizione è risolto. Altrimenti viene scelto un nuovo valore di m e la procedura viene eseguita di nuovo, fino alla convergenza.
2.4.2 Tecniche di approssimazione
Abbiamo parlato della necessità di ricercare una funzione interpolatrice f tale che N xn+1= fN( )x . In molti contesti n
pratici, inclusi gli studi sul teletraffico, questo vincolo può essere rilassato, e fare in modo che f sia una N approssimazione tale che:
1 ( )
n N
x + ≈ f x n
questo fa sì che si possa scegliere tra un ampio numero di possibili tecniche di interpolazione. Tipicamente, queste tecniche, si dividono in due grandi categorie: tecniche globali e tecniche locali. Nelle prime, la funzione interpolatrice è applicata all’intera serie di vettori che possono essere costruiti dalla sequenza di dati; nelle seconde, invece, la predizione è effettuata sulla base degli stati passati che sono “vicini” a quello corrente. La spiegazione letterale di quest’ultima tecnica è intuitiva: cercare dei segmenti di traiettoria nel passato che assomiglino al segmento corrente e ricavare il comportamento futuro in accordo al modo in cui si è evoluto il sistema nel passato. La scelta del numero k di “vicini” da ricercare nel passato, è un altro problema critico. Tipicamente viene scelto un valore pari a k=m+1, ma il valore ottimale può dipendere, talvolta in modo significativo, dalle caratteristiche statistiche della serie temporale.
2.5 Predizione
del
Traffico
Uno degli approcci usati nei sistemi di controllo ed allocazione delle risorse di rete, è quello di predire il valore del traffico in determinati istanti futuri mediante misurazioni on-line delle sue caratteristiche. L’idea è quella di predire le future variazioni del traffico nel modo più preciso possibile, basandosi sull’osservazione della sua storia passata. Tale predizione può essere effettuata affidandosi ad accurati modelli, che riflettano le caratteristiche del traffico reale, oppure mediante tecniche adattative che non richiedano modelli matematici. E’ da precisare che una modellazione
non accurata può portare ad avere predizioni che sovrastimino o sottostimino in maniera eccessiva il traffico futuro. Recentemente numerosi studi hanno portato significativi cambiamenti nella ricerca di modelli adatti al traffico di rete. E’ stato provato infatti come tale traffico esibisca una marcata self-similarity, che non può essere descritta dai modelli classici [12, 14, 15, 16, 17].
2.5.1 Self Similarity
E’ stato provato che il traffico è self-similar e frattale in natura. Un processo self-similar è sostanzialmente un processo le cui caratteristiche statistiche rimangono invariate su scale temporali differenti. Ciò significa che effettuare la media su periodi temporali contigui ed eguali, non cambia il suo comportamento statistico. Consideriamo il generico processo ( )x n tempo-discreto, stazionario almeno in senso lato, a media nulla e con funzione di autocovarianza
{
}
( )k E x n x n k( ) ( )
γ = − . Consideriamo la nuova serie
temporale ottenuta mediando ( )x n su blocchi non sovrapposti di dimensione m: ( ) ( 1) 1 1 ( ) mn ( ) m i m n x n x i m = − + =
∑
(2.8)Il processo x( )m ( )n è anch’esso stazionario in senso lato ed ha funzione di autocovarianza γ( )m ( )k .
Il processo x(n) è detto exactly second-order self-similar con parametro di Hurst H (1/ 2<H < se: 1)
2 2 2 2 ( ) ( 1) 2 ( 1) 2 H H H k σ k k k γ = + − + − (2.9)
per ogni k≥1, in cui σ2 =E x n
{
2( )}
. Il processo x(n) èinvece asimptotically second-order self-similar se:
2 ( ) 2 2 2 lim ( ) ( 1) 2 ( 1) 2 m H H H m k k k k σ γ →∞ = + − + − (2.10)
E’ da notare che l’equazione (2.9) implica
( )m ( )k ( )k m 1
γ =γ ∀ ≥ . Perciò la second-order
self-similarity, riflette la proprietà per cui la struttura della correlazione di un processo sia esattamente (2.9) o asintoticamente (2.10) conservata in caso di aggregazione temporale.
Per meglio comprendere la particolare forma della γ( )k nella definizione di second-order self-similarity, cerchiamo di analizzare i processi self-similar in modo più generale. Per questo definiamo il processo cumulativo y(n) definito come:
( ) ( ) ( 1)
x n = y n −y n−
Considerando tale processo tempo-continuo y(t), t∈ R
andiamo a dare una definizione di self-similarity per processi tempo-continui nel senso della distribuzione di probabilità (distributional self-similarity). Per quanto riguarda la modellazione dei processi di traffico si può pensare a y(t) come al traffico totale osservato fino al tempo t. Il processo y(t) è self-similar con parametro di Hurst H (0<H < se per 1) ogni a>0 e t≥0:
( ) H ( ) d
y t = a y at− (2.11)
in cui = significa uguaglianza tra le distribuzioni e y(t) d prende il nome di H-ss. Perciò y(t) e la sua versione scalata temporalmente y(at) e normalizzata tramite il fattore a−H, hanno le stesse distribuzioni di probabilità. Per a>1 viene applicato un fattore di normalizzazione a−H < per far sì che 1 l’ampiezza di y(at) sia confrontabile con quella di y(t). E’ da notare che al variare di a il valore di H rimane costante. A meno che y(t) sia degenere, cioè che y(t)=0 per ogni t∈ R, a causa del fattore di normalizzazione a−H non può essere stazionario. Diversamente accade per il processo degli incrementi ( )x t =y t( )−y t( 1)− (con t∈Z). In particolare consideriamo il caso in cui y(t) sia H-ss ed il processo degli incrementi x(t) sia stazionario. In questo caso y(t) è un processo H-sssi (Self-Similar with Stationary Increments). Si può verificare che dati:
{ }
{
2}
2 2 ( ) 0 ( ) H E y t = e E y t =σ t si ha:(
)
2 2 2 2 ( ) 2 H H H k σ t t k k γ = − − + (2.12)( ) H (1) d
y t = t y 1 e dalla quale segue E y t
{
2( )}
=σ2 2t H.Quello che interessa adesso è capire come la distributional self-similarity di un processo tempo continuo influenzi la second-order self-similarity di un processo tempo discreto che richieda l’invarianza, esatta o asintotica, delle statistiche del secondo ordine della serie temporale aggregata x . Una ( )m osservazione fondamentale sta nel fatto che x può essere ( )m calcolato come la media campionaria di x:
[
]
[
]
( ) 1 1 1 1 1 ( ) ( ) (0) (1) (0) m m n H H d x x n y m y m m m m y y m x = − − = = − = − =∑
perciò, se y(t) è un processo H-sssi allora il processo degli incrementi x soddisfa la relazione:
1 H ( )m d
x= m− x (2.13)
che mostra come x sia legato ad x, nel senso delle ( )m distribuzioni, da una semplice relazione dipendente da H. La (2.13) è necessaria per avere una corrispondenza esatta o asintotica tra le strutture delle statistiche del secondo ordine. Quindi, dipendentemente dal fatto che il processo tempo-discreto x(n) soddisfi la (2.13) per ogni m o solamente per
m→ ∞, x(n) è detto rispettivamente exacltly self-similar o asymptotically self-similar. E’ da notare che nel caso di
1 Dalla relazione H ( ) ( )
processo gaussiano, queste due definizioni coincidono con la second-order self-similarity.
Andiamo adesso ad analizzare il ruolo del parametro di Hurst H. A questo proposito ricordiamo che la varianza della media campionaria z di una variabile aleatoria z è data da
2
var( )z =σz /m dove m è la dimensione del campione. Dalla (2.13) segue che segue che:
( ) 2 2 2
var(xm )=σ m H− (2.14)
e nel caso di campioni indipendenti (H =1/ 2) si riduce a
2m 1
σ − . Se H ≠1/ 2, in particolare 1/ 2<H <1 si ha che:
( ) 2
var(xm )=σ m−β (2.15)
in cui H = −1 β/ 2 e 0< < che riflette una certa β 1 dipendenza dei campioni e fa sì che la varianza di x ( )m converga a zero più lentamente di m−1.
2.5.2 Short Range e Long Range Dependence
Short-range dependence (SRD) si riferisce al fenomeno per cui le osservazioni correnti di un processo non sono correlate con quelle effettuate in un passato molto lontano e la correlazione con tali osservazioni tende a zero molto rapidamente.
Dall’altro lato la long-range dependence (LRD) di un processo può essere considerato il fenomeno per cui le osservazioni correnti sono correlate in modo significativo con le osservazioni effettuate in istanti passati, anche lontani nel
tempo. Questo fenomeno è di particolare interesse nella modellazione dei processi di traffico Internet da quando è stato scoperto il loro marcato comportamento LRD.
Indicando con σ2 la varianza di ( )x n e con r k( )=γ( ) /k σ2
la funzione di autocovarianza normalizzata, risulta per 0<H <1, H ≠1/ 2:
2 2
( ) (2 1) H ,
r k ∼H H− k − k→ ∞ (2.16)
In particolare se 1/ 2<H <1, r k si comporta ( ) asintoticamente come ck−β in cui c>0, 0< < e si ha: β 1
( ) k r k ∞ =−∞ = ∞
∑
(2.17)Questo significa che la funzione di autocovarianza decade lentamente, cioè iperbolicamente, e la sua somma diverge. Quando è verificata la (2.17), il corrispondente processo stazionario x(n) è detto long-range dependent. Al contrario, il processo x(n) è detto short-range dependent se ( )r k è sommabile e quindi
∑
kr k( )< ∞. Una definizione equivalente può essere data nel dominio della frequenza dove la densità spettrale definita come:1 ( ) (2 ) ( ) jk k r k e ν ν π − ∞ =−∞ Γ =
∑
(2.18)deve soddisfare la proprietà:
( )ν cν −α, ν 0
Γ ∼ → (2.19)
in cui c>0 costante e 0< =α 2H− <1 1. Perciò ( )Γν diverge attorno all’origine, implicando un largo contributo delle componenti a bassa frequenza.
Di seguito discutiamo alcuni casi particolari che riguardano il valore di H e le sue conseguenze sulla funzione ( )r k . Innanzitutto se H =1/ 2, ( ) 0r k = e x(n) è banalmente short-range dependent in quanto i suoi campioni sono totalmente incorrelati. Nel caso in cui 0<H <1/ 2 si ha che
( ) 0 kr k =
∑
, una condizione artificiale raramente riscontrata in applicazioni reali. Il caso H = è privo di interesse, in 1 quanto porta alla relazione r k( ) 1= per ogni k≥1. Infine valori di H maggiori di 1 sono proibiti a causa della condizione di stazionarietà imposta su x(n).2.5.3 Self-Similarity e Long-Range Dependence
Dalle precedenti discussioni si può intuire che esistano processi self-similar non long-range dependent e viceversa. Ad esempio Brownian motion (2.5.6) è un processo ½-sssi con rumore gaussiano come processo degli incrementi che non è long-range dependent. Allo stesso modo alcune serie temporali di tipo ARIMA (2.5.6) generano long-range dependance ma non sono self-similar nel senso delle distribuzioni (distributional self-similarity, 2.5.1). Nel caso di second-order self-similarity comunque, restringendosi ai casi in cui 1/ 2<H <1, self-similarity implica long-range dependance e viceversa. E’ per questa ragione e per il fatto che i processi asintoticamente second-order self-similar sono impiegati come modelli canonici per i processi di traffico, che si usa scambiare i termini self-similarity e long-range
dependance in tutti quei contesti in cui i due significati non creano ambiguità.
2.5.4 Distribuzione Heavy-Tailed
Esiste una relazione molto stretta tra distribuzioni heavy-tailed e long-range dependance. Innanzitutto, una variabile aleatoria z ha una distribuzione heavy-tailed se:
{
}
,P z x> ∼cx−α x→ ∞ (2.20)
in cui 0< <α 2 è chiamato tail index o shape paraeter e c è una costante positiva. In altre parole la coda della distribuzione decade iperbolicamente. Questo in contrasto con altri tipi di distribuzioni, come quella gaussiana o esponenziale la cui coda decade esponenzialmente, che sono chiamate pertanto light-tailed distributions. Un carattere distintivo delle distribuzioni heavy-tailed è che hanno varianza infinita per 0< <α 2, e se 0< ≤α 1 posseggono anche una media illimitata. Nel contesto dei processi coinvolti nelle reti di comunicazione l’interesse principale è ristretto al caso 1< <α 2. Una distribuzione heavy-tailed che si incontra frequentemente è la distribuzione di Pareto la cui funzione di distribuzione di probabilità è definita da:
{
}
1 b , P z x b x x α ≤ = − ≤ (2.21)dove b è chiamato location parameter. La media è data da
/( 1)
b
La caratteristica principale di una variabile aleatoria con distribuzione di probabilità di tipo heavy-tailed è che esibisce una marcata variabilità. In pratica una distribuzione heavy-tailed dà luogo a valori molto grandi con probabilità non trascurabile, ed i campioni estratti da un processo con una tale distribuzione hanno, seppure in una piccola percentuale, valori molto elevati. La distribuzione heavy-tailed fa sì che la media campionaria converga alla media della popolazione sempre più lentamente al tendere di α ad 1. A titolo di esempio, la media campionaria z di dimensione m di una m variabile aleatoria di Pareto z, può allontanarsi significativamente dalla media complessiva della popolazione
/( 1)
b
α α− , spesso sottostimandola. Infatti, l’errore assoluto di stima zm−E z
{ }
si comporta asintoticamente come(1/ ) 1
m α− e quindi per α →1 deve essere fatta particolare
attenzione al campionamento di processi con tali distribuzioni.
2.5.5 Heavy-Tails e Predicibilità
La distribuzione heavy-tailed di alcune variabili nei sistemi di rete, come ad esempio le dimensioni dei files e la durata delle connessioni, può essere vista come la causa principale della long-range dependance e della self-similarity dei processi di traffico. Andiamo ora ad esaminare la predicibilità intrinseca associata ad una variabile aleatoria che presenta una distribuzione heavy-tailed. Indichiamo con z una variabile heavy-tailed che può essere interpretata come la durata di una connessione di rete (ad es. una connessione TCP). Dal momento che le connessioni sono eventi misurabili,
assumiamo di avere osservato che la connessione è attiva da τ secondi. Per semplificare la discussione assumiamo il tempo discreto ( t∈Z ) e che + A:Z+→
{ }
0,1 sia una funzione tale che ( ) 1A t = se z t≥ . Siamo interessati alla probabilità che la connessione persista sapendo che è stata attiva per τ secondi. In altre parole dobbiamo stimare la probabilità condizionata:{
}
L( )τ =P A(τ + =1) 1| ( ) 1,1A t = ≤ ≤t τ (2.22)
che può essere espressa come:
{
}
{
}
( ) 1 P z L P z τ τ τ = = − ≥ (2.23)In primo luogo andiamo a valutare L( )τ per light-tails, in particolare per distribuzioni con coda esponenziale tali che
{
}
2 1c x
P z x> ∼c e dove c c sono costanti positive. Il secondo 1, 2 termine nell’equazione (2.23) si può calcolare per grandi valori di τ come:
{
}
{
}
2 2 2 2 ( 1) 1 1 1 c c c c P z c e e e P z c e τ τ τ τ τ − − + − − = − = − ≥ ∼ (2.24) e pertanto: 2 ( ) c Lτ ∼e− (2.25)Quindi per light-tails esponenziali, la predizione non è migliorata dall’avere osservato lunghi periodi di attività. Per distribuzioni heavy-tailed la (2.24) si modifica in:
{
}
{
}
( 1) 1 1 P z c c P z c α α α α τ τ τ τ τ τ τ − − − = − + = − ≥ ∼ + (2.26) che implica: ( )Lτ 1, τ → ∞ (2.27)ciò significa che per tali distribuzioni, maggiore è il tempo di attività osservato della connessione, maggiore è la probabilità che persista negli istanti futuri. Infatti è semplice generalizzare la (2.22) in modo da calcolare la persistenza della connessione in δ unità temporali nel futuro (δ ≥1) come:
{
}
L( )τ =P A(τ+ =s) 1,1≤ ≤s δ | ( ) 1,1A t = ≤ ≤t τ (2.28)
Questo non cambia il risultato qualitativo. Per distribuzioni light-tailed L( )τ ∼e−c2δ; per il caso heavy-tailed
(
)
( ) 1 /
Lτ ∼ +δ τ −α e tende asintoticamente ad 1. Dal momento che
(
1+δ τ/)
−α ≤e−αδ τ/ , si può osservare che inentrambi i casi la predicibilità è sensibile in modo esponenziale all’intervallo di predizione δ . Nel caso heavy-tailed però, per ogni valore di δ unità temporali nel futuro, l’errore di predizione può essere ridotto a valori arbitrariamente piccoli condizionando la predizione ad una osservazione di durata sufficientemente elevata.
2.5.6 Long Memory Models
In questa sezione vengono presentati alcuni modelli non tradizionali, chiamati long memory models, capaci di rilevare le caratteristiche statistiche dei processi LRD.
2.5.6.1 Fractional Brownian Motion (fBm)
Brownian motion è un processo stocastico Bm(t), t>0 caratterizzato dalla proprietà per cui i suoi incrementi
0
( ) ( )
Bm t t+ −Bm t hanno distribuzione normale a media nulla e varianza tσ2. Il fractional brownian motion è un processo
self-similar con parametro di Hurst 1/ 2<H <1 i cui incrementi hanno varianza pari a t2Hσ2.
2.5.6.2 Fractional Gaussian Noise (fGn)
Mentre il modello fBm è molto utile per analisi teoriche, in pratica si preferisce utilizzare il seguente modello valido per un incremento temporale finito τ:
(
)
( ) ( ) ( 1)
fGn n = fBm nτ − fBm n− τ (2.29)
Il modello fGn è stazionario, al contrario di fBm, e la sua funzione di autocovarianza normalizzata è data da:
2 2 2 ( ) 1/ 2 (k k 1) H 2k h (k 1) H ρ = + − + + (2.30) e per k → ∞: (2 2) ( )k H H(2 1)k H ρ = − − (2.31)
2.5.6.3 Fractional ARIMA (FARIMA)
Il modello FARIMA, proposto da Hosking nel 1980, è un’estensione del processo tradizionale ARIMA. Un processo è stazionario e invertibile di tipo FARIMA(p, d, q) se:
( )φ B ∆dx n( )=θ( ) ( )B w n (2.32)
dove −1/ 2< <d 1/ 2 è un numero reale,
( ) ( ) ( 1)
x n x n x n
∆ = − − , w(n) è rumore bianco a media nulla ,
φ e θ sono rispettivamente i polinomi autoregressivo e a media mobile del processo. B è l’operatore di ritardo per cui
( ) ( )
s
B x n =x n s− . La relazione tra H e d è:
1/ 2
H = +d (2.33)
perciò, x è un processo LRD se 0< <d 1/ 2, altrimenti è un processo SRD. Il modello FARIMA è uno dei più utilizzati per la modellizzazione del traffico.
Se consideriamo il caso fondamentale FARIMA(0,d,0) abbiamo:
( )∆dx n =w n( ) (2.34)
e la funzione di covarianza normalizzata risulta:
( )!( 1)! ( ) ( 1)!( )! d k d k d k d ρ = − + − − − (2.35) e per k→ ∞:
2 1 ( )! ( ) ( 1)! d d k k d ρ = − − − (2.36)
2.5.6.4 Generalized ARMA (GARMA)
Questo modello è la generalizzazione di tutti i modelli autoregressivi. Un processo GARIMA(p,q) è definito come:
2
(1 2 B B ) ( )dx n w n( )
φ − η + =θ (2.37)
dove −1/ 2< <d 1/ 2 e 1− < < . η 1
2.5.7 Fractional Predictors
In questo paragrafo viene descritto il sistema per ottenere predittori basati sui modelli long-memory del paragrafo 2.5.6. In particolare vengono esaminati i modelli FARIMA e GARMA. Nonostante sia possibile trovare un predittore diretto basato sul modello fGn, la sua elevata computazione ne rende inutile la trattazione in previsione di una sua difficile implementazione software.
Dato un processo FARIMA(p,d,q) invertibile, dalla (2.32) deriva: 0 ( ) i ( ) j w n ∞ π x n j = =
∑
− (2.38) dove:1 0 ( ) ( )(1 ) j d j j B B B B π φ θ ∞ − = = −
∑
(2.39)ed il predittore FARIMA ad un passo risulta:
1 ˆ( 1) j ( 1) j x n ∞ π x n j = + = −
∑
− + (2.40)Il predittore GARMA è del tutto simile a quello FARIMA, tranne per la (2.39) che diventa:
1 2 0 ( ) ( )(1 2 ) j d j i B B B B B π φ θ η ∞ − = = − +
∑
(2.41)2.6 Predittore
LMMSE
Nelle sezioni precedenti 2.4 e 2.5 sono state esposte le tecniche di predizione per serie caotiche e tecniche per la predizione di processi LRD basate su modelli statistici. In questa sezione e nelle successive, vengono descritte altre tecniche di predizione standard che non sono basate su alcun modello matematico e che sono quindi indipendenti dalle caratteristiche dei processi a cui vengono applicate. In particolare in questa sezione, viene descritto il Linear Minimum Mean Square Error Predictor (LMMSE), un tipo di predittore lineare la cui condizione ottimale è la minimizzazione dell’errore quadratico medio [1].
Il problema è quello di predire il valore futuro di un processo aleatorio, nel nostro caso identificato dall’intensità di traffico in arrivo, avendo osservato i valori passati di tale processo.
Indicando con x(n)2 la quantità di traffico in arrivo al passo n, vogliamo ricavarne una stima attraverso una combinazione lineare dei campioni osservati:
[
]
( )= x n( ) x n( −1) x n( −2) x n p( − +1)
x n (2.42)
con p eventualmente infinito, del tipo:
1 0 ˆ( ) ( ) ( ) p i x n k h i x n i − = + =
∑
− (2.43)dove gli
{ }
h i( ) ip=−01 sono i coefficienti della risposta impulsiva del predittore di ordine p.La differenza tra x(n+k) ed il valore della sua stima ˆ(x n k+ ) viene chiamata errore di predizione al passo n e si indica con
ε(n): 1 0 ˆ ( ) ( ) ( ) ( ) p ( ) ( ) i n x n k x n k x n k h i x n i ε − = = + − + = + −
∑
− (2.44)I coefficienti h(i) vengono ricavati imponendo che l’errore quadratico medio 2 E
{
2( )n}
ε
σ = ε sia minimo. La soluzione si ricava imponendo il principio di ortogonalità [1], il quale stabilisce che 2
ε
σ è minimo quando l’errore di predizione ε(n) è a media nulla ed ortogonale a ciascun dato. Formalmente:
2 In questa trattazione consideriamo che il processo x sia a media nulla. Se
0 0 X R ε ε µ = = (2.45)
Risulta ovvio che il valor medio dell’errore di predizione debba essere zero. In caso contrario adottando la nuova stima
ˆ( )
x n k+ −µε si otterrebbe un errore a media nulla, e quindi un valore quadratico medio più piccolo. Conclusione che contrasta con l’ipotesi che ˆ(x n k+ ) sia la stima ottima. L’ortogonalità dell’errore ai dati può essere formalizzata come segue:
{
( ) ( )}
0 0 1E ε n x n m− = ≤ ≤ −m p (2.46)
sostituendo la (2.44) nella (2.46) si ottiene la seguente relazione: 1 0 ( ) ( ) ( ), 0 1 p x x i R m k h i R m i m p − = + =
∑
− ≤ ≤ − (2.47)detta anche equazione di Yule-Walker dove:
{
}
( ) ( ) ( )
x
R m =E x n x n m− (2.48)
Il problema della determinazione dei coefficienti è ridotto quindi alla risoluzione del seguente sistema lineare:
( )R h p k (2.49) x =
(0) ( 1) ( 1) (0) ( ) (1) (0) ( 1) (1) ( 1) ( 1) ( 2) (0) ( 1) ( 1) x x x x x x x x x x x x R R R p h R k R R R h R k R p R p R h p R k p − − + − + = − − − + − (2.50) 1 (0) ( 1) ( 1) ( ) (0) (1) (0) ( 1) ( 1) (1) ( 1) ( 2) (0) ( 1) ( 1) x x x x x x x x x x x x R R R p R k h R R R R k h R p R p R R k p h p − − − + − + − − + − − = (2.51)
ovvero per il predittore lineare ad un passo (k=1):
1 (0) ( 1) ( 1) (1) (0) (1) (0) ( 1) (2) (1) ( 1) ( 2) (0) ( ) ( 1) x x x x x x x x x x x x R R R p R h R R R R h R p R p R R p h p − − − + − − − − = (2.52)
In realtà l’implementazione di questo predittore, come risulta dalla descrizione, richiede la conoscenza della funzione di autocorrelazione di x e l’inversione di una matrice di dimensione p che può essere di difficile realizzazione. Per la risoluzione di questo problema esistono però tecniche
adattative, che permettono di calcolare i coefficienti del predittore ricorsivamente, senza la necessità di conoscere alcuna funzione statistica e con relativa semplicità computazionale.
L’utilizzo di queste tecniche viene esposto in dettaglio nel capitolo 4.
2.7 Interpolatore
parabolico
Questa tecnica di predizione si basa sull’approssimazione dell’andamento del processo x(n) incognito mediante una funzione elementare [18]. Tale approssimazione viene effettuata sulla base di un numero finito di punti, rappresentati dalle osservazioni del processo negli istanti passati. Dato il vettore degli osservati x(n):
[
]
( )= x n( ) x n( −1) x n( −2) x n p( − +1)
x n (2.53)
l’interpolazione parabolica consiste nel determinare un polinomio di grado al più p-1:
1 2 1( ) 1 2 1 0 p p p p p P− z =a z− − +a − z − + +a z a+ (2.54) tale che: 1( ) ( ), ( 1), , p P− k =x k k = n p− + … (2.55) n
il polinomio Pp−1( )z prende il nome di polinomio di interpolazione. Nell’insieme dei polinomi del tipo (2.54) ne esiste uno ed uno solo che verifica la (2.55). Infatti,
imponendo che il polinomio (2.54) verifichi le (2.55) si ottiene il sistema lineare di p equazioni in p incognite a : i
2 2 1 0 1 2 2 1 2 2 1 0 1 2 2 1 ( ) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1) p p p p p p p p a a n a n a n a n x n a a n a n a n a n x n x n p − − − − − − − − + + + + + = + − + − + + − + − = − = − − (2.56)
la matrice dei coefficienti del sistema risulta pertanto:
2 1 2 1 2 1 1 1 ( 1) ( 1) ( 1) 1 ( 1) ( 1) ( 1) p p p p p p n n n n n n n p n p n p − − − − − − − − − − + − + − + (2.57)
detta matrice di Vandermonde. La risoluzione di tale sistema porta al polinomio cercato in funzione di n. Il predittore si realizza pertanto in modo semplice ponendo:
1
ˆ( 1) p ( 1)
x n+ =P− n+ (2.58)
2.8 Predittore
LMK
In questa sezione viene mostrato un particolare tipo di predittore chiamato Least Mean Kurtosis Predictor (LMK), che assume come funzione “costo” da minimizzare la curtosi negata dell’errore di predizione piuttosto che il suo errore quadratico medio [16]. Mentre l’errore quadratico è una
statistica di secondo ordine, la curtosi di un processo è una statistica di ordine elevato.
Quello che si cerca è ancora un predittore lineare della forma:
1 0 ˆ( ) ( ) ( ) p i x n k h i x n i − = + =
∑
− (2.59) o in forma vettoriale: ˆ( ) ( ) x n k+ = hx n (2.60)data la serie (2.42) di p osservazioni. Nell’algoritmo LMK la funzione da minimizzare è rappresentata dalla curtosi negata dell’errore di predizione, definita come:
{
} {
}
2 2 4 ( ) 3 ( ) ( ) LMK J h = E ε n −E ε n (2.61) e quindi:[
]
{
2}
{
[
]
4}
2 ( ) 3 ( ) ( ) ( ) ( ) LMK J h = E x n k+ −hx n −E x n k+ −hx n (2.62) effettuando il gradiente rispetto al vettore h:{
2}
{
}
{
3}
( ) 4 3 ( ) ( ) 4 ( ) ( )
LMK
J E ε n E ε n E ε n
∇ h = − x n (2.63)
il valore di E
{
ε2( )n}
viene stimato dalla seguente equazionericorsiva:
2
( ) ( 1) (1 ) ( )
che sostituita nella (2.63) risulta: 2 ˆ ( ) 4 3 ( ) ( ) ( ) ( ) LMK J G n ε n ε n ∇ h = − x n (2.65)
in cui, in realtà, il vettore dei coefficienti del predittore viene calcolato ad ogni passo. E’ quindi utile specificare la sua dipendenza da n: ( )h h n . Il parametro = β è il forgetting factor che controlla la memoria della funzione di stima dell’errore quadratico medio.
L’equazione di aggiornamento dei coefficienti è:
(
)
1 ˆ ( 1) ( ) [ ] 4γ JLMK + = − ∇ h n h n h(n) (2.66)in cui γ è lo step-size. La (2.66) può essere normalizzata come segue:
(
2)
2 3 ( ) ( ) ( ) ( ) ( 1) ( ) [ ( ) ] G n n n γ −ε ε + = + T x n h n h n x n x (n) (2.67)Per un predittore LMK di ordine p, la complessità computazionale è di 2p+5 moltiplicazioni e di p+3 addizioni.
2.9 Predittore
Naive
Il predittore descritto in questa sezione è forse il più semplice dei predittori realizzabili. Tale predittore non si basa su alcuna minimizzazione di funzioni costo o su alcun modello matematico. La sua formula può essere ricavata anche dall’interpolatore parabolico assumendo la dimensione del vettore dati p=1. Consiste nell’assumere il campione successivo uguale al campione precedente:
ˆ( 1) ( )
x n+ =x n (2.68)
E’ da notare che pur non rispondendo ad alcun criterio ottimo, il predittore Naive risulta uno stimatore non polarizzato anche se poco efficiente in quanto il suo valor medio e la sua varianza coincidono con quelli del processo reale.
