(작성중)[Paper] Geometric deep learning: going beyond Euclidean data

이 논문을 정리한 포스트입니다.

Geometric deep learning: going beyond Euclidean data,
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, P. Vandergheynst, IEEE Signal Processing Magazine 2017


ABSTRACT

많은 데이터들이 Non-Euclidean 공간의 구조로 존재한다. 예를 들면, 소셜네트워크, 센서 네트워크, 뇌 영상의 functional 네트워크, Genetic Regulatory Network(GRN), 컴퓨터 그래픽의 meshed surface이 Non-Euclidean data이다. 보통 이런 데이터들은 크고 복잡한데, 이럴때 딱인게 머신러닝이다. 특히, 크고 복잡한 데이터에 대해 딥러닝을 흔히 사용하는데, 여태까진 주로 컴퓨터비젼, 자연어처리, 음성신호 분석들에 대해서 사용되어왔다. 그러나 대부분 Euclidean 또는 grid-like 구조의 데이터에 대해 성공적으로 적용되어 왔다. GDL은 딥뉴럴 모델을 non-Euclidean 도메인(그래프 또는 manifold)에 적용하기 위한 테크닉을 통틀어 칭한다.

INTRODUCTION

기존의 딥러닝 흥행은 많이 알려져있다. 음성인식, 번역, 컴퓨터비젼, 등등…. 이제는 제품으로도 많이 나오고 있는데, 이런 흥행의 비결중 하나는 딥러닝이 데이터의 statistical properties를 잘 이용하는 것이다. 여기서 말하는 statistical properties란, 1. stationarity, 2. compositionality through local statistics 를 말한다. 이러한 특성들은 이미지, 비디오, 스피치에 존재한다. 이미지를 Euclidean space의 grid상의 function으로 본다면(CV강의에서도 이미지를 함수라고 본다.), stationarity는 shift-invariance로 볼수있고(convolution을 돌리기 때문에 몇 픽셀씩 움직여도 같은 이미지이다. 어떤 패턴으로 이루어져있는지가 중요하다.), compositionality는 grid가 갖는 multi resolution 구조에 기인한다(점이 모여 선, 선이 모여 곡선, 이런식으로 모여서 눈,코,입,귀 등 특징을 이룬다). 이는 CNN구조에서 잘 이용해먹는데, filter를 평행 이동해가며 convolution연산을 하는것은 stationarity, pooling layer같이 down sampling하는 것은 compositionality를 잘 이용한다고 볼 수 있다.
CNN은 크게 두가지 장점을 갖는다. 첫번째는 local feature 들을 뽑아내는데, 이미지 도메인간에 어느정도 공유하기때문에 그냥 MLP보다 깊이대비 파라미터 수가 적다. (따라서 오버피팅 위험도!) 두번째는 Convolution 구조 자체가 데이터에 대한 어떤 prior을 두는데, 이것이 natural image에 특히 아주 적합하다.

근데 이렇게 CNN이 잘나가는 Euclidean domain의 데이터 말고, 요새는 non-Euclidean domain의 데이터에도 관심이 늘고 있다. 예를 들면, 소셜네트워크에서 유저가 갖는 특성은 소셜그래프의 vertice의 신호로 모델링 될 수 있고[22], 센서 네트워크는 센서들(시간에따른 신호를 갖는 vertice)이 퍼져서 연결되어 있는 그래프 형태의 네트워크고, 신경과학에서는 뇌의 기능적, 해부학적 특성을 나타내기 위해 그래프 모델이 사용된다. 유전학에선, Genetic Regulatory Networks(GRN)상에서 유전체 발현 데이터가 시그널로 모델링 된다[23]. 컴퓨터 그래픽, 비젼에서는 3D object가 색,질감등의 특성을 갖는 Riemannian manifold(surface)로 모델링 된다.

