Apa kutukan dimensi?

21

Secara khusus, saya sedang mencari referensi (makalah, buku) yang akan menunjukkan dan menjelaskan kutukan dimensi. Pertanyaan ini muncul setelah saya mulai membaca buku putih ini oleh Lafferty dan Wasserman. Dalam paragraf ketiga mereka menyebutkan persamaan "terkenal" yang menyiratkan bahwa tingkat konvergensi terbaik adalah ; kalau ada yang bisa menjelaskan itu (dan menjelaskannya), itu akan sangat membantu. $n^{-4/(4-d)}$

Juga, adakah yang bisa mengarahkan saya ke referensi yang menghasilkan persamaan "terkenal"?

theory khoda
sumber

7

Saya tidak bisa menjelaskan, tetapi saya yakin saya pernah mendengar apa yang terdengar seperti tiga versi kutukan yang berbeda: 1) dimensi yang lebih tinggi berarti jumlah pekerjaan yang meningkat secara eksponensial, dan 2) dalam dimensi yang lebih tinggi Anda akan mendapatkan lebih sedikit dan lebih sedikit contoh di bagian mana pun. ruang sampel Anda, dan 3) dalam dimensi tinggi semuanya cenderung pada dasarnya sama sehingga membuatnya sulit untuk membuat perbedaan.

Wayne

5

Anda bisa menafsirkan ini secara geometris. Katakanlah Anda memiliki bola dalam dimensi D dengan jari-jari r = 1. Anda kemudian dapat mengajukan pertanyaan tentang fraksi berapa volume bola yang terletak di antara jari-jari r = 1 dan r = 1-e. Karena kita tahu bahwa volume lingkup berskala seperti k (d) * r ^ (d), di mana d adalah jumlah dimensi, kita dapat memperoleh bahwa fraksi diberikan oleh 1- (1-e) ^ d. Dengan demikian, untuk bola dimensi tinggi sebagian besar volume terkonsentrasi dalam cangkang tipis di dekat permukaan. Lihat lebih lanjut tentang ini dalam buku Uskup "Pengenalan pola dan pembelajaran mesin".

Dr. Mike

@Wayne Sure; ditambah 5) lebih banyak redup biasanya berarti lebih banyak suara.

Mike, saya tidak mengikuti logika. Sepertinya Anda mengatakan bahwa "karena sebagian besar volume terkonsentrasi dalam cangkang tipis di dekat permukaan bola dimensi tinggi, maka Anda dikutuk dengan dimensi." Bisakah Anda menjelaskan lebih lanjut, dan mungkin secara eksplisit menunjukkan kepada saya bagaimana analogi ini terkait dengan statistik?

khoda

9

Menindaklanjuti richiemorrisroe, berikut adalah gambar yang relevan dari Elemen Pembelajaran Statistik , bab 2 (hal. 22-27):

ESL halaman 25

Seperti yang dapat Anda lihat di panel kanan atas, ada lebih banyak tetangga 1 unit dalam 1 dimensi daripada tetangga 1 unit dalam 2 dimensi. 3 dimensi akan lebih buruk!

Zach
sumber

7

Ini tidak menjawab pertanyaan Anda secara langsung, tetapi David Donoho memiliki artikel yang bagus tentang Analisis Data Dimensi Tinggi: Kutukan dan Berkat Dimensiitas (slide terkait ada di sini ), di mana ia menyebutkan tiga kutukan:

$D$ $(1/\epsilon)^D$ $\epsilon$
$d$ $(1/\epsilon)^D$ $\epsilon$
$D$ $(1/\epsilon)^D$ $\epsilon$

raegtin
sumber

6

Saya tahu bahwa saya terus merujuk padanya, tetapi ada penjelasan yang bagus tentang ini adalah Elemen Pembelajaran Statistik , bab 2 (hal 22-27). Mereka pada dasarnya mencatat bahwa dengan meningkatnya dimensi, jumlah data perlu meningkat (secara eksponensial) dengannya atau tidak akan ada cukup poin dalam ruang sampel yang lebih besar untuk analisis yang berguna untuk dilakukan.

Mereka menyebut sebuah makalah oleh Bellman (1961) sebagai sumber mereka, yang tampaknya merupakan bukunya Adaptive Control Processes, tersedia dari Amazon di sini

richiemorrisroe
sumber

+1. Penjelasan dalam ESL sangat bagus, dan diagram yang terkait banyak membantu.

Zach

2

masukkan deskripsi gambar di sini

Mungkin dampak yang paling terkenal ditangkap oleh batas berikut (yang (secara tidak langsung) diilustrasikan dalam gambar di atas):

lim_{d saya m \to \infty} \frac{d saya s t_{m Sebuah x} - d saya s t_{m saya n}}{d saya s t_{m saya n}}

$\lim_{dim\rightarrow\infty}\frac{dist_{max}-dist_{min}}{dist_{min}}$

$L_2$ $k$ $L_k$

Dampak Dimensi pada Data dalam Gambar

Raffael
sumber

Apa kutukan dimensi?

Jawaban: