Pemelajaran mesin daring

Bagian dari seri
Pembelajaran mesin dan penggalian data
Paradigma Pembelajaran terbimbing Pembelajaran tak terbimbing Pembelajaran mesin daring Pembelajaran mesin luring Meta-learning Pembelajaran semiterbimbing Pembelajaran swabimbing Pembelajaran pengukuhan Pembelajaran berbasis aturan Pembelajaran mesin kuantum
Masalah Klasifikasi Model generatif Regresi Kluster Reduksi dimensi Estimasi densitas Deteksi anomali Pembersihan data AutoML Aturan asosiasi Analisis semantik Rekayasa fitur Pembelajaran fitur
Pembelajaran terbimbing (Klasifikasi •Regresi) Pohon keputusan Pembelajaran ensambel Bagging boosting Random forest k-NN Regresi linear Naive Bayes Jaringan saraf tiruan Regresi logistik Perseptron Support vector machine (SVM)
Kekelompokkan BIRCH CURE Hierarki k-means Fuzi
Reduksi dimensi AKU
Jaringan saraf tiruan Pembelajaran dalam Jaringan saraf konvolusional
Diagnostik model Kurva belajar
l b s

Dalam ilmu komputer, pemelajaran mesin daring (bahasa Inggris: online machine learning atau online learning) adalah suatu paradigma dalam pemelajaran mesin yang menekankan pembaruan atau penyesuaian model secara dinamis seiring dengan masuknya data baru secara real-time.^[1] Dalam metode ini, pemelajar bertujuan untuk mempelajari dan meningkatkan prediktor terbaik untuk data masa depan pada setiap langkah, berbeda dengan pemelajaran lompok (batch learning) yang menggunakan seluruh himpunan data pelatihan sekaligus. Pemelajaran mesin daring umumnya digunakan ketika tidak memungkinkan secara komputasional untuk melakukan proses pelatihan di keseluruhan data himpunan sehingga memerlukan algoritma out-of-core. Selain itu, metode ini juga diterapkan dalam kondisi ketika algoritma perlu beradaptasi secara dinamis dengan pola-pola baru dalam data, atau ketika data itu sendiri dihasilkan sebagai fungsi waktu, misalnya, prediksi harga saham. Namun, perlu dicatat bahwa algoritma pemelajaran daring dapat menghadapi tantangan seperti catastrophic interference, suatu fenomena dengan pemelajaran informasi baru menghapus pengetahuan yang sudah diperoleh sebelumnya. Masalah ini dapat diatasi dengan menggunakan pendekatan incremental learning, memungkinkan algoritma untuk belajar dan beradaptasi secara iteratif tanpa mengakibatkan gangguan yang signifikan pada pola-pola yang telah dipelajari sebelumnya.

Pengenalan

Dalam konteks paradigma pemelajaran terarah, fungsi yang akan dipelajari oleh model adalah f : X → Y {\displaystyle f:X\to Y} dengan X {\displaystyle X} sebagai ruang masukan (input) dan Y {\displaystyle Y} sebagai label atau ruang keluaran (output). Fungsi ini diharapkan dapat memprediksi dengan baik titik-titik data yang diambil dari distribusi probabilitas bersama p ( x , y ) {\displaystyle p(x,y)} pada X × Y {\displaystyle X\times Y} . Namun dalam kenyataannya, pemelajar atau model tidak mengetahui true distribution p ( x , y ) {\displaystyle p(x,y)} terhadap titik-titik data dan biasanya hanya mengakses himpunan pelatihan yang berisi titik-titik data ( x 1 , y 1 ) , … , ( x n , y n ) {\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})} . Untuk mengukur seberapa baik prediksi model, digunakan fungsi kerugian V : Y × Y → R {\displaystyle V:Y\times Y\to \mathbb {R} } , yang memberikan nilai dari selisih antara prediksi f ( x ) {\displaystyle f(x)} dan nilai sebenarnya y {\displaystyle y} . Ide utamanya adalah mengubah parameter dalam fungsi f {\displaystyle f} sedemikian rupa sehingga kesalahan (loss) pada himpunan data pelatihan menjadi sekecil mungkin. Dengan cara ini, model dapat memberikan prediksi yang lebih akurat pada data yang belum pernah dilihat sebelumnya. Bergantung pada jenis model yang digunakan, baik itu bersifat statistis maupun adversarial, dapat dirancang berbagai konsep kerugian (loss) yang mengarah pada algoritma pembelajaran yang berbeda.

Pandangan statistik pemelajaran daring

