Penjelasan sederhana tentang generator bilangan acak semu (PRNG) modern dan implementasi NumPy barunya

Saat membuat sampel bilangan yang berdistribusi normal, saya penasaran dari mana 'asalnya' - khususnya bagaimana komputer dapat membuat bilangan yang mengikuti distribusi pilihan apakah itu Normal, Eksponensial, atau sesuatu yang lebih funky. Apapun metode yang mendasari pembuatan nilai-nilai yang terdistribusi secara normal ini (“inversion sampling”, “Box-Muller” atau “algoritma Ziggurat” yang cepat), semuanya dimulai dengan satu blok penyusun fundamental: serangkaian nilai yang terdistribusi secara seragam.

Yang kemudian menimbulkan pertanyaan: dari mana asalnya? Dalam kebanyakan kasus: dari 'pembuat nomor acak semu' — atau PRNG. Setelah memperhatikan bahwa NumPy mengubah PRNG defaultnya pada Juli 2019 sebagai tanggapan terhadap NEP ini (meskipun internet masih dipenuhi dengan cara lama untuk melakukannya), saya sangat ingin memahami:

  • mengapa mereka mengubahnya
  • bagaimana cara kerja PRNG

dan kemudian menuliskan pemikiran saya dalam bahasa Inggris sederhana dengan beberapa bagan dan contoh kode yang berguna. Ini adalah catatan ini, sangat dipandu oleh makalah "ini" (yang cukup mudah diakses) dan ceramah terkait "ini" oleh Melissa O'Neill - penulis keluarga PRNG PCG pada tahun 2014 yang sekarang menjadi PRNG default di NumPy.

Mengapa 'semu'?

Karena menghasilkan keacakan yang sebenarnya itu sulit — baik bagi manusia (cobalah keberuntungan Anda di sini dan lihat bagaimana kinerja Anda) dan juga mesin. Jika kita menganggap mesin hanya mengambil input dan menghasilkan output sesuai dengan instruksi yang kita berikan, maka menurut definisi, output akan sama acaknya dengan input.

Ada beberapa cara untuk memastikan masukan ini 'benar-benar' acak yang sebagian besar melibatkan perangkat keras untuk mengukur hal-hal yang benar-benar acak dari alam (seperti kebisingan atmosfer), tetapi biasanya kami 'menyemai' algoritme dengan nilai awal yang dipilih (non-acak). Bahkan jika kita menggunakan waktu mesin (sebagai bilangan bulat) ketika generator dimulai sebagai benih, ini tidak 100% acak. Namun kita mungkin harus mempertanyakan apakah kita perlu mengejar keacakan yang sebenarnya.

Apakah kita menginginkan 'keacakan yang sebenarnya'?

Itu tergantung pada konteksnya. Jika kita menganggap keacakan sebagai kebalikan dari prediktabilitas, dan prediktabilitas sebagai musuh keamanan, maka akan lebih mudah untuk menjawab pertanyaan ini. Saat kita menggunakan angka acak untuk menghasilkan kunci yang digunakan untuk keamanan, misalnya kriptografi, maka kita ingin angka tersebut tampak acak mungkin untuk meminimalkan kemungkinan ancaman. Jadi dalam hal ini generator bilangan acak yang sebenarnya berguna.

Dalam kasus lain ketika menghasilkan simulasi, kita mungkin memiliki prioritas lain yang mengimbangi keinginan untuk mendapatkan prediktabilitas nol mutlak. Kami mungkin senang dengan fungsi yang meskipun sepenuhnya deterministik dan dapat diprediksi ketika Anda mengetahui nilai awalnya (atau urutannya cukup), tampak acak ketika Anda:

  • tidak tahu nilai awalnya
  • mengetahui 'cukup' urutannya tidak mungkin dalam praktiknya

Yang kemudian menimbulkan pertanyaan berikutnya:

Properti PRNG apa yang diinginkan?

Kecepatan, ukuran, dan kemampuan reproduksi

Tidak ada yang istimewa di sini — kami menginginkan sesuatu yang dapat menghasilkan angka acak dalam jumlah besar yang dapat direproduksi dengan cepat dan tanpa menghabiskan terlalu banyak memori, terutama jika kami berencana untuk menjalankan banyak angka acak di berbagai thread.

Keseragaman

