Non-local Neural Networks Review

"Non-local Neural Networks"

Abstract

  Convolutional과 반복적인 연산은 한 번에 하나의 지역(one local neighborhood)을 처리하는 building block이다. 본 논문에서는 장거리 의존성을 알기 위한 일반적인 family of building blocks인 non-local 연산을 제안한다. Computer vision의 고전적인 non-local means method에 영감을 받아, non-local operation은 모든 위치에서 feature의 가중치 합으로 각 위치에서의 response(반응)을 계산한다. 이러한 building block은 많은 computer vision의 구조에 더할수 있다. Video classification 에서 non-local model은 어떠한 bell and whistles(optical flow, multi-scale testing) 없이, SotA를 달성했다. Static 영상 인식에서, non-local models은 object detection, segmentation, 그리고 pose estimation의 성능을 향상 시켰다.

 

1. Introduction

  장거리 의존성을 아는것은 DNN에서 매우 중요하며, RNN은 장거리 의존성에 유리한 모델이고 CNN은 깊게 쌓아 형성된 large receptive field로 모델링 되었다. CNN과 RNN은 공간 혹은 시간에서 local neighborhod를 처리 하므로 장거리 의존성은 이러한 연산이 반복적으로 적용될때만 capture되어 데이터를 통해 신호를 점진적으로 전파할 수 있다. local 연산을 반복적으로 하는것은 다음과 같은 제한이 있다.

1. 연산이 비효율적이다.
2. 최적화 문제를 야기한다.
3. Multi-hop 의존성 모델링을 만든다.

  본 논문에서는 DNN에서 장기 의존성 capture를 위해 효율적이고, 간단하며, 포괄적인 non-local operation을 제시한다. non-local operation은 computer vision에서 고전적인 non-local mean operation을 일반화 시킨 것이다. 직관적으로, non-local operation은 입력 feature map의 모든 위치에서 feature의 가중치 합으로 각 위치의 반응을 계산한다. 위치의 집합은 공간, 시간 혹은 시공간일 수 있어, non-local operation이 영상, 시퀀스, 비디오 문제에 적용될 수 있음을 의미한다. non-local operation을 사용해서 얻을수 있는 이점은 다음과 같다.

• non-local operation은 위치 거리에 관계없이 두 위치 간의 상호작용을 계산하여 직접 장거리 의존성을 capture 한다.
• 실험에서 non-local operation은 효율적이고, layer의 수가 적더라도 좋은 성능을 보여준다.
• non-local operation은 다양한 입력 크기를 유지하고 다른 연산과 쉽게 결합할 수 있다.

직관적으로, non-local 연산은 입력 feature map의 모든 위치에서 feature map의 가중치 합으로 위치의 반응을 계산한다.

  Video에서는 시간과 공간상에서 픽셀간의 장거리 상호작용이 발생하기 때문에, non-local block은 feed forward 방식으로 시공간의 의존성을 직접 capture할 수 있다. 몇가지 non-local block을 사용한 네트워크는 vidoe classification에서 정확도를 향상 시켰고 연산면에서 기존의 3D conv counterparts 보다 경제적이다. 이로인해 실험결과에서는 non-local operation을 적용시킨 모델들이 SotA를 달성했다.

 

2. Non-local Neural Networks

2.1 Formulation

  DNN에서의 일반적인 non-local operation은 다음 식과 같다.

식 1

