Latar Belakang
Mengenali keutamaan sepertinya tidak cocok untuk jaringan saraf (buatan). Namun, teorema aproksimasi universal menyatakan bahwa jaringan saraf dapat mendekati setiap fungsi kontinu, jadi khususnya harus dimungkinkan untuk merepresentasikan fungsi yang didukung secara halus seperti yang diinginkan. Jadi mari kita coba mengenali semua bilangan prima di antara jutaan angka pertama.
Lebih tepatnya, karena ini adalah situs web pemrograman, mari naik ke 2 ^ 20 = 1.048.576. Jumlah bilangan prima di bawah ambang batas ini adalah 82.025 atau sekitar 8%.
Tantangan
Seberapa kecil jaringan syaraf yang Anda temukan yang dengan benar mengklasifikasikan semua integer 20-bit sebagai prime atau bukan prime?
Untuk keperluan tantangan ini, ukuran jaringan saraf adalah jumlah total bobot dan bias yang diperlukan untuk mewakilinya.
Detail
Tujuannya adalah untuk meminimalkan ukuran jaringan saraf tunggal dan eksplisit.
Input ke jaringan Anda akan menjadi vektor dengan panjang 20 yang berisi bit individual dari integer, diwakili baik dengan 0s dan 1s atau sebagai alternatif dengan -1s dan +1. Urutan ini bisa menjadi bit paling signifikan pertama atau bit paling signifikan pertama.
Output dari jaringan Anda harus berupa angka tunggal, sehingga di atas beberapa cutoff input dikenali sebagai prima dan di bawah cutoff yang sama input diakui sebagai tidak prima. Misalnya, positif mungkin berarti prima (dan negatif tidak prima), atau alternatif lebih besar dari 0,5 mungkin berarti prima (dan kurang dari 0,5 tidak prima).
Jaringan harus 100% akurat pada semua 2 ^ 20 = 1.048.576 input yang mungkin. Seperti disebutkan di atas, perhatikan bahwa ada 82.025 bilangan prima dalam kisaran ini. (Oleh karena itu selalu menghasilkan "tidak prima" akan menjadi 92% akurat.)
Dalam hal terminologi jaringan saraf standar, ini kemungkinan akan disebut overfitting . Dengan kata lain, tujuan Anda adalah untuk menyesuaikan bilangan prima dengan sempurna. Kata lain yang mungkin digunakan adalah "set latihan" dan "set tes" adalah sama.
Tantangan ini tidak mempertimbangkan jumlah parameter "bisa dilatih" atau "bisa dipelajari". Memang, jaringan Anda cenderung berisi bobot yang dikodekan secara keras, dan contoh di bawah ini seluruhnya berkode keras. Sebaliknya, semua bobot dan bias dianggap sebagai parameter dan dihitung.
Panjang kode yang diperlukan untuk melatih atau menghasilkan jaringan saraf Anda tidak relevan dengan skor Anda, tetapi memposting kode yang relevan tentu dihargai.
Baseline
Sebagai dasar, adalah mungkin untuk "menghafal" semua 82.025 bilangan prima dengan 1.804.551 total bobot dan bias.
Perhatikan bahwa kode ini yang mengikuti mencakup banyak hal: contoh kerja, kode uji kerja, definisi kerja jaringan saraf menggunakan perpustakaan jaringan saraf yang dikenal, jaringan saraf "hard-coded" (atau setidaknya, tidak "terlatih"), dan pengukuran skor yang berhasil.
import numpy as np
bits = 20
from keras.models import Sequential
from keras.layers import Dense
from sympy import isprime
# Hardcode some weights
weights = []
biases = []
for n in xrange(1<<bits):
if not isprime(n):
continue
bit_list = [(n / (1 << i))%2 for i in xrange(bits)]
weight = [2*bit - 1 for bit in bit_list]
bias = - (sum(bit_list) - 1)
weights.append(weight)
biases .append(bias)
nprimes = len(biases)
weights1 = np.transpose(np.array(weights))
biases1 = np.array(biases )
weights2 = np.full( (nprimes,1), 1 )
biases2 = np.array( [0] )
model = Sequential()
model.add(Dense(units=nprimes, activation='relu', input_dim=bits, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
print "Total weights and biases: {}".format( np.size(weights1) + np.size(weights2) + np.size(biases1) + np.size(biases2) )
# Evaluate performance
x = []
y = []
for n in xrange(1<<bits):
row = [(n / (1 << i))%2 for i in xrange(bits)]
x.append( row )
col = 0
if isprime(n):
col = 1
y.append( col )
x = np.array(x)
y = np.array(y)
model.compile(loss='binary_crossentropy', optimizer='sgd', metrics=['accuracy'])
loss, accuracy = model.evaluate(x, y, batch_size=256)
if accuracy == 1.0:
print "Perfect fit."
else:
print "Made at least one mistake."
Apa itu jaringan saraf?
Untuk keperluan tantangan ini, kita dapat menuliskan definisi yang sempit tapi tepat dari jaringan saraf (buatan). Untuk beberapa bacaan eksternal, saya sarankan Wikipedia pada jaringan saraf tiruan , jaringan saraf feedforward , multilayer perceptron , dan fungsi aktivasi .
Sebuah jaringan saraf feedforward adalah kumpulan lapisan neuron. Jumlah neuron per lapisan bervariasi, dengan 20 neuron pada lapisan input, sejumlah neuron dalam satu atau lebih lapisan tersembunyi, dan 1 neuron pada lapisan output. (Harus ada setidaknya satu lapisan tersembunyi karena bilangan prima dan bukan-bilangan prima tidak dapat dipisahkan secara linier sesuai dengan pola bitnya.) Dalam contoh dasar di atas, ukuran lapisan adalah [20, 82025, 1].
Nilai-nilai neuron input ditentukan oleh input. Seperti dijelaskan di atas, ini akan menjadi 0s dan 1s yang sesuai dengan bit-bit angka antara 0 dan 2 ^ 20, atau -1s dan +1 sama.
Nilai-nilai neuron dari setiap lapisan berikut, termasuk lapisan keluaran, ditentukan dari lapisan sebelumnya. Pertama fungsi linear diterapkan, dengan mode yang sepenuhnya terhubung atau padat . Salah satu metode untuk mewakili fungsi tersebut adalah menggunakan matriks bobot . Misalnya, transisi antara dua lapisan pertama garis dasar dapat direpresentasikan dengan matriks 82025 x 20. Jumlah bobot adalah jumlah entri dalam matriks ini, misalnya 1640500. Kemudian setiap entri memiliki istilah bias (terpisah) yang ditambahkan. Ini dapat diwakili oleh vektor, misalnya 82025 x 1 matriks dalam kasus kami. Jumlah bias adalah jumlah entri, misalnya 82025. (Perhatikan bahwa bobot dan bias secara bersama-sama menggambarkan fungsi linear affine .)
Bobot atau bias dihitung bahkan jika itu nol. Untuk keperluan definisi sempit ini, bias dihitung sebagai bobot walaupun semuanya nol. Perhatikan bahwa dalam contoh dasar, hanya dua bobot berbeda (+1 dan -1) yang digunakan (dan hanya bias yang sedikit lebih berbeda); Meskipun demikian, ukurannya lebih dari satu juta, karena pengulangan tidak membantu dengan skor dengan cara apa pun.
Akhirnya, fungsi nonlinier yang disebut fungsi aktivasi diterapkan secara bijak pada hasil fungsi linear affine ini. Untuk keperluan definisi sempit ini, fungsi aktivasi yang diizinkan adalah ReLU , tanh , dan sigmoid . Seluruh lapisan harus menggunakan fungsi aktivasi yang sama.
Dalam contoh dasar, jumlah bobot adalah 20 * 82025 + 82025 * 1 = 1722525 dan jumlah bias adalah 82025 + 1 = 82026, untuk skor total 1722525 + 82026 = 1804551. Sebagai contoh simbolis, jika ada satu layer lagi dan ukuran layer sebaliknya [20, a, b, 1], maka jumlah bobot akan menjadi 20 * a + a * b + b * 1 dan jumlah bias akan menjadi + b + 1.
Definisi jaringan saraf ini didukung dengan baik oleh banyak kerangka kerja, termasuk Keras , scikit-belajar , dan Tensorflow . Keras digunakan dalam contoh dasar di atas, dengan kode pada dasarnya sebagai berikut:
from keras.models import Sequential
model = Sequential()
from keras.layers import Dense
model.add(Dense(units=82025, activation='relu', input_dim=20, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
score = numpy.size(weights1) + numpy.size(biases1) + numpy.size(weights2) + numpy.size(biases2)
Jika bobot dan matriks bias adalah array numpy , maka numpy.size akan langsung memberi tahu Anda jumlah entri.
Apakah ada jenis lain dari jaringan saraf?
Jika Anda menginginkan definisi jaringan saraf tunggal dan skor yang tepat untuk tujuan tantangan ini, silakan gunakan definisi di bagian sebelumnya. Jika Anda berpikir bahwa "fungsi apa pun" memandang dengan cara yang benar adalah jaringan saraf tanpa parameter , maka silakan gunakan definisi di bagian sebelumnya.
Jika Anda semangat lebih bebas, maka saya mendorong Anda untuk mengeksplorasi lebih jauh. Mungkin jawaban Anda tidak akan diperhitungkan dalam tantangan sempit , tetapi mungkin Anda akan lebih bersenang-senang. Beberapa ide lain yang dapat Anda coba termasuk fungsi aktivasi yang lebih eksotis, jaringan saraf berulang (membaca sedikit demi sedikit), jaringan saraf convolutional, arsitektur yang lebih eksotis, softmax, dan LSTMs (!). Anda dapat menggunakan fungsi aktivasi standar dan arsitektur standar apa pun. Definisi liberal tentang fitur-fitur jaringan saraf "standar" dapat mencakup apa pun yang diposting di arxiv sebelum memposting pertanyaan ini.
Jawaban:
Pembagian percobaan: skor 59407, 6243 lapisan, total 16478 neuron
Diberikan sebagai program Python yang menghasilkan dan memvalidasi jaring. Lihat komentar di
trial_division
untuk penjelasan tentang cara kerjanya. Validasi cukup lambat (seperti dalam, waktu berjalan diukur dalam jam): Saya sarankan menggunakan PyPy atau Cython.Ambangnya adalah 1: apa pun di atas yang prima, apa pun di bawah ini adalah gabungan atau nol, dan satu-satunya input yang memberikan output 1 adalah 1 itu sendiri.
Sebagai tambahan, kembali
sumber
Skor 984314, 82027 lapisan, total 246076 neuron
Kita dapat menyimpan semuanya sepenuhnya dalam bilangan bulat jika kita menggunakan fungsi aktivasi ReLU, yang menyederhanakan analisis.
...
Layer 82026: keluaranmengakumulasi1048571= ( 221mengakumulasi1048559- ge1048571- le1048571+ 1 )+ , ge1048573= ( ge1048571- ( 1048573 - 1048571 ) )+ , le1048573= ( - ge1048571+ ( 1048573 - 1048571 ) )+ . Biaya (3 + 1) * 3 = 12.
Layer 82027: keluaranmengakumulasi1048573= ( 221mengakumulasi1048571- ge1048573- le1048573+ 1 )+ . Biaya (3 + 1) * 1 = 4.
Ambangnya adalah 0. Jika bekerja dengan ganda, limpahkan ke+ ∞ sangat mungkin, tetapi itu tampaknya sangat sesuai dengan aturan.
Skor adalah (82026 - 3) * 12 + 21 + 4 + 9 + 4.
sumber