非負テンソルの多体近似

第26回 情報論的学習理論ワークショップ(IBIS2023), 企画セッション テンソルネットワーク,
福岡，北九州国際会議場, 29 Oct. – 1 Nov. 2023

[Video] https://www.youtube.com/watch?v=THLCzbIKU7E

[Paper] https://neurips.cc/virtual/2023/poster/72780

Ghalamkari, K., Sugiyama, M., & Kawahara, Y. (2023). Many-body approximation for non-negative tensors. Advances in Neural Information Processing Systems, 36, 74077-74102.

Transcript

1. 非負テンソルの多体近似 理化学研究所 革新知能統合研究センター https://arxiv.org/abs/2209.15338 ガラムカリ 和 第26回情報論的学習理論ワークショップ, 2023-10-29〜11-01, 北九州国際会議場, 企画セッション『テンソルネットワーク』 Many-Body Approximation for Non-negative Tensors
2. 非負テンソルからパターンや特徴を抽出したい 3 人 👨 👩 😸 店舗 ≃ = ത 𝒫 minmize 𝒫 − ത 𝒫 𝐹 + ⋯ + 𝒫 ▪ 実世界の様々なデータが非負テンソルとして格納される データからパターンや特徴を抽出したい ▪ 非負テンソルを分解することでデータから特徴を抽出する モード２ モード１
3. テンソル分解の様々な課題 4 ▪ 分解の構造とランクをあらかじめ決める必要がある CP分解 ≃ = 𝒫 ത 𝒫 ≃ タッカー分解 テンソルネットワークを用いた分解 + ⋯ + テンソルトレイン分解 テンソルリング分解 𝒫
4. テンソル分解の様々な課題 5 ▪ 分解の構造とランクをあらかじめ決める必要がある CP分解 ≃ = 𝒫 ത 𝒫 ▪ 最適化の困難さ ・😢 最良ランク１分解はNP困難 ≃ タッカー分解 テンソルネットワークを用いた分解 + ⋯ + 凸で安定なテンソル分解を開発したい minmize 𝒫 − ത 𝒫 𝐹 ※ フロベニウスノルム最小化のランク１近似がNP困難 非凸関数 𝒫 − ത 𝒫 𝐹 （解が無限個 etc..） … ・😢 解が不定になることも多い ・😢 誤差が非凸関数 ・解が初期置に依存（計算のたびに結果が異なる） ・最良解かどうかが分からない 最良解になっている保証なし テンソルトレイン分解 テンソルリング分解 𝒫
5. 提案手法: 非負テンソルの多体分解 6 指数型分布族の自然パラメータ エネルギー関数 規格化定数
6. 提案手法: 非負テンソルの多体分解 7 指数型分布族の自然パラメータ エネルギー関数
7. 提案手法: 非負テンソルの多体分解 8 モード k, l 間の 関係を制御 モード j, k, l 間の 関係を制御 指数型分布族の自然パラメータ エネルギー関数
8. 提案手法: 非負テンソルの多体分解 9 一体近似 ランク１近似（平均場近似） [NeurIPS 2021 Ghalamkari, K., Sugiyama, M. ]
9. 提案手法: 非負テンソルの多体分解 10 一体近似 二体近似 モード k, l 間の 関係を制御 表現力 大 ランク１近似（平均場近似） [NeurIPS 2021 Ghalamkari, K., Sugiyama, M. ] 二体相互作用
10. 提案手法: 非負テンソルの多体分解 11 一体近似 二体近似 二体相互作用 三体近似 表現力 大 モード間の相互作用に着目した直感的なモデリングが可能 モード j, k, l 間の 関係を制御 モード k, l 間の 関係を制御 三体相互作用 ランク１近似（平均場近似） [NeurIPS 2021 Ghalamkari, K., Sugiyama, M. ] をKL情報量の意味で最もよく近似する が凸最適化で一意に求まる！ 11
11. 提案手法の背景にあるアイデア 12 規格化された非負テンソル を，添字集合が標本空間である同時離散確率分布とみなし，情報幾何学を転用する． 添字が離散確率変数 💡 𝜽-表現 座標 変換 指数型分布族の自然パラメータで表現 𝜽-の幾何学 低ランク空間 （非平坦） 平坦な空間 最適化が困難 テンソルの分解条件を𝜽 -座標で記述することで，凸問題としての定式化が容易になる． モード間の相互作用に着目して 平坦なモデル空間を構成
12. 確率分布と非負テンソルの対応付け 13 3×3×3テンソルに対応する 同時離散分布の標本空間
13. 確率分布と非負テンソルの対応付け 14 確率変数 標本空間 確率値 ： テンソルの添字 𝑖, 𝑗, 𝑘 ： 添字集合に半順序を導入した集合 ： テンソルの値 𝒫𝑖𝑗𝑘 半順序構造 上の対数線形モデル 確率分布と非負テンソルの対応 3×3×3テンソルの標本空間に 半順序構造を導入した空間
14. 確率分布と非負テンソルの対応付け 15 3×3×3テンソルの標本空間に 半順序構造を導入した空間 確率変数 標本空間 確率値 ： テンソルの添字 𝑖, 𝑗, 𝑘 ： 添字集合に半順序を導入した集合 ： テンソルの値 𝒫𝑖𝑗𝑘 半順序構造 上の対数線形モデル 確率分布と非負テンソルの対応
15. 自然パラメータでの特徴づけ 確率変数 標本空間 確率値 ： テンソルの添字 𝑖, 𝑗, 𝑘 ： 添字集合に半順序を導入した集合 ： テンソルの値 𝒫𝑖𝑗𝑘 半順序構造 上の対数線形モデル 確率分布と非負テンソルの対応 非負テンソル を指数型分布族の自然パラメータ θ で記述 16 3×3×3テンソルの標本空間に 半順序構造を導入した空間 最適化に関する便利な性質がある
16. パラメータ空間の一点が入力テンソルに対応 17
17. パラメター空間での拘束条件 18 （経験分布） θ の線形な条件で拘束される部分空間（モデル空間）は e-平坦 e-平坦なモデル空間
18. パラメター空間での拘束条件 19 射影後の分布 が積の形で書けるようなモデル空間をθ の線形な条件で設計した． （経験分布） θ の線形な条件で拘束される部分空間（モデル空間）は e-平坦 😄 e-平坦な空間へのKL情報量最小化の射影は凸で一意に実現 e-平坦なモデル空間 指数型分布族 の最尤推定 は凸問題 （テンソル） m-射影
19. テンソル多体分解 20 添字に“1”を含むθ-パラメータは，テンソルのモード間の関係を制御している． 多体分解は，これらのθ-パラメータをm-射影によって削減する． 😄 凸最適化問題 😄 最適解の一意性 エネルギー関数 でも…，相互作用はどのように選択するの？ 🤔
20. 適用例：テンソル多体近似によるカラー画像の再構成 表現力 大 Reconstruction for 40×40×3×10 tensor. (width, height, colors, # images) 画像ごとに 色が変化 画像ごとの形を表現 画像内で色は一定 モード間の関連を捉えた直感的なモデル設計が可能 画像内の場所（画素） ごとに色が変化 三体近似 21
21. カラー画像を オブジェクトの 形×色 に分解 近似
22. カラー画像を オブジェクトの 形×色 に分解 × ≃ = 画像ごとの形 画像ごとの色 3×10 40×40×10
23. テンソル多体分解とテンソルネットワークの関係
24. 巡回二体近似とテンソルリング分解 30 巡回二体近似 相互作用表示 テンソルネットワーク テンソルリング分解 Qibin Zhao, et al., 2016 帰着 巡回二体近似は拘束条件付きテンソルリング分解．超対角テンソルを挟むと凸問題に帰着される．
25. 低ランク近似と多体近似の関係 □ 部分三体近似とテンソルツリー分解 □ 巡回二体近似とテンソルリング分解 テンソルツリー分解 テンソルリング分解 31
26. 応用例 : em-アルゴリズムとテンソル多体分解による欠損データ推定 33
27. 低ランク近似によるテンソルデータ補完 m-step 𝐏 ← 低ランク近似(𝐏) e-step 𝐏𝜏 ← 𝐓𝜏 𝜏 : 観測インデックス 低ランクテンソル補完 😢 低ランク空間はe-平坦ではない． m-射影が一意ではない． 🤔 どの低ランク構造で分解すべきか? 🤔 ランクをどのように選択すべきか? 低ランク空間 34 𝑒-射影 𝑚-射影
28. 多体近似によるテンソルデータ補完 m-step 𝐏 ← 低ランク近似(𝐏) e-step 𝐏𝜏 ← 𝐓𝜏 低ランクテンソル補完 𝑒-射影 Low-body many_body_approx 😄 相互作用の削減された空間はe-平坦. m-射影の一意性が保証される． 😄 直感的なモデル設計が可能！ 𝑚-射影 35 𝜏 : 観測インデックス 低Body空間 (e-flat)
29. 応用例：em-アルゴリズムによる欠損値推定の結果 欠損 正解 推定値 相関のあるモード間 の相互作用を使う Fit: 0.90 😄 36 欠損値を含む交通データ 28×24×12×4 の欠損値を観測値から推定 (days, hours, min, lanes)
30. 応用例：em-アルゴリズムによる欠損値推定の結果 欠損 正解 推定値 相関のあるモード間 の相互作用を使う Fit: 0.90 😄 37 欠損値を含む交通データ 28×24×12×4 の欠損値を観測値から推定 (days, hours, min, lanes) 相関のないモード間 の相互作用を使う Fit: 0.82 😢 😢 😢 ランクのチューニングが不要で，モデルの設計が容易な欠損値補完法
31. まとめ：相互作用で分解する非負テンソル分解を提案 ランクではなく https://arxiv.org/abs/2209.15338 ・提案手法ではランクのチューニングは不要 一体近似 三体近似 二体近似 テンソル多体分解 ・凸最適化で大域最適解が安定に求まる
32. 三体近似 二体近似 テンソル多体分解 バイアス (磁場) 重み (電子電子相互作用) 添字が二値だと二体分解は 全結合BMでの最尤推定と等価 （バイアス項は省略） 等価 ・提案手法ではランクのチューニングは不要 ・凸最適化で大域最適解が安定に求まる ・ボルツマンマシン(イジング模型)の多準位&高次の拡張によるテンソル分解 Accepted in NeurIPS 2023 🎉 https://arxiv.org/abs/2209.15338 まとめ：相互作用で分解する非負テンソル分解を提案 ランクではなく