Apakah ada pekerjaan yang menggabungkan pembelajaran mesin dan bentuk-bentuk teori kompleksitas yang lebih eksotis?

13

Sepertinya saya bahwa ahli pembelajaran mesin / penambangan data akrab dengan P dan NP, tetapi jarang berbicara tentang beberapa kelas kompleksitas yang lebih halus (misalnya NC, BPP, atau IP) dan implikasinya untuk menganalisis data secara efektif. Apakah ada survei pekerjaan yang melakukan ini?

cc.complexity-theory reference-request machine-learning Mike Izbicki
sumber
2
Tidak ada survei yang saya ketahui, tetapi periksa petunjuk ini untuk "belajar kuantum" (# 5) dari pos ini: blog.computationalcomplexity.org/2012/10/quantum-workshop.html
Suresh Venkat
pembelajaran mesin secara teratur menyerang masalah yang sangat sulit yang mungkin di luar NP untuk optimasi "global" tetapi di dalam NP atau kurang keras dari itu untuk optimasi "lokal". sehingga seluruh konsep kelas kompleksitas menjadi buram ketika seseorang mengoptimalkan untuk hasil "cukup baik" yang diukur lebih oleh pengukuran kualitas yang tergantung aplikasi & dalam arti apriori benar-benar dikenal untuk menjalankan algoritma (s) ....
vzn
@vzn Bagi saya, kehalusan itu sepertinya lebih banyak alasan untuk memperhatikan kompleksitas! Mungkin memberikan beberapa wawasan yang sangat menarik.
Mike Izbicki
tentu saja ada hubungan antara teori belajar, kompleksitas sirkuit, kriptografi. tapi ini adalah sudut teori belajar yang agak dihapus dari praktik pembelajaran mesin. jika Anda tertarik, saya bisa membuat beberapa petunjuk
Sasho Nikolov
ya, contoh lain, BDD (diagram keputusan biner) telah digunakan dalam algoritme basis data / penambangan data & memiliki koneksi yang kuat ke kompleksitas rangkaian. tapi menurut saya seluruh pertanyaan mungkin sedikit premis yang rumit karena banyak pembelajaran mesin yang pragmatis & kompleksitas ML yang diterapkan sering dipelajari secara tidak langsung / secara empiris melalui analisis implementasi nyata dari algoritma daripada mencoba untuk secara teoritis mengantisipasi atau mengklasifikasikannya secara ketat.
vzn

Jawaban:

3

Ada beberapa perbedaan yang melekat atau ketidaksamaan pendekatan antara dua bidang pembelajaran mesin yang diterapkan dan teori kompleksitas / TCS.

Berikut ini adalah lokakarya terbaru tentang masalah ini di Center for Computational Intractability, Princeton dengan banyak video.

Deskripsi: Banyak pendekatan saat ini dalam pembelajaran mesin bersifat heuristik: kami tidak dapat membuktikan batas yang baik pada kinerja atau waktu berjalannya. Lokakarya kecil ini akan fokus pada proyek merancang algoritma dan pendekatan yang kinerjanya dapat dianalisis secara ketat. Tujuannya adalah untuk melihat melampaui pengaturan di mana batas yang dapat dibuktikan sudah ada.

Dalam TCS bidang studi utama "belajar" kadang-kadang mungkin membingungkan bahkan disebut "pembelajaran mesin" disebut teori PAC yang merupakan kependekan dari Mungkin Sekitar Kurang Tepat. asalnya awal 1980-an mendahului penelitian yang jauh lebih modern dalam "pembelajaran mesin." wikipedia menyebutnya bagian dari teori pembelajaran komputasi lapangan . PAC sering menyangkut hasil belajar rumus boolean yang diberikan sampel statistik dari distribusi, dll, dan keakuratan pembelajaran yang dapat diperoleh dengan berbagai algoritme atau sampel terbatas. Ini dipelajari dengan cara teoritis yang ketat dengan kaitan dengan kelas kompleksitas. Tapi itu bukan halaman studi & wikipedias terapan tentang pembelajaran mesin bahkan tidak mencantumkannya.

vzn
sumber
5
"panggilan wikipedia" ... apakah Anda benar-benar tahu tentang subjek ini? 1) wiki untuk pembelajaran mesin memiliki bagian Teori yang menghubungkan ke teori pembelajaran komputasi halaman 2) karya teori pembelajaran Valiant, Vapnik, Schapire, antara lain, telah berdampak besar pada praktik pembelajaran mesin.
Sasho Nikolov