고차원 벡터

고차원 벡터는 데이터 하나를 수백에서 수천 개의 숫자로 나타냅니다. 글의 뜻처럼 숫자 몇 개로는 못 담는 특징을 담아 둡니다. 그러면 비슷한 데이터를 거리로 찾을 수 있습니다. 대신 숫자가 많을수록 가까운 것을 찾는 일이 어려워집니다.

상세

이 절은 고차원 벡터가 무엇인지, 어디서 생기는지, 차원이 높으면 무엇이 어려워지는지, 어떻게 다루는지를 봅니다.

사람을 키와 몸무게 두 숫자로만 적으면 전혀 다른 두 사람이 같은 숫자를 얻습니다. 설문지에 취미와 사는 동네와 좋아하는 음식까지 수백 항목을 넣으면 사정이 달라집니다. 수백 항목의 답이 비슷한 두 사람이라면 정말 닮은 사람입니다.

벡터와 차원

벡터는 숫자를 정해진 개수만큼 늘어놓은 목록입니다. [3, 4] 는 숫자 둘짜리 벡터입니다. 목록에서 숫자 하나가 들어가는 곳을 이 항목에서는 칸이라고 하겠습니다.

칸의 개수를 차원이라고 합니다. [3, 4] 는 칸이 둘이라 2차원입니다.

2차원 벡터는 평면 위의 점 하나로 볼 수 있습니다. [3, 4] 는 가로로 3, 세로로 4만큼 간 점입니다. 가로와 세로처럼 칸 하나가 재는 방향을 축이라고 합니다. 축 하나가 차원 하나입니다.

칸이 천 개면 축이 천 개인 공간의 점입니다. 그림으로는 못 그리지만 계산하는 방법은 2차원과 같습니다.

고차원 벡터는 차원이 아주 높은 벡터입니다. 숫자가 몇 개뿐이면 서로 다른 데이터가 같은 값을 얻기 쉽습니다. 숫자가 수백 개면 데이터의 여러 면이 그 숫자들에 흩어져 담깁니다.

앞의 설문지와 다른 점이 하나 있습니다. 설문지는 사람이 항목을 정하므로 항목마다 이름이 있습니다. 고차원 벡터는 학습한 모델이 숫자를 정하는 일이 많습니다. 이때는 숫자 하나하나에 사람이 읽을 수 있는 이름이 붙어 있지 않습니다.

고차원과 저차원의 경계

몇 차원부터 고차원인지 정한 경계는 없습니다. 기준은 차원 수가 아니라 현상입니다. 차원이 오르면 점 사이의 거리가 서로 비슷해집니다. 이 현상은 뒤 「거리가 서로 비슷해지는 현상」 소절에서 봅니다.

2차원과 3차원은 그림으로 그려 직관으로 다룰 수 있습니다. 차원이 수십을 넘으면 그림도 직관도 통하지 않습니다.

검색과 머신러닝에서 고차원이라고 부르는 벡터는 흔히 차원이 수백에서 수천입니다. 이 정도면 그 거리 문제가 뚜렷해집니다.

고차원 벡터가 생기는 곳

고차원 벡터를 만드는 길은 크게 둘입니다. 학습한 모델이 뽑아 주는 길과 낱말을 세어 만드는 길입니다. 두 길에서 나온 벡터는 숫자가 채워진 모양이 다릅니다.

첫째 길은 임베딩입니다. 임베딩은 글이나 그림을 학습을 마친 모델에 넣어 숫자 목록으로 바꾸는 일입니다. 모델은 뜻이 비슷한 데이터에 가까운 벡터를 주도록 미리 배워 둡니다.

임베딩으로 나온 벡터는 거의 모든 칸에 0이 아닌 숫자가 들어 있습니다. 숫자가 빽빽하게 차 있다는 뜻으로 이런 벡터를 밀집 벡터라고 합니다.

