[Finding Similar Items]

1.What is the Most Similar Image?

가장 유사한 이미지 찾기란, 500만 개의 이미지 중에서 가장 유사한 이미지를 찾는 과제를 말합니다. 이는 장면 완성 문제(Scene Completion Problem)와도 관련이 있습니다. 장면 완성 문제는 이미지 조각들이 포함된 유사한 장면을 찾아내어 이미지를 설득력 있게 완성하는 것을 목표로 합니다. 이러한 과제들의 동기는 이미지를 픽셀 색상의 벡터로 표현할 수 있다는 점에 있습니다. 주요 도전 과제는 고차원 데이터 포인트 x1, x2, ... 등이 주어졌을 때, 가능한 한 효율적으로 유사성을 어떻게 측정할 것인가입니다. 이를 해결하기 위한 방법으로는 다음과 같은 접근 방식이 있습니다: 특징 추출(Feature Extraction): 이미지로부터 중요한 정보를 추출하는 과정입니다. 예를 들어, 이미지의 색상, 질감, 모양 등을 벡터 형태로 표현할 수 있습니다. 차원 축소(Dimensionality Reduction): 고차원 데이터를 처리하는 것은 매우 어렵기 때문에, 차원 축소 기법을 사용하여 중요한 정보는 보존하면서 데이터의 차원을 줄이는 방법이 있습니다. PCA(주성분 분석), t-SNE, autoencoder 등이 이에 해당합니다. 유사도 측정(Similarity Measurement): 벡터로 표현된 이미지 간의 유사도를 측정합니다. 이를 위해 유클리드 거리, 코사인 유사도, 맨해튼 거리 등 다양한 거리 측정 방법을 사용할 수 있습니다. 효율적인 검색(Efficient Search): 수백만 개의 이미지 중에서 유사한 이미지를 빠르게 찾기 위해서는 효율적인 검색 알고리즘이 필요합니다. k-NN(k-Nearest Neighbors), KD-트리, LSH(Locality-Sensitive Hashing) 등의 방법이 있습니다. 위의 접근 방식을 통해, 대규모 이미지 데이터셋에서 유사한 이미지를 효과적으로 찾아내고, 장면 완성 문제를 해결할 수 있습니다.

2.Common Metaphor

공통적인 비유로, 많은 문제들은 비슷한 객체를 찾는 것으로 표현될 수 있습니다. 이는 고차원 공간에서 이웃을 찾는 것과 유사합니다. 여기에는 다음과 같은 예시들이 포함됩니다: 비슷한 특징을 가진 이미지들 비슷한 단어들을 포함한 페이지들 비슷한 제품을 구매한 고객들 이러한 예시들은 모두 서로 다른 도메인에 속하지만 공통적으로 ‘유사성’을 기반으로 하는 문제를 해결하는 것입니다. 고차원 공간에서 유사한 객체들을 찾는 것은 데이터의 차원이 높아질수록 더욱 어려워집니다. 이러한 문제를 해결하기 위해서는 객체들 간의 유사성을 측정하고, 이를 통해 객체들이 서로 얼마나 가까이 있는지를 파악해야 합니다. 이 과정에서 중요한 것은 '유사성 측정 방법'과 '효율적인 검색 방법'입니다. 유사성 측정 방법으로는 유클리드 거리, 코사인 유사도 등이 있으며, 이러한 측정치를 기반으로 유사한 객체들을 찾아내는 것입니다. 또한, 이러한 유사한 객체들을 빠르고 효율적으로 찾기 위해서는 적절한 검색 알고리즘의 선택이 필요합니다. 결론적으로, 다양한 문제들을 '비슷한 객체를 찾는 문제'로 바라보고 이를 해결하기 위한 방법론들을 적용함으로써, 이러한 문제들에 대한 해결책을 찾아낼 수 있습니다

3.Review: Document Similarity

