Algoritma Baru Memotong Waktu Komputasi berdasarkan Besaran

• Algoritme baru secara eksponensial mempercepat komputasi dengan mengurangi secara drastis jumlah iterasi yang diperlukan untuk menyelesaikan suatu masalah.
• Performanya jauh lebih baik dibandingkan algoritme konvensional (berurutan) pada kumpulan data skala besar, seperti analisis media sosial dan pengelompokan data genetik. 

Ribuan masalah optimasi (masalah menemukan solusi terbaik dari semua solusi yang layak) seperti mengalokasikan dana ke saham untuk meminimalkan risiko pengembalian, atau menugaskan karyawan ke kantor yang tersedia untuk memaksimalkan alur kerja dan ahli statistik karyawan, sangat bergantung pada algoritma sekuensial.

Pola kerja dasar algoritma ini belum diubah (ditingkatkan) sejak pertama kali dibuat pada awal tahun 1970an. Mereka memecahkan masalah tertentu secara berurutan dalam jumlah “n” langkah.

Jumlah langkah tergantung pada ukuran masalah (yang memberikan nilai tertentu pada algoritma sebagai masukan). Metode semacam ini biasanya menghasilkan hambatan komputasi. Keuntungan relatif dari setiap iterasi menjadi semakin kecil seiring kemajuan algoritma.

Bagaimana jika suatu algoritma memerlukan beberapa lompatan, dibandingkan mengambil ribuan langkah kecil untuk memecahkan masalah? Bagaimana jika kita dapat membuat sejumlah besar algoritma yang banyak digunakan saat ini bekerja lebih cepat secara eksponensial? Kita berbicara tentang algoritme yang membantu kita menemukan obat baru dan menghindari kemacetan.

Untuk mewujudkan hal ini, para peneliti di Universitas Harvard telah menciptakan jenis algoritme baru, yang mereka sebut “Terobosan”, yang mempercepat komputasi secara eksponensial dengan mengurangi secara drastis jumlah iterasi yang diperlukan untuk menyelesaikan suatu masalah.

Ini mempercepat komputasi untuk berbagai masalah di beberapa bidang berbeda, seperti ekstraksi informasi, desain lelang, visi mesin, biologi komputasi, analisis jaringan, dan banyak lagi.

Menurut pengembangnya, ia mampu melakukan komputasi besar dalam beberapa detik yang sebelumnya membutuhkan waktu berhari-hari atau berminggu-minggu. Hal ini dapat membuka pintu bagi pendekatan paralelisasi berskala luas yang baru, sehingga memungkinkan proses peringkasan praktis dibangun pada skala yang luar biasa.

Bagaimana Cara Kerjanya?

Algoritme sekuensial bekerja dengan mempersempit jumlah solusi yang layak selangkah demi selangkah. Sedangkan algoritme baru secara paralel mengambil sampel arah yang berbeda, lalu menghilangkan arah yang kurang relevan dan memilih arah yang paling disukai (bernilai tinggi) untuk mencapai solusi. Ini secara selektif membuang nilai-nilai yang akan diabaikan pada iterasi mendatang.

Algoritma terobosan menggunakan adaptive sampling | Atas izin peneliti

Lebih khusus lagi, algoritme ini memerlukan langkah-langkah berurutan O (log n) dan mencapai perkiraan mendekati 1/3. Saat mengaktifkan paralelisasi, algoritme mencapai perkiraan faktor konstan secara eksponensial lebih cepat dibandingkan metode maksimalisasi sub-modular yang ada.

Referensi:Harvard SEAS | Publikasi Harvard

Misalnya, jika tugasnya adalah merekomendasikan film yang mirip dengan Star Wars, algoritme konvensional akan menambahkan satu film di setiap langkah yang memiliki atribut serupa (aksi, petualangan, fantasi) dengan Star Wars.

Algoritma yang baru dikembangkan, sebaliknya, secara acak mengambil sampel serangkaian film, memangkas film-film yang sama sekali tidak cocok dengan Star Wars. Ini memberikan beragam koleksi film (tentunya Anda tidak ingin 10 film Superman dalam rekomendasi Anda) yang mirip dengan Star Wars.

Algoritme akan terus menambahkan variasi film di setiap langkah hingga memiliki cukup item untuk direkomendasikan. Kunci untuk mengambil keputusan berharga di setiap langkah terletak pada proses pengambilan sampel adaptif.

Jumlah langkah yang diambil oleh algoritma sekuensial (hitam) dan terobosan (merah) untuk menyelesaikan suatu masalah

Pengujian dan Penerapan

Para peneliti menguji algoritme pengambilan sampel adaptif mereka pada kumpulan data besar yang berisi 1 juta rating pada 4.000 film dari 6.000 pengguna. Ini berhasil merekomendasikan film yang dipersonalisasi dan bervariasi untuk seseorang 20 kali lebih cepat dibandingkan algoritma konvensional.

Mereka juga menerapkan algoritma ini pada masalah pengiriman taksi – memilih lokasi terbaik untuk melayani jumlah pelanggan maksimum dengan taksi terbatas. Untuk 2 juta perjalanan taksi, algoritme ini bekerja 6 kali lebih cepat dibandingkan algoritme canggih.

Hal ini dapat memberikan hasil yang jauh lebih baik pada kumpulan data berskala besar, seperti analisis media sosial atau pengelompokan data genetik.  Selain itu, algoritme ini dapat diterapkan untuk mengembangkan uji klinis berbagai penyakit, rangkaian sensor untuk pencitraan medis, dan mendeteksi interaksi antar obat.

Baca:Algoritma Pencarian Kendaraan Self-Driving Baru Bisa Pindah Jalur Secara Agresif

Saat ini, menemukan subkumpulan data yang efektif dari jutaan gambar/video untuk melatih jaringan pembelajaran mendalam telah menjadi tugas yang menantang. Studi ini dapat membantu mengekstraksi subset berharga dengan cepat dan memberikan dampak signifikan terhadap masalah peringkasan data berskala besar.