둘째 길은 낱말을 세는 방법입니다. 사전에 든 낱말마다 칸을 하나씩 둡니다. 문서에 그 낱말이 나온 횟수를 그 칸에 적습니다. 사전에 낱말이 십만 개면 벡터도 십만 차원이 됩니다.

이 방법은 낱말의 순서를 버리고 횟수만 남깁니다. 문서를 낱말을 쏟아 담은 가방처럼 다루는 셈이라 단어 가방 모델이라고 합니다.

문서 하나에는 사전의 낱말 가운데 일부만 나옵니다. 그래서 대부분의 칸이 0입니다. 이렇게 0이 아닌 칸이 드문 벡터를 희소 벡터라고 합니다.

두 벡터를 나란히 놓으면 아래와 같습니다.

희소 벡터는 흔히 역색인으로 찾습니다. 역색인은 낱말마다 그 낱말이 든 문서 목록을 미리 적어 둡니다. 찾을 때는 질문에 든 낱말의 목록만 열어 봅니다. 차원이 십만이어도 칸 전체를 훑지 않습니다.

밀집 벡터는 이렇게 건너뛸 0인 칸이 없습니다. 거리를 잴 때마다 칸 전체를 훑어야 합니다. 이어지는 비용과 거리 이야기는 주로 밀집 벡터의 것입니다.

거리로 재는 가까움

고차원 벡터를 쓰는 까닭은 데이터끼리 얼마나 닮았는지를 재기 위해서입니다. 두 벡터의 닮은 정도를 숫자 하나로 바꾸는 계산이 거리입니다. 이 소절은 자주 쓰는 셋을 봅니다.

유클리드 거리는 두 점을 곧게 이은 선의 길이입니다. 칸마다 두 숫자의 차를 제곱해 모두 더합니다. 그 합에 제곱근을 씌우면 거리입니다. 2차원에서는 피타고라스 정리와 같은 계산입니다.

코사인 유사도는 두 벡터가 가리키는 방향이 얼마나 같은지를 봅니다. 원점에서 두 점으로 화살표를 그었을 때 그 사이 각도로 잽니다. 같은 쪽을 가리키면 1, 직각으로 벌어지면 0입니다. 화살표의 길이는 따지지 않습니다. 덕분에 문서가 길고 짧은 차이에 덜 휘둘립니다.

내적은 칸마다 두 숫자를 곱해 모두 더한 값입니다. 계산이 가장 단순해서 많이 씁니다. 길이를 1로 맞춘 벡터끼리는 내적이 곧 코사인 유사도입니다.

차원이 늘면 커지는 비용

거리를 한 번 재려면 칸 수만큼 계산합니다. 그래서 차원은 계산 시간과 메모리 양쪽에 곱으로 붙습니다.

벡터 둘의 내적을 구하려면 칸마다 곱셈을 한 번 합니다. 차원이 d면 곱셈이 d번입니다. 저장된 벡터가 n개면 쿼리 하나를 전부와 견주는 데 곱셈이 n × d번 듭니다.

메모리도 같은 식으로 늡니다. 숫자 하나를 32비트 부동소수점 수로 적으면 4바이트입니다. 아래는 768차원 벡터 1억 개가 차지하는 메모리를 셈한 것입니다. 마지막 줄만은 메모리가 아니라 쿼리 하나를 전부와 견줄 때의 곱셈 횟수입니다.

d = 768                 # 차원
per_vec = d * 4         # 3072 바이트
n = 100_000_000         # 벡터 1억 개
total = n * per_vec     # 307_200_000_000
total / 10**9           # 307.2 기가바이트
n * d                   # 곱셈 768억 번

벡터 하나는 3킬로바이트 남짓입니다. 그런데 1억 개를 모으면 300기가바이트를 넘습니다. 쿼리 하나를 전부와 견주면 곱셈을 768억 번 합니다.

거리가 서로 비슷해지는 현상

차원이 높아지면 비용만 느는 것이 아닙니다. 거리라는 잣대 자체가 무뎌집니다. 이 소절은 그 현상과 까닭을 봅니다.