문서 유사도에 대한 검토에서, 문서들은 '단어의 가방(Bag of Words)'으로 표현될 수 있습니다. 예를 들어, 다음과 같은 문서가 있다고 해봅시다. D1: 하늘은 파랗다. D2: 태양은 밝다. D3: 하늘에 있는 태양은 밝다. D4: 우리는 태양을 본다, 빛나는 태양을. 이들 문서를 '문서-용어 행렬(Document-term matrix)'에 나타내면, 각 문서에서 사용된 단어들과 그 빈도수를 기반으로 문서들 사이의 유사성을 계산할 수 있습니다. 자카드 유사도(Jaccard Similarity)는 이러한 유사성 측정의 한 예로, 두 집합 A와 B가 있을 때, 이들의 교집합 크기를 합집합 크기로 나눈 값으로 정의됩니다. 예를 들어, A와 B의 교집합에 속하는 원소가 3개이고, 합집합에 속하는 원소가 총 8개라면, 자카드 유사도는 3/8이 됩니다. 이 개념을 문서 유사도에 적용하면, 두 문서 사이의 유사성을 단어의 존재 여부를 기반으로 계산할 수 있게 됩니다. 이를 통해 다양한 문서들 사이의 관련성을 평가하고, 비슷한 주제나 내용을 가진 문서들을 찾아낼 수 있습니다.

4.Problem Formulation

문제 정의에 따르면, 목표는 일정 유사도 임계값 d (xi, xj) ≥ s를 만족하는 데이터 포인트 쌍 (xi, xj)을 모두 찾는 것입니다. 주어진 n개의 데이터 포인트에 대해, 단순한 해결책은 O(n^2)의 시간 복잡도를 가집니다. 이 문제를 효율적으로 해결하기 위한 방법으로 'Shingling', 'Min Hashing', 그리고 'Locality Sensitive Hashing' 기법이 있습니다. Shingling: 문서를 'Shingle'이라 불리는 k 길이의 문자열 집합으로 변환합니다. 이는 문서의 내용을 일종의 '지문'처럼 나타내어, 문서의 유사성 비교 기반을 마련합니다. Min Hashing: Shingle 집합을 대표하는 짧은 정수 벡터인 '서명(Signatures)'으로 변환합니다. 이 서명들은 집합들의 유사성을 반영하여, 높은 차원의 데이터를 효율적으로 비교할 수 있게 합니다. Locality Sensitive Hashing (LSH): 서명들 사이에서 실제로 유사성을 테스트해야 하는 '후보 쌍(Candidate pairs)'을 찾습니다. LSH는 유사한 서명을 가진 쌍들을 효율적으로 찾아내어, 전체 쌍을 검사하는 대신 유사할 가능성이 높은 쌍들만을 검사하게 합니다. 이러한 과정을 통해, 대규모 데이터 세트 내에서 유사한 항목들을 효율적으로 찾아낼 수 있으며, n^2의 계산 비용을 크게 줄일 수 있습니다.

5.Shingling

Shingling 과정은 문서를 집합으로 변환하는 첫 번째 단계입니다. 이 과정에서 문서 내에 나타나는 길이 k의 문자열 집합, 즉 k-shingle(또는 k-gram)을 생성합니다. k-shingle은 문서에 나타나는 연속적인 k개의 토큰(문자 또는 단어) 시퀀스를 의미합니다. 이 토큰들은 적용하는 분야에 따라 문자 또는 단어가 될 수 있습니다. 예를 들어, "Data Mining is fun and interesting"이라는 문장이 있다고 가정해 보겠습니다. **Unigram (k = 1)**의 경우, 각 단어가 하나의 토큰으로 취급되어 {"data", "mining", "is", "fun", "and", "interesting"}와 같은 집합을 형성합니다. **Bigram (k = 2)**의 경우, 연속된 두 단어가 하나의 토큰으로 취급되어 {"data mining", "mining is", "is fun", "fun and", "and interesting"}와 같은 집합을 형성합니다. **Trigram (k = 3)**의 경우, 연속된 세 단어가 하나의 토큰으로 취급되어 {"data mining is", "mining is fun", "is fun and", "fun and interesting"}와 같은 집합을 형성합니다. 이러한 방식으로 각 문서를 고유한 집합으로 변환함으로써, 문서 간의 유사성을 보다 효과적으로 비교할 수 있게 됩니다. Shingling은 문서의 내용을 요약하는 고유한 "지문"을 생성하는 과정으로 볼 수 있으며, 이후의 Min Hashing 및 Locality Sensitive Hashing과 같은 단계를 통해 문서 간의 유사성을 효율적으로 계산할 수 있는 기반을 마련합니다.

