Stochastyczne opadanie gradientu w oparciu o operacje wektorowe?

Załóżmy, że chcę trenować algorytm regresji spadku gradientu stochastycznego przy użyciu zestawu danych zawierającego N próbek. Ponieważ rozmiar zestawu danych jest ustalony, ponownie użyję danych T razy. Przy każdej iteracji lub „epoce” używam każdej próbki treningowej dokładnie raz po losowym uporządkowaniu całego zestawu treningowego.

Moja implementacja oparta jest na Pythonie i Numpy. Dlatego użycie operacji wektorowych może znacznie skrócić czas obliczeń. Wymyślenie wektorowej implementacji opadania gradientu wsadowego jest dość proste. Jednak w przypadku stochastycznego spadku gradientu nie mogę dowiedzieć się, jak uniknąć zewnętrznej pętli, która przechodzi przez wszystkie próbki w każdej epoce.

Czy ktoś zna wektoryzowaną implementację stochastycznego spadku gradientu?

EDYCJA : Zostałem zapytany, dlaczego chciałbym korzystać z opadania gradientu online, jeśli rozmiar mojego zestawu danych jest stały.

Z [1] widać, że opadanie gradientu online zbiega się wolniej niż opadanie gradientu wsadowego do minimum kosztów empirycznych. Jednak zbiega się szybciej do minimum oczekiwanego kosztu, który mierzy wydajność uogólnienia. Chciałbym przetestować wpływ tych teoretycznych wyników w moim konkretnym problemie za pomocą krzyżowej weryfikacji. Bez implementacji wektoryzacyjnej mój kod zejścia gradientowego w trybie online jest znacznie wolniejszy niż kod partii z gradientowym spadkiem. To znacznie wydłuża czas potrzebny na zakończenie procesu weryfikacji krzyżowej.

EDYCJA : Podaję pseudokod mojej implementacji spadku gradientu on-line, zgodnie z prośbą ffriend. Rozwiązuję problem regresji.

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, NIPS 2003.

Po pierwsze, słowo „próbka” jest zwykle używane do opisania podzbioru populacji , więc będę odnosił się do tego samego co „przykład”.

Twoja implementacja SGD jest powolna z powodu tej linii:

for each training example i:

Tutaj jawnie używasz dokładnie jednego przykładu dla każdej aktualizacji parametrów modelu. Z definicji wektoryzacja jest techniką przekształcania operacji na jednym elemencie na operacje na wektorze takich elementów. Dlatego nie możesz przetwarzać przykładów jeden po drugim i nadal używać wektoryzacji.

Możesz jednak oszacować rzeczywistą wartość SGD za pomocą mini-partii . Mini-partia to niewielki podzbiór oryginalnego zestawu danych (powiedzmy 100 przykładów). Obliczasz błędy i aktualizacje parametrów na podstawie mini-partii, ale wciąż iterujesz wiele z nich bez globalnej optymalizacji, co czyni proces stochastycznym. Aby więc znacznie przyspieszyć wdrożenie, wystarczy zmienić poprzednią linię na:

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

i obliczyć błąd z partii, a nie z jednego przykładu.

Choć dość oczywiste, powinienem również wspomnieć o wektoryzacji na poziomie poszczególnych przykładów. Oznacza to, że zamiast czegoś takiego:

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

zdecydowanie powinieneś zrobić coś takiego:

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

które znów jest łatwe do uogólnienia dla mini-partii:

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)

Sprawdź metodę częściowego dopasowania klasyfikatora SGD scikit . Masz kontrolę nad tym, co nazywasz: możesz to zrobić „prawdziwą” nauką online, przekazując instancję na raz, lub możesz grupować instancje w mini-partie, jeśli wszystkie dane są dostępne w tablicy. Jeśli tak, możesz pokroić tablicę, aby uzyskać minibatche.