Summary

본 내용은 MIT 18.065 강의 33의 일부 내용 정리입니다. 자세한 내용은 해당 강의를 참고하세요.

공간상에 x1, x2, x3 벡터가 주어졌는데, 우리가 알고 있는 정보는 각 벡터 사이의 거리뿐이다. 즉, x1 에서 x2 의 거리, x1 에서 x3까지의 거리, x2 에서 x3 까지의 거리이다.

이 정보를 행렬로 구성하면, 거리행렬 Distance Matrix 는 다음과 같다.

\(D_{ij} = || x_i - x_j ||^2\)

그럼, 거리행렬이 주어졌을 경우, x1, x2, x3 의 위치를 알 수 있을까? 이 질문은 무선 센서망이나 머신 러닝에서 응용될 수 있다. training set 의 sample 들은 고차원의 feature vectors 로 변환이 된다. 이때 이 벡터들은 유사한 벡터들끼리 모여 있게 된다. 이렇게 모여 있는 공간을 찾아서 kernel trick 등을 이용해서 저차원으로 변환 후 classification 문제에 사용할 수 있다.

이제 거리행렬 D 에서 \(X^TX = G\) 가 나오는데 사용할 공식은 아래와 같다.

\(X^TX = G = -1/2(D - 1d_1^T - d_1 1^T)\)

  1. X 는 유도되는 위치 행렬
  2. G 는 위치행렬을 이용한 공분산행렬

본 내용에서는 공식에 대한 유도 과정을 포함하지 않고, 단순 예제값을 이용한 결과의 검토만 진행한다. 그리고 위치 행렬 X 는 여러방식으로 구할 수 있는데, 하나는 대칭행렬 고유값 분해를 이용하고 다른 하나는 소거를 이용한 Cholesky 분해를 사용할 수 있다. 여기서는 대칭행렬 고유값 분해를 이용한다.

# 3개의 벡터가 있고, 
x1 <- c(2, 2)
x2 <- c(5, 2)
x3 <- c(2, 6)

# 각 벡터 사이의 거리는 
x12 <- sum((x1 - x2)^2)
x13 <- sum((x1 - x3)^2)
x23 <- sum((x2 - x3)^2)

print(c(x12, x13, x23))
## [1]  9 16 25
# X 행렬 구성
data.frame(x1, x2, x3) # 테스트로 구성
##   x1 x2 x3
## 1  2  5  2
## 2  2  2  6
Xm <- as.matrix(data.frame(x1, x2, x3))
Xm 
##      x1 x2 x3
## [1,]  2  5  2
## [2,]  2  2  6
t(Xm) %*% Xm # 테스트로 XTX 를 구해본다. 이후 G 를 통해서 동일한 값이지 검증하기 위해서임
##    x1 x2 x3
## x1  8 14 16
## x2 14 29 22
## x3 16 22 40
# 거리행렬 Distance matrix 구성
# D_ij = || x_i - x_j ||^2
Dm <- matrix(c(0, x12, x13, x12, 0, x23, x13, x23, 0), ncol = 3, byrow = T)
Dm
##      [,1] [,2] [,3]
## [1,]    0    9   16
## [2,]    9    0   25
## [3,]   16   25    0
# 그럼, 거리행렬 D 에서 위치행렬 X 를 구성할 수 있을까? 
# G = XTX 라고 한다면, G 의 대각성분은 x1^2, x2^2, x3^2 과 동일하다.
d <- c(sum(x1^2), sum(x2^2), sum(x3^2))
d1 <- diag(d)
d1
##      [,1] [,2] [,3]
## [1,]    8    0    0
## [2,]    0   29    0
## [3,]    0    0   40
G <- -1/2*(Dm - matrix(c(1,1,1)) %*% t(matrix(c(d))) - matrix(c(d)) %*% t(matrix(c(1,1,1))))
G
##      [,1] [,2] [,3]
## [1,]    8   14   16
## [2,]   14   29   22
## [3,]   16   22   40
# 이제 G 로부터 위치행렬 X 를 복구한다.
# G = XTX 는 대칭행렬이다. 즉 고유값 분해가 가능하다.
# 대칭행렬 고유값 분해 사용
ev <- eigen(G)
L <- ev$values # 고유값 분리
V <- ev$vectors
V %*% diag(L) %*% t(V) # 복원 검토
##      [,1] [,2] [,3]
## [1,]    8   14   16
## [2,]   14   29   22
## [3,]   16   22   40
# 위치 행렬 X 구성
X <- diag(L)^(1/2) %*% t(V)
X
##               [,1]          [,2]          [,3]
## [1,] -2.813076e+00 -4.702173e+00 -5.920434e+00
## [2,] -2.942808e-01 -2.624799e+00  2.224515e+00
## [3,]  3.473930e-08 -1.068902e-08 -8.016762e-09
# x1과 x2 의 거리를 계산해서 위에서 구한 x12, x13, x23 의 거리와 비교한다.
X12 <- sum((X[,1] - X[,2])^2)
X13 <- sum((X[,1] - X[,3])^2)
X23 <- sum((X[,2] - X[,3])^2)

print(c(X12, X13, X23))
## [1]  9 16 25