Mengapa pembelajaran mesin tidak mengenali bilangan prima?

Katakanlah kita memiliki representasi vektor bilangan bulat n, V_n

Vektor ini adalah input untuk algoritma pembelajaran mesin.

Pertanyaan pertama: Untuk jenis representasi apa mungkin untuk mempelajari keutamaan / kekompakan n menggunakan jaringan saraf atau pemetaan vektor-ke-bit ML lainnya. Ini murni teoretis - jaringan syaraf mungkin tidak dibatasi ukurannya.

Mari kita abaikan representasi yang sudah terkait dengan pengujian primality seperti: daftar faktor n yang dipisahkan nol, atau keberadaan saksi kesesuaian seperti dalam Miller Rabin. Sebagai gantinya, mari kita fokus pada representasi dalam berbagai radio, atau representasi sebagai vektor koefisien (mungkin multivarian) polinomial. Atau yang eksotis lainnya seperti yang dinyatakan.

Pertanyaan kedua: untuk apa, jika ada, jenis algoritma ML akan mempelajari hal ini tidak mungkin terlepas dari spesifikasi vektor representasi? Sekali lagi, mari kita lupakan representasi 'terlarang oleh hal-hal sepele' yang contohnya diberikan di atas.

Output dari algoritma pembelajaran mesin adalah bit tunggal, 0 untuk prima, 1 untuk komposit.

Judul pertanyaan ini mencerminkan penilaian saya bahwa konsensus untuk pertanyaan 1 adalah 'tidak diketahui' dan konsensus untuk pertanyaan 2 adalah 'mungkin sebagian besar algoritma ML'. Saya bertanya ini karena saya tidak tahu lebih dari ini dan saya berharap seseorang dapat menunjukkan jalannya.

Motivasi utama, jika ada, dari pertanyaan ini adalah: adakah batasan 'informasi teoretis' pada struktur himpunan bilangan prima yang dapat ditangkap dalam jaringan saraf dengan ukuran tertentu? Karena saya tidak ahli dalam terminologi semacam ini, izinkan saya mengulangi ide ini beberapa kali dan melihat apakah saya mendapatkan pendekatan Monte-Carlo untuk konsep: apa kompleksitas algoritmik dari himpunan bilangan prima? Dapatkah fakta bahwa bilangan prima adalah Diophantine yang dapat dihitung berulang secara rekursif (dan dapat memenuhi persamaan diophantine besar tertentu ) dapat digunakan untuk menangkap struktur yang sama dalam jaringan saraf dengan input dan output yang dijelaskan di atas.

ini adalah pertanyaan / masalah lama dengan banyak, banyak koneksi yang mendalam ke dalam teori bilangan, matematika, TCS dan khususnya Pembuktian Teorema Otomatis. [5]

pertanyaan lama yang hampir kuno adalah, "adakah formula untuk menghitung bilangan prima"

jawabannya adalah, ya, dalam arti tertentu, ada berbagai algoritma untuk menghitungnya.

fungsi Riemann zeta dapat diorientasikan sebagai "algoritma" untuk menemukan bilangan prima.

Tampaknya mungkin bagi saya bahwa pendekatan GA, algoritma genetika mungkin berhasil pada masalah ini suatu hari dengan pengaturan yang cerdik, yaitu GA adalah teknologi terdekat yang diketahui memiliki peluang paling besar untuk berhasil. [6] [7] itu masalah menemukan algoritma dari serangkaian contoh yang terbatas, yaitu pembelajaran mesin, yang sangat mirip dengan induksi matematika. Namun tampaknya tidak ada banyak penelitian tentang penerapan GAS dalam teori bilangan sejauh ini.

yang terdekat dengan ini dalam literatur yang ada tampaknya misalnya [8] yang membahas pengembangan dugaan kembar utama dengan cara otomatis yaitu "pembuatan dugaan otomatis".

pendekatan lain adalah program yang memiliki seperangkat besar tabel fungsi standar, bersama dengan beberapa logika konversi canggih, untuk mengenali urutan bilangan bulat standar. ini adalah fungsi baru yang dibangun ke dalam Mathematica yang disebut findsequence[3]

ini juga terhubung ke bidang yang relatif baru yang disebut "matematika eksperimental" [9,10] atau apa yang juga disebut penelitian "empiris" di TCS.

Poin dasar lain untuk dibuat di sini adalah bahwa urutan bilangan prima tidak "mulus", sangat tidak teratur, kacau, fraktal, dan algoritma pembelajaran mesin standar secara historis didasarkan pada optimasi numerik dan meminimalkan kesalahan (misalnya penurunan gradien), dan tidak melakukannya baik menemukan jawaban yang tepat untuk masalah diskrit. tetapi sekali lagi GA dapat berhasil dan telah terbukti berhasil dalam bidang / rezim ini.

[1] apakah ada persamaan matematika untuk prime n, math.se

