논문공부한거 | Disentangling and Unifying Graph Convolutions for Skeleton-Based Action Recognition

 Disentangling and Unifying Graph Convolutions for Skeleton-Based Action Recognition

https://arxiv.org/pdf/2003.14111.pdf

읽는 이유: 그래프 컨벌루션의 개념과 SOTA 기술을 알아보기 위해

참고하면 좋은 블로그: https://medium.com/bioai/graph-convolutional-networks-cf5d0f7b28d2 GCN 기본 개념에 대해 먼저 읽으면 좋다

Abstract

스켈레톤 기반 행동인식에서 spatial-temporal(공간-시간적?) graph 를 많이 쓴다.

그래프에서 robust한 패턴을 잡아내려면 feature 추출할 때  long-range(local에 대비되는 용어인 듯 하다) and multi-scale context aggregation and spatial-temporal dependency modeling이 중요하다.

현재 사용하는 방법의 한계점

(1) unbiased long-range joint relationship modeling under multiscale operators

(2) unobstructed cross-spacetime information flow for capturing complex spatial-temporal dependencies

이 논문의 내용

(1) a simple method to disentangle multi-scale graph convolutions and 

(2) a unified spatial-temporal graph convolutional operator named G3D

단어 뜻) aggregation: 집합, 종합

1. Introduction

이전의 (스켈레톤 기반 행동인식) 접근방식: 관절간의 상관관계를 직접 설정[42,43]하거나 러닝[31,6,48,54]함

최근의 접근방식 [50,19,34,35,32]: 관절을 노드로, 뼈를 엣지로 하는 그래프인데 그걸 시각에 따라 여러개 놓은 spatial-temporal graph를 사용("a series of disjoint and isomorphic skeleton graphs at different time steps carrying information in both spatial and temporal dimensions") (각 시각의 그래프끼리는 안 이어진 듯)

robust하게 행동인식 하려면 

1) local joint 간의 연결관계를 넘어서 multi-scale한 구조, 특성 이런걸 봐야된다. 구조적으로는 떨어져있어도 강한 상관관계를 가질 수도 있기 때문.

** "Many existing approaches achieve this by performing graph convolutions [17] with higher-order polynomials of the skeleton adjacency matrix: intuitively, a powered adjacency matrix caparXiv:2003.14111v2 [cs.CV] 19 May 2020 tures the number of walks between every pair of nodes with the length of the walks being the same as the power; the adjacency polynomial thus increases the receptive field of graph convolutions by making distant neighbors reachable." higher-order polynomial에서 이미 이해를 포기... 이 부분에서 나오는 'walk란 그래프에서의 '경로'를 말하는 것 같다... 아무튼 이러한 이전 접근 방식은 biased weighting 문제를 낳는다고 한다. 즉, undirected한 그래프에서 cyclic한 경로가 있으면 먼 노드보다 가까운 노드에의 엣지에 가중치가 편향된다고 한다. 그러면 local한 관절끼리의 정보만 많이 뽑게 되고 서로 멀리 있는 관절 사이의 정보는 거의 못 뽑게 된다는데... 이해X

2) "the ability to leverage the complex cross-spacetime joint relationships for action recognition" 그러니까 시간+공간에서의 관절 사이 관계를 잘 사용해야 한다..?

이전의 접근 방식에서는 시간에서만, 혹은 공간에서만 사용되는 모듈을 썼다. 대표적인 접근방법으로, 각 시각에서 스켈레톤의 공간적 관계성을 추출하기 위해 일단 그래프 컨벌루션을 쓰고, 그 다음에 시간적 정보를 1D 컨벌루션이나 recurrent 컨벌루션을 사용해서 추출하는 것(factorized 3D convolution을 설명하는 듯하다). 그렇게 하면 long-range 한 modeling에는 효과적이지만 >시간, 공간적인 정보 흐름을 방해<하므로 >>복잡한 지엽적 시공간적 관절 의존성<<을 추출하기는 힘들다. 예를 들면, 일어나는 행동은 상체와 하체의 움직임이 동시에 일어나는데, 상체의 움직임(앞으로 숙이기)이 하체의 >미래< 움직임(일어나기)에 강하게 연관되어 있다. factorized 모델링 방식으로는 이런 행동을 예측하기가 힘들다.