6.Jaccard Similarity with Shingling

Jaccard 유사도는 두 집합 간의 유사도를 측정하는 방법 중 하나로, 두 집합의 교집합의 크기를 두 집합의 합집합의 크기로 나눈 값으로 정의됩니다. 이 예제에서는 먼저 불용어 제거, 어간 추출, 표제어 추출을 통해 필요 없는 단어를 제거하고, 단어의 기본 형태를 추출합니다. 주어진 문서 D1과 D2에 대해서, k=1, k=2, k=3일 때의 Jaccard 유사도를 계산해보겠습니다. D1 = {data, mining, is, fun} D2 = {computers, are, interesting, and, fun} 불용어 제거와 어간 추출, 표제어 추출 후의 집합은 다음과 같을 것입니다. D1 = {data, mine, be, fun} D2 = {computer, be, interest, and, fun} k=1일 때 (Unigram) 교집합: {fun, be} 합집합: {data, mine, fun, be, computer, interest, and} Jaccard 유사도 = 교집합의 크기 / 합집합의 크기 = 2 / 7 k=2일 때 (Bigram) Bigram을 생성할 때는 연속된 두 단어의 조합을 고려합니다. 하지만 예제에서 제공된 D1과 D2는 각각 4개와 5개의 단어만을 가지고 있으므로, 두 문서 간 공통의 bigram은 존재하지 않습니다. 교집합: {} 합집합: 모든 bigram의 조합 Jaccard 유사도 = 0 / 합집합의 크기 = 0 k=3일 때 (Trigram) Trigram은 연속된 세 단어의 조합을 고려합니다. 이 경우에도, 공통된 trigram은 존재하지 않습니다. 교집합: {} 합집합: 모든 trigram의 조합 Jaccard 유사도 = 0 / 합집합의 크기 = 0 이 예제를 통해 볼 때, Jaccard 유사도는 k의 값에 따라 달라질 수 있으며, 특히 더 긴 shingle(예: bigram, trigram)을 사용할 때는 두 문서 간의 유사도를 찾기가 더 어려울 수 있음을 알 수 있습니다.

7.Challenges of k-Shingling

k-Shingling 방식을 사용하여 문서 간의 유사성을 계산하는 과정에서는 몇 가지 도전과제가 있습니다. 예를 들어, 우리가 10^6개(백만 개)의 문서를 가지고 있다고 가정해 봅시다. 이 경우, 모든 문서 쌍의 짝에 대해 Jaccard 유사성을 계산해야 합니다. 이는 대략 10^6(10^6-1)/2 ≈ 5x10^11 회의 비교를 의미합니다. 이런 규모의 비교를 처리하는 데는 상당한 시간이 소요됩니다. 예를 들어, 하루에 10^5초가 있고, 초당 10^6번의 비교가 가능하다고 가정하면, 모든 비교를 완료하는 데 대략 5일이 걸립니다. 그리고 만약 문서의 수가 10백만(N = 10^7)개라면, 이 작업을 완료하는 데 1년 이상이 걸릴 수 있습니다. 이러한 계산의 복잡성은 매우 큰 데이터 세트를 처리할 때 실질적인 문제가 될 수 있으며, 이는 k-Shingling 방식을 직접적으로 적용하기 어려운 이유 중 하나입니다. 따라서, 대규모 데이터 세트에서 문서 간의 유사성을 효율적으로 계산하기 위해서는 Min Hashing과 Locality Sensitive Hashing(LSH)과 같은 추가적인 기술을 사용하여 계산의 효율성을 높일 필요가 있습니다. 이러한 기술들은 유사한 문서들을 빠르게 식별할 수 있게 해줌으로써, 전체 비교 횟수를 대폭 줄일 수 있습니다.

8.MinHashing

