이항 관계(Binary relations)의 개념과 몇 가지 성질

어떤 집합 $A$에서 정의되는 이항 관계(binary relation), 혹은 단순히 관계(relation) $\mathrm{R}$는, 그 집합의 원소들의 순서쌍 $(x,y)$들을 원소로 갖는 어떤 집합이다.

이런 것을 왜 정의하는가? 일상 언어에서의 '관계가 있다'라는 말을 집합의 언어로 형식화한다고 생각하면 이해가 쉽다. 세 원소 $a,b,c \in A$ 가 만드는 순서쌍 중, 예를 들어서 $(a,b)$는 특정한 관계를 만족하지만, $(a,c)$는 그러한 관계를 만족하지 않는 상황을 얼마든지 생각할 수 있다. 이를 $(a,b)\in\mathrm{R}$, $(a,c)\notin\mathrm{R}$로 하여, '관계를 만족한다(만족하지 않는다)'는 것을 '집합 $\mathrm{R}$의 원소이다(원소가 아니다)'라고 형식화하는 것이다.

이때 이항 관계 $\mathrm{R}$에 별다른 조건은 없다. 즉 사람 눈으로 보기에 이게 정확히 어떤 관계인지 의미를 부여하기 어렵더라도 상관이 없다. 마치 함수(실제로 이항 관계는 함수의 일반화이다)가 반드시 우리가 아는 어떤 식 $f(\cdot)$를 이용하여 $y=f(x)$ 꼴로 간결하게 나타내어지거나 일상 언어로 의미가 부여될 필요는 없는 것과 같다.

이를 간단히 $a\mathrm{R}b$라고 표기하기도 한다. 이렇게 표기하면 상당히 생소해 보이지만, 결국 집합에 대한 이야기이므로 너무 낯설어하지 않아도 되며, 공부하다가 확실하지 않은 것은 집합의 언어로 풀어 쓰면서 확인하고 이해해 볼 수 있다. 그렇지만 이항 관계들을 능숙하게 다루기 위해서는 그렇게 매번 집합의 언어로 바꾸어서 다루기보다는, 이항 관계의 주요 성질들을 숙지한 뒤 $a\mathrm{R}b$와 같은 표기법을 바탕으로 다룰 줄 아는 것도 필요할테다.

이하에서는 주어진 이항 관계가 만족하거나 만족하지 않는 몇 가지 주요 성질들(비대칭성, (비)반사성, 반대칭성 등)을 소개하고, 집합과 논리를 연습할 겸 간단한 정리 1개의 증명을 다룬다.

1. 비대칭성(asymmetry)

$$\forall x,y \in A,\, (x,y)\in\mathrm{R} \Rightarrow (y,x)\notin\mathrm{R}.$$

이항관계 $\mathrm{R}$이 비대칭적(asymmetric)이라는 것은, $(x,y)$가 그 관계를 만족할 경우 이것을 뒤집은 $(y,x)$는 그 관계를 만족하지 않는다는 뜻이다. 집합의 원소를 점으로 표현하고 관계를 화살표로 표현하면, 이를 어떤 두 점 사이에도 화살표가 한 방향으로만 있어야 한다(혹은 아예 없거나)고 말할 수 있다. 그림을 통한 이해는 최하단 사진에서 볼 수 있다.

2. 반사성(reflexive)와 비반사성(irreflexive)

(1) 반사성

$$\forall a\in A, (a,a)\in\mathrm{R}.$$

이항관계 $\mathrm{R}$이 반사적이라는 말의 정의는, $A$의 모든 원소 $a$에 대해 $a$에서 출발해서 바로 자기 자신으로 돌아가는 화살표가 있어야 한다는 것이다 (여러 점을 거쳐서 다시 들어가는 것은 가능하다. 이항(binary), 즉 두 원소 사이의 관계이므로 이런 것은 고려의 대상이 아니다).

(2) 비반사성

$$\forall a\in A, (a,a)\notin\mathrm{R}.$$

