Penelusuran acak acak

Unit ini berfokus pada penelusuran kuasi-acak.

Mengapa menggunakan penelusuran kuasi-random?

Penelusuran kuasi-acak (berdasarkan urutan perbedaan rendah) adalah preferensi kami dibandingkan alat pengoptimalan kotak hitam yang lebih bagus saat digunakan sebagai bagian dari proses penyesuaian iteratif yang dimaksudkan untuk memaksimalkan insight tentang masalah penyesuaian (apa yang kami sebut sebagai "fase eksplorasi"). Pengoptimalan Bayes dan alat serupa lebih sesuai untuk fase eksploitasi. Penelusuran kuasi-acak berdasarkan urutan perbedaan rendah yang bergeser secara acak dapat dianggap sebagai "penelusuran petak yang diacak dan diacak", karena penelusuran ini secara seragam, tetapi secara acak, menjelajahi ruang penelusuran tertentu dan menyebarkan titik penelusuran lebih banyak daripada penelusuran acak.

Keuntungan penelusuran kuasi-acak dibandingkan alat pengoptimalan kotak hitam yang lebih canggih (misalnya pengoptimalan Bayesian, algoritma evolusioner) mencakup:

  • Pengambilan sampel ruang penelusuran secara non-adaptasi memungkinkan Anda mengubah tujuan penyesuaian dalam analisis post-hoc tanpa menjalankan kembali eksperimen. Misalnya, kita biasanya ingin mencari uji coba terbaik dalam hal error validasi yang dicapai kapan saja dalam pelatihan. Namun, sifat non-adaptif penelusuran kuasi-acak memungkinkan untuk menemukan uji coba terbaik berdasarkan error validasi akhir, error pelatihan, atau beberapa metrik evaluasi alternatif tanpa menjalankan kembali eksperimen apa pun.
  • Penelusuran kuasi-acak berperilaku konsisten dan dapat direproduksi secara statistik. Seharusnya studi dari enam bulan lalu dapat direproduksi meskipun implementasi algoritma penelusuran berubah, selama studi tersebut mempertahankan properti keseragaman yang sama. Jika menggunakan software pengoptimalan Bayesian yang canggih, penerapan dapat berubah secara penting antar-versi, sehingga makin sulit untuk mereproduksi penelusuran lama. Roll back ke implementasi lama tidak selalu dapat dilakukan (misalnya, jika alat pengoptimalan dijalankan sebagai layanan).
  • Eksplorasinya yang seragam terhadap ruang penelusuran mempermudah pertimbangan tentang hasil dan saran yang mungkin disarankan tentang ruang penelusuran. Misalnya, jika titik terbaik dalam traversal penelusuran kuasi-acak berada di batas ruang penelusuran, ini adalah sinyal yang baik (tetapi tidak terjamin) bahwa batas ruang penelusuran harus diubah. Namun, algoritma pengoptimalan kotak hitam adaptif mungkin telah mengabaikan bagian tengah ruang penelusuran karena beberapa uji coba awal yang kurang beruntung meskipun kebetulan berisi poin yang sama baiknya, karena ketidakseragaman inilah yang perlu digunakan oleh algoritma pengoptimalan yang baik untuk mempercepat penelusuran.
  • Menjalankan jumlah uji coba yang berbeda secara paralel dan berurutan tidak memberikan hasil yang berbeda secara statistik saat menggunakan penelusuran kuasi-acak (atau algoritma penelusuran non-adaptif lainnya), tidak seperti algoritma adaptif.
  • Algoritma penelusuran yang lebih canggih mungkin tidak selalu menangani titik yang tidak masuk akal dengan benar, terutama jika tidak dirancang dengan mempertimbangkan penyesuaian hyperparameter jaringan neural.
  • Penelusuran kuasi-acak sederhana dan berfungsi dengan baik terutama saat banyak uji coba tuning yang berjalan secara paralel. Secara anekdot1, sangat sulit bagi algoritma adaptif untuk mengalahkan penelusuran semu-acak yang memiliki anggaran 2X lipat, terutama ketika banyak uji coba perlu dijalankan secara paralel (sehingga sangat sedikit peluang untuk menggunakan hasil uji coba sebelumnya saat meluncurkan uji coba baru). Tanpa keahlian dalam pengoptimalan Bayesian dan metode pengoptimalan blackbox lanjutan lainnya, Anda mungkin tidak akan mendapatkan manfaat yang, pada prinsipnya, dapat diberikan olehnya. Sangat sulit untuk membandingkan algoritma pengoptimalan blackbox lanjutan dalam kondisi penyesuaian deep learning yang realistis. Algoritma ini adalah bidang riset yang sangat aktif, dan algoritma yang lebih canggih memiliki kelemahannya sendiri bagi pengguna yang tidak berpengalaman. Pakar dalam metode ini dapat memperoleh hasil yang bagus, tetapi dalam kondisi paralelisme tinggi, ruang penelusuran dan anggaran cenderung lebih penting.

