Liu, Bing and Lee, Wee Sun and Yu, Philip S. and Li, Xiaoli (2002).
In Proc. 19th Intl. Conf. on Machine Learning.
これも考えている問題は、少数のラベルありドキュメントと大量のラベルなし(この場合はmixed documentsって書いてあるが)文章で文章分類。この論文ではそれをpartially supervised classificationといい、これを制約付き最適化問題として定式化、good solutionを提案するよという内容。
I-EMやS-EMと呼ばれる手法の元になった論文っぽいです。
理論的な解析
この論文の仕事の一つにエラーの期待値がこれくらいで抑えられるよ、というのを理論的に示したというのがある(ノイズありのケースとノイズなしのケース)。その導出にはVC次元(Vapnik-Chervonenkis dimension)というのが使われているが、この辺はちょっと理解ができない。。。ともあれ、性能を理論的に評価したのはよいことで、この辺に使われている式があとの手法のところで少し関連してくる。
提案した手法
この論文もベースはNaive BayesとEM。特徴的なところが2つほどあって
- 初期の分類器を使って、最も負例らしいと思われる文章を「スパイ」として正例に混ぜる
- EMは基本的に最尤推定なので、過学習がどうしても問題になる。そこで、エラーの確率を推定するような指標をヒューリステックな感じで導入して、それをよい分類器の選択に使う
というようなところ。
I-EM(initial EM)
初期段階では正例にラベル1を、ラベルなしデータにラベル-1を付与する(このアルゴリズムでは初期でもラベルなしを使っている)。あとはまあよくある感じでiterationを回す。気を付けるところとしてはiterationの間ラベル付きデータについてはラベルを変化させない、というところである。
- ラベルなしデータUと正例Pで初期のNBを構成する
- パラメータが動かなくなるまで以下を繰り返す
- ラベルなしデータU中の各文章djについて以下を繰り返す
- 現在のNBを使って、p(1|dj)を計算
- p(wt|1)とp(1)を更新する
- (ここで新しいNB学習器を作っている)
- ラベルなしデータU中の各文章djについて以下を繰り返す
I-EMは正例と負例がきっかり別れてくれるような場合にうまく行く。しかし、境界が際どいところだとうまくいかない場合が多い。そこでS-EMを導出する、とある。
S-EM
ここで問題にされているのは「(正例か負例かを)同定する信頼できる情報を得る方法はないか」ということ。EMの各iterationの終了段階というのはその情報を得るためのよい場所であると書いてある。この論文では正例からラベルなしデータへスパイを送り込むという方法が提案されている。S-EMの方法&コンセプトはこんな感じ。
- 正例の集合PからラベルなしデータUへ"Spy"を送り込む
- Pからs%の正例をSpyの集合Sとする
- SをラベルなしデータUに混ぜる
- Sは本当はPだってことを知っているので、iterationがうまく行っているのかを知る判断材料とできる
S-EMは2つのステップからなる。step 1は以下の通り。
- RN(比較的負例っぽい、というような感じのもの)を空集合とする
- 正例からサンプリングし、それを集合Sとする(Spy)
- サンプリングしてきたものとラベルなしの和集合をUsとする
- 正例からサンプリングしてきたものの差集合をPsとする
- Psを1、Usを-1とラベル付けする
- I-EM(Us, Ps)を使って、NBを構築。Usを分類する
- Sを使って閾値thを決定する
- Usの各文章dについて以下を繰り返す
- p(1|d) < thならRNにdを追加
スパイをなんで送り込んだかというと閾値を計算するため。閾値を計算して、ラベル1っぽいものを集めたUとラベル-1っぽいものを集めたNに分けるのがこのステップでやること。ステップ1を終えたらステップ2を実行する。ステップ1で準備したUとNを使う。
- スパイに送ったドキュメントをPに戻す
- PとNはiterationの間はラベルをいじらないで、Uに関してのみラベルをいじる
- P、RN、Qに対してEMが収束するまで繰り返す
というような感じでS-EMが完成。
