Embedding Dimension Lower Bounds for Universality of Deep Sets and Janossy Pooling

기술적 요약: 심층 집합과 자노시 풀링의 보편성을 위한 임베딩 차원 하한

문제 제기
본 논문은 심층 집합 (Deep Sets) 과 그 일반화인 자노시 풀링 (Janossy pooling) 에 대한 치환 불변 신경망 아키텍처의 보편성에 관한 이론적 문제를 다룹니다. 이러한 아키텍처가 모든 연속적인 치환 불변 함수를 근사할 수 있다는 점은 이미 입증되었으나, 이 보편성을 보장하기 위해 필요한 최소 임베딩 차원 $M$(잠재 차원) 을 결정하는 것은 여전히 중요한 미해결 과제로 남아 있습니다.

이전 연구들은 상한 (예: $d>1$인 심층 집합의 경우 $M \le 2nd + 1$) 과 자명한 하한 (예: $d=1$인 경우 $M \ge n$) 을 제시했습니다. 그러나 $d > 1$인 심층 집합과 $k > 1$인 $k$-ary 자노시 풀링의 경우, 주변 차원 $d$에 따라 확장되는 비자명한 하한은 알려져 있지 않았습니다. 본 논문은 $K = [0, 1]^d$ 영역에서 스칼라 출력 경우 ($p=1$) 에 초점을 맞추며, 보편성을 위해 필요한 최소 임베딩 차원을 $M_{univ}(d, n, k)$로 정의합니다.

방법론
저자들은 임베딩 차원에 대한 하한을 확립하기 위해 **보르수크 - 울람 정리 (Borsuk-Ulam theorem)**에 기반한 새로운 기법을 도입합니다. 방법론은 다음과 같은 주요 단계를 거칩니다:

1. 색인화된 자노시 풀링으로의 축소: 저자들은 먼저 표준 $k$-ary 자노시 아키텍처가 보편성을 가진다면, 입력 튜플의 특정 인덱스에 의존하도록 인코더 함수 $\phi_{i_1, \dots, i_k}$가 허용되는 더 크고 불변성이 없는 '색인화된 자노시 풀링 (indexed Janossy pooling)'이라는 클래스의 보편성도 함의함을 보여줍니다. 이 색인화된 변형에서는 모든 치환에 걸쳐 공유되는 대신 인코더 함수가 입력 튜플의 특정 인덱스에 의존할 수 있습니다. 이 축소를 통해 저자들은 원래 대칭 클래스에 자동으로 적용되는 색인화된 클래스에 대한 하한을 증명할 수 있습니다.
2. 유한 차분 강성 (Finite-Difference Rigidity): 색인화된 자노시 잠재 매핑이 특정 '유한 차분 강성'을 만족함을 보여주는 중요한 보조정리가 확립됩니다. 매핑이 그리드의 '축' 부분집합 (적어도 하나의 좌표가 0 인 경우) 에서 일치한다면, 전체 그리드에서도 일치해야 합니다. 이 속성은 희소 입력 집합에서의 인코더 행동을 조밀한 그리드에서의 행동과 연결합니다.
3. 보르수크 - 울람 구성: 하한을 증명하기 위해 저자들은 입력 공간 내에서 두 개의 서로소인 컴팩트 집합 $E_+$와 $E_-$를 구성합니다. 보르수크 - 울람 정리를 활용하여 임베딩 차원 $M$이 너무 작을 경우 (구체적으로 $M$이 유도된 임계값보다 작을 경우), $\mathbb{R}^M$으로 매핑되는 임의의 연속 인코더 $\Phi$가 한 쌍의 반대점 (하나는 $E_+$에서, 하나는 $E_-$에서) 을 동일한 잠재 벡터로 매핑해야 함을 보여줍니다.
4. 충돌 논증: $E_-$와 $E_+$에서 각각 서로 다른 값 (0 과 1) 을 갖는 연속적인 타겟 함수 $g$를 구성함으로써, 인코더가 이러한 집합들의 점들을 동일한 잠재 벡터로 매핑할 경우, 디코더 $\rho$가 $1/2$ 미만의 오차로 $g$를 근사할 수 없음을 저자들은 보여줍니다. 이 모순은 가정된 차원 $M$이 보편성을 위해 불충분함을 증명합니다.

주요 기여 및 결과

• 심층 집합 ($k=1$) 에 대한 새로운 하한: $\mathbb{R}^d$의 $n$개 점으로 구성된 집합에 작용하는 심층 집합의 경우, 최소 임베딩 차원은 다음을 만족함을 본 논문은 증명합니다:
  $$M_{univ}(d, n, 1) \ge d(n - 1)$$
  이는 $d > 1$에 대해 주변 차원 $d$에 따라 증가하는 최초의 하한입니다. 기존 상한인 $2nd + 1$(Dym–Gortler) 과 결합할 때, 필요한 차원이 상수 인자를 제외하고 $\Theta(nd)$로 확장됨을 확립합니다. $d=1$인 경우, 이 하한은 $n-1$을 도출하여 상수 덧셈 항을 제외하고 $n$에 대한 선형 의존성을 회복합니다.

• $k$-ary 자노시 풀링 ($k > 1$) 에 대한 최초의 비자명한 하한: 일반적인 $k$-ary 자노시 풀링의 경우, 저자들은 $d$에 의존하는 최초의 비자명한 하한을 유도합니다. 그 결과는 다음과 같습니다:
  $$M_{univ}(d, n, k) \gtrsim_k (d(n - k))^{1/k}$$
  이 결과는 유한 차수의 상호작용 ($k > 1$) 이 있더라도 필요한 잠재 차원은 주변 차원 $d$와 집합 크기 $n$ 모두에 따라 증가해야 함을 보여줍니다.

• 기술적 프레임워크: 본 논문은 대칭 아키텍처를 색인화된 것으로 축소하고 위상적 장애물 (보르수크 - 울람) 을 잠재 공간 매핑에 적용함으로써 보편성을 분석하는 엄격한 프레임워크를 제공합니다.

의의 및 한계
본 논문은 이러한 결과들이 치환 불변 네트워크의 차원 요구사항에 관한 기존 문헌에서 강조된 중요한 미해결 문제를 해결한다고 주장합니다. 구체적으로, 심층 집합의 경우 임베딩 차원이 $n$과 $d$ 모두에 대해 선형적으로 확장되어야 함을 확인하여, $d>1$인 경우 $n$에만 의존하는 하한만 알려져 있던 이전의 공백을 수정합니다. $k$-ary 풀링의 경우, 상호작용이 $d$에 따른 차원 증가 필요성을 제거하지 못함을 확립합니다.

저자들은 현재 구성의 특정 한계를 지적합니다:

• 심층 집합 ($k=1$) 의 경우, 하한은 $dn$이 아닌$d(n-1)$입니다. 이 '하나의 점 손실'은 보르수크 - 울람 논증에서 사용된 두 개의 서로소 컴팩트 집합을 분리하기 위해 변수의 한 블록이 필요하기 때문에 발생합니다.
• $k > 1$인 경우, 하한의 지수 $1/k$는 구의 영역을 라벨링하기 위해 $k$개의 기본 변수를 사용하는 현재 구성의 한계입니다. 이는 유도된 하한과 심층 집합에서 유래한 $O(nd)$ 상한 사이에 상당한 간격을 남깁니다.

본 논문은 유한 차수 자노시 풀링에 대한 정확한 $d$, $n$, $k$ 의존성을 결정하고 일치하는 상한과 하한을 증명하는 것은 여전히 미해결 문제라고 결론지었습니다.