Dapatkah jaringan saraf digunakan untuk merancang algoritma?

Setelah keberhasilan yang lebih baru dan lebih baru dari jaringan saraf dalam bermain game papan, orang merasa bahwa tujuan berikutnya yang kita tetapkan bisa menjadi sesuatu yang lebih berguna daripada mengalahkan manusia di Starcraft. Lebih tepatnya, saya bertanya-tanya apakah

Dapatkah jaringan saraf dilatih untuk memecahkan masalah algoritmik klasik?

Di sini saya berarti bahwa misalnya jaringan akan mendapatkan grafik masukan $G$ dengan tepi tertimbang, dan dua simpul $s$ dan $t$ ditentukan, dan kami meminta untuk menemukan terpendek $st$ jalan secepat mungkin. Lalu saya kira jaringan saraf akan menemukan dan melatih dirinya untuk menggunakan Dijkstra atau yang serupa.

$TC^0$$TC^0$$NP\not\subset TC^0$

Tentu saja, mengekstraksi algoritma adalah pertanyaan yang sama sekali berbeda. Saya menduga para ahli tahu bagaimana melakukan itu, tetapi mendiskusikannya bukanlah topik dari pertanyaan ini.

Ditambahkan dua hari kemudian: Setelah melihat jawaban, izinkan saya menentukan bahwa jika Anda menjawab dalam negatif, maka saya ingin tahu

Mengapa bermain catur lebih mudah daripada Dijkstra atau Graphisomorphism?

Menurut blog ini Oleh Reza Zadeh , melatih jaringan saraf untuk menghasilkan output yang benar bahkan hanya untuk dua pertiga dari contoh pelatihan itu secara komputasi sulit:

Memang, pada tahun 1988 J. Stephen Judd menunjukkan masalah berikut menjadi NP-hard:

Diberikan jaringan saraf umum dan satu set contoh pelatihan, apakah ada satu set bobot tepi untuk jaringan sehingga jaringan menghasilkan output yang benar untuk semua contoh pelatihan?

Judd juga menunjukkan bahwa masalah tetap NP-keras bahkan jika hanya membutuhkan jaringan untuk menghasilkan output yang benar untuk hanya dua pertiga dari contoh pelatihan, yang menyiratkan bahwa bahkan sekitar pelatihan jaringan saraf secara intrinsik sulit dalam kasus terburuk. Pada tahun 1993, Blum dan Rivest membuat berita lebih buruk: bahkan jaringan sederhana dengan hanya dua lapisan dan tiga node adalah NP-sulit untuk dilatih!

Ini bukan jawaban lengkap dan saya tidak terlalu berpengalaman dalam jaring saraf, tapi mungkin membantu.

NN pada dasarnya diberi input dan menghasilkan respons. Mereka kemudian dilatih melalui latihan untuk menghasilkan respons yang serupa pada input "serupa" dalam domain, misalnya, label yang sama untuk gambar binatang yang sama, atau peringkat tinggi ke posisi catur "baik" di mana bagus berarti peluang menang tinggi.

Jadi seperti yang saya komentari, jaring saraf adalah model komputasi yang tidak seragam yang bekerja dengan cara yang sama sekali berbeda dari algoritma langkah-demi-langkah yang dijalankan pada Mesin Turing. Alih-alih, anggap mereka sebagai sirkuit "lunak" yang menggunakan matematika kontinu daripada Boolean dan dapat diubah atau dilatih, dan diizinkan untuk dibuat salah.

Mengapa bermain catur lebih mudah daripada Dijkstra atau Graphisomorphism?

Sebagian, itu adalah perbedaan antara meminta seseorang untuk menjawab pertanyaan dengan kemampuan terbaik mereka, dan meminta mereka untuk satu jawaban yang benar bersama dengan bukti bahwa itu benar. Sebagian, itu adalah perbedaan antara memecahkan masalah ukuran tetap, dan sekaligus memecahkan masalah untuk semua ukuran input yang mungkin.

