📚 PAC Learning & Apa Artinya "Bisa Dipelajari"

Kategori: ML Theory · Kedalaman: Advanced-intermediate · Tanggal: 13 Oktober 2026

🎯 Tujuan Belajar

Setelah sesi ini, kamu harus bisa: - Mendefinisikan apa itu PAC learnable dan memberi contoh kelas hipotesis yang PAC-learnable dan yang tidak. - Menjelaskan peran ε (accuracy), δ (confidence), dan sample complexity. - Menurunkan (atau setidaknya membaca) bound sample complexity untuk kelas hipotesis berhingga. - Membedakan realizable vs agnostic PAC, dan paham kenapa distinction ini sentral. - Menjelaskan peran capacity measures (VC-dim, Rademacher, growth function) dalam generalisasi.

🧠 Penjelasan Inti

Apa itu PAC?

PAC = Probably Approximately Correct — kerangka formal (Valiant, 1984) untuk menjawab pertanyaan: "Kapan sebuah konsep benar-benar bisa dipelajari dari data? Dan berapa banyak data yang dibutuhkan?"

Sebelum PAC, "belajar" adalah istilah kabur. Valiant menuntutnya jadi objek matematis.

Formula Definisi

Misal: - $\mathcal{X}$ = ruang input (input space) - $\mathcal{Y} = {0,1}$ = label (klasifikasi biner; generalisasi ke multi-kelas trivial) - $D$ = distribusi unknown atas $\mathcal{X} \times \mathcal{Y}$ - $\mathcal{H}$ = kelas hipotesis (himpunan fungsi $h: \mathcal{X} \to \mathcal{Y}$) - Error (true risk) hipotesis $h$: $L_D(h) = \Pr_{(x,y)\sim D}[h(x) \neq y]$

Definisi (PAC learnable, versi agnostic): $\mathcal{H}$ adalah PAC-learnable jika ada algoritma $A$ dan fungsi $m_{\mathcal{H}}(\varepsilon, \delta)$ sedemikian sehingga untuk setiap $\varepsilon \in (0,1)$, $\delta \in (0,1)$, setiap distribusi $D$ atas $\mathcal{X}\times\mathcal{Y}$, dan setiap $n \geq m(\varepsilon,\delta)$, sampel $S \sim D^n$ yang diberikan ke $A$ menghasilkan hipotesis $A(S) = h$ yang memenuhi:

$$\Pr_{S \sim D^n}\Big[ L_D(h) \leq \min_{h' \in \mathcal{H}} L_D(h') + \varepsilon \Big] \geq 1 - \delta$$

Baca: "dengan probabilitas ≥ 1−δ, error yang dicapai tidak lebih buruk dari hipotesis terbaik di $\mathcal{H}$ plus ε."

Untuk versi realizable (ada $h^ \in \mathcal{H}$ dengan $L_D(h^) = 0$), definisinya lebih kuat: $L_D(h) \leq \varepsilon$.

Kenapa ada ε dan δ?

Ini dua sumbu ketidakpastian yang berbeda:

Poin krusial: kombinasi "probably approximately correct" bukan kompromi malas. Ini pengakuan bahwa sampel acak selalu bisa buruk secara kebetulan. Tidak ada algoritma yang bisa menjamin error kecil untuk semua sampel — karena ada probabilitas positif (sekecil apapun) mendapat sampel yang menyesatkan. PAC bilang: "kalau cukup data, kemungkinan sampel menyesatkan bisa dibuat sangat kecil."

Agnostic vs Realizable

• Realizable: asumsi kuat — ada $h^ \in \mathcal{H}$ dengan $L_D(h^) = 0$.
• Agnostic: asumsi realistis — tidak ada jaminan $L_D^* = 0$. Target bound ke $\min_{h'} L_D(h')$.

Real-world ML hampir selalu agnostic (model selalu salah di suatu titik). Realizable berguna secara pedagogis dan sebagai kasus batas.

⚙️ Cara Kerjanya

Uniform Convergence — masalah inti

Kenyataan: kita tidak tahu $D$. Kita hanya bisa mengukur empirical error:

