t-SNE

Prerequisite; Information Theory

---

• 정보이론(Information Theory) : 신호에 존재하는 정보의 양을 측정하는 이론으로서, 특정 확률분포의 특성을 알아내거나, 두 확률분포 간 유사성을 정량화하는 데 사용함

Information Gain

• 자기정보(Self-Information) : 확률변수 $X \sim P$ 에 대하여, 사건 $X=x$ 가 발생했을 때의 정보량

  \[\begin{aligned} I(X=x) &= \log{\frac{1}{P(X=x)}}\\ &=-\log{P(X=x)} \end{aligned}\]
  • 자주 발생하지 않는 사건(Unlikely Event)일수록 높은 정보량을 가짐(Informative)
  • 독립사건은 추가적인 정보량을 가짐(Addictive Information)
    • 동전을 두 번 던져서 앞면이 두 번 나오는 사건은 동전을 한 번 던져서 앞면이 나오는 사건보다 정보량이 두 배임

• 엔트로피(Entropy) : 자기정보의 기대값으로서, 주어진 확률분포에서 발생 가능한 사건들의 평균적인 정보량

  \[\begin{aligned} H(P) &= \mathbb{E}_{X \sim P}\left[I(X)\right]\\ &= \mathbb{E}_{X \sim P}\left[-\log{P(X)}\right]\\ &= -\mathbb{E}_{X \sim P}\left[\log{P(X)}\right]\\ &= -\sum_{x}{\log{P(x)} \cdot P(x)} \end{aligned}\]
  • 사건의 분포가 결정적일수록(Deterministic) 엔트로피가 감소함
  • 사건의 분포가 균등할수록(Uniform) 엔트로피가 증가함

Information Discrepancy

• 교차 엔트로피(Cross Entropy) : 확률변수 $X$ 의 분포 $P$ 와 그 근사 분포 $Q$ 에 대하여, $Q$ 가 $P$ 에 대하여 제공하는 정보의 불확실성을 측정하는 지표

  \[\begin{aligned} H(P,Q) &= \mathbb{E}_{X \sim P}\left[-\log{Q(X)}\right]\\ &= - \sum_{x}{\log{Q(x)} \cdot P(x)} \end{aligned}\]

• 쿨백 라이블러 발산(Kullback-Leibler Divergence) : 확률변수 $X$ 의 분포 $P$ 와 그 근사 분포 $Q$ 에 대하여, $Q$ 를 $P$ 의 근사 분포로 사용할 때의 비효율성을 측정하는 지표로서, $P$ 에서 샘플링된 $X$ 에 대하여, $P$ 가 제공하는 평균적인 정보량과 $Q$ 가 제공하는 평균적인 정보량의 차이

  \[\begin{aligned} D_{KL}(P \parallel Q) &= \mathbb{E}_{X \sim P}\left[-\log{P(X)}\right] - \mathbb{E}_{X \sim P}\left[-\log{Q(X)}\right]\\ &= \mathbb{E}_{X \sim P}\left[-\log{\frac{Q(X)}{P(X)}}\right]\\ &= \mathbb{E}_{X \sim P}\left[\log{\frac{P(X)}{Q(X)}}\right]\\ &= \sum_{x}{\log{\frac{P(x)}{Q(x)}} \cdot P(x)} \end{aligned}\]

• 교차 엔트로피와 쿨백 라이블러 발산의 관계

  \[\begin{aligned} D_{KL}(P \parallel Q) &= \sum_{x}{\log{\frac{P(x)}{Q(x)}} \cdot P(x)}\\ &= -\sum_{x}{\log{\frac{Q(x)}{P(x)}} \cdot P(x)}\\ &= -\sum_{x}{\left[\log{Q(x)}-\log{P(x)}\right] \cdot P(x)}\\ &= \left[-\sum_{x}{\log{Q(x)} \cdot P(x)}\right] -\left[-\sum_{x}{\log{P(x)} \cdot P(x)}\right]\\ &= H(P,Q) - H(P) \end{aligned}\]

t-SNE

---

• Stochastic Neighbor Embedding : 관측치 간 고차원 공간 상 확률적 유사도를 보존하면서 저차원으로 매핑하는 비선형 차원 축소

  

• SNE의 문제점 : Crowding Problem

  

  • 가우시안 분포는 양쪽 꼬리 부분이 충분히 두텁지 않은 형태를 보임
  • 즉, 확률변수 \(\Vert \overrightarrow{x}_{i}-\overrightarrow{x}_{j} \Vert\) 가 일정한 값 이상부터는 유사도에 큰 차이가 없음

• t-SNE의 해결책 : Student t-Dristribution

  

  \[\begin{aligned} T &= \frac{Z}{\sqrt{\displaystyle\frac{V}{\nu}}}\\ V &= \sum_{i=1}^{k}{Z_{i}^{2}} \end{aligned}\]
  • $Z$ : 표준 가우시안 분포
  • $V$ : 자유도가 $\nu$ 인 카이제곱 분포

How to Extract

---

