대규모 문서 모음이 있다고 가정해 보자. 그중에서 서로 대략 같은 문서가 무엇인지 찾아내고 싶다. 예를 들어 일정 기간 동안 웹을 크롤링했다면 “같은 페이지”를 여러 번 가져왔을 가능성이 높지만, 메타데이터가 약간씩 다르거나 작은 편집을 거친 여러 개정본이 섞여 있을 수 있다.

이번 글에서는 Jaccard 유사도와 MinHash 근사 트릭을 이용한 근사 중복 제거 방법을 살펴보고자 한다. 이는 이 문제에 대해 널리 쓰이는 접근법으로(예컨대 GPT-3 논문에서는 데이터셋 준비 파이프라인의 일부로 이를 사용했다고 설명한다), 필자는 최근까지 접해 본 적이 없었지만 꽤 흥미롭다고 느꼈다.

유사도

근사 중복 제거에 대한 우리의 접근법은 임의의 두 문서 사이에 “유사도”라는 개념을 정의한 뒤, 그 유사도 값이 특정 임계값을 넘는 쌍을 찾는 것이다. 가능한 모든 문서의 전체 집합을 \(U\)라 하면, 문서 쌍 사이의 유사도 척도를 다음과 같이 정의할 수 있다: $$S: U \times U \rightarrow [0,1]$$ 그리고 두 문서를 \(S(A,B) \geq S_\textrm{crit}\)인 경우 “근사 중복”으로 간주한다.

이 정의가 일반적으로 추이적이지 않다는 점에 주목할 가치가 있다. 세 문서 \(A, B, C\)에 대해 \(S(A,B)\geq{}S_\textrm{crit}\)이고 \(S(B,C) \geq{} S_\textrm{crit}\)이면서도 \(S(A,C) < S_\textrm{crit}\)인 경우가 충분히 있을 수 있다. 즉 “대략 동일하다”는 동치 관계가 아니며, 이는 정확한 일치를 찾는 경우에 비해 근사 중복 제거를 추론하고 대규모로 수행하는 것이 더 까다로운 이유 중 하나다.

Jaccard 유사도

대규모 텍스트 처리를 포함한 여러 분야에서 널리 쓰이는 유사도 척도 중 하나는 Jaccard 지수이며, Jaccard 유사도 계수라고도 불린다.

Jaccard 지수는 집합을 비교하는 함수로, 두 유한 집합의 유사도를 겹치는 부분과 합집합 크기의 비율로 특징짓는다:

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

이 계산은 직관적으로 꽤 타당하다고 생각한다. 두 집합이 유사하다면 대부분 같은 원소를 가져야 한다. 이는 두 집합의 크기가 비슷하고, 합집합은 조금만 더 크며 교집합은 조금만 더 작다는 뜻이다. 두 집합이 매우 다르거나 크기가 크게 다르면 합집합은 크고 교집합은 작아진다.

이 지수는 범위를 규정하는 두 개의 매우 자연스러운 극한점을 갖는다. 서로소인 두 집합에서는 분자 \(|A\cap{}B|\)가 0이므로 지수는 0이 된다. 반면에 두 집합이 동일하면 \(A\cap{}B = A\cup{}B = A = B\)이므로 Jaccard 유사도는 1이 된다.

Jaccard 유사도는 집합에 대해 동작하지만, 우리는 문서(일반적으로 유니코드 문자열로 표현됨)에서 출발한다는 점에 유의하자. 텍스트 문서를 어떻게 집합으로 바꾸는지는 뒤에서 다시 다루고, 지금은 이미 변환이 끝났다고 가정하겠다. 이러한 집합을 “피처 집합”이라고 부르고, 개별 원소를 문서의 “피처”라고 하겠다.

Jaccard 유사도의 규모 확장

이제 “근사 유사도”에 대한 정의를 갖게 되었다. 문서를 피처 집합으로 변환한 뒤, Jaccard 유사도가 높은 집합을 찾으면 된다.

