Trace Trick

Sung Jae Hyuk·2023년 6월 23일
Linear AlgebraMathematics
0

Mathematics

목록 보기
1/1

Motivation

일반적으로, 우리가 처음 배우는 미분이라는 개념은 고등학교 때 미적분을 배울 때 처음 등장한다.
미분의 정의부터 미분가능성, 실제 미분식까지 여러 가지를 배우는데, 이때 무엇을 해도 변하지 않는 것은 바로 일변수라는 것이다.
수학적으로 표현하면, 함수 f:R→Rf:\R\rightarrow\R에 대해서 미분을 다루기 때문에, 크게 문제가 일어나지 않는다.
하지만, 딥러닝으로 들어가면 하나의 데이터가 가지고 있는 feature들이 여러 개 있기 때문에 Vector를, 이것들을 한꺼번에 처리하기 위해 Matrix를 들고오게 된다.
특히, 딥러닝쪽에서는 Parameter update(often called Backpropagation)를 진행하기 위해서 현재 parameter에서의 Loss값을 이용하기 때문에, 그때의 Gradient를 구할 수 있어야 한다.
즉, 우리가 필요한 것은 f:Rm×n→Rf:\R^{m\times n}\rightarrow \R의 함수에서 f(X)f(X) 혹은 f:Rm→Rf:\R^m\rightarrow \R에서 f(x)f(\mathbf{x})의 Gradient 값이 필요하다.
이를 조금 쉽게 구할 방법에 대해서 알아볼 것이다.

Symbols

편의를 위해, 추후 자주 쓰일 것들에 대해 약속을 할 것이다.

  • x\mathbf{x}, y\mathbf{y}와 같이 굵은 소문자는 vector를 의미한다.
  • AA, BB와 같이 대문자는 Matrix, 즉 행렬을 의미한다.
    일반적으로 ff, gg, hh는 함수를 의미하며, R\R은 실수 전체의 집합이다.
  • ⋅\cdot는 행렬곱을 의미하며 대부분 줄여쓴다. 즉, A⋅B=ABA\cdot B=AB로 사용한다.
  • ⊙\odot는 Hadamard product를 의미하며, 각 원소끼리 곱을 의미한다.
    즉, 크기가 같은 행렬 AA, BB에 대해
    (A⊙B)ij=Aij×Bij(A\odot B)_{ij}=A_{ij}\times B_{ij}
  • ⊤\top는 Matrix의 전치를 할 때 사용한다. 즉,
    (A⊤)ij=Aji(A^\top)_{ij}=A_{ji}
  • Rn\R^n에서 각각의 변수는 (x1, x2, ⋯ , xn)(x_1,\:x_2,\:\cdots,\:x_n)으로 표기한다.
  • ⟨⋅, ⋅⟩\langle \cdot,\:\cdot\rangle은 내적을 의미한다. 즉, aa와 bb의 내적은 ⟨a, b⟩\langle a,\: b\rangle로 작성한다.
    • 편의를 위해 a⋅ba\cdot b로 작성할 때도 있다.

Total derivate

사실 다변수 함수의 미분과 가장 관련이 있는 값은 Gradient보다는 Total derivate이기 때문에, 이가 뭔지부터 알아보자.
일반적으로 다변수 같은 경우 미분을 고려할 때 여러 방향으로의 미분을 전체적으로 고려해야한다. 이를 Total derivate라고 한다.
참고로, 하나의 변수에 주목하여 이것에 대한 변화만 고려를 할 수 있는데, 이를 Partial derivate(편미분)이라고 한다.
위에서도 말했듯이 Total derivate는 전체에 대한 변화가 필요하기 때문에 각 부분에 대한 편미분의 값을 Vector로 만들어주는 식으로 진행한다.
즉, f:Rn→Rf:\R^n\rightarrow \R에 대해 Total Derivate DfaDf_a는

Dfa=[∂f∂x1(a)∂f∂x2(a)⋯∂f∂xn(a)]Df_a=\begin{bmatrix}\dfrac{\partial f}{\partial x_1}(a)&\dfrac{\partial f}{\partial x_2}(a)&\cdots&\dfrac{\partial f}{\partial x_n}(a)\end{bmatrix}

으로 표기한다.
현재 y=f(a)y=f(\mathbf{a})에서 yy에 대한 항이 아직 안 나온 것을 참고하자.
이때, 우리는 ff에 대한 변화량이 궁금한 것이고 이를 알기 위해서는 모든 xx에 대한 변화량에 대한 전체값의 변화가 필요하다.
따라서, 위의 값들을 모두 합쳐줄 필요가 있으므로

∑i=1n∂f∂xi(a)Δxi\displaystyle\sum_{i=1}^n\dfrac{\partial f}{\partial x_i}(a)\Delta x_i

