局所相関推論とＮＭＦ

局所相関推論とＮＭＦ

Inferring Local Correlations based on NMF

笹原啓佑 原口誠

∗

Keisuke SASAHARA, Makoto HARAGUCHI

北海道大学大学院情報科学研究科

Graduate School of Information Science and Technology, Hokkaido University

Abstract: We propose a method for finding local correlations among among features of data matrices. We regard the problem of correlation finding as an inference problem from an analogical hint for illustrating what features are analogous and correlated wrt some aspect. Some of samples would explain or support the hint, while remaining ones can not. The former type samples work as evidences of correlation. We propose to find such evidences as a subset of row vectors well approximated by basis vectors for hint features. The basis is computed by a partial NMF with a clique regularization term. We compute another embedding space of features also found by partial NMF for a smaller data matrix formed by ignoring rows unrelevant to the hint. Two features are then judged correlated whenever they become identical or close after the embedding.

1

はじめに

データベースにおける属性やアイテムの相関 (corre-lation) 検出は，データマイニングにおける基本問題の 一つである．比較的多数の個体により支持される「大 域的」相関のみが興味の対象ではなく，相関を支持す る個体数が比較的に少数であるがゆえに「目立たない」 局所的相関も重要であろう．特定のユーザにとっては 発想や発見のトリガーとなりえるからである [10]． 相関はそれを支持する事物（トランザクションや個 体）の集合が大規模もしくは大域的である場合は，標 準的な相関検出技法が良く用いられ，それで十分であ ろう．一方，本稿でターゲットとする局所相関の場合 は，支持集合が小∼中規模のものを想定しており，そ れ故に，可能な局所相関の数は一般に膨大であり，た とえ列挙できたとしても，（ユーザにとって）興味深い ものを洗い出すのはそう簡単ではない．「興味深さ」と いうコスト関数で絞り込むアプローチも，マイニング 研究の初期からいくつか提案されているが，多様な個 人の興味をカバーできるコスト関数はなかなか厳しい と思われる． 本稿で考察する相関とは，素朴な余弦類似度や内積 で良いが，データ行列の形でデータが提供される場合 は，行の一部分で観測できる相関を意味する例えば文 書ー項のデータ行列であれば，文書を制限してはじめ て観測できる項の共起であり，いわば条件付けた相関 ∗_{連絡先： 北海道大学大学院情報科学研究科}        札幌市北区北１４西９        E-mail: [email protected] とも言える．図 1 においては{x1, x2, x3, x4} に制限す れば，f1 と f2，および f3 と f4 の局所相関を認める ことができる． こうした局所相関は，ブール値のデータの場合は，組 み合わせ論的には形式概念分析 [9] における内包（属 性集合の閉包）と外延（それを支持する個体の閉包）の 組として列挙できるが，前述したように，候補となる 組の数が多すぎるという難点がある．また，行の相関 と列の相関を同時に求める，トライＮＭＦによっても 求めることができるが，基本的には ＮＭＦ の最適化手 法の拡張になっているために，結果的に局所相関は無 視され，大域的相関のみが浮かび上がる仕掛けとなっ ている． 上記の議論から，本稿で求めるべき方法とは，行（も しくは列）を如何にして制限するかが本質的となる．こ のために，相関検出を類推 [1]，特に，ヒント [2] に基づ いて類似性を推論する問題として考える．ここにヒン トとは，属性（列）f_i(k) の類似関係 f_i(1)∼ f(2) i をいく つか与え，その類似関係を説明できる事物に限定して 成り立つ 他の類似性 f_i+1(1) ∼ f(2) i+1 を推論する．ここで， 与えられる類似属性対の数が多い場合は，相関学習とし てとらえることも可能である．例えば，f(j) i (j = 1, 2) を同じラベルを持つグラフの頂点とみれば，多重ラベ ル学習問題としても定式化できる [8]. しかし，この場 合においてもトライ分解のときと同様に，ラベルの近 接性を近似できる線形部分空間を最適化により求めて おり，本稿で求める局所相関に焦点を与えた解法とは なっていない．こうした先行研究とは異なり，所与の 人工知能学会研究会資料 SIG-FPAI-B802-01 － 2 －