• i 는 응답이 계산될 출력 위치(공간, 시간, 시공간)의 인덱스, j 는 모든 possible 위치를 열거한 인덱스 이다.
• x 는 입력(영상, 시퀀스, 비디오 등), y 는 입력과 크기가 같은 출력 신호 이다.
• f (pairwise function)는 i 와 j 간의 sclar(affinity와 같은 관계를 나타내는것)을 계산한다.
• g (unary function)는 j 위치에서의 입력 신호의 표현을 계산한다.
• 반응(response)은 C(x)에 의해 정규화 된다.

  식 1의 non-local의 동작은 모든 위치 ( j ) 는 연산에서 고려되어진다. 비교적으로 CNN은 local neighborhood의 가중치 입력을 합산하고 i 시간대의 RNN은 종종 현재 혹은 최신 시간 단계만 기반으로 한다. Non-local operation은 또한 fully connected layer와 다르다. 식 1은 다른 위치 간의 관계를 기반으로 response를 계산하는 반면, fc 는 학습된 가중치를 사용한다. 달리 말하면, x_i 와 x_j 간의 관계는 non-local layer 와 다르게 fc 에서의 입력 데이터의 함수가 아니다. 게다가, 식 1은 다양한 크기를 입력할 수 있고, 출력에서 해당되는 크기를 유지한다. 반면에, fc layer는 고정된 크기의 입출력을 필요로 하고, positional correspondence를 잃는다.(어떠한 위치 i 에 대해 x로 부터 y까지의 정보를 잃는다)

  Non-local 연산은 유용한 buliding block이고 cnn, rnn에서 쉽게 사용할 수 있다. DNN에서 마지막 부분에서 사용되는 fc 와 다르게 non-local은 앞부분에 추가할 수 있다. 이를 통해 non-local과 local 정보를 모두 결합해 보다 풍부한 계층 구조를 구출할 수 있다.

2.2 Instatiations

  이 절에서는 f 와 g 에 대해서 설명한다. g 는 linear embedding 형태로만 고려해 식은 아래와 같다. W_g는 학습된 weight matrix이고, 공간상에서는 1x1 convolution, 시공간상에서는 1x1x1 convolution으로 실행된다.

  Pairwise function f 는 gaussian, embedded gaussian, dot product, concatenation이 있다.

Gaussian

Non-local mean과 bilateral filters에 따라서 f 를 Gaussian function 을 선택한다. 식은 아래와 같다.

식 2

• e의 지수는 dot-product와 비슷하다.
• Non-local mean과 bilateral filter에서 사용된 유클리디안 거리 또한 적용할 수 있지만, dot-product가 현재 딥러닝 플랫폼에서 실행하기 더 편리하다.
• Normalization factor는 아래의 식과 같이 모든 j 에 대한 합과 같다.

Gaussian Normalication factor

Embedded Gaussian

Gaussian function의 간단한 확장은 embedding 공간에서 유사성을 계산하기 위해서 이다. 식은 아래와 같이 정의한다.

식 3

• e의 지수들은 아래 그림과 같이 각각 임베딩 된다.
• Normalication factor는 Gaussian과 같다.

  최근 machine translation을 위해 제시된 self-attention module은 embedded Gaussain version을 사용한 특별한 non-local 연산 이다. 이것은 i 가 주어졌을 때 1/C(x) f(x_i, x_j) 가 차원 j 를 따라서 softmax 연산이 된다는 사실에서 알 수 있다. 이러한 의미는 self-attention에 있는 아래의 식을 얻을수 있다는 것이다. 이처럼, 본 연구는 최근 self-attention 모델을 non-local means의 고전적인 computer vision과 연관시킴으로써 insight를 제공하고, sequential self-attention 네트워크를 image/video 인식을 위해 일반적인 시간/시공간의 non-local 네트워크로 확장한다. 하지만, attention behavior이 본 연구에서는 필수적이지 않다. 이를 보여주기 위해 두가지 대안 version을 보여준다.

Dot product

f 는 dot-product와 비슷하게 다음과 같이 정의될 수 있다.

식 4

• Normalization factor 는 C(x) = N, N 은 gradient 계산을 단순화 하기 때문에 f 의 합이 아니라 x 의 위치 수 이다.
• 입력의 크기가 다양하기 때문에 normalization은 필수이다.
• Dot product와 embedded Gaussian veersion 과의 가장 큰 차이점은 활성화 기능의 역할을 하는 softmax의 존재 유무이다.

Concatenation

Concatenation은 시각적 추론을 위해 Relation Networks에서 pairwise function으로 사용된다. 또한 f 로 concatenation을 검증한다. f 식은 아래의 식 5와 같다.

식 5

• [·,·] 는 concatenation, w_f는 weight vector, normalization factor 는 C(x) = N

2.3 Non-local Block

  식 1의 non-local 연산을 non-local block으로 만들어서 많은 구조에 통합할 수 있다. Non-local block의 정의는 다음과 같다.

식 6

• y_i 는 식 1 에서 주어졌고, "+x_i" 는 residual connection으로 정의한다.
• Residual connection은 initial behavior 붕괴 없이 어떠한 pre-trained 모델에 새로운 non-local block를 삽입하도록 한다.
• Non-local block는 그림 2와 같다.
• 식 2, 3, 4의 pairwise computation은 그림 2와 같이 행렬 곱셈으로 간단하게 수행할 수 있다.
• Concatenation version 인 식 5는 straightforward(직설적) 이다.

  Non-local block의 pairwise computation은 high-level의 sub-sampled feature map에서 사용될때 가볍다. 예를들어 그림 2에서 전형적인 값은 T = 4, H = W = 14 or 7이다. 곱셈 행렬로 실행된 pairwise computation은 기존 네트워크의 전형적인 conv layer와 비교된다. 우리는 더 효율적으로 만들기 위해 다음의 implementations을 따른다.

Implementation of Non-local Blocks

  W_g , W_θ, W_φ로 나타나는 채널의 수를 x의 채널 수의 절반으로 설정한다. 이것은 Residual Learning의 bottleneck 구조를 따르고 block의 계산을 약 반으로 줄인다. 식 6의 W_z인 weight 행렬은 y_i 의 위치별 embedding과 channel의 수를 x 의 수와 일치시키는 연산을 한다. Subsampling trick은 연산량을 줄이는데 사용될 수 있다. 식 1을 아래와 같이 수정한다. x hat 은 x 의 subsampled version 이다. Pairwise 연산량을 1/4로 줄일수 있는 이것을 공간 영역에서 수행한다. 이런 trick은 non-local behavior을 바꿀수는 없지만, 연산량을 sparser(줄인다?)하게 만든다. 이것은 그림 2에서 φ 이나 g 이후에 max pooling layer를 추가해 수행할 수 있다. 

3. Video Classification Models

  Non-local 네트워크의 behavior을 이해하기 위해, video classification task에서 비교 실험을 한다. 먼저, baseline network 구조를 설명하고, 이를 3D ConvNets으로 확장하고 non-local nets을 제안한다.

2D ConvNet baseline (C2D)

  3D ConvNets과 비교해서  non-local nets의 시간적 효과를 분리하기 위해, 간단한 2D baseline 구조를 설계한다. 표 1은 ResNet-50을 backbone로 사용한 C2D baseline 이다. 시간 영역을 포함하는 유일한 작업은 pooling layer 이다. 즉, 이 baseline은 간단하게 시간 정보와 통합된다.

• Input video clip은 32 frames, 224x224 size 이다.
• 표 1의 convolution은 입력을 프레임 별로 처리하는 2D kernel 이다.
• 모델은 ImageNet으로 훈련되었고, ResNet-101 또한 같은 방법으로 구성된다.

Inflated 3D ConvNet (I3D)

  표 1의 C2D 모델을 kerenl을 팽창해 3D convolution으로 만들수 있다. 예를들어, 2D k x k kernel을 3D t x k x k 로 팽창할 수 있다. 팽창된 kernel은 ImageNet으로 훈련된 2D 모델로 부터 초기화될 수 있다(t x k x k kernel의 각 t plane은 훈련된 k x k 의 가중치에 의해 초기화 되며 1/t 만큼 재조정 된다). 만약 video가 단일 시간에서의 a single static frame으로 구성된다면, 이러한 초기화는 static frame에서 2D pre-trained model과 같은 결과를 생성한다.

  Kernel을 두가지 경우로 inflations(팽창)해 실험한다. 3x3을 3x3x3, 1x1을 3x1x1으로 팽창해 각 I3D(3x3x3). I3D(3x1x1)으로 정의한다. 3D 컨볼루션은 계산 집약적이기 때문에, 2개의 residual block마다 하나의 kernel만 팽창시킨다. 더 많은 layer를 팽창시키면 return값이 감소한다. 우리는 conv1을 5x7x7로 팽창시킨다.