Dalam model pemelajaran statistik, sampel pelatihan ( x i , y i ) {\displaystyle (x_{i},y_{i})} diasumsikan diambil dari true distribution p ( x , y ) {\displaystyle p(x,y)} dengan tujuan meminimalkan "risiko" harapan

I [ f ] = E [ V ( f ( x ) , y ) ] = ∫ V ( f ( x ) , y ) d p ( x , y )   . {\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}

Pendekatan yang umum digunakan di situasi ini adalah memperkirakan sebuah fungsi f ^ {\displaystyle {\hat {f}}} melalui minimasi risiko empiris atau minimasi risiko empiris yang teregularisasi (biasanya regularisasi Tikhonov). Pemilihan fungsi kerugian di sini menyebabkan munculnya beberapa algoritma terkenal, seperti algoritma least squares yang teregularisasi dan support-vector machines.

Model pembelajaran daring murni dalam kategori ini akan belajar hanya berdasarkan input baru ( x t + 1 , y t + 1 ) {\displaystyle (x_{t+1},y_{t+1})} , prediktor terbaik saat ini f t {\displaystyle f_{t}} , dan beberapa informasi tambahan yang disimpan (yang biasanya diharapkan memiliki kebutuhan penyimpanan yang independen dari ukuran data pelatihan). Untuk beberapa formulasi, misalnya metode kernel, pemelajaran daring murni tidak mungkin dilakukan. Namun, terdapat suatu bentuk pemelajaran daring campuran dengan menggunakan algoritma rekursif dengan f t + 1 {\displaystyle f_{t+1}} diperbolehkan bergantung pada f t {\displaystyle f_{t}} dan semua titik data sebelumnya ( x 1 , y 1 ) , … , ( x t , y t ) {\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})} . Dalam kasus ini, kebutuhan ruang penyimpanan tidak lagi dapat dijamin bernilai konstan karena ruang penyimpanan tersebut memerlukan penyimpanan titik-titik data sebelumnya. Namun, solusi ini mungkin saja membutuhkan waktu komputasi yang lebih sedikit jika dibandingkan dengan teknik pemelajaran lompok (batch learning).

Strategi yang umumnya digunakan untuk menyelesaikan masalah di atas adalah dengan belajar menggunakan kelompok kecil (mini-batch) yang memproses sebuah kelompok kecil dari b ≥ 1 {\displaystyle b\geq 1} titik-titik data dalam satu waktu. Strategi ini bisa dianggap sebagai pemelajaran daring semu (pseudo-online) untuk b {\displaystyle b} yang jauh lebih kecil dari total jumlah data pelatihan. Teknik ini biasanya digunakan dengan memanggil berulang pada data pelatihan untuk mendapatkan versi out-of-core yang teroptimasi dari algoritma pemelajaran mesin, seperti penurunan gradien stokastik yang ketika digabungkan dengan perambatan mundur, merupakan strategi metode pelatihan de facto untuk jaringan saraf tiruan.

Contoh: linear least squares

Contoh sederhana dari linear least squares digunakan untuk menjelaskan berbagai konsep dalam pemelajaran daring. Konsep-konsep tersebut cukup umum sehingga dapat diterapkan pada pendekatan lain. Contohnya, dengan fungsi kerugian konveks yang berbeda.

Pemelajaran batch

Pertimbangkan terdapat fungsi linear f {\displaystyle f} dalam pemelajaran diawasi yang akan dipelajari:

f ( x j ) = ⟨ w , x j ⟩ = w ⋅ x j {\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}

dengan x j ∈ R d {\displaystyle x_{j}\in \mathbb {R} ^{d}} adalah vektor masukan (titik-titik data atau data points) dan w ∈ R d {\displaystyle w\in \mathbb {R} ^{d}} adalah vektor filter linear. Di sini tujuan yang ingin dicapai adalah menghitung vektor filter w {\displaystyle w} dengan fungsi kerugian kuadrat (square loss function):

V ( f ( x j ) , y j ) = ( f ( x j ) − y j ) 2 = ( ⟨ w , x j ⟩ − y j ) 2 {\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}

Fungsi tersebut digunakan untuk menghitung vektor w {\displaystyle w} yang meminimalkan kerugian empiris:

I n [ w ] = ∑ j = 1 n V ( ⟨ w , x j ⟩ , y j ) = ∑ j = 1 n ( x j T w − y j ) 2 {\displaystyle I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}}

dengan

y j ∈ R {\displaystyle y_{j}\in \mathbb {R} } .

Di sini, y j {\displaystyle y_{j}} adalah nilai target yang bersesuaian dengan masukan x j {\displaystyle x_{j}} dan berada di ruang R {\displaystyle \mathbb {R} } .

