un

guest
1 / ?
back to lessons

Batas Keputusan sebagai Hiperpola

Klasifier biner mengasignasi setiap input ke salah satu dari dua kelas. Batas keputusan klasifier membagi ruang input menjadi dua region: satu per kelas. Geometri batas tersebut menentukan pola apa yang dapat dipelajari klasifier.

Hiperpola dalam ℝ^n: set semua titik x yang memenuhi w·x + b = 0, di mana w adalah vektor berat dalam ℝ^n dan b adalah skalar bias. Hiperpola memiliki n−1 dimensi.

Dalam 2D: hiperpola adalah garis. Dalam 3D: bidang datar. Dalam n-D: bidang datar (n−1)-dimensi.

Perceptron mengklasifikasikan dengan menghitung w·x + b dan kembali ke kelas 1 jika positif, kelas 0 jika negatif. Batas keputusannya adalah hiperpola.

Separabilitas Linier

Dataset disebut linearly separable dalam ℝ^n jika ada hiperpola yang memisahkan semua titik kelas-0 di satu sisi dan semua titik kelas-1 di sisi lain. Ini adalah sifat geometrik yang murni dari dataset tersebut.

Geometri Batas Keputusan: Separabilitas Linier & XOR

Menguji Separabilitas Linier

Dataset AND gate dalam 2D: titik kelas-0 di (0,0), (1,0), (0,1); titik kelas-1 di (1,1). Dataset ini linearly separable.

Dataset XOR dalam 2D: titik kelas-0 di (0,0) dan (1,1); titik kelas-1 di (1,0) dan (0,1). Kedua kelas ini terletak di diagonal yang saling berlawanan.

Verifikasi bahwa dataset XOR tidak linearly separable dalam 2D. Gunakan argumen geometrik: jelaskan mengapa tidak ada garis dalam bidang 2D yang dapat memisahkan dua kelas. Argumen Anda harus merujuk pada posisi empat titik dan properti garis lurus yang membuat pemisahan tidak mungkin.

Menaikkan ke Ruang Dimensi Lebih Tinggi

XOR tidak dapat dipisahkan secara linear di 2D. Solusinya: map data ke ruang dimensi lebih tinggi di mana menjadi linearly separable. Ini adalah ide inti dari kernel trick.

Feature map: fungsi φ: ℝ^n → ℝ^m (m > n) yang mengubah setiap titik input menjadi representasi dimensi lebih tinggi.

Untuk XOR, feature map yang berguna: φ(x₁, x₂) = (x₁, x₂, x₁x₂)

Ini menambah dimensi ketiga z = x₁ × x₂. Titik XOR transformasi ke:

