무작위 초평면 해싱: 충돌 확률을 유도하고 recall을 확률로 읽기

벡터 검색 엔진의 설정 파일에는 대개 숫자 두 개가 있습니다. 해시 비트 수와 테이블 개수입니다.

index:
  type: lsh
  num_bits: 16       # k
  num_tables: 50     # L

이 둘을 어떻게 정하는지가 문제입니다. 비트를 늘리면 후보가 줄어 빨라지지만 놓치는 이웃이 생기고, 테이블을 늘리면 덜 놓치지만 메모리와 시간이 그만큼 듭니다. 보통은 몇 번 돌려 보고 정합니다.

그런데 이 트레이드오프는 손으로 계산할 수 있습니다. 두 벡터가 같은 해시값을 가질 확률이 각도만으로 정확히 적히기 때문입니다. 이 글은 그 확률을 유도하고, $k$ 와 $L$ 이 그것을 어떤 곡선으로 바꾸는지, 그 곡선에서 recall과 후보 수를 어떻게 읽는지를 정리합니다.

지난 글에서 무작위 사영이 거리를 보존한다는 것을 봤습니다. 이번에는 사영한 값을 통째로 쓰지 않고 부호 한 비트만 남깁니다.

부호 한 비트

초평면 하나가 하는 일

무작위 벡터 $r$ 을 표준정규분포에서 뽑고, 벡터 $x$ 에 대해 이렇게 정의합니다.

$$h_r(x) = \operatorname{sign}(r \cdot x) \in \{0, 1\}$$

$r$ 에 수직인 초평면이 공간을 둘로 가르고, $x$ 가 어느 쪽에 있는지를 한 비트로 적는 것입니다. 이것을 무작위 초평면 해싱이라고 부릅니다.

두 벡터 $u, v$ 가 사이각 $\theta$ 를 이룬다고 할 때, 둘이 같은 비트를 받을 확률을 구해 보겠습니다. 이것을 충돌 확률이라고 부릅니다 — 해싱에서 서로 다른 입력이 같은 값을 받는 것을 충돌이라 하는데, 여기서는 그게 원하는 일입니다.

핵심은 $u$ 와 $v$ 가 만드는 평면만 보면 된다는 것입니다. $r \cdot u$ 와 $r \cdot v$ 는 $r$ 을 그 평면에 정사영한 성분만으로 정해지고, 나머지 $d-2$ 개 방향은 두 내적 어디에도 안 들어갑니다. 그리고 표준정규분포는 회전에 대해 대칭이므로, 그 평면 위에서 본 $r$ 의 방향은 원 위에서 균등합니다.

이제 그 평면에서 그림을 그립니다. 초평면은 이 평면을 원점을 지나는 직선 하나로 자릅니다. 그 직선이 $u$ 와 $v$ 사이를 지나면 둘의 부호가 갈리고, 지나지 않으면 같습니다. 직선의 방향은 $\pi$ 만큼 돌리면 자기 자신이므로 전체 후보가 $\pi$ 만큼이고, 그중 $u$ 와 $v$ 사이는 $\theta$ 만큼입니다.

$$P\bigl[h_r(u) \ne h_r(v)\bigr] = \frac{\theta}{\pi}, \qquad p \;=\; P\bigl[h_r(u) = h_r(v)\bigr] = 1 - \frac{\theta}{\pi}$$

128차원에서 초평면 200만 개를 뽑아 확인했습니다.

import numpy as np
rng = np.random.default_rng(0)
d = 128

for deg in [10, 30, 45, 60, 90, 120]:
    th = np.deg2rad(deg)
    u = np.zeros(d); u[0] = 1
    v = np.zeros(d); v[0] = np.cos(th); v[1] = np.sin(th)
    R = rng.standard_normal((2_000_000, d))
    same = np.mean(np.sign(R @ u) == np.sign(R @ v))
    print(f"θ={deg:3d}°  cos={np.cos(th):+.3f}  실측 p={same:.5f}  이론 {1-th/np.pi:.5f}")