이항관계 $\mathrm{R}$이 비반사적이라는 것은, $A$의 어떤 원소 $a$에 대해서도, $a$에서 출발해서 바로 자기 자신으로 돌아가는 화살표가 없어야 한다는 뜻이다. 이러한 비반사성은 단순히 '반사적이지 않다'는 것과는 다르다.

3. 반대칭성(antisymmetry)

$$\forall x,y\in A, \quad (x,y)\,\mathrm{and}\,(y,x)\in\mathrm{R}\,\,\Rightarrow\,\, x=y.$$

이항관계 $\mathrm{R}$이 반대칭적(antisymmetric)이라는 것은, 두 순서쌍 $(x,y),(y,x)$가 모두 $\mathrm{R}$을 만족하는 경우는 $x,y$가 사실 같은 원소인 경우뿐이라는 뜻이다. 이를 반대로 생각하면(대우명제) 더 쉬운데, $x,y$가 다른 원소일 경우에는 양쪽 화살표 둘 모두가 존재해서는 안 되고, 한쪽만 있거나 아예 없어야 한다는 뜻이다. 자기 자신에서 나와서 자기 자신으로 들어가는 화살표는 가능하다.

이상의 정의로부터, 어떤 이항관계가 반대칭인데, 자기 자신에서 나와서 자기 자신으로 들어가는 화살표까지 없으면, 그 이항관계는 비대칭이라는 것은 직관에 따라 비교적 명확하다. 실제로 다음이 성립한다. 즉 비대칭성과, '반대칭성 & 비반사성'은 서로 필요충분조건이다.

$$\textrm{R is asymmetric}\,\,\Leftrightarrow\,\,\textrm{R is irreflexive and antisymmetric}$$

이를 집합의 언어로 증명해 보자. 증명 과정을 명료하게 써 보는 일, 그러면서도 그림을 통한 직관적인 이해와 align시켜 보는 일은 생각보다 재미있다.

① $(\Rightarrow)$

i) asymmetric $\Rightarrow$ irreflexive

이항관계 $\mathrm{R}$이 비대칭일 때,

만약 어떤 $a_1,a_2\in A$가 존재하여 $a_1=a_2\,(=a)$이고 $(a_1,a_2)\in\mathrm{R}$이라면 (가정)

비대칭성의 정의에 의하여, 순서를 바꾼 순서쌍 $(a_2,a_1)$ 은 $\mathrm{R}$의 원소가 아니다.

그러나 $a_1=a_2$이므로 실제로는 이는 원래 순서쌍과 동일하며 따라서 $\mathrm{R}$의 원소여야 한다는 결론이 나온다. 이는 모순이다. 따라서 가정은 잘못되었다.

즉, 어떠한 $a\in A$에 대해서도 $(a,a)\notin\mathrm{R}$이다. 곧, $\mathrm{R}$은 비반사적이다.

ii) asymmetric $\Rightarrow$ antisymmetric

이항관계 $\mathrm{R}$이 비대칭일 때,

$(x,y)\in\mathrm{R}\,\,\Rightarrow\,\,(y,x)\notin\mathrm{R}$이므로,

반대칭 여부를 판단하기 위한 조건인 $(x,y)\,\mathrm{and}\,(y,x)\,\in\mathrm{R}$을 만족하는 순서쌍 자체가 존재하지 않는다. 따라서 $x=y$는 vacuously true이다. 곧, $\mathrm{R}$은 반대칭이다.

② $(\Leftarrow)$

이항관계 $\mathrm{R}$이 비반사적이고 반대칭일 때,

만약 어떤 $(x,y)\in\mathrm{R}$에 대해 $(y,x)\in\mathrm{R}$이라면 (가정)

$x,y$의 관계는 같거나 다르거나 둘 중 하나인데,

$x=y$라면 $(x,x)\in\mathrm{R}$이므로 비반사성에 모순이고,

