Meningkatkan Akurasi dan Efisiensi Pencarian Semantik dengan AdANNS
Dalam dunia pencarian web, mesin pencari skala besar menggunakan encoder untuk mempelajari representasi kueri yang kemudian dihubungkan ke jalur pencarian tetangga terdekat yang hampir akurat (ANNS). Representasi yang dipelajari seringkali berupa vektor berkualitas tinggi yang digunakan apa adanya dalam jalur pencarian ANNS. Namun, hal ini dapat memakan waktu komputasi yang mahal karena kemampuannya untuk secara akurat menangkap kueri dan titik data yang jarang.
Salah satu bagian integral dari pipa pencarian adalah pencarian semantik pada representasi yang dipelajari. Pembelajaran jaringan saraf untuk menyematkan kueri dan sejumlah besar (N) titik data dalam ruang vektor d-dimensional adalah hal minimal yang diperlukan untuk pendekatan pencarian semantik. Semua langkah dalam ANNS menggunakan informasi yang sama yang dipelajari oleh algoritma pencarian semantik yang ada, yang disebut representasi kaku (RRs). Dengan kata lain, sementara indeks ANNS memperbolehkan berbagai parameter untuk mencari ruang desain guna memaksimalkan keseimbangan akurasi-komputasi, diyakini bahwa dimensionalitas data masukan adalah tetap. Tahapan yang berbeda dalam ANNS dapat menggunakan representasi adaptif dengan kapasitas bervariasi untuk mencapai keseimbangan akurasi-komputasi yang jauh lebih baik daripada yang mungkin dengan representasi kaku, yaitu tahapan ANNS yang dapat menggunakan komputasi yang lebih kira-kira harus menggunakan representasi kapasitas lebih rendah dari titik data yang sama.
Para peneliti menawarkan AdANNS, kerangka desain ANNS baru yang memanfaatkan keadaptabilitas yang diberikan oleh Representasi Matryoshka. AdANNS memberikan akurasi-komputasi mutakhir menggunakan komponen pembangunan ANNS berbasis AdANNS yang unik, seperti struktur data pencarian (AdANNS-IVF) dan kuantisasi (AdANNS-OPQ). AdANNS-IVF, misalnya, mencapai akurasi 1,5% lebih tinggi daripada IVF berbasis representasi kaku pada pemulihan ImageNet dengan menggunakan anggaran komputasi yang sama, dan mencapai tingkat akurasi yang sama sambil berjalan 90 kali lebih cepat pada dataset yang sama. AdANNS-OPQ, varian 32-byte dari OPQ yang dibangun menggunakan representasi fleksibel, mencapai akurasi yang sama dengan basis OPQ 64-byte untuk Natural Questions. Mereka juga menunjukkan bahwa manfaat AdANNS dapat diterapkan pada indeks ANNS komposit mutakhir dengan menggunakan kedua struktur pencarian dan kuantisasi. Terakhir, mereka menunjukkan bahwa indeks ANNS yang dibangun tanpa adaptasi menggunakan representasi matryoshka dapat dicari secara komputasi dengan AdANNS.
AdANNS-IVF dapat diterapkan 90% lebih cepat daripada IVF tradisional sambil meningkatkan akurasi hingga 1,5%. AdANNS-OPQ memiliki presisi yang sama dengan standar emas dengan harga yang lebih murah. Struktur data pencarian yang didukung oleh AdANNS (AdANNS-IVF) dan kuantisasi (AdANNS-OPQ) secara signifikan mengungguli alternatif mutakhir yang ada dalam hal keseimbangan akurasi-komputasi. Selain itu, AdANNS memungkinkan pencarian yang dapat disesuaikan dengan komputasi selama inferensi dan dapat digeneralisasi ke indeks ANNS komposit mutakhir.
AdANNS adalah sistem untuk meningkatkan keseimbangan akurasi-komputasi dalam komponen pencarian semantik yang memanfaatkan fleksibilitas inherent dalam representasi matryoshka. Terdapat dua bagian utama dalam pipa ANNS yang tipikal: (a) struktur data pencarian yang mengindeks dan menyimpan titik-titik data; dan (b) metode komputasi titik kueri yang memberikan jarak (kasar) antara kueri dan serangkaian titik data. Dalam penelitian ini, kami menunjukkan bahwa AdANNS dapat digunakan untuk meningkatkan kinerja kedua subsistem ANNS tersebut, dan kami mengukur peningkatannya dalam hal trade-off antara upaya komputasi dan akurasi. Secara khusus, kami memperkenalkan AdANNS-IVF, struktur indeks berbasis AdANNS yang mirip dengan struktur IVF yang lebih umum dan struktur terkait ScaNN. Selain itu, kami memperkenalkan adaptivitas representasi dalam OPQ, kuantisasi standar de facto, dengan bantuan AdANNS-OPQ. AdANNS-IVFOPQ, varian AdANNS dari IVFOPQ, dan AdANNS-DiskANN, varian DiskANN, adalah dua contoh metode hibrida lain yang ditunjukkan oleh para peneliti. Dibandingkan dengan indeks IVF yang dibangun menggunakan RRs, AdANNS-IVF secara eksperimental terbukti lebih akurat dan optimal dalam hal komputasi. AdANNS-OPQ terbukti memiliki akurasi yang sama dengan OPQ pada RRs dengan biaya yang jauh lebih murah. AdANNS dirancang dengan arsitektur pencarian yang dapat menampung berbagai kasus penggunaan skala besar, masing-masing dengan kebutuhan sumber daya yang unik untuk pelatihan dan inferensi. Namun, hanya kadang-kadang pengguna tidak dapat mencari ruang desain karena masalah pembuatan indeks dan penyimpanan.
Secara keseluruhan, AdANNS diusulkan oleh sekelompok peneliti dari University of Washington, Google Research, dan Harvard University untuk meningkatkan keseimbangan akurasi-komputasi dengan memanfaatkan representasi adaptif di berbagai tahap pipa ANNS. Dibandingkan dengan blok bangunan ANNS tradisional yang menggunakan representasi yang kaku, AdANNS memanfaatkan fleksibilitas inherent dalam representasi matryoshka untuk membangun blok bangunan yang lebih unggul. Untuk dua blok bangunan ANNS utama – struktur data pencarian (AdANNS-IVF) dan kuantisasi (AdANNS-OPQ) – AdANNS mencapai trade-off akurasi-komputasi terbaik saat ini. Akhirnya, dengan menggabungkan blok bangunan berbasis AdANNS, indeks ANNS komposit yang lebih baik dalam dunia nyata dapat dibangun, memungkinkan pencarian yang elastis terhadap komputasi dan mengurangi biaya hingga 8 kali lipat dibandingkan dengan dasar yang kuat.
Disarikan dari: Link