Misal, X {\displaystyle X} adalah matriks data berukuran i × d {\displaystyle i\times d} dan y ∈ R i {\displaystyle y\in \mathbb {R} ^{i}} adalah kolom nilai target setelah kedatangan i {\displaystyle i} titik-titik data. Asumsikan matriks kovarian Σ i = X T X {\displaystyle \Sigma _{i}=X^{T}X} dapat diinvers (jika tidak, pendekatan dengan regularisasi Tikhonov lebih disukai), solusi terbaik f ∗ ( x ) = ⟨ w ∗ , x ⟩ {\displaystyle f^{*}(x)=\langle w^{*},x\rangle } untuk masalah linear least squares diberikan oleh

w ∗ = ( X T X ) − 1 X T y = Σ i − 1 ∑ j = 1 i x j y j {\displaystyle w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}} .

Sekarang, perhitungan kovarian matriks Σ i = ∑ j = 1 i x j x j T {\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}} memerlukan waktu O ( i d 2 ) {\displaystyle O(id^{2})} , menginverskan matriks d × d {\displaystyle d\times d} memerlukan waktu O ( d 3 ) {\displaystyle O(d^{3})} , sementara perkalian sisanya memerlukan waktu O ( d 2 ) {\displaystyle O(d^{2})} , memberikan total waktu yang diperlukan sebesar O ( i d 2 + d 3 ) {\displaystyle O(id^{2}+d^{3})} . Ketika terdapat total n {\displaystyle n} titik di himpunan data, untuk menghitung ulang solusi setelah kedatangan dari setiap titik data i = 1 , … , n {\displaystyle i=1,\ldots ,n} , pendekatan naif akan membutuhkan waktu O ( n 2 d 2 + n d 3 ) {\displaystyle O(n^{2}d^{2}+nd^{3})} . Di sini bisa dilakukan alternatif dengan menyimpan matriks Σ i {\displaystyle \Sigma _{i}} , kemudian memperbarui solusi dengan menambahkan x i + 1 x i + 1 T {\displaystyle x_{i+1}x_{i+1}^{T}} setiap kali kedatangan titik data baru, dapat menurunkan kompleksitas menjadi O ( d 2 ) {\displaystyle O(d^{2})} . Pendekatan ini menurunkan kompleksitas waktu secara keseluruhan menjadi O ( n d 2 + n d 3 ) = O ( n d 3 ) {\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})} , tetapi dengan tambahan penyimpanan sebesar O ( d 2 ) {\displaystyle O(d^{2})} untuk Σ i {\displaystyle \Sigma _{i}} .^[2]

Pemelajaran daring dengan least squares rekursif

Algoritma Recursive Least Squares (RLS) merupakan pendekatan daring (online approach) terhadap masalah least squares. Algoritma ini memungkinkan untuk menghitung solusi dari masalah least squares secara bertahap dengan memperbarui solusi setiap kali ada datapoint baru. Hal tersebut dapat ditunjukkan dengan menginisialisasi

w 0 = 0 ∈ R d {\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}} dan Γ 0 = I ∈ R d × d {\displaystyle \textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}}

dengan I {\displaystyle I} adalah matriks identitas.

Di setiap iterasi ke- i {\displaystyle i} , algoritma akan menghitung Γ i {\displaystyle \Gamma _{i}} dan w i {\displaystyle w_{i}} dengan memperbarui solusi dari iterasi sebelumnya.

Solusi dari masalah linear least square yang diberikan pada bagian sebelumnya dapat dihitung dengan iterasi berikut:

Γ i = Γ i − 1 − Γ i − 1 x i x i T Γ i − 1 1 + x i T Γ i − 1 x i {\displaystyle \Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}}

dengan x i {\displaystyle x_{i}} merupakan vektor masukan dari datapoint ke- i {\displaystyle i} dan Γ i − 1 {\displaystyle \Gamma _{i-1}} merupakan matriks kovarian dari iterasi sebelumnya. Adapun untuk vektor bobot w i {\displaystyle w_{i}} diperbarui dengan rumus

w i = w i − 1 − Γ i x i ( x i T w i − 1 − y i ) {\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}

dengan y i {\displaystyle y_{i}} adalah nilai target yang sesuai dengan datapoint ke- i {\displaystyle i} .

Algoritma iterasi di atas dibuktikan dengan menggunakan induksi pada i {\displaystyle i} .^[3] Pembuktian tersebut juga menyatakan bahwa Γ i = Σ i − 1 {\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}} . Algoritma RLS juga dapat dinilai dalam konteks filter adaptif (lihat RLS).

