Y Tech Blog search

GraphSAGE (Inductive Representation Learning on Large Graphs) 설명

|

본 글에서는 2017년에 발표된 Inductive Representation Learning on Large Graphs란 논문에 대한 Review를 진행할 것이다.

torch_geomectric을 이용하여 GraphSAGE를 사용하는 방법에 대해서 간단하게 Github에 올려두었으니 참고해도 좋을 것이다.


Inductive Representation Learning on Large Graphs Paper Review

1. Introduction

큰 Graph에서 Node의 저차원 벡터 임베딩은 다양한 예측 및 Graph 분석 과제를 위한 Feature Input으로 굉장히 유용하다는 것이 증명되어 왔다. Node 임베딩의 기본적인 아이디어는 Node의 Graph 이웃에 대한 고차원적 정보를 Dense한 벡터 임베딩으로 만드는 차원 축소 기법을 사용하는 것이다. 이러한 Node 임베딩은 Downstream 머신러닝 시스템에 적용될 수 있고 Node 분류, 클러스터링, Link 예측 등의 문제에 도움이 될 수 있다.

하지만 이전의 연구들은 고정된 단일 Graph로부터 Node를 임베딩하는 것에 집중하였는데 실제 현실에서는 새로운 Node와 (sub) Graph가 빠르게 생성되는 것이 일반적이다. (Youtube를 생각해보라!) 고정된 Graph에서 추론을 행하는 것을 transductive한 경우라고 부르고 틀에서 벗어나 새로운 Node에 대해서도 합리적인 추론을 행할 수 있는 경우를 inductive라고 부른다. Node 임베딩을 생성하기 위한 inductive한 접근은 또한 같은 형태의 feature가 존재할 때 Graph 전체에 대해 일반화된 결과를 제공하게 된다.

이러한 inductive Node 임베딩 문제는 굉장히 어렵다. 왜냐하면 지금껏 본 적이 없는 Node에 대해 일반화를 하는 것은 이미 알고리즘이 최적화한 Node 임베딩에 대해 새롭게 관측된 subgraph를 맞추는 (align) 작업이 필요하기 때문이다. inductive 프레임워크는 반드시 Node의 Graph 내에서의 지역적인 역할과 글로벌한 위치 모두를 정의할 수 있는 Node의 이웃의 구조적인 특성을 학습해야 한다.

Node 임베딩을 생성하기 위한 대부분의 기존 접근은 본질적으로 transductive하다. 다수의 이러한 접근 방법들은 행렬 분해 기반의 목적함수를 사용하여 각 Node에 대해 임베딩을 직접적으로 최적화하고 관측되지 않은 데이터를 일반화하지 않는다. 왜냐하면 이러한 방법들은 고정된 단일 Graph에 대해 예측하기 때문이다.

이러한 접근법들은 inductive한 방법에서 작동하도록 수정될 수 있는데, 이를 위해서는 굉장한 연산량이 수반되고 새로운 예측이 만들어지기 전에 추가적인 Gradient Descent 단계를 필요로 한다. 최근에는 Graph Convolution 연산을 이용한 방법들이 논의되었다. 지금까지는 Graph Convolutional Network 또한 transductive한 환경에서만 적용되었다. 본 논문에서 우리는 이 GCN을 inductive unsupervised learning으로 확장하고 단순한 합성곱 이상의 학습 가능한 Aggregation 함수를 사용하여 GCN을 일반화하는 프레임워크를 제안할 것이다.

본 논문에서는 Inductive Node Embedding을 위해 일반화된 프레임워크, Graph Sage를 제안한다. 이름은 SAmple과 aggreGatE를 결합하였다. 좀 끼워 맞춘 느낌이 들긴 하다. 행렬 분해에 기반한 임베딩 접근법과 달리 관측되지 않은 Node에서도 일반화할 수 있는 임베딩 함수를 학습하기 위해 Node Feature(텍스트, Node 프로필 정보, Node degree 등)를 Leverage한다. 학습 알고리즘에 Node Feature를 통합함으로써 우리는 이웃한 Node Feature의 분포와 각 Node의 이웃에 대한 위상적인 구조를 동시에 학습할 수 있다. 풍부한 Feature를 가진 Graph에 집중하여 우리의 접근법은 또한 (Node Degree와 같이) 모든 Graph에 존재하는 구조적인 Feature를 활용할 수 있다. 따라서 본 논문의 알고리즘은 Node Feature가 존재하지 않는 Graph에도 적용될 수 있다.

각 Node에 대한 고유의 임베딩 벡터를 학습하는 대신에, 우리는 Node의 지역 이웃으로부터 Feature 정보를 규합하는 Aggregator Function의 집합을 학습한다. 중요한 포인트이다. 왜냐하면 이 컨셉을 통해 각 Node에 귀속된 임베딩 벡터의 한계를 돌파할 수 있기 때문이다.


논문 참조


3. Proposed method: GraphSAGE

우리의 접근법의 가장 중요한 아이디어는 Node의 지역 이웃으로부터 Feature Information을 통합하는 방법에 대해 학습한다는 것이다. 먼저 1.3.1에서는 GraphSAGE 모델의 파라미터가 이미 학습되어 있다고 가정하고 GraphSAGE의 임베딩 생성 알고리즘에 대해 설명할 것이다. 이후 1.3.2에서는 Stochastic Gradient DescentBackpropagation 기술을 통해 모델이 어떻게 학습되는지 설명할 것이다.

3.1. Embedding Generation (i.e. forward propagation) Algorithm

본 섹션에서는 일단 모델의 파라미터가 모드 학습되었고 고정되어 있다고 가정하고 Embedding Generation 혹은 Propgation 알고리즘에 대해 설명할 것이다. 일단 2종류의 파라미터가 있다.

첫 번째는 $K$ 개의 Aggregator Function으로, $AGGREGATE_k, \forall k \in {1, …, K}$ 라고 표현되며, 이 함수는 Node 이웃으로부터 정보를 통합하는 역할을 수행한다.

두 번째는 Weight Matrices의 집합으로, $\mathbf{W}^k, \forall k \in {1, …, K}$ 라고 표현되며, 이들은 모델의 다른 layer나 search depth 사이에서 정보를 전달하는데 사용된다. 다음은 파라미터 학습 과정을 나타낸 것이다.

위에서 확인할 수 있는 직관은 각 iteration 혹은 search depth에서 Node는 그의 지역 이웃으로부터 정보들을 모으고, 이러한 과정이 반복되면서 Node는 Graph의 더 깊은 곳으로부터 정보를 증가시키면서 얻게 된다는 것이다.

알고리즘1은 Graph 구조와 Node Features가 Input으로 주어졌을 때의 임베딩 생성 과정에 대해 기술하고 있다. 아래에서는 Mini-batch 환경에서 어떻게 일반화할 수 있을지 설명할 것이다. 알고리즘1의 바깥 Loop의 각 단계를 살펴보면, $\mathbf{h}^k$ 는 그 단계에서의 Node의 Representation을 의미한다.

첫 번째로, 각 Node $v$ 는 그것의 바로 이웃(Immediate Neighborhood)에 속하는 Node들의 Representation을 하나의 벡터 $\mathbf{h}_{\mathcal{N}(v)}^{k-1}$ 로 합산한다. 이 때 이 합산 단계는 바깥 Loop의 이전 반복 단계(k-1)에서 생성된 Representation에 의존하고 $k=0$ 일 때는 Input Node Feature가 Base Representation의 역할을 하게 된다.

이웃한 Feature 벡터들을 모두 통합한 다음, 모델은 Node의 현재 Representation과 통합된 이웃 벡터를 결합한 뒤 비선형 활성화 함수를 통과시킨다.

[\mathbf{h}v^{k-1}, \mathbf{h}{\mathcal{N}(v)}^{k-1}]

최종적으로 depth $K$ 에 도달하였을 때의 Representation은 아래와 같이 표현할 수 있다.

[\mathbf{z}_v = \mathbf{h}_v^K, \forall v \in \mathcal{V}]

사실 Aggregator Function은 다양하게 변형될 수 있으며, 여러 방법에 대해서는 1.3.3에서 다루도록 하겠다.

알고리즘1을 Mini-batch 환경으로 확장하기 위해서는 우리는 먼저 depth $K$ 까지 필요한 이웃 집합을 추출해야 한다. 이후 안쪽 Loop(알고리즘1의 3번째 줄)를 실행하는데, 이 때 모든 Node를 반복하는 것이 아니라 각 depth에서의 반복(recursion)을 만족하는데 필요한 Represention에 대해서만 계산한다. (Appendix A 참조)

Relation to the Weisfeiler-Lehman Isomorphism Test
GraphSAGE 알고리즘은 개념적으로 Graph Isomorphism(동형 이성)을 테스트하는 고전적일 알고리즘에서 영감을 얻어 만들어졌다. 만약 위에서 확인한 알고리즘1에서 $K= \vert \mathcal{V} \vert$ 로 세팅하고 Weight Matrices를 단위 행렬로 설정하고 비선형적이지 않은 적절한 Hash 함수를 Aggregator로 사용한다면, 알고리즘1은 Naive Vertex Refinement라고 불리는 Weisfeiler-Lehman: WL Isomorphism Test의 Instance라고 생각할 수 있다.

이 테스트는 몇몇 경우에는 들어맞지 않지만, 여러 종류의 Graph에서는 유효하다. GraphSAGE는 Hash 함수를 학습 가능한 신경망 Aggregator로 대체한 WL Test의 연속형 근사에 해당한다. 물론 GraphSAGE는 Graph Isomorphism을 테스트하기 위해서 만들어진 것이 아니라 유용한 Node 표현을 생성하기 위함이다. 그럼에도 불구하고 GraphSAGE와 고전적인 WL Test 사이의 연결성은 Node 이웃들의 위상적인 구조를 학습하기 위한 본 알고리즘의 디자인의 기저에 깔려 있는 이론적 문맥을 이해하는 데에 있어 큰 도움을 준다.

Neighborhood Definition
본 연구에서 우리는 알고리즘1에서 기술한 것처럼 모든 이웃 집합을 사용하지 않고 고정된 크기의 이웃 집합을 샘플링하여 사용하였다. 이렇게 함으로써 각 Batch의 계산량을 동일하게 유지할 수 있었다.

다시 말해, $\mathcal{N}(v)$ 을 집합 ${u \in \mathcal{V}: (u, v) \in \mathcal{E}}$ 에서 각 반복 $k$ 에서 고정된 크기로 균일하게 뽑은 Sample이라고 정의할 수 있다.

이러한 샘플링 과정이 없으며, 각 Batch의 메모리와 실행 시간은 예측하기 힘들며 계산량 또한 엄청나다.

GraphSAGE의 per-batch space와 time complexity는 $O(\prod_{i=1}^K S_i)$ 로 고정되어 있으며, $S_i, i \in {1, …, K}$와 $K$ 는 User-specified 상수이다.

실제 적용할 때, $K=2$ 와 $S_1 * S_2 <= 500$ 으로 했을 때 좋은 성능을 보였다. (자세한 사항은 1.4.4를 참조)

3.2. Learning the Paremeters of GraphSAGE

완전한 비지도 학습 상황에서 유용하고 예측 능력이 있는 Representation을 학습하기 위해 우리는 Graph 기반의 Loss 함수를 $\mathbf{z}_u, \forall u \in \mathcal{V}$ 라는 Output Represnetation에 적용하고, Weight Matrices $\mathbf{W}^k, \forall k \in {1, …, K}$ 및 Stochastic Gradient Descent를 통해 Aggregator Funciton의 파라미터를 튜닝해야 한다.

Graph 기반의 Loss 함수는 인접한 Node들이 유사한 Representation을 갖도록 하게 하고 서로 멀리 떨어져 있는 Node들은 다른 Representation을 갖게 만든다.

[J_{\mathcal{G}} = \log (\sigma (\mathbf{z}u^T \mathbf{z}_v)) - Q \cdot \mathbb{E}{v_n \sim P_n(v)} \log (\sigma (\mathbf{z}u^T \mathbf{z}{v_n}))]

이 때 $v$ 는 고정된 길이의 Random Walk 에서 $u$ 근처에서 동시에 발생한 Node를 의미한다. $P_n$ 은 Negative Sampling Distribution을 $Q$ 는 Negative Sample의 개수를 의미한다.

중요한 것은 이전의 여러 임베딩 방법론에서와는 다르게, Loss 함수에 집어넣는 Representation $\mathbf{z}_u$ 가 Embedding Look-up을 통해 각 Node를 위한 고유의 Embedding을 학습하는 방식으로 형성되지 않는다. Node의 지역 이웃 안에서 포함된 feature로 부터 생성된다. (the representations z are generated from the features contained within a node’s local neighborhood)

이러한 비지도 학습 세팅은 Node Feature가 서비스 혹은 정적인 Repository에 있는 downstream 머신러닝 application에 적용될 때의 상황을 모방하게 된다. 위에서 설명한 Representation이 특정한, 구체적인 downstream task에 이용되어야 할 경우, 앞서 보았던 비지도 Loss는 그 일에 더욱 적합한 (예: cross-entropy loss) 목적함수로 대체되거나 변형될 수 있을 것이다.

3.3. Aggregator Architectures

N차원의 격자 구조 데이터를 이용한 머신러닝 예(텍스트, 이미지 등)들과 달리, Node의 이웃들은 자연적인 어떤 순서를 갖고 있지 않다. 따라서 알고리즘1에서 보았던 Aggregator Function은 반드시 순서가 정해져있지 않은 벡터의 집합에 대해 연산을 수행해야 한다.

이상적으로는 Aggregator Function이 여전히 학습이 가능하고 수준 높은 Representational Capacity를 갖고 있으면서도 대칭적인 형태를 띠고 있으면 좋을 것이다. Input이 순서를 바꿔도 상관 없게 말이다.