θ= 10°  cos=+0.985  실측 p=0.94450  이론 0.94444
θ= 30°  cos=+0.866  실측 p=0.83341  이론 0.83333
θ= 45°  cos=+0.707  실측 p=0.74984  이론 0.75000
θ= 60°  cos=+0.500  실측 p=0.66700  이론 0.66667
θ= 90°  cos=+0.000  실측 p=0.50004  이론 0.50000
θ=120°  cos=-0.500  실측 p=0.33275  이론 0.33333

크기가 빠진 자리

식에 무엇이 없는지가 무엇이 있는지만큼 중요합니다.

먼저 원래 차원 $d$ 가 없습니다. 768차원이든 3072차원이든 같은 각도면 같은 확률입니다. 위 실험이 128차원에서 돌았는데도 이론과 맞는 이유가 이것입니다.

그리고 벡터의 크기가 없습니다. $h_r(x)$ 는 $x$ 를 두 배로 늘려도 같은 값을 내므로, 이 해시는 방향만 보고 길이는 통째로 버립니다. 코사인 유사도로 검색하는 자리에서는 문제가 없지만, 길이가 뜻을 갖는 벡터 — 이를테면 등장 횟수를 담은 벡터나 정규화하지 않은 임베딩 — 에는 그대로 쓸 수 없습니다. 크기까지 재려면 뒤에 볼 유클리드 거리용 해시족으로 갑니다.

마지막으로 확률이 코사인이 아니라 각도에 선형입니다. 코사인 유사도로 순위를 매기는 검색에 각도 기반 해시를 쓰는 것이라, 순위는 같지만 눈금이 다릅니다 — 코사인 0.99와 0.90의 차이가 각도로는 $8^\circ$ 와 $26^\circ$ 로 벌어집니다.

원점과 경계

유도에서 조용히 쓴 가정이 하나 있습니다. 초평면이 원점을 지난다는 것입니다. $h_r(x) = \operatorname{sign}(r\cdot x)$ 에는 상수항이 없으므로 가르는 면이 언제나 원점을 통과합니다.

그래서 데이터를 평행이동하면 결과가 바뀝니다. 전처리로 평균을 빼는 중심화는 다른 알고리즘에서는 대개 무해한데 여기서는 아닙니다 — 원점이 옮겨지면 모든 벡터의 사이각이 달라지고, 충돌 확률이 통째로 바뀝니다. 임베딩의 평균이 0에서 멀리 떨어져 있는 경우가 흔하므로, 중심화를 할 것인지 말 것인지는 이 해시를 쓰기 전에 정해 두고 그다음에는 바꾸지 않아야 합니다.

경계도 짚고 갑니다. $r \cdot x$ 가 정확히 0이면 부호가 정해지지 않는데, $r$ 을 연속분포에서 뽑았으므로 그 일이 일어날 확률은 0입니다. 구현에서는 0을 한쪽으로 몰아 주면 되고, 유도에는 영향이 없습니다.

AND와 OR로 만드는 S자

선형으로는 못 거른다

확률이 각도에 선형이라는 것이 유도의 결과인데, 검색에는 이게 문제입니다. $30^\circ$ 짜리 진짜 이웃의 충돌 확률이 0.833이고 $90^\circ$ 짜리 무관한 점도 0.500입니다. 1.67배 차이로는 거를 수 없습니다. 100만 개 중 무관한 것 50만 개가 후보로 들어옵니다.

AND와 OR

AND — 비트 $k$ 개를 이어 붙인다. 초평면 $k$ 개를 독립으로 뽑아 비트 $k$ 개를 만들고, 전부 같아야 같은 버킷에 넣습니다. 독립이므로 확률이 곱해집니다.

$$p_{\text{AND}} = p^k$$

구현은 단순합니다. 비트 $k$ 개를 정수 하나로 묶어 사전의 키로 쓰면 되고, 그러면 가능한 버킷이 $2^k$ 개입니다. $k = 16$ 이면 65,536개이고 $k = 24$ 면 1,678만 개인데, 실제로 만들어 두는 것은 값이 들어온 버킷뿐이라 사전 크기는 데이터 개수를 넘지 않습니다.

$k=16$ 이면 $30^\circ$ 는 $0.8333^{16} = 0.0541$, $90^\circ$ 는 $0.5^{16} = 0.0000153$ 입니다. 비가 1.67배에서 3,500배로 벌어졌습니다. 대신 진짜 이웃도 94.6%를 놓칩니다.

