Sign In

Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS

์ž‘์„ฑ์ž
  • Haebom
์นดํ…Œ๊ณ ๋ฆฌ
Empty

์ €์ž

Laurent Guigues

๐Ÿ’ก ๊ฐœ์š”

๋ณธ ๋…ผ๋ฌธ์€ NP-๋‚œํ•ด ๋ฌธ์ œ์ธ ์ตœ๋Œ€ ๊ฐ€์ค‘์น˜ ๋…๋ฆฝ ์ง‘ํ•ฉ(MWIS) ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ฐจ๋ถ„ ๊ฐ€๋Šฅํ•œ ๊ทผ์‚ฌ ์—”์ง„์œผ๋กœ ๊ทธ๋ž˜ํ”„ ์ƒ์˜ ์›๋ฆฌ์ ์ธ ๋™์  ์‹œ์Šคํ…œ์ธ Graph Normalization(GN)์„ ์ œ์•ˆํ•ฉ๋‹ˆ๋‹ค. GN์€ Belief Propagation๊ณผ ๋‹ฌ๋ฆฌ ํ•ญ์ƒ ์ตœ๋Œ€ ๋…๋ฆฝ ์ง‘ํ•ฉ์˜ ์ด์ง„ ์ง€ํ‘œ๋กœ ์ˆ˜๋ ดํ•จ์ด ์ฆ๋ช…๋˜์—ˆ์œผ๋ฉฐ, ์ด๋ฅผ ํ†ตํ•ด MWIS ์™„ํ™”๋œ ๊ธฐ๋ณธ ๋ชฉํ‘œ๋ฅผ ์ฒด๊ณ„์ ์œผ๋กœ ๊ฐœ์„ ํ•˜๋Š” ๋น ๋ฅธ ์ค€-๋‰ดํ„ด ํ•˜๊ฐ•์„ ์‹คํ˜„ํ•ฉ๋‹ˆ๋‹ค.

๐Ÿ”‘ ์‹œ์‚ฌ์  ๋ฐ ํ•œ๊ณ„

โ€ข
GN์€ NP-๋‚œํ•ด ๋ฌธ์ œ์ธ MWIS๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ทผ์‚ฌํ•  ์ˆ˜ ์žˆ๋Š” ์ƒˆ๋กœ์šด ๋™์  ์‹œ์Šคํ…œ ์ ‘๊ทผ ๋ฐฉ์‹์„ ์ œ๊ณตํ•ฉ๋‹ˆ๋‹ค.
โ€ข
GN์€ Replicator Dynamics์™€์˜ ์—ฐ๊ด€์„ฑ์„ ํ†ตํ•ด ์ง„ํ™” ๊ฒŒ์ž„์˜ ๊ด€์ ์—์„œ ๋ฌธ์ œ ํ•ด๊ฒฐ์˜ ์›๋ฆฌ๋ฅผ ์„ค๋ช…ํ•˜๋ฉฐ, ์ตœ๋Œ€ ๋…๋ฆฝ ์ง‘ํ•ฉ์ด ํŠน์ • ์ด์ฐจ ํ˜•์‹์˜ ๊ตญ์†Œ ์ตœ์†Ÿ๊ฐ’๊ณผ ์ผ๋Œ€์ผ ๋Œ€์‘๋จ์„ ๋ณด์ž…๋‹ˆ๋‹ค.
โ€ข
Assignment Problem์˜ ๊ฒฝ์šฐ, Sinkhorn ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ผ๋ฐ˜ํ™”๋œ ํ˜•ํƒœ๋กœ ์ž‘๋™ํ•˜๋ฉฐ arbitrary constraint graph๋กœ ํ™•์žฅ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
โ€ข
GN์€ ์‹ค์ œ ์„ธ๊ณ„์˜ ๋Œ€๊ทœ๋ชจ ๊ทธ๋ž˜ํ”„์—์„œ ์ˆ˜ ์ดˆ ๋‚ด์— ์ตœ์  ๊ฒฐ๊ณผ์˜ 1% ์ด๋‚ด์˜ ํ•ด๋ฅผ ์ฐพ๋Š” ๋น ๋ฅธ ์ด์ง„ํ™” ์—”์ง„์œผ๋กœ ์„ฑ๋Šฅ์„ ์ž…์ฆํ–ˆ์Šต๋‹ˆ๋‹ค.
โ€ข
์‹ฌ์ธต ํ•™์Šต ๋ชจ๋ธ์—์„œ ์ œ์•ฝ ์กฐ๊ฑด ํ•˜์˜ ์ฐจ๋ถ„ ๊ฐ€๋Šฅํ•œ "ํ•˜๋“œ" ๊ฒฐ์ •์ด ํ•„์š”ํ•œ ๊ฒฝ์šฐ(์˜ˆ: ๊ตฌ์กฐ์  ํฌ์†Œ ์–ดํ…์…˜, ๋™์  ๋„คํŠธ์›Œํฌ ๊ฐ€์ง€์น˜๊ธฐ), ์ปดํ“จํ„ฐ ๋น„์ „, ๊ณ„์‚ฐ ์ƒ๋ฌผํ•™, ์ž์› ํ• ๋‹น ๋“ฑ ๋‹ค์–‘ํ•œ ๋ถ„์•ผ์—์„œ ์—”๋“œ-ํˆฌ-์—”๋“œ ํ•™์Šต์„ ๊ฐ€๋Šฅํ•˜๊ฒŒ ํ•ฉ๋‹ˆ๋‹ค.
โ€ข
GN์€ ๋น„์„ ํ˜• ์ง„ํ™” ๊ฒŒ์ž„์œผ๋กœ ์ž ์žฌ ํ•จ์ˆ˜ ๊ฒŒ์ž„์ด ์•„๋‹ˆ๋ฏ€๋กœ, ํŠน์ • ์ƒํ™ฉ์—์„œ๋Š” ์ˆ˜๋ ด์„ฑ์ด๋‚˜ ์ตœ์ ์„ฑ์„ ๋ณด์žฅํ•˜๊ธฐ ์–ด๋ ค์šธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๐Ÿ‘
Made with Slashpage