Kompleksitas waktu untuk n {\displaystyle n} langkah dari algoritma ini adalah O ( n d 2 ) {\displaystyle O(nd^{2})} , yang jauh lebih cepat daripada kompleksitas pemelajaran batch yang sesuai. Di setiap langkah i {\displaystyle i} , perlu menyimpan matriks Γ i {\displaystyle \Gamma _{i}} , keperluan penyimpanan ini konstan pada O ( d 2 ) {\displaystyle O(d^{2})} . Untuk kasus ketika matriks kovarian Σ i {\displaystyle \Sigma _{i}} tidak bisa diinvers, algoritma dapat disesuaikan dengan menggunakan versi teregulasi dari fungsi kerugian ∑ j = 1 n ( x j T w − y j ) 2 + λ | | w | | 2 2 {\displaystyle \sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}} . Kemudian, akan mudah menunjukkan algoritma yang sama dapat bekerja dengan Γ 0 = ( I + λ I ) − 1 {\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}} dan ketika iterasi berlangsung akan menghasilkan Γ i = ( Σ i + λ I ) − 1 {\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}} .^[2]

Stochastic gradient descent

Ketika formula berikut

w i = w i − 1 − Γ i x i ( x i T w i − 1 − y i ) {\displaystyle \textstyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}

diganti dengan

w i = w i − 1 − γ i x i ( x i T w i − 1 − y i ) = w i − 1 − γ i ∇ V ( ⟨ w i − 1 , x i ⟩ , y i ) {\displaystyle \textstyle w_{i}=w_{i-1}-\gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})}

atau Γ i ∈ R d × d {\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}} dengan γ i ∈ R {\displaystyle \gamma _{i}\in \mathbb {R} } , maka algoritma tersebut berubah menjadi algoritma stochastic gradient descent (SGD). Dalam kasus ini, kompleksitas waktu untuk langkah n {\displaystyle n} berkurang menjadi O ( n d ) {\displaystyle O(nd)} dan kebutuhan ruang untuk setiap langkah i {\displaystyle i} adalah konstan di O ( d ) {\displaystyle O(d)} .

Meskipun begitu, besarnya langkah γ i {\displaystyle \gamma _{i}} harus dipilih dengan hati-hati untuk menyelesaikan masalah minimasi risiko harapan, sebagaimana yang telah dijelaskan di atas. Dengan memilih besar langkah peluruhan γ i ≈ 1 i , {\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}},} didapatkan pembuktian konvergensi dari iterasi rata-rata w ¯ n = 1 n ∑ i = 1 n w i {\displaystyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}} . Skema ini merupakan salah satu kasus khusus dari optimasi stokastik yang mana merupakan salah satu masalah optimasi terkenal.^[2]

Incremental stochastic gradient descent

Dalam praktiknya, seseorang dapat melakukan pemanggilan beberapa SGD (juga dinamakan sebagai siklus atau epoch) pada data. Algoritma yang kemudian didapatkan tersebut dinamakan sebagai incremental stochastic gradient descent dan mengikut pada iterasi

w i = w i − 1 − γ i ∇ V ( ⟨ w i − 1 , x t i ⟩ , y t i ) {\displaystyle \textstyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}

Perbedaan utama algoritma ini dengan SGD adalah pada algoritma ini terdapat sebuah sekuens t i {\displaystyle t_{i}} yang dipilih untuk memutuskan titik pelatihan mana yang akan dikunjungi pada langkah ke- i {\displaystyle i} yang mana sekuens ini dapat bersifat stokastik atau deterministik. Banyaknya iterasi kemudian dipisah menjadi banyak titik (tiap titik dapat dipertimbangkan lebih dari sekali). Algoritma ini dapat ditunjukkan mampu memberikan minimasi pada risiko empiris.^[4] Incremental techniques can be advantageous when considering objective functions made up of a sum of many terms e.g. an empirical error corresponding to a very large dataset.^[2]

Metode kernel

Kernel dapat digunakan untuk memperluas algoritma-algoritma di atas menjadi model non-parameter (atau model yang parameter-parameternya membentuk sebuah ruang dimensi tak terhingga). Metode ini tidak bisa lagi bisa disebut sebagai pemelajaran daring penuh karena melibatkan penyimpanan seluruh titik data. Meskipun begitu, metode ini lebih cepat daripada metode brute-force. Metode kernel ini dapat digunakan untuk seluruh loss conveks yang lain, tetapi pada bagian ini pembahasan dibataskan pada square loss. Penerapan metode kernel pada square loss ditunjukkan dengan sebuah induksi sederhana^[2] yang jika X i {\displaystyle X_{i}} adalah matriks data dan w i {\displaystyle w_{i}} adalah keluaran setelah langkah i {\displaystyle i} dari algoritma SGD, maka,

