memo

Size: px

Start display at page:

Download "memo"

みりあかつもと
5 years ago
Views:

1 THE UNIVERSITY OF TOKYO 数理情報学演習第二 A 関係データの機械学習行列と多次元配列の解析かしまひさし鹿島久嗣情報理工学系研究科数理情報学専攻数理 6 研 kashima@mist.i.~ DEPARTMENT OF MATHEMATICAL INFORMATICS * Some figures in the slides are taken from 1T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3): , THE UNIVERSITY OF TOKYO 機械学習による関係データの解析手法について紹介します関係データとは関係データとは何か関係データにはどのようなものがあるか関係データ解析のタスク関係データの表現行列と多次元配列関係データの解析方法低ランク性の仮定特異値分解テンソル分解関係データ解析の応用 2 THE UNIVERSITY OF TOKYO 1

2 関係データ 3 THE UNIVERSITY OF TOKYO 近年データ間の関係の解析が注目を浴びつつある従来 : 個々のデータを対象とした解析近年 : データの間の関係の解析データ間の関係に注目することで個々のデータに注目しているだけでは見えない性質が見えてくるコンピュータネットワーク上のプロセス依存関係から異常を予測複数の脳波時系列の相関関係から思考を読みとる関係の分析は様々な領域において盛んに行われつつあるソーシャルネットワーク分析 : 人間関係オンラインショッピング : 顧客と商品の間の関係 4 THE UNIVERSITY OF TOKYO 2

3 関係データとはものごとの関係を表現したデータ通常のデータ解析ではひとつのデータについて成り立つ性質を推論する関係データとは : データの組についてのデータ関係の成立や関係のもつ性質についての推論を行うある性質をもつか? ある関係があるか? 単一データについての予測 2 つのデータの関係についての予測 5 THE UNIVERSITY OF TOKYO 関係データの例 : マーケティング Web バイオオンラインマーケティング顧客と商品との間の関係 ( 購買評価 ) ソーシャルネットワーク SNS 内の人間関係 (facebook, twitter, mixi, ) 企業間取引生体ネットワークタンパク質相互作用ネットワーク化合物タンパク質相互作用 6 THE UNIVERSITY OF TOKYO 3

4 関係データを用いたタスク : 予測と発見予測推薦システム ( 協調フィルタリング ) 顧客と商品との間の関係 ( 購買評価 ) を予測例 : Netflix challenge SNS の友人推薦新規薬剤候補の探索発見顧客セグメンテーションの発見協調するタンパク質グループの発見例外の発見 7 THE UNIVERSITY OF TOKYO 関係データの形式的表現 8 THE UNIVERSITY OF TOKYO 4

5 関係データの表現 : グラフや行列など通常データは表形式で不えられる顧客番号顧客氏名年齢性別住所代男性東京都代女性大阪府関係データはこれらの間の関係を表す数学的な表現行列 / 多次元配列グラフ / ハイパーグラフ 9 THE UNIVERSITY OF TOKYO 2 項関係の集合は行列として表現できる 2 項関係は行列として表現できる行と列がデータの集合に対応各要素がデータ間の関係を表すグラフ ( 重みつき ) の隣接行列としてもみることができる商品顧客評価 10 THE UNIVERSITY OF TOKYO 5

6 多項関係の集合は多次元配列やハイパーグラフとして表現できる多項関係の集合は多次元配列として表現できるハイパーグラフとしても表現可能こちらのほうがより一般的 : 関係に参加するデータの数が可変商品時間超辺顧客多次元配列ハイパーグラフ 11 THE UNIVERSITY OF TOKYO 行列データ (2 項関係 ) の解析手法 12 THE UNIVERSITY OF TOKYO 6

7 行列データの解析手法行列の補完問題を考える協調フィルタリングの初等的手法 :GroupLens 行列の低ランク分解トレースノルム 13 THE UNIVERSITY OF TOKYO GroupLens: 協調フィルタリングの初等的手法推薦システム ( 協調フィルタリング ) は顧客と商品との間の関係 ( 購買評価 ) を予測する値が分かっている部分からわかっていない部分を予測したい GroupLens: 初期の予測アルゴリズムニュースの推薦が目的商品顧客評価 14 THE UNIVERSITY OF TOKYO 7

8 GroupLens ではある顧客の評価を似た顧客の評価を持ってきて予測する予測したい顧客と似た顧客を集め類似顧客の評価を用いて予測を行う A さんの未知要素を予測したいとする A さんと良く似た評価を行っている別の顧客を集めてきて彼らの評価を用いて予測する A さんに似た人 A さん ? 5 3 知りたい要素 15 THE UNIVERSITY OF TOKYO 似ているの定義は評価値の相関係数で測り相関係数で重みづけして予測します 2 人の顧客の類似度を ( 共に評価値が観測されている部分の ) 相関係数で測る相関係数で重みづけし予測を行う y i,j = y i + Σ k i ½ i,k ( y k,j y k ) / Σ k i ½ i,k 同様に商品間の類似度を用いることも可能相関係数相関係数重みつき予測 16 THE UNIVERSITY OF TOKYO 8

