低ランク行列推定

低ランクテンソル推定

References

Convergence rate of Bayesian tensor estimatorand its minimax optimality† ‡†鈴木大慈

東京工業大学大学院情報理工学研究科 数理・計算科学専攻‡JST さきがけ

2015 年 8 月 4 日
ERATO 感謝祭 SeasonII@一橋講堂

1 / 37

低ランク行列推定

低ランクテンソル推定

References

Taiji Suzuki: Convergence rate of Bayesian tensor estimator and its
minimax optimality. The 32nd International Conference on Machine
Learning (ICML2015), JMLR Workshop and Conference Proceedings
37:pp. 1273–1282, 2015.

2 / 37

低ランク行列推定

低ランクテンソル推定

References

Outline1

低ランク行列推定
問題設定
トレースノルム正則化

2

低ランクテンソル推定テンソルのランク凸正則化推定法
ベイズ推定法
数値実験

3 / 37低ランク行列推定

低ランクテンソル推定

References

本日のお題

低ランクテンソル推定→ ベイズ推定量の性質
緩い仮定での最適な収束レート(Õd(M1 + · · · + MK )n)4 / 37

低ランク行列推定

低ランクテンソル推定

References

例: 推薦システム

映画 A

映画 B

映画 C···

映画 X

ユーザ 1

48*···

2

ユーザ 2

2

*2···

*ユーザ 3

2

4*···

*..
.
(e.g., Srebro et al. (2005a), NetFlix (Bennett & Lanning, 2007))

5 / 37

低ランク行列推定

低ランクテンソル推定

References

例: 推薦システム
ランク 1 と仮定する
映画 A

映画 B

映画 C···

映画 X

ユーザ 1

484···

2

ユーザ 2

242···

1

ユーザ 3

2

42···

1..
.
(e.g., Srebro et al. (2005a), NetFlix (Bennett & Lanning, 2007))

5 / 37

低ランク行列推定

低ランクテンソル推定

References

例: 推薦システム
NMovieA*=MUserA∗ij =d∑

Uir Vjrr =1→ 低ランク行列補完:
低ランク行列の Rademacher Complexity: Srebro et al. (2005a).
Compressed sensing: Candès and Tao (2009); Candès and Recht(2009).
6 / 37

低ランク行列推定

低ランクテンソル推定

References

例: 縮小ランク回帰
縮小ランク回帰 (Anderson, 1951; Burket, 1964; Izenman, 1975)
マルチタスク学習 (Argyriou et al., 2008)
普通の回帰YnX

WA+=M

スパース推定では A がスパース (多くの成分が 0).
7 / 37

低ランク行列推定

低ランクテンソル推定

References例: 縮小ランク回帰
縮小ランク回帰 (Anderson, 1951; Burket, 1964; Izenman, 1975)
マルチタスク学習 (Argyriou et al., 2008)
縮小ランク回帰XY

A*=nNW+M

N(A*=MN)

A∗ は 低ランク
7 / 37

低ランク行列推定

低ランクテンソル推定

References

高次元データでの問題意識
協調フィルタリング
コンピュータビジョン
音声認識
ゲノムデータ金融データ
次元 d = 10000 の時，サンプルサイズ n = 1000 で推定ができるか？
どのような条件があれば推定が可能か？
何らかの低次元性を利用．

8 / 37

低ランク行列推定

低ランクテンソル推定

References

高次元データでの問題意識
協調フィルタリング
コンピュータビジョン
音声認識
ゲノムデータ金融データ
次元 d = 10000 の時，サンプルサイズ n = 1000 で推定ができるか？
どのような条件があれば推定が可能か？
何らかの低次元性を利用．
→ 今日は低ランク性を扱う．

8 / 37

低ランク行列推定

低ランクテンソル推定References

Outline1低ランク行列推定
問題設定
トレースノルム正則化

2低ランクテンソル推定テンソルのランク凸正則化推定法
ベイズ推定法
数値実験

9 / 37

低ランク行列推定

低ランクテンソル推定

References

問題設定