MinHashing은 문서 간의 유사성을 보존하면서 큰 집합을 짧은 서명(signature)으로 변환하는 과정입니다. 이 과정은 특히 큰 데이터셋에서 문서 간의 유사성을 효율적으로 계산하기 위해 사용됩니다. 첫 번째 단계인 Shingling을 통해 문서는 k길이의 문자열 집합으로 변환됩니다. 그 후, MinHashing 과정에서 이 집합은 유사성을 반영하는 짧은 정수 벡터, 즉 '서명(signature)'으로 변환됩니다. 이 서명은 원본 집합의 특성을 간략하게 요약하며, 문서 간의 유사성 비교를 빠르고 효율적으로 만듭니다. MinHashing의 핵심 아이디어는 각 집합에 대해 여러 해시 함수를 적용하여, 각 함수에 대해 가장 작은 해시 값을 선택하는 것입니다. 이렇게 선택된 최소 해시 값들의 집합이 그 집합의 '서명'이 됩니다. 두 집합의 서명 간 유사성은 원래 집합의 Jaccard 유사성을 근사적으로 반영합니다. 따라서, MinHashing은 원본 집합의 크기에 관계없이 일정한 크기의 서명을 생성하여, 대규모 데이터셋에서도 문서 간의 유사성을 효율적으로 비교할 수 있게 합니다.

9.From Sets to Boolean Matrices

집합을 부울(Boolean) 행렬로 변환하는 과정에서, 행은 요소(셔링글)를 나타내고 열은 집합(문서)을 나타냅니다. 어떤 행 e와 열 s에서 값이 1이라는 것은 요소 e가 집합 s에 속해 있다는 것을 의미합니다. 이러한 행렬은 대부분의 값이 0인 희소 행렬(sparse matrix)이라는 특징을 가집니다. 각 문서는 한 열로 표현되며, 이를 통해 두 문서 간의 유사도(similarity)를 계산할 수 있습니다. 유사도 계산은 두 문서(열)에 공통적으로 1이 표시된 요소(셔링글)의 비율로 나타낼 수 있으며, 이는 자카드 유사도(Jaccard similarity)와 유사한 개념입니다. 예를 들어, 문서 C2와 C3의 유사도를 계산하고자 한다면, C2 열과 C3 열을 비교하여 두 열 모두에서 값이 1인 행의 비율을 계산합니다. 만약 C2와 C3가 공통된 요소를 많이 가지고 있다면 유사도는 높게 나타날 것입니다. 문서 C1과 C4의 유사도도 같은 방법으로 계산할 수 있습니다. C1 열과 C4 열을 비교하여 두 열 모두에서 값이 1인 행의 비율을 찾아 유사도를 계산합니다. 단, 여기서 주어진 정보만으로는 C2와 C3, 그리고 C1과 C4 간의 구체적인 유사도 값을 계산할 수 없습니다. 각 문서(열)에서 특정 요소(셔링글, 행)가 포함되어 있는지에 대한 구체적인 정보가 필요합니다.

10.Motivation: MinHashing

MinHashing의 동기는 각 문서(열) C를 작은 서명 h(C)로 "해시"하는 것으로, 이때 몇 가지 주요 목표가 있습니다: h(C)는 메모리에 들어갈 정도로 충분히 작아야 합니다. 두 문서 C1과 C2의 유사도 sim(C1, C2)는 서명 h(C1)과 h(C2)의 유사도와 같아야 합니다. 이를 달성하기 위한 해시 함수 h(·)는 다음과 같은 성질을 가져야 합니다: 만약 sim(C1, C2)가 높다면, 높은 확률로 h(C1) = h(C2)가 됩니다. 만약 sim(C1, C2)가 낮다면, 높은 확률로 h(C1) ≠ h(C2)가 됩니다. 즉, 문서들이 유사도가 높을 경우, 작은 서명들 또한 서로 유사하다는 것입니다. 이는 문서들 간의 유사도가 서명들의 유사도와 근사적으로 일치함을 의미합니다. MinHashing의 핵심 아이디어는 다음과 같습니다: pi를 임의의 순열이라고 할 때, 해시 hpi(Ci)는 열 Ci에서 첫 번째로 1이 되는 행의 인덱스입니다. 이 방식의 핵심 주장은 Pr[hpi(C1) = hpi(C2)] = sim(C1, C2)라는 것입니다. 즉, C1과 C2 열을 내려다보며 그들의 인덱스가 1이 되는 지점을 찾을 때, hpi(Ci) = hpi(Cj)가 성립하면 C1과 C2 모두에서 그 지점이 1이라는 것입니다. 이러한 방식으로, MinHashing은 문서 간의 유사도를 효율적으로 근사화하여, 대규모 문서 집합에서 유사한 문서들을 빠르게 찾아낼 수 있는 기법을 제공합니다.

