Apa artinya ketika kita mengatakan sebagian besar poin dalam hypercube berada di perbatasan?

Jika saya memiliki hypercube 50 dimensi. Dan saya mendefinisikan batasnya dengan atau mana adalah dimensi dari hypercube. Kemudian menghitung proporsi poin pada batas hypercube akan menjadi . Apa artinya? Apakah itu berarti bahwa sisa ruang kosong? Jika titik berada pada batas maka titik di dalam kubus tidak boleh terdistribusi secara seragam? $0<x_j<0.05$ $0.95<x_j<1$ $x_j$ $0.995$ $99\%$

machine-learning math Rohit Kumar Singh
sumber

Tidak, itu berarti pinggiran lebih luas, dan efeknya sepadan dengan dimensi. Ini agak berlawanan dengan intuisi. Fenomena ini memiliki konsekuensi pada distribusi jarak antara pasangan acak dari node yang menjadi relevan ketika Anda ingin mengelompokkan atau menghitung tetangga terdekat di ruang dimensi tinggi.

Emre

Hitung berapa proporsi poin pada segmen garis yang dekat dengan batasnya. Lalu menunjuk sebuah kotak. Lalu menunjuk sebuah kubus. Apa yang bisa Anda katakan tentang mereka?

user253751

Jawaban:

Berbicara tentang $99\%$ poin dalam hypercube ' agak menyesatkan karena hypercube mengandung banyak poin. Mari kita bicara tentang volume.

Volume hypercube adalah produk dengan panjang sisinya. Untuk unit hypercube 50 dimensi kita mendapatkan

Total volume = \underset{50 times}{\underset{⏟}{1 \times 1 \times \dots \times 1}} = 1^{50} = 1.

$\text{Total volume} = \underbrace{1 \times 1 \times \dots \times 1}_{50 \text{ times}} = 1^{50} = 1.$

Sekarang mari kita mengecualikan batas-batas hypercube dan melihat ' interior ' (saya menempatkan ini dalam tanda kutip karena interior istilah matematika memiliki arti yang sangat berbeda). Kami hanya menyimpan poin $x = (x_1, x_2, \dots, x_{50})$ yang memuaskan

0.05 < x_{1} < 0.95 and 0.05 < x_{2} < 0.95 and \dots and 0.05 < x_{50} < 0.95.

$0.05 < x_1 < 0.95 \,\text{ and }\, 0.05 < x_2 < 0.95 \,\text{ and }\, \dots \,\text{ and }\, 0.05 < x_{50} < 0.95.$ Berapa volume 'interior' ini? Nah, 'interior' sekali lagi hypercube, dan panjang setiap sisi adalah

0.9

$0.9$ (

= 0.95 - 0.05

$=0.95 - 0.05$ ... membantu membayangkan ini dalam dua dan tiga dimensi). Jadi volumenya adalah Volume

Interior volume = \underset{50 times}{\underset{⏟}{0.9 \times 0.9 \times \dots \times 0.9}} = {0.9}^{50} \approx 0.005.

$\text{Interior volume} = \underbrace{0.9 \times 0.9 \times \dots \times 0.9}_{50 \text{ times}} = 0.9^{50} \approx 0.005.$ Simpulkan bahwa volume 'batas' (didefinisikan sebagai unit hypercube tanpa 'interior ') adalah

1 - {0.9}^{50} \approx 0.995.

$1 - 0.9^{50} \approx 0.995.$

Ini menunjukkan bahwa $99.5\%$ dari volume hypercube 50-dimensi terkonsentrasi pada batasnya .

Tindak lanjut: ignatius mengajukan pertanyaan menarik tentang bagaimana ini terhubung dengan probabilitas. Berikut ini sebuah contoh.

Katakanlah Anda datang dengan model (pembelajaran mesin) yang memprediksi harga perumahan berdasarkan 50 parameter input. Semua 50 parameter input independen dan didistribusikan secara merata antara $0$ dan $1$ .

Katakanlah bahwa model Anda berfungsi dengan baik jika tidak ada parameter input yang ekstrem: Selama setiap parameter input tetap antara $0.05$ dan $0.95$ , model Anda memprediksi harga perumahan hampir sempurna. Tetapi jika satu atau lebih parameter input ekstrem (lebih kecil dari $0.05$ atau lebih besar dari $0.95$ ), prediksi model Anda benar-benar mengerikan.

Setiap parameter input yang diberikan ekstrem dengan probabilitas hanya $10\%$ . Jadi jelas ini adalah model yang bagus, bukan? Tidak! Probabilitas bahwa setidaknya satu dari $50$ parameter ekstrem adalah $1 - 0.9^{50} \approx 0.995.$ Jadi dalam $99.5\%$ kasus, prediksi model Anda sangat buruk.

Rule of thumb: Dalam dimensi tinggi, pengamatan ekstrem adalah aturan dan bukan pengecualian.

Elias Strehle
sumber

Layak menggunakan kutipan OP "Apakah itu berarti bahwa sisa ruang kosong?" dan menjawab: Tidak, itu berarti sisa ruangan relatif kecil . . . Atau serupa dengan kata-kata Anda sendiri. . .

Neil Slater

Penjelasan yang sangat bagus dari istilah "kutukan dimensi"

ignatius

Bertanya-tanya apakah yang berikut ini benar: mengambil contoh ini, jika satu set fitur didistribusikan secara merata di sepanjang [0,1] di masing-masing dari 50 dimensi, (99,5% -0,5%) = 99% dari volume (fitur hypercube space) hanya menangkap nilai 10% dari setiap fitur

ignatius

"Setiap parameter input yang diberikan ekstrem dengan probabilitas hanya 5%." Saya pikir probabilitas ini adalah 10%.

Rodvi

@ Radvi: Tentu saja Anda benar, terima kasih! Memperbaikinya.

Elias Strehle

Anda dapat melihat polanya dengan jelas bahkan dalam dimensi yang lebih rendah.

Dimensi 1. Ambil garis panjang 10 dan batas 1. Panjang batas adalah 2 dan rasio interior 8: 1: 4.

Dimensi ke-2. Ambil kuadrat sisi 10, dan batas 1 lagi. Batas wilayahnya adalah 36, rasio interior 64, 9:16.

Dimensi ke-3. Panjang dan batas yang sama. Volume batas adalah 488, interior 512, 61:64 - batas sudah menempati ruang hampir sebanyak interior.

Dimensi ke-4, sekarang batasnya adalah 5904 dan interior 4096 - batasnya sekarang lebih besar.

Bahkan untuk panjang batas yang lebih kecil dan lebih kecil, karena dimensi meningkatkan volume batas akan selalu menyalip interior.

HP Williams
sumber

Cara terbaik untuk "memahaminya" (meskipun IMHO mustahil bagi manusia) adalah membandingkan volume bola n-dimensi dan kubus n-dimensi. Dengan pertumbuhan n (dimensionalitas) semua volume bola "bocor" dan berkonsentrasi di sudut-sudut kubus. Ini adalah prinsip umum yang berguna untuk diingat dalam teori pengkodean dan aplikasinya.

Penjelasan buku teks terbaik dari itu adalah dalam buku Richard W. Hamming "Coding and Information Theory" (3.6 Geometric Approach, p 44).

The artikel pendek di Wikipedia akan memberikan ringkasan singkat yang sama jika Anda perlu diingat bahwa volume unit kubus n-dimensi selalu 1 ^ n.

Saya harap ini akan membantu.

Alex Fedotov
sumber