Meskipun demikian, jika resource komputasi Anda hanya mengizinkan sejumlah kecil uji coba untuk dijalankan secara paralel dan Anda mampu menjalankan banyak uji coba secara berurutan, pengoptimalan Bayesian akan menjadi jauh lebih menarik meskipun membuat hasil penyesuaian Anda lebih sulit ditafsirkan.

Open-Source Vizier memiliki implementasi penelusuran kuasi-acak. Tetapkan algorithm="QUASI_RANDOM_SEARCH" dalam contoh penggunaan Vizier ini. Implementasi alternatif ada dalam contoh sweep hyperparameter ini. Kedua implementasi ini menghasilkan urutan Halton untuk ruang penelusuran tertentu (dimaksudkan untuk menerapkan urutan Halton yang digeser dan diacak seperti yang direkomendasikan dalam Critical Hyper-Parameters: No Random, No Cry.

Jika algoritma penelusuran kuasi-acak yang didasarkan pada urutan perbedaan rendah tidak tersedia, penelusuran seragam acak pseudo-random dapat diganti, meskipun hal ini kemungkinan akan sedikit kurang efisien. Pada 1-2 dimensi, penelusuran petak juga dapat diterima, meskipun tidak untuk dimensi yang lebih tinggi. (Lihat Bergstra & Bengio, 2012).

Berapa banyak uji coba yang diperlukan untuk mendapatkan hasil yang baik dengan penelusuran kuasi-acak?

Tidak ada cara untuk menentukan berapa banyak uji coba yang diperlukan guna mendapatkan hasil dengan penelusuran kuasi-acak secara umum, tetapi Anda dapat melihat contoh spesifik. Seperti yang ditunjukkan oleh Gambar 3, jumlah uji coba dalam sebuah studi dapat berdampak besar pada hasil:

Diagram kotak rasio error validasi (sumbu y) vs. anggaran penyesuaian (sumbu x), dengan anggaran penyesuaian adalah jumlah uji coba. Rata-rata rasio error validasi umumnya turun seiring dengan meningkatnya anggaran penyesuaian.

Gambar 3: ResNet-50 yang di-tuning di ImageNet dengan 100 uji coba. Dengan menggunakan bootstrap, jumlah penyesuaian anggaran yang berbeda disimulasikan. Box plot dari performa terbaik untuk setiap anggaran uji coba diplot.

 

Perhatikan hal-hal berikut tentang Gambar 3:

  • Rentang interkuartil saat 6 uji coba diambil sampelnya jauh lebih besar daripada saat 20 uji coba diambil sampelnya.
  • Bahkan dengan 20 uji coba, perbedaan antara studi yang sangat beruntung dan tidak beruntung kemungkinan lebih besar daripada variasi umum antara melatih ulang model ini pada seed acak yang berbeda, dengan hyperparameter tetap, yang untuk beban kerja ini mungkin sekitar +/- 0,1% pada tingkat error validasi sebesar ~23%.

  1. Ben Recht dan Kevin Jamieson menunjukkan seberapa kuat penelusuran acak anggaran 2X sebagai dasar pengukuran (makalah Hyperband membuat argumen serupa), tetapi tentu saja mungkin untuk menemukan ruang penelusuran dan masalah ketika teknik pengoptimalan Bayesian yang canggih menghancurkan penelusuran acak yang memiliki anggaran 2X lipat. Namun, dalam pengalaman kami, mengalahkan penelusuran acak beranggaran 2X menjadi jauh lebih sulit dalam rezim paralelisme tinggi karena pengoptimalan Bayes tidak memiliki kesempatan untuk mengamati hasil uji coba sebelumnya. ↩

Sebelumnya
Kecepatan pembelajaran
Berikutnya
FAQ