Dimensionality Reduction
Feature Extraction: LSA & t-SNE
Latent Semantic Analysis?
Latent는 잠재
Semantic은 의미
Analysis는 분석
90년대 등장한 방법론이기 때문에 이 분야에서는 골동품과 같은 방법론
수학적 기저: 특이값 분해(SVD)
Singular Value Decomposition: SVD
어떤 매트릭스를 factorizing하는 것이 SVD의 목적
m by n 사이즈의 매트릭스
m이 n 보다 큼
BOW 리프리젠테이션으로 봤을 때 term의 수가 document 수보다 큰 것이 일반적
A = TDM
SVD를 통해서 어떤 임의의 rectangular 매트릭스 자체를 3가지의 매트릭스의 결합으로 표현 가능
U라는 하나의 매트릭스
시그마 매트릭스
$V^{T}$ 매트릭스
원래 사이즈가 m by n이었다면 U라는 매트릭스는 m by m, 시그마는 m by n $V^{T}$는 n by n
시그마 매트릭스: diagonal 값만 0보다 크거나 같은 값을 갖음. $\Sigma_{11} \geq \Sigma_{22} \geq \Sigma_{33}$. diagonal만 값을 갖고 있으며 그 값은 항상 내림차순으로 정렬이 됨. 나머지 파트 전부 0
U: 1. 어떠한 k에 대해서도 $u_{k}^{T} u_{k}=1$. unit 벡터라는 뜻. 2. 두 번째 특징은 서로 다른 두 컬럼 벡터를 내적시키면 0. 모든 column들이 서로 orthogonal. $u_{i}^{T} u_{j}=0 (i \neq j)$
V도 마찬가지. $v_{k}^{T} v_{k}=1$. 다시 말go 각각의 컬럼 벡터는 unit 벡터. $v_{i}^{T} v_{j}=0 (i \neq j)$
분해가 될 수 있는 것이 SVD의 결과물
Properties of SVD?
U라는 행렬에 컬럼 벡터들은 전부 unit vector임
서로 다른 컬럼들끼리 내적을 했을 때 0이 되는 것을 매트릭스 form으로 만들면 $U^{T} U=I$, $V^{T} V=I$
$\Sigma_{11} > \Sigma_{22} > \Sigma_{33} > \Sigma_{44}(0) = \Sigma_{55}=...=\Sigma_{mm}(0)$
singular value가 3개 => Rank(A) = 3
여기서 Rank는 매트릭스가 가지고 있는 서로 서로 orthogonal하게 만들어 낼 수 있는 가장 최대한의 차원 수의 개수
Reduces SVDs?
Thin SVD: 시그마 매트릭스는 square matrix로 만듦
n - m만큼의 사이즈가 없어지게 됨
Compact SVD: 시그마 매트릭스에서 zero-singular value를 지워버림
U매트릭스 하고 V매트릭스도 해당하는 컬럼과 로우가 없어짐
여기까지는 사실 A라는 매트릭스를 그대로 보존하고 복원을 할 수가 있음
LSA에서는 Truncated(Approximated) SVD 씀
Truncated(Approximated) SVD: singular value가 내림차순으로 정렬되어 있으니 시그마 매트릭스에서 top k개의 가장 큰 singular value 보존함
A simple example?
S는 시그마 행렬. Singular value는 2개. A행렬의 Rank는 2
A와 A'은 어느정도 대소 관계를 약간은 포함할 수 있음
$A \approx A'$ A'을 A로 근사시킬 수 있는 것이 Truncated SVD
Latent Semantic Indexing?
목적: high dimensional space의 TDM를 lower dimensional space로 컨버팅을 하는데 있어서 statistical structure을 보존함. SVD를 통해서 매트릭스 factorization을 수행
이를 통해서 최대한 변수의 숫자는 줄이면서 데이터가 가지고 있는 구조적인 특징은 보존을 하는 것이 목적
Term 기준으로 해서 차원을 축소하는 것도 가능
Document도 줄이는게 가능함 다시 말하면 문서 기준으로도 차원을 축소시키는 게 가능
Latent는 explicit하지 않은 연관관계를 captures
Semantic은 entitie들 간의 유사성 자체가 저차원으로 변환된 이후에는 거리 관계로서 보전이될 수 있도록 하겠다는 의미
예를 들어서 house라는 단어와 home이라는 단어는 굉장히 유사한 의미를 가지고 있을텐데 LSA나 LSI를 통해서 2차원 상에 매핑을 하게 되면 이 둘 사이의 거리는 상당히 가까울 것
과일들이 가지고 있는 특징들이 어느 정도 보존 됨을 기대
이전에 이제 distributed representation에서 충족하고자 했던 목적 중에 하나임
LSA을 통해서 차원 축소 시켰을 때에도 보존이 되는 것을 어느정도 기대함
Reduce the dimensions using SVD?
A라는 TDM은 U와 시그마와 $V^{T}$로 바뀔 수가 있는데 여기에서 diagonal 값들 중에서 일부분만을 취하게 되면Truncated(Approximated) SVD가 됨
상위 k개 까지만 사용하게 되면 $A_{k}$는 $U_{k}$ X $\Sigma_{k}$ X $V_{k}^{T}$가 됨
원래 오리지날 매트리스 TDM(A)는 k개의 상위의 singular value만을 사용한 $A_{k}$에 근사될 수 있음
차원을 축소시키고 싶으면
의미는 k x n 차원이 되면서 n은 document 개수이고 k가 축소시킨 차원의 크기가 됨
SVD를 통해서 몇 차원으로 줄이고 싶을지 결정할 때는 Truncated(Approximated) SVD의 singular value k개를 몇 개를 사용했느냐에 따라서 달라지게 됨
Document를 줄이고 싶으면 오른쪽에 $V_{k}$를 곱하면 됨
$A_{k}V_{k}$ 결국 남는 것은 $U_{k} \Sigma_{k}$
SVD는 반드시 문서 기준을 축소를 하는게 아니라 문서가 기준이 될 수도 있고 Term이 기준이 될 수도 있음
singular value를 몇 개 쓰느냐가 결정
SVD in text mining?
총 3개 SVD에 해당하는 축을 구함(k=3)
SVD의 값이 커지는 방향으로 단어의 영향력과 작아지는 방향으로 가는 단어의 영향력에 대해서 top ten 키워드를 보여줌
real이 많이 등장하면 SVD1이 커질 가능성이 높음
Sum이라는 단어가 많이 등장을 하게 되면 두 번째 SVD 축에 해당하는 값이 작아질 가능성이 높음
Visulize the project in the reduced 2-D space?
각각의 색깔은 research 카테고리가 됨
카테고리별로 어느 정도 개별적인 점들은 document 또는 abstract라고 보면 됨
Stochastic Neighbor Embedding(SNE)?
시각화 차원 축소 방법론 competition에서 1등한 방법론
데이터가 가지고 있는 structure들 중에서 local distance를 보존하는 것이 non-local distance를 보존하는 것보다 훨씬 더 중요
pairwise distance가 local일 상황을 probabilistic하게 결정함
다른 방법론은 local 다시 말하면 어떤 특정한 포인트와 가까이 있는 포인트들을 결정을 할 때 거리가 가까운 k개를 찾거나 또는 반경 앱실론 안에 속하는 것들을 모두 취하거나 이런 방식으로 determinstic하게 취했음
SNE는 두 가지의 dimension이 있음
high dimension은 현재 가지고 있는 하나의 다큐먼트가 특정 차원의 벡터 공간에서 표현되는 space임
row dimension은 찾아야 되는, 데이터가 가지고 있는 분포 또는 특징을 보존하는 훨씬 더 적은 차원
i를 기준으로 해서 j를 local neighbor로 선택할 확률을 다음과 같이 정의
j가 i에 대해서 굉장히 가깝게 위치하면 e의 -가 작아지는 거니까 확률은 커짐
분모는 전체 확률을 1로 만들어주는 nomalizing factor
j를 i의 이웃으로 선택할 확률을 확률적으로 정의
i하고 j라는 인덱스는 같은데 low dimension에서 $y_{j}$를 $y_{i}$의 이웃으로 정의할 확률은 다음과 같음
파란색의 확률은 원 공간에서 j라는 객체가 i라는 객체 이웃으로 선택의 확률
빨간색의 확률은 좀 더 축소된 공간 상에서 j번째 객체가 i번째 객체 이웃으로 선택될 확률을 정의
Picking the Radius of the Gaussian in p?
시그마($\sigma$)가 크면 클수록 멀리 존재하는 객체들도 선택될 확률이 높아짐
시그마가 크면 i를 기준으로 데이터가 넓게 퍼질 테니까 좀 더 멀리 있는 j들도 파란색 확률 값이 상당히 크게 될 가능성 높음
반면에 시그마가 만약에 작으면(봉오리 뾰족 올라감)갈 테니까 일정 거리 이상으로 벌어지게 되면 파란색 확률이 거의 0으로 간다는 뜻
그래서 시그마가 크면 클수록 멀리 있는 객체를 이웃으로 선택할 가능성이 좀 더 높아지니깐 엔드로피가 커짐
시그마가 작으면 작을수록 가까이 있는 객체들만 이웃으로 선택을 하게 될 가능성이 높아질 테니까 엔트로피가 낮아지게 됨
시그마 i라고 첩자가 되어 있기 때문에 원론적으로 시그마 i는 i에 대해서 dependent하니까 각각을 다 따로 따로 계산을 하게 됨
원 논문에서는 SNE 성능은 바로 위의 사항에 대해 민감하게 반응하지 않으니 신경을 많이 쓰지는 않아도 된다고 함
Cost Function for a Low-dimensional Representation?
얼마나 잘 만들어졌는지 측정(정량적 지표): Kullback-Leibler divergence를 씀
Kullback-Leibler divergence는 non-symmetric함
Kullback-Leibler divergence를 distance로 쓸 수 없음
$D_{KL} (P||Q)$ $\neq$ $D_{KL} (Q||P)$ 때문
distance 개념이 두 개의 객체 순서를 바꿔도 거리가 보존이 되어야 되는데 Kullback-Leibler divergence 같은 경우에는 보존되지 않음
Cost같은 경우에는 Kullback-Leibler divergence는 두 distribution이 완벽하게 일치 할 때 0의 값을 갖음
고차원에서 i번째 객체 이웃들을 선택할 확률 분포와 저차원에서 똑같은 아이에 대해서 이웃들이 섞이게 될 확률 분포를 완벽하게 일치 시키게 되면(i와 j 의 인덱스는 같음) 고차원에서 갖는 특징이 저차원에서 그대로 보존된다는 뜻
Kullback-Leibler divergence는 다음과 같이 계산함
Kullback-Leibler divergence를 이용해서 찾아내야 하는 미지수는 y임
이 식에서 x들은 데이터가 주어졌기 때문에 알고 있음
$y_{i}$와 $y_{j}$는 모르는 미지수
찾아 내야 되는 좌표계
미지수를 가져다가 미분을 해서 Gradient 알고리즘을 사용
Cost Function을 최소화하는데 있어서 이 Cost Function의 Gradient가 쉽게 나옴(위의 식)
Cost Function for a Low-dimensional Representation?
실제 Cost Function 미분하는 일은 귀찮고 짜증남
$y_{k}$가 $q_{ij}$에 영향을 미쳐서 미분 까다로움 그러나 결과물은 심플
논문에서 실제로 구현 안해줌
Gradient of the cost function(Optional)?
간단하게 의미만 보여줌
찾아가는 부분들은 강의자료 보고 직접 하기
여기서 핵심은 첫 번째 파트(두 번째 줄)는 x에 대한 식이기 때문에 상수 취급해도 됨
우리가 변화시킬 수 있는 것은 y라는 low dimension에서의 좌표계로 low dimension에서의 좌표계는 빨간색 q에 영향을 미치지 파란색 p에는 영향을 미치지 않음
이 부분을 날린 것이 C'
원래 오리지널 코스트를 $y_{t}$에 대해서 미분한 것은 앞부분을 날려버린 C'을 y에 대해서 미분한 것과 사실 같음
모든 i에 대해서 1번이 모든 j에 대해서 2번이 i와 j가 t가 아닐 때 3번이 나옴
$y_{t}$에 대해서 미분하고파
원래의 C' Cost를 세 개의 식으로 나눔
t가 앞쪽에 나와있을 때, 뒤에 있을 때, 양 쪽 다 없을 떄
이 세 파트를 따로 따로 계산
식을 좀 단순히 하기 위해 $d_{ti}$ 정의. 제곱이기 때문에 바꿔도 됨
t가 앞 쪽, 뒤 쪽, 양 쪽에 다 없는 것
마지막 줄에 $y_{t}$가 분모에서 한 번 등장함 -> 까다로움
3가지가 각각 t라는 항목이 어디에 들어가 있느냐에 따라 달라짐
1번은 분자에, 2번은 분자, 분모에, 3번은 없지만 k=j가 아닐때 중에서 k가 t인 상황에서 영향 미침
첫 번째 파트에 해당하는 Gradient만 구하기?
파란색 p는 y와는 아무런 상관이 없음
두 번째 파트?
세 번째 파트?
1번과 3번을 Gradient of the cost function을 더하면?
다 더하면?
시간을 두고 각자 해보는 것을 권장
From the original paper와 In this lecture note 비교?
똑같음
180도 치환을 했다고 보면 됨
식 자체가 첨자들이 다르다고 해서 문제가 되는 것은 아님
Symmetric SNE?
아까는 i|j와 j|i가 달랐음
i|j는 j를 기준으로 i라는 객체가 이웃으로 뽑힐 확률을 의미
j|i 경우에는 i를 기준으로 j가 이웃으로 뽑힐 확률은 의미
이 둘이 다름
symmetirc SNE에서는 given을 빼고
로 만듦 -> Gradient 단순하게 만들어짐
문제점: Crowding problem
가우시안 분포에서 거리가 길어지면 급격하게 감소함
하고 싶은 것은 조금 더 꼬리는 두껍고 긴 분포가 있어서 거리가 멀어졌을 때 이 선택이 급격하게 확률이 줄어드는 걸 좀 방지하고 싶음
정규분포보다 훨씬 더 봉우리는 낮고 꼬리가 두터운 분포는 t분포
t-SNE는 crowding problem을 감소기키기 위해서 t분포 사용
정규분포보다 봉우리는 낮고 꼬리는 두꺼운 분포를 사용함
Gradient 계산
원래 SNE에 대한 Gradient를 계산할 수 있었으면 나머지 Gradient는 어렵지 않게 계산 가능
따로 직접 해보기
t-SNE Examples?
t-SNE가 각각의 본질적인 모델들이 가지고 있는 응집성을 조금 더 잘 표현할 수 있음
Wiki t-SNE
Embedding Projector by Google
댓글