Vector DB 이론

벡터 DB는 벡터 기반 유사도 검색을 위해 구축된 특별한 데이터베이스이다. 유사도 검색은 단어의 알파벳 조합에 의한 표면적 유사성을 계산하는것에서 출발해 언어적 의미까지 해석하여 벡터로 임베딩하는 밀집 벡터 방법까지 발전하였다.

I. 유사도 검색

관계형 데이터 모델은 쿼리할 때 입력값과 속성값이 정확히 일치해야만 데이터를 찾을 수 있다. 이와 달리 비슷한 정도를 계산하여 유사도가 높은 순으로 데이터를 찾는 검색을 유사도 검색이라고 한다.

벡터DB를 공부하기 앞서 3가지의 전통적인 유사도 검색 알고리즘을 알아보자.

Jaccard

Jaccard는 각 문장을 구성하는 단어들의 집합을 구하여, 두 집합의 교집합 원소 갯수를 합집합 원소 갯수로 나눈 수치이다.

파이썬 예제는 다음과 같다.

def jaccard(x: str, y: str):
	# 각각 중복을 제거(set)한 집합으로 바꾼다.
	x = set(x.split())
	y = set(y.split())
	# 교집합과 합집합을 구한다.
	shared = x.intersection(y)
	union = x.union(y)
	# 교집합 원소 수 / 합집합 원소 수
	return len(shared) / len(union)

w shingling

기본적으로 자카드와 원리는 같으나 단어를 n개씩 묶어 집합을 구성하는 방식이다. 단어를 몇개씩 묶었는지를 n-gram으로 표현한다. 단어를 하나씩 원소로 하면 1-gram(원그램), 2개씩 묶어 원소로 하면 2-gram(투그램) 또는 bigram(바이그램) 이라고 한다. 1-gram은 Jaccard와 완전히 동일하다.

Levenshtein(레븐슈타인 거리)

한 단어를 다른 단어로 완전히 바꾸는데 필요한 최소한의 비용을 의미한다.

단어를 구성하는 알파벳들을 하나씩 풀어서 각각 행과 열의 헤더로 구성한다.
첫 번째 행과 열의 헤더는 빈 문자로 구성한다.
우선 첫 행, 첫 열을 0부터 1씩 증가하도록 작성한다. 이는 빈 문자->해당 알파벳으로 삽입하는 비용을 의미한다.
본격적인 시작은 (1, 1)부터 시작한다. 왼쪽 셀, 위쪽 셀, 왼쪽위 대각선 셀에 기입되어 있는 세 값중 최소값을 가져온다. 위쪽 셀의 값은 삭제하는 비용을, 왼쪽 셀의 값을 삽입하는 비용을, 대각선 셀의 값은 대체하는 비용을 의미한다.
해당 셀의 각 헤더 알파벳이 일치하지 않으면 경우 1을 추가한다.
모든 셀이 채워지면 가장 오른쪽 아래에 있는 값이 최종적인 비용이다.

파이썬 예제는 다음과 같다.

import numpy
# 각 단어의 맨 앞에 공백 문자열을 추가한다.
def leven(a: str, b: str):
	a = f" {a}"
	b = f" {b}"
	# 행렬을 초기화한다. 첫 값은 모두 0이다.
	lev = numpy.zeros((len(a), len(b)))
	# 맨 왼쪽 끝부터 순회 시작
	for i in range(len(a)):
		for j in range(len(b)):
			# 행렬의 각 첫 줄은 1씩 증가하는 삽입비용이다.
			if min([i, j]) == 0:
				lev[i, j] == max([i, j])
			else:
				x = lev[i-1, j]   # 삭제 비용
				y = lev[i, j-1]   # 삽입 비용
				z = lev[i-1, j-1] # 대체 비용
				lev[i, j] = min([x, y, z]) # 최소값 = 최저비용
				if a[i] != b[j]:           # 두 문자가 일치하지 않으면 1 추가
					lev[i, j] += 1
					
	return lev[-1, -1]

기존 유사도 검색의 한계 Hi 와 Hello는 거의 비슷한 의미를 가지나 기존의 유사도 검색 알고리즘은 알파벳 조합에 의한 표면적 유사성만을 검사하기에 한계가 있다. 따라서 의미적 유사성까지 파악하기 위해 등장한 검색 알고리즘이 바로 벡터 기반 유사도 검색이다.

II. 벡터 기반 유사도 검색

어떠한 문장에 대해, 그 문장을 구성하는 의미들을 실수 집합(벡터)으로 표현한다. 이 과정을 임베딩(Embedding) 이라고 한다. 산출된 벡터는 다차원 공간상에 존재하는 한 점을 의미할 수 있다. 쿼리 문장 역시 벡터로 임베딩하여 데이터셋에 저장된 다른 벡터들과 거리를 계산하거나 코사인 유사도(방향의 유사성)를 계산함으로서 검색을 수행할 수 있다. 이것을 벡터 기반 유사도 검색이라고 부른다.

