新年度第1回の助教の会は
数理6研の
林浩平さんに「Generalization of Tensor Factorization and Applications」というタイトルで話して頂きました。林さんは3月に
奈良先端科学技術大学院大学情報科学研究科で博士号を取得し、4月から
日本学術振興会特別研究員として数理6研に所属しています。
林さんは博士課程の間からデータマイニングにおけるテンソル分解 (Tensor Decomposition) と呼ばれる手法を研究しています。今回は二つの話題を紹介していただきました。前半はノイズにガウス分布を仮定しない多種多様な要素を持つテンソルに対するテンソル分解、後半はテンソルに低ランク性を仮定しないテンソル分解です。
前半のお話は、一昨年の国際会議
ICDM2010で発表[1]された、多種多様な（ヘテロな）要素を持つテンソルに対するテンソル分解です。
図1: ユーザ × 商品 × 時間の3階テンソルとして表現された購買データ
そもそもテンソルというのはテーブル形式のデータを多次元に拡張したもので、例えば、複数のユーザがいくつかの種類の商品をある時刻に購入したという購買データを考えるとユーザ × 商品 × 時間の3階テンソルとして表現することができます（図１）。あるいは、商品の代わりにユーザを複数種類のセンサーが取り巻いているユビキタスコンピューティング的状況を考えると、センサーデータはやはりユーザ × センサー × 時間の3階テンソルとして表現されます。テンソル分解はこのようなデータを低次元の因子行列の積で近似（低ランク近似）することでデータを見やすくしたり、見えていない要素を予測したりするための方法です。
ここでなぜ、データのヘテロ性が問題になるかと言うと、例えば購買データであれば数量、センサーデータではセンサーの種類によって、電子メールの件数などの非負整数値を取るセンサー、位置情報などの実数値を取るセンサーなどがあるからです。このように要素によって異なる種類の値を取るテンソルを近似するための基準はどのように選んだらよいのでしょうか。
図2: 指数型分布の例（ガウス分布、ポアソン分布、ベルヌーイ分布）
この問題に対して、林さんは指数型分布族（図2）に基づく確率モデルを用いて確率モデルの対数尤度を近似の基準として用いることを提案しています。林さんの方法では指数型分布族と対数尤度を用いることで異なる種類の要素を自然に扱うことができます。例えば実数を取る要素であればガウス分布、非負整数値を取る要素であれば分布を使うことができます。指数型分布族は非常に広いクラスの確率分布をカバーする確率分布のファミリーで、図2に示すように関数Ψの選び方で様々な分布を表現することができます。林さんの研究ではD個の観測値の要素ごとに互いに異なる関数Ψを用いて、対数尤度に正則化項を加えたもの
\mathcal{L} =\sum_{d=1}^{D}\left(x_d\mathbf{w}_d^\top\mathbf{z}-\psi_{h_d}(\mathbf{w}_d^\top\mathbf{z})\right)-\frac{1}{2}\|\mathbf{z}\|^2-\sum_{m=1}^{M}\frac{\alpha_m}{2}\left\|\mathbf{U}^{(m)}\right\|_{\rm Fro}^2 +{\rm const.}
ただし、
\mathbf{w}_d = \mathbf{u}_{i_1^{(d)}}^{(1)} \circ \mathbf{u}_{i_2^{(d)}}^{(2)} \circ \cdots \circ \mathbf{u}_{i_m^{(d)}}^{(m)}
を近似の基準として用いています。対数尤度を用いることで、要素ごとに異なる近似の基準の比較が可能になり、自然に組み合わせることができます。
林さんはこの手法を上述のセンサーデータからの異常検知に応用して、複数人からなるグループの行動パターンの異常を検出することに成功したということです。
指数型分布族という抽象的な世界と、多種多様なセンサーデータからの高精度の異常検知という具体課題が密に繋がっているところが非常に面白いと感じました。
後半のお話は、カーネル法を用いたフルランクテンソルの穴埋め手法についてです。既存の行列分解やテンソル分解の手法は背後にあるデータの構造に何らかの“単純さ”（低ランク性）を仮定します。低ランクであるということは実質的に推定すべきパラメータは小さいということで、それによって少ないサンプルからでも構造を推定することができていました。しかし、実問題においては低ランク性の仮定は必ずしも成り立っているとは限りません。そこで林さんはカーネル法を使った、フルランク行列（およびテンソル）に対しても適応できる穴埋め方法を提案しました。
林さんのアイディアは、列間の類似度および行間の類似度を非線形な尺度（カーネル関数と呼びます）で算出し、それらを組み合わせることによって(i,j)番目の要素と(k,l)番目の要素の類似度を表現します。こうすることによって、機械学習でスタンダードなカーネル法と呼ばれる枠組みに沿って欠損データの類推が可能になります。行列・テンソル穴埋め問題においては要素数が多く、カーネル法を適用するには計算量が多くなってしまう傾向がありますが、今回のお話ではクロネッカー積の性質を用いることによって少ない計算量で済むとのことです。
この手法はさらに、与えられた行列（やテンソル）の要素だけでなく行や列に付随した付加情報も用いることができます。行列穴埋めは、例えば「誰（人）」が「何（アイテム）」を買ったというように人とアイテムの関係で構成される二次元配列を対象とします。この際、誰が何を買ったという事実だけでなく、その人がどのような人で買ったアイテムがどのような商品なのかという付加情報も使った方が、「ではその人が他に何を買いたがっているのか」ということを予測しやすくなります。 林さんの手法では、カーネル法の枠組みを用いることで、そのような付加情報を自然に盛り込むことができるそうです。
林さんの手法は
movielensという映画推薦システムの問題に適用され、
mlcomp.orgという機械学習手法の性能を競いあうウェブページで現在も
一位の性能を示しているそうです。（self-reflective-multi-task-GP-* というアルゴリズム)
テンソルという数理的な道具から出発し、実問題で高い性能を示す方法論へつながっている点が大変面白いと感じました。
数理6研助教 冨岡亮太 ＆ 数理5研助教 鈴木大慈
[1] Kohei Hayashi, Takashi Takenouchi, Tomohiro Shibata, Yuki Kamiya, Daishi Kato, Kazuo Kunieda, Keiji Yamada, and Kazushi Ikeda.
Exponential family tensor factorization for missing-values prediction and anomaly detection. In the IEEE International Conference on Data Mining (ICDM'10), December 2010.
