桜がとってもきれいですね．すずかけ台は8分咲きといったところです．ところで，仲間で行っている小規模な勉強会で

• “Unified Expectation Maximization” Samdani et al, NAACL2012

を紹介してきたので，資料をslideshareにあげておきました．

Unified EMというと，じゃっかん大風呂敷な感じのタイトルですが，キーとなるアイデアはとても単純で，EMアルゴリズムのE-Stepで最小化するKLダイバージェンスにちょっと細工を入れることで，Hard-EMとふつうのEMの中間くらいの性質を持ったアルゴリズムになりますよ．というお話です．Deterministic Annealing EMの逆バージョンみたいな雰囲気(実際，DAEMもこの枠組で書けることが示されています) 手元にEMのコードがあれば，実装も非常に容易．

ただ，やっぱりそれだけだと一発ネタにしかならないので，「制約付きEM」のほうへ話を進めています．「制約付きEM」というと聞きなれないアルゴリズムですが，Un(semi-)supervised learningにおいて，事前知識を用いてモデルがとんでもない方向へ飛ぶのを防ごう，というモチベーションに基づく技法のようです．

自然言語処理におけるアプリケーションでは，たとえば以下のような制約を考えることができます：

• 品詞タグ付けなら

  • ある文には，名詞と動詞が最低一つづつ含まれる
  • ある語が，複数のPOSに割り当てられることは稀

• 機械翻訳におけるアラインメントなら

  • L1->L2のアラインメントと，L2->L1のアラインメントは一致する
  • L1の一つの語が，L2の多数の語と対応付けられることは稀

• 関係抽出なら

  • ある種のエンティティと，ある種のエンティティの間には，特定のリレーションしか成り立たない
    • (PERSON, LOCATION) -> LIVE IN
    • (ORGANIZATION, PERSON) -> WORK FOR

こういった事前知識に基づく制約を満たすモデルを，確率分布の集合として表現し，そこから離れないようにEMアルゴリズムを行うことによって，ラベルつきデータが利用可能ではない（または，少量しか存在しない）状況において，うまく学習が行おうというのが，「制約付きEM」の肝となる部分です．直感的には，Posterior Regularizationの論文から引用した以下の図が分かりやすいかもしれません．（日本語注釈は私によるものです）

歯切れのよいタイトルに惹かれて軽い気持ちで選んだ論文でしたが，そこそこホットな分野のようで，ACL 2011のチュートリアルで1トラックまるまるこの話題だったりしたらしく，問題設定や前提を理解するのにけっこう苦労しました．

結果として，UEMの本題ではなく，問題設定や先行研究の紹介に半分近くのスライドを割くことに・・・．まぁ，楽しんで頂けたようなのでなによりです．しかしひさびさに緊張感のあるプレゼンだった．

最後のスライドにも記載しましたが，以下の文献が，理解の助けになると思います．

• “Rich Prior Knowledge in Learning for Natural Language Processing” ACL 2011 tutorial
  • ACLで行われたチュートリアルの資料です．このファミリーに属するアルゴリズムについての資料の多くはここからたどれるようになっています．各種のアルゴリズムのあいだの関係についてよくまとまっていますし，著者らによって異なる表記系もすっきりまとめられているので読みやすい．今回は取り上げませんでしたが，Labeled Feature とかも追ってみるとおもしろそうなトピックなので，ぜひ．
• “Posterior Regularization for Structured Latent Variable Models” JMLR 2010
  • 今回紹介した論文の元ネタになっている Posterior Regularizationの論文です．品調ラベルづけにおける例とともに，少しづつ丁寧に議論が進められており，さすがジャーナルだけあって読みやすいです．

ひさびさに負荷の高い一週間だったので，来週はすこしゆっくりしたいと思います．（日記）