データ行列 X がブール値の 場合. ヒントH = {< f1, f2>, < f3, f4>} 右図は X の列をヒント属 性 {f1, f2, f3, f4} に制限し た部分行列．属性対の無相関 部分（行）は，生成系G = (g1 g2)が張る部分空間への射 影により無視できるが，H = (f₁f₂ f₃ f₄)の 圧縮として のGは，無相関部分の捨象に 起因する近似精度劣化を伴う． 図 1: 局所相関と生成系の例 ヒントを説明できる「エビデンス」行を先に求め，そ うした行に制限した上でヒントに出現しない列の相関 を射影空間における近接性で捉える． 行 xi = (xij)j がヒント fk1 ∼ fk2 を説明 できる行とは，近似関係 xik1 ≈ xik2 が成 り立つことと定める． この近似式はヒントで結合された属性（列）をグラフ として表現したとき，座標ベクトルとしての x がグラ フの近接関係を近似的に表現している．グラフ頂点の 近接性データから定まるグラフラプラシアン L の２次 形式 xt_{Lx として書けるので，グラフ正則化項を用い} たＮＭＦ [4] でヒントを説明できる行の生成系（圧縮） が求まることに気づく． 図 1 の 場合は２個の行生成ベクトル（(1, 1, 0, 0) お よび (0, 0, 1, 1)）の線形結合となる x とそれ以外の x の生成系にきれいに分離できる．一般には，各行はヒ ントとは無関係な情報も含んでいることが考えられる． そのことも考慮し，生成系をヒントを説明できる行の 非負の生成系（エビデンス）と残余を生成できる非負の 生成系にわけ，エビデンス成分が一定以上のものをヒン ト関連行として定め，それ以外のものを捨象すること により，部分行列を作成する．これも基本的には，グラ フ正則化項をＮＭＦに課すことで実現できるが，非エ ビデンス生成系に対しては制約項は定数項となる．つ まり，グラフ正則化は行の一部分に対してのみ働くこ とに注意する． このようにして作成した部分行列は，ヒントに出現 する属性（ヒント属性）とそうでないもの（非ヒント 属性）を列に持つが，列の相関に基づく列の圧縮によ り，ヒント属性で説明できる成分と，非ヒント属性固 有の成分に分解する．これは，手法としては共通空間 法 [3] の特別な場合（偏ＮＭＦ 節 5）として実現でき る．ヒント属性で説明できる成分を座標と持つ空間を 等価空間として定め，この空間における近接性により 非ヒント属性の類似性・局所相関を推論する． なお，以下の形式化においては，ヒントは属性対の 集合とは限らず，互いに素なクリークの集合として与 える．例えば_{f1, f2, f3} であり，fi は相互に類似して いる（fi∼ fjif i̸= j）との制約を表す．特にハイパー エッジがクリークの場合であり，類似性とは同値類で あるとの仮定を置いている．

2

ヒントとハイパーエッジ

非負の M× N データ行列 X を与え，行をサンプ ル，列を属性とする．属性を頂点とするハイパーグラ フを考える．_{F を属性集合，ハイパーエッジ を e}j と して，ヒントを_{E = {e}1, ..., eC} で定める．各 ej は通 常のグラフに展開したときのクリークであり，ejに含 まれる属性全てを類似物としてみなす．_{H はエッジに} 現れる属性の集まりで特にヒント属性と呼ぶ．ヒント 属性の総数を NH=|H| と記す．一般のハイパーグラ フでは異なるエッジ ei, ej が 属性 f∈ F を共有するこ とありえるが，ある観点のもとで，ei∪ ej の全ての属 性が類似物として認識された状態を示し，よって，一 つのエッジとして与えられると仮定する（類推におけ る類似関係を同値関係とみなすことと等価）．この仮 定のもとに，異なるクリークは互いに素となる．

3

ヒントが導入する近接性制約と偏

ＮＭＦ

ヒント属性 fi, fj が同一のエッジに帰属するときに Sij= 1，そうでないときに Sij= 0 とする NH× NH の類似行列 S = (Sij)ijを与え，そのラプラシアン (un-normalized) L = D− S を考える．D は次数行列であ る．このとき，KE× NH 行列 E の列ベクトルでヒン トの KE 次元の座標を表現させるが，同一のエッジに 帰属するヒント属性間の２乗距離総和をできるだけ小 さくする制約を課す．すなわち， 1 2 ∑ e_∈E ∑ fi,fj∈e ||fi− fj||2= Trace(ELEt) もとのデータ行列 X の列をヒント属性に制限した行列 を，同じ X で記す．X の各行のヒントとの整合性を 測るために，ヒントのエビデンス成分と非エビデンス 成分の線形和で各行を表現する．そのために，エビデ ンス成分の次元 KE，非エビデンス成分の次元を KY として，行の（圧縮）生成系を (K = KE+ KF)× NH 行列として求める．特に，KE× NH部分行列 E に対 する２次形式総和ができるだけ小さくなることを要請 する： min   X− A ( E F ) 2 + λTrace(ELEt)   － 3 －

