Hatena::Grouprekken

murawaki の雑記

2015-09-20

STRUCTURE と ADMIXTURE の混合分布モデル

久しぶりに NLP タグをつけたが、生物系の混合分布モデルの話。ゲノムを使う系統関係の論文では、PCA と並んで、よくこういう図が出てくる。

参考までに caption も引用。

(A) Representative estimate of population structure for 1,384 individuals from worldwide populations, including 432 individuals from India. The plot represents the highest-likelihood run among ten STRUCTURE runs with K = 7 clusters. Eight of the other nine runs identified a cluster largely corresponding to India, and five of these eight produced plots nearly identical to the one shown.

Figure 2. Population Structure Inferred from Microsatellite and Insertion/Deletion Polymorphisms

縦の列 (column) が各個体。各個体ゲノムの列 (sequence) で表現されている。これが K=7 個の潜在クラスで色分けされている。要は混合分布モデル、というか NLP 業界的にいうとトピックモデル。となると、具体的にどういうモデルなのか気になるところ。しかし、論文を読むと、生物系の人が生物の言葉で語っていて何度かくじけた。今回 ADMIXTURE の論文 (2009) を見たところ、最初から統計の言葉で説明されていて、ようやく糸口がつかめた。NLP 的な説明に翻訳してみる。

まずソフトウェアの確認から。STRUCTURE という検索泣かせな名前のソフトが昔からあった。最近、ADMIXTURE というこれまた嫌がらせのようなソフトが出てきた。新しい論文では ADMIXTURE を使っていることが多い。他に frappe というソフトもあるが、それほど見かけない。まずは新しい方の ADMIXTURE を見て、次に STRUCTURE に移る。

ADMIXTURE の混合分布モデルのグラフィカルモデルは以下の通り。

f:id:murawaki:20150921081447p:image

  • 事前分布が設定されておらず、pLSI 的。
  • 3 重の plate になっている。外側の I が個体のループ。次の J が DNA の列のループ。言語のトピックモデルだとこの 2 つ (I: 文書, J: 文書内の単語)。A は染色体の数。最近の genome-wide SNP の話だと、diploid といって、両親から 1 個ずつ受け継ぐため、A = 2 らしい。
  • \theta個体ごとの混合比。要素数は K。結果の図で色分けされているのはこれ。
  • \varphi が K と J の 2 重ループになっているのも特徴的。言語のトピックモデルだと K ごとにサイズ V の語彙分布を持っている。DNA の場合は列の場所ごとに別の分布を持っているので K x J 個の変数が必要。SNP の場合はベルヌーイ分布。
  • 記号は言語のトピックモデル風に変更している。また、元の説明だとカウントの分布 (多項分布) を考えているが、ここでは列の分布 (categorical 分布) を示している。

Z で周辺化して、W の確率にすると以下の通り。

\begin{eqnarray} p(W | \Theta,\Phi) &=& \prod_i \prod_j \prod_a \sum_k p(z_{i,j,a}=k | \theta_i) p(w_{i,j,a} | z_{i,j,a}=k, \Phi)\\ &=& \prod_i \prod_j \prod_a \sum_k \theta_{i, k} \,\times\, \varphi_{j,k,w_{i,j,a}} \end{eqnarray}

推論は、論文ではまず EM を導入する。しかし EM は遅いからと、別の手法提案する。EM で遅いと言われると、サンプリング脳なのでつらい。

次。STRUCTURE のグラフィカルモデルは、Pritchard et al. (2000) によると以下の通り。

f:id:murawaki:20150921081448p:image

ADMIXTURE のモデルとの違いは、事前分布が追加されていること。\alpha\eta はいずれも Dirichlet 分布のパラメータ。symmetric なパラメータを一つ与えるか、経験ベイズ的にデータから推定するかでモデルに変種がある。ほぼ LDA。

推論。\theta\varphi は共役性を利用して積分消去したいところだが、元論文はそのままにしている。\theta\varphi と z を (実は\alphaも) MCMCサンプリングする。

欠損値は、ADMIXTURE の場合、あらかじめ補完するという。STRUCTURE のような MCMC であれば、補完を sampling に組み込むのは簡単そう。

トピック数 K はあらかじめ指定する。Pritchard et al. (2000) では K を自動推定する怪しげなモデルが説明されている。実際に使われているのだろうか。AIC などを使ってモデル選択をするという手もある。論文でよく見かけるのは、K = 2 ... 5 くらいの結果を並べてお茶を濁すもの。

新しい ADMIXTURE の方がモデルが退化しているのが妙なところ。STRUCTURE はサンプリングの遅さが嫌われて ADMIXTURE への移行が進んでいるみたい。規模感としては、I が千ぐらい、J が数十万。確かに小規模とはいえない。でも、Wikipedia の記事 3M ページに対するトピック推定などと比べると、特別大きいわけでもない。

似た研究を別々に進めるのは不健全。LDA を提案した Blei et al. (NIPS2002) が 2002 年だから、実は STRUCTURE の Pritchard et al. (2000) の方が先行している。NIPS 2002 でも、2003 年の JMLR 版でも、Pritchard et al. (2000) への言及がない。2004 年の Blei の博論では引用されているので、このあたりで生物系の研究に気付いたらしい。というか、Blei の論文リストを眺めていると、2015 年になって Posterior predictive checks to quantify lack-of-fit in admixture models of latent population structure という論文を出しているのに気付いた。

ADMIXTURE の論文は 2009 年に出ているが、トピックモデルへの言及がない。ここ 10 年ぐらいで発展したトピックモデルの手法DNA データにもそのまま使えそう。例えば、階層 Dirichlet 過程を使ってトピック数 K をデータに決めさせるとか、高速化の手法とか。需要はないのだろうか。

2014-04-02

JUMAN メモ

黒橋研究室で開発している日本語形態素解析JUMAN についてのメモ。

