AULA04

PERCEPTRON MULTI-CAMADAS

MULTI-LAYER PERCEPTRON (MLP)

ALGORITMO DE RETRO-PROPAGAÇÃO

INTRODUÇÃOO perceptron de múltiplas camadas (Multi-Layer Perceptron – MLP) é uma rede do tipo perceptron com pelo menos uma camada intermediária.

Apesar desse tipo de rede apresentar soluções para funções linearmente não-separáveis, como visto anteriormente, torna-se necessário um algoritmo de treinamento capaz de definir de forma automática os pesos.

O algoritmo desta rede é uma generalização da regra delta de Widrow &Hoff para o treinamento da Adaline, e denomina-se backpropagation.

Este algoritmo consiste basicamente dos passos:

- propagação positiva do sinal: durante este processo todos os pesos são mantidos fixos; e- retropropagação do erro: durante este processo os pesos da rede são ajustados baseados na regra de correção de erro.

Como a propagação do erro é calculado no sentido inverso do sinal, o algoritmo é denominado de retropropagação do erro.

Características

1 1 1

x1

x2

xm

y1

y0

camadade

entrada

primeiracamada

escondida

segundacamada

escondida

camadade

saída

Uma rede MLP típica possui as seguintes características:

- os neurônios possuem uma função de ativação não-linear, diferenciável, do tipo sigmoidal (por exemplo, função logística e tangente-hiperbólica);- a rede possui uma ou mais camadas intermediárias; e- a rede possui uma alta conectividade.

propagaçãodo sinal

propagaçãodo erro

treinamento

A generalização da regra delta de Widrow &Hoff é usada para ajustar os pesos e bias da rede de forma a minimizar o erro entre a saída da rede e a saída desejada.

Para isso é calculado o gradiente da função de erro em relação aos pesos e bias, pois atualizando os pesos e bias na direção oposta a esse gradiente minimiza-se o erro.

Como o erro é calculado apenas para a camada de saída, o algoritmo de backpropagation responde como determinar a influência do erro nas camadas intermediárias da rede.

mi

mi

mim

ij

mij

mij b

ttbtb

w