Non-local network

  Non-local block을 C2D와 I3D에 넣어 non-local nets로 변형시킨다. Non-local block을 1, 5, 10개 사용한다. 

3.1 Implementation Details

Training

• ImageNet으로 pre-trained, 32 frame input clips.
• 원본인 full-length video에서 64개의 연속된 frame을 무작위로 잘라낸 다음, 다른 모든 frame을 drop(삭제?) 한다.
• Spatial size 224x224 (256x320 픽셀에서 shorter side가 무작위로 샘플된 scaled video로 부터 무작위로 crop 된)
• 8개의 GPU 사용, 각 GPU에는 8 clips의 mini-batch 사용, 총 mini batch 크기는 64 clips 이다.
• 총 400k 번의 반복을 돌렸고, learning rate는 0.01부터 시작해 150k 마다 10씩 나눠주었다(그림 4에 나타나듯이).
• momentum을 0.9, weight decay를 0.0001, 각 global pooling layer 이후에 dropout(0.5)을 사용한다.
• BN(batch norm)이 적용될 때 이를 활성화 하여 모델을 fine-tune 한다 (BN frozen).
• He[1]의 방법을 채택해 non-local block에 도입된 weight layer를 초기화 한다.
• W_z 로 제시된 1x1x1 layer 뒤에 BN layer(init zero)를 추가하고 non-local block에는 BN을 추가하지 않는다.

Inference

• Shorter side가 256으로 rescale된 video에 spatially fc로 inference를 수행한다.
• 시간적 도메인의 경우, 실험에서 전체 길이 video로 부터 10 clips을 sample 하고 개별적으로 softmax를 계산한다.
• 마지막 예측으로 모든 clips의 softmax score를 평균낸다.

4. Experiments on Video Classification

• Kinetics dataset을 사용하여 실험한다.
• 또한 모델의 일반적인 결과를 보여주기 위해 Charades dataset 도 사용한다.

4.1 Experimetns on Kinetics

  Kinetics는 246k의 훈련 video와 20k의 검증 video가 있다. 400개의 human action categories를 분류한다. 모든 모델을 training set으로 훈련시키고 validation set으로 테스트한다. 그림 4는 ResNet-50 C2D baseline과 non-local blcok 5개를 사용한 C2D의 훈련 절차 curve를 보여준 결과이다. Non-local C2D 모델이 훈련 절차를 통해 training, validation 둘다 일관적으로 C2D baseline 보다 결과가 좋다.

  그림 1과 3은 non-local block의 연산을 시각화한 예제이다. Non-local block을 사용한 네트워크는 시공간의 거리에 상관없이 의미있는 관계적 단서를 찾아 학습할 수 있다.

  표 2 는 ablation 결과를 보여주며 분석은 아래와 같다.

Instantiations.

표 2(a)는 C2D baseline에 추가된 non-local block의 신호(Gaussain, dot-product, etc.)에 대한 비교이다. Non-local block 하나만 추가해도 baseline에서 ~1%의 정확도를 향상할 수 있다. 흥미롭게도 embedded Gaussain, dot-product, concatenation 버전은 72.7 to 72.9까지 유사한 값을 나타냈다. 2.2 절에서 말한대로 Gaussain kernels을 사용한 non-local 연산은 self-attention 모듈과 비슷하다. 하지만 실험결과에서 이 모듈의 attentional(softmax) behavior은 제안하는 application의 정확도 향상 key가 아니다. 대신에, 이것은 non-local behavior이 더 중요할 가능성이 높고, instantiation에서 둔감하다.

