行列の条件数

エンジニアのtetsuです。

ディープラーニングを勉強されている方の中にはIan Goodfellowらによって書かれたDeep Learningという本をご存知の方も多いのではないでしょうか。この本の4章はNUMERICAL COMPUTATIONという題目となっており、そのなかには条件数(condition number)というものが紹介されています。今回はこの条件数について数値例を交えて説明していきたいと思います。

条件数(condition number)とは？

条件数とは連立一次方程式をコンピュータを用いて解く際に、どれだけ誤差が乗りやすい行列なのかを示した指標となります（実は連立一次方程式以外にも条件数を定義できますが、ここでは連立一次方程式に限定します）。行列A \in {\mathbb R^{n \times n}} に対して、その条件数はAの最大特異値\sigma_{\rm max}と最小特異値\sigma_{\rm min}を用いて次のように定義されます。

    \begin{eqnarray*} {\rm cond}(A) := \frac{\sigma_{\rm max}}{\sigma_{\rm min}} \end{eqnarray*}

Aが対称行列の場合には特異値と固有値が一致しますので、上記の最大特異値と最小特異値はそれぞれ最大固有値と最小固有値に置き換えても問題ありません。
この条件数が大きくなると、Aを係数にした連立一次方程式の解は丸め誤差の影響を大きく受けるため、誤差が大きくなりやすいです。一方で条件数が小さければ、丸め誤差の影響が小さくなります。ここで丸め誤差とはコンピュータの中で数値を有限桁で近似することで生じる誤差のことを指します。手計算とは異なり、コンピュータ上では無限桁の数値を有限桁であらわす必要があるため、丸め誤差が生じます。条件数の違いによって、この丸め誤差の影響の大きさが変化します。

連立一次方程式の数値例

ここでは行列の条件数が小さい場合と大きい場合に分けて、連立一次方程式A{\mbox{\boldmath $x$}} = {\mbox{\boldmath $b$}}を単精度でコンピュータによって解かせた例を示します。

条件数が小さい場合

行列Aとベクトル{\mbox{\boldmath $b$}}はそれぞれ次のとおりです。

    \begin{eqnarray*} A=\begin{bmatrix}0.9&-1&1&-1 \\ 1&-1&1&-1 \\ 1&-1&0&0 \\ 1&0&0&-1 \end{bmatrix},\ {\mbox{\boldmath $b$}}=\begin{bmatrix}-3\\-2\\ -1\\ -3 \end{bmatrix}. \end{eqnarray*}

この行列Aの条件数はおよそ90です。真の解 {\mbox{\boldmath $x$}}_{\rm truth}とNumPyのlinalg.solveによって求まった解 {\mbox{\boldmath $x$}}_{\rm solve}はそれぞれ次のようになります。

    \begin{eqnarray*} {\mbox{\boldmath $x$}}_{\rm truth} = \begin{bmatrix} 10\\11\\12\\13\end{bmatrix},\ {\mbox{\boldmath $x$}}_{\rm solve} = \begin{bmatrix} 9.999997\\10.99999\\11.99999\\12.99999\end{bmatrix}. \end{eqnarray*}

これらの相対誤差||{\mbox{\boldmath $x$}}_{\rm truth} - {\mbox{\boldmath $x$}}_{\rm solve}||_2 / ||{\mbox{\boldmath $x$}}_{\rm truth}||_2は1.6 \times 10^{-7}です。
この結果をみると、条件数が小さい問題では高い精度で解が得られていることがわかります。

条件数が大きい場合

続いて条件数が大きい問題となります。ここでは行列Aは

    \begin{eqnarray*} A=\begin{bmatrix}0.9999&-1&1&-1 \\ 1&-1&1&-1 \\ 1&-1&0&0 \\ 1&0&0&-1 \end{bmatrix} \end{eqnarray*}

とし、{\mbox{\boldmath $b$}}はさきほどと同じです。この行列Aの条件数はおよそ90000になります。真の解 {\mbox{\boldmath $x$}}_{\rm truth}とNumPyのlinalg.solveによって求まった解 {\mbox{\boldmath $x$}}_{\rm solve}はそれぞれ次のようになります。

    \begin{eqnarray*} {\mbox{\boldmath $x$}}_{\rm truth} = \begin{bmatrix} 10000\\10001\\10002\\10003\end{bmatrix},\ {\mbox{\boldmath $x$}}_{\rm solve} = \begin{bmatrix} 9998.340\\9999.349\\10000.34\\10001.34\end{bmatrix}. \end{eqnarray*}

これらの相対誤差||{\mbox{\boldmath $x$}}_{\rm truth} - {\mbox{\boldmath $x$}}_{\rm solve}||_2 / ||{\mbox{\boldmath $x$}}_{\rm truth}||_2は1.6 \times 10^{-4}です。
さきほどよりも精度が悪くなっていることがわかります。また条件数は前の行列よりも3桁大きくなっていますが、相対誤差もおおよそ3桁程度大きくなっています。

条件数が大きいときの対策は？

条件数が大きいときには正確な結果が得られないことが示されましたが、そのような場合にはどうすればよいのでしょうか。解法を工夫すれば解決されるのではとも思いますが、条件数というものは解法に依らずに決まり、解法を工夫して精度が改善されるという類のものではありません。
このため、高精度計算を用いることが解決方法となります。前述した例では単精度を使っていましたが、これを倍精度にしたり、4倍精度にしたりすることです。当然ながら計算時間が増えるため、精度と計算時間のバランスをみて決める必要があります。

終わりに

今回は行列の条件数について数値例を交えて説明をしました。機械学習のなかには連立一次方程式の計算が多くあらわれるため、いざというときのために知っておくと何かの役に立つかもしれませんね。

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP