ads:
Universidade Federal do Maranh
˜
ao - UFMA
Coordenac¸
˜
ao de P
´
os-Graduac¸
˜
ao em Engenharia El
´
etrica
Disserta¸c˜ao de Mestrado
ALGORITMO RECURSIVO BASEADO EM
UMA FUNC¸
˜
AO N
˜
AO LINEAR DO ERRO
CRISTIANE CRISTINA SOUSA DA SILVA
S˜ao Luis - MA, Brasil
6 de mar¸co de 2009
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Sum´ario
Agradecimentos 4
1 Introdu¸c˜ao 6
1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Organiza¸c˜ao do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Filtragem Adaptativa 9
2.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 O Combinador Linear Adaptativo . . . . . . . . . . . . . . . . . . . . 10
2.3 Algoritmos de Gradiente Estoc´astico . . . . . . . . . . . . . . . . . . 11
2.4 Algoritmos de M´ınimos Quadrados . . . . . . . . . . . . . . . . . . . 13
2.5 Conclus˜ao do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 O algoritmo M´ınimos Quadrados Recursivo (Recursive Least
Square-RLS ) 14
3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Dedu¸c˜ao do algoritmo RLS . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 O lema de invers˜ao de matrizes . . . . . . . . . . . . . . . . . 16
3.2.2 O algoritmo RLS ponderado exponencialmente . . . . . . . . 16
3.2.3 Atualiza¸c˜ao do vetor peso . . . . . . . . . . . . . . . . . . . . 17
3.3 Convergˆencia do algoritmo RLS . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 O comportamento m´edio do vetor peso no algoritmo RLS . . 18
3.3.2 Matriz de correla¸c˜ao do vetor desvio . . . . . . . . . . . . . . 19
3.3.3 Curva de apredizagem do algoritmo RLS . . . . . . . . . . . . 20
3.3.4 Tempo de aprendizagem . . . . . . . . . . . . . . . . . . . . . 22
i
ads:
3.3.5 Excesso do erro quadr´atico m´edio e o desajuste . . . . . . . . 23
3.4 Conclus˜ao do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 O Algoritmo Recursivo N˜ao Linear - RNL 25
4.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Dedu¸c˜ao do algoritmo RNL . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.1 O algoritmo RNL ponderado exponencialmente . . . . . . . . 28
4.2.2 Atualiza¸c˜ao do vetor peso . . . . . . . . . . . . . . . . . . . . 29
4.2.3 Resumo do algoritmo RNL . . . . . . . . . . . . . . . . . . . . 30
4.3 Convergˆencia do algoritmo RNL . . . . . . . . . . . . . . . . . . . . . 31
4.3.1 O comportamento m´edio do vetor peso no algoritmo RNL . . 31
4.3.2 Matriz de correla¸c˜ao do vetor desvio . . . . . . . . . . . . . . 32
4.3.3 Curva de apredizagem do algoritmo RNL . . . . . . . . . . . . 33
4.3.4 An´alise do tempo de aprendizagem . . . . . . . . . . . . . . . 35
4.3.5 Excesso do erro quadr´atico m´edio e o desajuste . . . . . . . . 37
4.4 Conclus˜oes do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Resultados e Discuss˜oes 38
5.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Simula¸c˜oes com o algoritmo RNL . . . . . . . . . . . . . . . . . . . . 38
5.3 Discuss˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.4 Conclus˜oes do Cap´ıtulo . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6 Conclus˜oes e Proposta de Continuidade 41
6.1 Conclus˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.2 Proposta de Continuidade . . . . . . . . . . . . . . . . . . . . . . . . 41
ii
ALGORITMO RECURSIVO BASEADO EM UMA
FUNC¸
˜
AO N
˜
AO LINEAR DO ERRO
Disserta¸c˜ao de mestrado submetida `a coordena¸c˜ao do Curso de P´os-
Gradua¸c˜ao de Engenharia de Eletricidade da UFMA como parte dos requisitos
para obten¸c˜ao do t´ıtulo de Mestre em Engenharia de Eletricidade na ´area de
Automa¸c˜ao e Controle.
CRISTIANE CRISTINA SOUSA DA SILVA
FEVEREIRO, 2009
Silva, Cristiane Cristina Sousa da
Algoritmo recursivo baseado em uma função não linear do erro /
Cristiane Cristina Sousa da Silva. – São Luís, 2009.
47f.
Orientador: Allan Kardec Duailibe Barros Filho.
Impresso por computador (Fotocópia).
Dissertação (Mestrado) – Universidade Federal do Maranhão,
Curso de Pós-Graduação em Engenharia Elétrica. São Luís, 2009.
1. Sinais – Processamento. 2. Filtragem adaptativa. 3. Algoritmos
adaptativos. I. Barros Filho, Allan Kardec Duailibe, orient. II. Título.
CDU 004.8
2
ALGORITMO RECURSIVO BASEADO EM UMA
FUNC¸
˜
AO N
˜
AO LINEAR DO ERRO
MESTRADO
´
Area de Concentra¸c˜ao: AUTOMAC¸
˜
AO E CONTROLE
CRISTIANE CRISTINA SOUSA DA SILVA
Orientador: Prof. Dr. Allan Kardec Duailibe Barros Filho
Curso de P´os-Gradua¸c˜ao
em Engenharia de Eletricidade da
Univesidade Federal do Maranh˜ao
AGRADECIMENTOS
Ao professor Allan Kardec Duailibe Barros Filho pela motiva¸c˜ao, apoio, carinho
e dedica¸c˜ao, fundamentais para a orienta¸c˜ao deste trabalho. Pela oportunidade de
crescimento e apredizado. Gostaria de ratificar a sua comp etˆencia, participa¸c˜ao
com discuss˜oes, corre¸c˜oes e sugest˜oes que fizeram com que conclu´ıssemos este
trabalho.
Ao professor Jo˜ao Viana Fonseca Neto, Co-Orientador deste trabalho, pelo
incentivo, orienta¸c˜ao, e cr´edito durante to das as fases do curso de mestrado.
Ao professor Marcos Antonio F. de Ara´ujo, Co-Orientador deste trabalho, pela
aten¸c˜ao, carinho, amizade e dedica¸c˜ao a mim dispensados em todas as fases do
curso de mestrado.
Ao professor Arist´ofanes Corrˆea Silva pelo cr´edito, incentivo e amizade.
A todos os meus amigos do PIB pelo companherismo e amizades sinceras.
A Deus pelas oportunidades que me foram dadas.
`
A toda a minha fam´ılia pelo carinho, apoio e compreens˜ao ao longo do ano em
que o presente trabalho foi desenvolvido. Em especial ao meu marido Marcio John
Moreira e meu filho Gustavo Henrique Sousa S. Moreira.
`
A CAPES pela bolsa a mim concedida.
Resumo
Muitos dos filtros adaptativos s˜ao baseados no m´etodo do Erro quadr´atico m´edio
(Mean Square Error - MSE). O desenvolvimento desses filtros nos garante recuperar
apenas informa¸c˜oes de segunda ordem dos sinais a serem filtrados, ou seja, s´o
consegue recuperar totalmente informa¸c˜oes de sinais Gaussianos. No entanto, os
sinais naturais ou artificiais n˜ao s˜ao necessariamente gaussianos. Desta forma, a
utiliza¸c˜ao de estat´ıstica de alta ordem, como uma forma de extrair mais informa¸c˜oes
dos sinais, tem se demonstrado de grande valia em sistemas adaptativos [7][8][9].
Neste trabalho, n´os apresentamos o desenvolvimento de um algoritmo adaptativo
baseado em fun¸c˜oes n˜ao lineares inspirado na dedu¸c˜ao do algoritmo Recursive Lest
Square (RLS) [1]. Tal desenvolvimento baseia-se na utiliza¸c˜ao de estat´ısticas de alta
ordem para a obten¸c˜ao de mais informa¸c˜oes dos sinais envolvidos no processo, com
o objetivo de melhorar a performance de um filtro adaptativo. Chamaremos esse
novo algoritmo de Recursivo n˜ao Linear - RNL.
Deduzimos equa¸c˜oes, baseadas em uma fun¸c˜ao n˜ao linear, para a obten¸c˜ao de
crit´erios que garantam a convergˆencia. Tamb´em fazemos um estudo da covariˆancia
do vetor peso em regime estacion´ario e determinamos equa¸c˜oes que calculem o
desajuste e o tempo de aprendizagem do processo adaptativo do algoritmo RNL.
Apresentamos o algoritmo n˜ao linear recursivo, que utiliza como crit´erio a
fun¸c˜ao ε
n
=
M
j=1
n
i=1
λ
n−i
[e
i
]
2j
, sendo M e n inteiros positivos. Foram feitas
simula¸c˜oes com este algoritmo para validar a teoria apresentada e estudamos o
comportamento da convergˆencia do algoritmo RNL. O resultado mostrou que o
algoritmo RNL possui uma r´apida convergˆencia para o mesmo desajuste quando
comparado com o algoritmo RLS. .
Palavras-chaves: Processamento de sinais. Filtragem Adaptativa. Algoritmos
Adaptativos
Cap´ıtulo 1
Introdu¸c˜ao
Os sinais envolvidos em processamentos de filtragem, predi¸c˜ao e estima¸c˜ao s˜ao
sinais aleat´orios, os quais s˜ao caracterizados por suas propriedades estat´ısticas. O
projeto de filtro para o processamento de sinais aleat´orios requer o conhecimento
pr´evio de algumas informa¸c˜oes sobre as propriedades estat´ısticas dos sinais
envolvidos. Quando isso ´e poss´ıvel, trata-se o problema no ˆambito do processamento
estat´ıstico de sinais. Nos casos em que tais informa¸c˜oes s˜ao desconhecidas e n˜ao
podem ser estimadas em tempo real, a melhor solu¸c˜ao ´e o emprego de filtros
adaptativos.
A filtragem adaptativa constitui uma ferramenta fundamental no processamento
de sinais digitais. Ela ´e aplicada atualmente em um grande n ´umero de problemas
de engenharia. Esta t´ecnica tem sido explorada com sucesso em problemas de
economia, engenharia biom´edica, equaliza¸c˜ao de canais, sistemas de controle e
em telecomunica¸c˜oes. Em especial, na ´area biom´edica, diversas aplica¸c˜oes p odem
ser encontradas, tais como: cancelamento de interferˆencias do cora¸c˜ao doador
no eletrocardiograma (ECG) durante o transplante de cora¸c˜ao; cancelamento da
influencia materna em ECG fetal.
O trabalho em filtragem adaptativa envolve o estudo de algoritmos e de
estruturas de filtragem de forma a melhorar o desempenho dos sistemas adaptativos
existentes. Entre os diversos algoritmos existentes na literatura, pode-se citar o
Recursive Least Square (RLS), nessa t´ecnica, o estimador m´edio ´e atualizado com
6
base em um conjunto de valores previamente simulados em vez de ser atualizado
com um ´unico valor.
Um sistema adaptativo ´e aquele cuja estrutura ´e alter´avel (atrav´es do ajuste dos
seus coeficientes) de tal forma que seu comportamento melhore de acordo com algum
crit´erio de desempenho atrav´es da exposi¸c˜ao ao ambiente no qual ser´a inserido. O
ajuste dos coeficientes do filtro adaptativo ´e realizado atrav´es da implementa¸c˜ao
de um algoritmo, devidamente escolhido, cujo objetivo ´e atender a requisitos dos
sistemas. Estes algoritmos s˜ao definidos como algoritmos adaptativos.
Neste trabalho, n´os apresentamos o desenvolvimento de um algoritmo adaptativo
que utiliza como fun¸c˜ao de custo uma n˜ao linearidade par. Chamaremos esse novo
algoritmo de Recursivo n˜ao linear.
1.1 Motiva¸c˜ao
Muitos dos filtros desenvolvidos, em filtragem adaptativa, s˜ao baseados no
m´etodo do Erro quadr´atico m´edio (Mean Square Error - MSE ) conseguindo, deste
modo, recuperar apenas informa¸c˜oes de segunda ordem dos sinais a serem filtrados,
ou seja, s´o conseguem recuperar totalmente informa¸c˜oes de sinais gaussianos.
No entanto, os sinais naturais (biom´edicos, geoprocessamento) ou artificiais (FM,
AM, telecomunica¸c˜ao em geral) n˜ao s˜ao necessariamente gaussianos, longe disso.
Assim, objetivando extrair mais informa¸c˜oes dos sinais envolvidos no processo de
adapta¸c˜ao, propomos o desenvolvimento de um novo algoritmo adaptativo baseado
em fun¸c˜oes n˜ao lineares inspirado no algoritmo RLS padr˜ao.
1.2 Organiza¸c˜ao do texto
Este trabalho est´a organizado da seguinte forma: No cap´ıtulo 2, apresentamos o
combinador linear adaptativo, fazemos uma revis˜ao da superf´ıcie quadr´atica e um
breve coment´ario sobre algoritmos de gradiente estoc´astico e de m´ınimos quadrados.
No cap´ıtulo 3, revisamos o algoritmo RLS mostrando a sua dedu¸c˜ao,
convergˆencia do vetor p eso, tempo de aprendizagem e desajuste final.
No cap´ıtulo 4, desenvolvemos um novo algoritmo, que utiliza como fun¸c˜ao de
7
custo ε
n
=
M
j=1
n
i=1
λ
n−i
[e
i
]
2j
, sendo M e n inteiros positivos. Obtemos express˜ao
para garantir a convergˆencia e determinamos o desajuste;
No cap´ıtulo 5, simula¸c˜oes computacionadas foram realizadas para comparar
o desempenho do algoritmo proposto com o RLS padr˜ao, aplicando as equa¸c˜oes
desenvolvidas no cap´ıtulo 4 . Apresentamos tamb´em as discuss˜oes do trabalho.
No cap´ıtulo 6, s˜ao apresentadas as conclus˜oes e sobre o algoritmo desenvolvido,
assim como algumas das possibilidades futuras de expans˜ao.
8
Cap´ıtulo 2
Filtragem Adaptativa
2.1 Introdu¸c˜ao
Os filtros Adaptativos representam uma parte significativa no processamento
de sinais digitais. Historicamente, a abordagem param´etrica de sinais tem sido
explorada com sucesso em problemas de comunica¸c˜oes, controle rob´otica, radar,
sismologia e engenharia biom´edica. Os chamados problemas de filtragem podem
ser identificados e caracterizados mais especificamente pelos termos de filtragem,
suaviza¸c˜ao, predi¸c˜ao [1].
O principal objetivo da filtragem de sinais ´e melhorar a qualidade do sinal de
acordo com um crit´erio de desempenho. Os sinais podem ser considerados tanto no
dom´ınio do tempo com no dom´ınio da freq¨uˆencia. A diferen¸ca dos filtros adaptativos
aos demais ´e o seu desempenho auto-ajust´avel e variante no tempo.
Muitos algoritmos adaptativos utilizam-se do erro quadr´atico m´edio como fun¸c˜ao
de custo que deseja-se minimizar. O erro quadr´atico m´edio ´e uma fun¸c˜ao convexa
dos componentes do vetor peso e gera uma superf´ıcie hiperparabol´oide que garante a
existˆencia de um m´ınimo global. O problema consiste em determinar procedimentos
de tal forma a encontrar esse m´ınimo, o mais r´apido poss´ıvel e com o menor erro
final.
9
2.2 O Combinador Linear Adaptativo
A estrutura mais usada na implementa¸c˜ao de filtros adaptativos ´e o combinador
linear adaptativo (CLA), mostrado na figura (2.1). Pode-se observar que o filtro
adaptativo possui uma entrada ´unica, u
i
(no tempo i), definida como
u
i
=
u
i
, u
i−1
, ..., u
i−(L−1)
T
(2.1)
sendo L o tamanho do filtro.
Figura 2.1: Combinador Linear Adaptativo - forma transversal
w
n
, ´e o vetor peso no tempo n, definido por
w
n
= [
w
n0
w
n1
. . . w
n(L−1)
]
T
. (2.2)
e a sa´ıda, y
i
, ´e igual ao produto interno de u
i
por w
n
:
y
i
= u
T
i
w
n
= w
T
n
u
i
(2.3)
Conforme visto na figura (2.1), o sinal de erro, no instante i, ´e dado por
e
i
= d
i
− y
i
. (2.4)
Substituindo (2.3) nesta express˜ao, temos:
10
e
i
= d
i
− u
T
i
w
n
= d
i
− w
T
n
u
i
. (2.5)
Existem v´arios algoritmos e abordagens que podem ser utilizados, dependendo
dos requisitos do problema. No entanto, existem duas ab ordagens principais para
o desenvolvimento de algoritmos de filtros adaptativos [1]. Discutiremos essas duas
abordagens nas pr´oximas se¸c˜oes.
2.3 Algoritmos de Gradiente Estoc´astico
O erro quadr´atico m´edio, como j´a foi dito, ´e uma fun¸c˜ao convexa dos
componentes do vetor peso e gera uma superf´ıcie hiperparabol´oide que garante
a existˆencia de um m´ınimo global, o que representa a solu¸c˜ao ´otima de Wiener.
Esta solu¸c˜ao pode ser encontrada pelo bem conhecido m´etodo de otimiza¸c˜ao,
denominado “m´etodo de decida mais ´ıngreme”, que utiliza o vetor gradiente para
descer gradualmente passo a passo para o m´ınimo da fun¸c˜ao erro. As chamadas
equa¸c˜oes de Wiener-Hopf, em forma matricial, definem esta solu¸c˜ao ´otima de
Wiener. Vamos, agora determinar a solu¸c˜ao ´otima a partir do crit´erio do erro
quadr´atico m´edio dado por [9].
ξ = E[e
2
i
] = E[(d
i
− w
T
n
u
i
)
2
] (2.6)
Considerando um ambiente est´acionario, podemos desenvolver a Equa¸c˜ao 2.6
como
ξ = E[d
i
] + w
T
ϕw − 2z
T
w (2.7)
sendo ϕ a matriz de auto-correla¸c˜ao do sinal de entrada u
i
e z a matriz de correla¸c˜ao
cruzada do sinal de entrada u
i
com o sinal desejado d
i
.
Pode-se observar que o erro quadr´atico m´edio ´e uma fun¸c˜ao quadr´atica dos pesos,
cujo gr´afico ´e uma superf´ıcie cˆoncava hiperparabol´oica, conforme vemos na figura
2.2, onde consideramos apenas dois pesos. Esta fun¸c˜ao, obviamente, nunca pode ser
negativa.
11
Figura 2.2: Por¸c˜ao de uma superf´ıcie quadr´atica tridimensional, juntamente com
alguns contornos. O erro quadr´atico m´edio est´a plotado na vertical, w
0
e w
1
variam
de −1 a 1
O gradiente da superf´ıcie de desempenho do erro quadr´atico m´edio, designado
por ∇, pode ser obtido derivando (3.2) para obter o erro quadr´atico m´edio m´ınimo.
O vetor peso ´e ajustado para seu valor ´otimo, w
∗
, onde o gradiente ´e zero, ou seja:
w
∗
= ϕ
−1
z (2.8)
Esta equa¸c˜ao ´e uma express˜ao matricial da equa¸c˜ao de Wiener-Hopf.
Um sistema modificado das equa¸c˜oes de Wiener-Hopf, usado para adaptar os
pesos do filtro em dire¸c˜ao ao m´ınimo ´e o algoritmo chamado “Least Mean Squares
(LMS)”, inventado por B. Widrow e M.E.Hoff Jr em 1959. Este algoritmo calcula
o gradiente da fun¸c˜ao de erro de valores instantˆaneos da matriz de correla¸c˜ao das
entradas e do vetor de correla¸c˜ao cruzada entre as entradas e a resposta desejada.
O algoritmo LMS ´e muito simples. Nesta se¸c˜ao, faremos uma breve discuss˜ao deste
algoritmo.
Para desenvolver o algoritmo LMS, usamos o pr´opio e
2
i
como uma estimativa de
ξ
i
. Ent˜ao, a cada itera¸c˜ao, no processo adaptativo, n´os teremos uma estima¸c˜ao do
12
gradiente da forma
ˆ
∇
n
=
∂e
2
n
∂w
0
.
.
.
∂e
2
n
∂w
L
= 2
e
n
∂e
n
∂w
0
.
.
.
∂e
n
∂w
L
=
−
2
e
n
U
n
.
(2.9)
As derivadas de e
i
, em rela¸c˜ao aos pesos, seguem, diretamente de 2.4.
A partir de 2.9 temos o algoritmo LMS [9]
W
n
= W
n−1
+ µe
n
U
n
. (2.10)
sendo µ o passo de adapta¸c˜ao. Tal parˆametro ´e uma constante que comanda a
velocidade de convergˆencia do algoritmo.
2.4 Algoritmos de M´ınimos Quadrados
´
E sabido que na dedu¸c˜ao do algoritmo LMS o objetivo ´e minimizar o quadrado
m´edio da estima¸c˜ao erro. No m´etodo dos m´ınimos quadrados, por outro lado, no
instante n > 0, os pesos do filtro adaptativo s˜ao calculados tal que a quantidade
ζ
n
=
n
i=1
ρ
i
. |e
i
|
2
(2.11)
´e minimizado, da´ı o nome m´ınimos quadrados
O algoritmo Recursive Least Squares - RLS, pode ser visto como um caso especial
do filtro de Kalman [1], que ´e uma forma dos m´ınimos quadrados. Tais algoritmos
tˆem como vantagem a baixa sensibilidade `a natureza do sinal de entrada e uma
maior velocidade de convergˆencia quando comparado com os algoritmos de gradiente
estoc´astico. O algoritmo mais popular desta fam´ılia ´e o RLS. No pr´oximo cap´ıtulo
faremos a dedu¸c˜ao deste algoritmo.
2.5 Conclus˜ao do Cap´ıtulo
Neste cap´ıtulo, realizou-se uma revis˜ao da superf´ıcie quadr´atica gerada quando
se utiliza o erro quadr´atico m´edio (EQM) como crit´erio aplicado sobre o erro em um
filtro adaptativo. Mostramos a deriva¸c˜ao do algoritmo LMS.
13
Cap´ıtulo 3
O algoritmo M´ınimos Quadrados
Recursivo (Recursive Least
Square-RLS )
3.1 Introdu¸c˜ao
Em implementa¸c˜oes recursivas do m´etodo dos m´ınimos quadrados come¸camos
com condi¸c˜oes iniciais conhecidas e utilizamos a informa¸c˜ao contida em novas
amostras de dados para atualizar as estimativas passadas. Assim, encontramos
que o tamanho do dado observ´avel ´e vari´avel. Desta forma expressamos a fun¸c˜ao de
custo para ser minimizada como ε
n
sendo n o tamanho vari´avel do dado observ´avel.
Portanto ´e comum introduzir um fator peso na defini¸c˜ao da fun¸c˜ao de custo.
3.2 Dedu¸c˜ao do algoritmo RLS
No algoritmo RLS o fator pondera¸c˜ao ρ
i
´e escolhido como sendo
ρ
i
= λ
n−i
(3.1)
sendo 0 << λ < 1 uma constante positiva a ser escolhida.
O m´etodo dos m´ınimos quadrados padr˜ao visto anteriormente coresponde ao
caso em que λ = 1. O parˆametro λ ´e denominado fator de equecimento. Claramente
quando λ < 1, os fatores de pondera¸c˜ao definidos 3.1 d´a um peso maior `as amostras
14
recentes das estimativas do erro (e assim, `a amostras recentes do dado observado)
comparado com as amostras mais antigas. Em outras palavras, a escolha de λ < 1
resulta em um esquema que d´a mais ˆenfase `as amostras recentes do dado observado
e tende a esquecer as amostras antigas.
Substituindo 3.1 em 2.11 obtem-se a fun¸c˜ao de custo a ser m´ınimizada na dedu¸c˜ao
do algoritmo RLS.
ε
n
=
n
i=1
λ
n−i
. |e
i
|
2
(3.2)
Supondo que ϕ seja uma matriz n˜ao singular, o valor ´otimo do vetor peso, ˆw
n
,
para que a fun¸c˜ao de custo atinja este valor m´ınimo ´e definido pela equa¸c˜ao normal
escrita em forma matricial
ˆw
n
= ϕ
−1
n
z
n
(3.3)
Sendo
ϕ
n
=
n
i=1
λ
n−i
.u
i
u
T
i
(3.4)
a matriz de auto-correla¸c˜ao do sinal de entrada u
i
e
z
n
=
n
i=1
λ
n−i
.u
i
d
i
(3.5)
a matriz de correla¸c˜ao cruzada do sinal de entrada u
i
com o sinal desejado d
i
.
Expandindo a Equa¸c˜ao 3.4 e isolando o termo i = n, temos
ϕ
n
= λ
n−1
i=1
λ
n−1−i
.u
i
.u
T
i
+ u
n
.u
T
n
ϕ
n
= λ [ϕ
n−1
] + u
n
.u
T
n
(3.6)
Analogamente podemos escrever a Equa¸c˜ao 3.5 da seguinte forma
z
n
= λ [z
n−1
] + u
n
.d
n
(3.7)
15
3.2.1 O lema de invers˜ao de matrizes
Lema 1: Sejam A e B matrizes definidas positivas de dimens˜ao L×L, definimos
A = B
−1
+ CD
−1
C
T
(3.8)
De 3.8 obtemos
A
−1
= B − BC
D + C
T
BC
−1
C
T
B (3.9)
Sendo D matriz definida positivamente de dimens˜ao N × L e C uma matriz L × N.
A demonstra¸c˜ao desse Lema ´e estabelecida pela multiplica¸c˜ao da Equa¸c˜ao 3.8
por 3.9. Na pr´oxima se¸c˜ao mostraremos como o lema de invers˜ao de matrizes pode
ser aplicado para obter uma equa¸c˜ao recursiva.
3.2.2 O algoritmo RLS ponderado exponencialmente
Como a matriz de auto-correla¸c˜ao ´e positivamente definida e n˜ao singular,
podemos aplicar o lema de invers˜ao de matrizes para equa¸c˜ao recursiva 3.4.
Primeiramente faremos as seguintes identifica¸c˜oes:
A = ϕ
n
B
−1
= λϕ
n−1
→ B = λ
−1
ϕ
−1
n−1
C = u
n
D = I
(3.10)
Substituindo as defini¸c˜oes 3.10 na equa¸c˜ao 3.9, obtemos a rela¸c˜ao de
recursividade da matriz ϕ
n
, ou seja:
ϕ
−1
n
= λ
−1
ϕ
−1
n−1
−
λ
−2
ϕ
−1
n−1
u
n
u
T
n
ϕ
−1
n−1
1 + λ
−1
u
T
n
ϕ
−1
n−1
u
n
(3.11)
Por conveniˆencia computacional podemos escrever as seguintes igualdades:
P
n
= ϕ
−1
n
(3.12)
k
n
=
λ
−1
P
n−1
u
n
1 + λ
−1
u
T
n
P
n−1
u
n
(3.13)
16
Podemos reescrever a equa¸c˜ao 3.11 como segue:
P
n
= λ
−1
P
n−1
− λ
−1
k
n
u
T
n
P
n−1
(3.14)
Sendo P
n
a inversa da matriz de auto-correla¸c˜ao de dimens˜ao L × L e k
n
o vetor
ganho de dimens˜ao L × 1. Reorganizando a equa¸c˜ao 3.13, temos:
k
n
+ k
n
λ
−1
u
T
n
P
n−1
u
n
= λ
−1
P
n−1
u
n
k
n
=
λ
−1
P
n−1
− kλ
−1
u
T
n
P
n−1
u
n
(3.15)
Substituindo a equa¸c˜ao 3.14 em 3.15 seque-se:
k
n
= P
n
u
n
k
n
= ϕ
−1
n
u
n
(3.16)
3.2.3 Atualiza¸c˜ao do vetor peso
No desenvolvimento de uma equa¸c˜ao recursiva, utilizaremos as Equa¸c˜oes 3.3,
3.7 e 3.12 para expressar a estimativa do m´ınimo quadrado do vetor peso, ˆw
n
, no
instante n como segue:
ˆw
n
= P
n
. [λz
n−1
+ u
n
]
ˆw
n
= λP
n
.z
n−1
+ P
n
u
n
(3.17)
Substituindo a equa¸c˜ao 3.14 na equa¸c˜ao 3.17, temos:
ˆw
n
= P
n−1
.z
n−1
− k
n
u
n
.P
n−1
.z
n−1
+ P
n
u
n
d
n
(3.18)
Das equa¸c˜oes 3.16 e 3.18, segue-se:
ˆw
n
= ˆw
n−1
− k
n
.
n
(3.19)
17
Sendo
n
a estimativa do erro a priori definida por:
n
= d
n
− u
T
n
. ˆw
n−1
(3.20)
3.3 Convergˆencia do algoritmo RLS
Estudaremos nesta se¸c˜ao a convergencia do algoritmo RLS no contexto de um
problema de modelagem de sistema. Como planta consideramos um regressor
m´ultiplo linear caracterizado pela equa¸c˜ao
d
n
= w
T
∗
u
n
+ e
n
(3.21)
sendo w
∗
o vetor peso do regressor, u
n
o vetor entrada, e
n
´e o ruido da planta e d
n
a sa´ıda da planta. O erro de medi¸c˜ao e
n
do processo ´e branco com m´edia zero e
variˆancia σ
2
3.3.1 O comp ortamento m´edio do vetor peso no algoritmo
RLS
De 3.3 e 3.5 obtemos
ˆw
n
= ϕ
−1
n
n
i=1
λ
n−i
.u
i
d
i
(3.22)
Substituindo 3.21 em 3.22 e usando 3.4, temos
ˆw
n
= ˆw
∗
+ ϕ
−1
n
n
i=1
λ
n−i
.u
i
e
i
(3.23)
Aplicando o operador esperan¸ca em ambos os membros da Equa¸c˜ao 3.23 e
reconhecemos do princ´ıpio de ortogonalidade que todos os elementos do vetor u
n
s˜ao ortogonais ao erro e
n
, obtemos
E[ ˆw
n
] = ˆw
∗
(3.24)
18
3.3.2 Matriz de correla¸c˜ao do vetor desvio
Definimos o vetor de desvio como
v
n
= ˆw
n
− w
∗
(3.25)
De 3.23 temos
v
n
= ϕ
−1
n
n
i=1
λ
n−i
.u
i
e
i
(3.26)
Definimos a matriz de correla¸c˜ao do vetor desvio da seguinte forma
K
n
= E[v
n
v
T
n
] (3.27)
Substituindo 3.26 em 3.27 e notando que [ϕ
−1
n
]
T
= ϕ
−1
n
e [λ
n−i
]
T
= λ
n−i
, obtemos
K
n
= E
ϕ
−1
n
n
i=1
λ
n−i
.u
i
e
i
n
i=1
λ
n−i
e
T
i
u
T
i
ϕ
−1
n
(3.28)
Podemos observar em [2] que para o rigoroso c´alculo da Equa¸c˜ao 3.28 devemos
fazer as seguintes hip´oteses:
1. O vetor de entrada u
i
constitui amostras de um processo estat´ıstico. Assim,
podemos usar as m´edias do tempo ao inv´es do conjunto de m´edias.
2. O fator de esquecimento λ ´e muito pr´oximo de 1.
3. O tempo n o qual K
n
´e calculado ´e grande.
Notamos de 3.4 que ϕ
n
´e uma soma ponderada dos produtos externos
u
n
u
T
n
, u
n−1
u
T
n−1
, u
n−2
u
T
n−2
, ...
Assim, considerando as hip´oteses acima, encontramos
ϕ
n
≈
1 − λ
n
1 − λ
R (3.29)
19
sendo R = E[u
n
u
T
n
] a matriz de correla¸c˜ao do vetor de entrada.
Substituindo 3.29 em 3.28 e notando que E[e
n
e
T
n
] = σ
2
, obtemos
K
n
= σ
2
1 − λ
1 − λ
n
2
·
1 − λ
2n
1 − λ
2
R
−1
= σ
2
1 − λ
1 + λ
·
1 + λ
n
1 − λ
n
R
−1
(3.30)
3.3.3 Curva de apredizagem do algoritmo RLS
Para algoritmo RLS ´e conveniente usar o erro
n
para definir o Erro Quadr´atico
M´edio(mean-squared error-MSE), assim podemos expressar a curva de apendizagem
do algoritmo RLS em termos do erro a priori como
ξ
n
= E[
2
n
] (3.31)
sendo de 4.29 e 3.21 o erro a priori escrito da seguinte forma:
n
= e
n
− v
T
n−1
u
n
(3.32)
Substituindo 3.32 em 3.31 e espandindo os termos, obtemos
ξ
n
= E
e
2
n
+ E
u
T
n
v
n−1
v
T
n−1
u
n
− E
v
T
n−1
u
n
e
n
− E
e
n
u
T
n
v
n−1
(3.33)
O primeiro valor esp erado do lado direito da equa¸c˜ao 3.33 ´e simplesmente a
variˆancia de e
n
. Para os demais valores esperados podemos fazer as seguintes
observa¸c˜oes
1. A estimativa ˆw
n−1
, e portanto o vetor desvio v
n−1
, ´e independente do vetor
de entrada u
n
; o ´ultimo ´e assunido como sendo derivado de um processo
est´acionario de amplo sentido de m´edia zero. Consequentemente, podemos
usar esta independencia estat´ıstica junto com os resultados conhecidos de
20
´algebra matricial para expressar o segundo valor esperado do lado direito da
equa¸c˜ao 3.33 como segue-se:
E
u
T
n
v
n−1
v
T
n−1
u
n
= E
tr
u
T
n
v
n−1
v
T
n−1
u
n
= E
tr
u
T
n
u
n
v
n−1
v
T
n−1
= tr
E
u
T
n
u
n
E
v
n−1
v
T
n−1
= tr {RK
n−1
} (3.34)
sendo que na ´ultima linha utilizamos as defini¸c˜oes de m´edias da matriz de
correla¸c˜ao R = E[u
n
u
T
n
] e da matriz de correla¸c˜ao do vetor desvio K
n
=
E[v
n
v
T
n
].
2. O error de medi¸c˜ao e
n
depende do vetor de entrada u
n
; isto segue de uma
simpes manipula¸c˜ao da Equa¸c˜ao 3.21. O vetor desvio v
T
n−1
´e portanto
independente de u
n
e e
n
. Entretanto podemos mostrar que o terceiro valor
esperado do lado direito da Equa¸c˜ao 3.33 ´e zero reformulando isto como segue:
E
v
T
n−1
u
n
e
n
= E
v
T
n−1
.E [u
n
e
n
] (3.35)
Reconhecemos do princ´ıpio de ortogonalidade que todos os elementos do vetor
u
n
s˜ao ortogonais ao erro de medi¸c˜ao e
n
, isto ´e:
E
v
T
n−1
u
n
e
n
= 0 (3.36)
3. O quarto valor esperado do lado direito da Equa¸c˜ao 3.33 tem a mesma forma
matem´atica considerada no item 2. Entretanto podemos dizer que este valor
esperado ´e igual a zero:
E
e
n
u
T
n
v
n−1
= 0 (3.37)
21
Assim, reconhecendo que E[e
2
n
] = ξ
mim
, e usando os resultados das Equa¸c˜oes
3.34 at´e 3.37 em 3.33, obtemos a seguinte f´ormula para o erro quadr´atico m´edio no
algoritmo RLS :
ξ
n
= ξ
min
+ tr {RK
n−1
} (3.38)
sendo ξ
min
o m´ınimo MSE do filtro encontrado quando uma estimativa perfeita de
w
∗
´e calculada. Substituindo 3.30 em 3.38 obtemos
ξ
n
= ξ
min
+
1 − λ
1 + λ
·
1 + λ
n−1
1 − λ
n−1
· Lξ
min
(3.39)
Este resultado descreve a curva de aprendizagem do algoritmo RLS. Na figura 3.1
podemos ver uma curva t´ıpica de aprendizagem resultante do uso deste algoritmo.
Figura 3.1: Curva de aprendizagem do algoritmo RLS. Na horizontal temos o n´umero
de itera¸c˜oes e na vertical o erro.
3.3.4 Tempo de aprendizagem
A esta altura ´e instrutivo que fa¸camos uma an´alise do comportamento do
algoritmo RLS . O segundo termo do lado direito da Equa¸c˜ao 3.39 ´e um valor positivo
22
que indica o desvio de ξ
n
de ξ
min
. Notamos tamb´em que a velocidade a qual estes
termos convergem ´e determinada pelo termo exponencial λ
n−1
, ou equivalentemente
λ
n
. Desta forma, definimos o tempo de aprendizagem τ
RLS
associado com o
algoritmo RLS usando a seguinte equa¸c˜ao:
λ
n
= e
−n
τ
RLS
(3.40)
Resolvendo 3.40 para τ
RLS
obtemos
τ
RLS
= −
1
ln λ
(3.41)
Para simplificar 3.41 usaremos a seguinte aproxima¸c˜ao
ln λ = ln(1 − (1 − λ)) ≈ −(1 − λ) (3.42)
Substituindo 3.42 em 3.41 temos
τ
RLS
≈
1
(1 − λ)
(3.43)
Deste resultado, notamos que o comportamento da convergˆencia do algoritmo
RLS ´e independente dos autovalores da matriz de correla¸c˜ao das entradas.
3.3.5 Excesso do erro quadr´atico m´edio e o desajuste
Na figura 3.1, podemos ver que quando os pesos n˜ao s˜ao iguais a w
∗
, o erro
quadr´atico m´edio (ξ
n
) ´e maior que o erro quadr´atico m´edio m´ınimo (ξ
min
). Temos,
assim, um excesso no erro final
Definimos, ent˜ao, o excesso do erro quadr´atico m´edio, ExcessoMSE, como a
diferen¸ca entre o erro quadr´atico m´edio atual e o erro quadr´atico m´edio m´ınimo [2]:
ExcessoMSE = lim
n→∞
ξ
n
− ξ
min
(3.44)
Usando 3.39 e 3.44 obtemos
23
ExcessoMSE =
1 − λ
1 + λ
· Lξ
min
(3.45)
Definimos, tamb´em, o ExcessoMSE normalizado pelo erro quadr´atico m´edio
m´ınimo, como o desajuste M
RLS
.
M
RLS
=
ExcessoMSE
ξ
min
. (3.46)
Substituido 3.45 em 3.46 temos
M
RLS
=
1 − λ
1 + λ
· L (3.47)
sendo L o tamanho do filtro.
3.4 Conclus˜ao do Cap´ıtulo
Neste cap´ıtulo, realizou-se a dedu¸c˜ao do algoritmo RLS e descrevemos as
equa¸c˜oes que determinam sua condi¸c˜ao de convergˆencia. O tempo de aprendizagem
e o desajuste tamb´em s˜ao enfatizados, pois os mesmso s˜ao utilizados como referˆencia
comparativa de outros algoritmos adaptativos.
24
Cap´ıtulo 4
O Algoritmo Recursivo N˜ao
Linear - RNL
4.1 Introdu¸c˜ao
Neste cap´ıtulo desenvolveremos um algoritmo adaptativo baseado em fun¸c˜oes
n˜ao lineares inspirado no algoritmo RLS padr˜ao. Chamaremos esse novo algoritmo
de Recursivo N˜ao Linear, no qual escolhemos a fun¸c˜ao ε
n
=
M
j=1
n
i=1
λ
n−i
[e
i
]
2j
como
crit´erio a ser aplicado sobre o erro. O nosso objetivo ´e determinar um algoritmo que
ajuste os pesos do CLA de forma tal a minimizar esta fun¸c˜ao. Mostraremos, tamb´em,
que a superf´ıcie de desempenho obtida por este crit´erio oferece maior velocidade de
convergˆencia, bem como um menor desajuste na busca do peso m´ınimo.
4.2 Dedu¸c˜ao do algoritmo RNL
A fun¸c˜ao ε
n
=
M
j=1
n
i=1
λ
n−i
[e
i
]
2j
, sendo M e n inteiros positivos, ´e uma fun¸c˜ao
n˜ao linear, par, cont´ınua, sim´etrica, cujo gr´afico est´a representado na figura 4.1.
Esta fun¸c˜ao, como podemos ver, n˜ao tem m´ınimo local, apenas o m´ınimo global.
Uma outra caracter´ıstica dos elementos deste conjunto de fun¸c˜oes ´e que, para
um valor fixo de M, podemos determinar intervalos [−δ, δ] onde as curvas destas
fun¸c˜ao tˆem inclina¸c˜ao maior do que a curva da fun¸c˜ao quadr´atica, neste mesmo
intervalo. Podemos observar esta caracter´ıstica na figura (4.2), onde temos plotados
os gr´aficos das fun¸c˜oes ε
2
+ ε
4
+ ε
6
e ε
2
.
25
Figura 4.1: Por¸c˜ao da superf´ıcie gerada pela fun¸c˜ao ε
2
+ ε
4
+ ε
6
juntamente com
alguns contornos.
Figura 4.2: Gr´aficos das fun¸c˜oes ε
2
+ ε
4
+ ε
6
e ε
2
, onde podemos ver a maior
inclina¸c˜ao da primeira, no intervalo [−1; 1]
26
Para desenvolver o algoritmo RNL, utilizamos como fun¸c˜ao de custo a fun¸c˜ao
ε
n
=
M
j=1
n
i=1
λ
n−i
[e
i
]
2j
(4.1)
sendo M e n inteiros positivos e 0 << λ < 1 fator peso exponencial ou fator de
esquecimento.
Derivando a Equa¸c˜ao 4.1 em rela¸c˜ao a w, obtemos
∂ε
∂w
=
M
j=1
N
i=1
λ
n−i
. − u
i
.2j
d
i
− ˆw
T
n
u
i
2j−1
(4.2)
Desenvolvendo o binˆomio podemos reescrever 4.2 da seguinte forma
∂ε
∂w
≈ −
M
j=1
2j
N
i=1
λ
n−i
u
i
d
2j−1
i
+
M
j=1
2j (2j − 1)
N
i=1
λ
n−i
d
2j−2
i
u
i
u
T
i
w
n
(4.3)
Assim, o valor ´otimo do vetor peso, ˆw
n
, para que a fun¸c˜ao da Equa¸c˜ao 4.1 atinja
o valor m´ınimo ´e definido pela equa¸c˜ao normal escrita em forma matricial
[z
n,j
] − [φ
n,j
] . ˆw
n
= 0 (4.4)
sendo a matriz correla¸c˜ao do vetor de entrada de dimens˜ao L × L agora definida
por,
φ
n,j
=
M
j=1
j. (2j − 1)
N
i=1
λ
n−i
.d
2j−2
i
.u
i
u
T
i
(4.5)
E o vetor correla¸c˜ao cruzada entre as entradas do CLA e a resposta desejada ´e
definido por,
z
n,j
=
M
j=1
j
N
i=1
λ
n−i
.d
2j−1
i
.u
i
(4.6)
27
sendo L o tamanho do filtro adaptativo.
Isolando o termo corespondente a i = n da Equa¸c˜ao 4.5, podemos escrever
φ
n,j
=
M
j=1
j. (2j − 1)
n−1
i=1
λ
n−i
.d
2j−2
i
u
i
u
T
i
+
M
j=1
j. (2j − 1) d
2j−2
n
u
n
.u
T
n
= φ
n−1,j
+
M
j=1
j. (2j − 1) .d
2j−2
n
u
n
.u
T
n
(4.7)
Analogamente podemos escrever a Equa¸c˜ao 4.6 da seguinte forma
z
n,j
= z
n−1,j
+
M
j=1
j.d
2j−1
n
u
n
(4.8)
4.2.1 O algoritmo RNL ponderado exponencialmente
Como a matriz de correla¸c˜ao ´e positivamente definida e n˜ao singular, podemos
aplicar o lema de invers˜ao de matrizes para equa¸c˜ao recursiva 4.5. Primeiramente
faremos as seguintes identifica¸c˜oes:
A = ϕ
n,j
B
−1
= ϕ
n−1,j
→ B = [ϕ
n−1,j
]
−1
C = u
n
D
−1
=
M
j=1
{j. (2j − 1) d
2j−2
n
}
(4.9)
Substituindo as defini¸c˜oes 4.9 na equa¸c˜ao 3.9, obtemos a rela¸c˜ao de recursividade
da matriz ϕ
n,j
, ou seja:
[ϕ
n,j
]
−1
= [ϕ
n−1,j
]
−1
−
[ϕ
n−1,j
]
−1
u
n
u
T
n
[ϕ
n−1,j
]
−1
D + u
T
n
[ϕ
n−1,j
]
−1
u
n
(4.10)
Por conveniˆencia computacional podemos escrever as seguintes igualdades:
P
n,j
= [ϕ
n,j
]
−1
(4.11)
k
n,j
=
P
n−1,j
u
n
1
α
1
+ u
T
n
P
n−1,j
u
n
(4.12)
28
sendo α
1
=
M
j=1
{j. (2j − 1) d
2j−2
n
}
Podemos reescrever a equa¸c˜ao 4.10 como segue:
P
n,j
= P
n−1,j
− k
n,j
u
T
n
P
n−1,j
(4.13)
sendo P
n,j
a inversa da matriz de auto-correla¸c˜ao de dimens˜ao L × L e k
n,j
o vetor
ganho de dimens˜ao L × 1. Reorganizando a equa¸c˜ao 4.12, temos:
k
n,j
1
α
1
+ k
n,j
u
T
n
P
n−1,j
u
n
= P
n−1,j
u
n
k
n,j
1
α
1
=
P
n−1,j
− k
n,j
u
T
n
P
n−1,j
u
n
(4.14)
Substituindo a equa¸c˜ao 4.13 em 4.14 seque-se:
k
n,j
1
α
1
= P
n,j
u
n
k
n,j
1
α
1
= [ϕ
n,j
]
−1
u
n
(4.15)
4.2.2 Atualiza¸c˜ao do vetor peso
No desenvolvimento de uma equa¸c˜ao recursiva utilizaremos as Equa¸c˜oes 4.4, 4.8
e 4.11 para expressar a estimativa ˆw
n
do vetor peso no instante n como segue:
ˆw
n
= P
n,j
[z
n−1,j
+ α
2
u
n
]
ˆw
n
= P
n,j
z
n−1,j
+ α
2
P
n
u
n
(4.16)
sendo α
2
=
M
j=1
{jd
2j−1
n
}
Substituindo a equa¸c˜ao 4.13 na equa¸c˜ao 4.16, temos:
ˆw
n
= P
n−1,j
z
n−1,j
− k
n,j
u
T
n
.P
n−1,j
z
n−1,j
+ α
2
· k
n,j
·
1
α
1
(4.17)
29
Das equa¸c˜oes 4.15 e 4.17, segue-se:
ˆw
n
= ˆw
n−1
− k
n
n
(4.18)
sendo
n
a estimativa do erro definida por:
n
= α
2
.
1
α
1
− u
T
n
. ˆw
n−1
= d
n
− u
T
n
. ˆw
n−1
(4.19)
4.2.3 Resumo do algoritmo RNL
Podemos observar que o algoritmo RNL ´e dado pela seq¨uˆencia c´ıclica da sequintes
equa¸c˜oes:
k
n,j
=
P
n−1,j
u
n
1
α
1
+ u
T
n
P
n−1,j
u
n
(4.20)
sendo α
1
=
M
j=1
{j. (2j − 1) d
2j−2
n
}
P
n,j
=
P
n−1,j
−
k
n,j
u
T
n
P
n−1,j
(4.21)
ˆw
n
= ˆw
n−1
− k
n
n
(4.22)
sendo
n
a estimativa do erro definida por:
n
= α
2
.
1
α
1
− u
T
n
. ˆw
n−1
(4.23)
sendo α
2
=
M
j=1
{jd
2j−1
n
}
30
4.3 Convergˆencia do algoritmo RNL
Estudaremos nesta se¸c˜ao a convergencia do algoritmo RNL no contexto de um
problema de modelagem de sistema, da mesma forma que estudamos a convergˆencia
do algoritmo RLS no cap´ıtulo anterior.
4.3.1 O comp ortamento m´edio do vetor peso no algoritmo
RNL
Consideramos um regressor multiplo linear caracterizado pela equa¸c˜ao
d
n
= e
n
+ w
T
∗
u
n
(4.24)
sendo w
∗
o vetor peso do regressor, u
n
o vetor entrada, e
n
´e o ruido da planta e d
n
a sa´ıda da planta. O erro de medi¸c˜ao e
n
do processo ´e branco com m´edia zero e
variˆancia σ
2
De 4.4 e 4.6 obtemos a seguinte equa¸c˜ao:
ˆw
n
= [ϕ
n,j
]
−1
.
M
j=1
j.
n
i=1
λ
n−i
.u
i
.d
2j−1
i
(4.25)
Substituindo 4.24 em 4.25, temos
ˆw
n
= [ϕ
n,j
]
−1
.
M
j=1
j.
n
i=1
λ
n−i
.u
i
.
w
T
∗
u
i
+ e
i
2j−1
(4.26)
Utilizando desenvoldimento Binomial, podemos reescrever a Equa¸c˜ao 4.26 como
ˆw
n
= w
∗
+ [ϕ
n,j
]
−1
.
M
j=1
j.
n
i=1
λ
n−i
.u
i
.e
2j−1
i
(4.27)
Aplicando o operador esperan¸ca em ambos os membros da Equa¸c˜ao 4.27 e
reconhecemos do princ´ıpio de ortogonalidade que todos os elementos do vetor u
n
s˜ao ortogonais ao erro e
n
, obtemos
E [ ˆw
n
] = w
∗
(4.28)
31
4.3.2 Matriz de correla¸c˜ao do vetor desvio
Definimos o vetor desvio como
v
n
= ˆw
n
− w
∗
(4.29)
De 4.27 temos
v
n
= [ϕ
n,j
]
−1
·
M
j=1
j ·
n
i=1
λ
n−i
· u
i
· e
2j−1
i
(4.30)
Definimos a matriz de correla¸c˜ao do vetor desvio da seguinte forma
K
n
= E[v
n
v
T
n
] (4.31)
Substituindo 4.30 em 4.31 e notando que
[ϕ
n,j
]
−1
T
= [ϕ
n,j
]
−1
e (λ
n−i
)
T
= λ
n−i
,
obtemos
K
n
= E
[ϕ
n,j
]
−1
·
M
j=1
j ·
n
i=1
λ
n−i
· u
i
· e
2j−1
i
·
M
j=1
j ·
n
i=1
λ
n−i
·
e
2j−1
i
T
u
T
i
· [ϕ
n,j
]
−1
(4.32)
Expandindo os somat´orios da Equa¸c˜ao 4.32 e notando que o erro de medi¸c˜ao
neste processo ´e um ruido branco, segue-se
K
n
= σ
2
· E
[ϕ
n,j
]
−1
· (U
n
Λ
2
n
U
T
n
) · [ϕ
n,j
]
−1
(4.33)
sendo Λ
n
uma matriz diagonal formada pelos fatores exponencias 1, λ, λ
2
, ...,.
Definimos tamb´em a matriz das amostras de entrada como
U
n
= [u
1
u
2
... u
n
] (4.34)
32
Podemos observar em [2] que para o rigoroso c´alculo da Equa¸c˜ao 4.33 devemos
fazer as seguintes hip´oteses:
1. O vetor de entrada u
i
constitui amostras de um processo estat´ıstico. Assim,
podemos usar as m´edias do tempo ao inv´es do conjunto de m´edias.
2. O fator de esquecimento λ ´e muito pr´oximo de 1.
3. O tempo n o qual K
n
´e calculado ´e grande.
Assim, considerando as hip´oteses acima, encontramos que,
U
n
Λ
n
U
T
n
≈
1 − λ
n
1 − λ
R (4.35)
Analogamente, podemos reescrever a Equa¸c˜ao 4.5 como
ϕ
n,j
≈
1 − λ
n
1 − λ
R · β (4.36)
sendo β =
M
j=1
[j(2j − 1) · d
2j−2
n
]
Substituindo 4.35 e 4.36 em 4.33 obtemos
K
n
= σ
2
·
E
1 − λ
1 − λ
n
R
−1
·
1
β
1 − λ
2n
1 − λ
2
R · β
1 − λ
1 − λ
n
R
−1
·
1
β
= σ
2
·
1
β
·
1 − λ
1 + λ
·
1 + λ
n
1 − λ
n
R
−1
(4.37)
4.3.3 Curva de apredizagem do algoritmo RNL
Para algoritmo RNL podemos expressar a curva de apendizagem em termos do
erro
n
como
ξ
n
=
M
j=1
E
|
n
|
2j
(4.38)
sendo M inteiro positivo.
33
Usando 4.29 e 4.24, obtemos
n
= e
n
− v
T
n−1
u
n
(4.39)
sendo v
n−1
o vetor desvio no instante n − 1.
Substituindo a Equa¸c˜ao 4.39 em 4.38, temos
ξ
n
=
M
j=1
E
e
n
− v
T
n−1
u
n
2j
=
M
j=1
E
−v
T
n−1
u
n
+ e
n
2j
(4.40)
Utilizando desenvolvimento Binomial e notando que v ´e pr´oximo de zero
podemos desconsiderar os termos de alta potˆencia de v. Assim, reescrevemos a
Equa¸c˜ao 4.40 da seguinte forma:
ξ
n
≈
M
j=1
E
|e
n
|
2j
+ j(2j − 1)E
|e
n
|
2j−2
.E
u
T
n
v
n−1
v
T
n−1
u
n
−
−jE
(v
T
n−1
u
n
)(e
n
)
2j−1
− jE
(u
T
n
v
n−1
)(e
n
)
2j−1
(4.41)
O primeiro valor esperado do lado direito da equa¸c˜ao 4.41 definimos como sendo
o momento 2j de e
n
ou simplesmente a variˆancia de e
n
. Para os demais valores
esperados, relembrado o princ´ıpio de ortogonalidade, podemos fazer as mesmas
observa¸c˜oes utilizadas pro algoritmo RLS. Desta forma, obtemos da 4.41
ξ
n
= σ
2
+
M
j=1
j(2j − 1)σ
2
.tr {RK
n−1
}
(4.42)
Substituindo 4.37 em 4.42, obtemos
ξ
n
= σ
2
+
M
j=1
j(2j − 1)σ
2
·
1 − λ
1 + λ
·
1 + λ
n−1
1 − λ
n−1
· L ·
1
β
· σ
2
(4.43)
Fazendo a expan¸c˜ao do somat´orio e notando que E[e
4
n
] = 0, reescrevemos 4.43
34
ξ
n
= σ
2
+
1 − λ
1 + λ
·
1 + λ
n−1
1 − λ
n−1
· L ·
1
β
· σ
2
(4.44)
Assim, reconhecendo que σ
2
= E[e
2
n
] = ξ
mim
´e o m´ınimo MSE do filtro encontrado
quando uma estimativa perfeita de w
∗
´e calculada, obtemos a seguinte f´ormula para
o erro quadr´atico m´edio no algoritmo RNL:
ξ
n
= ξ
mim
+
1 − λ
1 + λ
·
1 + λ
n−1
1 − λ
n−1
· L ·
1
β
· ξ
mim
(4.45)
sendo β =
M
j=1
[j(2j − 1) · d
2j−2
n
]
Este resultado descreve a curva de aprendizagem do algoritmo RNL. Na figura 4.3
podemos ver uma curva t´ıpica de aprendizagem resultante do uso deste algoritmo.
Figura 4.3: Curva de aprendizagem do algoritmo RNL. Na horizontal temos o
n´umero de itera¸c˜oes e na vertical o erro.
4.3.4 An´alise do tempo de aprendizagem
Nesta se¸c˜ao faremos uma an´alise comparativa entre as constantes de tempo
associadas ao algoritmo RLS e ao RNL.
35
Analogamente `a an´alise feita na dedu¸c˜ao da constante de tempo do RLS, no
cap´ıtulo anterior, podemos verificar que a velocidade na qual o segundo termo termo
do lado direito da Equa¸c˜ao 4.45 ´e um valor positivo que indica o desvio de ξ
n
de
ξ
min
. Notamos tamb´em que a velocidade a qual este termo converge ´e determinada
pelo termo exponencial
1
β
· λ
n−1
, ou equivalentemente
1
β
· λ
n
. Desta forma, definimos
a constante de tempo τ
RN L
associado com o algoritmo RNL usando a seguinte
equa¸c˜ao:
e
−n
τ
RN L
=
1
β
· λ
n
(4.46)
Resolvendo 4.46 para τ
RN L
obtemos
1
τ
RN L
= − ln λ +
ln β
n
(4.47)
Infelizmente a express˜ao dada em 4.47 n˜ao nos premite definir explicitamente o
valor da constante de tempo τ
RN L
. Entretanto, ela ´e ´util para fazermos uma an´alise
comparativa entre τ
RN L
e τ
RLS
. De fato, lembrando que
τ
RLS
= −
1
ln λ
(4.48)
ent˜ao
1
τ
RLS
= − ln λ (4.49)
Da´ı a Equa¸c˜ao 4.47 pode ser reescrita na forma
1
τ
RN L
=
1
τ
RLS
+
ln β
n
(4.50)
sendo β =
M
j=1
[j(2j − 1) · d
2j−2
n
] positivo,
ent˜ao a express˜ao
ln β
n
tamb´em ´e positiva. Desta forma podemos afirmar que
τ
RN L
< τ
RLS
(4.51)
36
4.3.5 Excesso do erro quadr´atico m´edio e o desajuste
Na figura 4.3, podemos ver que quando os pesos n˜ao s˜ao iguais a w
∗
, o erro
quadr´atico m´edio (ξ
n
) ´e maior que o erro quadr´atico m´edio m´ınimo (ξ
min
). Temos,
assim, um excesso no erro final
Definimos, ent˜ao, o excesso do erro quadr´atico m´edio, ExcessoMSE, como a
diferen¸ca entre o erro quadr´atico m´edio atual e o erro quadr´atico m´edio m´ınimo [2]:
ExcessoMSE = lim
n→∞
ξ
n
− ξ
min
(4.52)
Usando 4.45 e 4.52 obtemos
ExcessoMSE =
1 − λ
1 + λ
·
1
β
· Lξ
min
(4.53)
Definimos, tamb´em, o ExcessoMSE normalizado pelo erro quadr´atico m´edio m´ınimo,
da Equa¸c˜ao 4.45 como o desajuste M
RN L
.
M
RN L
=
1 − λ
1 + λ
·
1
β
· L (4.54)
sendo β =
M
j=1
[j(2j − 1) · d
2j−2
n
] e L o tamanho do filtro.
4.4 Conclus˜oes do Cap´ıtulo
Neste cap´ıtulo, descrevemos a id´eia b´asica da utiliza¸c˜ao de estat´ıstica de alta
ordem como uma forma de obten¸c˜ao de mais informa¸c˜oes sobre os sinais envolvidos
em um processo adaptativo. Desenvolvimento de um novo algoritmo inspirado no
algoritmo RLS, que utiliza como crit´erio aplicado sobre o erro uma fun¸c˜ao n˜ao linear,
a qual queremos minimizar. Isto origina o algoritmo Recursivo N˜ao Linear - RNL.
Deduzimos equa¸c˜oes que determinam sua condi¸c˜ao de convergˆencia. O tempo de
aprendizagem e o desajuste tamb´em s˜ao enfatizados.
37
Cap´ıtulo 5
Resultados e Discuss˜oes
5.1 Introdu¸c˜ao
Objetivando verificar a exatid˜ao das equa¸c˜oes deduzidas no cap´ıtulo anterior,
fizemos simula¸c˜oes, onde comparamos os desempenhos dos algoritmos RLS e RNL.
5.2 Simula¸c˜oes com o algoritmo RNL
Em nossa simula¸c˜ao verificamos que o novo algoritmo trabalha corretamente
na identifica¸c˜ao de um pequeno filtro FIR, como mostra a Figura 5.1. Este filtro ´e
caracterizado pela resposta impulso h. O sinal de entrada, u
i
, foi simulado como um
sinal aleat´orio uniformemente distribu´ıdo, limitado no intervalo [−1, 1]. Filtramos
este sinal por h obtendo o sinal desejado d
i
.
Na figura 5.2 podemos visualizar a curva de aprendizagem do algoritmo RLS e
as curvas de aprendizagens do algoritmo RNL com 2 termos e com 4 termos.
5.3 Discuss˜oes
Um novo algoritmo foi introduzido para ajustar os pesos de um filtro adaptativo
tal que o valo esperado do erro de grau 2j, sendo j inteiro positivo deve ser
minimizado. O desenvolvimento deste algoritmo adaptativo foi baseado em fun¸c˜oes
n˜ao lineares inspirado no algoritmo Recursive Lest Square (RLS) proposto por
Haykin [1]. Derivamos `a Equa¸c˜ao 4.1 e desemvolvemos a Equa¸c˜ao 4.4 para obter
o valor ´otimo do vetor peso w
n
. A estrutura de atualiza¸c˜ao do algoritmo RNL ´e
dada pela Equa¸c˜ao 4.18. A partir das express˜oes 3.47 e 4.54 podemos observar que
38
Figura 5.1: Diagrama de blocos de um filtro FIR de tamnho L = 15, usando o
algoritmo RNL para adapta¸c˜ao dos pesos
o desajuste do novo algoritmo ´e basicamente o mesmo do RLS padr˜ao, com m´erito
de apresentar um tempo de aprendizagem menor. Vale observar que quanto maior
for o valor de M na equa¸c˜ao 4.1 esta contante de tempo diminui.
5.4 Conclus˜oes do Cap´ıtulo
O algoritmo RNL, conforme proposto, mostrou uma melhora no desempenho
quando comparado com o RLS. Melhora esta que mostrou-se dependente da
quantidade de termos M, ou seja, ao aumentarmos a quantidade de termos,
conseguentemente, aumentando a inclina¸c˜ao da superf´ıcie de desempenho, isto
pode ser observado na figura 5.2. O algoritmo RNL aumenta a velocidade de
convergˆencia dos pesos com basicamente o mesmo desajuste, por´em com um tempo
de aprendizagem menor.
39
Figura 5.2: Curvas de aprendizagem dos algoritmos RLS e o algoritmo proposto
RNL.
40
Cap´ıtulo 6
Conclus˜oes e Proposta de
Continuidade
6.1 Conclus˜oes
A utiliza¸c˜ao de estat´ıstica de alta ordem, como uma forma de obten¸c˜ao de
mais informa¸c˜oes sobre sinais, tem-se demostrado de grande valia em sistemas
adaptativos. Neste trabalho desenvolvemos um filtro adaptativo, inspirado no RLS,
onde mostramos uma an´alise matem´atica para descrever a aplica¸c˜ao de fun¸c˜oes
n˜ao lineares, pares e cont´ınuas, como crit´erio aplicado sobre o erro. As equa¸c˜oes
obtidas mostraram-se adequadas e atrav´es de simula¸c˜oes obtemos a indica¸c˜ao de
sua veracidade.
Nas simula¸c˜oes, o algoritmo RNL mostrou-se mais eficiente quando comparado
com o RLS padr˜ao definido em [1]. Esta eficiˆencia acentua-se ao aumentarmos a
inclina¸c˜ao da superf´ıcie de desempenho.
6.2 Proposta de Continuidade
O desenvolvimento matem´atico aqui apresentado, foi baseado nas caracter´ısticas
das superf´ıcies de desempenho geradas pelas n˜ao linearidades aplicadas sobre o erro.
Baseado nesta id´eia alguns t´opicos de pesquisa podem ser identificados, tais como:
• Utiliza¸c˜ao de processos geom´etricos na determina¸c˜ao de fun¸c˜oes n˜ao lineares
a serem aplicadas como crit´erio sobre o erro;
• Desenvolvimento de equa¸c˜oes mais adequadas para o tempo de aprendizagem
41
e o desajuste;
• Estudos mais aprofundados sobre o tempo de aprendizagem.
• Evolu¸c˜ao para o filtro de Kalman.
• Aplica¸c˜oes do algoritmo proposto.
42
Referˆencias Bibliogr´aficas
[1] S. Haykin, ”Adaptive filter theory”. Englewood Cliffs, NJ: Pentice-Hall, 1991.
[2] B. Farhang-Boroujeny, ”Adaptive Filter Theory and Application”. John Wiley
e Sons, 1998.
[3] Ljung L., Morf M. and Falconer D., ”Fast calculation of gain matrices for
recursive estimation schemes”, International Journal of Control, Vol 27, No 1,
pp 1-19, Jan 1978.
[4] Carayannis G., Manolakis D. and Kalouptsidis N. ”A fast sequential algorithm
for Least-Square filter and prediction”, IEEE Transactions on ASSP, Vol ASSP-
31, pp 1392-1402, Dec 1983.
[5] Chansarkar M., Desai U. and Rao B. ”Comparison of Approximate RLS
algorithm with LMS and RLS algorithms”, Proceedings of IEEE Region 10
Conference TENCON-89, Bombay, 1989.
[6] Cioffi J. and Kailath T. ”Fast recursive least squares filter for adaptive filtering”,
IEEE Transactions on ASSP, Vol ASSP-32, pp 304-337, 1984.
[7] A. K. Barros, J. Principe, Y. Takeuchi, C. H. Sales, and N. Ohnishi, ”An
algorithm based on the even moments of the error,”in Proc. 8th Workshop on
Neural Networks for Signal Processing, Toulouse, France, 2003, pp. 879-885
[8] Ewaldo E. C. Santana, Y. Yasuda, Y. Takeuchi, A.K. Barros. ”Adaptive
Estimation of Impedance Cardiographic Signal by the Sigmoidal Algorithm”.
Proceedings of the Fifth International Workshop on Biosignal Interpretation,
September 6-8, Tokyo Japan. 2005.
43
[9] E. Walach, B. Widrow, ”The Lest Mean Fourth (LMF) Adaptive Algorithm
and Its Family”. IEEE Transactions on Information Theory No. 2, 1984.
44
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
