mots quotidiens.
Daichi Mochihashi (持橋大地) daichi <at> ism.ac.jp by hns, version 2.10-pl1.

先月 2024年03月 来月
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

2021年04月14日(水) [n年日記]

#1 NPMIによる教師なしフレーズ認識

Mikolov+(2013)の有名な Word2Vecの論文 では, 単語ベクトルを作る際に, "New York" や "Toronto Maple Leafs" (アイスホッケーチーム)の意味は要素である "new" や "maple" "leafs" とは基本的に 関係ないので, 先にフレーズを認識して "new_york", "toronto_maple_leafs" と 単語をまとめてからWord2Vecを適用する方法が述べられています。 もちろん固有表現認識(NER)を動かせばできますが, NERは事前に人が作成した教師データに依存する ため, 教師データを使わない方法として, word2vecの論文では単語vと単語wがフレーズとなる スコアを
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を計算しているので,

という欠点を解消した, Normalized PMI (NPMI)(Bouma 2009) を使えばよいような気がします。NPMIは, 次のようにして定義されます。
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つのフレーズと認識されています。「御樋代木奉曳式」(みひしろぎほうえいしき)は木曽で切り出された御料木が伊勢神宮に運ばれる儀式のことのようですが, こうした特殊な語彙のため形態素解析に失敗していても, フレーズ認識で一単語と認識することができています。
ただ今回, 先頭から最長一致でフレーズ化しているため, 「〜_っと_!_お_ジャ_魔女_どれ_み」「『_機動_戦士_ガン_ダム_seed」は本来は, 後から伸ばすことでもっと正確に認識できる名前ではないかと思います。 なお, 「絶叫_カオス_傑作_選_大声_クイズ_vs_谷_桃子_vs_ヒム_子」は何と12単語からなる フレーズ(!)で, これは こういうバラエティ番組のDVD の名前であるようです。
認識された長いフレーズのリストの例は, こちらに置いておきました。 バイグラムを結合するときの頻度を10以上などにすると, より綺麗なフレーズが 得られますが, 頻度の低い長いフレーズは認識されなくなります。 頻度を1以上にした場合の, 面白い長いフレーズの例を, 自分用メモも兼ねて こちらに置いておきます。

下に, フレーズを認識するPythonスクリプトを置いておきます。 使い方はそのまま実行してヘルプを読むか, 中身をご覧下さい。


2009年04月14日(火) [n年日記]

#1 ACL-IJCNLP 2009

ACLに通りました。
"Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling".
Daichi Mochihashi, Takeshi Yamada, Naonori Ueda, ACL-IJCNLP 2009, to appear.

これで落ちたら完全にACLを見限るところだったので, とりあえずよかった, と思います。 *1

ただ, Accepted Papers を見ると, 明らかにACLレベルなものとかなりmarginalに見える論文が混じっていて, 微妙な感じもします。
実際, 査読の時に明らかに素晴らしいアイデアだと思った論文が通っていなかったり して, *2 きっとどうでもいい細かい所をつつかれて落とされたんだろうな, という気がします。 通っていないので, 内容を紹介できないのが非常に残念ですが..。
僕の話も, アイデアは非常に素晴らしいと言いながら, どうでもいい瑣末な部分で 点数が下げられたりしていて(しかもそれが誤解だったりする), かなり細かい所に気を使わないといけないようです。


*1: これまで, 「難しくて理解できない」とか意味不明な落とされ方をされ続けて きました。
*2: 最初, 希望通りに僕に割り当てられましたが, 最終的に別の人が査読することになった らしい。

2008年04月14日(月) [n年日記]

#1 MCMC PCFG

研究に関係して, Mark Johnson, Tom Griffiths, Sharon Goldwaterの "Bayesian Inference for PCFGs via Markov Chain Monte Carlo" (NAACL-HLT 2007) を読んだ。面白い。

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なので, 各規則に対するパラメータの最適化が独立ではない, という利点があるのだと思う。

具体的には,

という2つのパターンになる。 後者の場合, 内部ではθとして事後分布の期待値を使ったものをproposalとして, 前の構文解析の尤度と比べて, 新しい構文解析をacceptするかどうかを 決めるらしい。
結果的には, 性能は普通の文に関しては *1 Inside-outsideを使った通常の最尤推定と同様にあまり良くない(与えられたPCFGが 自然言語を記述するのに充分でない)そうですが, 面白かったのは, 文wに対して, 構文木tを「サンプリングする」というところ。
これは, 先に文に対してinsideテーブルを動的計画法で計算しておいて,
(j,A,B) = Mult(X,w)
のようなサンプリングをトップダウンに, 再帰的に適用することで 構文木をサンプリングする方法。
Mult(X,w) は, 非終端記号Xとみた文字列wに対して, これを位置jで切って左側をA,右側をBに展開するペア(j,A,B)を確率的に返す関数。 Mult(S,w) から始めると, S->NP VP のような可能性と, 切る位置 j が 返され, 今度は左側と右側の部分文字列に対して, それぞれNPとVPなので, NP->DT N や NP->N のような展開の可能性に対して同様に再帰的にサンプリングを 行って, 最終的な単語列を得ることができる。
上の(j,A,B)はp(j,A,B|X)の意味なので,
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


*1: 論文では, バントゥー語の膠着的な動詞の解析をMCMC-PCFGで行って, 全体が1つの 動詞だという自明な結果になる最尤推定と比べて, 意味のある分節化が得られた という話が書いてあります。
*2: プログラムはC++としては綺麗なのだと思いますが, ギチギチに詰まっていて 暗号のようなので, 個人的には, こういうプログラムはocamlで書きたいなぁ.. という気になります。
*3: もちろんViterbiで解析するのも簡単。

3 days displayed.
タイトル一覧
カテゴリ分類
 なかのひと
Powered by hns-2.10-pl1, HyperNikkiSystem Project