ttwtw

)(

)()1(,)(

)()1(

Cálculo da saída

No algoritmo de backpropagation a saída de cada camada da rede é calculada por:

1,...,1,0para),( 1111 Mmf mmmmm byWy

onde M é o número de camadas da rede, y0 = x, a entrada da primeira camada é o vetor de entradas, e y = yM, a saída da rede é a saída da última camada.

Cálculo da retropropagação do erro

mi

mi

mi

mi

mij

mi

mi

mij b

u

ubw

u

uw

,

1eportanto 1

1

1

1

mi

mim

jmij

mi

S

j

mi

mj

mij

mi b

uy

w

ubywu

m

Para o cálculo do gradiente, como o erro é função indireta dos pesos nas camadas escondidas, deve ser usada a regra de cadeia:

O segundo termo das equações pode ser calculado considerando que a entrada líquida (soma ponderada dos pesos) da camada m é função dos pesos e bias (Sm é a quantidade de neurônios na camada m):

Entrada líquida

mim

i

mj

mim

ijmi

mi b

ywu

eentão 1

mi

mi

mi

mj

mi

mij

mij tbtbytwtw )()1(e)()1( 1

Definindo a sensibilidade de a mudanças na entrada líquida do i-ésimo neurônio da camada m como:

As atualizações de pesos e bias em qualquer camada são dadas por:

Sensibilidade

mi

mi

mi

mi

mij

mi

mi

mij b

u

ubw

u

uw

,Vimos que:

1e1

mi

mim

jmij

mi

b

uy

w

u

Representação matricial

Tm

S

mm

T

m

S

mmmm

mmmTmmmm

m

muuu

onde

tttt

......

)()1(e)()()1(

2121

1

uδ

δbbyδWW

Matricialmente tem-se:

Cálculo da sensibilidadeÉ necessário calcular a sensibilidade para camadas escondidas anteriores e isso requer a aplicação da regra de cadeia.

• calcular a sensibilidade na camada m a partir da sensibilidade na camada m + 1.

m

S

m

Sm

m

Sm

m

S

m

S

m

m

m

m

m

m

S

m

m

m

m

m

m

m

m

mmm

m

m

u

u

u

u

u

u

u

u

u

u

u

u

u

u

u

u

u

u

1

2

1

1

1

12

2

12

1

12

11

2

11

1

11

1

111

...

...

...

...

u

u

Para tanto é usada a seguinte matriz:

Sensibilidade (cont.)

)(...00

0...)(0

0...0)(

)(onde)(

.

2

.1

.

11

m

S

m

mm

mm

mm

mm

mm

m

muf

uf

uf

uFuFW

u

u ..

)()( .

1111

mj

mmijm

j

mj

mmijm

j

mjm

ijmj

mi ufw

u

ufw

u

yw

u

u

matricialmente

111

11

1

))(())((

mTmmm

mTmm

m

m

T

m

m

mm δWuF

uWuF

uu

u

uδ

..

portanto

Cálculo de sensibilidades (cont.)

)()( .

Mi

M

Mi

Mi

M

Mi

Mi

Mi

i ufu

uf

u

y

u

y

)()(2.

Mi

M

iiMi ufyd

Mi

iiiM

i

S

jjj

Mi

T

Mi

Mi u

yyd

u

yd

uu

M

)(2

)()()( 1

2

ydyd

As sensibilidades são calculadas da última para a primeira camada:121MM δδ...δδ

Para calcular a primeira sensibilidade (camada de saída):

))((2 yduFδ.

MM

MMatricialmente:

onde

portanto

Ilustração gráfica

W1x

b11

u1f1

y1

W2

b21

u2f2

y2

W3

b31

u3f3

y3

F1.

F2.

F3.

(W2)T (W3)T

32

1 2 3

(y - s)

Propagação progressiva dos sinais

Retro-propagação das sensibilidades

Procedure [W] = backprop (max_it, min_err, , X, D)for m from 1 to M do inicializa Wm e bm // valores pequenos escolhidos aleatoriamenteend // for t 1while t < max_it & MSE > min_err do for i from 1 to N do // para cada padrão de treinamento // propagação progressiva do sinal

// retro-propagação das sensibilidades

// atualização dos pesos

// cálculo do erro para o padrão i

end // for MSE sum( )/N t t+1 end // whileend // procedure

M - FM (uM ) (di - y i).

i i

m Fm (um ) (Wm+1)Tm+1, m = M-1, …, 2,1.

i i i

Wm Wm - m (ym-1)T, m = 1, …, Mi i

bm bm - m , m = 1, …, Mi

ei T ei = (di - yi )

T (di - yi )

Algoritmo backpropagation (ajuste local)

i

i

ii xy 0

1101111 ,...,M,mmmmmm ),by(Wfy ii

Capacidade de aproximação universal

Imxx m },...,{todoPara 1

),...,,(),...,,( 2121 mm xxxgxxxF

O teorema de aproximação universal é descrito a seguir:

Teorema: seja f(.) uma função contínua não-constante, limitada, e monotonicamente crescente. Seja Im um hipercubo unitário m-dimensional(0,1)m. O espaço das funções contínuas em Im é denominado C(Im). Então, para qualquer função , existe um inteiro M e conjuntos de constantes reais i e wij, onde i = 1,..., M e j = 1,...,m, tais que pode-se definir

0e)( mICg

M

i

m

joijijim wxwfxxxF

1 121 ),...,,(

como uma aproximação da função g(.) tal que,

O teorema afirma que o perceptron de múltiplas camadas com uma única camada intermediária realiza uma aproximação uniforme, dado um conjunto de treinamento suficiente para representar a função.

Porém, não garante que um MLP com uma única camada é a melhor solução, quanto ao tempo de processamento e facilidade de implementação.

Aspectos do treinamento de redes MLP

O aprendizado é resultado de apresentação repetitiva de todas as amostras do conjunto de treinamento.

Cada apresentação de todo o conjunto de treinamento é denominada época.

O processo de aprendizagem é repetido época após época, até que um critério de parada seja satisfeito.

É recomendável que a ordem de apresentação das amostras seja aleatória de uma época para outra. Isso tende a fazer com que o ajuste de pesos tenha um caráter estocástico ao longo do treinamento.

Atualização local ou por lote.Atualização pode ser de duas maneiras básicas: local e por lote.

Local: a atualização é feita imediatamente após a apresentação de cada amostra de treinamento.- é também chamado de método de atualização on-line ou padrão a padrão.

Lote: a atualização dos pesos só é feita após a apresentação de todas as amostras de treinamento que constituem uma época.

- é também conhecido como método de atualização off-line ou batch.

- o ajuste relativo a cada apresentação de uma amostra é acumulado.

- requer um menor armazenamento para cada conexão, e apresenta menos possibilidade de convergência para um mínimo local.

- fornece uma melhor estimativa do vetor gradiente.

Critérios de paradaO processo de minimização do MSE (função custo) não apresenta convergência garantida e não possui um critério de parada bem definido.

Um critério de parada não muito recomendável, que não leva em conta o estado do processo iterativo é o da pré-definição do número total de iterações.

Apresenta-se a seguir um critério de parada que leva em conta o processo iterativo.

)(med

)(

Consideremos um critério que leva em conta informações a respeito do estado iterativo. Considera-se nesse caso a possibilidade de existência de mínimos locais.Seja * o vetor de pesos que denota um ponto mínimo, local ou global.

Uma condição para que * seja um mínimo é que o gradiente , da função custo, seja zero em *.

Como critério tem-se as seguintes alternativas de parada:1 - quando a norma euclidiana da estimativa do vetor gradiente atinge um valor suficientemente pequeno.

)(

Critérios de parada (cont.)

2 - quando a variação do erro quadrático médio (MSE) de uma época para outra atingir um valor suficientemente pequeno.

3 - quando o erro quadrático médio atingir um valor suficientemente pequeno ou seja, onde é um valor suficientemente pequeno.

Critérios de parada (cont.)

• Nota-se que se o critério é de valor mínimo de MSE então não se garante que o algoritmo irá atingir esse valor.

• Por outro lado, se o critério é o mínimo valor do vetor gradiente deve-se considerar que o algoritmo termina no mínimo local mais próximo.

Mínimolocal Mínimo

Global

MSE

Critérios de parada (cont.)

Outro critério de parada, que pode ser usado em conjunto com um dos critérios anteriores é a avaliação da capacidade de generalização da rede após cada época de treinamento.

O processo de treinamento é interrompido antes que a capacidade de generalização da rede fique restrita.

Arquitetura da rede

A quantidade de neurônios na camada de entrada é dada pelo problema a ser abordado.

No entanto, a quantidade de neurônios nas camadas de processamento são características do projeto.

Aumentando-se o número de neurônios na camada escondida aumenta-se a capacidade de mapeamento não-linear da rede.

No entanto, quando esse número for muito grande, o modelo pode se sobre-ajustar aos dados, na presença de ruído nas amostras de treinamento. Diz-se que a rede está sujeito ao sobre-treinamento (overfitting).

Por outro lado, uma rede com poucos neurônios na camada escondida pode não ser capaz de realizar o mapeamento desejado, o que é denominado de underfitting.

O underfitting também pode ser causado quando o treinamento é interropido de forma prematura.

Normalização dos dados de entrada

Uma característica das funções sigmoidais é a saturação, ou seja, para valores grandes de argumento, a função opera numa região de saturação.

É importante portanto trabalhar com valores de entrada que estejam contidos num intervalo que não atinjam a saturação, por exemplo, [0,1] ou [-1,1].

Inicialização dos vetores de pesos e bias

A eficiência do aprendizado em redes multicamadas depende da:

- especificação de arquitetura da rede, - função de ativação, - regra de aprendizagem e - valores iniciais dos vetores de pesos e bias.

Considerando-se que os três primeiros itens já foram definidos, verifica-se agora a inicialização dos vetores de pesos e bias.

Inicialização aleatória dos pesos

A atualização de um peso entre duas unidades depende da derivada da função de ativação da unidade posterior e função de ativação da unidade anterior.

Por esta razão, é importante evitar escolhas de pesos iniciais que tornem as funções de ativação ou suas derivadas iguais a zero.

Um procedimento comum é inicializar os pesos e bias a valores randômicos entre -0.5 e 0.5, ou entre -1 e 1. Os valores podem ser positivos ou negativos porque os pesos finais após o treinamento também podem ser positivos ou negativos

Os valores para os pesos iniciais não devem ser muito grandes, tal que as derivadas das funções de ativação tenham valores muito pequenos (região de saturação). Por outro lado, se os pesos iniciais são muito pequenos, a soma pode cair perto de zero, onde o aprendizado é muito lento.

Inicialização de Nguyen-Widrow (1990)

• Os pesos e bias para os neurônios de saída são inicializados com valores randômicos entre -0.5 e 0.5, como é o caso comumente usado.

• A inicialização dos pesos para os neurônios das camadas escondidas é projetada para melhorar a habilidade de aprendizado desses neurônios.

• Isso é realizado distribuindo os pesos e bias iniciais tais que, para cada padrão de entrada, seja provável que a entrada líquida para cada um dos neurônios da camada escondida esteja no intervalo em que aquele neurônio aprenda mais rapidamente.

• Inicialmente para calcula-se:

fator de escala

nn pp 7.0)(7.01

n número de entradasp número de neurônios da camada escondida

Procedimento de Nguyen-Widrow

• O procedimento consiste dos seguintes passos:

– Para cada neurônio da camada escondida (j = 1,...,p):

• Inicializa-se o vetor peso dos neurônios da camada escondida:

wji (0) = número randômico entre -0.5 e 0.5

• Computa-se a norma euclidiana

• Reinicializa-se os pesos

– Inicializa-se os bias:

bj = número randômico entre – e .

)0(jw

)0(

)0(

j

jiji

w

ww

de todos os pesos de j

Quantos padrões de treinamento devem existir (Baum-Haussler, 1989)

• Qual a relação entre o número de padrões de treinamento disponíveis, N, o número de pesos a serem treinados, W, e a acuidade da classificação esperada dada

pela fração e, (acuidade máxima = 1, que corresponde a 100%)?

• Segundo Baum & Haussler, dada a equação

uma rede treinada para classificar a fração 1- e/2 dos padrões de treinamento corretamente, irá classificar a fração 1- e dos padrões de teste corretamente.

• Exemplo:

eN

W

Com e = 0.1, uma rede com W = 80 pesos irá requerer N = 800 padrões de treinamento para assegurar a classificação de 1- e = 0.9 (90% ) dos padrões de teste corretamente, assumindo que a rede é treinada para classificar 1- e/2 = 0.95 (95%) dos padrões de treinamento corretamente.