Aggregator Funcion의 대칭성은 우리의 신경망 모델이 임의의 순서를 갖고 있는 Node 이웃 feature 집합에도 학습/적용될 수 있게 한다. 본 논문은 이에 대해 3가지 후보를 검증해 보았다.

1) Mean Aggregator
단지 $h_u^{k-1}, \forall u \in \mathcal{N}(v)$ 에 있는 벡터의 원소 평균을 취한 함수이다.

Mean Aggregator는 Transductive GCN 프레임워크에서 사용되는 합성곱 순전파 규칙을 거의 따른다. 특히 우리는 알고리즘의 4~5줄을 다음과 같이 변형하면 GCN의 inductive한 변형 버전을 만들어낼 수 있다.

[h_v^k \leftarrow \sigma ( \mathbf{W} \cdot mean( { h_v^{k-1} } \cup { h_u^{k-1} } ),]

[\forall u \in \mathcal{N}(v)]

우리는 위 식이 Localized Spectral Convolution의 개략적인 선형 근사이기 때문에 이를 수정된 평균 기반 Aggregator Convolutional이라고 부를 것이다. (Modified Mean-based Aggregator Convolutional)

2) LSTM Aggregator
앞서 확인한 형태에 비해 조금 더 복잡한 형태의 함수이다. LSTM의 경우 표현력에 있어서 장점을 지니지만 본질적으로 대칭적이지 않기 때문에 permutation invariant 하지 않다.

따라서 본 논문에서는 LSTM을 Node의 이웃의 Random Permutation에 적용함으로써 순서가 없는 벡터 집합에 대해서도 LSTM이 잘 동작하도록 하였다.

3) Pooling Aggregator
Pooling Aggregator는 대칭적이면서도 학습 가능하다. 각 이웃의 벡터는 독립적으로 fully-connected된 신경망에 투입된다. 이후 이웃 집합에 Elementwise max-pooling 연산이 적용되어 정보를 통합한다.

[AGGREGATE^{pool}k = max({ \sigma (\mathbf{W}{pool} \mathbf{h}_{u_i}^k + \mathbf{b}) })]

[\forall u_i \in \mathcal{N}(v)]

이론 상으로 max-pooling 이전에 여러 겹의 layer를 쌓을 수도 있지만, 본 논문에서는 간단히 1개의 layer 만을 사용하였는데, 이 방법은 효율성 측면에서 더 나은 모습을 보여준다.

계산된 각 피쳐에 대해 max-pooling 연산을 적용함으로써 모델은 이웃 집합의 다른 측면을 효과적으로 잡아내게 된다. 물론 이 때 어떠한 대칭 벡터 함수든지 max 연산자 대신 사용할 수 있다.

본 논문에서는 max-pooling과 mean-pooling 사이에 있어 큰 차이를 발견하지 못하였고 이후 논문에서는 max-pooling을 적용하는 것으로 과정을 통일하였다.


4. Experiments

본 논문에서 GraphSAGE의 성능은 총 3가지의 벤치마크 task에서 평가되었다.

(1) Web of Science citation 데이터셋을 활용하여 학술 논문을 여러 다른 분류하는 것

(2) Reddit에 있는 게시물들이 속한 커뮤니티를 구분하는 것

(3) 다양한 생물학적 Protein-protein interaction 그래프 속에서 protein 함수를 구별하는 것

본 챕터의 경우 논문을 직접 참고하길 바라며, 몇 가지 포인트에 대해서만 정리를 하도록 하겠다.

일단, GraphSAGE의 비교 군으로 총 4가지 방법론이 사용되었다. 완전 무작위, 그래프 구조를 고려하지 않고 raw feature만을 사용한 로지스틱 회귀, DeepWalk 그리고 마지막으로 DeepWalk + raw features, 이렇게 4가지이다.

GraphSAGE도 총 4가지 스타일을 실험하였다. GCN구조, mean aggregator 구조, LSTM aggregator 구조, pooling aggregator 구조 이렇게 4가지이다. vanilla Gradient Descent Optimizer를 사용한 DeepWalk를 제외하고는 모두 Adam Opimizer를 적용하였다. 또한 공평한 비교를 위해 모든 모델은 동일한 미니배치 환경에서 작동하였다.

아래는 테스트 결과이다.

LSTM, Pooling 기반의 Aggregator가 가장 좋은 성능을 보여주었다. K=2로 설정하는 것이 효율성 측면에서 좋은 모습을 보여주었고, 이웃 개체들을 sub-sampling하는 것은 비록 분산을 크게 만들지만 시간을 크게 단축되기 때문에 꼭 필요한 단계라고 할 수 있겠다.


5. Theoretical Analysis

본 Chapter에서는 어떻게 GraphSAGE가 내재적으로는 feature에 의존하면서도 Graph 구조에 대해 학습할 수 있는지에 대해 설명하도록 하겠다.

케이스 스터디의 일환으로, 본 논문에서는 GraphSAGE가 Node의 Clustering Coefficient를 예측할 수 있는지에 대해 알아보았다. Clustering Coefficient는 Node의 지역 이웃들이 얼마나 잘 모여있는지를 측정하는 기준이며 더욱 복잡한 구조적 모티프를위한 토대 역할을 한다.

우리는 GraphSAGE의 임베딩 생성 알고리즘(1.3.1의 알고리즘1)이 Clustering Coefficient를 근사할 수 있음을 증명할 수 있다.

Theorem 1
$x_v$ 가 알고리즘1에서의 feature input을 의미한다고 하자. 모든 Node 쌍에 대해 아래와 같은 조건을 만족하는 고정된 양의 상수 $C$ 가 존재한다고 가정한다.

[C \in \mathbb{R}^+, \Vert x_v - x_{v^{‘}} \Vert_2 > C]

$K = 4$ 반복 후에 알고리즘1에 대한 파라미터 학습이 이루어졌을 때 $\forall \epsilon > 0$ 에 대해 아래 식이 존재한다.

[\vert z_v - c_v \vert < \epsilon, \forall v \in \mathcal{V}]

이 때 $z_v$ 는 알고리즘1에 의해 생성된 최종 아웃풋 벡터, 즉 Embedding 벡터이고 $c_v$ 는 Clustering Coefficient을 의미한다.

위 정리는, 만약 모든 Node의 feature가 고유한 값을 가질 때, Graph 속에서 Clustering Coefficient을 근사할 수 있는 파라미터 세팅이 존재함을 의미한다. 이에 대한 증명은 Appendix에서 확인할 수 있다.

증명의 기본적인 아이디어는, 각 Node가 고유한 feature representation을 갖고 있다면 우리는 Node를 indicator 벡터로 연결시키고 이 Node의 이웃을 찾는 방법에 대해 학습할 수 있다는 것이다. 또한 이 증명을 통해 위 정리는 Pooling Aggregator의 몇몇 특징에 의존적임을 밝혔는데, 이를 통해 Pooling을 이용한 GraphSAGE가 다른 GCN이나 Mean-based Aggregator에 비해 더 좋은 성능을 보여준다는 인사이트를 얻을 수 있다.


6. Conclusion

GraphSAGE는 directed 혹은 multi-model graph를 통합하는 것과 같이 무궁무진한 발전 가능성이 있는 모델이다. 최적화를 위해 Non-uniform Neighborhood Sampling 함수를 연구해보는 것과 같이 굉장히 흥미로운 주제들도 남아있다.


Reference

1) 논문 원본
2) 논문 원본 내 참고 사이트
3) 논문 저자 깃헙

Comment  Read more

Graph Convolutional Matrix Completion (GCMC) 설명

|

본 글은 2017년에 발표된 Graph Convolutional Matrix Completion에 대한 리뷰를 담은 글이다. Graph Neural Network에 대해서는 최근 수 년간 여러 연구가 이루어져 왔으며, 이 방법론은 다양한 분야에서 기존과는 사뭇 다른 새로운 해결 방안에 대해 제시하고 있다.

본 논문은 이러한 Graph 구조의 방법론을 추천 시스템, 그 중에서도 Matrix Factorization에 투영시킨 과정에 대해 설명하고 있다. 비록 적용에 있어 일부 한계점이 존재하기도 하지만, 추가적인 개선이 이루어진다면 여러 추천 시스템에서 참고할만한 중요한 인사이트들을 담고 있다고 할 수 있다. 먼저 논문 리뷰를 진행해보자.


1. Introduction

본 논문에서 우리는 Matrix Completion을 Graph에서의 Link 예측 문제라고 바라보고 있다. Collaborative Filtering에서의 상호작용 데이터는 Link로 표현되는 평점/구매 기록 그리고 User와 Item Node 사이의 Bipartite Graph (이분 그래프)로 표현된다. 컨텐츠 정보는 Node Feature로서 표현될 수 있다. 이제 평점을 예측하는 문제는 이분 User-Item Graph에서 라벨이 존재하는 Link를 예측하는 문제로 귀결된다.

본 논문에서는 Graph에 대한 최근 딥러닝 발전 과정 속에서 설계한, Matrix Completion을 위한 Graph-based Auto-encoder 프레임워크인 Graph Convolutional Matrix Completion: GCMC를 제안한다. 이 때 Auto-encoder는 User와 Item Node의 잠재 벡터를 생성하는데, 이는 이분 상호작용 그래프에서느 Message Passing의 형태로 구현된다. 이 User와 Item (잠재) 표현은 Bilinear Decoder를 통해 평점 Link를 재구성(Reconstruct)하는데 이용된다.

추천 시스템에서 일반적으로 사업자는 특정 User에게 Item Pool에서 이 User에게 잘 어울린다고 생각하는 특정 Item를 골라서 제시하게 된다. 그런데 이러한 논리의 기저에는 유사한 User들은 유사한 Item들을 좋아할 것이라는, 그 User와 Item가 갖고 있는 근본적인 특성의 동질성이 취향에 발현될 것이라는 전제가 깔려있다. 이전의 Matrix Factorization 기반 방법론들은 User/Item Feature의 잠재벡터의 내적 계산을 통해 이러한 철학을 구현하였다.

본 논문에서 제시한 GCMC도 이러한 철학을 계승하고 있다. Graph 구조라고 해서 이 틀을 벗어나지는 않는 것이다. 가장 큰 차이는 바로 위 단락에서 언급한 Message Passing이 될 것인데, 이에 대해서는 추후에 자세히 설명할 것이다.

Matrix Completion 문제를 이분 그래프에서의 Link 예측 문제로 형상화하는 것은 추천 그래프가 구조화된 외부 정보(예: Social Network)를 동반할 때 더욱 빛을 발하게 된다. 이렇게 외부 정보를 추가하는 것은 Cold Start 문제를 완화하는데 도움을 준다.


평점 행렬 $M$ 은 $N_u, N_v$ 의 크기를 가졌고, 행과 열의 수는 각각 User/Item의 수를 의미한다. 평점 행렬의 원소인 $M_{ij}$ 는 관측된 평점 값을 의미하는데, 이 값은 이산적인 (예: 1 ~ 5점) 값이고 미관측된 값은 0으로 처리한다. 최종 목적은 관측되지 않은 값을 예측하는 것이다.

Graph Network의 핵심 중 하나는 이러한 상호작용 데이터를 Undirected Graph (비방향성 그래프)로 표현한다는 것인데, 기호로 나타내자면 아래와 같다.

[G = (\mathcal{W}, \mathcal{E}, \mathcal{R}),]

[\mathcal{W} = \mathcal{U} \cup \mathcal{V},]

[(u_i, r, v_j) \in \mathcal{E},]

[r \in [1, …, R] = \mathcal{R}]

$\mathcal{W}, \mathcal{E}, \mathcal{R}$ 은 차례 대로, User/Item 집합, Edge 집합, Rating 집합을 의미한다. 즉, Graph라는 존재는 이와 같이 Node, Edge, Link로 이루어져 있다는 것을 의미한다.

2.1. Graph Auto-encoders

Graph Auto-encoder는 크게 2가지로 구성된다. 첫 번째는 Graph Encoder 모델로, $Z=f(X, A)$ 라고 정의할 수 있겠다. 이 때 각각의 Shape은 아래와 같다.

행렬 역할 Shape
$Z$ Node Embedding Matrix $N, E$
$X$ 원본 Feature Matrix $N, D$
$A$ Graph Adjacency Matrix $N, N$

$D$ 는 모든 변수의 개수를 의미하며, $N$ 은 $N_u + N_v$ 를 의미한다.

두 번째는 Pairwise Decoder 모델로 $\hat{A} = g(Z) $ 로 정의할 수 있으며 Node Embedding 쌍 $(z_i, z_j)$ 를 Input으로 받아 Adjacency Matrix의 원소인 $\hat{A}_{ij}$ 를 예측하는 역할을 수행하게 된다.

$X$ 는 원본 Feature를 의미하고 이 행렬의 Shape은 $(N=N_u + N_v, D)$ 이다. 한 가지 궁금할 수 있는 부분은 이와 같은 표기에서는 User Feature의 변수의 수와 Item Feature의 변수의 수가 $D$ 로 동일한 것처럼 보이는데, 다음 Chapter를 보면 그렇게 만들 필요는 없다고 설명이 나온다. 처음부터 설명해주는 친절함은 조금 부족했던 것 같다. 어찌 되었든 여기에서의 $D$ 는 편의를 위해 통일 된 것으로 생각하면 좋을 것 같다.

$A$ 는 Adjacency Matrix (인접 행렬)를 의미하는데, 평점 데이터를 기반으로 설명하자면 이 $A$ 는 여러 조각으로 나뉠 수 있다. 즉, 1점의 평점을 준 Link를 모두 모은 인접 행렬을 $M_1$ 이라고 하고, R점의 평점을 준 Link를 모두 모은 인접 행렬을 $M_R$ 이라고 한다면, 우리는 Encoder 모델의 함수를 다음과 같이 달리 표현할 수 있을 것이다.

