In computer science, online machine learning is a method of machine learning in which data becomes available in a sequential order and is used to update the best predictor for future data at each step, as opposed to batch learning techniques which generate the best predictor by learning on the entire training data set at once.
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.
It is also used in situations where it is necessary for the algorithm to dynamically adapt to new patterns in the data, or when the data itself is generated as a function of time, e.g., prediction of prices in the financial international markets.
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.
In the setting of supervised learning, a function of f : X → Y is to be learned, where X is thought of as a space of inputs and Y as a space of outputs, that predicts well on instances that are drawn from a joint probability distribution p ( x , y ) on X × Y .
Dalam konteks paradigma pemelajaran terarah, fungsi yang akan dipelajari oleh model adalah f : X → Y dengan X sebagai ruang masukan (input) dan Y sebagai label atau ruang keluaran (output).
In this setting, the loss function is given as V : Y × Y → R } , such that V ( f ( x ) , y ) measures the difference between the predicted value f ( x ) and the true value y .
Untuk mengukur seberapa baik prediksi model, digunakan fungsi kerugian V : Y × Y → R } , yang memberikan nilai dari selisih antara prediksi f ( x ) dan nilai sebenarnya y .
Depending on the type of model (statistical or adversarial), one can devise different notions of loss, which lead to different learning algorithms.
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.
In statistical learning models, the training sample ( x i , y i ) ,y_{i})} are assumed to have been drawn from the true distribution p ( x , y ) and the objective is to minimize the expected "risk" I
Dalam model pemelajaran statistik, sampel pelatihan ( x i , y i ) ,y_{i})} diasumsikan diambil dari true distribution p ( x , y ) dengan tujuan meminimalkan "risiko" harapan I
[V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}
[ f ]E [ V ( f ( x ) , y ) ]∫ V ( f ( x ) , y )
A common paradigm in this situation is to estimate a function f ^ }} through empirical risk minimization or regularized empirical risk minimization (usually Tikhonov regularization).
[V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .} Pendekatan yang umum digunakan di situasi ini adalah memperkirakan sebuah fungsi f ^ }} melalui minimasi risiko empiris atau minimasi risiko empiris yang teregularisasi (biasanya regularisasi Tikhonov).
The choice of loss function here gives rise to several well-known learning algorithms such as regularized least squares and support vector machines.
Pemilihan fungsi kerugian di sini menyebabkan munculnya beberapa algoritma terkenal, seperti algoritma least squares yang teregularisasi dan support-vector machines.
A purely online model in this category would learn based on just the new input ( x t + 1 , y t + 1 ) ,y_{t+1})} , the current best predictor f t } and some extra stored information (which is usually expected to have storage requirements independent of training data size).
Model pembelajaran daring murni dalam kategori ini akan belajar hanya berdasarkan input baru ( x t + 1 , y t + 1 ) ,y_{t+1})} , prediktor terbaik saat ini f t } , dan beberapa informasi tambahan yang disimpan (yang biasanya diharapkan memiliki kebutuhan penyimpanan yang independen dari ukuran data pelatihan).
Mini-batch techniques are used with repeated passing over the training data to obtain optimized out-of-core versions of machine learning algorithms, for example, stochastic gradient descent.
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.
The simple example of linear least squares is used to explain a variety of ideas in online learning.
Contoh sederhana dari linear least squares digunakan untuk menjelaskan berbagai konsep dalam pemelajaran daring.
f ( x j )⟨ w , x j ⟩w ⋅ x j )=\langle w,x_{j}\ranglew\cdot x_{j}} where x j ∈ R d \in \mathbb {R} ^{d}} is a vector of inputs (data points) and w ∈ R d ^{d}} is a linear filter vector.
w ⋅ x j )=\langle w,x_{j}\ranglew\cdot x_{j}} dengan x j ∈ R d \in \mathbb {R} ^{d}} adalah vektor masukan (titik-titik data atau data points) dan w ∈ R d ^{d}} adalah vektor filter linear.
∑ j1 n ( x j T w − y j ) 2 [w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{\mathsf {T}}w-y_{j})^{2}} where y j ∈ R .
∑ j1 n ( x j T w − y j ) 2 [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 \in \mathbb {R} } .
Assuming that the covariance matrix Σ iX T XX^{\mathsf {T}}X} is invertible (otherwise it is preferential to proceed in a similar fashion with Tikhonov regularization), the best solution f ∗ ( x )
Asumsikan matriks kovarian Σ iX T XX^{T}X} dapat diinvers (jika tidak, pendekatan dengan regularisasi
⟨ w ∗ , x ⟩ (x)=\langle w^{*},x\rangle } to the linear least squares problem is given by w ∗( X T X )
⟨ w ∗ , x ⟩ (x)=\langle w^{*},x\rangle } untuk masalah linear least squares diberikan oleh w ∗( X T X ) − 1 X T yΣ i − 1 ∑ j1 i x j y j(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}} .
− 1 X T yΣ i − 1 ∑ j1 i x j y j .
i ( x )∑ j1 i − 1 ( c i − 1 )
=(X^{\mathsf {T}}X)^{-1}X^{\mathsf {T}}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}.}
∑ j1 n ( x j T w − y j ) 2 [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 \in \mathbb {R} } .
Now, calculating the covariance matrix Σ i∑ j1 i x j x j T\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {T}}} takes time O ( i d 2 ) )} , inverting the d × d matrix takes time O ( d 3 ) )} , while the rest of the multiplication takes time O ( d 2 ) )} , giving a total time of O ( i d 2 + d 3 ) +d^{3})} .
Sekarang, perhitungan kovarian matriks Σ i∑ j1 i x j x j T\sum _{j=1}^{i}x_{j}x_{j}^{T}} memerlukan waktu O ( i d 2 ) )} , menginverskan matriks d × d memerlukan waktu O ( d 3 ) )} , sementara perkalian sisanya memerlukan waktu O ( d 2 ) )} , memberikan total waktu yang diperlukan sebesar O ( i d 2 + d 3 ) +d^{3})} .
When there are n total points in the dataset, to recompute the solution after the arrival of every datapoint i1 , … , n , the naive approach will have a total complexity O ( n 2 d 2 + n d 3 ) d^{2}+nd^{3})} .
Ketika terdapat total n titik di himpunan data, untuk menghitung ulang solusi setelah kedatangan dari setiap titik data i1 , … , n , pendekatan naif akan membutuhkan waktu O ( n 2 d 2 + n d 3 ) d^{2}+nd^{3})} .
Note that when storing the matrix Σ i } , then updating it at each step needs only adding x i + 1 x i + 1 T x_{i+1}^{\mathsf {T}}} , which takes O ( d 2 ) )} time, reducing the total time to O ( n d 2 + n d 3 )O ( n d 3 ) +nd^{3})=O(nd^{3})} , but with an additional storage space of O ( d 2 ) )} to store Σ i } .
Di sini bisa dilakukan alternatif dengan menyimpan matriks Σ i } , kemudian memperbarui solusi dengan menambahkan x i + 1 x i + 1 T x_{i+1}^{T}} setiap kali kedatangan titik data baru, dapat menurunkan kompleksitas menjadi O ( d 2 ) )} .
The recursive least squares (RLS) algorithm considers an online approach to the least squares problem.
Algoritma Recursive Least Squares (RLS) merupakan pendekatan daring (online approach) terhadap masalah least squares.
Γ iΓ i − 1 − Γ i − 1 x i x i T Γ i − 1 1 + x i T Γ i − 1 x i\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}} w iw i − 1 − Γ i x i ( x i T w i − 1 − y i )w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)} The above iteration algorithm can be proved using induction on i .
Γ iΓ i − 1 − Γ i − 1 x i x i T Γ i − 1 1 + x i T Γ i − 1 x 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 } merupakan vektor masukan dari datapoint ke- i dan Γ i − 1 } merupakan matriks kovarian dari iterasi sebelumnya.
The proof also shows that Γ iΣ i − 1\Sigma _{i}^{-1}} .
Pembuktian tersebut juga menyatakan bahwa Γ iΣ i − 1\Sigma _{i}^{-1}} .
One can look at RLS also in the context of adaptive filters (see RLS).
Algoritma RLS juga dapat dinilai dalam konteks filter adaptif (lihat RLS).
The complexity for n steps of this algorithm is O ( n d 2 ) )} , which is an order of magnitude faster than the corresponding batch learning complexity.
Kompleksitas waktu untuk n langkah dari algoritma ini adalah O ( n d 2 ) )} , yang jauh lebih cepat daripada kompleksitas pemelajaran batch yang sesuai.
The storage requirements at every step i here are to store the matrix Γ i } , which is constant at O ( d 2 ) )} .
Di setiap langkah i , perlu menyimpan matriks Γ i } , keperluan penyimpanan ini konstan pada O ( d 2 ) )} .
For the case when Σ i } is not invertible, consider the regularised version of the problem loss function ∑ j1 n ( x j T w − y j ) 2 + λ ‖ w ‖ 2 2 ^{n}\left(x_{j}^{\mathsf {T}}w-y_{j}\right)^{2}+\lambda \left\|w\right\|_{2}^{2}} .
Untuk kasus ketika matriks kovarian Σ i } tidak bisa diinvers, algoritma dapat disesuaikan dengan menggunakan versi teregulasi dari fungsi kerugian ∑ j1 n ( x j T w − y j ) 2 + λ | | w | | 2 2 ^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}} .
Then, it's easy to show that the same algorithm works with Γ 0( I + λ I )
Kemudian, akan mudah menunjukkan algoritma yang sama dapat bekerja dengan Γ 0( I + λ I )
− 1(I+\lambda I)^{-1}} , and the iterations proceed to give Γ i( Σ i + λ I ) − 1(\Sigma _{i}+\lambda I)^{-1}} .
− 1(I+\lambda I)^{-1}} dan ketika iterasi berlangsung akan menghasilkan Γ i( Σ i + λ I )
w i − 1 − γ i ∇ V ( ⟨ w i − 1 , x i ⟩ , y i )w_{i-1}-\gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})} or Γ i ∈ R d × d \in \mathbb {R} ^{d\times d}} by γ i ∈ R \in \mathbb {R} } , this becomes the stochastic gradient descent algorithm.
Γ iΓ i − 1 − Γ i − 1 x i x i T Γ i − 1 1 + x i T Γ i − 1 x 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 } merupakan vektor masukan dari datapoint ke- i dan Γ i − 1 } merupakan matriks kovarian dari iterasi sebelumnya.
In this case, the complexity for n steps of this algorithm reduces to O ( n d ) .
Kompleksitas waktu untuk n langkah dari algoritma ini adalah O ( n d 2 ) )} , yang jauh lebih cepat daripada kompleksitas pemelajaran batch yang sesuai.
However, the stepsize γ i } needs to be chosen carefully to solve the expected risk minimization problem, as detailed above.
Meskipun begitu, besarnya langkah γ i } harus dipilih dengan hati-hati untuk menyelesaikan masalah minimasi risiko harapan, sebagaimana yang telah dijelaskan di atas.
By choosing a decaying step size γ i ≈ 1 i , \approx {\frac {1}{\sqrt {i}}},} one can prove the convergence of the average iterate w ¯ n1 n ∑ i1 n w i {\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}} .
Dengan memilih besar langkah peluruhan γ i ≈ 1 i , \approx {\frac {1}{\sqrt {i}}},} didapatkan pembuktian konvergensi dari iterasi rata-rata w ¯ n1 n ∑ i1 n w i }_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}} .
This setting is a special case of stochastic optimization, a well known problem in optimization.
Skema ini merupakan salah satu kasus khusus dari optimasi stokastik yang mana merupakan salah satu masalah optimasi terkenal.
In practice, one can perform multiple stochastic gradient passes (also called cycles or epochs) over the data.
Dalam praktiknya, seseorang dapat melakukan pemanggilan beberapa SGD (juga dinamakan sebagai siklus atau epoch) pada data.
The algorithm thus obtained is called incremental gradient method and corresponds to an iteration w iw i − 1 − γ i ∇ V ( ⟨ w i − 1 , x t i ⟩ , y t i )w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}
Algoritma yang kemudian didapatkan tersebut dinamakan sebagai incremental stochastic gradient descent dan mengikut pada iterasi w iw i − 1 − γ i ∇ V ( ⟨ w i − 1 , x t i ⟩ , y t i )w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}
The main difference with the stochastic gradient method is that here a sequence t i } is chosen to decide which training point is visited in the i -th step.
Perbedaan utama algoritma ini dengan SGD adalah pada algoritma ini terdapat sebuah sekuens t i } yang dipilih untuk memutuskan titik pelatihan mana yang akan dikunjungi pada langkah ke- i yang mana sekuens ini dapat bersifat stokastik atau deterministik.
Kernels can be used to extend the above algorithms to non-parametric models (or models where the parameters form an infinite dimensional space).
Kernel dapat digunakan untuk memperluas algoritma-algoritma di atas menjadi model non-parameter (atau model yang parameter-parameternya membentuk sebuah ruang dimensi tak terhingga).
It can be shown by an easy induction that if X i } is the data matrix and w i } is the output after i steps of the SGD algorithm, then, w iX i T c iX_{i}^{\mathsf {T}}c_{i}} where c i( ( c i ) 1 , ( c i ) 2 , . . .
Penerapan metode kernel pada square loss ditunjukkan dengan sebuah induksi sederhana yang jika X i } adalah matriks data dan w i } adalah keluaran setelah langkah i dari algoritma SGD, maka, w iX i T c iX_{i}^{T}c_{i}} dengan c i( ( c i ) 1 , ( c i ) 2 , . . . , ( c i )
i ) ∈ R i((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}} and the sequence c i } satisfies the recursion: c 000} ( c i )
i ) ∈ R i((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}} dan sekuens c i } memenuhi rekursi: c 000} ( c i )
, i − 1 )_{j}=(c_{i-1})_{j},j=1,2,...,i-1} and ( c i )
, i − 1 )_{j}=(c_{i-1})_{j},j=1,2,...,i-1} dan ( c i )
j ⟨ x j , x i ⟩ ) )_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}} Notice that here ⟨ x j , x i ⟩ ,x_{i}\rangle } is just the standard Kernel on R d ^{d}} , and the predictor is of the form f i ( x )
j ⟨ x j , x 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 ⟩ ,x_{i}\rangle } hanyalah kernel standar pada R d ^{d}} , dan prediktornya didapatkan dari bentuk f i ( x )
⟨ w i − 1 , x ⟩∑ j1 i − 1 ( c i − 1 ) j ⟨ x j , x ⟩ .
i ( x )∑ j1 i − 1 ( c i − 1 )
(x)=\langle w_{i-1},x\rangle\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle .}
⟨ w i − 1 , x ⟩∑ j1 i − 1 ( c i − 1 ) j ⟨ x j , x ⟩ (x)=\langle w_{i-1},x\rangle\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle } .
Now, if a general kernel K is introduced instead and let the predictor be f i ( x )
Misalkan, jika suatu kernel umum K diperkenalkan dan prediktornya adalah f
The total time complexity for the recursion when evaluating for the n -th datapoint is O ( n 2 d k ) dk)} , where k is the cost of evaluating the kernel on a single pair of points.
Total kompleksitas waktu untuk rekursi di atas ketika mengevaluasi titik data ke- n adalah O ( n 2 d k ) dk)} , dengan k adalah biaya yang diperlukan untuk mengevaluasi kernel dari sepasang titik.
Thus, the use of the kernel has allowed the movement from a finite dimensional parameter space w i ∈ R d \in \mathbb {R} ^{d}} to a possibly infinite dimensional feature represented by a kernel K by instead performing the recursion on the space of parameters c i ∈ R i \in \mathbb {R} ^{i}} , whose dimension is the same as the size of the training dataset.
Maka, dengan penggunaan kernel di atas menjadikan pergerakan dari suatu dimensi terbatas w i ∈ R d \in \mathbb {R} ^{d}} menjadi sebuah kemungkinan fitur dimensi tak terbatas yang direpresentasikan oleh sebuah kernel K dengan melakukan rekursi di ruang parameter c i ∈ R i \in \mathbb {R} ^{i}} , yang mana dimensi di sini memiliki besar yang sama dengan himpunan data pelatihan.
In general, this is a consequence of the representer theorem.
Secara umum, ini adalah suatu akibat dari representer theorem.
As an example, consider the case of online least squares linear regression.
Sebagai contoh, pertimbangkan kasus regresi linear least squares.
Here, the weight vectors come from the convex set SR d ^{d}} , and nature sends back the convex loss function v t ( w )
Di sini, vektor weight didapatkan dari himpunan konveks SR d ^{d}} , dan nature (alam) mengirimkan balik fungsi kerugian konveks v t ( w )( ⟨ w , x t ⟩ − y t ) 2 (w)=(\langle w,x_{t}\rangle -y_{t})^{2}} .
Note here that y t } is implicitly sent with v t } .
Perhatikan bahwa di sini y t } dikirim secara implisit dengan v t } .
Follow the leader (FTL)
Follow the regularised leader (FTRL)
This algorithm is called Follow the leader, and round t is simply given by: w ta r g m i n w ∈ S ⁡ ∑ i1 t − 1 v i ( w )\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)} This method can thus be looked as a greedy algorithm.
Algoritma ini disebut Follow the Leader, dan iterasi atau round t dihitung sebagai berikut: w ta r g m i n w ∈ S ⁡ ∑ i1 t − 1 v i ( w )\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 } yang meminimalkan total kerugian sepanjang iterasi sebelumnya.
However, similar bounds cannot be obtained for the FTL algorithm for other important families of models like online linear optimization.
Namun, batas serupa tidak dapat didapatkan oleh algoritma FTL pada keluarga model penting lainnya, seperti optimisasi linear online.
To do so, one modifies FTL by adding regularisation.
Untuk mencapai batasan tersebut, FTL perlu dimodifikasi dengan menambahkan regularisasi.
This is a natural modification of FTL that is used to stabilise the FTL solutions and obtain better regret bounds.
FTRL adalah modifikasi dari FTL yang dimaksudkan untuk menstabilkan solusi yang didapatkan dari FTL dan mendapatkan batas regret yang lebih baik.
A regularisation function R : S → R } is chosen and learning performed in round t as follows: w ta r g m i n w ∈ S ⁡ ∑ i1 t − 1 v i ( w ) + R ( w )\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}
Sebuah fungsi regularisasi R : S → R } dipilih dan pemelajaran dilakukan pada iterasi t sebagai berikut: w ta r g m i n w ∈ S ⁡ ∑
⟨ w , z t ⟩ (w)=\langle w,z_{t}\rangle } .
⟨ w , z t ⟩ (w)=\langle w,z_{t}\rangle } dan SR d ^{d}} .
Suppose the regularisation function R ( w )1 2 η ‖ w ‖ 2 2 {\textstyle R(w)={\frac {1}{2\eta }}\left\|w\right\|_{2}^{2}} is chosen for some positive number η .
Misal, fungsi regularisasi R ( w )1 2 η | | w | | 2 2 {2\eta }}||w||_{2}^{2}} dipilih untuk suatu bilangan positif η .
Then, one can show that the regret minimising iteration becomes w t + 1− η ∑ i1 t z iw t − η z t-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}} Note that this can be rewritten as w t + 1w t − η ∇ v t ( w t )w_{t}-\eta \nabla v_{t}(w_{t})} , which looks exactly like online gradient descent.
Maka, dapat ditunjukkan bahwa iterasi yang meminimalkan regret menjadi w t + 1− η ∑ i1 t z iw t − η z t-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}} Perhatikan bahwa ini dapat ditulis ulang sebagai w t + 1w t − η ∇ v t ( w t )w_{t}-\eta \nabla v_{t}(w_{t})} yang ini persis sama dengan SGD sebelumnya.
If S is instead some convex subspace of R d ^{d}} , S would need to be projected onto, leading to the modified update rule w t + 1Π S ( − η ∑ i1 t z i )
Jika S adalah sebuah subruang konveks dari R d ^{d}} , S harus diproyeksikan ke, yang akhirnya mengarah kepada modikasi aturan pembaruan w t + 1Π S ( − η ∑ i1 t z i )
It is also known as Nesterov's dual averaging algorithm.
Algoritma ini juga dikenal sebagai Nesterov's dual averaging algorithm.
In this scenario of linear loss functions and quadratic regularisation, the regret is bounded by O ( T ) })} , and thus the average regret goes to 0 as desired.
Dalam skenario fungsi kerugian linier (linear loss functions) dan regularisasi kuadratik (quadratic regularisation) ini, regret dibatasi oleh O ( T ) })} .
The above proved a regret bound for linear loss functions v t ( w )
Di atas telah dibuktikan sebuah batas regret untuk fungsi kerugian linear v t ( w )⟨ w , z t ⟩ (w)=\langle w,z_{t}\rangle } .
To generalise the algorithm to any convex loss function, the subgradient ∂ v t ( w t ) (w_{t})} of v t } is used as a linear approximation to v t } near w t } , leading to the online subgradient descent algorithm:
Maka untuk menggeneralisasi algoritma sehingga dapat berlaku untuk semua fungsi kerugian konveks, subgradien ∂ v t ( w t ) (w_{t})} dari v t } digunakan sebagai suatu aproksimasi linear terhadap v t } dekat w t } yang kemudian menagrah kepada algoritma OSD:
Initialise parameter η , w 100}
Inisialisasi parameter η , w 100} Untuk t1 , 2 , .
, T Predict using w t } , receive f t } from nature.
, T Lakukan prediksi menggunakan w t } , menerima f t } dari nature.
max { 0 , 1 − y t ( w ⋅ x t ) } (w)=\max\{0,1-y_{t}(w\cdot x_{t})\}} Quadratically regularised FTRL algorithms lead to lazily projected gradient algorithms as described above.
max { 0 , 1 − y t ( w ⋅ x t ) } (w)=\max\{0,1-y_{t}(w\cdot x_{t})\}} Algoritma FTRL yang teregularisi secara kuadratik menyebabkan algoritma gradien menjadi diproyeksikan secara "malas" seperti yang dijelaskan di atas.
The optimal regularization in hindsight can be derived for linear loss functions, this leads to the AdaGrad algorithm.
Regularisasi optimal nantinya dapat diturunkan untuk fungsi kerugian linier yang kemudian mengarah kepada algoritma AdaGrad.
For the Euclidean regularisation, one can show a regret bound of O ( T ) })} , which can be improved further to a O ( log ⁡ T ) for strongly convex and exp-concave loss functions.
Untuk regularisasi Euclidean, dapat ditunjukkan batas regret O ( T ) })} , yang dapat diperbaiki lebih lanjut menjadi O ( log ⁡ T ) untuk fungsi kerugian konveks dan exp-concave yang sangat kuat.
Continual learning means constantly improving the learned model by processing continuous streams of information.
Pemelajaran berkelanjutan atau continual learning berarti terus meningkatkan model yang dipelajari dengan cara memproses aliran informasi yang terus menerus berubah.
Continual learning capabilities are essential for software systems and autonomous agents interacting in an ever changing real world.
Kemampuan pembelajaran berkelanjutan sangat penting untuk sistem perangkat lunak dan agen otonom yang berinteraksi di dunia nyata yang terus berubah.
The paradigm of online learning has different interpretations depending on the choice of the learning model, each of which has distinct implications about the predictive quality of the sequence of functions f 1 , f 2 , … , f n ,f_{2},\ldots ,f_{n}} .
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 ,f_{2},\ldots ,f_{n}} .
The prototypical stochastic gradient descent algorithm is used for this discussion.
Algoritma prototipe stochastic gradient descent digunakan untuk diskusi ini.
As noted above, its recursion is given by w tw t − 1 − γ t ∇ V ( ⟨ w t − 1 , x t ⟩ , y t )w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}
Seperti yang telah disebutkan di atas, rekursinya diberikan oleh w tw t − 1 − γ t ∇ V ( ⟨ w t − 1 , x t ⟩ , y t )w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}
The first interpretation consider the stochastic gradient descent method as applied to the problem of minimizing the expected risk I
Interpretasi pertama mempertimbangkan metode stochastic gradient descent yang diterapkan pada masalah minimasi risiko harapan
[ w ] defined above.
[ w ] yang telah didefinisikan di atas.
from the distribution p ( x , y ) , the sequence of gradients of V ( ⋅ , ⋅ ) in the above iteration are an i.i.d. sample of stochastic estimates of the gradient of the expected risk I
dari distribusi p ( x , y ) , barisan gradien dari V ( ⋅ , ⋅ ) pada iterasi di atas merupakan contoh i.i.d.
The second interpretation applies to the case of a finite training set and considers the SGD algorithm as an instance of incremental gradient descent method.
Interpretasi kedua berlaku untuk kasus himpunan pelatihan yang terbatas dan menganggap algoritma SGD sebagai contoh dari metode incremental gradient descent.
In this case, one instead looks at the empirical risk:
Dalam kasus ini, kita akan melihat risiko empiris:
[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}
⟨ w i − 1 , x ⟩∑ j1 i − 1 ( c i − 1 ) j ⟨ x j , x ⟩ (x)=\langle w_{i-1},x\rangle\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle } .
It uses the hashing trick for bounding the size of the set of features independent of the amount of training data.
Ini menggunakan trik hashing untuk membatasi ukuran set fitur yang tidak bergantung pada jumlah data pelatihan.
scikit-learn: Provides out-of-core implementations of algorithms for Classification: Perceptron, SGD classifier, Naive bayes classifier.
Scikit-learn: menyediakan implementasi dari algoritma out-of-core Klasifikasi: Perceptron, SGD, Naive bayes.
Regression: SGD Regressor, Passive Aggressive regressor.
Regresi: SGD Regressor, Passive Aggressive regressor.
Feature extraction: Mini-batch dictionary learning, Incremental PCA.
Ekstraksi fitur: Mini-batch dictionary learning, Incremental PCA.
Learning paradigms Incremental learning Lazy learning Offline learning, the opposite model Reinforcement learning Multi-armed bandit Supervised learning General algorithms Online algorithm Online optimization Streaming algorithm Stochastic gradient descent Learning models Adaptive Resonance Theory Hierarchical temporal memory k-nearest neighbor algorithm Learning vector quantization Perceptron 6.883: Online Methods in Machine Learning: Theory and Applications.
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 6.883: Online Methods in Machine Learning: Theory and Applications.