[3/18] Pruning and Sparsity (Part I)

[tjdtnsu]

이런 개념으로 깊게 공부해보는 건 처음이라 꼼꼼히 보는 노력해보기

[hoodong]

3/13목 1시간 강의자료 25쪽까지 공부

• 아직은 내용이 어렵지 않음
• 90% 제거해도 성능을 유지한다는 사실이 놀라움
• p21 파라미터수와 MAC 연산수가 비례하지 않는 점은 왜 그런지 모르겠음!
• p24 희소행렬 연산에 대한 하드웨어 지원이 중요해 보임 (현재 H100에서는 2:4 지원)
• 이번은 3시간내에 다 볼 수 있을지...

3/15토 1시간 강의자료 26-끝까지 공부

• 가지치기의 다양한 세분화 방법들과 선택기준들
• scaling-based pruning을 잘 모르겠음 (원래 CNN에 scaling factor가 있었던가?)
• second-order-based pruning은 대충 봤음 (뭔 말인지 모르겠음)

-> 동영상은 안봐도 될 듯
-> LLM쪽은 트랜스포머는 어려울 것 같음 (또 스킵?)

[namgyu-youn]

Pruning의 핵심은 low importance components in neural networks을 어떻게 찾고, 제거할 것인가? 입니다. 따라서, 강의의 내용은 "무엇이 importance를 결정(정의)하는가?", 그리고 "어떻게 pruning(제거)할 것인가?" 이렇게 두 가지로 나눠볼 수 있습니다.

그 중에서도 "어떻게 pruning할 것인가?"의 관점으로 본다면, "low-weight value를 직접적으로 제거하는 방법" & "Pruning했을 때 발생하는 변화를 활용하는 방법"으로 나눠볼 수 있습니다. 이를 다시 정리해보면 아래와 같습니다. :

• Direct Importance Estimation : Magnitude-based Pruning, Channel-level Pruning
• Impact of Removal : Scaling-based Pruning, Second-order-based Pruning

두 접근법은 다른 분야에서도 그렇듯이, Simple but low accuracy vs Hard but high accuracy의 대립으로 보입니다. 따라서 상황에 맞는 방법론을 선택하는 것이 좋을 것이라고 생각됩니다.

---

Obsidian Note :

[Saebitna]

강의 요약

• Pruning 소개 : Pruning 정의와 왜 Pruning을 하는가?
• 대표적인 Pruning structure 소개
• 어떤 weights 또는 neurons 을 pruning할 것인가

강의 소감 및 개인적 키 포인트들

• 적절한 pruning을 하면, 모델의 성능을 어느 정도 유지하면서 속도 향상, MAC을 줄일 수 있다는 pruning의 장점을 실제 예시와 함께 보여줘서 좋았음.
• 산업 현장에서 어떻게 적용되고 있는지 구체적인 소개가 특히 좋았음 (ex NVIDIA의 2:4 sparsity in A100 GPU). unstructured pruning은 GPU에는 적합하지 않다는 점을 짚어줌.
• Pruning Criterion에서 scaling-based pruning은 normalization layer로 풀 수 있다는 점과 second-order-based pruning에서 loss function의 에러를 최소화하는 방향으로 pruning을 진행하려면 어떤 weight을 제거해야 하는지 수학적으로 전개해서 설명해준 점이 좋았음
• Neuron pruning은 연결되어 있는 모든 weight을 제거하는 coarse-grained weight pruning이라는 관계
• Reconstruction error을 최소화하는 neuron을 제거하는 방식은 계산량이 꽤 될 것 같은데 아이디어가 좋았음
• 목적과 방법론에 다소 차이가 있지만 dropout이 생각남. 학습할 때 dropout을 적용하고 pruning할 때 prior information으로 활용할 수 있지 않을까? training with/out dropout이 pruning에 영향을 줄 수 있는지 궁금해짐

[surisurikim]

노션으로 정리했습니다.
https://pie-apparel-456.notion.site/day-2-1b4ec6ae9e2e8095b867db49ea2ff3ab?pvs=4

