Ph.D. defense "Convex Manifold Approximation for Tensors"

Convex Manifold Approximation for Tensors
ガラムカリ和
総合研究大学院大学
複合科学研究科情報学専攻
博士論文発表会
February 1, 2023
審査委員：杉山麿人, 𠮷田悠一, 井上克巳, 山田誠, 三村和史（敬称略）

View Slide

2
Motivation
2
□様々な構造を有するデータの非負低ランク近似
2

View Slide

3
Motivation
3
3
少ない基底(主成分)の線形結合で近似し，特徴量の抽出，メモリの削減，パターンの発見 😀
≃
≃
≃
≃

View Slide

4
Motivation
4
4
≃
≃
≃
≃
停止条件，学習率，初期値，ランクの適切な設計が必要 😢

View Slide

5
Motivation
5
5
≃
≃
≃
≃
停止条件，学習率，初期値，ランクの適切な設計が必要 😢
データの空間の幾何的な構造に注目して，これらの困難を緩和😀

View Slide

6
Strategy
□ データ構造を有向非巡回グラフ(DAG)上の離散確率分布として扱う.
6

View Slide

7
Strategy
□ 情報幾何学の射影に関する理論を適用する．
7

View Slide

8
8
Strategy
□ 情報幾何学の射影に関する理論を適用する．

View Slide

9
□ LTR: 低タッカーランク近似法
9
本研究の貢献
Chapter 3

View Slide

10
10
□ 欠損行列の高速ランク１近似
本研究の貢献
適用
解の公式を導出
Chapter 3 Chapter 4

View Slide

11
11
本研究の貢献
低ランク構造ではなく，
モード間の関係に注目した凸な分解
適用
Chapter 3 Chapter 4 Chapter 5
□ テンソル多体近似
(相互作用表示)

View Slide

12
12
勾配法に基づかず，学習率, 収束判定の設計が不要で高速な手法を開発 ✨
本研究の貢献
ランクのチューニングが不要✨
低ランク構造ではなく，
モード間の関係に注目した凸な分解
適用
Chapter 3 Chapter 4 Chapter 5
□ テンソル多体近似
データ(テンソル)の空間の幾何や平坦性に注目して，最適化と解空間の設計を工夫している
(相互作用表示)

View Slide

13
13
多様な構造の配列の低ランク近似を統一的に議論
□ 様々な行列/テンソルの構造を捉える柔軟なモデリング
行列やテンソルの構造を捉えたDAG(有向非巡回グラフ)上の対数線形モデルで低ランク近似を定式化．

View Slide

14
□ 半順序集合 (DAG) 集合の任意の要素𝑠1
, 𝑠2
, 𝑠3
∈ に次の関係があるときに，を半順序集合と呼ぶ．
(1)反射律: 𝑠1
≤ 𝑠1
(2)反対称律: 𝑠1
≤ 𝑠2
, 𝑠2
≤ 𝑠1
⇒ 𝑠1
= 𝑠2
(3)推移律:𝑠1
≤ 𝑠2
, 𝑠2
≤ 𝑠3
⇒ 𝑠1
≤ 𝑠3
□ 半順序集合上の対数線形モデル
写像𝑝: → 0,1 として，順序集合上の対数線形モデルを定義する．自然パラメータ𝜽で分布が定まる．
𝜃空間 𝜂空間
メビウス関数𝜇を用いて，期待値パラメータ𝜼で分布を定めることもできる．
Sugiyama, M., Nakahara, H., & Tsuda, K. Tensor balancing on statistical manifold. ICML2017
14
メビウス関数
入力のデータ構造
半順序集合上の対数線形モデル

View Slide