이고, 우리는 미소 변화량에 대한 값이 필요하므로 Δxi\Delta x_i를 dxidx_i로 보내면

dfa=∑i=1n∂f∂xi(a)dxidf_a=\displaystyle\sum_{i=1}^ n\dfrac{\partial f}{\partial x_i}(a) dx_i

ff의 output이 R\R, 즉 일변수이기 때문에 다음과 같이 표현가능하고 만약 다변수면 ff를 일변수 함수의 stacking으로 표현하면 된다.

Why we learn Total derivate, not Gradient?

실제로 Gradient Descent에서 활용되는 것은 Gradient인데, 왜 Total derivate를 소개하였을까?
첫째로 Total derivate가 활용도가 더 높다.
무슨 뜻이냐면, Gradient에서는 Backpropagation에서 필수적으로 활용이 되는 Chain Rule이 성립하지 않는다.
Chain Rule이 성립하지 않으면 Layer 하나와 하나 간의 관계에서 미분을 하는 것이 아니라 전체에 대한 함수에 대해서 calculation을 수행해야하기 때문에, 난이도가 수백 수천배는 올라가게 된다.
다음으로, Total derivate와 Gradient는 서로 Tranpose의 관계에 있다. 즉,

∇f(p)⊤=Dfp\nabla f(p)^\top=Df_p

이 성립하고, 이를 이용하면 dfp=∑i=1n∂f∂xi(a)dxi=∇f(p)⋅dxdf_p=\displaystyle\sum_{i=1}^n \dfrac{\partial f}{\partial x_i}(a) dx_i=\nabla f(p)\cdot d\mathbf{x}로 쓸 수 있다.
또한, Total derivate에서는 Chain rule이 성립하고, 함수 f∘gf\circ g에서

d(f∘g)a=dfg(a)∘dgad(f\circ g)_a = df_{g(a)}\circ dg_a

Trace and inner product

해당 Chapter에서는 추후 trick을 위해 필요한 것들을 간단하게 소개할 예정이다.
Matrix에서는 모든 대각선의 요소를 더하는 연산자가 있는데, 이를 trace라고 한다.
행렬 AA에 대한 Trace는 tr⁡(A)\operatorname{tr}(A)로 표기하며, 가장 대표적인 commutative하고 linearity를 가지는 연산자이다.
Inner product, 즉 내적 연산은 두 개의 Vector 또는 행렬이 결합하여 실수를 뱉는 대표적인 연산자이다. 다르게 적으면,

⟨⋅, ⋅⟩ : Rn×Rn→R\langle \cdot,\:\cdot\rangle \::\:\R^{n}\times\R^n\rightarrow \R

이외에 내적이 될려면 여러 가지 성질을 만족해야하는데, 이는 생략하도록 하겠다.
일반적이로 벡터에서는 element wise한 곱을, Matrix에서는 Frobenius norm을 쓰는 것이 대표적이다.
Vector form에서 내적은 일반적으로 ⟨u, v⟩=u⊤v\langle u,\:v\rangle=u^\top v로 정의하고, Matrix에서는 ⟨A, B⟩=tr⁡(A⊤B)\langle A,\:B\rangle=\operatorname{tr}(A^\top B)를 활용한다.
이때, trace의 성질 중 하나인 ∀a∈R : tr⁡(a)=a\forall a\in \R\::\:\operatorname{tr}(a)=a를 활용하면 Vector에서의 내적도 동일하게 trace를 이용하여 정의할 수 있다.

Properties of Trace

  • tr⁡(A±B)=tr⁡(A)±tr⁡(B)\operatorname{tr}(A\pm B)=\operatorname{tr}(A)\pm\operatorname{tr}(B)
  • tr⁡(cA)=ctr⁡(A)\operatorname{tr}(cA)=c\operatorname{tr}(A), where cc is scalar.
  • tr⁡(AB)=tr⁡(BA)\operatorname{tr}(AB)=\operatorname{tr}(BA) (If can)
    • Corollary: tr⁡(A1A2⋯An)=tr⁡(AnA1⋯An−1)\operatorname{tr}(A_1A_2\cdots A_n)=\operatorname{tr}(A_n A_1\cdots A_{n-1})
  • tr⁡(A⊤B)=tr⁡(B⊤A)=∑i∑jAijBij\operatorname{tr}(A^\top B)=\operatorname{tr}(B^\top A)=\sum_{i}\sum_{j} A_{ij}B_{ij}
    • Lemma: tr⁡(A⊤)=tr⁡(A)\operatorname{tr}(A^\top)=\operatorname{tr}(A)
  • tr⁡(a)=a\operatorname{tr}(a)=a if a∈Ra\in\R (Important property!!!)

