[CVPR23] DeepGraph : Towards Any Structural Pruning

Abstract (Motivation)

현대 딥러닝 모델들은 다양한 module (layer)가 결합되면서, 점점 많은 계산 비용을 유발한다는 문제가 있다. Pruning은 이를 위해서 중요도가 낮은 parameter를 제거 또는 0으로 만드는 기법이며, 그 접근 방식에 따라서 Structural Pruning과 Unstructural Pruning으로 나누어볼 수 있다.

Structural Pruning은 structurally-grouped parameters를 Neural Networks에서 완전히 제거하는 것이다. 하지만 이 방법은 Architecture의 다양성 (e.g. CNNs, Transformer) 때문에, unified protocol을 만들기 어렵다는 한계가 있다.

이 논문은 문제의 해결책을 any structrual pruning이라고 정의하며, 이를 위해 DepGraph (Dependency Graph)를 제안했다는 점에서 의의가 있다. DepGraph는 인접한 (between) layer 뿐만 아니라, 전체 schema를 고려해 자동으로 중요도가 낮은 Pruning 대상을 선택한다.

Introduction

Pruning은 redundant parameters를 network에서 제거함으로써 model inference에서 가속화 및 경량화를 의미하며, 다음과 같이 분류할 수 있다. :

Structural Pruning : Grouped-parameters를 제거함으로써, 물리적 구조를 간소화한다. (e.g. Learned sparsity, Efficacy of various criteria, Channel Pruning)
Nonstructural Pruning : Low-important weight를 zero(0)**로 바꿈으로써 물리적 구조를 유지한다. (e.g. Magnitude-based, Gradient-based)

Structural Pruning은 Nonstructural Pruning과 비교했을 때, network의 본질적인 구조를 간소화 하므로 더 범용적인 접근 방식으로 여겨지고 있다. (Unstructural은 specified accelerator 필요)

하지만 deep-neural networks는 정말 많은 수의 모듈의 집합체이기 때문에 (e.g. Convolution, Normalization, Activation), 인접하지 않더라도 전체 schema의 관점에서 바라봤을 때는 복잡한 연결성을 가지는 경우가 많다. 그런데 문제는 지금까지 연구는 case-by-case analyses (effort-consuming) & not-generalizable 방법으로 이루어져 왔다는 것이다.

따라서 이 논문은 이를 해결하기 위해 Dependency Graph (DepGraph)를 제안한다. DepGraph는 하나의 layer를 pruning 했을 때, 전체 schema에 어떤 영향을 주는지를 계산한 뒤에, 함께 pruning해야하는 layer들을 group으로 출력한다. 이 출력값은 zeroize(0)/removal을 해도 괜찮은 pruning 대상임을 의미한다.

Main Concept - DepGraph

Initial Approach : Grouping

Inter dependency를 가지는 group, `g = {w_1, w_2, w_3}`이 있다면, 이는 아래와 같이 다시 쓰일 수 있다.(`G_ij=1`는 i-th, j-th layer에 dependency가 존재함(`True`)을 의미한다.)

하지만 이전에 언급했듯이, 이 방법은 인접하지 않는 layer에서 발생하는 dependency를 고려하지 않는다는 문제가 있다.

Initial Approach : Network Decomposition

Layer-level에서 의존성을 설계하는 Grouping 기법은 실용적이지 않은 경우가 많다. (e.g. FC layer는 neuron의 갯수만큼을 출력한다.)

따라서 network (F = {f_1, f_2, ..., f_L})를 아래와 같이 분해할 수 있다. 즉, 하나의 layer를 input & output layer로 분해할 수 있다. 이 방법은 different pruning schemes를 유연하게 도울 수 있다.

Solution : Dependency Modeling

Network decomposition을 했을 때 의존성은 다음과 같이 분류해볼 수 있다. Group-level pruning을 위해서는, 이 의존성들을 모두 고려해야만 한다.

Inter-layer Dependency : Input - output layer가 연결되어 있기 때문에 발생하는 의존성이다.
Intra-layer Dependency : 연결되지 않더라도, pruning schemes를 공유하기 때문에 발생하는 의존성이다.

Intra-layer dependency는 인접하지 않아도 함께 pruning되어야 하는 것임을 의미한다 (e.g. Batch Normalization layer는 이전 layer와 이후 layer는 인접하지 않아도 의존적). 이를 정리하면 다음과 같다. :

𝟙 : True를 반환하는 condition holds (indicator function)임을 의미한다.
∨ (or) : Input, output format이 같은지를 boolean으로 판단한다.

Solution : Group-Level Pruning

Grouping

Dependency Modeling을 통해서 구한 DeepGraph(D)를 통해서 의존성 관계를 파악했으므로, 기존의 layer-level보다 심층적으로 의존성을 고려하는 group-level pruning을 해볼 수 있다.

그런데 기존의 group-level pruning은 모든 schema에서 발생하는 dependency를 고려하지 않는다는 문제가 있다. 이를 위해서 DeepGraph를 통해 확인한 의존성 관계를 활용해, 안전하게 group-level parameters pruning을 수행하는 알고리즘을 제안한다.

위 사진은 도식화 해보자면 아래와 같다. 1, 2, 3, 4는 각각의 node (layer)에 해당하며, g는 pruning 대상인 group-level parameters이고, <->는 의존성이 존재함 (by DeepGraph) 이라고 볼 수 있다. 이 알고리즘은 아래와 같은 방식으로 전개된다. :

Action : 1번 노드부터 시작해서, 마지막 노드까지 순차적으로 BFS 방식으로 전개된다.
만약 노드가 i=1인 노드와 의존적이라면, g에 그 노드의 parameters를 추가한다. (일종의 인덱스 추가 방식)
위의 반복이 끝난 뒤에는, group-level parameters인 g가 반환될 것이다.

따라서 DeepGraph & Grouping을 통해서 전체 schema에서 발생하는 dependency를 파악하고, 이를 통해서 group-level pruning을 해볼 수 있다.

Group Layer Zeroization

이제 지금까지 찾아낸 낮은 중요도의 parameters를 제거할 시간이다. 논문에서는 그룹 전체를 0으로 만듬으로써 중요도를 낮추는 정규화 (Regularization) 기법을 소개한다.

I_g,k : Pruning이 가능한 k-th 차원임을 의미한다.
r_k : Pruning을 적용했을 때, parameters를 제거함으로써 생기는 변화, 즉 pruning의 중요성을 의미한다.

Conclusion

이 논문은 기존의 Structural Pruning에서 발생했던, 아래의 문제를 극복하고자 한 논문이다.

(1) 전체 schema를 고려하지 않기 때문에 일관된 group-level pruning이 어려웠다는 문제
(2) 현대의 DNN (Deep Neural Networks)은 다양한 module (layer)로 구성되어 있기 때문에, unified-protocol이 없다는 문제 (이전에는 직접 시행착오를 통해서 경량화를 시도해야 했다.)

이를 위해서 전체 schema의 dependency를 계산하는 DeepGraph (Dependency Graph)를 최초로 제시했다는 점에서 의의가 있다. 이를 통해서 0(sparse)로 변환된 group-level parameters를 일관된 규칙으로 반환해준다. 또한 논문에서 제시된 알고리즘은 BFS 기반이므로, 시간 복잡도가 O(n^2)라는 특징이 있다.

관련 내용은 모두 GitHub에 코드베이스로 구현되어 있기 때문에, 구체적으로 어떻게 알고리즘이 전개되는지 모두 확인해볼 수 있다. (현재 코드를 리뷰하는 중이며, 관련 내용을 업로드할 계획이다.)