점들을 공간에 아무렇게나 흩어 놓고 한 점에서 나머지까지의 거리를 재 봅니다. 2차원에서는 아주 가까운 점과 아주 먼 점이 뚜렷이 갈립니다. 차원이 수백으로 늘면 거의 모든 점이 비슷한 거리에 몰립니다.

이때 가장 가까운 점과 가장 먼 점의 거리 차이는 거리 자체에 견주어 작아집니다. 「가장 가깝다」는 말이 힘을 잃는 것입니다. 이 현상을 거리 집중이라고 부릅니다.

까닭은 거리가 칸마다의 차이를 모두 더한 값이라는 데 있습니다. 칸이 늘면 합계는 칸 수에 비례해 커집니다. 칸마다의 차이는 점마다 크기도 하고 작기도 합니다. 칸이 많으면 어떤 칸의 큰 차이를 다른 칸의 작은 차이가 메웁니다.

그 결과 점마다 합계가 들쭉날쭉한 폭은 합계만큼 빨리 커지지 않습니다. 합계에 비해 그 폭이 점점 작아지니 거리들이 서로 비슷한 값으로 보입니다.

동전 던지기와 같은 원리입니다. 열 번 던지면 앞면이 일곱 번 나오기도 합니다. 만 번 던지면 앞면이 나온 비율은 절반 근처에 붙습니다.

던진 횟수가 차원에, 앞면 비율이 칸 하나당 평균 차이에 해당합니다. 횟수가 늘면 비율이 한 값에 붙듯, 칸마다의 차이를 더해 칸 수로 나눈 값도 점마다 한 값에 붙습니다.

차원이 높아질수록 낮은 차원에서 통하던 방법이 힘을 잃는 일을 통틀어 차원의 저주라고 부릅니다. 거리 집중은 그 대표적인 모습입니다.

다만 실제 데이터는 공간 전체에 고르게 흩어져 있지 않습니다. 뜻이 비슷한 문장의 임베딩은 몇몇 덩어리로 모입니다. 그래서 무작위로 흩은 점만큼 거리가 뭉개지지는 않습니다.

데이터가 실제로 퍼져 있는 방향의 수를 내재 차원이라고 합니다. 3차원 공간에 종이 한 장을 비스듬히 띄우고 그 위에만 점을 찍었다고 해 봅니다. 점마다 숫자는 셋이지만 점들은 종이의 가로와 세로 두 방향으로만 퍼져 있습니다. 겉의 차원은 3이고 내재 차원은 2입니다.

겉의 차원보다 내재 차원이 훨씬 낮을 때 가까운 이웃을 찾는 검색이 제 구실을 합니다.

공간을 나눠 찾는 방법이 막히는 까닭

낮은 차원에서는 공간을 영역으로 나눠 두고 쿼리가 든 영역 근처만 봅니다. 고차원에서는 이 방법이 듣지 않습니다. 이 소절은 영역이 몇 개로 불어나는지로 그 까닭을 봅니다.

축마다 한가운데를 잘라 반으로 나눈다고 해 봅니다. 축이 하나 늘 때마다 영역 수가 두 배가 됩니다. 차원별로 세면 아래와 같습니다.

100차원이면 영역 수가 어떤 데이터 개수보다도 훨씬 많아집니다. 영역 대부분은 비어 있습니다. 쿼리의 가까운 이웃은 쿼리가 든 영역이 아니라 수많은 옆 영역에 흩어집니다.

k-d 트리(k-dimensional tree)는 이 생각으로 짓는 자료구조입니다. 축을 번갈아 골라 데이터를 반씩 가르며 트리를 만듭니다. 찾을 때는 쿼리와 멀리 떨어진 가지를 열어 보지 않고 건너뜁니다.

