ビッグデータ時代のサンタ狩り - ML Advent Calendar 2013 最終日

Machine Learning Advent Calendar 2013 の最終日を担当します @sleepy_yoshi です．
ふだんはブログ記事をである調で書いていますが，なんとなく今日はですます調で書きます．あとクリスマスのノリで適当なことを書いているので，ネタをネタとしてとらえていただければと思います．

更新が遅くなり大変申し訳ありません．今年もサンタ狩りに参加していた結果，太平洋上空に逃げたサンタクロースを追いかけてサモアまで来てしまいました．残念ながらサンタを逃してしまったところです．というわけでこのブログ記事はサモアより更新しています．まだこちらはクリスマスです．

．．．というブログ記事をクリスマスに書いていたのですが，サモアでは通信環境を確保できず，日本に帰国したらこんな時間になってしまいました．

さてオオトリをおおせつかったわけですが，プレッシャーでお腹が痛いです．当初は初心者にもわかりやすくVC理論の素晴らしさを紹介し，Vapnik教を布教したかったのですが，聖夜ということもあり宗教戦争を起こしかねないのでやめました．そもそも自分自身がVC理論をちゃんと理解していません．また，人口が集中している都市部におけるサンタクロースの最適配置問題を今流行りの劣モジュラで解くという話をしようかとも思ったのですが，劣モジュラとかやっぱりよくわからなかったのでやめました．

さて最終日の今日は，このビッグデータ()時代におけるサンタ狩りへの機械学習適用について考えてみたいと思います．大量のデータが利用可能になっている*1といわれている昨今ですが，すべてのデータにラベルづけするのは困難であり，教師あり学習そのままでは，データの増加の恩恵を受けることができません．しかし，ラベルなしデータをうまく使うことができれば，ビッグデータ()の恩恵を受けることができます．

機械学習でいうところの半教師あり学習というアプローチを解説したいと思います．具体的には半教師あり学習の中で混合モデルと呼ばれるアプローチの説明を行います．ただし，手法自体は10年以上前に確立されており，内容としては古いです．今回，混合モデルによる半教師あり学習の解説を選択した理由は混合モデルによる半教師あり学習は，教師なしの混合モデル推定の特殊ケースとして説明できるので，やや混合分布やEMづいている(cf. 8日目，15日目) 今回のML Advent Calendarにふさわしいと考えたためです．

たぶんML Advent Calendarの読者の多くの方は知っている内容だと思うので，その場合にはそっと画面を閉じてください．

はじめに

近年，サンタクロースが増加の一途をたどっています．免許制が施行されてから世界中に公認サンタは増加しており，またクリスマスが近づくと，色めく街に一時的に雇われた傭兵サンタや無免許サンタもはびこります．聞いたところによると，子どもを持つ父親が仕事中に急にスーツを脱いでサンタの衣装に着替えて「靴下にアレを入れないと靴下にアレを入れないと」と意味不明の発言をして仕事を投げ出して帰宅する事案が報告されています．その他「メリークリスマース！」と叫びながらカップルをどついて回る辻斬りサンタも報告されています．

このようなサンタクロースの急激な増加は社会問題になりつつあると，専門家は指摘しています．戦う企業人であるお父さんがサンタ化することにより，会社業務や取引が停滞することで日本のGDP減少に影響を与えます．また，辻斬りサンタは暴力的な行為を行うため，治安の観点からも人々に不安を与えています．

サンタ化する人々は人狼のように自分がサンタクロースになっていることを自覚していません．自覚症状がないため，自然にサンタを減らすことが難しいという問題があります．

しかし，悲観することはありません．我々にはサンタバスターズがいます．普段我々があまりサンタの被害を受けていないと思うのはサンタバスターズのおかです．サンタバスターズは，みなさんの目に見えないところで「サンタ狩り」を実施し，人々の不要なサンタ化を抑制しています．日本，いや世界を守っているわけです．サンタバスターズについては政府の最高レベルの機密情報であり，秘密保護法に抵触するため，残念ながら詳しい話はできません．

我々も何かしらサンタバスターズのお役に立ちたいと思い，サンタ狩りのいちタスクである「サンタ判別」を機械学習によって高精度化することを目指します．