- (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

Di 3D: titik kelas-0 berada di (0,0,0) dan (1,1,1); titik kelas-1 berada di (1,0,0) dan (0,1,0). Sekarang cari bidang pemisah.

Bidang Pemisah di 3D

Setelah feature map φ(x₁, x₂) = (x₁, x₂, x₁x₂), data XOR hidup di 3D. Hiperbola di 3D memiliki persamaan w₁x₁ + w₂x₂ + w₃z + b = 0.

Temukan hiperbola w·x + b = 0 di ruang 3D yang diubah yang benar-benar memisahkan kelas XOR. Verifikasi hiperbola Anda dengan menggantikan semua empat titik yang diubah. Setiap titik kelas-0 harus memberikan w·x + b < 0 (atau > 0) dan setiap titik kelas-1 harus memberikan tanda sebaliknya.

Teorema Cover: Mengapa Dimensi Tinggi Bantu

Teorema Cover (1965): masalah klasifikasi kompleks yang dilemparkan ke ruang berdimensi tinggi lebih mungkin dapat dipisahkan linier daripada di ruang berdimensi rendah, asalkan ruang tidak padat penduduk.

Pernyataan sederhana: jika Anda mampatkan n titik ke ruang berdimensi d >> n, kemungkinan label acak dapat dipisahkan linier mendekati 1.

Versi formal: untuk n titik dalam posisi umum dalam ℝ^d, jumlah dichotomi pemisahan linier (penetapan kelas) adalah tepat 2 × Σ_{k=0}^{d} C(n−1, k) untuk d < n, dan sama dengan 2^n (semua dichotomi) untuk d ≥ n − 1.

Implikasi praktis: peta fitur φ yang mengangkat XOR ke 3D adalah kasus khusus dari prinsip umum ini. Mengangkat ke ruang berdimensi lebih tinggi meningkatkan kemungkinan ketelitian. Harga: lebih banyak parameter untuk disesuaikan, risiko overfitting yang lebih tinggi.

Bias-Variance Tradeoff sebagai Geometri

Batas keputusan berdimensi rendah (sedikit parameter): bias tinggi (tidak dapat menangkap pola kompleks), varian rendah (stabil di antara sampel). Batas berdimensi tinggi (banyak parameter): bias rendah, varian tinggi (dapat overfit ke kebisingan di data pelatihan).

VC Dimension: Berapa Sebuah Klasifier Lebih Ekspresif?

Dimensi Vapnik-Chervonenkis (VC) dari kelas hipotesis H mengukur seberapa kompleks kelas tersebut: angka terbesar dari titik yang dapat dihancurkan (dapat diklasifikasikan dengan benar dalam semua label 2^n yang mungkin).

Perceptron di ℝ^d: Dimensi VC = d + 1. Sebuah hiperpola d-dimensional dapat menghancurkan d + 1 titik (dalam posisi umum) tetapi tidak d + 2.

Dimensi VC menentukan kompleksitas sampel: untuk belajar hipotesis dengan kesalahan umum ε dengan probabilitas 1 − δ, Anda membutuhkan sekitar n ≥ (d × log(1/ε) + log(1/δ)) / ε sampel, di mana d adalah dimensi VC.

Seorang perceptron di ℝ^3 memiliki VC dimension 4. Menurut batas kompleksitas sampel VC, sekitar berapa banyak sampel pelatihan yang diperlukan untuk mencapai kesalahan umum ε = 0,05 dengan keyakinan 1 − δ = 0,95? Gunakan batas sederhana n ≥ (d × log(1/ε) + log(1/δ)) / ε dengan nilai yang diberikan. Tunjukkan semua perhitungan.

Batas Keputusan & Batas Mesin Kemampuan

Geometri batas keputusan langsung terhubung dengan batas alasan mesin Hamming.

Perceptron lapis tunggal (klasifikasi hiperpola) tidak dapat menyelesaikan XOR. Kritik Minsky & Papert terhadap perceptrons awal tahun 1969 adalah demikian. Argumen geometris: XOR tidak dapat dipisahkan secara linier. Mesin tidak dapat menyelesaikannya, bukan karena kekurangan daya komputasi, tetapi karena ketidakselarasannya geometris yang fundamental antara kelas hipotesis dan masalah.

Solusi: jaringan lapis beberapa dapat merepresentasikan batas non-linier. Laluan tersembunyi mengimplementasikan peta fitur φ - mengangkat data ke dimensi yang lebih tinggi di mana pemisahan linier menjadi mungkin. Setiap saraf tersembunyi menghitung satu hiperpola; kombinasi dari beberapa hiperpola mendekati kurva.

Sejarah ini mencerminkan pengamatan Hamming: setiap batasan rasional mesin memiliki struktur geometris di bawahnya. Tugas bukanlah untuk berargumen tentang apakah mesin 'bisa berpikir' tetapi untuk mengidentifikasi batasan geometris dan menemukan cara untuk mengatasi mereka.

Kritik Minsky & Papert tahun 1969 terhadap perceptron menggunakan argumen tidak dapat dipisahkan XOR. Buku mereka, 'Perceptrons', hampir membunuh penelitian jaringan saraf selama satu dekade. Tetapi jaringan lapisan ganda mengatasi masalah XOR. Apa yang sejarah ini sarankan tentang cara yang benar untuk memahami batasan yang ditunjukkan mesin sistem berpikir? Khususnya: apakah batasan geometris yang ditunjukkan harus dianggap sebagai permanen atau sebagai kontingen pada kelas hipotesis saat ini? Berikan jawaban yang berprinsip.