여러 distance 정리 - 1

안녕하세요~! pulluper 입니다. :)

 

오늘은 machine learning 에서 사용하는 여러가지 distance 를 비교, 분석 해 보는 시간을 가져보려고 합니다. 

 

요새 '사회적 거리두기' 가 4단계로 지정된다고 하는데요.

 

여기서 '거리' 란 무엇일까요?

 

위키피디아에 따르면  "거리(距離)는 어떤 사물이나 장소가 공간적으로 얼마나 멀리 떨어져 있는가를 수치로 나타낸 것이다." 

 

라고 하네요! 즉, 거리란 얼마나 차이가 있느냐의 개념으로 이해 할 수 있겠네요!

---

1. 거리란?

 

machine learning 에서도 이 거리의 개념이 아주 많이 사용됩니다.  

 

수학적으로 거리는 어떤 집합 X위의 함수로 정의됩니다. 

 

집합X의 두원소 x, y 에 대하여, 그 두 원소간의 거리는 다음과 같이 정의됩니다. 

 

d: X $\times$ X -> [0, $\infty$)

 

이때, 거리함수 d 는 다음 조건을 만족해야 합니다.

 

• $\forall x, y \in X, d(x, y)>=0$
• $d(x, y)  = 0 <-> x = y$                      : 어떤 거리가 0 이면 같은 원소에 대한 거리이다. 
• $d(x, y) = d(y, x)$                               : x 에서 y 까지의 거리는 y 에서 x 까지의 거리와 같다.  (대칭성)
• $d(x, z) + d(z, y) <= d(x, y)$             : 거리들은 항상 최단거리이다.                                     (삼각부등식 만족)   

이제 거리함수 d 가 정의된 집합 X는 거리공간 (X, d) 이 되며,  이는 그냥 거리함수가 주어진 집합입니다. :)

 

우리가 주로 사용하는 euclidean 공간은 잘 정의된 거리공간입니다. 

---

2. Distance, Similarity, Loss

 

거리는 유사도와 비슷한 개념입니다.

 

예를들어 2차원 좌표에서 두점의 거리가 가깝다는것은

 

그 위치가 그만큼 유사하다는 뜻이기 때문에 그렇게 해석 될 수 있습니다. 

 

따라서 이러한 거리들은 machine learning 에 있어서 다음과 같이 loss function 으로 사용이 될 수 있습니다.

 

어떤 deep neural network 를 $\theta$ 에 대한 parameteric fucntion $f_{\theta}$ 라고 하고, 

 

input x에 대한 network 의 output 과 ground truth y간의 거리 D가 가깝도록 (유사하도록)

 

network 의 parameter 들을 최적화 시켜주면 

 

$argmin_{\theta}D(f_{\theta}(x), y)$ 이와 같은 식이 나오게 됩니다. 

 

실제로 이러한 수식을 GD(gradient discent)등의 방식으로 최적화 하는것이

 

supervised learning 의 입장에서 일반적인 관점이므로 거리를 loss 로도 해석할 수 있습니다.

 

그렇다면 여러 거리와 그 특성들을 알아둔다면 적절한 loss 를 사용하는데 도움이 될 것입니다. 

---

3. L1 distance (맨하탄 거리, taxicab geometry) 

 

먼저 두 n차원 벡터를 다음과 같이 나타내겠습니다. 

 

$X = (x_1, x_2, ..., x_n), Y = (y_1, y_2, ..., y_n) \in R^{n} $. 

 

많은 regression 문제에 쓰이는 L1 distance 다음과 같이 표현할 수 있습니다. 

 

$D(X, Y) = \sum_i^n|x_i - y_i|$ 

 

특징은 outlier 에 강건하고 domain 에 따라 변화율이 일정하다는 것입니다. 

 

regularization 에도 쓰이고, 기본적인 regression 에도 쓰이며,

 

perceptual loss 를 위한 VGG network 에서 feature 간의 거리차이를 계산하는데도 쓰입니다. 

---

4. L2 distance (유클리드 거리, euclidean distance)

 

예전부터 잘 알고있는 좌표축상에서의 최소거리를 뜻하는 euclidean diatance 가 L2 distance 입니다.

 

또한 처음 regression 배울때 사용되는 mean square error 가 바로 이 L2 distance 입니다.

 

$D(X, Y) = (\sum_i^n(|x_i - y_i|)^2)^\frac{1}{2}$

 

특징을 생각해보면, L1 에 비해 outlier 에 강건하지 않은것과

 

x 가 변할때 그 기울기(변화율이) 정답에 가까울 수록 완만해진다는 것입니다. 

 

이런 특성을 적용하여 L1 과 L2 loss 가 합쳐진 smooth L1 loss 도 있습니다. 

 

사용되는 부분은 또한 regularization 에도 쓰이고, regression 문제에 사용됩니다. 

---

5. L-$\infty$ distance (Chebyshev distance)

 

L-$\infty$ distance 는 chebyshev distance 라고도 불리우며

 

$D_{chebyshev} = max_i (|x_i - y_i|)|$

 

chebyshev 거리는 각 dimension 의 L1 거리들 중 최댓값을 구하는 것입니다. 

 

예를들면, x = (1, 3, 2), y = (7, 0, -3) 이라 할때, |x - y| = |(-6, 3, 5)| 이므로    

 

$D_{chebyshev} (x, y) = max_i (|x_i - y_i|)| = 6$ 입니다. 

 

이는 2차원 체스판에서 어느 방향이나 갈 수 있는 킹과 퀸의 이동거리로도 설명을 할 수 있습니다. 

---

6. 민코프스키거리 (Minkowski distance)

 

민코프스키 거리는 여태까지의 거리들에 대한 일반화입니다. 

 

$D(X, Y) = (\sum_i^n(|x_i - y_i|)^p)^\frac{1}{p}$

 

p = 1 인 경우 맨하탄 거리가 되고, 

 

p = 2 인 경우 유클리디안 거리, 

 

p = $\infty$ 인 경우는 체비쇼프 거리가 됩니다. 

 

x = (1, 1), y = (2, 1), z = (2, 2) 라 할때 

 

p = 2 일때의 민코프스키 거리는 다음과 같습니다(유클리디안 거리)

 

d(x, y) = 1, d(y, z) = 1, d(x, z) = sqrt(2) 이므로 d(x, y) + d(y, z) >= d(x, z) 의 삼각부등식을 만족합니다. 

 

이번에는 p < 1 일 경우를 생각해봅시다. (p=0.5)

 

d(x, y) = 1, d(y, z) = 1, d(x, z)=4 이므로 삼각부등식을 만족하지 않습니다. 

 

따라서 p <1 일때는 위에서 정의한 거리는 아니게 됩니다. 

---

 

 

reference

 

https://junklee.tistory.com/29

L1, L2 Norm, Loss, Regularization?

https://en.wikipedia.org/wiki/Main_Page

Wikipedia, the free encyclopedia