Chapter 3. Legendre Tucker Rank Reduction
github.com/gkazunii/Legendre-tucker-rank-reduction
1.Ghalamkari, K., Sugiyama, M. NeurIPS 2020 WS DiffGeo4DL
2.Ghalamkari, K., Sugiyama, M. NeurIPS 2021
3.Ghalamkari, K., Sugiyama, M. Information Geometry Journal (Springer)
★ (前半) テンソルランク１近似
★ (後半) ビンゴルールによるタッカーランク削減
6:15

View Slide

テンソルに対応する半順序集合の導入
16

View Slide

テンソルに対応する半順序集合の導入
17

View Slide

(θ,η)でテンソルを記述する
18

View Slide

19
メビウス反転公式

View Slide

20

View Slide

21
確率変数：テンソルの添字𝑖, 𝑗, 𝑘
標本空間：添字集合
確率の値：テンソルの値𝒫𝑖𝑗𝑘
テンソルと確率分布の対応

View Slide

１体のパラメータと多体のパラメータの導入
22
１体のパラメータ多体のパラメータ

View Slide

テンソルのランク１条件のθ表示
23
全ての多体の𝜃-パラメータが0.
ランク１条件(𝜽-表示)

View Slide

24
は，e-平坦で射影先の点は一意．

View Slide

25
勾配法で射影先の点が見つかる！
But!! 勾配法は，初期値依存，停止条件，学習率の設定などが厄介 😢😢

View Slide

26
勾配法で射影先の点が見つかる！
But!! 勾配法は，初期値依存，停止条件，学習率の設定などが厄介 😢😢
期待値パラメータ𝜂でランク１条件を記述してみる．

View Slide

テンソルのランク１条件のη表示
27
𝜂𝑖𝑗𝑘
= 𝜂𝑖11
𝜂1𝑗1
𝜂11𝑘
ランク１条件(𝜼-表示)

View Slide

テンソルのランク１条件のη表示
28
１体の𝜼-パラメータは𝑚-射影の前後で変化しない.
=
=
=
𝜂𝑖𝑗𝑘
= 𝜂𝑖11
𝜂1𝑗1
𝜂11𝑘
Shun-ichi Amari, Information Geometry and Its Applications, 2008, Theorem 11.6

View Slide

テンソルのランク１近似公式の導出
29
𝜂𝑖𝑗𝑘
= 𝜂𝑖11
𝜂1𝑗1
𝜂11𝑘
射影後の全ての𝜼-パラメータが特定できた.
メビウス反転公式より，射影後のランク１テンソルが求まる．
10:00

View Slide

テンソル𝒫 ∈ ℝ>0
𝐼×𝐽×𝐾の各軸方向の和の積で得るテンソル
は，𝒫 ∈ ℝ>0
𝐼×𝐽×𝐾からのKL情報量を最小化するランク１テンソルである．
𝑖のみに依存する
規格化ベクトル
𝑗のみに依存する
𝑘のみに依存する
添字が3個で総和が１のテンソルを，確率変数が3個ある同時分布とみなしていた．
添字が1個で総和が１のベクトルは，確率変数が1つしかない分布とみなせる．
テンソルのランク１近似は同時分布を確率変数が１つしかない分布の積で近似する操作
KL情報量最小化の最良ランク１近似公式 (𝒅 = 𝟑 の場合)
平均場近似:多体問題を一体問題に帰着する方法論として物理学では頻繁に登場
30
ちなみに…
フロベニウス誤差
最小化はNP困難
最良ランク１分解公式と平均場近似
K.Huang, et al. “Kullback-Leibler principal component for tensors is not NP-hard.” ACSSC 2017 の結果を情報幾何学の観点から再現

View Slide

ランク１近似と平均場近似
ボルツマンマシンの平均場近似
𝑝 𝒙 =
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
+ ෍
𝑖<𝑗
𝜃𝑖𝑗
𝑥𝑖
𝑥𝑗
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
𝜂𝑖
= ෍
𝑥1=0
1
⋯ ෍
𝑥𝑛=0
1
𝑥𝑖
𝑝 𝒙
重み
(相互作用)
バイアス
（磁場）
𝒙 ∈ 0,1 𝑛
31

