ベクトルによる微分のレイアウト(分子レイアウト記法と分母レイアウト記法)

2つの異なる記法と混乱

ベクトル(や行列)による微分には2つの異なるレイアウトが用いられる。

  • 分母レイアウト記法 (Denominator Layout)
  • 分子レイアウト記法 (Numerator Layout)

これらは演算結果が異なるため、意識して用いないとしばしば混乱の元となる。

以下では \mathbf{x} \in \mathbb{R}^{n \times 1} は縦ベクトルとし、y \in \mathbb{R}スカラーする。また、便宜上、ライプニッツの記法に則り「分子」は微分される関数の方、「分母」は微分する独立変数の方を表すことにする。

分母レイアウト記法 (Denominator Layout)

スカラー微分する際、分母が縦ベクトルなら結果も縦ベクトルになる。分母が横ベクトルなら結果も横ベクトルとなる。つまり、直感的には分母のベクトル(や行列)のレイアウトが結果にそのまま反映されると解釈できる。

\displaystyle{
\frac{\partial y}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial y}{\partial x_1} \\ \vdots \\ \frac{\partial y}{\partial x_n} \end{bmatrix} \in \mathbb{R}^{n \times 1}
}

一方、スカラーによって微分する際は、分子が縦ベクトルなら結果は横ベクトルになる。分子が横ベクトルなら結果は縦ベクトルになる。

\displaystyle{
\frac{\partial \mathbf{x}}{\partial y} = \begin{bmatrix} \frac{\partial x_1}{\partial y} & \cdots & \frac{\partial x_n}{\partial y} \end{bmatrix} \in \mathbb{R}^{1 \times n}
}

分子レイアウト記法 (Numerator Layout)

スカラー微分する際、分母が縦ベクトルなら結果は横ベクトルになる。分母が横ベクトルなら結果は縦ベクトルになる。分母レイアウトとは転置したような関係となっている。

\displaystyle{
\frac{\partial y}{\partial \mathbf{x}} = \begin{bmatrix} \frac{\partial y}{\partial x_1} & \cdots & \frac{\partial y}{\partial x_n} \end{bmatrix} \in \mathbb{R}^{1 \times n}
}

一方、スカラーによって微分する際は、分子が縦ベクトルなら結果も縦ベクトルになる。分子が横ベクトルなら結果も横ベクトルになる。つまり、直感的には分子のベクトル(や行列)のレイアウトが結果にそのまま反映されると解釈できる。

\displaystyle{
\frac{\partial \mathbf{x}}{\partial y} = \begin{bmatrix} \frac{\partial x_1}{\partial y} \\ \vdots \\ \frac{\partial x_n}{\partial y} \end{bmatrix} \in \mathbb{R}^{n \times 1}
}

どちらを用いるべきか

分母レイアウト記法を目にする機会が多く感じるので、個人的にはこちらを推奨したい。

ただしヤコビ行列の定義は分子レイアウトを採用していることが多く感じるため、悩ましい。

関連リンク

知覚を考慮した色差 CIEDE2000 とその実装

色差の指標 CIEDE2000

色差、つまり2つの色の距離を計算する方法はいくつかあるが、人間の知覚を考慮した指標である CIEDE2000 を用いるのが良いことが多い。

知覚を考慮しているとは、例えば人間にとって見分けのつきにくい色同士は (たとえ RGB の値が遠くても) 距離が近く、人間にとって見分けのつきやすい色同士は距離が遠くなるように設計されていることを意味している。

f:id:yuki-koyama:20180504132639p:plain CIEDE2000 を用いることで、より人間の知覚に沿った色差を計算できる。両ペアは RGB 色空間では等しい距離を持つが、人間には左のペアの方が色が遠く、右のペアの方が色が近いと知覚されることが CIEDE2000 の計算に反映されている。*1

CIEDE2000 の数式

具体的な数式は複雑だが、下記文献を参照すると実装はそれほど難しくない。計算は CIELAB 色空間に基づいている。詳細は割愛する。

CIEDE2000 の実装

下記の GitHub レポジトリに CIEDE2000 の実装を公開した。なお、CIEDE2000 の計算に必要な色空間の変換(RGB から CIELAB へ)も実装に含まれている。C++11 で記述している。Header-only ライブラリとして利用可能になっている。ライセンスは MIT License とした。

github.com

他の色差計算手法との比較

RGB 色空間におけるユークリッド距離

これは色の距離を測る際の最も単純な方法の一つであり、しばしば用いられる。冒頭の図でも CIEDE2000 の結果との比較のために用いた。次の式で色差が計算される。

{ \displaystyle
d = \sqrt{ (r_1 - r_2)^2 + (g_1 - g_2)^2 + (b_1 - b_2)^2 }
}

しかし、この指標は人間の知覚特性を考慮していない。

CIELAB 色空間におけるユークリッド距離