OR — 테이블 $L$ 개를 만든다. 위 절차를 독립으로 $L$ 번 반복해 해시 테이블을 $L$ 개 만들고, 하나라도 같은 버킷에 들어가면 후보로 뽑습니다. 여집합으로 계산합니다.

$$P[\text{후보로 뽑힘}] = 1 - (1 - p^k)^L$$

이 한 줄이 이 글의 결론입니다. $L=50$ 을 넣으면 $30^\circ$ 는 $1 - (1-0.0541)^{50} = 0.938$ 로 돌아오고, $90^\circ$ 는 $1 - (1-0.0000153)^{50} = 0.00076$ 에 그칩니다.

문턱과 기울기

곡선이 S자가 됩니다. AND가 확률을 급격히 눌러 놓고 OR이 높은 쪽만 다시 끌어올리므로, 어느 각도를 경계로 「거의 다 뽑힘」과 「거의 다 버려짐」이 갈립니다. 문턱의 위치는 $p^k \approx 1/L$ 인 자리, 즉

$$p^* = \left(\frac{1}{L}\right)^{1/k}, \qquad \theta^* = \pi\,(1 - p^*)$$

입니다. $k=16, L=50$ 이면 $p^* = 50^{-1/16} = 0.783$ 이라 $\theta^* \approx 39^\circ$ 입니다.

이 값은 어림입니다. $p^k = 1/L$ 을 넣으면 실제 확률이 $1-(1-1/L)^L \approx 1-e^{-1} = 0.632$ 라 절반이 아니라 63%이기 때문입니다. 정확히 절반이 되는 각도를 원하면 $1-(1-p^k)^L = 0.5$ 를 이분법으로 풀면 되고, $k=16, L=50$ 에서는 $42.3^\circ$ 가 나옵니다. 3도 차이라 감을 잡는 데는 어림으로 충분하고, 설정을 확정할 때만 한 번 풀어 보면 됩니다.

두 손잡이가 하는 일도 수로 갈립니다. 문턱에서 곡선의 기울기를 함께 재 봤습니다.

고정	바꾼 값	문턱 $\theta$	문턱에서의 기울기
$L=50$	$k=8$	74.7°	4.8
$L=50$	$k=16$	42.3°	7.3
$L=50$	$k=32$	22.6°	12.8
$k=16$	$L=10$	28.0°	6.8
$k=16$	$L=50$	42.3°	7.3
$k=16$	$L=250$	55.4°	8.0

문턱은 둘 다 움직이지만 기울기는 사실상 $k$ 만 정합니다. $k$ 를 여덟에서 서른둘로 올리는 동안 기울기가 2.7배가 됐는데, $L$ 을 25배 늘린 쪽은 6.8에서 8.0으로 18%밖에 안 움직였습니다. $k$ 가 칼날의 날카로움이고 $L$ 은 그 칼을 어디에 대는가입니다.

예측 recall과 실측의 대조

심은 이웃으로 재기

식은 「같은 버킷에 들어갈 확률」인데 실무에서 재는 것은 recall, 즉 진짜 이웃 중 몇 개를 후보에 담았는가입니다. 둘이 같은 값인지 확인해 보겠습니다. 128차원 단위구에서 질의 벡터를 뽑고 그로부터 정확히 $\theta$ 만큼 떨어진 이웃을 심은 뒤, 실제로 해싱해 잡히는 비율을 셌습니다.

def plant(q, deg):                          # q 에서 정확히 deg 도 떨어진 벡터
    z = rng.standard_normal(d)
    z -= (z @ q) * q                        # q 성분을 빼서 수직으로
    z /= np.linalg.norm(z)
    th = np.deg2rad(deg)
    return np.cos(th)*q + np.sin(th)*z

def measure(k, L, deg, trials=4000):
    hit = 0
    for _ in range(trials):
        q = rng.standard_normal(d); q /= np.linalg.norm(q)
        x = plant(q, deg)
        for _ in range(L):
            H = rng.standard_normal((d, k))
            if np.all((q @ H > 0) == (x @ H > 0)):
                hit += 1; break
    return hit / trials

