bandit

crossroads
awas salah ngasih tahu abang gojeknya belok kiri atau kanan

Pembukaan

Pernahkah Anda berada dalam keadaan harus memilih di antara 2 pilihan, di mana pilihan yang Anda ambil itu dapat mengubah kehidupan Anda secara drastis?

Saya pernah dan hampir mengalaminya setiap hari. Setiap pulang dari kantor saya selalu dihadapkan pilihan untuk naik bis atau naik busway. Skenario pertama adalah saya langsung dapat bus dan sampai rumah dengan cepat. Skenario kedua saya langsung dapat busway, sampai rumah lumayan cepat tapi lebih capek karena harus berdiri. Skenario terburuk adalah menunggu bus, bus tidak lewat dalam waktu satu jam, Kemudian jadinya menunggu busway, tapi kemudian bisnya malah lewat di depan mata, akhirnya baru dapat busway 30 menit kemudian, itu pun berdiri hingga 1.5 jam karena jalan macet…

Efeknya tentunya sangat berpengaruh. Kalau saya dapat opsi yang pertama, maka saya bisa sampai rumah dengan waktu yang relatif lebih cepat, badan tidak terlalu capek, dan mungkin malamnya bisa produktif sedikit seperti untuk menulis blog atau belajar hal baru dengan menonton video online course.

Bandingkan dengan opsi terakhir yang mana saya sampai rumah larut malam dan kehabisan tenaga sehingga saya hanya bisa menghabiskan waktu dengan menonton video pewdiepie di youtube atau main hearthstone tanpa mikir.

Bandit algorithm

Joking aside, contoh kisah nyata di atas hanyalah ilustrasi belaka untuk menggambarkan suatu kelas masalah yang di matematika dikenal dengan nama bandit algorithm. Bandit algorithm ini namanya terinspirasi dari mesin slot yang ada di kasino2.

Las_Vegas_slot_machines
hati-hati judi dapat meracuni kehidupan, kata bang roma

Penjelasan resminya dari algoritma bandit kira-kira seperti berikut. Pada setiap turn kita memiliki beberapa opsi yang bisa dipilih. Masing-masing opsi akan memberikan reward/hadiah dengan jumlah yang kita belum ketahui sebelumnya. Tugas kita adalah memaksimalkan total reward yang kita dapatkan dari awal pilihan pertama hingga pilihan terakhir. Terdengarnya susah-susah gampang bukan?

Ada juga yang mengklasifikasikan algoritma bandit ini ke dalam special case dari reinforcement learning (RL yang tidak memiliki states). Kalau penasaran, lebih lanjutnya bisa cek chapter 1 dari buku Reinforcement Learning-nya Sutton & Barto.

Implementasi

Untuk mengetes performa dari algoritma2 yang akan kita coba, pertama kita generate terlebih dahulu 2000 simulasi yang masing-masing memiliki distribusi reward yang berbeda-beda. Simulasi ini akan kita jalankan selama 1000 putaran. Contoh salah satu distribusinya adalah sebagai berikut:

distribution
option 3 dan 4 punya reward yg relatif lebih besar dari pilihan lainnya, tapi kita tidak tahu informasi itu di awal

Apa strategi pertama yang bisa kita coba? Pure random. Di tiap turn kita pilih saja opsi terserah yang mana saja. Kalau misalkan random saja sudah bagus, ngapain mikirin algoritma lain yang lebih rumit?

random bandit

Ternyata kalau random, rata2 reward yg kita dapat untuk masing-masing putaran berkisar di angka 0. Weks, jelek sekali performanya.

Bagaimana kalau kita bersifat serakah (greedy), jadi kita hanya memilih opsi yang selama ini memberikan rata2 reward paling tinggi?

greedy bandit

Lumayan, hasilnya secara rata-rata lebih bagus dari random (1, bukan 0). Kekurangannya adalah, karena sifatnya yang greedy, begitu kita memilih opsi yang memberikan nilai positif, maka kita bakal terus-terusan memilih opsi tersebut. Padahal di luar sana mungkin ada pilihan yg bisa menghasilkan reward yang lebih tinggi.

