게시물 목록

Showing posts with label linear algebra. Show all posts
Showing posts with label linear algebra. Show all posts

Wednesday, September 18, 2024

Simple script for solving matrix equations via Mathematica

Using the Solve[...] function provided by Mathematica, users can solve matrix equations. For example, a set of matrix equations \(AC+CA^\mathrm{T} = 2D\) and \(C=C^\mathrm{T}\) will be solved below.

AMatrix = (* define a matrix *);                           
                                                           
Diff = (* define a matrix *);                              
                                                           
n = (Dimensions[AMatrix][[1]]);                            
                                                           
CMat = Array[x, {n, n}]; (* set proper dimension *)        
                                                           
Csol = Solve[                                              
   AMatrix.CMat + CMat.Transpose[AMatrix] == (2*Diff) &&   
    Transpose[CMat] == CMat                                
    (* replace this with your own equations *)             
, Flatten[CMat]];                                          
                                                           
Cvec = Array[x, {(n*n), 1}];                               
                                                           
For[i = 1, i < ((n*n) + 1), i++,                           
  Cvec[[i, 1]] = Csol[[All, i, 2]][[1]];                   
  ];                                                       
                                                           
CMat = Transpose[ArrayReshape[Cvec, {(2*n), (2*n)}]];      

This is a convenient and neat way to solve matrix equations. Indeed, one should always care about the existence and (non-)uniqueness of the solutions, which Mathematica may fail to address completely. Also note that fully symbolic calculations are quite heavy.

Wednesday, November 27, 2019

Coupled Oscillator and Kuramoto Model

하단에 embed된 Coupled oscillator 및 Kuramoto model에 대한 자료는 2019-2 서울대학교 전기정보공학부 <비선형제어특론(심형보 교수님)> 강좌에서 발표 진행을 위해 정리한 자료로, Francesco Bullo의 책 <Lectures on Network Systems>의 제17 장의 내용을 정리한 결과이다.

(추후 LaTeX documentation 예정)

Friday, October 11, 2019

[Review] Entropy Production and Information Transfer of Stochastic Dynamical Systems

[리뷰] 확률적 동역학 시스템에서 엔트로피 생성과 정보 전달

0. 개요

  State vector \( \vec{x} \)에 대한 미분방정식으로 표현되는 동역학 시스템(dynamical systems)의 이론은 응용수학의 한 갈래로서 물리학, 그리고 공학에서의 제어 이론(control theory) 등 다양한 분야에 활용된다. 특히 비평형 계를 다루는 비평형 통계물리학에서는 종래의 평형 통계역학에서와 같이 앙상블(ensemble) 접근을 통해 분배 함수(partition function)를 정의하여 물리량들을 유도하는 방법론을 적용하기 어려우므로 noisy term \( \vec{\xi}(t) \) (주로 stationary Ornstein-Uhlenbeck process with zero characteristic time)를 포함하는, 확률변수들의 벡터(random vector) \( \vec{X} \)에 대한 확률미분방정식(SDE)을 적극적으로 활용하여 시스템을 표현하고 해석한다.

  이 게시물에서는 확률미분방정식으로 표현되는 시스템(특히 Langevin 시스템)에서 이 시스템의 솔루션이 가지는 확률분포함수 및 그것이 따르는 Fokker-Planck 방정식 등을 바탕으로 하여 시스템의 엔트로피 생성(entropy production) 및 정보 전달(information transfer) 등을 정량적으로 다루고자 하는 일련의 논문들([1]-[4])을 소개하고, 관련된 몇 가지 이슈에 대해 생각해 본다.


1. 논문 소개: 선형 랑주뱅 시스템에서의 엔트로피 생성

  이 문단에서는 <Entropy production in linear Langevin systems>(Gabriel T. Landi et al., Journal of Physics A: Mathematical and Theoretical, 2013)에 대해 개괄한다([1], arXiv 링크). 이 논문에서는 엔트로피에 대한 물리학적 배경 설명 및 수학적인 전개가 상당히 rigorous하고 충실하게 기술되어 있으므로, 본 문단은 이 게시글 전체를 대표하는 표준적 논의라고 할 수 있다. 논문은 먼저 열역학에 대한 일반적인 논의로 시작한다.

  시스템이 상태 A에서 상태 B로 변화할 때 그러한 변화가 가역적(reversible)이라면, 시스템이 겪는 엔트로피 변화는 \( \Delta S = \int \frac{dQ}{T} \)로 나타내어진다. 반면 이 변화가 비가역적이라면 위의 등식은 성립하지 않으며, 다음과 같은 부등식이 성립한다. 이 때 \( S_{prod} \)가 바로 entropy production으로, 우주 전체에서 기존에는 없다가 새롭게 생성된 만큼의 엔트로피라고 볼 수 있다.
\[ \Delta S - \int \frac{dQ}{T} = S_{prod} \geq 0 \]
  이 식의 양변을 시간 \( \Delta t \)로 나누고 극한을 취해 주면 다음과 같이 된다. 여기서 \( \Pi (t) = \frac{dS_{prod}}{dt} = \frac{dS}{dt} + \frac{d}{dt}\int{\frac{dQ}{T}} \)는 entropy production rate, \( \Phi (t) = \frac{d}{dt} \int{\frac{dQ}{T}} \)는 계에서 외부로의 entropy flux rate가 된다. 위에서 살펴보았듯 비가역성에 기여하는 term은 바로 \( \Pi (t) \)로, 항상 non-negative하다.

