Batas Keputusan sebagai Hyperplane
Pengklasifikasi biner menetapkan setiap input ke salah satu dari dua kelas. Batas keputusan pengklasifikasi membagi ruang input menjadi dua wilayah: satu untuk setiap kelas. Geometri batas tersebut menentukan pola apa yang dapat dipelajari pengklasifikasi.
Sebuah hyperplane dalam ℝ^n: himpunan semua titik x yang memenuhi w·x + b = 0, di mana w adalah vektor bobot dalam ℝ^n dan b adalah bias skalar. Hyperplane memiliki dimensi n−1.
Dalam 2D: hyperplane adalah garis. Dalam 3D: bidang datar. Dalam n-D: subruang datar berdimensi (n−1).
Sebuah perceptron mengklasifikasi dengan menghitung w·x + b dan mengembalikan kelas 1 jika positif, kelas 0 jika negatif. Batas keputusannya adalah hyperplane.
Separabilitas Linear
Dataset adalah separabel linear dalam ℝ^n jika ada hyperplane yang menempatkan semua titik kelas-0 di satu sisi dan semua titik kelas-1 di sisi lain. Ini adalah sifat geometri murni dari dataset.
Menguji Separabilitas Linear
Dataset gerbang AND dalam 2D: titik kelas-0 pada (0,0), (1,0), (0,1); titik kelas-1 pada (1,1). Dataset ini separabel linear.
Dataset XOR dalam 2D: titik kelas-0 pada (0,0) dan (1,1); titik kelas-1 pada (1,0) dan (0,1). Kedua kelas ini terletak pada diagonal yang berlawanan.
Mengangkat ke Dimensi Lebih Tinggi
XOR tidak separabel linear dalam 2D. Solusinya: petakan data ke ruang berdimensi lebih tinggi tempat data menjadi separabel linear. Ini adalah ide inti dari trik kernel.
Pemetaan fitur: fungsi φ: ℝ^n → ℝ^m (m > n) yang mentransformasi setiap titik input menjadi representasi berdimensi lebih tinggi.
Untuk XOR, satu pemetaan fitur yang berguna: φ(x₁, x₂) = (x₁, x₂, x₁x₂)
Ini menambahkan dimensi ketiga z = x₁ × x₂. Titik XOR bertransformasi menjadi:
- (0,0) → (0, 0, 0), kelas 0
- (1,0) → (1, 0, 0), kelas 1
- (0,1) → (0, 1, 0), kelas 1
- (1,1) → (1, 1, 1), kelas 0
Dalam 3D: titik kelas-0 berada pada (0,0,0) dan (1,1,1); titik kelas-1 berada pada (1,0,0) dan (0,1,0). Sekarang cari bidang pemisah.
Bidang Pemisah dalam 3D
Setelah pemetaan fitur φ(x₁, x₂) = (x₁, x₂, x₁x₂), data XOR berada dalam 3D. Hyperplane dalam 3D memiliki persamaan w₁x₁ + w₂x₂ + w₃z + b = 0.
Teorema Cover: Mengapa Dimensi Tinggi Membantu
Teorema Cover (1965): masalah klasifikasi kompleks yang dilemparkan dalam ruang berdimensi tinggi lebih mungkin untuk separabel linear daripada dalam ruang berdimensi rendah, asalkan ruang tidak padat dihuni.
Pernyataan informal: jika Anda memetakan n titik data ke ruang dengan dimensi d >> n, kemungkinan bahwa pelabelan acak separabel linear mendekati 1.
Versi formal: untuk n titik dalam posisi umum di ℝ^d, jumlah dikotomi separabel linear (penugasan kelas) adalah tepat 2 × Σ_{k=0}^{d} C(n−1, k) untuk d < n, dan sama dengan 2^n (semua dikotomi) untuk d ≥ n − 1.
Implikasi praktis: pemetaan fitur φ yang mengangkat XOR ke 3D adalah kasus khusus dari prinsip umum ini. Mengangkat ke dimensi lebih tinggi meningkatkan peluang separabilitas. Biayanya: lebih banyak parameter untuk dipasang, risiko overfitting lebih tinggi.
Tradeoff Bias-Variance sebagai Geometri
Batas keputusan berdimensi rendah (beberapa parameter): bias tinggi (tidak dapat menangkap pola kompleks), varians rendah (stabil di seluruh sampel). Batas berdimensi tinggi (banyak parameter): bias rendah, varians tinggi (dapat overfitting ke noise dalam data pelatihan).
Dimensi VC: Seberapa Ekspresif Pengklasifikasi?
Dimensi Vapnik-Chervonenkis (VC) dari kelas hipotesis H mengukur seberapa kompleks kelasnya: jumlah titik terbesar yang dapat H hancurkan (klasifikasi dengan benar dalam semua pelabelan 2^n yang mungkin).
Perceptron dalam ℝ^d: dimensi VC = d + 1. Hyperplane berdimensi d dapat menghancurkan d + 1 titik (dalam posisi umum) tetapi bukan d + 2.
Dimensi VC menentukan kompleksitas sampel: untuk mempelajari hipotesis dengan kesalahan generalisasi ε dengan probabilitas 1 − δ, Anda memerlukan kira-kira n ≥ (d × log(1/ε) + log(1/δ)) / ε sampel, di mana d adalah dimensi VC.
Batas Keputusan & Batas Kapabilitas Mesin
Geometri batas keputusan terhubung langsung dengan batas penalaran mesin Hamming.
Perceptron lapis tunggal (pengklasifikasi hyperplane) tidak dapat menyelesaikan XOR. Ini adalah kritik Minsky & Papert terhadap perceptron awal pada tahun 1969. Argumen geometri: XOR tidak separabel linear. Mesin tidak dapat menyelesaikannya, bukan karena kurangnya daya komputasi, tetapi karena ketidakcocokan geometri fundamental antara kelas hipotesis dan masalah.
Resolusinya: jaringan multi-lapis dapat mewakili batas non-linear. Lapisan tersembunyi mengimplementasikan pemetaan fitur φ — mengangkat data ke dimensi lebih tinggi di mana pemisahan linear menjadi mungkin. Setiap neuron tersembunyi menghitung satu hyperplane; kombinasi dari berbagai hyperplane menjabarkan kurva.
Sejarah ini memetakan pengamatan Hamming: setiap keterbatasan penalaran mesin memiliki struktur geometri di bawahnya. Tugasnya bukan untuk berdebat tentang apakah mesin 'dapat berpikir' tetapi untuk mengidentifikasi kendala geometri dan menemukan cara untuk mengatasinya.