Upgrade to Pro — share decks privately, control downloads, hide ads and more …

テンソル分解の基礎と応用(MIRU2022チュートリアル)

 テンソル分解の基礎と応用(MIRU2022チュートリアル)

2022.7.25 MIRU2022 チュートリアル講演「テンソル分解の基礎と応用」でのスライド資料になります。

Tatsuya Yokota

July 22, 2022
Tweet

More Decks by Tatsuya Yokota

Other Decks in Research

Transcript

  1. 4 情報処理:表現 + 計算 画像復元の例 損失を含む情報 表現:未完行列 計算:低ランクモデル 表現:点群 計算:ボロノイ図

    x y v 1 1 80 2 1 95 … … … 256 256 18 ◎ 多くの場合,表現の土台の上に計算がある ◎ 情報の「良い」表現とはなにか?
  2. 5 本講演で解説すること 情報をテンソル表現し,テンソル分解によって価値を生み出すアプローチ ⚫ テンソルとは ⚫ テンソル分解とは ⚫ テンソル分解のモデル ⚫

    テンソル分解のアルゴリズム ⚫ テンソル分解の応用事例 ⚫ テンソル分解技術への期待・課題など 情報 価値 テンソル表現 テンソル分解 テンソル情報処理
  3. 6 添え字のついた数 スカラー,ベクトル,行列を一般化したもの ⚫ 例: ⚫ 添え字の数を「階数(order)」と呼ぶ ➢ スカラー :

    0階テンソル(0th order tensor) ➢ ベクトル : 1階テンソル(1st order tensor) ➢ 行列 : 2階テンソル(2nd order tensor) ➢ … テンソルとは
  4. 7 多次元配列 ⚫ 0階テンソル : ⚫ 1階テンソル : ⚫ 2階テンソル

    : ⚫ 3階テンソル : テンソルデータ ベクトル → スカラーの配列 行列 → ベクトルの配列 3階テンソル → 行列の配列
  5. 8 3階テンソルを立方体で図示します 4階テンソル ⚫ ベクトルの3階テンソル ⚫ 行列の行列 ⚫ 3階テンソルのベクトル 5階テンソル

    ⚫ ベクトルの4階テンソル ⚫ 行列の3階テンソル ⚫ 3階テンソルの行列 ⚫ 4階テンソルのベクトル N階テンソル ⚫ N-1階テンソルのベクトル N階テンソル ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・ ・・・ ・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・ ・・・ ・・・ ・ ・ ・ ブロック行列 ブロック行列 ブロックベクトル ブロックベクトル
  6. 9 濃淡画像 ⚫ 2階テンソル テンソルデータの例 カラー画像(RGB) ⚫ 3階テンソル 高さ 幅

    (R,G,B) 高さ 幅 空間(横向き) 周波数(横向き) 空 間 ( 縦 向 き ) 周 波 数 ( 縦 向 き ) 高さ 幅 色 時間 にんじ ん じゃが いも たまね ぎ にく Aさん 購入 Bさん 購入 購入 Cさん 購入 Dさん 購入 顧客 商品 Aさん Bさん Cさん Dさん Aさん フォロー フォロー フォロー Bさん フォロー Cさん フォロー Dさん ブロック ユ ー ザ ー ( す る 側 ) ユーザー(される側) 主語 述語 目的語 カラー動画像 ⚫ 4階テンソル 購買記録 ⚫ 2階テンソル(+時間) 2D離散コサイン基底 ⚫ 4階テンソル ソーシャルネット ⚫ 2階テンソル(+時間) 知識ベース ⚫ 3階テンソル(+時間) ➢ (主語,述語,目的語)
  7. 10 深層学習に現れるテンソル TensorFlow ⚫ 名前に現れる , height width channels height

    width channels , , conv layer 幅 高さ バッチサイズ (R,G,B) ミニバッチ(中間層の表現) ⚫ 4階テンソル ➢ 幅 ➢ 高さ ➢ チャネル(RGBなど) ➢ バッチサイズ 畳み込み層の重み ⚫ 4階テンソル ➢ 畳み込みカーネルの幅 ➢ 畳み込みカーネルの高さ ➢ チャネル ➢ フィルタ数
  8. 13 テンソルの抽象的な表記法の1つ テンソルダイアグラム ベクトル 行列 3階テンソル 4階テンソル 5階テンソル ・ ・

    ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・ ・・・ ・・・ ロジャー・ペンローズ 枝 足 ボンド モード
  9. 14 内積 (全モードの縮約) 外積 (モードを並べるのみ) 内積・外積・行列積・テンソル積など * * * *

    … * sum = = 行列積(特定のモードペアの縮約) テンソル積(特定のモードペアの縮約) = R I J I J = = R I J I J =
  10. 15 テンソルを複数のテンソルの積(縮約)で表現する数理モデル ⚫ 行列を表現する場合 ➔ 行列分解 ⚫ テンソルを表現する場合 ➔ テンソル分解

    さまざまな分解モデル テンソル分解 f( , , ) = QR分解 特異値分解 ランク1分解 CP分解 Tucker分解 TT分解
  11. 16 テンソル分解はどんなことに使えるか データ分析のための特徴抽出 ⚫ テンソル分解によって「因子行列」を得ることが目的 ⚫ 因子行列を観察・分析することで,データに対して説明・解釈を与えたい ⚫ 得られる分解(因子行列)が一意となることが望まれる ➢

    脳波解析(アルファ波が強い,運動野が活発,領域AとBに強い相関がある) ➢ バイオインフォマティクス(遺伝子,症例,ワクチン,タンパク質の関係などを分析) ➢ 独立成分分析/音源分離(バンド演奏 ➔ ボーカル,ギター,ベース,ドラム) 圧縮表現による軽量化,高速化 ⚫ テンソルをできるだけ少ないパラメータ数の表現へエンコードして保存する ⚫ 必要な時にはテンソル積によってデコードする ⚫ 分解は一意でなくて良い ➢ 画像圧縮(JPEG圧縮はTucker2分解と関係がある),動画像圧縮 ➢ ディープニューラルネットワークの重みパラメータを圧縮 劣化したデータの復元(逆問題) ⚫ ノイズ・外れ値・欠損値・ボケなどによる劣化(観測モデル)を仮定する ⚫ テンソル分解(低ランク性に基づく事前情報)を用いて原信号を復元する ⚫ 分解は一意でなくて良い ➢ ノイズ除去,外れ値除去(脳波,音声,自然画像,医用画像,ハイパースペクトル画像) ➢ テンソル補完(画像,推薦システム,交通データ,無線通信など)
  12. 17 テンソル分解の応用分野 情報処理の幅広い分野において行列・テンソル分解が扱われています ⚫ マルチメディア(音声,自然言語,画像,3D画像,ビデオ) ⚫ 生体データ(脳波,PET,MRI,機能的MRI,拡散テンソル画像) ⚫ バイオインフォマティクス ➢

    Unsupervised Feature Extraction Applied to Bioinformatics: A PCA based and TD based approach [Taguchi, 2019] ➢ 行列・テンソル分解によるヘテロバイオデータ統合解析の数理 第{1,2,3}回 [露崎, 2021-2022] ⚫ ネットワークデータ分析(無線通信,交通,ソーシャルネットワーク,文献,Web) ➢ Accurate Recovery of Internet Traffic Data: A Tensor Completion Approach [Xie+, 2016] ➢ HaTen2: Billion-scale Tensor Decomposition [Jeon+, 2015] ⚫ など… ID 001 ID 002 ID 003 ID 004
  13. 18 テンソル分解のパイオニアと重要な文献 Koldaのレビュー論文 Tensor Decompositions and Applications Kolda&Bader, SIAM Review,

    2009 [pdf] 講演 [youtube] Cichockiらのレビュー論文 Tensor Decompositions for Signal Processing Applications Cichocki+, IEEE SPM, 2015 [pdf] T. G. Kolda (MathSci.ai) Signal Processing Society Magazine Best Paper Award (ICASSPにて) A. Cichocki (Skoltech) L. De Lathauwer (KULeuven)
  14. 19 テンソル分解のパイオニアと重要な文献 Sidiropoulosらのレビュー論文 Tensor Decomposition for Signal Processing and Machine

    Learning Sidiropoulos+, IEEE TSP, 2017 [pdf] Cichockiらの書籍 Tensor Networks for Dimensionality Reduction and Large-Scale Optimization: Part 1 [link] , Part 2 [pdf] Cichocki+, Foundations and Trends in Machine Learning, 2016 [link] N. Sidiropoulos (Univ. of Virginia)
  15. 20 宣伝 Book chapterを書きました Tensors for Data Processing, Elsevier, 2021

    [link] 目次 1章 Tensor decompositions: Computations, applications, and challenges 2章 Transform-based tensor SVD in multidimensional image recovery 3章 Partensor 4章 A Riemannian approach to low-rank tensor learning 5章 Generalized thresholding for low-rank tensor recovery 6章 Tensor principal component analysis 7章 Tensors for deep learning theory 8章 Tensor network algorithms for image classification 9章 High-performance TD for compressing and accelerating DNN 10章 Coupled tensor decomposition for data fusion 11章 Tensor methods for low-level vision T. Yokota, CF. Caiafa, and Q. Zhao テンソル分解を用いた画像復元法についてまとめました 12章 Tensors for neuroimaging 13章 Tensor representation for remote sensing images 14章 Structured TT decomposition for speeding up kernel learning Qibin Zhao (RIKEN AIP) Cesar F. Caiafa (CONICET)
  16. 36 CPランクの不思議 Subtracting a best rank-1 approximation may increase tensor

    rank ⚫ Stegeman&Comon, Linear Algebra and its Applications, 433(7): 1276-1300, 2010. ⚫ 最良ランク1近似をして差分を取るとき,当然誤差は小さくなるが,必ずしもCPランクは縮退しない ⚫ 行列の場合は(エッカート・ヤングの定理より)切り捨て特異値分解との差分となるため必ず縮退する 最良ランク1近似 ⚫ ほぼ全ての実数テンソルにおいて最良ランク1近似は一意 ➢ 定理2, Friedland&Ottaviani, The Number of Singular Vector Tuples and Uniqueness of Best Rank- One Approximation of Tensors, Foundations of Computational Mathematics, 14:1209-1242, 2014. 最良ランク1近似 ランク3になってしまう ◦ = ー ランク2のテンソル > ◦ ー が最も小さくなるような ◦ のこと
  17. 38 CP分解 R個のランク1テンソルの和に分解 ⚫ 1927年Hitchcookが「Polyadic form」という呼び方で提案 ⚫ 1970年Carroll&Changが「CANDECOMP (canonical decomposition)」として提案

    ⚫ 1970年Harchmanが「PARAFAC (parallel factor) analysis」として提案 ⚫ 2000年Kiersが「CP(CANDECOMP/PARAFAC)」と呼び,CP分解が定着した ⚫ その後Hitchcookの業績として再発見され「CP=Canonical Polyadic」として再定義された + = + ◦ ◦ ◦ + …
  18. 39 CP分解の特徴 「ある条件下で分解が一意である」点がしばしば取り上げられる ⚫ まず,A+B+C=C+B+Aのような自明な任意性は排除して考える(置換行列 ) ⚫ 各ランク1テンソルの因子ベクトルのスケールの任意性も自明なので排除する ⚫ 以下の条件が成り立つときCP分解は一意である

    ➢ クラスカルの条件(Kruskal, 1977)と呼ばれる ➢ 大雑把に言うと,Rが小さくテンソルのサイズが大きければそのCP分解は一意になりやすい ⚫ 因子行列からデータを説明したい時(データ分析)に特に重要 + + ◦ ◦ ◦ + … ※クラスカルランク k個の列ベクトルを自由に 取ってきて,それが線形独立 になってるようなkの最大値
  19. 42 CP分解を用いたデータ分析の具体例 Higher-order web link analysis using multilinear algebra ⚫

    Kolda+, International Conference on Data Mining (ICDM), 2005. [link] ⚫ 情報検索に用いられるページランキング手法にテンソル分解を導入した ➢ 従来は注目部分グラフを行列表現し特異値分解を行っていた クエリ 注目部分グラフ テンソル表現 CP分解 因子行列からページ ランキングを作成 ページランキング処理の流れ
  20. 49 遅延埋め込み空間におけるタッカー分解を用いた画像補間(インペインティング) ⚫ Yokota+, IEEE Conference on Computer Vision and

    Pattern Recognition (CVPR), 2018. [pdf] ⚫ Yamamoto+, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021. [pdf] ⚫ 欠損画像➔遅延埋め込み変換➔低ランクテンソル補完➔逆変換 Tucker分解を用いた画像復元の具体例 信号空間 遅延埋め込み空間 高階低ランクテンソル 結果 欠損画像 原画像 埋め込み 逆変換 Tucker分解
  21. 54 TT分解を用いたパターン認識の例 Supervised Learning with Tensor Networks ⚫ Stoudenmire&Schwab, Advanced

    in Neural Information Processing Systems (NeurIPS), 2016 [pdf] ⚫ パターン認識では画像の非線形な埋め込みに対して線形識別する仕組みが良く用いられてきたがこの線形識別の ところをテンソルネットワークによって記述するアプローチが提案されている ⚫ MNIST識別タスクで99.03%の精度を達成した。 パターンxをランク1 テンソルへ埋め込む one-hot 表現 スイープ処理によって 重み係数を最適化する
  22. 55 その他のテンソルネットワークモデル = 階層Tucker (HT)分解 Projected Entangled-Pair States (PEPS) テンソルリング(TR)分解

    [Zhao+, 2016] Multi-scale Entanglement Renormalization Ansatz (MERA) 全結合テンソルネットワーク(FCTN)[Zheng+, 2021] =
  23. 59 さまざまなRにおける再構成結果 行列分解 vs テンソル分解の実験 CP Tucker SVD R=1 R=10

    R=100 R=200 R=400 R=800 R=1600 R=(1,1,1) R=1 R=5 R=10 R=20 R=40 R=70 R=100 R=(10,10,10) R=(30,30,30) R=(40,40,40) R=(50,50,50) R=(80,80,80) R=(120,120,120)
  24. 61 その他,テンソル分解に基づく次元削減法 テンソルのスパース符号化 [Caiafa+, 2013 (in NECO)] [Caiafa+, 2013 (in

    WIRES)] テンソルネットワークに基づく次元削減 [Zhao+, 2016] [Cichocki+, 2017] 遺伝的アルゴリズムによるテンソルネットワークのモデル選択 [Li+, 2020 (in ICML)]
  25. 64 信号復元の事例 低ランクテンソル補完 ⚫ 劣化信号(画像)を直接3階テンソルとして表現 (Height * Width * RGB)

    ⚫ 平滑CP分解 [Yokota+, 2016 (in IEEE-TSP)] = ・・・ height width rgb height width rgb 整合性最大化 + + ◦ ◦ ◦ ・・・ + + + + = ランク1平滑テンソルの和によって表現
  26. 65 信号復元の事例 非局所フィルタによるノイズ除去 ⚫ BM3D [Dabov+, 2007 (in IEEE-TIP)] ⚫

    GSR [Zhang+, 2014 (in IEEE-TIP)] ⚫ Truncated HOSVD [Yokota+, 2017 (in IEEE-TSP)] http://www.cs.tut.fi/~foi/GCF-BM3D/ ①類似パッチを抽出してテンソル表現 ② 切り捨てHOSVDによってノイズ除去
  27. 66 その他,テンソル分解に基づく信号復元法 低ランクテンソル信号復元 ⚫ Low-n-rank tensor recovery [Gandy+, 2011 (in

    Iverse Problems)] ⚫ Low rank tensor completion [Liu+, 2012 (in IEEE-TPAMI)] ⚫ Bayesian CP decomposition [Zhao+, 2015 (in IEEE-TPAMI)] ⚫ t-SVD [Zhang+, 2017 (in IEEE-TSP)] ⚫ Low-rank and smooth tensor recovery [Yokota+, 2017 (in CVPR)] [Yokota+, 2019 (in IEEE-Access)] ⚫ Tensor ring completion [Wang+, 2017 (in ICCV)]
  28. 69 深層ニューラルネットにおける重み係数のテンソル表現と分解 ⚫ 畳み込み層 [Lebedev+, 2015 (in ICLR)] ⚫ 全結合層

    [Novikov+, 2015 (in NeurIPS)] 深層ニューラルネット (DNNs) , , , 折り畳み/テンソル化 = = TT 分解 CP 分解 ◦ ◦ ◦
  29. 70 テンソル分解と深層学習 ⚫ 畳み込み層 [Lebedev+, 2015 (in ICLR)] ➢ Full

    convolution (4階テンソル) をCP分解によって近似 ➢ ファイバーの逐次的な畳み込みへ分離できる ➢ 画像認識タスク(ILSVRC) :少しの精度低下で大幅なスピードアップに成功した 深層ニューラルネット (DNNs) , , , CP decomposition ◦ ◦ ◦ (9,9,48,128) CPランク
  30. 71 テンソル分解と深層学習 ⚫ 全結合(FC)層 [Novikov+, 2015 (in NeurIPS)] ➢ 実験:

    1000クラス画像分類タスク(ImageNet)におけるVGG16,VGG19を圧縮 ➢ 3つの全結合層 深層ニューラルネット (DNNs) = = TT分解 FC1 (25088, 4096) FC2 (4096, 4096) FC3 (4096, 1000) 25088 = 2*7*8*8*7*4 4096 = 4*4*4*4*4*4 何もしない場合 ➔ TT分解 TTランク ➔ 1, 2, or 4 行列分解 行列ランク ➔ 1, 5, or 50 少しの精度低下で大幅な パラメータ圧縮に成功
  31. 72 深層ニューラルネット (DNNs) その他の文献 ⚫ Compression of CNN with Tucker

    [Kim+, 2016 (in ICLR)] ⚫ Supervised Learning with Tensor Networks [Stoudenmire+, 2016 (in NeurIPS)] ⚫ Exponential Machines [Nivikov+, 2017 (in ICLR workshop)] ⚫ Compact RNNs with Block-term Tensor Decomposition [Ye+, 2018 (in CVPR)] ⚫ Compressing RNNs with Tensor Ring [Pan+, 2019 (in AAAI)] ⚫ Tensor network decomposition of CNN kernels [Hayashi+, 2019 (in NeurIPS)] ⚫ For understanding DNNs [Li+, 2019 (in ICASSP)] [Li+, 2020 (in AISTATS)]
  32. 73 まとめと重要な議論 情報をテンソル表現しテンソル分解する方法論とその応用事例について紹介 テンソルの低ランク近似によって,特徴抽出,次元圧縮,信号復元などに応用できる ⚫ データの説明・解釈などを目的とした特徴抽出(分析)では分解の一意性が求められる ➢ CP分解が好まれる,また非負制約,スパース制約,統計的独立性などを課すことで解釈性を改善できる(NMFなど) ⚫ 圧縮では,分解時のパラメータ数が少ないことが求められる

    ➢ 圧縮性の高さから,テンソルネットワーク分解の発展が期待される ⚫ 復元では,再構成された低ランク近似そのものが得られれば良い ➢ 復元対象の性質(Prior),ノイズの性質,劣化モデルの性質などに合わせて多種多様なモデリングと最適化の技術が必要とされる テンソル分解技術の要点 ⚫ 情報をどのようにテンソル表現するか?(テンソル化の方法はさまざま) ⚫ 分解のランク決定をどうするか? ⚫ テンソル分解を高速化するためには? ID 001 ID 002 ID 003 ID 004 = + + ◦ ◦ ◦
  33. 74 良いテンソル表現とは? さまざまなテンソル化(折り畳み)の方法が考えられている 変換による高階テンソル化 ⚫ 類似パッチ抽出によるテンソル構築 [Dabov+, 2007 (in IEEE-TIP)]

    ⚫ 短時間フーリエ変換,ウェーブレット変換 [Tao+, 2007 (in TPAMI)] ⚫ 遅延埋め込み変換(ハンケル行列化) [Yokota+, 2018 (in CVPR)] (256,256) (2,2,2,2,2,2,2,2) (2,2,2,2,2,2,2,2) 16階テンソル Folding (4,4,4,4,4,4,4,4) Ket augmentation (KA) 8階テンソル
  34. 75 モデル選択と高速最適化 モデル選択 ⚫ 様々なテンソル分解モデルが提案されていて,何を使えば良いのか分からない ⚫ これはデータの特性とモデルの特性両方に精通している熟練者でないと難しい ⚫ テンソルネットワークの探索的モデル選択の手法が提案されている ➢

    Evolutionary Topology Search for Tensor Networks [Li+, 2020 (in ICML)] ⚫ また,テンソル分解のランク決定も重要なモデル選択問題の1つである ➢ スパース化 [Yokota, 2014],情報量基準 [Yokota+, 2017],ベイズ推論 [Takayama+, 2022] 高速最適化 ⚫ テンソルが大規模な時など,省メモリかつ高速にテンソル分解を求めるアルゴリズムが求められる ➢ 勾配法,ニュートン法,交互最小二乗法,階層的ALS,確率的勾配法,MMアルゴリズム,主双対分離… ⚫ ランダムサンプリング(射影)を用いた高速化も盛んに研究されている ➢ Randomized SVD [Minster+, 2020] [Ahmadi-Asl+, 2020] ➢ TensorSketch [Malik+, 2018 (in NeurIPS)] ➢ GPU acceleration [Choi+, 2018] ⚫ スーパーコンピュータなど分散処理が有効活用できる方法論の研究も重要である ⚫ 一意性のない分解モデルでは,多様体上の最適化など解空間を限定することで収束を早くできる
  35. 76 テンソル分解・テンソルネットワークのこれから 大規模データの圧縮・分散・高速処理 ⚫ テンソル表現 ➔ テンソルネットワーク表現 ⚫ テンソルネットワーク型に基づく情報処理の方法論構築と応用模索 ⚫

    テンソルネットワークの研究が盛んな物理分野との学際交流 ⚫ 量子計算,GPU計算,自動微分などとの技術的な融合 大規模 データ 価値 テンソルネットワークの進展 数理科学 2022年2月号
  36. 77 謝辞 Andrzej Cichocki (Skoltech) Qibin Zhao (RIKEN AIP) Chao

    Li (RIKEN AIP) Cesar F. Caiafa (CONICET) Hidekata Hontani (Nitech)
  37. 79 スカラー ⚫ 小文字 / 大文字 : ベクトル ⚫ 小文字ボールド

    : 行列 ⚫ 大文字ボールド : 高階テンソル (3rd, 4th, …, Nth ) ⚫ カリグラフの大文字ボールド : 数式での表記