문장을 벡터로 임베딩하는 두가지 방법이 있다.

희소(sparse) 벡터 방법

많은 0이 있고 가끔씩 값이 있는 벡터를 사용하는 방법이다. 가장 먼저 알아볼 것은 TF-IDF이다.

TF(단어 빈도): 쿼리 단어가 문서에서 등장하는 빈도수 / 문서의 총 단어 수

TF = \frac{f(q, D)}{f(t, D)}

IDF(역문서 빈도): 로그(총 문서 수 / 쿼리 단어를 포함하는 문서 수)

IDF = \log{\frac{N}{N(q)}}

IDF는 TF와는 반대로 많은 문서에서 등장할수록 낮은 수치가 나온다. 이는 쿼리 단어가 특정 문서에서 얼마나 중요한지를 나타내는 지표로 작용한다. 각각의 문서에 대한 TF를 공통된 IDF값과 곱한 값이 TF-IDF이다.

TF-IDF 산출을 파이썬 예제로 나타내면 다음과 같다.

import numpy
  
a = "purple is the best city in the forest".split()
b = "there is an art to getting your way and throwing bananas on to the street is not it".split() 
c = "it is not often you find soggy bananas on the street".split()

docs = [a, b, c]

def tfidf(word, sentence):
	freq = sentence.count(word)
	N_q = sum([1 for doc in docs if word in doc])
	tf = freq / len(sentence)
	idf = numpy.log10(len(docs) / N_q)
	return round(tf*idf, 4)

유사성 검색을 위한 DB를 구축한다면 먼저 전체 문서 집합을 구성하는 모든 어휘들로 각 문서에 대한 TF-IDF를 산출한다. 각각의 문서에 해당하는 TF-IDF 값들을 배열에 담으면 그것이 바로 TF-IDF 벡터가 되는데, 매우 많은 0이 존재하며 적은 값이 존재하는 형태가 된다.

vocab = set(a+b+c)

vac_a = []
vac_b = []
vac_c = []

for word in vocab:
	vac_a.append(tfidf(word, a))
	vac_b.append(tfidf(word, b))
	vac_c.append(tfidf(word, c))

BM25는 문서 길이에 따라 결과를 정규화하기 위해 TF-IDF를 최적화한 것이다. TF-IDF의 문제점은 문서에서 특정 단어가 차지하는 중요도가 단어 빈도에 따라 선형적으로 증가한다는 점이다.

선형적 중요도 증가의 문제점 예를 들어 500 단어로 구성된 기사가 있는데 거기서 "연성대"를 20번 언급하고 있다면 해당 기사가 충분히 연성대를 주제로 하고 있다고 볼 수 있다. 근데 500단어 중 "연성대"가 40개가 되면 이미 충분히 확보된 관련성 점수가 두배나 상승하게 된다. 실제 문서에서 특정 단어가 충분히 등장한 상태임에도 여전히 단어 수에 따라 중요도가 선형적으로 증가하는 경우는 많지 않다.

이 문제를 해결하기 위해 BM25에서는 길이 정규화 항을 추가하여 포화 효과를 부여한다. 단어가 어느수준 이상으로 자주 등장하면 그 이후로는 아무리 많이 등장해도 관련성 점수가 큰 폭으로 증가하지 않도록 하는 것이다.

TF_{TF-IDF} = \frac{f(q, D)}{f(t, D)}

TF_{BM25} = \frac{f(q, D)}{f(q, D) + K}

TF의 분모에 문서의 전체 단어수가 아닌 빈도수 + 정규화항으로 바뀐것이 TF-IDF와 BM25의 가장 중요한 차이이다. 정규화항인 K를 풀어서 쓰면 다음과 같다.

TF_{BM25} = \frac{f(q, D)}{f(q, D) + k\cdot(1-b+b\cdot\frac{D}{d_{avg}})}

$k$ 와 $b$ 는 상황에 따라 조정가능한 실수값이며 범위는 $k<=1.25$ , $b<=0.75$ 이다. $\frac{D}{d_{avg}}$ 는 현재 문서의 단어 수를 평균 단어 수로 나눈 값이다.

IDF는 다음과 같은 변화가 있다.

이제 이를 파이썬 예제로 작성해보자.

import numpy
  
a = "purple is the best city in the forest".split()
b = "there is an art to getting your way and throwing bananas on to the street is not it".split()
c = "it is not often you find soggy bananas on the street".split()
d = "green should have smelled more tranquil but somehow it just tasted rotten".split()
e = "joyce enjoyed eating pancakes with ketchup".split()
f = "as the asteroid hurtled toward earth becky was upset her dentist appointment had been canceled".split()