이웃 각도    p       (k, L)      예측 1-(1-p^k)^L    실측
  10°     0.9444   (16, 10)         0.994          0.995
  20°     0.8889   (16, 10)         0.807          0.812
  30°     0.8333   (16, 10)         0.427          0.428
  45°     0.7500   (16, 10)         0.096          0.094
  60°     0.6667   (16, 10)         0.015          0.013
  30°     0.8333   (16, 50)         0.938          0.935
  45°     0.7500   (16, 50)         0.396          0.399
  60°     0.6667   (16, 50)         0.073          0.071

여덟 줄 전부 소수 둘째 자리까지 맞습니다. recall은 측정해야 아는 값이 아니라 각도 분포만 알면 계산되는 값입니다.

재정렬이 있어야 한다

여기서 한 단계가 빠져 있습니다. 해시가 주는 것은 후보 목록이지 답이 아닙니다. 같은 버킷에 들어왔다는 것만으로는 어느 것이 더 가까운지 알 수 없고, 후보 안에는 운 좋게 걸린 먼 점도 섞여 있습니다.

그래서 실제 검색은 후보를 뽑은 뒤 정확한 거리로 다시 계산해 정렬합니다. 이 단계를 재정렬이라고 부릅니다. 재정렬이 있어야 위에서 잰 recall이 최종 정확도로 이어지고, 없으면 버킷 안의 순서가 그대로 답이 되어 품질이 무너집니다.

비용은 후보 수에 그대로 비례합니다. 후보가 $m$ 개이고 차원이 $d$ 이면 곱셈이 $md$ 번이라, 후보 수 표가 곧 질의 시간 표입니다. 다음 절의 표를 그렇게 읽으면 됩니다.

recall@10과 이웃 하나의 확률

위 식이 답하는 것은 「특정 이웃 하나가 잡힐 확률」인데, 실무에서 보는 지표는 대개 recall@10 — 진짜 상위 10개 중 몇 개를 담았는가 — 입니다. 둘이 어떻게 이어질까요.

기댓값 수준에서는 그냥 같습니다. 이웃 열 개가 각각 확률 $p_i$ 로 잡히면 담긴 개수의 기댓값이 $\sum p_i$ 이고, 이것을 10으로 나눈 것이 recall@10의 기댓값이라 평균 확률과 같아집니다. 열 개의 사건이 서로 독립일 필요도 없습니다 — 합의 기댓값은 언제나 기댓값의 합이기 때문입니다.

달라지는 것은 흔들림입니다. 상위 10개는 서로 가까이 모여 있는 경우가 많아 같은 테이블에서 함께 잡히거나 함께 빠지는 쪽으로 붙습니다. 그래서 recall@10의 평균은 예측대로인데 질의마다의 편차는 독립을 가정한 값보다 큽니다. 평균만 보고 설정을 고르면 꼬리에 있는 질의가 유난히 나쁜 것을 못 봅니다.

후보 수와 메모리 비용

후보 수의 기댓값

recall만 보면 $L$ 을 무한히 키우면 됩니다. 값을 치르는 쪽은 후보 수입니다.

데이터가 $N$ 개일 때, 질의와 무관한 점들은 앞 글에서 본 대로 고차원에서 거의 직교합니다 — 각도가 $90^\circ$ 근처라 $p \approx 0.5$ 입니다. 그러면 테이블 하나당 같은 버킷에 들어오는 무관한 점의 기댓값이 $N \cdot 0.5^k$ 이고, $L$ 개를 합치면 이렇습니다.

$$\mathbb{E}[\text{후보 수}] \;\lesssim\; N \cdot L \cdot 2^{-k}$$

여기서 $L$ 번의 조회 자체는 비용에 안 들어갑니다. 버킷이 $2^k$ 개인데 값이 든 것은 최대 $N$ 개뿐이라 대부분의 조회가 빈 버킷을 만나 그냥 끝나기 때문입니다. $N = 10^6$, $k = 24$ 면 버킷 1,678만 개에 점 100만 개라 열에 여섯은 비어 있습니다. 그래서 비용을 재는 단위가 조회 횟수가 아니라 후보 수입니다.

k와 L을 함께 올리는 쪽이 앞선다

$N = 10^6$ 으로 값을 넣어 표를 만들면 두 축이 함께 보입니다.