이 논문에서는:

1) 편향된 가중치 문제 "biased weighting problem" 해결. 멀거나 가까운 관절들 간의 불필요한 의존성을 제거함으로써, multi-scale aggregation을 통해 feature를 'disentangle' 한다. (이해 X) 그러면 관절들 사이의 거리와 상관없이 관계성을 모델링할 수 있는 강력한 multi-scale operator를 만들 수 있다.

2) 시간+공간상의 관절 의존성을 >>직접적으로<< 모델링할 수 있는 새로운 시공간 그래프 컨벌루션 모델을 제안한다. 이름은 G3D이다. 그니깐 '3차원'의 시간+공간 영역에서 그래프 엣지들을 만들어서 정보 흐름을 만들고, (잠재적으로) 시공간적 feature를 러닝할 수가 있다는 것.

3) 이 두개를 합쳐서 MS-G3D라고 부르겠다 이것이다...

단어 뜻) leverage: 영향력; 지레[의 작용]; 영향을 주다; ...에 지레를 사용하다

deploy: (군대, 무기를) 배치하다; 효율적으로 사용하다

2. Related Work

2.1 Neural Nets on Graphs 그래프에 뉴럴넷 적용

Architectures 구조

보통 GNN(Graph Neural Networks)을 씀.

Spectral GNN: 인풋 그래프 신호를 '그래프 푸리에 영역'에서 컨벌루션함. eigendecomposition을 해야 하고, adjacency가 고정되어있다고 가정하기 때문에, conputational efficiency와 새로운 그래프에의 generalizability에 한계가 있음.

Spatial GNN: 각 노드에서 레이어마다 업데이트를 함. 이때 layer-wise 업데이트 규칙은(중요!):

(1) neighborhood function을 통해 이웃을 고름
(2) 고른 이웃과 자기 자신의 feature들을 aggregation function들을 사용하여 aggregate함
(3) aggregate한 값에 activation 적용

이러한 GNN 중에서 Graph Convolutional Network(GCN)이 localized spectral convolution의 1차 근사로써 처음 도입되었는데 mean neighborhood aggregator로써의 simplicity가 어쩌구 웅앵웅 spatial-GNN baseline으로 여겨지게 되었다. 이 논문은 GCN의 layer-wise update rule을 적용한다.

Multi-Scale Graph Convolutions. 멀티스케일 그래프 컨벌루션.

(multi-scale이라 함은 local한(이웃인) 노드뿐만 아니라 non-local한 이웃에 대해서도 feature를 추출한다는 뜻인 것 같다.)

이전에는 멀티스케일 spatial GNN으로써 아까 말한 graph adjacency 행렬의 higher order polynomial을 사용하여 먼 곳의 feature를 aggregate했음. 비슷한게 어쩌구 웅앵웅 여러개 있음. 그러나 저자는 지금 이러한 알고리즘들이 weighting bias 문제가 생긴다고 주장하는 바임.

2.2. Skeleton-Based Action Recognition 스켈레톤 기반 행동인식

초기의 접근법: feature, joint relationship을 hand-craft 했었는데 그러면 인간 몸의 semantic한 연결성을 무시하게 된다. 최근에는 Spatial-temporal graph를 만들고 GNN으로 시공간적 관계성을 직접적으로 모델링하여 성능 향상을 보았다.

