[2000] Maximum Entropy Markov Models for Information Extraction and Segmentation

[yoheikikuta]

論文リンク

https://dl.acm.org/citation.cfm?id=658277

公開日（yyyy/mm/dd）

2000/06/29

概要

自然言語処理のタスクの多くは観測系列が与えられた上で状態系列を予測するというもの（だけ）である。 従来良く使われていた HMM は生成モデルであり、識別モデルではないがベイズの定理を経由することでこういう問題にも適用できていたが、問題設定を考えればこれは素直な解き方ではないし、overlapping feature が使えないなどの不都合も生じる。 この論文では Maximum Entropy Markov Model という識別モデルを導入する。これは P(s|s',o) という形で前の状態と観測を given にして状態をモデリングするもので、解きたい問題に対してよりストレートなアプローチになっている。多項分布などの性質の良い確率モデルが使えない分に関しては、素性を導入してそれを制約にした最大エントロピー法でモデリングをするという形にしている。 これによってかなり柔軟な特徴量エンジニアリングができるようになり、実際に識別問題に関しては HMM よりも高い性能を発揮するということを示した。

[yoheikikuta]

系列ラベリングの勉強をしようと思って、それにはやはり Conditional Random Field の原論文を読んでみることだろうという話になるかと思うが、その前にこの MEMM の論文を読んでおくのが良いと教えてもらった。ので読む。

そこそこ古い論文ではあるけど、この辺りの知識はあまりないので、ちょっと真面目に原論文を読んでいこうかなという趣旨。

[yoheikikuta]

まずどんな問題を解きたいという話から始まっているかを考える。

基本的には、sequential data をうまくモデリングすることで自然言語処理のタスクを解きたいと思っていて、具体的には以下のようなタスクである。

• Part Of Speech (POS) tagging 品詞を推定する問題。ナイーブには各単語に品詞が付随しているものだと思えば、この品詞を推定することはテキストデータを理解する上で重要になる。例えば品詞のリストは こういうの があったりするが、どういう粒度でラベル付けをするかは問題依存。品詞は順番が大きな情報を持つ（例えば英語なら主語の後は動詞が来やすい）ので、それを踏まえた系列モデリングは重要となる。ちなみに系列を考えずに 単語:品詞=1:1 の関係で予測するものは点予測と呼んだりする。
• text segmentation 与えられたテキストを適当な単位で分割するタスク。例えば、複数の文章から成るテキストを文章毎に分割したり、様々なトピックの話題が記述されているテキストに対してそれをトピック毎に分割したり、というもの。あまり取り扱ったことがないのでもっと具体的なものを考えてみる。 Wikipedia の記事を table of contents に従い分割する。そうすと n 個の sentence とどこの sentence で分割されているかというデータが作れる（{0,0,1,0,1} なら sentence が 6 つあって、3 つ目の sentence で一つ目のトピックが終わり、5 つ目の sentence で二つ目のトピックが終わり、という具合だ）。これは確かに sentence 系列を入力としてラベルを予測する問題として定式化できる。

その他にもたくさんあるが、まあ典型的にはこういうものを解きたいわけだ。

[yoheikikuta]

従来までどう解いていたのか。 ここでおなじみ Hidden Markov Model (HMM) が登場するわけだが、ここはなかなか考えさせられるところだ。

まず HMM には教師あり（観測系列に対して対応する状態系列のラベルが与えられている）と教師なし（状態系列のラベルが与えられていない）の両方を取り扱うことができる。それぞれをどうやって学習するのか、ということは一旦置いておいて以下のような例が考えられる。

教師ありの場合。 音声認識で特徴量系列を生成する音響モデルとしての利用するようなものが挙げられる（必ずしもラベルありの状況だけでなくて連結学習などあるが、まあここではそれは置いておく）。 データから学習したモデルがあれば、どのような特徴量系列が生成されるかの確率を求めることができるため、確率的にモデリングするための生成モデルとして機能している。 また、ベイズの定理を使うことで観測系列が与えられた状況で状態系列を推測をすることもできるため、それによって音声認識（の一部）として機能することができる。

教師なしの場合。 例えば状態として {正常, 異常} は与えられるが観測系列にそれらのラベルがついていないようなセンサーデータなどに対して適用することができる。これも学習済みモデルがあれば、観測系列が与えられた時に正常か異常かを推測することができる。

例えば今回考えている POS tagging などは基本的には教師あり学習の方として扱うことができる。 状態に対応するものが品詞で、これが求めたいものになっている。なので観測系列を所与とした際の状態系列が知りたいというわけだ。 趣が異なる点は、別に観測系列を確率的に生成したいというモチベーションは特にないというところだ。音声認識でも別に生成はしなくてもいいんじゃないかと言われるとまあそうかもしれないが、音声合成には必要だし、話の都合上そういうことにしておく。 つまり、従来通り HMM を使って解ける問題であるわけだが、なんというか直接的な解き方ではないというのは納得できる。直接的なのは観測系列を所与として状態系列を推測するというものを素直にモデリングしたものであろう。

[yoheikikuta]

となるとなぜ最初から素直に解かないのか、という疑問もわくが、論文で以下のように言われてもいるように、やはり HMM が広範に利用可能でよく知られているモデルだったからということなんだろう。多分。

Greatly contributing to their popularity is the availability of straightforward procedures for training by maximum likelihood (Baum-Welch) and for using the trained models to find the most likely hidden state sequence corresponding to an observation sequence (Viterbi).

[yoheikikuta]

論文の導入で書かれている HMM を使う問題点は二つ。

• overlapping feature を扱えない overlapping feature は例えば単語と overlap している情報で大文字か否か、記事の上の方に現れているか否か、などの feature を表す。例えば固有名詞を判断する際に大文字か否かなどが効果を発揮するのは想像に難くない。HMM ではこういうものを取り扱いづらい。状態系列とどう結びつければいいかわからないし、そういうものの多項分布考えたところで意味があるのか、という話になってしまう。ということでそういう feature も取り込めるモデリングがしたい、というのは素直な要望に思える。
• 解きたい問題に対して inappropriate に生成モデルを使っている ちょっと言葉が強い気もするが、話としては上で紹介したように、観測系列を所与として状態系列を推測するような直接的なモデリングが良いだろう、ということだ。多くのテキスト分析はこういう形になっている。

これらを解決するために導入されたものが Maximum Entropy Markov Model (MEMM) である。 グラフィカルモデルとしては以下のようになっている。

グラフィカルモデルから分かるように、左は $ P(s|s') P(o|s) $ で右は $ P(s|s',o) $ という形で表現される（ここでは $ s' $ を一つ前の状態としている）。

[yoheikikuta]

具体的なモデリングを見ていく。

まず、 $ P(s|s',o) $ を $ |S| $ 個の別個に学習する遷移確率とみなして $ P_{s'} (s|o) = P(s|s',o) $ と表現する。 $ s' $ が取りうる要素は全部で $ |S| $ 個あるということだ。 これは式をこのように書いているというだけで、こう書くことに特別な意味はない（と思う）。気持ちとしては、実際にこのモデルを使っていく時は前の状態 $ s' $ の要素を具体的に決めて $ p(s|o) $ を考えるということを意思表示しているという感じだろうか。例えば負の対数尤度を最小にする path を考える場合に、$ s' $ がある特定の要素の時に次の尤もらしい状態が取りうる要素を $ p(s|o) $ で決めてということを各 $ s' $ の要素でやっていく、みたいな。この段階ではこのように書く理由は特に見えてこないが、後で素性関数をつくるときに効いてくる。

このようなモデリングによって、パラメタ学習や観測系列が与えられたときの尤もらしい状態系列の推測、に関しては大きな違いはない。 マルコフ性によって、前状態と次状態を結ぶ各 path に関して前向き確率と後ろ向き確率を求めておけば道具としては事足りる。 HMM の場合は $ P(s|s') P(o|s) $ と表現していたものを $ P_{s'} (s|o) $ に置き換えればよい。

学習や推論の原理的な部分にはそこまで大きな差はないが、HMM のように遷移と観測を別個に取り扱ってないので、遷移部分のモデリングを観測の複数の非独立な特徴で表現することが可能になっている。これは、HMM の場合は観測部分が $ P(o|s) $ であり各観測は離散化した語彙に多項分布を当てはめるという感じで語彙と overlap のある大文字かどうかなどを表現できないものだったが、$ P_{s'} (s|o) $ という形ならばそのような制限はない。

制限はないが、多項分布のような性質の良い確率分布を使うことができないという代償があるので、それをどうするかというのがモデリングの主題となる。 結論から先に言ってしまうと、ここでは最大エントロピー法を使う。 最大エントロピー法は具体的で性質の良い確率分布を使えない場合に有効な手法の一つで、平均などの統計量は再現するように制約し後はエントロピー最大（つまり uniform distribution に近く）となるように確率分布を表現する手法である。 例えば物理においては、気体分子のマクスウェル=ボルツマン分布の導出には運動エネルギーの期待値一定という制約のもとでエントロピー最大となる分布として $ p(v) ∝ exp (- a v^2) $ が得られるという感じである。 この辺の議論を追ったことがある人ならば、ラグランジュ未定乗数法で制約を入れてエントロピー最大となる極値を求めるというステップで、エントロピーの log p(x) + (制約) = 0 みたいな形が出てきて結果として exponential モデルが出てくるというので exp の形になるのは理解できていると思う。自分も知ってるのでここでは最大エントロピー法そのものにはあまり深入りはしない。

ここでもう少し真面目に考えたいのは制約の入れ方だ。 これは機械学習でよく使われるもので、素性というものを考える。 これからの議論は一般には binary feature である必要はないものだが、多くの場合で binary feature が使われる。例えば、観測された単語が apple という単語であるか否か、観測された単語が大文字であるか否か、という具合で好きな binary feature を構築することができる。逆に言えば良い feature を構築しなければならない。 上述のように $ P_{s'} (s|o) $ という $ s' $ の要素毎に $ P(s|o) $ を考えるので、素性 $ a $ は関数系として $ f_a (o,s) $ という形で与えられる（そういうものとして定式化したと言ってもよい）。この $ a $ は観測の binary feature $ b $ と状態 $ s $ で特徴付けられるものなので $ a = <b,s> $ と書くことにして、$ f_a (b,s) $ を次のように表現する。ちなみに $ a =<b,s> $ とか書けるのはいいとしてここでそうする意味はよく分かってない。

これをどうやって制約として入れるかという問題だが、この論文では、観測系列（とそれに付随する状態系列）における平均値と学習した分布での各 feature の期待値とが一致せよ、という制約を課す。

ここで、$ ti $ は $ s{ti} = s' $ であるタイムステップであり、すなわち $ P{s'} $ という遷移関数を含むようなタイムステップである。ここで忘れてはいけないのは $ P_{s'} $ は $ s' $ の各要素毎にモデル化しているということだ。最後まで行ってからその意味を改めて考える。 ともかくここでやっているのは各素性 $ a $ 毎に学習データから単純にカウントして平均したものが、学習した確率分布を使って再現できるようにする、というものだ。

最後にこの制約によって確率分布がどう表現されるかだが、これは最大エントロピー法から exponential モデルとなるので以下の形が得られることは容易に理解できる。$ λ_a $ がパラメタで Z は s に関して sum を取った正規化係数である。

考えてみるとこれは結構難しい表現になっている。 まず、これは $ s' $ の各要素毎に構築されるもので $ |S| $ 個の関数である。その意味としては $ λ_a $ は $ s' $ の各要素毎に学習される別のパラメタになっていて、その意味としては $ s' = s_1 $ と $ s_2 $ という異なる場合では観測は同じでも素性の重みが変わるということを言っている。これは確かにパラメタ数を無視すればその方が表現力が高いわけだし、またそうでなければこのモデルには前の状態の情報がうまく使えてないということも分かる。

そうするとこの Z に $ s' $ 依存性があるように書いてる意味も分かる。 これは規格化定数なので分母を $ s $ の全状態について足し上げたものになっているわけだが、分子には $ s' $ が陽に現れていないのに Z に $ s' $ 依存性を書いていて一瞬「？」となるところだ。しかし上述のように $ λ_a $ は $ s' $ がどの要素であるかによって値が変わるものであるので、ここに $ s' $ が入ってくるのはおかしくないというわけだ。

$ λ_a $ に $ s' $ 依存性があることを明記してくれた方が分かりやすいよなぁ。もちろんこれは $ s' $ の関数ということではなくて $ s' $ の各要素ごとに定められるパラメタということなので陽に $ s' $ を書いていないと思うが、理解は結構大変なところだ。

[yoheikikuta]

MEMM の本質的な主張はこんなもんである。 あとはこれの学習方法を理解し、実際に適当な素性 a を考えた上で実験をして本当に良いモデルなのかを検証する、ということをやっていく。

具体的な学習法などに入る前にいまいちど何をやりたかったのかを見直しておく。 自然言語処理などのタスクでよく遭遇するのは、観測系列が与えられた状況で何かしらのラベルを推測すること、そしてそれだけ、という状況である。つまり何かしらの生成モデルで観測系列を生成するということはいらないことが多い。 そのような状況では生成モデルである HMM を使うというのはモデリングとして素直ではないし、実際に overlapping feature を使えないなどの制約が存在する。 それを打破するために P(s|s',o) というモデリングを考案して overlapping feature を使用できるようにして、代償として性質の良い確率分布が使えない問題を最大エントロピー法に押し付けた、というのが MEMM の話である。さらに、何かしらのラベルを予測する際に使う特徴量を人手で与えられるようになったというモデリングの柔軟性もこの時点ではモデルの性能を上げるのに寄与していただろう（この時点では、というのは現在なら BERT とかで解いてしまう方がラクだが、くらいの意味）。

[yoheikikuta]

ということでモデルの学習の話に移る。 Generalized Iterative Scaling (GIS) という手法で学習する。どの辺が Generalized なのかよく分かってないが、とにかくまず λ_a （これすなわち P_s' (a|o) を求めること）を求めるのは次のステップである。

まずは制約となる feature の平均値をカウント（これは学習データが与えられれば可能）し、それと学習する確率分布の下での期待値が一致するように λ を更新していくというステップである。 これが GIS であり、特になんということはないが、一つ強い過程として学習データの状態系列に関しては既知というものが含まれている。POS tagging などでは既知であるものだが、場合によってはあるラベルが与えられていて複数の状態要素を取りうるなど状態系列が未知の場合もある。このような場合でも学習は可能だが、後で考えるとして一旦置いておく。

GIS がわかれば全体の学習の流れを把握することは難しくない。 下の手順は状態系列が既知でない場合も含めた書き方をしているが、既知の場合は、単純に (s,o) というデータセットを準備してそれで GIS をやりましょうという話に過ぎない。 モデルが学習できたら、Viterbi algorithm で与えられた観測系列に対して尤もらしい状態系列を推測すれば良い。

[yoheikikuta]

状態系列が未知の場合の拡張について書いておく。 これは Baum-Welch algorithm の拡張で解くことができる。

• E-step として現在の遷移関数を用いて forward-backward algorithm で取りうる状態の期待値を計算する。
• M-step として GIS を用いて新しい遷移関数を計算する（ E step で求めた状態の期待値を用いて feature frequency をカウントして GIS を実施する）。

ここで M-step において GIS は収束するまで回す必要はなく、これは Generalized Expectation-Maximization (GEM) の例になっている、という説明があるがこれは分からん。GEM を知る必要がありそうだが、まあここではそういうもんかくらいにしておいて今度遭遇したら真面目に勉強するとしよう。

ともかくこれによって状態系列が未知の場合でも学習できることが分かるので、ラベルデータが少ないような場合でも使えたりするので嬉しい。

[yoheikikuta]

ここまで読んでいて、この辺の知識がないためか Viterbi とか Baum-Welch とかその違いとかで混乱してきた。ので HMM の文脈でこれらを軽く整理しておく。

• Viterbi algorithm 観測系列とモデルが与えられた時に、最も尤もらしい状態系列を推測するアルゴリズム。これをするためには状態遷移の際にどの path が確率最大かということを計算して path をつないでいく必要があるが、それを動的計画法で実施していくことになっている。
• Baum-Welch algorithm (= forward-backward algorithm) これはモデル学習に使われるアルゴリズムで、EM 法で反復的にパラメタを更新していくものである。これをするためには次の観測が生成される確率を前向き方向と後ろ向き方向の両方から計算しておく必要があるが、これがそれぞれ forward algorithm と backward algorithm となっていて動的計画法で求める。forward algorithm は Viterbi でやったものと似ているが、こちらは max を求めるということはしない。

もう少し違う言葉でも表現しておく。 ある特定の観測系列が実現される確率を求めることを考える。これをやるのは forward algorithm や backward algorithm である（forward-backward algorithm ではなく、その中で使われる要素であることに注意）。 一方で与えられた観測系列に対して最も尤もらしい状態系列を求めることを考える。これが Viterbi algorithm である。 最後にモデルパラメタを学習したい場合を考える。これが Baum-Welch アルゴリズムで、それをするためには forward algorithm と backward algorithm である観測系列が実現する確率を求めておく必要があるということである（期待値を計算したいのだから）。

[yoheikikuta]

実験に入る前に少し亜種に関しての議論がある。

MEMM の困る点は HMM と共通して状態遷移を考える際に $ |S|^2 $ のパラメタが発生することで、状態数が多い場合は学習データがスパース（状態系列の path が十分に尽くせない）になってしまう。さらに素性に関しても色々考えられるのでこれも増やせば増やすほど学習データが必要になる。 HMM で tied parameter を使うのと似たような感じで、例えば「全文はまだ終わっていないか」など複数の状態で共通して使えるような素性を考えることでパラメタ数を減らすことができる（考慮すべき状態遷移の可能な組み合わせを減らすことができる、ということ）。

その他には遷移確率を HMM 的に戻すという方法もある。 具体的には以下の形にする。$ P(s|s') $ は多項分布にして $ P(s|o) $ の部分で exponential model を使うということである。このように書けると仮定すれば $ s' $ の要素毎に $ λ_a $ を準備する必要もないので、これでパラメタ数が減るということになっている。実際この後に出た MEMM を使っている論文で、このような簡単化をしているものが見受けられる。

さらに遷移関数に action 依存性も入れて強化学習の話もしているが、これはなんかコメントしてるだけなので割愛。

[yoheikikuta]

次に実験で MEMM の威力を確かめる。

データは FAQ のテキストを用いる。典型的には header-question-answer-tail という感じに文章が構成されていて、インデントなどいくらかの formatting がなされているとのこと。 これの各行に head, question, answer, tail というラベルをつけて、以下のようなデータを得る。

モデリングのための素性としては以下を使用。これは完全に hand-crafted である。

これで MEMM のモデルを作るのは容易い。 状態系列は {head, question, answer, tail} の 4 要素を取りうるもので、一つのタイムステップが一行、そして素性には上で挙げたものを使うということで学習をすればよい。

一方で比較のための HMM はちとややこしい。 まず TokenHMM というのがいわゆる普通の HMM で、観測系列はアルファベットの組み合わせや pucture の記号などといった token である。状態は MEMM と同じ 4 要素を取るもので、同一行に現れる Token に対応する状態には全て同じラベルがつけられるように制約をかける。つまり行が変わるところで初めてラベルが変わりうるようにして、あとは Baum-Welch で学習して Viterbi でテストデータに対する予測をすれば良い。

次いで FeatureHMM というのも考えていて、これは素性を使うのが MEMM だけだと不公平な比較だということで HMM でも素性を使おうというモチベーションのモデルになっている。やり方としては各行において true となる素性を書き出す。この際に順番が重要なはずなのでどの行でも書き出す順番は固定する。そして素性に対して一意なシンボルを定義して、それを観測系列にする。ちょっとちゃんと分かってないがこんな感じでやってるように読める。なので例えばある行で true になる素性が 5 個あればその観測系列は 5 個で対応する状態系列も同じラベルのものが 5 個あるということになっていると思われる。

[yoheikikuta]

ちなみにデータは http://www.cs.cmu.edu/~mccallum/faqdata/ にある。 論文で書かれているものからアップデートされているようで、9 つのトピックに対してそれぞれ何個か faq のファイルが付随していて、合計 48 ファイルある（論文では 7 つのトピックで 38 ファイルとある）。 なんか tail はなくて junk になってたりもするが、ともかく 1 ファイルには複数の question-answer が含まれていたりする。

ちょっとテストデータの切り方が分かりづらいのだが、おそらくトピック毎に別個に扱い、同一トピック内の一つのファイルで学習をしてそれ以外でテストをするというのをやる "leave-n-minus-1-out" でやっているっぽい。

モデルを学習した後は観測系列を与えて状態系列を推測してそれが答えと合っているかということをするが、ここで使う metric としては以下の 3 つ

• Co-occurence Agreement Probability (COAP) 式の詳細は省くが、10 行以内に含まれる 2 つの行を抜き出して、それらの 2 つの行に付与されているラベルを正しく予測できる確率になっている。
• Segmentation Precision (SegPrec) これは単純な counting で計算できるもので、予測したラベルの数に対して実際に正しく予測できた割合となるもの。いまは 4 つラベルがあるのでそれぞれでカウントしたものを合計しているということだろう。
• Segmentation Recall (SegRecall) こちらも単純な counting で計算できるもので、答えのラベルに対して実際に正しく予測できた割合となるもの。

実験結果は以下の通りである。

ということで確かに MEMM が良い性能を発揮したという結果になった。 特に SegPrec と SegRecall は高く、確かに正しくラベルを予測できているということが見て取れる。FeatureHMM もそこそこ良くて、強引な形でもやはり問題にあった特徴量を使うのが有効だということも伺える。

[yoheikikuta]

ということで MEMM を読んだ。 いやーこれは自分の知識不足も相まってなかなか読むのが大変だった。けどまあかなり理解はできたんじゃないだろうか。 次は本丸であるところの CRF を読む。

[yoheikikuta]

コメントをもらったので補足。

MEMM の新しい点をより強調しておくと、モデルの使い手（すなわち素性を決定する人）によって最終的に得られる分布にはかなり幅が出るというものになっていることだ。 十分な学習データがあることを仮定すれば、最大エントロピー法を使う以上は素性による制約こそが確率分布の形状をコントロールするものであり、確率分布はまさに素性関数が exp の肩にそのまま乗っかる形になっている。 問題に対して人間の有する知識を入れ込んで素性として適切なものを選ぶ、というのは正に特徴量エンジニアリングで、MEMM はその性能を使い手の力量に多くを委ねているものである。