Jika kita mengetahui bahwa angka acak yang dihasilkan akan berada pada interval [0, n] maka kita ingin setiap angka dalam interval tersebut memiliki peluang yang sama untuk terpilih - sebaliknya meskipun secara teoritis kita memiliki banyak angka untuk dipilih dalam praktiknya, ini akan jauh lebih kecil. Sebagai contoh jika kita mempunyai kemungkinan angka pada interval [0, 255] namun dalam praktiknya PRNG kita hanya memilih 3 atau 250 maka itu tidak terlalu acak sama sekali. Di sisi lain, kita belum tentu menginginkan algoritma yang menjamin keseragaman. Jika hal ini terjadi, maka jika kita mempunyai kisaran n angka untuk dipilih dan kita telah memilih n-1 angka, maka angka terakhirnya tidak acak sama sekali - itu hanyalah angka yang belum dipilih. Dengan bekerja mundur kita dapat melihat bahwa algoritma apa pun yang menjamin keseragaman akan berkurang secara acak ketika kita mencapai akhir rentang - yang juga dikenal sebagai 'periode'.

'Periode' yang panjang

Jika kita menerima bahwa agar komputer dapat menghasilkan suatu barisan, kita harus memberinya fungsi yang mengubah bilangan sebelumnya menjadi bilangan berikutnya, kemudian jika kita mendapatkan bilangan yang telah kita lihat sebelumnya, kita akan mulai mengulangi barisan tersebut. . Hal ini dijamin akan terjadi suatu saat selama kita memilih angka dari interval yang dibatasi karena jika kita memilih angka di [0, n] maka menurut definisi angka ke n+1 harus merupakan pengulangan dari angka sebelumnya. Dengan kata lain, pada urutan dengan ukuran yang sesuai semua PRNG akan diduplikasi dan menjadi deterministik. Untuk mencegah hal ini kita dapat membuat jumlah bilangan ('periode') sebelum hal ini terjadi jauh lebih besar daripada panjang barisan bilangan yang ingin kita sampel.

Kurangnya pola

Sepertinya sudah jelas tetapi layak untuk ditambahkan. Misalnya algoritma yang baik untuk memenuhi semua properti di atas adalah dengan 'menambahkan 1' saja:

yang mana yang akan:

  • sangat cepat, kecil, dan dapat direproduksi (kita hanya perlu mengetahui X_0 nilai awal kita)
  • seragam: setiap nomor dalam interval tertentu akan dipilih satu kali
  • jangka waktu lama: tidak akan pernah terulang selama kita tidak pernah 'membungkusnya' pada nilai tertentu untuk memastikan ukuran angka tidak terlalu besar, yaitu memetakan angka yang besar, y, kembali ke nol dan mulai lagi

Dengan kata lain, kondisi sebelumnya memberikan kemampuan bagi algoritma pseudo-random untuk muncul acak tetapi tidak menjamin hal tersebut — kita tetap membutuhkan algoritma yang baik dan kurang dapat diprediksi jika kondisi awalnya tidak diketahui.

Bit ini adalah kuncinya — semua PRNG akan bersifat deterministik jika Anda mengetahui 'keadaan' algoritme (misalnya, bilangan acak terakhir dan fungsi untuk mengonversinya ke bilangan acak berikutnya). Kuncinya adalah tanpa informasi tersebut, angka-angka tersebut akan tampak acak — seperti seekor kalkun yang berpikir bahwa Natal adalah ‘Angsa Hitam’, namun petani tidak (keacakan bergantung pada kumpulan informasi Anda).

LCG

Linear Congruential Generators (LCGs) adalah salah satu PRNG tertua dan untungnya cukup mudah dipahami.

Dengan kata lain — untuk mendapatkan angka berikutnya dalam barisan tersebut kita mengambil angka sebelumnya dan:

  • kalikan dengan konstanta a
  • tambahkan beberapa konstanta lain c ke dalamnya
  • ambil sisanya jika kita membaginya dengan konstanta lain m

Sejauh ini, tidak ada yang terlalu 'ilmu komputer-y' dengan kata-kata atau frasa menakutkan seperti 'pengulangan linier matriks' atau 'Mersenne prime'. Mari pilih beberapa nilai untuk {a, c, m} dan lihat seperti apa hasilnya.

Secara khusus mari kita bentuk generator dengan gaya generator Lehmer 1951 yang sangat sederhana - a=3, c=0 dan untuk memastikan kita menghasilkan angka 8-bit mari kita atur m=2^8=256. Bit terakhir ini berarti bahwa angka akan tetap berada di antara [0, 255] dan cocok dalam 8-bit.

