Artikel ini menceritakan ulang gratis saya tentang Learnability dapat diputuskan, Shai Ben-David, et al.

Baru-baru ini, sebuah artikel muncul di Habré Machine belajar menghadapi masalah matematika yang belum terselesaikan , yang merupakan terjemahan dari artikel oleh Shay Ben-David di Nature News dengan nama yang sama. Namun, karena sifat topik dan singkatnya ulasan asli, tetap sama sekali tidak bisa dimengerti oleh saya apa yang ada di artikel. Mengenal Shai Ben-David, sebagai penulis buku yang sangat bagus "Memahami Pembelajaran Mesin: Dari Teori ke Algoritma", saya menjadi tertarik dengan topik ini, berkenalan dengan karya ini dan mencoba menguraikan poin-poin utama di sini.

Saya harus segera mengatakan bahwa artikelnya agak rumit dan, mungkin, saya melewatkan beberapa poin penting, tetapi ulasan saya akan lebih lengkap daripada yang sudah ada di Habré.

Beberapa kata tentang pembelajaran PAC secara umum

Hal pertama yang membingungkan saya dalam ulasan dari Nature News adalah bahwa masalah belajar itu sendiri disajikan sebagai sesuatu yang sama sekali baru. Sebenarnya, ini adalah masalah yang panjang dan relatif banyak dipelajari.

Ada teori tentang pembelajaran yang mungkin hampir benar (Mungkin A ppro kira-kira C orrect Learning, PAC ).

Teori ini berasal dari tahun 80-an abad lalu. Namun, itu tidak memberikan indikator terukur yang akan mencerminkan kemampuan pembelajaran suatu algoritma. Tetapi jawaban seperti itu diberikan oleh teori pembelajaran statistik ( teori VC ) yang sudah dikembangkan oleh V. Vapnik dan A. Chervonenkis. Teori ini didasarkan pada indikator numerik dimensi VC. Dimensi VC adalah perkiraan kombinasi ukuran data maksimum yang dapat dibagi oleh algoritma menjadi dua bagian dalam semua cara yang mungkin.

Teorema utama teori VC, dalam salah satu formulasi yang mungkin, membuktikan fakta bahwa jika dimensi VC dari algoritma tersebut terbatas, maka ia dilatih oleh PAC. Selain itu, dimensi VC merupakan indikator seberapa cepat dengan meningkatnya ukuran sampel empiris, nilai risiko empiris menyatu dengan nilai risiko rata-rata.

Dengan demikian, masalah pembelajaran mesin algoritma pembelajaran mesin per se relatif dipelajari dengan baik dan memiliki dasar matematika yang ketat.

Lalu, apa yang menjadi subjek dari sebuah artikel di Nature?

Para penulis menulis bahwa masalah dengan teori PAC, berdasarkan berbagai dimensi dimensi, adalah bahwa itu tidak universal.

Penulis memberikan contoh menarik dari masalah yang pernyataannya dirancang sedemikian rupa sehingga kesuksesan tidak dapat dirumuskan sebagai pembelajaran PAC. Penulis menulis:

Bayangkan kami memiliki situs Internet tempat kami menampilkan iklan. Tetapkan X sebagai himpunan semua pengunjung potensial ke situs ini. Iklan dipilih dari kumpulan iklan tertentu. Secara kondisional, anggaplah bahwa setiap iklan dari kumpulan diarahkan ke beberapa kategori pengguna: iklan olahraga untuk penggemar olahraga, dll. Tugasnya adalah menempatkan persis jenis iklan yang paling relevan bagi pengunjung situs .

Masalahnya di sini adalah bahwa kita tidak benar-benar tahu siapa yang akan mengunjungi situs di masa depan. Untuk meringkas, pernyataan masalah seperti itu dapat digambarkan sebagai berikut:

Memiliki set fitur $$$F$lebih dari set $$$X$menemukan fungsi seperti itu $$$F_ {best}$sehingga metriknya atas distribusi yang tidak diketahui $$$P$maksimum. Selain itu, perlu untuk menemukan fungsi seperti itu berdasarkan pada set terbatas jumlah independen yang terdistribusi secara identik dari $$$P$