$k$	$L$	후보 수	$30^\circ$ recall	$45^\circ$ recall
12	20	4,883	0.907	0.475
16	10	153	0.427	0.096
16	50	763	0.938	0.396
20	50	48	0.733	0.147
20	200	191	0.995	0.470
24	200	12	0.920	0.182
24	1000	60	1.000	0.634

읽는 법이 세 가지입니다.

첫째, $k$ 와 $L$ 을 함께 올리는 쪽이 앞섭니다. 위 일곱 조합 중 다른 어떤 조합에도 지지 않는 것은 $k=24$ 짜리 둘뿐입니다. $(12, 20)$ 은 후보를 4,883개나 훑고도 recall이 0.907이라, 후보 60개로 1.000을 내는 $(24, 1000)$ 에 모든 면에서 밀립니다. $k$ 를 1 늘리면 후보가 절반이 되므로, 그 여유로 $L$ 을 두 배 늘리면 후보 수는 그대로면서 recall만 오릅니다.

둘째, 그래서 값을 치르는 곳은 시간이 아니라 메모리입니다. $L$ 은 테이블 개수라 전체 데이터를 $L$ 번 저장합니다. $L = 1000$ 이면 인덱스가 원본의 천 배입니다. 위 표에서 $k$ 와 $L$ 을 함께 올리는 것이 공짜처럼 보이는 이유는 세로축에 메모리가 없기 때문입니다. LSH가 실무에서 HNSW 같은 그래프 기반 방법에 밀리는 자리가 대개 여기입니다.

셋째, 먼 이웃은 어차피 못 잡습니다. $45^\circ$ 열을 보면 후보 60개짜리 설정에서도 0.634이고, 대부분의 조합이 0.5 아래입니다. S자 문턱을 $45^\circ$ 까지 밀려면 $k$ 를 낮춰야 하는데 그러면 후보가 폭발합니다.

다중 프로브

메모리를 깎는 방법이 하나 있습니다. 질의가 떨어진 버킷만 보지 않고 비트 하나를 뒤집은 이웃 버킷까지 함께 훑는 것입니다. 이것을 다중 프로브라고 부릅니다.

근거는 앞 절의 경계 이야기입니다. 이웃인데 놓친 쌍은 대개 초평면 하나가 둘 사이를 아슬아슬하게 지난 경우이고, 그러면 그 한 비트만 다릅니다. 그 비트를 뒤집은 버킷을 함께 보면 테이블을 더 만들지 않고도 같은 이웃을 잡습니다.

맞바꿈이 분명합니다. 같은 recall을 얻는 데 드는 $L$ 이 줄어드는 만큼 메모리가 $L$ 배에서 그만큼 깎이고, 대신 질의 한 번에 하는 조회가 $L$ 번에서 $L \times (\text{프로브 수})$ 번으로 늡니다. 조회가 싸다는 앞의 관찰이 이 맞바꿈을 성립하게 하는 자리입니다.

유사도마다 다른 해시족

MinHash

각도 말고 다른 유사도를 재야 할 때가 있습니다. 문서를 낱말의 집합으로 볼 때 쓰는 자카드 유사도 — 두 집합의 교집합 크기를 합집합 크기로 나눈 값 — 가 대표적입니다.

여기에 맞는 해시가 MinHash입니다. 낱말 전체에 무작위 순서를 하나 매기고, 각 집합에서 그 순서로 가장 앞선 원소를 해시값으로 씁니다. 두 집합이 같은 값을 받는다는 것은 합집합에서 가장 앞선 원소가 하필 교집합에 있었다는 뜻이고, 순서가 무작위이므로 그 확률이 그대로

$$P[\text{충돌}] = \frac{|A \cap B|}{|A \cup B|} = J(A, B)$$

입니다. 충돌 확률이 자카드값 자체라 초평면 해싱보다도 식이 간단합니다.

p-stable 해시

유클리드 거리를 그대로 재려면 또 다른 해시족을 씁니다. 무작위 방향 $a$ 로 사영한 값을 폭 $w$ 짜리 칸으로 자르는 것입니다.

$$h_{a,b}(x) = \left\lfloor \frac{a \cdot x + b}{w} \right\rfloor, \qquad b \sim U[0, w)$$

