THE UNIVERSITY OF TOKYO

数理情報学演習第二Ａ

関係データの機械学習- 行列と多次元配列の解析 -かしま

ひさし

鹿島 久嗣
情報理工学系研究科
数理情報学専攻 数理6研
kashima@mist.i.～

DEPARTMENT OF MATHEMATICAL INFORMATICS* Some figures in the slides are taken fromT. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455–500,
2009.
THE U
NIVERSITY OF TOKYO

1

機械学習による関係データの解析手法について紹介します

関係データとは– 関係データとは何か– 関係データにはどのようなものがあるか– 関係データ解析のタスク


関係データの表現– 行列と多次元配列



関係データの解析方法– 低ランク性の仮定– 特異値分解– テンソル分解2

関係データ解析の応用
THE UNIVERSITY OF TOKYO1

関係データ3

THE UNIVERSITY OF TOKYO

近年、データ間の関係の解析が注目を浴びつつある 従来：「個々のデータを対象とした解析 」

近年：「データの間の関係の解析」
 データ間の関係に注目することで、個々のデータに注目しているだけでは見えない性質が見えてくる– コンピュータネットワーク上のプロセス依存関係から異常を予測– 複数の脳波時系列の相関関係から思考を読みとる

 関係の分析は様々な領域において盛んに行われつつある– ソーシャルネットワーク分析：人間関係– オンラインショッピング：顧客と商品の間の関係

4

THE UNIVERSITY OF TOKYO2

関係データとは ものごとの関係を表現したデータ


通常のデータ解析では、ひとつのデータについて成り立つ性質を推論する

関係データとは： データの組についてのデータ



関係の成立や、関係のもつ性質についての推論を行う
ある性質をもつか？

ある関係があるか？

単一データについての予測

2つのデータの関係についての予測

5

THE UNIVERSITY OF TOKYO

関係データの例：マーケティング、Web、バイオ、…
オンラインマーケティング– 顧客と商品との間の関係（購買、評価）ソーシャルネットワーク– SNS内の人間関係 (facebook, twitter, mixi, …)– 企業間取引生体ネットワーク– タンパク質相互作用ネットワーク– 化合物-タンパク質相互作用

6

THE UNIVERSITY OF TOKYO3

関係データを用いたタスク：予測と発見

予測– 推薦システム（協調フィルタリング）•

顧客と商品との間の関係（購買、評価）を予測– 例： Netflix challenge– SNSの友人推薦– 新規薬剤候補の探索
発見– 顧客セグメンテーションの発見– 協調するタンパク質グループの発見– 例外の発見

7

THE UNIVERSITY OF TOKYO

関係データの形式的表現

8

THE UNIVERSITY OF TOKYO

4

関係データの表現：グラフや行列など

通常、データは表形式で不えられる
顧客番号

顧客氏名

年齢

性別

住所

…

0001

○○

４０代

男性

東京都

…

0002

××

３０代

女性

大阪府

…

関係データはこれらの間の関係を表す
０００１０００２

数学的な表現– 行列／多次元配列– グラフ／ハイパーグラフ

9THE UNIVERSITY OF TOKYO

2項関係の集合は行列として表現できる


2項関係は行列として表現できる– 行と列がデータの集合に対応– 各要素がデータ間の関係を表す



グラフ（重みつき）の隣接行列としてもみることができる商品-------------------

顧客-------------------

１-------------------

５
２
３

10

-------------------

評価

４
３

THE UNIVERSITY OF TOKYO5

多項関係の集合は多次元配列やハイパーグラフとして表現できる


多項関係の集合は多次元配列として表現できる

ハイパーグラフとしても表現可能– こちらのほうがより一般的：関係に参加するデータの数が可変

時間

商品

超辺

顧客

多次元配列
11

ハイパーグラフTHE UNIVERSITY OF TOKYO

行列データ（２項関係）の解析手法

12THE UNIVERSITY OF TOKYO6

行列データの解析手法


行列の補完問題を考える

協調フィルタリングの初等的手法：GroupLens

行列の低ランク分解



トレースノルム

13THE UNIVERSITY OF TOKYOGroupLens：協調フィルタリングの初等的手法
推薦システム（協調フィルタリング）は、顧客と商品との間の関係（購買、評価）を予測する



値が分かっている部分から、わかっていない部分を予測したいGroupLens：初期の予測アルゴリズム– ニュースの推薦が目的-------------------

顧客商品-------------------

１-------------------

５２
３

14-------------------

評価

４３

THE UNIVERSITY OF TOKYO7

GroupLensでは、ある顧客の評価を、似た顧客の評価を持ってきて予測する


予測したい顧客と似た顧客を集め、類似顧客の評価を用いて予測を行う– Aさんの未知要素を予測したいとする– Aさんと良く似た評価を行っている別の顧客を集めてきて、彼らの評価を用いて予測する

Aさんに似た人----------------------------------------------------------------------------

１２５５

２４５？

Aさん

５

知りたい要素３15