以前は研究室のページに置いていたもの。長く放置していて内容的に古くなっていたが、最近になって突然晒された。*1文書に日付を入れていなかったのが敗因。この機会に雑記に移すことにした。古くなっても日付を言い訳に使えるし。

以前は中の人だった。どこを直すかという問題意識があった。今は所属も変わって、しばらくはそういうのはいいかなという気分。かわりに、使っている人向けにぼちぼち書き換えようかと考えている。論文には書きにくい小ネタなども。

タスク: 日本語の形態素解析

形態素解析と言っているのは、以下の3つのタスクの同時処理。

  • 分割 (segmentation)
  • 品詞タグ付け (POS tagging)
  • 見出し語化 (lemmatization)

分割は、テキストを形態素に区切ること。形態素というとおっかないが、単語だと思っておけば良い。品詞は「名詞」や「動詞」など。見出し語化という表現は聞き慣れないが、「走れ」のように活用変化した形を基本形の「走る」に戻すこと。

世の中一般的には、形態素解析は分割 + 品詞タグ付け と説明されることが多いが、見出し語化にも触れた方が良いと思う。ここが語形変化のない中国語の処理と決定的に違うところ。中国語の処理と違って辞書ベースの手法が主流なのも、これが大きい。

「X分割」という表現は混乱している。word segmentation の場合、X は分割後の状態だが、text segmentation や query segmentation だと分割対象。

入出力フォーマット

  • 入力は1行1文
  • 出力は1行1形態素
    • 最後の行は EOS (end of sentence)

子ども こども 子ども 名詞 6 普通名詞 1 * 0 * 0 "カテゴリ:人 代表表記:子供/こども"

は は は 助詞 9 副助詞 2 * 0 * 0 NIL

リンゴ りんご リンゴ 名詞 6 普通名詞 1 * 0 * 0 "カテゴリ:植物:人工物-食べ物 ドメイン:料理・食事 代表表記:林檎/りんご"

が が が 助詞 9 格助詞 1 * 0 * 0 NIL

すきだ すきだ すきだ 形容詞 3 * 0 ナ形容詞 21 基本形 2 "代表表記:好きだ/すきだ"

EOS

形態素解析は非常に局所的な文脈しか見ないので、別に複数文を一度に入れてもあまり問題にならない。構文解析でそれをやると、計算量が爆発するし、結果が気持ち悪いことになる。

英数字記号は全角で入力されることを期待している。UTF-8 化 (後述) にあわせて半角入力でもそれなりに処理するようになった。しかし全角に変換しておくことを勧める。出力時のエスケーピングをちゃんとやっていないので、特に記号がらみで事故が起きやすい。

エンコーディング

長らく EUC-JP だった。外部の人が UTF-8 版を作ってくれた。しばらく放置されていたが、時代の流れに逆らえず正式UTF-8 に移行した。

速度

MeCab とくらべると圧倒的に遅い。しかし中の人には「cat 状態」と認識されている。一般に、形態素解析の結果を受けて何かをしようとすると、後段の処理の方が比較にならないほど遅い。だから JUMAN の速度を改善する動機はとぼしい。

というか MeCab が頑張りすぎである。下手な英語の tokenizer よりもよっぽど速い。気合が違う。

解析結果をルールでゴリゴリ処理するようなアプリケーションを作っている人なら、JUMAN の速度は気にならないはず。でも、KNP で構文解析までやると遅い思う場合は、

juman | knp -tab -assignf

がお勧め。文節まとめあげ + 各種 feature 付与までで打ち切って構文解析をやらない。KNP が吐く feature をうまく使えば、解析結果に対するルールの再発明が減るはず。

内容物

プログラム古色蒼然としてる。C で書いてある。辞書のデータ構造は、パトリシア木を ChaSen から借りてきたり、double array を MeCab から借りてきたり。

連濁対応などでプログラムの更新もたまにあるが、実質的に辞書のみの更新。

文法辞書と形態素辞書は利用者が自由に定義できるとマニュアルではうたっている。しかしデフォルト以外の辞書が配布されている例を知らない。

ChaSenMeCab は配布のレベルで、プログラムと辞書を分離している。それらに対する辞書としては IPADIC, NAIST jdic, UniDicなどがある。

ライセンス

マニュアルには3条項BSDライセンスが書いてある。このライセンスプログラムだけでなく辞書に及んでいるかなどはよく分からない。中の人もあまりちゃんと決めていない。

よく分からない問題はいろいろある。最近 Wikipedia を加工して辞書を作っているんだけど、この辞書のライセンスはどうなるのか。テキストの解析結果には辞書の情報が大量に埋め込まれているけど、解析結果を配布するときどうなのかとか。頼まれて以前調べたけど、法律専門家でも何でもないので私には正解が分からない。詳しい人に教えてほしい。

品詞体系

  • いわゆる益岡・田窪文法
    • 基礎日本語文法』の記述に結構忠実
    • 学校文法 (橋本文法) 系の ipadic の IPA 品詞体系も異なる
      • 相互の変換は困難
    • unidic は unidic で IPA 品詞体系とも違うらしい
      • KyTeaデフォルトモデルは、unidic の品詞の大分類 & 「語尾」(活用語の変化する部分を切り出したもの)

益岡・田窪文法に慣れると IPA 品詞体系には拒否反応が出る。ただ、ナ形容詞と判定詞の区別は微妙。活用変化がほとんど同じなので。

つべこべ言わずに統一してくれよという声はよく聞く。

処理内容

  1. 入力に対して、形態素辞書を引いて出力 (形態素列) の候補を列挙
  2. コストにより最適な候補を選択

候補の列挙

  • 辞書を引く
  • 未知語候補をその場で生成
  • 連濁候補は基本形に戻して辞書を引く
  • 反復型オノマトペはパターンにマッチするものをその場で生成
  • 非標準表記を標準表記に戻して引く

ChaSenMeCab は最初の2つしかやっていない。残りは JUMAN でも比較的新しく入った機能。MeCab だとチューニングしすぎていて入れにくそうな機能。そのうちちゃんと説明するかも。

