벡터 공간 모델

벡터 공간 모델은 문서가 질의와 얼마나 닮았는지를 재서 검색 결과의 순서를 정합니다. 문서와 질의를 같은 꼴의 숫자 목록으로 바꿉니다. 두 목록의 숫자 비율이 비슷할수록 닮았다고 봅니다. 검색 엔진이 문서를 줄 세우는 고전적인 틀입니다.

상세

벡터 공간 모델(Vector Space Model, VSM)은 문서 모음과 질의 하나를 받아 문서마다 점수를 매기는 방법입니다. 질의는 사용자가 검색창에 넣은 낱말들입니다. 점수가 높은 문서부터 늘어놓으면 검색 결과의 순서가 됩니다.

문서가 질의에 얼마나 맞는지를 나타낸 점수를 관련도라고 부릅니다. 벡터 공간 모델은 관련도를 두 숫자 목록의 값 비율이 얼마나 비슷한지로 잽니다.

불리언 검색이 남긴 문제

벡터 공간 모델 앞에는 불리언 검색이 있었습니다. 불리언 검색은 「파이썬 AND 설치」처럼 낱말과 AND·OR·NOT 을 엮은 조건으로 문서를 거릅니다. 문서마다 답은 「맞는다」와 「안 맞는다」 둘뿐입니다.

답이 둘뿐이라 맞는 문서끼리는 순서가 없습니다. 조건에 맞는 문서가 천 개면 천 개가 똑같은 무게로 나옵니다. 조건을 좁히면 이번에는 하나도 안 나오기 쉽습니다.

사람이 원하는 것은 더 맞는 문서부터 보는 것입니다. 그러려면 맞다와 안 맞다 사이에 눈금이 있어야 합니다. 벡터 공간 모델은 문서와 질의를 숫자로 바꿔 이 눈금을 만듭니다.

문서를 벡터로 바꾸기

첫 단계는 문서 모음에 나오는 낱말을 모두 모으는 일입니다. 모은 낱말마다 칸을 하나씩 둡니다. 모음에 낱말이 3만 개면 칸도 3만 개입니다.

문서 하나는 이 칸마다 숫자를 하나씩 적은 목록이 됩니다. 칸에 적는 숫자를 가중치(weight)라고 합니다. 가중치는 그 낱말이 이 문서에서 얼마나 중요한지를 나타내는 숫자입니다. 어떻게 매기는지는 다음 절에서 봅니다.

칸의 순서는 모든 문서가 같습니다. 그래서 두 목록의 같은 칸은 늘 같은 낱말을 가리킵니다. 이렇게 순서를 정해 늘어놓은 숫자 목록을 벡터라고 부릅니다.

칸 하나를 차원이라고 합니다. 칸이 3만 개인 벡터는 3만 차원 공간에서 원점으로부터 뻗은 화살표 하나로 볼 수 있습니다. 모든 문서가 같은 공간 안의 화살표가 됩니다. 이름의 「벡터 공간」이 이 공간입니다.

한 문서에 든 낱말은 수백 개뿐입니다. 문서에 없는 낱말의 칸은 0 이라 3만 칸 중 거의 전부가 0 입니다. 이렇게 거의 0 으로 찬 벡터를 희소 벡터라고 합니다. 저장할 때는 0 이 아닌 칸의 번호와 값만 적습니다.

질의도 같은 방법으로 벡터가 됩니다. 「파이썬 설치」는 「파이썬」 칸과 「설치」 칸에만 값이 있는 벡터입니다. 문서와 질의가 같은 공간에 놓이므로 둘을 비교할 수 있습니다.

칸에 적는 가중치

칸에 무엇을 적을지는 벡터 공간 모델이 정하지 않습니다. 모델은 문서와 질의를 벡터로 놓고 비교하는 틀까지만 줍니다. 가중치를 매기는 공식은 따로 고릅니다.