$b$ 는 칸의 경계를 무작위로 밀어 주는 값입니다. 두 점이 같은 칸에 들어갈 확률은 둘의 거리 $c$ 가 $w$ 에 비해 얼마나 작은지로 정해지고, $c$ 가 0에 가까우면 1, $c$ 가 $w$ 의 두 배쯤이면 0.2 아래로 떨어집니다. $w$ 가 「어느 정도까지를 가깝다고 볼 것인가」를 쥔 손잡이이고, 초평면 해싱에 없던 것이 이 손잡이입니다 — 각도는 이미 0에서 $\pi$ 로 눈금이 정해져 있었습니다.

공통 틀

세 해시족은 재는 것이 다른데 쓰는 방식은 하나입니다.

세 곡선이 공유하는 것은 충돌 확률이 유사도의 증가함수로 적힌다는 성질뿐입니다. 그리고 이 글의 나머지 — AND로 $p^k$, OR로 $1-(1-p^k)^L$, 문턱 $p^* = L^{-1/k}$, 후보 수 $NL2^{-k}$ — 는 $p$ 가 어디서 왔는지를 전혀 묻지 않습니다. $p$ 를 주는 함수만 갈아 끼우면 $k$ 와 $L$ 계산이 그대로 따라옵니다.

그림에서 눈여겨볼 것은 세 곡선의 기울기가 다르다는 점입니다. MinHash는 자카드값을 그대로 쓰므로 직선이고, 초평면 쪽은 유사도가 1에 가까워질 때 가파르게 오릅니다. 같은 $k$ 를 걸어도 어느 해시족이냐에 따라 S자가 서는 자리가 달라진다는 뜻입니다.

16과 50이 정하는 것

각도 분포를 재는 절차

지금까지 $k$ 와 $L$ 에서 문턱을 계산했는데, 실제로 정해야 하는 순서는 반대입니다. 먼저 데이터의 각도 분포를 재고 거기서 문턱을 정한 다음 $k$ 와 $L$ 을 역산합니다. 재는 절차는 두 줄입니다.

1. 점을 무작위로 짝지어 각도를 재고 히스토그램을 그립니다 — 무관한 쌍의 분포입니다.
2. 각 점의 진짜 최근접 이웃 몇 개를 찾아 그 각도의 히스토그램을 따로 그립니다.

128차원 단위벡터 20,000개로 해 봤습니다.

겹치는 폭이 좁아야 한다

그림에서 읽을 것이 둘입니다.

먼저 두 분포가 갈리는 자리가 $75^\circ$ 입니다. 무작위 쌍은 평균 $90^\circ$ 에 표준편차 $5.1^\circ$ 로 모여 있고 최근접 10 이웃은 93%가 $70^\circ$ 와 $75^\circ$ 사이라, 겹치는 구간이 거의 없습니다. 문턱을 세울 자리가 있다는 뜻입니다.

그런데 설정 파일의 $39^\circ$ 는 그 자리에서 한참 왼쪽입니다. 이 데이터에 $k=16, L=50$ 을 걸면 이웃을 하나도 못 잡습니다. 문턱을 $75^\circ$ 로 옮기려면 표에서 본 대로 $k=8, L=50$ 인데, 그러면 후보 수가 $20{,}000 \times 50 / 2^8 \approx 3{,}900$ 개로 전체의 20%가 됩니다. 문턱이 설 자리는 있는데 그 자리에서는 거를 것이 거의 안 걸리는 상태입니다.

이유는 이 데이터가 무작위 점이기 때문입니다. 정규분포에서 뽑은 점들에는 이웃 구조라는 것이 아예 없고, 「최근접 10개」라고 부른 것도 그저 $90^\circ$ 분포의 왼쪽 꼬리에 있는 점들입니다. 진짜 임베딩에서는 이웃이 $20^\circ$ 에서 $40^\circ$ 사이에 서고, 그래서 $39^\circ$ 짜리 문턱이 뜻을 갖습니다. 같은 그림을 자기 데이터로 그려 보는 것이 $k$ 와 $L$ 을 고르는 첫 걸음인 이유가 이것입니다.

그래서 16과 50은

설정 파일의 num_bits: 16, num_tables: 50으로 돌아가면 그 둘이 무엇을 정하는지 말할 수 있습니다.

