Different embeddings+ย Word Mover Distanceย ๐Ÿ˜Š๐Ÿ˜Š

jjยท2021๋…„ 2์›” 26์ผ
0

SS-hashtag-recommendation-project

๋ชฉ๋ก ๋ณด๊ธฐ
3/15
post-thumbnail

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๋ผ๊ณ ๋„ ํ•œ๋‹ค.
profile
์žฌ๋ฐŒ๋Š”๊ฒŒ ์žฌ๋ฐŒ๋Š”๊ฑฐ๋‹ค

0๊ฐœ์˜ ๋Œ“๊ธ€