スキップしてメイン コンテンツに移動

ヘッセ行列

Introduction


今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。
これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。
.

概要

  • ヘッセ行列の定義
  • ベクトルを用いたテイラー展開
  • 関数の最適性

ヘッセ行列の定義

仮定

f は次のような条件を満たす関数です。.
  • f はn次元ベクトルから実数値を出力します。
    このベクトルは次のように表せます。
    \[x = [x_1,x_2,,,,x_n]\]
  • \(\forall x_i , i \in {1,2,,,n}\), f は二回偏微分可能です。

定義

ヘッセ行列は \(\frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。\)
よってヘッセ行列は次のように表せます。
\[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldots & \frac{\partial^2 f}{\partial x_n^2} \\ \end{array} \right) \]

ベクトルを用いたテイラー展開

テイラー展開を二次の項まで行った式を与えます。
\[f(a+h) = f(a) + \nabla f(a) h + \frac{1}{2} h^T \nabla f(a) h + R_3\]
ただし、 \(H=\nabla ^2 f\) はヘッセ行列です。
大事なのは二次の項までで止めていることです。理由は最適化できるようにです。

関数の最適性

定置性

  • \(n \times n\)行列A が 正定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z > 0\)
  • \(n \times n\)行列A が 負定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z < 0\)
  • \(n \times n\)行列A が 半正定置
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z => 0\)
  • \(n \times n\)行列A が 半不定値
    \(\forall x \in\)n次元ベクトル空間、\(z^T A z <= 0\)
\(z^T A z\) は二次形式と呼ばれています。

最適性

もちろん上記で書いた二次の項までのテイラー展開の式は二次形式を含みます。
よって関数の最適性は次のように考えられます。
  • H(a)(ヘッセ行列) が正定置\(\implies\)f(a) は極小値.
  • H(a)(ヘッセ行列) が負定置\(\implies\) f(a) は極大値

Reference

https://ja.wikipedia.org/wiki/%E3%83%98%E3%83%83%E3%82%BB%E8%A1%8C%E5%88%97
http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-1.pdf
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp04/mp04-8.pdf
http://tau.doshisha.ac.jp/lectures/2008.calculus-II/html.dir/node43.html
Labels:

コメント

コメントを投稿

このブログの人気の投稿

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　 実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...
コメントを投稿
続きを読む

Discrete Fourier transform

Introduction 日本語 ver I will write about Discrete Fourier transform. Discrete Fourier transform is Abbreviated DFT. I am making pdf about Audio Signal Processing. I publish pdf at  github . However, I write tex in Japanese. I take a lecture about the signal processing. There is lecture at  thie page . I update this pdf.
コメントを投稿
続きを読む