人間の知覚を考慮するために、RGB 色空間ではなく CIELAB 色空間におけるユークリッド距離を用いる方法があり、これもしばしば用いられる。なお、CIELAB 色空間とはここではCIE 1976 (L*, a*, b*) 色空間を指す。単に Lab 色空間とも呼ばれる。次の式で色差が計算される。

{ \displaystyle
d = \sqrt{ (L^*_1 - L^*_2)^2 + (a^*_1 - a^*_2)^2 + (b^*_1 - b^*_2)^2 }
}

なお、この色差の指標は CIE76 とも呼ばれる。

設計された当時、CIE76 は人間の知覚をよく反映した指標だとということになっていたようだが、それでもやはり人間の知覚特性を完全に再現できているわけではない。後により精度が高いとされる指標が提案されることになり、現在では CIEDE2000 が人間の知覚をよく反映した指標だということになっている。

*1:ここでは sRGB 色空間を仮定して 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)

等式制約あり最適化問題と拡張ラグランジュ乗数法

拡張ラグランジュ乗数法

等式制約あり最適化問題

\displaystyle{
\min_{\mathbf{x}} \: f(\mathbf{x}) \:\: \text{s.t.} \:\: g(\mathbf{x}) = 0
} *1

を解くためのアルゴリズムとして、拡張ラグランジュ乗数法 (augmented Lagrangian algorithm) という手法があります。これは、同じく制約あり最適化問題を扱うための手法であるラグランジュの未定乗数法 (the method of Lagrange multipliers)ペナルティ法 (penalty method) とよく似ていますが、これらよりもより実用的な手法となっています。

ラグランジュの未定乗数法

ラグランジュの未定乗数法ではラグランジュ関数 (Lagrange function)

\displaystyle{
\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x})
}

を考え、これの \mathbf{x}\lambda に対する偏微分が全て 0 となる状態を探索する(例えばラグランジュ関数を目的関数とみなして制約なし最適化問題を解く*2)ことで等式制約あり最適化問題を解きます。

ペナルティ法

ペナルティ法では「等式制約がどれだけ満たされていないか」に対応する項(ペナルティ)を目的関数に足した制約なし最適化問題

\displaystyle{
\min_{\mathbf{x}} \: \left\{ \: f(\mathbf{x}) + \frac{1}{2} \mu \{ g(\mathbf{x}) \} ^2 \right\}
}

を考え、これを解くことで、元の等式制約あり最適化問題を解きます*3。一回ではなく、徐々に係数  \mu の値を大きくしていき (\mu \rightarrow \infty) ながら、繰り返しこの問題を解くことで、等式制約が(ほぼ)満たされた解を得られることになります。

この手法は、\mu の値が大きくなったときに数値的に不安定な問題となってしまうという問題があります。

拡張ラグランジュ乗数法

拡張ラグランジュ乗数法では、ラグランジュ関数を上述のペナルティ項によって拡張したようなもの (= 拡張ラグランジュ関数) を制約なし最適化問題の目的関数とみなし、これを繰り返し解くことで、元の等式制約あり最適化問題を解きます。具体的には、

\displaystyle{
\min_{\mathbf{x}} \: \left\{ \: f(\mathbf{x}) + \frac{1}{2} \mu \{ g(\mathbf{x}) \} ^2 - \lambda g(\mathbf{x}) \right\}
}

という問題を繰り返し解いていきます。その際、

\displaystyle{
\lambda \leftarrow \lambda - \mu g(\mathbf{x}) \\
\mu \leftarrow \alpha \mu \:\: (\alpha > 1)
}

という更新をしていきます*4。ペナルティ法同様に \mu の値は増加していきますが、ラグランジュ乗数 \lambda が更新されていく分だけ制約 g(\mathbf{x}) = 0 が満たされた状態に近づくという性質があり*5、ペナルティ法に比べずっと小さい \mu でも有用な解に辿り着くことができます。

なお拡張ラグランジュ乗数法は "the original method of multipliers" と呼ばれることもあるようです*6*7

ライブラリを用いた利用例

NLopt というライブラリには拡張ラグランジュ乗数法が実装されており、これを呼び出すことで簡単に等式制約あり最適化問題を解くことができます。

以下の C++ による実装例では

\displaystyle{
\min_{x, y} \: x + y \:\: \text{s.t.} \:\: x^2 + y^2 = 1
}

という等式制約あり最適化問題を解いています。内部で繰り返し解く制約なし最適化問題に使用するアルゴリズムとして 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追記)

等式制約あり最適化問題を、ペナルティ法および拡張ラグランジュ乗数法で解くサンプルプログラムを公開しました。

github.com

C++11 で記述されており、制約なし最適化問題を解くために NLopt が使用されています。ソースコードは CMake で管理されています。

*1:ここでは簡単のため制約条件は1つとしていますが、任意の個数の制約条件がある場合でも基本的な考え方は変わりません。

*2:2018/02/12追記: 英語版 Wikipedia によると、\lambda に対する偏微分が 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