둘은 S자 곡선의 문턱과 날카로움을 정하는 값입니다. 문턱은 $p^* = L^{-1/k}$ 로 $39^\circ$ — 정확히 절반이 되는 자리로는 $42^\circ$ — 이고, 그보다 가까운 것은 대부분 담기고 먼 것은 대부분 버려집니다. 날카로움은 거의 $k$ 혼자 정합니다. 인덱스는 원본의 50배가 들고, 질의당 훑는 후보는 데이터 100만 개 기준 763개이며, 그 763개를 정확한 거리로 다시 정렬하는 것이 질의 시간의 본체입니다.

이 숫자들은 전부 $p = 1 - \theta/\pi$ 한 줄에서 나옵니다. 돌려 보고 정할 것은 데이터의 각도 분포뿐이고, 그것만 알면 나머지는 계산입니다.

정리

• 무작위 초평면 하나로 두 벡터가 같은 쪽에 놓일 확률은 $p = 1 - \theta/\pi$ 다. 두 벡터가 만드는 평면 위에서 초평면이 그리는 직선이 둘 사이를 지나는지만 보면 되고, 그 방향이 균등하므로 확률이 각도의 비다.
• 식에 없는 것이 셋이다 — 원래 차원 $d$, 벡터의 크기, 그리고 상수항이다. 128차원에서 초평면 200만 개로 잰 값이 여섯 각도 모두 이론과 소수 넷째 자리까지 맞았고, 대신 길이가 뜻을 갖는 벡터에는 못 쓰며 데이터를 평행이동하면 결과가 통째로 바뀐다.
• 확률이 각도에 선형이라 $30^\circ$ 의 0.833과 $90^\circ$ 의 0.500이 1.67배 차이뿐이다. 그대로는 거를 수 없다.
• 비트 $k$ 개를 AND로 묶으면 $p^k$, 테이블 $L$ 개를 OR로 묶으면 $1-(1-p^k)^L$ 이다. 둘이 만나 S자 문턱을 만들고, 문턱은 $p^* = L^{-1/k}$ 에 선다 — $k=16, L=50$ 이면 $39^\circ$ 이고 정확히 절반이 되는 자리는 $42.3^\circ$ 다. 문턱은 둘 다 움직이지만 기울기는 $k$ 가 정한다.
• 심은 이웃으로 실제 recall을 재 보니 여덟 설정 전부 예측과 소수 둘째 자리까지 맞았다. 다만 후보를 정확한 거리로 다시 정렬하는 단계가 있어야 그 recall이 정확도가 되고, recall@10의 평균은 이웃 하나의 확률과 같지만 편차는 그보다 크다.
• 후보 수는 무관한 점들이 $90^\circ$ 근처라 $N L 2^{-k}$ 정도다. $k$ 를 1 늘리면 후보가 절반이므로 $k$ 와 $L$ 을 함께 올리는 쪽이 언제나 앞선다 — 일곱 조합 중 밀리지 않은 것은 $k=24$ 짜리 둘뿐이었다.
• 대신 인덱스가 원본의 $L$ 배다. 후보 수 표에 안 보이는 값이 메모리이고, LSH가 밀리는 자리가 대개 거기다. 비트 하나를 뒤집은 버킷까지 훑는 다중 프로브가 그 $L$ 을 깎는 대신 조회 수를 늘린다.
• 틀은 해시족과 무관하다. 자카드에는 충돌 확률이 그대로 자카드값인 MinHash, 유클리드 거리에는 $\lfloor (a\cdot x + b)/w \rfloor$ 가 있고, $p$ 를 주는 함수만 갈아 끼우면 $k$ 와 $L$ 계산이 그대로 따라온다.
• $k$ 와 $L$ 을 고르기 전에 데이터의 각도 분포를 보고 「어디까지가 이웃인가」를 정하는 것이 먼저다. 무작위 벡터 20,000개로 그려 보면 두 분포가 $75^\circ$ 에서 갈리는데, 그 자리에 문턱을 세우면 전체의 20%가 후보로 들어온다 — 무작위 점에는 애초에 이웃 구조가 없기 때문이고, $39^\circ$ 짜리 설정이 뜻을 갖는 것은 이웃이 그보다 가까이 모인 데이터에서다.

---

읽어주셔서 감사합니다. 😊