Esclarecimento sobre a implementação da regra de Perceptron vs. descida de gradiente vs. descida estocástica de gradiente

15

Eu experimentei um pouco com diferentes implementações do Perceptron e quero ter certeza de que entendi as "iterações" corretamente.

Regra original do perceptron de Rosenblatt

Tanto quanto eu entendo, no algoritmo clássico de Rosenblatt perceptron, os pesos são atualizados simultaneamente após cada exemplo de treinamento via

Δw(t+1)=Δw(t)+η(targetactual)xi

onde eta é a regra de aprendizado aqui. E o alvo e o real são limitados (-1 ou 1). Eu o implementei como 1 iteração = 1 passagem sobre a amostra de treinamento, mas o vetor de peso é atualizado após cada amostra de treinamento.

E eu calculo o valor "real" como

sign(wwTxx)=sign(w0+w1x1+...+wdxd)

Descida do gradiente estocástico

Δw(t+1)=Δw(t)+η(targetactual)xi

Igual à regra do perceptron, no entanto, targete actualnão são limiares, mas valores reais. Além disso, conto "iteração" como caminho sobre a amostra de treinamento.

Tanto o SGD quanto a regra perceptron clássica convergem nesse caso linearmente separável; no entanto, estou tendo problemas com a implementação da descida do gradiente.

Gradiente descendente

Aqui, examino a amostra de treinamento e resuma as alterações de peso para 1 passagem sobre a amostra de treinamento e atualizei os pesos posteriormente, por exemplo,

para cada amostra de treinamento:

Δwnew+=Δw(t)+η(targetactual)xi

...

após 1 passagem sobre o conjunto de treinamento:

Δw+=Δwnew

Gostaria de saber se esta suposição está correta ou se estou faltando alguma coisa. Tentei várias taxas de aprendizado (até infinitamente pequenas), mas nunca consegui mostrar nenhum sinal de convergência. Então, eu estou querendo saber se eu entendi mal sth. aqui.

Obrigado Sebastian


fonte

Respostas:

19

Você tem alguns erros nas suas atualizações. Eu acho que geralmente você está confundindo o valor dos pesos atuais com a diferença entre os pesos atuais e os anteriores. Você tem Δ símbolos espalhados por onde não deveria haver nenhum, e + = onde você deveria ter =.

Perceptron:

ww(t+1)=ww(t)+ηt(y(i)y^(i))xx(i)

y^(i)=sign(wwxx(i))ith

Isso pode ser visto como um método estocástico de descida de subgradiente na seguinte função "perda de perceptron" *:

Perda de Perceptron:

.Lww(y(i))=max(0,y(i)wwxx(i))

Lww(y(i))={0}, if y(i)wwxx(i)>0{y(i)xx(i)}, if y(i)wwxx(i)<0[1,0]×y(i)xx(i), if wwxx(i)=0.

Since perceptron already is a form of SGD, I'm not sure why the SGD update should be different than the perceptron update. The way you've written the SGD step, with non-thresholded values, you suffer a loss if you predict an answer too correctly. That's bad.

Your batch gradient step is wrong because you're using "+=" when you should be using "=". The current weights are added for each training instance. In other words, the way you've written it,

ww(t+1)=ww(t)+i=1n{ww(t)ηtLww(t)(y(i))}.

What it should be is:

ww(t+1)=ww(t)ηti=1nLww(t)(y(i)).

Also, in order for the algorithm to converge on every and any data set, you should decrease your learning rate on a schedule, like ηt=η0t.


* The perceptron algorithm is not exactly the same as SSGD on the perceptron loss. Usually in SSGD, in the case of a tie (wwxx(i)=0), L=[1,0]×y(i)xx(i), so 00L, so you would be allowed to not take a step. Accordingly, perceptron loss can be minimized at ww=00, which is useless. But in the perceptron algorithm, you are required to break ties, and use the subgradient direction y(i)xx(i)L if you choose the wrong answer.

So they're not exactly the same, but if you work from the assumption that the perceptron algorithm is SGD for some loss function, and reverse engineer the loss function, perceptron loss is what you end up with.

Sam Thomson
fonte
Thank you Sam, and I do apologize for my messy question. I don't know where the deltas come from, but the "+=" was the the thing that went wrong. I completely overlooked that part. Thanks for the thorough answer!