ST-GCN은 spatial  graph  convolutions  along  with  inter-leaving temporal convolutions are used for spatial-temporal modeling하다. (깃헙보면 이 문단에서 함께 언급된 AS-GCN, STGR, 2s-AGCN, DGNN 중에 이걸 기반으로 된 것들이 많다는걸 알수 있을 것임. 이 논문의 MS-G3D도 마찬가지임. 몇 주 전에 https://github.com/niais/Awesome-Skeleton-based-Action-Recognition#2015 이 글을 봤을 때는 얘네가 다 SOTA였고 이 논문이 가장 성능이 좋았던 걸로 기억함) 추가로 GR-GCN도 있는데 이거랑 이 논문의 차이점은 그냥 안읽겠음

3. MS-G3D

3.1. Preliminaries

Notations.

스켈레톤은 라고 쓰기로 한다(이하 G).

이때 (이하 V)는 관절=노드의 집합, 는 뼈=엣지의 집합으로,(이하 E) adjacency matrix  (N×N행렬) 로 나타낼 수 있음(이하 A).

(adjacency matrix란 노드 에서로 가는 엣지가 존재하면 가 되고 아니면 0이 되는 행렬)

이때 G가 undirected하므로 A는 대칭이다.

행동은 그래프 시퀀스(graph sequence)로 나타내는데, node feature set을 가지고있다.

node feature set은 인데,

feature tensor set 으로 나타난다.

이때 은 총 프레임 중, 시각 에서 관절 에 대한 차원짜리 feature vector이다. t는 시각, n은 관절 인덱스라는 것만 알면 되겠다! x는 C차원짜리 벡터이고!!!

그러니까 텐서의 크기가 T(총 프레임 수)×N(총 관절 수)×C(feature의 총 차원 수) 가 되는 것.

이때 인풋은 구조적으로는 (각 시각 t에서) A가 되는 것이고, feature적으로는 가 되는 것.

네트워크 각 레이어 에서의 (앞으로 학습시킬!) 가중치들을 라고 부르자.

GCNs.

위에서 정한 notation들과 같이, feature는 X고, 그래프 구조는 A이다. 위에서 언급한 것처럼 레이어마다 업데이트되는 규칙을 사용한다고 하면 이렇게 된다

Eq 1:

 

time t에서의 feature만 고려했을 때의 식이다.

(*) : 로, self-loop를 추가하여 노드가 자기 자신과 이어져있다고 치는 것이다. (I는 모든 노드에게 self-loop가 존재하고 다른 엣지는 없는 adjacency matrix다) 이 포스트 위 링크의 블로그에서 보니까 "자기 자신의 정보를 이용하기 위하여"라고 한다.

는 의 "diagonal degree matrix" 로, 각 노드의 엣지 수(=degree)를 diagonal amtrix로 나타낸 것이다.

이러면 는 approximate spatial mean feature aggregation from the direct neighborhood가 된다고 하는데, 왜 그런지 아직은 잘 모르겠다. 일단은 공간 영역에서 이웃하는 노드의 feature를 평균종합(?) 하는 거라고 생각하고 넘어가기로 한다.

3.2. Disentangled Multi-Scale Aggregation

Biased Weighting Problem.

이때 기존의 접근은 higher-order polynomial을 사용하는데, 그러면 식이 이렇게 된다.

Eq 2:

사람을 가장 집에 가고 싶게 만든다는 수학기호, 가 등장한다. 

다시 하나씩 살펴보자. K는 내가 aggregate 하고자 하는 scale(노드 간 거리의 최댓값?)이다.

는 A의 Normalized form으로, 를 쓰거나 를 쓰는 논문이 있고, GCN에서는 단순히 로 일반화하여 사용할 수 있다. 

(근데 뭘 normalize 했다는 걸까? 아마 최댓값이 1이 되도록 했을 것이고...?? ???

여러 글을 봐도 잘 모르겠으니 일단  ...)

우리는 인접한 노드뿐만 아니라 거리가 2, 3, ..., K인 노드까지도 aggregate 하고 싶다.

인접한 노드만 aggregate하려면 그냥 adjacency matrix를 사용하면 되지만, 거리 2, 3, ... K인 노드들은 어쩌나? 그래서 A를 자승해준다.

그러면! 는 노드 i와 노드 j 사이의 k짜리 길이의 경로의 갯수라고 볼 수 있다.

그러므로 는 길이가 k인 경로들의 수만큼() 가중치를 준 feature average라고 볼 수 있다. 거기에 가중치 를 곱하고, 그걸 경로길이 k가 0(자기 자신만)부터 K(닿고자 하는 최대로 먼 길이)까지를 다 더한 뒤, 액티베이션을 해주는 것.

그런데 이때 cyclic 한 경로가 존재한다면, k개의 엣지만큼 떨어진 이웃노드의 수보다 길이 k의 경로의 수가 훨씬 많을 것이다. 그렇다면 (그 cyclic한 경로 안에서의?) 가까운 노드들은 가중치가 커질 것이고, 또 degree가 큰(이웃이 많음) 노드들도 가중치가 커질 것이다. 잠깐, self-loop도 cyclic한 경로니까, 더 가중치가 커질 것이다.

(self-loop은 표시되지 않았음) 

A~2를 보면, 노드 1에서 거리가 2인 노드 3, 5, 6이 거리가 1인 노드 0, 2, 4보다 가중치가 작다(self-loop가 있어서 가능하다). A~3에서도 노드 1에서 거리가 3인 노드 7의 값이 거리가 1인 노드들에 비하면 한참 작고, 거리가 2인 노드들보다도 작다. 가까이 있는 노드일수록 가중치가 커지는 것이다.

나는 그냥 멀리 있는 노드들도 aggregate 해주고 싶을 뿐인데... 가까이 있는 노드들끼리만 가중치가 쎄지게 된다...

Disentangling Neighborhoods.

그러니까 거리 k인 노드들을 나타내기 위해 가 아니라 k-adjacency matrix 를 새로 정의한다.

Eq 3:

이고,

이때 는  사이의 최단거리이다.

두 노드 사이의 거리가 k이면 1이요, 아니면 0이다.

단, self-loop 포함. 이는 해당 노드와 거리 k의 이웃 사이의 >관계성<을 파악하기 위해 필요하고, 또 "keeping each joint’s identity information when no k-hop neighbors are available"하다고 한다. 현재로서는 identity information이 무슨 뜻인지 잘 모르겠다.

아무튼 N(전체 노드 수)이 작으면 이 행렬은 쉽게 계산 가능하다. 이렇게.

자 이제 Eq2는 이렇게 바뀌었다.

Eq 4:

노란 부분만 저 식대로 바뀐거다. 그러면 어떻게 되냐면,

이렇게 해당 거리에 있는 노드만 표시하게 된다. A~(3)을 보면 노드 1에서 경로 3인 노드 7 말고는 다 0이 됨을 알 수 있다. 가까운 노드에 추가적인 가중치를 주지 않음으로써 이제 k가 커져도 long-range modeling을 효과적으로 할 수가 있다. 또한 이 k-adjacency matrix들은 이전의 polynomial로 나타낸 행렬보다 훨씬 sparce하므로 효율적으로 나타낼 수 있다(sparce matrix 등을 사용하기에 더 좋다는 뜻인 것 같다)

3.3. G3D: Unified Spatial-Temporal Modeling

여태까지는 공간 영역에서만(spatial-only) 혹은 시간 영역에서만(temporal-only) feature를 추출했지만, 저자들은 그렇게 factorize하면 시공간상에서의 관절 관계를 알아내는 데에 비효율적이라고 주장한다. 

두 개의 노드 사이에 강한 연결이 존재한다고 하자. 그러면 매 레이어에서 업데이트할 때마다 서로의 feature를 많이 반영하게 될 것이다. 그러나 local aggregator(GCN, TCN 둘 다)를 여러 번 통과하면서 점점 커지는 시공간적 receptive field로부터 불필요한 정보까지 aggregate되다 보면 서로의 정보는 약해진다. (??????) 예를 들어, GCN이 각각의 이웃들을 구별하기 위해 weighted aggregation을 하지 않는다는 것만 봐도 알 수 있다 (????) ?? 이 부분은 아예 이해가 안 가서 해석만 써놓음

Cross-Spacetime Skip Connections.

이러한 문제를 해결하기 위해 저자들은 cross-spacetime skip connection을 제안한다.

보통 skip connection 하면 ResNet을 떠올리게 된다. 한 레이어(혹은 여러 레이어들의 블럭)의 아웃풋과 인풋을 더하여 다음 레이어 인풋으로 쓰는 것이다.

여기서는 spatial-temporal graph에서 cross-spacetime(시간축과 공간축을 넘나드는?) 엣지를 미리 모델링한다고 한다. 벌써 뭔 소린지 모르겠지만 아직 멈추면 안 된다. 뭔 소린지 모르는 게 한 페이지 반 정도 더 남았기 때문이다. 꾹 참고 보다보면 이해가 갈 것이다.

spatial-temporal graph로 된 인풋 그래프 시퀀스가 있다. 이제 이 시퀀스에 크기 τ만큼의 sliding window가 있다고 하자.

(직접 그렸는데 맞는지는 모르겠음.) 이 윈도우는 시간축을 따라서 움직일 수 있다.

그러면 이 윈도우는 각 시각에서 spatial-temporal subgraph 를 가지게 된다. 이때  즉 τ 프레임 각각에서의 그래프들의 합집합이다. 

는 initial edge set으로, 이렇게 정의된다.

Eq 5:

가 N×N 행렬이므로(여기서 N은 노드 수), 는 그걸 τ×τ로 tile한 τN×τN짜리 행렬이 된다.

의 i,j번째 원소인 submatrix 는 (i번째 프레임의 그래프)의 모든 노드들이 자기 자신과 j번째 프레임에서의 1-hop spatial neighbor와 연결되어있다는 뜻이다.

어떻게? 각 프레임에서의 공간적 연결성(=의 i,i번째 원소)를 시간 영역으로 extrapolate함으로써...

?????????????????????????

Thus, each node within  is densely connected to itself and its 1-hop spatial neighbors across all τ frames.

????????????????????????????

????????????????????????????????

인접행렬의 경우에는 위와 같고, feature도 같은 sliding window를 에 사용하여 얻을 수 있다.

이때 (아마 temporal 한 방향으로?) zero-padding을 사용한다. (T가 전체 프레임의 수니까, T개의 윈도우를 적용하려면 padding이 필요할 것이다.)

이제 Eq 1을 사용하여 unified spatial-temporal graph convolutional operator를 얻을 수 있다.

(Eq 1:

 )

t번째 temporal window에서:

Eq 6:

Eq 1에 그냥 대입만 한 것 같다.

Dilated Windows.

위 방법처럼 윈도우를 만들면 프레임들끼리 인접할 필요가 없다.

이를테면 윈도우가 τ개의 프레임을 포함하고 dilation rate이 d가 되는 'dilated window'를 만들 수 있다.

똑같이 를 쓰는데, 프레임을 d 프레임마다 하나씩 τ개 골라서 만들면 된다.
같은 방식으로 feature도 (d 표시 없으면 d=1이라고 친다)를 얻을 수 있고, Eq 6을 따라서 layer-wise update를 해주면 된다.

이러면 의 크기를 늘리지 않아도 시간적 receptive field를 늘릴 수가 있다.

dilated convolution 참고.

Multi-Scale G3D.

Eq 6을 아까 만들었던 multi-scale aggregation scheme과 합치면 MS-G3D가 된다.

Eq 7:

아까 multi-scale할 때 만들었던 , 처럼 똑같이 , 를 만들면 끝이다.

정리하자면, 1) long-range aggregation을 위해 k만큼 멀리 있는 노드들까지 시그마로 더해주는데, 이때 기존 polynomial 방법 대신 k-hop neighbor 인접행렬을 쓰고, 2) 시공간적 연결을 동시에 고려하기 위해 sliding window를 통해 cross-spacetime+dilated skip connection을 사용한다는 것이 핵심인 듯하다.