non-Euclidean 데이터는 global parameterization, common system of coordinate, vector space structure, shift-invariance같은 특성들이 없다. 결과적으로, 기존에 잘먹히던 Convolution 연산은 여기선 잘 안먹힐 수 있다. 그래서 이 논문에서는, 어떻게 non-Euclidean 데이터에도 CNN같은것의 성공비결을 잘 먹히게 만들지 보여준다.

GEOMETRIC LEARNING PROBLEMS

GDL이 해결할 문제점을 두가지로 구분한다. 첫번째는 데이터의 구조를 잘 정의하는 도메인에 대한 이해이고, 두번째는 non-Euclidean 데이터가 주어졌을때 적절한 analyzing function을 다루는 도메인을 다루는 함수에 대한 이해이다. 도메인에 대한 이해도메인을 다루는 함수에 대한 이해 두가지가 서로 연관이 있다. 도메인 상에서 정의된 함수를 이해하는 것은 그 도메인에 대한 어떤 정보를 전달할 것이고, 또한 반대로 도메인의 구조가 함수에 어떤 특성을 부여할 것이기 때문이다.

Structure of the domain:

저차원의 구조의 데이터 셋이 고차원의 Euclidean space로 임베딩 된다고 하자. 이때, 저차원구조를 복원하는 것은 manifold learning, 또는 non-linear dimensionality reduction으로 알려져있다. (예를 들면 Auto Encoder에서 보면 인풋과 아웃풋이 고차원의 Euclidean space고, hidden layer가 저차원 구조이다.) 이런 방법들은 두가지 스텝으로 이루어져있는데,
첫번째는 데이터 포인트들의 local affinity(지엽적인 유사도)의 representation을 구축하는것부터 시작한다.(주로 sparsely connected graph)
두번째로 데이터 포인트들의 원본 유사도(affinity)를 보존하면서 저차원으로 임배딩한다.
예를들면, spectral embedding은 포인트들을 주변을 커넥션들로 맵핑한다. MDS-type[26] 방법은 그래프의 geodesic distance같은 전체적인 정보를 보존하면서 임배딩한다. t-SNE[28]방법은 t-distribution을 이용하여 high dimension 에서의 similarity score을 측정하여 row dimension에서도 같은 similarity를 갖도록 임베딩한다. Laplacian eigenmap[29]은 graph Laplacian과 Laplace Beltrami operator을 이용하여 임베딩한다. diffusion map[30]은 Markov matrix의 eigenfunction을 이용하여 복잡한 데이터구조를 임베딩한다. DrLIM[31]은 인풋 스페이스에서 어떠한 거리도 측정할 필요 없이, 주변과의 관계를 통해 임베딩하는 학습 방법이다. 여기에 용수철비유 등이 나온다. [32-34] 에서는 word embedding 을 graph로 하는 시도도 있었다.
데이터가 manifold나 graph로 주어진 경우엔 위에서 말한 affinity structure을 만드는 첫번째 과정이 불필요하다. [38,39]예를들어, 컴퓨터 그래픽이나 비젼에서는 3D shape을 local geometric descriptor을 이용해서 mesh로 표현할 수 있다. [40]전산 사회학같은 네트워크 분석에서는, 사람들간의 관계를 표현한 그래프를 이용해서 사람들을 분류하거나 communities를 찾아낼 수 있다. [41]자연어처리에서는 co-occurrence 정보를 edge로 이용하여 corpus를 표현할 수 있다.

Data on a domain:

두번째로 다룰 문제는, 이러한 non-Euclidean domain에서 정의된 분석 함수에 대한 것이다. 이 문제를 두가지의 하위클래스로 더 나눠보면,
첫번째로는, domain이 고정되어있거나 multiple domain이 주어지는 경우다. [42]예를들어, 소셜네트워크에서 유저의 지리적인 좌표를 얻었다고 가정하자. 이것은 소셜네트워크 상에서 time-dependent한 노드의 신호로 표현된다. 이런 데이터(location-based social network)의 주요 어플리케이션은 사용자의 과거 행동을 보고 사용자뿐만 아니라 친구의 다음 위치까지 예측하는 것이다. 이 문제에서 domain (social graph)는 고정되었다고 가정한다. [43]에서 리뷰한 방법이 이런 설정에 (특히, spectral domain에서 convolution 같은 연산을 하기위해서) 사용될 수 있다. 이 방법은 [44,45]에서 그래프 위에서도 CNN을 돌릴수 있게 해준다.
두번째로는, 컴퓨터 그래픽 또는 비젼에서 shape간의 similarity나 correspondence를 구하는 것이다. 각 shape은 manifold로 모델링되어있고, 여러 도메인에서 작업해야한다. 이런 설정에서는 local charting을 이용하여 spatial domain에서 convolution하는 [46-48]논문이 적합하다.

Brief history:

본 리뷰논문에서는 위에서 언급한 GDL의 두 종류의 해결과제 중 Structure of the domain보다는 Data on a domain(도메인을 다루는 함수에 대한 이해)에 대해서 주로 다룬다. 즉, non-Euclidean domain에서 CNN을 적용하기 위한 학습함수에 대해서 다룬다.
Graph : Graph에 뉴럴넷을 적용하려고 한 첫 시도는 scheme combining RNN과 random walk model을 제안한 [49]이다. 이 논문은 거의 주목받지 못했으나, 최근들어 딥러닝과 결합[50,51]하면서 관심받고있다. Graph에 처음으로 CNN을 수식화하여 적용한 것은 [52]다. spectral domain상에서 convolution을 정의하여 사용하였다. 그러나 이 논문은 개념적으로는 중요하지만 컴퓨팅관점에서의 단점때문에 유용하진 못하다. 이런 단점을 [44]와 [45]에서 극복하였다.
Vision : 컴퓨터비젼 그래픽에서도 딥러닝을 적용하고자 하는 노력이 있었는데, [47]논문은 meshed surface에서 CNN을 돌리려는 첫 시도였다. 이 논문에서는 local intrinsic patch에 기반한 convolution연산의 공간적 정의를 이용하였다. 여러 어플리케이션중에, deformable한 3D shape에서 correspondence(동일점)를 찾는 테스크에서 state-of-the-art(SOTA)를 달성했다. 후속연구들에서는 intrinsic patch를 다른방법으로 구성하여 적용했다. [53,48]에서는 point cloud에서, [54]는 일반적인 graph상에서 연구하였다.

graph나 manifold에 딥러닝을 적용하고자 하는 연구는 늘어나고 있으며, 생화학[55], 추천시스템[56] 등에서도 많은 시도가 이루어지고 있다. 그러나 각각의 분야마다 서로 쓰는 용어와 개념이 다르기 때문에 처음 접근하는 사람에겐 다소 어려울 수 있다. 그래서 이 논문에서 정리를 하고자 한다.

Structure of the paper:

Section III에서는 기존의 Euclidean deep learning에서의 데이터에 대한 가정과 그것이 어떻게 CNN에서 실현되는지를 대해 살펴본다. (CNN에 대한 더 딥한 리뷰는 [12],[1],[13] 에 있다.)
Section IV에서는 non-Euclidean에 대해 다루기 시작한다. differential geometry와 graph theory에 대한 기본적인 개념에 대해 정의한다. 이런 주제는 신호처리 학계에서도 잘 알려져있지않고, 산업에서도 통합적으로 다루는 것이 없다. 우리의 목표는 전통적인 신호처리 관점에서 전반적으로 이해할 수 있도록 하는 것이다.
Sections V–VIII에서는 GDL의 흐름에 대해서 다룬다. Euclidean 딥러닝 과 non-Euclidean 딥러닝의 차이점과 공통점을 비교하면서 서술한다. 가장 핵심적인 차이는 graph와 manifold에 대해서 convolution-like 연산을 정의하는 방법들이다. 첫번째 방법은 Convolution Theorem 을 이용하여 spectral domain에서 convolution연산을 정의하는 것이고, 두번째 방법은 convolution을 spatial domain상에서의 template matching으로 생각하는 것이다. 그러나 이 두가지 방법의 구분은 사실 명확하진 않다. 앞으로 살펴보겠지만, 어떤 연구는 spectral domain에서 공식을 이끌어내지만, 결국엔 spatial domain에서 필터를 적용하는 것으로 귀결된다. 두가지 방법을 혼합해서 사용 할 수도 있다. wavelet이나 window Fourier transform같은 spatio-frequency 분석기법을 이용하는 접근을 통해 가능하다.
Section IX에서는 네트워크분석, 입자물리학, 추천시스템, 컴퓨터비젼, 그래픽 등에서의 예시를 몇개 추려서 본다.
Section X에서는 현재의 해결과제들과 GDL의 잠재적인 연구방향들에 대해 다룬다.