• 두 관측치의 고차원 공간 상 유사도 도출

  • 확률변수 $X$ 가 가우시안 분포 $N(\mu, \sigma^{2})$ 을 따른다고 했을 때, $X$ 의 확률밀도함수는 다음과 같음

    \[\begin{aligned} f(x) &= \frac{1}{\sqrt{2\pi\sigma^{2}}}\exp{\left[-\frac{(x-\mu)^{2}}{2\sigma^{2}}\right]} \end{aligned}\]

  • 관측치 \(\overrightarrow{x}_{i}\) 로부터의 거리에 대한 \(\overrightarrow{x}_{i}\) 와의 유사도의 가우시안 분포에 기초했을 때, \(\overrightarrow{x}_{j}\) 가 \(\overrightarrow{x}_{i}\) 와 유사할 가능성을 다음과 같이 정의하자

    \[\begin{aligned} p_{j \mid i} &= \frac{\exp{\left[-\frac{\Vert\overrightarrow{x}_{i}-\overrightarrow{x}_{j}\Vert^{2}}{2\sigma^{2}}\right]}}{\sum_{k \ne i}{\exp{\left[-\frac{\Vert\overrightarrow{x}_{i}-\overrightarrow{x}_{k}\Vert^{2}}{2\sigma^{2}}\right]}}}\\ \Vert\overrightarrow{x}_{i}-\overrightarrow{x}_{j}\Vert &\sim N_{i}(0,\sigma^{2}) \end{aligned}\]

  • 또한 관측치 \(\overrightarrow{x}_{j}\) 로부터의 거리에 대한 \(\overrightarrow{x}_{j}\) 와의 유사도의 가우시안 분포에 기초했을 때, \(\overrightarrow{x}_{i}\) 가 \(\overrightarrow{x}_{j}\) 와 유사할 가능성을 다음과 같이 정의하자

    \[\begin{aligned} p_{i \mid j} &= \frac{\exp{\left[-\frac{\vert\overrightarrow{x}_{i}-\overrightarrow{x}_{j}\vert^{2}}{2\sigma^{2}}\right]}}{\sum_{k \ne j}{\exp{\left[-\frac{\vert\overrightarrow{x}_{j}-\overrightarrow{x}_{k}\vert^{2}}{2\sigma^{2}}\right]}}}\\ \Vert\overrightarrow{x}_{i}-\overrightarrow{x}_{j}\Vert &\sim N_{j}(0,\sigma^{2}) \end{aligned}\]

  • 두 가능성은 서로 다른 확률 분포에 기초하고 있으므로 그 값이 반드시 일치한다고 볼 수 없음

    \[p_{j \mid i} \ne p_{i \mid j}\]

  • 따라서 \(\overrightarrow{x}_{i}\) 와 \(\overrightarrow{x}_{j}\) 의 유사도를 다음과 같이 정의함

    \[\begin{aligned} p_{i,j} &= \frac{p_{j \mid i} + p_{i \mid j}}{2n} \end{aligned}\]

• 두 관측치의 2차원 공간 상 유사도 도출

  • 관측치 \(\overrightarrow{y}_{i}\) 로부터의 거리에 대한 \(\overrightarrow{y}_{i}\) 와의 유사도의 가우시안 분포에 기초했을 때, \(\overrightarrow{y}_{j}\) 가 \(\overrightarrow{y}_{i}\) 와 유사할 가능성을 다음과 같이 정의하자

    \[\begin{aligned} q_{j \mid i} &= \frac{\exp{\left[-\Vert\overrightarrow{y}_{i}-\overrightarrow{y}_{j}\Vert^{2}\right]}}{\sum_{k \ne i}{\exp{\left[-\Vert\overrightarrow{y}_{i}-\overrightarrow{y}_{k}\Vert^{2}\right]}}}\\ \Vert\overrightarrow{y}_{i}-\overrightarrow{y}_{j}\Vert &\sim N_{i}(0,\sigma^{2}) \end{aligned}\]
    • \(\overrightarrow{y}\) : 고차원 공간 상의 관측치 벡터 \(\overrightarrow{x}\) 를 2차원 공간 상에 매핑한 벡터

  • \(\overrightarrow{y}_{i}\) 와 \(\overrightarrow{y}_{j}\) 의 유사도를 다음과 같이 정의함

    \[\begin{aligned} q_{i,j} &= \frac{q_{j \mid i} + q_{i \mid j}}{2n} \end{aligned}\]

• 비용 함수를 최소화하는 아규먼트 도출

  • 쿨백 라이블러 발산에 기초한 비용함수 정의

    \[\begin{aligned} Cost &= \sum_{i}{\text{KL}(P_{i} \parallel Q_{i})}\\ &= \sum_{i}{\sum_{j}{\log{\frac{p_{i,j}}{q_{i,j}}}} \cdot p_{i,j}} \end{aligned}\]

  • $\hat{\mathbf{Y}}$ 도출

    \[\begin{aligned} \hat{\mathbf{Y}} &= \{\hat{\overrightarrow{y}}_{i} \mid \text{arg} \min_{\overrightarrow{y}_{i}}{Cost}\} \end{aligned}\]