Classification and Geometry of General Perceptual Manifolds
https://journals.aps.org/prx/abstract/10.1103/PhysRevX.8.031003
1. Introduction
신경 집단이 동일한 지각 객체의 다양한 물리적 속성(예: 방향, 자세, 크기, 위치, 강도)에 따라 변하는 감각 자극 집합에 반응할 때 지각 다양체(perceptual manifold) 가 형성된다.
지각 다양체는 신경망의 한 층의 모든 $N$개 뉴런들의 활성도 공간 $\mathbb{R}^N$에서 표현된다.
(즉 $\mathbb{R}^N$의 sub-manifold)
(a): 입력 객체의 각도와 크기에 따른 각 뉴런들의 활성도
(b): 뉴런들의 활성도 공간 $\mathbb{R}^N$에서 두 객체의 지각 다양체
이 관점에서 객체 인식이란, 서로 다른 다양체를 구분하는 것을 의미한다.
신경망의 층이 깊어질수록 지각 다양체가 명확히 분리(untangle)될 것이다.
가장 단순한 경우는 입력 패턴의 이분법(dichotomy) 문제이다.
Gardner의 선형 분리가능성(linear separability) 연구에서는 퍼셉트론이 뉴런 $N$개로 분류 가능한 패턴 수 $P$를 통해 퍼셉트론 용량(capacity) $\alpha=P/N$을 구했다.
이 연구에서는 패턴을 단순한 점 집합이 아닌, 다양체로 확장하여 퍼셉트론 용량을 구한다.
2. Model of Manifolds
Manifold in affine subspaces
우리는 $P$개의 지각(perceptual) 매니폴드를 $P$개의 지각 대상을 나타내는 집합으로 모델링한다. 각 매니폴드 $\mathcal{M}_\mu$ ($\mu = 1, \dots, P$)는 $\mathbb{R}^N$의 한 affine 부분공간(affine subspace)에 포함된 콤팩트 집합이며, 이 affine 차원은 $D < N$이다. 매니폴드 위의 한 점 $ \mathbf{x}_\mu \in \mathcal{M}_\mu$는 다음과 같이 매개변수화할 수 있다:
$$\mathbf{x}_\mu(\boldsymbol{S}) = \sum_{i=1}^{D+1} S_i\,\mathbf{u}^\mu_i,\tag{1}$$
여기서 $\{\mathbf{u}^\mu_i\}_{i=1}^{D+1}$는 $\mathcal{M}_\mu$를 포함하는 $(D+1)$-차원 선형 부분공간의 직교 정규 기저(orthonormal basis)다. 벡터 $\boldsymbol{S}=(S_1,\dots,S_{D+1})$는 그 부분공간 내에서의 좌표를 나타내며, $\boldsymbol{S}$는 어떤 집합 $S\subset\mathbb{R}^{D+1}$에 속한다고 가정한다. 굵은 글씨($\mathbf{x}, \mathbf{u}$)는 $\mathbb{R}^N$의 벡터, 화살표($\boldsymbol{S}$)는 $\mathbb{R}^{D+1}$의 벡터를 뜻한다.
이때 $S$는 매니폴드의 형태(shape)를 정의하며, affine 제약을 포함한다. 논문의 나머지에서는 우선 모든 매니폴드가 동일한 형태를 가진다고 가정하여, 모든 $\mu$에 대해 동일한 $S$를 사용한다(이질적 형태의 경우 제 VI.A절 참조).
우리는 이들 $P$개의 매니폴드를, 이분(binary) 레이블 $y_\mu=\pm1$로 구분하고, 원점을 지나는 선형 초평면(hyperplane)으로 분리할 수 있는지 살펴본다. 해당 초평면은 $\|\mathbf{w}\|_2=\sqrt{N}$인 가중치 벡터 $\mathbf{w}$로 표현하며, 모든 $\mu$와 $\mathbf{x}_\mu\in\mathcal{M}_\mu$에 대해 다음을 만족하면 마진(margin) $\kappa$로 올바르게 분리한다고 한다:
$$y_\mu\,\mathbf{w}\cdot \mathbf{x}_\mu \;\ge\;\kappa.\tag{2}$$
선형 분리는 볼록(convex) 문제이므로, 매니폴드를 분리하는 것은 각 매니폴드의 볼록 껍질(convex hull),
$\mathsf{conv}(\mathcal{M}_\mu)=\{\mathbf{x}_\mu(\boldsymbol{S})\mid \boldsymbol{S}\in\mathsf{conv}(S)\}$,
을 분리하는 것과 동치다. 여기서
$$\mathsf{conv}(S) =\Bigl\{\! \sum_{i=1}^{D+1}\alpha_i\,\widetilde{\boldsymbol{S}}_i \;\Big|\; \widetilde{\boldsymbol{S}}_i\in S,\; \alpha_i\ge0,\; \sum_i\alpha_i=1 \Bigr\}. \tag{3}$$
매니폴드가 포함된 affine 부분공간은, 원점에서 가장 가까운 한 점—orthogonal translation 벡터 $\mathbf{c}_\mu$—으로 위치를 정의할 수 있다. 이 $\mathbf{c}_\mu$는 해당 affine 부분공간 내 변위(displacement) 벡터들과 수직이며, 모든 $\mathbf{x}_\mu\in\mathcal{M}_\mu$에 대해
$\mathbf{x}_\mu\cdot \mathbf{c}_\mu = \|\mathbf{c}_\mu\|^2$를 만족한다(그림 2).
편의상, 모든 $\mu$에 대해 $\|\mathbf{c}_\mu\|=1$이라고 정규화한다.
마지막으로 매니폴드의 크기(size)를 조절할 수 있는 매개변수 $r$를 도입한다. 기준점(center) $\boldsymbol{S}_0\in S$을 중심으로,
$$r\,\mathcal{M}_\mu \;=\; \bigl\{\sum_{i=1}^{D+1}\bigl[S^0_i + r\,(S_i - S^0_i)\bigr]\mathbf{u}^\mu_i \;\big|\;\boldsymbol{S}\in S\bigr\}. \tag{4}$$
$r\to0$이면 매니폴드는 하나의 점 $\mathbf{x}_{\mu,0}=\sum_i S^0_i\mathbf{u}^\mu_i$으로,
$r\to\infty$이면 해당 affine 부분공간 전체로 퍼진다.
Bounds on linear separability of manifolds
다이코토미(dichotomy)로 분류된 $P$개의 입력 점들이 $\mathbb{R}^N$에서 여백(margin) $\kappa=0$일 때, 원점을 지나는 선형 초평면으로 분리 가능한 다이코토미의 수는 다음과 같이 주어진다:
$$C_0(P, N) \;=\; 2 \sum_{k=0}^{N-1} \binom{P-1}{k}\;\le\; 2^P.\tag{5}$$
증명:
1. $P-1$개 점에 대해 가능한 분류 수를 $f(P-1,N)$이라 하자.
2. 여기에 마지막 점 $x_P$를 추가할 때,
* 초평면이 $x_P$를 “지나지 않는” 경우:
$\;x_P$의 부호가 $w\cdot x_P\gtrless0$ 에 의해 한 번에 결정되므로,
가능한 분류 수는 $f(P-1,N)$.
* 초평면이 $x_P$를 “지나는”(즉 $w\cdot x_P=0$) 경우:
법선 $w$가 $x_P$에 수직이므로 차원이 $N-1$인 부분구면으로 내려가고,
이 경우 분류 가능한 수는 $f(P-1,N-1)$.
3. 따라서
$$f(P,N)\;=\;f(P-1,N)\;+\;f(P-1,N-1)$$
라는 재귀 관계가 성립하며,
초기조건 $f(1,N)=2$에서 출발해 이 재귀를 풀면
$$f(P,N)\;=\;2\sum_{k=0}^{N-1}\binom{P-1}{k}$$
라는 닫힌 형식을 얻는다.
여기서 $\displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!}$는 $n \ge k$일 때의 이항 계수이며, 그렇지 않으면 0이다. 이 결과는 모든 크기의 부분집합이 선형 독립인 일반 위치(general position)를 만족하는 입력 벡터에 적용된다.
큰 $P$와 $N$의 경우, 한 다이코토미가 선형 분리될 확률 $\displaystyle \frac{1}{2^P}\,C_0(P,N)$ 는 $P/N$ 비율에만 의존하며, 임계값 $\alpha_0=2$에서 급격한 전이(sharp transition)를 보인다. 일반 매니폴드에 대한 Cover의 계수 정리의 포괄적 확장은 알려져 있지 않으나, 다음의 두 극한을 고려함으로써 선형 실현 가능 다이코토미 수에 대한 하한과 상한을 유도할 수 있다.
1. $r \to 0$의 경우:
매니폴드를 크기 $r$로 축소하면 $\boldsymbol{S}_0$를 중심으로 한 점 $\mathbf{x}_{\mu,0}$들만 남게 되어, 매니폴드의 분리 문제는 이 $P$개의 중심점들의 분리 문제와 동치가 된다. 따라서 이 중심점들이 $\mathbb{R}^N$에서 일반 위치에 있어야 한다.
2. $r \to \infty$의 경우:
매니폴드가 완전한 affine 부분공간을 이루면, 가중치 벡터 $\mathbf{w}$는 그 부분공간의 모든 변위 벡터(displacement vectors)에 직교해야 한다. 이때 $\mathbf{w}$는 차원 $N - D_{\rm tot}$의 널(null) 공간에 놓여야 하며, $D_{\rm tot}$은 모든 매니폴드의 affine 변위 벡터의 합집합의 랭크이다. 일반 위치를 가정하면 $D_{\rm tot}=\min(PD,\,N)$가 되고, 선형 분리가 가능하려면 $P\,D < N$이어야 하며, 이 널 공간에서 $P$개의 orthogonal translation 벡터들의 투영 역시 분리 가능해야 한다.
이 조건 하에서 $D$차원 affine 부분공간의 다이코토미 수 $C_D(P,N)$는 다음과 같이 주어진다:
$$C_D(P,N) \;=\; C_0\bigl(P,\,N - P D\bigr).\tag{6}$$
이 관계로부터, $D$차원 affine 부분공간의 선형 분리성은 큰 $P,N$의 한계에서
$\displaystyle P/N = \frac{2}{1 + 2D}$
에서 ‘항상 분리 가능(always separable)’에서 ‘절대 분리 불가능(never separable)’으로 급격히 전이함을 알 수 있다 (Supplementary Materials, Sec. S1 참조).
3. 유한 크기의 일반 $D$차원 매니폴드:
위 극한값으로부터, 유한 크기의 $D$차원 매니폴드에 대해 선형 분리 가능한 다이코토미 수는 하한 $C_D(P,N)$ 및 상한 $C_0(P,N)$을 갖는다. 무작위 레이블링된 매니폴드가 여백 $\kappa$로 선형 분리 가능한 최대 부하(load) $\alpha_M(\kappa)=P/N$를 정의하면, 여백 $\kappa=0$일 때 그 역수는 다음과 같은 경계 안에 놓인다:
$$\frac12 \;\le\; \alpha_M^{-1}(0) \;\le\; \frac12 + D.\tag{7}$$
이들 경계는 $N\to\infty$ 한계에서, 각 매니폴드가 무한한 점을 포함함에도 불구하고 분리 가능한 매니폴드 수가 $N$에 비례함을 보여 준다. 이는 이어지는 통계역학적 해석의 토대를 마련한다.
3. Statistical Mechanical Theory
이론적 진전을 위해 위에서 도출한 경계만으로는 부족하므로, 매니폴드 공간과 레이블에 대해 추가적인 통계적 가정을 도입한다. 구체적으로, 매니폴드 $\mathcal{M}_\mu$를 구성하는 기저 벡터 $\mathbf{u}_i^\mu$의 각 성분은 평균 0, 분산 $1/N$인 동일한 가우스 분포에서 독립적으로 추출되며, 이분 레이블 $y_\mu=\pm1$도 각 매니폴드에 동등한 확률로 무작위 배정된다고 가정한다. 우리는 $N,P\to\infty$이지만 부하(load) $\alpha = P/N$는 유한하게 유지되는 열역학적 극한을 연구한다. 또한, 매니폴드 기하학은 집합 $\mathcal{S}\subset\mathbb{R}^{D+1}$로 정의되며, 특히 affine 차원 $D$는 극한에서 고정된 값으로 취급한다.
이러한 가정 하에서 식 (7)의 경계는 여백(margin) $\kappa$를 갖는 일반 매니폴드의 선형 분리 가능성을 다음과 같이 확장할 수 있다(Gardner 논문 참조):
$$\alpha_0^{-1}(\kappa)\;\le\;\alpha_{\mathrm{M}}^{-1}(\kappa)\;\le\;\alpha_0^{-1}(\kappa)\;+\;D,\tag{8}$$
여기서 $\alpha_0(\kappa)$는 Gardner 이론에 의해 유도된, 마진 $\kappa$를 갖는 무작위 i.i.d. 점들의 선형 분리 최대 부하를 의미한다.
$$\alpha_0^{-1}(\kappa) =\int_{-\infty}^{\kappa}\!Dt\,(t-\kappa)^2,\tag{9}$$
$$Dt=\frac{1}{\sqrt{2\pi}}\,e^{-t^2/2}\,dt$$
는 표준 정규분포 측도다.
많은 흥미로운 경우에서 affine 차원 $D$가 크면 식 (8)에서의 여유(gap)가 지나치게 커지므로, 유한 크기의 매니폴드에 대한 분리 용량을 추정하고 매니폴드의 기하학적 특성이 용량 및 해의 구조에 미치는 영향을 평가하는 것이 중요하다.
A. mean field theory of manifold separation capacity
Gardner의 틀을 따라, 우리는 해 공간(solution space)의 부피 $Z$의 통계적 로그 평균을 계산한다. 이때
$$Z \;=\;\int d^N\mathbf{w}\,\delta\bigl(\|\mathbf{w}\|^2 -N\bigr)\,\prod_{\mu,\,\mathbf{x}^\mu\in\mathcal{M}^\mu}\Theta\bigl(y^\mu\,\mathbf{w}\cdot\mathbf{x}^\mu - \kappa\bigr),\tag{10}$$
여기서 $\Theta(\cdot)$는 방정식 (2)의 마진 제약을, 델타 함수는 $\|\mathbf{w}\|^2=N$ 정규화를 강제한다. 우리는 고정된 마진 $\kappa$에서 달성 가능한 최대 부하(load) $\alpha_{\mathrm{M}}$ 해, 또는 주어진 $\alpha_{\mathrm{M}}$에서 마진 $\kappa$를 최대화하는 해의 성질에 집중한다 .
부피 $Z$의 로그 평균 계산은 부하 $\alpha=P/N$가 임계치에 접근할 때 $Z\to0$이 되는 지점을 찾는 것과 동치이며, 부하의 역수인 분리 용량의 역수는 열역학적 극한에서 다음과 같이 일반 형태로 주어진다 (Appendix A 참고):
$$\alpha_{\mathrm{M}}^{-1}(\kappa) =\bigl\langle F(\boldsymbol{T})\bigr\rangle_{\boldsymbol{T}},\tag{11}$$
$$F(\boldsymbol{T})=\min_{\boldsymbol{V}}\Bigl\{\|\boldsymbol{V}-\boldsymbol{T}\|^2 \;\big|\;\boldsymbol{V}\cdot\boldsymbol{S}-\kappa\ge0,\;\forall\,\boldsymbol{S}\in\mathcal{S}\Bigr\},$$
여기서 $\langle\cdot\rangle_{\boldsymbol{T}}$는 각 성분이 i.i.d. $\mathcal{N}(0,1)$인 $(D+1)$-차원 가우스 벡터 $\boldsymbol{T}$에 대한 평균이다. 벡터 $\boldsymbol{V}$의 성분은 분리 해 벡터 $\mathbf{w}$가 매니폴드의 직교 기저벡터들에 유도하는 부호화된 접선장(signed field)을, $\boldsymbol{T}$는 매니폴드 기저벡터 및 레이블의 quenched 변동성으로 인한 $\boldsymbol{V}$의 가우스적 변동분을 나타낸다 .
제약조건을 매니폴드 상의 투영이 최소인 점 하나로 환원하기 위해, 우리는 $\mathcal{S}$의 오목 지지 함수(concave support function)
$$g_{\mathcal{S}}(\boldsymbol{V}) =\min_{\boldsymbol{S}\in\mathcal{S}}\{\boldsymbol{V}\cdot\boldsymbol{S}\}$$
를 도입하고, 이를 통해
$$F(\boldsymbol{T}) =\min_{\boldsymbol{V}}\Bigl\{\|\boldsymbol{V}-\boldsymbol{T}\|^2 \;\big|\;g_{\mathcal{S}}(\boldsymbol{V})-\kappa\ge0\Bigr\}\tag{12}$$
로 다시 쓸 수 있다.
Karush–Kuhn–Tucker (KKT) 조건
최대 마진 해의 성질을 이해하기 위해, 위의 볼록 최적화 문제(Eq. 12)의 KKT 조건을 살펴본다. 각 $\boldsymbol{T}$에 대해 $\boldsymbol{V}$의 유일한 최적해는
$$\boldsymbol{V} = \boldsymbol{T} + \lambda\,\tilde{\boldsymbol{S}}(\boldsymbol{T}),\tag{13}$$
$$\lambda \ge 0,\quad g_{\mathcal{S}}(\boldsymbol{V})-\kappa\ge0,\quad \lambda\bigl[g_{\mathcal{S}}(\boldsymbol{V})-\kappa\bigr]=0,\tag{14}$$
로 특징지어진다. 여기서 $\tilde{\boldsymbol{S}}(\boldsymbol{T})\in\partial g_{\mathcal{S}}(\boldsymbol{V})$는 지지 함수의 subgradient로, 매니폴드의 볼록 껍질(convex hull) 위에서 $\boldsymbol{V}$와의 내적이 최소인 점이다.
지지 함수가 미분 가능하면 이 subgradient는 단일해이며,
$$\tilde{\boldsymbol{S}}(\boldsymbol{T}) =\nabla g_{\mathcal{S}}(\boldsymbol{V}) =\arg\min_{\boldsymbol{S}\in\mathcal{S}}\boldsymbol{V}\cdot\boldsymbol{S}.\tag{15}$$
로 표현된다 . (지지 함수는 양(陽)의 동차성: $g_{\mathcal{S}}(\gamma\boldsymbol{V})=\gamma\,g_{\mathcal{S}}(\boldsymbol{V})$를 갖기 때문에, 그 아기울기는 $\boldsymbol{V}$의 방향만으로 결정된다.)
용량 표현
식 (13)으로부터,
$$F(\boldsymbol{T}) =\bigl\|\lambda\,\tilde{\boldsymbol{S}}(\boldsymbol{T})\bigr\|^2\tag{16}$$
로 쓰이며 , 계수 $\lambda$는
* $g_{\mathcal{S}}(\boldsymbol{V})-\kappa>0$이면 $\lambda=0$ (이 때 $\boldsymbol{V}=\boldsymbol{T}$, $\boldsymbol{T}\cdot\tilde{\boldsymbol{S}}-\kappa>0$),
* $g_{\mathcal{S}}(\boldsymbol{V})-\kappa<0$이면 $\lambda>0$ (이 때 $\boldsymbol{V}\neq\boldsymbol{T}$)
이 두 경우를 통합하여 $\lambda$는 다음의 자체 일관 방정식을 만족한다:
$$\lambda =\frac{\bigl[-\,\boldsymbol{T}\cdot\tilde{\boldsymbol{S}}(\boldsymbol{T})+\kappa\bigr]_{+}} {\bigl\|\tilde{\boldsymbol{S}}(\boldsymbol{T})\bigr\|^2}, \quad[x]_{+}=\max(x,0).\tag{17}$$
이로써 $\alpha_{\mathrm{M}}^{-1}(\kappa)$는 식 (11)에 의해 $\langle F(\boldsymbol{T})\rangle_{\boldsymbol{T}}$로 계산할 수 있게 된다 .
B. Mean field interpretation of the KKT relations
KKT 조건은 평균장 이론 틀 안에서 직관적인 해석을 갖는다. 최대 마진 해 벡터 $\mathbf{w}$는 항상 일련의 **서포트 벡터**들의 선형 결합으로 쓸 수 있다. 각 매니폴드에는 무수히 많은 점이 있지만, 해 벡터는 결국 매니폴드마다 하나씩, 총 $P$개의 벡터로 분해된다:
$$\mathbf{w}\;=\;\sum_{\mu=1}^{P}\lambda_\mu\,y^\mu\,\tilde{\mathbf{x}}^{\,\mu}, \qquad\lambda_\mu\ge0\tag{18}$$
여기서 $\tilde{\mathbf{x}}^{\,\mu}\in\mathrm{conv}\bigl(M^\mu\bigr)$는 $\mu$번째 매니폴드의 볼록 껍질(convex hull) 안에 있는 벡터다. 차원 $N$이 매우 클 때 이들 벡터는 서로 상관이 사라지므로, 상호 항을 무시하고 양변의 노름을 제곱하면
$$\|\mathbf{w}\|^{2}=N=\sum_{\mu=1}^{P}\lambda_\mu^{2}\,\bigl\|\tilde{\mathbf{S}}^{\,\mu}\bigr\|^{2},$$
여기서 $\tilde{\mathbf{S}}^{\,\mu}$는 $\tilde{\mathbf{x}}^{\,\mu}$를 해당 매니폴드의 affine 부분공간 기저(식 1)로 전개한 좌표다. ‘cavity method’ 분석에 따르면, 평균장 KKT식에서의 $\lambda_\mu$와 (18)식의 $\lambda_\mu$는 개별 항들 간 상관을 보정하는 전체 스케일 인자 하나만 차이 난다\[17, 18].
따라서 분리 용량 역수는
$$\alpha^{-1} \;=\;\frac{N}{P}=\bigl\langle \lambda^{2}\,\|\tilde{\mathbf{S}}\|^{2}\bigr\rangle,$$
즉 식 (11)·(16)의 KKT 표현을 회복한다. 위 KKT 식은 $\lambda_\mu$와 $\tilde{\mathbf{S}}^{\,\mu}$의 통계량에 대한 자기일관(self-consistent) 방정식이다. 평균장 이론은 이를 **단일 매니폴드** 위에서 정의된 장(field)의 자기일관식으로 환원해 구한다.
구체적으로, 해 벡터 $\mathbf{w}$를 한 매니폴드($\mu=1$)의 affine 부분공간에 투영해
$$V^{1}_{i}=y^{1}\,\mathbf{w}\cdot\mathbf{u}^{1}_{i},\quad i=1,\dots,D+1$$
라 정의하면, 식 (18)은
$$\boldsymbol{V}^{1}= \lambda_{1}\,\tilde{\mathbf{S}}^{\,1} + \boldsymbol{T},$$
으로 줄어든다. 여기서 $\boldsymbol{T}$는 나머지 $P-1$개 매니폴드가 유도하는 기여로, 부분공간이 서로 무작위로 배향되어 있기 때문에 가우스 랜덤 벡터로 기술된다. 자기일관성은 (i) 주어진 $\boldsymbol{T}$에 대해 $\tilde{\mathbf{S}}^{\,1}$이 $\boldsymbol{V}^{1}$과의 내적을 최소화하는 점이어야 하며, (ii) 그 점이 마진 초평면 위에 있어야 한다고 요구한다. 이 조건이 충족되지 않으면 해당 매니폴드는 최대 마진 해에 기여하지 않는다.
결국 식 (13)은 “특정 매니폴드가 유도한 장”과 “나머지 매니폴드가 유도한 장”을 분해한 관계일 뿐이며, 식 (14)와 (17)에 나타난 $\lambda$의 자기일관 방정식은 $\tilde{\mathbf{S}}^{\,1}$이 서포트 벡터 역할을 해야 한다는 요구에서 자연스럽게 따라 나온다.
C. Anchor points and manifold supports
해(解)를 구성하는 벡터 $\mathbf{\tilde{x}}^{\mu}$―또는 그들의 affine 부분공간 좌표 $\tilde{S}^{\mu}$―를 매니폴드 앵커 포인트(manifold anchor points) 라고 부른다. 주어진 매니폴드 배치에 대해, 각 매니폴드를 그 하나의 앵커 포인트로 치환해도 최대-마진 해는 변하지 않는다. 하지만 개별 앵커 포인트는 자신이 속한 매니폴드의 기하뿐 아니라 다른 모든 매니폴드의 무작위 배향에도 의존한다. 따라서 서로 다른 매니폴드 배치가 주어지면, 같은 매니폴드라도 앵커 위치가 달라지며, 평균장 이론에서는 그 불확실성을 가우스 랜덤 벡터 $\vec{T}$에 대한 의존성으로 기술한다.
특히, 앵커 포인트가 매니폴드의 볼록 껍질(conv $\mathcal{S}$) 안에서 **어디에 놓이느냐**는 그 매니폴드가 마진 초평면들과 어떻게 만나느냐를 반영한다. 일반적으로 일부 매니폴드는 마진 초평면과 실제로 교차하여 라그랑주 승수 $\lambda\neq0$를 갖는데, 이들을 **서포트 매니폴드(support manifolds)** 라고 한다. 서포트의 형태는 다양하며, 교차 집합이 생성하는 부분공간의 차원 $k$로 특징지을 수 있다.
* 터칭(touching) 매니폴드 : 초평면과 딱 한 점(앵커) 에서만 접한다. 이때 $k=1$이고 앵커는 $\mathcal{S}$ 경계 위에 있다.
* 완전-서포트(fully supporting) 매니폴드: 매니폴드 전체가 마진 초평면 안에 놓인다. 이 경우 $k=D+1$이며, 해 벡터의 서명장 $\vec{V}$는 번역 벡터 $\vec{c}$와 평행하다. 매니폴드의 모든 점이 동일한 마진 $\kappa$로 서포트 벡터가 되고, 앵커는 볼록 껍질 내부의 유일한 점으로서 자가-일관 방정식을 만족해 $\vec{V}$의 직교 성분을 상쇄한다. 매니폴드가 매끄럽고 강하게 볼록(strongly convex)하면 이러한 두 가지 외에 다른 서포트 구성은 존재하지 않는다.
그 밖의 기하에서는 부분-서포트(partially supporting) 매니폴드가 가능하다. 이 경우 교차 집합이 $1<k<D+1$ 차원의 면(face)을 이루며, 앵커 포인트는 그 면의 내부(예: $k=2$이면 모서리(edge), $k=3$이면 2-차면) 안에 놓인다.
요컨대, 앵커 포인트는 (i) 다른 매니폴드들이 만드는 가우스장 $\vec{T}$와, (ii) 자신의 매니폴드 기하가 결합되어 결정되며, 그 위치와 서포트 차원 $k$가 매니폴드 분류 용량과 최대-마진 해의 구조를 좌우한다.
D. Conic decomposition
E. Numerical solution of the mean field equations
4. Manifold Geometry
In this section, we address how the capacity to separate a set of manifolds can be related to their geometry, in particular to their shape within the D-dimensional affine subspace.
A. Longitudinal and intrinsic coordinates
B. Types of supports
C. Effects of size and margin
D. Manifold anchor geometry
E. Gaussian geometry
F. Geometry and classification of high dimensional manifolds
5. Examples
A. Strictly convex manifolds: $l_2$ ellipsoids
B. Convex polytopes: $l_1$ ellipsoids
C. Smooth nonconvex manifolds: Ring manifolds
6. Manifolds with sparse labels
A. Mixtures of manifold geometries
B. Manifolds with sparse labels
Appendix A: Replica Theory of Manifold Capacity
본 절에서는 식 (11)–(12)에 요약된 평균장 레플리카 이론의 유도 과정을 개괄한다. 우리는 매니폴드의 선형 분류 용량 $\alpha_{\mathrm{M}}(\kappa)$을, 주어진 마진 $\kappa$에서 식
$$ y^{\mu}\,\mathbf{w}\!\cdot\!\mathbf{x}^{\mu}\;\ge\;\kappa $$
를 만족하는 해 $\mathbf{w}$가 높은 확률로 존재하는 최대 부하 $\alpha = P/N$로 정의한다. 여기서 $\mathbf{x}^{\mu}$는 식 (1)에서 정의된 $P$개의 매니폴드 $M^{\mu}$ 위의 점이며, $\{\mathbf{u}_{i}^{\mu}\}$의 총 $NP(D+1)$개 성분은 평균 0, 분산 $1/N$인 가우스 분포에서 독립적으로 추출된다고 가정한다. 또한 이진 레이블 $y^{\mu}=\pm1$은 각 매니폴드에 동일 확률로 무작위 부여된다. 우리는 $N,P\to\infty$이지만 부하 $\alpha=P/N$과 어파인 차원 $D$를 유한하게 유지하는 열역학적 극한을 다룬다.
해 초평면으로부터의 거리로 정의되는 기하학적 마진 $\kappa'$는
$$ y^{\mu}\,\mathbf{w}\!\cdot\!\mathbf{x}^{\mu}\;\ge\;\kappa'\,\lVert\mathbf{w}\rVert \;=\;\kappa'\sqrt{N}$$
로 주어진다. 그러나 이 거리는 입력 벡터 $\mathbf{x}^{\mu}$의 스케일에 의존하므로, 열역학적 극한에서 올바른 스케일링은
$$\kappa' \;=\;\frac{\lVert\mathbf{x}\rVert}{\sqrt{N}}\,\kappa$$
가 된다. 우리는 $\lVert\mathbf{x}^{\mu}\rVert=O(1)$로 정규화했으므로, 마진의 올바른 스케일링은 결국
$$y^{\mu}\,\mathbf{w}\!\cdot\!\mathbf{x}^{\mu}\;\ge\;\kappa$$
가 된다.
Evaluation of solution volume: Following Gardner's replica framework, we first consider the volume $Z$ of the solution space for $\alpha<\alpha_{\text{M}}(\kappa)$ . We define the signed projections of the the $i$th direction vector $\mathbf{u}_{i}^{\mu}$ on the solution weight as $H_{i}^{\mu}=\sqrt{N}y^{\mu}\mathbf{w}\cdot\mathbf{u}_{i}^{\mu}$, where $i=1,...,D+1$ and $\mu=1,...,P$. Then, the separability constraints can be written as $\sum_{i=1}^{D+1}S_{i}H_{i}^{\mu}\geq\kappa$ . Hence the volume can be written as
$$Z=\int d^{N}\mathbf{w}\delta(\mathbf{w}^{2}-N)\,\Pi_{\mu=1}^{P}\Theta_{\mu}\left(g_{\mathcal{S}}(\vec{H}^{\mu})-\kappa\right)\label{eq:V-1-1}$$
where $\Theta(x)$ is a Heaviside step function. $g_{\mathcal{S}}$ is the *support function* of ${\cal \mathcal{S}}$ defined for Eq.12 as
$$g_{\mathcal{S}}(\vec{V})=\min_{\vec{S}}\left\{ \vec{V}\cdot\vec{S}\mid\vec{S}\in{\cal \mathcal{S}}\right\}$$
The volume defined above depends on the the quenched random variables $\mathbf{u}_{i}^{\mu}$ and $y^{\mu}$ through $H_{i}^{\mu}$. It is well known that in order to obtain the typical behavior in the thermodynamic limit, we need to average $\log Z$, which we carry out using the replica trick,
$\langle\log Z\rangle=\lim_{n\rightarrow0}\frac{\langle Z^{n}\rangle-1}{n}$, where $\langle\rangle$ refers to the average over $\mathbf{u}_{i}^{\mu}$ and $y^{\mu}$.(무작위 데이터셋으로 일반화) For natural $n,$ we need to evaluate,
$$\begin{aligned}\langle Z^{n}\rangle & =\int\prod_{\alpha}^{n}d\mathbf{w}_{\alpha}\delta(\mathbf{w}_{\alpha}^{2}-N)\prod_{\mu}^{P}\int\mathbb{D}\vec{H}{}^{\mu\alpha}\label{eq:Vn0-1-1}\\ & \langle\prod_{i}^{D+1}\sqrt{2\pi}\delta(H_{i}^{\mu\alpha}-y^{\mu}w_{\alpha}^{T}\mathbf{u}_{i}^{\mu})\rangle_{\mathbf{u}_{i}^{\mu},y^{\mu}}\nonumber \end{aligned}$$
($u$와 $y$표현을 몰아넣음.)
where we have used the notation,
$$\mathbb{D}\vec{H}=\Pi_{i=1}^{D+1}\frac{dH_{i}}{\sqrt{2\pi}}\Theta\left(g_{\mathcal{S}}(\vec{H})-\kappa\right)$$
Using Fourier representation of the delta functions, we obtain
$$\begin{aligned} \langle Z^{n}\rangle & =\int\prod_{\alpha}^{n}d\mathbf{w}_{\alpha}\delta(\mathbf{w}_{\alpha}^{2}-N)\prod_{\mu}^{P}\int\mathbb{D}\vec{H}{}^{\mu\alpha}\label{eq:Vn0-2-1}\\ & \prod_{i=1}^{D+1}\int\frac{d\hat{H}_{i}^{\mu\alpha}}{\sqrt{2\pi}}\left\langle \text{exp}\left\{ i\hat{H}_{i}^{\mu\alpha}(H_{i}^{\mu\alpha}-y^{\mu}\mathbf{w}_{\alpha}^{T}\mathbf{u}_{i}^{\mu})\right\} \right\rangle _{\mathbf{u}_{i}^{\mu},y^{\mu}}\nonumber \end{aligned}$$
Performing the average over the Gaussian distribution of
$\mathbf{u}_{i}^{\mu}$ (each of the $N$ components has zero mean and
variance $\frac{1}{N}$) yields,
$$\begin{aligned} & \left\langle \text{exp}\sum_{i=1}^{D+1}\sum_{\mu\alpha}\left[i\hat{H}_{i}^{\mu\alpha}(-y^{\mu}\sum_{j=1}^{N}w_{\alpha}^{j}\mathbf{u}_{i,j}^{\mu})\right]\right\rangle _{\mathbf{u}_{i}^{\mu},y^{\mu}}\\ & =\text{exp}\left\{ -\frac{1}{2}\sum_{\alpha\beta}\mathfrak{q}_{\alpha\beta}\sum_{i\mu}\hat{H}_{i}^{\mu\alpha}\hat{H}_{i}^{\mu\beta}\right\} \nonumber \end{aligned}$$
where,
$\mathfrak{q}_{\alpha\beta}=\frac{1}{N}\sum_{j=1}^{N}w_{\alpha}^{j}w_{\beta}^{j}$.
Thus, integrating the variables $\hat{H}_{i}^{\mu\alpha}$ yields
$$\begin{aligned}\langle Z^{n}\rangle & =\int\prod_{\alpha=1}^{n}d\mathbf{w}_{\alpha}\delta(\mathbf{w}_{\alpha}^{2}-N)\int d\mathfrak{q}_{\alpha\beta}\Pi_{\alpha\beta}\label{eq:Vn-1}\\ & \cdot\delta\left(N\mathfrak{q}_{\alpha\beta}-\mathbf{w}_{\alpha}^{T}\mathbf{w}_{\beta}\right)\left[\exp\left(-\frac{(D+1)}{2}\text{log}\text{det}\mathfrak{q}\right)X\right]^{P}\nonumber \end{aligned}$$
where
$$\begin{aligned}X & =\int\prod_{\alpha}\mathbb{D}\vec{H}^{\alpha}\exp\left[-\frac{1}{2}\sum_{i,\alpha,\beta}H_{i}^{\alpha}(\mathfrak{q}^{-1})_{\alpha\beta}H_{i}^{\beta}\right]\label{eq:SquareBracket-1}\end{aligned}$$
and we have used the fact that all manifolds contribute the same factor.
We proceed by making the replica symmetric ansatz on the order parameter $\mathfrak{q}_{\alpha\beta}$ at its saddle point, $\mathfrak{q}_{\alpha\beta}=(1-q)\delta_{\alpha\beta}+q$, from which one obtains in the $n\rightarrow0$ limit:
$$\mathfrak{q}_{\alpha\beta}^{-1}=\frac{1}{1-q}\delta_{\alpha\beta}-\frac{q}{(1-q)^{2}}$$
and
$$\text{log}\text{det}\mathfrak{q}=n\log(1-q)+\frac{nq}{1-q}\label{eq:logdetq-1}$$
Thus the exponential term in $X$ can be written as
$$\exp\left[-\frac{1}{2}\sum_{\alpha i}\frac{\left(H_{i}^{\alpha}\right)^{2}}{1-q}+\frac{1}{2}\sum_{i}\left(\frac{\sqrt{q}}{1-q}\sum_{\alpha}H_{i}^{\alpha}\right)^{2}\right]$$
Using the Hubbard--Stratonovich transformation, we obtain
$$X=\int D\vec{T}\left[\int\mathbb{D}\vec{H}\exp\left\{ -\frac{1}{2}\frac{\vec{H}^{2}}{1-q}+\frac{\sqrt{q}}{1-q}\vec{H}\cdot\vec{T}\right\} \right]^{n}$$
where
$$D\vec{T}=\Pi_{i}\frac{dT_{i}}{\sqrt{2\pi}}\exp\left(-\frac{T_{i}^{2}}{2}\right).$$
Completing the square in the exponential and using $\int D\vec{T}A^{n}=\exp n\int D\vec{T}\log A$ in the $n\rightarrow0$ limit, we obtain,
$$X=\exp\left(\frac{nq(D+1)}{2(1-q)}+n\int D\vec{T}\log z(\vec{T})\right)$$
with
$$z(\vec{T})=\int\mathbb{D}\vec{H}\exp\left\{ -\frac{1}{2(1-q)}||\vec{H}-\sqrt{q}\vec{T}||^{2}\right\} \label{eq:Zt-1}$$
Combining these terms, we write the last factor in Eq.A6 as $\exp nPG_{1}$ where,
$$G_{1}=\int D\vec{T}\log z(\vec{T})-\frac{(D+1)}{2}\log(1-q)\label{eq:G1-1}$$
The first factors in $\langle Z^{n}\rangle$, Eq.A6, can be written as $\exp nNG_{0}$, where as in the Gardner theory, the entropic term in the thermodynamic limit is
$$G_{0}(q)=\frac{1}{2}\ln(1-q)+\frac{q}{2(1-q)}\label{eq:G0-1}$$
and represents the constraints on the volume of $\mathbf{w}_{\alpha}$due to normalization and the order parameter $\mathfrak{q}$. Combining the $G_{0}$ and $G_{1}$contributions, we have
$$\langle Z^{n}\rangle_{t_{0},t}=e^{Nn\left[G_{0}(q)+\alpha G_{1}(q)\right]}$$
The classification constraints contribute $\alpha G_{1}$, with Eq.A13, and
$$\begin{aligned}z(\vec{T}) & =\int\Pi_{i=1}^{D+1}\frac{dY_{i}}{\sqrt{2\pi(1-q)}}\exp\left(-\frac{\vec{Y}^{2}}{2(1-q)}\right)\label{eq:Z_append-1}\\ & \Theta\left(g_{\mathcal{S}}(\sqrt{q}\vec{T}+\vec{Y})-\kappa\right)\nonumber \end{aligned}$$
where, we have written the fields $H_{i}$ as
$$H_{i}=\sqrt{q}T_{i}+Y_{i}\label{eq:h_append-1}$$
Note that $\sqrt{q}T_{i}$ represents the quenched random component due to the randomness in the $\mathbf{u}_{i}^{\mu}$, and $Y_{i}$ is the "thermal" component due to the variability within the solution space. The order parameter $q$ is calculated via
$0=\frac{\partial G_{0}}{\partial q}+\alpha\frac{\partial G_{1}}{\partial q}$.
Capacity: In the limit where $\alpha\rightarrow\alpha_{\text{M}}(\kappa)$ , the overlap between the solutions become unity and the volume shrinks to zero. It is convenient to define $Q=\frac{q}{1-q}$ and study the limit of $Q\rightarrow\infty$. In this limit the leading order is
$$\langle\log Z\rangle=\frac{Q}{2}\left[1-\alpha\langle F(\vec{T})\rangle_{\vec{T}}\right]\label{eq:logVLargeQ-1}$$
where the first term is the contribution from $G_{0}\rightarrow\frac{Q}{2}$. The second term comes from $G_{1}\rightarrow-\frac{Q}{2}\alpha\langle F(\vec{T})\rangle_{\vec{T}}$, where the average is over the Gaussian distribution of the $D+1$ dimensional vector $\vec{T}$, and
$$F(\vec{T})\rightarrow-\frac{2}{Q}\log z(\vec{T})$$
is independent of $Q$ and is given by replacing the integrals in Eq.A16 by their saddle point, which yields
$$F(\vec{T})=\min_{\vec{V}}\left\{ \left\Vert \vec{V}-\vec{T}\right\Vert ^{2}\mid g_{\mathcal{S}}\left(\vec{V}\right)-\kappa\geq0\right\} \label{eq:F(t)-2}$$
At the capacity, $\log Z$ vanishes, the capacity of a general manifold with margin $\kappa$, is given by, $$\begin{aligned}\alpha_{\text{M}}^{-1}(\kappa) & =\langle F(\vec{T})\rangle_{\vec{T}}\label{eq:alphaLines-1}\\ F(\vec{T}) & =\min_{\vec{V}}\left\{ \left\Vert \vec{V}-\vec{T}\right\Vert ^{2}\mid g_{\mathcal{S}}(\vec{V})-\kappa\geq0\right\} \label{eq:F(t)-1-1}\end{aligned}$$
Finally, we note that the mean squared 'annealed' variability in the fields due to the entropy of solutions vanishes at the capacity limit, as $1/Q$ , see Eq.A16. Thus, the quantity $\left\Vert \vec{V}-\vec{T}\right\Vert ^{2}$in the above equation represents the annealed variability times $Q$ which remains finite in the limit of $Q\rightarrow\infty$.
Appendix B: Strictly Convex Manifolds
Appendix C: Limit of Large Manifolds
Furthermore
Linear Classification of Neural Manifolds with Correlated Variability (2023, PRL)
Statistical Mechanics of Support Vector Regression (2024)