Pengantar PAC Learning


Saat ini, Machine Learning is all about “belajar dari data”. Ketika sedang mendesain atau menganalisis algoritma learning, terkadang sering muncul pertanyaan-pertanyaan:

  • Berapa jumlah data/sampel yang dibutuhkan agar proses pembelajaran berhasil? (sample complexity)
  • Hal apakah yang dapat dipelajari secara efisien? problem apa yang sulit dipelajari? (time and space complexity)
  • Adakah algoritma learning yang dapat mempelajari semua hal? (general model of learning)

Untuk mengurangi proses trial-and-error dalam mendesain algoritma learning atau agar Machine Learning lebih dari sekadar seni, dibutuhkan sebuah framework formal yang mencoba menjawab pertanyaan-pertanyaan di atas. Salah satu framework yang dapat digunakan adalah Probably Approximately Correct (PAC) Learning.

1. Notasi

Sebelum mendefinisikan PAC Learning, saya akan memperkenalkan berbagai notasi dan istilah dasar. Asumsi pembaca sudah familiar dengan teori himpunan dan probabilitas.

  • {\mathcal{X}}: Ruang input / himpunan dari semua sampel yang mungkin.
  • {\mathcal{D}}: Distribusi (probabilitas).Jika terdapat sebuah sampel {x \in \mathcal{X}}, notasi {x \sim \mathcal{D}} berarti {x} diambil secara i.i.d. (independent and identically distributed) berdasarkan distribusi {\mathcal{D}}.
  • {\mathcal{Y}}: Ruang label.
  • {c:\mathcal{X} \rightarrow \mathcal{Y}}: concept , dimana {c \in \mathcal{C}} dan {\mathcal{C}} merupakan concept class.Concept merepresentasikan hubungan yang sebenarnya antara {\mathcal{X}} dan {\mathcal{Y}}, yang tidak diketahui. Inilah yang coba ditemukan oleh algoritma learning.
  • {h:\mathcal{X} \rightarrow \mathcal{Y}}: Hypothesis , dimana {h \in \mathcal{H}} dan {\mathcal{H}} merupakan hypothesis set.Walaupun tampak mirip, hypothesis merupakan hal yang berbeda dengan concept. Boleh jadi {\mathcal{H} \neq \mathcal{C}}. Hypothesis diketahui/dirancang sendiri oleh perancang algoritma.
  • {\mathcal{A}}: algoritma learning.

Tujuan dari proses learning adalah memilih hypothesis yang paling dekat dengan concept.

Untuk mempermudah memahami perbedaan antara hypothesis, concept dan learning algorithm, perhatikan contoh berikut.

=====================================================================

Universal Best Food Ingredients in The World

Dapatkah kamu menjawab pertanyaan bahan-bahan makanan apa sajakah yang dapat menghasilkan makanan yang SEMUA orang di dunia ini sepakat bahwa itu makanan terenak sedunia? Mungkin kita tidak pernah tahu jawabannya, namun kita percaya bahwa bahan-bahan makanan tersebut ada. Ini dapat dianalogikan sebagai concept. Untuk mencari estimasi jawaban dari pertanyaan tersebut, mungkin pertama-tama kita bisa mulai dengan melihat daftar ini. Ambil, katakanlah, 3 makanan pada ranking teratas: rendang, nasi goreng, dan sushi. Dari sini, mungkin kita bisa mengestimasi bahan-bahan dari makanan terenak di dunia universal terdiri dari {\mathcal{H}} = {“bawang”, “daging”, “ketumbar”,“nasi”,“ikan”, …}. Inilah salah satu contoh dari hypothesis.

Sekarang kita akan mencari tahu konfigurasi bahan yang seperti apakah yang menghasilkan makanan terenak di dunia (best hypothesis). Dari kumpulan bahan tersebut, buatlah semua makanan yang mungkin dihasilkan, termasuk rendang, nasi goreng, dan sushi. Kemudian mintalah seluruh orang di dunia ini untuk mencoba makanan-makanan tersebut dan untuk tiap-tiap jenis makanan, tanyakan “apakah ini makanan terenak yang pernah kamu coba?”. Setelah mendapatkan feedback, lihat makanan yang manakah yang paling banyak mendapatkan jawaban “Ya” dari pertanyaan tersebut. Bahan makanan dari makanan tersebutlah yang merupakan estimasi terbaik dari universal best food ingredients. Proses mencari best hypothesis ini dapat kita analogikan sebagai learning algorithm.

Apabila ada makanan yang tidak pernah mendapatkan jawaban “Tidak”, ini berarti hypothesis = concept. =====================================================================

2. Risk