아주 작은 말뭉치라면 이 정의를 직접 적용할 수도 있다. 하지만 모든 문서 쌍을 고려하는 방식은 말뭉치 크기에 대해 \(O(n^2)\)로 확장되므로, 금세 감당할 수 없게 된다.

정확한 중복을 찾을 때는 해싱으로 2차 비용을 피한다. 문서를 해시하고 해시값으로 그룹화하면, 동일한 문서(그리고 높은 확률로 동일한 문서만)가 같은 해시 버킷에 들어간다. 근사 중복에 대해서도 비슷한 지름길을 찾고 싶다. 이 분야의 용어로 말하면 locality-sensitive hash가 필요한 것이다.

다행히 Jaccard 유사도에 대해 이러한 기법이 존재한다! 어떻게 동작하는지 살펴보자.

Jaccard 유사도 근사하기

먼저 두 문서 사이의 Jaccard 유사도를 근사하는 문제를 고려해 보자. 전체 집합을 일일이 살펴보지 않고, 각 문서마다 독립적으로 미리 계산할 수 있는 작고 크기가 고정된 “시그니처”만을 필요로 하는 근사법을 찾을 것이다. 그런 다음, 그 시그니처의 구조를 이용해 문서들을 그룹화하는 방법을 찾아, 높은 확률로 유사한 문서끼리, 그리고 대부분 유사한 문서끼리만 함께 묶이도록 하겠다.

MinHash 시그니처

Jaccard 유사도는 두 크기의 비율, 즉 두 입력 집합의 교집합과 합집합이라는 점을 떠올려 보자.

$$J(A,B) = \frac{|A\cap{}B|}{|A\cup{}B|}$$

이와 같은 면적 비율을 추정하는 고전적인 전략 중 하나는 샘플링이다. (적절한 의미에서) 균일하게 무작위 원소를 생성할 수 있고, 그 원소가 비율의 양쪽에 존재하는지 질의할 수 있다면, 참값에 수렴하는 경험적 추정치를 만들 수 있다.

이 경우 합집합은 교집합보다 최소한 크므로, \(A\cup{}B\)에서 균일하게 무작위 샘플을 원한다. 집합 자체만으로는 어떻게 해야 할지 명확하지 않지만, 각 집합에 대해 사전 계산을 허용한다면 저렴하게 할 수 있음이 드러난다!

• 먼저 문제를 겉보기에는 더 복잡하게 만든다. 피처가 어떤 유한한 범위 \(0 \leq f_i \leq F\) 안의 정수라고 가정하고, \(\mathbb{Z}_F\) 위의 무작위 순열을 하나 고른다. 그 순열을 \(P(x)\)라 하자. 이제 이 순열에서 값이 가장 작은 피처를 선택함으로써 무작위 원소를 선택할 수 있다¹:

$$ x_{\textrm{random}} \leftarrow{} \argmin_{x\in{}A\cup{}B}{P(x)} $$

• 진정한 무작위 순열을 다루는 것은 실제로는 가능하지 않지만, 좋은 해시 함수를 이용해 이를 근사할 수 있다. 이는 또한 피처가 고정된 범위의 정수로 표현될 필요가 없게 한다. 충돌의 아주 작은 위험을 감수하고 해시값만 저장함으로써, 어떤 합리적인 피처 공간이든 고정 크기의 해시값으로 매핑할 수 있다:

$$ x_{\textrm{sig}} \leftarrow{} \min_{x\in{}A\cup{}B}{H(x)} $$

• 다음으로, min이 결합법칙을 만족한다는 점을 이용해 위 식을 각 집합을 개별적으로 전처리하도록 다시 쓴다:

\begin{align*} a_{\textrm{min}} &\leftarrow{} \min_{x\in{}A}H(x) \\ b_{\textrm{min}} &\leftarrow{} \min_{x\in{}B}H(x) \\ x_{\textrm{sig}} &\leftarrow{} \min(a_\textrm{min},b_\textrm{min}) \end{align*}

