Distance, Similarity, and Norm
수학에서 정의하는 거리 함수의 정의와 머신러닝, 딥러닝, 추천시스템을 공부하며 봤던 여러 거리 함수와 유사도 함수들을 정리한다.
여기 나온 거리나 유사도, 놈 외의 다양한 방법이 있겠지만 여태까지 공부하면서 봤던 함수들 위주로 정리한다.
Distance Function
기본적으로 0에 가까울 수록 비슷하다.
Definition of distance function
- The distance between an object and itself is always zero.
$d(x, x) = 0$. - The distance between distinct objects is always positive.
$d(x, y) > 0$ if $x \neq y$. - Distance is symmetric: the distance from x to y is always the same as the distance from y to x.
$d(x, y) = d(y, x)$ - Distance satisfies the triangle inequality: if x, y, and z are three objects,
$d(x, z) \leq d(x, y) + d(y, z)$.
데이터 $x$와 $y$ 벡터를 아래와 같이 정의한다.
$x= \left[ x_1, x_2, ..., x_p \right],y = \left[ y_1, y_2, ..., y_p \right]$
$L_1$ distance = Manhattan distance
$L_1 (x, y) = \sum_{i = 1}^{p} | x_i - y_i | $
이때 $ | a - b | $는 절대값 부호다.
$L_2$ distance = Euclidean distance
$L_2 (x, y) = \sqrt{\sum_{i = 1}^{p} ( x_i - y_i )^2} = \sqrt{ (x - y)^2} $
가장 일반적으로 많이 사용하는 거리다.
$L_\infty$ distance = Chebyshev distance = Tchebychev distance = maximum metric
$L_\infty (x, y) = \underset{i}{max}(| x_i - y_i |)$
개별 element $i$들에 대해서 $L_1 (x_i, y_i)$을 구한 다음에 그 값의 최대값을 $L_\infty$ distance로 사용한다.
Mahalnobis distance
$x$와 $y$가 어떤 분포를 따르고, 두 변수의 공분산을 $\Sigma$로 나타낸다.
이때 마할노비스 거리는 아래와 같다.
만약, $x, y$가 컬럼 벡터라면,
$ d(x, y) = \sqrt{ (y - x)^T \Sigma^{-1} (x - y) } $
벡터 연산이라서 quadratic form으로 썼으며 $L_2$ 거리와의 차이점은 가운데 공분산 행렬이 들어간다는 것 하나다.
Weighted Euclidean distance라고 보면 된다.
Metric learning을 공부할 때 종종 봤던 거리다.
Similarity Function
기본적으로 값이 클수록 비슷하다.
Dot product
Euclidean dot product를 다룬다.
<$x$, $y$> = $x \cdot y$ = $ \sum_{i = 1}^{p} ( x_i \times y_i )$
만약, $x, y$가 컬럼 벡터라면,
= $x^T y$
Euclidean space에서 vector norm $|| x ||_2$ = $x \cdot x$로 정의한다.
그렇다면, dot product $x \cdot y$ = $x^T y$ = $|| x ||_2$ $|| y ||_2$ cos $\theta$다.
Cosine similarity
$x \cdot y$ = $x^T y$ = $|| x ||_2$ $|| y ||_2$ cos $\theta$
위 식을 코사인에 대해서 정리하면,
cos $\theta$ = $ \frac{ x \cdot y }{ || x ||_2 || y ||_2 } $ 다.
코사인 유사도는 [-1, 1]의 범위를 갖는다.
대괄호 [와 ]은 각각 해당하는 숫자를 포함한다.
즉, 코사인 유사도의 최대값은 1이고 최소값은 -1이다.
Pearson correlation
이전에 블로그에 쓴 글 (링크)에서 이미 설명했으므로 식만 적는다.
$\rho_{X, Y} = \frac{ Cov \left[ X, Y \right] }{ \sigma_X, \sigma_Y }$
피어슨 상관계수도 코사인 유사도처럼 [-1, 1]의 범위를 갖는다.
Spearman corrleation
스피어만 상관계수는 데이터의 값 자체가 아니라 rank 순위를 사용한다.
R($x_i$)는 $x_i$가 $ x_1, x_2, ..., x_p $의 p개의 값들 중에서의 순위를 뜻한다.
R($y_i$)도 마찬가지로 $y_i$의 순위를 의미한다.
스피어만 상관계수 $r_s$는 R[$x_i$]와 R[$y_i$]으로 Pearson correlation을 계산한 값이다.
$ r_s (X, Y) $ = $ \frac{ Cov R ( X ) , R ( Y ) }{ \sigma_{ R ( X ) } \sigma_{ R ( Y ) } }$
Jaccard Index
두 개의 집합의 요소의 수를 가지고 측정하는 방법이다.
J(A ,B) = | A $\cap$ B | / | A $\cup$ B |
여기서의 | A |는 A의 cardinality를 의미한다.
Gaussian Kernel
K($x, x'$) = exp( $ \frac{ || x - x' ||^2 }{ 2 \sigma^2 } $ )
이때 $\sigma$는 $x$의 표준편차다.
$L_2$ 거리를 표준편차로 스케일링한 다음에 exponential을 취한 값으로
지수가 0에 가까워질수록 전체 값은 1에 가까워진다.
두 값의 차이가 커질수록 커널 K의 값도 커진다.
거리 함수의 특성상 0이거나 양수이므로
exponential의 특성상 양수의 값을 공역으로 지니지만, 그 중에서도 1과 같거다 더 큰 값을 공역으로 갖게 된다.
분포의 차이 등에서 은근 자주 보이는 함수다.
Norm
Vector norm과 Matrix norm이 있는데 둘 다 벡터나 행렬의 크기를 설정하는 함수다.
즉 무언가의 크기다.
Vector Norm
여기서는 vector $x$의 element를 $n$개라고 한다.
일반적으로 많이 쓰는 벡터 놈 (혹은 노름)은 아래와 같이 정의한다.
Euclidean space에서 vector norm $|| x ||_2$ = $ \sqrt{x \cdot x}$로 정의한다.
위에서 정의한 벡터 놈은 $L_2$ norm이라고 한다.
$L_1$ norm의 경우 $ \sum_{i}^{n} | x_i | $로 정의된다.
이를 일반화한 $L_p$ norm은 아래와 같다.
$|| x ||_p$ = $ ({\sum_{i} | x_i | })^{1 / p }$
max norm 혹은 $L_\infty$ norm은 아래와 같이 정의된다.
$|| x ||_\infty$ = $ max( |x_1|, |x_2|, ..., |x_n|, )$
Matrix Norm
벡터와 마찬가지로 행렬의 크기를 정의한다.
지금 기억하는 행렬 놈 중에서 논문을 보다가 발견한건 Frobenius norm 뿐이라서 일단 이것만 기록한다.
Frobenius norm
행렬 $A$는 m x n 크기의 직사각형 행렬이다.
$ || A ||_F $ = $ \sqrt{ \sum_i^m \sum_j^n |a_{ij}|^2 } = \sqrt{trace(A * A)} = \sqrt{ \sum_i^{min(m, n)} \sigma_i^2 (A) }$
trace는 행렬의 sum of diagonal terms다.
$\sigma_i(A)$는 행렬 A의 singular value다.
References:
https://en.wikipedia.org/wiki/Distance
https://en.wikipedia.org/wiki/Similarity_measure
https://en.wikipedia.org/wiki/Pearson_correlation_coefficient
https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient
https://overnap.com/manhattan-distance-and-chebyshev-distance/
https://gaussian37.github.io/ml-concept-mahalanobis_distance/
https://en.wikipedia.org/wiki/Gaussian_function
https://www.statisticshowto.com/mahalanobis-distance/
https://en.wikipedia.org/wiki/Norm_(mathematics)
https://en.wikipedia.org/wiki/Lp_space
https://en.wikipedia.org/wiki/Matrix_norm
https://hichoe95.tistory.com/58#google_vignette