• 고개 끄덕이면서 들었던 부분은 정리하지 않았고
• ??? 하면서 공부해야 했던 부분을 정리했습니다
• 테일러 전개, 프로베니우스 Norm, 수학적인 내용이 많아서 그 부분 파 보는게 재밌었습니다 (?)
• 정리하지 않은 부분에서도 아직 잘 모르는 내용이 많을텐데, 스터디에서 함께 얘기하면서 구체화해보고 싶습니다.

[tjdtnsu]

• 메모리 이동이 중요하기 때문에 모델 크기, activation size를 줄이는 것은 중요하다 -> pruning 중요성
• 그냥 pruning보다는 pruning+fine tuning, 그것보단 iterative pruning and finetuning이 좋음
• fine-grained pruning은 크기 줄이긴 좋은데 가속은 거의 안됨. N:M sparsity 쓰고, 2:4(50%) 많이 씀. 속도도 2배
• channel pruning은 uniform shrink보다 channel prune이 좋음.
• magnitude-based(0에 가까운것), scaling-based pruning(channel scaling factor) 둠. 이건 trainable parameter임.
• second-order-based pruning: loss function 최소화하기. weight 차이는 pruning되는 weight의 음수임. hessian과 weight 크기로 중요성 결정. 근데 H는 계산 어려움
• percentage-of-zero-based pruning: relu 수로 중요성 계산. average percentages of zeros라고 함.
• regression-based pruning: recon error를 최소화하도록 함. 이것도 coefficient vector beta 둠. 이것도 W 고정 beta 계산, beta 고정, error 최소화하는 W 계산 방식

[sw930718]

저도 노션으로 정리했습니다. 노션 내용을 다시 한 번 정리해서 discussion에 올리려고 했으나 시간이 없어서 노션 링크로 업로드 합니다 !
https://integerjs.notion.site/Lecture-3-Pruning-and-Sparsity-Part-I-1b93beecf793803dbd65cf89a3b36d83?pvs=4

• pruning의 다양한 방식들을 알 수 있어서 좋았고, 성능 실험 결과들을 보며 빨리 직접 적용해보고 싶다는 생각이 들었습니다.
• 수식적인 부분 같이 이야기 나눠보고 싶습니다

[tjdtnsu]

Second-Order-based Pruning

신경망의 가중치 $w_i$를 제거(prune)할 때, 손실 함수 $L(w)$의 변화량을 2차 테일러 근사를 통해 추정합니다. 즉, **“이 가중치를 제거했을 때 손실이 얼마나 늘어날 것인가?”**를 계산하여, 손실 증가량이 가장 작은 (즉, 중요도가 낮은) 가중치부터 제거하는 기법입니다.

1. 가중치 제거에 따른 손실 함수 변화

네트워크가 충분히 학습되어 최적점 근방에 있다고 가정하면,
$$L(w + \Delta w) \approx L(w) + \nabla L(w)^\top \Delta w + \frac{1}{2}\Delta w^\top H,\Delta w$$
여기서

• $\nabla L(w)$는 가중치에 대한 1차 미분(Gradient)
• $H$는 2차 미분(Hessian)
• $\Delta w$는 가중치의 변화량입니다.

최적점 근방에서는 $\nabla L(w) \approx 0$라고 가정하면,
$$L(w + \Delta w) \approx L(w) + \frac{1}{2}\Delta w^\top H,\Delta w$$

2. 특정 가중치 $w_i$ 제거 시 손실 변화량

가중치 $w_i$를 0으로 만드는 경우,
$$\Delta w_i = -w_i$$
이며, 이때 다른 원소는 0인 벡터로 간주하면 손실 변화량은
$$\Delta L_i \approx \frac{1}{2}w_i^2,H_{ii}$$
여기서 $H_{ii}$는 Hessian의 대각 원소입니다.

3. 중요도(Importance) 측정

각 가중치의 중요도는 제거 시 발생하는 손실 증가량으로 정의됩니다. 따라서,
$$\text{importance}(w_i) \approx \Delta L_i \approx \frac{1}{2}w_i^2,H_{ii}$$
즉, $w_i$의 크기가 크고 $H_{ii}$ 값이 클수록 해당 가중치를 제거하면 손실이 크게 늘어나므로, 그 가중치는 모델에 중요한 역할을 한다고 판단할 수 있습니다.