[Z = f(X, M_1, …, M_R)]

$Z$ 는 $[U, V]$ 로 표현되는데, User Embedding Matrix와 Item Embedding Matrix를 쌓아놓은 형태이다.

최종적으로 해결해야 하는 문제는 예상하는 그대로이다. Decoder $g(U, V)$ 는 $\hat{M}$ 이라는 평점에 대한 예측 값을 생성하게 되고, 이 행렬의 Shape은 당연히 기존 $M$ 과 동일한 $(N_u, N_v)$ 이다.

예측 행렬 $\hat{M}$ 과 관측된 Ground-Truth 행렬 $M$ 사이의 Reconstruction Error 를 줄이는 것이 본 모델의 목적이다.

2.2. Graph Convolutional Encoder

지금부터는 조금 더 진보된 형태의 Encoder 모델을 소개할 것이다. 이 모델은 Graph에서 location에 대한 효율적인 Weight Sharing을 특징으로 한다. 또한 이 모델은 각 평점 종류(Edge Type)에 대해 별도의 Processing Channel을 만든다. 즉 각각의 평점 종류(1점인지, 2점인지)에 따라 (형식은 같지만) 다른 처리 과정이 존재한다는 것이다.

Weight Sharing의 형식은 Graph 구조의 데이터에 직접적으로 작동하는 최근 CNN class에 영감을 받았는데, Graph Convolutional Layer가 Node의 1차 이웃만을 고려하여 지역 연산을 수행하면, 같은 Transformation이 Graph에 있는 모든 위치에서 수행된다는 것이다.

Graph 구조의 모델에 대해 처음 설명을 듣는다면 위 단락이 잘 이해가 되지 않을 수도 있다. 잠시 그림을 살펴보자.

User 1이 존재한다. 이 User는 총 3개의 Item에 대해 평점을 남겼는데, 이렇게 User 1이 평점을 남긴 Item을 우리는 1차 이웃이라고 부른다. 즉 User 1과 직접적인 관계를 맺고 있는 Node라고 할 수 있다. 그렇다면 2차 이웃은 무엇일까? User 1이 평점을 남긴 1차 이웃 Item이 직접적인 관계를 맺고 있는 User 집합이라고 할 수 있는데, 이들은 그림 상에서 초록색 원형으로 표시되었다. 3차 이웃은 이제 감이 올 것이다. 2차 이웃 User가 직접적으로 관계를 맺고 있는 Item 집합을 의미한다. 이렇게 차수를 높여감에 따라 우리가 알고 싶은 User 1의 관계의 깊이가 점점 깊어진다는 것을 알 수 있다. 더 깊게 알고 싶을 수록 연산량이 늘어나는 것은 당연한 숙제가 될 것이다.

그렇다면 하나 더, 위 그림에서 추론할 수 있는 것은 무엇일까? 간단하게 말해서 User 1은 파란색 상자로 표현한 Item 1, 2, 4 중에서 Item 1과 2에 대해서는 아주 좋은 평점을 남기지는 않았는데, User 2도 이와 유사한 평점을 남겼다. 그렇다면, 오직 이 Graph만 보았을 때는 User 1과 User 2가 나름 취향이 비슷할 수도 있을 것이다. 이 때 평점이 몇 점인지도 중요하지만 어떤 Item에 대해 평점을 남겼는지도 중요하다. 그 User의 행동 반경을 정의하는 단서가 되기 때문이다. 반대로 User 3은 User 1이 좋아했던 Item 4에 대해 안 좋은 평점을 남겼다. 어쩌면 이 두 User는 상극일지도 모른다.

다시 논문으로 돌아오겠다.

Local Graph Convolution은 Vector 값으로 만들어진 Message가 Graph의 모든 Edge를 타고 전달 및 변형되는 일종의 Message Passing의 형태로 볼 수 있다. 본 논문에서는 각 평점에 따라 별도의 Transformation을 행했다. Item j가 User i에게 주는 Edge-type Specific Message는 아래와 같은 형식으로 표현할 수 있다.

[\mu_{j \rightarrow i, r} = \frac {1} {c_{ij}} W_r x_j]

여기서 $c_{ij}$ 는 정규화 상수인데, 만드는 방법에는 2가지가 있다. Left Normalization을 택할 경우, $\vert{\mathcal{N}_i}\vert$ 을, Symmetric Normaliztion을 선택할 경우 $\vert{\mathcal{N}_i}\vert \vert \mathcal{N_j} \vert$ 로 택할 수 있다.

$\mathcal{N_i}$ 는 Node $i$ 의 이웃들의 집합을 의미한다. 따라서 위 기호는 그 이웃 집합의 길이를 의미하게 될 것이다. $W_r$ 은 Edge-type Specific Parameter를 의미한다. 참고로 뒤에 나올 $W$ 행렬과는 별개의 것이다. 논문에서 다소 혼란스럽게 적어 놓았으니 구별하길 바란다. $x_j$ 는 Node $j$ 의 (Initial) Feature 벡터를 의미한다. 이 예시에서는 Node $j$ 가 Item 이지만, 반대의 경우도 당연히 성립한다.

이렇게 $r$ 이라는 평점에서 Node $j$ 에서 Node $i$ 로 향하는 Message Passing을 정의하는 단계가 끝나면, 이제 $r$ 이라는 평점 하의 모든 이웃 $\mathcal{N_{i, r}}$ 의 입수되는 모든 Message를 규합해야 한다. 그렇게 합쳐서 아래와 같이 하나의 벡터 표현을 만들게 된다. 아래 벡터를 반드는 층을 Graph Convolution Layer라고 명명하겠다.

[h_i = \sigma [accum (\Sigma_{j \in \mathcal{N_{i, 1}}} \mu_{j \rightarrow i, 1}, …, \Sigma_{j \in \mathcal{N_{i, R}}} \mu_{j \rightarrow i, R}) ]]

평점의 종류가 총 $R$ 개라고 할 때 위 식은 모든 평점의 종류에 대해 Node $i$ 의 1차 이웃에 속하는 Item Node $j$ 들에 대해 모든 Message를 합치는 과정으로 설명할 수 있다. 합친다는 것을 의미하는 $accum$은 Stacking으로 생각할 수도 있고, Sum으로 생각할 수도 있는데, Sum이 좀 더 구현하기 편리하니 Sum으로 일단 생각해두자.

이제 최종적으로 Node $i$ 의 Embedding Vector를 생성하면 된다. 아래와 같이 만들 수 있다. 최종 Embedding Vector를 생성하는 아래 층은 Dense Layer라고 명명하겠다.

[u_i = \sigma(W h_i)]

Item Embedding Vector $v_j$ 역시 같은 Paramter 행렬 $W$ 에 의해 유사한 방식으로 생성된다. 만약 User, Item에 대한 Side Information, 즉 별개의 Feature Vector를 사용할 경우 이 Parameter 행렬 $W$ 는 User, Item에 따라 별도로 구성해야 할 것이다. ( $W_{user}, W_{item}$ )

여러 층을 추가하여 더욱 깊은 모델을 만들 수도 있고, Message Passing 구성을 위와 같이 하는 대신 새로운 신경망이나 Attention 모델을 통해 구성하는 방안도 생각해볼 수 있다. 그러나 본 논문에 따르면 위와 같이 구성하는 방법이 가장 효율적인 것으로 나타났다.

논문에서는 이렇게 소 Chapter를 마무리하는데, 보충 설명을 하도록 하겠다.

Message Passing 단위는 $\mu_{j \rightarrow i, r}$ 라는 벡터이다. 예시를 들어보자. 만약 평점이 1점, 2점 이렇게 2종류만 존재한다고 해보자. 그리고 User Node $i$ 가 1점을 준 Item Node는 $1, 2$ 이렇게 2가지가 있고, 2점을 준 Item Node는 $3$ 이렇게 1가지만 존재한다고 해보자.

그렇다면 User Node $i$ 의 이웃은 아래와 같이 구성할 수 있다.

위 그림과 같은 구조에서 우리는 다음과 같은 Message Passing 벡터를 얻을 수 있다.

[\mu_{1 \rightarrow i, 1}, \mu_{2 \rightarrow i, 1}, \mu_{3 \rightarrow i, 2}]

위 벡터들의 의미는 무엇일까? 위 3개의 벡터 중 첫 번째를 예시로 들어보자. $1$ 이라는 Item Node가 User $i$ 에게 미치는 영향으로 해석가능하다. 이 때 어떻게 영향을 미칠 것인가에 대해서는 $W_1$ Parameter 행렬이 역할을 수행하게 될 것이다. 그런데 User $i$ 에게 1점의 관계를 맺고 있는 Item Node는 총 2개이다. 따라서 앞서 보았던 $c_{ij}$라는 정규화 상수를 통해 영향의 크기를 분산시켜주는 것이다.

이렇게 만들어진 단위 벡터들은 Graph Convolution Layer에서 합쳐지고 최종적으로 User, Item Embedding Vector을 형성하게 된다.

2.3. Bilinear Decoder

행렬 분해를 기반으로 하는 추천 시스템에 대해 한 번이라고 공부를 해보았다면, 이전 Chapter에서 언급한 임베딩 벡터의 의미를 알아챘을 것이다. 가장 Classic하게 평점을 예측하는 방법은 User 임베딩 벡터와 Item 임베딩 벡터를 바로 내적 계산하는 것이다.

[\hat{y}_{ij} = u_i \cdot v_j]

본 논문에서는 이러한 역할을 수행하기 위해 Bilinear Decoder라는 형태를 제안한다. 이 때 각 평점 종류 마다 다른 Parameter Update를 수행한다는 점에 주의하기 바란다. ( $Q_1, Q_2, …, Q_R$ )

$M$ 평점 행렬의 한 원소를 예측하는 과정은 아래와 같이 Softmax 함수에 의해 Bilinear 연산을 가능한 평점 종류에 대해 수행하고 이에 대한 확률 분포를 생성하는 방식으로 이루어진다.

[p(\hat{M}{ij}) = \frac {e^{u_i^T Q_r v_j}} {\Sigma{s \in R} e^{u_i^T Q_s v_j}}]

여기서 $Q_r$ 은 학습 가능한 Parameter 행렬로, $(E, E)$ 의 Shape을 지녔다. 물론 여기서 $E$ 는 Embedding 차원을 의미한다. 최종적으로 평점 예측은 아래 식으로 계산된다.