한 걸음 물러서서 우리가 무엇을 달성했는지 생각해 보자. 피처에 대해 좋은 해시 함수를 하나 고르면, 각 집합마다 개별적으로, 그 피처들의 최소 해시값으로 이루어진 “시그니처”를 계산할 수 있다. 그러면 임의의 두 집합이 주어졌을 때 그 시그니처들의 최솟값을 취하면, 합집합에서 균일하게 무작위로 추출된 어떤 원소의 (해시)값을 얻게 된다.

우리는 그 원소가 교집합에 존재하는지, 아니면 한쪽에 빠져 있는지를 알고 싶다. 그런데 이 구성 덕분에 그 확인도 자명해진다! \(x_\textrm{sig}\)는 어느 한 집합에 속한 원소 중 해시값이 가장 작은 값임을 안다. 따라서 그 원소가 예컨대 집합 \(A\)에 존재한다면, 그것은 그 집합에서도 해시값이 가장 작은 원소임에 틀림없다. 그런데 우리는 각 집합의 최소 해시값을 이미 알고 있다 — 바로 우리가 가진 것이다!

따라서 실제로 \(x_\textrm{sig}\)를 계산할 필요는 없다. 대신 \(a_\textrm{min} = b_\textrm{min}\)인지 여부만 물으면 된다! 임의의 두 집합에 대해 이 등식은 \(J(A, B)\)와 같은 확률로 성립한다!

더 많은 해시 함수 사용하기

그 확률은 \(\mathbb{Z}_F\)의 순열 전체 집합에 대해(엄밀히는 몇 가지 전제 하에 “해시 함수의 선택”에 대해) 취한 것이다. 단일 해시 함수와 단일 min-hash만으로는 각 쌍에 대해 “같다” 혹은 “다르다”라는 불리언 추정치 하나만 얻을 수 있다.

대신 적절한 해시 패밀리에서 \(k\)개의 서로 다른 해시 함수를 선택하고, 각 문서를 \(k\)개 원소로 이루어진 벡터로 요약함으로써 이를 개선할 수 있다:

$$ A_\textrm{sig} = \begin{pmatrix} \displaystyle\min_{x\in{}A}H_1(x) & \displaystyle\min_{x\in{}A}H_2(x) & \cdots{} & \displaystyle\min_{x\in{}A}H_k(x) \end{pmatrix} $$

이러한 시그니처 두 개가 주어지면, 몇 개의 해시가 일치하는지를 세어 Jaccard 유사도를 근사할 수 있다:

$$ J(A,B) \approx{} \frac{1}{k}\sum_{i=1}^{k} (A_\textrm{sig}[i] = B_\textrm{sig}[i]) $$

한 가지 짚고 넘어갈 주의사항이 있다. 여기서 해시 패밀리의 선택은 다소 미묘하다. 우리는 피처 전체 집합에 대한 무작위 순열을 근사하려 하지만, 그러한 순열의 수는 매우 빠르게 증가하므로 우리 해시 패밀리는 가능한 모든 순열 중 극히 일부만을 나타낸다. 우리 해시 패밀리의 구성원들이 부당하게 상관관계를 갖지 않도록 해야 한다 — 형식적으로 여기서 중요한 속성은 “min-wise independence”라고 불린다. 다행히 이 문제는 꽤 잘 연구되어 있으며, 문헌에서 효율적인 해법을 찾을 수 있다.

모든 문서 비교하기

이제 각 문서를 \(k\)개의 해시값으로 이루어진 지문으로 압축했고, 이를 통해 Jaccard 유사도를 효율적으로 근사할 수 있다.

다음 문제는 전체 말뭉치에서 높은 유사도를 가진 근사 중복 문서들을 모든 문서 쌍을 고려하지 않고 찾는 것이다. 위에서 언급했듯이, 우리의 전략은 문서를 그룹화할 수 있는 일련의 키를 정의한 뒤, 각 그룹 내에서만 전체 비교를 수행하는 것이다. 유사한 문서는 높은 확률로 함께 묶이고, 유사하지 않은 문서는 그렇지 않도록 그룹화 키를 구성하는 것을 목표로 할 것이다.

전체 시그니처 활용하기