候補の選択

  • 形態素辞書と連接辞書により、形態素と、形態素同士の連接にコストを付与
  • コスト最小のパスを選択

パラメータ (コスト)

このご時世に人手で設定している。まさに職人芸。単語の生起コストはいい加減でもわりと大丈夫。連接コストは頑張って調整してある。

ChaSen/MeCab はそれぞれ隠れマルコフモデル (HMM)、条件付き確率場 (CRF) により訓練データからコストを学習する。単語の長さがいろいろなので、hidden semi-Markov model や semi-CRF と言ったほうが正確かもしれない。

JUMAN、ChaSenMeCab とも、解候補は同じ構造 (lattice) で表現できる。解探索のアルゴリズムも同じ。コストの決め方に関する考え方が違うだけ。KyTea はまったく異なる。

精度は完全に MeCab に負けている。

ちなみに日本語版 Wikipedia は、長い間、JUMAN は「隠れマルコフモデル」を使っているという誤った説明をしていた。生暖かく見守っていたら、中の人によって修正されてしまった。

人手による連接コストには利点もある。ありえない連接が候補から除外できる。そもそも付属語の連接にはかなりの程度文法的な制約があって、可能な連接は限られている。

一方、MeCab は完全にコーパスから学習するので、あらゆる連接が可能。もちろん変な連接には大きなコストが設定されるので、普段は問題が顕在化しない。しかし、未知語が入ってきたときなどに、どう考えてもありえない解析結果を吐いたりする。MeCab も連接制約のホワイトリストブラックリストを作って入れたらいいのに。

ただ、特に文頭の連接制約はきつすぎて、くだけたテキストの解析がつらい。

同形

  • コストが同じ複数の候補は同形として出力
  • @ から始まる出力行があるもの
    • 出力は単に辞書引きの順番なので、どちらが正しいというわけでもない
    • 方針として、JUMAN は曖昧性の候補を列挙するのみ; 選択は KNP で行う

かぜ かぜ かぜ 名詞 6 普通名詞 1 * 0 * 0 "漢字読み:訓 カテゴリ:抽象物 代表表記:風/かぜ"

@ かぜ かぜ かぜ 名詞 6 普通名詞 1 * 0 * 0 "カテゴリ:抽象物 ドメイン:健康・医学 代表表記:風邪/かぜ"

で で で 助詞 9 格助詞 1 * 0 * 0 NIL

おくれた おくれた おくれる 動詞 2 * 0 母音動詞 1 タ形 10 "可能動詞:送る/おくる 代表表記:送れる/おくれる"

@ おくれた おくれた おくれる 動詞 2 * 0 母音動詞 1 タ形 10 "付属動詞候補(基本) 自他動詞:他:遅らせる/おくらせる 自他動詞:他:遅らす/おくらす 代表表記:遅れる/おくれる"

EOS

  • 同形が出力されるのは分割とコストが同じ場合のみという微妙仕様 (e.g., おさない == 幼い != 押さない) だが、結構使える
  • 同じコストになるのはコストを人手で調整しているから
  • くる:子音動詞ラ行 (繰る) と くる:カ変動詞 (来る) のように品詞が一部違っても同形になる

MeCab は同形の曖昧性を考慮せずにパラメータを推定しているので、どちらとも言えないような場合でも、とにかく一つの解に決めてしまう。N-best にすれば複数の解を出力するが、N をいくつにすれば良いかは事前にはわからない。 そもそも同形の曖昧性解消を N-gram の情報で行うのが適当とも思えないから、JUMAN/KNP の方針は妥当だろう 「おくれた」のような用言の曖昧性解消は、KNP が格フレームを使って行う。修士論文の成果だったと思う。最近の格フレームでどれぐらい正しく曖昧性解消できているかは誰もちゃんと調べていないはず。

辞書の整備方針

  • 形態素数は削減する方向
    • 基本語彙のみを人手で整備し、残りは自動獲得したい
    • 基本語彙には人手で様々な意味情報を付与
  • 新聞記事に出てこない難しい単語や固有名詞などは、IPADIC の方が豊富
    • JUMAN/KNP を用いた日本語固有表現認識の論文でも、精度を上げるために MeCab の解析結果を参照するという変態的な処理をやっている
  • それ以外にも、なぜ登録されているのか不思議な形態素が辞書に残っていたりする

大人が読むテキストには普通出てこないようなひらがな表記も結構登録されている。「かぐ」(家具) とか。おそらく、小学生向けの辞書からの情報抽出を昔やっていたなごり。副作用も結構あって、「茄子」に対する「な子」のような変な混ぜ書きが悪さする。

代表表記

  • 基本語彙に付与されている
  • 表記ゆれをある程度吸収する
    • 風邪, かぜ -> 代表表記:風邪/かぜ
      • 代表表記は単なるキー
      • これが標準的な表記と主張しているわけではない

形態素よりも長いキーフレーズレベルでの表現の揺れの吸収は『キーワード蒸留型クラスタリングによる大規模ウェブ情報の俯瞰』が詳しい (ヒューリスティクスの塊)。解析に使う分には代表表記は便利。ユーザがいる問題設定だと、こんなものをユーザに見せるわけにはいかないので、処理中に、標準的な表記を代表表記といっしょに保持しておかないといけない。

カテゴリ・ドメイン

  • カテゴリは荒っぽい抽象化の単位
  • 付与されたカテゴリの半分ぐらいが「抽象物」
    • 卒論の成果
    • 設計ミスまがいだが、細分化しても取り分がなさそうだから放置してある

カテゴリ・ドメインは言葉の大雑把な分類。この2軸を組み合わせれば、大雑把な分類としては十分ではないかという見通しだったらしい。 他には、シソーラスを使うと権利の問題がややこしいから、独自に作ったとか。

カテゴリは省略解析などで実際に使われている。

