행렬곱 상태의 표현 정리

기본 정보

• 논문 ID: 2103.08277
• 제목: Representation Theorem for Matrix Product States (행렬곱 상태의 표현 정리)
• 저자: Erdong Guo, David Draper (캘리포니아 대학교 산타크루즈 캠퍼스)
• 분류: stat.ML cs.LG cs.NE quant-ph
• 발표 시간: 2021년 3월 15일 (arXiv 사전인쇄본)
• 논문 링크: https://arxiv.org/abs/2103.08277

초록

본 논문은 부울 함수와 연속 함수의 관점에서 행렬곱 상태(Matrix Product States, MPS)의 범용 표현 능력을 연구한다. 저자들은 MPS가 임의의 부울 함수를 정확히 구현할 수 있음을 증명하였으며, 주어진 부울 게이트에 대응하는 MPS 구조의 구성 방법을 제시하였다. 또한 스케일 불변 시그모이드 활성화 함수를 갖는 MPS 함수 공간이 n차원 실수 좌표 공간의 컴팩트 부분집합에서 정의된 연속 함수 공간에서 조밀함을 증명하였다. MPS와 신경망의 관계를 연구하여, 스케일 불변 시그모이드 함수를 갖는 MPS가 커널 함수를 갖춘 단일 은닉층 신경망과 동치임을 보였다. 마지막으로 동치 신경망을 연구함으로써 무한 폭 MPS가 가우스 과정(GP)을 구현하는 문제를 논의하였다.

연구 배경 및 동기

문제 배경

1. 텐서 네트워크의 부상: 텐서 네트워크는 다체 양자 시스템을 표현하는 강력한 그래픽 언어로서 양자 정보, 응축 물질 물리학, 응용 수학 및 컴퓨터 과학 등 여러 분야에서 광범위하게 응용되고 있다.
2. MPS의 표현 능력 문제: MPS는 양자 물리학에서 중요한 물리적 의미를 가지지만, 기계학습의 대수 도구로 사용할 때 자연스러운 질문이 제기된다: 대수 기계로서 MPS의 표현 능력은 얼마나 강한가?
3. 범용 근사 이론의 필요성: 신경망의 범용 근사 정리와 유사하게, MPS의 표현 능력 경계를 이론적으로 증명할 필요가 있다.

연구 동기

1. 이론적 공백 채우기: 기존 연구는 주로 MPS의 물리적 성질에 초점을 맞추고 있으며, 함수 근사기로서의 이론적 분석이 부족하다.
2. MPS와 신경망의 연결 구축: MPS와 고전 기계학습 모델(특히 신경망) 간의 동치 관계 탐색.
3. 실용성 고려: 실제 응용에서 완전 기저는 보통 무한 차원이므로, 온건한 가정 하에서 MPS가 "생성할 수 있는" 함수 공간의 크기를 연구할 필요가 있다.

핵심 기여

1. 부울 함수의 정확한 표현: MPS가 임의의 부울 함수를 정확히 구현할 수 있음을 증명하고 구성적 증명 방법을 제시하였다.
2. 연속 함수의 범용 근사: 스케일 불변 시그모이드 활성화를 갖는 MPS 함수 공간이 연속 함수 공간에서 조밀함을 증명하였다(상한 노름에 대해).
3. MPS와 신경망의 동치성: MPS와 단일 은닉층 신경망 간의 동치 관계를 확립하여 커널 함수가 MPS에서 자연스럽게 나타남을 밝혔다.
4. 가우스 과정의 구현: 무한 폭 MPS를 통해 가우스 과정의 구현 문제를 논의하였다.

방법 상세 설명

MPS 모델 정의

표준 MPS 구조

원래 MPS 모델은 다음과 같이 정의된다: $\Psi_l(x|w,B) = \sum_{\{\alpha,s\}} A^{s_1}_{\alpha_1\alpha_2} \cdots A^{s_i}_{l\alpha_i\alpha_{i+1}} \cdots A^{s_n}_{\alpha_n\alpha_1} \Phi^{s_1\cdots s_n}(x)$

여기서 커널 함수는 다음과 같이 정의된다: $\Phi^{s_1\cdots s_n}(x) = \phi^{s_1}(x_1) \otimes \cdots \otimes \phi^{s_i}(x_i) \cdots \otimes \phi^{s_n}(x_n)$

수정된 MPS 구조

범용 근사를 구현하기 위해 저자들은 수정된 MPS 구조를 제시하였다: $\Psi(x|w,B) = \sum_l \sigma\left(\sum_{\{\alpha,s\}} A^{s_1}_{\alpha_1\alpha_2} \cdots A^{s_i}_{l\alpha_i\alpha_{i+1}} \cdots A^{s_n}_{\alpha_n\alpha_1} \Phi^{s_1\cdots s_n}(x)\right)$

여기서 $\sigma(\cdot)$는 스케일 불변 시그모이드 함수이다: $\sigma(x) \to \begin{cases} 0 & x \to -\infty \\ C & x \to +\infty \end{cases}$