$$\hat{L}S(h) = \frac{1}{n}\sum[h(x_i) \neq y_i]$$}^{n} \mathbb{1

The learning task reduces to: pilih $h$ dengan empirical risk terendah (ERM). Pertanyaan: kapan empirical risk menyerupai true risk?

Jawaban: ketika uniform convergence bertahan — yaitu seluruh $\mathcal{H}$ punya $\hat{L}_S(h) \approx L_D(h)$, bukan cuma satu $h$.

Bound untuk kelas berhingga (finite $\mathcal{H}$)

Teorema (Uniform Convergence, finite $|\mathcal{H}|$): untuk $\delta \in (0,1)$, dengan probabilitas $\geq 1-\delta$, berlaku serentak untuk semua $h \in \mathcal{H}$:

$$\big| L_D(h) - \hat{L}_S(h) \big| \leq \sqrt{\frac{\ln|\mathcal{H}| + \ln(2/\delta)}{2n}}$$

Konsekuensi langsung (agnostic, ERM): $$L_D(\hat{h}) \leq \min_{h} L_D(h) + 2\sqrt{\frac{\ln|\mathcal{H}| + \ln(2/\delta)}{2n}}$$

Sample complexity (agnostic, finite): $$n \geq \frac{2}{\varepsilon^2}\Big( \ln|\mathcal{H}| + \ln\tfrac{2}{\delta} \Big)$$

Sample complexity (realizable, finite): $$n \geq \frac{1}{\varepsilon}\Big( \ln|\mathcal{H}| + \ln\tfrac{1}{\delta} \Big)$$

Perhatikan perbedaan ketergantungan $\varepsilon$: realizable butuh $\Theta(1/\varepsilon)$, agnostic butuh $\Theta(1/\varepsilon^2)$. Realizable jauh lebih hemat karena setiap error langsung "tampak" dan memberi sinyal eliminasi hipotesis.

Intuisi proof (realizable, finite)

Bukti erat dengan double sampling + union bound: 1. Ambil sampel latih $S$ dan sampel uji fresh $S'$ (hanya untuk analisis, tidak dipakai praktik). 2. Tentukan "hipotesis buruk" $\mathcal{H}B = {h : L_D(h) > \varepsilon}$. 3. Peluang satu hipotesis buruk punya $\hat{L}$. 4. Union bound atas $\mathcal{H}}(h) = 0$ adalah $(1-\varepsilon)^n \leq e^{-n\varepsilonB$: $\Pr[\exists h \in \mathcal{H}_B : \hat{L}$. 5. Karena $S$ menemukan $h$ dengan $\hat{L}_S(h)=0$ dan uniform convergence di $S'$, maka $h$ tak bisa buruk → kontradiksi terkendali jika $|\mathcal{H}| e^{-n\varepsilon} \leq \delta$. 6. Selesaikan untuk $n$: $n \geq \frac{1}{\varepsilon}(\ln|\mathcal{H}| + \ln(1/\delta))$. ✔}(h)=0] \leq |\mathcal{H}| e^{-n\varepsilon

Untuk $\mathcal{H}$ tak berhingga

$|\mathcal{H}|$ bisa tak berhingga (misal: setengah-bidang linier di $\mathbb{R}^2$). Ganti $|\mathcal{H}|$ dengan kapasitas:

• Growth function $\Pi_{\mathcal{H}}(n)$: jumlah dichotomies berbeda yang bisa dihasilkan $\mathcal{H}$ pada $n$ titik.
• VC-dimension (Vapnik–Chervonenkis): jumlah titik maksimum yang bisa shattered oleh $\mathcal{H}$. Untuk $n > d_{VC}$, growth function tumbuh polinomial ($O(n^{d_{VC}})$, Sauer–Shelah).
• Rademacher complexity: mengukur seberapa baik $\mathcal{H}$ bisa fit noise acak.

Bound uniform convergence dengan VC-dim: $$L_D(h) \leq \hat{L}S(h) + O!\left( \sqrt{\frac{d \right)$$} \ln(n/d_{VC}) + \ln(1/\delta)}{n}

Fundamental Theorem of Statistical Learning menyatukan semuanya: untuk binary classification, empat pernyataan berikut ekuivalen: 1. $\mathcal{H}$ PAC-learnable. 2. $\mathcal{H}$ punya uniform convergence property. 3. $\mathcal{H}$ punya VC-dim finite. 4. ERM berhasil untuk $\mathcal{H}$.

Ini hasil yang elegan — mengikat learnability, kapasitas, dan ERM dalam satu equivalensi.

No-Free-Lunch

Teorema: untuk setiap algoritma $A$, ada distribusi $D$ di mana $A$ gagal (error ≈ 1/2). Implikasi: tidak ada learner universal. PAC tidak melanggar ini — PAC membuat asumsi distribusi dengan restrict ke kelas hipotesis $\mathcal{H}$. Andaikan $\mathcal{H}$ berstruktur (punya $d_{VC}$ kecil), kita bisa mengeksploitasi struktur itu. Kalau $\mathcal{H}$ = semua fungsi dari $\mathcal{X} \to {0,1}$ ($d_{VC} = \infty$), tidak ada yang bisa dipelajari.

💡 Contoh / Analogi

Contoh konkret: interval di $\mathbb{R}$

$\mathcal{H} = {$ semua interval $[a,b]$ $}$ untuk mengklasifikasi poin; label 1 jika $x \in [a,b]$, else 0.

• VC-dim $\mathcal{H}$ = 2. Kenapa? Bisa shatter 2 titik (pilih interval yang menutup salah satu/keduanya/kosong), tapi tidak bisa shatter 3 titik titik: susunan 1-0-1 tidak mungkin (interval kontinu tidak bisa "lubang" di tengah).
• Sample complexity: $n = O(\frac{1}{\varepsilon}(2 \ln \frac{1}{\varepsilon} + \ln \frac{1}{\delta}))$.

Cek: mengapa label alternatif 1-0-1 mustahil? Analogi: menempatkan satu stretch selotip membungkus dua kotak terpisah dengan kotak kosong di antaranya — selotip kontinu tak bisa melompati lubang.

Analogi PAC

Bayangkan menaksir warna mayoritas kelereng dalam guci raksasa tanpa mengosongkan guci (D tak diketahui). Kamu ambil $n$ kelereng secara acak. - Realizable: kamu yakin guci murni merah & biru, aturan pasti bisa disimpulkan → sedikit sampel cukup. - Agnostic: guci bisa punya campuran aneh; estimator predikat terbaik pun bisa salah. Butuh lebih banyak sampel ($1/\varepsilon^2$ vs $1/\varepsilon$). - δ: jaminan menempel pada "dengan probabilitas tinggi" — kadang sampel randammu sial, semua kelereng kebetulan satu warna. δ mengukur risiko malang itu.

⚠️ Miskonsepsi Umum

1. "PAC guarantee berarti model saya pasti bagus." Tidak. Jaminan berlaku pada distribution yang sama dan kelas hipotesis $\mathcal{H}$ yang didefinisikan. Kalau test distribution shift (misal covariate shift, concept drift), bound tidak berlaku. PAC adalah distribution-specific, bukan jaminan universal.

2. "ε dan δ sama-sama error." Tidak. ε adalah parameter akurasi (deterministik), δ adalah parameter kepercayaan (probabilistik). Confounding kedua hal ini bikin bound tidak terbaca.

3. "Semua bound PAC praktis." Tidak. Bound klasik notoriously loose; misal VC-dim neural net dengan jutaan parameter memberi angka $n$ yang absurd. Inilah kenapa praktisi sering pakai bound algorithmic stability, PAC-Bayes, atau margin-based modern.

4. "Realizable dan agnostic cuma beda notasi." Tidak — beda sample complexity order. Realizable $\Theta(1/\varepsilon)$; agnostic $\Theta(1/\varepsilon^2)$. Beda kelas kompleksitas.

5. "$\mathcal{H}$ besar selalu buruk." Tidak otomatis. Yang penting bukan $|\mathcal{H}|$ tapi kapasitas efektif (VC-dim, Rademacher, norm). Sering kali $\mathcal{H}$ besar tapi VC-dim kecil (misal: linier separator di dimensi tinggi bisa punya $d_{VC} = d+1$).

6. "Union bound itu tight." Sering tidak; union bound mengabaikan overlap antara "bad events". Ini salah satu sumber looseness bound klasik.

⚖️ Trade-off / Limitasi

Limitasi fundamental: - i.i.d. assumption: bound berangkat dari sampel i.i.d. Realitas ML sering sequential/correlated (time series, RL). - Distribution fixed: tidak menjawab transfer learning atau out-of-distribution secara langsung. - Worst-case over $\mathcal{H}$: mengabaikan struktur algoritma; dua learner dengan $\mathcal{H}$ sama tapi inductive bias beda akan punya performa beda, tapi bound yang ada sering sama. - Computational hardness: PAC-learnable information-theoretically ≠ efficiently learnable (computational PAC: kriptografi-based lower bounds). - Looseness untuk deep learning: teori klasik tidak menjelaskan kenapa net overparameterized generalize baik — inilah kenapa ada double descent dan implicit regularization sebagai fenomena belakangan.

Yang belum tuntas: teori generalisasi untuk deep learning masih aktif diperdebatkan (heavy-tail, interpolation regimes). Bound klasik tidak menjelaskan double descent.

🛠️ Latihan Praktis

Latihan 1 — Turunkan sample complexity. Mulai dari union bound $\Pr[\exists h \in \mathcal{H}B: \hat L) \rceil$ (untuk realizable).}(h)=0] \leq |\mathcal{H}|e^{-n\varepsilon}$, selesaikan untuk $n$ yang menjamin probabilitas $\leq \delta$. Bandingkan dengan bentuk realizable di atas. Kunci: $n = \lceil \frac{1}{\varepsilon}(\ln|\mathcal{H}| + \ln\frac{1}{\delta

Latihan 2 — Hitung VC-dim. Buktikan VC-dim untuk: - Setengah-bidang (halfspace) linier di $\mathbb{R}^d$ = $d+1$. - Interval di $\mathbb{R}$ = 2. - Lingkaran (disk) di $\mathbb{R}^2$ = 3.

Latihan 3 — Empirik. Bangun kelas hipotesis berhingga (misal $|\mathcal{H}| = 100$), generate data dari $D$ sederhana, jalankan ERM untuk sampel $n = 10, 50, 200, 1000$; plot empirical vs true risk rata-rata. Amati gap mengecil mengikuti $O(\sqrt{\ln|\mathcal{H}|/n})$. Verifikasi bahwa gap empirically ≤ bound teoretis.

✅ Cek Pemahaman

1. Kenapa sample complexity realizable adalah $\Theta(1/\varepsilon)$ sementara agnostic $\Theta(1/\varepsilon^2)$? Sinyal apa yang membuat realizable lebih efisien?

2. VC-dim $d_{VC} = \infty$ untuk kelas $\mathcal{H}$ = semua fungsi boolean dari $\mathbb{R} \to {0,1}$. Mengapa ini berkonsekuensi langsung bahwa $\mathcal{H}$ tidak PAC-learnable? Kaitkan dengan No-Free-Lunch.

3. Sebuah bound bilang: $n = 10^6$ untuk $\varepsilon = 0.01$, $\delta = 0.05$. Dalam praktik kamu hanya punya $n = 10^4$. Sebutkan tiga cara berbeda untuk mendapatkan jaminan teoretis di regime $n$ kecil ini (petunjuk: lebih ketat tentang $\mathcal{H}$, lebih ketat tentang data, atau bound alternatif).

🔑 Poin Kunci

• PAC = probably approximately correct: jawab "bisakah dipelajari" dengan ε (accuracy) dan δ (confidence) sebagai dua sumbu ketidakpastian yang berbeda.
• Uniform convergence adalah inti formal: seluruh $\mathcal{H}$ harus punya empirical risk ≈ true risk serentak, bukan cuma hipotesis terpilih.
• Kapasitas (dari $|\mathcal{H}|$ → VC-dim → Rademacher/PAC-Bayes) menggantikan "jumlah hipotesis" untuk kelas tak berhingga.
• Realizable vs agnostic bukan kosmetik: beda order sample complexity ($1/\varepsilon$ vs $1/\varepsilon^2$).
• Fundamental Theorem: PAC-learnable ⟺ uniform convergence ⟺ $d_{VC}$ finite ⟺ ERM works. Empat wajah satu fakta.
• No-Free-Lunch lebih dulu: PAC tidak melawan NFL; ia mengeksploitasi struktur $\mathcal{H}$.
• Bound klasik loose untuk deep learning; teori generalisasi modern (PAC-Bayes, stability, Rademacher data-dependent) hadir untuk itu.

➡️ Eksplorasi Lanjut

Rademacher Complexity & Data-Dependent Generalization Bounds — langkah logis berikutnya. VC-dim memperlakukan $\mathcal{H}$ secara statis; Rademacher complexity mengukur kapasitas relatif terhadap distribusi data aktual (lewat korelasi maksimum $\mathcal{H}$ dengan noise acak). Ini jembatan menuju bound yang lebih tight dan analisis deep learning modern — sekaligus pintu masuk ke margin-based generalization dan PAC-Bayes.