[\hat{M}{ij} = g(u_i, v_j) = \mathbf{E}{p(\hat{M}{ij = r}} [r] = \Sigma{r \in R} r * p(\hat{M}_{ij})]

식을 보면 평점의 종류에 따라 확률이 가중 평균됨을 알 수 있다.

2.4. Model Training

논문의 흥미로운 내용만큼이나 학습시키는 것은 상당히 까다롭다. 어떻게 진행되는지 알아보자.

Loss Function은 다음과 같은 Negative Log Likelihood로 설정된다.

[\mathcal{L} = \Sigma_{i, j; \Omega_{i,j} = 1} \Sigma_{r=1}^R I[r=M_{ij}] logp(\hat{M_{ij}} = r)]

여기서 $I$ 함수는 Indicator Function으로 $[]$ 안이 참일 때 1, 그렇지 않을 때 0의 값을 가지게 된다. 이는 일종의 Mask 역할을 수항하게 되는데, 왜냐하면 오직 평점 기록이 존재하는 Link에 대해서만 Loss를 계산한다는 의미가 되기 대문이다.

Node Dropout
관측되지 않은 평점에 대해 모델이 잘 일반화하기 위해서는 또다른 장치가 필요하다. 특정 Node에 대해 $p_{dropout}$ 확률로 밖으로 나가는 모든 Message를 무작위로 drop out하는 방식으로 학습하는 것을 Node Dropout이라고 한다.

Message는 Dropout 단계 이후에 Rescaled된다. Node Dropout을 적용한 결과 임베딩 결과물이 특정 User나 Item에 좀 더 독립적이 된 것을 확인할 수 있었다. 추가적으로 Hidden Layer Unit에 Regular Dropout 역시 적용하였다.

Mini-batching
미니 배치는 User-Item Pair 총합에서 오직 고정된 수의 Contribution 만을 추출하여 학습에 사용한다는 것을 의미한다. 이렇게 함으로써 현재 Batch에서 존재하지 않는, 각 평점 Class의 User/Item 행을 제거할 수 있다.

이러한 과정은 또한 효율적인 정규화의 수단으로 기능하며 모델을 학습시키기 위해 필요한 메모리 역시 경감시키는 효과를 발휘한다.

2.5. Vector Implementation

실제로 코드를 구현하여 모델을 학습할 때, 지금까지 설명한 것처럼 일일히 벡터를 하나씩 구하는 것은 정말 어리석은 행위일 것이다. 간단히 (사실 간단하지 않다) 행렬을 활용하여 수많은 연산을 좀 더 효율적으로 수행해보자.

User Feature와 Item Feature의 수가 $D$ 로 같다고 가정해보자. 이 때 Embedding 행렬은 아래와 같이 구할 수 있다.

[\begin{bmatrix} U \ V \end{bmatrix} = f(X, M_1, …, M_R) = \sigma( \begin{bmatrix} H_u \ H_v \end{bmatrix} W^T )]

[with \begin{bmatrix} H_u \ H_v \end{bmatrix} = \sigma(\Sigma_{r=1}^R D^{-1} \mathcal{M}_r X W_r^T),]

[\mathcal{M}_r = \begin{bmatrix} 0 M_r \ M_r^T 0 \end{bmatrix}]

이 때 $D$ 는 대각행렬이며, 대각원소 $D_{ii} = \vert \mathcal{N}_i \vert$ 을 의미한다.

각 행렬의 크기는 아래와 같다.

행렬 역할 Shape
$\begin{bmatrix} U \ V \ \end{bmatrix}$ Node Embedding Matrix $N+M, E$
$\begin{bmatrix} H_u \ H_v \ \end{bmatrix}$ Hidden Matrix $N+M, E$
$W^T$ Weight Matrix $E, E$
$D^{-1}$ Normalization Matrix $N+M, N+M$
$A$ Graph Adjacency Matrix $N+M, N+M$
$X$ Feature Matrix $N+M, D$
$W_r^T$ Edge-type Specific Weight Matrix $D, E$

위와 같이 Encoder에서 벡터화한 방식을 그대로 Decoder에 적용하면 된다. 그리고 이러한 방식은 오직 관측된 원소를 평가할 때만 필요할 것이다.

2.6. Input Feature Representation and Side Information

컨텐츠 정보와 같이 각 Node에 대한 정보를 담고 있는 Feature는 Feature Matrix $X$ 라는 형태로 Input 레벨에서부터 투입될 수 있다. 그러나 만약 그러한 정보가 다른 User(Item)나 그들의 관심 사항을 제대로 구분할만한 충분한 정보를 갖고 있지 못하다면, 이 정보를 처음부터 Graph Convolutional Layer에 집어 넣으면 심각한 정보 병목현상이 발생할 수도 있다.

이러한 경우에는 Side Information으로 활용하는 방안을 생각해볼 수 있다. Node $i$ 에 대해 User/Item Feature Vector $x_i^f$ 를 만들고, 이를 Dense Hidden Layer에 독립적인 채널을 통해 직접적으로 투입하는 것이다.

[u_i = \sigma(W h_i + W_2^f f_i),]

[f_i = \sigma(W_1^f x_i^f + b)]

이 때 $W_1^f, W_2^f$ 는 학습 가능한 Weight 행렬이며, User Weight Matrix와 Item Weight Matrix는 구분된다. Graph Convolutional Layer를 위한 Node Feature를 담고 있는 Input Feature Matrix $X$ 는 Graph에 있는 모든 Node에 대한 고유한 One-Hot 벡터와 함께 Identity Matrix로 선택된다. 본 논문에서 사용된 데이터셋에 한해서는, User/Item Content 정보는 제한적인 크기를 갖고 있고 따라서 본 논문에서는 이들을 Side Information으로 이용하고자 한다.

Side Information은 꼭 Per-Node Feature 벡터의 형태일 필요는 없다. 사실 그래프 구조여도 되고, NLP 혹은 이미지 데이터일수도 있다. 물론 이 경우 위에서 보았던 식은 미분 가능한 적절한 다른 모듈로 대체되어야 할 것이다. RNN, CNN, GNN 같은 형태로 말이다.

논문에서의 이 부분은 기술적으로 다루기가 좀 어려운 부분이 있을 수는 있지만, 적절히 설계된다면 GCMC의 확장성에 관한 기술로 생각해볼 수 있으며 우리에게 주어진 Task에 유연하게 적용해볼 수도 있을 것이다.

2.7. Weight Sharing

One-Hot 벡터가 Input으로 주어지는 Collaborative Filtering 환경에서, Weight 행렬 $W_r$ 의 열은 특정 평점 값 $r$ 에 대해 독립적인 Node의 잠재 요인으로서의 역할을 갖게 된다. 참고로 $W_r$ 의 Shape은 $(E, D)$ 인데, 논문에서 말한 의 의미를 생각해보면 Weight 행렬을 $W_r^T$ 로 전치하여 $(D, E)$ 의 Shape을 갖고 있다고 생각하고 바라보는 것이 좀 더 편할 것이다.

어쨌든 이 잠재 변수들은 Message Passing이라는 형태를 통해 연결된 User/Item Node로 전달된다. 그러나 모든 User와 Item이 각 평점 레벨에서 갖은 수의 평점을 갖고 있지는 않을 것이다. 이 말은, $W_r$의 특정 열은 다른 열들에 비해 상대적으로 덜 최적화되는 결과를 야기할 수도 있다는 것이다.

따라서 이러한 최적화 문제를 해결하기 위해 다른 평점 class $r$ 에 대해 $W_r$ 에 대한 어떤 형태의 Weight Sharing이 필요하다. 다음과 같은 식을 보자.

[W_r = \Sigma_{s=1}^r T_s]

본 논문에서는 위와 같은 방식의 Weight SharingOrdinal Weight Sharing이라고 명명한다. 왜냐하면 높은 평점 레벨에는 더 많은 Weight 행렬이 들어가기 때문이다.

[W_1 = T_1]

[W_2 = T_1 + T_2]

[W_3 = T_1 + T_2 + T_3]

Pairwise Bilinear Decoder의 효과적인 정규화 수단으로 Basis Weight 행렬 $P_s$ 의 집합의 선형 결합의 형태로 Weight Sharing을 정의할 수 있겠다.

[Q_r = \Sigma_{s=1}^{n_b} a_{rs} P_s]

이 때 $n_b$ 는 기본 Basis Weight 행렬의 개수를 의미한다. $a_{rs}$ 는 학습 가능한 계수로, 각 Decoder Weight 행렬 $Q_r$ 의 선형 결합을 결정한다. 과적합을 피하고 파라미터의 수를 줄이기 위해 $n_b$ 는 평점 Class의 수보다는 작아야 할 것이다.

(중략)


5. Conclusions

Encoder는 Graph Convolutional Layer를 포함하는데, 이 layer는 User-Item 상호작용 Graph에서 오가는 Message 속에서 User/Item Embedding을 구성하게 된다. Bilinear Decoder와 결합하여 새 평점은 labeled edge의 형태로 예측되게 된다.

본 논문에서 제안한 모델은 여러 Benchmark 모델을 능가하는 결과를 보여주었다. 또한 본 논문에서는 확률적 미니배치를 통해 더 큰 데이터셋에서 학습될 수 있다는 것을 보여준다.

미래에 이 모델을 더욱 크고 Multi-modal 형태의 데이터 (Text, Image, Graph-based Information으로 구성된)에도 적용할 수 있기를 바란다. 이러한 세팅에서는 GCMC 모델은 Recurrent 또는 Convolutional Neural Network와 결합하여 사용될 수 있을 것이다.

더욱 확장하기 위해서는 효율적인 근사 방법이 필요한데, 예를 들어 Local Neighborhood를 Sub-sampling하는 방법이 그 예가 될 수 있을 것이다. 이 방법에 대해서는 Inductive Representation Learning on Large Graphs라는 논문을 참고하길 바란다. 이 논문에 대한 리뷰는 곧 블로그에 업데이트될 것이다.

마지막으로 Attention Mechanism은 이러한 종류의 모델의 성능을 더욱 향상시키는 방법이 될 수 있을 것이다.


Reference

1) 논문 원본
2) 리뷰 블로그

Comment  Read more

KnowIT VQA - Answering Knowledge-Based Questions about Videos(KnowIT VQA 논문 설명)

|

이 글에서는 KnowIT VQA: Answering Knowledge-Based Questions about Videos에 대해 알아보고자 한다.

VQA task는 이미지(Visual, 영상으로도 확장 가능)와 그 이미지에 대한 질문(Question)이 주어졌을 때, 해당 질문에 맞는 올바른 답변(Answer)을 만들어내는 task이다.

KnowIT VQA는 VQA 중에서도 Video를 다루는 QA이며, 전통적인 VQA와는 달리 이미지 등 시각자료에서 주어지는 정보뿐만 아니라 외부 지식(상식 베이스, Knowledge Base)이 있어야만 문제를 풀 수 있는 질의들로 이루어진 새로운 task이다.

KnowIT VQA 홈페이지는 https://knowit-vqa.github.io/ 이다.
데이터셋 중 Annotation도 같은 링크에서 다운받을 수 있다.

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


KnowIT VQA: Answering Knowledge-Based Questions about Videos

논문 링크: KnowIT VQA: Answering Knowledge-Based Questions about Videos

초록(Abstract)

지식기반 그리고 Video QA를 결합한 새로운 영상이해(video understanding) task를 제안한다. 먼저, 유명한 시트콤(참고: 빅뱅이론이다)에 대해 24,282개의 사람이 만든 질답 쌍을 포함하는 video dataset인 KnowIT VQA를 소개한다. 데이터셋은 시각적, 텍스트, 시간적 일관성 추론을 지식기반 질문과 결합하여 이는 시리즈를 봄으로써 얻을 수 있는 경험을 필요로 한다. 그리고 시트콤에 대한 세부적인 지식과 함께 시각적, 텍스트 비디오 자료를 모두 사용하는 영상이해 모델을 제안한다. 이 논문의 주된 결과는 1) (외부) 지식의 결합이 Video QA에 대한 성능을 크게 높여주는 것과 2) KnowIT VQA에 대한 성능은 사람의 정확도에 비해 많이 낮다는 것(현 video 모델링의 한계에 대한 연구의 유용성을 내포함)이다.


서론(Introduction)

VQA는 자연어와 이미지 이해를 함께 평가하는 중요한 task로 지난 몇 년간 많은 종류의 VQA가 제안되고 연구되어왔다. 특히 초기 연구와 그 모델들은 주로 이미지의 내용에만 집중하는 형태를 보여 왔다(질문의 예: 안경을 쓴 사람이 몇 명이나 있는가?).

단지 이미지-이미지에 대한 질문을 묻는 것은 한계가 명확했다.

  1. 이미지의 features는 오직 이미지의 정적인 정보만을 잡아낼 뿐 video에 대한 시간적인 일관성이나 연관성은 전혀 고려하지 않았다(예: 그들은 어떻게 대화를 끝내는가?).
  2. 시각 자료(이미지나 영상)는 그 자체로는 외부 지식을 필요로 하는 질문에 대답하는 충분한 정보를 포함하지 않는다.

이러한 한계를 해결하기 위해 단순 이미지와 질문만을 사용하는 Visual QA에서 1) 영상을 사용하는 VideoQA, 2) 외부 지식을 활용하는 KBVQA 등이 등장하였다. 하지만, 여러 종류의 질문을 다루는 일반적인 framework는 여전히 나오지 않았다.

이 논문의 기여하는 바는 여기서부터 출발한다. 영상에 대한 이해와, 외부 지식에 기반한 추론을 모두 활용하는 방법을 제안한다.

  1. 영상을 활용하기 위해 유명 시트콤인 빅뱅이론에다 annotation을 더하여 KnowIT VQA dataset을 만들었다. 질문들은 시트콤에 익숙한 사람만이 대답할 수 있는 수준으로 만들어졌다.
  2. 특정 지식을 continuous representation으로 연결하여 각 질문에 내재된 의도를 추론하는 모듈과 얻어진 지식을 영상 및 텍스트 내용과 결합하여 추론하는 multi-modal 모델을 제안한다.
KnowIT VQA

관련 연구(Related Work)

  • Video Question Answering은 행동인식, 줄거리 이해, 시간적 연관성을 추론하는 등의 시간적 정보를 해석하는 문제들을 다뤄 왔다. 영상의 출처에 따라 시각자료는 자막이나 대본 등 텍스트 자료와 연관되어 해석을 위한 추가 수준의 문맥을 제공한다. 대부분의 연구는 영상이나 텍스트 자체의 정보를 추출할 뿐 두 modality의 결합은 제대로 활용하지 않았다. MovieFIB, TGIF-QA, MarioVQA는 행동인식, Video Context QA는 시간적 일관성을 다룬다.
    • 오직 몇 개의 데이터셋, PororoQA와 TVQA만이 multi-model video representation을 함께 해석하는 benchmark를 제안하였다. 하지만 영상자료를 넘어서는 추가 지식에 대한 고려는 이루어지지 않았다.
  • Knowledge-Based Visual Question Answering: 시각자료와 텍스트만 가지고서는 그 자체에 내재된 정보 외에 추가 지식은 전혀 쓸 수가 없다. 그래서 외부 지식을 포함하는 VQA가 여럿 제안되었다. KBVQA(Knowledge-based VQA)는 외부 지식을 활용하는 대표 VQA 중 하나이다. 이는 지식을 포함하는 데이터셋이지만 초기 단계에 머물러 있다.
    • 그 중 일부 dataset은 질문의 형태가 단순하거나 외부 지식이 정해진 형태로만 제공되었다. KB-VQA는 template에서 만들어진 질문-이미지 쌍을 활용했으며, R-VQA는 각 질문에 대한 relational facts만을 사용했다. FVQA는 entity 식별, OK-VQA는 자유형식의 질문을 사용하였으나 지식에 대한 annotation이 없었다.
    • KnowIT-VQA는 영상을 활용하며, 지식을 특정 데이터에서 직접 추출한 것이 아닌 일반지식을 가져왔기에 이러한 단점들을 해결하였다고 한다.

KnowIT VQA 데이터셋(KnowIT VQA Dataset)

TV Show는 인물, 장면, 줄거리의 일반적인 내용들을 사전에 알 수 있기에 영상이해 task에서 현실 시나리오를 모델링하는 좋은 과제로 여겨진다. 그래서 이 논문에서는 유명 시트콤인 빅뱅이론을 선정하여 KnowIT VQA dataset으로 만들었고, 이는 영상과 show에 대한 지식기반 질답을 포함한다.

Video Collection

영상은 빅뱅이론 TV show에서 가져왔으며, 이는 각 20분 정도의 207개의 episode들로 구성된다. 텍스트 데이터는 DVD에 있는 자막(대본)을 그대로 가져왔다. 각각의 대사는 시간과 화자(speaker)의 순서에 맞게 주석을 달았다. 영상은 scene으로 나누어지며 이는 또 20초 정도의 clip으로 분리되어, 총 12,264개의 clip이 있다.