かつて、カテゴリ (のサブセット) を自動分類しようとしてひどい目にあった。いまでもトラウマ。そもそも意味的な情報を形態素という単位に与えるところに無理がある。人間の作業者が、直感に基づいて適当に割り当てる分には良いかもしれないが、データに基づいて決めさせようとすると、そのいい加減さに計算機が耐えられない。

その他の意味情報

「可能動詞」ラベルは、可能で使われる可能性があることを示すだけで、文中の個々の形態素が可能動詞の用法で使われているとは主張していない。これに限らず、JUMAN/KNP では、可能性があるために付与されている情報と、解析の結果 (いくつかの可能性の中から選択された結果) 付与された情報があまり整理されないまま混在している。

自他の対応などは、構文レベルの表現のゆれの吸収を目的に付与してある。

読み

辞書に代表的な読みが書いてある。解析時には辞書引きした結果を表示しているだけ。テキスト中での正しい読みを当てる気はない。数字の読み、音・訓の区別、表記に反映されない連濁の区別は間違っている可能性が高い。

だから転写や音声合成には使えない。UniDic はこのあたりもちゃんとやる方針らしい。いまの形態素解析器が使っている手がかりだけで正しく判別できるのか疑問だけど。

形態素の単位

以前辞書を整理した際に、構成的な語を削除しまくったらしい。それでも単位の不統一は残っている。

テキストの分割方法として、これが正しい単位だという基準が設定できない。辞書に載っているということが一種の基準になってしまっている。

「揺れの少ない斉一な単位」をうたう UniDic でも、直感に反して、「寿司屋」と「家具屋」で分割が違うらしい (未確認)。漢語と和語で扱いが違うとのこと。UniDic は踏み込みたくない領域に踏み込んでいる。

可能性に基づく品詞体系

「可能性に基づく品詞体系」という用語は IPADIC で使われているもの。JUMAN のデフォルトの品詞体系はこうは説明されない。しかし実質的に同じことをやっている。

例えば、「今年」は「今年の目標」であれば名詞として振舞っているが、「今年起きた事件」では連用修飾を行っており副詞的。辞書は「今年」に「名詞 - 時相名詞」という品詞を割り振っている。どちらの文の「今年」に対しても、この品詞を割り振っておしまい。IPADic は、その点を明確にしていて「名詞 - 副詞可能」という品詞が割り当ててある。名詞としても振る舞うし、副詞としても振る舞うということ。

文中でどのような振る舞いをしているかを当てに行くのをはなから放棄している。要するにインチキ。英語の品詞タグ付けとは大違い。

誰が名詞用法と副詞用法を区別しているかというと、文節まとめあげや係り受け解析で暗黙的に行っている。

一応区別はしているものの精度が悲惨な例もある。「で」の曖昧性問題。「京都は大学の町で観光地でもあります。」という例文では、「町で」の「で」は判定詞だが、「大学の街で観光した。」だと格助詞。いまの形態素解析器が見ているような局所的な手がかりでは区別しようがない。

動詞の連用名詞化

動詞の連用名詞化は、IPADIC では「可能性に基づく品詞」を採用していないけど、JUMAN では採用している。例えば動詞「遊ぶ」の連用形「遊び」。「外で遊び家に帰る」だと動詞用法だけど、「遊びを楽しむ」だと名詞用法。IPADIC では、動詞と名詞の両方が辞書登録してある。しかし MeCab の解析結果は不安定。「買いに行く」の「買い」をいろんな動詞に入れ替えてみると、名詞と解析されたり、動詞と解析されたり。

JUMAN はいずれの用法でも動詞の「基本連用形」とする。名詞用法のものは KNP が名詞に変換するという運用。この変換はちょっと面倒。名詞にすると活用しない扱いなので、見出し語 (JUMAN 用語では原形) もあわせて「遊ぶ」から「遊び」に変更しないといけないとか。こういう変換処理がプログラム内にベタ書きしてある。

JUMAN 的には KNP の担当になっているが、名詞用法の判定は難しい。上記の「外で遊び家に帰る」なら「遊び家」という複合名詞はありえない。「彼を操り人形にした」なら「操り人形」という複合名詞を採用する解釈が自然。「彼を操って人形にした」という解釈も可能だけど。KNP はどう処理しているかというと、明らかなものはルールで決め、残りはウェブコーパスから作った共起の統計量をもとに判定している。

京大テキストコーパスは KNP 仕様で、名詞と動詞の用法を区別している。MeCab のもととなった CRF モデルの論文の比較実験が、このあたりをどう処理したのか、いまだに把握していない。

その他の雑多な問題

悩ましい問題はいろいろあって、京大テキストコーパスアノテーションガイドで言及されている。形態素関連は3節。

コーパスのアノテーションガイドはいろんな知見がつまっていて面白い。みんなもっと読んだらいいのにと思う。

*1Internet Archive によると2009年1月には移設前の状態だったみたい。

2014-02-06

意味の意味が分からない

表題は某日記から拝借。計算機に自然言語を扱わせるうえで、意味を理解させるというのが大きな目標。しかしこの目標は漠然としている。何が達成できたら意味を理解したことになるのか分からない。いろんな人がいろんな方向から攻めている。適当に洗い出す。範囲は広いし時間もない。裏とりはせず、記憶に頼って殴り書き。

記号

意味は、対応する記号を置いておけば良いという立場。それ以上の表現を与えない。興味は、記号同士の関係を論理式で与えることと、その真偽値にある。この手の話は、元はといえばたぶん Frege あたりまでさかのぼる。

計算機との関係では、かつて人工知能屋さんが論理式と戯れていた。もはや教科書を通してしか知らない。Nixon diamond とか作って遊んでいた古き良き時代。planning とか、閉世界仮説とか。それ単独で見るとおもしろい話題はいろいろある。けれど、自然言語と遊離した独自世界。現実にそこにあるテキストと結びつく未来が見えない。

