The Postulate of Equal a Priori Probability: In the Sense of Gibbs Entropy Maximization

선험적 동등 확률의 원리: 깁스 엔트로피 최대화의 관점에서

아래의 pdf 파일에서는 별도의 구속조건이 없는(추가적인 정보가 주어지지 않은) 확률변수로 표현되는 시스템에 대하여 깁스 엔트로피(Gibbs entropy)를 최대화하는 확률분포는 확률변수의 가능한 모든 상태에 대해 같은 값을 가지는 분포임을 초등적인 미적분을 통해 증명하였다. 이러한 결과는 통계물리학의 선험적 동등 확률의 원리(Postulate of Equal a Priori Probability)에 부합하며, 정보이론적 함의도 가진다고 할 수 있다.

 

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의 특수한 경우임에 착안하여 증명을 제시하였다.

[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).

- 끝 -

[Review] Scale-free Networks: Historical view

[리뷰] 척도 없는 네트워크: 역사적 조명

  1990년대 후반에서 2000년대 초반 동안에 물리학계에서 급격히 성장한 복잡계 연구, 그 중에서도 복잡 연결망(complex network)에 대한 연구는 비단 물리학 내에서뿐만 아니라 생물학, 공학 등의 인접 분야에도 그 영향을 발휘했으며, <링크> 등의 서적을 통해 대중적으로 널리 알려지기도 했다.

  그 과정에서 가장 주목받은 학자 중 한 명은 (<링크>의 저자이기도 한) 알버트-라슬로 바라바시(Albert-Laszlo Barabasi)일 것이다. 그는 1999년부터 2000년대 초중반의 기간 동안 레카 알버트(Reka Albert), 정하웅(Hawoong Jeong) 등의 학자와 공동으로, 다양한 실제 시스템에서 관찰되는 '척도 없는 네트워크'(scale-free network), 그리고 그러한 네트워크를 절차적으로 생성하는 무작위성을 가진 수학적 모형인 '바라바시-알버트 모형'(Barabasi-Albert model, BA model)과 관련된 일련의 유명한 논문들을 발표하였다([1]-[4]).

  이러한 일련의 논문들을 통해 척도 없는 네트워크는 그 이론적 특성의 골자가 정리되면서 대표적인 네트워크 모델로 확립되었고, 해당 논문들 중 많은 수가 2019년 현재를 기준으로 각각 수천 회 이상의 높은 인용(citation) 횟수들을 보이면서, 해당 연구 패러다임이 복잡계 과학의 발전에 주도적인 역할을 하였음을 증언하고 있다.

  조금 더 구체적으로 살펴보자면, 월드 와이드 웹(World-Wide Web)을 복잡 네트워크로 간주하고 분석하여 그 척도 없는 성질(scale-free property), 그리고 웹 문서간 거리의 가까움을 밝힌 1999년도의 논문[1]을 해당 패러다임의 시작점으로 볼 수 있다. 척도 없는 성질이라고 함은, 연결선 수의 분포 \(P(k)\)가 다음과 같이 \(2 < \gamma < 3\)인 멱법칙(power law)을 따름을 의미한다.
\[ P(k) \propto k^{-\gamma} \]

  다음으로, 척도 없는 네트워크를 절차적으로 생성해 낼 수 있는 바라바시-알버트 모형이 같은 해에 제안되었다[2]. 점이 하나씩 추가되어 기존의 네트워크에 연결되는 방식으로 성장(growth)하는 네트워크에서 선호성 붙임(preferential attachment, 부익부 규칙이라고도 함)을 규칙으로 삼을 때 척도 없는 성질이 나타난다는 것을 해석적으로 밝힌 이 논문은 2019년 현재를 기준으로 3만 회 이상의 매우 높은 인용 횟수를 나타내는 등, 역사적으로 중요한 의미를 가진다고 간주된다.

  [3]에서는 네트워크에 새로운 node가 추가되어 growth가 일어나는 것을 미분방정식으로 나타냄으로써, 바라바시-알버트 모형에 의해 생성되는 네트워크가 가지는 scale-free property에 대한 해석적인 설명이 제공된다. 논문 제목에 mean-field가 언급되고 있는데, 내용 상으로 보았을 때 mean-field approximation이 일어난 부분은 바로 바라바시-알버트 규칙에 의해 정해지는 a priori probability와, 실제 생성된 네트워크에서의 frequency가 같다고 가정함으로써, 생성될 수 있는 네트워크의 variation을 없앤 부분일 것이다. 이렇게 함으로써 모든 네트워크를 고려하는 것이 아니라 마치 '1개의 평균적인 네트워크'를 고려하는 것처럼 논의를 전개할 수 있게 된다.

  이렇게 1999년을 기점으로 학계에 알려진 척도 없는 네트워크는 2000년대에 접어들면서 더욱 많은 학자들에 의하여 더욱 활발하게 이론적으로 연구되어 그 특성이 정리됨과 동시에 실제 시스템에 대한 분석의 틀로도 활발히 적용되었으며, 특히 생물학 분야에의 적용이 두드러졌다. 효모의 단백질-단백질 상호작용 네트워크를 연구한 논문[4]에 수록된 아래의 도식은, 네트워크 과학 분야에 관심을 가지고 찾아본 사람이라면 종종 보았을, 꽤나 상징적인 도식이기도 하다.

  이러한 과정을 거치면서 발달된 척도 없는 네트워크 모형은, 비슷한 시기인 1998년에 제안되어 역시 많은 주목을 받은 왓츠(Duncan Watts)와 스트로가츠(Steven H. Strogatz)의 좁은 세상 네트워크(small-world network) 모형, 1950-60년대에 수학계에서 제안된 전통 있는 무작위 네트워크 모형인 에르되시-레니(Erdos-Renyi) 모형 등과 함께 복잡계 과학의 한 축을 이끌어 왔다고 볼 수 있을 것이다.

[1] R. Albert, H. Jeong, A.-L. Barabasi, 'Diameter of the world-wide web', 1999.09.

[2] A.-L. Barabasi, R. Albert, 'Emergence of scaling in random networks', 1999.10.

[3] A.-L. Barabasi, R. Albert, H. Jeong, 'Mean-field theory for scale-free random networks', 1999.10.

[4] H. Jeong, S. P. Mason, A.-L. Barabasi, Z. N. Oltvai, 'Lethality and centrality in protein networks', 2001.05.

딥마인드 데미스 허사비스의 재미있는 경력

어릴 때 Black & White라는 CD게임을 했었는데, 거기서 플레이어가 키울 수 있는 creature에 적용된 인공지능이 당시 게임 AI 중 최고 성능이라고 기네스북에 올랐던 것을 기억한다.

사진: Black & White 인게임 스크린샷.

그 AI의 주요 개발자가 바로, 훗날 알파고를 개발한 딥마인드(DeepMind)의 수장 데미스 허사비스다.

Facebook에서 이 글 보기: 링크