勾配法
提供: Internet Web School
一次アルゴリズム
UNIQ37b9eb6f3611c8a7-MathJax-56-QINU を例にとる.UNIQ37b9eb6f3611c8a7-MathJax-57-QINUを列ベクトルと行列
UNIQ37b9eb6f3611c8a7-MathJax-58-QINU
を使って表現すると
UNIQ37b9eb6f3611c8a7-MathJax-59-QINU
から UNIQ37b9eb6f3611c8a7-MathJax-60-QINU と書ける．
ここで,UNIQ37b9eb6f3611c8a7-MathJax-61-QINUのUNIQ37b9eb6f3611c8a7-MathJax-62-QINUについての偏微分係数はそれぞれ,
UNIQ37b9eb6f3611c8a7-MathJax-63-QINU
である。これらを要素にもつ列ベクトルは, UNIQ37b9eb6f3611c8a7-MathJax-64-QINUのUNIQ37b9eb6f3611c8a7-MathJax-65-QINUについて の微分であり,
UNIQ37b9eb6f3611c8a7-MathJax-66-QINU
である。
また,UNIQ37b9eb6f3611c8a7-MathJax-67-QINUの２階微分は
UNIQ37b9eb6f3611c8a7-MathJax-68-QINU である。
UNIQ37b9eb6f3611c8a7-MathJax-69-QINU とすると
UNIQ37b9eb6f3611c8a7-MathJax-70-QINU
である.
これを一般化する.関数UNIQ37b9eb6f3611c8a7-MathJax-71-QINUが解析的な関数なら,
UNIQ37b9eb6f3611c8a7-MathJax-72-QINU
となる．UNIQ37b9eb6f3611c8a7-MathJax-73-QINUは３次以上の高位の項である。
勾配を使う計算法
UNIQ37b9eb6f3611c8a7-MathJax-74-QINUを最小化するため先ず,
初期点 UNIQ37b9eb6f3611c8a7-MathJax-75-QINU を与えて,UNIQ37b9eb6f3611c8a7-MathJax-76-QINUを求め,次に,
UNIQ37b9eb6f3611c8a7-MathJax-77-QINUでのUNIQ37b9eb6f3611c8a7-MathJax-78-QINUの微分,
UNIQ37b9eb6f3611c8a7-MathJax-79-QINU
を求め,これと微小な正数UNIQ37b9eb6f3611c8a7-MathJax-80-QINUを使って,
UNIQ37b9eb6f3611c8a7-MathJax-81-QINU
として,UNIQ37b9eb6f3611c8a7-MathJax-82-QINUを計算すると,
UNIQ37b9eb6f3611c8a7-MathJax-83-QINU
ここで,任意のベクトル UNIQ37b9eb6f3611c8a7-MathJax-84-QINU について
UNIQ37b9eb6f3611c8a7-MathJax-85-QINU であるからUNIQ37b9eb6f3611c8a7-MathJax-86-QINUである。
同様に,
UNIQ37b9eb6f3611c8a7-MathJax-87-QINU
UNIQ37b9eb6f3611c8a7-MathJax-88-QINU
である。
UNIQ37b9eb6f3611c8a7-MathJax-89-QINUが十分小さければ, UNIQ37b9eb6f3611c8a7-MathJax-90-QINU として, UNIQ37b9eb6f3611c8a7-MathJax-91-QINU となる．
UNIQ37b9eb6f3611c8a7-MathJax-92-QINU を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．
特に,毎回の繰り返しで,
UNIQ37b9eb6f3611c8a7-MathJax-93-QINU
となるように,UNIQ37b9eb6f3611c8a7-MathJax-94-QINUを選ぶ繰り返し計算法を最急降下法と呼ぶ．
UNIQ37b9eb6f3611c8a7-MathJax-95-QINU
を繰り返しながら
UNIQ37b9eb6f3611c8a7-MathJax-96-QINU
を生成し, UNIQ37b9eb6f3611c8a7-MathJax-97-QINU
とする計算法は,一次アルゴリズムと呼ばれている．
2次アルゴリズム
UNIQ37b9eb6f3611c8a7-MathJax-98-QINU
を使って,高速なアルゴリズムを造る．
UNIQ37b9eb6f3611c8a7-MathJax-99-QINU
とおき,上の式の右辺を書き換える．
UNIQ37b9eb6f3611c8a7-MathJax-100-QINU
これはUNIQ37b9eb6f3611c8a7-MathJax-101-QINUについての２次式である。この式がUNIQ37b9eb6f3611c8a7-MathJax-102-QINUについて,極小になるための 条件は,極値条件(UNIQ37b9eb6f3611c8a7-MathJax-103-QINUについての微分がUNIQ37b9eb6f3611c8a7-MathJax-104-QINUベクトル)
UNIQ37b9eb6f3611c8a7-MathJax-105-QINU
である。これから,行列 UNIQ37b9eb6f3611c8a7-MathJax-106-QINU が正則(逆行列をもつ)とすれば,
UNIQ37b9eb6f3611c8a7-MathJax-107-QINU
が得られる．
UNIQ37b9eb6f3611c8a7-MathJax-108-QINU を繰り返すアルゴリズムはニュートン法と呼ばれる．
