🔵Dasar ANN

Konsep Dasar

Bagaimana cara Anda mencari kemiripan anda dengan teman-teman dalam satu kelas? Ambil satu fitur misal warna kulit. Warna kulit dalam sebuah citra bisa direpresentasikan menggunakan ruang warna RGB. Ambil foto punggung tangan kita, crop dengan ukuran resolusi tertentu (misal 200 x 200 px). Hitung rata-rata RGB dari semua pixel, dan akan kita dapatkan satu nilai avg_RGB untuk warna kulit kita. langkah berikutnya tinggal kita hitung jarak terdekat antara avg_RGB kita sendiri dengan avg_RGB teman-teman sekelas. Dengan menghitung jarak untuk semua teman sekelas, maka akan kita dapatkan tabel urutan kemiripan mulai dari yg termirip hingga yang paling tidak mirip.

Misalkan, Anto memiliki warna kulit dalam rata-rata RGB adalah avg_RGB = (120, 65, 21). Teman-teman yang mirip warna kulitnya dengan Anto adalah,

Nama

Average RGB

Kedekatan

Andika

(123, 69, 17)

0.03

Wendy

(132, 56, 15)

0.05

...

Tabel diatas telah diurutkan mulai dari yang termirip hingga yang paling tidak mirip berdasarkan nilai kedekatannya (makin dekat makin kecil nilainya). Kedekatan dihitung dengan menggunakan euclidean distance. Selanjutnya, yang harus kita lakukan adalah menghitung jarak antara warna kulit Anto. dengan warna kulit semua teman-teman dalam sekelas. Data Anto kita kenal dengan nama Query Point. Artinya jika teman sekelas ada 30 orang, Anda akan menghitung jarak warna Anto akan menghitung jarak dengan semua 30 org temannya agar dapat membentuk tabel urutan seperti diatas. Sekarang jika Anto ingin menghitung kemiripan warna kulitnya dengan seluruh manusia diseluruh dunia, maka dia harus menghitung jaraknya dengan semua orang (sekitar 7,8 miliar orang) kemudian mengurutkannya.

Bagaimana jika fitur yang digunakan tidak hanya warna kulit namun juga warna rambut, tinggi badan, dan berat badan? Kita akan lakukan percobaan nanti terkait hal ini pada praktikum. Agar proses pencarian kedekatan data ini tidak memakan waktu, ada beberapa rekayasa model penentuan kedekatan / kemiripan data yang bisa digunakan yang dikenal dengan Approximate Nearest Neighbors (ANN). Dengan menggunakan model ini, kita dapat melakukan optimalisasi model clustering atau klasifikasi yang di dalam tahapannya ada perhitungan kedekatan, seperti misal KMeans ( untuk klasterisasi) dan KNN (untuk klasifikasi). ANN ini menjadi populer karena dapat memberikan hasil yang mendekati model nearest neighbors asli (exact) tetapi membutuhkan waktu komputasi yang jauh lebih cepat, sangat cocok sekali dengan skenario jumlah data yang sangat besar (big data). Beberapa model yang akan kita pelajari adalah ANNOY, FAISS, dan HNSW.

Konsep Metriks Pada ANN

Sebelum membahas tentang cara kerja ANN, kita perlu tahu tentang perhitungan (metrics) yang digunakan untuk mengukur jarak antar data. Beberapa metrics yang digunakan adalah Euclidean Distance, Inner Product, Cosine Similarity, dan Angular Distance.

Dalam sistem ANN seperti ANNOY misalnya, pilihan metrik jarak yang tersedia umumnya terbatas pada Euclidean dan Angular. Hal ini bukan tanpa alasan. Kedua metrik tersebut dianggap paling relevan untuk berbagai kasus pencarian kedekatan vektor berdimensi tinggi. Euclidean distance (L2 distance) dipilih karena ia mewakili jarak geometris absolut di ruang vektor, sehingga cocok ketika besarnya nilai (magnitudo) dari data memang penting. Sementara itu, Angular distance didasarkan pada cosine similarity yang hanya mempertimbangkan arah vektor, sehingga lebih sesuai ketika yang ingin dibandingkan adalah pola atau orientasi, bukan besarnya nilai.

Metrik lain contoh seperti Manhattan (L1 distance) atau Mahalanobis distance jarang digunakan dalam ANN library seperti ANNOY karena dua alasan utama. Pertama, dari sisi komputasi, perhitungan Euclidean dan Angular relatif sederhana serta efisien di ruang dimensi tinggi, sedangkan Manhattan atau Mahalanobis akan menambah beban perhitungan. Kedua, dalam banyak aplikasi similarity search, misalnya pada teks, gambar, atau embedding dari model pembelajaran mesin, informasi yang paling bermakna biasanya ada pada jarak Euclidean dan sudut (cosine/Angular), sehingga keduanya sudah cukup mewakili kebutuhan umum. Dengan demikian, ANNOY berfokus hanya pada dua metrik ini untuk menjaga performa dan kesesuaian dengan kasus nyata yang paling sering ditemui.

Library lain seperti FAISS (buatan Meta) dan HNSW (Hierarchical Navigable Small World) menyediakan lebih banyak fleksibilitas dalam pemilihan metrik. Selain Euclidean, keduanya mendukung inner product sebagai ukuran kesamaan, yang berguna pada kasus maximum inner product search (MIPS) seperti rekomendasi produk atau sistem retrieval berbasis embedding. Beberapa implementasi bahkan memungkinkan penggunaan variasi metrik lain, meskipun dengan konsekuensi beban komputasi lebih tinggi. Dengan kata lain, Annoy mengutamakan kesederhanaan dan efisiensi dengan dua metrik paling umum, sementara FAISS dan HNSW memberikan pilihan lebih luas sesuai kebutuhan spesifik aplikasi.

Perbandingan ketiga algoritma berbasis ANN secara ringkas dapat dilihat pada Tabel berikut,

Algortima

Struktur Data

Metriks

Catatan

ANNOY

Random Projection Trees

Euclidean, Angular

Sangat ringan, mudah digunakan

FAISS

Inverted file + clustering, GPU optimized

L2, Inner Product (Cosine via normalisasi)