Upload
internet
View
108
Download
5
Embed Size (px)
Citation preview
Ajuste de Dados através do Uso de Modelos Lineares
Prof. Júlio Cesar Nievola
PPGIA - PUCPR
PPGIA - PUCPR Prof. Júlio Cesar Nievola 2
Construção de Modelo Experimental
Ajuste de dados é uma das ciências experimentais
mais antigas
Vantagens de um modelo matemático: Habilidade de compreender, explicar, prever e controlar
a saída do sistema
Principal vantagem: capacidade de prever o
comportamento futuro e controlá-lo através da
aplicação de entradas apropriadas
PPGIA - PUCPR Prof. Júlio Cesar Nievola 3
Sistemas Naturais eModelos Formais
SistemaNatural
Observável
ModeloFormal
Prever
Decodificar
Medidas
Mundo Natural
MundoMatemático
PPGIA - PUCPR Prof. Júlio Cesar Nievola 4
Coleta de Dados
Deve ser cuidadosamente planejada
Principais pontos a serem observados:
Os dados devem ser suficientes
Os dados devem capturar as características principais
do problema a ser tratado
Os dados devem ser tão “limpos” quanto possível
PPGIA - PUCPR Prof. Júlio Cesar Nievola 5
Adaline - Regressão Linear
Adaline - Adaptive Linear Element, ou elemento de
processamento (PE)
Composto por dois multiplicadores e um somador
b
wxi
+1
yi
PEExemplo 01
PPGIA - PUCPR Prof. Júlio Cesar Nievola 6
Mínimos Quadrados
Uma reta ajusta perfeitamente duas observações
Qual a melhor escolha de (w, b) tal que uma reta
passe mais próxima de vários pontos?
Mínimos Quadrados: reta em que a soma do
quadrado dos desvios (resíduos) na direção d é
minimizada
Mínimos Quadrados: regressão linear
PPGIA - PUCPR Prof. Júlio Cesar Nievola 7
Determinação dos Parâmetros (1)
A média da soma dos erros ao quadrado,
denominado J (também chamado de MSE), que é
um dos critérios mais usados, é dado por:
onde N é o número de observações
N
iiN
J1
2
2
1
Exemplo 02
PPGIA - PUCPR Prof. Júlio Cesar Nievola 8
Determinação dos Parâmetros (2)
Para minimizar J, usando Gauss, igualam-se as
derivadas parciais a zero e resolve-se as equações,
ou seja:
Obtém-se então:
e
00
w
Je
b
J
ii
iii
ii
ii
ii
xxN
dxxdxb
2
2
ii
iii
xx
ddxxw 2
Exemplo 03
PPGIA - PUCPR Prof. Júlio Cesar Nievola 9
Coeficiente de Correlação
Por definição, o coeficiente de correlação entre
duas variáveis aleatórias x e d é
O numerador é a covariância das duas variáveis e
o denominador é o produto dos correspondentes
desvio padrão
N
xx
N
dd
N
ddxx
r
ii
ii
iii
22
PPGIA - PUCPR Prof. Júlio Cesar Nievola 10
Método dos Mínimos Quadrados
Interpretação da solução estimada dos mínimos
quadrados: o erro é ortogonal à entrada
Mínimos quadados: bastante potente
Pode ser generalizado para curvas polinomiais de
ordem superior, tal como quadráticas, cúbicas etc.,
dando origem aos mínimos quadrados
generalizados
PPGIA - PUCPR Prof. Júlio Cesar Nievola 11
Mínimos Quadrados como Busca de Parâmetros de um Sistema
Objetivo: encontrar os parâmetros (b,w) que
minimizam a diferença entre a saída yi do sistema
e a resposta desejada di.y
x
b
y=wx+b
. .. .
. .d1
d2
di
x1 x2 xi
Alterarparâmetros
+xi yi
di
(b,w)-
i
PPGIA - PUCPR Prof. Júlio Cesar Nievola 12
Proejto de um Sistema Supervisionado Adaptativo
Elementos Sistema (linear) com parâmetros adaptativos
Resposta desejada ou objetivo d
Critério de otimalidade (MSE) a ser minimizado
Método para calcular os parâmetros ótimos
O objetivo é encontrar uma forma alternativa de
calcular os parâmetros usando um procedimento
de busca
PPGIA - PUCPR Prof. Júlio Cesar Nievola 13
Análise do Erro no Espaço de Parâmetros
J(w) é chamada de superfície de desempenho. Para
b=0:
i
iiiii
ii dwxdwxN
wxdN
J 2222 22
1
2
1
J
w
Jmin
w*
Superfície de desempenho
Exemplo 04
PPGIA - PUCPR Prof. Júlio Cesar Nievola 14
Gradiente da Superfície de DesempenhoO gradiente de J é um vetor que sempre aponta na
direção da máxima alteração de J com magnitude igual à inclinação da tangente à superfície de desempenho
No ponto inferior (vértice), o gradiente é zero
w* w
Jmin
Superfície de desempenho
w0
w0-w
w0+w
Magnitude do gradiente
w
wwJwwJJ
wwo
2lim 00
0
PPGIA - PUCPR Prof. Júlio Cesar Nievola 15
Superfície de Performance - Notas
O valor mínimo do erro (Jmin) depende tanto da sinal
de entrada (xi) quanto do sinal desejado (di)
A posição no espaço de coeficientes onde o mínimo
w* ocorre também depende tanto de xi quanto de di
O formato da superfície de desempenho depende
somente do sinal de entrada xi
Exemplo 05
PPGIA - PUCPR Prof. Júlio Cesar Nievola 16
Busca usando Descida mais inclinadaBusca eficiente do mínimo usando vários métodos
baseados na informação do gradienteVantagens da busca:
Computação local O gradiente sempre indica a direção de máxima
alteraçãoPara o cálculo dos pesos em uma nova posição:
onde é uma pequena constante e J(k) indica o gradiente da superfície de desempenho na iteração k
kJkwkw 1
PPGIA - PUCPR Prof. Júlio Cesar Nievola 17
Busca usando a informação do gradiente
w
Jmin
w*
Superfície de desempenho
w(0)... ...w(1)
Vetor Gradiente
PPGIA - PUCPR Prof. Júlio Cesar Nievola 18
Estimativa do Gradiente:Algoritmo LMS
Um sistema adaptativo pode usar a informação do
gradiente para otimizar os parâmetros
Em 1960 Widrow propôs o uso do valor
instantâneo como estimativa do valor do
gradiente:
kxkkkwNkw
Jkw
kJ i
22
2
1
2
1
PPGIA - PUCPR Prof. Júlio Cesar Nievola 19
Algoritmo LMS
Usando a idéia de Widrow tem-se o algoritmo LMS, no qual o gradiente é estimado usando uma multiplicação por peso
A equação da descida (ou LMS) torna-se
onde a constante é chamada de tamanho do passo ou constante de aprendizagem
kxkkwkw 1
Exemplo 06
PPGIA - PUCPR Prof. Júlio Cesar Nievola 20
Aprendizagem On-line e Batch
Aprendizagem on-line ou exemplo por exemplo:
atualização dos pesos após o cálculo para cada
entrada
Aprendizagem batch: armazenam-se as
atualizações dos pesos durante uma época e no
final da mesma atualizam-se os mesmos
O algoritmo batch é ligeiramente mais eficiente
em termos do número de cálculos Exemplo 07
PPGIA - PUCPR Prof. Júlio Cesar Nievola 21
Robustez e avaliação do treinamento
O algoritmo LMS é robusto: sempre converge para o mesmo valor, independentemente dos pesos iniciais
Após o treinamento, os pesos são fixados para usoPrecisa-se do coeficiente de correlação r e do MSE
para testar os resultados: r informa é um indicador do resultado da modelagem,
dizendo o quanto da variância de d foi capturado pela regressão linear, mas não indica a média
o MSE indica a ordem de grandeza
Exemplo 08
Exemplo 09
PPGIA - PUCPR Prof. Júlio Cesar Nievola 22
Adaptação EstávelO algoritmo LMS tem um parâmetro livre, , que
deve ser selecionado pelo usuárioO gráfico do MSE ao longo das iterações é
chamado de curva de aprendizagem e é uma boa forma de monitorar a convergência do processo
A taxa de decréscimo do erro depende do valor do tamanho do passo
Busca-se uma forma de encontrar o maior tamanho de passo possível que garanta convergência Exemplo 10
PPGIA - PUCPR Prof. Júlio Cesar Nievola 23
Curva de Aprendizagem e Gráfico dos Pesos ao longo das iterações
Exemplo 11
PPGIA - PUCPR Prof. Júlio Cesar Nievola 24
Tamanho máximo do passo para convergência
Convergência rápida, mas sem sistema instável:
Na atualização batch, usa-se o passo normalizado:
No algoritmo LMS é comum incluir um fator de
segurança 10 no máximo ( máx) ou usar o
treinamento em batch, o qual reduz o ruído na
estimativa do gradiente
i
ixN
onde 2max
1,
2
Nn
PPGIA - PUCPR Prof. Júlio Cesar Nievola 25
Constantes de tempo
A envoltória da progressão geométrica dos valores dos pesos pode ser aproximado por uma exponencial com decréscimo dado pela constante de tempo de adaptação dos pesos :
Em termos práticos, o processo iterativo converge após 4 constantes de tempo
A constante de tempo da adaptação mse é:
1
2
mse
Exemplo 12
PPGIA - PUCPR Prof. Júlio Cesar Nievola 26
Estabilidade
Na busca em pontos próximos ao mínimo: o gradiente é pequeno mas não zero
o processo continua a se movimentar na vizinhança do
mínimo, sem estabilizar
Rattling: é proporcional ao tamanho do passo Nos mecanismos de busca com descida do
gradiente há um compromisso entre a precisão da
solução final e a velocidade de convergência
PPGIA - PUCPR Prof. Júlio Cesar Nievola 27
“Rattling” no procedimento iterativo
Exemplo 13
PPGIA - PUCPR Prof. Júlio Cesar Nievola 28
Escalonamento do tamanho dos passosForma simples de diminuir o “rattling”:
constante de aprendizagem grande no começo do processo para rápida convergência
pequena constante de aprendizagem no final do processo para obter boa exatidão
Escalonamento da taxa de aprendizagem:
O valor de precisa ser determinado experimentalmente
kk 1
Exemplo 14
PPGIA - PUCPR Prof. Júlio Cesar Nievola 29
Regressão para várias variáveisConsidere-se que d é uma função de várias
entradas x1, x2, ..., xD (variáveis independentes) e o objetivo é encontrar a melhor regressão linear de d em relação a todas as entradas
Assume-se que as medidas x são livres de ruído e d é contaminado por um vetor de ruídos com as propriedades:
distribuição Gaussiana com componentes com média zero
variâncias 2 igual não correlacionada com as entradas
PPGIA - PUCPR Prof. Júlio Cesar Nievola 30
..
Várias variáveis
+.
x1i
x2i
xDi
+1
w1
w2
wD
b
di
i
yi
Sistema de Regressão
PPGIA - PUCPR Prof. Júlio Cesar Nievola 31
Regressão para várias variáveis (1)
A equação para regressão com várias variáveis é
Neste caso o MSE é
A solução para esta equação (ponto de mínimo) é obtida
igualando a zero as derivadas de J com relação às variáveis
desconhecidas wk
Com isto, tem-se um conjunto de D+1 equações com D+1
variáveis, chamado equações normais (conforme a seguir)
NixwdxwbdD
kikki
D
kikkii ,...,1,
01
i
D
kikki xwd
NJ
2
02
1
PPGIA - PUCPR Prof. Júlio Cesar Nievola 32
Regressão para várias variáveis (2)
Estas equações podem ser escritas em notação matricial. Para tanto, define-se
Rkj é a auto-correlação das amostras de entrada para os índices k e j, a qual mede a similaridade entre exemplos do conjunto de treinamento
Tem-se então a matriz de auto-correlação
Djxxwdxi
ijik
D
kk
iiij ,...,1,0,
0
i
ijikkj xxN
R1
DDD
D
RR
RR
R
0
000
PPGIA - PUCPR Prof. Júlio Cesar Nievola 33
Regressão para várias variáveis (3) Considere-se
como sendo a correlação cruzada da entrada x para índice j e a resposta desejada d. A partir da mesma cria-se o vetor p de dimensão D+1. Portanto,
O coeficiente de correlação múltipla mede a quantidade de variação explicada pela regressão linear, normalizada pela variância de d
i
iijj dxN
p1
pRwouwRp 1**
2
2*
dNdd
dNdUwr
Tx
T
m
Exemplo 15
PPGIA - PUCPR Prof. Júlio Cesar Nievola 34
Superfície de desempenho para duas dimensões e gráfico de contorno
PPGIA - PUCPR Prof. Júlio Cesar Nievola 35
Visão do Procedimento de Busca A superfície de desempenho em várias dimensões de J
torna-o um parabolóide apontando para cima em D+1 dimensões:
Os coeficientes que minimizam a solução são
A auto-correlação das entradas R especifica de forma completa a superfície de desempenho
A localização da superfície de desempenho no espaço de pesos e o seu valor mínimo dependem a auto-correlação das entradas e da resposta desejada
i
TT
N
dwpRwwJ i
25,0
2
pRwoupRwJ 1**0
Exemplo 16
PPGIA - PUCPR Prof. Júlio Cesar Nievola 36
Gráfico de contornos da superfície de desempenho com dois pesos
w1*
Direção do maiorautovetor de Rw2
w1
w2*
Direção do menorautovetor de R
Gráficos de contorno de J
Inverso da diferençaé o maior autovalor de R
Inverso da diferençaé o menor autovalor de R
PPGIA - PUCPR Prof. Júlio Cesar Nievola 37
Descida mais inclinada no caso de vários pesos
Neste caso o gradiente é um vetor com D+1 componentes
Portanto,
Ou seja,
Os pesos convergem com diferentes constantes de tempo, cada uma ligada a um autovalor de R
T
Dw
J
w
JJ
,,0
kJkwkw 1
*RRI1 wkwkw
PPGIA - PUCPR Prof. Júlio Cesar Nievola 38
Controle do tamanho do passo
O conjunto de valores assumidos pelos pesos é chamado trilha dos pesos e se movem em direção oposta ao gradiente em cada ponto
O pior caso para garantir a convergência ao ótimo w* em todas as direções é
O tamanho do passo deve ser menor que o inverso do maior autovalor da matriz de auto-correlação, a fim de que não haja divergência
max
2
PPGIA - PUCPR Prof. Júlio Cesar Nievola 39
Trilha dos pesos em direção ao mínimo
w1
w2
w2*
w1(1) w1*w1(0)
w2(1)w1(0)
Gradientes
w(1)w(0)
w2
w1
w2*w2(1)w1(0)
w1(1) w1*w1(0)
w(1)w(0)
Gradientes
Autovalores iguais:
Autovalores diferentes:
PPGIA - PUCPR Prof. Júlio Cesar Nievola 40
Constante de tempo da adaptação
A constante de tempo da adaptação é dada por
Se a razão entre o maior e o menor autovalor for grande, a convergência será lenta
A curva de aprendizagem se aproxima de Jmin em uma progressão geométrica
Há várias constantes de tempo da adaptação (caso os autovalores sejam diferentes), sendo uma para cada direção
min
1
Exemplo 17
PPGIA - PUCPR Prof. Júlio Cesar Nievola 41
Algoritmo LMS com vários pesos
O algoritmo LMS com vários pesos torna-se
Para a abordagem com bias: amplia-se a matriz de entrada com uma coluna extra
com 1s; ou modificam-se as entradas e saídas para que tenham
variáveis com valor médio igual a zero
Selecionar para produzir 10% de erro significa uma duração de treinamento em iterações igual a 10 vezes o número de entradas
kxkkwkw 1Exemplo 18
Exemplo 19
PPGIA - PUCPR Prof. Júlio Cesar Nievola 42
Método de Newton (1) A equação adaptativa dos pesos usando o método de
Newton
Método de Newton corrige a direção de busca de tal forma que ela sempre aponta para o mínimo
O método de Newton é mais rápido que LMS quando a matriz de correlação dos dados de entrada tem uma grande faixa de autovalores
O cálculo da inversa da matriz de auto-correlação, é mais demorado que LMS e necessita de informação global
Se a superfície não for quadrática o método diverge
kJRkwkw 11
PPGIA - PUCPR Prof. Júlio Cesar Nievola 43
Método de Newton (2)
w2
w1
w2*
w1*
.
Método de Newton
Descida do gradiente
Exemplo 20
PPGIA - PUCPR Prof. Júlio Cesar Nievola 44
Solução Analítica x IterativaAnalítica
Se R é mal-condicionada, a inversa não é precisa Tempo para cálculo da inversa é O(D2)
Iterativa não há garantia da proximidade de w* grande faixa de autovalores causa lenta convergência
Vantagens da abordagem iterativa há algoritmos muito eficientes para estimar o gradiente ordem de complexidade O(D) o método pode ser estendido para sistemas não-lineares