Descente de gradient stochastique basée sur des opérations vectorielles?

10

supposons que je veux former un algorithme de régression de descente de gradient stochastique en utilisant un ensemble de données qui a N échantillons. Puisque la taille de l'ensemble de données est fixe, je vais réutiliser les données T fois. À chaque itération ou "époque", j'utilise chaque échantillon d'entraînement exactement une fois après avoir réorganisé au hasard l'ensemble de l'entraînement.

Mon implémentation est basée sur Python et Numpy. Par conséquent, l'utilisation d'opérations vectorielles peut considérablement réduire le temps de calcul. Venir avec une implémentation vectorisée de la descente de gradient par lots est assez simple. Cependant, dans le cas de la descente de gradient stochastique, je ne peux pas comprendre comment éviter la boucle externe qui itère à travers tous les échantillons à chaque époque.

Quelqu'un connaît-il une implémentation vectorisée de la descente de gradient stochastique?

EDIT : On m'a demandé pourquoi j'aimerais utiliser la descente de gradient en ligne si la taille de mon ensemble de données est fixe.

D'après [1], on peut voir que la descente de gradient en ligne converge plus lentement que la descente de gradient par lots vers le minimum du coût empirique. Cependant, il converge plus rapidement vers le minimum du coût attendu, qui mesure les performances de généralisation. Je voudrais tester l'impact de ces résultats théoriques sur mon problème particulier, au moyen d'une validation croisée. Sans implémentation vectorisée, mon code de descente de gradient en ligne est beaucoup plus lent que celui de descente de gradient par lots. Cela augmente considérablement le temps nécessaire pour terminer le processus de validation croisée.

EDIT : J'inclus ici le pseudocode de mon implémentation de descente de gradient en ligne, comme demandé par ffriend. Je résous un problème de régression.

Method: on-line gradient descent (regression)
Input: X (nxp matrix; each line contains a training sample, represented as a length-p vector), Y (length-n vector; output of the training samples)
Output: A (length-p+1 vector of coefficients)

Initialize coefficients (assign value 0 to all coefficients)
Calculate outputs F
prev_error = inf
error = sum((F-Y)^2)/n
it = 0
while abs(error - prev_error)>ERROR_THRESHOLD and it<=MAX_ITERATIONS:
    Randomly shuffle training samples
    for each training sample i:
        Compute error for training sample i
        Update coefficients based on the error above
    prev_error = error
    Calculate outputs F
    error = sum((F-Y)^2)/n
    it = it + 1

[1] "Apprentissage en ligne à grande échelle", L. Bottou, Y. Le Cunn, NIPS 2003.

Pablo Suau
la source
2
Divisez l'ensemble de données en mini-lots et ajustez le modèle à chaque mini-lot de manière séquentielle.
ffriend
Merci @ffriend. Cependant, ce ne serait pas une implémentation en ligne pure.
Pablo Suau
1
Quelle est la raison d'utiliser l'implémentation "en ligne pur" si votre jeu de données est corrigé? SGD dit seulement que vous n'avez pas besoin d'itérer l'ensemble de données en même temps, mais que vous pouvez le diviser en un nombre arbitraire de morceaux (mini-lots) et les traiter un par un. Un mini-lot de taille 1 n'a de sens que lorsque vous disposez d'une source de données continue et éventuellement infinie (comme le fil Twitter, par exemple) et que vous souhaitez mettre à jour le modèle après chaque nouvelle observation. Mais c'est un cas très rare et certainement pas pour les ensembles de données fixes.
ffriend
Toutes mes excuses pour ma réponse très tardive. Veuillez vérifier le texte que j'ai ajouté à la question d'origine.
Pablo Suau
1
Pouvez-vous montrer votre implémentation? Je vois un malentendu, mais sans exemple de code, il sera difficile de l'expliquer.
ffriend

Réponses:

10

Tout d'abord, le mot «échantillon» est normalement utilisé pour décrire un sous - ensemble de la population , donc je vais me référer à la même chose que «exemple».

Votre implémentation SGD est lente à cause de cette ligne:

for each training example i:

Ici, vous utilisez explicitement exactement un exemple pour chaque mise à jour des paramètres du modèle. Par définition, la vectorisation est une technique pour convertir des opérations sur un élément en opérations sur un vecteur de tels éléments. Ainsi, non, vous ne pouvez pas traiter les exemples un par un et toujours utiliser la vectorisation.

Cependant, vous pouvez approximer le vrai SGD en utilisant des mini-lots . Le mini-lot est un petit sous-ensemble de l'ensemble de données d'origine (disons, 100 exemples). Vous calculez les mises à jour des erreurs et des paramètres sur la base de mini-lots, mais vous continuez d'itérer sur bon nombre d'entre eux sans optimisation globale, ce qui rend le processus stochastique. Donc, pour rendre votre implémentation beaucoup plus rapide, il suffit de changer la ligne précédente en:

batches = split dataset into mini-batches
for batch in batches: 

et calculer l'erreur à partir du lot, pas à partir d'un seul exemple.

Bien que cela soit assez évident, je devrais également mentionner la vectorisation au niveau par exemple. Autrement dit, au lieu de quelque chose comme ça:

theta = np.array([...])  # parameter vector
x = np.array([...])      # example
y = 0                    # predicted response
for i in range(len(example)):
    y += x[i] * theta[i]
error = (true_y - y) ** 2  # true_y - true value of response

vous devriez certainement faire quelque chose comme ça:

error = (true_y - sum(np.dot(x, theta))) ** 2

qui, encore une fois, est facile à généraliser pour les mini-lots:

true_y = np.array([...])     # vector of response values
X = np.array([[...], [...]]) # mini-batch
errors = true_y - sum(np.dot(X, theta), 1)
error = sum(e ** 2 for e in errors)
ami
la source
1
Je pense que c'est la voie à suivre. Les mini-lots avec une taille bien choisie peuvent en fait converger plus rapidement que la version par lots ou en ligne (l'ancien ne met à jour les poids qu'une fois par ensemble entier, et ce dernier ne peut pas être vectorisé, plus a des étapes supplémentaires de mise à jour du poids plus souvent)
Neil Slater
Merci à vous deux. Toutes mes excuses pour avoir obstinément rejeté les mini-lots auparavant, mais je n'étais pas sûr des implications de cette méthode sur le taux de convergence. Neil, votre affirmation vient-elle de votre propre expérience, ou y a-t-il des résultats théoriques / empiriques publiés?
Pablo Suau
1
@PabloSuau Vous pouvez consulter le cours Machine Learning d'Andrew Ng sur Coursera, semaine 10, il explique pourquoi la convergence peut être plus rapide que SGD et batch GD. Pour être plus précis: il doit toujours être aussi rapide que SGD, mais parfois il doit être encore plus rapide en pratique.
gaborous
1

Découvrez la méthode partial_fit du classificateur SGD de scikit . Vous avez le contrôle sur ce que vous appelez avec lui: vous pouvez le faire en "vrai" apprentissage en ligne en passant une instance à la fois, ou vous pouvez regrouper des instances en mini-lots si toutes vos données sont disponibles dans un tableau. S'ils le sont, vous pouvez découper le tableau pour fournir les minibatches.

Ben Allison
la source