가장 단순한 선택은 단순히 \(k\)개의 MinHash 값을 모두 함께 그룹화 키로 사용하고, 두 문서가 모든 MinHash 값이 일치할 때에만 “근사 중복”으로 간주하는 것이다. 위에 인용된 GPT-3 논문에서 “우리는 Spark의 MinHashLSH 구현을 10개 해시로 사용해 문서를 퍼지 중복 제거했다 […]”라고 말한 것이 아마도 바로 이를 의미한다고 확신한다. 그들은 각 문서를 피처로 나누고, 각 문서마다 10개의 MinHash 값을 계산한 뒤(10개의 서로 다른 해시를 사용해²), 그 10차원 벡터로 문서를 그룹화하고 그룹당 하나의 문서만 남겼다.

이 접근법의 가장 큰 장점은 단순성과 효율성이다. 단일 고카디널리티 바이트 문자열로 문서를 그룹화하는 것은 효율적인 연산이며 수평적으로 확장하기 쉽고, 사실상 모든 데이터 처리 툴킷에서 기본 원시 연산으로 제공된다(이는 MapReduce에서 arguably 핵심 원시 연산으로, map과 reduce 단계 사이의 “shuffle” 형태로 나타난다).

이 접근법은 어떻게 동작할까? 단일 문서 쌍에 대해 각 MinHash 값이 일치할 확률을 \(J(A,B)\)라 기대하므로, 10개가 모두 일치할 확률은 \(p=J(A,B)^k\)가 된다. \(k=10\)인 경우 그 모습은 다음과 같다:

그리고 몇 가지 분위수는 다음과 같다:

유사도가 0.6 이하인 문서들은 거의 충돌하지 않고, 일치 확률은 0.95 부근에서 커진다는 것을 알 수 있다. 주로 매우 가까운 문서들에 관심이 있다면 이 접근법으로도 충분할 수 있다. 그리고 사실 필자는 — 검증하지는 않았지만 — 많은 말뭉치에서 Jaccard 값이 꽤나 이봉 분포를 보일 것이라고 의심한다 — 1과 0 근처에 두 개의 군집이 있는 형태다. 관련 없는 문서들의 유사도는 0에 가깝고, 유사한 문서들은 대부분 “거의 동일한” 문서들일 것이다 — 예컨대 글의 약간 다른 두 개정본이라든지, 타임스탬프나 메타데이터만 다른 동일한 콘텐츠의 두 사본 같은 경우다.

\(J^{k}\) 계산은 단일 문서 쌍에 대해 성립한다는 점도 주목할 가치가 있다. 서로 유사한 문서가 많이 있다면, 쌍별 확률은 전혀 독립적이지 않다. 실제로 매우 유사한 문서가 많이 있으면, 그 문서들은 최대 두세 개 버킷으로 해싱될 가능성이 높으므로, 어떤 의미에서는 중복의 “거의 전부”를 찾게 된다.

더 퍼지하게 가기

(참고: 이 논의는 주로 “Mining of Massive Datasets” 3.4절에서 가져왔다. 필자는 이 전략을 직접 다뤄 본 적이 없으며, 실제로 언제, 어떻게 쓰이는지는 아직 모른다.)

만약 더 “퍼지한” 중복을 탐지하고 싶다면 어떻게 해야 할까? 어쩌면 실증적인 연구 끝에 “1에 가까운” 경우만이 아니라 유사도가 0.8이나 0.7 이상인 쌍을 찾고 싶다고 판단할 수도 있다.

\(k\)개의 MinHash 해시 중 일부만을 그룹화 키로 사용함으로써 더 낮은 유사도 값에서도 충돌 가능성을 높일 수 있고, 이후 각 버킷 내에서 전체 시그니처를 비교해 잘못된 충돌을 걸러낼 수 있다. 예를 들어 처음 4개의 MinHash 값으로 그룹화한 뒤, 충돌한 각 그룹 내에서는 모든 MinHash 값을 이용해 실제 유사도를 추정할 수 있다.

더 적은 해시를 사용하는 것은 도움이 되지만 한계가 있다. \(J^r\)은 항상 \(J\)보다 작으며, \(r\)을 너무 작게 밀어붙이면 잘못된 매칭 비율이 감당할 수 없을 정도로 커진다.

