系列ラベリングのための前向き後ろ向きアルゴリズムの一般化 奈良先端科学技術大学院大学 　　　　　　　　東　藍 系列ラベリングのための前向き後ろ向きアルゴリズムの一般化という題で，奈良先端大の東が発表させていただきます．

系列ラベリング ある入力系列に対して，もっともらしい出力系列を推定する問題 自然言語処理の多くのタスクは，系列ラベリングとして定式化できる 形態素解析 固有表現抽出 文節区切り まず，系列ラベリングについてですが，系列ラベリングとは，ある入力系列に対してもっともらしい出力系列を推定する問題です．そして，自然言語処理のタスクの多くは，この系列ラベリングの問題として定式化できます．

前向き後ろ向きアルゴリズム 系列ラベリングの問題では，ある入力列に対して可能な出力候補系列すべてに関して，ある種の和を計算する必要が生じる場合がある HMM の EM アルゴリズム CRF における正規化定数の計算，素性関数のモデル期待値計算 これらの計算を定義どおり実行するのは不可能 さて，系列ラベリングの問題では，ある入力に対して可能な，出力候補系列すべてに関して，ある種の和を計算する必要が出てくる場合があります．たとえば，隠れマルコフモデルにおける EM アルゴリズムの E-step や， CRF のパラメタ推定においてです． これらの和の計算を定義どおり実行することは実質的に不可能であります．そこで，前向き後ろ向きアルゴリズムを用いて効率的にこれらの和を計算してきていました． これらは前向き後ろ向きアルゴリズムを用いて効率的に計算できる

従来の前向き後ろ向き アルゴリズム 「にわにはにわにわとり」 にわ に は にわ にわとり に わ はにわ にわ と り わに に わ に 　　にわ　　 に は 　　にわ　　 　　　　　　にわとり　　　　　　 に わ 　　　　はにわ　　　　 　　にわ　　 と り 　　わに　　 に わ に わ 　　とり　　 このスライドは具体的なラティスを見せるのが目的だが，どうか？ 　　わに　　

従来の前向き後ろ向き アルゴリズム 従来の前向き後ろ向きアルゴリズムが計算できる形式とは または は出力候補　　に現れるラベルおよび隣接ラベルペアの集合 (クリーク) さてですね．従来の前向き後ろ向きアルゴリズムが計算できる形式の和というのは，非常に限られた形式なわけであります．その限られた形式というのは次のようなものです． 式中で C(y) と書いていますが，この C(y) というのは，ある出力候補 y に現れるラベル，または隣接ラベルペアの集合を現します．この C(y) というのはクリークの集合である，と表現したほうが良いかもしれません． 1つ目は，クリーク上で定義された関数の積として表現できるものを可能な出力すべてで足し合わせる形式です． 2つ目は，クリーク上で定義された関数の積――先ほどと同じですね――それと，クリーク上で定義された関数の和，この2つの積となっているような形式を可能な出力候補すべてで足し合わせているものです．

従来の前向き後ろ向き アルゴリズム CRF のパラメタ推定において必要な計算の一例 CRF：

従来の前向き後ろ向き アルゴリズム 隠れマルコフモデルに対する EM アルゴリズムで必要な計算の一例 もう1つ例として， HMM に対する EM アルゴリズムの e-step で必要な計算の例を挙げます． P(x,y) が HMM による出力候補 y の確率で，その確率に関して(名詞-動詞)連接の期待値を計算する例です．この計算も結局，先に「従来の前向き後ろ向きアルゴリズムが計算できる形式」，つまりこの形ですね，に確かになっています．実際， phi を emission の確率または transition の確率とおいて，なおかつ f を(名詞-動詞)連接の indicator とおいた場合にそうなっています．

一般化への動機付け または の形式に収まらない和の計算が必要になる文脈が存在する． これらの計算に対しては，対象となる計算に特化した一般性の無い手法が用いられてきた． 一般的かつ普遍に適用できるようなアルゴリズムは知られていない． 従来の前向き後ろ向きアルゴリズムで計算できる形式，これらの形式ですね，に収まらない形式の和を計算したい，そういう文脈があります．これらの形ではない和を計算したい状況に直面した場合，これまでは一般性の無い計算方法を用いたり，あるいは近似を持ち出したりしてきました．これらの形式から逸脱した形の和を計算する，一般性のある，普遍的なアルゴリズムというのは知られていませんでした．そこで，本発表ではより一般的な形式である，この形，の和を効率的に計算するアルゴリズムを示します．