Untuk mengatasi hal tersebut, kita harus bisa menyeimbangkan antara exploitation (mengumpulkan reward sebanyak-banyaknya dengan memilih opsi yang pasti memberikan hasil bagus) dengan exploration (mencari opsi yang mungkin memberikan hasil yang lebih bagus lagi). Salah satu strategi yang bisa dipakai adalah e(epsilon)-greedy. Jadi pada setiap turn, kita punya peluang sebesar e untuk memilih opsi lain secara random. Nilai e ini sendiri jelas harus dipilih secara bijak, karena kalau terlalu kecil maka kita bisa terjebak di pilihan yang tidak optimal, tapi kalau terlalu besar maka kita akan melewatkan terlalu banyak kesempatan untuk mendapat reward yang pasti besar, sehingga secara kumulatif total reward yang kita kumpulkan bisa lebih kecil.

Implementasi-nya kira-kira seperti berikut:

greedy bandit code

egreedy bandit

Wow, sekarang kita bisa mendapatkan nilai dari 1.2 hingga 1.4, tergantung nilai e yg kita pilih.

Now can we do even better than that? Tentu saja. Perhatikan, pada strategy e-greedy, pada saat kita melakukan eksplorasi, kita memilih opsi secara random, tidak peduli terhadap performanya yang sebelumnya. Bagaimana kalau misalkan kita pilih suatu opsi berdasarkan rata-rata performanya sekarang dan yang paling sedikit dipilih sejak saat ini. Motivasinya adalah opsi yang jarang dipilih bisa jadi memiliki potensi memberikan reward besar yang belum terealisasikan.

Strategi ini bernama Upper Confidence Bound (UCB). Untuk derivasi lengkapnya, bisa diintip di blog-nya bang Jeremy Kun. Implementasinya kira-kira seperti ini:

ucb bandit code

Dan hasilnya ternyata memang paling bagus di antara algoritma-algoritma sebelumnya, hingga 1.5!.

ucb bandit

Dan ini adalah perbandingan semua algoritma yang sudah disebut di atas. UCB memiliki nilai paling tinggi dan paling cepat juga mencapai nilai tersebut.

bandit full

Penutup

Apa aplikasi langsung yang bisa dicoba dengan menggunakan teknik ini? Misalkan kamu mau mengoptimisasi conversion rate dari sebuah website dengan mencoba beberapa versi dari landing page-nya. Conventional wisdom-nya adalah kita lakukan A/B test untuk mengetahui varian mana yang performanya paling bagus. Nah, tapi seringkali A/B test ini harus dilakukan dalam jangka waktu yang lumayan lama dengan agar jumlah sampelnya cukup secara statistik. Dengan menjalankan A/B test ini, kita kehilangan potensi untuk menghasilkan reward karena sebagian user akan mendapat varian yang mungkin secara performa lebih buruk daripada yang lainnya.

Nah, kalau misalkan kita formulasikan ini sebagai problem bandit dengan menggunakan algoritma UCB misalnya, maka sistem akan secara otomatis meng-assign user ke varian yang mempunyai performa yang paling bagus. Tanpa harus menunggu A/B test-nya selesai sehingga total cumulative reward yang dikumpulkan di akhir jauh lebih tinggi.

Lalu apakah dengan adanya bandit algorithm maka A/B testing jadi obsolete? Tentu saja tidak, karena keduanya memiliki tujuan yang berbeda. Berikut wejangan dari om Chris Stucchio.

conclusions

File eksperimen di atas bisa ditemukan di link berikut: https://github.com/mitbal/sidu/blob/master/bandit.ipynb

Selamat mencoba. Semoga berguna. Salam.

Iklan

data driven

datadriven2

Beberapa saat yang lalu di salah satu saluran komunikasi kantor saya, terjadi perdebatan seru mengenai data driven company. Diskusi berkisar di definisi data-driven itu sendiri, apa manfaatnya, kenapa kita harus menjadi data-driven, dan bagaimana agar bisa menjadi data-driven company.