Matrix Differentiation rules

  • d(X±Y)=dX±dYd(X\pm Y)=dX\pm dY, d(XY)=(dX)Y+X(dY)d(XY)=(dX)Y+X(dY)
  • d(X⊤)=(dX)⊤d(X^\top)=(dX)^\top
  • dtr⁡(X)=tr⁡(dX)d\operatorname{tr}(X)=\operatorname{tr}(dX)
  • d(X⊙Y)=(dX⊙Y)=X⊙dYd(X\odot Y)=(dX\odot Y)=X\odot dY
  • dσ(X)=σ′(X)⊙dXd\sigma(X)=\sigma'(X)\odot dX, where σ(⋅)\sigma(\cdot) is an element wise function.
  • ⟨A, B⊙C⟩=⟨A⊙B, C⟩\langle A,\:B\odot C\rangle = \langle A\odot B,\:C\rangle, where AA, BB, CC has same size.

Inner product rules

  • ⟨X, Y⟩=⟨Y, X⟩\langle X,\:Y\rangle = \langle Y,\:X\rangle
  • ⟨aX, Y⟩=a⟨X, Y⟩=⟨X, aY⟩\langle aX,\:Y\rangle = a\langle X,\:Y\rangle=\langle X,\:aY\rangle
  • ⟨X+Z, Y⟩=⟨X, Y⟩+⟨Z, Y⟩\langle X+Z,\:Y\rangle = \langle X,\:Y\rangle + \langle Z,\:Y\rangle
  • ⟨X, Y⊙Z⟩=⟨X⊙Y, Z⟩\langle X,\:Y\odot Z\rangle = \langle X\odot Y,\:Z\rangle (Note that Hadamard product holds commutativity)
  • ⟨AC, BD⟩=⟨B⊤AC, D⟩=⟨ACD⊤, B⟩\langle AC,\:BD\rangle =\langle B^\top AC,\:D\rangle = \langle ACD^\top,\:B\rangle (Also holds BB or DD is vector)

Scalar function & Trace Trick

Scalar function은 함수 ff의 range가 실수 전체인 함수를 의미한다. 즉, f(x)∈Rf(\mathbf{x})\in\R 혹은 f(X)∈Rf(X)\in\R을 의미한다.
이때, 이전의 전미분과 Gradient의 관계식을 활용하면

∑i=1n∂f∂xidxi=(∇xf)⊤dx=tr⁡{(∇xf)⊤dx}=⟨∇xf, dx⟩\displaystyle\sum_{i=1}^n\dfrac{\partial f}{\partial x_i}dx_i=(\nabla_{\mathbf{x}}f)^\top d\mathbf{x}=\operatorname{tr}\{(\nabla_{\mathbf{x}}f)^{\top}d\mathbf{x}\}=\langle \nabla_{\mathbf{x}}f,\:d\mathbf{x}\rangle

Severel Examples

Example 1

Problem

정사각행렬 AA와 column vector x\mathbf{x}에 대해 함수 f(x)=x⊤Axf(\mathbf{x})=\mathbf{x}^\top A\mathbf{x}라 할때, ∇xf\nabla_\mathbf{x} f를 구하여라.

Solution

f : Rn→Rf\::\:\R^n\rightarrow \R이므로 scalar function이고 Trace Trick을 활용할 수 있다.
따라서,

df=⟨1, d(x⊤Ax)⟩=⟨1, (dx⊤)Ax+x⊤A(dx)⟩(∵ A is constant)=⟨1, (dx)⊤Ax+xTA(dx)⟩=⟨1, (dx)⊤Ax⟩+⟨1, x⊤A(dx)⟩=⟨1, x⊤A⊤(dx)⟩+⟨1, x⊤A(dx)⟩=⟨Ax, dx⟩+⟨A⊤x,dx⟩=⟨(A+A⊤)x, dx⟩=⟨∇xf, dx⟩∴ ∇xf=(A+A⊤)x\begin{aligned} df&=\langle1,\:d(\mathbf{x}^\top A\mathbf{x})\rangle\\ &=\langle 1,\:(d\mathbf{x}^\top)A\mathbf{x}+\mathbf{x^\top}A(d\mathbf{x})\rangle\qquad(\because~A\text{ is constant})\\ &=\langle 1,\:(d\mathbf{x})^\top A\mathbf{x}+\mathbf{x}^TA(d\mathbf{x})\rangle\\ &=\langle 1,\:(d\mathbf{x})^\top A\mathbf{x}\rangle +\langle 1,\:\mathbf{x}^\top A(d\mathbf{x})\rangle\\ &=\langle 1,\:\mathbf{x}^\top A^\top (d\mathbf{x})\rangle + \langle 1,\:\mathbf{x^\top}A(d\mathbf{x})\rangle\\ &=\langle A\mathbf{x},\:d\mathbf{x}\rangle+\langle A^\top \mathbf{x},d\mathbf{x}\rangle\\ &=\langle(A+A^\top)\mathbf{x},\:d\mathbf{x}\rangle=\langle\nabla_\mathbf{x}f,\:d\mathbf{x}\rangle\\ \therefore\:\nabla_{\mathbf{x}}f&=(A+A^\top)\mathbf{x} \end{aligned}

