|
mots quotidiens. | |
| Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp | by hns, version 2.10-pl1. |
|
||||||||||||||||||||||||||||||||||||||||||||||
score(v,w) = (n(v,w) - δ)/(n(v)*n(w))とする, という方法が述べられています((6)式)。 ここでn(v,w),n(v),n(w)はバイグラムおよびユニグラム頻度で, δは, 頻度の低いペアが上位に来るのを抑えるためのディスカウント係数です。
上のスコアは, 確率として考えると, ユニグラムの総和をNとして p(v,w)=n(v,w)/N, p(v)=n(v)/N, p(w)=n(w)/N なので, δの部分を除くと,
score(v,w) = n(v,w)/(n(v)*n(w)) = (p(v,w)*N)/(p(v)*N * p(w)*N) = p(v,w)/(p(v)*p(w)*N)となり, ほぼ, 自己相互情報量 PMI(v,w) = log p(v,w)/(p(v)*p(w)) と同じスコアを計算していることになります。
ただしよく見ると, 元の式には 1/N というファクターが入っており, これは コーパスに依存する ので, スコアが基本的にコーパスの長さに依存したものになってしまいます。 コーパスを固定して閾値を探索するのであれば問題ありませんが, 閾値の意味がわかりにくい上, 長さの違うテキストを使って結果を比べたい場合などでは, 同じ基準のフレーズにはならなくなってしまいます。
元のスコアにNを掛けてコーパス非依存にすることもできますが, そもそもこのスコアは本質的にPMIを計算しているので,
NPMI(v,w) = log p(v,w)/(p(v)*p(w)) / (-log p(v,w))NPMIは -1≦NPMI(v,w)≦1 の範囲で定義され, 1のときにvとwは完全に相関, -1のときに完全に逆相関という, 非常にわかりやすい基準になっています。 しかもPMIにあった「p(v)やp(w)が非常に小さい時にスコアがインフレしてしまう」 という欠点も解消されているので, こうすると, word2vecの元論文にあったヒューリスティックなディスカウント係数 δも不要になります。
というわけで, 少しスクリプトを書いて, フレーズの自動認識を試してみました。 核心部だけ書くと, unigram, bigram にそれぞれユニグラムとバイグラムの頻度が 辞書として保存されているとき, 単語バイグラム(v,w)がフレーズとなるかどうかは次のようにして 判定できます。
def compute_phrase (unigram, bigram, threshold=0.5):
N = sum (list(unigram.values()))
phrases = {}
for bi,freq in bigram.items():
if freq > 1:
v = bi[0]; w = bi[1]
npmi = (log(N) + log(freq) - log(unigram[v]) - log(unigram[w])) \
/ (log(N) - log(freq))
if npmi > threshold:
phrases[bi] = npmi
return phrases
閾値は, 試したところでは0.5くらいにするのがよいようです。
これをテキストについて1パス動かすと2単語のフレーズが得られ,
それを入力にして2パス目を動かすと2〜4単語のフレーズが得られます。
同様にしてnパス動かすと, 2〜2^n単語からなるフレーズが得られます。
日本語版text8
(100MB, 56万文, 1694万語)について4パスで動かしてみたところ,
次のようになりました。
甲_越_同盟 （ こう え つどう めい ） は 、 天正 7 年 （ 1579 年 ） に 甲斐 の 戦国_大名 武田_勝頼 と 越後 の 戦国_大名 上杉_景勝 と の 間 で 成立 し_た 同盟 。 定義 上 は 超_硬_合金 と 呼ば_れる 炭化_タングステン ( wc ) を 主成分 と し_た もの も 含ま_れる が 、 これ を 別 の もの として 扱う こと が 多い 。ここでは「甲越同盟」「戦国大名」「武田勝頼」「した」「超硬合金」「炭化タングステン」「呼ばれる」「含まれる」 などが, 統計的に自動的にフレーズとして認識されています。 通常のNERでは教師データに依存するため, 「甲越同盟」「超硬合金」などを認識するのは難しいと思われるため, これは非常に有用だと思います。 もちろんこれは word2vec の元論文のときからできていたわけですが, 上に書いたように基準がデータ依存で, 低頻度語に弱い(&それを避けるためのヒューリスティックなパラメータに依存する)という問題があったため, NPMI>0.5という基準は非常にわかりやすく, 有用なのではないかと思います。
なお, 4パスなので原理的には16単語までの単語がフレーズとして認識される可能性が あるわけですが, 調べてみると, 「福島_第_一_原子力_発電_所」などはもちろん フレーズとして認識されている他, 非常に長いものとしては以下のようなものがありました。(一部抜粋)
第_二_次_世界_大戦_末期 福島_第_一_原子力_発電_所_事故 連合_国軍_最高_司令_官_総_司令_部 全国_高等_学校_野球_選手権_大会 学研_奈良_登美_ヶ_丘_駅 国際_連合_安全_保障_理事_会 ユーゴスラビア_社会_主義_連邦_共和_国 全国_高等_学校_サッカー_選手権_大会 ニューヨーク_州立_大学_バッファ_ロー_校 全日本_実業_団_対抗_駅伝_競走_大会 芸術_選奨_文部_科学_大臣_賞_受賞 mf_文庫_j_ライト_ノベル_新人_賞 〜_っと_!_お_ジャ_魔女_どれ_み ufc_世界_女子_ストロー_級_タイトルマッチ pc_エンジン_オール_カタログ_'_93 独立_行政_法人_産業_技術_総合_研究所 国際_連合_難民_高等_弁務_官 ほっ_かい_どう_さ_っぽ_ろ ほっ_か_ほっ_か_亭_総本部 『_機動_戦士_ガン_ダム_seed 学_研究_科_修士_課程_修了 御_樋_代_木_奉_曳式 絶叫_カオス_傑作_選_大声_クイズ_vs_谷_桃子_vs_ヒム_子「福島_第_一_原子力_発電_所_事故」は7単語, 「連合_国軍_最高_司令_官_総_司令_部」は8単語がまとまって1つのフレーズと認識されています。「御樋代木奉曳式」(みひしろぎほうえいしき)は木曽で切り出された御料木が伊勢神宮に運ばれる儀式のことのようですが, こうした特殊な語彙のため形態素解析に失敗していても, フレーズ認識で一単語と認識することができています。
下に, フレーズを認識するPythonスクリプトを置いておきます。 使い方はそのまま実行してヘルプを読むか, 中身をご覧下さい。
これで落ちたら完全にACLを見限るところだったので, とりあえずよかった, と思います。 *1
ただ,
Accepted Papers
を見ると, 明らかにACLレベルなものとかなりmarginalに見える論文が混じっていて,
微妙な感じもします。
実際, 査読の時に明らかに素晴らしいアイデアだと思った論文が通っていなかったり
して,
*2
きっとどうでもいい細かい所をつつかれて落とされたんだろうな, という気がします。
通っていないので, 内容を紹介できないのが非常に残念ですが..。
僕の話も, アイデアは非常に素晴らしいと言いながら, どうでもいい瑣末な部分で
点数が下げられたりしていて(しかもそれが誤解だったりする),
かなり細かい所に気を使わないといけないようです。
PCFGはS->VP NP, NP->DT NN, DT->"the", N->"cat" のような生成規則と,
S->NP, S->VP, S->VP NPのように非終端記号を展開する複数の可能性があった時に,
それぞれが使われる
θ=[0.05, 0.2, 0.75]のような確率分布からなる。PCFGのベイズモデルは,
この確率分布がディリクレ分布から生成されたとするもの。
ディリクレ分布のハイパーパラメータαを小さくすることで, θが偏った分布である
という仮定を置くことができ, 関係するデータ量が少ない場合でも最尤推定に比べて
安定した推定が可能になる。
PCFGをベイズ化するという話自体は
栗原君
が変分ベイズで
前にやっている
のですが(この論文でどうして引用されていないのか謎ですが..), 今回はMCMCなので,
各規則に対するパラメータの最適化が独立ではない, という利点があるのだと思う。
具体的には,
(j,A,B) = Mult(X,w)のようなサンプリングをトップダウンに, 再帰的に適用することで 構文木をサンプリングする方法。
p(j,A,B|X) ∝ θ(X->A B)p_A(w(i,j)|θ)p_B(w(j,k)|θ)として確率が計算できる。ここでp_X(s|θ)はパラメータθの下で, 非終端記号Xが 文字列sになる確率で, inside確率を計算しておくと求まる。
さて, Mark Johnsonのページ を見ると, C++の実装 gibbs-pcfg.tgz が置いてあったので, ちょっと試してみました。
wave:/tmp/gibbs-pcfg% ./gibbs-pcfg -n 5000 -a 0.01 -A result -G grammar testengger.lt < testeng.yld wave:/tmp/gibbs-pcfg% v grammar 1 ROOT --> S 1 S --> NP VP 1 NP --> Det N 7.84215e-34 VP --> V 0.651455 VP --> V NP 2.6057e-61 VP --> NP V 0.348545 VP --> V NP NP 3.9252e-13 VP --> NP NP V 0.39633 Det --> the 1.58667e-15 N --> the 3.2873e-06 V --> the 0.600561 Det --> a 4.70053e-09 N --> a 1.61862e-10 V --> a 2.81297e-35 Det --> dog 0.264735 N --> dog 7.40429e-45 V --> dog 3.32051e-47 Det --> man 0.465411 N --> man 5.02489e-19 V --> man 1.27336e-08 Det --> bone 0.269448 N --> bone 2.87335e-27 V --> bone 5.31171e-77 Det --> bites 0.000406084 N --> bites 0.49108 V --> bites 0.00310949 Det --> gives 6.50102e-09 N --> gives 0.508917 V --> gives wave:/tmp/gibbs-pcfg% v result (ROOT (S (NP (Det the) (N dog)) (VP (V bites) (NP (Det a) (N man))))) (ROOT (S (NP (Det the) (N man)) (VP (V bites) (NP (Det a) (N dog))))) (ROOT (S (NP (Det a) (N man)) (VP (V gives) (NP (Det the) (N dog)) (NP (Det a) (N bone))))) (ROOT (S (NP (Det the) (N dog)) (VP (V gives) (NP (Det a) (N man)) (NP (Det the) (N bone))))) (ROOT (S (NP (Det a) (N dog)) (VP (V bites) (NP (Det a) (N bone)))))
かなり妥当な結果になっているのが面白い。 データが少ないのでこの解析は5秒くらいですが, Gibbsのiterationを少なくすると, 正しくない解が出ることもあるのがMCMCっぽい。 *2
これまで, 構文解析は自分にはあまり必要がなかったのと, 動的計画法で効率的に 計算するというのは離散数学の常なので, ふーん, よかったね, という感じだった のですが, こうやって具体的に構文木をサンプリングできるというと, がぜん 面白いような気がします。 いわゆる構文解析のN-bestはビタビの拡張でビームサーチをしているのでは ないかと予想するのですが(多分), バラエティを増やして安定した推定を 得るためには, こうやって確率的に正しい構文解析結果をサンプリングする, というのも興味深い感じです。
なお, この論文ではPCFGの規則を人手で与えていますが, これは The Infinite Tree のような形で, 係り受け解析結果からノンパラメトリック ベイズで学習することができそうです。 ので, ありそうな方向としては, 係り受け解析済み(係り受け解析なので文法的なタグ はない)に対して, The Infinite Tree でPCFGを教師なし学習して, この論文のような 形で構文木をサンプリングするのは面白そうです。 *3
| タイトル一覧 | |