頑張って自然言語形式言語と結びつけようとしている人もいる。英語を対象とした Montague の文法は、失敗したという結論でいいのだろうか。そんなこと言っていると、誰かに後ろから刺されたりするのかな。難しい課題はいろいろあるが、例えば may とか want N to V とかどうするのよ、とか。論理体系が既にあって、そこに自然言語をどうやって帰着するかという問題ではすまない。自然言語の論理をうまく表すような論理体系を作りつつ、自然言語形式言語との間の変換規則も作るという同時並行的な作業。

最近の論文では、Combinatory Categorial Grammar (組み合わせ範疇文法、CCG) というのをよく見かける。誰が親玉なのかわからないが、Steedman という名前をよく見る。日本では戸次先生。最近は構文がそこそこの精度で解析できるので、構文の延長として意味を何とかしようと思ったとき、形式言語の出番かなあと思っている人がそこそこいる。ただし、ハードコアな人の興味は、文法要素の扱いとか量化とかをどう処理するかにあるっぽい。それだけでもやることが山積みっぽい。それはそれで大変楽しそうだけど、短期間で実用状態に持っていくことを望んでいる人たちとどう折り合いをつけるのかなあ。

基本はやはり記号というアトミックな単位の組み合わせ。最小単位は記号を割り振ったらおわり。論理式に変換できたとして、その先で本当に何かできるのかなあ。

最近見かけるシリーズでいうと、neo-Davidsonian な論理式をよく見る。John loves Mary を love(John, Mary) に変換すればすむと思ったら大間違いで、∃e.love(e, John, Mary) にしないといけないという話。あってる?

論理式で言うと、Markov Logic Network というのが一時はやった。最近は見なくなってしまった。Domingos 先生が頑張って旗を振っていたのに。論理式といっても、ルールが論理式の形で書いてあって、それに具体的な値が入って instantiate されて、論理式に対応づいている重みから全体のスコア最適化されるってな感じ。こんな説明じゃ伝わらないと思うけど。論理式は人手でゴリゴリ書く。共参照 (coreference) のルールとか。自然言語の意味を扱う方向に発展する感じがしない。

同義性

テキストを処理する立場から言うと、最小単位は記号を割り振ったらおわりという部分が引っかかる。上位下位関係 (例えば、ペンギンと鳥) は論理式で表現できそう。部分全体 (meronymy/holonymy) とかは? 反義は? この手の、英語だと -onym (語について)、-onymy (関係について) と名のつく現象がいろいろある。

一番困るのは実は同義性。完全に同じ意味の語というのはなくて、どこかしら異なっている。仮に、ほぼ同じ、だいたい同じ、似てない、みたいに連続的に分布しているとしたら、離散的な記号でどう扱ったら良いのか。あるとき、国際会議で、上位下位とかの共通データセットを作っている人の発表を聞いたことがあったが、その人が「同義はわからないので扱わない」と宣言したものだから、唖然とした記憶がある。どのデータセットだったか覚えていないが、確かイタリア人の発表。

実用上は同義性は重要。例えば、検索するとして、知りたい内容が書いてあるのに、クエリとちょっと表現がずれていただけで引っかからないとなると困るから。

多義性

テキストを処理する立場から言うと、テキスト上の loves に love という記号を与えておわりで良いのかも疑問。love の語義は一個だけ? 別の語義もない? そもそも語義は1個、2個と離散的に数えられるもの?

人手で語義1、語義2とつけておいて、未知の出現に対して語義を推定するタスクが word sense disambiguation (語義曖昧性解消)。何を手がかりに推定するかというと、周りに出現する単語とかを見る。この話は後述。

発展として、以前、既存の語義一覧にない外れ値を当てるタスクを解いている人の発表を聞く機会があって、地をはう精度を見せられたことがあった。いや、そら難しいよね。

語義をあらかじめ定義せず、似た意味を持っていそうな出現をまとめていく (clustering) する流儀もある。こういう話と論理は、はたして将来統合されたりするのだろうか。

思いついたキーワードを適当にあげると、family resemblance。game に共通する意味って何だろうねってやつ。

意味を担う単位

テキストを処理する立場から言うと、単語にばらして記号を割り振れば良いという方針に疑問を感じる。慣用句はどうするよ? kick the bucket。idiom の例として散々紹介されるけど、実際に使われているのを見ないことでお馴染み。

別に慣用句に限らない。例外ではなく、むしろ一般の現象だと考えている。複合名詞には多かれ少なかれ構成性 (compositionality) で説明できない部分がある。「下駄箱」って「下駄」と「箱」の合成で説明できる? もはや「下駄」は関係なさそうなのに。

思うに、仮に世の中にある概念が離散的で数えられるとしても、概念の数は単語の数よりも多い。世の中は複雑すぎるから。先に概念があって、それをうまく説明しようと、単語を組み合わせる。そうやって人は新しい表現を作る。ひとたび社会に定着したら学習者はそれを受け入れるしかない。

とは言ったものの、いかにも構成的な場合と、そうでない場合がある。「木製下駄箱」という複合名詞は、「下駄箱」は語彙的だとしても、「木製」と「下駄箱」がその場で構文的に結びついている気がする。両者にきれいな境界があるかというと、なさそう。さあどうする?

ちょっと関連するのが collocation。これ自体は、テキスト中でよく共起する単語列 (ギャップを扱う場合もあるけど)。意味について何も言っていない。

分布仮説

ここからは、意味に対して記号を割り振るだけでなく、もっと具体的な表現を与えましょうという方向性。テキスト中での語の使われ方を見て何とかする。頑張ってさかのぼろうと思えば、みんな大好き後期 Wittgenstein とかまでいける気がする。こじつけかな? 一般に言われるのは Harris の分布仮説。「似た語は似た文脈で現れる」ってやつ。

どうやるかとうと、着目した語のテキスト中の出現を調べる。各出現について周りの単語を抽出してベクトルを作る。具体的なベクトルの作り方には山のような変種がある。で、これが意味だと主張する。

