Stocastico discesa del gradiente basato su operazioni vettoriali?

Question

Supponiamo che voglio allenare un algoritmo di regressione gradiente di discesa stocastico utilizzando un insieme di dati che ha N campioni. Poiché la dimensione del set di dati è fisso, io riutilizzare i tempi dati T. Ad ogni iterazione o "epoca", io uso ogni campione addestramento esattamente una volta, dopo il riordino in modo casuale l'intero insieme di addestramento.

La mia applicazione è basata su Python e Numpy. Pertanto, utilizzando operazioni vettoriali può notevolmente ridurre i tempi di calcolo. Venendo con un'implementazione vettorializzare gradiente lotto discesa è abbastanza semplice. Tuttavia, nel caso di discesa del gradiente stocastico non riesco a capire come evitare l'anello esterno che scorre tutti i campioni a ciascuna epoca.

Qualcuno sa qualsiasi implementazione vettorializzare di discesa del gradiente stocastico?

Modifica : Mi è stato chiesto il motivo per cui mi piacerebbe utilizzare discesa del gradiente in linea se le dimensioni del mio set di dati è fisso.

Da [1], si può vedere che converge gradiente di discesa in linea più lenta del lotto gradiente discesa al minimo del costo empirica. Tuttavia, converge più velocemente al minimo del costo previsto, che misura le prestazioni di generalizzazione. Mi piacerebbe testare l'impatto di questi risultati teorici nel mio problema particolare, per mezzo di validazione incrociata. Senza un'implementazione vettorializzare, il mio codice gradiente di discesa online è molto più lento del lotto gradiente discesa uno. Che aumenta notevolmente il tempo necessario per il processo di validazione incrociata da completare.

Modifica : includo qui la pseudocodice della mia implementazione gradiente discesa on-line, come richiesto dalla ffriend. Sto risolvendo un problema di regressione.

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] "Large Scale Online Learning", L. Bottou, Y. Le CUNN, i PIN 2003.

Answer 1

Prima di tutto, la parola "campione" è normalmente usato per descrivere sottoinsieme della popolazione , quindi mi si riferiscono alla stessa cosa di "esempio".

L'implementazione SGD è lento a causa di questa linea:

for each training example i:

Qui si utilizza esplicitamente esattamente un esempio per ogni aggiornamento dei parametri del modello. Per definizione, vettoriale è una tecnica per operazioni conversione su un elemento in operazioni su un vettore di tali elementi. Quindi, no, non è possibile elaborare esempi uno per uno e ancora usare vettorializzazione.

È possibile, tuttavia, approssimativa vero SGD utilizzando mini-lotti . Mini-batch è un piccolo sottoinsieme di dati originale (ad esempio, 100 esempi). Si calcola gli aggiornamenti di errore e dei parametri sulla base di mini-lotti, ma è ancora iterare su molti di loro senza ottimizzazione globale, rendendo il processo stocastico. Quindi, per rendere l'implementazione molto più veloce è sufficiente per cambiare la linea precedente:

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

e l'errore calcolare da lotto, non da un solo esempio.

Anche se abbastanza ovvio, vorrei anche menzionare vettorializzazione sul livello di singolo esempio. Cioè, invece di qualcosa di simile a questo:

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

si dovrebbe assolutamente fare qualcosa di simile:

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

, che, ancora una volta, facile da generalizzare per mini-lotti:

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)

Answer 2

Scopri il metodo partial_fit di scikit è SGD classificatore . Hai il controllo su ciò che si chiama con esso: si può fare "vero" apprendimento on-line passando un'istanza alla volta, oppure è possibile in batch fino casi in mini-lotti se sono disponibili tutti i dati in un array. Se lo sono, è possibile affettare la matrice per fornire le minibatches.