行列積状態の表現定理

基本情報

• 論文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. 加法に対する閉包性: 2つのMPSの和を表現する新しいMPSを構成

判別性質 (補題3.4): スケール不変シグモイド関数が判別性質を持つことを証明する: すべてのMPS関数の積分が0となる有限符号測度$\mu$が存在する場合、$\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. 分野横断的意義: 量子物理学と機械学習の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)