Sebelum kita membahas lebih lanjut mengenai data-driven, tentunya lebih baik untuk menyamakan persepsi terlebih dahulu mengenai definisi data-driven itu sendiri, karena tentunya masing-masing mempunyai definisinya sendiri. Berdasarkan Google (yang mengambil dari wikipedia), definisinya adalah sebagai berikut.

datadrivenyang kalau diterjemahkan secara bebas kurang lebih berarti mengambil keputusan berdasarkan data, bukan berdasarkan perasaan atau hanya mengikuti keputusan dari atasan atau orang yang kedudukannya lebih tinggi. Kalau ada sesuatu yang hendak diputuskan, terlebih dahulu cari data atau lakukan eksperimen.

Dalam konteks technology company, biasanya data-driven diwujudkan dalam bentuk A/B testing. Misalkan kita ingin tahu apakah tombol berwarna merah atau hijau yang lebih meningkatkan sales. Kita bagi dua saja dua saja traffic yang masuk ke 2 versi website dengan warna tombol yang berbeda. Setelah terkumpul jumlah sampel yang cukup, kita lakukan statistical test dan lihat versi mana yang lebih bagus. Bukan langsung memilih warna merah karena itu warna kesukaan boss kita.

Namun menurut saya sendiri, definisi data-driven yang paling pas itu yang diinspirasi dari bayesian method.

posterior belief is proportional to prior belief times likelihood.

Jadi keputusan yang kita ambil jadinya adalah kombinasi dari prior belief kita, hal yang kita sendiri percayai tanpa melihat data terlebih dahulu (walaupun sebenarnya ini adalah bentuk internalisasi semua kumpulan data yang pernah kita alami sebelumnya), kemudian di-update dengan hasil atau data terbaru yang sesungguhnya terjadi.

Bagaimana prakteknya? Mari kita ambil contoh Zlatan Ibrahimovic yang kini membela Manchester United.

ibrahimovic-ke-mu-730x480_c
Zlatan dengan kaus MU

Prior belief itu berguna agar kita tidak terlalu cepat mengambil kesimpulan dengan hasil/data yang masih sedikit. Kalau tanpa prior dan kita mengamati Zlatan tidak mencetak gol dalam 3 pertandingan terakhir, maka keputusan yang diambil adalah kita tidak memainkannya kembali untuk pertandingan berikutnya. Padahal kalau kita lihat rekam jejaknya, Ibra bisa mencetak di lebih dari 30 pertandingan sepanjang musim. Dengan prior belief ini seharusnya kita tetap memainkan Zlatan untuk pertandingan berikutnya.

Nah, tapi kalau misalkan hingga 35 pertandingan ternyata Zlatan tidak bisa mencetak gol sama sekali, maka kita sudah mempunyai observasi atau data yang cukup (the likelihood term). Maka keputusan yang tepat mungkin adalah tidak memainkan Ibra kembali.

(Untuk yang familiar dengan teknisnya, kita bisa modelkan peluang Zlatan mencetak gol diambil dari binomial distribution, dan memiliki conjugate prior beta distribution dengan alpha dan beta bisa diambil dengan jumlah pertandingan yang di mana Zlatan mencetak gol di musim sebelumnya) .

(Ini hanyalah contoh belaka, bukan jinx. Penulis sangat berharap Zlatan bisa mencetak banyak gol sehingga MU bisa meraih gelar juara Liga Premier musim ini dan Liga Champion musim depan. GGMU)

Bagaimana contohnya di kehidupan nyata? Misalkan kita mau pasang iklan di berbagai website untuk mempromosikan produk kita. Berdasarkan data dari similarweb kita tahu website mana saja yang mempunyai traffic tinggi. Kita kemudian bisa memasang di beberapa website yang memiliki traffic tinggi. Akan tetapi, setelah beberapa saat kita bisa evaluasi iklan dari website mana yang sebenarnya berhasil meningkatkan metrik penjualan kita. Kira-kira begitu.

Happy data-driving.