THE UNIVERSITY OF TOKYO「似ている」の定義は 評価値の相関係数で測り、相関係数で重みづけして予測します

2人の顧客の類似度を（共に評価値が観測されている部分の）相関係数で測る



相関係数で重みづけし予測を行う

yi,j = yi + Σki ½i,k ( yk,j - yk) / Σki ½i,k

同様に、商品間の類似度を用いることも可能

相関係数
相関係数16----------------------------------------------------------------------------

１２５５２４4.5５

重みつき予測３THE UNIVERSITY OF TOKYO

8協調フィルタリングの初等的手法は行列の低ランク性を暗に仮定している


行列の各行が、別の行の（相関係数で重み付けた）線形和によって表せるとしている– 線形従属

対象となる行列のランクがフルランクではない（⇒低い）ことを暗に仮定した方法ということになる



低ランク性の仮定は行列の穴埋めに有効であろう– データよりもパラメータが多い状況では、なんらかの事前知識を用いて解に制約を設ける必要がある– 低ランク性の仮定は、実質パラメータ数を減らす

17THE UNIVERSITY OF TOKYO

低ランク性を仮定する
低ランク性の仮定：行列が2つの（薄い）行列の積で書ける
商品
顧客X～

UV>

ランク

minimizeY ||X - Y ||F2 s.t. rank(Y)· k

実効パラメータ数が減っている

U（V）の各行： 顧客（商品）の特徴を捉えた低次元の潜在空間にデータを配置– この空間で近いものが似た顧客（商品）：グループ構造

18THE UNIVERSITY OF TOKYO9

特異値分解もよく用いられる


行列分解 X = UV>の仮定だけでは、解の丌定性があるので、制約を入れる



特異値分解

X
•


～

D
U

V>
対角行列（特異値）

制約： U>U = I V>V = I

X>X の固有値問題になる– 固有値を大きい方からk個とる

19THE UNIVERSITY OF TOKYO

欠損値がある場合には特異値分解は使えない

ランク制約をもった最適化問題は凸最適化問題ではない– ランクk以下の行列は凸集合ではない•目的関数 ＝ 復元誤差（凸関数） ＋ランク制約

minimizeY ||X - Y ||F2 s.t. rank(Y)· k

もしくは分解を UV> と明示的におくと誤差項が非凸になってしまう

minimizeY ||X - UV > ||F2


全データが観測されている場合には、固有値問題としてたまたま解ける

欠損値がある場合には困る

20

THE UNIVERSITY OF TOKYO10欠損値がある場合には、EMアルゴリズムが用いられる


ひとつの方法としては気にせず、勾配法などで適当に解く– データが大きいときにはこちら

EMアルゴリズム：未観測部分には暫定的な推定値をあてはめ、完全観測として問題を解く
1. 未観測部分を適当に初期化（平均など）
2. 低ランク行列分解を適用
3. 復元した値で未観測部分の値を置き換えるステップ 2~3を収束まで繰り返す

21

THE UNIVERSITY OF TOKYO

凸最適化としての定式化：トレースノルム正則化


行列のランク制約は凸集合ではないので、凸集合であり、ランク制約のよい近似となるような制約がほしい

行列の特異値の和を用いる

特異値||Y||* = ¾1(Y) + ¾2(Y) + …
– 特異値の集合（¾1(Y) , ¾2(Y),…）に対するL1ノルム制約と等価であるため、疎になる ⇒ ランクが落ちる– 一方、ランクは、非零の特異値の個数

目的関数 ＝ 観測部分の復元誤差 ＋ トレースノルム制約

minimizeY ||O*(X - Y )||F2 s.t. ||Y||*· c– 最適化は勾配法と特異値分解の組み合わせ22

THE UNIVERSITY OF TOKYO11

多次元配列（多項関係）の解析手法

23

THE UNIVERSITY OF TOKYO行列分解は多次元配列（テンソル）の低ランク分解に一般化される

行列の低ランク分解の多次元配列への一般化– ちいさな（コア）テンソルと因子行列に分解する

近年、機械学習やデータマイニングで盛んに用いられている
特異値行列

因子行列

因子行列

WX～

DUV>

X～ UGVコアテンソル24

THE UNIVERSITY OF TOKYO12

テンソル分解のタイプ：CP分解とTucker分解


よく用いられるのがCP分解とTucker分解

CP分解：特異値分解の自然な拡張（コアテンソルが対角；正方）Tucker分解：よりコンパクトな表現（みっちりコア；各モードの次数が異なる）
コアテンソルが対角

X～ U

コアテンソルが密W
GW
VX

CP分解

～ UG

V

Tucker分解25

THE UNIVERSITY OF TOKYOテンソルのランクは分解のタイプによって決まる


行列のランクはSVDの非零の特異値の数で決まった

テンソル分解の場合には分解のタイプによって決まる– CP分解、Tucker分解それぞれでランクの定義がある
コアテンソルのサイズがランク

対角テンソルのサイズがランク

W

X～ UCP分解

26

GW
V

X

～ UG

V

Tucker分解
THE UNIVERSITY OF TOKYO13

