Language-Independent Set Expansion of Named Entities using the Web

　Language-Independent Set Expansion of Named Entities using the Web (R. C. Wang and W. W. Cohen, 2007)を読んだ。例のSEAL(Google SetsとかBayesian Setsに似た奴)のアルゴリズムについて書いた論文だ。ちゃんと固有表現抽出までやってるとしか思えないとか書いてたが、実際には全然違った。固有表現抽出どころか形態素解析すらしてない。
　SEALがやってくれることはGoogle Setsなどと同じだ。いくつか単語を与えると、その単語と同じグループに含まれるような単語を返してくれる。この論文ではそのようなグループの例として、メジャーリーグの球団名とか、時計のブランド名とか、そういったものを使って実験している。
　アルゴリズムは以下の3ステップによって構成される。

与えられた単語を用いてweb検索を行い、返ってきたURLの上位n件のページ内容を取得する
単語に共通する文脈を見つける（これを論文ではwrapperと呼んでいる）
文脈を用いて同位語の候補を見つける
同位語の候補に対してランク付けを行う

　1は自明だとして、2以降のステップは具体的にどうなっているのか。例えば、「ホンダ」と「トヨタ」で検索して、以下のようなHTMLを得たとしよう。

<ul><li>ホンダ</li>
<li>トヨタ</li>
<li>日産</li></ul>

　この時、「ホンダ」と「トヨタ」の左右に共通する最長の部分文字列のことをwrapperと言う。目的となる単語の左右をラップしているからwrapperというのだろう。wを単語本体とすると、この例ではwrapperは<li>w</li>となる。
　このwrapperが決定すれば、次のステップでは「日産」を同位語の候補として取ってくることができる。これは正規表現でも使えば数行だろう。要するに、同じような形で挟まれている単語は同位語である可能性が高そうだ、という仮定に基づいている。wrapperはページによってまちまちであるので、各ページに対して専用のwrapperを作成をする、と書いてあった。もちろん、1つのページに複数のwrapperが存在する場合も考えられる。
　これを検索結果のページに対して適用すると多くの同位語候補が得られるが、これはノイズが多すぎてそのままでは使いものにならない。そこでランク付けを行う。
　ランク付けを行うために、まずwrapper, 同位語候補, 検索結果URLの3種類の要素をノードとしたグラフを1つ作る。そして、これらの間を結ぶが、その際は関係のあるもののみを結ぶ。つまり、wrapper1から同位語候補Aが得られた場合にはwrapper1と同位語候補Aの間を結ぶ。wrapper1がexample.comから得られたのだとしたら、その間も結ぶ。
　このようにしてグラフを作ると、以下のような性質ができる。(めんどくさいのでいくつか省いたけど、想像はつくと思う。)

複数のwrapperから生成された同位語候補はそうでないものと比べて多くの辺を持つ
多くのwrapperを生成したURLはそうでないものと比べ多くの辺を持つ

　で、このグラフのどこかから、ランダムにノードを移動していく。どの辺が選ばれるかは等確率であるとする。移動を繰り返していくと、多くの辺を持っていたり、選択される回数の大きなノードの近くに居るノードほど、選択される回数が増える。この選択される回数で、同位語候補のランク付けを行う。
　実験においてはGoogle Setsとの比較や、グラフウォークによるランキングを行わない例との比較を行っているが、提案手法が精度的には一番良いという結果になったようだ。まぁ、アルゴリズムを考えると、精度は高くなりそうだよね、確かに。
　以下は感想。

簡単な仕組みで精度は高い。
Introductionで「Google Setsは手法が非公開であり、アルゴリズムが変わってしまう可能性があるので再現性が保証できない。実験に使うには不適等だ」みたいな事が書いてあるんだけど、SEALもWeb検索使ってるので再現性は保証できない気がする。まぁ、SEAL自体はWebでもデモが公開されてる訳だし、実装も難しくない（というか、かなり簡単だろう）ので、実験するときに自分で追試すればいいんだけど。
このアルゴリズムは同意語を自動で抽出するわけではなく、人間が適切なシードを与えなければ適切な結果は返ってこない。また、関連語全般が取れる訳じゃなく、同位語しか取れない。逆に、そこを利用して同位語の判定に使えないかなーとか思った。というか、たぶん使えるんじゃないかな。もしかしたら既にそういう論文もあったりして。

　8ページにしては図とかが充実してて読みやすいので、気になった人は論文を読んでみるとよいと思います。