w i = X i T c i {\displaystyle w_{i}=X_{i}^{T}c_{i}}

dengan c i = ( ( c i ) 1 , ( c i ) 2 , . . . , ( c i ) i ) ∈ R i {\displaystyle \textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}} dan sekuens c i {\displaystyle c_{i}} memenuhi rekursi:

c 0 = 0 {\displaystyle c_{0}=0}

( c i ) j = ( c i − 1 ) j , j = 1 , 2 , . . . , i − 1 {\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1} dan

( c i ) i = γ i ( y i − ∑ j = 1 i − 1 ( c i − 1 ) j ⟨ x j , x i ⟩ ) {\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}}

Perhatikan bahwa di sini ⟨ x j , x i ⟩ {\displaystyle \langle x_{j},x_{i}\rangle } hanyalah kernel standar pada R d {\displaystyle \mathbb {R} ^{d}} , dan prediktornya didapatkan dari bentuk

f i ( x ) = ⟨ w i − 1 , x ⟩ = ∑ j = 1 i − 1 ( c i − 1 ) j ⟨ x j , x ⟩ {\displaystyle f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle } .

Misalkan, jika suatu kernel umum K {\displaystyle K} diperkenalkan dan prediktornya adalah

f i ( x ) = ∑ j = 1 i − 1 ( c i − 1 ) j K ( x j , x ) {\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}

maka pembuktian yang sama juga akan menunjukkan bahwa prediktor dapat melakukan minimasi pada least square loss dengan mengganti rekursif di atas menjadi

( c i ) i = γ i ( y i − ∑ j = 1 i − 1 ( c i − 1 ) j K ( x j , x i ) ) {\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}}

Rumus di atas membutuhkan penyimpanan seluruh data untuk memperbarui c i {\displaystyle c_{i}} . Total kompleksitas waktu untuk rekursi di atas ketika mengevaluasi titik data ke- n {\displaystyle n} adalah O ( n 2 d k ) {\displaystyle O(n^{2}dk)} , dengan k {\displaystyle k} adalah biaya yang diperlukan untuk mengevaluasi kernel dari sepasang titik.^[2] Maka, dengan penggunaan kernel di atas menjadikan pergerakan dari suatu dimensi terbatas w i ∈ R d {\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}} menjadi sebuah kemungkinan fitur dimensi tak terbatas yang direpresentasikan oleh sebuah kernel K {\displaystyle K} dengan melakukan rekursi di ruang parameter c i ∈ R i {\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}} , yang mana dimensi di sini memiliki besar yang sama dengan himpunan data pelatihan. Secara umum, ini adalah suatu akibat dari representer theorem.^[2]

Online convex optimization

Online convex optimization (OCO) ^[5] adalah kerangka kerja umum (framework) untuk pengambilan keputusan yang memanfaatkan convex optimization untuk menghasilkan algoritma yang efisien. Kerangka kerja ini mengikuti pola permainan (game playing berulang, sebagai berikut: Untuk t = 1 , 2 , . . . , T {\displaystyle t=1,2,...,T}

• Pemelajar menerima masukan x t {\displaystyle x_{t}}
• Pemelajar menghasilkan keluaran w t {\displaystyle w_{t}} dari sebuah himpunan konveks tetap S {\displaystyle S}
• Nature (alam) mengirimkan balik fungsi kerugian konveks v t : S → R {\displaystyle v_{t}:S\rightarrow \mathbb {R} } .
• Pemelajar mengalami kerugian v t ( w t ) {\displaystyle v_{t}(w_{t})} dan memperbarui modelnya

Tujuan dari OCO adalah meminimalkan regret, yaitu selisih antara akumulasi kerugian dan kerugian yang didapatkan dari titik tetap terbaik (best fixed point) u ∈ S {\displaystyle u\in S} yang dapat dipilh dalam pengamatan kembali. Sebagai contoh, pertimbangkan kasus regresi linear least squares. Di sini, vektor weight didapatkan dari himpunan konveks S = R d {\displaystyle S=\mathbb {R} ^{d}} , dan nature (alam) mengirimkan balik fungsi kerugian konveks v t ( w ) = ( ⟨ w , x t ⟩ − y t ) 2 {\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}} . Perhatikan bahwa di sini y t {\displaystyle y_{t}} dikirim secara implisit dengan v t {\displaystyle v_{t}} .

Akan tetapi, beberapa masalah prediksi daring tidak cocok dimasukkan ke dalam kerangka kerja OCO ini. Sebagai contoh, dalam klasifikasi daring, domain klaisifikasi dan fungsi kerugian, keduanya tidak bersifat konveks. Oleh karena itu, di kasus ini, teknik sederhana untuk konveksifikasi digunakan, yaitu randomisasi dan fungsi kerugian pengganti ^{[butuh rujukan]}.