Which stage to add non-local blocks?

  표 2(b)는 다른 ResNet에 하나의 non-local block을 추가해 성능을 비교한 결과이다. Block은 마지막 residual block의 바로 앞에 추가되었다. 그 결과 res 2, 3, 4의 경우 비슷하게 성능이 상승되었고 res 5의 경우 조금 작게 향상 되었다. 하나의 설명 가능한것은 res 5가 작은 spatial size(7x7)을 가지고, 이것은 정확한 공간 정보를 제공하기에 불충분하다. 공간 정보를 이용하는 non-local block의 더 많은 자료는 표 2(d)에서 연구된다.

Going deeper with non-local blocks.

  표 2(c)는 non-local blocks 개수에 따른 결과이다. ResNet-50과 101에 res 4에 block 1개, res4에 3개, res 3에 2개 총 5개, 모든 res 3와 res 4에 다 추가해서 총 10개해서 3가지 경우를 실험한다. 표 2(c)는 non-local block이 더 많이 추가될수록 좋은 결과를 나타내는것을 보여준다. 더 많은 non-local block이 장거리 multi-hop 통신을 수행한다는것을 논의한다. 정보는 local 모델은 할 수 없는 back이나 시공간상에서 전방의 먼 위치 사이로 전송될 수 있다. 주목할 점은 non-local block의 개선이 단순히 baseline model의 깊이를 추가한것은 아니다. 표 2(c)를 보면 non-local block 5개를 가진 ResNet-50의 정확도가 73.8%인데 ResNet-101 baseline이 73.1%이다. 하지만, 5-block ResNet-50은 ResNet-101 baseline 기준 오직 ~70%의 parameter, ~80%의 FLOPs를 가지며 또한 shallower(얕은) 하다. 이러한 비교로 non-local block이 standard 방법으로 더 깊이 들어가는것을 보완하기 때문에 성능이 향상된다고 볼 수 있다. 또한 실험에서 non-local blocks 대신 standard residual blocks을 baseline에 추가해 보았다. 이 실험에서 정확도는 상승 되지 않았다. 이러한 결과로 non-local block의 정확도 상승이 단지 모델의 깊이를 늘려서는 아니라는 것이다.

Non-local in spacetime.

  제안하는 방법은 시공간의 신호를 자연스럽게 처리할 수 있다. Video에 관련된 객체는 먼 공간과 장기적인 시간 간격으로 나타날 수 있고, 이것들의 의존성은 제안하는 모델에 capture 되어질 수 있다. 표 2(d)에서 시간, 공간, 시공간상 에서 non-local blocks의 적용 효과를 나타냈다. 공간상에서는 non-local 의존성이 오직 같은 frame에서만 일어난다. 시간상에서는 비슷하게 set-up될 수 있다. 표 2(d)는 공간, 시간상 둘다 C2D baseline보다 성능이 향상된것을 보여주지만, 시공간에서 보다는 성능이 좋지 않은것을 보여준다.

Non-local net vs 3D ConvNet.

  표 2(e)는 baseline, I3D, 확장된 3D ConvNet을 가진 non-local C2D를 비교한다. Non-local과 3D convolution은 C2D를 시간적 차원으로 확장하는 두가지 방법으로 볼 수 있다. 표 2(e)는 또한 baseline에 근거해 parameter 수와 FLOPs를 비교한다. Non-local C2D모델은 I3D 보다 더 정확한데, FLOPs는 더 작다. 이러한 비교로 제안하는 모델이 3D convolution만 사용하는것보다 효율적인것을 알려준다.

Non-local 3D ConvNet.

  위의 비교에도 불구하고, non-local operation과 3D convolution은 문제의 다른 측면을 모델링 할 수 있다(3D convolution은 local 의존성을 capture할 수 있다). 표 2(f)는 I3D(3x1x1)모델에 5개의 non-local block을 넣은 결과를 보여준다. Non-local I3D 모델은 I3D 보다 정확도가 1.6% 상승했고, non-local operation과 3d convolution이 보완적인걸 보여준다.