Example 2

Problem

f(X)=a⊤exp⁡(Xb)f(X)=a^\top \exp(Xb)에 대해 ∇Xf\nabla_X f를 구하시오.

Solution

f : Rn×m→Rf\::\:\R^{n\times m}\rightarrow \R이므로 scalar function이고 Trace trick을 활용할 수 있다.
따라서,

df=⟨1, d(a⊤exp⁡(Xb))⟩=⟨1, a⊤d(exp⁡(Xb))⟩=⟨a, d(exp⁡(Xb))⟩=⟨a, exp⁡(Xb)⊙d(Xb)⟩(∵ exp⁡(⋅) is element-wise function)=⟨a⊙exp⁡(Xb), d(Xb)⟩=⟨a⊙exp⁡(Xb), (dX)b⟩=⟨(a⊙exp⁡(Xb))⋅b⊤, dX⟩=⟨∇Xf, dX⟩∴ ∇Xf=(a⊙exp⁡(Xb))⋅b⊤\begin{aligned}df&=\langle 1,\:d(a^\top \exp(Xb))\rangle\\ &=\langle 1,\:a^\top d(\exp(Xb))\rangle\\&=\langle a,\:d(\exp(Xb))\rangle\\ &=\langle a,\:\exp(Xb)\odot d(Xb)\rangle\qquad(\because\:\exp(\cdot)\text{ is element-wise function})\\ &=\langle a\odot \exp(Xb),\:d(Xb)\rangle\\ &=\langle a\odot\exp(Xb),\:(dX)b\rangle\\ &=\langle (a\odot\exp(Xb))\cdot b^\top,\:dX\rangle=\langle\nabla_Xf,\:dX\rangle\\ \therefore\:\nabla_Xf&=(a\odot\exp(Xb))\cdot b^\top \end{aligned}

Example 3 (Neural Network)

Problem

L=f(Y)L=f(Y), Y=WXY=WX이라 하자. 이때, ff는 행렬에서 scalar로 보내는 함수이다. ∇Xf\nabla_X f, ∇Wf\nabla_W f을 구하여라. (이때, ∇Yf\nabla_Y f는 이미 구해진 상태라 가정하자.)

Solution

dL=df(Y)=⟨∇Yf, dY⟩=⟨∇Yf, d(WX)⟩=⟨∇Yf, (dW)X+W(dX)⟩=⟨∇Yf,(dW)X⟩+⟨∇Yf, W(dX)⟩\begin{aligned} dL=df(Y)&=\langle \nabla_Yf,\:dY\rangle\\&=\langle \nabla_Yf,\:d(WX)\rangle\\&=\langle\nabla_Yf,\:(dW)X+W(dX)\rangle\\&=\langle\nabla_Yf,(dW)X\rangle+\langle\nabla_Yf,\:W(dX)\rangle \end{aligned}

이때 ∇Xf\nabla_X f를 위해 WW를 constant라 가정하면 dW=0dW=0이므로

dL=⟨∇Yf, W(dX)⟩=⟨W⊤∇Yf,dX⟩=⟨∇Xf, dX⟩∴ ∇Xf=W⊤∇Yf\begin{aligned}dL&=\langle \nabla_Yf,\:W(dX)\rangle\\ &=\langle W^\top\nabla_Yf,dX\rangle=\langle\nabla_X f,\:dX\rangle\\ \therefore\:\nabla_Xf&=W^\top \nabla_Y f \end{aligned}

같은 방법으로 ∇Wf\nabla_W f를 위해 XX를 constant라 가정하면 dX=0dX=0이므로

dL=⟨∇Yf, (dW)X⟩=⟨∇Yf⋅X⊤,dW⟩=⟨∇Wf, dW⟩∴ ∇Wf=∇Yf⋅X⊤\begin{aligned}dL&=\langle \nabla_Yf,\:(dW)X\rangle\\ &=\langle \nabla_Yf\cdot X^\top,dW\rangle=\langle\nabla_W f,\:dW\rangle\\ \therefore\:\nabla_Wf&=\nabla_Y f\cdot X^\top \end{aligned}

Reference Link

profile
Sung Jae Hyuk
Hello World!

1개의 댓글

comment-user-thumbnail
김민규
2023년 7월 5일

잘 보고 있습니다

답글 달기