このベクトル自体は何とも解釈しようがない。しかし応用はできる。ベクトル同士の類似度をはかれば、それを語の類似度とできる。分布類似度というやつ。

分布類似度にはよく知られた問題がある。反義語の類似度は高くなる。考えてみると、似ていないというのは、全然無関係だってこと。反義語は、直感的には、ほとんど同じで、ある軸だけ反転している。そういう点ではよく似ている。

多義語をどうするのよという問題は当然ある。

あと、未整理のキーワードをあげると prototype と exemplar。

構文とトピック

周辺の語に着目した類似度は、かなりの程度構文的類似性となる。どういうことかというと、名詞と名詞、動詞動詞は近くなるけど、名詞と動詞は似ていない扱いになる。英語だと、同じ単語の単数形と複数形が、期待ほど似ていないという結果が返ったりする。

周辺の語という制約をゆるめて、いっそ文書内での共起に着目したらどうなるかというと、それはトピックモデル。LDA (Latent Dirichlet Allocation) とか。そうすると、経済とか政治といったトピックでまとまる。名詞と動詞のような構文的類似性は関係がなくなる。これはこれで、ある種の意味の類似性だと思うが、そういう文脈で取り上げられることは少ない気がする。両者の折衷モデルも提案されている。

ニューラルネットの逆襲

いままでは素朴に意味ベクトルを作っていたが、ニューラルネットを使って低次元ベクトルを学習するといい感じになるという話題が最近熱い。ベクトル同士を適当に足し算・引き算する、例えば、King - Man + Woman とすると Queen が浮かび上がるという衝撃的な論文が去年 (2013年) 発表されている。

この論文を見ると、recurrent neural network を使っている。言語モデル用に作ったのを使いまわしている。recurrent だから長距離の影響も残りはするけど、基本的には直前の語の影響が大きいはず。そうすると、上で議論したように、構文的な類似性が強くなるんじゃないかと予想する。論文の表1にあるように、see:sees との類推で return:__ の空欄を埋めるとか。しかし Queen の例を出されて驚いている。素朴に意味ベクトルを作ると、ベクトル中の see の要素と、sees の要素は別々だけど、低次元に変換すると、see の要素と単複の要素に汎化されたりしているのかな。economy と economic みたいに、構文的に類似しない関係はどの程度いけるのだろう。

意味の合成

単語に対して意味表現が与えられたする。しかし、言語というのは組み合わせて句や文をつくるわけで、句や文に対しても意味表現を作りたい。ではどうするか。2つの構成要素 (単語とか句) が結合するとき、例えば、ベクトルの要素同士を足し算して、あらたなベクトルを作る。しかし、それでは bag-of-words と変わらない。単語の並びには何らかの意味があるはずで、それを意味合成にも反映させたい。

要素同士の足し算以外にも、要素同士の掛け算とか、さらにテンソルが出てくるとか、量子論だとか言っている人もいる。黒魔術が展開されているっぽい。おそろしくて深入りしていないのでよくわからない。

意味合成もニューラルネットが席巻している。ベクトルに重み行列をかけて tanh する。もはや何が起きているのかわからない。とにかく、重み行列をいい感じに学習できたら、単にベクトルを足し合わせるよりは良い精度が得られている。

重みの学習方法はいろいろあるが、一つは task driven。これはわかりやすい。例えば感情推定 (文が positive か negative か判定)。文の出力が正解になるように重みを学習する。これなら、正解を出せば良いと割り切れる。1個のタスクだけだと、感情推定に特化した重みが学習される。multi-task learning にして隠れ層を共有すれば、それなりの汎用性を持つようになる、かもしれない。

ここでは構成性が仮定されている。意味を担う単位は単語で、それより大きな塊は合成によって得られる。WSD 的な解釈では、単語自体は多義で、特定の文脈で特定の語義が採用されると思うのだが、既存の研究はそういうモデル化をせずに、単純なモデルで攻めているっぽい。

おわりに

ニューラルネットと聞いて、あえて素人的な発想をするなら、脳である。意味は何らかの形で脳内に保持されているのだろう。脳と言えば、ニューロンで、そのネットワークである。そんなこんなで、よく分からない連続値の羅列が意味なんだと言われるとそうかもしれない。その方向に突撃すると未来があるかもしれない。しかし何かに負けた気がする。その対極として、論理の世界がある。分布仮説的な意味と論理の意味が統合される未来が想像できない。

2013-12-21

Randomized Pruning

Alexandre Bouchard-Côté et al. Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs. NIPS 2009. (pdf)

時間があいてしまったが、前回と同じ話題。sampling 時に pruning を行う手法。前回はいずれも slice sampling に基づいていたが、今回はかなり違う発想。そこが面白い。

あらかじめ断っておくと、使い勝手は悪い。sampling 対象とは別個に、簡単に計算できる別のモデルを用意しておく必要がある。論文の実験では、bitext parsing をするのに、Berkeley Aligner を使っている。機械翻訳の人は、簡単なモデルからはじめて徐々に複雑にしていくのに慣れているかもしれない。でも他の分野はそうでもない。

第一著者は、以前紹介した言語系統樹を与えて祖語の語形を推定する話の人。ちゃんと統計がわかっている人。MCMC sampling の使い方も王道的。表題にあるように、期待値計算の近似に用いる。私を含む他の言語処理関係者が、sampling を randomized search としてしか使っていないのとは大違い。

trick は大きく2つ。ひとつは pruning mask を分解していること。もう一つは MCMC にメタな MCMC を設けていること。論文はこの順番に説明しているが、ここでは後者を先に見る。

今回は blocked Gibbs sampling になっていて提案が常に受理されるが、Metropolis-Hasting の提案分布を考えた方がわかりやすい。MH の提案分布はパラメータを持っている。例えば、ガウス分布で random walk するなら分散パラメータとして持つ。普通はこのパラメータは固定しておいて MCMC を走らせる。でも、パラメータの値の集合を用意しておいて、適当に交代させても MCMC としては問題ない。例えば、ガウス分布なら、大きな分散と小さな分散を用意しておけば、ドツボにはまって動けなくなるのを防げそう。これをさらに一般化すると、パラメータ自体MCMC で遷移しても大丈夫ということになる。

