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

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.

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)

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.