yoheikikuta
commented
5 years ago 系列ラベリングと言えばやはり CRF ということで真面目に原論文を読んでみようという趣旨。 いきなりこれを眺めても導入のところの気持ちが分からないので、先だって MEMMの論文を読んだ。 準備万端（？）ということで CRF も読んでいく。
Open yoheikikuta opened 5 years ago
yoheikikuta
commented
5 years ago 系列ラベリングと言えばやはり CRF ということで真面目に原論文を読んでみようという趣旨。 いきなりこれを眺めても導入のところの気持ちが分からないので、先だって MEMMの論文を読んだ。 準備万端（？）ということで CRF も読んでいく。
yoheikikuta
commented
5 years ago まずは CRF というモデルを考えることになった背景に関して。
そもそも解きたいと思っていた問題は「観測系列が与えられた時にそれに付随する系列ラベル（これは大体の場合で状態系列に対応していると思っておけばよい）を予測する」という問題。具体的な問題などに関しては MEMM の論文読みの方に書いたので割愛。
HMM のような生成モデルを使っても Baum-Welch でモデルを学習して Vitrebi で予測をすればこの種の問題を解くこともできるわけだが、モデリングとして素直でないし、tractable なグラフィカルモデルを作った結果ラベルが given の場合に観測系列が条件付き独立であるようなものとなり overlapping feature などが使い難いなどの実用的な問題がある。
これを改善するために MEMM という観測系列を given にして状態系列を予測する識別モデルが考案された。P(s|s',o) というグラフィカルモデルを考案し、性質の良い確率分布を使えないという点に関しては素性を制約として使った最大エントロピー法で解決する。この素性はモデリングをする人が解きたい問題に対して有する知識を駆使して構築することで、良い性能を発揮するモデルを構築し得る。例えばテキストの行に対して「筆記体で書かれた単語を含む」「第一行目である」などの overlap し得る特徴を入れることが可能となる。 MEMM の原論文では FAQ のテキストの行にラベルを付与するという問題で HMM よりも高い性能を発揮することが示された。
この MEMM にもやはり不満なところがあってそれを解決するために CRF を提案したというのがストーリーである。 どんなところが不満なのかというといわゆる「ラベルバイアス問題」である。これは一言で言うと、現在の状態の各要素に対して MEMM は exponential model を構築していて次の状態に移る確率が別個に規格化されていて、それゆえに次の状態の要素数が小さいものほど高い確率が割り当てられてしまう、というものである。 これで理解できる人はもともと理解していた人だと思われるので、この問題をもう少し詳しく見ていく。
yoheikikuta
commented
5 years ago ラベルバイアス問題を具体的に考えるが、論文の最初に出てくる説明だけだと結構難しいと感じたので、後の実験で使うものも考慮してもう少し具体的に見てみる。
まず HMM を考える。 状態遷移として 0 -> 1 -> 2 -> 3 というパターンと 0 -> 4 -> 5 -> 3 という二つのパターンがある。 ここで黒丸は状態が取り得る要素を表現しているもので、time step との兼ね合いを考えると例えば $ s_1 = {1,4} $ という感じである。 それぞれの状態要素を given にして観測要素として {r,i,o,b} が出力されるようになっていて、その確率はここでは $ p(r|1) = p(r|4) = p(i|2) = p(o|4) = p(b|5) = 29/32 $ でそれ以外は全て 1/32 となっている。 遷移確率は $ p(1|0) = p(4|0) = 1/2 $ でそれ以外は一本しか path がないので確率 1 となる。
このような HMM が提供されれば観測とラベル（状態系列）のペア (o,l) として {(rib, 0123),(rob, 0453),(bib, 0123),...} みたいなデータが生成されることになる。
例えば観測系列が与えられていて状態系列を予測することを考えれば、状態遷移は最初以外一本道だが、例えば二つ目の観測が {i, o} のどちらかなら {上のpath, 下のpath} のどちらかの可能性が高いということが分かる。これは $ P(s|s') P(o|s) $ というモデリングになっていて、予測の際にはベイズの定理を介して $ P(o|s) $ が効いてくるので定性的にも理解できる。
一方で、MEMM の場合を考えてみる。 MEMM の場合は $ P(s|s',o) $ というモデリングだったので、観測を given で次の state を予測するものなので例えば以下のように図示できる。ちょっと書き方がよくないが、上の path は rib という観測系列が与えられたときに 0123 という状態系列が得られる流れを、下の path は rob という観測系列が与えられたときに 0453 という状態系列が得られる流れを描いている。
この MEMM においても状態系列の予測をしてみよう。 先ほどの HMM で２番目の観測が有効だったことを思い出し、rib という観測系列だったことを考えよう。 最初の遷移である $ p(1|0,r) $ と $ p(4|0,r) $ がどうなるかはモデルの学習に依存するところだが、どちらかを優先するような構造があるわけではないので学習データがよほど偏ったりしていない限りは大体 1/2, 1/2 になっているだろう。 次の観測は i であり、これは下の path の可能性が高いと思っていたわけだが、path が一本道であることを考えれば上下どちらの path においても $ p(2|1, i) = p(5|4, i) = 1 $ となってしまう。これはすなわち i を観測したという情報がまるで効いていないということになる。 状態 3 への遷移も一本道なので同じ議論でどちらの path でも確率 1 であり、最終的には上の path か下の path かを分けるのは最初の分岐のみということになる。先ほど述べたようにこの分岐は背後にある構造としては 1/2, 1/2 となるべきものだ。学習データのばらつきなどによって少しズレが生じるかもしれないが、そういったズレに引きずられて予測が決定されてしまうという結果になってしまった。
これこそがラベルバイアス問題である。この例における本質は path が一本道であった結果としてせっかく観測した情報が意味をなさなかったというものだが、一般化すると状態要素毎に規格化されているので path が少ないものほど選ばれやすいという問題を抱えているということが分かる。
これは確かに問題だ。MEMM が提供する柔軟なモデリングは確かに強力だが、overlapping feature を可能とするために導入した $ P(s|s',o) $ という構造は副産物としてラベルバイアスが生じてしまった。 ということで素性を使ったモデリングは維持しつつもラベルバイアス問題を解決しようとして考案されたモデルこそが CRF である。
yoheikikuta
commented
5 years ago CRF に行く前に他にラベルバイアスを解決する方法が提示されている。
その他にも heuristic な解決策などもあるようだが、CRF は純粋に確率論的な（すなわちグラフィカルモデル）アプローチでこの問題を解決していて、大域的な尤度最大の収束が担保されているモデルになっているということで良いモデルであるという主張。
yoheikikuta
commented
5 years ago それでは CRF の定義。
X は観測系列で例えば自然言語のセンテンスの連なりで、Y はラベル系列で例えば POS tagging である。 定義により、$ P(Y_v|X,Y_w) $ において隣り合う $ Y_v $ のみが寄与するため markov 性を有する。 また、X に関しては任意の X が寄与し得るので、ここはかなり自由度が高い。一般には X と Y は同じ構造を持っていなくてもよいし、一つの $ Y_v $ に関して複数の $ X_i $ が寄与してもよい。
モデリングとして、 X と Y は同時分布するものだが識別モデルとして $ p(Y|X) $ を直接的に考えることで、陽に周辺分布 $ p(X) $ をモデル化することなく CRF を構築している。
この形だと色々な形を取り得て具体的な議論がし難いので、以降では色々と限定した CRF に関して議論をしていく。
yoheikikuta
commented
5 years ago まず、$ X = (X_1, X_2, ..., X_n) $ と $ Y = (Y_1, Y_2, ..., Y_n) $ という最も興味のある X と Y の系列が同じ長さの場合を考える。
次に Y のなすグラフ $ G = (V,E) $ が木構造の場合を考える。
fundamental theorem of random fields (Hammersley & Clifford, 1971 により条件付き確率 $ p(y|x) $ は次のように書ける。
$ y_e $ は edge e で定義される y の要素の集合で、$ y_v $ は vertex v で定義される y の要素の集合を表す。 f や g は feature ですなわち素性である。 （ここではこのように書けることは認めてこの定理自体を深追いするのはやめておく）
この条件付き確率が観測系列を given にしたときのラベル系列を予測するのに使えるもので、求めたい対象である。素性を手で与えるものとすればその重みである λ や μ を学習したい、ということである。 MEMM との違いとして、MEMM は状態の各要素に対してそれぞれ exponential モデルを作っていたが、CRF では一つの exponential モデルになっているというところが見て取れる。
木構造を考えたことでかなり具体的な形が表現できるようになったが、ここからさらに簡単化する。 木構造の中でも chain を考えて HMM のような構造にする。これを実現するためには各状態のペア $ (y',y) $ と状態-観測のペア $ (y,x) $ のそれぞれに対して一つは以下のような feature を導入する。
これの意味するところを考えれば、f は隣り合う状態を結んでいるものなので $ p(y|x) = e^λ{y',y} ... $ は HMM で言うところの $ p(y'|y) $ に相当しているものであることが分かり、同様に $ g{y,x} $ は $ p(x|y) $ に相当するものであることが分かる。
ということで各モデルのグラフィカルモデルの対比は次のようになっている。
ここまでをまとめて、chain 構造の CRF のラベル系列の条件付き確率は次のように書ける。
記号の意味は以下。面倒なので論文のスクショを貼って済ませてしまう。 まあこれは記号をこう定義するという以上の情報はそんなにないのでいいだろう。
ここで生成モデルと違って可能な観測系列 x の全てを考慮しなくて良いと言ってるのは、条件付き確率にしているからで、与えられた観測系列 x （とパラメタ θ）から行列 Λ を計算できるという意味である。 Z は確率的解釈をするための規格化定数で、いわゆる分配関数である。ちょっと表記が難しいかもしれない。 $ M_i (x) $ という形で書いてる時は $ |Y| × |Y| $ の行列であり、これの全系列の積を取っているということは全ての path を考慮した計算をして最終的にやはり $ |Y| × |Y| $ の行列を得る。その entry の中から (start, end) に相当する要素を抜き出して、開始と終了は定まっていて途中の path は全て足し上げた数値になっているということである。なので分子に関して可能な y の要素全てで足しあげると 1 に規格化されるようになっている。 関係ないけど物理やってない人がいきなり分配関数ですよと書かれても厳しい気がするんだけどみんなどう対処しているのだろうか。
yoheikikuta
commented
5 years ago パラメタ学習についてまずは抽象的な議論を。
目的関数は log-likelihood を用いる。経験分布 $ \tilde{p} $ で近似すれば以下のような形で書ける。
このエントロピーのは convex であるので、CRF は general maximum entropy models の有する convex の性質を同じように活用することができるものになっている。
以降では具体的なパラメタの学習方法を議論していく。
yoheikikuta
commented
5 years ago パラメタの学習だが、まずもって識別モデルなので局所解を許容するならば SGD とか LBFGS などで学習することができるし、どちらかというこういう手法の方が最近では使われているのだと思う。 ちなみに この資料 では学習方法毎の速度や性能を比較している。
この論文では大域的な解を求める学習方法を解説していて、せっかくなのでそれをちゃんとフォローしてみる。 まず Iterative scaling algorithm がベースになっているが論文を読んでも理解するのは難しい。 ということで真面目に考えてみた。
ここで求めた等式で、経験分布は学習データから定められるので、これに基づいて変化分を定めるというものになっている。
yoheikikuta
commented
5 years ago 上の式で T(x,y) の定義を書いてなかった。定義はこれ。
この T は (x,y) に global に依存（特定の局所的な要素ではなく全系列に依存）するので、動的計画法を使っていく際にそれをちゃんと考慮する必要がある。ということでこの問題に合わせたアルゴリズムとして Algorithm S と Algorithm T という別々の二つのアルゴリズムを考える。 Algorithm S は近似などを使わないものだが T(x,y) をその最大値という定数で置き換えることに起因してパラメタ更新が小さくなって収束が遅い。一方で Algorithm T は近似を介したより早い学習アルゴリズムである。
Algorithm S まずは以下で定義される slack feature を導入する。
S に関しては全ての y と観測系列 x に関して $ s(x^i,y) \geq 0 $ となるように選ぶ。これは定数でこの定数で変化し得る T を置き換える、すなわち $ T(x,y) = S $ とする。 $ M_i $ を前後に動かす forward vector と backward vector を次で定義。
こいつらを用いて、パラメタの更新式を書き換える。
定数 S は学習データの系列長に比例するものになるので大きい値になり得る。 この S が大きくなると更新式でのパラメタアップデート分が小さくなるため、結果として学習が遅くなってしまう。
Algorithm T まず平均場近似で $ T(x,y) ≒ T(x) = max_y T(x,y) $ とすると f_k の期待値は以下のように書ける。
さらに、(x,y) に関して $ \max_x T(x) $ の値ごとに特徴付けられるのでそのように書き換えると以下。
ということで、ニュートン法などで解ける以下の形に帰着できる。 これを実際に解けばパラメタが更新できる。
ただし
yoheikikuta
commented
5 years ago ということで実験に入る。 まずはラベルバイアス問題を本当に解決できているのかという実験。
上のラベルバイアス問題での状況設定で、HMM で生成したデータに対して observation feature を observation symbol と同じにした MEMM と CRF で学習してテストデータに対して予測する。
学習データとして 2000 サンプル、テストデータに対して 500 サンプルを使った結果、CRF の error は 4.6% で MEMM の error は 42 % という結果が得られる。上の path か下の path かを当てるという問題設定なので、MEMM は random とそう変わらないくらい（これはラベルバイアスを考えれば自然）の性能で、CRF はちゃんとラベルバイアスを回避して解けているということが分かる。
yoheikikuta
commented
5 years ago 次の実験は mixed-order の HMM で生成したデータに対するものである。
実験の設定は、ラベルは 5 つ (a,b,c,d,e) で観測値は A-Z の 26 個の記号を考える。学習もテストも長さ 25 の系列を作る。 $ p_α (yi | y{i-1}, y_{i-2} ) = α p_2 (yi | y{i-1}, y_{i-2} ) + (1-α) p_1 (yi | y{i-1} ) $ という α で parametrize された一次と二次の HMM で生成する。 具体的な $ p_2 $ と $ p_1 $ がどうなっているかはパッと見わからないが、まあ適当に手で決めているだろうということで深追いはしない。
これらの対して一次 HMM と MEMM と Algorithm S で学習した CRF を比較する。結果は以下。
直線よりも左側に点が集まっていれば、横軸のモデルが縦軸のモデルよりも良いという風に読める。 左図は CRF が MEMM よりも良いことを示している。これは期待通り。 真ん中の図は HMM が MEMM よりも良いことを示している。これはちょっと考えるところだが、そもそも一次の HMM も MEMM も状態の二次接続の効果は考慮できないものなのでそこに違いはなく、そもそも HMM で生成したデータなので HMM の方がよくなるというのは不思議ではない。 右図は四角のデータ（これは α < 1/2 で一次の効果が強いもの）に関しては HMM の方が良くて、黒丸のデータ（これは α >= 1/2 で二次の効果が強いもの）に関しては CRF の方が良い。簡単なデータなので差はそこまで大きくはないが、CRF の方が表現力が高いということを示している。
yoheikikuta
commented
5 years ago 最後に POS tagging の実験。 Penn treebank データを使ったもので、MEMM と CRF に関しては hand-crafted な特徴量を使うこともできるので、詳細は省くがそれらの結果が以下。
hand-crafted な特徴量を使わなければ差がそこまで出ないことはまあ分かるが、やたらと MEMM が悪いのはラベルバイアスに依るものである。
一方で hand-crafted な特徴（ここでは -ing が suffix か否かなどを使っている）を入れると期待通り性能が向上する。その中でも期待通り CRF が最も良い結果を見せている。
yoheikikuta
commented
5 years ago ということで CRF の論文読み終わり。 いやー難しかった。記述が分かりづらいということもあるけど、自分の背景知識の無さなども相まって、理解するまでに結構しんどかった。 まあまあ頑張って読んだのである程度の理解には達したと思う。今後遭遇するかは分からないけど、これくらい理解しておけばその場合もちゃんと使っていけるだろう。
論文リンク
https://dl.acm.org/citation.cfm?id=655813
公開日（yyyy/mm/dd）
2001/06/28
概要
系列ラベリング問題を解くという目的に対して、HMM で扱えない overlapping feature などを使うために MEMM というモデルが考案され、確かに一定の成果を見せた。 一方で、MEMM にはラベルバイアス問題という、状態要素毎に遷移確率が規格化されている（状態要素毎に exponential model を構築するため）状態遷移の候補が少ない path が選ばれてしまうという問題がある。 これを解決するために Conditional Random Field (CRF) という無向グラフの識別モデルを考案した。これは $ p(y|x) $ という系列全体で一つの exponential model を構築するもので、それゆえにラベルバイアス問題を解決でき、MEMM と同様に問題に合わせた素性を使うことも可能になっているモデルである。 学習は Iteratie Scaling Algorithm をベースとした Algorithm S と Algorithm T という学習手法を提案（現在では単純に SGD とかで解けば十分そうな感じはする）。 人口データと Penn treebank の POS tagging データで実験をして、確かにラベルバイアス問題を解決してかつ HMM や MEMM よりも性能が高い（HMM に関しては問題が十分に複雑ならば）ということを示した。