bayesian sets のメモ - valdzone’s blog

以下は自分用の備忘録です。解説というにははしょり過ぎだし、わかっている人には自明すぎでしょうもないものです。

Bayesian Sets がやっていること

Google Sets がやっているようなことを実現するものです。まず、あるアイテム(例えば映画のタイトル)の集合Dに対してその部分集合Dcをあるクラスタであるとみなします。ユーザはDcに属すると思われるクエリ(例えば Police Academy (1984) + Porky's (1981))を与えると、Bayesian sets は全集合Dの各アイテムに対して、そのアイテムがDcに属する確率に比例する数値をスコアとして返します。例えば上記の2本の映画をクエリとして先日実装した Baeysian sets (with Movie Lense データ)に適用してみたところ、その2本が上位スコアの1, 2位となり、つづいて、Weired Science (1985), Weekend at Bernie's, European Vacation(1985)のような映画が上位となりました。これらはいずれも80年代のコメディ映画なので、そのようなクラスタが見えたと解釈できそうです。ちなみに上記の映画のリンク先である imdb のサイトに行くと、（おそらく）協調フィルタリングによるリコメンデーションがついてきますが、Bayesian Sets の結果とは必ずしも一致しないのが興味深いです。もちろん元となるデータセットが違うのに加え、マーケティング的な要素も絡むのでしょうが、アルゴリズムの違いもあるのかもしれません。このあたりいずれ勉強してみようと思っています。さらにちなみに、7作あるポリスアカデミーシリーズの中でも私が一番好きなのは Part II なのですが（これが一番ばかばかしくて笑える)、Part II のみをクエリにすると上位7位までがすべてポリスアカデミー作品になります。なぜか順位は 2, 3, 4, 5, 6, 7, 1 でした。そして8位は我らがポーキーズです。しかし Part I のみをクエリにすると、不思議なことに Part II 以降はランクインせず、他のコメディが入ってきます。これはあのようなバカバカしい映画を Part II以降も見続けるというのは相当にツボに入った人々だけで、そういう好き者の人々による、いわばファンのクラスタが出来ているということかもしれません。Bayesian sets の面白いところは、そのようなクラスタを発見的な方法でマイニングできるというところだと思います。逆にクエリのセンスが悪いとクラスタにはならず、よくわからない結果しか出ないようです。例えばおよそ対照的な人々によって評価されているであろう Scary Movie（最終絶叫計画）とGone with the Wind （風とともに去りぬ）をクエリに選ぶと、後者の名作クラスタに飲み込まれてしまうようで、コメディはクエリ以外ほとんど出てきません。（が、見ようによっては明るげな話の割合が多いかも？下記にランキングをのせておきます）
1: Gone with the Wind (1939)
2: Scary Movie (2000)
3: Casablanca (1942)
4: Graduate, The (1967)
5: Wizard of Oz, The (1939)
6: African Queen, The (1951)
7: Singin' in the Rain (1952)
8: West Side Story (1961)
9: My Fair Lady (1964)
10: Doctor Zhivago (1965)

ナイーブベイズとの違い

まずはナイーブベイズの場合を簡単に書いてみます。単純に考えれば、すべてのxに対してクラスDcに属する条件付き確率 P(Dc|x)を求め、その確率を最大化する順にxを並び替えればいいということになります。ここで問題設定が面白い（と自分が思った）のは、よくあるスパム分類などの場合、ある観測したメッセージxに対して事後確率P(C|x)を最大化するクラスC（=spam or ham）を選ぶこと(MAP)で分類器を構成するのに対し、この問題設定では、クラスは固定（クエリで与える）としたときに、事後確率が大きくなる順（スコアの高い順）にxを並びかえた結果を返しましょうという問題になっているということ。このような問題設定にすることで、クラスをクエリによってオンデマンドに決められるという面白い応用が出てきます。Dcをラベル付きのアイテムで構成すれば、ある種のsemi-supervised learning 的なこともできます。ところで事後確率は尤度と事前分布の積に比例しますが、ナイーブベイズの場合、特徴量x={x1, ..., xJ}が互いに独立であるという仮定をおくことで、
$P(D_C|x) \propt \prod_j P(x_j|D_C)P(x_j)$
のように事後確率を計算できます。ここで問題となるのは尤度と事前分布をそれぞれどのように求めるかということですが、尤度はクエリをラベル付きデータとみなして学習し、事前分布は経験データによって求めるという方法が自然だと思います。しかし、クエリが小さいため学習に必要なデータが十分ではなく、また学習に用いるデータ中には存在しない特徴量が出てくるため、ラプラス補正などの方法で確率を0よりも少し大きい値に修正する必要があります。この補正はよくやる方法なのですが、特に学習データが小さい場合分類精度に影響を及ぼす可能性があります。（実際に計算してみるのがはやそうですが）