View Slide

𝑝 𝒙 =
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
+ ෍
𝑖<𝑗
𝜃𝑖𝑗
𝑥𝑖
𝑥𝑗
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
𝜂𝑖
= ෍
𝑥1=0
1
⋯ ෍
𝑥𝑛=0
1
𝑥𝑖
𝑝 𝒙
重み
バイアス
=
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
= 𝑝 𝑥1
… 𝑝(𝑥𝑛
)
𝒙 ∈ 0,1 𝑛
32

View Slide

𝑂 2𝑛
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
𝐷𝐾𝐿
Ƹ
𝑝𝑒
, 𝑝
ҧ
𝜂𝑖
= sigmoid 𝜃𝑖
+ ෍
𝑘
𝜃𝑘𝑗
ҧ
𝜂𝑘
平均場方程式
𝑝 𝒙 =
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
+ ෍
𝑖<𝑗
𝜃𝑖𝑗
𝑥𝑖
𝑥𝑗 𝜂𝑖
= ෍
𝑥1=0
1
⋯ ෍
𝑥𝑛=0
1
𝑥𝑖
𝑝 𝒙
𝑂 2𝑛
重み
バイアス
𝒙 ∈ 0,1 𝑛
33

View Slide

テンソルのランク１近似
𝑝𝜃
(𝑖, 𝑗, 𝑘) = exp ෍
𝑖′=1
𝑖
෍
𝑗′=1
𝑗
෍
𝑘′=1
𝑘
𝜃𝑖′𝑗′𝑘′
𝑂 2𝑛
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
平均場方程式
独立分布の積からなる分布の集合
𝜂𝑖11
= ෍
𝑗′=1
𝐽
෍
𝑘′=1
𝐾
𝒫𝑖𝑗′𝑘′
ҧ
𝜂𝑖
= sigmoid 𝜃𝑖
+ ෍
𝑘
𝜃𝑘𝑗
ҧ
𝜂𝑘
𝐷𝐾𝐿
Ƹ
𝑝𝑒
, 𝑝
𝑝 𝒙 =
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
+ ෍
𝑖<𝑗
𝜃𝑖𝑗
𝑥𝑖
𝑥𝑗 𝜂𝑖
= ෍
𝑥1=0
1
⋯ ෍
𝑥𝑛=0
1
𝑥𝑖
𝑝 𝒙
𝑂 2𝑛
重み
バイアス
𝒙 ∈ 0,1 𝑛
34

View Slide

𝑝𝜃
(𝑖, 𝑗, 𝑘) = exp ෍
𝑖′=1
𝑖
෍
𝑗′=1
𝑗
෍
𝑘′=1
𝑘
𝜃𝑖′𝑗′𝑘′
𝑂 2𝑛
𝑂 𝐼𝐽𝐾
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
𝐷𝐾𝐿
𝑝, Ƹ
𝑝
平均場方程式
独立分布の積からなる分布の集合
𝜂𝑖11
= ෍
𝑗′=1
𝐽
෍
𝑘′=1
𝐾
𝒫𝑖𝑗′𝑘′
ҧ
𝜂𝑖
= sigmoid 𝜃𝑖
+ ෍
𝑘
𝜃𝑘𝑗
ҧ
𝜂𝑘
計算可能
𝐷𝐾𝐿
Ƹ
𝑝𝑒
, 𝑝
𝑝 𝒙 =
1
𝑍(𝜽)
exp ෍
𝑖
𝜃𝑖
𝑥𝑖
+ ෍
𝑖<𝑗
𝜃𝑖𝑗
𝑥𝑖
𝑥𝑗 𝜂𝑖
= ෍
𝑥1=0
1
⋯ ෍
𝑥𝑛=0
1
𝑥𝑖
𝑝 𝒙
𝑂 2𝑛
重み
バイアス
𝒙 ∈ 0,1 𝑛
テンソルのランク１近似
35 13:00