補足：テンソルの基本的演算

いくつか特殊な操作が用いられる– 行列化：テンソルを行列に変換する操作– モード積：テンソルと行列の掛け算

27

THE UNIVERSITY OF TOKYO

補足：テンソルの行列化


それぞれのモードに対してスライスが定義される– 各軸をモードと呼ぶ

モード3についてのスライスX

モード3行列化X(3)…

並べて行列にする



行列化はそれぞれのモードについてスライスをつなげたもの– X が3階テンソルなら、モードごとにX(1), X(2), X(3) の3つの行列ができる (4階以上も同様に定義される)* The figures are taken from T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.

28 –THE UNIVERSITY OF TOKYO14

補足：テンソルのモード積

各スライスのファイバー化

モード3についてのファイバー– ベクトルの集合を取り出す£3 UX £3 U

モード積は各モードのファイバーに行列を掛けること

X £3 U は 1-モード積の各ファイバーに行列U を掛ける

– Y = X £n U ⇔ Y(n) = UX(n)* The figures are taken from T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.

29

THE UNIVERSITY OF TOKYO

CP分解はランク１テンソルの和として定義される


行列はランク1行列の和＝＋＋…

ランク１行列

CP分解はランク1テンソルの和

ランク１テンソル

外積

X ～ r ¸r ar о br о crxijk = r ¸r ari brj crk* The figures are taken from T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3):455–500, 2009.

30THE UNIVERSITY OF TOKYO15

Tucker分解は小さいテンソルと行列によって定義される


Tucker分解はコアテンソルと、因子行列によって定義される– モード積を使って定義される

X ~ G £1 U £2 V £3 W (xijk = pqr gpqr uip viq wir)
WX～ UGV– 多くの場合因子行列の列ベクトルが正規直交であると仮定


CP分解はコアテンソルが対角であるようなTuckerの特殊ケース

G
31

THE UNIVERSITY OF TOKYOテンソル分解の方法：繰り返し最適化による準最適化

基本的には不えられたテンソルを2乗誤差の意味で最適近似するような分解を求める

minimize || X - Y ||F2 s.t. Y = G £1 U £2 V £3 W
最適解を求めるのは難しい– 凸最適化ではない– 特異値分解などで都合よく解が求まったりしない

繰り返し最適化を行うのが一般的– 最小二乗回帰もしくは特異値分解の繰り返し32THE UNIVERSITY OF TOKYO16

CP分解の方法：繰り返し最小二乗法（ALS）


解きたいのはminimizeY || X

- Y ||F2s.t. Y = G £1 U £2 V £3 W

=Z(1)Uについて最適化する（V, W についても同様）：

Y = Z £1 U ⇔ Y(1) = UZ(1)を使って目的関数を書き換えると|| X - Y ||F2 = || Y(1) - UZ(1) ||F2
これは最小二乗回帰


G は U, V, Wに吸収してよい（単位テンソル）

繰り返し最小二乗法（ALS）と呼ばれる

33

THE UNIVERSITY OF TOKYO

Tucker分解の方法：固有値問題の繰り返し
Tucker分解は直交条件が加わる：
minimize || X - Y ||F2 s.t. Y = G £1 U £2 V £3 W
s.t. U>U = I , V>V = I, W>W = I– Uについて最適化する（V, W についても同様）：•maxU || X - Y ||F2 = maxU || Y(1) - UZ(1) ||F2 = maxU tr Z(1)Y(1)> U•

2乗して maxU tr U> Y(1) Z(1)>Z(1)Y(1)> U s.t. U>U=I– これは固有値問題になる– G の最適解は G = X £1 U> £2 V> £3 W>

34

U, V, W について一回づつ解いて、最後にを求めて終わるものが高階SVD（HOSVD）、収束するまで繰り返すものを高階直行反復（HOOI）と呼ぶ
THE UNIVERSITY OF TOKYO17凸最適化問題としてのテンソル分解：
トレースノルムをテンソルに拡張する
テンソル分解の最適化問題は凸では無い行列の場合はトレースノルム（特異値の和）を用いることでランク制約を凸集合として入れることができた

トレースノルムをテンソルに拡張する– 行列化したもののトレースノルムを入れる

minimize || O*(X - Y) ||F2 s.t. n ||Y(n)||* · c

例えば：On the extension of trace norm to tensors. R.Tomioka, K.Hayashi, and H.Kashima, NIPS2010 Workshop: Tensors, kernels
and machine learning, 2010.

35

THE UNIVERSITY OF TOKYOテンソル分析の応用

36

THE UNIVERSITY OF TOKYO18

ソフトウェア：Matlabでの実装が公開されている
Matlabのツールボックスとして公開されている– Tensor Toolbox– N-way Toolbox

37

THE UNIVERSITY OF TOKYO事例
ソーシャルネットワーク分析

Webリンク解析

タグ推薦

脳みそ

画像認識

38

THE UNIVERSITY OF TOKYO19

以下借り物のスライドなので省略

39

THE UNIVERSITY OF TOKYO20