Yaklaşık Yakın Komşu Arama

Yapay zekanın kuşkusuz en heyecanlı alanlarından birisi denetimsiz öğrenme. Denetimsiz öğrenmeyi verinin özelliklerinin oluşturduğu doğal kümelenmenin analizi olarak tanımlayabiliriz. Yakın komşu arama da bu metodolojinin en performanslı yönlerinden bir tanesi.

Denetimsiz öğrenme sahasında elinizdeki veri, kümeler çözünürlüğünde değil de tekil örnek çözünürlüğünde anlamlı hale gelmeye başlıyorsa farklı yöntemler kullanılmaya başlanmalıdır.

Örnek olarak vermek gerekirse tersine görüntü arama motoru oluşturduğunuzu varsayalım. Bu arama motorunda kullanıcı görüntüyü yükleyecek ve yüklediği görüntüye en çok benzerlik gösteren diğer görüntüleri görmek isteyecektir. Söz konusu verinin sayısallığı(cardinality) ise 1.000.000 olsun. Yani bu denli fazla görüntü içerisinde elinizdeki görüntünün özellik vektörüne en yakın olanları arayacaksınız anlamına geliyor.

Doğrusal Arama

Bir diğer açılımı kaba kuvvet (Brute Force) olan doğrusal arama yöntemi en yavaş olandır ve O(N) maliyetine sahiptir.

Yazı boyunca aynı örnek üzerinde gideceğiz ve tersine resim arama motorunun arama dinamiği bizim için önemli olacak. Bu tip problemlerde öncelikli işimiz özellik çıkarımı ve kaynak görüntünün düşük boyutlu bir özellik vektörüne indirgenmesi. Bu aşama konumuz dahilinde olmadığından anlatmıyorum fakat autoencoder modeli veya hazır eğitilmiş modellerden facenet bu anlamda güzel bir örnek olabilir.

Uzaklık fonksiyonu olarak öklit mesafesi (euclidean distance) kullanacağız. 512 özellikten oluşan vektöre indirgenmiş resim bilgisini daha önce indeksimize aldığımız vektörler ile karşılaştırarak en yakın mesafedeki vektörü bulacağız. Aşağıdaki python örneğinde doğrusal arama ve çıktısı görünmektedir:

import numpy as np
import time

def bul(vector, vectorset):
    min_uzaklik = None
    min_indeks = None
    for i, _vec in enumerate(vectorset):
        uzaklik = np.linalg.norm(_vec-vector) #Öklit mesafesi
        if min_uzaklik is None or uzaklik<min_uzaklik:
            min_indeks = i
            min_uzaklik = uzaklik
    return min_indeks, min_uzaklik

#1.000.000 ayrı resim için örnek vektörler oluşturuluyor
vectorset = np.random.rand(1000000, 512)

aranacak = np.random.rand(512)

basla = time.time()
print("Sonuc: ", bul(aranacak, vectorset))
print("Doğrusal arama zamanı: " + str(time.time() - basla) + " saniye")

Çıktı ise aşağıdaki gibi:

Sonuc:  (431966, 8.156703660634795)
Doğrusal arama zamanı: 9.81592607498169 saniye

İlk satırda sırasıyla en yakın vektörü ve uzaklığını görüyorsunuz ve arama süresi hiç iç açıcı değil.

Yaklaşık yakın komşu arama ise doğrusal aramadaki kaba kuvvet yönteminden ziyade eldeki veriyi organize ederek saklar ve bu organizasyonda veriye erişir. Yöntem ise rassal projeksiyonlar algoritmasına dayanmaktadır. Bu algoritmanın işleyişinde kümeden seçilmiş rassal iki noktaya eşit uzaklıktaki hiperdüzlem seçilir ve ağaç oluşturulur. Bu ağaç ile arama yakınsanarak gerçekleştirilir.