11.How to Build MinHashing

MinHashing을 구축하는 방법은 다음과 같습니다: 임의의 순열 선택: 우선, p개의 임의의 순열을 선택합니다. 이 순열들은 문서 집합의 행을 다양한 순서로 재배치하는 데 사용됩니다. MinHash 서명 생성: 각 문서(또는 열) C에 대해, 선택한 각 순열 pi에 따라 재배치된 행 순서에서 C 열에 값 1이 처음으로 나타나는 행의 인덱스를 찾습니다. 이 인덱스는 해시 함수 hpi(C)로 정의됩니다. 문서 C의 MinHash 서명(sig(C))은 p개의 순열에 대해 각각 계산된 이러한 인덱스들의 리스트입니다. 즉, 열 C에서 값 1을 가진 첫 번째 행들의 p개 인덱스를 포함합니다. 서명의 유사성: 두 문서 Ci와 Cj의 서명 sig(Ci)와 sig(Cj) 사이의 유사성(sim(sig(Ci), sig(Cj)))을 관찰할 수 있습니다. 이 유사성은 두 서명이 동일한 인덱스를 얼마나 많이 공유하는지에 기반합니다. 유사성과 확률의 관계: 서명 간의 유사성은 원본 문서 간의 유사성, 즉 sim(Ci, Cj)와 확률적으로 일치합니다. 즉, Pr[sim(sig(Ci), sig(Cj))] = sim(Ci, Cj)입니다. 이는 MinHash 서명의 유사성이 원본 문서의 Jaccard 유사성을 효과적으로 근사화한다는 것을 의미합니다. 이러한 방식으로 MinHashing은 문서 간의 유사성을 효율적으로 계산할 수 있게 해주며, 특히 대규모 문서 집합에서 유사 문서를 신속하게 식별하는 데 유용합니다.

12.Example: MinHashing

MinHashing을 사용하여 모든 쌍의 유사도를 계산하는 예시는 다음과 같습니다: MinHashing을 통해, 우리는 대규모 문서 집합 내에서 문서 간의 유사도를 효율적으로 계산할 수 있습니다. 이 방법은 문서들의 집합을 대표하는 짧은 '서명(signature)'을 생성하여, 이 서명들 간의 유사도를 계산함으로써 집합 간의 유사도를 근사합니다. 서명 생성: 먼저, 각 문서에 대해 p개의 무작위 순열을 사용하여 MinHash 서명을 생성합니다. 각 순열에 대해, 문서의 열에서 1의 값이 처음으로 나타나는 행의 인덱스를 찾습니다. 이 인덱스들의 집합이 그 문서의 서명이 됩니다. 유사도 계산: 두 문서 Ci와 Cj의 서명 sig(Ci)와 sig(Cj)가 주어졌을 때, 이 두 서명의 유사도를 계산합니다. 이는 서명에서 일치하는 인덱스의 비율을 통해 계산됩니다. 즉, 두 서명에서 같은 위치에 동일한 인덱스가 얼마나 많이 나타나는지를 기반으로 합니다. 정확한 유사도와의 비교: MinHashing을 이용한 유사도 계산 결과는 정확한 유사도(예: 집합 간의 자카드 유사도)와 매우 가까운 값을 제공합니다. 이는 MinHashing이 문서 간의 유사도를 효율적이면서도 정확하게 추정할 수 있음을 의미합니다. 이 예시를 통해, MinHashing이 대규모 데이터에서 문서 간의 유사도를 계산하는데 어떻게 사용될 수 있는지를 볼 수 있습니다. 이 방법은 특히 문서 클러스터링, 중복 검출, 추천 시스템과 같은 분야에서 유용하게 사용될 수 있습니다.

13.Implementation Trick