차원이 높으면 이 건너뛰기가 거의 일어나지 않습니다. 앞 소절에서 본 대로 모든 점까지의 거리가 비슷합니다. 멀다고 잘라 낼 가지가 없습니다. 결국 대부분의 가지를 열어 보게 됩니다. 하나씩 전부 견주는 완전 탐색과 걸리는 시간이 별로 다르지 않습니다.

고차원 벡터를 다루는 세 방법

고차원의 비용을 줄이는 길은 셋입니다. 정확함을 조금 내주거나, 숫자의 개수를 줄이거나, 숫자 하나의 크기를 줄입니다. 이 소절은 셋을 하나씩 짚고 대가를 나란히 놓습니다.

근사 최근접 이웃 검색은 거리를 재는 벡터 수를 줄입니다. 미리 지어 둔 인덱스를 따라가며 가까울 만한 후보만 거리를 잽니다. 전부 재지 않으므로 빨리 끝납니다.

차원 축소는 벡터 하나에 든 숫자의 개수를 줄입니다. 예를 들어 768개의 숫자를 128개로 줄입니다. 이때 벡터끼리의 거리는 되도록 지킵니다.

대표적인 방법은 주성분 분석(PCA, Principal Component Analysis)입니다. 데이터가 가장 넓게 퍼진 방향부터 골라 새 축으로 삼습니다. 퍼짐이 작은 방향은 버립니다.

양자화는 숫자 하나를 적는 비트 수를 줄입니다. 4바이트 부동소수점 수를 1바이트 정수로 바꾸면 메모리가 4분의 1이 됩니다.

세 방법의 대가는 아래와 같습니다.

셋은 겹쳐 쓸 수 있습니다. 차원을 줄이고 양자화한 벡터 위에 근사 인덱스를 짓는 식입니다.

쓰는 때와 안 쓰는 때

고차원 벡터는 「이것과 닮은 것」을 찾을 때 씁니다. 뜻으로 글을 찾는 시맨틱 검색이 그렇습니다. 본 상품과 비슷한 상품을 고르는 추천 시스템과 비슷한 그림 찾기도 그렇습니다. 정답이 하나로 정해지지 않고 가까운 순서가 곧 답인 일입니다.

값이 딱 맞아야 하는 일에는 맞지 않습니다. 주문 번호나 에러 코드로 찾을 때 벡터는 가까운 다른 번호를 돌려줄 수 있습니다. 이럴 때는 B-tree 같은 보통의 인덱스나 글자 일치 검색을 씁니다.

벡터가 적으면 근사 방법을 쓸 까닭도 적습니다. 전부 견주는 완전 탐색으로도 빨리 끝납니다. 게다가 놓치는 것이 하나도 없습니다.

관련 항목

고차원 벡터를 이루는 기본 개념

벡터 · 차원 · 스칼라 · 행렬 · 부동소수점 · 벡터 공간

고차원 벡터의 하위 종류

밀집 벡터 · 희소 벡터 · 단위 벡터 · 원-핫 벡터 · 이진 벡터

고차원 벡터를 만들어 내는 방법

임베딩 · 임베딩 모델 · 단어 가방 · TF-IDF · Word2Vec · 특징 추출

고차원 벡터끼리 가까움을 재는 척도

유클리드 거리 · 코사인 유사도 · 내적 · 맨해튼 거리 · 해밍 거리

고차원에서 나타나는 현상

차원의 저주 · 거리 집중 · 내재 차원 · 다양체 가설

고차원 벡터를 줄이거나 압축하는 수단

차원 축소 · 주성분 분석 · 무작위 투영 · 양자화 · 곱 양자화

고차원 벡터를 찾는 검색 방법

최근접 이웃 검색 · 근사 최근접 이웃 · 완전 탐색 · k-d 트리 · HNSW · 지역 민감 해싱 · 벡터 검색 · 시맨틱 검색

고차원 벡터를 쓰는 응용 분야

검색 · 추천 시스템 · 머신러닝 · 이미지 검색

고차원 벡터가 저장되는 저장소

벡터 데이터베이스 · 벡터 인덱스 · 역색인 · B-tree