두 집합 사이의 거리에 대한 두 증명

두 유한집합 A,B에 대해, J_{\delta}(A,B)의 값을 다음과 같이 정의한다. (단 둘 다 공집합인 경우는 제외한다)

\displaystyle J_{\delta}(A,B) = 1-\frac{|A \cap B|}{|A \cup B|}

이 값은 두 집합 사이의 상관관계를 나타내는 척도가 된다. 예컨대 A=B이면 0이 되고, A \cap B = \emptyset인 경우는 1이 되는 등, 상대적으로 겹치는 정도가 클 수록 0에 가까워져 일종의 거리처럼 생각할 수 있게 된다. 이것이 실제로 수학에서 정의되는 거리(metric)가 되려면 다음과 같은 삼각부등식이 성립해야함을 증명해야 한다.

J_{\delta}(A,C) \leq J_{\delta}(A,B)+J_{\delta}(B,C)

J_{\delta}는 식물학자 Paul Jaccard의 이름을 따 Jaccard metric/Jaccard distance라 불리며, 위 삼각부등식은 현재까지도 복잡한 증명에서부터 간단한 증명까지 여러 새로운 증명이 발견되고 있다. 여기에서는 간단하면서도 그 성격과 맥락이 매우 대조적인 두 증명을 소개하고자 한다.

먼저 가장 직설적인 증명부터. StackExchange에 올라왔던 증명이다. 세 집합 A,B,C로 만들어지는 벤다이어 그램에서 위와 같이 일곱 개의 각각의 영역에 해당하는 부분의 원소의 개수를 x_{001}, x_{010},\ldots, x_{111}으로 둔다. 여기서 첨자는 각각의 부분이 A,B,C에 포함되는지 안 되는지 여부를 가리키는데, 예컨대 x_{101}A,C에는 속하나 B에는 안 속하는 (A\ \cap C)-B의 원소의 개수가 됨. 그러면 증명하고자 하는 부등식을 다음과 같이 표현할 수 있다.

이 식을 전개하면 모든 계수가 양수인 다항식이 나와 증명이 끝난다.

두 번째 증명. 먼저, 편의상 A \cup B \cup C의 원소를 $1, 2, \ldots, n$으로 둔다. 이 때 순열 \pi \in S_n에 대해, A=\{a_1, a_2, \ldots, a_i \}\pi를 적용하면 \pi(A)=\{\pi(a_1), \pi(a_2), \ldots, \pi(a_i)\}가 된다고 생각할 수 있다. 예컨대 n=5, A=\{2,3\}이고 \pi(1)=5, \pi(2)=4, \pi(3)=1, \pi(4)=2, \pi(5)=3인 경우 \pi(A)=\{1,4\}가 된다. 순열 \piS_n에서 균일하게 랜덤으로 선택된다고 생각한다. 그러면 두 집합 A,B에 대해 \pi(A)\pi(B)의 최솟값이 같을 확률이 \frac{|A \cap B|}{|A \cup B|}가 됨을 알 수 있다. (순서대로 나열해서 표현했을 때 A \cup B의 원소가 아닌 것들은 고려할 필요가 없으니 다 지우고, 가장 처음으로 등장하는 원소가 A \cap B의 원소여야 하므로) 즉 \min(\pi(A)) \neq \min(\pi(B))일 확률은 J_{\delta}(A,B)가 된다.

이제 \min(\pi(A)) \neq \min(\pi(B)), \min(\pi(B)) \neq \min(\pi(C)), \min(\pi(A)) \neq min(\pi(C))인 사건을 각각 X, Y, Z라 둔다. 그러면 Z라는 사건이 일어난다면 XY 둘 중 하나가 일어나야 하므로, \text{Pr}(Z) \leq \text{Pr}(X \vee Y) \leq \text{Pr}(X)+\text{Pr}(Y)가 되어 증명이 끝난다. Minhashing을 이용한 증명으로, Mining of Massive Datasets 등의 텍스트에서 찾아볼 수 있다.

Elegant Math 계정에서 작성한 트윗 타래를 정리. (2018/12/23)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중