Backpropagation과 Gradient에 대한 이모저모

Motivation

학교에서 딥러닝 수업을 수강하고 있던 도중, $$\dfrac{\partial L}{\partial W}=\dfrac{\partial L}{\partial z} x^T,\quad \dfrac{\partial L}{\partial \mathbf{x}}=W^T \dfrac{\partial L}{\partial z}$$ 라는 내용을 보게 되었다. 일반적으로 Chian rule은 $\dfrac{\partial y}{\partial x}=\dfrac{\partial y}{\partial z}\cdot\dfrac{\partial z}{\partial x}$로 작성하는데, 아래에 있는 것 때문에 순서가 바뀐다는 것 자체가 좀 이상하지 않나?라는 생각이 들었다.

물론 gradient descent 과정에서 size를 맞춰주기 위해 적절하게 저런걸 취해준다고 하지만.. 만약 input이 square로 들어오게 되면? fixed $n$에 맞게 $W\in\mathsf{M}_{n\times n}(\mathbb R)$, $x$, $z\in\mathbb{R}^n$이면 저거 순서 맞추기도 까다로울것 같다는 생각이 들었다.

특히, Chain rule에서 각 chain의 결과가 matrix이거나 tensor가 되는 순간 Commutative property가 성립하지 않게 되는데, 이게 순서에 의존한다는게 뭔가 이상했다.. Outer product도 아니고 dot product도 아니고 chain rule이? 이게 왜 문제나면, $f(2x)$를 미분할 때 $2f'(2x)$로 적는것과 $f'(2x)\times 2$로 적는게 다를 수 있다는 것이다. 이게 가당키나 한지도 모르겠다.

이거 때문에 시험기간임에도 불구하고 시간을 쏟아부어서 대략적으로 어느 정도 정리했고, 이 내용을 정리하려고 한다. 물론, 그래디언트나 자코비안처럼 여러 내용들을 포괄적으로 다룰 예정이다!

* 편의를 위해 bold체로 되어 있는 소문자 수식들은 vector을, (bold X)대문자 수식은 matrix을, 그렇지 않으면 scalar(혹은 실수)을 의미하는 걸로 정하겠다.

---

Gradient Descent & Gradient(Part I)

내용을 본격적으로 시작하기 전에, 간략하게 Gradient descent에 대해 언급할 필요가 있을 것 같다. 사실 gradient descent는 backpropagation과 더불어 딥러닝을 맛봤다면(고등학생들 포함) 한번쯤은 들어봤을 것이고, 실제로 이쪽으로 보고서 쓰는 학생들도 많다고 들었는데 뭐 그건 잘 모르겠고..그러면 왜 한 가지 질문을 던져보자. 지금 우리가 해결하고 싶은 문제는 Parameter $\Theta$에 대해 $L(\Theta)$를 최소화하고 싶은 건데, 갑자기 뜬금없이 그래디언트를 구해서 그거에 맞게 parameter들을 업데이트하는 것인가? 만일 이에 대한 답을 할 수 있다면, 이 내용은 skip하여도 좋다.

Descent Methods

현재 우리의 상황을 수식으로 작성하면 $x^{(k+1)}=x^{(k)}+t^{(k)}\Delta x^{(k)}$이고, 이때 $f(x^{(k+1)})$은 $f(x^k)$보다는 값이 작아야 한다. 그렇게 해야 우리가 원하는 최솟값으로 가니까 말이다.

이때, $f$가 convex하다는 strong한 assumption을 해야하는데, 이 가정이 있어야 우리가 GD를 실행할 때 최적으로 간다는 보장이 있기 때문이다. 다음 Theorem에 근거한다. (증명 X)

Let $f\,:\,\mathbb{R}\,\rightarrow\,\mathbb{R}^n$ be differentiable convex function. Then, $\nabla f(x^*)=0$ if and only if $f$ has global(=local) minimum at $x=x^*$

 

뭐 암튼... 근데 우리는 최대한 빠르게 빠르게 최적을 다가가고 싶은 것이 목표이다. 기왕 갈거면 지름길을 타는게 낫지 느릿느릿하게 가면 무슨 맛이 있겠는가? 즉, 우리는 1) 어디를 향해서 2) 얼만큼 이걸 진행해야 하는가? 에 대한 정보를 가지고 있어야 하는 것이다.