View Slide

github.com/gkazunii/Legendre-tucker-rank-reduction
1.Ghalamkari, K., Sugiyama, M. NeurIPS 2020 WS DiffGeo4DL
2.Ghalamkari, K., Sugiyama, M. NeurIPS 2021
★ (前半) テンソルランク１近似
★ (後半) ビンゴルールによるタッカーランク削減

View Slide

ランク１条件を緩和して，タッカーランク削減を定式化する
𝜃𝑖𝑗𝑘
= 0
𝜃112
𝜃131
𝜃121
𝜃113
𝜃211
𝜃311
𝒎番目の軸に注目してテンソルを展開して矩形行列𝜽(𝒎)にする（モード𝒎展開）
𝜃(1) =
𝜃111
𝜃121
𝜃131
𝜃112
0 0 𝜃113
0 0
𝜃211
0 0 0 0 0 0 0 0
𝜃311
0 0 0 0 0 0 0 0
𝜃(2) =
𝜃111
𝜃211
𝜃311
𝜃112
0 0 𝜃311
0 0
𝜃121
0 0 0 0 0 0 0 0
𝜃131
0 0 0 0 0 0 0 0
𝜃(3) =
𝜃111
𝜃211
𝜃311
𝜃121
0 0 𝜃131
0 0
𝜃112
0 0 0 0 0 0 0 0
𝜃113
0 0 0 0 0 0 0 0
ランク 1,1,1
ビンゴ２つ
rank 𝒫 = 1 ⟺ 多体の自然パラメータ𝜃が全て0
ランク１条件(𝜽表示)
ビンゴ２つ
ビンゴ２つ
１行(列)目は，他の行(列)の何倍かを表す
37

View Slide

ビンゴとランクの関係
テンソル𝒫 ∈ ℝ𝐼1×𝐼2×𝐼3の 𝜃のモード𝑚展開𝜃(𝑚)が𝑏𝑚
個のビンゴを有する ⇒ rank 𝒫 ≤ 𝐼1
− 𝑏1
, 𝐼2
− 𝑏2
, 𝐼3
− 𝑏3
𝜃(1) =
𝜃111
𝜃121
𝜃131
𝜃112
0 0 𝜃113
0 0
𝜃211
0 0 0 0 0 0 0 0
𝜃311
𝜃321
𝜃331
𝜃312
𝜃322
𝜃332
𝜃313
𝜃323
𝜃333
𝜃(2) =
𝜃111
𝜃211
𝜃311
𝜃112
0 𝜃312
𝜃311
0 𝜃313
𝜃121
0 𝜃321
0 0 𝜃322
0 0 𝜃323
𝜃131
0 𝜃331
0 0 𝜃332
0 0 𝜃333
𝜃(3) =
𝜃111
𝜃211
𝜃311
𝜃121
0 𝜃321
𝜃131
0 𝜃331
𝜃112
0 𝜃312
0 0 𝜃322
0 0 𝜃332
𝜃113
0 𝜃313
0 0 𝜃323
0 0 𝜃333
ビンゴ１つ
ビンゴルール(𝑑 = 3 の場合)
𝜃123
●
●
𝒫
ത
𝒫
入力テンソル
𝐷𝐾𝐿
𝒫, ത
𝒫
𝑚射影
モード1方向の2行目の𝜃が全て0の空間ℬ 1
ビンゴなし
ビンゴなし
ランク 2,3,3
38

View Slide

STEP1 : ビンゴの場所を選ぶ．
ビンゴ
ビンゴ
ビンゴ
𝜃がゼロ
39
𝜃が任意
例：(8,8,3)のテンソルのランクを(5,8,3)以下にする．

View Slide

網掛けの部分はm射影で値が変わらない
𝜃がゼロ
𝜃が任意
40

View Slide