$x\neq y$라면, $(x,y)\,\mathrm{and}\,(y,x)\,\in\mathrm{R}$인데 $x\neq y$이므로 반대칭성에 모순이다.

따라서 어떤 경우에도 가정은 잘못되었다.

즉 모든 $(x,y)\in\mathrm{R}$에 대해 $(y,x)\notin\mathrm{R}$이다. 곧, $\mathrm{R}$은 비대칭이다.

①, ②를 종합하면, 증명하고자 했던 정리가 참임을 알 수 있다.

Facebook에서 이 글 보기: 링크

- 끝 -

딥러닝의 일반화 성능에서 'flat minima' 테제의 역사

뉴럴 네트워크가 지극히 성공적인 이유를 설명할 때 주로 핵심이 되는 키워드는 일반화(generalization)이다. 일반화란 주어진 데이터에 과적합(overfitting)되지 않고 새로운 샘플들이 들어와도 좋은 성능을 내는 능력을 말한다. 이는 모델의 단순성(simplicity)과도 어느 정도 관련된다. 모델이 지나치게 복잡하면 training set은 아주 잘 맞출 수 있겠지만, (동일한 가상의 분포로부터 왔다고 간주되는) 새롭게 주어지는 test set은 잘 맞추지 못하게 되기 때문이다.

문헌들에서는 딥러닝이 이러한 높은 일반화 성능을 보여주는 이유가, loss function landscape의 flat minima와 거의 동일시되는 경우가 많다. 뉴럴 네트워크의 가중치들이 SGD와 같은 최적화 과정을 통해 도달한 지점이, 뾰족하지 않고 널찍한 곳일 때에 일반화를 잘 한다는 것이다.

SGD를 포함한 표준적인 딥러닝 학습 알고리즘의 recipe가 신경망 가중치들로 하여금 왜 이러한 flat minima를 선호하게 되는지, 혹은 표준적인 recipe를 어떻게 수정해서 flat minima를 일부러 더 선호하게 할지에 대해서, 비평형 통계물리학을 포함한 다양한 관점에서의 많은 연구가 존재한다.

그런데 더 기본으로 돌아가서, 이러한 flat minima가 일반화 성능과 동일시될 수 있는 이유는 정확히 무엇인가? 근래의 딥러닝 논문들에서 이 주장을 정당화할 때, loss landscape가 조금 뒤틀어져도 (즉, 데이터셋이 조금 바뀌어도) 모델의 특성이 크게 바뀌는 게 없어서라고 직관적으로만 주로 설명한다. 이는 설득력이 있으며 일반적으로 널리 받아들여진다. 그러나 정말로 그러한지, 그리고 이론적으로는 어떻게 설명할 수 있는지는 별개의 문제이다. 이에 문헌 조사를 해 보았다.

[1] S. Hochreiter and J. Schmidhuber, "Simplifying neural nets by discovering flat minima," NIPS 1994.

[2] S. Hochreiter and J. Schmidhuber, "Flat minimum search finds simple nets," Technische Universität München Technical report FKI-200-94, 1994.

[3] S. Hochreiter and J. Schmidhuber, "Flat minima," Neural Computation 9(1), 1997.

찾아본 결과, 위 논문 [1]이 머신 러닝에서 flat minima가 generalization에 좋다는 것을 논의한 제일 첫 문헌인 것 같다. 나는 사실 NIPS (NeurIPS의 예전 이름)가 1994년에 존재했는지도 몰랐다.

같은 저자들의 1997년 논문([3], 제목이 그냥 flat minima인)이 보통 최초라고 간주되고 많이 인용되는데, 상대적으로 인용이 덜 된 위 문헌이 사실 몇 년 더 먼저이고, [3]에도 [1]이 이미 인용이 되어 있다. 아마 조금 더 자세한 기술적 디테일과 실험 결과를 담은 technical report([2], 웹 검색으로 찾기 조금 어려운 편인데 Schmidhuber의 웹사이트에서 다행히 찾을 수 있었다)와 함께 NIPS 1994에 먼저 리포트한 뒤에, 이를 종합하고 보완해서 정식 저널에 1997년에 출판한 것으로 보인다. 내용들은 거의 비슷비슷하다.