一般化への動機付け または の形式に収まらない和の計算が必要になる文脈が存在する． これらの計算に対しては，対象となる計算に特化した一般性の無い手法が用いられてきた． 一般的かつ普遍に適用できるようなアルゴリズムは知られていない． 従来の前向き後ろ向きアルゴリズムで計算できる形式，これらの形式ですね，に収まらない形式の和を計算したい，そういう文脈があります．これらの形ではない和を計算したい状況に直面した場合，これまでは一般性の無い計算方法を用いたり，あるいは近似を持ち出したりしてきました．これらの形式から逸脱した形の和を計算する，一般性のある，普遍的なアルゴリズムというのは知られていませんでした．そこで，本発表ではより一般的な形式である，この形，の和を効率的に計算するアルゴリズムを示します． 本発表では という形式の和を効率的に計算するアルゴリズムを提案する．

前向き後ろ向きアルゴリズムの一般化 ・・・ ・・・・・ から への経路の集合 　　から　　への経路の集合 では，本発表で提案するアルゴリズムの中心，鍵となるアイデアに関して図で説明します．簡単のため，ラティス中のノードだけに注目します．ラティス中のエッジについては同様なので省略します．従来の前向き後ろ向きアルゴリズムでは，ラティス中の各ノードに対してただ1つの前向き変数 alpha を考えていました．本発表の一般化の本当に重要な部分はここに関する違いで，ラティス中の各ノードに対して複数の前向き変数を考えていくことです．たとえば，今，ラティスのスタート地点， BOS，のノードから u1 というノードにいたるすべての系列に関する和が alpha_0 から alpha_n まであります． Alpha_0 は従来の前向き後ろ向きアルゴリズムにおける前向き変数 alpha に対応していて，以下， alpha の添え字は，この和の中のべきの数字に対応しています．これら 0 から n までの複数の前向きの変数を考える，というのが本発表で提案する一般化のキーポイントです．

前向き後ろ向きアルゴリズムの一般化 ・・・・・ ・・・・・ で，後は従来の前向きの再帰と同じ感じで，今， v というノードを考えて， v の直前のノード， u1, u2 以下あるとして， src から v にいたる経路に関する和 alpha_n(v) を計算することを考えます．まず，この和を， u1 を通るすべての経路に関する和の部分， u2 を通るすべての経路に関する和の部分，以下略，と分解します．で， u1 の和の部分のこの部分のべき乗を2項展開を用いてばらして整理すると， u1 の alpha_0 から alpha_n で表すことができます．以下， u2 の和部分も同様で，結局， v の直前のノードすべてで alpha_0 から alpha_n まで計算できていれば v の alpha_n が計算できると，こういうアルゴリズムになってます．

一般化前向きアルゴリズム 個の前向き変数を出力候補系列が成す構造上で再帰計算することで という形式の計算ができる 式の詳細に audience の注意を向けさせない．重要なのは a の漸化式 (recursion) となっていることなので，そこに注意を向けさせる． 個の前向き変数を出力候補系列が成す構造上で再帰計算することで という形式の計算ができる

一般化前向き後ろ向き アルゴリズム 式の詳細に audience の注意を向けさせない．重要なのは b の漸化式 (recursion) となっていることなので，そこに注意を向けさせる． (HMM の EM でやっているような，後ろ向きの b を用いた形式も導出できますよ，とだけ軽く言及)

実験 CRF に対するラベル F-期待値最適化の目標関数 ある出力候補系列 のラベルF-値 出力候補系列の長さ　　が可変の場合，従来の前向き後ろ向きアルゴリズムでは計算できない 一般化前向きアルゴリズムで計算できる形式

実験 テイラー展開の展開項数 M を増やすことで真の値に漸近することを確認

実験 真の値はこの和を定義どおり計算した結果を用いる テイラー展開の展開項数 M を増やすことで真の値に漸近することを確認

実験 計算は倍精度浮動少数で実行 (マシンイプシロンが 1.0e-15 程度) 計算するパラメタ・出力候補系列をいくつか変えて計算を実行

展開次数を展開次数の増加に伴って，真の値との相対誤差が減少 実験 展開次数を展開次数の増加に伴って，真の値との相対誤差が減少

実験 相対誤差が底打ちするのは， 打切り誤差以外の数値誤差が原因

実験 展開次数を増やせば増やすほど打切り誤差が減少し， 実用上十分な計算精度を達成

結論 従来の前向き後ろ向きアルゴリズムはそもそも何を計算できるのか，を示した 従来の前向き後ろ向きアルゴリズムでは取り扱えない種類の計算に関する動機付けを示した より複雑な形式の和を計算できるようアルゴリズムの一般化を提示した 複雑な形式の計算の一例がこの一般化で計算できることを実証した （フーリエ変換を用いて提案アルゴリズムを高速化できることを示した） フーリエ変換による形式はここで軽く触れる．

今後の課題 具体的な系列ラベリング問題への適用 依存関係にループのある構造に対する本一般化の拡張

[補]フーリエ変換による高速化 この の更新式を変形すると と との畳み込み この　　の更新式を変形すると と　　　　　　　　　　　　　　　　　　との畳み込み ⇒フーリエ変換により要素毎の積となり，あらかじめ高速フーリエ変換を 適用しておくことでアルゴリズムの高速化が可能．