https://arxiv.org/pdf/1404.4661.pdf
이미지 간의 distance(similarity)를 구하는 방법(함수)를 학습하는 model이다.
detection & classfication 신경망을 거치는 경우, 그 출력을 그대로 similarity에 사용하면 안되나?
image classification과 similar image ranking task는 본질적으로 다르다.
출력 뉴런 값들을 저장해 놓았다가 distance를 계산하는 방법을 생각해 보았는데, class 내의 두 이미지 P, Q의 비교를 위해 "P, Q가 다른 class 각각에 속할 확률이 얼마나 되는지"를 사용하기 때문에 당연히 부정확하다.
detection & classification 신경망의 출력을 k(.)라고 하면 D(k(P), k(Q))를 구한다는 건데, 어쨌든 k(.)도 신경망을 통과한 output이기는 하지만 f(.)는 similarity를 위해 학습한 신경망이고, k(.)는 classification을 위해 학습한 신경망이다. 따라서 k(.)를 사용하는 것은 classification을 위해 학습한 신경망의 출력을 그냥 similarity에 가져다 쓰는 것 뿐이라 오히려 더 부정확할 수 있다.
그렇다면 신경망을 하나 더 사용한다고 했을 때, ResNet이나 VGG같은 CNN만 사용해서 similarity를 판정할 수 있나?
신경망의 성격은 어떤 training set을 사용했는가가 결정하니까 image similarity를 판정하도록 training set을 만들어 학습시키면 일반적인 CNN도 similarity 판정에 사용할 수는 있는데 아무래도 성능이 좀 떨어진다.
간단히 예를 들면 input으로 triplet을 받도록 설계하고 \\(p^+_i\\) 를 맞추도록 하는 식으로 학습시키는 방법을 생각해볼 수 있다.
Abstract
이미지로부터 직접 similarity metric을 학습한다.
input으로 triplet을 받기 때문에 논문에 triplet sampling algorithm에 대한 내용도 나와있다.
models based on hand-crafted visual features and deep classification models보다 성능이 좋다.
1. Introduction
기존의 hand-crafted features(방법)로 image features(특징)를 뽑아낸 다음 image similarity model을 학습시키는 방법은 hand-cratfted features의 성능에 크게 좌우된다. 반면 deep ranking은 features와 similarity model을 동시에 학습한다.
triplet \\(t_i = (p_i, p_i^+, p_i^-)\\)은 query image, positive image, negative image로 이루어진 이미지 묶음이다.
image similarity relationship을 triplet을 이용해 표현하게 된다.
이 논문의 main contributions는 다음과 같다.
- image에서 직접 fine-grained image similarity model을 학습할 수 있는 deep ranking model과 training data를 얻을 수 있는 bootstrapping 방법 제안
- multi-scale network structure 제안
- online triplet sampling algorithm 제안.
- evaluation dataset publishing.
2. Related Work
-
3. Overview
최종적인 목표는 image similarity models를 훈련시키는 것이다.
두 이미지 P와 Q의 similarity \\(D(. , .)\\)는 Euclidean distance의 제곱으로 정의한다.
\\[D(f(P), f(Q)) = ||f(P) - f(Q)||^2_2\\]
\\(f(.)\\)는 이미지를 Euclidean space의 한 점으로 mapping하는 image embedding function이다.
P, Q가 더 닮아있을 수록, Euclidean space의 두 점 사이의 거리인 \\(D(. , .)\\)값이 더 작아진다.
Euclidean space에서 인접 값을 찾는 문제는 nearest neighbor search algorithm으로 해결할 수 있기 때문에 문제는 \\(f(.)\\)다. \\(f(.)\\)가 두 이미지 P, Q가 닮아있는 만큼 둘을 인접한 곳에 mapping해주면 해결되는건데, 이 \\(f(.)\\)를 정의하기 위해 보통 hand-crafted features를 사용해 왔지만 여기서는 deep learning으로 \\(f(.)\\)를 학습한다.
두 이미지가 얼마나 닮아있느냐를 나타내기 위해 \\(D(. , .)\\)를 그대로 사용하는 것이 아니라 relevance score를 사용한다.
set of images \\(\mathcal{P}\\)에 속한 두 이미지 \\(p_i, p_j\\)에 대해, relevance score는 다음과 같다.
\\[r_{i,j} = r(p_i, p_j)\\]
\\(D(f(p_i), f(p^+_i)) < D(f(p_i), f(p^-_i))\\) 이면 \\(r(p_i, p^+_i) > r(p_i, p^-_i)\\) 이다.
triplet \\(t_i = (p_i, p_i^+, p_i^-)\\)에 대한 hinge loss는 다음과 같이 정의된다.
\\[l(p_i, p_i^+, p_i^-) = max\{0, g+D(f(p_i), f(p^+_i)) - D(f(p_i), f(p^-_i))\}\\]
hinge loss는 classifier traning에 사용되는 loss function을 말한다.
원래 \\(l(y) = max(0, 1-t\cdot y)\\) 형태로 정의되지만, 여러 variation이 존재하며 multiclass classification에서는 위와 같은 형태로 사용한다.
\\(g\\)는 image pairs 사이의 gap을 regularize하기위한 parameter다.
hinge loss는 0-1 ranking error loss의 convex approximation이고 ( 무슨 말인지... ) 이는 model이 triplet 내의 ranking을 잘못 배열하는지 측정한다. 아무튼 loss function이라는 소리다.
결과적으로 최소화 해야 하는 objective function은 다음과 같다.
\\[min\sum_i \xi_i + \lambda||\boldsymbol W||^2_2 \\ s.t. : max\{0, g+D(f(p_i), f(p^+_i)) - D(f(p_i), f(p^-_i))\} < \xi_i\\]
\\(\boldsymbol W\\)는 당연히 \\(f(.)\\)의 parameter이고 \\(\lambda\\)는 regularization parameter로 보통 0.001정도를 준다. 위 식은 \\(\xi_i = max\{0, g+D(f(p_i), f(p^+_i)) - D(f(p_i), f(p^-_i))\}\\)로 치환하면 unconstrained optimization으로 변환된다.
unconstrained optimization은 변수에 영향을 받는 objective function을 변수 값에 영향을 받지 않는 형태로 minimize하는 것을 말하는 듯. 아무튼 이렇게 optimization된 형태가 결과적으로 최소화 해야 하는 식이다.
4. Network Architecture
전체적인 Architecture는 이렇다.
input은 image triplet이다. triplet을 이루는 세 image는 독립적으로 각각 다른 deep neural network(Q, P, N) \\(f(.)\\)로 들어간다.
각각의 \\(f(.)\\)를 통과하고 나서 Ranking Layer에서 이를 다시 조합해 triplet의 hinge loss를 계산한다. hinge loss에 parameter가 안들어가기 때문에, Ranking Layer의 parameter는 따로 없다. Ranking Layer는 model이 ranking order를 제대로 매겼는지 보고 손실을 계산하여 back-propagation한다.
최소화 해야 하는건 objective function인데 왜 loss function으로 hinge loss를 사용하는거니...
각각의 deep neural network는 이렇게 구성된다. 1:1, 4:1, 8:1로 SubSampling해서 받는다. ( multiscale )
ConvNet에서는 image semantics를 해석하고
아래의 두 부분은 down-sampled image를 받아 visual apperance를 해석한다.
아래 두 부분 중 Convolution layer는 local feature detector다.
max pooling layer는 feature maps가 small translations에 robust하게 만들어준다
local nomalization layer는 illumination(조도) 와 contrast(대비)에 robust하게 만들어준다.
5. Optimization
optimizer로는 SGD랑 momentum을 사용해봤는데 momentum이 더 빠르게 converge했다고 한다. Adam도 써봐야 할 듯.
graident 계산은 당연히 Back-propagation을 사용.
dropout keeping probability는 0.6이며 모든 fully connected layers에 적용. 다른 layer에도 써봐야 할 듯.
dataset augmentation을 위해 input images에 random pixel shift를 사용.
* pixel shift는 tilt나 crop과는 다르다.
5.1 Triplet Sampling
images수가 꽤 된다면 만들 수 있는 triplet 조합이 굉장히 많아지기 때문에 이를 uniformly sampling 하는 것은 비효율적이다.
ranking model의 결과 중 관심있는 것은 top-ranked results이기 때문에 online importance sampling scheme을 사용했다.
uniformly sampling
uniformly와 randomly는 둘 다 랜덤으로 뭘 뽑을 때 쓰는 말이기는 한데 의미하는 바가 약간 다르다.
randomly는 말 그대로 무작위로 뽑는다는 뜻이고, uniformly는 각각의 원소를 동일한 확률로 뽑는 것을 의미한다.
그래서 uniformly and at random. 과 같이 사용한다.
query image
이미지가 query image로 선택될 가능성은 total relevance score에 비례한다.
카테고리 \\(c_i\\)에 속해있는 어떤 이미지 \\(p_i\\)의 total relevance score는 다음과 같다.
\\[r_i = \sum_{j:c_j=c_i, j\ne i} r_{i,j} \\]
즉, 같은 카테고리의 다른 이미지들과의 relevance score를 다 더하면 total relevance score다.
\\(r_{i,j}\\)는 \\(p_j\\)와의 유사도가 클 수록 큰 값을 가지므로, \\(r_i\\)가 크다는건 같은 카테고리 내에 \\(r_i\\)와 유사한 이미지가 많이 있다는 것을 의미한다.
positive image
그 다음 positive image \\(p^+_i\\)를 같은 카테고리 내에서 선택하게 되는데 top-ranked images를 얻어내기 위해서 당연히 \\(r_{i,i^+}\\)가 높은 image를 \\(p^+_i\\)로 선택해야 한다.
이미지 \\(p^+_i\\)가 positive image로 accept 될 확률은 다음과 같다.
그러니까 일단 draw된다고 무조건 선택되는게 아니라 아래 확률로 선택될지 말지를 한번 더 정한다.
\\[P(p^+_i) = \frac {min\{T_p, r_{i,i^+}\}}{Z_i}\\]
\\(T_p\\)는 threshold parameter이고, \\(Z_i\\)는 normalization constant로 카테고리 내의 모든 \\(p^+_i\\)에 대해 \\(Z_i = \sum\limits_{i^+} P(p^+_i)\\) 이다.
negative image
negative image는 out-of-class negative samples와 in-class negative samples로 나뉜다.
out-of-class의 경우 그냥 다른 카테고리에서 uniformly distribution으로 뽑는다. in-class의 경우 top-ranked images를 얻어내기 위해서 positive image와 같은 distribution으로 뽑는다.
margin constraint
\\(r_{i,i^+}\\)와 \\(r_{i,i^-}\\)의 차이가 거의 안나는 경우, 즉 threshold \\(T_r\\)를 넘지 못하는 경우 다시 뽑는다.
\\[r_{i,i^+} - r_{i,i^-} > T_r \tag{margin constraint}\\]
그리고, 실패 횟수가 어떤 threshold를 넘어가면, \\(p^+_i\\)도 다시 뽑는다.
out-of-class의 경우 따로 ratio parameter가 있다. 0.2 정도 주는게 좋다.
online triplet sampling algorithm
sampling하려면 image 목록을 일일히 비교해야 하는데, image를 전부 memory 로드해서 비교하는건 dataset이 너무 커서 불가능하다. 그래서 reservoir sampling 비슷하게 사용한다.
카테고리마다 버퍼를 생성하고 이미지를 뽑은 다음
버퍼가 비어있으면 버퍼에 추가
버퍼가 가득 차 있는 경우 버퍼에 있는 이미지들 중 total relevance score가 가장 작은 이미지와 total relevance score를 비교해서 더 크면 교체하고 작으면 버리는 방식이다.
버퍼에 넣으면서 total relevance score를 비교하게 되므로, 버퍼 내에 있는 이미지들을 uniformly sampling하는 것은 전체 집단에서 total relevance score에 비례한 images를 sampling하는 것과 동일하다.
정리
한 카테고리의 버퍼에서 \\(p_i\\)를 uniformly sampling한다.
그 다음 같은 카테고리 내에서 \\(p^+_i\\)도 uniformly sampling하고, 이를 위에서 설명한 대로 \\(min(1, r_{i,i^+}/r_i^+)\\) 확률로 accept한다.
그 다음 \\(p^-_i\\)를 정해야 하는데, out-of-class일 경우 모든 버퍼에서 uniformly sampling한다.
in-class일 경우 positive image를 정한 것과 동일한 distribution으로 진행한다. 그리고 margin constraint을 거쳐 threshold를 넘지 못하면 negative를 다시 뽑고, 실패 횟수가 일정 이상이 되면 positive도 다시 뽑는다.
6. Experiments
6.1 Training Data
ConvNet의 pre-training에 사용한 dataset은 ImageNet ILSVRC-2012이며, cost function으로는 softmax를 사용.
fine-grained visual similarity 학습에 사용한 training data는 Google image search를 통해 획득.
100000개의 search queries를 사용했으며 각 query 결과 중 top 140 image results만 추려 사용.
서로 다른 search query에 속한 이미지들 간의 \\(r_{i,j} = 0\\)으로 정의.
같은 search query 내의 \\(r_{i,j}\\)를 계산하기 위해 golden feature를 사용.
The
golden feature is a weighted linear combination of twenty seven features. It includes features described in section 6.4, with different parameter settings and distance metrics. More importantly, it also includes features learned through image annotation data, such as features or embeddings developed in
Large scale image annotation. The linear weights are learned through max-margin linear weight learning using human rated data.
그러니까, 여러 Hand-crafted Features를 조합해서 만든게 golden feature라는 소리다.
6.2 Triplet Evaluation Data
evaluation data는 training data와 달리 사람이 직접 필터링해야 정확한 결과를 얻을 수 있다.
우선 1000개의 text query를 사용해 top 50 search results에 대해 triplets (Q, A, B)를 샘플링한다.
그 다음 세 명의 human raters가 샘플링한 triplets에 점수를 매기는 식으로 필터링한다.
human raters는 다음 네 가지 중 하나를 고르게 된다.
- A와 B가 둘 다 Q와 비슷하다.
- A와 B가 둘 다 Q와 비슷하지 않다.
- A가 B보다 더 Q와 비슷하다.
- B가 A보다 더 Q와 비슷하다.
일단 세 명의 human raters가 동일한 선택을 한 triplets만 추린 다음, (1)과 (2)는 버린다.
6.3 Evaluation Metrics
evaluation metric으로는 다음 두 가지 방법을 사용했다.
- Similarity precision
- Score-at-top-K (K = 30)
Similarity precision
올바르게 rank된 triplets의 비율이다.
\\(t_i = (p_i, p_i^+, p_i^-)\\)에 대해 \\(p_i^+\\)가 \\(p_i^-\\)보다 높게 rank되어 있는 경우 올바르게 rank되어 있는 것.
Score-at-top-K
a subset of triplets에 대해 상위 K rank의 triplet 중 올바르게 rank 된 triplet개수 - 틀리게 rank 된 triplet 개수.
a subset of triplets는 test set에 있는 각각의 query image에 대해 같은 text query로 1000개의 이미지를 얻어낸 결과다.
이를 rank 순으로 정렬한다.
만약 \\(p_i^+\\) 또는 \\(p_i^-\\)가 query image \\(p_i\\)의 the top K nearest neighbors이면 그 triplet의 rank는 K보다 높은 것으로 본다.
그러니까 \\(p_i^+\\), \\(p_i^-\\)를 얼마나 \\(p_i\\)와 비슷한 놈으로 잘 뽑았느냐를 평가하는 metric이다.
6.4 Comparison with hand-crafted Features
- 표
DeepRanking's out-of-class ratio parameter = 0.2
7. Conclusion
ConvNet은 semantics만, OASIS는 visual appearance만 잘 잡아내는데 deep ranking은 visual appearance와 semantics 모두 잘 잡아낸다.
어차피 ImageNet같은 이미 분류된 dataset이 없는 경우, 직접 training data를 만들어야 한다.
evaluation data와 달리 training data는 얻은 다음 따로 필터링 하는 작업을 거치지 않기 때문에 좋지 않은 데이터가 섞여 있을 수 있다. 데이터의 질은 데이터를 얻기 위해 사용한 방법에 크게 좌우되는데 이 방법으로는 기존에 사용하던 Hand-crafted Features를 사용할 수 밖에 없다.
어떤 training data를 사용해서 학습했느냐가 NN의 성격에 지대한 영향을 미치므로 결국 NN은 분류 방법으로 사용한 Hand-crafted Features를 따라갈 수 밖에 없는데, 그렇다고 이게 성능이 더 안좋을 거라는 의미는 아니다.
6.4의 결과를 확인해 보면 golden feature나 deep ranking이나 정확도에 별 차이가 없기는 하지만 golden feature는 연산하는 비용이 꽤 많이 들고, 개발하기 성가시다고 한다. 또한 deep ranking은 추가적인 training set을 확보하면 더 개선될 여지가 있다.