DEEP LEARNING ON EUCLIDEAN DOMAINS

Geometric priors

square-integrable function $f \in L^2(\Omega)$ 이 정의된 compact $d$ 차원 Euclidean domain $\Omega = \left[ 0,1 \right]^d \subset \mathbb{R}^d$ 를 보자. (예를 들어, 이미지는 unit square $\Omega = \left[ 0,1 \right]^2$ 의 함수로 생각될 수 있다.) 일반적인 지도학습을 보면 학습 데이터셋에 대해 unknown function $y:L^2(\Omega) \rightarrow \mathcal{Y}$ 을 찾는다.

classification의 경우엔 target space $\mathcal{Y}$가 discrete한 클래스가 된다. multiple object recognition의 경우엔 $\mathcal{Y}$를 posterior class probabilities $p(y x)$ 인 $K$-dimensional simplex로 둘 수 있다. Regression에서는 $\mathcal{Y} = \mathbb{R}^m$ 이다.

대부분의 컴퓨터비젼과 음성분석 테스크에서, 우리는 unknown function $y$에 대해 중요한 가정을 한다. 뒤에서 설명하는대로, 이러한 가정은 CNN구조에서 효과적으로 써먹을 수 있다.

Stationarity

function $f \in L^2(\Omega)$에 대해 tranlation operator를 아래와같이 정의하자.

첫번째 가정은 function $y$가 invariant 또는 equivariant 하다는 것이다. invariant 하다는 것은 어떠한 $f \in L^2(\Omega)$와 $v \in \Omega$에 대해서도 $y (\mathcal{T}_vf) = y(f)$가 성립한다는 것이다. 예를 들면, image classification에서 고양이 image $f$ 가 $v$만큼 translation 하더라도, 똑같이 $y$는 고양이 라는 클래스라는 의미다. equivariant 하다는 것은 $y (\mathcal{T}_vf) = \mathcal{T}_vy(f)$를 의미한다. 즉, image segmentation이나 localization 등에서 image $f$가 $v$만큼 translation하면 segmentation mask 또는 localization box $y$ 또한 $v$만큼 translation한다는 의미다. 이러한 정의들은 기존 신호처리나 자연어 등에서 사용되는 invariant, equivariant의 의미와는 혼동되지 않도록 해야한다.

Local deformations and scale separation

위와 비슷하게, smooth vector field $\tau : \Omega \rightarrow \Omega$ 에서의 deformation $\mathcal{L}_\tau$ 는 $L^2(\Omega)$에서 아래와 같이 작동한다.

Deformation $\mathcal{L}_\tau$는 local translation, change of point of view, rotation, fequency transposition등으로 볼 수 있다. 컴퓨터 비젼에서 수행되는 task들은 대부분 translation invariant/equivariant 할 뿐만 아니라 local deformation에 대해 stable하다. translation invariant하다는 것은 모든 $f,\tau$에 대해 아래와 같다.

여기서 $\Vert \nabla \tau \Vert$ 는 deformation field 에서의 smoothness의 지표다. 다시말하면, input image가 약간 deformed 되었어도 예측량은 그만큼 변하지 않는다는 의미다.