# Hildreth algorithm
k-best MIRAはk=1のときはclosed-formで重み更新式が書けるが、k>1のときはclosed-formでは解くことができない。k>1のときに解が欲しければ、真面目にQPを解く必要がある。MSTParserの中で使われているQPを解くアルゴリズムにはHildreth algorithmが使われている。

Hildreth algorithm自体について説明しているWeb上のリソースはあまりないが、以下のサイトは雰囲気がつかめる。SMOのようにひとつの変数に着目して、それ以外は止めて一変数について最適化、というのを繰り返すようである。

- http://user.engineering.uiowa.edu/~dbricker/Stacks_pdf8/QP_H%26E.pdf

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による実装。短い

# 参考になるWebサイト
- http://metaoptimize.com/qa/questions/7029/open-access-description-of-the-hildreth-algorithm