Teorema Tanpa Makan Siang dan konsistensi K-NN

Dalam pembelajaran komputasi, teorema NFL menyatakan bahwa tidak ada pelajar universal. Untuk setiap algoritma pembelajaran, ada distribusi yang menyebabkan pelajar mengeluarkan hipotesis dengan kesalahan besar, dengan probabilitas tinggi (meskipun ada hipotesis kesalahan rendah). Kesimpulannya adalah bahwa untuk belajar, kelas hipotesis atau distribusi harus dibatasi. Dalam buku mereka "Sebuah teori probabilistik pengenalan pola", Devroye et al membuktikan theroem berikut untuk pelajar tetangga K-terdekat: Di mana

Assume μ has a density. if k \to \infty and k / n \to 0 then for every ϵ > 0, there's N, s.t. for all n > N : P (R_{n} - R^{*} > ϵ) < 2 e x p (- C_{d} n ϵ^{2})

$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \\ \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.} \text{ for all } n>N : \\ P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2})$

R^{*}

$R^*$

adalah kesalahan dari aturan -optimal, adalah kesalahan sebenarnya dari output K-NN (probabilitasnya melebihi set pelatihan ukuran ), adalah ukuran probabilitas pada ruang contoh dan adalah beberapa konstanta hanya bergantung pada dimensi euclidean. Oleh karena itu, kita bisa sedekat yang kita inginkan dengan hipotesis terbaik yang ada (bukan yang terbaik di beberapa kelas terbatas), tanpa membuat asumsi tentang pembagian. Jadi saya mencoba memahami bagaimana hasil ini tidak bertentangan dengan theroem NFL? Terima kasih!

R_{n}

$R_n$

n

$n$

μ

$\mu$

R^{d}

$\mathbb{R}^d$

C_{d}

$C_d$

k-nearest-neighbour consistency michael J
sumber

Jawaban:

Cara saya memahami teorema NFL adalah bahwa tidak ada algoritma pembelajaran yang lebih baik daripada yang lain dalam setiap tugas. Namun ini bukan teorema dalam pengertian matematika yang jelas bahwa ia memiliki bukti, melainkan pengamatan empiris.

Mirip dengan apa yang Anda katakan untuk kNN, ada juga Universal Approximation Theorem untuk Neural Networks, yang menyatakan bahwa dengan diberi jaringan neural 2-layer, kita dapat memperkirakan fungsi apa pun dengan kesalahan sewenang-wenang.

Sekarang, bagaimana ini tidak merusak NFL? Ini pada dasarnya menyatakan bahwa Anda dapat memecahkan masalah yang mungkin terjadi dengan NN 2-layer sederhana. Alasannya adalah bahwa sementara, secara teoritis NNs dapat memperkirakan apa saja, dalam praktiknya sangat sulit untuk mengajar mereka memperkirakan apa pun. Itu sebabnya untuk beberapa tugas, algoritma lain lebih disukai.

Cara yang lebih praktis untuk menafsirkan NFL adalah sebagai berikut:

Tidak ada cara untuk menentukan a-priori algoritma mana yang akan melakukan yang terbaik untuk tugas yang diberikan.

Kauk
sumber

Terima kasih atas jawabannya, tetapi ada beberapa ketidakakuratan .. Pertama, teorema NFL memiliki bukti (misalnya, shalev-shwartz & ben-david, memahami pembelajaran mesin, bab 5). Untuk Teorema Approximation Universal - teorema ini berkaitan dengan expresivness, sedangkan teorema NFL berkaitan dengan generalisasi.

michael J