低ランク行列推定
低ランク行列推定の基本形

Yi = ⟨Xi , A∗ ⟩ + Wi
A∗ , Xi ∈ RM×N : 行列,⟨Xi , A∗ ⟩ := Tr[Xi⊤ A∗ ]2Wi ∼ N (0, σ ): 観測ノイズ
観測量: {(X1 , Y1 ), . . . , (Xn , Yn )}推定したいもの: A∗

10 / 37

低ランク行列推定

低ランクテンソル推定

References

問題設定

低ランク行列推定
低ランク行列推定の基本形

Yi = ⟨Xi , A∗ ⟩ + Wi
A∗ , Xi ∈ RM×N : 行列,⟨Xi , A∗ ⟩ := Tr[Xi⊤ A∗ ]2Wi ∼ N (0, σ ): 観測ノイズ
観測量: {(X1 , Y1 ), . . . , (Xn , Yn )}推定したいもの: A∗

M × N ≫ n: 高次元データ (不良設定問題)→ A∗ は 低ランク であるとして推定する．
10 / 37

低ランク行列推定

低ランクテンソル推定

References

トレースノルム正則化

ランク正則化付きリスク最小化

正則化付き推定法の基本的な考え方:

1∑(Yi − ⟨Xi , A⟩)2 + Pen(rank(A)).
nnmin

A∈RM×N

i=1

しかし，rank 関数は行列 A に対して凸関数ではない．
ランク制約を満たす行列の集合は凸集合を成さない．
→

凸緩和 (トレースノルム正則化)

11 / 37

低ランク行列推定

低ランクテンソル推定

References

トレースノルム正則化

トレースノルム正則化
1∑(Yi − ⟨Xi , A⟩)2 + λ∥A∥tr ,A∈RM×N nnmini=1d∑√∥A∥tr := Tr( A⊤ A) =σi (A).
i=1

※トレースノルムは {A | ∥A∥sp ≤ 1} 上でランク関数の凸包絡.
これは，特異値への ℓ1 正則化．
→ 特異値がスパース = 低ランク.

(Srebro et al., 2005b; Argriou et al., 2008; Argyriou et al., 2008)
Lasso:n1∑
min(Yi − Xi⊤ β)2 + λ∥β∥ℓ1 .
β∈RM ni=112 / 37低ランク行列推定

低ランクテンソル推定

References

トレースノルム正則化

トレースノルム正則化の理論
真の行列 A∗ は M × N のランク d 行列.
ノイズあり:
スパース推定の一般論: Negahban et al. (2012).
行列補完, Spikiness 条件: Negahban and Wainwright (2012).
行列補完+マルチタスク学習: Rohde and Tsybakov (2011).
対称行列の行列補完: Koltchinskii (2012).

∥Â − A∗ ∥22 = Op
ただし，∥A∥2 :=√(d(M + N) log(MN)n).

1MN ∥A∥F .

基本的に観測デザインへの条件（制限強凸性）が必要．
13 / 37

低ランク行列推定

低ランクテンソル推定

References

Outline1

低ランク行列推定
問題設定
トレースノルム正則化

2

低ランクテンソル推定テンソルのランク凸正則化推定法
ベイズ推定法
数値実験

14 / 37

低ランク行列推定

低ランクテンソル推定

References

テンソルデータ

User

User

Context

Movie

行列−→Movie

テンソル (多次元アレイ)

15 / 37

低ランク行列推定

低ランクテンソル推定

References

Applications
推薦システム
関係データ
マルチタスク学習
時空間データ解析 (空間 (2D) × 時間)
動画像処理 (画像 (2D) × 時間)

16 / 37

低ランク行列推定低ランクテンソル推定

References

Applications
マルチタスク学習
reTask type 1featu

Tasktype2

推薦システム（テンソル補完）
利用場面

評価
44 2 33 4
141 2
1 2 1 42 2 4
商品
23 3 1 1
3 33 211 4 1
222
2
評価の予測 41311 322
ユーザー
17 / 37

低ランク行列推定