9 協調フィルタリングの初等的手法は行列の低ランク性を暗に仮定している行列の各行が別の行の ( 相関係数で重み付けた ) 線形和によって表せるとしている線形従属対象となる行列のランクがフルランクではない ( 低い ) ことを暗に仮定した方法ということになる低ランク性の仮定は行列の穴埋めに有効であろうデータよりもパラメータが多い状況ではなんらかの事前知識を用いて解に制約を設ける必要がある低ランク性の仮定は実質パラメータ数を減らす 17 THE UNIVERSITY OF TOKYO 低ランク性を仮定する低ランク性の仮定 : 行列が2つの ( 薄い ) 行列の積で書ける商品顧客 X ~ U V > minimize Y X Y F2 s.t. rank(y) k 実効パラメータ数が減っているランク U(V) の各行 : 顧客 ( 商品 ) の特徴を捉えた低次元の潜在空間にデータを配置この空間で近いものが似た顧客 ( 商品 ): グループ構造 18 THE UNIVERSITY OF TOKYO 9

10 特異値分解もよく用いられる行列分解 X = UV > の仮定だけでは解の丌定性があるので制約を入れる特異値分解制約 : U > U = I V > V = I D X ~ U V > 対角行列 ( 特異値 ) X > X の固有値問題になる固有値を大きい方から k 個とる 19 THE UNIVERSITY OF TOKYO 欠損値がある場合には特異値分解は使えないランク制約をもった最適化問題は凸最適化問題ではないランク k 以下の行列は凸集合ではない目的関数 = 復元誤差 ( 凸関数 ) + ランク制約 minimize Y X Y F2 s.t. rank(y) k もしくは分解を UV > と明示的におくと誤差項が非凸になってしまう minimize Y X UV > F 2 全データが観測されている場合には固有値問題としてたまたま解ける欠損値がある場合には困る 20 THE UNIVERSITY OF TOKYO 10

11 欠損値がある場合には EM アルゴリズムが用いられるひとつの方法としては気にせず勾配法などで適当に解くデータが大きいときにはこちら EM アルゴリズム : 未観測部分には暫定的な推定値をあてはめ完全観測として問題を解く 1. 未観測部分を適当に初期化 ( 平均など ) 2. 低ランク行列分解を適用 3. 復元した値で未観測部分の値を置き換えるステップ 2~3 を収束まで繰り返す 21 THE UNIVERSITY OF TOKYO 凸最適化としての定式化 : トレースノルム正則化行列のランク制約は凸集合ではないので凸集合でありランク制約のよい近似となるような制約がほしい行列の特異値の和を用いる Y * = ¾ 1 (Y) + ¾ 2 (Y) + 特異値特異値の集合 (¾ 1 (Y), ¾ 2 (Y), ) に対する L 1 ノルム制約と等価であるため疎になるランクが落ちる一方ランクは非零の特異値の個数目的関数 = 観測部分の復元誤差 + トレースノルム制約 minimize Y O*(X Y ) F2 s.t. Y * c 最適化は勾配法と特異値分解の組み合わせ 22 THE UNIVERSITY OF TOKYO 11

12 多次元配列 ( 多項関係 ) の解析手法 23 THE UNIVERSITY OF TOKYO 行列分解は多次元配列 ( テンソル ) の低ランク分解に一般化される行列の低ランク分解の多次元配列への一般化ちいさな ( コア ) テンソルと因子行列に分解する近年機械学習やデータマイニングで盛んに用いられている特異値行列因子行列因子行列 W D X ~ U V > X ~ U G V コアテンソル 24 THE UNIVERSITY OF TOKYO 12

13 テンソル分解のタイプ :CP 分解と Tucker 分解よく用いられるのが CP 分解と Tucker 分解 CP 分解 : 特異値分解の自然な拡張 ( コアテンソルが対角 ; 正方 ) Tucker 分解 : よりコンパクトな表現 ( みっちりコア ; 各モードの次数が異なる ) コアテンソルが対角 W コアテンソルが密 W X ~ U G V X ~ U G V CP 分解 Tucker 分解 25 THE UNIVERSITY OF TOKYO テンソルのランクは分解のタイプによって決まる行列のランクはSVDの非零の特異値の数で決まったテンソル分解の場合には分解のタイプによって決まる CP 分解 Tucker 分解それぞれでランクの定義がある対角テンソルのサイズがランク W コアテンソルのサイズがランク W X ~ U G V X ~ U G V CP 分解 Tucker 分解 26 THE UNIVERSITY OF TOKYO 13

