Bisakah jaringan saraf mendeteksi bilangan prima?

21

Saya tidak mencari cara yang efisien untuk menemukan bilangan prima (yang tentu saja merupakan masalah terpecahkan ). Ini lebih merupakan pertanyaan "bagaimana jika".

Jadi, dalam teori: Bisakah Anda melatih jaringan saraf untuk memprediksi apakah angka n yang diberikan adalah komposit atau utama? Bagaimana jaringan seperti itu ditata?

Fullk33
sumber
1
Lihatlah cs.indstate.edu/ ~legri
prime06.pdf
2
Jika bilangan prima mengikuti suatu pola dan seseorang kebetulan saja melatih jaringan saraf dengan cukup node tersembunyi untuk mendefinisikan batas klasifikasi, saya kira itu akan berhasil. Namun, kita tidak tahu apakah klasifikasi itu ada dan bahkan jika itu ada, kita harus membuktikan apa batasannya untuk membuktikan bahwa jaringan saraf memang menemukan pola yang benar.
quintumnia

Jawaban:

11

Keberhasilan awal pada pengujian bilangan prima melalui jaringan buatan disajikan dalam Solusi Jaringan Saraf Tiruan untuk Pengujian Bilangan Primer, László Egri, Thomas R. Shultz, 2006 . Pendekatan jaringan kaskade-korelasi (KBCC) berbasis pengetahuan menunjukkan yang paling menjanjikan, meskipun kepraktisan pendekatan ini dikalahkan oleh algoritma deteksi utama lainnya yang biasanya dimulai dengan memeriksa bit paling tidak signifikan, segera mengurangi pencarian menjadi setengah, dan kemudian mencari berdasarkan teorema lain dan heuristik hingga . Namun pekerjaan dilanjutkan denganPembelajaran Berbasis Pengetahuan dengan KBCC, Shultz et. Al. 2006floor(x)

02n1n

  1. Bisakah dengan hanya menghafal bilangan prima pada rentang bilangan bulat?
  2. Bisakah dengan mempelajari faktor dan menerapkan definisi prima?
  3. Bisakah dengan mempelajari algoritma yang dikenal?
  4. Bisakah dengan mengembangkan algoritma baru sendiri selama pelatihan?

Jawaban langsungnya adalah ya, dan sudah dilakukan sesuai dengan 1. di atas, tetapi itu dilakukan dengan pemasangan yang berlebihan, tidak mempelajari metode deteksi bilangan prima. Kita tahu otak manusia mengandung jaringan saraf yang dapat mencapai 2., 3., dan 4., jadi jika jaringan buatan dikembangkan sampai tingkat yang paling mereka pikirkan, maka jawabannya adalah ya untuk itu. Tidak ada bukti balik untuk mengecualikan mereka dari berbagai kemungkinan pada saat penulisan jawaban ini.

Tidak mengherankan bahwa pekerjaan telah dilakukan untuk melatih jaringan buatan pada pengujian bilangan prima karena pentingnya bilangan prima dalam matematika diskrit, penerapannya pada kriptografi, dan, lebih khusus lagi, untuk analisis kriptografi. Kita dapat mengidentifikasi pentingnya deteksi jaringan digital dari bilangan prima dalam penelitian dan pengembangan keamanan digital cerdas dalam karya-karya seperti Studi Pertama Pendekatan Jaringan Saraf Tiruan dalam Cryptosystem RSA , Gc Meletius et. al., 2002 . Ikatan kriptografi untuk keamanan negara kita masing-masing juga merupakan alasan mengapa tidak semua penelitian saat ini di bidang ini menjadi publik. Kita yang mungkin memiliki izin dan paparan hanya dapat berbicara tentang apa yang tidak diklasifikasikan.

Di pihak sipil, pekerjaan berkelanjutan dalam apa yang disebut deteksi kebaruan adalah arah penting penelitian. Mereka seperti Markos Markou dan Sameer Singh sedang mendekati deteksi kebaruan dari sisi pemrosesan sinyal , dan jelas bagi mereka yang memahami bahwa jaringan buatan pada dasarnya adalah prosesor sinyal digital yang memiliki kemampuan self-tuning multi-point dapat melihat bagaimana pekerjaan mereka berlaku langsung pada ini pertanyaan. Markou dan Singh menulis, "Ada banyak aplikasi di mana deteksi kebaruan sangat penting termasuk pemrosesan sinyal, visi komputer, pengenalan pola, penambangan data, dan robotika."