즉, 우리는 2번도 풀어야 하는데 무엇보다 1번이 제일 골때린다.. 2번은 사실 해당 점에서의 Gradient와 연관이 있는 사항이기때문에 문제가 없는데, 과연 어느 방향으로 가야 이걸 가장 빠르게 줄이는지를 모르지 않는가?

따라서 이를 해결하기 위해 1차 근사를 때려보자. Chain rule(or total derivate)에 의해..

$$\begin{align} f(x+\Delta x)&\approx f(x)+\displaystyle\sum_{i=1}^n \dfrac{\partial f}{\partial x_i} \cdot \Delta x_i\\ &=f(x)+\nabla f(x)^T\Delta x \end{align} \quad (1)$$ 로 적을 수 있고, 이때 $\nabla f(x)$는 점 $x$에서의 gradient이다.

즉, 임의의 vector $v$에 대해 점 $x$에서 $v$를 따라가는 방향에 대한 미분값은 $\nabla f(x)^T v$임을 알 수 있다! 이게 무슨 개소린가 싶겠지만, $\dfrac{d}{dt} f(x+tv)\Big| _{t=0}$ 로 생각을 해보면, 바로 앞서 한 1차 근사에 의해 $v$방향으로 아주 아주 아주 아주 쪼끔 움직였을 때의 방향 미분이 저렇게 됨을 알 수 있다.

즉, 우리는 관점을 바꾸어서 "어느 방향으로 가는게 제일 빨리 줄어드는데?" 가 아니라, "어느 벡터를 따라서 가면 그 방향 벡터의 값이 제일 작아지는데?"로 바꿀 수 있다. 즉, $$\min \nabla f(x)^T v$$로 바뀌게 된다. 이때, 우리가 중요한 건 "어느 방향으로 갑니까?" 이기 때문에, 편의를 위해서 모든 $v$의 크기를 $1$로 고정하자. 즉, $$\min_{\| v \|=1} \nabla f(x)^T v$$이고, 이 값은 Cauchy-Schwarz inequaility에 의해 $\nabla f(x)$와 $v$가 서로 반대로 평행할 때, 즉 정반대로 향할 때 최소값 $-\nabla f(x)$를 가짐을 알 수 있다! 그래서, 저렇게 파라미터를 최적화해나가는 과정에서 정반대편으로의 Gradient를 택하는 것이다.

참고로, 조금 더 상위의 개념으로 steepest gradient descent가 있는데, 이때는 dual로 최종 방향을 결정해서 우리가 생각하는것처럼 반대로 진행하고 그러지는 않는다. More generally하게, Gradient descent는 Steepest gradient descent의 2-norm 버전이다. Cauchy-Schwerz inequality는 2-norm에서의 버전이고 dualaity로 가면 Holder's inequality를 따르게 되기 때문에.. 대충 절망편이구나~ 싶으면 된다

참고로 Gradient를 정의하는 저 (1)번식은 추후에 다시 소개할 예정이니.. 기억해두면 좋다.

---

Differentation of vectors and expansion as matrices

일반적으로 우리는 미분이라는 개념을 일변수로부터 처음 배운다. 즉, $f\,:\,\mathbb{R}\rightarrow\mathbb{R}$로 배우는데, 이 경우는 굉장히 단순하게 표현이 가능하다. (미분의 정의가 아니라) 표기를 빌리면, $$df=f' dx$$로 적을 수 있다. 이 표기를 굳이 강조해서 적은 이유는.. 추후 벡터 미분할 때도, 행렬을 미분할 때도 쓸 것이기 때문이니 기억해두자.

자.. 이걸 확장해서 벡터와 행렬에 대해 미분을 하는 내용에 대해 다뤄보자. 추후 표기 시 "텐서"란 말이 나오게 될텐데, 텐서는 3차원 이상의 행렬을 의미한다고 보면 된다.

먼저, 벡터에 대한 미분을 알아보자. 일단 값을 반환하는 scalar에 대해 어떤 벡터를 미분하는, 즉 scalar $y$에 대한 vector $\mathbf{x}$에 대한 미분부터 알아보자. chapter 4(Persepective trace on differentiation)에서 두 개의 관점에 대해서 다룰 것이므로, 지금은 정의에 대해 불만(?) 없이 인정하고 사용하도록 하자.

위에서 설명한 개념은 우리가 귀에 닳도록 들었던 "Gradient"이고, 표기로는 $\nabla f(\mathbf{x})=\begin{bmatrix}\dfrac{\partial f}{\partial x_1}&\dfrac{\partial f}{\partial x_2}&\cdots&\dfrac{\partial f}{\partial x_n}\end{bmatrix}^T$로 작성할 수 있다. 원래 $\mathbf{x}$의 크기가 $\mathbb{R}^{n\times 1}$임을 기억하면, Gradient와 원래 벡터의 dimension은 동일함을 알 수 있다.

---

이를 확장하여, 벡터에서 벡터로 가는 함수를 생각해보자. 즉, $f\,:\,\mathbb{R}^n \rightarrow \mathbb{R}^m$인 선형변환에서 $f(\mathbf{x})=\mathbf{y}$라고 하자. 뒤에 쓸 내용을 위해 $\mathbf{y}=\begin{bmatrix}y_1&y_2&\cdots&y_n\end{bmatrix}^T$, $\mathbf{x}=\begin{bmatrix} x_1 & x_2&\cdots&x_m\end{bmatrix}^T$라 하자.

또, $f_i\,:\,\mathbb{R}^n\rightarrow \mathbb{R}$이고, $f_i(\mathbf{x})=y_i$임을 가정하자.

이때, $\dfrac{\partial \mathbf y}{\partial \mathbf x}$를 $jacobian$이라고 하며, 이는 $m\times n$의 행렬이다. (추후 소개하겠지만, 행렬과 벡터는 다른 개념이므로 $\mathbb{R}^{n\times m}$이라는 표기를 사용하지 않았다. 실제로, 조금 편하게 칭하겠다고 고지하지 않는 이상 어느 책에서도 저런 표기를 사용하지 않는다.)

More specifically, 앞서 각각의 스칼라에 대한 벡터의 미분(Gradient)를 합친 꼴이 되며, $\dfrac{\partial y}{\partial \mathbf{x}}=\begin{bmatrix} \nabla f_1^T(\mathbf{x})\\ \nabla f_2^T(\mathbf{x})\\\vdots \\\nabla f_m^T(\mathbf{x})\end{bmatrix}$가 되고, 각 row는 gradient의 transpose가 됨을 볼 수 있다.

---

다음 내용으로 넘어가기 전에 미분한 것에 대한 size를 확인하고 가자. Gradient는 $n \times 1$이고, Jacobian은 $n\times m$의 행렬이다. 즉, 1차원 벡터들끼리의 변환에 대해서는 2차원의 행렬이, 1차원 벡터에서 스칼라(0차원)로의 변환에 대해서는 1차원을 반환함을 알 수 있다. 따라서 $n$차원의 object에서 $m$차원의 object로의 변환이 있을 때, 그에 대한 미분값은 $m+n$차원의 object를 반환함을 알 수 있다.

---

이를 행렬로 확장하여 행렬에 대한 미분도 동일하게 쓸 수 있을까?

알아보기 전에, 먼저 행렬과 벡터에 대한 차이부터 알아보아야 한다.

이제 잘못된 개념이 잡히기 쉬운게 두 가지 있는데,

1. 미분과 적분은 서로 의미론적으로 관련이 있다. (식 뿐만 아니라 정의 등에도)
2. 행렬에서 벡터가 나온다.

이다.

일단, 1번은 사실 미분과 적분은 상관이 없는데, 어쩌다보니까 어라? 두개가 계산을 할 때 필요하다고 나오는 것이다.

이걸 연결시켜주는 정리가 미적분학의 기본 원리(Fundamental of theorem calculus)이다.

결국은 지금은 2번에 초점을 두어서 말할건데, 결론적으로 말하면 반은 맞고 반은 틀리다.

정확하게, 행렬에서 벡터가 나온다기 보다는 벡터에서 행렬이 나온다.

일반적인 선형대수학 책을 펼쳐보면, 맨 처음 다루는 것은 행렬이 아니라 어떤 Scalar Space $F$에서 만드는 Vector space $V$이다. $V$ 안에 있는 것의 원소를 우리는 벡터라고 하며, 어떠한 벡터 공간을 만들기 위해 필요한 최소한의 벡터들을 기저(Basis)라고 한다. 그 중에서도 조금 특이한 친구들을 standard basis라고 하는 것이다. (가장 깔끔하게 만들려면 orthonormal basis들이 되지 않을까 싶다.)

