双対分解を理解するノート

元々の発端は
http://aclweb.org/anthology/P/P13/P13-2004.pdf


岡野原さんによるレポート
http://research.preferred.jp/2010/11/dual-decomposition/

双対分解とは,argmax_y( g(y) + h(y) )が解けなくても(NP完全だから),argmax_z,y( g(z) + h(y) ) st. z=y にすれば解けますよ.という分解のことを指す.


argmax_z,y ( g(z) + h(y) )の解をL*とする.
argmax_z,y ( g(z) + h(y) ) st. z=y にラグランジュの定理を適応してL(u)を定義する.

双対定理ってのがあって,
L* = min_u L(u)
らしい.


L(u)は凸関数(らしい)ので,勾配法を用いてとける.
実際,確率的勾配法を用いて解けるらしい.


勾配の更新時に
u:=u–μ(y∗–z∗)

の式で,y* = z*の時に,主問題と双対問題が一致しているので,この時の値が最適解になる.


ではNLPへの応用は?
先も書いたとおり,argmax_y( g(y) + h(y) )が解けない問題(つまり探索空間が大きすぎる場合)に双対分解は有効.


その他にも,条件を2つ考えて,関数Aに1つの仕事をやらせ,関数Bにもうひとつの仕事をやらせ,解を一致する場合を採用する.というアイディアから次の使い方もできる.
以下,引用.


Kooらは、a. 抽出されるグラフが木の条件を満たすが、親子関係の情報しかスコアに反映させない b. 親兄弟についての情報を自由にスコアに反映できるが、抽出されるグラフが木である保障はない というa. b. の二つの解を一致させるという最適化問題を解くことにより、出力が木であることが保障されていながら自由に情報を利用できる係り受け解析木を作りました。



(略)


同時に利用することが一見できなさそうな特徴量やルールもこの方法を利用することで統合することができます。
自然言語処理のように複数の処理のパイプラインによって問題を解く場合や、複数の情報/システムを結合させるような場合、また最適化の制約のせいで、重要な情報を利用できない場合などに有効な方法だと考えられます。



引用おわり.
らしい.


ちなみに構造学習にはACLのチュートリアルがあるらしい(Hal Daumeの)
http://www.umiacs.umd.edu/~hal/SPIRL/10-07-acl-spirl.pdf