Di sisi matematika kognitif, pengembangan matematika kejutan, seperti Learning with Surprise: Theory and Applications (thesis), Mohammadjavad Faraji, 2016 dapat melanjutkan apa yang Ergi dan Shultz mulai.

Douglas Daseeco
sumber
1

Secara teori, jaringan saraf dapat memetakan setiap fungsi yang diberikan ( sumber ).

Namun, jika Anda melatih jaringan dengan angka 0untuk N, Anda tidak dapat menjamin bahwa jaringan akan mengklasifikasikan nomor di luar rentang yang benar ( n > N).

Jaringan seperti itu akan menjadi feed forward network ( MLP ) biasa karena recurrency tidak menambah apa pun pada klasifikasi input yang diberikan. Jumlah layer & node hanya dapat ditemukan melalui coba-coba.

Thomas W
sumber
1
Teorema universal berlaku untuk fungsi kontinu pada himpunan bagian yang ringkas. Prime / not prime bukanlah fungsi semacam itu.
pasaba por aqui
1
@pasabaporaqui: Dalam hal ini fungsi primeness dapat didekati dengan cukup baik oleh fungsi kontinu dengan puncak pada nilai-nilai bilangan prima. Jadi NN mungkin menghasilkan peluang 90% untuk menjadi yang terbaik untuk 6.93 - itu jelas tidak masuk akal, tetapi jika Anda mendiskritkan input dan output, Anda tidak benar-benar peduli tentang apa yang akan diprediksi oleh NN untuk non-integer. Saya pikir jawaban ini pada dasarnya benar.
Neil Slater
1

Saya seorang peneliti sarjana di universitas Prairie View A&M. Saya pikir saya akan berkomentar, karena saya hanya menghabiskan beberapa minggu mengutak-atik model MLPRegressor untuk memprediksi bilangan prima ke-n. Baru-baru ini tersandung ke dalam minima super rendah, di mana 1000 ekstrapolasi pertama di luar data pelatihan menghasilkan kesalahan kurang dari 0,02 persen. Bahkan pada 300.000 penawaran perdana, diskonnya sekitar 0,5 persen. Model saya sederhana: 10 lapisan tersembunyi, dilatih dengan prosesor tunggal kurang dari 2 jam.

Bagi saya, itu menimbulkan pertanyaan, "Apakah ada fungsi yang masuk akal yang menghasilkan bilangan prima ke-n?" Saat ini algoritma menjadi komputasi sangat melelahkan untuk n ekstrim. Lihat celah waktu antara bilangan prima terbesar terbaru yang ditemukan. Beberapa dari mereka terpisah bertahun-tahun. Saya tahu sudah dibuktikan bahwa jika fungsi seperti itu ada, itu tidak akan jumlahnya banyak.

Cody K
sumber
Selamat datang di AI.SE! Harap perhatikan bahwa kami hanya mengizinkan jawaban (sebagai lawan dari komentar) di bagian jawaban, jadi saya sedikit memperbaiki posting Anda untuk fokus pada menjawab pertanyaan. Untuk pengantar ke situs kami, lihat tur .
Ben N
Hai Cody, ini belum lama. Tapi saya ingin mengobrol dengan Anda tentang tes yang Anda lakukan. Apakah Anda bersedia untuk live chat tentang apa yang Anda lakukan dan apa yang Anda rasakan? Saya ingin melihat apakah ada kemungkinan untuk bereksperimen lebih jauh dengan ini.
momomo
-1

ya itu layak, tetapi menganggap bahwa masalah faktorisasi bilangan bulat adalah masalah NP-sesuatu dan masalah BQP .

karena ini, tidak mungkin bahwa jaringan saraf murni berdasarkan komputasi klasik menemukan bilangan prima dengan akurasi 100%, kecuali P = NP.

ncomputer
sumber
Seperti yang dijelaskan pertanyaan, periksa apakah angka prima bukan masalah NP.
pasaba por aqui