Introduction

　こんにちは、k_oomoriです。今回は非負値行列因子分解 (Non-negative Matrix Factorization, 略してNMF) を用いたデータの解析について触れてみたいと思います。

　まず最初に用語の定義として、「非負値行列」とは全ての要素が非負値（0以上の実数）であるような行列を指すこととします。これを用いると、NMFとは「与えられた非負値行列 $V$ を2つの非負値行列 $W$ と $H$ の積に（近似的に）分解するアルゴリズム」

と表現できます。これにより、なんと $V$ の中に潜んでいる特徴を抽出することができるというのです！これについては後ほど説明します。

　ひとまずは $V$ の具体例を見てみましょう。いくつかのニュース記事の中に特定の単語がそれぞれ何回現れるかを数えるという状況を想像してください。例えば記事が3つ、対象とする単語が5つの場合、出現回数を次のように並べることができます。 f:id:fan_k_oomori:20160506125639p:plain
上記の例では、記事Aの中に単語1が2回、単語2が0回、…、記事Cの中に単語5が3回現れたことを意味しています。出現回数が負になることはありえないので、これは3×5の非負値行列になっています。このようなデータに対してNMFを適用すると、記事をうまく分類できるという結果が得られています。
　他にも顔画像に対してNMFを適用すると、顔のパーツをうまく抽出したりできるようです。

なぜ特徴を抽出できるのか？

　ここに3人のユーザ(A,B,C)、4つの広告(a,b,c,d)があり、各人が各広告をクリックした回数が次の非負値行列で与えられるとします。 f:id:fan_k_oomori:20160506125645p:plain
実はこれは次のように分解できることがわかります。
単に「特徴1,2,3」とか言っても感覚が掴みにくいので、特徴1=アイドル、特徴2=電子書籍、特徴3=ソシャゲとしてみましょう。すると(4)の第1因子から、ユーザAはアイドル2:電子書籍1くらいの興味があり、ユーザBはアイドルにしか興味がなく、ユーザCはソシャゲにはまっている人と解釈できます。第2因子の方は、広告aがアイドル全面推し、広告bはアイドルをフィーチャーした電子書籍、広告cは純粋ソシャゲ、広告dはアイドル風味のソシャゲとなります。このように人・広告ごとの特徴を捉えた後で(3)を見てみると、ああ、アイドル好きなユーザBがアイドル広告aを9回もクリックしたんだなとか、ソシャゲ廃人Cはソシャゲ要素のない広告a,bには見向きもしないんだな、といったことが読み取れます。
　今のは各因子が与えられたとしてそこから掛け合わせた行列の値を見るという方向でしたが、これを逆に辿ると、単なるユーザ×広告のクリック数のデータでしかなかったものから何か特徴のようなものを引き出せることが期待できるのがわかるでしょう。なお、その「特徴」が一体何であるかについては、人間が考察しなければわかりません。

乗法的更新アルゴリズム(Multiplicative update rule)

　では与えられた $V$ から $W$ と $H$ を近似的に求めるアルゴリズムに進みましょう。まず、(1)を満たすような $W$ , $H$ を見つけようとしているので、2つの行列（ここでは $V$ と $WH$ ）がどれくらい近いかを判断する基準が必要になります。ここではコスト関数として、各成分の2乗和（いわゆる行列のFrobeniusノルム）を採用します。

Ref.[2]で示されているように、ノルム(5)は以下の乗法的更新ルールの下で非増加 (non-increasing) です。^※1

つまり、 $W$ と $H$ の初期値を適当に（ランダムでよい）用意し、(6)を何度も繰り返し適用していけば、 $WH$ が $V$ に近づいていくのです！

　さてこれまで $V$ を $W$ と $H$ に分解するという話をしてきましたが、行列のサイズ（行数、列数）はどうなるのでしょう？ $V$ のサイズは与えられたデータ量によって決まります。ここでは $V$ の行数を $n$ 、列数を $m$ と置くことにします。

$WH$ と $V$ を比較しているので、 $W$ の行数は $n$ 、 $H$ の列数は $m$ となります。また $W$ と $H$ の積を考える以上、 $W$ の列数と $H$ の行数は同じ（ここでは $r$ と置きます）でなければなりませんが、それがいくつになるかは一意的には決まりません。これは、抽出されるべき特徴の数を人間が推測して与えるか、または $r$ を調整されるべきパラメータとして扱うべきであるということを意味します。
　ここで(1)の両辺の要素数を計算してみましょう。左辺は明らかに $nm$ です。右辺は $nr+rm=r(n+m)$ となります。今やりたいことは、膨大な元データ( $V$ のこと)の中からある程度少数の特徴を発見して整理しようということなので、

を満たす、言い換えると $r$ は $n$ と $m$ のうち小さい方と同程度かそれ以下の大きさであることが望ましいです。逆に $r$ が小さすぎる場合、動かすことができるパラメータの量が減ってしまうので、コストを十分に小さくできない可能性が高くなります。
　以上をもとに、実際にアルゴリズムを走らせ、コスト値の収束性や $r$ 依存性を見てみましょう。テストデータとして $948\times 239$ 行列を用意し、100回のイテレーション（繰り返し）を行った例を以下に示します。 f:id:fan_k_oomori:20160506131946p:plain
NMFの収束性。横軸：イテレーションの回数、縦軸：コスト/行列の要素数。