MinHashing의 구현에 있어서 행을 실제로 순열하는 것은 계산량이 너무 많아 실행하기 어렵습니다. 그래서, 행을 순열하는 대신에 행 해싱 기법을 사용하는 트릭이 있습니다. 행 해싱(Row Hashing): 먼저, K개의 해시 함수 ki를 선택합니다. 이 K개의 해시 함수는 각각 다른 방식으로 행을 해시할 것이고, 이는 마치 행을 무작위로 순열하는 것과 같은 효과를 냅니다. 한 번의 패스로 구현하기(One-pass Implementation): 각 컬럼 C와 해시 함수 ki에 대해, MinHash 값의 "슬롯"을 유지합니다. 모든 sig(C)[i]를 무한대로 초기화합니다. 행 탐색(Scan Rows): 1 값을 갖는 행 j를 찾습니다. 만약 컬럼 C에 행 j가 1을 갖고 있다면, 각 ki에 대하여 다음을 수행합니다: 만약 ki(j) < sig(C)[i]이면, sig(C)[i]에 ki(j)를 할당합니다. 이러한 방식으로, 각 컬럼의 MinHash 시그니처를 한 번의 패스로 효율적으로 계산할 수 있습니다. 이 방법은 실제로 행을 순열하는 것보다 훨씬 더 계산 비용이 적게 들며, 대규모 데이터셋에서 문서 간의 유사성을 빠르게 추정할 수 있게 해 줍니다.

14.Example: Implementing MinHashing

MinHashing 구현 예시에 대해 설명해 드리겠습니다. 여기서는 두 개의 해시 함수 h(x)와 g(x)를 사용하고, 총 네 개의 열(column)과 세 개의 해시 함수가 있다고 가정합니다. 그러나, 세 번째 해시 함수에 대한 정의가 누락되었으므로 예시를 위해 추가적인 해시 함수 (f(x) = 3x + 2 \mod 5)를 사용한다고 가정하겠습니다. 해시 함수 정의: 첫 번째 해시 함수: (h(x) = x \mod 5) 두 번째 해시 함수: (g(x) = 2x + 1 \mod 5) 세 번째 해시 함수(가정): (f(x) = 3x + 2 \mod 5) MinHash 계산: 각 열(column) C에 대해서, 각 해시 함수 (h, g, f)를 사용하여 MinHash 시그니처(sig(C))를 계산합니다. 이를 위해 모든 sig(C)[i]를 무한대로 초기화합니다. 행 스캔 및 MinHash 업데이트: 데이터 집합을 스캔하면서, 각 열에서 1 값을 가진 행을 찾습니다. 해당 행 j에 대하여, 각 해시 함수 (h, g, f)를 적용합니다. 만약 (h(j)), (g(j)), 또는 (f(j))가 현재 sig(C)[i]보다 작다면, sig(C)[i]에 해당 해시 함수의 결과값을 할당합니다. 이러한 과정을 통해 각 열에 대한 MinHash 시그니처를 계산할 수 있으며, 이를 사용하여 열들 사이의 유사도를 효율적으로 추정할 수 있습니다. MinHashing은 대규모 데이터 집합에서 유사한 항목을 빠르게 찾는 데 유용합니다.

15.Building MinHash Signatures

MinHash 서명을 구축하는 과정은 큰 데이터 집합에서 문서 또는 항목 간의 유사도를 효율적으로 추정하는 데 사용됩니다. 이 방법은 긴 비트 벡터를 짧은 서명으로 압축하여 유사성 계산의 복잡성을 크게 줄입니다. 행의 무작위 순열 선택: 먼저, K=100개의 무작위 행 순열을 선택합니다. 이 순열들은 문서 집합을 다양한 방식으로 재정렬하는 데 사용됩니다. 서명 구축: 각 문서 C에 대해, sig(C)를 열 벡터로 생각합니다. i번째 순열에 따라, 열 C에서 값이 1인 첫 번째 행의 인덱스를 sig(C)[i]로 설정합니다. 이러한 방식으로 모든 K개의 순열에 대해 이 과정을 반복하여 문서 C의 MinHash 서명을 완성합니다. 스케치(서명)의 크기: 생성된 MinHash 서명은 매우 작은 크기(~100바이트)를 가지므로, 원래 문서의 긴 비트 벡터를 효과적으로 압축한 것입니다. 이 방법을 통해, 원래 문서의 집합 간 유사도를 직접 계산하는 대신, 훨씬 작은 크기의 MinHash 서명 간의 유사도를 계산함으로써 비교적 빠르고 효율적으로 유사 문서를 찾을 수 있습니다. 이는 대규모 데이터 집합에서 문서 분류, 중복 탐지, 추천 시스템 등 다양한 응용 프로그램에 유용하게 활용될 수 있습니다.