가장 널리 짝지어 쓰는 공식은 TF-IDF(Term Frequency-Inverse Document Frequency, 낱말 빈도-역문서 빈도)입니다. 이 문서에 자주 나오고 다른 문서에는 드문 낱말일수록 가중치가 큽니다. 「방법」처럼 거의 모든 문서에 든 낱말은 가중치가 0 에 가깝습니다.

흔히 고르는 가중치 셋을 비교하면 아래와 같습니다.

아래 예에서는 계산을 쉽게 하려고 나온 횟수를 적습니다. 가중치를 TF-IDF 로 바꿔도 뒤의 계산 방법은 같습니다.

방향으로 닮음을 잰다

칸이 두 개뿐인 작은 모음을 생각해 봅시다. 칸은 「파이썬」과 「설치」입니다. 질의와 문서 셋의 벡터는 아래와 같습니다.

A 와 B 는 내용이 같습니다. B 는 길이만 두 배입니다. 그러니 둘은 질의와 똑같이 닮았다고 나와야 합니다. C 는 「파이썬」이 없으니 A·B 보다 덜 닮았다고 나와야 합니다.

벡터에는 방향이 있습니다. 방향은 칸끼리 값이 어떤 비율로 놓였는지입니다. A 는 2 대 1, B 는 4 대 2 라서 둘의 방향이 같습니다.

벡터에는 길이도 있습니다. 길이는 값 전체가 얼마나 큰지입니다. B 의 길이는 A 의 두 배입니다.

닮음을 길이까지 넣어 재면 같은 글을 늘려 쓴 B 가 점수를 더 가져갑니다. 그래서 방향만 봅니다. 두 화살표 사이의 각도가 작을수록 방향이 같습니다. 이 각도를 점수로 바꾼 것이 코사인 유사도입니다.

코사인 유사도

코사인은 각도가 벌어질수록 1 에서 0 쪽으로 줄어드는 함수입니다. 두 벡터가 같은 방향이면 각도가 0 이라 값은 1 입니다. 두 벡터가 직각이면 값은 0 입니다. 가중치가 모두 0 이상이면 값은 늘 0 과 1 사이에 놓입니다.

각도를 직접 잴 필요는 없습니다. 재료는 내적과 벡터의 길이 둘입니다.

두 벡터의 같은 칸끼리 곱해 모두 더한 값을 내적이라고 부릅니다. q 와 A 의 내적은 1×2 + 1×1 = 3 입니다. 두 벡터가 같은 칸에 큰 값을 가질수록 내적이 커집니다.

벡터의 길이는 칸마다 값을 제곱해 더한 뒤 제곱근을 씌운 값입니다. 직각삼각형의 빗변을 구하는 피타고라스 정리와 같은 계산입니다. A 의 길이는 √(2² + 1²) = √5 입니다.

코사인 유사도는 내적을 두 길이의 곱으로 나눈 값입니다. 식으로 적으면 아래와 같습니다. |q| 는 q 의 길이, q · d 는 q 와 d 의 내적입니다.

cos(q, d) = (q · d) / (|q| × |d|)

두 길이의 곱으로 나누는 단계가 긴 문서의 이득을 지웁니다. 문서를 두 배로 늘리면 내적이 두 배가 됩니다. 길이도 두 배가 됩니다. 나눈 값은 변하지 않습니다.

앞의 벡터로 계산해 봅니다. 각 줄 오른쪽 주석이 돌려받는 값입니다.

import math

def cosine(q, d):
    dot = sum(a * b for a, b in zip(q, d))
    len_q = math.sqrt(sum(a * a for a in q))
    len_d = math.sqrt(sum(b * b for b in d))
    return dot / (len_q * len_d)

q = [1, 1]
A = [2, 1]
B = [4, 2]
C = [0, 3]

round(cosine(q, A), 2)  # 0.95
round(cosine(q, B), 2)  # 0.95
round(cosine(q, C), 2)  # 0.71