注意が必要なのは、このメタな MCMC は、sampling 対象の MCMC (e.g., bitext parsing) の状態とは別個に構成していること。言い換えると、元の MCMC の状態を見ながら遷移の仕方を変えているわけではない。これが理由で、本来の sampling 対象とは別個に、簡単に計算できる別のモデルが必要となる。このモデルの出力を適当に加工して遷移パラメータを決める。

MCMC の状態を見ながら遷移の仕方を変える手法を adaptive MCMC というらしい。adaptive MCMC の論文を眺めると、たかが Gaussian の提案分布を adaptive にするだけでも、ちょっと間違えれば不正確になってしまう。正しく構成するために大変な議論が必要になっている。adaptive にできないと決まったわけではないが、無理ゲー感が漂っている。

話を元に戻す。やりたいことは、候補数の爆発を抑えるための pruning。確率の高そうな候補群だけを考えたい。しかし、同時に sampling として正しく構成したい。例えば、常に pruning されるセルがあるとまずい。確率が低いセルにも低い確率で訪れる必要がある。

論文では CKY を例に説明している。pruning によりセル単位で枝刈りしていくことになる。簡単な別モデルを使うと、確率の高そうなセルの集合が得られる。こうして得られる新しい集合を直接 pruning に使う、つまり、残りのセルを pruning してしまうと、正しい sampling にならない。

ではどうするかというと、もう一つの trick の出番。mask (セルが keep か prune かを決める) を selection と assignment という2つに分解して構成している。selection はメタな MCMC で得られるもの。各セルに selected か excluded かいずれかの値を付与する。次の状態への遷移をどうするかというと、現在 selected なセルの一部を取り除いて、代わりに別モデルから得られるセル集合の一部を加える。

assignment は現在採用されているセル集合。sampling 対象の MCMC の状態では、いくつかのセルが採用されて構文木が作られている。

selection と assignment から決定的に mask が作られる。mask は selected なセルに関して発動する。あるセルが selected でかつ assigned (論文の用語で positive) なら、それと競合するセルを prune する。セルが selected でかつ unassigned (negative) なら、そのセルを prune する。残りは keep。

何が起きるかというと、いま採用されているセルは必ず keep される。残りが pruning の候補となるわけだが、selection の状態の変化によって、pruning の対象がちょっとずつ変わっていく。そのため、確率の低いセルもその確率に応じて採用できる。

あとは細かい話。結局 slice sampling と同じく、補助変数を導入していることになる。決定的な処理をいろいろやっているけど、それを確率の形で表しているから理解しにくい。

最初に言ったように使い勝手は悪い。前回見たように、slice sampling による pruning も微妙な点がある。何が大変かというと、対象の分布からの正しい sample を得る部分。でも、そもそも sampling を randomized search としてしか使っていないなら、本当にそこを頑張る必要があるのか怪しい。不正確なのを承知のうえで beam search しても良いんじゃないかと思えてくる。

2013-11-04

Slice Sampling for Pruning

Markov chain Monte Carlo による sampling 時に pruning したい。そのために slice sampling を使う手法。何年遅れて人のあと追いかけてるんだって話だが、細かい話題がいろいろあるので書き出してみる。

slice sampling

slice sampling 自体は (Neal, 2003) で提案された手法。当初の目的は普通に sampling すること。アイデアは単純だけど、連続分布に対して実装しようとすると途端に面倒になる。doubling とか shrinking とか。情弱には厳しい。

実物をはじめて見たのは Mark Johnson の adaptor grammar の実装。Pitman-Yor 過程の2個のパラメータを slice sampling で求めていた。ちなみに、今だったらこうはしない。Yee Whye Teh の方式で、パラメータに事前分布を置いて事後分布を sampling する方が簡単。式の導出は、というかどうしてこんな方法を思いつくのか意味不明だけど。

iHMM

slice sampling を pruning に応用したのは (Van Gael+, 2008) が最初だと思う。Teh と Ghahramani が共著者に入っていて恐ろしい。この論文は提案手法を beam sampling と呼んでいる。でも、なぜか以後の論文は追従していない。

iHMM は hidden Markov model で、Dirichlet 過程を使って隠れ状態のタイプを無限に拡張している。提案手法以前は、隠れ状態の変数を1つずつ Gibbs sampling していた。1 個だけを対象とするなら、既存のタイプか、未観測のタイプかで場合分けすれば良い。しかしこの手法は mixing が遅い。

効率を上げるために文単位で block sampling したい。しかし、状態のタイプが無限にあるので、動的計画法が使えない。そこで slice sampling が登場する。このあたりから中身を見ていく。

そもそも slice sampling は補助変数を追加するという trick を使っている。sampling したい元の分布を p(z) とすると、補助変数 u を追加して、同時確率 p(z,u) を考える。補助変数 u は好きに設計すれば良い。とにかく p(z,u) は、これはこれで立派な分布だから、 Gibbs sampling が行える。p(z)=\sum_u p(z,u) だから、p(z,u) からの集めた sample から単に u を落とせば、p(z) からの sample になる。

Gibbs sampling では、p(u|z)p(z|u) を交互に sampling する。通常通り。問題は p(u|z)設計だが、注目している値が小さい、つまり pruning したいときに、0 をとるようにする。そうすると p(z|u)=0 となって候補から外れる。

iHMM の場合は、遷移確率 \pi_{s_{t-1},s_t} を pruning の対象とする (s_tは隠れ状態)。p(u_t|s_{t-1},s_t,\pi)=\frac{\mathrm{I}(0<u_t<\pi_{s_{{t-1},s_t}})}{\pi_{s_{t-1},s_t}} とする。この分布は u_t積分するとちゃんと 1 になる。手続き的には u_t \sim \mathrm{Uniform}(0,\pi_{s_{t-1},s_t}) に従って sampling する。