Discussion.

(1) spatial-temporal receptive field가 τ, d, A~인 3D 컨벌루션 블록과 비슷하다고 볼 수 있다.

(2) 3D 컨벌루션과 다르게 G3D에서는 의 파라미터 수("parameter count'?)는 τ나 𝓔(τ)와 독립적이다. 그래서 τ가 크더라도 오버피팅의 위험이 적은 편이다.

(3) τ가 크면 temporal receptive field는 커지지만, immediate neighbor의 크기가 커지기 때문에 generic한 feature들을 잃게 된다. 즉, dense한 cross-spacetime connection은 τ에 대해 trade-off가 있다.

추가적으로, τ가 크면 는 quadratic하게 커진다. 그래서 multi-scale aggregation도 더 많은 연산이 필요하다. 반면에, dilation d가 커지면 temporal receptive field는 커지지만 temporal resolution은 떨어지게 된다. 따라서 τ와 d를 잘 조정해야 한다.

(4) G3D 모듈은 복잡하고 지엽적인(regional) spatial-temporal을 잡아내도록 설계되었다. long-range dependency는 factorized module이 더 효율적으로(?economically) 잡아낼 수 있다. 그래서 다음 섹션에서 얘기할 long-range, factorized 한 모델로 augment되었을 때 G3D가 가장 좋은 성능을 낸다는 걸 알 수 있었다. 이해가 안 가니까 그냥 다음 섹션을 보면 된다.

3.4 Model Architecture

Overall Architecture. 전반적인 구조

최종적인 모델 생김새는 다음과 같다.

집에 가고 싶어지는 그림이다. 하지만 나랏돈으로 공부하면서 이런 걸로 집에 가겠다고 떼를 쓰면 안 된다. 차근차근 살펴보자.

일단 전체 구조는 이렇다.

인풋인 스켈레톤 시퀀스는 먼저 r개의 spatial-temporal graph convolutional (STGC) 블록들을 통과하면서 feature를 뽑힌다.

뽑은 feature를 global average pooling하고, softmax classifier(FC + softmax)를 통해 행동을 분류한다. (global average pooling은 내가 이해하기로는 각각의 feature map을 평균내는 것이다. 채널마다 값이 1개씩 나오는 거.)

각각의 STGC 블럭은 두 개의 pathway를 가지고 있다. 복잡하고 지엽적인(regional) spatial-temporal 상관관계를, 하나는 long-range spatial-temporal 의존성(내가 보기엔 correlation이나 dependency나 그게 그거 같은데, 왜 구별해서 썼는지 모르겠다.) 을 동시에 잡아내기 위해서다.

(1) G3D pathway는

a. spatial-temporal 윈도우를 만들고

b. disentangled multi-scale graph convolutions을 수행한 뒤,

c. 그걸 다시 FC에 통과시켜서 윈도우 feature를 해독한다.

저기 점선으로 되어있는 추가적인 G3D pathway는 뭐냐면, τ와 d를 달리하는 G3D pathway를 여러 개 넣어서 여러가지 spatial-temporal context를 학습시킬 수도 있다는 뜻이다.

(2) factorized pathway는 long-range, spatial-only, and temporal-only modules로 G3D pathway를 보강한다.

a. 첫 번째 레이어: a multi-scale graph convolutional layer capable of modeling the entire skeleton graph with the maximum K

b. 두 번째 & 세 번째 레이어:  two multi-scale temporal convolutions layers to capture extended temporal contexts (discussed below)

The outputs from all pathways are aggregated as the STGC block output, which has 96, 192, and 384 feature channels respectively within a typical r=3 block architecture. Batch normalization [14] and ReLU is added at the end of each layer except for the last layer. All STGC blocks, except the first, downsample the temporal dimension with stride 2 temporal conv and sliding windows.

그렇다고 한다.

Multi-Scale Temporal Modeling.

이거랑 다음문단 끝나면 4. Experiments인데 거기는 영어로 보기 편하니까 해석 옮기지 않겠음....