Different embeddings+ Word Mover Distance 😊😊

Text Data:

• Obama speaks to the media in Illinois
• The president greets the press in Chicago

Removing stop words:

• Obama speaks media Illinois

• president greets press Chicago

• 위의 두 문장의 경우, 공통되는 단어가 없으므로, 코사인 유사도는 0이 될 것이다.

• 코사인 유사도 = 0 : 두 벡터가 직각이다

• word mover' distance의 경우, 이를 해결할 수 있다

Word Mover's distance:

• 단어 임베딩 공간에서의 단어 유사도를 고려할 수 있다

• WMD는 두 문장에 나온 단어들의 단어 임베딩을 이용해서, 최소 거리를 계산한다

  → 한 문장안의 단어가 semantic space 를 여행하면서 다른 문장의 단어로 도달하게 한다

obama → president와의 차이 : 0.45 vs band → president와의 차이 : 0.49

각 단어들 마다, 이 차이들을 더해서, 그 합이 작을 수록 유사한 문장이라고 판단한다

Earth Mover's Distance:

• region D에서의 두 확률 분포의 거리를 계산

• 만약 두 분포를 어떤 특정한 양의 모래가 쌓이는 두 가지의 다른 방법이라고 해석한다면, EMD는 하나의 pile을 다른 pile로 바꾸는 최소 비용이다; 이때의 비용은 (모래가 이동된 거리) X (모래가 이동된 횟수) 로 계산된다

  

• 즉, 이동의 문제로 해석할 수 있다.

• 우리는 큰 볼륨을 (동일한 크기의) 다른 볼륨으로 이동할 때의 비용을 최소화하려고 한다

  예)

  • Gini’s measure of discrepancy
  • Transportation problem [Hitchcock]
  • Monge Kantorovitch problem
  • Omstein Distance
  • Lipschitz norm …

• 유클리드 거리와 EMD를 썼을 때의 히스토그램 거리 계산
  

• 유클리드 거리의 경우: true distance를 반영하는데에 실패함

  • 히스토그램 A, B는 굉장히 비슷하고, A,C는 굉장히 다름에도 불구, 둘의 거리를 동일하게 측정함

• 이를 해결하기 위해 EMD사용

  - orientation과 energy 값을 반영함
  
  - details on EMD [https://leechamin.tistory.com/225](https://leechamin.tistory.com/225) (이거 설명이 너무 좋다...)
  
    - EMD (wasserstein distance): 두 확률 분포간의 사이를 측정하는 방법
    - 한 분포에서 다른 분포의 모양을 닮기 위해 옮겨지는 모래 더미의 최소 비용
    - 파일의 모래 양: (옮겨진 모래 양)X(이동거리)

  

EMD btw Equal-Weight Distributions

• 두개의 동일한 가중치 분포간의 EMD는 "하나의 분포를 다른 분포와 닮게 하기위해 필요한 일의 양"과 와 비례한다
• 하나의 분포에서 다른 분포로 이동할 때 필요한 일의 양의 최소값
• 전체 가중치의 normalization 은 EMD를 (한 파일에서 다른 파일로 갈때 걸리는 여행거리의 평균)과 같게 한다

FLOW in Word vector space

• 모든 단어들이 줄지어 서있는 것은 직관적이다. 그러나 만약 한 문장에서의 단어의 개수가 다르다면?
  → 내가 궁금했던 질문: 해시태그를 여러개 쓸수록 유사도가 높아질까?

<예>

1. Obama, speaks, media, Illinois
2. president, greets, press

---

• WMD는 Earth Mover's Distance라는 최적화 문제에서 시작한다. EMD는 flow를 위한 최적화 문제를 풀기 위한 시도이다.
• 각각의 고유한 단어들 (전제 단어 개수: N)은 1/N 의 flow를 부여받는다.
• 1번 문장에서, 각각의 단어는 0.25(=1/4)의 flow를 가지고, 2번 문장의 각 단어는 0.33(=1/3)의 flow를 가진다.
• 물처럼, 나가는 것은 들어오는 것과 합쳐져야 된다.
  : 1/3 > 1/4 이므로, 단어로 부터 넘치는 flow는 다른 단어들로 흘러들어갈 수 밖에 없다. 이것이 단어간의 거리를 최소화하기 위한 최적화 문제이다.T:

T: flow

c(i,j): 단어i와 j의 유클리드 거리

두 분포의 전체 무게가 동일하지 않다면, 한 무더기를 열심히 만져서 rearrange해도 다른 무더기로 만들수 없다.
예) 무게가 다른 하나의 찰흙을 가지고 다른 무게의 고양이 찰흙 조형물을 만들수는 없다

EMD btw unequal-weight distributions 문제는 더 무거운 분포로 더 가벼운 분포를 나타내기위해 필요한 최소 비용의 문제와 비슷하다

• 보통, 무거운 분포 → 가벼운 분포를 match할 때 굳이 모든 mass를 다 맞출 필요없다.
  → 그래서 matching unequal-weight distributions은 partial matching case라고도 한다.