低ランクテンソル推定

References

問題設定: 回帰回帰の問題設定:

Yi = ⟨Xi , A∗ ⟩ + Wi .
1 ×...MKA∗ , Xi ∈ RM∑: テンソル.
∗⟨Xi , A ⟩ := j1 ,...,jK Xi,(j1 ,...,jK ) A∗j1 ,...,jK .
Wi ∼ N (0, σ 2 ): 観測ノイズ.

仮定: A∗ は “低ランク”.

18 / 37

低ランク行列推定

低ランクテンソル推定

References

問題設定: 回帰
回帰の問題設定:

Yi = ⟨Xi , A∗ ⟩ + Wi .
1 ×...MKA∗ , Xi ∈ RM∑: テンソル.
∗⟨Xi , A ⟩ := j1 ,...,jK Xi,(j1 ,...,jK ) A∗j1 ,...,jK .
Wi ∼ N (0, σ 2 ): 観測ノイズ.

仮定: A∗ は “低ランク”.

E.g., Xi = ej1 ⊗ ej2 ⊗ · · · ⊗ ejK でテンソル補完問題.
18 / 37

低ランク行列推定

低ランクテンソル推定

References

テンソルのランクテンソルのランク: CP-ランク

CP-分解 (Canonical Polyadic Decomp.)(Hitchcock, 1927; Hitchcock, 1927)(figure is from Kolda and Bader (2009))

Xijk =d∑air bjr ckr =: [[A, B, C ]].

r =1

CP-分解はテンソルの CP ランクを定義する．
CP-分解は NP-困難.
CP-ランクはテンソルの辺の長さより大きくなる可能性がある.
直交分解が存在するとは限らない (対称テンソルに限っても).
19 / 37

低ランク行列推定

低ランクテンソル推定

References

テンソルのランクテンソルのランク: Tucker-ランク

Tucker-分解 (Tucker, 1966)(figure is from Kolda and Bader (2009))∑r1 ∑r2∑r3

Xijk = l=1 m=1 n=1 glmn ail bjm ckn =: [[G ; A, B, C ]].
G はコアテンソルとよばれている.
Tucker-ランク = (r1 , r2 , r3 )r1 , r2 , r3 はテンソルの辺の長さより大きくはならない.
20 / 37

低ランク行列推定

低ランクテンソル推定

References

凸正則化推定法

凸最適化によるテンソル推定方法

凸最適化によるアプローチ:

1∑(Yi − ⟨Xi , A⟩)2 + pen(A).
M×M
×···×M
2K nA∈R 1nmini=1和型 Schatten-1 ノルム (Tomioka et al., 2011)
畳み込み型 Schatten-1 ノルム (Tomioka & Suzuki, 2013)

Square deal (Mu et al., 2014)

21 / 37

低ランク行列推定

低ランクテンソル推定

References

凸正則化推定法

和型 Schatten-1 ノルム|||A|||S1 /1 :=K∑∥A(k) ∥Tr

k=1

和型 Schatten-1 ノルム正則化
2Ab = arg min |||Y − A|||F + λn |||A|||S1 /1 .
ATucker-ランクが小さなテンソルを推定.

−→AA(1)A(2)A(3)
22 / 37

低ランク行列推定

低ランクテンソル推定

References

凸正則化推定法

畳み込み型 Schatten-1 ノルム|||A|||S1 /1 :=K∑

inf

A=A1 +A2 +···+AK(k)∥Ak ∥Tr

k=1

畳み込み型 Schatten1 ノルム正則化

Ab = arg min
A2|||Y − A|||F + λn |||A|||S1 /1 ,s.t. A =K∑(k ′ )Ak , ∥Ak ∥S∞ ≤k=1α√N/nk ′ (∀k ′ ̸= k).
K

ランクの小さな方向を見つける．

AA1=
↓

A2+
↓(1)

A1A3+
↓(2)

A2(3)

A323 / 37

低ランク行列推定

低ランクテンソル推定

References

凸正則化推定法

