ceres solver
ceres solver (http://ceres-solver.org/) はgoogleの公開している非線形最小二乗ソルバーです.惑星のceresが最小二乗法によって発見されたことにちなんで名づけられたようです.
非線形最小二乗法
細かい説明は他に譲るとして最小二乗法とは,以下のように二乗和で表現される式を最小にする$x \in \Re^n$を求める問題です.
Minimize: $\sum_i ||f_i(x)||^2_2$
例えば $x = [a,b]; a,b \in \Re$,$f_i(a,b) = y_i - (a t_i + b)$ とすると
Minimize: $\sum_i ||y_i - (a t_i + b)||^2$
となります.これは $(t_i,y_i)$ に最もフィットする直線 $y=ax+b$ を求める問題です.
この例は線形最小二乗法ですが,ceresはこの $f_i(x)$ が非線形関数でも扱えるソルバーです.
Ceres Solverで扱うことのできる問題
Ceresはあくまで最小二乗法を解くことに特化したソルバーです.各変数に対して上界と下界を与えることはできますが,それ以上の拘束条件(等式制約や不等式制約など)を与えることは出来ません.制約を与える必要がある場合は,二次計画問題等を解けるソルバーを使う必要があります(もしくはラグランジュ緩和).
非凸な問題に対して,当然ながら大域的最適性は保証されませんが(局所)解を求めること自体は可能です.任意の初期値を与えることも可能です.
pythonから使いたい
さて本題のpythonから使いたいって話なのですが,どちらかというと良い方法ないですか?って記事です.というのも使えそうなラッパーライブラリを見つけることは出来ませんでした.(Cythonで公開されているものがちらほらあるようですが,得体が知れないライブラリ&Cythonの経験もなかったので)
ということで以下はとりあえず私が使っている方法の紹介です.もっといい方法があればぜひ教えてください.
とりあえずpythonから使う
私の解決策はBoost.numpyを使う方法です.
恥ずかしながら私はC++をほとんどやってこなかったので名前を聞いたことがある程度だったのですが,Boostは様々なライブラリの集合体のようです.
私の理解では,Boost.pythonというのがpythonからC++の関数やクラスを呼ぶためのラッパーライブラリで,Boost.numpyはC++の関数にnumpyのndarrayやmatrixを渡すことができるラッパーライブラリです.
正直このライブラリの存在を知っていればあとは簡単です.なんせC++の部分はネイティブ(?)のコードが書けるので学習コストはほぼゼロです.Cのコードとpythonのコード両方を書かなければならないのでpythonからceresを使えているというかは怪しいですが・・・
私自身は最低限最適化の部分をCの関数で定義して,残りはすべてpythonで実装しています.個人的には今の実装方法でとりあえず満足しています,ceresに限らず基本的にC++の任意の関数(ライブラリ的にはクラスなどもラッピングできるらしいですが)を呼び出すことができるので非常に幅が広まったと思います.
参考サイト
Boost.numpyについては以下を参考にしました.CMakeListsの例もあってとても参考になりました.
Ceresについてはチュートリアルだけでも十分に分かりやすいです.