1 milyon vektör arasında en yakın vektörü bulmak

Question

Yüz tanıma sistemlerinde derin öğrenme modelleri ile algılanan yüzler vektörlerde tutuluyor.

Veri tabanımızda bu şekilde kaydı yapılmış 1 milyon yüzün vektörü olduğunu ve her bir vektörün boyunun 128 olduğunu varsayalım.

Yeni bir yüz kaydı yapılmadan önce bu veri tabanında arama yapılıyor, yüz daha önceden tespit edilmiş ise kaydı yapılmıyor.

Arama sırasında yeni gelen vektör ile veri tabanında bulunan vektörler arasında uzaklık hesaplaması yapılıyor ve eğer uzaklık belirlenen eşit değerinin altında ise yüz veri tabanındadır deniyor.

Ancak 1+ milyon arasında tek tek karşılaştırma yapmak ciddi bir maliyet oluşturmakta.

Bu arama süreci nasıl daha hızlı yapılabilinir?

Comments

Mesafe yerine mesafenin karesini hesaplayarak baslayabilirsiniz. Paralel yapabilirsiniz isleminizi. Vektorize edilmis kod yazmak da ise yarayacaktir. Bunun disinda her vektore olan uzakligi hesaplamak yerine soyle bir sey yapabilirsiniz. $n$ vektorumuz olsun $k$ tane de "klas"iniz. Her klasin icindeki vektorler birbirlerine "yakinlar". Yeni bir vektor geldigi zaman $n$ vektorle karsilastirma yapmak yerine her klasin ortalamasi ile karsilastirilir ve en yakin olan klaslarda arama yapilir.

Uzun suruyor derken ne kadar bir sureden bahsediyoruz ve kullandiginiz teknolojiler neler? Julia da cok da optimize etmeden yazdigim find_dist(a,b) = sum((a .- b) .^ 2,dims=1 ) fonksiyonu ile bir 128 boyutlu vektorden, 1 milyon tane 128 boyutlu vektore mesafe hesaplamak yaklasik 0.7 saniye surdu. Bu is icin yazilmis Distances.jl paketini kullaninca 0.1 saniye surdu. 

---

Bence bu yorum da cevap olmalı. Soruyla ilgili de yorum haklı, hızlı derken neye göre hızlı net belirtilirse daha iyi cevaplar çıkabilir.