補足 : テンソルの基本的演算いくつか特殊な操作が用いられる行列化 : テンソルを行列に変換する操作モード積 : テンソルと行列の掛け算 27 THE UNIVERSITY OF TOKYO 補足 : テンソルの行列化それぞれのモードに対してスライスが定義される各軸をモードと呼ぶモード 3 についてのスライスモード 3 行列化 X X (3) 並べて行列にする

14 補足 : テンソルの基本的演算いくつか特殊な操作が用いられる行列化 : テンソルを行列に変換する操作モード積 : テンソルと行列の掛け算 27 THE UNIVERSITY OF TOKYO 補足 : テンソルの行列化それぞれのモードに対してスライスが定義される各軸をモードと呼ぶモード 3 についてのスライスモード 3 行列化 X 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): , THE UNIVERSITY OF TOKYO 14

29 THE UNIVERSITY OF TOKYO CP 分解はランク 1 テンソルの和として定義される行列はランク 1 行列の和 = + + ランク 1 行列 CP 分解はランク 1 テンソルの和ランク 1 テンソル外積 X ~ r r a r о b r о c r x ijk = r r

15 補足 : テンソルのモード積各スライスのファイバー化ベクトルの集合を取り出すモード 3 についてのファイバー 3 U X 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): , THE UNIVERSITY OF TOKYO CP 分解はランク 1 テンソルの和として定義される行列はランク 1 行列の和 = + + ランク 1 行列 CP 分解はランク 1 テンソルの和ランク 1 テンソル外積 X ~ r r a r о b r о c r x ijk = r r a ri b rj c rk * The figures are taken from T. G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51(3): , THE UNIVERSITY OF TOKYO 15

16 Tucker 分解は小さいテンソルと行列によって定義される Tucker 分解はコアテンソルと因子行列によって定義されるモード積を使って定義される X ~ G 1 U 2 V 3 W (x ijk = pqr g pqr u ip v iq w ir ) W X ~ 多くの場合因子行列の列ベクトルが正規直交であると仮定 CP 分解はコアテンソルが対角であるようなTuckerの特殊ケース U G G V 31 THE UNIVERSITY OF TOKYO テンソル分解の方法 : 繰り返し最適化による準最適化基本的には不えられたテンソルを 2 乗誤差の意味で最適近似するような分解を求める minimize X Y F2 最適解を求めるのは難しい凸最適化ではない s.t. Y = G 1 U 2 V 3 W 特異値分解などで都合よく解が求まったりしない繰り返し最適化を行うのが一般的最小二乗回帰もしくは特異値分解の繰り返し 32 THE UNIVERSITY OF TOKYO 16

17 CP 分解の方法 : 繰り返し最小二乗法 (ALS) 解きたいのは minimize Y X Y F2 s.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) F 2 これは最小二乗回帰 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 についても同様 ): max U X Y F2 = max U Y (1) UZ (1) F2 = max U tr Z (1) Y (1) > U 2 乗して max U 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 > U, V, W について一回づつ解いて最後にを求めて終わるものが高階 SVD(HOSVD) 収束するまで繰り返すものを高階直行反復 (HOOI) と呼ぶ 34 THE UNIVERSITY OF TOKYO 17

18 凸最適化問題としてのテンソル分解 : トレースノルムをテンソルに拡張するテンソル分解の最適化問題は凸では無い行列の場合はトレースノルム ( 特異値の和 ) を用いることでランク制約を凸集合として入れることができたトレースノルムをテンソルに拡張する行列化したもののトレースノルムを入れる 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, THE UNIVERSITY OF TOKYO テンソル分析の応用 36 THE UNIVERSITY OF TOKYO 18

19 ソフトウェア :Matlabでの実装が公開されている Matlabのツールボックスとして公開されている Tensor Toolbox Nway Toolbox 37 THE UNIVERSITY OF TOKYO 事例ソーシャルネットワーク分析 Webリンク解析タグ推薦脳みそ画像認識 38 THE UNIVERSITY OF TOKYO 19

20 以下借り物のスライドなので省略 39 THE UNIVERSITY OF TOKYO 20

memo

memo 数理情報工学特論第一機械学習とデータマイニング 4 章 : 教師なし学習 3 かしまひさし鹿島久嗣 ( 数理 6 研 ) kashima@mist.i.~ DEPARTMENT OF MATHEMATICAL INFORMATICS 1 グラフィカルモデルについて学びますグラフィカルモデルグラフィカルラッソグラフィカルラッソの推定アルゴリズム 2 グラフィカルモデル 3 教師なし学習の主要タスクは