Pemelajaran mesin daring

Artikel ini bukan mengenai daring dan luring.

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. 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\to Y$ dengan $X$ sebagai ruang masukan (input) dan $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)$ pada $X\times Y$. Namun dalam kenyataannya, pemelajar atau model tidak mengetahui true distribution $p(x,y)$ terhadap titik-titik data dan biasanya hanya mengakses himpunan pelatihan yang berisi titik-titik data $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$. Untuk mengukur seberapa baik prediksi model, digunakan fungsi kerugian $V:Y\times Y\to \mathbb {R}$, yang memberikan nilai dari selisih antara prediksi $f(x)$ dan nilai sebenarnya $y$. Ide utamanya adalah mengubah parameter dalam fungsi $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})$ diasumsikan diambil dari true distribution $p(x,y)$ dengan tujuan meminimalkan "risiko" harapan

$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 ${\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})$, prediktor terbaik saat ini $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}$ diperbolehkan bergantung pada $f_{t}$ dan semua titik data sebelumnya $(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 permasalahan di atas adalah dengan belajar menggunakan kelompok kecil (mini-batch) yang memproses sebuah kelompok kecil dari $b\geq 1$ titik-titik data dalam satu waktu. Strategi ini bisa dianggap sebagai pemelajaran daring semu (pseudo-online) untuk $b$ yang jauh lebih kecil dari total jumlah data pelatihan. Teknik ini biasanya digunakan dengan berulang-ulang melalui data pelatihan untuk mendapatkan versi out-of-core 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

Artikel utama: Linear least squares (matematika)

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 dalam pemelajaran terawasi terdapat fungsi linear $f$ yang akan dipelajari:

$f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}$

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

$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$ yang meminimalkan kerugian empiris:

$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}\in \mathbb {R}$.

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

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

$w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}$.

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

Pemelajaran daring dengan least squares rekursif

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

$\textstyle w_{0}=0\in \mathbb {R} ^{d}$ dan $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$

dengan $I$ adalah matriks identitas.

Pada setiap iterasi ke-$i$, algoritma akan menghitung $\Gamma _{i}$ dan $w_{i}$ dengan memperbarui solusi dari iterasi sebelumnya.

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

$\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}$ merupakan vektor masukan dari datapoint ke-$i$ dan $\Gamma _{i}-1$ merupakan matriks kovarian dari iterasi sebelumnya. Adapun untuk vektor bobot diperbarui $w_{i}$ dengan rumus

$w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

dengan $y_{i}$ adalah nilai target yang sesuai dengan datapoint ke-$i$.

Algoritma iterasi di atas dapat dibuktikan dengan menggunakan induksi pada $i$. Pembuktian tersebut juga menyatakan bahwa $\Gamma _{i}=\Sigma _{i}^{-1}$. Algoritma RLS juga dapat dipandang dalam konteks filter adaptif (lihat RLS).

Kompleksitas waktu untuk $n$ langkah dari algoritma ini adalah $O(nd^{2})$, yang jauh lebih cepat daripada Kompleksitas pemelajaran batch yang sesuai. Di setiap langkah $i$, perlu menyimpan matriks $\Gamma _{i}$, keperluan penyimpanan ini konstan pada $O(d^{2})$. Untuk kasus ketika matriks kovarian $\Sigma _{i}$ tidak bisa diinvers, algoritma dapat disesuaikan dengan menggunakan versi teregulasi dari fungsi kerugian $\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 $\Gamma _{0}=(I+\lambda I)^{-1}$ dan ketika iterasi berlangsung akan menghasilkan $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$.

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

Pranala luar

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