그러면, 우리는 벡터에서 다른 벡터로 바꾸는 어떠한 "변환"에 대해서 생각할 수 있고, 그 중에서 선형성을 가지는 변환을 선형변환이라고 한다. 그러면, $T\,:\,V\rightarrow\,V$의 변환에 대해 이걸 식으로 표현이 가능할까? 예를 들어, 2배를 시키는 함수를 $f(x)=2x$라고 적는 것처럼 벡터 $v\in V$에 대해 $T(v)$를 일차함수꼴로 적는 것을 말한다. 정답은 "있다"이고, Left multiplication을 통해 이러한 변환을 만들어 줄 수 있다. 이때! Left multiplication을 할 때 처음으로 하나의 개념이 나오게 되는데, 그게 바로 행렬이다.

즉, 행렬은 어떠한 벡터를 다른 벡터로 바꾸는 행위이고, 선형 변환을 깔끔하게 하기 위한 수단이다. 위의 내용을 깔끔하게 수학적으로 정리한 것이 Fundamental of theorem Linear algebra인데, 정식명칭은 아니고 보통 이 정리를 Rank theorem과 많이 연계시키곤 한다.

아무튼.. 핵심은 행렬이라는 것은 선형 변환과 동형이라는 것이고, 따라서 벡터에 대하여 미분하는 것과 행렬에 대해 미분하는 것은 의미 자체가 다르다고 생각할 수 있다.

자.. 그러면 우리가 흔히 쓰는 표기 $\mathbb{R}^{n\times m}$이라는 친구는, $n\times m$의 행렬이 아니라 $n \times m$의 벡터로, 굳이 따지자면 $n\times m$의 column vector을 의미한다. 이걸 행렬로 해석하는 경우가 종종 있는데, 이는 잘못된 해석임을 기억하자!

---

엇.. 그럼 앞서 Gradient를 Jacobian에서 확대했던 것처럼 하기에는.. 다소 무리가 있음을 직관적으로 깨달을 수 있다..!

그럼 어떻게 정의를 해야할까....?

실제로, 만약 행렬 $X=\mathsf{M}_{n\times n}(\mathbb{R})$에서 벡터 $\mathbf{y}=\mathbb{R}^m$으로 보내는 변환 $f$에 대해 $\dfrac{\partial \mathbf{y}}{\partial X}$는 앞서서 말했던 설명에 의해 $2+1=3$차원이 되고, 이는 텐서가 되어서, 평면 상에서 표현할 수 없다.

따라서 적을 수 없기 때문에(...) 실제로 스칼라, 벡터, 행렬에 대한 gradient는 최대 차원이 2가 될 때만 정의를 한다. 

1. 조금 더 상세하게 말하면, Gradient의 각 원소를 행렬 각 원소에 대한 gradient(즉, vector, matrix, or tensor)로 가정하면 이는 가능하다.
2. Derivate가 아닌 Gradient라는 용어로 쓴 이유는, 추후 total derivate가 나오면 정말 생각도 못할 정도로 간단하게 정의를 할 수 있기 때문이다.

엇.. 그럼 스칼라에서 행렬로 가는 미분은 정의할 수 있다는 것 아닌가?라는 의문이 들었다면.. 이건 맞다

$X=\mathsf{M}_{n \times m}(\mathbb{R})$에서 스칼라 $y$로 가는 변환 $f$에 대해, $\dfrac{\partial y}{\partial X}$는 행렬 각각의 element에 대한 단일 미분값으로 정의된다. 단일로 보면, $0$차원에서 $0$차원의 변환이므로 $0$차원의 scalar가 나오게 되어서 동일한 size($n\times m$)의 행렬이 반환이 된다.

출처: https://www.kamperh.com/notes/kamper_matrixcalculus13.pdf

• 저자에 따라 gradient나 jacobian의 size 표기를 마음대로 사용하는 경우가 많다.
• 위의 그림은, 행렬을 간편하게 표기하기로 약속한 상황이다. 이도 유사한 개념이기 때문에 혼용하는 경우가 많다.

Backpropagation trick using shape convention

* 작성 예정

* 주요 내용: Back propagation, Tensor, matrix, shape convention, transpose

Perspective trace on differentiation

* 작성 예정

* 주요 내용: Trace, Matrix differentation, total derivate, gradient

Mathematical process on backpropagation using relationship between total derivative and gradient (called trace trick)

* 작성 예정

* 주요 내용: Back propagation, trace