Risk (a.k.a. error) merupakan besaran yang digunakan untuk mengukur seberapa jauh bedanya antara hypothesis dengan concept secara kuantitatif. Semakin kecil risk berarti semakin dekat suatu hypothesis dengan concept. Terdapat 2 jenis risk: 1) expected risk and 2) empirical risk yang didefinisikan sebagai berikut.

Definisi 1 (Risk): Diberikan sebuah hypothesis {h \in \mathcal{H}}, sebuah target concept {c \in \mathcal{C}}, dan distribusi probabilitas {\mathcal{D}}, expected risk dari {h}:

\displaystyle R(h) = \mathbb{E}_{x \sim \mathcal{D}}[1_{h(x) \neq c(x)}]\quad\quad\quad(1)

dimana {1_{E}} merupakan fungsi indikator dari kejadian {E}. Diberikan {m} buah sampel diambil dari distribusi {\mathcal{D}}, empirical risk dari {h}:

\displaystyle \hat{R}(h) = \frac{1}{m} \sum_{i=1}^{m}[1_{h(x_i) \neq c(x_i)}]\quad\quad\quad(2).

Perlu diketahui bahwa algoritma learning yang baik harus mampu menghasilkan hypothesis dengan expected risk R(h) minimum, bukan sekadar dengan empirical risk \hat{R}(h) minimum. Namun demikian, berhubung disribusi probabilitas \mathcal{D} tidak diketahui maka kita tidak pernah mampu menghitung R(h) secara langsung. Yang dapat dilakukan oleh algoritma learning adalah mencari hypothesis h dengan \hat{R}(h) minimum

\displaystyle \hat{h} := \min_{h} \hat{R}(h) \quad \quad \quad (3)

sembari berharap mendapatkan R(h) minimum.

 3. PAC Learning

Ide utama dari PAC Learning adalah bagaimana menentukan worst case scenario dari suatu hipotesis dalam bahasa probabilistik. Dengan kata lain, PAC Learning memberikan indikasi seberapa besar risk dari hipotesis yang dipilih suatu algoritma learning.

Berikut ini definisi formal dari PAC-learning.

Definisi 2 (PAC-learning): Sebuah concept class {\mathcal{C}} dapat dikatakan PAC-learnable jika terdapat sebuah algoritma {\mathcal{A}} sedemikian sehingga {\forall \varepsilon > 0, \forall \delta > 0} dan untuk setiap distribusi {\mathcal{D}} di {\mathcal{X}} dan {c \in \mathcal{C}}, pertidaksamaan di bawah ini terpenuhi:

{\displaystyle \mathbb{P}_{x \sim \mathcal{D}^m}[R(h_s) \leq \varepsilon] \geq 1 - \delta \quad\quad\quad(4)},

dimana

\displaystyle m \geq poly(1/\varepsilon, 1/\delta, n, size(c))\quad\quad\quad(5)

dan poly(\cdot, \cdot, \cdot, \cdot) merupakan fungsi polinomial.

Persamaan (5) biasa dikenal dengan istilah “sample complexity” , konstanta \varepsilon disebut sebagai “generalization bound”, dan konstanta 1-\delta disebut sebagai “confidence level”.

Algoritma A yang mampu menghasilkan hipotesis yang PAC-learnable disebut sebagai PAC-learning algorithm.

Perlu diperhatikan bahwa PAC learning mengharuskan persamaan (4) “dan” (5) terpenuhi. Apabila pertumbuhan m eksponensial diberikan suatu algoritma, maka algoritma tersebut bukan PAC learning algorithm.

Selanjutnya kita akan melihat contoh sederhana penggunaan dari Risk dan PAC-learning framework.

4. contoh kasus: mencari persegi panjang terkecil

Definisi masalah

Kita akan menganalisis contoh problem klasifikasi yang sangat sederhana diilustrasikan pada Gambar 1 dan 2 di bawah ini: mencari persegi panjang terkecil yang memisahkan titik biru (positif) dan titik merah (negatif) dengan risk/error sekecil-kecilnya. B merupakan persegi panjang yang merepresentasikan concept (tidak diketahui), dan B’ merepresentasikan hypothesis.

Titik-titk biru dan merah merepresentasikan sampel. Semua titik yang berada di dalam persegi panjang akan dikategorikan sebagai titik positif, dan sebaliknya.

Slide1
Gambar 1: Kondisi awal
Slide2
Setelah menjalankan algoritma learning yang konsisten

Gambar 1 mengilustrasikan kondisi awal dari hypothesis –B’  dibentuk, misalnya, secara random. Dari sudut pandang hypothesis B’, maka terdapat 5 buah titik positif dan 8 buah titik negatif. Jika kita bandingkan dengan concept B, maka terdapat 6 buah titik yang diklasifikasi secara salah oleh B’  (3 false positive, 3 false negative) !.