サンタバスターズの朝は早い。サンタは一見すると一般人の様子をしており、本人にもその自覚がないためだ．クリスマスシーズンが近づくとサンタバスターズは子どもがいる家庭の張り込みから開始する．ゴミ出しの時間帯が始まるとサンタバスターズはゴミ袋の中からレシートを探す．ド○キホーテでサンタの衣装など購入していないか確認するためだ．けしていかがわしい目的のためではない．このような理由から変質者として通報されることも少なくない．このようにサンタバスターズは (社会的な意味で) 命がけの行動によってサンタ狩りを実施しているわけだ．
(民明書房刊「聖夜を狩る者・狩られる者」)

それでは半教師あり学習の中でも混合モデルのアプローチについて紹介したいと思います．混合ガウスモデルフィッティングを理解していれば，その特殊ケースとして理解できます．

今回のML Advent Calendarでも8日目と15日目にEMアルゴリズムの素晴らしい解説があるので，これをお読みの方はきっと混合ガウスフィッティングのEMアルゴリズムによる推定は理解していると思います (ニッコリ)．

まぁ混合ガウスモデルを理解している人は，すでにこれから話す内容を理解している可能性も高いのですが．．

まずはいったん理想的な状況を想定し，ラベルありデータが十分に利用可能な場合 (ケース0) にどうするのかということにいったん触れてから，ラベルありデータが一切利用できない状況 (ケース1) を説明し，その特殊ケースとして一部ラベルありデータを利用可能な状況 (ケース2) において半教師あり学習が可能であることを説明したいと思います．

箇条書きにすると以下の流れです．

ケース0: 大量のラベルありデータが利用可能な場合 (理想)
ケース1: ラベルありデータが一切利用できない場合 (最悪のケース)
ケース2: ラベルありデータが一部利用可能な場合 (現実的な状況)

準備