Beberapa algoritma sederhana dalam optimisasi konveks, antara lain:

Follow the leader (FTL)

Algoritma sederhana dalam optimisasi konveks yang pertama adalah Follow the Leader (FTL) yang merupakan teknik yang paling sederhana dengan hanya memilih (pada langkah saat ini) hipotesis yang memiliki kerugian paling sedikit sepanjang iterasi sebelumnya. Algoritma ini disebut Follow the Leader, dan iterasi atau round t {\displaystyle t} dihitung sebagai berikut:

w t = a r g m i n w ∈ S ⁡ ∑ i = 1 t − 1 v i ( w ) {\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}

Dengan kata lain, pada setiap langkah, kita memilih hipotesis w t {\displaystyle w_{t}} yang meminimalkan total kerugian sepanjang iterasi sebelumnya. Metode ini dapat dianggap sebagai algoritma serakah (greedy algorithm) karena setiap keputusan diambil dengan tujuan meminimalkan kerugian yang telah terjadi.

Pada kasus optimasi online quadratic yang fungsi kerugiannya adalah v t ( w ) = | | w − x t | | 2 2 {\displaystyle v_{t}(w)=||w-x_{t}||_{2}^{2}} ), dapat ditunjukkan bahwa terdapat batas regret yang naik sebanding log ⁡ ( T ) {\displaystyle \log(T)} . Namun, batas serupa tidak dapat didapatkan oleh algoritma FTL pada keluarga model penting lainnya, seperti optimisasi linear online. Untuk mencapai batasan tersebut, FTL perlu dimodifikasi dengan menambahkan regularisasi.

Follow the regularised leader (FTRL)

FTRL adalah modifikasi dari FTL yang dimaksudkan untuk menstabilkan solusi yang didapatkan dari FTL dan mendapatkan batas regret yang lebih baik. Sebuah fungsi regularisasi R : S → R {\displaystyle R:S\rightarrow \mathbb {R} } dipilih dan pemelajaran dilakukan pada iterasi t sebagai berikut:

w t = a r g m i n w ∈ S ⁡ ∑ i = 1 t − 1 v i ( w ) + R ( w ) {\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}

Sebagai contoh khusus, pertimbangkan kasus online linear optimisation , yaitu ketika alam mengirimkan kembali fungsi kerugian dalam bentuk v t ( w ) = ⟨ w , z t ⟩ {\displaystyle v_{t}(w)=\langle w,z_{t}\rangle } dan S = R d {\displaystyle S=\mathbb {R} ^{d}} . Misal, fungsi regularisasi R ( w ) = 1 2 η | | w | | 2 2 {\displaystyle R(w)={\frac {1}{2\eta }}||w||_{2}^{2}} dipilih untuk suatu bilangan positif η {\displaystyle \eta } . Maka, dapat ditunjukkan bahwa iterasi yang meminimalkan regret menjadi

w t + 1 = − η ∑ i = 1 t z i = w t − η z t {\displaystyle w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}}

Perhatikan bahwa ini dapat ditulis ulang sebagai w t + 1 = w t − η ∇ v t ( w t ) {\displaystyle w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})} yang ini persis sama dengan SGD sebelumnya.

Jika S adalah sebuah subruang konveks dari R d {\displaystyle \mathbb {R} ^{d}} , S harus diproyeksikan ke, yang akhirnya mengarah kepada modikasi aturan pembaruan

w t + 1 = Π S ( − η ∑ i = 1 t z i ) = Π S ( η θ t + 1 ) {\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}

Algoritma ini dikenal sebagai lazy projection, karena vektor θ t + 1 {\displaystyle \theta _{t+1}} mengakumulasi gradien. Algoritma ini juga dikenal sebagai Nesterov's dual averaging algorithm. Dalam skenario fungsi kerugian linier (linear loss functions) dan regularisasi kuadratik (quadratic regularisation) ini, regret dibatasi oleh O ( T ) {\displaystyle O({\sqrt {T}})} . Dengan demikian, rata-rata regret menuju kepada 0 sesuai yang diinginkan.

Online subgradient descent (OSD)

Di atas telah dibuktikan sebuah batas regret untuk fungsi kerugian linear v t ( w ) = ⟨ w , z t ⟩ {\displaystyle v_{t}(w)=\langle w,z_{t}\rangle } . Maka untuk menggeneralisasi algoritma sehingga dapat berlaku untuk semua fungsi kerugian konveks, subgradien ∂ v t ( w t ) {\displaystyle \partial v_{t}(w_{t})} dari v t {\displaystyle v_{t}} digunakan sebagai suatu aproksimasi linear terhadap v t {\displaystyle v_{t}} dekat w t {\displaystyle w_{t}} yang kemudian menagrah kepada algoritma OSD:

Inisialisasi parameter η , w 1 = 0 {\displaystyle \eta ,w_{1}=0}

Untuk t = 1 , 2 , . . . , T {\displaystyle t=1,2,...,T}

• Lakukan prediksi menggunakan w t {\displaystyle w_{t}} , menerima f t {\displaystyle f_{t}} dari nature.
• Pilih z t ∈ ∂ v t ( w t ) {\displaystyle z_{t}\in \partial v_{t}(w_{t})}
• Jika S = R d {\displaystyle S=\mathbb {R} ^{d}} , perbarui sampai w t + 1 = w t − η z t {\displaystyle w_{t+1}=w_{t}-\eta z_{t}}
• Jika S ⊂ R d {\displaystyle S\subset \mathbb {R} ^{d}} , proyeksikan gradien akumulatif kepada S {\displaystyle S} i.e. w t + 1 = Π S ( η θ t + 1 ) , θ t + 1 = θ t + z t {\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}

OSD dapat digunakan untuk menurunkan O ( T ) {\displaystyle O({\sqrt {T}})} iterasi bound untuk versi dari dari SVM untuk klasifikasi yang menggunakan kerugian hinge v t ( w ) = max { 0 , 1 − y t ( w ⋅ x t ) } {\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}

Algoritma lainnya

Algoritma FTRL yang teregularisi secara kuadratik menyebabkan algoritma gradien menjadi diproyeksikan secara "malas" seperti yang dijelaskan di atas. Untuk mengimplementasikan cara di atas untuk fungsi konveks dan regularisator sembarang, dapat digunakan online mirror descent. Regularisasi optimal nantinya dapat diturunkan untuk fungsi kerugian linier yang kemudian mengarah kepada algoritma AdaGrad. Untuk regularisasi Euclidean, dapat ditunjukkan batas regret O ( T ) {\displaystyle O({\sqrt {T}})} , yang dapat diperbaiki lebih lanjut menjadi O ( log ⁡ T ) {\displaystyle O(\log T)} untuk fungsi kerugian konveks dan exp-concave yang sangat kuat.

Pemelajaran yang berkelanjutan

Pemelajaran berkelanjutan atau continual learning berarti terus meningkatkan model yang dipelajari dengan cara memproses aliran informasi yang terus menerus berubah.^[6] Kemampuan pembelajaran berkelanjutan sangat penting untuk sistem perangkat lunak dan agen otonom yang berinteraksi di dunia nyata yang terus berubah. Namun, pemelajaran berkelanjutan merupakan tantangan bagi pemelajaran mesin dan model jaringan syaraf karena akuisisi informasi yang tersedia secara bertahap dari distribusi data non-stasioner secara umum mengarah pada catastrophic forgetting.

Interpretasi pemelajaran daring

Paradigma pemeelajaran online memiliki interpretasi yang berbeda, tergantung dengan pilihan model pemelajaran, yang masing-masing memiliki implikasi yang berbeda terkait kualitas prediksi dari barisan fungsi f 1 , f 2 , … , f n {\displaystyle f_{1},f_{2},\ldots ,f_{n}} . Algoritma prototipe stochastic gradient descent digunakan untuk diskusi ini. Seperti yang telah disebutkan di atas, rekursinya diberikan oleh

w t = w t − 1 − γ t ∇ V ( ⟨ w t − 1 , x t ⟩ , y t ) {\displaystyle \textstyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}

Interpretasi pertama mempertimbangkan metode stochastic gradient descent yang diterapkan pada masalah minimasi risiko harapan I [ w ] {\displaystyle I[w]} yang telah didefinisikan di atas.^[7] Memang, dalam kasus aliran data yang tak terbatas, karena contoh ( x 1 , y 1 ) , ( x 2 , y 2 ) , … {\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots } diasumsikan diambil secara independen dan terdistribusi secara identik (i.i.d.) dari distribusi p ( x , y ) {\displaystyle p(x,y)} , barisan gradien dari V ( ⋅ , ⋅ ) {\displaystyle V(\cdot ,\cdot )} pada iterasi di atas merupakan contoh i.i.d. sampel estimasi stokastik dari gradien risiko harapan I [ w ] {\displaystyle I[w]} . Oleh karena itu, didapatkan hasil kompleksitas untuk metode SGD untuk mengikat deviasi I [ w t ] − I [ w ∗ ] {\displaystyle I[w_{t}]-I[w^{\ast }]} yang w ∗ {\displaystyle w^{\ast }} adalah minimasi I [ w ] {\displaystyle I[w]} .^[8] Interpretasi ini juga berlaku dalam kasus himpunan pelatihan yang terbatas; meskipun dengan beberapa kali melakukan panggilan terhadap data, gradien tidak lagi independen sehingga tetap saja hasil yang kompleks dapat diperoleh dalam kasus-kasus khusus.

