テンソル分解の基礎（2014.3.13）

「テンソルデータ解析の基礎と応用」（コロナ社）の出版記念ということで10年前（D卒直前）の若気の至りスライドをアップします！
https://www.coronasha.co.jp/np/isbn/9784339014075/

Transcript

1. テンソル分解の基礎と 画像・信号処理への応用 横田 達也 2014年3月 13日 1
2. 高校時代 ～魚ロボット～ 大学時代 情報工学科 (計算機システム・プログラミングなど) 大学院 機械学習（パターン認識・データ解析）を研究 卒業後 → 理研の研究員 学歴 研究 2005年3月 東京工業大学工学部附属 工業高等学校機械科卒業 ↓ 特別推薦で合格 (10/200) 2009年3月 東京工業大学 卒業 杉山研究室 2011年3月 東京工業大学大学院 修士課程修了 山下研究室 2011年4月 ~現在 東京工業大学大学院 博士後期課程在学 大学:山下研 理研:チホツキ研 2 自己紹介
3. テンソルについて テンソルとは テンソルの計算則 テンソル分解のモデル CPモデル Tuckerモデル テンソル分解のアルゴリズム テンソル分解へのいろいろな拡張の研究 テンソル分解の応用技術の紹介 3 目次
4. 添え字のついた変数(配列) スカラー、ベクトル、行列の一般名 例 添え字の数：階数 スカラー：０階のテンソル ベクトル：１階のテンソル 行列 ：２階のテンソル ・・・ 4 テンソルとは？
5. 多次元配列としてイメージしてみる ０階テンソル： １階テンソル： ２階テンソル： ３階テンソル： 5 テンソルデータ ベクトル -スカラーを並べたもの 行列 -ベクトルを並べたもの -行列を並べたもの
6. ３階のテンソルを直方体で表す ４階のテンソルは、 ３階のテンソルを並べたものなので、➔ ５階のテンソルは、 ４階のテンソルを並べたものなので、➔ n階のテンソルは、 (n-1)階のテンソルを並べたもの。 6 高階のテンソル ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・ ・・・ ・・・
7. 7 テンソルデータの例 時系列データ ➔ １階のテンソル (ベクトル) 多チャンネルの時系列データ ➔ ２階のテンソル (行列) 濃淡画像 カラー画像 ➔ ２階のテンソル (行列) ➔ ３階のテンソル (RGB×濃淡画像) カラー動画 ➔ ４階のテンソル (フレーム×カラー画像)
8. N階のテンソルを で表し、 その 成分を または で表す。 足し算(引き算) 同じ大きさの二つのテンソルの和は、 定数cに対するテンソルXの定数倍 cX は、 8 テンソルの計算(1)
9. アダマール積(Hadamard product) 同じ大きさの二つのテンソルのアダマール積は、 成分ごとの商(elementwise division) 同じ大きさの二つのテンソルの成分ごとの商は、 クロネッカー積(Kronecker product) 9 テンソルの計算(2)
10. 内積とノルム 同じ大きさの二つのテンソルの内積は、 X = Y のとき、フロベニウスノルムになる 10 テンソルの計算(3)
11. テンソルの展開(Unforlding) ベクトル化(vectorization) 11 テンソルの計算(4)
12. n方向の行列化(n-way matricization) 12 テンソルの計算(5) -行列化の手順- ① テンソルをn方向へ スライスする。 (In 個のスライス) ② 各スライスを行ベク トルへ展開する。 (In 個のベクトル) ③ 各行ベクトルを上から 下に縦に並べる。
13. 行列と行列の積 (I×J)行列 ・(J×K)行列 = (I×K)行列 テンソルと行列の積 (I×J×K)テンソル ×1 (L×I)行列 = (L×J×K)テンソル (I×J×K)テンソル ×2 (L×J)行列 = (I×L×K)テンソル (I×J×K)テンソル ×3 (L×K)行列 = (I×J×L)テンソル 13 テンソルの計算(6) = ・ I J J K K I I J K ×1 I L = L J K I L I = JK L JK 行列化 行列化 ・
14. 3階テンソルと3つの行列との積 14 テンソルの計算(7) I J K ×1 L = L M N ×2 M ×3 N I J K I L I = JK L MN ・ ・ MN JK 行列化で表記すると = IJK LMN ・ ベクトル化で表記すると IJK LMN
15. いろいろなテンソル同士の積 外積 (s階テンソルとt階テンソルでs+t階テンソルになる) 15 テンソルの計算(8) I J K L J K I L = JK L JK I I L =
16. テンソルの概念について紹介 テンソルの計算 足し算(引き算) 定数倍 アダマール積 成分ごとの商 クロネッカー積 内積、ノルム 展開：ベクトル化 展開：行列化 テンソルと行列の積 テンソル同士の積 外積 16 途中まとめ
17. 行列の因子分解、特徴抽出 テンソルの因子分解と次元削減 行列分解をテンソルに拡張したもの 17 テンソル分解 ベクトルベースのデータ解析 ・・・ ➔ 主成分分析 (PCA) 独立成分分析(ICA) スパース成分分析 (SCA) 非負行列分解 (NMF) W ・・・
18. 18 テンソルデータの解析 MRI画像 脳波(時間・周波数) 3階テンソルの特徴抽出 A C BT ➔ 高階テンソルデータ CPモデル Tuckerモデル gr ar cr br G A C BT テンソル分解
19. 全部同じモデルを指す CP: canonical polyadic decomposition PARAFAC: pararell factor analysis CANDECOMP: canonical decomposition ここでは、CPモデルとよびます。 1ランクテンソル N個のベクトルの外積で表せるN階テンソル CPモデル(3階テンソル) Rランクへの近似モデルになっている 19 CPモデル
20. CPモデル(3階テンソル) カトリ・ラオ積 20 CPモデルの行列化 CPモデル 行列化された CPモデル
21. 評価基準 a,b,c のノルムは一意に決まらない 任意の実数dに対して, a a/d, bb*d としてもよい a,b,c のノルムを正規化 21 CP分解のための評価基準 特異値の テンソル版
22. 問題 導出 (λ,B,Cを固定して, Aについて解く) 最小化条件 更新式 22 CP分解のアルゴリズムの導出 この目的関数を 関数L とおく ➔
23. 入力: X, R 初期化：B, C (各列のノルムは1) 収束するまで繰り返し (r=1,…,R) (r=1,…,R) (r=1,…,R) (r=1,…,R) 出力: A, B, C, Λ 23 CP分解のアルゴリズムまとめ
24. Tucker3モデル(3階テンソル) Gが対角の時、Tuckerモデル＝CPモデル 24 Tuckerモデル =
25. Tuckerモデルの行列化(3階テンソル) Tuckerモデルのベクトル化 25 Tuckerモデルの展開 I R1 I = JK R2R3 JK A R1 R2R3 (C × B) 〇 T G(1) [Tuck](1) (C × B × A) 〇 〇 = IJK IJK R1R2R3 R1R2R3 ・
26. 評価基準 G,A,B,C は一意に決まらない A, B, C に正規直交制約を加える(これでも一意にはならない…) 目的関数Lについて見ていく 26 Tucker分解のための評価基準 この目的関数を 関数L とおく ➔
27. 目的関数LにGを代入する 目的関数の最小化は、 G のノルムの最大化となる(PCAと同じ) 27 Tucker分解のための評価基準(2)
28. 問題 導出 (λ,B,Cを固定して, Aについて解く) 更新則 28 Tucker分解のアルゴリズムの導出 または
29. 入力: X, R1, R2 , R3 初期化ステップ Repeat(収束まで) End 出力: G, A, B, C 29 Tucker分解のアルゴリズムまとめ HOSVD HOOI
30. 一般的な評価基準 モデル ＋ 制約 という組み合わせから、いくつもの手法とアルゴリズ ムが提案されている。 制約項 最適化アルゴリズム 30 制約付きのCP・Tucker分解 与えられたテンソルデータ モデル(CP・Tucker) 制約 ・直交制約 ・スパース制約 ・スムース制約 ・非負制約
31. 解の一意性の向上 目的にあった特徴を抽出したい 例: Textデータ(ヒストグラム)、確率密度関数は必ず非負であり、 それらを構成する基底(特徴)ベクトルもまた非負であるはず。 例: 物理的要因でスパース性、スムース性を仮定して良い場合、( スムースな自然画像、一般に疎なスペクトルなど) 例: それぞれが独立な特徴ベクトルを抽出したい ノイズや、無駄な因子をできるだけ取り除きたい 制約によっては、ノイズに対する頑健性を向上できる 31 なぜ、制約が必要なのか？ 解の領域 解の領域 制約
32. 特徴ベクトルをそれぞれが直交するベクトルの組に限定 ☺線形独立性が保障される ☺特徴ベクトルのノルムが正規化される 他の制約(疎、非負など)との親和性が低い 適用例：SVD、PCA、ICA、HOSVDなど 32 直交制約
33. スパースとは、 ベクトルの成分のほとんどの値が 0 のような状態をいう 例: a = [0 0 0 0 5 0 0 0 -1 4 0 0 0 0 0 0 -9 0 0 0 0] スパース性を得るための制約 l1-ノルムの最小化が良く用いられる l1-ノルム 評価基準: LASSO と呼ばれる 二次の目的関数＋L1ノルムの最小化 λ:正則化パラメータ 弱い成分をつぶして、主要な成分のみを残す 33 スパース制約 l1ノルムの等高線 目的関数の等高線
34. スムース性 ベクトルの隣り合う成分の値の差が小さい 例: a = [0 -3 9 0 5 15 0 0 0 0 1 1 0 -1 -1 1 2] 良く用いられる評価基準(fused lasso, total variation) 他にも、Aをスムースな基底関数の線形結合としてモデル 化する方法が提案されている A=ΦW ノイズに対する頑健性が得られる 34 スムース制約 スムースでない スムース
35. 非負制約とは、 特徴ベクトルの成分の値がすべて非負という制約 非負制約は、特徴ベクトルの非負性だけではあまり意味がなく、 係数の非負性があってはじめて効果を発揮する。 なぜなら非負制約は和算のみでモデル化するための制約だから 和算のみの制約によって相殺が不可能となるため、構成要素としての パーツを抽出することができる。 35 非負制約 ➔ ➔ + + + + + + + ➔ + + ➔ ➔ + - - ➔ +
36. スパース・スムース・非負制約などを付加したさまざまな 拡張が提案されている。 スパースCP分解[Allen, 2012] スパースTucker分解 非負CP分解 非負Tucker分解[Kim&Choi, 2007][Phan&Cichoki, 2008,2009,2011] スムース非負CP分解[Yokota et al, 2015] スムース非負Tucker分解[Tokota et al, 2015] 行列分解の多様な技術をテンソル分解に拡張したい 主成分分析(PCA)、スパースPCA、スパース＆スムースPCA 非負行列分解(NMF)、スパースNMF、スムースNMF 独立成分分析(ICA) 共通個別因子分析など 36 CP・Tucker分解のさまざまな拡張
37. 複数の濃淡画像を重ねた3階のテンソルデータ 特徴行列=基底行列であり、コアテンソルはその係数と考えて良い 。 37 テンソル分解の画像処理への応用 A BT タッカー分解 Tucker2モデル 特徴行列 特徴行列 コアテンソル = + + + + ・・・ = + + + + ・・・
38. 38 Tucker2モデルで得られた直交基底
39. 39 二次元DCT と Tucker2分解 の違い A BT Tucker2モデル 基底行列 基底行列 コアテンソル C1 C2 T コサイン 関数行列 コサイン 関数行列 コアテンソル DCT 基底行列が決まっていて、 コアテンソルだけを最適化して フィッティングしている 基底行列と コアテンソル両方最適化する フィッティングする DCT基底 Tucker2 基底
40. もし、NMF/NTFによって顔画像のパーツが的確に学習さ れていれば、パーツの組み合わせによって顔画像を構成で きる。 ノイズを付加された顔画像を、構成モデルで再構成する事を考え る。再構成された画像は基底行列が張る空間に限定されるため、 ノイズ除去に利用できる。 張る空間の次元が小さいとまったく別の(平均的な)顔になる… 40 非負テンソル分解による顔画像の再構成 ノイズ付加 NMF Smooth NMF NTF Smooth NTF
41. PSNR(peak signal to noise ratio) 41 再構成誤差の評価 11枚 33 pixels 26 pixels G A C BT ・・・ 15人 ・・・ ・・・ ・・・ ・・・ 11枚 858 pixels R1×10×10 ・画像にはノイズ(10dB)が付加されている ・R1個のパーツで各顔画像を再構成する ・再構成した画像とノイズのない原画像をPSNRで比較
42. 42 応用例2: 3階テンソルデータのノイズ除去 7.21 dB 非負CP分解 (19.8 dB) 非負Tucker分解 (13.5 dB) スムース非負 CP分解(26.8 dB) スムース非負Tu- cker分解(23.9 dB) Gaussian noise G A C B T G U W VT T 非負Tucker分解 非負CP分解 スムース非負Tucker分解 スムース非負CP分解
43. テンソルの概念とさまざまな計算則を紹介 2つのテンソル分解モデルを紹介 CPモデル Tuckerモデル 最も基本的な分解アルゴリズムを紹介 CP-ALS アルゴリズム HOOI アルゴリズム 制約付きテンソル分解について紹介 直交制約 スパース制約 スムース制約 非負制約 簡単な応用例を紹介 Tucker2モデルによる直交基底の学習 CP・Tucker分解によるノイズ除去 43 まとめ
44. 最後まで聞いてくださってありがとうございました。 44 おわり