自己紹介
• 専門：
– 統計的機械学習 / データマイ
ニング / 数理計画
• 機械学習？
– 多種多量のデータを解析する
ための方法論
• 例：ビジネス、医療、バイオ
New York Times 2012/11/24
• 今回のミニシンポジウムとの関係
テンソル型データ
• 行列型データの拡張として捉えられる
Vector (1D)
Matrix (2D)
Tensor (3D)
Sam
pl
es
Sam
pl
es
Features
Sam
pl
es
Features
テンソル型データで何をしたいか
• ノイズに埋もれた低ランク構
造を復元したい。
– 主成分分析の多次元拡張
• 欠損値を復元したい。
– 例：いくつかのセンサーが壊
れている
– レコメンデーション
（e.g., Amazon, Facebook）
−5 −4 −3 −2 −1 0 1 2 3 4 5 −3 −2 −1 0 1 2 3
復習：特異値分解 (SVD)
X
=
U
Σ
V
T
d
1
r
r
r
d
2
where U, V: Orthogonal (U
T
U=I, V
T
V=I)
=
1
...
r
σ
j
: jth largest singular value
r: rank (number of non-‐zero
singular values)
•
Note: r ≤ min(d
1
,d
2
)
•
Can be computed efficiently even for very large matrices
(see Liberty et al. “Randomized algorithms for the low-‐
rank approximaEon of matrices.”PNAS, 2007)
d
2
Tucker 分解
[Tucker 66]
• それぞれのモード（次元）が異なるランクを
持つ
• 直交変換の不定性
– 通常はコアが all-orthogonal となるようにする。
d
1
d
2
d
3
X
ijk
=
r
1⇤
a
=1
r
2⇤
b
=1
r
3⇤
c
=1
C
abc
U
i
(1)
a
U
j
(2)
b
U
k
(3)
c
⇥
r
1
r
2
r
3
=
1
d
1
2
3
r
1
d
2
r
2
d
3
r
3
Core
Factors
Tucker 分解の計算
n
1
n
2
n
3
n
1
n
2
n
2
n
2
n
2
・
n
3
Mode-1 unfolding
X
(1)
1. テンソルの展開（行列化）
2. 特異値分解
3. すべてのモードに関して繰り返す
X
(1)
U
(1)
V
1
T
=
Σ
1
d
1
d
2
d
3
d
1
r
1
r
1
r
1
r
1
d
2
d
3
d
1
d
2
d
3
d
1
d
2
d
2
d
2
d
2
d
3
コアの計算
U
(1)
, U
(2)
, U
(3)
を計算したあと、
d
1
d
2
d
3
r
1
r
2
r
3
=
1
2
3
d
1
r
1
r
2
d
2
r
3
d
3
Core
Factors
C
abc
=
d
1
X
i
=1
d
2
X
j
=1
d
3
X
k
=1
X
ijk
U
i
(1)
a
U
j
(2)
b
U
k
(3)
c
ランダムテンソル理論？
• Marchenko-Pastur 分布 (ランダム行列
の特異値の分布)
0 50 100 150 200 0 5 10 15 20 25 30 35 40 Order Singular values Gaussian, size=[200 500] 0 50 100 150 200 0 5 10 15 20 25 30 35 40 Order Singular values Uniform, size=[200 500] empirical spectrum theory empirical spectrum theoryテンソルのコアについて似たようなことが言えるか？
CP分解
• CP = CANDECOMP
[Carroll & Chang 70]
/
PARAFAC
[Harshman 70]
d
1
d
2
d
3
=
R
r=1
a
r
b
r
c
r
X
ijk
=
R
r=1
a
ir
b
jr
c
kr
Tucker分解の特別な場合（コアが対角）と見なせる
C =
R
R
R
最小のRは
ランク
と
呼ばれる。
CP分解の性質
• ランクの判定は
NP完全
[Håstad 90]
– 実際には適当なランクで近似することが多い。
• CP分解はある条件のもとでスケーリング
と置換の自由度を除いて
ユニーク
k-rank: 行列の任意のk本の列が線形独立
となる最大のk
CP分解の性質（続き）
X is rank 3
Y is rank 2
⌃X
Y⌃
F
⇥ 0
( ⇥ ⇤)
Kolda & Bader 2009
X = a
1
b
1
c
2
+ a
1
b
2
c
1
+ a
2
b
1
c
1
Y = (a
1
+
1
a
2
) ⇥ (b
1
+
1
b
2
) ⇥ (c
1
+
1
c
2
)
従来のテンソル分解法の問題
• ノイズや欠損値にどう対応するか
– 単純にSVDはできない
– 繰り返し最適化法は
局所最適
• ランクをどう選ぶか
– ランクが高すぎると
• ノイズの影響を受けやすい（オーバーフィット）
• 計算量多い（計算量トレードオフ）
– 何ら仮定なしに欠損値の復元は不可能
• 低ランク性はひとつの有効な仮定
凸最適化に基づく
大域最適
な推定法
（かつ
ランク自動決定
）を提案
凸関数・非凸関数
x
f(x)
y
f(y)
f(x)
f(y)
Non−convex
Convex
(-‐1,-‐1)
(1,1)
u
v
低ランク分解が局所最適になるイメージ
最適化問題
Non-‐convex!
minimize
U
,
V
(ij)⇥
(y
ij
u
i
⇤
v
j
)
2
ランク制約？
minimize
W
(ij)⇤
(y
ij
w
ij
)
2
,
subject to
rank(
W
)
⇥ r
最適化問題
SEll non-‐convex!
W=UV
T
を言い換えただけ
ランクの凸緩和
Schatten
p
-ノルム
(のp乗)
−3
0
−2
−1
0
1
2
3
1
2
3
4
|x|
0.01|x|
0.5|x|
x
2p=1
は最もタイ
トな凸緩和
(
trace norm /
nuclear norm
と
も呼ばれる
)
j
(
W
)
: jth largest singular value
W
p
S
p
:=
r
j=1
p
j
(
W
)
⇤
W
⇤
p
S
p
p
⇥0
⇥ rank(
W
)
凸最適化に基づく低ランク行列補完
minimize
W
(ij)⇤
(y
ij
w
ij
)
2
,
subject to
⌅
W
⌅
S
1
⇥
最適化問題
凸緩和
Schatten 1-ノルム
j
(
W
)
: jth largest singular value
W
S
1
=
r
j=1 j
(
W
)
Tuckerランクの凸緩和
Schatten 1-norm of
the
mode-l unfolding
W
S
1
:=
1
L
L
X
l=1
kW
(l)
k
S
1
n
1
n
2
n
3
n
1
n
2
n
2
n
2
n
2
・
n
3
Mode-1 unfolding
X
(1)
d
1
d
2
d
3
d
1
d
2
d
2
d
2
d
2
d
3
復元性能
minimize
X
X
S
1
,
subject to X
ijk
= Y
ijk
((i, j, k)
)
最適化問題
0
0.2
0.4
0.6
0.8
1
10
−310
0Fraction of observed elements
Estimation error
Convex
Tucker (exact)
Optimization tolerance
相転移！→なぜか？
解析：問題設定
観測モデル
ガウス雑音
最適化問題
正則化定数
観測作用素
X
(W) = ( X
1
,
W , . . . , X
M
,
W )
データ尤度
正則化項
ˆ
W =
argmin
W R
n1 ··· nK1
2
y
X
(W)
2
2
+
M
W
S
1y
i
= X
i
,
W +
i
(i = 1, . . . , M)
W
: 真のテンソル ランク(r
1
,...,r
L
)
D =
L
Y
l=1
d
k
!
X :
R
D
! R
M
解析結果
（ランダムガウスデザイン）
1. サンプル数Mに関する条件
2. 正則化定数λ
M
に関する条件
正規化ランク
#samples(M )
#variables(D)
c
1
kd
1
k
1/2
krk
1/2
⇡
r
d
M
c
0
X
L
l=1
⇣p
d
l
+
p
D/d
l
⌘
/(L
p
M )
ˆ
W
W
⇤ 2
F
N
O
p
2
kd
1
k
1/2
krk
1/2
M
!
kd
1
k
1/2
:=
⇣
1
L
P
L
l=1
p
1/d
l
⌘
2
,
krk
1/2
:=
⇣
L
1
P
L
l=1
p
r
l
⌘
2
0
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
1
Normalized rank ||n
−1||
1/2||r||
1/2Fraction at err<=0.01
size=[50 50 20]
size=[100 100 50]
size=[50 50 20 10]
0 0.2 0.4 0.6 0.8 1 10−3 100Fraction of observed elements
Estimation error Convex [7 8 9] Covex [40 9 7] Optimization tolerance
0.01
テンソル補完性能
観測ノイズなし
相転移点
size = 50x50x20 true rank 7x8x9 or 40x9x7
正規化ランク
#samples(M )
#variables(D)
ディスカッション
• ランダムガウスデザイン（＝Xの要素が独
立同一なガウス乱数）
– 解析が容易（ランダム行列の最大特異値）
– テンソル補完の状況とは異なる
– それにも関わらず理論と実験はよく一致
• 理論はかなり悲観的
– 必要なサンプル数
M = O(rd
L 1
)
O(rdL + r
L
)
まとめ
• Tucker 分解 (=HOSVD)
– ランクの判定は容易
– 特異値 -> コアテンソル
– 不定性、局所最適
• CP 分解
– ランクの判定はNP完全
– 分解がユニークになる場合がある
– 局所最適
• 凸最適化にもとづくHOSVD
– 大域最適解が求まる
– 解の統計的な性質の理論解析が可能
– 計算量的には改善が必要
参考文献
• Kolda & Bader (2009) Tensor decompositions and applications. SIAM Review, 51(3):455‒500. • Tucker (1966) Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3):279‒
311.
• Candès & Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 9(6):717‒ 772, 2009.
• Candès & Tao. The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inform. Theory, 56(5):2053‒2080, 2010.
• Foygel & Srebro. Concentration-based guarantees for low-rank matrix reconstruction. Arxiv preprint arXiv:1102.3923, 2011.
• Gandy, Recht, & Yamada (2011) Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27:025010.
• Liu, Musialski, Wonka, & Ye. (2009) Tensor completion for estimating missing values in visual data. In Prof. ICCV.
• Signoretto, de Lathauwer, & Suykens (2010) Nuclear norms for tensors and their use for convex multilinear estimation. Tech Report 10-186, K.U.Leuven.
• Recht, Fazel, & Parrilo (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(3):471‒501.
• Tomioka, Hayashi, & Kashima (2011) Estimation of low-rank tensors via convex optimization. Technical report, arXiv:1010.0789, 2011.
• Tomioka, Suzuki, Hayashi, & Kashima (2011) Statistical performance of convex tensor decomposition. Advances in NIPS 24. 2011, Granada, Spain.