Yaklaşık yakın komşu arama için etkin bir çözüm olan annoy kütüphanesini kullanacağız. Bu kütüphane oldukça etkili ve hızlı. Üstelik disk üzerinde indekslemeye izin verdiği için dağıtık işlemeye de izin vermekte. Pypi sayfasında da göreceğiniz üzere Spotify arkaplanında kullanılmakta.

Şimdi aynı örneği annoy ile deneyelim:

import numpy as np
import time
from annoy import AnnoyIndex


#1.000.000 ayrı resim için örnek vektörler oluşturuluyor
basla = time.time()
vectorset = np.random.rand(1000000, 512)
indeks = AnnoyIndex(512, metric='euclidean')
for i, _vec in enumerate(vectorset):
  indeks.add_item(i, _vec)
  
#Indeks kuruluyor, ağaç oluşturuluyor.
indeks.build(16)

print(f"Indeks şu kadar saniyede oluşturuldu: {time.time()-basla}")

def bul(vector):
    return indeks.get_nns_by_vector(vector, 1, include_distances=True)



aranacak = np.random.rand(512)

basla = time.time()
print("Sonuc: ", bul(aranacak))
print("annoy arama zamanı: " + str(time.time() - basla) + " saniye")

Ve yukarıdaki kod bloğunun sonucu:

Indeks şu kadar saniyede oluşturuldu: 273.5093071460724
Sonuc:  ([500807], [8.464658737182617])
annoy arama zamanı: 0.005526304244995117 saniye

Yukarıda gördüğünüz üzere arama zamanı 5 ms civarında. Yani doğrusal arama test değerlerinden oldukça iyi. Fakat burada sizinde gözünüze çarpacak bir sorun bulunmakta. Indeks 273.51 saniyede oluşturuldu. Bu yaklaşık yakın komşu aramanın en büyük dezavantajı. Yaklaşık yakın komşu aramanın gerçekleştirilebilmesi için yapılması gereken ağaçların hesaplanması oldukça fazla süre alabilmekte. Annoy kütüphanesi ise henüz gerçek zamanlı indeksleme metodolojisini desteklemiyor. Bunun için algoritma tabanında olmasa da annoy kütüphanesinin sağlamış olduğu ölçeklenebilirlik özellikleriyle neredeyse gerçek zamanlı indeksleme yapılabilmektedir.

“Buraya kadar olan bilgileri gerçek hayatta nerede kullanacağım?” sorusunu soruyorsanız Github üzerinde paylaştığım OneShotFaceDetectorWebService projesine göz gezdirebilirsiniz.

Ölçeklenebilirlik

Annoy için ölçeklenebilirlik CPU ve makine bazında ortak indeksleme ve işlem yük paylaşımı olarak ortaya çıkmakta. Statik dosyaları indeks olarak ayağa kaldırması senkronize olarak güncelleyebilmesi süreç açısından en büyük avantajımız. Henüz indeksleme işlem yükünün bölünmesiyle alakalı çözüm sunmasa da çoklu indeks oluşturma ve gerçek zamanlı indeks dosyası senkronizasyonuyla gerçek zamana yakın veri ekleme performansı sağlanabilmekte.

Nitekim bu tip bir metodu sigorta şirketlerinden akış olarak gelen fotoğrafların indekslenmesinde kullandım ve başarılı olarak çalışmakta. Yakın zamanda da bu metodolojiyi servisleştirip açık kaynak olarak paylaşmayı düşünüyorum.

Sonuç

Doğrusal aramayın 🙂 Yapay zeka modellerinin en büyük problemlerinden bir tanesi başlı başına servisleştirme ve sunma aşamasıdır. Bu aşamayı oldukça kolaylaştıracak yaklaşık yakın komşu aramayı, çevrimiçi olarak değişen modellerinizin sunumunda kullanabilirsiniz.

Sevgiyle kalın…

Yaklaşık Yakın Komşu Arama – Annoy Kütüphanesi

Doğrusal Arama