Longer sequences. 

  마지막으로 더 긴 input vidoes에서 모델의 일반성을 조사한다. Subsampling 없이 연속적인 128 frame을 가진 input clips을 사용한다. 표 2(g)는 128 frame clips을 사용한 결과이다. 32 frame의 결과인 표 2(f)와 비교했을때, 모든 모델이 더 긴 입력이 들어왔을 때 의 성능이 더 좋다. 또한 NL I3D가 I3D 모델보다 더 긴 sequence에서 더 잘 작동하는것을 보여주며, NL I3D가 I3D 모델에 대한 이득을 유지할 수 있다는것을 발견했다.

Comparisons with state-of-the-art results.

  표 3은 I3D와 2017 Kinetics 대회 우승 모델들, 그리고 제안하는 방법과 비교한 결과이다. 이것들이 여러 측면에서 다를 수 있는 시스템의 비교라는것에 주목한다. 제안하는 방법이 RGB, RGB+에서 모든 방법들을 능가해 큰 차이를 보였다.

4.2 Experiments on Charades

• Charades는 video dataset으로 8k 개의 training, 1.8k 개의 validaiton, 2k 개의 test를 가졌다. 
• 157개의 행동을 분류하는 multi-label classification 작업이다.
• Multi-label 속성을 처리하기 위해 범주별 sigmoid 출력을 사용한다.
• 128 frame을 사용한 Kinetics로 pre-trained 모델을 초기화 한다.
• GPU당 mini-batch size 크기는 1clip, 훈련 반복을 200k, learning rate를 0.00125로 시작해 75k마다 10씩 나누었다.
• Kinetics와 유사한 jittering 전략을 사용해 224x224 cropping window의 위치를 결정하지만, 네트워크를 fine-tune 하기 위해 cropping window 출력을 288x288로 재조정 한다. 테스트는 320 픽셀의 single scale로 한다.

  표 4는 Charades를 사용한 이전의 결과들과 비교한 결과이다. I3D baseline이 이전의 결과보다 높게 나왔고, non-local 네트워크는 테스트에서 I3D baseline 보다 2.3% 향상 되었다.

5. Extension: Experiments on COCO

  Static image recognition에서 제안하는 모델을 실험한다. Mask R-CNN baseline으로 실험한다. 모델은 COCO train 2017로 훈련되고, val 2017로 테스트된다.

Object detection and instance segmentation.

  Mask R-CNN backbone에 non-local block 하나를 추가해 수정한다. 표 5는 COCO에 대한 box와 mask AP를 나타낸다. Non-local block을 적용했을 때 정확도가 ~1% 향상 되었다. Non-local block이 모델 용량을 증가시키는데 보완한다.

Keypoint detection.

  Mask R-CNN을 사용해 keypoint detection을 한다. 4개의 non-local block을 keypoint head 부분에 추가해 실험한다. 실험은 COCO 데이터를 사용했고 그 결과는 표 6에 나타난다. Non-local block을 head에 4개 추가했을때 baseline 보다 ~1% 더 성능이 높아졌고, 여기에 backbone에 하나를 더 추가하면 성능이 ~1%더 개선되었다.

6. Conclusion

• Non-local operation으로 long-range 의존을 capture 가능한 새로운 neural network을 제시했다.
• Non-local block은 어떠한 구조와도 결합이 가능하다.
• Vidoe classification, object detection, segmentation, pose estimation 분야에서 non-local block을 모델링해 실험했고 그 결과 baseline보다 더 좋은 성능을 보였다.

Paper

He https://www.cvcoundation.org/openaccess/content_iccv_2015/papers/He_Delving_Deep_into_ICCV_2015_paper.pdf

Non-local

https://arxiv.org/abs/1711.07971