収束レート解析A∗ のモード k 展開のランクが rk であるとする: rk = rank(A∗N = M1 × · · · × MK .

(k)).

収束レート和型 (Tomioka et al., 2011)( ∑)2 ( ∑√√√ )2KK∗ 21C11bN/Mk )rkk=1 ( Mk +k=1N |||A − A |||F ≤ nKK
畳み込み型 (Tomioka & Suzuki, 2013)()2√√
1b − A∗ |||2 ≤ C maxk ( Mk + N/Mk ) mink rk
|||AN

Fn

Square deal (Mu et al.,∏2014):∗ 2
1M ∥Â − A ∥2 ≤ Cmin{k∈I1 rk ,n∏)(∏k∈I2 rk } ∏k∈I2 Mk ,k∈I1 Mk +where I1 and I2 are any disjoint decomposition of index set {1, . . . , K }.

これらは最適ではない.
ある種の強凸性の仮定が必要．

24 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法

ベイズ推定

ベイズ法で低ランクテンソル推定を行った時の統計的性質を調べる．
一般の回帰の設定で解析.
より少ない条件で最適レートを達成.

25 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法

事前分布
ランク d ′ と U (k) に事前分布 (データを見る前の確からしさ) を置く.

CP-ランクが d ′ のテンソル上の事前分布:
ランク d ′ なるテンソル A の分解′
A = [[U (1) , . . . , U (K ) ]] (U (k) ∈ Rd ×Mk ) と分解されるとして, 事前分布を次のように入れる：}{Kd′ ∑(k) ⊤ (k)(1)(K ) ′Tr[UU ] .
π(U , . . . , U |d ) ∝ exp − 22σpk=1

ランクの事前分布:π(d ′ ) ∝ ξ d′(∑π(d ′ ) = 1),d′

ただし 1 > ξ > 0 はある定数.

26 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法

事後分布
データ Dn = {(Xi , Yi )}ni=1 を観測した後の確からしさ．

π(A, d ′ |Dn )
|{z}
事後分布

[]
n1 ∑∝ exp − 2(Yi − ⟨Xi , A⟩)2 × π(A|d ′ )π(d ′ )2σi=1

尤度（データへの当てはまり）×事前分布

ベイズ推定量は Gibbs サンプリングで計算可能:′

条件付き事後分布 π(U (k) |{U (k ) }k ′ ̸=k , d ′ , Dn ) は正規分布.
条件付き事後分布からのサンプリングを k = 1, . . . , K とサイクリックに繰り返す．
ランク d ′ の事後確率は周辺尤度を Gibbs サンプリングを通して計算．
27 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法関連研究

確率テンソルの推定 (多項分布): Zhou et al. (2013)
離散カテゴリ，判別分析 (条件付き多項分布): Yang and Dunson(2013)
テンソル積空間上でのノンパラメトリック確率密度関数推定: Shenand Ghosal (2014)
低ランク行列のベイズ推定の収束レート (回帰): Alquier (2013)
テンソルのベイズモデルおよび計算方法: Xiong et al. (2010); Xuet al. (2013); Rai et al. (2014)28 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法用語の準備A∗ の max-norm:∥A∗ ∥max,2 := min {max ∥U:,i ∥ | A∗ = [[U (1) , . . . , U (K ) ]], U (k) ∈ Rd×Mk }.
(k){U (k) }i,k

固定デザイン・ランダムデザインのリスク:
固定デザイン:

1∥A − A∗ ∥2n :=nn∑
⟨Xi , A − A∗ ⟩2 .
i=1

ランダムデザイン:∥A − A∗ ∥2L2 := EX ∼PX [⟨X , A − A∗ ⟩2 ].
29 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法

固定デザインとランダムデザインの違い
固定デザイン: ∥A − A∗ ∥2n :=|422( 1 ∑nn8 *5.5* 2 + |{z}W = 14 *4noise{z}∗ 2i=1 ⟨Xi , A − A ⟩9*6*3*→) 12422.
8*4*
2*true value

ランダムデザイン: ∥A − A∗ ∥2L2 := EX ∼PX [⟨X , A − A∗ ⟩2 ] 2 .
1|4228 *
5.5* 2 + |{z}W = 14 *4noise{z}

9*
6*
3*→

42284
4422

true value

30 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法ベイズ事後分布の収束 (posterior 1)
A∗ : CP-ランク d.
(k)∥A∗ ∥max,2 := min{U (k) } {maxi,k ∥U:,i ∥ | A∗ = [[U (1) , . . . , U (K ) ]], U (k) ∈Rd×Mk }. (c.f., max-norm (Srebro & Shraibman, 2005))
L = ∥A∗ ∥max,2 とする.
Theorem
ある n, {Mk }k とは関係ない定数 C が存在して，
[]
∫1
∗ 2
EY1:n |X1:n∥A − A ∥n dΠ(A|X1:n , Y1:n )
2σ 2
∑K()
√ ∑d( k=1 Mk ) L
σpKK
L
22
K( σp ∨ 1) log ξ K n( k=1 Mk ( σp ∨ 1) ) .
≤Cn
このレートはデザイン行列に 強凸性を何も仮定せず に得られる．
ランク d は事前に知っている必要はない．自動的に調節．
31 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法ベイズ事後分布の収束 (posterior 1)
A∗ : CP-ランク d.
(k)∥A∗ ∥max,2 := min{U (k) } {maxi,k ∥U:,i ∥ | A∗ = [[U (1) , . . . , U (K ) ]], U (k) ∈d×MkR}. (c.f., max-norm (Srebro & Shraibman, 2005))
L = ∥A∗ ∥max,2 とする.
Theorem
ある n, {Mk }k とは関係ない定数 C が存在して，[]∫21∗
EY1:n |X1:nAdΠ(A|X1:n , Y1:n ) − A
2σ 2n
∑K()
√K
∑Kd( k=1 Mk ) Lσ( σp ∨ 1)2 log ξp K n( k=1 Mk ( σLp ∨ 1)2 )K .
≤Cn
このレートはデザイン行列に 強凸性を何も仮定せず に得られる．
ランク d は事前に知っている必要はない．自動的に調節．
31 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法ベイズ事後分布の収束 (posterior 2)∥A∗ ∥max,2 ≤ Rσp を仮定.
(真のテンソルは事前分布の台に含まれている)
Theorem
ある n, {Mk }k とは関係ない定数 C が存在して，
[]
∫
1
∗ 2
EY1:n ,X1:n∥A − A ∥n dΠ(A|∥A∥max,2 ≤ R, X1:n , Y1:n )
2σ 2
∑K())
d( k=1 Mk ) (σK √≤C
1 ∨ R 2 log K ξp nR K .
nlog 内の値が改善されている.

32 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法

ランダムデザイン におけるベイズ事後分布の収束∥A∗ ∥max,2 ≤ Rσp を仮定.
(真のテンソルは事前分布の台に含まれている)
Theorem
ある n, {Mk }k とは関係ない定数 C が存在して，
[]
∫1
∗ 2
EY1:n ,X1:n∥A−A∥dΠ(A|∥A∥≤R,X,Y)
max,2
1:n
1:n
L22σ 2∑K())
d( k=1 Mk ) (σK √≤C1 ∨ R 2(K +1) log K ξp nR K .
n
ランダムデザインでも ほぼ同じ収束レートを達成.

33 / 37

低ランク行列推定

低ランクテンソル推定

References

ベイズ推定法ミニマックス最適性

ランク d ，max-ノルム R 以下の集合:{}
Hd (R) := A ∈ RM1 ×···×MK | CP-ランク d, ∥A∥max,2 ≤ R .

Xi = ei1 ⊗ ei2 ⊗ · · · ⊗ eiK で，(i1 , . . . , iK ) は一様分布．
Theorem
Hd (R) 上のテンソル推定量のミニマックス最適リスクは以下で抑えられる:}{d(M1 + · · · + MK ) 2K
min ∗max E[∥Ab − A∗ ∥2L2 ] ≳ min σ 2,R.
b A ∈Hd (R)nA※ 先の収束レートは log 項を除いてミニマックス最適レートを達成．

34 / 37

低ランク行列推定

低ランクテンソル推定

References

数値実験

凸正則化手法との比較
0.98

setting 2: Bayes
setting 2: Convex
setting 5: Bayes
setting 5: Convex

0.8

0.7

6

Out-of-sample acc.

In-sample acc.

0.6

Bayes

0.5

0.4

0.3

0.2

0.1

00.4

0.5

0.6

ns

0.7

0.8

setting 2: Bayes
setting 2: Convex
setting 5: Bayes
setting 5: Convex

70.9

Convex

5432

100.4

0.5

0.6

ns0.7

0.80.9Figure: ベイズ推定法と凸正則化法 (和型 Schatten-1 ノルム) との比較.

35 / 37

低ランク行列推定

低ランクテンソル推定

References

数値実験

誤差のスケール
40.45

setting 1
setting 2
setting 3
setting 4
setting 5

0.4

Actual in-sample acc.

Scaled in-sample acc.

3.5

3

2.5

2

1.5

1

0.4

0.5

0.6

0.7

0.8

0.9

ns0.35

0.3

0.25

0.2

0.15

0.1

0.05

00.4

0.5

0.6

0.7

0.8

0.9

nsFigure: 固定デザイン: The scaled predictive accuracy (left) and the actual
predictive accuracy (right) against the number of samples.

scaled accuracy =actual accuracy∑Kd( k=1 Mk )36 / 37

低ランク行列推定

低ランクテンソル推定

References

数値実験

誤差のスケール
6

0.7

setting 1
setting 2
setting 3
setting 4
setting 5

5.5Actual out-of-sample acc.

Scaled out-of-sample acc.

0.6
5

4.5

4

3.5

3

2.5

2

1.5

1

0.4

0.5

0.6

0.7

0.8

0.9

ns

0.5

0.4

0.3

0.2

0.1

0

0.4

0.5

0.6

0.7

0.8

0.9

nsFigure: ランダムデザイン: The scaled predictive accuracy (left) and the actual
predictive accuracy (right) against the number of samples.

scaled accuracy =actual accuracy∑Kd( k=1 Mk )36 / 37

低ランク行列推定

低ランクテンソル推定

References

数値実験

まとめ
低ランクテンソル推定における事後分布の収束レートを導出.
推定誤差のミニマックス最適レートを導出.
導出した上界は (ほぼ) ミニマックス最適であることを証明.

Posterior contraction rate
∥Ab − A∗ ∥2n ≤ C√d(M1 + · · · + MK )log(K nR K ).
nMinimax rate{}∗ 22 d(M1 + · · · + MK )2Kb,R.
min ∗max E[∥A − A ∥L2 ] ≳ min σb A ∈Hd (R)nA37 / 37

低ランク行列推定

低ランクテンソル推定

References

Alquier, P. (2013). Bayesian methods for low-rank matrix estimation:
Short survey and theoretical study. Algorithmic Learning Theory (pp.
309–323). Springer-Verlag.
Anderson, T. (1951). Estimating linear restrictions on regression
coeﬃcients for multivariate normal distributions. Annals of
Mathematical Statistics, 22, 327–351.
Argriou, A., Evgeniou, T., & Pontil, M. (2008). Convex multi-task
feature learning. Machine Learning, 73, 243–272.
Argyriou, A., Micchelli, C. A., Pontil, M., & Ying, Y. (2008). A spectral
regularization framework for multi-task structure learning. Advances inNeural Information Processing Systems 20 (pp. 25–32). Cambridge,
MA: MIT Press.
Bennett, J., & Lanning, S. (2007). The netflix prize. Proceedings ofKDD Cup and Workshop 2007.
Burket, G. R. (1964). A study of reduced-rank models for multiple
prediction, vol. 12 of Psychometric monographs. Psychometric Society.
Candès, E., & Tao, T. (2009). The power of convex relaxations:
Near-optimal matrix completion. IEEE Transactions on Information
Theory, 56, 2053–2080.
37 / 37低ランク行列推定

低ランクテンソル推定References

Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex
optimization. Foundations of Computational Mathematics, 9, 717–772.
Hitchcock, F. L. (1927). Multilple invariants and generalized rank of ap-way matrix or tensor. Journal of Mathematics and Physics, 7, 39–79.
Izenman, A. J. (1975). Reduced-rank regression for the multivariate
linear model. Journal of Multivariate Analysis, 248–264.
Kolda, T. G., & Bader, B. W. (2009). Tensor decompositions andapplications. SIAM Review, 51, 455–500.
Koltchinskii, V. (2012). Sharp oracle inequalities in low rank estimation(Technical Report). arXiv:1210.1144.
Mu, C., Huang, B., Wright, J., & Goldfarb, D. (2014). Square deal:Lower bounds and improved relaxations for tensor recovery.
Proceedings of the 31th International Conference on Machine Learning(pp. 73–81).
Negahban, S., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012). A
unified framework for high-dimensional analysis of m-estimators withdecomposable regularizers. Statistical Science, 27, 538–557.
Negahban, S., & Wainwright, M. J. (2012). Restricted strong convexity
and weighted matrix completion: Optimal bounds with noise. Journalof Machine Learning Research, 13, 1665–1697.
37 / 37