이 논문들 역시 flat minima에 대해 위에서 서술한 직관에서 출발하지만, 그것을 이론적, 실험적으로 보다 엄밀하게 보이고자 한다. 먼저, 모델이 generalization를 잘 하기 위해서 가급적 simple해야 한다는 것 자체는 이 논문 이전에도 널리 알려진 것 같다. 이를 위해서 좋은 Gaussian prior를 골라야 한다는 Hinton 등의 연구가 있었다고 한다. 또한 지금은 Santa Fe 연구소에서 계산의 열역학을 연구하고 있는 D. H. Wolpert의 연구 또한 이 대목에서 인용된다.

반면 이 연구에서는 prior에 덜 의존하면서도 높은 generalization 성능을 달성하기 위해, flat minima를 처음으로 제안한다. 위에서 이야기한 것처럼, flat minima 제안의 토대가 되는 직관 자체는 현재 우리가 이해하고 있는 것(모델이 simple함 $\rightarrow$ weight가 바뀌어도 GE가 많이 안 변해야 함 $\rightarrow$ flat minima여야 함)과 거의 일치한다. Prior에 대해 덜 엄격한 가정만이 필요하다는 것은, appendix A.1.에서 GE를 overfitting error와 underfitting error로 나누고, 전자에서 베이즈 통계 기반으로 정당화한다.

다음으로 모델의 simplicity를 정보이론 내지는 코딩 이론의 MDL (minimum description length) 을 이용하여 설득력 있게 정량화하고, 이것이 loss의 Hessian과 관련지어지므로 landscape의 flatness에 대응된다는 것을 appendix 및 technical report에서 보이는 것 같다. 이론적으로 가장 흥미로운 부분이다.

이를 바탕으로, 일반적인 mean square error에 flatness를 선호하게끔 하는 항을 explicitly 더해준 채로 gradient descent를 하고, noisy classification 및 recurrent network 문제에서 그 성능을 검증해 보았다고 한다.

다만 현대 딥러닝에서는 이 논문처럼 flatness를 일부러 선호하게 해 주는 대신, 'stochastic' gradient descent가 random process로서 갖는 통계적 특성 자체가 implicit하게 flatness를 선호하게 해 주는 효과를 갖는다고 이해되고 있으며 이는 비평형 통계물리학 이론을 통해서도 활발히 연구된 바 있다. SGD는 단지 batch size 절약을 통해 계산 비용을 절감하는 것뿐 아니라, 더 나은 minima에 도달하기 위한 과정인 것이다.

Flat minima를 포함해서, 현대적인 딥러닝의 recipe에서 표준에 가깝게 받아들여지는 각각의 요소가 여러가지 다원적인 기여에 의해 만들어지는 과정이 참 흥미롭다. 수십 년 동안 제안되고 발전되어 온 여러 방법 및 개념들 중에서도, inductive bias가 적고 large scale에서도 성공적으로 작동한다고 검증된 것들이, 현재 트랜스포머 기반의 초거대 ai 시대에도 현재진행형으로 역할을 하며 도도하게 남아있는 걸 보면 너무 멋진 듯하다 (정작 트랜스포머의 원류가 되는 Kyunghyun Cho 교수님의 attention mechanism 논문은 딥러닝 붐 초기라고 할수 있는 2014년에 나오긴 했다). 이러한 과정이, 마치 양자역학의 초기 역사처럼 과학기술사가들에 의해 잘 탐구되고 정리되면 좋을 듯하다.

한편, 저자인 Hochreiter는 Neural computation 9(8) 1997에서 LSTM(Long Short-Term Memory)을 최초로 제안한 연구자이기도 하다. 1967년생이라고 하니, 20대 후반~30대 초반에 이 일련의 중요한 논문들을 쓴 셈이다.

