Ceres-SolverのCost関数書き方比較

研究で非線形最適化が必要となり、最初はPythonのScipy.optimizeやPyOptを使ってやっていたのですが、これらのライブラリでは解空間の次元が数100次元になってくると、なぜか途中でエラーを吐いて死んでしまったり、ものすごく遅かったりしていて、つらくなってきたのでCeres-Solverを使いはじめました。

Ceres-Solverは、C++用の非線形最小二乗ソルバーライブラリです。 パラメータ変数の上限下限が設定できますが、等式／不等式制約を伴う最適化は行えません。また、最小二乗だけでなく、一般的な非線形関数最適化も行えます。 詳しい使い方は本家Tutorialが比較的わかりやすいです。

Cost関数と微分計算の書き方分類

さて、Ceres-SolverにはCost関数と微分計算の書き方がいくつかあり、以下6パターンの中から選べます（表中の名称はクラス名）。コンパイル時にサイズが分かっている問題にするか、サイズ可変にできるようにするかでClassが分かれているのと、微分の計算方式によって分類されています。

解析微分は、あらかじめ自分でCost関数を微分しておき、自分で微分計算用のコードを書く方式です。また、数値微分はライブラリがCost関数を何回か呼ぶことで近似的に微分を計算します。

さて、解析微分や数値微分は巷の最適化ライブラリでもよく見かけますが、真ん中の自動微分というのはあまり見かけません。これがCeres-Solverの一つの特徴になっていて、これはCost関数だけ自分で書いておけば、ライブラリ側で勝手に解析的な微分をやってくれる！という素晴らしい機能です。数値微分ではなく、あくまで解析的な微分です。

もちろん、このための仕組みが組み込まれていて、Cost関数の書き方も少しだけ普通とは違っています。

template <typename T>
bool operator()( const T* const x, T *res ) const
{
    res[0] = x - T(1.0);
    return true;
}

こんな感じで、ライブラリ側から型Tで現状の最適化パラメータ(x)が渡され、型Tで残差(res)を返す必要があります。なので、数値もdoubleではなくTにしてやる必要があります。Ceres-Solverのドキュメントによれば、この型TはJetというクラスのオブジェクトで呼ばれるようですが、このJetをdoubleと同様に扱って演算を行えます。ただし、別ライブラリを呼ぶなどはできず、Ceres-Solverのソースコードを見てみると四則演算と比較演算しか行えないようです。つまり、それで書ける範囲のCost関数までしか対応できないことになります。

ということなので、微分の方式は例えばこんな基準で選べばいいと思います。

微分が書きやすい ⇒ 解析微分
微分が書きづらい（四則演算で書ける） ⇒ 自動微分
微分が書きづらい（四則演算で書けない） ⇒ 数値微分

処理速度比較

とは言え。微分を自分で書けるとしても、めんどくさいのでできれば書かないで済ませたいところです。といっても、処理速度しだいです。ということで、 各手法ごとの動作速度を比較してみました。

今回、単純な線形及び2次のコスト関数の最小二乗解を求めるサンプルで時間を計測しました。具体的には、N次元空間でN枚の超平面の交点を求める問題（N=1000）と、各超平面を二乗したもの（超放物面？）の交点を求める問題です。問題に特に意味はないです。詳しくはソースコードをご覧ください。

線形の場合の処理時間

2次の場合の処理時間

これを見ると、どちらも解析⇒自動⇒数値という順で重くなっていくのは予想どおりなのですが、驚くのは自動微分については、固定サイズよりも可変サイズのほうが明らかに速いことです。これは、さっぱり意味が分かりません。普通固定サイズのほうが速いと思うのですが、、、これを見ると固定サイズの自動微分を使う理由はなさそうです。自動微分なら常に可変サイズでよいと思います。Ceres-Solverのドキュメントにも、まずは自動微分でやってみろ、みたいなことを書いてあったので、「自動微分（可変サイズ）」がイチ押しで、かなり最適化されているのかもしれません。

また、自動微分以外は、固定サイズと可変サイズの処理時間の差がほとんどないので、より柔軟性の高い可変サイズのほうを使えばよいと思います。

それと、今回は比較的単純なCost関数で微分計算が軽かったので解析微分が速かったですが、微分が複雑な場合などは数値微分よりも遅くなる可能性もあると思います。そこらへんはやってみないと分からない部分です。

お薦めはこんな感じでしょうか。

• 基本、可変サイズ用を使う
• 四則演算で書けるなら、まずは「自動微分」
• 四則演算で書けないなら、まずは「数値微分」
• 処理量に不満なら「解析微分」を試してみる

参照

• ソースコード: https://github.com/coyote009/samples/tree/master/ceres-solver_comparison
• Ceres-Solver: http://ceres-solver.org/index.html