赤枠の部分テンソルを最良ランク１近似公式を用いて置換
STEP2 : ビンゴの部分をランク１テンソルで置換する
𝜃がゼロ
𝜃が任意
41

View Slide

赤枠の部分テンソルを最良ランク１近似公式を用いて置換
𝜃がゼロ
𝜃が任意
指定したビンゴ空間の中では最良のランク(5,8,3)テンソルが得られる 😄
最良のランク(5,8,3)近似になっている保証はない 😢 42

View Slide

𝜃がゼロ
𝜃が任意
43

View Slide

●
●
𝒫
ℬ 1
ℬ 2
ℬ 1 への射影後にℬ 2 へ射影してℬ 1 ∩ ℬ 2 に達する
(5,8,3)
𝜃がゼロ
𝜃が任意
44

View Slide

45
実験結果(合成データ)
既存の手法と同程度の近似性能で，高速な低ランク近似を実現
勾配法

View Slide

46
既存の手法と同程度の近似性能で，高速な低ランク近似を実現
(92, 112, 400) (9, 9, 512, 512, 3)

View Slide

Chapter 4. A1GM
github.com/gkazunii/A1GM
1.Ghalamkari, K., Sugiyama, M. AISTATS 2022
★ (前半) 複合行列因子分解(NMMF)の解の公式の導出
★ (後半) 解の公式に基づく欠損値を含む行列の高速なランク１近似

View Slide

49
欠損を含む行列のランク１分解の解法のアイデア
□ 欠損値を右下に集めることで複合行列分解(NMMF)に帰着する.
49
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
要素積
クロネッカー積

View Slide

50
等価
50
NMMF (Takeuchi et al., 2013)
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
要素積

View Slide

51
等価
51
ランク１分解の解の公式が導出可能
→高速な分解が可能になる！
NMMF (Takeuchi et al., 2013)
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
要素積

View Slide

52
NMMF, 複合行列分解 (Takeuchi et al., 2013)
52
user
artist
tag
user
user
tag
artist user
user
artist

View Slide

53
NMMF, 複合行列分解の最良ランク１近似
最良ランク１分解公式
53
user
artist
tag
user
user
tag
artist user
user
artist
21:00

View Slide

54
確率値は対応する行列の要素と一致する
□ 例
54

View Slide

55
1体のパラメータと2体のパラメータ
𝑿, 𝒀, 𝒁 が同時ランク１分解可能. ⇔ 𝑿, 𝒀, 𝒁 が 𝒘 ⊗ 𝒉, 𝒂 ⊗ 𝒉, 𝒘 ⊗ 𝒃 とかける
55

View Slide

56
同時ランク１条件の自然パラメータ表示
56
同時ランク１条件(𝜽-表示)

View Slide

57
同時ランク１条件の自然パラメータ表示
57

View Slide

58
同時ランク１条件の期待値パラメータ表示
58
𝜂𝑖𝑗
= 𝜂𝑖1
𝜂1𝑗
同時ランク１条件(𝜼-表示)

View Slide

59
最良ランク１近似公式の導出
59
𝜂𝑖𝑗
= 𝜂𝑖1
𝜂1𝑗

View Slide

60
最良ランク１近似公式の導出
射影後の全ての𝜼-パラメータが特定できた.
60
𝜂𝑖𝑗
= 𝜂𝑖1
𝜂1𝑗

View Slide

61
欠損を含む行列のランク１分解
□ NMMFは欠損を含むNMFの特別な場合と等価.
等価
□ NMFは行置換と列置換に同変
61 24:15

View Slide

62
A1GM: アルゴリズム
Step 1 : 行置換と列置換で欠損を右下に集める．
Step 2 : NMMFの最良ランク1近似公式を用いる．
62
Step 3 : Step1で施した行置換と列置換の逆置換を施す．
欠損を含むNMFの厳密解が求まる？

View Slide