부울 함수 표현 방법

기본 부울 게이트의 구현

AND 게이트 구현 (정리 2.1):

• 커널 함수: $\phi_i(X_i) = [X_i, 1-X_i]$
• 텐서 노드: $A^{s_i} = [1, 0]$, 결합 차원 $|\alpha| = 1$

OR 게이트 구현 (정리 2.2):

• 커널 함수: $\phi_i(X_i) = [X_i, 1-X_i]$
• 텐서 노드 결합 차원: $|\alpha| = 3$
• 구체적 텐서 구조: $A^{s_1}_{\alpha_1\alpha_2} = [[1, 0, 1], [0, 1, 0]]$$A^{s_2}_{\alpha_2\alpha_1} = [[0, 1, 1], [1, 0, 0]]$

NOT 게이트 구현 (정리 2.3):

• 커널 함수: $\phi_1(X_1) = 1-X_1$
• 텐서 노드: $A^{s_1} = 1$

범용 AND 게이트 및 임의의 부울 함수

범용 AND 게이트 (정리 2.4): n개의 입력 변수에 대해 다음을 구현할 수 있다: $\Psi(X_1, \cdots, X_n) = (\bigwedge_{i=1}^l X_i) \bigwedge (\bigwedge_{j=l+1}^n \overline{X_j})$

임의의 부울 함수 (정리 2.5): 임의의 부울 함수를 범용 AND 게이트의 분리 정규형으로 표현함으로써 대응하는 MPS를 구성할 수 있다. 구성 규칙:

1. 부울 함수를 진리표에 대응하는 분리 정규형으로 작성
2. 결합 차원을 분리 항의 개수 m으로 설정
3. 특정 규칙에 따라 텐서 원소 채우기

연속 함수 근사 이론

주요 정리 (정리 3.1)

MPS 함수 공간은 $C_0(I^n)$(단위 입방체 위의 연속 함수 공간)에서 조밀하다. 즉, 임의의 $f(x) \in C_0(I^n)$과 임의의 $\varepsilon > 0$에 대해, 다음을 만족하는 MPS 함수 $\Psi(x)$가 존재한다: $\sup_x |\Psi(x) - f(x)| < \varepsilon$

증명 기법

선형성 증명 (보조정리 3.2): MPS 함수족 $\mathcal{M}$이 $C_0(I^n)$의 선형 부분공간임을 증명:

1. 스칼라 곱셈에 대해 닫혀있음: 스케일 불변성 이용
2. 덧셈에 대해 닫혀있음: 두 MPS의 합을 나타내는 새로운 MPS 구성

판별 성질 (보조정리 3.4): 스케일 불변 시그모이드 함수가 판별 성질을 가짐을 증명: 유한 부호 측도 $\mu$가 모든 MPS 함수의 적분을 0으로 만들면, $\mu = 0$이다.

주요 정리 증명: Hahn-Banach 정리와 Riesz 표현 정리의 귀류법을 사용:

1. $\overline{\mathcal{M}}$이 $C_0(I^n)$의 진부분집합이라고 가정
2. Hahn-Banach 정리에 의해, $\overline{\mathcal{M}}$을 소멸시키는 비자명 범함수가 존재
3. Riesz 표현 정리에 의해, 대응하는 비자명 측도가 존재
4. 판별 성질에 의해, 해당 측도는 0이어야 하므로 모순 발생

MPS와 신경망의 동치성

동치성 정리 (정리 3.5)

스케일 불변 시그모이드 활성화를 갖는 MPS는 커널 함수를 갖춘 단일 은닉층 신경망과 동치이다.

변환 방법

내부 지표 $\{\alpha_i\}$를 축약함으로써, MPS는 다음과 같이 쓸 수 있다: $\Psi(x) = \sum_l \sigma\left(\sum_s W^l_s \Phi^s(x)\right)$

이는 정확히 단일 은닉층 신경망의 형태이며, 여기서:

• $W^l_s$는 가중치 매개변수
• $\Phi^s(x)$는 커널 함수로, 입력 성분 간의 결합을 자연스럽게 도입

커널 함수의 자연스러운 출현

구체적인 예시를 통해 다항식 커널 등의 비선형 커널이 동치 신경망에서 어떻게 자연스럽게 나타나는지 보여준다. 예를 들어: $(\Phi^s)^T = [x_1x_2x_3, x_2x_3, x_1x_3, x_1x_2, x_1, x_2, x_3, 1]$

실험 결과 및 사례 분석

부울 함수 구현 사례

3입력 OR 게이트: 부울 표현식: $f(X_1,X_2,X_3) = X_1 \vee X_2 \vee X_3$ 대응하는 MPS 텐서 구조는 방법 부분에서 상세히 제시되었다.

3입력 패리티 게이트: 부울 표현식: $f(X_1,X_2,X_3) = X_1 \oplus X_2 \oplus X_3$ 동치 신경망 가중치: $W^s = [1, 0, 0, 1, 0, 1, 1, 0]$

