A Hierarchical Pitman-Yor HMM for Unsupervised Part of Speech Induction

論文紹介です。今日引っ越す関係で、しばらく家からネットが繋がらなくなりそうで、自分の理解の整理も含めて書いてみます。まとまってないです。
今年のACLで、A Hierarchical Pitman-Yor Process HMM for Unsupervised Part of Speech Induction [ pdf ]というのがある。これは、教師なしの品詞推定モデルで、やったのはBlunsomという、最近だとTree Substituion GrammarをPYPでモデル化する？ということとかやった人。ジャーナルは読もう読もうと思って読めてない状態なので適当ですが。この論文は、教師なし品詞推定に、過去の系列モデル（言語モデルや品詞推定）のモデル化におけるstate-of-the-artな手法を様々組み合わせたら、過去最高の結果が出たよ、というもの。この論文はACLが公開されてすぐに読んだけれど、その時は推定手法を飛ばしてざっと読んで、ふーんという感じだった。しかしもう一度読んでみて、結構推定のところで工夫しているのがこの論文の肝みたいなので、それについてだらだらと書いてみる。
このモデルの新しいところは、（多分）HMMの階層化を考えたところ。つまり、３グラムHMMの推定に２グラムとの補間を用いる。すごいシンプルな気がするけど、これが自然に扱えるようになったのがPYPやDPで階層化が自然に出来るようになったから、だと思う。
で、これの推定で何が問題になるかというと、階層CRPにおけるテーブルのカウントが問題になる。推定は他のBayesian HMMと同じくGibbsを用いるのだが、このとき３グラムをサンプルしている途中で、サンプルの候補によってその後の確率が変化するということが生じる。（この辺りはちゃんと説明するとかなり面倒なので割愛します。といってもこれを説明しないと後の議論は成り立たないのですが・・・。余裕ができたら補足するかも）で、本来ならば３グラムをサンプリングしている途中で、テーブルが増えるかどうかをサンプリングしながら推定するのだろうが、それは重すぎるので、計算途中では近似的にやってしまおう、ということをしていて、それが式（３）になる。
まず最初に言っておくと、この式の分母は多分タイポで、E_n[K_i]b^Uとなっているところのb^Uは、a^Uの間違いのはず。そう考えると、これは現在のテーブル数の近似値に、新しくテーブルが増える確率を足して、新しい近似値とする、という形になっていて、ある程度納得がいく。で、これが実際のPYPのテーブルの期待値とどれぐらい差が出るのかというのが示されている。式（３）のこともあるので、この図を簡単にシミュレートしてみた。
C++のコードが以下のような感じ。

#include <iostream>
#include <vector>
#define RANDOM ((double)rand()/(double)RAND_MAX)

using namespace std;
vector<double> approxTableCount(int customer, double a, double b) {
  double p_0 = 0.25;
  vector<double> approxCounts(customer, 0);
  
  for (int i = 0; i < customer; ++i) {
    double approxE = i == 0 ? 0 : approxCounts[i-1];
    approxCounts[i] = approxE + (a * approxE + b) * p_0 / ((i - approxE * a) + (a * approxE + b) * p_0);
  }
  return approxCounts;
}

vector<double> expectTableCount(int customer, double a, double b) {
  double p_0 = 0.25;
  vector<double> expectCounts(customer, 0);
  for (int j = 0; j < 1000; ++j) {
    int tableCount = 0;
    for (int i = 0; i < customer; ++i) {
      double random = RANDOM;
      if (random < (a * tableCount + b) * p_0 / ((i - tableCount * a) + (a * tableCount + b) * p_0)) {
        ++tableCount;
      }
      expectCounts[i] += (tableCount - expectCounts[i]) / (j+1);
    }
  }
  return expectCounts;
}

int main(int argc, char *argv[])
{
  vector<double> approxTables = approxTableCount(100, 0.9, 1);
  vector<double> expectTables = expectTableCount(100, 0.9, 1);
  for (size_t i = 0; i < approxTables.size(); ++i) {
    cout << (i+1) << " " << approxTables[i] << " " << expectTables[i] << endl;
  }
  return 0;
}

この結果をプロットしてみると、以下のようになる

このように、図3の a = 0.9の場合が再現出来ているので、式（３）は間違いだったことになる。
論文ではこのあと、1 tag per word の制限、つまり、１つの単語は複数の品詞を持たない、という制限を置いてこの近似を使って推定すると、精度が上がるといっている。具体的には、サンプルする単位が、各typeに対応する品詞となり、関係する同時確率を計算し、比較してサンプリングするのだと思う。最初はこれがtype based sampling（Liang 2010）と関係あるのかと思って、訳が分からない、と思っていたのだが、どうももっとシンプルな話で、単にその語に関係するトライグラムを全て抜き出して、その語の品詞が k であるとした時の全同時確率を計算し、サンプリングする、という話になるよう（ちゃんと理解出来てない気がするので、間違ってたら教えて下さい）。

あと教師なし品詞推定について思うことを少し。これも含めて、ここ１〜２年の教師なし品詞は、1 tag per word制限のもとで求めるというのが主流で、そっちのほうが精度が良い、ということらしい。この精度が良いというのは、既存の品詞体系と、ここで求まった品詞体系とを比較して、最もよくマッチするものが取れているということで言っている。しかし、品詞というのはそれを求めることが目的にはならないもの（自然言語処理的には、係り受け解析や翻訳の前段階）で、教師なしでgold standardに近づけて意味があるのかは微妙な気がする。まして、1 tag per wordの制約を入れてしまうと、精度は上がるかもしれないが、本質的な品詞とは何かという問題には何も答えないんじゃないかと思う。この辺りは、murawakiさんが似たことを書かれている。
だけど、少し視点を変えると、これは完全にテキストデータのみから品詞っぽいものを取り出す方法を示していて、これは教師あり学習が行えるほどのリソースが存在しない言語の解析に役に立つんじゃないかという気がしている。というのも、最近インターンで、言語横断的な何かをするということをしていて、リソースの少ない言語にどうアプローチするかというのが、今後問題になりそうな感じなので。リソースのない言語に対して、どうにか情報を取り出したいという場合、精度はそこそこでもそれっぽいものが取れていれば良くて、そういう問題には1 tag per wordも有効に働くのかなあとも思う。教師なしのモデル化というのは、個人的には人間の思考モデル、言語の本質を捉えるための道具（うまくはまれば、人間をそういうモデルで近似出来る）、と考えていたのだけれど、工学的意義を考えると、これはこれで意味があるのかという視点で見ることが出来て、面白いなあと思ったり。