Andaikan terdapat sebuah algoritma learning \mathcal{A} dan \mathcal{A} mengetahui informasi dari sampel: titik koordinat dan label (‘biru’ atau ‘merah’). Tugas \mathcal{A} adalah mengubah-ubah lokasi dan ukuran dari hypothesis B’ sehingga mendapatkan hasil klasifikasi dengan kesalahan minimal. Jika algoritma \mathcal{A} konsisten, maka akan selalu menghasilkan kondisi pada Gambar 2 (B' = B_s).

Tujuan kita kali ini adalah untuk membuktikan apakah masalah ini PAC-learnable dan \mathcal{A} merupakan algoritma PAC-learning.

Error analysis

Perlu diperhatikan bahwa titik-titik yang tergambar pada Gambar 1 & 2 merupakan sampel yang “terlihat”, atau biasa disebut sebagai “data latih”. Atau jika kita kaitkan dengan risk, maka konfigurasi pada Gambar 2 secara matematis dapat dikatakan \hat{R}(B_s) = 0. Dikemudian hari, bisa jadi akan ada titik-titik biru yang muncul di area antara B dan  B_s, sehingga kita tidak bisa menjamin expected risk R(B_s) = 0. Ingat kembali bahwa tujuan kita mendapatkan expected risk minimum, bukan hanya empirical risk.

Pertanyaannya adalah seberapa “parah” expected risk R(B_s) yang dihasilkan oleh algoritma \mathcal{A}? Secara matematis, pertanyaan ini dapat dinyatakan sebagai berikut. Tetapkan nilai \varepsilon > 0 dan anggap R(B_s)>\varepsilon. Kita ingin mengetahui angka terbesar dari probabilitas berikut:

\displaystyle \mathbb{P}[R(B_s) > \varepsilon] \leq \quad ? \quad\quad\quad

Kita akan melihat bahwa PAC-learning dapat menjawab pertanyaan ini.

Pertama-tama, perhatikan bahwa untuk kasus pada Gambar 2, error hanya selalu terjadi di region antara B_s dan B. Apabila region tersebut dinyatakan sebagai nilai probabilitas, maka nilai tersebut lebih dari \varepsilon.

Selanjutnya, bagilah wilayah tersebut menjadi  4 bagian r_1, r_2, r_3 dan r_4 seperti gambar di bawah ini.

Gambar 3: Error regions
Gambar 3: Error regions

Dengan demikian, r_1 + r_2 + r_3 + r_4 < \varepsilon dan r_i < \frac{\varepsilon}{4}, \forall i=1,...,4.

GENERALIZATION bound & SAmple complexity

Selanjutnya kita memasuki bagian terpenting pada tulisan ini. Tujuan kita adalah untuk mengkuantifikasi seberapa besar nilai dari \varepsilon. Dari hasil error analysis sebelumnya, saya akan membuat klaim bahwa

Risk dari hypothesis B_s tidak melebihi nilai error \varepsilon, apabila persegi panjang B_s berpotongan dengan semua error region r_1, r_2, r_3, r_4.

Secara matematis, klaim di atas ekuivalen dengan pernyataan

\displaystyle \forall_{i=1,...,4}, B_s \cap r_i \neq \emptyset \implies R(B_s) \leq \varepsilon \quad\quad\quad (6)

Ambil kontraposisi dari pernyataan (6). Kita akan mendapatkan

R(B_s) > \varepsilon \implies \exists_{i=1,...,4}, B_s \cap r_i=\emptyset\quad \quad \quad(7).

Dengan kata lain, jika risk  ternyata melebihii error \varepsilon, maka pastilah ada, paling tidak, salah satu region yang tidak berpotongan dengan persegi panjang B_s. Alasan mengapa perlu membuat kontraposisi di atas adalah untuk mempermudah operasi dengan menggunakan probabilitas, karena pada akhirnya kita ingin mengetahui probabilitas dari kesalahan yang dibuat oleh hypothesis terpilih.

Kita dapat menginterpretasi ruas kiri dari pernyataan (7) dengan probabilitas \mathbb{P}[R(B_s) > \varepsilon], yang merupakan probabilitas dari sebuah sampel positif yang dianggap negatif oleh hypothesis B_s dengan minimum kesalahan sebesar \varepsilon.

Misalkan terdapat m buah sampel yang dapat diobservasi, dari pernyataan (7) kita dapat merumuskan pertidaksamaan di bawah ini

\displaystyle \mathbb{P}_{S \sim \mathcal{D}^m}[R(B_s)>\varepsilon]\leq\mathbb{P}_{S\sim\mathcal{D}^m}\left[\bigcup_{i=1}^4 B_s \cap r_i \neq \emptyset \right] \quad \quad \quad(8)

\displaystyle \leq \sum_{i=1}^{4}\mathbb{P}_{S \sim \mathcal{D}^m}[B_s \cap r_i \neq \emptyset]\quad\quad\quad(9)

\displaystyle \leq 4(1-\frac{\varepsilon}{4})^m\quad \quad \quad(10)

\displaystyle \leq 4 \exp( - \frac{m \varepsilon}{4})\quad\quad\quad(11)

Pertidaksamaan (9) didapatkan dari sifat gabungan/union –ingat kembali salah satu sifat yang diajarkan di sekolah menengah \mathbb{P}(A \cup B) = \mathbb{P}(A) + \mathbb{P}(B) - \mathbb{P}(A \cap B). Maka, aman untuk menyatakan \mathbb{P}(A \cup B) \geq \mathbb{P}(A) + \mathbb{P}(B). Beginilah kira-kira reasoning dari pernyataan (9).

Mungkin ada yang bertanya-tanya dari mana datangnya pernyataan (10): 4(1 - \frac{\varepsilon}{4})^m. Mari kita sama-sama pahami apa yang terjadi. Kita modifikasi sedikit Gambar 3 sehingga salah satu region berpotongan dengan persegi panjang B_s seperti yang ditunjukkan Gambar 4 (B_s \cap r_1 ditunjukkan oleh arsiran berwarna biru muda).

rect4
Gambar 4 Wilayah perpotongan antara r1 dan Bs

Seperti yang kita ketahui bahwa r_1 > \frac{\varepsilon}{4}. Dalam konteks probabilitas, luas seluruh wilayah persegi panjang B adalah 1. Dengan demikian, kita dapat dengan aman menyatakan nilai probabilitas dari sebuah sampel  yang memasuki area perpotongan: \mathbb{P} [B_s \cap r_1] \leq (1-\frac{\varepsilon}{4}). Jika terdapat m sampel independen, maka \mathbb{P}_{S \sim \mathcal{D}^m} [B_s \cap r_1] \leq (1-\frac{\varepsilon}{4})^m.

Pernyataan ini juga berlaku untuk area yang lainnya (r_2, r_3, r_4). Dengan demikian, jelaslah bahwa \sum_{i=1}^{4}\mathbb{P}_{S \sim \mathcal{D}^m}[B_s \cap r_i] \leq 4 (1 - \frac{\varepsilon}{4})^m.

Terakhir, pernyataan (11) didapatkan dari sifat (1 - x) \leq \exp(-x), \forall x \in \mathbb{R}

Problem terakhir kita adalah menentukan nilai \varepsilon dan m. Ingat kembali definisi dari PAC-learning yang ditunjukkan oleh pertidaksamaan (4). Saya akan membuat pernyataan yang ekuivalen dari pertidaksamaan (4) yaitu

\displaystyle \mathbb{P}_{S \sim \mathcal{D}^m}[R(B_s)>\varepsilon]<\delta \quad\quad\quad(12)

JIka kita kaitkan persamaan (11) dan (12), maka persamaan di bawah ini terpenuhi

\displaystyle \delta > 4\exp(-\frac{m \varepsilon}{4})

Dengan aljabar sederhana, kita dapat menentukan \varepsilon atau m (silakan dicek sendiri):

\displaystyle \varepsilon>\frac{4}{m}\log\frac{4}{\delta}\quad\quad\quad(13)

atau

\displaystyle m>\frac{4}{\varepsilon}\log\frac{4}{\delta}\quad\quad\quad(14)

Pertidaksamaan (13) disebut sebagai generalization bound dan (14) sebagai sample complexity.

Perhatikan bahwa bound (13) tidak lain menyatakan bahwa \mathbb{P}_{S \sim \mathcal{D}^m}[R(B_s) \leq \frac{4}{m} \log \frac{4}{\delta}] \geq 1-\delta, dan juga dapat dilihat bahwa sample complexity (14) bahkan lebih sederhana dari fungsi polynomial. Berdasarkan Definisi 2, kita dapat menyimpulkan bahwa concept B merupakan konsep yang PAC-learnable, dan algoritma untuk mendapatkan hypothesis B_s merupakan PAC-learning algorithm !

5. PENUTUP

Dengan PAC Learning, kita dapat menganalisis apakah suatu permasalahan learning dapat dipecahkan oleh algoritma tertentu tanpa harus berasumsi mengenai distribusi dari sampel. Contoh kasus yang dibahas di sini dapat dikatakan sebagai toy example yang mudah untuk melakukan error analysis, dengan memainkan sedikit trik geometri.

Tantangan sesungguhnya adalah menganalisis kasus yang lebih realistis daengan algoritma yang lebih kompleks, e.g., Support Vector Machines, Neural Networks. Dibutuhkan (math) tools khusus lebih dari sekadar definisi dan trik-trik geometri yang dibahas pada tulisan ini.

2 thoughts on “Pengantar PAC Learning

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s