요약:
Second-Order-based Pruning은 Hessian의 대각 원소를 활용하여 가중치 제거 시 발생하는 손실 증가량을 정량화합니다. 이를 통해 영향이 적은 가중치부터 제거하여 모델을 압축하며, 계산 복잡도를 낮추기 위해 주로 대각 근사(diagonal approximation)를 사용합니다.

[tjdtnsu]

Hessian Matrix 계산

다음은 함수 $$g(x, y) = 2x^2 + 4xy + 3y^2$$ 의 Hessian matrix를 구하는 과정입니다.

1. 1계 편미분 계산

(x)에 대한 편미분

$$\frac{\partial g}{\partial x} = \frac{\partial}{\partial x}\Big(2x^2 + 4xy + 3y^2\Big)$$

각 항을 미분하면:

• (2x^2)의 미분: $$\frac{\partial}{\partial x}(2x^2) = 4x$$
• (4xy)의 미분: $$\frac{\partial}{\partial x}(4xy) = 4y$$
• (3y^2)는 (x)에 대해 상수이므로: $$\frac{\partial}{\partial x}(3y^2) = 0$$

따라서,
$$\frac{\partial g}{\partial x} = 4x + 4y.$$

(y)에 대한 편미분

$$\frac{\partial g}{\partial y} = \frac{\partial}{\partial y}\Big(2x^2 + 4xy + 3y^2\Big)$$

각 항을 미분하면:

• (2x^2)는 (y)에 대해 상수이므로: $$\frac{\partial}{\partial y}(2x^2) = 0$$
• (4xy)의 미분: $$\frac{\partial}{\partial y}(4xy) = 4x$$
• (3y^2)의 미분: $$\frac{\partial}{\partial y}(3y^2) = 6y$$

따라서,
$$\frac{\partial g}{\partial y} = 4x + 6y.$$

---

2. 2계 편미분 계산

Hessian matrix는 모든 2계 편미분으로 구성됩니다. 아래 네 가지 편미분을 계산합니다.

(\frac{\partial^2 g}{\partial x^2})

$$\frac{\partial^2 g}{\partial x^2} = \frac{\partial}{\partial x}\Big(4x+4y\Big) = 4.$$

(\frac{\partial^2 g}{\partial y^2})

$$\frac{\partial^2 g}{\partial y^2} = \frac{\partial}{\partial y}\Big(4x+6y\Big) = 6.$$

교차 편미분

• (\frac{\partial^2 g}{\partial x \partial y}):

  $$\frac{\partial^2 g}{\partial x \partial y} = \frac{\partial}{\partial y}\Big(4x+4y\Big) = 4.$$

• (\frac{\partial^2 g}{\partial y \partial x}):

  $$\frac{\partial^2 g}{\partial y \partial x} = \frac{\partial}{\partial x}\Big(4x+6y\Big) = 4.$$

두 교차 편미분은 함수의 연속성에 의해 동일합니다.

---

3. Hessian Matrix 구성

계산된 2계 편미분들을 모아 Hessian matrix (H)는 다음과 같이 구성됩니다.

$$H = \begin{pmatrix} \frac{\partial^2 g}{\partial x^2} & \frac{\partial^2 g}{\partial x \partial y} \\\ \frac{\partial^2 g}{\partial y \partial x} & \frac{\partial^2 g}{\partial y^2} \end{pmatrix} = \begin{pmatrix} 4 & 4 \\\ 4 & 6 \end{pmatrix}.$$

---

결론

함수 $$g(x, y) = 2x^2 + 4xy + 3y^2$$ 의 Hessian matrix는

$$ \begin{pmatrix} 4 & 4 \\ 4 & 6 \end{pmatrix} $$

로 계산됩니다.

[tjdtnsu]

추가

• Hessian Matrix:
  https://angeloyeo.github.io/2020/06/17/Hessian.html

• Lp space:
  https://en.wikipedia.org/wiki/Lp_space