Pelatihan EMX

Shai Ben-David dan rekan-rekannya memperkenalkan konsep baru - E merangsang M a X imum (pembelajaran EMX), yang hanya memberikan kriteria pembelajaran untuk masalah maksimalisasi seperti:

Untuk set fitur $$$F$, set input $$$X$dan distribusi yang tidak diketahui $$$P$untuk nomor berapa pun $$$d = d (\ epsilon, \ delta)$fungsi $$$G (s)$adalah $$$(\ epsilon, \ delta)$-EMX-terlatih jika untuk distribusi apa pun $$$P$:

$$

$$Pr_ {S \ sim P ^ d} [\ mathbb {E} _P (G (S)) \ leq \ sup_ {h \ dalam F} \ mathbb {E} (h) - \ epsilon] \ leq \ delta$$

Definisi pembelajaran ini tidak diragukan lagi lebih umum daripada konsep PAC.

Lalu di mana kontinum dan "masalah matematika yang belum terpecahkan" ada hubungannya dengan itu?

Para penulis membuktikan teorema berikut:
Pergantian EMX $$$F$tentang $$$P$independen dari sistem aksioma Zermelo - Frenkel dengan aksioma pilihan (selanjutnya disebut ZFC).

Dengan kata lain, dengan menggunakan aksioma matematis standar, dalam kasus umum kita tidak dapat membuktikan kemungkinan menemukan solusi untuk masalah pembelajaran EMX atau membuktikan ketidakmungkinan menemukan solusi ini.

Para penulis juga menunjukkan bahwa untuk kasus umum pembelajaran EMX, tidak ada analog dari dimensi VC (atau dimensi lain) yang akan terbatas dalam hal pengukuran terukur EMX, dan sebaliknya, belajar-EMX akan mengikuti dari keterbatasannya. Lebih tepatnya mereka merumuskannya sebagai berikut:

Ada konstanta seperti itu $$$c$bahwa jika kita mengasumsikan konsistensi ZFC, maka tidak ada properti seperti itu $$$A (X, Y)$itu untuk beberapa$$ $ inline $ m, M> c $ inline $ untuk apa saja $$$X$dan set fitur $$$F$akan dilakukan:

• Jika $$$A (X, Y)$benar kalau begitu $$$(1/3, 1/3)$kompleksitas pembelajaran EMX $$$F$tidak melebihi M;
• Jika $$$A (X, Y)$salah kalau begitu $$$(1/3, 1/3)$kompleksitas pembelajaran EMX $$$F$setidaknya m;

Sebaliknya, ini berlaku untuk, misalnya, dimensi VC, karena untuk $$$A (X, Y)$sama $$$VC \ leq d$itu pada dasarnya akan menjadi perumusan teorema utama teori VC.

Kesimpulan

Pesan dari pekerjaan ini sebenarnya sedikit terkait dengan masalah praktis pembelajaran mesin, atau bahkan dengan pertanyaan teoretis dari teori pembelajaran statistik. Tampak bagi saya bahwa ada dua pemikiran utama dalam pekerjaan ini:

• Koneksi yang indah antara pembelajaran EMX dan teorema Gödel;
• Ketidakmungkinan mendasar untuk menciptakan karakterisasi pembelajaran universal (seperti dimensi VC) untuk kelas umum masalah pembelajaran mesin.

Pada saat yang sama, saya pribadi sangat tidak suka judul "Pembelajaran Mesin Telah Menghadapi Masalah Matematika yang Tidak Terselesaikan," digunakan dalam terjemahan ulasan artikel ini . Menurut pendapat saya, ini adalah clickbait absolut, apalagi, itu tidak sesuai dengan kenyataan. Karya aslinya tidak berarti seseorang menabrak sesuatu. Pembelajaran mesin dan teori PAC bekerja dan terus bekerja. Dikemukakan bahwa teori PAC tidak dapat digeneralisasi ke beberapa pernyataan khusus tentang masalah pembelajaran mesin, ditemukan hubungan yang menarik dengan teorema Gödel, tetapi tidak ada sepatah kata pun tentang beberapa masalah yang tidak terpecahkan yang telah dihadapi pembelajaran mesin.