QA Collection

Amazon Mechanical Turk (AMT)를 사용하였으며 빅뱅이론에 대해 깊은 이해도를 갖는 사람들로 하여금 질답을 생성하도록 했다. 목표는 show에 친숙한 사람들만이 질문에 대답할 수 있도록 하는 질문(그리고 답)을 만드는 것이었다. 각 clip에 대해, 영상과 자막을 각 episode의 대본과 요약과 연결시키도록 했다. 각 clip은 질문, 정답, 3개의 오답과 연관된다.

Knowledge Annotations

여기서 “knowledge”(지식)이란 주어진 영상 clip에 직접 포함되지 않는 정보를 가리킨다. 질답 쌍은 추가 정보로 annotated되어:

  • Knowledge: 짧은 문장으로 표현되는 질문에 대답하기 위해 필요한 정보.
    • 질문: 왜 Leonard는 Penny를 점심에 초대했는가?
    • Knowledge: Penny는 이제 막 이사를 왔다.
    • 정답: 그는 Penny가 빌딩에서 환영받는다고 느끼기를 원했다.
  • Knowledge Type: Knowledge가 특정 episode에서 왔는지, 아니면 show의 많은 부분에서 반복되는지(recurrent)를 말한다. 6.08%의 Knowledge만이 반복되며 나머지 9개의 season에 속하는 Knowledge는 거의 균등하다. 분포와 Knowledge의 예시를 아래 그림에서 볼 수 있다.
KnowIT VQA
  • Question Type: 범용 모델의 개발을 장려하기 위해 test set에서만 제공되며, 4가지 종류로 구분된다:
    • visual-based(22%): video frame 안에서 답을 찾을 수 있다.
    • textual-based(12%): 자막에서 답을 찾을 수 있다.
    • temporal-based(4%): 현재 video clip의 특정 시간에서 답을 예측 가능하다.
    • knowledge-based(62%): clip만으로는 답을 찾을 수 없다(외부 지식이 필요하다).
KnowIT VQA

Data Splits

12,087개의 video clip으로부터 24,282개의 sample을 추출하였으며 train/val/test set으로 구분되었다. 일반적인 QA dataset처럼 정답은 오답보다 살짝 더 길이가 긴 편향이 존재한다.

KnowIT VQA

Dataset Comparison

KnowIT VQA 데이터셋과 다른 데이터셋을 비교한 표를 아래에서 볼 수 있다:

KnowIT VQA
  • QA 생성이 더 까다롭기 때문에 KBVQA의 크기가 작다.
  • KnowIT VQA는 질문의 수가 24k개로 2.4k의 KB-VQA, 5.8k의 FVQA, 14k의 OK-VQA에 비해 훨씬 많다.
  • TVQA와 영상이 일부 겹치지만 KnowIT VQA는 더 많은 clip을 사용하였다.

인간 평가(Human Evaluation)

다음의 목적에 따라 평가를 진행하였다:

  1. video clip이 질문에 답하는 것과 연관이 있는지
  2. 질문이 답변하는데 Knowledge를 실제로 필요로 하는지
  3. Knowledge가 답변하는 데 정말로 도움이 되는지
  4. 모델 비교를 위한 human performance baseline을 설정하기 위해

Evaluation Design

AMT를 사용하였고, worker를 1) 9개의 시즌 전부를 적어도 한 번은 본 masters 그룹과 2) 빅뱅이론을 조금도 본 적 없는 rookies로 구분하였다. 질문에 대한 평가와 knowledge에 대한 평가를 중심으로 진행하였다.


Evaluation on the questions

위의 두 그룹은 각각 Blind(질답만 제공), Subs(질답과 자막 제공), Video(질답, 자막, 영상 clip 제공)으로 구분되었다. worker들은 4지선다형 중 맞는 답과 그 답을 선택한 이유를 6지선다형으로 풀게 하였다.

  • SubsVideo 그룹의 차이는 video의 영향을 보여준다.
  • mastersrookies 그룹의 차이는 knowledge의 중요성을 보여주며 KnowIT VQA는 show를 보지 않았을 때 굉장히 어려운 task임을 보여준다.

Evaluation on the knowledge

모아진 Knowledge의 품질과 질문 간 연관성을 분석하였다. rookies들에게 test set의 질문에 대답하도록 하였다. 각 질문과 선택지에 대해 자막과 video clip이 제공되었다. 답을 한 후에는 연관된 Knowledge를 보여주고 다시 답변하도록 하였다. 결과적으로 Knowledge가 주어지기 전후로 정확도는 0.683에서 0.823으로 증가하였다. 이는 답변을 하는 데 있어 Knowledge의 연관성(그리고 그 중요성)을 보여 준다.

KnowIT VQA

ROCK Model

ROCK (Retrieval Over Collected Knowledge) 모델의 구조는 다음과 같다.

KnowIT VQA
  • Knowledge Base(KB)에 있는 show 정보를 표현하는 언어 instance에 기초한다.
  • 언어와 시공간적 영상 표현을 합하여 질문에 대해 추론하고 답을 예측한다.

Knowledge Base

시청자가 시리즈를 볼 때 정보를 습득하는 것을 모방한다. show에 대해 특정 정보에 접근해야 하기 때문에, Knowledge의 AMT worker 주석에 의존한다.

모아진 Knowledge는 자연어 문장의 형태로 주어진다. ‘Raj가 Penny 집에서 한 것은 무엇인가?’라는 질문에서 주석 Knowledge는 다음과 같다:

Raj는 Missy에게 데이트하자고 요청하길 원했는데, Howard와 Leonard는 이미 그녀에게 물어봤지만 실패했기 때문이지만, (그가 먹었던) 약효가 사라졌고 그는 그럴(요청할) 수 없었다.

Knowledge Graphs와 같은 복잡한 구조에서 어떻게 정보를 가져오는지 불분명하기에, knowledge instance $w$는 자연어 문장으로 표현된다. 거의 중복되는 instance를 제거하였고, $N$은 24,282에서 19,821로 줄어들었다.

Knowledge base $K$는 다음과 같다.

[K = \lbrace w_j \vert j=1, …, N \rbrace]

Knowledge Base Cleaning

거의 중복되는 문장을 제거하기 위해 Knowledge instance 사이의 유사도를 측정하였다. 각 $w_j \in K$에 대해 다음과 같은 입력 문장을 만들었다:

[w_j^{‘} = [\text{CLS}] + w_j + [\text{SEP}]]

[CLS]는 문장의 시작을, [SEP]은 끝을 나타내는 token이다. 이를 60개의 token으로 나눈 뒤 BERT를 통과시켜 고차원의 projection을 얻었다.

[\mathbf{p}j = \text{BERT}{\mathbf{p}}(\tau_j)]

두 문장의 유사도는 cosine 유사도를 사용하였으며 다음과 같이 구해진다.

[\beta_{i, j} = sim(\mathbf{p}_i, \mathbf{p}_j)]

그리고 무향 그래프 $V$를 만들고 유사도 $\beta$가 0.998 초과인 경우에만 edge를 만들었다. 해당 그래프에서 크기 $L$ 이상의 clique를 찾아 임의로 1개만 남기고 나머지는 삭제하였다.

[V = \lbrace w_j \vert j=1, …, N\rbrace]

Knowledge Retrieval Module

전체 과정은 다음과 같다.
질문과 답안 선택지 $q_i, a_i^c, \quad c \in \lbrace 0, 1, 2, 3\rbrace$를 사용하여 Knowledge base $K$에 질의를 한다.
그리고 연관도 점수 $s_{ij}$에 따라 $w_j \in K$의 순위를 매긴다.

먼저 입력이 될 표현 $x_{ij}$를 다음과 같이 문자열들을 이어 붙여 구한다.

[x_{ij} = [\text{CLS}] + q_i + \sum_{k=0}^3 a_i^{\alpha_k} + [\text{SEP}] + w_j + [\text{SEP}]]

이전 연구들은 $a_i^c$의 순서는 별다른 영향이 없다고 하였지만, 불변성을 확보하기 위해 연관도가 높은 순($a_i^0 \rightarrow a_i^3$)으로 정렬하였다.

  • 그리고 입력 표현을 $n$개의 단어로 이루어진 sequence $\textbf{x}_{ij}^{10}$으로 토큰화하고 BERT에 입력으로 준다.
  • 점수를 매기기(scoring) 때문에 $\text{BERT}^{\text{S}}(\textbf{x}_{ij})$로 표기한다.
  • $s_{ij}$를 계산하기 위해 fully connected layer를 사용하고 sigmoid를 붙인다.
  • $\textbf{w}, b$를 각각 FC Layer의 weight와 bias라 할 때

[s_{ij} = \text{sigmoid} (\textbf{w}{\text{S}}^{\top} \cdot \text{BERT}^\text{S}(\textbf{x}{ij}) + b_{\text{S}} )]

$\text{BERT}^{\text{S}}, \textbf{w}, b$는 매칭되거나 되지 않는 QA-knowledge 쌍과 다음의 Loss로 미세조정(fine-tuned)된다:

[\mathcal{L} = -\sum_{i=j} \log(s_{ij}) -\sum_{i\neq j} \log(1 - s_{ij})]

각 $q_i$에 대해 $K$ 안의 모든 $w_j$는 $s_{ij}$에 의해 순위가 매겨진다. 이중 상위 $k$개가 질의로 주어진 질문과 가장 연관 있는 것으로써 이것들이 얻어진다.

Prior Score Computation

모델이 다른 답변 후보에 대해 다른 출력을 내는 것을 막기 위해 답안들을 정렬함으로써 순서에 불변적인 모델을 만들었다. prior score $\xi^c$에 따라

[a^c, \quad c \in \lbrace 0, 1, 2, 3\rbrace]

질문 $q$가 주어지면, $\xi^c$는 정답에 대한 $a^c$의 점수를 예측함으로써 얻어진다. 먼저 입력문장 $e^c$를 문자열을 이어 붙여 얻는다:

[e^c = [\text{CLS}] + q + [\text{SEP}] + a^c + [\text{SEP}]]

그리고 $e^c$를 120개의 토큰 $\mathbf{e}^c$로 토큰화한다. $\text{BERT}_{\text{E}}(\cdot)$를 output이 [CLS]인 BERT 네트워크라 한다면,

[\xi^c = \textbf{w}{\text{E}}^{\top} \text{BERT}{\text{E}}(\mathbf{e}^c) + b_E]

이제 모든 $\xi^c$를 내림차순으로 정렬한 후 이에 맞춰 답변 후보 $\alpha_c$를 재배열한다.

Video Reasoning Module

이 모듈에서는 얻어진 knowledge들이 영상 내용으로부터 얻은 multi-modal 표현과 함께 처리되어 정답을 예측한다. 이 과정은 다음 3가지 과정을 포함한다.

  1. Visual Representation
  2. Language Representation
  3. Answer Prediction

Visual Representation

각 video clip으로부터 $n_f$개의 프레임을 뽑아 영상 내용을 설명하기 위해 아래 4가지의 다른 과정을 거친다:

  1. Image features: 각 frame은 마지막 FC Layer가 없는 Resnet50에 들어가 2048차원의 벡터로 변환된다. 모든 frame에서 나온 벡터를 모아 새로운 FC Layer를 통과시켜 512차원으로 만든다.
  2. Concepts features: 주어진 frame에 대해, bottom-up object detector를 사용하여 object과 특성들의 리스트를 얻는다. 이를 전부 인코딩하여 $C$차원의 bag-of-concept 표현으로 만들고, FC Layer를 통해 512차원으로 변환된다. $C$는 가능한 모든 object와 특성들의 전체 수이다.
  3. Facial features: 주요 인물의 사진 3~18개를 사용하여 최신 얼굴인식 네트워크를 학습시켰다. 각 clip에 대해 $F$차원의 bag-of-faces 표현으로 인코딩하여, FC Layer를 통과시켜 512차원으로 만든다. $F$는 네트워크에서 학습되는 모든 사람의 수이다.
  4. Caption features: 각 frame에 대해 영상 내용을 설명하는 캡션을 Xu et al. 2015으로 만들었다. 각 clip으로부터 얻은 $n_f$개의 캡션은 언어표현 모델의 입력으로 사용된다.

Language Representation

텍스트는 미세조정된 BERT-reasoning을 통과한다. 언어입력은 다음과 같이 구해진다.

[y^c = [\text{CLS}] + caps + subs + q + [\text{SEP}] + a^c + w + [\text{SEP}]]

$caps$는 $n_f$개의 캡션을 시간순으로 이어 붙인 것이고 $subs$는 자막, $w$는 $k$개의 knowledge instance를 합친 것이다.
각 질문 $q$에 대해, 답변 후보 $a^c, \ c = \lbrace 0, 1, 2, 3\rbrace$ 하나당 하나씩 총 4개가 생성된다.

$m$개의 단어로 이루어진 $\mathbf{y}^c$로 토큰화하고 언어표현 $\mathbf{u}^c = \text{BERT}_{\text{R}}(\mathbf{y}^c)$를 얻는다. (R은 reasoning)

Answer Prediction

정답을 예측하기 위해, 시각표현 $\textbf{v}$(images, concepts, facial features)를 언어표현 $\mathbf{u}^c$를 이어 붙인다:

[\textbf{z}^c = [\mathbf{v}, \mathbf{u}^c]]

$ \textbf{z}^c$는 scalar로 사영된다.

[o^c = \textbf{w}_{\text{R}}^{\top}\textbf{z}^c + b_R]