대신 문서마다 여러 개의 키를 생성하고, 각 키마다 MinHash의 서로 다른 부분집합을 사용해 각 문서를 여러 버킷에, 키당 하나씩 배치할 수 있다. 시그니처로 \(k=20\)개의 해시를 계산한다면, 각 문서를 \(r=5\)개의 해시로 키를 구성해 \(b=4\)개의 서로 다른 버킷에 넣은 뒤, 각 버킷 내에서 각 쌍을 비교할 수 있다.

두 문서가 적어도 하나의 버킷에서 함께 해싱될 확률은 얼마일까?

• 단일 키를 사용해 두 문서가 충돌할 확률은 \(J^r\)이다
• 따라서 그 키를 기준으로 충돌하지 않을 확률은 \(1-J^r\)이다
• 따라서 어느 버킷에서도 충돌하지 않을 확률은 \((1-J^r)^b\)이다

따라서 적어도 한 번은 충돌할 확률은 결국 다음과 같다:

\[ p = 1 - (1-J^r)^b \]

예를 들어 위의 예 — 5개 해시로 이루어진 4개 그룹을 사용하는 경우 — 는 다음과 같은 확률 곡선을 만든다:

곡선이 앞선 예만큼 가파르지는 않지만, 성공적으로 왼쪽으로 이동했다 — 충돌 확률이 50%가 되는 지점은 대략 \(J=0.7\) 부근이다.

\(r\)과 \(b\)가 모두 1보다 큰 어떤 선택에 대해서도, 결과 곡선은 대체로 비슷한 방식으로 S자 형태를 띠며, 따라서 그 값들을 조정하면 민감도, 재현율, 성능 비용에 걸쳐 풍부한 트레이드오프 공간을 얻을 수 있다.

마무리 생각

AI 분야에서 일하기 전에는, 가장 일반적인 스케치 알고리즘을 포함해 흔한 알고리즘 트릭에 대해 비교적 잘 안다고 생각했다. 하지만 나는 어쩌다 MinHash를 한 번도 접해 본 적이 없었고, 심지어 그런 알고리즘(locality-sensitive hashing)이 존재한다거나 실용적이라는 사실조차 알지 못했다!

이 트릭이 어떻게 동작하는지 배우고 파고드는 과정이 정말 즐거웠다. 이 블로그 글이 더 많은 엔지니어들에게 이 기법을 처음으로 소개하고, 누군가의 이해에서 빈틈을 메우는 데 도움이 되길 바란다. 나는 멋진 수학적/알고리즘적 트릭을 정말 좋아한다!

후기: MinHash와 HyperLogLog

이 글을 조사하고 쓰는 동안, 핵심 MinHash 트릭이 고전적이고 꽤 유명한 스케치인 HyperLogLog를 약간 떠올리게 한다는 것을 깨달았다.

HyperLogLog의 핵심 아이디어(훨씬 더 오래된 알고리즘으로 거슬러 올라간다)는 스트림의 각 원소를 해시한 뒤, 그 해시 스트림에서 “앞부분 0의 개수”의 러닝 최댓값을 저장하는 것이다.

세부 사항에서는 알고리즘이 매우 다르지만, 분명한 유사성이 있다. 두 경우 모두 해시 함수를 사용해 입력 원소를 균일 분포로 매핑한 뒤, 러닝 최댓값/최솟값을 계산하는데, 적절한 계산을 거치면 입력에 대한 상수 크기의 요약만으로 어떤 분포적 특성을 추정할 수 있다.

사실 두 알고리즘은 처음 보기에 보이는 것보다 훨씬 더 유사하다고 주장하고 싶다. HyperLogLog는 앞부분 0의 개수(최하위 비트 쪽의 0)를 센다. 하지만 우리는 해시 함수가 \([0, 2^N)\)에서 균일한 값을 출력한다고 가정하므로, 비트 순서를 뒤집어 최상위 비트 쪽의 0 개수를 세는 것으로 생각해도 무방하다. 그런데 N비트 수 \(x\)가 주어졌을 때, 상위 비트의 0 개수는 \(\log_2(x)\)와 밀접하게 관련되어 있다 — 앞부분 0이 많을수록 \(x\)는 작아진다. 따라서 HyperLogLog를 MinHash의 \(H(x)\)와 비교했을 때 \(log_2(H(x))\)의 러닝 최솟값을 계산하는 것으로 생각해도 무방하다.

