Para peneliti selangkah lebih dekat untuk menambahkan proses probabilistik ke mesin deterministik
Masalah Perhitungan Jangka Panjang - Mensimulasikan Gulungan Dadu
Berikut adalah latihan yang tampaknya sederhana: Munculkan nomor telepon acak. Tujuh nomor berturut-turut, dipilih sehingga masing-masing memiliki kemungkinan yang sama, dan agar pilihan nomor berikutnya tidak memengaruhi pilihan nomor berikutnya. Kemungkinan besar, ini tidak akan berhasil untuk Anda. Anda tidak dapat mengambil kata-kata saya untuk itu - penelitian yang dilakukan sejak 1950-an menunjukkan bagaimana kita tidak acak dari sudut pandang matematika, bahkan tanpa menyadarinya.
Jangan kesal. Komputer juga tidak menghasilkan angka acak. Mereka seharusnya tidak - program dan perangkat keras komputer berjalan pada logika Boolean , bukan probabilitas. “Budaya komputer didasarkan pada determinisme,” kata Vikash Mansinhkayang menjalankan proyek komputasi probabilistik di MIT - dan ini muncul di hampir setiap level. "
Namun, programmer ingin membuat program yang berjalan dengan keacakan - terkadang tugas memerlukannya. Selama bertahun-tahun, algoritme cerdik telah dikembangkan yang, meski tidak menghasilkan angka acak, menawarkan cara yang cerdas dan efisien untuk menggunakan dan memanipulasi keacakan. Salah satu upaya terbaru telah dilakukan oleh grup Mansinkhee di MIT, yang akan mengungkap Fast Loaded Dice Roller , atau FLDR, pada konferensi AI dan statistik internasional pada bulan Agustus.
Secara sederhana, FLDR menggunakan urutan acak untuk secara sempurna mensimulasikan dadu curang (atau koin dengan bobot yang buruk, atau kartu yang ditandai). "Dia menunjukkan bagaimana mengubah lemparan koin yang acak sempurna menjadi yang terdistorsi," kata ahli matematika ituPeter Birhorst dari Universitas New Orleans. Birhorst tidak terlibat dalam penelitian ini, tetapi dia menganggap premis yang mendasari FLDR menjadi "menarik".
FLDR tidak akan memberi Anda keuntungan saat bermain Monopoli atau di meja dadu Las Vegas. Namun, penciptanya mengatakan itu memungkinkan nomor acak untuk diintegrasikan ke dalam perangkat lunak atau perangkat keras deterministik asli. Menyertakan ketidakpastian seperti itu akan membantu mesin membuat prediksi lebih seperti prediksi manusia dan lebih baik mensimulasikan peristiwa berdasarkan peluang, seperti iklim atau pasar keuangan.
Keacakan adalah konsep yang lebih kompleks daripada kedengarannya. Setiap digit dalam urutan digit acak, di mana tidak ada pola yang terlihat, kemungkinan kemunculannya sama. Misalnya, bilangan π tidak acak, tetapi menurut definisi ini nomornya acak (ahli matematika menyebutnya "normal"): setiap digit dari 0 hingga 9 muncul kira-kira dengan jumlah yang sama.
Dan meskipun Anda dapat menemukan "generator nomor acak" di Google, tidak akan ada peluang murni. Prosesor, mesin pencari, dan pembuat kata sandi saat ini menggunakan metode “pseudo-random” yang “cukup baik” untuk sebagian besar tugas. Angka dibuat menggunakan rumus kompleks - namun, secara teori, mengetahui rumus tersebut dapat memprediksi urutannya.
Para ilmuwan telah mencoba membuat keacakan nyata menjadi mesin selama setidaknya 80 tahun. Sampai saat itu, nomor acak diambil dari asisten tua dan andal - mereka melempar dadu, mengeluarkan bola dengan angka dari tas yang dicampur dengan baik, atau menggunakan perangkat mekanis lainnya. Pada tahun 1927, seorang ahli statistik mengambil sampel data sensus, menyusun tabel berisi 40.000 nomor acak.
Vikash Mansinkhka, Manajer Proyek Perhitungan Probabilistik di MIT
Sumber awal bilangan acak adalah mesin fisik. Generator nomor acak pertama ditemukan oleh ahli statistik Inggris Maurice George Kendall dan Bernard Babington Smith, yang mendeskripsikannya pada tahun 1938. Mereka meletakkan mobil di ruangan gelap, dan di sana ia memutar cakram, dibagi menjadi 10 sektor, diberi nomor dari 0 hingga 9. Ketika seseorang menekan tombol dengan interval yang tidak teratur, kilatan singkat neon atau percikan api menerangi cakram, mengambilnya dari kegelapan, tampaknya gambar beku di mana hanya satu nomor yang terlihat. Mesin selanjutnya, Ernie, menggunakan suara dalam tabung neon. Sejak 1957, dia telah memilih nomor pemenang dalam lotere Inggris.
Belakangan, dalam mencari urutan yang benar-benar acak, ilmuwan komputer, menurut Birhorst, harus beralih ke fenomena alam seperti radiasi relik atau sistem kuantum yang tidak dapat diprediksi. “Ada proses acak yang benar-benar tak terduga di alam yang dapat dieksploitasi,” katanya. "Sebuah elektron yang memantul ke kiri atau ke kanan tidak dapat menentukan sebelumnya apa yang akan dilakukannya."
Namun, kesempatan saja tidak akan membawa Anda jauh. Pada akhir 1940-an, fisikawan mulai menghasilkan bilangan acak yang sesuai dengan distribusi probabilitas tertentu. Alat semacam itu - versi teoretis dari kubus NOS - bekerja lebih tepat dalam situasi nyata, seperti kemacetan lalu lintas atau reaksi kimia. Pada tahun 1976, pelopor ilmu komputer Donald Knuth dan Andrew Yaomempresentasikan algoritma yang mampu menghasilkan sampel acak dari setiap larik hasil berbobot berdasarkan urutan bilangan acak. “Ini adalah algoritma paling efisien waktu yang dapat Anda pikirkan,” kata Fera Saad, seorang mahasiswa pascasarjana di lab Mansinkhka yang memimpin FLDR.
Sayangnya, kata Saad, algoritme tersebut membuat kompromi yang diketahui di antara ilmuwan komputer: banyak aplikasi yang berjalan cepat menggunakan banyak memori, dan aplikasi yang menggunakan sedikit memori dapat berjalan sangat lama. Algoritme Knuth dan Yao termasuk dalam kategori pertama, yang membuatnya elegan, tetapi terlalu intensif memori untuk penggunaan praktis.
Namun, Saad datang dengan langkah cerdas musim semi lalu. Dia menyadari bahwa jika jumlah bobot dari angka kubus sama dengan beberapa pangkat 2, algoritma tersebut ternyata efisien baik dalam memori maupun dalam waktu. Bayangkan bahwa untuk kubus bersisi enam, bobot 1, 2, 3, 4, 5, dan 1 ditambahkan ke probabilitas peluncuran angka dari 1 hingga 6. Artinya, probabilitas peluncuran 1 adalah 1/16 dan 2 adalah 2/16. Hasilnya, jumlah bobotnya adalah 16 - atau 2 4 - dan algoritme tersebut ternyata efisien baik dalam memori maupun waktu.
Fera Saad, mahasiswa PhD di MIT
Tapi katakanlah bobotnya adalah 1, 2, 3, 2, 4, 2, yang berjumlah 14. Karena 14 bukanlah pangkat 2, algoritme Knut-Yao akan membutuhkan lebih banyak memori secara signifikan. Saad menyadari bahwa ia dapat menambahkan bobot ekstra sehingga bobotnya selalu bertambah menjadi pangkat 2. Dalam hal ini, Anda dapat menambahkan wajah fiktif dengan bobot 2, lalu bobotnya bertambah menjadi 16. Jika algoritme memilih wajah asli, nilai ini akan dicatat. Jika ini fiktif, nilainya akan dibuang dan algoritme dimulai lagi.
Ini adalah kunci keefektifan FLDR, menjadikannya alat simulasi yang ampuh. Jumlah memori ekstra untuk lemparan ekstra dapat diabaikan dibandingkan dengan jumlah besar yang diperlukan dalam versi asli algoritme.
FLDR membuat algoritme Knuth-Yao efisien dan memberikan kesempatan untuk memperluas cakupannya. Simulasi perubahan iklim, prediksi tanaman, simulasi partikel, model pasar keuangan, dan ledakan nuklir bawah tanah semuanya bergantung pada angka acak yang didistribusikan dengan probabilitas tertimbang. Selain itu, nomor acak berada di jantung skema kriptografi yang melindungi data yang dikirimkan melalui Internet.
Mansinkhka mengatakan FLDR dapat membantu peneliti menemukan cara untuk mengintegrasikan probabilitas ke dalam prosesor komputer, laboratoriumnya di MIT melakukan ini. Algoritme dapat membantu meningkatkan pustaka perangkat lunak dan arsitektur prosesor baru yang dapat menghasilkan angka acak dan menggunakannya secara efisien. Ini akan menjadi perubahan signifikan dari mesin Boolean deterministik yang biasa kita gunakan.
“Kami mungkin memiliki peluang bagus untuk mengintegrasikan keacakan ke dalam blok bangunan perangkat lunak dan perangkat keras,” katanya.
Lihat juga: