์ค๋ ๋ฆฌ๋ทฐ/๋ฒ์ญ/๊ตฌํ
ํ ๋
ผ๋ฌธ์ Visualizing Data using t-SNE์ผ๋ก, 2008๋
์ Geoffrey Hinton์ด ์ ์์ธ ๋
ผ๋ฌธ์
๋๋ค. t-SNE(t-Stochastic Nearest Neighbor)์ ์ง๊ธ๊น์ง๋ ์๊ฐํ๋ฅผ ํ๋ ๋ฐ ์์ฃผ ์ฌ์ฉ๋๋ ์๊ณ ๋ฆฌ์ฆ์
๋๋ค. ์ด๋ ๊ณ ์ฐจ์์ ๋ฒกํฐ๋ก ํํ๋๋ ๋ฐ์ดํฐ ๊ฐ์ neighbor structure ๋ฅผ ๋ณด์กดํ๋ 2 ์ฐจ์์ embedding vector ๋ฅผ ํ์ตํจ์ผ๋ก์จ, ๊ณ ์ฐจ์์ ๋ฐ์ดํฐ๋ฅผ 2 ์ฐจ์์ผ๋ก ํํํ ์ ์๋๋ก ํฉ๋๋ค.
๊ณ ์ฐจ์ ๋ฐ์ดํฐ์ ์๊ฐํ๋ ๋ง์ ๋๋ฉ์ธ ์์ญ์์ ์ฃผ์ํ๊ฒ ๋ค๋ฃจ์ด์ง๋๋ค.
๋น์ ํ์กดํ๋ ์์ด์ฝ๊ทธ๋ํฝ ๋์คํ๋ ์ด(iconographic disaplay), Chernoff Face (Chernoff, 1973), pixel-based techniques (Keim, 2000)๊ณผ ๊ฐ์ ์๊ฐํ ๊ธฐ๋ฒ์ ๋๋๋ถ ๋๊ฐ ์ด์์ ๋ฐ์ดํฐ ์ฐจ์์ ์๊ฐํํ ์ ์๋๋ก๋ง ์ ๊ณตํด์ฃผ๊ณ , ์ฌ๋์ด ์ด๋ฅผ ํด์ํ๋ ๋ฐฉ์์ผ๋ก ์งํ์ด ๋์์ต๋๋ค.
Chernoff-face : https://en.wikipedia.org/wiki/Chernoff_face
pixel-based techniques : https://www.semanticscholar.org/paper/Pixel-Oriented-Visualization-Techniques-for-Very-Keim/ce1eb9ed41232690a1ab0b6b7322cfdb10a385cc
์ด์๋ ๋ฐ๋๋ก, ์ฐจ์์ถ์(dimensional reduction) ๋ฐฉ๋ฒ์ ๊ณ ์ฐจ์ ๋ฐ์ดํฐ๋ฅผ ์ ์ฐจ์(2์ฐจ์ ๋๋ 3์ฐจ์)์ผ๋ก ์ถ์ฝ์์ผ, ์ด๋ฅผ ์ฐ์ ๋๋ก ํํ์ ํด์ค ์ ์๊ฒ ํฉ๋๋ค.
์ฐจ์ ์ถ์์ ๋ชฉํ๋ ์ ์ฐจ์ ๋ฐ์ดํฐ์์ ์ค์ํ ๊ณ ์ฐจ์๋ฐ์ดํฐ์ ๊ตฌ์กฐ๋ฅผ ์ ์งํด์ฃผ๋ ๊ฒ์ ๋๋ค.
PCA(์ฃผ์ฑ๋ถ๋ถ์), MDS(๋ค์ฐจ์์ฒ๋๋ฒ)์ ๋ํ์ ์ธ ์ฐจ์์ถ์ ๋ฐฉ๋ฒ๋ก ์ผ๋ก, ์๋ก ๋ค๋ฅธ ๋ฐ์ดํฐ ํฌ์ธํธ์ ์ ์ฐจ์ ํํ์ผ๋ก ๋ฉ๋ฆฌ ๋จ์ด๋จ๋ฆฌ๋ ๋ฐ ์ด์ ์ ๋ง์ถ ์ ํ ๊ธฐ์ ์ ๋๋ค.
๊ณ ์ฐจ์ ๋ฐ์ดํฐ์์๋ ์ ํ ๋งคํ์ผ๋ก๋ ๊ณ ์ฐจ์ ๋ฐ์ดํฐ ์ ๋ณด์ ์ง๊ฐ ๋ถ๊ฐ๋ฅํ์ฌ ๋ฐ์ดํฐ์ ์ง์ญ ๊ตฌ์กฐ๋ฅผ ๋ณด์กดํ๋ ๊ฒ์ ๋ชฉํ๋ก ํ๋ ๋ง์ ์์ ๋น์ ํ ์ฐจ์ ๊ฐ์ ๊ธฐ์ ์ด ์ ์๋์์ต๋๋ค.
ํ์ง๋ง, ์ด๋ฌํ ๋ฐฉ๋ฒ๋ก ๋ค๋ ๊ณ ์ฐจ์ ๋ฐ์ดํฐ์ ๋ก์ปฌ ๋๋ ๊ธ๋ก๋ฒํ ์ ๋ณด๋ฅผ ๋ ๋ค ์ ์ ์งํ์ง๋ ๋ชปํ์๋ค. t-SNE๋ ์ด๋ฅผ ๊ฐ๋ฅํ๊ฒ ํด์ค๋๋ค.
SNE(Stochastic Neighbor Embedding)์ ๋ฐ์ดํฐ ์ ์ฌ์ด์ ๊ณ ์ฐจ์์ "์ ํด๋ฆฌ๋ ๊ฑฐ๋ฆฌ"๋ฅผ "์ ์ฌ์ฑ์ ๋ํ๋ด๋ ์กฐ๊ฑด๋ถ ํ๋ฅ "๋ก ๋ณํํ์ฌ ์ฌ์ฉํฉ๋๋ค.
SNE๋ย ์ย ์ฌ์ด์ ๋ถ์ผ์น๋ฅผ ์ต์ํํ๋ ์ ์ฐจ์ ๋ฐ์ดํฐ ํํ์ ์ฐพ๋ ๊ฒ์ ๋ชฉํ๋ก ํฉ๋๋ค.
๋ ๊ณ ์ฐจ์ ๋ฐ์ดํฐ ํฌ์ธํธ์ ์กฐ๊ฑด๋ถ, ๋ ์ ์ฐจ์ ๋ฐ์ดํฐ ํฌ์ธํธ์ ์กฐ๊ฑด๋ถ์ ๋๋ค
์ ์ ์ ์ฌ์ฑ์, ๊ฐ ๋ฅผ ์ค์ฌ์ผ๋ก ํ ๊ฐ์ฐ์ค ์๋์์ ํ๋ฅ ๋ฐ๋์ ๋น๋กํ์ฌ ์ด์์ ์ ํํ๋ค๋ฉด ๋ฅผ ์ด์์ผ๋ก ์ ํํ ์ ์๋ ์กฐ๊ฑด๋ถ ํ๋ฅ ๋ฅผ ์๋ฏธํฉ๋๋ค.
์ ์ ์ ์ฌ์ฑ์, ๊ฐ ๋ฅผ ์ค์ฌ์ผ๋ก ํ ๊ฐ์ฐ์ค ์๋์์ ํ๋ฅ ๋ฐ๋์ ๋น๋กํ์ฌ ์ด์์ ์ ํํ๋ค๋ฉด ๋ฅผ ์ด์์ผ๋ก ์ ํํ ์ ์๋ ์กฐ๊ฑด๋ถ ํ๋ฅ ๋ฅผ ์๋ฏธํฉ๋๋ค.
์กฐ๊ฑด๋ถ ํ๋ฅ ๊ฐ()์ด ๋์ผ๋ฉด ๋ฐ์ดํฐ ํฌ์ธํธ๊ฐ ๊ฐ๊น์ต๋๋ค.
์กฐ๊ฑด๋ถ ํ๋ฅ ๊ฐ()์ด ๋ฎ์ผ๋ฉด ๋ฐ์ดํฐ ํฌ์ธํธ๊ฐ ๋ฉ๋๋ค.
, ,
SNE๋ ๊ฐ์ฐ์์ ๋ถํฌ๋ฅผ ๋ฐ๋ฅด๊ธฐ ๋๋ฌธ์, ์ธ์ ๋ฐ์ดํฐ ํฌ์ธํธ์ ๊ฒฝ์ฐ ์กฐ๊ฑด๋ถ ํ๋ฅ ์ด ๋์ง๋ง, ๋๊ฒ ๋ถ๋ฆฌ๋ ๋ฐ์ดํฐ ํฌ์ธํธ์ ๊ฒฝ์ฐ ์กฐ๊ฑด๋ถ ํ๋ฅ ์ด ๋ฐ์ฐํ๊ฒ ๋ฉ๋๋ค.
์ฐจ์ ์ถ์๊ฐ ์ ๋๋ก ์ ์ด๋ค์ก๋ค๋ฉด ๊ณ ์ฐจ์ ๊ณต๊ฐ์์ ์ด์์ผ๋ก ๋ฝํ ํ๋ฅ ๊ณผ ์ ์ฐจ์ ๊ณต๊ฐ์์ ์ด์์ผ๋ก ๋ฝํ ํ๋ฅ ์ด ๋น์ทํ ๊ฒ์ ๋๋ค. ์ด๋ ๋ฏ SNE์ ๋ชฉ์ ์ p์ q์ ๋ถํฌ ์ฐจ์ด๊ฐ ์ต๋ํ ์๊ฒ๋ ํ๊ณ ์ ํฉ๋๋ค.
๋ ํ๋ฅ ๋ถํฌ๊ฐ ์ผ๋ง๋ ๋น์ทํ์ง ์ธก์ ํ๋ ์งํ ์ฒ๋๋ Kullback-Leibler divergence๋ฅผ ์ด์ฉํฉ๋๋ค.
KL Divergence๋ ์ด๋ค ํ๋ฅ ๋ถํฌ๋ฅผ ๋ค๋ฅธ ํ๋ฅ ๋ถํฌ๋ก ๊ทผ์ฌํ ๋ ์ ํํ ์ผ๋ง๋ ๋ง์ ์ ๋ณด(์ํธ๋กํผ)๊ฐ ์์ค๋๋์ง๋ฅผ ๊ณ์ฐํ ์ ์์ต๋๋ค.
๋ ํ๋ฅ ๋ถํฌ๊ฐ ์์ ํ ๋ค๋ฅด๋ฉด 1, ๋์ผํ๋ฉด 0์ ๊ฐ์ ๊ฐ์ต๋๋ค.
SNE๋ ์๋ ๋น์ฉํจ์๋ฅผ ์ต์ํํ๋ ๋ฐฉํฅ์ผ๋ก ํ์ต์ ์งํํ๊ฒ ๋ฉ๋๋ค.
SNE ๋น์ฉ ํจ์๋ ๋งต์์ ๋ฐ์ดํฐ์ ๋ก์ปฌ ๊ตฌ์กฐ๋ฅผ ์ ์งํ๋๋ฐ ์ด์ ์ ๋ง์ถฅ๋๋ค.
์ ํ๋ ๋๋จธ์ง ํ๋ผ๋ฏธํฐ๋ ๊ฐ๊ฐ์ ๊ณ ์ฐจ์ ๋ฐ์ดํฐ ํฌ์ธํธ xi์ ์ง์ค๋๋ ๊ฐ์ฐ์์์ ๋ถ์ฐ ฯi์ ๋จ์ผ ๊ฐ์ผ๋ก ํ๋ ๊ฒ์ ๋ถ์ ์ ํฉ๋๋ค. (๋ฐ์ดํฐ์ ๋ฐ๋๊ฐ ๋ค์ํ๊ธฐ ๋๋ฌธ์, ๋ฐ๋๊ฐ ๋์ ์์ญ์์ ฯi์ ๊ฐ์ด ์์์๋ก ์ข์)
์ด๋คํ ฯi ๊ฐ์ด๋ ๋ค๋ฅธ ๋ชจ๋ ๋ฐ์ดํฐ ํฌ์ธํธ์ ๋ํด ํ๋ฅ ๋ถํฌ Pi๋ฅผ ์ ๋๋ฉ๋๋ค. ๋ถํฌ๋ ฯi๊ฐ ์ฆ๊ฐํจ์ ๋ฐ๋ผ ์ฆ๊ฐํ๋ ์ํธ๋กํผ๋ฅผ ๊ฐ์ต๋๋ค.
SNE๋ ฯi์ ๊ฐ์ ๋ํด ์ด์ง ๊ฒ์์ ์ํํฉ๋๋ค. ์ฌ์ฉ์๊ฐ ์ง์ ํ ๊ณ ์ ๋ ๋ณต์ก๋(perplexity)๋ฅผ ๊ฐ๋ Pi๋ฅผ ์์ฑํฉ๋๋ค. Perplexity๋ ๋ค์๊ณผ ๊ฐ์ด ์ ์๋ฉ๋๋ค.
์ด๋ ๋ Shannon Entrophy of ์ ๋๋ค.
SNE์ ๊ฐ์ perplextity์ ํฐ ์ํฅ์ ๋ฐ์ง ์์ต๋๋ค. (fairly robust)
์ต์ข ์ ์ผ๋ก ๊ตฌํ๊ณ ์ ํ๋ ๋ฏธ์ง์๋ ์ ์ฐจ์์ ์๋ฒ ๋ฉ๋ ์ขํ๊ฐ yi, SNE๋ ๊ทธ๋๋์ธํธ ๋์ผํธ(gradient descent) ๋ฐฉ์์ผ๋ก yi๋ค์ ์ ๋ฐ์ดํธํฉ๋๋ค.
์์์ ์ ์ํ ๊ฑฐ๋ฆฌ ํจ์๋ ์กฐ๊ฑด๋ถ ํ๋ฅ ์ด๊ธฐ ๋๋ฌธ์ Symmetric(๋น๋์นญ)ํ์ง ๋ชปํ๋ฏ๋ก, ๋ฐ์ดํฐ ์์ ๋ํ Joint Probability(๋์นญ)์ ์ฌ์ฉํ์์ต๋๋ค.
์ด์ ์กฐ๊ฑด๋ถํ๋ฅ , ์ฌ๊ฑด B๊ฐ ๋ฐ์ํ๋ค๋ ๊ฐ์ ํ์ ์ฌ๊ฑด A๊ฐ ์ผ์ด๋ ํ๋ฅ ( โ )
Joint Probability๋ฅผ ์ฌ์ฉํด์ค์ผ๋ก์ ์ฐ์ฐ์ด ๋นจ๋ผ์ง ์ ์์์ต๋๋ค.
๋์นญ SNE์ gradient๋ ๋น๋์นญ SNE์ gradient์ ์๋นํ ์ ์ฌํ๋ฉฐ ์คํ์์ ๋์นญ SNE๊ฐ ๋น๋์นญ SNE์ ๋ง์ฐฌ๊ฐ์ง๋ก ์ข๊ณ ๊ฒฝ์ฐ์ ๋ฐ๋ผ ์กฐ๊ธ ๋ ๋์ ๋งต์ ์์ฑํ๋ ๊ฒ์ผ๋ก ๋ํ๋ฌ์ต๋๋ค.
ฯi๋ ๊ฐ ๊ฐ์ฒด๋ง๋ค ๋ฐ์ดํฐ ๋ฐ๋๊ฐ ๋ฌ๋ผ์ ์ด์์ผ๋ก ๋ฝํ ํ๋ฅ ์ด ์๊ณก๋๋ ํ์์ ๋ฐฉ์งํ๊ธฐ ์ํ ๊ฐ์ ๋๋ค. ์ ์๋ ๋ฐ๋ณต ์คํ ๊ฒฐ๊ณผ p๋ฅผ ๊ณ์ฐํ ๋ ์ฐ๋ ฯi๋ ๊ณ ์ ๋ ๊ฐ์ ์จ๋ ์ฑ๋ฅ์ ํฐ ์ฐจ์ด๋ฅผ ๋ณด์ด์ง ์์๋ค๊ณ ํ์ฌ ฯi ๊ณ์ฐ์ ์๋ตํ์์ต๋๋ค.
source : https://andyjconnelly.wordpress.com/2017/05/16/uncertainty-and-repeats/
๊ณ์ฐ์ ์ผ๋ก ํธ๋ฆฌํ ์์ฑ์ Student t ๋ถํฌ๊ฐ Gaussians์ ๋ฌดํํ ํผํฉ(infinite mixture of Gaussians)๊ณผ ๊ฐ์์๋ ๋ถ๊ตฌํ๊ณ ์ง์๊ฐ ํฌํจ๋์ง ์๊ธฐ ๋๋ฌธ์ Student t ๋ถํฌ ์๋์ ์ ์ ๋ฐ๋๋ฅผ ๊ฐ์ฐ์์๋ณด๋ค ๋ ๋น ๋ฅด๊ฒ ํ๊ฐํฉ๋๋ค.
The gradient of the Kullback-Leibler divergence between P and the Student-t based joint probability distribution Q
source : ๋ ผ๋ฌธ ์๋ฌธ
2๊ฐ์ง ์ด์
๋ฅผ ๋ญ๋๋ค.t-SNE ๊ทธ๋ผ๋์ธํธ๋ ์ ์ฐจ์ ํํ์์ ์์ pairwise distance๋ก ๋ชจ๋ธ๋ง ๋ ๋ค๋ฅธ datapoints๋ฅผ ๊ฐํ๊ฒ ๋ฐ๋ฐํฉ๋๋ค.
t-SNE๊ฐ ์์ pairwise distance์ ์ํด ๋ชจ๋ธ๋ง๋ ๋ค๋ฅธ datapoint๋ค ์ฌ์ด์ ์ผ์ผํจ ๊ฐ๋ ฅํ ๋ฐ๋ฐ์ ๋ฌดํ๋๋ก ๋ฐ์ฐํ์ง ์์ต๋๋ค.
source : ๋ ผ๋ฌธ ์๋ฌธ
gradient decent๋ฅผ ์งํํ๋ฉด ๋ถ์์ ํ๊ธฐ ๋๋ฌธ์ momentum์ผ๋ก paraemter๋ฅผ ์ ๋ฐ์ดํธํฉ๋๋ค. ๋ฐ๋ณต ํ์๋ฅผ ์ค์ด๊ธฐ ์ํด momentum์ ํ์ฉํ๋ฉฐ, momentum์ด ์์ผ๋ฉด ๋งต ํฌ์ธํธ๊ฐ ์ ์ ํ๊ฒ ์ ์ ๋ฆฌ ๋ ๋๊น์ง ํ์ต์ด ๋ฉ๋๋ค.
Jacobs(1988)์ ์ํด ์ค๋ช ๋ adaptive learning rate๋ฅผ ์ฌ์ฉํ์ฌ ํ์ต์ ๊ฐ์ํ ํ ์ ์๋๋ฐ, ์ด ๋ฐฉ๋ฒ์ ๊ทธ๋ผ๋์ธํธ๊ฐ ์์ ํ ๋ฐฉํฅ์ผ๋ก ์ ์ง์ ์ผ๋ก ํ์ต ์๋๋ฅผ ์ฆ๊ฐ์ํต๋๋ค.
์๊ณ ๋ฆฌ์ฆ์ด ๋ค๋ฅธ ๋น๋ชจ์ ์ฐจ์์ ์ถ์ ๊ธฐ์ ๋ก ์์ฑ๋ ๊ฒ๋ณด๋ค ํจ์ฌ ๋์ ์๊ฐํ๋ฅผ ์์ฑํ์ง๋ง, ์๋์ 2๊ฐ์ง ํจ๊ณผ์ ์ธ ๋ฐฉ๋ฒ
์ ํตํด ์ข ๋ ํจ์จ์ ์ผ๋ก ์ต์ ํ๋ฅผ ์ํํ ์ ์์ต๋๋ค.
Early Compression (์ด๋ฅธ ์์ถ ๋ฐฉ๋ฒ)
์ต์ ํ๊ฐ ์์๋ ๋ ๋งต ํฌ์ธํธ๋ค์ด ์๋ก ๊ฐ๊น์ด์ ์๋๋ก ๊ฐ์ ํฉ๋๋ค. (force the map points to stay close together at the start of the optimization)
๋งต ํฌ์ธํธ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๊ฐ ์์ผ๋ฉด ํด๋ฌ์คํฐ๊ฐ ์๋ก ์ด๋ํ๊ธฐ ์ฝ๊ธฐ ๋๋ฌธ์ ๊ฐ๋ฅํ ๊ธ๋ก๋ฒ ํ๊ฒ ๋ฐ์ดํฐ์ ๊ณต๊ฐ์ ํ์ํ๋ ๊ฒ์ด ํจ์ฌ ์ฌ์์ง๋๋ค.
์์ ์ผ๋ก๋ถํฐ์ ๋งต ํฌ์ธํธ์ ์ ๊ณฑ ๊ฑฐ๋ฆฌ์ ํฉ์ ๋น๋กํ๋ ๋น์ฉ ํจ์์ L2 ํ๋ํฐ๋ฅผ ์ถ๊ฐํจ์ผ๋ก์จ, ํ๋ํฐ ๊ธฐ๊ฐ์ ํฌ๊ธฐ์ ๋ฐ๋ณต์ ์๋์ผ๋ก ์ค์ ํด์ค๋๋ค.
Early Exaggeration (์ด๋ฅธ ๊ณผ์ฅ ๋ฐฉ๋ฒ)
pij์ ํน์ ์์(๋ ผ๋ฌธ ์์๋ก 4)๋ฅผ ๊ณฑํ์ฌ, qij๊ฐ ์๋์ ์ผ๋ก ์๊ธฐ ๋๋ฌธ์ pij์ ๋์ํ๊ธฐ ์ํ์ฌ ํฌ๊ฒ ์์ง์ด๊ณ ๋งต ํฌ์ธํธ๊ฐ ๋๊ฒ ์์ง์ด๋๋ก ํฉ๋๋ค.
ํด๋ฌ์คํฐ๊ฐ ๋งต ํฌ์ธํธ์์ ๋จ๋จํ๊ณ ์๋ก ๊ฐ์ ๋๊ฒ ๋ถ๋ฆฌ๋ ํด๋ฌ์คํฐ๋ฅผ ํ์ฑํ๋ ๊ฒฝํฅ์ผ๋ก ๋น ๊ณต๊ฐ์ด ๋ง์ด ์๊ธธ ์ ์๋๋ก ์กฐ์ ํด์ฃผ๋ ๋ฐ ์์๊ฐ ์์ต๋๋ค.
์คํ์ผ๋ก ์๋ 5๊ฐ์ ๋ฐ์ดํฐ ์ธํธ๋ฅผ ์ด์ฉํ์ต๋๋ค:
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
์ด๋ฒ ํํธ์์๋ ์ ์ฒด(๋๋ต์ ์ผ๋ก ๋งค์ฐ ํฐ) ๋ฐ์ดํฐ ์งํฉ์ ์ ๋ณด๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์์ผ๋ก t-SNE๋ฅผ ์์ ํ์ฌ ๋ฐ์ดํฐ ์ (์ผ๋ช landmark point)์ ๋๋ค ์๋ธ์ ์ ํ์ํ๋ ๋ฐฉ๋ฒ์ ๋ณด์ฌ์ค๋๋ค. ๋งค์ฐ ํฐ ๋ฐ์ดํฐ ์ธํธ์ ์ ๋ณด๋ฅผ ์ฌ์ฉํ๋ ๋ฐฉ์์ผ๋ก ๋ฐ์ดํฐ ํฌ์ธํธ์ ๋๋ค ์๋ธ ์ธํธ๋ฅผ ํ์ํ๋๋ก t-SNE๋ฅผ ์์ ํ๋ ๋ฐฉ๋ฒ์ ์ ์ํฉ๋๋ค. (Figure 6 ์ฐธ๊ณ )
ํ์๋์ง ์์ ๋ฐ์ดํฐ ํฌ์ธํธ๊ฐ ๊ธฐ๋ณธ ๋งค๋ํด๋์ ๋ํด ์ ๊ณตํ๋ ์ ๋ณด๋ฅผ ์ฌ์ฉํฉ๋๋ค. ๋ฐ์ ์์๋ฅผ ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
ํด๋น ๋ฐฉ๋ฒ๋ก ์ ๋ค์๊ณผ ๊ฐ์ ์์๋ฅผ ๋ฐ๋ฆ ๋๋ค.
์ด ๋ฐฉ๋ฒ์ Isomap์ด ์ ์ฌ์ด์ ์ ๋ฐฉํฅ ๊ฑฐ๋ฆฌ๋ฅผ ์ธก์ ํ๋ ๋ฐฉ์๊ณผ ๋ฎ์์ง๋ง, diffusion map (Lafon and Lee, 2006; Nadler et al., 2006)์์์ ๊ฐ์ด ๊ฐ์ฅ ์งง์ ์ธ์ (shortest path)๋ง์ ๋ณด๋ ๊ฒ ์๋๋ผ, ์ด๋ฅผ ํ์ฉํด ๋๋ค ์ํฌ ๊ธฐ๋ฐ์ ์ธก์ ์น๊ฐ ์ธ์ ๊ทธ๋ํ๋ฅผ ํตํด ๋ชจ๋ ๊ฒฝ๋ก์ ํตํฉ๋๋๋ก ํ์ฌ ๊ฒฐ๊ณผ์ ์ผ๋ก ๋ฌด์์ ์ํฌ ๊ธฐ๋ฐ ์ธก์ ์ short-circuit (Lee and Verleysen, 2005)์ ํจ์ฌ ๋ ๋ฏผ๊ฐํฉ๋๋ค.
๋๋ค ์ํฌ ๊ธฐ๋ฐ ์ ์ฌ๋()๋ฅผ ๊ณ์ฐํ๋ ๊ฐ์ฅ ํ์คํ ๋ฐฉ๋ฒ์ 100๋ง๋ฒ์ ๋๋ค ์ํฌ๋ฅผ ์ฝ๊ฒ ์ํํ ์ ์๋ค๋ ๊ฒ์ ๊ฐ์ํ ๋, ์ด๋ฅผ ๋ช ์์ ์ผ๋ก ์ํํ๋ ๊ฒ์ ๋๋ค.
๋๋ Grady (2006)๋ sparse ์ ํ ์์คํ ์ ํด๊ฒฐํ๋ ์ ๋ฐฉํฅ ์ ์ฌ๋ย ๋ฅผ ๊ณ์ฐํ๋ ๋ถ์ ์๋ฃจ์ ์ ์ ์ํ๊ธฐ๋ ํ์์ต๋๋ค. (์๋น ์คํ์์ Random Walk(๋ฌด์์ ๊ฑธ์)๋ฅผ ๋ช ์์ ์ผ๋ก ์ํํ๋ ๊ฒ๊ณผ ๋ถ์์ ์๋ฃจ์ ์ฌ์ด์ ํฐ ์ฐจ์ด์ ์ ๋ฐ๊ฒฌํ์ง ๋ชปํจ)
Source : ๋ ผ๋ฌธ ๋ณธ๋ฌธ
Figure 7์ ๋๋ค ์ํฌ ๋ฒ์ ์ ์ ์ฉํ ์คํ ๊ฒฐ๊ณผ๋ก, t-SNE๋ฅผ MNIST ๋ฐ์ดํฐ ์ธํธ(60,000 ์ซ์)๋ก๋ถํฐ ๋ฌด์์๋ก ์ ํ๋ 6000๊ฐ๋ฅผ ์ด์ฉํ์ฌ pairwise ์ ์ฌ์ฑ ๋ฅผ ๊ณ์ฐํ ๊ฒ์ ๋๋ค. ์คํ์์๋ k = 20 ๊ฐ๊น์ด ์ด์๋ค์ ๊ฐ์ ์ฌ์ฉํ์ฌ ๊ตฌ์ฑ๋ ์ด์ ๊ทธ๋ํ๋ฅผ ์ฌ์ฉํ์์ต๋๋ค.
์ฝ์ ๊ทธ๋ฆผ(inset figure)์ ์์์ด ์๋ฆฟ์์ ๋ ์ด๋ธ์ ๋ํ๋ด๋ ์ฐ์ ๋์ ๋์ผํ ์๊ฐํ๋ฅผ ๋ํ๋ ๋๋ค.
t-SNE ๋งต์์๋ ๋ชจ๋ ํด๋์ค๊ฐ ๋ช ํํ๊ฒ ๊ตฌ๋ถ๋ฉ๋๋ค. ๋ํ, t-SNE๋ 1, 4, 7, 9์ ๋ฐฉํฅ์ด๋ 2์ โ๊ณ ๋ฆฌ ๋ชจ์โ๊ณผ ๊ฐ์ ๊ฐ ํด๋์ค ๋ด์ ๋ณํ์ ์ฃผ ํฌ๊ธฐ๋ฅผ ๋ํ๋ ๋๋ค.
t-SNE์ ๊ฐํ ์ฑ๋ฅ์ ๋ํ ์ ์ฐจ์ ํํ์ ๋ํด ํ๋ จ๋ ๊ฐ์ฅ ๊ฐ๊น์ด ์ด์ ๋ถ๋ฅ ์์ ์ผ๋ฐํ ์ค์ฐจ์ ๋ฐ์ํฉ๋๋ค.
์๋์ 784 ์ฐจ์ ๋ฐ์ดํฐ ์ ์ ๋ํด ํ๋ จ๋ ์ต๊ทผ์ ์ด์ ๋ถ๋ฅ๊ธฐ์ ์ผ๋ฐํ ์ค์ฐจ (10 ๋ฐฐ ๊ต์ฐจ ๊ฒ์ฆ์ ์ฌ์ฉํ์ฌ ์ธก์ )๊ฐ 5.75 % ์ธ ๋ฐ๋ฉด์, 2 ์ฐจ์์ ํ๋ จ ๋ ์ต๊ทผ์ ์ด์ ๋ถ๋ฅ๊ธฐ์ ์ผ๋ฐํ ์ค์ฐจ t-SNE์ ์ํด ์์ฑ๋ ๋ฐ์ดํฐ ํํ์ ๋จ์ง 5.13 %์ ๋ถ๊ณผํ๊ฒ ๋ฉ๋๋ค.
์์ ๋ ์น์ ์์ ๋ค์ํ ๋ฐ์ดํฐ ์ธํธ์์ t-SNE์ ์ฑ๋ฅ์ ๋ณด์์ต๋๋ค. ์ด ์น์ ์์๋ t-SNE์ ๋ค๋ฅธ ๋น๋ชจ์ ๊ธฐ๋ฒ์ ์ฐจ์ด์ ์ ๋ํด ๋ ผ์ํ๊ณ , ์ฝ์ ๋ฐ ๊ฐ๋ฅํ ๊ฐ์ ์ ์ ๋ ผ์ํฉ๋๋ค.
PCA ์ ๋ฐ์ ํ ๊ด๊ณ๊ฐ ์๋ classical scaling(Torgerson, 1952)์ ๊ณ ์ฐจ์์ ์ ๊ฑฐ๋ฆฌ์ ๊ทธ๊ฒ๋ค ์ฌ์ด์ ์ ๊ณฑ ์ค์ฐจ์ ํฉ์ ์ต์ํํ๋ ๋ฐ์ดํฐ์ ์ ํ ๋ณํ์ ๋ฐ๊ฒฌํ์์ต๋๋ค.
- Classical scaling๊ณผ ๊ฐ์ ์ ํ ๋ฐฉ๋ฒ์ ๊ทผ์ฒ์ ๋ฐ์ดํฐ ์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์งํ๋ ๊ฒ์ด ์๋๋ผ ๋๋ฆฌ ๋ถ๋ฆฌ ๋ ๋ฐ์ดํฐ ์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์งํ๋ ๋ฐ ์ด์ ์ ๋ง์ถ์์ต๋๋ค. ํ์ง๋ง, ์ด๋ ๊ณก์ ๋งค๋ ํด๋๋ฅผ ๋ชจ๋ธ๋งํ๋๋ฐ ์ข์ง ์์ต๋๋ค.
Classical scaling์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ์ํ ์ค์ํ ์ ๊ทผ ๋ฐฉ๋ฒ์ผ๋ก ์ ์๋ ๊ฒ์ด ๋ฐ๋ก Sammon ๋งคํ (Sammon, 1969)์
๋๋ค.
- ์ด ๋ฐฉ๋ฒ์ ๊ฐ๊ฐ์ pairwise ์ ํด๋ฆฌ๋ ๊ฑฐ๋ฆฌ์ ํํ์์ ์ ๊ณฑ ์ค์ฐจ๋ฅผ ๋์ ์ ํด๋ฆฌ๋ ๊ฑฐ๋ฆฌ๋ก ๋๋์ด classical scaling์ ๋น์ฉ ํจ์๋ฅผ ๋ณ๊ฒฝํด์ค๋๋ค.
![Cost Func](https://velog.velcdn.com/images%2Feuisuk-chung%2Fpost%2F2c2e78ec-c91d-4c0d-b6c5-b7ddfa3b1873%2Fimage.png)
- ๊ฒฐ๊ณผ ๋น์ฉ ํจ์๋ ๊ทธ๋ ๋์ธํธ์ ์ ๋๋ฅผ ๋จ์ํํ๊ธฐ ์ํด ํฉ๊ณ ์ธ๋ถ์ ์์๊ฐ ์ถ๊ฐ๋๋ ์์น์ ์ํด ์ ๊ณต๋ฉ๋๋ค.
- Sammon ๋น์ฉ ํจ์์ ๊ฐ์ฅ ํฐ ์ฝ์ ์ ์ง๋์์ ์๊ฑฐ๋ฆฌ๋ฅผ ์ ์งํ๋ ์ค์์ฑ์ด pairwise ๊ฑฐ๋ฆฌ์ ์์ ์ฐจ์ด์ ํฌ๊ฒ ์์กดํ๋ค๋ ์ ์
๋๋ค.
- ์์ pairwise ๊ฑฐ๋ฆฌ๊ฐ ๋ฐ์ดํฐ์ ๋ก์ปฌ ๊ตฌ์กฐ๋ฅผ ๊ณ ๋ คํ ๋ ์์ ์ ๊ฑฐ๋ฆฌ์ ๊ฑฐ์ ๋์ผํ ์ค์์ฑ์ ๋ถ์ฌํ๋ ๊ฒ์ด ๋ ์ ํฉํฉ๋๋ค. ํนํ, ๋งค์ฐ ๊ทผ์ ํ 2 ๊ฐ์ ๊ณ ์ฐจ์ ์ ๋ชจ๋ธ์ ์์ ์ค์ฐจ๋ ๋น์ฉ ํจ์์ ํฐ ๊ธฐ์ฌ๋ฅผ ํฉ๋๋ค.
Sammon ๋งคํ๊ณผ๋ ๋ฌ๋ฆฌ, t-SNE์ ์ํ ๊ณ ์ฐจ์ ๊ณต๊ฐ์์ ์ฌ์ฉ๋ ๊ฐ์ฐ์์ ์ปค๋์ ๋ฐ์ดํฐ์ ๋ก์ปฌ ๋ฐ ๊ธ๋ก๋ฒ ๊ตฌ์กฐ์ ๊ฐ์ฐ์ค์ ํ์ค ํธ์ฐจ์ ๋น๋กํ์ฌ ์๋ก ๊ฐ๊น์ด ๋ฐ์ดํฐ ์ ์์ ๋ํ ์ํํธ ๊ฒฝ๊ณ๋ฅผ ์ ์ํ๊ฒ ๋ฉ๋๋ค.
- ๋ถ๋ฆฌ๋ฅผ ๋ชจ๋ธ๋งํ๋ ๊ฒ์ ์ค์์ฑ์ ๋ถ๋ฆฌ์ ํฌ๊ธฐ์ ๊ฑฐ์ ๋ฌด๊ดํฉ๋๋ค.
- t-SNE๋ ๋ฐ์ดํฐ์ ๋ก์ปฌ ๋ฐ๋์ ๊ธฐ์ดํ์ฌ ๊ฐ ๋ฐ์ดํฐ ํฌ์ธํธ์ ๋ํ ๋ก์ปฌ ์ธ์ ํฌ๊ธฐ๋ฅผ ๊ฐ๋ณ์ ์ผ๋ก ๊ฒฐ์ ํฉ๋๋ค.
Isomap์ ๋นํด t-SNE๊ฐ ๊ฐ๋ ฅํ ์ด์
: Isomap์ โshort-circuitingโ์ ๋ํ ์ทจ์ฝ์ฑ + Isomap์ ์ฃผ๋ก ์์ ์ธก์ง ๊ฑฐ๋ฆฌ๋ณด๋ค๋ ํฐ ์ธก์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ชจ๋ธ๋งํ๋ ๋ฐ ์ค์ ์ ๋๊ธฐ ๋๋ฌธ์
๋๋ค.
LLE์ ๋นํด t-SNE๊ฐ ๊ฐ๋ ฅํ ์ด์
: LLE๋ ๊ธฐ๋ณธ์ ์ผ๋ก ๋ชจ๋ ๋ฐ์ดํฐ ํฌ์ธํธ๊ฐ ๋จ์ผ ์ง์ ์ผ๋ก ์ ํ๋ ๊ฒ์ ๋ฐฉ์งํ๊ธฐ ์ํด ์ ์ฐจ์ ํํ์ ๊ณต๋ถ์ฐ์ ๋ํ ์ ์ฝ์ ๋ก๋๋ค. ์ค์ ๋ก ์ด ์ ์ฝ ์กฐ๊ฑด์ ๋๋ค์์ ๋งต ํฌ์ธํธ๋ฅผ ๋งต์ ์ค์์ ๋ฐฐ์นํ๊ณ ๋ช ๊ฐ์ ๋๋ฆฌ ๋ถ์ฐ ๋ ํฌ์ธํธ๋ฅผ ์ฌ์ฉํ์ฌ ํฐ ๊ณต๋ถ์ฐ์ ๋ง๋ญ๋๋ค.
๋ํ Isomap ๋ฐ LLE์ ๊ฐ์ ์ธ์ ๊ทธ๋ํ ๊ธฐ๋ฐ ๊ธฐ์ ์ ๋ ๊ฐ ์ด์์ ๋๋ฆฌ ๋ถ๋ฆฌ ๋ ํ์ ๋งค๋ ํด๋๋ก ๊ตฌ์ฑ๋ ๋ฐ์ดํฐ๋ฅผ ์๊ฐํ ํ ์ ์์ต๋๋ค. ์ด๋ฌํ ๋ฐ์ดํฐ๋ ์ฐ๊ฒฐ๋ ์ธ์ ๊ทธ๋ํ๋ฅผ ๋ฐ์์ํค์ง ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ฐ๊ฒฐ๋ ๊ฐ ๊ตฌ์ฑ ์์์ ๋ํด ๋ณ๋์ ์ง๋๋ฅผ ์์ฑ ํ ์๋ ์์ง๋ง ์ด ๋ฐฉ๋ฒ์ ์๋์ ์ ์ฌ์ฑ์ ๋ํ ์ ๋ณด๋ฅผ ์์ด๋ฒ๋ฆฌ๊ฒ ๋ฉ๋๋ค.
1. ์ฝ์ 1 : ๋ค๋ฅธ ๋ชฉ์ ์ ์ํ ์ฐจ์ ์ถ์์๋ tSNE๊ฐ ์ ํฉํ์ง ์์ต๋๋ค.
2. ์ฝ์ 2 : ์ฐจ์์ ์ ์ฃผ์ ๋ฏผ๊ฐํฉ๋๋ค.
3. ์ฝ์ 3 : t-SNE ๋น์ฉ ํจ์์ Non - convexity
๋ณธ ๋ ผ๋ฌธ reproduction ๊ณผ์ ์ ์์ด์ ๊ตฌํ์ ํด๋ณธ ๋ถ๋ถ์ t-SNE ๋ ผ๋ฌธ์ experiment ๋ด์ฉ ์ค MNIST Dataset์ ๋ํ ๋ด์ฉ์ด๋ค. ๋ ผ๋ฌธ๊ณผ ๋์ผํ ์คํํ๊ฒฝ์ผ๋ก ์ ํ ํ์ผ๋ฉฐ, ํจ์ ์ต์ ํ๋ฅผ ์ํด ํจ์๋ง ๊ตฌํํ๊ณ ์ค์ ๋ก ๋๋ฆฐ ๋ชจ๋ธ์ ๋๋ฆด๋๋ sklearn ๋ด์ฅํจ์๋ฅผ ์ด์ฉํ๋ค. ํ๋ผ๋ฏธํฐ๋ ๋ ผ๋ฌธ์ ๋์จ ํ๋ผ๋ฏธํฐ๊ฐ์ ๊ทธ๋๋ก ์ฌ์ฉํ์๋ค. ๋ ผ๋ฌธ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก Isomap๊ณผ LLE ๋ํ ์ ์ฉํ์ฌ ๋น๊ต๋ฅผ ์ํํ์๋ค. t-SNE์ ๋ฒ ์ด์ค๋ผ์ธ ์ฝ๋๋ ์๋ ๋งํฌ๋ฅผ ์ฐธ๊ณ ํ์ฌ ๊ตฌํํ์๋ค. (https://nlml.github.io/in-raw-numpy/in-raw-numpy-t-sne/)
๊ธฐ๋ณธ metric ์ฐ์ฐ ํจ์
# neg-์ ํด๋ฆฌ๋์ ๊ฑฐ๋ฆฌ ํจ์(-|xi-xj|^2)
def neg_squared_euc_dists(X):
sq_sum = np.square(np.linalg.norm(X, ord = 2, axis = 1))
D = np.add(np.add(-2 * np.dot(X, X.T), sq_sum).T, sq_sum)
return -D
# ๊ฑฐ๋ฆฌ๋ฅผ ํ๋ฅ ๊ฐ๋ค๋ก ๋ณํํด์ฃผ๋ ํจ์
def calc_prob_matrix(distances, sigmas=None):
if sigmas is not None:
two_sig_sq = 2.0 * np.square(sigmas.reshape((-1, 1)))
return scipy.special.softmax((distances / two_sig_sq), axis = 1)
else:
return scipy.special.softmax(distances, axis = 1)
# Perplexity ๋ฐํ ํจ์
def perplexity(distances, sigma):
probability_matrix = calc_prob_matrix(distances, sigma)
Hp = -np.sum(probability_matrix * np.log2(probability_matrix), 1)
return 2**Hp
# ์์ธก๊ฐ์ด ํ๊ฒ๊ฐ๊ณผ ๊ฐ์์ง๋๋ก ํ์์ ๋ฐ๋ณตํ๋ ์๊ณ ๋ฆฌ์ฆ
def binary_search(function, target, tol=1e-10, max_iter=10000,
lower=1e-20, upper=1000.):
for i in range(max_iter):
guess = (lower + upper) / 2.
value = function(guess)
if value > target: upper = guess
else: lower = guess
# break if target = prediction
if np.abs(value - target) <= tol:
break
return guess
# ๋ฐ์ดํฐ๋ก๋ถํฐ ์ป์ ๊ฑฐ๋ฆฌ ํ๋ ฌ์ ๊ฐ ํ์ ์ ํฉํ ์๊ทธ๋ง ๋ฐํ
def find_optimal_sigmas(distances, target_perplexity):
sigmas = []
for i in range(distances.shape[0]):
# Perplexity calculation for one row
function = lambda sigma: perplexity(distances[i:i+1, :], np.array(sigma))
# return correct sigmas
correct_sigma = binary_search(function, target_perplexity)
sigmas.append(correct_sigma)
return np.array(sigmas)
๋ ผ๋ฌธ์์ ์ ์๋ Equation
*# Eauation 1 - p(j|i)*
def p_ji_prob(X, target_perplexity):
distances = neg_squared_euc_dists(X)
sigmas = find_optimal_sigmas(distances, target_perplexity)
probability_matrix = calc_prob_matrix(distances, sigmas)
p_ji_output =(probability_matrix + probability_matrix.T) / (2.0 * probability_matrix.shape[0])
return p_ji_output
# Equation 4 - q(ij)
def q_tsne(Y):
distances = neg_squared_euc_dists(Y)
inv_distances = np.power(1.0 - distances, -1)
np.fill_diagonal(inv_distances, 0.)
q_tsne = inv_distances / np.sum(inv_distances)
return q_tsne, inv_distances
# Equation 5 - Gradient of Cost
def tsne_grad(P, Q, Y, inv_distances):
pq_diff = P - Q
pq_expanded = np.expand_dims(pq_diff, 2) *#p(ij)-q(ij)*
y_diffs = np.expand_dims(Y, 1) - np.expand_dims(Y, 0) *#y(i)-y(j)*
distances_expanded = np.expand_dims(inv_distances, 2) *#(1+||yi-yj||^2)^(-1)*
return 4. * (pq_expanded * y_diffs * distances_expanded).sum(1)
# Y ์
๋ฐ์ดํธ ํจ์
def estimate_sne(X, y, P, num_iters, q_function, gradient_function, learning_rate, momentum):
Y = np.random.RandomState(1234).normal(0., 0.0001, [X.shape[0], 2])
Y_m2 = Y.copy(); Y_m1 = Y.copy()
*# Gradient Descent*
for i in range(num_iters):
Q, distances = q_function(Y)
gradient = gradient_function(P, Q, Y, distances)
*# Y Update*
Y = Y - learning_rate * gradient
Y += momentum * (Y_m1 - Y_m2)
Y_m2 = Y_m1.copy()
Y_m1 = Y.copy()
return Y
๋ ผ๋ฌธ ์คํ ๊ตฌํ ์ฝ๋
# import libraries
from __future__ import print_function
import time
import numpy as np
import pandas as pd
from sklearn.datasets import fetch_openml
from sklearn.decomposition import PCA
from sklearn.manifold import TSNE, LocallyLinearEmbedding, Isomap
%matplotlib inline
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import seaborn as sns
# fetch data
mnist = fetch_openml('mnist_784')
X = mnist.data / 255.0
y = mnist.target
print(X.shape, y.shape)
# make dataframe
feat_cols = [ 'pixel'+str(i) for i in range(X.shape[1]) ]
df = pd.DataFrame(X,columns=feat_cols)
df['y'] = y
df['label'] = df['y'].apply(lambda i: str(i))
X, y = None, None
print('Size of the dataframe: {}'.format(df.shape))
# ๋๋ค ์๋ ์ค์
np.random.seed(42)
rndperm = np.random.permutation(df.shape[0])
# 6000๊ฐ row sampling
N = 6000
df_subset = df.loc[rndperm[:N],:].copy()
data_subset = df_subset[feat_cols].values
# pca๋ฅผ ์ด์ฉํ ์ฐจ์์ถ์ (30์ฐจ์)
pca = PCA(n_components=30)
pca_result = pca.fit_transform(data_subset)
# fit model
tsne_result = tsne.fit_transform(pca_result)
lle_result = lle.fit_transform(pca_result)
isomap_result = isomap.fit_transform(pca_result)
# visualize t-sne
df_subset['tsne-2d-one'] = tsne_result[:,0]
df_subset['tsne-2d-two'] = tsne_result[:,1]
plt.figure(figsize=(16,10))
sns.scatterplot(
x="tsne-2d-one", y="tsne-2d-two",
hue="y",
palette=sns.color_palette("hls", 10),
data=df_subset,
legend="full",
alpha=0.3
)
# visualize isomap
df_subset['isomap-2d-one'] = isomap_result[:,0]
df_subset['isomap-2d-two'] = isomap_result[:,1]
plt.figure(figsize=(16,10))
sns.scatterplot(
x="isomap-2d-one", y="isomap-2d-two",
hue="y",
palette=sns.color_palette("hls", 10),
data=df_subset,
legend="full",
alpha=0.3
)
# visualize lle
df_subset['lle-2d-one'] = lle_result[:,0]
df_subset['lle-2d-two'] = lle_result[:,1]
plt.figure(figsize=(16,10))
sns.scatterplot(
x="lle-2d-one", y="lle-2d-two",
hue="y",
palette=sns.color_palette("hls", 10),
data=df_subset,
legend="full",
alpha=0.3
)
๊ธด ๊ธ ์ฝ์ด์ฃผ์ ์ ๊ฐ์ฌํฉ๋๋ค ^~^