ベクトルによる微分のレイアウト(分子レイアウト記法と分母レイアウト記法)
2つの異なる記法と混乱
ベクトル(や行列)による微分には2つの異なるレイアウトが用いられる。
- 分母レイアウト記法 (Denominator Layout)
- 分子レイアウト記法 (Numerator Layout)
これらは演算結果が異なるため、意識して用いないとしばしば混乱の元となる。
以下では は縦ベクトルとし、 はスカラーする。また、便宜上、ライプニッツの記法に則り「分子」は微分される関数の方、「分母」は微分する独立変数の方を表すことにする。
分母レイアウト記法 (Denominator Layout)
スカラーを微分する際、分母が縦ベクトルなら結果も縦ベクトルになる。分母が横ベクトルなら結果も横ベクトルとなる。つまり、直感的には分母のベクトル(や行列)のレイアウトが結果にそのまま反映されると解釈できる。
一方、スカラーによって微分する際は、分子が縦ベクトルなら結果は横ベクトルになる。分子が横ベクトルなら結果は縦ベクトルになる。
分子レイアウト記法 (Numerator Layout)
スカラーを微分する際、分母が縦ベクトルなら結果は横ベクトルになる。分母が横ベクトルなら結果は縦ベクトルになる。分母レイアウトとは転置したような関係となっている。
一方、スカラーによって微分する際は、分子が縦ベクトルなら結果も縦ベクトルになる。分子が横ベクトルなら結果も横ベクトルになる。つまり、直感的には分子のベクトル(や行列)のレイアウトが結果にそのまま反映されると解釈できる。
どちらを用いるべきか
分母レイアウト記法を目にする機会が多く感じるので、個人的にはこちらを推奨したい。
ただしヤコビ行列の定義は分子レイアウトを採用していることが多く感じるため、悩ましい。
関連リンク
知覚を考慮した色差 CIEDE2000 とその実装
色差の指標 CIEDE2000
色差、つまり2つの色の距離を計算する方法はいくつかあるが、人間の知覚を考慮した指標である CIEDE2000 を用いるのが良いことが多い。
知覚を考慮しているとは、例えば人間にとって見分けのつきにくい色同士は (たとえ RGB の値が遠くても) 距離が近く、人間にとって見分けのつきやすい色同士は距離が遠くなるように設計されていることを意味している。
CIEDE2000 の数式
具体的な数式は複雑だが、下記文献を参照すると実装はそれほど難しくない。計算は CIELAB 色空間に基づいている。詳細は割愛する。
- Sharma, G., Wu, W., & Dalal, E. N. (2005). The CIEDE2000 color‐difference formula: Implementation notes, supplementary test data, and mathematical observations. Color Research & Application, 30(1), 21-30. https://onlinelibrary.wiley.com/doi/full/10.1002/col.20070
CIEDE2000 の実装
下記の GitHub レポジトリに CIEDE2000 の実装を公開した。なお、CIEDE2000 の計算に必要な色空間の変換(RGB から CIELAB へ)も実装に含まれている。C++11 で記述している。Header-only ライブラリとして利用可能になっている。ライセンスは MIT License とした。
他の色差計算手法との比較
RGB 色空間におけるユークリッド距離
これは色の距離を測る際の最も単純な方法の一つであり、しばしば用いられる。冒頭の図でも CIEDE2000 の結果との比較のために用いた。次の式で色差が計算される。
しかし、この指標は人間の知覚特性を考慮していない。
CIELAB 色空間におけるユークリッド距離
人間の知覚を考慮するために、RGB 色空間ではなく CIELAB 色空間におけるユークリッド距離を用いる方法があり、これもしばしば用いられる。なお、CIELAB 色空間とはここではCIE 1976 (L*, a*, b*) 色空間を指す。単に Lab 色空間とも呼ばれる。次の式で色差が計算される。
なお、この色差の指標は CIE76 とも呼ばれる。
設計された当時、CIE76 は人間の知覚をよく反映した指標だとということになっていたようだが、それでもやはり人間の知覚特性を完全に再現できているわけではない。後により精度が高いとされる指標が提案されることになり、現在では CIEDE2000 が人間の知覚をよく反映した指標だということになっている。
macOSでCMakeを使ってビルドする際にQt 5へのパスを渡す
Qt 5をライブラリとして用いるプログラムをCMakeを使ってビルドする際、例えばQt 5 Widgetsを使う場合はCMakeLists.txtに
find_package(Qt5Widgets REQUIRED)
または
find_package(Qt5 COMPONENTS Widgets REQUIRED)
などと記述することになります*1。
しかしmacOSでは、これに対して単に
cmake [path for the project root]
と実行すると、
CMake Error at CMakeLists.txt:4 (find_package): By not providing "FindQt5Widgets.cmake" in CMAKE_MODULE_PATH this project has asked CMake to find a package configuration file provided by "Qt5Widgets", but CMake did not find one. Could not find a package configuration file provided by "Qt5Widgets" with any of the following names: Qt5WidgetsConfig.cmake qt5widgets-config.cmake Add the installation prefix of "Qt5Widgets" to CMAKE_PREFIX_PATH or set "Qt5Widgets_DIR" to a directory containing one of the above files. If "Qt5Widgets" provides a separate development package or SDK, be sure it has been installed.
というエラーが表示されてしまいます。これの意味は、CMakeからはQt 5 (ここでは特にQt5Widgets) が発見できなかった、ということです。
これの解決策の一つは、エラー表記にも書いてある通り、CMAKE_PREFIX_PATHを指定することです*2。
例えば公式サイトのパッケージからQt 5 (ver. 5.8) をインストールしてある場合、デフォルトの設定でインストールされていれば次のようにパスを指定することになります。
cmake [path for the project root] -DCMAKE_PREFIX_PATH=~/Qt/5.8/clang_64/
Homebrewを使ってQt 5 (ver. 5.10.0) インストールしてある場合は次のようになります。
cmake [path for the project root] -DCMAKE_PREFIX_PATH=/usr/local/Cellar/qt/5.10.0
Homebrewの場合は次のように指定することもできます。
cmake [path for the project root] -DCMAKE_PREFIX_PATH=$(brew --prefix qt5)
等式制約あり最適化問題と拡張ラグランジュ乗数法
拡張ラグランジュ乗数法
等式制約あり最適化問題
を解くためのアルゴリズムとして、拡張ラグランジュ乗数法 (augmented Lagrangian algorithm) という手法があります。これは、同じく制約あり最適化問題を扱うための手法であるラグランジュの未定乗数法 (the method of Lagrange multipliers) やペナルティ法 (penalty method) とよく似ていますが、これらよりもより実用的な手法となっています。
ラグランジュの未定乗数法
ラグランジュの未定乗数法ではラグランジュ関数 (Lagrange function)
を考え、これの と に対する偏微分が全て 0 となる状態を探索する(例えばラグランジュ関数を目的関数とみなして制約なし最適化問題を解く*2)ことで等式制約あり最適化問題を解きます。
ペナルティ法
ペナルティ法では「等式制約がどれだけ満たされていないか」に対応する項(ペナルティ)を目的関数に足した制約なし最適化問題
を考え、これを解くことで、元の等式制約あり最適化問題を解きます*3。一回ではなく、徐々に係数 の値を大きくしていき () ながら、繰り返しこの問題を解くことで、等式制約が(ほぼ)満たされた解を得られることになります。
この手法は、 の値が大きくなったときに数値的に不安定な問題となってしまうという問題があります。
拡張ラグランジュ乗数法
拡張ラグランジュ乗数法では、ラグランジュ関数を上述のペナルティ項によって拡張したようなもの (= 拡張ラグランジュ関数) を制約なし最適化問題の目的関数とみなし、これを繰り返し解くことで、元の等式制約あり最適化問題を解きます。具体的には、
という問題を繰り返し解いていきます。その際、
という更新をしていきます*4。ペナルティ法同様に の値は増加していきますが、ラグランジュ乗数 が更新されていく分だけ制約 が満たされた状態に近づくという性質があり*5、ペナルティ法に比べずっと小さい でも有用な解に辿り着くことができます。
- Augmented Lagrangian method - Wikipedia
- http://www.math.cm.is.nagoya-u.ac.jp/~kanamori/lecture/lec.2007.1st.suurijouhou1/Suuri1.html
なお拡張ラグランジュ乗数法は "the original method of multipliers" と呼ばれることもあるようです*6*7。
ライブラリを用いた利用例
NLopt というライブラリには拡張ラグランジュ乗数法が実装されており、これを呼び出すことで簡単に等式制約あり最適化問題を解くことができます。
以下の C++ による実装例では
という等式制約あり最適化問題を解いています。内部で繰り返し解く制約なし最適化問題に使用するアルゴリズムとして Nelder-Mead 法を指定しています。
#include <iostream> #include <nlopt.hpp> // f(x, y) = x + y double objective_function(const std::vector<double> &x, std::vector<double>& /*grad*/, void* /*data*/) { return x[0] + x[1]; } // g(x, y) = x^2 + y^2 - 1 double equality_constraint(const std::vector<double> &x, std::vector<double>& /*grad*/, void* /*data*/) { return x[0] * x[0] + x[1] * x[1] - 1.0; } int main() { // Specify the augmented Lagrangian algorithm nlopt::opt optimizer(nlopt::LN_AUGLAG, 2); // Specify the objective function and the equality constraint optimizer.set_max_objective(objective_function, nullptr); optimizer.add_equality_constraint(equality_constraint, nullptr); // Specify the Nelder-Mead algorithm for solving each step nlopt::opt local_optimizer(nlopt::LN_NELDERMEAD, 2); optimizer.set_local_optimizer(local_optimizer); // Set initial solution std::vector<double> x = { 0.0, 0.0 }; // Run optimization try { double value; optimizer.optimize(x, value); } catch (std::runtime_error e) { std::cerr << e.what() << std::endl; } // Print the result std::cout << "Solution: " << x[0] << ", " << x[1] << std::endl; return 0; }
C++による実装例 (2018/2/13追記)
等式制約あり最適化問題を、ペナルティ法および拡張ラグランジュ乗数法で解くサンプルプログラムを公開しました。
C++11 で記述されており、制約なし最適化問題を解くために NLopt が使用されています。ソースコードは CMake で管理されています。
*1:ここでは簡単のため制約条件は1つとしていますが、任意の個数の制約条件がある場合でも基本的な考え方は変わりません。
*2:2018/02/12追記: 英語版 Wikipedia によると、 に対する偏微分が 0 になる点はラグランジュ関数の極小値や極大値ではなく停留点 (saddle point) となるらしく、通常の数値最適化アルゴリズムでラグランジュ関数を目的関数として計算しても解を発見できないようです。そこで、ラグランジュ関数そのものではなく、例えばラグランジュ関数の勾配の大きさを最小化するように数値最適化問題を解くことで、元々の等式制約あり最適化問題の解を得られるそうです。
*3:ペナルティ法では等式制約だけでなく不等式制約も扱うことができます。
*4:ただしパラメタ更新方法には様々な亜種があるようです。
*5:証明は教科書等を参照。
*6:http://www.mit.edu/~dimitrib/lagr_mult.html
*7:Interactive High-Quality Green-Screen Keying via Color Unmixing – Yağız Aksoy