Setiap kali Dijkstra dijalankan pada sebuah instance, yang mungkin dalam ukuran berapa pun, itu secara implisit membuktikan bahwa outputnya adalah satu jawaban yang benar dan tidak ada yang lain. Dalam catur dan pengenalan gambar, seseorang memberikan jawaban terbaik dan kesalahan dapat ditoleransi. Lebih jauh, seseorang hanya melatih jaringan untuk memecahkan masalah ini satu ukuran pada satu waktu. Saya belum berpikir kita tahu bagaimana menggeneralisasi solusi neural net untuk, katakanlah, contoh masalah dari ukuran dan bentuk yang sama sekali berbeda.

Saya tidak berpikir kita harus berasumsi bahwa jaring saraf tidak bisa menyelesaikan jalur terpendek atau masalah algoritmik serupa, tetapi mereka memecahkan masalah dengan cara yang secara fundamental berbeda dari algoritma langkah-demi-langkah yang selalu benar.

Kembali ke kesamaan antara jaring saraf dan sirkuit, perhatikan bahwa sirkuit telah dipelajari selama beberapa dekade, namun dilihat dari kurangnya jawaban untuk (5) dari pertanyaan saya sebelumnya , kita hampir tidak tahu apa-apa tentang bagaimana membangun sirkuit yang sepenuhnya benar untuk diberikan. masalah kecuali melalui mentransformasikan algoritma yang seragam (Turing Machine) menjadi suatu rangkaian.

Saya bukan ahli dengan cara apa pun, tetapi saya belum melihat mengapa belum.

Jaringan saraf secara fundamental melakukan optimasi sesuai dengan semacam "model biaya / manfaat" yang sering sudah diketahui sebelumnya. Selain itu, ruang pencarian didefinisikan dengan baik, dengan gerakan yang valid dan tidak valid yang diketahui, dan "variasi" yang mudah untuk didefinisikan. Bahkan untuk AlphaZero dan AlphaGo, fungsi biaya mungkin didasarkan pada win-rate dan distribusi win-rate yang dihasilkan untuk semua gerakan yang mungkin setelah melakukan gerakan, atau semacam heuristik untuk itu.

Untuk merancang algoritma, Anda pada dasarnya meminta program untuk belajar bagaimana cara menghasilkan string yang benar (dengan fungsi enkode dan biaya implisit sudah diketahui) yang sesuai dengan program yang "mengeksekusi algoritma." Namun, ada banyak kemungkinan tak terbatas algoritma yang Anda gunakan untuk mengimplementasikan suatu program. Jadi mungkin Anda ingin mendefinisikan metrik "kebugaran" yang benar.

Namun, bahkan untuk program tertentu, metrik "kebugaran" bisa agak sulit untuk didefinisikan. Waktu? Penggunaan ruang? Kuantifikasi "efek samping?" Secara optimal, Anda akan menghasilkan "program terpendek" yang hanya melakukan apa yang Anda inginkan.

Saya kira jika Anda menemukan metrik kebugaran yang benar dan algoritma penyesuaian, Anda akan dapat melakukan ini.

"jaringan saraf" mengubah vektor dari satu ruang dimensi ke ruang dimensi lain. sehingga mereka tidak lebih dari penaksir fungsi yang sangat, sangat non-linear. bahkan jaringan saraf menggunakan algoritma aproksimasi untuk meminimalkan kerugian. Namun melatih jaringan saraf untuk merancang algoritma baru tidak perlu dipertanyakan lagi. tomas mikolov melakukan beberapa pekerjaan di area ini dengan stack augmented neural network, dan saya juga pernah mendengar tentang "mesin turing neural" untuk domain ini. Namun, menemukan strategi yang optimal telah menjadi penyebab mendasar mempelajari pembelajaran penguatan yang agak terkait dengan pertanyaan Anda. tetapi menggunakan jaringan saraf untuk merancang algoritma baru tidak mungkin, setidaknya dalam waktu dekat.

Saya seorang insinyur QA Automation jadi jangan mengklaim keahlian di jaringan saraf, tetapi, secara tautologis, ya NN dapat membuat algoritma sendiri. Manusia sendiri adalah NN pada tingkat tertentu, dan kami membuat algoritma, jadi masuk akal bahwa sistem NN buatan yang kami buat dapat membuat algoritma sendiri.