横軸はイテレーションの回数、縦軸はコスト値(5)を $948\times 239$ で割ったもの（つまり各要素ごとに取った差の2乗の平均値）、凡例は $r$ の値を表します。このグラフから、以下のことが読み取れます。

$r$ の値がいくらであっても、50～60回程度繰り返すとコスト値は収束する。
$r$ の値を大きくしていくにつれて、コストの収束値は減少する。これは、動かせるパラメータ（自由度）が多くなるほど $V$ を近似しやすくなることを示す。
$r$ の値が大きいと、ランダムな初期値からスタートしたにもかかわらずコスト値の変動が少ない。逆に $r$ の値が小さいときには極小ではあるが最小ではない解にはまる可能性がある。

　なお、以上の話の中に正方行列は一切出てこず、 $V$ の自分自身との積などは定義されていません。なので今回考えている行列には群どころか半群の構造すら入っていません。正方行列の集合だと何かとトピックが豊富なのですが、今回はただ更新ルール(6)に従って計算するだけなので特に難しいことはありません。^※2

更新ルール(6)に関する注意

　この更新ルール、 $n$ 回目のイテレーションによって得られる値を $W_{(n)}$ , $H_{(n)}$ と書くとき、私は最初てっきり

の意味かと思って実装してみたのですが、これでは収束しない！実は f:id:fan_k_oomori:20160506133010p:plain
としなければなりませんでした。摂動論などに馴染んだ（毒された？）私には意外だったのですが、これって普通なんですかね？

実データ解析

　それではいよいよ実際のデータ解析に入ります。今回は元データ( $V$ )としてnendのコンバージョンデータを使用し、広告キャンペーンの特徴による分類を試みたいと思います。データ例はこちらになります。行がユーザ、列がキャンペーンに対応しています。ただ眺めていても一切面白くないですね。しかし、この中に宝が埋まってると期待して採掘を行います。
　まずは $r$ の決定の仕方を考えなければなりません。上記の $V$ は $n=638, m=236$ なので、(8)式より $r\lt 172.3$ という制限がつきます。営業サイドに尋ねたところ、多少細かく分類したとしてもキャンペーンのカテゴリ数は100くらいという意見でしたので、今回は $r=100$ という値を用いることにします。
　イテレーション回数を100として(6)のアルゴリズムにかけた結果、W $\times$ Hという結果が得られました。 $W$ はユーザ×特徴、 $H$ は特徴×キャンペーンの情報を担っているので、 $H$ の方に着目します。
　さて、問題はどうやってこのデータから特徴の似通ったキャンペーンを抽出するかですが、やり方はいろいろあり得ると思います。今回は、各キャンペーン（つまり各列）に着目するとそれぞれが $r=100$ 次元のベクトルとみなせることから、ベクトル間のコサイン類似度を元に値が大きいものを抜き出してみました。ここでは具体的なキャンペーン名を挙げられないのが残念ですが、営業側に確認していただいたところ、一部大手クライアントのキャンペーンには関連性が不明瞭なものがあるものの、概ね納得できる関連性を抽出できているとのことでした。あらかじめキャンペーンに属性情報等を付与したりしたわけでもないのに、多くのユーザがとった行動データからこのような関係性を抜き出せるというのは大変興味深いですね。またこのような「誰が見ても関連ありそう」という情報だけでなく、いわゆる「ビールと紙おむつ」のような未知の価値ある情報を引き出せれば言うことはありません。

Furthermore...

　今回はNMFを用いてキャンペーン間の関連性を調べましたが、某密林よろしく「このキャンペーンでコンバージョンしている人はこんなキャンペーンでもコンバージョンしています」的なことも容易に調べられるので、これらの結果を比較してみる価値はあると思います。
　またグラフ理論的な観点からは各キャンペーンは頂点(vertex)であり、今回はそれらの間のリンクの強さを調べたことになりますが、さらに踏み込んで大域的なコミュニティ構造を調べてみるのも面白いかもしれません。
　最終的にはより効果的な広告の配信につなげていきたいですが、それはまた別のお話。

Summary

　In this article I first illustrated why Non-negative Matrix Factorization (NMF) was expected to reveal some hidden features from users' behavioral data. Then I described the multiplicative update rule and applied it to conversion data in nend to classify ad campaigns based on their similarities.
　Further possible directions would include: (1) study of other methods for finding relationships between ad campaigns to be compared with NMF, and (2) make use of this achievement to develop more effective advertising solutions.

References

[1] D. D. Lee and H. S. Seung, "Learning the parts of objects by non-negative matrix factorization," Nature 401, 788-791, 1999. リンク切れの場合はこちら
[2] D. D. Lee and H. S. Seung, "Algorithms for Non-negative Matrix Factorization," In NIPS, 556-562, 2000. リンク切れの場合はこちら
[3] 集合知プログラミング（書籍）
[4] Non-negative Matrix Factorization（非負値行列因子分解） - あらびき日記

※1. ^ Ref.[2]ではもう一つ別の更新規則も与えられているのですが、そちらでは基準となるコスト関数が拡張されたKullback-Leiblerダイバージェンスという(5)より複雑な表式で与えられるため、今回は(6)のルールを採用することとします。
※2. ^ とかなんとか言ってますが、単にタイトルが言いたかっただけなのは確定的に明らか。