p(z|u) を sampling するとき、隠れ状態 s_t に着目すると、u_t は固定。\pi_{s_{t-1},s_t} \leq u_t となる \pi_{s_{t-1},s_t} については、p(z|u)=0 となるから考えなくて良い。pruning される。u_t < \pi_{s_{t-1},s_t} を満たす \pi_{s_{t-1},s_t} のみを考える。そうした候補は有限なので forward-backward が使える。

言い忘れていたし、だから上記の式は不正確なのだが、\pi_{s_{t-1},s_t}積分消去していない。従来の Gibbs sampling の場合は積分消去していたけど。slice sampling を使うときには、\pi も sampling する。Teh の黒魔術を使って。だから p(u|z,\pi), p(u|z,\pi) と書いた方が正確。

p(z|u) の導出が論文の式 (4)。\pi_{s_{t-1},s_t} は打ち消し合って最後の式から消える。何だか不思議な感じ。

p(u|z,\pi)p(z|u,\pi)\pi は共通の値。*1だから、p(z|u,\pi) からの sampling 時、各状態遷移について、少なくとも 1 個の \pi_{s_{t-1},s_t} は必ず pruning から生き残る。sampling 前の z の値をそのまま使えば良い。だからすべての候補が pruning されて HMM の path が通らないということはない。どうしてパラメータ積分消去をやめてしまったのかと最初は思ったけど、恐ろしい人たちが共著者に入っていることだし、よくよく考えてのことだろう。

infinite mixture model に slice sampling を適用した例も iHMM と似た感じ。*2stick-breaking representation で明示的に Dirichlet 過程からの sample を考えて、棒の高さで slice する。

PCFG

(武井+, 2009) という論文を最近みつけた。国内だけど、IBIS という恐ろしい集まりの発表。

PCFG (ただし Chomsky 標準形に限る) に slice sampling を適用している。何が困るかというと、HMM の場合と違って、補助変数の設定が難しい。p(u|z) から sampling しようと思っても、z は CKY の chart の一部の cell しか埋めない。残り cell の扱いに困る。提案手法は split position というのを考えて、tricky に数合わせを行っている。何しろ tricky なので、例えば semi-Markov な単語分割には適用できない。

引っかかるのは、iHMM の場合と違って、パラメータ積分消去をしたまま slice sampling を行っていること。PCFG なので導出確率 \theta_{A \rightarrow B C} があるが、共役性を利用して積分消去してしまう。z 中のカウントと hyperparameter で擬似的に \theta^\prime を考えている。とすると uz 全体に依存していることになる。まじめに graphical model を考えると恐ろしいことになる。u設計は何でもありなので、これ自体は問題ないだろう。

問題なのは、擬似的なパラメータ \theta^\prime の扱い。普通に Gibbs sampling すると、以下の手順に従う。

  • p(u|Z) から u を sampling
  • z のカウントを decrement
  • p(z|u,Z^{-}) から sampling
  • z のカウントを increment

Step 2でカウントを decrement するから、\theta^\prime の値が Step 1 で u を sampling したときから変わってしまう。運が悪いとすべての候補が pruning される気がする。

SCFG

(Blunsom+, NAACL2010) は SCFG に slice sampling を適用している。SCFG は機械翻訳に使う PCFG の拡張で、2 言語を同時に導出する。機械翻訳の常だが組み合わせ爆発地獄。普通に動的計画法で parsing しようとしても、遅いどころか、現実的な時間内に終わらない。そこで slice sampling で pruning しようというもの。

short paper なので全然 self-contained ではない。あたかも \theta という導出確率を持っているような書きっぷり。でも、(Cohn+, ACL2009) で提案した collapsed Gibbs sampler のモデルから変更したとは書いていない。積分消去して得られる擬似的なパラメータを使っているのだろう。そうすると、PCFG の場合と同じく候補全滅のおそれがありそう。

SCFG は PCFG の拡張なので、PCFG と同じく、zcell を埋め切らないという問題がある。Blunsom らは、z が未使用の cell も含めて、すべての cell に補助変数を設定している。z が未使用の場合は u_s \sim \mathrm{Beta}(a,b) と、ベータ分布を使っている。\theta の確率をまったく無視して u_s を決めているから、全滅する cell が続出する。これは Blunsom らの意図通り。そもそもすべての cell を見て回るだけでも大変だから、cell をまるごと pruning していくらしい。

p(z|u)、あるいはこの論文記法に従うと p(d|u) は、式 (2-4) で求められている。CFG で木の確率を求めるというのに、導出確率 \theta が打ち消されて最後の式には出てこない。しかしこの式変形は間違っているのではないかと思う。p(u|d) から sampling するときに使った、前の状態の d と、今まさに sampling しようとしている d を混同している。本当は \theta は打ち消されないはず。識者の意見を乞う。

雑感

iHMM, PCFG, SCFG と見てきたが、いずれも pruning 対象は 1 個のパラメータ。iHMM なら遷移確率、PCFG/SCFG なら導出確率。1 個のパラメータだから、生き残って欲しい候補は (0, 1) のなかで適当な範囲に収まっている。だから適当に u_s \sim \mathrm{Beta}(a,b) で足切りするといった乱暴なことが可能となる。

普通の beam search だと、ある時点での one-best を基準に pruning を行う。上位 K 個とか、one-best の10^{-10} までとか。これはパラメータの組み合わせなので、生き残って欲しい候補であっても極端に小さな値になる。そうなると、決め打ちパラメータベータ分布で足切りなんてできない。意外と使い勝手が悪い。

*1p(u|z,\pi) からの sampling と p(z|u,\pi) からの sampling の間に、p(\pi|z,u)=p(\pi|z) からの sampling をするといった妙なことを行わなければ。

*2:実はもともとこちらのほうが (Van Gael+, 2008) より早い。