장 첫머리의 물음으로 돌아가자. 퍼셉트론이 무작위 라벨을 모두 외울 수 있는지는 입력 수의 2배 근처에서 갈렸다. 홉필드 네트워크에서는 뉴런의 상태가 움직였지만, 퍼셉트론에서 움직이는 것은 가중치다. 가중치를 찾는 문제에도 같은 계산을 쓸 수 있을까?
역사: 가드너와 커버
에든버러 대학교의 엘리자베스 가드너는 1988년 1월 퍼셉트론의 용량을 가중치 공간의 부피로 계산한 두 논문을 발표한 뒤 그해 6월 서른 살로 세상을 떠났다. 그보다 앞서 커버(1965)는 일반적인 위치(어떤 N개를 골라도 원점을 지나는 한 초평면 위에 함께 놓이지 않음)의 점 P개에 ±1을 붙이는 라벨 조합 가운데 원점을 지나는 초평면으로 나눌 수 있는 것을 직접 세어, 그 비율이 P = 2N에서 정확히 1/2임을 보였다.
가중치 공간의 부피
가드너는 문제를 뒤집었다. 결합을 주고 스핀의 배치를 세는 대신, 데이터 P개를 주고 그 데이터의 라벨을 모두 여유(margin: 결정 경계에서 가장 가까운 입력까지의 거리) κ 이상으로 맞히는 가중치들의 부피를 쟀다. 데이터가 굳은 무질서이고 가중치가 요동하는 변수다. 이 부피를 가드너 부피 (모든 라벨을 여유 κ 이상으로 맞히는 가중치들의 부피, Gardner volume)라 한다.
데이터가 하나 늘 때마다 가능한 가중치가 반쪽씩 잘려 나가는 모습(입력 2개). 원은 길이를 고정한 가중치 전체이고, 초록 화살표는 데이터마다 라벨을 곱한 입력 방향, 점선은 그 데이터를 맞히는 쪽과 틀리는 쪽의 경계다. 남은 원호의 비율(보라)은 데이터 1개에서 1/2, 2개에서 0.31, 3개에서 0.15로 줄어든다. 이 남은 비율이 가드너 부피이고, 입력이 많으면 데이터 수가 입력 수의 2배에 이를 때 거의 늘 0이 된다.
부피 V는 가중치에 대한 경우의 수이고, 데이터에 따라 지수적으로 흔들리므로 알고 싶은 것은 ln V의 굳힌 평균이다. 가드너는 이것을 레플리카 방법으로 계산했다. 조건을 만족하는 가중치 두 개를 무작위로 뽑으면 데이터가 늘수록 둘의 겹침 q가 1로 다가가고, q = 1이 되는 곳이 용량이다. 가드너가 얻은 용량 식이 오른쪽 식이고, κ = 0이면 적분이 1/2이라 용량은 정확히 2다. 커버가 라벨 조합을 직접 세어 얻은 경계를, 가드너는 부피의 로그를 평균해서 얻은 것이다. 커버도 라벨 조합을 직접 세어 같은 2를 얻었는데, 그 셈은 아래 문제에서 평면부터 해 본다. 그래서 「퍼셉트론은 입력 수의 두 배까지 외운다」는 말은, 가중치 공간에서 해의 부피가 한 점으로 줄어 두 복제본의 겹침이 1이 되는 경계를 말한다. 입력을 x 대신 ξ^μ로 적은 것은 가드너 이후 통계물리 문헌의 관습으로, 홉필드 네트워크의 패턴과 같은 글자를 쓴다. 글자만 바꾼 것이고 뜻은 보통의 입력 x와 같다.
가드너의 식이 주는 가장 큰 여유를, 실제로 푼 여유가 가장 큰 분리 초평면과 비교한다.
import numpy as np
from scipy.stats import norm
from scipy.integrate import quad
from scipy.optimize import brentq, minimize
rng = np.random.default_rng(0)
def load_at(kappa): # 여유 κ로 외울 수 있는 가장 큰 P/N (가드너의 식)
return 1 / quad(lambda t: norm.pdf(t) * (t + kappa)**2, -kappa, np.inf)[0]
def max_margin(X, lab): # 여유가 가장 큰 분리 초평면 (쌍대 문제를 L-BFGS-B로)
A = lab[:, None] * X; K = A @ A.T
f = lambda al: (0.5 * al @ K @ al - al.sum(), K @ al - 1)
al = minimize(f, np.zeros(len(lab)), jac=True, method="L-BFGS-B",
bounds=[(0, None)] * len(lab), options={"maxiter": 20000, "ftol": 1e-15, "gtol": 1e-10}).x
w = A.T @ al
return np.min(A @ w) / np.linalg.norm(w) # 가장 가까운 점까지의 거리 (입력 길이 ≈ √N 기준)
print("κ = 0에서 외울 수 있는 P/N =", round(load_at(0.0), 3))
N = 400
for a in (0.5, 1.0, 1.5):
kappa_th = brentq(lambda k: load_at(k) - a, -5, 10)
ks = [max_margin(rng.standard_normal((round(a * N), N)), rng.choice([-1.0, 1.0], round(a * N))) for _ in range(10)]
print(f"P/N = {a}: 가드너 식의 κ = {kappa_th:.3f}, 실제 가장 큰 여유 {np.mean(ks):.3f} ± {np.std(ks):.3f}")
# κ = 0에서 외울 수 있는 P/N = 2.0
# P/N = 0.5: 가드너 식의 κ = 1.034, 실제 가장 큰 여유 1.059 ± 0.025
# P/N = 1.0: 가드너 식의 κ = 0.471, 실제 가장 큰 여유 0.467 ± 0.022
# P/N = 1.5: 가드너 식의 κ = 0.186, 실제 가장 큰 여유 0.189 ± 0.024
퍼셉트론의 가장 큰 여유는 입력 400개에서 이미 가드너의 식과 표준편차 안에서 맞는다.
ML에서: 교사가 라벨을 붙이면
라벨이 무작위가 아니라 교사 퍼셉트론 하나가 정해 준 것이라면 외우기는 늘 가능하고, 물을 것은 새 입력에서 얼마나 맞히느냐다. 1992년 승, 솜폴린스키, 티시비는 이런 교사–학생 설정(teacher–student setting)에서 뽑은 예제를 굳은 무질서로, 그 예제로 학습한 가중치를 요동하는 변수로 두고 예제로 배우는 학습을 통계역학으로 정리했다. 입력이 정규분포를 따르면 학생이 새 입력에서 틀릴 확률(일반화 오차)은 학생과 교사 가중치 사이의 각 θ 하나로 정해진다. 둘의 결정 경계 사이에 낀 쐐기 두 개에 든 입력에서만 답이 갈리고, 그런 입력의 비율이 θ/π이기 때문이다. 각의 코사인이 두 가중치의 겹침 R이므로 틀릴 확률은 arccos(R)/π다.
교사와 학생 퍼셉트론의 가중치(화살표)와 결정 경계(실선은 교사, 점선은 학생). 칠한 쐐기 두 개 안의 입력에서만 둘의 답이 갈리고, 두 쐐기의 각을 합하면 2θ이므로 학생이 틀릴 확률은 2θ/(2π) = θ/π다. 그림은 겹침 0.62, 곧 θ ≈ 51.7°인 경우로 틀릴 확률은 0.287이다.
입력 500개, 예제 수가 입력의 1·5·10배일 때 예제마다 라벨 × 입력을 더해 학생을 만들어 보면(헤브 규칙) 겹침 R은 0.620·0.869·0.929(입력이 많은 극한의 이론값은 0.624·0.872·0.930)이고, 새 입력에서 잰 오차는 0.286·0.162·0.120으로 arccos(R)/π와 거의 같다.
ML에서: 풀린 근사와 레플리카 이론
승, 솜폴린스키, 티시비(1992)는 논문 요약에서 어림 이론으로 「높은 온도 극한과 풀린 근사(annealed approximation)」를 들고, 예제를 뽑아 생기는 굳은 무질서를 정확히 다루면 레플리카 이론이 필요하다고 썼다. 이 문장은 이렇게 풀 수 있다. ln Z를 구할 때 Z를 데이터에 대해 먼저 평균하면 풀린 근사, 로그를 먼저 씌우면 굳힌 평균이고, 굳힌 평균이 전형적인 학습 결과를 준다.
문제 13. 핀을 지나는 자로 구슬 가르기
책상 가운데 핀을 꽂고 둘레에 구슬 P개를 흩어 놓는다(어느 두 구슬도 핀과 한 직선 위에 있지 않다). 구슬마다 동전을 던져 빨강이나 파랑을 칠한 뒤, 핀을 지나는 자 하나로 빨강과 파랑을 양쪽으로 가르려 한다. (가) P = 3, 4, 6에서 가를 수 있는 색칠은 2^P가지 가운데 몇 가지인가? (나) 민준이는 P = 4인 어떤 색칠에서 자를 10°씩 돌려 보다가 안 되자 가를 수 없다고 했다. 무엇이 문제인가?
핀을 지나는 자와 구슬 네 개. 빨강 둘, 파랑 둘이고 자는 핀을 지나는 직선으로만 놓을 수 있다.
김민준
자를 10°씩 한 바퀴 돌려 봤는데 이 색칠은 안 갈라져요. 구슬 네 개면 대부분 안 될 것 같은데요.
이서연
10°씩 돌린 건 시도일 뿐이야. 두 구슬 방향 사이가 3°밖에 안 되면 10° 간격으로는 그 사이에 자를 못 넣잖아. 셈으로 확인해야지.
선생님
자를 반 바퀴 돌리는 동안, 가르는 방식은 언제 바뀌죠?
이서연
자가 구슬 하나를 지날 때만요. 반 바퀴에 P번 바뀌니까 가르는 방식이 P가지예요.
선생님
색은요? 자의 어느 쪽이 빨강인지도 정해야 하죠.
이서연
두 가지니까 모두 2P가지예요.
김민준
그럼 P = 3이면 8가지 가운데 6가지, 4면 16가지 가운데 8가지로 절반, 6이면 64가지 가운데 12가지로 19%예요. 열쇠 꾸러미에서 몇 개만 꽂아 보고 맞는 열쇠가 없다고 한 셈이네요. 구슬 수가 평면의 차원 2의 두 배일 때 절반이고요.
선생님
문제에 「어느 두 구슬도 핀과 한 직선 위에 있지 않다」는 조건이 있었죠. 두 구슬이 핀을 사이에 두고 한 직선 위에 놓이면 어떻게 되죠?
이서연
자가 반 바퀴 도는 동안 그 두 구슬은 같은 순간에 지나가니까, 가르는 방식이 바뀌는 순간이 P번이 아니라 P − 1번이에요. P = 4면 2 × 3 = 6가지로, 8가지에서 줄어요.
김민준
그 두 구슬은 자의 늘 서로 반대편에 남네요. 둘을 같은 편에 넣는 색칠은 아예 안 되고요.
선생님
그래서 셈이 깔끔하려면 「일반적인 위치」라는 조건이 필요해요. 구슬을 무작위로 흩으면 그런 일이 일어날 확률은 0이고요.
문제 14. 퍼셉트론은 몇 개까지 외우나
입력 N = 100개인 퍼셉트론에 표준정규분포에서 뽑은 입력 P개와 무작위 라벨 ±1을 준다. (가) 퍼셉트론 학습 알고리즘을 입력 전체를 1000번 훑을 때까지(1000 에폭) 돌려, P = 150, 200, 250에서 모든 라벨을 맞히는 비율을 재라. (나) (가)에서 잰 비율로 외우기의 경계를 말할 수 있는가? (다) 경계가 왜 무작위 데이터에 대한 평균으로 정해지는지 가중치 공간의 부피로 설명하라. 부피를 데이터에 대해 먼저 평균하면 무엇이 나오는가? (라) 여유 κ를 요구하면 경계가 어떻게 바뀌는가? P/N = 0.25, 0.75, 1.25에서 입력 400개로 확인하라.
김민준
20번씩 돌렸어요. P = 150은 20번 모두 맞히고 훑는 횟수의 중앙값이 64번이에요. 200은 15%만 맞히고, 250은 한 번도 못 맞혀요. 그러니까 경계는 150과 200 사이, 대략 입력 수의 1.5배쯤이네요.
이서연
잠깐, 퍼셉트론 알고리즘은 해가 있으면 언젠가 멈춘다는 정리만 있지, 1000번 안에 멈춘다는 보장은 없잖아. 1000번 안에 못 끝낸 것과 해가 아예 없는 건 달라.
김민준
아… 해가 있는지는 선형계획법으로 따로 확인해야겠네요. 200번씩 확인하니 P = 200에서 49%, 240에서 0%예요. 200에서 절반이나 풀리는데요? 1.5배라고 한 건 제 알고리즘이 느렸던 거였네요.
이서연
커버의 셈으로 따져 볼게. 아까 평면에서 센 2P를 N차원으로 넓히면, 가를 수 있는 라벨 조합이 C(P, N) = 2 Σ_(k<N) C(P − 1, k)가지야.
선생님
P = 2N을 넣으면 그 합은 전체의 얼마일까요?
이서연
이항계수 C(2N − 1, k)가… k와 2N − 1 − k에서 같으니까 k < N인 쪽의 합이 꼭 절반이에요. P = 2N에서 정확히 1/2이네요.
김민준
경계가 2인 건 이항계수가 좌우 대칭이라서구나.
이서연
입력이 많을수록 경계가 2에 날카롭게 서고.
김민준
책상 위 구슬도 4개, 평면의 차원 2의 두 배에서 절반이었잖아. 자를 10°씩 돌리다 포기한 게 퍼셉트론을 1000번에서 멈춘 거랑 같네.
선생님
이제 (다). 가드너처럼 라벨을 모두 맞히는 가중치들의 부피 V를 생각해 봐요. 데이터를 뽑을 때마다 V가 달라지는데, 경계에서는 무엇이 일어나죠?
이서연
부피가 가중치의 경우의 수네요. 처음에 동전 앞면 수별로 경우의 수를 셌던 것처럼요. 데이터가 늘 때마다 조건이 늘어 부피가 줄고 경계에서 0이 돼요.
선생님
그 V를 데이터에 대해 평균하려면 무엇을 평균해야 할까요?
이서연
V는 데이터에 따라 지수적으로 흔들리니까… Z 때처럼 ln V를 평균해야겠네요.
김민준
그냥 V를 먼저 평균하면 안 돼요? 라벨이 무작위면 가중치가 어떤 거든 조건 하나를 만족할 확률이 1/2이니까, 평균 V는 전체 구면의 넓이 × 2^(−P)예요. 간단한데요.
이서연
그럼 P가 아무리 커도 평균 V는 0보다 크잖아. 경계가 아예 없다는 답이야.
김민준
어, 그러네. 풀린 평균으로는 외우기가 영원히 가능하다고 나오네.
선생님
라벨이 우연히 한쪽으로 쏠린 드문 데이터에서는 부피가 크게 남고, 평균 V는 그 드문 경우가 끌고 가요. 평균 Z가 드문 결합에 끌려간 것과 같죠. 가드너는 ln V의 굳힌 평균을 레플리카 방법으로 계산했어요. 조건을 만족하는 가중치 두 개를 무작위로 뽑으면 그 겹침 q가 데이터가 늘수록 커지고, q가 1이 되는 곳, 곧 해가 한 점으로 줄어드는 곳이 경계예요.
이서연
(라)는 가드너의 식으로 계산하면 P/N = 0.25, 0.75, 1.25에서 가장 큰 여유 κ가 1.736, 0.691, 0.311이에요. κ = 0이면 적분이 1/2이라 경계가 정확히 2고요.
김민준
여유가 가장 큰 분리 초평면은 서포트 벡터 머신이니까, 입력 400개로 쌍대 문제를 풀어서 10번씩 쟀어요. 1.708, 0.694, 0.305이고 표준편차가 0.044, 0.040, 0.028이에요. 표준편차 안에서 다 맞아요. 복제본을 0개로 보내는 이상한 계산이었는데 이게 맞는다고요?
이서연
입력 100개에서는 표준편차가 더 컸을 거야. 입력이 많아질수록 데이터 하나로 잰 여유가 평균으로 모이니까, 이것도 자기 평균이네.
선생님
정리하면, 데이터는 굳은 무질서이고 가중치는 그 위에서 요동하는 변수예요. 알고리즘이 느린 것과 해가 없는 것을 구별하고 로그를 먼저 씌운 뒤 평균을 내면, 외우기 경계 2와 여유에 따른 경계가 모두 복제본 두 개의 겹침 하나로 나와요.