ここに，F は (KF = K− KE)× NH 行列で，「非エビ デンス行の圧縮」である．A は M_{× K の係数重み行} 列で，各行の最初の KE個 の要素の並びが各行が持つ エビデンス座標，残り KY 個の係数が非エビデンス座 標である．また，λ は正則化項に対するラグランジェ 定数である． グラフとしてのヒントは，互いに疎なクリークと定 めたことにより，ヒント属性を適当に再配置すると，（列 をヒント属性に制限した） X は X = ( X1 · · · XC ) . C はクリーク数 ( E Y ) = ( E1 Y1 · · · EC YC ) と書ける． また，ラプラシアン L も，各クリーク ec に対するラ プラシアン Lc に対し， L =    L1 . ._. LC    と書ける． この変形を用いて目的関数を書き換えると C ∑ c=1   Xc− A ( Ec Fc ) 2 + λTrace(EcLcEct)   となり，クリーク毎に独立した最適化により実行可能 なことがわかる．さらに，グラフをクリーク集合に単 純化したことにより，ＮＭＦの更新式は下記に示すよ うにより簡略化される．簡単のために，Xc, Ec, Fc を X, E, F と略記し， ( E F ) の列ベクトル f = ( z y ) 単位 の更新式を考える．さらに，v を f と同じ位置にある X の列ベクトルとする． A = ( A1A2 ) . A の更新は標準ＮＭＦ z = z• A t 1v + λΣzj̸=z zj At 1A1z + At1A2y + λ(C− 1)z . y は固定 y = y• A t 2v At 2A2y + At2A1z . z は固定

4

等化空間とその補空間