まず今回は説明のため*2，かなり極端な仮定をおきます．サンタ，非サンタの判別には体重 (x_1) と年収 (x_2) という2つの特徴が判別に有効であり，かつその2次元特徴空間上で，サンタ，非サンタはそれぞれ固有のガウス分布に従うという仮定をおきます((体重と年収を調べる特徴抽出自体が判別そのものより難しいのではないかということは気にしません)．

したがって，仮にサンタと非サンタの散布図を描くと以下のようなどっかで見たことのあ
るような図になります．今回はサンタは平均=[-2, -2], 分散Σ=[[3,1],[1,3]]のガウス分布，非サンタは平均=[1,1]，分散Σ=[[-2,1],[1,-2]]のガウス分布からランダムに生成した25個ずつのデータを利用しています．少し偏ったサンプル結果が得られるような乱数シードを選択しました．

ケース0: 大量のラベルありデータが利用可能な場合 (理想)

優秀なサンタバスターズたちの手によって十分な数のサンタ，非サンタに対してラベル付与が行われた状況を想定します．この場合には，通常の教師あり学習のアプローチを利用して分類器の構築が可能です．

今回は各クラスが生成される分布を仮定しているので，観測データが与えられた際に事後確率が最大になるクラスに分類する生成モデル (ベイズ識別器とも呼ばれます) による分類を説明します．

ベイズ識別器では，観測データXが与えられた場合に，クラスYの事後確率 $P(Y|\mathbf{X})$ が最大となるクラスを選択します．式で書くとこんな感じです．

$\hat{Y} = \mathrm{argmax}_Y P(Y|\mathbf{X}) = \mathrm{argmax}_Y P(\mathbf{X}|Y) P(Y)$

この予測に必要な情報は， $P(\mathbf{X}|Y)$ と $P(Y)$ です．今回はガウス分布を仮定しているので $P(\mathbf{X}|Y=Santa)$ にはサンタのガウス分布， $P(\mathbf{X}|Y=Non-Santa)$ には非サンタの確率密度関数を利用します．クラス事前分布 $P(Y=Santa)$ はサンタ，非サンタの割合を利用します．

以下の点だけ覚えておけば大丈夫です．

生成モデルの予測には各分布のパラメータとクラス事前分布が必要

さきほどの散布図に事後確率の差の値に基づいて色分けしたのが下図です．ちょうど0の値である薄いきみどり色の部分が分離線になります．この図では $P(\mathbf{X}|Y)$ に対応する2つのガウス分布のパラメータは25個ずつの観測点から最尤推定しました．カラープロットは密度関数の値の差を表しています．カラーバーが表す0の値がちょうど分類結果が変化する点です．

このようにデータ点に対して十分な数のラベルが付与されていれば，我々はサンタの分布，非サンタの分布というように別々に分布パラメータの推定が可能となり，その結果を使って分類することができます．

参考までにデータを生成した元の分布で色分けした場合には下図になります．

サンプル数が少ないため，真の分布と最尤推定でフィットした分布の形がかなり異なることがわかりますね．

少し余談になりますが， $P(\mathbf{X}|Y)$ のパラメータ推定に今回はきちんと共分散を考慮したガウス分布のフィッティングを行っています．たとえば，共分散が0であるようなガウス分布を考えると，多次元ガウス分布は1次元ガウス分布の積で表現できます．

2次元ガウス分布の場合ですとこんな感じです．

$N(\mathbf{X}; \mathbf{\mu}^{Santa}, \Sigma^{Santa}) = N(x_1; \mu_1^{Santa}, \sigma_1^{Santa}) N(x_2; \mu_2^{Santa}, \sigma_2^{Santa})$

共分散が0ということは，特徴空間の各次元が独立であるということを仮定しており，これはいわゆるナイーブベイズ仮説というやつです．ML Advent Calendar 20日目でも紹介されていますよね．ナイーブベイズはテキスト分類の文脈で利用される場合が多いためか，離散分布とセットで説明される解説が多いですが，ガウス分布のような連続分布でももちろん利用可能です．

この記事の最後にナイーブベイズを利用した半教師あり学習についても一言触れますが，それまで基本的にナイーブベイズのことは忘れて大丈夫です．

ケース1: ラベルありデータが一切利用できない場合 (最悪のケース)

さてデータに対するラベルは誰が付与するのでしょうか? サンタのラベル付けには高度な技術が必要となり，なかなかラベルを利用することができません．

そこでまず極端な状況としてラベルありデータが一切利用できない状況を考えます．そのような場合においてどうするかということを考えます．幸いなことに今回は「体重と年収」という特徴空間においてそれぞれ固有のガウス分布に従うという知識が利用可能とします．ただし，それぞれのガウス分布のパラメータ (平均，分散) や事前分布 (混合比) はわかりません．

与えられた知識を利用すると，データ集合に対して混合数2の混合ガウス分布フィッティングをすることによって，なんとなくサンタのガウス分布，非サンタのガウス分布を推定できそうな気がします．

ではやってみましょう．みなさん耳タコの混合ガウス分布フィッティングは，EMアルゴリズムで推定すると以下のアルゴリズムで推定できます．

 Algorithm: 混合ガウス分布フィッティング
     INPUT: ラベルなしデータU, 混合数K
    OUTPUT: K個のガウス分布パラメータ，混合比

1: K個のガウス分布パラメータを適当に初期化する
2: 収束するまで以下のEステップ，Mステップを繰り返す
3:   Eステップ:
       現在のパラメータを用いてUに含まれる全データについて
       K個のガウス分布から生成されてるっぽさ (負担率) を計算する
4:   Mステップ:
       推定された負担率を用いてK個のガウス分布の平均，分散と混合比を推定する．
       混合ガウス分布の場合，負担率を重みとした重みづけ平均，重みづけ分散となる．

ポイントは「各データ点についてどの分布に属しているかわからないため，各分布に属している具合を表す負担率を計算し (Eステップ)，その負担率に基づいて分布パラメータを再計算する (Mステップ)」ということです．

混合ガウス分布フィッティングによって2つのガウス分布は推定できましたが，このままではどちらがサンタでどちらが非サンタかわかりません．たとえば，そこに事前知識として「サンタは非サンタに比べて体重も年収も多い」という知識が利用可能な場合には，ラベルを一切利用せずに生成モデルの分類器を構築することが可能です．すなわち分布に対する知識が十分にあれば，事例に対応するラベルは必ずしも必要ないということです．

(脱線ここから)

少し横道にそれます．予測問題を機械学習を用いて解こうとすると，正解ラベルを用意して教師あり学習を用いるンだ，という考え方をしてしまいがちですが，必ずしもそれだけではありません．上述の例のように，問題に対して人間サマが持っている知識を整理して，それらの知識をフルに活用できる形で適用するべきだと考えています．

奇しくも本日最終回を迎えた機械学習はじめようの最終回でも「機械学習を使わずのすすめ」という話題がありました．人間サマの知識を直接活かせる手段があるならば機械学習は使わなくてもよい，というように解釈すると，さきほど申し上げたように人間サマが持っている知識を軸に考える点において同じ考え方だと思っています．

(脱線ここまで)

さきほどのデータについて2混合ガウス分布フィッティングを行った結果を示します．いずれもEMアルゴリズムによって得られた局所解における結果です．わかりづらいですが，各データ点の色が負担率を表しています．また，カラープロットにおいて色が濃くなっているところがガウス分布の密度が高いところです．2つのガウス分布の密度の差に基づいてカラープロットしたので，赤色が濃いエリアと青色が濃いエリアで2つのガウス分布の山を表現しています．

(a)の結果が一番まともです．(b)もなんとなく許容できる結果です．しかし，(c)や(d)はなかなかアナーキーな結果ですね．今回のケースでは，(a)の対数尤度が最大になっており，一番よい局所解を選ぶだけで(a)の結果を選択することができます．しかし，今回は2つの異なるガウス分布からサンプリングされたデータを用いているということもあるので，必ずしも対数尤度の最大化が一番良いフィッティング結果を生み出すとは限らないということを補足しておきます．混合ガウス分布の場合は特異性の問題もありますしね．

ケース2: ラベルありデータが一部利用可能な場合 (現実的な状況)

さて現実的な状況としては，ラベルありデータが一部利用可能であり，ほとんどの観測はラベルなしデータであるという状況が自然です．このような場合には，どんなアプローチが取れるでしょうか?

通常の半教師あり学習では，"ラベルありデータに加えて" ラベルなしデータが利用可能である，というような流れで解説されることが多いですが，今回は逆にラベルなしデータが大量に存在している状況において，"一部のデータにラベルが付与されている" というように解釈して話を進めましょう．

そう考えると，基本的にはケース1の状況と変わりません．やはり2つのガウス分布であるという知識を利用して，混合ガウス分布フィッティングを考えます．

異なる点は一部のデータについては真のラベルがわかっているという点です．さきほど「各データ点についてどの分布に属しているかわからないため，各分布に属している具合を表す負担率を計算し (Eステップ)，〜」という説明をしました．しかし，ラベルが付与されたデータについてはどの分布に属しているかわかっています．そのため，負担率を計算する必要がありません．

ラベルありデータについては負担率は固定できる．

ということです．

ではその部分だけ変えて半教師あり混合ガウスフィッティングを考えてみましょう．アルゴリズムに直すと以下のとおりになります．

 Algorithm: 半教師あり混合ガウス分布フィッティング
     INPUT: ラベルなしデータU, ラベルありデータL (new!), 混合数K
    OUTPUT: K個のガウス分布パラメータ，混合比

1: Lを用いてガウス分布のパラメータと混合比を推定する．(new!)
2: 収束するまで以下のEステップ，Mステップを繰り返す
3:   Eステップ:
       現在のパラメータを用いてUに含まれる全データについて
       K個のガウス分布から生成されてるっぽさ (負担率) を計算する
       ラベルありデータLについては負担率を指定されたクラスに固定する (new!)

4:   Mステップ:
       推定された負担率を用いてK個のガウス分布の平均，分散と混合比を推定する．
       混合ガウス分布の場合，負担率を重みとした重みづけ平均，重みづけ分散となる．

何が違うかわかりますか? 変わった部分に(new!)と付けてみました．さきほど言ったようにラベルありデータについては「負担率を固定して」Eステップ，Mステップを計算していることがわかります．

PRMLのEMアルゴリズムの説明のところで完全データ，不完全データという言葉が出てきたと思います．教師なしの状況においてはすべてのデータが不完全データですが，半教師ありの状況においては，一部のデータは完全データとして存在するわけです．

改めて言われるまでもなく「そりゃそうだ」という感じですよね．

一部のラベルありデータを利用した場合の混合ガウス分布推定の可視化結果は以下のとおりです．

今回は○で囲まれた各分布3つずつのデータにラベルを付与しました．さきほどの混合ガウス分布フィッティングの結果(a)と変わっていません．しかし，今回の場合にはガウス分布パラメータの初期値がラベルありデータによって決定されるため，(b)-(d)のような結果になることはありません．

本当はラベルを一切使わない状況に比べてよい結果が得られることを示したかったのですが，すべての図を作り直す必要があるためあきらめました．

さて，それでは「ラベルありデータだけ」を利用した場合にはどうなるでしょうか．ケース0においてラベルありデータが6つだけ利用可能な状況です．ラベルありデータのみを用いてガウス分布パラメータと事前分布 (3つ3つなので0.5, 0.5) を最尤推定しています．

こちらはわかりやすく悪い結果になってくれましたね．少し離れた点に対して非サンタラベルを付与しているため，ガウス分布の分散パラメータが大きく推定されました．サンタクラスについてはそれなりにまとまっているデータ集合にラベルが付与されているため，ガウス分布の分散パラメータは小さめです．その結果，事後分布P(Y|X)がひっくりかえる線がへんなところに存在しています．

おわりに

本日は半教師あり学習の一手法である混合モデルについて，混合ガウス分布を例に挙げて教師なしの混合分布フィッティングにおいて，負担率計算の部分を与えられたラベルで固定する，という流れで説明しました．

Nigamら[1]は，テキスト分類における混合分布の半教師あり学習を適用を提案しています．一言でいえば半教師ありナイーブベイズです．Nigamらは分布として多項分布を利用しています．多項分布にナイーブ仮説をすることによって，半教師ありナイーブベイズモデルのできあがりです．

ナイーブベイズ->半教師あり，と説明するよりも混合分布フィッティング->半教師ありへの拡張->分布に対してナイーブベイズ仮説適用という流れの説明の方が理解しやすいかなぁと思ったのが今回の記事の発端だったりします．

なお今回は1クラス1分布の仮定を置いていましたが，当然成立しない状況があります．先述のNigamらも1クラスに複数分布を用意する方法について言及しています．さきほど述べたようにサンタにも公認サンタ，傭兵サンタ，無免許サンタ，辻斬りサンタさまざまな種類がありますから，内部に複数の分布を考えるモデルの方が高性能になりそうです．

半教師あり学習にはいろいろなアプローチがあり，混合モデルはその一つです．最初にラベルありデータで分布パラメータを計算してから，EMを回す様子はラベルありデータを使って構築された分類器の予測結果をそのまま新たなラベルとして利用するself-trainingとも似ていることがわかります．

グラフベースの方法ではZhuのGaussian Random Field [2]が有名です．今年ICML2013 Classic Paper Prizeを受賞したことも話題に上がったりしました．グラフベースの半教師あり学習については@niam さんの資料が参考になります．

とたくさんあるのですが，完全にエネルギー切れです．Python+NumPy+matplotlibによる作図にエネルギーを注ぎすぎました*3．

まったくもってオオトリに見合わない内容だと思いますが，参加 (執筆) することに意義があると信じてML Advent Calendar最終日の記事をしめくくりたいと思います．ML Advent Calendar幹事の @naoya_t さん．執筆者のみなさま，読者のみなさまありがとうございました．ここまで読んでくださりありがとうございました!

エピローグ

こうして聖夜は終わり，奴らは去った．しかし，やつらはまた帰ってくる．2014年もサンタとサンタバスターズの戦いは続くのだ! 来年は Google Glass にサンタ判別機能を実装して道行く人々をサンタ判別するネタを書きたいと思います! Ok, Glass! それではみなさんよいお年を!

References

[1] Kamal Nigam, Andrew McCallum, Sebastian Thrun, Tom M. Mitchell, "Text Classification from Labeled and Unlabeled Documents using EM", Journal of Machine Learning 39(2/3), pp.103-134, 1999.
[2] Xiaojin Zhu, Zoubin Ghahramani, John Lafferty, "Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions", ICML '03, 2003.
[3]
Introduction to Semi-Supervised Learning (Synthesis Lectures on Artificial Intelligence and Machine Learning)
- 作者: Xiaojin Zhu,Andrew B. Goldberg
- 出版社/メーカー: Morgan and Claypool Publishers
- 発売日: 2009/09/15
- メディア: ペーパーバック
- 購入: 1人クリック: 52回
- この商品を含むブログ (9件) を見る
- たぶん一番平易に書かれている半教師あり学習の解説本．
[4]
Semi-Supervised Learning (Adaptive Computation and Machine Learning)
- 作者: Olivier Chapelle,Bernhard Schoelkopf,Alexander Zien
- 出版社/メーカー: The MIT Press
- 発売日: 2010/03/31
- メディア: ペーパーバック
- 購入: 1人クリック: 4回
- この商品を含むブログを見る
- いろんな論文をまとめて本にした感じ．Nigam論文もほぼそのままで掲載されている

*1:本当でしょうか?

*2:魔法の言葉．なんでも思い通りの世界を描くことが許されます．

*3:使い方に癖があるが，慣れてしまえば図の作成を自動化できるので大変便利．カッコイイ図が簡単にできます．