Metric Learning 1
본 글은 2020-2학기 “컴퓨터 비전” 수업의 내용을 개인적으로 정리한 것입니다. 지적은 언제나 환영입니다 :)
keywords
- Metric
- semantic distance
- Mahalanobis Distance
- Metric Learinng: a fist approach
- LMNN
What is a Metric?
Metric은 집합 안에 있는 모든 원소 사이의 거리distance를 수치화하는 함수function이다.
일반적으로 Euclid distance, Manhattan distance, cosine similarity 등이 Metric function으로 쓰인다.
Metric 두 대상 사이의 distance를 측정하는 것이지만, 반대로 생각하면 두 대상 사이의 유사도similarity를 따지는 데에도 사용할 수 있다!
일반적인 Metric이 두 대상 사이의 기하학적 특징을 이용해 거리를 부여한다면, 컴퓨터 비전, 그 중에서도 Metric Learning은 두 대상 사이의 semantic distance에 주목한다!
Pairwise vs. Triplet
Metric을 학습 방법에는 크게 두 가지 접근이 있다.
Pairwise
논의의 편의를 위해 대상 $\{ x_1, x_2, x_3 \}$에 대한 Metric을 학습한다고 가정하자.
우리의 목표는 두 함수 $D$와 $f$를 학습하는 것이다.
함수 $D$는 두 입력을 받아 두 입력 사이의 거리를 반환한다.
\[D(x, y) = \textrm{distance btw two objects}\]함수 $f$는 대상에서 feature를 추출하는 feature extractor이다.
\[f(x) = \textrm{feature vector}\]이제 두 함수 $D$, $f$를 잘 조합해 다음의 Pairwise relation을 학습시킨다고 하자.
\[D(f(x_1), f(x_2)) \downarrow \quad D(f(x_1), f(x_3)) \uparrow\]즉, Metric Learning가 두 대상의 extracted feature의 값을 최대한 낮추는 것을 목표로 한다는 말이다.
Loss minimization과 비슷한 맥락이다.
Triplet
반면에 Triplet은 아래와 같은 relation을 학습시킨다.
\[D(f(x_1), f(x_2)) < D(f(x_1), f(x_3))\]즉, 대상 사이의 수치화된 거리값을 줄이거나 늘리는 것이 아니라, 거리값의 대소 관계를 학습하는 것을 목표로 한다.
Triplet relation을 학습시키는 것은 단순히 다소 관계만 만족시키면 되기 때문에 Pairwise relation을 학습시키는 것보다 더 유연flexible하다고 한다.
종합하자면, Metric Learning은 주어진 데이터셋에서 함수 $D$, $f$가 pairwise relation 또는 triplet relation을 잘 출력하도록 학습시키는 분야다.
Classical Metric Learning
Deep Learning 이전의 Metric Learning에 대한 부분이다.
실제 연구에서는 안 쓰겠지만, 고전적인 방법은 지금의 DL 기반 방법들을 이끌어내는 동기를 부여하고, DL 기반 접근에 영감을 준다.
Mahalanobis Distance
두 점에 대한 Euclidean metric $D_E$는 아래와 같이 정의한다.
\[D_E(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x}-\mathbf{y})^T (\mathbf{x}-\mathbf{y})}\]이때, Mahalanobis distance $D_M$은 아래와 같이 정의한다.
\[D_M(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x}-\mathbf{y})^T M (\mathbf{x}-\mathbf{y})}\]자료를 더 찾아보니, Mahalanobis distance는 multi-variate distribution에서 거리를 재는 좋은 도구라고 한다.
multi-variate distribution 상의 한 점을 $\mathbf{x}$라고 하고, distribution의 평균을 $\mu$, 분산을 $\Sigma$라고 했을 때 Mahalanobis distance는 아래와 같다.
\[D_{\Sigma}(\mathbf{x}, \mu) = \sqrt{(\mathbf{x}-\mu)^T \, {\Sigma^{-1}} \, (\mathbf{x}-\mu)}\]흥미로운 점은 multi-variate normal distribution $\mathcal{N}(\mathbf{x})$에도 Mahalanobis distance가 등장한다.
\[\begin{aligned} \mathcal{N}(\mathbf{x}) &= \frac{1}{\sqrt{(2\pi)^k \lvert \Sigma \rvert}} \exp{\left( - \frac{1}{2} (\mathbf{x}-\mu)^T \, {\Sigma^{-1}} \, (\mathbf{x}-\mu) \right)} \\ &= \frac{1}{\sqrt{(2\pi)^k \lvert \Sigma \rvert}} \exp{\left( - \frac{1}{2} {\left(D_{\Sigma}\right)}^2 \right)} \end{aligned}\]Mahalanobis distance $D_M$에서 주목할 점은 행렬 $M$을 학습시킬 수 있다learnable는 것이다!
우리는 주어진 데이터셋으로부터 $M$을 학습시키게 되는데,1 가장 직관적이고 unsupervised 방법은 데이터셋의 covariance matrix $\Sigma$를 구해 그것의 역행렬을 $M$으로 삼는 것이다. $M={\Sigma}^{-1}$
수업에서는 Mahalanobis distance을 다루는 방법을 소개하였다.
- A first approach to distance metric learning
- Large Margin Nearest Neighbor(LMNN)
A first approach to distance metric learning
데이터셋에서 pair를 바탕으로 두 집합 $S^{+}$, $S^{-}$를 만든다.
\[\begin{aligned} S^{+} &= \textrm{The set of similar pairs} \\ S^{-} &= \textrm{The set of disimilar pairs} \end{aligned}\]그리고 아래와 같이 최적화 문제를 구성한다.
\[M^{*} = \underset{M}{\textrm{argmin}} \sum_{\left(\mathbf{x}_i, \mathbf{x}_j\right) \in S^{+}} (\mathbf{x}_i - \mathbf{x}_j)^{T} \, M \, (\mathbf{x}_i - \mathbf{x}_j)\]당연히 $S^{+}$에 속하는 pair $(\mathbf{x}_i, \mathbf{x}_j)$에 대한 거리값은 작아야 한다.
이때, 위의 최적화 문제에서 $S^{-}$를 고려한 constraint를 추가해준다!
\[\begin{aligned} M^{*} &= \underset{M}{\textrm{argmin}} \sum_{\left(\mathbf{x}_i, \mathbf{x}_j\right) \in S^{+}} (\mathbf{x}_i - \mathbf{x}_j)^{T} \, M \, (\mathbf{x}_i - \mathbf{x}_j) \\ & \textrm{s.t.} \; \sum_{\left(\mathbf{x}_i, \mathbf{x}_j\right) \in S^{-}} (\mathbf{x}_i - \mathbf{x}_j)^{T} \, M \, (\mathbf{x}_i - \mathbf{x}_j) \ge 1 \end{aligned}\]즉, $S^{-}$에 속하는 pair $(\mathbf{x}_i, \mathbf{x}_j)$에 대한 거리값은 어느 정도 -Margin- 만큼은 보장되어야 한다는 것이다.
이 방식으로 최적화 문제를 풀어서 $M^{*}$을 구했다면, Mahalanobis distance는 데이터셋을 아래와 같이 잘 분할하게 된다.
"Distance metric learning with application to clustering with side-information", NIPS 2002
Large Margin Nearest Neighbor
Large Margin Nearest Neighbor, 줄여서 LMNN의 경우 좀더 복잡한 형태의 Objective function을 채용한다. 한번 살펴보자!
먼저 $S^{+}$에 대한 부분을 살펴보자. LMNN도 마찬가지로 positive pair의 거리합이 최소가 되는 것을 목표로 한다.
\[\begin{aligned} M^{*} &= \underset{M}{\textrm{argmin}} \sum_{i, j} \eta_{ij} \cdot {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 \\ & \textrm{where} \\ & \eta_{ij} = \begin{cases} 1, \quad (\mathbf{x}_i, \mathbf{x}_j) \in S^{+}\\ 0, \quad (\mathbf{x}_i, \mathbf{x}_j) \in S^{-} \end{cases} \end{aligned}\]$\eta_{ij}$라는 indicator variable을 도입해 positive pair의 거리합을 최소화하도록 디자인 했다.
여기서 끝나는게 아니라 $S^{-}$에 대한 부분도 고려한 텀을 추가해준다. 해당 텀만 따로 작성해보면 아래와 같다.
\[\sum_{i, j, k} \eta_{ij}(1-\eta_{ij}) \cdot h\left[ 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \right]\]위 텀은 세 점 $\{\mathbf{x}_i, \mathbf{x}_j, \mathbf{x}_k\}$에 대한 Triplet relation을 고려하는 텀으로 $(\mathbf{x}_i, \mathbf{x}_j) \in S^{+}$이고, $(\mathbf{x}_i, \mathbf{x}_k) \in S^{-}$일 때를 고려한다.
이때, $h\left[ 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \right]$는 hinge function으로 아래와 같다.
\[h\left[ 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \right] \\ = \max \left(0, 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \right)\]이 hinge function의 값을 최소화하려면 $1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \le 0$ 이 되어야 한다. 그래야 hinge function의 값이 0이 되기 때문이다.
이것을 다시 쓰면
\[\begin{aligned} 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 & \le 0 \\ 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 & \le {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \end{aligned}\]의 조건을 만족해야 하는 것이 된다.
이것은 negative-pair dist가 positive-pair dist보다 Margin $1$ 만큼 더 멀리있도록 만든다. 즉,
\[\begin{aligned} 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 & \le {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \\ \textrm{Margin} + \left(\textrm{positive-pair dist}\right)^2 & \le \left(\textrm{negative-pair dist}\right)^2 \end{aligned}\]이제 Pairwise 텀과 Triplet 텀을 종합하면 아래와 같다.
\[M^{*} = \underset{M}{\textrm{argmin}} \left\{ \sum_{i, j} \eta_{ij} \cdot {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 \right\} + c \left\{ \sum_{i, j, k} \eta_{ij}(1-\eta_{ij}) \cdot h\left[ 1 + {D_M\left(\mathbf{x}_i, \mathbf{x}_j\right)}^2 - {D_M\left(\mathbf{x}_i, \mathbf{x}_k\right)}^2 \right] \right\}\]즉,
1. pair $(\mathbf{x}_i, \mathbf{x}_j)$가 positive-pair라면, 두 점의 거리값을 줄여 서로 가까워지도록 끌어당긴다; Pull
2. pair $(\mathbf{x}_i, \mathbf{x}_k)$가 negative-pair라면, 두 점의 거리값을 positive-pair의 가장 큰 거리값보다 1 만큼의 여유Margin를 두고 멀어지도록 밀어낸다; Push
처음의 시도와 비교했을 때, LMNN는 좀더 동적이라고 말할 수 있다.
앞의 시도에선 negative-pair에 대해 거리값이 $1$이라는 지정된 값보다 크기만 하면 충분했다. 그러나 이런 접근은 허점이 있는데, positive-pair의 거리값이 도저히 1보다 좁혀지지 않을 수도 있다는 것이다; positive-pair에 대해선 constraint를 만족하면서 거리합이 줄어들기만 하면 된다는 점을 상기하라.
그래서 negative-pair가 positive-pair보다 더 가까이 위치하는 상황이 충분히 가능하다는 점이 허점으로 지적받는다.
LMNN에선 이것을 극복해 negative-pair가 positive-pair보다 Margin $1$만큼 떨어지도록 최적화한다.
이때, negative-pair의 거리값의 기준이 되는 positive-pair의 거리값이 고정된 것이 아니라 동적으로 변하기 때문에 LMNN은 더 동적으로 작동한다고 평가한다.
Metric Learning + DL
\[D_M (\mathbf{x}_i, \mathbf{x}_j) = \sqrt{(\mathbf{x}_i - \mathbf{x}_j)^T M (\mathbf{x}_i - \mathbf{x}_j)}\]고전적인 Metric Learning에선 Mahalanobis distance의 $M$ 값을 구하는 최적화 문제에 집중했다.
\[D\left(f(\mathbf{x}_i), f(\mathbf{x}_j)\right)\]고전적인 방법에서도 feataure extractor $f$를 사용하기는 했지만, 이미지 데이터를 그대로 사용하거나, 직접 디자인한 Image descriptor를 사용했다.
Metric Learning에서 DL이 도입되고부터는 distance metric을 학습하는 게 아니라, feature extractor $f$를 학습시키는 방향으로 발전해왔다.
다음 포스트에선 DL을 바탕으로 하는 Metric Learning에 대해 정리한다.
-
유의할 점은 $M$는 positive semi-definite matrix여야 한다는 점이다. 이 조건을 만족하지 않는다면, 복소수인 Mahalanobis dist를 얻는다… ↩