さて，前節でエビデンス生成系 E が得られ，それを 列でみると，各クリーク内の属性は近接した列ベクト ルとなることが期待できる．したがって，基本的にはこ れらのクリーク内の列ベクトルを平均化した列ベクト ル（丁度クリークの数）を以下固定し，斜交基底として 用いる．この基底に関する座標空間を「等価空間」と呼 ぶ．一方，残りの非ヒント属性数は少数であるとは限 らず，列に関する圧縮を行った方が経験則としては良 い結果をもたらすであろう．等価空間基底を固定した 形で非ヒント属性の圧縮を行うことにより，等価空間 座標，「補空間」とその補空間座標を全てＮＭＦで求め ることができる．節 1 で述べたように，部分空間法の 特殊形である 偏ＮＭＦで求める．具体的には，転置を 行い，(EΦ)t を E，Gt _{を F , B}t₌( (B(E)t _(B(G)₎t ) を A に見たて，前節における y の更新式（E を固定 し F を更新）を用いれば良い． min F− (EΦ G) ( B(E) B(G) ) 2 但し，Φij = { 1/|ej| if fi∈ ej 0 ow G は KE × (KF − C) 行列で，その列が補空間の斜 交基底をあらわす．KF は列全体の圧縮次元である． B(E) _{と B}(G) _{の列 は，それぞれ，等化空間および補} 空間における 非ヒント属性の座標を表す．目的関数は ||F − (EΦB(E)_{+ GB}(G)_)||2 _{と書けるので，ヒントに} 照らした成分とそうでない成分の線形和の形で非ヒン ト属性を表現し，前者が近接しているときにヒントに 照らした相関性を認める．すなわち， 局所相関推論： B(E) _{= (f} NH+1 · · · fN) とする． このとき，非ヒント属性 fNH+i と fNH+j が近接する ときのみ，属性 fNH+i と fNH+j は所与のヒントに照 らして相関．

5

偏 ＮＭＦ

最後に 偏ＮＭＦについて説明をしておく．簡単のた め，この節では ＮＭＦの原論文 [7] の記法に合わせて 説明する． F = v− W ( h(c) h(v) ) 2 _{ただし，v, W ，h}(c)_は固 定し，h(v)_{が更新の対象} となる可変箇所とする 定数部分 h(c) _{の次元を S とし，h}(v)_{を変数化したも} のを x = (xi)iと記すと，目的関数は F (x) である． Fxi(x) =−2(W t_v) S+i+ 2(WtW h)S+i, ただし，h = ( h(c) h(v) ) は更新前のベクトル Fxixi= 2(W t_{W )} (S+i)(S+i) xi のみを変数化した場合の Fiを同じ Fiで表記し，そ のテイラー展開における２次の項を (WtW h)S+i h(v)_i (x− h(v)_i )2 － 4 －

で置き換えた関数 Gi(xi, h (v) i ) は Fi(xi) の補助関数と なる．W および 相関行列 Wt_{W をそれぞれ} W = (W(c) _W(v)_), Wt_{W =} ( A1 A2= At A B ) に分解すると，補助関数の２次の項は下記で表記できる． (Bh(v)+ Ah(c))i h(v)_i (x− h(v)_i )2 特に B は可変部分に関する相関行列であり，標準ＮＭ Ｆの補助関数と比較すると，定数項 (Ah(c) )i を足しこ むだけの違いしかない．一方，F (x) の補助関数として は同じく F (x) の２次の項 (x− h(v)₎t_{B(x− h}(v)_{) を} (x− h(v))t  K = ( δij (Bh(v)+ Ah(c))i h(v)_i ) ij   (x − h(v) ) で置き換えた関数 G(x, h(v)_{) は多変数関数としの F (x)} の補助関数となることがわかる．その検証は，標準Ｎ ＭＦのときとほとんど同じで，定数項 (Ah(c)₎ i を足し こんでも K− B が半正定値行列となることを確認す るだけで済む．あとは，_{∇G(x, h}(v) ) = 0 を解き，ベ クトルに関する更新式を行列に対する更新式として纏 めて書けば十分である． V − W ( H(c) H(v) ) 2 に対し H(v)_{の更新式は，} H(v)= H(v)• (W (v)₎t_V BH(v)_{+ AH}(c).

6

今後の課題

本稿では比較的少数のヒントから，ヒントに照らし た非ヒント属性間の相関を，ヒントのエビデンスで条 件づける形で求める考えを述べた．局所相関関係にあ る属性は互いに素なクリークとの仮定を置いているが， オーバラップするクリークになっている場合も，ヒント 属性が増加するほど生じると考えられる．学習の立場 から言えば，ハイパーエッジが互いに交差することを 意味しており，データ数の多さからそうした複雑な状 況も学習によりうまく対処できると考えられよう．本 稿で論じた局所相関推論においては，複数の典型的か つ代表的とユーザが感じる関係データを与え，等価空 間における座標の近さでオーバーラップする属性群を， 局所クラスタ―や（疑似）クリーク等により求めるこ とを意図している．大規模データからの学習という現 代的アプローチとは真逆であるが，少数の例題から学 習・汎化できる能力も知性の証左であり，追求する意 義はあると考えている． とはいえ，相関関係データがあまりにも少数である がゆえに，推論性能が思わしくない場合は，ヒントの 拡大推論（クリークの各頂点と結合度が高いものを疑 似クリークとして拡大して与える）などの前処理が必 要になる可能性もある．ただし，エビデンス成分を求 め，ヒントと関連しないものを捨象する操作によりヒ ントの拡大推論そのものが等化空間における近接性に より実現できている可能性も高い．ここらへんの事情 は，ロール・格関係まで考慮したデータ行列，信号デー タの特徴量から構成したデータ行列等々，実験を重ね ながら見極める予定である．

参考文献

[1] Mary B. Hesse: Models and Analogies in Science, University Notre Dame Press (1966).

[2] R. Greiner.“Learning by understanding analogies”. Ph.D.Thesis, Stanford University (1985).

[3] S.K. Gupta, D.Phung, B.Adams, T. Tran and S. Venkatesh: Nonnegative Shared Subspace Learn-ing and Its Application to Social Media Retrieval, KDD’10, 1169 – 1178 (2010).

[4] D. Cai, X.He, J.Han, T.S.Huang: Graph regularized nonnegative matrix factorization for data representa-tion, IEEE Trans. Pattern Anal. Mach. Intell. , 33(8), 1548-1560 (2011).

[5] H. Zhai, M. Haraguchi: A Linear Algebraic Inference for Feature Association, 12th KICSS, IEEE CPS, 102 – 107 (2017).

[6] ジェイ ホンジェ・原口 誠・今井 英幸：ヒントによる局

所相関推論，人工知能学会全国大会(第32回)論文集，

1P3-03 (2018).

[7] Lee, D. D. and Seung, H. S.: Algorithms for Non-negative Matrix Factorization, NIPS 2000, pp. 556 – 562 (2000).

[8] Sun, L., Ji, S. and Ye, J.: Hypergraph Spectral Learning for Multi-Label Classification, 14th KDD, pp. 668 – 676 (2008).

[9] Ganter, B. and Wille, R.: Formal Concept Analy-sis - Mathematical Foundations, 284 pages, Springer, 1999.

[10] T. Taniguchi and M. Haraguchi: Discovery of Hidden Correlations in a Local Transaction Database Based on Differences of Correlations, Engineering Applica-tion of Artificial Intelligence, 19(4), pp. 419 – 428, Elsevier, 2006.