예측된 답안 $\hat{a} = a^{\text{argmax}_c\textbf{o}}$는 $\textbf{o} = (o^0, o^1, o^2, o^3)^\top$ 중 최댓값의 index로 구해진다. $c^*$를 정답이라고 하면 multi-class cross-entropy loss를 써서 미세조정한다:

[\mathcal{L}(\mathbf{o}, c^) = - \log \frac{\exp(o^{c^})}{\Sigma_c \exp{(o^c)}} \qquad \text{for} \ \text{BERT}{\text{R}}, \textbf{w}{\text{R}}, b_{\text{R}}]


실험 결과(Experimental Results)

ROCK 모델을 여러 기준 모델과 비교하여 아래에 정리하였다. SGD를 사용하여 momentum 0.9, learning rate는 0.001을 사용하였으며 BERT는 사전학습된 초기값을 사용한 uncased based 모델을 사용하였다.

KnowIT VQA

Answers

데이터셋에 존재할 수 있는 잠재적 편향을 찾기 위해서 단지 답변 자체만을 고려하여 정답을 예측하는 평가를 진행하였다:

  • Longest / Shortest: 예측 답변이 가장 많거나 적은 단어를 포함하는 답을 선택한다.
  • word2vec / BERT sim: word2vec은 300차원의 사전학습된 벡터를 사용하였다. BERT에서는 3번째~마지막 layer의 출력을 사용하였다. 답변은 word representation의 평균으로 인코딩되었다. 예측은 가장 높은 코사인 유사도를 갖는 것을 선택한다.

전체적으로, baseline은 매우 낮은 성능을 보였으며, Longest만이 찍는 것보다 간신히 나은 성능을 보였다. 정답이 긴 경우가 조금 많은 것을 제외하면 데이터셋에서는 특별한 편향은 발견되지 않았다.

KnowIT VQA

QA

오직 질문과 답변만을 고려하여 여러 baseline에 대해 실험을 진행하였다.

  • word2vec / BERT sim: 위의 Answers와 비슷하게 진행되었으며 질문이 고려 대상에 추가되었다.
  • TF IDF: tf-idf에 의한 단어벡터 가중으로 질문과 답변을 표현한 후 512차원으로 만들었다. 질문과 4개의 답변을 이어 붙여 4-class 분류기에 집어넣었다.
  • LSTM Emb. / BERT: 질문과 답변들의 단어를 사전학습된 BERT와 LSTM에 통과시킨다. LSTM의 마지막 layer는 512차원의 문장표현으로 사앵되었다. 역시 각각을 이어 붙여 4-class 분류기에 넣었다.
  • ROCK_QA: $m = 120$ token을 사용하는 ROCK 모델을 질문과 답변만으로 학습시켰다.

유사도에 기반한 방법을 찍는 것보다 형편없지만, 분류기를 사용한 경우는 훨씬 더 나은 결과를 보이며, 사람보다 더 잘하기도 했다.

KnowIT VQA

Subs, QA

자막, 질문, 답변을 사용한다.

  • LSTM Emb. / BERT: 자막은 LSTM에 의해 인코딩된 후 자막-질문-답변으로 이어 붙여 4-class 분류기에 넣는다.
  • TVQA_SQA: 언어는 LSTM layer에 의해 인코딩되며 다른 시각정보는 쓰지 않았다.
  • ROCK_SQA: $m = 120$ token을 사용하는 ROCK 모델을 자막, 질문, 답변만으로 학습시켰다.

LSTM BERT와 ROCK_SQA는 질문과 답변만을 사용할 때보다 성능이 5.7% 향상되었다. LSTM Emb.는 전혀 향상되지 않았으며 자막의 긴 문장을 인코딩하는 데 한계가 있었기 때문이라 생각된다.

KnowIT VQA

Vis, Sub, QA

이제 언어와 시각 정보 둘 다에 기반한 Video QA 모델이다.

  • TVQA: SOTA VideoQA 방법이다. 언어는 LSTM layer로, 시각 데이터는 visual concepts으로 인코딩된다.
  • ROCK_VSQA: $m = 120$ token과 $n_f=5$ frame을 사용하는 ROCK 모델을 질문과 답변만으로 학습시켰다. 4개의 다른 시각표현이 사용되었다.

ROCK_VSQA는 TVQA를 6.6%만큼 앞질렀다. 그러나, 어떤 visual 모델이든지 ROCK_SQA를 능가하는데 이는 현 영상모델링 기법의 큰 한계를 암시한다.

KnowIT VQA

Knowledge

모델이 이제 Knowledge를 정답을 예측하는 데 사용한다. 전체 버전의 ROCK 모델은 $n=128, k=5$의 지식검색 모듈과 $m=512$의 영상추론 모듈을 사용한다.
non-knowledge 모델과 비교하여, 지식검색 모듈을 포함함으로써 6.5%의 성능 향상이 있으며, 지식기반 접근법의 상당한 잠재력을 보인다(시각표현인 Image, Concepts, Facial과 같이). 그러나, 전문가인 사람과 비교하여, ROCK은 여전히 뒤처지며, 이는 향상시킬 여지가 충분하다는 것을 뜻한다. 지식검색 대신 딱 맞는 지식을 그대로 갖고 오는 모델(ROCK_GT)를 사용하면 정확도는 0.731까지 오르며, 지식검색 모듈도 개선할 여지가 있음을 보여준다.

KnowIT VQA

마지막으로 아래 그림에서 질적 평가 결과를 볼 수 있다.

KnowIT VQA

Knowledge Retrieval Results

지식검색 모듈에 대한 결과로, recall at K와 median rank(MR)에 대한 결과를 아래 표에서 볼 수 있다.

  • 질문만 있는 경우
  • QA parameter sharing: 같은 parameter가 4개의 후보 답변에 사용됨
  • QA prior score: prior score에 따라 순서를 배열하는 방법
KnowIT VQA

질문만 사용하는 경우와 다른 두 경우에 큰 차이가 있는데 이는 후보 답변에 올바른 지식을 가져오는 데 필요한 정보가 포함되어 있음을 나타낸다. 가장 좋은 결과는 prior score에 따라 순서를 정한 것인데, 이는 모든 후보 답변을 전부 사용하는 것이 더 정확한 정보를 얻는 데 도움이 된다는 뜻이다.


결론(Conclusion)

새로운 지식 필요 영상 VQA를 제시하였고 multi-modal 영상정보와 지식을 결합하여 사용하는 영상추론 모델을 제시하였다. 진행된 실험은 영상이해 문제에서 지식기반 접근법의 상당한 잠재력을 보였다. 그러나, 사람의 능력에 비하면 크게 뒤처지며, 이 데이터셋을 통해 더 강력한 모델의 개발을 장려하며 이를 바라는 바이다.

Acknowledgements

New Energy and Industrial Technology Development Organization


참고문헌(References)

논문 참조!


Comment  Read more

KVQA - Knowledge-Aware Visual Question Answering(KVQA 논문 설명)

|

이 글에서는 KVQA: Knowledge-Aware Visual Question Answering에 대해 알아보고자 한다.

VQA task는 이미지(Visual, 영상으로도 확장 가능)와 그 이미지에 대한 질문(Question)이 주어졌을 때, 해당 질문에 맞는 올바른 답변(Answer)을 만들어내는 task이다.

KVQA는 VQA의 일종이지만, 전통적인 VQA와는 달리 이미지 등 시각자료에서 주어지는 정보뿐만 아니라 외부 지식(상식 베이스, Knowledge Base)이 있어야만 문제를 풀 수 있는 질의들로 이루어진 새로운 task이다.

KVQA 홈페이지는 http://malllabiisc.github.io/resources/kvqa/ 이다.
데이터셋도 같은 링크에서 다운받을 수 있다(총 90G 상당).

중요한 부분만 적을 예정이므로 전체가 궁금하면 원 논문을 찾아 읽어보면 된다.


KVQA: Knowledge-Aware Visual Question Answering

논문 링크: KVQA: Knowledge-Aware Visual Question Answering

초록(Abstract)

Visual Question Answering(VQA)는 CV, NLP, AI에서 중요한 문제로 떠오르고 있다. 전통적인 VQA에서는, 이미지에 대한 질문이 주어지는데 이는 이미지에 있는 정보만으로도 답변할 수 있다: 예를 들어, 사람들이 있는 이미지가 주어지면, 이미지 안에 사람이 몇 명이나 있는지를 묻는 것과 같은 식이다.
좀 더 최근에는 고양이/개 등 일반명사를 포함하는 일반상식(commonsense knowledge)을 요구하는 질문에 답변하는 것이 주목받고 있다. 이러한 흐름에도 버락 오바마 등 고유명사에 대한 세계 지식(world knowledge)를 요하는 질문에 답변하는 것은 다뤄진 적이 없었다. 그래서 이러한 부분을 이 논문에서 다루며, (세계) 지식을 알아햐 하는 VQA인 KVQA를 제안한다.
이 데이터셋은 18K개의 고유명사와 24K개의 이미지를 포함하는 183K개의 질답 쌍으로 이루어져 있다. 데이터셋의 질문들은 여러 객체와 다중 관계, 큰 Knowledge Graphs(KG) 상에서 다중도약 추론을 요구한다. 이러한 점에서 KVQA는 KG를 갖는 VQA에서 가장 큰 데이터셋이다. 또한, KVQA에 SOTA 방법을 사용한 결과도 보인다.


서론(Introduction)

ovieQA Dataset

VQA는 AI와 소통하는 데 있어 아주 훌륭한 도구로 자리잡았다. 지난 몇 년간 많은 발전이 있었는데, 우선은 VQA의 시초가 되는 VQA 논문가 있다. 전통적인 VQA는 이미지 등의 시각자료가 주어지면, 이미지에 관련한 질문을 묻고, 이미지에서 얻은 정보를 바탕으로 답변을 하는 방식이다.

위 그림이 주어졌을 때, 전통적인 VQA 질문의 예시는 다음과 같다.

  • Q: 이미지에 몇 명의 사람이 있는가?
  • A: 3

최근에는 Commonsense Knowledge를 사용해야만 문제를 풀 수 있는 VQA가 더 관심을 받고 있다. 이러한 일반상식의 예시는 다음과 같다.

  • Microphone은 소리를 증폭시키는 데 쓴다.
    • Microphone은 일반명사이다.

일반상식을 필요로 하는 질문은 다음과 같다.

  • Q: 이미지에 있는 것 중 무엇이 소리를 증폭시키는 데 쓰이는가?
  • A: Microphone

그러나 실생활에서 문제는 이렇게 간단하지 않고 이미지에 존재하는 고유명사(named entities)에 대한 정보를 필요로 하는 경우가 많다. 예를 들면,

  • Q: 버락 오바마의 왼쪽에 있는 사람은 누구인가?
  • A: Richard Cordray

  • Q: 이미지에 있는 사람들은 공통 직업을 가지는가?
  • A: Yes

그래서 이러한 경우를 다루기 위해 논문에서 KVQA(Knowledge-aware VQA)를 제안한다. 이러한 방향의 연구는 별로 다뤄지지 않았고 또한 필요할 것이라 생각된다.

Wikidata(Vrandecic and Kr¨otzsch 2014)는 대규모 KG로서 사람들, 생물 분류, 행정상 영토, 건축구조, 화합물, 영화 등 5천만 개의 객체를 포함하는 KG이다. 여기서 필요한 것을 추출하는 것은 어렵기 때문에, 논문에선 생략되었다. 대신 이에 대한 배경지식과 관련한 사람들과 수동으로 검증된 질답 쌍을 포함하는 KVQA 데이터셋을 제안한다.

KVQA 데이터셋에서는 visual 고유명사와 Wikidata의 객체를 연결하기 위해 Wikidata에서 69K 명의 사람들 이미지를 포함하도록 했다.

이 논문이 기여한 바는:

  1. 이미지의 고유명사를 다로는 VQA를 처음으로 다룬다.
  2. Knowledge-aware VQA인 KVQA 데이터셋을 제안하며 이는 일반상식을 요구하는 기존 데이터셋보다 12배 크며 고유명사를 다룬 것으로는 유일하다.
  3. KVQA에 SOTA 방법을 적용하여 그 성능을 제시하였다.

관련 연구(Related Works)

  • VQA는 2015년 제시된 이후 계속해서 발전하여 2017년 v2.0 데이터셋 발표, (2020년까지) 챌린지를 매년 열고 있다. 비슷한 연구가 많이 발표되었지만 문제가 단순하다는 점에서 한계점이 명확하다.
  • 이후에는 일반상식을 필요로 하는 VQA가 많이 연구되어 왔다.
  • Computer Vision and Knowledge Graph: 컴퓨터비전과 KG를 연결하려는 데 관심이 늘고 있다. 이는 단지 VQA의 활용에만 그치는 것이 아니라 이미지 분류 등의 전통적인 CV 문제에서도 사용된다. 하지만, 대부분은 이미지와 일반상식 그래프를 연결짓는 데에 치중하고 있다.
  • Other Datasets: CV에서 사람을 인식하고 판별하는 것은 주류 연구 분유 중 하나이다. 유명인사나 사람의 자세 추정, 장소 추정 등이 있다.
  • Face identification and context: 이미지에 나타나는 고유명사와 KG를 연결하는 것은 web scale에서 얼굴식별의 필요로 이어진다. 얼굴식별은 연구가 많이 이루어졌지만 대부분 작은 규모에서 이루어지고 있다. KVQA이 더 규모가 크기 때문에 좋다는 뜻이다.

KVQA 데이터셋과 다른 데이터셋을 비교한 표를 아래에서 볼 수 있다:

ovieQA Dataset

KVQA 데이터셋(KVQA)

간략한 통계는 아래 표와 같다. 이미지와 질문의 수 등을 볼 수 있고, train/val/test set이 구분되어 있다.

ovieQA Dataset