A 와 B 가 같은 점수를 받습니다. 길이 차이가 점수에서 지워진 것입니다. C 는 「파이썬」 칸이 0 이라 방향이 벌어졌습니다. 그만큼 낮은 점수를 받습니다.

내적·유클리드 거리와의 비교

방향 대신 다른 기준으로 재면 결과가 어떻게 바뀌는지 봅니다. 비교할 기준은 앞에서 푼 내적과 유클리드 거리입니다. 유클리드 거리는 두 화살표의 끝점 사이의 직선거리입니다. 거리는 작을수록 닮은 것입니다.

내적은 길이를 반영해서 긴 B 를 1등에 올립니다. 유클리드 거리는 거꾸로 B 를 꼴찌로 보냅니다. B 의 끝점이 질의에서 멀리 뻗어 있기 때문입니다.

셋 중 코사인 유사도만 A 와 B 를 같게 봅니다. 「파이썬」이 빠진 C 는 아래로 내립니다. 벡터 공간 모델이 코사인 유사도를 기본 기준으로 쓰는 까닭입니다.

검색 한 번의 흐름

계산은 두 때로 나뉩니다. 문서가 들어올 때 미리 해 두는 일이 있습니다. 질의가 올 때 하는 일이 있습니다.

문서가 들어오면 문서를 낱말로 쪼개 벡터를 만듭니다. 글을 낱말로 쪼개는 일을 토큰화라고 부릅니다. 문서 벡터의 길이도 이때 구해 둡니다. 질의마다 다시 계산하지 않으려는 것입니다.

문서 벡터는 역색인에 담습니다. 역색인은 희소 벡터를 문서별로 묶지 않고 낱말별로 다시 묶은 구조입니다. 질의 낱말에서 출발해 그 낱말이 든 문서를 바로 찾으려는 것입니다.

역색인은 낱말마다 묶음을 하나씩 둡니다. 묶음에는 그 낱말이 든 문서 번호와 가중치가 적힙니다. 낱말 하나에 딸린 이 묶음을 포스팅 리스트라고 합니다. 「파이썬」의 포스팅 리스트에는 「파이썬」이 든 문서만 들어 있습니다.

질의가 오면 질의도 벡터로 바꿉니다. 질의 낱말마다 그 낱말의 포스팅 리스트를 읽어 문서마다 내적을 쌓습니다. 쌓은 내적을 미리 구한 길이로 나누면 코사인 유사도가 됩니다. 점수가 높은 순서로 위에서 몇 개만 돌려줍니다.

앞의 두 칸 예시로 역색인의 모양과 내적이 쌓이는 과정을 그리면 아래와 같습니다.

flowchart TD
    subgraph V["문서별로 묶은 벡터"]
        VA["문서 A · 파이썬 2 · 설치 1"]
        VB["문서 B · 파이썬 4 · 설치 2"]
        VC["문서 C · 설치 3"]
    end
    subgraph X["역색인 · 낱말별로 묶은 포스팅 리스트"]
        XP["파이썬 → A 2 · B 4"]
        XS["설치 → A 1 · B 2 · C 3"]
    end
    subgraph R["질의 「파이썬 설치」로 쌓은 내적"]
        RS["A 3 · B 6 · C 3"]
    end
    V -- "낱말별로 묶는다" --> X
    X -- "질의 낱말의 포스팅 리스트만 읽는다" --> R

질의 「파이썬 설치」는 두 포스팅 리스트만 읽습니다. 파이썬 리스트에서 A·B 가, 설치 리스트에서 A·B·C 가 점수를 받습니다. 문서마다 받은 점수를 더하면 앞 표의 내적 3·6·3 이 됩니다.

두 때를 한 그림에 모으면 아래와 같습니다.

