논문 "From Word Embeddings to Document Distances"는 http://proceedings.mlr.press/v37/kusnerb15.html 단어 임베딩을 사용해서 문서 간 유사성을 계산하는 방법론을 제시합니다. 이 논문에서 사용한 WMD (Word Mover's Distance) 는 문서간 유사성을 측정하는 거리함수로, 한 문서의 단어들이 다른 문서들의 단어들로 이동하는 "비용"을 최소화해서 두 문서간 거리를 계산합니다. 이는 기존의 Earth Mover's Distance (EMD) 문제와 유사한 최적화 문제로 다룰 수 있습니다.
기존 BOW (Bag of Words) 나 TF-IDF 모델은 단어 간 의미적 유서성을 충분히 반영하지 못한 문제가 있습니다. 예를 들어 "Obama speaks to the media in Illinois"와 "The President greets the press in Chicago" 는 유사한 의미를 가지지만 BOW 모델은 이를 감지할 수 없고요.
* BOW: 문서를 단어의 빈도수만으로 표현하는 단순한 텍스트 표현기법. 단어의 순서나 의미적 유사도를 고려하지 않음.* TF-IDF: 한 문서에서 자주 등장하는 TF와 여러 문장에서 공통으로 등장하는 IDF 를 적게 반영해 가중치를 계산. 중요한 단어에 더 많은 가중치 부여.
WMD
WMD 는 각 문서를 단어 임베딩을 기반으로 가중치를 가진 포인트 클라우드로 나타내고, 한 문서의 단어가 다른 문서의 단어와 일치하도록 이동하는 최소 비용을 계산해 문서간 거리를 정의합니다. 단어 이동 비용은 word2vec 임베딩 공간에서 유클리드 거리를 기반으로, 임베딩 거리가 짧을수록 두 단어가 유사하다고 판단합니다.
Word Mover's Distance
n개의 단어를 d차원 벡터로 embedding 시킨 n x d word2vec 행렬이 있다고 하면, i 번째 단어는 행렬의 i 번째 컬럼 벡터로 표현된다. text document 를 n 차원 벡터인 nBOW 로 표현한다고 가정하면 이 nBOW 원소는 전체 단어의 개수에서 해당 단어가 등장한 횟수를 비율로 표현한 값입니다.
nBOW
vector d를 (n-1) dimensional simplex of word distribution 의 point 로 생각합니다. 다른 단어들로 이루어진 문서들은 다른 simplex 에 위치합니다. 그러나 의미적으로 유사할 수 있습니다. stop word (불용어)를 모두 제거한 후 2개의 nBOW 벡터 d, d'는 실질 거리가 가까울 수 있어도 non zero dimension 이 공통되지 않기 때문에 simplex distance 가 커지게 됩니다.
여기서 T 는 가중치를 의미하며 수식에서의 최적값인 EMD (Earth Mover's Distance) 는 특별한 경우 입니다. 이 경우와 EMD 의 관계를 강조하기 위한 지표가 WMD 라 부릅니다.
이 사진에서는, WMD 가 모든 단어는 모든단어와 비교된다는 특징을 볼 수 있습니다. 각 단어는 다른 문서의 모든 단어와의 거리를 계싼해 이 거리가 단어 임베딩 공간에서 유클리드 거리로 정의되는거죠.
최소 비용 매칭 선택
흐름행렬 T 를 사용해 단어 이동 비용을 최소화하는 매칭을 찾고, 단어의 빈도나 문서 간 단어수 차이에 따라 한 단어는 여러 단어와도 매칭될 수 있습니다. 여기서 흐름행렬이란 두 문서 간 단어의 "연결"과 "기여도"를 나타내는 표에요.
Fast Distance Computation
WMD 최적화 문제의 평균 시간 복잡도는 문서의 unique word 의 수가 q 일 때 O(p^3logp) 입니다. 시간 복잡도를 줄이기 위한 방법으로 Word centroid distance 를 구할 수 있고, 이는 삼각 부등식을 사용해 O(dp)가 lower bound 값인 Word Centroid Distance 를 구할 수 있습니다. WCD 는 각 문서들의 word vector 들의 가중 평균으로 표현됩니다.
Prefetch and prune
문서들을 계산 속도에 이점이 있는 query 문서와의 WCD 를 사용해 오름차순으로 정렬합니다. 오름차순으로 정렬된 k 문서에 대해 WMD 를 계산하고, 나머지는 RWMD lower bound 가 현재 계산된 k개의 WMD 를 넘는지 확인합니다. 넘으면 해당 문서를 제거합니다. RWMD 는 tight 하기에 prune 되는 문서들이 약 95%라고 합니다.
WMD는 word2vec embedding 퀄리티가 좋았기 때문에 error rate 가 낮을 수 있었습니다. WMD 의 단어간 거리는 user 가 알 수 있을만큼 설명 가능하며 시각화도 가능하기에 유용한 면이 있는 것 같습니다.
참고자료
https://velog.io/@mingqook/From-Word-Embeddings-To-Document-Distances
'논문' 카테고리의 다른 글
| [논문] Attention is All you need (1) | 2025.01.05 |
|---|---|
| 페이지랭크 알고리즘 (PageRank algorithm) (1) | 2024.11.03 |