Modelagem computacional de dados estocásticos de
Transcrição
Modelagem computacional de dados estocásticos de
XII Simpósio Brasileiro de Automação Inteligente (SBAI) Natal – RN, 25 a 28 de outubro de 2015 MODELAGEM COMPUTACIONAL DE DADOS ESTOCÁSTICOS DE SÉRIE TEMPORAL MULTIVARIÁVEL NO ESPAÇO DE ESTADO PELO MÉTODO DE AKAIKE: ANÁLISE E APLICAÇÃO MARLENY A. CHARAGUA JAVIER∗ ANGIE J. FORERO∗ CELSO P. BOTTURA∗ ∗ DSIF-FEEC-UNICAMP, Av. Albert Einstein - 400, Cidade Universitária Zeferino Vaz Distrito Barão Geraldo Campinas, SP, 13083-852, Brasil Email: [email protected],[email protected],[email protected] Abstract— The state-space realization theory of dynamical systems developed by Kalman received important contributions to the stochastic case of Faurre and Akaike. In this paper first we present some aspects of the theory of stochastic realization by Akaike. Then we present the method due to Akaike implemented in MATLAB and apply it to the computational modeling of stochastic data of multivariate time séries. At the end we analyze the results. Keywords— Data modeling, Stochastic Realization, Akaike, Multivariate Time Series. Resumo— A teoria da realização no espaço de estado de sistemas dinâmicos desenvolvida por Kalman recebeu importantes contribuições para o caso estocástico de Faurre e de Akaike. Neste trabalho primeiramente tratamos de alguns aspectos da teoria de realização estocástica de Akaike. Em seguida apresentamos o método de Akaike implementado em MATLAB e o aplicamos na modelagem computacional de dados estocásticos de séries temporais multivariadas. Para finalizar fazemos uma análise dos resultados obtidos. Palavras-chave— 1 Modelagem de dados, Realização Estocástica, Akaike, Séries Temporais Multivariádas Introdução no espaço de estado na forma inovativa Kalman (1960), a construção das matrizes de Hankel e Toeplitz a partir das covariâncias do futuro e do passado da série temporal; depois mostra-se a abordagem geométrica de Akaike. Nela, de forma especial, definimos os espaços preditores, os vetores base x e x̆, bem como apresentamos o cálculo associado à análise de correlação canônica entre o futuro e o passado da série temporal pela decomposição em valores singulares da matriz de Hankel e a solução aproximada da equação algébrica de Ricatti. Em seguida é calculada a tripla (A, C, K) do modelo inovativo. Finalmente o algoritmo apresentado é aplicado em dois exemplos de séries temporais multivariadas. A série temporal multivariada estocástica constitui um processo estocástico vetorial, e os modelos dessas séries podem ser descritos no espaço de estado. A modelagem computacional de dados de séries temporais tem sido abordada por diversas áreas de estudo, devido à grande importância de encontrar modelos matemáticos que possam descrever o comportamento dinâmico da série temporal. Alguns trabalhos relacionados com a modelagem de séries temporais e a identificação de sistemas multivariáveis no espaço de estado desenvolvidos no Laboratorio de Controle e Sistemas Inteligentes -LCSI- UNICAMP podem ser vistos em Torrico Cáceres (2005), Clavijo (2008), Tamariz (2005), Barreto (2002), Giesbrecht (2013), Tobar (2013), Alegria (2015), Serra (2005). A teoria da realização estocástica de Akaike (1974) está baseada na teoria da realização de sistemas lineares desenvolvida por Kalman (1963), no algoritmo de realização determinı́stica de Ho e Kalman (1966) e no algoritmo de realização estocástica de Faurre (1976). O método proposto por Akaike trata o problema da realização estocástica com uma abordagem geométrica, onde a partir dos dados da série temporal são gerados os espaços preditores do futuro e do passado. Aplicando a análise de correlação canônica aos espaços preditores são obtidos os vetores base ortonormais, os quais são usados como vetores de estado na representação Markoviana, ver Akaike (1975). Neste artigo apresentamos de forma breve, o problema da realização estocástica, o modelo 2 O Problema de Realização Estocástica Dada uma série temporal y(t) para t = 0, ±1, . . . com média zero e matriz de covariância descrita por: Λ(l) = E{y(t + l)y T (t)}, l = 0 ± 1, . . . (1) onde E{·} é o operador esperança matemática, o problema da realização estocástica é encontrar um modelo Markoviano no espaço de estado com a forma inovativa, a partir das matrizes de covariância (1) da saı́da y(t): x(t + 1) y(t) = Ax(t) + Ke(t) = Cx(t) + e(t) (2) onde x(t) ∈ Rn é o vetor de estado, K ∈ Rn×p é o ganho de Kalman , A ∈ Rn×n e C ∈ Rp×n são 1830 XII Simpósio Brasileiro de Automação Inteligente (SBAI) as matrizes do sistema, e e(t) ∈ Rp é o processo de inovação, expresso como um ruido branco com media zero e matriz de covariância: 4 = E{e(t)eT (t)} 3 Neste trabalho o problema de modelagem computacional de dados estocásticos de série temporal multivariada é abordado pela teoria da realização estocástica baseada em correlações canônicas proposta por Akaike (1974), Akaike (1976). Nesta teoria, a partir de y(t) é gerado o espaço Yt definido por: (3) Para o modelo descrito em (2), definimos a matriz de observabilidade estendida dada por: O= h CT AT C T AT 2 CT ··· i (4) Yt = span{y(t), t = 0, ±1, 2, . . .} e a matriz de controlabilidade estendida dada por: C= onde C̄ T AC̄ T A2 C̄ T ··· onde span{· · · } representa o espaço fechado de Hilbert gerado pelos elementos infinitos {· · · }. O espaço Yt é dividido nos subespaços do futuro Yt+ e do passado Yt− , dados por: (5) C̄ T = E{x(t + 1)y(t)T } Yt+ = span{y(t), y(t + 1), . . .}, Yt− = span{y(t − 1), y(t − 2), . . .} A matriz de Hankel é calculada com as matrizes de observabilidade e controlabilidade estendidas, da seguinte forma: H = OC A estimativa de variância minima do futuro baseado no passado ŷf |p é calculada mediante a projeção ortogonal do futuro f (t) sobre o subespaço do passado Yt− , como é mostrado na figura 1. (6) A partir dos dados da série temporal y(t), definem-se os vetores do futuro e do passado como: y(t) f (t) := y(t + 1) , .. . y(t − 1) p(t) := y(t − 2) .. . f (t) A matriz de Hankel de covariância é calculada a partir da matriz de covariância cruzada do futuro e do passado, da forma: Λ(1) Λ(2) H = E{f (t)pT (t)} = Λ(3) .. . Λ(2) Λ(3) Λ(4) .. . Λ(3) Λ(4) Λ(5) .. . 0 = = E{f (t)f T (t)} Λ(0) ΛT (1) Λ(1) Λ(0) Λ(2) Λ(1) .. .. . . ΛT (2) . . . ΛT (1) . . . Λ(0) . . . .. .. . . ... . . . . . . .. . Figura 1: Projeção ortogonal do futuro no passado Assim a equação da estimativa de variância minima do futuro baseado no passado é dada por: ŷf |p = Ê{f (t) | Yt− } = E{p(t)pT (t)} Λ(0) Λ(1) Λ(2) ΛT (1) Λ(0) Λ(1) = ΛT (2) ΛT (1) Λ(0) .. .. .. . . . ... . . . . . . .. . (10) onde Ê{·} representa o operador projeção ortogonal. Da mesma forma, a estimativa de variância minima do passado baseada no futuro ŷp|f é calculada mediante a projeção ortogonal do passado p(t) sobre o subespaço do futuro Yt+ , como é mostrado na figura 2. A equação da estimativa de variância minima do passado baseado no futuro é dada por: (8) e a matriz de covariância do passado é definida como a matriz de Toeplitz do passado, da forma: T− ŷf |p Yt− (7) A matriz de covariância do futuro é definida como a matriz de Toeplitz do futuro, da forma: T+ Modelagem Computacional Estocástica pelo Método de Akaike y̆p|f = Ê{p(t) | Yt+ } (9) (11) Com as estimativas de variância minima de (10) e (11) são gerados o espaço preditor do futuro 1831 XII Simpósio Brasileiro de Automação Inteligente (SBAI) onde p é o numero de saı́das, N o numero de amostras da serie temporal e k é o numero de linhas das matrizes bloco do futuro Yf e do passado Yp ; k é escolhido com a condição k n. p(t) Com as matrizes do passado Yp e do futuro Yf obtemos as matrizes de covariâncias Σf f , Σpp e as matrizes de covariâncias cruzadas Σf p e Σpf : 1 Yp T Σpp Σpf T Yp Yf = Σ f p Σf f N Yf ŷp|f 0 Yt+ Para calcular as matrizes de covariâncias aplicamos a fatoração LQ da forma: T 1 Yp L11 0 Q1 √ = (14) Y L L QT2 f 21 22 N Figura 2: Projeção ortogonal do passado no futuro X̂t+ e do passado X̆t− , como segue: X̂t+ := Ê{Yt+ | Yt− } = span{ŷf |p (t + h) | h = 0, 1, . . .} X̆t− := Ê{Yt− | Yt+ } = span{y̆p|f (t − l) | l = 1, 2, . . .} Assim, elas podem ser calculadas em função das componentes da matriz L em (14): (12) (13) Obtendo os vetores base ortonormais dos espaços preditores do futuro e do passado temos uma representação no espaço de estado do sistema estocástico. Estes vetores base são chamados vetores de estado do futuro x̂(t) e do passado x̆(t). A caracterização especifica da estrutura do vetor de estado define a representação canônica de um sistema linear estocástico; esta representação canônica é obtida escolhendo o vetor de estado como o primeiro conjunto máximo de elementos linearmente independentes entre as estimativas de variância minima. Devido a que as matrizes de covariância de estado do futuro x̂(t) e do passado x̆(t) são iguais à matriz de correlação canônica Σ, E{x̂(t)x̂(t)T } = E{x̆(t)x̆(t)T } = Σ, pode-se usar qualquer um dos vetores de estado x̂(t) ou x̆(t) indiferentemente, ver Katayama (2005). Neste trabalho será usado o vetor de estado do futuro x̂(t) e será denotado como x(t) no modelo de Markov apresentado em (2). Σf p = L21 LT11 , Σf f = L21 LT21 + L22 LT22 , Σf f = L21 LT21 + L22 LT22 Aplicando a decomposição em valores singulares SVD, obtem-se as correlações canônicas do futuro e do passado da série temporal, como se mostra a seguir: −1/2 Σf f Σf p ΣTpp/2 = U ΣV T ' Û Σ̂V̂ T (15) onde a dimensão do vetor de estado é dada pela dimensão de Σ̂ e o vetor de estado estimado X k é dado pela equação (16): X k = Σ̂1/2 V̂ T Σ−1/2 Yp ∈ Rn×N pp (16) Σ̂ e Σ̄ são as soluções aproximadas das equações algébricas de Ricatti para o futuro e para o passado respectivamente: Σ̂ = AΣ̂AT + (C̄ T − AΣ̂C T ) ×(Λ(0) − C Σ̂C T ) ×(C̄ T − AΣ̂C T )T (17) e 3.1 Algoritmo Σ̄ = AT Σ̄A + (C T − AT Σ̄C̄ T ) Com os dados da série temporal y(t), construı́mos as matrizes do passado Yp ∈ Rkp×N e do futuro Yf ∈ Rkp×N , da forma: y(k − 1) y(k) . . . y(N + k − 2) y(k − 2) y(k − 1) . . . y(N + k − 3) Yp := .. .. .. . . . y(0) y(1) ... y(N − 1) y(k) y(k + 1) y(k + 1) y(k + 2) Yf := ... ... y(2k − 1) y(2k) ×(Λ(0) − C̄ Σ̄C̄ T )−1 ×(C − C̄ Σ̄A) (18) Os valores singulares de Σ̂ e Σ̄ são as correlações canônicas do futuro e do passado do processo estacionário y(t). . . . y(k + N − 1) ... y(k + N ) ... ... . . . y(N + 2k − 2) 1832 A partir da decomposição em valores singulares, obtemos a observabilidade Ok e a controlabilidade Ck , como: −1/2 Ok = Σf f Û Σ̂1/2 , Ck = Σ̂1/2 V T ΣTpp/2 (19) XII Simpósio Brasileiro de Automação Inteligente (SBAI) As matrizes A, C e C̄ T são calculadas a partir das matrizes de observabilidade e controlabilidade, da forma: A partir da série temporal y(t) são estimadas as matrizes (As , Ks , Cs ) pelo algoritmo de Akaike A = O†k Ok , C = Ok (1 : p, :), C̄ = Ck (:, 1 : p) (20) onde: Ok = Ok (1 : (k − 1)p, :) As = Ks = e Ok = Ok (p + 1 : kp :) Cs = O ganho de Kalman é: K = (C̄ T − AΣ̂C T )(Λ(0) − C Σ̂C T )−1 −0.8314 −0.3738 0.3364 −0.4580 −0.0798 −0.945 0.1805 −0.6320 1.9227 −2.5746 −3.2490 1.3082 (21) Para avaliação dos resultados obtidos, comparamos a sequência calculada ys (t) gerada com as matrizes estimadas (As , Cs , Ks ) Figura 3 (B e E) com a sequência vetorial y(t), Figura 3 (A e D). Consideramos, também, a diferença entre as duas saı́das y(t) − ys (t), Figura 3 (E e F). onde Λ(0) = Σf f (1 : p, 1 : p). 3.2 Sı́ntese do Metodo O método de Akaike passo a passo é o seguinte: 1. Calcule a decomposição LQ de (14) 2. Calcule a SVD segundo (15) A) Saida y1 Real 20 Amplitude 3. Calcule as matrizes de observabilidade e de controlabilidade dadas por (19) 4. Calcule as matrizes A, C e C̄ T com (20) 10 0 −10 −20 0 2 4 6 8 10 8 10 B) Saida y1 Estimada 5. Calcule o ganho de Kalman K como na equação (21). Amplitude 20 6. Finalmente represente o modelo de espaço de estado na forma inovativa (2). 10 0 −10 −20 0 2 4 6 C) Erro de estimacão y(1)−yest(1) 4 1 Exemplos de modelagem de dados de séries temporais multivariáveis 0.5 0 −0.5 O algoritmo da realização estocástica devido ao Akaike é aplicado na modelagem computacional de dados de séries temporais multivariadas. Dois casos são apresentados a seguir. −1 0 2 4 6 8 10 8 10 8 10 D) Saida y2 Real 10 Caso 1 Amplitude 4.1 Considerando o seguinte modelo de segunda ordem ”benckmark” no espaço de estado com a forma inovativa: −0.735 −0.363 A= 0.333 −0.565 −1.502 −0.949 K= −0.945 −0.088 −1.438 −0.680 C= 1.067 −0.531 5 0 −5 −10 0 2 4 6 E) Saida y2 Estimada Amplitude 10 5 0 −5 −10 0 2 4 6 F) Erro de estimacão y(2)−yest(2) 1 0.5 0 geramos a série temporal multivariada da seguinte forma: y1 (t) y(t) = , com t=1 ,2, 3. . . 1000, y2 (t) perı́odo de amostragem de 1 × 10−2 s e 10s de duração. −0.5 −1 0 2 4 6 8 10 Tempo em s Figura 3: Comparação dos resultados do caso 1. 1833 XII Simpósio Brasileiro de Automação Inteligente (SBAI) 4.2 Caso 2 A) Saida y1 Real 20 Amplitude Considerando o seguinte modelo de ordem 3 no espaço de estado com a forma inovativa: −0.5465 0.6630 −0.1199 A = −0.8468 −0.8542 −0.0653 −0.2463 −1.2013 0.4853 −0.5955 −0.0793 K = −0.1497 1.5352 −0.4348 −0.6065 −1.3474 −0.9036 −0.6275 C= 0.4694 0.0359 0.5354 0 −10 −20 0 2 4 6 8 10 8 10 B) Saida y1 Estimada Amplitude 20 10 0 −10 −20 0 2 4 6 C) Erro de estimacão y(1)−yest(1) 1 0.5 geramos a série temporal multivariada da seguinte forma: y1 (t) y(t) = , com t=1 ,2, 3. . . 1000, pey2 (t) rı́odo de amostragem de 1 × 10−2 s e 10s de duração. A partir da série temporal y(t) são estimadas as matrizes (As , Ks , Cs ) pelo algoritmo de Akaike −0.7290 0.6587 0.0107 As = −0.6686 −0.7028 −0.0512 0.0051 0.1667 0.5013 −0.1438 −0.1276 0.2162 Ks = 0.1175 0.3473 0.9298 −1.9481 −5.1173 0.4378 Cs = 0.3995 1.5113 −0.5956 0 −0.5 −1 0 2 4 6 8 10 8 10 8 10 D) Saida y2 Real Amplitude 10 5 0 −5 −10 0 2 4 6 E) Saida y2 Estimada Amplitude 10 5 0 −5 −10 0 2 4 6 F) Erro de estimacão y(2)−yest(2) 1 0.5 Para avaliação dos resultados obtidos, comparamos a sequência calculada ys (t) gerada com as matrizes estimadas (As , Cs , Ks ) Figura 4 (B e E) com a sequência vetorial y(t),Figura 4 (A e D). Consideramos, também, a diferença entre as duas saı́das y(t) − ys (t), Figura 4 (E e F). 5 10 0 −0.5 −1 0 2 4 6 8 10 Tempo em s Figura 4: Comparação dos resultados do caso 2. Conclusões Referências Com os dados das séries temporais multivariadas dos dois casos apresentados 1 e 2, obtivemos através do método de Akaike para cada um deles a realização estocástica (A, K, C) na forma inovativa através do método de Akaike. Vemos que os erros calculados são desprezı́veis. Akaike, H. (1974). Stochastic theory of minimal realization., IEEE Trans. Automatic control AC-19: 667–674. Akaike, H. (1975). Markovian representation of stochastic processes by canonical variables, SIAM J. control 13: 162–173. Agradecimentos Akaike, H. (1976). Canonical correlation analysis of time series and the use of an information criterion., System identication: Advances and case studies (R. Mehra and D.Lainiotis, eds) pp. 27–96. Os autores agradecem ao MSc. Jorge Andrés Puerto Acosta por sua ajuda neste trabalho. Alegria, E. O. J. (2015). Estimação on-line de parâmetros dependentes do estado (state dependent parameter - sdp) em modelos de regresão não lineares, Master’s thesis, Universidade Estadual de Campinas UNICAMP. 1834 XII Simpósio Brasileiro de Automação Inteligente (SBAI) Aoki, M. (1987). State space modeling of time series, Universitext, Springer, Berlin, Heidelberg, New York. Soares, A. and Bottura, C. P. (2011). Identificação de séries temporais multivariadas no espaço de estado pelo método de akaike baseado em correlações canônicas com parâmetro iterativo, Anais do X Simpósio Brasileiro de Automação Inteligente, Universidade Federal de São João del-Rei, São João del-Rei, MG, Brasil, pp. 314–319. Barreto, G. (2002). Modelagem Computacional Distribuı́da e Paralela de Sistemas e de Séries Temporais Multivariáveis no Espaço de Estado, PhD thesis, Universidade Estadual de Campinas. Tamariz, A. D. R. (2005). Modelagem Computacional de Dados e Controle Inteligente no Espaço de Estado, PhD thesis, Universidade Estadual de Campinas. Chiuso, A. and Picci, G. (2001). Some algorithmic aspects of subspace identification with inputs, Int. J. Applied Math and Computer Science 11(1): 55–75. Tobar, J. B. Q. (2013). Propostas para modelagem computacional de series temporais e de sistemas multivariaveis variantes no tempo no espaço de estado, Master’s thesis, Universidade Estadual de Campinas. Clavijo, D. G. (2008). Metodos de subespaços para identificação de sistemas: Propostas de alterações, implementações e avaliações, Master’s thesis, Universidade Estadual de Campinas. Torrico Cáceres, A. F. (2005). Identificação e Controle Estocásticos Descentralizados de Sistemas Interconectados Multivariáveis no Espaço de Estado, PhD thesis, Universidade Estadual de Campinas. Faurre, P. (1976). Stochastic realization algorithms, in R. K. Mehra and D. G. Lainiotis (eds), System Identification Advances and Case Studies, Vol. 126 of Mathematics in Science and Engineering, Elsevier, pp. 1 – 25. Van Overschee, P. and De Moor, B. (1996). Subspace Identification for Linear Systems, Kluwer Academic Pub. Giesbrecht, M. (2013). Propostas imunoinspiradas para identificação de sistemas e realização de séries temporais multivariáveis no espaço de estado, PhD thesis, Universidade Estadual de Campinas. Verhaegen, M. (1994). Identification of the deterministic part of mimo state space models given in innovations from input-output data, Automatica 30(1): 61–74. Ho, B. and Kalman, R. E. (1966). Effective construction of linear, state-variable models from input/output functions, Regelungstechnik 14: 545–548. Kalman, R. E. (1960). A new approach to linear filtering and prediction problems, Trans. ASME J. Basic Engineering 82D: 34–45. Kalman, R. E. (1963). Mathematical description of linear dynamical systems, Journal of the Society for Industrial and Applied Mathematics Series A Control 1(2): 152–192. Katayama, T. (2005). Subspace Methods for System Identification, Springer. Lindquist, A. and Picci, G. (1996a). Canonical correlation analysis, approximate covariance extension, and identification of stationary time series, Automatica 32(5): 709–733. Lindquist, A. and Picci, G. (1996b). Geometric methods for state space identification, The Science of Learning Models from Data 50: 1– 69. Serra, G. L. O. (2005). Propostas de metodologias para Identificação e Controle Inteligentes, PhD thesis, Universidade Estadual de Campinas. 1835