flowchart TD
    subgraph S1["문서가 들어올 때"]
        D["문서 벡터 · 낱말로 쪼개 가중치를 적는다"]
        D --> I["역색인 · 낱말마다 포스팅 리스트"]
        D --> L["문서 벡터의 길이"]
    end
    subgraph S2["질의가 올 때"]
        Q["질의 벡터"]
        Q --> P["질의 낱말의 포스팅 리스트만 읽어 내적을 쌓는다"]
        P --> C["길이로 나눠 코사인 유사도 · 높은 순으로 몇 개"]
    end
    I --> P
    L --> C

그림에서 위 칸에서 아래 칸으로 건너가는 화살표 둘이 미리 해 둔 일입니다. 질의 때는 역색인과 길이를 꺼내 쓰기만 합니다.

계산에 드는 비용

질의 벡터를 모든 문서 벡터와 하나씩 비교하면 문서 수 N 과 칸 수 V 를 곱한 만큼 일합니다. 이를 O(N×V) 라고 적습니다. 문서 수나 칸 수가 두 배면 일도 두 배라는 뜻입니다.

역색인을 쓰면 질의 낱말의 포스팅 리스트만 읽습니다. 드는 시간은 그 리스트들에 든 항목 수를 모두 더한 것에 비례합니다. 질의 낱말이 하나도 없는 문서는 내적이 0 이라 건드릴 필요가 없습니다.

저장 공간은 모든 문서 벡터에서 0 이 아닌 칸의 수에 비례합니다. 0 인 칸은 적지 않기 때문입니다. 칸이 3만 개여도 문서마다 수백 칸만 저장됩니다.

벡터 공간 모델이 놓치는 것

첫째는 낱말의 순서입니다. 벡터에는 낱말마다 가중치만 남습니다. 「개가 사람을 물었다」와 「사람이 개를 물었다」는 거의 같은 벡터가 됩니다. 문서를 낱말이 담긴 가방으로만 보는 이 관점을 단어 가방 모델이라고 부릅니다.

둘째는 뜻입니다. 칸은 글자가 다른 낱말마다 따로 섭니다. 「자동차」 칸과 「차량」 칸은 서로 직각인 축입니다. 그래서 「차량」만 쓴 글은 「자동차」 질의와 내적이 0 입니다.

셋째는 낱말 사이의 관계입니다. 칸끼리 직각으로 둔 것은 낱말끼리 아무 관계가 없다고 가정한 것입니다. 「파이썬」과 「프로그래밍」은 함께 나오기 쉬운 낱말입니다. 모델은 이 관계를 모릅니다.

넷째는 가중치의 근거입니다. 어떤 가중치가 옳은지를 모델 안에서 끌어낼 수 없습니다. 가중치 공식은 여러 방법을 시험해 보고 잘 맞는 것을 골라 왔습니다.

뒤를 이은 방법

벡터 공간 모델로 순위를 매기다 보면 문제가 둘 더 드러납니다. 하나는 나온 횟수입니다. 한 낱말이 열 번 나온 문서가 한 번 나온 문서보다 열 배 관련된 것은 아닙니다. 그런데 나온 횟수를 가중치로 적으면 점수도 횟수만큼 커집니다.

다른 하나는 문서 길이입니다. 코사인 유사도는 길이로 나눠 같은 글을 늘려 쓴 문서의 이득을 지웠습니다. 하지만 긴 문서가 늘 같은 글을 되풀이한 것은 아닙니다. 여러 주제를 다뤄 길어진 문서는 관련된 대목이 있어도 길이로 나누면 점수가 지나치게 줄어들 수 있습니다.

BM25(Best Matching 25)는 지금 검색 엔진이 기본 점수 공식으로 흔히 쓰는 방법입니다. 이 두 문제를 공식 하나 안에서 다룹니다. 낱말이 많이 나와도 점수가 어느 선에서 멈추게 합니다. 문서 길이는 모음의 평균 길이와 비교해 얼마나 깎을지를 조절합니다.

BM25 의 뿌리는 벡터 공간 모델이 아니라 확률 모델입니다. 확률 모델은 문서가 질의에 맞을 확률을 추정해 순서를 정하는 틀입니다. 문서를 화살표로 놓고 방향을 재는 생각과는 출발점이 다릅니다.