3, 9, 27, 81, 243, 217, 139, 161, 227, 169, 251, 241, 211, 121, 107, 65, 195, 73, 219, 145, 179, 25, 75, 225, 163, 233, 187, 49, 147, 185, 43, 129, 131, 137, 155, 209, 115, 89, 11, 33, 99, 41, 123, 113, 83, 249, 235, 193, 67, 201, 91, 17, 51, 153, 203, 97, 35, 105, 59, 177, 19, 57, 171, 1, 3, 9, 27, 81, 243, 217, 139, 161, 227, 169, 251, 241, 211, 121, 107, 65, 195, 73, 219, 145, 179, 25, 75, 225, 163, 233, 187, 49, 147, 185, 43, 129, 131, 137, 155, 209

Jadi masalah apa yang sudah kita lihat?

  • semua angkanya ganjil sehingga kita tidak menyentuh semua angka secara seragam (pola apa pun yang dapat diamati merupakan antitesis dari keacakan)
  • periodenya singkat - Anda dapat melihat sekitar setengah jalan, kita kembali ke awal dan kemudian mulai mengulanginya

Jika LCG sangat buruk, apakah ini relevan dengan PRNG saat ini?

Karena LCG tidak buruk. LCG di atas sangat buruk, tetapi hal ini tidak ada hubungannya dengan LCG sebagai kelompok penghasil angka itu sendiri dan lebih berkaitan dengan cara kita membuat parameter LCG tersebut. Faktanya, LCG berikut disebut drand48 dan mendasari java.util.Random:

namun memiliki perbedaan krusial dengan spesifikasi LCG di atas.

Jangan hanya menampilkan 'status', tetapi fungsinya

Pada contoh pertama kita baru saja membuat nomor berikutnya dalam urutan dan mengeluarkannya. Jika 255, maka angka berikutnya dalam barisan kita adalah 255. Tidak ada urusan yang lucu. Dalam implementasi LCG di atas, hal ini tidak terjadi - kami memiliki yield seed >> 16 berikut. Dalam python, ini adalah operator bitwise yang menggeser semua bit 16 tempat ke kanan sehingga 16-bit paling kanan dihilangkan sebagai hasilnya.

Kita dapat mengambil contoh di sini - jika kita memiliki angka 1017 kita dapat menyatakannya dalam biner sebagai 11 1111 1001 (spasi hanya untuk kemudahan membaca) - jika kita melakukan 1017 >> 3 maka kita akan mendapatkan 111 1111 (yaitu 127) yaitu kita menggeser semuanya ke di sebelah kanan sebanyak 3 tempat dan letakkan 3 bit pertama di sebelah kanan. Ini hanyalah salah satu jenis fungsi yang menggambarkan cara untuk meningkatkan keluaran kita. Kami sekarang memiliki pengaturan berikut untuk algoritma LCG kami:

  • menghasilkan nomor berikutnya dalam urutan - ini adalah 'keadaan' LCG (hanya terminologi)
  • gunakan 'keadaan' itu untuk menghasilkan 'keluaran' — ini adalah angka yang kemudian digunakan untuk membentuk bagian dari barisan

Ini adalah bagaimana kita dapat memiliki 'generator 16-bit' dengan 'keluaran 8-bit' — karena 'keadaan' generator adalah bilangan 16-bit tetapi keluarannya adalah bilangan 8-bit yang mana 8-bit tersebut nomor dibuat dengan menerapkan beberapa fungsi ke keadaan 16-bit. Seperti yang akan kita lihat, pembuatan PRNG dengan keluaran yang berbeda dari negara bagian dapat meningkatkan sifat statistiknya secara drastis.

Randograms: memvisualisasikan keacakan

Untuk mendapatkan intuisi tentang betapa acaknya berbagai algoritma, kita memerlukan cara untuk memvisualisasikan keacakan ini. Untuk melakukan ini kita akan kembali meminjam ide dari “makalah oleh Melissa O’Neill”. Dalam praktiknya, generator bilangan acak jauh lebih besar daripada apa yang akan kita lakukan (keadaan 64-bit dengan keluaran 32-bit) namun berikut adalah idenya:

  • buat generator dengan status 16-bit yaitu seed/status berada di kisaran[0, 65535] (dimana batas atasnya adalah 2**16-1)
  • mengeluarkan angka 8-bit yang berasal dari keadaan 16-bit tersebut — yaitu setiap angka dalam urutan keluaran akan berada di [0, 255]
  • ambil barisan tersebut dan kelompokkan titik-titik yang berdekatan menjadi berpasangan yaitu [x_0, x_1], [x_2, x_3], etc
  • pasangan ini membentuk koordinat {x, y} dalam plot 256 x 256
  • gunakan PRNG untuk menghasilkan 2^16 koordinat dan plot mereka di mana jika kita tidak memiliki pasangan untuk koordinat maka koordinat tersebut berwarna putih dan semakin banyak pasangan yang kita miliki pada koordinat tertentu, semakin banyak koordinat hitam yang akan menjadi