데이터는 다음 과정을 통해 모았다:

  1. Image Collection: Wikidata로부터 운동선수, 정치인, 배우 등의 사람들의 리스트를 가져와 Wikipedia에서 사람(30K)의 이미지(70K)와 설명을 가져왔다.
  2. Counting, identifying and ordering persons in image: 이미지의 사람 수를 세고, 사람 수에 따라 human annotator를 부여하였다. 사람이 없거나 너무 많은 경우 등은 제외하고 중복 제거 등을 수행하였다. 그리고 왼쪽부터 오른쪽으로 맞는 human annotator를 부여하였다.
  3. Obtaining ground-truth answers: 이제 고유명사(사람)와 이미지 안의 관계(왼쪽/오른쪽 등)를 파악하였으니 이미지에 있는 사람에 어떤 질문을 할 수 있는지를 정하여 질문 템플릿을 정하고 SPARQL는 오직 ground truth를 얻기 위해 사용되었다.
  4. Training, Validation, and testing: train/val/test set을 70/20/10%의 비율로 다른 VQA와 동일하게 구분하였다.
  5. Paraphrasing questions: task의 복잡도를 늘리고 실세계와 유사하게 만들기 위해 test set의 질문을 다른 표현으로 바꿔서(https://paraphrasing-tool.com/) 이를 수동으로 검증하여 일부를 사용하였다. 예시는:
  • 원래 질문: 이미지에 있는 사람들 중 Paula Ben-Gurion와 결혼했던 사람은 누구인가?
  • 바뀐 질문: Paula Ben-Gurion과 어떤 시점에선 결혼한 적 있는 사람은 누구인가?
ovieQA Dataset

KVQA 데이터셋 분석(Analysis of KVQA)

KVQA는 자세나 인종 등 광범위한 사람들을 다루거나 KG에서 다중도약 추론을 해야 하는 challenge를 포함한다. 질문은 총 10가지 분류로 나뉜다:

spatial, 1-hope, multi-hop, Boolean, intersection, subtraction, comparison, counting, multi-entity, multi-relation

위 분류는 상호 배제적인 것은 아니다. 위 그림의 (c)에서, 추론은 다음과 같이 여러 단계를 거쳐야 한다:

  • 왼쪽부터 2번째 사람을 찾고
  • Narendra Modi는 BJP의 일원이며
  • BJP는 Syama Prasad Mookerjee에 의해 설립되었다.

질문의 종류와 답변의 간략한 분포는 아래와 같이 확인할 수 있다.

ovieQA Dataset

일반적인 VQA에서는 ‘어떤 스포츠인가’라는 질문에는 높은 확률로 ‘테니스’가 정답이고, Yes/no 질문에서는 ‘Yes’가 87%으로 꽤 편향된 것을 볼 수 있다.
단 KVQA는 꽤 균등한 분포를 보이는데, 이는 질문을 다양하게 바꿈으로써 해결한 것이라 한다.

Knowledge Graph(KG)

논문 발표 시점 최신인 2018-05-05 버전의 Wikidata를 KG로 사용하였다. 이는 ‘주어-관계-목적어’의 triplet 형태를 가지고 각 객체와 관계는 고유한 Qid와 Pid로 표현된다(예. Barack Obama는 Q76, has-nickname은 P1449). 이 KG는 5200개의 관계, 1280만개의 객체와 5230만 개의 지식을 포함한다. 이럴 114명K의 사람에 대한 것을 고려하여 Wikidata에서 사람들의 이미지를 가져왔다. 단 데이터가 불완전하여 69K명의 것만 가져왔다. 이 이미지는 visual entity를 연결하는 데 사용된다.

Baseline을 평가하는 두 세팅은 다음과 같다:

  1. Closed-world setting: 18K의 객체와 3단계 추론을 사용한다. 사실(Facts)은 18종류의 관계만을 포함한다(직업, 시민권 국적, 출생지 등).
  2. Open-world setting: 훨씬 open된 3단계 추론 실험적 세팅이다. 69K의 객체와 상위 200개의 관계를 포함한다.

접근법(Approach)

Visual Entity Linking

Visual entity linking은 visual entity를 KG에 연결하는 것인데, KVQA에서 visual entity는 사람이다. 그래서 visual entity linking은 안면 식별이 되는데, 사람의 수가 매우 많으므로 그 규모가 매우 크다.

Face identification at scale

Face Localization은 KVQA에서 안면 식별의 선구자격 역할을 한다. 그래서 두 가지 방법(Zhang et al. 2016; Hu and Ramanan 2017)을 사용해보고 더 좋은 방법(Zhang)을 써서 face localization을 수행한다. 이후 얼굴 식별(face identificatino)을 수행하는데, Baseline으로 Facenet을 선정하여 사용하였다.

그래서 참고 이미지의 face representation을 얻고 1-최근접 이웃을 18K/69K명의 고유명사 이미지에 대해 찾았다. 결과는 아래에서 볼 수 있다.

ovieQA Dataset

VQA over KG

일단 Visual Entity를 KG에 열결하면, VQA 문제는 KG로부터 (질문과) 관련 있는 fact를 찾아 추론한 뒤 답변하는 것을 학습하는 것과 같아진다. 이 논문에서는 visual entity linking과 QA를 두 개의 분리된 모듈로 다룬다(end-to-end를 쓰지 않음).

KVQA의 baseline으로 memNet(memory network, Weston at al., 2014)을 썼는데 이 모델은 외부 지식으로부터 학습하는 일반적인 구조를 제공한다(memNet은 상식 요구 VQA에서 SOTA 성능을 보임). 이 논문에서 사용한 모델의 구조는 다음과 같다:

ovieQA Dataset

1. Entity Linking

이미지, Wikipedia 캡션(선택적 요소), 질문이 주어지면 이미지와 질문에 있는 entity(visual entities: 사람)를 찾는 것이다. Wikidata에서 가져온 참고 이미지를 활용하며, 텍스트(캡션과 질문)에 있는 entity를 찾기 위해 Dexter 라고 하는 오픈소스 entity recognizer를 사용한다. Visual entity linking과 Text entity linking은 위 그림에서 보듯이 따로 이루어진다.

이 부분에서 entity를 모두 찾고 또한 추가적으로 이미지 상의 entity들의 위치(상대적 위치나 얼굴의 좌표 등)를 얻는다.

2. Fetching facts from KG

이제 entity와 연관 있는 정보를 KG에서 찾는다. 여기서는 3단계(3-hop)만 거치도록 제한하였다. 이러한 knowledge fact들을 공간적 fact(ex. Barack Obama(의 얼굴의 중심)는 (x1, y1) 좌표에 있다)와 함께 보강한다.

그림에서 Facts + Face coornidates라 표시된 부분이다.

3. Memory and question representation

각 knowledge와 공간적 fact는 연관된 memory embedding $m_i$를 얻기 위해 BLSTM에 입력으로 주어진다. 질문 $Q$에 대한 embedding ($q$) 또한 비슷하게 얻어진다.

그리고 $q$와 $m_{ij}$ 사이의 매치되는 정도를 구하기 위해 내적과 softmax를 거친다:

[p_{ij} = \text{softmax}(q^Tm_{ij})]

여기서 $p_{ij}$는 knowledge fact들과 $Q$ 사이의 soft attention과 같은 역할을 한다. 이를 얻으면 모든 fact에 대한 출력 representation을 선형결합하여 출력 representation을 구한다:

[O = \sum_j p_{ij}o_{ij}]

$o_{ij}$는 fact $j$에 대한 representation이다.

4. Question answering module

출력 representation $O$와 $q$의 합은 MLP $f_\theta$에 입력으로 들어간다($\theta$는 학습가능한 parameter). 그리고 정답 $\hat{a}$를 구하기 위해 softmax를 적용한다:

[\hat{a} = \text{softmax}(f_\theta(O+q))]

학습하는 동안, memory/question representation과 QA 모듈을 함께 학습한다. 손실함수는 cross-entropy loss를 사용하였으며 SGD로 최소화한다.

다중도약(multi-hop) facts 탐색을 효율적으로 하기 위해 memory layer를 쌓고 질문 representation을 다음과 같이 구한다:

[q_{k+1} = O_{k+1} + q_k]

첫 번째 레이어의 질문 representation은 BLSTM으로부터 구해진다. 최상층 레이어(layer K)에서 질문에 대한 답은 다음과 같이 구해진다.

[\hat{a} = \text{softmax}(f_{\theta}(O_K+q_{K-1}))]

이 논문에서는 3-hop을 사용하므로 $K=3$이다.

Memory Network의 대안은 knowledge facts를 표현하기 위해 BLSTMs를 사용하는 것이다. 이는 baseline의 하나로 사용되었다.

KVQA의 양적평가(quantitative results)는 아래 표의 왼쪽 부분과 같다.

ovieQA Dataset

Closed/Open World 각각에 대해 평가하였으며, Wikipedia Caption을 사용했으면 +wikiCap, 아니면 -wikiCap으로 표시되어 있다. 질문을 paraphrase했으면 PRP, 아니면 ORG(original)이다.
모든 평가에서는 고정된 크기의 사전을 사용하였으며 질문에서 각 token, Wikipedia caption, visual entity들은 1-hot 벡터로 표현하였다.

결과를 보면,

  • BLSTMs는 fact의 수가 증가할수록 비효율적이었으며 memNet이 이를 압도한다.
    • visual entity linking은 많은 수의 다른 요인에 의해 open world에서 실수가 많았으며
    • 수많은 fact에서 질문과 관련된 fact를 찾는 것이 어려워지기 때문이다.
  • Ablation study에서(위 표에서 오른쪽 부분)는
    • KG에서 논리적 추론만에 의한 부분을 연구하기 위한 세팅을 oracle setting이라 한다.
    • 이 oracle setting은 각 사람과 이미지 내에서 사람의 순서는 알려져 있다고 가정한다.
    • memNet은 공간적, 다중도약, 다중관계, subtraction 등에서 부적합했지만 1-hop, 이지선다 및 교차질문에서는 괜찮은 성능을 보였다.
    • 이것은 질문의 종류에 따라 어떤 가이드가 필요하다는 것을 뜻할 수 있다. 이는 추후 연구로 남겨둔다.

논의 및 요약(Discussion and Summary)

얼굴 식별과 VQA에서의 진전에도 불구하고 Knowledge-aware VQA에서 더 많은 연구가 필요함을 보였다. 기존의 Facenet이나 memory network는 수많은 distractor가 존재하거나 규모가 커진 경우에는 제대로 성능을 내지 못하였다.

이 논문에서는 Knowledge-aware VQA인 KVQA를 제안하였고 평가방법과 baseline을 제시하였다. KVQA의 현재 버전은 KG의 중요 entity인 사람에만 국한되어 있다. 하지만 Wikidata와 같은 KG는 기념물이나 사건 등 여러 흥미로운 entity에 대한 정보도 갖고 있기 때문에 추후 확장할 수 있다. 이 분야에 많은 연구가 이루어지길 희망한다.

Acknowledgements

MHRD와 인도 정부, Intel이 지원하였다고 한다..


참고문헌(References)

논문 참조!


Comment  Read more

Self-Supervised Learning(자기지도 학습 설명)

|

이 글에서는 Self-Supervised Learning(자기지도 학습)에 대해 알아본다. Self-Supervised Learning은 최근 Deep Learning 연구의 큰 트렌드 중 하나이다.

Self-Supervised Learning의 기본적인 개념과 여러 편의 논문을 간략히 소개하고자 한다.


Self-Supervised Learning

일반적으로 Supervised Learning(지도학습)이 높은 성능의 모델을 만드는 것이 유리하지만, 수많은 데이터에 label을 전부 달아야 한다는 점에서 데이터셋 모으기가 어려우며 따라서 활용하는 방법도 제한적일 수밖에 없다.
이와 같은 문제를 해결하고자 나온 방법이

  • 아주 일부분만 label이 존재하는 데이터셋을 사용하는 Semi-Supervisd Learning(준지도 학습)
  • label이 전혀 없는 데이터셋을 사용하는 Unsupervised Learning(비지도 학습)

이고, 최근 주목받는 연구 방법이 Self-Supervised Learning(자기지도 학습)이다. 보통 Self-Supervised Learning을 연구할 때, 다음과 같은 과정을 따른다:

  1. Pretext task(연구자가 직접 만든 task)를 정의한다.
  2. Label이 없는 데이터셋을 사용하여 1의 Pretext task를 목표로 모델을 학습시킨다.
    • 이때, 데이터 자체의 정보를 적당히 변형/사용하여 (label은 아니지만) 이를 supervision(지도)으로 삼는다.
  3. 2에서 학습시킨 모델을 Downstream task에 가져와 weight는 freeze시킨 채로 transfer learning을 수행한다(2에서 학습한 모델의 성능만을 보기 위해).
  4. 그래서 처음에는 label이 없는 상태에서 직접 supervision을 만들어 학습한 뒤, transfer learning 단계에서는 label이 있는 ImageNet 등에서 Supervised Learning을 수행하여 2에서 학습시킨 모델의 성능(feature를 얼마나 잘 뽑아냈는지 등)을 평가하는 방식이다.

여기서 Self-Supervised Learning의 이름답게 label 등의 직접적인 supervision이 없는 데이터셋에서 스스로 supervision을 만들어 학습하기 때문에, supervision이 전혀 없는 Unsupervised Learning의 분류로 보는 것은 잘못되었다는 시각이 있다.

I now call it “self-supervised learning”, because “unsupervised” is both a loaded and confusing term. In self-supervised learning, the system learns to predict part of its input from other parts of it input. In other words a portion of the input is used as a supervisory signal to a predictor fed with the remaining portion of the input. Self-supervised learning uses way more supervisory signals than supervised learning, and enormously more than reinforcement learning. That’s why calling it “unsupervised” is totally misleading. That’s also why more knowledge about the structure of the world can be learned through self-supervised learning than from the other two paradigms: the data is unlimited, and amount of feedback provided by each example is huge. Self-supervised learning has been enormously successful in natural language processing. For example, the BERT model and similar techniques produce excellent representations of text. BERT is a prototypical example of self-supervised learning: show it a sequence of words on input, mask out 15% of the words, and ask the system to predict the missing words (or a distribution of words). This an example of masked auto-encoder, itself a special case of denoising auto-encoder, itself an example of self-supervised learning based on reconstruction or prediction. But text is a discrete space in which probability distributions are easy to represent. So far, similar approaches haven’t worked quite as well for images or videos because of the difficulty of representing distributions over high-dimensional continuous spaces. Doing this properly and reliably is the greatest challenge in ML and AI of the next few years in my opinion. - Yann Lecun

게시물을 보면 예전에는 이러한 학습 방식을 “주어진” supervision이 없기 때문에 Unsupervised Learning이라 불렀지만, 사실은 모델이 “스스로” supervision을 만들어 가며 학습하기 때문에 Self-Supervised Learning이라 부르는 것이 맞다고 설명하는 내용이다.
그리고 (label은 없어도) 데이터는 무궁무진하며, 그로부터 얻을 수 있는 feedback 역시 엄청나기 때문에 “스스로” supervision을 만드는 Self-Supervised Learning 방식이 매우 중요하게 될 것이라고 언급한다.


Image Representation Learning

Discriminative Unsupervised Feature Learning with Exemplar Convolutional Neural Networks

NIPS 2014

Examples

이 논문에서는 Examplarpretext task로 한 Examplar-CNN이라고 하는 모델을 소개한다.

$N$개의 이미지에서 중요한 부분, 정확히는 considerable gradients를 가지고 있는 32 $\times$ 32 크기의 patch를 하나씩 추출한다(Gradient 크기의 제곱에 비례하는 확률로 patch를 선정함). 이렇게 추출한 Seed patch를 갖고 여러 가지 data augmentation을 진행한다. 위 그림의 오른쪽에서 볼 수 있듯이 translation, scaling, rotation, contrast, color 등을 이동하거나 조정하여 만든다.

분류기는 Data augmentation으로 얻어진 patch들은 하나의 class로 학습해야 한다. 여기서 Loss는 다음과 같이 정의된다.

[L(X) = \sum_{\text{x}i\in X} \sum{T \in T_i} l(i, T\text{x}_i)]

$l(i, T\text{x}_i)$은 Transformed sample과 surrogate true lable $i$ 사이의 loss를 의미한다. 즉 하나의 이미지가 하나의 class를 갖게 되는데, 이는 데이터셋이 커질수록 class의 수도 그만큼 늘어난다는 문제를 갖고 따라서 학습하기는 어렵다는 단점을 안고 있다.

아래는 실험 결과이다.

Examples

Unsupervised Visual Representation Learning by Context Prediction

ICCV 2015

이 논문에서는 context prediction 종류의 pretext task를 제안하는데, 간단하게 말하면 이미지에 $ 3 \times 3 = 9$개의 patch를 가져와, 중간 patch와 다른 1개의 patch를 보여 주고, 다른 1개의 patch가 중간 patch의 어느 뱡향(왼쪽 위, 위, 오른쪽 등 8방향)에 위치하는지를 찾는 문제이다. 아래 그림을 보면 이해가 빠를 것이다:

Examples
위 그림에서 무엇이 정답인지 보기

Answer key: Q1: Bottom right Q2: Top center

두 장의 이미지를 한 번에 입력으로 받아야 하기 때문에 아래와 같이 patch를 받는 부분을 두 부분으로 만들었다.

Examples

그리고 “자명한” 해를 쉽게 찾을 것을 방지하기 위해, 9개의 patch들이 딱 붙어 있지 않도록 하였으며 중심점의 위치도 랜덤하게 약간 이동하여 patch를 추출하여 자명한 경우를 최대한 피하고자 하였다(하지만 충분치는 않았다고 한다).

아래는 실험 결과이다.

Examples

Unsupervised Learning of Visual Representations using Videos

ICCV 2015

CNN에 의미적으로 레이블링된(semantically-labeled) 것이 꼭 필요한지 의문을 가지며 출발하는 이 논문은 시각적 표젼(visual representatinos)을 학습하기 위해 레이블이 없는 십만 개의 영상을 웹에서 가져와 사용하였다. 핵심 아이디어는 visual tracking이 supervision을 준다는 것이다. track으로 연결된 두 개의 패치는 같은 물체나 그 일부분을 포함할 것이기에, deep feature space에서 비슷한 시각적 표현을 갖고 있을 것이라 생각할 수 있다. 이러한 CNN 표현을 학습하기 위해 ranking loss function을 사용하는 Siamese-triplet 네트워크를 사용한다.
ImageNet에서 단일 이미지를 가져오는 대신 레이블이 없는 10만 개의 영상과 VOC 2012 dataset을 사용하여 비지도 학습을 수행, 52% mAP를 달성하였다. 이는 지도학습을 사용한 ImageNet 기존 결과의 54.4% mAP에 거의 근접하는 수치이다.
또한 이 논문은 surface-normal 추정 문제와 같은 것도 충분히 잘 수행함을 보여준다.

Examples
  • (a) 레이블이 없는 영상이 주어지면 그 안에서 비지도 tracking을 수행한다.
  • (b) 첫 frame에서 Query 패치, 마지막 frame에서 추적하는 patch, 다른 영상에서 가져온 무작위 패치로 구성된 총 3개의 패치가 siamese-triplet 네트워크에 입력으로 들어가 학습된다.
  • (c) 학습 목표: Query 패치-추적된 패치 사이의 거리가 Query 패치-무작위 패치 사이의 거리보다 더 작게 되도록 학습한다.

Joint Unsupervised Learning of Deep Representations and Image Clusters

CVPR 2016

JULE는 deep representations와 image cluster의 Joint Unsupervised LEarning을 위한 recurrent framework를 말한다. 이 framework에서, clustering 알고리즘에서 연속적인 동작이 recurrent process의 한 스텝으로 표현되어, CNN의 representation 출력의 위에 쌓아지는 형태를 갖는다. 학습하는 동안, image clusters와 representations는 공동으로 업데이트된다: image clustering은 forward pass로, representation 학습은 backward pass로 수행된다.
좋은 표현은 image clustering에 유익하며, 그 결과는 representation 학습에 지도를 해 줄 수 있을 것이라는 것이 핵심 부분이다. 두 과정을 하나의 모델에 통합하여 합쳐진 가중 triplet loss를 사용하여 end-to-end 방식으로 최적화했기에, 더 강력한 표현뿐만 아니라 더 정확한 image cluster도 얻을 수 있다.
여러 실험은 이 방법이 여러 데이터셋에서 image clustering을 할 때 기존 SOTA를 뛰어넘는다는 것을 보여준다.

Examples
Examples

Colorful Image Colorization

ECCV 2016

이 논문에서는 회색조 이미지가 입력으로 주어지면 적절히 색깔을 입혀 그럴 듯한 컬러 이미지로 바꾸는 작업을 수행한다. 이 문제는 명백히 제약조건이 부족하기 때문에, 기존 접근법은 사용자와 상호작용하거나 채도를 감소시킨 채색에 의존하였다.
여기서는 선명하고 사실적인 채색 결과를 도출하는 완전히 자동화된 접근법을 제시한다. 저자들은 이 문제에 내재하는 불확실성을 포용하여 이 문제를 분류 문제로 생각하고 채색 결과의 색깔 다양성을 증가시키기 위해 학습 시간에서 class별 rebalancing을 사용한다. 시스템은 CNN에서 feed-forward pass로 구성된다.

결과는 ‘채색 튜링 테스트(colorization Turing test)’으로 평가하는데, 사람 지원자에게 실제 이미지와 생성된 이미지 중 어떤 것이 실제 이미지인지 판별하도록 하였다. 결과는 32%가 답을 틀렸다는 점에서 이전 방법에 비해 매우 뛰어난 결과를 보여준다.

더욱이, 채색이라는 문제가 cross-channel encoder로서 기능하는 self-supervised feature 학습을 위한 강력한 pretext task로 기능할 수 있음을 보였다.

아래에서 채색(colorization) 결과를 확인할 수 있다. 꽤 뛰어난 결과를 보여준다.

Examples

전체 모델 구조는 아래와 같다.

Examples

Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles

ECCV 2016

이 논문은 직소 퍼즐처럼 이미지에 9개의 patch를 만들어 순서를 뒤섞은 뒤 원래 배치를 찾아내는 문제를 pretext task로 지정하였다. 대부분은 너무 비슷한 순열이기 때문에 딱 100개의 순열만을 지정하여 이를 분류하는 것을 목표로 한다.

Examples

다른 문제 간 호환성을 위해 context-free network(CFN, siamese-enread CNN)을 사용하였다. 이미지 패치를 입력으로 하고 CFN은 AlexNet에 비해 적은 parameter를 가지면서 동일한 의미 학습 능력을 유지한다고 한다.


Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion

입력 이미지에 무작위 noise를 추가한 뒤 원래 이미지를 복원하는 것을 pretext task로 지정하였다.

Examples

Self-supervised learning of visual features through embedding images into text topic spaces

CVPR 2017

대규모의 multimodal (텍스트와 이미지) 문서를 사용함으로써 visual features를 self-supervised learning을 수행한 논문이다. 특정 이미지가 그림으로 나타날 가능성이 더 높은 의미론적 문맥을 예측하는 CNN을 학습함으로써 구별되는 visual features이 학습될 수 있음을 보였다고 한다.

이를 위해 잘 알려진 주제 모델링 기술을 사용하여 텍스트 말뭉치에서 발견 된 숨겨진 의미 구조를 활용하였고, 최근의 자기지도 접근 방식과 비교하여 이미지 분류, object detection 및 multimodal 검색에서 SOTA 성능을 보여주었다.

Examples

Colorization as a Proxy Task for Visual Understanding

여기서는 Proxy Task라는 이름으로 self-supervised learning을 수행했다. 이 논문에서는 ImageNet의 학습 paradigm을 재검토하여 다음 질문에 대한 답을 찾는다:

  • 얼마나 많은 학습 데이터가 필요한가?
  • 얼마나 많은 레이블이 필요한가?
  • 미세조정할 시 얼마나 많은 features가 변화하는가?

그래서 Proxy task로 채색(colorization) 문제를 사용하여 강력한 지도를 해줄 수 있음을 보인다.

Examples

Learning Image Representations by Completing Damaged Jigsaw Puzzles

WACV 2018

이 논문은 직소 퍼즐을 사용하는데 위의 논문과는 달리 일부 손상이 가해진 직소 퍼즐을 pretext task로 삼아 손상된 직소 퍼즐을 맞추는 것을 목표로 하였다.

3 $\times$ 3개의 패치를 만들고 순서를 섞은 뒤, 9개 중 1개를 제거하고 회색조 이미지로 변환한다. 이를 원래 이미지로 복원하는 것이 목표이다.

Examples
Examples

Unsupervised Representation Learning by Predicting Image Rotations

ICLR 2018

Examples

이 논문은 이미지를 0°, 90°, 180°, 270° 회전시킨 후 얼마나 회전시켜야 원본 이미지가 나오는지를 맞히는 4-class 분류 문제를 pretext task로 사용하였다.

Examples

회전시킨 4종류의 이미지를 한 번에 넣는 것이 효율이 좋고, 2 또는 8방향 회전도 고려하였으나 4방향이 가장 좋은 성능을 보인다고 한다.


Cross-Domain Self-supervised Multi-task Feature Learning using Synthetic Imagery

CVPR 2018

보다 일반적인 고수준의 시각표현을 얻기 위해 하나의 task가 아닌 여러 개의 task를 학습시키는 방법을 제안하는 이 논문은 합성된 이미지를 학습한다. 실제 이미지와 합성된 이미지의 도메인 차이를 극복하기 위해 적대적 학습 방법에 기초한 비지도 domain adaptation 방법을 사용한다. 합성된 RGB 이미지가 입력으로 들어오면 네트워크는 그 표면 normal, depth, 등고선 등을 동시 추정하며 실제와 합성된 이미지 domain 간의 차이를 최소화하려 한다.

Examples

Depth prediction에서 기존 feature 학습 방법은 패치의 상대적 위치를 예측하능 등의 task를 pretext task로 한다. 이 논문에서, pretext task는 pixel prediction task를 채택하였다.

Examples

이 논문에서, Instance contour detection(객체 등고선 탐지), Depth Prediction(깊이 추정), Surface normal estimation(표면 수직벡터 추정)이 multi-task를 구성한다.


Self-Supervised Representation Learning by Rotation Feature Decoupling

ICML 2019

이 논문에서는 회전과 관련된 부분과 무관한 부분을 포함하는 split representation을 학습하는 모델을 제시한다. 이미지 회전과 각 instance를 동시에 식별하는데, 회전 식별과 instance 식별을 분리함으로써 회전의 noise 영향을 최소화하여 회전 각도 예측의 정확도를 높이고 이미지 회전과 관계없이 instance를 식별하는 것 역시 향상시키도록 한다.

Examples

방법은 다음으로 구성된다:

  • Rotation Feature Decoupling
    • 이미지 회전 예측
    • Noisy한 회전된 이미지 식별
    • Feature Decoupling
      • 회전 분류
      • 회전과 무관한 부분
      • 이미지 instance 분류
Examples

Unsupervised Deep Learning by Neighbourhood Discovery

ICML 2019


##


##


##


##


Examples
Comment  Read more