Linkedin에서 이 글 보기: 링크

Facebook에서 이 글 보기: 링크

Sanaka AI의 swarm intelligence와 AI Scientist의 관계가 그 윤곽을 드러내다

Sanaka AI는 자연-모방 계산(nature-inspired computing), 무리짓는 지능(swarm intelligence) 등을 테마로 해서 창업된 회사이다. 이 테마는 silicon photonics, reservoir computing, probabilistic 및 thermodynamic computing 등과 함께 비전형적(unconventional) 컴퓨팅, 그 중에서도 analog computing의 한 종류에 잠재적으로 해당할 수 있다.

그런데 Sakana AI가 발표한 초기 결과들(특히 굉장한 화제가 된 The AI Scientist: 링크)은 이 테마와는 언뜻 크게 관련 없어 보이는, LLM을 이용한 과학 연구 자동화 쪽이어서 나로서는 한동안 의아하게 생각하고 있었다. 그런데 ASAL(Automated Search for Artificial Life)을 비롯한 최근에 발표되는 결과들(ASAL 논문: https://arxiv.org/pdf/2412.17799 , LinkedIn 포스트: https://bit.ly/40fGL9Z )을 보니 이것이 회사의 본래 테마와 어떻게 연결되는지 어느 정도 이해가 된다.

내 과거 포스트 "세포 자동자와 능동 물질: 비교하고 접점을 탐색하기" (블로그 링크: https://lnkd.in/gbM_EGMz)에서는 SmoothLife 및 Lenia를 비롯한 세포 자동자(특히 전통적인 세포 자동자와 달리 연속적 공간에서 정의되는)의 여러 예시들을 간단히 소개하고, 제 연구 분야인 능동 물질(active matter)과의 연관성도 생각해 본 바 있다.

최소주의적 상호작용 규칙을 통해 자발적으로 구성되고 유지되는 이러한 '인공세포'들의 패턴형성과 각종 기능수행은 눈으로 감상하기에 매우 재미있을 뿐만 아니라, 무리짓는 지능을 구현할 수 있는 잠재력이 크다. Sakana AI의 창립자인 David Ha 역시 과거부터 이 분야에 관심이 많았다.

그러나 이들을 이용한 저전력 아날로그 계산이 실현되려면, 이러한 인공 세포들이 디지털 컴퓨터 속에서 고비용으로 emulate되는 데에 그치지 않고 실제 물리적 제약을 만족시킬 필요가 있다 (실제로 Lenia의 최근 버전인 Flow-Lenia는 보존법칙, 국소성을 비롯한 이러한 부분에 집중한 것으로 알고 있다. 논문 링크: https://bit.ly/3PzwMHr).

ASAL을 보니, Sakana AI가 과학연구 자동화 솔루션을 만든 목적 역시, 잠재적으로 존재할 수 있는 인공세포들의 거대한 공간 속에서, 원하는 형태론적 조건을 충족시키거나 원하는 기능을 수행하면서도 물리적 제약을 만족하는 상호작용 규칙을 LLM으로 광범위하게 탐색하고 자동적으로 찾아내는 데에 초점이 맞추어진 것 같다. 이러한 광범위한 탐색 과업은, 인간의 창조성이 기계를 통해 간접적으로 행사되게 함으로써 스케일을 키우고 자동화한 AI Scientist의 시도와 잘 어울려 보인다.

이러한 무리짓는 지능은 현재 주류 패러다임인 디지털 컴퓨터 기반의 계산뿐 아니라 다른 비전형적 컴퓨팅 방법과 비교하더라도 당장의 현실화와는 꽤나 거리가 있어 보인다. 그럼에도 앞으로 이 창의적인 분야의 방법론적, 내용적 발전을 더욱 기대하게 된다.

LinkedIn에서 이 글 보기: https://bit.ly/40uFjlc

Facebook에서 이 글 보기: 링크