docs = [a, b, c, d, e, f]
avgdl = sum(len(doc) for doc in docs) / len(docs)
N = len(docs)


def bm25(word, sentence, k=1.2, b=0.75):
	freq = sentence.count(word)
	N_q = sum([1 for doc in docs if word in doc])
	tf = (freq * (k + 1)) / (freq + k * (1 - b + b * (len(sentence) / avgdl)))
	idf = numpy.log(((N - N_q + 0.5) / (N_q + 0.5)) + 1)
	return round(tf*idf, 4)

쿼리 단어 빈도수에 따른 관련성 증가 그래프는 다음과 같다.

희소 벡터 방법의 문제점 'hi'와 'hello'는 매우 비슷한 단어지만 한 글자를 빼고는 알바펫이 완전히 달라 희소 벡터 방법으로는 어휘 자체가 담고있는 의미를 고려하기 어렵다. 이를 보완하기 위해 밀집 벡터 방법이 사용된다.

밀집(dense) 벡터 방법

0이 대부분인 희소 벡터와 달리 0대신 유의미한 실수값들이 대부분을 차지하는 밀집된 벡터를 사용한다. 이러한 유의미한 값들을 부여하기 위해 미리 학습된 변환 모델이 사용된다. 이 방법은 희소 벡터보다 어휘에 대한 더욱 많은 의미를 내포할 수 있다는 장점이 있다.

BERT는 가장 널리 사용되는 변환 모델이며 12개정도의 인코더 레이어를 통해 768개의 원소로 구성된 밀집 벡터를 문장마다 최대 512개씩 생성한다.

Sentence-BERT(SBERT) 는 BERT의 한계를 극복한 버전이다. BERT는 문장을 구성하는 토큰(단어)마다 하나의 벡터를 출력하기에, 문장 전체의 의미를 비교하려면 각 벡터들의 평균을 구하거나 하는 방식으로 합쳐야했다. 하지만 SBERT는 문장 전체의 의미를 하나의 벡터에 담도록 특수한 미세조정 작업을 통해 개선됨으로서 높은 성능을 보여준다.

파이썬의 sentence_tranformers 모듈을 사용해 이 알고리즘의 예제를 작성할 수 있다.

from sentence_transformers import SentenceTransformer
from sklearn.metrics.pairwise import cosine_similarity
import numpy

a = "purple is the best city in the forest"
b = "there is an art to getting your way and throwing bananas on to the street is not it"  # this is very similar to 'g'
c = "it is not often you find soggy bananas on the street"
d = "green should have smelled more tranquil but somehow it just tasted rotten"
e = "joyce enjoyed eating pancakes with ketchup"
f = "as the asteroid hurtled toward earth becky was upset her dentist appointment had been canceled"
g = "to get your way you must not bombard the road with yellow fruit"  # this is very similar to 'b'

# 임베딩 모델을 생성하고 각 문장들을 임베딩한다.
model = SentenceTransformer('bert-base-nli-mean-tokens')
sentence_embeddings = model.encode([a, b, c, d, e, f, g])

print(sentence_embeddings.shape)

(7, 768)

7: 7개의 문장이 임베딩 되었음을 의미한다. 768: 각 문장에 대한 단일 밀집 벡터의 길이를 의미한다.

이렇게 임베딩된 각 문장들을 하나씩 다른 문장과 비교하여 유사도를 산출해보자.

# 7X7 2차원 배열을 만든다. 문장들간 유사도 점수를 담을 행렬이다.
scores = numpy.zeros((sentence_embeddings.shape[0], sentence_embeddings.shape[0]))
# 
for i in range(sentence_embeddings.shape[0]):
    scores[i, :] = cosine_similarity(
        [sentence_embeddings[i]], # 현재 문장에 대한 밀집 벡터
        sentence_embeddings       # 다른 문장들에 대한 밀집 벡터
    )[0]

산출된 유사도 점수

print(scores)

[[ 1.000000  0.186927  0.282976  0.296282  0.274510  0.101762  0.216962]
 [ 0.186927  1.        0.720587  0.514289  0.117496  0.193069  0.661823]
 [ 0.282976  0.720587  1.000000  0.488644  0.235689  0.171571  0.55993 ]
 [ 0.296282  0.514289  0.488644  0.999999  0.269854  0.378894  0.523888]
 [ 0.274510  0.117496  0.235689  0.269854  0.999999  0.234221 -0.015997]
 [ 0.101762  0.193069  0.171571  0.378894  0.234221  1.000000  0.223196]
 [ 0.216962  0.661823  0.55993   0.523888 -0.015997  0.22319   1.000000]]

이 정보들을 그림으로 시각화하면 다음과 같다.