Efficient Image Retrieval via Decoupling Diffusion into Online and Offline ProcessingAbstract
이번 포스팅은 diffusion에 관한 논문 번역 및 요약입니다.
번역 상의 오류가 있을 수 있으니 참고하시기 바랍니다.
Efficient Image Retrieval via Decoupling Diffusion into Online and Offline ProcessingAbstract
논문 본문 링크 : https://arxiv.org/abs/1811.10907
Efficient Image Retrieval via Decoupling Diffusion into Online and Offline Processing
Diffusion is commonly used as a ranking or re-ranking method in retrieval tasks to achieve higher retrieval performance, and has attracted lots of attention in recent years. A downside to diffusion is that it performs slowly in comparison to the naive k-NN
arxiv.org
Diffusion은 일반적으로 retrieval 분야에서 높은 성능을 끌어올리기 위한 ranking을 하는 역할로 최근 몇년간 주목을 끌고 있음. 그 이면에는 k-NN보다 느린 수행능력을 가진다는 단점이 있음
이 약점을 이겨내기 위해, 우리는 쿼리에 Diffusion을 적용하는 대신, 온라인 검색을 간단한 선형 결합으로 만들기 위해서 Database의 각 요소의 Diffusion결과를 미리 계산함.
이 방식은 온라인 검색에서 10배 이상 빠른 성능을 보이며, 더 나은 성능을 내기 위해 early truncation 대신 late truncation을 제안 함
Introduction
Convolutional 레이어는 retrieving image에서 가장 뛰어남이 증명이 되었고, Nearest neighbor 검색은 쿼리에서 가장 비슷한 이미지를 찾는 방법으로 사용이 되었다.
Related Works
(추후에 추가 할 예정)
Preliminaries of Diffusion
Diffusion을 수행하는데 있어 아래와 같이 2가지의 주요한 접근이 있음
- 반복적인 업데이트 _iterative update
- 닫힌 방정식을 해결 _solving the close form directly
Problem setup
이미지는 전체 이미지와 일치하는 global feature, 다양한 지역과 일치하는 regional feature로 나타내어 질 수 있음
이미지 검색 분야에서, 데이터베이스는 X, 각각의 x는 feature vector를 의미함
$$\chi = \{ \mathbf{x_1}, \dots, \mathbf{x_n} \} \subset \mathbb{R}^d \qquad (1)$$
쿼리는 Q로 정의함, 이때 m=1이면 쿼리는 gloval feature, m >1 이면 regional feature를 포함한다.
$$\mathcal{Q} = \{ \mathbf{q_1}, \dots, \mathbf{q_m} \} \subset \mathbb{R}^d \qquad (2)$$
Graph construction
하나의 쿼리 이미지만 다루고, 그 이미지는 데이터베이스에 포함된다고 가정함.
전체 셋은 아래와 같이 정의함
$$\bar{\chi} = \{\mathbf{q_1}, \dots, \mathbf{q_m},\mathbf{x_1}, \dots, \mathbf{x_n}\} \qquad (3)$$
Affinity matrix(=Similarity Matrix, 선호도 매트릭스)는 A라고 정의함
$$A = (a_{ij}) \in \mathbb{R}^{(n+m)\times(n+m)} \qquad (4)$$
$$a_{ij} = \begin{cases} s(\bar{\chi_i},\bar{\chi_j}) & \bar{\chi_j} \in \mathbf{NN}_k(\bar{\chi_j}),\bar{\chi_j} \in \mathbf{NN}_k(\bar{\chi_j}), \\ 0 & otherwise \end{cases} \qquad (5)$$
$$\forall i,j \in \{1,\dots,n+m\} \qquad (6)$$
그리고 x의 k-NN값은 NNk(x)으로 표현한다.
similarity metric인 s는 보통 대칭이므로, A는 대칭 매트릭스이다.
degree matrix인 D는 diagonal marix이다. 그리고 그 각각의 요소들의 A의 가로 합과 일치한다.
$$\mathrm{d_{\mathfrak{ii}}} = \sum_{j=1}^{n+m} a_{ij} \qquad (7)$$
대각 행렬인 D 는 후에 대칭 행렬인 A를 마스코프 행렬인 S로 (대칭적인) normalize하기위해 사용됨
$$\mathrm{S} = \mathrm{D^{-1/2}AD^{-1/2}} \qquad (8)$$
$$\mathrm{S} = \mathrm{D^{-1}A} \qquad (9)$$
S(그래프 8)는 전형적인 전이행렬(그래프 9)의 변형. 그리고 둘다 고유 값과 고유 벡터를 가짐.
Random walk
graph contruction이후, 수렴단계에 도달할 때 까지 random walk 작업을 수행하고, 그 결과로 각 이미지에 해당하는 최종 ranking socre가 나옴. t번째 random walk의 스텝에 대해 벡터 f로 기록됨.
$$where \quad \mathbf{f_q^t} \in \mathbb{R}^m, \mathbf{f_d^t} \in \mathbb{R}^n$$
$$\mathbf{f^t} = [ \mathbf{f_q^t}^{\top}, \mathbf{f_d^t}^{\top}]^{\top} \in \mathbb{R}^{n+m} \qquad (10)$$
아래 조건일 경우 초기값을 m-hot벡터로 셋팅.
$$where \quad \mathbf{f_q^0} = 1_m,\quad \mathbf{f_d^0} = 0_n $$
random walk는 아래 스텝을 반복함.
$$\mathbf{f^{t+1}} = \alpha\mathbf{S}\mathbf{f^t} + (1-\alpha)\mathbf{f^0}, \quad \alpha \in (0,1) \qquad (11)$$
여기서 알파는 현재 상태에서 랜덤하게 이동할 개연성. (1 -알파)는 초기값에서 재 시작할 개연성을 의미함. 알파가 0,1 사이라는 사실과 S가 1보다 크지않은 추상적인 고유값이라는 걸 감안할 때, 이 반복은 닫힌 방정식으로 수렴한다.
$$\mathbf{f^*} = (1-\alpha)(\mathbf{I}-\alpha\mathbf{S})^{-1}\mathbf{f}^0 \qquad (12)$$
수렴한후에, f의 값들은 쿼리에 대해 각각 데이터베이스의 유사도를 포함한다. 그리고 그것은 re-ranking을 위한 ranking 스코어로 사용됨
Decomposition
위에서 보여준 단계는 diffusion 과정 중에 쿼리가 graph로 되는 것을 통합한다. Grady는 위 작동에서 쿼리를 분해하는 것을 제안함. 그의 기술은 최근 Iscen에 의해서 뒤이어 오고 있음.
아래 닫힌 방적식을 주목. f는 쿼리와 데이터베이스 요소 둘다의 ranking 점수를 포함함. 그러나 이미지 검색 분야에서는 우리는 오직 데이터베이스의 요소에 대한 점수만을 다룸.
$$\mathbf{f^*} \in \mathbb{R}^{n+m} \qquad (13)$$
이미지 검색분야의 특성으로 인해 필요한 부분만을 찾기 위해 쿼리와 데이터베이스의 ranking 점수의 분해로 이끔. 그에 따라 S 매트릭스를 아래와 같이 4개의 블럭으로 나눔
$$\mathbf{S} = \begin{bmatrix} \mathbf{S_{qq}} \quad \mathbf{S_{qd}} \\ \mathbf{S_{dq}} \quad \mathbf{S_{dd}}\end{bmatrix} \qquad (14)$$
아래 조건일 경우
$$where \quad \mathbf{S_{qq}} \in \mathbb{R}^{m\times m},\ \mathbf{S_{qd}} \in \mathbb{R}^{m\times n}, \\ \mathbf{S_{dq}} \in \mathbb{R}^{n\times m},\ \mathbf{S_{dd}} \in \mathbb{R}^{n\times n}$$
분할되어진 해결법은 아래와 같음.
$$\mathbf{f^*} = (1-\alpha)(\mathbf{I}-\alpha\mathbf{S_{dd}})^{-1}\mathbf{S_{dq}}\mathbf{f_q^0} \in \mathbb{R} \qquad (15)$$
따라서, 아래와 같이 볼 수 있음
정리하자면, Sdq행렬은 쿼리와 그것의 근접이웃들 간의 정규화된 유사성으로 구성되어있음.
$$\mathbf{S_{dd}} = \text{transition matrix for random walk on the database side}$$
$$\mathbf{S_{dq}} = \mathbf{S_{qd}}^{\top} \\ \text{consists of normalized similarities between query and nearest neighbors}$$
결국, 우리는 아래와 같이 깔끔한 형식을 얻게됨
$$\mathbf{f_d^*} \propto \mathcal{L_\alpha^{-1}}\mathrm{y}$$