Keturunan gradien stokastik berdasarkan pada operasi vektor?

mari kita asumsikan bahwa saya ingin melatih algoritma regresi penurunan gradien stokastik menggunakan dataset yang memiliki sampel N. Karena ukuran dataset sudah diperbaiki, saya akan menggunakan kembali data T kali. Pada setiap iterasi atau "zaman", saya menggunakan masing-masing sampel pelatihan tepat satu kali setelah secara acak memesan kembali seluruh rangkaian pelatihan.

Implementasi saya didasarkan pada Python dan Numpy. Oleh karena itu, menggunakan operasi vektor dapat sangat mengurangi waktu komputasi. Datang dengan implementasi vektor keturunan gradien batch cukup mudah. Namun, dalam kasus keturunan gradien stokastik saya tidak bisa mencari cara untuk menghindari loop luar yang berulang melalui semua sampel di setiap zaman.

Adakah yang tahu implementasi vektor dari penurunan gradien stokastik?

EDIT : Saya ditanya mengapa saya ingin menggunakan gradient descent online jika ukuran dataset saya diperbaiki.

Dari [1], orang dapat melihat bahwa penurunan gradien online menyatu lebih lambat dari penurunan gradien batch ke minimum biaya empiris. Namun, konvergen lebih cepat ke minimum biaya yang diharapkan, yang mengukur kinerja generalisasi. Saya ingin menguji dampak dari hasil teoritis ini dalam masalah khusus saya, dengan cara validasi silang. Tanpa implementasi vectorized, kode online gradient descent saya jauh lebih lambat daripada batch gradient descent. Itu sangat meningkatkan waktu yang diperlukan untuk proses validasi silang untuk diselesaikan.

EDIT : Saya menyertakan di sini pseudocode implementasi gradient descent on-line saya, seperti yang diminta oleh teman. Saya memecahkan masalah regresi.

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] "Pembelajaran Online Skala Besar", L. Bottou, Y. Le Cunn, NIPS 2003.

Pertama-tama, kata "sampel" biasanya digunakan untuk menggambarkan subset populasi , jadi saya akan merujuk hal yang sama dengan "contoh".

Implementasi SGD Anda lambat karena baris ini:

for each training example i:

Di sini Anda secara eksplisit menggunakan tepat satu contoh untuk setiap pembaruan parameter model. Menurut definisi, vektorisasi adalah teknik untuk mengubah operasi pada satu elemen menjadi operasi pada vektor elemen tersebut. Jadi, tidak, Anda tidak dapat memproses contoh satu per satu dan masih menggunakan vektorisasi.

Namun, Anda dapat memperkirakan SGD sebenarnya dengan menggunakan mini-batch . Mini-batch adalah sebagian kecil dari dataset asli (misalnya, 100 contoh). Anda menghitung kesalahan dan pembaruan parameter berdasarkan mini-batch, tetapi Anda masih menggunakannya berulang kali tanpa optimasi global, membuat proses menjadi stokastik. Jadi, untuk membuat implementasi Anda lebih cepat, cukup mengubah baris sebelumnya menjadi:

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

dan menghitung kesalahan dari batch, bukan dari satu contoh.

Meskipun cukup jelas, saya juga harus menyebutkan vektorisasi pada tingkat per-contoh. Artinya, bukannya sesuatu seperti ini:

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

Anda pasti harus melakukan sesuatu seperti ini:

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

yang, sekali lagi, mudah digeneralisasi untuk mini-batch:

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)

Lihatlah metode partial_fit dari classifier SGD scikit . Anda memiliki kendali atas apa yang Anda panggil dengannya: Anda dapat melakukannya dengan belajar online "benar" dengan melewatkan sebuah instance pada satu waktu, atau Anda dapat mengelompokkan instance menjadi mini-batch jika semua data Anda tersedia dalam array. Jika ya, Anda dapat mengiris array untuk menyediakan minibatch.