数式を含む論文の読解効率化
知的作業の生産性はやり方の設計によって左右される。「数式だらけの論文を読む」というタスクも「とにかく頑張って読む」のではなく、やり方をうまく設計することで生産性向上ができるんじゃないかなぁ。そう考えて、自分を観察しながらやってみることにした。
読む論文はCRF(条件付き確率場)についての次の二つ: Lafferty: Conditional random fields: Probabilistic... - Google ScholarとSutton: An introduction to conditional random fields... - Google Scholar
まずは目的の明確化。目的は達成したかどうかが客観的に計測できるものでなければならない。つまり「CRFを理解する」なんてのではダメ。「CRFを実装して学習過程を可視化した動画を作ってブログに載せる」を目標とする。
次にそのタスクにどの程度の時間がかかるかを考える。タイムタギング。25分を一塊(ポモドーロ)と考えて、何塊で達成できるか？皆目見当がつかない。7ポモドーロでできるかというとできそうに思えない。これはタスクが大きすぎるか、タスクのゴールから遠すぎてタスクの全体像を把握できていないことを意味する。大きなタスクは一足飛びには達成できない。できることはゴールに向かって1歩進むことだけだ。というわけで25分でできる、ゴールに近づくであろうタスクを行うことにする。
フォトリーディングでは、対象図書を読む目的を明確化した後、章タイトルや図表のキャプションなどを読んで調査することを提案している。本格的に読む前に、読む対象に対する情報収集を行い、その上で本当にそれを読むべきかどうかを判断すべき、という主張だ。実は上の2つの論文を今回の実験対象に選ぶ過程で、読むべき対象かどうか判断するためにSuttonの方はこのタスクをやってある。そこからわかったこと:
- CRFとHMMの関係はロジスティック回帰とナイーブベイズの関係に似ている、とSuttonは考えている
- 識別モデル(CRF, ロジスティック回帰)と生成モデル(HMM, ナイーブベイズ)
- 系列データが対象(linear-chain CRF, HMM)
- 一般のグラフを対象としたものもあるらしいけどそれは今回の僕の目的には不要なのでスルー
- それぞれについてのパラメータ推定と推論の説明が書かれている
- 実装上の問題点について書かれた章がある、これは重要そう
- 後半でSkip-Chain CRFについて書かれているがこれは今回の僕の目的には不要
同様にLaffertyもざっと章タイトルだけ見る
- ラベルバイアス問題ってものがあるらしい、それを解決したくてCRFを作ったっぽい
- パラメータ推定の方法を描いた章がある
とりあえずいきなり頭から読むよりはおおまかな地図が把握できて心理的ハードルが下がったように思う。フォトリーディングのポールRシーリィはこのあと「眼の焦点をぼかして潜在意識に情報を送り込め」「読めている気がしなくてもちゃんと読めているので必要なときに取り出すことが出来る」という検証の難しそうなことを主張するわけだが、まあそれが数式を含む論文に対して有効であるかどうかに関しては言及されてない。僕はフォトリーディングは「重要なことは何度も書かれる」という前提を仮定しているので数式には成立しないと思う。が、まあ38ページフォトリーディングするのは1分も掛からないからやるだけやっとくか。
次は何をするか。あ、今気づいたんで念のため書いておくと、普段ならここらでもう「頭から普通に読む」を選択しちゃってると思う。今回は暗黙に「真面目な読み方を一切せずに成果を出す」も目標にしてるんだな。さて、次は何をするか。フォトリーディングからの提案は「キーワード探し」だな。複雑なシステムはいきなり飲み込むことはできないので断片的な知識に刻む必要がある。フォトリーディングはキーワードを探して単にリストアップすることを提案しているけど、僕はこのあとKJ法につなげるので付箋にキーワードを書いていくことにしよう。時間は最長25分、途中でもういいと思ったらやめる。所要時間を計測していて今後別の論文を読む際の挑戦目標にする。さあ、開始！
25分経過。えっと、自然言語なら38ページの論文からキーワード抽出をするのも25分で十分すぎるくらいなんだが「数式は全てキーワードである」と思ったら膨大な量に膨れ上がったのでLaffertyの5ページ目までしか到達しなかった。数式の部分を真面目に捉えすぎだったかも知れない。最初の段階では数式字体ではなく「数式にどんな記号が出てくるか？」くらいに抑えるべきだったか。あとLaffertyのは一般のグラフに対してのCRFなのでLinear-chain CRFを実装しようとしている僕の目的にはオーバースペックだったな。それがわかっていたのにLaffertyの数式に密着してしまったのは時間配分のミスかも知れない。まあ、わかったこと
- Laffertyは一般のグラフについて定義している
- HMMと同じようにαβの再帰的な計算をしている
- 1軸がラベルのサイズの正方行列Mがある、HMMの遷移行列に似ている
- δがクロネッカーのかとおもいきやδμみたいな使い方をしていて、更新差分だろうかコレ？
- label-bias problemの内容が気になる。書いてある場所はわかるが読んでいない
- y|eiという表記の意味がよくわからない
何がわからないかわかることも重要だね。さて、それを解決する前にSuttonの方も最低限1.3章Linear-Chain CRFからの7ページをやるべき。数式の量的には今のと同じペースでやると25分でギリギリくらいかなぁ。
25分経過。1.26までしか終わっていない。予定より2ページ短い。数式をついついまじめに読んでしまう。数式のナナメ読みは難しい。っていうか1.26とかまじめに読む必要なかった。これは「再帰的に書けます」を表現しているだけなのだから。視野が狭くなってしまっているなぁ。わかったこと
- パラメータ推定フェーズで直接的な最大化ができないからBFGSを使ったりするって書いている？
- 正則化項いれるの？
- xとyが両方共T次元なの？
- Sってどこで定義されてたっけ
- HMM-like CRFとlinear chain CRFは別物か
読む予定でまだ読んでない範囲にαβの再帰が書かれているからここを読むことは必須だ。あと25分でそこを読んで残りの時間で全体をもう一度読み直すべき。
25分経過。
- これはTが時間軸方向なのでおかしくない。勘違い＞「xとyが両方共T次元なの？」
- アンダーフローを避けるためにスケーリングする方法と対数空間で計算する方法があってSuttonは後者をmore stableにする方法を解説している
- Suttonはパラメータ推定フェーズにL-BFGSを使って高速化する方法を研究している。Laffertyはニュートン法で求まるよね、と言ってる。
- Ψの定義がHMMとCRFで異なるだけで、アルゴリズムは同じ
- HMMとHMM-like CRFは自然に導出される生成-識別ペアである。詳しく知りたいけど目的にマッチしないので保留。
- LaffertyのAってEMアルゴリズムのQみたいなものかな。多分収束性に関する議論だから実装には関係ないや。
L-BFGSの勉強を始めると時間がかかりそうなので今回はLaffertyのニュートン法で解くことにしよう。2つの論文は付箋の山に変わった。次はこれを結合していくフェーズだ。
付箋は95枚あった。缶ペプシを飲みながら考える。
- 今回の実装に関係ない問
- ラベルバイアス問題とは何か？CRFでなぜ解決するのか？
- L-BFGSってどんなもの？
- 生成-識別対ってどんなもの？
- Improved Iterative Scalingって何？(関係あるかも？)
- 関係ある問
- どうやってパラメータを推定するのか？！
35分ほどのんびりペプシを飲みながら考えたり付箋を並び替えたり論文を読みなおしたりしてわかったこと:
- Laffertyはパラメータの推定方法を「この式を解け」まで書いてあるのでそれをニュートン法でとけばよい
- Suttonは「ニュートン法で解くのはパラメータ数の2乗のサイズのヘシアンを計算しないといけないからパラメータの多い実用用途では無理。擬似ニュートン法であるL-BFGSを使えばメモリの消費量が少ないから大丈夫」と言ってるけど具体的な話は別の論文。
- δは更新差分だって書いてあった
- Laffertyが解けと言っている式の~Efkとか~Egkがどこで定義されているかわからないが~E[fk]は定義されているからこれのことを指していて、~Egkはそれを参考に自分で定義しろってことかね？
- 求めろと言われている式の中のaとbが定義されていないなぁと思ったら文章中でfkとgkの期待値だって書いてあった。それを求める式も自分で作れってことね。
次に何をするか。もう直接大学ノートに数式を書き始めてもいい気もするけど、KJ法的には先に空間的配置をしてからシリアライズなんだよな。
25分経過。もうゴールからスタートまで一気にかけると思って図を書き始めたが、途中で躓く。
- Efkと~Efkは異なるもの。~Efkはどこで定義されているんだ？
- ~Efkと~E[fk]が同じものなんだとすると、これはfkの~p(x, y)の下での平均ってことになるかな
- feature fk, gkはgivenと書いてあるけどどう与えればいいんだろう？
25分で他の文章を読む
- 「機械学習による自然言語処理チュートリアル 〜PerceptronからCRFまで〜」岡野原 大輔
- そうかλkfkをkについて合計するのは重みベクトルwと素性ベクトルΦ(x, y)との内積と考えていいのか
- 頂点にしか素性を付けなくてもOKか。fkは全部0ということだよね？
- MeCab 汎用日本語形態素解析エンジン 工藤拓
- 「正解コスト＜その他のコスト」上の内積の話とあわせて考えるとPassive Agressiveみたいな感じのことが中で行われている？？
疲れてきた。閉塞感を感じてきた。多分この長いトンネルを抜けると花畑が待っているはずなんだけど、ここで心が折れそうになる。
id:n_shuyoさんからのフィードバックでPAに似ているとか考えるのは間違った方向に進んでるっぽいので保留することに。
ホワイトボードにわかっている知識を書きだしてみるなどする。星野さんに何に悩んでいるかを説明しようとした結果、対数尤度の勾配を求める方法の理解が必要だということがわかった。対話による表出化ですな。
疲れて25分の集中ボックスができてないせいで時間の計測が曖昧になってきた。この記録のこのあたりの時間の経過には信頼性なし。
- 最大エントロピーモデル＝ログリニアモデル＝線形対数モデル＝conditional exponential model？
- IISはconditional exponential modelの尤度を最大化する手法
- 尤度の勾配の式の2つの項のうち片方がαとβの再帰での動的計画法で求まるっぽい
- log(Z(X))をθで微分したらEy'[Φ(y', x)]になるはずだがそこのギャップが埋まっていない
- Ey'[Φ(y', x)]がどうやって動的計画法に対応付けられるのかもギャップになっている
- この2つのギャップを埋めることが必要
昼休みの中谷さんとの会話をメモ
- ME(maximum entropy)は可能な分布のうちなるべく余計な情報を持っていない(エントロピーの大きい)ものを選ぼうという戦略、ただ離散でない分布についてはエントロピーの定義が難しい(微分エントロピーとかあるけど)ので、例えば一様分布が最も情報量が少ないと仮定して、一様分布へのKLダイバージェンスを最小化などする
- 事前分布を一様分布と仮定した時のMLとMEは一致することもあるししないこともある
- MEはログリニアと相性がいい
- Sutton1.14のZは1.15では分子分母両方にあるから消えるのか
- 対数尤度の微分を計算してSutton1.22の式にはなった。第1項と第2項はそれぞれ別の分布の下でのfkの平均ととらえることができて、微分が0であることからこの2つの平均は等しい。これはEP法の所でやったモーメント一致法？
- 対数尤度は対数の和の形になっているので凸関数
- 対数尤度の微分の第2項目のp(y|x;θ)のところにだけパラメータθが関係している
- 分配関数Z(X)と周辺分布p(yt, yt-1 | X)が両方フォワードバックワードで求まる
- →どうやって？
- p(yt, yt-1 | X) \propto αt-1(yt-1)Ψt(yt, yt-1, xt)βt(yt) (eq.Sutton1.34)
- p(X) = sum_xn α(xn) (eq.PRML13.42)
- αとβの再帰の式はSuttonに書いてある
お、実装に必要なパーツが全部揃った？
まだか。
p(yt, yt-1 | X)がPRML p334で言うところのξで、PRML p335ではMステップでξを使ってパラメータをどうアップデートするかの式が書かれていたのでそれを使ったけど今回は書かれていないから自分で求めないといけないのか
p(yt, yt-1 | X)は対数尤度の微分のSutton1.22に出てきているし、PRMLでは対数尤度の期待値をラグランジュ未定乗数法で最大化してMステップの式を導出したような記憶がある。
そこをおさらいする必要があるかな。
EM法とHMMをおさらいする。
- 「Qを求めるにはモーメントを求める必要がある。多項分布だからモーメントはパラメータと一致する。」とノートに書いてあるけどどういう意味だろう。
- Qの計算過程で隠れ変数の取りうるすべての系列についての和が必要になって、この計算がフォワードバックワードで省力化できるってのはわかるが、値を求めてしまったら後のargmax_thetaがどうしていいかわからない。
- Qを一つの値として求めるのではなく、フォワードバックワードで求められる値とパラメータとで構成された式で表現して、それからラグランジュ未定乗数法で個別のパラメータについての更新式を導いてるな。PRML P334。
- CRFのパラメータ推定はHMMのパラメータにとても似ているはず(by Sutton)なので、どこが似ていてどこが違うかについての情報を集めて整理するか
- 「目的：HMMのパラメータ推定とCRFのパラメータ推定の似ている部分と異なる部分についての情報収集」1ポモドーロやる
途中で昼食で中断されて、その後25分終了。Sutton1.19の式を理解することが重要だと思う。
- 1.19のθ'は古いθでもθの微分でもなく「なんか適当なパラメータ」って意味か。ここで言っているのは「これから条件付き対数尤度の最大化をしようと思うんだけど、θはp(x)には影響しないからθについての最適化を考えるだけなら条件付き同時確率を考えてもいいよね」ってことか。
- 1.20はそれとは無関係に単に項を置換しただけ。1.21はそれに正規化項を付け加えただけ。
- 1.22の式の正規化項の微分って合ってる？Sum_kが付いているからkが消えてしまって、この式が0だという情報からλkの値を求めることができないなぁと思っていたんだが、1.21の正規化項を微分するとSum_kは取れてλkが裸で露出するように思える。
- もしそうだとすればこの右辺の第1項と第2項はフォワードバックワードで求まるから、対数尤度が最大値であるときには微分が0であることから、対数尤度を最大にするようなλkを求めることが出来る。これでいいんじゃないの？
中谷さんから「1.22は間違ってそう」との同意が得られた。その後CRFもHMMと同じEMアルゴリズムだとどこかで聞いた気がしたが、どこがQ関数に相当するのかわからないなぁと思っていたら「LaffertyやSuttonのCRFの解法はEMアルゴリズムではない」との指摘が。僕の抱えていた問題は全部解決した。
整理すると
- そもそもHMMでなぜEMAが使われたか
- 教師なしで学習する(隠れ変数の系列Zの状態が与えられないことを仮定している)のでP(X | θ )を最大化したい
- でもこれを直接計算することは困難
- P(X, Z | θ)なら容易に計算できる
- じゃあそれを使おう
- CRFは「P(X, Z | θ)のことなんか知らん、識別モデルを作るにはP(Z | X; θ)さえ作れればいい」派
なんかいろいろあって時間が開いてしまった。そもそも当初CRFを勉強しようと思った目的は「HMMとCRFは両方EMらしいので両方学ぶことで理解を深めよう」というものだったのだけども、CRFがEMではないという結論になってしまい、どうしようかなーと思って。まあでも、ここまで学んだことを理解できているかどうかの確認としてやっぱりCRFの実装までは行こうと思う。
ノートに数式と日本語でやるべきことを書きだす。素性の作り方は http://www.slideshare.net/uchumik/crf-8416551 を参考にした。
案の定infやnanに悩まされるという。
1回目のestepの後のxiの値はだいたい確率値っぽい範囲なので合ってるんだと思うが1回目のmstepの後で素性の係数が-1.58295102e+67になってるのは間違ってるんだろうなぁ→alpha[t - 1] * ... * beta[t]をやるときにtを0から始めていたので境界を踏み越え得ていてxiの値が0のところだけe+66のオーダーになっていた
output_featureが全部マイナスになっているのはおかしいのではないか…あ、添字の指定を間違えていてブロードキャストされてる…
alphaの計算でオーバーフローするようになった。これは今はlogを取ってないせいなのでSuttonの1.55の式に従って小細工をする必要がある
値のレンジが明らかに振動を始めたので、重みベクトルのノルムで割って正規化項が満たされるように保証してやったらそれっぽい値に収束するようになった。
勾配をそのまま引くような方法だと学習係数がでかすぎたら振動するので、正規化項の制約から外れたときに1ステップごとに制約を守る方向に更新されるけど行きすぎてだんだん振幅が大きくなってしまうのかなと…
実装できた。
今回の実験を通じてわかったことの整理