63
Step 2 : NMMFの最良ランク1近似公式を用いる．
63
Step 3 : Step1で施した行置換と列置換の逆置換を施す．
欠損を含むNMFの厳密解が求まる？

View Slide

64
行置換と列置換のみでNMMFに帰着できない例
64

View Slide

65
65

View Slide

66
66

View Slide

67
欠損を増やしてNMMFに帰着させる
67

View Slide

68
68
再構成誤差は悪化？ 😢

View Slide

69
69
計算速度は向上！ 😀
再構成誤差は悪化？ 😢

View Slide

70
🙆A1GMが得意なケースと苦手なケース🙅
70
実データでは，欠損が同じ行や列に集中しがち．
例) アンケートフォーム, センサーの断線
🙅 各行・各列にまんべんなく欠損がある → 欠損値が増える
🙆 欠損が特定の行や列に集中している → 欠損値の増え方が小さい
欠損数3 欠損数9

View Slide

71
Step 1 : 欠損を増やす．
Step 3 : NMMFの最良ランク１近似公式を適用する.
71
Step 4 : Step 2で施した行置換と列置換の逆置換を施す．
欠損を増やさずに済めば厳密解
欠損を増やすと近似解が求まる

View Slide

72
実データセットでの実験
□ 勾配法に基づくKL-WNMFとの比較
- 欠損増加率は，欠損が何倍になったかを意味する．
- 相対誤差 > 1 は A1GM の再構成誤差が KL-WNMF よりも大きいことを意味する.
- 相対実行時間 < 1 は A1GM が KL-WNMF よりも高速であることを意味する．
5～10倍高速!
72
欠損は増えない
最良解
欠損は増える
解の精度が落ちる
28:00

View Slide

73
拡張NMMFと欠損値を含むランク１NMFの厳密解
拡張NMMFの最良ランク１分解公式
73

View Slide

74
74
等価
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise

View Slide

75
75
If rank(𝚽) ≦2,
the matrix can be transformed into the form
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
置換
等価

View Slide

76
76
If rank(𝚽) ≦2,
the matrix can be transformed into the form
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
置換
rank(𝚽) ≦2 の欠損を含むランク１分解は厳密に解ける.
等価

View Slide

77
77
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
置換
等価
欠損を増やす

View Slide

78
78
𝚽𝑖𝑗
= ቊ
0
1
If 𝐗𝑖𝑗
is missing
otherwise
置換
等価
欠損を増やす
But, How?
(Future Work)

View Slide

Chapter 5. Many-body Approximation for Tensors
1.Ghalamkari, K., Sugiyama, M. ICML2023 (Under Review)
★ (前半) 多体近似の定式化
★ (後半) 多体近似と従来の低ランク近似の関係性の指摘
30:00

View Slide

80
80
ランクｒ近似の解空間全体は平坦でない
全ての多体のθパラメータが0
(4次元テンソルを3次元テンソル3つで可視化)

View Slide

81
81
ランクｒ近似の解空間全体は平坦でない
ランク１の和(m結合)で
表現力を向上
【低ランク近似】
LTRでは，平坦でない解空間から
平坦な部分空間を選択して凸問題として近似的に解いた．
解空間が初めから平坦な新しい近似を新たに定義したら便利

View Slide

82
テンソル多体近似のアイデア
表現力を向上

View Slide

83
全ての三体，四体のθパラメータが0
表現力を向上
一体のパラメータ
二体のパラメータ
三体のパラメータ
四体のパラメータ

View Slide

84
多体のパラメータ 84
全ての三体，四体のθパラメータが0
表現力を向上
一体のパラメータ
三体のパラメータ
𝜃𝑖111
, 𝜃1𝑗11
, 𝜃111𝑘
, 𝜃111𝑙
一体のパラメータ三体のパラメータ
𝜃𝑖𝑗11
, 𝜃𝑖1𝑘1
, … , 𝜃11𝑘𝑙
𝜃𝑖𝑗𝑘1
, 𝜃𝑖1𝑘𝑙
, 𝜃𝑖𝑗1𝑙
, 𝜃𝑖𝑗𝑘1
𝜃𝑖𝑗𝑘𝑙

