임베딩을 이용한 검색

Approximate Nearest Neighbor Search

문서 임베딩의 유사도를 이용하여 검색하면 단어가 일치하지 않아도 의미적으로 비슷한 문서를 찾을 수있음
키워드 기반의 검색과는 다른 인덱싱 방법이 필요
ANN
- Approximate: 근사
- Nearest Neighbor: 가장 가까운 사례
정확하게 비슷한 사례를 찾으려면 시간이 오래 걸리므로, 대략 비슷한 사례를 찾아 검색 속도를 높이는 방법
방법: PQ, IVF, 트리, 해시, HNSW, NGT 등

Product Quantization

큰 실수 벡터를 작은 정수 벡터로 표현하는 방법
하나의 큰 벡터를 작은 서브벡터들로 자르고(product)
각각의 서브벡터를 클러스터링하여, 클러스터 번호로 대체(quantization)

Inverted File Index

임베딩을 k-Means 등의 방법으로 클러스터링
검색 시 먼저 클러스터를 찾고, 클러스터 내에서 만 세부 검색

트리를 이용한 문서 검색

공간을 축에 정렬된(axis-aligned) 방식으로 분할 → 트리(tree)로 만듦
문서를 찾을 때 트리의 같은 말단(terminal)에 있는 문서를 비슷한 문서로 판정
위와 같은 트리를 여러 개 만들어 포레스트(forest)를 구성
여러 트리의 결과를 합쳐서 비슷한 문서들을 찾음
저차원에서는 효율적이지만 고차원에서는 비효율
현대 딥러닝 임베딩 검색에서는 잘 사용하지 않음

해시를 이용한 문서 검색

해시 함수(hash function): 데이터를 고정된 크기의 값으로 매핑하는 함수(예: 나머지)
랜덤 투영(random projection): 랜덤하게 만든 행렬을 곱하여 작은 차원으로 투영한다 → 축별로 +면 1, -면 0으로 변환한다 → 이진수로 변환한다
Locally Sensitive Hashing: 비슷한 데이터를 쉽게 찾기 위한 해싱 방법
- ↔ 조금만 바뀌어도 해시값이 크게 달라지는 암호학적 해시와 정반대 성질
비슷한 데이터는 비슷한 해시값을 갖도록 하는 방법을 여러 번 적용
하나라도 일치하면 비슷한 데이터로 판정
메모리를 많이 사용

위계적 탐색가능한 작은 세상 네트워크

Hierarchical Navigable Small Worlds Network
1960년대 심리학자 스탠리 밀그램의 실험: 멀리 떨어진 지역의 모르는 사람에게 편지를 전달 → 5~6단계만에 가능
작은 세상 네트워크: 주로 가까운 점과 연결되어 있지만, 멀리 떨어진 점들과도 일정 비율 연결된 형태
탐색 가능한: 네트워크의 전체 구조를 모르더라도 최대한 가까운 방향으로 이동 하면 짧은 경로로 도달 가능
멀리 떨어진 점들과 적정 비율로 연결되어야 함
위계적: 연결된 거리에 따라 단계적으로 구성

알고리즘 성능 비교

다양한 알고리즘들이 개발 중
비슷한 알고리즘도 구현에 따라 속도 차이가 있음

초당 검색량(높을 수록 빠름)

속도와 정확함 사이에는 로그 선형 관계가 있음

재현도(높을 수록 정확)

pg_vector 확장 설치

PostgreSQL 17 개발용 헤더 및 라이브러리 설치

!sudo apt update
!sudo apt install -y postgresql-server-dev-17

pgvector 컴파일 및 설치

!git clone https://github.com/pgvector/pgvector.git
!cd pgvector && make clean && make && sudo make install
!sudo -u postgres psql -d searchdb -c "CREATE EXTENSION vector;"

sentence transformers

테이블 변경

%%sql
ALTER TABLE wikipages ADD COLUMN IF NOT EXISTS title_embedding vector(768);

sentence transformers 설치

!pip install sentence_transformers
from sentence_transformers import SentenceTransformer
sbert = SentenceTransformer('jhgan/ko-sroberta-multitask')

임베딩 불러오기

import numpy as np
data = np.load('wikipedia_ko_embeddings.npz')
embeddings = data['embeddings']

데이터 로딩 준비

import json
import pandas as pd
import sqlalchemy
from tqdm.auto import tqdm
engine = sqlalchemy.create_engine(
    'postgresql+psycopg2://colab:colab@localhost:5432/searchdb')
df = pd.read_csv('wikipedia_ko.csv')
ids = df['id'].tolist()

임베딩을 DB에 추가

with engine.begin() as conn:
    for i, doc_id in enumerate(tqdm(ids)):
        embedding_val = embeddings[i].tolist()
        embedding_json = json.dumps(embedding_val)
        stmt = sqlalchemy.text("""
            UPDATE wikipages
            SET title_embedding = CAST(:embedding AS vector)
            WHERE id = :doc_id
        """)
        conn.execute(stmt, {"embedding": embedding_json, "doc_id": str(doc_id)})

임베딩으로 검색

vec_search_query = sqlalchemy.text(f"""
    SELECT id, title, title_embedding <=> CAST(:query_emb AS vector) AS similarity
    FROM wikipages
    ORDER BY similarity
    LIMIT 5;
""")

<-> : L2 distance
<=> : Cosine distance
<#> : Negative inner product

임베딩으로 검색

search_query = "한국사"
query_embedding = sbert.encode(search_query).tolist()
query_embedding_json = json.dumps(query_embedding)
vec_results = pd.read_sql(
    vec_search_query, engine, params={"query_emb": query_embedding_json})
vec_results