Upload
internet
View
112
Download
4
Embed Size (px)
Citation preview
Aproximação de Funções usando MLPs, RBFs e SVM
Prof. Júlio Cesar NievolaPPGIAPUCPR
PPGIA - PUCPR Prof. Júlio Cesar Nievola 2
Aproximação de FunçõesRegressão: representar o relacionamento entre os dados de entrada e saídaClassificação: considera-se a entrada como sendo pertencendo a várias classses e o objetivo é separá-la nas classes tão corretamente quanto possívelAproximação de funções(AF): regressão linear é AF com topologias lineares e classificação é AF com funções especiais chamadas funções indicadoras
PPGIA - PUCPR Prof. Júlio Cesar Nievola 3
Mapeamento Entrada-Saída como Aproximação de Funções
Objetivo da Aprendizagem: descobrir a função f() dado um número finito (desejável pequeno) de pares entrada-saída (x,d)RNAs são úteis para aproximação de funções porque: elas são aproximadores universais elas são aproximadores eficientes elas podem ser implementadas como
máquinas de aprendizagem
PPGIA - PUCPR Prof. Júlio Cesar Nievola 4
Treinamento supervisionado como aproximação de funções
PPGIA - PUCPR Prof. Júlio Cesar Nievola 5
Teorema da Projeção LinearObjetivo da aproximação de funções: em uma área compacta S do espaço de entrada descrever uma função f(x), pela combinação de funções i(x) mais simples
onde wi são elementos reais do vetor w=[w1,…,wN] tais que
e pode ser arbitrariamente pequeno. A função é chamada de aproximante e as funções
{i(x)} são chamadas de funções elementares
N
iiiwf
1
,ˆ xwx
wx,f̂
wxx ,f̂f
PPGIA - PUCPR Prof. Júlio Cesar Nievola 6
Implementação do Teorema da Projeção
PPGIA - PUCPR Prof. Júlio Cesar Nievola 7
Aproximação de Funções
Decisões básicas na aproximação de funções escolha das funções elementares {i(x)} como calcular os pesos wi
seleção do número de funções elementares
Se o número de vetores de entrada xi é igual ao número de funções elementares {i(x)} a solução torna-se
Condição importante: a inversa de deve existir
f1w
PPGIA - PUCPR Prof. Júlio Cesar Nievola 8
Interpretação Geométrica do Teorema da Projeção
Quando f(x) é externo ao espaço de projeção, o erro diminui fazendo mais próximo de f(x)Isto pode ser feito aumentando o número de funções elementares
wx,f̂
PPGIA - PUCPR Prof. Júlio Cesar Nievola 9
Escolhas para as funções elementares
Requisito: -1(x) deve existir. Isto é obtido se as funções elementares constituírem uma base, isto é, elas forem linearmente independentes, ou seja,
Hipótese simplificadora: impor que as funções elementares usem bases ortonormais:
onde (x) é a função delta de Dirac
0,,0 111 NNN wwsseww xx
xxxx ijS ji d
PPGIA - PUCPR Prof. Júlio Cesar Nievola 10
Função Elementar: sinc
i
iii xx
xxsinxxsincx
Exemplo 01
PPGIA - PUCPR Prof. Júlio Cesar Nievola 11
Função elementar: série de Fourier
ittj
i et
2
Exemplo 02
PPGIA - PUCPR Prof. Júlio Cesar Nievola 12
Função elementar: waveletA partir da wavelet mãe (x) obtém-se bases através de translação e escalamento:
ixx jj
ij 22 2
PPGIA - PUCPR Prof. Júlio Cesar Nievola 13
Bases para Aproximação de Funções na Rede MLP
As funções elementares podem ser globais, quando respondem a todo o espaço de entrada locais, quando respondem de maneira especial a uma
área limitada do espaço de entrada
Uma rede MLP com uma camada escondida com um PE de saída linear pode ser considerado como uma implementação de um sistema para aproximação de funções, onde as bases são os PEs escondidosO PE sigmoidal responde a todo o espaço de entrada, ou seja, a MLP implementa uma aproximação com funções elementares globais
Exemplo 03
PPGIA - PUCPR Prof. Júlio Cesar Nievola 14
Aproximação de Funções usando Rede MLP
A rede MLP realiza aproximação de funções com um conjunto adaptativo de bases, determinados a partir dos dados entrada-saídaAs bases são alteradas em função dos dados, ou seja, o espaço de projeção é dependente dos dadosO treinamento é mais difícil pois não somente a projeção como também a base está sendo alteradaAs representações são mais compactasDevido à alta conectividade e natureza global das funções elementares, bom ajuste é obtido com poucas bases, isto é, com poucos PEs escondidos
PPGIA - PUCPR Prof. Júlio Cesar Nievola 15
Aproximação de Funções usando Rede MLP
O treinamento é mais difícil, pois as bases não são ortogonaisMLPs são mais eficientes que polinômios para aproximação de funções em espaços de alta dimensão
Aproximação de funçõesusando função logística
Exemplo 04
PPGIA - PUCPR Prof. Júlio Cesar Nievola 16
MLP: Classificação x Aproximação de funções
Elemento de saída Aproximação de funções: PE linear Classificação: PE não-linear
Ponto de operação dos PEs escondidos Aproximação de funções: longe da saturação
para que mapeamento seja suave Classificação: PEs operam na região de
saturação, já que as saídas devem tender para 1 ou 0
Exemplo 05
PPGIA - PUCPR Prof. Júlio Cesar Nievola 17
Base alternativa para sistemas não-lineares: rede RBF
Para as funções de base radial (RBF) tem-se
onde () é normalmente uma função gaussiana:
com variância 2 ou covariância = 2I.
Gaussiana centrada em xi com variância 2, ou seja, é uma função elementar local
ii xxx
sionalmultidimen,2
expG
onalunidimensi,2
exp
1
2
2
xxx
x
T
xG
PPGIA - PUCPR Prof. Júlio Cesar Nievola 18
Aproximação de RBFs em uma dimensão
Exemplo 06
PPGIA - PUCPR Prof. Júlio Cesar Nievola 19
Redes RBFAproximação de funções em área limitada do espaço de entrada requer posicionamento das gaussianas
localizadas para cobrir o espaço controle da largura de cada gaussiana ajuste da amplitude de cada gaussiana
Como as bases RBF são locais, alteração em uma delas não perturba a aproximação em outras áreas do espaço
PPGIA - PUCPR Prof. Júlio Cesar Nievola 20
Redes RBFNecessita-se exponencialmente de mais RBFs para cobrir espaços de alta dimensãoCom os centros já determinados, as RBFs treinam eficientemente, já que o erro é linear nos pesosSe os centros forem otimamente ajustados, isto garante a convergência para o mínimo globalRedes RBF possuem a propriedade de melhor aproximação como definido por Chebyshev
Exemplo 07
PPGIA - PUCPR Prof. Júlio Cesar Nievola 21
Interpretação probabilística do mapeamento
Redes MLP e RBF realizam regressão não-linear, generalizando o AdalineCapazes de descobrir qualquer relação entrada-saída determinista com ruído aditivo de média zeroRequisitos convergência para mínimo global número graus de liberdade suficiente dados suficientes para treinamento
Estas conclusões são válidas desde que se use o critério MSE no treinamento
Exemplo 08
PPGIA - PUCPR Prof. Júlio Cesar Nievola 22
Adaptação do centro e da variância das gaussianas
Método simples: distribuir uniformemente os centros das gaussianas Para funções que cobrem todo o espaço OK Para clusters de dados não é indicado
Métodos supervisionado e auto-organizadoBackpropagation pode ser usado para treinar RBFs Treinamento lento Variâncias se tornam muito grandes e RBF
perde a sua natureza de processo local
PPGIA - PUCPR Prof. Júlio Cesar Nievola 23
Método auto-organizado de treinamento de RBFs
Treinamento em dois passos Adaptação independente dos pesos da
primeira camada: os clusters de dados atuam como atratores para os centros das gaussianas e as variâncias são estimadas para cobrir a distribuição dos dados de entrada
Adaptação dos pesos de saída, usando o algoritmo LMS já que o problema de adaptação é linear nos pesos, mantendo a primeira camada “congelada”
Exemplo 09
PPGIA - PUCPR Prof. Júlio Cesar Nievola 24
Seleção do número de bases
Com poucas bases a aproximação é fracaDepende do tamanho da rede e dos valores dos coeficientesPolinômio de grau muito baixo: bias do modeloPolinômio de grau muito alto: grande oscilação, ou seja, variância do modeloCompromisso entre baixo bias e baixa variância ao longo do domínio
PPGIA - PUCPR Prof. Júlio Cesar Nievola 25
Sub- e sobre-ajuste do polinômio
Exemplo 10
PPGIA - PUCPR Prof. Júlio Cesar Nievola 26
Dilema Bias-Variância
Problema da generalização: Pontos fiduciais são os exemplos de treinamento O domínio representa todos possíveis dados de
teste para a máquina de aprendizagem O polinômio é representado pelo mapa funcional
entrada-saída da máquina de aprendizagem Os pesos da máquina de aprendizagem são
equivalentes aos coeficientes do polinômio O tamanho do polinômio é o número de pesos
PPGIA - PUCPR Prof. Júlio Cesar Nievola 27
Dilema Bias-Variância
Com poucos parâmetros o desempenho no conjunto de treinamento (e de teste) é ruim, pois as superfícies de separação não são adequadamente colocadasCom muitos parâmetros, há um ajuste exato (memorização) ao conjunto de treinamento, mas o resultado no conjunto de teste não é aceitávelA diferença entre o desempenho sobre os conjuntos de treinamento e teste é uma medida da variância do modeloO objetivo da aprendizagem não deve ser o erro igual a zero no conjunto de treinamento
PPGIA - PUCPR Prof. Júlio Cesar Nievola 28
Penalizando o erro de treinamento
Generalização pode ser vista como encontrar um critério geral para a determinação da ordem do modelo para um problemaErro de ajuste não é um critério do ótimoO critério MDL (minimum description length) [Rissanen, 89] considera o comprimento do código do modelo e dos errosO melhor compromisso em termos de comprimento de código reside entre máquinas menores e erros aceitáveis
PPGIA - PUCPR Prof. Júlio Cesar Nievola 29
Critério de Informação de Akaike
Penaliza o erro médio quadrático no treinamento incluindo um termo que aumenta com o tamanho do modelo
onde J(k) é o MSE do conjunto de treinamento, k é o número de parâmetros livres do modelo e N é o número de amostras de dados
Funciona bem para sistemas de uma camada, especialmente lineares. Para várias camadas há problemas, pois o tamanho do modelo não é somente função do número de pesos
kkJNkAICk 2lnmin
PPGIA - PUCPR Prof. Júlio Cesar Nievola 30
Critério de Informação de Akaike
Ponto positivo: usar todos os dados disponíveis para treinamentoFoi demonstrado que a validação cruzada é assintoticamente equivalente ao critério de informação de Akaike
Melhor modelo segundo o critério de Akaike
Exemplo 11
PPGIA - PUCPR Prof. Júlio Cesar Nievola 31
Regularização
A teoria da regularização adiciona um termo extra ao custo da função: , onde Jc é a função custo, Jr é o regularizador e é o parâmetro que indica a influência do regulador versus o custoUm regularizador é
Decaimento de pesos é um regulador:
deve ser selecionado experimentalmente
rcnew JJJ
i
icnew wJJ 2
Exemplo 12
n n
nr
x
yJ
2
2
2
PPGIA - PUCPR Prof. Júlio Cesar Nievola 32
RBF como regressor: A rede neural probabilística
Pode-se utilizar a RBF para estimar a função de regressão de dados ruidosos seguindo as idéias de núcleo de regressão
Busca-se estimar a função densidade de probabilidade p(x,d) de pares entrada-saída
(xi,di) usando o método da janela de Parzen:
é a largura da gaussiana
e deve ser determinada
experimentalmente
i
i
i
ii
xx
xxd
xy
2
2
2
2
2exp
2exp
Exemplo 13
Exemplo 14
Exemplo 15
PPGIA - PUCPR Prof. Júlio Cesar Nievola 33
SVM – Support Vector Machine
Idéias básicas Transformar os dados para um espaço de alta
dimensionalidade para tornar as funções discriminantes lineares práticas
Treinamento usando classificadores de margem larga
Quando usada como uma SVM, a RBF coloca uma gaussiana em cada amostra de dados de maneira tal que o espaço de características torna-se tão grande quanto o número de amostras
Treinar uma RBF para margem larga desacopla a capacidade do classificador do espaço de entrada e simultaneamente fornece boa generalização
PPGIA - PUCPR Prof. Júlio Cesar Nievola 34
Extensão do Adatron para Máquinas de Núcleo
Escreve-se a função discriminante da RBF em termos da representação dependente dos dados
onde G(x,2) representa a função gaussiana, L é o número de PEs na RBF, wk são os pesos, N é o número de amostras e i são conjuntos de multiplicadores (um para cada amostra)
Este algoritmo, chamado Adatron de núcleo pode adaptar uma RBF para ter uma margem ótima, sendo a versão “online” da abordagem de otimização quadrática utilizada para SVM e pode encontrar as mesmas soluções que o algoritmo original de Vapnik
N
iii
L
kkk bxxGbxGwxg
0
2
1
2 2,,
PPGIA - PUCPR Prof. Júlio Cesar Nievola 35
Topologia de uma máquina SVM com núcleo RBF
Exemplo 16
PPGIA - PUCPR Prof. Júlio Cesar Nievola 36
Adatron com núcleo e margem suave
Existem espaços de características em que os padrões não são linearmente separáveis
Introduz-se então uma margem suave e obtém-se
novas funções g(xi) que podem ser implementadas
como algoritmo iterativo
Grandes conjuntos de entrada produzem RBFs muito grandes, com uma gaussiana por amostra de dados
Como a camada de entrada não tem parâmetros livres o mapeamento pode realmente ser calculado uma vez e salvo em memória
Exemplo 17