[es8] kNN vs ANN 성능비교

kNN ( k-nearest neighbor ) 검색은 유사성 메트릭으로 측정된 쿼리 벡터에 가장 가까운 k 개의 벡터를 찾습니다 .

 

ANN ( approximate nearest neighbor search )

KD-트리와 같은 저차원 벡터에는 kNN에 대한 잘 확립된 데이터 구조가 있습니다. 실제로 Elasticsearch는 KD-트리를 통합하여 지리 공간 및 숫자 데이터에 대한 검색을 지원합니다. 그러나 텍스트 및 이미지에 대한 최신 임베딩 모델은 일반적으로 100 - 1000개 또는 그 이상의 요소로 구성된 고차원 벡터를 생성합니다. 이러한 벡터 표현은 고차원에서 가장 가까운 이웃을 효율적으로 찾는 것이 매우 어렵기 때문에 고유한 문제를 제시합니다.

이러한 어려움에 직면한 가장 가까운 이웃 알고리즘은 일반적으로 속도를 향상시키기 위해 완벽한 정확도를 희생합니다. 이러한 근사 최근접 이웃(ANN) 알고리즘은 항상 진정한 k개의 최근접 벡터를 반환하지 않을 수 있습니다. 그러나 효율적으로 실행되어 우수한 성능을 유지하면서 대규모 데이터 세트로 확장됩니다.

 

kNN,  ANN 하고 그냥 match 쿼리의 성능을 비교 해봐야 하는데...

project path : /Users/doo/project/tf-embeddings

 

 

#가상환경  목록확인
conda info --envs 

#가상환경 생성
conda create --name "text" python="3.7"

#가상환경 실행
conda activate text

kNN

• 검색 대상 벡터와 모든 벡터와의 거리를 계산 
• 가장 거리가 가까운 K개를 리턴 
• 256차원 벡터 150~200만 개, K가 1000쯤 되면 응답 시간이 느려지기 시작

ANN

• 특정 방식으로 검색 대상 벡터와 가까운 벡터를 찾아내는 기법
• Spotify의 Annoy 알고리즘
• 데이터를 추가하기 힘들다

 

HNSW

Hierarchical Navigable Small Worlds

 

 

ANN 은 가이드에서 나온 대로 ..  kNN 은 dense_vector 512 차원

match 는 knn 과 같지만 name에 match 쿼리만 실행할 예정  

    INDEX_NAME_A = "ann-index"
    INDEX_FILE_A = "./data/products/ann-index.json"

    INDEX_NAME_B = "knn-index"
    INDEX_FILE_B = "./data/products/knn-index.json"

    INDEX_NAME_C = "match-index"
    INDEX_FILE_C = "./data/products/knn-index.json"

 

테스트 환경은 아래와 동일 

https://ldh-6019.tistory.com/180?category=1043090 

[tensorflow 2] Text embedding A/B TEST - 2

put_data.py 실행

인덱스 생성 

 

삽질 삽질 하다가

 

이부분 수정  doc['name_vector'] 에서 'name_vector'

"source": "cosineSimilarity(params.query_vector, 'name_vector') + 1.0",

 

이기 뭐여..

 

스코어는 무의미 하고 

 

 

# -*- coding: utf-8 -*-
import time
import json

from elasticsearch import Elasticsearch
from elasticsearch.helpers import bulk

import tensorflow_hub as hub
import tensorflow_text
import matplotlib.pyplot as plt
import kss, numpy

##### SEARCHING #####

def run_query_loop():
    while True:
        try:
            handle_query()
        except KeyboardInterrupt:
            return

def handle_query():
    query = input("Enter query: ")

    embedding_start = time.time()
    query_vector = embed_text([query])[0]
    embedding_time = time.time() - embedding_start

    with open(ANN) as index_file:
        script_query_a = index_file.read().strip()
        script_query_a = script_query_a.replace("${query_vector}", str(query_vector))
        script_query_a = script_query_a.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    with open(KNN) as index_file:
        script_query_b = index_file.read().strip()
        script_query_b = script_query_b.replace("${query_vector}", str(query_vector))
        script_query_b = script_query_b.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    with open(MATCH) as index_file:
        script_query_c = index_file.read().strip()
        script_query_c = script_query_c.replace("${query}", str(query))
        script_query_c = script_query_c.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    search_start = time.time()
    response_a = client.search(
        index=INDEX_NAME_A,
        body=script_query_a
    )
    response_b = client.search(
        index=INDEX_NAME_B,
        body=script_query_b
    )

    print(script_query_c)
    response_c = client.search(
        index=INDEX_NAME_C,
        body=script_query_c
    )

    search_time = time.time() - search_start
    score_a =[]
    score_b =[]
    score_c =[]

    print("검색어 :", query)
    print("CASE A : ")
    for hit in response_a["hits"]["hits"]:
        score_a.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    print("CASE B : ")
    for hit in response_b["hits"]["hits"]:
        score_b.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    print("CASE C : ")
    for hit in response_c["hits"]["hits"]:
        score_c.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    t= range(0, SEARCH_SIZE)
    plt.rcParams['font.family'] = 'AppleGothic'

    fig, ax = plt.subplots()
    ax.set_title('ANN vs kNN vs match')
    line1, = ax.plot(t, score_a, lw=2, label='ANN')
    line2, = ax.plot(t, score_b, lw=2, label='kNN')
    line3, = ax.plot(t, score_c, lw=2, label='match')
    leg = ax.legend(fancybox=True, shadow=True)

    ax.set_ylabel('score')
    ax.set_xlabel('top' + str(SEARCH_SIZE))

    lines = [line1, line2, line3]
    lined = {}  # Will map legend lines to original lines.
    for legline, origline in zip(leg.get_lines(), lines):
        legline.set_picker(True)  # Enable picking on the legend line.
        lined[legline] = origline


    def on_pick(event):
        legline = event.artist
        origline = lined[legline]
        visible = not origline.get_visible()
        origline.set_visible(visible)
        legline.set_alpha(1.0 if visible else 0.2)
        fig.canvas.draw()

    fig.canvas.mpl_connect('pick_event', on_pick)
    plt.show()




##### EMBEDDING #####

def embed_text(input):
    vectors = embed(input)
    return [vector.numpy().tolist() for vector in vectors]

##### MAIN SCRIPT #####

if __name__ == '__main__':
    INDEX_NAME_A = "ann-index"
    INDEX_NAME_B = "knn-index"
    INDEX_NAME_C = "match-index"

    ANN = "ann/query/ann_query.json"
    KNN = "ann/query/knn_query.json"
    MATCH = "ann/query/match_query.json"

    SEARCH_SIZE = 5

    print("Downloading pre-trained embeddings from tensorflow hub...")
    embed = hub.load("https://tfhub.dev/google/universal-sentence-encoder-multilingual-large/3")
    client = Elasticsearch(http_auth=('elastic', 'dlengus'))
    run_query_loop()
    print("Done.")

 

ann_query.json

{
  "query": {
    "match_all": {}
  },
  "knn": {
    "field": "name_vector",
    "query_vector": ${query_vector},
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": ${SEARCH_SIZE}
}

knn_query.json

{
  "query": {
    "script_score": {
      "query": {
        "match_all": {}
      },
      "script": {
        "source": "cosineSimilarity(params.query_vector, 'name_vector') + 1.0",
        "params": {
          "query_vector": ${query_vector}
        }
      }
    }
  },
  "size": ${SEARCH_SIZE}
}

match_query.json

{
  "query": {
    "match": {
      "name": {
        "query": "${query}",
        "boost": 0.9
      }
    }
  },
  "size": ${SEARCH_SIZE}
}