Clarification sur la mise en œuvre de la règle Perceptron vs descente de gradient vs mise en œuvre de descente de gradient stochastique

15

J'ai expérimenté un peu avec différentes implémentations de Perceptron et je veux m'assurer si je comprends bien les "itérations".

La règle originale de Perceptron de Rosenblatt

D'après ce que je comprends, dans l'algorithme de perceptron classique de Rosenblatt, les poids sont mis à jour simultanément après chaque exemple de formation via

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

où est la règle d'apprentissage ici. Et cible et réel sont tous deux seuillés (-1 ou 1). Je l'ai implémenté comme 1 itération = 1 passage sur l'échantillon d'entraînement, mais le vecteur de poids est mis à jour après chaque échantillon d'entraînement.eta

Et je calcule la valeur "réelle" comme

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

Descente de gradient stochastique

Δw(t+1)=Δw(t)+η(tunerget-unectuunel)Xje

Identique à la règle du perceptron, cependant, targetet actualne sont pas des seuils mais des valeurs réelles. De plus, je compte "l'itération" comme chemin sur l'échantillon d'apprentissage.

SGD et la règle classique du perceptron convergent dans ce cas linéairement séparable, cependant, j'ai des problèmes avec la mise en œuvre de la descente de gradient.

Descente graduelle

Ici, je passe en revue l'échantillon d'entraînement et résume les changements de poids pour 1 passage sur l'échantillon d'entraînement et met à jour les poids par la suite, par exemple,

pour chaque échantillon de formation:

Δwnew+=Δw(t)+η(tunerget-unectuunel)Xje

...

après 1 passage sur l'ensemble d'entraînement:

Δw+=Δwnew

Je me demande si cette hypothèse est correcte ou s'il me manque quelque chose. J'ai essayé différents taux d'apprentissage (jusqu'à infiniment petits), mais je n'ai jamais réussi à montrer un signe de convergence. Je me demande donc si j'ai mal compris qc. ici.

Merci, Sebastian


la source

Réponses:

20

Vous avez quelques erreurs dans vos mises à jour. Je pense qu'en général, vous confondez la valeur des poids actuels avec la différence entre les poids actuels et les poids précédents. Vous avez des symboles dispersés partout où il ne devrait pas y en avoir, et + = où vous devriez avoir =.Δ

Perceptron:

ww(t+1)=ww(t)+ηt(y(je)-y^(je))XX(je) ,

où est la prédiction du modèle sur l' exemple de formation.y^(je)=signe(wwXX(je))jeth

Cela peut être considéré comme une méthode de descente stochastique de premier cycle sur la fonction de "perte de perceptron" suivante *:

Perte de Perceptron:

Lww(y(je))=max(0,-y(je)wwXX(je)) .

Lww(y(je))={0}, si y(je)wwXX(je)>0{-y(je)XX(je)}, si y(je)wwXX(je)<0[-1,0]×y(je)XX(je), si wwXX(je)=0 .

Étant donné que le perceptron est déjà une forme de SGD, je ne sais pas pourquoi la mise à jour de SGD devrait être différente de la mise à jour du perceptron. La façon dont vous avez écrit l'étape SGD, avec des valeurs non seuillées, vous subissez une perte si vous prédisez une réponse trop correctement. C'est mauvais.

Votre étape de gradient par lots est incorrecte car vous utilisez "+ =" alors que vous devriez utiliser "=". Les poids actuels sont ajoutés pour chaque instance de formation . En d'autres termes, la façon dont vous l'avez écrit,

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

Ce que cela devrait être:

ww(t+1)=ww(t)-ηtje=1nLww(t)(y(je)) .

De plus, pour que l'algorithme converge sur chaque ensemble de données, vous devez diminuer votre taux d'apprentissage selon un calendrier, comme .ηt=η0t


* L'algorithme perceptron n'est pas exactement le même que SSGD sur la perte perceptron. Généralement en SSGD, dans le cas d'une égalité ( ), , donc , vous serez donc autorisé à ne pas faire un pas. En conséquence, la perte de perceptron peut être minimisée à , ce qui est inutile. Mais dans l' algorithme perceptron , vous devez rompre les liens et utiliser la direction du sous-gradient si vous choisissez la mauvaise réponse.wwXX(je)=0L=[-1,0]×y(je)XX(je)00Lww=00-y(je)XX(je)L

Ils ne sont donc pas exactement les mêmes, mais si vous travaillez en supposant que l'algorithme du perceptron est SGD pour une fonction de perte et que vous inversez la fonction de perte, la perte de perceptron est ce que vous vous retrouvez.

Sam Thomson
la source
Merci Sam, et je m'excuse pour ma question en désordre. Je ne sais pas d'où viennent les deltas, mais c'est le "+ =" qui a mal tourné. J'ai complètement ignoré cette partie. Merci pour la réponse complète!