そして Bayesian sets でのアプローチですが、細かいことははしょりますが、上記の事後確率を評価するのと同様な値としてP(x|Dc)/P(x)を計算します。この形にする理由は単に計算が楽になるからです。また、尤度P(x|Dc)や事前分布P(x)を評価するのに、ハイパーパラメタを導入することによって、ラプラス補正を施すよりも柔軟なモデルにしているようです。共役事前分布を用いることで計算が楽になります。つまり、
$P(x|\theta_j)=\prod_j \theta_j^{x_j}(1-\theta_j)^{1-x_j}$
のようにxの発生モデルをパラメタθのベルヌイ分布によってモデル化するのですが、このとき共役事前分布P(θj)はαj, βjをパラメタとするベータ分布となります。これらのパラメタをより上の層のパラメタということでハイパーパラメタといいます。これらを使うと
$P(x_j|\alpha_j, \beta_j)=\int P(x_j|\theta_j)P(\theta_j) d\theta_j$
のようにθjを積分消去することができますので、あとはなんらかの方法や基準でハイパーパラメタを定めてやればいいということになります。同様にしてP(x|Dc)もハイパーパラメタで表現することができ、最終的にあるxのスコアS(x)は重み係数
$q_j = \log(\alpha_j^*) - \log\alpha_j - \log\beta_j^* + \log\beta_j$
を用いて、
$S(x)=\sum_j x_j q_j$
のような簡単な計算で求めることができます。

ハイパーパラメタの決定方法

今回の論文の例では、θjはある特徴xj={0,1}が1をとる確率なので、その平均値はE[θj]=E(xj)=mjのように計算すればよさそうです。ところで(θjがしたがうところの)パラメタαj,βjをもつベータ分布の平均値は
$\frac{\alpha_j}{\alpha_j+\beta_j}$
なので、これらが等しいと仮定すると
$\frac{\alpha_j}{\beta_j}=\frac{m_j}{1-m_j}$
という関係が導かれます。これを上記のqjに代入すると
$q_j = \log\frac{\alpha_j+\sum_{x\in D_C} x_j}{\beta_j + N -\sum_{x\in D_C} x_j}- \log\frac{m_j}{1-m_j}$
となりますが、まず第2項はデータの平均値のオッズ比の対数になっています。これは、データにおける特徴jの頻度が高いほど大きな値となりますので、Movie Lense データの例でいうと、ある人(=j)の投票があったとしてもその人が他の映画にも投票しまくっていたら(mjが高い)スコアはマイナスに寄与するという効果を表現しています。逆にあまりたくさん投票していない人の一票の重みは大きくなります。一方第1項は、仮にαj,βjが十分に小さければクエリ集合におけるオッズ比の対数となります。つまり、ある人(=j)がクエリ集合において投票をしているとスコアアップに寄与します。ので、先ほどの効果とあわせると、クエリ集合だけピンポイントで投票しているような人による一票はスコアに大きく貢献します。では残りのα,βは何かということですが、その両者のバランスをとるための因子ととらえるのがよさそうです。mj=αj/(αj+βj)ですので、例えばαj=c mj, βj=c(1-mj)としてもよいはずで、c を大きくとるほど、第1項にはデータの平均値の寄与が増えてきます。つまり、たくさんの映画に投票した人のある映画への一票の重みを増す方向に働きます。というわけで、この問題におけるハイパーパラメタの決定方法は、ある制約（例えばここでは経験データの平均値）を満たしつつ、あとは都合の良いように主観的に決めてしまっているというところでしょうか。主観的に決めることによって、スコアの重み付けのポリシーがある程度柔軟になるというメリットがありそうです。これはナイーブベイズにおいてラプラスの補正項を色々といじくるよりもとても見通しが良い感じがします。・・・のように理解しているのですが、間違えていたら指摘していただけると大変嬉しいです。

ところで上記の投票数が多い人による投票をどのようにスコアに反映するかという話ですが、別の尺度を付け足せたら面白いかもしれないと思い、色々と考えているのですがその話はまたいずれ。

追記:
αj=c mj, βj=c(1-mj)としておけば、クエリ集合上にその特徴が現れなかったとき、重みがちょうど0になるという点はそのようにハイパーパラメタを選ぶ理由のひとつになっていそうです。