잠재 의미 분석(Latent Semantic Analysis, LSA)은 앞 절의 둘째와 셋째 약점을 겨냥합니다. 문서와 낱말의 표를 수학적으로 압축해 칸 수를 수백 개로 줄입니다. 자주 함께 나오는 낱말들이 같은 칸으로 모입니다. 그러면 「자동차」와 「차량」이 가까운 방향을 갖게 됩니다.

임베딩은 글의 뜻을 숫자 목록으로 옮긴 것입니다. 많은 글로 미리 학습시킨 모델이 이 목록을 만듭니다. 뜻이 비슷한 글은 글자가 달라도 비슷한 방향의 목록을 받습니다.

임베딩의 벡터는 앞의 희소 벡터와 모양이 다릅니다. 칸 하나가 낱말 하나를 뜻하지 않습니다. 거의 모든 칸에 값이 찹니다. 이런 벡터를 밀집 벡터라고 합니다.

임베딩끼리 가까운 것을 찾는 벡터 검색도 코사인 유사도를 흔히 씁니다. 칸의 뜻은 바뀌었어도 문서를 벡터로 놓고 방향으로 비교한다는 생각은 이어집니다.

쓸 때와 안 쓸 때

벡터 공간 모델은 미리 학습시킬 모델이 필요 없습니다. 문서 모음만 있으면 바로 벡터를 만들 수 있습니다. 작은 모음에서 순위를 매기거나 비교 기준을 세울 때 먼저 꺼내 볼 만합니다.

질의 대신 문서 하나를 넣으면 문서끼리의 닮음이 나옵니다. 이걸로 비슷한 글을 찾아 주거나 닮은 글끼리 묶습니다. 닮은 글끼리 묶는 일을 문서 군집화라고 부릅니다.

검색 순위를 새로 짤 때는 BM25 를 먼저 봅니다. 앞 절에서 본 횟수 문제와 길이 문제를 공식 안에서 다루기 때문입니다.

뜻이 맞는 글을 찾아야 할 때는 낱말 칸으로 짠 벡터가 모자랍니다. 그때는 임베딩과 벡터 검색을 씁니다. 낱말 맞추기와 뜻 맞추기를 함께 돌려 점수를 섞는 방식을 하이브리드 검색이라고 부릅니다.

관련 항목

벡터 공간 모델의 계산을 이루는 수학

벡터 · 내적 · 벡터의 길이 · 코사인 유사도 · 유클리드 거리 · 희소 벡터 · 차원

벡터 칸에 가중치를 매기는 공식

TF-IDF · 낱말 빈도 · 역문서 빈도 · 문서 빈도 · 길이 정규화

벡터 공간 모델과 겨루는 검색 모델

불리언 검색 · 확률 모델 · BM25 · 언어 모델 검색 · 잠재 의미 분석

벡터 공간 모델이 속하는 검색 분야

정보 검색 · 전문 검색 · 관련도 · 관련도 점수 · 랭킹

벡터 공간 모델을 담고 계산하는 구조

역색인 · 포스팅 리스트 · 문서-용어 행렬 · 단어 가방 모델

벡터 공간 모델 앞에서 글을 쪼개는 처리 단계

분석기 · 토큰화 · 불용어 · 어간 추출 · 형태소 분석

벡터 공간 모델의 생각을 잇는 뜻 기반 검색

임베딩 · 밀집 벡터 · 벡터 검색 · 시맨틱 검색 · 하이브리드 검색 · 근사 최근접 이웃

벡터 공간 모델로 점수를 매겨 온 검색 엔진

검색 엔진 · Apache Lucene · Elasticsearch · Apache Solr

벡터 공간 모델로 푸는 텍스트 작업

문서 군집화 · 유사 문서 검색 · 추천 시스템 · 텍스트 분류