게다가 HyperLogLog와 MinHash가 (어느 정도) 서로 쌍대라는 의미가 있음이 드러난다. 두 개의 서로 다른 집합에 대한 두 HyperLogLog 구조가 주어지면, 이를 결합해 합집합의 크기를 추정할 수 있다. 그 집합들에 대한 두 MinHash 구조가 주어지면, 이를 비교해 교집합의 (상대적) 크기를 추정할 수 있다.

따라서 두 구조를 결합하면 임의의 집합들의 교집합과 합집합 모두에 대해 질문할 수 있는 스케치를 만들 수 있다! 이 아이디어는 적어도 2013년에는 이미 알려진 바 있으며, 두 자료구조의 아이디어를 흥미로운 방식으로 결합하는 스케치에 대한 연구가 계속되고 있음이 드러났다. 정말 멋지다고 생각한다!

부록: 문서를 집합으로 표현하기

문서를 집합으로 표현하는 문제로 돌아오겠다고 약속했으니, 두 가지 일반적인 접근법에 대해 간단히 메모를 남기겠다.

우선, 이 두 전략 중 하나를 적용하기 전에 문서를 어떤 식으로든 정규화하고 싶을 수 있다. 예를 들어 표준 유니코드 정규화 형식으로 변환하고 싶을 것이고, 대소문자를 통일하거나 연속된 공백을 하나로 합치는 등의 변환도 수행하고 싶을 수 있다.

n-gram 일명 “shingle”

문서에 등장하는 모든 n-gram 집합으로 문서를 표현할 수 있으며, 적절한 \(n\) 값을 선택하면 된다. 대규모 텍스트 처리 분야에서는 종종 문헌에서 “n-gram” 대신 “shingle”이라는 단어를 사용하지만, 나는 그 용어가 불필요하게 혼란스럽다고 생각한다. 어떤 \(n\) 값이든 선택할 수 있으며, 주요 트레이드오프는 작은 값을 선택할수록 문서를 더 거칠게 비교하게 되고(예컨대 대부분의 영어 텍스트는 bigram 관점에서 보면 꽤 비슷해 보일 것이다), 큰 값을 선택하면 더 많은 개별 피처가 생겨 더 큰 집합이 만들어진다는 점이다. 어느 한계에 이르면 민감도도 떨어질 것으로 예상하지만, 그보다 먼저 성능 문제가 발생할 것으로 짐작한다.

내가 찾은 한 자료에 따르면³, 다양한 응용 분야에서 5에서 9 사이의 \(n\) 값이 일반적인 선택으로 보인다.

단어 분리

대신 입력을 “단어” 혹은 “토큰”으로 나누어 이를 피처로 사용할 수도 있다. 위 GPT-3 논문 발췌문에서는 “Spark의 표준 토크나이저”를 언급하는데, 이는 입력을 소문자로 바꾼 뒤 공백을 기준으로 나누는 이 클래스를 가리키는 것으로 보인다.

더 정교한 토크나이저를 사용할 수도 있고, 토큰화한 뒤 토큰의 n-gram을 사용하는 방식으로 두 접근법을 혼합할 수도 있다. 이 경우에는 개별 토큰이 바이트나 문자보다 훨씬 더 높은 엔트로피를 가져야 하므로 더 작은 \(n\) 값을 사용하게 될 것이다.

1. SELECT ... FROM table ORDER by random() LIMIT 1을 작성해 본 적이 있다면, 비슷한 트릭을 사용해 본 것이다! ↩︎

2. 궁금하다면, Spark는 해시 패밀리 선택을 문서화하고 있으며, 관련 문헌 참조도 함께 제공한다. ↩︎

3. Mining of Massive Datasets §3.2.2 ↩︎