#1 Text Classification from Labeled and Unlabeled Documents using EM

Kamal Nigam, Andrew McCallum, Sebastian Thrun and Tom Mitchell.
Machine Learning, 39(2/3). pp. 103-134. 2000.

少数のラベルありドキュメントと大量のラベルなし文章で文章分類。学習器は主にNaive Bayes(以下NBと書く)を利用している。最初はラベル付きだけで推定することもあって、Laplace smoothingを採用。基本的には以下をパラメータが動かなくなるまで繰り返す。

  • 作ったNBでラベルなしデータに確率を付与
  • 前からラベルが付いていたデータとさっきラベルを付けたデータで新たなNBを構成

これだけだとなんとなくな感じ(?)だからちゃんとEMの枠組みに乗せてあげる(そうすることによって単調増加が保証され、局所最適であるところに辿りつける)。まず、完全データの尤度((8)式)を定義。基本的には、ラベルなしの尤度とラベルありの尤度のかけ算。ラベルありのほうはラベルが確定しているので、混合要素の部分の和の計算が書いてないことに注意が必要。これとpriorのかけ算であるposteriorの対数の最大化を目指す。しかし、隠れ変数があったほうがEMとして扱いやすいので、取り入れる。(10)式のように隠れ変数を導入し、ラベルありとなしを同じように扱う。あとは普通のEMで動かす。

しかし、ラベルなしデータが少なければうまくいくが、ラベルなしデータが多すぎると逆に悪化するというようなケースがある。これを改良するための方法をこの論文では2つ提案している。

  • ラベルなしデータにweightを付けてやる(5.3.1)
  • 混合要素とクラスには一対一の関係があるという制約を取り外す(5.3.2)

ラベルなしデータにweightを付ける

ラベルなしデータがあまりにも多すぎると逆効果になるときがあった。EMのパラメータ推定がラベルなしデータに大きく左右されすぎるのが問題。そこでラベルなしデータの影響力(主に小さくするのが目的)をコントロールするパラメータ\lambda (0 \leq \lambda \leq 1)を導入してやる。更新式はあんまり変化しないが、実験では結果が改善されたと書いてある。\lambdaの推定にはleave-one-out cross-validationを使ったらしい。

混合要素とクラスには一対一の関係があるという制約を取り外す

具体的にはクラス:混合要素=1:多という風に仮定を外してやる。混合要素はトッピックとして考えることができる。例えばスポーツのサブトピックとしてホッケーとベースボールのような。このようにサブトピックを設けることで、"bat"と"base"は共起しているというような関係を捉えることが可能となり、推定の精度が上がることが期待される。

ただし、推定するものとしては多少増える。ラベルgivenのもとで、どの混合要素(topic)に属する(components membership of each document)かというものも推定しないといけなくはなる(文章はどの混合要素から来ているか)。推定の方法としては相変らずEMでMステップは変化がないが、Eステップに変化がある。以前はドキュメントgivenのでのクラスへの確率は(ラベルありだったので)0か1だったが、この場合は0から1まで自由に動くことができるようになる。ちなみに、混合要素(topic)の数はcross-validationで決定すると書いてあった。

アルゴリズム全体の流れとしてはTable 2を見るべし。どう見ても言語モデルにおけるトピックモデル的な進化をしていきそうな感じである。。。