k-best MIRAはk=1のときはclosed-formで重み更新式が書けるが、k>1のときはclosed-formでは解くことができない。k>1のときに解が欲しければ、真面目にQPを解く必要がある。MSTParserの中で使われているQPを解くアルゴリズムにはHildreth algorithmが使われている。
Hildreth algorithm自体について説明しているWeb上のリソースはあまりないが、以下のサイトは雰囲気がつかめる。SMOのようにひとつの変数に着目して、それ以外は止めて一変数について最適化、というのを繰り返すようである。
Hildreth algorithmで出力されるのは双対変数なので、主問題の変数には変換する必要があることに注意。
- http://www.seas.upenn.edu/~strctlrn/MSTParser/MSTParser.html
- MSTparser。Parameters.javaにHildreth algorithmが書かれている
- http://www.seas.upenn.edu/~strctlrn/StructLearn/StructLearn.html
- 正則化あり(スラック変数あり。Cあり)の場合に対してHildreth algorithmを動かしたい場合。Cが双対変数の値の上限値になるので、双対変数が暴れる場合はこっちの適用を考えたほうがよさそう
- https://code.google.com/p/thebeast/
- これにも正則化ありで動くコードがある
- http://www.cs.bgu.ac.il/~yoavg/fs/hildreth.pyx
- pythonによる実装。短い