[2] rumus untuk bilangan prima , wikipedia

[3] fungsi pencarian wolfram

[4] fungsi riemann zeta

[5] sukses atas pembuktian teorema otomatis

[6] aplikasi algoritma genetika di dunia nyata

[7] menerapkan algoritma genetika untuk membuktikannya secara otomatis oleh Wang

[8] Pembuatan Konjektur Otomatis dalam Teori Angka menggunakan HR, Otter dan Maple colton

[9] Apakah ada aplikasi matematika eksperimental di TCS?

[10] Daftar bacaan tentang algoritme eksperimental

Pertanyaannya, menurut saya, cukup kabur dan melibatkan beberapa kesalahpahaman, jadi jawaban ini hanya berusaha untuk menyediakan kosakata yang tepat dan mengarahkan Anda ke arah yang benar.

Ada dua bidang ilmu komputer yang secara langsung mempelajari masalah tersebut. Inferensi induktif dan teori pembelajaran komputasi . Kedua bidang ini sangat terkait erat dan perbedaannya adalah sosial dan estetika, bukan formal.

Perbaiki alfabet yang terbatas dan himpunan semua bahasa yang terdiri dari kata-kata yang terbatas panjang lebih . Ini adalah semua yang Anda dapat mengekspresikan dalam hal . Sekarang pertimbangkan bahasa . Anda dapat menganggap ini sebagai konsep yang Anda minati. Anda sering harus memperbaiki keluarga konsep yang Anda pedulikan karena, seperti yang telah ditunjukkan orang lain, representasi konsep dan penyajian data sangat penting.P ( A ∗ ) A A F ⊆ P ( A ∗$A$$\mathcal{P}(A^*)$$A$$A$$\mathcal{F} \subseteq \mathcal{P}(A^*)$

Bayangkan seorang guru yang akan mengajarkan Anda sebuah konsep. Guru akan memilih salah satu bahasa tanpa sepengetahuan Anda. Guru kemudian akan memberikan informasi kepada Anda tentang bahasa tersebut. Ada banyak presentasi. Yang paling sederhana adalah memberi Anda contoh. Sebuah penyajian data positif adalah fungsi memuaskan yang$f: \mathbb{N} \to A^*$

Jadi, penyajian data positif adalah penghitungan konsep target, seringkali dengan beberapa kondisi kewajaran tambahan. Anda juga dapat meminta presentasi yang melabeli kata-kata tergantung pada apakah mereka dalam bahasa atau tidak. Sekali lagi, Anda dapat menambahkan kondisi tambahan untuk memastikan keadilan dan cakupan semua kata.

Misalkan kita memiliki keluarga representasi bahasa. Itu berarti setiap elemen dari mendefinisikan bahasa . Contoh representasi adalah rumus Boolean, automata terbatas, ekspresi reguler, sistem persamaan linear, bahasa pemrograman domain spesifik, dll. Apa pun yang Anda inginkan, sungguh, kecuali berbagai kondisi biasanya dikenakan untuk memastikan representasi memiliki sifat-sifat penelusuran dasar.M R e p L ( M $Rep$$M$$Rep$$L(M)$

Sebuah pelajar pasif adalah fungsi yang membuat dugaan setelah melihat setiap kata yang disediakan oleh guru. Kita mungkin sering meminta pembelajar konsisten. Artinya, bahasa harus berisi semua kata untuk . Pelajar menstabilkan jika pelajar menebak untuk bahasa target tidak berubah. Secara khusus, harus ada beberapa indeks sehingga untuk semua , . Pelajar berhasil jika bahasa final sama dengan bahasa target.L ( p ( i ) ) f ( j ) j ≤ i k j ≥ k L ( p ( j ) ) = L ( p ( j + 1 ) $p: \mathbb{N} \to Rep$$L(p(i))$$f(j)$$j \le i$$k$$j \ge k$$L(p(j)) = L(p(j+1))$

Izinkan saya menekankan bahwa ini hanya satu formalisasi spesifik dari satu model pembelajaran tertentu. Tetapi ini adalah langkah nol sebelum Anda dapat mulai bertanya dan mempelajari pertanyaan-pertanyaan yang Anda minati. Model pembelajaran dapat diperkaya dengan memungkinkan interaksi antara pelajar dan guru. Daripada keluarga bahasa yang sewenang-wenang, kita dapat mempertimbangkan bahasa yang sangat spesifik, atau bahkan representasi spesifik (seperti fungsi Boolean monoton). Ada perbedaan antara apa yang dapat Anda pelajari di setiap model dan kompleksitas pembelajaran. Inilah salah satu contoh hasil ketidakmungkinan yang mendasar.

Emas [1967] Tidak satu pun rumpun bahasa yang berisi semua bahasa berhingga dan setidaknya satu bahasa super berhingga dapat dipelajari secara pasif hanya dari data positif.

Seseorang harus sangat berhati-hati dalam menafsirkan hasil ini. Misalnya, Dana Angluin menunjukkan di tahun 80-an itu

Angluin [1982] Kelas bahasa reversibel dapat dipelajari secara pasif dalam batas dari data positif.$k$

Kelas bahasa reversibel tidak terbatas, berisi bahasa super-terbatas, tetapi yang menarik, tidak mengandung semua bahasa terbatas. Sekarang setelah Anda mengubah model pembelajaran, hasil dasarnya berubah.$k$

Angluin [1987] Bahasa reguler dapat dipelajari dari seorang guru yang menjawab pertanyaan kesetaraan dan memberikan contoh tandingan. Algoritme adalah polinomial dalam himpunan status DFA minimal dan panjang sampel balik maksimal.

Ini adalah hasil yang cukup kuat dan positif dan baru-baru ini telah menemukan beberapa aplikasi. Namun, seperti biasa detailnya penting, seperti judul makalah di bawah ini sudah menyarankan.

Masalah DFA konsisten minimum tidak dapat diperkirakan dalam dan polinomial , Pitt dan Warmuth, 1989.

Sekarang Anda mungkin bertanya-tanya, bagaimana semua ini relevan dengan pertanyaan Anda? Jawaban saya adalah bahwa ruang desain untuk definisi matematis masalah Anda sangat besar dan titik spesifik yang Anda pilih dalam ruang ini akan memengaruhi jenis jawaban yang akan Anda dapatkan. Hal di atas tidak dimaksudkan sebagai survei komprehensif tentang bagaimana memformalkan masalah pembelajaran. Itu hanya dimaksudkan untuk menunjukkan arah yang ingin Anda selidiki. Semua referensi dan hasil yang saya kutip sangat tanggal, dan lapangan telah melakukan banyak hal sejak itu. Ada buku teks dasar yang bisa Anda baca untuk mendapatkan latar belakang yang cukup untuk merumuskan pertanyaan Anda secara tepat dan menentukan apakah jawaban yang Anda cari sudah ada.

Keberhasilan suatu algoritma pembelajaran sangat tergantung pada representasi. Bagaimana Anda menyajikan input ke algoritma? Dalam kasus yang ekstrem, anggaplah Anda menyajikan angka sebagai urutan faktor prima - dalam hal ini, belajar cukup sepele. Di ekstrem lain, anggap mewakili angka sebagai string biner. Semua algoritma pembelajaran standar yang saya tahu akan gagal di sini. Inilah yang akan berhasil: temukan mesin Turing terkecil yang menerima semua contoh positif dan menolak semua yang negatif. [Latihan: buktikan bahwa ini adalah pelajar universal.] Satu masalah dengan itu adalah bahwa tugas tersebut tidak dapat dihitung oleh Turing. Untuk meletakkan segala sesuatu dalam perspektif, dapatkah Anda belajar mengenali keutamaan hanya berdasarkan representasi biner?

Masalah ini adalah bagian dari penelitian modern: diberikan input dan output data, cari algoritma paling sederhana yang menghasilkan output dari input. Jaringan RNN adalah Turing-complete, jadi secara teoritis dengan SGD tanpa akhir Anda bisa berakhir di RNN yang setara dengan kode ini:

bool isPrime(int n, int d) {
    if(n<2)
        return 0;
    if(d == 1)
        return true;
    else 
    {
        if(n % d == 0) 
            return false;
        else
            return isPrime(n, d - 1);
    }
}

pada dataset ini: 0 => 0, 1 => 0, 2 => 1, 3 => 1, 4 => 0, 5 => 1, ... dll

Masalahnya adalah bahwa kita tidak memiliki teori praktis yang dapat diandalkan pada konvergensi SGD atau perkiraan waktu yang diperlukan untuk konvergensi atau kedalaman jaringan saraf. Tetapi penelitian terbaru menunjukkan bahwa masalah yang sama dapat diselesaikan:

https://en.wikipedia.org/wiki/Neural_Turing_machine

https://www.microsoft.com/en-us/research/wp-content/uploads/2017/10/curr_opin_sys_biol_17.pdf

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/12/cav13.pdf

gunakan google scholar untuk mencari kata kunci ...

Pembelajaran mesin tunduk pada hukum kompleksitas komputasi.

Masalah faktorisasi utama adalah di kelas kompleksitas NP, bahkan mungkin NP-keras (tidak terbukti).

Itulah mengapa mendeteksi bilangan prima adalah salah satu masalah tersulit dalam pembelajaran mesin, dan mungkin tidak mungkin sama sekali dengan pendekatan itu.

Komputer kuantum (QC) dapat melakukannya dalam waktu polinomial, tetapi Shor's adalah determinisme kasar, bukan pembelajaran mesin.

Mungkin algoritma pembelajaran QC berdasarkan Shor adalah sebuah pendekatan. Saya benar-benar hanya membenturkan batu bersama-sama dengan menyarankan itu.