임계값 게이트 Th₃²: 최소 2개의 입력이 1일 때 1을 출력하는 임계값 함수.

복잡도 분석

n입력 부울 게이트의 경우, 극단적인 경우 결합 차원이 $O(2^n)$이 필요하지만, 카르노 맵 단순화를 통해 $O(2^{n-1})$로 감소시킬 수 있으며, 총 매개변수 개수는 $O(n2^{n-1})$로 단일 은닉층 신경망의 효율과 동등하다.

관련 연구

텐서 네트워크 이론 기초

• Penrose (1971)의 텐서 계산 그래픽 기호 체계
• Vidal (2003, 2007)의 Schmidt 분해 및 DMRG 방법
• Perez-Garcia 등 (2006)의 MPS 성질에 대한 체계적 연구

기계학습에서의 텐서 네트워크

• Stoudenmire & Schwab (2016)의 지도학습 응용
• 회귀, 분류 및 밀도 추정에서의 다양한 텐서 네트워크 응용

범용 근사 이론

• Cybenko (1989), Hornik (1991)의 신경망 범용 근사성에 관한 고전 연구
• 본 논문은 유사한 함수해석학 기법을 채택

결론 및 논의

주요 결론

1. 이론적 완전성: MPS는 임의의 부울 함수를 표현하고 임의의 연속 함수를 근사할 수 있는 능력을 가진다.
2. 동치성 규명: MPS는 본질적으로 커널 함수를 갖춘 단일 은닉층 신경망과 동치이다.
3. 커널 함수의 중요성: 커널 함수 $\Phi^{s_1\cdots s_n}$이 MPS의 표현 능력의 핵심이며, 결합 지표 $\{\alpha_i\}$가 아니다.

한계점

1. 실용성 문제: 부울 함수의 MPS 구현은 지수 수준의 결합 차원이 필요하다.
2. 물리적 의미 상실: 순수 대수 도구로 사용할 때, MPS는 양자 물리학에서의 얽힘 등 중요한 성질을 잃는다.
3. 커널 함수 설계: 충분한 표현 능력을 얻기 위해 커널 함수를 신중하게 설계해야 한다.

향후 방향

1. 효율적 구성 방법: MPS의 더 효율적인 구성 방법을 찾아 복잡도 감소.
2. 심층 구조: 심층 신경망에 유추하여 다층 MPS 구조 탐색.
3. 양자 우위: 양자 컴퓨팅 환경에서 MPS의 독특한 우위 탐색.

심층 평가

장점

1. 이론적 기여 중대: 함수 근사 관점에서 MPS의 표현 능력을 처음으로 체계적으로 분석.
2. 증명의 엄밀성: 함수해석학의 고전 도구를 사용하여 증명 과정이 엄밀함.
3. 연결성 통찰: MPS와 신경망 간의 심층적 연결을 규명하여 학제 간 이해를 위한 다리 제공.
4. 구성적 증명: 존재성만 증명하는 것이 아니라 구체적인 구성 방법 제시.

부족한 점

1. 실용성 제한: 이론적 결과가 실제 응용에서 차원의 저주에 직면할 수 있음.
2. 실험 검증 부족: 대규모 수치 실험으로 이론적 결과를 검증하는 것이 부족함.
3. 최적화 알고리즘 부재: 이러한 MPS 모델을 효율적으로 훈련하는 방법에 대한 논의 부족.
4. 비교 분석 미흡: 다른 범용 근사기와의 상세한 비교 분석이 부족함.

영향력

1. 이론적 가치 높음: 텐서 네트워크의 기계학습 응용에 견고한 이론적 기초 제공.
2. 학제 간 의의: 양자 물리학과 기계학습 두 분야를 연결.
3. 영감 제공: 텐서 네트워크의 표현 능력과 최적화 방법에 대한 후속 연구에 중요한 참고 자료 제공.

적용 분야

1. 이론 연구: 텐서 네트워크 표현 이론의 기초 문헌으로 적합.
2. 교육 목적: MPS와 신경망의 관계를 설명하는 데 사용 가능.
3. 알고리즘 설계: MPS 기반 기계학습 알고리즘 설계에 이론적 지도 제공.
4. 양자 기계학습: 양자 기계학습 알고리즘 설계에 이론적 지원 제공.

참고문헌

본 논문은 텐서 네트워크, 양자 정보, 기계학습 및 함수해석학 등 여러 분야의 중요 문헌을 인용하고 있으며, 다음을 포함한다:

• 텐서 네트워크 기초 이론 (Penrose, 1971; Vidal, 2007; Perez-Garcia et al., 2006)
• 신경망 범용 근사 이론 (Cybenko, 1989; Hornik, 1991)
• 기계학습에서의 텐서 네트워크 응용 (Stoudenmire & Schwab, 2016; 등)
• 함수해석학 이론 기초 (Folland, 2013)