低ランク行列推定

低ランクテンソル推定

References

Rai, P., Wang, Y., Guo, S., Chen, G., Dunson, D., & Carin, L. (2014).
Scalable Bayesian low-rank decomposition of incomplete multiwaytensors. Proceedings of the 31th International Conference on Machine
Learning (pp. 1800–1808).
Rohde, A., & Tsybakov, A. B. (2011). Estimation of high-dimensional
low-rank matrices. The Annals of Statistics, 39, 887–930.
Shen, W., & Ghosal, S. (2014). Adaptive bayesian density regression for
high-dimensional data. arXiv:1403.2695.
Srebro, N., Alon, N., & Jaakkola, T. (2005a). Generalization error
bounds for collaborative prediction with low-rank matrices. Advancesin Neural Information Processing Systems (NIPS) 17.
Srebro, N., Rennie, J., & Jaakkola, T. (2005b). Maximum margin matrix
factorization. Advances in Neural Information Processing Systems 17(pp. 1329–1336). MIT Press.
Srebro, N., & Shraibman, A. (2005). Rank, trace-norm and max-norm.
Proceedings of the 18th Annual Conference on Learning Theory (pp.
545–560). Springer-Verlag.
Tomioka, R., & Suzuki, T. (2013). Convex tensor decomposition via
structured schatten norm regularization. Advances in Neural
Information Processing Systems 26 (pp. 1331–1339). NIPS2013.
37 / 37

低ランク行列推定

低ランクテンソル推定

References

数値実験

Tomioka, R., Suzuki, T., Hayashi, K., & Kashima, H. (2011). Statistical
performance of convex tensor decomposition. Advances in Neural
Information Processing Systems 24 (pp. 972–980). NIPS2011.
Tucker, L. R. (1966). Some mathematical notes on three-mode factor
analysis. Psychometrika, 31, 279–311.
Xiong, L., Chen, X., Huang, T.-K., Schneider, J., & Carbonell, J. G.
(2010). Temporal collaborative filtering with bayesian probabilistic
tensor factorization. Proceedings of SIAM Data Mining (pp. 211–222).
Xu, Z., Yan, F., & Qi, Y. (2013). Bayesian nonparametric models for
multiway data analysis. IEEE Transactions on Pattern Analysis andMachine Intelligence, 99, 1. PrePrints.
Yang, Y., & Dunson, D. B. (2013). Bayesian conditional tensor
factorizations for high-dimensional classification. arXiv:1301.4950.
Zhou, J., Bhattacharya, A., Herring, A., & Dunson, D. (2013). Bayesian
factorizations of big sparse tensors. arXiv:1306.1598.

37 / 37