logsumexpとスケーリング法

少し前にtwitter上でCRFSuiteはスケーリング法を使っているから速い，的なことを書いたのでその解説です． linear-chain CRFのパラメタ推定に必要なのは対数尤度関数の微分です．これの計算に必要なのが，前向き・後ろ向きのスコアαとβです．時刻t（系列上での位置）とラベルiに対する前向きスコアαは，以下の式で計算されます．fは特徴ベクトル，wは重みベクトルです． ところがこのままだと問題が起こります．αの値はexp個の足し算で構成されるため，最終的にかなり大きくて，簡単に倍精度の限界を超えてしまうのです．困った．そこで，logの世界に落とします．αの代わりにlog(α)を計算します．すると，expの世界の掛け算はlogの世界の足し算になります．問題は，足し算です．expの世界の足し算を，logの世界で行う２項関数がlogsumexpです． で定義されます．expをかけてる

[mamoruk]

自分もスケーリング法で一度作ってみたい

[gologo13]

ME読んでたときに反復スケーリングってあったけどそのこと？実装について書いてある