Di satu sisi, ini akan memberi kita gambaran bagus tentang keacakan. Jika kita memiliki algoritme yang baik, kita akan memiliki plot dengan banyak titik yang secara keseluruhan terlihat acak. Ini akan lebih mudah dilihat dengan sebuah contoh. Mari kita ambil parameter “keadaan 16-bit, LCG keluaran 8-bit” dan menggambar beberapa 'randogram'.

Bagan kiri atas menunjukkan apa yang kita dapatkan ketika kita mengambil 8-bit paling kanan dari nomor keadaan 16-bit. Misalnya, jika 'status' kita untuk suatu iterasi adalah angka 65413 yang direpresentasikan dalam biner sebagai 1111 1111 1000 0101, maka kita akan menampilkan 8 bit paling kanan - 1000 0101 (atau 133). Kami melakukan ini untuk semua nomor, mengelompokkannya sebagai pasangan dan memplotnya.

Kita dapat melihat bahwa angka-angkanya tidak tampak acak sama sekali — mereka membentuk garis lurus yang rapi. Ini adalah Teorema Marsaglia dan menunjukkan masalah pada LCG ketika kita memiliki periode yang terlalu kecil (dan sebagainya dapatkan nilai berulang seperti ini). Namun, ketika kita naik ke tingkat yang lebih tinggi, keadaan 16-bit mulai terlihat sedikit lebih baik. Masih ada struktur yang jelas di grafik kanan bawah, namun kami melakukannya jauh lebih baik dalam hal menutupi ruang.

Jadi ketika melihat hal ini kita dapat melakukan pengamatan berikut: semakin tinggi kelompok 8-bit dalam bilangan keadaan 16-bit yang dihasilkan oleh LCG, semakin terlihat acak.

Masukkan PCG

Meskipun LCG masih banyak digunakan secara praktis, LCG bukanlah PRNG default untuk NumPy sebelum tahun 2019. Sebaliknya, sebelum NumPy 1.17, algoritma yang disebut Mersenne Twister digunakan — khususnya MT19937 — dinamai karena panjang periodenya (yang sangat besar) menjadi Mersenne Prime (2**19937 - 1 - pangkat 2 dikurangi 1). Namun dengan rilis 1.17 NumPy, PRNG dialihkan menjadi PRNG default menjadi PCG - Permuted (Linear) Kongruential Generator.

PCG adalah rangkaian generator yang dibuat oleh Melissa O'Neill yang memanfaatkan pengamatan di atas dengan cerdas — terutama grafik. Idenya adalah ini:

  • mengeluarkan fungsi negara, bukan negara secara langsung, tampaknya meningkatkan keacakan
  • LCG jelas kurang memiliki keacakan pada bit yang lebih rendah (grafik kiri atas), namun bit yang lebih tinggi cenderung 'lebih acak' (grafik kanan bawah)
  • jika kita punya mis. keadaan 16-bit yang mengeluarkan angka 8-bit, maka kita hanya perlu memilih 8 bit untuk dikeluarkan
  • mengapa kita tidak menggunakan beberapa bit teratas dari keadaan 16-bit, yang paling acak, untuk memilih fungsi mana yang kita terapkan pada sisa keadaan 16-bit untuk menghasilkan keluaran 8-bit
  • dengan kata lain, mari kita gunakan bagian paling acak dari negara kita untuk secara acak memilih fungsi transformasi untuk diterapkan ke negara bagian lainnya - semacam algoritma acak

Mari kita lihat contoh sederhana.

PCG RS

9 bagan di atas melakukan hal berikut: menghitung keluaran 8-bit dari keadaan 16-bit di mana keluaran 8-bit tersebut dihasilkan oleh pergeseran bit yang telah ditentukan sebelumnya (0 untuk kiri atas hingga 8 untuk kanan bawah ). Namun bagaimana dengan pergeseran tetap, melainkan pergeseran acak?

