Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity

기술 요약: 표현력 포화: 과업 복잡도 증가에 따른 아핀 영역 사용량 감소

문제 정의
ReLU 또는 LeakyReLU 활성화 함수를 사용하는 PANNs와 같은 조각별 아핀 신경망(piecewise-affine neural networks)은 입력 공간이 아핀 영역으로 분할되는 연속 조각별 아핀(CPWA) 사상(map)을 정의한다. 이때 아핀 영역의 개수는 네트워크의 표현 능력을 나타내는 자연스러운 대리 지표가 되지만, 이론적인 최악의 경우 용량(종종 조합론적 상한으로부터 유도됨)과 훈련 후 실제로 실현된 아핀 영역의 수 사이에는 상당한 격차가 존재한다. 이러한 불일치는 입력-레이블 관계가 매우 복잡할 때 특히 중요하다. 본 논문은 고정된 아키텍처와 훈련 프로토콜 하에서, 과업의 복잡도(구체적으로는 무작위 레이블 및 샘플 크기 증가를 통해)를 높이는 것이 실현된 아핀 영역의 수를 감소시키는지, 즉 저자들이 **표현력 포화(expressivity saturation)**라고 명명한 현상을 초래하는지 조사한다.

방법론
저자들은 1차원(1D) 프로브에 대한 엄밀한 이론적 분석과 고차원(2D 및 3D) 유계 영역에서의 정밀한 경험적 열거를 결합한 이중 접근 방식을 채택한다.

1. 이론적 분석 (1D 프로브):

   • 저자들은 아핀 선분 프로브 $\gamma: [0, 1] \to \mathbb{R}^d$를 정의한다.
   • 저자들은 CPWA MLP가 이러한 프로브를 따라 실현할 수 있는 아핀 조각의 수($\alpha(f; \gamma)$)에 대한 결정론적이고 아키텍처 의존적인 상한을 도출한다. 이 상한은 레이어별 너비 항과 활성화 브레이크포인트 인자의 곱이다.
   • 이를 바탕으로 저자들은 **뉴런 임계값 하한(neuron-threshold lower bound)**을 도출하여, 주어진 1D 조각 복잡도를 가진 타겟 함수를 표현하는 데 필요한 최소 아키텍처 용량을 설정한다.
   • 저자들은 실제 영역 효율성($\eta_{norm}$)과 뉴런당 영역 통계량을 도입하여 이론적 용량과 실제 사용량 사이의 격차를 정량화한다.

2. 경험적 열거 (2D 및 3D):

   • 1D 프로브를 넘어 확장하기 위해, 저자들은 **정밀 유계 영역 열거(exact bounded-domain enumeration)**를 위한 알고리즘을 개발한다.
   • 알고리즘 1은 구간 분할(interval partitions)을 신경망 레이어를 통해 전파함으로써 1D 선형 프로브를 따른 아핀 조각의 수를 정확하게 계산한다.
   • 알고리즘 2는 규정된 컴팩트 도메인 $\Omega$(예: $[-1, 1]^d$)와 교차하는 모든 아핀 셀을 철저히 탐색한다. 이는 실행 가능한 시드(seed) 식별, 로컬 아핀 기술자(descriptor) 복구, 그리고 실현된 영역 집합 $R_\Omega(f)$를 열거하기 위한 경계 교차 연산의 순회를 포함한다.
   • 실험에서는 제어된 변수인 샘플 크기 변화를 통한 무작위 레이블 데이터셋을 사용하여 증가하는 과업 복잡도를 모사하며, 이를 통해 고정된 아키텍처를 활용한다.

주요 기여

