Apakah kutukan Dimensi mempengaruhi beberapa model lebih dari yang lain?

15

Tempat saya telah membaca tentang kutukan dimensionalitas menjelaskannya dalam hubungannya dengan kNN terutama, dan model linier secara umum. Saya secara teratur melihat peringkat teratas di Kaggle menggunakan ribuan fitur pada dataset yang hampir tidak memiliki 100k titik data. Mereka terutama menggunakan pohon Boosted dan NN, antara lain. Banyak fitur yang tampak terlalu tinggi dan saya merasa mereka akan terpengaruh oleh kutukan dimensionalitas. Tapi itu tampaknya tidak menjadi masalah karena model ini membuat mereka menjadi yang teratas dalam kompetisi. Jadi, kembali ke pertanyaan awal saya - apakah beberapa model terpengaruh oleh kutukan dimensionalitas lebih dari yang lain?

Secara khusus, saya tertarik pada model-model berikut (hanya karena ini adalah yang saya sadari / gunakan):

  • Regresi Linier dan Logistik
  • Decision Trees / RandomForest / Boosted Trees
  • Jaringan Saraf Tiruan
  • SVM
  • KNN
  • k-berarti pengelompokan
Dileep Kumar Patchigolla
sumber
Jawaban singkatnya pasti ya, tapi mungkin Anda menginginkan model yang benar-benar Anda minati? Saya yakin komunitas CV dapat memberi tahu Anda tentang ribuan jenis model yang dipengaruhi oleh kutukan dimensi. Jadi, mempersempit fokus Anda ke jenis model tertentu dapat membantu menjawab pertanyaan ini.
@RustyStatistician - Saya telah menambahkan beberapa model yang saya minati.
Dileep Kumar Patchigolla
Saya cukup tertarik dengan pertanyaan ini tetapi tetap tidak terjawab. Bagaimana saya bisa membawa ini dalam visibilitas, untuk mendapatkan jawaban?
Dileep Kumar Patchigolla

Jawaban:

16

Secara umum, kutukan dimensi membuat masalah pencarian melalui ruang jauh lebih sulit, dan efek mayoritas algoritma yang "belajar" melalui partisi ruang vektor mereka. Semakin tinggi dimensi masalah optimisasi kami, semakin banyak data yang kami butuhkan untuk mengisi ruang yang kami optimalkan.

Model Linier Umum

β^=(XX)1Xy

Pohon Keputusan Pohon
keputusan juga menderita kutukan dimensi. Pohon keputusan secara langsung mempartisi ruang sampel di setiap node. Ketika ruang sampel meningkat, jarak antara titik data meningkat, yang membuatnya lebih sulit untuk menemukan pemisahan "baik".

Hutan Acak Hutan
Acak menggunakan kumpulan pohon keputusan untuk membuat prediksi mereka. Tetapi alih-alih menggunakan semua fitur dari masalah Anda, setiap pohon hanya menggunakan subset fitur. Ini meminimalkan ruang yang dioptimalkan oleh setiap pohon dan dapat membantu memerangi masalah kutukan dimensi.


Algoritma Boosted Tree's Boosting seperti AdaBoost menderita kutukan dimensi dan cenderung overfit jika regularisasi tidak digunakan. Saya tidak akan masuk secara mendalam, karena postingan Apakah AdaBoost lebih sedikit atau lebih cenderung overfitting? menjelaskan alasan mengapa lebih baik daripada yang saya bisa.

Jaringan Saraf Tiruan
Jaringan saraf aneh dalam arti keduanya dan tidak terpengaruh oleh kutukan dimensi tergantung pada arsitektur, aktivasi, kedalaman dll. Jadi untuk mengulangi kutukan dimensi adalah masalah bahwa sejumlah besar titik diperlukan dalam tinggi dimensi untuk menutupi ruang input. Salah satu cara untuk menafsirkan jaringan saraf yang dalam adalah dengan memikirkan semua lapisan yang mengharapkan lapisan terakhir sebagai melakukan proyeksi rumit manifold dimensi tinggi menjadi manifold dimensi lebih rendah, di mana kemudian lapisan terakhir mengklasifikasikan di atasnya. Jadi misalnya dalam jaringan konvolusional untuk klasifikasi di mana lapisan terakhir adalah lapisan softmax, kita dapat menafsirkan arsitektur sebagai melakukan proyeksi non-linear ke dimensi yang lebih kecil dan kemudian melakukan regresi logistik multinomial (lapisan softmax) pada proyeksi itu. Jadi dalam beberapa hal representasi terkompresi dari data kami memungkinkan kami untuk menghindari kutukan dimensi. Sekali lagi ini adalah satu interpretasi, dalam kenyataannya kutukan dimensi sebenarnya berdampak pada jaringan saraf, tetapi tidak pada tingkat yang sama dengan model yang diuraikan di atas.

SVM
SVM cenderung tidak terlalu berlebih seperti model linier umum karena regularisasi berlebihan yang terjadi. Lihat posting ini SVM, Overfitting, kutukan dimensi untuk lebih detail.

K-NN, K-Berarti

Baik K-mean dan K-NN sangat dipengaruhi oleh kutukan dimensi, karena keduanya menggunakan ukuran jarak kuadrat L2. Ketika jumlah dimensi meningkatkan jarak antara berbagai titik data juga meningkat. Inilah sebabnya mengapa Anda membutuhkan jumlah poin yang lebih besar untuk mencakup lebih banyak ruang dengan harapan jarak akan lebih deskriptif.

Jangan ragu untuk bertanya secara spesifik tentang model, karena jawaban saya cukup umum. Semoga ini membantu.

Armen Aghajanyan
sumber
Hai Amen Penjelasan singkat yang bagus untuk semua model yang saya tanyakan. Masalah dengan model linier masih belum jelas bagi saya: Apakah model linier berkinerja lebih baik atau lebih buruk daripada model k-NN dan k-Means untuk no: dimensi yang sama? Dan ketika Anda mengatakan collinearity adalah masalah untuk model linier, apakah Anda menyiratkan bahwa tanpa collinearity (atau minimal), dimensi tinggi tidak menjadi masalah dengan model linier?
Dileep Kumar Patchigolla
Sulit untuk mengukur apakah model linier akan berkinerja lebih baik daripada k-nn atau k-means untuk masalah yang sewenang-wenang. Jika masalah Anda terpisah secara linear, saya akan menempatkan taruhan saya pada model linier, sementara jika ruang Anda sedikit lebih rumit, saya akan menggunakan k-nn. Collinearity memperburuk masalah kutukan dimensionalitas, bahkan tanpa collinearity, kutukan dimensionalitas masih berlaku. K-means harus menderita pada tingkat yang sama seperti k-nn karena keduanya didorong oleh tetangga, dan umumnya menggunakan fungsi jarak yang sama. Pada kenyataannya sulit untuk mengukur seberapa buruk COD itu. Semoga ini membantu!
Armen Aghajanyan
Apa definisi Anda tentang kutukan dimensi (CoD)? Jawaban Anda tampaknya menunjukkan bahwa model linier paling menderita dari CoD, ini menyesatkan: sebagai metode global, model linier lebih sedikit menderita daripada metode lokal seperti KNN.
Matifou