View Slide

85
テンソル多体近似

View Slide

86
規格化因子

View Slide

87
一体近似
ランク１近似，平均場近似

View Slide

88
一体近似
二体近似

View Slide

89
一体近似
三体近似
二体近似
モデルの表現力
大

View Slide

90
一体近似
三体近似
二体近似
自然パラメータの線形な条件で記述される部分空間への射影＝凸最適化で解ける！
大

View Slide

91
テンソル多体近似の相互作用表示
一体近似
相互作用の有無を可視化するダイアグラムを導入
三体近似
二体近似
モード(3,4)間の関係
を制御

View Slide

92
一体近似
三体近似
二体近似
を制御
モード(2,3,4)間の関係
を制御

View Slide

93
一体近似
三体近似
二体近似
を制御
を制御

View Slide

94
一体近似
三体近似
二体近似
を制御
を制御

View Slide

95
一体近似
三体近似
二体近似

View Slide

96
96
巡回二体近似

View Slide

97
97
巡回二体近似

View Slide

98
98
巡回二体近似
巡回二体近似で0に拘束されないパラメータ

View Slide

99
99
巡回二体近似
n体のパラメータで，モード間のn体の相互作用を制御できる．
34:30

View Slide

100
巡回二体近似とリング分解
巡回二体近似
相互作用表示

View Slide

101
巡回二体近似
相互作用表示
テンソル
ネットワーク
= Ω𝑖𝑗𝑘
= 𝛿𝑖𝑗
𝛿𝑗𝑘
𝛿𝑖𝑘

View Slide

102
巡回二体近似テンソルリング分解
Qibin Zhao, et al., 2016
相互作用表示
テンソル
ネットワーク
= Ω𝑖𝑗𝑘
= 𝛿𝑖𝑗
𝛿𝑗𝑘
𝛿𝑖𝑘

View Slide

103
相互作用表示
テンソル
ネットワーク
= Ω𝑖𝑗𝑘
= 𝛿𝑖𝑗
𝛿𝑗𝑘
𝛿𝑖𝑘

View Slide

104
巡回二体近似は拘束条件付きテンソルリング分解．
相互作用表示
テンソル
ネットワーク
= Ω𝑖𝑗𝑘
= 𝛿𝑖𝑗
𝛿𝑗𝑘
𝛿𝑖𝑘
超対角テンソルを挟むと凸問題に帰着される．
帰着

View Slide

105
低ランク近似と多体近似の関係
□ 部分三体近似とテンソルツリー分解
テンソルツリー分解
テンソルリング分解
□ 巡回二体近似とテンソルリング分解

View Slide

106
数値実験
テンソルリング分解
VS.
・凸最適化
・ランクのチューニング不要
巡回二体近似
・非凸最適化（初期値依存性）
・ランクのチューニングが必要

View Slide

107
107
実験結果
初期値依存性があるので5回繰り返して，
最もよい結果をプロット
交点が提案手法の性能
合成データ実データ
YuYuan Yu, et al., 2021

View Slide

108
本研究の適用限界
□ 入力テンソルの非負性
□ KL情報量での最適化
□ DAGは学習しない
・情報幾何学（確率分布の幾何学）に基づく定式化のため，
入力データと分解表現に非負性が課される．
・テンソル分解の最も一般的なコスト関数はフロベニウスノルム．
KL情報量の最適化がフロベニウスノルムをどの程度小さくするかの理論的保証はない．
・入力データの構造に対応するDAGを手動で設計した．
本研究では，入力データの構造が動的に変化する状況は扱えない．

View Slide