1. 엄밀한 1D 용량 상한: 본 논문은 CPWA MLP가 임의의 아핀 선분 프로브를 따라 실현할 수 있는 아핀 조각의 결정론적 상한을 증명한다. 이는 특정 1D 조각 복잡도를 가진 타겟을 표현하기 위한 필수적인 뉴런 임계값 하한을 제공하는 결론을 도출한다.
2. 표현력 포화의 증거: 2D 및 3D에서의 정밀 열거를 통해, 저자들은 고정된 아키텍처와 훈련 프로토콜 하에서 과업 복잡도(무작위 레이블 및 샘플 크기를 통해)를 높이는 것이 실제 실현된 아핀 영역의 수를 급격히 감소시킬 수 있음을 보여준다. 이는 아키텍처의 최악의 경우 이론적 용량이 변하지 않음에도 불구하고 발생한다.
3. 기하학적 및 동역학적 연결: 본 연구는 실현된 아핀 영역의 붕괴와 효과적인 결정 경계(decision boundary) 형성 실패 사이의 관계를 시각적 및 정량적 증거를 통해 연결한다. 가장 도전적인 환경(예: 높은 샘플 크기와 무작위 레이블)에서, 영역 사용량의 감소는 결정 경계의 기하학적 구조 악화와 일치한다.

결과

• 1D 일관성: 프로브를 따른 정밀한 계산은 실현된 아핀 조각의 수가 초기화 상태에서도 이론적인 최악의 경우 상한보다 일관되게 훨씬 낮음을 확인시켜 준다. "뉴런당 영역" 통계량은 완만한 범위를 유지하지만, 과업 복잡도가 고정된 아키텍처의 유효 용량을 초과하면 붕괴된다.
• 2D/3D 포화: 무작위 레이블을 사용한 고정된 ReLU MLP(예: $[32, 32, 32]$) 실험에서:
  • 샘플 크기가 작을 때는 훈련 과정 동안 실현된 영역의 수가 증가하는 경향을 보인다.
  • 큰 샘플 크기(예: 5,000 ~ 10,000)의 경우, 훈련 중에 실현된 영역의 수가 급격히 감소하며, 종종 초기화 수준 미만으로 떨어진다.
  • 이 "붕괴" 현상은 다양한 옵티마이저(Adam vs. SGD)와 초기화 방식(Xavier)에 걸쳐 견고하게 나타난다.
• 결정 경계: 시각화를 통해 영역 사용량이 붕괴되는 환경(높은 복잡도)에서는 네트워크가 효과적인 결정 경계를 형성하지 못하는 반면, 학습 가능한 데이터셋(make_moons)에서는 영역의 정교화가 경계 정렬과 상관관계가 있음을 보여준다.

의의 및 범위
본 논문은 명목상의 최악의 경우 표현 용량이 훈련 후 실제로 실현되는 비선형 구조를 나타내는 불완전한 대리 지표라고 주장한다. 표현력 포화라는 개념은 제어된 저차원 설정에서 과업 복잡도를 높이는 것이 반드시 더 풍부한 분할로 이어지는 것이 아니라, 오히려 사용되는 영역의 감소와 낮은 분류 기하학적 성능을 초래할 수 있음을 시사한다.

저자들은 다음과 같은 한계점을 명시한다:

• 이론적 결과는 1D 프로브에 국한되며, 전체 차원의 영역 기하학을 직접적으로 특징짓지는 않는다.
• 정밀 열거는 일반적인 상황에서의 아핀 영역 계산의 NP- 및 #P-난해성(hardness)으로 인해 저차원(2D/3D) 및 중간 규모의 아키텍처로 계산적 제약을 받는다.
• 본 연구 결과는 완전 연결된 ReLU MLP와 무작위 레이블 환경을 기반으로 하며, 이러한 현상이 구조화된 데이터, 실제 응용 분야 또는 더 복잡한 아키텍처(예: CNN, Transformer)에서 어떻게 나타나는지는 아직 확립되지 않았다.

이 연구는 입력-레이블 복잡도와 실현된 영역 사용량을 연결하는 기초적인 단계로서, 표현 용량과 표현 활용 사이의 격차에 대한 새로운 관점을 제공한다.