Interpretasi kedua berlaku untuk kasus himpunan pelatihan yang terbatas dan menganggap algoritma SGD sebagai contoh dari metode incremental gradient descent.^[4] Dalam kasus ini, kita akan melihat risiko empiris:

I n [ w ] = 1 n ∑ i = 1 n V ( ⟨ w , x i ⟩ , y i )   . {\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}

Karena gradien V ( ⋅ , ⋅ ) {\displaystyle V(\cdot ,\cdot )} terdapat dalam iterasi incremental SGD yang merupakan estimasi stokastik dari gradien I n [ w ] {\displaystyle I_{n}[w]} , interpretasi ini juga terkait dengan metode SGD, tetapi diterapkan untuk meminimalkan risiko empiris dan bukan risiko harapan. Karena interpretasi ini berkaitan dengan risiko empiris dan bukan risiko harapan, beberapa lintasan melalui data dapat dengan mudah diizinkan dan benar-benar mengarah pada batas yang lebih ketat pada penyimpangan I n [ w t ] − I n [ w n ∗ ] {\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]} dengan w n ∗ {\displaystyle w_{n}^{\ast }} adalah peminimalisasi dari I n [ w ] {\displaystyle I_{n}[w]} .

Implementasi

• Vowpal Wabbit: Sistem pemelajaran daring cepat yang terkenal karena mendukung banyak pemelajaran reduksi, pembobotan kepentingan, dan pilihan fungsi kerugian yang berbeda serta algoritma pengoptimalan. Ini menggunakan trik hashing untuk membatasi ukuran set fitur yang tidak bergantung pada jumlah data pelatihan.
• Scikit-learn: menyediakan implementasi dari algoritma out-of-core
  • Klasifikasi: Perceptron, SGD, Naive bayes.
  • Regresi: SGD Regressor, Passive Aggressive regressor.
  • Klustering: Mini-batch k-means.
  • Ekstraksi fitur: Mini-batch dictionary learning, Incremental PCA.

Lihat juga

Paradigma pemelajaran

• Pemelajaran bertahap
• Lazy learning
• Pemelajaran luring, kebalikan pemelajaran mesin daring
• Pemelajaran kukuh
• Multi-armed bandit
• Pemelajaran terarah

Algoritma umum

• Algoritma daring
• Optimisasi daring
• streaming algorithm
• Turunan gradien stokastik

Model pemelajaran

• Teori Resonansi Adaptif
• Hierarchical temporal memory
• Algoritme k tetangga terdekat
• Learning vector quantization
• Perseptron

Referensi

1. ↑ Hoi, Steven C. H.; Sahoo, Doyen; Lu, Jing; Zhao, Peilin (2021-10-12). "Online learning: A comprehensive survey". Neurocomputing. 459. doi:10.1016/j.neucom.2021.04.112.
2. 1 2 3 4 5 6 7 L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning
3. ↑ Yin, Harold J. Kushner, G. George (2003). Stochastic approximation and recursive algorithms and applications (Edisi Second). New York: Springer. hlm. 8–12. ISBN 978-0-387-21769-7.{{cite book}}: Pemeliharaan CS1: Banyak nama: daftar penulis (link)
4. 1 2 Bertsekas, D. P. (2011). Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. Optimization for Machine Learning, 85.
5. ↑ Hazan, Elad (2015). Introduction to Online Convex Optimization (PDF). Foundations and Trends in Optimization.
6. ↑ Parisi, German I.; Kemker, Ronald; Part, Jose L.; Kanan, Christopher; Wermter, Stefan (2019). "Continual lifelong learning with neural networks: A review". Neural Networks. 113: 54–71. arXiv:1802.07569. doi:10.1016/j.neunet.2019.01.012. ISSN 0893-6080.
7. ↑ Bottou, Léon (1998). "Online Algorithms and Stochastic Approximations". Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6.
8. ↑ Stochastic Approximation Algorithms and Applications, Harold J. Kushner and G. George Yin, New York: Springer-Verlag, 1997. ISBN0-387-94916-X; 2nd ed., titled Stochastic Approximation and Recursive Algorithms and Applications, 2003, ISBN0-387-00894-2.

Pranala luar

• 6.883: Online Methods in Machine Learning: Theory and Applications. Alexander Rakhlin. MIT