113
まとめ
■ 多次元配列を離散分布とみなし，情報幾何学の双対平坦な座標系で次元削減を定式化した．
■ 解空間の平坦性 → 解の初期値依存性を取り除いた．
■ 双対平坦な座標系の性質 → 厳密解に基づく議論 → 学習率や停止問題の問題を取り除いた．
■ 平均場近似や相互作用など，物理学の諸概念から着想を得たユニークな研究になっている．

View Slide

114
まとめ
・双対平坦な座標系でのテンソルランク１近似の公式と平均場近似の幾何的な関係を指摘．
・勾配法に基づかないタッカーランク近似の高速な実装．

View Slide

115
まとめ
Chapter 4. A1GM
・双対平坦な座標系の性質を用いてランク１複合行列分解の解の公式を閉形式で導出.
・欠損を含む行列分解への応用．欠損を増やすことで，勾配法に基づかない最適化．

View Slide

116
まとめ
Chapter 4. A1GM
・双対平坦な座標系の性質を用いてランク１複合行列分解の解の公式を閉形式で導出.
・欠損を含む行列分解への応用．欠損を増やすことで，勾配法に基づかない最適化．
Chapter 5. Many-body Approximation for Tensors
・自然パラメータを用いてモード間の相互作用が制御できることに注目．
・低ランク構造に着目しない，ランクフリーな分解を実現．
・相互作用表示をテンソルネットワークに書き直し，低ランク近似との関係も議論．
・自然勾配法に基づいた高速な凸最適化による分解を実現．

View Slide

118
１体近似は線，２体近似は面で近似する．

View Slide

120
KL情報量での最適化
・音響，音声，ノイズを含むデータに対するKL-NMFの頑健性は良く知られている．
・データがポアソン分布に従う場合は，KL-NMFの誤差関数が最尤推定と一致して，自然な分解
・多くの行列分解ライブラリでは，LS-NMFとKL-NMFの両方が実装されている．
(e.g., sk-learn)
・誤りに対して，誤差の増加が緩やかで過学習しにくい．
二乗誤差最適化よりもロバストな指標として頻繁に用いられる．

View Slide

121
応用: 多体近似による画像復元
□ emアルゴリズムによる欠損値補完ができる
モデル多様体が平坦でない
モデル多様体がe平坦
m-平坦のデータ多様体と e-平坦なモデル多様体間の emアルゴリズムは大域解がが求まる😄
二体近似による画像の復元

View Slide

122
0の扱い
𝜃11
𝜃21
𝜃12
𝜃22
𝜂11
𝜂21
𝜂12
𝜂22
𝒫22
= exp 𝜃11
+ 𝜃12
+ 𝜃21
+ 𝜃22
𝒫11
= exp 𝜃11
𝒫12
= exp 𝜃11
+ 𝜃12
𝒫21
= exp 𝜃11
+ 𝜃21
𝒫22
= 𝜂22
𝒫11
= 𝜂11
− 𝜂21
− 𝜂12
+ 𝜂22
𝒫12
= 𝜂12
− 𝜂22
𝒫21
= 𝜂21
− 𝜂22
数値計算では𝜂𝑖𝑗
= 0にして0を扱う．
𝜃表示だとexpの性質から0を扱えない．

View Slide

123
KLエラーもLSエラーも小さくできている．
19:00

View Slide

124
テンソル多体近似による動画再構成例
一体近似三体近似
二体近似
大
入力

View Slide

125
テンソル多体近似によるパターン抽出の例
入力テンソル再構成テンソル
≃
≃
≃ =
=
=

View Slide

126
テンソル多体近似によるパターン抽出の例
入力テンソル再構成テンソル
≃
≃
≃ =
=
=

View Slide

Ph.D. defense "Convex Manifold Approximation for Tensors"

Ph.D. defense "Convex Manifold Approximation for Tensors"

Kazu Ghalamkari

More Decks by Kazu Ghalamkari

Other Decks in Science

Featured

Transcript