LMNN(Large Margin Nearest Neighbors)

안녕하세요. 오랜만에 글을 쓰게 되었습니다. 이번 글은 LMNN이라는 알고리즘으로 기존의 K-Nearest Neighbors를 보완한 모델입니다. 참고한 자료는 다음과 같습니다.

 

Distance Metric Learning for Large Margin Nearest Neighbor Classification (2009)

(저자 : Weinberger, Kilian Q., and Lawrence K. Saul.)

www.jmlr.org/papers/volume10/weinberger09a/weinberger09a.pdf

 

Online and Batch Learning of Pseudo-Metrics (2004)

(저자 : Shalev-Shwartz 외)

citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.9018&rep=rep1&type=pdf

 

LMNN 개념

sanghyukchun.github.io/38/

LMNN(Large Margin Nearest Neighbors) (NIPS 2006) LMCA(Large Margin Component Anaylsis) (NIPS 2007) - README

 

이 알고리즘을 공부하기 앞서 다음과 같은 선행 지식이 있어야 합니다.

- Distance Metric Learning

    - mapping 함수 D가 다음과 같은 조건을 만족하면 metric이라 함    

        - 용어

            - $\vec{x}_{i}$ : i번째 input vector

        - 설명

            - 1 : triangular inequality로 삼각형에서 두 변의 길이를 더하면 다른 1개 변과 길이가 같거나 크다는 점입니다.

            - 2 : non-negativity로 i 벡터에서 j 벡터까지의 거리는 0보다 크거나 같습니다.(삼각형의 점과 점 사이 거리를 상상하셔도 됩니다)

            - 3 : symmetry로 metric의 input으로 두 벡터를 넣을 때 순서를 바꿔도 결과는 같습니다.

            - 4 : distinguishability로 두 벡터 간 거리가 0이면 두 벡터는 같은 벡터임을 말합니다.

    - pseudometric : 위의 1~3의 조건을 만족하는 경우

 

위를 고려하면 D는 사실 거리값으로도 볼 수 있습니다. 즉, 우리가 흔히 쓰던 Euclidean distance measure가 D가 될 수 있습니다. 여기서 만약 $\vec{x}_{i}$를 linear transform 시킨 결과를 $\vec{x}^{\prime}_{i}  = \textbf{L} \vec{x}_{i}$라고 하고 D가 Euclidean distance measure라고 한다면 다음과 같이 바꿔 쓸 수 있습니다.

 

$D_{\textbf{L}}(\vec{x}_{i}, \vec{x}_{j}) = ||\textbf{L}(\vec{x}_{i} - \vec{x}_{j}) ||^{2}_{2}$   

(여기서 L은 matrix입니다)

 

위의 식을 간단히 나타내면 다음과 같이 변형할 수 있습니다.

 

$D_{\textbf{L}}(\vec{x}_{i}, \vec{x}_{j}) = D_{\textbf{M}}(\vec{x}_{i}, \vec{x}_{j}) = (\vec{x}_{i} - \vec{x}_{j})^{T} \textbf{M} (\vec{x}_{i} - \vec{x}_{j})$

 

이는 $\textbf{L}$을 $\textbf{M}$으로 변형시켜 만듭니다.

 

$ \textbf{M} = \textbf{L}^{T} \textbf{L}$

(M은 positive semidefinite matrix입니다)

 

위의 $D_{\textbf{M}}(\vec{x}_{i}, \vec{x}_{j}) = (\vec{x}_{i} - \vec{x}_{j})^{T} \textbf{M} (\vec{x}_{i} - \vec{x}_{j})$는 사실 Mahalanobis distance 식 형태이기도 합니다. 즉, Euclidean distance에서 Linear trnasform을 시키면 Mahalanobis 형태로 바뀌는 것이죠. Gaussian 분포의 quadratic form이기도 합니다.

 

그렇다면 이 Mahalanobis distance metrics는 어떤 목적으로 최적화를 하는 것일까요? 그것은 kNN에서 point 간 거리 계산에 쓰일 수 있습니다. 즉, 같은 클래스는 최대한 거리를 가깝게 하는 linear transform인 M을 찾는 것입니다.

 

이러한 식을 만족시키기 위해 저자는 다음과 같은 아이디어를 제안합니다.

여기서 $\vec{x}_{i}$와 $\vec{x}_{j}$는 같은 레이블을 가지고 있으며, j는 i의 target neighbor이라고 합니다. 반면 $\vec{x}_{i}$와 $\vec{x}_{l}$은 다른 레이블을 가지고 있어 l은 i의 impostor라고 합니다. 즉, i와 impostor와의 거리고 i와 target neighbor과의 거리 +1보다 작은 경우 i의 영역을 침범했다고 정의하는 것입니다.

 

위의 사진을 예시로 저자는 설명을 하는데 loss식을 통해 위의 margin에 들어온 impostor는 margin 바깥으로, target neighbor는 가깝게 만드는 것입니다. loss 식이 어떻게 만들어지는지 보겠습니다.

 

첫 번째 loss term은 위의 식입니다. 아까 i와 j는 같은 레이블을 공유한다고 했는데 즉, i와 j의 거리가 클수록 위의 값이 커지므로 이 값을 줄이는 쪽으로 학습을 시킵니다. 여기서 j --> i 부분의 화살표는 i에 속한 target neighbor만 의미합니다. 즉, i의 target neighbor이 아닌 경우 같은 레이블이어도 식에 반영을 안한다는 의미입니다. (target neighbor의 경우 i와의 거리 등으로 결정한다고 합니다)

 

두 번째 loss term은 위의 식입니다. 여기서 $[z]_{+}$는 max(z, 0)으로 standard hinge loss입니다. 즉, loss가 -로 떨어지는 경우 0으로 처리하는데 이는 i와 impostor l과의 거리가 1 + target neighbor과의 거리보다 작은 경우 loss값이 더해지며 반대는 0으로 처리됩니다. 다시 말해 margin에서만 벗어나면 loss를 더이상 주지 않는 것입니다. 여기서 $y_{il}$은 l이 i의 impostor인 경우 0, 같은 레이블인 경우 1이 되므로 impostor에 대해서만 계산하게 됩니다.

 

이를 통해 아래와 같은 loss 식이 만들어집니다.

여기서 $\mu$는 hyperparameter로 0에서 1사이 값을 가지며, 0.5가 제일 성능이 좋았다고 합니다.

 

여기까지가 LMNN 알고리즘에 대한 설명이었습니다. 

잘못된 점이나 질문 있으시면 말씀해주세요!