Dari mana kita mendapatkan keacakan itu? Dari beberapa bit teratas dari status 16-bit kami. Dengan kata lain, jika kita mempunyai keadaan 57277 (1101 1111 1011 1101) kita dapat:

  • gunakan 2 bit teratas, 11, untuk menentukan pergeseran - dalam hal ini 3
  • terapkan pergeseran ini ke bit lainnya, 01 1111 1011 1101 s.t. alih-alih memilih 8 bit paling kiri, 0111 1110, kita menggeser 3 bit ke kanan dan memilih bit 1111 0111

Apa yang kita lakukan ketika melihat 9 grafik di atas adalah menggunakan keacakan plot 8–15, 9–16 untuk memilih secara acak apakah kita memilih nomor dari plot {4-11} - {7-14}. Mari kita lihat tampilannya:

Jelas masih ada beberapa struktur di sana tetapi peningkatannya sangat besar hanya dengan mengambil 2 bit teratas dari keadaan 16-bit dan menggunakannya untuk memilih permutasi ke keadaan lainnya — oleh karena itu dinamakan Generator Kongruensial Permuted (Linear). Tapi ini hanyalah salah satu transformasi — sedikit perubahan.

Bagaimana dengan transformasi lainnya? Ada sejumlah transformasi yang tersedia (xor, rotasi, dll) yang membuat keluarga PCG di mana bit teratas secara acak memilih permutasi mana yang akan diterapkan ke keadaan yang dihasilkan secara linier. Mari kita lihat 2 permutasi lain yang dapat digunakan.

Rotasi

Salah satu transformasi yang dapat kita pilih (secara acak) adalah 'rotasi' bit. Sama seperti sebelumnya dengan operator >> kita menggeser bit ke kanan dan menghilangkan overflow, dengan rotasi kita menggeser satu arah tetapi bukannya menghilangkan overflow kita membawanya ke sisi yang lain.

Jika kita mempunyai bilangan 113, yang direpresentasikan dalam biner sebagai 111 0001, kita dapat melakukan 'rotasi ke kanan' pada 2 untuk membuat 011 1100, atau 60. Di sini kita telah mengambil 2 bit paling kanan (01) dan memutarnya ke awal dan menggeser semuanya ke bawah.

xorshift

Transformasi lain yang bisa kita terapkan adalah 'xorshift'. Sekali lagi, mari kita ilustrasikan dengan contoh yang sama. Sekali lagi mengambil 113 (111 0001) kita dapat:

  • 'menggesernya' ke bawah dengan jumlah mis. 2 untuk mendapatkan 001 1100
  • terapkan fungsi bitwise eksklusif atau ke nomor asli dan nomor yang digeser

Dalam hal ini kita akan menghitung xor (atau ^ dengan python) pada 111 0001 dan 001 1100 untuk mendapatkan 110 1101 (1s ketika hanya 1-bit adalah 1, 0 jika keduanya 1 atau 0).

PCG XSH-RS & PCG XSH-RR

Sekarang mari kita lihat randogram untuk 2 PCG umum dan lihat perbandingannya dengan di atas. Mereka:

  • PCG XSH-RS: pertama-tama hitung operasi xorshift, lalu shift bit yang dihasilkan secara acak
  • PCG XSH-RR: pertama-tama hitung operasi xorshift, lalu putar bit yang dihasilkan secara acak

Sekali lagi, strukturnya masih ada, namun ada kemajuan yang nyata. Struktur ini ada karena kami menggunakan generator ‘kecil’. Sama seperti 8-bit teratas lebih acak daripada 8-bit terbawah dalam keadaan 16-bit, 16-bit teratas lebih acak daripada 8-bit terbawah dalam keadaan 32-bit. Juga saat kita menggunakan keadaan yang semakin besar, kita secara alami menambah periodenya. Menggabungkan kedua hal ini adalah alasan mengapa LCG yang sangat besar (keadaan 96-bit, keluaran 32-bit) dapat melewati Big Crush— serangkaian uji statistik ekstensif yang dikemas oleh Pierre L'Ecuyer dan Richard Simard akan menguji PRNG untuk mengetahui sifat-sifat yang diinginkan yang disebutkan sebelumnya.

Mengingat keacakan tambahan dari permutasi yang dipilih secara acak, kinerja PCG jauh lebih baik daripada LCG dan sebagai hasilnya tidak memerlukan negara bagian yang besar untuk lulus rangkaian pengujian. Karena alasan inilah mereka diadopsi sebagai PRNG default di NumPy — dengan “algoritma yang tepat” adalah PCG XSL RR 128/64.