\[ \frac{dS_{prod}}{dt} = \frac{dS}{dt} - \frac{d}{dt} \int{\frac{dQ}{T}} \geq 0 \]
이항하면, 
\[ \frac{dS}{dt} = \frac{dS_{prod}}{dt} ( \geq 0) - \frac{d}{dt} \int{\frac{dQ}{T}} = \Pi (t) - \Phi (t) \]

  이렇게 하면 계의 entropy 생성과 출입에 대해 다음과 같이 intuitive한 식을 쓸 수도 있다.
\[ S = \int_{0}^{t}{dt' (\Pi(t') - \Phi(t'))} \]

  한편, 저자는 random vector \( X = (X_1, ... , X_n) \)가 따르는 랑주뱅 방정식(Langevin equation) \( \dot{X} = f(X, t) + B\dot{\xi}(t) \), 그 중에서도 특히 \( f(x, t) = -Ax + b(t) \)인 선형 랑주뱅 방정식과, 그에 대응되는 Fokker-Planck 방정식 \( \frac {\partial P }{ \partial t} = -\frac {\partial g }{ \partial x } \) (단 확률흐름(probability current) \( g(x,t) = f(x, t) P(x, t) - D \frac {\partial P }{ \partial x } (x, t) \))으로써 우리가 관심 있는 시스템을 정의한다.

  여기서 diffusion tensor \(D\)는 \(D = \frac{1}{2} {B} {B^T} \)로 정의되며, \(B\)가 full row rank를 가진다면 \(D\)는 positive definite(그렇지 않다면 positive semi-definite)가 된다. 이 positive definiteness 성질이 이하의 main formalism에서 중요하게 쓰이게 된다.

  다음으로 저자는 시스템에 대한 구체적인 지식 없이도 비가역성과 가역성에 대해 성공적으로 취급할 수 있도록 하기 위한, 본 문헌의 첫 번째 핵심적인 논의를 다음과 같이 clever하게 전개한다. 시스템을 이루는 상태변수들 중에, 시스템에 시간 되짚기(time reversal) 대칭을 시행했을 때 부호가 변하는 상태변수(odd variables), 그렇지 않은 상태변수(even variables)를 구분하기 위해 indicator \( \epsilon_i = \pm 1 \)을 정의한다. 이어서 odd variable끼리, even variable끼리 묶이도록 상태변수들의 순서를 rearrange하여 \(x = {\begin{bmatrix} x_{even} &  x_{odd} \end{bmatrix}}^T \)로 쓰고, 대각행렬 \( E = diag (\epsilon_1, ... , \epsilon_n ) \)를 사용하면 다음과 같이 쓸 수 있다.
\[ Ex = E{\begin{bmatrix} x_{even} &  x_{odd} \end{bmatrix}}^T = {\begin{bmatrix} x_{even} &  -x_{odd} \end{bmatrix}}^T \]

  먼저 주어진 랑주뱅 시스템이 다음과 같이 비가역 부분과 비가역 부분으로 나눠짐에 주목하자.
\[f(x,t) = f^{irr}(x,t) + f^{rev}(x,t) = Ef^{irr}(Ex, t) + (- Ef^{rev}(Ex, t)) \]
  이렇게 하면 확률흐름 \(g\)가 다음과 같이 비가역 부분과 가역 부분으로 나뉘게 되며 두 부분은 매우 주목할 만한 차이가 있다.

\[ g^{irr}(x, t) = f^{irr}(x, t) P(x, t) - D \frac{\partial P}{\partial x}(x, t)
\\ g^{rev}(x, t) = f^{rev}(x, t) P(x, t) \]

  다음으로 저자는 확률적 동역학 시스템의 엔트로피를 정의하는, 본 문헌의 두 번째 핵심적인 논의를 전개한다. 시스템의 엔트로피는 다음과 같이 정의된다.
\[ S = -\int P \log P dx \]
  가능한 상태공간 전체에 대해 \( - P \log P \)를 evaluate해서 적분해 주는, 익숙한 식이다. 여기서 \(P = P(x, t) \)이므로 적분의 결과인 엔트로피 \(S\)는 시간의 함수가 됨에 주목한다. 엔트로피를 시간에 대해 미분해 주되 앞에서 소개한, 시스템의 비가역적 요소와 가역적 요소를 나누어서 생각하는 philosophy를 도입해 주면 다음과 같다.

\[ \frac{dS}{dt} = \int (g^{irr})^T D^{-1} g^{irr} \frac{dx}{P} - \int (g^{irr})^T D^{-1} f^{irr} \frac{dx}{P} \]
  여기서 첫 번째 항의 피적분함수는 quadratic form이고, 앞서 강조하였듯 diffusion tensor D가 정의상 positive (semi-)definite하므로 이 quadratic form은 non-negative하다. 이를 맨 처음의 열역학적 논의와 비교하면 아래의 수식과 같이 결론내릴 수 있다. 이로써, Langevin 방정식(및 대응되는 Fokker-Planck 방정식)으로 기술되는 확률적 동역학 시스템에서의 entropy production과 entropy flux를 explicitly 유도하였다. 

\[ \Pi (t)  =  \int (g^{irr})^T D^{-1} g^{irr} \frac{dx}{P}, \]
\[ \Phi (t) = \int (g^{irr})^T D^{-1} f^{irr} \frac{dx}{P}   \]

  논문의 나머지 부분에서는 entropy production rate \( \Pi (t) \)를 (i) integral fluctuation theorem을 따르며 non-adiabatic한 부분, (ii) integral fluctuation theorem을 따르며 adiabatic한 부분, (iii) integral fluctuation theorem을 따르지 않는 부분으로 나눈다. 다음으로 선형 Langevin 방정식으로 국한하여 논의를 특수화시켜, 행렬과 벡터만을 사용한 선형대수학적 형태로 그러한 각 부분을 표현한다. 이 단계에 이르면 Fokker-Planck 방정식의 해인 확률분포함수 \(P\)가 식에 드러나지 않는다.

  다음으로 저자는 간단한 응용의 시도로서, noise term을 추가해 준 전기 회로(RL, RLC)에 대해 entropy production rate의 각 부분((i), (ii), (iii))을 계산해 본다. 시간이 지남에 따라 inductor L은 asymptotic하게 short처럼 작동하고, capacitor C는 asymptotic하게 open처럼 작동함을 고려할 때 이러한 회로들은 시간이 지남에 따라 단순히 resistive한 회로처럼 작동하면서 일정한 전력을 소비하게 되는데, 이는 논문의 FIG. 1.과 FIG. 2.에서 보듯이 entropy production rate가 asymptotically constant하게 계산되는 것에 의미적으로 부합하는 결과이다. 또한 초반의 transient한 상태에서는 계의 엔트로피도 증가하나, 시간이 무한대로 지남에 따라 asymptotically 도달하는 steady state에서는 계의 엔트로피는 고정되고, 생성되는 엔트로피가 모두 계의 외부로 전달됨을 알 수 있다.




2. 논문 소개: 확률적 동역학 시스템에서의 정보 전달

  이 문단에서는 이차 시스템(2차원 시스템)에서의 변수 간의 정보 전달에 초점을 맞춘 연구 논문 <Information flow within stochastic dynamical systems>(X. San Liang, Physical Review E, 2008)을 소개한다([2], arxiv 링크). 벡터 \( \vec{x} = {\begin{bmatrix} x_1 & x_2 \end{bmatrix}}^T \)와 미분방정식 \( d\vec{x} / dt = f(\vec{x}, t) \)로 표현되는 동역학 시스템에 대하여, 위의 논문 [1]과 동일한 방식으로 joint entropy \(H = -\int \int \rho \log \rho dx_1 dx_2 \)가 정의된다. 여기서, 결정론적 시스템임에도 불구하고 entropy가 정의될 수 있는 이유는, initial condition을 달리함에 따라 서로 다른 무수히 많은 trajectory들이 발생하므로 이들을 모아서 생각할 수 있기 때문이다.

  이 때 joint entropy \(H\)는 다음의 미분방정식을 따름이 알려져 있다.
\[ \frac{dH}{dt} = E[\nabla \cdot f] \]
  그러나 standard Wiener process \(\vec{w}\)를 이용하여 stochasticity가 도입된 확률적 동역학 시스템 \( d\vec{x} = f(\vec{x}, t)dt + B(\vec{x}, t)d\vec{w} \)에서는 위처럼 entropy가 만족하는 미분방정식을 state할 수 있는 elegant form이 없다고 한다(엔트로피의 정의는 같다). 따라서 \(dH_1/dt\)를 evaluate하기 위해 \(\rho\)와 marginal distribution \( \rho_1, \rho_2 \)가 따르는 Fokker-Planck 방정식을 활용해야 한다. 한편, \(x_2\)가 frozen된 조건 하에서의 엔트로피 \(H_{1,2}\)에 대해서는 \(dH_{1,2} / dt\)를 evaluate할 때 Fokker-Planck 방정식으로 할 수 없으며, 보다 fundamental하게 미분의 정의로 돌아가서 계산을 해야 한다. 해당 계산이 이 논문의 첫 번째 핵심적인 논의라고 할 수 있을 것이다.

  이렇게 \(dH_1/dt\)와 \(dH_{1,2} / dt\)를 계산하고 나면, 다음과 같이 정의되는 정보 전달률(rate of information transfer)를 계산할 수 있게 된다. 상태변수 2에서 상태변수 1로의 정보 전달률 \(T_{2 \rightarrow 1}\)는 다음과 같이 정의된다.
\[ T_{2 \rightarrow 1} = \frac{dH_1}{dt} - \frac{dH_{1,2}}{dt} \]
  위에서 evaluate한 엔트로피 표현식을 바탕으로 이를 계산해 주면 다음과 같다(여기서 \(g_{ij}\)는 시스템의 stochastic perturbation을 나타내는 텐서의 각 성분으로, [1]의 diffusion matrix에 해당하는 것이다). 엔트로피를 바탕으로 상태변수들 사이의 정보 전달률을 계산하는 식을 만드는 이 부분이, 본 문헌의 두 번째 핵심적인 논의라고 할 수 있을 것이다. 여기서 연산자 \(E_{i|j}\)는 확률분포 \( \rho_{i|j} \) 위에서 evaluate되는 conditional expectation을 의미한다.
\[ T_{2 \rightarrow 1} = - E_{1|2}[ \frac{\partial(F_1 \rho_1)}{\partial x_1}] + \frac{1}{2} E_{2|1}[ \frac{\partial ^2 ( g_{11} \rho_1 )}{\partial x_1^2} ] \]
\[ T_{1 \rightarrow 2} = - E_{2|1}[ \frac{\partial(F_2 \rho_2)}{\partial x_2}] + \frac{1}{2} E_{1|2}[ \frac{\partial ^2 ( g_{22} \rho_2 )}{\partial x_2^2} ] \]
  이로써 확률적 거동을 하는 이차 시스템에서 각 상태변수 간의 정보 전달률을 정의하고 계산하였다. 이 식에서 발견할 수 있는 몇 가지 흥미로운 aspect를 열거하자면, (i) 만약 시스템의 stochastic perturbation이 변수 \(x_2\)로부터 독립적이라면, \(x_2\)에서 \(x_1\)로의 정보 전달률은 이 시스템과 대응되는 결정론적 시스템의 정보 전달률과 동일하다는 것, (ii) 만약 \(x_1\)의 evolution이 \(x_2\)와 독립적이라면 \(T_{2 \rightarrow 1} = 0\)이라는 것 등이 있다. 이는 정보 전달률이 그 자체로 consistent하고, 그 의미에도 부합하도록 잘 정의된 값이라는 것을 시사한다.

  논문의 FIG. 1.에서는 예시된 간단한 시스템에 대해 동역학의 시늉내기 결과를 보여주는데 여기서 위의 aspect (ii)와도 연관되는 매우 흥미로운 점이 드러난다. 이것은 바로 \(T_{1 \rightarrow 2} \neq 0\)인 반면, \(x_1\)과 \(x_2\)가 서로 거의 똑같은 양상으로 evolve하면서 매우 높은 correlation을 보여줌에도 불구하고, \(T_{2 \rightarrow 1} = 0\)이라는 것이다. 즉, 정보 전달률을 이상과 같이 정의하면 단순한 상관관계 분석만으로는 알 수 없는, 인과관계에 대한 지식이 정량적으로 imply되는 것이 가능하다는 것이다. 이는 수학적으로 보면 conditional probability가 involve되어 있기 때문이라고 생각할 수 있다.



3. 논문 소개: 기타

  이상의 두 논문보다 시기적으로 앞서서 쓰인 <Steady State Thermodynamics of Langevin Systems>(Takahiro Hatano and Shin-ichi Sasa, Physical Review Letters, 2001)에서 역시 stochasticity가 involve된 Langevin 타입의 동역학 시스템에 대하여 Shannon entropy를 위의 두 논문과 정확히 동일하게 정의하고, Jarzynski equality를 바탕으로 이 시스템의 정상상태(steady-state) 열역학을 전개하며, 이러한 formalism은 Crooks의 fluctuation theorem과 consistent하다는 것도 특기된다([3], arXiv 링크).

  한편, 무인 항공기(UAV) 등 기계적 agent들의 동역학을 연구해 온 항공공학자 J. G. Manathara의 <Entropy as a measure of consensus on large networks>(J. G. Manathara, working manuscript, 2013)에서는, \(N\)개의 수많은 agent가 네트워크로 연결되어 있는 multi-agent system(혹은 network system) \( \dot{\vec{x}} = f(\vec{x}) \)에서의 consensus(혹은 synchronization, 각 상태변수들의 값이 서로 일치되는 현상)의 척도로 entropy가 사용될 수 있음을 제시한다. Agent가 충분히 많아서 네트워크의 nodal value들의 distribution \(f(x)\)를 논할 수 있을 경우에, entropy는 다음과 같이 정의된다.
\[ H = - \int f \log f dx \]
  이렇게 정의된 엔트로피는 각각의 agent들의 동역학이 서로 일치될수록 그 값이 작다는 것이 시늉내기를 통해 확인되며, 그 의미상으로도 물리학에서 엔트로피를 무질서도라고 해석하는 것과 일맥상통한다. 따라서 이 양을 consensus의 척도로 사용할 수 있다. 또한 이 양은 기존에 consensus의 척도로 많이 사용되어 온 mean square 타입의 error에 비해서 consensus의 판단에 있어 훨씬 더 엄격하다(문헌의 Figure 1). 즉, mean square error는 시간에 따라 consensus가 달성되는 시스템에서 초반부터 상당히 급격하게 감소하나, entropy는 마치 sigmoid function과 유사한 개형으로, 초반부에는 느리게 감소하다가 후반에 consensus가 많이 달성되면 그 때에야 변곡점을 거치며 민감하게 감소하는 양상을 보인다([4], 저자 홈페이지 링크).

  이외에도 entropy, network dynamics 등의 keyword를 포함하여 인터넷 검색을 해 보면 opinion dynamics 등 다양한 multi-agent dynamical system에 대해 entropy를 정의하여 과학적 탐구 및 공학적 활용을 꾀하는 문헌들이 많이 있음을 알 수 있다.



4. 종합적 고찰: comment on the 'distribution' approach

  동역학 시스템에 대하여 probability distribution으로 접근하는 Fokker-Planck approach는 근본적으로, noisy term이 가지는 stochasticity에 의해 발생하는 가능한 trajectory들을 모두 모아서(이는 평형 통계역학에서의 ensemble approach에 대응된다) 고려하겠다는 것과 동등한 철학이다. 그리고 이상에서 소개한 4개 논문 모두에서, entropy 및 그것으로부터 유도되는 information transfer 등을 정의할 때에 항상 이러한 확률분포의 관점이 채택되고 있음을 확인할 수 있다. 즉, 확률분포의 개념이 들어가 있지 않은, 1개의 sample trajectory만으로는 엔트로피라는 물리량이 제대로 정의되지 않는다. 이는 엔트로피가 근본적으로 통계역학적인 개념인 이유이다.

평형 통계역학에서도 주어진 constraint하에서 가능한 모든 상태들의 configuration에 대한 정보가 주어져야 entropy를 제대로 계산할 수 있으며(\(  S = - \sum_{r}{P_r \log P_r} \)), '계가 지금 \(r = r_1\)이라는 상태에 있다'라는 것을 알려주는 sample snapshot 하나만으로는 엔트로피가 제대로 정의되지 않는다.

그렇다면 자유도가 dramatically reduce되고 fluctuation이 제거되어 결정론적인 trajectory를 따르는 것처럼 보이는 '열역학'에서는 엔트로피라는 값이 어떻게 정의되고 계산될 수 있는 것인가? 대표적으로 일반물리학에서부터 학습하여 잘 알고 있는 이상 기체의 열역학을 생각해 보자.

이 문제를 해결함에 있어서 중요한 것은, 열역학에서는 microstate의 configuration에 따라 발생하는 fluctuation이 '제거된' 적이 없으며, 다만 전체 시스템의 크기에 비해 그 fluctuation이 매우 작아, 확률분포의 deviation이 매우 작을 뿐이라는 것이다. 그러한 상황에서 average dynamics를 따로 정의한 것이 바로 우리가 알고 있는 열역학의 식들이다. 즉 우리는 열역학에서 주로 average dynamics만을 tracking하지만, microstate configuration의 많은 가능성에 따른 deviation은 결코 없어지지 않았으며, (비록 그 상댓값이 매우 작을지언정) 늘 average dynamics와 함께 존재하고 있는 것이다. 그리고 바로 그 configuration의 다양한 가능성으로부터 엔트로피가 정의되고 계산되게 된다.

이 점을 보다 명확히 확인하려면, 준정적 과정(quasi-static process)과, 자유 팽창(free expansion)으로 대표되는 비평형 과정을 비교해 보면 된다. 논문 [1]을 소개하는 문단에서 살펴보았듯, 준정적 과정에서는 \( \Delta S = \int \frac{dQ}{T} \)가 근사적으로 성립하는 반면 자유 팽창과 같은 비평형 과정에서는 좌변이 항상 같거나 크게 되고, 그 차이만큼이 바로 entropy production에 해당한다. 즉 우주에서 기존에 없던 엔트로피가 새로 생겨나는 것이다.

열역학으로 올바르게 기술되는 준정적 과정(이는 자유 팽창과 가열/냉각을 지극히 작은 간격으로, 오랜 시간 간격으로, 지극히 많은 횟수만큼 단계적으로 반복하는 '느리고 답답한' 과정이라고 할 수 있다)에 비해서, 자유 팽창의 경우에는 trajectory의 deviation이 매우 크다. 즉, 처음 상태에서 나중 상태로 갈 때에 가능한 trajectory들의 폭이 매우 넓으므로 그 중간 과정의 average dynamics만을 추적하여 진술하는 것이 크게 의미가 없게 된다. 이러한 경우가 바로 비가역적 과정이며 entropy production이 발생하게 되는 것이다.

- 끝 -



[1] Landi, Gabriel T., Tânia Tomé, and Mário J. De Oliveira. "Entropy production in linear Langevin systems." Journal of Physics A: Mathematical and Theoretical 46.39 (2013): 395001.

[2] San Liang, X. "Information flow within stochastic dynamical systems." Physical Review E 78.3 (2008): 031113.

[3] Hatano, Takahiro, and Shin-ichi Sasa. "Steady-state thermodynamics of Langevin systems." Physical review letters 86.16 (2001): 3463.

[4] Manathara, Joel G., "Entropy as a measure of consensus on large networks.", working manuscript, retrieved from jgmanathara.files.wordpress.com/2013/01/conentpy.pdf (2019.10).


Monday, October 7, 2019

Centrality Measures of Graphs: Mathematics, intuitions, and some notable issues

그래프의 중심성 척도: 수식, 직관, 그리고 몇 가지 주목할 만한 사항들

하단에 Embed된 pdf 파일은 2019-2학기 전기정보공학부의 '비선형제어특론'(심형보 교수님)의 수업을 통해 Francesco Bullo의 책 <Lectures on Network Systems>를 기반으로 하여 제작하게 된 발표자료이다. 그래프(혹은 네트워크)에서 어떤 노드가 구조적으로 중요한 역할을 하는지 측정하기 위한 다양한 지표들(중심성 척도, 중심도)에 대해 공부하여 개략적으로 정리하였고, 가능하다면 응용 사례도 첨부하고자 하였다.

첫째로 가장 기본적이라고 할 수 있는 차수 중심도(Degree centrality)는 각 노드가 몇 개의 간선(edge)을 가지고 있는지 세어 주는 것이다. 복잡 네트워크 과학 분야의 역사적 발달에 있어서, 차수 중심도의 분포가 멱법칙을 띠는 네트워크인 '척도 없는 네트워크'에 대해 A.-L. Barabasi, R. Albert, H. Jeong 등이 수행한 일련의 연구가 중요한 역할을 하기도 하였다.

고윳값 중심도(Eigenvalue centrality)는 특정 노드의 중심성을 평가할 때, 그 주변 노드의 중심성까지 고려하겠다는 철학으로 개발되었다. 각 노드의 중심도를 구하는 방정식이 고윳값 방정식의 형태를 보인다는 점에서 이와 같이 이름붙여진 것 같다. 주변 노드의 개수뿐 아니라, 주변 노드의 중요성 또한 자신의 중요성에 영향을 미치게 된다. 한편 카츠 중심도(Katz centrality)의 경우 차수 중심도와 고윳값 중심도의 특징을 합쳐 놓은 것이라고 할 수 있다.

다음으로 다룰 페이지랭크 중심도(PageRank centrality)는 구글의 창업 기반이 된 것으로 유명하며, 검색 순위 결정을 위해 각 웹 페이지의 유명세를 평가하는 데 사용되었다. 재미있게도 발명자이자 구글 창업자인 래리 페이지(Larry Page)의 이름을 따서 명명된 것이라고 한다. 페이지랭크 중심도의 철학은, (i) 어떤 웹 페이지가 유명한 페이지에게 인용당할수록 더 높게 평가되는 것, (ii) 무차별 수집가(collector, 수많은 페이지를 인용하는 페이지)보다는 세심한 비평가(delicate critic, 적은 수의 페이지만 선별하여 인용하는 페이지)에게 인용당할수록 더 높게 평가되는 것으로 요약될 수 있다.

마지막으로 다룰 Betweenness centrality(BC)closeness centrality(CC)의 가장 큰 특징은, 그 정의상 노드 1개의 중심성을 평가하는 데에 네트워크 전체가 직접적으로 involve되는 것이라고 할 수 있겠다. 네트워크 상에서 정보가 전달된다고 보았을 때, 특정 노드를 대체할 만한 경로가 없어 '병목 현상'이 일어날 경우 그 노드는 큰 BC 값을 가지게 된다.

한편, 네트워크는 spatial embedding을 가지고 있지 않은 구조이지만 노드간의 거리를 통해 대략적인 '지름'를 정의할 수 있는데, CC는 그 척도라고 할 수 있겠다. 어느 노드를 중심으로 CC를 평가하느냐에 따라 지름이 다르게 평가되게 되며, 지름이 작을수록 해당 노드는 전체 네트워크와 밀접하게 연결되어 있다는 뜻이 된다.

Wednesday, September 25, 2019

Evaluating Eigenvalues of the Adjacency Matrix associated with Cycle Graph

순환 그래프 인접행렬의 고윳값 구하기

Francesco Bullo의 책 <Lectures on Network Systems>의 연습문제 4.18(ii)에서는 순환 그래프(cycle graph)에 대응되는 인접행렬의 고윳값을 구하도록 지시하고 있다. 하단에 embed된 pdf 파일에서는 이 행렬이 circulant matrix의 특수한 경우임에 착안하여 증명을 제시하였다.


Sunday, July 28, 2019

[Review] Why is artificial neural network successful?: explanation based on spectral ergodicity

[리뷰] 인공신경망은 왜 성공적인가?: spectral ergodicity에 근거하여 설명하기

0. 개요

이 게시물에서는 각광받고 있는 최적화 기법인 인공신경망의 원리에 대해 일반론적으로 짧게 개괄한 뒤, 인공신경망의 높은 성능을 이론적으로 설명하고자 하는 가설적 시도로서 무작위 행렬 이론(random matrix theory)를 활용한 논문<Spectral ergodicity in deep learning architectures via surrogate random matrices>(M. Süzen et al., arXiv preprint arXiv:1704.08303, 2017)을 소개한다(arXiv preprint 링크). 논문에 대한 몇가지 코멘트와 함께, 보완된 논의를 제안하고 논문이 가지는 한계점에 대해서도 살펴본다. 관심을 가지고 읽어 주시는 분이 계시다면, 위 링크의 논문과 함께 읽기를 권한다.

1. 신경망 개요

시그모이드(sigmoid), 정류 선형 유닛(Rectified Linear Unit, ReLU) 등의 비선형 활성함수(activation function)를 가지는 인공신경망(artificial neural network)은, 네트워크의 구성 단위인 각 퍼셉트론(perceptron) 간의 연결 강도(weight)들과 바이어스(bias) 값들을 적절하게 선택함으로써 임의의 함수에 대한 보편적 근사기(universal approximator)로 작동한다.

신경망은 주로 그 아키텍쳐가 그림으로 나타내어지기 때문에 다소 생소하게 느껴질 수 있다. 그러나 사실 신경망이란 다름이 아니라, 수많은 똑같은 비선형 함수들이 scaling, biasing되고 서로 합성(고교 교육과정에서 배우는 '함수의 합성'이다)되어 있는 것뿐이라고 할 수 있다.

전기전자공학이나 기계공학 분야에서 제어 이론(control theory)를 공부해 본 사람이라면, 복잡해 보이는 block diagram이 다름이 아니라 결국 한 줄의 미분방정식을 공학적 활용을 위해 도식화시킨 것일 뿐임을 알 수 있을 것인데, 신경망의 도식적 표현도 마찬가지인 것이다.

어찌되었든 우리는 이렇게 표현된 신경망의 각각의 연결 강도 값들을 모아서 행렬로 구성할 수 있는데(주로 층층이 깊게 쌓여진 아키텍쳐를 사용하고(그래서 '딥 러닝'(deep learning)'이다), 이 때 n번째 층에서 n+1번째 층으로 연결되는 연결 강도 값들을 n번째 행렬로 구성하게 된다), 이를 weight matrix라고 부른다. 이렇게 하면 신경망의 최적화 과정(즉 신경망이 표현하는 함수가 우리가 원하는 target 함수에 가까워지도록 만드는 과정)은 곧 weight matrix의 각 성분들을 update하는 과정이 된다.

이러한 update(혹은 training)는 weight 값들을 인자로 받아 한 개의 scalar 값으로 보내는 오차 함수(error 혹은 loss function)을 정의하여, 그러한 오차 함수의 값을 작게 만드는 과정으로 이루어진다(gradient descent와 그 변형인 SGD, RMSprop, Adam 등이 바로 이러한 과정을 잘 수행하기 위한 알고리즘들이다).

이 때 각 성분들을 변화시킴에 따라 오차 함수가 유일한 minimum point를 갖는다는 보장이 없으므로, 출발점(즉 weight matrix의 초기조건)에 따라서, 최적화 과정을 거쳐 도달하는 종착점이 달라질 가능성이 있게 된다. 초기조건을 잘못 설정해 버리면, 오차 함수를 훨씬 더 줄일 수 있는 좋은 종착점이 있음에도 불구하고 그렇지 못한 애매한 종착점에서 멈출 수 있는 것이다.

그러나, 일반적으로 오차 함수에는 대칭성이 아주 많이 존재하여, 우리의 우려에 비해서 상황이 그렇게 나쁘지만은 않다는 것 역시 어느 정도 알려져 있기도 하다[1]. 오차 함수에 수많은 대칭성이 존재하는 이유는, 신경망의 통상적인 architecture상, weight 두 개가 서로 swap되어도 상관없는 경우가 아주 많기 때문이라고 설명될 수 있다.




2. 논문 소개

이 게시물에서 소개할 문헌([2], 위에 링크됨)에서는 (신경망의 weight matrix들의 ensemble에 착안하여) random matrix ensemble의 spectral ergodicity라는 지표를 새롭게 제안하였고, 몇 종류의 유명한 random matrix ensemble(CSE, CUE, COE)에서 matrix size가 커짐에 따라 그 지표가 일관적으로 빠르게 감소함을 전산적으로 시늉내어 확인하였다.

이 결과는, 신경망을 활용한 머신러닝 아키텍쳐에서 layer의 크기가 커질수록 그 layer의 spectral ergodicity가 개선됨을(감소함을) 의미한다. 즉 layer의 크기가 커질수록, 특정한 1개의 training 결과가, 모든 가능한 샘플들에 대한 평균적 결과에서 그리 멀리 떨어져 있지 않게 됨을 시사한다. 이는 신경망을 활용한 최적화가 왜 성공적인지에 대한 가설적인 설명이 될 수 있다고 저자들은 주장한다.

이 논문은 사실 그 이론적 내용상으로만 보면 기계학습(machine learning)과의 직접적인 연관이 있다기보다는, random matrix theory 분야의 꽤나 간단한 실험수학(?) 정도에 해당한다. 그럼에도 불구하고 이 논문을 신경망 아키텍쳐를 활용한 머신러닝과 결부지어 볼 수 있는 근거는, 여기에서 제안한 spectral ergodicity라는 지표가 다름이 아니라 신경망에서 착안된 것이며, 그렇기 때문에 결과적으로 신경망의 성능에 대한 가설적 설명을 제공한다는 것 정도이겠다.




3. 추가적인 코멘트

(1) 보론: 대칭성 논의

위의 문단에서 언급했듯이, 이 논문은 그 내용상 단순히 random matrix ensemble들의 spectral ergodicity를 평가한 것이므로 그 결과를 인공신경망의 성능과 직접 결부짓고자 한다면 보완된 논의가 필요하다. 여기서는 그 근거를 1에서 언급한 대칭성 논의에서 찾아보고자 한다.

이 논문이 인공신경망과 결부되어 의미를 가지려면, 분석에 사용한 random matrix ensemble들에서 각각의 matrix를, 신경망의 weight matrix를 임의의 초기조건에서 출발시켜 training한 결과로서 나온 '종착점'들로 간주할 수 있어야 한다. 그래야만, 임의의 출발점으로부터 training한 결과들이 서로 크게 다르지 않아, 초기조건에 관계없이 이 신경망이 믿을 만한 결과를 준다고 이야기할 수 있기 때문이다. 위의 '1. 신경망 개요'에서, 그러한 종착점들은 주로 상당히 많은 대칭성을 가지고 있다는 것을 이미 설명하였다.

그런데, 이 논문에서 분석에 사용한 3종의 random matrix ensemble들 모두에서, eigenvalue들의 모임의 example을 복소평면에 나타내어 보면 모두 원형 대칭성을 가짐이 확인된다(논문의 FIG. 1.). 따라서, 이 논문에서 사용한 random matrix ensemble들은, 우리가 설명해야 할 인공신경망 training의 종착점들의 집합과 (대칭성을 가진다는 측면에서) 어떤 면에서 분명히 닮아 있음을 알 수 있다.

이상의 보론을 거치면 논문의 실제 내용과 그 신경망에서의 함의 사이에, 보다 덜 비약적인 설명이 가능하다. 다만 여기서 행렬의 eigenvalue 분포의 대칭성이, 행렬의 weight들 사이의 swap symmetry를 비롯한 weight space 상에서의 symmetry와 대응이 잘 되는 개념인지는 초등적인 선형대수학적 감각을 동원하여 직관적으로만 이해해 보았고, 수학적으로 정확한 argument는 제시하지 못하였다.


(2) 에르고딕성의 개념과 관련하여

에르고딕성(ergodicity)이란 통계물리학에서 유래된 개념으로, 어떤 시스템에서 잠재적으로 가능한 모든 trajectory들의 collection에서 특정 물리량의 평균을 구한 것(ensemble average)과, 한 개의 sample trajectory에서 그 물리량의 긴 시간 동안의 평균을 구한 것(time average)가 일치하는 성질을 말한다.  즉, 매우 단순하게 말해서, 한 개의 trajectory만 계속 추적해도 전체 ensemble의 특징을 알 수 있다는 것이다. 여기서 알 수 있듯, ergodicity의 본래적 개념은 시스템에 따라서 성립하거나/성립하지 않는 '성질'(property)이지, 정량화되어 값을 가지는 '지표'(quantitative measure)가 아니다.

그렇다면 이 논문에서는 정량화된 지표를 제시하면서 왜 spectral 'ergodicity'라는 이름을 붙였을까? 이것은 단순히 하나의 sample matrix가 다른 matrix들과(따라서 전체 ensemble과) 크게 다르지 않은 결과를 준다는 결론이, 위에서 서술한 에르고딕성의 개념과 의미상으로 어떤 면에서 유사하기 때문으로 보인다.


(3) 한계점: 그럼에도 불구하고....

이 논문에서는 인공신경망에서 단일 layer의 크기(너비, width)가 클수록 training 결과가 믿을 만함을 이야기하고 있다. 이것이 바로 이 논문의 한계이다. 기계학습 분야에서 널리 알려진 사실은, 인공신경망을 '넓게' 쌓는 것보다는, '깊게', 즉 층층이 쌓을수록 성능이 좋아진다는 것이다(물론 깊게 쌓음에 따라 발생하는 vanishing gradient 등의 문제는 적절한 활성함수의 선택, 배치 정규화(batch normalization) 등을 통해서 해결해야 한다).

그러나 이 논문은 신경망의 깊이에 대해서는 어떠한 논의도 하고 있지 않다. 따라서 이 논문은 인공신경망의 성능에 대한 위의 사실에 비추어 볼 때 묘하게 핀트가 어긋나 있는 면이 있다. 이를 해결하려면 신경망의 깊이에 대한 논의까지 포함할 수 있도록 문제 정의를 확장시켜야 할 것이다.

그러나 각각의 layer는 비선형 활성함수를 통해 연결이 되어 있으므로, 단순히 모든 layer를 포함하도록 weight matrix를 더욱 크게 잡는 정도의 작은 수정만으로 해결이 되기는 쉽지 않아 보인다. 설령 그렇게 한다고 하더라도, 깊이를 키우는 것과 넓이를 키우는 것 사이에 spectral property가 명백한 질적인 차이를 갖도록 matrix를 구성해야 하는데 이것이 가능한지 또한 의문이다. 따라서, 이 논문의 framework와의 연속성을 유지하면서, 신경망의 깊이와 관련된 argument까지 도출해 낼 수 있는 방안을 아직까지는 생각하지 못하였다.




4. 참고 문헌

[1] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016

[2] Süzen, Mehmet, Cornelius Weber, and Joan J. Cerdà. "Spectral ergodicity in deep learning architectures via surrogate random matrices." arXiv preprint arXiv:1704.08303 (2017).


- 끝 -